一種二值圖像物體形狀特征計算方法

何立風， 高啟航， 趙 曉， 姚 斌

(陜西科技大學 電氣與信息工程學院， 陜西 西安 710021)

0 引言

二值圖像連通域(物體)的形狀特征提取是物體識別、圖像分析和計算機視覺等領(lǐng)域不可或缺的處理.連通域的形狀特征一般包含面積、周長、圓形度和重心等[1-3].連通域形狀特征的計算一般以連通域標記算法為前提.首先要對圖像中的各個連通域用不同的標號進行標記，再根據(jù)標號對各個連通域進行形狀特征的計算.主流的連通域標記算法[4]有以下兩類：

(1)標號傳播算法[5,6].該類算法首先尋找一個未標記的像素，將其用一個新的標號進行標記，再用該標號標記該像素所在連通域的所有其他像素.此類算法中最高效的是文獻[6]中提出的基于邊界追蹤的連通域標記算法.

(2)基于等價標號解析的算法[7-17].此類算法按照掃描像素的次數(shù)可分為多次掃描[7,8]、二次掃描[9-16]和四次掃描[17]算法.首先，對掃描中遇到的前景像素分配一個暫定標號并將屬于同一連通域的不同暫定標號記錄為等價標號(同一連通域上的所有暫定標號都將是等價標號).其次，通過解析等價標號關(guān)系，將等價標號中的最小標號作為該連通域所有暫定標號的代表標號.最后，將各個像素的暫定標號用其代表標號進行替換，得到最終的標號.

針對現(xiàn)有的物體形狀特征提取的方法[1-3]只能處理不含孔洞的物體的局限性，本文提出一種計算含有孔洞的物體的形狀特征的算法.在上述的連通域標記算法中，文獻[6]中提出的基于邊界追蹤的連通域標記算法可以在進行標記的同時提取連通區(qū)域的邊界，并具有一次標記、標號值不會改變且標號值連續(xù)的特點.本文提出的算法是在基于邊界追蹤的連通域標記算法的基礎(chǔ)上，融合了物體形狀特征計算.實驗結(jié)果表明本算法能有效地進行連通域標記和物體形狀特征提取.

1 背景知識

M×N的二值圖像I(M,N)在(x,y)處的像素及其值用p(x,y)表示，其中0≤x

連通域標記示意圖如圖1所示.經(jīng)過標記的圖像，每個連通域上的像素都由一個相同的標號(數(shù)字)標記，不同的連通域代表不同的物體，具有不同的標號.由于二值圖像中的前景像素值為1，所以為了區(qū)分標號值與原始二值圖像的前景像素值，在基于邊界追蹤的連通域標記算法中，連通區(qū)域的標號取2以上的整數(shù).

圖1 連通區(qū)域標記示意圖

1.1 連通域基本形狀特征的定義

連通區(qū)域基本形狀特征主要有面積、周長、圓形度和重心等[2].

(1)面積

面積的定義：連通域內(nèi)所有像素的個數(shù)，用A表示.

(2)周長

圖2 四種邊界模式

(3)圓形度

圓形度是衡量連通域形狀的重要特征，是表示連通域圓形程度的指標，值介于0和1之間，用C表示.圓形度的計算與連通域的面積與周長有關(guān).如果連通域中含有孔洞，則計算圓形度時的面積包括孔洞面積H.圓形度的計算公式如下所示：

C=4π·(A+H)/P2

(1)

從公式(1)中可以看出，當C=1時，連通區(qū)域即為圓形；C越小，連通區(qū)域與圓形差距越大.

(4)重心

連通區(qū)域的重心和中心含義相同，用所有像素點的中心位置表示.中心位置即所有坐標點的行和列的坐標值的平均值.設(shè)重心坐標為(X,Y)，計算公式如下所示：

(2)

(3)

1.2 邊界追蹤標記算法

連通域形狀特征的計算是基于連通域標記算法的.邊界追蹤標記算法是連通域標記算法中的一種典型算法，該算法能同時完成連通域標記和連通域邊界提取.邊界追蹤標記算法的大致思路是：從上到下、從左到右掃描圖像像素，當掃描到前景像素時，按照下面四個步驟處理：

(1)當掃描到的前景像素是未標記的外邊界像素Aout時，首先用一個新的標號l標記該像素，然后從該像素出發(fā)進行外邊界追蹤操作直到回到像素Aout，用相同的標號l標記這個連通域的外邊界上所有的像素，如圖3(a)所示；

