querbeet bei Color und ColorLookUpTable eingepflanzt:
[spoiler]
package dithering;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
class HistColor implements Comparable<HistColor>, Cloneable {
private static final float RED_SCALE = 0.299f;
private static final float GREEN_SCALE = 0.587f;
private static final float BLUE_SCALE = 0.114f;
int numPixels;
private int argb;
int r;
int g;
int b;
int ri;
int gi;
int bi;
final int hash;
HistColor(int r, int g, int b) {
this((r << 16) + (g << 8) + b);
}
HistColor(int argb) {
this.argb = argb;
this.r = getRed();
this.g = getGreen();
this.b = getBlue();
ri = r / ColorLookUpTable.r2;
gi = g / ColorLookUpTable.r2;
bi = b / ColorLookUpTable.r2;
final int prime = 31;
int result = 1;
result = prime * result + b;
result = prime * result + g;
result = prime * result + r;
hash = result;
}
/**
* @inheritDoc
*/
@Override
public int hashCode() {
return hash;
}
/**
* @inheritDoc
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
HistColor other = (HistColor) obj;
if (b != other.b)
return false;
if (g != other.g)
return false;
if (r != other.r)
return false;
return true;
}
final int getRed() {
return (argb >> 16) & 0xFF;
}
final void setRed(int red) {
red &= 0xFF;
argb &= 0xFF00FFFF;
argb |= (red << 16);
}
final int getGreen() {
return (argb >> 8) & 0xFF;
}
final void setGreen(int green) {
green &= 0xFF;
argb &= 0xFFFF00FF;
argb |= (green << 8);
}
final int getBlue() {
return argb & 0xFF;
}
final void setBlue(int blue) {
blue &= 0xFF;
argb &= 0xFFFFFF00;
argb |= blue;
}
final int getARGB() {
return argb;
}
final void setARGB(int argb) {
this.argb = argb;
r = getRed();
g = getGreen();
b = getBlue();
ri = r / ColorLookUpTable.r2;
gi = g / ColorLookUpTable.r2;
bi = b / ColorLookUpTable.r2;
}
final void set(HistColor c) {
this.argb = c.argb;
}
final long longARGB() {
long a = getAlpha() * 257;
long r = getRed() * 257;
long g = getGreen() * 257;
long b = getBlue() * 257;
return a << 48 | r << 32 | g << 16 | b;
}
final void setARGB(long argb) {
int a = (int) ((argb >> 48 & 0xFFFF) / 257);
int r = (int) ((argb >> 32 & 0xFFFF) / 257);
int g = (int) ((argb >> 16 & 0xFFFF) / 257);
int b = (int) ((argb & 0xFFFF) / 257);
this.argb = a << 24 | r << 16 | g << 8 | b;
}
final int getAlpha() {
return (argb >> 24) & 0xFF;
}
final void setAlpha(int alpha) {
alpha &= 0xFF;
argb &= 0x00FFFFFF;
argb |= (alpha << 24);
}
@Override
protected HistColor clone() {
try {
HistColor rc = (HistColor) super.clone();
rc.numPixels = 0;
return rc;
} catch (CloneNotSupportedException e) {
throw new RuntimeException("accidental not cloned");
}
}
void premultiply() {
int a = getAlpha();
if (a != 0xFF) {
int r = getRed() * a / 255;
int g = getGreen() * a / 255;
int b = getBlue() * a / 255;
if (a != 0) {
a = 255;
}
argb = a << 24 | r << 16 | g << 8 | b;
}
}
float greyValue() {
float rc = (int) (getRed() * RED_SCALE + getGreen() * GREEN_SCALE + getBlue()
* BLUE_SCALE);
rc /= 255.0f;
if (rc < 0.0f) {
rc = 0.0f;
}
if (rc > 1.0f) {
rc = 1.0f;
}
return rc;
}
static long count;
int distanceSquared(HistColor hc) {
// int a = getAlpha();
// if (a == 0) {
// return ((hc.argb & 0xFF000000) != 0) ? Integer.MAX_VALUE : 0;
// }
count++;
int rd = getRed() - hc.getRed();
int gd = getGreen() - hc.getGreen();
int bd = getBlue() - hc.getBlue();
rd = rd * rd + gd * gd + bd * bd;
return rd;
}
@Override
public int compareTo(HistColor o) {
int b = numPixels;
int a = o.numPixels;
if (a > b)
return 1;
if (a < b)
return -1;
int c = r - o.r;
if (c != 0)
return c;
c = g - o.g;
if (c != 0)
return c;
return b - o.b;
}
/**
* @inheritDoc
*/
@Override
public String toString() {
return "Col [r=" + r + ", g=" + g + ", b=" + b + "] - [ri=" + ri
+ ", gi=" + gi + ", bi=" + bi + "]";
}
}
class ColorRect extends HistColor {
private Collection<HistColor> rects;
private int redMin, redMax, greenMin, greenMax, blueMin, blueMax;
ColorRect(int argb) {
super(argb);
blueMin = greenMin = redMin = 0xFF;
blueMax = greenMax = redMax = 0;
}
boolean isDividable() {
if (numPixels <= 1) {
return false;
}
int rRed = redMax - redMin;
int rGreen = greenMax - greenMin;
int rBlue = blueMax - blueMin;
if (rRed <= 1 && rGreen <= 1 && rBlue <= 1) {
return false;
}
return true;
}
ColorRect add(HistColor c) {
int a = getAlpha();
if (c.getAlpha() != a) {
throw new IllegalArgumentException("icompatible color rect");
}
numPixels += c.numPixels;
int r = c.getRed();
int g = c.getGreen();
int b = c.getBlue();
if (a != 0) {
redMin = Math.min(redMin, r);
greenMin = Math.min(greenMin, g);
blueMin = Math.min(blueMin, b);
redMax = Math.max(redMax, r);
greenMax = Math.max(greenMax, g);
blueMax = Math.max(blueMax, b);
r = (redMax + redMin) / 2;
g = (greenMax + greenMin) / 2;
b = (blueMax + blueMin) / 2;
setARGB(a << 24 | r << 16 | g << 8 | b);
}
if (rects == null) {
rects = new ArrayList<HistColor>();
}
rects.add(c);
return this;
}
ColorRect divide() {
int a = getAlpha();
if (a == 0) {
throw new IllegalArgumentException("icompatible color rect");
}
int r = getRed();
int g = getGreen();
int b = getBlue();
int rRed = redMax - redMin;
int rGreen = greenMax - greenMin;
int rBlue = blueMax - blueMin;
if ((rRed <= 1 && rGreen <= 1 && rBlue <= 1) || numPixels <= 1) {
throw new IllegalArgumentException("icompatible color rect");
}
ColorRect rc = clone();
if (rRed > rGreen && rRed > rBlue) {
rc.redMax = redMin = r;
rc.setRed((rc.redMin + rc.redMax) / 2);
setRed((redMin + redMax) / 2);
} else if (rGreen > rBlue) {
rc.greenMax = greenMin = g;
rc.setGreen((rc.greenMin + rc.greenMax) / 2);
setGreen((greenMin + greenMax) / 2);
} else {
rc.blueMax = blueMin = b;
rc.setBlue((rc.blueMin + rc.blueMax) / 2);
setBlue((blueMin + blueMax) / 2);
}
HistColor cr;
int j, k;
reset();
rc.reset();
Iterator<HistColor> it = rects.iterator();
while (it.hasNext()) {
cr = it.next();
j = distanceSquared(cr);
k = rc.distanceSquared(cr);
r = cr.getRed();
g = cr.getGreen();
b = cr.getBlue();
if (j > k) {
it.remove();
rc.numPixels += cr.numPixels;
rc.redMin = Math.min(rc.redMin, r);
rc.greenMin = Math.min(rc.greenMin, g);
rc.blueMin = Math.min(rc.blueMin, b);
rc.redMax = Math.max(rc.redMax, r);
rc.greenMax = Math.max(rc.greenMax, g);
rc.blueMax = Math.max(rc.blueMax, b);
if (rc.rects == null) {
rc.rects = new ArrayList<HistColor>();
}
rc.rects.add(cr);
} else {
numPixels += cr.numPixels;
redMin = Math.min(redMin, r);
greenMin = Math.min(greenMin, g);
blueMin = Math.min(blueMin, b);
redMax = Math.max(redMax, r);
greenMax = Math.max(greenMax, g);
blueMax = Math.max(blueMax, b);
}
}
return (rc.numPixels == 0) ? null : rc;
}
private void reset() {
redMin = greenMin = blueMin = 0xFF;
numPixels = redMax = greenMax = blueMax = 0;
}
@Override
protected ColorRect clone() {
ColorRect rc = (ColorRect) super.clone();
rc.rects = null;
return rc;
}
}
package dithering;
import java.awt.image.BufferedImage;
import java.lang.ref.Reference;
import java.lang.ref.WeakReference;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.WeakHashMap;
public enum ColorLookUpTable {
UNIFORM_SUBDIVISIONS, POPULARITY_CUT, MEDIAN_CUT, ;
private static final Map<BufferedImage, List<HistColor>[]> HIST_CACHE = new WeakHashMap<BufferedImage, List<HistColor>[]>();
private static final Map<BufferedImage, Map<Integer, Data>> MEDIAN_CACHE = new WeakHashMap<BufferedImage, Map<Integer, Data>>();
private static final Map<BufferedImage, Map<Integer, List<HistColor>>> POPULARITY_CACHE = new WeakHashMap<BufferedImage, Map<Integer, List<HistColor>>>();
/*
* private static final Comparator<HistColor> RED_COMPARATOR = new
* Comparator<HistColor>() {
*
* @Override public int compare(HistColor o1, HistColor o2) { int a =
* o1.red; int b = o2.red; return (a > b)? 1 : (a < b)? - 1 : 0; } };
* private static final Comparator<HistColor> GREEN_COMPARATOR = new
* Comparator<HistColor>() {
*
* @Override public int compare(HistColor o1, HistColor o2) { int a =
* o1.green; int b = o2.green; return (a > b)? 1 : (a < b)? - 1 : 0; } };
* private static final Comparator<HistColor> BLUE_COMPARATOR = new
* Comparator<HistColor>() {
*
* @Override public int compare(HistColor o1, HistColor o2) { int a =
* o1.blue; int b = o2.blue; return (a > b)? 1 : (a < b)? - 1 : 0; } }; //
*/
public static final int MIN_BITS = 1;
public static final int MAX_BITS = 16;
public ColorMatcher createMatcher() {
switch (this) {
case UNIFORM_SUBDIVISIONS:
return new UniformSubdivisions();
case POPULARITY_CUT:
return new PopulationCut();
default:
case MEDIAN_CUT:
return new MedianCut();
}
}
static class Data {
HistColor[] colorRects;
HistColor[][][][] room = new HistColor[ColorLookUpTable.r][ColorLookUpTable.r][ColorLookUpTable.r][];
}
public static abstract class ColorMatcher implements Cloneable {
static final int[][] rgbtable = { //
{ 0, 65535, 0 }, // 1/16=>1/2/1
{ 65535, 65535, 0 }, // 2/16=>2/2/1
{ 65535, 65535, 65535 }, // 3/32=>2/2/2
{ 65535, 32768, 65535 }, // 4/16=>2/3/2
{ 32768, 32768, 32768 }, // 5/32=>3/3/3
{ 21845, 21845, 32768 }, // 6/64=>4/4/3
{ 16384, 16384, 16384 }, // 7/128=>5/5/5
{ 13107, 10923, 13107 }, // 8/256=>6/7/6
{ 9363, 9363, 10923 }, // 9/512=>8/8/7
{ 7282, 7282, 7282 }, // 10/1024=>10/10/10
{ 5958, 5462, 5958 }, // 11/2048=>12/13/12
{ 4369, 4369, 4682 }, // 12/4096=>16/16/15
{ 3450, 3450, 3450 }, // 13/8192=>20/20/20
{ 2731, 2622, 2731 }, // 14/16384=>25/26/25
{ 2115, 2115, 2185 }, // 15/32768=>32/32/31
{ 1681, 1681, 1681 }, // 16/65536=>40/40/40
};
static int[] MASKS = { 0xFFFFFFFF, 0xFFFEFEFE, 0xFFFCFCFC, 0xFFF8F8F8,
0xFFF0F0F0, 0xFFE0E0E0, 0xFFC0C0C0, 0xFF808080, };
private int bitSize;
private transient WeakReference<BufferedImage> wrv;
boolean justMask;
int sourceColors;
protected ColorMatcher() {
}
public final int getBitSize() {
return bitSize;
}
public final void setSource(BufferedImage source) {
if (wrv != null && wrv.get() == source) {
return;
}
wrv = new WeakReference<BufferedImage>(source);
if (bitSize != 0) {
getHistory(bitSize, source);
sourceColors = HIST_CACHE.get(source)[0].size();
justMask = (1 << bitSize) >= sourceColors;
}
}
final Reference<BufferedImage> getSourceReference() {
return wrv;
}
@Override
public ColorMatcher clone() {
try {
return (ColorMatcher) super.clone();
} catch (CloneNotSupportedException e) {
throw new RuntimeException("accidental not cloned");
}
}
public final BufferedImage getSource() {
if (wrv == null) {
return null;
}
return wrv.get();
}
public final void setBitSize(int bitSize) {
if (bitSize < MIN_BITS || bitSize > MAX_BITS) {
throw new IllegalArgumentException("invalid bitsize " + bitSize);
}
this.bitSize = bitSize;
BufferedImage source = getSource();
if (source != null) {
getHistory(bitSize, source);
sourceColors = HIST_CACHE.get(source)[0].size();
justMask = (1 << bitSize) >= sourceColors;
}
}
public final void match(HistColor c) {
if (bitSize == 1) {
c.setARGB((c.greyValue() < 0.5) ? 0xFF000000 : 0xFFFFFFFF);
return;
}
if (justMask) {
return;
}
matchIntern(c);
}
public final boolean justMask() {
return justMask;
}
public int getSourceColors() {
return sourceColors;
}
public final double getProgress() {
return (justMask) ? 1.0 : progress();
}
protected abstract double progress();
protected abstract void matchIntern(HistColor c);
static List<HistColor> getHistory(int bits, BufferedImage v) {
if (v == null) {
throw new NullPointerException();
}
if (bits < MIN_BITS || bits > MAX_BITS) {
throw new IllegalArgumentException("invalid number of bits");
}
synchronized (HIST_CACHE) {
List<HistColor>[] tmpHist = HIST_CACHE.get(v);
if (tmpHist == null) {
@SuppressWarnings("unchecked")
List<HistColor>[] t = new List[MASKS.length];
tmpHist = t;
HIST_CACHE.put(v, tmpHist);
}
int mask = MASKS[0];
int i;
int numCols = (1 << bits);
List<HistColor> rc = tmpHist[0];
if (rc == null) {
Map<Integer, HistColor> tmp = new TreeMap<Integer, HistColor>();
HistColor c = new HistColor(0xFF000000);
int width = v.getWidth(null);
int height = v.getHeight(null);
for (int y = 0; y < height; y++) {
for (int x = 0; x < width; x++) {
c.setARGB(v.getRGB(x, y));
c.premultiply();
i = c.getARGB();
i = (i & mask);
HistColor hc = tmp.get(i);
if (hc == null) {
hc = new HistColor(i);
tmp.put(i, hc);
}
hc.numPixels++;
}
}
rc = new ArrayList<HistColor>(tmp.values());
Collections.sort(rc);
rc = Collections.unmodifiableList(rc);
tmpHist[0] = rc;
for (int n = 1; n < MASKS.length; n++) {
tmp.clear();
mask = MASKS[n];
for (HistColor hc2 : tmpHist[n - 1]) {
i = hc2.getARGB();
i = (i & mask);
HistColor hc = tmp.get(i);
if (hc == null) {
hc = new HistColor(i);
tmp.put(i, hc);
}
hc.numPixels += hc2.numPixels;
}
rc = new ArrayList<HistColor>(tmp.values());
Collections.sort(rc);
rc = Collections.unmodifiableList(rc);
tmpHist[n] = rc;
}
rc = tmpHist[0];
}
for (List<HistColor> l : tmpHist) {
if (numCols > l.size()) {
break;
}
rc = l;
}
return rc;
}
}
}
private static class UniformSubdivisions extends ColorMatcher {
private int rDiv, gDiv, bDiv, bits;
private UniformSubdivisions() {
}
@Override
protected void matchIntern(HistColor c) {
int bits = getBitSize();
if (bits != this.bits) {
int[] d = rgbtable[bits - MIN_BITS];
rDiv = d[0];
gDiv = d[1];
bDiv = d[2];
this.bits = bits;
}
long argb = c.longARGB();
long alpha = argb & 0xFFFF000000000000L;
if (alpha == 0L && bits >= 4) {
c.setARGB(0);
return;
}
long red = 0, green = 0, blue = 0;
if (rDiv > 0) {
red = (int) (argb >> 32) & 0xFFFF;
red = getModulo(red, rDiv);
red <<= 32;
}
if (gDiv > 0) {
green = (int) (argb >> 16) & 0xFFFF;
green = getModulo(green, gDiv);
green <<= 16;
}
if (bDiv > 0) {
blue = (int) argb & 0xFFFF;
blue = getModulo(blue, bDiv);
}
argb = alpha | red | green | blue;
c.setARGB(argb);
}
@Override
public double progress() {
return 1.0;
}
private static long getModulo(long component, int cdiv) {
if (cdiv > 0) {
long i = (component / cdiv) * cdiv;
long j = ((component + cdiv) / cdiv) * cdiv;
j = Math.min(j, 65535);
component = (component - i < j - component) ? i : j;
}
return component;
}
}
private static class PopulationCut extends ColorMatcher {
private double numColors;
private int count;
private PopulationCut() {
}
@Override
public double progress() {
return count / numColors;
}
@Override
protected void matchIntern(final HistColor c) {
int bits = getBitSize();
BufferedImage v = getSource();
if (bits == 0 || v == null) {
return;
}
Map<Integer, List<HistColor>> tmp = POPULARITY_CACHE.get(v);
if (tmp == null) {
tmp = new TreeMap<Integer, List<HistColor>>();
POPULARITY_CACHE.put(v, tmp);
}
numColors = (1 << bits) - 1;
List<HistColor> colorRects = tmp.get(bits);
if (colorRects == null) {
count = 0;
colorRects = new ArrayList<HistColor>((int) numColors + 1);
List<HistColor> rects = getHistory(bits, v);
HistColor alpha = null;
for (HistColor cr : rects) {
if (cr.getAlpha() == 0 && alpha == null) {
alpha = cr;
} else if (count < numColors) {
colorRects.add(cr);
count++;
}
}
colorRects.add((alpha == null) ? rects.get(count) : alpha);
tmp.put(bits, colorRects);
}
count = (int) numColors + 1;
int argb = c.getARGB();
if ((argb & 0xFF000000) == 0) {
c.setARGB(0);
return;
}
/*
* if(numColors > 1000) { int red = ((argb >> 16) & 0xFF); int green
* = ((argb >> 8) & 0xFF); int blue = (argb & 0xFF); if(red > green
* && red > blue) { Collections.sort(colorRects, RED_COMPARATOR); }
* else if(green > blue) { Collections.sort(colorRects,
* GREEN_COMPARATOR); } else { Collections.sort(colorRects,
* BLUE_COMPARATOR); } } //
*/
int argb2 = argb;
int currentError = 0;
int minError = Integer.MAX_VALUE;
for (HistColor cr3 : colorRects) {
currentError = cr3.distanceSquared(c);
if (minError > currentError) {
minError = currentError;
argb2 = cr3.getARGB();
}
if (currentError == 0) {
break;
}
}
c.setARGB(argb2);
}
}
private static class MedianCut extends ColorMatcher {
private double numColors;
private int count;
private MedianCut() {
}
@Override
public double progress() {
return count / numColors;
}
@Override
protected synchronized void matchIntern(final HistColor c) {
int bits = getBitSize();
BufferedImage v = getSource();
if (bits == 0 || v == null) {
return;
}
Map<Integer, Data> tmp = MEDIAN_CACHE.get(v);
if (tmp == null) {
tmp = new TreeMap<Integer, Data>();
MEDIAN_CACHE.put(v, tmp);
}
numColors = (1 << bits);
Data data = tmp.get(bits);
if (data == null) {
System.out.println(System.currentTimeMillis()
+ " vor generateLUT");
List<HistColor> colorRects = generateLUT(
getHistory(MAX_BITS, v), (int) numColors);
data = new Data();
data.colorRects = colorRects.toArray(new HistColor[0]);
Arrays.sort(data.colorRects);
tmp.put(bits, data);
for (int i = 0; i < ColorLookUpTable.r; i++)
for (int j = 0; j < ColorLookUpTable.r; j++)
for (int k = 0; k < ColorLookUpTable.r; k++) {
Set<HistColor> cand = new HashSet<HistColor>();
// debug = i== 4 && j == 5 && k== 5;
addCandidates((i + 0.5) * ColorLookUpTable.r2,
(j + 0.5) * ColorLookUpTable.r2, (k + 0.5)
* ColorLookUpTable.r2, cand,
data.colorRects);
HistColor[] candA = cand.toArray(new HistColor[cand
.size()]);
Arrays.sort(candA);
data.room**[j][k] = candA;
}
System.out.println(System.currentTimeMillis()
+ " generateLUT fertig, " + colorRects.size() + ", "
+ HistColor.count + ", rad: " + ColorLookUpTable.radius);
}
count = (int) numColors;
// search(c, data.colorRects);
search(c, data.room[c.ri][c.gi][c.bi]);
}
static int countC;
static void search(HistColor c, HistColor[] pal) {
int argb = c.getARGB();
if ((argb & 0xFF000000) == 0) {
c.setARGB(0);
return;
}
int argb2 = argb;
int currentError = 0;
int minError = Integer.MAX_VALUE;
for (HistColor cr3 : pal) {
currentError = cr3.distanceSquared(c);
if (minError > currentError) {
minError = currentError;
argb2 = cr3.getARGB();
}
if (currentError == 0) {
break;
}
}
c.setARGB(argb2);
}
static void addCandidates(double r, double g, double b,
Set<HistColor> cand, HistColor[] pal) {
HistColor mid = new HistColor((int) r, (int) g, (int) b);
int smallestError = Integer.MAX_VALUE;
int maxError = Integer.MAX_VALUE;
for (HistColor color2 : pal) {
int currentError = mid.distanceSquared(color2);
if (smallestError > currentError) {
smallestError = currentError;
maxError = smallestError + ColorLookUpTable.radius;
}
if (currentError < maxError) {
cand.add(color2);
}
}
Iterator<HistColor> iter = cand.iterator();
while (iter.hasNext()) {
HistColor next = iter.next();
int currentError = mid.distanceSquared(next);
if (currentError > maxError) {
iter.remove();
}
}
}
private List<HistColor> generateLUT(List<HistColor> lhc, int numColors) {
count = 0;
ColorRect all = new ColorRect(0xFF000000);
ColorRect alpha = null;
for (HistColor cr : lhc) {
if (cr.getAlpha() == 0) {
if (alpha == null) {
alpha = new ColorRect(0);
numColors--;
}
alpha.add(cr);
} else {
all.add(cr);
}
}
List<ColorRect> lhc1 = new ArrayList<ColorRect>();
lhc1.add(all);
count = lhc1.size();
int index = 0;
ColorRect add;
while (count < numColors && index < count) {
all = lhc1.get(index);
if (!all.isDividable()) {
index++;
continue;
}
add = all.divide();
if (add != null) {
lhc1.add(add);
Collections.sort(lhc1);
}
count = lhc1.size();
}
if (alpha != null) {
lhc1.add(alpha);
}
lhc = new ArrayList<HistColor>();
for (ColorRect cr : lhc1) {
lhc.add(new HistColor(cr.getARGB()));
}
return lhc;
}
}
static final int r = 32;
static final int r2 = 256 / r;
static final int radius = (int) (3 * r2 * 1.5 * r2 * 1.5);
}
[/spoiler]
Und „Entschuldige dich nicht immer für solche Kleinigkeiten“, sagt mein Kollege immer. Warum wohl? 
