tag:图像旋转,任意角度,图像缩放,速度优化,定点数优化,近邻取样插值,二次线性插值,
   三次卷积插值,MipMap链,三次线性插值,MMX/SSE优化,CPU缓存优化,AlphaBlend,颜色混合,并行

摘要: 该文章是《任意角度的高质量的快速的图像旋转》的一些高级补充话题；
     给出了一个完整的Alpha混合的插值旋转实现；并尝试将旋转函数并行化，从而在多核电脑上获得更快的速度；添加优化预读缓冲区的函数实现版本，提高超大图片的旋转的速度；

任意角度的高质量的快速的图像旋转 全文 分为:
     上篇 纯软件的任意角度的快速旋转
     中篇 高质量的旋转
     下篇 补充话题

(2007.07.15 添加对大图片旋转的预读缓冲区优化版本)

正文：
  为了便于讨论，这里只处理32bit的ARGB颜色；
  代码使用C++;涉及到汇编优化的时候假定为x86平台;使用的编译器为vc2005;
  为了代码的可读性,没有加入异常处理代码;
   测试使用的CPU为AMD64x2 4200+(2.37G) 和 Intel Core2 4400(2.00G);
  (基础代码参考《图形图像处理－之－任意角度的高质量的快速的图像旋转》系列前面的文章)

A:完整的Alpha混合的双线性插值旋转实现
  《高质量的旋转》中已经涉及到了边界的AlphaBlend的问题，这里顺水推舟的实现一个支持全图片Alpha通道Blend混合的双线性插值旋转函数；
   首先给出带完整Alpha通道的源图片:

              

   这张图片是带有8比特Alpha的32比特RGB真彩bmp图片;
   带的Alpha通道在工具里可能显示不出来，单独提取出来的图示：

               

   函数实现：  

  效果图:

B:在双核上并行三次卷积插值旋转的一个简单实现
  (假设图片旋转绘制到目的图片的中间)
  这里利用CWorkThreadPool来并行执行任务;
  (参见我的文章《并行计算简介和多核CPU编程Demo》，里面有CWorkThreadPool类的完整源代码)
  最容易想到的方案就是分成上下两部分分别调用PicRotaryThreeOrder_MMX，从而并行执行；

//注：测试图片都是800*600的图片旋转到1004*1004的图片中心 测试成绩取各个旋转角度的平均速度值
//////////////////////////////////////////////////////////////////////////////////
//速度测试:    CPU: AMD64x2 4200+             
//==============================================================================
// PicRotaryThreeOrder_MMX_parallel2  87.6 fps
//==============================================================================

//////////////////////////////////////////////////////////////////////////////////
//速度测试:    CPU: Intel Core2 4400(2.00G)             
//==============================================================================
// PicRotaryThreeOrder_MMX_parallel2  89.3 fps
////////////////////////////////////////////////////////////////////////////////  

并行化的实现PicRotaryThreeOrder_MMX_parallel2比PicRotaryThreeOrder_MMX的44.2fps快了98.2%!  (Intel Core2 4400上快了94.6%)
在双核CPU上执行速度几乎是单核上的2倍!

B':一个通用的针对任意多核并行的一个简单实现
  有了上面的并行基础，我们来实现一个更加通用一些的版本；根据CPU核心数来动态分配任务；
  实现方式为直接按照扫描行来分配(但这样处理可能不利于内存的高效访问)，就懒得去估算任务量了:)

//注：测试图片都是800*600的图片旋转到1004*1004的图片中心 测试成绩取各个旋转角度的平均速度值
//////////////////////////////////////////////////////////////////////////////////
//速度测试: CPU: AMD64x2 4200+                
//==============================================================================
// PicRotaryThreeOrder_MMX_parallel   81.0 fps
////////////////////////////////////////////////////////////////////////////////  

//////////////////////////////////////////////////////////////////////////////////
//速度测试: CPU: Intel Core2 4400(2.00G)                
//==============================================================================
// PicRotaryThreeOrder_MMX_parallel   89.5 fps
////////////////////////////////////////////////////////////////////////////////   

 这个实现能应付大多数时候的并行需求了，包括以后的4核8核...

