4.7 插值算法

实现几何运算时，有两种方法。第一种称为向前映射法，其原理是将输入图像的灰度一个像素一个像素地转移到输出图像中，即从原图像坐标计算出目标图像坐标：g(x1,y1)=f ( a(x0,y0), b(x0, y0) )。前面的平移、镜像等操作就可以采用这种方法。

另外一种称为向后映射法，它是向前映射变换的逆，即输出像素一个一个地映射回输入图像中。如果一个输出像素映射到的不是输入图像的采样栅格的整数坐标处的像素点，则其灰度值就需要基于整数坐标的灰度值进行推断，这就是插值。由于向后映射法是逐个像素产生输出图像，不会产生计算浪费问题，所以在缩放、旋转等操作中多采用这种方法，本书中采用的也全部为向后映射法。

本节中将介绍3种不同的插值算法，处理效果好的算法一般需要较大的计算量。

4.7.1 最近邻插值

这是一种最简单的插值算法，输出像素的值为输入图像中与其最邻近的采样点的像素值。例如，图4.13中的点P0在几何变换中被映射至点P1'，但由于点P1’处于非整数的坐标位置，无法提取其像素灰度值。所以可以用与P1’最邻近的采样点P1的灰度值近似作为P1’的灰度值。

最近邻插值可表示如下。

本书在之前各种变换的Visual C++实现中采用的均为最近邻插值，它计算简单，而且在很多数情况下的输出效果也可以接受。然而，最近邻插值法会在图像中产生人为加工的痕迹，详见例4.1。

4.7.2 双线性插值

1．理论基础

双线性插值又称为一阶插值，是线性插值扩展到二维的一种应用。它可以通过一系列的一阶线性插值得到。

输出像素的值为输入图像中距离它最近的2×2邻域内采样点像素灰度值的加权平均。

设已知单位正方形的顶点坐标分别为f(0,0)、f(1,0)、f(0,1)、f(1,1)，如图4.14所示，本节要通过双线性插值得到正方形内任意点f(x, y)的值。

首先对上端的两个点进行线性插值得到：

再对下端的两个顶点进行线性插值得到：

最后，对垂直方向进行线性插值得到：

综合式（4-26）至式（4-28），整理得出：

上面的推导是在单位正方形的前提下进行的，稍加变换就可以推广到一般情况中。

线性插值的假设是原图的灰度在两个像素之间是线性变化的，显然这是一种比较合理的假设。因此在一般情况下，双线性插值都能取得不错的效果。更精确的方法是采用曲线插值，即认为像素之间的灰度变化规律符合某种曲线方程，当然这种处理的计算量是很大的。

2．Visual C++实现

