图片缩放旋转

高质量的快速的图像缩放 上篇 近邻取样插值和其速度优化

正文：

为了便于讨论，这里只处理32bit的ARGB颜色；

代码使用C++;涉及到汇编优化的时候假定为x86平台;使用的编译器为vc2005; 为了代码的可读性,没有加入异常处理代码;

测试使用的CPU为AMD64x2 4200+(2.37G) 和 Intel Core2 4400(2.00G);

速度测试说明:

只测试内存数据到内存数据的缩放

测试图片都是800*600缩放到1024*768; fps表示每秒钟的帧数,值越大表示函数越快

////////////////////////////////////////////////////////////////////////////////

//Windows GDI相关函数参考速度:

//==============================================================================

// BitBlt 544.7 fps //is copy 800*600 to 800*600 // BitBlt 331.6 fps //is copy 1024*1024 to 1024*1024 // StretchBlt 232.7 fps //is zoom 800*600 to 1024*1024 ////////////////////////////////////////////////////////////////////////////////

A: 首先定义图像数据结构:

#define asm __asm

typedef unsigned char TUInt8; // [0..255] struct TARGB32 //32 bit color {

TUInt8 B,G,R,A; // A is alpha };

struct TPicRegion //一块颜色数据区的描述，便于参数传递 {

TARGB32* pdata; //颜色数据首地址

long byte_width; //一行数据的物理宽度(字节宽度)；

//abs(byte_width)有可能大于等于width*sizeof(TARGB32); long width; //像素宽度 long height; //像素高度 };

//那么访问一个点的函数可以写为：

inline TARGB32& Pixels(const TPicRegion& pic,const long x,const long y)

{

return ( (TARGB32*)((TUInt8*)pic.pdata+pic.byte_width*y) )[x]; }

B: 缩放原理和公式图示:

缩放后图片 原图片

(宽DW,高DH) (宽SW,高SH)

(Sx-0)/(SW-0)=(Dx-0)/(DW-0) (Sy-0)/(SH-0)=(Dy-0)/(DH-0) => Sx=Dx*SW/DW Sy=Dy*SH/DH

C: 缩放算法的一个参考实现

//给出一个最简单的缩放函数(插值方式为近邻取样,而且我“尽力”把它写得慢一些了:D) //Src.PColorData指向源数据区,Dst.PColorData指向目的数据区

//函数将大小为Src.Width*Src.Height的图片缩放到Dst.Width*Dst.Height的区域中

void PicZoom0(const TPicRegion& Dst,const TPicRegion& Src) {

if ( (0==Dst.width)||(0==Dst.height)

||(0==Src.width)||(0==Src.height)) return; for (long x=0;x

for (long y=0;y

long srcx=(x*Src.width/Dst.width); long srcy=(y*Src.height/Dst.height); Pixels(Dst,x,y)=Pixels(Src,srcx,srcy); } } }

////////////////////////////////////////////////////////////////////////////////

//速度测试:

//==============================================================================

// PicZoom0 19.4 fps

////////////////////////////////////////////////////////////////////////////////

D: 优化PicZoom0函数

a.PicZoom0函数并没有按照颜色数据在内存中的排列顺序读写(内部循环递增y行 索引)，将造成CPU缓存预读失败和内存颠簸导致巨大的性能损失,(很多硬件都有这种特性, 包括缓存、内存、显存、硬盘等,优化顺序访问，随机访问时会造成巨大的性能损失) 所以先交换x,y循环的顺序:

void PicZoom1(const TPicRegion& Dst,const TPicRegion& Src) {

if ( (0==Dst.width)||(0==Dst.height)

||(0==Src.width)||(0==Src.height)) return; for (long y=0;y

for (long x=0;x

long srcx=(x*Src.width/Dst.width); long srcy=(y*Src.height/Dst.height); Pixels(Dst,x,y)=Pixels(Src,srcx,srcy); } } }

//////////////////////////////////////////////////////////////////////////////// //速度测试:

//==============================================================================

