一种适于硬件实现的快速连通域标记算法

张国和, 徐快, 段国栋, 赵晨, 梁峰

(西安交通大学电子与信息工程学院, 710049, 西安)

在计算机视觉、遥感、医学、生物特征学、文档分析、机器人等领域,图像中连通区域信息的提取和标记具有重要的作用[1]。在基于硬件实现的图像、视频处理系统中,与可流水实现的图像滤波、边缘检测和阈值分割等算法相比,连通区域标记算法往往需要占用更多的硬件资源和处理时间[2],成为高速图像处理的瓶颈。因此,如何提高连通区域标记算法的执行效率是整个图像处理系统中的关键问题[3]。

通过对近些年提出的典型的二值图像连通域标记算法进行详细描述,总结其优缺点,对相应算法复杂度和资源需求进行了分析,以供设计出适合于硬件实现的二值图像连通域标记算法。当前已有的区域连通标记算法根据其实现方式可以分为2类:软件可实现算法和硬件可实现算法。

Rosenfeld等提出的两遍扫描算法被视为经典的区域连通标记算法[4],但是由于存储等价标记所需的内存空间和合并等价标记所需的时间都很大,此算法仅仅适用于软件实现。Chang等提出的轮廓追踪(CT)算法[5]只需扫描图像一次,然而轮廓像素点可能被扫描多次。由于算法中对内存的访问非常没有规律,此算法也仅仅适用于软件实现。何立风等人设计的基于游程的两遍扫描连通域标记算法[6-8],引入游程的概念,对像素批量进行标记和等价标记合并。经过测试,该算法在同类算法中的效率最高,且随着图像像素和复杂度的增大具有较稳定的线性特性,本文的连通域标记算法借鉴了此算法对于等价标记表的实现方式。在目前已知的区域连通算法中,Grana等提出的块决策表(BBDT)算法[9]具有最好的性能,该算法增大了相邻像素的扫描窗口,缺点是只能支持8连通规则。

由于对大存储空间的要求,上述区域连通算法往往无法通过硬件逻辑加速,由此又出现了一些适用于硬件实现的连通域标记算法。Kofi等提出一种基于游程长度的区域连通算法[10],可以通过片上RAM实现,但对于大于1 024×1 024像素的图像,过高的存储空间要求依然成为瓶颈。Johnston等提出的一次扫描算法[11]在FPGA实现过程中,由于需要对堆栈进行复杂的写入读出操作,使得电路的最高工作频率很低,并不利于图像的实时高速处理。

国内许多高校也对区域连通标记算法进行了一定的研究[12-14],如沈阳工业大学的冯海文等人提出的高效一遍扫描连通域标记算法[12]、四川大学的王凯等人设计的基于图像分块的连通域标记算法[13]、华东理工大学的刘关松提出的新型二值图像连通域标记算法[14]等都是在一些经典算法的基础之上做了一定的改进,对算法效率的改善不大,且大多基于软件实现,本文主要研究连通域标记算法的硬件电路实现,因此这类算法仅作参考。

从国内外研究现状来看,比较主流的连通域标记算法仍然是基于对图像的光栅扫描,这些算法受限于过高的资源需求,只适用于软件实现,因此速度成为其主要的衡量指标。

为了减少存储等价标记所需的空间和处理等价标记所需的时间,本文以游程为单位批量地对行内连续像素进行处理。在逐行对图像进行光栅扫描的过程中,将已经结束的连通区域即时输出,不仅减少了存储这些连通域信息所需的空间,而且只需对图像完整地扫描一遍,就可以完成对连通域信息的提取或者连通域像素的标记,极大地提高了运行速度,使其能高速、高效完成连通域的标记,用于实现图像的快速扫描与追踪。

1 二值图像连通域标记算法的设计

常见的连通区域分8邻域和4邻域连通2种,由于8邻域连通更为全面,通用性好[15],因此本文以8邻域连通为例进行描述。本文所提出的快速连通域标记算法需要经过行扫描、游程标记和等价游程对合并、已结束游程检测和已结束区域信息输出几个主要阶段,完成整幅图片的连通域标记和特征提取。

本文所提出的连通域标记算法采用光栅扫描顺序[16],逐行逐列扫描图像的每个像素,将每一行内连续的前景像素归为一个游程,以游程为基本单位进行预标记和等价标记合并,降低了所需记录标记的数量和处理等价标记所需的时间。为了减小存储已扫描完游程所需的存储空间,在当前行扫描结束后对上一行游程进行检测,输出已结束区域包含的所有游程。该算法只需对图像完整地扫描一遍,就可以完成所有连通域的标记,避免了对整幅图像的临时标记值进行缓存。本文算法的流程图如图1所示,主要分为以下几个步骤。

