基于生长的棋盘格角点检测方法--（1）原理介绍
基于生长的棋盘格角点检测方法--（1）原理介绍
前言
棋盘格中角点检测方法是相机标定中必不可少的步骤之一。Opencv中的函数
bool findChessboardCorners(InputArray image, Size patternSize, OutputArray corners, int flags=CALIB_CB_ADAPTIVE_THRESH+CALIB_CB_NORMALIZE_IMAGE )就可以轻松实现棋盘格角点检测结果。如下图所示
具体使用方法参考如下链接 http://blog.csdn.net/u011651743/article/details/51099543 但是，这种方法虽然简单，但是在实际使用中有如下问题： 1、 需要提前指定棋盘格尺寸。这在很多自动化应用中是很难做到的。 2、 鲁棒性差。棋盘格如果有干扰（比如轻微的遮挡）就会使得检测失败，而且棋盘倾斜角度较大也会检测失败。具体测试见上述链接。 3、 无法处理一张图片包含多张棋盘的情况。
基于此，今天介绍的是一种新的检测方法。主要参考论文《Automatic Camera and Range Sensor Calibration using a single Shot》。可以针对性地解决上述问题。 优点： 1、 不需要提前指定棋盘格数目。 2、 鲁棒性好。因为是基于生长的算法，所以如果出现干扰，就会绕过干扰，生长出最大的棋盘。 3、 可以检测一个图片里包含多张棋盘的情况。 缺点： 1、受棋盘的矩形形状约束，只能生长出矩形的棋盘。严格的说也不能算缺点，因为本身棋盘就是矩形的，真的长出三头六臂还能叫棋盘吗。不过以后我会介绍一种不依赖棋盘约束的方法。 2、计算量较大。主要集中在棋盘生长部分。
先来欣赏一下该方法的结果吧
算法原理介绍
算法主要分三个步骤：1、 定位棋盘格角点位置，2、亚像素级角点和方向的精细化，3、优化能量函数、生长棋盘格。下面具体来说明
1、 定位棋盘格角点位置
要处理的图片中一般会包含很多非棋盘的自然或人工背景，所以第一步就是定位角点的位置。下图是角点检测原理示例。
首先定义两种不同的角点原型。一种用于和坐标轴平行的角点（上图a），另一种用于旋转45°的角点（上图b）。根据实践经验可以发现，这两种简单的原型对于由透视变换引起的较大范围的变形的角点检测来说，已经足够。每个原型由4个滤波核{A,B,C,D}组成，用于后面和图像进行卷积操作。 下面我们利用这两个角点原型来计算每个像素点与角点的相似程度（Corner likelihood），来看下面的定义：
我们得到的Corner likelihood图虽然能够给出大致的角点范围，但是如何进一步得到角点精确的位置呢？下一步就是在Corner likelihood图上利用非极大值抑制（non-maxima-suppression，NMS）来获得候选点。 那么何为非极大值抑制呢？ 非极大值抑制顾名思义就是抑制不是极大值的元素，搜索局部的极大值。这个局部代表的是一个邻域，邻域有两个参数可变，一是邻域的维数，二是邻域的大小。这里我们用NMS来选取那些邻域里分数最高的极大值像素点，同时抑制那些分数低的像素点。非极大值抑制算法的详细原理参考： http://www.cnblogs.com/liekkas0626/p/5219244.html
2、 亚像素级角点和方向的精细化
邻域的像素通过梯度幅值自动加权，上述式子右侧对c’求导并令其等于0，可以得到解析解:
下一步就是refine边缘方向矢量e1,e2，可以通过最小化normals的偏差和对应的梯度实现：
3、 优化能量函数生长棋盘格
我们定义棋盘格的能量函数如下：
其中第一项E_corners是当前棋盘中角点总数的负值。 第二项E_structure描述了用两个相邻角点来预测第3个角点的匹配程度，分别对棋盘的每行和每列相邻的3个角点（triples）计算其结构能量，取其中的最大值作为该棋盘的结构能量。 值得注意的是，由于结构能量约束中使用的是局域的线性约束，上述棋盘格生长方法可以扩展到鱼眼镜头拍摄的高畸变图像。
不难发现，计算量和棋盘大小呈现指数关系，当棋盘尺寸较大时，计算量会非常惊人。所以在求解时不能使用穷举法搜索，在此使用的是一种离散优化策略，在实践中证明比较有效。具体过程（见上图（a））如下： 给定一个种子角点，我们沿着其边缘方向搜索产生一个初始化的种子棋盘格。该棋盘格有3x3个角点，有2x2个棋盘（见上图（a）中最左侧）。然后以此种子棋盘格为基础，分别从最外沿的4个边缘去生长棋盘格，生成4个新的棋盘格proposals。如果其中能量最小的那个棋盘格的能量值比棋盘格扩展前的能量更减少了，就说明生长成功，用这个新的棋盘格代替原来棋盘格。继续生长，直到4个 方向新棋盘格能量不再减少为止。
另外，为了在单张图片中生长出多个棋盘格，我们把每个角点都尝试作为种子点用上述方法去生长，这样会产生多个重叠的棋盘格。我们只保留能量函数最小的那个作为最终的结果，其他的重叠部分去掉即可。
参考资料
1、论文 Geiger A, Moosmann F, Car Ö, et al. Automatic camera and range sensor calibration using a single shot[C]//Robotics and Automation (ICRA), 2012 IEEE International Conference on. IEEE, 2012: 3936-3943.