점 대응 문제 개요

다중 뷰 기하학에서 중요한 문제 중 하나는 서로 다른 시점에서 촬영된 이미지들 간에 동일한 3차원 점이 어디에 대응되는지 찾는 것이다. 이 문제는 다양한 컴퓨터 비전 응용에서 중요한 역할을 하며, 주로 3차원 구조 복원, 스테레오 비전, 카메라 추정 등에 활용된다.

에피폴라 제약과 기본 행렬

점 대응 문제를 해결하는 과정에서 에피폴라 제약(Epipolar Constraint)이 핵심 역할을 한다. 이는 두 카메라 사이에서의 대응점을 찾는 과정을 단순화시키는 기하학적 제약으로, 두 이미지 사이의 기본 행렬이나 본질 행렬을 통해 설명할 수 있다. 기본 행렬 \mathbf{F}은 두 시점에서 동일한 3차원 점이 각각의 이미지 상에서 나타나는 위치를 제약하는데 사용된다.

만약 \mathbf{x}_1이 첫 번째 이미지에서의 한 점을 나타내고, \mathbf{x}_2가 두 번째 이미지에서의 해당하는 점이라면, 이 두 점은 기본 행렬을 통해 다음과 같은 관계를 만족해야 한다.

\mathbf{x}_2^\top \mathbf{F} \mathbf{x}_1 = 0

여기서: - \mathbf{x}_1 = [x_1, y_1, 1]^\top는 첫 번째 이미지에서의 점의 동차 좌표(homogeneous coordinates), - \mathbf{x}_2 = [x_2, y_2, 1]^\top는 두 번째 이미지에서의 점의 동차 좌표를 나타낸다.

이 제약 조건은 이미지 상의 점들이 에피폴라 선(Epipolar Line) 위에 존재해야 함을 의미하며, 따라서 검색 공간을 2차원이 아닌 1차원으로 줄일 수 있다.

점 대응 문제 해결 방법

점 대응 문제를 해결하기 위한 대표적인 방법은 특징 기반 방법과 직접 방법으로 나눌 수 있다.

1. 특징 기반 방법

특징 기반 방법은 이미지 내에서 특정한 특징점(예: 코너, 에지 등)을 찾아 대응점을 구하는 방식이다. 이러한 특징점들은 이미지가 달라져도 비교적 불변성을 유지하는 특성을 가져야 하며, 주로 다음과 같은 단계로 해결된다.

  1. 특징 추출: 두 이미지에서 각각의 특징점들을 추출한다. 대표적인 알고리즘으로는 SIFT(Scale-Invariant Feature Transform), SURF(Speeded-Up Robust Features), ORB(Oriented FAST and Rotated BRIEF) 등이 있다.
  2. 특징 대응: 추출한 특징점들 간의 대응을 찾아낸다. 이 과정에서는 각 특징점 간의 유사도를 측정하여 대응되는 점들을 결정한다. 유사도는 일반적으로 두 특징점의 디스크립터(descriptor)를 비교하여 측정한다.
  3. 이상치 제거: 대응된 점들 중에서 잘못 대응된 점(Outlier)을 제거하는 과정이 필요하다. 이를 위해 RANSAC(Random Sample Consensus) 알고리즘이 주로 사용된다.

2. 직접 방법

직접 방법은 이미지의 픽셀 강도(intensity) 정보를 직접적으로 이용하여 대응점을 찾는 방식이다. 특징 기반 방법에 비해 픽셀 단위의 미세한 차이를 분석하는 데 더 민감하며, 다음과 같은 단계로 수행된다.

  1. 이미지 피라미드: 서로 다른 해상도의 이미지를 사용하여 처음에는 저해상도에서 대응점을 찾고, 점진적으로 고해상도로 올라가며 정교한 대응을 구한다.
  2. 이미지 정합: 픽셀 강도 차이를 최소화하는 방식으로 대응점을 찾는다. 대표적인 방법으로는 SSD(Sum of Squared Differences), NCC(Normalized Cross-Correlation) 등이 있다.

RANSAC을 통한 이상치 제거

다중 뷰에서의 점 대응 문제에서 가장 큰 난관 중 하나는 잘못된 대응점을 제거하는 것이다. 특징 기반 방법을 사용할 때 특히 이러한 잘못된 대응이 발생할 수 있다. RANSAC(Random Sample Consensus) 알고리즘은 이러한 이상치를 제거하는 데 널리 사용되는 방법이다.

