선형 방식과 비선형 방식

선형 방식

에피폴라 기하학에서 기본 행렬 $\mathbf{F}$ 는 두 카메라 뷰 사이의 점 대응 관계를 설명하는 중요한 역할을 한다. 선형 방식은 관찰된 점들의 대응 관계를 이용하여 $\mathbf{F}$ 를 계산하는 기본적인 방법이다.

선형 방식의 핵심은 최소한 8개의 대응점 쌍을 사용하여 기본 행렬 $\mathbf{F}$ 를 추정하는 것이다. 이러한 방식은 일반적으로 "8점 알고리즘"으로 불리며, 대응점들 사이의 관계를 선형 시스템으로 변환하여 행렬을 계산한다.

에피폴라 제약식은 다음과 같다:

$\mathbf{x}'^\top \mathbf{F} \mathbf{x} = 0$

여기서 $\mathbf{x}$ 는 첫 번째 이미지에서의 한 점, $\mathbf{x}'$ 는 두 번째 이미지에서의 대응점이다. 이 방정식을 최소 8개의 점에 대해 설정하면, 선형 방정식의 시스템을 얻게 된다.

선형 시스템의 구축

각 대응점 쌍 $(\mathbf{x}, \mathbf{x}')$ 에 대해, $\mathbf{x}'^\top \mathbf{F} \mathbf{x} = 0$ 을 전개하면 다음과 같은 선형 방정식을 얻을 수 있다:

$x' \cdot f_{11} \cdot x + x' \cdot f_{12} \cdot y + x' \cdot f_{13} \cdot 1 + y' \cdot f_{21} \cdot x + y' \cdot f_{22} \cdot y + y' \cdot f_{23} \cdot 1 + f_{31} \cdot x + f_{32} \cdot y + f_{33} \cdot 1 = 0$

이를 각 대응점에 대해 전개하면, 다음과 같은 행렬 형태로 표현할 수 있다:

$\mathbf{A} \mathbf{f} = \mathbf{0}$

여기서 $\mathbf{f}$ 는 기본 행렬 $\mathbf{F}$ 의 요소를 벡터화한 것이다. $\mathbf{A}$ 는 대응점에서 계산된 선형 방정식의 계수를 포함하는 행렬이다.

행렬 $\mathbf{A}$ 는 최소한 8개의 대응점이 있을 때 완전히 정의되며, 그 이상의 대응점이 있을 경우 과잉제약(over-determined)된 시스템이 된다. 이러한 시스템은 최소 제곱법을 사용하여 해를 구할 수 있다.

비선형 방식

비선형 방식에서는 선형 방식과 달리, 기본 행렬 $\mathbf{F}$ 를 직접 계산하는 대신, 초기 추정 값을 개선하기 위한 최적화 과정을 포함한다. 비선형 방식은 주로 비선형 최소화 문제로 정의되며, 대응점들 사이의 에피폴라 제약 조건을 만족시키는 $\mathbf{F}$ 를 찾는다.

일반적인 비선형 방식에서는 다음과 같은 최소화 문제를 정의한다:

$\min_{\mathbf{F}} \sum_{i=1}^{N} \left( \mathbf{x}_i'^\top \mathbf{F} \mathbf{x}_i \right)^2$

여기서 $N$ 은 대응점의 수이며, 각 대응점 $(\mathbf{x}_i, \mathbf{x}_i')$ 에 대해 에피폴라 제약 조건을 최대한 만족하도록 $\mathbf{F}$ 를 최적화한다.

비선형 방식의 특징은 초기값에 민감하다는 점이다. 일반적으로 선형 방식으로 계산된 기본 행렬 $\mathbf{F}$ 를 초기값으로 사용하며, 이를 기반으로 최적화 과정을 통해 더 정확한 결과를 도출한다.

비선형 최적화는 보통 반복적인 방식으로 수행되며, 루프 내에서 목표 함수의 기울기를 계산하고 업데이트 과정을 거쳐 점진적으로 해를 개선한다. 이 과정에서는 수치 최적화 알고리즘, 예를 들어 가우스-뉴턴(Gauss-Newton) 방식이나 르벤베르크-마콰르트(Levenberg-Marquardt) 알고리즘 등이 사용된다.

비선형 방식의 최적화 과정

비선형 방식의 최적화는 반복적인 방식으로 이루어지며, 주어진 대응점 집합에 대해 에피폴라 제약식을 최대한 만족시키는 기본 행렬 $\mathbf{F}$ 를 찾는 과정이다. 이 과정은 다음과 같은 단계로 진행된다.

초기화: 기본 행렬 $\mathbf{F}$ 의 초기 추정값은 일반적으로 선형 방식에서 계산된 값을 사용한다. 선형 방식에서 구한 $\mathbf{F}$ 가 최적화 알고리즘의 시작점을 제공하는 역할을 한다.
목표 함수 설정: 비선형 방식에서는 최소화해야 할 목표 함수가 설정된다. 일반적으로 사용되는 목표 함수는 다음과 같다:

$J(\mathbf{F}) = \sum_{i=1}^{N} \left( \mathbf{x}_i'^\top \mathbf{F} \mathbf{x}_i \right)^2$

이 함수는 각 대응점 $(\mathbf{x}_i, \mathbf{x}_i')$ 에 대해 에피폴라 제약 조건을 최대한 만족시키는 방향으로 기본 행렬을 최적화한다.

기울기 계산: 최적화 과정에서 목표 함수의 기울기를 계산하는 단계이다. 기울기는 목표 함수 $J(\mathbf{F})$ 가 기본 행렬 $\mathbf{F}$ 의 어떤 방향으로 변화하는지를 나타낸다. 기울기를 사용하여 $\mathbf{F}$ 를 점진적으로 업데이트한다.
업데이트: 기울기를 계산한 후, 기본 행렬 $\mathbf{F}$ 는 다음과 같이 업데이트된다:

$\mathbf{F}^{(k+1)} = \mathbf{F}^{(k)} - \alpha \nabla J(\mathbf{F}^{(k)})$

여기서 $\mathbf{F}^{(k)}$ 는 $k$ -번째 반복에서의 기본 행렬이고, $\alpha$ 는 학습률을 나타낸다. $\nabla J(\mathbf{F}^{(k)})$ 는 목표 함수의 기울기이다.

반복: 위의 과정을 반복하여 목표 함수 $J(\mathbf{F})$ 의 값을 점진적으로 줄여나간다. 최적화 과정은 수렴할 때까지, 즉 더 이상 목표 함수의 값이 크게 변하지 않을 때까지 반복된다.

비선형 방식의 장점과 한계

비선형 방식은 선형 방식에 비해 몇 가지 중요한 장점과 한계를 가지고 있다. 첫째, 비선형 방식은 대응점의 개수가 많을 때 보다 정확한 기본 행렬을 추정할 수 있다. 이는 초기 선형 추정값을 더욱 세밀하게 조정할 수 있기 때문이다.

그러나 비선형 방식은 초기값에 민감하며, 최적화 알고리즘이 지역 최적해에 빠질 가능성이 있다. 따라서 초기값으로 사용되는 기본 행렬의 품질이 최적화 과정의 결과에 큰 영향을 미친다. 또한 비선형 방식은 계산 비용이 크기 때문에, 실시간 응용보다는 오프라인 처리에 주로 사용된다.

비선형 방식에서 사용하는 대표적인 최적화 알고리즘으로는 다음과 같은 것들이 있다.

르벤베르크-마콰르트 알고리즘 (Levenberg-Marquardt): 비선형 최소 제곱 문제를 해결하기 위한 알고리즘으로, 가우스-뉴턴 알고리즘과 더불어 많이 사용된다.
가우스-뉴턴 알고리즘 (Gauss-Newton): 비선형 최소 제곱 문제에서 목적 함수의 2차 도함수를 근사하여 해를 구하는 방식이다.

이러한 알고리즘들은 각각의 장단점이 있으며, 주어진 문제 상황에 맞는 최적의 알고리즘을 선택하는 것이 중요하다.

선형 방식과 비선형 방식의 비교

계산 복잡도:
선형 방식: 선형 방식은 주로 행렬 연산을 기반으로 하기 때문에 계산 비용이 낮고, 매우 빠르게 결과를 도출할 수 있다. 최소한의 대응점만 있으면 쉽게 기본 행렬 $\mathbf{F}$ 를 계산할 수 있으며, 이는 실시간 응용에도 적합하다.
비선형 방식: 비선형 방식은 반복적인 최적화 과정을 필요로 하기 때문에 계산 비용이 높다. 각 반복마다 기울기를 계산하고 업데이트해야 하므로 시간이 오래 걸리며, 특히 대응점이 많을 경우 계산 시간이 더욱 증가한다. 따라서 실시간 응용보다는 오프라인 처리에 적합하다.
정확도:
선형 방식: 선형 방식은 빠르지만 대응점의 수나 잡음에 민감하며, 정확도가 떨어질 수 있다. 특히 실제 환경에서는 대응점들이 이상적으로 대응되지 않기 때문에 잡음에 영향을 받기 쉽다. 따라서 선형 방식으로 계산된 기본 행렬 $\mathbf{F}$ 는 초기 추정치로 사용되는 경우가 많다.
비선형 방식: 비선형 방식은 초기값을 기반으로 최적화를 진행하여 더 정확한 기본 행렬 $\mathbf{F}$ 를 계산할 수 있다. 대응점의 수가 많거나 잡음이 포함된 데이터에서도 보다 견고한 결과를 도출할 수 있지만, 계산 시간이 길어진다.
초기값의 중요성:
선형 방식: 선형 방식은 초기값이 필요하지 않으며, 주어진 대응점들만으로 기본 행렬을 계산할 수 있다. 이는 선형 방식의 주요 장점 중 하나로, 빠르고 간단하게 결과를 얻을 수 있다.
비선형 방식: 비선형 방식은 초기 추정값에 크게 의존한다. 일반적으로 선형 방식에서 계산된 기본 행렬 $\mathbf{F}$ 를 초기값으로 사용하며, 잘못된 초기값을 사용할 경우 최적화 과정에서 지역 최적해에 빠질 위험이 있다. 따라서 초기값의 품질이 비선형 방식의 성공 여부를 결정짓는 중요한 요소가 된다.
잡음에 대한 민감도:
선형 방식: 선형 방식은 잡음에 민감하며, 데이터에 잡음이 많을 경우 기본 행렬 $\mathbf{F}$ 의 정확도가 크게 떨어질 수 있다. 잡음이 있는 데이터를 처리할 때는 추가적인 필터링이나 정규화가 필요하다.
비선형 방식: 비선형 방식은 잡음에 더 강건하게 작동한다. 최적화 과정에서 잡음의 영향을 최소화하기 위한 다양한 전략을 적용할 수 있으며, 그 결과 잡음이 있는 데이터에서도 더 나은 성능을 발휘할 수 있다.
적용 가능성:
선형 방식: 선형 방식은 빠르고 효율적이기 때문에 실시간 응용이나 대응점이 적은 상황에서 적합하다. 예를 들어, 빠른 계산이 필요한 드론이나 로봇 비전 시스템 등에 유리하다.
비선형 방식: 비선형 방식은 대응점이 많거나 잡음이 포함된 데이터를 처리하는 데 적합하다. 오프라인에서 보다 정확한 기본 행렬을 계산해야 할 때 유용하며, 스테레오 비전이나 3D 복원 등의 응용에서 많이 사용된다.

이와 같이 선형 방식과 비선형 방식은 각각의 특성에 맞는 상황에서 사용되며, 선형 방식은 빠르고 간단하지만 정확도가 떨어질 수 있는 반면, 비선형 방식은 계산이 복잡하지만 보다 높은 정확도를 제공한다. 두 방식을 적절히 결합하여 사용하는 경우도 많다.