張 恒 倪永婧

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

面向目標(biāo)特征提取的連通域標(biāo)記算法

張 恒1倪永婧2

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

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

連通域標(biāo)記輪廓跟蹤特征提取

1 引言

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

2 實(shí)現(xiàn)方法

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

3 應(yīng)用局限性

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

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

4 連通域分析

4.1 目標(biāo)連通定義

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

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

同屬一個(gè)目標(biāo)的像素，不論其分布于前景連通域還是背景連通域，都會(huì)對(duì)目標(biāo)特征有貢獻(xiàn)。為提高目標(biāo)特征的完整性和準(zhǔn)確性，在目標(biāo)語義層次定義這些像素是連通的，進(jìn)而基于連通域分析提取目標(biāo)特征。

4.2 目標(biāo)輪廓及標(biāo)記

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

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

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

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

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

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

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

5 算法實(shí)現(xiàn)

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

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

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

5.2 算法描述

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

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

A若V=1，則更新F為F+1，并以P為起始點(diǎn)啟動(dòng)輪廓遍歷，同時(shí)分別標(biāo)記輪廓點(diǎn)和包圍點(diǎn)為F和-1，最后更新Tag為F；

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

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

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

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

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

更新Tag為-1；

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

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

C若V=1，則標(biāo)記P為Tag，并將特征計(jì)入目標(biāo)Tag。

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

A若V=1，則更新Tag為-Tag；啟動(dòng)內(nèi)輪廓遍歷，標(biāo)記輪廓點(diǎn)為Tag，包圍點(diǎn)為-Tag，并將輪廓特征計(jì)入目標(biāo)Tag；

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

6 實(shí)驗(yàn)與分析

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

6.1 算法效率及魯棒性

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

表1 連通域標(biāo)記算法效率及魯棒性

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

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

6.2 目標(biāo)連通標(biāo)記

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

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

6.3 內(nèi)存耗費(fèi)

7 結(jié)束語

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

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

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

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

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

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

[6]周躍,閆豐,章明朝,等.基于標(biāo)號(hào)回傳的二值圖像連通體標(biāo)記算法[J].計(jì)算機(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]孔斌.快速連通域分析算法及實(shí)現(xiàn)[J].模式識(shí)別與人工智能,2003,6(1)：110-115．

[9]羅志灶,周贏武,鄭忠楷.基于區(qū)域增長的連通域標(biāo)記算法的優(yōu)化[J].閩江學(xué):學(xué)報(bào),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ū)域標(biāo)記快速算法[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