rotateLeftAndFlipInSitu

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);
       g2.dispose();
       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) {
    continue;
   }
   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);
    --movesLeft;
   }
   --movesLeft;
  }

  // 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.