Different Methods of Performing FloodFill

问题:

OK everyone I have several different methods of performing a FloodFill. All of them cause problems. I will list the 3 methods and explain what happens with each one. If anyone could give me some pointers that would be great. I have seen some similar posts but none of them have been for C#, java, or VB.net (the only languages I know).

The givens for this are that I have a class called PixelData which stores a Color in a CellColor member variable. I have an array that is 50x50 of PixelData objects in size called "pixels". I also have a constant called CANVAS_SIZE which is 50 in this case. Here are the three methods I have tried using.

This one is recursive. It is EXTREMELY prone to stack overflows. I have tried settings a timer that enabled a CanFill member after this method is complete. This still does not prevent the overflows:

private void FloodFill(Point node, Color targetColor, Color replaceColor)
{
  //perform bounds checking X
  if ((node.X >= CANVAS_SIZE) || (node.X < 0))
    return; //outside of bounds

  //perform bounds checking Y
  if ((node.Y >= CANVAS_SIZE) || (node.Y < 0))
    return; //ouside of bounds

  //check to see if the node is the target color
  if (pixels[node.X, node.Y].CellColor != targetColor)
    return; //return and do nothing
  else
  {
    pixels[node.X, node.Y].CellColor = replaceColor;

    //recurse
    //try to fill one step to the right
    FloodFill(new Point(node.X + 1, node.Y), targetColor, replaceColor);
    //try to fill one step to the left
    FloodFill(new Point(node.X - 1, node.Y), targetColor, replaceColor);
    //try to fill one step to the north
    FloodFill(new Point(node.X, node.Y - 1), targetColor, replaceColor);
    //try to fill one step to the south
    FloodFill(new Point(node.X, node.Y + 1), targetColor, replaceColor);

    //exit method
    return;
  }
}

Next I have a method that uses a Queue based fill. This method causes OutOfMemory Exceptions at runtime and is EXTREMELY slow when filling the entire canvas. If just filling a small portion of the canvas, it is somewhat effective:

private void QueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
  Queue<Point> points = new Queue<Point>();
  if (pixels[node.X, node.Y].CellColor != targetColor)
    return;

  points.Enqueue(node);

  while (points.Count > 0)
  {
    Point n = points.Dequeue();
    if (pixels[n.X, n.Y].CellColor == targetColor)
      pixels[n.X, n.Y].CellColor = replaceColor;

    if (n.X != 0)
    {
      if (pixels[n.X - 1, n.Y].CellColor == targetColor)
        points.Enqueue(new Point(n.X - 1, n.Y));
    }

    if (n.X != CANVAS_SIZE - 1)
    {
      if (pixels[n.X + 1, n.Y].CellColor == targetColor)
        points.Enqueue(new Point(n.X + 1, n.Y));
    }

    if (n.Y != 0)
    {
      if (pixels[n.X, n.Y - 1].CellColor == targetColor)
        points.Enqueue(new Point(n.X, n.Y - 1));
    }

    if (n.Y != CANVAS_SIZE - 1)
    {
      if (pixels[n.X, n.Y + 1].CellColor == targetColor)
        points.Enqueue(new Point(n.X, n.Y + 1));
    }
  }
  DrawCanvas();
  return;
}

The final method that I have tried also uses a queue based floodfill. This method is MUCH faster than the previous queue based floodfill but also eventually causes OutOfMemory exceptions at runtime. Again, I have tried setting a FillDelay timer that would prevent the user from rapidly clicking but this still doesn't stop the exceptions from occurring. Another bug with this one is that it has a hard time properly filling small areas. I see no point in fixing this until I can get it to not crash.

private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
  Queue<Point> q = new Queue<Point>();
  if (pixels[node.X, node.Y].CellColor != targetColor)
    return;

  q.Enqueue(node);
  while (q.Count > 0)
  {
    Point n = q.Dequeue();
    if (pixels[n.X, n.Y].CellColor == targetColor)
    {
      Point e = n;
      Point w = n;
      while ((w.X != 0) && (pixels[w.X, w.Y].CellColor == targetColor))
      {
        pixels[w.X, w.Y].CellColor = replaceColor;
        w = new Point(w.X - 1, w.Y);
      }

      while ((e.X != CANVAS_SIZE - 1) && (pixels[e.X, e.Y].CellColor == targetColor))
      {
        pixels[e.X, e.Y].CellColor = replaceColor;
        e = new Point(e.X + 1, e.Y);
      }

      for (int i = w.X; i <= e.X; i++)
      {
        Point x = new Point(i, e.Y);
        if (e.Y + 1 != CANVAS_SIZE - 1)
        {
          if (pixels[x.X, x.Y + 1].CellColor == targetColor)
            q.Enqueue(new Point(x.X, x.Y + 1));
        }
        if (e.Y - 1 != -1)
        {
          if (pixels[x.X, x.Y - 1].CellColor == targetColor)
            q.Enqueue(new Point(x.X, x.Y - 1));
        }
      }
    }
  }
}

Thanks for everyone's help! All of these methods are based on pseudo code on wikipedia.

EDIT:

I selected the RevisedQueueFloodFill and modified as suggested so that no variables are declared within the loops. An OutOfMemory is still generated. Even with a filldelay timer.

