Rolling Ball Transformation

이미지를 획득할 때 조명 조건이 균일하지 않으면 이미지 처리 과정에서 복잡성이 증가하게 된다. 이런 경우에 배경의 불균일성을 제거하는 전처리 과정을 수행할 필요가 생기게 된다. 일반적으로 조명의 불균일성은 공간적으로 넓은 범위에서 천천히 일어나게 되는데, 이를 이용하면 이미지에서 배경을 좀 더 수월하게 제거할 수 있다. 보통 큰 윈도를 (전경의 물체의 크기에 비해서) 가지는 median filter를 연속적으로 적용하여 배경을 추출할 수 있지만, median filter는 일반적으로 계산 비용이 상당히 비싸다.

좀 더 저렴한 연산비용이 드는 방법으로는 이미지가 각 픽셀 좌표에서 하나의 값을 할당하므로 3차원 공간에서 곡면으로 생각할 수 있다는 점을 이용하면 된다. 일정하게 변하는 조명에 의한 배경은 3차원에서 평면을 형성하는 것으로 근사할 수 있다. 주어진 이미지 곡면에서 배경 평면을 추출하는 쉬운 방법은 최소자승법을 사용하여 이미지 곡면을 가장 잘 근사하는 평면을 찾는 것이다. 그러나 이 방법은 전경의 물체가 fitting에 있어 일종의 outlier 역할을 하게 된다. 전경에 해당하는 물체가 많은 이미지에서도 잘 동작하려면 보다 robust 한 fitting 알고리즘을 고안해야 한다.

3차원 공간에서 이미지 곡면을 고려할 때, 전경(밝은 색)이 이미지 영역에서 차지하는 비중이 작은 경우에는 그림처럼(A) 충분히 큰 공을 곡면 아래쪽에서 접하게 굴리면 공의 표면이 형성하는 곡면은 이미지의 작은 요철(전경 물체)에 영향을 거의 받지 않는다. 따라서 구르는 공에 의해 형성된 접곡면은 이미지의 배경으로 생각할 수 있다 (B는 전경이 어두운 경우).

이미지 곡면이 요철이 심하더라도 반지름이 충분히 큰 공을 사용하게 되면 부드러운 배경 표면을 얻을 수 있다. 공 표면과 이미지 표면과의 접촉 관계는 공의 표면에 놓인 patch의 좌표점에서 (미리 계산) 높이를 이미지의 픽셀 값과 비교하여 얻는다. 공의 반경이 큰 경우에는 연산을 줄이기 위해서 원본 이미지를 축소해서 작업을 하고, 다시 간단한 보간을 써서 원본 크기로 복원하면 충분하다.

다음 예는 밝은 배경에 어두운 전경인 이미지에 대해서 이 알고리즘을 적용한 경우다. 먼저, 원본 이미지의 negative 이미지를  만들어서 (어두운 배경에 밝은 전경) rolling ball transformation을 적용해서 배경을 얻었다.

 

 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;
                    } 
        } 
    }
}