Geometry & Recognition

이제는 내 땀이 들어갔던 핫코드가 잊히고 QR코드가 대세인 모양이다...
우연히, ZXing library를 보고, c#(cpp-코드도 있음) -> cpp 코드로 바꾸어 본 것이다.

영상에서 코드를 검출하기 위한 전 단계로 영상을 이진화시켜야 한다. QR-code는 대체로 흰 배경에 검은색으로 인쇄가 되고 코드가 있는 영역은 검정과 흰색이 일정한(?) 비율로 섞여있다는 특징을 이용하면 좀 더 용이하게 이진화를 시킬 수 있게 된다. 전체 영상을 8x8 크기의 블록으로 나누고, 각 블록을 이진화시키는데, 이진화의 임계값은 주변 25개의 블록의 평균값을 이용한다(코드가 없는 영역은 픽셀 값이 균일할 수 있으므로 이런 경우에 예외적으로 처리하는 방법이 필요하다). 어느 정도 empirical 한 수치가 들어간다.

// 한 8x8블럭의 검정(코드)과 하얀(배경)으로 구분짓는 값을 결정한다;
// 밝은 픽셀과 어두운 픽셀값간의 값의 차이가 24이상이면, 블럭평균값을 반환하고,
// 아니면, 이 블럭은 하얀색(배경)으로 인식하고, 이 경우에 임계값은 배경의 가장 어두운
// 값의 절반을 이용한다.
void calculateBlackPoints(BYTE *luminances, int stride, 
                          int *blackPoints, int subWidth, int subHeight) {
    int lineStart = 0;
    for (int y = 0; y < subHeight; y++) {
        for (int x = 0; x < subWidth; x++) {
            int sum = 0;
            int min = 255;
            int max = 0;
            for (int yy = 0; yy < 8; yy++) {
                int offset = ((y << 3) + yy) * stride + (x << 3);
                for (int xx = 0; xx < 8; xx++) {
                    int pixel = luminances[offset + xx] & 0xff;
                    sum += pixel;
                    if (pixel < min) {
                        min = pixel;
                    }
                    if (pixel > max) {
                        max = pixel;
                    }
                }
            }
            
            int average = (max - min > 24)?(sum >> 6):(min >> 1);
            blackPoints[lineStart + x] = average;
        }
        // move to next line;
        lineStart += subWidth;
    }
}   
// 주어진 임계값을 이용해서 한 개의 8x8 블럭내의 픽셀들을 이진화시킨다.
void threshold8x8Block(BYTE * luminances, int stride, 
                       int xoffset, int yoffset, 
                       int threshold, 
                       BYTE *matrix) {
    int offset = yoffset * stride + xoffset;
    for (int y = 0; y < 8; y++) {
        matrix[offset + 0] = luminances[offset + 0] < threshold ? 0x00 : 0xff ;
        matrix[offset + 1] = luminances[offset + 1] < threshold ? 0x00 : 0xff ;
        matrix[offset + 2] = luminances[offset + 2] < threshold ? 0x00 : 0xff ;
        matrix[offset + 3] = luminances[offset + 3] < threshold ? 0x00 : 0xff ;
        matrix[offset + 4] = luminances[offset + 4] < threshold ? 0x00 : 0xff ;
        matrix[offset + 5] = luminances[offset + 5] < threshold ? 0x00 : 0xff ;
        matrix[offset + 6] = luminances[offset + 6] < threshold ? 0x00 : 0xff ;
        matrix[offset + 7] = luminances[offset + 7] < threshold ? 0x00 : 0xff ;
        //moveto next line;
        offset += stride;
    }
}
// 각각의 8x8 블럭은 주변의 25개 블럭의 그레이값의 평균을 이용해서 이진화를 시도한다;
// 가장자리 특히 오른쪽과 아래쪽 0-7픽셀은 처리가 안될 수 도 있다.
void  calculateThresholdForBlock(BYTE *luminances, int stride, 
                                 int *blackPoints, int subWidth, int subHeight, 
                                 BYTE *matrix) {
    for (int y = 0; y < subHeight; y++) {
        for (int x = 0; x < subWidth; x++) {
            int left = (x > 1)?x:2;
            left = (left < subWidth - 2)?left:subWidth - 3; // center-x;
            int top = (y > 1)?y:2;
            top = (top < subHeight - 2)?top:subHeight - 3;  // center-y;
            int sum = 0;
            // real top-line pointer;
            int *blackRow = &blackPoints[(top - 2) * subWidth];
            for (int yy = - 2; yy <= 2; yy++) {
                // int *blackRow = &blackPoints[(top + yy) * subWidth];
                sum += blackRow[left - 2];
                sum += blackRow[left - 1];
                sum += blackRow[left];
                sum += blackRow[left + 1];
                sum += blackRow[left + 2]; 
                // moveto nextline;
                blackRow += subWidth;
            }
            int average = sum / 25;
            threshold8x8Block(luminances, stride, x << 3, y << 3, average, matrix);
        }
    }
}
// test module;
void binarizeEntireImageHybrid(CRaster& raster, CRaster& out) {
    CSize sz = raster.GetSize();
    int width = sz.cx ;
    int height = sz.cy ;
    int subWidth = width >> 3 ;
    int subHeight = height >> 3 ;
    int *blackPoints = new int [subWidth * subHeight];
    calculateBlackPoints((BYTE *)raster.GetDataPtr(), (int)raster.GetBytesPerLine(), 
                            blackPoints, subWidth, subHeight);
    calculateThresholdForBlock((BYTE *)raster.GetDataPtr(), (int)raster.GetBytesPerLine(), 
                                blackPoints, subWidth, subHeight, (BYTE *)out.GetDataPtr());
    delete [] blackPoints;
};

