FPGA Implementation of Feature Matching in ORB-SLAM2

Abstract

Simultaneous Localization And Mapping (SLAM) is an important component in
solving the problem of autonomous navigation — allowing machines such as selfdriving cars and mobile robots to find their way in the world without human instruction. Though there is a steadily growing body of literature in the field of SLAM, far fewer works currently address using hardware acceleration to speed up this computationally heavy task.

That is precisely the concern of this thesis project, in which one of the largest bottlenecks in feature based visual SLAM — feature matching — is investigated for hardware acceleration. After comparing several state of the art methods, the Hamming Distance Embedding Binary Search Tree (HBST) is identified as the best candidate for a hardware-based feature matching system; and the specifics of such a system design are presented in detail.

As a means of reducing memory requirements by up to 50%, thus enabling a component of the system to reside in on-chip memory, a new way of storing binary trees was invented: the Heterogeneous Binary Tree Array (HBTA). This method enables binary trees with different sizes of data in their internal and leaf nodes to be stored in an array-based layout with significantly less overhead than a traditional approach; thereby enhancing cache performance, prefetching capabilities, and minimizing storage space.

Popular Abstract

What if we could release a swarm of butterfly sized robots to explore and map a
forest? Imagine sending a tiny helicopter, the size of a fist, to fly along a country
road and check it for potholes, all without needing a human to look at it. With
this thesis project, we take a step closer towards that vision of the future.

For robots to do this type of work on their own, they need to be able to
move around on their own, to navigate and find their way in the world. A way of
accomplishing this is known as Simultaneous Localization And Mapping (SLAM),
in which a robot is able to both build up a map of its surroundings and use
that map to navigate at the same time, using a camera to look at the world. This
project looks at one of the most important building blocks of SLAM, called feature
matching, and how to make it as effcient as possible.

There are already many systems using SLAM today, from self-driving cars to
robot vacuum cleaners. These systems run on normal computer chips, programmed
with software which performs all the work required for SLAM. This is all well and
good when you have a car battery to run off or only drive around for half an hour
before going home to charge like a robot vacuum. But if we want to shrink down to
the tiny robots mentioned at the start the battery would drain far too quickly, or
have to be so heavy the robot could barely lift it, when running SLAM in software.

Luckily, there are other options! Computers are great because we can program
them to do anything we want. All it takes is a bit of code and the exact same
computer chip can write emails, play video games, or even send commands to the
Mars rover. But as the saying goes, computers are jacks of all trades and masters
of none. Specialized hardware is the true king of effciency; it's made to do one
job and one job only, but it does it faster and using less battery than a computer.

So to achieve the effciency we strive for, this project developed a specialized
hardware component which speeds up one of the slowest and most energy-intensive
parts of SLAM. An algorithm was found which is both very effcient and suitable
for implementation in hardware, and a design based around this algorithm was
created. Several tricks and optimizations were used to squeeze the best possible
performance from each part of the system, and a brand new invention was created
to cut the memory requirements in half for one of the components! In total, the
design created in this project is expected to improve several hundreds of thousands
of times on the current state of the art's performance, drastically lowering the
battery requirements for the tiny robots of the future.

• author: Lindström, Hannah
• supervisor: Liang Liu; Lucas Ferreira
• organization: Department of Electrical and Information Technology
• course: EITM01 20212
• year: 2022
• type: H2 - Master's Degree (Two Years)
• subject: Technology and Engineering
• keywords: Autonomous navigation, SLAM, Feature matching, FPGA, ORB, Heterogeneous binary tree
• report number: LU/LTH-EIT 2022-857
• language: English
• id: 9073887
• date added to LUP: 2022-02-02 11:06:45
• date last changed: 2022-02-02 11:06:45