next »

[st33d]

So how do I find out quickly if two BitmapData's are identical? I know we have the compare() method, but what I'm looking for is a Boolean result.

The question being - I have two BitmapDatas - are all the pixels identical?

Now I know I can compare every pixel, but I'm wondering if there's some clever use of the existing BitmapData methods that could answer this problem quicker.

Any ideas?

[Zaratustra]

if (bitmap1.compare(bitmap2).getColorBoundsRect(0, 0, false).isEmpty()) // bitmaps are identical

[grapefrukt]

how big are they? i can think of a couple of ways, but it mosty depends on how many pixels you're dealing with.

[st33d]

if (bitmap1.compare(bitmap2).getColorBoundsRect(0, 0, false).isEmpty()) // bitmaps are identical

I just tried this on identical BitmapDatas and it didn't work.

I read the compare() function more thoroughly and found out why:

If the BitmapData objects are equivalent (with the same width, height, and identical pixel values), the method returns the number 0

You can't call getColorBoundsRect() on a Number.

Turns out the compare() function had this capability all along, it does other wierd stuff if the dimensions are off as well.

Sorry about that. At least it answers my question.

[grapefrukt]

well, that was easy

[bateleur]

As a footnote to all this: depending on exactly what your BitmapData objects might contain you can in special cases make this many, many times faster.

What are you actually doing?

[st33d]

It's a Flixel style animation.

Because the frames have been captured from a MovieClip using bitmapData.draw(), there exists the possibility that two frames may be identical. And that means a lot of memory is needlessly taken up storing a number of frames that may be identical.

I'm pretty sure the compare() function is going to be faster than any other trick because the bitmapData methods aren't processing images at the bytecode level.

[BorisTheBrave]

So you are comparing one image to many preexisting ones? That calls for a hash function, which is what bateleur was probably hinting at.

[bateleur]

That was one of the methods I had in mind.

The other is that if there are typically multiple non-local differences you can compare subsets of the image and shortcut the rest of the calculation if you find a difference. So, for example, if you have many animation frames and most of them contain a difference within some particular row of pixels then testing just that row first before testing the rest could make you many times faster (easily x20+) at the expense of a bit of code complexity.

[st33d]

Perhaps people didn't bother to read this bit:

The bitmapdatas are generated by the draw() method. There is no way to tell in advance if frames will be identical.

The method I looked up for a comparison is a method native to bitmapdata - which probably means it will be even faster than scanning the first row.

This is why Flixel exists - the copyPixels method is incredibly fast, as are most other bitmapData functions - far faster than it would be to execute the functions in code yourself.

And what good is scanning the first row going to do if the bottom right pixel is different?

[bateleur]

The bitmapdatas are generated by the draw() method. There is no way to tell in advance if frames will be identical.

That doesn't invalidate hashing as a method. What matters for hashing is how many times each frame is compared. If the answer is "only a few times" then it's probably not worth it (because calculating the hash is slow), but if each frame must be compared to every other frame then it's a big saving.

The method I looked up for a comparison is a method native to bitmapdata ... This is why Flixel exists

Nah, Flixel exists because people like rapid development tools. But I've heard rumours that some fearless programmers have been known to use the Flash BitmapData API directly!

It's a red herring anyway. There's nothing stopping you from using compare() on rows if you find the higher speed makes that much difference.

And what good is scanning the first row going to do if the bottom right pixel is different?

You'll notice I didn't say "first" row.

The answer is, it's statistical. If a test that takes 5% of the time allows you to shortcut the full length test 90% of the time, then that's a win. Obviously if the one row test returns a match you then do the full test, but so long as that's rare it doesn't matter much.

[Zaphos]

It's a red herring anyway. There's nothing stopping you from using compare() on rows if you find the higher speed makes that much difference.

How do you do that?  compare only seems to operate on full BitmapData objects, not on individual rows ...

[st33d]

The frames are only compared once:

Code:

