libcbdetect

libcbdetect 是一个用于自动子像素级别的棋盘格（checkerboard）、棋盘（chessboard）以及 Deltille 图案检测的库。它主要由 C++ 编写，旨在提供高精度、高鲁棒性的角点检测和图案组合功能，是一种基于生长的棋盘格角点检测方法。

基于生长的棋盘格焦点检测方法具有以下特性：

解决的问题：

• 需要提前指定棋盘格尺寸。这在很多自动化应用中是很难做到的。
• 鲁棒性差。棋盘格如果有干扰（比如轻微的遮挡）就会使得检测失败，而且棋盘倾斜角度较大也会检测失败。具体测试见上述链接。
• 无法处理一张图片包含多张棋盘的情况。

优点：

• 不需要提前指定棋盘格数目。
• 鲁棒性好。因为是基于生长的算法，所以如果出现干扰，就会绕过干扰，生长出最大的棋盘。
• 可以检测一个图片里包含多张棋盘的情况。

缺点：

• 受棋盘的矩形形状约束，只能生长出矩形的棋盘。严格的说也不能算缺点，因为本身棋盘就是矩形的，真的长出三头六臂还能叫棋盘吗。
• 计算量较大。主要集中在棋盘生长部分。
  

算法原理介绍

算法主要分三个步骤：1、 定位棋盘格角点位置，2、亚像素级角点和方向的精细化，3、优化能量函数、生长棋盘格。

定位棋盘格角点位置

要处理的图片中一般会包含很多非棋盘的自然或人工背景，所以第一步就是定位角点的位置。下图是角点检测原理示例。

首先定义两种不同的角点原型。一种用于和坐标轴平行的角点（上图 a），另一种用于旋转 45° 的角点（上图 b）。根据实践经验可以发现，这两种简单的原型对于由透视变换引起的较大范围的变形的角点检测来说，已经足够。每个原型由 4 个滤波核{A,B,C,D}组成，用于后面和图像进行卷积操作。

下面我们利用这两个角点原型来计算每个像素点与角点的相似程度（Corner likelihood），来看下面的定义：

$$\begin{gathered} c=max(s_1^1,s_2^1,s_1^2,s_2^2) \\ {s}_1^i=min(min(f_A^i,f_B^i)-\mu ,\mu -min(f_C^i,f_D^i)) \\ {s}_2^i=min(\mu -min(f_A^i,f_B^i),min(f_C^i,f_D^i)-\mu ) \\ \mu =0.25(f_A^i+f_B^i+f_C^i+f_D^i) \end{gathered}$$
其中：

• $f_A^i$表示卷积核和原型i（i=1,2）在某个像素点的卷积结果。
• $s_1^i$和$s_2^i$表示原型i的两种可能的flippings，考虑棋盘格角点出向左对角线为黑，右对角线为白；或相反

若4个核中任何一个结果比较小，则Corner linkelihood的值c很小，对于过滤大量的非棋盘格式的角点，然后通过NMS算法获取角点精确的位置。

亚像素级角点和方向的精细化

上面得到的角点一般不是很精确，需要进一步对角点的位置以及边缘方向进行亚像素级精细化处理。

假设c是理想的角点，p是c的局部领域的一个像素点，$g_P$是p点在图像梯度的向量，那么
$$g_p^T(p-c)=0$$

如图所示，中心点绿色表示理想点c，假如图像点p不再边界上，标号1的位置平坦区域梯度$g_p$为零向量，所以：
$$g_p^T(p-c)=0$$

假如像素点p在边界上，标号2的位置，梯度$g_P$向量方向垂直向下，$(p-c)$方向水平向左，两向量方向互相垂直，所以:
$$g_p^T(p-c)=0$$

这是一种在理想情况下的棋盘格，但实际上边缘不可能这样锐利（只有一个像素大小），梯度方向也没有这么理想，最理想的角点c的位置就是我们在角点候选点$c^{\prime }$的领域$N_I(c^{\prime })$内找到满足以下的式子c’:
邻域的像素通过梯度幅值自动加权，上述式子右侧对c’求导并令其等于0，可以得到解析解:
下一步就是refine边缘方向矢量e1,e2，可以通过最小化normals的偏差和对应的梯度实现：

优化能量函数生长棋盘格

定义棋盘格的能量函数如下：

其中第一项E_corners是当前棋盘中角点总数的负值。 第二项E_structure描述了用两个相邻角点来预测第3个角点的匹配程度，分别对棋盘的每行和每列相邻的3个角点（triples）计算其结构能量，取其中的最大值作为该棋盘的结构能量。
值得注意的是，由于结构能量约束中使用的是局域的线性约束，上述棋盘格生长方法可以扩展到鱼眼镜头拍摄的高畸变图像。
计算量和棋盘大小呈现指数关系，当棋盘尺寸较大时，计算量会非常惊人。所以在求解时不能使用穷举法搜索，在此使用的是一种离散优化策略，在实践中证明比较有效。

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

另外，为了在单张图片中生长出多个棋盘格，我们把每个角点都尝试作为种子点用上述方法去生长，这样会产生多个重叠的棋盘格。我们只保留能量函数最小的那个作为最终的结果，其他的重叠部分去掉即可。

应用场景

1. 相机标定 ：libcbdetect 是相机标定过程中常用的工具之一。通过检测图像中的棋盘格图案，可以准确地计算出相机的内参和外参，从而实现对相机的精确标定。这对于机器视觉、摄影测量等领域具有重要意义。
2. 视觉测量与定位 ：除了相机标定外，libcbdetect 还可以用于视觉测量与定位等领域。通过对图像中的特征点进行精确提取和匹配，可以实现高精度的测量和定位功能。这对于工业自动化、机器人导航等领域具有潜在的应用价值。