665bfac0b339
matting.rs
//! Matte utilities: exact Euclidean distance transforms (Felzenszwalb & Huttenlocher,
//! "Distance Transforms of Sampled Functions", Theory of Computing 8, 2012), box and Gaussian
//! filters, the colour **guided filter** (K. He, J. Sun and X. Tang, "Guided Image Filtering",
//! ECCV 2010 / IEEE PAMI 2013) used for edge matting, foreground colour estimation
//! (decontamination, from the compositing equation I = αF + (1 − α)B with B and F estimated from
//! nearby pure background / foreground pixels), and the Refine Edge matte adjustments.
use rayon::prelude::*;
const BIG: f32 = 1e12;
/// 1-D squared distance transform of `f` (lower envelope of parabolas).
fn dt1(f: &[f32], d: &mut [f32], v: &mut [usize], z: &mut [f64]) {
let n = f.len();
if n == 0 {
return;
}
let ff = |q: usize| f[q] as f64 + (q * q) as f64;
let mut k = 0usize;
v[0] = 0;
z[0] = f64::NEG_INFINITY;
z[1] = f64::INFINITY;
for q in 1..n {
let mut s = (ff(q) - ff(v[k])) / (2.0 * (q as f64 - v[k] as f64));
while s <= z[k] {
if k == 0 {
break;
}
k -= 1;
s = (ff(q) - ff(v[k])) / (2.0 * (q as f64 - v[k] as f64));
}
k += 1;
v[k] = q;
z[k] = s;
z[k + 1] = f64::INFINITY;
}
k = 0;
for (q, dq) in d.iter_mut().enumerate().take(n) {
while z[k + 1] < q as f64 {
k += 1;
}
let p = v[k];
let dd = q as f64 - p as f64;
*dq = (dd * dd + f[p] as f64) as f32;
}
}
/// Scratch vectors (`f`, `v`, `z`) for `dt1` over a line of `n` samples; sized per pass so a
/// 1 x N image does not allocate N-sized buffers for each of its N one-pixel rows.
fn line_scratch(n: usize) -> (Vec<f32>, Vec<usize>, Vec<f64>) {
(vec![0.0; n], vec![0; n], vec![0.0; n + 1])
}
/// Euclidean distance from every pixel to the nearest pixel where `seed` is true (BIG.sqrt()
/// when there is none).
pub fn distance(seed: &[bool], w: usize, h: usize) -> Vec<f32> {
if w == 0 || h == 0 {
return vec![];
}
// dt1 needs its input intact while it writes the output, so each line goes through scratch
// (`f`, `v`, `z`) that rayon creates once per work split, not once per line. The column pass
// runs on a transposed copy so that every column is a contiguous chunk.
// Columns: `t[x * h + y]` is pixel (x, y).
let mut t = vec![0.0f32; w * h];
t.par_chunks_mut(h).enumerate().for_each_init(
|| line_scratch(h),
|(f, v, z), (x, col)| {
for (y, fv) in f.iter_mut().enumerate() {
*fv = if seed.get(y * w + x).copied().unwrap_or(false) { 0.0 } else { BIG };
}
dt1(f, col, v, z);
},
);
// Rows, then the square root.
let mut g = vec![0.0f32; w * h];
g.par_chunks_mut(w).enumerate().for_each_init(
|| line_scratch(w),
|(f, v, z), (y, row)| {
for (x, fv) in f.iter_mut().enumerate() {
*fv = t[x * h + y];
}
dt1(f, row, v, z);
for d in row.iter_mut() {
*d = d.sqrt();
}
},
);
g
}
/// Signed distance to a binary matte's edge: positive inside (distance to the nearest
/// background pixel centre, minus ½), negative outside.
pub fn signed_distance(m: &[u8], w: usize, h: usize) -> Vec<f32> {
let fg: Vec<bool> = m.iter().map(|v| *v != 0).collect();
let bg: Vec<bool> = m.iter().map(|v| *v == 0).collect();
let din = distance(&bg, w, h);
let dout = distance(&fg, w, h);
m.iter().enumerate().map(|(i, v)| if *v != 0 { din[i] - 0.5 } else { 0.5 - dout[i] }).collect()
}
/// Mean over the (2r+1)² window (clamped at the edges: averages only the pixels inside).
pub fn box_mean(src: &[f32], w: usize, h: usize, r: usize) -> Vec<f32> {
if w == 0 || h == 0 {
return vec![];
}
// Horizontal window sums per row.
let mut tmp = vec![0.0f64; w * h];
tmp.par_chunks_mut(w).enumerate().for_each(|(y, row)| {
let s = &src[y * w..y * w + w];
let mut acc = 0.0f64;
for x in 0..r.min(w) {
acc += s[x] as f64;
}
for (x, o) in row.iter_mut().enumerate() {
if x + r < w {
acc += s[x + r] as f64;
}
if x > r {
acc -= s[x - r - 1] as f64;
}
*o = acc;
}
});
// Vertical prefix sums (row by row, cache friendly), then window differences.
let mut pre = vec![0.0f64; w * (h + 1)];
for y in 0..h {
let (done, rest) = pre.split_at_mut((y + 1) * w);
let prev = &done[y * w..];
let cur = &mut rest[..w];
let t = &tmp[y * w..y * w + w];
for x in 0..w {
cur[x] = prev[x] + t[x];
}
}
let mut out = vec![0.0f32; w * h];
out.par_chunks_mut(w).enumerate().for_each(|(y, row)| {
let a = y.saturating_sub(r);
let b = (y + r + 1).min(h);
let cy = (b - a) as f64;
for (x, o) in row.iter_mut().enumerate() {
let cx = ((x + r + 1).min(w) - x.saturating_sub(r)) as f64;
*o = ((pre[b * w + x] - pre[a * w + x]) / (cx * cy)) as f32;
}
});
out
}
/// Box radius of [`gauss`]: three passes of it match the variance, 3·((2r+1)² − 1)/12 = σ².
/// `None` when the blur is a copy.
fn gauss_box(sigma: f64) -> Option<usize> {
(sigma >= 0.3).then(|| (((4.0 * sigma * sigma + 1.0).sqrt() - 1.0) / 2.0).round().max(1.0) as usize)
}
/// How far (pixels, per axis) [`gauss`] reaches: an output pixel depends only on the input
/// within this distance.
pub fn gauss_reach(sigma: f64) -> usize {
gauss_box(sigma).map_or(0, |r| 3 * r)
}
/// Approximate Gaussian blur (three box passes) with standard deviation `sigma` pixels.
pub fn gauss(src: &[f32], w: usize, h: usize, sigma: f64) -> Vec<f32> {
let Some(r) = gauss_box(sigma) else { return src.to_vec() };
let a = box_mean(src, w, h, r);
let b = box_mean(&a, w, h, r);
box_mean(&b, w, h, r)
}
fn inv3(m: [[f32; 3]; 3]) -> [[f32; 3]; 3] {
let d = m[0][0] * (m[1][1] * m[2][2] - m[1][2] * m[2][1]) - m[0][1] * (m[1][0] * m[2][2] - m[1][2] * m[2][0])
+ m[0][2] * (m[1][0] * m[2][1] - m[1][1] * m[2][0]);
let d = if d.abs() < 1e-20 { 1e-20 } else { d };
[
[(m[1][1] * m[2][2] - m[1][2] * m[2][1]) / d, (m[0][2] * m[2][1] - m[0][1] * m[2][2]) / d, (m[0][1] * m[1][2] - m[0][2] * m[1][1]) / d],
[(m[1][2] * m[2][0] - m[1][0] * m[2][2]) / d, (m[0][0] * m[2][2] - m[0][2] * m[2][0]) / d, (m[0][2] * m[1][0] - m[0][0] * m[1][2]) / d],
[(m[1][0] * m[2][1] - m[1][1] * m[2][0]) / d, (m[0][1] * m[2][0] - m[0][0] * m[2][1]) / d, (m[0][0] * m[1][1] - m[0][1] * m[1][0]) / d],
]
}
/// The colour guided filter of `p` with guide `img` (RGB, w × h), window radius `r`,
/// regularisation `eps` (He et al. 2010, section 3.5).
pub fn guided_filter(img: &[[f32; 3]], p: &[f32], w: usize, h: usize, r: usize, eps: f32) -> Vec<f32> {
let n = w * h;
let ch = |c: usize| -> Vec<f32> { img.iter().map(|v| v[c]).collect() };
let (ir, ig, ib) = (ch(0), ch(1), ch(2));
let mul = |a: &[f32], b: &[f32]| -> Vec<f32> { a.iter().zip(b).map(|(x, y)| x * y).collect() };
let bm = |v: &[f32]| box_mean(v, w, h, r);
let (mr, mg, mb, mp) = (bm(&ir), bm(&ig), bm(&ib), bm(p));
let (mrp, mgp, mbp) = (bm(&mul(&ir, p)), bm(&mul(&ig, p)), bm(&mul(&ib, p)));
let (vrr, vrg, vrb) = (bm(&mul(&ir, &ir)), bm(&mul(&ir, &ig)), bm(&mul(&ir, &ib)));
let (vgg, vgb, vbb) = (bm(&mul(&ig, &ig)), bm(&mul(&ig, &ib)), bm(&mul(&ib, &ib)));
let mut a = vec![[0.0f32; 3]; n];
let mut b = vec![0.0f32; n];
a.par_iter_mut().zip(b.par_iter_mut()).enumerate().for_each(|(i, (ai, bi))| {
let cov = [mrp[i] - mr[i] * mp[i], mgp[i] - mg[i] * mp[i], mbp[i] - mb[i] * mp[i]];
let s = [
[vrr[i] - mr[i] * mr[i] + eps, vrg[i] - mr[i] * mg[i], vrb[i] - mr[i] * mb[i]],
[vrg[i] - mr[i] * mg[i], vgg[i] - mg[i] * mg[i] + eps, vgb[i] - mg[i] * mb[i]],
[vrb[i] - mr[i] * mb[i], vgb[i] - mg[i] * mb[i], vbb[i] - mb[i] * mb[i] + eps],
];
let inv = inv3(s);
let av = [
cov[0] * inv[0][0] + cov[1] * inv[1][0] + cov[2] * inv[2][0],
cov[0] * inv[0][1] + cov[1] * inv[1][1] + cov[2] * inv[2][1],
cov[0] * inv[0][2] + cov[1] * inv[1][2] + cov[2] * inv[2][2],
];
*ai = av;
*bi = mp[i] - av[0] * mr[i] - av[1] * mg[i] - av[2] * mb[i];
});
let (a0, a1, a2): (Vec<f32>, Vec<f32>, Vec<f32>) = (a.iter().map(|v| v[0]).collect(), a.iter().map(|v| v[1]).collect(), a.iter().map(|v| v[2]).collect());
let (ma0, ma1, ma2, mbb) = (bm(&a0), bm(&a1), bm(&a2), bm(&b));
(0..n).into_par_iter().map(|i| ma0[i] * ir[i] + ma1[i] * ig[i] + ma2[i] * ib[i] + mbb[i]).collect()
}
/// Closed-form matting (A. Levin, D. Lischinski and Y. Weiss, "A Closed-Form Solution to Natural
/// Image Matting", IEEE PAMI 30(2), 2008): the alpha that minimises αᵀLα with the matting
/// Laplacian `L` of the colour image, with `known` pixels fixed to `init`. Solved by conjugate
/// gradients over the unknown pixels, starting from `init`; `L·x` is evaluated with box filters
/// (K. He, J. Sun and X. Tang, "Fast Matting Using Large Kernel Matting Laplacian Matrices",
/// CVPR 2010): `(L·x)ᵢ = Σ_{k∋i} (xᵢ − a_kᵀIᵢ − b_k)` with `(a_k, b_k)` the ridge-regression
/// fit of `x` to the colours in window k.
pub fn closed_form(img: &[[f32; 3]], init: &[f32], known: &[bool], size: (usize, usize), r: usize, eps: f32, iters: usize) -> Vec<f32> {
let (w, h) = size;
let n = w * h;
if n == 0 || known.iter().all(|k| *k) {
return init.to_vec();
}
let ch = |c: usize| -> Vec<f32> { img.iter().map(|v| v[c]).collect() };
let ic = [ch(0), ch(1), ch(2)];
let bm = |v: &[f32]| box_mean(v, w, h, r);
let mu = [bm(&ic[0]), bm(&ic[1]), bm(&ic[2])];
let prod = |a: usize, b: usize| -> Vec<f32> { ic[a].iter().zip(&ic[b]).map(|(x, y)| x * y).collect() };
let mut cov = [[vec![], vec![], vec![]], [vec![], vec![], vec![]], [vec![], vec![], vec![]]];
for a in 0..3 {
for b in a..3 {
let m = bm(&prod(a, b));
cov[a][b] = m.clone();
cov[b][a] = m;
}
}
let inv: Vec<[[f32; 3]; 3]> = (0..n)
.into_par_iter()
.map(|i| {
let mut s = [[0.0f32; 3]; 3];
for a in 0..3 {
for b in 0..3 {
s[a][b] = cov[a][b][i] - mu[a][i] * mu[b][i] + if a == b { eps } else { 0.0 };
}
}
inv3(s)
})
.collect();
// Pixels per window (= windows per pixel).
let cnt: Vec<f32> = {
let (rr, mut out) = (r as i64, vec![0.0f32; n]);
for (i, o) in out.iter_mut().enumerate() {
let (x, y) = ((i % w) as i64, (i / w) as i64);
let cx = (x + rr).min(w as i64 - 1) - (x - rr).max(0) + 1;
let cy = (y + rr).min(h as i64 - 1) - (y - rr).max(0) + 1;
*o = (cx * cy) as f32;
}
out
};
let lap = |x: &[f32]| -> Vec<f32> {
let pm = bm(x);
let ipm: Vec<Vec<f32>> = (0..3).map(|c| bm(&ic[c].iter().zip(x).map(|(a, b)| a * b).collect::<Vec<_>>())).collect();
let ab: Vec<[f32; 4]> = (0..n)
.into_par_iter()
.map(|i| {
let cv = [ipm[0][i] - mu[0][i] * pm[i], ipm[1][i] - mu[1][i] * pm[i], ipm[2][i] - mu[2][i] * pm[i]];
let m = &inv[i];
let a = [
m[0][0] * cv[0] + m[0][1] * cv[1] + m[0][2] * cv[2],
m[1][0] * cv[0] + m[1][1] * cv[1] + m[1][2] * cv[2],
m[2][0] * cv[0] + m[2][1] * cv[1] + m[2][2] * cv[2],
];
[a[0], a[1], a[2], pm[i] - a[0] * mu[0][i] - a[1] * mu[1][i] - a[2] * mu[2][i]]
})
.collect();
let sa: Vec<Vec<f32>> = (0..3).map(|c| bm(&ab.iter().map(|v| v[c]).collect::<Vec<_>>())).collect();
let sb = bm(&ab.iter().map(|v| v[3]).collect::<Vec<_>>());
(0..n).into_par_iter().map(|i| cnt[i] * (x[i] - sa[0][i] * ic[0][i] - sa[1][i] * ic[1][i] - sa[2][i] * ic[2][i] - sb[i])).collect()
};
// L_UU x = −(L α_K)_U.
let a0: Vec<f32> = (0..n).map(|i| if known[i] { init[i] } else { 0.0 }).collect();
let la0 = lap(&a0);
let mut x: Vec<f32> = (0..n).map(|i| if known[i] { 0.0 } else { init[i] }).collect();
let lx = lap(&x);
let mut res: Vec<f64> = (0..n).map(|i| if known[i] { 0.0 } else { (-la0[i] - lx[i]) as f64 }).collect();
let mut p = res.clone();
let mut rs: f64 = res.iter().map(|v| v * v).sum();
let rs0 = rs.max(1e-30);
for _ in 0..iters {
if rs <= rs0 * 1e-8 {
break;
}
let pf: Vec<f32> = p.iter().map(|v| *v as f32).collect();
let ap: Vec<f64> = lap(&pf).iter().enumerate().map(|(i, v)| if known[i] { 0.0 } else { *v as f64 }).collect();
let pap: f64 = p.iter().zip(&ap).map(|(a, b)| a * b).sum();
if pap <= 1e-30 {
break;
}
let alpha = rs / pap;
for i in 0..n {
x[i] += (alpha * p[i]) as f32;
res[i] -= alpha * ap[i];
}
let rs_new: f64 = res.iter().map(|v| v * v).sum();
let beta = rs_new / rs;
rs = rs_new;
for i in 0..n {
p[i] = res[i] + beta * p[i];
}
}
(0..n).map(|i| if known[i] { init[i] } else { x[i].clamp(0.0, 1.0) }).collect()
}
/// Contrast (0–100 %) around ½ on a soft alpha.
pub fn contrast(a: &mut [f32], pc: f64) {
if pc <= 0.0 {
return;
}
let k = 1.0 / (1.0 - 0.99 * (pc / 100.0).clamp(0.0, 1.0)) as f32;
a.par_iter_mut().for_each(|v| *v = (0.5 + (*v - 0.5) * k).clamp(0.0, 1.0));
}
/// Shift Edge (−100–100 %) on a soft alpha: positive values grow the matte (a gamma curve on α).
pub fn shift_soft(a: &mut [f32], pc: f64) {
if pc.abs() < 1e-9 {
return;
}
let g = 2f32.powf((-pc / 50.0) as f32);
a.par_iter_mut().for_each(|v| *v = v.clamp(0.0, 1.0).powf(g));
}
/// Estimate the pure foreground colour of every pixel listed in `region` (alpha strictly
/// between 0 and 1) and mix it in by `amount` (0–1). `radius`: neighbourhood (pixels) that pure
/// background / foreground estimates are taken from. Returns the decontamination map (how much
/// each pixel's colour changed, 0–1).
pub fn decontaminate(img: &mut [[f32; 3]], alpha: &[f32], region: &[bool], w: usize, h: usize, radius: usize, amount: f32) -> Vec<f32> {
let n = w * h;
let mut map = vec![0.0f32; n];
if !region.iter().any(|r| *r) || amount <= 0.0 {
return map;
}
let lo: Vec<f32> = alpha.iter().map(|a| if *a < 0.02 { 1.0 } else { 0.0 }).collect();
let hi: Vec<f32> = alpha.iter().map(|a| if *a > 0.98 { 1.0 } else { 0.0 }).collect();
// Windowed means of pure background / foreground colours, widening where none is near.
let est = |m: &[f32]| -> Vec<Option<[f32; 3]>> {
let mut out: Vec<Option<[f32; 3]>> = vec![None; n];
let mut r = radius.max(2);
for _ in 0..4 {
let cnt = box_mean(m, w, h, r);
let sums: Vec<Vec<f32>> = (0..3).map(|c| box_mean(&img.iter().zip(m).map(|(p, k)| p[c] * k).collect::<Vec<_>>(), w, h, r)).collect();
let mut missing = false;
for i in 0..n {
if region[i] && out[i].is_none() {
if cnt[i] > 1e-4 {
out[i] = Some([sums[0][i] / cnt[i], sums[1][i] / cnt[i], sums[2][i] / cnt[i]]);
} else {
missing = true;
}
}
}
if !missing {
break;
}
r *= 2;
}
out
};
let bgc = est(&lo);
let fgc = est(&hi);
for i in 0..n {
if !region[i] {
continue;
}
let a = alpha[i].clamp(0.0, 1.0);
if a <= 0.0 || a >= 1.0 {
continue;
}
let c = img[i];
let f = match (bgc[i], fgc[i]) {
(Some(b), fbar) => {
let mut f = [0.0f32; 3];
for k in 0..3 {
f[k] = ((c[k] - (1.0 - a) * b[k]) / a).clamp(0.0, 1.0);
}
// Low alphas amplify noise: lean on the nearby foreground colour there.
if let Some(fb) = fbar {
let t = ((0.25 - a) / 0.25).clamp(0.0, 1.0);
for k in 0..3 {
f[k] += (fb[k] - f[k]) * t;
}
}
f
}
(None, Some(fb)) => fb,
(None, None) => c,
};
let mut d = 0.0f32;
for k in 0..3 {
let v = c[k] + (f[k] - c[k]) * amount;
d = d.max((v - c[k]).abs());
img[i][k] = v;
}
map[i] = d.min(1.0);
}
map
}
/// Sample a float plane bilinearly at continuous coordinates (pixel centres at +0.5), clamped.
pub fn sample(p: &[f32], w: usize, h: usize, x: f64, y: f64) -> f32 {
if w == 0 || h == 0 {
return 0.0;
}
let fx = (x - 0.5).clamp(0.0, (w - 1) as f64);
let fy = (y - 0.5).clamp(0.0, (h - 1) as f64);
let (x0, y0) = (fx.floor() as usize, fy.floor() as usize);
let (x1, y1) = ((x0 + 1).min(w - 1), (y0 + 1).min(h - 1));
let (tx, ty) = ((fx - x0 as f64) as f32, (fy - y0 as f64) as f32);
let g = |x: usize, y: usize| p[y * w + x];
let top = g(x0, y0) + (g(x1, y0) - g(x0, y0)) * tx;
let bot = g(x0, y1) + (g(x1, y1) - g(x0, y1)) * tx;
top + (bot - top) * ty
}
/// Average of `a` sampled along the segment `[-v/2, v/2]` with `samples` taps (motion blur of a
/// matte moving by `v` pixels during the shutter).
pub fn motion_blur(a: &[f32], w: usize, h: usize, v: [f64; 2], samples: usize) -> Vec<f32> {
let n = samples.max(2);
if v[0].hypot(v[1]) < 0.25 {
return a.to_vec();
}
(0..w * h)
.into_par_iter()
.map(|i| {
let (x, y) = ((i % w) as f64 + 0.5, (i / w) as f64 + 0.5);
let mut s = 0.0;
for k in 0..n {
let t = k as f64 / (n - 1) as f64 - 0.5;
s += sample(a, w, h, x - v[0] * t, y - v[1] * t);
}
s / n as f32
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn line_scratch_is_sized_to_the_line_not_the_image() {
let (f, v, z) = line_scratch(1);
assert_eq!((f.len(), v.len(), z.len()), (1, 1, 2));
// A 1 x N image: every row job needs one sample, every column job N.
let (w, h) = (1usize, 50_000usize);
let seed: Vec<bool> = (0..w * h).map(|i| i == 777).collect();
let d = distance(&seed, w, h);
let r = distance_reference(&seed, w, h);
assert!(d.iter().zip(&r).all(|(a, b)| a.to_bits() == b.to_bits()));
}
/// The distance transform as it was before the scratch reuse (one set of vectors per line).
fn distance_reference(seed: &[bool], w: usize, h: usize) -> Vec<f32> {
if w == 0 || h == 0 {
return vec![];
}
let mut g: Vec<f32> = seed.iter().map(|s| if *s { 0.0 } else { BIG }).collect();
let cols: Vec<Vec<f32>> = (0..w)
.map(|x| {
let f: Vec<f32> = (0..h).map(|y| g[y * w + x]).collect();
let mut d = vec![0.0; h];
let (mut v, mut z) = (vec![0usize; h], vec![0.0f64; h + 1]);
dt1(&f, &mut d, &mut v, &mut z);
d
})
.collect();
for (x, c) in cols.iter().enumerate() {
for y in 0..h {
g[y * w + x] = c[y];
}
}
for row in g.chunks_mut(w) {
let f = row.to_vec();
let (mut v, mut z) = (vec![0usize; w], vec![0.0f64; w + 1]);
dt1(&f, row, &mut v, &mut z);
}
g.iter().map(|v| v.sqrt()).collect()
}
#[test]
fn distance_is_bit_identical_to_the_per_line_version() {
let disk =
|w: usize, h: usize, cx: f64, cy: f64, r: f64| -> Vec<bool> { (0..w * h).map(|i| ((i % w) as f64 - cx).hypot((i / w) as f64 - cy) <= r).collect() };
let cases: Vec<(usize, usize, Vec<bool>)> = vec![
(64, 48, disk(64, 48, 30.0, 20.0, 11.0)),
(64, 48, disk(64, 48, 30.0, 20.0, 11.0).iter().map(|b| !b).collect()),
(97, 1, (0..97).map(|i| i % 13 == 0).collect()),
(1, 97, (0..97).map(|i| i % 17 == 5).collect()),
(40, 30, vec![true; 1200]),
(40, 30, vec![false; 1200]),
(40, 30, (0..1200).map(|i| i % 40 == 39 || i / 40 == 0).collect()),
(333, 211, (0..333 * 211).map(|i| (i * 7919) % 1031 == 0).collect()),
];
for (w, h, seed) in cases {
let a = distance(&seed, w, h);
let b = distance_reference(&seed, w, h);
assert_eq!(a.len(), b.len());
for (i, (x, y)) in a.iter().zip(&b).enumerate() {
assert_eq!(x.to_bits(), y.to_bits(), "{w}x{h} pixel {i}: {x} vs {y}");
}
}
assert!(distance(&[], 0, 5).is_empty());
}
/// `cargo test --release -p effectcraft-track distance_bench -- --ignored --nocapture`
/// (set `RAYON_NUM_THREADS` to compare thread counts).
#[test]
#[ignore]
fn distance_bench() {
let (w, h) = (1920, 1080);
let seed: Vec<bool> = (0..w * h).map(|i| ((i % w) as f64 - 960.0).hypot((i / w) as f64 - 540.0) <= 300.0).collect();
let mut times = vec![];
for _ in 0..15 {
let t = std::time::Instant::now();
std::hint::black_box(distance(&seed, w, h));
times.push(t.elapsed().as_secs_f64() * 1000.0);
}
times.sort_by(f64::total_cmp);
eprintln!("distance 1080p, {} threads: median {:.2} ms", rayon::current_num_threads(), times[times.len() / 2]);
}
#[test]
fn distance_matches_brute_force() {
let (w, h) = (23, 17);
let seed: Vec<bool> = (0..w * h).map(|i| (i * 7919) % 31 == 0).collect();
let d = distance(&seed, w, h);
for y in 0..h {
for x in 0..w {
let mut b = f32::INFINITY;
for j in 0..h {
for i in 0..w {
if seed[j * w + i] {
b = b.min(((x as f32 - i as f32).powi(2) + (y as f32 - j as f32).powi(2)).sqrt());
}
}
}
assert!((d[y * w + x] - b).abs() < 1e-3, "{x},{y}: {} vs {b}", d[y * w + x]);
}
}
}
#[test]
fn guided_filter_recovers_a_linear_blend() {
// I = αF + (1 − α)B with constant F, B: the filtered binary matte is close to α.
let (w, h) = (64, 8);
let alpha: Vec<f32> = (0..w * h).map(|i| (((i % w) as f32 - 26.0) / 12.0).clamp(0.0, 1.0)).collect();
let (f, b) = ([0.9f32, 0.2, 0.1], [0.1f32, 0.3, 0.8]);
let img: Vec<[f32; 3]> = alpha.iter().map(|a| [a * f[0] + (1.0 - a) * b[0], a * f[1] + (1.0 - a) * b[1], a * f[2] + (1.0 - a) * b[2]]).collect();
let p: Vec<f32> = alpha.iter().map(|a| if *a >= 0.5 { 1.0 } else { 0.0 }).collect();
let q = guided_filter(&img, &p, w, h, 8, 1e-5);
let err: f32 = q.iter().zip(&alpha).map(|(a, b)| (a.clamp(0.0, 1.0) - b).abs()).sum::<f32>() / (w * h) as f32;
assert!(err < 0.03, "mean error {err}");
}
}
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.