一种基于鲁棒Hausdorff距离的目标匹配算法
- 格式：pdf
- 大小：342.53 KB
- 文档页数：3
收稿日期:2008-07-11;修回日期:
2008
-
10-07。 基金项目:国家部委预研项目(51405030104BQ0171)。 作者简介:周志强(1982-),男,江西鹰潭人,博士研究生,主要研究方向:图像匹配、目标识别; 汪渤(1963-),男,辽宁辽阳人,教授,博士生导师,主要研究方向:精确制导。文章编号:1001-9081(2009)01-0086-03
一种基于鲁棒Hausdorff距离的目标匹配算法
周志强,汪 渤
(北京理工大学信息科学技术学院,北京100081)
(zhzhzhou@bit.edu.cn)
摘 要:在传统的基于边缘位置的Hausdorff距离匹配的基础上,将边缘的梯度信息引入到距离度量当中,构造了
一种新的三维距离函数。在此基础上,提出了一种鲁棒的三维Hausdorff距离及其目标匹配算法,采用粗匹配与精匹
配相结合的两步匹配策略有效解决了由距离度量维数增加所导致的算法复杂性增大的问题。实验表明,该算法相对
于传统的基于边缘位置的Hausdorff距离目标匹配算法在鲁棒性上有很大的提高。
关键词:Hausdorff距离;目标匹配;边缘梯度
中图分类号:TP391.41 文献标志码:A
Objectmatchingalgorithmbasedonrobusthausdorffdistance
ZHOUZhi2qiang,WANGBo
(SchoolofInformationScienceandTechnology,BeijingInstituteofTechnology,Beijing100081,China)
Abstract:BasedontheconventionalHausdorffdistanceofedgeposition,weintroducedtheinformationofedgegradient
todistancemeasuring,andconstructedanewdistancefunctionthatusedtheinformationofedgepositionandgradient.Then
wepresentedarobustthree2dimensionHausdorffdistanceandtheobjectmatchingalgorithmusingtheproposedHausdorff
distance.Intheproposedalgorithm,weusedatwo2stepmatchingschemethatcombinedtwostepsofcoarseandrefined
matchingtosolvetheproblemofcomputationcomplexityincreasingcausedbyusing3Ddistancemeasure.Experimentalresult
showsthatthematchingrobustnessoftheproposedalgorithmhasbeenimprovedgreatlycomparedtoconventionalalgorithms
thatonlyusetheinformationofedgeposition.
Keywords:HausdorffDistance(HD);objectmatching;edgegradient
0 引言
图像匹配技术是图像处理及计算机视觉等领域中十分重
要的技术。根据应用场合的不同,已发展成多种不同的方法,
其中,基于Hausdorff距离(HD)的图像匹配方法由于其良好
的匹配性能被广泛应用。Hausdorff距离主要用来测量两点集
间的相似度,不需要建立点与点之间的对应关系,是一种图像
点集间的模糊匹配方法,在图像边缘匹配中具有非常好的应
用效果。文献[1]提出的利用部分Hausdorff距离(PHD)匹配
的方法,在一定程度上解决了图像遮挡和质量退化的问题;为
克服零均值噪声的影响,文献[2]提出利用基于平均距离值
的改进Hausdorff距离(MHD)进行图像边缘匹配;文献[3]提
出了一种鲁棒型的Hausdorff距离(LTS2HD),此外还有其他
各种改进的Hausdorff距离匹配方法[4-6]等。目前,在各种基
于以上Hausdorff距离的目标匹配算法中,主要还是利用图像
边缘的位置信息进行Hausdorff距离的计算,匹配中没有充分
利用边缘点的其他有用信息。为提高目标匹配算法的鲁棒
性,本文引入边缘点的梯度信息,首先构造了基于边缘位置和
梯度的三维距离度量函数,在此基础上,提出了一种鲁棒性更
好的三维Hausdorff距离及其目标匹配算法。最后,与传统匹
配算法进行了实验比较。实验结果表明,在图像几何变形及
噪声干扰下,本文算法的鲁棒性有很大的提高。1 经典的Hausdorff距离及其改进形式
给定两个点集A={a1,a2,…,a3}和B={b1,b2,…,
b3},经典的Hausdorff距离定义如下:
H(A,B)=max(h(A,B),h(B,A))(1)
其中:h(A,B),h(B,A)分别称为点集A与B间的前向距离和
反向距离,h(B,A)定义为:
h(B,A)=maxb∈BdA(b)(2)
其中:距离函数dA(b)=mina∈A‖b-a‖,表示点b到点集A的
距离。这种Hausdorff距离应用于图像匹配时的鲁棒性不好,
目标图像若被遮挡或存在噪声点,会严重影响匹配的准确度。
有向PHD定义为:
hk(B,A)=Kthb∈BdA(b)(3)
其中:Kth表示对所有dA(b)从小到大排序后的第k个值,k由
给定分数参数f∈[0,1]决定:k=[f×NB],NB表示点集B中
的点数,[・]表示向下取整运算。部分Hausdorff距离能有效
地解决目标被部分遮挡的图像匹配问题。
有向LTS2HD定义为:
hLTS(B,A)=1H∑H
n=1dA(b)(n)(4)
其中:H=[f×NA],f∈[0,1],dA(b)(n)表示将B中所有点到
A的距离dA(b)由小到大排序后的第n个值,于是hLTS(B,A)
就等于dA(b)序列的前n个值累加和的平均值。可见LTS2HD第29卷第1期
2009年1月 计算机应用
JournalofComputerApplications Vol.29No.1
Jan.2009是将大的距离值剔除后,再对保留下来的距离求平均值,所
以,即使目标图像被遮挡或质量退化,应用LTS2HD进行匹配
也能得到较好的结果。
2 基于鲁棒三维HD的目标匹配方法综合利用边缘位置和梯度信息,采用三维坐标(x,y,g)
表示边缘点,其中(x,y)表示边缘点的位置,g表示梯度。在这
种情况下,构造某点b到边缘点集A的三维距离函数dA(b)如
下:
dA(b)=
min(xa,ya)∈A(xb-xa)2+(yb-ya)2+[ω×(gb-ga)]2(5)
其中:常量ω表示梯度分量在距离度量中的权重因子,改变ω
的大小可调整梯度差值在距离计算中的贡献。将式(5)所示
的三维距离函数代入传统的Hausdorff距离计算公式(如式
(3)、(4))中,可在传统Hausdorff距离的基础上得到各种相
应的三维Hausdorff距离,从而提高匹配的鲁棒性。
由于将距离测度扩展到三维空间,若依然采用传统的
Hausdorff距离匹配方法,势必增加计算的复杂度。为了减小
计算复杂度,本文在目标匹配过程中采用粗匹配与精匹配相
结合的两步匹配策略。具体方法是,首先在粗匹配时,忽略边
缘的梯度信息,采用传统的Hausdorff距离匹配方法单纯地根
据边缘的位置信息寻找目标图像潜在的匹配位置,然后在有
限数量的潜在匹配位置处,再综合利用边缘的位置和梯度信
息寻找最终的正确匹配位置。在上述精匹配过程中,本文采
用了一种不同于传统Hausdorff距离的鲁棒型三维Hausdorff
距离,记为G2HD。利用G2HD的目标匹配算法过程如下:
1)利用边缘位置进行粗匹配,主要采用PHD方法。首先
利用Canny算子提取目标图像B和测试图像A的边缘Be和
Ae。设置分数参数f及距离阈值h,单纯根据边缘的位置信息
逐个计算每个可能匹配位置处的PHD值hk(Be,Ae),若
hk(Be,Ae)
录此时的位置坐标及距离值hk(Be,Ae)。
2)引入边缘的梯度信息进行目标的精确定位。首先利用
高斯滤波及Soble算子计算原图所有点处的梯度,得到原图的
梯度图Ag和Bg。其中,高斯滤波的作用在于消除噪声对梯度
的影响。在粗匹配得到的每个潜在匹配位置处,结合梯度信息
计算本文三维Hausdorff距离G2HD,具体过程如下:
对于目标边缘Be中的每一边缘点b,只在与b相对应的
Ae中的点a附近一个小邻域δ(a,hk)(邻域半径为该匹配位
置处PHD值hk(Be,Ae))内搜索边缘点,得到边缘点集e(a,
hk)(e(a,hk)∈Ae)。在计算点b与边缘Ae的距离函数dAe(b)
时,将所考查的边缘点的范围由点集Ae缩小至点集e(a,hk),
重新构造三维距离函数dAe(b)如下:
dAe(b)=
min(x,y)∈e(a,h
k)(xb-x)2+(yb-y)2+[ω×ρ(gb-g)]2,
e(a,hk)≠
0,e(a,hk)=
(6)若在邻域δ(a,hk)中没有边缘点,即集合e(a,hk)为空
时,则令dAe(b)=0,即点b不在考虑之内,这样就剔除了Be上距离大的边缘点,有利于消除外部点的干扰。式(6)中函数
ρ(x)定义为:
ρ(x)=|x|, |x|
τ,|x|≥τ(7)
函数ρ(x)的作用在于剔除大于阈值τ的梯度差值,消除
由噪声干扰及图像质量退化等因素造成的边缘点梯度值突变
所产生的影响。由第1步和式(6)可推知,在边缘Be上,需要
考虑的边缘点b的数量近似等于[f×NBe],所以,在剔除了所
有可能的外部点以及消除了噪声等干扰因素的影响后,采用
均值求取方法得到的三维Hausdorff距离为:
hG-HD(Be,Ae)=1[f×NBe]∑
b∈BedAe(b)(8)
3)根据式(8)计算得到每个潜在匹配位置处的G2HD
值后进行比较,其中取得最小值的匹配位置即为目标所在位
置。
上述G2HD利用了边缘的梯度信息,同时考虑了对各种
影响因素的抑制,通过恰当地选取参数f和τ,可以有效的克
服目标遮挡、噪声干扰及图像质量退化等因素的影响,具有更
好的鲁棒性。
3 实验结果
为了验证本文算法的鲁棒性,将其与传统的基于边缘位
置的目标匹配算法进行实验比较。实验所用图像均为灰度值
归一化于[0,255]的灰度图,所有实验均取权重因子ω=
0.8、梯度差阈值τ=20。处理器为P42.8GHz,内存容量
1GB。
首先比较算法在高斯噪声干扰下的匹配鲁棒性。图1所
示的是在没有加噪声情况下的一幅256×256卫星图像目标
匹配结果。在未加噪声情况下,分别用PHD、LTS2HD及本文
G2HD取分数参数f=0.8,得到了如图1(c)所示的正确匹配
结果,匹配位置均为(140,146),各算法所用时间分别为:
PHD:2016ms;LTS2HD:2031ms;G2HD:2125ms,其中G2HD
算法在粗匹配时距离阈值h取为2,得到47个候选匹配位置
(各算法在初始阶段均使用了相同的加速搜索技术,详见文
献[1])。在测试图像中加入不同方差的高斯噪声,各算法得
