FFT를 적용할 때 이미지의 폭이나 높이가 2의 지수승으로 주어지는 경우가 가장 간단하다. 따라서 주어진 정수 x가 2의 지수 승인가 판별할 수 있는 방법이 필요하다. x가 양의 정수이고, 2^n으로 표현이 된다면, 2진수로 나타낼 때, (n+1) 번째 비트만 1이고 (0부터 센다), 나머지 비트는 모두 0이다. 그리고 x-1은 n 번째에서 0번째까지 모든 비트가 1이 된 다. x x(2진수) x-1 1 1 0 2 10 1 4 100 11 8 1000 111 ................................................................ 이 표를 보면, x와 x-1 사이에는 겹치는 비트가 없다. 따라서 두 수를 and 연산을 하면 0 이 되는 경우에는 2의 지수승이고, 그 이외의 경우에는 0이 아님을 알 수 있다. x = 2의 지수승 판별은
return x & (x - 1) == 0 /* x != 0 인 정수*/
인가를 보면 된다.
그런데 이 판별식은 x = 0 인 경우에는 성립이 안된다. x-1 = -1 이므로 32비트 자리 전부가 1로 채워지므로 x & (x-1) = 0 이어서 2의 지수승으로 판별한다. 따라서 0을 제외하는 방법을 찾아야 한다. (물론 함수 인자에서 양수로 제한을 하면 되지만 폼이 안 난다). 음수는 최상위 비트가 1로 채워진다는 사실을 이용하자. 최상위 비트를 1로 만들려면,
~0U =111111111111111..11111111(32개) ~0U>>1 = 011111111111111..11111111 ~(~0U>>1) =100000000000000..00000000 ~(~0U>>1)|x = x의 최상위 비트를 항상 1로 채워준다(음수 일 때는 자동으로 만족) 나머지 비트는 그대로 둔다.
따라서 이 값과 x-1을 and 연산을 하면 0 이하인 수가 들어오면 연산이 결과를 항상 0이 아니게 된다.
matlab에서 rgb 컬러 이미지를 gray 이미지로 바꿀 때, 호출하는 함수가 rgb2gray이다. 이 함수는 주어진 RGB 값에 다음과 같은 weight를 주어서 명암 값을 얻는다:
gray = 0.2989 * r + 0.5870 * g + 0.1140 * b ;
이 계산을 fixed-point 버전으로 바꾸어 보자. 정밀도를 유지하기 위해서는 소수점 이하 4자리까지 유지해야 하는데, 이것은 weight에 각각 10000을 곱한 값을 사용한 후에 다시 10000으로 나누면 된다 (10000을 곱하더라도 r, g, b가 0-255사이의 값이므로 최대로 255 * 10000 보다 작은 값이 나와서 32-비트 정수 범위 내에 있게 된다)
gray = (2989 * r + 5870 * g + 1140 * b) / 10000;
여기서 좀 더 개선을 할 수 있다. 10000으로 나누는 과정을 shift 연산으로 바꾸면 된다. 정밀도를 보존하기 위해서 10000보다 큰 2의 power의 수를 찾으면 2^14 = 16384 이 주어진다. 따라서 10000 대신에 2^14을 곱한 weight를 쓰고, 계산 결과를 오른쪽으로 14만큼 shift 연산을 하면 된다. 0.2989 * 2^14 = 4897.1776; 0.5870 * 2^14 = 9617.408; 0.1140 * 2^14 = 1867.776;
gray = (4897 * r + 9617 * g + 1868 * b) >> 14;
weight의 총 합 = 4897 + 9617 + 1868 < 2^14 이어서 gray 값은 255를 넘지 않고, 중간 계산은 32-비트 정수 범위 내에서만 이루어진다. 정말 빠를까?
제대로 segmented 된 그레이 영상은 원래의 영상이 나타내고자 하는 전경이 잘 표현이 된 것이다. 이 경우의 원래 영상과 segmented 된 영상은 높은 상관관계를 갖는다. 따라서, 세그먼트를 위한 임계값의 설정 기준으로 이 상관계수를 최대로 하는 임계값을 찾는 것도 좋은 방법 중의 하나가 될 수 있다.
여기서 사용할 상관계수는 원래의 영상(A)과 전경과 배경을 그들의 픽셀 평균값으로 대체한 segmented 된 영상(B) 간의 상관계수를 사용한다. 임계값이 $T$인 경우 세그먼트된 영상B는
로 나타난다. 여기서 $m_0$는 배경 픽셀의 평균값이고, $m_1$은 전경 픽셀의 평균값이다. 이 값은 임계값 $T$에 따라 달라진다. 임계값이 높으면 $m_0$는 커지고, 반대로 $m_1$은 작아진다.
임계값이 $T$일 때배경 픽셀 비를 $p$,전경 픽셀 비를 $q(=1- p)$라 하면 segmented된 영상 B는 각 영역에서의 픽셀 값을 평균으로 대체했으므로 원본 영상의 평균과 같다. 또한, 원본 영상의 분산은 임계값에 무관하게 일정한 값을 유지한다. 이를 정리하면,
물론, 이들 central moment을 이용해서 만든 공분산 행렬(covariance matrix)
$$ \Sigma = \left( \begin{array}{cc} \mu_{20} & \mu_{11} \\ \mu_{11} & \mu_{02} \end{array} \right) $$의 두 eigenvalue 중 큰 값에 해당하는 eigenvector가 물체의 정렬 방향을 알려준다.
이미지 처리에서 픽셀 좌표는 간격이 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;
}
};