Hacker News Reader

Comment by CyberShadow | Hacker News Reader

There is an algorithm to rotate an image by any angle (not just multiple of 90), and without adding, duplicating or deleting pixels, using three shear operations (which only move rows/columns along one orthogonal axis).

https://www.ocf.berkeley.edu/~fricke/projects/israel/paeth/r...

View on HN

If you rotate a straight line by 45 degrees, there will be deleted pixels. A horizontal line of 100 pixels will consist of ~70 pixels (100 * sqrt(2) / 0.5) after such rotation.

I don’t think so. As I understand the algorithm, no pixels are ever deleted. The 100 pixels would still be there, but probably a bit mushed together to fit on a line 70 pixels in length.

> The 100 pixels would still be there, but probably a bit mushed together to fit on a line 70 pixels in length.

This seems incorrect. It sounds like you are saying that you can store any 100 random values into 70 values. Or 100 bits of information in to 70 bits.

If you could, what would stop you from then storing that 70 bits in 49 bits, then that 49 in ~34 bits, etc and therefor have infinite information storage?

You're assuming the rotated line maintains the same pixelwise thickness. A straight 1 pixel line edge-to-edge may not translate to a diagonal 1 pixel line corner-to-corner. I think that's what the parent is saying. No data is being 'compressed' here; the shear operation simply preserves all pixels uniquely.

It’s certainly not incorrect, these are not infinitely thin lines. The original line is 100 pixels long and 1 pixel wide. A diagonal stair-stepped line of 70 pixels is an average of about 0.7 pixels wide, which is why you’re deleting about 30%. You need to mush the additional pixels in somewhere between the stair steps to make it an average of 1 pixel wide again.

There will always be 100 pixels, however, they will no longer be arranged in a perfectly straight and consistent line any more.

The drawback is that it does require 3 times interpolation. With neares-neighbour interpolation that is not obvious from the example, but it's there.

Each interpolation step causes loss of resolution and the multiple passes might in practice make it slower due to increased memory bandwidth requirements compared to a single pass algorithm.

That of course doesn't take away that it's an interesting trick to know about.

But nearest neighbors interpolation would be quick on a gpu, right?

Here's an some source code for bitmap rotation from the mid 90's:

http://cd.textfiles.com/ems/emspro1/PASUTIL/ROTATEBM.ZIP

It's Turbo Pascal with inline ASM.

Reply on news.ycombinator.com