granicus.if.org Git - imagemagick/blob - MagickCore/layer.c

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