?

一種基于交叉熵的黑白棋盤角點(diǎn)檢測算法

趙斌1，2，J．Guo2，E．K．A．Gill2，周軍1

(1．西北工業(yè)大學(xué)精確制導(dǎo)與控制研究所，陜西西安710072 2．Faculty of Aerospace Engineering，Delft University of Technology，Kluyverweg 1，2629 HS Delft，The Netherlands)

摘要:分析了現(xiàn)有黑白棋盤角點(diǎn)檢測算法存在的不足，將交叉熵思想引入角點(diǎn)檢測中。該算法首先將角點(diǎn)周圍像素劃分為4個(gè)象限，通過相鄰象限間的像素灰度差實(shí)現(xiàn)角點(diǎn)初選;其次，給出對(duì)角象限灰度交叉熵定義，根據(jù)局部交叉熵最小原理實(shí)現(xiàn)角點(diǎn)篩選;第3，針對(duì)備選角點(diǎn)局部重疊的問題，采用梯度幅值非極大值抑制方法實(shí)現(xiàn)像素級(jí)角點(diǎn)定位;最后采用Frostner算子實(shí)現(xiàn)角點(diǎn)的亞像素坐標(biāo)解算。實(shí)驗(yàn)結(jié)果顯示該算法檢測結(jié)果優(yōu)于經(jīng)典Harris算子以及SV算子，獲取的角點(diǎn)亞像素坐標(biāo)精度與Matlab相機(jī)標(biāo)定工具箱相當(dāng)，同時(shí)易于實(shí)現(xiàn)在線標(biāo)定。

關(guān)鍵詞:相機(jī)標(biāo)定;棋盤角點(diǎn)檢測;交叉熵;非極大值抑制;梯度幅值

在室內(nèi)衛(wèi)星編隊(duì)飛行平臺(tái)［1-2］中，視覺系統(tǒng)的標(biāo)定精度是確保漂浮體定位精度的關(guān)鍵，其通常包括圖像特征點(diǎn)檢測和相機(jī)參數(shù)求解2個(gè)過程。關(guān)于相機(jī)參數(shù)求解，張正友算法［3］已經(jīng)比較成熟，而圖像特征點(diǎn)檢測則成為研究熱點(diǎn)。

第1類方法多采用黑白棋盤標(biāo)定模板，對(duì)此實(shí)現(xiàn)角點(diǎn)檢測最早的方法是Harris算法［4］，采用局部灰度值的高斯梯度實(shí)現(xiàn)角點(diǎn)檢測，當(dāng)角點(diǎn)周圍存在圖像模糊時(shí)會(huì)得到多個(gè)虛假角點(diǎn)，影響標(biāo)定精度。文獻(xiàn)［5］采用2次Hough變換實(shí)現(xiàn)黑白柵格直線擬合，并根據(jù)直線交點(diǎn)獲取角點(diǎn)精確坐標(biāo)。文獻(xiàn)［6］采用旋轉(zhuǎn)直角模板進(jìn)行角點(diǎn)篩選，然后采用多次曲線擬合實(shí)現(xiàn)角點(diǎn)確定。這2種方法計(jì)算量大，難以實(shí)現(xiàn)在線標(biāo)定。文獻(xiàn)［7］提出對(duì)稱方差檢測算法(SV算子)，該方法僅采用角點(diǎn)附近2個(gè)象限的像素信息，實(shí)際使用中會(huì)產(chǎn)生錯(cuò)誤角點(diǎn)。文獻(xiàn)［8］提出一種改進(jìn)的SV檢測算子，采用平面到平面的變換實(shí)現(xiàn)角點(diǎn)初定位，基于區(qū)域能量中心概念實(shí)現(xiàn)精確定位。其仿真結(jié)果表明，該算法會(huì)造成部分角點(diǎn)丟失。文獻(xiàn)［9］通過Radon變換和黑白檢測算子檢測4個(gè)典型特征方向上像素灰度分布特征實(shí)現(xiàn)角點(diǎn)檢測，當(dāng)圖像邊緣存在畸變時(shí)其檢測性能得不到保證。文獻(xiàn)［10］采用Hessian矩陣算子進(jìn)行角點(diǎn)初選，然后基于對(duì)稱約束確定真實(shí)角點(diǎn)，該方法采用圓形檢測模板使得有用像素總有一部分處于扇形邊緣，這會(huì)造成有用信息流失，進(jìn)而影響檢測精度。

