Something went wrong. Try again.
Monorepo for PackTools - tooling for Minecraft Modpacks!
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232//! A deterministic palette quantizer: median cut, then a few k-means rounds, then remapping with//! optional Floyd–Steinberg dithering. Every step walks colors in sorted order, so the palette//! never depends on hashing or threads.//!//! Colors are compared premultiplied, as (r·a, g·a, b·a, a) on a 0–255 scale: the color under a//! transparent pixel is invisible, so transparent pixels cluster together whatever their RGB.
type Vector = [f64; 4];
fn vector(c: [u8; 4]) -> Vector { let a = f64::from(c[3]) / 255.0; [f64::from(c[0]) * a, f64::from(c[1]) * a, f64::from(c[2]) * a, f64::from(c[3])]}
fn color(v: Vector) -> [u8; 4] { let a = v[3].round().clamp(0.0, 255.0); if a == 0.0 { return [0, 0, 0, 0]; } let un = |c: f64| (c * 255.0 / a).round().clamp(0.0, 255.0) as u8; [un(v[0]), un(v[1]), un(v[2]), a as u8]}
fn distance(a: &Vector, b: &Vector) -> f64 { (0..4).map(|i| (a[i] - b[i]) * (a[i] - b[i])).sum()}
fn nearest(palette: &[Vector], v: &Vector) -> usize { let mut best = 0; let mut best_d = f64::INFINITY; for (i, p) in palette.iter().enumerate() { let d = distance(p, v); if d < best_d { best = i; best_d = d; } } best}
/// Unique colors with their counts, sorted by color.pub fn histogram(pixels: &[[u8; 4]]) -> Vec<([u8; 4], u64)> { let mut sorted = pixels.to_vec(); sorted.sort_unstable(); let mut out: Vec<([u8; 4], u64)> = Vec::new(); for c in sorted { match out.last_mut() { Some((last, n)) if *last == c => *n += 1, _ => out.push((c, 1)), } } out}
struct Box { colors: Vec<(Vector, u64)>,}
impl Box { fn mean(&self) -> Vector { let total: f64 = self.colors.iter().map(|c| c.1 as f64).sum(); let mut m = [0.0; 4]; for (v, n) in &self.colors { for i in 0..4 { m[i] += v[i] * *n as f64; } } m.map(|x| x / total) }
/// Weighted squared error per channel. fn variance(&self) -> Vector { let m = self.mean(); let mut var = [0.0; 4]; for (v, n) in &self.colors { for i in 0..4 { var[i] += (v[i] - m[i]) * (v[i] - m[i]) * *n as f64; } } var }
fn error(&self) -> f64 { self.variance().iter().sum() }
/// Splits along the channel with the most variance, at the weighted median. fn split(mut self) -> (Box, Box) { let var = self.variance(); let axis = (0..4).fold(0, |best, i| if var[i] > var[best] { i } else { best }); self.colors.sort_by(|a, b| { a.0[axis] .total_cmp(&b.0[axis]) .then_with(|| a.0.iter().map(|x| x.to_bits()).cmp(b.0.iter().map(|x| x.to_bits()))) }); let total: u64 = self.colors.iter().map(|c| c.1).sum(); let mut seen = 0; let mut cut = 1; for (i, c) in self.colors.iter().enumerate() { seen += c.1; if seen * 2 >= total { cut = (i + 1).clamp(1, self.colors.len() - 1); break; } } let rest = self.colors.split_off(cut); (self, Box { colors: rest }) }}
/// A palette of at most `size` colors for `pixels`, or `None` when the image already has that/// few (a lossless palette needs no quantizing).pub fn palette(pixels: &[[u8; 4]], size: usize) -> Option<Vec<[u8; 4]>> { let hist = histogram(pixels); if hist.len() <= size { return None; } let mut boxes = vec![Box { colors: hist.iter().map(|(c, n)| (vector(*c), *n)).collect() }]; while boxes.len() < size { let (index, err) = boxes .iter() .enumerate() .filter(|(_, b)| b.colors.len() > 1) .map(|(i, b)| (i, b.error())) .fold((usize::MAX, -1.0), |best, cur| if cur.1 > best.1 { cur } else { best }); if index == usize::MAX || err <= 0.0 { break; } let (a, b) = boxes.swap_remove(index).split(); boxes.push(a); boxes.push(b); } let mut centers: Vec<Vector> = boxes.iter().map(Box::mean).collect();
// k-means: reassign every unique color to its nearest center, recompute the centers. let points: Vec<(Vector, u64)> = hist.iter().map(|(c, n)| (vector(*c), *n)).collect(); for _ in 0..4 { let mut sums = vec![[0.0; 4]; centers.len()]; let mut counts = vec![0u64; centers.len()]; for (v, n) in &points { let k = nearest(¢ers, v); for i in 0..4 { sums[k][i] += v[i] * *n as f64; } counts[k] += n; } for k in 0..centers.len() { if counts[k] > 0 { centers[k] = sums[k].map(|s| s / counts[k] as f64); } } } let mut colors: Vec<[u8; 4]> = centers.into_iter().map(color).collect(); colors.sort_unstable(); colors.dedup(); Some(colors)}
/// `pixels` mapped onto `palette`. `dithering` in 0..=1 scales the Floyd–Steinberg error.pub fn remap(pixels: &[[u8; 4]], width: usize, palette: &[[u8; 4]], dithering: f64) -> Vec<[u8; 4]> { let vectors: Vec<Vector> = palette.iter().map(|c| vector(*c)).collect(); if dithering <= 0.0 { let hist = histogram(pixels); let mapped: Vec<[u8; 4]> = hist.iter().map(|(c, _)| palette[nearest(&vectors, &vector(*c))]).collect(); return pixels .iter() .map(|c| mapped[hist.binary_search_by(|(h, _)| h.cmp(c)).expect("every pixel is in the histogram")]) .collect(); } let height = pixels.len() / width; let mut work: Vec<Vector> = pixels.iter().map(|c| vector(*c)).collect(); let mut out = Vec::with_capacity(pixels.len()); for y in 0..height { for x in 0..width { let at = y * width + x; let v = work[at].map(|c| c.clamp(0.0, 255.0)); let k = nearest(&vectors, &v); out.push(palette[k]); let err: Vector = std::array::from_fn(|i| (v[i] - vectors[k][i]) * dithering); let mut spread = |dx: isize, dy: usize, w: f64| { let nx = x as isize + dx; if nx >= 0 && (nx as usize) < width && y + dy < height { let n = (y + dy) * width + nx as usize; for i in 0..4 { work[n][i] += err[i] * w; } } }; spread(1, 0, 7.0 / 16.0); spread(-1, 1, 3.0 / 16.0); spread(0, 1, 5.0 / 16.0); spread(1, 1, 1.0 / 16.0); } } out}
#[cfg(test)]mod tests { use super::*;
fn gradient() -> Vec<[u8; 4]> { (0..64 * 64).map(|i| [(i % 64 * 4) as u8, (i / 64 * 4) as u8, 128, 255]).collect() }
#[test] fn few_colors_need_no_palette() { assert_eq!(palette(&[[1, 2, 3, 255], [1, 2, 3, 255], [0, 0, 0, 0]], 16), None); }
#[test] fn palettes_fit_and_are_deterministic() { let px = gradient(); let p = palette(&px, 16).unwrap(); assert!(p.len() <= 16); assert_eq!(palette(&px, 16).unwrap(), p); let mapped = remap(&px, 64, &p, 0.0); assert!(mapped.iter().all(|c| p.contains(c))); let dithered = remap(&px, 64, &p, 1.0); assert!(dithered.iter().all(|c| p.contains(c))); assert_eq!(remap(&px, 64, &p, 1.0), dithered); }
#[test] fn transparent_pixels_cluster_together() { let mut px: Vec<[u8; 4]> = (0..200u32).map(|i| [i as u8, 0, 0, 0]).collect(); px.extend((0..200u32).map(|i| [0, i as u8, 255, 255])); let p = palette(&px, 4).unwrap(); assert!(p.contains(&[0, 0, 0, 0])); }}