基于游程與輪廓跟蹤的連通區(qū)域標記改進算法

楊定禮，孫山林，嚴 石,3，尹曉琦，付成芳，吳天馳，張約騁

(1. 淮陰工學院 電子信息工程學院， 江蘇 淮安 223003;2. 北京航空航天大學 儀器科學與光電工程學院，北京 100191；3. 淮陰工學院 成人教育處， 江蘇 淮安 223001)

?

基于游程與輪廓跟蹤的連通區(qū)域標記改進算法

楊定禮1，孫山林2，嚴 石1,3，尹曉琦1，付成芳1，吳天馳1，張約騁1

(1. 淮陰工學院 電子信息工程學院， 江蘇 淮安 223003;2. 北京航空航天大學 儀器科學與光電工程學院，北京 100191；3. 淮陰工學院 成人教育處， 江蘇 淮安 223001)

為了進一步提高連通區(qū)域標記的效率，提出了一種改進的基于游程與輪廓跟蹤技術(shù)相結(jié)合的連通區(qū)域標記算法。該算法首先判斷當前前景像素點是孤立點還是輪廓點，然后判斷是外輪廓還是內(nèi)輪廓，并用相應(yīng)的輪廓標記算法對其進行標記，最后用游程標記方法對本行中剩余的前景像素進行標記，整個過程無需等價表，耗時較少。實驗證明，改進后算法的標記效率提高大約24.5% 。

連通域標記；游程；輪廓跟蹤；外輪廓；內(nèi)輪廓

0 引言

一般將二值圖像進行連通區(qū)域標記的目的是:首先將二值圖像中屬于同一連通區(qū)域的所有像素檢測出來，并將每個連通區(qū)域分配唯一的標號。然后根據(jù)標號來分割出不同的物體。在分割出不同的物體以后，就可以計算每個連通區(qū)域的質(zhì)心、周長、面積等特征。這些在計算機視覺、模式識別、圖像處理等領(lǐng)域有非常重要的作用。目前二值圖像連通區(qū)域標記算法主要有：像素標記法[1]、游程編碼法[2-3]、區(qū)域生長法[4-6]、輪廓跟蹤標記算法[7]。這些算法都需要處理大量的中間信息，所消耗的時間較多。張云哲等[8]提出了一種新的基于非對稱游程和輪廓跟蹤技術(shù)相結(jié)合的連通區(qū)域標記算法，該算法避免了上述的缺點。其主要先采用輪廓跟蹤技術(shù)搜索連通區(qū)域的輪廓，然后以游程為單位來標記二值的圖像[8]。在用游程標記時，有的采用起始點像素的標記來標記游程[8]，有的采用終點的像素的標記來標記游程。在用終點的像素標記進行標記時，則必須先掃描游程的每個像素點，直到該游程終點的像素，在標記時又需要重新掃描一遍，勢必要浪費時間。本文對此進行了改進，無需掃描到游程的終點就可以得到該像素的標記。改進后算法的每一個游程的起始點一定是已經(jīng)標記過的，如果沒有標記則一定是新的輪廓的起始點，則先進行輪廓標記，再進行游程標記。主要改進有這樣幾個方面。改進一：在處理內(nèi)輪廓時，用搜索內(nèi)輪廓的方法進行標記，并用游程的標記方法[8]，但是由于在檢測是否是輪廓像素以及在上下兩行搜索游程時耗費大量的時間，所以本文提出用當前前景像素點的P5位置的標號來標記較好。P5位置的標號是非常重要的，如果P5位置有前景像素，則其為內(nèi)輪廓，必須按照內(nèi)輪廓的標記方法進行標記。如果P5位置沒有前景像素，則其為外輪廓，必須按照外輪廓的標記方法進行標記。改進二：對于外輪廓，第一次遇到的，從P0開始搜索，不應(yīng)該按照從P5開始[8]。對于內(nèi)輪廓點則要從P5開始搜索。改進三：每個游程的標記都用起始點進行標記，而不是用游程終點進行標記，也不需要搜索上一行的游程或者下一行的游程而浪費時間。

1 連通域標記的算法

