Leptonica 1.68
C Image Processing Library

rotateshear.c

Go to the documentation of this file.
00001 /*====================================================================*
00002  -  Copyright (C) 2001 Leptonica.  All rights reserved.
00003  -  This software is distributed in the hope that it will be
00004  -  useful, but with NO WARRANTY OF ANY KIND.
00005  -  No author or distributor accepts responsibility to anyone for the
00006  -  consequences of using this software, or for whether it serves any
00007  -  particular purpose or works at all, unless he or she says so in
00008  -  writing.  Everyone is granted permission to copy, modify and
00009  -  redistribute this source code, for commercial or non-commercial
00010  -  purposes, with the following restrictions: (1) the origin of this
00011  -  source code must not be misrepresented; (2) modified versions must
00012  -  be plainly marked as such; and (3) this notice may not be removed
00013  -  or altered from any source or modified source distribution.
00014  *====================================================================*/
00015 
00016 /*
00017  *  rotateshear.c
00018  *
00019  *      Shear rotation about arbitrary point using 2 and 3 shears
00020  *
00021  *              PIX      *pixRotateShear()
00022  *              PIX      *pixRotate2Shear()
00023  *              PIX      *pixRotate3Shear()
00024  *
00025  *      Shear rotation in-place about arbitrary point using 3 shears
00026  *              l_int32   pixRotateShearIP()
00027  *
00028  *      Shear rotation around the image center
00029  *              PIX      *pixRotateShearCenter()    (2 or 3 shears)
00030  *              l_int32   pixRotateShearCenterIP()  (3 shears)
00031  *
00032  *  Rotation is measured in radians; clockwise rotations are positive.
00033  *
00034  *  Rotation by shear works on images of any depth, 
00035  *  including 8 bpp color paletted images and 32 bpp
00036  *  rgb images.  It works by translating each src pixel
00037  *  value to the appropriate pixel in the rotated dest.
00038  *  For 8 bpp grayscale images, it is about 10-15x faster
00039  *  than rotation by area-mapping.
00040  *
00041  *  This speed and flexibility comes at the following cost,
00042  *  relative to area-mapped rotation:
00043  *
00044  *    -  Jaggies are created on edges of straight lines
00045  *
00046  *    -  For large angles, where you must use 3 shears,
00047  *       there is some extra clipping from the shears.
00048  *
00049  *  For small angles, typically less than 0.05 radians,
00050  *  rotation can be done with 2 orthogonal shears.
00051  *  Two such continuous shears (as opposed to the discrete
00052  *  shears on a pixel lattice that we have here) give
00053  *  a rotated image that has a distortion in the lengths
00054  *  of the two rotated and still-perpendicular axes.  The
00055  *  length/width ratio changes by a fraction 
00056  *
00057  *       0.5 * (angle)**2
00058  *
00059  *  For an angle of 0.05 radians, this is about 1 part in
00060  *  a thousand.  This distortion is absent when you use
00061  *  3 continuous shears with the correct angles (see below).
00062  *
00063  *  Of course, the image is on a discrete pixel lattice.
00064  *  Rotation by shear gives an approximation to a continuous
00065  *  rotation, leaving pixel jaggies at sharp boundaries.
00066  *  For very small rotations, rotating from a corner gives
00067  *  better sensitivity than rotating from the image center.
00068  *  Here's why.  Define the shear "center" to be the line such
00069  *  that the image is sheared in opposite directions on
00070  *  each side of and parallel to the line.  For small
00071  *  rotations there is a "dead space" on each side of the
00072  *  shear center of width equal to half the shear angle,
00073  *  in radians.  Thus, when the image is sheared about the center,
00074  *  the dead space width equals the shear angle, but when
00075  *  the image is sheared from a corner, the dead space
00076  *  width is only half the shear angle.
00077  *
00078  *  All horizontal and vertical shears are implemented by
00079  *  rasterop.  The in-place rotation uses special in-place
00080  *  shears that copy rows sideways or columns vertically
00081  *  without buffering, and then rewrite old pixels that are
00082  *  no longer covered by sheared pixels.  For that rewriting,
00083  *  you have the choice of using white or black pixels.
00084  *  (Note that this may give undesirable results for colormapped
00085  *  images, where the white and black values are arbitrary
00086  *  indexes into the colormap, and may not even exist.)
00087  *
00088  *  Rotation by shear is fast and depth-independent.  However, it
00089  *  does not work well for large rotation angles.  In fact, for
00090  *  rotation angles greater than about 7 degrees, more pixels are
00091  *  lost at the edges than when using pixRotationBySampling(), which
00092  *  only loses pixels because they are rotated out of the image. 
00093  *  For large rotations, use pixRotationBySampling() or, for
00094  *  more accuracy when d > 1 bpp, pixRotateAM().
00095  *
00096  *  For small angles, when comparing the quality of rotation by
00097  *  sampling and by shear, you can see that rotation by sampling
00098  *  is slightly more accurate.  However, the difference in
00099  *  accuracy of rotation by sampling when compared to 3-shear and
00100  *  (for angles less than 2 degrees, when compared to 2-shear) is
00101  *  less than 1 pixel at any point.  For very small angles, rotation by
00102  *  sampling is slower than rotation by shear.  The speed difference
00103  *  depends on the pixel depth and the rotation angle.  Rotation
00104  *  by shear is very fast for small angles and for small depth (esp. 1 bpp).
00105  *  Rotation by sampling speed is independent of angle and relatively
00106  *  more efficient for 8 and 32 bpp images.  Here are some timings
00107  *  for the ratio of rotation times: (time for sampling)/ (time for shear)
00108   *
00109  *       depth (bpp)       ratio (2 deg)       ratio (10 deg)
00110  *       -----------------------------------------------------
00111  *          1                  25                  6
00112  *          8                   5                  2.6
00113  *          32                  1.6                1.0
00114  *
00115  *  Consequently, for small angles and low bit depth, use rotation by shear.
00116  *  For large angles or large bit depth, use rotation by sampling.
00117  *
00118  *  There has been some work on what is called a "quasishear
00119  *  rotation" ("The Quasi-Shear Rotation, Eric Andres,
00120  *  DGCI 1996, pp. 307-314).  I believe they use a 3-shear
00121  *  approximation to the continuous rotation, exactly as
00122  *  we do here.  The approximation is due to being on
00123  *  a square pixel lattice.  They also use integers to specify
00124  *  the rotation angle and center offset, but that makes
00125  *  little sense on a machine where you have a few GFLOPS
00126  *  and only a few hundred floating point operations to do (!) 
00127  *  They also allow subpixel specification of the center of
00128  *  rotation, which I haven't bothered with, and claim that
00129  *  better results are possible if each of the 4 quadrants is
00130  *  handled separately.
00131  * 
00132  *  But the bottom line is that for binary images, the quality
00133  *  of the simple 3-shear rotation is about as good as you can do,
00134  *  visually, without dithering the result.  The effect of dither
00135  *  is to break up the horizontal and vertical shear lines.
00136  *  It's a bit tricky to dither with block shears -- you have to
00137  *  dither the pixels on the block boundaries!
00138  */
00139 
00140 #include <stdio.h>
00141 #include <string.h>
00142 #include <stdlib.h>
00143 #include <math.h>
00144 #include "allheaders.h"
00145 
00146 static const l_float32  VERY_SMALL_ANGLE = 0.001;  /* radians; ~0.06 degrees */
00147 static const l_float32  MAX_2_SHEAR_ANGLE = 0.05;  /* radians; ~3 degrees    */
00148 
00149 
00150 /*------------------------------------------------------------------*
00151  *                Rotations about an arbitrary point                *
00152  *------------------------------------------------------------------*/
00153 /*!
00154  *  pixRotateShear()
00155  *
00156  *      Input:  pixs
00157  *              xcen (x value for which there is no horizontal shear)
00158  *              ycen (y value for which there is no vertical shear)
00159  *              angle (radians)
00160  *              incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK);
00161  *      Return: pixd, or null on error.
00162  *
00163  *  Notes:
00164  *      (1) This rotates an image about the given point, using
00165  *          either 2 or 3 shears.
00166  *      (2) A positive angle gives a clockwise rotation.
00167  *      (3) This brings in 'incolor' pixels from outside the image.
00168  */
00169 PIX *
00170 pixRotateShear(PIX       *pixs,
00171                l_int32    xcen,
00172                l_int32    ycen,
00173                l_float32  angle,
00174                l_int32    incolor)
00175 {
00176     PROCNAME("pixRotateShear");
00177 
00178     if (!pixs)
00179         return (PIX *)(PIX *)ERROR_PTR("pixs not defined", procName, NULL);
00180     if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
00181         return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", procName, NULL);
00182 
00183     if (L_ABS(angle) < VERY_SMALL_ANGLE)
00184         return pixClone(pixs);
00185 
00186     if (L_ABS(angle) <= MAX_2_SHEAR_ANGLE)
00187         return pixRotate2Shear(pixs, xcen, ycen, angle, incolor);
00188     else
00189         return pixRotate3Shear(pixs, xcen, ycen, angle, incolor);
00190 
00191 }
00192 
00193 
00194 /*!
00195  *  pixRotate2Shear()
00196  *
00197  *      Input:  pixs
00198  *              xcen, ycen (center of rotation)
00199  *              angle (radians)
00200  *              incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK);
00201  *      Return: pixd, or null on error.
00202  *
00203  *  Notes:
00204  *      (1) This rotates the image about the given point,
00205  *          using the 2-shear method.  It should only
00206  *          be used for angles smaller than MAX_2_SHEAR_ANGLE.
00207  *      (2) A positive angle gives a clockwise rotation.
00208  *      (3) 2-shear rotation by a specified angle is equivalent
00209  *          to the sequential transformations
00210  *             x' = x + tan(angle) * (y - ycen)     for x-shear
00211  *             y' = y + tan(angle) * (x - xcen)     for y-shear
00212  *      (4) Computation of tan(angle) is performed within the shear operation.
00213  *      (5) This brings in 'incolor' pixels from outside the image.
00214  */
00215 PIX *
00216 pixRotate2Shear(PIX       *pixs,
00217                 l_int32    xcen,
00218                 l_int32    ycen,
00219                 l_float32  angle,
00220                 l_int32    incolor)
00221 {
00222 PIX  *pixt, *pixd;
00223 
00224     PROCNAME("pixRotate2Shear");
00225 
00226     if (!pixs)
00227         return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
00228     if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
00229         return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", procName, NULL);
00230     
00231     if (L_ABS(angle) < VERY_SMALL_ANGLE)
00232         return pixClone(pixs);
00233 
00234     if ((pixt = pixHShear(NULL, pixs, ycen, angle, incolor)) == NULL)
00235         return (PIX *)ERROR_PTR("pixt not made", procName, NULL);
00236     if ((pixd = pixVShear(NULL, pixt, xcen, angle, incolor)) == NULL)
00237         return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
00238     pixDestroy(&pixt);
00239 
00240     return pixd;
00241 }
00242 
00243 
00244 /*!
00245  *  pixRotate3Shear()
00246  *
00247  *      Input:  pixs
00248  *              xcen, ycen (center of rotation)
00249  *              angle (radians)
00250  *              incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK);
00251  *      Return: pixd, or null on error.
00252  *
00253  *  Notes:
00254  *      (1) This rotates the image about the image center,
00255  *          using the 3-shear method.  It can be used for any angle, and
00256  *          should be used for angles larger than MAX_2_SHEAR_ANGLE.
00257  *      (2) A positive angle gives a clockwise rotation.
00258  *      (3) 3-shear rotation by a specified angle is equivalent
00259  *          to the sequential transformations
00260  *            y' = y + tan(angle/2) * (x - xcen)     for first y-shear
00261  *            x' = x + sin(angle) * (y - ycen)       for x-shear
00262  *            y' = y + tan(angle/2) * (x - xcen)     for second y-shear
00263  *      (4) Computation of tan(angle) is performed in the shear operations.
00264  *      (5) This brings in 'incolor' pixels from outside the image.
00265  *      (6) The algorithm was published by Alan Paeth: "A Fast Algorithm
00266  *          for General Raster Rotation," Graphics Interface '86,
00267  *          pp. 77-81, May 1986.  A description of the method, along with
00268  *          an implementation, can be found in Graphics Gems, p. 179,
00269  *          edited by Andrew Glassner, published by Academic Press, 1990.
00270  */
00271 PIX *
00272 pixRotate3Shear(PIX       *pixs,
00273                 l_int32    xcen,
00274                 l_int32    ycen,
00275                 l_float32  angle,
00276                 l_int32    incolor)
00277 {
00278 l_float32  hangle;
00279 PIX              *pixt, *pixd;
00280 
00281     PROCNAME("pixRotate3Shear");
00282 
00283     if (!pixs)
00284         return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
00285     if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
00286         return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", procName, NULL);
00287     
00288     if (L_ABS(angle) < VERY_SMALL_ANGLE)
00289         return pixClone(pixs);
00290 
00291     hangle = atan(sin(angle));
00292     if ((pixd = pixVShear(NULL, pixs, xcen, angle / 2., incolor)) == NULL)
00293         return (PIX *)ERROR_PTR("pixd not made", procName, NULL);
00294     if ((pixt = pixHShear(NULL, pixd, ycen, hangle, incolor)) == NULL)
00295         return (PIX *)ERROR_PTR("pixt not made", procName, NULL);
00296     pixVShear(pixd, pixt, xcen, angle / 2., incolor);
00297     pixDestroy(&pixt);
00298 
00299     return pixd;
00300 }
00301 
00302 
00303 /*------------------------------------------------------------------*
00304  *             Rotations in-place about an arbitrary point          *
00305  *------------------------------------------------------------------*/
00306 /*!
00307  *  pixRotateShearIP()
00308  *
00309  *      Input:  pixs (any depth; not colormapped)
00310  *              xcen, ycen (center of rotation)
00311  *              angle (radians)
00312  *              incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK)
00313  *      Return: 0 if OK; 1 on error
00314  *
00315  *  Notes:
00316  *      (1) This does an in-place rotation of the image
00317  *          about the image center, using the 3-shear method.
00318  *      (2) A positive angle gives a clockwise rotation.
00319  *      (3) 3-shear rotation by a specified angle is equivalent
00320  *          to the sequential transformations
00321  *            y' = y + tan(angle/2) * (x - xcen)      for first y-shear
00322  *            x' = x + sin(angle) * (y - ycen)        for x-shear
00323  *            y' = y + tan(angle/2) * (x - xcen)      for second y-shear
00324  *      (4) Computation of tan(angle) is performed in the shear operations.
00325  *      (5) This brings in 'incolor' pixels from outside the image.
00326  *      (6) The pix cannot be colormapped, because the in-place operation
00327  *          only blits in 0 or 1 bits, not an arbitrary colormap index.
00328  */
00329 l_int32
00330 pixRotateShearIP(PIX       *pixs,
00331                  l_int32    xcen,
00332                  l_int32    ycen,
00333                  l_float32  angle,
00334                  l_int32    incolor)
00335 {
00336 l_float32  hangle;
00337 
00338     PROCNAME("pixRotateShearIP");
00339 
00340     if (!pixs)
00341         return ERROR_INT("pixs not defined", procName, 1);
00342     if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
00343         return ERROR_INT("invalid value for incolor", procName, 1);
00344     if (pixGetColormap(pixs) != NULL)
00345         return ERROR_INT("pixs is colormapped", procName, 1);
00346 
00347     if (angle == 0.0)
00348         return 0;
00349     
00350     hangle = atan(sin(angle));
00351     pixHShearIP(pixs, ycen, angle / 2., incolor);
00352     pixVShearIP(pixs, xcen, hangle, incolor);
00353     pixHShearIP(pixs, ycen, angle / 2., incolor);
00354 
00355     return 0;
00356 }
00357 
00358 
00359 /*------------------------------------------------------------------*
00360  *                    Rotations about the image center              *
00361  *------------------------------------------------------------------*/
00362 /*!
00363  *  pixRotateShearCenter()
00364  *
00365  *      Input:  pixs
00366  *              angle (radians)
00367  *              incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK)
00368  *      Return: pixd, or null on error
00369  */
00370 PIX *
00371 pixRotateShearCenter(PIX       *pixs,
00372                      l_float32  angle,
00373                      l_int32    incolor)
00374 {
00375     PROCNAME("pixRotateShearCenter");
00376 
00377     if (!pixs)
00378         return (PIX *)ERROR_PTR("pixs not defined", procName, NULL);
00379     
00380     return pixRotateShear(pixs, pixGetWidth(pixs) / 2,
00381                           pixGetHeight(pixs) / 2, angle, incolor);
00382 }
00383 
00384 
00385 /*!
00386  *  pixRotateShearCenterIP()
00387  *
00388  *      Input:  pixs
00389  *              angle (radians)
00390  *              incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK)
00391  *      Return: 0 if OK, 1 on error
00392  */
00393 l_int32
00394 pixRotateShearCenterIP(PIX       *pixs,
00395                        l_float32  angle,
00396                        l_int32    incolor)
00397 {
00398     PROCNAME("pixRotateShearCenterIP");
00399 
00400     if (!pixs)
00401         return ERROR_INT("pixs not defined", procName, 1);
00402     
00403     return pixRotateShearIP(pixs, pixGetWidth(pixs) / 2,
00404                             pixGetHeight(pixs) / 2, angle, incolor);
00405 }
00406 
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines