A Two-Stage Point Pattern Matching Algorithm Using Ellipse Fitting and Dual Hilbert Scans
A Two-Stage Point Pattern Matching Algorithm Using Ellipse Fitting and Dual Hilbert Scans
复制标题
DOI：
10.1093/ietisy/e91-d.10.2477
复制
发表时间：
2008-10
期刊：
影响因子：
--
通讯作者：
Li Tian;S. Kamata
中科院分区：
文献类型：
--
作者：
Li Tian;S. Kamata
点模式匹配是许多图像分析和计算机视觉任务中的一个基本问题。提出了一种基于椭圆拟合和双Hilbert扫描的PPM问题的两阶段算法。在第一个匹配阶段，利用加权最小二乘拟合法(WLSF)拟合出椭圆的四个节点，粗略估计变换参数。然后，将希尔伯特扫描应用于第二匹配阶段的两个方面：一是用于相似性度量，二是用于搜索空间约简。通过希尔伯特扫描将二维点的二维坐标转换为一维空间信息，可以快速计算出希尔伯特扫描距离。另一方面，通过N-D Hilbert扫描将N-D搜索空间转换为一维搜索空间序列，并在一维搜索空间序列上提出了一种有效的搜索策略。在实验中，我们使用模拟的点集数据和真实的指纹图像来评估我们的算法的性能，我们的算法在精度和效率上都取得了令人满意的结果。
Point Pattern Matching (PPM) is an essential problem in many image analysis and computer vision tasks. This paper presents a two-stage algorithm for PPM problem using ellipse fitting and dual Hilbert scans. In the first matching stage, transformation parameters are coarsely estimated by using four node points of ellipses which are fitted by Weighted Least Square Fitting (WLSF). Then, Hilbert scans are used in two aspects of the second matching stage: it is applied to the similarity measure and it is also used for search space reduction. The similarity measure named Hilbert Scanning Distance (HSD) can be computed fast by converting the 2-D coordinates of 2-D points into 1-D space information using Hilbert scan. On the other hand, the N-D search space can be converted to a 1-D search space sequence by N-D Hilbert Scan and an efficient search strategy is proposed on the 1-D search space sequence. In the experiments, we use both simulated point set data and real fingerprint images to evaluate the performance of our algorithm, and our algorithm gives satisfying results both in accuracy and efficiency.