이번 리뷰는 Multiview Geometry 책의 Homogeneous 좌표계부터 Perspective Transformation을 구하는 챕터까지를 정리하고자 합니다.
해당 내용은 정규 세미나에서 이미 발표했던 내용으로 혹시나 못들으신 분을 위해 글로도 정리하고자 합니다.
Homogeneous Coordinate
먼저 우리는 투영 변환에 대하여 다룰 때 좌표 값을 동차좌표(Homogeneous coordinate)로 표현합니다. 이때 동차란 무엇일까요?
동차에 대해서 알아보기 전에, 우리는 어떠한 값을 표현할 때 단순히 a라고 표현하지 않고, a/w로 표현할 수가 있습니다. 이때 w값이 점점 커질수록, 해당 값은 0이 되며, w값이 점점 작아질수록 무한대가 됩니다. 즉 a/w로 표현하게 되면 무한대의 개념을 조금 더 잘 활용할 수 있게 되는 것입니다.
그럼 이제 위에 그림에서 첫번째 방정식을 보시면, 해당 방정식은 일반적인 직선의 방정식입니다. 해당 직선의 방정식을, 무한대의 개념을 활용하기 위해 x와 y의 w를 나누는 꼴로 치환을 하게 되면 2번째 방정식이 되고, 양변에 w를 곱하여 마지막 세번째 방정식처럼 만들어 줍니다,
해당 방정식을 유심히 처다보면, 기존의 직선의 방정식에 경우에는 맨 마지막 상수 c는 0차항에 해당됐지만, 치환하여 만든 방정식은 모든 차수가 1차항으로 동일한 것을 확인할 수가 있습니다.
즉 방정식의 모든 항에 대하여 차수가 동일한 차수가 된다 하여 동차라고 얘기하는 것 입니다.
그럼 동차 좌표계는 어떻게 표현할 수 있을까요? 왼쪽에 (x,y)는 우리가 일반적으로 아는 2차원 점을 나타내는 좌표입니다. 이 점 좌표를 동차 좌표로 만드는 방법은 간단합니다. 차원을 하나 늘려준 다음에 모든 차원 대하여 w를 곱해주면 되는 것입니다.
반대로 동차 좌표에서 비동차 좌표로 변환하는 방법은 무엇일까요? 동차 좌표를 생선한 것과 반대로, 모든 차원에 대하여 w로 나눠준 후에, 마지막 차원을 제거해주면 됩니다.
동차 좌표계에서 눈여겨보셔야 할 가장 중요한 점은 동차좌표에서 해당 w의 값이 0이 아닌 어떠한 값이 되더라도, 비동차 좌표로의 역변환을 할 시에 항상 동일한 (x,y)가 나온다는 점입니다. 즉 w가 2가 되던, 1000이 되던, -500이 되던 상관없이, 비동차 좌표로 변환하게 되면 항상 동일한 비동차 좌표값이 나온다는 것입니다.
그럼 이러한 동차 좌표를 투영 좌표에 사용하는 이유가 무엇일까요?
위에 그림은 3차원 공간에 어떠한 점 X를 2차원 평면에 투영하는 것을 나타낸 그림입니다. 이때 투영되어 평면에 생성된 점이 바로 x입니다. 그럼 파란색 점을 기준으로 생각해봅시다. 파란색 점은 점X에 상수 k배를 곱한 것인데, 이때 해당 k가 어떠한 값을 가진다고 하더라도, 결국엔 2차원 평면에 대하여 점x에 투영이 됩니다.
이러한 투영의 성질은 동차좌표(3차원 공간)에서 w값이 어떠한 크기의 값을 가지더라도, 비동차 좌표(2차원 평면)로 역변환 하였을 때 항상 동일한 좌표를 가진다의 성질과 완벽히 동일하기에, 저희는 투영 변환에 대하여 동차 좌표계로 계산을 진행한다고 생각하시면 될 것 같습니다.
Point & line using Homogeneous vector
그럼 점과 직선에 대하여 동차벡터로 표현하는 방법에 대해서 알아봅시다.
위에 식은 일반적인 직선의 방정식입니다. 해당 방정식은 3×1벡터와 1×3벡터의 곱으로 표현할 수가 있습니다. 그럼 이때 직선 위의 한 점을 (x, y, 1)로 놓으면, 직선은 (a, b, c)로 표현할 수가 있게 되고, 이 둘의 내적을 하게 되면 위와 같은 방정식이 성립하게 됩니다. 그리고 해당 방정식은 ‘=0’의 값을 가지므로, 두 벡터(점과 직선)의 내적=0이라고 할 수가 있습니다.
즉 여기서 우리는 점과 직선을 동차 벡터로 나타낼 수 있으며, 점과 직선을 내적하였을 때 결과 값이 0이 나오게 된다면, 해당 점과 직선은, 직선과 직선위의 한 점에 대한 관계라는 것을 알 수 있습니다.
Intersect two line
그럼 두 직선에 교차하는 상황에 대해서도 알아봅시다.
서로 다른 두 직선 l과 l’이 존재하고, 해당 두 직선의 외적하면 나오는 좌표를 점 x의 좌표라고 가정합시다. 서로 다른 두 직선 벡터에 대해서, Triple Scalar product를 진행하게 되면, 0이 나오게 됩니다.
저희는 이때 서로 다른 두 직선의 벡터를 점 x라고 가정하였기에, 해당 연산을 점 x로 치환하게 되면 직선과 점의 내적으로 나타낼 수 있게 됩니다. 이때 내적하여 나온 결과값이 0이 되기에, 위에서 설명했듯이, 직선 l, l’과 점 x는 해당 직선들 위의 한 점이라고 볼 수 있으므로, 두 직선의 교점이라고 놓을 수 있습니다.
Point at infinity & Line at infinity
이번엔 다른 경우에 대해서 알아봅시다. 여기 두 평행한 직선 l과 l’이 존재합니다.
그리고 두 직선의 외적을 마찬가지로 어떠한 점 x라고 가정하였을 때, 점 x의 값은 위에 그림과 같이 나옵니다. 여기서 (c’ – c)는 scale값에 해당하기에 고려를 해주지 않습니다.
위에 결과를 보면, 두 평행한 직선에 대하여 외적을 해보니, (b, -a, 0)^T 라는 점 좌표가 나오게 되고, 이를 통해 교점이 존재하는가? 라는 생각이 들게 됩니다. 하지만 점 x의 좌표를 비동차 좌표로 변환하게 되면 b와 -a에 0을 나누게 되므로, 해당 식은 성립하지 않는다고 보실 수 있습니다. 즉 두 평행한 직선에 대하여 교점은 존재하지 않는 것이지요.
위와 같이, 맨 마지막 차원이 0인 동차 좌표를 가지는 점을 우리는 무한원점(point at infinity)라고 합니다. 그리고 무한원점도 역시 동차좌표계에서 표현되는 하나의 점이므로, 무한원점을 지나는 직선이 존재하게 되는데, 해당 직선을 line at infinity라고 합니다.
Difference of Affine & Projective transformation
영상 기하학에서, 회전, 평행이동, 닮음 등 정말 다양한 변환이 존재하는데, 이중에서 Affine 변환과 Projective 변환에 차이에 대하여 가볍게 알아보고자 합니다.
위에 그림을 보면, 좌측에 Affine 변환과 우측에 투영변환은 생김새가 매우 유사합니다. 먼저 공통점으로, 회전변환 특성을 지니고 있는 a11~a22 요소들과, translation 특성을 지니고 있는 tx, ty요소를 지니고 있습니다.
하지만 이 둘의 차이는 바로 맨 마지막 row에서 Affine은 0 0 1을 지니는 반면에, 투영 변환은 투영특성을 지니는 a31, a32요소가 있는 것입니다.
Affine과 Projective 변환의 가장 큰 차이점은 바로 변환 전과 후의 평행성이 보존되는가? 입니다.
위에 그림을 보시면, Affine 변환은 직사각형, 평행사변형 등과 같이, 변환후에도 항상 직선의 평행성이 보존되는 결과값을 제공합니다. 반면에 투영변환은 사다리꼴과 같이 직선의 평행성이 보존이 되지가 않습니다.
이러한 두 변환의 차이점을 무한원점을 통해서 알아봅시다.
무한원점은 위에서 설명드렸다시피, 두 평행한 직선을 외적하면 생성할 수 있었습니다. 즉 무한원점에 대하여 어떠한 변환을 하였을 때, 해당 결과값이 여전히 무한원점 꼴이라면, 해당 변환은 평행성을 유지한다는 점이죠!
무한원점을 왼쪽에 Affine으로 연산을 하게 되면, 결과값도 역시 맨 마지막 차원이 0인 무한원점 꼴로 나타냅니다. 반면에 평행성을 보존하지 못하는 Projective 변환에 경우 무한원점을 적용시킬 경우, 맨 마지막 차원이 0이 아닌 값이 들어있는 것을 확인할 수가 있습니다.
이를 통해 Affine은 평행성을 보존, Projective는 평행성을 비보존한다는 것을 알 수 있습니다.
How to calculate Homography
자 그럼 이제 Projective transformation을 어떻게 구할 수 있는지 알아봅시다. 참고로 Projective transformation을 Homography라고도 부릅니다. 호모그래피는 위에서도 봤듯이 총 9개의 원소를 지닌 3×3 행렬로 이루어집니다.
이제 위 좌측에 수식처럼 어떠한 점 x에 대하여 호모그래피 변환행렬 H를 적용시켜 새로운 점 x’을 만든다고 해봅시다.
이때 Hx를 위에 그림과 같이 나타낼 수 있는데요, 여기서 h1^T는 첫번째 row를 나타내는 1×3 벡터입니다.
그럼 이제 변환 후의 점 벡터 x’과 Hx를 외적하게 되면 다음과 같이 연산이 진행되어 결과값은 0이 되게 됩니다.
여기서 유의하셔야할 점은, 우측에 행렬이 얼핏보면 3×3 행렬과 3×1 행렬의 곱으로 보이실 수 있겠지만, 좌측 행렬의 x^T는 점을 나타내는 벡터이며, h는 H행렬의 column이므로, 해당 연산은 3×9 행렬과 9×1행렬의 곱임을 아셔야합니다.
그리고 이때 해당 행렬을 가우스 소거법을 통해 계산해보면 맨 마지막 row 가 zero-row가 되기에 마지막 row는 소거하여 결과적으로 2×9행렬이 됩니다.
자 저희는 i번째 점에 대하여 위와 같은 방정식을 구했습니다. 하지만 호모그래피 행렬 H는 9개의 요소를 가지고 있으며, 이때 맨 마지막 요소는 항상 1이기에, 8개의 요소값만을 구하면 됩니다.
즉 최소한 점 4개에 대하여 위와 같은 방정식을 쌓게 되면 우리는 하나의 Homography 행렬을 구할 수 있게 됩니다.
Overdetermined
우리는 지금껏 호모그래피 행렬을 구하기 위해서는 최소 4개의 점이 필요하다는 것을 알아봤습니다. 하지만 위와 같은 수식이 성립하기 위해서는 점 x와 그의 대응점 x’이 정확하게 대응관계를 가져야한다는 것입니다.
하지만 우리가 얻는 영상에는 항상 noise가 존재하기에, 우리는 두 점이 서로 완벽한 대응관계를 가진다고 보장할 수가 없습니다.
그러므로 이론적으로는 최소 4개의 점으로 호모그래피 행렬을 구할 수 있지만, 실제로는 보다 더 많은 점을 통해 정확한 호모그래피 행렬과 아주 근사하는 호모그래피 행렬을 구해야만 합니다.
즉 우리는 위에 그림에서 좌측과 같은 이론적 수식을 우측처럼 표현하여 근사화된 행렬을 구합니다. 여기서 우측 항에 값은 에러 값을 나타냅니다.
헌대 여기서 또 문제가 발생합니다. 저희가 결과값을 근사하기 위해 수많은 점들을 가져와 연산하게 되는데, 이때 n의 값이 커짐으로써, 미지수보다 방정식이 더 많아지는 상황이 발생합니다. 이러한 경우를 Over-determined라고 합니다.
위에 그림은 over-determined의 한 예시입니다. 보시면 행렬의 사이즈를 mxn이라고 했을 때, m의 값이 n보다 크게 되어, 방정식이 미지수보다 많은 상황입니다. 이러한 경우에는 해당 방정식의 근을 구할 수가 없게 됩니다.
How to solve over-determined?
그렇다면 이러한 over-determined를 어떻게하면 풀어나갈 수 있을까요?
원리는 정말 간단합니다. over-determined인 행렬 A가 존재한다고 했을 때, 해당 행렬 A의 transpose한 행렬 A^T를 곱하게 되면, 우측과 같이 n x n의 정방행렬이 완성됩니다.
이때 가장 중요한 점은, 해당 연산을 통해 생성되는 n x n 행렬은 정방행렬의 특성뿐만 아니라, 대칭행렬이어야만 하며, 역행렬로도 표현할 수 있어야만 합니다.
다행히 저희가 구하려는 Homograhpy행렬 역시도, 위와 같은 연산을 하게 되면, 아래와 같이 정방이며 동시에 대칭 및 역행렬의 특성을 지니게 됩니다.
자 그러면 이제 거의다 왔습니다. 저희는 기존의 over-determined case인 방정식에 대하여 전치행렬을 양변에 곱하여 정방행렬로 만들고, 해당 정방행렬의 역행렬을 또 곱하여 최종적으로 저희가 구하려는 h를 구할 수 있게 됩니다.
