快速缝翘曲图像重定向算法

赵 亮，杜振龙，彭宏京

(南京工业大学 计算机科学与技术学院，江苏 南京 211816)

0 引 言

如今，硬件显示设备的多样性给信息呈现带来了新的挑战，特别是在图像显示领域。要使图像具有不同的显示功能，我们需要调整图像的大小以适应不同的屏幕。图像重定向就是解决这一问题的一种技术。它适用于在不同屏幕大小和高宽比的显示设备上有效地查看图像，而不会失去图像本身的意义[1]。

随着图像重定向需求的不断增加，人们提出了多种图像重定向方法。从传统方法(如：uniform scaling和cropping)到基于图像内容的方法(如：seam carving[2,3]和warping)；然而，传统方法由于忽略了图像的内容，往往不能得到满意的目标图像。与传统的方法相比，基于内容感知的图像重定向方法虽然能很好地保护图像的内容，适用于图像高宽比变化等图像处理应用，但是也会出现算法处理速度慢、自适应焦点区域检测不精确等问题，进一步影响目标图像的视觉效果。

针对这些问题，我们提出了一种快速缝翘曲(FSW)的图像重定向方法。该方法结合了warping和seam carving的技术，以一种各相邻行(列)像素间的最优匹配关系对传统seam carving方法的寻缝方案进行改进，并通过一种与人类感知更相关的能量图的指导更精确地寻找高能量缝。以上两点的改进就可以快速、精确地进行自适应焦点区域检测。然后根据最优高能量缝对图像进行翘曲变换得到目标图像。该方法有3个明显的优点：①通过优化能量图生成方案，使得焦点区域的定位更准确，进一步更好保留重要的图像内容；②通过最优匹配关系来优化最优高能量缝的寻找方案，大大减少了算法的复杂度，使得方法变得快速、高效；③保留了基于warping方法的优点，同时也克服了seam carving方法的本质局限性，既强调图像的重要内容，又不完全丢弃不重要的内容。通过以上的改进，可以保证目标图像具有良好的视觉效果。

1 相关工作

一般地，有效的图像重定向方法通常有两个目标：①尽可能保存图像内容重要区域的信息；②尽可能减少图像内容重要区域的语义信息丢失。这些方法被统称为内容感知的图像重定向方法。近年来，不同类型的内容感知图像重定向技术得到了发展，如：seam carving方法[2,3]、内容感知的cropping方法[4,5]、基于分割的方法[6]、基于块的方法[7,8]、基于warping的方法[9,10]和多种操作符方法[11,12]。所有的这些方法都有各自的优点和局限性，一些经典方法的局限性如图1所示。由于考虑到本文的研究重点，我们只综述了其中两个方面的经典方法：seam carving和warping。

1.1 Seam carving

Seam carving是一种目前流行的内容感知的图像重定向方法，这是由Shai Avidan和Ariel Shamir[2]提出的。为了缩小图像大小，该方法一般是通过去除一个最小重要性值的缝，将图像的宽度或高度重复减少一个像素。一条缝被定义为从上到下或从左到右，每一行或每列只包含一个像素的8连通的像素路径。Seam carving是通过计算重要性图得到的能量来指导最小能量缝的寻找，而重要性图通常是由梯度能量计算得到。当一条缝被删除后，图像需要通过往左或往上移动一个像素进行调整，以补偿已删除的缝；因此，该图像无论在宽度或高度将会缩小一个像素。图像只在缝所在区域发生变化，而其它区域则保持不变。利用动态规划方法计算得到了最优缝，并给出了一种通过选择最优的垂直缝或水平缝对二维尺寸进行调整的算法。

大多数情况下，seam carving方法都能取得令人满意的效果。然而，使用这种方法可能会导致目标图像变成不完整的图像，因为删除的缝会破坏图像的完整性。删除缝的数量越多，这种重定向后图像不完整的问题就越严重；这种问题对图像的整体理解至关重要，有时目标图像可能会显示出一些视觉效果上无法接受的扭曲或失真，如图1(b)所示。此外，为该方法寻找合适的能量函数也是一个巨大的挑战。

图1 经典方法的局限性(图宽缩小50%)

