matlab에서 rgb 컬러 이미지를 gray 이미지로 바꿀 때, 호출하는 함수가 rgb2gray이다. 이 함수는 주어진 RGB 값에 다음과 같은 weight를 주어서 명암 값을 얻는다:
gray = 0.2989 * r + 0.5870 * g + 0.1140 * b ;
이 계산을 fixed-point 버전으로 바꾸어 보자. 정밀도를 유지하기 위해서는 소수점 이하 4자리까지 유지해야 하는데, 이것은 weight에 각각 10000을 곱한 값을 사용한 후에 다시 10000으로 나누면 된다 (10000을 곱하더라도 r, g, b가 0-255사이의 값이므로 최대로 255 * 10000 보다 작은 값이 나와서 32-비트 정수 범위 내에 있게 된다)
gray = (2989 * r + 5870 * g + 1140 * b) / 10000;
여기서 좀 더 개선을 할 수 있다. 10000으로 나누는 과정을 shift 연산으로 바꾸면 된다. 정밀도를 보존하기 위해서 10000보다 큰 2의 power의 수를 찾으면 2^14 = 16384 이 주어진다. 따라서 10000 대신에 2^14을 곱한 weight를 쓰고, 계산 결과를 오른쪽으로 14만큼 shift 연산을 하면 된다. 0.2989 * 2^14 = 4897.1776; 0.5870 * 2^14 = 9617.408; 0.1140 * 2^14 = 1867.776;
gray = (4897 * r + 9617 * g + 1868 * b) >> 14;
weight의 총 합 = 4897 + 9617 + 1868 < 2^14 이어서 gray 값은 255를 넘지 않고, 중간 계산은 32-비트 정수 범위 내에서만 이루어진다. 정말 빠를까?
내 점으로 만들어진 convex인 사변형에 어떤 점이 포함되어 있는지 않은지를 판별하는 문제는 프로그램을 하다 보면 종종 만나게 된다. 이보다 더 근본적인 문제는 주어진 점이 세 점으로 만들어진 삼각형의 내부점인가를 판단하는 것이다. 세 점이 주어지면, 시계방향이던, 아니면 반시계 방향이던, 한 방향으로 oriented 된 삼각형이 구성이 된다. 삼각형의 내부점들은 이 삼각형은 이루는 변(orientation 때문에 이 변들은 방향을 가지는 벡터임)에 대해서 모두 한쪽으로 치우쳐 상태가 된다. 이것을 수학적으로 표현하면, 삼각형의 세 변 벡터와 각각의 변 벡터의 시작점에서 주어진 점까지 선분이 만드는 벡터와의 외적의 부호가 동일한 값을 갖는다(삼각형의 CW나 CCW인 것에 상관없다)
// 평면에서 두 벡터의 외적은 숫자를 준다; 3차원으로 생각할 때 z-성분이다.
BOOL insideTriangle(POINT p, POINT A, POINT POINT B, POINT C) {
ab = vec(A,B)와 vec(A,P)의 외적;
bc = vec(B,C)와 vec(B,P)의 외적;
ca = vec(C,A)와 vec(C,P)의 외적;
// 점이 변 위에 놓인 경우 외적이 0이 되므로 sign함수를 쓰는 경우 주의!
// return SIGN(ab) == SIGN(bc) && SIGN(bc) == SIGN(ca);
return (ab * bc >= 0) && (bc * ca >=0) && (ca * ab >= 0)
};
(convex) 사변형은 항상 두 개의 삼각형으로 나누어지므로, 각각의 삼각형에 대해서 테스트하면 된다(이 방식이 직접적으로 4 변에 대해서 모두 다 같은 쪽에 치우쳐 있는가를 테스트하는 것보다 효과적이다. 삼각형을 이용하면 4 변에 대해서 다 테스트하지 않아도 중간에 결과를 얻을 수 있다. 물론, 주어진 사변형이 처음에 어떤 방향으로 orient 되었는지의 정보가 주어졌다면 훨씬 더 빨리 판별할 수 있는 방법이 있다).
// 점이 변 위에 있는 경우는 포함한다;
// 사변형의 orientation에 무관하다(단, convex이어야 한다);
BOOL insideQuadrilateral(POINT p, POINT A, POINT B, POINT C, POINT D) {
if (insideTriangle(p, A, B, D)) return TRUE;
else if (insideTriangle(p, B, C, D)) return TRUE;
return FALSE;
}
기하 알고리즘을 다루다 보면 삼각형 그중에서도 직각 삼각형을 다루어야 할 경우가 많다. 대부분의 문제에서는 직각이 되는 꼭짓점을 가운데 두고 세 꼭짓점이 반시계 방향으로 정렬되는 형태로 쓰였기를 원한다. 이 경우 먼저 해야 할 일은 직각이 되는 꼭짓점을 찾는 것이다 (수치적으로 정확히 직각이지 않은 데이터도 처리할 수 있도록 구현이 되어야 한다). 여러 가지 방법이 있을 수 있지만, 그중 간단한 방법은 이 꼭짓점의 대변이 가장 길다는 점을 이용하면 된다. 즉, 3 변의 길이를 구하고, 이 중에서 가장 긴 변을 마주 보는 꼭짓점을 찾으면 된다. 따라서 문제는 3개의 숫자 중에서 가장 큰 것의 번호를 찾으면 된다.
세 숫자를 num [] ={a, b, c} 라 하자, a가 가장 크려면, a > b, a > c이어야 한다. 그렇지 않다면, b나 c 중에 최댓값이 있다. 따라서 b와 c만 비교하면 된다.
if (a > b && a > c) return 0;
else if (b > c) return 1;
else return 2;
이제는 내 땀이 들어갔던 핫코드가 잊히고 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 한 결과를 얻을 수 있다:
회색으로 칠해진 바닥에 검정색 점과 흰색 점들이 분포해 있다. 이제 이 점들을 몇 단계의 간단한 직선가르기로 분류를 하려고 한다. 먼저 바닥에 임의로 선을 그려서 바닥의 점이 선의 오른쪽에 (직선의 방향벡터를 생각하면 오른쪽의 의미가 명확해진다) 위치하면 흰색으로 분류하는 규칙을 마련하자.
그런데 이 직선가르기에 의한 분류는 "직선의 오른쪽에 검정색의 점이 있거나, 직선의 왼쪽에 흰색의 점이 있을 때 점들을 잘못 분류하는 에러를 일으킨다. 따라서 에러를 최소화시키기 위해서 여러 가지 직선을 그려보아서 분류에러가 최소인것을 분류기로 선택한다. 이렇게 만든 직선분류기는 대부분의 경우에 단순한 동전던지기에 의한 랜덤분류방법(50% 에러)보다는 좀 더 낳은 결과를 낸다.
다음 단계의 직선 가르기를 할 때는 이전 단계의 분류규칙에 의한 잘못을 참조하여서 만들어야 한다. 간단한 방법은 이전에 제대로 분류된 흰색 점은 약간 덜 희게 하고, 제대로 분류된 검정점도 덜 검게 하면, 잘못 분류된 흰색과 검정색의 점만 두드려지게 보이게 되어 다음번 직선 가르기를 할 때 이전 단계에서 잘못 분류한 점들이 더 눈에 잘 보이게 되므로 더 많이 참고를 하게 된다(기술적으로는 잘못 분류된 점들이 에러에 기여하는 가중치를 상대적으로 더 크게 만드는 것이다). 이러한 과정을 반복적으로 하면 횟수만큼의 직선분류기를 가지게 되고, 각각의 분류기에 의한 분류에러도 가지게 된다.
이들 분류기를 선형결합을 하면 개별적인 분류기보다도 훨씬 분류에러가 적은 강력한 분류기를 만들 수 있는데, 이때, 각각의 직선분류기에 주는 가중치는 그 분류기가 일으키는 에러를 참조해서 만든다. Adaboost 알고리즘에서는 직선분류기가 ε의 에러를 주면 최종분류에 기여하는 정도는 α = log (1-ε)/ε 로 잡는다.
