Efficiently XOR two images in Flash compile target

Question

I need to XOR two BitmapData objects together.

I'm writing in Haxe, using the flash.* libraries and the AS3 compile target.

I've investigated HxSL and PixelBender, and neither one seems to have a bitwise XOR operator, nor do they have any other bitwise operators that could be used to create XOR (but am I missing something obvious? I'd accept any answer which gives a way to do a bitwise XOR using only the integer/float operators and functions available in HxSL or PixelBlender).

None of the predefined filters or shaders in Flash that I can find seem to be able to do a XOR of two images (but again, am I missing something obvious? Can XOR be done with a combination of other filters).

I can find nothing like a XOR drawmode for drawing things onto other things (but that doesn't mean it doesn't exist! That would work too, if it exists!)

The only way I can find at the moment is a pixel-by-pixel loop over the image, but this takes a couple of seconds per image even on a fast machine, as opposed to filters, which I use for my other image processing operations, which are about a hundred times faster.

Is there any faster method?

Answer 1

Edit:

Playing around with this a bit more I found that removing the conditional and extra Vector access in the loop speeds it up by about 100ms on my machine.

Here's the previous XOR loop:

// Original Vector XOR code:
for (var i: int = 0; i < len; i++) {
    // XOR.
    result[i] = vec1[i] ^ vec2[i];

    if (ignoreAlpha) {
        // Force alpha of FF so we can see the result.
        result[i] |= 0xFF000000;
    }
}

Here is the updated XOR loop for the Vector solution:

if (ignoreAlpha) {
    // Force alpha of FF so we can see the result.
    alphaMask = 0xFF000000;
}

// Fewer Vector accessors makes it quicker:
for (var i: int = 0; i < len; i++) {
    // XOR.
    result[i] = alphaMask | (vec1[i] ^ vec2[i]);
}

---

Answer:

Here are the solutions that I've tested to XOR two images in Flash.

I found that the PixelBender solution is about 6-10 slower than doing it in straight ActionScript.

I don't know if it's because I have a slow algorithm or it's just the limits of trying to fake bitwise operations in PixelBender.

Results:

• PixelBender: ~6500ms
• BitmapData.getVector(): ~480-500ms
• BitmapData.getPixel32(): ~1200ms
• BitmapData.getPixels(): ~1200ms

The clear winner is use BitmapData.getVector() and then XOR the two streams of pixel data.

---

1. PixelBender solution

This is how I implemented the bitwise XOR in PixelBender, based on the formula given on Wikipedia: http://en.wikipedia.org/wiki/Bitwise_operation#Mathematical_equivalents

Here is a Gist of the final PBK: https://gist.github.com/Coridyn/67a0ff75afaa0163f673

On my machine running an XOR on two 3200x1400 images this takes about 6500-6700ms.

I first converted the formula to JavaScript to check that it was correct:

// Do it for each RGBA channel.
// Each channel is assumed to be 8bits.
function XOR(x, y){
    var result = 0;
    var bitCount = 8;   // log2(x) + 1
    for (var n = 0; n < bitCount; n++) {
        var pow2 = pow(2, n);

        var x1 = mod(floor(x / pow2), 2);
        var y1 = mod(floor(y / pow2), 2);

        var z1 = mod(x1 + y1, 2);
        result += pow2 * z1;
    }

    console.log('XOR(%s, %s) = %s', x, y, result);
    console.log('%s ^ %s = %s', x, y, (x ^ y));

    return result;
}

// Split out these functions so it's
// easier to convert to PixelBender.
function mod(x, y){
    return x % y;
}

function pow(x, y){
    return Math.pow(x, y);
}

function floor(x){
    return Math.floor(x);
}

Confirm that it's correct:

// Test the manual XOR is correct.
XOR(255, 85);   // 170
XOR(170, 85);   // 255
XOR(170, 170);  // 0

Then I converted the JavaScript to PixelBender by unrolling the loop using a series of macros:

// Bitwise algorithm was adapted from the "mathematical equivalents" formula on Wikipedia:
// http://en.wikipedia.org/wiki/Bitwise_operation#Mathematical_equivalents

// Macro for 2^n (it needs to be done a lot).
#define POW2(n) pow(2.0, n)

