Android flood-fill algorithm [closed]

Question

Does anyone know a iterative and efficient algorithm for flood-fill?

Or is there any way to implement recursive floodfill algorithm without stack overflow error?

Tried the one @ Flood fill using a stack but i cant find a way to work on white and black image.

Answer 1

Somebody ported J. Dunlap's Queue-Linear Flood Fill Algorithm to android here. I've tried it and it's pretty fast.

I've modified the copyImage() method which originally makes use of a class called Utilities which the author hasn't provided.

public class QueueLinearFloodFiller {

    protected Bitmap image = null;
    protected int[] tolerance = new int[] { 0, 0, 0 };
    protected int width = 0;
    protected int height = 0;
    protected int[] pixels = null;
    protected int fillColor = 0;
    protected int[] startColor = new int[] { 0, 0, 0 };
    protected boolean[] pixelsChecked;
    protected Queue<FloodFillRange> ranges;

    // Construct using an image and a copy will be made to fill into,
    // Construct with BufferedImage and flood fill will write directly to
    // provided BufferedImage
    public QueueLinearFloodFiller(Bitmap img) {
        copyImage(img);
    }

    public QueueLinearFloodFiller(Bitmap img, int targetColor, int newColor) {
        useImage(img);

        setFillColor(newColor);
        setTargetColor(targetColor);
    }

    public void setTargetColor(int targetColor) {
        startColor[0] = Color.red(targetColor);
        startColor[1] = Color.green(targetColor);
        startColor[2] = Color.blue(targetColor);
    }

    public int getFillColor() {
        return fillColor;
    }

    public void setFillColor(int value) {
        fillColor = value;
    }

    public int[] getTolerance() {
        return tolerance;
    }

    public void setTolerance(int[] value) {
        tolerance = value;
    }

    public void setTolerance(int value) {
        tolerance = new int[] { value, value, value };
    }

    public Bitmap getImage() {
        return image;
    }

    public void copyImage(Bitmap img) {
        // Copy data from provided Image to a BufferedImage to write flood fill
        // to, use getImage to retrieve
        // cache data in member variables to decrease overhead of property calls
        width = img.getWidth();
        height = img.getHeight();

        image = Bitmap.createBitmap(width, height, Bitmap.Config.RGB_565);
        Canvas canvas = new Canvas(image);
        canvas.drawBitmap(img, 0, 0, null);

        pixels = new int[width * height];

        image.getPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
    }

    public void useImage(Bitmap img) {
        // Use a pre-existing provided BufferedImage and write directly to it
        // cache data in member variables to decrease overhead of property calls
        width = img.getWidth();
        height = img.getHeight();
        image = img;

        pixels = new int[width * height];

        image.getPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
    }

    protected void prepare() {
        // Called before starting flood-fill
        pixelsChecked = new boolean[pixels.length];
        ranges = new LinkedList<FloodFillRange>();
    }

    // Fills the specified point on the bitmap with the currently selected fill
    // color.
    // int x, int y: The starting coords for the fill
    public void floodFill(int x, int y) {
        // Setup
        prepare();

        if (startColor[0] == 0) {
            // ***Get starting color.
            int startPixel = pixels[(width * y) + x];
            startColor[0] = (startPixel >> 16) & 0xff;
            startColor[1] = (startPixel >> 8) & 0xff;
            startColor[2] = startPixel & 0xff;
        }

        // ***Do first call to floodfill.
        LinearFill(x, y);

        // ***Call floodfill routine while floodfill ranges still exist on the
        // queue
        FloodFillRange range;

        while (ranges.size() > 0) {
            // **Get Next Range Off the Queue
            range = ranges.remove();

            // **Check Above and Below Each Pixel in the Floodfill Range
            int downPxIdx = (width * (range.Y + 1)) + range.startX;
            int upPxIdx = (width * (range.Y - 1)) + range.startX;
            int upY = range.Y - 1;// so we can pass the y coord by ref
            int downY = range.Y + 1;

            for (int i = range.startX; i <= range.endX; i++) {
                // *Start Fill Upwards
                // if we're not above the top of the bitmap and the pixel above
                // this one is within the color tolerance
                if (range.Y > 0 && (!pixelsChecked[upPxIdx])
                        && CheckPixel(upPxIdx))
                    LinearFill(i, upY);

                // *Start Fill Downwards
                // if we're not below the bottom of the bitmap and the pixel
                // below this one is within the color tolerance
                if (range.Y < (height - 1) && (!pixelsChecked[downPxIdx])
                        && CheckPixel(downPxIdx))
                    LinearFill(i, downY);

                downPxIdx++;
                upPxIdx++;
            }
        }

        image.setPixels(pixels, 0, width, 1, 1, width - 1, height - 1);
    }

