# 선형 방식과 비선형 방식

#### 선형 방식

에피폴라 기하학에서 기본 행렬 $\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}$를 찾는 과정이다. 이 과정은 다음과 같은 단계로 진행된다.

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

$$
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')$에 대해 에피폴라 제약 조건을 최대한 만족시키는 방향으로 기본 행렬을 최적화한다.

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

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

#### 비선형 방식의 장점과 한계

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

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

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

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

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

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

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

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