How to do alpha blend fast?

Question

I am using c++ , I want to do alpha blend using the following code.

#define CLAMPTOBYTE(color) if((color) & (~255)) {color = (BYTE)((-(color)) >> 31);}else{color = (BYTE)(color);}
#define GET_BYTE(accessPixel, x, y, scanline, bpp)\
((BYTE*)((accessPixel) + (y) * (scanline) + (x) * (bpp))) 

 for (int y = top ; y < bottom; ++y)
 {
  BYTE* resultByte = GET_BYTE(resultBits, left, y, stride, bytepp);
  BYTE* srcByte = GET_BYTE(srcBits, left, y, stride, bytepp);
  BYTE* srcByteTop = GET_BYTE(srcBitsTop, left, y, stride, bytepp);
  BYTE* maskCurrent = GET_GREY(maskSrc, left, y, width);
  int alpha = 0;
  int red = 0;
  int green = 0;
  int blue = 0;
  for (int x = left; x < right; ++x)
  {
   alpha = *maskCurrent;
   red = (srcByteTop[R] * alpha + srcByte[R] * (255 - alpha)) / 255;
   green = (srcByteTop[G] * alpha + srcByte[G] * (255 - alpha)) / 255;
   blue = (srcByteTop[B] * alpha + srcByte[B] * (255 - alpha)) / 255;
   CLAMPTOBYTE(red);
   CLAMPTOBYTE(green);
   CLAMPTOBYTE(blue);
   resultByte[R] = red;
   resultByte[G] = green;
   resultByte[B] = blue;
   srcByte += bytepp;
   srcByteTop += bytepp;
   resultByte += bytepp;
   ++maskCurrent;
  }
 }

however I find it is still slow, it takes about 40 - 60 ms when compose two 600 * 600 image. Is there any method to improve the speed to less then 16ms?

Can any body help me to speed this code? Many thanks!

Answer 1

I've done similar code in unsafe C#. Is there any reason you aren't looping through each pixel directly? Why use all the BYTE* and GET_BYTE() calls? That is probably part of the speed issue.

What does GET_GRAY look like?

More importantly, are you sure your platform doesn't expose alpha blending capabilities? What platform are you targeting? Wiki informs me that the following support it out of the box:

• Mac OS X
• Windows 2000, XP, Server 2003, Windows CE, Vista and Windows 7
• The XRender extension to the X Window System (this includes modern Linux systems)
• RISC OS Adjust
• QNX Neutrino
• Plan 9
• Inferno
• AmigaOS 4.1
• BeOS, Zeta and Haiku
• Syllable
• MorphOS

Answer 2

I think hardware support will help you. try to move the logic from software to hardware if feasible

Answer 3

You can use 4 bytes per pixel in both images (for memory alignment), and then use SSE instructions to process all channels together. Search "visual studio sse intrinsics".

Answer 4

Depending on the target architecture, you could try either vectorize or parallellize the function.

Other than that, try to linearize the whole method (i.e. no loop-in-loop) and work with a quadruple of bytes at once, that would lose the overhead of working with single bytes plus make it easier for the compiler to optimize the code.

Answer 5

Move it to the GPU.

Answer 6

Use SSE - start around page 131.

The basic workflow

1. Load 4 pixels from src (16 1 byte numbers) RGBA RGBA RGBA RGBA (streaming load)

2. Load 4 more which you want to blend with srcbytetop RGBx RGBx RGBx RGBx

3. Do some swizzling so that the A term in 1 fills every slot I.e

   xxxA xxxB xxxC xxxD -> AAAA BBBB CCCC DDDD

   In my solution below I opted instead to re-use your existing "maskcurrent" array but having alpha integrated into the "A" field of 1 will require less loads from memory and thus be faster. Swizzling in this case would probably be: And with mask to select A, B, C, D. Shift right 8, Or with origional, shift right 16, or again.

4. Add the above to a vector that is all -255 in every slot

5. Multiply 1 * 4 (source with 255-alpha) and 2 * 3 (result with alpha).

   You should be able to use the "multiply and discard bottom 8 bits" SSE2 instruction for this.

6. add those two (4 and 5) together

7. Store those somewhere else (if possible) or on top of your destination (if you must)

Here is a starting point for you:

    //Define your image with __declspec(align(16)) i.e char __declspec(align(16)) image[640*480]
    // so the first byte is aligned correctly for SIMD.
    // Stride must be a multiple of 16.

    for (int y = top ; y < bottom; ++y)
    {
        BYTE* resultByte = GET_BYTE(resultBits, left, y, stride, bytepp);
        BYTE* srcByte = GET_BYTE(srcBits, left, y, stride, bytepp);
        BYTE* srcByteTop = GET_BYTE(srcBitsTop, left, y, stride, bytepp);
        BYTE* maskCurrent = GET_GREY(maskSrc, left, y, width);
        for (int x = left; x < right; x += 4)
        {
            //If you can't align, use _mm_loadu_si128()
            // Step 1
            __mm128i src = _mm_load_si128(reinterpret_cast<__mm128i*>(srcByte)) 
            // Step 2
            __mm128i srcTop = _mm_load_si128(reinterpret_cast<__mm128i*>(srcByteTop)) 

            // Step 3
            // Fill the 4 positions for the first pixel with maskCurrent[0], etc
            // Could do better with shifts and so on, but this is clear
            __mm128i mask = _mm_set_epi8(maskCurrent[0],maskCurrent[0],maskCurrent[0],maskCurrent[0],
                                        maskCurrent[1],maskCurrent[1],maskCurrent[1],maskCurrent[1],
                                        maskCurrent[2],maskCurrent[2],maskCurrent[2],maskCurrent[2],
                                        maskCurrent[3],maskCurrent[3],maskCurrent[3],maskCurrent[3],
                                        ) 

            // step 4
            __mm128i maskInv = _mm_subs_epu8(_mm_set1_epu8(255), mask) 

            //Todo : Multiply, with saturate - find correct instructions for 4..6
            //note you can use Multiply and add _mm_madd_epi16

            alpha = *maskCurrent;
            red = (srcByteTop[R] * alpha + srcByte[R] * (255 - alpha)) / 255;
            green = (srcByteTop[G] * alpha + srcByte[G] * (255 - alpha)) / 255;
            blue = (srcByteTop[B] * alpha + srcByte[B] * (255 - alpha)) / 255;
            CLAMPTOBYTE(red);
            CLAMPTOBYTE(green);
            CLAMPTOBYTE(blue);
            resultByte[R] = red;
            resultByte[G] = green;
            resultByte[B] = blue;
            //----

            // Step 7 - store result.
            //Store aligned if output is aligned on 16 byte boundrary
            _mm_store_si128(reinterpret_cast<__mm128i*>(resultByte), result)
            //Slow version if you can't guarantee alignment
            //_mm_storeu_si128(reinterpret_cast<__mm128i*>(resultByte), result)

            //Move pointers forward 4 places
            srcByte += bytepp * 4;
            srcByteTop += bytepp * 4;
            resultByte += bytepp * 4;
            maskCurrent += 4;
        }
    }