(1)行扫描。从左至右逐个对当前行的像素进行扫描,判定行内的所有游程,并将游程的起始坐标和结束坐标存入Ao或Ae数组(奇数行存入Ao数组,偶数行存入Ae数组)。当目标像素和前一个像素为“01”时,意味着一个游程的开始,当目标像素和前一个像素为“10”时,意味着一个游程的结束,需要注意的是在行开始和行结束像素的边界情况。

图1 本文提出算法流程图

(2)游程标记和等价游程对合并。对于步骤(1)中在当前行产生的每个游程,需要对其赋予临时标记。对于当前行的某个游程R1,需要扫描上一行的所有游程信息,若当前行为奇数行,则扫描Ae数组中上一行的游程信息,若当前行为偶数行,则扫描Ao数组中上一行的游程信息。2行间的2个游程由于位置不同存在的连通情况如图2所示。

图2 行间游程可能存在的连通关系示意图

若上一行的游程与当前行的游程的位置关系如图2中的游程②、③、④的情况所示,则认定两者之间存在连通关系。算法中的实现方式为:设当前行游程的起始坐标为X0,结束坐标为X1,上一行游程的起始坐标为Y0,结束坐标为Y1,若坐标满足下列2个公式,则认定这2个游程存在连通关系,可描述为

X0≤Y1;X1≥Y0(四连通)

(1)

X0≤Y1+1;X1≥Y0-1(八连通)

(2)

若当前行游程R1仅与上一行的一个游程R2连通,则将R2的临时标记L2赋予R1即可,同时需要将该标记值存入Ao或Ae数组中相应的游程信息中,以供后续的等价标记合并时查看,还需将游程信息(起始坐标、结束坐标、所在行数、临时标记)记录到An数组(记录所有游程的信息)中,以供后续输出已结束游程的信息时查看。如图2所示,若当前行游程R1同时与上一行的多个游程②、③、④连通,则将这些游程中最左侧的(即最早被扫描到的)游程②的临时标记L2赋予R1即可,并将相应信息记录到Ao、Ae和An数组中。同时,游程③、④的标记值L3、L4与L2被认定为等价标记对,需要在后续的等价标记对合并操作中进行合并。

若当前行游程R1与上一行的游程的位置关系如游程①或⑤的情况所示,说明未与上一行的任何游程连通,则需要为R1新建一个临时标记L1,新的临时标记L1的代表标记也为L1,并将相应信息记录到Ao、Ae和An数组中。

对于上述记为等价标记对的2个临时标记,需要进行合并。合并的主要操作是将2个临时标记所在的代表标记集合进行合并。首先取出这2个临时标记值的代表标记S1和S2,若S1=S2,则不需要合并;否则,将较大的代表标记集合中的所有临时标记归入较小的代表标记集合中,实现了2个游程所代表的区域的合并。

(3)扫描上一行游程。在当前行游程标记和等价游程对合并结束后,需要对上一行的游程信息进行扫描,主要检测Fl(代表该游程是否与下一行的游程发生连通关系)标志位。若Fl=1,意味着该游程与当前行的游程发生连通关系,跳过;若Fl=0,意味着该游程未与当前行的游程发生连通关系,但这只能说明该游程所在的区域在局部结束,是不是真正结束还要根据该游程的代表标记与当前行所有游程代表标记的关系来判定。如图3所示的图像形状,当扫描到第5行时,第4行的游程②未与当前行的任何游程连通,但其所在区域在游程①、③的位置与当前行游程④、⑤连通,因此并未结束。

考虑到这种特殊情况,本文采取的策略是对于上一行未与当前行的连通的游程,取出其代表标记值S2与当前行所有游程的代表标记值进行比较(代表标记表征了游程所在的区域),若没有与之相等的,则说明该游程未与当前行的任何游程存在等价关系,换言之就是该游程未与当前行的任何游程处在同一区域,说明此区域在上一行的这个游程位置已经结束,将其代表标记值S2作为结束标记存入Af数组(记录上一行已结束游程的代表标记),不重复记录;若有与之相等的,则该游程所在的区域在当前行还在延伸,不作任何操作。

图3 判定游程结束的特殊案例

(4)输出已结束区域信息。若步骤(3)中检测出上一行存在已经结束的游程,则从Af数组中取出其代表标记Lf,遍历An数组中游程的临时标记,将代表标记和Lf相等的所有游程的信息输出,输出后要对An数组中空出的空间做出填充以节省存储空间。

2 存储机制和资源需求优化

2.1 游程信息表存储机制