在連通區(qū)域標記的過程中，不同物體的像素將被標上不同的標號，同一物體的像素則被標上相同的標號。通常的連通性有兩種：4連通與8連通。本文主要討論8連通，并從當前像素點的右側(cè)開始標號，起始標號為P0，按照順時針方向進行標號，直到P7，如圖1所示。目前常用的二值圖像連通區(qū)域標記算法大致有下面幾種方法。

5674P0321

圖1 八連通的表示

1.1 像素標記法

該方法要求對二值圖像進行多次掃描，每次掃描以后對屬于同一連通區(qū)域的像素標號進行更新，直到二值圖像中所有像素的標號不再變化，這種方法的效率較低。有研究將當前像素的8個鄰域像素進行拆分，拆分為2個子集，一個向前掃描，一個向后掃描，經(jīng)過多遍的交替掃描，不斷調(diào)整等價表，最后得到一個不變等價標號表，然后根據(jù)等價標號表得到每個像素的最終的標號[9]。這種方法缺點是要多次掃描圖像，耗費大量的時間。

1.2 游程編碼法

所謂游程是將一行中連續(xù)相連的前景像素即一條直線段作為連通區(qū)域檢測的基本單元，一行中可能有一個游程，也可能有幾個游程。游程編碼法是對二值處理后的圖像進行逐行掃描時，每當掃描出當前行的一條直線段，就和上一行檢測出的直線段進行連通性檢測，那些滿足連通性要求的直線段將被賦予相同的標號[2]。在進行第二次掃描時，應(yīng)該用等價標記中最小的標號來代替所有等價標號對應(yīng)的像素點。由于該算法充分利用了區(qū)域連通性的結(jié)構(gòu)的特征，與像素標記法相比，產(chǎn)生的等價對個數(shù)要減少很多，因而具有更高的效率。不過在工程實踐中也遇到不少問題，如當圖像較大時利用數(shù)組或者鏈表處理等價對時，占用內(nèi)存太大，甚至出現(xiàn)溢出問題[2]。

1.3 區(qū)域生長法

區(qū)域生長法可以彌補像素標記法與游程編碼法的多次掃描的缺陷，可以實現(xiàn)一次標記一個連通區(qū)域內(nèi)所有的像素，然后再標記下一個連通區(qū)域的像素，直到標記完所有的連通區(qū)域內(nèi)的像素。該方法是以當前像素為種子，用一個新的標號標記當前像素，然后標記與其相鄰的前景像素，再把它們壓入堆棧，作為種子，繼續(xù)標記，不斷重復這個過程，直到標記完整個連通區(qū)域。由于這個方法不需要用等價標記表，不受目標數(shù)量與目標圖像復雜度的影響，因而具有一定的魯棒性[2]。但是，當連通區(qū)域面積較大時，如果對每個目標像素點進行8鄰域的判斷，那么所需堆棧會較大，此時它的算法效率反而會下降。

1.4 輪廓跟蹤標記算法

輪廓跟蹤標記算法在標記時主要分三個步驟。

第一，如果遇到外輪廓起始點時，則用一個新標號來標記外輪廓。

第二，當遇到內(nèi)輪廓起始點時，要分兩種情況：(1) 如果起始點已經(jīng)標記，則用它的標號標記內(nèi)輪廓；(2) 如果該起始點沒有標記，那么它的左鄰P4一定是已經(jīng)標記的像素點，則用P4的標號標記本行內(nèi)輪廓。

第三，當遇到已經(jīng)標記的輪廓點時，用這個輪廓點的標號標記本行中位于其后的所有前景像素[8]。

2 連通區(qū)域標記的改進算法

本文在仔細研究文獻[8]后，在其基礎(chǔ)上提出了改進的方法。改進的方法是用輪廓跟蹤技術(shù)與游程標記相結(jié)合的標記方法來標記二值圖像，與文獻[8]不同的是本文先進行輪廓跟蹤再進行游程標記，而且本文的輪廓跟蹤技術(shù)是對文獻[8]的輪廓跟蹤技術(shù)的改進。該方法只需要掃描一遍圖像，不需要等價對表，耗時較少。主要的改進有以下幾個方面。

2.1 外輪廓搜索方法的改進