(注意:这里的并行任务分割方案仅仅是简单的举例(用了代码改动最小的方案)，你应该根据你的需求来更好的并行化你的任务； 如果分割后的单个任务太小，并行的优势可能就体现不出来，甚至于更慢；)

C:超大图片旋转优化

  1.使用PicRotary*、PicRotaryBilInear*、PicRotaryThreeOrder*等函数在旋转大图片的时候，会出现一个速度变慢问题：就是旋转不同的角度，速度差异巨大(甚至达到8倍以上！)

速度测试:
//注：CPU: AMD64x2 4200+(2.37G)
////////////////////////////////////////////////////////////////////////////////
//   800x600的源图片             各角度平均帧数     角度中最小帧数     角度中最大帧数
//==============================================================================
// PicRotarySSE2                  304.2 fps       250.7 fps       565.3 fps
// PicRotaryBilInear_MMX          100.2 fps        87.8 fps       130.3 fps
// PicRotaryThreeOrder_MMX         44.2 fps        41.4 fps        49.7 fps
////////////////////////////////////////////////////////////////////////////////  
//  3200x2400的源图片            各角度平均帧数     角度中最小帧数     角度中最大帧数
//==============================================================================
// PicRotarySSE2                   12.2 fps         4.6 fps        36.3 fps
// PicRotaryBilInear_MMX            5.0 fps         1.1 fps         8.7 fps
// PicRotaryThreeOrder_MMX          2.6 fps         0.9 fps         3.5 fps
////////////////////////////////////////////////////////////////////////////////  

//注：CPU: Intel Core2 4400(2.00G)
////////////////////////////////////////////////////////////////////////////////
//   800x600的源图片             各角度平均帧数     角度中最小帧数     角度中最大帧数
//==============================================================================
// PicRotarySSE2                  449.3 fps       250.5 fps       753.4 fps
// PicRotaryBilInear_MMX          109.5 fps        95.3 fps       132.4 fps
// PicRotaryThreeOrder_MMX         45.9 fps        41.5 fps        50.3 fps
////////////////////////////////////////////////////////////////////////////////  
//  3200x2400的源图片            各角度平均帧数     角度中最小帧数     角度中最大帧数
//==============================================================================
// PicRotarySSE2                   18.3 fps        12.0 fps        44.8 fps
// PicRotaryBilInear_MMX            6.7 fps         3.5 fps         8.7 fps
// PicRotaryThreeOrder_MMX          2.9 fps         2.2 fps         3.4 fps
////////////////////////////////////////////////////////////////////////////////  

  在我的AMD64下 4200+ CPU上800x600的源图片对旋转的角度不是很敏感，但当源图片为3200x2400的时候，最小速度和平均速度差异巨大；(Intel Core2 4400上稍好)

  2.先来分析一下问题出现的原因，对于某些角度(比如90度和270度)，按以前的函数实现，访问源图片内存的方式将是列方向的,当图片比较大的时候，内 存的读取访问将变得非常低效；一般CPU访问内存的时候都会一次性读取连续相邻的64字节放到缓存，但很明显对于某些角度，预读的大部分数据都没有用(甚 至只使用了其中的4个字节，浪费了60字节完全没有用就被新的数据挤出了缓存)；对于小缓存的CPU和较大的源图片，这种情况会更严重；
  能想到的一些解决方案：a.使用CPU的预读指令来手工预读数据，但是没有办法指定预读的内存块大小从而避免带宽浪费；而且以后的硬件趋势也只会朝一次读 取更大的块发展，所以该方案不可行；b.针对不同的角度方向分别编码，使读取的内存方向尽量按行方向(从而使预读生效)，比如靠近90度旋转的时候写内存 的方向将变为列方向，因为写内存指令中可以禁止写缓存，应该可以降低列写入带来的性能损失；该方案还有一个缺点是代码编写稍嫌麻烦:)  C:利用内存访问的局部性来使缓存的数据有效，就是分成小块来处理旋转算法，使内存访问在任何角度时都有相关性；

  3.分块局部性旋转算法的实现方案；
      
             以前的扫描算法图示                        新的分块扫描算法图示

     为了实现新的扫描路径，有一个简单的改进办法，把以前的扫描行(起始和结束位置)先保存起来，然后在处理这是扫描行；代码就很简单了，如下：