// PicZoom1 30.1 fps

////////////////////////////////////////////////////////////////////////////////

b.“(x*Src.Width/Dst.Width)”表达式中有一个除法运算，它属于很慢的操作(比一般 的加减运算慢几十倍!),使用定点数的方法来优化它；

void PicZoom2(const TPicRegion& Dst,const TPicRegion& Src) {

if ( (0==Dst.width)||(0==Dst.height)

||(0==Src.width)||(0==Src.height)) return; //函数能够处理的最大图片尺寸65536*65536

unsigned long xrIntFloat_16=(Src.width<<16)/Dst.width+1; //16.16格式定点数

unsigned long yrIntFloat_16=(Src.height<<16)/Dst.height+1; //16.16格式定点数

//可证明: (Dst.width-1)*xrIntFloat_16

for (unsigned long x=0;x

unsigned long srcx=(x*xrIntFloat_16)>>16; unsigned long srcy=(y*yrIntFloat_16)>>16; Pixels(Dst,x,y)=Pixels(Src,srcx,srcy); } } }

//////////////////////////////////////////////////////////////////////////////// //速度测试:

//==============================================================================

// PicZoom2 185.8 fps

////////////////////////////////////////////////////////////////////////////////

c. 在x的循环中y一直不变，那么可以提前计算与y相关的值; 1.可以发现srcy的值和x变量无关，可以提前到x轴循环之前；2.展开Pixels函数，优化与y相关的指针计算；

void PicZoom3(const TPicRegion& Dst,const TPicRegion& Src) {

if ( (0==Dst.width)||(0==Dst.height)

||(0==Src.width)||(0==Src.height)) return;

unsigned long xrIntFloat_16=(Src.width<<16)/Dst.width+1; unsigned long yrIntFloat_16=(Src.height<<16)/Dst.height+1; unsigned long dst_width=Dst.width; TARGB32* pDstLine=Dst.pdata; unsigned long srcy_16=0;

for (unsigned long y=0;y

TARGB32* pSrcLine=((TARGB32*)((TUInt8*)Src.pdata+Src.byte_width*(srcy_16>>16)));

unsigned long srcx_16=0;

for (unsigned long x=0;x

pDstLine[x]=pSrcLine[srcx_16>>16]; srcx_16+=xrIntFloat_16; }

srcy_16+=yrIntFloat_16;

((TUInt8*&)pDstLine)+=Dst.byte_width; } }

//////////////////////////////////////////////////////////////////////////////// //速度测试:

//==============================================================================

// PicZoom3 414.4 fps

////////////////////////////////////////////////////////////////////////////////

d.定点数优化使函数能够处理的最大图片尺寸和缩放结果(肉眼不可察觉的误差)受到了一 定的影响,这里给出一个使用浮点运算的版本,可以在有这种需求的场合使用:

void PicZoom3_float(const TPicRegion& Dst,const TPicRegion& Src) {

//注意: 该函数需要FPU支持

if ( (0==Dst.width)||(0==Dst.height)

||(0==Src.width)||(0==Src.height)) return;

double xrFloat=1.000000001/((double)Dst.width/Src.width); double yrFloat=1.000000001/((double)Dst.height/Src.height);

unsigned short RC_Old; unsigned short RC_Edit;

asm //设置FPU的取整方式 为了直接使用fist浮点指令 {

FNSTCW RC_Old // 保存协处理器控制字,用来恢复 FNSTCW RC_Edit // 保存协处理器控制字,用来修改 FWAIT

OR RC_Edit, 0x0F00 // 改为 RC=11 使FPU向零取整 FLDCW RC_Edit // 载入协处理器控制字,RC场已经修改 }

unsigned long dst_width=Dst.width; TARGB32* pDstLine=Dst.pdata; double srcy=0;

for (unsigned long y=0;y

TARGB32* pSrcLine=((TARGB32*)((TUInt8*)Src.pdata+Src.byte_width*((long)srcy))); /**//*

double srcx=0;

for (unsigned long x=0;x

pDstLine[x]=pSrcLine[(unsigned long)srcx];//因为默认的浮点取整是一个很慢

//的操作! 所以才使用了直接操作FPU的内联汇编代码。

srcx+=xrFloat; }*/

asm fld xrFloat //st0==xrFloat

asm fldz //st0==0 st1==xrFloat unsigned long srcx=0;

for (long x=0;x

asm fist dword ptr srcx //srcx=(long)st0 pDstLine[x]=pSrcLine[srcx];

asm fadd st,st(1) //st0+=st1 st1==xrFloat }

asm fstp st asm fstp st

srcy+=yrFloat;

((TUInt8*&)pDstLine)+=Dst.byte_width; }

asm //恢复FPU的取整方式 {

FWAIT

FLDCW RC_Old } }

