Class MedianCutContourRemoval

java.lang.Object
net.sourceforge.jiu.ops.Operation
net.sourceforge.jiu.ops.ImageToImageOperation
net.sourceforge.jiu.color.quantization.MedianCutContourRemoval

public class MedianCutContourRemoval extends ImageToImageOperation
Performs the Median Cut color quantization algorithm in combination with a contour removal algorithm.

Quantization is an operation that reduces the number of colors in an image while trying to remain as close to the original image as possible. Standard Median Cut quantization is implemented in the MedianCutQuantizer class.

This class implements an algorithm that improves the standard implementation. It repeatedly calls the original quantizer and adjusts the palette in order to reduce the amount of contouring errors.

Image types

This operation requires an RGB24Image object as input and produces a Paletted8Image as output.

Usage example

 RGB24Image inputImage = ...; // image to be processed, from a file etc. 
 MedianCutQuantizer quantizer = new MedianCutQuantizer();
 quantizer.setPaletteSize(256);
 MedianCutContourRemoval removal = new MedianCutContourRemoval();
 removal.setQuantizer(quantizer);
 removal.setInputImage(inputImage);
 removal.setTau(11.0);
 removal.setNumPasses(3);
 removal.process();
 PixelImage outputImage = removal.getOutputImage();
 

Rationale - why an extension to Median Cut?

Quantization without dithering can lead to contouring (banding) in the output image. The contours introduced that way are not only ugly but they may lead to erroneous results when processing that quantized image. Dithering, an alternative group of algorithms used in combination with quantizers to improve output quality, leads to output which is more pleasant to the human eye. However, it introduces noise that may not be acceptable when the output image is to be further processed by image processing algorithms. Instead, this algorithm attempts to adjust the palette found by the Median Cut algorithm. The adjustments aim at reducing the amount of contouring caused by a palette found in a previous Median Cut operation.

How the contour removal algorithm works

  • First, a normal Median Cut quantization operation is performed. The class MedianCutQuantizer is used for that purpose. This results in a palette and an output image that was mapped from the original using the palette.
  • Now a CoOccurrenceFrequencyMatrix is created from a CoOccurrenceMatrix, which is in turn created from the paletted image that was produced in the previous step. The co-occurrence frequency matrix stores how often a pixel value j is the neighbor of pixel i in the image, in relation to all occurrences of i. The matrix stores this information as double values between 0.0 and 1.0. If the value is 0.6, j makes 60 percent of all neighboring pixels of i.
  • Using certain heuristics that take advantage of the above mentioned matrices, colors are classified into three groups:
    • contouring color pairs which contribute significantly to the contouring,
    • compressible color pairs, two colors which are similar to each other and not contouring, and
    • all colors which are not part of one of the two color pair types described before.
    The tau value which can be specified with setTau(double) is a distance value in RGB space (tau is adjusted for an RGB cube where each axis can take values from 0 to 255). It is used to define a threshold for similar colors. A pair of compressible colors may not differ by more than tau. It is guaranteed that no color can be both compressible and contouring.
  • Note that each palette color generated by the Median Cut algorithm represents a cuboid part of the RGB color cube. For each pair of compressible colors, their corresponding cuboids are neighbors in the cube. Now a number N of palette entries is changed. That number N is either the number of compressible color pairs found, or the number of contouring color pairs found, whichever is smaller. If N equals zero, nothing can be done and the algorithm terminates.
  • Now N swap operations are performed on the palette. Two palette entries of a compressible color pair are merged to form one palette entry. Their colors are similar so it will not decrease image quality much. The newly freed palette entry is used to split one color of a contouring color pair into two, thus allowing to represent a gradient type section in the image with an additional color.
  • The original truecolor image is mapped to the new, modified palette. This whole process can now be performed again with the modified palette. That's why this operation has a setNumPasses(int) method. Usually, more than eight iterations do not make a difference.
For an in-depth description of the algorithm see the journal article mentioned in the Credits section below.

Credits

