Please enable Javascript to view the contents

Seam Carving

 ·  ☕ 3 åˆ†é’Ÿ

result

Seam Carving算法是一种基于内容的图像缩放方法,在保证图像中“重要区域”不发生形变的前提下,对图像进行缩放。

一种直观的想法便是找出图像中的“不重要区域”,并将其删除。文献[1]中便是采用这种思想,

通过定义像素的能量函数,通过动态规划方法对某一方向的像素进行能量累积,最后回溯求出能量最低的一条路径,该路径便是我们要删除的“最不重要”路径。

1. 基本方法

图像的能量简单地由图像梯度描述:
$$
e_1(\pmb I)=\left|\frac{\partial}{\partial x}\pmb I\right|+\left|\frac{\partial}{\partial y}\pmb I\right|
$$
论文中也给出另外一种能量的变体实现:
$$
e_{HoG}(\pmb I)=\frac{\left|\frac{\partial}{\partial x}\pmb I\right|+\left|\frac{\partial}{\partial y}\pmb I\right|}{\max(HoG(\pmb I(x,y)))}
$$
实现中,采用Sobel算子提取图像梯度作为能量图:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
void SeamCarving::genEnergyMap(const cv::Mat& img, cv::Mat& energy)
{
    cv::Mat sobel_x, sobel_y, gray_energy;
    cv::cvtColor(img, gray_energy, cv::COLOR_BGR2GRAY);
    cv::Sobel(gray_energy, sobel_x, CV_32F, 1, 0, 3);
    cv::convertScaleAbs(sobel_x, sobel_x);
    cv::Sobel(gray_energy, sobel_y, CV_32F, 0, 1, 3);
    cv::convertScaleAbs(sobel_y, sobel_y);
    cv::addWeighted(sobel_x, 0.5, sobel_y, 0.5, 0, energy);
    energy.convertTo(energy, CV_32FC1);
}

对于$n\times m$的图像$\pmb I$,用于删除的接缝由如下定义:

水平接缝:
$$
\pmb{s^x}=\{s_i^x\}_{i=1}^n=\{(x(i),i)\}_{i=1}^n,\ \
s.t.\ \ \forall i,\ \ |x(i)-x(i-1)|\leq 1
$$

竖直接缝:

$$
\pmb{s^y}=\{s_i^y\}_{j=1}^m=\{(j, y(j))\}_{j=1}^m,\ \
s.t.\ \ \forall j,\ \ |y(j)-y(j-1)|\leq 1
$$

其中,$x:[1,\cdots,n]\rightarrow[1,\cdots,m]$,$y:[1,\cdots,m]\rightarrow[1,\cdots,n]$

而我们要寻找最低能量路径即求解最小优化问题:
$$
s^\ast=\min_{\pmb s}E(\pmb s)=\min_{\pmb s}\sum_{i=1}^ne(\pmb I(s_i))
$$
利用动态规划的思想可以很方便地求出上述优化问题,利用能量累积矩阵$M$,转移方程:
$$
M(i,j)=e(i,j)+\min(M(i-1,j-1), M(i-1,j), M(i-1,j+1))
$$
从边缘出发按转移方程填充能量累积矩阵,最后寻找能量最低的终点$M(n,x)$(竖直搜索)或$M(x,m)$(水平搜索),回溯即可得到完整的最优路径。

1.1. 图像缩小任务

对于单方向缩小任务,只需重复上述接缝搜索流程,每次删除一条接缝即可。

对于多方向缩小任务,文献中也将横向竖向接缝的选择顺序其视为一个优化问题,假设现有$m\times n$的图像$\pmb I$欲缩小至$m'\times n'$,其中$m>m',n>n'$,接缝顺序的选择等价于优化以下能量函数:
$$
\min_{\pmb{s^x},\pmb{s^y},\alpha}\sum_{i=1}^kE(\alpha_i\pmb {s_i^x}+(1-\alpha_i)\pmb{s_i^y})
$$
其中,$r=m-m'$,$c=n-n'$, $\alpha_i\in{0,1}$描述了接缝选择的方向,因此有$\sum_{i=1}^k\alpha_i=r$,$\sum_{i=1}^k(1-\alpha_i)=c$成立。该问题同样可以利用动态规划的想法进行求解,取能量累积矩阵$\pmb T$,满足$\pmb T(0,0)=0$,转移方程:
$$
\pmb T(r,c)=\min(\pmb T(r-1,c),E(\pmb s^x(\pmb {I_{n-r-1\times m-c}})),\pmb T(r,c-1),E(\pmb s^y(\pmb {I_{n-r\times m-c-1}})))
$$
$\pmb {I_{n-r-1\times m-c}}$表示大小为$n-r-1\times m-c$的图像(中间量),$E(\pmb{s^x}(\pmb I))$和$E(\pmb{s^y}(\pmb I))$为相应的方向接缝删除后的能量。

但上述方法实测速度很慢,因此在实现中选择简单的贪婪策略选择带来当前最低能量的方法。

1.2. 图像拉伸任务

对于图像拉伸任务,同样可以采用缩小任务相似的处理方法,只是将最优接缝的删除修改为最优接缝邻域的插值,但和缩小任务不同的是,每次对单条最优接缝进行插值,容易导致后续的最优接缝

搜索会集中在同一区域,因此在图像拉伸任务中,建议一次性选择多条低能量接缝进行插值。

2. 实验结果

2.1. 图像缩小

原图像 图像能量 结果图像
m_src_image m_energy_map m_dst_image
m_src_image m_energy_map m_dst_image
m_src_image m_energy_map m_dst_image

2.2. 图像拉伸

原图像 图像能量 最优接缝 结果图像
m_src_image m_energy_map m_seam_map m_dst_image
m_src_image m_energy_map m_seam_map m_dst_image
m_src_image m_energy_map m_seam_map m_dst_image

3. 总结

从上图中可以看出 Seam Carving 的一些局限性:

  • 进行图像拉伸任务时容易造成图像区块重复,可以考虑手动排除部分区域进行优化
  • 在梯度变化不明显的“重要区域”容易造成误处理,比如:《蒙娜丽莎》大片的头发。可以考虑手动划分“重要区域”进行处理

参考文献

[1] S. Avidan and A. Shamir. Seam carving for content-aware image resizing. In ACM SIGGRAPH 2007 papers, pages 10–es. 2007

分享

Wenbo Chen
作者
Wenbo Chen
CG Student

目录