Rolling Ball Transformation

이미지를 획득할 때 조명 조건이 균일하지 않으면 동일한 물체라도 위치에 따라 밝기가 달라져 이후의 영상 처리 과정이 복잡해진다. 따라서 물체를 분석하기에 앞서 조명에 의한 배경의 불균일성을 제거하는 전처리 과정이 필요한 경우가 많다.

일반적으로 조명에 의한 밝기 변화는 공간적으로 넓은 영역에 걸쳐 천천히 변하는 저주파(low-frequency) 성분인 반면, 전경의 물체는 상대적으로 작은 영역에서 급격하게 밝기가 변하는 고주파(high-frequency) 성분을 가진다. 이러한 특성을 이용하면 배경과 전경을 비교적 쉽게 분리할 수 있다.

가장 간단한 방법은 전경 물체보다 충분히 큰 윈도를 사용하는 median filter를 적용하여 배경 영상을 추정하는 것이다. 윈도가 충분히 크면 작은 물체들은 대부분 제거되고 배경만 남게 된다. 그러나 median filter는 윈도 내의 픽셀을 정렬해야 하므로 계산량이 많아, 큰 윈도를 사용할수록 연산 비용이 크게 증가한다.

보다 계산 비용이 적은 방법은 이미지를 하나의 3차원 곡면(surface) 으로 생각하는 것이다. 영상의 각 픽셀 \((x,y)\)를 평면상의 좌표, 밝기값 \(I(x,y)\)를 높이로 생각하면 이미지는 3차원 공간에서 하나의 곡면으로 표현된다. 조명이 완만하게 변화하는 경우에는 이 곡면의 배경을 하나의 평면 또는 완만한 곡면으로 근사할 수 있다.

가장 단순한 접근은 최소자승법(least squares)을 이용하여 이미지 곡면을 가장 잘 근사하는 평면을 구하는 것이다. 그러나 실제 영상에서는 전경의 물체가 배경보다 높거나 낮은 돌출부를 형성하므로, 이들은 평면 추정에서 이상치(outlier) 역할을 한다. 특히 전경이 넓은 영역을 차지하는 경우에는 최소자승법으로는 정확한 배경을 추정하기 어렵다. 따라서 이러한 경우에는 이상치의 영향을 적게 받는 보다 강인한(robust) 배경 추정 알고리즘이 필요하다.

대표적인 방법이 Rolling Ball 알고리즘이다. 이미지를 3차원 곡면으로 생각할 때, 전경(밝은 물체)이 영상에서 차지하는 비율이 크지 않다면 충분히 큰 반지름을 가진 공을 곡면의 아래쪽에서 굴릴 수 있다. 공은 작은 돌출부인 전경 물체에는 거의 영향을 받지 않고 전체적인 곡면의 아래쪽을 따라 움직인다. 이때 공의 표면이 그리는 접곡면(envelope)이 바로 배경 곡면이 된다. 그림 (A)는 전경이 배경보다 밝은 경우를 나타내며, 반대로 전경이 배경보다 어두운 경우에는 그림 (B)와 같이 공을 곡면의 위쪽에서 굴려 동일한 원리로 배경을 추정할 수 있다.

Rolling Ball 알고리즘은 물체의 세부 구조에는 영향을 거의 받지 않으면서 배경의 완만한 밝기 변화만 효과적으로 추출할 수 있으므로, 현미경 영상이나 의료 영상과 같이 조명 불균일이 큰 영상의 배경 보정(background correction)에 널리 사용된다.

이미지 곡면에 작은 요철이나 잡음이 많이 존재하더라도, 반지름이 충분히 큰 공을 사용하면 이러한 국소적인 변화는 대부분 무시되고 전체적으로 부드러운 배경 곡면을 추정할 수 있다. 공이 이미지 곡면을 따라 이동하는 동안에는 공의 표면과 이미지 곡면이 서로 겹치지 않으면서 최소 한 점 이상에서 접촉하도록 공의 위치를 결정한다. 이때 공 표면을 작은 패치(patch)로 미리 샘플링해 두면, 각 패치의 높이와 해당 위치의 이미지 밝기값을 비교하는 방식으로 접촉 여부를 효율적으로 계산할 수 있다.

