이미지처리에서 픽셀좌표는 간격이 1인 2차원의 그리드 교차점들로 볼 수 있다. 이미지를 확대하거나 축소할 때, 픽셀과 픽셀사이의 값이 필요한 경우가 발생한다. 이러한 경우에 보통은 주변의 가장 가까은 픽셀의 값을 가져다 쓰거나, 아니면 주변의 픽셀값을 선형보간하여서 쓴다. 2차원 그리드에서 선형보간은 bilinear interpolation이다. 이러한 보간법들은 속도면에서 빠르지만, 픽셀값의 분포가 부드럽게 이어지지 않는 단점이 있다. 픽셀값의 분포가 부드럽게 이어지기 위해서는 1차 미분이 적어도 연속인 보간법을 사용해야하는데, 이러한 조건을 만족시키는 가장 낮은 찾수의 다항식 보간법이 bicubic interpolation이다.

네점 (0,0), (0,1), (1,0),(1,1)을 꼭지점으로하는 정사각형내의 임의의 지점(x, y) 0<=x<=1, 0<= y <=1에서의 픽셀값을 주변의 16개 지점 (i,j) -1<= i <=2, -1 <= j <= 2에서의 픽셀값을 이용해서 구하도록하자. 픽셀값 f(x,y)은 x와 y의 3차 함수로 주어지진다

이제, 문제는 3차 다항식의 계수 aij = a(i,j) 16 개를 구하는 것이다.  따라서 16개의 조건이 필요한데 이것을 주변의 16개의 픽셀값을 이용해서 만들 수 있다.

1. f(x, y) : 4 꼭지점에서 원래의 값:
    f(0,0) = a00;
    f(1,0) = a00 + a10 + a20 + a30;
    f(0,1) = a00 + a01 + a02 + a03;
    f(1,1) = a00 + a01 + a02 + a03 + a10 + a11 + a12 + a13 + a20 + a21 + a22 + a23 + a30 + a31 + a32 + a33;
2. 4 꼭지점에서 x/y-미분값:
    fx(0,0) = a10;
    fx(1,0) = a10 + 2*a20 + 3*a30;
    fx(0,1) = a10 + a11 + a12 + a13;
    fx(1,1) = a10 + 2*a20 + 3*a30 + a11 + 2*a21 + 3*a31 + a12 + 2*a22 + 3*a32 + a13 + 2*a23 + 3*a33;
    fy(0,0) = a01;
    fy(1,0) = a01 + a11 + a21 + a31;
    fy(0,1) = a01 + 2*a02 + 3*a03;
    fy(1,1) = a01 + a11 + a21 + a31 + 2*a02 + 2*a12 + 2*a22 + 2*a32 + 3*a03 + 3*a13 + 3*a23 + 3*a33;
3. 4 꼭지점에서 교차미분값:
    fxy(0, 0) = a11;
    fxy(1, 0) = a11 + 2*a21 + 3*a31;
    fxy(0, 1) = a11 + 2*a12 + 3*a13;
    fxy(1, 1) = a11 + 2*a21 + 3*a31 + +2*a12 + 4*a22 + 6*a32 + 3*a13 + 6*a23 + 9*a33;

(x,y) = (0,0), (1,0), (0,1), (1,1) 지점에서 f-값이나 f-미분값은 계수 a(i,j)로 표현이 되고, 또 이것은 꼭지점에서 픽셀값 및 인접픽셀값과의 차이로 표현(미분의 경우)되므로 16개의 다항식의 계수를 16차원 벡터 v로
    v=[a00, a10, a20, a30, a01, a11, a21, a31, a02, a12, a22, a32, a03, a13, a23, a33];
각각의 꼭지점에서의 픽셀값, 미분값을 f 벡터로 나타내면
    f =[f00, f10, f01, f11, fx00, fx10, fx01, fx11, fy00, fy10, fy01, fy11, fxy00, fxy10, fxy01, fxy11];
방정식으로 해는 
    v = A.f 
