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