use ::rlx::ir::ops::vq::VqMetric;
use ::rlx::{DType, Device, Graph, Shape};
use crate::math::Color;
use super::session::GraphRunner;
use super::tensor::{ColorSpace, Tensor, TensorError};
#[derive(Debug, Clone, PartialEq)]
pub struct Palette {
pub colors: Vec<Color>,
space: ColorSpace,
}
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct PaletteOptions {
pub iterations: usize,
pub samples: usize,
pub color_space: ColorSpace,
}
impl Default for PaletteOptions {
fn default() -> Self {
Self {
iterations: 12,
samples: 20_000,
color_space: ColorSpace::Srgb,
}
}
}
impl Default for Palette {
fn default() -> Self {
Self {
colors: Vec::new(),
space: ColorSpace::Srgb,
}
}
}
impl Palette {
pub fn new(colors: Vec<Color>) -> Self {
Self {
colors,
space: ColorSpace::Srgb,
}
}
pub fn len(&self) -> usize {
self.colors.len()
}
pub fn is_empty(&self) -> bool {
self.colors.is_empty()
}
pub fn extract(
rgba: &[u8],
count: usize,
options: &PaletteOptions,
device: Device,
) -> Result<Self, TensorError> {
let count = count.max(1);
let samples = sample_pixels(rgba, options.samples, options.color_space);
let n = samples.dims()[0];
if n == 0 {
return Ok(Self {
colors: Vec::new(),
space: options.color_space,
});
}
let mut centroids = seed_centroids(&samples, count);
let mut runner = assignment_runner(n, centroids.len() / 3, device);
for _ in 0..options.iterations {
runner.set_param("codebook", ¢roids);
let assignment = runner.run(&[("pixels", &samples)]).remove(0).into_data();
let (next, moved) = update(&samples, &assignment, ¢roids);
centroids = next;
if !moved {
break;
}
}
runner.set_param("codebook", ¢roids);
let assignment = runner.run(&[("pixels", &samples)]).remove(0).into_data();
let mut used: Vec<bool> = vec![false; centroids.len() / 3];
for a in &assignment {
let i = *a as usize;
if i < used.len() {
used[i] = true;
}
}
let colors = centroids
.as_chunks::<3>()
.0
.iter()
.zip(used)
.filter(|(_, used)| *used)
.map(|(c, _)| Self::to_linear([c[0], c[1], c[2]], options.color_space))
.collect();
Ok(Self {
colors,
space: options.color_space,
})
}
pub fn assign(&self, rgba: &[u8], device: Device) -> Result<Vec<u32>, TensorError> {
if self.colors.is_empty() || rgba.len() < 4 {
return Ok(vec![0; rgba.len() / 4]);
}
let pixels = all_pixels(rgba, self.space);
let n = pixels.dims()[0];
let mut runner = assignment_runner(n, self.colors.len(), device);
runner.set_param("codebook", &self.codebook());
let assignment = runner.run(&[("pixels", &pixels)]).remove(0);
Ok(assignment.data().iter().map(|a| *a as u32).collect())
}
pub fn posterize(&self, rgba: &[u8], device: Device) -> Result<Vec<u8>, TensorError> {
let assignment = self.assign(rgba, device)?;
let mut out = Vec::with_capacity(rgba.len());
for (px, index) in rgba.as_chunks::<4>().0.iter().zip(assignment) {
let c = self
.colors
.get(index as usize)
.copied()
.unwrap_or(Color::BLACK);
let encoded = Self::from_linear(c, self.space);
for v in encoded {
out.push((v.clamp(0.0, 1.0) * 255.0 + 0.5) as u8);
}
out.push(px[3]);
}
Ok(out)
}
pub fn nearest(&self, color: Color) -> Option<usize> {
let target = Self::from_linear(color, self.space);
self.colors
.iter()
.enumerate()
.map(|(i, c)| {
let c = Self::from_linear(*c, self.space);
let d: f32 = (0..3).map(|k| (c[k] - target[k]).powi(2)).sum();
(i, d)
})
.min_by(|a, b| a.1.total_cmp(&b.1))
.map(|(i, _)| i)
}
fn codebook(&self) -> Vec<f32> {
self.colors
.iter()
.flat_map(|c| Self::from_linear(*c, self.space))
.collect()
}
fn to_linear(rgb: [f32; 3], space: ColorSpace) -> Color {
match space {
ColorSpace::Linear => Color::new(rgb[0], rgb[1], rgb[2]),
ColorSpace::Srgb => Color::new(
super::srgb_to_linear(rgb[0]),
super::srgb_to_linear(rgb[1]),
super::srgb_to_linear(rgb[2]),
),
}
}
fn from_linear(color: Color, space: ColorSpace) -> [f32; 3] {
match space {
ColorSpace::Linear => [color.r, color.g, color.b],
ColorSpace::Srgb => [
super::linear_to_srgb(color.r),
super::linear_to_srgb(color.g),
super::linear_to_srgb(color.b),
],
}
}
}
fn assignment_runner(pixels: usize, codes: usize, device: Device) -> GraphRunner {
let mut g = Graph::new("assign");
let x = g.input("pixels", Shape::new(&[pixels, 3], DType::F32));
let codebook = g.param("codebook", Shape::new(&[codes, 3], DType::F32));
let (indices, _quantized) = g.vector_quantize(x, codebook, VqMetric::L2);
g.set_outputs(vec![indices]);
GraphRunner::new(g, device)
}
fn all_pixels(rgba: &[u8], space: ColorSpace) -> Tensor {
let linear = matches!(space, ColorSpace::Linear);
let mut data = Vec::with_capacity(rgba.len() / 4 * 3);
for px in rgba.as_chunks::<4>().0 {
for &channel in &px[..3] {
let v = channel as f32 / 255.0;
data.push(if linear { super::srgb_to_linear(v) } else { v });
}
}
let n = data.len() / 3;
Tensor::new(data, &[n, 3]).expect("three per pixel")
}
fn sample_pixels(rgba: &[u8], wanted: usize, space: ColorSpace) -> Tensor {
let pixels = rgba.len() / 4;
if pixels == 0 {
return Tensor::new(Vec::new(), &[0, 3]).expect("empty");
}
let wanted = wanted.clamp(1, pixels);
let stride = (pixels / wanted).max(1);
let linear = matches!(space, ColorSpace::Linear);
let mut data = Vec::with_capacity(wanted * 3);
for p in (0..pixels).step_by(stride) {
for c in 0..3 {
let v = rgba[p * 4 + c] as f32 / 255.0;
data.push(if linear { super::srgb_to_linear(v) } else { v });
}
}
let n = data.len() / 3;
Tensor::new(data, &[n, 3]).expect("three per pixel")
}
fn seed_centroids(samples: &Tensor, count: usize) -> Vec<f32> {
let data = samples.data();
let n = samples.dims()[0];
let count = count.min(n.max(1));
if n == 0 {
return Vec::new();
}
let mut out = Vec::with_capacity(count * 3);
out.extend_from_slice(&data[0..3]);
let mut nearest: Vec<f32> = (0..n)
.map(|p| {
(0..3)
.map(|j| (data[p * 3 + j] - out[j]).powi(2))
.sum::<f32>()
})
.collect();
for _ in 1..count {
let (best, spread) =
nearest
.iter()
.enumerate()
.fold(
(0usize, -1.0f32),
|(bi, bd), (i, d)| {
if *d > bd {
(i, *d)
} else {
(bi, bd)
}
},
);
if spread <= 0.0 {
break;
}
let base = out.len();
out.extend_from_slice(&data[best * 3..best * 3 + 3]);
for (p, near) in nearest.iter_mut().enumerate() {
let d: f32 = (0..3)
.map(|j| (data[p * 3 + j] - out[base + j]).powi(2))
.sum();
*near = near.min(d);
}
}
out
}
fn update(samples: &Tensor, assignment: &[f32], centroids: &[f32]) -> (Vec<f32>, bool) {
let k = centroids.len() / 3;
let data = samples.data();
let n = data.len() / 3;
let mut sums = vec![0.0f32; k * 3];
let mut counts = vec![0u32; k];
for (p, a) in assignment.iter().enumerate().take(n) {
let c = (*a as usize).min(k.saturating_sub(1));
counts[c] += 1;
for j in 0..3 {
sums[c * 3 + j] += data[p * 3 + j];
}
}
let mut next = centroids.to_vec();
let mut moved = false;
for c in 0..k {
if counts[c] == 0 {
continue;
}
for j in 0..3 {
let mean = sums[c * 3 + j] / counts[c] as f32;
if (mean - next[c * 3 + j]).abs() > 1e-4 {
moved = true;
}
next[c * 3 + j] = mean;
}
}
let empty: Vec<usize> = (0..k).filter(|c| counts[*c] == 0).collect();
if !empty.is_empty() {
let mut worst: Vec<(f32, usize)> = (0..n)
.map(|p| {
let c = (assignment[p] as usize).min(k.saturating_sub(1));
let d: f32 = (0..3)
.map(|j| (data[p * 3 + j] - next[c * 3 + j]).powi(2))
.sum();
(d, p)
})
.collect();
worst.sort_by(|a, b| b.0.total_cmp(&a.0));
for (slot, c) in empty.into_iter().enumerate() {
if let Some((_, p)) = worst.get(slot) {
next[c * 3..c * 3 + 3].copy_from_slice(&data[p * 3..p * 3 + 3]);
moved = true;
}
}
}
(next, moved)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::rlx::preferred_device;
fn frame_of(colors: &[[u8; 3]], per_color: usize) -> Vec<u8> {
let mut out = Vec::new();
for _ in 0..per_color {
for c in colors {
out.extend_from_slice(&[c[0], c[1], c[2], 255]);
}
}
out
}
#[test]
fn an_image_of_three_colours_yields_those_three_colours() {
let wanted = [[220u8, 30, 30], [30, 200, 60], [40, 60, 210]];
let frame = frame_of(&wanted, 300);
let palette =
Palette::extract(&frame, 3, &PaletteOptions::default(), preferred_device()).unwrap();
assert_eq!(palette.len(), 3);
for c in wanted {
let target = Color::new(
super::super::srgb_to_linear(c[0] as f32 / 255.0),
super::super::srgb_to_linear(c[1] as f32 / 255.0),
super::super::srgb_to_linear(c[2] as f32 / 255.0),
);
let nearest = palette.nearest(target).unwrap();
let found = Palette::from_linear(palette.colors[nearest], palette.space);
for j in 0..3 {
let want = c[j] as f32 / 255.0;
assert!(
(found[j] - want).abs() < 0.02,
"channel {j}: found {}, wanted {want}",
found[j]
);
}
}
}
#[test]
fn asking_for_more_colours_than_exist_gives_the_ones_that_do() {
let frame = frame_of(&[[255, 255, 255], [0, 0, 0]], 200);
let palette =
Palette::extract(&frame, 8, &PaletteOptions::default(), preferred_device()).unwrap();
assert!(
palette.len() <= 2,
"expected at most 2 entries, got {}",
palette.len()
);
}
#[test]
fn posterizing_snaps_every_pixel_onto_the_palette() {
let wanted = [[220u8, 30, 30], [30, 200, 60]];
let frame = frame_of(&wanted, 200);
let device = preferred_device();
let palette = Palette::extract(&frame, 2, &PaletteOptions::default(), device).unwrap();
let posterized = palette.posterize(&frame, device).unwrap();
let swatches: Vec<[u8; 3]> = palette
.colors
.iter()
.map(|c| {
let e = Palette::from_linear(*c, palette.space);
[
(e[0] * 255.0 + 0.5) as u8,
(e[1] * 255.0 + 0.5) as u8,
(e[2] * 255.0 + 0.5) as u8,
]
})
.collect();
for px in posterized.as_chunks::<4>().0 {
assert!(
swatches.iter().any(|s| s
.iter()
.zip(px)
.all(|(a, b)| (*a as i32 - *b as i32).abs() <= 1)),
"pixel {:?} is not a palette entry ({swatches:?})",
&px[..3]
);
assert_eq!(px[3], 255);
}
}
#[test]
fn zero_iterations_still_returns_the_seeded_colours() {
let frame = frame_of(&[[220u8, 30, 30], [30, 200, 60]], 200);
let palette = Palette::extract(
&frame,
2,
&PaletteOptions {
iterations: 0,
..Default::default()
},
preferred_device(),
)
.unwrap();
assert_eq!(palette.len(), 2, "seeded colours were reported unused");
}
#[test]
fn an_empty_frame_assigns_and_posterizes_to_nothing() {
let device = preferred_device();
let palette = Palette::new(vec![Color::WHITE, Color::BLACK]);
assert!(palette.assign(&[], device).unwrap().is_empty());
assert!(palette.posterize(&[], device).unwrap().is_empty());
}
#[test]
fn an_empty_frame_gives_an_empty_palette() {
let palette =
Palette::extract(&[], 4, &PaletteOptions::default(), preferred_device()).unwrap();
assert!(palette.is_empty());
assert_eq!(palette.nearest(Color::WHITE), None);
}
}