Graphics processing unit‐accelerated multi‐resolution exhaustive search algorithm for real‐time keypoint descriptor matching in high‐dimensional spaces

Abstract

Image keypoint descriptor matching is an important pre‐processing task in various computer vision applications. This study first introduces an existing multi‐resolution exhaustive search (MRES) algorithm combined with a multi‐resolution candidate elimination technique to address this issue efficiently. A graphics processing unit (GPU) acceleration design is then proposed to improve its real‐time performance. Suppose that a scale‐invariant feature transform like algorithm is used to extract image keypoint descriptors of an input image, the MRES algorithm first computes a multi‐resolution table of each keypoint descriptor by using a L1‐norm‐based dimension reduction approach. Next, a fast candidate elimination algorithm is employed based on the multi‐resolution tables to remove all non‐candidates from a candidate matching list by using a simple L1‐norm computation. However, when the MRES algorithm was implemented on the central processing unit, the authors observed that the step of multi‐resolution table building is not computationally efficient, but it is very suitable for parallel implementation on the GPU. Therefore, this study presents a GPU acceleration method for the MRES algorithm to achieve better real‐time performance. Experimental results validate the computational efficiency and matching accuracy of the proposed algorithm by comparing with three existing methods.

Keywords

• GPU-accelerated multiresolution exhaustive search algorithm
• graphics processing unit
• real-time keypoint descriptor matching
• high-dimensional spaces
• image keypoint descriptor matching
• multiresolution candidate elimination technique