    // Finds the furthermost left and right boundaries of the fill area
    // on a given y coordinate, starting from a given x coordinate, filling as
    // it goes.
    // Adds the resulting horizontal range to the queue of floodfill ranges,
    // to be processed in the main loop.

    // int x, int y: The starting coords
    protected void LinearFill(int x, int y) {
        // ***Find Left Edge of Color Area
        int lFillLoc = x; // the location to check/fill on the left
        int pxIdx = (width * y) + x;

        while (true) {
            // **fill with the color
            pixels[pxIdx] = fillColor;

            // **indicate that this pixel has already been checked and filled
            pixelsChecked[pxIdx] = true;

            // **de-increment
            lFillLoc--; // de-increment counter
            pxIdx--; // de-increment pixel index

            // **exit loop if we're at edge of bitmap or color area
            if (lFillLoc < 0 || (pixelsChecked[pxIdx]) || !CheckPixel(pxIdx)) {
                break;
            }
        }

        lFillLoc++;

        // ***Find Right Edge of Color Area
        int rFillLoc = x; // the location to check/fill on the left

        pxIdx = (width * y) + x;

        while (true) {
            // **fill with the color
            pixels[pxIdx] = fillColor;

            // **indicate that this pixel has already been checked and filled
            pixelsChecked[pxIdx] = true;

            // **increment
            rFillLoc++; // increment counter
            pxIdx++; // increment pixel index

            // **exit loop if we're at edge of bitmap or color area
            if (rFillLoc >= width || pixelsChecked[pxIdx] || !CheckPixel(pxIdx)) {
                break;
            }
        }

        rFillLoc--;

        // add range to queue
        FloodFillRange r = new FloodFillRange(lFillLoc, rFillLoc, y);

        ranges.offer(r);
    }

    // Sees if a pixel is within the color tolerance range.
    protected boolean CheckPixel(int px) {
        int red = (pixels[px] >>> 16) & 0xff;
        int green = (pixels[px] >>> 8) & 0xff;
        int blue = pixels[px] & 0xff;

        return (red >= (startColor[0] - tolerance[0])
                && red <= (startColor[0] + tolerance[0])
                && green >= (startColor[1] - tolerance[1])
                && green <= (startColor[1] + tolerance[1])
                && blue >= (startColor[2] - tolerance[2]) && blue <= (startColor[2] + tolerance[2]));
    }

    // Represents a linear range to be filled and branched from.
    protected class FloodFillRange {
        public int startX;
        public int endX;
        public int Y;

        public FloodFillRange(int startX, int endX, int y) {
            this.startX = startX;
            this.endX = endX;
            this.Y = y;
        }
    }
}

You could also use a thread if you don't want the UI to wait for the image to be filled.

public class FloodFillThread extends Thread {
    ProgressDialog mProgressDialog;
    Bitmap mBitmap;
    int mTargetColor;
    int mNewColor;
    Point mPoint;
    Runnable mCallback;

    public FloodFillThread(ProgressDialog pd, Runnable callback, Bitmap bitmap,
            Point pt, int targetColor, int newColor) {
        mBitmap = bitmap;
        mPoint = pt;
        mTargetColor = targetColor;
        mNewColor = newColor;
        mProgressDialog = pd;
        mCallback = callback;
    }

    @Override
    public void run() {
        QueueLinearFloodFiller filler = new QueueLinearFloodFiller(mBitmap, mTargetColor, mNewColor);
        filler.setTolerance(10);
        filler.floodFill(mPoint.x, mPoint.y);

        handler.sendEmptyMessage(0);
    }