private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
  Queue<Point> q = new Queue<Point>();

  if (pixels[node.X, node.Y].CellColor != targetColor)
    return;

  q.Enqueue(node);

  Point n, e, w, x;
  while (q.Count > 0)
  {
    n = q.Dequeue();
    if (pixels[n.X, n.Y].CellColor == targetColor)
    {
      e = n;
      w = n;
      while ((w.X != 0) && (pixels[w.X, w.Y].CellColor == targetColor))
      {
        pixels[w.X, w.Y].CellColor = replaceColor;
        w = new Point(w.X - 1, w.Y);
      }

      while ((e.X != CANVAS_SIZE - 1) && (pixels[e.X, e.Y].CellColor == targetColor))
      {
        pixels[e.X, e.Y].CellColor = replaceColor;
        e = new Point(e.X + 1, e.Y);
      }

      for (int i = w.X; i <= e.X; i++)
      {
        x = new Point(i, e.Y);
        if (e.Y + 1 != CANVAS_SIZE - 1)
        {
          if (pixels[x.X, x.Y + 1].CellColor == targetColor)
            q.Enqueue(new Point(x.X, x.Y + 1));
        }
        if (e.Y - 1 != -1)
        {
          if (pixels[x.X, x.Y - 1].CellColor == targetColor)
            q.Enqueue(new Point(x.X, x.Y - 1));
        }
      }
    }
  }
}

回答1:

Ok a couple of things:

1. C# has a recursive limit (determined by stack size) of a few thousand in depth. This means you can't go DEEPER in recursion downward without causing a stack overflow. As soon as a method returns its pointer is popped off the stack. Your problem is not the same as an OutOfMemoryException. The stack holds pointers not actual memory and as such is not meant to hold thousands of pointers.

2. Garbage collection is what's causing your out of memory exception. You need to stop declaring variables inside of your loops. The garbage collector sees these as "still in scope" and will not free up the memory space until the loop completes all iterations. But if you use the same memory address, it will just overwrite it each time and hardly use any memory.

To be clear:

for (int i = w.X; i <= e.X; i++)
{
    Point x = new Point(i, e.Y);
}

Should be like this:

Point x;

for(int i = w.X; i<= e.X; i++)
{
   x = new Point(i, e.Y);
}

This will reuse the memory address like you would want it to.

Hope that helps!

回答2:

I have no idea if this will work, but my own suspicion is that a lot more memory is being used than necessary due to all the 'new' operators, and perhaps due to the intensive nature of the algorithm, the garbage collector didn't have a chance to kick in?

I've rewritten the algorithm so that all the Point variables just get reused rather, but I've not currently got a way of testing this.

I've also taken the liberty of altering the first few lines of code, but this is because of a pet peeve of mine that most flood-fill algorithms you find out there need the user to specify the target colour, when in fact you can simply get the target colour automatically from the point given in the argument.

Anyway, have a try at using this, or otherwise just laugh at it:

private void RevisedQueueFloodFill(Point node, Color replaceColor)
{
    Color targetColor = pixels[node.X, node.Y].CellColor;
    if (targetColor == replaceColor) return;

    Queue<Point> q = new Queue<Point>();
    q.Enqueue(node);

    Point n, t, u;

    while (q.Count > 0)
    {
        n = q.Dequeue();
        if (pixels[n.X, n.Y].CellColor == targetColor)
        {

            t = n;
            while ((t.X > 0) && (pixels[t.X, t.Y].CellColor == targetColor))
            {
                pixels[t.X, t.Y].CellColor = replaceColor;
                t.X--;
            }
            int XMin = t.X + 1;


            t = n;
            t.X++;
            while ((t.X < CANVAS_SIZE - 1) &&
                   (pixels[t.X, t.Y].CellColor == targetColor))
            {
                pixels[t.X, t.Y].CellColor = replaceColor;
                t.X++;
            }
            int XMax = t.X - 1;

            t = n;
            t.Y++;

            u = n;
            u.Y--;

            for (int i = XMin; i <= XMax; i++)
            {
                t.X = i;
                u.X = i;

                if ((t.Y < CANVAS_SIZE - 1) &&
                    (pixels[t.X, t.Y].CellColor == targetColor)) q.Enqueue(t);

                if ((u.Y >= 0) &&
                    (pixels[u.X, u.Y].CellColor == targetColor)) q.Enqueue(u);
            }
        }
    }
}

回答3:

In the third method, you should check the pixels to the immediate west and east of the current point. Instead of checking pixels[w.X, w.Y] you should be checking pixels[w.X - 1, w.Y] and instead of pixels[e.X, e.Y] you should have pixels[e.X + 1, e.Y]. Here is my take on your third method:

private void RevisedQueueFloodFill(Point node, Color targetColor, Color replaceColor)
{
    if (pixels[node.X, node.Y].CellColor != targetColor) return;

    Queue<Point> Q = new Queue<Point>();
    Q.Enqueue(node);

    while (Q.Count != 0)
    {
        Point n = Q.Dequeue();
        if (pixels[n.X, n.Y].CellColor == targetColor)
        {
            int y = n.Y;
            int w = n.X;
            int e = n.X;
            while (w > 0 && pixels[w - 1, y].CellColor == targetColor) w--;
            while (e < CANVAS_SIZE - 1 && pixels[e + 1, y].CellColor == targetColor) e++;

            for (int x = w; x <= e; x++)
            {
                pixels[x, y].CellColor = replaceColor;
                if (y > 0 && pixels[x, y - 1].CellColor == targetColor)
                {
                    Q.Enqueue(new Point(x, y - 1));
                }
                if (y < CANVAS_SIZE - 1 && pixels[x, y + 1].CellColor == targetColor)
                {
                    Q.Enqueue(new Point(x, y + 1));
                }
            }
        }
    }
}

回答4:

The issue here with the basic algorithm is that you queue multiple visits to a point and do a breadth-first search. This means that you create several copies of the same point during each pass. This accumulates exponentially, since each point is allowed to spread (queue more points), even if it's not the target color (already been replaced.)

Set the color at the same time that you Enqueue them (rather than on Dequeue), so that you never end up adding them to the Queue twice.