鏈碼跟蹤在矩形檢測中的應用?

袁鑄 張毅

（河南工業(yè)職業(yè)技術學院 南陽 473000）

1 引言

幾何圖形的識別是計算機視覺領域的重要任務之一，它主要應用于設計自動化、深海探測及國防建設等。就矩形檢測問題而言，國內外學者對矩形檢測研究做了不少工作并取得了不少實際應用，如低溫電子顯微鏡圖像中提取矩形狀的棵粒物，圖像和視頻中的車牌提取，建筑知識圖和布局設計知識圖求解，衛(wèi)星圖片建筑物提取，公路監(jiān)視系統(tǒng)車牌檢測。迄今為止，已提出了許多矩形檢測方法，可主要分為如下幾類：

1）基于Hough變換及其改進的算法：標準Hough變換最初使用于直線檢測，因其具有良好的抗噪性，現(xiàn)已廣泛運用于具有線性特征的物體檢測。矩形是具有優(yōu)良幾何性質的線性圖形，其每條邊均可用Hough變換檢測出。但因Hough變換檢測直線時，丟失了直線端點信息，為恢復直線的端點無疑要增加算法的計算復雜度，故一些學者對Hough變換進行改進以適用于矩形檢測。Zhu［1］等研究出檢測矩形的Hough變換用于在低溫電子顯微鏡圖像中檢測近似矩形的塵埃粒子的檢測，該方法通過采樣估計出近似矩形的塵埃粒子的長和寬后，先利用圖像邊緣局部信息和2-D累加器檢測出矩形的中心坐標，再用一個1-D累加器檢測出矩形的方向。該方法檢測速度快，但精度過低。Claudio等［2］提出了窗口化的Hough變換矩形檢測方法，該方法將矩形四條邊進行Hough變換后參數(shù)空間對應峰值點的性質確定侯選矩形中心坐標（x0，y0），然后對以該中心為圓心，包含該侯選矩形最小圓和不與該侯選矩形相交的最大圓組成的圓環(huán)區(qū)域進行Hough變換以確定侯選矩形的長a，寬b和方向角3個參數(shù)。該方法的優(yōu)點是抗噪聲能力強，圖像邊緣可以不連續(xù)；缺點是由于采用的是STH，故有較大的計算量。

2）基于直線組合的方法：因矩形是由互相垂直的兩組平行直線組成。一些學者提出可利用直線檢測的結果判斷圖象中是否存在矩形并確定其參數(shù)。Lagunovsky［3］等提出一種基于直線基元檢測的矩形檢測方法。該方法首先從圖像中檢測所有直線并且在已檢測的每條直線中找出線段；接著通過比較線段的長度和方向確定出四邊形并按矩形的定義確認出真矩形。Lin［4］等研究出基于直線檢測的矩形檢測算法，用于航空拍攝的建筑圖像檢測問題。其思路是在直線檢測時找出某一長度范圍的線段，對每一條線段，搜索出與之垂直的線段并檢測出對應的矩形。Tao［5～7］等使用分裂算法提取被檢測圖像中的邊緣線段。利用線段的基本信息（起點、終點坐標和斜率）找出并行線段組。將并行線組構成矩形基元后合并成矩形。這些方法的檢測效率一方面直接依賴于檢測直線的效率，另一方面在圖像中若矩形的個數(shù)很多時，還產生大量的無效線段組合，檢測效率將進一步降低。

作者研究的是復雜布局設計中圖形的檢測。如圖1（a）所示的衛(wèi)星艙布局求解問題［8～9］的二維問題，可歸結為在一個圓容器中布置若干圓形、矩形待布物的帶性能約束（如動力約束）復雜布局設計問題（如圖1（b）所示），而對圖像空間的多個矩形的檢測是該布局設計中待解決的問題之一。對于前兩類方法檢測矩形，顯然，第一類方法由于采用的是標準Hough變換的投票機制，故必須花費較多的檢測時間。第二類方法的檢測效率和檢測精度依賴于直線檢測算法和直線數(shù)目。因此，它們難以實現(xiàn)復雜布局圖形的多矩形檢測。

