基于内容划分和傅里叶分析的图像缩放算法

朱 运，沈一帆，姜 昊

（复旦大学 计算机科学技术学院，上海200433）

0 引 言

保持图像重要内容和视觉连贯性是图像缩放算法的两个重要要求。传统的图像缩放方法包括比例变化（scaling）和裁剪（cropping），但是它们各有各的缺点。非等比例的缩放会造成图像中的物体变形失真，而裁剪虽然可以避免变形失真，但是它需要用户交互信息，并且会丢失图像中次重要的信息。这两种算法都难以满足人们对图像缩放的要求。因此人们提出了基于内容的图像缩放技术，其主要步骤为：①检测原图像中的显著性区域；②根据显著性区域选择合适的缩放算子。主要的缩放算法一般可以分为两类：一类是以Seam Carving算法为代表的离散型缩放算子，该类方法利用贪心算法逐步删除或复制图像中不重要的seam，直至达到指定的缩放尺寸；另一类是以变形技术（Image Warping）为代表的连续型缩放算子，该类方法将图像视为连续的区域，将缩放过程视为原图像区域通过几何形变直至指定形状的过程。前者算法简洁，计算效率较高，但容易产生人工痕迹，出现视觉瑕疵；后者计算开销较大，且容易产生局部比例失调的现象。因此，寻找高效且广泛适用的基于内容的图像缩放算法依然是计算机图像处理方向的研究热点。

本文在此提出了一种结合基于内容自适应划分和傅里叶分析的图像缩放算法，它综合考虑了图像的视觉显著性、语义信息和结构信息，将图像划分为多个子图，并根据其视觉重要度自适应性地采样，较好地保护了图像中的重要内容和全局框架，有效地避免了视觉失真，实验证明了该算法的有效性。

1 相关研究

Shamir和Sorkin在文献［1］总结了图像缩放算法的三条原则：①缩放后的图像必须保持原图像中的重要内容；②缩放后的图像必须保持原图像中的结构信息；③缩放后的图像必须避免视觉失真。但这三条原则却往往存在矛盾，例如对于指定的缩小尺寸，保护重要区域则意味着删除更多的非重要区域像素，而这往往会造成视觉失真，因此现有的图像缩放算法只能尽量地满足该三条原则并取得某种平衡。

文献［2］提出了开创性的Seam Carving算法，该算法每次删除和复制图像中能量最小的seam直至到达指定大小，它可以有效地保护图像中的重要内容，但是对于包含复杂场景和显著结构的图像，其缩放处理效果则不尽如人意。文献［3］对其做了改进，利用k－means对图像进行划分，加速了Seam Carving中求最小能量seam的动态规划过程。文献［4］提出了最早的非均匀变形（warping）算法，该算法对原图像中重要区域等比缩放，而非重要部分则根据缩放尺寸进行调整，因此往往造成非重要区域变形失真。文献［5］则将图像划分为多个网格，对不同的网格应用不同的变形操作，并定义视觉损失能量函数以衡量变形操作所造成的失真程度，将形变过程转换为求解带有限制条件的函数优化问题，但该算法计算开销非常大，且存在局部比例失调的现象。文献［6］将图像缩放看成采样过程，根据对图像重要度的扩散和平滑确定采样因子。文献［7］利用频域分析对图像进行缩放，但它只考虑了图像的结构信息，而容易造成图像内容区域变形。文献［8］利用滤波的思想，将原图像中像素位移量视作其显著度的积分，其缩放效果依赖于其显著度图检测效果。

根据图像缩放算法的三条原则，本文提出了基于内容划分和傅里叶分析的图像缩放算法。首先计算了输入图像的重要度图，该重要度图包含了视觉显著度信息，图像语义信息和全局结构信息。然后根据重要度图将图像转换为一维离散信号，并且通过对该信号的分析将原图像自适应地划分为多个子图。接着利用傅里叶变换和频域分析确定每个子图缩放的比例。最后根据其缩放比例对每个子图进行下采样，最终获得指定尺寸的缩放图像。

2 算法流程

