基于 Hausdorff 距离的图像配准快速算法—数字图像处理大作业
基于 Hausdorff 距离的图像配准快速算法
(数字图像处理大作业)
基于 Hausdorff 距离的图像配准快速算法—数字图像处理大作业
摘要：在图像配准过程中，传统 Hausdorff 距离算法的计算量较大。针对该问题，杨通
钰等人提出一种基于 Hausdorff 距离的图像配准快速算法。本文详细介绍了这一图像配准 快速算法，通过论文介绍，在 win7+vc6.0+opencv1.0 环境下用 c/c++编程实现和验证了本 文的算法，并对该算法提出了一些改进意见。
关键词：Hausdorff 距离，图像配准，图像匹配，模板匹配，边缘检测
引言：图像配准(Image registration)就是将不同时间、不同传感器（成像设备）或不同
条件下（天候、照度、摄像位置和角度等）获取的两幅或多幅图像进行匹配、叠加的过程， 它已经被广泛地应用于遥感数据分析、计算机视觉、图像处理等领域。要进行图像配准， 首先对两幅图像进行特征提取得到特征点，通过进行相似性度量找到匹配的特征点对，然 后通过匹配的特征点对得到图像空间坐标变换参数，最后由坐标变换参数进行图像配准。
传统的模板匹配方法有平均绝对差(Mean Absolute Deviation, MAD)算法、 Hausdorff 距离算法和序贯相似性检测(Sequential Similarity Detection algorithm, SSDA)算法等。但 MAD 算法效率低、鲁棒性差；与 MAD 算法相比， SSDA 算法速度略好，匹配精度较好，但对噪声点很敏感；Hausdorff 距离算法 匹配精度很高，对于目标遮挡、图像噪声和图像晃动等情况具有较好的鲁棒性， 优点非常突出，因此，使用 Hausdorff 距离进行图像匹配是较常用的方法之一， 但缺点是计算复杂导致匹配速度慢。
为了解决使用 Hausdorff 距离进行图像匹配时由于计算复杂导致匹配速度慢的 问题，杨通钰等人提出了一种改进的 Hausdorff 距离算法，去除了冗余的计算 量从而提高了匹配速度，能够高精度、高效地实现配准。由于图像会有旋转、 尺度等变换(本文只考虑微小旋转及尺度变换)，在模板匹配过程中不能完全匹 配， 而是采用 Hasudorff 距离算法进行相似度计算，因此选取待匹配图像中 与模板相似度最大的部分作为匹配区域。
int x; int y; }; double compute_hausdorffdistance(CArray<POINT, POINT&> &pointarrayA,
CArray<POINT, POINT&> &pointarrayB) {
double hausdorffdistance;//最终的 Hausdorff 距离 int num_arrayA=pointarrayA.GetSize();//记录两点数组个数 int num_arrayB=pointarrayB.GetSize(); double H,H1=0.0,H2=0.0; int i,j; //计算 h(A,B)的平方 H1 for(i=0;i<num_arrayA;i++) {
一、原有方法综述
图像匹配是数字图像处理的基本任务，是图像处理等领域的基本问题它有 2 种 基本模型：(1)2 幅或多幅来自不同传感器、不同视角或不同时间的图像需找出 对应关系，经过匹配步骤可得出 2 幅图像的差别所在，为下一步处理作基础； (2)根据已知的图像模式在另一幅图像中搜索类似模板的目标，即模板匹配。已 有的图像匹配算法可分为 2 类：基于图像几何特征的匹配和基于像素灰度值的 匹配。前者计算量虽小，但无通用性模型，而后者有一定的数学统计模型，简 单易行。在使用模板匹配来实现图像配准的方法中，模板匹配的效率和精度决 定了图像配准的效率和精度。
二、算法的提出和详细推导
1.模板匹配
1.1Hausdorff 距离定义
基于 Hausdorff 距离的图像配准快速算法—数字图像处理大作业
Hausdorff 距离是量度度量空间中真子集之间的距离，是集合与集合之间距离 的一种定义形式，其值越大，点集之间匹配得越差。 其标准定义如下： 设 X 和 Y 是度量空间 M 的两个真子集，那么 Hausdorff 距离 dH(X,Y)是最小的 数 r 使得 X 的闭 r—邻域包含 Y，Y 的闭 r—邻域也包含 X。 即：
基于 Hausdorff 距离的图像配准快速算法—数字图像处理大作业
h(Y ,X)同理可得。双向 Hausdorff 距离 dH(X,Y)是单向距离 h(X,Y)和 h(Y ,X) 两者中的较大者,它度量了两个点集间的最大不匹配程度。 根据定义写出程序代码如下： /*---------计算两点数组的 Hausdorff 距离-----------*/ // 定义 POINT 结构体 struct POINT{
用图像表示如下：
这距离函数令 M 的所有真子集组成的集成为度量空间，且记为 F(M)。F(M)的拓 扑只是依赖于 M 的拓扑。若 M 是非空的，则 F(M)也是。 豪斯多夫空间也可以照样定义在 M 的闭非真子集上，但距离可能是无限大，F(M) 的拓扑不只依赖于 M 的拓扑，也依赖于 M 的特有度量。非闭子集间的豪斯多夫 距离可以定义为它们的闭包的豪斯多夫距离。这给予 M 的所有子集组成的集一 个伪度量。（两个有相同闭包的子集的豪斯多夫距离是零）。 更加具体一点，我们假设集合 X={a1,…,am },Y={b1,…,bn},则这两个点集合之 间的 Hausdorff 距离定义为：dH(X,Y)=max{h(X,Y),h(Y ,X)}其中, h(X,Y)=max a∈X {min（b∈Y）{ ‖a-b‖ }} h(Y ,X)= max b∈Y {min（a∈X）{‖b-a‖ }} ‖·‖是点集 X 和 Y 点集间的距离范式，一般直接用欧氏距离，下面用 D 表示。 这里,式 dH(X,Y)称为双向 Hausdorff 距离,是 Hausdorff 距离的最基本形式; h(X,Y)和 h(Y ,X)分别称为从 X 集合到 Y 集合和从 Y 集合到 X 集合的单向 Hausdorff 距离。 即 h(X,Y)实际上首先对点集 X 中的每个点ai到距离此点ai最近的 B 集合中点bj 之间的距离‖ai-bj‖进行排序,然后取该距离中的最大值作为 h(X,Y)的值。