圖1 衛(wèi)星艙的布局圖及平面布局圖

對于邊緣連續(xù)的矩形檢測問題，如果能找出每一個候選矩形的鏈碼，就能快速找出該候選矩形的四個頂點，根據(jù)矩形的定義就能快速確認出該候選矩形是否是真矩形。根據(jù)這一思想，文獻［10］提出基于廣義Hough變換的快速多矩形檢測方法。但它只能檢測不相交的多個矩形，對于相交或被遮擋的情形仍然有待研究。為解決該問題，本文提出了一種可較好地應用于相交矩形的檢測算法。實驗結果表明，該算法有檢測精度高、速度快的優(yōu)點，能較好地應用于復雜布局設計中矩形檢測。

2 相關定義及理論

本文中所處理的圖像均為二值化圖像，如果圖像中不為二值圖可通過閾值變換將其轉換為二值圖像。關于圖像點、非圖像點、孤立噪聲點、半連續(xù)噪聲點的定義請參考文獻［11］。

設矩陣A=［aij］H×W表示圖像空間的0，1數(shù)字化信息（圖像點值為1，非圖像點值為0）。其中W為圖像空間的寬度，H為高度，i為圖像中象素的y坐標值，j為x坐標值。

定義1 設在直角坐標系中，矩形的左下角頂點坐標為（x1，y1），右下角頂點坐標為（x2，y2），右上角頂點坐標為（x3，y3），左上角頂點坐標為（x4，y4），則該矩形記為R（x1，y1，x2，y2，x3，y3，x4，y4）。

兩平行矩形相交有以下幾種可能：1）一矩形分裂成兩新的小矩形。如圖2（a）所示，矩形R1、R2相交后演變?yōu)槿匦?R1、R21、R22。2）產生一新的矩形。如圖2（b）所示，矩形R1、R2相交后演變?yōu)槿匦?R1、R2、R12。3）其中一矩形的一邊被遮擋而無法求解該矩形。如圖2（c）所示，矩形R1、R2相交后演變?yōu)榫匦蜶1。為避免前兩種情形發(fā)生，且能較好地符合視覺習慣，本文規(guī)定所求解矩形需符合規(guī)則1：

圖2 兩平行的矩形相交

規(guī)則1 數(shù)字圖像中直線段最多只能屬于一個矩形，且優(yōu)先屬于大矩形。

定理1 在數(shù)字圖像中，設其最短連續(xù)曲線長為l，則圖像點P是連續(xù)曲線上的點的必要條件是以P為中心、邊長為2r+1的正方形區(qū)域中圖像點個數(shù)不小于 r+1（r+1＜l）。

證明：反證法。假設P是連續(xù)曲線上一點，以P為中心的邊長為2r+1的正方形區(qū)域中圖像點個數(shù)NP＜r+1。由最短連續(xù)曲線長為l可知，若P是連續(xù)曲線上一點，則在以P為中心、邊長為2l+1的正方形區(qū)域中至少存在一圖像點個數(shù)不小于l的連通圖像點區(qū)域；由連續(xù)曲線的生成算法可知，在以P為中心、邊長為2r+1的正方形區(qū)域中至少存在r+1個圖像點（r+1＜l）。故NP ≥ l＞r成立，這與假設中NP＜r+1矛盾，因此假設不成立，定理得證。

證畢

定義2 數(shù)字圖像中孤立和半連續(xù)噪聲點及不滿足定理1的圖像點稱為第一類非曲線噪聲點；除第一類非曲線噪聲點外的不在曲線上的圖像點稱為第二類非曲線噪聲點。

由定理1知，不滿足定理1的圖像點必不在連續(xù)曲線上。故在檢測前，可剔除第一類非曲線噪聲點來提高圖像質量以利于檢測。圖3（b）為剔除圖像中第一類非曲線噪聲點后的效果圖（其中l(wèi)=5），可以看到經此處理后絕大部分噪聲點被剔除。

圖3 預處理效果圖

3 算法思想

3.1 數(shù)據(jù)結構

3.2 不相交封閉圖形的鏈碼跟蹤思想

