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