作业|学习资料|算法|题解

SeamCarving

凝神长老 · 11月20日 · 2017年 · · · · 742次已读

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 的过程中,基本上就是最短路径,区别在于:

  1. 权重不是在边上,而是在顶点上。
  2. 需要找一条最短路,从顶部的 W 个像素中的任意一个出发,到底部的 W 个像素中的任意一个。
  3. 这条最短路是没有循环的,同时它是连续的,即 (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

0 0 投票
Article Rating
订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论