第2類方法采用新的標(biāo)定模板進(jìn)行特征點(diǎn)檢測。文獻(xiàn)［11］在黑白棋盤四周增加了4條長寬比較大的長方形邊界，基于參考圖像和腐蝕算子檢測長方形邊界，在此基礎(chǔ)上采用交比不變性原理實(shí)現(xiàn)角點(diǎn)定位。文獻(xiàn)［12］在黑白棋盤中增加了5個(gè)沙漏狀的圖形，充分減小了立體投影后圖像幾何形狀變化的影響。文獻(xiàn)［13］提出一種以漸進(jìn)圓形為特征的標(biāo)定模板及相應(yīng)的檢測算法，結(jié)果顯示標(biāo)定精度相比黑白棋盤提高20%。這些方法多次采用曲線擬合計(jì)算量較大，此外其標(biāo)定模板也僅適用于具體的應(yīng)用。

第3類方法是采用現(xiàn)有的軟件工具箱直接進(jìn)行相機(jī)標(biāo)定，使用較廣泛的有2種: Matlab相機(jī)標(biāo)定工具箱［14］和OpenCV算法庫［15］。前者在使用過程中需要用戶人工選擇4個(gè)邊界角點(diǎn)，無法實(shí)現(xiàn)自動(dòng)標(biāo)定，而且該工具箱不支持處理大于2Mb的圖像［6，11］。從實(shí)驗(yàn)結(jié)果看，OpenCV算法庫實(shí)現(xiàn)的標(biāo)定精度不如Matlab標(biāo)定工具箱，并且其角點(diǎn)檢測結(jié)果往往排序混亂，對(duì)于參數(shù)求解不利。

基于此，本文在分析黑白棋盤角點(diǎn)特性基礎(chǔ)上，提出一種基于交叉熵的角點(diǎn)檢測算法。該算法原理簡單、易于實(shí)現(xiàn)并且可用于自動(dòng)標(biāo)定。對(duì)比實(shí)驗(yàn)結(jié)果證明了算法的有效性和實(shí)用性。

1　棋盤角點(diǎn)特性分析

典型黑白棋盤標(biāo)定模板如圖1所示。定義棋盤格內(nèi)部角點(diǎn)為: 2個(gè)相間的黑色方格和白色方格的交叉點(diǎn)。定義像素點(diǎn)的四象限如圖2所示。對(duì)比其他像素點(diǎn)，內(nèi)部角點(diǎn)具有如下的特性:

1)角點(diǎn)相鄰象限像素的灰度差絕對(duì)值最大。

2)角點(diǎn)對(duì)角象限像素的灰度差異最大;

3)角點(diǎn)局部灰度值變化劇烈，具有最大的灰度梯度值。

圖1　標(biāo)準(zhǔn)黑白棋盤標(biāo)定模板

圖2　內(nèi)部角點(diǎn)局部象限定義

2　角點(diǎn)檢測算法描述

如圖3所示本文提出的交叉熵檢測算法包括4個(gè)步驟:角點(diǎn)初定位，交叉熵篩選，局部非極大值抑制及亞像素坐標(biāo)解算。其主要特點(diǎn)是在傳統(tǒng)角點(diǎn)初選基礎(chǔ)上引入象限灰度信息距離實(shí)現(xiàn)精確篩選。

圖3　交叉熵檢測算法流程

2. 1角點(diǎn)初定位

根據(jù)上文特性1，定義角點(diǎn)鄰域正方形滑動(dòng)窗W，邊長l = 2s + 1，s為分布到每個(gè)象限的正方形區(qū)域邊長。據(jù)此對(duì)4個(gè)象限像素灰度和計(jì)算如下:

式中: f(i，j)為像素點(diǎn)(i，j)的灰度值，F(xiàn)(i，j)k是第k個(gè)象限的像素灰度和，k∈{ 1，2，3，4}。

理想情況下，圖2中黑白相鄰象限中像素灰度差絕對(duì)值為255s2?？紤]到傾斜投影及采樣噪聲，灰度差通常小于該值。故得到角點(diǎn)初選規(guī)則如下:

