MaxCon (최대 컨센서스)

최대 컨센서스는 RANSAC이 근사적으로만 풀어내는 최적화 문제입니다. 잔차 함수 $r_i(\theta)$와 인라이어 임계값 $\epsilon$을 가진 측정값이 주어졌을 때, 가능한 한 많은 측정값과 일치하는 모델을 찾습니다:

최대화되는 집합이 컨센서스 집합(인라이어 집합)입니다. 기본 행렬, 호모그래피, 카메라 자세, 또는 포인트 클라우드 정합을 “가장 많은 인라이어로” 적합시키는 것은 모두 이 하나의 문제의 사례입니다.

RANSAC이 이야기의 끝이 아닌 이유

RANSAC은 무작위 최소 샘플링으로 최대 컨센서스를 공략합니다: 높은 확률로 좋은 컨센서스 집합을 반환하지만,

• 무작위입니다 — 동일한 데이터에 대해 두 번 실행하면 다른 답이 나올 수 있습니다;
• 최적성 보장이 없습니다 — 반환된 컨센서스 집합이 실제 최댓값보다 작을 수 있으며, 특히 필요한 샘플 수가 폭증하는 높은 이상치 비율에서 그렇습니다;
• 반환하는 모델은 최소 샘플에 적합된 것이므로, 정제되기 전까지는 잡음에 민감합니다.

최대 컨센서스를 제대로 된 최적화 문제로 연구한다는 것은 다음을 묻는 것입니다: 결정론적으로 정확한 최대화 해를 찾으려면 무엇이 필요한가?

난이도와 정확 알고리즘

나쁜 소식은 근본적입니다: 최대 컨센서스는 일반적으로 NP-난해합니다 — 어떤 측정값의 부분집합을 신뢰할 것인지에 대한 조합 문제이며, P = NP가 아닌 한 모든 사례를 효율적으로 풀 수 있는 알고리즘은 없습니다. 컨센서스 목적 함수는 해석적으로도 다루기 어렵습니다: 이는 $\theta$의 구간별 상수 카운팅 함수로, 거의 모든 곳에서 기울기가 0이므로 일반적인 비선형 최적화로는 직접 다룰 수 없습니다.

따라서 정확한 (전역 최적) 방법은 지수적인 최악 비용을 대가로 지불하지만, 작은 문제에서는 실용적일 수 있습니다:

• 분기 한정 (BnB, Branch-and-bound): 매개변수 공간(예: 회전/이동 공간)을 재귀적으로 분할하고, 달성 가능한 컨센서스의 상한이 지금까지 찾은 최선의 해보다 나쁜 분기를 가지치기합니다. 종료 시 전역 최적이 보장됩니다.
• 활성 집합에 대한 트리 탐색: 이러한 문제의 최적해가 작은 제약 조건의 *기저(basis)로 특징지어진다는 사실을 활용하여, 최선 우선 (A 방식) 전략으로 기저들을 탐색합니다.
• 혼합 정수 계획법: 측정값당 이진 변수 $z_i \in \{0, 1\}$를 도입하고 다음을 풉니다

큰 상수 $M$과 함께, 문제를 기성 MIP 솔버에 넘깁니다.

유용한 재구성이 하나 있습니다: 컨센서스를 최대화하는 것은 위반된 제약 조건의 개수를 최소화하는 것과 동치입니다 — $\ell_0$ 유형의 목적 함수입니다. 이 관점은 MaxCon을 다루기 쉬운 대체 문제들과 연결합니다: $\ell_0$을 $\ell_1$이나 다른 컨벡스 손실로 완화하면 컨벡스 완화 접근법이 되고, 강건 커널을 컨벡스에서 재하강형으로 점진적으로 변형하면 graduated non-convexity (GNC)가 됩니다. 이들은 정확성을 포기하고 다항 시간 실행을 얻으며, 때로는 사후 최적성 증명서를 함께 얻습니다.

실용적인 지형

SLAM에서의 의미

SLAM의 모든 기하학적 추정 단계 — 본질 행렬, PnP, 루프 클로저 검증, 포인트 클라우드 정합 — 는 본질적으로 컨센서스 최대화 문제입니다. 실시간 프론트엔드는 계속해서 RANSAC 계열의 휴리스틱을 사용하겠지만, 정확한 문제를 아는 것은 무엇을 포기하고 있는지를 명확히 해 줍니다: 무작위화된 프론트엔드는 조용히 최적이 아닌 컨센서스 집합을 받아들일 수 있고, 그 위에 세워진 단 하나의 잘못된 루프 클로저가 맵 전체를 뒤틀 수 있습니다. 이것이 잘못된 답이 값비싼 대가를 치르는 SLAM 시스템에서 점점 더 많이 등장하는 증명 가능한 강건 추정 연구 (전역 최적 회전 탐색, TEASER 방식 정합, GNC 백엔드)의 동기입니다.

관련 문서

• RANSAC
• PROSAC
• 컨벡스 완화
• M-Estimator
• TEASER++