Integral Image을 이용한 Adaptive Threshold

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 코드가 인쇄된 지면에 그라데이션이 있어서 전역 이진화로는 코드의 분리가 쉽지 않다.