式中:μ表征相鄰像素象限灰度值差異程度，s表征檢測窗尺寸。隨著μ減小，角點(diǎn)檢測數(shù)量呈非線性增長，根據(jù)經(jīng)驗(yàn)取值0. 1～0. 3; s可以根據(jù)圖像尺寸及黑白棋盤像素面積確定，通常取值為5即可。

2. 2交叉熵篩選規(guī)則

隨機(jī)分布的交叉熵［16］表征了其信息差異的定量描述。對(duì)于角點(diǎn)(i，j)，可以得到先驗(yàn)公式如下:

即小范圍內(nèi)相對(duì)角點(diǎn)(i，j)對(duì)稱的像素點(diǎn)灰度值也對(duì)稱。由此可知互相對(duì)稱的2個(gè)象限之間灰度差異最小，可以給出兩者交叉熵定義如下。

定義1針對(duì)角點(diǎn)(i，j)，其第1象限和第3象限像素灰度交叉熵可表示為:

同理可得第二和第四象限灰度交叉熵D24(i，j)。

其中s同樣取值為5。對(duì)于候選角點(diǎn)進(jìn)行交叉熵計(jì)算，對(duì)應(yīng)象限灰度值對(duì)稱特性最好時(shí)，即可實(shí)現(xiàn)角點(diǎn)篩選，相關(guān)實(shí)驗(yàn)結(jié)果見第3節(jié)。

2. 3局部梯度幅值非極大值抑制

為避免在模糊角點(diǎn)附近產(chǎn)生多個(gè)候選角點(diǎn)(如圖4c)所示)，這里引入邊緣檢測思想進(jìn)行角點(diǎn)精確定位。通常真實(shí)的角點(diǎn)始終處于圖像黑白框的邊緣，采用Canny［17］算子設(shè)計(jì)非極大值抑制規(guī)則如下:

1)計(jì)算備選角點(diǎn)附近x與y向的灰度梯度［18］;

2)根據(jù)梯度值計(jì)算梯度向量幅值;

3)局部梯度幅值最大點(diǎn)即為最終的角點(diǎn)像素。

2. 4亞像素角點(diǎn)坐標(biāo)解算

室內(nèi)衛(wèi)星編隊(duì)飛行要求視覺定位精度達(dá)到毫米級(jí)［2］，因此相機(jī)標(biāo)定精度要足夠高。在上述像素級(jí)精度基礎(chǔ)上，引入Forstner算子［19］實(shí)現(xiàn)亞像素級(jí)的角點(diǎn)定位。以下給出亞像素坐標(biāo)計(jì)算方法:

式中: (x'，y')是像素點(diǎn)(x，y)優(yōu)化后的亞像素坐標(biāo)。其中各個(gè)中間變量計(jì)算如下:

Ix與Iy分別為像素(x，y)在x及y向的灰度梯度。

3　算法測試與分析

為了對(duì)所提出的交叉熵檢測算法進(jìn)行性能對(duì)比測試，選擇相機(jī)標(biāo)定算法常用的標(biāo)準(zhǔn)測試圖片［14］。

3. 1算法執(zhí)行結(jié)果

以圖像包中“Image 13”為例，圖4為算法的檢測結(jié)果，表1總結(jié)了前3步執(zhí)行過后的角點(diǎn)數(shù)。

圖4　交叉熵檢測算法執(zhí)行結(jié)果(Image13)

表1　交叉熵檢測算法的檢測角點(diǎn)數(shù)總結(jié)

如圖4a)所示，角點(diǎn)初選結(jié)果包括很多非角點(diǎn)像素;對(duì)比圖4b)可知交叉熵篩選可剔除大部分非角點(diǎn)像素，僅有角點(diǎn)附近的像素需要排除，證明了該方法的有效性;對(duì)比圖4c)說明非極大值抑制可以很好實(shí)現(xiàn)真實(shí)角點(diǎn)局部相鄰像素點(diǎn)的排除。

3. 2與其他算法結(jié)果對(duì)比

