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