豪斯多夫（Hausdorff）距离详解
豪斯多夫（Hausdorff）距离详解
豪斯多夫（Hausdorff）距离是一种衡量两个点集之间相似度的方法，在计算机视觉、模式识别等领域有着广泛的应用。本文将详细介绍豪斯多夫距离的定义、计算方法及其性质，并通过具体例子帮助读者理解这一概念。
一、定义
给定欧氏空间中的两点集 (A = {a_1, a_2, \ldots}) 和 (B = {b_1, b_2, \ldots})，豪斯多夫（Hausdorff）距离就是用来衡量这两个点集间的距离。定义公式如下：
[H(A, B) = \max[h(A, B), h(B, A)]]
其中，
[h(A, B) = \max_{a \in A} \min_{b \in B} ||a - b||]
[h(B, A) = \max_{b \in B} \min_{a \in A} ||b - a||]
(H(A, B)) 称为双向 Hausdorff 距离，(h(A, B)) 称为从点集 A 到点集 B 的单向 Hausdorff 距离。相应地，(h(B, A)) 称为从点集 B 到点集 A 的单向 Hausdorff 距离。
二、例子
下面从一个例子来理解 Hausdorff 距离：
上图中，给出了 A、B、C、D 四条路径，其中路径 A 具体为（16-17-18-19-20），路径 B 具体为（1-2-3-4-9-10）。要求 Hausdorff 距离 (H(A, B))，则需要先求出单向 Hausdorff 距离 (h(A, B)) 和 (h(B, A))。
对于 (h(A, B))，以 A 中的点 16 为例，在路径 B 中的所有点中，距离点 16 最近的是点 1，距离为 3。即：
[\min_{b \in B} ||a_{(16)} - b|| = 3]
同理由图可得：
[\min_{b \in B} ||a_{(17)} - b|| = 3]
[\min_{b \in B} ||a_{(18)} - b|| = 3]
[\min_{b \in B} ||a_{(19)} - b|| = 2]
[\min_{b \in B} ||a_{(20)} - b|| = 2]
在它们中，值最大的为 3，故 (h(A, B) = 3)。
同理可得，(h(B, A) = 4)。
所以 (H(A, B) = \max[h(A, B), h(B, A)] = 4)。
同理可求出上图中四条路径间的单向 Hausdorff 距离如下表所示：
三、性质
- 双向 Hausdorff 距离 (H(A, B)) 是单向 Hausdorff 距离 (h(A, B)) 和 (h(B, A)) 两者中较大者，显然它度量了两个点集间的最大不匹配程度。
- 如上图，当 A 和 B 都是闭集的时候，Hausdorff 距离满足度量的三个定理：
- (H(A, B) \geq 0)，当且仅当 (A = B) 时，(H(A, B) = 0)
- (H(A, B) = H(B, A))
- (H(A, B) + H(B, C) \geq H(A, C))
- 若凸集 A 和 B 满足 (A \not\subset B) 且 (B \not\subset A)，并记 (\partial A) 和 (\partial B) 分别为 A 和 B 边界的点集合，则 A 和 B 的 Hausdorff 距离等于 (\partial A) 和 (\partial B) 的 Hausdorff 距离。
- Hausdorff 距离易受到突发噪声的影响。
当图像受到噪声污染或存在遮挡等情况时，原始的 Hausdorff 距离容易造成误匹配。所以，在 1933 年，Huttenlocher 提出了部分 Hausdorff 距离的概念。
简单地说，包含 q 个点的集合 B 与集合 A 的部分 Hausdorff 距离就是选取 B 中的 K 个点（(K \geq 1) 且 (K \leq q)），然后求这 K 个点到 A 集合的最小距离，并排序，则排序后的第 K 个值就是集合 B 到集合 A 的部分单向 Hausdorff 距离。定义公式如下：
[h_K(A, B) = K^{th} \max_{a \in A} \min_{b \in B} ||a - b||]
相应地，部分双向 Hausdorff 距离定义为：
[H_K(A, B) = \max[h_K(A, B), h_K(B, A)]]
参考：