后续也提出了seam carving方法的许多改进措施。Rubinstein 和Shamir等[3]引入一个前向能量准则，该准则规定最佳被删除的缝即是其被删除后能够引入最小能量的缝。该标准处理的事实是，由于以前不相邻的像素点成为相邻像素点，seam carving实际上可能会在重要性图中引入更多的能量。Shao等[13]提出了一种基于立体视觉注意引导接缝雕刻的立体图像重定向方法。通过将2D显著度图和深度显著图相结合来生成立体显著图，并通过考虑双眼视差双目和双眼正视差(BJND)来生成显著能量图。Shafieya等[14]则提出了一种新颖的能量函数，该函数结合了显著图、深度图和梯度图的信息；还提出了一种算法，可以为每个输入图像自适应分配适当的权重给这3个重要性图。然后根据能量图计算切换阈值，该阈值确定何时应用seam carving或scaling。Feng和Wen等[15]提出了一种基于颜色和空间信息的图像显著性检测算法。使用基于图像的SLIC方法，融合图像的颜色和空间信息以计算区域的显著特征，在一定程度上分离前景和背景。防止了背景区域被错误检测，得到了满足人类视觉注意力机制的检测结果。

这些改进在一定程度上提高了目标图像的视觉效果，但是seam carving方法存在的可能导致目标图像不完整的内在问题还是没有得到彻底的解决。虽然seam carving方法有其固有的缺陷，但是它的缝寻找的方法启发了我们改进我们的工作。

1.2 Warping

Warping是目前另一种流行的内容感知的图像重定向方法。这种方法使用合适的变形函数来保存ROI区域(即：感兴趣区域，图像的重要区域)，同时达到重定向图像的效果。最早Liu和Gleicher等[16]提出以这种方法在得到目标图像的同时达到ROI区域失真最小化、非ROI区域允许失真的效果。与其它重定向方法相比，基于warping的方法在不丢失图像信息的情况下可以得到更平滑的结果，即：目标图像中包含图像的“焦点+上下文语义信息”。基于变形函数目标对象的类型，现有的基于warping的方法可以被分类为3个类：①基于图像网格的方法[10]；②基于图像区域的方法[17,18]；③基于图像像素点的方法[19]。所有这些方法都面临着一个共同的问题，即：如何在源图像中准确找到ROI区域。这是一个被称为自动聚焦检测的难题。另外，warping算法的选择也是非常重要的。

如果检测到的ROI区域不准确，或者warping算法不合适，就会严重影响目标图像的视觉效果，如图1(c)所示。目前，大多数研究人员选择显著性方法作为自动聚焦检测的一种方法。Itti等[20]提出了最经典的基于显著性的视觉注意模型，目前已经应用于许多领域。该模型利用颜色、亮度、方位等特征，并通过分析和合并最终形成显著性图。随后Achanta等[21]提出了一种基于Itti视觉注意模型的改进模型方法。将整个图像作为参照的邻域，显著的区域和对象在视觉上相对于它们的相邻区域来说是非常突出的。这项工作的目的是根据其颜色和亮度计算每个像素相对于其邻域的突出程度或显著性。大多数显著性检测方法都采用类似的中心-周围对比方法。做出的关键决定是用于计算显著性的邻域面积的大小。

这些方法和改进方法在一定程度上提高了自动对焦检测的精度，但是对于图像重定向问题，我们还需要进一步的改进，以提高目标图像的视觉效果。要做到这一点，一方面我们需要寻找一种更合适的自动焦点检测方法，另一方面我们需要对现有的warping算法进行改进和优化。

2 提出的方法

针对seam carving方法本质上的缺陷和基于warping方法所需要的改进，我们提出了一种快速缝翘曲(FSW)的图像重定向方法。我们提出的图像重定向的方法包括两个关键环节：自动焦点检测和缝翘曲。这大致可分为3个步骤：①通过我们制定的找缝方案可以快速找到最优的高能量缝；②通过得到的最优高能量缝并对其进行调整，得到所有高能量缝阵列，构成焦点区域；③通过缝翘曲，将源图像重定向到目标图像。前两个步骤可以高效地解决自动焦点检测的困难，最后一步可以很好解决离散方法本质上的缺陷，保证目标图像的完整性和一致性。

2.1 快速寻找最优高能量缝方案

传统的seam carving方法[2]首先计算图像中每个像素的能量，然后再进行调整大小。能量代表像素的重要性，Avidan和Shamir提出一种简单且高效的能量计算方式，以图像梯度为能量函数来衡量图像中每个像素的能量，如式(1)所示

(1)

在定义了每个像素的能量之后，他们采用动态规划方法，以寻找最小能量的缝。以垂直缝为例，当找到最后一行最小能量像素时，他们再从这个像素回溯，以获得一个最优的垂直缝。

