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