設當前點為P（x，y），將其8個鄰接點按圖4所示進行編碼，可通過如下步驟實現(xiàn)對不相交封閉圖形的鏈碼跟蹤：

1）從左到右、從下到上地搜索。將第一個圖像點作為圖形的起點Ps，并將其記為當前點PCur，搜索下一個圖像點。

2）搜索當前點PCur的八鄰域中未跟蹤過的圖像點數(shù)NP，將當前點PCur信息（followLink-＞node?Num，followLink-＞x，followLink-＞y，followLink-＞neighborsNum）插入到跟蹤鏈表中，并將當前點PCur標記為已跟蹤，再根據(jù)NP來選擇下一跟蹤點：若NP=1，直接將該圖像點作為下一跟蹤點PNext；若NP＞1，從圖4所示的鏈碼方向中優(yōu)先選擇鏈碼方向值小的圖像點作為下一跟蹤點PNext；若NP=0，則回退到跟蹤鏈表中的前一NP＞1的結點處（即followLink-＞NeighborsNum＞1）。并將PCur其設置為PNext。

圖4 鏈碼方向

3）重復第二步直至|PsPCur|＜wd（wd為不封閉的閾值），若跟蹤鏈表中結點個數(shù)（即followLink-＞nodeNum）大于最小圖形周長閾值Lw，則跟蹤結果為封閉圖形；否則，跟蹤結果不為封閉圖形，清空跟蹤鏈表來跟蹤下一個封閉圖形。

3.3 相交矩形的輪廓跟蹤

3.2節(jié)所述的輪廓跟蹤方法可適用于不相交圖形的跟蹤，但難以適用于相交圖形（如圖5（b）所示）。根據(jù)矩形的幾何性質，本文將輪廓跟蹤法加以了改進以適用于矩形跟蹤：

圖5 輪廓跟蹤效果對比

1）在跟蹤過程中將跟蹤點存入到局部跟蹤點集合SegmentSet中，并計算這段擬和直線段的角度。根據(jù)擬和直線的角度差可排除直線和相交矩形的干擾。

在跟蹤過程中將當前點存到集合SegmentSet中，若集合SegmentSet不滿足式（1），則繼續(xù)下一圖像點的跟蹤；否則，對其用最小二乘法作擬和直線l：ay+bx+c=0，其中直線參數(shù)可由式（2）求出。

求得擬和直線參數(shù)后，可由式（3）求得該擬和直線的傾斜角度θk。

再利用SegmentSet中起點（x1，y1）和終點（xN，yN）信息，由式（4）求得該擬和直線段的角度θt，將θt及SegmentSet中點的坐標存入擬和直線段鏈表angleLink，再將集合SegmentSet清空。

其中：情形1：θk＞0&&xN ≥ x1&&yN ≥ y1；情形2：θk＞0&&xN ≤ x1&&yN ≤ y1；情形 3：θk＜0&&xN ≤x1&&yN ≥ y1；情形 4：θk＜0&&xN ≥ x1&&yN ≤ y1；情形5：θk=0，xN＞x1；情形6：θk=0，xN＜x1。

在求得當前擬和直線段的角度θtn后，根據(jù)式（5）計算該擬和直線段的角度與前n-1段擬和直線段（θt1，θt1…）的夾角和 sumθtn和夾角平均值aveθtn。

設定閾值 Tw ，若 aveθtn＜Tw ，置angleLink-＞flag為0。若 aveθtn≥Tw ，置angleLink-＞flag為1；若aveθtn連續(xù)兩次大于Tw，將擬和直線段鏈表an?gleLinks上對應于這兩段擬和直線段的結點的flag置為2，并回退至跟蹤鏈表followLink中上一neigh?borsNum＞1的結點處。如此，可排除大部分直線段和相交矩形（傾斜角相差較大）的干擾。

2）在多岔口處優(yōu)先跟蹤擬和直線段方向以加快檢測速度。