The algorithm was developed by Jefferey Shufelt and described in his article Texture Analysis for Enhanced Color Image Quantization. CVGIP: Graphical Model and Image Processing 59(3): 149-163 (1997).
Author:
Marco Schmidt
See Also:
  • Field Details

    • DEFAULT_TAU

      public static final double DEFAULT_TAU
      The default tau value, used if none is specified with setTau(double). Check the class documentation to find out more about the meaning of tau: MedianCutContourRemoval.
      See Also:
    • DEFAULT_NUM_PASSES

      public static final int DEFAULT_NUM_PASSES
      The default number of passes, used if they are not specified with setNumPasses(int). Check the class documentation to find out more about the meaning of that number of passes: MedianCutContourRemoval.
      See Also:
    • compressibleNodes

      private Vector compressibleNodes
    • contouringPairs

      private Vector contouringPairs
    • leaves

      private MedianCutNode[] leaves
    • meanC

      private double[] meanC
    • meanS

      private double meanS
    • numPasses

      private int numPasses
    • palette

      private Palette palette
    • quantizer

      private MedianCutQuantizer quantizer
    • stdDevS

      private double stdDevS
    • stdDevC

      private double[] stdDevC
    • sumMeanStdDevS

      private double sumMeanStdDevS
    • tau

      private double tau
  • Constructor Details

    • MedianCutContourRemoval

      public MedianCutContourRemoval()
  • Method Details

    • computeDistance

      private double computeDistance(int index1, int index2)
    • computeStatistics

      private void computeStatistics(CoOccurrenceFrequencyMatrix matrix)
      Computes the mean and standard deviation (stddev) values and from the argument matrix and initializes the mean / stddev fields of this class with them.
      Parameters:
      matrix -
    • createContouringIndexList

      private Vector createContouringIndexList()
      Takes
      Returns:
    • findColorPairs

      private void findColorPairs(CoOccurrenceFrequencyMatrix matrix, CoOccurrenceMatrix A)
    • main

      public static void main(String[] args) throws Exception
      Small command line application that performs a contour removal on an image. The first and only argument must be the name of image file from which the image to be quantized is loaded.
      Parameters:
      args - program arguments; must have length one, the only argument being the input image file name
      Throws:
      Exception
    • mergeAndSplit

      private void mergeAndSplit()
    • process

      Description copied from class: Operation
      This method does the actual work of the operation. It must be called after all parameters have been given to the operation object.
      Overrides:
      process in class Operation
      Throws:
      MissingParameterException - if any mandatory parameter was not given to the operation
      WrongParameterException - if at least one of the input parameters was not initialized appropriately (values out of the valid interval, etc.)
      OperationFailedException
    • setQuantizer

      public void setQuantizer(MedianCutQuantizer medianCutQuantizer)
      Set the MedianCutQuantizer object to be used with this contour removal operation. This is a mandatory parameter. If process gets called before the quantizer object was specified, a MissingParameterException is thrown.
      Parameters:
      medianCutQuantizer - the quantizer object that will get used by this operation
    • setNumPasses

      public void setNumPasses(int newValue)
      Specify the number of contour removal passes to be performed. Check out the section How the contour removal algorithm works to learn more about the meaning of this value. If this method is not called the default value DEFAULT_NUM_PASSES is used.
      Parameters:
      newValue - number of passes, 1 or higher
      Throws:
      IllegalArgumentException - if the argument is 0 or smaller
    • setTau

      public void setTau(double newValue)
      Specify the tau value to be used by this operation. Check out the section How the contour removal algorithm works to learn more about the meaning of this value. If this method is not called the default value DEFAULT_TAU is used.
      Parameters:
      newValue - tau value, 0.0 or higher
      Throws:
      IllegalArgumentException - if the argument is smaller than 0.0
    • toArray

      private Object[] toArray(Vector list)
      Converts a Vector to an Object array. Since Java 1.2 Vector has a toArray method, but we cannot rely on 1.2 being available.
      Parameters:
      list - Vector with objects
      Returns:
      Object array with elements from list, in the same order