4 ms·

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 operation

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/rotation_by_shearing.html https://www.ocf.berkeley.edu/~fricke/projects/israel/paeth/r...

RicoElectrico 5y ago
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.
- teddyh 5y ago
  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.
  - davorak 5y ago
    > 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?
    - isaacimagine 5y ago
      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.
    - tobr 5y ago
      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.
- CyberShadow 5y ago
  There will always be 100 pixels, however, they will no longer be arranged in a perfectly straight and consistent line any more.
Fronzie 5y ago
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.
- edge17 5y ago
  But nearest neighbors interpolation would be quick on a gpu, right?
phkahler 5y ago
Here's an some source code for bitmap rotation from the mid 90's: http://cd.textfiles.com/ems/emspro1/PASUTIL/ROTATEBM.ZIP http://cd.textfiles.com/ems/emspro1/PASUTIL/ROTATEBM.ZIP It's Turbo Pascal with inline ASM.

RicoElectrico 5y ago

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.

teddyh 5y ago
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.
- davorak 5y ago
  > 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?
  - isaacimagine 5y ago
    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.
  - tobr 5y ago
    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.
CyberShadow 5y ago
There will always be 100 pixels, however, they will no longer be arranged in a perfectly straight and consistent line any more.

Fronzie 5y ago

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.

edge17 5y ago
But nearest neighbors interpolation would be quick on a gpu, right?

phkahler 5y ago

Here's an some source code for bitmap rotation from the mid 90's: http://cd.textfiles.com/ems/emspro1/PASUTIL/ROTATEBM.ZIP http://cd.textfiles.com/ems/emspro1/PASUTIL/ROTATEBM.ZIP It's Turbo Pascal with inline ASM.