我刚上大学那会儿，课上到最后几分钟的时候，我会翘课奔到另外一个我几乎不怎么了解的班上去蹭课。碰巧，那个班上的课是我觉得最棒的课之一 ——计算机视觉。此外，那个课上介绍了一种很赞的算法：Seam Carving，精雕细琢。

这个算法大概是酱紫的：一般我们想改变图片大小的时候，会采用裁剪和缩放的方式，这样一来，图片会损失很多重要信息，在处理过程中，图片甚至被歪曲。那么，我们怎么才能找到图片中视觉信息最少的部分，要调整图片大小的时候，只把这部分移除掉是不是可以呢？

上图展示给我们一副很美的画面：开阔的蓝天，俊逸的城堡。但是，对我们来说，图有点大，我们得往小调一下。怎么弄呢？

第一个进入我们大脑的想法是改变原始图像的尺寸。改变之后的图像（如上图）变小了，而且所有的主要信息（左边的人，右边的城堡）都还在新的图像上。但是，改变后的图像有一个问题，右边城堡变形了，所以这张改变之后的图像就显得不太完美了。在大部分情况下，这种图像的改变是可以接受的，但是如果我们试图提供一个高质量的图像的话，这种改变就不能接受了。

另外一个想法是切掉原始图像的一部分以适应我们新的尺寸（如上图）。基本上我们可以理解发现新的图像有一个致命的缺点，一半的城堡被切掉了，而且左边的人现在也太靠近图像的边缘。相对于原始图像，新的图像确实包含了大部分原始图像的信息，但是同时也丢失了很多的重要信息。我个人就比较喜欢城堡右边的那个炮楼，希望在新的图像中可以保留这个炮楼。幸运的是，我们可以做到这点。

让我们看上面的图像，图像的尺寸已经减小了，在新的图像中，城堡是完整的，并且左边的人也不再位于图像的边缘。上面的这张新的图像是经过一个叫做Seam Carving的算法进行处理过的。这个算法将动态监测原始图像，发现原始图像中不太重要的部分，并且将这部分不太重要的图像有限切除掉。在上面的新的图像中，你可以发现这个算法把城堡右边的蓝天给切除了，而且还切除了部分位于原始图像中间部分的蓝天。

它是如何确定哪些区域应该首先去掉呢？我们通过研究一个Go语言实现的算法来找到答案。我们研究算法的各个步骤，以及每一步对下面的图片产生的效果。这个算法虽然是用来减少图像高度的，但是也可以很容易地修改用来减小图像的宽度。

该算法包含了三个主要的步骤: 从原图生成能量图、 定位找出最低能量消耗的 “seam" , 将找出的”seam“从图像中去除.

能量图计算图像中的一个点包含了多少“能量”，也就是说该点包含了多少信息。低能量的像素同周围像素融合在一起，去掉它们对整个图的影响比较小。因此能量图的计算，采用了考虑图像水平和垂直的梯度值的方法来进行。通过这种方法产生的能量图，其中每个点代表了原始图像中的对应点与周边点相似或不同的程度。
幸运的是，这可以通过一个特定的滤波器（这里采用一个sobel滤波器）对输入图像进行卷积计算。我在这里不详细讨论卷积，但要知道一个重要的事情是，通过将sobel滤波器应用到一个输入图像的灰度图像上（通常可选的平滑滤波器，如高斯滤波器，来获得灰度图像），我们可以很容易地获得的输入图像的梯度。要做到这一点我使用了功能强大的GIFT库。

正如所期望的，高能量的区域一般都是边缘，低能量的区域均是由少量相似颜色（天空）扩展而来的。从这里我们可以估计到，减少图片的高度，减少的部分应该大部分都是在天空区域，其他部分保持不变。

下一步决定哪些像素需要进行移除。我们将一个像素一个像素的减少图像的高度，就需要一列一列的找那个像素能够移除。我们希望找到一系列的具有尽可能最低总能量的像素集合，移除掉这些seam，对整个图片产生影响最小。可以按如下两步来确定最佳去除像素点：

第一步是用一个八连通区域像素去水平滤波整个图像，获得包含“seams"的最低积累能量的消耗矩阵。

这次我们首先看如下代码：

在上面的函数中，我们开始创建一个同图像具有相同维数的矩阵。我们从最左列到最右列，不断的计算每一个像素的最低累积能量。在一列中的每一个像素，选取其左边或者左上或者左下三个点中最小积累能量的点，然后将该点的能量累加到选取的点的积累能量上。这种做法，使得我们能够不是那么死板的只能线性移除seam，带来更大的灵活性，获得更好的清除效果。

然后我们就可以利用这个矩阵来确定哪些像素可以被移除。我们从一个包含每列一个点的seam开始，找到最小成本的seam的开始。

然后我们从右到左遍历矩阵。每一次循环遍历，查看该点、以及其上和其下三点，将最小的积累能力赋值给该seam。

我们通过在图像上画出seam来可视化的检查我们的程序逻辑，确认了seam是通过了我们所期待的区域。下面的图像是上面代码生成的第一个seam，用红色线画在输入图像上。

因此算法就是通过编写一个函数，该函数创建一个新的去掉了计算出来的seam的图像，并且将ReduceHeight函数放到一个循环中去，我们就可以不断的通过消除最小能量的seam来放大缩小一个图像。

在这里是清除了50个像素后的效果。我们可以看到，哪些具有最少信息的区域（天空）已经清除掉，而哪些有船，水和建筑的区域没有改变。因为天空基本上是一致的，清除这些区域没有太大的影响。

最终的实现代码可以在 Github 上找到，所有函数均能被导出，可以按你想要的方式去研究修改。

这篇文章只是浅显地介绍了 seam 的裁剪。关于这个话题，我强烈推荐你阅读原创的论文，或者视频，这些算法证明了许多应用的可能性。这些应用包括对象移除，增加图像的尺寸，或者更多。

这不是说 seam 裁剪没有警告。正如上面的资源链接中的讨论那样，这可以探索许多不同功能的函数，这种处理方法处理具有非常严格的空间关系（例如人类的脸）的图片是非常困难的。这意味着这些东西可以被避免，但在这里可以先不讨论这些。

如果你有任何评论或关于这篇文章的问题，请联系我们，进行算法或其他你关心的任何讨论。