不失一般性，本文假设只对图像进行水平方向上的缩放（因为垂直方向上的缩放可以通过相同算法类推获得）。因此图像缩放过程可以表示为：对于分辨率为m×n的原图像I以及分辨率为m′×n′的目标图像I′（其中m＝m′，n′＜n），希望找到这样一个映射函数f：I→I′，使得：①目标图像I′尽可能地保全原图像I中的重要内容；②目标图像I′尽可能地保全原图像I中的重要结构；③目标图像I′尽可能地避免视觉失真。

2.1 重要度图

为了保护图像中的重要内容和结构信息，本节定义了重要度图来衡量原图像中每个区域对于观察者的重要程度。重要度图是和原图像大小相等的二维矩阵，其中每一项的值反映了原图像中对应像素点处的重要程度，取值为［0，1］。根据人类视觉的特征，通常认为图像中的视觉显著区域，语义信息区域和结构信息区域是重要区域，因此本节对这3种类型区域分别进行了检测，并最后合并计算出原图像的重要度图。

根据人类视觉模型，利用颜色，亮度和方向等底层视觉特征在不同尺度上的对比程度来检测图像的显著度，可以较好地提取图像中人眼敏感的视觉显著区域，其结果记做Si。

为了识别图像中的内容信息，文献［9］提出了基于上下文的显著度（context－aware saliency）检测算法，通过计算每个图像块（patch）和与其最相似的K个图像块在颜色域和空间域上的距离来检测图像的显著度，并根据Gestalt法则（即人类视觉焦点总是接近的）对其进行了修正，它可以有效地提取体现图像语义和内容信息的区域。因此，本文应用该算法计算原图像中的语义信息区域，其结果记做Sc。

梯度表示图像中的边缘信息，可以用来衡量原图像中的结构信息区域。本文使用Sobel算子计算其梯度图，其表达式为

综上，输入图像的重要度图S可以表示为

式中：α，β、γ——比例系数，在本文实验中α＝0.6，β＝0.6，γ＝0.2。

图1是图像woman的重要度图。其中图1（a）是输入图像，图1（b）是视觉显著度图，图1（c）是应用文献［9］算法得到的语义显著度图，图1（d）是梯度图，即结构显著度图，图1（e）是最终的重要度图。可以看到该重要度图能够较好地体现原图像中的视觉显著性信息，语义信息以及整体结构信息，图中较亮的部分反映了人眼对图像woman最为关注的区域。

2.2 划 分

由于对同一个物体或区域应用不同的缩放比例会导致视觉变形失真，为了避免该情况，需要对相同的物体或区域尽量应用相同的缩放比例。因此，根据第2.1节计算得到的重要度图对输入图像进行划分，将相同的物体和重要区域尽可能地划分到同一个子图中，使得可以对子图应用相同的缩放算子。自适应内容划分算法的步骤如下：

首先，将输入图像的重要度图S通过式（3）转换为长度为n的一维离散信号C

图1 图像woman的重要度图

式中：c（x）——横坐标为x的所有像素点在垂直方向上的重要度的平均值。该信号反映了输入图像在水平方向上的重要度分布。

然后，使用双边滤波器对C进行滤波。双边滤波器可以保护一维信号震荡强烈的区域，而对信号中震荡不那么剧烈的区域进行平滑，因此可以较好地在保护不同重要区域边界的同时降低重要区域内部像素的重要度差异，提高划分的准确度。

接着，应用动态规划方法对C进行自适应划分，其具体步骤如下。

（1）初始化对C的划分。首先将C平均地划分为K个子信号，每个子信号的长度为m／K，在本文实验中K取10。此处用向量B来描述一个划分，其中B＝（b1，b2，...，bK＋1），bk和bk＋1分别为第k个子信号左边界和右边界的坐标。对于初始划分B，bk＝kn／K，且b0＝1，bK＋1＝n。

（2）根据式（4）动态地更新每一个bk

式中：sk－1、sk——分割点bk左边和右边的子信号内部重要度的平均值。式（5）的前两项表示分割点bk左右两边的子信号内部重要度差异，而第三项表示这两个子信号之间的重要度差异。而式（4）表示在固定bk－1和bk＋1的情况下，寻找一个最优的bk使得两边的子信号内部重要度差异尽可能地小，而不同子信号之间的重要度差异尽可能地大（即寻找使得能量函数J最小的bk），其中参数α是用来确保子信号最小宽度，本文实验中α取5。

