Dynamic Spot the Difference game

[munkychop]

Hi there,

I have recently been looking into making a 'spot the difference' type game that will automatically detect the difference between two similar images.

It will eventually do the following:

1. compare two images
2. detect and separate the differences (hotspots)
3. create clickable movieclips from the separate objects (differences)


So far I have done the following:

1. loaded two images using XML
2. drawn these images into separate BitmapData objects
3. used the 'compare' method of the BitmapData class to detect opaque pixels that are different between the two images
4. created a third BitmapData object containing the differences.



Now, here is where I am stuck...

How would I separate the third BitmapData object (the differences) into individual objects?

I would like to add click functionality to them individually.

I'm pretty sure I need to simplify the objects to black and white blobs and then separate them somehow... I just don't know how.

I have found algorithms such as marching ants, but i am not sure if this is the right approach for this type of application.

Any help would be greatly appreciated. Thanks in advance

[5TonsOfFlax]

Off the top of my head, I'd say use threshold to turn them into binary (black and white) images. Then in a loop:
* use flood fill on any white pixel, turning it a third color.
* use all pixels that are that third color and make a new sprite from them from the original bitmaps
* turn all pixels that are that third color and turn them black.
When no white pixels exist any more, you've found all blobs.

[munkychop]

Hi 5TonsOfFlax,

Thanks for the reply. I am still having a few issues... maybe you could help?


I have managed to compare two slightly different images and create a bitmapData object of those differences and then use bitmapData.threshold to find transparent pixels and set them to black using a white mask, effectively meaning the blobs I am interested in are white.

now, here's is where I have run into a few problems:

1. The white blobs contain a few transparent pixels within them, so how do I create a true blob and remove these? blur filter??
2. And this is most important; how would I separate these blobs into different sprites, since they are in the same bmd object?

here's what I have so far:

package 
{
    import flash.display.Bitmap;
    import flash.display.BitmapData;
    import flash.display.DisplayObject;
    import flash.display.MovieClip;
    import flash.events.Event;
    import flash.geom.Point;
    import flash.geom.Rectangle;
    
    public class Main extends MovieClip
    {
        private var _img1:Img1;
        private var _img2:Img2;
        private var _bmd1:BitmapData;
        private var _bmd2:BitmapData;
        private var _bitmap1:Bitmap;
        private var _bitmap2:Bitmap;
        
        //-------------------------------------------------------------------------------
        //--constructor
        //-------------------------------------------------------------------------------
        public function Main ()
        {
            this.addEventListener (Event.ADDED_TO_STAGE, init);
        }
        
        //-------------------------------------------------------------------------------
        //--initialization
        //-------------------------------------------------------------------------------
        private function init (event:Event):void
        {
            this.removeEventListener (Event.ADDED_TO_STAGE, init);
            
            _img1 = new Img1 ();
            _img2 = new Img2 ();
            
            _bmd1 = compare (_img1, _img2);
            
            _bitmap1 = new Bitmap (_bmd1);
            addChild (_bitmap1);
            
            _bmd2 = new BitmapData (_bmd1.width,_bmd1.height);
            
            _bmd2.threshold (_bmd1, _bmd1.rect, new Point (), "==", 0x00000000, 0xFF000000, 0xFFFFFFFF);
            
            _bitmap2 = new Bitmap (_bmd2);
            _bitmap2.x = _bitmap1.width;
            addChild (_bitmap2);
        }
        
        //-------------------------------------------------------------------------------
        //--private methods
        //-------------------------------------------------------------------------------
        private function compare (image1:DisplayObject, image2:DisplayObject):BitmapData
        {
            var bitmapData1:BitmapData = new BitmapData (image1.width, image1.height, false);
            bitmapData1.draw (image1);
            
            var bitmapData2:BitmapData = new BitmapData (image2.width, image2.height, false);
            bitmapData2.draw (image2);
            
            var bitmapDataDifference = BitmapData (bitmapData1.compare (bitmapData2));
            
            var rect:Rectangle = bitmapDataDifference.getColorBoundsRect (0xFF000000, 0x00000000, false);
            
            var hotspot:BitmapData = new BitmapData (rect.width,rect.height);
            hotspot.copyPixels (bitmapDataDifference,rect,new Point ());
            
            return hotspot;
        }
    }
}

Thanks again, I really appreciate your help

[munkychop]

OK, so I solved it myself, although thank you for your input 5TonsOfFlax.

The process is this:

1. load two images
2. use the bitmapData.compare method to get the pixel differences from the bitmapData of the loaded images into a seperate bitmapData object
3. use a blur filter on the bitmapData object to smooth possible single pixel lines etc.
4. create a second bitmapData object and use the bitmapData.threshold method to turn transparent pixels black and non-transparent pixels white
5. loop through each pixel in the image, looking for white pixels
6. when the first white pixel is found, use the bitmapData.floodFill method to turn all connected white pixels a third colour (using a uint variable for the colour), effectively creating a blob
7. use the bitmapData.getColourBoundsRect method on that third colour to get a rectangle of the bounding box of that blob
8. create a bitmap from the bitmapData of the image at the position and size of the rectangle
9. add the bitmap to a new movieclip and give it x/y properties based on those of the rectangle
10. push the movieclip to an array
11. increment the colour variable by one and then start the loop again
12. when no more white pixels are found, all the blobs have been detected
13. add interactivity to the blob movieclips by looping through the movieclip array

