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

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