一种连通量统计信息提取方法及VLSI结构

摘要

本发明公开了一种连通量统计信息提取方法及VLSI结构，包括以下步骤：同时对二值图像的相邻两个行进行扫描，判断当前行与上一行之间是否存在连通区域，当当前行与上一行之间存在连通区域时，则将上一行中与当前行相连通区域通过等价游程对合并规则合并至当前行中，同时将上一行中未与当前行连通的区域记作已结束区域，并输出已结束区域的信息，再更新当前行中连通区域的游程编号；当当前行为最后一行时，则根据等价游程对合并规则合并当前行行内的连通区域，然后将合并后得到的区域记作已结束区域，再输出已结束区域的信息，得连通量统计信息。本发明能够通过快速对二值图像处理提取二值图像的连通量统计信息，硬件资源消耗小。

说明书

技术领域

本发明属于图像处理技术及集成电路设计领域，涉及一种连通量统 计信息提取方法及VLSI结构。

背景技术

二值图像的连通量信息统计是从仅由“0”像素(通常表示背景点) 和“1”像素(通常表示前景点)组成的一幅点阵图像中，将相互连接(4 邻域或8邻域)的“1”值像素集合提取出来，其目的就是要寻找图像中 所有的连通区域，并且将属于同一连通区域的所有像素用唯一的标记值 进行标记，统计每个连通区域的特性。这种预处理操作在图像处理和模 式识别的许多领域中被广泛采用。因此通过某种方法把各个连通区域区 分开来，分别研究各个连通区域的特性，是提取图像特征、进行目标检 测和识别的重要一步。

当前已有的区域连通算法根据其实现方式可以分为两类：软件可实 现算法和硬件可实现算法。

Rosenfeld等发表的(A.Rosenfeld and J.L.Pfaltz.Sequential  Operations in Digital Picture Processing，J.ACM，13(4)：471-494， 1966)中提出的两遍扫描算法被视为经典的区域连通标记算法，通过两次 扫描图像，完成对连通区域的预标记以及等价标记的合并，但是由于存 储等价标记所需的内存空间和合并等价标记所需的时间都很大，此算法 仅仅适用于软件实现。Chang等发表的(F.Chang，C，J，Chen and C，J，Lu. A Linear-Time Component-Labeling Algorithm Using Contour  Tracing Technique，Computer Vision and Image Understand，vol.93， pp.206-220，2004)中提出的轮廓追踪算法通过追踪连通区域的轮廓， 同一连通区域内部的像素被置相同的标记，从而完成对图像所有像素的 标记，得到区域连通结果，但是由于算法中对内存的访问非常没有规律， 此算法也仅仅适用于软件实现。在目前已知的区域连通算法中，Grana等 发表的(Grana，C，Borghesani，D，and Cucchiara，R，Optimized  block-based connected components labeling with decision trees， IEEE Trans.Image Process，2010，19，(6)，pp.1596-1609)中提出 的BBDT(block based decision table)算法具有最好的性能。

由于对大存储空间的要求，上述区域连通算法往往无法通过硬件逻 辑加速，由此又出现了一些适用于硬件实现的连通域标记算法。Lumia 等发表的(R.Lumia，L.Shapiro and O.Zungia，A New Connected  Components Algorithm for Virtual Memory Computers，Computer  Vision and Image Unders tand，vol.22，No.2，pp.287-300，1983)中提出 的算法在Rosenfeld的算法的基础之上，通过在第一次扫描过程中局部 地合并等价标记，可以减少存储这些标记所需的内存空间。Kofi Appi ah 等发表的(Kofi Appiah，Andrew Hunter，Patrick Dickinson，and  Jonathan Owens，A Run-Length Based Connected Component Algorithm  for FPGA Implementation，2008)中提出一种基于游程长度的区域连通 算法，该算法可以通过片上RAM实现，但是对于大于1024X 1024的图 像，大内存空间的要求依然成为瓶颈。

