• https://arxiv.org/pdf/2001.07715
• https://github.com/MIT-SPARK/TEASER-plusplus

1. 설명

• TEASER (Truncated Least Squares Estimation And SEmidefinite Relaxation)라는 알고리즘을 중심으로, 복잡한 수학적 개념을 포함한 3D 점군 정합(point cloud registration)을 직관적으로 이해할 수 있도록 설명해드리겠습니다.

TEASER: 무엇을 위한 알고리즘인가요?

• TEASER는 3D 점군 정합을 수행하는 알고리즘입니다.
• 쉽게 말해, 두 개의 3D 데이터 세트(예: 스캔한 물체의 점군)를 맞춰서 겹치도록 정렬하는 과정입니다.
• 이 과정은 자율주행, 증강 현실, 로봇공학 등에서 매우 중요한데요, 두 데이터 세트가 정확하게 맞아야 로봇이나 차량이 주변 환경을 이해할 수 있기 때문입니다.

• 하지만 이 정합 문제에는 아웃라이어(outlier)라는 큰 난관이 있습니다.
  • 아웃라이어는 맞지 않는 데이터, 즉 두 데이터 세트를 정렬하는데 방해가 되는 점들을 말합니다.
  • 예를 들어, 잡음(noise)이나 잘못된 측정값이 포함된 경우를 생각해볼 수 있습니다.
• TEASER는 이 아웃라이어가 많을 때도 정확한 정합을 수행할 수 있도록 설계된 알고리즘

TEASER의 핵심 개념과 단계

• TEASER 알고리즘은 3가지 주요 변환인 크기(Scale), 회전(Rotation), 이동(Translation)을 단계적으로 추정하여 두 3D 점군을 맞추는 방식으로 구성되어 있습니다.
• TEASER는 이러한 3가지 변환을 분리해서 계산하는 방식을 사용하여 효율적으로 문제를 해결합니다.
• 각 변환은 아웃라이어의 영향을 최소화할 수 있는 방법으로 계산됩니다.

1. 크기(Scale) 추정

• 먼저, TEASER는 두 점군 사이의 크기 비율을 계산합니다.
• 예를 들어, 동일한 물체가 두 점군에 있는데, 한 점군이 다른 점군보다 2배 더 큰 경우가 있을 수 있습니다.
• 이때 크기를 추정하여 두 점군의 크기를 맞추는 작업을 수행합니다.
• TEASER는 Truncated Least Squares (TLS)라는 방법을 사용하여, 아웃라이어의 영향을 줄이며 정확하게 크기를 계산합니다.

2. 회전(Rotation) 추정

크기를 맞춘 후, TEASER는 두 점군이 같은 방향을 바라보도록 회전 각도를 계산합니다. TEASER는 아웃라이어가 많을 때에도 정확한 회전 각도를 계산할 수 있는 방법을 사용하여, 방해 요소를 무시하고 필요한 각도를 정확히 찾습니다.

이를 위해 TEASER는 복잡한 수학적 접근인 준정규화 이완(Semidefinite Relaxation)을 사용하여 문제를 해결하는데, 이를 통해 높은 아웃라이어 비율에서도 안정적인 회전 추정이 가능합니다.

3. 이동(Translation) 추정

크기와 회전이 맞춰진 후, TEASER는 마지막으로 두 점군을 서로 겹치도록 위치를 조정합니다. 이 과정에서는 각 점의 위치 차이를 최소화하는 방식으로 이동 변환을 추정합니다.

TEASER의 핵심 기술: Truncated Least Squares와 Semidefinite Relaxation

Truncated Least Squares (TLS)

TLS는 TEASER에서 사용되는 핵심 기법으로, 아웃라이어를 무시하면서 오차를 최소화하는 방법입니다. 일반적으로 오차를 계산할 때 모든 데이터를 고려하게 되지만, TLS는 아웃라이어로 간주되는 점들은 제외하고 오차를 계산함으로써 방해되는 요소를 줄입니다.

Semidefinite Relaxation (SDR)

TEASER는 회전 추정을 위해 준정규화 이완(SDR)이라는 복잡한 수학 기법을 사용합니다. 일반적으로 회전 문제는 계산이 매우 어려운데, SDR을 사용하면 이 문제를 좀 더 쉽게 풀 수 있습니다. SDR은 계산의 복잡도를 줄이면서도 정확한 결과를 보장할 수 있는 방법입니다.

TEASER의 강점: 빠르면서도 높은 정확도

• 높은 아웃라이어 내성: TEASER는 전체 데이터의 99%가 아웃라이어일 때에도 정합을 정확하게 수행할 수 있습니다.
• 빠른 계산: TEASER는 복잡한 수학적 최적화 과정을 효율적으로 설계하여 빠르게 정합을 수행합니다.
• 확인 가능한 정확성: TEASER는 결과가 최적인지 확인할 수 있는 방법을 제공하여 안정적인 결과를 제공합니다.

TEASER++: 더 빠른 알고리즘

• TEASER의 개선판인 TEASER++는 기존 TEASER 알고리즘을 더욱 빠르게 만든 버전입니다.
• 특히, TEASER++는 매우 큰 데이터에서도 짧은 시간 안에 정합을 수행할 수 있도록 최적화되어 있으며,
  • 기존의 다양한 정합 알고리즘(RANSAC, ICP 등)보다도 뛰어난 성능을 자랑합니다.

TEASER의 활용 분야

• 로봇공학: 로봇이 주변을 인식하고 물체를 정확히 위치시키는 데 유용합니다.
• 자율주행: 자율주행 차량이 환경을 인식하고 위치를 파악하는 데 사용됩니다.
• 3D 스캔 매칭: 3D 스캔 데이터를 다른 데이터와 맞추는 데 활용할 수 있습니다.

마무리

• TEASER는 3D 점군 데이터를 빠르고 정확하게 맞추기 위해 설계된 알고리즘으로, 많은 아웃라이어가 있는 경우에도 안정적으로 동작합니다.