Flood Fill

[ColinWhite]

Hi,

I've written a short program to flood fill a simple black and white image of the outline of a cell. The image is too big to do this recursively (about 400x400 pixels) so I've used queues. However, my program only runs for a short while and then returns and out of memory error. I'm really not sure why it ends up using an upwards of 400MB of memory before it crashes.

Any help is appreciated.
-Colin

import ij.*;
import ij.plugin.filter.PlugInFilter;
import ij.process.*;
import ij.gui.*;
import java.awt.*;
import java.util.*;
import java.lang.Math.*;

public class Filopodia_Analyzer implements PlugInFilter{
        ImagePlus analyzed;

        public int setup(String arg, ImagePlus analyzed){
                return DOES_ALL;
        }

        public void run(ImageProcessor anal_ip){

                Point n = new Point();

                ArrayDeque<Point> q = new ArrayDeque<Point>();

                if(anal_ip.getPixelValue(12, 10) == 255.0) q.offer(new Point(12, 10));

                while(q.size() != 0){
                        n = q.poll();
                        if(anal_ip.getPixelValue(n.x, n.y) == 255.0) anal_ip.putPixel(n.x, n.y, 223);

                        if(anal_ip.getPixelValue(n.x-1, n.y) == 255.0) q.offer(new Point(n.x-1, n.y));
                        if(anal_ip.getPixelValue(n.x+1, n.y) == 255.0) q.offer(new Point(n.x+1, n.y));
                        if(anal_ip.getPixelValue(n.x, n.y-1) == 255.0) q.offer(new Point(n.x, n.y-1));
                        if(anal_ip.getPixelValue(n.x, n.y+1) == 255.0) q.offer(new Point(n.x, n.y+1));
                        analyzed.updateAndDraw();
                }
        }
}

[Michael Schmid]

Hi Colin,

there is a lot of overhead needed for the Point objects. Even if you  
have no memory problem, Garbage collection of some 100000 Point  
objects will make it unnecessarily slow.
Also, this code is not very efficient because you will enter many  
points into the queue more than once.

ImageJ has an efficient built-in flood fill algorithm, why not use  
it? See
   http://pacific.mpi-cbg.de/cgi-bin/gitweb.cgi?
p=imagej.git;a=blob;f=ij/process/FloodFiller.java

Michael
________________________________________________________________

On 21 Jul 2011, at 17:06, ColinWhite wrote:

> Hi,
>
> I've written a short program to flood fill a simple black and white  
> image of
> the outline of a cell. The image is too big to do this recursively  
> (about
> 400x400 pixels) so I've used queues. However, my program only runs  
> for a
> short while and then returns and out of memory error. I'm really  
> not sure
> why it ends up using an upwards of 400MB of memory before it crashes.
>
> Any help is appreciated.
> -Colin
>
> import ij.*;
> import ij.plugin.filter.PlugInFilter;
> import ij.process.*;
> import ij.gui.*;
> import java.awt.*;
> import java.util.*;
> import java.lang.Math.*;
>
> public class Filopodia_Analyzer implements PlugInFilter{
> ImagePlus analyzed;
>
> public int setup(String arg, ImagePlus analyzed){
> return DOES_ALL;
> }
>
> public void run(ImageProcessor anal_ip){
>
> Point n = new Point();
>
> ArrayDeque<Point> q = new ArrayDeque<Point>();
>
> if(anal_ip.getPixelValue(12, 10) == 255.0) q.offer(new Point(12,  
> 10));
>
> while(q.size() != 0){
> n = q.poll();
> if(anal_ip.getPixelValue(n.x, n.y) == 255.0) anal_ip.putPixel
> (n.x, n.y,
> 223);
>
> if(anal_ip.getPixelValue(n.x-1, n.y) == 255.0) q.offer(new Point
> (n.x-1,
> n.y));
> if(anal_ip.getPixelValue(n.x+1, n.y) == 255.0) q.offer(new Point
> (n.x+1,
> n.y));
> if(anal_ip.getPixelValue(n.x, n.y-1) == 255.0) q.offer(new Point
> (n.x,
> n.y-1));
> if(anal_ip.getPixelValue(n.x, n.y+1) == 255.0) q.offer(new Point
> (n.x,
> n.y+1));
> analyzed.updateAndDraw();
> }
> }
> }
>
> --
> View this message in context: http://imagej.588099.n2.nabble.com/ 
> Flood-Fill-tp6607146p6607146.html
> Sent from the ImageJ mailing list archive at Nabble.com.