Complexity Analysis of Featured-Based Image Matching

Abstract

A fundamental problem in computer vision is to map a pixel in one image to a pixel in another image of the same scene. This is called the image correspondence problem. Many algorithms have been proposed in literature to solve the problem, however no rigorous analysis has been conducted to study the parameters that contribute to the complexity. The main objective of this paper is to investigate the complexity of matching feature points (pixels) between multiple views of a given scene. The advantage of this work is that a formal analysis is introduced to explore the relationship between the minimum Euclidean distance between the feature points detected on the image and the area of the search region on the overall computational time complexity of the problem.