林 意，薛思骐，郭婷婷

(江南大学数字媒体学院，江苏 无锡 214122)

Hausdorff距离在几何设计、图像匹配、图像识别中有广泛应用[1-2]，但是现阶段关于参数曲线间Hausdorff距离[3]的研究较少，计算仍有一定难度，无法通过其定义直接计算获得。Scharf等[4-5]提出了在自由曲线上可能产生Hausdorff距离的4种情况：产生在端点处、极值点处、共线法向点处或是平分线交点处，并给出了对应的求解方程或方程组[6-7]。虽然通过方程组计算Hausdorff距离产生的结果比较精确，但是对于参数曲线来说，求解方程组的复杂度很高，计算较为困难。因此，Chen等[8-10]从几何角度提出了曲线间Hausdorff距离的计算方法，通过不断减小半径的圆弧来排除无效曲线段，直至最后收敛于一个确定的值。这种方法需要计算距离方差，虽然计算量比前种方法小，但仍然不是很方便。此外，在进行圆弧剪枝时，如何判断曲线段是否在圆弧外也较困难。白彦冰[11]将曲线在给定误差下离散成折线，然后在Scharf[12]提出的基于Voronoi图性质的单向Hausdorff距离计算方法的基础上计算折线间的Hausdorff距离，以近似获得曲线间的Hausdorff距离。这种方法无需计算方程，但Voronoi图的构建比较复杂，且在进行曲线离散时采用递归分割的方法，需另外采取节点插入算法，比较繁琐。

本文将曲线绘制过程中产生的折线作为曲线离散折线，然后将曲线间的Hausdorff距离转化为折线间的Hausdorff距离并进一步转化为点到线段间的距离进行计算，并加以必要的剪枝策略[13]以提高计算效率。

1 Hausdorff距离的定义

Hausdorff距离是描述两组点集之间相似程度的一种量度，它是两个点集之间距离的一种定义形式，它具有方向性。……