在處理外輪廓時，通過從左上鄰居P5開始按照順時針方向掃描它的鄰居，首先遇到的前景像素就是下一個輪廓點，如果遇到一個新的輪廓點，最上面的第一個輪廓點P5位置是沒有前景像素的[8]。一般在P0的位置是有前景像素的，因此本文提出對于外輪廓，第一次遇到的，從P0開始搜索，不應(yīng)該從P5開始。以后就按照下面的規(guī)則進行搜索。該規(guī)則是假設(shè)下一個輪廓點是當前輪廓點的Pj，則當前輪廓點是下一個輪廓點的鄰居 Pi=mod(Pj+4)，那么下次從Pi+2開始按照順時針的方向來掃描當前輪廓點的鄰居，第一個遇到的前景像素就是下一個輪廓點，標記該輪廓點，并按照上面的方法繼續(xù)搜索下一個輪廓點，直到當前點是起始點，而下一個點是原始第二個點，則輪廓標記程序結(jié)束。

2.2 內(nèi)輪廓搜索方法的改進

在處理內(nèi)輪廓時，如果遇到的第一個點是沒有標記的，通過尋找內(nèi)輪廓上的某個點的左鄰P4，該P4一定是已經(jīng)標記的像素點，然后用P4的標號標記本行內(nèi)輪廓。該方法由于要先判斷是否是內(nèi)輪廓點，然后尋找標記點，最后再標記，浪費不少時間[8]。本文在處理輪廓時用第一個遇到的輪廓點的P5位置的標號來標記當前像素。如果P5位置沒有前景像素，則其為外輪廓，必須按照外輪廓的標記方法進行標記。如其為內(nèi)輪廓最上面的第一個點，其P5位置一定是有前景像素的。如果P5位置有前景像素，則其為內(nèi)輪廓，必須按照內(nèi)輪廓的標記方法進行標記。如圖2，首先標記完外輪廓，再用游程標記后，W點上面的前景像素一定是已經(jīng)標記好的，同時W點左邊也是標記好的，當用本文方法游程掃描時，遇到W右邊的第一個點時，如果該點沒有標記，則檢查它的左上角P5位置是否有前景像素，如果有，則用P5位置的標號標記W右邊的第一點，然后以此為起始點，第一次是從P5位置開始搜尋，以后就按照下面的規(guī)則進行搜索。該規(guī)則是假設(shè)下一個輪廓點是當前輪廓點的Pj，則當前輪廓點是下一個輪廓點的鄰居Pi=mod(Pj+4)，那么下次從Pi+2開始按順時針方向掃描當前輪廓點的鄰居，第一個遇到的前景像素就是下一個輪廓點，標記該輪廓點，并按照上面的方法繼續(xù)搜索下一個輪廓點，直到當前點是起始點，而下一個點是原始第二個點，則輪廓標記程序結(jié)束。

圖2 內(nèi)輪廓的標記方法

2.3 游程的標記方法的改進

在進行游程標記時，通過用起始點的標號或者終止點的標號來標記，尤其是起始點沒有標記，而終止點有標記，則用終止點的標記來標記該游程[8]。由于要搜索到終止點才能確定是否有標記，該方法消耗了不少時間，用本文的方法，不需要搜索，直接用起始點的標記來標記游程。如果起始點沒有標記，則其必為輪廓，通過判斷P5位置有無前景像素，可以判斷其為外輪廓還是內(nèi)輪廓，然后按照外內(nèi)輪廓的方法進行標記。

2.4 標記的過程

用本文算法進行標記的流程圖見圖3。標記過程如下：

(1) 首先進行初始化，設(shè)置標號label為1，然后按照從上到下，從左到右的順序?qū)Χ祱D像進行掃描圖像。

(2) 當遇到一個前景像素點時，首先看是否已經(jīng)標記，如果已經(jīng)標記，則用游程法進行標記。如果沒有標記，則轉(zhuǎn)到(3)。

(3) 搜索該點周圍的8個點，判斷該點是否是孤立點，如果是孤立點則直接將該點設(shè)置為背景像素，起到了濾波的作用。如果該點不是孤立點，則認為該點是某輪廓的起始點，可能是外輪廓點，也可能是內(nèi)輪廓點。

(4) 根據(jù)P5位置是否有前景像素，如果沒有前景像素，則該點是外輪廓上的一點，進入(5)調(diào)用外輪廓標記程序。如果有前景像素，則該點是內(nèi)輪廓的一點，進入(6)調(diào)用內(nèi)輪廓標記程序。

圖3 用改進的算法進行標記的流程圖

