一種常用兩次掃描算法的改進*

張春明，解永春，王 立

(1.北京控制工程研究所，北京100190;2.空間智能控制技術重點實驗室，北京100190)

0 引言

在目標識別之前，需要對相互隔離的連通域進行標記.二值的連通域標記(CCL，connected-component labeling)是模式分析、計算機視覺和機器智能中最基本的操作之一［1］.連通域標記將二值圖像轉化到特征空間，為每個對象(圖像區(qū)域)分配唯一的標簽.連通域標記一般比降噪處理、閾值化、邊緣檢測等耗時要多(文獻［2］處理512×512圖像的連通域標記算法的運行平均時間為78 ms)，要實現(xiàn)快速目標識別，快速的連通域標記是其前提.對于刷新頻率為5 Hz的光學成像敏感器而言，其測量算法留給光學成像敏感器圖像處理的時間小于140 ms，因而對連通域標記算法的性能有很高的要求.近年來，標記算法的改進以及與硬件的結合是主流發(fā)展方向.文獻［3］認為，兩次掃描算法更容易與嵌入式的硬件相結合.

本文針對交會對接最后逼近段光學成像敏感器圖像處理中的快速連通域標記問題，基于標記融合和兩次掃描相結合的思想改進了連通域標記中常用的兩次掃描算法，并基于標志燈成像的幾何約束和統(tǒng)計約束給出了可完成目標粗識別的連通域標記算法.最后給出了仿真結果.

1 快速連通域標記

1.1 常用兩次掃描算法

記b(x，y)(1≤x，y≤N)為二值圖像，其像素值0，1分別表示背景和目標.記存儲標記的矩陣為L，則其維數(shù)等于圖像的尺寸.通常使用的連通域模板如圖1所示.

圖1中，當前像素為e=b(x，y)，4個相鄰像素為Ms=(a，b，c，d).第一次掃描主要為目標像素分配臨時標記［4］，可表達如下(i∈Ms):

式中，當前像素的標記為L［e］，設遞增的標記l初值為1.第二次掃描中，目標像素的標記修改為其鄰域的最小標記，可表述為［4］

式(1)～(2)同時適合于前向和后向掃描.

圖2顯示了包含標記融合的兩次掃描算法的示意圖.通常，在標記融合中通過整理等價關系表以確定各像素的最終標記.然后，通過第二次掃描提取出帶有標記的連通域.無論是前向掃描還是后向掃描，每次操作可只調入兩行圖像數(shù)據(jù).

圖2 連通域標記中標記融合的示意圖Fig.2 Sketch of label merging in CCL

兩次掃描也可以按照固定設計的代碼執(zhí)行.文獻［5］基于ASIC硬件構架，將連通域的個數(shù)固定為512個，因而可對ASIC接口的數(shù)據(jù)區(qū)地址包括行坐標、列坐標、面積、交互參數(shù)等的地址進行固定分配，這些為快速尋址準備了前提條件.圖3給出了一種標記單元的硬件構架示意圖［3］.

圖3 標記單元的硬件構架Fig.3 Architecture of the labeling units

在圖3中，總線用于數(shù)據(jù)和訪問控制，輸入和輸出緩存用于數(shù)據(jù)快速轉移，控制參數(shù)寫入寄存器文件，行內(nèi)存意味著每次只調入兩行圖像數(shù)據(jù).圖3的一個重要特點是在等價單元中引入了與之大小相等的等價RAM(查找表).查找表在第一次掃描時建立，在第二次掃描時直接使用查找表而避免調整等價關系對，主要原因是每個像素調整等價關系一般需要消耗多個時鐘周期［3］.

下面的兩次掃描算法的改進思路與之類似，均設法避免調整等價關系對.

1.2 兩次掃描算法的改進

在標記融合的過程中，并不確定每個連通域有多少像素，因而鏈表結構中將出現(xiàn)大量非規(guī)則內(nèi)存.常規(guī)的兩次掃描算法需要頻繁訪問及修改鏈表結構以調整等價關系表，因而訪問這些內(nèi)存的時間代價高昂.對于1 024×1 024的圖像，兩次掃描的時間代價同樣高昂.

正因如此，這里通過引入特殊的鏈表結構(包含像素索引數(shù)組、當前存儲位置、鏈表指針以及記錄數(shù)組的函數(shù))，將第二次掃描與標記融合部分結合在一起，可避免建立和整理等價關系表.兩次掃描算法的改進主要體現(xiàn)在以下兩方面:

1)利用式(2)得到某個像素的最終標記，再插入該像素對應連通域的鏈表(僅存在后向插入，并不需要調整鏈表)，可避免建立等價關系對和頻繁調整鏈表結構.

