Coverage Report

Created: 2024-06-18 06:05

/src/leptonica/src/rotateshear.c
Line
Count
Source (jump to first uncovered line)
1
/*====================================================================*
2
 -  Copyright (C) 2001 Leptonica.  All rights reserved.
3
 -
4
 -  Redistribution and use in source and binary forms, with or without
5
 -  modification, are permitted provided that the following conditions
6
 -  are met:
7
 -  1. Redistributions of source code must retain the above copyright
8
 -     notice, this list of conditions and the following disclaimer.
9
 -  2. Redistributions in binary form must reproduce the above
10
 -     copyright notice, this list of conditions and the following
11
 -     disclaimer in the documentation and/or other materials
12
 -     provided with the distribution.
13
 -
14
 -  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15
 -  ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16
 -  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17
 -  A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL ANY
18
 -  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19
 -  EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20
 -  PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21
 -  PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22
 -  OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23
 -  NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24
 -  SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25
 *====================================================================*/
26
27
/*!
28
 * \file rotateshear.c
29
 * <pre>
30
 *
31
 *      Shear rotation about arbitrary point using 2 and 3 shears
32
 *
33
 *              PIX      *pixRotateShear()
34
 *              PIX      *pixRotate2Shear()
35
 *              PIX      *pixRotate3Shear()
36
 *
37
 *      Shear rotation in-place about arbitrary point using 3 shears
38
 *              l_int32   pixRotateShearIP()
39
 *
40
 *      Shear rotation around the image center
41
 *              PIX      *pixRotateShearCenter()    (2 or 3 shears)
42
 *              l_int32   pixRotateShearCenterIP()  (3 shears)
43
 *
44
 *  Rotation is measured in radians; clockwise rotations are positive.
45
 *
46
 *  Rotation by shear works on images of any depth,
47
 *  including 8 bpp color paletted images and 32 bpp
48
 *  rgb images.  It works by translating each src pixel
49
 *  value to the appropriate pixel in the rotated dest.
50
 *  For 8 bpp grayscale images, it is about 10-15x faster
51
 *  than rotation by area-mapping.
52
 *
53
 *  This speed and flexibility comes at the following cost,
54
 *  relative to area-mapped rotation:
55
 *
56
 *    ~  Jaggies are created on edges of straight lines
57
 *
58
 *    ~  For large angles, where you must use 3 shears,
59
 *       there is some extra clipping from the shears.
60
 *
61
 *  For small angles, typically less than 0.05 radians,
62
 *  rotation can be done with 2 orthogonal shears.
63
 *  Two such continuous shears (as opposed to the discrete
64
 *  shears on a pixel lattice that we have here) give
65
 *  a rotated image that has a distortion in the lengths
66
 *  of the two rotated and still-perpendicular axes.  The
67
 *  length/width ratio changes by a fraction
68
 *
69
 *       0.5 * (angle)**2
70
 *
71
 *  For an angle of 0.05 radians, this is about 1 part in
72
 *  a thousand.  This distortion is absent when you use
73
 *  3 continuous shears with the correct angles (see below).
74
 *
75
 *  Of course, the image is on a discrete pixel lattice.
76
 *  Rotation by shear gives an approximation to a continuous
77
 *  rotation, leaving pixel jaggies at sharp boundaries.
78
 *  For very small rotations, rotating from a corner gives
79
 *  better sensitivity than rotating from the image center.
80
 *  Here's why.  Define the shear "center" to be the line such
81
 *  that the image is sheared in opposite directions on
82
 *  each side of and parallel to the line.  For small
83
 *  rotations there is a "dead space" on each side of the
84
 *  shear center of width equal to half the shear angle,
85
 *  in radians.  Thus, when the image is sheared about the center,
86
 *  the dead space width equals the shear angle, but when
87
 *  the image is sheared from a corner, the dead space
88
 *  width is only half the shear angle.
89
 *
90
 *  All horizontal and vertical shears are implemented by
91
 *  rasterop.  The in-place rotation uses special in-place
92
 *  shears that copy rows sideways or columns vertically
93
 *  without buffering, and then rewrite old pixels that are
94
 *  no longer covered by sheared pixels.  For that rewriting,
95
 *  you have the choice of using white or black pixels.
96
 *  When not in-place, the new pix is initialized with white or black
97
 *  pixels by pixSetBlackOrWhite(), which also works for cmapped pix.
98
 *  But for in-place, this initialization is not possible, so
99
 *  in-place shear operations on cmapped pix are not allowed.
100
 *
101
 *  Rotation by shear is fast and depth-independent.  However, it
102
 *  does not work well for large rotation angles.  In fact, for
103
 *  rotation angles greater than about 7 degrees, more pixels are
104
 *  lost at the edges than when using pixRotationBySampling(), which
105
 *  only loses pixels because they are rotated out of the image.
106
 *  For larger rotations, use pixRotationBySampling() or, for
107
 *  more accuracy when d > 1 bpp, pixRotateAM().
108
 *
109
 *  For small angles, when comparing the quality of rotation by
110
 *  sampling and by shear, you can see that rotation by sampling
111
 *  is slightly more accurate.  However, the difference in
112
 *  accuracy of rotation by sampling when compared to 3-shear and
113
 *  (for angles less than 2 degrees, when compared to 2-shear) is
114
 *  less than 1 pixel at any point.  For very small angles, rotation by
115
 *  sampling is much slower than rotation by shear.  The speed difference
116
 *  depends on the pixel depth and the rotation angle.  Rotation
117
 *  by shear is very fast for small angles and for small depth (esp. 1 bpp).
118
 *  Rotation by sampling speed is independent of angle and relatively
119
 *  more efficient for 8 and 32 bpp images.  Here are some timings
120
 *  for the ratio of rotation times: (time for sampling)/ (time for shear)
121
  *
122
 *       depth (bpp)       ratio (2 deg)       ratio (10 deg)
123
 *       -----------------------------------------------------
124
 *          1                  25                  6
125
 *          8                   5                  2.6
126
 *          32                  1.6                1.0
127
 *
128
 *  In summary:
129
 *    * For d == 1 and small angles, use rotation by shear.  By default
130
 *      this will use 2-shear rotations, because 3-shears cause more
131
 *      visible artifacts in straight lines and, for small angles, the
132
 *      distortion in asperity ratio is small.
133
 *    * For d > 1, shear is faster than sampling, which is faster than
134
 *      area mapping.  However, area mapping gives the best results.
135
 *  These results are used in selecting the rotation methods in
136
 *  pixRotateShear().
137
 *
138
 *  There has been some work on what is called a "quasishear
139
 *  rotation" ("The Quasi-Shear Rotation, Eric Andres,
140
 *  DGCI 1996, pp. 307-314).  I believe they use a 3-shear
141
 *  approximation to the continuous rotation, exactly as
142
 *  we do here.  The approximation is due to being on
143
 *  a square pixel lattice.  They also use integers to specify
144
 *  the rotation angle and center offset, but that makes
145
 *  little sense on a machine where you have a few GFLOPS
146
 *  and only a few hundred floating point operations to do (!)
147
 *  They also allow subpixel specification of the center of
148
 *  rotation, which I haven't bothered with, and claim that
149
 *  better results are possible if each of the 4 quadrants is
150
 *  handled separately.
151
 *
152
 *  But the bottom line is that you are going to see shear lines when
153
 *  you rotate 1 bpp images.  Although the 3-shear rotation is
154
 *  mathematically exact in the limit of infinitesimal pixels, artifacts
155
 *  will be evident in real images.  One might imagine using dithering
156
 *  to break up the horizontal and vertical shear lines, but this
157
 *  is hard with block shears, where you need to dither on the block
158
 *  boundaries.  Dithering (by accumulation of 'error') with sampling
159
 *  makes more sense, but I haven't tried to do this.  There is only
160
 *  so much you can do with 1 bpp images!
161
 * </pre>
162
 */
