Fast Geometric Searching Algorithm

我們提出一種幾何圖形搜尋的演算法。我們的演算法包含三個步驟:訓練、粗略搜尋及詳細搜尋。有別於像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.