7 ms·
Rotating Images
- nxpnsv 13y agoOk but, 126% is not a good rounding of 1.2956...
- deletes 13y agoIt is an obvious typo if you do the math. Angle = 27° result = 1/(cos Angle )^2 = 1.25961 which is rounded to 126%
- nxpnsv 13y agoyup. Anyhow, nice entry :)
- squeakynick 13y agoOooops, yes, a typo. I'll correct it later. :)
- adyus 13y agoI wonder if the onset of Retina-like displays would remove some of the issues with antialiasing when rotating bitmap images. I'm tired of looking at the digital world straight on.
- Tycho 13y agoSo when you do a shear, the pixels are only being moved horizontally or vertically in each stage, so therefore no gaps appear. Is that it?
- andrewcooke 13y agobut they still need interpolation because pixels in general won't exactly overlap. as far as i can see it's replacing the interpolation in 2d with multiple interpolations in 1d. but perhaps i am missing something. [edit] ok, after skimming the paper, it seems that they approximate the interpolation (using nearest neighbour). which makes it very fast. so really it's a neat way of working out what nearest neighbour is in 2d by doing it in 1d multiple times.
- GrantS 13y agoNote that one could also do "area mapping" with nearest neighbor instead of 4-pixel interpolation (if speed is more important than smoothness) to avoid the white dots. This is the most obvious "naive" approach to me -- basically the same cost as the white dots approach (loop over every destination pixel just once, grab just one pixel from source) but with some repeated neighboring pixels instead of missing information.
- logicallee 13y agoUm, these results look pretty horrible. Where are the pictures of area mapping that he mentions? (Where the missing holes are filled by doing averaging of four source pixels). Anyone knows what that looks like by comparison?
- nawitus 13y agoArea mapping certainly makes better images, but it's slower. These "horrible results" actually remind me of older games and some pc demos.
- deletes 13y agoRotation clockwise by 27° http://i.imgur.com/itniCWR.png http://i.imgur.com/itniCWR.png Left is my area mapping algorithm and right is adobe photoshop bilinear rotation.
- raphaelj 13y agoAs I understand his description of the area mapping algorithm, this is actually a bilinear interpolation from the resulting, rotated, image over the original image.
- theoh 13y agoThere's a Java applet comparing various high quality techniques here: http://bigwww.epfl.ch/demo/jrotation/index.html http://bigwww.epfl.ch/demo/jrotation/index.html
- fnayr 13y agoVery cool!
- brilee 13y agoAnother popular method of doing this is a variant on the area mapping technique, except that instead of taking the weighted average of the four nearest pixels, it instead creates a 2-D spline across the R/G/B "heights" of the image, and interpolate with the spline. The reason the triple-sheared images look crappy is because the three shears themselves are subject to pixel aliasing. Still pretty cool.
- bajsejohannes 13y agoWhile the result isn't great, it's a neat algorithm, and it will actually do gamma correction correctly. Sampling and weighing the four pixels will not, unless you specifically code for it. And looking at the history of gamma correction in software, most developers don't care about that.
- svantana 13y agoThat's not fair - you can look at this algorithm as doing nearest neighbor interpolation. No matter how you look at it, (bi-)linear interpolation will be more accurate, whether gamma corrected or not.
- michaelerule 13y agoIt is my understanding that gamma correction occurs in the display driver ( or possibly display itself, in some cases ). The colors that your application manipulates are the "raw" colors. Linearly interpolating in this space is correct. Gamma correction will be applied automatically later in the display pipeline.
- slig 13y agoNice article, this is HN material. My only "complain" is that he isn't using Lena as test images. ;-)
- squeakynick 13y agoGuilty, but I make up for it in another article on JPEG :) http://www.datagenetics.com/blog/november32012/index.html http://www.datagenetics.com/blog/november32012/index.html
- slig 13y agoThanks, I follow your twitter for a while and I love reading your posts! Keep up the good work!
- sammyo 13y agoWow, your hybrid optical illusion at the end of the article was fascinating, quite spooky/surprising.
- squeakynick 13y agoThanks for kind comments.
- pwg 13y agoThe unmentioned publication behind this method is: "A Fast Algorithm for General Raster Rotation" by Alan W. Paeth. A copy of which can be obtained here: http://www.cipprs.org/papers/VI/VI1986/pp077-081-Paeth-1986.pdf http://www.cipprs.org/papers/VI/VI1986/pp077-081-Paeth-1986.... While most explanations of the algorithm follow this blog post and imply that it is a three pass algorithm, if one carefully reads Paeth's paper, one realizes that the algorithm can be implemented as a one pass algorithm.
- DanielRibeiro 13y agoAnother very good overview of rendering algorithms was given by Steven Wittens on his Making Webgl Dance[1, 2] [1] slides: http://acko.net/files/fullfrontal/fullfrontal/webglmath/online.html http://acko.net/files/fullfrontal/fullfrontal/webglmath/onli... [2] video: http://www.youtube.com/watch?v=GNO_CYUjMK8 http://www.youtube.com/watch?v=GNO_CYUjMK8
- e98cuenc 13y agoThis is a fantastic speech and slides. Thanks for the link!
- jwmerrill 13y agoCan you expand on the one pass algorithm, or provide a link? There was a two pass variant at the end of the paper, but I didn't see any explicit one pass variant.
- deletes 13y agoThe single pass is the first algorithm mentioned in the article that produces "holes". You have to split the operations to avoid them and thus make more passes.
- pwg 13y agoThe first algorithm mentioned in the article is not a one-pass Paeth algorithm. The first algorithm in the article is a pure trigonometry algorithm. A one pass Paeth algorithm produces identical results to the typical three pass implementation, because there is only one round of trigonometry up front, so there is only one round of round-off. Once the shear amounts are calculated, the rest is just integer pixel shears.
- deleted 13y ago[deleted]
- anonymous 13y agoWouldn't the 3 shears method take a preposterous¹ amount of memory if you rotate by something like 180 degrees? The first shear will take a w.h image and output a w.h.h one! Why not simply use Bresenham's line drawing algorithm to "draw" a reverse-rotated rectangle over your image, but rather than drawing, you'd read pixels and write them to the destination image. You'll need to only rotate the corners of the image once and everything else is simple integer math. ¹ preposterous for the kind of device where doing it any other way is too slow Edit: replaced stars with dots for multiplication because stars make italic text
- pwg 13y ago> Wouldn't the 3 shears method take a preposterous¹ amount of memory if you rotate by something like 180 degrees? The first shear will take a w.h image and output a w.h.h one! If implemented as a three pass algorithm, yes. If implemented as a one pass algorithm, no.
- CamperBob2 13y agoWhy not simply use Bresenham's line drawing algorithm to "draw" a reverse-rotated rectangle over your image, but rather than drawing, you'd read pixels and write them to the destination image. You'll need to only rotate the corners of the image once and everything else is simple integer math. Trivia: this is how Wing Commander worked. Nobody was concerned about filtering or gamma correction in those days, needless to say! Bresenham point-sampling is an example of a 'forward transform', where you look at each pixel in the source image and decide where it goes in the destination image. You can also use conventional texture mapping to rotate an image, which is a case of an 'inverse transform' where you traverse each pixel in the destination image and figure out what texel(s) contribute to it. Inverse transforms are much simpler -- Bresenham sampling has some ugly complexities, especially if you want to scale the image as well as rotate it -- but they aren't as efficient if the image has a lot of transparency.
- marshray 13y agoClearly there are better ways to rotate by 180 degrees! If you need to rotate by 179, first rotate by 180, then by -1.
- jloughry 13y agoThe post reminds me of BYTE article from 1981, in the Smalltalk special issue. It was the first time I had ever seen recursion illustrated graphically, on a bitmap of Mickey Mouse's face [1]. Lots of good articles in that issue, and the whole thing is available on-line at the Internet Archive [2]. [1] Daniel H. H. Ingalls. The Smalltalk Graphics Kernel. BYTE 6(8), August, 1981, pp. 168--94. [2] http://archive.org/stream/byte-magazine-1981-08/1981_08_BYTE_06-08_Smalltalk#page/n181/mode/2up http://archive.org/stream/byte-magazine-1981-08/1981_08_BYTE...
- javajosh 13y agoWonderful link! Off-topic, but I was particularly enthralled with the ads. Many of them are great, but my favorite was for "The Last One"[1]. "Say goodbye to the frustrations of computer programming. The Last One will be available very soon...The Last One is a computer program that writes computer programs. Programs that work the first time. Every time." And for only $600. I was surprised to see that this software actually shipped, according to Wikipedia. [2] Alas, it was not the last piece of software that people ever needed to use, apparently. [1] http://archive.org/stream/byte-magazine-1981-08/1981_08_BYTE_06-08_Smalltalk#page/n209/mode/2up http://archive.org/stream/byte-magazine-1981-08/1981_08_BYTE... [2] https://en.wikipedia.org/wiki/The_Last_One_(software) https://en.wikipedia.org/wiki/The_Last_One_(software)
- adsr 13y agoAppart from the aliasing issue, isn't there also a way to use complex numbers to do the rotation?
- wetmore 13y agoYeah, you can view complex numbers as 2d vectors. In this view, you can choose a complex number with a magnitude of 1, at some angle θ to the x-axis (the real line). If you multiply this number by another complex number, it will rotate that number by the angle θ. We can express such a complex number as cosθ + i sinθ. If you express such a complex number as a 2x2 matrix (there is a unique 2x2 matrix for each complex number, such that the complex number a + ib becomes the matrix [ a, b -b, a ] you'll notice that the matrix form of our unitary (magnitude 1) complex number is just a rotation matrix like the one discussed in the article.
- dsugarman 13y agoa little anti-aliasing would go a long way in these rotated images
- bitL 13y agoI would still rather use a simple texture mapping - map the image to a rectangle and then just rotate the 4 corner points. Rest is done naturally by your texture mapper. You can implement a texture mapper easily by finding the top-most rotated corner, take the two edge lines coming out of that corner, linearly interpolate texture coordinates on these lines for each horizontal line they cross and then simply walk linearly between those two texture positions spread across the horizontal line range. Then replace the edge line whose endpoint you reached by the next line until you reach the bottom-most corner. You can add surrounding texels to the mix to get the bilinear or another filtering. Also, Bresenham's line algorithm can be used for each of the line interpolations (though my assembly language experience showed that fixed point ints were actually faster). This is also embarrassingly parallel.
- fprawn 13y agoThis is really neat, but seems to neglect an alternative (and just as simple) method. Instead of traversing through each pixel of the source buffer, traverse through each pixel of the destination buffer sampling the correct pixels from the source. Using different sampling methods results in various qualities, and efficiencies in cpu use and memory access. This method is as simple to code and doesn't suffer from the missing-pixel aliasing problem of the simple method of the article, and is also capable of higher quality results than the shearing method.
- deletes 13y agoYou have to traverse sqrt(2) times more pixels than in the original method unless you somehow know where the borders of the destination square are ( additional computation ).
- fprawn 13y agoThis is true only if the source image is smaller than the destination image. In the article, the source image is shown as the same size as the destination, and includes a large white border that can be clipped without the inner image being affected. In the event that the destination buffer is much larger than the source, that additional computation is trivial (it's the same calculation that's already being done for each and every pixel). As it only needs to be additionally done on the corners, not per-pixel, the additional time spent should be quite minimal. The shearing method in the article is genuinely clever and totally cool, but I just can't shake the feeling that even on 1980s hardware, this method would be better. On modern hardware, there's no question, it's still used to this day. Nowhere near as cool, though.
- deletes 13y agoCould you post some links explaining your method?
- gijjk 13y ago"conformal" means "angle-preserving", not "area-preserving" http://en.wikipedia.org/wiki/Conformal_map http://en.wikipedia.org/wiki/Conformal_map