Commits

Fredrik Lundh committed 7ee696c Merge

Merged in PNG branch.

Comments (0)

Files changed (15)

 
   http://bitbucket.org/effbot/pil-2009-raclette/changesets/
 
-(1.2a0 snapshot)
++ Added Oliver Tonnhofer's PNG and Quantization work:
+
+  - Added support for PNG8 images with transparency
+  - Added a new color quantizer: Image.FASTOCTTREE
+  - Added new compress_level and compress_type options to
+    the PNG writer to get more control over ZIP compression
+
++ Restored support for Python 2.2, for now.
+
+(1.2a0-20110108 snapshot)
+
++ Setup now migrates all Python files if installing under Python
+  3.1 or later.
 
 + Modules must now be imported using the full package name.  The
   PIL.pth helper has been removed.
 Imaging/libImaging/ImPlatform.h
 
 Imaging/libImaging/Quant.h
+Imaging/libImaging/QuantOctree.h
 Imaging/libImaging/QuantHash.h
 Imaging/libImaging/QuantHeap.h
 Imaging/libImaging/QuantDefines.h
 Imaging/libImaging/Paste.c
 Imaging/libImaging/Point.c
 Imaging/libImaging/Quant.c
+Imaging/libImaging/QuantOctree.c
 Imaging/libImaging/QuantHash.c
 Imaging/libImaging/QuantHeap.c
 Imaging/libImaging/RankFilter.c
 WEB = 0
 ADAPTIVE = 1
 
+MEDIANCUT = 0
+MAXCOVERAGE = 1
+FASTOCTREE = 2
+
 # categories
 NORMAL = 0
 SEQUENCE = 1
 CONTAINER = 2
 
+if hasattr(core, 'DEFAULT_STRATEGY'):
+    DEFAULT_STRATEGY = core.DEFAULT_STRATEGY
+    FILTERED = core.FILTERED
+    HUFFMAN_ONLY = core.HUFFMAN_ONLY
+    RLE = core.RLE
+    FIXED = core.FIXED
+    
+
 # --------------------------------------------------------------------
 # Registries
 
             self.palette.mode = "RGB"
             self.palette.rawmode = None
             if "transparency" in self.info:
-                self.im.putpalettealpha(self.info["transparency"], 0)
+                if isNumberType(self.info["transparency"]):
+                    self.im.putpalettealpha(self.info["transparency"], 0)
+                else:
+                    alphas = "".join(map(chr, self.info["transparency"]))
+                    self.im.putpalettealphas(alphas)
                 self.palette.mode = "RGBA"
         if self.im:
             return self.im.pixel_access(self.readonly)
         # methods:
         #    0 = median cut
         #    1 = maximum coverage
+        #    2 = fast octree
 
         # NOTE: this functionality will be moved to the extended
         # quantizer interface in a later version of PIL.

PIL/PngImagePlugin.py

 }
 
 
+_simple_palette = re.compile('^\xff+\x00+$')
+
 # --------------------------------------------------------------------
 # Support classes.  Suitable for PNG and related formats like MNG etc.
 
         return s
 
     def chunk_tRNS(self, pos, len):
-
         # transparency
         s = self.fp.saferead(len)
         if self.im_mode == "P":
             i = s.find(chr(0))
             if i >= 0:
                 self.im_info["transparency"] = i
+            if _simple_palette.match(s.tostring()):
+                i = s.find(s, chr(0))
+                if i >= 0:
+                    self.im_info["transparency"] = i
+            else:
+                self.im_info["transparency"] = list(s)
         elif self.im_mode == "L":
             self.im_info["transparency"] = s.unpack("!H")
         elif self.im_mode == "RGB":
         dictionary = ""
 
     im.encoderconfig = ("optimize" in im.encoderinfo, dictionary)
+    im.encoderconfig = ("optimize" in im.encoderinfo,
+        im.encoderinfo.get("compress_level", -1),
+        im.encoderinfo.get("compress_type", -1),
+        dictionary)
 
     # get the corresponding PNG mode
     try:
             chunk(fp, "tRNS", o16(red) + o16(green) + o16(blue))
         else:
             raise IOError("cannot use transparency for this mode")
