臺灣博碩士論文加值系統

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

1. Introduction 1
1.1. Geometric Searching Problems 1
1.2. Pattern Searching 1
2. Previous Work 2
2.1. Blob Analysis 2
2.2. Binary Template Matching 2
2.3. Normalized Cross-Correlation 3
2.4. Multilevel Searching 3
3. Our Algorithm 4
3.1. Training Phase 4
3.1.1. Edge Detection 5
3.1.2. Edge Connection 6
3.1.3. Edge Characterization 7
3.2. Coarse Phase 8
3.2.1. Pattern Searching 8
3.2.2. Direction Scoring Function 11
3.2.3. Refine Results 11
3.3. Fine Phase 12
3.3.1. Pattern Searching 13
3.3.2. Magnitude Scoring Function 13
3.3.3. Refine Results 15
4. Experiments 15
4.1. Accuracy 15
4.2. Execution Time 50
5. Future Work 51
6. Reference 52
7. Appendix 53

[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.