2)對整幅圖像進行標記融合后，各個連通域的鏈表已建立完畢，此時連通域的數(shù)據(jù)是逐行存儲的.將鏈表中的信息提取時，定義了一種區(qū)域信息結構體(包含x，y像素坐標及像素值、外接矩形頂點索引、像素數(shù)目、灰度平均值以及質心位置、峰值位置等)，可方便求出連通域外接矩形的長寬比和一些統(tǒng)計信息，用于目標粗識別，實現(xiàn)了標記融合和兩次掃描的融合.

新的標記融合算法如圖4所示.

圖4 一種新的標記融合算法Fig.4 A new label merging algorithm

圖4中，在第一次掃描后，標記融合算法可總結如下:

1)初始化:設置連通域統(tǒng)計數(shù)目和標記數(shù)組，分配鏈表指針內(nèi)存，為每個待選的連通域建立各自的當前存儲指針.

2)在標記融合時(應用式(2)后)更新臨時標記和規(guī)則內(nèi)存的指針及當前元素存儲位置，可避免記錄等價關系表.

3)在標記融合后，首先應用下一節(jié)的面積約束信息消除小面積區(qū)域，然后從鏈表中直接填充區(qū)域信息結構體，在此過程中可直接求出連通域外接矩形的長寬比和一些統(tǒng)計數(shù)據(jù).

在上面的標記融合算法的基礎上，參考文獻［3］和［5］，可設計一種新的標記單元硬件構架，如圖5所示.

與圖3相比，圖5的最大特點是避免了等價單元而用區(qū)域RAM代替，引入了流程控制代碼可實現(xiàn)代碼復用，設置寄存器變量及指針為標記融合提供便利.圖5決定了整個連通域標記算法的實現(xiàn)性能.

圖5 標記單元的硬件構架Fig.5 Architecture of the labeling units

2 標記融合中嵌入目標粗識別

上面給出了兩次掃描算法的改進算法.在此基礎上，在提取鏈表信息的過程中，可直接利用統(tǒng)計約束先排除小面積和能量集中度不高的連通域(偽特征點)，并圍繞目標標志燈成像的幾何約束計算候選的特征點組，從而完成目標粗識別.

2.1 幾何約束

理論上，利用不在同一平面內(nèi)的4個特征點［6］即可唯一解算出相對導航信息，利用冗余的1個或2個特征點提高導航算法的穩(wěn)定性和準確性.假定有5個特征光點(光點布局見文獻［6］)，以P1，P2，P4，P54點為例，而將P3視為出現(xiàn)故障而丟失的特征點，得到點Pi的幾何約束條件

這里，Δθ，δP，Δγ為預定義的常數(shù)，lP為外圍Pi(i=1，2，3，4)點所圍成矩形的邊長，在兩航天器逐漸逼近時，可以利用卡爾曼濾波計算的預估值代替，

式(3)為標志燈成像的幾何約束，并以此為硬約束條件首先識別外圍的3個特征點，而在識別之前先利用統(tǒng)計約束對待選的目標區(qū)域進行篩選.

2.2 統(tǒng)計約束

對于標志燈而言，標志燈輻射出的亮度有一個發(fā)散角(一般小于8°)，對應的標志燈成像的最亮的位置在幾何中心位置附近.因而，同一批次標志燈輻射能量的集中程度存在一個設計容差，對應的成像表現(xiàn)出一種能量聚合特性.該能量聚合特性與圖像區(qū)域I(x，y)∈Rc存在的3類中心位置即幾何中心Vo(xo，yo)、峰值中心Vp(xp，yp)和質心Vg(xg，yg)有關，三類中心位置分別為

假定標志燈成像的能量集中程度有一容差設計，則Vp，Vo，Vg3點必須限制在一個有效區(qū)域，描述該限制條件的因子tr可定義為

式中，SΔVpVoVg表示ΔVpVoVg的外接圓面積，S是區(qū)域Rc的面積，εr為常數(shù).

類似地，同一批次的標志燈有一致的能量和面積，則圖像區(qū)域的平均能量與面積的比值可定義為另一種不變量，即

式中，Nr為圖像區(qū)域Rc的像素數(shù)，Nr=S，Pea代表圖像區(qū)域的平均功率.顯然，Pea可作為共面或非共面特征點的一致判斷條件，用于快速目標識別.由于在標記融合算法中，會順便計算一些統(tǒng)計量，因而tr，Pea直接可求.

式(5)利用了面積信息.當近距離兩航天器最后逼近時，完整的標志燈成像有一個時域限制條件，即S(t+1)＞S(t).在實際應用時，可取上一次各標志燈面積的平均值作為約束條件，即

作為連通域標記融合子程序中剔除小面積連通域(偽特征點)的一個判斷條件.

2.3 目標粗識別

