CODEWITHSUNDEEP
java
Torn
Torn

Reputation: 346

Code stuck in loop

I made a script that takes a picture, starts from the top left corner (a white pixel in the case of my test image), and proceeds to go through the image like a magic wand tool, selecting the pixels that are of a similar enough color.

But the script doesn't finish executing even after going through the loop more times than there are pixels in the image.

The test image is roughly 160K pixels. Tools.loadImage() is a self-written method. I've used it elsewhere, it most probably works. The following is not the entirety of my code, but the part that seemed relevant to the problem.

static int[][][] image;

public static void main(String[] args) {
    image = Tools.loadImage(path1);

    int height = image.length;
    int width = image[0].length;
    int[][][] newImage = new int[height][width][4];

    ArrayList<Integer> toCheck = new ArrayList<Integer>();
    ArrayList<Integer> checked = new ArrayList<Integer>();

    int[] baseColor = image[0][0];
    toCheck.add(0);

    while (!toCheck.isEmpty()) {
        i++;
        int coords = toCheck.get(0);
        int x = coords % width;
        int y = coords / width;

        if (check(x, y, baseColor, 128)) {
            coords = y * width + x - 1;
            if (x > 0 && !(checked.contains(coords) || toCheck.contains(coords))) {
                toCheck.add(coords);
            }
            coords = y * width + x + 1;
            if (x < width - 1 && !(checked.contains(coords) || toCheck.contains(coords))) {
                toCheck.add(coords);
            }
            coords = (y - 1) * width + x;
            if (y > 0 && !(checked.contains(coords) || toCheck.contains(coords))) {
                toCheck.add(coords);
            }
            coords = (y + 1) * width + x;
            if (y < height - 1 && !(checked.contains(coords) || toCheck.contains(coords))) {
                toCheck.add(coords);
            }
        }

        checked.add(coords);
        toCheck.remove(0);
    }
}

static boolean check(int x, int y, int[] color, int threshold) {
    for (int i = 0; i < 3; i++) {
        if (Math.abs(image[y][x][i] - color[i]) > threshold) {
            return false;
        }
    }
    return true;
}

PS. If you feel like pointing out obvious ways to make this loop faster, that would be appreciated as well.

Upvotes: 1

Views: 654

Answers (2)

shinobi
shinobi

Reputation: 361

You're overwriting coords in the body of the loop, so at the end of each iteration you're marking the wrong pixel. It's perfectly safe to move the marking immediately after popping the next point off toCheck.

Perfomance-wise, consider using a BitSet for checked (as per @JB Nizet's suggestion,) and an ArrayDeque for toCheck.

Upvotes: 1

laune
laune

Reputation: 31300

The add to checked is in the wrong place.

while (!toCheck.isEmpty()) {
    i++;
    int coords = toCheck.get(0);
    checked.add(coords);        // important
    toCheck.remove(0);          // might as well do this here too
    int x = coords % width;
    int y = coords / width;

coords is overwritted repeatedly in the loop, and thus the current pixel is not added but the last of the four neighbours. Thus some condition fails later and some wrong pixel is added toCheck.

Upvotes: 2

Related Questions