2-3 Trees

• DBMS(Database management System)

2-3-4 Trees

Red-Black Trees

1. its a height balanced binary search tree, similar to 2-3-4 tree
2. Every node is Red or Black
3. Root of a Tree is Black
4. Null is also Black
5. Number of Blacks on path from root to leaf are same
6. No 2 consecutive Red, Parent and children of Red are Black
7. New inserted Node is Red
8. Height in logn <= H<= 2logn

Red-Black Deletion

Bag of Visual words

• Limitation of previous methods
  • What if only use simple feature point matching?
    • high computational time
    • If lighting environment is different, comparison using descriptor is unstable.
• Bag of Visual Words
  • Let’s explain the features of the frame in ‘words’?!
  • Process
    1. 영상 내에서 ‘단어’의 개념을 결정하여 하나의 ‘사전’을 구성한다
    2. 단어(히스토그램)을 통해 영상 전체를 설명한다. 이 설명은 벡터 형태로 변환된다.
    3. 서로 다른 영상 간 유사성을 검사한다.

Visual Codebook

Similarity Measurement

DBoW

Additional Issues

Reference

SLAM KR

Visual SLAM Workflow

Mapping

• Usefulness of Map in SLAM
  • Save Map-Save map to place robot on map at next boot
  • Navigation-Control the robot to find and move to the target point
  • Obstacle avoidance- Lack of feature points only, Dense map required
  • 3D restoration-visualization, reconstruction of surrounding environment
  • Interaction-Interaction between people and map (ex. AR, robot command execution)
• Necessity of Dense Map Generation

Dense Map

• Triangulation after moving the camera using a monocular camera(using current and previous frame)
• Calculate the pixel distance using the baseline using a stereo camera
• RGB-D 카메라 사용

Stereo Vision

• Epipolar line상에서 block matching을 통해 corresponding point 결정

Probabilistic Depth Sensor

• Gaussian distribution depth filter
  • When the search range is long, convex functions are generally not obtained.
  • Instead of using a single value to find true depth from multiple peaks, use probability distribution

Probabilistic Depth Sensor - Uncertainty

1. Initialize gaussian distribution to each pixel depth
2. Perform epipolar line and block matching from new frame
3. Calculate depth and uncertainty through triangulation based on geometric relationship
4. Incorporate current observations into previous estimates
5. If it converges, the calculation stops, otherwise it returns to step 2.

Reference

SLAM KR

Loop Closure Detection

• Frontend: Feature extraction, trajectory/map initial value provision
• Backend: data optimization
• Generated errors are accumulated by considering the relationship between adjacent frames.(인접 frame들의 관계만 고려하면 생성된 에러들이 누적됨)
  • Inaccurate results in long-term estimation, overall inconsistent results
• Backend-post-error estimation, but…
• Good models + Bad data = Bad analysis
• Loop closure detection: provide long-term constraint
  • e.g., Transform the pose between x1-x100 nodes in order
  • Camera passes through the same location and collects similar data
  • How can you effectively detect a camera passing through the same place?
• Loop Closure Detection: a very important part of the SLAM system
  • Better closure detection → Better input to backend pose graph → better output
  • Influences the accuracy of the map over time with estimated trajectories
  • Improved accuracy and robustness of the entire SLAM
• VO: front + backend, local consistency
• V-SLAM: VO + loop closure/global backend, global consistency

How Loop Closure Detection Works?

• Easiest way: any two images → feature correspondence → are they similar?
• Any two images can have a loop back → O(n^2)
• Random sample: randomly extract past data and detect loopback
• As data increases, the probability determined by the loop decreases → detection efficiency decreases
• Odometry based
  • Detect whether there is a loopback relationship when the current camera moves to a position near the previous position
• Appearance based
  • Determine loop closure detection relationship based on the similarity between two images
  • Similarity of images?

Similarity of Images

Precision and Recall

• Loop closure detection algorithm should…

Reference

SLAM KR

Graph SLAM

• Graph-based formulation of the SLAM problem by Lu and Milios in 1997
• Build the graph and find the robot poses and landmarks that minimize the error

• Spring-mass model

Front-end and Back-end

• Front-end
  • construct the graph using the odometry and sensory measurements by the robot
  • Data association
  • 즉 Feature Based로 구해진 MapPoint 및 키프레임 포즈 든, Direct Method로 Intensity를 통해 구해진 MapPoint 및 키프레임 포즈든, 키 데이터들을 데이터 베이스에다가 저장 하여 Covisibility 등을 생성
• Back-end
  • input
    • The completed graph with all of the constraints
      • 데이터 베이스에 Covisibility를 Essential Graph로 최적화 시기거나 BA방법 등을 사용하여서 Camera Pose 와 MapPoint 교정
  • Output
    • The most probable configuration of robot poses and map features
      • 현재 프레임에서 얻어지는 Camera Pose와 MapPoints의 Pose를 얻을 수 있음
  • Graph optimization
    • Find the system configuration that produces the smallest error
    • 데이터 베이스에 저장된 데이터들을 가지고 최적화

Maximum Likelihood Estimation

• Probability
  • The ratio at which the observed value will appear in a given probability distribution.
• Likelihood
  • Concept complementary to probability
  • The ratio at which a given observation will yield this probability distribution
  • 즉 확률 분포를 움직여서 꼭대기 점을 얻는 파라미터

1-Dimensional Case

• Negative Log를 취해주면 Minimum 값을 구할 수 있다.

N-Dimensional Case

• Q is covariance of Measurement(Measurement noise), R is covariance of Motion Model(Process noise)

Pose Graph Optimization(PGO)

• 간혈적으로 랜드마크를 사용
• Disadvantages of bundle adjustment, graph slam
  • Over time, the trajectory of the robot increases and the map continues to grow in size.
  • As the size of the map grows, the number of constraints to be calculated increases exponentially.
• Can I ignore the landmark(MapPoints) when to perform optimization?
• Graph optimization considering only robot pose
• When the initial estimation of the robot pose using the landmark is completed, the location of the landmark is no longer optimized, and only the connection between the camera poses is optimized.

Least Squares Optimization

Structure of Linearized System

Pseudo Code

PGO on a Manifold

• Overall objective function form (least squares)

• T는 R,T 행렬로 (4x4)

Experiment

• 빨간 부분은 에러값

Reference

SLAM KR