SeamCarving – jxtxzzw个人博客

SeamCarving

11月20日 · 2017年
jxtxzzw · · ·

这是jxtxzzw的个人博客普林斯顿大学的有一题编反采集功能启动程题。

这是jxtxzzw的个人博客

还蛮好玩的。

比较偏向实反采集功能启动用性,而不是傻傻的OJ题。

不太是最短路径,更像是动态规划。

没啥好多说的。

反采集功能启动

下面这段代码,代码复反采集功能启动文章由jxtxzzw原创制想文章由jxtxzzw原创象比较严重,其实H这是jxtxzzw的个人博客orizonal和Copyright Reserved @jxtxzzwVertical可以用一个转置,然后调用另一者,不应该是大段代码复制。

另外,运行效率可以提Powered by jxtxzzw高。

比如裁减掉若干条的这是jxtxzzw的个人博客时候,只要重新计算那边附近的一些能量密度就可以了,不用整个n*m推欢迎访问jxtxzzw个人博客翻重来。

中间的pic请勿采集与复制,转载请注明出处ture保留也是,不需要所有的中间Copyright Reserved @jxtxzzw过程都neCopyright Reserved @jxtxzzww一个对象出来,中间可以用数组维护Powered by jxtxzzw请勿采集与复制,转载请注明出处最后加new一个。

