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