Getting the dominant RGB color of a bitmap

Question

I'm currently running this function 60 times per second in order to get the dominant color on my screen in RGB values. It is using approximately 15% of my CPU on 30FPS and 25% of my CPU on 60FPS. Is there any way I can improve the efficiency of this loop or is there a better way to get the color altogether?

public Color getDominantColor(System.Drawing.Bitmap bmp) {
            BitmapData srcData = bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadOnly, System.Drawing.Imaging.PixelFormat.Format32bppArgb);

            int stride = srcData.Stride;

            IntPtr Scan0 = srcData.Scan0;

            int[] totals = new int[] { 0, 0, 0 };

            int width = bmp.Width;
            int height = bmp.Height;

            unsafe
            {
                byte* p = (byte*)(void*)Scan0;

                for (int y = 0; y < height; y++) {
                    for (int x = 0; x < width; x++) {
                        for (int color = 0; color < 3; color++) {
                            int idx = (y * stride) + x * 4 + color;
                            totals[color] += p[idx];
                        }
                    }
                }
            }

            int avgB = totals[0] / (width * height);
            int avgG = totals[1] / (width * height);
            int avgR = totals[2] / (width * height);

            bmp.UnlockBits(srcData);

            return Color.FromArgb(avgR, avgG, avgB);
        }

Answer 1

If we look at your for loop very carefully we can see that you can eliminate two multiplications:

for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
        for (int color = 0; color < 3; color++) {
            int idx = (y * stride) + x * 4 + color;
            totals[color] += p[idx];
        }
    }
}

You don't use y except for y * stride, and you don't use x except for x * 4, rewrite the for loop and you can eliminate those entirely.

var heightLimit = height * stride;
var widthLimit = width * 4;

for (int y = 0; y < heightLimit; y += stride) {
    for (int x = 0; x < widthLimit; x += 4) {
        for (int color = 0; color < 3; color++) {
            int idx = y + x + color;
            totals[color] += p[idx];
        }
    }
}

