Color Counting

Image Recognition 2010. 1. 18. 21:02

컬러 이미지가 있을 때, 몇 가지 색상이 쓰였는가를 찾아내는 것은 간단한 문제가 아니다. 왜냐면 24비트 RGB 컬러 영상에서 최대로 가능한 컬러의 수는 256*256*256=16777216나 되어서 간단히 히스토그램을 이용해서 셀 문제가 아니다. 정수의 히스토그램을 이용한다고 하더라도 대략 64MB의 메모리가 필요하다.

그런데 한 영상에는 픽셀 수 이상의 컬러를 담을 수 없으므로, 실제로 필요한 메모리는 정수 배열로 하면, 4*(이미지 폭)*(이미지 높이) 정도만 필요로 한다. 정수 배열을 준비하여 컬러 값을 옮기고 나서 정렬 알고리즘을 이용해서 정수 배열을 크기 순서대로 정렬하면 컬러의 수와 도수를 구할 수 있다(적은 사이즈의 이미지/메모리가 작을 때 유리)

물론 STL의 map을 이용해서 간단히 컬러 히스토그램을 구현할 수 있다 (이것은 아무래도 모기를 잡는데 도끼를 휘두르는 것 같은 느낌이다). 이들 방법을 동원해서 프로그램을 하면 큰 이미지에 대해서는 그다지 빠르다는 느낌이 없다.
         std::map <DWORD, int> table ; 
         .... table [color]++;

만약에 사용된 컬러의 도수가 필요하지 않고 사용된 색상의 총 수에만 관심이 있다면 좀 더 빠른 방법을 찾을 수 있다. 색상이 사용되었는지 안 되었는지 표시하는 데는 1비트의 정보만 기록하면 되므로 총 16777216개의 색상이 사용되었는지 안되었는지를 기록하기 위해서는 1 바이트가 8개의 비트를 저장할 수 있으므로 16777216/8 = 2MB의 메모리만 필요로 한다. 이 값은 이미지의 크기에 상관없이 일정하다. 

아래 소스는 사용된 색상의 수를 총 수를 얻는 법을 구현한 것이다. 주어진 컬러 값을 8로 나누면 비트 정보를 기록할 바이트 배열의 위치가 나오고, 컬러 값을 8로 나눈 나머지가 그 바이트에서 비트의 위치이므로 해당 비트가 체크가 안되어 있으면 새로운 컬러를 찾은 것이므로 비트 마스크를 이용해서 비트를 기록하면 된다.

static BYTE bitmasks[] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};//1바이트에서 비트 위치를 표시하기 위한 마스크
int CountColors(BYTE *rgbimage, int w, int h) {
    std::vector<BYTE> (1024 * 1024 * 2, 0);
    int count = 0; 
    int k = w * h ;
    while (k--) {
        DWORD color = (*(DWORD*)rgbimage) & 0xFFFFFF;  //Little endian machine ;
        DWORD idx = color >> 3;
        DWORD bit_pos = color - (idx << 3);
        BYTE *a = &table[idx];
        if (!((*a) & bitmasks[bit_pos])) {//if bit is not set;
            *a |= bitmasks[bit_pos] ; //set bit;
            count++ ;
        };
        rgbimage += 3; //rgb
    }
    return count ;
} ;
728x90

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

Fant's Algorithm  (0) 2010.01.22
Affine Transformation  (0) 2010.01.20
Isometric Transformation  (0) 2010.01.11
Active Shape Model (3)  (0) 2009.12.30
Eigenface (2)  (0) 2009.12.28
Posted by helloktk
,