首页 > 代码库 > 普林斯顿算法课Part2第二周作业_SeamCarving
普林斯顿算法课Part2第二周作业_SeamCarving
作业地址:http://coursera.cs.princeton.edu/algs4/assignments/seamCarving.html
作业难点:
1、如何获取图形的RGB属性?
需要研习下Picture、Color类等,使用getRGB()、getRed()、getGreen()、getBlue()等函数;
2、如何计算从顶端到底部的最低energy曲线(即最短路径)?
使用课上讲的Dijkstra算法求解即可;
3、是否将findHorizontalSeam和findVerticalSeam的方法合并?
如果要合并,关键的问题在于将energy矩阵转置;
容易扣分点:
1、怎么确保对象内存使用在要求的内存范围内?
不同于第一份的作业,第二部分的作业的数据结构没有显示给出。本次作业中,为了降低对象的内存使用情况,要尽量避免使用全局性的私有变量,因此部分函数的参数会变得很长;
2、removeHorizontalSeam和removeVerticalSeam函数执行后对象未及时更新。
要确保在两个函数的最后进行图像更新;
部分代码:
1、数据结构:
private int[][] colorRGB; private int width; private int height; private Picture picture; private static final double MAX_ENERGY = 1000.0;
2、求解最短路径:
private void DijkstraSP(boolean isVertical, double[][] energy, double[] distTo, int[] edgeTo) { int V = width * height; for (int v = 0; v < V; v++) { distTo[v] = Double.POSITIVE_INFINITY; edgeTo[v] = 0; } int initLen = width; if (!isVertical) initLen = height; IndexMinPQ<Double> pq = new IndexMinPQ<Double>(V); for (int v = 0; v < initLen; v++) { distTo[v] = MAX_ENERGY; pq.insert(v, distTo[v]); } boolean notFinStat = true; while (!pq.isEmpty() && notFinStat) { relax(pq.delMin(), isVertical, energy, distTo, edgeTo, pq); for (int i = V - 1; i > V - initLen; i--) if (distTo[i] != Double.POSITIVE_INFINITY) { notFinStat = false; break; } } } private void relax(int v, boolean isVertical, double[][] energy, double[] distTo, int[] edgeTo, IndexMinPQ<Double> pq) { int x, y, w; double weight; int seamWidth = width, seamHeight = height; if (!isVertical) { seamWidth = height; seamHeight = width; } x = v % seamWidth; y = v / seamWidth; if (x == 0 || x == seamWidth -1 || y == seamHeight - 1) return; for (int delta = -1; delta < 2; delta++) { w = (y+1) * seamWidth + (x + delta); weight = energy[x + delta][y + 1]; if (distTo[w] > distTo[v] + weight) { distTo[w] = distTo[v] + weight; edgeTo[w] = v; if(y + 1 == seamHeight - 1) return; if (pq.contains(w)) pq.changeKey(w, distTo[w]); else pq.insert(w, distTo[w]); } } }
3、求解顶端到底部的路径:
private int[] findSeam(boolean isVertical, double[] distTo, int[] edgeTo) { int minIndex = 0; double minDist = Double.POSITIVE_INFINITY; int seamWidth = width, seamHeight = height; if (!isVertical) { seamWidth = height; seamHeight = width; } int[] seamPath = new int [seamHeight]; for (int i = 0; i < seamWidth; i++) if (distTo[(seamHeight - 1) * seamWidth + i] < minDist) { minIndex = (seamHeight - 1) * seamWidth + i; minDist = distTo[(seamHeight -1) * seamWidth + i]; } for (int i = seamHeight - 1; i > 0 ; i--) { seamPath[i] = minIndex % seamWidth; minIndex = edgeTo[minIndex]; } if (seamPath.length > 1) seamPath[0] = seamPath[1]; return seamPath; }
4、energy转置:
private double[][] energyTranspose(int W, int H, boolean isTranspose) { double[][] result = new double[W][H]; for (int y = 0; y < H; y++) for (int x = 0; x < W; x++) { if (isTranspose) result[x][y] = energy(y, x); else result[x][y] = energy(x, y); } return result; }
5、removeVerticalSeam():
public void removeVerticalSeam(int[] seam) { if (seam.length != height || width <= 1) throw new java.lang.IllegalArgumentException(); checkSeam(seam, width); int[][] copy = new int[width-1][height]; for (int y = 0; y < height; y++) { for (int x = 0; x < width; x++) { if (x < seam[y]) copy[x][y] = colorRGB[x][y]; else if (x > seam[y]) copy[x-1][y] = colorRGB[x][y]; } } width--; colorRGB = copy; picture(); }
普林斯顿算法课Part2第二周作业_SeamCarving
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。