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:

I want to detect and extract all individual sprites. I've followed the algorithm detailed in Alferd's Blog Post which goes like:

1. Determine predominant color and dub it the BackgroundColor
2. Iterate over each pixel and check ColorAtXY == BackgroundColor
3. If 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.
4. Repeat this until all sprites are boxed up.
5. Combined overlapping boxes (or within a very short distance)
6. 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?