Optimization on algorithm of labeling connected
components in binary images
LUO Zhi-Zao 1 ZHUO Ying-Wu1 LUO Zhi-Shi 2
(1．department of electronic engineering in Minjiang University in Fu Zhou City 350108；
2．Sanming City Electric Power Bureau 365000)
Abstract: The improved algorithm is introduced based on analysis of existing algorithms of labeling connected regions through scanning pixels in binary images.The algorithm has many advantages such as faster,simpler,easier to realize than the others, has more preponderance in terms of multi-objects labeling,and keeping the original edges.The improved algorithm could label background as objects, label and merge connected regions via the two procedure of scanning binary image and scanning buffer block of unmerged regeions.It adopts sequential storage structure instead of chain,stack and tree structure,runs more rapidly, occupies much less memory than the unimproved algorithm.
Key words:binary images;connected components;scanning by pixels;labeling
Binary image is matrix which is component of white pixels and black pixels (commonly ‘1’ represents white pixels in binary image, as well ‘255’ in gray image)[1]. In binary images, labeling connected components indicates to label the connected pixels as one object according with the same connected rule(such as 4-Neighbour,8-Neighbour,m-Neighbour)[2].It is important to construct appropriate data structure,for the object’s attribute and temporary operating result,such as wich object current pixel belong to,quantity of pixels in the object,the center of gravity of objects,and so on[3]. labeling connected components is important procedure for object identification,and directly affect the correctness and speed of identification[4].
It is mainly throught two paths to affect performance of labeling connected components,for the following paths:a) the scanning mode in image and the way of correcting the collision of labeling connected components;b) data structure for information of connected components.So It would be throught the same paths to improve the performance of algorithm of labeling connected components:1)cut down the times of scanning image,as few as possible to scan,avoid backtracking image as possible,and get most information from one scanning;2)constructing appropriate data struct for connected components,reduce time of accessing information about objects,enhance efficiency of the algorithm of labeling connected components. 1 Existing algorithms introduce
There are various algorithms to label connected components,which could be classified into two different regions according to mode of scanning,one is labeling objects by scanning pixels just as namely point-labeling[5],the other is labeling objects by scanning segment,namely line-labeling [6].the modes of point-labeling are various,as follows:1 Sequential scanning mode[7],2 recursive scanning mode[8],3 region-growing mode[9] and so on. labeling objects algorithm based on run-length is the research focus in Line-scanning algorithms [10].These algorithms could label objects exactly,their differentia mainly focus on how to solve labeling collision. The result express one object with same label number.The goal of optimizing algorithm is to simplify it’s operation and improve it’s performance,baesd on correct solving conflicting labeling number.
Pixel-scanning is favorite algorithm,for it’s intuition,simple data structure,easy to realize[5].There are many conflicting labeling numbers,after scanning binary image;normally the method to solve the problem is to iterate scanning image until all conflicting labeling numbers were cleared up[8].It’s running time could be not stable,and it adopts linkedlist struct,tree struct or stack storage struct for labeling object, lots running time is spended on recursively calling and passing pointer.
The paper improve pixel-scanning algorithm ,On the basis of it’s disadvantages. Firstly due to the shortcoming of the linkedlist storage structure,adopts sequential storage structure instead of linkedlist,in order to reduce times of passing pointers;secondly adopt two dimension array to store labeling numbers,which indicate connected components every pixels belong to, and are convenient for following operation;Thirdly use one dimension array to store the number which
labeling common connected components,namely common labeling number,and attributes of object,so that can solve conflicting labeling numbers;lastly improve the algorithm for emerge conflicting labeling number,reorder labeling numbers to get appropriate labeling numbers. 2 algorithm introduce 2.1 glossaries define
Connected components labeling number for pixel(CCLNP):the number which label connected component which one pixel belong to,and store in two dimensions array as large as the binary image. The number has two different periods: in stageⅠ,it indicates the number of labeling connected components from scanning binary image,and different number could label same connected components. So could name the number as pre-emerging connected components labeling number(PCCLN).In stage II,it indicates emerged connected components labeling number, videlicet,which are common connected components labeling number instead of CCLNP.The number is the number of labeling objects at last,named as labeling number for object(LNO).
Conflicting number labeling connected component:in PCCLN matrix,there could be some different number which identify same object,so is named as Conflicting number labeling connected component,also named as homogeneous number labeling connected component.
Common connected components labeling number:the number indicates which object the pre-emerge connected components labeled by pre-emerge labeling number should belong to,the numbers are stored in one dimension array.the array index is pre-emerge labeling number,and the array numerics is composed of the number indicating which object one pre-emerge connected component belong to.
2.2 algorithm Summary
The algorithm runs in two stages
In stage I,scanning binary image one time according with one connected rule,and label the number of pre-emerge connected components for each pixels; and simultaneitily record the common components number that the pre-emerge components belong to;due to 4-Neighbour or 8-Neighbour kernel is very small,so couldn’t label all objects in one scanning,there are many conflicting numbers labeling which connected component the pixel belong to.the common connected components labeling number indicate the common object which the conflicting connected components belong to.
In stage II,scanning the pre-emerge matrix which store pre-emerge connected components labeling number for each pixels,and rewrite the pre-emerge number in matrix,that is to use common connected component labeling number instead of pre-emerge number,the procedure is called emerge pre-emerge connected components. In the procedure reorder the number of common connected components,according with sequence of the number occurring,to keep the nember valid.after the procedure, the labeling number in the matrix represent the number of object that the pixel belong to in same position. 2.3 algorithm describing
The 4-Neighbour and 8-Neighbour have same operation in the algorithm,so we can explain the algorithm via 4-Neighbour.
We presume that f(x1,y),f(x1,y),f(x,y1),f(x,y1)is respectively left- Neighbour ,right-neighbour,top-neighbour and bottom-neighbour of one pixelf(x,y). The
emerge(x,y) represents number labeling Connected components by pixel(CCLNP).We can assure thatf(x1,y)andf(x,y1)had been scanned untilf(x,y)occurred,so emerge(x1,y) and emerge(x,y1) became known number. Connected components
(x,y)specified by pixel,only relate to emerge(x,y1) and labeling number emergeemerge(x,y) specified by pixel f(x1,y) and f(x,y1).the relations between them
expressed as follow formula (1):
(x1,y)emergeemerge(x,y1)emerge(x,y)(x,y1)emerge)1max(emergeif f(x,y)f(x1,y) and f(x,y)f(x,y1)if f(x,y)f(x1,y) and f(x,y)f(x,y1)（1）
if f(x,y)f(x1,y) and f(x,y)f(x,y1)if f(x,y)f(x1,y) and f(x,y)f(x,y1)
Formula(1) indicates:
(1) if pixelsf(x,y)f(x1,y) and f(x,y)f(x,y1),that is f(x,y) equals it’s left-neighbour,which indicates that pixelf(x,y)is connected with it’s left-neighbour,then
emerge(x,y),the number of connected component specified by pixelf(x,y),equals emerge(x1,y), the number of connected component specified by pixelf(x1,y).
(2)if f(x,y)f(x1,y) and f(x,y)f(x,y1),that is f(x,y)is connected with top-neighbour,but not connected with left-neighbour,then emerge(x,y) equals emerge(x,y1).
（3）当像素点f(x,y)f(x,y1)且f(x,y)f(x1,y)时，则f(x,y)与上邻域、
左邻域在同一个连通域内，则需考虑：
(i)若emerge(x,y1)=emerge(x1,y)，则表明f(x,y)的上邻域和左邻域连通域标号一致，仅需emerge(x,y)=emerge(x,y1)即可。
(x,y1)≠emerge(x1,y)，则表明f(x,y)的上邻域和左邻域连通域(ii) 若emerge(x,y)=emerge(x,y1)。 标号冲突，需处理冲突标号，然后emerge(3) if pixelf(x,y)f(x,y1) and f(x,y)f(x1,y),that is pixel f(x,y) is connected with top-neighbour and left-neighbour,then we could draw a following conclusion:
(x,y1)=emerge(x1,y),namely the labeling number of connected (i) if emergecomponent specified by pixel f(x,y)equals labeling number of its’left-neighbour and
(x,y)=emerge(x,y1). top-neighbour,then emerge(x,y1)≠emerge(x1,y) (ii) if emerge(4)若f(x,y)f(x,y1)且f(x,y)f(x1,y)时，表明像素点f(x,y)属于新的连
gxe,y),即通域，因此连通域标号自动加1，并将新的连通域标号赋予emer(emerge(x,y)=max(emerge)1。
本算法的实现难点主要是等价标号的处理和共同连通域的标记。等价标号在算法的第一阶段完成，用数组记录各等价标号的共同连通域标号，当遇到标号冲突时，要合并等价连通域标号，即对common扫描一遍，将等价标号的共同连通域标号标记成一致。
(x,y)的值，common设一维数组common,其下标为待合并连通域标号emerge元素的
(emerge(x,y))表示像素点f(x,y)的共同连通域标值表示某个共同连通域标号。common号。
扫描二值图像时，common按如下方法处理：
(i)当f(x,y)f(x,y1)且f(x,y)f(x1,y)时，表明像素点f(x,y)属于新的连(merge(x,y))emerge(x,y) 。通，则共同连通域标号common新增一个元素。即common
(ii)扫描图像时，当出现f(x,y)f(x,y1)且f(x,y)f(x1,y)和
merge(x,y)merge(x,y1)且merge(x,y)merge(x1,y)时，则说明遇到标号冲突，
(i)=common(merge(x1,y))则修改其需扫描common数组一遍，任一元素i,若common(i)common(merge(x,y1))。 共同连通域标号common扫描图像时，若出现新的孤点，即f(x,y)f(x,y1)且f(x,y)f(x1,y)时，共同连通域标号common新增元素标记该元素。若元素f(x,y)与它的左邻域f(x1,y)和上邻
(x1,y)与emerge(x,y1)不一致，则表明连域f(x,y1)连通，且连通域标号emerge(x1,y)与emerge(x,y1)不连通，需要合并，因此要对共同连通域标号通域emerge(x1,y)的元素改为emerge(x,y1)。 中所有的值等于emergecommon经合并处理后，emerge的元素表示像素点的待合并连通域。但emerge表示的连通域会有大量的冲突标号，因此用数组common标记emerge各元素的共同连通域。此时，
的值是断续的，对后续的处理很不利，需要对common及emerge的标号调整。 common调整方法如下：
定义临时一维数组temp及变量nIndex，temp大小与common相同。temp元素初始化为-1。nIndex初始化为0。
(x,y)作如下操作： 扫描emerge数组，对任一元素emerge(i)若temp(common(emerge(x,y))<0，则
nIndex=nIndex+1；
temp(common(emerge(x,y))=nIndex; emerge(x,y)=temp(common(emerge(x,y));
(emerge(x,y))0,即该共同连域已出现过，则 (ii)若temp(commonemerge(x,y)=temp(common(emerge(x,y));
上述调整主要完成合并图像等价连通域，并按出现的先后次序，标记合并后的连通域。
操作(i)表示：该等价标号所指的共同连通域标号首次出现，因此标号自动加1。操作(ii)表示：该等价标号所指的共同连通域标号至少已出现过1次，因此只需temp的已分配的标号直接
(x,y)即可。 赋给emerge图像的第一行像素点没有上邻域，第一列没有左邻域，需特殊处理。如下所示：
(i)二值图像左上角的像素f(0,0)，由于是第1个扫描的像素，无需考虑相邻点连通性。
(ii)二值图像第1行(最上行)的像素f(x,0)，只需考虑左相邻像素的连通性。
(iii)二值图像第1列(最左列)的像素f(0,y)，只需考虑上相邻像素的连通性。
除此之外的所有像素都要考虑左、上2个相邻像素的连通性来确定自己的连通性。
2.4算法数据结构描述
本算法改进了顺序扫描法，以二维数组保存像素点连通域标号，在第一阶段保存待合并连通域标号，第二阶段保存目标连通域标号；以一维数组保存共同连通域标号；以一维结构数组保存目标连通域的属性。为便于说明，现对所需的数据结构进行说明:
int* emerge ;
emerge用于保存二值图像扫描后的连通域的标号，标号会有冲突标号。每个像素点用一个标号标记像素点所属的连通域。emerge的大小与图像尺寸相同。
int *common;
common用于保存共同连通域标号，以待合并连通域标号为该数组的下标。指示待合并连通域标号所属的共同连通域。
typedef struct tagAttr
{long size;//包含像素个数，也叫面积 POINT center;//中心点 RECT rect;//外接矩形 } pattr;
pattr* pObjectAttr;
pObjectAttr保存目标的属性,目标标识后,每个目标均分配一个结构数据块,保存其属性。该数组的元素表示某个目标连通域的属性。
由于初始分配空间时，并未知道目标连通域的数量，因此假定足够大的连通域数，例如 int maxsize=5000;
2.5算法实现
算法运行分为两个阶段，设f(x,y)是图像的像素点： 第一阶段：
(1)提取图像参数，如宽nWidth和高nHeight等。 (2)初始化emerge(0,0)=0,common(0)=0,nIndex=0;
(3)扫描图像第1行，x从1开始，标记待合并连通域标号emerge(x,0),和共同连通域 common。按如下处理：
若f(x,0)=f(x-1,0)，则跳过当前像素点即x=x+1,否则nIndex=nIndex+1,emerge(x,0)=nIndex, common(emerge(x,0))=emerge(x,0);
(4)扫描图像其余行
(i)标记图像每行的第1个像素f(0,y)，
若f(0,y)=f(0,y-1),则emerge(0,y)=emerge(0,y-1);
若f(0,y)≠f(0,y-1),则nIndex=nIndex+1,emerge(0,y)=nIndex, common(emerge(0,y))=emerge(0,y); (ii)标记其余像素点f(x,y)(x>0,y>0)
若f(x,y) =f(x-1,y)且f(x,y)≠f(x,y-1)，则emerge(x,y)=emerge(x-1,y)； 若f(x,y)≠f(x-1,y)且f(x,y)=f(x,y-1)，则emerge(x,y)=emerge(x,y-1)；
若f(x,y)=f(x-1,y)且f(x,y)=f(x,y-1)，则比较emerge(x-1,y)和emerge(x,y-1)， 若emerge(x-1,y)=emerge(x,y-1)，则emerge(x,y)=emerge(x,y-1); 若emerge(x-1,y)≠emerge(x,y-1)，则扫描common,对任一元素i，
若元素common(i)=common(emerge(x-1,y)),则common(i)=common(emerge(x,y-1))。 若f(x,y)≠f(x-1,y)且f(x,y)≠f(x,y-1)，则nIndex=nIndex+1,emerge(x,y)=nIndex, common(emerge(x,y))=emerge(x,y);
第二阶段：
合并图像等价连通域，并按出现的先后次序，标记合并后的连通域。
(1)定义临时一维数组temp及变量index，temp大小与common相同。temp元素初始化为-1。index初始化为0。
(2)扫描emerge数组，按如下操作：
若temp(common(emerge(x,y))) <0，则 temp(common(emerge(x,y))) =index; index=index+1；
若temp(common(emerge(x,y))) ≥0,即该共同连域已出现过，则 emerge(x,y)=temp(common(emerge(x,y))) ;
3 算法特点分析
(1) 初次扫描图像过程中，在标记待合并的连通域的同时，对冲突标号进行初步标记，即用一维数组记录等价标号的共同连通域标号，一方面当遇到等价标号时，无需回溯扫描；另一方面，在扫描图像时，完整保留标号冲突的信息，标记等价连通域的共同标号。
(2)待合并连通域标号扫描，集中处理等价标号，一方面合并等价连通域，用共同连通域标号标记像素点，用二维数组标记各像素点的连通域标号，后续图像处理，可根据像素点坐标，索引连通域标号；另一方面，重新排列各连通域标号，以扫描过程出现的次序，标记各连通域。
(3)本算法采用顺序存储结构保存待合并连通域标号和共同连通域标号，利用像素点连通域标号的存储空间，不同阶段分别存储待合并连通域标号和像素点的最终目标连通域标号，既节约算法所需内存又提高连通域标号索引的速度；一次扫描图像后，即可通过待合并连通域标号索引共同连通域标号，获得目标连通域标号，但将给后续的目标处理带来麻烦，因此算法采用二次扫描方式，第二次扫描，重新排列各连通域标号，用二维数组标记各像素点的目标连通域标号。
4结束语
本文算法综合了连续缓冲块快速索引的优点和无回溯扫描的优点，提出像素扫描法的改进和优化算法；本算法充分利用图像扫描的信息，快速地标记目标连通域，较之原算法多次扫描图像相比具有速度快，和链表、树和堆栈等数据结构相比，具有节约内存，快速索引的特点。
参考资料
[1]Rafael C.Gonzalez,Richard E.Woods.Digital Image Processing [M].2nd ed.北京:电子工业出版社,2007
[2]Sonka M,Hlavac V,Boyle R.Image Processing,Analysis,andMachine Vision[M].2nd ed.北京:人民邮电出版社,2002
[3]Bulgarelli A,Stefano L D.A Simple and Effeient Connected Component Labeling Algorithm.In: Proc of the 10th Internationa1 conference on Image Analysis and Processing,Venice,Italy,1999: 322-327
[4]Yang,X.D.An Improved Algorithm for Labeling Connected Components in a Binary Image[J]. International Joumal of Computer Vision,Graphies,and Image Processing, 1992,555-569 [5]Fast Connected Component Labeling Algorithm Using A Divide and Conquer Technique[R]. TR-2000-04,Department of Computer Science,The University of Alabama
[6]IRANIM,ANANDAN P,BERGEN J.Efficient representations of video sequences and their applications[J]. Signal Processing: Image Communication, 1996, 8(4): 327-351
[7]孙莹涛,李玉山.多运动目标跟踪及连通域标记方法[J].电子元器件应用,2007,9(5):44-48 [8]徐正光,鲍东来,张利欣.基于递归的二值图像连通域像素标记算法[J].计算机工程,2006,32(24):186:225
[9]REDDY B S,CHATTERJIB N.A FFT-based technique for translation, rotation, and scale invariant image registration[J]. IEEE Transactions on Image Processing, 1996, 5(8), 1266-1271 [10]BARTOLIA,DALALN,BOSE B.From video sequences tomotion panoramas[C] USA:IEEE Computer Society, 2002: 201-207
[11]朱云芳,叶秀清,顾伟康.视频序列的全景图拼接技术[J].中国图象图形学报,2006,11(8): 1150-1155
[12]王钲旋,李志林,庞云阶.一个二值图像连通成份标记的快速算法[J].工程图学学报, 1998,3(13):80-86
[13]张修军,郭霞,金心宇.带标记矫正的二值图像连通域像素标记算法[J].中国图像图形学报,2003,8(2):198-201
[14]刘贤喜,李邦明,苏庆堂,刘中合,王玉亮,杨峰.一种新的二值图像连通区域准确标记算法[J]计算机工程与应用,2007,43(22):76-98
---------------------------------
收稿日期：
Biography: LUO Zhi-Zao,male, was born in Sanming of Fujian province in1971,lecturer,work in department of electronic engineering in Minjiang University,His research work refers to the development of digital image and embedded system Linux.
因篇幅问题不能全部显示，请点此查看更多更全内容