3D Transformations(변환):: Geometry of Image Formation

Published by onesixx on

https://darkpgmr.tistory.com/81

(3D 비전 geometry 4번째 파트 3D 변환입니다)

4. 3D 변환 (3D Transformations)

컴퓨터 비전에서 관심있는 3D 변환은 회전과 평행이동 뿐입니다 (즉, rigid 변환). 하늘에 떠 있는 비행기가 갑자기 커지거나 로보트로 변신하는 것 등은 관심사항이 아닙니다.

4.1 변환 행렬

3차원 공간의 점 (X, Y, Z)를 X축, Y축, Z축을 중심으로 θ 라디안(radian) 회전시키는 행렬을 각각 Rx(θ), Ry(θ), Rz(θ)라 하면 이들은 다음과 같다.

 — (1)

 — (2)

 — (3)

이 때, 회전방향은 아래 그림과 같이 각 축에 대해 반시계 방향이다 (오른손 주먹을 말아쥐고 엄지를 들었을 때 엄지 방향이 회전축 방향, 말아쥔 손가락 방향이 회전방향).

이제 위 3개의 기본 회전변환을 조합하면 임의의 3D 회전을 표현할 수 있다.

 — (4)

좌표축이 아닌 임의의 단위벡터 u = (ux, uy, uz)을 회전축으로 한 회전변환 행렬은 다음과 같다 (단, ux2 + uy2 + uz2 = 1) (출처: 위키피디아)

— (5)

회전변환 R, 평행이동 t = [tx, ty, tz]T를 이용한 일반적인 3D 변환식(rigid 변환)은 다음과 같다.

 — (6)

2D 변환과 마찬가지로, 3D 변환에서도 homogeneous 좌표를 사용하면 다음과 같이 회전변환과 평행이동을 하나의 변환행렬로 즉, 선형변환 형태로 표현할 수 있다.

 — (7)

참고로, 위키피디아에 보면 어떤 행렬 R이 회전변환이 되기 위한 필요충분 조건은 RT = R-1, det(R) = 1 이라 한다.

4.2 변환관계 구하기

예를 들어 3D 공간에서 비행기 한대가 마음대로 이동한다고 했을 때, 비행기 동선의 임의의 두 지점 사이의 변환관계를 구하는 것이 목적입니다. 물론 이 변환관계는 회전변환과 평행이동만으로 표현이 가능합니다. 먼저 두 벡터 사이의 회전변환을 구하는 문제부터 시작해서 평행이동을 포함한 변환까지 구해보도록 하겠습니다.

4.2.1 회전변환 구하기

크기가 같은 임의의 두 벡터 u = [x, y, z]Tu‘ = [x’, y’, z’]T가 있을 때, u을 u‘로 이동시키는 회전변환은 다음과 같이 구할 수 있습니다.

 — (8)

 — (9)

 — (10)

 — (11)

θ는 두 벡터 uu‘ 사이의 사잇각이며 벡터의 내적을 이용하면 손쉽게 구할 수 있습니다. 회전축이 문제인데, 회전축은 두 벡터 uu‘에 의해 결정되는 평면에 수직인 벡터 즉, 벡터의 외적을 이용하면 됩니다. 이렇게 구한 회전각 θ와 회전축 단위벡터 v를 앞서 식 (5)에 대입하면 원하는 회전변환 행렬을 구할 수 있습니다.

☞ 벡터의 개념 및 백터의 내적, 외적은 알아두면 여러모로 유용합니다. 참고로, 벡터의 외적은 http://blog.naver.com/mindo1103/90103361104 글을 참조하면 잘 설명되어 있습니다. 앞 글에서도 설명했지만 벡터의 외적 u1 × u2 란 두 벡터 u1, u2에 의해 결정되는 평면에 수직이면서(오른손 방향) 그 크기가 u1, u2를 두 변으로 하는 평행사변형의 면적과 같은 벡터를 말합니다

4.2.2 Rigid 변환 구하기

이제 회전뿐만 아니라 평행이동까지 포함한 문제로 확대해 보겠습니다.

3차원 공간에서 어떤 물체의 위치 및 방향을 유일하게 결정하기 위해서는 최소 몇 개의 점이 필요할까요?

물체 위의 3개의 점만 있으면 됩니다. 또한 마찬가지로 3차원 공간에서 움직이는 물체의 위치관계를 표현하기 위해서는 3개의 매칭쌍만 있으면 됩니다.

즉, 3D에서 rigid 변환을 결정하기 위해 필요한 매칭쌍의 개수는 3개입니다.