区域连通算法提取的连通量信息在各类图像处理和模式识别算法中 的应用相当广泛。Arnon Amir等发表的(Arnon Amir；Lior Zimet， Alberto Sangiovanni-Vincentelli and Sean KAO，An embedded system  for an eye-detection sensor，Computer Vision and Image  Understanding，98(2005)：104-123)中提出的嵌入式人眼识别系统主要 关注输入二值图像的连通区域的面积、边界和一阶距，其中面积的计算 需要统计连通区域中像素点的总个数(SUM_n)，边界的划定需要统计连 通区域中像素横向坐标和纵向坐标的极值(X_min、X_max、Y_min、X_max)， 一阶距(几何中心)的计算不仅需要统计连通区域中像素点总个数 (SUM_n)，还需要统计连通区域中所有像素横向坐标和纵向左边的累加 和(SUM_x、SUM_y)。

由上述可以看出，在目前已有连通域标记算法中，即使性能最优的 BBDT算法也只能在高性能PC机器上取得较快的处理速度，往往无法满 足高速实时图像处理的需要，尤其是对微形化的嵌入式图像处理系统， 这就需要一种适用于硬件加速实现、硬件资源消耗小的连通量统计信息 提取方法。

发明内容

本发明的目的在于克服上述现有技术的缺点，提供了一种连通量统 计信息提取方法及VLSI结构，该方法及VLSI结构能够通过快速的对二 值图像处理提取二值图像的连通量统计信息，并且硬件资源消耗小。

为达到上述目的，本发明所述的连通量统计信息提取方法包括以下 步骤：

同时对二值图像的相邻两个行进行扫描，判断当前行与上一行之间 是否存在连通区域，当当前行与上一行之间存在连通区域时，则将上一 行中与当前行相连通区域通过等价游程对合并规则合并至当前行中，同 时将上一行中未与当前行连通的区域记作已结束区域，并输出已结束区 域的信息，再更新当前行中连通区域的游程编号；

当当前行为最后一行时，则根据等价游程对合并规则合并当前行行 内的连通区域，然后将合并后得到的区域记作已结束区域，再输出已结 束区域的信息，完成图像信息的提取，得连通量统计信息。

所述等价游程对合并规则为：

两个连通区域合并得到的区域的游程编号为两个连通区域的游程编 号中较小的一个；

两个连通区域合并得到的区域的X向像素坐标最小值为两个连通区 域的X向像素坐标最小值中较小的一个；

两个连通区域合并得到的区域的Y向像素坐标最小值为两个连通区 域的Y向像素坐标最小值中较小的一个；

两个连通区域合并得到的区域的X向像素坐标的最大值为两个连通 区域的X向像素坐标最大值中较大的一个；

两个连通区域合并得到的区域的Y向像素坐标的最大值为两个连通 区域的Y向像素坐标最大值中较大的一个；

两个连通区域合并得到的区域的X向像素坐标的累加和为两个连通 区域的X向像素坐标的累加和之和；

两个连通区域合并得到的区域的Y向像素坐标的累加和为两个连通 区域的Y向像素坐标的累加和之和；

两个连通区域合并得到的区域的区域像素个数为两个连通区域的区 域像素个数之和。

所述已结束区域的信息包括已结束区域的游程编号、X向像素坐标 最小值、Y向像素坐标最小值、X向像素坐标的最大值、Y向像素坐标 的最大值、X向像素坐标的累加和、Y向像素坐标的累加和及区域像素 个数。

本发明所述的连通量统计信息提取的VLSI结构包括输入端、输出 端、控制器、图像扫描模块、区域合并模块、RAM_A、RAM_B、 RAM_EQU、RAM_PAIR及RAM_BUFFER；

所述控制器与输入端、RAM_BUFFER及图像扫描模块的相连接， 图像扫描模块与控制器和区域合并模块相连接，区域合并模块与图像扫 描模块、RAM_A、RAM_B、RAM_EQU、RAM_PAIR及输出端相连接；

输入端接收图像二值数据，并将图像二值数据存储到RAM_BUFFER 中，控制器控制RAM_BUFFER将图像相邻两行的二值数据并行输出至图像 扫描模块中，图像扫描模块对相邻两行进行扫描，判断每行的游程及两 行的等价游程，再将当前行的游程信息及两行的等价游程对信息转发至 区域合并模块中，区域合并模块将当前行的游程信息存储到RAM_A或 RAM_B，将两行间等价游程对的行内次序编号记录到RAM_EQU中，然后合 并两行间等价游程的游程信息，当当前行行内产生游程编号不同的等价 游程对时，则将等价游程编号记录到RAM_PAIR中，再扫描上一行中所有 未合并游程，将具有相同游程编号的游程标记为一个已结束区域，然后 通过输出端输出已结束区域的信息，再根据RAM_PAIR中的信息更新当前 行的游程标号，若当前行是最后一行，则将具有相同游程编号的游程标 记为已结束区域，然后通过输出端输出已结束区域的信息。

