1 背景

我们经常会有缩放图像的需求，然而直接缩放的问题是，如果宽高缩放比例不一致，会导致图像内容发生形变“失真”。

Seam Carving 算法是下面论文中提出的一种图像缩放算法，它的好处是可以尽可能保持图像中“重要区域”的比例，避免由于直接缩放造成的“失真”。

@inproceedings{avidan2007seam,
title={Seam carving for content-aware image resizing},
author={Avidan, Shai and Shamir, Ariel},
booktitle={ACM Transactions on graphics (TOG)},
volume={26},
number={3},
pages={10},
year={2007},
organization={ACM}
}

上图是几种缩放方法的对比，左侧是 seam carving 结果，中间是直接缩放，右侧是 crop ，可以发现 seam carving 方法很好地保持了原图中大部分“信息”，且看起来画面中的主要物体也没有出现比例“失真”的情况（比如图片底部的岩石，直接缩放比例变化很大，crop 的话直接就没了）。

2 算法原理

基本思想

算法的基本思想非常直观，先考虑下沿着宽的方向进行缩放，缩放实质是删去了若干条纵向的像素“路径”(或者 seam，缝隙)，直接缩放删去的路径都是竖直的长条，相当于沿着图像竖直方向做了均匀的降采样。那么我们为什么一定要删去竖直的“路径”呢，如果能保持删去路径后，剩余的图像部分还是“平滑”的，或者说删去的路径是最不重要的，那么不就实现了基于图像内容的缩放了吗？

于是该论文作者提出了可以删去“能量”最少的 seam 来实现图像缩小。

“能量” 如何定义，最容易想到的就是梯度信息：

用像素在水平和竖直方向上的一阶梯度值的之和来表示该像素点的能量，那么一条缝隙的能量就是该缝隙上所有像素点能量之和。

我们需要做的就是每次找到像素能量最小的一条缝隙，然后删去它。

算法步骤

有了基本思想的铺垫，算法步骤也非常直观了，假设我们要删去 K 条 seam：

1. 计算每个像素点的能量；
2. 找到竖直/水平方向上的能量最小的路径，称为 seam；
3. 移除 seam，得到新图像；
4. 重复步骤 1 至步骤 3 K 次，得到缩放后的图像，

3 实现细节

能量图的计算

可以利用 OpenCV 中的 cv::Sobel 计算能量图：

  cv::cvtColor(carved_image_, carved_image_gray_, cv::COLOR_BGR2GRAY);

  cv::Sobel(carved_image_gray_, sobel_x_map_, CV_32F, 1, 0, 3);
  cv::convertScaleAbs(sobel_x_map_, sobel_x_map_);

  cv::Sobel(carved_image_gray_, sobel_y_map_, CV_32F, 0, 1, 3);
  cv::convertScaleAbs(sobel_y_map_, sobel_y_map_);

  cv::addWeighted(sobel_x_map_, 0.5, sobel_y_map_, 0.5, 0, energy_map_);

使用动态规划查找最优 seam

如何查找最优seam？以竖直 seam 为例，这个问题可以看成图论里的最短路径问题，把每个像素点看成一个节点，像素 (i, j) 连通的边只有上一行的左、中、右和下一行的左、中、右像素，那么我们要找的就是从图像第一行像素出发到图像最后一行像素的最短路。

我们可以用经典的最短路算法来求解，然而这里可以用动态规划进行更高效的求解：设图像宽、高分别为 W，H，记 M[i][j] 为到 (i, j) 像素点的最优 seam 的像素能量和，那么我们只要找到最后一行里能量最小的像素，即 min(M[H-1][j])，然后回溯即可以找到最优 seam。

记像素点 (i, j) 的能量为 e[i][j]，则能量转移公式为：

M[i][j] = e[i][j] + min(M[i-1][j-1], M[i-1][j], M[i-1][j+1])

C++ 代码：

/*
  // DP matrix (we use dynamic programming to find the optimal seam)
  std::vector<std::vector<float> > dp_mat_;

  // dp_path[i][j] records the `parent` index of dp_mat[i][j]
  std::vector<std::vector<int> > dp_path_;
*/

void SeamCarver::FindSeamWithDynamicProgramming(const cv::Mat &energy_map,
    std::vector<int> *seam) {
  assert(seam);
  const int r = energy_map.rows;
  const int c = energy_map.cols;
  dp_mat_.clear();
  dp_mat_.resize(r, std::vector<float>(c, 0.f));
  dp_path_.clear();
  dp_path_.resize(r, std::vector<int>(c, 0));

  // 第一行的路径能量直接用像素能量赋值
  for (int j = 0; j < c; ++j) {
    dp_mat_[0][j] = energy_map.at<float>(0, j);
    dp_path_[0][j] = j;
  }

  // 向下遍历像素，更新 M[i][j]，记录路径
  for (int i = 1; i < r; ++i) {
    for (int j = 0; j < c; ++j) {
      float energy_left_upper = j - 1 >= 0 ?
          dp_mat_[i - 1][j - 1] :
          std::numeric_limits<int>::max();
      float energy_right_upper = j + 1 < c ?
          dp_mat_[i - 1][j + 1] :
          std::numeric_limits<int>::max();
      float energy_upper = dp_mat_[i - 1][j];
      float energy_min = std::min(energy_upper,
          std::min(energy_left_upper, energy_right_upper));

      int parent_idx = j;
      if (std::fabs(energy_min - energy_left_upper) < 1e-6) {
        parent_idx = j - 1;
      } else if (std::fabs(energy_min - energy_right_upper) < 1e-6) {
        parent_idx = j + 1;
      }
      dp_mat_[i][j] = energy_map.at<float>(i, j) +
          energy_min;
      dp_path_[i][j] = parent_idx;
    }
  }

  seam->resize(r, 0);
  // 找最后一行里对应最小路径能量和的像素点
  int col_idx = std::min_element(dp_mat_[r - 1].begin(),
      dp_mat_[r - 1].end()) - dp_mat_[r - 1].begin();
  // 回溯得到完整路径
  (*seam)[r - 1] = col_idx;
  for (int k = r - 1; k > 0; --k) {
    col_idx = dp_path_[k][col_idx];
    (*seam)[k - 1] = col_idx;
  }
}

4 其他应用

放大图像

前面的内容只介绍了缩小，如何用类似的思想放大图像呢？

还是以竖直情况为例，作者给出的第一种方法是先按类似方法找到一条最优 seam，然后将这条 seam 与左右相邻的 seam 平均，这样得到一条新 seam 并插入到原图。这种方法的问题在于每次插入新 seam 后，下次再找最优 seam 可能还是在前一次最优 seam 的附近，即我们利用的信息重复/冗余了：

怎么利用更多信息？假设我们要插入 k 条新 seam，那么先一次性找到 k 条最优 seam，然后按反向顺序逐一取左右 seam 平均插入到图像中即可：

目标保护与去除

我们可以通过修改能量图来实现图像中目标的保护和去除，增加能量图中相关像素的能量值则可以起到保护作用，降低能量值则可以起到删除作用。

5 C++ 实现

我用 C++ 和 OpenCV 实现了基本的 Seam Carving 算法（包含目标保护与去除），代码地址在：

https://github.com/insaneyilin/SeamCarving

6 更多

Github 上有一个 pyCAIR 项目，用 Python 较为完整地实现了 Seam Carving 算法，可以直接使用。

---

参考资料

http://www.faculty.idc.ac.il/arik/SCWeb/imret/index.html

https://zhuanlan.zhihu.com/p/65339171

https://zhuanlan.zhihu.com/p/38974520