Chamfer Matching 是二维 Shape Matching 的一个经典且常用的方法。

距离变换

距离变换(DT, distance transform, distance function),给定一个有特征点(*)和非特征点(-)组成的二值图像，距离变换就是求得每一个点到最近特征点的距离。如下图：

Chamfer Matching

Chamfer matching 是用来匹配两个边缘图像（edge map），并计算它们之间的二维变换矩阵。

\[ \mathbf H=(\theta, t_x,t_y) \quad \mathbf H \in SE(2) \]

\[ \begin{equation} \hat{\mathbf H}=\arg\min_{\mathbf H\in SE(2)}d_{CM}(\mathbf W(Q;\mathbf H),T) \end{equation} \]

其中\(\mathbf Q={\mathbf q_i},\mathbf T={\mathbf t_i}\)别为待匹配图像及模版图像,\(d_{CM}\)为距离。\(\mathbf W(Q;\mathbf H)\)为变换。

\[ \begin{equation} \mathbf{W}(Q ; \mathbf{H})=\mathbf{H} \cdot Q \end{equation} \]

\[ \begin{equation} d_{C M}(Q, T)=\frac{1}{|Q|} \sum_{\mathbf{q}_i \in Q} \min _{\mathbf{t}_{j} \in T}\left|\mathbf{q}_{\boldsymbol{i}}-\mathbf{t}_{j}\right| \end{equation} \]

Hierarchical Chamfer Matching

章(Borgefors,1988)给出了一种优化的过程。从文章的题目可知，第一步是构建图像金字塔，构建的方法是对原始边缘图进行比例为2的降采样。降采样的方法是在2x2的小块上进行OR，即或运算。这一步得到的叫做边缘金字塔。对边缘金字塔进行距离变换，得到的叫做距离金字塔。

用来构建距离金字塔的图像叫做pre-distance image。带匹配的图像叫做pre-polygon image。在将polygon叠加在DT上之前，可以进行一些变换，这些变换用参数表示，比如平移可以用一对参数(x,y)表示。优化的过程就是按照一定的步长(dx,dy)调整参数，在参数空间的邻近点上寻找局部最优值。比如，调整x，就可以比较f(x+dx),f(x),f(x-dx)获取x的优化方向，如此迭代直至找到局部最优。当参数维度较大时，同时比较参数空间各个维度上的邻近点会导致严重的性能问题。因此，文章采取住个参数调整的方法。

优化的过程从一个较粗的尺度开始，以若干个不同的参数值为起点，分别独立的进行优化。在得到一组局部最优点后，根据一些原则拒绝掉其中的一部分。剩余的局部最优点再次作为起点，在下一个尺度层次上进行优化。

Fast Directional Chamfer Matching (FDCM)

FDCM [3] 将边缘图像中的点转换为线段，而线段的数量远远小于点的数量。此外，FDCM 还在 cost function 中加入了方向信息，因此速度较快。

Reference

[1] Barrow, H. G., Tenenbaum, J. M., Bolles, R. C., & Wolf, H. C. (1977). Parametric correspondence and chamfer matching: Two new techniques for image matching. [2] Borgefors, G. (1986). Distance transformations in digital images. Computer vision, graphics, and image processing, 34(3), 344-371. [3] Borgefors, G. (1988). Hierarchical chamfer matching: A parametric edge matching algorithm. IEEE T-PAMI, 10(6), 849-865. [4] Fast Directional Chamfer Matching https://github.com/CognitiveRobotics/object_tracking_2D/tree/master/3rdparty/Fdcm [5] OpenStreetSLAM: Global Vehicle Localization Using OpenStreetMaps