public class Main {
    public static void main(StCopyright Reserved @jxtxzzwring[] args) {
        // 从命令行输入获取信息,并对文件、对象进行必要初始化行为
        String fileName = args[0];
        int widthCuttingPercent = Integer.parseInt(args[1]);
        int heightCuttingPercent = Integer.parseInt(args[2]);
        File file = new File(fileName);
        Picture picture = new Picture(file);
        SeamCarver sc = new SeamCarver(picture);

        // 根据裁剪比例,计算需要进行多少次remove操作(因为每次去掉一条Seam,相当于像素减去1)
        int widthCutting = (int) (widthCuttingPercent / (double) 100 * picture.width());
        int heightCutting = (int) (heightCuttingPercent / (double) 100 * picture.height());

        // 每次去掉一条Seam,遍历若干次后就是需要的裁剪比例
        while (widthCutting-- != 0)
            sc.removeVerticalSeam(sc.findVerticalSeam());
        while (heightCutting-- != 0)
            sc.removeHorizontalSeam(sc.findHorizontalSeam());
        // 显示裁剪后的图片
        sc.picture().show();

    }
}
public 请勿采集与复制,转载请注明出处class SeamCarver {

    Picture picture; // 图片
    double[][] energy; // 能量密度

    /**
     * create a seam carver object based on the given picture
     * 
     * @param picture
     *            需要处理的图片
     */
    public SeamCarver(Picture picture) {
        this.picture = picture;
        energy = new double[picture.height()][picture.width()]; // 根据图片长宽,初始化数组长度
    }

    /**
     * current picture
     * 
     * @return 图片
     */
    public Picture picture() {
        return picture;
    }

    /**
     * width of current picture
     * 
     * @return 图片的宽度
     */
    public int width() {
        return picture.width();
    }

    /**
     * height of current picture
     * 
     * @return 图片的高度
     */
    public int height() {
        return picture.height();
    }

    /**
     * energy of pixel at column x and row y
     * 
     * @param x
     *            第x列
     * @param y
     *            第y行
     * @return 第x列第y行的像素的能量密度
     */
    public double energy(int x, int y) {
        int col;
        int row;

        // 取出这个像素上面那个像素的RGB颜色
        col = x;
        row = y - 1;
        // 如果是边界情况,特殊处理
        if (row < 0)
            row = picture.height() - 1;
        // 取出颜色
        Color colorUp = picture.get(col, row);

        // 取出这个像素下面那个像素的RGB颜色,与上面类似
        col = x;
        row = y + 1;
        if (row == picture.height())
            row = 0;
        Color colorDown = picture.get(col, row);

        // 计算纵向的梯度(gradient)
        int yGradient = yielding(colorUp, colorDown);

        // 取出左边和右边的颜色,与取出上下颜色是类似的
        col = x - 1;
        row = y;
        if (col < 0)
            col = picture.width() - 1;
        Color colorLeft = picture.get(col, row);

        col = x + 1;
        row = y;
        if (col == picture.width())
            col = 0;
        Color colorRight = picture.get(col, row);

        // 计算横向的梯度(gradient)
        int xGradient = yielding(colorLeft, colorRight);

        // 梯度之和就是能量密度
        return xGradient + yGradient;

    }

    /**
     * 计算所有像素点的能量密度
     */
    private void getAllEnergy() {
        // 双重循环,遍历二维数组,求出每个像素的能量密度
        for (int i = 0; i < picture.height(); ++i) {
            for (int j = 0; j < picture.width(); ++j) {
                energy[i][j] = energy(j, i);
                /*
                 * 这里需要特别注意一下: energy[][]数组的横纵坐标是[i][j] 而energy()函数的参数是(j,i)
                 */
            }
        }
    }

    /**
     * 根据给定的颜色,计算dual-gradient energy公式
     * 
     * @param c1
     *            颜色1
     * @param c2
     *            颜色2
     * @return 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;

    }

    /**
     * sequence of indices for vertical seam
     * 
     * @return 一个数组,表示垂直的一条可切割的最短路径
     */
    public int[] findVerticalSeam() {

        // 计算所有像素的能量密度
        getAllEnergy();

        // 动态最小能量[i][j]表示到[i][j]点的最小花费
        double[][] dynamicMinimumEnergy = new double[picture.height()][picture.width()];

        // 遍历二维数组
        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];
                }
            }
        }
        // 二维数组遍历结束,得到所有的能量路径总和
        int[] verticalSeam = new int[picture.height()]; // 存放最短的一条路径

        // 显然最短的路径如果存在,那么其一定满足最下方的那个像素有最小的能量密度总和
        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) {
                        possibleMinimumEnergy = dynamicMinimumEnergy[row][verticalSeam[row + 1] + 1];
                        verticalSeam[row] = verticalSeam[row + 1] + 1;
                    }
                }
            }
        }
        // 循环结束,得到整个路径数组
        return verticalSeam;

    }

    /**
     * sequence of indices for horizontal seam
     * 
     * @return 一个数组,表示水平的一条可切割的最短路径
     */
    // 水平切割与垂直切割类似,这里从略,详细注释见垂直切割
    // 需要注意的是,这里的矩阵相当于做了一个转置,所以要注意row和col的加一减一、以及height和width的改变
    public int[] findHorizontalSeam() {
        getAllEnergy();
        double[][] dynamicMinimumEnergy = new double[picture.height()][picture.width()];
        for (int col = 0; col < picture.width(); ++col) {
            for (int row = 0; row < picture.height(); ++row) {

                if (col == 0) {
                    dynamicMinimumEnergy[row][col] = energy[row][col];
                } else {
                    double possibleMinimumEnergy = dynamicMinimumEnergy[row][col - 1];
                    if (row - 1 >= 0) {
                        if (possibleMinimumEnergy > dynamicMinimumEnergy[row - 1][col - 1]) {
                            possibleMinimumEnergy = dynamicMinimumEnergy[row - 1][col - 1];
                        }
                    }
                    if (row + 1 < picture.height()) {
                        if (possibleMinimumEnergy > dynamicMinimumEnergy[row + 1][col - 1]) {
                            possibleMinimumEnergy = dynamicMinimumEnergy[row + 1][col - 1];
                        }
                    }
                    dynamicMinimumEnergy[row][col] = possibleMinimumEnergy + energy[row][col];
                }
            }

        }

        int[] horizontalSeam = new int[picture.width()];

        for (int col = picture.width() - 1; col >= 0; --col) {
            if (col == picture.width() - 1) {
                int minimumIndex = 0;
                for (int row = 0; row < picture.height(); ++row) {
                    if (dynamicMinimumEnergy[row][col] < dynamicMinimumEnergy[minimumIndex][col]) {
                        minimumIndex = row;
                    }
                }
                horizontalSeam[col] = minimumIndex;
            } else {
                horizontalSeam[col] = horizontalSeam[col + 1];
                double possibleMinimumEnergy = dynamicMinimumEnergy[horizontalSeam[col + 1]][col];
                if (horizontalSeam[col + 1] - 1 >= 0) {
                    if (dynamicMinimumEnergy[horizontalSeam[col + 1] - 1][col] < possibleMinimumEnergy) {
                        possibleMinimumEnergy = dynamicMinimumEnergy[horizontalSeam[col + 1] - 1][col];
                        horizontalSeam[col] = horizontalSeam[col + 1] - 1;
                    }
                }
                if (horizontalSeam[col + 1] + 1 < picture.height()) {
                    if (dynamicMinimumEnergy[horizontalSeam[col + 1] + 1][col] < possibleMinimumEnergy) {
                        possibleMinimumEnergy = dynamicMinimumEnergy[horizontalSeam[col + 1] + 1][col];
                        horizontalSeam[col] = horizontalSeam[col + 1] + 1;
                    }
                }

            }
        }

        return horizontalSeam;

    }

    /**
     * remove vertical seam from current picture
     * 
     * @param seam
     *            一个数组,表示一条给定的路径
     */
    public void removeVerticalSeam(int[] seam) {
        // 首先新建一个图片,宽度减1、高度不变
        Picture newPicture = new Picture(picture.width() - 1, picture.height());
        // 从0到高度,依次复制第row行
        for (int row = 0; row < picture.height(); ++row) {
            // 注意到前面seam[row]列照常复制
            for (int col = 0; col < seam[row]; ++col) {
                newPicture.set(col, row, picture.get(col, row));
            }
            // 后面的每一个,因为删掉了一条Seam,所以就有一个单位的位移
            for (int col = seam[row]; col < picture.width() - 1; ++col) {
                newPicture.set(col, row, picture.get(col + 1, row));
            }
        }
        // 把新图片保存下来
        picture = newPicture;
    }

    /**
     * remove horizontal seam from current picture
     * 
     * @param seam
     *            一个数组,表示一条给定的路径
     */
    // 与删除垂直Seam类似
    public void removeHorizontalSeam(int[] seam) {
        Picture newPicture = new Picture(picture.width(), picture.height() - 1);
        for (int col = 0; col < picture.width(); ++col) {
            for (int row = 0; row < seam[col]; ++row) {
                newPicture.set(col, row, picture.get(col, row));
            }
            for (int row = seam[col]; row < picture.height() - 1; ++row) {
                newPicture.set(col, row, picture.get(col, row + 1));
            }
        }
        picture = newPicture;
    }

//  public void debug() {
//      getAllEnergy();
//      for (int i = 0; i < energy.length; ++i) {
//          for (int j = 0; j < energy[i].length; ++j) {
//              System.out.printf("%.1f%c", energy[i][j], j == energy[i].length - 1 ? '\n' : ' ');
//          }
//      }
//  }

}
0 条回应
验证码
输入运算符及数字使等式成立
{{comment.validate_num1}} = {{comment.validate_num2}}
点赞确定
退出登录?
取消 确定