根据上文的描述,本文算法需要的资源需求主要是来自Ao、Ae、An、Af、Br(记录临时标记集合中所有标记的代表标记)、Bn(记录临时标记集合中所有标记的排列顺序)、Bt(记录临时标记集合的结束点)等数组,其中An数组用来记录扫描过程中所有游程的信息,所需的位宽和深度最大。为了降低An存储块的大小,本文对第1章中算法步骤(2)中An数组的存储机制进行一定的优化,主要的思想就是将已结束游程的信息输出后,将新建立的游程信息存入空闲的存储空间里,避免建立新的存储空间。如图4所示,位于An数组中地址4的游程被检测为结束游程,将其游程信息输出,这样地址4指向的空间就闲置了出来,当扫描下一行像素检测到新的游程时,把新的游程信息存入地址4,避免建立新的地址空间,这样可以降低存储所有游程信息需要的存储块深度。

通过对多幅分辨率为2 048×1 536像素的图片进行测试,经过优化后,An数组的深度需求大大减少,最大降低的幅度高达90.3%,最少的也有32.6%,其中资源节约率为后者相对于前者降低的幅度,计算公式为

式中:Pr为资源节约率;Hbefore为优化前应有深度;HAn为An数组实际占用深度。

经过优化后的An数组的存储机制虽然极大地降低了资源需求,但是考虑到每次有新的游程需要存储时,都需要对An数组中已占用过的所有的空间进行遍历,寻找闲置的空间,这个过程会随着游程数量的增多耗费更多的时间。因此也需要对1中算法步骤(4)An数组中游程信息的输出机制进行优化,主要的思想就是当某个地址的游程信息输出后,将数组末尾的游程信息存至该位置,地址指针减1,这样有新的游程需要存储时,就可以省去遍历An数组的时间,直接将数组信息存入地址指针指向的空间,即原来末尾游程的存储空间,如图4所示。

(a)优化前 (b)优化后图4 An数组输出机制优化前后示意图

2.2 硬件实现资源需求分析及优化

在硬件实现时,首先要考虑算法需求的片上资源。由上述分析过程可知,该算法共需要7个数据阵列:Ao、Ae、An、Af、Bn、Bt和Br,对于分辨率M×N图像,每组存储块所需的位宽和深度分析如下。

对于分辨率M×N图像,区域个数的极限值为M×N/2,考虑到发生这种情况的时候,图像检测区域已经没有意义,所以即使求出区域信息也是没有必要的。故可以约定一个可以接受的区域上限,来减少资源的占用。如果输入图像对单独一个点的区域做了过滤,那么区域上限为M×N/4。

当图像像素分辨率为2 048×1 536像素时,本文连通域标记算法在硬件实现时理论上所需的存储资源大约为88.87 Mbit,这大大超出了可以接受的范围。但是,在实际测试中发现一些RAM的使用率远远小于其理论所需设计的深度,而且一些变量的最大值也远远小于其理论预估的极值,因此需要对上述RAM深度和宽度的分配进行一定的优化。

首先需要优化的变量为临时标记和代表标记的最大值。根据上文的分析,认定临时标记和代表标记的最大值为区域数量的上限,对于分辨率M×N的图像,最大的连通域数量为M×N/4。考虑到本文算法最大支持的图像分辨率为2 048×1 536像素,在MATLAB中对于大量分辨率为2 048×1 536像素、且构成复杂的图像进行测试,发现其游程的最大临时标记和代表标记值远远小于理论最大值M×N/4。出于节约硬件资源的考虑,这里取214=16 384即可以满足实际需求,也就是临时标记和代表标记的记录需要占用位宽14 bit,深度为16 kbit。因此Bn、Bt和Br数组的RAM需求为16 000×14 bit。Ao和Ae数组的位宽需求为40(40=2×12+14+2)bit,Af数组的位宽需求为14 bit,An数组的位宽需求为50(50=2×12+12+14)bit。

表1 本文算法各数组对应的RAM需求

图5 本文算法的硬件系统结构图

接下来对各数组所需求RAM的深度进行优化。如之前2.1所述,通过对An数组存入读出机制进行一定的调整,实现了对其存储深度的最大利用,根据表1统计的信息,将An数组对应RAM的深度设为64 kbit即可满足实际需求。为了节省硬件资源,将Ao和Ae数组的RAM深度设为M/4=512 bit,将Af数组的RAM深度设为M/8=256 bit,即可满足实际需求。因此,对于分辨率为2 048×1 536的图像,RAM总需求量为20.48+224+3.584+3 200=3 448 kbit≈3.45 Mbit。

表2 5种算法硬件实现需求的片上资源对比

如表2所示,对比可见本文算法硬件实现时需要的片上资源为BBDT算法的21.9%,为He算法[8]的7.6%。该配置所提供的硬件资源空间足以处理分辨率2 048×1 536像素及其以下的绝大多数二值图像。

3 算法的硬件架构

