fitting의 목표는 관찰된 데이터를 가장 잘 설명하는 파라메트릭 모델을 찾는 것이다. 우리는 데이터와 특정 모델 파라미터의 추정 사이의 선택된 fitting error를 최소화하여 그러한 모델의 최적의 파라미터를 얻는다. 전통적인 예는 주어진 $(x, y)$ 점의 집합에 선을 fitting하는 것이다. 이 수업에서 본 다른 예는 서로 다른 이미지에 대응점들의 집합 사이의 2d homography $H$를 계산하거나 eight-point algorithm을 사용하여 fundamental matrix $F$를 계산하는 것이 있다.
$N$개의 일련의 2d 점 $\{(x_i, y_i)\}_{i=1}^N$가 주어지면, least-squares fitting의 방법은 $y$ 차원의 제곱 에러가 최소화되도록 선 $y = mx+b$를 찾으려 한다. 그림 1 참조.
구체적으로 우리는 방정식 1에서 주어진 $y_i$와 모델 추정치 $\hat{y}_i = mx_i + b$ 사이의 squared residual의 합을 최소화하도록 하는 모델 파라미터 $w = [m \quad b]^\top$을 찾기를 원한다. 우리는 residual을 $y_i = \hat{y}_i$로 정의한다.
$$ \begin{aligned} E &= \sum_{i=1}^{N} (y_i-\hat{y}i)^2 \\ &= \sum{i=1}^N (y_i - mx_i-b)^2 \end{aligned} \tag{1-2} $$
이것을 행렬 표기로 다음처럼 작성할 수 있다.
$$ \begin{aligned} E &= \sum_{i=1}^N (y_i - \begin{bmatrix} x_i & 1 \end{bmatrix} \begin{bmatrix} m \\ b \end{bmatrix})^2 \\ &= \|\begin{bmatrix} y_1 \\ \vdots \\ y_N \end{bmatrix} - \begin{bmatrix} x_1 & 1 \\ \vdots & \vdots \\ x_N & 1\end{bmatrix}\begin{bmatrix} m \\ b\end{bmatrix}\|^2 \\ &= \|Y - Xw\|^2 \end{aligned} \tag{3-5} $$
residual은 이제 $r = y-Xw$이다. 우리는 $X$가 skinny이고 full rank라고 가정한다. 우리는 residual squared의 norm을 최소화하는 $B$를 찾기를 원한다. 이것은 다음처럼 작성할 수 있다.
$$ \begin{aligned} \|r\|^2 &= r^\top r \\ &= (y-Xw)^\top(y-Xw) \\ &= y^\top y - 2y^\top Xw + w^\top X^\top X w \end{aligned} \tag{6-8} $$
그러면 $w$에 대한 residual의 gradient를 $0$으로 설정한다. $X^\top X$가 대칭임을 떠올려라.
$$ \begin{aligned} \nabla_w\|r\|^2 &= -2X^\top y + 2X^\top Xw \\ &= 0 \end{aligned} \tag{9-10} $$
이것은 normal equations를 이끈다.
$$ X^\top Xw = X^\top y \tag{11} $$
이제 방정식 12에서 $w$에 대한 닫힌 형식의 해를 갖는다. $A$는 full rank이므로 $A^\top A$는 가역이다.
$$ w = (X^\top X)^{-1} X^\top y \tag{12} $$
그러나 이 방법은 수직선($m$이 정의되지 않음)을 설명하는 점을 fitting하는데 완전히 실패하는 것에 유의하라. 이 경우에 $m$은 매우 큰 수로 설정되어 수치적으로 불안정한 해를 이끈다. 이것을 해결하기 위해 $ax + by + d = 0$ 형식의 대안 line formulation을 사용할 수 있다. $b = 0$을 설정하면 수직선을 얻을 수 있다. 여기서 이 선 표현에 관한 생각을 하나 할 수 있다. 선 방향(slope)는 $\vec{\bold{n}}$에 의해 주어지며, $(x, y) \cdot (a, b) = xa + by = 0$를 만족하는 $(x, y)$의 집합은 $\vec{\bold{n}}$에 수직인 선이다. 그러나 선은 $(x_0, y_0)$로 임의로 이동할 수 있다. 따라서 다음을 갖는다.