多邊形路徑的比對與應用

Abstract

多邊形路徑的比對，在電腦視覺與圖形識別的領域中，是時常被討論的課題，並且往往被應用在中國字型、波形或是染色體的比對上。本論文將多邊形路徑比對的問題，轉換成找尋字串中最長的相同字元問題，首先我們對曲線編碼後，將每組曲線所對應的字串彼此作比對。而透過Chain Codes與Dynamic Programming的比對技術，我們能夠將原本需人類肉眼判斷相似曲線的工作利用電腦來取代處理，而利用我們改進後的比對方式，另外再加上對判別相似度上的條件，我們將此技術應用至電泳比對實驗及心臟電腦斷層掃描圖的配對實驗中，透過計算機的輔助將降低人工判斷時所需花費之成本，而利用電腦比對後之結果與肉眼判斷相似之曲線的結果幾乎是一致的。

The problem of polygonal paths comparison is an important task in computer vision and pattern recognition. In this thesis we present a method that determine the similarity of curves or contours in two-dimension space. The polygonal path is converted to a chain code. The similarity of contours is obtained using dynamic programming method to match the longest common subsequence. The matching technique is applied to match the lanes in the Pulsed-Field Gel Electrophoresis Image.