BackTrack.java

Go to the documentation of this file.

package theba.core;

import java.awt.Rectangle;

public class BackTrack {

        static short[] queuex;

        static short[] queuey;

        static boolean[][] mark;

        static int first, last; // Pointers to first and last element in queue

        static final int overflow = 1000; // Max size of queue

        static int xx, yy; // Image dimensions

        static int px, py; // Queue pointers

        static int max;

        static int val;

        static short[] lumens; // Lumen image

        static int[] histogram;

        public static short[] backTrack(short[] lumens_, int max, int width,
                        int height, Rectangle bounds) {

                queuex = new short[overflow];
                queuey = new short[overflow];

                xx = width;
                yy = height;

                lumens = lumens_;

                mark = new boolean[width][height];

                for (int y = 0; y < yy; y++) {
                        for (int x = 0; x < xx; x++) {
                                if ((lumens[y * width + x] & 0xff) == max) { // Do backtracking with floodfill
                                        histogram = new int[max + 1];
                                        seed(x, y); // Seeds and creates histogram
                                        // Find minima in histogram
                                        int min = Integer.MAX_VALUE;
                                        int nr = 0;
                                        for (int t = 2; t < histogram.length; t++) {
                                                if (histogram[t] < min) {
                                                        min = histogram[t];
                                                        nr = t;
                                                }
                                        }
                                        // Remove pixels outside crack-point
                                        remove(nr, false);
                                }
                        }
                }
                remove(100, true);
                return lumens;

        }

        public static void remove(int remove, boolean last) {
                for (int y = 0; y < yy; y++) {
                        for (int x = 0; x < xx; x++) {
                                if ((lumens[y * xx + x] & 0xff) >= 50 + remove) {
                                        lumens[y * xx + x] = (byte) 0;
                                }
                                if (last && (lumens[y * xx + x] & 0xff) > 1) {
                                        lumens[y * xx + x] = (byte) 1;
                                }
                        }
                }
        }

        public static void seed(int x, int y) {
                int p;

                max = 0;
                push(x, y);
                while (first != last) {
                        p = pop();
                        px = queuex[p];
                        py = queuey[p];
                        val = lumens[py * xx + px] & 0xff;
                        histogram[val]++;
                        lumens[py * xx + px] = (byte) (50 + val);

                        // Add new points to queue:
                        if (px - 1 >= 0) {
                                if (!mark[px - 1][py]
                                                && (lumens[py * xx + px - 1] & 0xff) <= val
                                                && (lumens[py * xx + px - 1] & 0xff) > 1) {
                                        push(px - 1, py);
                                        mark[px - 1][py] = true;
                                }
                        }
                        if (px + 1 < xx) {
                                if (!mark[px + 1][py]
                                                && (lumens[py * xx + px + 1] & 0xff) <= val
                                                && (lumens[py * xx + px + 1] & 0xff) > 1) {
                                        push(px + 1, py);
                                        mark[px + 1][py] = true;
                                }
                        }
                        if (py - 1 >= 0) {
                                if (!mark[px][py - 1]
                                                && (lumens[(py - 1) * xx + px] & 0xff) <= val
                                                && (lumens[(py - 1) * xx + px] & 0xff) > 1) {
                                        push(px, py - 1);
                                        mark[px][py - 1] = true;
                                }
                        }
                        if (py + 1 < yy) {
                                if (!mark[px][py + 1]
                                                && (lumens[(py + 1) * xx + px] & 0xff) <= val
                                                && (lumens[(py + 1) * xx + px] & 0xff) > 1) {
                                        push(px, py + 1);
                                        mark[px][py + 1] = true;
                                }
                        }
                        if (py + 1 < yy && px - 1 >= 0) {
                                if (!mark[px - 1][py + 1]
                                                && (lumens[(py + 1) * xx + px - 1] & 0xff) <= val
                                                && (lumens[(py + 1) * xx + px - 1] & 0xff) > 1) {
                                        push(px - 1, py + 1);
                                        mark[px - 1][py + 1] = true;
                                }
                        } // 8-connected
                        if (px + 1 < xx && py + 1 < yy) {
                                if (!mark[px + 1][py + 1]
                                                && (lumens[(py + 1) * xx + px + 1] & 0xff) <= val
                                                && (lumens[(py + 1) * xx + px + 1] & 0xff) > 1) {
                                        push(px + 1, py + 1);
                                        mark[px + 1][py + 1] = true;
                                }
                        } // 8-connected
                        if (px - 1 >= 0 && py - 1 >= 0) {
                                if (!mark[px - 1][py - 1]
                                                && (lumens[(py - 1) * xx + px - 1] & 0xff) <= val
                                                && (lumens[(py - 1) * xx + px - 1] & 0xff) > 1) {
                                        push(px - 1, py - 1);
                                        mark[px - 1][py - 1] = true;
                                }
                        } // 8-connected
                        if (py - 1 >= 0 && px + 1 < xx) {
                                if (!mark[px + 1][py - 1]
                                                && (lumens[(py - 1) * xx + px + 1] & 0xff) <= val
                                                && (lumens[(py - 1) * xx + px + 1] & 0xff) > 1) {
                                        push(px + 1, py - 1);
                                        mark[px + 1][py - 1] = true;
                                }
                        } // 8-connected
                }
        }

        public static int pop() {
                first++;
                if (first == overflow) {
                        first = 0;
                        return overflow - 1;
                }
                return first - 1;
        }

        public static void push(int x, int y) {
                queuex[last] = (short) x;
                queuey[last] = (short) y;
                last++;
                if (last == overflow) {
                        last = 0;
                }
                if (last < first) {
                        if (last + overflow - first > max) {
                                max = last + overflow - first;
                        }
                } else if (last - first > max) {
                        max = last - first;
                }
                if (last == first) {
                        System.out.println("Queue overflow");
                        System.exit(1);
                }
        }
}