2

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?

  • How about: A "sprite sheet" is always an xy bitmap comprised of nm identically sized subimages. Set n1=x, m1=y, then identify the background colour, then decrement n1 until you find some value which results in a number of chunks with no non-background pixels on the separating line. Repeat for m1. Worst case is still O(xy), but average case I'd expect to be O(nm). Not an answer because this is off the top of my head and untested. – Phoshi Feb 26 '14 at 10:53
  • Just a minor note (I created ASU). ASU first splits the sprite sheet into several smaller sheets and then unpacks each smaller sheet first, before combining them at the end (I've updated the blog post). This does provide a performance boost but obviously still pretty slow, I'd be interested to see what better approaches there are. – ForkandBeard Jun 2 '14 at 11:47
  • @ForkandBeard thanks for the update! I've added my own solution as an answer below. Why not do the same so I can give you the upvote you deserve? – IAE Jun 2 '14 at 14:00
  • Just out of curiosity, as I think this is pretty cool. You said that it takes too long on large sprite sheets but how often would this need to run? I would guess that it would be a one shot deal and then the sprite coordinates are stored afterwards by an app that needed to use the sprite sheet. Also, one of the key parts of a decent sprite sheet is having the "main body" be centered so different images aren't offset from the character location. It seems like this algorithm wouldn't handle this very well. Does it? – Dunk Jun 2 '14 at 14:57
  • @Dunk yes for my purposes the speed was fine. I was happy with anything under a minute because as you say this is a one time deal. Regards the offsets, no it doesn't handle it, but I have another app to actually manage the offsets and animation data. My goal was just to get 20+ images out of a sprite sheet without spending hours using MSPaint. Would be interesting to see a really quick solution though. – ForkandBeard Jun 2 '14 at 18:29
3

After a little browsing, I created my own solution a few months back but failed to post it here in the interest of anybody that would like to do the same. Therefore, I will quickly describe the method before showing the code. It's in kotlin, but if you're familiar with Java and/or AS3 you should be able to understand the syntax.

The Method

  1. Scan the entire image and store each color in a table.
  2. Determine which color shows up most often- this is the background color
  3. Start at the top left and scan each line.
  4. If a pixel does not match the background color, then it is a sprite.
  5. Use a backtracking algorithm to "fill out" the entire sprite.
  6. Create a rectangle out of this plot.
  7. Store it and cut the sprite out of the image.
  8. Repeat 4-7 until finished.

The Code

The source is available on github, and here is the code w/o documentation or imports.

 fun unpack(spriteSheet: Path): List<Image> {
    Preconditions.checkArgument(Files.exists(spriteSheet),
                                "The file ${spriteSheet.getFileName()} does not exist")

    logger.debug("Loading sprite sheet.")
    // TODO: Convert to png so we have an alpha layer to work with
    val spriteSheetImage = readImage(spriteSheet).toBufferedImage()

    logger.debug("Determining most probable background color.")
    val backgroundColor  = determineProbableBackgroundColor(spriteSheetImage)
    logger.debug("The most probable background color is $backgroundColor")

    return findSprites(spriteSheetImage, backgroundColor) map(::copySubImage.bindFirst(spriteSheetImage))
}

private fun findSprites(image: BufferedImage,
                        backgroundColor: Color): List<Rectangle> {
    val workingImage = copy(image)

    val spriteRectangles = ArrayList<Rectangle>()
    for (pixel in workingImage) {
        val (point, color) = pixel

        if (color != backgroundColor) {
            logger.debug("Found a sprite starting at (${point.x}, ${point.y})")
            val spritePlot = findContiguous(workingImage, point) { it != backgroundColor }
            val spriteRectangle = Rectangle(spritePlot, image)

            logger.debug("The identified sprite has an area of ${spriteRectangle.width}x${spriteRectangle.height}")

            spriteRectangles.add(spriteRectangle)
            eraseSprite(workingImage, backgroundColor, spritePlot)
        }
    }

    logger.info("Found ${spriteRectangles.size()} sprites.")
    return spriteRectangles
}

private fun findContiguous(image: BufferedImage, point: Point, predicate: (Color) -> Boolean): List<Point> {
    val unvisited = LinkedList<Point>()
    val visited   = HashSet<Point>()

    unvisited.addAll(neighbors(point, image) filter { predicate(Color(image.getRGB(it.x, it.y))) })

    while (unvisited.isNotEmpty()) {
        val currentPoint = unvisited.pop()
        val currentColor = Color(image.getRGB(currentPoint.x, currentPoint.y))

        if (predicate(currentColor)) {
            unvisited.addAll(neighbors(currentPoint, image) filter {
                !visited.contains(it) && !unvisited.contains(it) &&
                predicate(Color(image.getRGB(it.x, it.y)))
            })

            visited.add(currentPoint)
        }
    }

    return visited.toList()
}

private fun neighbors(point: Point, image: Image): List<Point> {
    val points = ArrayList<Point>()

    if (point.x > 0)
        points.add(Point(point.x - 1, point.y))
     if (point.x < image.getWidth(null) - 1)
     points.add(Point(point.x + 1, point.y))

     if (point.y > 0)
     points.add(Point(point.x, point.y - 1))
     if (point.y < image.getHeight(null) - 1)
     points.add(Point(point.x, point.y + 1))

     return points
 }

However, the code is not yet complete- packing and creating the metafile is missing- and has been languishing in my Github since March, but I'll hopefully complete it one day.

| improve this answer | |
1

I implemented a very decent and fast sprite detection algorithm but different to above and... superior in speed and accuracy (10 seconds on I7 vs ~ instant on a bitmap 2048 * 2048).

because of the way the standard VB rectangle structure worked I had to roll my own. reason being for theirs Right = Left + Width. I needed it so Left could be equal to Right. In my case for a single pixel at (0, 0) { Left = 0, Right = 0, Top = 0, Bottom = 0, Width = 1, Height = 1 }. However for the standard one this would have deemed the rectangle as "empty".

Firstly if extracting off a JPG then the background has a bit of noise so need to use a color tolerance algorithm when determining if a pixel is background or other.

This algorithm assume sprites are randomly over the sheet and have background around them such that a rectangle can enclose single sprites without overlapping other sprites. It however WON'T work for example if the sheet has sprites that are 32*32 and are packed 32*32 with no gaps.

1) Let user click on a pixel that is deemed the background (In testing I just assumed pixel at (0, 0) was the background). Tightly packed sprite sheets can have less background pixels than other colors and again JPG noise will skew if looking for most frequent color as advised above.