RANSAC 개요

RANSAC은 데이터 포인트 중 일부 이상치(Outlier)가 섞여 있을 때도 모델을 안정적으로 추정하는 알고리즘이다. 기본적인 아이디어는 다수의 데이터 포인트에서 임의의 소표본을 선택하고, 그 소표본으로부터 모델을 추정한 뒤, 해당 모델이 얼마나 많은 데이터 포인트에 잘 맞는지를 평가하는 것이다. 다중 뷰 기하학에서는 점 대응 관계를 나타내는 기본 행렬 \mathbf{F} 또는 본질 행렬 \mathbf{E}를 추정할 때 사용된다.

RANSAC 알고리즘 단계

  1. 임의 샘플 선택: 점 대응 데이터셋에서 임의의 소수의 대응점을 선택한다.
  2. 모델 추정: 선택된 대응점을 사용하여 모델(예: 기본 행렬)을 추정한다.
  3. 내부점 계산: 추정된 모델에 얼마나 많은 점들이 잘 맞는지 평가한다. 이때 에피폴라 제약을 사용하여 대응점이 에피폴라 선 위에 있는지를 확인한다. 즉, 모델과 대응되는 점의 관계가 다음 조건을 얼마나 잘 만족하는지 계산한다. $$ \mathbf{x}_2^T \mathbf{F} \mathbf{x}_1 \approx 0 $$

여기서 오차 범위 내에 있는 점들을 내부점(inlier)이라고 한다. 4. 최적 모델 선택: 여러 번의 반복을 통해 내부점이 가장 많은 모델을 최종 모델로 선택한다.

에피폴라 제약을 통한 RANSAC 적용

RANSAC을 사용하여 기본 행렬을 추정하는 경우, 점 대응이 에피폴라 제약을 만족하는지를 검증한다. 각 반복마다 임의로 선택된 소수의 점들로 기본 행렬 \mathbf{F}를 계산하고, 그 행렬을 기반으로 다른 대응점들이 에피폴라 제약을 만족하는지를 확인한다. 최종적으로 내부점 개수가 가장 많은 기본 행렬을 선택하고, 이를 통해 이상치를 제거한 후 최종 대응점을 결정한다.

점 대응 문제의 난이도와 해결 전략

점 대응 문제는 이미지의 상태(조명, 노이즈, 각도 등)에 따라 매우 달라질 수 있다. 이러한 문제를 해결하기 위한 주요 전략들은 다음과 같다.

이미지 전처리

노이즈가 많은 이미지는 대응점 추정에 큰 영향을 미칠 수 있다. 따라서 이미지 전처리 과정에서 필터링을 통해 노이즈를 줄이는 것이 중요하다. Gaussian 필터나 Median 필터와 같은 방법들이 주로 사용된다.

다중 이미지 융합

두 장 이상의 이미지를 사용할 때, 추가적인 시점에서 촬영된 이미지를 활용하여 보다 정교한 대응점을 추정할 수 있다. 이를 통해 개별 이미지 간의 불확실성을 줄이고, 더욱 정확한 3차원 구조 복원이 가능해진다.

최적화 기법 적용

점 대응 과정에서 발생하는 에러를 최소화하기 위해 최적화 기법이 사용될 수 있다. 이러한 최적화는 픽셀 강도나 기하학적 제약을 기반으로 이루어지며, 특히 Levenberg-Marquardt 알고리즘과 같은 비선형 최적화 기법이 자주 사용된다.

다중 뷰에서의 점 대응의 한계

점 대응 문제는 많은 경우에서 매우 어려운 문제로, 특히 다음과 같은 상황에서 더욱 복잡해진다.

  1. 반복적인 패턴: 반복적인 패턴이 포함된 이미지에서는 서로 다른 위치에 존재하는 점들이 동일하게 인식될 수 있다. 이러한 경우에는 에피폴라 제약만으로 대응점을 정확히 구분하기 어려울 수 있다.
  2. 조명 변화: 이미지 촬영 시점 간에 조명이 크게 변할 경우, 동일한 3차원 점이라도 이미지 상에서 다른 밝기나 명암을 가질 수 있다. 이는 특히 직접 방법을 사용하는 경우에 문제가 된다.
  3. 텍스처가 부족한 영역: 이미지 상에 명확한 텍스처가 없는 영역에서는 대응점을 찾는 것이 매우 어렵다. 이러한 경우, 추가적인 전처리나 후처리 과정이 필요할 수 있다.