를 얻고, 이 식을 풀어서 ${\bf x}^*$을 구하면 된다. $\bf A^T \cdot A$는 $8\times 8$의 대칭 행렬로 역행렬을 구할 수 있다 (주어진 점들 중 한 직선 위에 놓이지 않는 점이 4개 이상이 있어야 한다). 따라서 최소자승해는 다음과 같이 쓸 수 있다:
한 평면에서 다른 평면으로 연결하는 2차원 변환 중에서 직선의 직선성을 유지하는 것은 perspective 변환(사영변환)이다. 이 변환의 부분인 affine 변환은 평행한 두 직선의 평행성을 그대로 유지한다. 따라서 사각형은 perspective 변환에 의해서 다시 사각형으로 변환된다. 물론 bilinear 변환도 사각형을 다른 사각형으로 변환시키지만 일반적으로 직선의 직선성은 보전하지 못한다. 이 직선성의 보존은 매우 중요한 특성이다. 카메라도 일종의 perspective 변환기로 영상을 센서에 형성할 때 찍는 대상의 직선은 그대로 영상에 직선으로 표현된다. (FOV가 큰 카메라는 렌즈 왜곡이 심해서 보존이 안된다) 평면에서의 변환을 다룰 때는 $2 \times 2$행렬보다는 $3\times 3$ 행렬을 이용하는 것이 더 편리하다. 이렇게 하면 평면에서 평행이동을 행렬의 요소로 넣어서 생각할 수 있다.
이 표현은 perspective 변환이 선형 변환임을 명시적으로 보여주므로 직선성이 보존된다는 사실 또한 자명해진다. $3\times 3$ 행렬로 표현할 때 평면의 좌표는 $(x, y ,1)^T$처럼 3번째 좌표의 값은 항상 1로 고정한다(homogeneous coordinate).
카메라로 물체를 촬영할 때, 가까운 거리에서 촬영을 하던, 먼 거리에서 촬영을 하던 두 영상은 크기 차이만 있는 동일한 모양의 물체 상을 만들어 낸다. perspective 변환은 3차원에 놓인 평면에서 평면으로 변환으로 생각할 수 있는데, 크기의 차이만 있는 경우에 같은 것으로 본다. 3차원에서 행렬 변환은 9개의 매개변수에 의해서 기술이 되는데, 전체적인 크기의 차이를 무시하므로 1개 매개변수가 줄어들어서 8개의 매개변수로 표현이 된다. perspective 변환을 아래처럼 쓰면 변환된 좌표의 3번째 성분은 일반적으로 1이 아니다. 3번째 좌표 $w$을 구한 후에 이 값으로 $x$, $y$를 나누어서 생각하면 된다.
$$\begin{bmatrix} x\\ y \\ w \end{bmatrix} = \begin{bmatrix} a_{11} & a_{21} & a_{31} \\ a_{12} & a_{22} & a_{32} \\ a_{13} & a_{23} & a_{33} \end{bmatrix} \begin{bmatrix} u \\ v \\1\end{bmatrix} \quad(a_{33}=1)$$
$$ x = x / w, \quad y = y / w$$
perspective 변환 행렬 $a_{ij}$는 4개의 점에 대응하는 출력 영상에서의 4 점이 주어지면 8개의 방정식을 만들 수 있고, 이를 이용해서 계수를 구할 수 있다. 그러나, 8차 방정식의 근의 공식이 없으므로 수치해석적으로 해결해야 한다. 그리고 주어진 4 점이 (입력 또는 출력) 일직선 위에 있으면 답을 구할 수 없고, 또 3개가 일직선 위에 있는 경우에는 이 변환은 평행성을 보존하는 affine 변환이 된다.(affine은 6개의 매개변수로 표현되고, 평행이동을 빼면 4개의 매개변수가 남는데 4차 방정식은 근의 공식이 있으므로 답을 적을 수 있다)
처럼 2 단계 변환의 곱으로 주어진다. 사변형에 정사각형으로 변환은 정사각형에서 사변형으로 변환의 역변환이므로 역행렬을 구해야 하나, 이보다는 수치적으로 안정적인 adjoint 행렬을 이용하는 것이 낫다(adjoint을 쓰면 determinant로 나누기를 할 필요가 없다). 이는 perspective변환에서 항상 좌표를 3번째 좌표로 나누어서 사용하기 때문에 가능하다.
양의 정수 $x$가 주어질 때, 이보다 크거나 같은 가장 작은 $2^n$으로 표현되는 숫자를 찾아보자. 왜? FFT 때문이다. 물론, $\tt n = int(ceil(\log(double(x)) / \log(2.)))$로 계산하거나,
int a = 1;
while (a < x) a <<= 1;
로 찾을 수 있다;
$2^{n-1} < x \le 2^n$ 사이에 있으면, 원하는 답은 $2^n$이다. $x=2^n$인 경우를 제외하고 모두 $n$번째 비트가 1로 세팅이 된다. 따라서, 통일시키기 위해서 1을 빼면, $x-1$ 은 $n$ 번째 비트가 항상 1로 주어진다. 이제, 남은 일은 $n-1$ 번째에서 0번째까지 모든 비트를 1로 채우면 된다. 그 결과에 1을 더하면 원하는 $2^n$을 얻는다. $n$-번째 비트가 1이고 이를 이용해서 하위 비트를 채우기 위해서는 차례로 >> 연산을 한 후에 or 연산을 하면 된다.
a = x - 1 a = 1xxxxxxxxxxxxxxxxxxxxxxxx a >> 1 = 01xxxxxxxxxxxxxxxxxxxxxxx a >> 2 = 001xxxxxxxxxxxxxxxxxxxxxx .......
31번의 >> 연산을 한 후에 or 연산을 하면 $n$ 이하의 모든 비트가 1로 채워진다(31은 최대인 경우다. 사전에 답을 모르므로 >>를 31번까지 해야 한다). 이것은 너무 낭비다. 잘 살펴보면,
a | (a>>1) = 11xxxxxxxxxxxxxxxxxxxxxxxxx
형태여서, 상위 두 자리 비트가 이미 세팅이 되어 있으므로, 이 결과를 다시 >> 2 하여 이전 결과와 or 연산을 하면 상위 4자리의 비트가 채워지고, 또다시 이 결과를 >>4 하고 난 후에 직전 결과와 or 연산을 하면 상위 8자리의 비트가 1로 채워진다. 이런 식으로 하면 >>16까지 하면 32자리를 모두 커버할 수 있다.
따라서, 전체적인 알고리즘은 $(x > 0)$
x-- ;
x |= (x >> 1); //상위 2 자리 채움
x |= (x >> 2); //상위 4자리 채움
x |= (x >> 4); //상위 8자리 채움
x |= (x >> 8); //상위 16자리 채움
x |= (x >> 16);//상위 32자리 채움
x++;
return x;
단, 32비트 머신에서만이다. 64비트 프로그래밍에서는 >>32 도 추가로 해주어야 한다.
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이 아니게 된다.
Adaptive threshold를 적용하는 데 있어서 윈도 계산의 로드를 줄이는 방법은 integral image을 이용하면 된다. 물론 메모리의 소요가 부가적으로 발생하지만, 요 근래의 스마트 기기에서는 메모리는 별로 문제가 안된다.
아래의 코드는 integral 이미지를 이용해서 moving 윈도 내의 픽셀 평균 (= local average)을 기준으로 영상을 이진화시키는 함수다 (정확히는 "평균값 - 3"이다. 여기서 3은 바코드 인식 open library인 zbar에서 쓰는 기준을 잡았다. zbar library에서는 moving average를 구해 임계값으로 사용하는데, 윈도가 움직이면서 나가는 픽셀과 들어오는 픽셀을 업데이트하는 과정이 정확히 구현이 되어 있지는 않다. 그렇지만 근사적으로는 맞게 구현되어 있으므로 코드는 대부분의 경우 원하는 데로 잘 동작을 한다. integral image를 이용하면 윈도가 이동에 따른 픽셀 정보를 업데이트하는 복잡한 과정이 필요 없이 integral image의 단순 합/차만 수행하면 된다)
"윈도 평균-3" 대신 윈도의 표준편차를 이용할 수 있다. 그러나 이 경우에는 합의 제곱에 대한 적분 영상이 하나 더 필요하고, 얼마의 편차를 허용할 것인지를 정해야 한다. 이 기준에 맞게 구현된 코드는 http://kipl.tistory.com/30에서 찾을 수 있다.
2차원 바코드가 아닌 일차원 바코드 영상을 이진화할 때는 이만큼 복잡한(?) 알고리즘을 쓸 필요가 없다. 일차원 바코드는 보통 한 scanline의 정보만으로도 인식이 가능하므로 라인 단위의 이진화를 시키면 충분히다. 이 경우도 moving average를 사용하면 매우 간단하게 adaptive 한 임계값을 구할 수 있다. scanline 기준이므로 integral image는 따로 필요하지 않다.
void makeIntegralImage(BYTE *image, int width, int height, int* intImage);
