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