Here is the code:

package com.engine
{
    import flash.display.Bitmap;
    import flash.display.BitmapData;
    import flash.display.DisplayObject;
    import flash.display.Loader;
    import flash.display.MovieClip;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.filters.BlurFilter;
    import flash.geom.Point;
    import flash.geom.Rectangle;
    import flash.net.URLLoader
    import flash.net.URLRequest;
    
    public class Main extends MovieClip
    {
        private var _imageXML:XML;
        private var _imageGroupList:XMLList;
        private var _imageList:XMLList;
        private var _imageArray:Array;
        private var _urlLoader:URLLoader;
        private var _loader:Loader;
        
        private var _blobColour:uint;

        private var _bitmapData1:BitmapData;
        private var _bitmapData2:BitmapData;
        private var _blurFilter:BlurFilter;
        
        private var _hotspotArray:Array;
        private var _blobFound:Boolean;
        
        private var _minBlobWidth:int;
        private var _minBlobHeight:int;
        private var _imageGroupListIndex:int;
        private var _clicksRemaining:int;
        private var _totalHotspotsFound:int;
        private var _imageLoadedIndex:int;
        
        public function Main ()
        {
            this.addEventListener (Event.ADDED_TO_STAGE, init);
        }
        
        private function init (event:Event):void
        {
            _urlLoader = new URLLoader ();
            _urlLoader.addEventListener (Event.COMPLETE, xmlLoaded);
            _urlLoader.load (new URLRequest ("xml/imageList.xml"));
        }
        
        private function xmlLoaded (event:Event):void
        {
            event.currentTarget.removeEventListener (Event.COMPLETE, xmlLoaded);
            
            _imageGroupListIndex = 0;
            _imageLoadedIndex = 0;
            
            _imageXML = new XML (event.currentTarget.data);
            _imageGroupList = new XMLList (_imageXML.imageGroup);
            
            _minBlobWidth = _imageXML.imageSettings.minBlobWidth;
            _minBlobHeight = _imageXML.imageSettings.minBlobHeight;
            
            _blobColour = 0xFF00FF00;
            _clicksRemaining = 5;
            _totalHotspotsFound = 0;
            
            _blurFilter = new BlurFilter (4.0,4.0);
            
            _imageArray = new Array ();
            _hotspotArray = new Array ();
            _imageList = new XMLList (_imageGroupList[_imageGroupListIndex].image);
            
            _loader = new Loader ();
            
            loadImage ();
        }
        
        private function loadImage ():void
        {
            _loader.contentLoaderInfo.addEventListener (Event.COMPLETE, imageLoaded);
            _loader.load (new URLRequest (_imageList[_imageLoadedIndex].imageURL));
        }
        
        private function imageLoaded (event:Event):void
        {
            event.currentTarget.loader.contentLoaderInfo.removeEventListener (Event.COMPLETE, imageLoaded);
            
            _imageArray.push (event.currentTarget.loader.content);
            _imageLoadedIndex++;
            
            if (_imageArray.length == 2)
            {
                allImagesLoaded ();
                _imageGroupListIndex++;
            }
            else
            {
                loadImage ();
            }
        }
        
        private function allImagesLoaded ():void
        {
            _bitmapData1 = BitmapData (_imageArray[0].bitmapData.compare (_imageArray[1].bitmapData));
            _bitmapData1.applyFilter (_bitmapData1,_bitmapData1.rect,new Point (), _blurFilter);
            
            _bitmapData2 = new BitmapData (_bitmapData1.width,_bitmapData1.height);
            //if a pixel in the source image is less than or equal to black (ie any transparency from the blur filter), set it to black in the destination image and
            //use a white mask, so that any non-transparent pixels will become white in the destination image.
            //-----------------------------------------------------------------------------alpha-------black-----white mask
            _bitmapData2.threshold (_bitmapData1, _bitmapData1.rect, new Point (), "<=", 0xF0000000, 0xFF000000, 0xFFFFFFFF);
            
            for (var i:int = 0; i < _imageArray.length; i++)
            {
                var mc:MovieClip = new MovieClip ();
                mc.addChild (_imageArray[i]);
                mc.x = mc.width * i;
                
                mc.addEventListener (MouseEvent.CLICK, reduceClicksRemaining);
                
                _imageArray[i] = mc;
                
                addChild (_imageArray[i]);
            }
            
            detectBlobs (_bitmapData2, 0xFFFFFF, _blobColour);
        }
        
        private function detectBlobs (src:BitmapData, colourToFind:uint, blobColour:uint):void
        {
            _blobFound = false;
            
            for (var py:int = 0; py < src.height; py++)
            {
                for (var px:int = 0; px < src.width; px++)
                {
                    var pixelValue:uint = src.getPixel (px,py);
                    
                    if (pixelValue == colourToFind)
                    {
                        _blobFound = true;
                        
                        src.floodFill (px,py, blobColour);
                        var rect:Rectangle = src.getColorBoundsRect (0xFFFFFFFF, blobColour);
                        
                        if (rect.width > _minBlobWidth && rect.height > _minBlobHeight)
                        {
                            var bmd:BitmapData = new BitmapData (rect.width,rect.height);
                            
                            bmd.copyPixels (src, rect, new Point ());
                            var bitmap:Bitmap = new Bitmap (bmd);
                            var hotspot:MovieClip = new MovieClip ();
                            
                            hotspot.addChild (bitmap);
                            
                            hotspot.xPos = rect.x;
                            hotspot.yPos = rect.y;
                            _hotspotArray.push (hotspot);
                            
                            blobColour += 1;
                        }
                        
                        detectBlobs (src, colourToFind, blobColour);
                        return;
                    }
                    
                    if (px == src.width - 1 && py == src.height - 1 && !_blobFound)
                    {
                        displayResults ();
                    }
                }
            }
        }
        
        private function displayResults ():void
        {
            if (_hotspotArray.length > 0)
            {
                for (var i:int = 0; i < _hotspotArray.length; i++)
                {
                    var hotspot:MovieClip = _hotspotArray[i] as MovieClip;
                    
                    hotspot.addEventListener (MouseEvent.CLICK, hotspotClicked);
                    hotspot.x = _imageArray[1].x + hotspot.xPos;
                    hotspot.y = _imageArray[1].y + hotspot.yPos;
                    hotspot.alpha = 0;
                    
                    addChild (hotspot);
                }
            }
            
            trace ("differences found : " + String (_totalHotspotsFound) + "/" + _hotspotArray.length);
        }
        
        private function reduceClicksRemaining (event:MouseEvent):void
        {
            _clicksRemaining--;
            
            if (_clicksRemaining == 0)
            {
                gameFailed ();
            }
            
            trace ("clicks remaining: " + String (_clicksRemaining));
        }
        
        private function hotspotClicked (event:MouseEvent):void
        {
            event.currentTarget.removeEventListener (MouseEvent.CLICK, hotspotClicked);
            
            _totalHotspotsFound++;
            
            event.currentTarget.alpha = .4;
            
            if (_totalHotspotsFound == _hotspotArray.length)
            {
                gameWon ();
            }
            
            trace ("differences found : " + String (_totalHotspotsFound) + "/" + _hotspotArray.length);
        }
        
        private function gameWon ():void
        {
            for (var i:int = 0; i < _imageArray.length; i++)
            {
                _imageArray[i].removeEventListener (MouseEvent.CLICK, reduceClicksRemaining);
                removeChild (_imageArray[i]);
            }
            
            for (var j:int = 0; j < _hotspotArray.length; j++)
            {
                _hotspotArray[j].removeEventListener (MouseEvent.CLICK, hotspotClicked);
                removeChild (_hotspotArray[j]);
            }
            
            
            trace ("You did it! game over");
        }
        
        private function gameFailed ():void
        {
            for (var i:int = 0; i < _imageArray.length; i++)
            {
                _imageArray[i].removeEventListener (MouseEvent.CLICK, reduceClicksRemaining);
                removeChild (_imageArray[i]);
            }
            
            for (var j:int = 0; j < _hotspotArray.length; j++)
            {
                _hotspotArray[j].removeEventListener (MouseEvent.CLICK, hotspotClicked);
                removeChild (_hotspotArray[j]);
            }
            
            trace ("You suck dude!");
        }
    }
}