2) Once a background color is decided and a tolerance chosen (say 32) take a clone of the sprite sheet and iterate over every pixel ONCE. Set the pixel values to 0 if they meet the background color tolerance otherwise ... 1. Now you end up with a clone with 0's and 1's which will be a LOT easier (and faster) to deal with below.

3) Now iterate over each pixel in the modified clone once. Top to bottom, left to right, order not really important now.

4) When you hit a non-background pixel (ie 1) use a flood-fill algorithm to erase the pixels to 0. I used a custom one that was very fast and offered me exact control. The custom flood-fill also (importantly) allowed me to return the bounding rectangle of the fill operation.

5) The bounding rectangle of every flood-fill is added to a list of rectangles.

6) At the end of scanning every pixel you should have a list of rectangles. On a test .PNG file with 63 sprites the original algorithm had > 10,000 rectangles that then needed to be merged. The flood-fill one had... "drum roll" 88.

7) The list of rectangles will be close but may have "orphans". Iterate through all like a sort algorithm so you compare each element to all the others. If they intersect merge them (union) so 2 rectangles becomes 1. (to merge I take the bottom rectangle on the list and put it in place of the 2nd one I compared. The first one is modified and the list count is decremented by 1. Now... if they are touching they are again merged ONLY if they meet the maximum area condition.

1) The color tolerance 2) The rectangle merge maximum size. When 2 rectangles are intersecting they're always merged (union) however when 2 rectangles are next to each other with no pixel gap then they are only merged if their internal area is < some cutoff. This way small orphans get joined to a larger rectangles but larger rectangles don't get merged. 3) Flood fill, has an option. When it iterates looking for the next pixel it looks up, right, down, left. However if desired it can also look on the diagonals as well.

NOTE ... To check if 2 rectangles are next to each other use the code below with expand=1.

Public Function IntersectsWith(rectb As strRect, expand As Integer) As Boolean
    If isEmpty Or rectb.isEmpty Then Return False

    If Not (m_top - expand <= rectb.m_bottom + expand) Then Return False

    If Not (m_bottom + expand >= rectb.m_top - expand) Then Return False

    If Not (m_left - expand <= rectb.m_right + expand) Then Return False

    If Not (m_right + expand >= rectb.m_left - expand) Then Return False

    Return True
End Function 

Bit of code that sets the clone pixels to either 1 or 0 :-

    m_bmp = DirectCast(p_bmp.Clone(), Bitmap)

    Dim lock As BitmapData = BMPLock(m_bmp)

    Dim dword_bgcolor As Integer = bgcolor.ToArgb

    ' first smash the copied bitmap into either BG or non bg so can search exact

    For i As Integer = 0 To lock.Width * lock.Height - 1
        If BMPColorsAreSimilar(BMPGetPixelFastDWORD(lock, i), dword_bgcolor, tol) > 0 Then  ' bg
            BMPSetPixelFast(lock, i, 0)
        Else
            BMPSetPixelFast(lock, i, 1)
        End If
    Next

