基于Seam Carving的双向接缝裁剪图像重定向

陈加玲， 叶少珍, 2

(1. 福州大学数学与计算机科学学院， 福建 福州 350108； 2. 福州大学智能制造仿真研究院， 福建 福州 350108)

0 引言

随着经济与科学技术的发展， 数字电子设备普及千家万户， 同一尺寸图像在不同屏幕比例的数字电子设备上普遍存在显示差异， 于是如何处理图像与屏幕尺寸不适配问题成为新的研究热点. 针对这个问题， 传统图像缩放技术一般有三种方法， 均匀缩放、 居中裁剪和黑边填充. 均匀缩放是通过几何变换方式对图像像素进行映射填充， 会对图像的水平及竖直方向上造成挤压或拉伸形变； 居中裁剪是按显示屏宽高比尽可能大的范围裁剪图像中间区域， 虽然图像整体没有发生扭曲， 但是图像信息部分丢失了； 黑边填充是对图像进行等比缩放加上边缘黑色填充， 虽没有整体扭曲和内容丢失， 但屏幕周围填充的黑边， 没有充分利用屏幕空间特性. 这些传统技术都采用统一处理方式， 无差别地处理所有结构和内容相差异的图像， 往往达不到用户满意的结果.

1 现有图像重定向方法比较

与传统方法不同， 内容感知的重定向方法通过自动识别不同内容区域的重要程度， 并保持高重要性的主体区域不变或均匀缩放， 同时允许重要性低且分布均匀的背景区域尽可能调整和适当变形. 当前内容感知的图像重定向方法主要有以下几种： 智能裁剪方法[1-3]、 形变方法[4]、 多操作符方法[5]和Seam Carving方法[6-8]. 智能裁剪方法一般分为基于注意力的和美学导向， 二者统一目标都是基于上下文感知的图像进行裁剪， 但又有区别. 基于注意力的方法侧重于在裁剪或者调整大小过程中保留视觉重要区域， 如自动保留注意力百分比方法[3]寻找到注意力和裁剪区域之间的平衡点； 后者侧重于在众多任意裁剪的子图中通过图像质量评估遴选最具视觉吸引力的候选子图， 如使用贝叶斯网络作为质量选择标准， 以流形嵌入算法核心指导图像裁剪[2]， 和选择宽高比下最大尺寸且最大显著性得分的子图的内容保留裁剪(content-persistent thumbnail cropping)方法[1]. 基于形变的方法一般使用一个三角形或四边形网格对图像进行分区， 通过调整翘曲图顶点坐标来实现重定图像. 如使用贝尔特拉米表示(Beltrami representation)作为翘曲图[4]维持形变过程的几何形状, 然后利用双射翘曲将翘曲图映射到重定向目标. 多操作符方法重定向效果往往比单一操作更好， 如结合缝刻、 裁剪、 形变和缩放四种重定向算子， 使用尺度不变特征变换(SIFT)流和结构相似度(SSIM)进行原始图像和重定向图像的对应密集和相似度估计， 利用视觉显著性加权相似度估计结果确定迭代算子[5]. Seam Carving(下称“SC”)图像调整技术或称接缝雕刻[6]， 其算法比前面提到的方法都简单且具有不错的重定向性能. 这类方法一般通过原图启发式得到代表像素重要程度的能量图， 根据能量图进行反复裁剪水平或者竖直方向能量最小细缝. 但由于能量图仅检测到图像的边缘信息， 裁剪的细缝不可避免穿过重要主体对象. 近年来不断有其他研究者提出改进， 如使用原始的梯度图融合GBVS模型(graph-based visual saliency, GBVS)产生的显著度图[7]， 通过线性加权和相乘两种方式得到两种不同功能的能量图； 更有利用融合了显著性和HVS边缘映射[8]， 将平面图像重定向扩展到立体图像重定向也取得不错的效果.

综上所述， 关于SC算法， 如何得到包含边缘和保护主体的重定向成为一个共同关注的问题， 本研究提出对应于上述研究问题的双向接缝剪裁的重定向方法. 首先， 使用融合梯度和显著图提出一种新型能量图； 其次， 提出了SC裁剪策略的改进方法； 最后， 进行多组多方法对比实验并采用SIFT Flow指标对其质量进行分析和评价.

2 图像重定向改进算法

SC是一种非均匀的图像大小调整方法， 也是一种内容感知的图像重定向方法. 根据能量图检测出原图中不重要区域， 然后在某一维度贪心的删除或插入能量最小的细缝. 算法定义能量图为表示像素重要程度的梯度图， 定义裁剪缝为图像中的一条纵向或横向连续路径， 自顶向下的路径每一行只经过一个像素点， 从左到右的路径每一列只经过一个像素点. 以搜索最小能量纵向裁剪缝为例， 从第一行开始， 向左下、 正下、 右下方寻找路径并累计能量. 这样利用动态规划搜索出能量图的最小代价路径称为“细缝”.