(3)當掃描到的、已標記過的前景像素是未經(jīng)內(nèi)邊界追蹤處理過的內(nèi)邊界像素Ain時，從該像素出發(fā)進行內(nèi)邊界追蹤操作直到回到像素Ain，并用Ain的標號標記該內(nèi)邊界上的所有像素，如圖3(c)所示；

(a) 未標記的外邊界 (b) 已標記的外邊界

(c) 未處理的內(nèi)邊界 (d) 已處理的內(nèi)邊界圖3 邊界追蹤標記步驟示意圖

另外，在以上四個步驟中，當進行外邊界追蹤時，用-1標記與邊界像素鄰接的背景像素，在圖3中用“-”表示；在進行內(nèi)邊界追蹤時，用-2標記與邊界像素鄰接的背景像素，在圖3中用“*”表示.

算法中的邊界追蹤方法簡述如下：

邊界追蹤的目的是找到連通域的外邊界或內(nèi)邊界.邊界追蹤的大致思路為：設(shè)P為邊界追蹤的起始當前像素，初始檢查方向為K.如果P是一個孤立像素，則結(jié)束追蹤；否則，從K方向開始沿順時鐘方向檢查該方向上的P的鄰接像素，如果檢查中的鄰接像素為前景像素，則該像素也是邊界像素，把該像素作為當前像素繼續(xù)(重復)邊界追蹤處理，直到下列兩個條件同時得到滿足時終止：①當前像素為起始像素P；②檢查方向與起始像素P的初始檢查方向K一致.

外邊界追蹤與內(nèi)邊界追蹤的唯一區(qū)別在于初始檢查方向不同.方向標號表示圖如圖4所示.外邊界追蹤的初始方向為起始像素P的正上方，在圖4中為像素A0的方向；內(nèi)邊界追蹤的初始方向在P的正下方，在圖4中為像素A4的方向.

圖4 方向標號表示圖

2 基于邊界追蹤的連通域形狀特征計算方法

在使用邊界追蹤標記算法對連通域進行標記時，需要對連通域的邊界進行追蹤.在進行邊界追蹤的同時，可以計算連通域的邊界長(周長)，這為計算連通域的形狀特征提供了極大的方便.如上所述，連通域的形狀特征包括面積、周長、圓形度和重心.根據(jù)前述形狀特征的定義，可在邊界追蹤標記的基礎(chǔ)上按照下列方法計算連通域的形狀特征：

(1)連通域的面積為連通域上所有像素個數(shù)之和，所以只須在連通域標記過程中添加對每一個標號的像素的計數(shù)操作，就可以在結(jié)束圖像掃描時完成所有連通域的面積計算；

(2)連通域的周長為外邊界的長度，因此可以在對連通域進行外邊界追蹤的過程中同時計算該連通域的周長；

(3)重心坐標是連通域內(nèi)所有像素點的坐標的平均數(shù)，所以在標記連通域時，對同一標號的像素的橫縱軸坐標分別進行累加，在標記結(jié)束后用相應(yīng)的累加值除以該連通域的面積就可得到重心坐標；

(4)圓形度與連通域的面積、連通域內(nèi)的孔洞面積以及連通域的外周長有關(guān)，由公式(1)計算.各個連通域的面積和連通域的外周長可由上述(1)和(2)分別獲得.而各個連通域的孔洞面積可以在標記結(jié)束后，通過再次掃描圖像計算.

算法的偽代碼如下：

算法：使用邊界追蹤標記算法計算連通域基本形狀特征

InitializeA,H,P,C,X,Y←0

l=2

x=0,y=0

Whiley

|Whilex

| |Ifp(x,y)==1

| | |Ifp(x,y)是未被標記的外邊界像素

| | | |OuterTrace(p(x,y),l)

| | | |Ifp(x,y)是未被內(nèi)邊界追蹤處理過的

| | | | 像素

| | | | |InnerTrace(p(x,y),l)

| | | |EndIf

| | | |l++

| | |Else

| | | |Whilep(x,y)==1

| | | | |Ifp(x,y)是未被標記的內(nèi)邊界像素

| | | | | |InnerTrace(p(x,y),p(x-1,y))

| | | | |Else

| | | | | |p(x,y)=p(x-1,y)

