分类: LINUX
2015-03-20 14:05:27
原文地址:图像缩放算法 作者:shenhailuanma
转自:http://blog.chinaunix.net/space.php?uid=22915173&do=blog&id=2185545
摘要:首先给出一个基本的图像缩放算法,然后一步一步的优化其速度和缩放质量; 高质量的快速的图像缩放 全文 分为: 正文: 为了便于讨论,这里只处理32bit的ARGB颜色; A: 首先定义图像数据结构: B: 缩放原理和公式图示:
缩放后图片 原图片 (Sx-0)/(SW-0)=(Dx-0)/(DW-0) (Sy-0)/(SH-0)=(Dy-0)/(DH-0) C: 缩放算法的一个参考实现 //给出一个最简单的缩放函数(插值方式为近邻取样,而且我“尽力”把它写得慢一些了:D)
//////////////////////////////////////////////////////////////////////////////// a.PicZoom0函数并没有按照颜色数据在内存中的排列顺序读写(内部循环递增y行
//////////////////////////////////////////////////////////////////////////////// b.“(x*Src.Width/Dst.Width)”表达式中有一个除法运算,它属于很慢的操作(比一般
//////////////////////////////////////////////////////////////////////////////// c. 在x的循环中y一直不变,那么可以提前计算与y相关的值;
1.可以发现srcy的值和x变量无关,可以提前到x轴循环之前;2.展开Pixels函数,优化与y相关的指针计算;
//////////////////////////////////////////////////////////////////////////////// d.定点数优化使函数能够处理的最大图片尺寸和缩放结果(肉眼不可察觉的误差)受到了一
////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////// f.为了加快缩放,可以采用根据缩放比例动态生成函数的方式来得到更快的缩放函数;这 g.现代CPU中,在读取数据和写入数据时,都有自动的缓存机制;很容易知道,算法中生
////////////////////////////////////////////////////////////////////////////////
原图 放大图(x轴放大8倍,y轴放大12倍)
F: 把测试成绩放在一起: 补充Intel Core2 4400上的测试成绩:
上篇 近邻取样插值和其速度优化
中篇 二次线性插值和三次卷积插值
下篇 三次线性插值和MipMap链
代码使用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
////////////////////////////////////////////////////////////////////////////////
#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];
}
(宽DW,高DH) (宽SW,高SH)
=> Sx=Dx*SW/DW
Sy=Dy*SH/DH
//Src.PColorData指向源数据区,Dst.PColorData指向目的数据区
//函数将大小为Src.Width*Src.Height的图片缩放到Dst.Width*Dst.Height的区域中
{
if ( (0==Dst.width)||(0==Dst.height)
||(0==Src.width)||(0==Src.height)) return;
for (long x=0;x
long srcy=(y*Src.height/Dst.height);
Pixels(Dst,x,y)=Pixels(Src,srcx,srcy);
}
}
}
//速度测试:
//==============================================================================
// PicZoom0 19.4 fps
////////////////////////////////////////////////////////////////////////////////
D: 优化PicZoom0函数
索引),将造成CPU缓存预读失败和内存颠簸导致巨大的性能损失,(很多硬件都有这种特性,
包括缓存、内存、显存、硬盘等,优化顺序访问,随机访问时会造成巨大的性能损失)
所以先交换x,y循环的顺序:
{
if ( (0==Dst.width)||(0==Dst.height)
||(0==Src.width)||(0==Src.height)) return;
for (long y=0;y
long srcy=(y*Src.height/Dst.height);
Pixels(Dst,x,y)=Pixels(Src,srcx,srcy);
}
}
}
//速度测试:
//==============================================================================
// PicZoom1 30.1 fps
////////////////////////////////////////////////////////////////////////////////
的加减运算慢几十倍!),使用定点数的方法来优化它;
{
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格式定点数
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
////////////////////////////////////////////////////////////////////////////////
{
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;
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
////////////////////////////////////////////////////////////////////////////////
定的影响,这里给出一个使用浮点运算的版本,可以在有这种需求的场合使用:
{
//注意: 该函数需要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*((
/**//*
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
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的实现等价);
{
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
TARGB32* pSrcLine=((TARGB32*)((TUInt8*)Src.pdata+Src.byte_width*srcy));
for (unsigned long x=0;x
((TUInt8*&)pDstLine)+=Dst.byte_width;
}
delete [] SrcX_Table;
}
//速度测试:
//==============================================================================
// PicZoom3_Table 390.1 fps
////////////////////////////////////////////////////////////////////////////////
有点像编译器的工作原理;要实现它需要的工作量比较大(或比较晦涩)就不再实现了;
(动态生成是一种不错的思路,但个人觉得对于缩放,实现它的必要性不大)
成的数据不会很快再次使用,所以不需要写入缓存的帮助;在SSE指令集中增加了movntq
等指令来完成这个功能;
(尝试过利用CPU显式prefetcht0、prefetchnta预读指令或直接的mov读取指令等速度反
而略有下降:( 但预读在copy算法中速度优化效果很明显 )
{
//警告: 函数需要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
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;
}
}
//读者可以相互对照来阅读代码
//要编译PicZoom3_SSE_mmh,需要#include
//并且需要编译器支持
//函数PicZoom3_SSE_mmh速度为 593.7 fps
{
//警告: 函数需要CPU支持MMX和movntq指令
||(0==Src.width)||(0==Src.height)) return;
unsigned long yrIntFloat_16=(Src.height<<16)/Dst.height+1;
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); //不使用缓存的写入指令
}
for (x=for4count;x
pDstLine[x]=pSrcLine[srcx_16>>16];
srcx_16+=xrIntFloat_16;
}
srcy_16+=yrIntFloat_16;
((TUInt8*&)pDstLine)+=Dst.byte_width;
}
_m_empty();
}
//速度测试:
//==============================================================================
// PicZoom3_SSE 711.7 fps
////////////////////////////////////////////////////////////////////////////////
E: 缩放效果图:
原图 缩小图(缩小到0.66倍) 放大图(放大到1.6倍)
////////////////////////////////////////////////////////////////////////////////
//CPU: AMD64x2 4200+(2.1G) zoom 800*600 to 1024*768
//==============================================================================
// 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
//
// PicZoom0 19.4 fps
// PicZoom1 30.1 fps
// PicZoom2 185.8 fps
// PicZoom3 414.4 fps
// PicZoom3_float 286.2 fps
// PicZoom3_Table 390.1 fps
// PicZoom3_SSE 711.7 fps
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
//CPU: Intel Core2 4400(2.00G) zoom 800*600 to 1024*768
//==============================================================================
// PicZoom0 15.0 fps
// PicZoom1 63.9 fps
// PicZoom2 231.2 fps
// PicZoom3 460.5 fps
// PicZoom3_float 422.5 fps
// PicZoom3_Table 457.6 fps
// PicZoom3_SSE 1099.7 fps
////////////////////////////////////////////////////////////////////////////////
摘要:首先给出一个基本的图像缩放算法,然后一步一步的优化其速度和缩放质量;
高质量的快速的图像缩放 全文 分为:
上篇 近邻取样插值和其速度优化
中篇 二次线性插值和三次卷积插值
下篇 三次线性插值和MipMap链
正文:
为了便于讨论,这里只处理32bit的ARGB颜色;
代码使用C++;涉及到汇编优化的时候假定为x86平台;使用的编译器为vc2005;
为了代码的可读性,没有加入异常处理代码;
测试使用的CPU为AMD64x2 4200+(2.37G) 和 Intel Core2 4400(2.00G);
速度测试说明:
只测试内存数据到内存数据的缩放
测试图片都是800*600缩放到1024*768; fps表示每秒钟的帧数,值越大表示函数越快
A:近邻取样插值、二次线性插值、三次卷积插值 缩放效果对比
原图 近邻取样缩放到0.6倍 近邻取样缩放到1.6倍
二次线性插值缩放到0.6倍 二次线性插值缩放到1.6倍
三次卷积插值缩放到0.6倍 三次卷积插值缩放到1.6倍
原图 近邻取样缩放到8倍 二次线性插值缩放到8倍 三次卷积插值缩放到8倍 二次线性插值(近似公式)
近邻取样插值缩放简单、速度快,但很多时候缩放出的图片质量比较差(特别是对于人物、景色等),
图片的缩放有比较明显的锯齿;使用二次或更高次插值有利于改善缩放效果;
B: 首先定义图像数据结构:
二次线性插值缩放:
C: 二次线性插值缩放原理和公式图示:
缩放后图片 原图片
(宽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
聚焦看看(Sx,Sy)坐标点(Sx,Sy为浮点数)附近的情况;
对于近邻取样插值的缩放算法,直接取Color0颜色作为缩放后点的颜色;
二次线性插值需要考虑(Sx,Sy)坐标点周围的4个颜色值Color0\Color1\Color2\Color3,
把(Sx,Sy)到A\B\C\D坐标点的距离作为系数来把4个颜色混合出缩放后点的颜色;
( u=Sx-floor(Sx); v=Sy-floor(Sy); 说明:floor函数的返回值为小于等于参数的最大整数 )
二次线性插值公式为:
tmpColor0=Color0*(1-u) + Color2*u;
tmpColor1=Color1*(1-u) + Color3*u;
DstColor =tmpColor0*(1-v) + tmpColor2*v;
展开公式为:
pm0=(1-u)*(1-v);
pm1=v*(1-u);
pm2=u*(1-v);
pm3=u*v;
则颜色混合公式为:
DstColor = Color0*pm0 + Color1*pm1 + Color2*pm2 + Color3*pm3;
参数函数图示:
二次线性插值函数图示
对于上面的公式,它将图片向右下各移动了半个像素,需要对此做一个修正;
=> Sx=(Dx+0.5)*SW/DW-0.5; Sy=(Dy+0.5)*SH/DH-0.5;
而实际的程序,还需要考虑到边界(访问源图片可能超界)对于算法的影响,边界的处理可能有各种
方案(不处理边界或边界回绕或边界饱和或边界映射或用背景颜色混合等;文章中默认使用边界饱和来处理超界);
比如:边界饱和函数:
D:
二次线性插值缩放算法的一个参考实现:PicZoom_BilInear0
该函数并没有做什么优化,只是一个简单的浮点实现版本;
////////////////////////////////////////////////////////////////////////////////
//速度测试:
//==============================================================================
// PicZoom_BilInear0 8.3 fps
////////////////////////////////////////////////////////////////////////////////
E: 把PicZoom_BilInear0的浮点计算改写为定点数实现:PicZoom_BilInear1
////////////////////////////////////////////////////////////////////////////////
//速度测试:
//==============================================================================
// PicZoom_BilInear1 17.7 fps
////////////////////////////////////////////////////////////////////////////////
F: 二次线性插值需要考略边界访问超界的问题,我们可以将边界区域和内部区域分开处理,这样就可以优化内部的插值实现函数了:比如不需要判断访问超界、减少颜色数据复制、减少一些不必要的重复坐标计算等等
////////////////////////////////////////////////////////////////////////////////
//速度测试:
//==============================================================================
// PicZoom_BilInear2 43.4 fps
////////////////////////////////////////////////////////////////////////////////
(F'补充:
如果不想处理边界访问超界问题,可以考虑扩大源图片的尺寸,加一个边框 (“哨兵”优化);
这样插值算法就不用考虑边界问题了,程序写起来也简单很多!
如果对缩放结果的边界像素级精度要求不是太高,我还有一个方案,一个稍微改变的缩放公式:
Sx=Dx*(SW-1)/DW; Sy=Dy*(SH-1)/DH; (源图片宽和高:SW>=2;SH>=2)
证明这个公式不会造成内存访问超界:
要求Dx=DW-1时: sx+1=int( (dw-1)/dw*(dw-1) ) +1 <= (sw-1)
有: int( (sw-1)*(dw-1)/dw ) <=sw-2
(sw-1)*(dw-1)/dw <(sw-1)
(dw-1) /dw<1
(dw-1)
)
G:利用单指令多数据处理的MMX指令一般都可以加快颜色的运算;在使用MMX改写之前,利用
32bit寄存器(或变量)来模拟单指令多数据处理;
数据储存原理:一个颜色数据分量只有一个字节,用2个字节来储存单个颜色分量的计算结果,
对于很多颜色计算来说精度就够了;那么一个32bit寄存器(或变量)就可以储存2个计算出的
临时颜色分量;从而达到了单个指令两路数据处理的目的;
单个指令两路数据处理的计算:
乘法: ((0x00AA*a)<<16) | (0x00BB*a) = 0x00AA00BB * a
可见只要保证0x00AA*a和0x00BB*a都小于(1<<16)那么乘法可以直接使用无符号数乘法了
加法: ((0x00AA+0x00CC)<<16) | (0x00BB+0x00DD) = 0x00AA00BB + 0x00CC00DD
可见只要0x00AA+0x00CC和0x00BB+0x00DD小于(1<<16)那么加法可以直接使用无符号数加法了
(移位、减法等稍微复杂一点,因为这里没有用到就不推倒运算公式了)
////////////////////////////////////////////////////////////////////////////////
//速度测试:
//==============================================================================
// PicZoom_BilInear_Common 65.3 fps
////////////////////////////////////////////////////////////////////////////////
H:使用MMX指令改写:PicZoom_Bilinear_MMX
////////////////////////////////////////////////////////////////////////////////
//速度测试:
//==============================================================================
// PicZoom_BilInear_MMX 132.9 fps
////////////////////////////////////////////////////////////////////////////////
H' 对BilInear_MMX简单改进:PicZoom_Bilinear_MMX_Ex
////////////////////////////////////////////////////////////////////////////////
//速度测试:
//==============================================================================
// PicZoom_Bilinear_MMX_Ex 157.0 fps
////////////////////////////////////////////////////////////////////////////////
I: 把测试成绩放在一起:
////////////////////////////////////////////////////////////////////////////////
//CPU: AMD64x2 4200+(2.37G) zoom 800*600 to 1024*768
//==============================================================================
// StretchBlt 232.7 fps
// PicZoom3_SSE 711.7 fps
//
// PicZoom_BilInear0 8.3 fps
// PicZoom_BilInear1 17.7 fps
// PicZoom_BilInear2 43.4 fps
// PicZoom_BilInear_Common 65.3 fps
// PicZoom_BilInear_MMX 132.9 fps
// PicZoom_BilInear_MMX_Ex 157.0 fps
////////////////////////////////////////////////////////////////////////////////
补充Intel Core2 4400上的测试成绩:
////////////////////////////////////////////////////////////////////////////////
//CPU: Intel Core2 4400(2.00G) zoom 800*600 to 1024*768
//==============================================================================
// PicZoom3_SSE 1099.7 fps
//
// PicZoom_BilInear0 10.7 fps
// PicZoom_BilInear1 24.2 fps
// PicZoom_BilInear2 54.3 fps
// PicZoom_BilInear_Common 59.8 fps
// PicZoom_BilInear_MMX 118.4 fps
// PicZoom_BilInear_MMX_Ex 142.9 fps
////////////////////////////////////////////////////////////////////////////////
三次卷积插值:
J: 二次线性插值缩放出的图片很多时候让人感觉变得模糊(术语叫低通滤波),特别是在放大
的时候;使用三次卷积插值来改善插值结果;三次卷积插值考虑映射点周围16个点(4x4)的颜色来
计算最终的混合颜色,如图;
P(0,0)所在像素为映射的点,加上它周围的15个点,按一定系数混合得到最终输出结果;
混合公式参见PicZoom_ThreeOrder0的实现;
插值曲线公式sin(x*PI)/(x*PI),如图:
三次卷积插值曲线sin(x*PI)/(x*PI) (其中PI=3.1415926...)
K:三次卷积插值缩放算法的一个参考实现:PicZoom_ThreeOrder0
该函数并没有做过多的优化,只是一个简单的浮点实现版本;
////////////////////////////////////////////////////////////////////////////////
//速度测试:
//==============================================================================
// PicZoom_ThreeOrder0 3.6 fps
////////////////////////////////////////////////////////////////////////////////
L: 使用定点数来优化缩放函数;边界和内部分开处理;对SinXDivX做一个查找表;对border_color做一个查找表;
////////////////////////////////////////////////////////////////////////////////
//速度测试:
//==============================================================================
// PicZoom_ThreeOrder_Common 16.9 fps
////////////////////////////////////////////////////////////////////////////////
M: 用MMX来优化ThreeOrder_Common函数:ThreeOrder_MMX
////////////////////////////////////////////////////////////////////////////////
//速度测试:
//==============================================================================
// 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
////////////////////////////////////////////////////////////////////////////////
摘要:首先给出一个基本的图像缩放算法,然后一步一步的优化其速度和缩放质量;
高质量的快速的图像缩放 全文 分为:
上篇 近邻取样插值和其速度优化
中篇 二次线性插值和三次卷积插值
下篇 三次线性插值和MipMap链
正文:
A:对于前一篇文章中的二次线性插值、三次卷积插值算法,但它们处理缩小到0.5倍以下的
时候效果就会越来越差;这是因为插值的时候自考虑了附近点的原因;如下图:
原图 近邻取样 缩放到0.4倍 缩放到0.2倍 缩放到0.1倍
二次线性插值 缩放到0.4倍 缩放到0.2倍 缩放到0.1倍
三次卷积插值 缩放到0.4倍 缩放到0.2倍 缩放到0.1倍
可以看出:当缩小的比例很大的时候,插值算法的效果和近邻取样的效果差不多了:( ;
一种可行的解决方案就是:缩小时考虑更多的点; 但这种解决方案有很多缺点:函数编写麻烦,
速度也许会很慢,优化也不容易做; 还有一个方案就是预先建立一个缩放好的大小不同的图片
列表,每一张图片都是前一张的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链图片示意图
可能的一种物理储存方案(我对每张图片加了一个边框)
D: 定义MipMap数据结构:
MipMap数据结构可以定义为一个TPicRegion数组和该数组的大小;
(MipMap图片的储存参见上面的图示)
比如:
E: MipMap的选择函数和偏好:
在进行缩放时,根据目标图片缓冲区的大小来动态的选者MipMap中的一幅图片来作为源图片;这就需要一个
选择函数;比如:
选择函数可以增加一个偏好参数:
mip选择偏好:0.5没有偏好,靠近0偏向选择小图片,靠近1偏向选择大图片(质量好一些)
F:利用MipMap后的缩放效果:
MipMap+近邻取样 缩放到0.4倍 缩放到0.2倍 缩放到0.1倍
(利用MipMap做一次近邻取样)
MipMap+二次线性插值 缩放到0.4倍 缩放到0.2倍 缩放到0.1倍
(利用MipMap做一次二次线性插值)
MipMap+三次卷积插值 缩放到0.4倍 缩放到0.2倍 缩放到0.1倍
(利用MipMap做一次三次卷积插值)
G: 在MipMap的两张图片之间插值:
选择MipMap的时候,同时可以选择相邻的两张MipMap图片;分别进行插值算法后得到两个颜色结果;
对两个MipMap图片产生的评价值可以作为这两个颜色的插值权重,得到最终的颜色插值结果;优点是
缩放效果好,避免跳跃;缺点是速度慢:)
选择和权重函数的一个可能实现:
H:MipMap间插值效果:
MipMap+两次近邻取样 缩放到0.4倍 缩放到0.2倍 缩放到0.1倍
(利用MipMap做两次近邻取样输出两个值,然后线性插值为最终结果)
三次线性插值 缩放到0.4倍
缩放到0.2倍 缩放到0.1倍
(三次线性插值:利用MipMap做两次二次线性插值输出两个值,然后线性插值为最终结果)
MipMap+两次三次卷积插值 缩放到0.4倍 缩放到0.2倍 缩放到0.1倍
(利用MipMap做两次三次卷积插值输出两个值,然后线性插值为最终结果)
(图像缩放系列终于写完了,计划中写图像任意角度的高质量的快速旋转、Alpha图片混合等,尽请期待:)
(ps: 思考中的一个图片压缩方法:利用MipMap来压缩图像数据;输入一张图片,然后生成MipMap链,保存相邻之间图片的差(数值差可能很小,很容易找好的算法压缩得很小)和最顶的一张图片(一个点); 解压的时候依次求和就得到原图片了; 该算法为无损压缩,适合于人物风景等过渡比较多的图片的压缩,不太适合线条类等相邻间颜色变化剧烈的图片;)