若當前點存在多個后繼點時，需從中選擇一點來作為下一跟蹤點。本文利用當前點的前一擬和直線段的角度θ來確定主方向和次方向，并優(yōu)先考慮主方向和次方向。在主方向和次方向上都不存在圖像點時，按圖4所示的鏈碼方向從小到大來選擇圖像點作為下一跟蹤點。其中，主方向為方向序號為偶數(shù)（0，2，4，6）且與 θ 最為靠近的方向，次方向為方向序號為奇數(shù)（1，3，5，7）且與θ最為靠近的方向。

3）如果當前點八鄰域中沒有未跟蹤的圖像點，則在以該點為中心，長為2Lw+1的正方形區(qū)域D中搜索未跟蹤的圖像點作為下一跟蹤點。如果D中仍無未跟蹤的圖像點，則回退到跟蹤鏈表中上一neighborsNum＞1的結點處。

3.4 矩形頂點計算及真矩形確認

通過以上算法可跟蹤得到圖像中近似于矩形的圖形（如圖5（c）），稱其為候選矩形。

將擬和直線段li按式（6）分為四類：

分類后，第k類擬和直線段在候選矩形的第k邊。將第k類擬和直線段上所有點用最小二乘法求解所得的擬和直線方程，即為矩形第k邊的直線方程lrk：aky+bkx+ck=0。將矩形兩鄰邊的直線方程聯(lián)立得式（7）：

其中，n=（m+1）%4（m=0，1，2，3）。

由式（8）可求解得候選矩形兩鄰邊的交點，即候選矩形的頂點（xm，ym）：

計算得候選矩形頂點P0（x0，y0），P1（x1，y1），P2（x2，y2），P3（x3，y3）后，若落在候選矩形R（x0，y0，x1，y1，x2，y2，x3，y3）各邊上的點數(shù) Mic（i=0，1，2，3）均大于該邊長度的w倍（w為比例系數(shù)，w＜1&&w＞0），則為真矩形；否則，為虛假矩形。

4 數(shù)值實驗與討論

以下實驗是在4GB內存的雙核i3 3.4 GHz計算機上用VC++6.0編程實現(xiàn)的。在待檢測圖中，坐標原點規(guī)定為矩形左下角，坐標軸分別平行于矩形的兩相鄰邊。在本文中，將文獻［5］中算法稱為Tao算法。

實驗1 圖形檢測實例

為驗證、對比算法的檢測性能，做了如下兩組實驗：1）只含噪聲點干擾；2）含噪聲點和線條干擾。

圖6（a）為含7個矩形、6個橢圓、4個多邊形的331×234的圖像空間。在第一組實驗中，我們對圖6（a）增加不同程度的噪聲點，噪聲點個數(shù)為圖像空間像素點個數(shù)的1%～10%（如圖6（b）所示）。在第二組實驗中，我們對圖6（a）增加干擾線條和噪聲點，干擾線條條數(shù)為0～60，噪聲點個數(shù)為圖像空間像素點個數(shù)的0%～3%（如圖6（c）所示）。

圖6 多種圖形中矩形檢測實例

本文算法對6（a），6（b），6（c）檢測結果基本相同且與精確值相差不超過兩個像素（如表1所示），如圖6（d）所示為對6（a），6（b），6（c）的檢測效果最差的圖。

表1 本文算法對圖6（b）的檢測結果

表2為第一組實驗中，Tao算法和本文算法的檢測性能對比。其中，對圖6（b），Tao算法的平均檢測時間為0.09s，本文算法的平均檢測時間為1.36s。

表3為第二組實驗中，Tao算法和本文算法的檢測性能對比。其中，對圖6（c），Tao算法的平均檢測時間為0.11s，本文算法的平均檢測時間為1.33s。

表2 實驗1中第一組實驗的算法檢測性能對比表

表3 實驗1中第二組實驗的算法檢測性能對比表

雖然Tao算法的檢測速度要比本文算法快，但該算法的檢測精度要低于本文算法，且誤檢率和漏檢率均要高于本文算法。其原因如下：1）隨噪聲點及干擾線條增加，Tao算法所采用的直線檢測算法檢測所得的直線段多為短直線，這使得在短直線合并過程中出錯率增大，而造成無法檢測出矩形。2）Tao算法將直線按傾斜角度分類并將其角度調整為同一角度，大大地降低了檢測精度。