위 비행기 그림을 예로 들어 rigid 변환을 구하는 과정을 설명하겠습니다.

위치 A에서의 비행기 상의 임의의 점을 (x, y, z), 위치 A’에서의 대응되는 점을 (x’, y’, z’)라 할 때, 주어진 3개의 매칭쌍 p1-p1′, p2-p2′, p3-p3’를 이용하여 (x, y, z)에서 (x’, y’, z’)로의 rigid 변환관계를 구하는 것이 목적입니다 (pi = (xi,yi,zi), pj’=(xj’,yj’,zj’)).

과정을 간략히 말로 설명하면 1) p1이 원점이 되도록 A를 평행이동 시킨 후, 2) A’의 방향과 일치되도록 회전시켜서, 3) p1’까지 평행이동시킨다 입니다.

결국 관건은 회전변환인데, 두 물체를 일치시키기 위해서는 총 2번의 회전이 필요합니다. 먼저 벡터 p1p2가 벡터 p1’p2’가 되도록 회전시킨 후 (R1), p3와 p3’이 일치되도록 한번 더 회전을 시킵니다 (R2).

 — (12)

R1은 4.2.1 회전변환 구하기 방법을 사용하면 구할 수 있습니다.

그런데 문제는 R2를 구하는 것인데, 이걸 구하는 게 쉽지가 않네요.. 이리 저리 궁리를 해 봤지만 간결한 방법은 발견하지 못했습니다. 제가 푼 방법을 간략히 설명하면 다음과 같습니다.

먼저 R1까지 적용하면 벡터 R1*p1p2와 벡터 p1’p2’가 일치됩니다. 다음으로 벡터 R1*p1p3를 회전시켜서 p1’p3’이 되도록 만들어야 합니다. 회전축은 R1*p1p2인데 회전각이 문제입니다. 벡터 R1*p1p3와 벡터 p1’p3′ 사잇각을 구하는 것은 바람직하지 않습니다. 두 벡터를 R1*p1p2에 수직인 평면에 projection 시킨 후 사잇각을 구해야 합니다. projection을 직접 구하는 것은 어렵기 때문에 R1*p1p2 & R1*p1p3에 의해 결정되는 평면에 수직인 벡터(법선벡터)와 R1*p1p2 & p1’p3’에 의해 결정되는 평면에 수직인 법선벡터를 구해서 두 법선벡터가 일치되도록 회전을 시키면 됩니다. 즉, R2는 (R1*p1p2)×(R1*p1p3)를 (R1*p1p2)×p1’p3’로 회전시키는 행렬입니다.

☞ 이상으로 3D 공간에서 물체의 임의의 변환관계를 3개의 매칭쌍을 이용하여 계산하는 방법을 살펴보았습니다. 그런데 여기서 설명한 방법은 나름 구해본 방법이기 때문에 더 좋은 방법이 있을 거라 생각합니다 (지금은 모르지만). 특히 여기서 설명한 방법은 매칭쌍이 3개인 경우에만 적용가능하며 매칭쌍이 3개 이상인 경우까지는 확장이 안됩니다. 즉, 다수의 (3개 이상) 매칭쌍에 대해 이들을 가장 잘 근사하는 변환을 구할 때에는 다른 방법이 필요할 것입니다.

4.3 좌표축 변환

마지막으로 3D 공간에서 좌표축 변환 행렬을 살펴보고 글을 마무리하겠습니다.

