| /*====================================================================* |
| - Copyright (C) 2001 Leptonica. All rights reserved. |
| - This software is distributed in the hope that it will be |
| - useful, but with NO WARRANTY OF ANY KIND. |
| - No author or distributor accepts responsibility to anyone for the |
| - consequences of using this software, or for whether it serves any |
| - particular purpose or works at all, unless he or she says so in |
| - writing. Everyone is granted permission to copy, modify and |
| - redistribute this source code, for commercial or non-commercial |
| - purposes, with the following restrictions: (1) the origin of this |
| - source code must not be misrepresented; (2) modified versions must |
| - be plainly marked as such; and (3) this notice may not be removed |
| - or altered from any source or modified source distribution. |
| *====================================================================*/ |
| |
| /* |
| * rotateshear.c |
| * |
| * Shear rotation about arbitrary point using 2 and 3 shears |
| * |
| * PIX *pixRotateShear() |
| * PIX *pixRotate2Shear() |
| * PIX *pixRotate3Shear() |
| * |
| * Shear rotation in-place about arbitrary point using 3 shears |
| * l_int32 pixRotateShearIP() |
| * |
| * Shear rotation around the image center |
| * PIX *pixRotateShearCenter() (2 or 3 shears) |
| * l_int32 pixRotateShearCenterIP() (3 shears) |
| * |
| * Rotation is measured in radians; clockwise rotations are positive. |
| * |
| * Rotation by shear works on images of any depth, |
| * including 8 bpp color paletted images and 24 bpp |
| * rgb images. It works by translating each src pixel |
| * value to the appropriate pixel in the rotated dest. |
| * For 8 bpp grayscale images, it is about 10-15x faster |
| * than rotation by area-mapping. |
| * |
| * This speed and flexibility comes at the following cost, |
| * relative to area-mapped rotation: |
| * |
| * - Jaggies are created on edges of straight lines |
| * |
| * - For large angles, where you must use 3 shears, |
| * there is some extra clipping from the shears. |
| * |
| * For small angles, typically less than 0.05 radians, |
| * rotation can be done with 2 orthogonal shears. |
| * Two such continuous shears (as opposed to the discrete |
| * shears on a pixel lattice that we have here) give |
| * a rotated image that has a distortion in the lengths |
| * of the two rotated and still-perpendicular axes. The |
| * length/width ratio changes by a fraction |
| * |
| * 0.5 * (angle)**2 |
| * |
| * For an angle of 0.05 radians, this is about 1 part in |
| * a thousand. This distortion is absent when you use |
| * 3 continuous shears with the correct angles (see below). |
| * |
| * Of course, the image is on a discrete pixel lattice. |
| * Rotation by shear gives an approximation to a continuous |
| * rotation, leaving pixel jaggies at sharp boundaries. |
| * For very small rotations, rotating from a corner gives |
| * better sensitivity than rotating from the image center. |
| * Here's why. Define the shear "center" to be the line such |
| * that the image is sheared in opposite directions on |
| * each side of and parallel to the line. For small |
| * rotations there is a "dead space" on each side of the |
| * shear center of width equal to half the shear angle, |
| * in radians. Thus, when the image is sheared about the center, |
| * the dead space width equals the shear angle, but when |
| * the image is sheared from a corner, the dead space |
| * width is only half the shear angle. |
| * |
| * All horizontal and vertical shears are implemented by |
| * rasterop. The in-place rotation uses special in-place |
| * shears that copy rows sideways or columns vertically |
| * without buffering, and then rewrite old pixels that are |
| * no longer covered by sheared pixels. For that rewriting, |
| * you have the choice of using white or black pixels. |
| * (Note that this may give undesirable results for colormapped |
| * images, where the white and black values are arbitrary |
| * indexes into the colormap, and may not even exist.) |
| * |
| * Rotation by shear is fast and depth-independent. However, it |
| * does not work well for large rotation angles. In fact, for |
| * rotation angles greater than about 7 degrees, more pixels are |
| * lost at the edges than when using pixRotationBySampling(), which |
| * only loses pixels because they are rotated out of the image. |
| * For large rotations, use pixRotationBySampling() or, for |
| * more accuracy when d > 1 bpp, pixRotateAM(). |
| * |
| * For small angles, when comparing the quality of rotation by |
| * sampling and by shear, you can see that rotation by sampling |
| * is slightly more accurate. However, the difference in |
| * accuracy of rotation by sampling when compared to 3-shear and |
| * (for angles less than 2 degrees, when compared to 2-shear) is |
| * less than 1 pixel at any point. For very small angles, rotation by |
| * sampling is slower than rotation by shear. The speed difference |
| * depends on the pixel depth and the rotation angle. Rotation |
| * by shear is very fast for small angles and for small depth (esp. 1 bpp). |
| * Rotation by sampling speed is independent of angle and relatively |
| * more efficient for 8 and 32 bpp images. Here are some timings |
| * for the ratio of rotation times: (time for sampling)/ (time for shear) |
| * |
| * depth (bpp) ratio (2 deg) ratio (10 deg) |
| * ----------------------------------------------------- |
| * 1 25 6 |
| * 8 5 2.6 |
| * 32 1.6 1.0 |
| * |
| * Consequently, for small angles and low bit depth, use rotation by shear. |
| * For large angles or large bit depth, use rotation by sampling. |
| * |
| * There has been some work on what is called a "quasishear |
| * rotation" ("The Quasi-Shear Rotation, Eric Andres, |
| * DGCI 1996, pp. 307-314). I believe they use a 3-shear |
| * approximation to the continuous rotation, exactly as |
| * we do here. The approximation is due to being on |
| * a square pixel lattice. They also use integers to specify |
| * the rotation angle and center offset, but that makes |
| * little sense on a machine where you have a few GFLOPS |
| * and only a few hundred floating point operations to do (!) |
| * They also allow subpixel specification of the center of |
| * rotation, which I haven't bothered with, and claim that |
| * better results are possible if each of the 4 quadrants is |
| * handled separately. |
| * |
| * But the bottom line is that for binary images, the quality |
| * of the simple 3-shear rotation is about as good as you can do, |
| * visually, without dithering the result. The effect of dither |
| * is to break up the horizontal and vertical shear lines. |
| * It's a bit tricky to dither with block shears -- you have to |
| * dither the pixels on the block boundaries! |
| */ |
| |
| #include <stdio.h> |
| #include <string.h> |
| #include <stdlib.h> |
| #include <math.h> |
| #include "allheaders.h" |
| |
| static const l_float32 VERY_SMALL_ANGLE = 0.001; /* radians; ~0.06 degrees */ |
| static const l_float32 MAX_2_SHEAR_ANGLE = 0.05; /* radians; ~3 degrees */ |
| |
| |
| /*------------------------------------------------------------------* |
| * Rotations about an arbitrary point * |
| *------------------------------------------------------------------*/ |
| /*! |
| * pixRotateShear() |
| * |
| * Input: pixs |
| * xcen (x value for which there is no horizontal shear) |
| * ycen (y value for which there is no vertical shear) |
| * angle (radians) |
| * incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK); |
| * Return: pixd, or null on error. |
| * |
| * Notes: |
| * (1) This rotates an image about the given point, using |
| * either 2 or 3 shears. |
| * (2) A positive angle gives a clockwise rotation. |
| * (3) This brings in 'incolor' pixels from outside the image. |
| */ |
| PIX * |
| pixRotateShear(PIX *pixs, |
| l_int32 xcen, |
| l_int32 ycen, |
| l_float32 angle, |
| l_int32 incolor) |
| { |
| PROCNAME("pixRotateShear"); |
| |
| if (!pixs) |
| return (PIX *)(PIX *)ERROR_PTR("pixs not defined", procName, NULL); |
| if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK) |
| return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", procName, NULL); |
| |
| if (L_ABS(angle) < VERY_SMALL_ANGLE) |
| return pixClone(pixs); |
| |
| if (L_ABS(angle) <= MAX_2_SHEAR_ANGLE) |
| return pixRotate2Shear(pixs, xcen, ycen, angle, incolor); |
| else |
| return pixRotate3Shear(pixs, xcen, ycen, angle, incolor); |
| |
| } |
| |
| |
| /*! |
| * pixRotate2Shear() |
| * |
| * Input: pixs |
| * xcen, ycen (center of rotation) |
| * angle (radians) |
| * incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK); |
| * Return: pixd, or null on error. |
| * |
| * Notes: |
| * (1) This rotates the image about the given point, |
| * using the 2-shear method. It should only |
| * be used for angles smaller than MAX_2_SHEAR_ANGLE. |
| * (2) A positive angle gives a clockwise rotation. |
| * (3) 2-shear rotation by a specified angle is equivalent |
| * to the sequential transformations |
| * x' = x + tan(angle) * (y - ycen) for x-shear |
| * y' = y + tan(angle) * (x - xcen) for y-shear |
| * (4) Computation of tan(angle) is performed within the shear operation. |
| * (5) This brings in 'incolor' pixels from outside the image. |
| */ |
| PIX * |
| pixRotate2Shear(PIX *pixs, |
| l_int32 xcen, |
| l_int32 ycen, |
| l_float32 angle, |
| l_int32 incolor) |
| { |
| PIX *pixt, *pixd; |
| |
| PROCNAME("pixRotate2Shear"); |
| |
| if (!pixs) |
| return (PIX *)ERROR_PTR("pixs not defined", procName, NULL); |
| if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK) |
| return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", procName, NULL); |
| |
| if (L_ABS(angle) < VERY_SMALL_ANGLE) |
| return pixClone(pixs); |
| |
| if ((pixt = pixHShear(NULL, pixs, ycen, angle, incolor)) == NULL) |
| return (PIX *)ERROR_PTR("pixt not made", procName, NULL); |
| if ((pixd = pixVShear(NULL, pixt, xcen, angle, incolor)) == NULL) |
| return (PIX *)ERROR_PTR("pixd not made", procName, NULL); |
| pixDestroy(&pixt); |
| |
| return pixd; |
| } |
| |
| |
| /*! |
| * pixRotate3Shear() |
| * |
| * Input: pixs |
| * xcen, ycen (center of rotation) |
| * angle (radians) |
| * incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK); |
| * Return: pixd, or null on error. |
| * |
| * Notes: |
| * (1) This rotates the image about the image center, |
| * using the 3-shear method. It can be used for any angle, and |
| * should be used for angles larger than MAX_2_SHEAR_ANGLE. |
| * (2) A positive angle gives a clockwise rotation. |
| * (3) 3-shear rotation by a specified angle is equivalent |
| * to the sequential transformations |
| * y' = y + tan(angle/2) * (x - xcen) for first y-shear |
| * x' = x + sin(angle) * (y - ycen) for x-shear |
| * y' = y + tan(angle/2) * (x - xcen) for second y-shear |
| * (4) Computation of tan(angle) is performed in the shear operations. |
| * (5) This brings in 'incolor' pixels from outside the image. |
| * (6) The algorithm was published by Alan Paeth: "A Fast Algorithm |
| * for General Raster Rotation," Graphics Interface '86, |
| * pp. 77-81, May 1986. A description of the method, along with |
| * an implementation, can be found in Graphics Gems, p. 179, |
| * edited by Andrew Glassner, published by Academic Press, 1990. |
| */ |
| PIX * |
| pixRotate3Shear(PIX *pixs, |
| l_int32 xcen, |
| l_int32 ycen, |
| l_float32 angle, |
| l_int32 incolor) |
| { |
| l_float32 hangle; |
| PIX *pixt, *pixd; |
| |
| PROCNAME("pixRotate3Shear"); |
| |
| if (!pixs) |
| return (PIX *)ERROR_PTR("pixs not defined", procName, NULL); |
| if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK) |
| return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", procName, NULL); |
| |
| if (L_ABS(angle) < VERY_SMALL_ANGLE) |
| return pixClone(pixs); |
| |
| hangle = atan(sin(angle)); |
| if ((pixd = pixVShear(NULL, pixs, xcen, angle / 2., incolor)) == NULL) |
| return (PIX *)ERROR_PTR("pixd not made", procName, NULL); |
| if ((pixt = pixHShear(NULL, pixd, ycen, hangle, incolor)) == NULL) |
| return (PIX *)ERROR_PTR("pixt not made", procName, NULL); |
| pixVShear(pixd, pixt, xcen, angle / 2., incolor); |
| pixDestroy(&pixt); |
| |
| return pixd; |
| } |
| |
| |
| /*------------------------------------------------------------------* |
| * Rotations in-place about an arbitrary point * |
| *------------------------------------------------------------------*/ |
| /*! |
| * pixRotateShearIP() |
| * |
| * Input: pixs (any depth; not colormapped) |
| * xcen, ycen (center of rotation) |
| * angle (radians) |
| * incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK) |
| * Return: 0 if OK; 1 on error |
| * |
| * Notes: |
| * (1) This does an in-place rotation of the image |
| * about the image center, using the 3-shear method. |
| * (2) A positive angle gives a clockwise rotation. |
| * (3) 3-shear rotation by a specified angle is equivalent |
| * to the sequential transformations |
| * y' = y + tan(angle/2) * (x - xcen) for first y-shear |
| * x' = x + sin(angle) * (y - ycen) for x-shear |
| * y' = y + tan(angle/2) * (x - xcen) for second y-shear |
| * (4) Computation of tan(angle) is performed in the shear operations. |
| * (5) This brings in 'incolor' pixels from outside the image. |
| * (6) The pix cannot be colormapped, because the in-place operation |
| * only blits in 0 or 1 bits, not an arbitrary colormap index. |
| */ |
| l_int32 |
| pixRotateShearIP(PIX *pixs, |
| l_int32 xcen, |
| l_int32 ycen, |
| l_float32 angle, |
| l_int32 incolor) |
| { |
| l_float32 hangle; |
| |
| PROCNAME("pixRotateShearIP"); |
| |
| if (!pixs) |
| return ERROR_INT("pixs not defined", procName, 1); |
| if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK) |
| return ERROR_INT("invalid value for incolor", procName, 1); |
| if (pixGetColormap(pixs) != NULL) |
| return ERROR_INT("pixs is colormapped", procName, 1); |
| |
| if (angle == 0.0) |
| return 0; |
| |
| hangle = atan(sin(angle)); |
| pixHShearIP(pixs, ycen, angle / 2., incolor); |
| pixVShearIP(pixs, xcen, hangle, incolor); |
| pixHShearIP(pixs, ycen, angle / 2., incolor); |
| |
| return 0; |
| } |
| |
| |
| /*------------------------------------------------------------------* |
| * Rotations about the image center * |
| *------------------------------------------------------------------*/ |
| /*! |
| * pixRotateShearCenter() |
| * |
| * Input: pixs |
| * angle (radians) |
| * incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK) |
| * Return: pixd, or null on error |
| */ |
| PIX * |
| pixRotateShearCenter(PIX *pixs, |
| l_float32 angle, |
| l_int32 incolor) |
| { |
| PROCNAME("pixRotateShearCenter"); |
| |
| if (!pixs) |
| return (PIX *)ERROR_PTR("pixs not defined", procName, NULL); |
| |
| return pixRotateShear(pixs, pixGetWidth(pixs) / 2, |
| pixGetHeight(pixs) / 2, angle, incolor); |
| } |
| |
| |
| /*! |
| * pixRotateShearCenterIP() |
| * |
| * Input: pixs |
| * angle (radians) |
| * incolor (L_BRING_IN_WHITE, L_BRING_IN_BLACK) |
| * Return: 0 if OK, 1 on error |
| */ |
| l_int32 |
| pixRotateShearCenterIP(PIX *pixs, |
| l_float32 angle, |
| l_int32 incolor) |
| { |
| PROCNAME("pixRotateShearCenterIP"); |
| |
| if (!pixs) |
| return ERROR_INT("pixs not defined", procName, 1); |
| |
| return pixRotateShearIP(pixs, pixGetWidth(pixs) / 2, |
| pixGetHeight(pixs) / 2, angle, incolor); |
| } |
| |
