一种基于交叉熵的黑白棋盘角点检测算法



一种基于交叉熵的黑白棋盘角点检测算法

赵斌1，2，J．Guo2，E．K．A．Gill2，周军1

(1．西北工业大学精确制导与控制研究所，陕西西安710072 2．Faculty of Aerospace Engineering，Delft University of Technology，Kluyverweg 1，2629 HS Delft，The Netherlands)

摘要:分析了现有黑白棋盘角点检测算法存在的不足，将交叉熵思想引入角点检测中。该算法首先将角点周围像素划分为4个象限，通过相邻象限间的像素灰度差实现角点初选;其次，给出对角象限灰度交叉熵定义，根据局部交叉熵最小原理实现角点筛选;第3，针对备选角点局部重叠的问题，采用梯度幅值非极大值抑制方法实现像素级角点定位;最后采用Frostner算子实现角点的亚像素坐标解算。实验结果显示该算法检测结果优于经典Harris算子以及SV算子，获取的角点亚像素坐标精度与Matlab相机标定工具箱相当，同时易于实现在线标定。

关键词:相机标定;棋盘角点检测;交叉熵;非极大值抑制;梯度幅值

在室内卫星编队飞行平台［1-2］中，视觉系统的标定精度是确保漂浮体定位精度的关键，其通常包括图像特征点检测和相机参数求解2个过程。关于相机参数求解，张正友算法［3］已经比较成熟，而图像特征点检测则成为研究热点。

第1类方法多采用黑白棋盘标定模板，对此实现角点检测最早的方法是Harris算法［4］，采用局部灰度值的高斯梯度实现角点检测，当角点周围存在图像模糊时会得到多个虚假角点，影响标定精度。文献［5］采用2次Hough变换实现黑白栅格直线拟合，并根据直线交点获取角点精确坐标。文献［6］采用旋转直角模板进行角点筛选，然后采用多次曲线拟合实现角点确定。这2种方法计算量大，难以实现在线标定。文献［7］提出对称方差检测算法(SV算子)，该方法仅采用角点附近2个象限的像素信息，实际使用中会产生错误角点。文献［8］提出一种改进的SV检测算子，采用平面到平面的变换实现角点初定位，基于区域能量中心概念实现精确定位。其仿真结果表明，该算法会造成部分角点丢失。文献［9］通过Radon变换和黑白检测算子检测4个典型特征方向上像素灰度分布特征实现角点检测，当图像边缘存在畸变时其检测性能得不到保证。文献［10］采用Hessian矩阵算子进行角点初选，然后基于对称约束确定真实角点，该方法采用圆形检测模板使得有用像素总有一部分处于扇形边缘，这会造成有用信息流失，进而影响检测精度。

第2类方法采用新的标定模板进行特征点检测。文献［11］在黑白棋盘四周增加了4条长宽比较大的长方形边界，基于参考图像和腐蚀算子检测长方形边界，在此基础上采用交比不变性原理实现角点定位。文献［12］在黑白棋盘中增加了5个沙漏状的图形，充分减小了立体投影后图像几何形状变化的影响。文献［13］提出一种以渐进圆形为特征的标定模板及相应的检测算法，结果显示标定精度相比黑白棋盘提高20%。这些方法多次采用曲线拟合计算量较大，此外其标定模板也仅适用于具体的应用。

第3类方法是采用现有的软件工具箱直接进行相机标定，使用较广泛的有2种: Matlab相机标定工具箱［14］和OpenCV算法库［15］。前者在使用过程中需要用户人工选择4个边界角点，无法实现自动标定，而且该工具箱不支持处理大于2Mb的图像［6，11］。从实验结果看，OpenCV算法库实现的标定精度不如Matlab标定工具箱，并且其角点检测结果往往排序混乱，对于参数求解不利。

基于此，本文在分析黑白棋盘角点特性基础上，提出一种基于交叉熵的角点检测算法。该算法原理简单、易于实现并且可用于自动标定。对比实验结果证明了算法的有效性和实用性。

1　棋盘角点特性分析

典型黑白棋盘标定模板如图1所示。定义棋盘格内部角点为: 2个相间的黑色方格和白色方格的交叉点。定义像素点的四象限如图2所示。对比其他像素点，内部角点具有如下的特性:

1)角点相邻象限像素的灰度差绝对值最大。

2)角点对角象限像素的灰度差异最大;

3)角点局部灰度值变化剧烈，具有最大的灰度梯度值。

图1　标准黑白棋盘标定模板

图2　内部角点局部象限定义

2　角点检测算法描述

如图3所示本文提出的交叉熵检测算法包括4个步骤:角点初定位，交叉熵筛选，局部非极大值抑制及亚像素坐标解算。其主要特点是在传统角点初选基础上引入象限灰度信息距离实现精确筛选。

图3　交叉熵检测算法流程

2. 1角点初定位

根据上文特性1，定义角点邻域正方形滑动窗W，边长l = 2s + 1，s为分布到每个象限的正方形区域边长。据此对4个象限像素灰度和计算如下:

