版權聲明：本文為部落客原創文章，未經部落客允許不得轉載。 https://blog.csdn.net/zhangjunhit/article/details/89173488
Automatic camera and range sensor calibration using a single shot
Robotics and Automation (ICRA), IEEE, 2012: 3936-3943
2012 IEEE International Conference on.
這裡主要介紹一下 Automatic camera and range sensor calibration using a single shot 這篇文獻中的棋盤格特征點檢測算法
參考了 https://blog.csdn.net/electech6/article/details/52770010
大的思路就是基于模闆比對檢測棋盤格角點，首先定義角點的模闆，然後使用模闆和圖像進行卷積得到一個 Corner likelihood 圖 C，将卷積響應較大的位置作為棋盤格角點的候選位置，接着使用了非極大值抑制進行過濾，然後用梯度方向資訊進行二次過濾，具體就是用梯度統計的方法在一個n x n局部鄰域内驗證這些候選點。
下面進行詳細分析
首先來看看這個 Corner likelihood 圖 C 是怎麼得到的？ 它是 模闆和圖像進行卷積得到的。需要先定義角點模闆，這裡我們定義了兩組不同的模闆（兩種角點原型）， two different n × n corner prototypes，主要針對兩種不同情況，
第一種情況就是針對 axis-aligned corners，如下圖所示
我們定義的模闆如下圖所示
第二種情況就是棋盤有旋轉45度的角點，定義的模闆如下圖所示
每種角點原型定義了 四個 filter kernels {A,B,C,D}
Each prototype is composed of four filter kernels {A,B,C,D}, which are convolved with the input image I
從模闆定義圖我們可以看出， A，B是互為對角的， C，D 互為對角，
對應一個棋盤格角點，要麼 A、B 比 C、D 亮，要麼C、D比 A、B 亮。如何将這個特點使用數學公式描述了
上面的 i 表示 prototype類型 s_i_1 ，s_i_2 表示 the likelihood of the two possible flippings for prototype i，即這個 1,2 對應角點翻轉的情況，如下圖所示就是一個翻轉情況， s_i_1 對應下圖左邊的情況，s_i_2 對應下圖右邊情況,i=1（白色為255,黑色為0）
µ 表示 使用一類角點原型 4個濾波器核進行圖像卷積響應 求和平均，類似計算鄰域的均值
每一類角點原型有兩種情況（對應翻轉），一共有兩類角點原型（對應旋轉），一共有四種情況，
圖像每個位置我們不知道是哪種情況，是以将四種情況都計算一遍，然後以響應值最大的作為輸出
是以 c 是求 四種情況中響應最大的那個響應值，
Corner likelihood 圖 C 如下所示
Importantly, note that the above definition leads to a low likelihood c, if any of the four filter kernels responds weakly. This is important for removing as many non-checkerboard style corners as possible from the hypotheses space.
注意： 從上面的定義我們知道，如果4個卷積核響應中任意一個比較弱，那麼就會得到一個較小的 likelihood c，這對于過濾圖像中很多非棋盤格角點的位置很重要。當然這也會導緻一些漏檢問題，因為圖像存在一些畸變、光照等問題，導緻 4個卷積核響應中某一個響應可能比較弱，那麼就會直接過濾掉了。
To produce a list of corner candidates, we apply conservative non-maxima-suppression (with parameters n_nms and τ_nms ) [18] on C
接下來我們在 C 上進行 非極大值抑制，過濾一些噪聲點。
followed by verifying the candidates by their gradient statistics in a local n × n pixel neighborhood,
接着我們在 n × n 鄰域 使用梯度方向統計 進行 角點驗證，對應棋盤格角點，其鄰域梯度方向非零的值基本是兩個值中的一個，對應這個鄰域中的兩條直線，下面就是用方向直方圖将這兩條直線的角度找出來，使用 mean shift 得到 α1 and α2， 對應這兩條直線
We compute a weighted orientation histogram (32 bins) from Sobel filter responses and find the two dominant modes α1 and α2 using mean shift [19]
Based on the edge orientations, we construct a template T for the expected gradient strength ||∇I|| 2
基于上面得到的直線方向，我們建構一個模闆 T，然後用這個 T 和 梯度幅值 ||∇I|| 2 計算 歸一化相關系數 normalized cross-correlation operator
将這個 歸一化相關系數 與 corner likelihood 相乘得到最終的 corner score，使用門檻值過濾，得到最終的 corner candidates
B. Sub-pixel Corner and Orientation Refinement 亞像素角點和方向優化
角點亞像素精确定位有助于相機标定準确度的提升。這裡我們優化角點的位置和方向兩個資訊。這裡的位置和方向優化都是基于方向限制來設計的。
對于角點位置優化來說，假定角點位于 c 點，其鄰域有一個圖像點 p， 其圖像梯度為 g_p， 這個梯度方向應該垂直于 pc 線段的方向，也就是這兩個向量相乘為0 即： g_pT(p-c)=0 ，當p點不是邊緣點，位于平坦區域，那麼其圖像梯度 g_p=0, 還是滿足 g_pT(p-c)=0
在實際中，平坦區域的圖像點的梯度可能不是0，邊緣點的梯度方向不一定完全垂直邊緣直線方向，可以使用下面的最小化來表示
N_I 是一個位于角點候選位置的 局部 11 × 11 的像素區域，上面這個最小化問題有一個解析解：
接下來優化邊緣方向 edge orientation vectors e1 和 e2，we seek to minimize the error in deviation of their normals
with respect to the image gradients，這裡我們最小化 圖像梯度和他們的法線方向的偏差，即梯度方向和法線方向是垂直的
M_i 是鄰域的一些點，這些點位于邊緣直線上，neighboring pixels, which are aligned with the gradient
mi = [cos(αi )sin(αi)]T of mode i
上面最小化問題的解可以通過設定 上式 Lagrangian 的 derivative 為 0，變為一個 eigenvalue problem， ei 對應一個矩陣最小特征值對應的向量，這個矩陣如下所示
棋盤格檢測：
這裡通過檢測到的角點，将屬于同一個棋盤的角點連接配接起來。具體步驟如下：給定一個種子角點，我們沿着它的邊緣方向 e1 和 e2 尋找離它最近的角點，我們得到一個 2 × 2 棋盤區域，以及一個對應的 energy value E(X,Y)，然後我們向四周擴充這個 2 × 2 棋盤區域，具體往哪裡擴充了？ 朝使 E(X,Y) 下降最多的那個方向 擴充。最終我們找到一個棋盤格内左右的小方塊區域。
Given a seed corner, we search for its closest neighbors in the direction of its edges e 1 and e 2 , yielding an initial
2 × 2 checkerboard hypothesis with an associated energy value E(X,Y). To optimize E(X,Y), we propose expansion
moves on Y, which expand any of the checkerboard borders by a single row or column. Amongst all four possibilities,
we select the proposal, which reduces E(X,Y) the most.
Fig. 3(a) illustrates the expansion moves exemplarily
能量函數定義
11