Image Rotation Code Interview

[refactored from InterviewingWithCode, SteveHowell, 08/17/2001]

A guy at work asked me a question he had been asked in an interview: given 1.5 Mb of RAM and a 1 Mb image, how do you rotate the image (in Java). Now the first thing you need to know is that in order to rotate an image in Java, you need to copy it into a buffer. This means that you could not have the whole image in RAM and rotate it and hold the rotated image -- he explained this to me so I may have explained it incorrectly. I solved the problem by splitting the image into four parts and rotating each part. He said that I could have done it in two parts (1 Mb for whole image plus 0.5Mb for one half at a time in RAM). So I asked him how much it costs to perform a rotate. He didn't know. Please, please if you are going to ask questions that have to do with code in an interview be prepared for stuff like this. If you are nitpicking about somebody using RAM or CPU-cycles or some such thing be prepared to answer questions like the ones I had or at least be prepared to say "this guy may not have answered this the way I expected but he is demonstrating the quality I am looking for."

JeffGrigg's answer: VirtualMemory?. It doesn't matter that you have only 1.5 MB of RAM for two copies of a 1 MB image. Load and rotate it using any convenient library. Let the OperatingSystem's memory management system do it's job and don't worry about it until you can demonstrate, with real measurements, that it's "too slow."

StevenNewton's gotcha: I have an embedded system a la PalmOS. I can "save" to a persistent datastore, but the OS doesn't have any way to access that as virtual memory. If my program attempts to allocate more than 1.5MB of RAM I will get an out of memory error.

OK, you've added new constraints. Try this: The PalmOS isn't usually considered a batch processing system; it's interactive. So perhaps the real requirement is that you *DISPLAY* the rotated image. Why not load the image into memory and have your "rendering" logic rotate it as you copy it to the screen?

Simple answer:- It's a handheld device. Yes? The user can physically rotate it.

If you said the reason was it was PalmOS (or anything like it), I'd laugh in your face and walk out of the interview. "Obviously" your company doesn't actually code anything, but writes marketing fluff about what you wish you could do. Lesson. Never interview with code that doesn't exist. I think I might kick you in the shins on the way out, too, for disrespecting me that much. -- SunirShah, HandHeld developer, aggressive interviewee

New Twists

SteveHowell -- Let me add these constraints: It's a square array of pixels, represented by a 2d array of 128-bit ints on a remote machine, and because it must often be embedded into bigger square arrays of pixels, your fellow coders have asked that you update the chunk of memory itself, rather than relying on tricks of physically rotating the device or tweaking the rendering logic for this particular subimage. You need to rotate the image 90 degrees clockwise about the center coordinate 0,0. The remote machine only has enough memory for the existing array, plus it has some 128-bit registers. The two machines have no network drivers, but there is a serial connector that lets your machine send these commands to the remote machine: 

  GET X, Y, N - gets coordinates from x,y into register N
  PUT X, Y, N - puts coordinates of register N into x,y
How many registers do you need for a TxT array? (Assume T is odd.)

I think that I can do it with two registers. I've got a proof for 1x1, 3x3 and 5x5. The step from 3x3 to 5x5 isn't strong enough to be used for proof by induction, but I think it scales properly. -- RogerLipscombe

128 bits of color??? Human eyes can't resolve such subtle differences in color. Drop the useless low bits and and use them for the rotation. Now you have plenty of memory.

Especially since, IIRC, the color versions of PalmOS only support 12-bit color.

Hey! That was my answer!

Forget X,Y. The problem can be restated like so "How many registers does it take to reorder a bunch of memory m from one sequence to a different sequence." Like Roger I think (but have no proof) that you only need two registers. Let's say you want to move the value from m[a] to m[b]. You load m[a] and m[b] into r1 and r2, respectively. Then move r1 to to m[a]. Now figure out where you need to move r2. Let's say that's position m[c]. Load m[c] into r1 and r2 into m[c]. And on and on. --AndrewQueisser

That only works if the sequences are permutations, so that they are mutually bijective. If you have a lossy transformation, you might have problems. -- SunirShah

SteveHowell: I was thinking of the two-register solution when I posed the problem above. If you're rotating a square about the center, then you only have to rotate quartets of points at a time. For example, A:(3,2) goes to B:(2,-3), B goes to C:(-3,-2), C goes to D:(-2,3), and D goes to A. So, for each quartet, you do this: 

  D -> R1
  C -> R2
  R2 -> D
  B -> R2
  R2 -> C
  A -> R2
  R2 -> B
  R1 -> A
I agree that 128-bit color is totally absurd; I guess all I should have stated to constrain the problem was that you had no network drivers.

You can do it with one register and XORing (if the XOR x,y,N instruction were available), but it's much slower. 

 #define NUMELEM(x) (sizeof (x) / sizeof *(x))


 // For ease of description, pretend the quartet (or its coordinates) 
 // is placed in source[].
 int source[4] = {...};
 for( int i = 0; i < (NUMELEM(source)*NUMELEM(source)-1); i++ ) {
     // source[i+1] ^= source[i];
     GET(source[i],R1);
     XOR(source[i+1],R1);
 }
-- SunirShah

There is a very clever algorithm around (sorry, no name name or author right now) that allows one to rotate images by processing only one line at a time. It can be useful for large images in a low RAM environment. One downside is that the algorithm requires three passes over the data, so having more RAM is definitely quicker. From memory the algorithm achieves its trickery by shearing, or tilting the image by different amounts each time, so that after the third pass, the image has been rotated by the required amount.

I think you mean Fant, K.M. (1986) IEEE Computer Graphics & Applications 6,1 71-80. "A nonaliasing, real-time spatial transform technique."

Here's an example I just cooked up. Graphics Gems I maybe. The example is a 90 degree flip in place i.e. no extra memory required (okay a register to hold the shift). Super fast rotozoomers use a lookup table for the three shifts. Ultrafast ones subdivide the image into cache lines and rotate the smaller squares recursively. The final shift is left till the end if I remember correctly. Anywhoo, here's the cute example: 

   1  2  3  4     2  3  4  1    13  9  5  1   13  9  5  1
   5  6  7  8     7  8  5  6     2 14 10  6   14 10  6  2
   9 10 11 12    12  9 10 11     7  3 15 11   15 11  7  3
  13 14 15 16    13 14 15 16    12  8  4 16   16 12  8  4
Or, in case this isn't obvious: 

   1  2  3  4              1  2  3  4   13  9  5  1             13  9  5  1  
   5  6  7  8           5  6  7  8         14 10  6  2          14 10  6  2
   9 10 11 12        9 10 11 12               15 11  7  3       15 11  7  3
  13 14 15 16    13 14 15 16                     16 12  8  4    16 12  8  4
I thairkyaw, RichardHenderson.

There is a Linux screensaver which performs 90-degree rotations, and displays intermediate results, by what looks like an in-place algorithm which recurses upon each quadrant of the image. Unfortunately, my understanding of it is insufficient for a more complete description. -- DanielKnapp 

 rotate(squareArea) {
   cut into four quads
   shift each quad
   for each quad 
      rotate(quad)
 }
I have a vague recollection that this algorithm was discussed in a Xerox PARC tech report, circa 1980. -- DaveSmith

It is also possible to rotate an image by arbitrary angles in-place, though this is fairly slow and doesn't do anti-aliasing. Basic scheme:

I once used a variant of this once for a warp effect which applied this repeatedly, so the radius calculations could be reused.

CategoryInterview

EditText of this page (last edited July 18, 2008) or FindPage with title or text search