Delaunay Triangualtion-Based Matching Algorithm/
Amira Elnouty
- 2017
- 66 p. ill. 21 cm.
Supervisor: Mohamed A. El helw
Thesis (M.A.)—Nile University, Egypt, 2017 .
"Includes bibliographical references"
Contents: Chapter 1: Introduction ............................................................................................................................... 2 Motivation:................................................................................................................................... 3 Problem Definition ........................................................................................................................ 3 Contributions ............................................................................................................................... 4 Organization of the Thesis ............................................................................................................ 4 Chapter 2: Related Work .............................................................................................................................. 5 Background .................................................................................................................................. 5 2.1.1 Feature Extraction Methods ................................................................................................. 5 2.1.2 Delaunay triangulation .......................................................................................................... 7 Graph‐Based Matching ............................................................................................................... 10 2.2.1 Technical Details about FGM .............................................................................................. 11 Nearest Neighbor‐Based Matching ............................................................................................. 12 Summary of Feature Matching Techniques ................................................................................ 13 Chapter 3: Delaunay Triangulation Based Matching (DTBM) ..................................................................... 14 The DTBM Algorithm ................................................................................................................... 14 3.1.1 Pre‐processing Step: (Line 0 in the pseudo code) ............................................................... 15 3.1.2 Computing Candidate Matches: (Line 7 in the pseudo code) ............................................. 16 3.1.3 Testing Candidates to Decide the Matches: (Lines 8 & 9 in the pseudo code) .................. 20 Bi‐directional DTBM (Bi_DTBM) .................................................................................................. 20 Summary for the Proposed DTBM Algorithms ........................................................................... 20 Chapter 4: DTBM Initialization and Evolution ............................................................................................. 22 Initialization ................................................................................................................................ 22 DTBM with Neighbors Matching ................................................................................................. 24 DTBM with Neighbors Matching and Variable Depth of Neighbors ........................................... 25 DTBM with Edge Matching with No Weighting for Candidate Matches .................................... 26 DTBM with Edge Matching with Weighting for Candidate Matches .......................................... 27 Summary of the Development of the DTBM algorithms ............................................................ 29 Chapter 5: Evaluation, Results and Discussion ........................................................................................... 30 Data ............................................................................................................................................ 31 5.1.1 Extra Dataset ....................................................................................................................... 31 5.1.2 The Middlebury Dataset ..................................................................................................... 31 5.1.3 The Graffiti Dataset ............................................................................................................. 32 5.1.4 The CMU House Dataset ..................................................................................................... 33 Evaluation Metrics ...................................................................................................................... 33 Test the Performance when using a Non‐deterministic Descriptor ........................................... 35 DTBM/Bi_DTBM vs. Neighbor‐Based Techniques (NN, NNDR, Bi‐directional NNDR) ................ 35 5.4.1 Extra Dataset ....................................................................................................................... 36 5.4.2 Middleburry Dataset: .......................................................................................................... 37 5.4.3 House Dataset ..................................................................................................................... 44 5.4.4 The Average overall Performance ....................................................................................... 46 DTBM/Bi_DTBM vs. Graph‐Based Techniques (FGM, RRWM[10]) ............................................. 47 5.5.1 Extra Dataset ....................................................................................................................... 48 5.5.2 Middleburry Dataset ........................................................................................................... 48 5.5.3 House Dataset ..................................................................................................................... 50 Summary and Conclusion on the overall performance: ............................................................. 51 Chapter 6: Conclusions and Future work .................................................................................................... 53 Delaunay Triangulation‐Based Matching .................................................................................... 53 Thesis Contributions ................................................................................................................... 54 Future Work ............................................................................................................................... 54 Bibliography ............................................................................................................................................... 55
Abstract: Feature matching is a fundamental problem in many of the computer vision applications. Various feature matching algorithms have been proposed for this purpose. However, these algorithms suffer from various limitations mainly related to their applicability, efficiency, robustness to resolution, and the discriminating capability of the used feature representation. We present a novel feature matching algorithm based on the spatial relation between the features and their neighboring features. Our algorithm proposes to solve the feature matching problem by defining the spatial relation between each feature set from an image by constructing the Delaunay triangulation between them. We use the Delaunay triangulation to solve the matching problem in a graph traversal manner. In this thesis the goal is to compare the performance of the proposed algorithm of Delaunay Triangulation Based Matching (DTBM) with the performance of simple matching techniques as the nearest neighbor distance ratio (NNDR) and the Bi‐directional NNDR techniques from the accuracy and the time taken points of view. The comparison shows that using the proposed algorithm gives the same accuracy or in some cases better where the descriptor is not discriminative enough in much less time than the others. The proposed algorithm in the bidirectional mode (Bi_DTBM) has an average f‐score of 78.19% over all the datasets tested in this work, and the DTBM has an average of 76.99% which is higher than the NNDR that is of 63.97% and also for the bi_NNDR of 63.31% over all the datasets.