[HN Gopher] Recursive image rotation (2020) [video]
___________________________________________________________________
Recursive image rotation (2020) [video]
Author : tosh
Score : 54 points
Date : 2021-11-11 06:51 UTC (1 days ago)
(HTM) web link (www.youtube.com)
(TXT) w3m dump (www.youtube.com)
| acomjean wrote:
| I see what it's doing recursively (splitting into quadrants and
| moving clockwise) . But I'm a bit startled as to why it rotates,
| but I'm thinking when it gets to one pixel is key but it still
| seems like a lateral shift...
| arketyp wrote:
| This lateral shift on a 2x2 grid is equal to rotation. In each
| iteration tiles are shifted/rotated but its content is not. So
| the content is split into smaller tiles which are rotated but
| the content is not, so it is split and so on until you reach
| pixel level.
| Someone wrote:
| If you have AB CD
|
| with A, B, C, D square blocks of 2^nx2^n pixels, it correctly
| moves the pixels in A to where those in B are, those in B to
| where those in D are, etc.
|
| It doesn't rotate A, B, C, and D, though. So, we have to rotate
| the four smaller blocks A, B, C, D.
|
| Let's assume the algorithm works. Then, we can recurse into
| each of the smaller blocks.
|
| Eventually, you hit the case where A, B, C, and D are 1x1
| pixels (and the image 2x2 pixels). Here, you cannot recurse
| anymore, but luckily, you notice that you can't see the
| difference between a single pixel and that pixel rotated by 90
| degrees. So, for sunblocks that small, you don't have to rotate
| the pixels. Because of that, the 2x2 case works. Because of
| that, the 4x4 case works, etc.
|
| You could also say it doesn't work. If, say, your pixels had a
| wood grain running horizontally, that grain would still run
| horizontally after this set of shifts.
| daneel_w wrote:
| Grossly inefficient, yet grossly interesting.
| Kenji wrote:
| Divide and conquer.
| HPsquared wrote:
| Is there any advantage to doing it this way? Partitioning?
| gsliepen wrote:
| It's easy to parallelize this, and at a certain recursion level
| the whole block will fit into cache, so this might avoid
| inefficient memory access compared to a naive for-loop that
| just moves every pixel to its rotated position.
| dan-robertson wrote:
| Except you need to access each pixel log(n) times and it
| doesn't obviously work for non-square images (or for non-
| right rotations).
|
| Compare to the normal way you rotate things by right angles
| where e.g. new_image(x,y) = old_image(y, old_height - x),
| which is extremely embarrassingly parallel.
|
| The actual reason is that it is fun.
| CyberShadow wrote:
| > new_image(x,y) = old_image(y, old_height - x)
|
| If you implement this as a view (rather than imperatively),
| you can get the compiler to optimize out four successive
| rotations to nothing :)
|
| https://blog.cy.md/2014/03/21/functional-image-processing-
| in...
| gsliepen wrote:
| I assume that in an actual implementation you are not
| really processing every pixel log(n) times, but rather do
| something like new_image = rotate(old_image, 1), where 1 is
| the recursion level, and rotate(image, level) calls
| rotate(subset_of(image), level + 1) recursively until it
| reaches a single pixel, which is then returned as-is.
| Combined with return value optimization, that should avoid
| any temporaries being stored.
|
| But yes, it's mostly fun :)
| a4isms wrote:
| I'm not making claims about production graphics algorithms, but
| this gets really interesting if you consider using quad trees
| to represent images rather than bitmaps.
|
| The algorithm as presented turns the image into a quadtree as
| it works, for then re-flattens it. But if we store the image as
| a quadtree to begin with, we obtain other advantages:
|
| 1. We can memoize operations like rotation so that the
| algorithm goes much faster for images that have large blocks of
| a single colour or pattern;
|
| 2. We can write other operations that recursively apply to the
| image, like changing one color to another.
|
| http://raganwald.com/2016/12/27/recursive-data-structures.ht...
|
| Original discussion:
|
| https://news.ycombinator.com/item?id=13304487
| baybal2 wrote:
| No lookup tables
| user-the-name wrote:
| No rotate-by-ninety-degree algorithms use lookup tables.
| user-the-name wrote:
| Not really. It requires far too many memory accesses to be
| efficient.
| a_e_k wrote:
| I wouldn't do it exactly this way, but for a CPU implementation
| I would consider a blocked rotate that decomposes the image
| into square tiles of about [cache-line x cache-line] in size
| (e.g., 8x8 for RGBA8 data with a 32 byte cache line). Then
| cycle sets of four tiles and rotate within them in the process.
| E.g., cycle and rotate the four A tiles, cycle and rotate the
| four B tiles, etc: A B C D M I E A E
| F G H N J F B I J K L O K G C M N O P P L H D
| D H L P P O N M C G K O L K J I B F J N H G F E
| A E I M D C B A
|
| With the right tile sizes and memory alignment you could
| parallelize these steps without false sharing.
| albert_e wrote:
| does the pixel size of the image need to be a power of 2 for this
| to work without artifacts
| tromp wrote:
| yes, you cannot do this to a 3x3 grid of pixels for example.
| a4isms wrote:
| Any right quadrangle of any dimensions can be rotated with
| this algorithm by padding it to become a square with 2^n
| pixels per side, rotating the square, and then removing the
| padding.
|
| The degenerate case is when the right quadrangle is already a
| square with 2^n sides, in which case there is no padding to
| remove.
| [deleted]
| rambojazz wrote:
| I guess this is a nice example of why multimedia people benefit
| tremendously from high parallelization.
| dolmen wrote:
| This is more an example of a case where a recursive algorithm
| is very slow.
| tromp wrote:
| This is transforming the address of each pixel one bit (of both x
| and y coordinate) at a time, from most to least significant.
| teddyh wrote:
| Used in the 1992 BlitSpin screen saver, part of the XScreenSaver
| collection:
|
| https://www.youtube.com/watch?v=UTtcwb-UWW8&list=PLbe67PprBS...
|
| EDIT: But I can't find any acknowledgement in either the
| "Recursive Image Rotation" YouTube video, the original tweet, or
| the source code.
|
| EDIT2: In a Reddit thread1, they acknowledge a PDF of a book from
| 20192. The book itself gives no acknowledgements for the
| algorithm.
|
| 1.
| https://www.reddit.com/r/compsci/comments/izy2kf/rotating_an...
|
| 2.
| https://jeffe.cs.illinois.edu/teaching/algorithms/book/01-re...
| abecedarius wrote:
| IIRC it was in _Smalltalk-80: the language and its
| implementation_ from the 1980s. Or perhaps one of the other two
| books in that series.
| igouy wrote:
| page 408 ?
|
| https://rmod-
| files.lille.inria.fr/FreeBooks/BlueBook/Blueboo...
| teddyh wrote:
| Yup, there it is. (Pages 430-432 of that PDF file, figures
| 20.8 through 20.10) So I guess that 1983 is the earliest
| year found so far.
| igouy wrote:
| We can do almost a decade better :-)
|
| Pages 26 through 28, "The Evolution of Smalltalk: From
| Smalltalk-72 through Squeak"
|
| Proc. ACM Program. Lang., Vol. 4, No. HOPL, Article 85.
| Publication date: June 2020.
|
| http://worrydream.com/refs/Ingalls%20-%20The%20Evolution%
| 20o...
| teddyh wrote:
| A decade? That reference gives a date of 1981 for the
| bitmap-rotating algorithm:
|
| > _The Byte article on "The Smalltalk Graphics Kernel"
| [Ingalls 1981] details Smalltalk methods that, with
| BitBlt at their core, can lay out and display text, draw
| lines, and magnify and rotate images--each in little more
| than a dozen lines of code._
|
| [...]
|
| > _Daniel H. H. Ingalls. 1981. The Smalltalk Graphics
| Kernel. Byte 6, 8,
| 168-194.https://archive.org/details/byte-
| magazine-1981-08/page/n181/..._
|
| In that reference, the bitmap rotation is on page 188 in
| the original publication (page 202 of the archived
| document).
| CyberShadow wrote:
| 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...
| Fronzie wrote:
| 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 wrote:
| But nearest neighbors interpolation would be quick on a gpu,
| right?
| phkahler wrote:
| 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.
| RicoElectrico wrote:
| 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.
| CyberShadow wrote:
| There will always be 100 pixels, however, they will no longer
| be arranged in a perfectly straight and consistent line any
| more.
| teddyh wrote:
| 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 wrote:
| > 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 wrote:
| 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 wrote:
| 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.
| dvh wrote:
| This is similar to how to swap two numbers without using
| temporary variable: X = 31; Y = 25;
| console.log(X, Y); // prints 31 25 X = X + Y; Y =
| X - Y; X = X - Y; console.log(X, Y); // prints 25
| 31
| teddyh wrote:
| Only if you assume that X+Y never exceeds 9007199254740991
| (Number.MAX_SAFE_INTEGER, 253-1).
|
| Also, that algorithm has nothing in common with the image
| rotation one; the image rotation algorithm _does_ require a
| temporary buffer.
| nomel wrote:
| This is why I like python: X = 31 Y =
| 25 X, Y = Y, X
| robomartin wrote:
| This still creates a temporary variable. Sorry.
| brrrrrm wrote:
| Where? Variables are a language semantic not an
| implementation detail. A temporary variable is just a new
| symbolic name. You may be thinking of temporary storage
___________________________________________________________________
(page generated 2021-11-12 23:02 UTC)