用 Go 实现图片尺寸的自动调节

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

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

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

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

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

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

它是如何确定哪些区域应该首先去掉呢？我们通过研究一个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 裁剪没有警告。正如上面的资源链接中的讨论那样，这可以探索许多不同功能的函数，这种处理方法处理具有非常严格的空间关系（例如人类的脸）的图片是非常困难的。这意味着这些东西可以被避免，但在这里可以先不讨论这些。

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