독일 튀빙겐 대학교의 Andreas Geiger 교수님의 Computer Vision 강의를 듣고 그 내용을 정리하고자 한다.
Geiger 교수님 연구실에서는 Computer Vision 중에서도 특히 3D Human & Animal, Human Pose & Motion, Robot Perception, Holistic Vision, NeRF 등의 분야를 다루신다.
Computer Vision 분야 중에서도 3D Vision 분야를 연구하기 위한 배경 지식을 쌓아볼 것이다.
사전에 선형 대수 등의 수학 기초를 숙지하고 있다고 가정하고 내용을 기술한다.
강의는 아래 유튜브를 참조하자.
https://www.youtube.com/watch?v=D4wpa-prk4I&list=PL05umP7R6ij35L2MHGzis8AEHz7mg381_&index=4
목차
Image Formation이란, 사람이 보는 실제 세계(3D scene)를 2D 이미지 상에 어떻게 projection할 것인지에 대한 내용이다.
그 중에서도 본 포스팅에서 다룰 내용은 'Primitives and Transformations'이고, 키워드는 다음과 같다.
- Geometric Primitives : 3D shape을 나타내기 위한 basic building blocks
- 기초 : Points, Lines, Planes, Basic Transformations
2D Primitives
먼저, 2차원의 점, 선 등의 primitive가 어떤 식으로 표현되고 앞으로 어떻게(어떤 표현 방법으로) 쓰일지 알아보자.
2D Points
Computer Visoin 분야에서 point는 크게 두 가지 방법을 사용하여 나타낸다.
- Inhomogeneous Coordinates
- Homogeneous Coordinates (동차 좌표계)
2D Point를 기준으로 살펴보자.
Inhomogeneous coordinate에서의 2D point 표현은 우리가 일반적으로 x, y 좌표값을 (열)벡터 형태로 나타낸 형태를 말한다.
\( \boldsymbol{x} = \begin{pmatrix} x \\ y \end{pmatrix} \in \mathbb{R}^2 \)
위 표현에서, 2차원 상의 점은 두 개의 좌표값(numbers) x, y로 나타낼 수 있다.
하지만, homogeneous coordinate에서는 하나의 차원을 추가하여 3D인것처럼 나타낸다.
\( \tilde{\boldsymbol{x}} = \begin{pmatrix} \tilde{x} \\ \tilde{y} \\ \tilde{w} \end{pmatrix} \in \mathbb{P}^2 \)
tilde(~)는 homogeneous coordinate임을 나타내는 symbol이며, 좌표값 두 개에 \(\tilde{w}\)가 추가된 것을 볼 수 있다.
이때 \(\mathbb{P}^2 = \mathbb{R}^3 \, \backslash \{(0, 0, 0) \} \)는 projective space(사영 공간)이라 한다.
그리고 homogeneous vector에서 scale만 다른 벡터는 서로 같은 벡터이다.
예를 들어, \( (1, 2, 5)\)와 \((2, 4, 10)\)은 같은 벡터를 나타낸다.
굳이 차원을 하나 추가하여 homogeneous coordinate로 나타내는 이유는 transformation을 나타내기 용이하고, 마지막 항을 통해 특별한 점을 표현할 수 있기 때문이다.
두 좌표계 간의 변환도 가능하다.
먼저 inhomogeneous coordinate vector \(\boldsymbol{x}\)는 homogeneous vector \(\tilde{\boldsymbol{x}}\)로 다음의 과정을 거쳐 변환할 수 있다.
\( \tilde{\boldsymbol{x}} = \begin{pmatrix} \tilde{x} \\ \tilde{y} \\ \tilde{w} \end{pmatrix} = \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} \boldsymbol{x} \\ 1 \end{pmatrix} = \bar{\boldsymbol{x}} \)
이때 inhomogeneous vector에 1이라는 element를 추가한 벡터 \(\bar{\boldsymbol{x}}\)를 augmented vector라 한다.
역으로 homogeneous vector를 inhomogeneous vector로 다음과 같이 변환한다.
\(\bar{\boldsymbol{x}} = \begin{pmatrix} \boldsymbol{x} \\ 1 \end{pmatrix} = \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \frac{1}{\tilde{w}} \tilde{\boldsymbol{x}} = \frac{1}{\tilde{w}} \begin{pmatrix} \tilde{x} \\ \tilde{y} \\ \tilde{w} \end{pmatrix} = \begin{pmatrix} \tilde{x} / \tilde{w} \\ \tilde{y} / \tilde{w} \\ 1 \end{pmatrix} \)
Homogeneous point 중에서 마지막 요소 (\(\tilde{w}\))가 0인 경우, 해당 점을 ideal point 또는 point at infinity라 한다.
이 점은 0으로 나눌 수 없기 때문에 inhomogeneous coordinate에서는 표현할 수 없으며, 기하학적으로는 다음과 같은 의미를 갖는다.
사영 공간 \(\mathbb{P}^2\)의 점과 선은 위 그림에서 각각 빛과 평면으로 나타난다. ideal point는 공간 상에서 \(x_1, x_2\)평면 상의 line으로 나타나게 된다.
더 자세한 내용은 앞으로 계속 다루게 될 것이다.
2D Lines
2차원에서의 선 또한 점과 마찬가지로 homogeneous coordinate를 사용하여 나타낼 수 있다.
\( \tilde{\boldsymbol{l}} = (a, b, c)^T \)
이때 augmented vector \(\bar{\boldsymbol{x}}\)를 사용하여 homogeneous coordinate에서의 line equation을 다음과 같이 나타낸다.
\( \left\{ \bar{\boldsymbol{x}} \, \vert \tilde{\boldsymbol{l}}^T \bar{\boldsymbol{x}} = 0 \right\} \Leftrightarrow \left\{ x, y \, \vert ax + by + c = 0 \right\} \)
그리고 \(\tilde{\boldsymbol{l}}\)을 normalize하게 되면 \(\tilde{\boldsymbol{l}} = (n_x, n_h, d)^T = (\boldsymbol{n}, d)^T \)에서 \(\boldsymbol{n}\)의 l2 norm \(\lVert \boldsymbol{n} \rVert_2 = 1\)을 만족하게 된다.
이때 \(\boldsymbol{n}\)은 line에 수직한 normal vector이고, \(d\)는 origin으로부터의 거리를 나타낸다.
정규화가 불가능한 예외가 하나 존재하는데, 바로 line at infinity \(\tilde{\boldsymbol{l}}_\infty = (0, 0, 1)^T \)로, 모든 ideal points가 지나가는 선이다.
Cross Product
Cross product는 아래와 같이 skew-symmetric matrix와 벡터의 곱으로 표현된다.
\( \boldsymbol{a} \times \boldsymbol{b} = \left[ \boldsymbol{a} \right]_\times \boldsymbol{b} = \begin{bmatrix} 0 & -a_3 & a_2 \\ a_3 & 0 & -a_1 \\ -a_2 & a_1 & 0 \end{bmatrix} \begin{pmatrix} b_1 \\ b_2 \\ b_3 \end{pmatrix} = \begin{pmatrix} a_2 b_3 - a_3 b_2 \\ a_3 b_1 - a_1 b_3 \\ a_1 b_2 - a_2 b_1 \end{pmatrix} \)
참고로 강의 내에서 대괄호'[]'는 행렬을, 소괄호'()'는 벡터를 표현한다.
2D Line Arithmetic
2D Line과 관련된 계산 방법을 알아보자.
Homogeneous coordinates에서, 두 line의 intersection은 cross product로 표현한다.
\( \tilde{\boldsymbol{x}} = \tilde{\boldsymbol{l}}_1 \times \tilde{\boldsymbol{l}}_2 \)
이와 비슷하게, 두 점이 만나는 line 또한 같은 형태로 표현한다.
\( \tilde{\boldsymbol{l}} = \bar{\boldsymbol{x}}_1 \times \bar{\boldsymbol{x}}_2 \)
augmented vector를 사용하여 표현했지만, homogeneous vector도 사용 가능하다.
두 예시를 살펴보자.
또다른 예시를 보자.
평행한 두 직선이 교차하는 점은 ideal point이고, line of infinity는 오른쪽 아래 식과 같이 나타남을 알 수 있다.
More Complex Algebric Objects
polynomial homogeneous equation을 통해 더 복잡한 형상을 표현할 수 있다. 자세히 다루지는 않고 간단히 살펴보고 넘어가자.
예를 들어, conic sections(plane과 3D cone 구조가 교차할 때 만들어지는 형상)는 다음과 같은 식으로 표현된다.
\( \left\{ \bar{\boldsymbol{x}} \, \vert \bar{\boldsymbol{x}}^T \boldsymbol{Q} \bar{\boldsymbol{x}} = 0 \right\} \)
이러한 특징은 multi-view geometry와 camera calibration에서 유용하게 사용된다.
3D Primitives
3차원은 2차원에서 차원이 하나 더 추가되었을 뿐이다.
2차원의 내용을 좀 더 확장시켜 본다면 어렵지 않게 이해할 수 있을 것이다.
3D Points, Planes, Lines
3D Points
3D point는 2D point를 이해했다면 단순히 좌표값 하나를 추가한 형태일 뿐이다.
inhomogeneous coordinates는 다음과 같다.
\( \boldsymbol{x} = \begin{pmatrix} x \\ y \\ z \end{pmatrix} \in \mathbb{R}^3 \)
또한 homogeneous coordinates는 2차원에서와 마찬가지로 \(\tilde{w}\) term을 추가하여 사영 공간 내에서 표현한다.
\( \boldsymbol{x} = \begin{pmatrix} \tilde{x} \\ \tilde{y} \\ \tilde{z} \\ \tilde{w} \end{pmatrix} \in \mathbb{P}^3 \)
마찬가지로 사영공간은 \(\mathbb{P}^3 = \mathbb{R}^4 \, \backslash \left\{ (0, 0, 0, 0) \right\} \)를 만족한다.
3D Planes
다음으로 3D Plane을 먼저 알아보자. 3D Plane은 homogeneous coordinates \(\tilde{\boldsymbol{m}} = (a, b, c, d)^T\)를 사용하여 다음과 같이 표현하며, 2D에서의 Line과 비슷한 형태를 갖는다. (3D Line과 2D Line이 같은 표현 형태가 아님에 유의하자.)
\( \left\{ \tilde{\boldsymbol{x}} \, \vert \tilde{\boldsymbol{m}}^T \bar{\boldsymbol{x}} = 0 \right\} \Leftrightarrow \left\{ x, y, z \, \vert ax + by + cz + d = 0 \right\} \)
2D Line과 마찬가지로 plane \(\tilde{\boldsymbol{m}}\)을 normalize하여 \( \lVert \boldsymbol{n} \rVert_2 = 1 \)인 \(\tilde{\boldsymbol{m}} = (n_x, n_y, n_z, d)^T = (\boldsymbol{n}, d)^T \) 평면으로 만들 수 있다.
이때 \(\boldsymbol{n}\)은 plane에 수직인 normal vector이고, \(d\)는 원점으로부터의 거리이다.
그리고 모든 ideal points가 지나가는 plane at infinity \(\tilde{\boldsymbol{m}} = (0, 0, 0, 1)^T\)는 정규화가 불가능하다.
3D Lines
3D Lines는 2D line 또는 3D Plane 등과 같이 명확하게 정의되지 않는다.
여러 표현 방법 중 하나는 다음과 같이 선 상의 point \(\boldsymbol{p}, \boldsymbol{q}\)의 linear combination으로 표현하는 것이다.
\( \left\{ \boldsymbol{x} \, \vert \boldsymbol{x} = (1 - \lambda) \boldsymbol{p} + \lambda \boldsymbol{q} \wedge \lambda \in \mathbb{R} \right\} \)
하지만, 이 표현 방법은 4Dof이며, 6개 parameter나 필요하다.
다른 표현 방법으로는 'two-plane parameterization', 'Plucker coordinates' 등이 있는데, 여기서 다루지는 않을 것이다.
3D Quadrics
Quadric surface(2차 초곡면)이란, 2차 다항식으로 정의되는 대수 다양체이다.
간단하게 생각해보면, 2D에서 conic section 개념을 3D로 확장시킨 개념이다.
2D conic에서 사용했던 식과 동일한 식을 사용하며, \(\boldsymbol{Q}\) term이 모양에 영향을 준다.
\( \left\{ \bar{\boldsymbol{x}} \, \vert \bar{\boldsymbol{x}}^T \boldsymbol{Q} \bar{\boldsymbol{x}} = 0 \right\} \)
Multi-view geometry 연구에 많이 사용되고, 구, 타원면, 원기둥 등의 primitives를 모델링할 때 많이 사용된다.
기초적인 3D primitives 여러 개를 통해 복잡한 3D 형상을 압축할 수 있다.
2D and 3D Transformations
Transformation(변환)은 2D, 3D를 막론하고 Computer Vision과 Computer Graphics 분야에서 아주 중요한 내용이다.
확실히 알아두고 넘어가도록 하자.
2D Transformations
2D Transformation은 다음과 같이 분류된다.
- Translation
- Euclidean
- Similarity
- Affine
- Projective (Perspective)
Translation Transformations
Translation은 입력에 2D Translation(평행 이동)을 적용한 것이고, 2 DoF(Degree of Freedom)를 갖는다.
Homogeneous coordinate를 사용하여 다음과 같이 transformation matrix를 표현한다.
\( \boldsymbol{x}^\prime = \boldsymbol{x} + \boldsymbol{t} \Leftrightarrow \bar{\boldsymbol{x}}^\prime = \begin{bmatrix} \boldsymbol{I} & \boldsymbol{t} \\ \boldsymbol{0}^T & 1 \end{bmatrix} \bar{\boldsymbol{x}} \)
Augmented vectors \(\bar{\boldsymbol{x}}\)는 homogeneous vectors \(\tilde{\boldsymbol{x}}\)로 항상 대체 가능하다.
Homogeneous coordinate에서 transformation matrix로 위와 같이 표현하는 경우, chain rule, inverse 등의 연산을 적용하기 쉽다.
Euclidean Transformations
Euclidean transformation은 2D Translation(평행 이동)과 2D Rotation(회전)을 적용한 것이며, 3 DoF를 갖는다.
Transformation matrix는 다음과 같다.
\( \boldsymbol{x}^\prime = \boldsymbol{R} \boldsymbol{x} + \boldsymbol{t} \Leftrightarrow \bar{\boldsymbol{x}}^\prime = \begin{bmatrix} \boldsymbol{R} & \boldsymbol{t} \\ \boldsymbol{0}^T & 1 \end{bmatrix} \bar{\boldsymbol{x}} \)
\(\boldsymbol{R} \in \text{SO}(2)\)은 orthonormal rotation matrix로, \( \boldsymbol{R} \boldsymbol{R}^T = \boldsymbol{I}\)와 \(\text{det}(\boldsymbol{R}) = 1\)을 만족한다.
Euclidean transformation의 특징은 변환 후에도 Euclidean distance를 보존한다는 점이다.
Similarity Transformations
Similarity(유사, 닮음) transformation은 2D Translation과 Scaled 2D Rotation을 적용한 것이며, 4 DoF를 갖는다. 즉, Euclidean transformation에서 scale의 변화가 추가된다.
\( \boldsymbol{x}^\prime = s \boldsymbol{R}\boldsymbol{x} + \boldsymbol{t} \Leftrightarrow \bar{\boldsymbol{x}}^\prime = \begin{bmatrix} s \boldsymbol{R} & \boldsymbol{t} \\ \boldsymbol{0}^T & 1 \end{bmatrix} \bar{\boldsymbol{x}} \)
\(\boldsymbol{R}\)은 rotation matrix, \(s\)는 scale factor이다.
Similarity transformation은 line 간의 angle을 보존한다. 예를 들어, 정사각형은 변환 후에도 정사각형이다.
Affine Transformations
Affine transformation은 2D linear transformation이며, 6 DoF를 갖는다. Similarity transformation에서 shearing(특정 방향으로 미는 것)이 포함된 개념, 또는 기존 좌표가 선형 변환한 개념으로 이해하면 쉬울 것이다.
\( \boldsymbol{x}^\prime = \boldsymbol{A}\boldsymbol{x} + \boldsymbol{t} \Leftrightarrow \bar{\boldsymbol{x}}^\prime = \begin{bmatrix} \boldsymbol{A} & \boldsymbol{t} \\ \boldsymbol{0}^T & 1 \end{bmatrix} \bar{\boldsymbol{x}} \)
\( \boldsymbol{A} \in \mathbb{R}^{2 \times 2} \)는 임의의 2 × 2 matrix이다. (rotation matrix에서 orthogonal과 determinant 조건이 사라진 행렬이 된다.)
Affine transformation은 직선, 길이의 비, 평행인 line 간의 관계가 보존된다. 예를 들어, 정사각형이 평행사변형이 될 수 있다.
Projective (Perspective) Transformations
Projective transformation(원근 변환)은 homography transformation이며, 8 DoF를 갖는다. Affine transformation에서 \(\tilde{w}\) term까지 변경된 개념이라고 보면 된다.
\( \tilde{\boldsymbol{x}}^\prime = \tilde{\boldsymbol{H}} \tilde{\boldsymbol{x}} \left( \bar{\boldsymbol{x}} = \frac{1}{\tilde{w}} \tilde{\boldsymbol{x}} \right) \)
\( \tilde{\boldsymbol{H}} \in \mathbb{R}^{3 \times 3} \)은 임의의 homogeneous 3 × 3 matrix이다. 그런데도 9 DoF가 아닌 8 DoF인 이유는 homogeneous matrix는 scale이 달라져도 같은 matrix이기 때문에 하나의 자유도가 사라지는 것이다 (\(\tilde{w}\))
직선은 직선으로 보존된다.
어떤 perspective 2D transformation \( \tilde{\boldsymbol{x}}^\prime = \tilde{\boldsymbol{H}} \tilde{\boldsymbol{x}} \)에 따라 변환된 2D line equation은 다음과 같이 바뀌게 된다.
\( \tilde{\boldsymbol{l}^\prime}^T \tilde{\boldsymbol{x}}^\prime = (\tilde{\boldsymbol{H}}^T \tilde{\boldsymbol{l}^\prime})^T \tilde{\boldsymbol{x}} = \tilde{\boldsymbol{l}}^T \tilde{\boldsymbol{x}} = 0 \)
\( \therefore \tilde{\boldsymbol{l}^\prime} = \tilde{\boldsymbol{H}}^{-T} \tilde{\boldsymbol{l}} \)
따라서, 2D line, 3D normal과 같은 co-vector에 projective transformation을 하는 과정은 위와 같이 transposed inverse를 사용하여 표현할 수 있다.
Summary, 3D Transformations
2D Transformation 내용은 아래와 같이 정리할 수 있다.
Transformation은 위 표와 같이 nested set of groups를 형성한다.
쉽게 말하면 위로 갈수록 제한 사항이 많아지고, 위에 있는 것은 아래에서 보존하는 것도 보존한다.
3D Transformation은 2D transformation과 같은 맥락이며, 단순히 homogeneous coordinate에서 한 차원씩 추가한 개념이다.
표에서 Affine trnasformation matrix 까지의 3 × 4 matrix는 4번째 행에 \( [ \boldsymbol{0}^T \, 1 ] \)행이 추가된다.
각 변환의 성질은 2D에서와 동일하다.
Direct Linear Transform for Homography Estimation
2D correspondences(변환 전, 후 2D 좌표 쌍)가 어떤 집합으로 주어진 경우, homography를 추정하는 알고리즘을 Direct Linear Transformation이라 한다.
그 과정을 살펴보자.
N개의 2D to 2D correspondences가 \( \mathcal{X} = \left\{ \tilde{\boldsymbol{x}}_i, \tilde{\boldsymbol{x}}_i^\prime \right\}_{i=1}^N \)로 주어졌다고 하자.
두 좌표간의 관계는 \( \tilde{\boldsymbol{x}}_i^\prime = \tilde{\boldsymbol{H}} \tilde{\boldsymbol{x}}_i \)임을 배웠다.
correspondence vector가 homogeneous일 때, 방향은 같지만 크기가 다를 것이다.
그러므로, 같은 방향임을 cross product를 사용하여 수식으로 나타내면 다음과 같다.
\( \tilde{\boldsymbol{x}}_i^\prime \times \tilde{\boldsymbol{H}} \tilde{\boldsymbol{x}}_i = \boldsymbol{0} \)
\(\tilde{\boldsymbol{H}}\)의 k번째 행을 \( \tilde{\boldsymbol{h}}_k^T \)로 나타낼 때, 위 식을 아래와 같이 \( \tilde{\boldsymbol{h}} \)에 대한 선형 방정식으로 나타낼 수 있다.
이때 마지막 행은 scale에 따라 linearly dependent하고 (drop!), 위 두 행이 나타내는 선형 방정식이 중요하다.
따라서 각 correspondence 당 두 가지 방정식을 얻을 수 있다.
\(\boldsymbol{A}_i\) 행렬의 두 행을 1번째부터 N번째까지 모두 쌓게 되면, \(2N \times 9\) 차원의 matrix \(\boldsymbol{A}\)를 얻을 수 있다.
이 행렬을 사용하여 다음과 같은 constrained least squares problem을 유도할 수 있다.
\( \begin{align*} \tilde{\boldsymbol{h}}^* &= \underset{\tilde{\boldsymbol{h}}}{\operatorname{argmin}} \lVert \boldsymbol{A} \tilde{\boldsymbol{h}} \rVert_2^2 + \lambda \left( \lVert \tilde{\boldsymbol{h}} \rVert_2^2 - 1 \right) \\ &= \underset{\tilde{\boldsymbol{h}}}{\operatorname{argmin}} \tilde{\boldsymbol{h}}^T \boldsymbol{A}^T \boldsymbol{A} \tilde{\boldsymbol{h}} + \lambda \left(\tilde{\boldsymbol{h}}^T \tilde{\boldsymbol{h}} - 1 \right) \end{align*} \)
여기서 \( \tilde{\boldsymbol{H}} \)가 homogeneous이므로 scale을 조정하여 \( \lVert \tilde{\boldsymbol{h}} \rVert_2^2 = 1 \)을 적용했다. 또한 \( \tilde{\boldsymbol{h}} = 0 \)의 경우 trivial solution이므로 고려하지 않았다.
위 optimization problem의 해는 \( \boldsymbol{A} \)의 가장 작은 singular value값에 따른 singular vector이다. 여기서의 singular value는 Vector Decomposition에 따라 \( \boldsymbol{A} = \boldsymbol{U} \boldsymbol{D} \boldsymbol{V}^T \)에서 \(\boldsymbol{V}\)의 마지막 column을 말한다.
이러한 알고리즘은 두 사진의 겹치는 부분에 맞춰 panorama 사진을 만드는 'Panorama Stitching' task에 많이 사용된다.
최근댓글