HomeArchivesTagsCategories
连通域提取的FPGA设计
|fpga

摘要

关于连通域提取算法的FPGA设计。与传统基于CPU的设计比具有低延时、资源消耗少的优点。

什么是连通域提取

连通域提取演示

连通域提取一般是针对二值图像（只有0和1），它就是把连通着的1的部分标记出来。至于什么是连通，又分为4连通与8连通。我们采用8连通，更符合人的直觉。

连通域matlab处理结果

可以看到，总共有12个区域。顺序排列是从图像的最左边开始，面积依次为38,93,167,32…

中心为[50.6579,147.6842]，[57.2581,15.8495]… 坐标原点为图像左上角，先X后Y。

你可以下载下面的图像，在本地的matlab上，跑下面这段.m脚本，获得更直观的理解，matlab将此功能封装在regionprops函数，可以说是非常简单了。
点击图像，右键另存为data.jpg即可
matlab脚本如下：你需要更改第3行的图像路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
clc; clear all; close all;

src_img = 'C:/Users/zhang/Desktop/data.jpg';
img = imread(src_img);

T = graythresh(img);
bw_img = im2bw(img, T);

img_reg = regionprops(bw_img,  'area', 'boundingbox');

areas = [img_reg.Area];
rects = cat(1,  img_reg.BoundingBox);

figure(1),
imshow(bw_img);title('测试数据');

figure(2),
imshow(bw_img);title('连通域边界标记');
for i = 1:size(rects, 1)
    rectangle('position', rects(i, :), 'EdgeColor', 'r');
end

region_detail = regionprops(bw_img);  % see this varible in workspace for detail 
endl=1

CPU处理存在的问题

  • 需要加载完一张图像，才开始处理，算法延时高
  • 需要存储一张图像，存储资源消耗大

FPGA能解决这样的问题吗

  • 图像边传输，边处理，一个一个像素进行处理
  • 事实上连通域只与周围的像素有关，存储周围的像素即可

问题就这么简单吗

我们看这样一张图片，80即图像中亮的部分
V形图片

