The directed Hausdorff distance between imprecise point sets

We consider the directed Hausdorff distance between point sets in the plane, where one or both point sets consist of imprecise points. An imprecise point is modelled by a disc given by its centre and a radius. The actual position of an imprecise point may be anywhere within its disc. Due to the direction of the Hausdorff distance and whether its tight upper or lower bound is computed, there are several cases to consider. For every case we either show that the computation is NP-hard or we present an algorithm with a polynomial running time. Further we give several approximation algorithms for the hard cases and show that one of them cannot be approximated better than with factor 3, unless P=NP.     

Robust Hausdorff distance measure for face recognition

Face is considered to be one of the biometrics in automatic person identification. The non-intrusive nature of face recognition makes it an attractive choice. For face recognition system to be practical, it should be robust to variations in illumination, pose and expression as humans recognize faces irrespective of all these variations. In this paper, an attempt to address these issues is made using a new Hausdorff distance-based measure. The proposed measure represent the gray values of pixels in face images as vectors giving the neighborhood intensity distribution of the pixels. The transformation is expected to be less sensitive to illumination variations besides preserving the appearance of face embedded in the original gray image. While the existing Hausdorff distance-based measures are defined between the binary edge images of faces which contains primarily structural information, the proposed measure gives the dissimilarity between the appearance of faces. An efficient method to compute the proposed measure is presented. The performance of the method on bench mark face databases shows that it is robust to considerable variations in pose, expression and illumination. Comparison with some of the existing Hausdorff distance-based methods shows that the proposed method performs better in many cases.     

GPU-accelerated Hausdorff distance computation between dynamic deformable NURBS surfaces

We present a parallel GPU-accelerated algorithm for computing the directed Hausdorff distance from one NURBS surface to another, within a bound. We make use of axis-aligned bounding-box hierarchies that bound the NURBS surfaces to accelerate the computations. We dynamically construct as well as traverse the bounding-box hierarchies for the NURBS surfaces using operations that are optimized for the GPU. To compute the Hausdorff distance, we traverse this hierarchy after culling bounding-box pairs that do not contribute to the Hausdorff distance. Our contribution includes two-sided culling tests that can be performed in parallel using the GPU. The culling, based on the minimum and maximum distance ranges between the bounding boxes, eliminates bounding-box pairs from both surfaces that do not contribute to the Hausdorff distance simultaneously. We calculate accuracy bounds for our computed Hausdorff distance based on the curvature of the surfaces. Our algorithm runs in real-time with very small guaranteed error bounds for complex NURBS surfaces. Since we dynamically construct our bounding-box hierarchy, our algorithm can be used to interactively compute the Hausdorff distance for models made of dynamic deformable surfaces.     

Error-bounded biarc approximation of planar curves

Presented in this paper is an error-bounded method for approximating a planar parametric curve with a G¹ arc spline made of biarcs. The approximated curve is not restricted in specially bounded shapes of confined degrees, and it does not have to be compatible with non-uniform rational B-splines (NURBS). The main idea of the method is to divide the curve of interest into smaller segments so that each segment can be approximated with a biarc within a specified tolerance. The biarc is obtained by polygonal approximation to the curve segment and single biarc fitting to the polygon. In this process, the Hausdorff distance is used as a criterion for approximation quality. An iterative approach is proposed for fitting an optimized biarc to a given polygon and its two end tangents. The approach is robust and acceptable in computation since the Hausdorff distance between a polygon and its fitted biarc can be computed directly and precisely. The method is simple in concept, provides reasonable accuracy control, and produces the smaller number of biarcs in the resulting arc spline. Some experimental results demonstrate its usefulness and quality.     

Line segment Hausdorff distance on face matching

A novel concept of line segment Hausdorff distance is proposed in this paper. Researchers apply Hausdorff distance to measure the similarity of two point sets. It is extended here to match two sets of line segments. The new approach has the advantage to incorporate structural and spatial information to compute the similarity. The added information can conceptually provide more and better distinctive capability for recognition. This would strengthen and enhance the matching process of similar objects such as faces. The proposed technique has been applied online segments generated from the edge maps of faces with encouraging result that supports the concept experimentally. The results also implicate that line segments could provide sufficient information for face recognition. This might imply a new way for face coding and recognition.     

A new interpolation algorithm for tracing planar equidistant curves

