Delaunay Triangualtion-Based Matching Algorithm/ Amira Elnouty

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.

Text in English, abstracts in English.