856f865cf98d
quantize.rs
//! Colour reduction for Image › Mode › Indexed Color and Bitmap: palette construction (exact,
//! system, web, uniform, perceptual, selective, adaptive), forced colours, and dithering
//! (none, Floyd–Steinberg diffusion, ordered pattern, noise), plus 1-bit conversion methods.
//!
//! Buffers are straight RGBA in 0..=1, row-major. Median cut follows Heckbert (1982); k-means
//! refinement is Lloyd's algorithm; error diffusion is Floyd & Steinberg (1976).
use photocraft_color::convert::srgb_to_lab;
use serde::{Deserialize, Serialize};
mod nearest;
use nearest::Nearest;
pub type Rgb8 = [u8; 3];
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub enum PaletteKind {
/// Every colour of the image (fails above 256).
Exact,
SystemMac,
SystemWindows,
Web,
Uniform,
/// Lab median cut + k-means (perceptually weighted).
Perceptual,
/// Perceptual, with entries near web-safe colours snapped to them.
Selective,
/// RGB median cut weighted by frequency.
Adaptive,
}
impl PaletteKind {
pub fn from_id(s: &str) -> Option<Self> {
Some(match s {
"exact" => PaletteKind::Exact,
"system" | "systemMac" | "systemMacOs" => PaletteKind::SystemMac,
"systemWindows" => PaletteKind::SystemWindows,
"web" => PaletteKind::Web,
"uniform" => PaletteKind::Uniform,
"perceptual" | "localPerceptual" => PaletteKind::Perceptual,
"selective" | "localSelective" => PaletteKind::Selective,
"adaptive" | "localAdaptive" => PaletteKind::Adaptive,
_ => return None,
})
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub enum Forced {
None,
BlackWhite,
Primaries,
Web,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub enum Dither {
None,
Diffusion,
Pattern,
Noise,
}
/// `(v.clamp(0, 1) * 255).round() as u8`, without the libm `roundf` call per channel (that call
/// was about a tenth of the palette scan on a large image). `x` is in 0..=255, so truncating
/// with an integer cast and adding one when the exact remainder is at least a half is
/// round-half-away-from-zero, the same as `f32::round`; NaN gives 0 in both. The
/// `to8_matches_round_for_every_float` test checks every input.
fn to8(v: f32) -> u8 {
let x = v.clamp(0.0, 1.0) * 255.0;
let t = x as u32;
(t + u32::from(x - t as f32 >= 0.5)) as u8
}
fn rgb8(p: &[f32; 4]) -> Rgb8 {
[to8(p[0]), to8(p[1]), to8(p[2])]
}
/// The 216-colour web-safe cube (0, 51, …, 255 per channel).
pub fn web_palette() -> Vec<Rgb8> {
let mut v = Vec::with_capacity(216);
for r in 0..6u8 {
for g in 0..6u8 {
for b in 0..6u8 {
v.push([r * 51, g * 51, b * 51]);
}
}
}
v
}
/// Classic Mac OS system palette: the web cube plus 10-step red, green, blue and gray ramps.
pub fn mac_palette() -> Vec<Rgb8> {
let mut v = web_palette();
// Ramps use the values between cube steps (17-unit spacing, skipping multiples of 51).
let steps: Vec<u8> = (1..=15u8).map(|k| k * 17).filter(|x| x % 51 != 0).collect();
for &s in steps.iter().rev() {
v.push([s, 0, 0]);
}
for &s in steps.iter().rev() {
v.push([0, s, 0]);
}
for &s in steps.iter().rev() {
v.push([0, 0, s]);
}
for &s in steps.iter().rev() {
v.push([s, s, s]);
}
v.truncate(256);
v
}
/// Windows default palette: the 20 static system colours plus the web cube and a gray ramp.
pub fn windows_palette() -> Vec<Rgb8> {
let mut v: Vec<Rgb8> = vec![
[0, 0, 0],
[128, 0, 0],
[0, 128, 0],
[128, 128, 0],
[0, 0, 128],
[128, 0, 128],
[0, 128, 128],
[192, 192, 192],
[192, 220, 192],
[166, 202, 240],
[255, 251, 240],
[160, 160, 164],
[128, 128, 128],
[255, 0, 0],
[0, 255, 0],
[255, 255, 0],
[0, 0, 255],
[255, 0, 255],
[0, 255, 255],
[255, 255, 255],
];
for c in web_palette() {
if !v.contains(&c) {
v.push(c);
}
}
let mut g = 8u8;
while v.len() < 256 {
if !v.contains(&[g, g, g]) {
v.push([g, g, g]);
}
g = g.wrapping_add(12);
}
v
}
/// Up to `n` colours on an equal-step RGB grid.
pub fn uniform_palette(n: usize) -> Vec<Rgb8> {
let k = ((n as f32).cbrt().floor() as usize).max(2);
let lv = |i: usize| ((i as f32 / (k - 1) as f32) * 255.0).round() as u8;
let mut v = Vec::with_capacity(k * k * k);
for r in 0..k {
for g in 0..k {
for b in 0..k {
v.push([lv(r), lv(g), lv(b)]);
}
}
}
v
}
fn forced_colors(f: Forced) -> Vec<Rgb8> {
match f {
Forced::None => Vec::new(),
Forced::BlackWhite => vec![[0, 0, 0], [255, 255, 255]],
Forced::Primaries => vec![[0, 0, 0], [255, 255, 255], [255, 0, 0], [0, 255, 0], [0, 0, 255], [0, 255, 255], [255, 0, 255], [255, 255, 0]],
Forced::Web => web_palette(),
}
}
/// Unique 8-bit colours with counts (opaque pixels only), sorted by colour.
fn histogram(px: &[[f32; 4]]) -> Vec<(Rgb8, u32)> {
// Pack each opaque pixel into one u32 (r, g, b from the top, so the numeric order is the
// `[u8; 3]` order), sort the plain integers and count the runs. This replaces a SipHash
// `HashMap` insert per pixel: counts are integers, so any order of work gives the same
// result, and equal colours sit next to each other after the sort. One 4-byte value per
// pixel is the only large allocation (no per-thread tables).
let pack = |p: &[f32; 4]| {
let [r, g, b] = rgb8(p);
u32::from(r) << 16 | u32::from(g) << 8 | u32::from(b)
};
#[cfg(not(target_arch = "wasm32"))]
let keys = {
use rayon::prelude::*;
let mut keys: Vec<u32> = px.par_iter().filter(|p| p[3] >= 0.5).map(pack).collect();
keys.par_sort_unstable();
keys
};
#[cfg(target_arch = "wasm32")]
let keys = {
let mut keys: Vec<u32> = px.iter().filter(|p| p[3] >= 0.5).map(pack).collect();
keys.sort_unstable();
keys
};
let mut out: Vec<(Rgb8, u32)> = Vec::new();
for k in keys {
let c = [(k >> 16) as u8, (k >> 8) as u8, k as u8];
match out.last_mut() {
Some((last, n)) if *last == c => *n = n.saturating_add(1),
_ => out.push((c, 1)),
}
}
out
}
/// Widest axis of `b` and its split score (weighted extent), or `None` for a box that cannot
/// be split. Every score is bit for bit what the old per-iteration scan gave.
fn split_score(b: &[([f32; 3], u32)]) -> Option<(usize, f32)> {
if b.len() <= 1 {
return None;
}
// One pass per axis, then the weight sum: the same folds the old per-iteration scan ran
// (measured faster than a single fused pass, which the compiler does not vectorise).
let mut best = (0usize, -1.0f32);
for a in 0..3 {
let (lo, hi) = b.iter().fold((f32::MAX, f32::MIN), |(lo, hi), p| (lo.min(p.0[a]), hi.max(p.0[a])));
if hi - lo > best.1 {
best = (a, hi - lo);
}
}
let w: f32 = b.iter().map(|p| p.1 as f32).sum();
Some((best.0, best.1 * w.sqrt()))
}
/// Maps an f32 to a u32 whose unsigned order is exactly `f32::total_cmp` order.
fn total_order_key(v: f32) -> u32 {
let bits = v.to_bits();
// Negative: flip every bit (reverses their order, puts them below). Positive: set the sign bit.
bits ^ ((((bits as i32) >> 31) as u32) | 0x8000_0000)
}
/// Stable LSD radix sort of `b` along `axis`, in the order of `f32::total_cmp`. Stable like
/// `sort_by`, so ties keep their original order and the result is element for element the same;
/// it is several times faster than a comparison sort on millions of points.
fn radix_sort_along(b: &mut Vec<([f32; 3], u32)>, axis: usize) {
let n = b.len();
let Some(&fill) = b.first() else { return };
if n < 2 {
return;
}
// Three digits of 11, 11 and 10 bits; count all of them in one read.
let mut counts = [[0u32; 2048]; 3];
for e in b.iter() {
let k = total_order_key(e.0[axis]);
counts[0][(k & 0x7ff) as usize] += 1;
counts[1][((k >> 11) & 0x7ff) as usize] += 1;
counts[2][(k >> 22) as usize] += 1;
}
let mut src = std::mem::take(b);
let mut dst = vec![fill; n];
for (pass, count) in counts.iter_mut().enumerate() {
// A digit that is the same for every point would not move anything.
if count.iter().any(|&c| c as usize == n) {
continue;
}
let mut sum = 0u32;
for c in count.iter_mut() {
let here = *c;
*c = sum;
sum += here;
}
let shift = 11 * pass as u32;
for e in &src {
let d = ((total_order_key(e.0[axis]) >> shift) & 0x7ff) as usize;
dst[count[d] as usize] = *e;
count[d] += 1;
}
std::mem::swap(&mut src, &mut dst);
}
*b = src;
}
/// Stable sort of `b` along `axis`. Boxes this small are quicker with `sort_by` than with the
/// radix sort's fixed counting cost.
fn sort_along(b: &mut Vec<([f32; 3], u32)>, axis: usize) {
if b.len() >= 256 {
radix_sort_along(b, axis);
} else {
b.sort_by(|p, q| p.0[axis].total_cmp(&q.0[axis]));
}
}
/// Median cut over `pts` (feature vectors + weights) into at most `n` boxes; returns box means.
fn median_cut(pts: &[([f32; 3], u32)], n: usize) -> Vec<[f32; 3]> {
if pts.is_empty() || n == 0 {
return Vec::new();
}
let mut boxes: Vec<Vec<([f32; 3], u32)>> = vec![pts.to_vec()];
// Each box's (axis, score), kept in lockstep with `boxes` (same swap_remove and pushes).
// Only the two boxes made by a split change, so only those are scanned again; rescanning
// every box on every iteration was most of the time here.
let mut scores: Vec<Option<(usize, f32)>> = vec![split_score(pts)];
while boxes.len() < n {
// Split the box with the largest weighted extent (first one wins a tie, as before).
let (bi, axis, score) = scores
.iter()
.enumerate()
.filter_map(|(i, s)| s.map(|(axis, score)| (i, axis, score)))
.fold((usize::MAX, 0, -1.0f32), |acc, x| if x.2 > acc.2 { x } else { acc });
if bi == usize::MAX || score <= 0.0 {
break;
}
let mut b = boxes.swap_remove(bi);
scores.swap_remove(bi);
sort_along(&mut b, axis);
let total: u64 = b.iter().map(|p| u64::from(p.1)).sum();
let mut acc = 0u64;
let mut cut = 1;
for (i, p) in b.iter().enumerate() {
acc += u64::from(p.1);
if acc * 2 >= total {
cut = (i + 1).clamp(1, b.len() - 1);
break;
}
}
let rest = b.split_off(cut);
scores.push(split_score(&b));
scores.push(split_score(&rest));
boxes.push(b);
boxes.push(rest);
}
boxes
.iter()
.map(|b| {
let w: f64 = b.iter().map(|p| f64::from(p.1)).sum();
std::array::from_fn(|a| (b.iter().map(|p| f64::from(p.0[a]) * f64::from(p.1)).sum::<f64>() / w) as f32)
})
.collect()
}
/// Lloyd refinement of `centers` over weighted points.
fn kmeans(pts: &[([f32; 3], u32)], centers: &mut [[f32; 3]], iters: usize) {
if centers.is_empty() {
// No room left (the forced colours fill the palette): nothing to refine.
return;
}
for _ in 0..iters {
let lookup = Nearest::new(centers.iter().copied());
let mut sum = vec![[0.0f64; 3]; centers.len()];
let mut cnt = vec![0.0f64; centers.len()];
// The nearest-centre search is the expensive part and has no cross-point state, so it
// runs in parallel. The f64 sums below stay sequential in the original point order:
// float addition is not associative, and this keeps every bit of the result unchanged.
#[cfg(not(target_arch = "wasm32"))]
let nearest: Vec<u32> = {
use rayon::prelude::*;
pts.par_iter().map(|(p, _)| lookup.find(*p) as u32).collect()
};
#[cfg(target_arch = "wasm32")]
let nearest: Vec<u32> = pts.iter().map(|(p, _)| lookup.find(*p) as u32).collect();
for ((p, w), &i) in pts.iter().zip(&nearest) {
let i = i as usize;
for a in 0..3 {
sum[i][a] += f64::from(p[a]) * f64::from(*w);
}
cnt[i] += f64::from(*w);
}
for (i, c) in centers.iter_mut().enumerate() {
if cnt[i] > 0.0 {
*c = std::array::from_fn(|a| (sum[i][a] / cnt[i]) as f32);
}
}
}
}
fn lab_to_rgb8(lab: [f32; 3]) -> Rgb8 {
photocraft_color::convert::lab_to_srgb(lab).map(to8)
}
/// Histogram colours as CIE Lab points with their counts. Each point depends only on its own
/// colour and `collect` keeps the order, so the parallel map gives the same list; the log/pow
/// in `srgb_to_lab` made this a visible serial cost with millions of unique colours.
fn lab_points(hist: &[(Rgb8, u32)]) -> Vec<([f32; 3], u32)> {
let lab = |(c, n): &(Rgb8, u32)| (srgb_to_lab(c.map(|v| f32::from(v) / 255.0)), *n);
#[cfg(not(target_arch = "wasm32"))]
{
use rayon::prelude::*;
hist.par_iter().map(lab).collect()
}
#[cfg(target_arch = "wasm32")]
hist.iter().map(lab).collect()
}
/// Builds the palette for `px`. `colors` is the requested count (2..=256) for the computed
/// kinds; forced colours are included first and count toward it.
pub fn build_palette(px: &[[f32; 4]], kind: PaletteKind, colors: usize, forced: Forced) -> Result<Vec<Rgb8>, String> {
let colors = colors.clamp(2, 256);
let mut pal = forced_colors(forced);
let room = colors.saturating_sub(pal.len());
// Fixed palettes, or computed palettes already filled by forced colours, need no scan.
// Exact still counts every colour to enforce its 256-colour limit.
let hist = if kind == PaletteKind::Exact || (room > 0 && matches!(kind, PaletteKind::Adaptive | PaletteKind::Perceptual | PaletteKind::Selective)) {
histogram(px)
} else {
Vec::new()
};
let computed: Vec<Rgb8> = match kind {
PaletteKind::Exact => {
if hist.len() > 256 {
return Err(format!("the image has {} colours; Exact needs 256 or fewer", hist.len()));
}
hist.iter().map(|h| h.0).collect()
}
PaletteKind::SystemMac => mac_palette(),
PaletteKind::SystemWindows => windows_palette(),
PaletteKind::Web => web_palette(),
PaletteKind::Uniform => uniform_palette(room.max(8)),
PaletteKind::Adaptive => {
if hist.len() <= room {
hist.iter().map(|h| h.0).collect()
} else {
let pts: Vec<([f32; 3], u32)> = hist.iter().map(|(c, n)| (c.map(f32::from), *n)).collect();
let mut centers = median_cut(&pts, room);
kmeans(&pts, &mut centers, 2);
centers.iter().map(|c| c.map(|v| v.round().clamp(0.0, 255.0) as u8)).collect()
}
}
PaletteKind::Perceptual | PaletteKind::Selective => {
if hist.len() <= room {
hist.iter().map(|h| h.0).collect()
} else {
let pts = lab_points(&hist);
let mut centers = median_cut(&pts, room);
kmeans(&pts, &mut centers, 4);
let mut v: Vec<Rgb8> = centers.iter().map(|c| lab_to_rgb8(*c)).collect();
if kind == PaletteKind::Selective {
// Favour web-safe colours: snap entries within ~10 levels of one.
for c in &mut v {
let snap = c.map(|x| ((f32::from(x) / 51.0).round() * 51.0) as u8);
if c.iter().zip(snap).all(|(a, b)| a.abs_diff(b) <= 10) {
*c = snap;
}
}
}
v
}
}
};
for c in computed {
if pal.len() >= 256 {
break;
}
if !pal.contains(&c) {
pal.push(c);
}
}
if matches!(kind, PaletteKind::Adaptive | PaletteKind::Perceptual | PaletteKind::Selective | PaletteKind::Uniform) {
pal.truncate(colors.max(forced_colors(forced).len()));
}
if pal.is_empty() {
pal.push([0, 0, 0]);
}
Ok(pal)
}
/// 8×8 Bayer threshold in -0.5..0.5.
pub fn bayer8(x: usize, y: usize) -> f32 {
const M: [u8; 64] = [
0, 32, 8, 40, 2, 34, 10, 42, 48, 16, 56, 24, 50, 18, 58, 26, 12, 44, 4, 36, 14, 46, 6, 38, 60, 28, 52, 20, 62, 30, 54, 22, 3, 35, 11, 43, 1, 33, 9, 41,
51, 19, 59, 27, 49, 17, 57, 25, 15, 47, 7, 39, 13, 45, 5, 37, 63, 31, 55, 23, 61, 29, 53, 21,
];
(f32::from(M[(y % 8) * 8 + x % 8]) + 0.5) / 64.0 - 0.5
}
fn hash01(x: usize, y: usize, seed: u32) -> f32 {
let mut h = (x as u32).wrapping_mul(0x8da6_b343) ^ (y as u32).wrapping_mul(0xd816_3841) ^ seed.wrapping_mul(0xcb1a_b31f);
h ^= h >> 13;
h = h.wrapping_mul(0x5bd1_e995);
h ^= h >> 15;
(h & 0xffff) as f32 / 65535.0
}
/// Maps every opaque pixel to its palette entry (in place) with the chosen dither; returns the
/// index per pixel. Pixels with alpha < ½ become index `transparent` (and alpha 0) when given;
/// otherwise alpha is kept. `amount` (0..=1) scales diffusion / pattern / noise strength.
pub fn quantize(px: &mut [[f32; 4]], w: usize, pal: &[Rgb8], dither: Dither, amount: f32, transparent: Option<usize>) -> Vec<u8> {
let lookup = Nearest::new(pal.iter().map(|c| c.map(f32::from)));
quantize_with(px, w, pal, dither, amount, transparent, |c| lookup.find(c.map(|v| v * 255.0)))
}
fn quantize_with(
px: &mut [[f32; 4]],
w: usize,
pal: &[Rgb8],
dither: Dither,
amount: f32,
transparent: Option<usize>,
nearest: impl Fn([f32; 3]) -> usize + Sync,
) -> Vec<u8> {
let h = px.len().checked_div(w).unwrap_or(0);
let mut idx = vec![0u8; px.len()];
// Typical palette spacing sets the ordered/noise dither amplitude.
let spread = (1.0 / (pal.len() as f32).cbrt().max(1.0)).min(0.5) * amount.clamp(0.0, 1.0);
// None / Pattern / Noise dither have no cross-pixel dependency: map every pixel in parallel.
// (Diffusion propagates error between pixels, so it stays serial below.)
if dither != Dither::Diffusion {
crate::photo_util::par_rows2(&mut idx, px, w, |y, idxrow, pxrow| {
for (x, (ip, p)) in idxrow.iter_mut().zip(pxrow.iter_mut()).enumerate() {
let pv = *p;
if pv[3] < 0.5 {
if let Some(t) = transparent {
*ip = t as u8;
*p = [0.0, 0.0, 0.0, 0.0];
continue;
}
if pv[3] <= 0.0 {
continue;
}
}
let mut c = [pv[0], pv[1], pv[2]];
match dither {
Dither::Pattern => c = c.map(|v| v + bayer8(x, y) * spread),
Dither::Noise => c = c.map(|v| v + (hash01(x, y, 7) - 0.5) * spread),
_ => {}
}
let c = c.map(|v| v.clamp(0.0, 1.0));
let k = nearest(c);
*ip = k as u8;
let e = pal[k].map(|v| f32::from(v) / 255.0);
*p = [e[0], e[1], e[2], if transparent.is_some() { 1.0 } else { pv[3] }];
}
});
return idx;
}
let mut err = vec![[0.0f32; 3]; 2 * (w + 2)];
for y in 0..h {
if dither == Dither::Diffusion {
// Rows ping-pong: `cur` is row y, `next` row y + 1 (offset by one for x = -1).
let (cur, next) = err.split_at_mut(w + 2);
cur.copy_from_slice(next);
next.iter_mut().for_each(|e| *e = [0.0; 3]);
}
for x in 0..w {
let i = y * w + x;
let p = px[i];
if p[3] < 0.5 {
if let Some(t) = transparent {
idx[i] = t as u8;
px[i] = [0.0, 0.0, 0.0, 0.0];
continue;
}
if p[3] <= 0.0 {
continue;
}
}
let mut c = [p[0], p[1], p[2]];
match dither {
Dither::None => {}
Dither::Diffusion => {
for k in 0..3 {
c[k] += err[x + 1][k];
}
}
Dither::Pattern => {
let t = bayer8(x, y) * spread;
c = c.map(|v| v + t);
}
Dither::Noise => {
let t = (hash01(x, y, 7) - 0.5) * spread;
c = c.map(|v| v + t);
}
}
let c = c.map(|v| v.clamp(0.0, 1.0));
let k = nearest(c);
idx[i] = k as u8;
let e = pal[k].map(|v| f32::from(v) / 255.0);
if dither == Dither::Diffusion {
let a = amount.clamp(0.0, 1.0);
let d: [f32; 3] = std::array::from_fn(|q| (c[q] - e[q]) * a);
let (cur, next) = err.split_at_mut(w + 2);
for q in 0..3 {
cur[x + 2][q] += d[q] * 7.0 / 16.0;
next[x][q] += d[q] * 3.0 / 16.0;
next[x + 1][q] += d[q] * 5.0 / 16.0;
next[x + 2][q] += d[q] / 16.0;
}
}
px[i] = [e[0], e[1], e[2], if transparent.is_some() { 1.0 } else { p[3] }];
}
}
idx
}
/// Image › Mode › Bitmap methods.
#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
pub enum BitmapMethod {
Threshold,
Pattern,
Diffusion,
/// Halftone screen: lines per pixel-cell size, angle in degrees, dot shape.
Halftone {
cell: f32,
angle: f32,
shape: HalftoneShape,
},
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub enum HalftoneShape {
Round,
Ellipse,
Line,
Square,
Diamond,
Cross,
}
impl HalftoneShape {
pub fn from_id(s: &str) -> Option<Self> {
Some(match s {
"round" => HalftoneShape::Round,
"ellipse" => HalftoneShape::Ellipse,
"line" => HalftoneShape::Line,
"square" => HalftoneShape::Square,
"diamond" => HalftoneShape::Diamond,
"cross" => HalftoneShape::Cross,
_ => return None,
})
}
}
/// Spot function in 0..=1 for a position (u, v) in -1..1 within a halftone cell.
fn spot(shape: HalftoneShape, u: f32, v: f32) -> f32 {
let s = match shape {
HalftoneShape::Round => 1.0 - (u * u + v * v) / 2.0,
HalftoneShape::Ellipse => 1.0 - (u * u + 0.6 * v * v) / 1.6,
HalftoneShape::Line => 1.0 - v.abs(),
HalftoneShape::Square => 1.0 - u.abs().max(v.abs()),
HalftoneShape::Diamond => 1.0 - (u.abs() + v.abs()) / 2.0,
HalftoneShape::Cross => 1.0 - u.abs().min(v.abs()),
};
s.clamp(0.0, 1.0)
}
/// Converts gray values (0..=1, row-major `w` wide) to 0/1 in place.
pub fn to_bitmap(gray: &mut [f32], w: usize, method: BitmapMethod) {
BitmapStrips::new(w, method).convert(gray);
}
/// Image › Mode › Bitmap fed in strips of whole rows, top to bottom, so a huge image never needs a
/// full-size gray plane (#8477): [`BitmapStrips::convert`] turns each strip to 0/1 in place,
/// carrying error diffusion's error into the next strip. The result is the same however the image
/// is cut into strips.
pub struct BitmapStrips<'a> {
w: usize,
kind: StripKind<'a>,
/// Image row of the next strip's first row.
y: usize,
}
enum StripKind<'a> {
Threshold,
Pattern,
/// Floyd–Steinberg: the error each pixel of the last converted row passes down.
Diffusion {
errs: Vec<f32>,
},
/// The spot function's values over a cell, sorted (its CDF ranks coverage by tone).
Halftone {
cell: f32,
sin: f32,
cos: f32,
shape: HalftoneShape,
table: Vec<f32>,
},
/// Custom Pattern's threshold map, `mw` x `mh`, tiled from the top-left corner.
Custom {
map: &'a [f32],
mw: usize,
mh: usize,
},
}
impl<'a> BitmapStrips<'a> {
pub fn new(w: usize, method: BitmapMethod) -> Self {
let kind = match method {
BitmapMethod::Threshold => StripKind::Threshold,
BitmapMethod::Pattern => StripKind::Pattern,
BitmapMethod::Diffusion => StripKind::Diffusion { errs: Vec::new() },
BitmapMethod::Halftone { cell, angle, shape } => {
let (sin, cos) = angle.to_radians().sin_cos();
// Rank the spot function over the cell so coverage is proportional to the tone.
let mut table: Vec<f32> =
(0..32 * 32).map(|k| spot(shape, ((k % 32) as f32 + 0.5) / 16.0 - 1.0, ((k / 32) as f32 + 0.5) / 16.0 - 1.0)).collect();
table.sort_by(f32::total_cmp);
StripKind::Halftone { cell: cell.max(2.0), sin, cos, shape, table }
}
};
Self { w, kind, y: 0 }
}
/// Bitmap's Custom Pattern: each gray value turns white where it reaches the threshold `map`
/// (`mw` x `mh`, from [`custom_pattern_thresholds`]) tiled from the image's top-left corner,
/// black elsewhere. A map that doesn't fit `mw` x `mh` thresholds at 50%.
pub fn custom(w: usize, map: &'a [f32], mw: usize, mh: usize) -> Self {
let fits = mw > 0 && mh > 0 && mw.checked_mul(mh) == Some(map.len());
let kind = if fits { StripKind::Custom { map, mw, mh } } else { StripKind::Threshold };
Self { w, kind, y: 0 }
}
/// Converts the next rows (gray 0..=1, `w` wide; a short last row is allowed) to 0/1 in place.
pub fn convert(&mut self, gray: &mut [f32]) {
let (w, y0) = (self.w, self.y);
if w == 0 {
// No rows to lay a pattern or diffuse along: a 50% threshold.
gray.iter_mut().for_each(|v| *v = if *v >= 0.5 { 1.0 } else { 0.0 });
return;
}
self.y = y0.saturating_add(gray.len().div_ceil(w));
// Every method but diffusion is pointwise: rows convert in parallel.
let par = gray.len() >= 1 << 16;
match &mut self.kind {
StripKind::Threshold => crate::par::chunks_mut(gray, w, par, |_, row| {
row.iter_mut().for_each(|v| *v = if *v >= 0.5 { 1.0 } else { 0.0 });
}),
StripKind::Pattern => crate::par::chunks_mut(gray, w, par, |r, row| {
for (x, v) in row.iter_mut().enumerate() {
*v = if *v > bayer8(x, y0 + r) + 0.5 { 1.0 } else { 0.0 };
}
}),
StripKind::Diffusion { errs } => {
// The previous strip's last row passes its error down to this strip's first.
let first = w.min(gray.len());
pass_down(errs, gray.get_mut(..first).unwrap_or_default());
let mut rest = gray;
while !rest.is_empty() {
let n = w.min(rest.len());
let (row, tail) = std::mem::take(&mut rest).split_at_mut(n);
diffuse_row(row, errs);
let below = w.min(tail.len());
pass_down(errs, tail.get_mut(..below).unwrap_or_default());
rest = tail;
}
}
StripKind::Halftone { cell, sin, cos, shape, table } => {
let (cell, s, c, shape, table) = (*cell, *sin, *cos, *shape, &*table);
let cdf = |x: f32| table.partition_point(|t| *t < x) as f32 / table.len() as f32;
crate::par::chunks_mut(gray, w, par, |r, row| {
let y = (y0 + r) as f32 + 0.5;
for (x, v) in row.iter_mut().enumerate() {
let x = x as f32 + 0.5;
let (rx, ry) = (x * c + y * s, -x * s + y * c);
let u = (rx / cell).rem_euclid(1.0) * 2.0 - 1.0;
let vv = (ry / cell).rem_euclid(1.0) * 2.0 - 1.0;
// Ink (black) covers where the spot function exceeds the gray level.
*v = if cdf(spot(shape, u, vv)) >= *v { 0.0 } else { 1.0 };
}
});
}
StripKind::Custom { map, mw, mh } => {
let (map, mw, mh) = (&**map, *mw, *mh);
crate::par::chunks_mut(gray, w, par, |r, row| {
let base = (y0 + r) % mh * mw;
for (x, v) in row.iter_mut().enumerate() {
let t = map.get(base + x % mw).copied().unwrap_or(0.5);
*v = if *v >= t { 1.0 } else { 0.0 };
}
});
}
}
}
}
/// One Floyd–Steinberg row, in place: each pixel takes its error from the left (7/16), and
/// `errs` gets the error it passes down to the next row ([`pass_down`]).
fn diffuse_row(row: &mut [f32], errs: &mut Vec<f32>) {
errs.clear();
for x in 0..row.len() {
let old = row[x];
let new = if old >= 0.5 { 1.0 } else { 0.0 };
let e = old - new;
row[x] = new;
if let Some(next) = row.get_mut(x + 1) {
*next += e * 7.0 / 16.0;
}
errs.push(e);
}
}
/// Adds the error `errs` of a row to the row below: 1/16 from the pixel up-left, 5/16 from the
/// one above, 3/16 from the one up-right, in that order (the order the row's pixels were
/// converted in), so the result is the same whether or not the rows are in the same strip.
fn pass_down(errs: &[f32], below: &mut [f32]) {
for (t, v) in below.iter_mut().enumerate() {
if let Some(e) = t.checked_sub(1).and_then(|l| errs.get(l)) {
*v += e / 16.0;
}
if let Some(e) = errs.get(t) {
*v += e * 5.0 / 16.0;
}
if let Some(e) = errs.get(t + 1) {
*v += e * 3.0 / 16.0;
}
}
}
/// The threshold map of Bitmap's Custom Pattern from a pattern's lightness (0..=1, row-major):
/// pattern pixels ranked by lightness, ties sharing their average rank, the lightest pixel
/// thresholding lowest (it turns white first). A map of `n` pixels thus spreads `n` evenly
/// spaced levels `(k + 0.5) / n`, whatever the pattern's own contrast, as Photoshop's does
/// (measured: a 2x2 pattern of 32/96/160/224, a 3x1 of 50/128/200 and a 7x1 ramp all give
/// exactly those levels).
/// Reject oversized workspace or allocation failure rather than aborting the process.
pub fn custom_pattern_thresholds(lightness: &[f32]) -> Result<Vec<f32>, photocraft_raster::AllocationError> {
let n = lightness.len();
let bytes = custom_pattern_working_bytes(n)?;
let key = |i: usize| lightness.get(i).copied().filter(|v| v.is_finite()).unwrap_or(0.0);
let allocation = || photocraft_raster::AllocationError::NotEnoughMemory { bytes };
let mut order = Vec::new();
order.try_reserve_exact(n).map_err(|_| allocation())?;
order.extend((0..n).map(|i| i as u32));
// Ties receive the same mean rank, so stability is unnecessary. This sort
// uses no heap scratch; fixed-width indices also bound web/desktop equally.
order.sort_unstable_by(|a, b| key(*a as usize).total_cmp(&key(*b as usize)));
let mut out = Vec::new();
out.try_reserve_exact(n).map_err(|_| allocation())?;
out.resize(n, 0.5);
let mut start = 0;
while start < n {
let v = order.get(start).map(|i| key(*i as usize));
let end = (start..n).find(|&j| order.get(j).map(|i| key(*i as usize)) != v).unwrap_or(n);
// Ranks start..end share their mean.
let rank = (start + end - 1) as f32 / 2.0;
let t = 1.0 - (rank + 0.5) / n as f32;
for i in order.get(start..end).unwrap_or_default() {
if let Some(o) = out.get_mut(*i as usize) {
*o = t;
}
}
start = end;
}
Ok(out)
}
/// Admit input lightness, fixed-width order and output thresholds before reading any pattern pixels.
pub fn custom_pattern_working_bytes(count: usize) -> Result<usize, photocraft_raster::AllocationError> {
let bytes = count.checked_mul(12).ok_or(photocraft_raster::AllocationError::SizeOverflow)?;
if bytes > 256 << 20 {
return Err(photocraft_raster::AllocationError::SizeOverflow);
}
Ok(bytes)
}
/// Bitmap's Custom Pattern over a whole image (gray 0..=1, row-major `w` wide), see
/// [`BitmapStrips::custom`]. An image `w` of 0 thresholds at 50%.
pub fn to_bitmap_custom(gray: &mut [f32], w: usize, map: &[f32], mw: usize, mh: usize) {
BitmapStrips::custom(w, map, mw, mh).convert(gray);
}
#[cfg(test)]
mod tests;
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.