    private Handler handler = new Handler() {
        @Override
        public void handleMessage(Message msg) {
            mProgressDialog.dismiss();
            mCallback.run();
        }
    };
}

Answer 2

The highest ranked answer (by Shubhadeep Chaudhuri) can't handle transparent backgrounds. In order to do that you need to add an alpha check. Here are the changes needed to do that:

Update Private Members

protected int[] tolerance = new int[] { 0, 0, 0, 0 };
protected int[] startColor = new int[] { 0, 0, 0, 0 };

Update Methods

public void setTargetColor(int targetColor) {
    /*Same as before....*/
    startColor[3] = Color.alpha(targetColor);
}

public void setTolerance(int value) {
    tolerance = new int[] { value, value, value, value };
}

protected boolean CheckPixel(int px) {
    int red = (pixels[px] >>> 16) & 0xff;
    int green = (pixels[px] >>> 8) & 0xff;
    int blue = pixels[px] & 0xff;
    int alpha = (Color.alpha(pixels[px]));

    return (red >= (startColor[0] - tolerance[0]) && red <= (startColor[0] + tolerance[0])
            && green >= (startColor[1] - tolerance[1]) && green <= (startColor[1] + tolerance[1])
            && blue >= (startColor[2] - tolerance[2]) && blue <= (startColor[2] + tolerance[2])
            && alpha >= (startColor[3] - tolerance[3]) && alpha <= (startColor[3] + tolerance[3]));
}

Answer 3

this algorithm worked good for me.

private void FloodFill(Bitmap bmp, Point pt, int targetColor, int replacementColor) 
{
    Queue<Point> q = new LinkedList<Point>();
    q.add(pt);
    while (q.size() > 0) {
        Point n = q.poll();
        if (bmp.getPixel(n.x, n.y) != targetColor)
            continue;

        Point w = n, e = new Point(n.x + 1, n.y);
        while ((w.x > 0) && (bmp.getPixel(w.x, w.y) == targetColor)) {
            bmp.setPixel(w.x, w.y, replacementColor);
            if ((w.y > 0) && (bmp.getPixel(w.x, w.y - 1) == targetColor))
                q.add(new Point(w.x, w.y - 1));
            if ((w.y < bmp.getHeight() - 1)
                    && (bmp.getPixel(w.x, w.y + 1) == targetColor))
                q.add(new Point(w.x, w.y + 1));
            w.x--;
        }
        while ((e.x < bmp.getWidth() - 1)
                && (bmp.getPixel(e.x, e.y) == targetColor)) {
            bmp.setPixel(e.x, e.y, replacementColor);

            if ((e.y > 0) && (bmp.getPixel(e.x, e.y - 1) == targetColor))
                q.add(new Point(e.x, e.y - 1));
            if ((e.y < bmp.getHeight() - 1)
                    && (bmp.getPixel(e.x, e.y + 1) == targetColor))
                q.add(new Point(e.x, e.y + 1));
            e.x++;
        }
    }
}

Answer 4

I made the algorithm above faster.
Use getPixels() and setPixels() instead of calling getPixel() repeatedly.

But here is a tarde off.
This algorithm uses more memory space for an array int[bmp.width * bmp.height].

private void floodFill_array(Bitmap bmp, Point pt, int targetColor, int replacementColor)
{
    if(targetColor == replacementColor)
        return;

    int width, height;
    int[] arrPixels;

    width = bmp.getWidth();
    height = bmp.getHeight();

    arrPixels = new int[width*height];
    bmp.getPixels(arrPixels, 0, width, 0, 0, width, height);

    Queue<Point> q = new LinkedList<Point>();
    q.add(pt);

    while (q.size() > 0) {
        Point n = q.poll();
        if (arrPixels[width*n.y + n.x] != targetColor)
            continue;

        Point w = n, e = new Point(n.x + 1, n.y);
        while ((w.x > 0) && (arrPixels[width*w.y + w.x] == targetColor)) {

            arrPixels[width*w.y + w.x] = replacementColor;  // setPixel

            if ((w.y > 0) && (arrPixels[width*(w.y-1) + w.x] == targetColor))
                q.add(new Point(w.x, w.y - 1));
            if ((w.y < height - 1)
                    && (arrPixels[width*(w.y+1) + w.x] == targetColor))
                q.add(new Point(w.x, w.y + 1));
            w.x--;
        }

        while ((e.x < width - 1)
                && (arrPixels[width*e.y + e.x] == targetColor)) {

            arrPixels[width*e.y + e.x] = replacementColor;  // setPixel

            if ((e.y > 0) && (arrPixels[width*(e.y-1) + e.x] == targetColor))
                q.add(new Point(e.x, e.y - 1));
            if ((e.y < height - 1)
                    && (arrPixels[width*(e.y+1) + e.x] == targetColor))
                q.add(new Point(e.x, e.y + 1));
            e.x++;
        }
    }

    bmp.setPixels(arrPixels, 0, width, 0, 0, width, height);
}

