Parallel K Nearest Neighbor Matching for 3D Reconstruction

Abstract

In recent years, a 3D reconstruction based on structure from motion (SFM) has attracted much attention from the communities of computer vision and graphics. It is well known that the speed and quality of SFM systems largely depend on the technique of feature tracking. If a big volume of image data is inputted for SFM, the speed of this SFM system would become very slow. And, this problem becomes severer for large-scale scenes, which typically needs to capture several thousands of images to recover the point-cloud model of the scene. However, none of the existing methods fully addresses the problem of fast feature tracking. Brute force matching is capable of producing correspondences for small-scale scenes but often getting stuck in repeated features. Hashing matching can only deal with middle-scale scenes and is not capable of large-scale scenes. In this paper, we propose a new feature tacking method working in a parallel manner rather than in a single thread scheme. Our method consists of steps of keypoint detection, descriptor computing, descriptor matching by parallel k -nearest neighbor (Parallel-KNN) search, and outlier rejecting. This method is able to rapidly match a big volume of keypoints and avoids to consume high computation time, then yielding a set of correct correspondences. We demonstrate and evaluate the proposed method on several challenging benchmark datasets, including those with highly repeated features, and compare to the state-of-the-art methods. The experimental results indicate that our method outperforms the compared methods in both efficiency and effectiveness.

Keywords

• 3D reconstruction
• K nearest neighbor
• feature matching
• structure from motion
• parallel computing