張 恒 倪永婧

（1中國電子科技集團公司第五十四研究所，河北 石家莊 050081)（2河北科技大學(xué)，河北 石家莊 050011）

面向目標特征提取的連通域標記算法

張 恒1倪永婧2

（1中國電子科技集團公司第五十四研究所，河北 石家莊 050081)（2河北科技大學(xué)，河北 石家莊 050011）

目標特征是目標分類識別的基礎(chǔ)，在二值圖像中?；谙袼剡B通關(guān)系進行提取并通過連通域標記使所含像素能便捷訪問。文章簡要分析了常見連通域標記算法的性能，針對三種特殊而常見的連通域與目標間的對應(yīng)關(guān)系指出其在目標特征提取中的不適用性，為提高目標特征完整性和準確性在目標語義層次重新定義了像素連通，利用區(qū)域邊界掃描以及對邊界像素的有效標記，將取決于二維信息的連通關(guān)系識別轉(zhuǎn)化到一維中，使每行（列）的處理過程相互獨立，從而實現(xiàn)一遍逐行（列）的圖像掃描即可完成特征提?。ò繕溯喞┘斑B通域標記，且標號連續(xù)。最后通過仿真從效率、適用性及內(nèi)存耗費等方面對算法進行了驗證與分析。

連通域標記輪廓跟蹤特征提取

1 引言

目標特征是目標分類識別的基礎(chǔ)，后者在圖像分析及計算機視覺等多個領(lǐng)域都有著廣泛應(yīng)用。由圖像分割或運動檢測得到的像素連通區(qū)域與實際目標存在對應(yīng)關(guān)系，連通域標記也因此成為提取目標特征的有效手段。本文結(jié)合實際，從目標語義理解角度定義像素連通，提高特征的完整性和準確性；進而基于輪廓標記判定像素連通關(guān)系及所屬目標，同時提取特征。算法經(jīng)一遍掃描完成原圖目標標記處理且標號連續(xù)，并將目標特征存儲在一維數(shù)組的相應(yīng)位置，便于通過標號直接訪問和應(yīng)用。

2 實現(xiàn)方法

按像素連通關(guān)系對圖像中同值區(qū)域進行分類是連通域分析的主要內(nèi)容，為便于同類像素訪問類屬性（如標號、特征等），還需將類屬性的存儲位置信息反饋給所含的每個像素，該過程可由連通域標記算法實現(xiàn)。這樣連通域分析包括連通信息收集和下發(fā)2個過程，按處理方式的不同可分為逐行式[1-[4]2種。前者逐行收集、下發(fā)連通信息，存在固有的標號沖突問題，通過改善連通信息記錄、更新的方式并斟酌下發(fā)的時機可在不同程度上提高算法效率；后者逐鄰域收集、下發(fā)連通信息，對鄰域大量的重復(fù)處理成為影響算法性能的主要因素。提高信息處理單位的層次，如行程而非像素，能在一定程度上改善算法性能[5-9]。

3 應(yīng)用局限性

受掃描順序影響，上述算法不能方便地提取目標輪廓，而輪廓正是目標形狀特征的集中反映，從而丟失了后續(xù)目標分類識別的有效依據(jù)。

基于連通域分析提取目標特征，其成立的前提是同一目標的像素在圖像中完備連通，而不同目標的像素不具有連通關(guān)系，即目標與連通域一一對應(yīng)。但由于種種原因，同一個目標的像素可能分布于不同的前景連通域，甚至背景連通域，此時單純依靠上述算法提取目標特征是失效的。

4 連通域分析

4.1 目標連通定義

二值圖像中，連通域與實際目標可能存在多種對應(yīng)關(guān)系，比較特殊而常見的有3種：①目標和前景連通域一一對應(yīng)；②目標與前景連通域及為其所包圍的前景連通域?qū)?yīng)；③目標與前景連通域及為其所包圍的背景連通域和前景連通域?qū)?yīng)。連通域與目標間不同對應(yīng)關(guān)系及連通域標記結(jié)果如圖1所示。

