首页 理论教育匹配相似度度量技术

匹配相似度度量技术

【摘要】:对目标进行匹配识别,需要选用合适的相似度比较函数,这个函数可以称之为相似度度量。相似度度量具有特征依赖性,不同的特征应该采用不同的度量方法获得最佳的测度效果。由于局部特征是采用模式向量的方式描述的,计算两个特征向量之间的距离是它们相似度的一种很好的度量。二次型距离考虑到特征分量之间的相关性,但是对称矩阵的计算量较大。

对目标进行匹配识别,需要选用合适的相似度比较函数,这个函数可以称之为相似度度量。相似度度量具有特征依赖性,不同的特征应该采用不同的度量方法获得最佳的测度效果。由于局部特征是采用模式向量的方式描述的,计算两个特征向量之间的距离是它们相似度的一种很好的度量。设d为距离函数,XYZ为局部特征的模式向量,表示形式为X=x1x2,…,xn)T。通常情况下,距离度量函数应该满足如下四个性质:

相似性978-7-111-38182-2-Chapter03-4.jpg

最小性978-7-111-38182-2-Chapter03-5.jpg

对称性978-7-111-38182-2-Chapter03-6.jpg

三角不等性978-7-111-38182-2-Chapter03-7.jpg

在实际应用中,所采用的相似度比较函数并不一定全都要满足上述的四条定理,可能只满足其中的一个或者几个。目前常用的距离函数有明可夫斯基距离、马氏距离、二次型距离和EMD距离等。

1.明可夫斯基距离(Minkowski Distance)

p=1时,L1XY)称为海明距离(Haming Distance):

p=2时,L2XY)称为欧氏距离(Euclidean Distance):

p→∞时,L∞(XY)称为切比雪夫距离(Chebychv Distance):

从向量范数的角度来讲,明可夫斯基距离可以称之为p-范数,海明距离、欧氏距离和切比雪夫距离分别称为1-范数、2-范数和∞-范数[106]

2.马氏距离(Mahalanobis Distance)

马氏距离,即马哈拉诺比斯距离,是由印度统计学家马哈拉诺比斯提出的,表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法,与欧氏距离不同的是它考虑到各种特性之间的联系(例如:一条关于身高的信息会带来一条关于体重的信息,因为两者是有关联的)并且是尺度无关的(Scale-invariant),即独立于测量尺度。其数学表达式为

其中,C为特征向量的协方差矩阵,T表示矩阵的转置运算。如果协方差矩阵为单位矩阵,马氏距离就被简化为欧氏距离;如果协方差矩阵为对角阵,则其也可称为正规化的欧氏距离。

马氏距离有很多优点。它不受量纲的影响,两点之间的马氏距离与原始数据的测量单位无关;由标准化数据和中心化数据(即原始数据与均值之差)计算出的两点之间的马氏距离相同。马氏距离还可以排除变量之间的相关性的干扰。它的缺点是夸大了变化微小的变量的作用。

3.二次型距离(Quadratic Distance)

明可夫斯基距离对所有的特征向量平均对待,没有考虑特征向量之间的关系。二次型距离与马氏距离一样,考虑了各个特征向量之间的关联性。其数学表达式为

其中A=[aij]为一个对称矩阵,表示特征向量之间的相关性;aij为下标为ij的特征分量之间的相似性。二次型距离考虑到特征分量之间的相关性,但是对称矩阵的计算量较大。

4.EMD(Earth Mover′s Distance)

EMD度量是Rubner等人[107]提出的一种相似度度量,它把运筹学的运输问题引入到图像识别中,采用最优化求解最小运输成本的方法来度量图像间的相似性。

在理解EMD计算原理时,可以把多个分布的其中之一视为地球表面的高山,另一分布则视为地球表面的低洼部分,而EMD主要的目的是要找出可以将低洼部分填平的最小成本。对地距离(Ground Distance)是用于计算高山与低洼部分的距离,也就是搬移一个单位所需花费的成本,当EMD的值愈小时则表示这个分布愈相似。计算EMD距离的方法比较复杂,不同应用需根据要求选择有效的对地距离[108]

EMD距离在最近得到了较广泛的关注,因为它能以一种非常自然的方式处理部分匹配的问题,对于处理图像领域中广泛存在的遮挡、轮廓片段匹配具有很大的用途;另外,当对地距离具有感知意义时,EMD距离往往最能体现视觉感知上的相似性。