diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/main/java/Seam.java | 82 |
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 | /** |