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 条评论
登录 后参与评论

相关文章

来自专栏机器学习原理

我的机器学习numpy篇何为ndarray?ndarry创建生成正态分布ndarry属性修改形状ndarry运算ndarry切片矩阵转置聚合函数

前言: numpy是以矩阵为基础的数学计算模块,其基础为多维数组为ndarray 官方文档:(https://docs.scipy.org/doc/nump...

3828
来自专栏数据结构与算法

洛谷P3209 [HNOI2010]PLANAR(2-SAT)

题目描述 若能将无向图G=(V,E)画在平面上使得任意两条无重合顶点的边不相交,则称G是平面图。判定一个图是否为平面图的问题是图论中的一个重要问题。现在假设你要...

3286
来自专栏CVPy

利用 Python 优雅地可视化数据

最近看《机器学习系统设计》的前两章,学到了一些用Matplotlib进行数据可视化的方法。在这里整理一下。

8110
来自专栏林冠宏的技术文章

自己在总结前人经验下弄的几个opencv封装函数

第一个是增加对比度的函数,就是变亮。 1 IplImage* EqualizeHistColorImage(IplImage *pImage) 2 { 3...

1847
来自专栏HansBug's Lab

1295: [SCOI2009]最长距离

1295: [SCOI2009]最长距离 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 960  Solve...

2824
来自专栏移动开发面面观

OpenGL ES——导入.stl格式的3D模型

1664
来自专栏技术专栏

Python3入门机器学习(三)- matplotlib基础与简单应用

2252
来自专栏机器之心

教程 | 如何使用TensorFlow中的高级API:Estimator、Experiment和Dataset

选自Medium 作者:Peter Roelants 机器之心编译 参与:李泽南、黄小天 近日,背景调查公司 Onfido 研究主管 Peter Roelant...

5897
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列七:基于SSE实现的极速的矩形核腐蚀和膨胀(最大值和最小值)算法。

  因未测试其他作者的算法时间和效率,本文不敢自称是最快的,但是速度也可以肯定说是相当快的,在一台I5机器上占用单核的资源处理 3000 * 2000的灰度...

3499
来自专栏一棹烟波

OpenGL+OpenCV实现立方体贴图

我屮艸芔茻,转眼就7月份了。 今天试了一下立方体贴图,比较简单,大概说下和平面贴图的区别。 1. 平面贴图需要的是纹理坐标vec2;立方体贴图需要的是一个方向向...

2305

扫码关注云+社区