CS131学习笔记（lecture8）

本文主要是介绍CS131学习笔记（lecture8），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

讲义链接：http://vision.stanford.edu/teaching/cs131_fall1718/files/08_seam_carving.pdf

图像大小调整

截至上一节，对图像匹配的介绍暂时告一段落。本节将介绍在尽量少地改变图片观感情况下的尺寸调整（resizing）问题，即：
输入图像 $I$ : $m\times n$ ;
输出图像 $I'$ : $m'\times n'$ ，且具有“好”的视觉效果——这里的“好”仅表示具体观感，没有明确的定义（荒谬不荒缪？）。但是有一些要求必须满足：
1. 目标图像中的基本长宽比须满足要求；
2. 一些重要的内容和结构（important content and structures）需要保持；
3. Limit artifact；
虽然评价标准如此主观，但是办法总归是比问题要多的，我们还是可以定义一些用来描述“看起来好”的程度的概念——显著性度量(Saliency Measures)函数 $E(p)$ : $I\rightarrow[0,1]$ .
$E(p)$ 对一幅给定图像 $I$ 中的每一个像素p赋予了相应的能量值 $E\in[0,1]$ 。而能量越高，意味着这个像素 $p$ 越重要。

裂缝切割（Seam Carving）

我们先看该算法用于处理将图像 $I$ : $m\times n$ 转化为图像 $I'$ : $m\times n'（n'<n）$ 的问题。
第一步：记

E (I) = ∣ ∣ ∣ \partial I \partial x ∣ ∣ ∣ + ∣ ∣ ∣ \partial I \partial y ∣ ∣ ∣

$E(I)=\left|\dfrac{\partial I}{\partial x}\right|+\left|\dfrac{\partial I}{\partial y}\right|$
直觉上，一方面边缘处所包含的信息量更大，另一方面人眼对于边缘也更加敏感，所以对于边缘上的点（导数绝对值最大的点）应当赋予更高的能量值。
第二步：定义裂缝：

m m $m$ 维向量

S^{Y} = {s_{j}^{y}}_{j = 1}^{m} = {(j, y (j))}_{j = 1}^{m}, s . t . \forall j, | y (j) - y (j - 1) | \leq 1

$S^Y=\{s_j^y\}_{j=1}^{m}=\{(j, y(j))\}_{j=1}^{m}, s.t.\forall j, \left|y(j)-y(j-1)\right|\leq1$
（另一方向上同理）
第三步：选取裂缝并删除：选取并删去总能量最低的一条裂缝（optimal seam，最优裂缝）

S⋆=argminS∑s∈SE(s) S ⋆ = a r g m i n S ∑ s ∈ S E ( s ) $S^\star=argmin_{S} \sum\limits_{s\in S} E(s)$ 。
为了找到这条optimal seam，下面介绍了基于递归的动态规划算法。

动态规划（dynamic programming）

建立累积能量的递归关系：

M (i, j) = E (i, j) + m i n [M (i - 1, j - 1), M (i - 1, j), M (i - 1, j + 1)]

$M(i, j)=E(i,j)+min[M(i-1,j-1),M(i-1,j),M(i-1,j+1)]$
对于一个像素能量矩阵

E E $E$ ：
像素能量矩阵

建立累积能量矩阵

M

$M$ ，其第一行为

E E $E$ 的第一行，第二行及之后每行元素由递推关系式求得：
累积能量矩阵

然后从

M

$M$ 的最后一行开始按照最小的累积能量路径溯回，从而得到seam。
一些思考：
1.运行时间：上述步骤每运行一次，图像缩短一个像素。则从宽度

n n $n$ 到宽度

n^{'}

$n'$ 共需要运行

n−n′ n − n ′ $n-n'$ 次。总的时间复杂度为

O((n−n′)mn) O ( ( n − n ′ ) m n ) $O((n-n')mn)$
2.图片在上下翻折之后，算法运行结果不变。
3.由于每次裂缝切割都删去了能量值较低的像素，所以随着算法的运行，图像中像素的平均能量是在逐渐增加的。

两个维度的像素调整

有了前述算法，我们直觉上也许会说，那就先横着删，再竖着删呗？这种思想是可以理解的。但是，这是optima吗？答案是不一定。所以动态规划要重出江湖了。
递推关系式：

T (r, c) = m i n {T (r - 1, c) + E (s x (I n - r - 1 \times m - c)), T (r, c - 1) + E (s y (I n - r \times m - c - 1))}

$T(r,c)=min\{T(r-1,c)+E(s^x(I_{n-r-1\times m-c})),T(r,c-1)+E(s^y(I_{n-r\times m-c-1}))\}$
在这里我们删除的其实是一条从左上角到右下角的路径，每做一次removal，图像在两个维度的size都会减1。
在大部分情况下，上面的这一系列删除算法都是相当有效的，但是也存在一个limitation：这种像素删除算法会破坏图像的结构。
badstructure

这时我们通过最小化插入能量来实现原图结构的保持。直觉上，每删除一个像素，会存在原本不相邻的像素变得相邻的事发生，由于这个过程会产生图像的结构破坏，所以我们计算所有产生“相邻化“的地方的能量，作为“插入能量“。最后择取最三种选择中“插入能量“最小的方案。
如图，在删除（i，j）像素的上一行像素时有三种选择（i-1，j-1）（i-1，j）（i-1，j+1）。
这里写图片描述