+    else:
+        if im.mode == "P" and im.im.getpalettemode() == "RGBA":
+            alpha = im.im.getpalette("RGBA", "A")
+            chunk(fp, "tRNS", alpha)
 
     if 0:
         # FIXME: to be supported some day

Tests/test_file_png.py

 
     assert_no_exception(lambda: im.load())
 
+def test_load_transparent_p():
+    file = "Tests/images/pil123p.png"
+    im = Image.open(file)
+
+    assert_image(im, "P", (162, 150))
+    im = im.convert("RGBA")
+    assert_image(im, "RGBA", (162, 150))
+
+    # image has 124 uniqe qlpha values
+    assert_equal(len(im.split()[3].getcolors()), 124)
+
 def test_load_verify():
     # Check open/load/verify exception (@PIL150)
 

Tests/test_image_quantize.py

     im = im.quantize(palette=lena("P"))
     assert_image(im, "P", im.size)
     
+def test_octree_quantize():
+    im = lena()
+
+    im = im.quantize(100, Image.FASTOCTREE)
+    assert_image(im, "P", im.size)
+
+    assert len(im.getcolors()) == 100
     return palette;
 }
 
+static PyObject* 
+_getpalettemode(ImagingObject* self, PyObject* args)
+{
+    if (!self->image->palette) {
+	PyErr_SetString(PyExc_ValueError, no_palette);
+	return NULL;
+    }
+
+    return PyString_FromString(self->image->palette->mode);
+}
+
 static inline int
 _getxy(PyObject* xy, int* x, int *y)
 {
 }
 
 static PyObject* 
+_putpalettealphas(ImagingObject* self, PyObject* args)
+{
+    int i;
+    UINT8 *values;
+    int length;
+    if (!PyArg_ParseTuple(args, "s#", &values, &length))
+	return NULL;
+
+    if (!self->image->palette) {
+	PyErr_SetString(PyExc_ValueError, no_palette);
+	return NULL;
+    }
+
+    if (length  > 256) {
+	PyErr_SetString(PyExc_ValueError, outside_palette);
+	return NULL;
+    }
+
+    strcpy(self->image->palette->mode, "RGBA");
+    for (i=0; i<length; i++) {
+	self->image->palette->palette[i*4+3] = (UINT8) values[i];
+    }
+
+    Py_INCREF(Py_None);
+    return Py_None;
+}
+
+static PyObject* 
 _putpixel(ImagingObject* self, PyObject* args)
 {
     Imaging im;
     {"setmode", (PyCFunction)im_setmode, 1},
     
     {"getpalette", (PyCFunction)_getpalette, 1},
+    {"getpalettemode", (PyCFunction)_getpalettemode, 1},
     {"putpalette", (PyCFunction)_putpalette, 1},
     {"putpalettealpha", (PyCFunction)_putpalettealpha, 1},
+    {"putpalettealphas", (PyCFunction)_putpalettealphas, 1},
 
 #ifdef WITH_IMAGECHOPS
     /* Channel operations (ImageChops) */
 #endif
 
 #ifdef HAVE_LIBZ
+#include "zlib.h"
+  /* zip encoding strategies */
+  PyModule_AddIntConstant(m, "DEFAULT_STRATEGY", Z_DEFAULT_STRATEGY);
+  PyModule_AddIntConstant(m, "FILTERED", Z_FILTERED);
+  PyModule_AddIntConstant(m, "HUFFMAN_ONLY", Z_HUFFMAN_ONLY);
+  PyModule_AddIntConstant(m, "RLE", Z_RLE);
+  PyModule_AddIntConstant(m, "FIXED", Z_FIXED);
   {
     extern const char* ImagingZipVersion(void);
     PyDict_SetItemString(d, "zlib_version", PyString_FromString(ImagingZipVersion()));
   }
 #endif
+
 }
     char* mode;
     char* rawmode;
     int optimize = 0;
