/*====================================================================*
- 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);
}