Commits

Oliver Tonnhofer committed 20ee6db

renaming of node to bucket; some refactoring

Comments (0)

Files changed (1)

libImaging/QuantOctree.c

 
 #include "Quant.h"
 
-typedef struct _ColorNode{
+typedef struct _ColorBucket{
    unsigned long count;
    unsigned long r;
    unsigned long g;
    unsigned long b;
-} *ColorNode;
+} *ColorBucket;
 
 typedef struct _ColorCube{
-   int level;
-   int rBits, gBits, bBits;
-   int rWidth, gWidth, bWidth;
-   int rOffset, gOffset, bOffset;
-   int size;
-   ColorNode nodes;
+   unsigned int level;
+   unsigned int rBits, gBits, bBits;
+   unsigned int rWidth, gWidth, bWidth;
+   unsigned int rOffset, gOffset, bOffset;
+   long size;
+   ColorBucket buckets;
 } *ColorCube;
 
 static ColorCube
    cube->gBits = level;
    cube->bBits = level;
    
+   /* the width of the cube for each dimension */
    cube->rWidth = 1<<cube->rBits;
    cube->gWidth = 1<<cube->gBits;
    cube->bWidth = 1<<cube->bBits;
    
+   /* the offsets of each color */
    cube->rOffset = cube->rBits + cube->gBits;
    cube->gOffset = cube->gBits;
    cube->bOffset = 0;
    
+   /* the number of color buckets */
    cube->size = cube->rWidth * cube->gWidth * cube->bWidth;
-   cube->nodes = calloc(cube->size, sizeof(struct _ColorNode));
+   cube->buckets = calloc(cube->size, sizeof(struct _ColorBucket));
    