(5) 調(diào)用外輪廓標記程序過程：首先用label標記該前景像素點，然后從P0開始，按照順時針方向進行掃描，將遇到的第一個前景像素點作為下一個輪廓點，并標記。假設(shè)下一個輪廓點是當前輪廓點的鄰居Pj，則當前輪廓點是下一個輪廓點的鄰居 Pi=mod(Pj+4)，那么下次從Pi +2開始按順時針方向掃描下一個當前輪廓點的鄰居，第一個遇到的前景像素就是下一個當前輪廓點，標記該輪廓點，并按照上面的方法搜索它的下一個輪廓點，直到當前點是起始點，而下一個點是原始第二個點，則輪廓標記程序結(jié)束。并更新標號，將標號label自動加1，即label= label+1。這種標記結(jié)果是按照順時針方向標記外輪廓。

(6) 調(diào)用內(nèi)輪廓標記程序過程：首先用P5位置前景像素的標記標記當前前景像素，然后從P5開始，按照順時針方向進行掃描，將遇到的第一個前景像素點作為下一個輪廓點，并標記。假設(shè)下一個輪廓點是當前輪廓點的鄰居Pj，則當前輪廓點是下一個輪廓點的鄰居 Pi=mod(Pj+4)，那么下次從Pi +2開始按順時針方向掃描下一個當前輪廓點的鄰居，第一個遇到的前景像素就是下一個當前輪廓點，標記該輪廓點，并按照上面的方法搜索它的下一個輪廓點，直到當前點是起始點，而下一個點是原始第二個點，則輪廓標記程序結(jié)束。并更新標號，將標號label自動加1，即label= label+1。這種標記結(jié)果是按照逆時針方向標記內(nèi)輪廓。

(7) 標記完輪廓以后，沿著當前行繼續(xù)向前掃描，如果遇到前景像素點，則回到(2)。如果掃描到最后一行，最后一列，則結(jié)束。

3 實驗與分析

在對水果商品品質(zhì)進行分級時，首先要提取水果的圖像，將水果從背景中分割出來，然后進行特征提取，最后進行分級。而要將水果分割出來，必須要進行連通區(qū)域的標記。本實驗是在MATLAB R2010b軟件環(huán)境下編程，PC機的配置為 Intel Core I5-5200U CPU@2.2GHz 2.2GHz雙核，內(nèi)存為4.0GB。在HIS顏色空間對含有蘋果的圖像運用色度閾值進行判斷，可得二值圖像，見圖4(a)。該圖中存在噪聲，必須去掉噪聲，只留下蘋果的圖像。采用本文的基于游程與輪廓跟蹤技術(shù)的連通區(qū)域標記改進算法可以得到各個連通區(qū)域的標記，取含有最大數(shù)目像素的標記，可以將蘋果從背景中分割出來。圖4(b)表示輪廓提取，當搜索到輪廓最上面第一個像素時，就按照輪廓搜索的方法將輪廓提取出來。圖4(c)表示游程標記過程，當從左向右搜索的時候，用游程的第一個像素的標記進行其他像素的標記。圖4(d)表示標記后的結(jié)果，從圖中可以看出不同的連通區(qū)域具有不同的標記。如果取最大數(shù)目像素的標記，就可以將蘋果從背景中分割出來。圖5與圖4類似，只是含有兩個蘋果，其中第一個蘋果已被損壞，含有內(nèi)輪廓時，演示如何來搜索外輪廓與內(nèi)輪廓并標記的。

(a)原始的二值圖像 (b)輪廓提取

(c)游程標記過程 (d) 標記后的圖像

圖4 本文方法對單個蘋果進行連通區(qū)域標記的過程

(a)原始的二值圖像 (b)輪廓提取

(c)游程標記過程 (d) 標記后的圖像

圖5 本文方法對兩個蘋果進行連通區(qū)域標記的過程

