Abstract
本篇論文的目的在於研究平面圖形的比對問題。我們提出了以最少特徵關係（minimum feature relations） 為基礎的比對演算法來解決此問題。在提出的平面圖形比對演算法中，包括一個點圖形比對演算法和一個線圖形比對演算法。我們的方法希望能在下列情況下應用：（１）兩圖形之特徵個數不同。（２）兩圖形之間有平移量。（３）兩圖形之間有旋轉角度差。（４）兩圖形之間有大小關係。（５）兩圖形之特徵間有區域位置誤差。我們所提出的比對演算法可分為兩部分: 鬆弛法的處理(relaxation process) 和選擇配對個數的處理 (select- match-pairprocess) 。第一部分鬆弛法的處理運用最少特徵關係和鬆弛法的技術來決定每個可能配對的相對機率。在鬆弛法處理過程中，藉著對註冊（registration）的區域驗證使我們的演算法能夠對於圖形的任意平移、旋轉和放大（縮小）產生不變性。第二部分選擇配對個數運用每對誤差容忍度（pairwise error bound）來決定實際的配對個數與配對誤差（matcherror） 。整個系統對雜訊的容忍度亦可由每對誤差容忍度來控制。在實驗中我們對自己的資料與實際的例子來做測試。在實際的例子中，我們所提出的點圖形比對演算法運用在指紋的辨識上，而線圖形比對演算法運用在中文字的辨識上。實驗結果顯示，我們所提出的比對演算法確實對於圖形的任意平移、旋轉和放大（縮小）上擁有不變性。本文共分五章：第一章引言；第二章鬆弛法簡介；第三章我們提出的演算法；第四章實驗結果；第五章討論與結論。New planar pattern matching algorithms based on minimum featurerelations are proposed here. The proposed algorithms include apoint pattern matching algorithm and a line pattern matchingalgorithm. The matching algorithms can be divided into twophases: relaxation process(RP) and select-match-pair process(SMPP). The first phase RP applies minimum feature relations andrelaxation technique to determine the relative probability ofeach possible match pair. The local evidence of registration inthe relaxation process enable the algorithms invariant toarbitrary translations, rotations and scale changes. The secondphase SMPP applies pairwise error bound(PEB) to determine theexact number of match pairs and match error. The tolerance ofnoise is also controlled by PEB. Experiments are tested forgenerated data and real cases. In real cases, the point patternmatching algorithm is applied to fingerprint recognition andthe line pattern matching algorithm is applied to Chinesecharacter recognition. The results proved that the matchingalgorithms are really invariant to arbitrary translations,rotations, and scale changes.