Tuesday, March 04, 2008


Recently I was working with some large (200MB) vertically-oriented core images in Java. I needed a way to rotate these images CCW so they were horizontally-oriented and flip them vertically for display on an OpenGL canvas. It's a pretty easy task if you're using the Java2D API:

// get our dimensions
final int w = image.getWidth();
final int h = image.getHeight();

// create our new image and graphics
final BufferedImage out = new BufferedImage(h, w, image.getType());
final Graphics2D g2 = out.createGraphics();

// setup up an affine transformation
final AffineTransform at = AffineTransform.getRotateInstance(Math
.toRadians(-90.0), h / 2, w / 2);
at.translate((h - w) / 2, (w - h) / 2);
g2.drawRenderedImage(image, at);
return out;

That snippet will rotate your image to the left. If you twiddle with the affine transform, you can also get it to flip the image for you. The only problem with this approach is that it requires you allocate a second image to hold the results of the transformation. So rotating a 200MB image actually requires 400MB of memory (give or take). This isn't a big deal if I only ever needed to rotate one large image at a time, but in the application, I didn't know how many large images the user was going to be working with at a time. So I decided to see if I could do the rotation in O(1) space complexity.

It turns out that this is actually a pretty difficult problem. It's been studied since the 70s under the guise of "in-situ transposition of a rectangular matrix". Once I found this out, it became a personal quest to come up with a solution. In the end, I was successful:

// get our sample model and data buffer
final SampleModel model = image.getSampleModel();
final DataBuffer db = image.getRaster().getDataBuffer();

final int w = model.getWidth();
final int h = model.getHeight();
final int[] t1 = new int[model.getNumBands()];
final int[] t2 = new int[model.getNumBands()];

// transpose
int i, j, k, movesLeft;
for (i = 0, movesLeft = w * h; movesLeft > 0; i++) {
for (j = pred(i, w, h); j > i; j = pred(j, w, h)) {
// spin

if (j < i) {
for (k = i, j = pred(i, w, h); j != i; k = j, j = pred(j, w, h)) {
// get our pixels
model.getPixel(k % w, k / w, t1, db);
model.getPixel(j % w, j / w, t2, db);

// swap them
model.setPixel(k % w, k / w, t2, db);
model.setPixel(j % w, j / w, t1, db);

// now return a new image with an updated sample model
final WritableRaster raster = Raster.createWritableRaster(model
.createCompatibleSampleModel(h, w), db, null);
return new BufferedImage(image.getColorModel(), raster, image
.isAlphaPremultiplied(), null);

with pred() defined as:

return (i % h) * w + (i / h);

This algorithm works. It'll rotate the image in place. Thus, if you could load the image in the first place, you shouldn't run out of memory when you rotate it.

With that being said, this approach is pretty naive. There are numerous optimizations that could be implemented, from increasing the amount of temporary storage you use to optimizing the look up so you spend less time spinning.

In the end, I didn't end up using the code in production. It was a fun exercise to work through, though.

No comments: