Homography Estimation

Homography formula

Homography를 이용해서 camera A의 point에서 camera B의 point로의 변환을 아래와 같이 표현할 수 있다.

$\begin{bmatrix} x_2\\y_2\\z_2 \end{bmatrix}=\begin{bmatrix}H_{11}&H_{12}&H_{13}\\H_{21}&H_{22}&H_{23}\\H_{31}&H_{32}&H_{33}\end{bmatrix}\begin{bmatrix}x_1\\y_1\\z_1\end{bmatrix}$

point는 homogeneous coordinate이므로 실제 2D 좌표를 구할때는 $x,y$를 각각 $z$로 나눠주면 된다.

inhomogeneous coordinate로 위 식을 다시 쓰면 아래와 같다. ($z_1$=1로 설정한다.)

$x_2'=x_2/z_2=\frac{H_{11}x_1+H_{12}y_1+H_{13}}{H_{31}x_1+H_{32}y_1+H_{33}}$

$y_2'=y_2/z_2=\frac{H_{21}x_1+H_{22}y_1+H_{23}}{H_{31}x_1+H_{32}y_1+H_{33}}$

$x_2'(H_{31}x_1+H_{32}y_1+H_{33})=H_{11}x_1+H_{12}y_1+H_{13}$
$y_2'(H_{31}x_1+H_{32}y_1+H_{33})=H_{21}x_1+H_{22}y_1+H_{23}$

위 두 방정식을 $Ah=0$ 형태로 변환할 수 있다.

$\begin{bmatrix}0&0&0&-x_1&-y_1&-1&y_2'x_1&y_2'y_1&y_2'\\x_1&y_1&1&0&0&0&-x_2'x_1&-x_2'y_1&-x_2'\end{bmatrix}\begin{bmatrix}H_{11}\\H_{12}\\H_{13}\\H_{21}\\H_{22}\\H_{23}\\H_{31}\\H_{32}\\H_{33}\end{bmatrix}=0$

한 쌍의 point를 이용해 2 by 9 matrix를 만들 수 있고, n 쌍의 point가 있다면 2n by 9 matrix를 만들 수 있다.

homography matrix의 자유도는 8이고, 한 쌍의 point에 의해 2개의 방정식을 얻을 수 있으므로 네 쌍의 point가 있으면 homography를 계산할 수 있다.

Homogeneous Linear Least Squares

$Ah=0$로부터 h를 얻기 위해서 Singular Value Decomposition을 이용할 수 있다.
$A=U\Sigma V^T$이고, $V^T$의 마지막 행의 9개 성분이 우리가 원하는 h이다.

RANSAC

n 쌍의 point를 이용해 homography를 구할 때, outlier가 존재하는 경우 이때문에 least squares의 결과에 영향이 있을 수 있다. 따라서 RANSAC 알고리즘을 적용해볼 수 있다.
RANSAC 알고리즘은 아래와 같다.

• 적은 수(최소 4쌍)의 point 쌍을 샘플링해 homography를 구함
• reprojection error를 기준으로 inlier와 outlier를 구분
  reproejction error : $(x_2'-\frac{H_{11}x_1+H_{12}y_1+H_{13}}{H_{31}x_1+H_{32}y_1+H_{33}})^2+(y_2'-\frac{H_{21}x_1+H_{22}y_1+H_{23}}{H_{31}x_1+H_{32}y_1+H_{33}})^2$
• 위 과정을 반복해 가장 inlier의 개수가 가장 많은 homography와 inliers를 얻어냄.
• (optional) 위에서 얻은 inlier들을 이용해서 homography 계산.

Non-linear optimization

위에서 진행한 Linear Least Squares는 algebraic(대수적) 에러를 최소화 시킬 뿐 reprojection error를 최소화하지는 않는다고 한다. 따라서 non-linear optimization을 사용해 reprojection error를 최소화하는 H를 새롭게 계산해줄 수 있다.

OpenCV의 findHomography 함수에 대한 docs를 살펴보면 Levenberg-Marquardt method를 이용해 비선형최적화를 진행하는 것을 확인할 수 있다.