로 쓰여진다. 이때 16x16 행렬 A는 
   A= {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
        {-3,0,0,3,0,0,0,0,-2,0,0,-1,0,0,0,0},
        {2,0,0,-2,0,0,0,0,1,0,0,1,0,0,0,0},
        {0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
        {0,0,0,0,-3,0,0,3,0,0,0,0,-2,0,0,-1},
        {0,0,0,0,2,0,0,-2,0,0,0,0,1,0,0,1},
        {-3,3,0,0,-2,-1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,-3,3,0,0,-2,-1,0,0},
        {9,-9,9,-9,6,3,-3,-6,6,-6,-3,3,4,2,1,2},
        {-6,6,-6,6,-4,-2,2,4,-3,3,3,-3,-2,-1,-1,-2},
        {2,-2,0,0,1,1,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,2,-2,0,0,1,1,0,0},
        {-6,6,-6,6,-3,-3,3,3,-4,4,2,-2,-2,-2,-1,-1},
        {4,-4,4,-4,2,2,-2,-2,2,-2,-2,2,1,1,1,1}
이 결과는 mathematica나 maple등의 프로그램을 이용하면 쉽게 답을 구할 수 있고, 출력을 C-형태로 얻을 수 있다. 픽셀에서의 미분값은 인접픽셀값의 평균변화율로 정의할 수 있는데, 예를 들면
fx00 = fx(0,0) = ( p(1,0) - p(-1,0))/2,.......
fxy00 = fxy(0,0) = (p(1,0) - p(1,-1) - p(-1, 1) + p(-1,-1)) / 4....
와 같다.

/* 픽셀의 위치가 grid의 교차점이 되도록 표현하였다*/


/* [ix, ix+1][iy+iy+1] 영역에서 보간을 하는 경우에, 주변픽셀의 정보는
p[a][b]에 들어가고, p[a][b]= Image (ix - 1 + a, iy - 1 + b)*/
double BicubicInterpolate(double p[4][4], double x, double y) { /* 0 <= x <= 1, 0 <= y <= 1 */
    double a00 = p[1][1];
    double a01 = (-p[1][0] + p[1][2])/2.;
    double a02 = p[1][0] - (5*p[1][1])/2. + 2*p[1][2] - p[1][3]/2.;
    double a03 = (-p[1][0] + 3*p[1][1] - 3*p[1][2] + p[1][3])/2.;
    double a10 = (-p[0][1] + p[2][1])/2.;
    double a11 = (p[0][0] - p[0][2] - p[2][0] + p[2][2])/4.;
    double a12 = (-2*p[0][0] + 5*p[0][1] - 4*p[0][2] + p[0][3] + 
                         2*p[2][0] - 5*p[2][1] + 4*p[2][2] - p[2][3])/4.;
    double a13 = (p[0][0] - 3*p[0][1] + 3*p[0][2] - p[0][3] -
                        p[2][0] + 3*p[2][1] - 3*p[2][2] + p[2][3])/4.;
    double a20 = p[0][1] - (5*p[1][1])/2. + 2*p[2][1] - p[3][1]/2.;
    double a21 = (-2*p[0][0] + 2*p[0][2] + 5*p[1][0] - 5*p[1][2] -
                         4*p[2][0] + 4*p[2][2] + p[3][0] - p[3][1])/4.;
    double a22 = (4*p[0][0] - 10*p[0][1] + 8*p[0][2] - 2*p[0][3] - 10*p[1][0] + 
                      25*p[1][1] - 20*p[1][2] + 5*p[1][3] + 8*p[2][0] -
                      20*p[2][1] + 16*p[2][2] - 4*p[2][3] - 2*p[3][0] + 7*p[3][1] - 6*p[3][2] + p[3][3])/4.;
    double a23 = (-2*p[0][0] + 6*p[0][1] - 6*p[0][2] + 2*p[0][3] + 5*p[1][0] - 15*p[1][1] +
                        15*p[1][2] - 5*p[1][3] - 4*p[2][0] + 12*p[2][1] - 12*p[2][2] +
                          4*p[2][3] + p[3][0] - 4*p[3][1] + 4*p[3][2] - p[3][3])/4.;
    double a30 = (-p[0][1] + 3*p[1][1] - 3*p[2][1] + p[3][1])/2.;
    double a31 = (p[0][0] - p[0][2] - 3*p[1][0] + 3*p[1][2] + 
                     3*p[2][0] - 3*p[2][2] - p[3][0] + p[3][1])/ 4.;
    double a32 = (-2*p[0][0] + 5*p[0][1] - 4*p[0][2] + p[0][3] + 6*p[1][0] - 15*p[1][1] + 
                        12*p[1][2] - 3*p[1][3] - 6*p[2][0] + 15*p[2][1] -
                        12*p[2][2] + 3*p[2][3] + 2*p[3][0] -  7*p[3][1] + 6*p[3][2] - p[3][3])/4.;
    double a33 = (p[0][0] - 3*p[0][1] + 3*p[0][2] - p[0][3] - 3*p[1][0] + 9*p[1][1] - 9*p[1][2] +
                     3*p[1][3] + 3*p[2][0] - 9*p[2][1] + 9*p[2][2] - 3*p[2][3] -
                        p[3][0] + 4*p[3][1] - 4*p[3][2] + p[3][3])/4 ;
        
    double x2 = x * x;
    double x3 = x2 * x;
    double y2 = y * y;
    double y3 = y2 * y;
    //
    return a00 + a01 * y + a02 * y2 + a03 * y3 +
        a10 * x + a11 * x * y + a12 * x * y2 + a13 * x * y3 +
        a20 * x2 + a21 * x2 * y + a22 * x2 * y2 + a23 * x2 * y3 +
        a30 * x3 + a31 * x3 * y + a32 * x3 * y2 + a33 * x3 * y3;
}
*원본 16x16 이미지:

bicubic interpolation 결과 (256x256): (경계지점에서 P를 구성하는데 필요한 값은 경계값을 반복해서 적용하였다. 히스토그램 스트레치한 후의 결과이다. 필셀 간격을 확대한 것이 아니라 픽셀 수를 확대한 것이므로 확대비율이 큰 경우에 오른쪽과 하단은 2 픽셀을 두 중복해서 사용한 결과가 나온다. 폭/높이가 큰 이미지에서는 문제가 안되는 작은 이미지에서는 문제가 된다. 이것을 방지하려면, 픽셀의 값을 그리드의 중앙에서의 값으로 생각하고 보간을 하면 된다) 


*simple stretch 결과 (256x256) :




코드 구현 일부:

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

Otsu-알고리즘의 새로운 해석  (0) 2010.01.28
Object Orientation  (1) 2010.01.17
Bicubic Interpolation  (1) 2010.01.14
Histogram Smoothing via Bezier Curve  (1) 2010.01.10
Running Median Filter  (0) 2010.01.07
Fast Median Filter 3x3  (0) 2009.11.27
Posted by helloktk

댓글을 달아 주세요

  1. 2010.12.02 00:49  댓글주소  수정/삭제  댓글쓰기

    비밀댓글입니다