式中: f(i，j)为像素点(i，j)的灰度值，F(i，j)k是第k个象限的像素灰度和，k∈{ 1，2，3，4}。

理想情况下，图2中黑白相邻象限中像素灰度差绝对值为255s2。考虑到倾斜投影及采样噪声，灰度差通常小于该值。故得到角点初选规则如下:

式中:μ表征相邻像素象限灰度值差异程度，s表征检测窗尺寸。随着μ减小，角点检测数量呈非线性增长，根据经验取值0. 1～0. 3; s可以根据图像尺寸及黑白棋盘像素面积确定，通常取值为5即可。

2. 2交叉熵筛选规则

随机分布的交叉熵［16］表征了其信息差异的定量描述。对于角点(i，j)，可以得到先验公式如下:

即小范围内相对角点(i，j)对称的像素点灰度值也对称。由此可知互相对称的2个象限之间灰度差异最小，可以给出两者交叉熵定义如下。

定义1针对角点(i，j)，其第1象限和第3象限像素灰度交叉熵可表示为:

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

其中s同样取值为5。对于候选角点进行交叉熵计算，对应象限灰度值对称特性最好时，即可实现角点筛选，相关实验结果见第3节。

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

为避免在模糊角点附近产生多个候选角点(如图4c)所示)，这里引入边缘检测思想进行角点精确定位。通常真实的角点始终处于图像黑白框的边缘，采用Canny［17］算子设计非极大值抑制规则如下:

1)计算备选角点附近x与y向的灰度梯度［18］;

2)根据梯度值计算梯度向量幅值;

3)局部梯度幅值最大点即为最终的角点像素。

2. 4亚像素角点坐标解算

室内卫星编队飞行要求视觉定位精度达到毫米级［2］，因此相机标定精度要足够高。在上述像素级精度基础上，引入Forstner算子［19］实现亚像素级的角点定位。以下给出亚像素坐标计算方法:

式中: (x'，y')是像素点(x，y)优化后的亚像素坐标。其中各个中间变量计算如下:

Ix与Iy分别为像素(x，y)在x及y向的灰度梯度。

3　算法测试与分析

为了对所提出的交叉熵检测算法进行性能对比测试，选择相机标定算法常用的标准测试图片［14］。

3. 1算法执行结果

以图像包中“Image 13”为例，图4为算法的检测结果，表1总结了前3步执行过后的角点数。

图4　交叉熵检测算法执行结果(Image13)

表1　交叉熵检测算法的检测角点数总结

如图4a)所示，角点初选结果包括很多非角点像素;对比图4b)可知交叉熵筛选可剔除大部分非角点像素，仅有角点附近的像素需要排除，证明了该方法的有效性;对比图4c)说明非极大值抑制可以很好实现真实角点局部相邻像素点的排除。

3. 2与其他算法结果对比

为了严格地对交叉熵检测算法性能进行对比，选择标准测试图像包中“Image13”、“Image18”和“Image20”3幅图进行实验，这几幅图的拍摄倾斜角最大，产生的畸变也最大。图5～图7分别对比了Harris算子、SV算子以及交叉熵检测算法之间的检测结果，该结果同时也总结于表2中。

图5　对比算法检测结果

图6　Image18检测结果

图7　Image20检测结果

表2　几种算法检测结果对比

对比图5中3种方法的检测结果，可知交叉熵检测算法可正确检测出所有的内部角点，Harris算子检测出所有角点，但是还包括非角点像素; SV算子性能最差，不但丢失了部分角点而且检测出了大量非角点像素。由此可知:交叉熵检测算法优于后两者。同样的结果可以从图6、图7中看出。

3. 3亚像素检测精度分析

以“Image 13”为例，对本文算法得到的亚像素坐标值和Marlab标定工具箱得到的结果进行对比。选择图“Image 13”中第一行从右至左的角点坐标，对比结果列于表3中。

表3　亚像素坐标对比

表3显示，2种检测方法得到的结果相差不超过1个像素值，由此证明交叉熵检测算法结果正确。

4　结论

本文提出一种基于交叉熵的角点检测算法。该算法实现过程包括4个步骤:角点初选，交叉熵筛选，局部梯度非极大值抑制以及亚像素角点解算等。实验结果显示，该算法优于Harris算子以及SV算子，其亚像素级检测精度与Matlab标定工具箱相当，易于实现在线标定。目前该算法已经应用于室内卫星编队飞行平台的视觉定位系统中，效果良好。

参考文献:

［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］刘阳成，朱枫．一种新的棋盘格图像角点检测算法［J］．中国图像图形学报，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］郝颖明，朱枫．摄像机在线标定中的棋盘格角点自动检测方法［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］刘阳，王福利，常玉清，等．黑白棋盘格角点检测算法［J］．东北大学学报，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］．西安交通大学学报，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—)，西北工业大学讲师，主要从事飞行器制导控制及半实物仿真研究。

收稿日期:2014-09-18基金项目:西北工业大学基础研究基金(JCT20130101)资助

文章编号:1000-2758(2015) 02-0216-06

文献标志码:A

中图分类号:TP391．4