기준 좌표계에 대해서 원점을 이동하고 좌표축을 회전시킨 새로운 좌표계에서 점의 좌표는 바뀐다. 원래의 좌표와 바뀐 좌표값 사이의 관계를 주는 변환이 Isometric transformation (isometry)이다. 평면에서 이 변환은 평행이동을 나타내는 파라미터 2개, 그리고 1개의 회전각 파라미터에 의해서 결정이 된다. 회전각이 $θ$고, 평행이동이 $(t_x, t_y)$인 isometry에 의해서 두 점 $(x, y)$가 $(u, v)$로 연결이 되는 경우에, 아래의 식으로 표현이 된다:
$$u=\cos( \theta ) x -\sin (\theta) y + t_x;\\ v = \sin (\theta) x + \cos (\theta) y + t_y;$$
따라서 isometry로 연결이 되는 두 점의 조합 $\{(x_1, y_1) \rightarrow(u_1, v_1), (x_2, y_2)\rightarrow(u_2, v_2)\}$ 만 있으면 이들 파라미터를 정확히 결정할 수 있다. 그러나 변환에 필요한 점 정보를 얻는 과정은 필연적으로 노이즈의 영향을 받게 되므로 주어진 모든 점을 정확히 연결하는 변환을 일반적으로 구할 수 없다. 이 경우에는 isometry 파라미터는 일반적으로 최소자승법에 의해서 결정될 수 있다.
최소자승법을 사용하기 위해서는 회전각 $θ$보다는 $a = \cos θ$, $b = \sin θ$로 정의된 새로운 파라미터로 식을 표현하는 것이 더 편리하다. 그러나 이 경우에 파라미터 $a, b$는 서로 독립적이 아니고 $a^2 + b^2 = 1$의 제한 조건을 만족시켜야 한다.
평행이동 파라미터는 질량중심의 isometry 관계로 해결이 되므로, 이 전체 계산을 각각의 질량중심을 원점으로 하는 좌표로 옮겨서 적용하면 더 이상 평행이동을 고려할 필요 없이 회전만 계산하면 된다.
최소자승법의 원리에 따라 입력점의 isometry 결과와 대응점 사이의 거리의 제곱 합 $L$을 주어진 제약조건 내에서 최소화시키는 파라미터 $a, b, λ$를 찾으면 된다:
$$L = \sum_i \big [ (a x_i - b y_i - u_i)^2 + (b x_i + a y_i - v_i)^2 \big] + λ (a^2 + b^2 - 1) ;$$
여기서 $λ$는 제한 조건 $a^2 + b^2 = 1$를 넣기 위한 Lagrange multiplier이다. 극값을 찾기 위해서 $L$를 각각 $a, b, λ$에 대해서 미분해서 다음 조건을 얻는다:
$$\sum_i ( a x_i - b y_i - u_i) x_i + ( b x_i + a y_i - v_i) y_i + λ a = 0 ;\\ \sum_i ( a x_i - b y_i - u_i) (-y_i) + ( b x_i + a y_i - v_i) x_i + λ b = 0;\\ a^2 + b^2 = 1; $$
이 식들을 $a, b, λ$에 대해서 풀면 다음의 관계식을 얻는다:
$$a = ∑(x_i u_ i + y_ i v_ i) / ∑ (x_ i^2 + y_i^2 + λ) ; \\ b = ∑ (x_i v_ i - y_i u_i) / ∑ (x_i^2 + y_i^2 + λ); $$ 또한, Lagrange 멀티플라이어 $λ$는
2차원 이미지의 기하학적인 변형 중에서 평행이동, 회전 및 전체적인 크기의 변화를 주는 변환이 similarity transformation이다. 이 변환은 두 직선이 이루는 각을 보존하고 길이 비를 유지한다. 따라서 similarity 변환 후 물체의 모양은 변환 전과 같은 형태를 가진다. 이 변환보다도 더 일반적인 2차원의 기하학적인 변환은 affine transformation이다. Affine 변환은 한쪽 방향으로의 밀림(sheer)도 허용한다. 평행한 두 직선은 affine 변환 후에도 여전히 평행하다.
Hierarchy of 2d transformation
Similarity transformation은 전체적인 크기를 바꾸는 scale parameter($s$) 1개와 회전각($θ$) 1개, 그리고 $x, y$축으로의 평행이동을 나타내는 parameter ($t_x$, $t_y$) 2 개를 합해서 총 4개가 있어야 한다. 이 parameter에 의해서 원본 이미지의 픽셀 $(x, y)$가 변환된 이미지의 픽셀 $(u, v)$에 대응한다고 하면, 이들 간의 관계는 다음식으로 주어진다. $$u = s\cos (θ) x - s \sin (θ) y + t_x;$$ $$v = s \sin (θ) y + s \cos (θ) y + t_y;$$ 따라서 원본 영상의 2점에 대응하는 정보만 주어지면 파라미터 $(s, θ, t_x, t_y)$를 유일하게 결정할 수 있다. $$(x_1, y_1) \rightarrow (u_1, v_1),\\ (x_2 , y_2) \rightarrow (u_2, v_2) $$그러나 많은 경우에는 기준점을 잡는데 에러 등을 고려하여서 일반적으로 원본 영상의 $N(\ge 2)$ 개의 점에 대응하는 정보를 주게 되는데, 이 경우에 변환 관계식은 overdetermined 되어서 해를 구할 수 없는 경우도 있다. 이 경우에는 최소자승법을 써서 변환점과 변환식에 의해서 의해서 주어지는 값의 차이를 최소화시키는 파라미터를 구해서 쓰면 된다.$$L = \sum_{i} | u_i - (s\cos(θ) x_i - s \sin(θ) y_i + t_x)|^2 + |v_i - (s \sin(θ) x_i + s \cos(θ) y_i + t_y)|^2, \\ (s, \theta, t_x, t_y) =\text {argmin}(L);$$이 식을 최소화시키는 파라미터는 $(a= s \cos(θ), b=s \sin(θ)$로 놓으면) $a, b, t_x, t_y$에 대해서 극값을 가질 조건에서 얻을 수 있다. $$\frac {\partial L}{\partial a}=0: \quad \sum_{i} (u_i - (ax_i - by_i + t_x))(-x_i) + (v_i - (bx_i + ay_i + t_y))(-y_i) = 0,\\ \frac {\partial L}{\partial b}=0:\quad \sum _{i} (u_i - (ax_i - by_i + t_x))(y_i) + (v_i - (bx_i + a y_i + t_y))(-x_i) = 0, \\ \frac {\partial L}{\partial t_x}=0: \quad \sum_{i} (u_i - (ax_i - by_i + t_x)) = 0, \\ \frac {\partial L}{\partial t_y}=0: \quad \sum_{i} (vi - (bx_i + ay_i + t_y)) = 0.$$ 따라서, $S_u = \sum_i u_i$, $S_v = \sum_i v_i$, $S_{ux} = \sum _i u_i x_ i$, $S_{uy} = \sum _i u_iy_i$, $S_{vx} = \sum_i v_i x_i$, $S_{vy} = \sum _i v_i y_i$, $S_x = \sum x_i$, $S_y=\sum _i y_i$, $S_{xx} = \sum_i x_i^2$, $S_{xy} = \sum_i x_iy_i$, $S_{yy}=\sum_i y_i^2$라고 하면,$$-S_{ux} + a S_{xx} + t_x S_x - S_{vy} + a S_{yy} + t_y S_y = 0; \\ S_{uy} + b S_{yy} - t_x S_y -S_{vx} + b S_{xx} + t_y S_x = 0;\\ S_u - a S_x + bS_y - t_x N = 0; \\ S_v - b S_x - aS_y - t_y N = 0;$$의 4개의 식을 얻으므로 $(a, b, t_x, t_y)$에 대한 1차 연립방정식을 풀면 된다.
$$\left [\begin {array}{cccc} S_x&-S_y&N&0\\S_y &S_x&0&N\\ S_{xx}+S_{yy}&0&S_x&S_y\\0 &S_{xx}+S_{yy}&-S_y&S_x\end {array} \right]\left [\begin {array}{c} a\\b\\t_x\\t_y \end {array}\right]=\left [\begin {array}{c} S_u\\S_v\\S_{ux} +S_{vy}\\S_{vx}-S_{uy}\end {array}\right]$$이 식의 답은 쉽게 구할 수 있고, 아래의 코드는 이것을 구현한 것이다. 물론, $N=2$개인 경우에는 파라미터는 유일하게 정해지고 이보다도 더 간단한 식으로 주어진다.
얼굴인식용 training data set을 만들기 위해서 얼굴을 정렬시키는 데 사용한 예: - 양 눈의 위치 변환: (70,93), (114, 84) --> (30,45), (100,45)로 변환( linear interpolation사용) - 실제로 사용되는 변환은 정해진 dst영역으로 매핑하는 src영역을 찾아야 하므로, 역변환이 필요하다. - 필요한 역변환은 src와 dst의 역할만 바꾸면 쉽게 구할 수 있다.
