Get the brightest rectangle within an image

Question

I wrote an extension method for bitmaps which finds the brightest rectangle (with specified width & 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 & 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<Rectangle, float>();
 // Iterate through all possible rectangle points.
 for (var x = 0; x < bitmap.Width - width; x++)
 for (var y = 0; y < bitmap.Height - height; y++)
 {
 var brightnesses = new List<float>();
 // Iterate through all rectangle pixels.
 for (var w = x; w < x + width; w++)
 for (var h = y; h < 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 => 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

Steve

Jobs.png

Jobs

bitmap.Size: {Width=500, Height=500}

brightestRectangle: {X=194,Y=99,Width=50,Height=25}

stopwatch.Elapsed.Seconds: 37

• VisualMelon: Hopefully you'll get a complete answer, but you'll probably end up reading about Bitmap.LockBits at some point. GetPixel is really slow because it has to lock a part of the bitmap with each call. The idea is basically to lock the whole once and then manually index into the buffer. (Not that this makes looking for a better algorithm redundant, which will be necessary for the procedure to scale)
• Owen: @VisualMelon This question has a different focus. I'm semi-familiar with quick image processing.
• VisualMelon: Ah, OK: so you're really only interested in the algorithmic concerns. I'll delete my comment if it reiterated else where, but I'm minded to leave it at the moment for the benefit of any third parties that may not be so aware.
• Heslacher: Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers .
• Owen: @Heslacher My apologies. I won't modify the code ever again.

Answer 1

It is easy to make mistake, but as long as you get the right idea, the implementation is easy.

The calculation is based on doing a accumulation of Brightness. In order to be able to deal with the edges, The accumulation matrix a and b is one size bigger than the bitmap.

[bitmap.Width + 1, bitmap.Height + 1];

So that a[0,y] and a[x,0] (same as b) are all set to zero.

Then what we caculate is let b[x+1,y+1] = Brightness(at point x, y) + b[x+1][y]. as you can see, then b[x+1][y+1] will be equal to

Brightness(at point x, 0) + Brightness(at point x, 1) + ..... + Brightness(at point x, y) 

This is I call cumulation of brightest along the y-axis.

Then we can do along the x-axis, however we do not accumulation on the bitmap Brightness, but accumulate on b. we want

a[x+1,y+1]=b[0,y+1]+b[1,y+1]+....+b[x+1,y+1]

this can be easily done as

a[x+1][y+1]=b[x+1,y+1] +a[x,y+1]

So what does a[x+1,y+1] mean?

a[x+1,y+1] will represent the brightest summation of pixels from {0,0} to {x,y}

a[x+1,y+1] = Brightness({0,0})+Brightness({0,1})+Brightness({0,2}) + ... + Brightness({0,y}) +
 Brightness({1,0})+Brightness({1,1})+Brightness({0,2}) + ... + Brightness({1,y}) +
 ....
 ....
 Brightness({x,0})+Brightness({x,1})+Brightness({x,2}) + ... + Brightness({x,y})

with a[x,y] matrix ready, the next question is how to get the brightest of any rectangle:

Brightness{left, top, width, height} =
a[left+width+1,top+height+1] - a[left+width+1,top] - a[left,top+height+1] + a[left,top]

Here, by my code definition, a rectangle of {left, top, width, height} is include {left,top} point and {left+width, top+height} point. This is just how you consider the rectangle is.

So for the rectangle in my code, a rectangle of width and height, it include width+1 pixels along the x-axis, and height+1 pixels along the y-axis. total pixels (width+1)*(height+1)

To be able to compare the result with the poster, you need use the width and height he given, and minus one on both to put into this calculation.

As I have tested (number below refered in this code.) for width = 49 and height = 24 will give the same result of x_left = 194, y_top = 99.

for width = 50 and height = 25 will give the same result of

x_left = 193, y_top = 98.

So the result is right.

public static Rectangle GetBrightestRectangle(this Bitmap bitmap, int width, int height)
{
 float [,] a = new float[bitmap.Width + 1, bitmap.Height + 1];
 float [,] b = new float[bitmap.Width + 1, bitmap.Height + 1];
 // Iterate through all possible rectangle points.
 for (var x = 0; x < bitmap.Width; x++)
 for (var y = 0; y < bitmap.Height; y++)
 {
 b[x + 1, y + 1] = bitmap.GetPixel(x, y).GetBrightness();
 b[x + 1, y + 1] += b[x + 1, y];
 a[x + 1, y + 1] = b[x + 1, y + 1] + a[x, y + 1];
 }
 float max = 0, max_xp = 0, max_yp = 0;
 for (var x = 0; x < bitmap.Width - width; x++)
 for (var y = 0; y < bitmap.Height - height; y++)
 {
 if (a[x + width + 1, y + height + 1] + a[x, y] - a[x, y + height + 1]- a[x + width + 1, y ] > max)
 {
 max = a[x + width + 1, y + height + 1] + a[x, y] - a[x, y + height + 1] - a[x + width + 1, y];
 max_xp = x;
 max_yp = y;
 }
 }
 // then here max_x and max_y will the brightest rectangle's top left conner.
 // i.e. max_x, max_y, max_x + width, max_y + height
 return Rectangle(max_xp, max_yp, width, height);
}

If you really so much want to let the rectangle of width and height include the top and left edge(low bond in x and y), but exclude the bottom and right edge, you can just change the express in code like blow(need change two nearby places), and that would be it.

Brightness{left, top, width, height} =
 a[left+width,top+height] - a[left+width,top] - a[left,top+height] + a[left,top]

• t3chb0t: This is not a review and answers that contain only code are off-topic. Please describe your improvements and changes.
• phy nju: The code is very straightforward, do not even need a word if you read.
• Owen: You can't specify the second index on construction.
• Owen: It doesn't compile.
• phy nju: yeah, it is not complete, I intend to show the idea underneath.

Answer 2

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<float> queue = new Queue<float>(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 < bitmap.Height; y++)
{
 for (int x = 0; x < bitmap.Width; x++)
 {
 // this is the only time we call bitmap.GetPixel(,)
 queue.Enqueue(bitmap.GetPixel(x, y).GetBrightness());
 if (x >= 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<float>(rectHeight);
float bestAverage = float.NegativeInfinity;
Rectangle bestRectangle = default(Rectangle);
for (int x = 0; x < hSumWidth; x++)
{
 for (int y = 0; y < bitmap.Height; y++)
 {
 queue.Enqueue(hSums[x, y]);
 if (y >= rectHeight)
 {
 float rectangleAverage = queue.Average();
 if (rectangleAverage > 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 < 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.

• Owen: I'm having a tough time understanding the pieces whilst trying to piece it all together simultaneously. Would you mind combining the two code blocks and fixing the variable names for clarity's sake? I would greatly appreciate it!
• VisualMelon: @Owen I've fixed some stuff that was clearly broken in my code (e.g. never reading from hSums); if you're still have trouble later, perhaps I'll put a gist together
• VisualMelon: @Owen Here is the code fixed up and turned into a gist. It runs in under a second on my machine, and seems to find the right rectangle (not thoroughly tested).
• Owen: Thank you, but phy nju has shared a seemingly flawless revamp.
• VisualMelon: @Owen indeed, his method is sound, and will be faster for larger search rectangles because it doesn't avoid subtraction (as per the comment I made about floating point stuff).

Answer 3

You have several factors in your code which performance-wise aren't doing any good:

• GetPixel() is extremly slow compared to other methods.
• You are calling GetPixel() to often.
• Using the Average() method is slow.

Regarding best practices you have some problems as well:

• Not using braces {} although they might be optional.
• missing null check for passed method parameters although the method is public.
• missing validation of passed method parameters, e.g width < 0

---

Performance-wise it would be better to just iterate over each pixel and calculate the brightness of each pixel. In this way GetPixel() will be called only once. I will avoid showing the alternative way of accessing the pixels because you seem to be resistant to given advice like in your previous question regarding opaque.

That beeing said, let us start with getting only the brightness values of a given Bitmap. We could do this in a way which solely relies on Botmap.GetPixel() like

public static float[] ToBrightnessArray(this Bitmap bitmap)
{
 .... calls to GetPixel()
}

but maybe you change your mind so let us pass a Func<Bitmap, int, int, Color> as a second parameter like so

public static float[] ToBrightnessArray(this Bitmap bitmap, Func<Bitmap, int, int, Color> getColor)
{
 if (bitmap == null) { throw new ArgumentNullException(nameof(bitmap)); }
 float[] result = new float[bitmap.Height * bitmap.Width];
 int currentY = -bitmap.Width;
 for (var y = 0; y < bitmap.Height; y++)
 {
 currentY += bitmap.Width;
 for (var x = 0; x < bitmap.Width; x++)
 {
 result[currentY + x] = getColor(bitmap, x, y).GetBrightness();
 }
 }
 return result;
}

Next we need a method to calculate the brightness of a rectangle defined by x, y, width and height for which we make an extension method like so

private static float GetBrightness(this float[] values, int startX, int startY, int width, int height, int bitmapWidth)
{
 int currentY = startY * bitmapWidth;
 int maxY = (startY + height) * bitmapWidth;
 int currentX = currentY + startX;
 float sum = 0;
 float max = width * height;
 for (int y = currentY; y < maxY; y += bitmapWidth)
 {
 for (int x = currentX; x < currentX + width; x++)
 {
 sum += values[x];
 }
 currentX += bitmapWidth;
 }
 return sum / max;
} 

which is used in

public static Rectangle GetBrightestRectangle(this float[] brightnessValues, int bitmapWidth, int bitmapHeight, int width, int height)
{
 if (brightnessValues == null) { throw new ArgumentNullException(nameof(brightnessValues)); }
 if (brightnessValues.Length == 0) { throw new ArgumentOutOfRangeException(nameof(brightnessValues), "Parameter's length may not be 0"); }
 //some more validations for you to add
 int maxBrightnessX = -1;
 int maxBrightnessY = -1;
 float maxBrightness = 0;
 for (int y = 0; y < bitmapHeight - height; y++)
 {
 for (var x = 0; x < bitmapWidth - width; x++)
 {
 var brightness = brightnessValues.GetBrightness(x, y, width, height, bitmapWidth);
 if (brightness > maxBrightness)
 {
 maxBrightness = brightness;
 maxBrightnessX = x;
 maxBrightnessY = y;
 }
 }
 }
 return new Rectangle(maxBrightnessX, maxBrightnessY, width, height); ;
}

which could be either called by

public static Rectangle GetBrightestRectangle(this Bitmap bitmap, int width, int height, Func<Bitmap, int, int, Color> getColor = null)
{
 if (getColor == null) { getColor = (bmp, x, y) => bmp.GetPixel(x, y); }
 //some more validation work for you to do
 float[] brightnessValues = bitmap.ToBrightnessArray(getColor);
 return brightnessValues.GetBrightestRectangle(bitmap.Width, bitmap.Height, width, height);
}

if you are only searching for one rectangle of a specific size, or if you want to search for multiple rectangles you would first call ToBrightnessArray() and pass this array to GetBrightestRectangle() for each rectangle size to search.

With poor man benchmarking by using a Stopwatch this runs in 550 ms on my virtualbox.

Answer 4

You can improve your access to the bitmap by using the LockBits() method. This method locks the pixels in memory and returns a BitmapData structure that gives you access to the pixels via its Scan0 property. Once you have a pointer to the pixels, getting a pixel is just some pointer math and a deference. If you're scanning over a rectangle of the image, this can be much faster in an inner loop than a function call, as you just increment your pointer and read from memory. I'm not a C# developer, so instead of trying to cobble together some example code that will likely be filled with errors, I'll just recommend looking at the above link for an example.