1. 问题描述

结合 “Lecture 6 Resizing“ 的 Seam Carving 算法，设计并实现前景保持的图像缩放，前景由 gt 文件夹中对应的标注给定。要求使用“Forward Seam Removing”机制， X， Y 方向均要进行压缩。压缩比例视图像内容自行决定（接近1-2*前景区域面积/图像面积即可）。需要从测试子集中任选两张代表图，将每一步的 seam removing 的删除过程记录，做成 gif 动画格式，测试子集的其余图像展示压缩后的图像结果。

2. 求解过程与算法

Seam Carving的基本思想是移除图像中不重要的像素，也就是能量更少的像素。能量高一般来说有较强的轮廓。人类的视觉对边缘更敏感，所以试着从平滑的区域移除内容。则可以使用能量函数： $$ E_1(I)=|\frac\part{\part x}I|+|\frac\part{\part y}I| $$ 也就是以梯度的绝对值作为能量函数，对图像进行处理，可以得到一张关于图像的能量图。对于多通道的图片，对不同通道进行梯度计算然后将多通道的能量进行简单加和即可。能量越大的地方表明该处的梯度更大，因此更加重要。考虑优先删除更不重要的地方，也就是能量图中能量更少的地方。图像需要保证方正，因此考虑每次移除每一行中能量最低的像素。而且这些像素必须相邻才不会破坏图像内容。看上去，每次移除的一组像素就是从图像顶上到底下的一条曲线。

