快速幾何圖形搜尋演算法

Fast Geometric Searching Algorithm

顏慕帆(Mu-Fan Yen)

指導教授 ： 傅楸善

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2007年)

https://doi.org/10.6342/NTU.2007.00222

摘要

我們提出一種幾何圖形搜尋的演算法。我們的演算法包含三個步驟:訓練、粗略搜尋及詳細搜尋。有別於像NCC (normalized cross-correlation)般完整比對搜尋樣本，我們從中沿著邊擷取出樣本點。這種方法降低搜尋時間因為比對的次數遠小於NCC的方法。在經過比對後，我們有一些可能的結果，且這些結果都擁有一個分數。這樣的分數也就是搜尋樣本和比對出的結果之間的相似程度。我們可以將此分數跟預先定義的數值做比較來決定一個找到的結果是否是真正的結果。

關鍵字

幾何搜尋 ； 訓練 ； 樣本點

並列摘要

We propose an algorithm to achieve geometric search. Our algorithm includes three phases: training phase, coarse phase, and fine phase. Instead of comparing the whole pattern with image like NCC (normalized cross-correlation) does, we extract some sample points along edges. This method reduces searching time because the number of comparisons is smaller than NCC. After matching, we have a list of possible instances with scores. Such score means the similarity between the pattern and the matched instance. We can compare these scores with a predefined threshold to decide a found instance to be a true instance or not.

並列關鍵字

geometric searching ； training ； sample point

參考文獻

[1] Cognex, “Cognex Corporation,” http://www.cognex.com/products/VisionTools/PatMax.asp, 2007.

[2] W. M. Silver, A. Garakani, and A. Wallack, “Apparatus and Method for Detection and Sub-pixel Location of Edges in a Digital Image,” U.S. Patent#6,690,842 B1, 2004.

[3] W. M. Silver, E. J. McGarry, M. L. Hill, N. Foster, S. Nichani, and W. P. Foster, “Method for Fast, Robust, Multi-Dimensional Pattern Recognition,” U.S. Patent#7,016,539 B1, 2006.

[4] Wikipedia, “Wikipedia,” http://en.wikipedia.org/wiki/pattern_recognition, 2007.