為了嚴(yán)格地對(duì)交叉熵檢測算法性能進(jìn)行對(duì)比，選擇標(biāo)準(zhǔn)測試圖像包中“Image13”、“Image18”和“Image20”3幅圖進(jìn)行實(shí)驗(yàn)，這幾幅圖的拍攝傾斜角最大，產(chǎn)生的畸變也最大。圖5～圖7分別對(duì)比了Harris算子、SV算子以及交叉熵檢測算法之間的檢測結(jié)果，該結(jié)果同時(shí)也總結(jié)于表2中。

圖5　對(duì)比算法檢測結(jié)果

圖6　Image18檢測結(jié)果

圖7　Image20檢測結(jié)果

表2　幾種算法檢測結(jié)果對(duì)比

對(duì)比圖5中3種方法的檢測結(jié)果，可知交叉熵檢測算法可正確檢測出所有的內(nèi)部角點(diǎn)，Harris算子檢測出所有角點(diǎn)，但是還包括非角點(diǎn)像素; SV算子性能最差，不但丟失了部分角點(diǎn)而且檢測出了大量非角點(diǎn)像素。由此可知:交叉熵檢測算法優(yōu)于后兩者。同樣的結(jié)果可以從圖6、圖7中看出。

3. 3亞像素檢測精度分析

以“Image 13”為例，對(duì)本文算法得到的亞像素坐標(biāo)值和Marlab標(biāo)定工具箱得到的結(jié)果進(jìn)行對(duì)比。選擇圖“Image 13”中第一行從右至左的角點(diǎn)坐標(biāo)，對(duì)比結(jié)果列于表3中。

表3　亞像素坐標(biāo)對(duì)比

表3顯示，2種檢測方法得到的結(jié)果相差不超過1個(gè)像素值，由此證明交叉熵檢測算法結(jié)果正確。

4　結(jié)論

本文提出一種基于交叉熵的角點(diǎn)檢測算法。該算法實(shí)現(xiàn)過程包括4個(gè)步驟:角點(diǎn)初選，交叉熵篩選，局部梯度非極大值抑制以及亞像素角點(diǎn)解算等。實(shí)驗(yàn)結(jié)果顯示，該算法優(yōu)于Harris算子以及SV算子，其亞像素級(jí)檢測精度與Matlab標(biāo)定工具箱相當(dāng)，易于實(shí)現(xiàn)在線標(biāo)定。目前該算法已經(jīng)應(yīng)用于室內(nèi)衛(wèi)星編隊(duì)飛行平臺(tái)的視覺定位系統(tǒng)中，效果良好。

參考文獻(xiàn):

［1］Andani Osuman．Multi-Robot Testbed for Distributed Space System［D］．Delft University of Technology，2012

［2］Zhao B，Guo J，Gill E K A．A Camera-Based Positioning System for the Formation Flying Testbed［C］∥Proceedings of the 63rd International Astronautical Congress，2012: 8325-8333

［3］Zhang Z．A Flexible New Technique for Camera Calibration［J］．IEEE Trans on Pattern Analysis and Machine Intelligence，2000，22: 1330-1334

［4］Chris Harris，Mike Stephens．A Combined Corner and Edge Detector［C］∥Proceedings of the 4th Alvey Vision Conference，Manchester，1988: l47-l51

［5］Arturo de Laescalera，Jose Maria Armingol．Automatic Chessboard Detection for Intrinsic and Extrinsic Camera Parameter Calibration［J］．Sensors，2010，10: 2027-2044

［6］Wang Zhongshi，Wu Wei，Xu Xinhe，et al．Recognition and Location of the Internal Corners of Planar Checkerboard Calibration Pattern Image［J］．Applied Mathematics and Computation，2007，185: 894-906

［7］劉陽成，朱楓．一種新的棋盤格圖像角點(diǎn)檢測算法［J］．中國圖像圖形學(xué)報(bào)，2006，11(5) : 656-660 Liu Yangcheng，Zhu Feng．A New Algorithm for X-Corner Detection［J］．Journal of Image and Graphics，2006，11(5) : 656-660 (in Chinese)

［8］郝穎明，朱楓．?dāng)z像機(jī)在線標(biāo)定中的棋盤格角點(diǎn)自動(dòng)檢測方法［J］．計(jì)算機(jī)工程，2007，33(17) : 213-215 Hao Yingming，Zhu Feng．Automatic X-Corners Detection for Online Camera Calibration［J］．Computer Engineering，2007，33 (17) : 213-215 (in Chinese)