这样一来，删除的应该是能量最低的一条曲线。从上到下、从左往右遍历图片，计算到达当前位置的接缝最小的累计能量，遍历完图片后就能依据累计能量最少的路径来决定删除哪条接缝。其中，累计能量可以用动态规划计算，其动态转移方程为： $$ M(i,j)=E(i,j)+\min(M(i-1,j-1),M(i-1,j),M(i-1,j+1)) $$ 上述方法称为Backward Seam Moving。对于某些图像，采用该方法会产生断层。考虑不移除能量最少的接缝，而是移除插入能量最少的接缝，换句话说，就是去掉接缝后，希望接缝两端像素的差值最小，就能改进该不足，这样就能得到改进的Forward Seam Moving机制。上述的动态转移方程改为： $$ M(i,j)=\min\left{\begin{matrix}{} M(i-1,j-1)+|I(i,j+1)-I(i,j-1)|+|I(i-1,j)-I(i,j-1)|\ M(i-1,j)+|I(i,j+1)-I(i,j-1)|\ M(i-1,j+1)+|I(i,j+1)-I(i,j-1)|+|I(i-1,j)-I(i,j+1)| \end{matrix}\right. $$ 对于某些图片，我们不希望图中的某些部分被删改，因此才需要本题中的前景背景图像，确定前景位置保证前景尽可能不被删除。既然希望前景不被删除，那么就意味着前景部分有着更多的能量，因此，我们只需要将前景所在部分的能量加上一个常数即可。这个常数可以由自己设置，其值越大，表明前景越重要，被删除的优先级越低。即新能量函数为： $$ E_2(I)=\left{\begin{matrix}{E_1(I),当前位置为背景\E_1(I)+k,当前位置为前景}\end{matrix}\right. $$ 因此，算法实现的步骤为：

计算原图的能量图：
先计算梯度图
在梯度图的基础上，在前景像素对应的位置加上一个常数
依据上述动态转移方程，通过动态规划方法找出能量最少的接缝并删除
重复以上两步，直到图片大小被裁剪到规定的大小

3. 代码实现与说明

我使用3.7版本的 python 对该算法进行了实现。本实验涉及到图片存取与删改，因此用到了图像处理库 PIL ，为了方便处理，将图像转换为矩阵进行处理，还用到了 numpy 库，为了预览中间结果，还使用了 matplotlib 库。缺少上述组件会导致程序报错。

3.1 预处理与参数设置和说明

首先读入图片，考虑到背景图为RGB图像，但色彩只有黑白，我直接将其转换成了黑白图表示：

python for i in range(57, 1000, 100): img = Image.open("data\\imgs\\"+str(i)+".png") ground = Image.open("data\\gt\\"+str(i)+".png").convert('1')

对于每一张图片，我们首先应该要确定其缩放比例。依据题目要求，图片的应该要缩放到原来的$1-(2*前景面积)/总面积$，但据我观察，如果等比例缩放，有时最终图片不能达到较好的效果，这是因为有的图片在竖直方向上前景比例更小，有的在水平方向上前景比例更小。因此我手动设置了适合每张图片的宽度缩放比例：

python pic_rate = [0.5, 0.8, 0.4, 0.5, 0.7, 0.6, 0.7, 0.7, 0.5, 0.2]

假设当前图片对应的 pic_rate 大小为$\alpha$在计算新图像大小时，在原来的缩放比例 rate 基础上，宽度的缩放比例变为$rate^\alpha$，而高度的缩放比例变为$rate^{1-\alpha}$，这样一来可以保证图片压缩率的同时，针对图片内容进行效果更优的缩小。代码实现如下：

python size = img.size front_ground = np.sum(np.array(ground) == 1) # 统计前景面积 rate = 1 - (2*front_ground / (size[0]*size[1])) # 计算缩小比例 new_size = (int(size[0]*(rate**pic_rate[i//100])), int(size[1]*(rate**(1-pic_rate[i//100])))) # 进一步计算宽度和高度分别的缩小比例

3.2 对高度和宽度裁剪的说明

针对宽和高的Seam Carving过程，我设计了以下两个函数：

python def widthCarve(img, ground, new_width, save_frames, mode) def heightCarve(img, ground, new_height, save_frames)

其中， img 为原图， ground 为前景图， new_width 和 new_height 为最终输出图像的宽或高， save_frames 为保存每次中间结果的选项，如果为 True 则会保存每一帧以便之后制作gif图像。 mode 表示保存 gif 的一帧时是否要转置图片。两个函数都返回最终得到的图片和对应的前景图。

需要说明的是，对宽度的裁剪和对高度的裁剪具有高度相似性：二者执行算法的流程是一致的，只是接缝的方向不同。因此，代码很大程度上可以重用。实际上，删除图片的横向接缝，相当于将图片转置后删除图片的竖向接缝，因此，在实现高度裁剪时，只需要转置图片再调用宽度裁剪即可。得到图片后，再转置回来，从而得到最终结果：

```python

高度裁剪

def heightCarve(img, ground, new_height, save_frames): # 转置 img = img.transpose(Image.TRANSPOSE) ground = ground.transpose(Image.TRANSPOSE) # 调用宽度裁剪 img, ground = widthCarve(img, ground, new_height, save_frames, 2) # 转置回来 img = img.transpose(Image.TRANSPOSE) ground = ground.transpose(Image.TRANSPOSE) # 将帧号变为0 global frame frame = 0 return img, ground ```

我的算法是先进行宽度裁剪再进行高度裁剪，因此高度裁剪完成意味着当前图片处理完成，全局变量 frame 表示帧号，应重新置为0。

3.3 算法实现主体

下面的内容在函数 widthCarve 中实现。在实现对图片的裁剪时，要一直修剪到图片和预期大小相同为止，因此所有的算法在一个大循环中：

python while True: width = img.size[0] # 宽度达到要求则退出循环 if width == new_width: break

为了方便计算，先将图片对象转换为 numpy 的数组对象：

python img_array = np.array(img).astype(np.int8) ground_array = np.array(ground).astype(np.int8)

然后计算能量图，即梯度图。对于RGB三通道图片来说，只需要分别计算三个通道的梯度图然后进行相加即可，注意梯度要取绝对值：

python red_gradient = np.array(np.gradient(img_array[:,:,0])) red_gradient = np.maximum(red_gradient, -red_gradient) green_gradient = np.array(np.gradient(img_array[:,:,1])) green_gradient = np.maximum(green_gradient, -green_gradient) blue_gradient = np.array(np.gradient(img_array[:,:,2])) blue_gradient = np.maximum(blue_gradient, -blue_gradient) energy_map = red_gradient[0] + red_gradient[1] + green_gradient[0] + green_gradient[1]+ blue_gradient[0] + blue_gradient[1] energy_map = np.array(energy_map).astype(np.int16)

将前景部分增加能量的部分，我在之后的计算累计能量时进行了实现，而没有直接加在能量图上。

还需要初始化以下变量：

python cumulate_energy = np.zeros(energy_map.shape)# 累计能量图，使用动态规划更新的对象 path = np.zeros(energy_map.shape).astype(np.int16)# 路径图，记录最少能量的路径 new_img = np.zeros((energy_map.shape[0],energy_map.shape[1]-1,3)).astype(np.int8) # 删除接缝后的图片 new_ground = np.zeros((energy_map.shape[0],energy_map.shape[1]-1)).astype(np.int8) # 删除接缝后的前景背景图

cumulate_energy 即为累计能量图， cumulate_energy[i,j] 表示从图片顶部到达 [i,j] 位置的接缝所需的最少能量，而 path 用于记录该能量最少接缝的实际路径。如：到达 [i,j] 处能量最少的接缝的上一处位置为 [i-1,j-1] ，则 path[i,j]=j-1 。因为从上往下的接缝其行坐标依次增加，很容易得知，所以只需要保存列坐标即可。

对于第一行，直接进行赋值：

python cumulate_energy[0,:] = energy_map[0,:] # 累计能量图和能量图的第一行相同 path[0,:] = -1 # 第一行路径为-1表示路径终止

之后的内容，依次遍历图像的每个像素并通过动态规划方法更新即可。遍历到位置 [i,j] 时，计算从左、中、右来的三条接缝分别的累计能量：

python left = cumulate_energy[i-1,j-1] + abs(energy_map[i,j+1] - energy_map[i,j-1]) + abs (energy_map[i-1,j] - energy_map[i,j-1]) mid = cumulate_energy[i-1,j] + abs(energy_map[i,j+1] - energy_map[i,j-1]) right = cumulate_energy[i-1,j+1] + abs(energy_map[i,j+1] - energy_map[i,j-1]) + abs (energy_map[i-1,j] - energy_map[i,j+1])

需要说明的是，如果在边界处，即 j 为0或 img.size[0]-1 时，上述接缝只有两条且下标会出界，因此在边界处按照Backward方法计算能量即可，即：

python if j == 0: # 第一列不能有从左边来的路径 right = cumulate_energy[i-1,j+1] + energy_map[i,j] mid = cumulate_energy[i-1,j] + energy_map[i,j] elif j == img.size[0]-1: # 最后一列不能有从右边来的路径 left = cumulate_energy[i-1,j-1] + energy_map[i,j] mid = cumulate_energy[i-1,j] + energy_map[i,j]

只需要将 left 、 right 、 mid 初始化为一个很大的值，就能在有边界条件时也不会选到非法位置。得到三条不同接缝的累计能量后，选择最小的，并更新对应的累计能量图和路径即可。 choosePath 函数用于找出累计能量最小的路径，当 left 、 mid 、 right 分别为最小值时会分别返回-1、0、1。另外，如果当前位置是前景则额外再加上一个常数，我设置的是2550。

```python

找到累计能量最小的路径，记录累计能量和路径

p = choosePath(left, mid, right) cumulate_energy[i,j] = (left, mid, right)[p+1]

如果当前像素是前景，则加入惩罚，即增加当前能量

if ground_array[i,j] == 1: cumulate_energy[i,j] += 2550 path[i,j] = j+p ```

当整张图遍历后， cumulate_energy 的最后一行最小的值对应的接缝就是整张图中能量最少的接缝。我们只需要从下往上通过之前保存好的 path 找出该路径即可。从下往上遍历的同时，一行行将删除当前行接缝像素后的图片赋值给新图片：

python for i in range(img.size[1]-1, -1, -1): bias = 0 # 遇到删除点前，偏移为0 for j in range(img.size[0]-1): if j == pos: # 遇到删除点，偏移加一 bias = 1 # 将该行除了删除点外的像素赋值给新图片 new_img[i,j,:] = img_array[i,j+bias,:] new_ground[i,j] = ground_array[i,j+bias] # 通过path查询上一行删除的像素点所在列 pos = path[i, pos]

如果需要保存gif，在将上述路径删除前先赋值上色再保存即可，代码基本一致，不再赘述。需要注意的是，在高度裁剪时，使用的是转置的图片，因此保存的图片需要再进行一次转置才能恢复原来的形状。转移与否是通过之前提到的函数参数列表中的 mode 控制的。