（3）合并相似子信号。由于初始定义的子信号个数K可能远远大于图像中重要区域的数量，可能导致将某个重要区域划分到不同的子图中，因此需要在根据图像的内容自适应地调整图像划分的数量。当划分向量B中的所有项更新完毕时，先检测其是否收敛：如果收敛，则转向步骤4）；否则，逐步检测相邻的两个子信号之间平均显著度的差异｜sk－sk－1｜，如果该差异小一定的阈值时，则将两个子信号合并，然后转到步骤（2），在本文实验中，该阈值取。

（4）根据对一维信号C的划分对输入图像I进行划分。

图2是图像woman的划分效果图。其中图2（a）是输入图像，图2（b）是未使用合并的划分效果图，图2（c）是使用合并的划分效果图。可以看到在未使用合并的划分中，图像中的重要区域（人的头和腿）被划分到了不同的子图中；而在使用合并的划分中，图中的女人被较好地划分到了一个子图中，且其划分结果符合该输入图像的整体结构。

图2 划分效果

2.3 缩 放

对于被划分为多个子图的输入图像，需要根据每个子图的重要度信息决定其缩放因子，使得非重要区域缩放的像素更多一些，而重要区域尽可能保持不变。假设lk是第k个子图的宽度，而rk表示该子图需要删除的列个数，因此每个子图的采样率为。

每个子图中的重要度分布情况可以用一维的离散信号Ck来描述，其定义类似式（3），而删除子图中列的过程可以视为对该信号进行下采样的过程。而下采样过程中，该信号损失的是其高频部分，即图像中的细节信息，因而导致该信号或图像失真，因此需要最小化其能量损失。在本文中使用指数函数来模拟该一维离散信号，其中sk的定义见式（6）。对该信号进行傅里叶变换，其高频部分损失的能量为

而所有子图经过下采样造成的高频部分能量损失可以表示为

我们用式（8）中能量作为衡量是视觉连贯性损失的能量函数（visual distortion energy function）。因此，需求出使得该能量函数值最小的rk，且rk需要满足限制条件

该问题等价于带有限制条件的能量优化问题，可以使用拉格朗日乘数法，即对函数

对rk求导，使其偏导数等于0，得到的结果为

最后根据rk对所有子图进行均匀下采样，从而得到最终的缩放结果。

3 实验和结果

为了测试本文算法的性能，本文在CPU为Pentium（R）4 2.00GHz和内存为3G的PC上进行了仿真实验，编程语言采用的是matlab r2011a，而作为对比的算法是Seam Carving和文献［4］中的算法。在将分辨率为700×1024的输入图像缩小至分辨率为700×512的目标图像的过程中，Seam Carving算法平均耗时24s，文献［4］中的算法平均耗时13s，而本文中的算法平均耗时0.7s，可以看出该算法的计算效率优于Seam Carving和文献［4］中的缩放效率。这主要是因为该算法计算完输入图像的重要度图后，所有的频域分析和缩放操作都是投影到一维向量空间进行操作的，大大地减少了计算开销。

同时为了测试本文的性能，将本算法应用于文献［10］中提出的图像缩放标准数据库，并与Seam Carving算法，裁剪算法和文献［4］中算法的缩放效果进行比较。图3是应用不同缩放算法所得的缩放效果图。其中图3（a）是输入图像，图3（b）是应用了Seam Carving算法的结果，图3（c）是应用了裁剪算法的结果，图3（d）是应用了文献［5］中缩放算法的结果，图3（e）是本文算法的结果，以上算法的缩放比例均为50%。从实验结果中可以看到：Seam Carving算法逐次删除图像中的不重要seam，但在图像中可供删除的不重要seam数量不足以让原图像缩放至指定尺寸的情况时，依然按照贪心算法删除重要区域的seam而不考虑这些重要区域的全局信息，无法保护其视觉连贯性，例如图3（a）中小孩的脸，在缩放过程中产生了严重的视觉变形；裁剪算法选取最优的裁剪窗口，虽然不会产生变形，但无法传递原图像的整体信息，不可避免地会造成图像信息丢失，例如图3（b）中小孩和雪人各被裁剪掉了一部分；文献［5］中通过非均匀的变形算法获得缩放图像，虽然可以保全原图像的整体结构信息和重要区域，但由于对非重要区域的形变是只加有缩放尺寸的限制而无其它约束条件，因而容易造成不同区域间物体的缩放比例不协调，例如图3（d）中小孩的脸和身体就比例失调了。而本文中的算法充分考虑输入图像的视觉显著性信息、内容语义信息和全局结构信息，因而可以较好地保护输入图像中的重要区域和结构信息，且根据其重要度信息进行划分采样，使得同一重要区域应用同样的采样率和采样方法，从而保持目标图像的视觉连贯性，在效果图3（e）中，图像中的重要区域（小孩和雪人）的比例基本保持协调，原图像的整体架构也得到了保护，其产生的视觉失真远小于其它几种算法。

