Algorithms-II : 2-SeamCarving: implementation (fast but heavy mem usage)

2 files changed, 379 insertions, 20 deletions

diff --git a/Algorithms/Part-II/2-SeamCarving/Makefile b/Algorithms/Part-II/2-SeamCarving/Makefile
index 8a7d1c1..8e826fe 100644
--- a/Algorithms/Part-II/2-SeamCarving/Makefile
+++ b/Algorithms/Part-II/2-SeamCarving/Makefile
@@ -4,7 +4,7 @@ ALGS4	= $(HOME)/algs4
 BIN	= SeamCarver
 SRCS	= SeamCarver.java
 CLASSES	= PrintEnergy.class PrintSeams.class ResizeDemo.class SCUtility.class ShowEnergy.class ShowSeams.class
-CLASSPATH	= -classpath .:$(ALGS4)/algs4.jar:$(ALGS4)/stdlib.jar
+CLASSPATH	= -classpath '.:$(ALGS4)/algs4.jar:$(ALGS4)/stdlib.jar'
 
 .SUFFIXES:
 .SUFFIXES: .java .class
@@ -16,13 +16,28 @@ CLASSPATH	= -classpath .:$(ALGS4)/algs4.jar:$(ALGS4)/stdlib.jar
 
 $(BIN): $(BIN).class
 
-run: $(BIN) $(CLASSES)
-	java $(CLASSPATH) PrintEnergy ./data/6x5.png
-	java $(CLASSPATH) PrintSeams ./data/6x5.png
+check.sh:
+	echo -e "#! /bin/bash\nF=./data/\$${1}\njava $(CLASSPATH) PrintSeams \$${F}.png > \$${F}.txt && diff -B \$${F}.txt \$${F}.printseams.txt && rm \$${F}.txt" > check.sh
+	chmod +x check.sh
+
+check: $(BIN) $(CLASSES) check.sh
+	./check.sh 3x7
+	./check.sh 4x6
+	./check.sh 5x6
+	./check.sh 6x5
+	./check.sh 7x3
+	./check.sh 10x12
+	./check.sh 12x10
+	./check.sh HJocean
+	./check.sh HJoceanTransposed
+
+test: $(BIN) $(CLASSES)
+	java $(CLASSPATH) ResizeDemo ./data/HJocean.png 200 100
 
 zip: $(BIN)
 	$(ALGS4)/bin/findbugs $(BIN).class
-	zip $(BIN).zip $(SRCS)
+	rm -f *.zip
+	zip seamCarving.zip $(SRCS)
 
 clean:
-	rm -f *.class *.zip $(BIN)
+	rm -f *.class *.zip check.sh $(BIN)
diff --git a/Algorithms/Part-II/2-SeamCarving/SeamCarver.java b/Algorithms/Part-II/2-SeamCarving/SeamCarver.java
index 48e7f6e..70df587 100644
--- a/Algorithms/Part-II/2-SeamCarving/SeamCarver.java
+++ b/Algorithms/Part-II/2-SeamCarving/SeamCarver.java
@@ -1,54 +1,398 @@
 /* vim: set expandtab tabstop=4 shiftwidth=4 : */
 
