# Programming Assignment 2 Seam Carving 暴力实现

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

## 问题概述

```  (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)同理。```

## 算法实现

### 能量函数

```    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;
}```

## 后记

0 条评论

• ### UVA 10600 ACM Contest and Blackout(次小生成树)

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=...

• ### 【PAT乙级】换个格式输出整数

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### 复习C艹（更新中）

之前在win7中运行c／c++下个vc就可以编译运行了，现在换了Mac，上网一看需要下个xcode，哎哟，好大啊，当时又没网，捉急，咦，mac的终端可以编译cp...

• ### 数字问题-LeetCode 524、525、526、528、530、537、539、540

LeetCode # 524 525 526 528 530 537 539 540

• ### Java工具集-支持各种类型快速排序工具

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### LeetCode算法(二)

自评：需要先将每个罗马数字代表的数字保存起来。循环提取每一个罗马数字。因为不同的位置会有不同的做法，所以记录之前罗马数字的值，如果比上一次加的值大，则本次减去2...

• ### Codeforces Round #543 (Div. 2, based on Technocup 2019 Final Round) A. Technogoblet of Fire(思维)

题目链接：https://codeforces.com/contest/1121/problem/A