本发明具有以下有益效果：

本发明所述的连通量统计信息提取方法及VLSI结构对二值图像进 行连通量统计信息提取时，同时对原始二值图像的相邻两行进行扫描， 获取两行的连通区域，再将两行的连通区域进行合并，然后将上一行中 未合并区域的信息作为已结束区域信息进行输出，每次扫描完毕后均进 行一次已结束区域信息的输出，避免了对整幅二值图像数据的记录，大 大节省了内存空间，只需对整幅二值图像扫描一次，提高了运行速度， 与目前区域连通算法相对具有明显的速度优势，并且能直接得到连通区 域的统计信息。

附图说明

图1为本发明的流程图；

图2为本发明中2X2扫描模板示意图；

图3本发明中连通量统计信息提取的VLSI结构示意图；

图4(a)为测试用图1；

图4(b)为测试用图1；

图4(c)为测试用图1；

图4(d)为测试用图1。

具体实施方式

下面结合附图对本发明做进一步详细描述：

参考图1，本发明所述的连通量统计信息提取方法包括以下步骤：

同时对二值图像的相邻两个行进行扫描，判断当前行与上一行之间 是否存在连通区域，当当前行与上一行之间存在连通区域时，则将上一 行中与当前行相连通区域通过等价游程对合并规则合并至当前行中，同 时将上一行中未与当前行连通的区域记作已结束区域，并输出已结束区 域的信息，再更新当前行中连通区域的游程编号；

当当前行为最后一行时，则根据等价游程对合并规则合并当前行行 内的连通区域，然后将合并后得到的区域记作已结束区域，再输出已结 束区域的信息，完成图像信息的提取，得连通量统计信息。

所述等价游程对合并规则为：

两个连通区域合并得到的区域的游程编号为两个连通区域的游程编 号中较小的一个；

两个连通区域合并得到的区域的X向像素坐标最小值为两个连通区 域的X向像素坐标最小值中较小的一个；

两个连通区域合并得到的区域的Y向像素坐标最小值为两个连通区 域的Y向像素坐标最小值中较小的一个；

两个连通区域合并得到的区域的X向像素坐标的最大值为两个连通 区域的X向像素坐标最大值中较大的一个；

两个连通区域合并得到的区域的Y向像素坐标的最大值为两个连通 区域的Y向像素坐标最大值中较大的一个；

两个连通区域合并得到的区域的X向像素坐标的累加和为两个连通 区域的X向像素坐标的累加和之和；

两个连通区域合并得到的区域的Y向像素坐标的累加和为两个连通 区域的Y向像素坐标的累加和之和；

两个连通区域合并得到的区域的区域像素个数为两个连通区域的区 域像素个数之和。

所述已结束区域的信息包括已结束区域的游程编号、X向像素坐标 最小值、Y向像素坐标最小值、X向像素坐标的最大值、Y向像素坐标 的最大值、X向像素坐标的累加和、Y向像素坐标的累加和及区域像素 个数。

参考图3，本发明所述的连通量统计信息提取的VLSI结构包括输入 端、输出端、控制器、图像扫描模块、区域合并模块、RAM_A、RAM_B、 RAM_EQU、RAM_PAIR及RAM_BUFFER；

所述控制器与输入端、RAM_BUFFER及图像扫描模块的相连接， 图像扫描模块与控制器和区域合并模块相连接，区域合并模块与图像扫 描模块、RAM_A、RAM_B、RAM_EQU、RAM_PAIR及输出端相连接；

