summaryrefslogtreecommitdiffstats
path: root/Algorithms/Part-II/2-SeamCarving
diff options
context:
space:
mode:
Diffstat (limited to 'Algorithms/Part-II/2-SeamCarving')
-rw-r--r--Algorithms/Part-II/2-SeamCarving/SeamCarver.java261
1 files changed, 121 insertions, 140 deletions
diff --git a/Algorithms/Part-II/2-SeamCarving/SeamCarver.java b/Algorithms/Part-II/2-SeamCarving/SeamCarver.java
index 70df587..b87a953 100644
--- a/Algorithms/Part-II/2-SeamCarving/SeamCarver.java
+++ b/Algorithms/Part-II/2-SeamCarving/SeamCarver.java
@@ -10,6 +10,9 @@ public class SeamCarver
private int width;
private int height;
+ // using a byte[3*w*h] array will reduce mem usage,
+ // and speed up cause there will be no need to rotate the matrix
+ // maybe enough to drop out energies cache matrix !?
private int[][] pixels;
private int[][] energies;
private int[][] edgeTo;
@@ -25,7 +28,6 @@ public class SeamCarver
copyPixels(picture);
initEnergies();
- initPaths();
}
private void copyPixels(Picture picture)
@@ -38,14 +40,33 @@ public class SeamCarver
}
}
+ private void initEnergies()
+ {
+ verticalE = true;
+ energies = new int[height][width];
+ for (int i = 0; i < width; i++)
+ energies[0][i] = MAX_ENERGY;
+
+ for (int i = 0; i < width; i++)
+ energies[height - 1][i] = MAX_ENERGY;
+
+ for (int i = 0; i < height; i++)
+ energies[i][0] = MAX_ENERGY;
+
+ for (int i = 0; i < height; i++)
+ energies[i][width - 1] = MAX_ENERGY;
+
+ for (int h = 1; h < (height - 1); h++)
+ for (int w = 1; w < (width - 1); w++)
+ energies[h][w] = energyPriv(h, w);
+ }
+
public Picture picture()
{
Picture p = new Picture(width, height);
- if (!verticalP) {
- pixels = getRotatedMatrix(pixels, height, width);
- verticalP = true;
- }
+ if (!verticalP) rotateMatrix(pixels);
+
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
p.set(x, y, new Color(pixels[y][x]));
@@ -65,33 +86,34 @@ public class SeamCarver
return height;
}
- private void initEnergies()
+ private void rotateMatrix(int[][] matrix)
{
- verticalE = true;
- energies = new int[height][width];
- for (int i = 0; i < width; i++)
- energies[0][i] = MAX_ENERGY;
-
- for (int i = 0; i < width; i++)
- energies[height - 1][i] = MAX_ENERGY;
-
- for (int i = 0; i < height; i++)
- energies[i][0] = MAX_ENERGY;
-
- for (int i = 0; i < height; i++)
- energies[i][width - 1] = MAX_ENERGY;
+ int x, y;
- for (int h = 1; h < (height - 1); h++)
- for (int w = 1; w < (width - 1); w++)
- energies[h][w] = energyPriv(h, w);
- }
+ if (matrix == energies) {
+ if (verticalE) {
+ x = height;
+ y = width;
+ } else {
+ x = width;
+ y = height;
+ }
+ verticalE = !verticalE;
+ } else {
+ if (verticalP) {
+ x = height;
+ y = width;
+ } else {
+ x = width;
+ y = height;
+ }
+ verticalP = !verticalP;
+ }
- private int[][] getRotatedMatrix(int[][] matrix, int y, int x)
- {
if (DEBUG) {
- if (matrix == energies) System.out.println("rotate energies");
- else System.out.println("rotate pixels");
- System.out.println(" new ["+y+";"+x+"]");
+ if (matrix == energies) System.out.print(" rotate energies");
+ else System.out.print(" rotate pixels");
+ System.out.println(" -> ["+y+"]["+x+"]");
}
int[][] m = new int[y][x];
@@ -101,7 +123,10 @@ public class SeamCarver
}
}
- return m;
+ if (matrix == energies)
+ energies = m;
+ else
+ pixels = m;
}
private int getRed(int rgb) { return (rgb >> 16) & 0x0ff; }
@@ -125,27 +150,6 @@ public class SeamCarver
return (rx * rx) + (gx * gx) + (bx * bx) + (ry * ry) + (gy * gy) + (by * by);
}
- private void initPaths()
- {
- int sz = Math.max(height, width);
- edgeTo = new int[sz][sz];
- distTo = new int[sz][sz];
- }
-
- private void clearPaths(int Y, int X)
- {
- for (int x = 0; x < X; x++) {
- // edgeTo[0][x] = -1;
- distTo[0][x] = MAX_ENERGY;
- }
-
- for (int y = 1; y < Y; y++) {
- for (int x = 0; x < X; x++) {
- distTo[y][x] = 0;
- }
- }
- }
-
public double energy(int x, int y)
{
int w = (width - 1);
@@ -179,7 +183,8 @@ public class SeamCarver
{
if (DEBUG) st = new Stopwatch();
- clearPaths((Y + 1), (X + 1));
+ edgeTo = new int[Y + 1][X + 1];
+ distTo = new int[Y + 1][X + 1];
int e, c, d, v;
// from 0 to before last
@@ -229,27 +234,28 @@ public class SeamCarver
}
path[0] = x;
- if (DEBUG) System.out.println("seam found in "+st.elapsedTime());
+ if (DEBUG) System.out.println(" seam found in "+st.elapsedTime());
+
+ edgeTo = null;
+ distTo = null;
return path;
}
public int[] findHorizontalSeam()
{
- if (verticalE) {
- energies = getRotatedMatrix(energies, width, height);
- verticalE = false;
- }
+ if (DEBUG) System.out.println("search horizontal seam");
+
+ if (verticalE) rotateMatrix(energies);
return findMinPath((width - 1), (height - 1));
}
public int[] findVerticalSeam()
{
- if (!verticalE) {
- energies = getRotatedMatrix(energies, height, width);
- verticalE = true;
- }
+ if (DEBUG) System.out.println("search vertical seam");
+
+ if (!verticalE) rotateMatrix(energies);
return findMinPath((height - 1), (width - 1));
}
@@ -275,72 +281,63 @@ public class SeamCarver
}
}
- private void removeItem(int[] a, int index)
+ private void removeSeam(int[] a, boolean vertical)
{
- for (int i = index; i < a.length - 1; i++) {
- a[i] = a[i+1];
+ int len;
+ int[][] p;
+ int[][] e;
+
+ if (vertical) {
+ if (!verticalP) rotateMatrix(pixels);
+ if (!verticalE) rotateMatrix(energies);
+ width -= 1;
+ len = width;
+ p = new int[height][width];
+ e = new int[height][width];
+ } else {
+ if (verticalP) rotateMatrix(pixels);
+ if (verticalE) rotateMatrix(energies);
+ height -= 1;
+ len = height;
+ p = new int[width][height];
+ e = new int[width][height];
}
- }
- private void removeSeam(int[] a, int J, int[][] e, int[][] p)
- {
- for (int i = 0; i < a.length; i++)
- removeItem(p[i], a[i]);
+ // copy pixels
+ for (int i = 0; i < a.length; i++) {
+ int v = a[i];
+ if (v > 0) System.arraycopy(pixels[i], 0, p[i], 0, v);
+ if (v < len) System.arraycopy(pixels[i], (v + 1), p[i], v, (len - v));
+ }
+ pixels = p;
+
+ // copy energies
+ for (int i = 0; i < a.length; i++) {
+ int v = a[i];
+ if (v > 0) System.arraycopy(energies[i], 0, e[i], 0, v);
+ if (v < len) System.arraycopy(energies[i], (v + 1), e[i], v, (len - v));
+ }
+ energies = e;
+ // update energies
+ int l = len - 1;
for (int i = 1; i < (a.length - 1); i++) {
int v = a[i];
if (v == 0) {
e[i][0] = MAX_ENERGY;
- removeItem(e[i], 1);
- } else if (v == 1) {
- e[i][1] = energyPriv(i, 1);
- removeItem(e[i], 2);
} else {
- e[i][v - 1] = energyPriv(i, (v - 1));
- if (v < (J - 1)) {
+ if (v < l) {
e[i][v] = energyPriv(i, v);
- removeItem(e[i], v+1);
- } else {
+ } else if (v == l) {
e[i][v] = MAX_ENERGY;
}
- }
- }
-
- if (!DEBUG) return;
-
- String err;
- for (int j = 0; j < J; j++) {
- int i = 0;
- if (e[i][j] != MAX_ENERGY) {
- err = "["+a.length+" ; "+J+"] : "+i+" ; "+j+" != MAX";
- throw new java.lang.IndexOutOfBoundsException(err);
- }
- i = a.length - 1;
- if (e[i][j] != MAX_ENERGY) {
- err = "["+a.length+" ; "+J+"] : "+i+" ; "+j+" != MAX";
- throw new java.lang.IndexOutOfBoundsException(err);
- }
- }
- for (int i = 0; i < a.length; i++) {
- int j = 0;
- if (e[i][j] != MAX_ENERGY) {
- err = "["+a.length+" ; "+J+"] : "+i+" ; "+j+" != MAX";
- throw new java.lang.IndexOutOfBoundsException(err);
- }
- j = J - 1;
- if (e[i][j] != MAX_ENERGY) {
- err = "["+a.length+" ; "+J+"] : "+i+" ; "+j+" != MAX";
- throw new java.lang.IndexOutOfBoundsException(err);
- }
- }
- for (int i = 1; i < (a.length - 1); i++) {
- int[] ei = e[i];
- for (int j = 1; j < (J - 1); j++) {
- int v = ei[j];
- int eij = energyPriv(i, j);
- if (v != eij) {
- err = "["+a.length+" ; "+J+"] : "+i+" ; "+j+" != "+eij;
- throw new java.lang.IllegalArgumentException(err);
+ v -= 1;
+ if (v == 0) {
+ e[i][0] = MAX_ENERGY;
+ } else if (v < l) {
+ e[i][v] = energyPriv(i, v);
+ } else if (v == l) {
+ e[i][v] = MAX_ENERGY;
}
}
}
@@ -351,22 +348,14 @@ public class SeamCarver
if (width <= 1)
throw new java.lang.IllegalArgumentException("image is to small");
- if (DEBUG) st = new Stopwatch();
-
- validateSeam(a, width, height);
-
- if (verticalE) {
- energies = getRotatedMatrix(energies, width, height);
- verticalE = false;
+ if (DEBUG) {
+ st = new Stopwatch();
+ System.out.println("remove horizontal seam");
}
- if (verticalP) {
- pixels = getRotatedMatrix(pixels, width, height);
- verticalP = false;
- }
+ validateSeam(a, width, height);
- height -= 1;
- removeSeam(a, height, energies, pixels);
+ removeSeam(a, false);
if (DEBUG) System.out.println("["+width+" "+height+"] in "+st.elapsedTime());
}
@@ -376,22 +365,14 @@ public class SeamCarver
if (height <= 1)
throw new java.lang.IllegalArgumentException("image is to small");
- if (DEBUG) st = new Stopwatch();
-
- validateSeam(a, height, width);
-
- if (!verticalE) {
- energies = getRotatedMatrix(energies, height, width);
- verticalE = true;
+ if (DEBUG) {
+ st = new Stopwatch();
+ System.out.println("remove vertical seam");
}
- if (!verticalP) {
- pixels = getRotatedMatrix(pixels, height, width);
- verticalP = true;
- }
+ validateSeam(a, height, width);
- width -= 1;
- removeSeam(a, width, energies, pixels);
+ removeSeam(a, true);
if (DEBUG) System.out.println("["+width+" "+height+"] in "+st.elapsedTime());
}
generated by cgit v1.1-2-g2b99 at 2024-11-23 04:02:37 +0100