Seam Carving
Seam Carving 算法与一般的图像裁剪技术不同，它可以保持图像最具有信息量的部分。
根据提示，我们首先要计算每一个像素的能量值，能量值越高的像素越不可能被作为 Seam 被裁剪。计算能量值使用的函数是 dual-gradient energy，从图中可以看到，重要信息的边缘基本都是能量较高的点，这是因为根据该函数的定义，重要信息的边缘的点会有非常明显的颜色差异，因此颜色的梯度值比较大。
首先要计算出整个图的能量值，这个只需要按照函数的定义逐步处理就可以了。
private int yielding(Color c1, Color c2) {
// 计算两个颜色的R、G、B差值
int r = (c1.getRed() - c2.getRed());
int g = (c1.getGreen() - c2.getGreen());
int b = (c1.getBlue() - c2.getBlue());
// 代入公式计算结果
return r * r + g * g + b * b;
}
// energy of pixel at column x and row y
public double energy(int x, int y) {
if (x < 0 || x >= width() || y < 0 || y >= height()) {
throw new IllegalArgumentException();
}
// 如果是边界情况，按照定义，能量是 1000
final int DEFAULT_ENERGY = 1000;
if (x == 0 || y == 0 || x == width() - 1 || y == height() - 1) {
return DEFAULT_ENERGY;
}
// 计算纵向的梯度
int yGradient = yielding(picture.get(x, y - 1), picture.get(x, y + 1));
// 计算横向的梯度
int xGradient = yielding(picture.get(x - 1, y), picture.get(x + 1, y));
return Math.sqrt(xGradient + yGradient);
}接下来是在寻找 Seam 的过程中，基本上就是最短路径，区别在于：
- 权重不是在边上，而是在顶点上。
- 需要找一条最短路，从顶部的 W 个像素中的任意一个出发，到底部的 W 个像素中的任意一个。
- 这条最短路是没有循环的，同时它是连续的，即 (x, y) 的下一个点只能是 (x + 1, y + 1), (x, y + 1) 和 (x - 1, y + 1) 中的任意一个。
寻找最短路径的过程其实是一个动态规划的过程。
有一个动态最小能量的二维数组，dp[i][j] 表示在这个点的位置上，所有经过它的合法路径中能量总和最小的那条路所花费的能量值。初始化令第一行的所有值 dp[0][j] = energy[0][j]，对于某一个点 dp[x][y]，去寻找 dp[xx - 1][y - 1], dp[x][y - 1] 和 dp[x + 1][y - 1] 三者中最小的一个 possibleMin，则 dp[x][y] = possibleMin + energy[x][y]。
// 遍历二维数组
for (int row = 0; row < picture.height(); ++row) {
for (int col = 0; col < picture.width(); ++col) {
if (row == 0) {
// 如果这是最上面的一行，那么最小能量花费显然就是它自己的能量
dynamicMinimumEnergy[row][col] = energy[row][col];
} else {
/*
* 如果不在最上面的一行，那么能量有三种路径可能到达 左上（如果存在）、正上、右上（如果存在）
* 所以需要在三个中找到最小的，从那个像素到达这个像素的路径保证是最短的
*/
// 首先令可能的路径为正上的那个，因为这个必定存在
double possibleMinimumEnergy = dynamicMinimumEnergy[row - 1][col];
if (col - 1 >= 0) {
// 如果左上方不越界，就说明可能是，于是判断是不是比当前的更小，如果是比当前更小，就更新
if (possibleMinimumEnergy > dynamicMinimumEnergy[row - 1][col - 1]) {
possibleMinimumEnergy = dynamicMinimumEnergy[row - 1][col - 1];
}
}
if (col + 1 < picture.width()) {
// 右上方同理，如果存在，就判断
if (possibleMinimumEnergy > dynamicMinimumEnergy[row - 1][col + 1]) {
possibleMinimumEnergy = dynamicMinimumEnergy[row - 1][col + 1];
}
}
// 到这里求出了最短的那个路径，加上当前点的能量，就是累计最小能量
dynamicMinimumEnergy[row][col] = possibleMinimumEnergy + energy[row][col];
}
}
}在得到了 dp[][] 数组之后，遍历整个数组，就可以找到能量最小的那一条，复制每一个坐标值。
// 显然最短的路径如果存在，那么其一定满足最下方的那个像素有最小的能量密度总和
for (int row = picture.height() - 1; row >= 0; --row) {
// 从最后一行开始往前遍历，依次回溯出所有的路径
if (row == picture.height() - 1) {
// 如果在最后一行就遍历找到这一行中最小的总和
int minimumIndex = 0;
for (int col = 0; col < picture.width(); ++col) {
if (dynamicMinimumEnergy[row][col] < dynamicMinimumEnergy[row][minimumIndex]) {
minimumIndex = col;
}
}
// 这个点就是路径的最后一个点
verticalSeam[row] = minimumIndex;
} else {
// 如果不在最后一行，注意这里不能遍历整个第row行去找最小的，而只能是与刚才那个路径点相邻的那3个点中找最小的
// 显然其正上方的点一定存在，假设为最小的路径
verticalSeam[row] = verticalSeam[row + 1];
double possibleMinimumEnergy = dynamicMinimumEnergy[row][verticalSeam[row + 1]];
// 如果其左上方的坐标合法，就判断是不是最上方的点下来的
if (verticalSeam[row + 1] - 1 >= 0) {
if (dynamicMinimumEnergy[row][verticalSeam[row + 1] - 1] < possibleMinimumEnergy) {
possibleMinimumEnergy = dynamicMinimumEnergy[row][verticalSeam[row + 1] - 1];
verticalSeam[row] = verticalSeam[row + 1] - 1; // 如果是，就更新为左上方为前一个路径
}
}
// 右上方同理
if (verticalSeam[row + 1] + 1 < picture.width()) {
if (dynamicMinimumEnergy[row][verticalSeam[row + 1] + 1] < possibleMinimumEnergy) {
verticalSeam[row] = verticalSeam[row + 1] + 1;
}
}
}
}最后就是消去这条 Seam。
代码注意 picture = new Picture(picture)，不能留一个 reference，其他就没什么需要注意的了。
即使开了二维数组，也不会浪费时间和空间。
以上代码得分 100 分，其中时间复杂度获得 Bonus。完整代码可以移步：https://gitlab.jxtxzzw.com/jxtxzzw/coursera_assignments 或者 https://www.github.com/jxtxzzw/coursera_assignments