C# - Finding the Boundaries of an Image (not the size)

Question

Hello ! I'm developing an application to split an image grid equally and center the images (based on their similarity). So far, I could manage to fix a grid of images with small sizes, but whenever I try a larger "sprite" size (100x100, for instance), I get Stack Overflow error.

Yes I'm using recursion, but whenever a pixel is checked, I set a boolean to deactivate it, copy it to a list and go on checking the others (in all directions), until the list is filled up with an image from the grid. I'm not sure if this is the best way since for each call, I call the same method 7 times (supposing there are 7 adjacent pixels which weren't checked yet)... until there are no pixels left to check, and I can move on to the next image in the grid.

I tried tracing where the error started happening, it was after checking more or less 1600 pixels and adding them to the List. MyPixel is a class which contains 4 variables: x(int), y(int), color (Color), and checked (bool)

    public void processSprite(int i, int j)
    {
        //OOO
        //OXO
        //OOO
        pixeltemp.Add(new MyPixel(imap.pixels[i, j].x, imap.pixels[i, j].y, imap.pixels[i, j].color));
        imap.pixels[i, j].read = true;
        //OOO
        //OOX
        //OOO
        try
        {
            if (!imap.pixels[i + 1, j].read)
            {
                if (imap.pixels[i + 1, j].color.A == 0) //Found a Border
                {
                    imap.pixels[i + 1, j].read = true;
                }
                else
                {
                    processSprite(i + 1, j);
                }
            }
        }
        //... (code goes on)
    }

• pixeltemp is the temporary list of pixels which holds the image (List<MyPixel>)
• imap contains the entire image (List<MyPixel>)

I guess it's not a memory problem since my app just takes about 16mb tops.

My question is, why do I have this "Stack overflow" error if it's not an infinite recursion? Is there an easier way to do this? I do think my code looks ugly, I just have no idea how to make it better.

Thanks in advance !

Answer 1

Stack overflows aren't caused by infinite recursion but by more recursion (or, rather, call stack) than the process can handle. In your case, each recursive call to processSprite is going to do the same number of recursive calls to processSprite. So in the worst-case scenario of 1600 pixels without finding a boundary, your call tree would look like this:

  processSprite(0, j)
    processSprite(1, j)
      processSprite(2, j)
        ...
          processSprite(1599, j) <-- That's 1600 call frames,
                                     enough for an overflow.

You'll want to reorganize your algorithm into a linear loop that does a depth-first search, perhaps in a spiral pattern if you're wanting to to find a pixel that's closest to the starting point. I'm sure there are already other spiffy algorithms others have already developed to solve this problem.

Edit:

I think I understand better now the problem that you're trying to solve. It sounds like you have an image that may contain multiple image tiles surrounded by 0-alpha pixels and you want to find the bounding rectangles for each of these tiles. That looked like an interesting problem to solve, so I implemented it:

IEnumerable<Rectangle> FindImageTiles(Bitmap compositeImage)
{
    var result = new List<Rectangle>();

    // Scan for a non-empty region that hasn't already been "captured"
    for (var x = 0; x < compositeImage.Width; x++)
    {
        for (var y = 0; y < compositeImage.Height; y++)
        {
            // Only process the pixel if we don't have a rectangle that
            // already contains this and if it's not empty
            if (!result.Any(r => r.Contains(x, y)) 
                && compositeImage.GetPixel(x, y).A != 0)
            {
                // Now that we've found a point, create a rectangle
                // surrounding that point, then expand outward until
                // we have a bounding rectangle that doesn't intersect
                // with the tile
                var rect = new Rectangle(x - 1, y - 1, 2, 2);
                bool foundBounds = false;
                while (!foundBounds)
                {
                    var xRange = Enumerable.Range(rect.Left, rect.Right)
                        .Where(px => px >= 0 && px < compositeImage.Width);
                    var yRange = Enumerable.Range(rect.Top, rect.Bottom)
                        .Where(py => py >= 0 && py < compositeImage.Height);

                    // Adjust the top
                    if (rect.Top >= 0 
                        && xRange
                            .Select(bx => compositeImage.GetPixel(bx, rect.Top))
                            .Any(p => p.A != 0))
                    {
                        rect.Y--;
                        rect.Height++;
                    }
                    else if (rect.Bottom < compositeImage.Height
                        && xRange
                            .Select(bx => compositeImage.GetPixel(bx, rect.Bottom))
                            .Any(p => p.A != 0))
                    {
                        rect.Height++;
                    }
                    else if (rect.Left >= 0
                        && yRange
                            .Select(by => compositeImage.GetPixel(rect.Left, by))
                            .Any(p => p.A != 0))
                    {
                        rect.X--;
                        rect.Width++;
                    }
                    else if (rect.Right < compositeImage.Width
                        && yRange
                            .Select(by => compositeImage.GetPixel(rect.Right, by))
                            .Any(p => p.A != 0))
                    {
                        rect.Width++;
                    }
                    else
                    {
                        foundBounds = true;
                    }
                }
                result.Add(rect);
            }
        }
    }

    return result;
}