granicus.if.org Git - imagemagick/blob - magick/layer.c

   1 /*
   2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   3 %                                                                             %
   4 %                                                                             %
   5 %                     L       AAA   Y   Y  EEEEE  RRRR                        %
   6 %                     L      A   A   Y Y   E      R   R                       %
   7 %                     L      AAAAA    Y    EEE    RRRR                        %
   8 %                     L      A   A    Y    E      R R                         %
   9 %                     LLLLL  A   A    Y    EEEEE  R  R                        %
  10 %                                                                             %
  11 %                      MagickCore Image Layering Methods                      %
  12 %                                                                             %
  13 %                              Software Design                                %
  14 %                                John Cristy                                  %
  15 %                              Anthony Thyssen                                %
  16 %                               January 2006                                  %
  17 %                                                                             %
  18 %                                                                             %
  19 %  Copyright 1999-2009 ImageMagick Studio LLC, a non-profit organization      %
  20 %  dedicated to making software imaging solutions freely available.           %
  21 %                                                                             %
  22 %  You may not use this file except in compliance with the License.  You may  %
  23 %  obtain a copy of the License at                                            %
  24 %                                                                             %
  25 %    http://www.imagemagick.org/script/license.php                            %
  26 %                                                                             %
  27 %  Unless required by applicable law or agreed to in writing, software        %
  28 %  distributed under the License is distributed on an "AS IS" BASIS,          %
  29 %  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.   %
  30 %  See the License for the specific language governing permissions and        %
  31 %  limitations under the License.                                             %
  32 %                                                                             %
  33 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  34 %
  35 */
  36 \f
  37 /*
  38   Include declarations.
  39 */
  40 #include "magick/studio.h"
  41 #include "magick/artifact.h"
  42 #include "magick/cache.h"
  43 #include "magick/color.h"
  44 #include "magick/color-private.h"
  45 #include "magick/composite.h"
  46 #include "magick/effect.h"
  47 #include "magick/exception.h"
  48 #include "magick/exception-private.h"
  49 #include "magick/geometry.h"
  50 #include "magick/image.h"
  51 #include "magick/layer.h"
  52 #include "magick/list.h"
  53 #include "magick/memory_.h"
  54 #include "magick/monitor.h"
  55 #include "magick/monitor-private.h"
  56 #include "magick/pixel-private.h"
  57 #include "magick/property.h"
  58 #include "magick/profile.h"
  59 #include "magick/resource_.h"
  60 #include "magick/resize.h"
  61 #include "magick/statistic.h"
  62 #include "magick/string_.h"
  63 #include "magick/transform.h"
  64 \f
  65 /*
  66 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  67 %                                                                             %
  68 %                                                                             %
  69 %                                                                             %
  70 +     C l e a r B o u n d s                                                   %
  71 %                                                                             %
  72 %                                                                             %
  73 %                                                                             %
  74 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  75 %
  76 %  ClearBounds() Clear the area specified by the bounds in an image to
  77 %  transparency.  This typically used to handle Background Disposal
  78 %  for the previous frame in an animation sequence.
  79 %
  80 %  WARNING: no bounds checks are performed, except for the null or
  81 %  missed image, for images that don't change. in all other cases
  82 %  bound must fall within the image.
  83 %
  84 %  The format is:
  85 %
  86 %      void ClearBounds(Image *image,RectangleInfo *bounds)
  87 %
  88 %  A description of each parameter follows:
  89 %
  90 %    o image: the image to had the area cleared in
  91 %
  92 %    o bounds: the area to be clear within the imag image
  93 %
  94 */
  95 static void ClearBounds(Image *image,RectangleInfo *bounds)
  96 {
  97   ExceptionInfo
  98     *exception;
  99
 100   long
 101     y;
 102
 103   if (bounds->x < 0)
 104     return;
 105   if (image->matte == MagickFalse)
 106     (void) SetImageAlphaChannel(image,OpaqueAlphaChannel);
 107   exception=(&image->exception);
 108   for (y=0; y < (long) bounds->height; y++)
 109   {
 110     register long
 111       x;
 112
 113     register PixelPacket
 114       *__restrict q;
 115
 116     q=GetAuthenticPixels(image,bounds->x,bounds->y+y,bounds->width,1,exception);
 117     if (q == (PixelPacket *) NULL)
 118       break;
 119     for (x=0; x < (long) bounds->width; x++)
 120     {
 121       q->opacity=(Quantum) TransparentOpacity;
 122       q++;
 123     }
 124     if (SyncAuthenticPixels(image,exception) == MagickFalse)
 125       break;
 126   }
 127 }
 128 \f
 129 /*
 130 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 131 %                                                                             %
 132 %                                                                             %
 133 %                                                                             %
 134 +     I s B o u n d s C l e a r e d                                           %
 135 %                                                                             %
 136 %                                                                             %
 137 %                                                                             %
 138 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 139 %
 140 %  IsBoundsCleared() tests whether any pixel in the bounds given, gets cleared
 141 %  when going from the first image to the second image.  This typically used
 142 %  to check if a proposed disposal method will work successfully to generate
 143 %  the second frame image from the first disposed form of the previous frame.
 144 %
 145 %  The format is:
 146 %
 147 %      MagickBooleanType IsBoundsCleared(const Image *image1,
 148 %        const Image *image2,RectangleInfo bounds,ExceptionInfo *exception)
 149 %
 150 %  A description of each parameter follows:
 151 %
 152 %    o image1, image 2: the images to check for cleared pixels
 153 %
 154 %    o bounds: the area to be clear within the imag image
 155 %
 156 %    o exception: return any errors or warnings in this structure.
 157 %
 158 %  WARNING: no bounds checks are performed, except for the null or
 159 %  missed image, for images that don't change. in all other cases
 160 %  bound must fall within the image.
 161 %
 162 */
 163 static MagickBooleanType IsBoundsCleared(const Image *image1,
 164   const Image *image2,RectangleInfo *bounds,ExceptionInfo *exception)
 165 {
 166   long
 167     y;
 168
 169   register long
 170     x;
 171
 172   register const PixelPacket
 173     *p,
 174     *q;
 175
 176   if ( bounds->x< 0 ) return(MagickFalse);
 177
 178   for (y=0; y < (long) bounds->height; y++)
 179   {
 180     p=GetVirtualPixels(image1,bounds->x,bounds->y+y,bounds->width,1,
 181       exception);
 182     q=GetVirtualPixels(image2,bounds->x,bounds->y+y,bounds->width,1,
 183       exception);
 184     if ((p == (const PixelPacket *) NULL) || (q == (PixelPacket *) NULL))
 185       break;
 186     for (x=0; x < (long) bounds->width; x++)
 187     {
 188       if ((p->opacity <= (long) (QuantumRange/2)) &&
 189           (q->opacity > (long) (QuantumRange/2)))
 190         break;
 191       p++;
 192       q++;
 193     }
 194     if (x < (long) bounds->width)
 195       break;
 196   }
 197   return(y < (long) bounds->height ? MagickTrue : MagickFalse);
 198 }
 199 \f
 200 /*
 201 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 202 %                                                                             %
 203 %                                                                             %
 204 %                                                                             %
 205 %     C o a l e s c e I m a g e s                                             %
 206 %                                                                             %
 207 %                                                                             %
 208 %                                                                             %
 209 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 210 %
 211 %  CoalesceImages() composites a set of images while respecting any page
 212 %  offsets and disposal methods.  GIF, MIFF, and MNG animation sequences
 213 %  typically start with an image background and each subsequent image
 214 %  varies in size and offset.  A new image sequence is returned with all
 215 %  images the same size as the first images virtual canvas and composited
 216 %  with the next image in the sequence.
 217 %
 218 %  The format of the CoalesceImages method is:
 219 %
 220 %      Image *CoalesceImages(Image *image,ExceptionInfo *exception)
 221 %
 222 %  A description of each parameter follows:
 223 %
 224 %    o image: the image sequence.
 225 %
 226 %    o exception: return any errors or warnings in this structure.
 227 %
 228 */
 229 MagickExport Image *CoalesceImages(const Image *image,ExceptionInfo *exception)
 230 {
 231   Image
 232     *coalesce_image,
 233     *dispose_image,
 234     *previous;
 235
 236   register Image
 237     *next;
 238
 239   RectangleInfo
 240     bounds;
 241
 242   /*
 243     Coalesce the image sequence.
 244   */
 245   assert(image != (Image *) NULL);
 246   assert(image->signature == MagickSignature);
 247   if (image->debug != MagickFalse)
 248     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 249   assert(exception != (ExceptionInfo *) NULL);
 250   assert(exception->signature == MagickSignature);
 251
 252   /* initialise first image */
 253   next=GetFirstImageInList(image);
 254   bounds=next->page;
 255   if (bounds.width == 0)
 256     {
 257       bounds.width=next->columns;
 258       if (bounds.x > 0)
 259         bounds.width+=bounds.x;
 260     }
 261   if (bounds.height == 0)
 262     {
 263       bounds.height=next->rows;
 264       if (bounds.y > 0)
 265         bounds.height+=bounds.y;
 266     }
 267   bounds.x=0;
 268   bounds.y=0;
 269   coalesce_image=CloneImage(next,bounds.width,bounds.height,MagickTrue,
 270     exception);
 271   if (coalesce_image == (Image *) NULL)
 272     return((Image *) NULL);
 273   coalesce_image->page=bounds;
 274   coalesce_image->dispose=NoneDispose;
 275   coalesce_image->background_color.opacity=(Quantum) TransparentOpacity;
 276   (void) SetImageBackgroundColor(coalesce_image);
 277   /*
 278     Coalesce rest of the images.
 279   */
 280   dispose_image=CloneImage(coalesce_image,0,0,MagickTrue,exception);
 281   (void) CompositeImage(coalesce_image,CopyCompositeOp,next,next->page.x,
 282     next->page.y);
 283   next=GetNextImageInList(next);
 284   for ( ; next != (Image *) NULL; next=GetNextImageInList(next))
 285   {
 286     /*
 287       Determine the bounds that was overlaid in the previous image.
 288     */
 289     previous=GetPreviousImageInList(next);
 290     bounds=previous->page;
 291     bounds.width=previous->columns;
 292     bounds.height=previous->rows;
 293     if (bounds.x < 0)
 294       {
 295         bounds.width+=bounds.x;
 296         bounds.x=0;
 297       }
 298     if ((long) (bounds.x+bounds.width) > (long) coalesce_image->columns)
 299       bounds.width=coalesce_image->columns-bounds.x;
 300     if (bounds.y < 0)
 301       {
 302         bounds.height+=bounds.y;
 303         bounds.y=0;
 304       }
 305     if ((long) (bounds.y+bounds.height) > (long) coalesce_image->rows)
 306       bounds.height=coalesce_image->rows-bounds.y;
 307     /*
 308       Replace the dispose image with the new coalesced image.
 309     */
 310     if (GetPreviousImageInList(next)->dispose != PreviousDispose)
 311       {
 312         dispose_image=DestroyImage(dispose_image);
 313         dispose_image=CloneImage(coalesce_image,0,0,MagickTrue,exception);
 314         if (dispose_image == (Image *) NULL)
 315           {
 316             coalesce_image=DestroyImageList(coalesce_image);
 317             return((Image *) NULL);
 318           }
 319       }
 320     /*
 321       Clear the overlaid area of the coalesced bounds for background disposal
 322     */
 323     if (next->previous->dispose == BackgroundDispose)
 324       ClearBounds(dispose_image, &bounds);
 325     /*
 326       Next image is the dispose image, overlaid with next frame in sequence.
 327     */
 328     coalesce_image->next=CloneImage(dispose_image,0,0,MagickTrue,exception);
 329     coalesce_image->next->previous=coalesce_image;
 330     previous=coalesce_image;
 331     coalesce_image=GetNextImageInList(coalesce_image);
 332     coalesce_image->matte=MagickTrue;
 333     (void) CompositeImage(coalesce_image,next->matte != MagickFalse ?
 334       OverCompositeOp : CopyCompositeOp,next,next->page.x,next->page.y);
 335     (void) CloneImageProfiles(coalesce_image,next);
 336     (void) CloneImageProperties(coalesce_image,next);
 337     (void) CloneImageArtifacts(coalesce_image,next);
 338     coalesce_image->page=previous->page;
 339     /*
 340       If a pixel goes opaque to transparent, use background dispose.
 341     */
 342     if (IsBoundsCleared(previous,coalesce_image,&bounds,exception))
 343       coalesce_image->dispose=BackgroundDispose;
 344     else
 345       coalesce_image->dispose=NoneDispose;
 346     previous->dispose=coalesce_image->dispose;
 347   }
 348   dispose_image=DestroyImage(dispose_image);
 349   return(GetFirstImageInList(coalesce_image));
 350 }
 351 \f
 352 /*
 353 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 354 %                                                                             %
 355 %                                                                             %
 356 %                                                                             %
 357 %     D i s p o s e I m a g e s                                               %
 358 %                                                                             %
 359 %                                                                             %
 360 %                                                                             %
 361 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 362 %
 363 %  DisposeImages() returns the coalesced frames of a GIF animation as it would
 364 %  appear after the GIF dispose method of that frame has been applied.  That
 365 %  is it returned the appearance of each frame before the next is overlaid.
 366 %
 367 %  The format of the DisposeImages method is:
 368 %
 369 %      Image *DisposeImages(Image *image,ExceptionInfo *exception)
 370 %
 371 %  A description of each parameter follows:
 372 %
 373 %    o image: the image sequence.
 374 %
 375 %    o exception: return any errors or warnings in this structure.
 376 %
 377 */
 378 MagickExport Image *DisposeImages(const Image *image,ExceptionInfo *exception)
 379 {
 380   Image
 381     *dispose_image,
 382     *dispose_images;
 383
 384   register Image
 385     *next;
 386
 387   /*
 388     Run the image through the animation sequence
 389   */
 390   assert(image != (Image *) NULL);
 391   assert(image->signature == MagickSignature);
 392   if (image->debug != MagickFalse)
 393     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 394   assert(exception != (ExceptionInfo *) NULL);
 395   assert(exception->signature == MagickSignature);
 396   next=GetFirstImageInList(image);
 397   dispose_image=CloneImage(next,next->page.width,next->page.height,MagickTrue,
 398     exception);
 399   if (dispose_image == (Image *) NULL)
 400     return((Image *) NULL);
 401   dispose_image->page=next->page;
 402   dispose_image->page.x=0;
 403   dispose_image->page.y=0;
 404   dispose_image->dispose=NoneDispose;
 405   dispose_image->background_color.opacity=(Quantum) TransparentOpacity;
 406   (void) SetImageBackgroundColor(dispose_image);
 407   dispose_images=NewImageList();
 408   for ( ; next != (Image *) NULL; next=GetNextImageInList(next))
 409   {
 410     Image
 411       *current_image;
 412
 413     /*
 414       Overlay this frame's image over the previous disposal image.
 415     */
 416     current_image=CloneImage(dispose_image,0,0,MagickTrue,exception);
 417     if (current_image == (Image *) NULL)
 418       {
 419         dispose_images=DestroyImageList(dispose_images);
 420         dispose_image=DestroyImage(dispose_image);
 421         return((Image *) NULL);
 422       }
 423     (void) CompositeImage(current_image,next->matte != MagickFalse ?
 424       OverCompositeOp : CopyCompositeOp,next,next->page.x,next->page.y);
 425     /*
 426       Handle Background dispose: image is displayed for the delay period.
 427     */
 428     if (next->dispose == BackgroundDispose)
 429       {
 430         RectangleInfo
 431           bounds;
 432
 433         bounds=next->page;
 434         bounds.width=next->columns;
 435         bounds.height=next->rows;
 436         if (bounds.x < 0)
 437           {
 438             bounds.width+=bounds.x;
 439             bounds.x=0;
 440           }
 441         if ((long) (bounds.x+bounds.width) > (long) current_image->columns)
 442           bounds.width=current_image->columns-bounds.x;
 443         if (bounds.y < 0)
 444           {
 445             bounds.height+=bounds.y;
 446             bounds.y=0;
 447           }
 448         if ((long) (bounds.y+bounds.height) > (long) current_image->rows)
 449           bounds.height=current_image->rows-bounds.y;
 450         ClearBounds(current_image,&bounds);
 451       }
 452     /*
 453       Select the appropriate previous/disposed image.
 454     */
 455     if (next->dispose == PreviousDispose)
 456       current_image=DestroyImage(current_image);
 457     else
 458       {
 459         dispose_image=DestroyImage(dispose_image);
 460         dispose_image=current_image;
 461       }
 462     {
 463       Image
 464         *dispose;
 465
 466       /*
 467         Save the dispose image just calculated for return.
 468       */
 469       dispose=CloneImage(dispose_image,0,0,MagickTrue,exception);
 470       if (dispose == (Image *) NULL)
 471         {
 472           dispose_images=DestroyImageList(dispose_images);
 473           dispose_image=DestroyImage(dispose_image);
 474           return((Image *) NULL);
 475         }
 476       (void) CloneImageProfiles(dispose,next);
 477       (void) CloneImageProperties(dispose,next);
 478       (void) CloneImageArtifacts(dispose,next);
 479       dispose->page.x=0;
 480       dispose->page.y=0;
 481       dispose->dispose=next->dispose;
 482       AppendImageToList(&dispose_images,dispose);
 483     }
 484   }
 485   dispose_image=DestroyImage(dispose_image);
 486   return(GetFirstImageInList(dispose_images));
 487 }
 488 \f
 489 /*
 490 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 491 %                                                                             %
 492 %                                                                             %
 493 %                                                                             %
 494 +     C o m p a r e P i x e l s                                               %
 495 %                                                                             %
 496 %                                                                             %
 497 %                                                                             %
 498 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 499 %
 500 %  ComparePixels() Compare the two pixels and return true if the pixels
 501 %  differ according to the given LayerType comparision method.
 502 %
 503 %  This currently only used internally by CompareImageBounds(). It is
 504 %  doubtful that this sub-routine will be useful outside this module.
 505 %
 506 %  The format of the ComparePixels method is:
 507 %
 508 %      MagickBooleanType *ComparePixels(const ImageLayerMethod method,
 509 %        const MagickPixelPacket *p,const MagickPixelPacket *q)
 510 %
 511 %  A description of each parameter follows:
 512 %
 513 %    o method: What differences to look for. Must be one of
 514 %              CompareAnyLayer, CompareClearLayer, CompareOverlayLayer.
 515 %
 516 %    o p, q: the pixels to test for appropriate differences.
 517 %
 518 */
 519
 520 static MagickBooleanType ComparePixels(const ImageLayerMethod method,
 521   const MagickPixelPacket *p,const MagickPixelPacket *q)
 522 {
 523   MagickRealType
 524     o1,
 525     o2;
 526
 527   /*
 528     Any change in pixel values
 529   */
 530   if (method == CompareAnyLayer)
 531     return(IsMagickColorSimilar(p,q) == MagickFalse ? MagickTrue : MagickFalse);
 532
 533   o1 = (p->matte != MagickFalse) ? p->opacity : OpaqueOpacity;
 534   o2 = (q->matte != MagickFalse) ? q->opacity : OpaqueOpacity;
 535
 536   /*
 537     Pixel goes from opaque to transprency
 538   */
 539   if (method == CompareClearLayer)
 540     return((MagickBooleanType) ( (o1 <= ((MagickRealType) QuantumRange/2.0)) &&
 541       (o2 > ((MagickRealType) QuantumRange/2.0)) ) );
 542
 543   /*
 544     overlay would change first pixel by second
 545   */
 546   if (method == CompareOverlayLayer)
 547     {
 548       if (o2 > ((MagickRealType) QuantumRange/2.0))
 549         return MagickFalse;
 550       return((MagickBooleanType) (IsMagickColorSimilar(p,q) == MagickFalse));
 551     }
 552   return(MagickFalse);
 553 }
 554
 555 \f
 556 /*
 557 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 558 %                                                                             %
 559 %                                                                             %
 560 %                                                                             %
 561 +     C o m p a r e I m a g e B o u n d s                                     %
 562 %                                                                             %
 563 %                                                                             %
 564 %                                                                             %
 565 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 566 %
 567 %  CompareImageBounds() Given two images return the smallest rectangular area
 568 %  by which the two images differ, accourding to the given 'Compare...'
 569 %  layer method.
 570 %
 571 %  This currently only used internally in this module, but may eventually
 572 %  be used by other modules.
 573 %
 574 %  The format of the CompareImageBounds method is:
 575 %
 576 %      RectangleInfo *CompareImageBounds(const ImageLayerMethod method,
 577 %        const Image *image1, const Image *image2, ExceptionInfo *exception)
 578 %
 579 %  A description of each parameter follows:
 580 %
 581 %    o method: What differences to look for. Must be one of
 582 %              CompareAnyLayer, CompareClearLayer, CompareOverlayLayer.
 583 %
 584 %    o image1, image2: the two images to compare.
 585 %
 586 %    o exception: return any errors or warnings in this structure.
 587 %
 588 */
 589
 590 static RectangleInfo CompareImageBounds(const Image *image1,const Image *image2,
 591   const ImageLayerMethod method,ExceptionInfo *exception)
 592 {
 593   RectangleInfo
 594     bounds;
 595
 596   MagickPixelPacket
 597     pixel1,
 598     pixel2;
 599
 600   register const IndexPacket
 601     *indexes1,
 602     *indexes2;
 603
 604   register const PixelPacket
 605     *p,
 606     *q;
 607
 608   long
 609     y;
 610
 611   register long
 612     x;
 613
 614   /*
 615     Set bounding box of the differences between images
 616   */
 617   GetMagickPixelPacket(image1,&pixel1);
 618   GetMagickPixelPacket(image2,&pixel2);
 619   for (x=0; x < (long) image1->columns; x++)
 620   {
 621     p=GetVirtualPixels(image1,x,0,1,image1->rows,exception);
 622     q=GetVirtualPixels(image2,x,0,1,image2->rows,exception);
 623     if ((p == (const PixelPacket *) NULL) ||
 624         (q == (const PixelPacket *) NULL))
 625       break;
 626     indexes1=GetVirtualIndexQueue(image1);
 627     indexes2=GetVirtualIndexQueue(image2);
 628     for (y=0; y < (long) image1->rows; y++)
 629     {
 630       SetMagickPixelPacket(image1,p,indexes1+x,&pixel1);
 631       SetMagickPixelPacket(image2,q,indexes2+x,&pixel2);
 632       if (ComparePixels(method,&pixel1,&pixel2))
 633         break;
 634       p++;
 635       q++;
 636     }
 637     if (y < (long) image1->rows)
 638       break;
 639   }
 640   if (x >= (long) image1->columns)
 641     {
 642       /*
 643         Images are identical, return a null image.
 644       */
 645       bounds.x=-1;
 646       bounds.y=-1;
 647       bounds.width=1;
 648       bounds.height=1;
 649       return(bounds);
 650     }
 651   bounds.x=x;
 652   for (x=(long) image1->columns-1; x >= 0; x--)
 653   {
 654     p=GetVirtualPixels(image1,x,0,1,image1->rows,exception);
 655     q=GetVirtualPixels(image2,x,0,1,image2->rows,exception);
 656     if ((p == (const PixelPacket *) NULL) ||
 657         (q == (const PixelPacket *) NULL))
 658       break;
 659     indexes1=GetVirtualIndexQueue(image1);
 660     indexes2=GetVirtualIndexQueue(image2);
 661     for (y=0; y < (long) image1->rows; y++)
 662     {
 663       SetMagickPixelPacket(image1,p,indexes1+x,&pixel1);
 664       SetMagickPixelPacket(image2,q,indexes2+x,&pixel2);
 665       if (ComparePixels(method,&pixel1,&pixel2))
 666         break;
 667       p++;
 668       q++;
 669     }
 670     if (y < (long) image1->rows)
 671       break;
 672   }
 673   bounds.width=(unsigned long) (x-bounds.x+1);
 674   for (y=0; y < (long) image1->rows; y++)
 675   {
 676     p=GetVirtualPixels(image1,0,y,image1->columns,1,exception);
 677     q=GetVirtualPixels(image2,0,y,image2->columns,1,exception);
 678     if ((p == (const PixelPacket *) NULL) ||
 679         (q == (const PixelPacket *) NULL))
 680       break;
 681     indexes1=GetVirtualIndexQueue(image1);
 682     indexes2=GetVirtualIndexQueue(image2);
 683     for (x=0; x < (long) image1->columns; x++)
 684     {
 685       SetMagickPixelPacket(image1,p,indexes1+x,&pixel1);
 686       SetMagickPixelPacket(image2,q,indexes2+x,&pixel2);
 687       if (ComparePixels(method,&pixel1,&pixel2))
 688         break;
 689       p++;
 690       q++;
 691     }
 692     if (x < (long) image1->columns)
 693       break;
 694   }
 695   bounds.y=y;
 696   for (y=(long) image1->rows-1; y >= 0; y--)
 697   {
 698     p=GetVirtualPixels(image1,0,y,image1->columns,1,exception);
 699     q=GetVirtualPixels(image2,0,y,image2->columns,1,exception);
 700     if ((p == (const PixelPacket *) NULL) ||
 701         (q == (const PixelPacket *) NULL))
 702       break;
 703     indexes1=GetVirtualIndexQueue(image1);
 704     indexes2=GetVirtualIndexQueue(image2);
 705     for (x=0; x < (long) image1->columns; x++)
 706     {
 707       SetMagickPixelPacket(image1,p,indexes1+x,&pixel1);
 708       SetMagickPixelPacket(image2,q,indexes2+x,&pixel2);
 709       if (ComparePixels(method,&pixel1,&pixel2))
 710         break;
 711       p++;
 712       q++;
 713     }
 714     if (x < (long) image1->columns)
 715       break;
 716   }
 717   bounds.height=(unsigned long) (y-bounds.y+1);
 718   return(bounds);
 719 }
 720 \f
 721 /*
 722 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 723 %                                                                             %
 724 %                                                                             %
 725 %                                                                             %
 726 %     C o m p a r e I m a g e L a y e r s                                     %
 727 %                                                                             %
 728 %                                                                             %
 729 %                                                                             %
 730 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 731 %
 732 %  CompareImageLayers() compares each image with the next in a sequence and
 733 %  returns the minimum bounding region of all the pixel differences (of the
 734 %  ImageLayerMethod specified) it discovers.
 735 %
 736 %  Images do NOT have to be the same size, though it is best that all the
 737 %  images are 'coalesced' (images are all the same size, on a flattened
 738 %  canvas, so as to represent exactly how an specific frame should look).
 739 %
 740 %  No GIF dispose methods are applied, so GIF animations must be coalesced
 741 %  before applying this image operator to find differences to them.
 742 %
 743 %  The format of the CompareImageLayers method is:
 744 %
 745 %      Image *CompareImageLayers(const Image *images,
 746 %        const ImageLayerMethod method,ExceptionInfo *exception)
 747 %
 748 %  A description of each parameter follows:
 749 %
 750 %    o image: the image.
 751 %
 752 %    o method: the layers type to compare images with. Must be one of...
 753 %              CompareAnyLayer, CompareClearLayer, CompareOverlayLayer.
 754 %
 755 %    o exception: return any errors or warnings in this structure.
 756 %
 757 */
 758
 759 MagickExport Image *CompareImageLayers(const Image *image,
 760   const ImageLayerMethod method, ExceptionInfo *exception)
 761 {
 762   Image
 763     *image_a,
 764     *image_b,
 765     *layers;
 766
 767   RectangleInfo
 768     *bounds;
 769
 770   register const Image
 771     *next;
 772
 773   register long
 774     i;
 775
 776   assert(image != (const Image *) NULL);
 777   assert(image->signature == MagickSignature);
 778   if (image->debug != MagickFalse)
 779     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 780   assert(exception != (ExceptionInfo *) NULL);
 781   assert(exception->signature == MagickSignature);
 782   assert((method == CompareAnyLayer) ||
 783          (method == CompareClearLayer) ||
 784          (method == CompareOverlayLayer));
 785   /*
 786     Allocate bounds memory.
 787   */
 788   next=GetFirstImageInList(image);
 789   bounds=(RectangleInfo *) AcquireQuantumMemory((size_t)
 790     GetImageListLength(next),sizeof(*bounds));
 791   if (bounds == (RectangleInfo *) NULL)
 792     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
 793   /*
 794     Set up first comparision images.
 795   */
 796   image_a=CloneImage(next,next->page.width,next->page.height,
 797     MagickTrue,exception);
 798   if (image_a == (Image *) NULL)
 799     {
 800       bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
 801       return((Image *) NULL);
 802     }
 803   image_a->background_color.opacity=(Quantum) TransparentOpacity;
 804   (void) SetImageBackgroundColor(image_a);
 805   image_a->page=next->page;
 806   image_a->page.x=0;
 807   image_a->page.y=0;
 808   (void) CompositeImage(image_a,CopyCompositeOp,next,next->page.x,next->page.y);
 809   /*
 810     Compute the bounding box of changes for the later images
 811   */
 812   i=0;
 813   next=GetNextImageInList(next);
 814   for ( ; next != (const Image *) NULL; next=GetNextImageInList(next))
 815   {
 816     image_b=CloneImage(image_a,0,0,MagickTrue,exception);
 817     if (image_b == (Image *) NULL)
 818       {
 819         image_a=DestroyImage(image_a);
 820         bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
 821         return((Image *) NULL);
 822       }
 823     (void) CompositeImage(image_a,CopyCompositeOp,next,next->page.x,
 824                            next->page.y);
 825     bounds[i]=CompareImageBounds(image_b,image_a,method,exception);
 826
 827     image_b=DestroyImage(image_b);
 828     i++;
 829   }
 830   image_a=DestroyImage(image_a);
 831   /*
 832     Clone first image in sequence.
 833   */
 834   next=GetFirstImageInList(image);
 835   layers=CloneImage(next,0,0,MagickTrue,exception);
 836   if (layers == (Image *) NULL)
 837     {
 838       bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
 839       return((Image *) NULL);
 840     }
 841   /*
 842     Deconstruct the image sequence.
 843   */
 844   i=0;
 845   next=GetNextImageInList(next);
 846   for ( ; next != (const Image *) NULL; next=GetNextImageInList(next))
 847   {
 848     image_a=CloneImage(next,0,0,MagickTrue,exception);
 849     if (image_a == (Image *) NULL)
 850       break;
 851     image_b=CropImage(image_a,&bounds[i],exception);
 852     image_a=DestroyImage(image_a);
 853     if (image_b == (Image *) NULL)
 854       break;
 855     AppendImageToList(&layers,image_b);
 856     i++;
 857   }
 858   bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
 859   if (next != (Image *) NULL)
 860     {
 861       layers=DestroyImageList(layers);
 862       return((Image *) NULL);
 863     }
 864   return(GetFirstImageInList(layers));
 865 }
 866 \f
 867 /*
 868 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 869 %                                                                             %
 870 %                                                                             %
 871 %                                                                             %
 872 %     D e c o n s t r u c t I m a g e s                                       %
 873 %                                                                             %
 874 %                                                                             %
 875 %                                                                             %
 876 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 877 %
 878 %  DeconstructImages() compares each image with the next in a sequence and
 879 %  returns the minimum bounding region of all differences from the first image.
 880 %
 881 %  This function is deprecated in favor of the more universal
 882 %  CompareImageLayers() function.
 883 %
 884 %  The format of the DeconstructImages method is:
 885 %
 886 %      Image *DeconstructImages(const Image *images, ExceptionInfo *exception)
 887 %
 888 %  A description of each parameter follows:
 889 %
 890 %    o image: the image.
 891 %
 892 %    o exception: return any errors or warnings in this structure.
 893 %
 894 */
 895
 896 MagickExport Image *DeconstructImages(const Image *images,
 897   ExceptionInfo *exception)
 898 {
 899   return(CompareImageLayers(images,CompareAnyLayer,exception));
 900 }
 901 \f
 902 /*
 903 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 904 %                                                                             %
 905 %                                                                             %
 906 %                                                                             %
 907 +     O p t i m i z e L a y e r F r a m e s                                   %
 908 %                                                                             %
 909 %                                                                             %
 910 %                                                                             %
 911 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 912 %
 913 %  OptimizeLayerFrames() compares each image the GIF disposed forms of the
 914 %  previous image in the sequence.  From this it attempts to select the
 915 %  smallest cropped image to replace each frame, while preserving the results
 916 %  of the animation.
 917 %
 918 %  Note that this not easy, and may require the expandsion of the bounds
 919 %  of previous frame, to clear pixels for the next animation frame,
 920 %  using GIF Background Dispose method.
 921 %
 922 %  Currently this only used internally, with external wrappers below.
 923 %
 924 %  The format of the OptimizeLayerFrames method is:
 925 %
 926 %      static Image *OptimizeLayerFrames(const Image *image,
 927 %               const ImageLayerMethod method, ExceptionInfo *exception)
 928 %
 929 %  A description of each parameter follows:
 930 %
 931 %    o image: the image.
 932 %
 933 %    o method: the layers type to optimize with. Must be one of...
 934 %             OptimizeImageLayer, or  OptimizePlusLayer
 935 %
 936 %    o exception: return any errors or warnings in this structure.
 937 %
 938 */
 939 /*
 940   Define a 'fake' dispose method where the frame is duplicated, with a
 941   extra zero time delay frame which does a BackgroundDisposal to clear the
 942   pixels that need to be cleared.
 943 */
 944 #define DupDispose  ((DisposeType)9)
 945 /*
 946   Another 'fake' dispose method used to removed frames that don't change.
 947 */
 948 #define DelDispose  ((DisposeType)8)
 949
 950 static Image *OptimizeLayerFrames(const Image *image,
 951   const ImageLayerMethod method, ExceptionInfo *exception)
 952 {
 953   ExceptionInfo
 954     *sans_exception;
 955
 956   Image
 957     *prev_image,
 958     *dup_image,
 959     *bgnd_image,
 960     *optimized_image;
 961
 962   RectangleInfo
 963     try_bounds,
 964     bgnd_bounds,
 965     dup_bounds,
 966     *bounds;
 967
 968   MagickBooleanType
 969     add_frames,
 970     try_cleared,
 971     cleared;
 972
 973   DisposeType
 974     *disposals;
 975
 976   register const Image
 977     *next;
 978
 979   register long
 980     i;
 981
 982   assert(image != (const Image *) NULL);
 983   assert(image->signature == MagickSignature);
 984   if (image->debug != MagickFalse)
 985     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
 986   assert(exception != (ExceptionInfo *) NULL);
 987   assert(exception->signature == MagickSignature);
 988   assert(method == OptimizeLayer ||
 989          method == OptimizeImageLayer ||
 990          method == OptimizePlusLayer);
 991
 992   /*
 993     Are we allowed to add/remove frames from animation
 994   */
 995   add_frames=method == OptimizePlusLayer ? MagickTrue : MagickFalse;
 996   /*
 997     Ensure  all the images are the same size
 998   */
 999   next=GetFirstImageInList(image);
1000   for (; next != (Image *) NULL; next=GetNextImageInList(next))
1001   {
1002     if ((next->columns != image->columns) || (next->rows != image->rows))
1003       ThrowImageException(OptionError,"ImagesAreNotTheSameSize");
1004     /*
1005       FUTURE: also check they are fully coalesced (full page settings)
1006     */
1007   }
1008   /*
1009     Allocate memory (times 2 if we allow frame additions)
1010   */
1011   next=GetFirstImageInList(image);
1012   bounds=(RectangleInfo *) AcquireQuantumMemory((size_t)
1013     GetImageListLength(next),(add_frames != MagickFalse ? 2UL : 1UL)*
1014     sizeof(*bounds));
1015   if (bounds == (RectangleInfo *) NULL)
1016     ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1017   disposals=(DisposeType *) AcquireQuantumMemory((size_t)
1018     GetImageListLength(image),(add_frames != MagickFalse ? 2UL : 1UL)*
1019     sizeof(*disposals));
1020   if (disposals == (DisposeType *) NULL)
1021     {
1022       bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
1023       ThrowImageException(ResourceLimitError,"MemoryAllocationFailed");
1024     }
1025   /*
1026     Initialise Previous Image as fully transparent
1027   */
1028   prev_image=CloneImage(next,next->page.width,next->page.height,
1029     MagickTrue,exception);
1030   if (prev_image == (Image *) NULL)
1031     {
1032       bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
1033       disposals=(DisposeType *) RelinquishMagickMemory(disposals);
1034       return((Image *) NULL);
1035     }
1036   prev_image->page=next->page;  /* ERROR: <-- should not be need, but is! */
1037   prev_image->page.x=0;
1038   prev_image->page.y=0;
1039   prev_image->dispose=NoneDispose;
1040
1041   prev_image->background_color.opacity=(Quantum) TransparentOpacity;
1042   (void) SetImageBackgroundColor(prev_image);
1043   /*
1044     Figure out the area of overlay of the first frame
1045     No pixel could be cleared as all pixels are already cleared.
1046   */
1047   disposals[0]=NoneDispose;
1048   bounds[0]=CompareImageBounds(prev_image,next,CompareAnyLayer,exception);
1049   /*
1050     Compute the bounding box of changes for each pair of images.
1051   */
1052   i=1;
1053   bgnd_image=(Image *)NULL;
1054   dup_image=(Image *)NULL;
1055   dup_bounds.width=0;
1056   dup_bounds.height=0;
1057   dup_bounds.x=0;
1058   dup_bounds.y=0;
1059   next=GetNextImageInList(next);
1060   for ( ; next != (const Image *) NULL; next=GetNextImageInList(next))
1061   {
1062     /*
1063       Assume none disposal is the best
1064     */
1065     bounds[i]=CompareImageBounds(next->previous,next,CompareAnyLayer,exception);
1066     cleared=IsBoundsCleared(next->previous,next,&bounds[i],exception);
1067     disposals[i-1]=NoneDispose;
1068     if ( bounds[i].x < 0 ) {
1069       /*
1070         Image frame is exactly the same as the previous frame!
1071         If not adding frames leave it to be cropped down to a null image.
1072         Otherwise mark previous image for deleted, transfering its crop bounds
1073         to the current image.
1074       */
1075       if ( add_frames && i>=2 ) {
1076         disposals[i-1]=DelDispose;
1077         disposals[i]=NoneDispose;
1078         bounds[i]=bounds[i-1];
1079         i++;
1080         continue;
1081       }
1082     }
1083     else
1084       {
1085         /*
1086           Compare a none disposal against a previous disposal
1087         */
1088         try_bounds=CompareImageBounds(prev_image,next,CompareAnyLayer,exception);
1089         try_cleared=IsBoundsCleared(prev_image,next,&try_bounds,exception);
1090         if ( (!try_cleared && cleared ) ||
1091                 try_bounds.width * try_bounds.height
1092                     <  bounds[i].width * bounds[i].height )
1093           {
1094             cleared=try_cleared;
1095             bounds[i]=try_bounds;
1096             disposals[i-1]=PreviousDispose;
1097           }
1098
1099         /*
1100           If we are allowed lets try a complex frame duplication.
1101           It is useless if the previous image already clears pixels correctly.
1102           This method will always clear all the pixels that need to be cleared.
1103         */
1104         dup_bounds.width=dup_bounds.height=0;
1105         if ( add_frames )
1106           {
1107             dup_image=CloneImage(next->previous,next->previous->page.width,
1108                 next->previous->page.height,MagickTrue,exception);
1109             if (dup_image == (Image *) NULL)
1110               {
1111                 bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
1112                 disposals=(DisposeType *) RelinquishMagickMemory(disposals);
1113                 prev_image=DestroyImage(prev_image);
1114                 return((Image *) NULL);
1115               }
1116             dup_bounds=CompareImageBounds(dup_image,next,CompareClearLayer,exception);
1117             ClearBounds(dup_image,&dup_bounds);
1118             try_bounds=CompareImageBounds(dup_image,next,CompareAnyLayer,exception);
1119             if ( cleared ||
1120                    dup_bounds.width*dup_bounds.height
1121                       +try_bounds.width*try_bounds.height
1122                    < bounds[i].width * bounds[i].height )
1123               {
1124                 cleared=MagickFalse;
1125                 bounds[i]=try_bounds;
1126                 disposals[i-1]=DupDispose;
1127                 /* to be finalised later, if found to be optimial */
1128               }
1129             else
1130               dup_bounds.width=dup_bounds.height=0;
1131           }
1132
1133         /*
1134           Now compare against a simple background disposal
1135         */
1136         bgnd_image=CloneImage(next->previous,next->previous->page.width,
1137           next->previous->page.height,MagickTrue,exception);
1138         if (bgnd_image == (Image *) NULL)
1139           {
1140             bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
1141             disposals=(DisposeType *) RelinquishMagickMemory(disposals);
1142             prev_image=DestroyImage(prev_image);
1143             if ( disposals[i-1] == DupDispose )
1144               bgnd_image=DestroyImage(bgnd_image);
1145             return((Image *) NULL);
1146           }
1147         bgnd_bounds=bounds[i-1];
1148         ClearBounds(bgnd_image,&bgnd_bounds);
1149         try_bounds=CompareImageBounds(bgnd_image,next,CompareAnyLayer,exception);
1150
1151         try_cleared=IsBoundsCleared(bgnd_image,next,&try_bounds,exception);
1152         if ( try_cleared )
1153           {
1154             /*
1155               Straight background disposal failed to clear pixels needed!
1156               Lets try expanding the disposal area of the previous frame, to
1157               include the pixels that are cleared.  This guaranteed
1158               to work, though may not be the most optimized solution.
1159             */
1160             try_bounds=CompareImageBounds(prev_image,next,CompareClearLayer,exception);
1161             if ( bgnd_bounds.x < 0 )
1162               bgnd_bounds = try_bounds;
1163             else
1164               {
1165                 if ( try_bounds.x < bgnd_bounds.x )
1166                   {
1167                      bgnd_bounds.width+= bgnd_bounds.x-try_bounds.x;
1168                      if ( bgnd_bounds.width < try_bounds.width )
1169                        bgnd_bounds.width = try_bounds.width;
1170                      bgnd_bounds.x = try_bounds.x;
1171                   }
1172                 else
1173                   {
1174                      try_bounds.width += try_bounds.x - bgnd_bounds.x;
1175                      if ( bgnd_bounds.width < try_bounds.width )
1176                        bgnd_bounds.width = try_bounds.width;
1177                   }
1178                 if ( try_bounds.y < bgnd_bounds.y )
1179                   {
1180                      bgnd_bounds.height += bgnd_bounds.y - try_bounds.y;
1181                      if ( bgnd_bounds.height < try_bounds.height )
1182                        bgnd_bounds.height = try_bounds.height;
1183                      bgnd_bounds.y = try_bounds.y;
1184                   }
1185                 else
1186                   {
1187                     try_bounds.height += try_bounds.y - bgnd_bounds.y;
1188                      if ( bgnd_bounds.height < try_bounds.height )
1189                        bgnd_bounds.height = try_bounds.height;
1190                   }
1191               }
1192             ClearBounds(bgnd_image,&bgnd_bounds);
1193             try_bounds=CompareImageBounds(bgnd_image,next,CompareAnyLayer,exception);
1194           }
1195         /*
1196           Test if this background dispose is smaller than any of the
1197           other methods we tryed before this (including duplicated frame)
1198         */
1199         if ( cleared ||
1200               bgnd_bounds.width*bgnd_bounds.height
1201                 +try_bounds.width*try_bounds.height
1202               < bounds[i-1].width*bounds[i-1].height
1203                   +dup_bounds.width*dup_bounds.height
1204                   +bounds[i].width*bounds[i].height )
1205           {
1206             cleared=MagickFalse;
1207             bounds[i-1]=bgnd_bounds;
1208             bounds[i]=try_bounds;
1209             if ( disposals[i-1] == DupDispose )
1210               dup_image=DestroyImage(dup_image);
1211             disposals[i-1]=BackgroundDispose;
1212           }
1213       }
1214     /*
1215        Finalise choice of dispose, set new prev_image,
1216        and junk any extra images as appropriate,
1217     */
1218     if ( disposals[i-1] == DupDispose )
1219       {
1220          if (bgnd_image != (Image *) NULL)
1221            bgnd_image=DestroyImage(bgnd_image);
1222          prev_image=DestroyImage(prev_image);
1223          prev_image=dup_image, dup_image=(Image *) NULL;
1224          bounds[i+1]=bounds[i];
1225          bounds[i]=dup_bounds;
1226          disposals[i-1]=DupDispose;
1227          disposals[i]=BackgroundDispose;
1228          i++;
1229       }
1230     else
1231       {
1232         if ( disposals[i-1] != PreviousDispose )
1233           prev_image=DestroyImage(prev_image);
1234         if ( disposals[i-1] == BackgroundDispose )
1235           prev_image=bgnd_image,  bgnd_image=(Image *)NULL;
1236         else if (bgnd_image != (Image *) NULL)
1237           bgnd_image=DestroyImage(bgnd_image);
1238         if ( dup_image != (Image *) NULL)
1239           dup_image=DestroyImage(dup_image);
1240         if ( disposals[i-1] == NoneDispose )
1241           {
1242             prev_image=CloneImage(next->previous,next->previous->page.width,
1243               next->previous->page.height,MagickTrue,exception);
1244             if (prev_image == (Image *) NULL)
1245               {
1246                 bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
1247                 disposals=(DisposeType *) RelinquishMagickMemory(disposals);
1248                 return((Image *) NULL);
1249               }
1250           }
1251       }
1252     disposals[i]=disposals[i-1];
1253     i++;
1254   }
1255   prev_image=DestroyImage(prev_image);
1256   /*
1257     Optimize all images in sequence.
1258   */
1259   sans_exception=AcquireExceptionInfo();
1260   i=0;
1261   next=GetFirstImageInList(image);
1262   optimized_image=NewImageList();
1263   while ( next != (const Image *) NULL )
1264   {
1265 #if 0 /*  For debuging */
1266     printf("image %ld :- %d  %ldx%ld%+ld%+ld\n", i, disposals[i],
1267            bounds[i].width, bounds[i].height, bounds[i].x, bounds[i].y );
1268 #endif
1269     prev_image=CloneImage(next,0,0,MagickTrue,exception);
1270     if (prev_image == (Image *) NULL)
1271       break;
1272     if ( disposals[i] == DelDispose ) {
1273       unsigned long time = 0;
1274       while ( disposals[i] == DelDispose ) {
1275         time += next->delay*1000/next->ticks_per_second;
1276         next=GetNextImageInList(next);
1277         i++;
1278       }
1279       time += next->delay*1000/next->ticks_per_second;
1280       prev_image->ticks_per_second = 100L;
1281       prev_image->delay = time*prev_image->ticks_per_second/1000;
1282     }
1283     bgnd_image=CropImage(prev_image,&bounds[i],sans_exception);
1284     prev_image=DestroyImage(prev_image);
1285     if (bgnd_image == (Image *) NULL)
1286       break;
1287     bgnd_image->dispose=disposals[i];
1288     if ( disposals[i] == DupDispose ) {
1289       bgnd_image->delay=0;
1290       bgnd_image->dispose=NoneDispose;
1291     }
1292     else
1293       next=GetNextImageInList(next);
1294     AppendImageToList(&optimized_image,bgnd_image);
1295     i++;
1296   }
1297   sans_exception=DestroyExceptionInfo(sans_exception);
1298   bounds=(RectangleInfo *) RelinquishMagickMemory(bounds);
1299   disposals=(DisposeType *) RelinquishMagickMemory(disposals);
1300   if (next != (Image *) NULL)
1301     {
1302       optimized_image=DestroyImageList(optimized_image);
1303       return((Image *) NULL);
1304     }
1305   return(GetFirstImageInList(optimized_image));
1306 }
1307 \f
1308 /*
1309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1310 %                                                                             %
1311 %                                                                             %
1312 %                                                                             %
1313 %     O p t i m i z e I m a g e L a y e r s                                   %
1314 %                                                                             %
1315 %                                                                             %
1316 %                                                                             %
1317 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1318 %
1319 %  OptimizeImageLayers() compares each image the GIF disposed forms of the
1320 %  previous image in the sequence.  From this it attempts to select the
1321 %  smallest cropped image to replace each frame, while preserving the results
1322 %  of the GIF animation.
1323 %
1324 %  The format of the OptimizeImageLayers method is:
1325 %
1326 %      Image *OptimizeImageLayers(const Image *image,
1327 %               ExceptionInfo *exception)
1328 %
1329 %  A description of each parameter follows:
1330 %
1331 %    o image: the image.
1332 %
1333 %    o exception: return any errors or warnings in this structure.
1334 %
1335 */
1336 MagickExport Image *OptimizeImageLayers(const Image *image,
1337   ExceptionInfo *exception)
1338 {
1339   return(OptimizeLayerFrames(image,OptimizeImageLayer,exception));
1340 }
1341 \f
1342 /*
1343 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1344 %                                                                             %
1345 %                                                                             %
1346 %                                                                             %
1347 %     O p t i m i z e P l u s I m a g e L a y e r s                           %
1348 %                                                                             %
1349 %                                                                             %
1350 %                                                                             %
1351 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1352 %
1353 %  OptimizeImagePlusLayers() is exactly as OptimizeImageLayers(), but may
1354 %  also add or even remove extra frames in the animation, if it improves
1355 %  the total number of pixels in the resulting GIF animation.
1356 %
1357 %  The format of the OptimizePlusImageLayers method is:
1358 %
1359 %      Image *OptimizePlusImageLayers(const Image *image,
1360 %               ExceptionInfo *exception)
1361 %
1362 %  A description of each parameter follows:
1363 %
1364 %    o image: the image.
1365 %
1366 %    o exception: return any errors or warnings in this structure.
1367 %
1368 */
1369 MagickExport Image *OptimizePlusImageLayers(const Image *image,
1370   ExceptionInfo *exception)
1371 {
1372   return OptimizeLayerFrames(image, OptimizePlusLayer, exception);
1373 }
1374 \f
1375 /*
1376 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1377 %                                                                             %
1378 %                                                                             %
1379 %                                                                             %
1380 %     O p t i m i z e I m a g e T r a n s p a r e n c y                       %
1381 %                                                                             %
1382 %                                                                             %
1383 %                                                                             %
1384 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1385 %
1386 %  OptimizeImageTransparency() takes a frame optimized GIF animation, and
1387 %  compares the overlayed pixels against the disposal image resulting from all
1388 %  the previous frames in the animation.  Any pixel that does not change the
1389 %  disposal image (and thus does not effect the outcome of an overlay) is made
1390 %  transparent.
1391 %
1392 %  WARNING: This modifies the current images directly, rather than generate
1393 %  a new image sequence.
1394 %
1395 %  The format of the OptimizeImageTransperency method is:
1396 %
1397 %      void OptimizeImageTransperency(Image *image,ExceptionInfo *exception)
1398 %
1399 %  A description of each parameter follows:
1400 %
1401 %    o image: the image sequence
1402 %
1403 %    o exception: return any errors or warnings in this structure.
1404 %
1405 */
1406 MagickExport void OptimizeImageTransparency(const Image *image,
1407      ExceptionInfo *exception)
1408 {
1409   Image
1410     *dispose_image;
1411
1412   register Image
1413     *next;
1414
1415   /*
1416     Run the image through the animation sequence
1417   */
1418   assert(image != (Image *) NULL);
1419   assert(image->signature == MagickSignature);
1420   if (image->debug != MagickFalse)
1421     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1422   assert(exception != (ExceptionInfo *) NULL);
1423   assert(exception->signature == MagickSignature);
1424   next=GetFirstImageInList(image);
1425   dispose_image=CloneImage(next,next->page.width,next->page.height,
1426     MagickTrue,exception);
1427   if (dispose_image == (Image *) NULL)
1428     return;
1429   dispose_image->page=next->page;
1430   dispose_image->page.x=0;
1431   dispose_image->page.y=0;
1432   dispose_image->dispose=NoneDispose;
1433   dispose_image->background_color.opacity=(Quantum) TransparentOpacity;
1434   (void) SetImageBackgroundColor(dispose_image);
1435
1436   while ( next != (Image *) NULL )
1437   {
1438     Image
1439       *current_image;
1440
1441     /*
1442       Overlay this frame's image over the previous disposal image
1443     */
1444     current_image=CloneImage(dispose_image,0,0,MagickTrue,exception);
1445     if (current_image == (Image *) NULL)
1446       {
1447         dispose_image=DestroyImage(dispose_image);
1448         return;
1449       }
1450     (void) CompositeImage(current_image,next->matte != MagickFalse ?
1451       OverCompositeOp : CopyCompositeOp, next,next->page.x,next->page.y);
1452     /*
1453       At this point the image would be displayed, for the delay period
1454     **
1455       Work out the disposal of the previous image
1456     */
1457     if (next->dispose == BackgroundDispose)
1458       {
1459         RectangleInfo
1460           bounds=next->page;
1461
1462         bounds.width=next->columns;
1463         bounds.height=next->rows;
1464         if (bounds.x < 0)
1465           {
1466             bounds.width+=bounds.x;
1467             bounds.x=0;
1468           }
1469         if ((long) (bounds.x+bounds.width) > (long) current_image->columns)
1470           bounds.width=current_image->columns-bounds.x;
1471         if (bounds.y < 0)
1472           {
1473             bounds.height+=bounds.y;
1474             bounds.y=0;
1475           }
1476         if ((long) (bounds.y+bounds.height) > (long) current_image->rows)
1477           bounds.height=current_image->rows-bounds.y;
1478         ClearBounds(current_image, &bounds);
1479       }
1480     if (next->dispose != PreviousDispose)
1481       {
1482         dispose_image=DestroyImage(dispose_image);
1483         dispose_image=current_image;
1484       }
1485     else
1486       current_image=DestroyImage(current_image);
1487
1488     /*
1489       Optimize Transparency of the next frame (if present)
1490     */
1491     next=GetNextImageInList(next);
1492     if ( next != (Image *) NULL ) {
1493       (void) CompositeImage(next, ChangeMaskCompositeOp,
1494           dispose_image, -(next->page.x), -(next->page.y) );
1495     }
1496   }
1497   dispose_image=DestroyImage(dispose_image);
1498   return;
1499 }
1500 \f
1501 /*
1502 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1503 %                                                                             %
1504 %                                                                             %
1505 %                                                                             %
1506 %     R e m o v e D u p l i c a t e L a y e r s                               %
1507 %                                                                             %
1508 %                                                                             %
1509 %                                                                             %
1510 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1511 %
1512 %  RemoveDuplicateLayers() removes any image that is exactly the same as the
1513 %  next image in the given image list.  Image size and virtual canvas offset
1514 %  must also match, though not the virtual canvas size itself.
1515 %
1516 %  No check is made with regards to image disposal setting, though it is the
1517 %  dispose setting of later image that is kept.  Also any time delays are also
1518 %  added together. As such coalesced image animations should still produce the
1519 %  same result, though with duplicte frames merged into a single frame.
1520 %
1521 %  The format of the RemoveDuplicateLayers method is:
1522 %
1523 %      void RemoveDuplicateLayers(Image **image, ExceptionInfo *exception)
1524 %
1525 %  A description of each parameter follows:
1526 %
1527 %    o images: the image list
1528 %
1529 %    o exception: return any errors or warnings in this structure.
1530 %
1531 */
1532 MagickExport void RemoveDuplicateLayers(Image **images,
1533      ExceptionInfo *exception)
1534 {
1535   register Image
1536     *curr,
1537     *next;
1538
1539   RectangleInfo
1540     bounds;
1541
1542   assert((*images) != (const Image *) NULL);
1543   assert((*images)->signature == MagickSignature);
1544   if ((*images)->debug != MagickFalse)
1545     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",(*images)->filename);
1546   assert(exception != (ExceptionInfo *) NULL);
1547   assert(exception->signature == MagickSignature);
1548
1549   curr=GetFirstImageInList(*images);
1550   for (; (next=GetNextImageInList(curr)) != (Image *) NULL; curr=next)
1551   {
1552     if ( curr->columns != next->columns || curr->rows != next->rows
1553          || curr->page.x != next->page.x || curr->page.y != next->page.y )
1554       continue;
1555     bounds=CompareImageBounds(curr,next,CompareAnyLayer,exception);
1556     if ( bounds.x < 0 ) {
1557       /*
1558         the two images are the same, merge time delays and delete one.
1559       */
1560       unsigned long time;
1561       time = curr->delay*1000/curr->ticks_per_second;
1562       time += next->delay*1000/next->ticks_per_second;
1563       next->ticks_per_second = 100L;
1564       next->delay = time*curr->ticks_per_second/1000;
1565       next->iterations = curr->iterations;
1566       *images = curr;
1567       (void) DeleteImageFromList(images);
1568     }
1569   }
1570   *images = GetFirstImageInList(*images);
1571 }
1572 \f
1573 /*
1574 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1575 %                                                                             %
1576 %                                                                             %
1577 %                                                                             %
1578 %     R e m o v e Z e r o D e l a y L a y e r s                               %
1579 %                                                                             %
1580 %                                                                             %
1581 %                                                                             %
1582 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1583 %
1584 %  RemoveZeroDelayLayers() removes any image that as a zero delay time. Such
1585 %  images generally represent intermediate or partial updates in GIF
1586 %  animations used for file optimization.  They are not ment to be displayed
1587 %  to users of the animation.  Viewable images in an animation should have a
1588 %  time delay of 3 or more centi-seconds (hundredths of a second).
1589 %
1590 %  However if all the frames have a zero time delay, then either the animation
1591 %  is as yet incomplete, or it is not a GIF animation.  This a non-sensible
1592 %  situation, so no image will be removed and a 'Zero Time Animation' warning
1593 %  (exception) given.
1594 %
1595 %  No warning will be given if no image was removed because all images had an
1596 %  appropriate non-zero time delay set.
1597 %
1598 %  Due to the special requirements of GIF disposal handling, GIF animations
1599 %  should be coalesced first, before calling this function, though that is not
1600 %  a requirement.
1601 %
1602 %  The format of the RemoveZeroDelayLayers method is:
1603 %
1604 %      void RemoveZeroDelayLayers(Image **image, ExceptionInfo *exception)
1605 %
1606 %  A description of each parameter follows:
1607 %
1608 %    o images: the image list
1609 %
1610 %    o exception: return any errors or warnings in this structure.
1611 %
1612 */
1613 MagickExport void RemoveZeroDelayLayers(Image **images,
1614      ExceptionInfo *exception)
1615 {
1616   Image
1617     *i;
1618
1619   assert((*images) != (const Image *) NULL);
1620   assert((*images)->signature == MagickSignature);
1621   if ((*images)->debug != MagickFalse)
1622     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",(*images)->filename);
1623   assert(exception != (ExceptionInfo *) NULL);
1624   assert(exception->signature == MagickSignature);
1625
1626   i=GetFirstImageInList(*images);
1627   for ( ; i != (Image *) NULL; i=GetNextImageInList(i))
1628     if ( i->delay != 0L ) break;
1629   if ( i == (Image *) NULL ) {
1630     (void) ThrowMagickException(exception,GetMagickModule(),OptionWarning,
1631        "ZeroTimeAnimation","`%s'",GetFirstImageInList(*images)->filename);
1632     return;
1633   }
1634   i=GetFirstImageInList(*images);
1635   while ( i != (Image *) NULL )
1636   {
1637     if ( i->delay == 0L ) {
1638       (void) DeleteImageFromList(&i);
1639       *images=i;
1640     }
1641     else
1642       i=GetNextImageInList(i);
1643   }
1644   *images=GetFirstImageInList(*images);
1645 }
1646 \f
1647 /*
1648 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1649 %                                                                             %
1650 %                                                                             %
1651 %                                                                             %
1652 %     C o m p o s i t e L a y e r s                                           %
1653 %                                                                             %
1654 %                                                                             %
1655 %                                                                             %
1656 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1657 %
1658 %  CompositeLayers() compose first image sequence (source) over the second
1659 %  image sequence (destination), using the given compose method and offsets.
1660 %
1661 %  The pointers to the image list does not have to be the start of that image
1662 %  list, but may start somewhere in the middle.  Each layer from the two image
1663 %  lists are composted together until the end of one of the image lists is
1664 %  reached.  The offset of each composition is also adjusted to match the
1665 %  virtual canvas offsets of each layer. As such the given offset is relative
1666 %  to the virtual canvas, and not the actual image.
1667 %
1668 %  No GIF disposal handling is performed, so GIF animations should be
1669 %  coalesced before use.  However this not a requirement, and individual
1670 %  layer images may have any size or offset, for special compositions.
1671 %
1672 %  Special case:- If one of the image sequences is just a single image that
1673 %  image is repeatally composed with all the images in the other image list.
1674 %  Either the source or destination lists may be the single image, for this
1675 %  situation.
1676 %
1677 %  The destination list will be expanded as needed to match number of source
1678 %  image overlaid (from current position to end of list).
1679 %
1680 %  The format of the CompositeLayers method is:
1681 %
1682 %      void CompositeLayers(Image *destination,
1683 %          const CompositeOperator compose, Image *source,
1684 %          const long x_offset, const long y_offset,
1685 %          ExceptionInfo *exception);
1686 %
1687 %  A description of each parameter follows:
1688 %
1689 %    o destination: the destination images and results
1690 %
1691 %    o source: source image(s) for the layer composition
1692 %
1693 %    o compose, x_offset, y_offset:  arguments passed on to CompositeImages()
1694 %
1695 %    o exception: return any errors or warnings in this structure.
1696 %
1697 */
1698 static inline void CompositeCanvas(Image *destination,
1699      const CompositeOperator compose, Image *source,
1700      long x_offset, long y_offset )
1701 {
1702   x_offset += source->page.x - destination->page.x;
1703   y_offset += source->page.y - destination->page.y;
1704   (void) CompositeImage(destination, compose, source, x_offset, y_offset);
1705 }
1706
1707 MagickExport void CompositeLayers(Image *destination,
1708       const CompositeOperator compose, Image *source,
1709       const long x_offset, const long y_offset,
1710       ExceptionInfo *exception)
1711 {
1712   assert(destination != (Image *) NULL);
1713   assert(destination->signature == MagickSignature);
1714   assert(source != (Image *) NULL);
1715   assert(source->signature == MagickSignature);
1716   assert(exception != (ExceptionInfo *) NULL);
1717   assert(exception->signature == MagickSignature);
1718   if (source->debug != MagickFalse || destination->debug != MagickFalse)
1719     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s - %s",
1720          source->filename, destination->filename);
1721
1722   /*
1723     Overlay single source image over destation image/list
1724   */
1725   if ( source->previous == (Image *) NULL && source->next == (Image *) NULL )
1726     while ( destination != (Image *) NULL )
1727     {
1728       CompositeCanvas(destination, compose, source, x_offset, y_offset);
1729       destination=GetNextImageInList(destination);
1730     }
1731
1732   /*
1733     Overlay source image list over single destination
1734     Generating multiple clones of destination image to match source list.
1735     Original Destination image becomes first image of generated list.
1736     As such the image list pointer does not require any change in caller.
1737     Some animation attributes however also needs coping in this case.
1738   */
1739   else if ( destination->previous == (Image *) NULL &&
1740             destination->next == (Image *) NULL )
1741   {
1742     Image *dest = CloneImage(destination,0,0,MagickTrue,exception);
1743
1744     CompositeCanvas(destination, compose, source, x_offset, y_offset);
1745     /* copy source image attributes ? */
1746     source=GetNextImageInList(source);
1747
1748     while ( source != (Image *) NULL )
1749     {
1750       AppendImageToList(&destination,
1751            CloneImage(dest,0,0,MagickTrue,exception));
1752       destination=GetLastImageInList(destination);
1753
1754       CompositeCanvas(destination, compose, source, x_offset, y_offset);
1755       destination->delay = source->delay;
1756       destination->iterations = source->iterations;
1757       source=GetNextImageInList(source);
1758     }
1759     dest=DestroyImage(dest);
1760   }
1761
1762   /*
1763     Overlay a source image list over a destination image list
1764     until either list runs out of images. (Does not repeat)
1765   */
1766   else
1767     while ( source != (Image *) NULL && destination != (Image *) NULL )
1768     {
1769       CompositeCanvas(destination, compose, source, x_offset, y_offset);
1770       source=GetNextImageInList(source);
1771       destination=GetNextImageInList(destination);
1772     }
1773 }
1774 \f
1775 /*
1776 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1777 %                                                                             %
1778 %                                                                             %
1779 %                                                                             %
1780 %     M e r g e I m a g e L a y e r s                                         %
1781 %                                                                             %
1782 %                                                                             %
1783 %                                                                             %
1784 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
1785 %
1786 %  MergeImageLayers() composes all the image layers from the current given
1787 %  image onward to produce a single image of the merged layers.
1788 %
1789 %  The inital canvas's size depends on the given ImageLayerMethod, and is
1790 %  initialized using the first images background color.  The images
1791 %  are then compositied onto that image in sequence using the given
1792 %  composition that has been assigned to each individual image.
1793 %
1794 %  The format of the MergeImageLayers is:
1795 %
1796 %      Image *MergeImageLayers(const Image *image,
1797 %        const ImageLayerMethod method, ExceptionInfo *exception)
1798 %
1799 %  A description of each parameter follows:
1800 %
1801 %    o image: the image list to be composited together
1802 %
1803 %    o method: the method of selecting the size of the initial canvas.
1804 %
1805 %        MergeLayer: Merge all layers onto a canvas just large enough
1806 %           to hold all the actual images. The virtual canvas of the
1807 %           first image is preserved but otherwise ignored.
1808 %
1809 %        FlattenLayer: Use the virtual canvas size of first image.
1810 %           Images which fall outside this canvas is clipped.
1811 %           This can be used to 'fill out' a given virtual canvas.
1812 %
1813 %        MosaicLayer: Start with the virtual canvas of the first image,
1814 %           enlarging left and right edges to contain all images.
1815 %           Images with negative offsets will be clipped.
1816 %
1817 %        TrimBoundsLayer: Determine the overall bounds of all the image
1818 %           layers just as in "MergeLayer", then adjust the the canvas
1819 %           and offsets to be relative to those bounds, without overlaying
1820 %           the images.
1821 %
1822 %           WARNING: a new image is not returned, the original image
1823 %           sequence page data is modified instead.
1824 %
1825 %    o exception: return any errors or warnings in this structure.
1826 %
1827 */
1828 MagickExport Image *MergeImageLayers(Image *image,
1829   const ImageLayerMethod method,ExceptionInfo *exception)
1830 {
1831 #define MergeLayersTag  "Merge/Layers"
1832
1833   Image
1834     *canvas;
1835
1836   MagickBooleanType
1837     proceed;
1838
1839   MagickOffsetType
1840     scene;
1841
1842   RectangleInfo
1843     page;
1844
1845   unsigned long
1846     width,
1847     height;
1848
1849   register const Image
1850     *next;
1851
1852   unsigned long
1853     number_images;
1854
1855   assert(image != (Image *) NULL);
1856   assert(image->signature == MagickSignature);
1857   if (image->debug != MagickFalse)
1858     (void) LogMagickEvent(TraceEvent,GetMagickModule(),"%s",image->filename);
1859   assert(exception != (ExceptionInfo *) NULL);
1860   assert(exception->signature == MagickSignature);
1861   /*
1862     Determine canvas image size, and its virtual canvas size and offset
1863   */
1864   page=image->page;
1865   width=image->columns;
1866   height=image->rows;
1867   switch (method)
1868   {
1869     case TrimBoundsLayer:
1870     case MergeLayer:
1871     default:
1872     {
1873       next = GetNextImageInList(image);
1874       for ( ; next != (Image *) NULL;  next=GetNextImageInList(next)) {
1875         if ( page.x > next->page.x ) {
1876              width += page.x-next->page.x;
1877              page.x = next->page.x;
1878         }
1879         if ( page.y > next->page.y ) {
1880              height += page.y-next->page.y;
1881              page.y = next->page.y;
1882         }
1883         if ( width < (next->page.x + next->columns - page.x) )
1884            width = (unsigned long) next->page.x + next->columns - page.x;
1885         if ( height < (next->page.y + next->rows - page.y) )
1886            height = (unsigned long) next->page.y + next->rows - page.y;
1887       }
1888       break;
1889     }
1890     case FlattenLayer:
1891     {
1892       if ( page.width > 0 )
1893         width=page.width;
1894       if ( page.height > 0 )
1895         height=page.height;
1896       page.x=0;
1897       page.y=0;
1898       break;
1899     }
1900     case MosaicLayer:
1901     {
1902       if ( page.width > 0 )
1903         width=page.width;
1904       if ( page.height > 0 )
1905         height=page.height;
1906       for (next=image; next != (Image *) NULL; next=GetNextImageInList(next)) {
1907         if (method == MosaicLayer) {
1908           page.x=next->page.x;
1909           page.y=next->page.y;
1910           if ( width < (next->page.x + next->columns) )
1911              width = (unsigned long) next->page.x + next->columns;
1912           if ( height < (next->page.y + next->rows) )
1913              height = (unsigned long) next->page.y + next->rows;
1914         }
1915       }
1916       page.width=width;
1917       page.height=height;
1918       page.x=0;
1919       page.y=0;
1920     }
1921     break;
1922   }
1923   /* set virtual canvas size if not defined */
1924   if ( page.width == 0 )
1925     page.width = (page.x < 0) ? width : width+page.x;
1926   if ( page.height == 0 )
1927     page.height = (page.y < 0) ? height : height+page.y;
1928
1929   /*
1930     Handle "TrimBoundsLayer" method seperatally to normal 'layer merge'
1931   */
1932   if ( method == TrimBoundsLayer ) {
1933     number_images=GetImageListLength(image);
1934     for (scene=0; scene < (long) number_images; scene++)
1935     {
1936       image->page.x -= page.x;
1937       image->page.y -= page.y;
1938       image->page.width = width;
1939       image->page.height = height;
1940       proceed=SetImageProgress(image,MergeLayersTag,scene,number_images);
1941       if (proceed == MagickFalse)
1942         break;
1943       image=GetNextImageInList(image);
1944     }
1945     return((Image *) NULL);
1946   }
1947
1948   /*
1949     Create canvas size of width and height, and background color.
1950   */
1951   canvas=CloneImage(image,width,height,MagickTrue,exception);
1952   if (canvas == (Image *) NULL)
1953     return((Image *) NULL);
1954   (void) SetImageBackgroundColor(canvas);
1955   canvas->page=page;
1956   canvas->dispose=UndefinedDispose;
1957
1958   /*
1959     Compose images onto canvas, with progress monitor
1960   */
1961   number_images=GetImageListLength(image);
1962   for (scene=0; scene < (long) number_images; scene++)
1963   {
1964     (void) CompositeImage(canvas,image->compose,image,image->page.x-
1965       canvas->page.x,image->page.y-canvas->page.y);
1966     proceed=SetImageProgress(image,MergeLayersTag,scene,number_images);
1967     if (proceed == MagickFalse)
1968       break;
1969     image=GetNextImageInList(image);
1970   }
1971   return(canvas);
1972 }
1973