Image processing performance for flood fill

Question

I'm working on an image processing routines in C# .Net 4.6 or later.

The background

I have a whole bunch of image processing methods that work on a specialized DirectBitmap Class. Without going into to much depth, the premise of the class is it internally calls LockBits on the Bitmap, which pins the memory and allows direct pointer access.

The code posted below is actually an optionally Parallel Method (most of the Image processing methods work this way) which is the extra plumbing you can see.

However the primary concern of what i want reviewed is the Workload (local Method)

The workload

This is a basic 4 point Flood Fill implementation (with a threshold).

In short :

• It starts at a certain points in an image (initializes the stack).
• It checks the source image a pixel (via a pointer) is within a threshold
• Updates the Source image with a mask color (to determine what has been checked)
• Updates the Target image with the Flood Fill Color
• Adds 4 new points on the stack to check in the future.

The Code

public static Bitmap ToColorCorrection3(this Bitmap source, Color sourceColor, Color targetColor, Color maskColor, int threshold, BitmapParallelOptions options = null)
{   

   // what i want revied
   unsafe void Workload(DirectBitmap dbMask, DirectBitmap dbDest, Rectangle? bounds = null)
   {
      // storing values so we don't need IL to reevaluate them
      var rect = bounds ?? dbMask.Bounds;
      var maskColorInt = maskColor.ToArgb();
      var targetColorInt = targetColor.ToArgb();

      // Create the stack
      var pixels = new Stack<Point>();

      // This is just a way to have multiple starting points, 
      // it just looks in the corners at a rectangle
      // of pixels to see if they are within a threshold and to allow 
      // it to pick starting points, this method doesn't need to be reviewed
      AddStartLocations(dbMask, rect, pixels, sourceColor, threshold);

      // start the loop
      while (pixels.Count > 0)
      {
         var point = pixels.Pop(); // get next point to check

         // make sure we are in side our rectangle (very important, unsafe)
         if (!rect.Contains(point))
         {
            continue;
         }

         // get the color of a pixel
         var value = *(dbMask.Scan0Ptr + point.X + point.Y * dbMask.Stride);

         // convert to Rbg
         var r = ((value >> 0) & 255) - sourceColor.R;
         var g = ((value >> 8) & 255) - sourceColor.G;
         var b = ((value >> 16) & 255) - sourceColor.B;

         // simple threshold calc
         // this also makes sure we arnt searching the same pixel twice
         if ((r * r + g * g + b * b) > threshold * threshold)
         {
            continue; // failed so continue
         }

         // update the source (mask) this just for internal use to know where we have been
         *(dbMask.Scan0Ptr + point.X + point.Y * dbMask.Stride) = maskColorInt;

         // update the target with the fill color
         *(dbDest.Scan0Ptr + point.X + point.Y * dbDest.Stride) = targetColorInt;

         // push 4 new pixels on the the stack
         pixels.Push(new Point(point.X - 1, point.Y));
         pixels.Push(new Point(point.X + 1, point.Y));
         pixels.Push(new Point(point.X, point.Y - 1));
         pixels.Push(new Point(point.X, point.Y + 1));
      }
   }

   using (DirectBitmap dbMask = source.FastLock(), dbDest = source.FastLock(BitmapStyle.Clone))
   {
      if (options == null)
      {
         Workload(dbMask, dbDest);
      }
      else
      {   
         Parallel.ForEach(dbMask.Bounds.GetSubRects(options.TableSize), options.ParallelOptions, rect => Workload(dbMask, dbDest, rect));
      }
      return dbDest.Clone();
   }

}

Some ways i have thought of making this more efficient.

• Instead of storing a point, just store the offset (however there is 2 images (pointers that need consult))
• Save some IL by not calling contains and do the check there.
• Instead of putting each 4 points back on the stack, check there and then if it passes the rectangle bounds check and threshold (for each new point)

Has anyone got any ideas?

Answer 1

I managed to shave quite a bit off the IL and processing time

The key optimizations here were

