'warping'에 해당되는 글 3건

  1. 2010.01.24 Image Morphing
  2. 2010.01.22 Fant's Algorithm
  3. 2008.12.17 Fant's Resampling

Image Morphing

Image Recognition 2010. 1. 24. 13:50
 
Beier & Neely Field Morphing Algorithm:


모핑 결과: 치타의 이미지 영역밖의 픽셀값은 0으로 처리하였다.


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

Retinex 알고리즘  (11) 2010.02.03
Gaussian Mixture Model & KMeans  (4) 2010.01.30
Image Morphing  (0) 2010.01.24
Fant's Algorithm  (0) 2010.01.22
Affine Transformation  (0) 2010.01.20
Color Counting  (0) 2010.01.18
Posted by helloktk

댓글을 달아 주세요

Fant's Algorithm

Image Recognition 2010. 1. 22. 17:38

이미지 resampling CCD에서 받은 신호를 sampling 해서 만든 이미지를 확대하거나 줄이는 경우에, 또는 기하학적인 변환을 걸쳐서 다시 이미지를 생성하는 과정이다. 이 과정에서 출력영상의 픽셀좌표 (x, y)에 대응하는 입력영상의 픽셀좌표 (u, v)를 구하는데, 일반적으로 입력영상에서 이 좌표값은 정수로 주어지지 않는다. 따라서 입력영상에서 픽셀값을 얻을 때 모호함이 생기는데 이 경우에 (u, v)에 가장 가까운 정수에 해당하는 지점의 픽셀값을 얻어와서 사용하거나(nearest neighbor interpolation), 아니면 (u, v) 주변의 픽셀값들 사용하여서 보간한 값을 사용한다(bilinear or bicubic.interpolation).

 

그러나 이러한 이차원적인 resampling 방법은 영상처리가 스캔라인 방식으로 이루어지는 것이 대부분인 현실에서 하드웨어로 직접적으로 구현하는데 문제가 있다. 따라서, resampling 과정을 스캔라인 방식에 맟주어서, 수평방향으로 처리하고, 그 결과를 다시 수직방향으로 처리하는 separable 알고리즘이 요구되었다.

 

또한, 2차원 방식에서도 마찬가지지만, 1차원 resample에서도, 특히 down sampling을 할 때, 입력픽셀 정보의 손실로 인해서 나타나는 계단 현상이나 모아레 무늬와 같은 alias를 줄이는 알고리즘이 필요한데, Fant 알고리즘은 스캔라인 방식이어서 하드웨어적으로 구현이 쉽게, 각각의 입력 픽셀들이 출력픽셀을 만드는데 얼마나 기여하는지를 고려하여서, 그 기여분 만큼 가중치를 주어서 합산하므로써 입력 픽셀의 정보의 손실을 줄어들게 하여 alias 현상을 줄일 수 있도록 된 알고리즘이다.

 

Fants 알고리즘은 일반적으로 출력영상에 해당하는 입력픽셀의 좌표가 주어지는 역변환(inverse mapping)에 대해서 사용이 된다(참고: 이곳에서는 입력영상에 대응하는 출력영상의 좌표가 주어지는 정변환(forward mapping)에 대한 Fants 알고리즘의 구현이 있다)

 참고:
// dst--->src;
// index ++ ;
// pointer += stride ;
/* stride = horizontal_scan=3; vertical_scan=bytes_per_line;*/
void fant_resample24_inverse(const BYTE src[], const int src_len, const int src_stride,
                              BYTE dest[], const int dest_len, const int dest_stride,
                              const float f[/*dest_len+1*/])  /* dest_pixel => src_pixel mapping*/
{
    float inseg, outseg ;
    //dest scanline pixel projects into [0, src_len];
    if(f[dest_len] < 0 || f[0] > src_len) return ;
    //advance to;
    for(int x = 0; f[x] < 0; x++) ;
    int xl = x > 0 ? x - 1 :  x ;
    //
    for(x = dest_len; f[x] > src_len; x--) ;
    int xr = (x == dest_len) ? dest_len - 1 : x ;
    //
    float isf = f[xl + 1] - f[xl];  //inverse_size_factor;
    if(f[x] < 0) {
        inseg = 1;
        outseg = isf + f[xl] ;
    } else {
        inseg = 1 - (f[0] - int(f[0]));
        outseg = isf ;
    }
    //src_initial_pos
    int u = f[x] < 0 ? 0 : int(f[xl]) ;
    src += u * src_stride ;
    int bval = src[0];
    int gval = src[1];
    int rval = src[2];
    src += src_stride ;
    u++ ;
    //src_next_pos ;
    int bnext = src[0];
    int gnext = src[1];
    int rnext = src[2];
    src += src_stride ;
    u++;
    //dest_inital_pos;
    dest += xl * dest_stride ;
    float bsum = 0, gsum = 0, rsum = 0;
    for(x = xl ; x <= xr; ) {
        float binten = inseg * bval + (1 - inseg) * bnext;
        float ginten = inseg * gval + (1 - inseg) * gnext;
        float rinten = inseg * rval + (1 - inseg) * rnext;
        if(inseg < outseg) {
            bsum += binten * inseg ;
            gsum += ginten * inseg ;
            rsum += rinten * inseg ;
            //
            outseg -= inseg ;
            inseg = 1;
            //copy pixel values for next use;
            bval = bnext ;
            gval = gnext ;
            rval = rnext ;
            if(u < src_len) {   //dest를 채우기에 부족한 부분은 마지막에서 계속 반복 사용;
                bnext = src[0]; //여기서 끝낼수도 있음;
                gnext = src[1];
                rnext = src[2];
            }
            src += src_stride ;
            u++ ;
        } else {
            bsum += binten * outseg ; bsum /= isf ;
            gsum += ginten * outseg ; gsum /= isf ;
            rsum += rinten * outseg ; rsum /= isf ;
            dest[0] = (BYTE)min(max(bsum, 0), 255);
            dest[1] = (BYTE)min(max(gsum, 0), 255);
            dest[2] = (BYTE)min(max(rsum, 0), 255);
            dest += dest_stride ;
            //
            bsum = gsum = rsum = 0;
            inseg -= outseg ;
            x++ ;
            if(x == dest_len) break ;
            isf = f[x + 1] - f[x] ;
            outseg = isf ;
        }
    }
}

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

