Homography Estimation

haeryong·2023년 8월 7일
0

Homography formula

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

[x2y2z2]=[H11H12H13H21H22H23H31H32H33][x1y1z1]\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,yx,y를 각각 zz로 나눠주면 된다.

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

x2=x2/z2=H11x1+H12y1+H13H31x1+H32y1+H33x_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}}

y2=y2/z2=H21x1+H22y1+H23H31x1+H32y1+H33y_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}}

x2(H31x1+H32y1+H33)=H11x1+H12y1+H13x_2'(H_{31}x_1+H_{32}y_1+H_{33})=H_{11}x_1+H_{12}y_1+H_{13}
y2(H31x1+H32y1+H33)=H21x1+H22y1+H23y_2'(H_{31}x_1+H_{32}y_1+H_{33})=H_{21}x_1+H_{22}y_1+H_{23}

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

[000x1y11y2x1y2y1y2x1y11000x2x1x2y1x2][H11H12H13H21H22H23H31H32H33]=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=0Ah=0로부터 h를 얻기 위해서 Singular Value Decomposition을 이용할 수 있다.
A=UΣVTA=U\Sigma V^T이고, VTV^T의 마지막 행의 9개 성분이 우리가 원하는 h이다.

RANSAC

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

  • 적은 수(최소 4쌍)의 point 쌍을 샘플링해 homography를 구함
  • reprojection error를 기준으로 inlier와 outlier를 구분
    reproejction error : (x2H11x1+H12y1+H13H31x1+H32y1+H33)2+(y2H21x1+H22y1+H23H31x1+H32y1+H33)2(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를 이용해 비선형최적화를 진행하는 것을 확인할 수 있다.

1개의 댓글

comment-user-thumbnail
2023년 8월 7일

정보 감사합니다.

답글 달기