输入端接收图像二值数据，并将图像二值数据存储到RAM_BUFFER 中，控制器控制RAM_BUFFER将图像相邻两行的二值数据并行输出至图像 扫描模块中，图像扫描模块对相邻两行进行扫描，判断每行的游程及两 行的等价游程，再将当前行的游程信息及两行的等价游程对信息转发至 区域合并模块中，区域合并模块将当前行的游程信息存储到RAM_A或 RAM_B，将两行间等价游程对的行内次序编号记录到RAM_EQU中，然后合 并两行间等价游程的游程信息，当当前行行内产生游程编号不同的等价 游程对时，则将等价游程编号记录到RAM_PAIR中，再扫描上一行中所有 未合并游程，将具有相同游程编号的游程标记为一个已结束区域，然后 通过输出端输出已结束区域的信息，再根据RAM_PAIR中的信息更新当前 行的游程标号，若当前行是最后一行，则将具有相同游程编号的游程标 记为已结束区域，然后通过输出端输出已结束区域的信息。

实施例一

参考图2，本发明的具体过程为：

1)图像输入：选择四连通或者八连通配置。

2)行缓存：接收输入端输入的图像二值数据，通过RAM_BUFFER 的缓存作用，同时将图像相邻两行的二值数据并行输出。

3)行扫描：对图像的二值数据阵列进行扫描，每次对图像的两行同 时扫描，即每行都要被扫描两次，第一次作为当前行，第二次作为上一 行，行扫描的过程中，采用2X2扫描模板，如图2所示，扫描过程中模 板逐列右移。

标记游程并记录：2X2扫描模板的上一行的二值数据为01时，上 一行产生一个新的游程；2X2扫描模板的上一行的二值数据为10时，上 一行的当前游程结束；2X2扫描模板的当前行的二值数据为01时，当前 行产生一个新的游程；2X2扫描模板的上一行的二值数据为10时，当前 行的当前游程结束；在游程结束后，对游程信息进行记录，存到RAM_A 或RAM_B，其中，奇数行存入RAM_A，偶数行存入RAM_B。由于上 一行的游程信息在上一次行扫描过程已经作为当前行存到相应RAM，因 此只需记录本次扫描中当前行的游程信息。游程信息包括游程编号 (lam_id)，X向像素坐标最大值(X_max)和最小值(X_min)、Y向像 素坐标最大值(Y_max)和最小值(Y_min)、X向像素坐标累加和 (SUM_x)、Y向像素坐标累加和(SUMy)、区域像素个数(SUM_n) 和游程合并标记(S)(1表示该游程已经与)下一行某个游程合并，0表 示该游程未与下一行某个游程合并)。

判别等价游程并记录：在行扫描的过程中，根据四连通或者八联通 的相应规则判别相邻两行间的等价游程对。

对于四连通来说，2X2扫描模板出现下列三种情况时，认定有新的 等价游程对出现。

$\left(\begin{array}{cc}0& 1\\ 0& 1\end{array}\right)\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)$

对于八连通来说，2X2扫描模板出现下列五种情况时，认定有新的 等价游程对出现。

$\left(\begin{array}{cc}0& 1\\ 0& 1\end{array}\right)\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)\left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right)\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$

当有新的等价游程对出现时，把这两个游程在其相应行的行内游程 次序编号存入RAM_equ中。

4)合并等价游程：对于步骤3中检测出的等价游程对，需要将游程 对中上一行游程的信息合并到当前行的游程信息，合并后的游程信息存 入当前行的游程信息中，上一行被合并的游程的合并标记(S)置1。

合并输出上一行剩余游程：经过步骤4以后，上一行的游程中，会 剩余一些未合并(合并标记S为0)的游程。在这些剩余的游程中，具 有相同游程编号的游程标记为一个结束连通区域，合并信息输出，包括 X向像素坐标最大值(X_max)和最小值(X_min)、Y向像素坐标最大 值(Y_max)和最小值(Y_min)、X向像素坐标累加和(SUM_x)、Y 向像素坐标累加和(SUM_y)、区域像素个数(SUM_n)。

更新当前行游程编号：合并行间等价游程会在当前行产生游程编号 (lam_id)不同的等价游程，将等价游程编号存入RAM_PAIR，然后对 当前行游程进行游程编号的更新，等价游程编号取最小值赋予等价的游 程。