而后注意到细缝移除时会伴随新的能量插入， 即当前像素及其左上、 正上和右上像素分别作为细缝像素移除后， 周边像素由不相邻变为相邻， 则新相邻像素之间的差值作为额外的移除代价， 如下式所示：

(1)

于是进一步提出向前能量法则的改进， 改进了能量函数为能量值e(i,j)、 能量累计值C(i,j)、 移除代价公式(1)三方面总和的最小值， 表示为以下公式：

(2)

图1 算法框架流程图

虽然SC在重定向方面具有不错的效果， 但仍存在两方面问题： 1) 使用梯度能量图仅仅检测到图像的边缘信息， 容易造成图像中显著物体形状结构被破坏和重要内容缺失的现象. 2) 图像缩放比率较大且分布均匀的信息在裁剪方向上消耗完时， 裁剪的细缝不仅会穿过感兴趣区域(region of interest, ROI)使图像发生扭曲， 而且ROI区域与全局之间的布局关系受到破坏.

本研究以SC算法为研究对象， 针对以上两个问题， 首先提出了融合边缘梯度和内容显著性的能量图， 其次基于能量图又提出了双向裁剪方法重定向方法. 框架流程如图1所示， 首先使用原图自适应生成梯度图和显著图， 二者线性融合得到能量图； 然后， 使用动态规划方法对能量图进行水平和竖直两个方向上搜索最小能量细缝， 根据原图和目标图之间的尺寸关系， 交替插入/删除竖直/水平细缝； 最后， 得到微调的图像， 以之取代原图， 反复迭代前面操作达到目标尺寸.

2.1 构造新的能量图

近年视觉性、 显著性逐渐受到许多国内外研究者的关注， 通常图像在没有给出其他注意力信息的情况下， 人类视觉水平的显著性作为重要图的依据具有重要意义. SC的梯度图认为图像边缘部分是相对比较重要的， 但对于一些多纹理为背景的图像中， 这种方法常常会丧失前景主体的重要保留. 本研究方法认可传统方法边缘检测的必要性， 但同时额外融合了表征重要对象边界和主体的显著图， 希望通过产生新能量图对SC算法效果起到较好的提升.

文献[9]提出的全分辨率频率调制算法(称FT法)， 能够高效简洁地检测显著性对象清晰边界. 文献[10]提出的快速光栅扫描显著性检测算法(称MB法), 这是一种近似最小障碍距离变换的算法， 对图像像素波动具有很好的鲁棒性， 且能够捕获图像边界关联线索从而保留重要内容. 通过线性融合FT显著图、 MB显著图及梯度图并归一化进而构造出一种新型能量图.

梯度法定义为表示图像像素的能量值为x方向和y方向上的梯度绝对值的和， 即下式中e(i,j)对应的是图像中(i,j)位置像素的能量值. 图像对应的高能量像素点， 说明该像素点是需要保留的高能量像素值， 对图像重要性越大， 反之低能量像素值， 保留的意义较弱， 对图像重要性越小.

(3)

FT显著性检测是在颜色空间(lab color space, LAB)下， 利用颜色特征的中央-周边算子来得到显著图， 此算法简单、 高效而且可以生成全分辨率高质量的显著图. 首先， 将输入图像I经过高斯滤波得到Ihc， 并将图像由RGB颜色空间转换为LAB颜色空间， 取其三通道均值为Iave(lm, am, bm)； 然后， 利用均值Iave(lm, am, bm)对图Ihc每个像素计算欧式距离得到S(x,y)(见下式)； 最后， 对S进行最大值归一化， 即得FT显著图.

S(x,y)=|Iave-Ihc(x,y)|

(4)

MB显著性检测以最小障碍距离路径代价计算像素颜色距离， 然后利用快速光栅扫描的迭代方式获得显著图. 首先， 采用Minimum Barrier Distance(MBD)作为路径代价函数， 选取图像的边界像素作为背景种子； 然后， 通过FastMBD计算图像每个颜色通道的各个像素和背景种子像素的MBD距离图； 最后， 所有通道累加， 再进行最大值归一化， 即得MB显著图.

如图2所示， 使用256阶灰度图作为能量图. 256阶灰度图最亮为255， 最暗为0， 将最亮与最暗之间的亮度变化划分为256份. 像素灰阶是0～255中任意数值， 表示对应像素的重要性， 像素能量越高， 像素灰阶数值越大， 对应能量图越亮. 使用图2(a)梯度法检测出了表征边缘重要度的梯度图Sgrad， 图2(b)中FT算法检测出了表示重要对象边界的显著图Sft， 图2(c)中MB算法检测出了表示重要对象内容的显著图Smb， 对这三种重要性图使用下式进行线性融合, 然后归一化得到一种新的能量图Senery(见图2(d)). 通过实验表明， 线性融合的参数α,β,θ分别控制在0.9～1.1， 0～0.3， 0～0.2之间生成的能量图重定向效果性能较好. 本研究第三部分实验采用的参数为α=1,β=0.25,θ=0.16.