By removing all three multiplication operations, we effectively reduce the amount of work we do by a significant portion. (There are roughly 8 instructions in the original, and 6 in the reduced, so we've eliminated 25% of our work.)

Other than that, there really isn't much you can do. You could consider chunking the work, then only recalculate the regions that were re-drawn if that's reasonable, you could also chunk and thread it (this wouldn't reduce CPU usage but it would reduce time spend on this method).

With as frequently as you call this method, the next lines may be a potential for optimization as well:

int avgB = totals[0] / (width * height);
int avgG = totals[1] / (width * height);
int avgR = totals[2] / (width * height);

Why do width * height in all three calculations? Why not store var pixelCount = width * height; then divide by pixelCount? Of course, division is still slow, but you're not using floating-point math so we can't use the reciprocal of it.

You could consider, as mentioned in a comment, using CUDA/OpenGL/GPU-level work. Basically, operating on the GPU itself instead of using the CPU to do what could be very efficient on the GPU. (It's built specifically for this type of processing.) There is at least one Stack Overflow question on running C# code on the GPU, it's not very easy or simple, but it can give you a lot of power.

Answer 2

One useful performance trick when dealing with low-level pixel manipulations like this is that it's often possible to process red and blue together using the 8 bits for green as a gap. Since here you're just adding them, you can add 256 blue values before they would overflow past green into red.

Taking into account John Wu's comment about the stride being irrelevant you can do (untested, and in particular might have endianness bugs; it's several years since I regularly wrote this kind of code, and that was in Java rather than C#):

        unsafe
        {
            uint* p = (uint*)(void*)Scan0;

            uint pixelCount = width * height;
            uint idx = 0;
            while (idx < (pixelCount & ~0xff)) {
                uint sumRR00BB = 0;
                uint sum00GG00 = 0;
                for (int j = 0; j < 0x100; j++) {
                    sumRR00BB += p[idx] & 0xff00ff;
                    sum00GG00 += p[idx] & 0x00ff00;
                    idx++;
                }

                totals[0] += sumRR00BB >> 16;
                totals[1] += sum00GG00 >> 8;
                totals[2] += sumRR00BB & 0xffff;
            }

            // And the final partial block of fewer than 0x100 pixels.
            {
                uint sumRR00BB = 0;
                uint sum00GG00 = 0;
                while (idx < pixelCount) {
                    sumRR00BB += p[idx] & 0xff00ff;
                    sum00GG00 += p[idx] & 0x00ff00;
                    idx++;
                }

                totals[0] += sumRR00BB >> 16;
                totals[1] += sum00GG00 >> 8;
                totals[2] += sumRR00BB & 0xffff;
            }
        }

Answer 3

Five ideas, from easy to hard:

• You can simplify your x/y loop to run in one dimension instead of two-- for ( i = 0; i < y * x * c; i += 4 ). Since you're looking at the whole image, you don't need to worry about the stride. Not only will this reduce the number of operations required, but you may get better performance from your CPU due to better pipelining and branch prediction.

• If you can, use a lower color depth (I don't think you need 24 bits of color depth if you're just computing an average). The smaller storage size will yield a smaller memory area to scan. You will have to shift bits around to do the math, but that sort of thing is faster than memory access.

• You could try resizing or scaling the bitmap to something lower rez. The resize operation will interpolate color. In theory you could scale it to a 1x1 image and just read that one pixel. If you use GDI+ to perform the scale it could use hardware acceleration and be very fast.

• Keep a copy of the last bitmap and its totals. Use REPE CMPSD (yes, this is assembly) to compare your new bitmap to the old one and find non-matching cells. Adjust totals and recompute average. This is probably a little harder than it sounds but the scan would be incredibly fast. This option would work better if most pixels are expected to stay the same from frame to frame.

• Do the entire scan in assembly, four bytes at a time. DWord operations, believe it or not, are faster than byte operations, for a modern CPU. You can get the byte you need through bit shifting, which take very few clock cycles. Been a while for me, but would look something like this:

      MOV ECX, ArrayLength ;ECX is our counter (= bytecount ÷ 4)
      MOV EDX, Scan0       ;EDX is our data pointer
      SUB BX, BX           ;Set BX to 0 for later
  Loop:
      LODSL                ;Load EAX from array, increment pointer
      SHRL 8, EAX          ;Dump the least eight bits
      ADDB GreenTotal, AL  ;Add least 8 bits to green total
      ADCW GreenTotal+1,BX ;Carry the 1
      SHRL 8, EAX          ;Shift right 8 more bits
      ADDB BlueTotal, AL   ;Add least 8 bits to blue total
      ADCW BlueTotal+1, BX ;Carry the 1
      SHRL 8, EAX          ;Shift right 8 more bits
      ADDB RedTotal, AL    ;Add least 8 bits to red total
      ADCW RedTotal+1, BX  ;Carry the 1
      LOOPNZ Loop          ;Decrement CX and keep going until it is zero
  

  If the assembly is too much to take on, you can try to do the same in C++ and maybe the compiler will do a pretty good job of it. At the very least, we have gotten rid of all of your multiplication operations (which can take up 5-20x the number of clock cycles compared to a shift), two of your loops, and a whole bunch of if conditionals (which would mess up your CPU's branch prediction). Also we will get nice big cache bursts regardless of the dword alignment of the byte buffer, because it is a single-dimensional contiguous blob.

Answer 4

Validation

Because the method is public you shouldn't assume that you get a valid non null Bitmap. You should add a null check otherwise you are exposing implementation details of your method.

Naming

Based on the C# Naming guidelines methods should be named using PascalCase casing. Method level variables should be named using camelCase casing. Hence getDominantColor->GetDominantColor and IntPtr Scan0->IntPtr scan0.

Possible problems

You state in your question that this method is used to get the dominant color of your desktop. If you use it only for that, then all will be good.

A problem could come up if you use this method with some different bitmap.

• If the bitmap which is passed is of DIN A4 size with e.g 300dpi your int[] totals will overflow.

Performance

I would suggest to use pointer arithmetic instead of calculating each time the idx value. I also would remove the most inner loop like @Zefick posted.

public System.Drawing.Color GetDominantColor(Bitmap bmp)
{
    if (bmp == null)
    {
        throw new ArgumentNullException("bmp");
    }

    BitmapData srcData = bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadOnly, bmp.PixelFormat);

    int bytesPerPixel = Image.GetPixelFormatSize(srcData.PixelFormat) / 8;

    int stride = srcData.Stride;

    IntPtr scan0 = srcData.Scan0;

    long[] totals = new long[] { 0, 0, 0 };

    int width = bmp.Width * bytesPerPixel;
    int height = bmp.Height;

    unsafe
    {
        byte* p = (byte*)(void*)scan0;

        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x += bytesPerPixel)
            {
                totals[0] += p[x + 0];
                totals[1] += p[x + 1];
                totals[2] += p[x + 2];
            }

            p += stride;
        }
    }

    long pixelCount = bmp.Width * height;

    int avgB = Convert.ToInt32(totals[0] / pixelCount);
    int avgG = Convert.ToInt32(totals[1] / pixelCount);
    int avgR = Convert.ToInt32(totals[2] / pixelCount);

    bmp.UnlockBits(srcData);

    return Color.FromArgb(avgR, avgG, avgB);

}

Benchmarking with BechnmarkDotNet with x64 compiled yields

Yours: 17.5252 ms
EBrown's: 14.6109 ms
Mine: 8.4846 ms
Peter Taylor's: 4.6419 ms

Until @PeterTylor doesn't change its code please see my comment: Getting the dominant RGB color of a bitmap

Answer 5

At least you can unroll the most inner loop without losing quality following way:

for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
         int idx = (y * stride) + x * 4;
         totals[color] += p[idx];
         totals[color+1] += p[idx+1];
         totals[color+2] += p[idx+2];
    }
}

