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-2015 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[MagickPathExtent];
 641
 642     (void) FormatLocaleString(angle,MagickPathExtent,"%.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 1:
 763     {
 764       size_t
 765         tile_height,
 766         tile_width;
 767
 768       ssize_t
 769         tile_y;
 770
 771       /*
 772         Rotate 90 degrees.
 773       */
 774       GetPixelCacheTileSize(image,&tile_width,&tile_height);
 775       tile_width=image->columns;
 776 #if defined(MAGICKCORE_OPENMP_SUPPORT)
 777       #pragma omp parallel for schedule(static,4) shared(status) \
 778         magick_threads(image,image,1,1)
 779 #endif
 780       for (tile_y=0; tile_y < (ssize_t) image->rows; tile_y+=(ssize_t) tile_height)
 781       {
 782         register ssize_t
 783           tile_x;
 784
 785         if (status == MagickFalse)
 786           continue;
 787         tile_x=0;
 788         for ( ; tile_x < (ssize_t) image->columns; tile_x+=(ssize_t) tile_width)
 789         {
 790           MagickBooleanType
 791             sync;
 792
 793           register const Quantum
 794             *restrict p;
 795
 796           register Quantum
 797             *restrict q;
 798
 799           register ssize_t
 800             y;
 801
 802           size_t
 803             height,
 804             width;
 805
 806           width=tile_width;
 807           if ((tile_x+(ssize_t) tile_width) > (ssize_t) image->columns)
 808             width=(size_t) (tile_width-(tile_x+tile_width-image->columns));
 809           height=tile_height;
 810           if ((tile_y+(ssize_t) tile_height) > (ssize_t) image->rows)
 811             height=(size_t) (tile_height-(tile_y+tile_height-image->rows));
 812           p=GetCacheViewVirtualPixels(image_view,tile_x,tile_y,width,height,
 813             exception);
 814           if (p == (const Quantum *) NULL)
 815             {
 816               status=MagickFalse;
 817               break;
 818             }
 819           for (y=0; y < (ssize_t) width; y++)
 820           {
 821             register const Quantum
 822               *restrict tile_pixels;
 823
 824             register ssize_t
 825               x;
 826
 827             if (status == MagickFalse)
 828               continue;
 829             q=QueueCacheViewAuthenticPixels(rotate_view,(ssize_t)
 830               (rotate_image->columns-(tile_y+height)),y+tile_x,height,1,
 831               exception);
 832             if (q == (Quantum *) NULL)
 833               {
 834                 status=MagickFalse;
 835                 continue;
 836               }
 837             tile_pixels=p+((height-1)*width+y)*GetPixelChannels(image);
 838             for (x=0; x < (ssize_t) height; x++)
 839             {
 840               register ssize_t
 841                 i;
 842
 843               if (GetPixelReadMask(image,tile_pixels) == 0)
 844                 {
 845                   tile_pixels-=width*GetPixelChannels(image);
 846                   q+=GetPixelChannels(rotate_image);
 847                   continue;
 848                 }
 849               for (i=0; i < (ssize_t) GetPixelChannels(image); i++)
 850               {
 851                 PixelChannel channel=GetPixelChannelChannel(image,i);
 852                 PixelTrait traits=GetPixelChannelTraits(image,channel);
 853                 PixelTrait rotate_traits=GetPixelChannelTraits(rotate_image,
 854                   channel);
 855                 if ((traits == UndefinedPixelTrait) ||
 856                     (rotate_traits == UndefinedPixelTrait))
 857                   continue;
 858                 SetPixelChannel(rotate_image,channel,tile_pixels[i],q);
 859               }
 860               tile_pixels-=width*GetPixelChannels(image);
 861               q+=GetPixelChannels(rotate_image);
 862             }
 863             sync=SyncCacheViewAuthenticPixels(rotate_view,exception);
 864             if (sync == MagickFalse)
 865               status=MagickFalse;
 866           }
 867         }
 868         if (image->progress_monitor != (MagickProgressMonitor) NULL)
 869           {
 870             MagickBooleanType
 871               proceed;
 872
 873 #if defined(MAGICKCORE_OPENMP_SUPPORT)
 874             #pragma omp critical (MagickCore_IntegralRotateImage)
 875 #endif
 876             proceed=SetImageProgress(image,RotateImageTag,progress+=tile_height,
 877               image->rows);
 878             if (proceed == MagickFalse)
 879               status=MagickFalse;
 880           }
 881       }
 882       (void) SetImageProgress(image,RotateImageTag,(MagickOffsetType)
 883         image->rows-1,image->rows);
 884       Swap(page.width,page.height);
 885       Swap(page.x,page.y);
 886       if (page.width != 0)
 887         page.x=(ssize_t) (page.width-rotate_image->columns-page.x);
 888       break;
 889     }
 890     case 2:
 891     {
 892       /*
 893         Rotate 180 degrees.
 894       */
 895 #if defined(MAGICKCORE_OPENMP_SUPPORT)
 896       #pragma omp parallel for schedule(static,4) shared(status) \
 897         magick_threads(image,image,1,1)
 898 #endif
 899       for (y=0; y < (ssize_t) image->rows; y++)
 900       {
 901         MagickBooleanType
 902           sync;
 903
 904         register const Quantum
 905           *restrict p;
 906
 907         register Quantum
 908           *restrict q;
 909
 910         register ssize_t
 911           x;
 912
 913         if (status == MagickFalse)
 914           continue;
 915         p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
 916         q=QueueCacheViewAuthenticPixels(rotate_view,0,(ssize_t) (image->rows-y-
 917           1),image->columns,1,exception);
 918         if ((p == (const Quantum *) NULL) || (q == (Quantum *) NULL))
 919           {
 920             status=MagickFalse;
 921             continue;
 922           }
 923         q+=GetPixelChannels(rotate_image)*image->columns;
 924         for (x=0; x < (ssize_t) image->columns; x++)
 925         {
 926           register ssize_t
 927             i;
 928
 929           q-=GetPixelChannels(rotate_image);
 930           if (GetPixelReadMask(image,p) == 0)
 931             {
 932               p+=GetPixelChannels(image);
 933               continue;
 934             }
 935           for (i=0; i < (ssize_t) GetPixelChannels(image); i++)
 936           {
 937             PixelChannel channel=GetPixelChannelChannel(image,i);
 938             PixelTrait traits=GetPixelChannelTraits(image,channel);
 939             PixelTrait rotate_traits=GetPixelChannelTraits(rotate_image,
 940               channel);
 941             if ((traits == UndefinedPixelTrait) ||
 942                 (rotate_traits == UndefinedPixelTrait))
 943               continue;
 944             SetPixelChannel(rotate_image,channel,p[i],q);
 945           }
 946           p+=GetPixelChannels(image);
 947         }
 948         sync=SyncCacheViewAuthenticPixels(rotate_view,exception);
 949         if (sync == MagickFalse)
 950           status=MagickFalse;
 951         if (image->progress_monitor != (MagickProgressMonitor) NULL)
 952           {
 953             MagickBooleanType
 954               proceed;
 955
 956 #if defined(MAGICKCORE_OPENMP_SUPPORT)
 957             #pragma omp critical (MagickCore_IntegralRotateImage)
 958 #endif
 959             proceed=SetImageProgress(image,RotateImageTag,progress++,
 960               image->rows);
 961             if (proceed == MagickFalse)
 962               status=MagickFalse;
 963           }
 964       }
 965       (void) SetImageProgress(image,RotateImageTag,(MagickOffsetType)
 966         image->rows-1,image->rows);
 967       Swap(page.width,page.height);
 968       Swap(page.x,page.y);
 969       if (page.width != 0)
 970         page.x=(ssize_t) (page.width-rotate_image->columns-page.x);
 971       break;
 972     }
 973     case 3:
 974     {
 975       size_t
 976         tile_height,
 977         tile_width;
 978
 979       ssize_t
 980         tile_y;
 981
 982       /*
 983         Rotate 270 degrees.
 984       */
 985       GetPixelCacheTileSize(image,&tile_width,&tile_height);
 986       tile_width=image->columns;
 987 #if defined(MAGICKCORE_OPENMP_SUPPORT)
 988       #pragma omp parallel for schedule(static,4) shared(status) \
 989         magick_threads(image,image,1,1)
 990 #endif
 991       for (tile_y=0; tile_y < (ssize_t) image->rows; tile_y+=(ssize_t) tile_height)
 992       {
 993         register ssize_t
 994           tile_x;
 995
 996         if (status == MagickFalse)
 997           continue;
 998         tile_x=0;
 999         for ( ; tile_x < (ssize_t) image->columns; tile_x+=(ssize_t) tile_width)
1000         {
1001           MagickBooleanType
1002             sync;
1003
1004           register const Quantum
1005             *restrict p;
1006
1007           register Quantum
1008             *restrict q;
1009
1010           register ssize_t
1011             y;
1012
1013           size_t
1014             height,
1015             width;
1016
1017           width=tile_width;
1018           if ((tile_x+(ssize_t) tile_width) > (ssize_t) image->columns)
1019             width=(size_t) (tile_width-(tile_x+tile_width-image->columns));
1020           height=tile_height;
1021           if ((tile_y+(ssize_t) tile_height) > (ssize_t) image->rows)
1022             height=(size_t) (tile_height-(tile_y+tile_height-image->rows));
1023           p=GetCacheViewVirtualPixels(image_view,tile_x,tile_y,width,height,
1024             exception);
1025           if (p == (const Quantum *) NULL)
1026             {
1027               status=MagickFalse;
1028               break;
1029             }
1030           for (y=0; y < (ssize_t) width; y++)
1031           {
1032             register const Quantum
1033               *restrict tile_pixels;
1034
1035             register ssize_t
1036               x;
1037
1038             if (status == MagickFalse)
1039               continue;
1040             q=QueueCacheViewAuthenticPixels(rotate_view,tile_y,(ssize_t) (y+
1041               rotate_image->rows-(tile_x+width)),height,1,exception);
1042             if (q == (Quantum *) NULL)
1043               {
1044                 status=MagickFalse;
1045                 continue;
1046               }
1047             tile_pixels=p+((width-1)-y)*GetPixelChannels(image);
1048             for (x=0; x < (ssize_t) height; x++)
1049             {
1050               register ssize_t
1051                 i;
1052
1053               if (GetPixelReadMask(image,tile_pixels) == 0)
1054                 {
1055                   tile_pixels+=width*GetPixelChannels(image);
1056                   q+=GetPixelChannels(rotate_image);
1057                   continue;
1058                 }
1059               for (i=0; i < (ssize_t) GetPixelChannels(image); i++)
1060               {
1061                 PixelChannel channel=GetPixelChannelChannel(image,i);
1062                 PixelTrait traits=GetPixelChannelTraits(image,channel);
1063                 PixelTrait rotate_traits=GetPixelChannelTraits(rotate_image,
1064                   channel);
1065                 if ((traits == UndefinedPixelTrait) ||
1066                     (rotate_traits == UndefinedPixelTrait))
1067                   continue;
1068                 SetPixelChannel(rotate_image,channel,tile_pixels[i],q);
1069               }
1070               tile_pixels+=width*GetPixelChannels(image);
1071               q+=GetPixelChannels(rotate_image);
1072             }
1073 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1074             #pragma omp critical (MagickCore_IntegralRotateImage)
1075 #endif
1076             sync=SyncCacheViewAuthenticPixels(rotate_view,exception);
1077             if (sync == MagickFalse)
1078               status=MagickFalse;
1079           }
1080         }
1081         if (image->progress_monitor != (MagickProgressMonitor) NULL)
1082           {
1083             MagickBooleanType
1084               proceed;
1085
1086             proceed=SetImageProgress(image,RotateImageTag,progress+=tile_height,
1087               image->rows);
1088             if (proceed == MagickFalse)
1089               status=MagickFalse;
1090           }
1091       }
1092       (void) SetImageProgress(image,RotateImageTag,(MagickOffsetType)
1093         image->rows-1,image->rows);
1094       Swap(page.width,page.height);
1095       Swap(page.x,page.y);
1096       if (page.width != 0)
1097         page.x=(ssize_t) (page.width-rotate_image->columns-page.x);
1098       break;
1099     }
1100     default:
1101       break;
1102   }
1103   rotate_view=DestroyCacheView(rotate_view);
1104   image_view=DestroyCacheView(image_view);
1105   rotate_image->type=image->type;
1106   rotate_image->page=page;
1107   if (status == MagickFalse)
1108     rotate_image=DestroyImage(rotate_image);
1109   return(rotate_image);
1110 }
1111 \f
1112 /*
1113 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1114 %                                                                             %
1115 %                                                                             %
1116 %                                                                             %
1117 +   X S h e a r I m a g e                                                     %
1118 %                                                                             %
1119 %                                                                             %
1120 %                                                                             %
1121 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1122 %
1123 %  XShearImage() shears the image in the X direction with a shear angle of
1124 %  'degrees'.  Positive angles shear counter-clockwise (right-hand rule), and
1125 %  negative angles shear clockwise.  Angles are measured relative to a vertical
1126 %  Y-axis.  X shears will widen an image creating 'empty' triangles on the left
1127 %  and right sides of the source image.
1128 %
1129 %  The format of the XShearImage method is:
1130 %
1131 %      MagickBooleanType XShearImage(Image *image,const double degrees,
1132 %        const size_t width,const size_t height,
1133 %        const ssize_t x_offset,const ssize_t y_offset,ExceptionInfo *exception)
1134 %
1135 %  A description of each parameter follows.
1136 %
1137 %    o image: the image.
1138 %
1139 %    o degrees: A double representing the shearing angle along the X
1140 %      axis.
1141 %
1142 %    o width, height, x_offset, y_offset: Defines a region of the image
1143 %      to shear.
1144 %
1145 %    o exception: return any errors or warnings in this structure.
1146 %
1147 */
1148 static MagickBooleanType XShearImage(Image *image,const double degrees,
1149   const size_t width,const size_t height,const ssize_t x_offset,
1150   const ssize_t y_offset,ExceptionInfo *exception)
1151 {
1152 #define XShearImageTag  "XShear/Image"
1153
1154   typedef enum
1155   {
1156     LEFT,
1157     RIGHT
1158   } ShearDirection;
1159
1160   CacheView
1161     *image_view;
1162
1163   MagickBooleanType
1164     status;
1165
1166   MagickOffsetType
1167     progress;
1168
1169   PixelInfo
1170     background;
1171
1172   ssize_t
1173     y;
1174
1175   /*
1176     X shear image.
1177   */
1178   assert(image != (Image *) NULL);
1179   assert(image->signature == MagickSignature);
1180   if (image->debug != MagickFalse)
1181     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1182   status=MagickTrue;
1183   background=image->background_color;
1184   progress=0;
1185   image_view=AcquireAuthenticCacheView(image,exception);
1186 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1187   #pragma omp parallel for schedule(static,4) shared(progress,status) \
1188     magick_threads(image,image,height,1)
1189 #endif
1190   for (y=0; y < (ssize_t) height; y++)
1191   {
1192     PixelInfo
1193       pixel,
1194       source,
1195       destination;
1196
1197     double
1198       area,
1199       displacement;
1200
1201     register Quantum
1202       *restrict p,
1203       *restrict q;
1204
1205     register ssize_t
1206       i;
1207
1208     ShearDirection
1209       direction;
1210
1211     ssize_t
1212       step;
1213
1214     if (status == MagickFalse)
1215       continue;
1216     p=GetCacheViewAuthenticPixels(image_view,0,y_offset+y,image->columns,1,
1217       exception);
1218     if (p == (Quantum *) NULL)
1219       {
1220         status=MagickFalse;
1221         continue;
1222       }
1223     p+=x_offset*GetPixelChannels(image);
1224     displacement=degrees*(double) (y-height/2.0);
1225     if (displacement == 0.0)
1226       continue;
1227     if (displacement > 0.0)
1228       direction=RIGHT;
1229     else
1230       {
1231         displacement*=(-1.0);
1232         direction=LEFT;
1233       }
1234     step=(ssize_t) floor((double) displacement);
1235     area=(double) (displacement-step);
1236     step++;
1237     pixel=background;
1238     GetPixelInfo(image,&source);
1239     GetPixelInfo(image,&destination);
1240     switch (direction)
1241     {
1242       case LEFT:
1243       {
1244         /*
1245           Transfer pixels left-to-right.
1246         */
1247         if (step > x_offset)
1248           break;
1249         q=p-step*GetPixelChannels(image);
1250         for (i=0; i < (ssize_t) width; i++)
1251         {
1252           if ((x_offset+i) < step)
1253             {
1254               p+=GetPixelChannels(image);
1255               GetPixelInfoPixel(image,p,&pixel);
1256               q+=GetPixelChannels(image);
1257               continue;
1258             }
1259           GetPixelInfoPixel(image,p,&source);
1260           CompositePixelInfoAreaBlend(&pixel,(double) pixel.alpha,
1261             &source,(double) GetPixelAlpha(image,p),area,&destination);
1262           SetPixelViaPixelInfo(image,&destination,q);
1263           GetPixelInfoPixel(image,p,&pixel);
1264           p+=GetPixelChannels(image);
1265           q+=GetPixelChannels(image);
1266         }
1267         CompositePixelInfoAreaBlend(&pixel,(double) pixel.alpha,
1268           &background,(double) background.alpha,area,&destination);
1269         SetPixelViaPixelInfo(image,&destination,q);
1270         q+=GetPixelChannels(image);
1271         for (i=0; i < (step-1); i++)
1272         {
1273           SetPixelViaPixelInfo(image,&background,q);
1274           q+=GetPixelChannels(image);
1275         }
1276         break;
1277       }
1278       case RIGHT:
1279       {
1280         /*
1281           Transfer pixels right-to-left.
1282         */
1283         p+=width*GetPixelChannels(image);
1284         q=p+step*GetPixelChannels(image);
1285         for (i=0; i < (ssize_t) width; i++)
1286         {
1287           p-=GetPixelChannels(image);
1288           q-=GetPixelChannels(image);
1289           if ((size_t) (x_offset+width+step-i) > image->columns)
1290             continue;
1291           GetPixelInfoPixel(image,p,&source);
1292           CompositePixelInfoAreaBlend(&pixel,(double) pixel.alpha,
1293             &source,(double) GetPixelAlpha(image,p),area,&destination);
1294           SetPixelViaPixelInfo(image,&destination,q);
1295           GetPixelInfoPixel(image,p,&pixel);
1296         }
1297         CompositePixelInfoAreaBlend(&pixel,(double) pixel.alpha,
1298           &background,(double) background.alpha,area,&destination);
1299         q-=GetPixelChannels(image);
1300         SetPixelViaPixelInfo(image,&destination,q);
1301         for (i=0; i < (step-1); i++)
1302         {
1303           q-=GetPixelChannels(image);
1304           SetPixelViaPixelInfo(image,&background,q);
1305         }
1306         break;
1307       }
1308     }
1309     if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1310       status=MagickFalse;
1311     if (image->progress_monitor != (MagickProgressMonitor) NULL)
1312       {
1313         MagickBooleanType
1314           proceed;
1315
1316 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1317         #pragma omp critical (MagickCore_XShearImage)
1318 #endif
1319         proceed=SetImageProgress(image,XShearImageTag,progress++,height);
1320         if (proceed == MagickFalse)
1321           status=MagickFalse;
1322       }
1323   }
1324   image_view=DestroyCacheView(image_view);
1325   return(status);
1326 }
1327 \f
1328 /*
1329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1330 %                                                                             %
1331 %                                                                             %
1332 %                                                                             %
1333 +   Y S h e a r I m a g e                                                     %
1334 %                                                                             %
1335 %                                                                             %
1336 %                                                                             %
1337 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1338 %
1339 %  YShearImage shears the image in the Y direction with a shear angle of
1340 %  'degrees'.  Positive angles shear counter-clockwise (right-hand rule), and
1341 %  negative angles shear clockwise.  Angles are measured relative to a
1342 %  horizontal X-axis.  Y shears will increase the height of an image creating
1343 %  'empty' triangles on the top and bottom of the source image.
1344 %
1345 %  The format of the YShearImage method is:
1346 %
1347 %      MagickBooleanType YShearImage(Image *image,const double degrees,
1348 %        const size_t width,const size_t height,
1349 %        const ssize_t x_offset,const ssize_t y_offset,ExceptionInfo *exception)
1350 %
1351 %  A description of each parameter follows.
1352 %
1353 %    o image: the image.
1354 %
1355 %    o degrees: A double representing the shearing angle along the Y
1356 %      axis.
1357 %
1358 %    o width, height, x_offset, y_offset: Defines a region of the image
1359 %      to shear.
1360 %
1361 %    o exception: return any errors or warnings in this structure.
1362 %
1363 */
1364 static MagickBooleanType YShearImage(Image *image,const double degrees,
1365   const size_t width,const size_t height,const ssize_t x_offset,
1366   const ssize_t y_offset,ExceptionInfo *exception)
1367 {
1368 #define YShearImageTag  "YShear/Image"
1369
1370   typedef enum
1371   {
1372     UP,
1373     DOWN
1374   } ShearDirection;
1375
1376   CacheView
1377     *image_view;
1378
1379   MagickBooleanType
1380     status;
1381
1382   MagickOffsetType
1383     progress;
1384
1385   PixelInfo
1386     background;
1387
1388   ssize_t
1389     x;
1390
1391   /*
1392     Y Shear image.
1393   */
1394   assert(image != (Image *) NULL);
1395   assert(image->signature == MagickSignature);
1396   if (image->debug != MagickFalse)
1397     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1398   status=MagickTrue;
1399   progress=0;
1400   background=image->background_color;
1401   image_view=AcquireAuthenticCacheView(image,exception);
1402 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1403   #pragma omp parallel for schedule(static,4) shared(progress,status) \
1404     magick_threads(image,image,width,1)
1405 #endif
1406   for (x=0; x < (ssize_t) width; x++)
1407   {
1408     ssize_t
1409       step;
1410
1411     double
1412       area,
1413       displacement;
1414
1415     PixelInfo
1416       pixel,
1417       source,
1418       destination;
1419
1420     register Quantum
1421       *restrict p,
1422       *restrict q;
1423
1424     register ssize_t
1425       i;
1426
1427     ShearDirection
1428       direction;
1429
1430     if (status == MagickFalse)
1431       continue;
1432     p=GetCacheViewAuthenticPixels(image_view,x_offset+x,0,1,image->rows,
1433       exception);
1434     if (p == (Quantum *) NULL)
1435       {
1436         status=MagickFalse;
1437         continue;
1438       }
1439     p+=y_offset*GetPixelChannels(image);
1440     displacement=degrees*(double) (x-width/2.0);
1441     if (displacement == 0.0)
1442       continue;
1443     if (displacement > 0.0)
1444       direction=DOWN;
1445     else
1446       {
1447         displacement*=(-1.0);
1448         direction=UP;
1449       }
1450     step=(ssize_t) floor((double) displacement);
1451     area=(double) (displacement-step);
1452     step++;
1453     pixel=background;
1454     GetPixelInfo(image,&source);
1455     GetPixelInfo(image,&destination);
1456     switch (direction)
1457     {
1458       case UP:
1459       {
1460         /*
1461           Transfer pixels top-to-bottom.
1462         */
1463         if (step > y_offset)
1464           break;
1465         q=p-step*GetPixelChannels(image);
1466         for (i=0; i < (ssize_t) height; i++)
1467         {
1468           if ((y_offset+i) < step)
1469             {
1470               p+=GetPixelChannels(image);
1471               GetPixelInfoPixel(image,p,&pixel);
1472               q+=GetPixelChannels(image);
1473               continue;
1474             }
1475           GetPixelInfoPixel(image,p,&source);
1476           CompositePixelInfoAreaBlend(&pixel,(double) pixel.alpha,
1477             &source,(double) GetPixelAlpha(image,p),area,
1478             &destination);
1479           SetPixelViaPixelInfo(image,&destination,q);
1480           GetPixelInfoPixel(image,p,&pixel);
1481           p+=GetPixelChannels(image);
1482           q+=GetPixelChannels(image);
1483         }
1484         CompositePixelInfoAreaBlend(&pixel,(double) pixel.alpha,
1485           &background,(double) background.alpha,area,&destination);
1486         SetPixelViaPixelInfo(image,&destination,q);
1487         q+=GetPixelChannels(image);
1488         for (i=0; i < (step-1); i++)
1489         {
1490           SetPixelViaPixelInfo(image,&background,q);
1491           q+=GetPixelChannels(image);
1492         }
1493         break;
1494       }
1495       case DOWN:
1496       {
1497         /*
1498           Transfer pixels bottom-to-top.
1499         */
1500         p+=height*GetPixelChannels(image);
1501         q=p+step*GetPixelChannels(image);
1502         for (i=0; i < (ssize_t) height; i++)
1503         {
1504           p-=GetPixelChannels(image);
1505           q-=GetPixelChannels(image);
1506           if ((size_t) (y_offset+height+step-i) > image->rows)
1507             continue;
1508           GetPixelInfoPixel(image,p,&source);
1509           CompositePixelInfoAreaBlend(&pixel,(double) pixel.alpha,
1510             &source,(double) GetPixelAlpha(image,p),area,
1511             &destination);
1512           SetPixelViaPixelInfo(image,&destination,q);
1513           GetPixelInfoPixel(image,p,&pixel);
1514         }
1515         CompositePixelInfoAreaBlend(&pixel,(double) pixel.alpha,
1516           &background,(double) background.alpha,area,&destination);
1517         q-=GetPixelChannels(image);
1518         SetPixelViaPixelInfo(image,&destination,q);
1519         for (i=0; i < (step-1); i++)
1520         {
1521           q-=GetPixelChannels(image);
1522           SetPixelViaPixelInfo(image,&background,q);
1523         }
1524         break;
1525       }
1526     }
1527     if (SyncCacheViewAuthenticPixels(image_view,exception) == MagickFalse)
1528       status=MagickFalse;
1529     if (image->progress_monitor != (MagickProgressMonitor) NULL)
1530       {
1531         MagickBooleanType
1532           proceed;
1533
1534 #if defined(MAGICKCORE_OPENMP_SUPPORT)
1535         #pragma omp critical (MagickCore_YShearImage)
1536 #endif
1537         proceed=SetImageProgress(image,YShearImageTag,progress++,image->rows);
1538         if (proceed == MagickFalse)
1539           status=MagickFalse;
1540       }
1541   }
1542   image_view=DestroyCacheView(image_view);
1543   return(status);
1544 }
1545 \f
1546 /*
1547 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1548 %                                                                             %
1549 %                                                                             %
1550 %                                                                             %
1551 %   S h e a r I m a g e                                                       %
1552 %                                                                             %
1553 %                                                                             %
1554 %                                                                             %
1555 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1556 %
1557 %  ShearImage() creates a new image that is a shear_image copy of an existing
1558 %  one.  Shearing slides one edge of an image along the X or Y axis, creating
1559 %  a parallelogram.  An X direction shear slides an edge along the X axis,
1560 %  while a Y direction shear slides an edge along the Y axis.  The amount of
1561 %  the shear is controlled by a shear angle.  For X direction shears, x_shear
1562 %  is measured relative to the Y axis, and similarly, for Y direction shears
1563 %  y_shear is measured relative to the X axis.  Empty triangles left over from
1564 %  shearing the image are filled with the background color defined by member
1565 %  'background_color' of the image..  ShearImage() allocates the memory
1566 %  necessary for the new Image structure and returns a pointer to the new image.
1567 %
1568 %  ShearImage() is based on the paper "A Fast Algorithm for General Raster
1569 %  Rotatation" by Alan W. Paeth.
1570 %
1571 %  The format of the ShearImage method is:
1572 %
1573 %      Image *ShearImage(const Image *image,const double x_shear,
1574 %        const double y_shear,ExceptionInfo *exception)
1575 %
1576 %  A description of each parameter follows.
1577 %
1578 %    o image: the image.
1579 %
1580 %    o x_shear, y_shear: Specifies the number of degrees to shear the image.
1581 %
1582 %    o exception: return any errors or warnings in this structure.
1583 %
1584 */
1585 MagickExport Image *ShearImage(const Image *image,const double x_shear,
1586   const double y_shear,ExceptionInfo *exception)
1587 {
1588   Image
1589     *integral_image,
1590     *shear_image;
1591
1592   MagickBooleanType
1593     status;
1594
1595   PointInfo
1596     shear;
1597
1598   RectangleInfo
1599     border_info,
1600     bounds;
1601
1602   assert(image != (Image *) NULL);
1603   assert(image->signature == MagickSignature);
1604   if (image->debug != MagickFalse)
1605     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1606   assert(exception != (ExceptionInfo *) NULL);
1607   assert(exception->signature == MagickSignature);
1608   if ((x_shear != 0.0) && (fmod(x_shear,90.0) == 0.0))
1609     ThrowImageException(ImageError,"AngleIsDiscontinuous");
1610   if ((y_shear != 0.0) && (fmod(y_shear,90.0) == 0.0))
1611     ThrowImageException(ImageError,"AngleIsDiscontinuous");
1612   /*
1613     Initialize shear angle.
1614   */
1615   integral_image=CloneImage(image,0,0,MagickTrue,exception);
1616   if (integral_image == (Image *) NULL)
1617     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1618   shear.x=(-tan(DegreesToRadians(fmod(x_shear,360.0))));
1619   shear.y=tan(DegreesToRadians(fmod(y_shear,360.0)));
1620   if ((shear.x == 0.0) && (shear.y == 0.0))
1621     return(integral_image);
1622   if (SetImageStorageClass(integral_image,DirectClass,exception) == MagickFalse)
1623     {
1624       integral_image=DestroyImage(integral_image);
1625       return(integral_image);
1626     }
1627   if (integral_image->alpha_trait == UndefinedPixelTrait)
1628     (void) SetImageAlphaChannel(integral_image,OpaqueAlphaChannel,exception);
1629   /*
1630     Compute image size.
1631   */
1632   bounds.width=image->columns+(ssize_t) floor(fabs(shear.x)*image->rows+0.5);
1633   bounds.x=(ssize_t) ceil((double) image->columns+((fabs(shear.x)*image->rows)-
1634     image->columns)/2.0-0.5);
1635   bounds.y=(ssize_t) ceil((double) image->rows+((fabs(shear.y)*bounds.width)-
1636     image->rows)/2.0-0.5);
1637   /*
1638     Surround image with border.
1639   */
1640   integral_image->border_color=integral_image->background_color;
1641   integral_image->compose=CopyCompositeOp;
1642   border_info.width=(size_t) bounds.x;
1643   border_info.height=(size_t) bounds.y;
1644   shear_image=BorderImage(integral_image,&border_info,image->compose,exception);
1645   integral_image=DestroyImage(integral_image);
1646   if (shear_image == (Image *) NULL)
1647     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1648   /*
1649     Shear the image.
1650   */
1651   if (shear_image->alpha_trait == UndefinedPixelTrait)
1652     (void) SetImageAlphaChannel(shear_image,OpaqueAlphaChannel,exception);
1653   status=XShearImage(shear_image,shear.x,image->columns,image->rows,bounds.x,
1654     (ssize_t) (shear_image->rows-image->rows)/2,exception);
1655   if (status == MagickFalse)
1656     {
1657       shear_image=DestroyImage(shear_image);
1658       return((Image *) NULL);
1659     }
1660   status=YShearImage(shear_image,shear.y,bounds.width,image->rows,(ssize_t)
1661     (shear_image->columns-bounds.width)/2,bounds.y,exception);
1662   if (status == MagickFalse)
1663     {
1664       shear_image=DestroyImage(shear_image);
1665       return((Image *) NULL);
1666     }
1667   status=CropToFitImage(&shear_image,shear.x,shear.y,(MagickRealType)
1668     image->columns,(MagickRealType) image->rows,MagickFalse,exception);
1669   shear_image->compose=image->compose;
1670   shear_image->page.width=0;
1671   shear_image->page.height=0;
1672   if (status == MagickFalse)
1673     shear_image=DestroyImage(shear_image);
1674   return(shear_image);
1675 }
1676 \f
1677 /*
1678 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1679 %                                                                             %
1680 %                                                                             %
1681 %                                                                             %
1682 %   S h e a r R o t a t e I m a g e                                           %
1683 %                                                                             %
1684 %                                                                             %
1685 %                                                                             %
1686 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1687 %
1688 %  ShearRotateImage() creates a new image that is a rotated copy of an existing
1689 %  one.  Positive angles rotate counter-clockwise (right-hand rule), while
1690 %  negative angles rotate clockwise.  Rotated images are usually larger than
1691 %  the originals and have 'empty' triangular corners.  X axis.  Empty
1692 %  triangles left over from shearing the image are filled with the background
1693 %  color defined by member 'background_color' of the image.  ShearRotateImage
1694 %  allocates the memory necessary for the new Image structure and returns a
1695 %  pointer to the new image.
1696 %
1697 %  ShearRotateImage() is based on the paper "A Fast Algorithm for General
1698 %  Raster Rotatation" by Alan W. Paeth.  ShearRotateImage is adapted from a
1699 %  similar method based on the Paeth paper written by Michael Halle of the
1700 %  Spatial Imaging Group, MIT Media Lab.
1701 %
1702 %  The format of the ShearRotateImage method is:
1703 %
1704 %      Image *ShearRotateImage(const Image *image,const double degrees,
1705 %        ExceptionInfo *exception)
1706 %
1707 %  A description of each parameter follows.
1708 %
1709 %    o image: the image.
1710 %
1711 %    o degrees: Specifies the number of degrees to rotate the image.
1712 %
1713 %    o exception: return any errors or warnings in this structure.
1714 %
1715 */
1716 MagickExport Image *ShearRotateImage(const Image *image,const double degrees,
1717   ExceptionInfo *exception)
1718 {
1719   Image
1720     *integral_image,
1721     *rotate_image;
1722
1723   MagickBooleanType
1724     status;
1725
1726   MagickRealType
1727     angle;
1728
1729   PointInfo
1730     shear;
1731
1732   RectangleInfo
1733     border_info,
1734     bounds;
1735
1736   size_t
1737     height,
1738     rotations,
1739     shear_width,
1740     width;
1741
1742   /*
1743     Adjust rotation angle.
1744   */
1745   assert(image != (Image *) NULL);
1746   assert(image->signature == MagickSignature);
1747   if (image->debug != MagickFalse)
1748     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1749   assert(exception != (ExceptionInfo *) NULL);
1750   assert(exception->signature == MagickSignature);
1751   angle=degrees;
1752   while (angle < -45.0)
1753     angle+=360.0;
1754   for (rotations=0; angle > 45.0; rotations++)
1755     angle-=90.0;
1756   rotations%=4;
1757   /*
1758     Calculate shear equations.
1759   */
1760   integral_image=IntegralRotateImage(image,rotations,exception);
1761   if (integral_image == (Image *) NULL)
1762     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1763   shear.x=(-tan((double) DegreesToRadians(angle)/2.0));
1764   shear.y=sin((double) DegreesToRadians(angle));
1765   if ((shear.x == 0.0) && (shear.y == 0.0))
1766     return(integral_image);
1767   if (SetImageStorageClass(integral_image,DirectClass,exception) == MagickFalse)
1768     {
1769       integral_image=DestroyImage(integral_image);
1770       return(integral_image);
1771     }
1772   if (integral_image->alpha_trait == UndefinedPixelTrait)
1773     (void) SetImageAlphaChannel(integral_image,OpaqueAlphaChannel,exception);
1774   /*
1775     Compute maximum bounds for 3 shear operations.
1776   */
1777   width=integral_image->columns;
1778   height=integral_image->rows;
1779   bounds.width=(size_t) floor(fabs((double) height*shear.x)+width+0.5);
1780   bounds.height=(size_t) floor(fabs((double) bounds.width*shear.y)+height+0.5);
1781   shear_width=(size_t) floor(fabs((double) bounds.height*shear.x)+
1782     bounds.width+0.5);
1783   bounds.x=(ssize_t) floor((double) ((shear_width > bounds.width) ? width :
1784     bounds.width-shear_width+2)/2.0+0.5);
1785   bounds.y=(ssize_t) floor(((double) bounds.height-height+2)/2.0+0.5);
1786   /*
1787     Surround image with a border.
1788   */
1789   integral_image->border_color=integral_image->background_color;
1790   integral_image->compose=CopyCompositeOp;
1791   border_info.width=(size_t) bounds.x;
1792   border_info.height=(size_t) bounds.y;
1793   rotate_image=BorderImage(integral_image,&border_info,image->compose,
1794     exception);
1795   integral_image=DestroyImage(integral_image);
1796   if (rotate_image == (Image *) NULL)
1797     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1798   /*
1799     Rotate the image.
1800   */
1801   status=XShearImage(rotate_image,shear.x,width,height,bounds.x,(ssize_t)
1802     (rotate_image->rows-height)/2,exception);
1803   if (status == MagickFalse)
1804     {
1805       rotate_image=DestroyImage(rotate_image);
1806       return((Image *) NULL);
1807     }
1808   status=YShearImage(rotate_image,shear.y,bounds.width,height,(ssize_t)
1809     (rotate_image->columns-bounds.width)/2,bounds.y,exception);
1810   if (status == MagickFalse)
1811     {
1812       rotate_image=DestroyImage(rotate_image);
1813       return((Image *) NULL);
1814     }
1815   status=XShearImage(rotate_image,shear.x,bounds.width,bounds.height,(ssize_t)
1816     (rotate_image->columns-bounds.width)/2,(ssize_t) (rotate_image->rows-
1817     bounds.height)/2,exception);
1818   if (status == MagickFalse)
1819     {
1820       rotate_image=DestroyImage(rotate_image);
1821       return((Image *) NULL);
1822     }
1823   status=CropToFitImage(&rotate_image,shear.x,shear.y,(MagickRealType) width,
1824     (MagickRealType) height,MagickTrue,exception);
1825   rotate_image->compose=image->compose;
1826   rotate_image->page.width=0;
1827   rotate_image->page.height=0;
1828   if (status == MagickFalse)
1829     rotate_image=DestroyImage(rotate_image);
1830   return(rotate_image);
1831 }