aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/main/java/Seam.java82
1 files changed, 80 insertions, 2 deletions
diff --git a/src/main/java/Seam.java b/src/main/java/Seam.java
index d74dff7..d3ffa8e 100644
--- a/src/main/java/Seam.java
+++ b/src/main/java/Seam.java
@@ -40,6 +40,70 @@ public final class Seam {
40 } 40 }
41 41
42 /** 42 /**
43 * Build the vertical predecessors graph of a matrix, plus an entry and an exit vertex
44 *
45 * @param width width of the matrix
46 * @param height height of the matrix
47 * @return an oriented predecessors graph of the size (width * height + 2)
48 */
49 private static int[][] buildPredecessorsGraph(int width, int height) {
50 int matrixSize = width * height;
51 int[][] graph = new int[matrixSize + 2][];
52
53 for (int row = 0; row < height - 1; ++row) {
54 int shift = (row + 1) * width;
55
56 graph[row * height] = new int[]{
57 shift,
58 shift + 1,
59 };
60
61 graph[row * height + (width - 1)] = new int[]{
62 shift + (width - 2),
63 shift + (width - 1),
64 };
65
66 for (int col = 1; col < width - 1; ++col)
67 graph[row * height + col] = new int[]{
68 shift + (col - 1),
69 shift + (col),
70 shift + (col + 1),
71 };
72 }
73
74 graph[(matrixSize)] = new int[width];
75 for (int col = 0; col < width; ++col) graph[matrixSize][col] = col;
76
77 graph[matrixSize + 1] = new int[0];
78 for (int col = 0; col < width; ++col) graph[(height - 1) * width + col] = new int[]{matrixSize + 1};
79
80 return graph;
81 }
82
83 /**
84 * Build a sequence of vertex costs from a cost matrix, with nil-cost entry and exit vertices
85 *
86 * @param energy the cost matrix
87 * @return a sequence of costs of the size (width * height + 2)
88 */
89 private static float[] buildVerticesCostSequence(float[][] energy) {
90 int width = energy[0].length;
91 int height = energy.length;
92 int matrixSize = width * height;
93
94 float[] costs = new float[matrixSize + 2];
95
96 for (int row = 0; row < height; ++row)
97 for (int col = 0; col < width; ++col)
98 costs[row * width + col] = energy[row][col];
99
100 costs[matrixSize] = 0;
101 costs[matrixSize + 1] = 0;
102
103 return costs;
104 }
105
106 /**
43 * Compute shortest path between {@code from} and {@code to} 107 * Compute shortest path between {@code from} and {@code to}
44 * 108 *
45 * @param successors adjacency list for all vertices 109 * @param successors adjacency list for all vertices
@@ -76,8 +140,22 @@ public final class Seam {
76 * @return a sequence of x-coordinates (the y-coordinate is the index) 140 * @return a sequence of x-coordinates (the y-coordinate is the index)
77 */ 141 */
78 public static int[] find(float[][] energy) { 142 public static int[] find(float[][] energy) {
79 // TODO find 143 int width = energy[0].length;
80 return null; 144 int height = energy.length;
145 int matrixSize = width * height;
146
147 int[][] predecessors = Seam.buildPredecessorsGraph(width, height);
148 float[] costs = Seam.buildVerticesCostSequence(energy);
149
150 int[] path = Seam.path(predecessors, costs, matrixSize, matrixSize + 1);
151
152 if (path == null) return null;
153
154 int[] coordinates = new int[path.length - 2]; // ignore added beginning and ending vertices
155 for (int x = 0; x < path.length - 2; ++x)
156 coordinates[x] = path[x + 1] - x * width; // retrieve the y-coordinate
157
158 return coordinates;
81 } 159 }
82 160
83 /** 161 /**