To find out which AMD processors will run this code (currently it is using SSE2 instructions) see Wikipedia's List of AMD Turion microprocessors. You could also look at other lists of processors on Wikipedia but my research shows that AMD cpus from around 4 years ago all support at least SSE2.

You should expect a good SSE2 implimentation to run around 8-16 times faster than your current code. That is because we eliminate branches in the loop, process 4 pixels (or 12 channels) at once and improve cache performance by using streaming instructions. As an alternative to SSE, you could probably make your existing code run much faster by eliminating the if checks you are using for saturation. Beyond that I would need to run a profiler on your workload.

Of course, the best solution is to use hardware support (i.e code your problem up in DirectX) and have it done on the video card.

Answer 7

I am assuming that you want to do this in a completely portable way, without the help of a GPU, the use of a proprietry intel SIMD library (which may not work as efficiently on AMD processors).

Put the following inplace of your calculation for RGB

R = TopR + (SourceR * alpha) >> 8;
G = TopG + (SourceG * alpha) >> 8;
B = TopB + (SourceB * alpha) >> 8;

It is a more efficient calculation.

Also use shift left instruction on your get pixel macro instead of multiplying by the BPP.

Answer 8

Here's some pointers.

Consider using pre-multiplied foreground images as described by Porter and Duff. As well as potentially being faster, you avoid a lot of potential colour-fringing effects.

The compositing equation changes from

r =  kA + (1-k)B

... to ...

r =  A + (1-k)B

Alternatively, you can rework the standard equation to remove one multiply.

r =  kA + (1-k)B
==  kA + B - kB
== k(A-B) + B

I may be wrong, but I think you shouldn't need the clamping either...

Answer 9

No exactly answering the question but...

One thing is to do it fast, the other thing is to do it right. Alpha compositing is a dangerous beast, it looks straight forward and intuitive but common errors have been widespread for decades without anybody noticing it (almost)!

The most famous and common mistake is about NOT using premultiplied alpha. I highly recommend this: Alpha Blending for Leaves

Answer 10

The main problem will be the poor loop construct, possibly made worse by a compiler failing to eliminate CSE's. Move the real common bits outside the loops. int red isn't common, thouigh - that should be inside the inner loop.

Furthermore, red, green and blue are independent. If you calculate them in turn, you don't need to keep interim red results in registers when you are calculating green results. This is especially important on CPUs with limited registers like x86.

There will be only a limited number of values allowed for bytepp. Make it a template parameter, and then call the right instantiation from a switch. This will produce multiple copies of your function, but each can be optimized a lot better.

As noted, clamping is not needed. In alphablending, you're creating a linear combination of two images a[x][y] and b[x][y]. Since 0<=alpha<=255, you know that each output is bound by max(255*a[x][y], 255*b[x][y]). And since your output range is the same as both input ranges (0-255), this is OK.

With a small loss of precision, you could calculate (a[x][y]*alpha * b[x][y]*(256-alpha))>>8. Bitshifts are often faster than division.

Answer 11

You can always calculate the alpha of red and blue at the same time. You can also use this trick with the SIMD implementation mentioned before.

int colora = 0xFFFFFF; // a color
int colorb = 0xFF007F; // other color
int rb = (colora & 0xFF00FF) + (alpha * (colorb & 0xFF00FF));
int g = (colora & 0x00FF00) + (alpha * (colorb & 0x00FF00));
return (rb & 0xFF00FF) + (g & 0x00FF00);

Answer 12

First of all lets use the proper formula for each color component

You start with this:

v = ( 1-t ) * v0 + t * v1

where t=interpolation parameter [0..1] v0=source color value v1=transfer color value v=output value

Reshuffling the terms, we can reduce the number of operations:

v = v0 + t * (v1 - v0)

You would need to perform this calculation once per color channel (3 times for RGB).

For 8-bit unsigned color components, you need to use correct fixed point math:

i = i0 + t * ( ( v1 - v0 ) + 127 ) / 255

where t = interpolation paramter [0..255] i0= source color value [0..255] i1= transfer color value [0..255] i = output color

If you leave out the +127 then your colors will be biased towards the darker end. Very often, people use /256 or >> 8 for speed. This is not correct! If you divide by 256, you will never be able to reach pure white (255,255,255) because 255/256 is slightly less than one.

I hope this helps.