效果优于MATLAB——基于生长的棋盘格角点检测

该算法在论文《Automatic camera and range sensor calibration using a single shot》中被提出，同时作者还给出了角点检测部分的MATLAB源代码。这篇文章的工作主要是使用OpenCV和C++复现MATLAB的代码效果，同时梳理一下角点检测的过程。

复现的代码见camera_calibration

算法分为三个部分：角点提取、角点亚像素化、棋盘生长。

角点提取

角点提取部分采取的是类似Harris特征的检测方法。它设置的角点特征如下图所示：

这里有两组特征，如果角点的旋转角度不大，则由第一组特征检测，如果角点旋转角度大，则由第二组特征检测。

使用这些特征作为卷积核对图像进行卷积。对于每一个像素i，它经过一组特征的四个卷积核的卷积后会得到四个值f_A f_B f_C f_D，其最后的卷积结果c的定义如下：

最后每个像素由不同大小、不同类型的卷积核卷积后取各个卷积结果的最大值，其得到角点似然域，如下图右图所示：

最后对角点似然域进行非极大值抑制即可得到像素精度的角点值。

角点亚像素化

该方法是根据角点所对应的两条线的角度来对角点坐标进行优化，同时也优化了两条线的角度（后文以角点的方向代指）。

首先使用Sobel算子对图像进行横向和纵向的滤波，滤波卷积核如下图所示：

分别得到两幅图像梯度，将两个梯度一一对应进行反正切计算，即可得到每个像素的角度，将两幅图像的像素进行平方和计算，可以作为角度对应的权重。

img_du     = conv2(double(img),du,'same');
img_dv     = conv2(double(img),dv,'same');
img_angle  = atan2(img_dv,img_du);
img_weight = sqrt(img_du.^2+img_dv.^2);

对于每一个角点，以角点为中心取一个正方形，在正方形内，以像素角度为横坐标，角度权重为纵坐标绘制角度直方图，可以从直方图中找到经过角点的两条线的角度α1和α2，如下图所示：

但这只是线条角度的估计，不过可以使用得到的结果对角点进行初步筛选，删除α1和α的角度差值小于0.3的角点。

假设c是理想的角点位置，p是c的局部邻域的一个像素点，gp是p点的图像梯度向量，那么就有：

简单解释一下上式。原因如下图：中心绿色的点表示理想角点c，假如像素点p不在边界上，如下图标号为1的位置，平坦区域梯度gp为零向量，所以上式成立；假如像素点p在边界上，如下图标号为2的位置，梯度gp向量方向垂直向下，(p-c)方向水平向左，两向量方向互相垂直，所以上式仍成立。

上图是理想情况下棋盘格，但是实际上边缘不可能这样锐利（只有一个像素大小），梯度方向也没有这么理想，最理想的角点c的位置就是我们在角点候选点c’的邻域Ni(c’)内找到满足以下式子的c’：

邻域的像素通过梯度幅值自动加权，上述式子右侧对c’求导并令其等于0，可以得到解析解：

上式计算的是角点的真正中心坐标。而对于角点的α1和α2，可将其转换为方向矢量e1和e2，其中ei=[cos(αi), sin(αi)]，计算方向矢量可转化为最小化下列式子：

这可以对梯度矩阵进行奇异值分解，取最小的奇异值对应的特征向量，即为方向矢量。

棋盘生长

得到角点之后，需要从角点中重构出棋盘结构，利用这种方法，可以在一副图片中识别多个棋盘，同时对于不完整的棋盘也可以提取出部分可用的棋盘角点。

首先对每一个角点初始化一个以其为中心的，包含3×3个角点的棋盘，并定义了一个能量函数来描述棋盘的合理性：

能量函数分为两部分，第一部分是角点能量，其值为棋盘角点个数的相反数。第二部分是局部线性约束的能量，对于每个角点，取其左右或者上下的相邻角点构成一个triple，如下图所示：

公式中i和k分别代表两端的角点，j代表中心的角点，显然，如果三个角点处于一条直线上，则局部线形约束的能量就越小。

最后棋盘的能量为两部分能量之和：

值得注意的是，由于结构能量约束中使用的是局域的线性约束，上述棋盘格生长方法可以扩展到鱼眼镜头拍摄的高畸变图像。

棋盘生长的过程如下图所示：

给定一个种子角点，我们沿着其边缘方向搜索产生一个初始化的种子棋盘格。该棋盘格有3x3个角点，有2x2个棋盘。然后以此种子棋盘格为基础，分别从最外沿的4个边缘去生长棋盘格，生成4个新的棋盘格。如果其中能量最小的那个棋盘格的能量值比棋盘格扩展前的能量更减少了，就说明生长成功，用这个新的棋盘格代替原来棋盘格。继续生长，直到4个方向新棋盘格能量不再减少为止。下图是最终的检测结果。

参考

• 《Automatic camera and range sensor calibration using a single shot》
• 一次拍摄搞定多相机自动化标定
• 基于生长的棋盘格角点检测方法 代码介绍
• 论文作者MATLAB代码下载地址