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