Geometry & Recognition

WEB cam의 영상에 들어오는 QR코드의 FinderPattern (topLeft, topRight, bottomLeft ==> 붉은색 십자)와 Alignment pattern(==> 초록색 십자)을 찾고, 이를 이용해서 perspective 변환을 구해서 code의 bounding box을 찾는다. Alignment Pattern을 못 찾는 경우에는 bottomRight의 코너(==> 초록색 십자)를 찾고, 그마저도 실패하면, FinderPattern 3 개를 이용하여서 Affine 변환으로 bounding box을 찾는다.

웹  카메라:  이미지 형식: RGB24만 지원 (마이크로소프트의 vx-1000으로 테스트함)
                  이미지 크기: 640x480만 지원
                  영상을 보여주는 Callback함수 내에서 알고리즘을 호출하여서 빠른 컴퓨터에서는 마크가 보이지 않을 수 있음.
테스트용이므로 상업적 사용을 허용하지 않음.
 

실행 파일 (detector + decoder 포함):

32 비트 머신에서 float 형의 변수는 4 바이트의 메모리 공간을 차지한다. 즉, int와 같은 크기의 메모리가 할당된다. 그리고 4 바이트의 최상위 비트가 1로 세팅이 되면 이 float형의 변수는 음수를 의미한다. 따라서 float 형의 변수의 절댓값을 구하고 싶으면 메모리에 접근해서 4 바이트를 얻어 온 다음 최상위 비트만 0으로 만들고 나머지는 그대로 두면 된다. 비트 마스크를 이용해서 이 과정을 수행하고 싶으면 비트 마스크를

01111111 11111111 11111111 11111111 = 2^31 - 1 = 0x7F FF FF FF

처럼 잡아서 and 연산을 수행하면 된다:

float fast_abs(float fx) {
    int ix = *(int *)&fx ;    // 4 바이트 비트 데이터 정수로 변환;
    ix &= 0x7FFFFFFF;         // MSB 지우기
    return *(float *)&ix ;    // float 형으로 되돌려 줌;
}

한 평면에서 다른 평면으로 연결하는 2차원 변환 중에서 직선의 직선성을 유지하는 것은 perspective 변환(사영변환)이다. 이 변환의 부분인 affine 변환은 평행한 두 직선의 평행성을 그대로 유지한다. 따라서 사각형은 perspective 변환에 의해서 다시 사각형으로 변환된다. 물론 bilinear 변환도 사각형을 다른 사각형으로 변환시키지만 일반적으로 직선의 직선성은 보전하지 못한다. 이 직선성의 보존은 매우 중요한 특성이다. 카메라도 일종의 perspective 변환기로 영상을 센서에 형성할 때 찍는 대상의 직선은 그대로 영상에 직선으로 표현된다. (FOV가 큰 카메라는 렌즈 왜곡이 심해서 보존이 안된다) 평면에서의 변환을 다룰 때는 $2 \times 2$행렬보다는 $3\times 3$ 행렬을 이용하는 것이 더 편리하다. 이렇게 하면 평면에서 평행이동을 행렬의 요소로 넣어서 생각할 수 있다.

(ex) affine 변환: $$x = a_{11}  u + a_{21}  v + t_u$$

$$y = a_{12} u + a_{22} v + t_v$$

==>

$$\begin{bmatrix} x \\ y \\1\end{bmatrix} = \begin{bmatrix}a_{11} & a_{21} & t_u \\ a_{12} & a_{22} & t_v \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix}  u\\v\\   1   \end{bmatrix} $$

이 표현은 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차 방정식은 근의 공식이 있으므로 답을 적을 수 있다)

다행히 정사각형에서 사변형으로 변환은 수치해석에 의존하지 않고도 답을 적을 수 있다.

\begin{gather} (0,0) \rightarrow (x_0, y_0)\\ (1,0 ) \rightarrow (x_1, y_1)\\ (1,1) \rightarrow (x_2, y_2) \\ (0,1) \rightarrow (x_3, y_3) \\ \end{gather}

denom = (x1 - x2) * (y3 - y2) - (x3 - x2) * (y1 - y2);     
a11 = x1 - x0 + a13 * x1 ;
a21 = x3 - x0 + a23 * x3 ;
a31 = x0 ;
a12 = y1 - y0 + a13 * y1;
a22 = y3 - y0 + a23 * y3;
a32 = y0;
a13 = ((x0-x1+x2-x3)*(y3-y2) - (x3-x2)*(y0-y1+y2-y3)) / denom;
a23 = ((x1-x2)*(y0-y1+y2-y3) - (x0-x1+x2-x3)*(y1-y2)) / denom;
a33 = 1.0;

따라서 일반적인 사변형에서 사변형으로의 변환은 

처럼 2 단계 변환의 곱으로 주어진다. 사변형에 정사각형으로 변환은 정사각형에서 사변형으로 변환의 역변환이므로 역행렬을 구해야 하나, 이보다는 수치적으로 안정적인 adjoint 행렬을 이용하는 것이 낫다(adjoint을 쓰면 determinant로 나누기를 할 필요가 없다). 이는 perspective변환에서 항상 좌표를 3번째 좌표로 나누어서 사용하기 때문에 가능하다.