Programming Assignment 2 Seam Carving 暴力实现

Programming Assignment 2 Seam Carving 暴力实现

Robert Sedgewick教授在Coursera上开了一门算法课,这是图论中的一道编程作业题

问题概述

图像由像素构成,可以看成是一张二维数组,其中的存储着Color,这样每个位置都有相应的颜色,就可以表示一张图片了。 这道题目的目的是resize图像,每次删除一行或一列颜色值最不明想的像素。

图像在二维数组中的表示 :

  (255,101,51)        (255,101,153)       (255,101,255)  
  (255,153,51)        (255,153,153)       (255,153,255)  
  (255,203,51)        (255,204,153)       (255,205,255)  
  (255,255,51)        (255,255,153)       (255,255,255)  

解题思路

能量函数

如何界定某个像素是否明显,可以被删除呢?

    是否明显是由周围的像素决定的,基于此有公式
    pixel(x,y)的能量函数表示为:
    Δx2(x, y) + Δy2(x, y)
    其中,Δx2(x, y) = Rx(x, y)2 + Gx(x, y)2 + Bx(x, y)2
    Rx、Gx、Bx分别为为pixel(x+1,y)与pixel(x-1,y)对应RGB的差值。
    Δy2(x, y)同理。

最短路径

我想到的暴力求解的笨办法是,将图像的位置映射成唯一的整型索引,并算出其能量函数的值,加上起始终点两个虚拟位置(它门的能量值都为0)以此构造一张加权有向图。找出起始点到终点的最短路径。

顶点的权重

加权有向图的权重是指边的权重,而上面构造的图形的权重值是在顶点中表示的,这需要转化为边的权重。这很简单,只需要将将一条边的两个顶点的权重相加表示成边的权重即可。

算法实现

能量函数

    private Picture mPicture; 
    private static final double BORDER_ENERGY = 255.0 * 255 * 3;
    /**
     * 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 IndexOutOfBoundsException();
        if (isBorder(x, y)) return BORDER_ENERGY;

        return energyFun(mPicture.get(x - 1, y), mPicture.get(x + 1, y))
                + energyFun(mPicture.get(x, y - 1), mPicture.get(x, y + 1));

    }
      private double energyFun(Color color1, Color color2) {

        int r1 = color1.getRed();
        int g1 = color1.getGreen();
        int b1 = color1.getBlue();

        int r2 = color2.getRed();
        int g2 = color2.getGreen();
        int b2 = color2.getBlue();

        int delta = square(r1 - r2) + square(g1 - g2) + square(b1 - b2);

        return delta;
    }

    private int square(int i) {
        return i * i;
    }

    private boolean isBorder(int x, int y) {
        if (x == 0 || x == mPicture.width() - 1) return true;
        else if (y == 0 || y == mPicture.height() - 1) return true;
        else return false;

    }

找到垂直方向的最短路径

    /**
     * sequence of indices for vertical seam
     *
     * @return
     */
    public int[] findVerticalSeam() {
        int[] result = new int[height()];

        //解法一:构造图
        EdgeWeightedDigraph verticalG = buildVerticalGraph(width(), height());
        AcyclicSP sp = new AcyclicSP(verticalG, 0);
        Iterable<DirectedEdge> edges = sp.pathTo(verticalG.V() - 1);
        int len = 0;
        for (DirectedEdge e : edges) {
            //StdOut.println(e); //调试 打印路径

            int v = e.from();
            if (v != 0 && v != (verticalG.V() - 1)) {
                result[len++] = convertToX(v);
            }
        }

        return result;
    }

     /**
     * 将图中标示的点映射到相应的x值
     *
     * @param v
     * @return
     */
    private int convertToX(int v) {
        return (v - 1) % width();
    }


        /**
     * //构造图,将二维矩阵转化为唯一标示的整数作为图的顶点
     * //顶点的权重转化为边的权重:一条边两个顶点的权重之和
     * //上下两个虚拟点的energy为0,这样把最终算出来的总权重之和除以2就是原来最短路径的顶点的权重之和了
     *
     * @param width
     * @param height
     */
    private EdgeWeightedDigraph buildVerticalGraph(int width, int height) {

        EdgeWeightedDigraph G = new EdgeWeightedDigraph(width * height + 2);
        for (int i = 0; i < G.V() - 1; i++) {  //上方的起始虚拟点
            if (i == 0) {
                for (int j = 1; j <= width; j++) {
                    G.addEdge(new DirectedEdge(0, j, 0 + energy(j - 1, 0)));
                }
            } else if (i >= G.V() - 1 - width) {  //最下方的所有点连接 下方的终点虚拟点
                G.addEdge(new DirectedEdge(i, G.V() - 1, energy((i - 1) % width, height - 1) + 0));
            } else {
                int fromX = (i - 1) % width;
                int fromY = (i - 1) / width;
                int toX = fromX; //正下方
                int toY = fromY + 1;
                if ((i - 1) % width == 0) { //最左边的点(以排除最下方的最左侧的点)
                    toX = fromX; //正下方
                    toY = fromY + 1;
                    double fromWeight = energy(fromX, fromY);
                    double toWeight = energy(toX, toY);
                    G.addEdge(new DirectedEdge(i, i + width, fromWeight + toWeight));

                    toX = fromX + 1; //右下方
                    toY = fromY + 1;
                    toWeight = energy(toX, toY);
                    G.addEdge(new DirectedEdge(i, i + width + 1, fromWeight + toWeight));
                } else if ((i - 1) % width == (width - 1)) {//最右边的点((以排除最下方的点)
                    toX = fromX; //正下方
                    toY = fromY + 1;
                    double fromWeight = energy(fromX, fromY);
                    double toWeight = energy(toX, toY);
                    G.addEdge(new DirectedEdge(i, i + width, fromWeight + toWeight));

                    toX = fromX - 1; //左下方
                    toY = fromY + 1;
                    toWeight = energy(toX, toY);
                    G.addEdge(new DirectedEdge(i, i + width - 1, fromWeight + toWeight));
                } else { //一般的点都有3个有向边发出((以排除最下方的)
                    toX = fromX; //正下方
                    toY = fromY + 1;
                    double fromWeight = energy(fromX, fromY);
                    double toWeight = energy(toX, toY);
                    G.addEdge(new DirectedEdge(i, i + width, fromWeight + toWeight));

                    toX = fromX - 1; //左下方
                    toY = fromY + 1;
                    toWeight = energy(toX, toY);
                    G.addEdge(new DirectedEdge(i, i + width - 1, fromWeight + toWeight));

                    toX = fromX + 1; //右下方
                    toY = fromY + 1;
                    toWeight = energy(toX, toY);
                    G.addEdge(new DirectedEdge(i, i + width + 1, fromWeight + toWeight));
                }
            }


        }
        return G;
    }

