Crop image to smallest size by removing transparent pixels in java

Question

I have a sprite sheet which has each image centered in a 32x32 cell. The actual images are not 32x32, but slightly smaller. What I'd like to do is take a cell and crop the transparent pixels so the image is as small as it can be.

How would I do that in Java (JDK 6)?

Here is an example of how I'm currently breaking up the tile sheet into cells:

BufferedImage tilesheet = ImageIO.read(getClass().getResourceAsStream("/sheet.png");
for (int i = 0; i < 15; i++) {
  Image img = tilesheet.getSubimage(i * 32, 0, 32, 32);
  // crop here..
}

My current idea was to test each pixel from the center working my way out to see if it is transparent, but I was wondering if there would be a faster/cleaner way of doing this.

Answer 1

There's a trivial solution – to scan every pixel. The algorithm bellow has a constant performance of O(w•h).

private static BufferedImage trimImage(BufferedImage image) {
    int width = image.getWidth();
    int height = image.getHeight();
    int top = height / 2;
    int bottom = top;
    int left = width / 2 ;
    int right = left;
    for (int x = 0; x < width; x++) {
        for (int y = 0; y < height; y++) {
            if (image.getRGB(x, y) != 0){
                top    = Math.min(top, y);
                bottom = Math.max(bottom, y);
                left   = Math.min(left, x);
                right  = Math.max(right, x);
            }
        }
    }
    return image.getSubimage(left, top, right - left + 1, bottom - top + 1);
}

But this is much more effective:

private static BufferedImage trimImage(BufferedImage image) {
    WritableRaster raster = image.getAlphaRaster();
    int width = raster.getWidth();
    int height = raster.getHeight();
    int left = 0;
    int top = 0;
    int right = width - 1;
    int bottom = height - 1;
    int minRight = width - 1;
    int minBottom = height - 1;

    top:
    for (;top <= bottom; top++){
        for (int x = 0; x < width; x++){
            if (raster.getSample(x, top, 0) != 0){
                minRight = x;
                minBottom = top;
                break top;
            }
        }
    }

    left:
    for (;left < minRight; left++){
        for (int y = height - 1; y > top; y--){
            if (raster.getSample(left, y, 0) != 0){
                minBottom = y;
                break left;
            }
        }
    }

    bottom:
    for (;bottom > minBottom; bottom--){
        for (int x = width - 1; x >= left; x--){
            if (raster.getSample(x, bottom, 0) != 0){
                minRight = x;
                break bottom;
            }
        }
    }

    right:
    for (;right > minRight; right--){
        for (int y = bottom; y >= top; y--){
            if (raster.getSample(right, y, 0) != 0){
                break right;
            }
        }
    }

    return image.getSubimage(left, top, right - left + 1, bottom - top + 1);
}

This algorithm follows the idea from pepan's answer (see above) and is 2 to 4 times more effective. The difference is: it never scans any pixel twice and tries to contract search range on each stage.

The worst case of the method's performance is O(w•h–a•b)