圖1 連通域與目標的不同對應(yīng)關(guān)系及標記結(jié)果示意圖

同屬一個目標的像素，不論其分布于前景連通域還是背景連通域，都會對目標特征有貢獻。為提高目標特征的完整性和準確性，在目標語義層次定義這些像素是連通的，進而基于連通域分析提取目標特征。

4.2 目標輪廓及標記

輪廓是目標形狀特征的集中反映，在平面圖像中體現(xiàn)為連通域邊界像素的有序集，可分外輪廓和內(nèi)輪廓，其中外輪廓是對不同目標的分隔，內(nèi)輪廓是對目標不同組成部分的分隔，輪廓像素鄰域中的背景像素稱為目標的包圍像素。

連通定義不同，輪廓特點也不盡相同，如圖2所示。在對應(yīng)關(guān)系①下，目標的所有輪廓都是外輪廓，沒有內(nèi)輪廓；對應(yīng)關(guān)系②下，目標有且只有一條外輪廓，可以有多條內(nèi)輪廓；對應(yīng)關(guān)系③下，目標有且只有一條外輪廓，沒有內(nèi)輪廓。但不論哪種對應(yīng)關(guān)系，任一目標都有且只有這樣一條外輪廓，即若順（逆）時針遍歷該輪廓則目標像素均位于其右（左）側(cè)，使得在逐行掃描過程中最先遇到的像素必處在該輪廓上。利用這個特點對連通域作標記處理，就可以實現(xiàn)不經(jīng)任何處理而使目標標號連續(xù)。

利用目標輪廓的封閉特性，可以完成輪廓像素的有序遍歷[11]和目標輪廓特征的提取。在該過程中，對輪廓像素及相應(yīng)的包圍像素進行標記（輪廓像素標記為目標標號，外輪廓包圍像素標記位-1，內(nèi)輪廓包圍像素標記為目標標號的相反數(shù)），從而將基于多維信息的連通關(guān)系判定轉(zhuǎn)化到一維（行或列）中，減少連通域關(guān)系判定中像素的重復(fù)掃描[4][9,10]或可能的等價關(guān)系存儲、處理[5-8]等。

圖2 對應(yīng)關(guān)系與目標輪廓示意圖

圖2中字母表示所屬目標，下標o代表外輪廓，i代表內(nèi)輪廓，數(shù)字代表在其所屬目標中的輪廓序號，箭頭表示本文輪廓跟蹤順序。

4.3 目標連通關(guān)系判定

根據(jù)輪廓的封閉特性，若像素屬于某目標，則必被該目標的輪廓所包圍，在其所屬行（列）中亦然；而輪廓跟蹤可以完成對輪廓點及包圍點的正負標記，使任一目標被正負對包圍。這樣在每行（列）中，像素被正負對分割成目標區(qū)和非目標區(qū)2種狀態(tài)區(qū)間（后者在對應(yīng)關(guān)系②下又可進一步分為內(nèi)非目標區(qū)和外非目標區(qū)），同一區(qū)間內(nèi)的像素具有連通性，且連通性的改變只可能發(fā)生在正負對處。這樣就將基于多維信息的連通關(guān)系判定轉(zhuǎn)化到一維（行或列）中，且各行(列)的判定過程相互獨立，通過對圖像逐行（列）掃描，即可完成連通關(guān)系判定和目標特征提取。

5 算法實現(xiàn)

5.1 數(shù)據(jù)結(jié)構(gòu)

其中，F(xiàn)Type為針對不同對應(yīng)關(guān)系所采用的相應(yīng)分析規(guī)則，該值至晚在外輪廓跟蹤后確定。flag為目標序號，也為目標像素的標號，與在一維數(shù)組中的存儲位置直接相關(guān)。pFeature指向為目標特征分配的存儲空間。

定義一維object型數(shù)組array_objects，數(shù)組大小視可能的最大目標數(shù)而定。

5.2 算法描述

