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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
/**
* @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;
}
/**
* Build the vertical predecessors graph of a matrix, plus an entry and an exit vertex
*
* @param width width of the matrix
* @param height height of the matrix
* @return an oriented predecessors graph of the size (width * height + 2)
*/
private static int[][] buildPredecessorsGraph(int width, int height) {
int matrixSize = width * height;
int[][] graph = new int[matrixSize + 2][];
for (int row = 0; row < height - 1; ++row) {
int shift = (row + 1) * width;
graph[row * height] = new int[]{
shift,
shift + 1,
};
graph[row * height + (width - 1)] = new int[]{
shift + (width - 2),
shift + (width - 1),
};
for (int col = 1; col < width - 1; ++col)
graph[row * height + col] = new int[]{
shift + (col - 1),
shift + (col),
shift + (col + 1),
};
}
graph[(matrixSize)] = new int[width];
for (int col = 0; col < width; ++col) graph[matrixSize][col] = col;
graph[matrixSize + 1] = new int[0];
for (int col = 0; col < width; ++col) graph[(height - 1) * width + col] = new int[]{matrixSize + 1};
return graph;
}
/**
* Build a sequence of vertex costs from a cost matrix, with nil-cost entry and exit vertices
*
* @param energy the cost matrix
* @return a sequence of costs of the size (width * height + 2)
*/
private static float[] buildVerticesCostSequence(float[][] energy) {
int width = energy[0].length;
int height = energy.length;
int matrixSize = width * height;
float[] costs = new float[matrixSize + 2];
for (int row = 0; row < height; ++row)
for (int col = 0; col < width; ++col)
costs[row * width + col] = energy[row][col];
costs[matrixSize] = 0;
costs[matrixSize + 1] = 0;
return costs;
}
/**
* 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) {
int width = energy[0].length;
int height = energy.length;
int matrixSize = width * height;
int[][] predecessors = Seam.buildPredecessorsGraph(width, height);
float[] costs = Seam.buildVerticesCostSequence(energy);
int[] path = Seam.path(predecessors, costs, matrixSize, matrixSize + 1);
if (path == null) return null;
int[] coordinates = new int[path.length - 2]; // ignore added beginning and ending vertices
for (int x = 0; x < path.length - 2; ++x)
coordinates[x] = path[x + 1] - x * width; // retrieve the y-coordinate
return coordinates;
}
/**
* 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;
}
}
|