-   if (!cube->nodes) {
+   if (!cube->buckets) {
       free(cube);
       return NULL;
    }
 
 static void
 free_color_cube(ColorCube cube) {
-   if (cube->nodes != NULL)
-      free(cube->nodes);
-   if (cube != NULL)
+   if (cube != NULL) {
+      free(cube->buckets);
       free(cube);
+   }
 }
 
-static int
-color_node_offset_pos(const ColorCube cube, int r, int g, int b) {
+static long
+color_bucket_offset_pos(const ColorCube cube,
+   unsigned int r, unsigned int g, unsigned int b)
+{
    return r<<cube->rOffset | g<<cube->gOffset | b<<cube->bOffset;
 }
 
-static int
-color_node_offset(const ColorCube cube, const Pixel *p) {
-   int r = p->c.r>>(8-cube->rBits);
-   int g = p->c.g>>(8-cube->gBits);
-   int b = p->c.b>>(8-cube->bBits);
-   return color_node_offset_pos(cube, r, g, b);
+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);
+   return color_bucket_offset_pos(cube, r, g, b);
 }
 
-
-static ColorNode
-color_node_from_cube(const ColorCube cube, const Pixel *p) {
-   int offset = color_node_offset(cube, p);
-   return &cube->nodes[offset];
+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) {
-   ColorNode node = color_node_from_cube(cube, p);
-   node->count += 1;
-   node->r += p->c.r;
-   node->g += p->c.g;
-   node->b += p->c.b;
+   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;
 }
 
 static long
-count_used_color_nodes(const ColorCube cube) {
-   long usedNodes = 0;
-   int i;
+count_used_color_buckets(const ColorCube cube) {
+   long usedBuckets = 0;
+   long i;
    for (i=0; i < cube->size; i++) {
-      if (cube->nodes[i].count > 0) {
-         usedNodes += 1;
+      if (cube->buckets[i].count > 0) {
+         usedBuckets += 1;
       }
    }
-   return usedNodes;
+   return usedBuckets;
 }
 
 static void
-avg_color_from_color_node(const ColorNode node, Pixel *dst) {
-   float count = node->count;
-   dst->c.r = (int)(node->r / count);
-   dst->c.g = (int)(node->g / count);
-   dst->c.b = (int)(node->b / count);
+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);
 }
 
 static int
-compare_node_count(const ColorNode a, const ColorNode b) {
+compare_bucket_count(const ColorBucket a, const ColorBucket b) {
    return b->count - a->count;
 }
 
-static ColorNode
-create_color_cube_palette(const ColorCube cube) {
-   ColorNode nodes;
-   nodes = malloc(sizeof(struct _ColorNode)*cube->size);
-   if (!nodes) return NULL;
-   memcpy(nodes, cube->nodes, sizeof(struct _ColorNode)*cube->size);
+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(nodes, cube->size, sizeof(struct _ColorNode), 
-         (int (*)(void const *, void const *))&compare_node_count);
+   qsort(buckets, cube->size, sizeof(struct _ColorBucket), 
+         (int (*)(void const *, void const *))&compare_bucket_count);
    
-   return nodes;
+   return buckets;
 }
 
-void add_node_values(ColorNode src, ColorNode dst) {
+void add_bucket_values(ColorBucket src, ColorBucket dst) {
    dst->count += src->count;
    dst->r += src->r;
    dst->g += src->g;
    dst->b += src->b;
 }
 
-static ColorCube copy_color_cube(const ColorCube cube, int level) {
-   int r, g, b;
-   int src_pos, dst_pos;
-   int src_reduce, dst_reduce;
-   int width;
+static ColorCube copy_color_cube(const ColorCube cube, unsigned int level) {
+   unsigned int r, g, b;
+   long src_pos, dst_pos;
+   unsigned int src_reduce, dst_reduce;
+   unsigned int width;
    ColorCube result;
    
    result = new_color_cube(level);
    for (r=0; r<width; r++) {
       for (g=0; g<width; g++) {
          for (b=0; b<width; b++) {
-            src_pos = color_node_offset_pos(cube,
+            src_pos = color_bucket_offset_pos(cube,
                                             r>>src_reduce,
                                             g>>src_reduce,
                                             b>>src_reduce);
-            dst_pos = color_node_offset_pos(result,
+            dst_pos = color_bucket_offset_pos(result,
                                             r>>dst_reduce,
                                             g>>dst_reduce,
                                             b>>dst_reduce);
-            add_node_values(
-               &cube->nodes[src_pos],
-               &result->nodes[dst_pos]
+            add_bucket_values(
+               &cube->buckets[src_pos],
+               &result->buckets[dst_pos]
             );
          }
       }
    return result;
 }
 
-void subtract_color_nodes(ColorCube cube, ColorNode nodes, long nNodes) {
-   ColorNode minuend, subtrahend;
+void
+subtract_color_buckets(ColorCube cube, ColorBucket buckets, long nBuckets) {
+   ColorBucket minuend, subtrahend;
    long i;
    Pixel p;
-   for (i=0; i<nNodes; i++) {
-      subtrahend = &nodes[i];
-      avg_color_from_color_node(subtrahend, &p);
-      minuend = color_node_from_cube(cube, &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;
 
 static void
 set_lookup_value(const ColorCube cube, const Pixel *p, long value) {
-   ColorNode node = color_node_from_cube(cube, p);
-   node->count = value;
+   ColorBucket bucket = color_bucket_from_cube(cube, p);
+   bucket->count = value;
 }
 
 unsigned long
 lookup_color(const ColorCube cube, const Pixel *p) {
-   ColorNode node = color_node_from_cube(cube, p);
-   return node->count;
+   ColorBucket bucket = color_bucket_from_cube(cube, p);
+   return bucket->count;
 }
 
 static ColorCube
 create_lookup_color_cube(
    const ColorCube cube,
-   ColorNode palette,
+   ColorBucket palette,
    int nColors)
 {
    ColorCube lookupCube;
    Pixel p;
    int i;
-   lookupCube = malloc(sizeof(struct _ColorCube));
+
+   lookupCube = new_color_cube(cube->level);
    if (!lookupCube) return NULL;
-   memcpy(lookupCube, cube, sizeof(struct _ColorCube));
-   lookupCube->nodes = calloc(cube->size, sizeof(struct _ColorNode));
-   if (!lookupCube->nodes) {
-      free(lookupCube);
-      return NULL;
-   }
    
    for (i=0; i<nColors; i++) {
-      avg_color_from_color_node(&palette[i], &p);
+      avg_color_from_color_bucket(&palette[i], &p);
       set_lookup_value(lookupCube, &p, i);
    }
    return lookupCube;
 }
 
 
-void add_lookup_nodes(ColorCube cube, ColorNode palette, long nColors, long offset) {
-   int i;
+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_node(&palette[i], &p);
+      avg_color_from_color_bucket(&palette[i], &p);
       set_lookup_value(cube, &p, i);
    }
 }
 
-ColorNode combined_palette_nodes(ColorNode nodesA, int nNodesA, ColorNode nodesB, int nNodesB) {
-   ColorNode result;
-   result = malloc(sizeof(struct _ColorNode)*(nNodesA+nNodesB));
-   memcpy(result, nodesA, sizeof(struct _ColorNode) * nNodesA);
-   memcpy(&result[nNodesA], nodesB, sizeof(struct _ColorNode) * nNodesB);
+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 ColorNode palette, unsigned int paletteLength) {
+create_palette_array(const ColorBucket palette, unsigned int paletteLength) {
    Pixel *paletteArray;
-   long i;
+   unsigned int i;
    
    paletteArray = malloc(sizeof(Pixel)*paletteLength);
    if (!paletteArray) return NULL;
    
    for (i=0; i<paletteLength; i++) {
-      avg_color_from_color_node(&palette[i], &paletteArray[i]);
+      avg_color_from_color_bucket(&palette[i], &paletteArray[i]);
    }
    return paletteArray;
 }
           unsigned long **quantizedPixels,
           int kmeans)
 {
-   ColorCube fineCube;
-   ColorCube coarseCube;
-   ColorCube lookupCube, coarseLookupCube;
-   ColorNode paletteNodesCoarse;
-   ColorNode paletteNodesFine;
-   ColorNode paletteNodes;
+   ColorCube fineCube = NULL;
+   ColorCube coarseCube = NULL;
+   ColorCube lookupCube = NULL;
+   ColorCube coarseLookupCube = NULL;
+   ColorBucket paletteBucketsCoarse = NULL;
+   ColorBucket paletteBucketsFine = NULL;
+   ColorBucket paletteBuckets = NULL;
    unsigned long *qp;
    long i;
    long nCoarseColors, nFineColors;
    
    /*
    Create two color cubes, one fine grained with 16x16x16=4096
-   colors nodes and a coarse with 4*4*4=64 color nodes.
-   The coarse one guarantes that there are color nodes available for
-   the whole color range. The most used color nodes from the fine color
+   colors buckets and a coarse with 4*4*4=64 color buckets.
+   The coarse one guarantes that there are color buckets available for
+   the whole color range. The most used color buckets from the fine color
    cube will be used.
    */
    
    
    coarseCube = copy_color_cube(fineCube, 2);
    if (!coarseCube) goto error_1;
-   nCoarseColors = count_used_color_nodes(coarseCube);
+   nCoarseColors = count_used_color_buckets(coarseCube);
    
    /* TODO nCoarseColors > nQuantPixels */
    
    nFineColors = nQuantPixels - nCoarseColors;
-   paletteNodesFine = create_color_cube_palette(fineCube);
-   if (!paletteNodesFine) goto error_2;
-   subtract_color_nodes(coarseCube, paletteNodesFine, nFineColors);
+   paletteBucketsFine = create_sorted_color_palette(fineCube);
+   if (!paletteBucketsFine) goto error_2;
+   subtract_color_buckets(coarseCube, paletteBucketsFine, nFineColors);
    
-   if (nCoarseColors > count_used_color_nodes(coarseCube)) {
-      nCoarseColors = count_used_color_nodes(coarseCube);
+   if (nCoarseColors > count_used_color_buckets(coarseCube)) {
+      nCoarseColors = count_used_color_buckets(coarseCube);
       nFineColors = nQuantPixels - nCoarseColors;
-      subtract_color_nodes(coarseCube, paletteNodesFine, nFineColors);
+      subtract_color_buckets(coarseCube, paletteBucketsFine, nFineColors);
    }
    
-   paletteNodesCoarse = create_color_cube_palette(coarseCube);
-   if (!paletteNodesCoarse) goto error_3;
+   paletteBucketsCoarse = create_sorted_color_palette(coarseCube);
+   if (!paletteBucketsCoarse) goto error_3;
    
-   paletteNodes = combined_palette_nodes(paletteNodesCoarse, nCoarseColors,
-                                         paletteNodesFine, nFineColors);
+   paletteBuckets = combined_palette(paletteBucketsCoarse, nCoarseColors,
+                                     paletteBucketsFine, nFineColors);
    
-   free(paletteNodesFine);
-   paletteNodesFine = NULL;
-   free(paletteNodesCoarse);
-   paletteNodesCoarse = NULL;
+   free(paletteBucketsFine);
+   paletteBucketsFine = NULL;
+   free(paletteBucketsCoarse);
+   paletteBucketsCoarse = NULL;
    
    coarseLookupCube = new_color_cube(2);
    if (!coarseLookupCube) goto error_4;
-   add_lookup_nodes(coarseLookupCube, paletteNodes, nCoarseColors, 0);
+   add_lookup_buckets(coarseLookupCube, paletteBuckets, nCoarseColors, 0);
    
    lookupCube = copy_color_cube(coarseLookupCube, 4);
    if (!lookupCube) goto error_5;
    
-   add_lookup_nodes(lookupCube, paletteNodes, nFineColors, nCoarseColors);
+   add_lookup_buckets(lookupCube, paletteBuckets, nFineColors, nCoarseColors);
       
    qp = malloc(sizeof(Pixel)*nPixels);
    if (!qp) goto error_6;
 
    map_image_pixels(pixelData, nPixels, lookupCube, qp);
    
-   *palette = create_palette_array(paletteNodes, nQuantPixels);
+   *palette = create_palette_array(paletteBuckets, nQuantPixels);
    if (!(*palette)) goto error_7;
    
    *quantizedPixels = qp;
    free_color_cube(fineCube);
    free_color_cube(lookupCube);
    free_color_cube(coarseLookupCube);
-   free(paletteNodes);
+   free(paletteBuckets);
    return 1;
 
 error_7:
 error_5:
    free_color_cube(coarseLookupCube);
 error_4:
-   free(paletteNodesCoarse);
+   free(paletteBucketsCoarse);
 error_3:
-   free(paletteNodesFine);
+   free(paletteBucketsFine);
 error_2:
    free_color_cube(coarseCube);
 error_1: