{"id":477,"date":"2020-08-20T13:37:45","date_gmt":"2020-08-20T13:37:45","guid":{"rendered":"https:\/\/www.kudan.io\/jp\/?p=477"},"modified":"2020-11-17T13:53:34","modified_gmt":"2020-11-17T13:53:34","slug":"visual-slam-the-basics","status":"publish","type":"post","link":"https:\/\/www.kudan.io\/jp\/archives\/477","title":{"rendered":"Visual SLAM: The Basics"},"content":{"rendered":"

\u200bSLAM\u306b\u306f\u591a\u304f\u306e\u5f62\u5f0f\u3084\u624b\u6cd5\u304c\u3042\u308a\u307e\u3059\u304c\u3001\u307e\u305a\u306f\u6a5f\u80fd\u30d9\u30fc\u30b9\u306evisual SLAM\u304b\u3089\u59cb\u3081\u307e\u3057\u3087\u3046\u3002Direct Visual SLAM\u3084\u3001\u6df1\u5ea6\u30bb\u30f3\u30b5\u4ed8\u304d\u30ab\u30e1\u30e9\u3092\u4f7f\u7528\u3059\u308bSLAM\u3001LiDAR\u306a\u3069\u306e\u4ed6\u306eSLAM\u624b\u6cd5\u306b\u3064\u3044\u3066\u306f\u3001\u4ee5\u964d\u306e\u8a18\u4e8b\u3067\u8aac\u660e\u3057\u307e\u3059\u3002<\/p>\n

\u307e\u305a\u306f\u3001Visual SLAM\u306b\u3064\u3044\u3066\u3001\u6982\u8aac\u3057\u307e\u3059\u3002\uff08\u4ee5\u4e0b\u3001\u82f1\u6587\u306e\u307f\uff09<\/p>\n

\n

\"\"<\/p>\n

In my last article<\/a>, we looked at SLAM from a 16km (50,000 feet) perspective, so let\u2019s look at it from 2m. Not close enough to get your hands dirty, but enough to get a good look over someone\u2019s shoulders. SLAM can take on many forms and approaches, but for our purpose, let\u2019s start with feature-based visual SLAM. I will cover other SLAM approaches such as direct visual SLAM, and those that use cameras with depth sensors, and LiDAR in subsequent articles.<\/p>\n

As the name implies, visual SLAM utilizes camera(s) as the primary source of sensor input to sense the surrounding environment. This can be done either with a single camera, multiple cameras, and with or without an inertial measurement unit (IMU) that measure translational and rotational movements.<\/p>\n

Let\u2019s walk through the process chart and see what happens at each stage.<\/p>\n

\"\"<\/p>\n

Sensor\/Camera Measurements: Setup<\/strong><\/h3>\n

In order to make this a bit more concrete, let\u2019s imagine a pair of augmented reality glasses. For simplicity, the glasses have two cameras mounted at the temple and an IMU centered between the cameras. The two cameras provide the stereo vision to make depth estimations easier, and the IMU will help provide better movement estimations.<\/p>\n

\"\"<\/p>\n

There are a couple specifications for the camera that help with SLAM: global shutter and grayscale sensor. Also, the tracking cameras don\u2019t have to be super high-resolution, and typically a VGA (640×480 pixel) camera is sufficient (more pixels, more processing). Let\u2019s also assume there is a 6-axis IMU: motion on the x, y and z-axis, and pitch, yaw and roll. Finally, these sensors should be synchronized against a common clock to match the sensor outputs against each other.<\/p>\n

Let’s start solving the puzzle<\/strong><\/h3>\n

I find the process of completing a jigsaw puzzle as a good analogy for some major components of the SLAM process. The processes described below are mostly conceptual and simplified to help in understanding the overall mechanisms involved.<\/p>\n

When the system is initialized, and the cameras are turned on, you are given your first piece of the puzzle. You don\u2019t know how many pieces there are, and you don\u2019t know what part of the puzzle you are looking at. You have your first stereo images and IMU readings.<\/p>\n

Feature Extraction: Distortion correction<\/strong><\/h3>\n

Most camera lenses will introduce some level of distortion to the captured images. There will be distortion from the design of the lenses, as well as distortion in each lens from minute differences during manufacturing. We can \u201cundistort\u201d the image through a distortion grid that transforms the image close to its original representation.<\/p>\n

\"\"<\/p>\n

Feature Extraction: Feature points<\/strong><\/h3>\n

Features in computer vision can take on a number of forms, and don\u2019t necessarily correspond to what humans think of as features. Features typically take the form of corners, or blobs, a collection of pixels that uniquely stand out, and should be able to be consistently identified from an image, and occasionally edges. The figure below depicts the features detected (left), how they would be represented in a map (right).<\/p>\n

\"\"<\/p>\n

Feature Extraction: Feature matching and depth estimation<\/strong><\/h3>\n

\"\"<\/p>\n

Given these stereo images, we should be able to see overlapping features between the images. These identical features can then be used to estimate the distance from the sensor. We know the orientation of the cameras and the distance between them. We use this information to perform image rectification – the mapping pixels between the two images against a common plane. This is then used to determine the disparity of the common features between the two images. Disparity and distance are inversely related, such that as the distance from the camera increases, the disparity decreases.<\/p>\n

Now, we can estimate the depth of each of the features using triangulation.<\/p>\n

\"\"<\/p>\n

In a single camera scenario, we cannot infer depth from a single image, but as the camera moves around, depth can be inferred through parallax by comparing the features in subsequent images.<\/p>\n

Data association<\/strong><\/h3>\n

The data association step takes the features detected, along with its estimated location in space, and builds a map of these features with regards to the cameras. As this process continues through subsequent frames, the system continually takes new measurements, and associates features to known elements of the map, and prunes uncertain features.<\/p>\n

As we track the motion of the camera, we can start making predictions based on the known features, and how they should change based on the motion.<\/p>\n

\"\"<\/p>\n

The constraint of computing resources and time (especially real-time requirements) creates a forcing function for SLAM, where the process becomes a tradeoff between map accuracy, and processing resource and time.\u00a0As the measurements of features, and location\/pose increase over time, representation of the observed environment has to be constrained and optimized.\u00a0We\u2019ll take a look at some of these tools, and different approaches to optimizing the model.<\/p>\n

Location, Pose and Map Update: Kalman filters<\/strong><\/h3>\n

As the camera moves through space, there is increasing noise and uncertainty between the images the camera captures and its associated motion.\u00a0Kalman filters reduce the effects of noise and uncertainty among different measurements to model a linear system more accurately by continually making predictions, updating and refining the model against the observed measurements.\u00a0For SLAM systems, we typically use extended Kalman filters (EKF), which takes nonlinear systems, and linearizes the predictions and measurements around their mean.<\/p>\n

\"\"<\/p>\n

Utilizing a probabilistic approach, Kalman filters take into account all the previous measurements and associate the features to the latest camera pose through the use of a state vector and a covariance matrix for each feature against one another.\u00a0However, all noise and states are assumed to be Gaussian.\u00a0As you can imagine as the tracked points grow, the computation becomes quite expensive, and harder to scale.<\/p>\n

\"\"<\/p>\n

Location, Pose and Map Update: Particle filters<\/strong><\/h3>\n

In contrast to Kalman filters, particle filters treat each feature point as a particle in space with some level of positional uncertainty. At each measurement this uncertainty is updated (normalized and re-weighted) against the predicted position with regard to the camera movement. Unlike Kalman filters, particle filters can handle noise from any distribution, and states can have a multi-modal distribution.<\/p>\n

\"\"<\/p>\n

Location, Pose and Map Update: Bundle adjustment<\/strong><\/h3>\n

As the number of points being tracked in space along with corresponding camera poses increase, bundle adjustment is an optimization step that performs a nonlinear least squares operation on the current model.\u00a0Imagine a \u201cbundle\u201d of light rays from all the features connected to each of the camera observations, and \u201cadjusted\u201d to optimize these connections directly to the sensor position and orientation as in the figure below.<\/p>\n

\"\"<\/p>\n

Bundle adjustment is a batch operation, and not performed on every captured frame.<\/p>\n

Location, Pose and Map Update: Keyframe<\/strong><\/h3>\n

Keyframes are select observations by the camera that capture a \u201cgood\u201d representation of the environment.\u00a0Some approaches will perform a bundle adjustment after every keyframe.\u00a0 Filtering becomes extremely computationally expensive as the map model grows, however keyframes enable more feature points or larger maps, with a balanced tradeoff between accuracy and efficiency.<\/p>\n

\"\"<\/p>\n

Post-update<\/strong><\/h3>\n

Once\u00a0the update step completes, the 3D map of the current environment is updated, and the position and orientation of the sensor within this map is known.\u00a0There are two important concepts that loosely fit into this final step – a test to see if the system has been here before, and what happens when the system loses tracking or gets lost.<\/p>\n

Post update: Loop closure<\/strong><\/h3>\n

As the system continues to move through space and build a model of its environment, the system will continue to accumulate measurement errors and sensor drift, which will be reflected in the map being generated.\u00a0Loop closure occurs when the system recognizes that it is revisiting a previously mapped area, and connects previously unconnected parts of the map into a loop, correcting the accumulated errors in the map.<\/p>\n

\"\"<\/p>\n

Post update: Relocalization<\/strong><\/h3>\n

The term localization in SLAM is the awareness of the system\u2019s orientation and position within the given environment and space.\u00a0Relocalization occurs when a system loses tracking (or initialized in a new environment), and needs to assess its location based on currently observable features.\u00a0If the system is able to match the features it observes against the available map, it will localize itself to the corresponding pose in the map, and continue the SLAM process.<\/p>\n

Final words<\/strong><\/h3>\n

With the goal of trying not to be too mathy and technical, and yet conceptually descriptive enough to help get a depth of understanding of the processes that take place within one type of SLAM system, this goes a bit beyond my \u201c5 minute read\u201d target, but I think it\u2019s essential to cover these fundamental concepts for visual SLAM to help with future topics.<\/p>\n

Let me know your thoughts, comments and questions.<\/p>\n","protected":false},"excerpt":{"rendered":"

\u200bSLAM\u306b\u306f\u591a\u304f\u306e\u5f62\u5f0f\u3084\u624b\u6cd5\u304c\u3042\u308a\u307e\u3059\u304c\u3001\u307e\u305a\u306f\u6a5f\u80fd\u30d9\u30fc\u30b9\u306evisual SLAM\u304b\u3089\u59cb\u3081\u307e\u3057\u3087\u3046\u3002Direct Visual SLAM\u3084\u3001\u6df1\u5ea6\u30bb\u30f3\u30b5\u4ed8\u304d\u30ab\u30e1\u30e9\u3092\u4f7f\u7528\u3059\u308bSLAM\u3001LiDAR\u306a\u3069\u306e\u4ed6\u306eSLAM\u624b\u6cd5\u306b\u3064\u3044 […]<\/p>\n","protected":false},"author":1,"featured_media":242,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":""},"categories":[3],"tags":[47,16,73,7,13,74,63,30,61],"acf":[],"aioseo_notices":[],"jetpack_featured_media_url":"https:\/\/www.kudan.io\/jp\/wp-content\/uploads\/sites\/3\/2020\/06\/blog.jpg","_links":{"self":[{"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/posts\/477"}],"collection":[{"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/comments?post=477"}],"version-history":[{"count":2,"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/posts\/477\/revisions"}],"predecessor-version":[{"id":494,"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/posts\/477\/revisions\/494"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/media\/242"}],"wp:attachment":[{"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/media?parent=477"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/categories?post=477"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.kudan.io\/jp\/wp-json\/wp\/v2\/tags?post=477"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}