而上述的最优缝寻找方案存在两点局限性：①单一地使用图像梯度为能量图来指导后续缝的搜索工作会存在一些缺陷(如：忽略图像颜色信息、噪声敏感)，从而进一步导致一些重要同质区域大面积失真，如图1(b)所示；②虽然使用动态规划方法来寻找最优缝是有效的，但速度太慢，找到所有垂直或水平缝需要O(m2n) 或O(n2m) 的时间复杂度，大幅减缓了整个算法的运行速度。

针对这两点局限性，我们提出了一种快速寻找最优高能量缝的方案。我们大致将它分为两个小节来介绍：优化的能量图和快速寻找最优高能量缝。

2.1.1 优化的能量图

与文献[22]中相似，我们没有直接使用梯度幅度，而是使用了与人类感知更相关的能量图。首先采用一个决策过程，由它决定使用显著图与否；决策过程主要是一个简单的比较

(2)

其中

图2 优化的重要性图的组成

图3 优化的能量

2.1.2 快速寻找最优高能量缝

当我们有了源图像的能量图时，就可以根据每个像素的能量得到一条最优的高能量缝。传统的seam carving方法采用动态规划的方法来寻找最优的缝，虽然有效，但是十分耗时。此处我们就提出了一种快速寻找最优高能量缝的方案。我们通过快速建立图像中行(或列)之间的匹配关系[25]来并行地查找所有高能量缝。建立相邻行对之间的匹配关系是整个过程的关键。这种匹配包括在相邻行对中的像素之间找到一对一的对应关系。也就是说，每个像素在上面的行和下面的行中都有一个匹配的像素。在所有相邻行之间建立匹配关系之后，从第一行(或最后一行)的任何像素开始，通过跟踪各行之间的匹配，我们可以通过图像获得像素序列Sq。因此，在建立所有相邻行之间的匹配关系后，我们可以找到所有的垂直接缝。

不失一般性，以下只讨论缩小图像宽度的情况；关于图像高度调整的情况类似。在N×M的图像I中，利用一个简单约束，就是相邻像素缝之间距离小于等于1，公式表达如下

∀i∈[1,m]∧j∈[1,n),|m(i,j)-i|≤1

(3)

值得注意的是，I(m(i,j),j+1) 是像素I(i,j) 在第j+1 行的匹配像素。根据这个约束条件会有两种匹配情况，我们将其通过以下表达式描述

(4)

其中， F(i-1) 和F(i-2) 分别为前i-1、i-2对像素的匹配边的权重之和；w(i,i)、w(i,i-1) 和w(i-1,i) 则分别表示剩下的像素对的匹配边权重。而关于匹配边权重的定义则基于匹配边能量，由于我们寻找最优高能量缝，换言之，高能量缝匹配边具有较高能量，剩余匹配边能量较低。所以采用最大化匹配边能量方差的策略

(5)

(6)

由于上述内容只考虑两行之间的匹配情况，这两行是从整个图像中分离出来的。因此，这个定义只保证了某些两行之间的匹配边的方差是最大的，但并不保证整个图像中垂直接缝之间的最大差异。也就是说，它只实现局部最优，而不是全局最优。因此定义了像素矩阵P和矩阵Q， P(i,j) 代表经过像素I(i,j) 从第一行到第j行的缝的累积能量； Q(i,j) 代表从像素I(i,j) 开始并以最后一行中的像素结束的最佳缝的累积能量

Q(i,j)=e(i,j)+
max{Q(i-1,j+1),Q(i,j+1),Q(i+1,j+1)}

(7)

分别用P(i.k) 和Q(m(i,k),k+1) 代替上述讨论中的e(i,k) 和e(m(i,k),k+1)。 所以我们将权重更新为w′

(8)

在这个定义下我们就可以快速的根据最优匹配关系寻找到最优高能量垂直缝，如图4所示。那么一条垂直最优高能量缝定义可如以下表达式

vSq={EvSq,(x1,y1),(x2,y2),…,(xN,yN)}

(9)

其中，EvSq是这条最优垂直缝的总能量；而后面组成这条缝的像素点则是满足上述最优匹配关系的。

2.2 构建焦点区域

不失一般性，我们首先定义一个垂直高能量缝数组VS[n] 用于存储由2.1节所得到的最优高能量缝，其中包含其能量值和其中所有的像素点。如Zhang等[19]提出的方法中的描述，在数组VS[n] 中，所有能量缝按能量值进行排序，第一个元素是具有最高能量的缝，每个缝的能量值低于前一条缝的能量值。以下是垂直高能量缝数组生成过程，水平高能量缝数组类似。