图3 缩放效果

4 结束语

本文提出了一种基于内容划分和傅里叶分析的图像缩放算法。首先根据缩放算法3个原则，建立了结合了视觉显著信息，语义信息，结构信息的重要度图。接着根据该重要度图，对输入图像进行动态地划分，使得不同的重要区域被划分到不同的子图中。最后，根据傅里叶变换和频域分析确定每个子图的采样率并对之进行下采样，从而得到最终的目标图像。与同类的seam carving，裁剪等算法相比，该算法的计算效率较高，并且较好地在保护原图像的重要区域和结构的同时，避免了视觉上的变形和失真现象。在引入帧差异信息的情况下，该算法可以拓展到视频缩放处理领域。

［1］Shamir A，Sorkine O.Visual media retargeting［C］／／SIGGRAPH ASIA.Yokohama，Japan：ACM，2009.

［2］Avian S，Shamir A.Seam carving for content－aware image resizing［J］.ACM Transactions on Graphics，2007，26（3）：267－276.

［3］WANG Huiqian，YANG Gaobo，ZHANG Zhaoyang，et al.Fast image resizing by combining with saliency map and adaptive seam［J］.Application Research of Computers，2010，27（9）：3594－3597（in Chinese）.［王会千，杨高波，张兆扬，等.结合显著度图和自适应能量线的快速图像缩放［J］.计算机应用研究，2010，27（9）：3594－3597.］

［4］Wolf L，Guttmann M，Cohen－or D.Non－homogeneous content－driven video－retargeting［C］／／Proceedings of the 11th IEEE International Conference on Computer Vision.Rio de Janeiro，Brazil：IEEE Computer Society，2007.

［5］ Wang Yu－Shuen，Tai Chiew－Lan，Sorkine O，et al.Optimized scale－and－stretch for image resizing［J］.ACM Transactions on Graphics，2008，27（5）：1－8.

［6］WANG Huiqian，YANG Gaobo，ZHANG Zhaoyang，et al.Image and video resizing algorithm based on importance diffusion and adaptive scaling［J］.Journal on Communications，2011，32（8）：166－170（in Chinese）.［王会千，杨高波，张兆扬，等.基于重要度扩散和自适应采样的图像／视频缩放技术［J］.通信学报，2011，32（8）：166－170.］

［7］Kim Jun－Seong，Kim Jin－Hwan，Kim Chang－Su.Adaptive image and video retargeting technique based on fourier analysis［C］／／Proceedings of the 22th IEEE Confe－rence on Computer Vision and Pattern Recognition.Florida，USA：IEEE Computer Society，2009.

［8］Ding Yuanyuan，Xiao Jing，Yu Jingyi.Important filtering for image retageting［C］／／Proceedings of the 24th IEEE Conference on Computer Vision and Pattern Recognition.Colorado Springs，USA：IEEE Computer Society，2009.

［9］Stas Goferman，Lihi Zelnik－Manor，Ayellet Tal.Context－aware saliency detection［C］／／Proceedings of the 23th IEEE Conference on Computer Vision and Pattern Recognition.San Francisco，USA：IEEE Computer Society，2010.

［10］Rubinstein M，Gutierrez D，Sorkine O，et al.A comparative study of image retargeting［J］.ACM Transactions on Graphics，2010，29（6）：1－9.