不妨設(shè)原二值圖像中前景像素為1，背景像素為0，并初始化目標序號為2。首先將圖像上下左右邊界像素統(tǒng)一標記為-1[11]，同時初始化區(qū)間狀態(tài)為非目標區(qū)，然后進行逐行掃描。為敘述方便，用P表示當前像素，V表示像素值，F(xiàn)記錄目標標號，Tag記錄區(qū)間狀態(tài)。根據(jù)區(qū)間狀態(tài)對連通域分析算法作如下描述：

ⅠTag=-1，即非目標區(qū)：

A若V=1，則更新F為F+1，并以P為起始點啟動輪廓遍歷，同時分別標記輪廓點和包圍點為F和-1，最后更新Tag為F；

B若V躍1，則更新Tag為V。

ⅡTag躍1，即目標區(qū)：

A若V約0，則更新Tag為V；

B若V=0，針對不同對應(yīng)關(guān)系相應(yīng)處理如下：

①對應(yīng)關(guān)系I：啟動外輪廓遍歷，標記輪廓點為Tag，包圍點為-1，并將輪廓特征計入目標Tag；

更新Tag為-1；

②對應(yīng)關(guān)系II:啟動內(nèi)輪廓遍歷，標記輪廓點為Tag，包圍點為-Tag，并將輪廓特征計入目標Tag；更新Tag為-Tag；

③對應(yīng)關(guān)系III:標記P為Tag；并將特征計入目標Tag；

C若V=1，則標記P為Tag，并將特征計入目標Tag。

ⅢTag約-1，即內(nèi)非目標區(qū)（僅限于對應(yīng)關(guān)系②）：

A若V=1，則更新Tag為-Tag；啟動內(nèi)輪廓遍歷，標記輪廓點為Tag，包圍點為-Tag，并將輪廓特征計入目標Tag；

B若V躍1，則更新Tag為V。

6 實驗與分析

本節(jié)在Windows XP操作系統(tǒng)、奔4處理器、3G主頻、1G內(nèi)存的測試平臺下，對算法性能及實際應(yīng)用給出驗證。

6.1 算法效率及魯棒性

本節(jié)采用多種測試圖像檢驗算法效率及其魯棒性，包括漢字、指紋、指紋骨架等，并對這些圖像作旋轉(zhuǎn)、翻轉(zhuǎn)等變換，以探求圖像掃描順序、連通域形狀及相對分布對算法效率的影響。將本文算法與經(jīng)典的回溯處理式[1]、種子增長式[4]及基于行程的優(yōu)化算法[5]按對應(yīng)關(guān)系①作效率對比，測試中只關(guān)心前景連通域并采用8-連通鄰域定義，且要求連通域標號連續(xù)（回溯法未作此要求）。同時定義時間耗費的平均相對偏差衡量算法魯棒性。

表1 連通域標記算法效率及魯棒性

注：像素回溯和行程等價算法中最大標號標注于所耗時間后的括號內(nèi)。

可以看出，相對于文獻算法，本文算法在效率、魯棒性等方面都獲得了極大改善?；谥鹦惺占B通關(guān)系的像素回溯式、行程等價式等算法的魯棒性不及逐鄰域式，這是因為連通信息不完備導(dǎo)致的標號沖突受圖像掃描順序、連通域形狀的影響更為嚴重。種子增長類算法的效率普遍較低，尤其在連通域輪廓所占比例較小的情況下，鄰域的重復(fù)處理很嚴重。本文算法所涉及的重復(fù)操作只發(fā)生在連通域輪廓處，而輪廓像素占連通域的比例通常是比較小的，且不隨圖像的變換而改變，故具有較高的效率和較好的魯棒性。實際上，在輪廓象素所占比例很小的圖像中，算法所耗時間與圖像大小成正比[10]。

6.2 目標連通標記

針對同一二值圖像，分別按對應(yīng)關(guān)系①、對應(yīng)關(guān)系②和對應(yīng)關(guān)系③進行連通域標記。為便于顯示，令標號均勻分布在[0,255]之間，標記結(jié)果如圖3所示。

