Seam Carving

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算子提取图像梯度作为能量图：

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))$为相应的方向接缝删除后的能量。

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