granicus.if.org Git - imagemagick/blob - MagickCore/shear.c

   1 /*
   2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   3 %                                                                             %
   4 %                                                                             %
   5 %                                                                             %
   6 %                      SSSSS  H   H  EEEEE   AAA    RRRR                      %
   7 %                      SS     H   H  E      A   A   R   R                     %
   8 %                       SSS   HHHHH  EEE    AAAAA   RRRR                      %
   9 %                         SS  H   H  E      A   A   R R                       %
  10 %                      SSSSS  H   H  EEEEE  A   A   R  R                      %
  11 %                                                                             %
  12 %                                                                             %
  13 %    MagickCore Methods to Shear or Rotate an Image by an Arbitrary Angle     %
  14 %                                                                             %
  15 %                               Software Design                               %
  16 %                                 John Cristy                                 %
  17 %                                  July 1992                                  %
  18 %                                                                             %
  19 %                                                                             %
  20 %  Copyright 1999-2011 ImageMagick Studio LLC, a non-profit organization      %
  21 %  dedicated to making software imaging solutions freely available.           %
  22 %                                                                             %
  23 %  You may not use this file except in compliance with the License.  You may  %
  24 %  obtain a copy of the License at                                            %
  25 %                                                                             %
  26 %    http://www.imagemagick.org/script/license.php                            %
  27 %                                                                             %
  28 %  Unless required by applicable law or agreed to in writing, software        %
  29 %  distributed under the License is distributed on an "AS IS" BASIS,          %
  30 %  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
  31 %  See the License for the specific language governing permissions and        %
  32 %  limitations under the License.                                             %
  33 %                                                                             %
  34 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  35 %
  36 %  The XShearImage() and YShearImage() methods are based on the paper "A Fast
  37 %  Algorithm for General Raster Rotatation" by Alan W. Paeth, Graphics
  38 %  Interface '86 (Vancouver).  ShearRotateImage() is adapted from a similar
  39 %  method based on the Paeth paper written by Michael Halle of the Spatial
  40 %  Imaging Group, MIT Media Lab.
  41 %
  42 */
  43 \f
  44 /*
  45   Include declarations.
  46 */
  47 #include "MagickCore/studio.h"
  48 #include "MagickCore/artifact.h"
  49 #include "MagickCore/attribute.h"
  50 #include "MagickCore/blob-private.h"
  51 #include "MagickCore/cache-private.h"
  52 #include "MagickCore/color-private.h"
  53 #include "MagickCore/colorspace-private.h"
  54 #include "MagickCore/composite.h"
  55 #include "MagickCore/composite-private.h"
  56 #include "MagickCore/decorate.h"
  57 #include "MagickCore/distort.h"
  58 #include "MagickCore/draw.h"
  59 #include "MagickCore/exception.h"
  60 #include "MagickCore/exception-private.h"
  61 #include "MagickCore/gem.h"
  62 #include "MagickCore/geometry.h"
  63 #include "MagickCore/image.h"
  64 #include "MagickCore/image-private.h"
  65 #include "MagickCore/memory_.h"
  66 #include "MagickCore/list.h"
  67 #include "MagickCore/monitor.h"
  68 #include "MagickCore/monitor-private.h"
  69 #include "MagickCore/nt-base-private.h"
  70 #include "MagickCore/pixel-accessor.h"
  71 #include "MagickCore/quantum.h"
  72 #include "MagickCore/resource_.h"
  73 #include "MagickCore/shear.h"
  74 #include "MagickCore/statistic.h"
  75 #include "MagickCore/string_.h"
  76 #include "MagickCore/string-private.h"
  77 #include "MagickCore/thread-private.h"
  78 #include "MagickCore/threshold.h"
  79 #include "MagickCore/transform.h"
  80 \f
  81 /*
  82 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  83 %                                                                             %
  84 %                                                                             %
  85 %                                                                             %
  86 %     A f f i n e T r a n s f o r m I m a g e                                 %
  87 %                                                                             %
  88 %                                                                             %
  89 %                                                                             %
  90 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  91 %
  92 %  AffineTransformImage() transforms an image as dictated by the affine matrix.
  93 %  It allocates the memory necessary for the new Image structure and returns
  94 %  a pointer to the new image.
  95 %
  96 %  The format of the AffineTransformImage method is:
  97 %
  98 %      Image *AffineTransformImage(const Image *image,
  99 %        AffineMatrix *affine_matrix,ExceptionInfo *exception)
 100 %
 101 %  A description of each parameter follows:
 102 %
 103 %    o image: the image.
 104 %
 105 %    o affine_matrix: the affine matrix.
 106 %
 107 %    o exception: return any errors or warnings in this structure.
 108 %
 109 */
 110 MagickExport Image *AffineTransformImage(const Image *image,
 111   const AffineMatrix *affine_matrix,ExceptionInfo *exception)
 112 {
 113   double
 114     distort[6];
 115
 116   Image
 117     *deskew_image;
 118
 119   /*
 120     Affine transform image.
 121   */
 122   assert(image->signature == MagickSignature);
 123   if (image->debug != MagickFalse)
 124     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 125   assert(affine_matrix != (AffineMatrix *) NULL);
 126   assert(exception != (ExceptionInfo *) NULL);
 127   assert(exception->signature == MagickSignature);
 128   distort[0]=affine_matrix->sx;
 129   distort[1]=affine_matrix->rx;
 130   distort[2]=affine_matrix->ry;
 131   distort[3]=affine_matrix->sy;
 132   distort[4]=affine_matrix->tx;
 133   distort[5]=affine_matrix->ty;
 134   deskew_image=DistortImage(image,AffineProjectionDistortion,6,distort,
 135     MagickTrue,exception);
 136   return(deskew_image);
 137 }
 138 \f
 139 /*
 140 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 141 %                                                                             %
 142 %                                                                             %
 143 %                                                                             %
 144 +   C r o p T o F i t I m a g e                                               %
 145 %                                                                             %
 146 %                                                                             %
 147 %                                                                             %
 148 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 149 %
 150 %  CropToFitImage() crops the sheared image as determined by the bounding box
 151 %  as defined by width and height and shearing angles.
 152 %
 153 %  The format of the CropToFitImage method is:
 154 %
 155 %      MagickBooleanType CropToFitImage(Image **image,
 156 %        const MagickRealType x_shear,const MagickRealType x_shear,
 157 %        const MagickRealType width,const MagickRealType height,
 158 %        const MagickBooleanType rotate,ExceptionInfo *exception)
 159 %
 160 %  A description of each parameter follows.
 161 %
 162 %    o image: the image.
 163 %
 164 %    o x_shear, y_shear, width, height: Defines a region of the image to crop.
 165 %
 166 %    o exception: return any errors or warnings in this structure.
 167 %
 168 */
 169 static MagickBooleanType CropToFitImage(Image **image,
 170   const MagickRealType x_shear,const MagickRealType y_shear,
 171   const MagickRealType width,const MagickRealType height,
 172   const MagickBooleanType rotate,ExceptionInfo *exception)
 173 {
 174   Image
 175     *crop_image;
 176
 177   PointInfo
 178     extent[4],
 179     min,
 180     max;
 181
 182   RectangleInfo
 183     geometry,
 184     page;
 185
 186   register ssize_t
 187     i;
 188
 189   /*
 190     Calculate the rotated image size.
 191   */
 192   extent[0].x=(double) (-width/2.0);
 193   extent[0].y=(double) (-height/2.0);
 194   extent[1].x=(double) width/2.0;
 195   extent[1].y=(double) (-height/2.0);
 196   extent[2].x=(double) (-width/2.0);
 197   extent[2].y=(double) height/2.0;
 198   extent[3].x=(double) width/2.0;
 199   extent[3].y=(double) height/2.0;
 200   for (i=0; i < 4; i++)
 201   {
 202     extent[i].x+=x_shear*extent[i].y;
 203     extent[i].y+=y_shear*extent[i].x;
 204     if (rotate != MagickFalse)
 205       extent[i].x+=x_shear*extent[i].y;
 206     extent[i].x+=(double) (*image)->columns/2.0;
 207     extent[i].y+=(double) (*image)->rows/2.0;
 208   }
 209   min=extent[0];
 210   max=extent[0];
 211   for (i=1; i < 4; i++)
 212   {
 213     if (min.x > extent[i].x)
 214       min.x=extent[i].x;
 215     if (min.y > extent[i].y)
 216       min.y=extent[i].y;
 217     if (max.x < extent[i].x)
 218       max.x=extent[i].x;
 219     if (max.y < extent[i].y)
 220       max.y=extent[i].y;
 221   }
 222   geometry.x=(ssize_t) ceil(min.x-0.5);
 223   geometry.y=(ssize_t) ceil(min.y-0.5);
 224   geometry.width=(size_t) floor(max.x-min.x+0.5);
 225   geometry.height=(size_t) floor(max.y-min.y+0.5);
 226   page=(*image)->page;
 227   (void) ParseAbsoluteGeometry("0x0+0+0",&(*image)->page);
 228   crop_image=CropImage(*image,&geometry,exception);
 229   if (crop_image == (Image *) NULL)
 230     return(MagickFalse);
 231   crop_image->page=page;
 232   *image=DestroyImage(*image);
 233   *image=crop_image;
 234   return(MagickTrue);
 235 }
 236 \f
 237 /*
 238 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 239 %                                                                             %
 240 %                                                                             %
 241 %                                                                             %
 242 %     D e s k e w I m a g e                                                   %
 243 %                                                                             %
 244 %                                                                             %
 245 %                                                                             %
 246 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 247 %
 248 %  DeskewImage() removes skew from the image.  Skew is an artifact that
 249 %  occurs in scanned images because of the camera being misaligned,
 250 %  imperfections in the scanning or surface, or simply because the paper was
 251 %  not placed completely flat when scanned.
 252 %
 253 %  The format of the DeskewImage method is:
 254 %
 255 %      Image *DeskewImage(const Image *image,const double threshold,
 256 %        ExceptionInfo *exception)
 257 %
 258 %  A description of each parameter follows:
 259 %
 260 %    o image: the image.
 261 %
 262 %    o threshold: separate background from foreground.
 263 %
 264 %    o exception: return any errors or warnings in this structure.
 265 %
 266 */
 267
 268 typedef struct _RadonInfo
 269 {
 270   CacheType
 271     type;
 272
 273   size_t
 274     width,
 275     height;
 276
 277   MagickSizeType
 278     length;
 279
 280   MagickBooleanType
 281     mapped;
 282
 283   char
 284     path[MaxTextExtent];
 285
 286   int
 287     file;
 288
 289   unsigned short
 290     *cells;
 291 } RadonInfo;
 292
 293 static RadonInfo *DestroyRadonInfo(RadonInfo *radon_info)
 294 {
 295   assert(radon_info != (RadonInfo *) NULL);
 296   switch (radon_info->type)
 297   {
 298     case MemoryCache:
 299     {
 300       if (radon_info->mapped == MagickFalse)
 301         radon_info->cells=(unsigned short *) RelinquishMagickMemory(
 302           radon_info->cells);
 303       else
 304         radon_info->cells=(unsigned short *) UnmapBlob(radon_info->cells,
 305           (size_t) radon_info->length);
 306       RelinquishMagickResource(MemoryResource,radon_info->length);
 307       break;
 308     }
 309     case MapCache:
 310     {
 311       radon_info->cells=(unsigned short *) UnmapBlob(radon_info->cells,(size_t)
 312         radon_info->length);
 313       RelinquishMagickResource(MapResource,radon_info->length);
 314     }
 315     case DiskCache:
 316     {
 317       if (radon_info->file != -1)
 318         (void) close(radon_info->file);
 319       (void) RelinquishUniqueFileResource(radon_info->path);
 320       RelinquishMagickResource(DiskResource,radon_info->length);
 321       break;
 322     }
 323     default:
 324       break;
 325   }
 326   return((RadonInfo *) RelinquishMagickMemory(radon_info));
 327 }
 328
 329 static MagickBooleanType ResetRadonCells(RadonInfo *radon_info)
 330 {
 331   register ssize_t
 332     x;
 333
 334   ssize_t
 335     count,
 336     y;
 337
 338   unsigned short
 339     value;
 340
 341   if (radon_info->type != DiskCache)
 342     {
 343       (void) ResetMagickMemory(radon_info->cells,0,(size_t) radon_info->length);
 344       return(MagickTrue);
 345     }
 346   value=0;
 347   (void) lseek(radon_info->file,0,SEEK_SET);
 348   for (y=0; y < (ssize_t) radon_info->height; y++)
 349   {
 350     for (x=0; x < (ssize_t) radon_info->width; x++)
 351     {
 352       count=write(radon_info->file,&value,sizeof(*radon_info->cells));
 353       if (count != (ssize_t) sizeof(*radon_info->cells))
 354         break;
 355     }
 356     if (x < (ssize_t) radon_info->width)
 357       break;
 358   }
 359   return(y < (ssize_t) radon_info->height ? MagickFalse : MagickTrue);
 360 }
 361
 362 static RadonInfo *AcquireRadonInfo(const Image *image,const size_t width,
 363   const size_t height,ExceptionInfo *exception)
 364 {
 365   MagickBooleanType
 366     status;
 367
 368   RadonInfo
 369     *radon_info;
 370
 371   radon_info=(RadonInfo *) AcquireMagickMemory(sizeof(*radon_info));
 372   if (radon_info == (RadonInfo *) NULL)
 373     return((RadonInfo *) NULL);
 374   (void) ResetMagickMemory(radon_info,0,sizeof(*radon_info));
 375   radon_info->width=width;
 376   radon_info->height=height;
 377   radon_info->length=(MagickSizeType) width*height*sizeof(*radon_info->cells);
 378   radon_info->type=MemoryCache;
 379   status=AcquireMagickResource(AreaResource,radon_info->length);
 380   if ((status != MagickFalse) &&
 381       (radon_info->length == (MagickSizeType) ((size_t) radon_info->length)))
 382     {
 383       status=AcquireMagickResource(MemoryResource,radon_info->length);
 384       if (status != MagickFalse)
 385         {
 386           radon_info->mapped=MagickFalse;
 387           radon_info->cells=(unsigned short *) AcquireMagickMemory((size_t)
 388             radon_info->length);
 389           if (radon_info->cells == (unsigned short *) NULL)
 390             {
 391               radon_info->mapped=MagickTrue;
 392               radon_info->cells=(unsigned short *) MapBlob(-1,IOMode,0,(size_t)
 393                 radon_info->length);
 394             }
 395           if (radon_info->cells == (unsigned short *) NULL)
 396             RelinquishMagickResource(MemoryResource,radon_info->length);
 397         }
 398     }
 399   radon_info->file=(-1);
 400   if (radon_info->cells == (unsigned short *) NULL)
 401     {
 402       status=AcquireMagickResource(DiskResource,radon_info->length);
 403       if (status == MagickFalse)
 404         {
 405           (void) ThrowMagickException(exception,GetMagickModule(),CacheError,
 406             "CacheResourcesExhausted","`%s'",image->filename);
 407           return(DestroyRadonInfo(radon_info));
 408         }
 409       radon_info->type=DiskCache;
 410       (void) AcquireMagickResource(MemoryResource,radon_info->length);
 411       radon_info->file=AcquireUniqueFileResource(radon_info->path);
 412       if (radon_info->file == -1)
 413         return(DestroyRadonInfo(radon_info));
 414       status=AcquireMagickResource(MapResource,radon_info->length);
 415       if (status != MagickFalse)
 416         {
 417           status=ResetRadonCells(radon_info);
 418           if (status != MagickFalse)
 419             {
 420               radon_info->cells=(unsigned short *) MapBlob(radon_info->file,
 421                 IOMode,0,(size_t) radon_info->length);
 422               if (radon_info->cells != (unsigned short *) NULL)
 423                 radon_info->type=MapCache;
 424               else
 425                 RelinquishMagickResource(MapResource,radon_info->length);
 426             }
 427         }
 428     }
 429   return(radon_info);
 430 }
 431
 432 static inline size_t MagickMin(const size_t x,const size_t y)
 433 {
 434   if (x < y)
 435     return(x);
 436   return(y);
 437 }
 438
 439 static inline ssize_t ReadRadonCell(const RadonInfo *radon_info,
 440   const MagickOffsetType offset,const size_t length,unsigned char *buffer)
 441 {
 442   register ssize_t
 443     i;
 444
 445   ssize_t
 446     count;
 447
 448 #if !defined(MAGICKCORE_HAVE_PPREAD)
 449 #if defined(MAGICKCORE_OPENMP_SUPPORT)
 450   #pragma omp critical (MagickCore_ReadRadonCell)
 451 #endif
 452   {
 453     i=(-1);
 454     if (lseek(radon_info->file,offset,SEEK_SET) >= 0)
 455       {
 456 #endif
 457         count=0;
 458         for (i=0; i < (ssize_t) length; i+=count)
 459         {
 460 #if !defined(MAGICKCORE_HAVE_PPREAD)
 461           count=read(radon_info->file,buffer+i,MagickMin(length-i,(size_t)
 462             SSIZE_MAX));
 463 #else
 464           count=pread(radon_info->file,buffer+i,MagickMin(length-i,(size_t)
 465             SSIZE_MAX),offset+i);
 466 #endif
 467           if (count > 0)
 468             continue;
 469           count=0;
 470           if (errno != EINTR)
 471             {
 472               i=(-1);
 473               break;
 474             }
 475         }
 476 #if !defined(MAGICKCORE_HAVE_PPREAD)
 477       }
 478   }
 479 #endif
 480   return(i);
 481 }
 482
 483 static inline ssize_t WriteRadonCell(const RadonInfo *radon_info,
 484   const MagickOffsetType offset,const size_t length,const unsigned char *buffer)
 485 {
 486   register ssize_t
 487     i;
 488
 489   ssize_t
 490     count;
 491
 492 #if !defined(MAGICKCORE_HAVE_PWRITE)
 493 #if defined(MAGICKCORE_OPENMP_SUPPORT)
 494   #pragma omp critical (MagickCore_WriteRadonCell)
 495 #endif
 496   {
 497     if (lseek(radon_info->file,offset,SEEK_SET) >= 0)
 498       {
 499 #endif
 500         count=0;
 501         for (i=0; i < (ssize_t) length; i+=count)
 502         {
 503 #if !defined(MAGICKCORE_HAVE_PWRITE)
 504           count=write(radon_info->file,buffer+i,MagickMin(length-i,(size_t)
 505             SSIZE_MAX));
 506 #else
 507           count=pwrite(radon_info->file,buffer+i,MagickMin(length-i,(size_t)
 508             SSIZE_MAX),offset+i);
 509 #endif
 510           if (count > 0)
 511             continue;
 512           count=0;
 513           if (errno != EINTR)
 514             {
 515               i=(-1);
 516               break;
 517             }
 518         }
 519 #if !defined(MAGICKCORE_HAVE_PWRITE)
 520       }
 521   }
 522 #endif
 523   return(i);
 524 }
 525
 526 static inline unsigned short GetRadonCell(const RadonInfo *radon_info,
 527   const ssize_t x,const ssize_t y)
 528 {
 529   MagickOffsetType
 530     i;
 531
 532   unsigned short
 533     value;
 534
 535   i=(MagickOffsetType) radon_info->height*x+y;
 536   if ((i < 0) ||
 537       ((MagickSizeType) (i*sizeof(*radon_info->cells)) >= radon_info->length))
 538     return(0);
 539   if (radon_info->type != DiskCache)
 540     return(radon_info->cells[i]);
 541   value=0;
 542   (void) ReadRadonCell(radon_info,i*sizeof(*radon_info->cells),
 543     sizeof(*radon_info->cells),(unsigned char *) &value);
 544   return(value);
 545 }
 546
 547 static inline MagickBooleanType SetRadonCell(const RadonInfo *radon_info,
 548   const ssize_t x,const ssize_t y,const unsigned short value)
 549 {
 550   MagickOffsetType
 551     i;
 552
 553   ssize_t
 554     count;
 555
 556   i=(MagickOffsetType) radon_info->height*x+y;
 557   if ((i < 0) ||
 558       ((MagickSizeType) (i*sizeof(*radon_info->cells)) >= radon_info->length))
 559     return(MagickFalse);
 560   if (radon_info->type != DiskCache)
 561     {
 562       radon_info->cells[i]=value;
 563       return(MagickTrue);
 564     }
 565   count=WriteRadonCell(radon_info,i*sizeof(*radon_info->cells),
 566     sizeof(*radon_info->cells),(const unsigned char *) &value);
 567   if (count != (ssize_t) sizeof(*radon_info->cells))
 568     return(MagickFalse);
 569   return(MagickTrue);
 570 }
 571
 572 static void RadonProjection(RadonInfo *source_cells,
 573   RadonInfo *destination_cells,const ssize_t sign,size_t *projection)
 574 {
 575   RadonInfo
 576     *swap;
 577
 578   register ssize_t
 579     x;
 580
 581   register RadonInfo
 582     *p,
 583     *q;
 584
 585   size_t
 586     step;
 587
 588   p=source_cells;
 589   q=destination_cells;
 590   for (step=1; step < p->width; step*=2)
 591   {
 592     for (x=0; x < (ssize_t) p->width; x+=2*(ssize_t) step)
 593     {
 594       register ssize_t
 595         i;
 596
 597       ssize_t
 598         y;
 599
 600       unsigned short
 601         cell;
 602
 603       for (i=0; i < (ssize_t) step; i++)
 604       {
 605         for (y=0; y < (ssize_t) (p->height-i-1); y++)
 606         {
 607           cell=GetRadonCell(p,x+i,y);
 608           (void) SetRadonCell(q,x+2*i,y,cell+GetRadonCell(p,x+i+(ssize_t)
 609             step,y+i));
 610           (void) SetRadonCell(q,x+2*i+1,y,cell+GetRadonCell(p,x+i+(ssize_t)
 611             step,y+i+1));
 612         }
 613         for ( ; y < (ssize_t) (p->height-i); y++)
 614         {
 615           cell=GetRadonCell(p,x+i,y);
 616           (void) SetRadonCell(q,x+2*i,y,cell+GetRadonCell(p,x+i+(ssize_t) step,
 617             y+i));
 618           (void) SetRadonCell(q,x+2*i+1,y,cell);
 619         }
 620         for ( ; y < (ssize_t) p->height; y++)
 621         {
 622           cell=GetRadonCell(p,x+i,y);
 623           (void) SetRadonCell(q,x+2*i,y,cell);
 624           (void) SetRadonCell(q,x+2*i+1,y,cell);
 625         }
 626       }
 627     }
 628     swap=p;
 629     p=q;
 630     q=swap;
 631   }
 632 #if defined(MAGICKCORE_OPENMP_SUPPORT)
 633   #pragma omp parallel for schedule(dynamic,4)
 634 #endif
 635   for (x=0; x < (ssize_t) p->width; x++)
 636   {
 637     register ssize_t
 638       y;
 639
 640     size_t
 641       sum;
 642
 643     sum=0;
 644     for (y=0; y < (ssize_t) (p->height-1); y++)
 645     {
 646       ssize_t
 647         delta;
 648
 649       delta=GetRadonCell(p,x,y)-(ssize_t) GetRadonCell(p,x,y+1);
 650       sum+=delta*delta;
 651     }
 652     projection[p->width+sign*x-1]=sum;
 653   }
 654 }
 655
 656 static MagickBooleanType RadonTransform(const Image *image,
 657   const double threshold,size_t *projection,ExceptionInfo *exception)
 658 {
 659   CacheView
 660     *image_view;
 661
 662   MagickBooleanType
 663     status;
 664
 665   RadonInfo
 666     *destination_cells,
 667     *source_cells;
 668
 669   register ssize_t
 670     i;
 671
 672   size_t
 673     count,
 674     width;
 675
 676   ssize_t
 677     y;
 678
 679   unsigned char
 680     byte;
 681
 682   unsigned short
 683     bits[256];
 684
 685   for (width=1; width < ((image->columns+7)/8); width<<=1) ;
 686   source_cells=AcquireRadonInfo(image,width,image->rows,exception);
 687   destination_cells=AcquireRadonInfo(image,width,image->rows,exception);
 688   if ((source_cells == (RadonInfo *) NULL) ||
 689       (destination_cells == (RadonInfo *) NULL))
 690     {
 691       if (destination_cells != (RadonInfo *) NULL)
 692         destination_cells=DestroyRadonInfo(destination_cells);
 693       if (source_cells != (RadonInfo *) NULL)
 694         source_cells=DestroyRadonInfo(source_cells);
 695       return(MagickFalse);
 696     }
 697   if (ResetRadonCells(source_cells) == MagickFalse)
 698     {
 699       destination_cells=DestroyRadonInfo(destination_cells);
 700       source_cells=DestroyRadonInfo(source_cells);
 701       return(MagickFalse);
 702     }
 703   for (i=0; i < 256; i++)
 704   {
 705     byte=(unsigned char) i;
 706     for (count=0; byte != 0; byte>>=1)
 707       count+=byte & 0x01;
 708     bits[i]=(unsigned short) count;
 709   }
 710   status=MagickTrue;
 711   image_view=AcquireCacheView(image);
 712 #if defined(MAGICKCORE_OPENMP_SUPPORT)
 713   #pragma omp parallel for schedule(dynamic,4) shared(status)
 714 #endif
 715   for (y=0; y < (ssize_t) image->rows; y++)
 716   {
 717     register const Quantum
 718       *restrict p;
 719
 720     register ssize_t
 721       i,
 722       x;
 723
 724     size_t
 725       bit,
 726       byte;
 727
 728     if (status == MagickFalse)
 729       continue;
 730     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
 731     if (p == (const Quantum *) NULL)
 732       {
 733         status=MagickFalse;
 734         continue;
 735       }
 736     bit=0;
 737     byte=0;
 738     i=(ssize_t) (image->columns+7)/8;
 739     for (x=0; x < (ssize_t) image->columns; x++)
 740     {
 741       byte<<=1;
 742       if ((double) GetPixelIntensity(image,p) < threshold)
 743         byte|=0x01;
 744       bit++;
 745       if (bit == 8)
 746         {
 747           (void) SetRadonCell(source_cells,--i,y,bits[byte]);
 748           bit=0;
 749           byte=0;
 750         }
 751       p+=GetPixelChannels(image);
 752     }
 753     if (bit != 0)
 754       {
 755         byte<<=(8-bit);
 756         (void) SetRadonCell(source_cells,--i,y,bits[byte]);
 757       }
 758   }
 759   RadonProjection(source_cells,destination_cells,-1,projection);
 760   (void) ResetRadonCells(source_cells);
 761 #if defined(MAGICKCORE_OPENMP_SUPPORT)
 762   #pragma omp parallel for schedule(dynamic,4) shared(status)
 763 #endif
 764   for (y=0; y < (ssize_t) image->rows; y++)
 765   {
 766     register const Quantum
 767       *restrict p;
 768
 769     register ssize_t
 770       i,
 771       x;
 772
 773     size_t
 774       bit,
 775       byte;
 776
 777     if (status == MagickFalse)
 778       continue;
 779     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
 780     if (p == (const Quantum *) NULL)
 781       {
 782         status=MagickFalse;
 783         continue;
 784       }
 785     bit=0;
 786     byte=0;
 787     i=0;
 788     for (x=0; x < (ssize_t) image->columns; x++)
 789     {
 790       byte<<=1;
 791       if ((double) GetPixelIntensity(image,p) < threshold)
 792         byte|=0x01;
 793       bit++;
 794       if (bit == 8)
 795         {
 796           (void) SetRadonCell(source_cells,i++,y,bits[byte]);
 797           bit=0;
 798           byte=0;
 799         }
 800       p+=GetPixelChannels(image);
 801     }
 802     if (bit != 0)
 803       {
 804         byte<<=(8-bit);
 805         (void) SetRadonCell(source_cells,i++,y,bits[byte]);
 806       }
 807   }
 808   RadonProjection(source_cells,destination_cells,1,projection);
 809   image_view=DestroyCacheView(image_view);
 810   destination_cells=DestroyRadonInfo(destination_cells);
 811   source_cells=DestroyRadonInfo(source_cells);
 812   return(MagickTrue);
 813 }
 814
 815 static void GetImageBackgroundColor(Image *image,const ssize_t offset,
 816   ExceptionInfo *exception)
 817 {
 818   CacheView
 819     *image_view;
 820
 821   PixelInfo
 822     background;
 823
 824   MagickRealType
 825     count;
 826
 827   ssize_t
 828     y;
 829
 830   /*
 831     Compute average background color.
 832   */
 833   if (offset <= 0)
 834     return;
 835   GetPixelInfo(image,&background);
 836   count=0.0;
 837   image_view=AcquireCacheView(image);
 838   for (y=0; y < (ssize_t) image->rows; y++)
 839   {
 840     register const Quantum
 841       *restrict p;
 842
 843     register ssize_t
 844       x;
 845
 846     if ((y >= offset) && (y < ((ssize_t) image->rows-offset)))
 847       continue;
 848     p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
 849     if (p == (const Quantum *) NULL)
 850       continue;
 851     for (x=0; x < (ssize_t) image->columns; x++)
 852     {
 853       if ((x >= offset) && (x < ((ssize_t) image->columns-offset)))
 854         continue;
 855       background.red+=QuantumScale*GetPixelRed(image,p);
 856       background.green+=QuantumScale*GetPixelGreen(image,p);
 857       background.blue+=QuantumScale*GetPixelBlue(image,p);
 858       if ((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0)
 859         background.alpha+=QuantumScale*GetPixelAlpha(image,p);
 860       count++;
 861       p+=GetPixelChannels(image);
 862     }
 863   }
 864   image_view=DestroyCacheView(image_view);
 865   image->background_color.red=(double) ClampToQuantum((MagickRealType)
 866     QuantumRange*background.red/count);
 867   image->background_color.green=(double) ClampToQuantum((MagickRealType)
 868     QuantumRange*background.green/count);
 869   image->background_color.blue=(double) ClampToQuantum((MagickRealType)
 870     QuantumRange*background.blue/count);
 871   if ((GetPixelAlphaTraits(image) & UpdatePixelTrait) != 0)
 872     image->background_color.alpha=(double) ClampToQuantum((MagickRealType)
 873       QuantumRange*background.alpha/count);
 874 }
 875
 876 MagickExport Image *DeskewImage(const Image *image,const double threshold,
 877   ExceptionInfo *exception)
 878 {
 879   AffineMatrix
 880     affine_matrix;
 881
 882   const char
 883     *artifact;
 884
 885   double
 886     degrees;
 887
 888   Image
 889     *clone_image,
 890     *crop_image,
 891     *deskew_image,
 892     *median_image;
 893
 894   MagickBooleanType
 895     status;
 896
 897   RectangleInfo
 898     geometry;
 899
 900   register ssize_t
 901     i;
 902
 903   size_t
 904     max_projection,
 905     *projection,
 906     width;
 907
 908   ssize_t
 909     skew;
 910
 911   /*
 912     Compute deskew angle.
 913   */
 914   for (width=1; width < ((image->columns+7)/8); width<<=1) ;
 915   projection=(size_t *) AcquireQuantumMemory((size_t) (2*width-1),
 916     sizeof(*projection));
 917   if (projection == (size_t *) NULL)
 918     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
 919   status=RadonTransform(image,threshold,projection,exception);
 920   if (status == MagickFalse)
 921     {
 922       projection=(size_t *) RelinquishMagickMemory(projection);
 923       ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
 924     }
 925   max_projection=0;
 926   skew=0;
 927   for (i=0; i < (ssize_t) (2*width-1); i++)
 928   {
 929     if (projection[i] > max_projection)
 930       {
 931         skew=i-(ssize_t) width+1;
 932         max_projection=projection[i];
 933       }
 934   }
 935   projection=(size_t *) RelinquishMagickMemory(projection);
 936   /*
 937     Deskew image.
 938   */
 939   clone_image=CloneImage(image,0,0,MagickTrue,exception);
 940   if (clone_image == (Image *) NULL)
 941     return((Image *) NULL);
 942   (void) SetImageVirtualPixelMethod(clone_image,BackgroundVirtualPixelMethod);
 943   degrees=RadiansToDegrees(-atan((double) skew/width/8));
 944   if (image->debug != MagickFalse)
 945     (void) LogMagickEvent(TransformEvent,GetMagickModule(),
 946       "  Deskew angle: %g",degrees);
 947   affine_matrix.sx=cos(DegreesToRadians(fmod((double) degrees,360.0)));
 948   affine_matrix.rx=sin(DegreesToRadians(fmod((double) degrees,360.0)));
 949   affine_matrix.ry=(-sin(DegreesToRadians(fmod((double) degrees,360.0))));
 950   affine_matrix.sy=cos(DegreesToRadians(fmod((double) degrees,360.0)));
 951   affine_matrix.tx=0.0;
 952   affine_matrix.ty=0.0;
 953   artifact=GetImageArtifact(image,"deskew:auto-crop");
 954   if (artifact == (const char *) NULL)
 955     {
 956       deskew_image=AffineTransformImage(clone_image,&affine_matrix,exception);
 957       clone_image=DestroyImage(clone_image);
 958       return(deskew_image);
 959     }
 960   /*
 961     Auto-crop image.
 962   */
 963   GetImageBackgroundColor(clone_image,(ssize_t) StringToLong(artifact),
 964     exception);
 965   deskew_image=AffineTransformImage(clone_image,&affine_matrix,exception);
 966   clone_image=DestroyImage(clone_image);
 967   if (deskew_image == (Image *) NULL)
 968     return((Image *) NULL);
 969   median_image=StatisticImage(deskew_image,MedianStatistic,3,3,exception);
 970   if (median_image == (Image *) NULL)
 971     {
 972       deskew_image=DestroyImage(deskew_image);
 973       return((Image *) NULL);
 974     }
 975   geometry=GetImageBoundingBox(median_image,exception);
 976   median_image=DestroyImage(median_image);
 977   if (image->debug != MagickFalse)
 978     (void) LogMagickEvent(TransformEvent,GetMagickModule(),"  Deskew geometry: "
 979       "%.20gx%.20g%+.20g%+.20g",(double) geometry.width,(double)
 980       geometry.height,(double) geometry.x,(double) geometry.y);
 981   crop_image=CropImage(deskew_image,&geometry,exception);
 982   deskew_image=DestroyImage(deskew_image);
 983   return(crop_image);
 984 }
 985 \f
 986 /*
 987 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 988 %                                                                             %
 989 %                                                                             %
 990 %                                                                             %
 991 +   I n t e g r a l R o t a t e I m a g e                                     %
 992 %                                                                             %
 993 %                                                                             %
 994 %                                                                             %
 995 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 996 %
 997 %  IntegralRotateImage() rotates the image an integral of 90 degrees.  It
 998 %  allocates the memory necessary for the new Image structure and returns a
 999 %  pointer to the rotated image.
1000 %
1001 %  The format of the IntegralRotateImage method is:
1002 %
1003 %      Image *IntegralRotateImage(const Image *image,size_t rotations,
1004 %        ExceptionInfo *exception)
1005 %
1006 %  A description of each parameter follows.
1007 %
1008 %    o image: the image.
1009 %
1010 %    o rotations: Specifies the number of 90 degree rotations.
1011 %
1012 */
1013 static Image *IntegralRotateImage(const Image *image,size_t rotations,
1014   ExceptionInfo *exception)
1015 {
1016 #define RotateImageTag  "Rotate/Image"
1017
1018   CacheView
1019     *image_view,
1020     *rotate_view;
1021
1022   Image
1023     *rotate_image;
1024
1025   MagickBooleanType
1026     status;
1027
1028   MagickOffsetType
1029     progress;
1030
1031   RectangleInfo
1032     page;
1033
1034   ssize_t
1035     y;
1036
1037   /*
1038     Initialize rotated image attributes.
1039   */
1040   assert(image != (Image *) NULL);
1041   page=image->page;
1042   rotations%=4;
1043   if (rotations == 0)
1044     return(CloneImage(image,0,0,MagickTrue,exception));
1045   if ((rotations == 1) || (rotations == 3))
1046     rotate_image=CloneImage(image,image->rows,image->columns,MagickTrue,
1047       exception);
1048   else
1049     rotate_image=CloneImage(image,image->columns,image->rows,MagickTrue,
1050       exception);
1051   if (rotate_image == (Image *) NULL)
1052     return((Image *) NULL);
1053   /*
1054     Integral rotate the image.
1055   */
1056   status=MagickTrue;
1057   progress=0;
1058   image_view=AcquireCacheView(image);
1059   rotate_view=AcquireCacheView(rotate_image);
1060   switch (rotations)
1061   {
1062     case 0:
1063     {
1064       /*
1065         Rotate 0 degrees.
1066       */
1067       break;
1068     }
1069     case 1:
1070     {
1071       size_t
1072         tile_height,
1073         tile_width;
1074
1075       ssize_t
1076         tile_y;
1077
1078       /*
1079         Rotate 90 degrees.
1080       */
1081       GetPixelCacheTileSize(image,&tile_width,&tile_height);
1082       tile_width=image->columns;
1083 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1084       #pragma omp parallel for schedule(dynamic,4) shared(progress, status) omp_throttle(1)
1085 #endif
1086       for (tile_y=0; tile_y < (ssize_t) image->rows; tile_y+=(ssize_t) tile_height)
1087       {
1088         register ssize_t
1089           tile_x;
1090
1091         if (status == MagickFalse)
1092           continue;
1093         tile_x=0;
1094         for ( ; tile_x < (ssize_t) image->columns; tile_x+=(ssize_t) tile_width)
1095         {
1096           MagickBooleanType
1097             sync;
1098
1099           register const Quantum
1100             *restrict p;
1101
1102           register Quantum
1103             *restrict q;
1104
1105           register ssize_t
1106             y;
1107
1108           size_t
1109             height,
1110             width;
1111
1112           width=tile_width;
1113           if ((tile_x+(ssize_t) tile_width) > (ssize_t) image->columns)
1114             width=(size_t) (tile_width-(tile_x+tile_width-image->columns));
1115           height=tile_height;
1116           if ((tile_y+(ssize_t) tile_height) > (ssize_t) image->rows)
1117             height=(size_t) (tile_height-(tile_y+tile_height-image->rows));
1118           p=GetCacheViewVirtualPixels(image_view,tile_x,tile_y,width,height,
1119             exception);
1120           if (p == (const Quantum *) NULL)
1121             {
1122               status=MagickFalse;
1123               break;
1124             }
1125           for (y=0; y < (ssize_t) width; y++)
1126           {
1127             register const Quantum
1128               *restrict tile_pixels;
1129
1130             register ssize_t
1131               x;
1132
1133             if (status == MagickFalse)
1134               continue;
1135             q=QueueCacheViewAuthenticPixels(rotate_view,(ssize_t)
1136               (rotate_image->columns-(tile_y+height)),y+tile_x,height,1,
1137               exception);
1138             if (q == (Quantum *) NULL)
1139               {
1140                 status=MagickFalse;
1141                 continue;
1142               }
1143             tile_pixels=p+((height-1)*width+y)*GetPixelChannels(image);
1144             for (x=0; x < (ssize_t) height; x++)
1145             {
1146               register ssize_t
1147                 i;
1148
1149               for (i=0; i < (ssize_t) GetPixelChannels(image); i++)
1150               {
1151                 PixelChannel
1152                   channel;
1153
1154                 PixelTrait
1155                   rotate_traits,
1156                   traits;
1157
1158                 traits=GetPixelChannelMapTraits(image,(PixelChannel) i);
1159                 channel=GetPixelChannelMapChannel(image,(PixelChannel) i);
1160                 rotate_traits=GetPixelChannelMapTraits(rotate_image,channel);
1161                 if ((traits == UndefinedPixelTrait) ||
1162                     (rotate_traits == UndefinedPixelTrait))
1163                   continue;
1164                 SetPixelChannel(rotate_image,channel,tile_pixels[i],q);
1165               }
1166               tile_pixels-=width*GetPixelChannels(image);
1167               q+=GetPixelChannels(rotate_image);
1168             }
1169             sync=SyncCacheViewAuthenticPixels(rotate_view,exception);
1170             if (sync == MagickFalse)
1171               status=MagickFalse;
1172           }
1173         }
1174         if (image->progress_monitor != (MagickProgressMonitor) NULL)
1175           {
1176             MagickBooleanType
1177               proceed;
1178
1179 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1180             #pragma omp critical (MagickCore_IntegralRotateImage)
1181 #endif
1182             proceed=SetImageProgress(image,RotateImageTag,progress+=tile_height,
1183               image->rows);
1184             if (proceed == MagickFalse)
1185               status=MagickFalse;
1186           }
1187       }
1188       (void) SetImageProgress(image,RotateImageTag,(MagickOffsetType)
1189         image->rows-1,image->rows);
1190       Swap(page.width,page.height);
1191       Swap(page.x,page.y);
1192       if (page.width != 0)
1193         page.x=(ssize_t) (page.width-rotate_image->columns-page.x);
1194       break;
1195     }
1196     case 2:
1197     {
1198       /*
1199         Rotate 180 degrees.
1200       */
1201 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1202       #pragma omp parallel for schedule(dynamic,4) shared(progress,status) omp_throttle(1)
1203 #endif
1204       for (y=0; y < (ssize_t) image->rows; y++)
1205       {
1206         MagickBooleanType
1207           sync;
1208
1209         register const Quantum
1210           *restrict p;
1211
1212         register Quantum
1213           *restrict q;
1214
1215         register ssize_t
1216           x;
1217
1218         if (status == MagickFalse)
1219           continue;
1220         p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
1221         q=QueueCacheViewAuthenticPixels(rotate_view,0,(ssize_t) (image->rows-y-
1222           1),image->columns,1,exception);
1223         if ((p == (const Quantum *) NULL) || (q == (Quantum *) NULL))
1224           {
1225             status=MagickFalse;
1226             continue;
1227           }
1228         q+=GetPixelChannels(rotate_image)*image->columns;
1229         for (x=0; x < (ssize_t) image->columns; x++)
1230         {
1231           register ssize_t
1232             i;
1233
1234           q-=GetPixelChannels(rotate_image);
1235           for (i=0; i < (ssize_t) GetPixelChannels(image); i++)
1236           {
1237             PixelChannel
1238               channel;
1239
1240             PixelTrait
1241               rotate_traits,
1242               traits;
1243
1244             traits=GetPixelChannelMapTraits(image,(PixelChannel) i);
1245             channel=GetPixelChannelMapChannel(image,(PixelChannel) i);
1246             rotate_traits=GetPixelChannelMapTraits(rotate_image,channel);
1247             if ((traits == UndefinedPixelTrait) ||
1248                 (rotate_traits == UndefinedPixelTrait))
1249               continue;
1250             SetPixelChannel(rotate_image,channel,p[i],q);
1251           }
1252           p+=GetPixelChannels(image);
1253         }
1254         sync=SyncCacheViewAuthenticPixels(rotate_view,exception);
1255         if (sync == MagickFalse)
1256           status=MagickFalse;
1257         if (image->progress_monitor != (MagickProgressMonitor) NULL)
1258           {
1259             MagickBooleanType
1260               proceed;
1261
1262 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1263             #pragma omp critical (MagickCore_IntegralRotateImage)
1264 #endif
1265             proceed=SetImageProgress(image,RotateImageTag,progress++,
1266               image->rows);
1267             if (proceed == MagickFalse)
1268               status=MagickFalse;
1269           }
1270       }
1271       (void) SetImageProgress(image,RotateImageTag,(MagickOffsetType)
1272         image->rows-1,image->rows);
1273       Swap(page.width,page.height);
1274       Swap(page.x,page.y);
1275       if (page.width != 0)
1276         page.x=(ssize_t) (page.width-rotate_image->columns-page.x);
1277       break;
1278     }
1279     case 3:
1280     {
1281       size_t
1282         tile_height,
1283         tile_width;
1284
1285       ssize_t
1286         tile_y;
1287
1288       /*
1289         Rotate 270 degrees.
1290       */
1291       GetPixelCacheTileSize(image,&tile_width,&tile_height);
1292       tile_width=image->columns;
1293 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1294       #pragma omp parallel for schedule(dynamic,4) shared(progress,status) omp_throttle(1)
1295 #endif
1296       for (tile_y=0; tile_y < (ssize_t) image->rows; tile_y+=(ssize_t) tile_height)
1297       {
1298         register ssize_t
1299           tile_x;
1300
1301         if (status == MagickFalse)
1302           continue;
1303         tile_x=0;
1304         for ( ; tile_x < (ssize_t) image->columns; tile_x+=(ssize_t) tile_width)
1305         {
1306           MagickBooleanType
1307             sync;
1308
1309           register const Quantum
1310             *restrict p;
1311
1312           register Quantum
1313             *restrict q;
1314
1315           register ssize_t
1316             y;
1317
1318           size_t
1319             height,
1320             width;
1321
1322           width=tile_width;
1323           if ((tile_x+(ssize_t) tile_width) > (ssize_t) image->columns)
1324             width=(size_t) (tile_width-(tile_x+tile_width-image->columns));
1325           height=tile_height;
1326           if ((tile_y+(ssize_t) tile_height) > (ssize_t) image->rows)
1327             height=(size_t) (tile_height-(tile_y+tile_height-image->rows));
1328           p=GetCacheViewVirtualPixels(image_view,tile_x,tile_y,width,height,
1329             exception);
1330           if (p == (const Quantum *) NULL)
1331             {
1332               status=MagickFalse;
1333               break;
1334             }
1335           for (y=0; y < (ssize_t) width; y++)
1336           {
1337             register const Quantum
1338               *restrict tile_pixels;
1339
1340             register ssize_t
1341               x;
1342
1343             if (status == MagickFalse)
1344               continue;
1345             q=QueueCacheViewAuthenticPixels(rotate_view,tile_y,(ssize_t) (y+
1346               rotate_image->rows-(tile_x+width)),height,1,exception);
1347             if (q == (Quantum *) NULL)
1348               {
1349                 status=MagickFalse;
1350                 continue;
1351               }
1352             tile_pixels=p+((width-1)-y)*GetPixelChannels(image);
1353             for (x=0; x < (ssize_t) height; x++)
1354             {
1355               register ssize_t
1356                 i;
1357
1358               for (i=0; i < (ssize_t) GetPixelChannels(image); i++)
1359               {
1360                 PixelChannel
1361                   channel;
1362
1363                 PixelTrait
1364                   rotate_traits,
1365                   traits;
1366
1367                 traits=GetPixelChannelMapTraits(image,(PixelChannel) i);
1368                 channel=GetPixelChannelMapChannel(image,(PixelChannel) i);
1369                 rotate_traits=GetPixelChannelMapTraits(rotate_image,channel);
1370                 if ((traits == UndefinedPixelTrait) ||
1371                     (rotate_traits == UndefinedPixelTrait))
1372                   continue;
1373                 SetPixelChannel(rotate_image,channel,tile_pixels[i],q);
1374               }
1375               tile_pixels+=width*GetPixelChannels(image);
1376               q+=GetPixelChannels(rotate_image);
1377             }
1378             sync=SyncCacheViewAuthenticPixels(rotate_view,exception);
1379             if (sync == MagickFalse)
1380               status=MagickFalse;
1381           }
1382         }
1383         if (image->progress_monitor != (MagickProgressMonitor) NULL)
1384           {
1385             MagickBooleanType
1386               proceed;
1387
1388 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1389             #pragma omp critical (MagickCore_IntegralRotateImage)
1390 #endif
1391             proceed=SetImageProgress(image,RotateImageTag,progress+=tile_height,
1392               image->rows);
1393             if (proceed == MagickFalse)
1394               status=MagickFalse;
1395           }
1396       }
1397       (void) SetImageProgress(image,RotateImageTag,(MagickOffsetType)
1398         image->rows-1,image->rows);
1399       Swap(page.width,page.height);
1400       Swap(page.x,page.y);
1401       if (page.width != 0)
1402         page.x=(ssize_t) (page.width-rotate_image->columns-page.x);
1403       break;
1404     }
1405   }
1406   rotate_view=DestroyCacheView(rotate_view);
1407   image_view=DestroyCacheView(image_view);
1408   rotate_image->type=image->type;
1409   rotate_image->page=page;
1410   if (status == MagickFalse)
1411     rotate_image=DestroyImage(rotate_image);
1412   return(rotate_image);
1413 }
1414 \f
1415 /*
1416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1417 %                                                                             %
1418 %                                                                             %
1419 %                                                                             %
1420 +   X S h e a r I m a g e                                                     %
1421 %                                                                             %
1422 %                                                                             %
1423 %                                                                             %
1424 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1425 %
1426 %  XShearImage() shears the image in the X direction with a shear angle of
1427 %  'degrees'.  Positive angles shear counter-clockwise (right-hand rule), and
1428 %  negative angles shear clockwise.  Angles are measured relative to a vertical
1429 %  Y-axis.  X shears will widen an image creating 'empty' triangles on the left
1430 %  and right sides of the source image.
1431 %
1432 %  The format of the XShearImage method is:
1433 %
1434 %      MagickBooleanType XShearImage(Image *image,const MagickRealType degrees,
1435 %        const size_t width,const size_t height,
1436 %        const ssize_t x_offset,const ssize_t y_offset,ExceptionInfo *exception)
1437 %
1438 %  A description of each parameter follows.
1439 %
1440 %    o image: the image.
1441 %
1442 %    o degrees: A MagickRealType representing the shearing angle along the X
1443 %      axis.
1444 %
1445 %    o width, height, x_offset, y_offset: Defines a region of the image
1446 %      to shear.
1447 %
1448 %    o exception: return any errors or warnings in this structure.
1449 %
1450 */
1451 static MagickBooleanType XShearImage(Image *image,const MagickRealType degrees,
1452   const size_t width,const size_t height,const ssize_t x_offset,
1453   const ssize_t y_offset,ExceptionInfo *exception)
1454 {
1455 #define XShearImageTag  "XShear/Image"
1456
1457   typedef enum
1458   {
1459     LEFT,
1460     RIGHT
1461   } ShearDirection;
1462
1463   CacheView
1464     *image_view;
1465
1466   MagickBooleanType
1467     status;
1468
1469   MagickOffsetType
1470     progress;
1471
1472   PixelInfo
1473     background;
1474
1475   ssize_t
1476     y;
1477
1478   /*
1479     X shear image.
1480   */
1481   assert(image != (Image *) NULL);
1482   assert(image->signature == MagickSignature);
1483   if (image->debug != MagickFalse)
1484     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1485   status=MagickTrue;
1486   background=image->background_color;
1487   progress=0;
1488   image_view=AcquireCacheView(image);
1489 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1490   #pragma omp parallel for schedule(dynamic,4) shared(progress, status)
1491 #endif
1492   for (y=0; y < (ssize_t) height; y++)
1493   {
1494     PixelInfo
1495       pixel,
1496       source,
1497       destination;
1498
1499     MagickRealType
1500       area,
1501       displacement;
1502
1503     register Quantum
1504       *restrict p,
1505       *restrict q;
1506
1507     register ssize_t
1508       i;
1509
1510     ShearDirection
1511       direction;
1512
1513     ssize_t
1514       step;
1515
1516     if (status == MagickFalse)
1517       continue;
1518     p=GetCacheViewAuthenticPixels(image_view,0,y_offset+y,image->columns,1,
1519       exception);
1520     if (p == (Quantum *) NULL)
1521       {
1522         status=MagickFalse;
1523         continue;
1524       }
1525     p+=x_offset*GetPixelChannels(image);
1526     displacement=degrees*(MagickRealType) (y-height/2.0);
1527     if (displacement == 0.0)
1528       continue;
1529     if (displacement > 0.0)
1530       direction=RIGHT;
1531     else
1532       {
1533         displacement*=(-1.0);
1534         direction=LEFT;
1535       }
1536     step=(ssize_t) floor((double) displacement);
1537     area=(MagickRealType) (displacement-step);
1538     step++;
1539     pixel=background;
1540     GetPixelInfo(image,&source);
1541     GetPixelInfo(image,&destination);
1542     switch (direction)
1543     {
1544       case LEFT:
1545       {
1546         /*
1547           Transfer pixels left-to-right.
1548         */
1549         if (step > x_offset)
1550           break;
1551         q=p-step*GetPixelChannels(image);
1552         for (i=0; i < (ssize_t) width; i++)
1553         {
1554           if ((x_offset+i) < step)
1555             {
1556               p+=GetPixelChannels(image);
1557               SetPixelInfo(image,p,&pixel);
1558               q+=GetPixelChannels(image);
1559               continue;
1560             }
1561           SetPixelInfo(image,p,&source);
1562           CompositePixelInfoAreaBlend(&pixel,(MagickRealType) pixel.alpha,
1563             &source,(MagickRealType) GetPixelAlpha(image,p),area,&destination);
1564           SetPixelPixelInfo(image,&destination,q);
1565           SetPixelInfo(image,p,&pixel);
1566           p+=GetPixelChannels(image);
1567           q+=GetPixelChannels(image);
1568         }
1569         CompositePixelInfoAreaBlend(&pixel,(MagickRealType) pixel.alpha,
1570           &background,(MagickRealType) background.alpha,area,&destination);
1571         SetPixelPixelInfo(image,&destination,q);
1572         q+=GetPixelChannels(image);
1573         for (i=0; i < (step-1); i++)
1574         {
1575           SetPixelPixelInfo(image,&background,q);
1576           q+=GetPixelChannels(image);
1577         }
1578         break;
1579       }
1580       case RIGHT:
1581       {
1582         /*
1583           Transfer pixels right-to-left.
1584         */
1585         p+=width*GetPixelChannels(image);
1586         q=p+step*GetPixelChannels(image);
1587         for (i=0; i < (ssize_t) width; i++)
1588         {
1589           p-=GetPixelChannels(image);
1590           q-=GetPixelChannels(image);
1591           if ((size_t) (x_offset+width+step-i) >= image->columns)
1592             continue;
1593           SetPixelInfo(image,p,&source);
1594           CompositePixelInfoAreaBlend(&pixel,(MagickRealType) pixel.alpha,
1595             &source,(MagickRealType) GetPixelAlpha(image,p),area,&destination);
1596           SetPixelPixelInfo(image,&destination,q);
1597           SetPixelInfo(image,p,&pixel);
1598         }
1599         CompositePixelInfoAreaBlend(&pixel,(MagickRealType) pixel.alpha,
1600           &background,(MagickRealType) background.alpha,area,&destination);
1601         q-=GetPixelChannels(image);
1602         SetPixelPixelInfo(image,&destination,q);
1603         for (i=0; i < (step-1); i++)
1604         {
1605           q-=GetPixelChannels(image);
1606           SetPixelPixelInfo(image,&background,q);
1607         }
1608         break;
1609       }
1610     }
1611     if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1612       status=MagickFalse;
1613     if (image->progress_monitor != (MagickProgressMonitor) NULL)
1614       {
1615         MagickBooleanType
1616           proceed;
1617
1618 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1619         #pragma omp critical (MagickCore_XShearImage)
1620 #endif
1621         proceed=SetImageProgress(image,XShearImageTag,progress++,height);
1622         if (proceed == MagickFalse)
1623           status=MagickFalse;
1624       }
1625   }
1626   image_view=DestroyCacheView(image_view);
1627   return(status);
1628 }
1629 \f
1630 /*
1631 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1632 %                                                                             %
1633 %                                                                             %
1634 %                                                                             %
1635 +   Y S h e a r I m a g e                                                     %
1636 %                                                                             %
1637 %                                                                             %
1638 %                                                                             %
1639 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1640 %
1641 %  YShearImage shears the image in the Y direction with a shear angle of
1642 %  'degrees'.  Positive angles shear counter-clockwise (right-hand rule), and
1643 %  negative angles shear clockwise.  Angles are measured relative to a
1644 %  horizontal X-axis.  Y shears will increase the height of an image creating
1645 %  'empty' triangles on the top and bottom of the source image.
1646 %
1647 %  The format of the YShearImage method is:
1648 %
1649 %      MagickBooleanType YShearImage(Image *image,const MagickRealType degrees,
1650 %        const size_t width,const size_t height,
1651 %        const ssize_t x_offset,const ssize_t y_offset,ExceptionInfo *exception)
1652 %
1653 %  A description of each parameter follows.
1654 %
1655 %    o image: the image.
1656 %
1657 %    o degrees: A MagickRealType representing the shearing angle along the Y
1658 %      axis.
1659 %
1660 %    o width, height, x_offset, y_offset: Defines a region of the image
1661 %      to shear.
1662 %
1663 %    o exception: return any errors or warnings in this structure.
1664 %
1665 */
1666 static MagickBooleanType YShearImage(Image *image,const MagickRealType degrees,
1667   const size_t width,const size_t height,const ssize_t x_offset,
1668   const ssize_t y_offset,ExceptionInfo *exception)
1669 {
1670 #define YShearImageTag  "YShear/Image"
1671
1672   typedef enum
1673   {
1674     UP,
1675     DOWN
1676   } ShearDirection;
1677
1678   CacheView
1679     *image_view;
1680
1681   MagickBooleanType
1682     status;
1683
1684   MagickOffsetType
1685     progress;
1686
1687   PixelInfo
1688     background;
1689
1690   ssize_t
1691     x;
1692
1693   /*
1694     Y Shear image.
1695   */
1696   assert(image != (Image *) NULL);
1697   assert(image->signature == MagickSignature);
1698   if (image->debug != MagickFalse)
1699     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1700   status=MagickTrue;
1701   progress=0;
1702   background=image->background_color;
1703   image_view=AcquireCacheView(image);
1704 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1705   #pragma omp parallel for schedule(dynamic,4) shared(progress, status)
1706 #endif
1707   for (x=0; x < (ssize_t) width; x++)
1708   {
1709     ssize_t
1710       step;
1711
1712     MagickRealType
1713       area,
1714       displacement;
1715
1716     PixelInfo
1717       pixel,
1718       source,
1719       destination;
1720
1721     register Quantum
1722       *restrict p,
1723       *restrict q;
1724
1725     register ssize_t
1726       i;
1727
1728     ShearDirection
1729       direction;
1730
1731     if (status == MagickFalse)
1732       continue;
1733     p=GetCacheViewAuthenticPixels(image_view,x_offset+x,0,1,image->rows,
1734       exception);
1735     if (p == (Quantum *) NULL)
1736       {
1737         status=MagickFalse;
1738         continue;
1739       }
1740     p+=y_offset*GetPixelChannels(image);
1741     displacement=degrees*(MagickRealType) (x-width/2.0);
1742     if (displacement == 0.0)
1743       continue;
1744     if (displacement > 0.0)
1745       direction=DOWN;
1746     else
1747       {
1748         displacement*=(-1.0);
1749         direction=UP;
1750       }
1751     step=(ssize_t) floor((double) displacement);
1752     area=(MagickRealType) (displacement-step);
1753     step++;
1754     pixel=background;
1755     GetPixelInfo(image,&source);
1756     GetPixelInfo(image,&destination);
1757     switch (direction)
1758     {
1759       case UP:
1760       {
1761         /*
1762           Transfer pixels top-to-bottom.
1763         */
1764         if (step > y_offset)
1765           break;
1766         q=p-step*GetPixelChannels(image);
1767         for (i=0; i < (ssize_t) height; i++)
1768         {
1769           if ((y_offset+i) < step)
1770             {
1771               p+=GetPixelChannels(image);
1772               SetPixelInfo(image,p,&pixel);
1773               q+=GetPixelChannels(image);
1774               continue;
1775             }
1776           SetPixelInfo(image,p,&source);
1777           CompositePixelInfoAreaBlend(&pixel,(MagickRealType) pixel.alpha,
1778             &source,(MagickRealType) GetPixelAlpha(image,p),area,
1779             &destination);
1780           SetPixelPixelInfo(image,&destination,q);
1781           SetPixelInfo(image,p,&pixel);
1782           p+=GetPixelChannels(image);
1783           q+=GetPixelChannels(image);
1784         }
1785         CompositePixelInfoAreaBlend(&pixel,(MagickRealType) pixel.alpha,
1786           &background,(MagickRealType) background.alpha,area,&destination);
1787         SetPixelPixelInfo(image,&destination,q);
1788         q+=GetPixelChannels(image);
1789         for (i=0; i < (step-1); i++)
1790         {
1791           SetPixelPixelInfo(image,&background,q);
1792           q+=GetPixelChannels(image);
1793         }
1794         break;
1795       }
1796       case DOWN:
1797       {
1798         /*
1799           Transfer pixels bottom-to-top.
1800         */
1801         p+=height*GetPixelChannels(image);
1802         q=p+step*GetPixelChannels(image);
1803         for (i=0; i < (ssize_t) height; i++)
1804         {
1805           p-=GetPixelChannels(image);
1806           q-=GetPixelChannels(image);
1807           if ((size_t) (y_offset+height+step-i) >= image->rows)
1808             continue;
1809           SetPixelInfo(image,p,&source);
1810           CompositePixelInfoAreaBlend(&pixel,(MagickRealType) pixel.alpha,
1811             &source,(MagickRealType) GetPixelAlpha(image,p),area,
1812             &destination);
1813           SetPixelPixelInfo(image,&destination,q);
1814           SetPixelInfo(image,p,&pixel);
1815         }
1816         CompositePixelInfoAreaBlend(&pixel,(MagickRealType) pixel.alpha,
1817           &background,(MagickRealType) background.alpha,area,&destination);
1818         q-=GetPixelChannels(image);
1819         SetPixelPixelInfo(image,&destination,q);
1820         for (i=0; i < (step-1); i++)
1821         {
1822           q-=GetPixelChannels(image);
1823           SetPixelPixelInfo(image,&background,q);
1824         }
1825         break;
1826       }
1827     }
1828     if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1829       status=MagickFalse;
1830     if (image->progress_monitor != (MagickProgressMonitor) NULL)
1831       {
1832         MagickBooleanType
1833           proceed;
1834
1835 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1836         #pragma omp critical (MagickCore_YShearImage)
1837 #endif
1838         proceed=SetImageProgress(image,YShearImageTag,progress++,image->rows);
1839         if (proceed == MagickFalse)
1840           status=MagickFalse;
1841       }
1842   }
1843   image_view=DestroyCacheView(image_view);
1844   return(status);
1845 }
1846 \f
1847 /*
1848 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1849 %                                                                             %
1850 %                                                                             %
1851 %                                                                             %
1852 %   R o t a t e I m a g e                                                     %
1853 %                                                                             %
1854 %                                                                             %
1855 %                                                                             %
1856 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1857 %
1858 %  RotateImage() creates a new image that is a rotated copy of an existing
1859 %  one.  Positive angles rotate counter-clockwise (right-hand rule), while
1860 %  negative angles rotate clockwise.  Rotated images are usually larger than
1861 %  the originals and have 'empty' triangular corners.  X axis.  Empty
1862 %  triangles left over from shearing the image are filled with the background
1863 %  color defined by member 'background_color' of the image.  RotateImage
1864 %  allocates the memory necessary for the new Image structure and returns a
1865 %  pointer to the new image.
1866 %
1867 %  The format of the RotateImage method is:
1868 %
1869 %      Image *RotateImage(const Image *image,const double degrees,
1870 %        ExceptionInfo *exception)
1871 %
1872 %  A description of each parameter follows.
1873 %
1874 %    o image: the image.
1875 %
1876 %    o degrees: Specifies the number of degrees to rotate the image.
1877 %
1878 %    o exception: return any errors or warnings in this structure.
1879 %
1880 */
1881 MagickExport Image *RotateImage(const Image *image,const double degrees,
1882   ExceptionInfo *exception)
1883 {
1884   Image
1885     *rotate_image;
1886
1887   MagickRealType
1888     angle;
1889
1890   PointInfo
1891     shear;
1892
1893   size_t
1894     rotations;
1895
1896   /*
1897     Adjust rotation angle.
1898   */
1899   assert(image != (Image *) NULL);
1900   assert(image->signature == MagickSignature);
1901   if (image->debug != MagickFalse)
1902     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1903   assert(exception != (ExceptionInfo *) NULL);
1904   assert(exception->signature == MagickSignature);
1905   angle=degrees;
1906   while (angle < -45.0)
1907     angle+=360.0;
1908   for (rotations=0; angle > 45.0; rotations++)
1909     angle-=90.0;
1910   rotations%=4;
1911   shear.x=(-tan((double) DegreesToRadians(angle)/2.0));
1912   shear.y=sin((double) DegreesToRadians(angle));
1913   if ((fabs(shear.x) < MagickEpsilon) && (fabs(shear.y) < MagickEpsilon))
1914     return(IntegralRotateImage(image,rotations,exception));
1915   rotate_image=DistortImage(image,ScaleRotateTranslateDistortion,1,&degrees,
1916     MagickTrue,exception);
1917   return(rotate_image);
1918 }
1919 \f
1920 /*
1921 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1922 %                                                                             %
1923 %                                                                             %
1924 %                                                                             %
1925 %   S h e a r I m a g e                                                       %
1926 %                                                                             %
1927 %                                                                             %
1928 %                                                                             %
1929 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1930 %
1931 %  ShearImage() creates a new image that is a shear_image copy of an existing
1932 %  one.  Shearing slides one edge of an image along the X or Y axis, creating
1933 %  a parallelogram.  An X direction shear slides an edge along the X axis,
1934 %  while a Y direction shear slides an edge along the Y axis.  The amount of
1935 %  the shear is controlled by a shear angle.  For X direction shears, x_shear
1936 %  is measured relative to the Y axis, and similarly, for Y direction shears
1937 %  y_shear is measured relative to the X axis.  Empty triangles left over from
1938 %  shearing the image are filled with the background color defined by member
1939 %  'background_color' of the image..  ShearImage() allocates the memory
1940 %  necessary for the new Image structure and returns a pointer to the new image.
1941 %
1942 %  ShearImage() is based on the paper "A Fast Algorithm for General Raster
1943 %  Rotatation" by Alan W. Paeth.
1944 %
1945 %  The format of the ShearImage method is:
1946 %
1947 %      Image *ShearImage(const Image *image,const double x_shear,
1948 %        const double y_shear,ExceptionInfo *exception)
1949 %
1950 %  A description of each parameter follows.
1951 %
1952 %    o image: the image.
1953 %
1954 %    o x_shear, y_shear: Specifies the number of degrees to shear the image.
1955 %
1956 %    o exception: return any errors or warnings in this structure.
1957 %
1958 */
1959 MagickExport Image *ShearImage(const Image *image,const double x_shear,
1960   const double y_shear,ExceptionInfo *exception)
1961 {
1962   Image
1963     *integral_image,
1964     *shear_image;
1965
1966   ssize_t
1967     x_offset,
1968     y_offset;
1969
1970   MagickBooleanType
1971     status;
1972
1973   PointInfo
1974     shear;
1975
1976   RectangleInfo
1977     border_info;
1978
1979   size_t
1980     y_width;
1981
1982   assert(image != (Image *) NULL);
1983   assert(image->signature == MagickSignature);
1984   if (image->debug != MagickFalse)
1985     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1986   assert(exception != (ExceptionInfo *) NULL);
1987   assert(exception->signature == MagickSignature);
1988   if ((x_shear != 0.0) && (fmod(x_shear,90.0) == 0.0))
1989     ThrowImageException(ImageError,"AngleIsDiscontinuous");
1990   if ((y_shear != 0.0) && (fmod(y_shear,90.0) == 0.0))
1991     ThrowImageException(ImageError,"AngleIsDiscontinuous");
1992   /*
1993     Initialize shear angle.
1994   */
1995   integral_image=CloneImage(image,0,0,MagickTrue,exception);
1996   if (integral_image == (Image *) NULL)
1997     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1998   shear.x=(-tan(DegreesToRadians(fmod(x_shear,360.0))));
1999   shear.y=tan(DegreesToRadians(fmod(y_shear,360.0)));
2000   if ((shear.x == 0.0) && (shear.y == 0.0))
2001     return(integral_image);
2002   if (SetImageStorageClass(integral_image,DirectClass,exception) == MagickFalse)
2003     {
2004       integral_image=DestroyImage(integral_image);
2005       return(integral_image);
2006     }
2007   if (integral_image->matte == MagickFalse)
2008     (void) SetImageAlphaChannel(integral_image,OpaqueAlphaChannel,exception);
2009   /*
2010     Compute image size.
2011   */
2012   y_width=image->columns+(ssize_t) floor(fabs(shear.x)*image->rows+0.5);
2013   x_offset=(ssize_t) ceil((double) image->columns+((fabs(shear.x)*image->rows)-
2014     image->columns)/2.0-0.5);
2015   y_offset=(ssize_t) ceil((double) image->rows+((fabs(shear.y)*y_width)-
2016     image->rows)/2.0-0.5);
2017   /*
2018     Surround image with border.
2019   */
2020   integral_image->border_color=integral_image->background_color;
2021   integral_image->compose=CopyCompositeOp;
2022   border_info.width=(size_t) x_offset;
2023   border_info.height=(size_t) y_offset;
2024   shear_image=BorderImage(integral_image,&border_info,image->compose,exception);
2025   integral_image=DestroyImage(integral_image);
2026   if (shear_image == (Image *) NULL)
2027     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
2028   /*
2029     Shear the image.
2030   */
2031   if (shear_image->matte == MagickFalse)
2032     (void) SetImageAlphaChannel(shear_image,OpaqueAlphaChannel,exception);
2033   status=XShearImage(shear_image,shear.x,image->columns,image->rows,x_offset,
2034     (ssize_t) (shear_image->rows-image->rows)/2,exception);
2035   if (status == MagickFalse)
2036     {
2037       shear_image=DestroyImage(shear_image);
2038       return((Image *) NULL);
2039     }
2040   status=YShearImage(shear_image,shear.y,y_width,image->rows,(ssize_t)
2041     (shear_image->columns-y_width)/2,y_offset,exception);
2042   if (status == MagickFalse)
2043     {
2044       shear_image=DestroyImage(shear_image);
2045       return((Image *) NULL);
2046     }
2047   status=CropToFitImage(&shear_image,shear.x,shear.y,(MagickRealType)
2048     image->columns,(MagickRealType) image->rows,MagickFalse,exception);
2049   if (status == MagickFalse)
2050     {
2051       shear_image=DestroyImage(shear_image);
2052       return((Image *) NULL);
2053     }
2054   shear_image->compose=image->compose;
2055   shear_image->page.width=0;
2056   shear_image->page.height=0;
2057   return(shear_image);
2058 }
2059 \f
2060 /*
2061 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2062 %                                                                             %
2063 %                                                                             %
2064 %                                                                             %
2065 %   S h e a r R o t a t e I m a g e                                           %
2066 %                                                                             %
2067 %                                                                             %
2068 %                                                                             %
2069 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2070 %
2071 %  ShearRotateImage() creates a new image that is a rotated copy of an existing
2072 %  one.  Positive angles rotate counter-clockwise (right-hand rule), while
2073 %  negative angles rotate clockwise.  Rotated images are usually larger than
2074 %  the originals and have 'empty' triangular corners.  X axis.  Empty
2075 %  triangles left over from shearing the image are filled with the background
2076 %  color defined by member 'background_color' of the image.  ShearRotateImage
2077 %  allocates the memory necessary for the new Image structure and returns a
2078 %  pointer to the new image.
2079 %
2080 %  ShearRotateImage() is based on the paper "A Fast Algorithm for General
2081 %  Raster Rotatation" by Alan W. Paeth.  ShearRotateImage is adapted from a
2082 %  similar method based on the Paeth paper written by Michael Halle of the
2083 %  Spatial Imaging Group, MIT Media Lab.
2084 %
2085 %  The format of the ShearRotateImage method is:
2086 %
2087 %      Image *ShearRotateImage(const Image *image,const double degrees,
2088 %        ExceptionInfo *exception)
2089 %
2090 %  A description of each parameter follows.
2091 %
2092 %    o image: the image.
2093 %
2094 %    o degrees: Specifies the number of degrees to rotate the image.
2095 %
2096 %    o exception: return any errors or warnings in this structure.
2097 %
2098 */
2099 MagickExport Image *ShearRotateImage(const Image *image,const double degrees,
2100   ExceptionInfo *exception)
2101 {
2102   Image
2103     *integral_image,
2104     *rotate_image;
2105
2106   MagickBooleanType
2107     status;
2108
2109   MagickRealType
2110     angle;
2111
2112   PointInfo
2113     shear;
2114
2115   RectangleInfo
2116     border_info;
2117
2118   size_t
2119     height,
2120     rotations,
2121     width,
2122     y_width;
2123
2124   ssize_t
2125     x_offset,
2126     y_offset;
2127
2128   /*
2129     Adjust rotation angle.
2130   */
2131   assert(image != (Image *) NULL);
2132   assert(image->signature == MagickSignature);
2133   if (image->debug != MagickFalse)
2134     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
2135   assert(exception != (ExceptionInfo *) NULL);
2136   assert(exception->signature == MagickSignature);
2137   angle=degrees;
2138   while (angle < -45.0)
2139     angle+=360.0;
2140   for (rotations=0; angle > 45.0; rotations++)
2141     angle-=90.0;
2142   rotations%=4;
2143   /*
2144     Calculate shear equations.
2145   */
2146   integral_image=IntegralRotateImage(image,rotations,exception);
2147   if (integral_image == (Image *) NULL)
2148     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
2149   shear.x=(-tan((double) DegreesToRadians(angle)/2.0));
2150   shear.y=sin((double) DegreesToRadians(angle));
2151   if ((shear.x == 0.0) && (shear.y == 0.0))
2152     return(integral_image);
2153   if (SetImageStorageClass(integral_image,DirectClass,exception) == MagickFalse)
2154     {
2155       integral_image=DestroyImage(integral_image);
2156       return(integral_image);
2157     }
2158   if (integral_image->matte == MagickFalse)
2159     (void) SetImageAlphaChannel(integral_image,OpaqueAlphaChannel,exception);
2160   /*
2161     Compute image size.
2162   */
2163   width=image->columns;
2164   height=image->rows;
2165   if ((rotations == 1) || (rotations == 3))
2166     {
2167       width=image->rows;
2168       height=image->columns;
2169     }
2170   y_width=width+(ssize_t) floor(fabs(shear.x)*height+0.5);
2171   x_offset=(ssize_t) ceil((double) width+((fabs(shear.y)*height)-width)/2.0-
2172     0.5);
2173   y_offset=(ssize_t) ceil((double) height+((fabs(shear.y)*y_width)-height)/2.0-
2174     0.5);
2175   /*
2176     Surround image with a border.
2177   */
2178   integral_image->border_color=integral_image->background_color;
2179   integral_image->compose=CopyCompositeOp;
2180   border_info.width=(size_t) x_offset;
2181   border_info.height=(size_t) y_offset;
2182   rotate_image=BorderImage(integral_image,&border_info,image->compose,
2183     exception);
2184   integral_image=DestroyImage(integral_image);
2185   if (rotate_image == (Image *) NULL)
2186     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
2187   /*
2188     Rotate the image.
2189   */
2190   status=XShearImage(rotate_image,shear.x,width,height,x_offset,(ssize_t)
2191     (rotate_image->rows-height)/2,exception);
2192   if (status == MagickFalse)
2193     {
2194       rotate_image=DestroyImage(rotate_image);
2195       return((Image *) NULL);
2196     }
2197   status=YShearImage(rotate_image,shear.y,y_width,height,(ssize_t)
2198     (rotate_image->columns-y_width)/2,y_offset,exception);
2199   if (status == MagickFalse)
2200     {
2201       rotate_image=DestroyImage(rotate_image);
2202       return((Image *) NULL);
2203     }
2204   status=XShearImage(rotate_image,shear.x,y_width,rotate_image->rows,(ssize_t)
2205     (rotate_image->columns-y_width)/2,0,exception);
2206   if (status == MagickFalse)
2207     {
2208       rotate_image=DestroyImage(rotate_image);
2209       return((Image *) NULL);
2210     }
2211   status=CropToFitImage(&rotate_image,shear.x,shear.y,(MagickRealType) width,
2212     (MagickRealType) height,MagickTrue,exception);
2213   if (status == MagickFalse)
2214     {
2215       rotate_image=DestroyImage(rotate_image);
2216       return((Image *) NULL);
2217     }
2218   rotate_image->compose=image->compose;
2219   rotate_image->page.width=0;
2220   rotate_image->page.height=0;
2221   return(rotate_image);
2222 }