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

    public int height()
    {
        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)
    {
        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()
    {
        if (verticalE) {
            energies = getRotatedMatrix(energies, width, height);
            verticalE = false;
        }

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

    public int[] findVerticalSeam()
    {
        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)
    {
        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)
    {
        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());
    }
}