public class BlitClip extends BlitSprite{
	
	public var frames:Array/*BitmapData*/;
	public var total_frames:int;
	
	public function BlitClip(mc:MovieClip = null, colour_transform:ColorTransform = null) {
		super(mc, colour_transform);
		if(mc != null){
			frames = [data];
			for (var i:int = 2; i < mc.totalFrames + 1; i++){
				mc.gotoAndStop(i);
				frames[i-1] = new BitmapData(Math.ceil(bounds.width), Math.ceil(bounds.height), true, 0x00000000);
				frames[i-1].draw(mc, new Matrix(1, 0, 0, 1, -bounds.left, -bounds.top), colour_transform);
			}
			total_frames = mc.totalFrames;
		}
	}
	override public function render(destination:BitmapData, frame:int = 0):void{
		p.x = x + dx;
		p.y = y + dy;
		destination.copyPixels(frames[frame], rect, p, null, null, true);
	}
	/* Reduces the number of BitmapDatas in memory by checking to see if any frames are identical */
	public function compress():void{
		for(var i:int = 0; i < frames.length; i++) {
			for(var j:int = i + 1; j < frames.length; j++) {
				if(frames[i].compare(frames[j]) == 0) frames[i] = frames[j];
			}
		}
	}
	
}

The task at hand was to simply reduce any duplicate BitmapDatas in memory by calling the compress() method after the BlitClip is created.

The compress() method never need be called again afterwards - its work is done.

I still don't see how a partial test can return an accurate result. Without examining the entire BitmapData, you've no way of knowing if there may be pixels astray.

[bateleur]

How do you do that?  compare only seems to operate on full BitmapData objects, not on individual rows.

Correct, but you just copy out the row.

[Sam]

I would assume that the downside of using the BitmapData.compare function is that it will not stop once it has found a single difference because, it assumes you want to know the location of all the differences between the images.

So the question is if the wasted time of checking the rest of the images after a difference has been found is made up for by the speed improvement over 'manually' checking.

Sounds like time for BENCHMARKS!

Basic test program:

Code:

package  
{
	import flash.display.Bitmap;
	import flash.display.BitmapData;
	import flash.display.Sprite;
	import flash.events.Event;
	import flash.events.KeyboardEvent;
	import flash.utils.getTimer;

	public class Test extends Sprite
	{
		private var one:BitmapData, two:BitmapData;
		private const w:int = 1000, h:int = 1000;
		private const numberOfRepeats:int = 1000;
		
		public function Test() 
		{
			if (stage != null)
			{
				init();
			}
			else
			{
				addEventListener(Event.ADDED_TO_STAGE, init);
			}
		}
		
		private function init(e:Event = null):void
		{
			//make a large BitmapData filled with pretty colours.
			one = new BitmapData(w, h, true, 0);
			one.perlinNoise(10, 10, 3, 123, false, false);
			
			//make a second BitmapData, and either..
			//have it be identical:
			two = one.clone();

			//make it very slightly different:
			//two = one.clone();
			//two.setPixel32(w / 2, h / 2, 0);

			//make it very different:
			//two = new BitmapData(w, h, true, 0);
			//two.perlinNoise(50, 50, 3, 456, false, false);


			//..and because a .swf that doesn't display anything is boring:
			addChild(new Bitmap(one));
			
			//press any key to perform the comparison.
			stage.addEventListener(KeyboardEvent.KEY_UP, doCompare);
		}
		
		private function doCompare(e:Event = null):void
		{
			var timeAtStart:int = getTimer();
			var areSame:Boolean;
			for (var repeat:int = 0; repeat < numberOfRepeats; repeat++)
			{
				/*
				 * 
				 * Insert comparison code in here.
				 * 
				 */
			}
			var timeAtEnd:int = getTimer();
			trace("result:", areSame);
			trace("time:", ((timeAtEnd - timeAtStart) / repeat).toPrecision(3));
		}
	}
}

