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