1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
/**
* @author Pacien TRAN-GIRARD
* @author Timothée FLOURE
*/
public final class Seam {
/**
* Find the best predecessors between {@code from} and {@code to} using Dijkstra's algorithm
*
* @param successors adjacency list for all vertices
* @param costs weight for all vertices
* @param from first vertex
* @return best predecessor of each vertex
*/
private static int[] findBestPredecessors(int[][] successors, float[] costs, int from) {
int nbVertices = successors.length;
float distances[] = new float[nbVertices];
int bestPredecessors[] = new int[nbVertices];
for (int v = 0; v < nbVertices; ++v) {
distances[v] = Float.POSITIVE_INFINITY;
bestPredecessors[v] = -1;
}
distances[from] = costs[from];
boolean modified = true;
while (modified) {
modified = false;
for (int v = 0; v < nbVertices; ++v)
for (int n : successors[v])
if (distances[n] > distances[v] + costs[n]) {
distances[n] = distances[v] + costs[n];
bestPredecessors[n] = v;
modified = true;
}
}
return bestPredecessors;
}
/**
* Compute shortest path between {@code from} and {@code to}
*
* @param successors adjacency list for all vertices
* @param costs weight for all vertices
* @param from first vertex
* @param to last vertex
* @return a sequence of vertices, or {@code null} if no path exists
*/
public static int[] path(int[][] successors, float[] costs, int from, int to) {
int[] bestPredecessors = Seam.findBestPredecessors(successors, costs, from);
int count = 0; // we could have used a Deque<Integer>, but we could not have returned an int[]; CC Pr. Odersky
int predecessor = -1, newPredecessor = to;
while (newPredecessor > -1) {
predecessor = newPredecessor;
newPredecessor = bestPredecessors[newPredecessor];
++count;
}
if (predecessor != from) return null; // "no way!"
int[] path = new int[count];
path[count - 1] = to;
for (int v = count - 2; v >= 0; --v)
path[v] = bestPredecessors[path[v + 1]];
return path;
}
/**
* Find best seam
*
* @param energy weight for all pixels
* @return a sequence of x-coordinates (the y-coordinate is the index)
*/
public static int[] find(float[][] energy) {
// TODO find
return null;
}
/**
* Draw a seam on an image
*
* @param image original image
* @param seam a seam on this image
* @return a new image with the seam in blue
*/
public static int[][] merge(int[][] image, int[] seam) {
// Copy image
int width = image[0].length;
int height = image.length;
int[][] copy = new int[height][width];
for (int row = 0; row < height; ++row)
for (int col = 0; col < width; ++col)
copy[row][col] = image[row][col];
// Paint seam in blue
for (int row = 0; row < height; ++row)
copy[row][seam[row]] = 0x0000ff;
return copy;
}
/**
* Remove specified seam
*
* @param image original image
* @param seam a seam on this image
* @return the new image (width is decreased by 1)
*/
public static int[][] shrink(int[][] image, int[] seam) {
int width = image[0].length;
int height = image.length;
int[][] result = new int[height][width - 1];
for (int row = 0; row < height; ++row) {
for (int col = 0; col < seam[row]; ++col)
result[row][col] = image[row][col];
for (int col = seam[row] + 1; col < width; ++col)
result[row][col - 1] = image[row][col];
}
return result;
}
}
|