'Background Subtraction'에 해당되는 글 2건

  1. 2012.02.28 2차원 Savitzky-Golay Filters 응용
  2. 2008.08.09 Rolling Ball Transformation (1)
Savitzky-Golay 필터는 일차원의 데이터에 대해서 일종의 이동평균을 취하는 경우와 동일하게 동작하는 필터이지만, 추정하는 지점의 주변의 모든 점에 동일한 가중치를 주는 방식(이동평균)을 택하지 않고, 그들을 보간하는 다항식을 최소자승법으로 찾아서 해당 지점의 값을 추정하는 방식을 택한다(frequency domain에서 분석을 하면 Savitzky-Golay 필터의 특성, 예를 들면, 피크의 위치나 등이 잘 유지되는 점등, 좀 더 다양하게 볼 수 있다). 이 필터를 쓰기 위해서는 몇 차의 다항식과 얼마의 윈도우 크기를 사용해야 하는지 설정을 해야 한다. (다항식의 찻수가 정해지면 최소의 윈도우 크기가 정해진다).
동일한 방식으로 이차원에 대해서도 Savitzky-Golay를 적용할 수 있다. 이 경우에는 다항식이 (x,y)의 2변수 함수 (2차원 평면에서의 정의되는 곡면)로 주어질 것이다. 이차원의 경우도 국소적인 필터로 사용하여서 영상의 smoothing 필터로 사용할 수 있지만, 필터의 윈도우를 영상전체로 잡아서, 즉 영상을 구성하는 픽셀값을 전 영역에서 보간하는 곡면을 찾을 수도 있다. 이렇게 찾은 곡면은 만들어진 영상의 배경조명이 균일하지 않는 경우에 이 추정된 곡면을 이용하면, 조명에 의한 효과를 예측할 수 있고, 배경조명이 보정된 영상을 만들어서 영상의 인식에 도움을 받을 수 있다. (문서인식에서 문서를 스캔할 때 생기는 균일하지 않은 배경이나, 2차원 코드 인식에서 배경의 추정등 다양한 부분에서 사용할 수 있다. 물론 간단한 경우에는 배경의 변화를 균일하게 기울어진 평면으로 근사를 하여서 추정할 수 있다)  

간단한 경우가 3차 다항식으로 영상을 보간하는 경우:

I(x, y) = a00
         + a
10*x + a01*y
         + a
20*x2 + a11*x*y + a02*y2
         + a
30*x3 + a21*x2*y + a12*x*y2 + a03*y3 
                                                      (x, y) ∈ image 


다항식은 x = [a00, a10,..., a03]T 의 10개의 필터계수를 추정하면 얻어진다. 추가적으로 Savitzky-Golay을 이용하면 영상의 미분값을 쉽게 구할 수 있다. 로컬버전의 필터인 경우에 필터적용값은 윈도우의 중심인 (x, y) = (0, 0)에서 다항식 값인 a00이다. 이 지점에서 x-방향의 편미분값은 a10, y방향의 편미분 값은 a01, 식으로 미분값을 구할 수 있다.

필터의 계수 x는 최소자승법 적용하면 얻어질 수 있다.  위의 다항식에  N (= width * height) 개의 픽셀로 구성된 영상의 각각의 픽셀에서의 좌표와 픽셀값을 대입하면,  N개의 식을 얻는다. 이것을 행렬식으로 쓰면

A.x = b

A는 N x 10 의 행렬로 각 행은 픽셀의 좌표로 구해진다:

A = [1, x0,  y0,  x02,  x0*y0,  y02,  x03,  x02*y0,  x0*y02,  y03]
     [1, x1,  y1,  x12,  x1*y1,  y12,  x13,  x12*y1,  x1*y12,  y13] 
     [1, x2,  y2,  x22,  x2*y2,  y22,  x23,  x22*y2,  x2*y22,  y23] 
     [1, .....................................................................] 
     [1, .....................................................................] 
                       ......................................
     [1, .....................................................................] 

여기서, 영상을 읽을 때, i-번째의 픽셀 위치가 (xi, yi) 로 주어진 경우다.

b 는 N-(열)벡터로 각각의 픽셀 위치에서 픽셀 값을 나타내는 벡터이다:

