Massive Algorithms: Seam Carving - Princeton Part II

Seam Carving - Princeton Part II - Programming Assignment 2

http://coursera.cs.princeton.edu/algs4/assignments/seamCarving.html
Seam-carving is a content-aware image resizing technique where the image is reduced in size by one pixel of height (or width) at a time. A vertical seam in an image is a path of pixels connected from the top to the bottom with one pixel in each row. (A horizontal seam is a path of pixels connected from the left to the right with one pixel in each column.) Below left is the original 505-by-287 pixel image; below right is the result after removing 150 vertical seams, resulting in a 30% narrower image. Unlike standard content-agnostic resizing techniques (e.g. cropping and scaling), the most interesting features (aspect ratio, set of objects present, etc.) of the image are preserved.
As you'll soon see, the underlying algorithm is quite simple and elegant. Despite this fact, this technique was not discovered until 2007 by Shai Avidan and Ariel Shamir. It is now a feature in Adobe Photoshop (thanks to a Princeton graduate student), as well as other popular computer graphics applications.

In this assignment, you will create a data type that resizes a W-by-H image using the seam-carving technique.

Energy calculation. The first step is to calculate the energy of each pixel, which is a measure of the importance of each pixel—the higher the energy, the less likely that the pixel will be included as part of a seam (as we'll see in the next step). In this assignment, you will implement the dual-gradient energy function, which is described below. Here is the dual-gradient energy function of the surfing image above:
The energy is high (white) for pixels in the image where there is a rapid color gradient (such as the boundary between the sea and sky and the boundary between the surfing Josh Hug on the left and the ocean behind him). The seam-carving technique avoids removing such high-energy pixels.

Seam identification. The next step is to find a vertical seam of minimum total energy. This is similar to the classic shortest path problem in an edge-weighted digraph except for the following:
- The weights are on the vertices instead of the edges.
- We want to find the shortest path from any of the W pixels in the top row to any of the W pixels in the bottom row.
- The digraph is acyclic, where there is a downward edge from pixel (x, y) to pixels (x − 1, y + 1), (x, y + 1), and (x + 1, y + 1), assuming that the coordinates are in the prescribed range.

Seam removal. The final step is to remove from the image all of the pixels along the seam.

The SeamCarver API. Your task is to implement the following mutable data type:

public class SeamCarver {
   public SeamCarver(Picture picture)                // create a seam carver object based on the given picture
   public Picture picture()                          // current picture
   public     int width()                            // width of current picture
   public     int height()                           // height of current picture
   public  double energy(int x, int y)               // energy of pixel at column x and row y
   public   int[] findHorizontalSeam()               // sequence of indices for horizontal seam
   public   int[] findVerticalSeam()                 // sequence of indices for vertical seam
   public    void removeHorizontalSeam(int[] seam)   // remove horizontal seam from current picture
   public    void removeVerticalSeam(int[] seam)     // remove vertical seam from current picture
}

Computing the energy of a pixel. You will use the dual-gradient energy function: The energy of pixel $(x, y)$ is $\sqrt{Δ_{x}^{2} (x, y) + Δ_{y}^{2} (x, y)}$ , where the square of the x-gradient $Δ_{x}^{2} (x, y) = R_{x} (x, y)^{2} + G_{x} (x, y)^{2} + B_{x} (x, y)^{2}$ , and where the central differences $R_{x} (x, y)$ , $G_{x} (x, y)$ , and $B_{x} (x, y)$ are the differences in the red, green, and blue components between pixel (x + 1, y) and pixel (x − 1, y), respectively. The square of the y-gradient $Δ_{y}^{2} (x, y)$ is defined in an analogous manner. We define the energy of a pixel at the border of the image to be 1000, so that it is strictly larger than the energy of any interior pixel.As an example, consider the 3-by-4 image (supplied as 3x4.png) with RGB values—each component is an integer between 0 and 255—as shown in the table below:

The ten border pixels have energy 1000. Only the pixels (1, 1) and (1, 2) are nontrivial. We calculate the energy of pixel (1, 2) in detail:
R_x(1, 2) = 255 − 255 = 0,
G_x(1, 2) = 205 − 203 = 2,
B_x(1, 2) = 255 − 51 = 204,
yielding Δ_x²(1, 2) = 2² + 204² = 41620.
R_y(1, 2) = 255 − 255 = 0,
G_y(1, 2) = 255 − 153 = 102,
B_y(1, 2) = 153 − 153 = 0,
yielding Δ_y²(1, 2) = 102² = 10404.

Thus, the energy of pixel (1, 2) is $\sqrt{41620 + 10404} = \sqrt{52024}$ . Similarly, the energy of pixel (1, 1) is $\sqrt{204^{2} + 103^{2}} = \sqrt{52225}$ .
Finding a vertical seam. The findVerticalSeam() method returns an array of length H such that entry y is the column number of the pixel to be removed from row y of the image. For example, the dual-gradient energies of a 6-by-5 image (supplied as 6x5.png).
The minimum energy vertical seam is highlighted in blue. In this case, the method findVerticalSeam() returns the array { 3, 4, 3, 2, 2 } because the pixels in a minimum energy vertical seam are (3, 0), (4, 1), (3, 2), (2, 3), and (2, 4). When there are multiple vertical seams with minimal total energy, your method can return any such seam.
Finding a horizontal seam. The behavior of findHorizontalSeam() is analogous to that of findVerticalSeam() except that it returns an array of length W such that entry x is the row number of the pixel to be removed from column x of the image. For the 6-by-5 image, the method findHorizontalSeam() returns the array { 2, 2, 1, 2, 1, 2 } because the pixels in a minimum energy horizontal seam are (0, 2), (1, 2), (2, 1), (3, 2), (4, 1), and (5, 2).
Performance requirements. The width(), height(), and energy() methods should take constant time in the worst case. All other methods should run in time at most proportional to W H in the worst case. For faster performance, do not construct explicit DirectedEdge and EdgeWeightedDigraph objects.

https://github.com/nastra/AlgorithmsPartII-Princeton/tree/master/seamCarving
http://nifty.stanford.edu/2015/hug-seam-carving/
https://segmentfault.com/a/1190000005345079

作业中值得提到的点其实不多，大部分功能的实现都非常直接，中间加入了一点图像处理的入门知识，同样也非常好理解，重点是最短路径的BFS：

对于固定值边界的处理比较繁琐，需要仔细处理；
对很多图像处理问题，虽处理对象大体上还符合“图”的定义，但因为很多图像固有的因素，会将问题简化得多，不必再使用重量级的Digraph类，就事论事地解决问题即可；
要找到能量最小的seam需要对整个图像计算路径距离，我的做法是维护distTo（最近距离）和edgeTo（最近距离对应“父节点”）两个数组，遍历全图后在最后一行（列）找到distTo的最小值即为所求seam的尾元素，通过追踪edgeTo即可得到所求seam。
energy的复用是一个小难点，需要认真考虑每移除一列或一行seam后，哪些情况下的点应该被重新计算，参考作业说明的vertical-seam.png、horizontal-seam.png或下图去分析，可能会有帮助：
我想到的转置的目的是为了在纵横两个方向都能利用System.arraycopy()的高效，开始时我没有做这项优化，是手写了removeHorizontalSeam()的这个过程，因已达到了满分要求便没有再优化。

https://blog.niallconnaughton.com/2015/11/21/image-resizing-with-seam-carving/

Seam carving achieves this by identifying the “energy” of each pixel, which is a measurement of the how important to the image the detail of each pixel is. It then identifies horizontal or vertical seams through the image and removes the seam with the least total energy. The seams don’t have to be straight lines, allowing the algorithm to remove paths of low detail pixels that follow the shape of the image.

Colour gradients – a simple measurement of pixel energy

The energy function used will determine the results of the resize. It’s easy to imagine customised energy functions to suit certain types of images. A general purpose approach is to use the rate of colour change around a pixel, and this is the one used in the Algorithms II assignment. The idea is that areas of an image with very little variation in colour have less detail and so are better candidates for removal when resizing.

Below is an example showing the energy of a photo and the lowest energy vertical seam that would be removed from the image. The highest energy parts of the photo are the edges between the rocks and water, and the hills and skyline. The detail in the water and rocks does have some energy, but on the whole I was surprised that so much of the photo has low energy, given the level of detail we perceive with our eyes. Presumably this is what allows Jpeg compression to be so effective.

The implementation can be seen as a graph algorithm on a weighted directed acyclic graph. Each pixel contributes energy to the three pixels immediately below it. As pixels only contribute energy downwards, there are no cycles in the graph. By finding the shortest weighted path from the top row to the bottom row, you find the vertical seam with the least energy. This is the topological order approach to shortest paths in a weighted DAG. After identifying the minimal seam, its pixels are removed and the process is repeated.

There are some improvements that could be made to the approach. In their videos and papers, the original creators refer to this approach as “backwards energy”, meaning looking at the image as it was and then removing a seam. This can lead to bringing together two sharp edges that end up having significantly increased energy, which you see in the image as artefacts in lines and edges. They propose using “forwards energy” which takes into account the impact on the image if this seam were to be removed. From my examples, I think this would reduce the artefacts significantly, but I haven’t had time to try it.

Another possibility that occurred to me was anti-aliasing high detail sections along seams that were removed. This may help smooth/soften harsh changes visible when the seam crosses edges in the image, like a horizon line. Although possibly it could cause more trouble than it solves if it results in large areas of the image being blurred over – I haven’t had time to test this either.

https://github.com/zhichaoh/Coursera-Algorithms/blob/master/src/SeamCarver.java
public class SeamCarver {

private Picture pic;

private double[][] energy;

public SeamCarver(Picture picture) {
pic = new Picture(picture);
energy = new double[pic.height()][pic.width()];
}

public Picture picture() {
// current picture
return pic;
}

public int width() {
// width of current picture
return pic.width();
}

public int height() {
// height of current picture
return pic.height();
}

public double energy(int x, int y) throws IndexOutOfBoundsException {
// energy of pixel at column x and row y
if (x < 0 || y < 0 || x >= pic.width() || y >= pic.height())
throw new IndexOutOfBoundsException();
else if (x == 0 || y == 0 || x == pic.width() - 1
|| y == pic.height() - 1)
return 195075.0;
else {
Color xp1y = pic.get(x + 1, y);
Color xn1y = pic.get(x - 1, y);
Color xyp1 = pic.get(x, y + 1);
Color xyn1 = pic.get(x, y - 1);
double detX = (xn1y.getRed() - xp1y.getRed())
* (xn1y.getRed() - xp1y.getRed())
+ (xn1y.getBlue() - xp1y.getBlue())
* (xn1y.getBlue() - xp1y.getBlue())
+ (xn1y.getGreen() - xp1y.getGreen())
* (xn1y.getGreen() - xp1y.getGreen());
double detY = (xyn1.getRed() - xyp1.getRed())
* (xyn1.getRed() - xyp1.getRed())
+ (xyn1.getBlue() - xyp1.getBlue())
* (xyn1.getBlue() - xyp1.getBlue())
+ (xyn1.getGreen() - xyp1.getGreen())
* (xyn1.getGreen() - xyp1.getGreen());
return detX + detY;
}
}

private void dfsMinPath(int x, int y, double[][] sumEnergy,
double[][] energy, int[][] steps, boolean horizontal) {
if ((horizontal && x == pic.width() - 1)
|| (!horizontal && y == pic.height() - 1)) {
sumEnergy[y][x] = energy[y][x];
steps[y][x] = -1;
return;
}
double minPath = Double.MAX_VALUE;
int bestMv = 0;
for (int mv = -1; mv <= 1; mv++) {
if (horizontal) {
int py = y + mv;
if (py >= pic.height() || py < 0)
continue;
if (steps[py][x + 1] == 0)
dfsMinPath(x + 1, py, sumEnergy, energy, steps, horizontal);
if (sumEnergy[py][x + 1] < minPath) {
minPath = sumEnergy[py][x + 1];
bestMv = py;
}
} else {
int px = x + mv;
if (px >= pic.width() || px < 0)
continue;
if (steps[y + 1][px] == 0)
dfsMinPath(px, y + 1, sumEnergy, energy, steps, horizontal);
if (sumEnergy[y + 1][px] < minPath) {
minPath = sumEnergy[y + 1][px];
bestMv = px;
}
}
}
steps[y][x] = bestMv;
sumEnergy[y][x] = energy[y][x] + minPath;
}

private void calSumEnergy() {
for (int j = 0; j < pic.height(); j++)
for (int i = 0; i < pic.width(); i++) {
energy[j][i] = this.energy(i, j);
}
}

public int[] findHorizontalSeam() {
// sequence of indices for horizontal seam
int[][] steps = new int[pic.height()][pic.width()];
double[][] sumEnergy = new double[pic.height()][pic.width()];
this.calSumEnergy();
for (int y = 0; y < this.height(); y++)
this.dfsMinPath(0, y, sumEnergy, energy, steps, true);
int[] ht = new int[pic.width()];
double bestEnergy = Double.MAX_VALUE;
for (int y = 0; y < this.height(); y++) {
if (sumEnergy[y][0] < bestEnergy) {
bestEnergy = sumEnergy[y][0];
ht[0] = y;
}
}
for (int x = 1; x < this.width(); x++) {
ht[x] = steps[ht[x - 1]][x - 1];
}
return ht;
}

public int[] findVerticalSeam() {
// sequence of indices for vertical seam
int[][] steps = new int[pic.height()][pic.width()];
double[][] sumEnergy = new double[pic.height()][pic.width()];
this.calSumEnergy();
for (int x = 0; x < this.width(); x++)
this.dfsMinPath(x, 0, sumEnergy, energy, steps, false);
int[] ht = new int[pic.height()];
double bestEnergy = Double.MAX_VALUE;
for (int x = 0; x < this.width(); x++) {
if (sumEnergy[0][x] < bestEnergy) {
bestEnergy = sumEnergy[0][x];
ht[0] = x;
}
}
for (int y = 1; y < this.height(); y++)
ht[y] = steps[y - 1][ht[y - 1]];
return ht;
}

public void removeHorizontalSeam(int[] a) throws IllegalArgumentException {
// remove horizontal seam from picture
if (a.length != pic.width())
throw new IllegalArgumentException();
Picture cPic = new Picture(pic.width(), pic.height() - 1);
for (int i = 0; i < pic.width(); i++) {
for (int j = 0; j < pic.height(); j++) {
if (j == a[i])
continue;
int pt = j;
if (pt > a[i])
pt--;
cPic.set(i, pt, this.pic.get(i, j));
}
}
this.pic = cPic;
}

public void removeVerticalSeam(int[] a) throws IllegalArgumentException {
// remove vertical seam from picture
if (a.length != pic.height())
throw new IllegalArgumentException();
Picture cPic = new Picture(pic.width() - 1, pic.height());
for (int j = 0; j < pic.height(); j++) {
for (int i = 0; i < pic.width(); i++) {
if (i == a[j])
continue;
int pt = i;
if (pt > a[j])
pt--;
cPic.set(pt, j, pic.get(i, j));
}
}
this.pic = cPic;
}
}

Seam Carving - Princeton Part II - Programming Assignment 2

Colour gradients – a simple measurement of pixel energy

Labels

Popular Posts