OctreeQuantization.java
package libsidplay.components.mos656x;
import java.util.*;
/**
* Classic octree color quantization algorithm. Given a histogram as a packed
* color value and count of occurences, computes and returns the optimal palette
* when requested from the state of the tree.
* <p>
* The class operates on 24-bit colors. The components are called red, green, and
* blue, but they can be anything. The components should be in some coding that
* compensates for the eye's different sensitivity for errors in each component, as
* the color distance calculation and quantization assume so.
*
* @author Antti Lankila
*/
class OctreeQuantization {
/**
* Bits per component
*/
private static final int MAX_DEPTH = 10;
/**
* Bits per component lookup bucket
*/
private static final int MAX_BUCKET_DEPTH = 2;
private static final int COMPONENT_MASK = (1 << MAX_DEPTH) - 1;
/**
* Fast color lookup in the least-squares sense each color is put in the bucket.
*/
final List<List<Node>> buckets = new ArrayList<>();
/**
* The start of the quantization tree.
*/
final Node root = new Node(null);
/**
* List of current leaf nodes. leaf.parents are targets for reduction.
*/
protected final Set<Node> leaves = new HashSet<>();
/**
* Size of palette to compute.
*/
private final int max;
/**
* Quantizer instance. Make a new quantizer for a specific number of colors, add
* colors, and finally ask for a palette.
*
* @param max size of palette to quantize to.
*/
protected OctreeQuantization(final int max) {
this.max = max;
}
private class Node {
private boolean leaf;
protected int reference;
protected int red;
protected int green;
protected int blue;
protected final Node parent;
private final Node[] children = new Node[8];
protected Node(final Node parent) {
this.parent = parent;
}
/**
* Select the appropriate child node based on the requested depth
*
* @param packed the packed color to pick child for
* @param depth 0-based depth
* @return child index
*/
private int pickChild(int packed, int depth) {
int r = packed >> MAX_DEPTH * 2 + depth - 1 & 1;
int g = packed >> MAX_DEPTH * 1 + depth - 1 & 1;
int b = packed >> MAX_DEPTH * 0 + depth - 1 & 1;
return r << 2 | g << 1 | b;
}
/**
* Add a weighed pixel into a tree.
*
* @param packed the packed data to add.
* @param weight the weight of this pixel
* @param depth current depth
*/
protected void add(final int packed, final int weight, final int depth) {
reference += weight;
if (leaf) {
red += (packed >> MAX_DEPTH * 2 & COMPONENT_MASK) * weight;
green += (packed >> MAX_DEPTH * 1 & COMPONENT_MASK) * weight;
blue += (packed >> MAX_DEPTH * 0 & COMPONENT_MASK) * weight;
return;
}
final int i = pickChild(packed, depth);
if (children[i] == null) {
children[i] = new Node(this);
if (depth == 1) {
leaves.add(children[i]);
children[i].leaf = true;
}
}
children[i].add(packed, weight, depth - 1);
}
/**
* Find the nearest node in a tree to color
*
* @param packed the color to look for
* @param depth current depth
* @return nearest node
*/
@SuppressWarnings("unused")
protected Node find(final int packed, final int depth) {
final int i = pickChild(packed, depth);
/* Further nodes in a tree? Enter. */
if (children[i] != null) {
return children[i].find(packed, depth - 1);
}
/*
* In a general case we might end up in a situation where this node is not a leaf
* node. However, because we only ask after colors that are added to the tree,
* we will always be a leaf here.
*/
return this;
}
/**
* Reduce a node and mark it as a leaf.
* <p>
* Invariant: because this only collapses child nodes into itself, the reference
* count of parent remains unchanged.
* <p>
* Because we are calling reduction always for the least referenced parent, every
* parent candidate for reduction can only have leaf nodes under it.
* <p>
*/
protected void reduce() {
/* collapse all subnodes into this node. */
for (final Node c : children) {
if (c == null) {
continue;
}
red += c.red;
green += c.green;
blue += c.blue;
leaves.remove(c);
}
leaf = true;
leaves.add(this);
Arrays.fill(children, null);
}
/**
* Construct the original kind of packed color value from the node.
*
* @return packed color.
*/
protected int toPacked() {
final int r = red / reference;
final int g = green / reference;
final int b = blue / reference;
return r << MAX_DEPTH * 2 | g << MAX_DEPTH * 1 | b << MAX_DEPTH * 0;
}
/**
* Calculate distance in 3d geometric terms between two colors. YUV palette is
* used: it should be a perceptively linear coding system.
*
* @param a color to compare to.
* @return distance squared.
*/
protected int distance(final Node a) {
final int dr = a.red / a.reference - red / reference;
final int dg = a.green / a.reference - green / reference;
final int db = a.blue / a.reference - blue / reference;
return dr * dr + dg * dg + db * db;
}
}
/**
* Add a color to the quantization algorithm.
*
* @param color The packed color to add.
* @param weight Number of occurences of this color. (How important it is.)
*/
protected void addColor(final int color, final int weight) {
root.add(color, weight, MAX_DEPTH);
}
/**
* Actually quantize the palette.
* <p>
* Called when a palette is requested.
*/
private void quantize() {
if (leaves.size() <= max) {
return;
}
/*
* Create a sorted tree that can be used to select the least useful colors.
*/
final TreeSet<Node> parentSet = new TreeSet<>((o1, o2) -> {
/*
* Tree is sorted according to usage count and secondarily by id to disambiguate
* equally used colors.
*/
if (o1.reference > o2.reference) {
return 1;
}
if (o1.reference < o2.reference) {
return -1;
}
final int id1 = System.identityHashCode(o1);
final int id2 = System.identityHashCode(o2);
return Integer.compare(id1, id2);
});
for (final Node leaf : leaves) {
parentSet.add(leaf.parent);
}
/* Reduce nodes until we have dispensed with enough colors. */
while (leaves.size() > max) {
final Node parent = parentSet.first();
parentSet.remove(parent);
parent.reduce();
parentSet.add(parent.parent);
}
}
/**
* Returns the optimized palette of constructor-time specified length. Pads with
* 0 if more colors were requested than existed in source material.
*
*/
protected int[] getPalette() {
quantize();
/* Construct accelerator structure */
buckets.clear();
for (int i = 0; i < 1 << 3 * MAX_BUCKET_DEPTH; i++) {
buckets.add(new ArrayList<>());
}
int i = 0;
final int[] finalPalette = new int[max];
for (final Node node : leaves) {
finalPalette[i++] = node.toPacked();
bucketStore(node);
}
return finalPalette;
}
/**
* Generate color buckets for faster color lookup. Each color is distributed to
* the buckets at a granularity of 2 bits per component (4 * 4 * 4 = 64 buckets in
* total).
*
* @param node the node to store in buckets
*/
private void bucketStore(Node node) {
int color = node.toPacked();
/* MAX_DEPTH bits */
int r_ref = color >> MAX_DEPTH * 2 & COMPONENT_MASK;
int g_ref = color >> MAX_DEPTH * 1 & COMPONENT_MASK;
int b_ref = color >> MAX_DEPTH * 0 & COMPONENT_MASK;
/* Reduced to 2 bits now. */
r_ref >>= MAX_DEPTH - MAX_BUCKET_DEPTH;
g_ref >>= MAX_DEPTH - MAX_BUCKET_DEPTH;
b_ref >>= MAX_DEPTH - MAX_BUCKET_DEPTH;
/* Scan the cube around the reference value */
for (int dr = -1; dr <= 0; dr += 1) {
for (int dg = -1; dg <= 0; dg += 1) {
for (int db = -1; db <= 0; db += 1) {
int r = r_ref + dr;
int g = g_ref + dg;
int b = b_ref + db;
/* Exclude outside buckets */
if (r < 0 || g < 0 || b < 0) {
continue;
}
if (r > 7 || g > 7 || b > 7) {
continue;
}
int bucketIdx = r << MAX_BUCKET_DEPTH * 2 | g << MAX_BUCKET_DEPTH * 1 | b << MAX_BUCKET_DEPTH * 0;
buckets.get(bucketIdx).add(node);
}
}
}
}
/**
* Do a nearest-node scan looking for the best match.
*
* @param color Color to get the best match of.
* @return best node from a simple scan
*/
public int lookup(final int color) {
/* MAX_DEPTH bits */
int r_ref = color >> MAX_DEPTH * 2 & COMPONENT_MASK;
int g_ref = color >> MAX_DEPTH * 1 & COMPONENT_MASK;
int b_ref = color >> MAX_DEPTH * 0 & COMPONENT_MASK;
/* Reduced to 3 bits now. */
int rb = r_ref >> MAX_DEPTH - MAX_BUCKET_DEPTH;
int gb = g_ref >> MAX_DEPTH - MAX_BUCKET_DEPTH;
int bb = b_ref >> MAX_DEPTH - MAX_BUCKET_DEPTH;
int bucketIdx = rb << MAX_BUCKET_DEPTH * 2 | gb << MAX_BUCKET_DEPTH * 1 | bb << MAX_BUCKET_DEPTH * 0;
Iterable<Node> bucket = buckets.get(bucketIdx);
if (!bucket.iterator().hasNext()) {
/* Nothing nearby. Hopefully this doesn't happen often. */
bucket = leaves;
}
int bestDistance = Integer.MAX_VALUE;
Node bestMatch = null;
Node n = new Node(null);
n.red = r_ref;
n.green = g_ref;
n.blue = b_ref;
n.reference = 1;
for (Node s : bucket) {
int trialDistance = n.distance(s);
if (trialDistance < bestDistance) {
bestDistance = trialDistance;
bestMatch = s;
}
}
assert bestMatch != null;
// Node fast = root.find(color, MAX_DEPTH);
// System.out.println("All that work paid off by: "+
// fast.distance(bestMatch));
return bestMatch.toPacked();
}
}