从图像中删除垂直最短路径(即最不明显的像素)

     /**
     * remove vertical seam from current picture
     *
     * @param seam
     */
    public void removeVerticalSeam(int[] seam) {
        if (height() <= 1)
            throw new java.lang.IllegalArgumentException();
        Picture pic = new Picture(width() - 1, height());
        for (int h = 0; h < pic.height(); h++) {

            for (int w = 0; w < seam[h]; w++) {
                pic.set(w, h, mPicture.get(w, h));
            }

            for (int w = seam[h] + 1; w < width(); w++) {
                pic.set(w - 1, h, mPicture.get(w, h));

            }
        }
        this.mPicture = pic;
    }

后记

提交了n次,虽然通过了正确性测试,但是timing的5个测试全部没有通过,看样子此算法还是太过复杂了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏搞前端的李蚊子

Html5模拟通讯录人员排序(sen.js)

// JavaScript Document  var PY_Json_Str = ""; var PY_Str_1 = ""; var PY_Str_...

5906
来自专栏草根专栏

适合在Markdown里面使用的emoji

因为Markdown里面加颜色需要写html style, 所以对于一些标题, 还是用一下emoji吧: RED APPLE (&#x1F34E;): ? GR...

2714
来自专栏技术之路

wpf键盘记录器

很简单的一个wpf键盘记录器 ? 这个程序我一样用了全局勾子,之前用的都是winform上运行了,前一段时间 在国外的论坛上逛看到了一个wpf能用的就做了一个小...

2015
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2312
来自专栏码匠的流水账

聊聊hikari连接池的isAllowPoolSuspension

本文主要研究一下hikari连接池的isAllowPoolSuspension属性

1442
来自专栏码匠的流水账

聊聊kafka consumer offset lag increase异常

本文主要解析一下遇到的一个kafka consumer offset lag不断增大的异常。

741
来自专栏我和未来有约会

简练的视图模型 ViewModel

patterns & practices Developer Center 发布了 Unity Application Block 1.2 for Silver...

2179
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

702
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

781
来自专栏码匠的流水账

spring security reactive获取security context

本文主要研究下reactive模式下的spring security context的获取。

1792

扫码关注云+社区