圖3 二值圖像按不同對應(yīng)關(guān)系的目標標記結(jié)果

6.3 內(nèi)存耗費

7 結(jié)束語

為提高基于連通域提取的目標特征的完整性和準確性，本文針對二值圖像中3種特殊而常見連通域與目標的對應(yīng)關(guān)系，在目標語義層次重新定義像素連通，進而利用輪廓標記將取決于多行信息的連通關(guān)系判定轉(zhuǎn)化到每一行中，經(jīng)一遍圖像掃描即完成連通域標記和目標特征提取。算法運行效率高、占用內(nèi)存少且魯棒性好。

[1]劉賢喜,李邦明,蘇慶堂,等.一種新的二值圖像連通區(qū)域準確標記算法[J].計算機工程與應(yīng)用,2007(22):76-78,98.

[2]羅志灶,周贏武,鄭忠楷.二值圖像連通域標記優(yōu)化算法[J].安慶師范學(xué):學(xué)報(自然科學(xué)版),2010,16(4):34-39.

[3]宋斌.一種新的圖像連通域快速標號算法[J].電子測量技術(shù),2009,32(9):67-68,73.

[4]劉奇琦,龔曉峰.一種二值圖像連通區(qū)域標記的新方法[J].計算機工程與應(yīng)用,2012,48(11):178-180,200.

[5]張恒,胡文龍,丁赤飆.基于快速連通域分析的目標特征提取算法[J].計算機工程與應(yīng)用,2009,45(29):230-232,244.

[6]周躍,閆豐,章明朝,等.基于標號回傳的二值圖像連通體標記算法[J].計算機工程與應(yīng)用,2009,45(33):153-155.

[7]CHAO YU-YAN,KENJI SUZUKI.A run-based two-scan labeling algorithm[A].In:4th International Conference on Image Analysis and Recognition[C].Montreal,Canada, 2007,3-42.

[8]孔斌.快速連通域分析算法及實現(xiàn)[J].模式識別與人工智能,2003,6(1)：110-115．

[9]羅志灶,周贏武,鄭忠楷.基于區(qū)域增長的連通域標記算法的優(yōu)化[J].閩江學(xué):學(xué)報,2011,32(2):41-44.

[10]CHANG fu,CHEN Chunjen,LU Chijen.A linear-time component-labeling algorithm using contour tracing technique[J].Computer Vision and Image Understanding, 2003,93(2):206-220.

[11]曹長虎,李亞非.一種二值圖像連通區(qū)域標記快速算法[J].科學(xué)技術(shù)與工程,2010,10(33):8168-8171,8180.

Connected Component Labeling Algorithm Oriented to Target Feature Extraction

ZHANG Heng1,NI Yong-jing2
(1 The 54th Research Institute of CETC,Shijiazhuang Hebei 050081,China) (2 Hebei University of Science and Technology,Shijiazhuang Hebei 050011,China)

The target feature is the foundation of target classification and recognition,which can be extracted based on pixel connected relation and accessed easily by pixel through connected component labeling in binary image.This paper briefly analyzes the function of common connected component labeling algorithm,points out the inapplicability of connected component labeling algorithm in target feature extraction aiming at three kinds of special and common corresponding relations between connected components and targets,and redefines the pixel connectivity in the target semantic level to improve the completeness and accuracy of target feature.Using the regional boundary scanning and the efficient labeling,the connected relation depending on two-dimensional signal is recognized and transformed into one-dimensional to make the processing procedures in each row(column)mutually independent,so that the feature extraction(including target contour)and the connected component labeling are realized through picture scanning row by row(line by line),the labeling number is continuous.Finally,through simulation,this paper verifies and analyzes the algorithm from such aspects as efficiency,applicability and memory consumption.

connected component labeling;contour tracking;feature extraction

TP391

A

1008-1739（2015）07-58-4

定稿日期：2015-03-12