영상처리에서 한 픽셀의 수정을 위해서 주변픽셀의 정보를 요구하는 윈도우에 기반한 필터들은 일반적 연산비용이 큰 편이다. 한변의 길이가 W인 윈도우를 사용할 때  W^2의 번의 픽셀을 참조해야 하므로 윈도우가 클수록 그 비용이 제곱으로 커진다. 
선형 필터 중에는 x방향과 y 방향으로 연산이 분리가 가능해서 이 연산비용이 필터의 크기에만 비례하도록 만들 수 있다. 메디안 필터는 이런 분리가 안되는 비선형 필터중 하나다. 물론 근사적으로 x방향으로 메디안 필터링을 하고, 그 결과를 y방향으로 다시 메디안 필터링을 하여서 근사적인 메디안 필터를 구성하여 사용하기도 한다.  
그러나 윈도우가 움직이면서 윈도우내의 모든 픽셀이 다 바뀌는 것이 아니라 움직이는 방향에 수직인 가장자리 픽셀만 바뀐다는 사실을 이용하면 각각의 픽셀위의 윈도우에서 메디안을 찾는 작업을 할 필요가 없다.
예를 들면 스캔라인 방향(x-방향)으로 윈도우를 움직이면서 메디안 필터를 작용할 때, 윈도우가 오른쪽으로 1픽셀 움직이면 윈도우의 왼쪽 가장자리의 수직픽셀들은 새 윈도우에서 사라지고, 기존윈도우의 오른쪽 수직가장자리 앞의 픽셀들이 새로이 들어온다. 따라서 처음 한번만 윈도우에 대해서 메디안을 찾으면, 이 나가는 픽셀과 새로 들어오는 픽셀들만 고려하면 (2*W개)되므로 연산시간이 윈도우에 선형적으로만 늘어나게 되어서 연산비용을 많이 줄일 수 있다. 이 기법은 윈도우가 사각형인 필터들(평균, 최대, 최소...)에 적용이 가능하다.

아래의 코드는 이것을 구현한 것이다. 
-영상의 가장자리에서 윈도우폭의 절반에 해당하는 픽셀들은 따로 취급 해주어야 한다;
-y값의 변화는 영상을 일차원배열로 취급하였기 때문에 항상 y*width의 형태로만 나타난다. 따라서 곱셈을 없애기 위해서 모든 y의 변화는 width를 곱한 형태로 구현되게 했다.
-좌표값은 윈도우의 top-left의 위치를 기준으로 만들었고, 적용 픽셀은 윈도우의 중심픽셀이다.

// 경계에서의 픽셀처리가 없다;
// 윈도우의 topleft를 기준으로 작동하도록 만들어졌다(픽셀값은 윈도우 중심에서);
// y --> y * width 단위로 변경하여서 곱셈연산을 줄였다;
BOOL RunningMedianFilter(BYTE* image, int width, int height, int wSize/*=7*/, BYTE* out) {
    int hist[256] ;
    int hwSize = wSize/2;               // half-windows-size;
    wSize  = (hwSize<<1)+1;             // wSize=odd-number;
    int nW2     = wSize * wSize / 2;        // half number of pixels in the windows;

    int xoff = hwSize ;                 //outpixel의 x-출발점;
    int xEnd = width - wSize;           //window topleft의 한계;
    int yoff = hwSize * width ;         //outpixel의 y-출발점;
    int yEnd = (height - wSize) * width;

    //window의 topleft 위치를 옮기면서,  윈도우 중심위치의 픽셀의 median값을 찾는다;
    for (int y = 0 ; y < yEnd; y += width) {
        memset(hist, 0, sizeof(hist));
        //각각이 행에서 첫번째 윈도우에서의 메디안값은 정상적으로 구한다;
        int iyEnd = y + wSize * width;          //window-bottom;
        for (int iy = y ; iy < iyEnd; iy += width) {
            for (int ix = 0; ix < wSize; ix++)
                hist[image[iy + ix]]++ ;
        }
        //첫 윈도우에서 메디안 찾기;
        int median = 0;
        int ltmed = 0;                  //메디안 값보다 작은 픽셀의 수; <= nW2 이어야 한다;
        while(ltmed < nW2) {
            ltmed += hist[median];
            median++ ;
        };//==>ltmed > nW일 때도 생김-->이것을 없애기 위해서;
        while(ltmed > nW2) {
            median--;
            ltmed -= hist[median];
        };
        out[y + yoff + xoff] = median;
        //
        for (int x = 1; x < xEnd; x++) {
            for (iy = y; iy < iyEnd ; iy += width) {
                //왼편에서 기존의 윈도우에서 나가는 픽셀 제외;
                int v = image[iy + x - 1];
                hist[v]-- ;
                if(v < median) ltmed--;
                //오른편에서 들어오는 픽셀 추가;
                v = image[iy + x + wSize - 1] ;
                hist[v]++ ;
                if(v < median) ltmed++ ;
            }
            //update median;
            //ltmed <= nW2;
            while(ltmed < nW2) {
                ltmed += hist[median];
                median++ ;
            }; //ltmed>nW일 수 있으므로;
            while(ltmed > nW2) {
                median--;
                ltmed -= hist[median];
            }
            //윈도우 중심에서의 픽셀값;
            out[y + yoff + x + xoff] = median ;
        }
    }
    //결과이미지에서 경계영역이 처리안되어 있으므로 이부분에 대한 처리가 필요함;
    return TRUE ;
};
wSize = 11 결과(가장자리 5픽셀은 원본을 그대로 복사한 것이다)

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

Bicubic Interpolation  (1) 2010.01.14
Histogram Smoothing via Bezier Curve  (1) 2010.01.10
Running Median Filter  (0) 2010.01.07
Fast Median Filter 3x3  (0) 2009.11.27
Fant's Resampling  (0) 2008.12.17
Bright Preserving Histogram Equalization with Maximum Entropy  (0) 2008.07.31
Posted by helloktk