b = [ I(x0, y0) ]
     [ I(x1, y1) ] 
     [ I(x2, y2) ] 
     [ ............] 
     [ ............]
      ..............
     [.............]  


최소자승법을 적용하면, 추정된 다항식의 계수벡터 x는 

x = (A
T .A)-1.AT.b

임을 알 수 있다.

이렇게 추정된 2차원 곡면은 영상에서 추정된 배경의 픽셀 값 분포를 의미한다. 문자인식의 예를 들면, 보통의 경우에 흰 배경에 검정색 활자를 인식한다. 스캔된 영상에 검정색 활자들 때문에 추정된 곡명은 일반적으로 주어진 픽셀이 만드는 곡면보다도 낮게 된다. 픽셀 값이 추정된 곡면보다 더 낮은 픽셀들은 보통 검정색 문자들을 의미하므로, 이 차이의 평균값을 구하면, 대략적으로 어떤 픽셀이 배경에 속하는지 (곡면과 차이가 평균보다 작고, 또한 픽셀 값이  곡면의 아래에 놓인 경우), 아니면 문자영역인지(곡면과 차이가 평균보다 크고, 픽셀 값이 곡면의 아래에 놓인 경우)를 구별할 있게 된다.  
이제 이 정보들을 이용해서 추정을 다시 하는데 이번에는 1차 추정에서 글자영역으로 분류된 픽셀을 제외하고 배경을 추정하면 좀 더 정확한 배경을 기술하는 곡면을 얻을 수 있다.

로컬버전 필터로 사용할 때는 1차원에서와 마찬가지로 필터계수를 lookup table로 만들어서 사용할 수 있으나, 전영역을 대상으로 할 때는 행렬의 크기가 매우 커져서 연산도 많아진다. 

""

""

""


Posted by helloktk

댓글을 달아 주세요

이미지를 형성할 때 조명의 조건이 균일하지 않으면 이미지 처리과정에서 복잡성이 증가하게 된다. 따라서 이미지 의 전처리 과정으로 배경의 불균일성을 제거하여야 할 필요가 생기는 경우가 많다. 일반적으로 배경의 불균일성은 공간적으로 넓은 범위에서 천천이 일어나기 때문에, 이러한 사실을 이용하면 이미지상에서 배경에 의한 효과를 제거할 수 있다. 어떤 경우에는 큰(전경의 물체의 크기에 비해서) 윈도우를 가지는 메디안 필터를 연속적으로 적용하여서 배경을 얻을 수 있다. 그러나 이 과정은 계산비용이 상당하다. 다른 방법으로는 이미지의 픽셀값을 z-값으로 하면 (x,y,z=픽셀값)을 지나는 평면의 방정식을 최소자승법으로 구하여서 배경으로 이용할 수 있다. 이 경우에는 전경의 물체가 최소자승피팅에 있어서 outlier역할을 하여서 좀더 robust한 피팅방법을 이용하여야 한다.
또 다른 방법으로는 이미지가 3차원 공간에서 surface(x,y,z=픽셀값)을 형성하므로, 만약에 전경(밝은색)이 전체 이미지중에서 차지하는 비중이 작은 경우에는 아래의 그림처럼(A)충분히 큰 공을 표면에 접하도록 굴리면, 구르는 공의 표면이 그리는  surface를 배경으로 생각할 수 있다(B는 전경이 어두운 경우).

사용자 삽입 이미지

사용자 삽입 이미지


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


아래의 밝은 배경에 어두운 전경인 경우에 대해서 이것을 적용한 예인데 먼저, negative 이미지를  만들어서(어두운 배경에 밝은 전경) rolling ball transformation을 적용하여 배경을 얻은 것이다.


사용자 삽입 이미지


 negative image:

사용자 삽입 이미지

radius=16;

사용자 삽입 이미지

radius=5:

사용자 삽입 이미지

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

사용자 삽입 이미지


