summaryrefslogtreecommitdiffstats
path: root/Algorithms/Part-II/2-SeamCarving/SeamCarver.java
diff options
context:
space:
mode:
Diffstat (limited to 'Algorithms/Part-II/2-SeamCarving/SeamCarver.java')
-rw-r--r--Algorithms/Part-II/2-SeamCarving/SeamCarver.java372
1 files changed, 358 insertions, 14 deletions
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());
}
}
generated by cgit v1.1-2-g2b99 at 2024-11-22 06:16:36 +0100