图形图像处理－之－高质量的快速的图像缩放下篇三次线性插值和MipMap链

忘是亡心i 2022-06-12 11:47 150阅读 0赞

转自 [http://blog.csdn.net/housisong/article/details/1528392][http_blog.csdn.net_housisong_article_details_1528392]

图形图像处理－之－高质量的快速的图像缩放 下篇 三次线性插值和MipMap链  
                     [HouSisong@Gmail.com][HouSisong_Gmail.com]   2007.03.13

tag:图像缩放,速度优化,定点数优化,近邻取样插值,二次线性插值,三次线性插值,  
   MipMap链,三次卷积插值,MMX,SSE优化,CPU缓存优化

摘要:首先给出一个基本的图像缩放算法，然后一步一步的优化其速度和缩放质量；

高质量的快速的图像缩放 全文 分为:  
     上篇 近邻取样插值和其速度优化  
     中篇 二次线性插值和三次卷积插值  
     下篇 三次线性插值和MipMap链

补充 使用SSE2优化

正文：

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

![yu.JPG][]  ![zoom1yu0.4.JPG][]        ![zoom1yu0.2.JPG][]          ![zoom1yu0.1.JPG][]   
           原图          近邻取样 缩放到0.4倍     缩放到0.2倍     缩放到0.1倍

![zoom2yu0.4.JPG][]         ![zoom2yu0.2.JPG][]          ![zoom2yu0.1.JPG][]  
                     二次线性插值 缩放到0.4倍     缩放到0.2倍     缩放到0.1倍

![zoom3yu0.4.JPG][]         ![zoom3yu0.2.JPG][]          ![zoom3yu0.1.JPG][]  
                     三次卷积插值 缩放到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链图片的储存方案:

![yuMipMapTruePic.JPG][]  
                    MipMap链图片示意图           
                     
               ![yuMipMapPic.JPG][]              
         可能的一种物理储存方案(我对每张图片加了一个边框)

D: 定义MipMap数据结构:  
   MipMap数据结构可以定义为一个TPicRegion数组和该数组的大小；   
   (MipMap图片的储存参见上面的图示)  
  比如:

\#include <vector>  
     typedef std::vector <TPicRegion>  TMipMap;  
     //其中，第一个元素TMipMap\[0\]指向原始图片，后面的依次为缩小图片；

E: MipMap的选择函数和偏好:  
    在进行缩放时，根据目标图片缓冲区的大小来动态的选者MipMap中的一幅图片来作为源图片；这就需要一个  
选择函数；比如:

long SelectBestPicIndex(const TMipMap& mip,const long dstWidth,const long  dstHeight)  
\{  
    long oldS=mip\[0\].width\*mip\[0 \].height;  
    long dstS=dstWidth\* dstHeight;  
    if ( (dstS>=oldS) || (mip.size()==1 ) )  
        return 0 ;  
    else if (dstS<=1 )  
        return mip.size()-1 ;  
    else  
         return (long)(log(oldS/dstS)\*0.5+0.5 );  
\}

选择函数可以增加一个偏好参数：  
mip选择偏好：0.5没有偏好，靠近0偏向选择小图片，靠近1偏向选择大图片(质量好一些)

float public\_mip\_bias=0.5; //\[0..1\]    
  
long SelectBestPicIndex(const TMipMap& mip,const long dstWidth,const long  dstHeight)  
\{  
    long oldS=mip\[0\].width\*mip\[0 \].height;  
    long dstS=dstWidth\* dstHeight;  
    if ( (dstS>=oldS) || (mip.size()==1 ) )  
        return 0 ;  
    else if (dstS<=1 )  
        return mip.size()-1 ;  
    else  
         return (long)(log(oldS/dstS)\*0.5+ public\_mip\_bias);  
\}

F:利用MipMap后的缩放效果:

![MipMapzoom1yu0.4.JPG][]           ![MipMapzoom1yu0.2.JPG][]         ![MipMapzoom1yu0.1.JPG][]    
                 MipMap+近邻取样 缩放到0.4倍     缩放到0.2倍     缩放到0.1倍  
               (利用MipMap做一次近邻取样)

![MipMapzoom2yu0.4.JPG][]           ![MipMapzoom2yu0.2.JPG][]          ![MipMapzoom2yu0.1.JPG][]  
              MipMap+二次线性插值 缩放到0.4倍     缩放到0.2倍     缩放到0.1倍  
              (利用MipMap做一次二次线性插值)

![MipMapzoom3yu0.4.JPG][]           ![MipMapzoom3yu0.2.JPG][]          ![MipMapzoom3yu0.1.JPG][]  
              MipMap+三次卷积插值 缩放到0.4倍     缩放到0.2倍     缩放到0.1倍  
              (利用MipMap做一次三次卷积插值)

G: 在MipMap的两张图片之间插值:  
  选择MipMap的时候，同时可以选择相邻的两张MipMap图片；分别进行插值算法后得到两个颜色结果；  
对两个MipMap图片产生的评价值可以作为这两个颜色的插值权重，得到最终的颜色插值结果；优点是  
缩放效果好，避免跳跃;缺点是速度慢:)

选择和权重函数的一个可能实现：

struct  TMipWeight \{  
  long   BigMip;  
  long   SmallMip;  
  float BigMipWeight;//\[0..1\]   
 \};  
  