163
164
#ifdef HAVE_CONFIG_H
165
#include <config_auto.h>
166
#endif  /* HAVE_CONFIG_H */
167
168
#include <math.h>
169
#include <string.h>
170
#include "allheaders.h"
171
172
    /* Angle limits:
173
     *     angle < MinAngleToRotate    ==>  clone
174
     *     angle > MaxTwoShearAngle    ==>  warning for 2-angle shears
175
     *     angle > MaxThreeShearAngle  ==>  warning for 3-angle shears
176
     *     angle > MaxShearAngle       ==>  error
177
     */
178
static const l_float32  MinAngleToRotate = 0.001f;   /* radians; ~0.06 deg */
179
static const l_float32  MaxTwoShearAngle = 0.06f;    /* radians; ~3 deg    */
180
static const l_float32  MaxThreeShearAngle = 0.35f;  /* radians; ~20 deg   */
181
static const l_float32  MaxShearAngle = 0.50f;       /* radians; ~29 deg   */
182
183
/*------------------------------------------------------------------*
184
 *                Rotations about an arbitrary point                *
185
 *------------------------------------------------------------------*/
186
/*!
187
 * \brief   pixRotateShear()
188
 *
189
 * \param[in]    pixs     any depth; cmap ok
190
 * \param[in]    xcen     x value for which there is no horizontal shear
191
 * \param[in]    ycen     y value for which there is no vertical shear
192
 * \param[in]    angle    radians
193
 * \param[in]    incolor  L_BRING_IN_WHITE, L_BRING_IN_BLACK;
194
 * \return  pixd, or NULL on error.
195
 *
196
 * <pre>
197
 * Notes:
198
 *      (1) This rotates an image about the given point, using
199
 *          either 2 or 3 shears.
200
 *      (2) A positive angle gives a clockwise rotation.
201
 *      (3) This brings in 'incolor' pixels from outside the image.
202
 *      (4) For rotation angles larger than about 0.35 radians, we issue
203
 *          a warning because you should probably be using another method
204
 *          (either sampling or area mapping)
205
 * </pre>
206
 */