(1)定义一个n维垂直高能量缝数组VS[n]， 用于每次存储最佳垂直高能量缝；

(2)将2.1节所得到的最优垂直高能量缝vSqi放在VS[n] 中；

(3)从源图像中移除缝vSqi， 然后将vSqi的右侧区域向左移动一个像素，经过上述步骤后，源图像的宽度可以减少一个像素。

(4)当步骤(2)和(3)循环执行n次后，可以得到n维垂直高能量缝数组，可表示为

VS[n]={vSq1,vSq2,…,vSqn}

(10)

当所有垂直高能缝都被发现时，我们需要调整每条缝，以便在源图像中删除之前可以将其恢复到位置。从vSqn-1到vSq1对VS[n] 进行反向遍历对其进行调整，从而得到调整后的VS[n]。 调整情况如下：

(1)假设目前缝为vSqi， 对于VS[n] 中位置在vSqi之后的每条缝vSqj， 即从vSqi+1到vSqn， 比较vSqi和vSqj中相同水平线上的每个像素。

(2)如果当前在vSqi中的像素位置与vSqj中的位置相同，或者在它左边，然后将vSqi中的当前像素位置向右移动一个像素。

在快速缝翘曲法(FSW)中，由最优高能缝组成的区域是源图像的焦点区域。为了保证高能缝数组能够基本覆盖焦点区域，必须选择合适的高能缝数量。随着高能缝的能量值不断减小，我们可以分析其下降趋势，当下降趋势突然增加时，我们将先前的高能缝视为最后一条缝，然后可以确定数量n。

2.3 缝翘曲操作

焦点区域构建完成后，我们就可以通过缝翘曲的操作得到最终的目标图像。该方法对高能部分(焦点区域)进行放大，相对较低能量的部分收缩。这样，图像的焦点区域就可以得到强调，而不会失去非聚焦的内容。首先，需要分别确定高能部分和低能部分的缩放因子；然后，利用缝翘曲法对源图像进行重定向操作。值得注意的是，重定向结果会随高能缝数组的垂直或水平方向的不同而不同。而为了承接以上的垂直高能缝数组的情况，并且后续对比实验只考虑图像宽度缩小情况，所以下文我们只从垂直方向对缝翘曲分别进行探讨。水平方向的缝翘曲操作与之类似。

设源图像和目标图像的宽度分别为ws和wt， 最佳的高能量缝数量为k， 高能量部分(焦点区域)和低能量部分的缩放因子分别为sh和sl。 它们的取值范围可由下式表示

wt/ws≤sh≤wt/k
sl=(wt-ksh)/(ws-k)

(11)

显而易见，当sh越来越大时，sl则越来越小，反之亦然。那么对于不同的图像和不同的要求，sh和sl的确切值则会随之变化。例如，如果我们要求焦点区域相对放大，那么sh的值应该更大；反之，它就应该更小。考虑到计算复杂性，我们对所有高能量缝使用相同的缩放因子sh， 所有低能量缝使用相同的缩放因子sl。 确定缩放因子后，就可以使用缝翘曲重定向源图像。

对于垂直高能量缝部分(焦点区域)，我们每次转换一行。采用线性插值方法计算目标图像的每个像素值。也就是说，目标图像的像素值由源图像中对应的两个相邻像素的加权平均值计算，如式(12)所示

p=p1*(d2/(d1+d2))+p2*(d1/(d1+d2))

(12)

其中，p是当前像素的值，p1和p2是其相邻像素的值；而d1和d2分别代表当前像素p与其相邻像素p1、p2之间的距离。这种方法能够在保证像素值连续性的同时使得目标图像具有较高的质量。

得到目标图像的每个像素值后，我们使用式(13)计算目标图像中每个像素点的位置。其中，xs是源图像中当前行位置的横坐标，xt是与之对应的目标图像中当前行位置的横坐标。wh则表示当前行从0到xs的范围内垂直高能量缝数组的大小(宽度)

xt=sh*wh+sl*(xs-wh)

(13)

3 实验对比与结果

关于实验结果对比，我们主要从3个方向来综合做出评价：视觉效果、算法运行速度、主观满意度测试。

3.1 视觉效果

图4为测试图像集(图像来源RetargetMe数据集[26])，图5则显示了我们提出的方法与传统seam carving[2]、SNS[10]、缝翘曲方法[19]的视觉效果比较结果。从图中可以看出，与其它几种方法相比，通过快速缝翘曲(FSW)方法获得的目标图像没有明显的失真或程度较小。