+    int compress_level = -1;
+    int compress_type = -1;
     char* dictionary = NULL;
     int dictionary_size = 0;
-    if (!PyArg_ParseTuple(args, "ss|is#", &mode, &rawmode, &optimize,
+    if (!PyArg_ParseTuple(args, "ss|iiis#", &mode, &rawmode, &optimize,
+			  &compress_level, &compress_type,
 			  &dictionary, &dictionary_size))
 	return NULL;
 
 	((ZIPSTATE*)encoder->state.context)->mode = ZIP_PNG_PALETTE;
 
     ((ZIPSTATE*)encoder->state.context)->optimize = optimize;
+    ((ZIPSTATE*)encoder->state.context)->compress_level = compress_level;
+    ((ZIPSTATE*)encoder->state.context)->compress_type = compress_type;
     ((ZIPSTATE*)encoder->state.context)->dictionary = dictionary;
     ((ZIPSTATE*)encoder->state.context)->dictionary_size = dictionary_size;
 

libImaging/Fill.c

 ImagingFill(Imaging im, const void* colour)
 {
     int x, y;
+    ImagingSectionCookie cookie;
 
     if (im->type == IMAGING_TYPE_SPECIAL) {
         /* use generic API */
                 memset(im->image[y], 0, im->linesize);
         }
     } else {
+        ImagingSectionEnter(&cookie);
         INT32 c = 0L;
         memcpy(&c, colour, im->pixelsize);
         if (im->image32 && c != 0L) {
             for (y = 0; y < im->ysize; y++)
                 memset(im->image[y], cc, im->linesize);
         }
+        ImagingSectionLeave(&cookie);
     }
 
     return im;

libImaging/Quant.c

 #include <time.h>
 
 #include "Quant.h"
+#include "QuantOctree.h"
 
 #include "QuantDefines.h"
 #include "QuantHash.h"
     int result;
     unsigned long* newData;
     Imaging imOut;
+    int withAlpha = 0;
+    ImagingSectionCookie cookie;
 
     if (!im)
 	return ImagingError_ModeError();
         return (Imaging) ImagingError_ValueError("bad number of colors");
 
     if (strcmp(im->mode, "L") != 0 && strcmp(im->mode, "P") != 0 &&
-        strcmp(im->mode, "RGB"))
+        strcmp(im->mode, "RGB") != 0 && strcmp(im->mode, "RGBA") !=0)
         return ImagingError_ModeError();
 
+    /* only octree supports RGBA */
+    if (!strcmp(im->mode, "RGBA") && mode != 2)
+       return ImagingError_ModeError();
+
     p = malloc(sizeof(Pixel) * im->xsize * im->ysize);
     if (!p)
         return ImagingError_MemoryError();
                 p[i].c.b = pp[v*4+2];
             }
 
-    } else if (!strcmp(im->mode, "RGB")) {
+    } else if (!strcmp(im->mode, "RGB") || !strcmp(im->mode, "RGBA")) {
         /* true colour */
 
         for (i = y = 0; y < im->ysize; y++)
         return (Imaging) ImagingError_ValueError("internal error");
     }
 
+    ImagingSectionEnter(&cookie);
+
     switch (mode) {
     case 0:
         /* median cut */
             kmeans
             );
         break;
+    case 2:
+        if (!strcmp(im->mode, "RGBA")) {
+            withAlpha = 1; 
+        }
+        result = quantize_octree(
+            p,
+            im->xsize*im->ysize,
+            colors,
+            &palette,
+            &paletteLength,
+            &newData,
+            withAlpha
+            );
+        break;
     default:
         result = 0;
         break;
     }
 
     free(p);
