shear.c

Go to the documentation of this file.

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%                      SSSSS  H   H  EEEEE   AAA    RRRR                      %
%                      SS     H   H  E      A   A   R   R                     %
%                       SSS   HHHHH  EEE    AAAAA   RRRR                      %
%                         SS  H   H  E      A   A   R R                       %
%                      SSSSS  H   H  EEEEE  A   A   R  R                      %
%                                                                             %
%                                                                             %
%    MagickCore Methods to Shear or Rotate an Image by an Arbitrary Angle     %
%                                                                             %
%                               Software Design                               %
%                                 John Cristy                                 %
%                                  July 1992                                  %
%                                                                             %
%                                                                             %
%  Copyright 1999-2008 ImageMagick Studio LLC, a non-profit organization      %
%  dedicated to making software imaging solutions freely available.           %
%                                                                             %
%  You may not use this file except in compliance with the License.  You may  %
%  obtain a copy of the License at                                            %
%                                                                             %
%    http://www.imagemagick.org/script/license.php                            %
%                                                                             %
%  Unless required by applicable law or agreed to in writing, software        %
%  distributed under the License is distributed on an "AS IS" BASIS,          %
%  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
%  See the License for the specific language governing permissions and        %
%  limitations under the License.                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  The RotateImage, XShearImage, and YShearImage methods are based on the
%  paper "A Fast Algorithm for General Raster Rotatation" by Alan W. Paeth,
%  Graphics Interface '86 (Vancouver).  RotateImage is adapted from a similar
%  method based on the Paeth paper written by Michael Halle of the Spatial
%  Imaging Group, MIT Media Lab.
%
%
*/

