diff options
| -rw-r--r-- | Algorithms/Part-II/2-SeamCarving/Makefile | 27 | ||||
| -rw-r--r-- | Algorithms/Part-II/2-SeamCarving/SeamCarver.java | 372 |
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()); } } |