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