//////////////////////////////////////////////////////////////////////////////// //速度测试:

//==============================================================================

// PicZoom3_float 286.2 fps

////////////////////////////////////////////////////////////////////////////////

e.注意到这样一个事实:每一行的缩放比例是固定的;那么可以预先建立一个缩放映射表格 来处理缩放映射算法(PicZoom3_Table和PicZoom3_float的实现等价); void PicZoom3_Table(const TPicRegion& Dst,const TPicRegion& Src) {

if ( (0==Dst.width)||(0==Dst.height)

||(0==Src.width)||(0==Src.height)) return; unsigned long dst_width=Dst.width;

unsigned long* SrcX_Table = new unsigned long[dst_width]; for (unsigned long x=0;x

SrcX_Table[x]=(x*Src.width/Dst.width); }

TARGB32* pDstLine=Dst.pdata;

for (unsigned long y=0;y

unsigned long srcy=(y*Src.height/Dst.height);

TARGB32* pSrcLine=((TARGB32*)((TUInt8*)Src.pdata+Src.byte_width*srcy));

for (unsigned long x=0;x

delete [] SrcX_Table; }

//////////////////////////////////////////////////////////////////////////////// //速度测试:

//==============================================================================

// PicZoom3_Table 390.1 fps

////////////////////////////////////////////////////////////////////////////////

f.为了加快缩放，可以采用根据缩放比例动态生成函数的方式来得到更快的缩放函数；这 有点像编译器的工作原理；要实现它需要的工作量比较大(或比较晦涩)就不再实现了； (动态生成是一种不错的思路，但个人觉得对于缩放，实现它的必要性不大)

g.现代CPU中，在读取数据和写入数据时，都有自动的缓存机制；很容易知道，算法中生 成的数据不会很快再次使用，所以不需要写入缓存的帮助；在SSE指令集中增加了movntq 等指令来完成这个功能；

(尝试过利用CPU显式prefetcht0、prefetchnta预读指令或直接的mov读取指令等速度反

而略有下降:( 但预读在copy算法中速度优化效果很明显 )

void PicZoom3_SSE(const TPicRegion& Dst,const TPicRegion& Src) {

//警告: 函数需要CPU支持MMX和movntq指令 if ( (0==Dst.width)||(0==Dst.height)

||(0==Src.width)||(0==Src.height)) return;

unsigned long xrIntFloat_16=(Src.width<<16)/Dst.width+1; unsigned long yrIntFloat_16=(Src.height<<16)/Dst.height+1;

unsigned long dst_width=Dst.width; TARGB32* pDstLine=Dst.pdata; unsigned long srcy_16=0;

for (unsigned long y=0;y

TARGB32* pSrcLine=((TARGB32*)((TUInt8*)Src.pdata+Src.byte_width*(srcy_16>>16)));

asm {

push ebp

mov esi,pSrcLine mov edi,pDstLine mov edx,xrIntFloat_16 mov ecx,dst_width

xor ebp,ebp //srcx_16=0

and ecx, (not 3) //循环4次展开 TEST ECX,ECX //nop jle EndWriteLoop

lea edi,[edi+ecx*4] neg ecx

//todo: 预读

WriteLoop:

mov eax,ebp

shr eax,16 //srcx_16>>16 lea ebx,[ebp+edx] movd mm0,[esi+eax*4]

shr ebx,16 //srcx_16>>16 PUNPCKlDQ mm0,[esi+ebx*4] lea ebp,[ebp+edx*2]

// movntq qword ptr [edi+ecx*4], mm0 //不使用缓存的写入指令

asm _emit 0x0F asm _emit 0xE7 asm _emit 0x04 asm _emit 0x8F

mov eax,ebp

shr eax,16 //srcx_16>>16 lea ebx,[ebp+edx]

movd mm1,[esi+eax*4]

shr ebx,16 //srcx_16>>16 PUNPCKlDQ mm1,[esi+ebx*4] lea ebp,[ebp+edx*2]

// movntq qword ptr [edi+ecx*4+8], mm1 //不使用缓存的写入指令

asm _emit 0x0F asm _emit 0xE7 asm _emit 0x4C asm _emit 0x8F asm _emit 0x08

add ecx, 4 jnz WriteLoop

//sfence //刷新写入

asm _emit 0x0F asm _emit 0xAE asm _emit 0xF8 emms EndWriteLoop:

mov ebx,ebp pop ebp

//处理边界 循环次数为0,1,2,3；(这个循环可以展开,做一个跳转表,略) mov ecx,dst_width and ecx,3 TEST ECX,ECX jle EndLineZoom

lea edi,[edi+ecx*4] neg ecx StartBorder:

mov eax,ebx

shr eax,16 //srcx_16>>16 mov eax,[esi+eax*4] mov [edi+ecx*4],eax add ebx,edx

inc ECX

JNZ StartBorder EndLineZoom: }

//

srcy_16+=yrIntFloat_16;

((TUInt8*&)pDstLine)+=Dst.byte_width;

} }

//=====================================================================

//鉴于有读者反映汇编代码阅读困难，这里给出一个使用intel提供的函数调用方式的实现， //读者可以相互对照来阅读代码

//要编译PicZoom3_SSE_mmh,需要#include #include

//并且需要编译器支持

//函数PicZoom3_SSE_mmh速度为 593.7 fps

void PicZoom3_SSE_mmh(const TPicRegion& Dst,const TPicRegion& Src) {

//警告: 函数需要CPU支持MMX和movntq指令 if ( (0==Dst.width)||(0==Dst.height)

||(0==Src.width)||(0==Src.height)) return;

unsigned long xrIntFloat_16=(Src.width<<16)/Dst.width+1; unsigned long yrIntFloat_16=(Src.height<<16)/Dst.height+1; unsigned long dst_width=Dst.width; TARGB32* pDstLine=Dst.pdata; unsigned long srcy_16=0;

unsigned long for4count=dst_width/4*4; for (unsigned long y=0;y

TARGB32* pSrcLine=((TARGB32*)((TUInt8*)Src.pdata+Src.byte_width*(srcy_16>>16)));

unsigned long srcx_16=0; unsigned long x;

for (x=0;x

__m64 m0=_m_from_int(*(int*)(&pSrcLine[srcx_16>>16])); srcx_16+=xrIntFloat_16;

m0=_m_punpckldq(m0, _m_from_int(*(int*)(&pSrcLine[srcx_16>>16])) );

srcx_16+=xrIntFloat_16;

__m64 m1=_m_from_int(*(int*)(&pSrcLine[srcx_16>>16])); srcx_16+=xrIntFloat_16;

m1=_m_punpckldq(m1, _m_from_int(*(int*)(&pSrcLine[srcx_16>>16])) );

srcx_16+=xrIntFloat_16;

_mm_stream_pi((__m64 *)&pDstLine[x],m0); //不使用缓存的写入指令

_mm_stream_pi((__m64 *)&pDstLine[x+2],m1); //不使用缓存的写入指令

}

unsigned long y0_sub1=(y_16>>16)-1;

long u_16_add1=((unsigned short)(x_16))+(1<<16); long v_16_add1=((unsigned short)(y_16))+(1<<16);

TARGB32 pixel[16];

for (long i=0;i<4;++i) {

long y=y0_sub1+i;

pixel[i*4+0]=Pixels_Bound(pic,x0_sub1 ,y); pixel[i*4+1]=Pixels_Bound(pic,x0_sub1+1,y); pixel[i*4+2]=Pixels_Bound(pic,x0_sub1+2,y); pixel[i*4+3]=Pixels_Bound(pic,x0_sub1+3,y); }

TPicRegion npic;

npic.pdata =&pixel[0];

npic.byte_width=4*sizeof(TARGB32); //npic.width =4; //npic.height =4;

ThreeOrder_Fast_MMX(npic,u_16_add1,v_16_add1,result); }

void PicZoom_ThreeOrder_MMX(const TPicRegion& Dst,const TPicRegion& Src) {

if ( (0==Dst.width)||(0==Dst.height)

||(0==Src.width)||(0==Src.height)) return;

long xrIntFloat_16=((Src.width)<<16)/Dst.width+1; long yrIntFloat_16=((Src.height)<<16)/Dst.height+1; const long csDErrorX=-(1<<15)+(xrIntFloat_16>>1); const long csDErrorY=-(1<<15)+(yrIntFloat_16>>1);

unsigned long dst_width=Dst.width;

//计算出需要特殊处理的边界

long border_y0=((1<<16)-csDErrorY)/yrIntFloat_16+1;//y0+y*yr>=1; y0=csDErrorY => y>=(1-csDErrorY)/yr

if (border_y0>=Dst.height) border_y0=Dst.height; long border_x0=((1<<16)-csDErrorX)/xrIntFloat_16+1; if (border_x0>=Dst.width ) border_x0=Dst.width;

long border_y1=(((Src.height-3)<<16)-csDErrorY)/yrIntFloat_16+1; //y0+y*yr<=(height-3) => y<=(height-3-csDErrorY)/yr

if (border_y1

long border_x1=(((Src.width-3)<<16)-csDErrorX)/xrIntFloat_16+1;; if (border_x1

TARGB32* pDstLine=Dst.pdata; long srcy_16=csDErrorY; long y;

for (y=0;y

long srcx_16=csDErrorX;

for (unsigned long x=0;x

ThreeOrder_Border_MMX(Src,srcx_16,srcy_16,&pDstLine[x]); //border

srcx_16+=xrIntFloat_16; }

srcy_16+=yrIntFloat_16;

((TUInt8*&)pDstLine)+=Dst.byte_width; }

for (y=border_y0;y

long srcx_16=csDErrorX; long x;

for (x=0;x

ThreeOrder_Border_MMX(Src,srcx_16,srcy_16,&pDstLine[x]);//border

srcx_16+=xrIntFloat_16; }

for (x=border_x0;x

ThreeOrder_Fast_MMX(Src,srcx_16,srcy_16,&pDstLine[x]);//fast MMX !

srcx_16+=xrIntFloat_16; }

for (x=border_x1;x

ThreeOrder_Border_MMX(Src,srcx_16,srcy_16,&pDstLine[x]);//border

srcx_16+=xrIntFloat_16; }

srcy_16+=yrIntFloat_16;

((TUInt8*&)pDstLine)+=Dst.byte_width; }

for (y=border_y1;y

long srcx_16=csDErrorX;

for (unsigned long x=0;x

ThreeOrder_Border_MMX(Src,srcx_16,srcy_16,&pDstLine[x]); //border

srcx_16+=xrIntFloat_16; }

srcy_16+=yrIntFloat_16;

((TUInt8*&)pDstLine)+=Dst.byte_width; }

asm emms }

//////////////////////////////////////////////////////////////////////////////// //速度测试:

//==============================================================================

// PicZoom_ThreeOrder_MMX 34.3 fps

////////////////////////////////////////////////////////////////////////////////

N：将测试结果放到一起：

////////////////////////////////////////////////////////////////////////////////

//CPU: AMD64x2 4200+(2.37G) zoom 800*600 to 1024*768

//==============================================================================

// StretchBlt 232.7 fps // PicZoom3_SSE 711.7 fps // PicZoom_BilInear_MMX_Ex 157.0 fps //

// PicZoom_ThreeOrder0 3.6 fps // PicZoom_ThreeOrder_Common 16.9 fps // PicZoom_ThreeOrder_MMX 34.3 fps

////////////////////////////////////////////////////////////////////////////////

补充Intel Core2 4400上的测试成绩:

////////////////////////////////////////////////////////////////////////////////

//CPU: Intel Core2 4400(2.00G) zoom 800*600 to 1024*768

//===================================================================

===========

// PicZoom3_SSE 1099.7 fps // PicZoom_BilInear_MMX_Ex 142.9 fps //

// PicZoom_ThreeOrder0 4.2 fps // PicZoom_ThreeOrder_Common 17.6 fps // PicZoom_ThreeOrder_MMX 34.4 fps

////////////////////////////////////////////////////////////////////////////////

高质量的快速的图像缩放 下篇

A:对于前一篇文章中的二次线性插值、三次卷积插值算法，但它们处理缩小到0.5倍以下的 时候效果就会越来越差；这是因为插值的时候自考虑了附近点的原因；如下图：

原图 近邻取样 缩放到0.4倍 缩放到0.2倍 缩放到0.1倍

0.1倍

二次线性插值 缩放到0.4倍 缩放到0.2倍 缩放到

0.1倍

三次卷积插值 缩放到0.4倍 缩放到0.2倍 缩放到

可以看出：当缩小的比例很大的时候，插值算法的效果和近邻取样的效果差不多了:( ; 一种可行的解决方案就是:缩小时考虑更多的点； 但这种解决方案有很多缺点：函数编写麻烦， 速度也许会很慢，优化也不容易做； 还有一个方案就是预先建立一个缩放好的大小不同的图片

列表，每一张图片都是前一张的0.5倍(这种图片列表就是MipMap链)，缩放的时候根据需要缩放

的比例从表中选择一张大小接近的图片来作为缩放的源图片； 该方案的优点：不需要编写新的 底层缩放算法，直接使用前面优化好的插值算法； 缺点：需要预先建立MipMap链，它需要时间，

并且它的储存需要多占用原图片的1/3空间(0.5^2+0.5^4+0.5^6+...=1/3)；还有一个不

太明显

的小问题，就是在一张图片的连续的比例不同的缩放中，选择会从MipMap的一张源图片跳到另

一张图片，视觉效果上可能会有一个小的跳跃(我在《魔兽世界》里经常看到这种效应:)；一种 改进方案就是选择MipMap图片的时候，选择出附近的两张图片作为缩放的源图片；对两张图片

单独进行插值(和原来一致)输出两个值，然后把这两个值线性插值为最终结果；还有一个比较 大的缺点就是当缩放比例不均匀时(比如x轴放大y轴缩小)，缩放效果也不好；

(当前很多显卡都提供了MipMap纹理和对应的插值方案，OpenGL和DirectX都提供了操作接口)

（\三次线性插值和MipMap链\其实比较简单，这里只给出关键代码或算法） B: MipMap图片的生成:

原图片缩放到0.5倍(宽和高都为原图片的1/2),在把0.5倍的图片缩放到0.25倍,....

直到宽和高都为1个像素，如果有一个长度先到1就保持1； 缩放过程中，可以可采用前面的缩放插值算法；

如果为了速度可以考虑这样的方案，要求原图片的宽和高必须是2的整数次方的数值，缩放时就可以直接将

2x2的像素快速合并为一个像素(如果允许原图片宽和高为任何值，可以考虑在合并时引入Alpha通道)；

C: MipMap链图片的储存方案:

MipMap链图片示意图

本文来源：https://www.bwwdw.com/article/3ish.html