// processing을 빠르게 하기 위해서, ball의 반경이 큰 경우에는 원본이미지를
// 축소하여서(2,4,8,..) 처리한 후에, 처리 안된 점들은 interpolation을 하여서
// bacground image을 생성한다.
void RollBall(RollingBall& ball,                        //rolling ball object;
              BYTE *smallImage, int swidth, int sheight,//shrinked source image;
              BYTE *background) //shrinked background image
{
    int wsz   =  ball.patchwidth ;   //patch width(odd);
    int hwsz = wsz>>1;        
    BYTE *patch = &ball.data[0] ;           //pre-calculated patch z-value;
    int zctr = 0; // start z-center in the xy-plane
    for (int y=0; y<sheight; y++) {
            for (int x=0; x<swidth; x++) {
            // 현재의 패치내에서(중심(x-patchwidth/2, y-patchwidth/2)) 픽셀의 z값(그레이레벨)과
            // zctr만큼 shift한 공의 윗표면에 놓인 패치의 z-값간의 차이를 구함. 그 값의 차이가
            // 가장 작을 때의 값만큼 공의 중심을 높이거나, 내리면 공과 이미지의 픽셀 surface가 밑에서
            // 접하게 된다.
            int zmin = 255;
            int yend = y+hwsz;
            int xend = x+hwsz;
            for(int yy=y-hwsz, ballpt=0; yy<=yend; yy++){
                for(int xx=x-hwsz, imgpt=yy*swidth+xx; xx<=xend; xx++){
                    if(xx>=0 && xx<swidth && yy>=0 && yy<sheight) {
                        int zdif = smallImage[imgpt] - (zctr + (patch[ballpt]));
                        if (zdif<zmin) zmin = zdif;
                    }
                    ballpt++; imgpt++;
                }
            }
            if (zmin!=0) zctr += zmin;
            // zmin<0 인 경우는 x의 오른쪽 반만 처리하면 된다(not yet);
            for(yy=y-hwsz, ballpt=0; yy<=yend; yy++){
                for(int xx=x-hwsz, imgpt=yy*swidth+xx; xx<=xend; xx++){
                    if(xx>=0 && xx<swidth && yy>=0 && yy<sheight) {
                        int zadd = zctr + (patch[ballpt]); 
                        if (zadd>(sbackground[imgpt]))          
                            sbackground[imgpt] = (BYTE)zadd;
                    }
                    ballpt++; imgpt++;
                }
            }
        }
    }
}

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

Spline Based Snake  (0) 2008.08.15
Anisotropic Diffusion Filter  (0) 2008.08.11
Rolling Ball Transformation  (1) 2008.08.09
Mean Shift Filter  (5) 2008.08.06
Chamfer Match  (0) 2008.08.01
Retinex Algorithm  (2) 2008.07.26
Posted by helloktk

댓글을 달아 주세요

  1. helloktk 2012.01.17 19:26 신고  댓글주소  수정/삭제  댓글쓰기

    #define SQR(x) ((x)*(x))
    struct RollingBall {
    std::vector<BYTE> data;
    int patchwidth;
    int shrinkfactor;
    RollingBall(int radius) {
    int artrimper;
    if (radius<=10) {
    shrinkfactor = 1;
    artrimper = 12; // trim 24% in x and y
    } else if (radius<=30) {
    shrinkfactor = 2;
    artrimper = 12; // trim 24% in x and y
    } else if (radius<=100) {
    shrinkfactor = 4;
    artrimper = 16; // trim 32% in x and y
    } else {
    shrinkfactor = 8;
    artrimper = 20; // trim 40% in x and y
    }
    Build(radius, artrimper);
    }
    void Build(int ballradius, int artrimper) {
    int sballrad = ballradius/shrinkfactor;
    if (sballrad<1) sballrad = 1;
    int rsquare = SQR(sballrad);
    int diam = sballrad*2;
    int xtrim = (artrimper*diam)/100; // only use a patch of the rolling ball
    patchwidth = diam - xtrim - xtrim;
    int halfpatchwidth = sballrad - xtrim;
    int ballsize = SQR(patchwidth+1);
    data.resize(ballsize);

    for (int i=0; i<ballsize; i++) {
    int xval = i % (patchwidth+1) - halfpatchwidth; //relative to patch center-x.
    int yval = i / (patchwidth+1) - halfpatchwidth; //relative to patch center-y;
    int temp = rsquare - SQR(xval) - SQR(yval);
    if (temp >= 0)
    data[i] = int(sqrt(temp));
    else
    data[i] = 0;
    }
    }
    };