+    ImagingSectionLeave(&cookie);
 
     if (result) {
-
         imOut = ImagingNew("P", im->xsize, im->ysize);
+        ImagingSectionEnter(&cookie);
 
         for (i = y = 0; y < im->ysize; y++)
             for (x=0; x < im->xsize; x++)
             *pp++ = palette[i].c.r;
             *pp++ = palette[i].c.g;
             *pp++ = palette[i].c.b;
-            *pp++ = 255;
+            if (withAlpha) {
+               *pp++ = palette[i].c.a;
+            } else {
+               *pp++ = 255;
+            }
         }
         for (; i < 256; i++) {
             *pp++ = 0;
             *pp++ = 255;
         }
 
+        if (withAlpha) {
+            strcpy(imOut->palette->mode, "RGBA");
+        }
+
         free(palette);
+        ImagingSectionLeave(&cookie);
 
         return imOut;
 

libImaging/QuantOctree.c

+/* Copyright (c) 2010 Oliver Tonnhofer <olt@bogosoft.com>, Omniscale
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+// THE SOFTWARE.
+*/
+
+/*
+// This file implements a variation of the octree color quantization algorithm.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "Quant.h"
+
+typedef struct _ColorBucket{
+   /* contains palette index when used for look up cube */
+   unsigned long count;
+   unsigned long r;
+   unsigned long g;
+   unsigned long b;
+   unsigned long a;
+} *ColorBucket;
+
+typedef struct _ColorCube{
+   unsigned int rBits, gBits, bBits, aBits;
+   unsigned int rWidth, gWidth, bWidth, aWidth;
+   unsigned int rOffset, gOffset, bOffset, aOffset;
+
+   long size;
+   ColorBucket buckets;
+} *ColorCube;
+
+#define MAX(a, b) (a)>(b) ? (a) : (b)
+
+static ColorCube
+new_color_cube(int r, int g, int b, int a) {
+   ColorCube cube;
+
+   cube = malloc(sizeof(struct _ColorCube));
+   if (!cube) return NULL;
+
+   cube->rBits = MAX(r, 0);
+   cube->gBits = MAX(g, 0);
+   cube->bBits = MAX(b, 0);
+   cube->aBits = MAX(a, 0);
+
+   /* the width of the cube for each dimension */
+   cube->rWidth = 1<<cube->rBits;
+   cube->gWidth = 1<<cube->gBits;
+   cube->bWidth = 1<<cube->bBits;
+   cube->aWidth = 1<<cube->aBits;
+
+   /* the offsets of each color */
+
+   cube->rOffset = cube->gBits + cube->bBits + cube->aBits;
+   cube->gOffset = cube->bBits + cube->aBits;
+   cube->bOffset = cube->aBits;
+   cube->aOffset = 0;
+
+   /* the number of color buckets */
+   cube->size = cube->rWidth * cube->gWidth * cube->bWidth * cube->aWidth;
+   cube->buckets = calloc(cube->size, sizeof(struct _ColorBucket));
+
+   if (!cube->buckets) {
+      free(cube);
+      return NULL;
+   }
+   return cube;
+}
+
+static void
+free_color_cube(ColorCube cube) {
+   if (cube != NULL) {
+      free(cube->buckets);
+      free(cube);
+   }
+}
+
+static long
+color_bucket_offset_pos(const ColorCube cube,
+   unsigned int r, unsigned int g, unsigned int b, unsigned int a)
+{
+   return r<<cube->rOffset | g<<cube->gOffset | b<<cube->bOffset | a<<cube->aOffset;
+}
+
+static long
+color_bucket_offset(const ColorCube cube, const Pixel *p) {
+   unsigned int r = p->c.r>>(8-cube->rBits);
+   unsigned int g = p->c.g>>(8-cube->gBits);
+   unsigned int b = p->c.b>>(8-cube->bBits);
+   unsigned int a = p->c.a>>(8-cube->aBits);
+   return color_bucket_offset_pos(cube, r, g, b, a);
+}
+
+static ColorBucket
+color_bucket_from_cube(const ColorCube cube, const Pixel *p) {
+   unsigned int offset = color_bucket_offset(cube, p);
+   return &cube->buckets[offset];
+}
+
+static void
+add_color_to_color_cube(const ColorCube cube, const Pixel *p) {
+   ColorBucket bucket = color_bucket_from_cube(cube, p);
+   bucket->count += 1;
+   bucket->r += p->c.r;
+   bucket->g += p->c.g;
+   bucket->b += p->c.b;
+   bucket->a += p->c.a;
+}
+
+static long
+count_used_color_buckets(const ColorCube cube) {
+   long usedBuckets = 0;
+   long i;
+   for (i=0; i < cube->size; i++) {
+      if (cube->buckets[i].count > 0) {
+         usedBuckets += 1;
+      }
+   }
+   return usedBuckets;
+}
+
+static void
+avg_color_from_color_bucket(const ColorBucket bucket, Pixel *dst) {
+   float count = bucket->count;
+   dst->c.r = (int)(bucket->r / count);
+   dst->c.g = (int)(bucket->g / count);
+   dst->c.b = (int)(bucket->b / count);
+   dst->c.a = (int)(bucket->a / count);
+}
+
+static int
+compare_bucket_count(const ColorBucket a, const ColorBucket b) {
+   return b->count - a->count;
+}
+
+static ColorBucket
+create_sorted_color_palette(const ColorCube cube) {
+   ColorBucket buckets;
+   buckets = malloc(sizeof(struct _ColorBucket)*cube->size);
+   if (!buckets) return NULL;
+   memcpy(buckets, cube->buckets, sizeof(struct _ColorBucket)*cube->size);
+
+   qsort(buckets, cube->size, sizeof(struct _ColorBucket),
+         (int (*)(void const *, void const *))&compare_bucket_count);
+
+   return buckets;
+}
+
+void add_bucket_values(ColorBucket src, ColorBucket dst) {
+   dst->count += src->count;
+   dst->r += src->r;
+   dst->g += src->g;
+   dst->b += src->b;
+   dst->a += src->a;
+}
+
+/* expand or shrink a given cube to level */
+static ColorCube copy_color_cube(const ColorCube cube,
+   int rBits, int gBits, int bBits, int aBits)
+{
+   unsigned int r, g, b, a;
+   long src_pos, dst_pos;
+   unsigned int src_reduce[4] = {0}, dst_reduce[4] = {0};
+   unsigned int width[4];
+   ColorCube result;
+
+   result = new_color_cube(rBits, gBits, bBits, aBits);
+   if (!result) return NULL;
+
+   if (cube->rBits > rBits) {
+      dst_reduce[0] = cube->rBits - result->rBits;
+      width[0] = cube->rWidth;
+   } else {
+      src_reduce[0] = result->rBits - cube->rBits;
+      width[0] = result->rWidth;
+   }
+   if (cube->gBits > gBits) {
+      dst_reduce[1] = cube->gBits - result->gBits;
+      width[1] = cube->gWidth;
+   } else {
+      src_reduce[1] = result->gBits - cube->gBits;
+      width[1] = result->gWidth;
+   }
+   if (cube->bBits > bBits) {
+      dst_reduce[2] = cube->bBits - result->bBits;
+      width[2] = cube->bWidth;
+   } else {
+      src_reduce[2] = result->bBits - cube->bBits;
+      width[2] = result->bWidth;
+   }
+   if (cube->aBits > aBits) {
+      dst_reduce[3] = cube->aBits - result->aBits;
+      width[3] = cube->aWidth;
+   } else {
+      src_reduce[3] = result->aBits - cube->aBits;
+      width[3] = result->aWidth;
+   }
+
+   for (r=0; r<width[0]; r++) {
+      for (g=0; g<width[1]; g++) {
+         for (b=0; b<width[2]; b++) {
+            for (a=0; a<width[3]; a++) {
+               src_pos = color_bucket_offset_pos(cube,
+                                               r>>src_reduce[0],
+                                               g>>src_reduce[1],
+                                               b>>src_reduce[2],
+                                               a>>src_reduce[3]);
+               dst_pos = color_bucket_offset_pos(result,
+                                               r>>dst_reduce[0],
+                                               g>>dst_reduce[1],
+                                               b>>dst_reduce[2],
+                                               a>>dst_reduce[3]);
+               add_bucket_values(
+                  &cube->buckets[src_pos],
+                  &result->buckets[dst_pos]
+               );
+            }
+         }
+      }
+   }
+   return result;
+}
+
+void
+subtract_color_buckets(ColorCube cube, ColorBucket buckets, long nBuckets) {
+   ColorBucket minuend, subtrahend;
+   long i;
+   Pixel p;
+   for (i=0; i<nBuckets; i++) {
+      subtrahend = &buckets[i];
+      avg_color_from_color_bucket(subtrahend, &p);
+      minuend = color_bucket_from_cube(cube, &p);
+      minuend->count -= subtrahend->count;
+      minuend->r -= subtrahend->r;
+      minuend->g -= subtrahend->g;
+      minuend->b -= subtrahend->b;
+      minuend->a -= subtrahend->a;
+   }
+}
+
+static void
+set_lookup_value(const ColorCube cube, const Pixel *p, long value) {
+   ColorBucket bucket = color_bucket_from_cube(cube, p);
+   bucket->count = value;
+}
+
+unsigned long
+lookup_color(const ColorCube cube, const Pixel *p) {
+   ColorBucket bucket = color_bucket_from_cube(cube, p);
+   return bucket->count;
+}
+
+void add_lookup_buckets(ColorCube cube, ColorBucket palette, long nColors, long offset) {
+   long i;
+   Pixel p;
+   for (i=offset; i<offset+nColors; i++) {
+      avg_color_from_color_bucket(&palette[i], &p);
+      set_lookup_value(cube, &p, i);
+   }
+}
+
+ColorBucket
+combined_palette(ColorBucket bucketsA, long nBucketsA, ColorBucket bucketsB, long nBucketsB) {
+   ColorBucket result;
+   result = malloc(sizeof(struct _ColorBucket)*(nBucketsA+nBucketsB));
+   memcpy(result, bucketsA, sizeof(struct _ColorBucket) * nBucketsA);
+   memcpy(&result[nBucketsA], bucketsB, sizeof(struct _ColorBucket) * nBucketsB);
+   return result;
+}
+
+static Pixel *
+create_palette_array(const ColorBucket palette, unsigned int paletteLength) {
+   Pixel *paletteArray;
+   unsigned int i;
+
+   paletteArray = malloc(sizeof(Pixel)*paletteLength);
+   if (!paletteArray) return NULL;
+
+   for (i=0; i<paletteLength; i++) {
+      avg_color_from_color_bucket(&palette[i], &paletteArray[i]);
+   }
+   return paletteArray;
+}
+
+static void
+map_image_pixels(const Pixel *pixelData,
+                 unsigned long nPixels,
+                 const ColorCube lookupCube,
+                 unsigned long *pixelArray)
+{
+   long i;
+   for (i=0; i<nPixels; i++) {
+      pixelArray[i] = lookup_color(lookupCube, &pixelData[i]);
+   }
+}
+
+const int CUBE_LEVELS[8]       = {4, 4, 4, 0, 2, 2, 2, 0};
+const int CUBE_LEVELS_ALPHA[8] = {3, 4, 3, 3, 2, 2, 2, 2};
+
+int quantize_octree(Pixel *pixelData,
+          unsigned long nPixels,
+          unsigned long nQuantPixels,
+          Pixel **palette,
+          unsigned long *paletteLength,
+          unsigned long **quantizedPixels,
+          int withAlpha)
+{
+   ColorCube fineCube = NULL;
+   ColorCube coarseCube = NULL;
+   ColorCube lookupCube = NULL;
+   ColorCube coarseLookupCube = NULL;
+   ColorBucket paletteBucketsCoarse = NULL;
+   ColorBucket paletteBucketsFine = NULL;
+   ColorBucket paletteBuckets = NULL;
+   unsigned long *qp = NULL;
+   long i;
+   long nCoarseColors, nFineColors, nAlreadySubtracted;
+   const int *cubeBits;
+
+   if (withAlpha) {
+       cubeBits = CUBE_LEVELS_ALPHA;
+   }
+   else {
+       cubeBits = CUBE_LEVELS;
+   }
+
+   /*
+   Create two color cubes, one fine grained with 8x16x8=1024
+   colors buckets and a coarse with 4x4x4=64 color buckets.
+   The coarse one guarantes that there are color buckets available for
+   the whole color range (assuming nQuantPixels > 64).
+
+   For a quantization to 256 colors all 64 coarse colors will be used
+   plus the 192 most used color buckets from the fine color cube.
+   The average of all colors within one bucket is used as the actual
+   color for that bucket.
+
+    For images with alpha the cubes gets a forth dimension,
+    8x16x8x8 and 4x4x4x4.
+   */
+
+   /* create fine cube */
+   fineCube = new_color_cube(cubeBits[0], cubeBits[1],
+                             cubeBits[2], cubeBits[3]);
+   if (!fineCube) goto error;
+   for (i=0; i<nPixels; i++) {
+      add_color_to_color_cube(fineCube, &pixelData[i]);
+   }
+
+   /* create coarse cube */
+   coarseCube = copy_color_cube(fineCube, cubeBits[4], cubeBits[5],
+                                          cubeBits[6], cubeBits[7]);
+   if (!coarseCube) goto error;
+   nCoarseColors = count_used_color_buckets(coarseCube);
+
+   /* limit to nQuantPixels */
+   if (nCoarseColors > nQuantPixels)
+      nCoarseColors = nQuantPixels;
+
+   /* how many space do we have in our palette for fine colors? */
+   nFineColors = nQuantPixels - nCoarseColors;
+
+   /* create fine color palette */
+   paletteBucketsFine = create_sorted_color_palette(fineCube);
+   if (!paletteBucketsFine) goto error;
+
+   /* remove the used fine colors from the coarse cube */
+   subtract_color_buckets(coarseCube, paletteBucketsFine, nFineColors);
+
+   /* did the substraction cleared one or more coarse bucket? */
+   while (nCoarseColors > count_used_color_buckets(coarseCube)) {
+      /* then we can use the free buckets for fine colors */
+      nAlreadySubtracted = nFineColors;
+      nCoarseColors = count_used_color_buckets(coarseCube);
+      nFineColors = nQuantPixels - nCoarseColors;
+      subtract_color_buckets(coarseCube, &paletteBucketsFine[nAlreadySubtracted],
+                             nFineColors-nAlreadySubtracted);
+   }
+
+   /* create our palette buckets with fine and coarse combined */
+   paletteBucketsCoarse = create_sorted_color_palette(coarseCube);
+   if (!paletteBucketsCoarse) goto error;
+   paletteBuckets = combined_palette(paletteBucketsCoarse, nCoarseColors,
+                                     paletteBucketsFine, nFineColors);
+
+   free(paletteBucketsFine);
+   paletteBucketsFine = NULL;
+   free(paletteBucketsCoarse);
+   paletteBucketsCoarse = NULL;
+
+   /* add all coarse colors to our coarse lookup cube. */
+   coarseLookupCube = new_color_cube(cubeBits[4], cubeBits[5],
+                                     cubeBits[6], cubeBits[7]);
+   if (!coarseLookupCube) goto error;
+   add_lookup_buckets(coarseLookupCube, paletteBuckets, nCoarseColors, 0);
+
+   /* expand coarse cube (64) to larger fine cube (4k). the value of each
+      coarse bucket is then present in the according 64 fine buckets. */
+   lookupCube = copy_color_cube(coarseLookupCube, cubeBits[0], cubeBits[1],
+                                                  cubeBits[2], cubeBits[3]);
+   if (!lookupCube) goto error;
+
+   /* add fine colors to the lookup cube */
+   add_lookup_buckets(lookupCube, paletteBuckets, nFineColors, nCoarseColors);
+
+   /* create result pixles and map palatte indices */
+   qp = malloc(sizeof(Pixel)*nPixels);
+   if (!qp) goto error;
+   map_image_pixels(pixelData, nPixels, lookupCube, qp);
+
+   /* convert palette buckets to RGB pixel palette */
+   *palette = create_palette_array(paletteBuckets, nQuantPixels);
+   if (!(*palette)) goto error;
+
+   *quantizedPixels = qp;
+   *paletteLength = nQuantPixels;
+
+   free_color_cube(coarseCube);
+   free_color_cube(fineCube);
+   free_color_cube(lookupCube);
+   free_color_cube(coarseLookupCube);
+   free(paletteBuckets);
+   return 1;
+
+error:
+   /* everything is initialized to NULL
+      so we are safe to call free */
+   free(qp);
+   free_color_cube(lookupCube);
+   free_color_cube(coarseLookupCube);
+   free(paletteBucketsCoarse);
+   free(paletteBucketsFine);
+   free_color_cube(coarseCube);
+   free_color_cube(fineCube);
+   return 0;
+}