為了比較不同方法標記的效果，本文采用方法一：基于區(qū)域增長的標記算法、方法二：基于標號等價技術(shù)的標記算法，方法三：基于非對稱游程和輪廓跟蹤的連通區(qū)域標記算法，方法四：在方法三基礎(chǔ)上提出改進方法。用上述的四種方法對三幅圖像進行實驗，圖像一是含有1個蘋果的圖像；圖像二是含有2個蘋果的圖像，其中一個蘋果壞掉，搜索時有內(nèi)輪廓的提??；圖像三是含有1個梨子的圖像，對這三幅圖像分別用上述四種方法進行連通區(qū)域的標記。每種方法的執(zhí)行時間如下表所示。從表中可以看出，由于方法一要進行多次掃描圖像與等價表，所需時間最多。方法二采用區(qū)域增長的標記算法，要不斷訪問前景像素，如果前景像素在圖中所占的比例較大時，其所需要的時間較大。在實驗時占用內(nèi)存最大。方法三與前兩種方法相比，所需時間較少，方法四是在方法三的基礎(chǔ)上進行的改進，使得執(zhí)行時間進一步減少。

表1 四種不同算法的執(zhí)行時間 /s

由表1中最下面的兩行數(shù)據(jù)可以得到改進的方法比方法三提高的效率，效率的公式為:

(1)

上式可以得到表2，從表2中可知改進的方法的效率比方法三的效率平均提高了大約24.5%。

表2 效率提高表

4 結(jié)論

本文在仔細研究已有文獻的基礎(chǔ)上，提出一些改進方法。主要改進有三個方面。第一，是在處理內(nèi)輪廓時，提出用當前前景像素點的P5位置的標號來標記較好。第二，在處理外輪廓時，第一次從P0開始搜索，不應(yīng)該從P5開始。對于內(nèi)輪廓點則要從P5開始搜索。第三，每個游程的標記都用起始點進行標記，而不是用游程終點進行標記，也不需要搜索上一行的游程或者下一行的游程而浪費時間。實驗證明改進后算法的標記效率得到了提高。

[1] 蔡世界,于強.基于游程編碼的連通區(qū)域標記算法優(yōu)化及應(yīng)用[J].計算機應(yīng)用,2008(12):3150-3153．

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

[3] 牛連強,彭敏.利用游程集合的標號傳播實現(xiàn)快速連通域標記[J].計算機輔助設(shè)計與圖形學學報,2015(1):128-135.[4] 沈喬楠,安雪暉.基于游程遞歸的連通區(qū)域標記算法[J].計算機應(yīng)用,2010(6):616-618.

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

[6] 高紅波,王衛(wèi)星.一種二值圖像連通區(qū)域標記的新算法[J].計算機應(yīng)用,2007(11): 2776- 2777.

[7] REN M W, YANG J Y, SUN H. Tracing boundary contours in a binary image[J].Image and Vision Computing,2002(3):125-131.

[8] 張云哲,趙海,宋純賀,等.一種新的連通區(qū)域標記算法[J].計算機應(yīng)用研究,2010(11): 4335-4337.

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

(責任編輯：孫文彬)

Improved Algorithm of the Connected Component Labeling Based on the Run Length and Contour Tracking

YANG Ding-li1, SUN Shan-lin2, YAN Shi1,3, YIN Xiao-qi1, FU Cheng-fang1, WU Tian-chi1, ZHANG Yue-cheng1

(1. Faculty of Electronic Information Engineering, Huaiyin Institute of Technology; Huai'an Jiangsu 223003,China; 2.School of instrumentation Science and Opto-electronics Engineering, Beihang University, Beijing 100191,China; 3. College of Extended Education, Huaiyin Institute of Technology, Huai'an Jiangsu 223001, China)

In order to further improve the efficiency of the connected component labeling, an improved algorithm of the connected component labeling based on the run length and contour tracking technology is proposed. Firstly, the current foreground pixel is determined by whether it is the contour point or isolated point. Then, it is determined by whether it is the outer contour or inner contour. It is marked with the corresponding contour marking algorithm. Finally, the remaining foreground pixels on this row are marked with run length marking method. There is no need of equivalence table during the whole process and the elapsed time is less. Experiments show that the efficiency of the improved algorithm is increased by 24.5%.

connected component labeling; run length; contour tracking; outer contour; inner contour

2016-06-27

國家青年基金項目(61401173)；淮安市工業(yè)項目(HAG2013064)；淮陰工學院基金項目(HGB1202)

楊定禮(1973-)，男，江蘇淮安人，副教授，碩士，主要從事數(shù)字信號處理、圖像處理、模式識別和DSP的開發(fā)研究。

TP391.41

A

1009-7961(2016)05-0001-05