【图像配准】基于灰度的模板匹配算法（二）：局部灰度值编码

简介：

        在上一篇文章： 基于灰度的模板匹配算法（一）：MAD、SAD、SSD、MSD、NCC、SSDA、SATD算法中，介绍了几种典型的模板匹配算法，但此类算法都存在时间复杂度高，对图像尺寸敏感等问题，即便是SSDA这样的优化算法复杂度也是很高的。

        本文将介绍一种新的算法，叫做局部灰度值编码算法，它通过对灰度值编码来进行粗匹配，再用相位相关法进行精匹配。

算法介绍

粗匹配

        与上一篇文章的假设相似，这里搜索图S尺寸为MxM，模板T的尺寸NxN，模板T在S上滑动搜索，滑动的上、下步长都为N（一个模板尺寸），也就把S分成了若干个T尺寸的子图。如果M不是N的整数倍，那么也不用管S图中的最底部和最右部剩余的几行几列。下面举一个例子来进行阐述。

        搜索图S是一个512x512的lena图像即M=512，模板图T是其中的一个部分，大小为64x64，即N=64。正好将S划分成8x8个相邻且不重合的子图（也称限制块），每个子图（限制块）的尺寸与模板大小一样。接下来我们将要分别对模板和各个限制块进行编码（这就是为什么叫做局部灰度编码），再判断模板与哪个限制块相似度最高，以初步确定模板的位置，这就是粗匹配。

局部灰度编码

       编码是通过定义KxK大小的R块来进行（这里分块有点多，画画图就一目了然了）。以对模板T编码为例，此处取R块的大小8x8，即K=8。此时就将T划分成了HxH个R块，此处H=8，求每个R块内部的像素和。

说明：R块的尺寸根据情况而定，也可以是....，9x9，10x10...，如果N不是K的整数倍，处理同上。总之分的R块越小对图像的描述就越精确，同样计算量也越大。

以某个R块为中心及其8-邻域的R块，如下图所示。以相邻的2x2的R块当做一个D块（如：D1=R1 U R2 U R4 U R5）。

        实际上，只有划斜线的阴影部分才能编码，图像外围一圈的R块都不能。接下来对每个D块进行编码。以D1为例，S(R1)表示R1块内部所有像素之和，对D1块所包含的4个R块的S(R)进行排序（升序、降序都行，选定一种）。例如取顺时针方向规定R1-R2-R5-R4的顺序为1-2-3-4。但以S(R)进行排序的话，共有24种排列组合方法（如下图左表），转化成二进制表示（如下图右表）。假如S(R)的排序结果为3-1-4-2，那么这个D块的特征编码就为01101。（左、右表及方向，都可以自己定义）

       以此类推，4个D块就有4个5bit二进制编码，将它们做位拼接串起来，形成一个20位的二进制编码，这个20位的编码就当做中心R块（R5）的特征编码。【实际上，只有划斜线的阴影部分才能编码，图像外围一圈的R块都不能。】

特征描述符

        综上所述，一个可以划分成HxH个R块的模板，有个20bit的二进制描述符，把这个20bit的特征转化成一个十进制数，那么同理就有个十进制数，将其行列排列成一个一维向量，这就是模板图的特征向量了。上述中，模板图就有(8-2)x(8-2)=36维特征向量。

        同理，对每一个子图（限制块）进行同样的编码操作，提取每个子图（限制块）的特征向量，将模板特征与子图特征逐一比较，求相似度最高的子图，这就完成了粗匹配。

——————————————————————————————分割线————————————————————————————————

精匹配

        由于粗匹配的子图选取时按照一定的步长进行的，通过粗匹配找到相似度最高的子图，与模板有重合的部分但并不是完全重叠的，会存在一定的偏差。这就需要进一步确定这个偏差。下面利用相位相关法进行精匹配。

相位相关法

        根据二维傅里叶变换的性质：空域上的平移等价于频域相位的平移。两幅图的平移矢量可以通过他们的互功率谱的相位直接计算。假设额图像与的平移关系为：

相应的二维傅里叶变换关系应为：

定义它们的归一化互功率谱为：

其中：表示的复数共轭。

        对上述归一化互功率谱等式左右两边进行二维傅里叶逆变换，右边逆变换可得到在空间位置(x0,y0)处形成的一个脉冲函数。所以我们只需要左边式子进行逆变换，再寻找脉冲位置（即峰值），峰值的位置(x0,y0)就是偏移矢量。

精匹配实现

MATLAB代码

%//***************************************** 
%//Copyright (c) 2015 Jingshuang Hu 

%//@filename:demo.cpp 
%//@datetime:2015.08.20 
%//@author:HJS 
%//@e-mail:[e-mail] 
%//@blog:http://blog.csdn.net/hujingshuang 
%//*****************************************
%%
%//相位相关法
clear all;
close all;
%%
img=rgb2gray(imread('lena.jpg'));%//载入图像
dl=64;%//模板大小64x64
x0=200;y0=200;%//起点
dx0=20;dy0=30;%//偏移量（不超过模板尺寸）
f1=img(x0:x0+dl-1,y0:y0+dl-1);%//截取一个图当做模板
f2=img(x0+dx0:x0+dx0+dl-1,y0+dy0:y0+dy0+dl-1);%//截取一个图当做粗匹配找到的子图
[m n]=size(f1);%//m行n列
F1=fft2(f1,m,n);%//傅里叶变换
F2=fft2(f2,m,n);
%//FC1=conj(F1);%//共轭
FC2=conj(F2);%//共轭
delta=abs(ifft2((F1.*FC2)./abs(F1.*FC2)));
figure;surf(1:dl,1:dl,delta);shading interp;
max_delat=max(max(delta));
[dx dy]=find(delta==max_delat);
dx=dx-1;dy=dy-1;

相位相关峰值图

输出结果：

          可以看到，这跟代码中设定的偏移量是一致的，说明我们得到了正确的计算结果。此时，我们在粗匹配的子图位置基础上平移(dx,dy)，再取模板NxN的子图，这个子图就是最终的匹配结果。

          素材及代码下载：http://download.csdn.net/detail/hujingshuang/9029593

——————————————————————————————分割线————————————————————————————————

参考文献：

1、李强,张钹. 一种基于图像灰度的快速匹配算法[J],软件学报, 2006,17(2), 216-222.

2、冯宇平,赵文仓. 基于局部灰度值编码的图像匹配[J], 青岛科技大学学报(自然科学版),2011,32(4),435-440.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------补刀--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

        今天正好是农历七月初七，空间，微信好多人都在秀玫瑰、秀恩爱；别人浪漫相约，我在实验室敲代码；别人花前月下，我在实验室敲代码。所以走远点，不要问我爱你有多深，我要敲代码。【生活照】