[영상처리] – [컴퓨터 비전에서의 Geometry #1] 좌표계 에서 설명했던 월드 좌표계와 카메라 좌표계 사이의 변환이 좌표축 변환에 해당합니다.

월드좌표계 상에서 카메라 초점(카메라 좌표계의 원점)의 좌표를 (Fx, Fy, Fz), 월드좌표계의 좌표축을 카메라 좌표계 좌표축으로 회전시키는 행렬을 R이라 하겠습니다.

이 때, 월드 좌표계의 점 (X, Y, Z)을 카메라 좌표계로 봤을 때의 좌표 (Xc, Yc, Zc)는 다음과 같이 구해집니다.

 — (13)

회전변환 행렬의 경우 RTR = I 즉, R-1 = RT가 성립하므로 위 식은 아래와 같이 쓸 수 있습니다.

 — (14)

카메라 좌표계 상의 점을 월드 좌표계로 바꿀 때에도 위 식을 역으로 이용하면 됩니다.

실제로 R을 구하는 방법에 대해서는 [영상처리] – 3D 좌표계 변환 방법 (예: 월드좌표계 – 카메라 좌표계) 글을 참조하기 바랍니다.

by 다크 프로그래머

(3D 비전 geometry 마지막 6번째 파트 epipolar geometry입니다)

6장 epipolar geometry를 마지막으로 ‘영상 geometry’ 글을 마무리하고자 합니다.

6. Epipolar Geometry

Epipolar geometry는 스테레오 비전(stereo vision) 즉, 2-view 비전에서의 기하라고 생각하면 됩니다.

즉, Epipolar geometry는 동일한 사물 또는 장면에 대한 영상을 서로 다른 두 지점에서 획득했을 때, 영상 A와 영상 B의 매칭쌍들 사이의 기하학적 관계를 다루는 것입니다.

<그림 1>

6.1 용어 및 기본 개념

<그림 1>과 같이 3차원 공간상의 한 점 P가 영상 A에서는 p에 투영되고, 영상 B에서는 p’에 투영됐다고 하겠습니다. 이 때, 두 카메라 원점을 잇는 선과 이미지 평면이 만나는 점 e, e’을 epipole이라 부르고 투영점과 epipole을 잇는 직선 ll‘을 epiline (또는 epipolar line)이라 부릅니다. Epiline은 3차원의 점 P와 두 카메라 원점을 잇는 평면(epipolar plane)과 이미지 평면과의 교선으로도 볼 수 있습니다.

두 카메라 위치 사이의 기하학적 관계 [R|t]를 알고 있고 영상 A에서의 영상좌표 p를 알고 있을 때, 영상 B에서 대응되는 점 p’의 좌표를 구하는 문제를 생각해 보겠습니다. 이 때, 점 P까지의 거리(depth) 정보를 모른다면 영상좌표 p로부터 투영되기 전의 3차원 좌표 P를 복원할 수는 없습니다. 따라서 점 P가 영상 B에 투영된 좌표 p’ 또한 유일하게 결정할 수 없습니다. 하지만 점 P는 A 카메라의 원점과 p를 잇는 직선(ray) 상에 존재하기 때문에 이 직선을 영상 B에 투영시키면 점 p’이 이 투영된 직선 위에 있음은 알 수 있습니다. 이 투영된 직선이 바로 epiline l’ 입니다.

정리하면, ‘A의 영상좌표 p로부터 대응되는 B의 영상좌표 p’을 유일하게 결정할 수는 없지만 p’이 지나는 직선인 epiline l’은 유일하게 결정할수 있다’ 입니다. 그리고 한 영상좌표로부터 다른 영상에서의 대응되는 epiline을 계산해주는 변환행렬이 Fundamental Matrix, Essential Matrix 입니다. 즉, 서로 다른 두 시점에서 찍은 영상좌표들 사이에는 Fundamental Matrix, Essential Matrix를 매개로 하는 어떤 변환 관계가 성립하는데, Epipolar Geometry에서는 이 변환관계를 바탕으로 여러 기하학적 문제를 풀게 됩니다.

6.2 Essential Matrix

위 <그림 1>과 같이 3D 공간상의 한 점 P가 영상 A에서는 p에 투영되고, 영상 B에서는 p’에 투영됐다고 하면 두 영상 좌표 p와 p’ 사이에는 다음 관계를 만족하는 행렬이 항상 존재한다는 것이 epipolar geometry의 핵심입니다 (단, p, p’은 normalized 이미지 평면에서의 homogeneous 좌표임).

 — (1)

 — (2)

즉, 임의의 두 지점에서 찍은 영상의 매칭점들은 항상 식 (1)을 통해 관계지을 수 있으며, 이 때 식 (1)을 epipolar constraint (또는 essential constraint), 이 3×3 행렬 E를 Essential Matrix라 부릅니다.

Essential Matrix E가 항상 존재하는 이유는 다음과 같습니다. 임의의 두 카메라 좌표축 사이의 관계는 회전, 평행이동에 의해 관계지을 수 있기 때문에 두 카메라 좌표축 사이의 3 × 3 회전행렬을 R, 3 × 1 평행이동 벡터를 t라 했을 때, 외부 공간상의 한 점을 두 카메라 좌표계에서 봤을 때의 관계를

 — (3)

와 같이 잡을 수 있습니다 (단, P는 외부 공간 상의 점을 A 카메라 좌표계에서 봤을 때의 3차원 좌표, P’은 B 카메라 좌표계에서 봤을 때의 3차원 좌표).

이 때, essential matrix E를 다음과 같이 잡으면

 — (4)

아래의 식 (5)가 만족됨을 알 수 있습니다. 단, 식 (4)에서 [t]x는 벡터 t와의 벡터 외적(outer product)을 의미합니다. 또한, [t]xR은 t와 R과의 외적을 의미하는게 아니라 먼저 R로 회전을 시킨 후 다음에 t와 외적을 시키는 일련의 변환을 의미합니다. 즉, Ep = [t]xRp = t × (Rp) 입니다.

 — (5)

 — (6)

식 (5)의 좌변에 E = [t]xR을 대입해 보면 다음과 같이 항상 0이 나옴을 알 수 있습니다.

 — (7)

이제 식 (5)의 카메라 좌표를 정규 이미지 좌표로 바꾸면 식 (1)이 성립함을 알 수 있습니다.

 — (8)

6.3 Fundamental Matrix

앞서 설명한 Essential Matrix는 정규화된 이미지 평면에서의 매칭 쌍들 사이의 기하학적 관계를 설명하는 행렬입니다. 즉, 카메라 내부 파라미터 행렬인 K가 제거된 좌표계에서의 변환관계입니다.

반면 fundamental matrix는 카메라 파라미터까지 포함한 두 이미지의 실제 픽셀(pixel) 좌표 사이의 기하학적 관계를 표현하는 행렬입니다.

임의의 두 이미지 A, B에 대하여, 매칭되는 픽셀 좌표 pimg, pimg‘ 사이에는 항상 다음과 같은 관계를 만족하는 행렬 F가 존재하고, 이러한 행렬 F를 fundamental matrix라 부릅니다.

 — (9)

 — (10)

이 때, 이미지 A에 대한 카메라 내부 파라미터 행렬을 K, 이미지 B에 대한 카메라 행렬을 K’, 이미지 A, B 사이의 essential matrix를 E라 하면 fundamental matrix F는 다음과 같이 주어집니다.

 — (11)

 — (12)

만일 이미지 A, B를 동일한 카메라로 촬영했다면 카메라 행렬(K)이 동일하기 때문에 식 (11), 식 (12)는 다음과 같이 좀더 단순화됩니다.

 — (13)

 — (14)

[부연설명]

앞서 [컴퓨터 비전에서의 Geometry #1] 좌표계에서 설명한 바와 같이 이미지 픽셀좌표 pimg와 normalized 좌표 p 사이에는 camera matrix K에 대해 다음과 같은 변환관계를 가집니다.

 — (15)

 — (16)

따라서 이미지 A의 카메라 파라미터 행렬을 K, 이미지 B의 카메라 파라미터 행렬을 K’라 놓으면 다음 관계가 성립합니다.

 — (17)

이제 식 (17)를 식 (1)에 대입하면 다음과 같이 fundamental matrix가 구해짐을(존재함을) 알 수 있습니다.

 — (18)

6.4 Epipolar Geometry

epipolar geometry에서 다루는 것은 크게 두가지인데 하나는 epipolar constraint이고 다른 하나는 triangulation입니다.

6.4.1 epipolar constraint

epipolar constraint는 두 이미지 평면 사이의 기하학적 관계에 따른 constrain(제약)인데 바로 식 (1)이 epipolar constraint를 나타냅니다.

두 이미지가 주어지고 대응되는 매칭 쌍들을 알고 있을 때, 만일 카메라 파라미터를 모른다면 fundametal matrix F를 직접 구해야 하는데 F를 구하기 위해서는 최소 7쌍의 매칭점들을 필요로 합니다.

단, 여기서 주의해야 할 점은 F의 스케일(scale)까지는 결정할 수 없다는 점입니다 (E도 마찬가지입니다). 스케일을 결정할수 없다 함은 아래 그림과 같이 물체와 카메라가 존재하는 공간 전체를 확대하거나 축소해도 동일한 이미지를 얻기 때문에 이미지만 가지고는 스케일을 알 수 없다는 것을 의미합니다 (가까이에 있는 작은 물체를 찍거나 멀리 있는 큰 물체를 찍어도 같은 영상을 얻을 수 있음을 상기하기 바랍니다).

<그림 2> 스케일 문제

만일 카메라 파라미터를 알고 있다면 Essential matrix E만 구하면 됩니다. Essential matrix E를 결정하기 위해서는 보통 5쌍의 매칭점을 필요로 합니다만 알고리즘에 따라서는 8 쌍의 매칭점을 필요로 하는 경우도 있고, 어떤 경우에는 3쌍, 2쌍, 심지어는 1쌍의 매칭점만을 필요로 하는 경우도 있습니다.

☞ E는 R, t로 구성되는데 회전변환 R이 3 자유도, 스케일을 무시한 평행이동 t가 2 자유도, 도합 5 자유도이므로 5쌍의 매칭점을 필요로 함.

Essential 행렬을 구할 때 몇 쌍의 매칭점들을 필요로 하느냐에 따라서 알고리즘을 8-point 알고리즘, 5-point 알고리즘, …, 1-point 알고리즘 등과 같이 부릅니다. 예를 들어, 3-point 알고리즘은 E를 구할 때 3쌍의 매칭점을 이용하는 알고리즘을 지칭합니다.

3-point 알고리즘, 2-point 알고리즘 등과 같이 원래 요구되는 매칭쌍(5쌍)보다 적은 수의 매칭쌍을 이용하여 E를 구할 수 있는 이유는 E에 추가적인 constraint를 가하기 때문입니다. 예를 들어, 달리는 자동차에 장착된 카메라로 촬영한 영상들 사이에는 우리가 손으로 카메라를 들고 맘대로 찍은 영상과는 분명히 다른 어떤 추가적인 constraint가 존재합니다 (지면과의 높이가 고정된 점, 자동차의 pitch와 roll의 변화가 거의 없는 점 등). 여기에 추가적으로 자동차의 모션을 원운동 또는 직선운동으로 모델링하게 되면 훨씬 적은 수의 매칭쌍만으로 E를 결정할 수 있게 됩니다.

Epipolar geometry에서 essential 행렬이 중요한 이유는 E를 알면 이로부터 두 카메라 A, B 사이의 또는 두 시점 사이의 회전, 평행이동 관계를 파악할 수 있기 때문입니다. 실제 계산 과정에 대해서는 위키피디아를 참조하기 바라며 opencv 함수를 이용해도 [R|t] 를 구할 수 있습니다.

6.4.2 triangulation

마지막으로 triangulation (삼각측량법)은 두 이미지 평면 사이의 기하학적 관계가 주어지고 (즉, E 또는 F가 주어지고), 두 이미지 평면상의 매칭쌍 p, p’이 주어지면 이로부터 원래의 3D 공간좌표 P를 결정할 수 있다는 것을 말합니다. 바로 스테레오 비전에서 거리(depth)를 구할 때 하는 일입니다. 계산과정 및 수식 등은 위키피디아를 참조하기 바랍니다.

6.5 OpenCV 관련 함수

아래 목록의 함수중 회색으로 음영처리한 함수들은 opencv 버전 3.0부터 포함될 예정이라 합니다.

  • findFundamentalMat(): 두 이미지 사이의 fundamental matrix를 계산하여 반환. 입력으로는 8쌍 이상의 매칭 이미지 좌표쌍을 입력
  • findEssentialMat(): 두 이미지 사이의 essential matrix를 계산하여 반환. 입력할 내용은 5쌍 이상의 매칭 이미지 좌표쌍과 카메라 파라미터(초점거리, 주점). 내부적으로 5-point 알고리즘을 사용. 이미지 좌표로는 normalized 좌표가 아닌 픽셀 좌표를 입력 (현재 미구현)
  • decomposeEssentialMat(): 입력 essential matrix로부터 회전변환 R, 평행이동 t를 추출해 줌. 가능한 4가지 조합의 [R|t]를 반환 (현재 미구현)
  • recoverPose(): 입력된 essential matrix와 두 이미지에서의 매칭쌍으로부터 두 이미지의 상대적인 [R|t] 관계를 추출해 줌. decomposeEssentialMat()이 [R|t]를 유일하게 결정하지 못하고 해를 여러개 반환하는 반면, recoverPose()는 부가적인 기하학적 조건 검사를 통해 [R|t]를 유일하게 결정하여 반환해 줌 (현재 미구현)

6.6 참고 자료

위키피디아 epipolar geometry

위키피디아 essential matrix

위키피디아 fundamental matrix

☞ 이상으로 컴퓨터 비전에서의 geometry 시리즈를 마무리합니다. 생각보다 글이 길어졌고 시간도 많이 걸렸네요. 스테레오 비전쪽이 아직도 숙제이긴 하지만 이번 글들을 정리하면서 개인적으로 imaging geometry에 대한 개념이 많이 정리가 되었습니다. 이 글을 읽는 분들에게도 도움이 되었으면 좋겠네요.

☞ 최근 영상기하학에 대한 전반적인 내용을 정리한 글을 올렸는데 이것도 같이 참조하면 좋을듯 싶습니다 -> [영상처리] – Extrinsic Camera Calibration – 카메라의 위치 및 자세 파악

(2014.5.7일자로 최종 수정됨)

by 다크 프로그래머

Categories: Uncategorized

onesixx

Blog Owner

guest

0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x