本文所提出标记算法的硬件系统结构框图如图5所示。其中对外连接的数据接口主要分为3组,第一组接口连接图像源输入模块,接受来自图像源的数据和数据有效信号,并反馈行结束信号给图像输入模块,以开启下一行的图像数据输入;第二组接口连接参数配置模块,主要完成对图像分辨率以及二值图像连通规则的配置,图像分辨率的配置一定要与图像的像素个数匹配,避免出现数据不足或溢出的情况;第3组接口通过输出使能信号的控制,输出已结束的区域游程息。

在二值图像连通域标记硬件结构内部,主要分为4个操作模块、2个控制模块以及4组片上RAM,这4个操作模块都受状态机控制模块的控制,与片上RAM交互标记过程中产生中间信息,其中An数组对应RAM的存储机制较为复杂,要受到An存储控制模块的控制。这4个操作模块组成了一个完整的行操作流程,完成一幅分辨率M×N的二值图像的连通域标记需要N次行操作流程。

扫描模块根据输入的图像数据,判定当前行的所有游程,将游程的起始坐标和结束坐标存入Ao、Ae数组中;标记及合并模块读取当前行和上一行的游程坐标,判定当前行每一个游程与上一行游程的连通关系,将游程的临时标记和标志位送回Ao、Ae数组中,将新建的代表标记和合并等价标记对的信息传递给Bn、Bt、Br存储器,最终还要将游程的信息存入An存储器中;结束区域检测模块根据Ao/Ae存储器中存的上一行游程的标记位,将上一行中未与当前行连通的游程取出作为待检测游程,将这些游程的代表标记与当前行所有游程的代表标记进行比较(需要与Br存储器交互信息),锁定已结束的游程,再将这些游程的代表标记存入Af存储器中;结束区域信息输出模块根据Af中存储的代表标记,将An存储器中所有与之相等的游程全部输出。在算法的硬件实现过程中,为了提高运行速度,使用多个电路同时工作以充分利用硬件系统的并行处理能力。

4 实验结果及分析

为了对比本文算法与其他算法的性能,选取了2幅分辨率为512×512像素的图像,分为记为图A和图B在图像源一定的情况下,对比不同算法处理的运行时间。由于其他算法都是在高速PC工作站上基于软件运行,因此这里引入频率换算因数来有效地对比工作速度。各算法的类型和仿真平台如表3所示。并且将本文提出的算法在Altera公司的StrtixIV系列EP4SGX530H H35C2板子上进行了验证,证实了其硬件可行性。

表3 不同算法的类型和仿真平台

仿真结果如表4所示,其中用到3个不同的仿真平台,平台1为C language on a PC-based workstation(Intel Pentium D 3.0 GHz+3.0 GHz CPUs,2GB-Memory,Mandriva Linux OS);平台2为C++language on a PC-based workstation(Inter Core i5 2.4 GHz+2.4 GHz CPUs,2GB-Memory);平台3为Verilog language on Modelsim 10.2c @100 MHz。从表4可以看出,在频率换算以后,本文的算法要快于其他4种算法,其中比He算法要快至少3倍以上,比BBDT算法要快至少9倍以上。考虑到仿真频率较低,在最大工作频率限度内提高运行频率能够极大提高处理速度,而且SMIC 0.18 um仿真库并不是当前最先进的工艺,因此若将工艺尺寸减小,本文算法的工作性能还有很大的提升潜力。

表4 对比测试仿真结果

为了进一步验证本算法的正确性和与已有算法相比较的优势,在SIMPLIcity数据库[18]中选取了500张分辨率都为512×512像素的图片,将其分为9个不同疏密等级(即前景像素占总像素的比例),图6为各算法在图像密度不同时的柱型统计图。

由图6分析可得,本文算法在图像疏密等级较低,图像构成复杂度稍低时具有明显优势,游程数量巨大,图像复杂度太高时标记速度会有所减慢,分析其原因主要是本文算法在扫描过程中实时输出已结束游程的信息,这样可以大大减少需要存储的游程信息条目,但是代价是,在游程信息表中遍历查找已结束游程需要耗费绝大部分运行时间,特别是游程数量巨大的情况。这主要是资源需求和运算速度之间的折中问题。

图6 各算法在图像疏密不同时标记时间对比图

5 结 论

本文提出了一种快速连通区域标记算法的硬件实现方法。算法的主要特点是在扫描过程中实时输出检测到的已结束区域信息,只需完整地扫描一遍图像,就可以完成对所有区域的标记,不仅避免了对整幅图像标记值的缓存,还减少了需要记录的游程信息。通过对游程信息表存取机制的优化,大大降低了算法的存储资源需求,但是由于算法在扫描过程中实时输出检测的已结束游程信息,这样可以减少存储资源,而在游程信息表中遍历查找已结束游程需要耗费绝大部分运行时间,特别是游程数量巨大、图像复杂的情况,这主要是资源需求和运算速度之间的折衷问题。因此,本文所提出的算法是一种对于小图像特别高效的算法。