从左上开始，按照行方向进行逐像素扫描。我们会得到这样的结果(2,2)(第一个连通域)、(2,8)（第二个连通域），（3,3)(第一个连通域，与（2,2）连通)、（3,7)(第二个连通域，与（2,8）连通）…

这样一直下去，到（5,5）就会有一个神奇的变化。（5,5）起到了纽带作用，将两片独立的连通域连接到了一起，我们前面标记的如（2,2）与（2,8）实际是连通的，但是在第二行的局部看，我们不可能知道。

这样就需要一个连通域合并判断。合并之后需要将所有第二个连通域（简称标号为2）转成标号是1，这依然有可能需要大量的存储器（极限是一幅图），这对于FPGA设计是不现实的！

深入思考之后😳反复尝试之后，可以发现，只需要对上一行的标号2连通域（而不是所有的标号2连通域）更新为标号1就可以了，之后对两个连通域的信息进行合并（如面积、灰度和、边界），而其他内部的元素标号改不改是没有影响的。

这样就变成了需要一行的存储器，即便对于1080p这样的分辨率，一行1920个像素，FPGA存储器是足够的且微不足道的（这都不是事儿）。

我相信大部分人看完这样的描述，依然是一头雾水😅。对于一个算法的理解，一般是这样的过程。这里只是初步看一下，看不懂没有关系（非常正常），这里提供可信的已经完成的代码，先确定代码是好使的，至于为什么这样做就能简单好使，需要你自己去调一调、试一试。

如何知道设计是可行的（强大的测试）

代码好不好使，当然是看测试用例了。给几组输入，看看结果，与MATLAB或者人的直观感觉，对比一下就ok。

测试用例1

我们用前面的V形图像作为输入，来看一下iverilog仿真的结果
V形图像仿真结果

这里注意几点

  • 所有数据是在fs下降沿（一帧图像完成后）间隔2个时钟开始输出，处理是边接收边处理的，延时低。
  • e_label是连通域标号，e_upm（外接矩形上边界），e_dw（外接矩形下边界），e_le（外接矩形左边界），e_ri（外接矩形右边界），e_num_gray（连通域像素个数），e_sum_gray（连通域像素总和）。
  • 这里输出了两个连通域，但标号2像素个数是0,这样的连通域是被合并过的连通域，后续可以删除。
  • 连通域1的信息是最终的结果，7个像素，总和560（7*80），上边界2，下边界5，左边界2，右边界8。结果是正确的。

我们深入细节，看一下算法的过程：
V形图像仿真细节

标号1（label1）的连通域像素个数（num_gray1）变化为1-2-3-7。标号2（label2）的连通域像素个数（num_gray1）变化为1-2-3-0：起到了连通域合并的效果。

进一步分析，外接矩形边界（upm,dw,le,ri）的变化，理解程序的执行过程。

觉得这样的测试，Too Young Too Simple? 可能程序的正确只是一种巧合？

测试用例2

我们采用lena图二值化后进行测试。

考虑到iverilog仿真的速度问题，我们采用32*32低一点的分辨率及进行测试，但程序是适用于1080p的，从逻辑的角度讲，两者没有差别，只是资源消耗有差别。

32*32 二值化后LENA

lena_32_32仿真结果

​ 这个结果，通过直觉来看，总共应该有7个连通域。像素个数分别是61,1,222,98,10,1,2。Looks not bad。

我们跟matlab对比一下
matlab_lena_32_32仿真结果

  • Area 对应像素个数，两者是一致的。
  • Bounding Box 与这里的格式不一致，matlab里的Bounding Box [x1,x2,x3,x4] , x3, x4 表示的是矩形的长和宽像素数=（dw-upm+1）or =（ri-le+1）。x1,x2是矩形左上角位置。matlab上向上取整后，与（le,upm）一致。个人感觉左上角不应是小数。对matlab机制，这里不做深入讨论（其实我也不懂😳）。

是时候安利一波源码及仿真使用了

模块架构

文件依赖

文件结构图
注：（蓝字部分是需要使用的设计文件，黑字部分为xilinx ip，只需要指定参数并调用xilinx ip core）。

模块依赖

模块结构图

模块端口

connect_domain_get

端口类型 名称 描述 备注
输入 clk 数据时钟
rst_n 复位信号，低有效
fs 场同步
hs 行同步
data 图像数据
hang_cnt_out 当前像素是第几行
lie_cnt_out 当前像素是第几列
输出 e_label 连通域标号
e_le 连通域外接矩形左边界
e_ri 连通域外接矩形右边界
e_upm 连通域外接矩形上边界
e_dw 连通域外接矩形下边界
e_sum_gray 连通域图像灰度总和
e_num_gray 连通域图像像素个数

u_get_around

端口类型 名称 描述 备注
输入 clk 数据时钟
rst_n 复位信号，低有效
fs 场同步
hs 行同步
data 图像数据
输出 middle 当前像素（正中间）
up_right1 右上像素
up_middle1 中上像素
up_left1 左上像素
left 左边像素
fs_neg 场同步下降沿
hs_neg 行同步下降沿

源码使用

所有的代码均共享在Github。verilog设计文件在zhangxin6/iverilog_testbench，xilinx ip core文件在zhangxin6/manage_ip
如果你会使用Github，推荐使用命令行中的Git下载

1
2
git clone git@github.com:zhangxin6/iverilog_testbench.git
git clone git@github.com:zhangxin6/manage_ip.git

反之，你可以通过上面的链接，通过Download ZIP下载。
insert0 iverilog仿真波形
这里提供file_io_testbench.v及iverilog仿真的file_io_testbench.bat供参考。双击file_io_testbench.bat即可实现仿真！

file_io_testbench.bat

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
@echo off
set testbench=file_io_testbench

set iverilog_path=c:\iverilog\bin;
set gtkwave_path=c:\iverilog\gtkwave\bin;
set path=%iverilog_path%%gtkwave_path%%path%

set dir=C:\Users\zhang\iverilog_testbench
set ip_dir=C:\Users\zhang\manage_ip
set batdir=C:\Users\zhang\iverilog_testbench\bat

set s1=%dir%\file_io_testbench.v
set s2=%dir%\data_gen.v
set s3=%dir%\connect_domain_get.v

set ip1="%ip_dir%\delay_1hang\simulation\blk_mem_gen_v8_4.v"
set ip2="%ip_dir%\delay_1hang\sim\delay_1hang.v"

set vivado_dir=C:\Xilinx\Vivado\2018.2\data\verilog\src
set vivado_lib="-y%vivado_dir%" "-y%vivado_dir%\retarget" "-y%vivado_dir%\unifast" "-y%vivado_dir%\unimacro" "-y%vivado_dir%\unisims" "-y%vivado_dir%\xeclib"

iverilog -g2012 -o "%batdir%\%testbench%.vvp" %vivado_lib% %s1% %s2% %s3% %ip1% %ip2% %vivado_dir%/glbl.v

vvp "%batdir%\%testbench%.vvp"

set gtkw_file="%batdir%\%testbench%.gtkw"
if exist %gtkw_file% (gtkwave %gtkw_file%) else (gtkwave "%batdir%\%testbench%.vcd")

pause

里面绝对路径iverilog_path，gtkwave_path，vivado_dir需要根据软件实际安装位置进行调整。
各个文件的相对路径如有修改，则file_io_testbench.bat需要做相应修改。
zhang可以替换成不含中文的路径，其他建议按照下图处理。
文件路径

设计思路细节

挖坑待填😳

软件依赖

  • 仿真必需
  • 推荐
    • Notepad++（查看源码）或Atom
    • VHDL
      • 如果你更熟悉VHDL而不是Verilog，可以使用XHDL软件进行转换，你可以支持正版或淘宝购买
    • 操作系统
      • Windows 没有任何问题
      • 理论上Linux也是支持的，但iverlog的设置会有不同（参考iverilog官方文档），文件路径也和Windows不一样，需要探索

最后

如果你有任何问题，有以下3种方式给我反馈:

  • 在下面评论
  • 去相应的github repo提issue
  • 发邮件给我，zhangxin_mail163@163.com

Just feel free to raise a question and have some fun with using this code 😄

Author: Zhang Xin
Link: https://zhangxin6.github.io/2019/01/20/connected_regions_labeling（连通域提取）/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
iverilog