Skip to main content

chess_corners_core/
noise.rs

1//! Per-image estimate of the pixel-noise level.
2//!
3//! A 4×4 window is expanded in the orthogonal polynomials on four points,
4//! `s = (1, 1, 1, 1)`, `l = (−3, −1, 1, 3)`, `e = (1, −1, −1, 1)`,
5//! `d = (1, −3, 3, −1)` (degrees 0–3), giving 16 components `(i, j)`
6//! (degree `i` along x, `j` along y). The estimator measures the noise with
7//! `d ⊗ d`, the product of third differences: it cancels every intensity
8//! that is at most quadratic along either axis — planar shading, straight
9//! edges parallel to an image axis, most of a smoothly blurred pattern —
10//! and for white noise of standard deviation `σ` its output has standard
11//! deviation `20σ`.
12//!
13//! What it does not cancel — sharp edges at any angle, corners — also
14//! drives the other non-smooth components, so a window is used only when
15//! those are small against the current noise level. The gate takes
16//! every component of total degree 3 or more except the operator itself:
17//! `(1,2)`, `(2,1)`, `(2,2)`, `(1,3)`, `(3,1)`, `(2,3)`, `(3,2)`, `(3,0)`,
18//! `(0,3)`. A straight edge along the window diagonal projects only onto
19//! `(i, i)` components, so `(2,2)` is what catches it; smooth shading lives
20//! in the low-degree components and drives none of them.
21//!
22//! Each gate component is scaled to the operator's white-noise variance,
23//! so a noise-only window's gate statistic is χ²₉, and the gate keeps
24//! windows below a fixed multiple of the current noise variance (never
25//! below the 8-bit rounding variance). Under Gaussian noise the components
26//! are uncorrelated with the operator output, so the gate does not bias it.
27//!
28//! The noise level is a fixed point — the gate it sets yields it — reached
29//! from the quietest sixteenth of the windows, so it starts below any
30//! structure, and every estimate is a 4σ-truncated mean of the operator's
31//! square. The threshold is applied exactly to an in-memory sample, so the
32//! result does not jump with the gate setting.
33//!
34//! Sensor noise grows with brightness, so windows are split into four
35//! intensity bands, each reaching its own fixed point from its own quietest
36//! windows. A band holds structure rather than noise — and is dropped — if
37//! its variance exceeds eight times the image-wide one or three times the
38//! median over bands (noise changes smoothly with brightness; edge-only
39//! intensities between flat dark and bright areas stand out). The result
40//! is the admitted-count weighted mean of the remaining bands.
41//!
42//! Windows whose mean lies within [`RAIL_MARGIN`] gray levels of 0 or 255
43//! are skipped: clipping there removes noise. The window mean is the
44//! `(0, 0)` component, orthogonal to the operator, so this selection does
45//! not bias the statistic (rejecting by pixel value would).
46//!
47//! The windows are a fixed sample of about [`WINDOWS`] on a staggered grid
48//! (four times as many, once, when too few are free of edges); everything
49//! after sampling works on the sample alone.
50
51/// About this many 4×4 windows are sampled per image.
52const WINDOWS: usize = 8192;
53/// Windows whose mean is within this many gray levels of 0 or 255 are
54/// skipped (clipped noise).
55const RAIL_MARGIN: i32 = 12;
56/// Gate components `(degree along x, degree along y)`.
57const GATE_TERMS: [(usize, usize); 9] = [
58    (1, 2),
59    (2, 1),
60    (2, 2),
61    (1, 3),
62    (3, 1),
63    (2, 3),
64    (3, 2),
65    (3, 0),
66    (0, 3),
67];
68/// Keep windows whose gate statistic (χ²₉ for noise) is below this.
69const GATE: f64 = 20.0;
70/// Truncation of the operator's second moment, in its standard deviations.
71const TRUNC: f64 = 4.0;
72/// A band whose noise variance exceeds this many times the image-wide one
73/// is taken for structure.
74const MAX_BAND_RATIO: f64 = 8.0;
75/// A band whose noise variance exceeds this many times the median over
76/// bands is taken for structure.
77const MAX_BAND_OUTLIER: f64 = 3.0;
78/// A band needs this many admitted windows to contribute.
79const MIN_BAND_SAMPLES: usize = 128;
80/// Below this many admitted windows over all bands the estimate is not
81/// reported (the relative standard error of σ̂ is about `1/sqrt(2n)`, 3%
82/// here).
83const MIN_SAMPLES: usize = 512;
84/// A fixed point counts as settled when the variance moves by less than
85/// this fraction.
86const SETTLED: f64 = 1e-3;
87/// Fixed-point rounds (the gate settles in a handful).
88const ROUNDS: usize = 12;
89/// Intensity bands, by window mean: `[0, 64)`, `[64, 128)`, ….
90const BANDS: usize = 4;
91/// Standard deviation of the operator output per unit pixel noise σ
92/// (`sqrt(Σ wᵢ²) = sqrt(20 · 20)`).
93const OPERATOR_GAIN: f64 = 20.0;
94
95/// Estimate the standard deviation of the pixel noise in an 8-bit
96/// grayscale image, in gray levels.
97///
98/// Measures the noise as it appears in the 8-bit image, so the estimate
99/// includes the rounding to integers (`1/12` gray level² when the noise
100/// spans several levels). It is designed for images dominated by strong
101/// edges, such as calibration boards: edges, corners and smooth shading are
102/// excluded from the statistic, and so are areas within 12 gray levels of
103/// black or white, where clipping removes noise. Under signal-dependent
104/// noise the estimate is the root of the mean noise variance over the
105/// image's structure-free areas.
106///
107/// For white noise it is the noise standard deviation; adding white noise
108/// of variance `σₐ²` raises its square by `σₐ²`. It is not reliable for
109/// spatially correlated noise: on Bayer-demosaiced images it reads the
110/// demosaicing pattern along edges (about 4 gray levels whatever the
111/// noise), and on JPEG images of a dense board it usually returns `None`,
112/// because almost every 8×8 block holds an edge. Supply the noise level for
113/// such images instead, measured on the delivered images (for example from
114/// two frames of a static scene).
115///
116/// Accuracy on synthetic boards with white noise (cells 5–12, any rotation
117/// or shear, blur up to 2.5 px): within about 4% for σ ≥ 2 gray levels and
118/// 5% for σ ≥ 1 (12% on images with very few structure-free areas). Below
119/// 1 gray level, residual pattern in strongly blurred images is comparable
120/// to the noise and reads up to about 20% high. Images
121/// with almost no structure-free area — small, sharp or slightly blurred
122/// cells filling the whole frame — give no estimate at low noise and can
123/// read high (up to 2×) at very high noise.
124///
125/// Deterministic and cheap: it samples about 8 000 4×4 windows on a
126/// regular grid, so the cost does not grow with the image size (under
127/// 0.1 ms per frame); only an image where too few of them are free of edges
128/// is sampled once more, four times as densely.
129///
130/// Returns `None` when the image is smaller than 4×4 or too few windows
131/// (fewer than 512) are free of edges.
132///
133/// # Panics
134///
135/// Panics if `img.len() != w * h`.
136pub fn estimate_noise_sigma_u8(img: &[u8], w: usize, h: usize) -> Option<f32> {
137    assert_eq!(
138        img.len(),
139        w * h,
140        "estimate_noise_sigma_u8: img.len() ({}) must equal w*h ({w} * {h} = {})",
141        img.len(),
142        w * h,
143    );
144    if w < 4 || h < 4 {
145        return None;
146    }
147    // An image with too few structure-free windows in the sample is
148    // sampled once more, four times as densely.
149    let (sample, step) = Sample::collect(img, w, h, WINDOWS);
150    noise_sigma(&sample).or_else(|| {
151        (step > 1)
152            .then(|| Sample::collect(img, w, h, 4 * WINDOWS).0)
153            .and_then(|dense| noise_sigma(&dense))
154    })
155}
156
157/// The noise σ of a sample (see [`estimate_noise_sigma_u8`]).
158fn noise_sigma(sample: &Sample) -> Option<f32> {
159    if sample.len() < MIN_SAMPLES {
160        return None;
161    }
162    let image_var = sample.image_variance();
163    // Per band: the fixed point of its own gate and its admitted count.
164    let mut bands = [(0usize, 0f64); BANDS];
165    let mut count = 0;
166    for found in (0..BANDS).filter_map(|b| sample.band(b).variance(image_var)) {
167        bands[count] = found;
168        count += 1;
169    }
170    let bands = &bands[..count];
171    // Noise variance changes smoothly with brightness; a band far above the
172    // others holds structure (edge-only intensities between the flat ones).
173    let mut vars = [0f64; BANDS];
174    for (slot, &(_, v)) in vars.iter_mut().zip(bands) {
175        *slot = v;
176    }
177    let vars = &mut vars[..count];
178    vars.sort_by(f64::total_cmp);
179    let median = match vars.len() {
180        0 => return None,
181        n if n % 2 == 1 => vars[n / 2],
182        n => 0.5 * (vars[n / 2 - 1] + vars[n / 2]),
183    };
184    let (mut n, mut nvar) = (0usize, 0f64);
185    for &(nb, var) in bands {
186        if var <= MAX_BAND_OUTLIER * median.max(ROUNDING_OP_VAR) {
187            n += nb;
188            nvar += nb as f64 * var;
189        }
190    }
191    (n >= MIN_SAMPLES).then(|| ((nvar / n as f64).sqrt() / OPERATOR_GAIN) as f32)
192}
193
194/// Windows per block of [`Band::admitted`]'s sum.
195const BLOCK: usize = 256;
196/// Blocks [`Band::admitted`] sums side by side.
197const LANES: usize = 8;
198
199/// The sampled windows of one intensity band, structure of arrays: gate
200/// statistic (in units of the operator's noise variance) and squared
201/// operator output per window.
202#[derive(Clone, Copy)]
203struct Band<'a> {
204    gate: &'a [f32],
205    op: &'a [f32],
206}
207
208impl Band<'_> {
209    /// Truncated mean of the operator's square over the windows whose gate
210    /// statistic is below [`GATE`] times `gate_var`, and their count.
211    fn admitted(&self, gate_var: f64, op_var: f64) -> (usize, f64) {
212        let threshold = (GATE * gate_var.max(ROUNDING_OP_VAR)) as f32;
213        let cut = (TRUNC * TRUNC * op_var.max(ROUNDING_OP_VAR)) as f32;
214        let kept = |g: f32, o: f32| {
215            let keep = (g < threshold) & (o <= cut);
216            (if keep { o } else { 0.0 }, u32::from(keep))
217        };
218        let (mut sum, mut n) = (0f64, 0usize);
219        // Branch-free blocks of `BLOCK` windows summed in f32, accumulated
220        // in f64 in block order. `LANES` blocks run side by side, each in
221        // its own order, so the sum does not wait on one chain of additions.
222        let (gate, op) = (self.gate, self.op);
223        let full = gate.len() / BLOCK;
224        let mut first = 0;
225        while first + LANES <= full {
226            let (mut block, mut count) = ([0f32; LANES], [0u32; LANES]);
227            let gates: [&[f32]; LANES] =
228                core::array::from_fn(|l| &gate[(first + l) * BLOCK..(first + l + 1) * BLOCK]);
229            let ops: [&[f32]; LANES] =
230                core::array::from_fn(|l| &op[(first + l) * BLOCK..(first + l + 1) * BLOCK]);
231            for i in 0..BLOCK {
232                for l in 0..LANES {
233                    let (v, c) = kept(gates[l][i], ops[l][i]);
234                    block[l] += v;
235                    count[l] += c;
236                }
237            }
238            for l in 0..LANES {
239                sum += f64::from(block[l]);
240                n += count[l] as usize;
241            }
242            first += LANES;
243        }
244        let rest = first * BLOCK;
245        for (gates, ops) in gate[rest..].chunks(BLOCK).zip(op[rest..].chunks(BLOCK)) {
246            let (mut block, mut count) = (0f32, 0u32);
247            for (&g, &o) in gates.iter().zip(ops) {
248                let (v, c) = kept(g, o);
249                block += v;
250                count += c;
251            }
252            sum += f64::from(block);
253            n += count as usize;
254        }
255        (n, sum)
256    }
257
258    /// Operator noise variance of the band, with its admitted window
259    /// count: the fixed point of the band's own gate, starting from the
260    /// quietest sixteenth of its windows. `None` when too few windows are
261    /// admitted or the variance exceeds [`MAX_BAND_RATIO`] times the
262    /// image-wide one (structure).
263    fn variance(&self, image_var: f64) -> Option<(usize, f64)> {
264        if self.gate.len() < MIN_BAND_SAMPLES {
265            return None;
266        }
267        let quiet = quantile(self.gate, 1.0 / 16.0);
268        let mut var = mean_quiet(self.op, self.gate, quiet);
269        let mut n_prev = usize::MAX;
270        for _ in 0..ROUNDS {
271            let (n, sum) = self.admitted(var, var);
272            if n == 0 {
273                return None;
274            }
275            let next = sum / n as f64 / TRUNC_SECOND_MOMENT;
276            let settled = n == n_prev || (next - var).abs() <= SETTLED * var;
277            (var, n_prev) = (next, n);
278            if settled {
279                break;
280            }
281        }
282        let structure = var > MAX_BAND_RATIO * image_var.max(ROUNDING_OP_VAR);
283        (n_prev >= MIN_BAND_SAMPLES && !structure).then_some((n_prev, var))
284    }
285}
286
287/// The sampled windows, by intensity band: the bands one after the other,
288/// each in sampling order.
289struct Sample {
290    /// Gate statistics of the `kept` windows, then squared operator outputs
291    /// of the same: each followed by one spare slot (the sink for windows
292    /// near the rails while sorting), `2 * kept + 2` values in all.
293    buf: Vec<f32>,
294    kept: usize,
295    /// Band `b` is windows `start[b]..start[b + 1]`.
296    start: [usize; BANDS + 1],
297}
298
299impl Sample {
300    fn len(&self) -> usize {
301        self.kept
302    }
303
304    /// Gate statistic per window, all bands.
305    fn gate(&self) -> &[f32] {
306        &self.buf[..self.kept]
307    }
308
309    /// Squared operator output per window, all bands.
310    fn op(&self) -> &[f32] {
311        &self.buf[self.kept + 1..2 * self.kept + 1]
312    }
313
314    /// The windows of band `b`.
315    fn band(&self, b: usize) -> Band<'_> {
316        let range = self.start[b]..self.start[b + 1];
317        Band {
318            gate: &self.gate()[range.clone()],
319            op: &self.op()[range],
320        }
321    }
322
323    /// Sample about `windows` 4×4 windows on a grid of step
324    /// `⌈√(w·h / windows)⌉`, each grid row offset by a golden-ratio fraction
325    /// of the step so a coarse grid does not alias with a periodic pattern
326    /// such as a board's cells. Returns the sample and the step.
327    fn collect(img: &[u8], w: usize, h: usize, windows: usize) -> (Self, usize) {
328        let step = (((w * h) as f64 / windows as f64).sqrt().ceil() as usize).max(1);
329        // Grid row `j` has its first window at `x0` and `count` windows.
330        let grid_row = |j: usize| {
331            let x0 = ((j as f64 * 0.618_034).fract() * step as f64) as usize;
332            (x0, (w - 3).saturating_sub(x0).div_ceil(step))
333        };
334        let total: usize = (0..(h - 3).div_ceil(step)).map(|j| grid_row(j).1).sum();
335        // Every window in sampling order: pixel sum, gate, operator output.
336        let mut raw = vec![0i32; 3 * total];
337        let (sums, rest) = raw.split_at_mut(total);
338        let (gates, ops) = rest.split_at_mut(total);
339        let mut at = 0;
340        for (j, y) in (0..h - 3).step_by(step).enumerate() {
341            let (x0, count) = grid_row(j);
342            let rows = &img[y * w..(y + 4) * w];
343            let mut k = 0;
344            while k + BATCH <= count {
345                let xs = core::array::from_fn(|l| x0 + (k + l) * step);
346                let [s, g, o] = window_batch(rows, w, &xs);
347                sums[at..at + BATCH].copy_from_slice(&s);
348                gates[at..at + BATCH].copy_from_slice(&g);
349                ops[at..at + BATCH].copy_from_slice(&o);
350                (k, at) = (k + BATCH, at + BATCH);
351            }
352            for k in k..count {
353                [sums[at], gates[at], ops[at]] = window(rows, w, x0 + k * step);
354                at += 1;
355            }
356        }
357        // Band of a window by its mean (window mean / 64 = sum / 1024), or
358        // `BANDS` near the rails, where clipping removes noise: those are
359        // skipped.
360        let band = |sum: i32| {
361            if (16 * RAIL_MARGIN..=16 * (255 - RAIL_MARGIN)).contains(&sum) {
362                (sum >> 10) as usize
363            } else {
364                BANDS
365            }
366        };
367        let mut count = [0usize; BANDS + 1];
368        for &sum in &*sums {
369            let b = band(sum);
370            for (slot, n) in count.iter_mut().enumerate() {
371                *n += usize::from(b == slot);
372            }
373        }
374        let mut start = [0usize; BANDS + 1];
375        for b in 0..BANDS {
376            start[b + 1] = start[b] + count[b];
377        }
378        let kept = start[BANDS];
379        // Grouped by band, each in sampling order; windows near the rails
380        // land in one spare slot past the end.
381        let mut buf = vec![0f32; 2 * kept + 2];
382        let (gate, op) = buf.split_at_mut(kept + 1);
383        let [mut c0, mut c1, mut c2, mut c3] = [start[0], start[1], start[2], start[3]];
384        for ((&sum, &g), &o) in sums.iter().zip(&*gates).zip(&*ops) {
385            let b = band(sum);
386            let k = match b {
387                0 => c0,
388                1 => c1,
389                2 => c2,
390                3 => c3,
391                _ => kept,
392            };
393            let o = o as f32;
394            (gate[k], op[k]) = (g as f32, o * o);
395            c0 += usize::from(b == 0);
396            c1 += usize::from(b == 1);
397            c2 += usize::from(b == 2);
398            c3 += usize::from(b == 3);
399        }
400        (Self { buf, kept, start }, step)
401    }
402
403    /// Image-wide operator noise variance: the fixed point where the gate
404    /// it sets yields it, starting from the quietest sixteenth of the
405    /// windows (below any structure).
406    fn image_variance(&self) -> f64 {
407        let quiet = quantile(self.gate(), 1.0 / 16.0);
408        let mut var = mean_quiet(self.op(), self.gate(), quiet);
409        let mut n_prev = usize::MAX;
410        for _ in 0..ROUNDS {
411            let (n, sum) = (0..BANDS)
412                .map(|b| self.band(b).admitted(var, var))
413                .fold((0, 0.0), |(n, s), (bn, bs)| (n + bn, s + bs));
414            if n == 0 {
415                break;
416            }
417            let next = sum / n as f64 / TRUNC_SECOND_MOMENT;
418            let settled = n == n_prev || (next - var).abs() <= SETTLED * var;
419            (var, n_prev) = (next, n);
420            if settled {
421                break;
422            }
423        }
424        var
425    }
426}
427
428/// The 4×4 window with top-left pixel `(x, 0)` of the four image rows
429/// `rows` (stride `w`): its pixel sum, gate statistic and operator output
430/// `(3, 3)`.
431#[inline(always)]
432fn window(rows: &[u8], w: usize, x: usize) -> [i32; 3] {
433    window_stats(core::array::from_fn(|k| {
434        let start = k * w + x;
435        let px: [u8; 4] = rows[start..start + 4]
436            .try_into()
437            .expect("window lies inside the image");
438        px.map(i32::from)
439    }))
440}
441
442/// Pixel sum, gate statistic and operator output `(3, 3)` of the 4×4
443/// window `px` (`px[y][x]`).
444#[inline(always)]
445fn window_stats(px: [[i32; 4]; 4]) -> [i32; 3] {
446    // Polynomials down the columns, then across: `comp[i][j]` is component
447    // `(i, j)` (degree `i` along x, `j` along y).
448    let comp = poly4_down(transpose(poly4_down(px)));
449    // On 8-bit pixels the weighted sum stays below 7.4·10⁸: exact in `i32`.
450    let mut gate = 0;
451    for (c, wt) in comp.iter().zip(&GATE_WEIGHT) {
452        for j in 0..4 {
453            gate += c[j] * c[j] * wt[j];
454        }
455    }
456    [comp[0][0], gate, comp[3][3]]
457}
458
459/// Windows [`window_batch`] evaluates side by side.
460const BATCH: usize = 8;
461/// One value per window of a batch.
462type Lanes = [i32; BATCH];
463
464/// The [`BATCH`] 4×4 windows with top-left pixels `(xs[l], 0)` of the four
465/// image rows `rows` (stride `w`): per window the pixel sum, the gate
466/// statistic and the operator output `(3, 3)`.
467#[inline(always)]
468fn window_batch(rows: &[u8], w: usize, xs: &[usize; BATCH]) -> [Lanes; 3] {
469    // Four pixels per window and row, packed little-endian.
470    let packed: [[u32; BATCH]; 4] = core::array::from_fn(|k| {
471        core::array::from_fn(|l| {
472            let start = k * w + xs[l];
473            u32::from_le_bytes(
474                rows[start..start + 4]
475                    .try_into()
476                    .expect("window lies inside the image"),
477            )
478        })
479    });
480    let mut out = [[0i32; BATCH]; 3];
481    // One window per iteration, the same arithmetic in every lane.
482    for l in 0..BATCH {
483        let px = core::array::from_fn(|k| {
484            core::array::from_fn(|c| ((packed[k][l] >> (8 * c)) & 0xff) as i32)
485        });
486        let [sum, gate, op] = window_stats(px);
487        (out[0][l], out[1][l], out[2][l]) = (sum, gate, op);
488    }
489    out
490}
491
492/// Operator variance of the 8-bit rounding noise (`400 / 12`): the gate is
493/// never set tighter than this.
494const ROUNDING_OP_VAR: f64 = 400.0 / 12.0;
495
496/// `E[z² | |z| < TRUNC]` for a standard normal `z`: the truncated second
497/// moment is divided by it.
498const TRUNC_SECOND_MOMENT: f64 = 0.998_929;
499/// Squared norms of the orthogonal polynomials `s`, `l`, `e`, `d`
500/// ([`poly4_down`]).
501const POLY_NORM2: [i32; 4] = [4, 20, 4, 20];
502/// Weight of component `(i, j)` in the gate statistic, `[i][j]`: the
503/// [`GATE_TERMS`] scaled to the operator's white-noise variance
504/// (`‖d‖⁴ = 400`), `400 / (‖Pᵢ‖²‖Pⱼ‖²)` (1, 5 or 25); 0 elsewhere.
505const GATE_WEIGHT: [[i32; 4]; 4] = {
506    let mut wt = [[0; 4]; 4];
507    let mut k = 0;
508    while k < GATE_TERMS.len() {
509        let (i, j) = GATE_TERMS[k];
510        wt[i][j] = 400 / (POLY_NORM2[i] * POLY_NORM2[j]);
511        k += 1;
512    }
513    wt
514};
515
516/// The four orthogonal polynomials `[s, l, e, d]` applied down each column
517/// of four rows: `out[p][x]` is polynomial `p` over `rows[0..4][x]`.
518#[inline(always)]
519fn poly4_down([v0, v1, v2, v3]: [[i32; 4]; 4]) -> [[i32; 4]; 4] {
520    let lanes = |f: fn(i32, i32, i32, i32) -> i32| -> [i32; 4] {
521        core::array::from_fn(|x| f(v0[x], v1[x], v2[x], v3[x]))
522    };
523    [
524        lanes(|a, b, c, d| a + b + c + d),
525        lanes(|a, b, c, d| 3 * (d - a) + c - b),
526        lanes(|a, b, c, d| a - b - c + d),
527        lanes(|a, b, c, d| a - 3 * b + 3 * c - d),
528    ]
529}
530
531/// Transpose of a 4×4 array.
532#[inline(always)]
533fn transpose(m: [[i32; 4]; 4]) -> [[i32; 4]; 4] {
534    core::array::from_fn(|i| core::array::from_fn(|j| m[j][i]))
535}
536
537/// Mean of `op[k]` over the windows whose `gate[k] <= quiet` (0 if none),
538/// summed in window order.
539fn mean_quiet(op: &[f32], gate: &[f32], quiet: f32) -> f64 {
540    let (mut sum, mut n) = (0f64, 0usize);
541    let mut picked = [0f32; BLOCK];
542    for (ops, gates) in op.chunks(BLOCK).zip(gate.chunks(BLOCK)) {
543        // Branch-free selection: write every value, keep the quiet ones.
544        let mut m = 0;
545        for (&o, &g) in ops.iter().zip(gates) {
546            picked[m] = o;
547            m += usize::from(g <= quiet);
548        }
549        for &v in &picked[..m] {
550            sum += f64::from(v);
551        }
552        n += m;
553    }
554    if n == 0 {
555        0.0
556    } else {
557        sum / n as f64
558    }
559}
560
561/// The `p`-quantile of a sub-sample of at most 255 evenly spaced values.
562fn quantile(values: &[f32], p: f64) -> f32 {
563    let stride = values.len().div_ceil(255).max(1);
564    let mut buf = [0f32; 255];
565    let mut n = 0;
566    for &v in values.iter().step_by(stride) {
567        buf[n] = v;
568        n += 1;
569    }
570    let sub = &mut buf[..n];
571    let at = ((n as f64 * p) as usize).min(n - 1);
572    *sub.select_nth_unstable_by(at, f32::total_cmp).1
573}
574
575#[cfg(test)]
576mod tests {
577    use super::*;
578
579    #[test]
580    fn tiny_or_flat_images() {
581        assert_eq!(estimate_noise_sigma_u8(&[0; 4], 2, 2), None);
582        // Too few samples.
583        assert_eq!(estimate_noise_sigma_u8(&[7; 100], 10, 10), None);
584        // Flat, noise-free: zero.
585        let flat = vec![100u8; 64 * 64];
586        let s = estimate_noise_sigma_u8(&flat, 64, 64).expect("estimate");
587        assert!(s < 0.01, "{s}");
588        // Saturated: no usable window.
589        let white = vec![255u8; 64 * 64];
590        assert_eq!(estimate_noise_sigma_u8(&white, 64, 64), None);
591    }
592
593    #[test]
594    #[should_panic(expected = "estimate_noise_sigma_u8: img.len()")]
595    fn panics_on_dimension_mismatch() {
596        let _ = estimate_noise_sigma_u8(&[0; 10], 4, 4);
597    }
598}