// Slight optimisation for the zeroth case - 2^0 = 1 is redundant so remove it.
#define XOR_i_0(x, y) ( mod( mod(floor(x), 2.0) + mod(floor(y), 2.0), 2.0 ) )
// Calculations for a given "iteration".
#define XOR_i(x, y, i) ( POW2(i) * ( mod( mod(floor(x / POW2(i)), 2.0) + mod(floor(y / POW2(i)), 2.0), 2.0 ) ) )

// Flash doesn't support loops.
// Unroll the loop by defining macros that call the next macro in the sequence.
// Adapted from: http://www.simppa.fi/blog/category/pixelbender/
// http://www.simppa.fi/source/LoopMacros2.pbk
#define XOR_0(x, y) XOR_i_0(x, y)
#define XOR_1(x, y) XOR_i(x, y, 1.0) + XOR_0(x, y)
#define XOR_2(x, y) XOR_i(x, y, 2.0) + XOR_1(x, y)
#define XOR_3(x, y) XOR_i(x, y, 3.0) + XOR_2(x, y)
#define XOR_4(x, y) XOR_i(x, y, 4.0) + XOR_3(x, y)
#define XOR_5(x, y) XOR_i(x, y, 5.0) + XOR_4(x, y)
#define XOR_6(x, y) XOR_i(x, y, 6.0) + XOR_5(x, y)
#define XOR_7(x, y) XOR_i(x, y, 7.0) + XOR_6(x, y)

// Entry point for XOR function.
// This will calculate the XOR the current pixels.
#define XOR(x, y) XOR_7(x, y)

// PixelBender uses floats from 0.0 to 1.0 to represent 0 to 255
// but the bitwise operations above work on ints.
// These macros convert between float and int values.
#define FLOAT_TO_INT(x) float(x) * 255.0
#define INT_TO_FLOAT(x) float(x) / 255.0

XOR for each channel of the current pixel in the evaluatePixel function:

void evaluatePixel()
{
    // Acquire the pixel values from both images at the current location.
    float4 frontPixel = sampleNearest(inputImage, outCoord());
    float4 backPixel = sampleNearest(diffImage, outCoord());

    // Set up the output variable - RGBA.
    pixel4 result = pixel4(0.0, 0.0, 0.0, 1.0);

    // XOR each channel.
    result.r = INT_TO_FLOAT ( XOR(FLOAT_TO_INT(frontPixel.r), FLOAT_TO_INT(backPixel.r)) );
    result.g = INT_TO_FLOAT ( XOR(FLOAT_TO_INT(frontPixel.g), FLOAT_TO_INT(backPixel.g)) );
    result.b = INT_TO_FLOAT ( XOR(FLOAT_TO_INT(frontPixel.b), FLOAT_TO_INT(backPixel.b)) );

    // Return the result for this pixel.
    dst = result;
}

---

ActionScript Solutions

2. BitmapData.getVector()

I found the fastest solution is to extract a Vector of pixels from the two images and perform the XOR in ActionScript.

For the same two 3200x1400 this takes about 480-500ms.

package diff
{
    import flash.display.Bitmap;
    import flash.display.DisplayObject;
    import flash.display.IBitmapDrawable;
    import flash.display.BitmapData;
    import flash.geom.Rectangle;
    import flash.utils.ByteArray;


    /**
     * @author Coridyn
     */
    public class BitDiff
    {

        /**
         * Perform a binary diff between two images.
         * 
         * Return the result as a Vector of uints (as used by BitmapData).
         * 
         * @param   image1
         * @param   image2
         * @param   ignoreAlpha
         * @return
         */
        public static function diffImages(image1: DisplayObject,
                                          image2: DisplayObject,
                                          ignoreAlpha: Boolean = true): Vector.<uint> {

            // For simplicity get the smallest common width and height of the two images
            // to perform the XOR.
            var w: Number = Math.min(image1.width, image2.width);
            var h: Number = Math.min(image1.height, image2.height);
            var rect: Rectangle = new Rectangle(0, 0, w, h);

            var vec1: Vector.<uint> = BitDiff.getVector(image1, rect);
            var vec2: Vector.<uint> = BitDiff.getVector(image2, rect);

            var resultVec: Vector.<uint> = BitDiff.diffVectors(vec1, vec2, ignoreAlpha);
            return resultVec;
        }


        /**
         * Extract a portion of an image as a Vector of uints.
         * 
         * @param   drawable
         * @param   rect
         * @return
         */
        public static function getVector(drawable: DisplayObject, rect: Rectangle): Vector.<uint> {
            var data: BitmapData = BitDiff.getBitmapData(drawable);
            var vec: Vector.<uint> = data.getVector(rect);
            data.dispose();
            return vec;
        }


        /**
         * Perform a binary diff between two streams of pixel data.
         * 
         * If `ignoreAlpha` is false then will not normalise the 
         * alpha to make sure the pixels are opaque.
         * 
         * @param   vec1
         * @param   vec2
         * @param   ignoreAlpha
         * @return
         */
        public static function diffVectors(vec1: Vector.<uint>,
                                           vec2: Vector.<uint>,
                                           ignoreAlpha: Boolean): Vector.<uint> {

            var larger: Vector.<uint> = vec1;
            if (vec1.length < vec2.length) {
                larger = vec2;
            }

            var len: Number = Math.min(vec1.length, vec2.length),
                result: Vector.<uint> = new Vector.<uint>(len, true);

            var alphaMask = 0;
            if (ignoreAlpha) {
                // Force alpha of FF so we can see the result.
                alphaMask = 0xFF000000;
            }

            // Assume same length.
            for (var i: int = 0; i < len; i++) {
                // XOR.
                result[i] = alphaMask | (vec1[i] ^ vec2[i]);
            }

            if (vec1.length != vec2.length) {
                // Splice the remaining items.
                result = result.concat(larger.slice(len));
            }

            return result;
        }

    }

}