We vary what's in the doCompare function to try out different techniques.

As you can see it's testing two 1000x1000 BitmapData objects filled with Perlin noise.  Test cases will be:
When they are identical
When they are completely different (both filled with different Perlin noise)
When they have a single pixel (right in the middle) different.

Each test is repeated 1000 times and the time given below is the mean execution time for a single test.

BitmapData.compare

Code:

if (one.compare(two) as Number == 0)
{
	areSame = true;
}
else
{
	areSame = false;
}

(I added on the "as Number" for the sake of clarity)

With identical bitmapData objects:
4.03ms

With slightly different:
5.38ms

With totally different:
34.0ms

I suspect the increased time when there are differences (especially when there are large differences) is the time taken to create the new BitmapData object used to report what the differences are.  Which is a shame, because our program isn't using that data.

BitmapData.getPixel32

Code:

areSame = true;
checkSameness:
for (var bx:int = 0; bx < one.width; bx++)
{
	for (var by:int = 0; by < one.height; by++)
	{
		if (one.getPixel32(bx, by) != two.getPixel32(bx, by))
		{
			areSame = false;
			break checkSameness;
		}
	}
}

Using identical:
226ms

Using slightly different:
116ms

Using very different:
0.001ms

I had to limit the number of repeats for the first two conditions so as to avoid timeout errors.  As you'd expect manually checking each of a million pixels does indeed take a while.  Also unsurprising is that if you can end the check after just one pixel it gets very fast.


Custom Shader

The PixelBender shader

Code:

<languageVersion : 1.0;>

kernel TestDifference
<   namespace : "";
    vendor : "";
    version : 1;
    description : "Compares two images. If the pixels matche, the result is coloured black and if they differ it is coloured white.";
>
{
    input image4 one;
    input image4 two;
    output pixel4 dst;

    void
    evaluatePixel()
    {
        float2 here = outCoord();
        float4 fromOne = sampleNearest(one, here);
        float4 fromTwo = sampleNearest(two, here);

        //(fromOne == fromTwo) works in PixelBender, but not when compiled
        // and run through Flash. So I have to check each channel instead.
        if (fromOne.r == fromTwo.r && fromOne.g == fromTwo.g && fromOne.b == fromOne.b && fromOne.a == fromTwo.a)
        {
            dst = pixel4(0.0,0.0,0.0,0.0);
        }
        else
        {
            dst = pixel4(1.0,1.0,1.0,1.0);
        }
    }
}

The comparison function:

Code:

var testDifference:Shader = new Shader(new MyEmbeddedShader() as ByteArray);
testDifference.data.one.input = one;
testDifference.data.two.input = two;
var result:Vector.<Number> = new Vector.<Number>();
var differenceJob:ShaderJob = new ShaderJob(testDifference, result, one.width, one.height);
differenceJob.start(true);

if (result.indexOf(1, 0) == -1)
{
	areSame = true;
}
else
{
	areSame = false;
}

Shaders are designed to operate on images.  Here I am pushing the result of the shader into a vector instead. My hope is that the necessary search is faster on a Vector than on a BitmapData, mainly as Vector.IndexOf() can stop its search as soon as it finds a matching instance.

Using identical:
55.2ms

Using slightly different:
39.5ms

Using very different:
21.5ms

I had to again use fewer repeats for these tests to avoid running out of memory.  Would have thought the garbage collector could collect some garbage between iterations, but I've never really studied Flash's garbage collection.  The extra time taken in the cases of similar images must be due to the extra time the IndexOf() function takes to find evidence of difference.  I tried repeating the test using LastIndexOf() and found just the same results.

Shader with analysis through BitmapData

Same shader as above, but new comparison function:

Code:

var testDifference:Shader = new Shader(new MyEmbeddedShader() as ByteArray);
testDifference.data.one.input = one;
testDifference.data.two.input = two;

