Module imagingbook.common
Package imagingbook.common.color.quantize

Class OctreeQuantizer

java.lang.Object
imagingbook.common.color.quantize.OctreeQuantizer
All Implemented Interfaces:
ColorQuantizer
public class OctreeQuantizer extends Object implements ColorQuantizer

This class implements color quantization based on the octree method. It is a re-factored version of an implementation (OctTreeOpImage.java) used in Sun's JAI (Java Advanced Imaging) framework, which – in turn – is based on a C implementation (quantize.c) by John Cristy in 1992 as part of ImageMagick. The associated source code can be found here, the original license note is provided at the bottom of this source file. This implementation is similar but not identical to the original octree quantization algorithm described in [1].

This implementation uses a modified strategy for pruning the octree for better efficiency. "Quick quantization" means that original colors are mapped to their color index by simply finding the containing octree node. Otherwise, the closest quantized color (in terms of Euclidean distance) is searched for, which is naturally slower. See Sec. 13.4 of [2] for more details.

[1] M. Gervautz and W. Purgathofer, "A simple method for color quantization: octree quantization", in A. Glassner (editor), Graphics Gems I, pp. 287–293. Academic Press, New York (1990).
[2] W. Burger, M.J. Burge, Digital Image Processing – An Algorithmic Introduction, 3rd ed, Springer (2022).

Version:
2022/11/05

  • Field Summary

    Fields inherited from interface imagingbook.common.color.quantize.ColorQuantizer

    MAX_RGB

  • Constructor Summary

    Constructors
    Constructor
    Description
    OctreeQuantizer(int[] pixels, int K)
    Constructor, creates a new OctreeQuantizer with up to K colors, but never more than the number of colors found in the supplied image.
    OctreeQuantizer(int[] pixels, int K, boolean quick)
    Constructor, creates a new OctreeQuantizer with up to K colors, but never more than the number of colors found in the supplied image.

  • Method Summary

    Modifier and Type
    Method
    Description
    int
    findColorIndex(int p, float[][] colormap)
    Finds the color table index of the color that is "closest" to the supplied RGB color (minimum Euclidean distance in color space).
    float[][]
    getColorMap()
    Retrieves the color map produced by this color quantizer.
    void
    listNodes()
    Lists the octree nodes to System.out (for debugging only).

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface imagingbook.common.color.quantize.ColorQuantizer

    getColorCount, quantize, quantize, quantize

  • Constructor Details

    • OctreeQuantizer

      public OctreeQuantizer(int[] pixels, int K)
      Constructor, creates a new OctreeQuantizer with up to K colors, but never more than the number of colors found in the supplied image. Quick quantization is turned off by default.
      Parameters:
      pixels - an image as a aRGB-encoded int array
      K - the desired number of colors (1 or more)

    • OctreeQuantizer

      public OctreeQuantizer(int[] pixels, int K, boolean quick)
      Constructor, creates a new OctreeQuantizer with up to K colors, but never more than the number of colors found in the supplied image. "Quick" quantization can be selected, which means that original colors are mapped to their color index by simply finding the containing octree node. Otherwise, the closest quantized color (in terms of Euclidean distance) is searched for, which is naturally slower but usually gives better results. This setting only affects the final assignment of input colors to the nearest reference colors, the reference colors themselves are not changed.
      Parameters:
      pixels - an image as a aRGB-encoded int array
      K - the desired number of colors (1 or more)
      quick - turns "quick quantization" on or off

  • Method Details

    • listNodes

      public void listNodes()
      Lists the octree nodes to System.out (for debugging only).

    • getColorMap

      public float[][] getColorMap()
      Description copied from interface: ColorQuantizer
      Retrieves the color map produced by this color quantizer. The returned array is in the format float[idx][rgb], where rgb = 0 (red), 1 (green), 2 (blue) and 0 ≤ idx < nColors.
      Specified by:
      getColorMap in interface ColorQuantizer
      Returns:
      The table of reference (quantization) colors.

    • findColorIndex

      public int findColorIndex(int p, float[][] colormap)
      Description copied from interface: ColorQuantizer
      Finds the color table index of the color that is "closest" to the supplied RGB color (minimum Euclidean distance in color space). This method may be overridden by inheriting classes, for example, to use quick indexing in the octree method.
      Specified by:
      findColorIndex in interface ColorQuantizer
      Parameters:
      p - Original color, encoded as an ARGB integer.
      colormap - a color map (float)
      Returns:
      The associated color table index.