And here is the XML:

<?xml version="1.0" encoding="ISO-8859-1"?>

<imageList>

	<imageSettings>
		<minBlobWidth>5</minBlobWidth>
		<minBlobHeight>5</minBlobHeight>
	</imageSettings>
	
	<imageGroup>
		<image>
			<imageURL>images/01.jpg</imageURL>
		</image>

		<image>
			<imageURL>images/02.jpg</imageURL>
		</image>
	</imageGroup>

</imageList>

I hope that helps somebody, someday



.

[5TonsOfFlax]

I'm glad you got it working. The use of getColorBoundsRect is pretty good for most things, but you may want to experiment with more pixel-specific areas. Imagine a thin line feature at 45 degrees. That will result in a very large bounding box for a very small number of actual differing pixels. But that is probably fine for your purposes.

[munkychop]

Thanks, yeah I did consider that, but this is good for what I need currently.

If I wanted more pixel specific control i would add an array of each blob's colour and using getPixel with mouseX && mouseY (on a click), I would check if the pixel colour matches any of the colours in the array. If it does; run a blobClicked method and if not do nothing.

Do you reckon that is a good way to do something like that? Or are there more efficient ways?

Thanks for the input

[5TonsOfFlax]

Yeah, that seems like a pretty good method. You wouldn't even need the array if you checked against the blob map. Just see whether the color at the click coordinates is not black or transparent or whatever the default was.