I'm currently writing a Sprite Sheet Unpacker such as Alferds Spritesheet Unpacker. Now, before this is sent to gamedev, this isn't necessarily about games. I would like to know how to detect a sprite within a spriitesheet, or more abstactly, a shape inside of an image.Given this sprite sheet:http://www.gotoandplay.it/_articles/2006/06/beatemup/pixel_splatter.gifI want to detect and extract all individual sprites. I've followed the algorithm detailed in Alferd's Blog Post which goes like:Determine predominant color and dub it the BackgroundColorIterate over each pixel and check ColorAtXY == BackgroundColorIf false, we've found a sprite. Keep going right until we find a BackgroundColor again, backtrack one, go down and repeat until a BackgroundColor is reached. Create a box from location to ending location.Repeat this until all sprites are boxed up.Combined overlapping boxes (or within a very short distance)The resulting non-overlapping boxes should contain the sprite.This implementation is fine, especially for small sprite sheets. However, I find the performance too poor for larger sprite sheets and I would like to know what algorithms or techniques can be leveraged to increase the finding of sprites.A second implementation I considered, but have not tested yet, is to find the first pixel, then use a backtracking algorithm to find every connected pixel. This should find a contiguous sprite (breaks down if the sprite is something like an explosion where particles are no longer part of the main sprite). The cool thing is that I can immediately remove a detected sprite from the sprite sheet.Any other suggestions?
How to Detect Sprites in a SpriteSheet?
design;algorithms;image