图形图像处理－之－任意角度的高质量的快速的图像旋转 中篇 高质量的旋转
HouSisong@GMail.com 2007.06.26
(2009.03.09 可以到这里下载旋转算法的完整的可以编译的项目源代码: http://blog.csdn.net/housisong/archive/2009/03/09/3970925.aspx )
(2007.09.14 修正三次卷积的MMX版本中表的精度太低(7bit),造成卷积结果误差较大的问题,该版本提高了插值质量,并且速度加快约15-20%)
tag:图像旋转,任意角度,图像缩放,速度优化,定点数优化,近邻取样插值,二次线性插值,
三次卷积插值,MipMap链,三次线性插值,MMX/SSE优化,CPU缓存优化,AlphaBlend,颜色混合,并行
摘要:首先给出一个基本的图像旋转算法，然后一步一步的优化其速度和旋转质量,打破不能软件旋转的神话!
任意角度的高质量的快速的图像旋转 全文 分为:
上篇 纯软件的任意角度的快速旋转
中篇 高质量的旋转
下篇 补充话题(完整AlphaBlend旋转、旋转函数并行化、针对大图片的预读缓冲区优化)
正文：
为了便于讨论，这里只处理32bit的ARGB颜色；
代码使用C++;涉及到汇编优化的时候假定为x86平台;使用的编译器为vc2005;
为了代码的可读性,没有加入异常处理代码;
测试使用的CPU为AMD64x2 4200+(2.37G),测试时使用的单线程执行;
(一些基础代码和插值原理的详细说明参见作者的《图形图像处理－之－高质量的快速的图像缩放》系列文章
旋转原理和基础参考《图形图像处理－之－任意角度的高质量的快速的图像旋转 上篇 纯软件的任意角度的快速旋转》)
速度测试说明:
只测试内存数据到内存数据的缩放
测试图片都是800*600旋转到1004*1004，测试成绩取各个旋转角度的平均速度值; fps表示每秒钟的帧数,值越大表示函数越快
A:一些颜色和图片的数据定义:
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(TARGB32* pcolor,const long byte_width,const long x,const long y){
return ( (TARGB32*)((TUInt8*)pcolor+byte_width*y) )[x];
} //那么访问一个点的函数可以写为：
inline TARGB32& Pixels(const TPicRegion& pic,const long x,const long y)
{
return Pixels(pic.pdata,pic.byte_width,x,y);
}
//判断一个点是否在图片中
inline bool PixelsIsInPic(const TPicRegion& pic,const long x,const long y)
{
return ( (x>=0)&&(x<pic.width) && (y>=0)&&(y<pic.height) );
} //访问一个点的函数，(x,y)坐标可能超出图片边界； //边界处理模式:边界饱和
inline TARGB32& Pixels_Bound(const TPicRegion& pic,long x,long y)
{
//assert((pic.width>0)&&(pic.height>0));
if (x<0) x=0; else if (x>=pic.width ) x=pic.width -1;
if (y<0) y=0; else if (y>=pic.height) y=pic.height-1;
return Pixels(pic,x,y);
}
inline TARGB32
& Pixels_Bound(const TPicRegion& pic,long x,long y,bool& IsInPic){
//assert((pic.width>0)&&(pic.height>0));
IsInPic=true;
if (x<0) {x=0; IsInPic=false; } else if (x>=pic.width ) {x=pic.width -1; IsInPic=false; }
if (y<0) {y=0; IsInPic=false; } else if (y>=pic.height) {y=pic.height-1; IsInPic=false; }
return Pixels(pic,x,y);
}
B:实现二次线性插值的旋转
(插值原理参见我的blog文章《图形图像处理－之－高质量的快速的图像缩放 中篇 二次线性插值和三次卷积插值》)
a.首先改写用于边界扫描的类TRotaryClipData；在图片边缘插值的时候，插值的颜色数据可能
部分在图片外，部分颜色数据在图片内,所以TRotaryClipData需要同时找出“插值边界以外”、
“插值边界”、“插值边界以内”
扫描线图示: 外 | 边界 | 内 | 边界 | 外
public:
long src_width;
long src_height;
long dst_width;
long dst_height;
long Ax_16;
long Ay_16;
long Bx_16;
long By_16;
long Cx_16;
long Cy_16;
long border_width;//插值边界宽度
private:
long cur_dst_up_x0;
long cur_dst_up_x1;
long cur_dst_down_x0;
long cur_dst_down_x1;
inline bool is_border_src(long src_x_16,long src_y_16)
{
return ( ( (src_x_16>=(-(border_width<<16)))&&((src_x_16>>16)<(src_width +border_width)) )
&& ( (src_y_16>=(-(border_width<<16)))&&((src_y_16>>16)<(src_height+border_width)) ) );
}
inline bool is_in_src(long src_x_16,long src_y_16)
{
return ( ( (src_x_16>=(border_width<<16))&&((src_x_16>>16)<(src_width-border_width) ) )
&& ( (src_y_16>=(border_width<<16))&&((src_y_16>>16)<(src_height-border_width)) ) );
}
void find_begin_in(long dst_y,long& out_dst_x,long& src_x_16,long& src_y_16)
{
src_x_16-=Ax_16;
src_y_16-=Ay_16;
while (is_border_src(src_x_16,src_y_16))
{
--out_dst_x;
src_x_16-=Ax_16;
src_y_16-=Ay_16;
}
src_x_16+=Ax_16;
src_y_16+=Ay_16;
}
bool find_begin(long dst_y,long& out_dst_x0,long dst_x1)
{
long test_dst_x0=out_dst_x0-1;
long src_x_16=Ax_16*test_dst_x0 + Bx_16*dst_y + Cx_16;
long src_y_16=Ay_16*test_dst_x0 + By_16*dst_y + Cy_16;
for (long i=test_dst_x0;i<=dst_x1;++i)
{
if (is_border_src(src_x_16,src_y_16))
{
out_dst_x0=i;
if (i==test_dst_x0)
find_begin_in(dst_y,out_dst_x0,src_x_16,src_y_16);
if (out_dst_x0<0)
{
src_x_16-=(Ax_16*out_dst_x0);
src_y_16-=(Ay_16*out_dst_x0);
}
out_src_x0_16=src_x_16;
out_src_y0_16=src_y_16;
return true;
}
else
{
src_x_16+=Ax_16;
src_y_16+=Ay_16;
}
}
return false;
}
void find_end(long dst_y,long dst_x0,long& out_dst_x1)
{
long test_dst_x1=out_dst_x1;
if (test_dst_x1<dst_x0) test_dst_x1=dst_x0;
long src_x_16=Ax_16*test_dst_x1 + Bx_16*dst_y + Cx_16;
long src_y_16=Ay_16*test_dst_x1 + By_16*dst_y + Cy_16;
if (is_border_src(src_x_16,src_y_16))
{
++test_dst_x1;
src_x_16+=Ax_16;
src_y_16+=Ay_16;
while (is_border_src(src_x_16,src_y_16))
{
++test_dst_x1;
src_x_16+=Ax_16;
src_y_16+=Ay_16;
}
out_dst_x1=test_dst_x1;
}
else
{
src_x_16-=Ax_16;
src_y_16-=Ay_16;
while (!is_border_src(src_x_16,src_y_16))
{
--test_dst_x1;
src_x_16-=Ax_16;
src_y_16-=Ay_16;
}
out_dst_x1=test_dst_x1;
}
}
inline
void update_out_dst_x_in(){
if ((0==border_width)||(out_dst_x0_boder>=out_dst_x1_boder) )
{
out_dst_x0_in=out_dst_x0_boder;
out_dst_x1_in=out_dst_x1_boder;
}
else
{
long src_x_16=out_src_x0_16;
long src_y_16=out_src_y0_16;
long i=out_dst_x0_boder;
while (i<out_dst_x1_boder)
{
if (is_in_src(src_x_16,src_y_16)) break;
src_x_16+=Ax_16;
src_y_16+=Ay_16;
++i;
}
out_dst_x0_in=i;
src_x_16
=out_src_x0_16+(out_dst_x1_boder-out_dst_x0_boder)*Ax_16;src_y_16=out_src_y0_16+(out_dst_x1_boder-out_dst_x0_boder)*Ay_16;
i=out_dst_x1_boder;
while (i>out_dst_x0_in)
{
src_x_16-=Ax_16;
src_y_16-=Ay_16;
if (is_in_src(src_x_16,src_y_16)) break;
--i;
}
out_dst_x1_in=i;
}
}
inline void update_out_dst_up_x()
{
if (cur_dst_up_x0<0)
out_dst_x0_boder=0;
else
out_dst_x0_boder=cur_dst_up_x0;
if (cur_dst_up_x1>=dst_width)
out_dst_x1_boder=dst_width;
else
out_dst_x1_boder=cur_dst_up_x1;
update_out_dst_x_in();
}
inline void update_out_dst_down_x()
{
if (cur_dst_down_x0<0)
out_dst_x0_boder=0;
else
out_dst_x0_boder=cur_dst_down_x0;
if (cur_dst_down_x1>=dst_width)
out_dst_x1_boder=dst_width;
else
out_dst_x1_boder=cur_dst_down_x1;
update_out_dst_x_in();
} public:
long out_src_x0_16;
long out_src_y0_16;
long out_dst_up_y;
long out_dst_down_y;
long out_dst_x0_boder;
long out_dst_x0_in;
long out_dst_x1_in;
long out_dst_x1_boder; public:
bool inti_clip(double move_x,double move_y,unsigned long aborder_width)
{
border_width=aborder_width;
//计算src中心点映射到dst后的坐标
out_dst_down_y=(long)(src_height*0.5+move_y);
cur_dst_down_x0=(long)(src_width*0.5+move_x);
cur_dst_down_x1=cur_dst_down_x0;
//得到初始扫描线
if (find_begin(out_dst_down_y,cur_dst_down_x0,cur_dst_down_x1))
find_end(out_dst_down_y,cur_dst_down_x0,cur_dst_down_x1);
out_dst_up_y=out_dst_down_y;
cur_dst_up_x0=cur_dst_down_x0;
cur_dst_up_x1=cur_dst_down_x1;
update_out_dst_up_x();
return (cur_dst_down_x0<cur_dst_down_x1);
}
bool next_clip_line_down()
{
++out_dst_down_y;
if (!find_begin(out_dst_down_y,cur_dst_down_x0,cur_dst_down_x1)) return false;
find_end(out_dst_down_y,cur_dst_down_x0,cur_dst_down_x1);
update_out_dst_down_x();
return (cur_dst_down_x0<cur_dst_down_x1);
}
bool next_clip_line_up()
{
--out_dst_up_y;
if (!find_begin(out_dst_up_y,cur_dst_up_x0,cur_dst_up_x1)) return false;
find_end(out_dst_up_y,cur_dst_up_x0,cur_dst_up_x1);
update_out_dst_up_x();
return (cur_dst_up_x0<cur_dst_up_x1);
}
};
b. 边界插值的特殊处理
对于“插值边界以外”很简单，不用处理直接跳过插值；
对于“插值边界以内”，也比较容易处理，直接调用快速的差值算法就可以了，不用担心内存访问问题；
插值实现：
（从《图形图像处理－之－高质量的快速的图像缩放 中篇 二次线性插值和三次卷积插值》文章来的，后面不再说明）
{
TARGB32* PColor0=&Pixels(pic,x_16>>16,y_16>>16);
TARGB32* PColor1=(TARGB32*)((TUInt8*)PColor0+pic.byte_width);
unsigned long u_8=(unsigned char)(x_16>>8);
unsigned long v_8=(unsigned char)(y_16>>8);
unsigned long pm3_8=(u_8*v_8)>>8;
unsigned long pm2_8=u_8-pm3_8;
unsigned long pm1_8=v_8-pm3_8;
unsigned long pm0_8=256-pm1_8-pm2_8-pm3_8;
unsigned
long Color=*(unsigned long*)(PColor0);unsigned long BR=(Color & 0x00FF00FF)*pm0_8;
unsigned long GA=((Color & 0xFF00FF00)>>8)*pm0_8;
Color=((unsigned long*)(PColor0))[1];
GA+=((Color & 0xFF00FF00)>>8)*pm2_8;
BR+=(Color & 0x00FF00FF)*pm2_8;
Color=*(unsigned long*)(PColor1);
GA+=((Color & 0xFF00FF00)>>8)*pm1_8;
BR+=(Color & 0x00FF00FF)*pm1_8;
Color=((unsigned long*)(PColor1))[1];
GA+=((Color & 0xFF00FF00)>>8)*pm3_8;
BR+=(Color & 0x00FF00FF)*pm3_8;
*(unsigned long*)result=(GA & 0xFF00FF00)|((BR & 0xFF00FF00)>>8);
}
对于“插值边界”，就需要特殊处理了，很多插值旋转的实现可能都在这里打了折扣；要想完美的解决
这块区域，可以引入AlphaBlend(带Alpha通道的颜色混合) ；
其实AlphaBlend的原理也很简单，就是按不同的比例混合两种颜色:
new_color=dst_color*(1-alpha)+src_color*alpha;
对于ARGB32bit颜色，需要用该公式分别处理4个颜色通道，并假设Alpha为[0..255]的整数，那么完整的实现函数为:
{
//AlphaB