Color Counting

Image Recognition 2010. 1. 18. 21:02

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

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

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

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

아래의 소스는 이것을 구현한 것이다. 컬러값이 주어지면 이것을 8로 나누면 비트정보를 기록할 바이트 배열의 위치가 나오고, 컬러값을 8로 나눈 나머지가 그 바이트에서 비트의 위치이므로 해당 비트가 체크가 안되어 있으면 새로운 컬러를 찾은 것이므로 비트마스크를 이용해서 비트를 기록하면 된다.
//
static BYTE bitmasks[] = {1, 2, 4, 8, 16, 32, 64, 128};//1바이트에서 비트위치를 표시하기 위한 마스크
int CountColors(BYTE *rgbimage, int w, int h) {
    BYTE *table =  new BYTE [1024 * 1024 * 2] ;
    memset(table, 0, 1024 * 1024 * 2) ;
    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
    }
    delete [] table ;
    return count ;
} ;

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

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

댓글을 달아 주세요