(没有给出的基础代码参见该系列的其他文章)

  4.近邻取样插值的分块扫描函数实现PicRotarySSE2_Block

  5.二次线性插值的分块扫描函数实现PicRotaryBilInear_MMX_Block
    这里比近邻取样的相应函数多出一些边界处理代码

  6.三次卷积插值的分块扫描函数实现PicRotaryThreeOrder_MMX_Block
   几乎就是拷贝PicRotaryBilInear_MMX_Block，然后稍做改动;
   (实际项目中的代码和文章中的代码还是有很多不同的，要是实际代码中也有这么多长篇长篇的拷贝然后稍作修改的代码，那就要疯了:)

 

  7.分块处理的旋转函数的速度测试:
//注：CPU: AMD64x2 4200+(2.37G)
////////////////////////////////////////////////////////////////////////////////
//   800x600的源图片             各角度平均帧数    角度中最小帧数    角度中最大帧数
//==============================================================================
// PicRotarySSE2                  304.2 fps       250.7 fps       565.3 fps
// PicRotarySSE2_Block            316.6  fps      255.5 fps       495.6 fps
// PicRotaryBilInear_MMX          100.2 fps        87.8 fps       130.3 fps
// PicRotaryBilInear_MMX_Block     99.5  fps       92.7 fps       122.3 fps
// PicRotaryThreeOrder_MMX         44.2 fps        41.4 fps        49.7 fps
// PicRotaryThreeOrder_MMX_Block   43.2 fps        41.3 fps        47.8 fps
////////////////////////////////////////////////////////////////////////////////  
//  3200x2400的源图片            各角度平均帧数    角度中最小帧数    角度中最大帧数
//==============================================================================
// PicRotarySSE2                   12.2 fps         4.6 fps        36.3 fps
// PicRotarySSE2_Block             19.2 fps        15.9 fps        33.3 fps
// PicRotaryBilInear_MMX            5.0 fps         1.1 fps         8.7 fps
// PicRotaryBilInear_MMX_Block      6.3 fps         5.8 fps         8.3 fps
// PicRotaryThreeOrder_MMX          2.6 fps         0.9 fps         3.5 fps
// PicRotaryThreeOrder_MMX_Block    2.9 fps         2.7 fps         3.4 fps
////////////////////////////////////////////////////////////////////////////////
 

//注：CPU: Intel Core2 4400(2.00G)
////////////////////////////////////////////////////////////////////////////////
//   800x600的源图片             各角度平均帧数    角度中最小帧数    角度中最大帧数
//==============================================================================
// PicRotarySSE2                  449.3 fps       250.5 fps       753.4 fps
// PicRotarySSE2_Block            351.3 fps       219.0 fps       436.3 fps
// PicRotaryBilInear_MMX          109.5 fps        95.3 fps       132.4 fps
// PicRotaryBilInear_MMX_Block    112.2 fps        98.1 fps       124.9 fps
// PicRotaryThreeOrder_MMX         45.9 fps        41.5 fps        50.3 fps
// PicRotaryThreeOrder_MMX_Block   47.7 fps        44.8 fps        50.1 fps
////////////////////////////////////////////////////////////////////////////////  
//  3200x2400的源图片            各角度平均帧数     角度中最小帧数     角度中最大帧数
//==============================================================================
// PicRotarySSE2                   18.3 fps        12.0 fps        44.8 fps
// PicRotarySSE2_Block             18.4 fps        15.5 fps        23.8 fps
// PicRotaryBilInear_MMX            6.7 fps         3.5 fps         8.7 fps
// PicRotaryBilInear_MMX_Block      7.3 fps         6.8 fps         8.3 fps
// PicRotaryThreeOrder_MMX          2.9 fps         2.2 fps         3.4 fps
// PicRotaryThreeOrder_MMX_Block    3.2 fps         2.9 fps         3.4 fps
////////////////////////////////////////////////////////////////////////////////
 

测试更大的源图片(6400x4800)或者CPU的缓存越小的时候*_Block优化版本优势越明显!