use crate::encode_image::AlphaPlane;
use crate::encoding_context::EncodingContext;
use crate::function_fields::{self, FittedProfile, NestedProfile, ResidualFit};
use crate::image::Image3F;
use crate::thread_pool::ThreadPool;
const VIEW_SLACK: f64 = 1e-4;
fn depth(plane: &AlphaPlane) -> Option<(&[u16], u8, i32)> {
match plane {
AlphaPlane::U16 { data, bits } if (9..=16).contains(bits) => {
Some((data, *bits, (1i32 << *bits) - 1))
}
_ => None,
}
}
fn bias(max: i32) -> i32 {
(max + 1) / 2
}
pub(crate) fn fit(
pool: &ThreadPool,
plane: &AlphaPlane,
width: usize,
height: usize,
lossy: bool,
) -> Option<ResidualFit> {
let (data, bits, max) = depth(plane)?;
if width.checked_mul(height)? != data.len() {
return None;
}
let scale = max as u32;
let view = AlphaPlane::U8(
data.iter()
.map(|&value| ((u32::from(value) * 255 + scale / 2) / scale) as u8)
.collect(),
);
let (periodic, smooth) = pool.join(
|| function_fields::fit_periodic(&view, width, height),
|| {
lossy
.then(|| function_fields::fit_residual(pool, &view, width, height))
.flatten()
},
);
deepen(periodic.or(smooth)?, data, bits, max, width)
}
fn deepen(
coarse: ResidualFit,
data: &[u16],
bits: u8,
max: i32,
width: usize,
) -> Option<ResidualFit> {
let NestedProfile { profile, u, v } = coarse.base.model;
let length = profile.len();
let bias = bias(max);
let mut starts = vec![0usize; length + 1];
for (row, &vy) in data.chunks_exact(width).zip(&v) {
for &ux in &u[..row.len()] {
starts[(ux + vy) as usize + 1] += 1;
}
}
for i in 0..length {
starts[i + 1] += starts[i];
}
let mut grouped = vec![0u16; data.len()];
let mut next = starts.clone();
for (row, &vy) in data.chunks_exact(width).zip(&v) {
for (&value, &ux) in row.iter().zip(&u) {
let slot = &mut next[(ux + vy) as usize];
grouped[*slot] = value;
*slot += 1;
}
}
let mut deep = vec![0i32; length];
let mut previous: Option<(usize, i32)> = None;
for i in 0..length {
let group = &mut grouped[starts[i]..starts[i + 1]];
if group.is_empty() {
continue;
}
let middle = group.len() / 2;
let median = i32::from(*group.select_nth_unstable(middle).1);
let lo = i32::from(*group.iter().min()?);
let hi = i32::from(*group.iter().max()?);
let value = median.clamp(hi - (max - bias), lo + bias);
deep[i] = value;
match previous {
Some((start, from)) => {
for j in start + 1..i {
let span = (i - start) as i64;
deep[j] = from + (i64::from(value - from) * (j - start) as i64 / span) as i32;
}
}
None => deep[..i].fill(value),
}
previous = Some((i, value));
}
let (last, value) = previous?;
deep[last + 1..].fill(value);
drop(grouped);
let mut function = Vec::with_capacity(data.len());
let mut residual = Vec::with_capacity(data.len());
let (mut missed, mut error, mut max_error) = (0usize, 0u64, 0i32);
for (row, &vy) in data.chunks_exact(width).zip(&v) {
for (&value, &ux) in row.iter().zip(&u) {
let model = deep[(ux + vy) as usize];
let difference = i32::from(value) - model;
missed += usize::from(difference != 0);
error += u64::from(difference.unsigned_abs()).pow(2);
max_error = max_error.max(difference.abs());
function.push(model as u16);
residual.push((difference + bias) as u16);
}
}
if coarse.periodic && missed * 8 > data.len() {
return None;
}
for value in &mut deep {
*value -= bias;
}
Some(ResidualFit {
base: FittedProfile {
model: NestedProfile {
profile: deep,
u,
v,
},
reconstructed: AlphaPlane::U16 {
data: function,
bits,
},
squared_error: error,
max_error: max_error.min(255) as u8,
},
residual: AlphaPlane::U16 {
data: residual,
bits,
},
periodic: coarse.periodic,
})
}
pub(crate) fn dead_zone(fit: &ResidualFit, source: &AlphaPlane, zone: u8) -> AlphaPlane {
let (Some((source, _, max)), Some((residual, bits, _))) = (depth(source), depth(&fit.residual))
else {
return fit.residual.clone();
};
let bias = bias(max);
let threshold = ((i32::from(zone) * max + 127) / 255).unsigned_abs();
AlphaPlane::U16 {
data: residual
.iter()
.zip(source)
.map(|(&r, &s)| {
let keep = s == 0
|| i32::from(s) == max
|| (i32::from(r) - bias).unsigned_abs() > threshold;
if keep { r } else { bias as u16 }
})
.collect(),
bits,
}
}
pub(crate) fn compose(fit: &ResidualFit, residual: &AlphaPlane) -> Option<AlphaPlane> {
let (function, bits, max) = depth(&fit.base.reconstructed)?;
let (residual, residual_bits, _) = depth(residual)?;
if bits != residual_bits || function.len() != residual.len() {
return None;
}
let bias = bias(max);
Some(AlphaPlane::U16 {
data: function
.iter()
.zip(residual)
.map(|(&f, &r)| (i32::from(f) - bias + i32::from(r)).clamp(0, max) as u16)
.collect(),
bits,
})
}
struct Incumbent {
luma: Vec<f32>,
views: Vec<msssim_lite::PreparedReference>,
deficits: Vec<f64>,
squared_error: u64,
moved_endpoints: usize,
}
#[derive(Default)]
pub(crate) struct GateCache {
incumbent: std::sync::OnceLock<Option<Incumbent>>,
}
pub(crate) fn score(
ctx: &EncodingContext,
color: &Image3F,
source: &AlphaPlane,
incumbent: &AlphaPlane,
candidate: &AlphaPlane,
cache: &GateCache,
) -> Option<f64> {
let (source, bits, max) = depth(source)?;
let (incumbent, incumbent_bits, _) = depth(incumbent)?;
let (candidate, candidate_bits, _) = depth(candidate)?;
let (width, height) = (color.xsize(), color.ysize());
let pixels = width.checked_mul(height)?;
if bits != incumbent_bits
|| bits != candidate_bits
|| [source.len(), incumbent.len(), candidate.len()] != [pixels; 3]
{
return None;
}
if candidate == incumbent {
return Some(f64::INFINITY);
}
let errors = |plane: &[u16]| {
source
.iter()
.zip(plane)
.fold((0u64, 0usize), |(squared, moved), (&s, &v)| {
let endpoint = s == 0 || i32::from(s) == max;
(
squared + u64::from(s.abs_diff(v)).pow(2),
moved + usize::from(endpoint && s != v),
)
})
};
let (squared_error, moved_endpoints) = errors(candidate);
if squared_error == 0 {
return Some(0.0);
}
let unit = 1.0 / max as f32;
let view = |index: usize, plane: &[u16], luma: &[f32]| -> Vec<f32> {
let alpha = plane.iter().map(|&sample| f32::from(sample) * unit);
match index {
0 => alpha.collect(),
1 => alpha.zip(luma).map(|(alpha, &luma)| luma * alpha).collect(),
_ => alpha
.zip(luma)
.map(|(alpha, &luma)| luma * alpha + 1.0 - alpha)
.collect(),
}
};
let size = (width, height);
let reference = cache
.incumbent
.get_or_init(|| {
let luma = lightness(ctx, color);
let views = ctx
.thread_pool
.map(3, |index| {
let samples = view(index, source, &luma);
msssim_lite::PreparedReference::new(image(&samples, size).ok()?).ok()
})
.into_iter()
.collect::<Option<Vec<_>>>()?;
let deficits = ctx
.thread_pool
.map(3, |index| {
let samples = view(index, incumbent, &luma);
Some(
views[index]
.compare(image(&samples, size).ok()?)
.ok()?
.deficit(),
)
})
.into_iter()
.collect::<Option<Vec<f64>>>()?;
let (squared_error, moved_endpoints) = errors(incumbent);
Some(Incumbent {
luma,
views,
deficits,
squared_error,
moved_endpoints,
})
})
.as_ref()?;
if squared_error > reference.squared_error || moved_endpoints > reference.moved_endpoints {
return None;
}
let deficits = ctx
.thread_pool
.map(3, |index| {
let samples = view(index, candidate, &reference.luma);
let score = reference.views[index]
.compare(image(&samples, size).ok()?)
.ok()?;
Some(score.deficit()).filter(|deficit| deficit.is_finite())
})
.into_iter()
.collect::<Option<Vec<f64>>>()?;
let no_view_worse = deficits
.iter()
.zip(&reference.deficits)
.all(|(&new, &old)| new <= old + VIEW_SLACK);
let (pooled, old): (f64, f64) = (deficits.iter().sum(), reference.deficits.iter().sum());
(no_view_worse && pooled <= old * (1.0 + 1e-6) + 1e-9).then_some(pooled)
}
fn image(
samples: &[f32],
(width, height): (usize, usize),
) -> Result<msssim_lite::GrayImage<'_>, msssim_lite::Error> {
msssim_lite::GrayImage::unit_f32(samples, width, height, width)
}
fn lightness(ctx: &EncodingContext, color: &Image3F) -> Vec<f32> {
let mut peak = crate::xyb::rgb_to_xyb_pixel_f32(&ctx.xyb, 1.0, 1.0, 1.0).1;
let mut luma: Vec<_> = color
.plane_data(1)
.iter()
.map(|&value| {
let value = if value.is_finite() {
value.max(0.0)
} else {
0.0
};
peak = peak.max(value);
value
})
.collect();
if peak > 0.0 {
let scale = 1.0 / peak;
for value in &mut luma {
*value *= scale;
}
}
luma
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn lightness_clamps_samples_and_normalizes_in_raster_order() {
let ctx = EncodingContext::default();
let white = crate::xyb::rgb_to_xyb_pixel_f32(&ctx.xyb, 1.0, 1.0, 1.0).1;
let mut color = Image3F::new(3, 2);
color
.plane_row_mut(1, 0)
.copy_from_slice(&[-1.0, white * 0.5, f32::NAN]);
color.plane_row_mut(1, 1).copy_from_slice(&[
f32::INFINITY,
white * 0.25,
f32::NEG_INFINITY,
]);
let check = |color: &Image3F, expected: [f32; 6]| {
let values = lightness(&ctx, color);
assert_eq!(values.len(), expected.len());
for (value, expected) in values.into_iter().zip(expected) {
assert!((value - expected).abs() <= f32::EPSILON);
}
};
check(&color, [0.0, 0.5, 0.0, 0.0, 0.25, 0.0]);
color.plane_row_mut(1, 1)[1] = white * 2.0;
check(&color, [0.0, 0.25, 0.0, 0.0, 1.0, 0.0]);
}
fn glow(width: usize, height: usize, bits: u8) -> Vec<u16> {
let max = f64::from((1u32 << bits) - 1);
let mut state = 7u32;
(0..width * height)
.map(|i| {
let (x, y) = ((i % width) as f64, (i / width) as f64);
let (dx, dy) = (x - 0.5 * width as f64, y - 0.5 * height as f64);
let r = (dx * dx + dy * dy).sqrt() / width as f64;
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
if r < 0.15 {
0
} else {
let noise = f64::from(state % 5) - 2.0;
let value = max * (-((r - 0.15) / 0.2).powi(2)).exp() + noise * max / 4096.0;
value.round().clamp(0.0, max) as u16
}
})
.collect()
}
#[test]
fn deep_fit_reconstructs_every_sample_at_its_depth() {
let (width, height) = (320, 288);
let pool = ThreadPool::new(2);
for bits in [10u8, 12, 16] {
let data = glow(width, height, bits);
let plane = AlphaPlane::U16 {
data: data.clone(),
bits,
};
let fitted = fit(&pool, &plane, width, height, true).expect("deep fit");
let max = (1i32 << bits) - 1;
let (function, _, _) = depth(&fitted.base.reconstructed).unwrap();
let (residual, residual_bits, _) = depth(&fitted.residual).unwrap();
assert_eq!(residual_bits, bits);
let model = &fitted.base.model;
for (i, &value) in data.iter().enumerate() {
let s = (model.u[i % width] + model.v[i / width]) as usize;
assert_eq!(model.profile[s] + i32::from(residual[i]), i32::from(value));
assert_eq!(model.profile[s] + bias(max), i32::from(function[i]));
}
let composed = compose(&fitted, &fitted.residual).expect("composition");
assert_eq!(depth(&composed).unwrap().0, &data[..]);
let zoned = dead_zone(&fitted, &plane, 2);
let (zoned, _, _) = depth(&zoned).unwrap();
let threshold = (2 * max + 127) / 255;
for ((&z, &r), &s) in zoned.iter().zip(residual).zip(&data) {
let misfit = (i32::from(r) - bias(max)).abs();
if s == 0 || i32::from(s) == max || misfit > threshold {
assert_eq!(z, r);
} else {
assert_eq!(i32::from(z), bias(max));
}
}
}
}
#[test]
fn deep_fit_declines_other_planes() {
let pool = ThreadPool::new(1);
assert!(fit(&pool, &AlphaPlane::U8(vec![0; 64 * 64]), 64, 64, true).is_none());
let mut state = 1u32;
let noise = AlphaPlane::U16 {
data: (0..96 * 96)
.map(|_| {
state ^= state << 13;
state ^= state >> 17;
state ^= state << 5;
(state & 1023) as u16
})
.collect(),
bits: 10,
};
assert!(fit(&pool, &noise, 96, 96, true).is_none());
let short = AlphaPlane::U16 {
data: vec![0; 10],
bits: 16,
};
assert!(fit(&pool, &short, 64, 64, true).is_none());
}
}