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