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함수 내에서 알고리즘을 호출하여서 빠른 컴퓨터에서는 마크가 보이지 않을 수 있음. 테스트용이므로 상업적 사용을 허용하지 않음.
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);
이제는 내 땀이 들어갔던 핫코드가 잊히고 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 한 결과를 얻을 수 있다:
