1차원 바코드 인식은 이미지에서 바코드 영역 전체를 분리하는 과정이 없이도 처리가 가능하다. 이미지의 한 스캔라인이 바코드 영역에 걸쳐있기만 해도 인식하는데 충분하기 때문이다. 스캔라인에서 바코드 정보를 뽑아내기 위해서는 이진화 과정을 거쳐야 하는데 이 또한 adaptive 한 방식으로 처리할 수 있다. 바코드 영역은 전경과 배경이 매우 균일하게 섞여 있으므로 적당한 너비의 스캔라인 구간(moving window)에서 픽셀 평균값을 기준으로 임계값을 정해도 충분하다. 아래의 코드는 일정한 크기의 moving window를 이용해서 바코드를 담고 있는 영상을 스캔라인 별로 이진화를 시킨다. 윈도가 한 픽셀 이동하면 이전 평균값을 빼고, 새로운 픽셀 값을 더해서 윈도 평균을 업데이트한다. 스캔라인 시작 부분에서는 윈도 평균값 정보가 없으므로 이전 스캔라인의 평균값을 사용한다. 이 알고리즘은 이미지를 한 번만 스캔하고도 이진화가 가능해서 연산 비용이 매우 저렴한 알고리즘이다(바코드를 발견한 스캔라인에서 종료시키면 이미지를 다 처리할 필요도 없다). 그리고 윈도 크기를 이미지 폭으로 하더라도 여전히 스캔라인 별로 달라지는 adaptive 방식이다. 처음 몇 개의 스캔라인이 바코드와 겹치는 영역이 아니면 윈도 평균값 계산이 제대로 이루어지지 않으므로 잘못 이진화될 수 있지만 바코드 영역에 들어서면 정상적으로 동작하게 된다. 적용 예를 보면 시작 라인이 (비트맵의 시작 라인은 맨 아래이다) 바코드를 포함하지 않으므로 잘못 이진화가 되는 것을 볼 수 있다. 글씨가 전 영역에 거의 균일하게 인쇄된 이미지의 이진화에도 잘 동작하여 OCR에도 응용할 수 있다.
void MovingAvgThreshold(BYTE *image, int width, int height, int wsz, BYTE *res) {
if (wsz < 0 || wsz > width) wsz = width / 4; // default window size;
double sum = 128 * wsz; // initial moving window sum = 128 * wsz;
double sumOld = sum; // backup sum of the first wsz pixels in each row;
for (int y = 0, pos = 0; y < height; y++) {
sum = sumOld; // reset sum = result of previous row;
for (int x = 0; x < wsz; x++) {
int v = image[pos];
sum += v - sum / wsz; // update sum;
res[pos++] = v < (sum / wsz) ? 0: 0xFF;
}
sumOld = sum; // backup for next line;
for (int x = wsz; x < width; x++) {
int v = image[pos];
sum += v - sum / wsz; // update sum;
res[pos++] = v < (sum / wsz) ? 0: 0xFF;
}
}
}
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);
제대로 segmented 된 그레이 영상은 원래의 영상이 나타내고자 하는 전경이 잘 표현이 된 것이다. 이 경우의 원래 영상과 segmented 된 영상은 높은 상관관계를 갖는다. 따라서, 세그먼트를 위한 임계값의 설정 기준으로 이 상관계수를 최대로 하는 임계값을 찾는 것도 좋은 방법 중의 하나가 될 수 있다.
여기서 사용할 상관계수는 원래의 영상(A)과 전경과 배경을 그들의 픽셀 평균값으로 대체한 segmented 된 영상(B) 간의 상관계수를 사용한다. 임계값이 $T$인 경우 세그먼트된 영상B는
로 나타난다. 여기서 $m_0$는 배경 픽셀의 평균값이고, $m_1$은 전경 픽셀의 평균값이다. 이 값은 임계값 $T$에 따라 달라진다. 임계값이 높으면 $m_0$는 커지고, 반대로 $m_1$은 작아진다.
임계값이 $T$일 때배경 픽셀 비를 $p$,전경 픽셀 비를 $q(=1- p)$라 하면 segmented된 영상 B는 각 영역에서의 픽셀 값을 평균으로 대체했으므로 원본 영상의 평균과 같다. 또한, 원본 영상의 분산은 임계값에 무관하게 일정한 값을 유지한다. 이를 정리하면,
이미지를 이진화시키기 위해서 여러 알고리즘이 사용된다. 그중 이미지 전체에 대해 하나의 임계값으로 이진화시키는 전역 이진화 알고리즘은 간단하고 빠르기 때문에 많이 이용이 된다. 그러나 이미지를 형성할 때 조명 조건이 균일하지 않은 경우에는 전역 이진화는 원하는 결과를 얻기가 힘들다. 이런 경우에는 각각의 픽셀 주위의 그레이 값을 참조하여 임계치를 결정하는 국소적 이진화 방법을 사용한다. 국소적 이진화에서 임계값을 추출하는 간단한 방법은 윈도 내의 평균값을 이용하면 된다. 좀 더 개선된 알고리즘은 평균값($m(x, y)$)을 참조하되, 편차($\sigma(x, y)$)를 한번 더 고려해 주는 것이다. 이렇게 하여 잡은 국소적 임계값은 다음과 같이 표현된다:
여기서 $128$은 그레이 값이 가질 수 있는 최대 편차를 의미한다. 편차가 $128$이면 단순 평균값으로 취한다는 의미가 된다. 그 외의 경우는 표준편차와 128의 차이(항상 음수다)에 비례하는 값으로 윈도 평균값을 offset 한 값을 임계치로 잡는다. $\text{factor}$는 일반적으로 정해지지 않고, 실험적으로 $[0.2, 0.5]$ 사이의 값이 취해진다. (문서처럼 배경이 흰색인 경우는 $\text{factor} > 0$이지만, 검정 배경에 흰색 글씨를 처리하는 경우는 음수의 값을 취하는 것이 맞다) 국소적인 이진화 알고리즘은 매 픽셀마다 윈도를 잡아서 계산해야 하므로 연산 비용이 많이 든다. 충분한 메모리를 갖춘 시스템의 경우에는 적분 이미지(integral image)를 이용하면 윈도 연산에 소요되는 비용을 대폭 줄일 수 있다.. 국소적 이진화 알고리즘에서 윈도 크기와 $\text{factor}$를 결정하는 기준은 무엇일까? 이것은 해결하고자 하는 문제의 특성, 예를 들면 스캔된 문서를 이진화시키는 경우에는 윈도에 충분한 글자가 들어 있어야 한다... 등에 많이 의존한다.
void make_int_img12(BYTE *gray, int width, int height, *int intimage, int *intsqimg);
이미지의 히스토그램을 이용하여 전경과 배경을 분리하는 이진화는 가우시안 mixture model과 EM 알고리즘을 적용하기에 좋은 예다. 히스토그램에는 전경에 해당하는 픽셀 분포와 배경에 해당하는 픽셀 분포가 혼합되어 있다. 이를 두 가우시안의 혼합으로 모델링하고 EM 알고리즘을 사용해서 mixing parameter(πa), 각 클래스의 평균(μa) 과 표준편차(σa)를 추정한다. N개의 Gaussian mixture일 때,
Mixing parameter가πa (a=1, 2,..., nclass)일 때 특정 픽셀 값(=xi)이 클래스 a 소속일posterior 확률은
로 쓸 수 있다. posterior 정보를 이용하면 mixing parameter, 평균 그리고 분산은 다음 식으로 주어진다. H[i]=Hi는 이미지의 히스토그램을 나타내고, bin 인덱스 i는 픽셀 값 xi를 나타낸다:
log-likelihood:
// mixing 클래스를 기술하는 클래스;
struct mixclass {
double prob ; // mixing parameter;
double mean ; // mean
double var ; // variance;
};