［9］劉陽，王福利，常玉清，等．黑白棋盤格角點(diǎn)檢測算法［J］．東北大學(xué)學(xué)報(bào)，2007，28(8) : 1090-1093 Liu Yang，Wang Fuli，Chang Yuqing，et al．Black and White X-Corner Detection Algorithm［J］．Journal of Northeastern University，2007，28(8) : 1090-1093 (in Chinese)

［10］He Juan，Xia Junying，Xu Xiaoquan，et al．Automatic Corner Detection and Localization for Camera Calibration［C］∥The 10th International Conference on Electronic Measurement＆Instruments，2011: 312-315

［11］Shi Xifan，Hong Ning，Cai Tiefeng．An Automatic and Robust Chessboard Corner Extraction［J］．LNCS Transactions on Edutainment 6758，2011，49-56

［12］Yu Chunsheng，Peng Qingjin．Robust Recognition of Checkerboard Pattern for Camera Calibration［J］．Optical Engineering，2006，45: 093201

［13］梁力，尹東斐，王川．高精度攝像機(jī)標(biāo)定模板的設(shè)計(jì)及識(shí)別算法［J］．西安交通大學(xué)學(xué)報(bào)，2011，45(4) : 82-85 (in Chinese) Liang Li，Yin Dongfei，Wang Chuan．Design and Detection Methods for Accurate Camera Calibration Targets［J］．Journal of Xi' an Jiaotong University，2011，45(4) : 82-85 (in Chinese)

［14］Jean-Yves Bouguet．Camera Calibration Toolbox for Matlab［EB/OL］．(2013-12-02)［2014-02-10］．http:∥www．vision．caltech．edu/bouguetj/calib-doc/index．html

［15］Gary Bradski，Adrian Kaehler: Learning Open CV［M］．USA，O'Reiuy Media，Inc，2008

［16］Li C H，Lee C K．Minimum Cross Entropy Thresholding［J］．Pattern Recognition，1993，26: 617-625

［17］John Canny．A Computational Approach to Edge Detection［J］．IEEE Trans on Pattern Analysis And Machine Intelligence，1986，8(6) : 679-698

operators，MATLAB，pixels; camera calibration，chess board corner detection，gradient amplitude，grey value difference，local overlap，non-maximum suppression，principle of minimum cross entropy

［18］Gonzalez R C，Woods R E．Digital Image Processing［M］．2nd ed，New Jersey，USA，Prentice Hall，2002

Chessboard Corner Detection Algorithm Based on Minimum Cross Entropy

Zhao Bin1，2，J．Guo2，E．K．A．Gill2，Zhou Jun1

(1．Institute of Precision Guidance and Control，Northwestern Polytechnical University，Xi'an 710072，China 2．Faculty of Aerospace Engineering，Delft University of Technology，Kluyverweg 1，2629 HS Delft，The Netherlands)

Abstract:The shortcoming of the present B/W chessboard corner detection algorithm is analyzed and a new method based on cross entropy is proposed．Firstly，the pixels around the corner are divided into 4 quadrants，and initial selection of corners is carried out based on the gray value difference between the adjacent quadrants; secondly，the cross entropy of the diagonal quadrant is defined，and the corner screening is done using the principle of minimum cross entropy; thirdly，the idea of non-maximum suppression of local gradient amplitude is introduced to solve the problem of local overlap of the candidates; at last，sub-pixel coordinates of corners are calculated using Frostner Operator．Experiments and their analysis prove preliminarily that: (1) the detection result of this algorithm is better than the classical Harris Operator and SV Operator; (2) the sub-pixel accuracy obtained is almost the same as that obtained with the Matlab Camera Calibration Toolbox，and it is suitable for online camera calibration．

Key words:algorithms，calibration，CCD cameras，entropy，flowcharting，interference suppression，mathematical

作者簡介:趙斌(1986—)，西北工業(yè)大學(xué)講師，主要從事飛行器制導(dǎo)控制及半實(shí)物仿真研究。

收稿日期:2014-09-18基金項(xiàng)目:西北工業(yè)大學(xué)基礎(chǔ)研究基金(JCT20130101)資助

文章編號(hào):1000-2758(2015) 02-0216-06

文獻(xiàn)標(biāo)志碼:A

中圖分類號(hào):TP391．4