英文原文：
Dynamic Image Resizing with Go
我刚上大学那会儿，课上到最后几分钟的时候，我会翘课奔到另外一个我几乎不怎么了解的班上去蹭课。碰巧，那个班上的课是我觉得最棒的课之一 ——计算机视觉。此外，那个课上介绍了一种很赞的算法：Seam Carving，精雕细琢。
这个算法大概是酱紫的：一般我们想改变图片大小的时候，会采用裁剪和缩放的方式，这样一来，图片会损失很多重要信息，在处理过程中，图片甚至被歪曲。那么，我们怎么才能找到图片中视觉信息最少的部分，要调整图片大小的时候，只把这部分移除掉是不是可以呢？
上图展示给我们一副很美的画面：开阔的蓝天，俊逸的城堡。但是，对我们来说，图有点大，我们得往小调一下。怎么弄呢？
第一个进入我们大脑的想法是改变原始图像的尺寸。改变之后的图像（如上图）变小了，而且所有的主要信息（左边的人，右边的城堡）都还在新的图像上。但是，改变后的图像有一个问题，右边城堡变形了，所以这张改变之后的图像就显得不太完美了。在大部分情况下，这种图像的改变是可以接受的，但是如果我们试图提供一个高质量的图像的话，这种改变就不能接受了。
另外一个想法是切掉原始图像的一部分以适应我们新的尺寸（如上图）。基本上我们可以理解发现新的图像有一个致命的缺点，一半的城堡被切掉了，而且左边的人现在也太靠近图像的边缘。相对于原始图像，新的图像确实包含了大部分原始图像的信息，但是同时也丢失了很多的重要信息。我个人就比较喜欢城堡右边的那个炮楼，希望在新的图像中可以保留这个炮楼。幸运的是，我们可以做到这点。
让我们看上面的图像，图像的尺寸已经减小了，在新的图像中，城堡是完整的，并且左边的人也不再位于图像的边缘。上面的这张新的图像是经过一个叫做Seam Carving的算法进行处理过的。这个算法将动态监测原始图像，发现原始图像中不太重要的部分，并且将这部分不太重要的图像有限切除掉。在上面的新的图像中，你可以发现这个算法把城堡右边的蓝天给切除了，而且还切除了部分位于原始图像中间部分的蓝天。
其它翻译版本 (1)
加载中
它是如何确定哪些区域应该首先去掉呢？我们通过研究一个Go语言实现的算法来找到答案。我们研究算法的各个步骤，以及每一步对下面的图片产生的效果。这个算法虽然是用来减少图像高度的，但是也可以很容易地修改用来减小图像的宽度。
该算法包含了三个主要的步骤: 从原图生成能量图、 定位找出最低能量消耗的 “seam" , 将找出的”seam“从图像中去除.
// ReduceHeight 使用seam carving算法，减少给定的具有n个像素点的图像的高度.
func ReduceHeight(im image.Image, n int) image.Image {
energy := GenerateEnergyMap(im)
seam := GenerateSeam(energy)
return RemoveSeam(im, seam)
}
能量图计算图像中的一个点包含了多少“能量”，也就是说该点包含了多少信息。低能量的像素同周围像素融合在一起，去掉它们对整个图的影响比较小。因此能量图的计算，采用了考虑图像水平和垂直的梯度值的方法来进行。通过这种方法产生的能量图，其中每个点代表了原始图像中的对应点与周边点相似或不同的程度。
幸运的是，这可以通过一个特定的滤波器（这里采用一个sobel滤波器）对输入图像进行卷积计算。我在这里不详细讨论卷积，但要知道一个重要的事情是，通过将sobel滤波器应用到一个输入图像的灰度图像上（通常可选的平滑滤波器，如高斯滤波器，来获得灰度图像），我们可以很容易地获得的输入图像的梯度。要做到这一点我使用了功能强大的GIFT库。
// GenerateEnergyMap 应用输入灰度和sobel滤波器到输入图像上，生成能量图.
func GenerateEnergyMap(im image.Image) image.Image {
g := gift.New(gift.Grayscale(), gift.Sobel())
res := image.NewRGBA(im.Bounds())
g.Draw(res, im)
return res
}
正如所期望的，高能量的区域一般都是边缘，低能量的区域均是由少量相似颜色（天空）扩展而来的。从这里我们可以估计到，减少图片的高度，减少的部分应该大部分都是在天空区域，其他部分保持不变。
下一步决定哪些像素需要进行移除。我们将一个像素一个像素的减少图像的高度，就需要一列一列的找那个像素能够移除。我们希望找到一系列的具有尽可能最低总能量的像素集合，移除掉这些seam，对整个图片产生影响最小。可以按如下两步来确定最佳去除像素点：
// GenerateSeam 返回最优的可以消除的水平 seam.
func GenerateSeam(im image.Image) Seam {
mat := GenerateCostMatrix(im)
return FindLowestCostSeam(mat)
}
第一步是用一个八连通区域像素去水平滤波整个图像，获得包含“seams"的最低积累能量的消耗矩阵。
这次我们首先看如下代码：
// GenerateCostMatrix 从图像左端到每一个像素，创建一个表明最低消耗seam矩阵.
//
// mat[x][y] 是从图像左端到列x行y像素点的seam的累积能量.
func GenerateCostMatrix(im image.Image) [][]float64 {
min, max := im.Bounds().Min, im.Bounds().Max
height, width := max.Y-min.Y, max.X-min.X
mat := make([][]float64, width)
for x := min.X; x < max.X; x++ {
mat[x-min.X] = make([]float64, height)
}
// Initialize first column of matrix
for y := min.Y; y < max.Y; y++ {
e, _, _, a := im.At(0, y).RGBA()
mat[0][y-min.Y] = float64(e) / float64(a)
}
updatePoint := func(x, y int) {
e, _, _, a := im.At(x, y).RGBA()
up, down := math.MaxFloat64, math.MaxFloat64
left := mat[x-1][y]
if y != min.Y {
up = mat[x-1][y-1]
}
if y < max.Y-1 {
down = mat[x-1][y+1]
}
val := math.Min(float64(left), math.Min(float64(up), float64(down)))
mat[x][y] = val + (float64(e) / float64(a))
}
// Calculate the remaining columns iteratively
for x := min.X + 1; x < max.X; x++ {
for y := min.Y; y < max.Y; y++ {
updatePoint(x, y)
}
}
return mat
}
在上面的函数中，我们开始创建一个同图像具有相同维数的矩阵。我们从最左列到最右列，不断的计算每一个像素的最低累积能量。在一列中的每一个像素，选取其左边或者左上或者左下三个点中最小积累能量的点，然后将该点的能量累加到选取的点的积累能量上。这种做法，使得我们能够不是那么死板的只能线性移除seam，带来更大的灵活性，获得更好的清除效果。
然后我们就可以利用这个矩阵来确定哪些像素可以被移除。我们从一个包含每列一个点的seam开始，找到最小成本的seam的开始。
type Seam []Point
type Point struct {
X, Y int
}
// FindLowestCostSeam uses an cost matrix to find the optimal seam for removal.
func FindLowestCostSeam(mat [][]float64) Seam {
width, height := len(mat), len(mat[0])
seam := make([]Point, width)
min, y := math.MaxFloat64, 0
for ind, val := range mat[width-1] {
if val < min {
min = val
y = ind
}
}
seam[width-1] = Point{X: width - 1, Y: y}然后我们从右到左遍历矩阵。每一次循环遍历，查看该点、以及其上和其下三点，将最小的积累能力赋值给该seam。
for x := width - 2; x >= 0; x-- {
left := mat[x][y]
up, down := math.MaxFloat64, math.MaxFloat64
if y > 0 {
up = mat[x][y-1]
}
if y < height-1 {
down = mat[x][y+1]
}
if up <= left && up <= down {
seam[x] = Point{X: x, Y: y - 1}
y = y - 1
} else if left <= up && left <= down {
seam[x] = Point{X: x, Y: y}
y = y
} else {
seam[x] = Point{X: x, Y: y + 1}
y = y + 1
}
}我们通过在图像上画出seam来可视化的检查我们的程序逻辑，确认了seam是通过了我们所期待的区域。下面的图像是上面代码生成的第一个seam，用红色线画在输入图像上。
因此算法就是通过编写一个函数，该函数创建一个新的去掉了计算出来的seam的图像，并且将ReduceHeight函数放到一个循环中去，我们就可以不断的通过消除最小能量的seam来放大缩小一个图像。
// RemoveSeam creates a copy of the provided image, with the pixels at
// the points in the provided seam removed.
func RemoveSeam(im image.Image, seam Seam) image.Image {
b := im.Bounds()
out := image.NewRGBA(image.Rect(0, 0, b.Dx(), b.Dy()-1))
min, max := b.Min, b.Max
for _, point := range seam {
x := point.X
for y := min.Y; y < max.Y; y++ {
if y == point.Y {
continue
}
if y > point.Y {
out.Set(x, y-1, im.At(x, y))
} else {
out.Set(x, y, im.At(x, y))
}
}
}
return out
}
// ReduceHeight uses seam carving to reduce height of given image n pixels.
func ReduceHeight(im image.Image, n int) image.Image {
for x := 0; x < n; x++ {
energy := GenerateEnergyMap(im)
seam := GenerateSeam(energy)
im = RemoveSeam(im, seam)
}
return im
}
在这里是清除了50个像素后的效果。我们可以看到，哪些具有最少信息的区域（天空）已经清除掉，而哪些有船，水和建筑的区域没有改变。因为天空基本上是一致的，清除这些区域没有太大的影响。
最终的实现代码可以在 Github 上找到，所有函数均能被导出，可以按你想要的方式去研究修改。
这篇文章只是浅显地介绍了 seam 的裁剪。关于这个话题，我强烈推荐你阅读原创的论文，或者视频，这些算法证明了许多应用的可能性。这些应用包括对象移除，增加图像的尺寸，或者更多。
这不是说 seam 裁剪没有警告。正如上面的资源链接中的讨论那样，这可以探索许多不同功能的函数，这种处理方法处理具有非常严格的空间关系（例如人类的脸）的图片是非常困难的。这意味着这些东西可以被避免，但在这里可以先不讨论这些。
如果你有任何评论或关于这篇文章的问题，请联系我们，进行算法或其他你关心的任何讨论。
本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接。
2KB翻译工作遵照
CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。
2KB项目（www.2kb.com，源码交易平台）,提供担保交易、源码交易、虚拟商品、在家创业、在线创业、任务交易、网站设计、软件设计、网络兼职、站长交易、域名交易、链接买卖、网站交易、广告买卖、站长培训、建站美工等服务
