Seam Carving

1. Def

Problem statement:

Input Image $𝐼_{𝑛×𝑚}$ and new size 𝑛′×𝑚′
Output Image 𝐼′of size 𝑛′×𝑚′which will be “ good representative ” of the original image 𝐼

即：对图像进行缩放的同时希望输出图像对内容有好的展示

2. General Retargeting Framework

Assume $m \times n \rightarrow m \times n’, n’<n$ (summarization)
Basic Idea: remove unimportant pixels from the image 移除不重要的像素出去
- Unimportant = pixels with less “energy” 不重要指的是能量较低

$E_{1}(\mathbf{I})=\left|\frac{\partial}{\partial x} \mathbf{I}\right|+\left|\frac{\partial}{\partial y} \mathbf{I}\right|$

Intuition for gradient based energy:
- Preserve strong contours
- Human vision more sensitive to edges so try remove content from smoother areas
- Simple enough for producing some nice results

3. A Seam

3.1 Def

A connected path of pixels from top to bottom (or left to right).可以理解为一个像素的八领域像素点4

$\begin{aligned} &\mathrm{s}^{\mathrm{x}}=\left\{s_{i}^{x}\right\}_{i=1}^{n}=\{(x(i), i)\}_{i=1}^{n}, \text { s.t. } \forall i,|x(i)-x(i-1)| \leq 1 \end{aligned}$ $\begin{aligned} &\mathrm{~s}^{\mathrm{y}}=\left\{s_{j}^{y}\right\}_{j=1}^{m}=\{(j, y(j))\}_{j=1}^{m}, \text { s.t. } \forall j|y(j)-y(j-1)| \leq 1 \end{aligned}$

3.2 Finding the Seam?

3.3 The Optimal Seam

The recursion relation

$\mathbf{M}(i, j)=E(i, j)+\min (\mathbf{M}(i-1, j-1), \mathbf{M}(i-1, j), \mathbf{M}(i-1, j+1))$

Can be solved efficiently using dynamic programming in $O(s\times n\times m)$

3.4 Dynamic Programming

3.4.1 Recursion

𝑀(𝑖,𝑗)= minimal cost of a seam going through (𝑖,𝑗) 先计算整张图的能量，计算的方法为该像素点过去的领域像素中能量的最小值加上自身的能量。

最终：

3.4.2 Backtrack

Backtrack (can store choices along the path, but do not have to)
- 在最后一层找最小的一个能量的像素点
- 然后回溯，找该像素上三领域中能量最小的像素
- 直到遍历到第一行结束。

3.4.3 伪代码

3.5 效果

Q: Will the result be the same if the image is flipped upside down?
- A: Yes (up to numerical stability)
Q: What happens to the overall energy in the image during seam carving?
- 变大
所以当我们resize图像后，对于整个图像的平均能量应该变大

比较：

我们可以发现seam的效果最好

3.6 Both Dimensions?

$m \times n \rightarrow m’ \times n’, n’<n, m’<m$

The recursion relation:

$\begin{aligned} &\min _{\mathbf{s}^{\mathbf{x}}, \mathbf{s}^{y}, \alpha} \sum_{i=1}^{k} E\left(\alpha_{i} \mathbf{s}_{\mathbf{i}}^{\mathbf{x}}+\left(1-\alpha_{i}\right) \mathbf{s}_{\mathbf{i}}^{\mathbf{y}}\right) \end{aligned}$ $\begin{aligned} &r=n-n^{\prime} \quad c=m-m^{\prime} \quad \mathrm{k}=r+c \end{aligned}$

Transport map :

$\begin{aligned} \mathbf{T}(r, c)=\min \left(\mathbf{T}(r-1, c)+E(\mathbf{s}^{\mathbf{x}}(\mathbf{I}_{\mathbf{n}-\mathbf{r}-1 \times \mathbf{m}-\mathbf{c}}\right)), \\ \left.\mathbf{T}(r, c-1)+E\left(\mathbf{s}^{\mathbf{y}}\left(\mathbf{I}_{\mathbf{n}-\mathbf{r} \times \mathbf{m}-\mathbf{c}-\mathbf{1}}\right)\right)\right) \end{aligned}$

其物理含义就是，