3. BitmapData.getPixel32()

Your current approach of looping over the BitmapData with BitmapData.getPixel32() gave a similar speed of about 1200ms:

for (var y: int = 0; y < h; y++) {
    for (var x: int = 0; x < w; x++) {
        sourcePixel = bd1.getPixel32(x, y);
        resultPixel = sourcePixel ^ bd2.getPixel(x, y);
        result.setPixel32(x, y, resultPixel);
    }
}

4. BitmapData.getPixels()

My final test was to try iterating over two ByteArrays of pixel data (very similar to the Vector solution above). This implementation also took about 1200ms:

/**
 * Extract a portion of an image as a Vector of uints.
 * 
 * @param   drawable
 * @param   rect
 * @return
 */
public static function getByteArray(drawable: DisplayObject, rect: Rectangle): ByteArray {
    var data: BitmapData = BitDiff.getBitmapData(drawable);
    var pixels: ByteArray = data.getPixels(rect);
    data.dispose();
    return pixels;
}


/**
 * Perform a binary diff between two streams of pixel data.
 * 
 * If `ignoreAlpha` is false then will not normalise the 
 * alpha to make sure the pixels are opaque.
 * 
 * @param   ba1
 * @param   ba2
 * @param   ignoreAlpha
 * @return
 */
public static function diffByteArrays(ba1: ByteArray,
                                      ba2: ByteArray,
                                      ignoreAlpha: Boolean): ByteArray {

    // Reset position to start of array.
    ba1.position = 0;
    ba2.position = 0;

    var larger: ByteArray = ba1;
    if (ba1.bytesAvailable < ba2.bytesAvailable) {
        larger = ba2;
    }

    var len: Number = Math.min(ba1.length / 4, ba2.length / 4),
        result: ByteArray = new ByteArray();

    // Assume same length.
    var resultPixel:uint;
    for (var i: uint = 0; i < len; i++) {
        // XOR.
        resultPixel = ba1.readUnsignedInt() ^ ba2.readUnsignedInt();
        if (ignoreAlpha) {
            // Force alpha of FF so we can see the result.
            resultPixel |= 0xFF000000;
        }

        result.writeUnsignedInt(resultPixel);
    }

    // Seek back to the start.
    result.position = 0;
    return result;
}

Answer 2

There are a few possible options depending on what you want to achieve (e.g. is the XOR per channel or is it just any pixel that is non-black?).

1. There is the BitmapData.compare() method which can give you a lot of information about the two bitmaps. You could BitmapData.threshold() the input data before comparing.

2. Another option would be to use the draw method with the BlendMode.DIFFERENCE blend mode to draw your two images into the same BitmapData instance. That will show you the difference between the two images (equivalent to the Difference blending mode in Photoshop).

3. If you need to check if any pixel is non-black then you can try running a BitmapData.threshold first and then draw the result with the difference blend mode as above for the two images.

Are you doing this for image processing or something else like per-pixel hit detection?

To start with I'd have a look at BitmapData and see what is available to play with.