另外，作者采用文獻［2］、文獻［10］中算法進行本實驗的檢測，實驗結果表明：在本實驗中，這兩種算法性能不佳。

實驗2 圖像檢測實例

圖7（a）為某衛(wèi)星艙的布局掃描圖，其大小為280×280，共含五個矩形和六個圓。對該圖提取輪廓后如圖7（b），再用本文算法來檢測矩形，檢測結果如圖7（c）所示，檢測時間為1.9s。因為該圖像較為簡單，采用Tao算法和文獻［10］中算法均能檢測到兩個矩形，雖然這兩種算法的檢測速度要略快于本文算法，但兩者的檢測精度均要比本文算法低。

圖7 圖像檢測實例

5 結語

針對矩形檢測問題，本文提出了一種基于鏈碼跟蹤的矩形檢測算法，該算法能較好地適應圖像空間較復雜的情形（如矩形相交、雜亂線條較多、其他圖形干擾較為嚴重等）。數(shù)值實驗結果表明：本文算法具有較快的檢測速度，可滿足實時要求；并具有很高的檢測精度，可滿足精度要求。

［1］Zhu Y，Carragher B，Mouche F，Potter C.Automatic par?ticle detection through efficient Hough transforms［J］.IEEE Transactions on Medical Imaging，2003，22（9）：1053-1062.

［2］Clàudio Rosito Jung，Rodrigo Schramm.Rectangle Detec?tion based on a Windowed Hough Transform［J］.Proceed?ing of the XVII Brazilian Symposium on Computer Graph?ics and image Processing（SIBGRAPI'04）.

［3］Lagunovsky D，Ablameyko S.Straight-line-based primi?tive extraction in grey-scale object recognition［J］.Pat?tern Recognition Letters，1999，20（10）：1005-1014.

［4］Lin C，Nevatia R.Building detection and description from a single intensity image.Computer Vision and Image Understanding，1998，72（2）：101-121.

［5］Tao Wen-bing，Tian Jin-wen，Liu Jian.A new approach to extract rectangle building form aerial urban images［C］//In International Conference on Signal Processing，pages 143-146，2002.

［6］王佳，李波，徐其志.邊緣檢測中局部區(qū)域的動態(tài)閾值選取方法［J］.計算機應用研究，2010，27（2）：772-774.WANG Jia，LI Bo，XU Qizhi.Dynamic threshod selection based on local region in edge detection［J］.Application Research of Computers，2010，27（2）：772-774.

［7］覃勛輝，馬戎，付維平，等.一種基于梯度的直線段檢測算法［J］.光子學報，2012，41（2）：205-209.QIN Xunhui，MA Rong，F(xiàn)U Weiping，et al.A Line Seg?ment Detection Algorithm Based on Grad［J］.Acta Photon?ica Sinica，2012，41（2）：205-209.

［8］Grompone von Gioi R，Jakubowicz J，Morel JM，Randall G.，LSD：A Fast Line Segment Detector with a False Detec?tion Controll［C］//IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（4）：722-732.

［9］劉景發(fā)，黃娟，蔣宇聰，等.基于Wang-Landau抽樣的帶靜不平衡約束的簡化衛(wèi)星艙布局方法［J］.計算機科學.2016，12：287-292.LIU Jingfa，HUANG Juan，JIANG Yucong，et al.Packing Method Based on Wang-Landau Samplified Satellite Mod?ule With Static Non-equilibrium Constraints［J］.Comput?er Science，2016，12：287-292.

［10］ Zi-qiang Li.Generalized Hough Transform Fast Detec?tion for Hybrid Multi-Circle and Multi-Rectangle［C］//Proceedings of the 6thWorld Congress on control and Au?tomation， June 21-23， 2006， Dalian， China.10130-10134.

［11］王新，張元東，王莉.一種隨機Hough變換檢測圓的優(yōu)化方法［J］.測控技術，2016，06：112-116.WANG Xin，ZHANG Yuandong，WANG Li.Optimiza?tion Method of Randomized Hough Transform to Detect Circle［J］.Measurement&Control Technology，2016，06：112-116.