207
PIX *
208
pixRotateShear(PIX       *pixs,
209
               l_int32    xcen,
210
               l_int32    ycen,
211
               l_float32  angle,
212
               l_int32    incolor)
213
0
{
214
0
    if (!pixs)
215
0
        return (PIX *)(PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
216
0
    if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
217
0
        return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", __func__, NULL);
218
219
0
    if (L_ABS(angle) > MaxShearAngle) {
220
0
        L_ERROR("%6.2f radians; too large for shear rotation\n", __func__,
221
0
                L_ABS(angle));
222
0
        return NULL;
223
0
    }
224
0
    if (L_ABS(angle) < MinAngleToRotate)
225
0
        return pixClone(pixs);
226
227
0
    if (L_ABS(angle) <= MaxTwoShearAngle)
228
0
        return pixRotate2Shear(pixs, xcen, ycen, angle, incolor);
229
0
    else
230
0
        return pixRotate3Shear(pixs, xcen, ycen, angle, incolor);
231
0
}
232
233
234
/*!
235
 * \brief   pixRotate2Shear()
236
 *
237
 * \param[in]    pixs         any depth; cmap ok
238
 * \param[in]    xcen, ycen   center of rotation
239
 * \param[in]    angle        radians
240
 * \param[in]    incolor      L_BRING_IN_WHITE, L_BRING_IN_BLACK;
241
 * \return  pixd, or NULL on error.
242
 *
243
 * <pre>
244
 * Notes:
245
 *      (1) This rotates the image about the given point, using the 2-shear
246
 *          method.  It should only be used for angles no larger than
247
 *          MaxTwoShearAngle.  For larger angles, a warning is issued.
248
 *      (2) A positive angle gives a clockwise rotation.
249
 *      (3) 2-shear rotation by a specified angle is equivalent
250
 *          to the sequential transformations
251
 *             x' = x + tan(angle) * (y - ycen)     for x-shear
252
 *             y' = y + tan(angle) * (x - xcen)     for y-shear
253
 *      (4) Computation of tan(angle) is performed within the shear operation.
254
 *      (5) This brings in 'incolor' pixels from outside the image.
255
 *      (6) If the image has an alpha layer, it is rotated separately by
256
 *          two shears.
257
 * </pre>
258
 */
259
PIX *
260
pixRotate2Shear(PIX       *pixs,
261
                l_int32    xcen,
262
                l_int32    ycen,
263
                l_float32  angle,
264
                l_int32    incolor)
265
0
{
266
0
PIX  *pix1, *pix2, *pixd;
267
268
0
    if (!pixs)
269
0
        return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
270
0
    if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
271
0
        return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", __func__, NULL);
272
273
0
    if (L_ABS(angle) > MaxShearAngle) {
274
0
        L_ERROR("%6.2f radians; too large for shear rotation\n", __func__,
275
0
                L_ABS(angle));
276
0
        return NULL;
277
0
    }
278
0
    if (L_ABS(angle) < MinAngleToRotate)
279
0
        return pixClone(pixs);
280
0
    if (L_ABS(angle) > MaxTwoShearAngle)
281
0
        L_WARNING("%6.2f radians; large angle for 2-shear rotation\n",
282
0
                  __func__, L_ABS(angle));
283
284
0
    if ((pix1 = pixHShear(NULL, pixs, ycen, angle, incolor)) == NULL)
285
0
        return (PIX *)ERROR_PTR("pix1 not made", __func__, NULL);
286
0
    pixd = pixVShear(NULL, pix1, xcen, angle, incolor);
287
0
    pixDestroy(&pix1);
288
0
    if (!pixd)
289
0
        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
290
291
0
    if (pixGetDepth(pixs) == 32 && pixGetSpp(pixs) == 4) {
292
0
        pix1 = pixGetRGBComponent(pixs, L_ALPHA_CHANNEL);
293
            /* L_BRING_IN_WHITE brings in opaque for the alpha component */
294
0
        pix2 = pixRotate2Shear(pix1, xcen, ycen, angle, L_BRING_IN_WHITE);
295
0
        pixSetRGBComponent(pixd, pix2, L_ALPHA_CHANNEL);
296
0
        pixDestroy(&pix1);
297
0
        pixDestroy(&pix2);
298
0
    }
299
0
    return pixd;
300
0
}
301
302
303
/*!
304
 * \brief   pixRotate3Shear()
305
 *
306
 * \param[in]    pixs         any depth; cmap ok
307
 * \param[in]    xcen, ycen   center of rotation
308
 * \param[in]    angle        radians
309
 * \param[in]    incolor      L_BRING_IN_WHITE, L_BRING_IN_BLACK;
310
 * \return  pixd, or NULL on error.
311
 *
312
 * <pre>
313
 * Notes:
314
 *      (1) This rotates the image about the given point, using the 3-shear
315
 *          method.  It should only be used for angles smaller than
316
 *          MaxThreeShearAngle.  For larger angles, a warning is issued.
317
 *      (2) A positive angle gives a clockwise rotation.
318
 *      (3) 3-shear rotation by a specified angle is equivalent
319
 *          to the sequential transformations
320
 *            y' = y + tan(angle/2) * (x - xcen)     for first y-shear
321
 *            x' = x + sin(angle) * (y - ycen)       for x-shear
322
 *            y' = y + tan(angle/2) * (x - xcen)     for second y-shear
323
 *      (4) Computation of tan(angle) is performed in the shear operations.
324
 *      (5) This brings in 'incolor' pixels from outside the image.
325
 *      (6) If the image has an alpha layer, it is rotated separately by
326
 *          two shears.
327
 *      (7) The algorithm was published by Alan Paeth: "A Fast Algorithm
328
 *          for General Raster Rotation," Graphics Interface '86,
329
 *          pp. 77-81, May 1986.  A description of the method, along with
330
 *          an implementation, can be found in Graphics Gems, p. 179,
331
 *          edited by Andrew Glassner, published by Academic Press, 1990.
332
 * </pre>
333
 */
334
PIX *
335
pixRotate3Shear(PIX       *pixs,
336
                l_int32    xcen,
337
                l_int32    ycen,
338
                l_float32  angle,
339
                l_int32    incolor)
340
0
{
341
0
l_float32  hangle;
342
0
PIX       *pix1, *pix2, *pixd;
343
344
0
    if (!pixs)
345
0
        return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
346
0
    if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
347
0
        return (PIX *)(PIX *)ERROR_PTR("invalid incolor value", __func__, NULL);
348
349
0
    if (L_ABS(angle) > MaxShearAngle) {
350
0
        L_ERROR("%6.2f radians; too large for shear rotation\n", __func__,
351
0
                L_ABS(angle));
352
0
        return NULL;
353
0
    }
354
0
    if (L_ABS(angle) < MinAngleToRotate)
355
0
        return pixClone(pixs);
356
0
    if (L_ABS(angle) > MaxThreeShearAngle) {
357
0
        L_WARNING("%6.2f radians; large angle for 3-shear rotation\n",
358
0
                  __func__, L_ABS(angle));
359
0
    }
360
361
0
    hangle = atan(sin(angle));
362
0
    if ((pixd = pixVShear(NULL, pixs, xcen, angle / 2.f, incolor)) == NULL)
363
0
        return (PIX *)ERROR_PTR("pixd not made", __func__, NULL);
364
0
    if ((pix1 = pixHShear(NULL, pixd, ycen, hangle, incolor)) == NULL) {
365
0
        pixDestroy(&pixd);
366
0
        return (PIX *)ERROR_PTR("pix1 not made", __func__, NULL);
367
0
    }
368
0
    pixVShear(pixd, pix1, xcen, angle / 2.f, incolor);
369
0
    pixDestroy(&pix1);
370
371
0
    if (pixGetDepth(pixs) == 32 && pixGetSpp(pixs) == 4) {
372
0
        pix1 = pixGetRGBComponent(pixs, L_ALPHA_CHANNEL);
373
            /* L_BRING_IN_WHITE brings in opaque for the alpha component */
374
0
        pix2 = pixRotate3Shear(pix1, xcen, ycen, angle, L_BRING_IN_WHITE);
375
0
        pixSetRGBComponent(pixd, pix2, L_ALPHA_CHANNEL);
376
0
        pixDestroy(&pix1);
377
0
        pixDestroy(&pix2);
378
0
    }
379
0
    return pixd;
380
0
}
381
382
383
/*------------------------------------------------------------------*
384
 *             Rotations in-place about an arbitrary point          *
385
 *------------------------------------------------------------------*/
386
/*!
387
 * \brief   pixRotateShearIP()
388
 *
389
 * \param[in]    pixs         any depth; no cmap
390
 * \param[in]    xcen, ycen   center of rotation
391
 * \param[in]    angle        radians
392
 * \param[in]    incolor      L_BRING_IN_WHITE, L_BRING_IN_BLACK
393
 * \return  0 if OK; 1 on error
394
 *
395
 * <pre>
396
 * Notes:
397
 *      (1) This does an in-place rotation of the image about the
398
 *          specified point, using the 3-shear method.  It should only
399
 *          be used for angles smaller than MaxThreeShearAngle.
400
 *          For larger angles, a warning is issued.
401
 *      (2) A positive angle gives a clockwise rotation.
402
 *      (3) 3-shear rotation by a specified angle is equivalent
403
 *          to the sequential transformations
404
 *            y' = y + tan(angle/2) * (x - xcen)      for first y-shear
405
 *            x' = x + sin(angle) * (y - ycen)        for x-shear
406
 *            y' = y + tan(angle/2) * (x - xcen)      for second y-shear
407
 *      (4) Computation of tan(angle) is performed in the shear operations.
408
 *      (5) This brings in 'incolor' pixels from outside the image.
409
 *      (6) The pix cannot be colormapped, because the in-place operation
410
 *          only blits in 0 or 1 bits, not an arbitrary colormap index.
411
 * </pre>
412
 */
413
l_ok
414
pixRotateShearIP(PIX       *pixs,
415
                 l_int32    xcen,
416
                 l_int32    ycen,
417
                 l_float32  angle,
418
                 l_int32    incolor)
419
0
{
420
0
l_float32  hangle;
421
422
0
    if (!pixs)
423
0
        return ERROR_INT("pixs not defined", __func__, 1);
424
0
    if (incolor != L_BRING_IN_WHITE && incolor != L_BRING_IN_BLACK)
425
0
        return ERROR_INT("invalid value for incolor", __func__, 1);
426
0
    if (pixGetColormap(pixs) != NULL)
427
0
        return ERROR_INT("pixs is colormapped", __func__, 1);
428
429
0
    if (angle == 0.0)
430
0
        return 0;
431
0
    if (L_ABS(angle) > MaxThreeShearAngle) {
432
0
        L_WARNING("%6.2f radians; large angle for in-place 3-shear rotation\n",
433
0
                  __func__, L_ABS(angle));
434
0
    }
435
436
0
    hangle = atan(sin(angle));
437
0
    pixHShearIP(pixs, ycen, angle / 2.f, incolor);
438
0
    pixVShearIP(pixs, xcen, hangle, incolor);
439
0
    pixHShearIP(pixs, ycen, angle / 2.f, incolor);
440
0
    return 0;
441
0
}
442
443
444
/*------------------------------------------------------------------*
445
 *                    Rotations about the image center              *
446
 *------------------------------------------------------------------*/
447
/*!
448
 * \brief   pixRotateShearCenter()
449
 *
450
 * \param[in]    pixs      any depth; cmap ok
451
 * \param[in]    angle     radians
452
 * \param[in]    incolor   L_BRING_IN_WHITE, L_BRING_IN_BLACK
453
 * \return  pixd, or NULL on error
454
 */
455
PIX *
456
pixRotateShearCenter(PIX       *pixs,
457
                     l_float32  angle,
458
                     l_int32    incolor)
459
0
{
460
0
    if (!pixs)
461
0
        return (PIX *)ERROR_PTR("pixs not defined", __func__, NULL);
462
463
0
    return pixRotateShear(pixs, pixGetWidth(pixs) / 2,
464
0
                          pixGetHeight(pixs) / 2, angle, incolor);
465
0
}
466
467
468
/*!
469
 * \brief   pixRotateShearCenterIP()
470
 *
471
 * \param[in]    pixs      any depth; no cmap
472
 * \param[in]    angle     radians
473
 * \param[in]    incolor   L_BRING_IN_WHITE, L_BRING_IN_BLACK
474
 * \return  0 if OK, 1 on error
475
 */
476
l_ok
477
pixRotateShearCenterIP(PIX       *pixs,
478
                       l_float32  angle,
479
                       l_int32    incolor)
480
0
{
481
0
    if (!pixs)
482
0
        return ERROR_INT("pixs not defined", __func__, 1);
483
484
0
    return pixRotateShearIP(pixs, pixGetWidth(pixs) / 2,
485
0
                            pixGetHeight(pixs) / 2, angle, incolor);
486
0
}