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

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