浅谈基于NCC的图像匹配快速算法
发布时间：2015-07-01 16:33
摘 要: 在图像匹配过程中,针对传统归一化积相关(ncc)算法计算量大的问题,提出一种对ncc进行改进的图像匹配快速算法。该算法首先使用差分求和定理改造ncc相似度量函数,以降低匹配计算量。然后提出模板区域分割,设定阈值,进一步去除大量不必要的计算,优化匹配搜索过程,实现了快速匹配。实验结果证明,与传统的匹配算法相比,在保证精度的前提下,计算复杂度大大降低。关键词:图像匹配; 归一化积相关; 相似度函数; 区域分割; 差分
fast algorithm for image matching based onncc
yang tong-yu, peng guo-hua
(school of science,northwestern polytechnical university,xi’an 710129, china)
abstract: in the image matching process, the computational complexity was the major problem of the traditional ncc (normalized product correlation) algorithm. an image matching fast algorithm for improving the ncc is presented. first, it combined with the summation theorem of difference to improve the ncc for reducing the amount of calculation of matching. second, it showed region segmentation for the template and then set threshold to get rid of some calculation to achieve rapid matching. the experimental results prove that the computational complexity is reduced greatly compared with the traditional matching algorithm by the premise of the precision,.
keywords: image matching; normalized product correlation; similarity function; region segmentation; difference
0 引 言
图像匹配问题是计算机视觉、图像处理领域中的基本问题,有两种对应的模型:一是两幅(或者多幅)来自不同传感器、不同视角或不同时间的图像需找出对应关系,经过匹配步骤可得出两幅图像的差别所在,为下一步处理作基础;二是根据已知的图像模式在另一幅图像中搜索类似模板的目标,即模板匹配。图像匹配技术是数字图像处理领域的一项重要研究,已在虚拟现实场景、航空航天遥感测量、医学影像分析、光学和雷达跟踪、景物制导等领域有着重要的应用价值。已有的图像匹配算法可分为两类:基于像素灰度值的匹配和基于图像几何特征的匹配。
所有的基于像素灰度值匹配算法的计算量等于模板运算量和搜索位置数之积。故提高匹配速度的角度有:
(1) 减少每个位置处模板相似度计算的运算量;
(2) 改变搜索策略,减少搜索像素点或在搜索图像中的搜索位置数。模板匹配的传统算法[1]有:mad[2](平均绝对差)算法,归一化积相关[3-5](ncc)算法,序贯相似性检测法[6](ssda),图像灰度值编码[7](pfc)算法等。其中mad算法计算过程非常简单,无需复杂的乘除法运算,但是对噪声比较敏感,在加噪声的情况下,匹配准确率随着信噪比的增加而减少; ssda算法虽然相对mad算法速度提高了很多,但是其精度低,匹配效果不好,而且易受噪声影响,一旦进入信息贫乏的区域,会导致误匹配率的上升;pfc算法无法适应图像局部光照的非线性变化,匹配容易错误;ncc算法的优点是抗白噪声干扰能力强,且在灰度变化及几何畸变不大的情况下精度很高,它的这种优点非常突出,但该方法受局部光照变化的影响,且匹配速度较慢。针对该问题,本文在保证匹配精度的前提下,提高ncc匹配算法的速度,增强算法对实际应用的适应性。
文献[8]提出的ncc快速模板匹配算法,结合文献[9]的差分求和定理对每个位置处的模板计算进行改进,减少了计算量。本文在文献[8]的基础上,从上面所述的角度(2),改变搜索策略,即提出模板分块匹配策略,减少不必要的运算,进一步优化算法。该算法能适应一定光照的变化,适合任何形状的匹配模型,相对于文献[8]的匹配算法大大提高了速度。
1 ncc匹配
1.1 ncc原理
ncc匹配算法是一种经典的匹配算法。通过计算模板图像和搜索图像的互相关值确定匹配的程度。互相关值最大时的位置决定了模板图像在搜索图像中的位置。假设搜索图像s的尺寸为m×m,模板t的尺寸为n×n,其中m>n,m,n代表图像像素大小。
模板t在图像s上平移,模板所覆盖的子图记作si,j,(i,j)为子图左上角顶点在搜索图s中的坐标。在实际匹配应用中,搜索图和模板的相似性通过度量函数来度量,则归一化积相关匹配度量定义为:
r(i,j)=∑mm=1∑nn=1si,j(m,n)t∑mm=1∑nn=1[si,j(m,n)-si,j]2×∑mm=1∑nn=1[t(m,n)-t]2(1)
ncc算法具有很高的准确性、适应性, 对图像灰度值线性变换具有“免疫性”, 即所求的ncc值不受灰度值的线性变换的影响, 但计算耗费过于庞大,导致匹配效率低,所以需要一种新的快速的匹配算法。
1.2 改进ncc
1.2.1 差分求和定理
文献[9]中提出差分求和定理,即设有两个大小同为n的一维数组f(x) 和g(x),x= 1,2,…,k,则这两个数组的乘积等于将其中一个数组f(x)差分,另一个数组g(x)累进求和后的乘积,即:
∑kx=1f(x)g(x)=∑kx=1f(x)g(x)(2)
式中:
f(x)=f(x)-f(x+1)(3)
g(x)=g(x-1)-g(x+1)(4)
g(0)=0(5)
f(k+1)=0(6)
1.2.2 改进ncc算法
将上述差分求和定理用于式(1)。t(m,n)为模板上(m,n)位置点的像素值,其中0≤m≤n,0≤n≤n,将模板内的所有点保存为一维数组f(x),子图内对应模板的点保存为g(x)。令f(x)为对f(x)的差分数组,即f(x)=f(x)-f(x+1),并根据式(5)对子图g(x)累进求和得数组g(x)。
这样就可以把模板t和子图si,j的乘积根据式(3)转化为对f(x)和g(x)的乘积运算。由于在灰度变化不大的图像中,相邻像素的灰度值非常相近,这样差分后的数组会产生大量的0,1或-1,而0,1,-1的乘法运算可以忽略。
在实际的模板匹配中,模板是固定的,故对其进行差分的运算只需进行1次,耗时很少。此外,在模板中相邻像素间同样存在大量的相同像素值,差分后可得到大量0,1和-1,从而大大地提高了匹配速度。
2 区域分割进一步改进
第1.2节为文献[8]从引言中提到的角度(1),即从减少每个位置处模板相似度计算的运算量对ncc算法进行改进,效率有了很大程度的提高;下面本文针对角度(2),即通过改变搜索策略减少像素数量,来进一步提高匹配效率。本文提出区域分割的方法,也即模板分块匹配,通过设定阈值,对分割后的小区域进行计算、比较,排除掉大量不符合要求的点,从而进一步提高匹配速度。区域分割法是用如图1所示的分割图来代替原来的模板,通过计算r1~r4四个小矩形的相关性来判断匹配区域的位置。
图1 分割模板
具体实现步骤如下:
(1)设定一个常数为最大相似性度量max r=0.98,其中r为相关系数。
(2) 在搜索图上,采用上述改进的ncc匹配算法,计算模板块r1的相似度。如果r1的相似度小于max r,完成本步骤后转步骤(6);否则转步骤(3)。
(3)计算模板块r2的相似度。如果r2相似度小于max r,完成本步骤后转步骤(6);否则转步骤(4)。
(4) 计算模板块r3的相似度。如果r3相似度小于max r,完成本步骤后转步骤(6);否则转步骤(5)。
(5)计算模板块r4的相似度。如果r4相似度也大于max r,即找到匹配目标。否则, 在完成本步骤后转步骤(6)。
(6)结束。
实验结果证明, 在保证图像质量的前提下, 通过模板分块, 减少了匹配时间, 准确地找到匹配的目标。该搜索策略能够大大提高匹配速度, 同时不影响图像质量, 较好地解决了匹配质量与运算量之间的矛盾。
3 实验结果与分析
实验运行环境为2.40 ghz intel处理器,4 gb内存,visual c++ 6.0。采用448×434的lena图像(如图2(a)所示)做搜索图,从搜索图上任意位置取一块子图作为模板(如图2(b),(c)所示),分别用传统的ncc算法,本文改进的快速算法进行模板匹配,运算结果如表1所示。
图2 匹配图像
从表1数据分析可得到结论:本文算法在保证精度的前提下,时间远远小于传统算法。如表2所示,在灰度模板的情况下,同样一副图像,模板尺寸越大,则进行模板匹配运算的量也越大。特别,当模板较大时更突显本文算法的优势。
表1 两种算法的结果比较
算法模板图像时间 /s 检测位置
本文算法57×48448×4340.250(201,198)
传统算法57×48448×43413.224(201,198)
当模板变小时,两者的时间都在骤减,但即使是在模板为10×10时,本文算法时间仍然远小于传统算法。当搜索图和模板图皆为二值图时,本文算法匹配速度更加快,传统算法跟图像类型无关,只和大小有关。故对于越简单,灰度值变换范围越小的图像,本文算法越快,更能突显其优势。
4 结 语
本文通过采用模板分块匹配策略对文献[8]中经典的ncc算法进行了进一步改进,提出基于ncc的图像匹配快速算法。在保持原有的高精度的前提下,相对于文献[8]中的算法,速度上有了很大的提高;实时性强,可用于图像实时处理。但由于文献[8]的ncc算法局限于灰度变化不大的图像,使适用范围受到了一定的限制,在这方面可以做进一步的研究。另外,在图像处理领域采用进行并行处理[10]是一个很好的切入点。
表2 不同类型图像两种算法的比较结果
模板类型模板大小本文算法 /s传统算法 /s准确率
灰度模板
80×800.95421.235100%
57×480.25013.224100%
10×100.1079.621100%
二值模板
80×800.58721.554100%
57×480.13612.894100%
10×100.0759.541100%
参考文献
[1]刘宝生.几种经典相似性度量的比较研究[j].计算机应用研究,2006(11):1-3.
[2]李俊山,沈绪榜.图像分块平均绝对差匹配并行算法[j].小型微型计算机系统,2002,23(6):695-698.
[3]孙祖鑫,吴强.一种基于ts201的归一化互相关快速算法[j].计算机应用技术,2010(11):125-127.
[4]韩冰,王永明,刘杨,等.一种基于积分图像的快速归一化积相关算法[j].弹箭与制导学报,2009,29(5):283-286.
[5]郭伟,赵亦工,谢振华. 一种改进的红外图像归一化互相关匹配算法[j].光子学报,2009,38(1):189-193.
[6]王立新,刘彤宇,李阳.ssda图像匹配算法的研究及实现[j].光电技术应用,2005,20(3):53-55.
[7]李强,张钹.一种基于图像灰度的快速匹配算法[j].软件学报,2006,17(2):217-222.
[8]刘锦峰.图像模板匹配快速算法研究[d].长沙:中南大学,2007.
[9]王冰.基于差分矩因子的灰度图像矩快速算法[j].计算机学报,2005,28(8):1367-1375.
[10]李俊山.归一化积相关图像匹配算法中的图像分块并行处理方法[j].小型微型计算统,2004,25(11):1986-1989.
fast algorithm for image matching based onncc
yang tong-yu, peng guo-hua
(school of science,northwestern polytechnical university,xi’an 710129, china)
abstract: in the image matching process, the computational complexity was the major problem of the traditional ncc (normalized product correlation) algorithm. an image matching fast algorithm for improving the ncc is presented. first, it combined with the summation theorem of difference to improve the ncc for reducing the amount of calculation of matching. second, it showed region segmentation for the template and then set threshold to get rid of some calculation to achieve rapid matching. the experimental results prove that the computational complexity is reduced greatly compared with the traditional matching algorithm by the premise of the precision,.
keywords: image matching; normalized product correlation; similarity function; region segmentation; difference
0 引 言
图像匹配问题是计算机视觉、图像处理领域中的基本问题,有两种对应的模型:一是两幅(或者多幅)来自不同传感器、不同视角或不同时间的图像需找出对应关系,经过匹配步骤可得出两幅图像的差别所在,为下一步处理作基础;二是根据已知的图像模式在另一幅图像中搜索类似模板的目标,即模板匹配。图像匹配技术是数字图像处理领域的一项重要研究,已在虚拟现实场景、航空航天遥感测量、医学影像分析、光学和雷达跟踪、景物制导等领域有着重要的应用价值。已有的图像匹配算法可分为两类:基于像素灰度值的匹配和基于图像几何特征的匹配。
所有的基于像素灰度值匹配算法的计算量等于模板运算量和搜索位置数之积。故提高匹配速度的角度有:
(1) 减少每个位置处模板相似度计算的运算量;
(2) 改变搜索策略,减少搜索像素点或在搜索图像中的搜索位置数。模板匹配的传统算法[1]有:mad[2](平均绝对差)算法,归一化积相关[3-5](ncc)算法,序贯相似性检测法[6](ssda),图像灰度值编码[7](pfc)算法等。其中mad算法计算过程非常简单,无需复杂的乘除法运算,但是对噪声比较敏感,在加噪声的情况下,匹配准确率随着信噪比的增加而减少; ssda算法虽然相对mad算法速度提高了很多,但是其精度低,匹配效果不好,而且易受噪声影响,一旦进入信息贫乏的区域,会导致误匹配率的上升;pfc算法无法适应图像局部光照的非线性变化,匹配容易错误;ncc算法的优点是抗白噪声干扰能力强,且在灰度变化及几何畸变不大的情况下精度很高,它的这种优点非常突出,但该方法受局部光照变化的影响,且匹配速度较慢。针对该问题,本文在保证匹配精度的前提下,提高ncc匹配算法的速度,增强算法对实际应用的适应性。
文献[8]提出的ncc快速模板匹配算法,结合文献[9]的差分求和定理对每个位置处的模板计算进行改进,减少了计算量。本文在文献[8]的基础上,从上面所述的角度(2),改变搜索策略,即提出模板分块匹配策略,减少不必要的运算,进一步优化算法。该算法能适应一定光照的变化,适合任何形状的匹配模型,相对于文献[8]的匹配算法大大提高了速度。
1 ncc匹配
1.1 ncc原理
ncc匹配算法是一种经典的匹配算法。通过计算模板图像和搜索图像的互相关值确定匹配的程度。互相关值最大时的位置决定了模板图像在搜索图像中的位置。假设搜索图像s的尺寸为m×m,模板t的尺寸为n×n,其中m>n,m,n代表图像像素大小。
模板t在图像s上平移,模板所覆盖的子图记作si,j,(i,j)为子图左上角顶点在搜索图s中的坐标。在实际匹配应用中,搜索图和模板的相似性通过度量函数来度量,则归一化积相关匹配度量定义为:
r(i,j)=∑mm=1∑nn=1si,j(m,n)t∑mm=1∑nn=1[si,j(m,n)-si,j]2×∑mm=1∑nn=1[t(m,n)-t]2(1)
ncc算法具有很高的准确性、适应性, 对图像灰度值线性变换具有“免疫性”, 即所求的ncc值不受灰度值的线性变换的影响, 但计算耗费过于庞大,导致匹配效率低,所以需要一种新的快速的匹配算法。
1.2.1 差分求和定理
文献[9]中提出差分求和定理,即设有两个大小同为n的一维数组f(x) 和g(x),x= 1,2,…,k,则这两个数组的乘积等于将其中一个数组f(x)差分,另一个数组g(x)累进求和后的乘积,即:
∑kx=1f(x)g(x)=∑kx=1f(x)g(x)(2)
式中:
f(x)=f(x)-f(x+1)(3)
g(x)=g(x-1)-g(x+1)(4)
g(0)=0(5)
f(k+1)=0(6)
1.2.2 改进ncc算法
将上述差分求和定理用于式(1)。t(m,n)为模板上(m,n)位置点的像素值,其中0≤m≤n,0≤n≤n,将模板内的所有点保存为一维数组f(x),子图内对应模板的点保存为g(x)。令f(x)为对f(x)的差分数组,即f(x)=f(x)-f(x+1),并根据式(5)对子图g(x)累进求和得数组g(x)。
这样就可以把模板t和子图si,j的乘积根据式(3)转化为对f(x)和g(x)的乘积运算。由于在灰度变化不大的图像中,相邻像素的灰度值非常相近,这样差分后的数组会产生大量的0,1或-1,而0,1,-1的乘法运算可以忽略。
在实际的模板匹配中,模板是固定的,故对其进行差分的运算只需进行1次,耗时很少。此外,在模板中相邻像素间同样存在大量的相同像素值,差分后可得到大量0,1和-1,从而大大地提高了匹配速度。
2 区域分割进一步改进
第1.2节为文献[8]从引言中提到的角度(1),即从减少每个位置处模板相似度计算的运算量对ncc算法进行改进,效率有了很大程度的提高;下面本文针对角度(2),即通过改变搜索策略减少像素数量,来进一步提高匹配效率。本文提出区域分割的方法,也即模板分块匹配,通过设定阈值,对分割后的小区域进行计算、比较,排除掉大量不符合要求的点,从而进一步提高匹配速度。区域分割法是用如图1所示的分割图来代替原来的模板,通过计算r1~r4四个小矩形的相关性来判断匹配区域的位置。
图1 分割模板
具体实现步骤如下:
(1)设定一个常数为最大相似性度量max r=0.98,其中r为相关系数。
(2) 在搜索图上,采用上述改进的ncc匹配算法,计算模板块r1的相似度。如果r1的相似度小于max r,完成本步骤后转步骤(6);否则转步骤(3)。
(3)计算模板块r2的相似度。如果r2相似度小于max r,完成本步骤后转步骤(6);否则转步骤(4)。
(4) 计算模板块r3的相似度。如果r3相似度小于max r,完成本步骤后转步骤(6);否则转步骤(5)。
(5)计算模板块r4的相似度。如果r4相似度也大于max r,即找到匹配目标。否则, 在完成本步骤后转步骤(6)。
(6)结束。
实验结果证明, 在保证图像质量的前提下, 通过模板分块, 减少了匹配时间, 准确地找到匹配的目标。该搜索策略能够大大提高匹配速度, 同时不影响图像质量, 较好地解决了匹配质量与运算量之间的矛盾。
3 实验结果与分析
实验运行环境为2.40 ghz intel处理器,4 gb内存,visual c++ 6.0。采用448×434的lena图像(如图2(a)所示)做搜索图,从搜索图上任意位置取一块子图作为模板(如图2(b),(c)所示),分别用传统的ncc算法,本文改进的快速算法进行模板匹配,运算结果如表1所示。
图2 匹配图像
从表1数据分析可得到结论:本文算法在保证精度的前提下,时间远远小于传统算法。如表2所示,在灰度模板的情况下,同样一副图像,模板尺寸越大,则进行模板匹配运算的量也越大。特别,当模板较大时更突显本文算法的优势。
表1 两种算法的结果比较
算法模板图像时间 /s 检测位置
本文算法57×48448×4340.250(201,198)
传统算法57×48448×43413.224(201,198)
当模板变小时,两者的时间都在骤减,但即使是在模板为10×10时,本文算法时间仍然远小于传统算法。当搜索图和模板图皆为二值图时,本文算法匹配速度更加快,传统算法跟图像类型无关,只和大小有关。故对于越简单,灰度值变换范围越小的图像,本文算法越快,更能突显其优势。
4 结 语
本文通过采用模板分块匹配策略对文献[8]中经典的ncc算法进行了进一步改进,提出基于ncc的图像匹配快速算法。在保持原有的高精度的前提下,相对于文献[8]中的算法,速度上有了很大的提高;实时性强,可用于图像实时处理。但由于文献[8]的ncc算法局限于灰度变化不大的图像,使适用范围受到了一定的限制,在这方面可以做进一步的研究。另外,在图像处理领域采用进行并行处理[10]是一个很好的切入点。
表2 不同类型图像两种算法的比较结果
模板类型模板大小本文算法 /s传统算法 /s准确率
灰度模板
80×800.95421.235100%
57×480.25013.224100%
10×100.1079.621100%
二值模板
80×800.58721.554100%
57×480.13612.894100%
10×100.0759.541100%
参考文献
[1]刘宝生.几种经典相似性度量的比较研究[j].计算机应用研究,2006(11):1-3.
[2]李俊山,沈绪榜.图像分块平均绝对差匹配并行算法[j].小型微型计算机系统,2002,23(6):695-698.
[3]孙祖鑫,吴强.一种基于ts201的归一化互相关快速算法[j].计算机应用技术,2010(11):125-127.
[4]韩冰,王永明,刘杨,等.一种基于积分图像的快速归一化积相关算法[j].弹箭与制导学报,2009,29(5):283-286.
[5]郭伟,赵亦工,谢振华. 一种改进的红外图像归一化互相关匹配算法[j].光子学报,2009,38(1):189-193.
[6]王立新,刘彤宇,李阳.ssda图像匹配算法的研究及实现[j].光电技术应用,2005,20(3):53-55.
[7]李强,张钹.一种基于图像灰度的快速匹配算法[j].软件学报,2006,17(2):217-222.
[8]刘锦峰.图像模板匹配快速算法研究[d].长沙:中南大学,2007.
[9]王冰.基于差分矩因子的灰度图像矩快速算法[j].计算机学报,2005,28(8):1367-1375.
[10]李俊山.归一化积相关图像匹配算法中的图像分块并行处理方法[j].小型微型计算统,2004,25(11):1986-1989.
上一篇：计算机辅助数学分析教学的好处