利用Visual C++实现双线性插值的代码如下。

      /*******************
      int CImgProcess::InterpBilinear(double x, double y)
      功能：      双线性插值

      参数：      double x：需要计算插值的横坐标
                  double y：需要计算插值的纵坐标
      返回值：    int插值的结果
      *******************/
      int CImgProcess::InterpBilinear(double x, double y)
      {
            if(int(y)==300)
                  int cc = 1;

            // 4个最临近像素的坐标 (i1, j1), (i2, j1), (i1, j2), (i2, j2)
            int x1, x2;
            int y1, y2;

            // 4个最临近像素值
            unsigned char  f1, f2, f3, f4;

            // 两个插值中间值
            unsigned char  f12, f34;

            double    epsilon = 0.0001;

            // 计算4个最临近像素的坐标
            x1 = (int) x;
            x2 = x1 + 1;
            y1 = (int) y;
            y2 = y1 + 1;

            int nHeight = GetHeight();
            int nWidth = GetWidthPixel();
            if( (x < 0) || (x > nWidth -1) || (y < 0) || (y > nHeight -1))
            {
                  // 如果计算的点不在原图范围内，返回-1
                  return -1;
            }
            else
            {
                  if (fabs(x - nWidth + 1) <= epsilon)
                  {
                      // 如果计算的点在图像右边缘上
                      if (fabs(y - nHeight + 1) <= epsilon)
                      {
                          // 如果计算的点正好是图像最右下角那一个像素，直接返回该点像素值
                          f1 = (unsigned char)GetGray( x1, y1 );
                          return f1;
                      }
                      else
                      {
                          // 如果是在图像右边缘上且不是最后一点，直接一次插值即可
                          f1 = (unsigned char)GetGray(x1, y1 );
                          f3 = (unsigned char)GetGray( x1, y2 );

                          // 返回插值结果
                          return ((int) (f1 + (y -y1) * (f3- f1)));
                      }
                }
                else if (fabs(y - nHeight + 1) <= epsilon)
                {
                      // 如果计算的点在图像下边缘上且不是最后一点，直接一次插值即可
                      f1 = (unsigned char)GetGray( x1, y1 );
                      f2 = (unsigned char)GetGray( x2, y1 );

                      // 返回插值结果
                      return ((int) (f1 + (x -x1) * (f2- f1)));
                }
                else
                {
                      // 计算4个最临近像素值
                      f1 = (unsigned char)GetGray( x1, y1 );
                      f2 = (unsigned char)GetGray( x2, y1 );
                      f3 = (unsigned char)GetGray( x1, y2 );
                      f4 = (unsigned char)GetGray( x2, y2 );

                      // 插值1
                      f12 = (unsigned char) (f1 + (x - x1) * (f2- f1));

                      // 插值2
                      f34 = (unsigned char) (f3 + (x - x1) * (f4- f3));

                      // 插值3
                      return ((int) (f12 + (y -y1) * (f34- f12)));
                }
            }
      }

4.7.3 高阶插值

在几何运算的一些情况中，双线性插值的平滑作用会使图像的细节退化，而其斜率的不连续性则会导致变换产生不希望的结果。这些都可以通过高阶插值得到弥补，高阶插值常用卷积来实现。输出像素的值为输入图像中距离它最近的4×4领域内采样点像素值的加权平均值。

下面以三次插值为例，它使用了如下的三次多项式来逼近理论上的最佳插值函数sin(x)/x，如图4.15所示。

上式中|x|是周围像素沿x方向与原点的距离。待求像素(x, y)的灰度值由其周围16个点的灰度值加权插值得到。计算公式如下：

三次插值方法通常应用在光栅显示中，它在允许任意比例的缩放操作的同时，较好地保持了图像细节。

【例4.1】插值方法的比较。

图4.16和图4.17分别给出了采用最近邻、双线性和三次插值时对于两幅不同图像的旋转效果。从图4.17可以看出最近邻的插值方法得到的结果还是可以接受的，但当图像中包含的像素之间灰度级有明显变化时（见图4.16），从结果图像的锯齿形边可以看出三种插值方法的效果依次递减，最近邻插值的效果明显不如另外两个好，锯齿比较多，而三次插值得出的图像较好地保持了图像的细节。这是因为参与计算输出点的像素值的拟合点个数不同，个数越多效果越精确，当然参与计算的像素个数会影响计算的复杂度。实验结果也清楚地表明：三次插值法花费的时间比另外两种的要长一些。最近邻和线性插值的速度在此次图像处理中几乎分不出来。所以，在计算时间与质量之间有一个折中问题。

利用MATLAB实现上述3种插值方法用代码如下。

      A=imread('test.bmp');
      B = imrotate(A,30, 'nearest');
      C = imrotate(A,30, 'bilinear');
      D = imrotate(A,30, 'bicubic');
      %图像旋转30°的插值方法比较
      subplot(2,2,1), imshow(A);
      title(’原图像’);
      subplot(1,3,1), imshow(B);
      title(’最近邻插值’);
      subplot(1,3,2), imshow(C);
      title(’双线性插值’);
      subplot(1,3,3), imshow(D);
      title(’三次插值’);