接着上一篇基于生长的棋盘格角点检测方法–（2）代码详解（上），来看一下第二个重要函数chessboardsFromCorners。
该函数的目的是用上一步骤中找到的角点恢复出棋盘结构。首先初始化一个3x3的角点矩阵，也就是一个 2x2的棋盘格，这是组成一个棋盘的最小单位了。然后利用定义的棋盘能量函数来从4个外沿生长棋盘格，取其中能量最小（最可能是棋盘）的方向作为新的棋盘，以此类推，最后得到一个最优化的棋盘格阵列。
该函数的主要结构：
chessboards = chessboardsFromCorners(corners);
chessboard = initChessboard(corners,i);
energy = chessboardEnergy(chessboard,corners)
proposal{j} = growChessboard(chessboard,corners,j);
pred = predictCorners(p1,p2,p3)
idx = assignClosestCorners(cand,pred);initChessboard
初始化一个3x3的chessboard为0，选取第idx个Corner，其两个主梯度方向为v1,v2,将该Corner作为chessboard的初始中心。如下图
然后以此角点为中心，按照两个主梯度方向寻找最近的邻居角点。
directionalNeighbor
function [neighbor_idx,min_dist] = directionalNeighbor(idx,v,chessboard,corners)其中，v是归一化方向向量。该函数计算当前点和其他所有点的距离向量dir、其他点在该点主方向上的投影距离dist。
dir = corners.p(unused,:) - ones(length(unused),1)*corners.p(idx,:);
dist = (dir(:,1)*v(1)+dir(:,2)*v(2));参考下图看一下其中一些重要参数的物理意义：
dist*v 表示其他点在该点梯度向量方向上的投影向量。
dist_edge表示其他点到该点梯度向量v方向的垂直距离。
dist_point(dist_point<0) = inf;表示其他点和该点的方向夹角大于90度，点乘为负的情况下认为是无穷远。
dist_edge为对应点到棋盘中心点边缘方向的垂直距离。
dist为投影距离，考虑到我们希望寻找对应v方向的最近点，因此对dist_edge的值进行一个放大。代码中进行了5倍的放大，如下：
[min_dist,min_idx] = min(dist_point+5*dist_edge);
neighbor_idx = unused(min_idx);寻找米字形的3x3九宫格（上、下、左、右、左上、左下、右上、右下）内所有点最近的邻居。代码如下
% find left/right/top/bottom neighbors
[chessboard(2,3),dist1(1)] = directionalNeighbor(idx,+v1,chessboard,corners);
[chessboard(2,1),dist1(2)] = directionalNeighbor(idx,-v1,chessboard,corners);
[chessboard(3,2),dist2(1)] = directionalNeighbor(idx,+v2,chessboard,corners);
[chessboard(1,2),dist2(2)] = directionalNeighbor(idx,-v2,chessboard,corners);
% find top-left/top-right/bottom-left/bottom-right neighbors
[chessboard(1,1),dist2(3)] = directionalNeighbor(chessboard(2,1),-v2,chessboard,corners);
[chessboard(3,1),dist2(4)] = directionalNeighbor(chessboard(2,1),+v2,chessboard,corners);
[chessboard(1,3),dist2(5)] = directionalNeighbor(chessboard(2,3),-v2,chessboard,corners);
[chessboard(3,3),dist2(6)] = directionalNeighbor(chessboard(2,3),+v2,chessboard,corners);下面验证找到的棋盘格是否符合自定义的棋盘标准，在此有一个概念叫标准离差率。标准离差率＝标准离差/期望值。
这里的阈值0.3应该是经过多次实验仔细选取的。如果选取偏大会降低棋盘的约束条件，容易引人假棋盘；如果选取偏小，约束条件过于严格，生成的棋盘格数会较少。代码如下
if any(isinf(dist1)) || any(isinf(dist2)) || ...
std(dist1)/mean(dist1)>0.3 || std(dist2)/mean(dist2)>0.3
chessboard = [];
return;
end然后对生成的所谓的3x3初始化棋盘格进一步验证，要保证不是空的，并且棋盘能量值大于0。下面是很重要的函数，计算棋盘能量。
chessboardEnergy
棋盘总能量定义：
其中第一项E_corners是当前棋盘角点总数的负值，表达式和代码如下：
E_corners = -size(chessboard,1)*size(chessboard,2);E_structure描述了两个相邻Corner和预测Corner的匹配程度，分别对chessboard的每行和每列相邻的3个Corner计算其结构能量，取其中的最大值。其表达式为：
代码如下
% walk through rows
for j=1:size(chessboard,1)
for k=1:size(chessboard,2)-2
x = corners.p(chessboard(j,k:k+2),:);
E_structure = max(E_structure,norm(x(1,:)+x(3,:)-2*x(2,:))/norm(x(1,:)-x(3,:)));
end
end
% walk through columns
for j=1:size(chessboard,2)
for k=1:size(chessboard,1)-2
x = corners.p(chessboard(k:k+2,j),:);
E_structure = max(E_structure,norm(x(1,:)+x(3,:)-2*x(2,:))/norm(x(1,:)-x(3,:)));
end
end最终的棋盘能量为
E = E_corners + 1*size(chessboard,1)*size(chessboard,2)*E_structure;所以要满足总能量E要大于0，也就是每3个相邻点的E_structure中最大值要小于1
下面我画了个图来解释一下棋盘结构能量约束E_structure的含义。如下图：
- 上图中上面是理想棋盘的情况（为方便描述称为case1），下面是有畸变的棋盘的情况（为方便描述称为case2）。p1,p2,p3是得到的棋盘格内3个相邻的角点坐标。对应代码中的x(1,:), x(2,:), x(3,:),
- 结构能量分子norm(x(1,:)+x(3,:)-2*x(2,:))其中x(1,:)+x(3,:)-2*x(2,:)可以分开写为[x(1,:) -x(2,:)] + [x(3,:)-x(2,:)]也就是图中的[p1-p2]+[p3-p2]。
- 结构能量分母norm(x(1,:)-x(3,:))，也就是norm(p1-p3)。
- Case1中：结构能量分子[p1-p2]和[p3-p2]大小相等，方向相反，其和的2范数（norm）结果为0，所以结构能量也为0。
- Case2中：p4是p1,p2,p3所构成的平行四边形的第4个顶角，是虚构出来的，不在棋盘格出现，只作为分析用。结构能量分子[p1-p2]+[p3-p2]对应图中的向量v2, 结构能量分母p1-p3对应图中的向量v1。前面所述的E_structure中最大值为1的情况就是向量v1,v2的2范数相等。这样平行四边形p1,p2,p3，p4其实就升级变成了矩形。这是结构约束里的畸变极限了，此时E_structure中值为1。
至此，已经完成了棋盘格的初始化种子（尺寸2x2棋盘格，也就是3x3角点）。
growChessboard
如果顺利通过前面的一系列测试，下一步就要升级打怪模式了，进入棋盘格生长阶段。棋盘格每次生长都分别从上下左右四个方向整行或整列地生长，计算生长后的新棋盘的能量，选择其中能量最小的那个生长方向作为新的棋盘。首先需要在已有棋盘的周围来预测可能的角点位置：
predictCorners
预测角点的思想很直观，就是根据已知3个相邻角点的角度差和长度差的增量来预测下一个相邻角点出现的位置，然后打个折，代码里打的是75折。这个参数的选取应该也是多次实验结果，我做了实验，它对于畸变较大的图像比较敏感。
pred = p3 + 0.75*s3*ones(1,2) .* [cos(a3) sin(a3)];我举个例子就很明白了，如下图，蓝色是初始的棋盘格中的角点。我们向棋盘格右侧的最外沿预测出延展的3个点的结果如下图绿色点。红色点是其余的检测出来的角点。下一步就是根据预测点的位置，来寻找离他们最近的角点。
assignClosestCorners
寻找到离pred最近的Corner，使用贪心算法查找距离最近的角点。代码如下
for i=1:size(pred,1)
[row,col] = find(D==min(D(:)),1,'first');
idx(col) = row;
D(row,:) = inf;
D(:,col) = inf;
End分别从4个方向去生长棋盘格，生成4个新的棋盘格proposal。如果其中能量最小的那个棋盘格的能量值比棋盘格扩展前的能量更减少了，就说明生长成功，用这个新的棋盘格代替原来棋盘格。继续生长，直到4个方向新棋盘格能量不再减少为止。代码如下:
% compute proposals and energies
for j=1:4
proposal{j} = growChessboard(chessboard,corners,j);
p_energy(j) = chessboardEnergy(proposal{j},corners);
end
% find best proposal
[min_val,min_idx] = min(p_energy);
% accept best proposal, if energy is reduced
if p_energy(min_idx)<energy
chessboard = proposal{min_idx};下面检查新生成的棋盘是否和原有的棋盘有重复，如果有重复就用overlap标记一下，第一列表示重复的棋盘编号，第2列表示对应的能量值。代码如下
% check if new chessboard proposal overlaps with existing chessboards
overlap = zeros(length(chessboards),2);
for j=1:length(chessboards)
for k=1:length(chessboards{j}(:))
if any(chessboards{j}(k)==chessboard(:))
overlap(j,1) = 1;
overlap(j,2) = chessboardEnergy(chessboards{j},corners);
break;
end
end
end如果新棋盘能量比现有的棋盘能量小，那么删掉重复的棋盘，用能量更小的棋盘代替
% add chessboard (and replace overlapping if neccessary)
if ~any(overlap(:,1))
chessboards{end+1} = chessboard;
else
idx = find(overlap(:,1)==1);
if ~any(overlap(idx,2)<=chessboardEnergy(chessboard,corners))
chessboards(idx) = [];
chessboards{end+1} = chessboard;
end
end最后生长出的棋盘格结果如下图:
上面举例的棋盘主要是为了表现在自然环境中抗干扰的效果。下面给出几个在鱼眼镜头下图像畸变较大时的棋盘格检测效果。从结果来看，效果很不错，见下图：
但是这种方法也有其缺点，因为它是受限于棋盘格的约束，所以当棋盘被部分遮挡时，检测结果就不尽如人意。如下图。
算法找到的棋盘格是在其约束条件下最好的结果。但是上图左下方的棋盘因为是次优的所以被忽略掉。这在鱼眼相机标定中非常不利。因为鱼眼镜头越靠近边缘畸变越大，越难以被检测到，但是却对计算标定参数越重要。以后有机会我在介绍其他的棋盘格角点检测方法，可以解决这个问题。
参考资料
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.
2、http://www.cvlibs.net/software/libcbdetect/