| | | | | |A[p(x,y)]+=1

| | | | | |X[p(x,y)]+=x,Y[p(x,y)]+=y

| | | | |EndIf

| | | | |x++

| | | |EndWhile

| | |EndIf

| |x++

|EndWhile

|y++

EndWhile

% 計算孔洞面積

x=0,y=0

Whiley

|Whilex

| |Ifp(x,y)屬于標號m的孔洞部分：

| | |H[m]+= 1

| |EndIf

|EndWhile

EndWhile

% 計算各個連通域的圓形度和重心

i=2

Whilei

|C[i]=4π*(A[i]+H[i])/(P[i]∧2)

|X[i]/=A[i],Y[i]/=A[i]

EndWhile

在執(zhí)行外邊界追蹤函數(shù)OuterTrace時，從像素p(x,y)開始沿外邊界追蹤邊界像素，邊標記邊計算累加面積和周長，并將檢查到的背景像素標記為-1.該函數(shù)偽代碼如下：

FunctionOuterTrace(p(x,y),l)

|For從像素p(x,y)開始的外邊界追蹤處理中

| | 的每個當前像素p(u,v)

| |Ifp(u,v)是背景像素

| | |p(u,v)=-1

| |Else

| | |p(u,v)=l

| | |A[l]+=1

| | |X[l]+=x,Y[l]+=y

| | |Ifp(u,v)與前一個外邊界像素在同行或

| | | 同列

| | | |P[l]+=1

| | |Else

| | |EndIf

| |EndIf

|EndFor

End

由于連通域內(nèi)邊界與周長無關(guān)，所以在執(zhí)行內(nèi)邊界追蹤函數(shù)InnerTrace時，不需要計算周長，其偽代碼如下：

FunctionInnerTrace(p(x,y),l)

|For從像素p(x,y)開始的內(nèi)邊界上追蹤處理

| 中的每一個當前像素p(u,v)

| |Ifp(u,v) 是背景像素

| | |p(u,v)=-2

| |Else

| | |p(u,v)=l

| | |A[l]+=1

| | |X[l]+=u,Y[l]+=v

|EndFor

End

第一次掃描完畢后，對于標號為l的連通域，其面積和外周長分別為A[l]和P[l]；重心的橫縱坐標可分別由X[l]=X[l]/A[l]和Y[l]=Y[l]/A[l]計算.由于在對標號為l的連通域的內(nèi)邊界追蹤時將掃描到的背景像素用-2標記，孔洞部分可以看作以-2為邊界的背景像素的連通域.在第二次掃描中，統(tǒng)計孔洞部分的像素個數(shù)就能得到相應(yīng)的孔洞面積.這樣，標號為l的連通域的圓形度C[l]可由C[l]=4π*(A[l]+H[l])/(P[l]∧2)計算.如果連通域不含孔洞，則在第二次掃描中不會做任何處理，所以算法也同樣適用于不含孔洞的連通域形狀特征的計算.

3 實驗結(jié)果

為了驗證本文提出的計算物體特征算法的有效性，在圖5(a)所示的測試圖像進行了測試.算法程序用C語言編寫，編譯環(huán)境為GCC 5.4.0，操作系統(tǒng)為Ubuntu14.04 64位.計算機硬件配置為：Intel i5-3470 3.2 GHz雙核處理器，4 GB內(nèi)存.圖5(b)是經(jīng)過連通域標記的圖像，每個連通域上方的數(shù)字代表其標號值.表1為各個連通域(物體)的各種形狀特征的計算結(jié)果.算法在測試圖像上運行500次的平均運行時間為7.36毫秒.

(a) 測試圖像 (b) 帶標號的圖像圖5 測試圖像與標記后的圖像

標號周長面積孔洞面積重心(X)重心(Y)圓形度21228．7775949211922056880．813867．5041440126222912360．9041002．015718605317110．7251266．0064525282716022660．736984．192761148767897200．427711．972799286258682370．91

4 算法性能分析

基于邊界追蹤的連通域標記算法只需掃描圖像一次.在掃描過程中，非邊界像素只訪問一次，邊界像素被訪問的次數(shù)不超過4次，因此算法在線性時間內(nèi)完成[6]，時間復雜度為O(n)，其中n為圖像的像素個數(shù).本文提出的算法在第一次掃描圖像時，與連通域標記算法對像素的掃描方式和訪問模式相同，在第二次掃描時，只對孔洞區(qū)域進行處理，故本文算法的時間復雜度也為O(n).