Senery=αSgrad+βSft+θSmb

(5)

(a) 梯度图

2.2 融合显著性的双接缝裁剪

本研究提出结合了裁剪和扩增的双向接缝裁剪方法， 根据图像重定向的目标比例采取适当的策略对水平和竖直两个方向进行裁剪和插入像素. 具体做法： 使用上面介绍新型能量图， 根据能量图动态规划搜索水平和垂直两个方向的最小能量细缝， 对于宽高比缩小的一边使用细缝裁剪， 对于宽高比扩张的一边使用进行细缝插入， 目的是使得图像重定向取得较好效果的同时尽可能保留重要内容的布局.

2.2.1结合邻近相似的像素扩增法

图3 结合邻近相似的像素扩增法

重定向方法涉及到图像扩增插入细缝， 除了找出插入位置还要选取合适的插入像素值， 然后再移动像素， 基于以上因素提出了结合邻近相似的像素扩增法. 以插入竖直细缝为例(见图3)， 图左侧是能量图使用动态规划查找最小路径细缝后， 进行图像边缘相似填充； 图中间是细缝像素a0为中心的3×3的区域， 选择周边8个像素与之最相似的像素作为扩增像素值a8(见下式)； 图右侧是扩增像素pi(a8=pi)在细缝像素p2(a0=p2)右侧进行插入， 其余像素依次向右移动一个像素单位.

(6)

另外, 对于图像的非重要边缘, 如大面积的天空、 草地、 海洋， 这类同质性纹理具有一般重复性, 本文提出使用对称仿制对同质背景进行像素扩增, 以避免过度细缝剪裁的问题及大幅实失真的现象. 即取原图四周N行/列像素作为仿制原子, 增加的N列行像素与仿制原子互为对称.

2.2.2改进算法的设计与整合

3 实验对比和分析

实验使用MIT RetargetMe数据集， 采用五种方法与本研究方法进行实验对比： 人工剪裁(CR)、 均匀缩放(SCL)、 Multi Operator(MULTIOP)[11]、 Scale and Stretch(SNS)[12]、 Seam Carving(SC)[6]. 同时， 设定了4∶3、 2∶1、 3∶4、 1∶2四种不同宽度的缩放比例实验， 通过分别进行这四种比例的五种方法图像重定向的对比实验来验证本研究提出方法有效性.

3.1 定量分析

为了对重定向方法的性能进行客观的检测， 采用SIFT Flow[13]作为本研究提出的重定向方法效果的衡量指标. SIFT Flow质量评价标准能有效地衡量重定向图像较原始图像的形状信息的变化， 在两幅图中进行稠密的特征采样， 找到所有像素点相似处的位移差； 位移差越大， 两个图像重要物体之间的形变距离越大, 重定向图像中的显著物体较原图扭曲失真越严重. 随机选取几组对比实验进行SIFT Flow质量测评， 从表1的质量评价数据来看， 相对于其他的重定向方法， 本研究方法较其他方法在客观指标上均取得最小值， 也就是图像重定向前后形状信息变化和扭曲失真程度都比其他方法小.

表1 SIFT Flow评价指标下其他重定向方法与本研究方法的对比

3.2 定性分析

(a) Original (b) CR (c) SCL (d) MULTIOP (e) SNS (f) SC (g) Ours

(a) Original (b) CR (c) SCL (d) MULTIOP (e) SNS (f) SC (g) Ours

前面两组都是对于图像宽度缩小的情况， 后面两组是图像宽度扩增. 如图6所示， 第三组是重定向目标宽为原来的4/3倍(图6(a))， 第四组是重定向目标为原来的2倍(图6(b)). 观察第三、 四组图像的威尼斯小船和天妇罗碗碟， 对比其他重定向方法的结果及结合前面几组对比实验， 可以得出本研究方法都较好地维持原本形状及主体对象在图像中的布局.

(a) Original (b) CR (c) SCL (d) MULTIOP (e) SNS (f) SC (g) Ours

3.3 与原算法复杂度对比分析

4 结语

本研究提出一种双向接缝裁剪的图像重定向改进方法， 结合梯度图和显著图构造了一种新型能量图， 基于提出的新能量图， 又对传统的方法单向过度裁剪造成的问题提出了双向裁剪接缝的改进. 在当前广泛使用于重定向领域的公开数据集MIT RetargetMe中， 进行了多组多种方法对比实验， 实验结果表明该方法相对具有优越性. 所提的改进方法适应于不同比例尺寸图像重定向， 符合人眼视觉中心原则， 在突出重要对象主体和保护重要边缘信息的同时， 调整了重要内容在图像整体中的布局.