-이 단계 후에는 QR코드의 finderpattern(영상의 검정/하얀 네모 박스로 둘러싸인 패턴)를 찾으면 된다. 이 패던은 영상의 라인을 스캔하면 검점-하얀-검정-하얀-검점이 폭의 비가 1 : 1 : 3 : 1 : 1으로 나타난다는 QR코드의 특성을 이용하면 쉽게 찾을 수 있다.

아래 그림(반전을 함)은 이것을 구현하여서 finder pattern의 중심(빨간 십자)을 찾는 결과를 표시한 것이다. 이 부분의 구현은 코드가 좀 길므로(그러나 쉬움) ZXing library를 직접 참고하면 된다. 이 작업은 ZXing 라이브러리에 몇 가지 문제점과 비효율적인 부분이 있어서 코드를 새롭게 작성했음을 밝힌다.

-finder pattern의 세 중심을 찾은 후에는 추가로 bottom-right 영역의 alignment pattern (W-B-W=1:1:1)을 찾으면 QR코드가 perspective view에 의해서 코드가 왜곡이 된 정보를 구할 수 있다. 그러나, 이 alignment pattern은 finder pattern 보다도 찾기가 쉽지는 않다. 이 경우에는 finder pattern의 3점을 이용해서 왜곡정보를 얻어야 하는데, 이 경우에 가능한 기하학적인 변환은 affine변환으로 근사를 시켜야 한다 (직선의 평행성을 보존하는 2d-변환으로 일반적인 직사각형을 평형 사변형으로 바꾸고, 6개의 매개변수에 의해서 결정이 된다).
alignment pattern의 중심이 얻어지면 4개의 중심점으로 perspective변환의 매개변수를 얻을 수 있다.

-alignment pattern의 중심(녹색 십자)을 찾는 결과이다: finder pattern 3개 (bottomLeft, topLeft, topRight)와 alignment pattern이 화면상에서 시계방향으로 정렬이 된 사변형의 꼭짓점을 이룰 때, 정상적인 코드 이미지이고, 반대로 반시계 방향으로 주어지면 뒷면에서 찍은 코드 이미지이므로, 디코딩 시 이 점을 고려해야 한다.

- finder pattern과 alignenment pattern(이것을 찾을 수 없는 경우에는 affine변환을 이용한다)의 정보를 이용해서 코드 영역을 inverse perspective 변환을 통해서 rectify 한 결과를 얻을 수 있다: