图像缩放算法——近邻取样插值

近邻取样插值原理：  
   
      缩放后图片         原来的图片

    对于缩放后图片中的某点 (Dx, Dy) 对应于原图片中的点 (Sx, Sy)，它们之间存在如下的比例关系：
    (Sx-0)/(SW-0)=(Dx-0)/(DW-0)
    (Sy-0)/(SH-0)=(Dy-0)/(DH-0)
    因此，已知缩放后图片中的任意一点 (Dx, Dy)，可以求得其对应的原图片中的点 Sx=Dx*SW/DW，Sy=Dy*SH/DH。

近邻取样插值算法及其优化：
struct image_info {
    int width;             /* 图像宽度 */
    int height;            /* 图像高度 */
    int bpp;               /* 每像素占据的位数，单位bit */
    int line_width;        /* 图像每行占据的字节数，单位byte */
    unsigned char *data;   /* 图像像素数据 */
};

void zoom0(struct image *src_image, struct image *dst_image)
{
    int x, y;
    int srcx, srcy;
    for(x=0; xwidth; x++)   
    {
        for(y=0; yheight; y++)
        {
            srcx = (x * src_image->width / dst_image->width);
            srcy = (y * src_image->height / dst_image->height);   
            Pixel(dst_image, x, y) = Pixel(src_image, srcx, srcy);
        }
    }
}
    函数 zoom0() 并没有按照颜色数据在内存中的排列顺序读写(图片的像素数据是逐行存储的)，将造成 CPU 缓存预读失败和内存颠簸导致巨大的性能损失，很多硬件都有这种特性，包括缓存、内存、显存、硬盘等，优化顺序访问，随机访问时会造成巨大的性能损失，所以先交换x,y循环的顺序：
void zoom1(struct image *src_image, struct image *dst_image)
{
    int x, y;
    int srcx, srcy;
    for(y=0; yheight; y++)
    {
        for(x=0; xwidth; x++)   
        {
            srcx = (x * src_image->width / dst_image->width);
            srcy = (y * src_image->height / dst_image->height);
            Pixel(dst_image, x, y) = Pixel(src_image, srcx, srcy);
        }
    }
}
    可以发现 srcy 的值和 x 变量无关，可以提前到 x 循环之前：
void zoom2(struct image *src_image, struct image *dst_image)
{
    int x, y;
    int srcx, srcy;
    for(y=0; yheight; y++)
    {
        srcy = (y * src_image->height / dst_image->height);
        for(x=0; xwidth; x++)   
        {
            srcx = (x * src_image->width / dst_image->width);   
            Pixel(dst_image, x, y) = Pixel(src_image, srcx, srcy);
        }
    }
}
    每一行的缩放比例是固定的，那么可以预先建立一个缩放映射表格：
void zoom3(struct image *src_image, struct image *dst_image)
{
    int x, y;
    int srcy;
    unsigned int *xtable;
    xtable = (unsigned int *)malloc(dst_image->width * 4);
    for(x=0; xwidth; x++)
        xtable[x] = (x * src_image->width / dst_image->width);   
    for(y=0; yheight; y++)
    {
        srcy = (y * src_image->height / dst_image->height);
        for(x=0; xwidth; x++)   
        {
            Pixel(dst_image, x, y) = Pixel(src_image, xtable[x], srcy);
        }
    }
}
    除法运算属于很慢的操作，比一般的加减运算慢几十倍，因此使用定点数的方法来优化它：
void zoom4(struct image *src_image, struct image *dst_image)
{
    int x, y;
    int srcy;
    int xscale, yscale;
    unsigned int *xtable;
    xtable = (unsigned int *)malloc(dst_image->width * 4);
    /* 函数能够处理的最大图片尺寸 65536*65536 */
    xscale = (src_image->width << 16) / dst_image->width;
    yscale = (src_image->height << 16) / dst_image->height
    for(x=0; xwidth; x++)
        xtable[x] = (x * xscale) >> 16;   
    for(y=0; yheight; y++)
    {
        srcy = (y * yscale) >> 16;
        for(x=0; xwidth; x++)   
        {
            Pixel(dst_image, x, y) = Pixel(src_image, xtable[x], srcy);
        }
    }
}
       ——Be loyal to dream. Be brave to try!    [e-mail]