ericf@persoft.UUCP (Eric R. Feigenson) (06/10/89)
[Please excuse me if this type of thing has been requested before. I don't
normally read this newsgroup]
I am look for any and all algorithms relating to rotating a bitmap an
aribtrary amount. Efficiency and accuracy (minimal distortion) are,
of course, important considerations. An English or pseudo-code
description would be fine, but any high level language implementation
would do nicely. Pointers to books and/or articles on the subject
are also welcome. Please e-mail responses. If there is sufficient
interest, I will post results to the net.
Thanks in advance!
-Eric
---------------------------------------------------------------------------
-Eric Feigenson
Persoft, Inc.
(Internet) ericf@Persoft.COM
(UUCP) {ihnp4, seismo, uunet, allegra}!uwvax!persoft!ericfmike@relgyro.stanford.edu (Mike Macgirvin) (06/13/89)
In article <8.UUL1.2#261@persoft.UUCP> ericf@persoft.UUCP (Eric R. Feigenson) writes: >I am look for any and all algorithms relating to rotating a bitmap an >aribtrary amount. Efficiency and accuracy (minimal distortion) are, >of course, important considerations. An English or pseudo-code #include <math.h> #define radians(angle) ((angle) / 5.729578E+01) #define HEIGHT some_integer_number #define WIDTH some_integer_number unsigned char image[WIDTH][HEIGHT]; rotate(angle) double angle; /* rotate image 'angle' degrees */ { int color; int xx,yy; for(y = 0;y < HEIGHT; y ++) for(x = 0;x < WIDTH; x ++) { color = image[xx][yy]; xx = (x * cos(radians(angle)) - (y * sin(radians(angle)); yy = (x * sin(radians(angle)) + (y * cos(radians(angle)); setpixel(xx,yy,color); } } There are some 'holes' in an image using this method at angles which are not right angles. I have experimented with methods that set surrounding pixels to the same value (and covering some of them over later with real values) to eliminate the 'holes', but have had limited success. ------------------------------------------------------- "There must be some kind of way out of here." Mike Macgirvin - mike@relgyro.stanford.edu (36.64.0.50) -------------------------------------------------------
rokicki@polya.Stanford.EDU (Tomas G. Rokicki) (06/13/89)
mike@relgyro.stanford.edu (Mike Macgirvin) writes: > >I am look for any and all algorithms relating to rotating a bitmap an > >aribtrary amount. Efficiency and accuracy (minimal distortion) are, > >of course, important considerations. An English or pseudo-code > ericf@persoft.UUCP (Eric R. Feigenson) writes: > unsigned char image[WIDTH][HEIGHT]; > rotate(angle) > double angle; /* rotate image 'angle' degrees */ > { > int color; > int xx,yy; > for(y = 0;y < HEIGHT; y ++) > for(x = 0;x < WIDTH; x ++) { > color = image[xx][yy]; > xx = (x * cos(radians(angle)) - (y * sin(radians(angle)); > yy = (x * sin(radians(angle)) + (y * cos(radians(angle)); > setpixel(xx,yy,color); > } > } This algorithm can be generalized and improved (eliminating the `holes') quite easily; simply iterate over the output points rather than the input points. Thus, for (P = each point in the output) { P2 = TRANSFORM(P) ; /* can include rotations, scaling, etc */ setpixel(destination, P, getpixel(source, P2)) ; } TRANSFORM is the usual six-element matrix, that rounds the point after it's done. The resulting bitmap won't be beautiful. Better results can often be obtained by interpolating between source pixels. For instance, if the unrounded transformed result was (2.3, 4.6), then a better looking image might be obtained by using .3[.6[g(2,4),g(2,5)],.6[g(3,4),g(3,5)]] where n[a,b] means ((1-n) * a + n * b) and g(x,y) means the value of the source at pixel (x,y). The image may be more `blurry' this way, though . . . If you are scaling up (to more bits), this type of interpolation is probably not a bad idea. If you are scaling down (to less bits), it can give odd effects; you might want to high-pass filter the image before scaling it down. -tom
foster@tramp.Colorado.EDU (J. Gabriel Foster) (06/14/89)
In article <230@helens.Stanford.EDU> mike@relgyro.STANFORD.EDU (Mike Macgirvin) writes: >In article <8.UUL1.2#261@persoft.UUCP> ericf@persoft.UUCP (Eric R. Feigenson) writes: >>I am look for any and all algorithms relating to rotating a bitmap an >>aribtrary amount. Efficiency and accuracy (minimal distortion) are, >>of course, important considerations. An English or pseudo-code > Some code is included at this point. > > There are some 'holes' in an image using this method at angles >which are not right angles.... > Two comments: 1) I think there is a bug in the included code. 2) There is a way that is less likely to produce holes. Here are the proposed fixes. > for(y = 0;y < HEIGHT; y ++) > for(x = 0;x < WIDTH; x ++) { > xx = (x * cos(radians(angle)) - (y * sin(radians(angle)); > yy = (x * sin(radians(angle)) + (y * cos(radians(angle)); > color = image[xx][yy]; > setpixel(x,y,color); > } Notice that you always fetch from the source picture at the rotated angle. (The angle may need to be -angle by the way. I have not tested it.) This means that you set every pixel in the destination image, so there are no rounding errors that leave holes. (There are other problems, mostly with some pixels getting spread out a bit.) Hope this helps. --> J. Gabriel Foster --> foster@eprince.colorado.edu --> foster%eprince@vaxf.colorado.edu.BITNET University of Colorado @ Boulder.
levine@well.UUCP (Ron Levine) (06/22/89)
In article <8.UUL1.2#261@persoft.UUCP> ericf@persoft.UUCP (Eric R. Feigenson) writes: > >I am look for any and all algorithms relating to rotating a bitmap an >aribtrary amount. Efficiency and accuracy (minimal distortion) are, >of course, important considerations. .... > I believe that the fastest methods of rotating raster images, and the easiest to which to add filtering to fix the aliasing (holes in the image), are the so-called two-pass methods, in which one pass preserves horizontal scan lines and the other preserves vertical scan lines. These are especially effective when frame buffer memory has been designed for efficient access by horizontal and vertical scan lines. This is the basis of the ADO, (Ampex Digital Optics), the machine which makes most of the real-time video effects that we see so much of on TV, involving rotations and other 2D linear transformations. References: Ed Catmull and Alvy Ray Smith, 3-D Transformations of Images in Scan-Line Order, Computer Graphics, Vol. 14, No. 3, pp.279-285, July, 1980 (Siggraph Proceedings) Philip P. Bennet and Steven A. Gabriel, System for Spatially Transforming Images, U.S. Patent #4,472,732, September 18, 1984. Alvy Ray Smith, Planar 2-Pass Texture Mapping and Warping, Computer Graphics, Vol 21, No. 4, July 1987 (Siggraph Proceedings) --Ron Levine
awpaeth@watcgl.waterloo.edu (Alan Wm Paeth) (06/26/89)
>I am look for any and all algorithms relating to rotating a bitmap an >aribtrary amount. Efficiency and accuracy (minimal distortion) are, >of course, important considerations. An English or pseudo-code >description would be fine, but any high level language implementation >would do nicely. Pointers to books and/or articles on the subject >are also welcome. If rotation with scale invariance is required, then three simple image skewing passes suffice. Each pass shears (like a deck of cards) pixels along a scan line or column. Unlike the 2-pass approach, no potential degradation through pixel (re)scaling is occurs, making a fast inner loop, but disallowing general image warping. Rotations of up to 90-degrees are possible for pixel skews of up to one unit on consecutive scanlines; in practice one normally limits to 45-degrees and takes advantage of 8-fold pixel symmetry. Anti-alising is done for fractional pixel skews easily (read the paper). Here is pseudocode from: Paeth, A. W. ``A Fast Algorithm for General Raster Rotation'' PROCEEDINGS, Graphics Interface '86 Vancouver, B.C. May 26-30, 1986 ------------------------------------ IMPLEMENTATION .PP Scan line shearing is approximated by a blending of adjacent pixels. In the following code segment, the ``pixmult'' function returns a pixel scaled by a value $skewf$, where $0 <= skewf < 1$, is a constant parameter for all ``width'' passes through the inner-most loop: .sp .LP .ft CW PROCEDURE xshear(shear, width, height) FOR y := 0 TO height-1 DO skew := shear * (y+0.5); skewi := floor(skew); skewf := frac(skew); oleft := 0; FOR x := 0 TO width-1 DO pixel := P(width-x, y); left := pixmult(pixel, skewf); /* pixel - left = right */ pixel := pixel - left + oleft; P(width-x+skewi, y) := pixel; oleft := left; OD P(skewi, y) := oleft; OD .sp ----- The whole technique phrases the rotation question as a system of 2x2 matrices. Ironically, the earliest reference I can find for decomposition of rotation matrices into unit-determinant shear matrices is due C.F. Gauss. Ironically, he was working on a unified approach to a major problem in Geometric Optics: better ray tracing! /Alan Paeth Computer Graphics Laboratory University of Waterloo