The aim of this paper is to propose an interpolation algorithm for tracing the equidistant (bisector) of two planar curves. The structure of the algorithm may be adapted accordingly so as to be used either for purely computing purposes or for presentation purposes. As a computing tool, the algorithm is suitable for computation of offset intersections and construction of Voronoi diagrams. In this case the step size is adjusted appropriately in order to reach the desired position in a small number of steps but with high accuracy. As a presentation tool, it may be embedded in a CAD system, entrusted with the task of drawing equidistants or even it may be used for plotting equidistants by driving the plotting tip. In this case, a fixed step size is selected to satisfy the specific precision requirements of the presentation. The development of the algorithm is achieved by treating equidistant generation as a locus-tracing problem. Using analytic concepts and the locus-defining geometric property, we formulate two sophisticated constructive operations. The repeated application of these operations generates a succession of points on the desired path (the locus) accurately and efficiently.     

一种快速计算参数曲面间Hausdorff距离近似值的方法

针对曲面间Hausdorff距离计算复杂度高、相关计算方法少的问题,提出一种三角面片-包围盒方法快速计算参数曲面间Hausdorff距离的近似值。曲面离散化后的三角面片集合可以较好地逼近曲面,借助这一特性,将曲面间的Hausdorff距离近似转化为三角面片集合间的Hausdorff距离。在具体计算过程中,辅之以包围盒技术对无效的三角面片进行排除,以提高计算效率。为进一步简化两三角面片间的距离计算,在误差可控范围内提出采样点近似计算方法。实验表明,与曲面直接构造包围盒方法相比,该方法简便、易于实现、排除率高,在不影响计算结果的情况下,计算效率显著提高,有广泛的应用价值。     

Bisector curves of planar rational curves

This paper presents a simple and robust method for computing the bisector of two planar rational curves. We represent the correspondence between the foot points on two planar rational curves C₁(t) and C₂(r) as an implicit curve (t,r)=0, where (t,r) is a bivariate polynomial B-spline function. Given two rational curves of degree m in the xy-plane, the curve (t,r)=0 has degree 4m−2, which is considerably lower than that of the corresponding bisector curve in the xy-plane.     

一种基于Hausdorff距离的运动物体跟踪算法

针对视频处理中运动物体的检测和跟踪问题,提出了一种基于Hausdorff距离的目标跟踪算法。新算法提出首先采用多尺度分水岭变换获取运动物体模型,消除了传统基于分水岭变换算法存在的缺陷;然后使用部分Hausdorff距离实现后续帧中运动物体模型的匹配;最后再次使用多尺度分水岭算法完成运动物体模型的更新。实验表明,该算法可以有效地跟踪多个刚体或非刚体目标。     

Noisy logo recognition using line segment Hausdorff distance

Logo recognition is of great interest in the document and shape analysis domain. In order to develop a recognition method that is robust to employ under adverse conditions such as different scale/orientation, broken curves, added noise and occlusion, a modified line segment Hausdorff distance is proposed in this paper. The new approach has the advantage to incorporate structural and spatial information to compute dissimilarity between two sets of line segments rather than two sets of points. The proposed technique has been applied on line segments generated from logos with encouraging results. Clear cut distinction between the correct and incorrect matches has been observed. This suggests a strong potential for logo and shape recognition system.     

A new algorithm for computing the minimum Hausdorff distance between two point sets on a line under translation

To determine the similarity of two point sets is one of the major goals of pattern recognition and computer graphics. One widely studied similarity measure for point sets is the Hausdorff distance. So far, various computational methods have been proposed for computing the minimum Hausdorff distance. In this paper, we propose a new algorithm to compute the minimum Hausdorff distance between two point sets on a line under translation, which outperforms other existing algorithms in terms of efficiency despite its complexity of O((m+n)lg(m+n)), where m and n are the sizes of two point sets.     

一种改进的Hausdorff距离地图匹配方法

目前的地图匹配算法分为在线和离线匹配两类。针对离线地图匹配中Marchal算法精度较低的问题,提出了一种改进的Housdorff距离匹配算法,利用航线方向角与Housdorff距离对Marchal匹配算法进行了改进。通过仿真试验的定性定量分析,新算法可以较好地纠正矢量数据不完整时产生的错误结果,很大程度上提高了匹配的准确性,可以为导航系统以及规划部门提供保障服务。     

Tracking non-rigid objects using probabilistic Hausdorff distance matching

This paper proposes a new method of extracting and tracking a non-rigid object moving against a cluttered background while allowing camera movement. For object extraction we first detect an object using watershed segmentation technique and then extract its contour points by approximating the boundary using the idea of feature point weighting. For object tracking we take the contour to estimate its motion in the next frame by the maximum likelihood method. The position of the object is estimated using a probabilistic Hausdorff measurement while the shape variation is modelled using a modified active contour model. The proposed method is highly tolerant to occlusion. Unless an object is fully occluded during tracking, the result is stable and the method is robust enough for practical application.     