Main loop that finds pixels to flood fill :-

    Dim rect As strRect
    Dim temp_stack As New Stack ' fill algo uses this... passing it means not allocated every call

    For y As Integer = 0 To lock.Height - 1
        For x As Integer = 0 To lock.Width - 1
            If BMPGetPixelFastDWORD(lock, x, y) = 1 Then ' hit a sprite so erase it with flood fill to get the bounds
                BMPFloodFill(lock, temp_stack, filldiag, x, y, 0)
                rect.SetBounds(BMPFloodFillLastMinX(), BMPFloodFillLastMaxX(), BMPFloodFillLastMinY, BMPFloodFillLastMaxY)
                m_bounds.Add(rect) ' add to our list of rectangles
            End If
        Next
    Next

Hope this helps anyone. Very fun little algorithm.

My code for the flood fill is below... It's in managed C++ and called via VB.NET. It uses a stack of coordinates to backtrack when looking for new paths of pixels rather than being recursive. No idea if other people make flood fills like this... but it's fast and accurate and unlike the boxed in ones works on a 32 bit locked surface and offers full control.

int fill_dx[] = { 0, -1, 0, 1, -1, -1, 1, 1 };
int fill_dy[] = { -1, 0, 1, 0, -1, 1, -1, 1 };

int fill_minx;
int fill_miny;
int fill_maxx;
int fill_maxy;

BYTE *fill_track = 0;
DWORD fill_track_size = 0;

Int32  MCUMakerSupport::MCUBitmap::BMPFloodFill(BitmapData ^%bmp_lock,  Stack ^%mCods, Int32 diag, Int32 x, Int32 y, Int32 col)
{
    diag = diag ? 8 : 4;

    if (!bmp_lock)
    {
        return 0;
    }

    int w = bmp_lock->Width;
    int h = bmp_lock->Height;

    if (x < 0 || x >= w || y < 0 || y >= h) return 0;

refill:

    if (!fill_track)
    {
        fill_track = (BYTE *)malloc(w * h);
        fill_track_size = w * h;
    }
    else
    {
        if (fill_track_size < w * h)
        {
            free(fill_track);
            fill_track = 0;
            fill_track_size = 0;
            goto refill;
        }

    }

    if (!fill_track)
    {
        fill_track_size = 0;
        return 0;
    }

    memset(fill_track, 0, w * h);

    //BitmapData ^bmp_lock = bmp->LockBits(Rectangle(0, 0, w, h), ImageLockMode::ReadWrite, bmp->PixelFormat);


    DWORD *fill_addr = (DWORD *)bmp_lock->Scan0.ToPointer();

    DWORD fill_color = col;
    DWORD target_color = fill_addr[y * w + x];

    //Stack ^mCods = gcnew Stack();

    Point pt;

    pt.X = x;
    pt.Y = y;

    mCods->Clear();

    int filled = 1;

    fill_minx = fill_maxx = x;
    fill_miny = fill_maxy = y;

    fill_addr[pt.Y * w + pt.X] = fill_color;
    fill_track[pt.Y * w + pt.X] = 255;
    mCods->Push(pt);

    while (mCods->Count > 0)
    {
    recheck:

        for (int i = 0; i < diag; i++)
        {
            int cx = pt.X + fill_dx[i];

            if (cx < 0 || cx >= w) continue;

            int cy = pt.Y + fill_dy[i];

            if (cy < 0 || cy >= h) continue;

            bool res = false;

            if (!fill_track[cy * w + cx])
            {
                fill_track[cy * w + cx]++;

                DWORD c = fill_addr[cy * w + cx];

                if (c == target_color)
                {
                    res = true;
                    fill_addr[cx + cy * w] = fill_color;

                    if (cx < fill_minx) { fill_minx = cx; }
                    if (cy < fill_miny) { fill_miny = cy; }

                    if (cx > fill_maxx) { fill_maxx = cx; }
                    if (cy > fill_maxy) { fill_maxy = cy; }
                }
            }

            if (res) // fill?
            {
                mCods->Push(pt);
                filled++;
                pt.Y = cy;
                pt.X = cx;
                goto recheck;
            }
        }

        pt.X = ((Point ^)mCods->Peek())->X;
        pt.Y = ((Point ^)mCods->Peek())->Y;
        mCods->Pop();
    }

    mCods->Clear();

    return filled;    // number of pixels filled
}
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.