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