/*
  Include declarations.
*/
#include "magick/studio.h"
#include "magick/artifact.h"
#include "magick/blob-private.h"
#include "magick/cache-private.h"
#include "magick/color-private.h"
#include "magick/colorspace-private.h"
#include "magick/composite.h"
#include "magick/composite-private.h"
#include "magick/decorate.h"
#include "magick/distort.h"
#include "magick/draw.h"
#include "magick/exception.h"
#include "magick/exception-private.h"
#include "magick/gem.h"
#include "magick/geometry.h"
#include "magick/image.h"
#include "magick/image-private.h"
#include "magick/memory_.h"
#include "magick/list.h"
#include "magick/monitor.h"
#include "magick/monitor-private.h"
#include "magick/pixel-private.h"
#include "magick/quantum.h"
#include "magick/resource_.h"
#include "magick/shear.h"
#include "magick/statistic.h"
#include "magick/threshold.h"
#include "magick/transform.h"

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%     A f f i n e T r a n s f o r m I m a g e                                 %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  AffineTransformImage() transforms an image as dictated by the affine matrix.
%  It allocates the memory necessary for the new Image structure and returns
%  a pointer to the new image.
%
%  The format of the AffineTransformImage method is:
%
%      Image *AffineTransformImage(const Image *image,
%        AffineMatrix *affine_matrix,ExceptionInfo *exception)
%
%  A description of each parameter follows:
%
%    o image: the image.
%
%    o affine_matrix: the affine matrix.
%
%    o exception: return any errors or warnings in this structure.
%
*/
MagickExport Image *AffineTransformImage(const Image *image,
  const AffineMatrix *affine_matrix,ExceptionInfo *exception)
{
  double
    distort[6];

  Image
    *affine_image;

  /*
    Affine transform image.
  */
  assert(image->signature == MagickSignature);
  if (image->debug != MagickFalse)
    (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
  assert(affine_matrix != (AffineMatrix *) NULL);
  assert(exception != (ExceptionInfo *) NULL);
  assert(exception->signature == MagickSignature);
  distort[0]=affine_matrix->sx;
  distort[1]=affine_matrix->rx;
  distort[2]=affine_matrix->ry;
  distort[3]=affine_matrix->sy;
  distort[4]=affine_matrix->tx;
  distort[5]=affine_matrix->ty;
  affine_image=DistortImage(image,AffineProjectionDistortion,6,distort,
    MagickTrue,exception);
  return(affine_image);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
+   C r o p T o F i t I m a g e                                               %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  CropToFitImage() crops the sheared image as determined by the bounding box
%  as defined by width and height and shearing angles.
%
%  The format of the CropToFitImage method is:
%
%      Image *CropToFitImage(Image **image,const MagickRealType x_shear,
%        const MagickRealType x_shear,const MagickRealType width,
%        const MagickRealType height,const MagickBooleanType rotate,
%        ExceptionInfo *exception)
%
%  A description of each parameter follows.
%
%    o image: the image.
%
%    o x_shear, y_shear, width, height: Defines a region of the image to crop.
%
%    o exception: return any errors or warnings in this structure.
%
*/
static inline void CropToFitImage(Image **image,const MagickRealType x_shear,
  const MagickRealType y_shear,const MagickRealType width,
  const MagickRealType height,const MagickBooleanType rotate,
  ExceptionInfo *exception)
{
  Image
    *crop_image;

  PointInfo
    extent[4],
    min,
    max;

  RectangleInfo
    geometry,
    page;

  register long
    i;

  /*
    Calculate the rotated image size.
  */
  extent[0].x=(double) (-width/2.0);
  extent[0].y=(double) (-height/2.0);
  extent[1].x=(double) width/2.0;
  extent[1].y=(double) (-height/2.0);
  extent[2].x=(double) (-width/2.0);
  extent[2].y=(double) height/2.0;
  extent[3].x=(double) width/2.0;
  extent[3].y=(double) height/2.0;
  for (i=0; i < 4; i++)
  {
    extent[i].x+=x_shear*extent[i].y;
    extent[i].y+=y_shear*extent[i].x;
    if (rotate != MagickFalse)
      extent[i].x+=x_shear*extent[i].y;
    extent[i].x+=(double) (*image)->columns/2.0;
    extent[i].y+=(double) (*image)->rows/2.0;
  }
  min=extent[0];
  max=extent[0];
  for (i=1; i < 4; i++)
  {
    if (min.x > extent[i].x)
      min.x=extent[i].x;
    if (min.y > extent[i].y)
      min.y=extent[i].y;
    if (max.x < extent[i].x)
      max.x=extent[i].x;
    if (max.y < extent[i].y)
      max.y=extent[i].y;
  }
  geometry.x=(long) (min.x+0.5);
  geometry.y=(long) (min.y+0.5);
  geometry.width=(unsigned long) ((long) (max.x+0.5)-(long) (min.x+0.5));
  geometry.height=(unsigned long) ((long) (max.y+0.5)-(long) (min.y+0.5));
  page=(*image)->page;
  (void) ParseAbsoluteGeometry("0x0+0+0",&(*image)->page);
  crop_image=CropImage(*image,&geometry,exception);
  (*image)->page=page;
  if (crop_image != (Image *) NULL)
    {
      crop_image->page=page;
      *image=DestroyImage(*image);
      *image=crop_image;
    }
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
%     D e s k e w I m a g e                                                   %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  DeskewImage() removes skew from the image.  Skew is an artifact that
%  occurs in scanned images because of the camera being misaligned,
%  imperfections in the scanning or surface, or simply because the paper was
%  not placed completely flat when scanned.
%
%  The format of the DeskewImage method is:
%
%      Image *DeskewImage(const Image *image,const double threshold,
%        ExceptionInfo *exception)
%
%  A description of each parameter follows:
%
%    o image: the image.
%
%    o threshold: separate background from foreground.
%
%    o exception: return any errors or warnings in this structure.
%
*/

typedef struct _RadonInfo
{
  CacheType
    type;

  unsigned long
    width,
    height;

  MagickSizeType
    length;

  MagickBooleanType
    mapped;

  char
    path[MaxTextExtent];

  int
    file;

  unsigned short
    *cells;
} RadonInfo;

static RadonInfo *DestroyRadonInfo(RadonInfo *radon_info)
{
  assert(radon_info != (RadonInfo *) NULL);
  switch (radon_info->type)
  {
    case MemoryCache:
    {
      if (radon_info->mapped == MagickFalse)
        radon_info->cells=(unsigned short *) RelinquishMagickMemory(
          radon_info->cells);
      else
        radon_info->cells=(unsigned short *) UnmapBlob(radon_info->cells,
          (size_t) radon_info->length);
      RelinquishMagickResource(MemoryResource,radon_info->length);
      break;
    }
    case MapCache:
    {
      radon_info->cells=(unsigned short *) UnmapBlob(radon_info->cells,(size_t)
        radon_info->length);
      RelinquishMagickResource(MapResource,radon_info->length);
    }
    case DiskCache:
    {
      if (radon_info->file != -1)
        (void) close(radon_info->file);
      (void) RelinquishUniqueFileResource(radon_info->path);
      RelinquishMagickResource(DiskResource,radon_info->length);
      break;
    }
    default:
      break;
  }
  return((RadonInfo *) RelinquishMagickMemory(radon_info));
}

static MagickBooleanType ResetRadonCells(RadonInfo *radon_info)
{
  long
    y;

  register long
    x;

  ssize_t
    count;

  unsigned short
    value;

  if (radon_info->type != DiskCache)
    {
      (void) ResetMagickMemory(radon_info->cells,0,(size_t) radon_info->length);
      return(MagickTrue);
    }
  value=0;
  (void) MagickSeek(radon_info->file,0,SEEK_SET);
  for (y=0; y < (long) radon_info->height; y++)
  {
    for (x=0; x < (long) radon_info->width; x++)
    {
      count=write(radon_info->file,&value,sizeof(*radon_info->cells));
      if (count != (ssize_t) sizeof(*radon_info->cells))
        break;
    }
    if (x < (long) radon_info->width)
      break;
  }
  return(y < (long) radon_info->height ? MagickFalse : MagickTrue);
}

static RadonInfo *AcquireRadonInfo(const Image *image,const unsigned long width,
  const unsigned long height,ExceptionInfo *exception)
{
  MagickBooleanType
    status;

  RadonInfo
    *radon_info;

  radon_info=(RadonInfo *) AcquireMagickMemory(sizeof(*radon_info));
  if (radon_info == (RadonInfo *) NULL)
    return((RadonInfo *) NULL);
  (void) ResetMagickMemory(radon_info,0,sizeof(*radon_info));
  radon_info->width=width;
  radon_info->height=height;
  radon_info->length=(MagickSizeType) width*height*sizeof(*radon_info->cells);
  radon_info->type=MemoryCache;
  status=AcquireMagickResource(AreaResource,radon_info->length);
  if ((status != MagickFalse) &&
      (radon_info->length == (MagickSizeType) ((size_t) radon_info->length)))
    {
      status=AcquireMagickResource(MemoryResource,radon_info->length);
      if (status != MagickFalse)
        {
          radon_info->mapped=MagickFalse;
          radon_info->cells=(unsigned short *) AcquireMagickMemory((size_t)
            radon_info->length);
          if (radon_info->cells == (unsigned short *) NULL)
            {
              radon_info->mapped=MagickTrue;
              radon_info->cells=(unsigned short *) MapBlob(-1,IOMode,0,(size_t)
                radon_info->length);
            }
          if (radon_info->cells == (unsigned short *) NULL)
            RelinquishMagickResource(MemoryResource,radon_info->length);
        }
    }
  radon_info->file=(-1);
  if (radon_info->cells == (unsigned short *) NULL)
    {
      status=AcquireMagickResource(DiskResource,radon_info->length);
      if (status == MagickFalse)
        {
          (void) ThrowMagickException(exception,GetMagickModule(),CacheError,
            "CacheResourcesExhausted","`%s'",image->filename);
          return(DestroyRadonInfo(radon_info));
        }
      radon_info->type=DiskCache;
      (void) AcquireMagickResource(MemoryResource,radon_info->length);
      radon_info->file=AcquireUniqueFileResource(radon_info->path);
      if (radon_info->file == -1)
        return(DestroyRadonInfo(radon_info));
      status=AcquireMagickResource(MapResource,radon_info->length);
      if (status != MagickFalse)
        {
          status=ResetRadonCells(radon_info);
          if (status != MagickFalse)
            {
              radon_info->cells=(unsigned short *) MapBlob(radon_info->file,
                IOMode,0,(size_t) radon_info->length);
              if (radon_info->cells != (unsigned short *) NULL)
                radon_info->type=MapCache;
              else
                RelinquishMagickResource(MapResource,radon_info->length);
            }
        }
    }
  return(radon_info);
}

static inline size_t MagickMin(const size_t x,const size_t y)
{
  if (x < y)
    return(x);
  return(y);
}

static inline ssize_t ReadRadonCell(const RadonInfo *radon_info,
  const off_t offset,const size_t length,unsigned char *buffer)
{
  register ssize_t
    i;

  ssize_t
    count;

#if !defined(MAGICKCORE_HAVE_PPREAD)
#if defined(MAGICKCORE_OPENMP_SUPPORT)
  #pragma omp critical
#endif
  {
    i=(-1);
    if (MagickSeek(radon_info->file,offset,SEEK_SET) >= 0)
      {
#endif
        count=0;
        for (i=0; i < (ssize_t) length; i+=count)
        {
#if !defined(MAGICKCORE_HAVE_PPREAD)
          count=read(radon_info->file,buffer+i,MagickMin(length-i,(size_t)
            SSIZE_MAX));
#else
          count=pread(radon_info->file,buffer+i,MagickMin(length-i,(size_t)
            SSIZE_MAX),(off_t) (offset+i));
#endif
          if (count > 0)
            continue;
          count=0;
          if (errno != EINTR)
            {
              i=(-1);
              break;
            }
        }
#if !defined(MAGICKCORE_HAVE_PPREAD)
      }
  }
#endif
  return(i);
}

static inline ssize_t WriteRadonCell(const RadonInfo *radon_info,
  const off_t offset,const size_t length,const unsigned char *buffer)
{
  register ssize_t
    i;

  ssize_t
    count;

#if !defined(MAGICKCORE_HAVE_PPWRITE)
#if defined(MAGICKCORE_OPENMP_SUPPORT)
  #pragma omp critical
#endif
  {
    if (MagickSeek(radon_info->file,offset,SEEK_SET) >= 0)
      {
#endif
        count=0;
        for (i=0; i < (ssize_t) length; i+=count)
        {
#if !defined(MAGICKCORE_HAVE_PPWRITE)
          count=write(radon_info->file,buffer+i,MagickMin(length-i,(size_t)
            SSIZE_MAX));
#else
          count=pwrite(radon_info->file,buffer+i,MagickMin(length-i,(size_t)
            SSIZE_MAX),(off_t) (offset+i));
#endif
          if (count > 0)
            continue;
          count=0;
          if (errno != EINTR)
            {
              i=(-1);
              break;
            }
        }
#if !defined(MAGICKCORE_HAVE_PPWRITE)
      }
  }
#endif
  return(i);
}

static inline unsigned short GetRadonCell(const RadonInfo *radon_info,
  const long x,const long y)
{
  off_t
    i;

  unsigned short
    value;

  i=(off_t) radon_info->height*x+y;
  if ((i < 0) ||
      ((MagickSizeType) (i*sizeof(*radon_info->cells)) >= radon_info->length))
    return(0);
  if (radon_info->type != DiskCache)
    return(radon_info->cells[i]);
  value=0;
  (void) ReadRadonCell(radon_info,i*sizeof(*radon_info->cells),
    sizeof(*radon_info->cells),(unsigned char *) &value);
  return(value);
}

static inline MagickBooleanType SetRadonCell(const RadonInfo *radon_info,
  const long x,const long y,const unsigned short value)
{
  off_t
    i;

  ssize_t
    count;

  i=(off_t) radon_info->height*x+y;
  if ((i < 0) ||
      ((MagickSizeType) (i*sizeof(*radon_info->cells)) >= radon_info->length))
    return(MagickFalse);
  if (radon_info->type != DiskCache)
    {
      radon_info->cells[i]=value;
      return(MagickTrue);
    }
  count=WriteRadonCell(radon_info,i*sizeof(*radon_info->cells),
    sizeof(*radon_info->cells),(unsigned char *) &value);
  if (count != (ssize_t) sizeof(*radon_info->cells))
    return(MagickFalse);
  return(MagickTrue);
}

static void RadonProjection(RadonInfo *source_cells,
  RadonInfo *destination_cells,const long sign,unsigned long *projection)
{
  RadonInfo
    *swap;

  register long
    x;

  register RadonInfo
    *p,
    *q;

  unsigned long
    step;

  p=source_cells;
  q=destination_cells;
  for (step=1; step < p->width; step*=2)
  {
    for (x=0; x < (long) p->width; x+=2*step)
    {
      long
        y;

      register long
        i;

      unsigned short
        cell;

      for (i=0; i < (long) step; i++)
      {
        for (y=0; y < (long) (p->height-i-1); y++)
        {
          cell=GetRadonCell(p,x+i,y);
          (void) SetRadonCell(q,x+2*i,y,cell+GetRadonCell(p,x+i+step,y+i));
          (void) SetRadonCell(q,x+2*i+1,y,cell+GetRadonCell(p,x+i+step,y+i+1));
        }
        for ( ; y < (long) (p->height-i); y++)
        {
          cell=GetRadonCell(p,x+i,y);
          (void) SetRadonCell(q,x+2*i,y,cell+GetRadonCell(p,x+i+step,y+i));
          (void) SetRadonCell(q,x+2*i+1,y,cell);
        }
        for ( ; y < (long) p->height; y++)
        {
          cell=GetRadonCell(p,x+i,y);
          (void) SetRadonCell(q,x+2*i,y,cell);
          (void) SetRadonCell(q,x+2*i+1,y,cell);
        }
      }
    }
    swap=p;
    p=q;
    q=swap;
  }
#if defined(MAGICKCORE_OPENMP_SUPPORT)
  #pragma omp parallel for
#endif
  for (x=0; x < (long) p->width; x++)
  {
    register long
      y;

    unsigned long
      sum;

    sum=0;
    for (y=0; y < (long) (p->height-1); y++)
    {
      long
        delta;

      delta=GetRadonCell(p,x,y)-(long) GetRadonCell(p,x,y+1);
      sum+=delta*delta;
    }
    projection[p->width+sign*x-1]=sum;
  }
}

static MagickBooleanType RadonTransform(const Image *image,
  const double threshold,unsigned long *projection,ExceptionInfo *exception)
{
  long
    y;

  MagickBooleanType
    status;

  RadonInfo
    *destination_cells,
    *source_cells;

  register long
    i;

  unsigned char
    byte;

  unsigned long
    count,
    width;

  unsigned short
    bits[256];

  ViewInfo
    *image_view;

  for (width=1; width < ((image->columns+7)/8); width<<=1) ;
  source_cells=AcquireRadonInfo(image,width,image->rows,exception);
  destination_cells=AcquireRadonInfo(image,width,image->rows,exception);
  if ((source_cells == (RadonInfo *) NULL) ||
      (destination_cells == (RadonInfo *) NULL))
    {
      if (destination_cells != (RadonInfo *) NULL)
        destination_cells=DestroyRadonInfo(destination_cells);
      if (source_cells != (RadonInfo *) NULL)
        source_cells=DestroyRadonInfo(source_cells);
      return(MagickFalse);
    }
  if (ResetRadonCells(source_cells) == MagickFalse)
    {
      destination_cells=DestroyRadonInfo(destination_cells);
      source_cells=DestroyRadonInfo(source_cells);
      return(MagickFalse);
    }
  for (i=0; i < 256; i++)
  {
    byte=(unsigned char) i;
    for (count=0; byte != 0; byte>>=1)
      count+=byte & 0x01;
    bits[i]=(unsigned short) count;
  }
  status=MagickTrue;
  image_view=AcquireCacheView(image);
#if defined(MAGICKCORE_OPENMP_SUPPORT)
  #pragma omp parallel for schedule(dynamic,8) shared(status)
#endif
  for (y=0; y < (long) image->rows; y++)
  {
    register const PixelPacket
      *p;

    register long
      i,
      x;

    unsigned long
      bit,
      byte;

    if (status == MagickFalse)
      continue;
    p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
    if (p == (const PixelPacket *) NULL)
      {
        status=MagickFalse;
        continue;
      }
    bit=0;
    byte=0;
    i=(long) (image->columns+7)/8;
    for (x=0; x < (long) image->columns; x++)
    {
      byte<<=1;
      if (((MagickRealType) p->red < threshold) ||
          ((MagickRealType) p->green < threshold) ||
          ((MagickRealType) p->blue < threshold))
        byte|=0x01;
      bit++;
      if (bit == 8)
        {
          (void) SetRadonCell(source_cells,--i,y,bits[byte]);
          bit=0;
          byte=0;
        }
      p++;
    }
    if (bit != 0)
      {
        byte<<=(8-bit);
        (void) SetRadonCell(source_cells,--i,y,bits[byte]);
      }
  }
  RadonProjection(source_cells,destination_cells,-1,projection);
  (void) ResetRadonCells(source_cells);
#if defined(MAGICKCORE_OPENMP_SUPPORT)
  #pragma omp parallel for schedule(dynamic,8) shared(status)
#endif
  for (y=0; y < (long) image->rows; y++)
  {
    register const PixelPacket
      *p;

    register long
      i,
      x;

    unsigned long
      bit,
      byte;

    if (status == MagickFalse)
      continue;
    p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
    if (p == (const PixelPacket *) NULL)
      {
        status=MagickFalse;
        continue;
      }
    bit=0;
    byte=0;
    i=0;
    for (x=0; x < (long) image->columns; x++)
    {
      byte<<=1;
      if (((MagickRealType) p->red < threshold) ||
          ((MagickRealType) p->green < threshold) ||
          ((MagickRealType) p->blue < threshold))
        byte|=0x01;
      bit++;
      if (bit == 8)
        {
          (void) SetRadonCell(source_cells,i++,y,bits[byte]);
          bit=0;
          byte=0;
        }
      p++;
    }
    if (bit != 0)
      {
        byte<<=(8-bit);
        (void) SetRadonCell(source_cells,i++,y,bits[byte]);
      }
  }
  RadonProjection(source_cells,destination_cells,1,projection);
  image_view=DestroyCacheView(image_view);
  destination_cells=DestroyRadonInfo(destination_cells);
  source_cells=DestroyRadonInfo(source_cells);
  return(MagickTrue);
}

static void GetImageBackgroundColor(Image *image,const long offset,
  ExceptionInfo *exception)
{
  long
    y;

  MagickPixelPacket
    background;

  MagickRealType
    count;

  ViewInfo
    *image_view;

  /*
    Compute average background color.
  */
  if (offset <= 0)
    return;
  GetMagickPixelPacket(image,&background);
  count=0.0;
  image_view=AcquireCacheView(image);
  for (y=0; y < (long) image->rows; y++)
  {
    register const PixelPacket
      *p;

    register long
      x;

    if ((y >= offset) && (y < ((long) image->rows-offset)))
      continue;
    p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,exception);
    if (p == (const PixelPacket *) NULL)
      continue;
    for (x=0; x < (long) image->columns; x++)
    {
      if ((x >= offset) && (x < ((long) image->columns-offset)))
        continue;
      background.red+=QuantumScale*p->red;
      background.green+=QuantumScale*p->green;
      background.blue+=QuantumScale*p->blue;
      background.opacity+=QuantumScale*p->opacity;
      count++;
      p++;
    }
  }
  image_view=DestroyCacheView(image_view);
  image->background_color.red=RoundToQuantum((MagickRealType) QuantumRange*
    background.red/count);
  image->background_color.green=RoundToQuantum((MagickRealType) QuantumRange*
    background.green/count);
  image->background_color.blue=RoundToQuantum((MagickRealType) QuantumRange*
    background.blue/count);
  image->background_color.opacity=RoundToQuantum((MagickRealType) QuantumRange*
    background.opacity/count);
}

MagickExport Image *DeskewImage(const Image *image,const double threshold,
  ExceptionInfo *exception)
{
  const char
    *artifact;

  double
    degrees,
    sum;

  Image
    *clone_image,
    *crop_image,
    *median_image,
    *rotate_image;

  long
    skew;

  MagickBooleanType
    status;

  RectangleInfo
    geometry;

  register long
    i;

  unsigned long
    max_projection,
    *projection,
    width;

  /*
    Compute deskew angle.
  */
  for (width=1; width < ((image->columns+7)/8); width<<=1) ;
  projection=(unsigned long *) AcquireQuantumMemory((size_t) (2*width-1),
    sizeof(*projection));
  if (projection == (unsigned long *) NULL)
    ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
  status=RadonTransform(image,threshold,projection,exception);
  if (status == MagickFalse)
    {
      projection=(unsigned long *) RelinquishMagickMemory(projection);
      ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
    }
  max_projection=0;
  sum=0.0;
  skew=0;
  for (i=0; i < (long) (2*width-1); i++)
  {
    if (projection[i] > max_projection)
      {
        skew=i-(long) width+1;
        max_projection=projection[i];
      }
    sum+=projection[i];
  }
  projection=(unsigned long *) RelinquishMagickMemory(projection);
  /*
    Deskew image.
  */
  degrees=RadiansToDegrees(-atan((double) skew/width/8));
  if (image->debug != MagickFalse)
    (void) LogMagickEvent(TransformEvent,GetMagickModule(),"  Deskew angle: %g",
      degrees);
  artifact=GetImageArtifact(image,"deskew:auto-crop");
  if (artifact == (const char *) NULL)
    return(RotateImage(image,degrees,exception));
  /*
    Auto-crop image.
  */
  clone_image=CloneImage(image,0,0,MagickTrue,exception);
  if (clone_image == (Image *) NULL)
    return((Image *) NULL);
  GetImageBackgroundColor(clone_image,atol(artifact),exception);
  rotate_image=RotateImage(clone_image,degrees,exception);
  clone_image=DestroyImage(clone_image);
  if (rotate_image == (Image *) NULL)
    return((Image *) NULL);
  median_image=MedianFilterImage(rotate_image,0.0,exception);
  if (median_image == (Image *) NULL)
    {
      rotate_image=DestroyImage(rotate_image);
      return((Image *) NULL);
    }
  geometry=GetImageBoundingBox(median_image,exception);
  median_image=DestroyImage(median_image);
  if (image->debug != MagickFalse)
    (void) LogMagickEvent(TransformEvent,GetMagickModule(),"  Deskew geometry: "
      "%lux%lu%+ld%+ld",geometry.width,geometry.height,geometry.x,geometry.y);
  crop_image=CropImage(rotate_image,&geometry,exception);
  rotate_image=DestroyImage(rotate_image);
  return(crop_image);
}

/*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                                             %
%                                                                             %
%                                                                             %
+   I n t e g r a l R o t a t e I m a g e                                     %
%                                                                             %
%                                                                             %
%                                                                             %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  IntegralRotateImage()  rotates the image an integral of 90 degrees.  It
%  allocates the memory necessary for the new Image structure and returns a
%  pointer to the rotated image.
%
%  The format of the IntegralRotateImage method is:
%
%      Image *IntegralRotateImage(const Image *image,unsigned long rotations,
%        ExceptionInfo *exception)
%
%  A description of each parameter follows.
%
%    o image: the image.
%
%    o rotations: Specifies the number of 90 degree rotations.
%
*/
static Image *IntegralRotateImage(const Image *image,unsigned long rotations,
  ExceptionInfo *exception)
{
#define TileHeight  128
#define TileWidth  128
#define RotateImageTag  "Rotate/Image"

  Image
    *rotate_image;

  long
    progress,
    y;

  MagickBooleanType
    status;

  RectangleInfo
    page;

  ViewInfo
    *image_view,
    *rotate_view;

  /*
    Initialize rotated image attributes.
  */
  assert(image != (Image *) NULL);
  page=image->page;
  rotations%=4;
  if ((rotations == 1) || (rotations == 3))
    rotate_image=CloneImage(image,image->rows,image->columns,MagickTrue,
      exception);
  else
    rotate_image=CloneImage(image,image->columns,image->rows,MagickTrue,
      exception);
  if (rotate_image == (Image *) NULL)
    return((Image *) NULL);
  /*
    Integral rotate the image.
  */
  status=MagickTrue;
  progress=0;
  image_view=AcquireCacheView(image);
  rotate_view=AcquireCacheView(rotate_image);
  switch (rotations)
  {
    case 0:
    {
      /*
        Rotate 0 degrees.
      */
#if defined(MAGICKCORE_OPENMP_SUPPORT)
  #pragma omp parallel for schedule(dynamic,8) shared(progress,status)
#endif
      for (y=0; y < (long) image->rows; y++)
      {
        MagickBooleanType
          sync;

        register const IndexPacket
          *indexes;

        register const PixelPacket
          *p;

        register IndexPacket
          *rotate_indexes;

        register PixelPacket
          *q;

        if (status == MagickFalse)
          continue;
        p=GetCacheViewVirtualPixels(image_view,0,y,image->columns,1,
          exception);
        q=QueueCacheViewAuthenticPixels(rotate_view,0,y,
          rotate_image->columns,1,exception);
        if ((p == (const PixelPacket *) NULL) || (q == (PixelPacket *) NULL))
          {
            status=MagickFalse;
            continue;
          }
        indexes=GetCacheViewVirtualIndexQueue(image_view);
        (void) CopyMagickMemory(q,p,image->columns*sizeof(*p));
        if (indexes != (IndexPacket *) NULL)
          {
            rotate_indexes=GetCacheViewAuthenticIndexQueue(rotate_view);
            (void) CopyMagickMemory(rotate_indexes,indexes,image->columns*
              sizeof(*indexes));
          }
        sync=SyncCacheViewAuthenticPixels(rotate_view,exception);
        if (sync ==