Fant's Algorithm

이미지 resampling은 이미 샘플링된 디지털 영상을 확대하거나 축소하는 과정, 또는 기하학적 변환을 적용한 후 새로운 영상을 생성하는 과정에서 사용되는 기본적인 영상 처리 기술이다. 이 과정에서는 출력 영상의 각 픽셀 좌표 \((x,y)\)에 대응하는 입력 영상의 좌표 \((u,v)\)를 계산해야 한다. 일반적으로 \((u,v)\)는 정수 좌표가 아니므로, 입력 영상의 픽셀 값을 추정하는 interpolation 과정이 필요하다. 가장 가까운 픽셀 값을 사용하는 nearest neighbor interpolation이 가장 간단한 방법이며, 보다 좋은 화질을 위해 bilinear interpolation, bicubic interpolation 등의 보간법이 널리 사용된다.

실제 영상 데이터는 대부분 scanline 방식으로 저장되고 처리된다. 따라서 resampling 알고리즘 역시 먼저 수평 방향으로 1차원 처리를 수행한 뒤, 그 결과에 대해 다시 수직 방향으로 처리하는 separable 방식으로 구현하는 것이 일반적이다. Fant 알고리즘도 이러한 스캔라인 구조를 기반으로 설계되어 계산량이 적고, 순차적인 메모리 접근이 가능하므로 소프트웨어와 하드웨어 모두에서 효율적으로 구현할 수 있다.

Resampling 과정에서 특히 영상을 down sampling 하는 경우에는 입력 영상의 고주파 성분이 충분히 제거되지 않으면 계단 현상(staircase artifact)이나 모아레(moiré) 무늬와 같은 aliasing이 발생할 수 있다. Fant 알고리즘은 출력 픽셀을 계산할 때 각 입력 픽셀이 출력 픽셀에 기여하는 정도를 고려하여 가중 평균을 계산한다. 1차원에서는 입력 픽셀과 출력 픽셀이 겹치는 길이에 비례하여 밝기값을 누적하며, 2차원 영상에서는 이를 수평과 수직 방향으로 각각 적용하는 separable 방식으로 수행한다. 이러한 방법은 면적 기반(area-based) resampling을 효율적으로 구현하므로, 특히 축소 영상에서 aliasing을 효과적으로 줄일 수 있다.

Fant 알고리즘의 또 다른 장점은 이전 출력 픽셀에서 계산한 누적 결과를 재사용하면서 입력 픽셀과 출력 픽셀 사이의 중첩 비율만 갱신하면 되므로, 매 출력 픽셀마다 새로운 면적 적분을 수행할 필요가 없다는 점이다. 이러한 누적(accumulation) 방식을 이용하여 계산량을 크게 줄이면서도 고품질의 resampling 결과를 얻을 수 있다.

Fant 알고리즘은 일반적으로 출력 영상의 각 픽셀에 대응하는 입력 영상의 좌표를 계산하는 역변환(inverse mapping) 방식의 resampling에 사용된다. 역변환은 출력 영상의 모든 픽셀을 빠짐없이 계산할 수 있으므로 영상에 빈 공간(hole)이 생기지 않는 장점이 있다. (참고로 이곳에서 소개하는 구현은 입력 영상의 각 픽셀이 대응하는 출력 좌표를 계산하는 정변환(forward mapping) 방식으로 구현한 예이다.)

참고:

// 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 map*/ 
{
    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 ;
        }
    }
}

kipl.tistory.com/41

Fant's Resampling