基于主分量与Hausdorff距离的匹配算法

2025-09-29 理论教育版权反馈

【摘要】：如图7-6所示，Hausdorff距离表征了两个点集之间的最大不相似程度。因为Hausdorff距离的适用形式限制在有限点集内，所以非常适合度量特征点集的相似性。而角点点集经过主分量法处理后，消除了其对尺寸、位置、方位的依赖性，就可以作为Hausdorff距离的匹配元素，对这些元素的相似性进行度量并将此度量值作为目标与原型相似性的依据，如此一来，大大降低了算法的运算复杂度，并减少了噪声对识别效果的影响。

霍特林（Hotelling）^［207］提出了一个可以去掉一个随机向量中各元素间相关性的线性变换，并把它称作“主分量法”。此后，卡胡南（Karhunen）和列夫（Loeve）提出了一种针对连续信号的类似的变换。这种方法派生出了一种离散图像变换的方法。

我们根据角点的坐标可以生成二维向量，可以把这些二维向量当成原理中的随机向量X=(a，b)T处理，其中a和b是角点关于x₁轴和x₂轴的坐标值。总体的均值向量（边界点）可以通过K个样本向量（角点）来估计：

总体向量的协方差矩阵可以以如下方式用样本近似得到：

因为C_X是实对称的，找到一组n个标准正交特征向量总是可能的。令e_i和λ_i，i=1，2，…，n为特征向量和对应的C_X特征值，以降序排布，使λ_j≥λ_j+1，j=1，2，…，n-1。令A为一个由C_X的特征向量组成其行元素的矩阵，并进行排序，使A的第一行为对应最大特征值的特征向量，而最后一行为对应最小特征值的特征向量。假设把A作为将X的向量映射到用y代表的向量的变换矩阵，就得到了霍特林变换的表达式：

使用式（7-14）的实际结果是需要设置一个新的坐标系统，这个坐标系统以角点总体的质心（均值向量的坐标）为原点，以C_X的特征向量所指方向为轴的方向，如图7-5b所示。这个坐标系统清晰地显示出式（7-14）所进行的变换是一种旋转变换，这种变换使用特征向量将数据排列起来，如图7-5c所示。实际上，这种排列正好是数据去相关的机理。另外，由于特征值沿着C_y的主对角线排列，λ_i是沿着特征向量e_i的分量y_i的方差，这两个特征向量是正交的。由于这个明显的原因，y轴被称为本征轴^［8］。

图7-5 用主分量法将目标沿着自身的本征轴对准

a）一个目标 b）特征向量 c）旋转目标

使用主特征向量排列角点的概念在图像描述中起着十分重要的作用。正如前面提到的，目标的描述对于大小变化、平移和旋转变化本应是尽可能独立的。使用目标的主轴校正的能力为消除旋转变化的影响提供了一种可靠手段。特征值是沿着本征轴的方差，并可用于尺寸的归一化。平移带来的影响可以通过将角点的均值设定为中心来解决。(https://www.chuimin.cn)

Huttenlocher等人^［208］提出的Hausdorff距离是用来描述两组点集之间相似程度的一种度量，是集合与集合之间距离的一种定义形式。它与许多其他匹配算法不一样，它并不要求目标与模板的简单一致，而是可以针对部分匹配作出良好的反应，因此它本身就具有一定的抗遮挡能力。对有限点集A=｛a₁，a₂，…，a_p｝和B=｛b₁，b₂，…，b_p｝，A，B之间的Hausdorff距离定义如下：

式中，H（A，B）是h（A，B）、h（B，A）中较大的那一个，称为A、B之间的Hausdorff距离；h（A，B）称为点集A到B的有向Hausdorff距离，即点集A中的每个点a_i到B集中与其距离最近的点b_j之间的距离a_i-b_j‖进行排序，取这样的距离中的最大值作为h（A，B）的值，同理可得h（B，A）；∗‖表示某种距离范数，如欧氏距离。如图7-6所示，Hausdorff距离表征了两个点集之间的最大不相似程度。

图7-6 Hausdorff距离示意图

a）表示点集A到B的有向Hausdorff距离 b）表示点集B到A的有向Hausdorff距离

在本书的应用中，为了降低噪声的影响，我们使用部分Hausdorff距离，其定义如下：

式中，H_LK（A，B）仍是h_L（A，B）和h_K（B，A）中较大的一个。h_L（A，B）虽然还是按照a_i-b_j‖（即A中的每个点a_i到B中与其距离最近的点b_j之间的距离）进行排序，但不是像h（A，B）那样取全局最大值，而是取第L个值（1≤L≤q，q为A集中点的数目），h_K（B，A）同理可得。

通过角点检测算法可以得到待匹配目标和原型的两组特征点集，则目标匹配问题就转化为特征点匹配问题。因为Hausdorff距离的适用形式限制在有限点集内，所以非常适合度量特征点集的相似性。而角点点集经过主分量法处理后，消除了其对尺寸、位置、方位的依赖性，就可以作为Hausdorff距离的匹配元素，对这些元素的相似性进行度量并将此度量值作为目标与原型相似性的依据，如此一来，大大降低了算法的运算复杂度，并减少了噪声对识别效果的影响。

基于主分量与Hausdorff距离的匹配算法

相关推荐