If you want to use the "Tolerance" option, use this code below.

int minR, maxR, minG, maxG, minB, maxB;  // instance values

private void floodFill_array(Bitmap bmp, Point pt, int targetColor, int replacementColor, int tolerance)
    {
        if(targetColor == replacementColor)
            return;

        /* tolerable values */
        minR = ((targetColor & 0xFF0000) >> 16) - tolerance;
        if(minR < 0) minR = 0;
        else minR = minR << 16;
        maxR = ((targetColor & 0xFF0000) >> 16) + tolerance;
        if(maxR > 0xFF) maxR = 0xFF0000;
        else maxR = maxR << 16;

        minG = ((targetColor & 0x00FF00) >> 8) - tolerance;
        if(minG < 0) minG = 0;
        else minG = minG << 8;
        maxG = ((targetColor & 0x00FF00) >> 8) + tolerance;
        if(maxG > 0xFF) maxG = 0x00FF00;
        else maxG = maxG << 8;

        minB = (targetColor & 0x0000FF) - tolerance;
        if(minB < 0) minB = 0;
        maxB = (targetColor & 0x0000FF) + tolerance;
        if(maxB > 0xFF) maxB = 0x0000FF;
        /* tolerable values */

        int width, height;
        int[] arrPixels;

        width = bmp.getWidth();
        height = bmp.getHeight();

        arrPixels = new int[width*height];
        bmp.getPixels(arrPixels, 0, width, 0, 0, width, height);

        Queue<Point> q = new LinkedList<Point>();
        q.add(pt);

        while (q.size() > 0) {

            Point n = q.poll();

            if(!isTolerable(arrPixels[width*n.y + n.x]))
                continue;

            Point w = n, e = new Point(n.x + 1, n.y);
            while ((w.x > 0) && isTolerable(arrPixels[width*w.y + w.x])) {
                arrPixels[width*w.y + w.x] = replacementColor;  // setPixel

                if ((w.y > 0) && isTolerable(arrPixels[width*(w.y-1) + w.x]))
                    q.add(new Point(w.x, w.y - 1));

                if ((w.y < height - 1) && isTolerable(arrPixels[width*(w.y+1) + w.x]))
                    q.add(new Point(w.x, w.y + 1));

                w.x--;
            }

            while ((e.x < width - 1) && isTolerable(arrPixels[width*e.y + e.x])) {
                arrPixels[width*e.y + e.x] = replacementColor;  // setPixel

                if ((e.y > 0) && isTolerable(arrPixels[width*(e.y-1) + e.x]))
                    q.add(new Point(e.x, e.y - 1));

                if ((e.y < height - 1) && isTolerable(arrPixels[width*(e.y+1) + e.x]))
                    q.add(new Point(e.x, e.y + 1));

                e.x++;
            }
        }

        bmp.setPixels(arrPixels, 0, width, 0, 0, width, height);
    }


    /** 
     * If the passed color is tolerable, return true.
     */
    private boolean isTolerable(int currentColor){
        int r = currentColor & 0xFF0000;
        int g = currentColor & 0x00FF00;
        int b = currentColor & 0x0000FF;

        if(r<minR || r>maxR || g<minG || g>maxG || b<minB || b>maxB)
            return false;   // less than or grater than tolerable values
        else
            return true;
    }