Get the brightest rectangle within an image I wrote an extension method for bitmaps which finds the brightest rectangle (with specified width &amp; height) within an image.

Hopefully my code comments eliminate any confusion. If not, please let me know what I need to elaborate on.

I would like some help reducing repetitive calls to the conjoined Bitmap.GetPixel &amp; Color.GetBrightness methods during the scanning process. (subsequently improving performance tremendously)

Method:

    public static Rectangle GetBrightestRectangle(this Bitmap bitmap, int width, int height)
    {
        // Each rectangle's value is its average pixel color.
        var rectangles = new Dictionary&lt;Rectangle, float&gt;();

        // Iterate through all possible rectangle points.
        for (var x = 0; x &lt; bitmap.Width - width; x++)
            for (var y = 0; y &lt; bitmap.Height - height; y++)
            {
                var brightnesses = new List&lt;float&gt;();

                // Iterate through all rectangle pixels.
                for (var w = x; w &lt; x + width; w++)
                    for (var h = y; h &lt; y + height; h++)
                    {
                        brightnesses.Add(bitmap.GetPixel(w, h).GetBrightness());
                    }

                rectangles.Add(new Rectangle(x, y, width, height), brightnesses.Average());
            }

        // The brightness ranges from 0.0 through 1.0, where 0.0 represents black and 1.0 represents white.
        return rectangles.OrderByDescending(pair =&gt; pair.Value).First().Key;
    }


Demo:

        var bitmap = (Bitmap)Image.FromFile(@"C:\Steve.png");
        var stopwatch = Stopwatch.StartNew();
        var brightestRectangle = bitmap.GetBrightestRectangle(50, 25);
        stopwatch.Stop();
        using (var graphics = Graphics.FromImage(bitmap))
        {
            graphics.DrawRectangle(new Pen(Color.Lime, 5), brightestRectangle);
        }
        bitmap.Save(@"C:\Jobs.png");
        Console.WriteLine($"bitmap.Size: {bitmap.Size}");
        Console.WriteLine($"brightestRectangle: {brightestRectangle}");
        Console.WriteLine($"stopwatch.Elapsed.Seconds: {stopwatch.Elapsed.Seconds}");


Steve.png



Jobs.png




  bitmap.Size: {Width=500, Height=500}
  
  brightestRectangle: {X=194,Y=99,Width=50,Height=25}
  
  stopwatch.Elapsed.Seconds: 37
Performance

Here is one simple suggestion, which doesn't require any real thought, and is simple enough to implement. It will result in only calling GetPixel once per pixel, but obviously has some other costs.

Instead of convolving a whole w*h rectangle over the image, first compute the sum of each horizontal strip of length w and store it in a buffer (essentially the same size as the image). Then compute the average of each h tall vertical strip in this buffer, each of which represents a w*h rectangle in the original image.

My only hesitation with suggesting this, is that currently you seem to deliberately call Average on a collection of pixels, which could give you slightly different results owing to joys of float-point maths (assuming nothing about the implementation). Any such error would, however, be imperceptible, but we don't know what your application is, so it is not for us to say that this isn't an issue (but I would wager it isn't).

Because this is just as an example, and I don't know much about floating point maths, I'll follow suit with the OP and only ever perform additions: I'll keep a queue (e.g. ring buffer) of elements as we scan across and down. You could instead keep a running sum, instead of computing sums over a queue, which would make the algorithm complexity order 2 rather than order 3 (the code in the OP is order 4). This is probably the most sensible change if performance is a serious concern, but I'll let you work out the changes necessary.

I'll ignore the joys of considering the actual memory layout of bitmaps: it might be better to sum across the columns first, and then the width, but I can't remember.



int hSumWidth = bitmap.Width - rectWidth + 1;
int hSumHeight = bitmap.Height;
float[,] hSums = new float[hSumWidth, hSumHeight];

Queue&lt;float&gt; queue = new Queue&lt;float&gt;(rectWidth);

// I would never use `var` in a for-loop; makes it immediately obvious we are using ints and not floats
for (int y = 0; y &lt; bitmap.Height; y++)
{
    for (int x = 0; x &lt; bitmap.Width; x++)
    {
        // this is the only time we call bitmap.GetPixel(,)
        queue.Enqueue(bitmap.GetPixel(x, y).GetBrightness());

        if (x &gt;= rectWidth)
        {
            hSums[x - rectWidth, y] = queue.Sum();
            // if the ring-buffer isn't fixed size, we may have to manually evict the old value at this point
            queue.Dequeue();
        }
    }

    queue.Clear(); // we don't need to do this, but it is much clearer if we do
}


Now we have our 2D buffer of sums of horizontal strips of width w. Now we perform a similar operation to scan down them, and find the 'brightest' rectangle.

I don't see any real reason to keep an actual record of all the rectangles; we can just remember the best as we go along. It will reduce the time complexity (from O(n^2 log(n)) to O(n^2)) and won't clutter the code too much.

queue = new Queue&lt;float&gt;(rectHeight);

float bestAverage = float.NegativeInfinity;
Rectangle bestRectangle = default(Rectangle);

for (int x = 0; x &lt; hSumWidth; x++)
{
    for (int y = 0; y &lt; bitmap.Height; y++)
    {
        queue.Enqueue(hSums[x, y]);

        if (y &gt;= rectHeight)
        {
            float rectangleAverage = queue.Average();

            if (rectangleAverage &gt; bestAverage)
            {
                bestRectangle = new Rectangle(x, y - rectHeight, rectWidth, rectHeight);
                bestAverage = rectangleAverage;
            }

            // if the ring-buffer isn't fixed size, we may have to manually evict the old value at this point
            queue.Dequeue();
        }
    }

    queue.Clear();
}

return bestRectangle;


I have tested this quickly against your test image, and it finds a rectangle in the same place (quick visual inspection, no promises). Your code has an order 4 time complexity; this only has order 3 time complexity, 2 if you replace the queues with a running count. There is really nothing clever going on, but I think it ought to work. A gist of the complete method is provided.

Other

I've changed width and height into rectWidth and rectHeight, so that there can be no confusion.

I think you have an off-by-one error:

for (var x = 0; x &lt; bitmap.Width - width; x++)


Consider if you had a 1*1 image, looking for 1*1 rectangles. This loop would never run, no rectangle would be found, and .First() would crash on the last line.