libImaging/QuantOctree.h

+#ifndef __QUANT_OCTREE_H__
+#define __QUANT_OCTREE_H__
+
+int quantize_octree(Pixel *,
+          unsigned long,
+          unsigned long,
+          Pixel **,
+          unsigned long *,
+          unsigned long **,
+          int);
+
+#endif
 
     /* Optimize (max compression) SLOW!!! */
     int optimize;
+    
+    /* 0 no compression, 9 best compression, -1 default compression */
+    int compress_level;
+    /* compression strategy Z_XXX */
+    int compress_type;
 
     /* Predefined dictionary (experimental) */
     char* dictionary;

libImaging/ZipEncode.c

 {
     ZIPSTATE* context = (ZIPSTATE*) state->context;
     int err;
+    int compress_level, compress_type;
     UINT8* ptr;
     int i, bpp, s, sum;
     ImagingSectionCookie cookie;
 	context->z_stream.next_in = 0;
 	context->z_stream.avail_in = 0;
 
+	compress_level = (context->optimize) ? Z_BEST_COMPRESSION
+					     : context->compress_level;
+
+	if (context->compress_type == -1) {
+	    compress_type = (context->mode == ZIP_PNG) ? Z_FILTERED
+						       : Z_DEFAULT_STRATEGY;
+	} else {
+	    compress_type = context->compress_type;
+	}
+
 	err = deflateInit2(&context->z_stream,
 			   /* compression level */
-			   (context->optimize) ? Z_BEST_COMPRESSION
-					       : Z_DEFAULT_COMPRESSION,
+			   compress_level,
 			   /* compression method */
 			   Z_DEFLATED,
 			   /* compression memory resources */
 			   15, 9,
 			   /* compression strategy (image data are filtered)*/
-			   (context->mode == ZIP_PNG) ? Z_FILTERED
-						      : Z_DEFAULT_STRATEGY);
+			   compress_type);
 	if (err < 0) {
 	    state->errcode = IMAGING_CODEC_CONFIG;
 	    return -1;
     "Geometry", "GetBBox", "GifDecode", "GifEncode", "HexDecode",
     "Histo", "JpegDecode", "JpegEncode", "LzwDecode", "Matrix",
     "ModeFilter", "MspDecode", "Negative", "Offset", "Pack",
-    "PackDecode", "Palette", "Paste", "Quant", "QuantHash",
+    "PackDecode", "Palette", "Paste", "Quant", "QuantOctree", "QuantHash",
     "QuantHeap", "PcdDecode", "PcxDecode", "PcxEncode", "Point",
     "RankFilter", "RawDecode", "RawEncode", "Storage", "SunRleDecode",
     "TgaRleDecode", "Unpack", "UnpackYCC", "UnsharpMask", "XbmDecode",