벡터 외적을 이용한 직선의 교점 구하기

이미지 평면위의 네 점(픽셀) p1, p2, p3, p4가 주어졌을 때, 두 직선 p1p2, p3p4의 교점을 벡터의 외적(cross product)를 이용하여 구하는 방법입니다.

 

[두 직선의 교점 구하기]

먼저, 네 점의 픽셀 좌표를 homogeneous 좌표로 변환하고 3D 벡터로 해석한다 (카메라 원점과 이미지 평면위의 점을 잊는 벡터).

직선1: $p_1 = (x_1, y_1, 1)$, $p_2 = (x_2, y_2, 1)$

직선2: $p_3 = (x_3, y_3, 1)$, $p_4 = (x_4, y_4, 1)$

 

벡터의 외적을 이용하여 $v$를 계산

$v = (p_1 \times p_2) \times (p_3 \times p_4)$

 

계산된 결과가 $v = (x, y, w)$라면 두 직선의 교점의 좌표는 $(x/w, y/w)$로 주어진다.

 

[원리]

네 점 p1, p2, p3, p4를 3D 좌표계(카메라 좌표계)에서 이미지 평면 위에 있는 점으로 생각하자. 그리고 이 점들은 3차원 공간에서 카메라 원점(C)으로부터의 3D 벡터들로 해석할 수 있다. 이 때, 카메라 원점 C와 점 p1, p2를 지나는 평면을 생각하면 두 벡터 $p_1$, $p_2$의 외적 $n_1 = p_1 \times p_2$는 이 평면의 normal 벡터이다. 마찬가지로, $n_2 = p_3 \times p_4$은 C와 p3, p4를 지나는 평면에 수직인 벡터이다. 이 때, 두 평면의 교선을 $v$라 하면 $v$는 카메라 원점 C를 지나면서 두 직선 p1p2, p3p4의 교점을 지난다. 교선 $v$는 두 평면 위에 있으므로 $n_1$과도 수직이고 $n_2$와도 수직이다 (평면 위에 모든 벡터는 그 평면의 normal 벡터와 수직이다). 즉, $v = n_1 \times n_2$ (homogeneous 좌표에서 scale은 무시).

 

[여러 직선의 교점 구하기]

이미지 평면에 존재하는 여러 line segment들의 최소자승(least squares) 교점을 구하는 문제를 생각해 보자. Line segment l1, l2, ...로부터 구한 normal 벡터(line segment의 양 끝점과 카메라 원점을 지나는 평면의 normal 벡터)들을 n1, n2, ...라 하자. 최소좌승 교점을 v라 하면, v는 모든 normal 벡터들과 수직인 벡터이다.

$$v = \arg \min_v \sum_{i=1}^{n}{( n_i^T v)^2 }$$

그리고, 이러한 v는 ni들을 행벡터로 갖는 행렬 A에 대해 Av = 0의 해를 구함으로써 구할 수 있다.

 

☞ 관련 원리는 벡터의 외적 및 homogeneous 좌표에 대한 이해가 필요하며, [영상처리] - [영상 Geometry #2] Homogeneous Coordinates 글 참조하기 바랍니다.

 

by 다크 프로그래머