基于邊界追蹤的連通域標記算法在原始圖像上完成標記，不需要占用額外空間，因此其空間復雜度為O(1).本文連通域形狀特征計算方法與此標記算法相比只需要存儲各個連通域的形狀特征量等，故算法所占空間僅依賴于連通域的數(shù)量.由于像素個數(shù)為n的圖像的最大連通域的數(shù)量為n/4[11]，因此本文算法的空間復雜度為O(n).

5 結(jié)論

本文在基于邊界追蹤的連通域標記算法的基礎(chǔ)上，首次提出了一種計算二值圖像中含孔洞物體的形狀特征的算法.本文提出的計算含有孔洞的物體的形狀特征的算法優(yōu)點有：①可以同時進行連通域標記和形狀特征的計算；②除了計算連通域的形狀特征，算法還可以直接提取連通域的邊界；③本文算法在線性時間和線性空間內(nèi)完成；④本文算法可擴展性好，經(jīng)過簡單擴展還可應(yīng)用于歐拉數(shù)、密度等其他形狀特性的計算.實驗結(jié)果表明本算法可以有效的計算二值圖像中含有孔洞的連通域的基本形狀特征.

[1] Rafael Gonzalez,Richard Woods.數(shù)字圖像處理[M].3版.阮秋琦,阮宇智.北京:電子工業(yè)出版社，2017.

[2] Richard Szeliski.計算機視覺：算法與應(yīng)用[M].1版.艾海舟，興軍亮.北京:清華大學出版社，2012.

[3] David Forsyth,Jean Ponce.計算機視覺——一種現(xiàn)代方法[M].2版.高永強.北京:電子工業(yè)出版社，2017.

[4] He L,Ren X,Gao Q,et al.The connected-compo-nent labeling problem:A review of state-of-the-art al-gorithms[J].Pattern Recognition,2017(70):25-43.

[5] Hu Q,Qian G,Nowinski W L.Fast connected-component labelling in three-dimensional binary images based on iterative recursion[J].Computer Vision and Image Understanding,2005,99(3):414-434.

[6] Chang F,Chen C J,Lu C J.A linear-time compo-nent-labeling algorithm using contour tracing technique[J].Computer Vision and Image Understanding,2004,93(2):206-220.

[7] He L,Chao Y,Suzuki K.A run-based one-and-a-half-scan connected-component labeling algorithm[J].International Journal of Pattern Recognition and Artificial Intelligence,2010,24(4):557-579.

[8] 馮海文,牛連強,劉曉明.高效的一遍掃描式連通區(qū)域標記算法[J].計算機工程與應(yīng)用,2014,50(23):31-35.

[9] Wu K,Otoo E,Shoshani A.Optimizing connected component labeling algorithms[C]//Proceedings of the 19th International Conference on Information Processing in Medical Imaging. Glenwood:IEEE,2005:1 965-1 976.

[10] He L,Chao Y,Suzuki K.A run-based two-scan labeling algorithm[J].IEEE Transactions on Image Processing,2008,17(5):749-756.

[11] He L,Chao Y,Suzuki K,et al.Fast connected-component labeling[J].Pattern Recognition,2009,42(9):1 977-1 987.

[12] 謝宜壯,譚許彬,陳 禾.一種新的連通域標記算法[J].北京理工大學學報,2012,32(12):1 273-1 278.

[13] Zhao X,He L,Yao B,et al.A new connected-component labeling algorithm[J].IEICE Transactions on Information & Systems,2015(11):2 013-2 016.

[14] 牛連強,彭 敏,孫忠禮,等.利用游程集合的標號傳播實現(xiàn)快速連通域標記[J].計算機輔助設(shè)計與圖形學學報,2015,27(1):128-135.

[15] Grana C,Borghesani D,Cucchiara R.Fast block based connected components labeling[C]//Proceedings of the International Conference on Image Processing.Cairo:IEEE,2009:4 061-4 064.

[16] He L,Chao Y,Zhao X,et al.Configuration-transition-based connected-component labeling[J].IEEE Transactions on Image Processing,2014,23(2):943-951.

[17] Suzuki K,Horiba I,Sugie N.Linear-time connected-component labeling based on sequential local operations[J].Computer Vision and Image Understanding,2003,89(1):1-23.