Potentially, the compiler can do this optimization itself, but I'm not sure that it does this inside an "unsafe" block.

Answer 6

Currently doing real-time processing where every frame counts, with a modified version of Peter Taylor's answer. Tested on a weak Raspberry PI it still resulted in 24 out of 25 frames per second. Which is amazing performance knowing what the specifications are of it and running it through Mono.

The method itself was hard to understand at first, but maybe this way of using it might clear a few things up. There probably is a small performance penalty due to the support of averaging in regions, but i'm sure it will still be faster than any other method.

Please note that this only works with 32bpp images due to the use of the Unsigned 32-bit integer to go through the memory.

    public unsafe uint[] GetAverageColorInRegion(Bitmap source, Rectangle region)
    {
        var rectangle = new Rectangle(0, 0, source.Width, source.Height);
        var bitmapData = source.LockBits(rectangle, ImageLockMode.ReadOnly, source.PixelFormat);
        var pixelCount = region.Width * region.Height;
        var scanWidth = bitmapData.Stride / 4;

        uint[] totals = { 0, 0, 0 };
        int flushCounter = 0;
        uint sumRR00BB = 0;
        uint sum00GG00 = 0;

        for (var y = region.Y; y < region.Y + region.Height; y++)
        {
            uint* row = (uint*)bitmapData.Scan0 + y * scanWidth;

            for (var x = region.X; x < region.X + region.Width; x++)
            {
                sumRR00BB += row[x] & 0xff00ff;
                sum00GG00 += row[x] & 0x00ff00;

                // Flush before overflow occurs.
                if (flushCounter++ == 0xff)
                {
                    totals[0] += sumRR00BB >> 16;
                    totals[1] += sum00GG00 >> 8;
                    totals[2] += sumRR00BB & 0xffff;

                    sumRR00BB = 0;
                    sum00GG00 = 0;

                    flushCounter = 0;
                }
            }
        }

        // Flush left-over's.
        totals[0] += sumRR00BB >> 16;
        totals[1] += sum00GG00 >> 8;
        totals[2] += sumRR00BB & 0xffff;

        // Average the totals.
        totals[0] /= (uint)pixelCount;
        totals[1] /= (uint)pixelCount;
        totals[2] /= (uint)pixelCount;

        source.UnlockBits(bitmapData);

        return totals;
    }