공의 반경이 매우 큰 경우에는 연산량을 줄이기 위해 먼저 원본 이미지를 축소한 뒤 Rolling Ball 알고리즘을 적용하고, 추정된 배경 영상을 보간(interpolation)을 이용하여 원래 크기로 복원하는 방법을 많이 사용한다. 배경은 공간적으로 천천히 변화하는 저주파 성분이므로, 이러한 축소 및 복원 과정에서도 배경 추정의 정확도는 거의 유지되면서 계산 시간을 크게 줄일 수 있다.

다음 예는 밝은 배경에 어두운 전경이 있는 영상에 Rolling Ball 알고리즘을 적용한 결과이다. Rolling Ball 알고리즘은 일반적으로 밝은 전경과 어두운 배경을 가정하므로, 먼저 원본 영상의 negative 영상을 생성하여 어두운 전경을 밝은 전경으로 변환한다. 그런 다음 negative 영상에 Rolling Ball 변환을 적용하여 배경 영상을 추정한다. 마지막으로 추정된 배경 영상을 원래 영상의 밝기 극성에 맞게 다시 변환한 후 원본 영상에서 이를 제거하면, 조명에 의한 배경의 불균일성이 보정되고 전경 물체만 균일한 밝기로 남게 된다.

 

 negative image:

radius=16;

radius=5:

배경을 뺀 결과(radius=16):

#define SQR(x) ((x)*(x))
struct RollingBall {
    std::vector<BYTE> data;
    int patchwidth;
    RollingBall(int radius) {
        int artrimper;
        if (radius <= 30)
            artrimper = 12; // trim 24% in x and y
        else if (radius <= 100) 
            artrimper = 16; // trim 32% in x and y
        else 
            artrimper = 20; // trim 40% in x and y
        
        Build(radius, artrimper);
    }
    void Build(int ballradius, int artrimper) {
        if (ballradius < 1) ballradius = 1;
        const int diam = ballradius << 1;
        const int xtrim = (artrimper * diam) / 100;
        const int hwpatch = ballradius - xtrim;
        patchwidth = (hwpatch<<1) + 1;			// make odd number;
        data.resize(patchwidth * patchwidth, 0);

        const int rsquare = SQR(ballradius);
        for (int k = data.size(); k-->0;) {
            int x = k % (patchwidth) - hwpatch; //relative to patch center-x.
            int y = k / (patchwidth) - hwpatch; //relative to patch center-y;
            int tmp = rsquare - SQR(x) - SQR(y);
            if (tmp > 0) data[k] = int(sqrt(double(tmp)));
        }
    }
};

// processing을 빠르게 하기 위해서, ball의 반경이 큰 경우에는 원본이미지를 
// 축소하여서(2,4,8,..) 처리한 후에, 처리 안된 점들은 interpolation을 하여서
// bacground image을 생성하면 된다.
void RollBall(const RollingBall& ball,                  //rolling ball object;
              BYTE **image, int width, int height,      //source image;
              BYTE **background)                        //background; 
{
    const int hwpatch = ball.patchwidth >> 1;         
    const BYTE *patch = &ball.data[0] ;         //pre-calculated patch z-value;
    int zcenter = 0;                            //start z-center in the xy-plane
    for (int y = 0; y < height; y++) {
        int top = y - hwpatch;
        int bot = y + hwpatch;
        for (int x = 0; x < width; x++) {
            // 현패치 내에서(중심(x-hwpatch, y-hwpatch)) 픽셀의 z값(그레이 레벨)과 
            // zcenter만큼 shift한 공의 윗표면에 놓인 패치의 z와 차이를 구함. 차이가
            // 가장 작을 때 값만큼 공의 중심을 높이거나 내리면 공과 픽셀 surface가 밑에서 
            // 접하게 된다. 
            int zmin   = 255; 
            int left  = x - hwpatch;
            int right = x + hwpatch;
            for (int iy = top, ball_pos = 0; iy <= bot; iy++) 
                for (int ix = left; ix <= right; ix++, ball_pos++) 
                    if (ix >= 0 && ix < width && iy >= 0 && iy < height) {
                        int zdif = image[iy][ix] - (zcenter + (patch[ball_pos]));
                        if (zdif < zmin) zmin = zdif;
                    }

            if (zmin != 0) zcenter += zmin; 
            for (int iy = top, ball_pos = 0; iy <= bot; iy++) 
                for (int ix = left; ix <= right; ix++, ball_pos++)
                    if (ix >= 0 && ix < width && iy >= 0 && iy < height) {
                       int zadd = zcenter + patch[ball_pos];  
                       if (zadd > background[iy][ix])           
                           background[iy][ix] = (BYTE)zadd;
                    } 
        } 
    }
}