算法第四版
引言
作业要求链接：
https://coursera.cs.princeton.edu/algs4/assignments/seam/specification.php
作业常见问题解答（包含API的推荐实现顺序）：
https://coursera.cs.princeton.edu/algs4/assignments/seam/faq.php
本次作业需要完成一个名为SeamCarver的内容感知的图像大小调整技术。通过该技术，可以在保留图像感兴趣特征的前提下实现裁剪和缩放。
如下图，上方是原始的505×287像素的图像；下方是移除150条垂直接缝后的结果，从而使图像缩小30%。
一、SeamCarver.java
1、解析
计算energy的部分较为简单，主要讨论如何找最小路径。
lab中推荐使用拓扑排序或动态规划来找最小路径，这里仅讨论拓扑排序。
在此，最小路径的主要思路就是首先进行拓扑排序，然后对每个点relax（松弛）。
（1）拓扑排序实际上拓扑排序实际上就是有优先级限制的排序，可以理解为我必须先在第i行找一点，那么才能在i+1行再找一点。因此我们一行一行遍历，也就实现了拓扑排序。
（2）relax，对于点（x,y），我们需要对（x-1，y+1）,(x,y+1),(x+1,y+1)这三个相邻点进行判断，并改变disto和pathto。
细节部分
（1）见specific，中如何优化代码，主要考虑代码复用问题
（2）使用矩阵转置tranpose，，即水平和竖直，只要完成其中一个，另一个可通过转置图片，能量图来实现。
public class SeamCarver {
// create a seam carver object based on the given picture
public SeamCarver(Picture picture)
// current picture
public Picture picture()
// width of current picture
public int width()
// height of current picture
public int height()
// energy of pixel at column x and row y
public double energy(int x, int y)
// sequence of indices for horizontal seam
public int[] findHorizontalSeam()
// sequence of indices for vertical seam
public int[] findVerticalSeam()
// remove horizontal seam from current picture
public void removeHorizontalSeam(int[] seam)
// remove vertical seam from current picture
public void removeVerticalSeam(int[] seam)
// unit testing (optional)
public static void main(String[] args)
}
2、代码
import edu.princeton.cs.algs4.Picture;
public class SeamCarver {
private Picture picture;
private double[][] energy;
// create a seam carver object based on the given picture
public SeamCarver(Picture picture) {
if (picture == null) {
throw new IllegalArgumentException();
}
this.picture = picture;
computeenergy();
}
// current picture
public Picture picture() {
return this.picture;
}
// width of current picture
public int width() {
return picture.width();
}
// height of current picture
public int height() {
return picture.height();
}
private void computeenergy() {
double[][] energy = new double[width()][height()];
for (int i = 0; i < width(); i++) {
for (int j = 0; j < height(); j++) {
energy[i][j] = energy(i, j);
}
}
this.energy = energy;
}
// energy of pixel at column x and row y
public double energy(int x, int y) {
if (!(x >= 0 && x <= width() - 1)) {
throw new IllegalArgumentException();
}
if (!(y >= 0 && y <= height() - 1)) {
throw new IllegalArgumentException();
}
if (x == 0 || x == width() - 1 || y == 0 || y == height() - 1) {
return 1000;
} else {
// x-gradient
int left = this.picture.getRGB(x - 1, y);
int right = this.picture.getRGB(x + 1, y);
int R_x = ((left >> 16) & 0xFF) - ((right >> 16) & 0xFF);
int G_x = ((left >> 8) & 0xFF) - ((right >> 8) & 0xFF);
int B_x = ((left) & 0xFF) - ((right) & 0xFF);
int RGB_x = R_x * R_x + G_x * G_x + B_x * B_x;
// Y-gradient
int top = this.picture.getRGB(x, y + 1);
int bottom = this.picture.getRGB(x, y - 1);
int R_y = ((top >> 16) & 0xFF) - ((bottom >> 16) & 0xFF);
int G_y = ((top >> 8) & 0xFF) - ((bottom >> 8) & 0xFF);
int B_y = ((top) & 0xFF) - ((bottom) & 0xFF);
int RGB_y = R_y * R_y + G_y * G_y + B_y * B_y;
return Math.sqrt(RGB_x + RGB_y);
}
}
// sequence of indices for horizontal seam
public int[] findVerticalSeam() {
double disto[][] = new double[width()][height()];
int pathto[][] = new int[width()][height()];
for (int col = 0; col < width(); col++) {
for (int row = 0; row < height(); row++) {
if (row == 0) disto[col][row] = energy[col][row];
else disto[col][row] = Double.MAX_VALUE;
}
}
for (int row = 0; row < height() - 1; row++) {
for (int col = 0; col < width(); col++) {
relax(col - 1, row + 1, col, row, disto, pathto);
relax(col, row + 1, col, row, disto, pathto);
relax(col + 1, row + 1, col, row, disto, pathto);
}
}
// find min mindisto
int min_disto = -1;
double min_energy = Double.MAX_VALUE;
for (int col = 0; col < width(); col++) {
if (disto[col][height() - 1] < min_energy) {
min_energy = disto[col][height() - 1];
min_disto = col;
}
}
// find the path
int[] rs = new int[height()];
for (int i = height() - 1; i >= 0; i--) {
rs[i] = min_disto;
min_disto = pathto[min_disto][i];
}
return rs;
}
// sequence of indices for Horizontal seam
public int[] findHorizontalSeam() {
trans(this.picture);
int[] res;
res = findVerticalSeam();
trans(this.picture);
return res;
}
private void trans(Picture picture) {
int newheight = width();
int newwidth = height();
Picture newpicture = new Picture(newwidth, newheight);
for (int i = 0; i < newheight; i++) {
for (int j = 0; j < newwidth; j++) {
newpicture.setRGB(j, i, picture.getRGB(i, j));
}
}
this.picture = newpicture;
computeenergy();
newpicture = null;
}
private void relax(int col, int row, int lastcol, int lastrow, double disto[][], int pathto[][]) {
if ((col >= 0 && col <= width() - 1 && row >= 0 && row <= height() - 1)) {
// out_of_bound
double w = energy[col][row];
// double a = disto[col][row];
if (disto[col][row] > disto[lastcol][lastrow] + w) {
//double b = disto[lastcol][row - 1] + w;
disto[col][row] = disto[lastcol][lastrow] + w;
pathto[col][row] = lastcol;
}
}
}
// remove vertical seam from current picture
public void removeVerticalSeam(int[] seam) {
if (seam == null) {
throw new IllegalArgumentException();
}
if (seam.length != height()) {
throw new IllegalArgumentException();
}
if (width() <= 1) {
throw new IllegalArgumentException();
}
for (int k : seam) {
if (!(k >= 0 && k <= width() - 1)) {
throw new IllegalArgumentException();
}
}
Picture newpicture = new Picture(width() - 1, height());
for (int j = 0; j < height(); j++) {
int ii = 0;
for (int i = 0; i < width() - 1; i++) {
if (seam[j] == i) {
ii++;
}
newpicture.setRGB(i, j, this.picture.getRGB(ii, j));
ii++;
}
}
this.picture = newpicture;
computeenergy();
newpicture = null;
}
// remove horizontal seam from current picture
public void removeHorizontalSeam(int[] seam) {
trans(this.picture);
removeVerticalSeam(seam);
trans(this.picture);
}
// unit testing (optional)
public static void main(String[] args) {
}
}
总结
最终得分90/100，只有少部分参考了其他博主，算较为满意的一次lab