4
\$\begingroup\$

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?

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't know much about C#, so I don't want to post an answer here. But it's typically very advantageous to access memory in storage order. Assuming your image is stored row-wise, you could have a for loop going right, until your end condition is met, handling pixels and putting their up and down neighbors on the stack. You also put fewer pixels on the stack this way, a second advantage. \$\endgroup\$ – Cris Luengo Mar 31 '18 at 2:33
  • \$\begingroup\$ @CrisLuengo this is a great suggestion and i have definitely understand what you are saying. however i guess the nature of the flood fill is it must start at any point and be able to walk its way around any object and also not jump into and isolated (island ) sections, however for what i needed with this actual project ( i actually didn't need to care about isolated sections, and this would have worked extremely well;. i.e i just needed a white correction algorithm to change nearly white to white with a threshold. thanks a lot for your comment and advice \$\endgroup\$ – TheGeneral Mar 31 '18 at 2:41
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.