Package net.sourceforge.jiu.color.quantization

# 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:
  - `MedianCutQuantizer`

## Field Summary

Fields
Modifier and Type
Field
Description
`private Vector`
`compressibleNodes`
`private Vector`
`contouringPairs`
`static final int`
`DEFAULT_NUM_PASSES`
The default number of passes, used if they are not specified with `setNumPasses(int)`.
`static final double`
`DEFAULT_TAU`
The default tau value, used if none is specified with `setTau(double)`.
`private MedianCutNode[]`
`leaves`
`private double[]`
`meanC`
`private double`
`meanS`
`private int`
`numPasses`
`private Palette`
`palette`
`private MedianCutQuantizer`
`quantizer`
`private double[]`
`stdDevC`
`private double`
`stdDevS`
`private double`
`sumMeanStdDevS`
`private double`
`tau`

## Constructor Summary

Constructors
Constructor
Description
`MedianCutContourRemoval()`

## Method Summary

Modifier and Type
Method
Description
`private double`
`computeDistance(int index1, int index2)`
`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.
`private Vector`
`createContouringIndexList()`
Takes
`private void`
`findColorPairs(CoOccurrenceFrequencyMatrix matrix, CoOccurrenceMatrix A)`
`static void`
`main(String[] args)`
Small command line application that performs a contour removal on an image.
`private void`
`mergeAndSplit()`
`void`
`process()`
This method does the actual work of the operation.
`void`
`setNumPasses(int newValue)`
Specify the number of contour removal passes to be performed.
`void`
`setQuantizer(MedianCutQuantizer medianCutQuantizer)`
Set the `MedianCutQuantizer` object to be used with this contour removal operation.
`void`
`setTau(double newValue)`
Specify the tau value to be used by this operation.
`private Object[]`
`toArray(Vector list)`
Converts a Vector to an Object array.

### Methods inherited from class net.sourceforge.jiu.ops.ImageToImageOperation

`canInputAndOutputBeEqual, ensureImagesHaveSameResolution, ensureInputImageIsAvailable, ensureOutputImageResolution, getInputImage, getOutputImage, setCanInputAndOutputBeEqual, setInputImage, setOutputImage`

### Methods inherited from class net.sourceforge.jiu.ops.Operation

`addProgressListener, addProgressListeners, getAbort, removeProgressListener, setAbort, setProgress, setProgress`

### Methods inherited from class java.lang.Object

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

## 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:
  - Constant Field Values

### 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:
  - Constant Field Values

### 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

public void process() throws MissingParameterException, OperationFailedException, WrongParameterException
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
  `OperationFailedException`
  `WrongParameterException` - if at least one of the input parameters was not initialized appropriately (values out of the valid interval, etc.)

### 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