Gaussian Mixture Model & KMeans  (4) 2010.01.30
Image Morphing  (0) 2010.01.24
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
Posted by helloktk

댓글을 달아 주세요


// 배열첨자(dj)와 픽셀의 실제위치(srcindex, destindex)를 따로 분리하여서
// 열방향을 따라서 작업을 하더라도 메모리 복사가 필요없이 처리가 가능하도록 하였음.
BOOL
resampleRGB(BYTE *source, BYTE* dest, int length,    // 
               int stride,                                                   //RGB=3(행방향), 한행의 총 바이트수(열방향) 
               double outpos[length+1])                            //forward map:source->dest; 
{
    double *inpos = new double[length+1];
    //si=source index;
    //dj=dest index;
    // Find inverse map; dest--> source;
    for (int si = 0, dj = 0; dj < length; dj++) {
        while (si < (length-1) && outpos[si+1] < dj) si++;       //max(si)=length-1;
        //
        if(si < length-1) {
        inpos[dj] = si + (dj - outpos[si]) / (outpos[si + 1] - outpos[si]);
        }else{
            //max(inpos[dj])=lenght-1;
            inpos[dj]=si+1 ;
        }
    }
    inpos[length] = length;

    double inseg  = 1.0;                //첫입력픽셀은 완전히 사용가능;
    double outseg = inpos[1];       //첫출력을 위해서 필요한 입력의 양은
                                                //inpos[1]-inpos[0]이나 inpos[0]=0으로 함;
    double sizefac = outseg ;
    int srcindex = 0;
    int destindex = 0;
    //첫번째 픽셀;
    int b = source[0] ;
    int g = source[1] ;
    int r = source[2] ;
    srcindex += stride ;
    //두번째 픽셀;
    int nextb = source[srcindex+0] ;
    int nextg = source[srcindex+1] ;
    int nextr = source[srcindex+2] ;
    srcindex += stride ;
    //
    double bsum = 0, gsum = 0, rsum = 0;
    for(dj = 1; dj < length; ) {
        //linear interpolation;
        double bintensity = inseg* b + (1-inseg)*nextb ;
        double gintensity = inseg* g + (1-inseg)*nextg ;
        double rintensity = inseg* r + (1-inseg)*nextr ;
        //
        if(inseg < outseg) {//output cycle;
            //accumulation of weighted contrib;
            bsum += inseg * bintensity ;
            gsum += inseg * gintensity ;
            rsum += inseg * rintensity ;
            //기존에 현재의 픽셀을 추가하므로, 출력을 위한 입력픽셀의 소요량이 줄어든다.
            outseg -= inseg ;
           
            //현재의 현재의 픽셀값을 갱신한다.
            b = nextb ;
            g = nextg ;
            r = nextr ;
            //새로 들어올 입력픽셀을 준비한다.
            inseg = 1.0 ;
            //srcindex < endindex-2;
            nextb = source[srcindex+0];
            nextg = source[srcindex+1];
            nextr = source[srcindex+2];
            srcindex += stride ;
        }else{ //input cycle;
            //accumulation of weighted contrib;
            bsum +=outseg* bintensity ;
            gsum +=outseg* gintensity ;
            rsum +=outseg* rintensity ;
            //hack;
            if(sizefac==0) sizefac = 1;
            //set dest pixel if inpos[dj]>=0; dj=1,2,3,....;
            //source가 dest 내부로 들어가는 경우임;
            if(inpos[dj-1]>=0){
                //x=0,1,2...
                // 출력픽셀을 만드는데 sizefac만큼의 입력픽셀이 들어갔으므로 나누어 주어야 한다.
                dest[destindex+0] = (BYTE)min(bsum/sizefac, 0xFF);
                dest[destindex+1] = (BYTE)min(gsum/sizefac, 0xFF);
                dest[destindex+2] = (BYTE)min(rsum/sizefac, 0xFF);
            }
            destindex += stride ;

            // reset accumulator for next output;
            bsum = gsum = rsum = 0;
            // source has been consumed outseg fraction;
            // 현재의 입력픽셀이 다음 출력픽셀에 기여할 수 있는 남아 있는 양;
            inseg -= outseg ;
            // set new outseg; = 다음 출력픽셀을 완성하는데 필요한 입력픽셀의 양;
            outseg = inpos[dj+1] - inpos[dj] ;
            // 출력픽셀을 완성하는데 필요한 입력픽셀의 양(outseg는 다음 출력시까지 계속 변하므로
            // 처음 세팅할 때 기억해 두어야 한다;
            sizefac = outseg ;
            dj++ ;
        }
    }

    delete[] inpos ;
    return TRUE;
}

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

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
Adaptive Binarization  (1) 2008.07.14
Histogram Equalization  (0) 2008.06.22
Posted by helloktk

댓글을 달아 주세요