+import java.awt.Color;
+
 public class SeamCarver
 {
+    private static int MAX_ENERGY = 195075;
+
+    private static boolean DEBUG = false;
+
+    private int width;
+    private int height;
+    private int[][] pixels;
+    private int[][] energies;
+    private int[][] edgeTo;
+    private int[][] distTo;
+    private boolean verticalE;
+    private boolean verticalP;
+    private Stopwatch st;
+
     public SeamCarver(Picture picture)
     {
+        width = picture.width();
+        height = picture.height();
+
+        copyPixels(picture);
+        initEnergies();
+        initPaths();
+    }
+
+    private void copyPixels(Picture picture)
+    {
+        verticalP = true;
+        pixels = new int[height][width];
+        for (int y = 0; y < height; y++) {
+            for (int x = 0; x < width; x++)
+                pixels[y][x] = picture.get(x, y).getRGB();
+        }
     }
 
     public Picture picture()
     {
-        // current picture
-        return null;
+        Picture p = new Picture(width, height);
+
+        if (!verticalP) {
+            pixels = getRotatedMatrix(pixels, height, width);
+            verticalP = true;
+        }
+        for (int y = 0; y < height; y++) {
+            for (int x = 0; x < width; x++) {
+                p.set(x, y, new Color(pixels[y][x]));
+            }
+        }
+
+        return p;
     }
 
     public int width()
     {
-        // width  of current picture
-        return 0;
+        return width;
     }
 
     public int height()
     {
-        // height of current picture
-        return 0;
+        return height;
+    }
+
+    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);
+    }
+
+    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+"]");
+        }
+
+        int[][] m = new int[y][x];
+        for (int i = 0; i < y; i++) {
+            for (int j = 0; j < x; j++) {
+                m[i][j] = matrix[j][i];
+            }
+        }
+
+        return m;
+    }
+
+    private int getRed(int rgb)     { return (rgb >> 16) & 0x0ff; }
+    private int getGreen(int rgb)   { return (rgb >> 8) & 0x0ff; }
+    private int getBlue(int rgb)    { return (rgb) & 0x0ff; }
+
+    private int energyPriv(int y, int x)
+    {
+        int left = pixels[y][x - 1];
+        int right = pixels[y][x + 1];
+        int up = pixels[y - 1][x];
+        int down = pixels[y + 1][x];
+
+        int rx = getRed(left) - getRed(right);
+        int gx = getGreen(left) - getGreen(right);
+        int bx = getBlue(left) - getBlue(right);
+        int ry = getRed(up) - getRed(down);
+        int gy = getGreen(up) - getGreen(down);
+        int by = getBlue(up) - getBlue(down);
+
+        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)
     {
-        // energy of pixel at column x and row y in current picture
-        return 0;
+        int w = (width - 1);
+        int h = (height - 1);
+
+        if ((x < 0) || (x > w) || (y < 0) || (y > h)) {
+            String err = "["+x+";"+y+"] out of ["+w+";"+h+"]";
+            throw new java.lang.IndexOutOfBoundsException(err);
+        }
+
+        if ((x == 0) || (x == w) || (y == 0) || (y == h))
+            return MAX_ENERGY;
+
+        if (verticalE)
+            return energies[y][x];
+        else
+            return energies[x][y];
+    }
+
+    private void relax(int e, int p, int cy, int cx)
+    {
+        int d = distTo[cy][cx];
+        int v = e +  energies[cy][cx];
+        if ((d == 0) || (d > v)) {
+            edgeTo[cy][cx] = p;
+            distTo[cy][cx] = v;
+        }
+    }
+
+    private int[] findMinPath(int Y, int X)
+    {
+        if (DEBUG) st = new Stopwatch();
+
+        clearPaths((Y + 1), (X + 1));
+
+        int e, c, d, v;
+        // from 0 to before last
+        for (int y = 0, cy = 1; y < Y; y++, cy++) {
+            // first element
+            e = distTo[y][0];
+            // relax center child
+            relax(e, 0, cy, 0);
+            // relax right child
+            relax(e, 0, cy, 1);
+            // inner elements
+            for (int x = 1; x < X; x++) {
+                e = distTo[y][x];
+                // relax left child
+                relax(e, x, cy, (x - 1));
+                // relax center child
+                relax(e, x, cy, x);
+                // relax right child
+                relax(e, x, cy, (x + 1));
+            }
+            // last element
+            e = distTo[y][X];
+            // relax left child
+            relax(e, X, cy, X - 1);
+            // relax center child
+            relax(e, X, cy, X);
+        }
+
+        // find first min bottom element
+        int best = 0;
+        v = Integer.MAX_VALUE;
+        for (int x = 0, y = Y; x < X; x++) {
+            d = distTo[y][x];
+            if ((d != 0) && (d < v)) {
+                best = x;
+                v = d;
+            }
+        }
+
+        // build path
+        int[] path = new int[Y + 1];
+        int x = edgeTo[Y][best];
+        path[Y] = best;
+        for (int y = (Y - 1); y > 0; y--) {
+            path[y] = x;
+            x = edgeTo[y][x];
+        }
+        path[0] = x;
+
+        if (DEBUG) System.out.println("seam found in "+st.elapsedTime());
+
+        return path;
     }
 
     public int[] findHorizontalSeam()
     {
-        // sequence of indices for horizontal seam in current picture
-        return null;
+        if (verticalE) {
+            energies = getRotatedMatrix(energies, width, height);
+            verticalE = false;
+        }
+
+        return findMinPath((width - 1), (height - 1));
     }
 
     public int[] findVerticalSeam()
     {
-        // sequence of indices for vertical   seam in current picture
-        return null;
+        if (!verticalE) {
+            energies = getRotatedMatrix(energies, height, width);
+            verticalE = true;
+        }
+
+        return findMinPath((height - 1), (width - 1));
+    }
+
+    private void validateSeam(int[] a, int X, int Y)
+    {
+        if (a.length > X) {
+            String err = "seam length "+a.length+" > "+X;
+            throw new java.lang.IllegalArgumentException(err);
+        }
+        int prev = a[0];
+        for (int i = 0; i < X; i++) {
+            int v = a[i];
+            if ((v >= Y) || (v < 0)) {
+                String err = v+" is out of bounds [0;"+Y+"[";
+                throw new java.lang.IllegalArgumentException(err);
+            }
+            if (Math.abs(prev - v) > 1) {
+                String err = "wrong move: "+prev+" -> "+v;
+                throw new java.lang.IllegalArgumentException(err);
+            }
+            prev = v;
+        }
+    }
+
+    private void removeItem(int[] a, int index)
+    {
+        for (int i = index; i < a.length - 1; i++) {
+            a[i] = a[i+1];
+        }
+    }
+
+    private void removeSeam(int[] a, int J, int[][] e, int[][] p)
+    {
+        for (int i = 0; i < a.length; i++)
+            removeItem(p[i], a[i]);
+
+        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)) {
+                    e[i][v] = energyPriv(i, v);
+                    removeItem(e[i], v+1);
+                } else {
+                    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);
+                }
+            }
+        }
     }
 
     public void removeHorizontalSeam(int[] a)
     {
-        // remove horizontal seam from current picture
+        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 (verticalP) {
+            pixels = getRotatedMatrix(pixels, width, height);
+            verticalP = false;
+        }
+
+        height -= 1;
+        removeSeam(a, height, energies, pixels);
+
+        if (DEBUG) System.out.println("["+width+" "+height+"] in "+st.elapsedTime());
     }
 
     public void removeVerticalSeam(int[] a)
     {
-        // remove vertical   seam from current picture
+        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 (!verticalP) {
+            pixels = getRotatedMatrix(pixels, height, width);
+            verticalP = true;
+        }
+
+        width -= 1;
+        removeSeam(a, width, energies, pixels);
+
+        if (DEBUG) System.out.println("["+width+" "+height+"] in "+st.elapsedTime());
     }
 }