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);
더보기
void makeIntegralImage(BYTE *image, int width, int height, int* intImage) {    
    intImage[0] = image[0]; 
    for (int x = 1; x < width; ++x)
        intImage[x] = intImage[x - 1] + image[x];
    //next line;
    image += width;
    for (int y = 1, offset = y * width; y < height; ++y, offset += width) {
        int linesum = 0;
        for(int x = 0; x < width; ++x) {
            linesum += image[x];
            intImage[offset + x] = intImage[offset - width + x] + linesum ;
        }
        //next line;
        image += width ;
    }
}
/*
** moving window의 중심에 해당픽셀을 놓을 필요는 없다; 
*/
void thresholdByIntegralImage(BYTE *image, int width, int height, int wsz, BYTE *matrix) { 
    std::vector<int> intImage(width * height);
    makeIntegralImage(image, width, height, &intImage[0]);
    const int winArea = wsz * wsz ;
    /* const int wsz = 10;*/
    for (int y = 0, offset = 0; y < height; y++, offset += width) {
        int top = y - (wsz >> 1) ;
        if (top < 0 ) top = 0;
        else if (top > height - wsz) top = height - wsz;
        int bottom = top + wsz - 1;
        // y-range = [top, bottom];
        for (int x = 0; x < width; x++) {
            int left = x - (wsz>>1);
            if (left < 0) left = 0;
            else if (left > width - wsz) left = width - wsz;
            int right = left + wsz - 1;
            // xrange = [left, right];
            //
            int sum1 = (left > 0  && top > 0) ? intImage[(top - 1) * width + left - 1] : 0;
            int sum2 = (left > 0) ? intImage[bottom * width + left - 1] : 0;
            int sum3 = (top > 0) ? intImage[(top - 1) * width + right] : 0;
            //
            int graySum = intImage[bottom * width + right] - sum3 - sum2 + sum1;
            // overflow ? 
            // Threshold T = (window_mean - 3); why 3?
            if ((image[offset + x] + 3) * winArea <= graySum)
                matrix[offset + x] = 0xFF; //inverted!
            else
                matrix[offset + x] = 0x00;
        }
    }
}

 

QR 코드가 인쇄된 지면에 그라데이션이 있어서 전역 이진화로는 코드의 분리가 쉽지 않다.
728x90

'Image Recognition' 카테고리의 다른 글

Least Squares Estimation of Perspective Transformation  (4) 2012.02.15
Perspective Transformation  (2) 2012.02.14
Peak Finder  (1) 2012.02.02
QR-code: decoder  (0) 2012.01.26
QR-code: detector  (0) 2012.01.12
Posted by helloktk
,

QR-code: decoder

Image Recognition 2012. 1. 26. 00:54

이미지에서 코드의 영역을 검출한 후에 는 코드 영역의 비트 값을 읽어 들여서 디코딩하는 과정을 거쳐야 최종적으로 QR-code가 담고 있는 정보를 읽을 수 있다. 검출된 코드 영역은 역 perspective 변환을 거치면 정사각형의 코드 영역으로 변환된다. 그러나 이 과정은 실제 프로그램 설계에서는 불필요한 과정이다. 이미 주어진 perspective 변환을 이용하면, 이진화된 원래의 이미지에서 바로 코드를 재구성할 수 있다. 아래의 그림은 이 과정을 빠르게 수행하기 위해서 코드 영역을 블록 단위로 구분하는 마스크 이미지를 만든 것을 보여준다.

 

 

마스크 이미지: 컬러는 각 블록의 라벨링을 표현하기 위해서 사용했다.

 

이 마스크를 이용하면 각 블럭의 비트 값을 majority test에 의해서 쉽게 결정할 수 있다.
재구성된 코드블럭:

 


이제 나머지는 QR-code의 스펙을 참고하면 (Reed-Solomon error-correction code는 영상처리 관점에서 약간 벗어나므로 취급하지 않음) 인코딩 된 정보를 얻을 수 있다:

 

 

 

 

예제 코드의 정보는

 

 

728x90

'Image Recognition' 카테고리의 다른 글

Integral Image을 이용한 Adaptive Threshold  (0) 2012.02.04
Peak Finder  (1) 2012.02.02
QR-code: detector  (0) 2012.01.12
Adaboost  (0) 2010.12.28
Blur Detection  (0) 2010.05.25
Posted by helloktk
,

이제는 내 땀이 들어갔던 핫코드가 잊히고 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 한 결과를 얻을 수 있다:

 

 

 

728x90

'Image Recognition' 카테고리의 다른 글

Peak Finder  (1) 2012.02.02
QR-code: decoder  (0) 2012.01.26
Adaboost  (0) 2010.12.28
Blur Detection  (0) 2010.05.25
Savitzky-Golay Smoothing Filter  (2) 2010.03.24
Posted by helloktk
,