基于距离变换的图像匹配图像处理

之前一直以为距离变换的意义就在于骨架抽取，看到一篇论文用距离变换的方式来实现匹配，配合倒角距离变换（Chamfer Distance Transform）可以达到快速匹配的效果。
距离变换通俗的说，距离变换就是对于一幅二值图像的每个前景点（255），计算与其最近的背景点的距离，根据距离生成一幅灰度图（图1-1b），可以看到，距离变换有骨架抽取的效果。

文章图片

图1-1. 距离变换
可以想象，挨个对每个前景点计算其最近的距离是很耗时的，因此距离变换算法使用模板来加速：
对于3x3的模板（表1-1）

…	…	…
q2	q3	q4
q1	p	q5
q8	q7	q6

1）按从上到下，从左到右的顺序，计算每个前景点的最小距离（背景点直接赋0）

?????????????d0=f(p)d1=f(q1)+dist(q1,p)d2=f(q2)+dist(q2,p)d3=f(q3)+dist(q3,p)d4=f(q4)+dist(q4,p)
f(p)=MIN(d0,d1,d2,d3,d4)
2）按从下到上，从右到左的顺序，再次计算距离

?????????????d0=f(p)d5=f(q5)+dist(q5,p)d6=f(q6)+dist(q6,p)d7=f(q7)+dist(q7,p)d8=f(q8)+dist(q8,p)
f(p)=MIN(d0,d5,d6,d7,d8)即为所求。
【基于距离变换的图像匹配】在这里，距离的计算有不同的方法：欧式距离、街区距离、棋盘距离、倒角距离。其中欧式距离最精确但计算量也最大，这里有各个距离的耗时对比，可以看到，倒角距离确实最快。
基于距离变换的匹配也是模板匹配的流程，但特征变了
1）求模板图的距离变换，统计模板图前景点个数 Na
2）在待匹配图中滑动窗口，遍历其前景点，累加相应位置模板距离变换图的值 D
计算当前窗口匹配值 Pmatch
Pmatch=D+|Na?Nb|Na+Nb
其中 Nb是待匹配窗口的前景数
分析博文给出的代码，发现其距离变换有点不同：
对于前景点，直接赋0，个数加1
对于背景点，计算其8邻域加权值为距离

//如果该点是边缘点 dist=0； if (piexl ==255) { pTDist[(i-1) *nTwidth + (j-1)] =0; Nb++; } else { //否则看8邻域膨化加权 u11 = *(pTdata + (i-1)*(nTwidthstep+2)+j-1); u12 = *(pTdata +(i-1)*(nTwidthstep+2)+j); u13 =*(pTdata +(i-1)*(nTwidthstep+2)+j+1); u21 =*(pTdata +i*(nTwidthstep+2)+j-1); u23 =*(pTdata +i*(nTwidthstep+2)+j+1); u31 =*(pTdata + (i+1)*(nTwidthstep+2)+j-1); u32 =*(pTdata +(i+1)*(nTwidthstep+2)+j); u33 =*(pTdata +(i+1)*(nTwidthstep+2)+j+1); if (u12==255 ||u21==255 ||u23==255 ||u32==255) pTDist[(i-1) *nTwidth + (j-1)] =0.3; else if(u11==255 || u13==255 ||u31==255 ||u33==255) pTDist[(i-1) *nTwidth + (j-1)] =0.7; else pTDist[(i-1) *nTwidth + (j-1)] =1; }

这样对于待匹配图的前景点，如果在模板图里不是前景点，其累加值会增加。
图1-1c是用d在a里匹配的结果，可以看到，匹配是成功的。但实际匹配速度没有想象的那么美好，而且很显然，这种方法对旋转、缩放是无效的。