图4 文中所用测试图像

图5 实验结果对比(图宽缩小50%)

由于对能量图的优化，我们的方法在焦点区域检测的精确度上明显高于其它方法。以第一组对比为例，传统seam carving[2]和缝翘曲方法[19]对最左侧椅子腿产生了明显的内容丢失，而我们的方法则很好地保存了重要对象的完整性。在优化的能量图中加入Hough直线检测与Canny边缘检测，使得我们的方法对直线区域以及重要对象的边缘比较敏感，对图像中重要内容的结构保护起到了很大的作用。以第二组右边的屋脊、第三组的左侧墙面为例，其它的3种方法都产生了较大程度的弯曲与失真，而我们的方法就很好地保留了这些重要对象的结构信息。如果图像重要内容中包含人像时，我们的方法就明显优于其它3种方法。以第六组为例，seam carving方法导致内容明显丢失(左侧人身体不完整)，造成了很大失真；而SNS、缝翘曲方法虽然很好保证了图像内容的完整性，而在人脸比例的保持上产生明显拉长，造成了明显的失真；我们的方法在优化的能量图中加入人脸检测，就很好保证了包含人脸图像的重定向效果。

综上所述，根据图5中对比结果所示，相比于其它3种图像重定向算法，我们的快速缝翘曲(FSW)方法获得的目标图像具有更良好的视觉效果。

3.2 算法处理速度

当使用传统seam carving中的最优缝搜索方案时，我们需要计算每个像素的累积能量值，并涉及大量的循环操作。这肯定会影响算法的处理速度。而本文方法利用每行(列)像素间的最优匹配关系对此方案做出了改进，从而大大提升了算法处理速度。为了客观说明这一点，我们将本文算法处理速度与传统seam carving方法[2]、SNS方法[10]、原始的缝翘曲方法[19]进行了比较。比较结果见表1。从表1中我们可以看出，原始缝翘曲的处理速度比seam carving还慢一点；而我们的快速缝翘曲(FSW)方法则明显快于其它3种图像重定向算法。这种差异会对算法的实现产生很大的影响。

表1 算法处理速度对比

3.3 主观满意度测试

测试中，我们选择6组图像。每组包含源图像和通过不同图像重定向方法获得的4个目标图像。另外，在实验室找了20名参与者，所有参与者同时获得一组图像。我们的目的是测试参与者对目标图像视觉效果的满意度。因此，我们先将当前组的源图像提供给参与者。然后，在不告知方法的前提下，目标图像以随机顺序出现，并要求参与者对他们给定图像的视觉效果的满意程度进行评分(分值从1到5，1：最不满意；5：最满意)。在此测试数据的基础上，给出了用户主观满意度，如图6所示。图中的数字坐标代表参与者评价得分的平均值，得分越高代表满意度越好。显而易见，我们的方法主观满意度高于其它经典方法。结果表明，我们的方法是解决图像重定目标问题的一个好方法。

图6 主观满意度的对比结果

4 结束语

本文提出了一种快速缝翘曲(FSW)的图像重定向方法，该方法结合了warping和seam carving的技术。该方法以一种各相邻行(列)像素间的最优匹配关系对传统seam carving方法的缝寻找方案进行改进，并通过改善能量图生成方案,更精确地寻找高能量缝。以上两点的优化就可以精确、快速地进行自动对焦检测(焦点区域检测)。然后根据最优高能量缝对图像进行翘曲变换得到目标图像，而不是像一般warping方法采用基于区域或网格的变形模型来解决有关图像重定向的问题。这种方法不仅保存了图像的完整性，而且还高效、精确地解决了焦点区域的检测工作；同时，它还能够处理很多类型的图像，目标图像都具有良好的视觉效果。这些特点使我们的算法成为一种非常有吸引力的图像重定向方法。通过上节的对比实验，验证了该方法在图像重定向问题上的有效性并且获得的目标图像具有良好的视觉效果及主观满意度。

虽然验证了我们的工作在图像重定向问题上的有效性，但本研究有一定的局限性。利用发现的高能量缝来识别焦点区域，我们可能会看到一些焦点区域没有被得到的高能缝数组所覆盖，因此目标图像中可能会发生一些失真。在今后的工作中，我们将致力于图像焦点区域的精确检测工作，达到进一步改进算法的目的，使之具有更好的视觉效果。