물론, 이들 central moment을 이용해서 만든 공분산 행렬(covariance matrix)
$$ \Sigma = \left( \begin{array}{cc} \mu_{20} & \mu_{11} \\ \mu_{11} & \mu_{02} \end{array} \right) $$의 두 eigenvalue 중 큰 값에 해당하는 eigenvector가 물체의 정렬 방향을 알려준다.
이미지에서 물체를 인식할 때 물체의 윤곽 정보는 매우 중요한 역할을 한다. 이 윤곽 정보는 보통의 경우 에지를 검출한 후 적절한 영상처리를 거쳐서 단일 픽셀의 선으로 표현된다. 그러나 이렇게 만든 윤곽선은 불필요하게 많은 점으로 구성이 되어 있는 경우가 많으므로, 실제 결과를 사용할 때 적당한 길이의 직선으로 연결된 폴리 라인(polyline)으로 근사를 하여 사용한다. 이 경우 윤곽선의 연접한 점들을 어디까지 직선으로 판단할 것인가에 대한 문제가 생긴다.
이에 대한 한 가지 접근법은 먼저 윤곽선의 처음과 끝점을 잇는 선분을 만들고 사이의 점들이 이 선분에서 벗어난 정도를 조사한다. 최대로 벗어난 윤곽선의 점이 폴리 라인의 새 꼭짓점이 되고 그 꼭짓점을 기준으로 이전 선분을 두 개로 분할한다. 다시 분할된 두 선분에 대해서 같은 작업을 시행하여 더 이상 작은 선분으로의 분할이 없을 때까지 반복하는 것이다. 이 방법은 잘 알려진 Douglas-Peucker 알고리즘이다.
두 번째 방법은 윤곽선의 처음 점에서 시작하는 직선의 끝점의 위치를 윤곽선을 따라 순차적으로 옮겨가면 선분을 만들고, 사이의 점들이 이 선분에서 너무 멀리 떨어지지 않는가를 체크한다. 선분에서 너무 벗어난 점이 있으면, 바로 직전의 윤곽선 점을 꼭짓점으로 분류한 후 이 꼭짓점에서 시작하는 선분을 앞에서와 같은 방식으로 만들어서 다음 꼭짓점 후보를 찾는다. DP 알고리즘이 분할에 기반한 것이라면, 이 방법은 점들의 합병(merging)에 기반한 알고리즘이다. 두 알고리즘 모두 재귀적으로 구현할 수 있다. 아래 그림은 DP-알고리즘(Green Line)과 merge-알고리즘 (Blue Line)을 동시에 비교한 것이다.
거리-tolerance를 10씩 증가시키면(점점 단순해진다) 두 알고리즘을 적용하여 본 결과:
// mark는 새로운 꼭지점의 후보를 기록한다(1=꼭짓점, 0=아님)
// mark[0] = mark[end_idx] = 1;
// end = size(v) - 1: not changing;
void mergeSimplication(double tolerance, int start, int end, std::vector<CfPt>& v,
std::vector<int>& mark)
{
if (end <= start + 1) return ; //at least 3 ;
int k = start + 2;
for (;k <= end; k++) {
double dist_max = 0;
for (int i = start+1 ; i < k; i++) {
// distance to a segment(v[start], v[k]) from v[i];
double dist = distance2Segment(v[start], v[k], v[i]);
if (dist_max < dist) dist_max = dist;
}
if (dist_max > tolerance) break;
}
// 정상적으로 끝나면 k==end + 1;
if (k <= end) {
//k 에서 tolerance을 넘었으므로 새로운 vertex은 k-1;
mark[k-1] = 1; // new_vertex;
mergeSimplication(tolerance, k-1, end, v, mark);
}
return;
};
// distance2Segment()는 한 점에서 선분까지 거리를 구하는 함수; // distantance tolerance 이내에 근접한 이웃점들은 미리 제외시킨 후 알고리즘을 적용한다.
두 점 $A$와 $B$가 만드는 선분 $\overline{AB}$가 있고, 한 점 $P$에서 이 선분까지 거리를 구하려고 할 때 단순히 $\overline{AB}$를 통과하는 직선과 점 $P$의 거리를 구해서 쓰면 안 된다. 그림처럼 $P$가 $P'$의 위치에 있는 경우에 $\overline{AB}$를 통과하는 직선과의 거리가 더 짧지만, 선분과의 거리는 $P'$와 $A$와 거리로 주어진다. 마찬가지로 $P$가 $P''$에 있을 때는 점 $B$와 거리가 최단거리다. 정리하면, 1. 선분 $\overline{AP}$와 $\overline{AB}$의 사이각이 $90^\circ$를 넘는 경우는 $A$까지 거리; $$\cos (\text{사이각}) = \frac{(P.x - A.x)*(B.x - A.x) + (P.y - A.y)*(B.y - A.y)}{\overline{AP}\text{ 길이} * \overline{AB}\text{ 길이}} < 0 .$$ 2. 선분 $\overline{AP}$의 $\overline{AB}$로의 정사영 길이가 $\overline{AB}$의 길이보다 클 때는 $B$까지 거리: $$\text{정사영 길이} = \frac{(P.x - A.x)*(B.x - A.x) + (P.y - A.y)*(B.y - A.y)}{ \overline{AB}\text{ 길이}} > \overline{AB}\text{ 길이} .$$ 3. 직선 $\overline{AB}$와의 거리 = $\overline{AP}$의 수선으로 정사영 길이: $$\text{수선으로 정사영} = \frac{-(P.x - A.x)*(B.y - A.y) + (P.y - A.y)*(B.x - A.x)}{\overline{AB}\text{ 길이}} .$$
이미지 처리에서 픽셀 좌표는 간격이 1인 2차원 그리드의 교차점으로 볼 수 있다. 이미지를 확대하거나 축소할 때, 픽셀과 픽셀 사이 구간에서 값이 필요한 경우가 생긴다. 간단하게는 가장 가까운 주변 픽셀의 값을 그대로 가져다 쓰거나, 또는 주변의 4 픽셀 값을 선형보간해서 사용할 수 있다. 2차원 그리드에서 선형보간은 bilinear interpolation이다. 이 보간법은 속도는 빠르지만 픽셀 값이 인접 그리드에서의 값으로 부드럽게 이어지지 않는 단점이 있다. 인접 그리드 경계에서 픽셀 값이 부드럽게 이어지기 위해서는 적어도 1차 미분이 연속인 보간법을 사용해야 하는데, 이러한 조건을 만족시키는 가장 낮은 찾수의 다항식 보간법이 bicubic interpolation이다.
4점 $(0,0), (0,1), (1,0),(1,1)$을 꼭짓점으로 하는 정사각형 내의 임의 지점 $D=\{(x, y)| 0 \le x\le1, 0\le y \le 1\}$ 에서 픽셀 값을 주는 보간곡면 $f(x, y)$을 주변의 16개 점 $\{(i, j)| -1 \le i \le 2, -1 \le j \le 2\}$에서 픽셀 값을 사용하는 bicubic interpolation을 이용해서 추정할 수 있다. 곡면 $f(x, y)$은 $x$와 $y$의 3차 함수로 다음과 같이 쓸 수 있다.
이 역행렬은 mathematica나 maple 등의 프로그램을 이용하면 쉽게 구할 수 있다. 이렇게 구한 $f(x, y)$는 $[0,1]\times [0,1]$ 영역에서 연속인 smooth 한 곡면을 형성한다. 또한 인접하는 그리드 영역의 곡면과 경계에서 smooth 하게 연결된다.
* 원본 4x4 이미지(RGB): nearest-neighbor interploation으로 256x256 크기로 만듦;
* bicubic interpolation 결과 (256x256):
* bilinear interpolation 결과 (256x256):
코드 구현 일부: bicubic interpolation은 주변의 16개 픽셀 정보가 필요한데, 가장자리 픽셀인 경우는 이를 충족시킬 수 없으므로 이를 해결하기 위해 영역 밖은 가장자리 픽셀이 반복된 것으로 처리하는 것이 가장 쉽다. 그리고 소스 영상이 큰 경우에는 문제가 되지 않지만 예제처럼 작은 소스 영상의 경우는 가장자리 부근에서 단순 채움을 사용하면 왜곡이 발생한다. 이를 해소하기 위해서는 소스 픽셀 위치가 픽셀의 중간을 나타낸 것으로 처리하면 된다.
for (int y = 0; y < dstHeight; y++) {
BYTE *pdst = (BYTE *)dst.GetLinePtr(y);
double src_fy = y * scaley - 0.5;
int src_iy = int(floor(src_fy));
double ry = src_fy - src_iy;
for (int x = 0; x < dstWidth; x++) {
double src_fx = x * scalex - 0.5;
int src_ix = int(floor(src_fx));
double rx = src_fx - src_ix;
// Fill interpolation matrices for R,G,B;
for (int by = 0; by < 4; by++) {
int yy = by + src_iy - 1;
CLAMP(yy, 0, srcHeight - 1);
BYTE *psrc = (BYTE *)src.GetLinePtr(yy);
for (int ax = 0; ax < 4; ax++) {
int xx = ax + src_ix - 1;
CLAMP(xx, 0, srcWidth - 1);
B[ax][by] = psrc[3 * xx + 0];
G[ax][by] = psrc[3 * xx + 1];
R[ax][by] = psrc[3 * xx + 2];
}
}
int bb = (int)BicubicInterpolate(B, rx, ry);
int gg = (int)BicubicInterpolate(G, rx, ry);
int rr = (int)BicubicInterpolate(R, rx, ry);
*pdst++ = bb < 0 ? 0: bb > 255 ? 255: bb;
*pdst++ = gg < 0 ? 0: gg > 255 ? 255: gg;
*pdst++ = rr < 0 ? 0: rr > 255 ? 255: rr;
}
};
기준 좌표계에 대해서 원점을 이동하고 좌표축을 회전시킨 새로운 좌표계에서 점의 좌표는 바뀐다. 원래의 좌표와 바뀐 좌표값 사이의 관계를 주는 변환이 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 멀티플라이어 $λ$는
