Hardware accelerator for feature matching with binary search tree

• Main Authors: Thathsara, Miyuru, Lam, Siew-Kei, Kawshan, Damith, Piyasena, Duvindu
• Other Authors: College of Computing and Data Science
• Format: Conference or Workshop Item
• Language: English
• Published: 2024
• Subjects: Computer and Information Science; Feature matching; FPGA; Binary search tree; Hardware acceleration
• Online Access: https://hdl.handle.net/10356/179622
• Institution: Nanyang Technological University

Feature matching is an essential step for autonomous robot to localize itself during navigation. However, it is often difficult to achieve the matching in real-time due to limited on-board computing resources. We present an FPGA implementation for stream-processing based feature matching called Binary Search Tree Matcher (BSTM) that utilizes a balanced binary search tree. To improve the matching precision, we integrated a ratio-test (RT) outlier rejection mechanism in our design. Our proposed FPGA-based BSTM is scalable and resource efficient, and significantly faster than the best-performing hardware implementation in the literature. When compared to the commonly used Linear Exhaustive Search (LES) method running on the FPGA, our proposed design is approximately 12X faster.