在填充區(qū)域信息結構體后，利用式(4)～(6)設計排序規(guī)則(根據(jù)實際測試結果而定)，剔除偽特征點以進行目標區(qū)域的篩選，然后應用式(3)可實現(xiàn)目標粗識別.

根據(jù)實際測試，目標粗識別可按如下方式進行:

1)利用式(6)剔除小面積連通域.

2)排除tr＞0.3的連通域，然后求剩下的連通域的均值，再排除掉大于均值的連通域.

3)比較在0.3＜Pea＜0.5(具體范圍視測試結果而定)范圍內(nèi)的連通域，作為連通域相互確認的條件.

4)對各連通域的中心點位置進行排序，找出外圍的3個或4個特征點.對于4個特征點，執(zhí)行4次循環(huán)，判斷是否滿足式(3).

前面3步得到了待選的連通域，第(4)步利用迭代方式獲得候選的包含外圍3點的特征點組，從而可實現(xiàn)目標粗識別.如果最后求得的特征點組多于一組，則需要對后續(xù)的目標識別進行篩選，直至剩下一個特征點組為止.

3 仿真分析

在實際仿真中，選擇的測試平臺為Inter(R)Core(TM)2CPU@2.40 GHz和 2G Memory的計算機，編程語言為Visual C++2005，測試的圖像大小為1 024×1 024，耗時數(shù)據(jù)均為50次重復計算的平均耗時.

圖6顯示連通域標記后剔除小面積區(qū)域的結果.其中，未標記十字的圖像區(qū)域的小面積區(qū)域被剔除.

圖6 連通域標記后剔除小面積區(qū)域的結果Fig.6 The results of CCL with small areas eliminated

表1顯示了連通域標記的耗時對比.表1顯示，改進后的連通域標記算法處理一幅1 024×1 024的圖像其50次重復運行的平均耗時小于98 ms，與已有方法相比，連通域標記耗時縮減至原有的32%.

表2顯示了目標粗識別的統(tǒng)計結果.表2中，Pea可區(qū)分完整的目標區(qū)域，對應數(shù)值區(qū)間0.38～0.40，而不完整的目標區(qū)域對應數(shù)值0.79.tr對目標和非目標的區(qū)分程度不明顯，但可以通過排序算法預選.在此基礎上，結合標志燈成像的幾何約束，可以實現(xiàn)目標粗識別.

表1 連通域標記耗時對比Tab.1 Comparison of time cost for CCL

表2 目標粗識別統(tǒng)計Tab.2 Statistics of coarse target recognition

4 結論

針對交會對接最后逼近段光學成像敏感器圖像處理中的快速連通域標記問題，將標記融合和兩次掃描相結合，改進了連通域標記中常用的兩次掃描算法.結合自行設計的標志燈成像的幾何約束和統(tǒng)計約束，改進后的連通域標記算法可實現(xiàn)快速目標粗識別.仿真結果顯示，改進后的連通域標記算法處理一幅1 024×1 024的圖像其50次重復運行的平均耗時小于98ms，與已有方法相比，連通域標記耗時縮減至原有的32%，從而改進后的連通域標記算法具備實時應用的能力.

［1］HE L F，CHAO Y Y，SUZUKI K，et al.Fast connected-component labeling［J］.Elsevier on Pattern Recognition，2009，42(9):1977-1987.

［2］SUZUKI K，HORIBA I，SUGIE N.Fast connectedcomponent labeling based on sequential local operations in the course of forward raster scan followed by backward raster scan［C］//2000 IEEE on Proceedings of Pattern Recognition.New York:IEEE，2000:434-437.

［3］FLATT H，BLUME S，HESSELBARTH S，et al.A parallel hardware architecture for connected component labeling based on fast labeling merging［C］//IEEE on Application-Specific Systems，Architectures and Processors.New York:IEEE，2008:144-149.

［4］WU K S，EKOW O，SUZUKI K.Optimizing two-pass connected-component labeling algorithms［J］.Pattern A-nalysis ＆ Applications，2009，12(2):117-135.

［5］趙慧.改進的多值圖像連通域標記ASIC設計［D］.武漢:華中科技大學，2007.ZHAO H.Revision of connected-component labeling for multi-level image［D］.Wuhan:Huazhong University of Science and Technology，2007.

［6］張昊，解永春，吳宏鑫.交會對接光學成像敏感器光點布局求解有效性研究［J］.航天控制，2008，26(3):44-48.ZHANG H，XIE Y C，WU H X.Research on the target pattern solution validity of optical imaging sensor used in RVD［J］.Aerospace Control，2008，26(3):44-48.

［7］謝宜壯，譚許彬，陳禾.一種新的連通域標記算法［J］.北京理工大學學報，2012，32(12):1273-1278.XIE Y Z，TAN X B，CHEN H.A new algorithm for connected-component labeling［J］.Transactions of Beijing Institute of Technology，2012，32(12):1273-1278.