Graphics processing unit‐accelerated multi‐resolution exhaustive search algorithm for real‐time keypoint descriptor matching in high‐dimensional spaces
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 efficient...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2016-04-01
|
| Series: | IET Computer Vision |
| Subjects: | |
| Online Access: | https://doi.org/10.1049/iet-cvi.2015.0137 |
| _version_ | 1797684946551177216 |
|---|---|
| author | Chi‐Yi Tsai Chih‐Hung Huang An‐Hung Tsao |
| author_facet | Chi‐Yi Tsai Chih‐Hung Huang An‐Hung Tsao |
| author_sort | Chi‐Yi Tsai |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T00:37:11Z |
| format | Article |
| id | doaj.art-7316acc6f4114b1eab11f4d4dda1f568 |
| institution | Directory Open Access Journal |
| issn | 1751-9632 1751-9640 |
| language | English |
| last_indexed | 2024-03-12T00:37:11Z |
| publishDate | 2016-04-01 |
| publisher | Wiley |
| record_format | Article |
| series | IET Computer Vision |
| spelling | doaj.art-7316acc6f4114b1eab11f4d4dda1f5682023-09-15T09:27:05ZengWileyIET Computer Vision1751-96321751-96402016-04-0110321221910.1049/iet-cvi.2015.0137Graphics processing unit‐accelerated multi‐resolution exhaustive search algorithm for real‐time keypoint descriptor matching in high‐dimensional spacesChi‐Yi Tsai0Chih‐Hung Huang1An‐Hung Tsao2Department of Electrical EngineeringTamkang University151 Ying‐chuan Road, Danshui DistrictNew Taipei City251TaiwanDepartment of Electrical EngineeringTamkang University151 Ying‐chuan Road, Danshui DistrictNew Taipei City251TaiwanDepartment of Electrical EngineeringTamkang University151 Ying‐chuan Road, Danshui DistrictNew Taipei City251TaiwanImage 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.https://doi.org/10.1049/iet-cvi.2015.0137GPU-accelerated multiresolution exhaustive search algorithmgraphics processing unitreal-time keypoint descriptor matchinghigh-dimensional spacesimage keypoint descriptor matchingmultiresolution candidate elimination technique |
| spellingShingle | Chi‐Yi Tsai Chih‐Hung Huang An‐Hung Tsao Graphics processing unit‐accelerated multi‐resolution exhaustive search algorithm for real‐time keypoint descriptor matching in high‐dimensional spaces IET Computer Vision 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 |
| title | Graphics processing unit‐accelerated multi‐resolution exhaustive search algorithm for real‐time keypoint descriptor matching in high‐dimensional spaces |
| title_full | Graphics processing unit‐accelerated multi‐resolution exhaustive search algorithm for real‐time keypoint descriptor matching in high‐dimensional spaces |
| title_fullStr | Graphics processing unit‐accelerated multi‐resolution exhaustive search algorithm for real‐time keypoint descriptor matching in high‐dimensional spaces |
| title_full_unstemmed | Graphics processing unit‐accelerated multi‐resolution exhaustive search algorithm for real‐time keypoint descriptor matching in high‐dimensional spaces |
| title_short | Graphics processing unit‐accelerated multi‐resolution exhaustive search algorithm for real‐time keypoint descriptor matching in high‐dimensional spaces |
| title_sort | graphics processing unit accelerated multi resolution exhaustive search algorithm for real time keypoint descriptor matching in high dimensional spaces |
| topic | 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 |
| url | https://doi.org/10.1049/iet-cvi.2015.0137 |
| work_keys_str_mv | AT chiyitsai graphicsprocessingunitacceleratedmultiresolutionexhaustivesearchalgorithmforrealtimekeypointdescriptormatchinginhighdimensionalspaces AT chihhunghuang graphicsprocessingunitacceleratedmultiresolutionexhaustivesearchalgorithmforrealtimekeypointdescriptormatchinginhighdimensionalspaces AT anhungtsao graphicsprocessingunitacceleratedmultiresolutionexhaustivesearchalgorithmforrealtimekeypointdescriptormatchinginhighdimensionalspaces |