5)图像结束检查：若当前行不是最后一行，则进入新一轮的行扫描。 若当前行是最后一行，具有相同游程编号的游程标记为一个已结束区域， 然后输出该已结束区域的信息，一幅图像的区域信息统计量提取完成， 最终能够得到图像当中每个连通区域的7个统计信息，包括X向像素坐 标最大值(X_max)和最小值(X_min)、Y向像素坐标最大值(Y_max) 和最小值(Y_min)、X向像素坐标累加和(SUM_x)、Y向像素坐标累 加和(SUM_y)、区域像素个数(SUM_n)。

6)所需片上存储资源分析：对于像素大小M×N的图像，每组RAM 所需的位宽和深度分析如下(其中log₂X的结果向上取整)。[1].RAM_A (RAM_B)记录的是图像每个游程区域的信息，扫描一行更新一次。由 于每行的最大游程区域数为M/2，所需的深度为M/2，所需的位宽总共 有5部分构成：区域编号：考虑到极限情况，对于M×N图像，区域个 数的极限值为M×N/2，考虑到发生这种情况的时候，图像检测区域已 经没有意义，所以即使求出区域信息也是没有必要的，故可以约定一个 可以接受的区域上限，来减少资源的占用，如果输入图像对单独一个点 的区域做了过滤，那么区域上限为M×N/4，所需位宽为 (log₂(M×N/4))bit；区域顶点坐标：由于需要最大满足M×N分辨率，X 向坐标位宽均为(log₂M)bit，Y向坐标位宽均为(log₂N)bit，系统需要X轴 的最大最小值和Y轴的最大最小值，总计需要(2log₂M+2log₂N)bit；区域 像素坐标和：对于M×N图像分辨率，区域坐标累加最大值为M×(M+1) /2×N，所需位宽为(2log₂(M×(M+1)/2×N))bit；区域像素点个数：最 大为M×N，所需位宽为(log₂(M×N))bit。连通标记：所需位宽为1bit， 所需的总位宽为(log₂(M×N/4)) +(2log₂M+2log₂N)+(2log₂(M×(M+1)/2×N))+(log₂(M×N))(bit)。

RAM_EQU记录的是相邻两行间等价游程对的行内次序编号，最大 值为M/2，因此所需的位宽为(2log₂(M/2))bit。通过MATLAB仿真大量 图像(像素构成复杂，其中最大像素可到2048×1536)，相邻两行间等 价游程对的数量远小于其理论最大数量M/2。出于节约硬件资源的考虑， 这里我们取M/4即可以满足实际需求，因此RAM_EQU所需的深度为 M/4。

RAM_PAIR记录的是当前行内等价游程的游程编号，即RAM_A (RAM_B)中的区域编号，因此所需的位宽为(log₂(M×N/4))bit。与 RAM_EQU同理，当前行内等价游程对的数量远小于其最大值，这里我 们取M/8即可满足实际需求。

RAM_BUFFER是与输入控制模块连接的行缓存RAM，因此所需位 宽为1bit，所需深度为M。

表1统计了对于像素M×N的图像，在不做区域数约束的情况下， 预估该算法的最大的资源占用；

表1

表2统计了对于像素2048×1536的图像，在不做区域数约束的情况 下，预估该算法的最大的资源占用；

表2

表3是扫描不同大小图像时，本文的连通标记算法与BBDT算法的 性能对比，BBDT算法的测试平台为Microsoft Visual C++2008，CPU主频 为2.4GHZ，内存6.00GB；本文算法通过RTL代码实现，仿真平台为 ModelSim6.2E，仿真频率为100MHZ。从仿真结果可以看出，BBDT算法 通过软件实现，在较高的工作频率下处理不同复杂程度(不同连通区域 个数)图像的速度较快；本文算法基于硬件实现，在较低的工作频率下， 处理简单图像的速度甚至要优于BBDT算法，随着图像复杂程度提高， 速度有所下降，但是考虑到仿真频率较低，提高运行频率能够极大提高 处理速度。

表3

表4是RTL代码综合后的资源统计，其中RAM_A和RAM_B需求155 位宽，SRAM Generator支持的最大位宽为128位。通过对不同位宽拼接 方案的综合面积比较，最终采用一个深度相同的78位RAM和77位RAM 拼接而成。

表4