var resultBmd:BitmapData = new BitmapData(one.width, one.height, true, 0);
var differenceJob:ShaderJob = new ShaderJob(testDifference, resultBmd);
differenceJob.start(true);

if (resultBmd.getColorBoundsRect(0xffffffff, 0xffffffff, true).isEmpty())
{
	areSame = true;
}
else
{
	areSame = false;
}

Just as above, the shader checks if each pixel is the same.  When it finds a difference, it sets the corresponding pixel on resultBmd to be white.  getColorBoundsRect is then used to find if there are any white pixels in resultBmd.

Using identical:
14.8ms

Using slightly different:
13.4ms

Using very different:
11.9ms

As these times are less than even the fastest example of using a Vector to hold output from the shader it seems that forcing a shader to fill a Vector instead of a BitmapData slows it down.  The wide variation in times for searching through the Vector shown in the previous test shows that the IndexOf() function is pretty slow, at least compared to BitmapData.getColourBoundsRect.

getColourBoundsRect is VERY fast it seems - skipping it only increases the execution time by around 1ms.

Summary
Yeah, BitmapData.compare() is pretty good.  It showed a dramatic slowdown when given completely different images but I am fairly sure that was due to the time taken to generate a new huge BitmapData object.  It would be nice for BitmapData.compare() to take a parameter that told it not to bother making the BitmapData showing where the differences lie, and instead just return its number codes.

Choosing which areas of the image to compare first is nice smart thinking, but given that BitmapData.compare() can examine a million pixels in a handful of milliseconds it is unlikely to be a necessary optimisation (see also: root of all evil).  Especially as I assume this process would only be performed once when the animations are first loaded, or at least wouldn't need to be repeated each frame.

It was interesting trying to do some of the work on a shader, but they're really just not designed for this kind of task.  Like BitmapData.compare() the shader has to produce a new image full of information which isn't actually required by the task at hand.  Custom shaders in Flash are also still freaky - the times above would likely at least double when running on a Mac for instance.

So there you go, a comprehensive answer to a question no-one asked! 

I still don't see how a partial test can return an accurate result. Without examining the entire BitmapData, you've no way of knowing if there may be pixels astray.

I don't think he's suggesting that.  Rather, you would start your search at areas which you happen to know are likely to be different.  If they are different then you can stop checking.  If they're the same, then you go on to check everywhere else to be sure.

For example, an animation of a rocket ship - start your search for changes at the "engine flame" area which you know is very likely to be different between frames.

Unless you're comparing huge images very often such cleverness is probably just not going to be needed.  It's a good technique that can be reused in other applications though!

[increpare]

Nice analysis, salt : )

[st33d]

 

[grapefrukt]

Okay. I just went completely overboard with this. Lucky for me it's a slow day at work.

I've been meaning to try out grant skinners performance test thing for a while, so this was my opportunity.

I tested the native compare, the iterative compare, a reverse iterative compare (because i know they're a bit faster) and finally a compare using blendmode DIFFERENCE.

The first two are essentially identical to salts.
The reverse iterative compare looks like this:

Code:

for (var bx:int = _base.width - 1; bx >= 0; --bx) {
	for (var by:int = _base.height - 1; by >= 0; --by) {
		if (_base.getPixel32(bx, by) != compareTo.getPixel32(bx, by)) {
			return false;
		}
	}
}
return true;

The blendmode compare looks like this:

Code:

var test:BitmapData = _base.clone();
test.draw(compareTo, null, null, BlendMode.DIFFERENCE);
var rect:Rectangle = test.getColorBoundsRect(0xffffff, 0x000000, false);
return (rect.toString() != _base.rect.toString());

I'm not 100% sure this is completely reliable, but it seemed to work.

I ran each test for 50 iterations on 500x500 images.

Unfortunately my pixel bender toolkit is borked, so I couldn't try that method.

Each test was ran in both the debug and release players for comparison, notice the massive differences!

I also put the whole flashdevelop project here.

[jotapeh]