Fast Feature Matching of UAV Images via Indexing Constraints of Vocabulary Trees

Objectives:  Efficient match pair selection and image feature matching directly affect the efficiency of SfM-based 3D reconstruction for UAV images. This study combines the inverted and direct index structure of the vocabulary tree to achieve the speedup of match pair selection and feature matching for UAV images.   Methods:  First, for match pair selection, vocabulary tree-based image retrieval has been the commonly used technique. However, it depends on the fixed number or fixed ratio threshold for match pair selection, which may cause many redundant match pairs. An adaptive vocabulary tree-based retrieval algorithm is designed for match pair selection by using the "word-image" index structure and the spatial distribution of similarity scores, and it can avoid the drawback of depending on fixed thresholds. Second, for feature matching, the nearest neighbor searching (NNS) method attempts to compute the Euclidean distance exhaustively between two sets of feature descriptors, which causes high computational costs and generates high outlier ratios. Thus, a guided feature matching (GFM) algorithm is presented. It casts the explicit closest descriptor searching as the direct assignment by using the "image-word" index structure of the vocabulary tree. Combining the match pair selection and guided feature matching algorithm, an integrated workflow is finally presented to achieve feature matching of both ordered and unordered UAV images with high precision and efficiency.   Results:  The proposed workflow is verified using four UAV datasets and compared comprehensively with classical NNS algorithms and commercial software packages.   Conclusions:  The experimental results verify that the proposed method can achieve efficient match pair selection and avoid the problem of retrieving too many or too few match pairs that are usually caused by traditional methods using fixed threshold or number strategies; without the sacrifice of matching precision, the speedup ratio of direct assign based feature matching ranges from 156 to 228, and competitive accuracy is also obtained from 3D reconstruction compared with the nearest neighbor searching (NNS) method.