TMipWeight SelectBestPicIndexEx(const TMipMap& mip,const long dstWidth,const long  dstHeight)  
\{  
    long oldS=mip\[0\].width\*mip\[0 \].height;  
    long dstS=dstWidth\* dstHeight;  
    TMipWeight result;  
    if ( (dstS>=oldS) || (mip.size()==1 ) )  
    \{  
        result.BigMip=0 ;  
        result.SmallMip=0 ;  
        result.BigMipWeight=1.0 ;  
    \}  
    else if (dstS<=1 )  
    \{  
        result.BigMip=mip.size()-1 ;  
        result.SmallMip=mip.size()-1 ;  
        result.BigMipWeight=1.0 ;  
    \}  
    else  
    \{  
         float bestIndex=log(oldS/dstS)\*0.5+0.5; //or + public\_mip\_bias   
         result.BigMip=(long )bestIndex;  
        if (bestIndex==mip.size()-1 )  
        \{  
            result.SmallMip=mip.size()-1 ;  
            result.BigMipWeight=1.0 ;  
        \}  
        else  
        \{  
            result.SmallMip =result.BigMip+1 ;  
            result.BigMipWeight=1.0-(bestIndex- result.BigMip);  
        \}  
    \}  
    return  result;  
\}

H:MipMap间插值效果:

![MipMap2zoom1yu0.4.JPG][]         ![MipMap2zoom1yu0.2.JPG][]          ![MipMap2zoom1yu0.1.JPG][]  
              MipMap+两次近邻取样 缩放到0.4倍     缩放到0.2倍     缩放到0.1倍  
              (利用MipMap做两次近邻取样输出两个值，然后线性插值为最终结果)

![MipMap2zoom2yu0.4.JPG][]        ![MipMap2zoom2yu0.2.JPG][]           ![MipMap2zoom2yu0.1.JPG][]  
                     三次线性插值 缩放到0.4倍     缩放到0.2倍     缩放到0.1倍  
             (三次线性插值:利用MipMap做两次二次线性插值输出两个值，然后线性插值为最终结果)    
                     
                              ![MipMap2zoom3yu0.4.JPG][]       ![MipMap2zoom3yu0.2.JPG][]           ![MipMap2zoom3yu0.1.JPG][]  
           MipMap+两次三次卷积插值 缩放到0.4倍    缩放到0.2倍     缩放到0.1倍  
         (利用MipMap做两次三次卷积插值输出两个值，然后线性插值为最终结果)

(图像缩放系列终于写完了，计划中写图像任意角度的高质量的快速旋转、Alpha图片混合等，尽请期待:)

(ps: 思考中的一个图片压缩方法：利用MipMap来压缩图像数据;输入一张图片，然后生成MipMap链，保存相邻之间图片的差(数值差可能很小，很容易找好的算法压缩得很小)和最顶的一张图片(一个点)；  解压的时候依次求和就得到原图片了；  该算法为无损压缩，适合于人物风景等过渡比较多的图片的压缩，不太适合线条类等相邻间颜色变化剧烈的图片；)

[http_blog.csdn.net_housisong_article_details_1528392]: http://blog.csdn.net/housisong/article/details/1528392
[HouSisong_Gmail.com]: mailto:HouSisong@Gmail.com
[yu.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/yu.JPG
[zoom1yu0.4.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/zoom1yu0.4.JPG
[zoom1yu0.2.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/zoom1yu0.2.JPG
[zoom1yu0.1.JPG]: /images/20220612/3fda1cc718e9427984c6054441a3ccb0.png
[zoom2yu0.4.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/zoom2yu0.4.JPG
[zoom2yu0.2.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/zoom2yu0.2.JPG
[zoom2yu0.1.JPG]: /images/20220612/e81bfc026dd34b8089cbf9e1c3f8c910.png
[zoom3yu0.4.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/zoom3yu0.4.JPG
[zoom3yu0.2.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/zoom3yu0.2.JPG
[zoom3yu0.1.JPG]: /images/20220612/1fff24469c114eb49a7ec88f5c22902a.png
[yuMipMapTruePic.JPG]: /images/20220612/fc745cec42974045a60d43755b19fb48.png
[yuMipMapPic.JPG]: /images/20220612/4da7ec87ac894422a7e42a7e62351e72.png
[MipMapzoom1yu0.4.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMapzoom1yu0.4.JPG
[MipMapzoom1yu0.2.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMapzoom1yu0.2.JPG
[MipMapzoom1yu0.1.JPG]: /images/20220612/716d5ef790a6468d9fdc69e712938238.png
[MipMapzoom2yu0.4.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMapzoom2yu0.4.JPG
[MipMapzoom2yu0.2.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMapzoom2yu0.2.JPG
[MipMapzoom2yu0.1.JPG]: /images/20220612/b1e136ba3c1849f19b7f175be980b242.png
[MipMapzoom3yu0.4.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMapzoom3yu0.4.JPG
[MipMapzoom3yu0.2.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMapzoom3yu0.2.JPG
[MipMapzoom3yu0.1.JPG]: /images/20220612/7353fdb0caf0410db6e50218c862ffd7.png
[MipMap2zoom1yu0.4.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMap2zoom1yu0.4.JPG
[MipMap2zoom1yu0.2.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMap2zoom1yu0.2.JPG
[MipMap2zoom1yu0.1.JPG]: /images/20220612/1af0e531f59c459793b9713443cd4be8.png
[MipMap2zoom2yu0.4.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMap2zoom2yu0.4.JPG
[MipMap2zoom2yu0.2.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMap2zoom2yu0.2.JPG
[MipMap2zoom2yu0.1.JPG]: /images/20220612/213e63b2c78243739b4ec59e3073de48.png
[MipMap2zoom3yu0.4.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMap2zoom3yu0.4.JPG
[MipMap2zoom3yu0.2.JPG]: https://p-blog.csdn.net/images/p_blog_csdn_net/housisong/MipMap2zoom3yu0.2.JPG
[MipMap2zoom3yu0.1.JPG]: /images/20220612/7bc7c25c1d46422b95ac24dd9fd93abc.png