張春明，解永春，王 立

(1.北京控制工程研究所，北京100190;2.空間智能控制技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京100190)

0 引言

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

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

1 快速連通域標(biāo)記

1.1 常用兩次掃描算法

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

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

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

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

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

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

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

圖3 標(biāo)記單元的硬件構(gòu)架Fig.3 Architecture of the labeling units

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

下面的兩次掃描算法的改進(jìn)思路與之類似，均設(shè)法避免調(diào)整等價關(guān)系對.

1.2 兩次掃描算法的改進(jìn)

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

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

1)利用式(2)得到某個像素的最終標(biāo)記，再插入該像素對應(yīng)連通域的鏈表(僅存在后向插入，并不需要調(diào)整鏈表)，可避免建立等價關(guān)系對和頻繁調(diào)整鏈表結(jié)構(gòu).

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

新的標(biāo)記融合算法如圖4所示.

圖4 一種新的標(biāo)記融合算法Fig.4 A new label merging algorithm

圖4中，在第一次掃描后，標(biāo)記融合算法可總結(jié)如下:

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

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

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

在上面的標(biāo)記融合算法的基礎(chǔ)上，參考文獻(xiàn)［3］和［5］，可設(shè)計一種新的標(biāo)記單元硬件構(gòu)架，如圖5所示.

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

圖5 標(biāo)記單元的硬件構(gòu)架Fig.5 Architecture of the labeling units

2 標(biāo)記融合中嵌入目標(biāo)粗識別

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

2.1 幾何約束

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

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

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

2.2 統(tǒng)計約束

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

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

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

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

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

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

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

2.3 目標(biāo)粗識別

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

根據(jù)實(shí)際測試，目標(biāo)粗識別可按如下方式進(jìn)行:

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

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

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

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

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

3 仿真分析

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

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

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

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

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

表1 連通域標(biāo)記耗時對比Tab.1 Comparison of time cost for CCL

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

4 結(jié)論

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

［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］趙慧.改進(jìn)的多值圖像連通域標(biāo)記ASIC設(shè)計［D］.武漢:華中科技大學(xué)，2007.ZHAO H.Revision of connected-component labeling for multi-level image［D］.Wuhan:Huazhong University of Science and Technology，2007.

［6］張昊，解永春，吳宏鑫.交會對接光學(xué)成像敏感器光點(diǎn)布局求解有效性研究［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］謝宜壯，譚許彬，陳禾.一種新的連通域標(biāo)記算法［J］.北京理工大學(xué)學(xué)報，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.