• Ditching the second image and just using a pointer to an array to check if a location has been checked
• Anything that is being reused create a variable for it
• Removing the Stack and decoding the X,Y in an int
• Prechecking the location before adding it to the stack
• Prechecking the bounds before adding it to the stack

Here is the end result for your enjoyment

public static unsafe Bitmap ToColorCorrection(this Bitmap source, Color sourceColor, int threshold, BitmapParallelOptions options = null)
{
   using (var db = source.FastLock(BitmapStyle.Clone))
   {
      // create a new array to keep of locations that have been checked
      var aray = new int[db.Width * db.Height];

      // pin the array in memory, fixed dosnt really work in this scenerio
      // as it dosnt like delegates or lamda
      var gcHandle = GCHandle.Alloc(aray, GCHandleType.Pinned);

      var targetColorInt = sourceColor.ToArgb();

      // Pointers and stride
      var dbPtr = db.Scan0Ptr;
      var dbStride = db.Stride;

      // get the pointer from the pinned address
      var maskPtr = (int*)gcHandle.AddrOfPinnedObject()
                                    .ToPointer();

      void Workload(Rectangle? bounds = null)
      {
         // The basic premise here is, if its used more than once
         // or if its accessed by a period then store it in a variable once
         // for reuse

         // ReSharper disable AccessToDisposedClosure

         // The rectangle we are working with
         // If single threaded its just the main Image Rec
         var rect = bounds ?? db.Bounds;

         // ReSharper restore AccessToDisposedClosure

         // location variables
         var rX = rect.X;
         var rY = rect.Y;
         var rW = rect.X + rect.Width;
         var rH = rect.Y + rect.Height;

         // precaculated threshold
         var thresh = threshold * threshold;

         // source RBG values
         var sR = sourceColor.R;
         var sG = sourceColor.G;
         var sB = sourceColor.B;

         // worker stack
         var pixels = new Stack<int>();

         // intial start places, basicaly just the 4 corners
         pixels.Push((rX << 16) + rY);
         pixels.Push(((rW - 1) << 16) + rY);
         pixels.Push(((rW - 1) << 16) + rH - 1);
         pixels.Push((rX << 16) + rH - 1);

         // main worker loop
         while (pixels.Count > 0)
         {
            // get next potential fill location
            var point = pixels.Pop();

            // decocde the x and y 
            var y = point & 0xffff;
            var x = (point >> 16) & 0xffff;

            // prestore the pointer address claculations
            var offset = x + y * dbStride;
            var pImg = dbPtr + offset;
            var pMask = maskPtr + offset;

            // decode the RBG from the image Pointer
            var r = ((*pImg >> 0) & 255) - sR;
            var g = ((*pImg >> 8) & 255) - sG;
            var b = ((*pImg >> 16) & 255) - sB;

            // do the threshold check, 
            if (r * r + g * g + b * b > thresh)
            {
               continue;
            }

            // make this location as done
            *pMask = 1;

            // set the flood fill color
            *pImg = targetColorInt;

            // push 4 new locations on the stack
            if (!(x - 1 < rX || x - 1 >= rW || y < rY || y >= rH) && *(pMask - 1) != 1)
            {
               pixels.Push(((x - 1) << 16) + y);
            }
            if (!(x + 1 < rX || x + 1 >= rW || y < rY || y >= rH) && *(pMask + 1) != 1)
            {
               pixels.Push(((x + 1) << 16) + y);
            }
            if (!(x < rX || x >= rW || y - 1 < rY || y - 1 >= rH) && *(pMask - dbStride) != 1)
            {
               pixels.Push((x << 16) + y - 1);
            }
            if (!(x < rX || x >= rW || y + 1 < rY || y + 1 >= rH) && *(pMask + dbStride) != 1)
            {
               pixels.Push((x << 16) + y + 1);
            }
         }
      }

      // some sugar to processing single or parallel 
      DoWorkload(db.Bounds, options, Workload);

      // free the handle
      gcHandle.Free();

      return db.Clone();
   }
}

In the spirit of the question, if anyone has further optimizations i will be happy to mark them as the correct answer