一种参数曲线间Hausdorff 距离的计算方法

针对一般的连续参数曲线,提出一种快速计算曲线间Hausdorff 距离的方法。由 于曲线的近似折线能很好的表示曲线,所以,许多软件中,采用曲线的近似折线绘制曲线。为 此,证明了在任意给定误差范围下,可以将曲线间的Hausdorff 距离转化为折线间的Hausdorff 距离,进一步转化为点到线段间的距离进行计算,并辅之必要的剪枝策略和增量式算法以提高 计算效率。该方法计算速度快,逼近度高,基本解决了参数曲线间Hausdorff 距离的计算问题, 在几何设计、图像匹配、图像识别等领域有广泛应用。     

A unified approach to autofocus and alignment for pattern localization using hybrid weighted Hausdorff distance

Pattern localization is a fundamental task in machine vision, and autofocus is a requirement for any automated inspection system by allowing greater variation in the distance from the camera to the object being imaged. In this paper, we propose a unified approach to simultaneous autofocus and alignment for pattern localization by extending the idea of image reference approach. Under the least trimmed squares (LTS) scheme, the proposed hybrid weighted Hausdorff distance (HWHD) is a robust similarity metric that combines the Hausdorff distance (HD) with the edge-amplitude normalized gradient (EANG) matching. The EANG is designed to characterize the different degrees of blur at the edge points for focus cues, immune to illumination variations between the reference and the target image. We experimentally illustrate its performance on simulated as well as real data.     

The Hausdorff Voronoi Diagram of Point Clusters in the Plane

We study the Hausdorff Voronoi diagram of point clusters in the plane, a generalization ofVoronoi diagrams based on the Hausdorff distance function. We derive a tight combinatorial bound on the structural complexity of this diagram and present a plane sweep algorithm for its construction. In particular, we show that the size of the Hausdorff Voronoi diagram is (n + m), where n is the number of points on the convex hulls of the given clusters, and m is the number of crucial supporting segments between pairs of crossing clusters. The plane sweep algorithm generalizes the standard plane sweep paradigm for the construction of Voronoi diagrams with the ability to handle disconnected Hausdorff Voronoi regions. The Hausdorff Voronoi diagram finds direct application in the problem of computing the critical area of a VLSI layout, a measure reflecting the sensitivity of the VLSI design to spot defects during manufacturing.     

基于改进Hausdorff距离的分层景象匹配算法

为克服传统的相似性度量容易受到噪声、遮挡和成像机理等因素影响的缺点,结合人的认知过程,提出了一种分层的模板匹配算法.首先利用了统计指标来对候选匹配区域进行预标记,其次通过对Hausdorff相似性度量的改进来提高其对遮挡、异源图像匹配的鲁棒性.实验结果证明了该方法能够有效地减少搜索区域大小,提高了遮挡情况下的匹配精度,验证了算法的有效性.     

Approximation of graph edit distance based on Hausdorff matching

Graph edit distance is a powerful and flexible method for error-tolerant graph matching. Yet it can only be calculated for small graphs in practice due to its exponential time complexity when considering unconstrained graphs. In this paper we propose a quadratic time approximation of graph edit distance based on Hausdorff matching. In a series of experiments we analyze the performance of the proposed Hausdorff edit distance in the context of graph classification and compare it with a cubic time algorithm based on the assignment problem. Investigated applications include nearest neighbor classification of graphs representing letter drawings, fingerprints, and molecular compounds as well as hidden Markov model classification of vector space embedded graphs representing handwriting. In many cases, a substantial speedup is achieved with only a minor loss in accuracy or, in one case, even with a gain in accuracy. Overall, the proposed Hausdorff edit distance shows a promising potential in terms of flexibility, efficiency, and accuracy.     

基于改进Hausdorff距离的人脸匹配方法

提出了一种基于改进Hausdorff距离的人脸相似度匹配的方法,该方法首先将人脸划分为脸型、双眼、鼻、嘴等几个特征点集,分别计算各部分的改进Hausdorff距离,然后进行加权计算相似度。利用该方法,在ASM（主动形状模型）定位人脸的基础上进行了人脸检索。实验表明,利用人脸相似度计算方法对人脸特征库进行搜索,达到了较好的效果。同时结合ASM自动人脸检测,本方法可以全自动完成人脸匹配,应用于人脸识别及数字娱乐等领域。