path: root/Algorithms/Part-II/2-SeamCarving/SeamCarver.java

/* 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;
    // 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;
    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();
    }

    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();
        }
    }

    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) 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]));
            }
        }

        return p;
    }

    public int width()
    {
        return width;
    }

    public int height()
    {
        return height;
    }

    private void rotateMatrix(int[][] matrix)
    {
        int x, y;

        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;
        }

        if (DEBUG) {
            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];
        for (int i = 0; i < y; i++) {
            for (int j = 0; j < x; j++) {
                m[i][j] = matrix[j][i];
            }
        }

        if (matrix == energies)
            energies = m;
        else
            pixels = 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);
    }

    public double energy(int x, int y)
    {
        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();

        edgeTo = new int[Y + 1][X + 1];
        distTo = new int[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());

        edgeTo = null;
        distTo = null;

        return path;
    }

    public int[] findHorizontalSeam()
    {
        if (DEBUG) System.out.println("search horizontal seam");

        if (verticalE) rotateMatrix(energies);

        return findMinPath((width - 1), (height - 1));
    }

    public int[] findVerticalSeam()
    {
        if (DEBUG) System.out.println("search vertical seam");

        if (!verticalE) rotateMatrix(energies);

        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 removeSeam(int[] a, boolean vertical)
    {
        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];
        }

        // 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;
            } else {
                if (v < l) {
                    e[i][v] = energyPriv(i, v);
                } else if (v == l) {
                    e[i][v] = MAX_ENERGY;
                }
                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;
                }
            }
        }
    }

    public void removeHorizontalSeam(int[] a)
    {
        if (width <= 1)
            throw new java.lang.IllegalArgumentException("image is to small");

        if (DEBUG) {
            st = new Stopwatch();
            System.out.println("remove horizontal seam");
        }

        validateSeam(a, width, height);

        removeSeam(a, false);

        if (DEBUG) System.out.println("["+width+" "+height+"] in "+st.elapsedTime());
    }

    public void removeVerticalSeam(int[] a)
    {
        if (height <= 1)
            throw new java.lang.IllegalArgumentException("image is to small");

        if (DEBUG) {
            st = new Stopwatch();
            System.out.println("remove vertical seam");
        }

        validateSeam(a, height, width);

        removeSeam(a, true);

        if (DEBUG) System.out.println("["+width+" "+height+"] in "+st.elapsedTime());
    }
}