线性插值的复杂度是多少？比如将N点插值到2N点，复杂度如何衡量？

插值（Interpolation）

插值（Interpolation/resampling）是一种图像处理方法，它可以为数码图像增加或减少象素的数目。某些数码相机运用插值的方法创造出象素比传感器实际能产生象素多的图像，或创造数码变焦产生的图像。实际上，几乎所有的图像处理软件支持一种或以上插值方法。图像放大后锯齿现象的强弱直接反映了图像处理器插值运算的成熟程度。

下面的例子是一幅106*40的图像放大成450%的效果：

最接近原则插值（Nearest Neighbor Interpolation）

最接近原则插值是最简单的插值方法，它的本质就是放大象素。新图像的象素颜色是原图像中与创造的象素位置最接近象素的颜色。如果把原图像放大200%，1个象素就会被放大成（2*2）4个与原象素颜色相同的象素。多数的图像浏览和编辑软件都会使用这种插值方法放大数码图像，因为这不会改变原图像的颜色信息，并且不会产生防锯齿效果。同理，在实际放大照片中这种方法并不合适，因为这种插值会增加图像的可见锯齿。

双线性插值（Bilinear Interpolation）

在双线性插值中，新创造的象素值，是由原图像位置在它附近的（2 x -2）4个邻近象素的值通过加权平均计算得出的。这种平均算法具有放锯齿效果，创造出来的图像拥有平滑的边缘，锯齿难以察觉。

双三次插值（Bicubic interpolation）

双三次插值是一种更加复杂的插值方式，它能创造出比双线性插值更平滑的图像边缘。请读者留意下图中的眼睫毛部分，在这个地方，软件通过双三次插值创造了一个象素，而这个象素的象素值是由它附近的（4 x 4）个邻近象素值推算出来的，因此精确度较高。双三次插值方法通常运用在一部分图像处理软件、打印机驱动程序和数码相机中，对原图像或原图像的某些区域进行放大。Adobe Photoshop CS 更为用户提供了两种不同的双三次插值方法：双三次插值平滑化和双三次插值锐化。

双三次插值

（1）双三次插值平滑化 （2）普通双三次插值 （3）双三次插值锐化