Skip to content

armgit / ente

Public Imported from GitHub
0

πŸ’š End-to-end encrypted cloud for everything.

76.8 KB
Raw Blame
use super::page::{SourceExtent, area, cross, distance, points, quad_from_points, validate_quad};
use super::segmentation::ProbabilityMap;
use super::{OpResult, Point, Quad};
use crate::cv::image::ImageU8;

#[derive(Clone, Copy)]
pub(super) enum SearchBudget {
    Live,
    Capture,
}

#[derive(Clone, Copy)]
pub(super) struct MaskQuad {
    pub corners: Quad,
    pub needs_complete_source_support: bool,
    extent: SourceExtent,
}

impl MaskQuad {
    pub fn in_source(self, source: SourceExtent) -> Quad {
        quad_from_points(points(self.corners).map(|p| Point {
            x: p.x * source.width / self.extent.width,
            y: p.y * source.height / self.extent.height,
        }))
    }
}

pub(super) struct Detection {
    pub quad: Option<MaskQuad>,
    pub confidence: f64,
    pub reason: &'static str,
}

#[derive(Clone, Copy)]
struct Line {
    nx: f64,
    ny: f64,
    offset: f64,
}

impl Line {
    fn through(a: Point, b: Point) -> Self {
        let length = distance(a, b);
        let nx = (b.y - a.y) / length;
        let ny = (a.x - b.x) / length;
        Self {
            nx,
            ny,
            offset: nx * a.x + ny * a.y,
        }
    }

    fn residual(self, p: Point) -> f64 {
        self.nx * p.x + self.ny * p.y - self.offset
    }

    fn intersection(self, other: Self) -> Option<Point> {
        let determinant = self.nx * other.ny - self.ny * other.nx;
        if determinant.abs() < 1e-4 {
            return None;
        }
        Some(Point {
            x: (self.offset * other.ny - self.ny * other.offset) / determinant,
            y: (self.nx * other.offset - self.offset * other.nx) / determinant,
        })
    }
}

fn fit_line(samples: &[Point], initial: Line, scale: f64) -> Line {
    let mut line = initial;
    for _ in 0..3 {
        let mut sx = 0.0;
        let mut sy = 0.0;
        let mut weight = 0.0;
        for &p in samples {
            let w = (1.0 + (line.residual(p) / scale).powi(2)).recip();
            sx += p.x * w;
            sy += p.y * w;
            weight += w;
        }
        if weight < 2.0 {
            return initial;
        }
        let center = Point {
            x: sx / weight,
            y: sy / weight,
        };
        let mut xx = 0.0;
        let mut yy = 0.0;
        let mut xy = 0.0;
        for &p in samples {
            let w = (1.0 + (line.residual(p) / scale).powi(2)).recip();
            xx += (p.x - center.x).powi(2) * w;
            yy += (p.y - center.y).powi(2) * w;
            xy += (p.x - center.x) * (p.y - center.y) * w;
        }
        let angle = 0.5 * (2.0 * xy).atan2(xx - yy);
        let nx = -angle.sin();
        let ny = angle.cos();
        line = Line {
            nx,
            ny,
            offset: nx * center.x + ny * center.y,
        };
    }
    line
}

fn convex_hull(mut boundary: Vec<Point>) -> Vec<Point> {
    boundary.sort_by(|a, b| a.x.total_cmp(&b.x).then(a.y.total_cmp(&b.y)));
    boundary.dedup_by(|a, b| a.x == b.x && a.y == b.y);
    let mut hull: Vec<Point> = Vec::new();
    for &p in &boundary {
        while hull.len() >= 2 && cross(hull[hull.len() - 2], hull[hull.len() - 1], p) <= 0.0 {
            hull.pop();
        }
        hull.push(p);
    }
    let lower = hull.len();
    for &p in boundary.iter().rev().skip(1) {
        while hull.len() > lower && cross(hull[hull.len() - 2], hull[hull.len() - 1], p) <= 0.0 {
            hull.pop();
        }
        hull.push(p);
    }
    hull.pop();
    hull
}

fn simplify(mut hull: Vec<Point>, count: usize) -> Vec<Point> {
    while hull.len() > count {
        let Some(index) = (0..hull.len()).min_by(|&a, &b| {
            let loss = |i| {
                cross(
                    hull[(i + hull.len() - 1) % hull.len()],
                    hull[i],
                    hull[(i + 1) % hull.len()],
                )
                .abs()
            };
            loss(a).total_cmp(&loss(b)).then(a.cmp(&b))
        }) else {
            break;
        };
        hull.remove(index);
    }
    hull
}

pub(super) fn canonical(mut p: [Point; 4], extent: SourceExtent) -> Quad {
    if area(&p) < 0.0 {
        p.reverse();
    }
    let first = (0..4)
        .min_by(|&a, &b| {
            let pa = p[a];
            let pb = p[b];
            (pa.x / extent.width + pa.y / extent.height)
                .total_cmp(&(pb.x / extent.width + pb.y / extent.height))
                .then(pa.x.total_cmp(&pb.x))
                .then(pa.y.total_cmp(&pb.y))
        })
        .unwrap_or(0);
    quad_from_points(std::array::from_fn(|i| p[(i + first) % 4]))
}

struct Component {
    pixels: Vec<usize>,
    boundary: Vec<Point>,
}

fn background_regions(map: &ProbabilityMap, cutoff: f32) -> Vec<usize> {
    let mut labels = vec![0; map.values.len()];
    let mut touches_frame = vec![true];
    let mut queue = Vec::new();
    for seed in 0..map.values.len() {
        if map.values[seed] >= cutoff || labels[seed] != 0 {
            continue;
        }
        let label = touches_frame.len();
        touches_frame.push(false);
        labels[seed] = label;
        queue.clear();
        queue.push(seed);
        let mut cursor = 0;
        while cursor < queue.len() {
            let index = queue[cursor];
            cursor += 1;
            let x = index % map.width;
            let y = index / map.width;
            touches_frame[label] |= x == 0 || y == 0 || x + 1 == map.width || y + 1 == map.height;
            for dy in -1isize..=1 {
                for dx in -1isize..=1 {
                    let nx = x as isize + dx;
                    let ny = y as isize + dy;
                    if nx < 0 || ny < 0 || nx >= map.width as isize || ny >= map.height as isize {
                        continue;
                    }
                    let neighbor = ny as usize * map.width + nx as usize;
                    if map.values[neighbor] < cutoff && labels[neighbor] == 0 {
                        labels[neighbor] = label;
                        queue.push(neighbor);
                    }
                }
            }
        }
    }
    for label in &mut labels {
        if touches_frame[*label] {
            *label = 0;
        }
    }
    labels
}

fn components(map: &ProbabilityMap, cutoff: f32, count: usize, outer_only: bool) -> Vec<Component> {
    let background = outer_only.then(|| background_regions(map, cutoff));
    let mut visited = vec![false; map.values.len()];
    let mut components = Vec::new();
    for seed in 0..map.values.len() {
        if visited[seed] || map.values[seed] < cutoff {
            continue;
        }
        let exterior = if seed < map.width {
            0
        } else {
            background
                .as_ref()
                .map_or(0, |regions| regions[seed - map.width])
        };
        let mut queue = vec![seed];
        visited[seed] = true;
        let mut cursor = 0;
        let mut boundary = Vec::new();
        while cursor < queue.len() {
            let index = queue[cursor];
            cursor += 1;
            let x = index % map.width;
            let y = index / map.width;
            for (dx, dy) in [(-1isize, 0isize), (1, 0), (0, -1), (0, 1)] {
                let nx = x as isize + dx;
                let ny = y as isize + dy;
                if nx < 0 || ny < 0 || nx >= map.width as isize || ny >= map.height as isize {
                    boundary.push(Point {
                        x: x as f64 + 0.5 + dx as f64 * 0.5,
                        y: y as f64 + 0.5 + dy as f64 * 0.5,
                    });
                    continue;
                }
                let neighbor = ny as usize * map.width + nx as usize;
                if map.values[neighbor] < cutoff {
                    if background
                        .as_ref()
                        .is_some_and(|regions| regions[neighbor] != exterior)
                    {
                        continue;
                    }
                    let t = ((map.values[index] - cutoff)
                        / (map.values[index] - map.values[neighbor]))
                        as f64;
                    boundary.push(Point {
                        x: x as f64 + 0.5 + dx as f64 * t,
                        y: y as f64 + 0.5 + dy as f64 * t,
                    });
                } else if !visited[neighbor] {
                    visited[neighbor] = true;
                    queue.push(neighbor);
                }
            }
        }
        if queue.len() >= 64 && queue.len() * 500 >= map.values.len() {
            components.push(Component {
                pixels: queue,
                boundary,
            });
        }
    }
    components.sort_by(|a, b| {
        b.pixels
            .len()
            .cmp(&a.pixels.len())
            .then(a.pixels[0].cmp(&b.pixels[0]))
    });
    components.truncate(count);
    components
}

fn supported_fit(p: [Point; 4], boundary: &[Point], extent: SourceExtent) -> Option<[Point; 4]> {
    let initial = std::array::from_fn::<_, 4, _>(|i| Line::through(p[i], p[(i + 1) % 4]));
    let mut sides: [Vec<Point>; 4] = std::array::from_fn(|_| Vec::new());
    let band = extent.width.hypot(extent.height) * 0.025;
    for &point in boundary {
        let side = (0..4)
            .min_by(|&a, &b| {
                initial[a]
                    .residual(point)
                    .abs()
                    .total_cmp(&initial[b].residual(point).abs())
            })
            .unwrap_or(0);
        if initial[side].residual(point).abs() < band {
            sides[side].push(point);
        }
    }
    let mut lines = initial;
    for i in 0..4 {
        if sides[i].len() < 4 {
            return None;
        }
        lines[i] = fit_line(&sides[i], initial[i], (band / 4.0).max(0.5));
        let along = |p: Point| lines[i].ny * p.x - lines[i].nx * p.y;
        let lo = sides[i]
            .iter()
            .map(|&p| along(p))
            .fold(f64::INFINITY, f64::min);
        let hi = sides[i]
            .iter()
            .map(|&p| along(p))
            .fold(f64::NEG_INFINITY, f64::max);
        if hi - lo < distance(p[i], p[(i + 1) % 4]) * 0.55 {
            return None;
        }
    }
    let mut fitted = p;
    for i in 0..4 {
        fitted[i] = lines[(i + 3) % 4].intersection(lines[i])?;
    }
    if (0..4).any(|i| distance(fitted[i], p[i]) > band * 2.0) {
        return None;
    }
    Some(fitted)
}

fn evidence(
    map: &ProbabilityMap,
    component: &Component,
    p: [Point; 4],
    live: bool,
) -> Option<(f64, bool)> {
    let extent = SourceExtent {
        width: map.width as f64,
        height: map.height as f64,
    };
    validate_quad(quad_from_points(p), extent).ok()?;
    let lines = std::array::from_fn::<_, 4, _>(|i| Line::through(p[i], p[(i + 1) % 4]));
    let inside = |q: Point| (0..4).all(|i| cross(p[i], p[(i + 1) % 4], q) >= -0.1);
    let captured = component
        .pixels
        .iter()
        .filter(|&&i| {
            inside(Point {
                x: (i % map.width) as f64 + 0.5,
                y: (i / map.width) as f64 + 0.5,
            })
        })
        .count() as f64
        / component.pixels.len() as f64;
    if captured < if live { 0.93 } else { 0.90 } {
        return None;
    }
    let mut mass = 0.0;
    let mut count = 0usize;
    for y in (0..map.height).step_by(2) {
        for x in (0..map.width).step_by(2) {
            if inside(Point {
                x: x as f64 + 0.5,
                y: y as f64 + 0.5,
            }) {
                mass += map.values[y * map.width + x] as f64;
                count += 1;
            }
        }
    }
    if count == 0 {
        return None;
    }
    let purity = mass / count as f64;
    if purity < if live { 0.78 } else { 0.68 } {
        return None;
    }
    let mut residuals: Vec<f64> = component
        .boundary
        .iter()
        .map(|&p| {
            lines
                .iter()
                .map(|line| line.residual(p).abs())
                .fold(f64::INFINITY, f64::min)
        })
        .collect();
    residuals.sort_by(f64::total_cmp);
    let residual = residuals[residuals.len() * 4 / 5];
    let thickness =
        (area(&p) / (0..4).map(|i| distance(p[i], p[(i + 1) % 4])).sum::<f64>()).max(1.0);
    let tolerance = (thickness * if live { 0.065 } else { 0.085 }).max(1.2);
    if residual > tolerance && (live || !sustained_sides(&component.boundary, p, tolerance)) {
        return None;
    }
    let fill = component.pixels.len() as f64 / area(&p);
    if !(0.76..=1.16).contains(&fill) {
        return None;
    }
    Some((
        purity
            * captured
            * (1.0 - 0.15 * (residual / tolerance).min(1.0))
            * (component.pixels.len() as f64 / map.values.len() as f64).sqrt(),
        residual > tolerance,
    ))
}

fn sustained_sides(boundary: &[Point], p: [Point; 4], tolerance: f64) -> bool {
    let lines = std::array::from_fn::<_, 4, _>(|side| Line::through(p[side], p[(side + 1) % 4]));
    let mut straight_sides = 0;
    for side in 0..4 {
        let a = p[side];
        let b = p[(side + 1) % 4];
        let line = lines[side];
        let length_squared = (b.x - a.x).powi(2) + (b.y - a.y).powi(2);
        let mut bins: [Vec<f64>; 16] = std::array::from_fn(|_| Vec::new());
        for &point in boundary {
            let along =
                ((point.x - a.x) * (b.x - a.x) + (point.y - a.y) * (b.y - a.y)) / length_squared;
            let residual = line.residual(point).abs();
            if (0.0..1.0).contains(&along)
                && lines
                    .iter()
                    .all(|other| residual <= other.residual(point).abs())
            {
                bins[(along * 16.0) as usize].push(residual);
            }
        }
        let mut touched = 0;
        let mut straight = 0;
        for mut bin in bins {
            if bin.is_empty() {
                continue;
            }
            bin.sort_by(f64::total_cmp);
            touched += usize::from(bin[0] <= tolerance);
            straight += usize::from(bin[bin.len() / 2] <= tolerance);
        }
        if touched < 12 {
            return false;
        }
        straight_sides += usize::from(straight >= 12);
    }
    straight_sides >= 3
}

fn supporting_intersections(hull: &[Point], indices: [usize; 4]) -> Option<[Point; 4]> {
    let edges = indices.map(|i| [hull[i], hull[(i + 1) % hull.len()]]);
    let lines = edges.map(|[a, b]| Line::through(a, b));
    let mut p = [Point { x: 0.0, y: 0.0 }; 4];
    for i in 0..4 {
        p[i] = lines[(i + 3) % 4].intersection(lines[i])?;
    }
    let hull_area = (0..hull.len())
        .map(|i| {
            let a = hull[i];
            let b = hull[(i + 1) % hull.len()];
            a.x * b.y - a.y * b.x
        })
        .sum::<f64>()
        * 0.5;
    if area(&p) <= 0.0 || hull_area / area(&p) < 0.90 {
        return None;
    }
    let mut missing_corners = 0;
    for i in 0..4 {
        let next = (i + 1) % 4;
        let length = distance(p[i], p[next]);
        if distance(edges[i][0], edges[i][1]) < length * 0.60 {
            return None;
        }
        let missing_area = cross(edges[(i + 3) % 4][1], p[i], edges[i][0]).abs() * 0.5;
        if missing_area > area(&p) * 0.01 {
            missing_corners += 1;
        }
    }
    (missing_corners <= 1).then_some(p)
}

pub(super) fn locate(map: &ProbabilityMap, frame: SourceExtent, budget: SearchBudget) -> Detection {
    let detection = locate_with_boundaries(map, frame, budget, false);
    if detection.quad.is_some() || matches!(budget, SearchBudget::Live) {
        detection
    } else {
        locate_with_boundaries(map, frame, budget, true)
    }
}

fn locate_with_boundaries(
    map: &ProbabilityMap,
    frame: SourceExtent,
    budget: SearchBudget,
    outer_only: bool,
) -> Detection {
    let live = matches!(budget, SearchBudget::Live);
    let extent = SourceExtent {
        width: map.width as f64,
        height: map.height as f64,
    };
    let mut best = Detection {
        quad: None,
        confidence: 0.0,
        reason: "insufficient supported page boundary",
    };
    let cutoffs: &[f32] = if live { &[0.5] } else { &[0.5, 0.35, 0.7] };
    let component_groups = cutoffs
        .iter()
        .map(|&cutoff| components(map, cutoff, if live { 2 } else { 4 }, outer_only))
        .collect::<Vec<_>>();
    let largest = component_groups
        .iter()
        .flatten()
        .map(|c| c.pixels.len())
        .max()
        .unwrap_or(0);
    for group in component_groups {
        for component in group {
            if component.pixels.len() * 2 < largest {
                continue;
            }
            let boundary_source: Vec<_> = component
                .boundary
                .iter()
                .map(|p| Point {
                    x: p.x * frame.width / extent.width,
                    y: p.y * frame.height / extent.height,
                })
                .collect();
            let hull_source = convex_hull(boundary_source);
            if hull_source.len() < 4 {
                continue;
            }
            let supporting_hull = simplify(hull_source.clone(), 6)
                .into_iter()
                .map(|p| Point {
                    x: p.x * extent.width / frame.width,
                    y: p.y * extent.height / frame.height,
                })
                .collect::<Vec<_>>();
            let simplified = simplify(hull_source, if live { 4 } else { 6 });
            let mut candidates = Vec::new();
            for a in 0..simplified.len() - 3 {
                for b in a + 1..simplified.len() - 2 {
                    for c in b + 1..simplified.len() - 1 {
                        for d in c + 1..simplified.len() {
                            let candidate =
                                [simplified[a], simplified[b], simplified[c], simplified[d]].map(
                                    |p| Point {
                                        x: p.x * extent.width / frame.width,
                                        y: p.y * extent.height / frame.height,
                                    },
                                );
                            candidates.push(candidate);
                        }
                    }
                }
            }
            if supporting_hull.len() > 4 {
                for a in 0..supporting_hull.len() - 3 {
                    for b in a + 1..supporting_hull.len() - 2 {
                        for c in b + 1..supporting_hull.len() - 1 {
                            for d in c + 1..supporting_hull.len() {
                                if let Some(candidate) =
                                    supporting_intersections(&supporting_hull, [a, b, c, d])
                                {
                                    candidates.push(candidate);
                                }
                            }
                        }
                    }
                }
            }
            for candidate in candidates {
                let Some(candidate) = supported_fit(candidate, &component.boundary, extent) else {
                    continue;
                };
                let quad = canonical(candidate, extent);
                let Some((confidence, needs_complete_source_support)) =
                    evidence(map, &component, points(quad), live)
                else {
                    continue;
                };
                let needs_complete_source_support = needs_complete_source_support || outer_only;
                if best.quad.is_none_or(|current| {
                    if current.needs_complete_source_support != needs_complete_source_support {
                        !needs_complete_source_support
                    } else {
                        confidence > best.confidence
                    }
                }) {
                    best = Detection {
                        quad: Some(MaskQuad {
                            corners: quad,
                            needs_complete_source_support,
                            extent,
                        }),
                        confidence,
                        reason: "four supported sides",
                    };
                }
            }
        }
    }
    best
}

fn brightness(source: &ImageU8, x: f64, y: f64) -> Option<f64> {
    if x < 0.0 || y < 0.0 || x >= source.width as f64 || y >= source.height as f64 {
        return None;
    }
    let offset = ((y as usize) * source.width as usize + x as usize) * 3;
    Some(
        (source.data[offset] as f64
            + 2.0 * source.data[offset + 1] as f64
            + source.data[offset + 2] as f64)
            / 4.0,
    )
}

struct ColorEdgeScores {
    values: [[f64; 91]; 48],
    supported: [bool; 48],
}

impl ColorEdgeScores {
    fn supported_positions(&self) -> usize {
        self.supported
            .iter()
            .filter(|&&supported| supported)
            .count()
    }
}

fn color_edge_scores(source: &ImageU8, edge: [Point; 2], band: f64) -> ColorEdgeScores {
    let line = Line::through(edge[0], edge[1]);
    let sample = |x: f64, y: f64| -> Option<[f64; 3]> {
        if x < 0.0 || y < 0.0 || x >= source.width as f64 || y >= source.height as f64 {
            return None;
        }
        let offset = ((y as usize) * source.width as usize + x as usize) * 3;
        Some(std::array::from_fn(|channel| {
            source.data[offset + channel] as f64
        }))
    };
    let mut supported = [false; 48];
    let values = std::array::from_fn(|i| {
        let t = (i as f64 + 1.0) / 49.0;
        let center = Point {
            x: edge[0].x + (edge[1].x - edge[0].x) * t,
            y: edge[0].y + (edge[1].y - edge[0].y) * t,
        };
        std::array::from_fn(|step| {
            let offset = (step as f64 - 45.0) * band / 30.0;
            let Some(a) = sample(
                center.x + line.nx * (offset - 1.25),
                center.y + line.ny * (offset - 1.25),
            ) else {
                return 0.0;
            };
            let Some(b) = sample(
                center.x + line.nx * (offset + 1.25),
                center.y + line.ny * (offset + 1.25),
            ) else {
                return 0.0;
            };
            let delta = std::array::from_fn::<_, 3, _>(|i| a[i] - b[i]);
            let dot =
                |a: [f64; 3], b: [f64; 3]| (a[0] * b[0] + 2.0 * a[1] * b[1] + a[2] * b[2]) / 4.0;
            let energy = dot(delta, delta);
            let penalty = 1.0 + 0.25 * (offset / band).powi(2);
            if energy < 9.0 {
                return 0.0;
            }
            let Some(inner) = sample(
                center.x + line.nx * (offset - 0.5),
                center.y + line.ny * (offset - 0.5),
            ) else {
                return 0.0;
            };
            let Some(outer) = sample(
                center.x + line.nx * (offset + 0.5),
                center.y + line.ny * (offset + 0.5),
            ) else {
                return 0.0;
            };
            let fine = std::array::from_fn::<_, 3, _>(|i| inner[i] - outer[i]);
            let wide = [2.5, 4.0, 6.0].map(|reach| {
                let a = sample(
                    center.x + line.nx * (offset - reach),
                    center.y + line.ny * (offset - reach),
                )?;
                let b = sample(
                    center.x + line.nx * (offset + reach),
                    center.y + line.ny * (offset + reach),
                )?;
                Some(std::array::from_fn::<_, 3, _>(|i| a[i] - b[i]))
            });
            let [Some(a), Some(b), Some(c)] = wide else {
                return 0.0;
            };
            let agrees = |wide: [f64; 3], minimum: f64| {
                let wide_energy = dot(wide, wide);
                wide_energy >= minimum && dot(delta, wide) >= 0.7 * (energy * wide_energy).sqrt()
            };
            if (15..76).contains(&step)
                && energy >= (6.0 * penalty).powi(2)
                && [a, b, c].into_iter().all(|wide| agrees(wide, 36.0))
            {
                supported[i] = true;
            }
            if [a, b].into_iter().all(|wide| agrees(wide, 9.0)) {
                (1.0 + dot(fine, fine).sqrt()) / penalty
            } else {
                0.0
            }
        })
    });
    ColorEdgeScores { values, supported }
}

fn refine_color_edges(
    p: [Point; 4],
    scores: &[ColorEdgeScores; 4],
    band: f64,
) -> Option<[Point; 4]> {
    let mut lines = std::array::from_fn::<_, 4, _>(|i| Line::through(p[i], p[(i + 1) % 4]));
    for i in 0..4 {
        let available = scores[i].supported_positions();
        if available < 32 {
            return None;
        }
        let mut best = None;
        let mut best_score = 0.0;
        for start in 0..91 {
            for end in 0..91 {
                let mut supported = 0;
                let mut strength = 0.0;
                let mut weighted_support = 0.0;
                for (position, row) in scores[i].values.iter().enumerate() {
                    let t = (position as f64 + 1.0) / 49.0;
                    let offset = (start as f64 * (1.0 - t) + end as f64 * t).round() as usize;
                    let score = row[offset];
                    supported += usize::from(score > 0.0);
                    strength += score / (score + 16.0);
                    if score > 0.0 {
                        weighted_support +=
                            (1.0 + 0.25 * ((offset as f64 - 45.0) / 30.0).powi(2)).recip();
                    }
                }
                let score = weighted_support + strength * 0.1;
                if supported >= 32 && supported * 5 >= available * 4 && score > best_score {
                    best_score = score;
                    best = Some((start, end));
                }
            }
        }
        let (start, end) = best?;
        let mut samples = Vec::new();
        for (position, row) in scores[i].values.iter().enumerate() {
            let t = (position as f64 + 1.0) / 49.0;
            let index = (start as f64 * (1.0 - t) + end as f64 * t).round() as usize;
            if row[index] == 0.0 {
                continue;
            }
            let offset = (index as f64 - 45.0) * band / 30.0;
            samples.push(Point {
                x: p[i].x + (p[(i + 1) % 4].x - p[i].x) * t + lines[i].nx * offset,
                y: p[i].y + (p[(i + 1) % 4].y - p[i].y) * t + lines[i].ny * offset,
            });
        }
        if samples.len() < 32 {
            return None;
        }
        lines[i] = fit_line(&samples, lines[i], band);
    }
    let mut refined = p;
    for i in 0..4 {
        refined[i] = lines[(i + 3) % 4].intersection(lines[i])?;
        if distance(refined[i], p[i]) > band * 1.5 {
            return None;
        }
    }
    Some(refined)
}

fn source_color(source: &ImageU8, x: f64, y: f64) -> Option<[u8; 3]> {
    if x < 0.0 || y < 0.0 || x >= source.width as f64 || y >= source.height as f64 {
        return None;
    }
    let index = (y as usize * source.width as usize + x as usize) * 3;
    Some([
        source.data[index],
        source.data[index + 1],
        source.data[index + 2],
    ])
}

fn printed_band_color(source: &ImageU8, p: [Point; 4], side: usize, band: f64) -> Option<[u8; 3]> {
    let a = p[side];
    let b = p[(side + 1) % 4];
    let line = Line::through(a, b);
    let reach =
        (band * 12.0).min(distance(a, p[(side + 3) % 4]).min(distance(b, p[(side + 2) % 4])) / 4.0);
    let mut profile = [[0_u8; 3]; 14];
    for (index, profile_color) in profile.iter_mut().enumerate() {
        let depth = index as i32 - 1;
        let offset = if depth < 0 {
            band
        } else {
            -(depth as f64) * reach / 12.0
        };
        let mut colors = [[0_u8; 3]; 16];
        for (i, color) in colors.iter_mut().enumerate() {
            let t = 0.2 + 0.6 * i as f64 / 15.0;
            let x = a.x + (b.x - a.x) * t + line.nx * offset;
            let y = a.y + (b.y - a.y) * t + line.ny * offset;
            *color = source_color(source, x, y)?;
        }
        *profile_color = std::array::from_fn(|channel| {
            let mut values = colors.map(|color| color[channel]);
            values.sort_unstable();
            values[8]
        });
    }
    (0..3)
        .any(|channel| {
            let change = profile[0][channel].abs_diff(profile[13][channel]);
            change >= 32
                && profile.windows(2).any(|pair| {
                    let step = pair[0][channel].abs_diff(pair[1][channel]);
                    step >= 24 && step as u16 * 2 >= change as u16
                })
        })
        .then_some(profile[0])
}

fn edge_continues_beyond_content(
    source: &ImageU8,
    corner: Point,
    neighbor: Point,
    band: f64,
    outside_sign: f64,
    content: [u8; 3],
) -> bool {
    let length = distance(corner, neighbor);
    let beyond = |amount: f64| Point {
        x: corner.x + (corner.x - neighbor.x) * amount / length,
        y: corner.y + (corner.y - neighbor.y) * amount / length,
    };
    let edge = [beyond(band), beyond(band * 3.0)];
    let line = Line::through(edge[0], edge[1]);
    let scores = color_edge_scores(source, edge, band / 2.0);
    (0..91).any(|step| {
        if scores.values.iter().filter(|row| row[step] >= 4.0).count() < 40 {
            return false;
        }
        let offset = (step as f64 - 45.0) * band / 60.0;
        let mut background = [[0_u8; 3]; 16];
        for (i, color) in background.iter_mut().enumerate() {
            let center = beyond(band * (1.0 + 2.0 * i as f64 / 15.0));
            let x = center.x + line.nx * (offset + outside_sign * band);
            let y = center.y + line.ny * (offset + outside_sign * band);
            let Some(value) = source_color(source, x, y) else {
                return false;
            };
            *color = value;
        }
        if !(0..3).any(|channel| {
            let mut values = background.map(|color| color[channel]);
            values.sort_unstable();
            let reference = values[8];
            let mut deviations = values.map(|value| value.abs_diff(reference));
            deviations.sort_unstable();
            let difference = content[channel].abs_diff(reference);
            difference >= 24 && difference as u16 > 3 * deviations[8] as u16
        }) {
            return false;
        }
        let mut deltas = [[0.0; 3]; 48];
        for (i, delta) in deltas.iter_mut().enumerate() {
            let center = beyond(band * (1.0 + 2.0 * (i as f64 + 1.0) / 49.0));
            let sample = |offset: f64| {
                source_color(
                    source,
                    center.x + line.nx * offset,
                    center.y + line.ny * offset,
                )
            };
            let (Some(a), Some(b)) = (sample(offset - 1.25), sample(offset + 1.25)) else {
                return false;
            };
            *delta = std::array::from_fn(|channel| a[channel] as f64 - b[channel] as f64);
        }
        let reference = std::array::from_fn(|channel| {
            let mut values = deltas.map(|delta| delta[channel]);
            values.sort_by(f64::total_cmp);
            values[24]
        });
        let dot = |a: [f64; 3], b: [f64; 3]| a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
        (0..48)
            .filter(|&i| {
                scores.values[i][step] >= 4.0
                    && dot(deltas[i], reference)
                        > 0.9 * (dot(deltas[i], deltas[i]) * dot(reference, reference)).sqrt()
            })
            .count()
            >= 40
    })
}

fn cuts_printed_content(source: &ImageU8, p: [Point; 4], band: f64) -> bool {
    let support = |edge: [Point; 2]| {
        color_edge_scores(source, edge, band / 2.0)
            .values
            .iter()
            .filter(|row| row.iter().any(|&score| score >= 4.0))
            .count()
    };
    (0..4).any(|side| {
        let Some(content) = printed_band_color(source, p, side, band) else {
            return false;
        };
        let first =
            edge_continues_beyond_content(source, p[side], p[(side + 3) % 4], band, 1.0, content);
        let second = edge_continues_beyond_content(
            source,
            p[(side + 1) % 4],
            p[(side + 2) % 4],
            band,
            -1.0,
            content,
        );
        (first && second) || ((first || second) && support([p[side], p[(side + 1) % 4]]) < 32)
    })
}

pub(super) fn refine_capture(
    source: &ImageU8,
    quad: Quad,
    needs_complete_support: bool,
) -> OpResult<Option<Quad>> {
    refine_capture_with_support(source, quad, needs_complete_support, 3)
}

pub(super) fn refine_capture_region(source: &ImageU8, quad: Quad) -> OpResult<Quad> {
    Ok(refine_capture_with_support(source, quad, false, 4)?.unwrap_or(quad))
}

fn refine_capture_with_support(
    source: &ImageU8,
    quad: Quad,
    needs_complete_support: bool,
    minimum_supported_sides: usize,
) -> OpResult<Option<Quad>> {
    let extent = SourceExtent::new(source.width, source.height)?;
    validate_quad(quad, extent)?;
    let scale = (640.0 / extent.width.max(extent.height)).min(1.0);
    let preview = crate::cv::resize_u8(
        source,
        (extent.width * scale).round().max(1.0) as i32,
        (extent.height * scale).round().max(1.0) as i32,
        crate::cv::Interp::Area,
    )?;
    let sx = preview.width as f64 / extent.width;
    let sy = preview.height as f64 / extent.height;
    let p = points(quad).map(|p| Point {
        x: p.x * sx,
        y: p.y * sy,
    });
    let band = (preview.width.min(preview.height) as f64 * 0.008).clamp(1.5, 5.0);
    let retain_content = |candidate: [Point; 4], source_quad: Quad| {
        if cuts_printed_content(&preview, candidate, band) {
            None
        } else {
            Some(source_quad)
        }
    };
    let mut lines = std::array::from_fn::<_, 4, _>(|i| Line::through(p[i], p[(i + 1) % 4]));
    let mut improved = 0;
    let mut supported = 0;
    for side in 0..4 {
        let line = lines[side];
        let edge_points = [p[side], p[(side + 1) % 4]];
        let border = edge_points.iter().all(|p| p.x.abs() < 1.0)
            || edge_points
                .iter()
                .all(|p| (p.x - preview.width as f64).abs() < 1.0)
            || edge_points.iter().all(|p| p.y.abs() < 1.0)
            || edge_points
                .iter()
                .all(|p| (p.y - preview.height as f64).abs() < 1.0);
        if border {
            supported += 1;
            continue;
        }
        let mut samples = Vec::new();
        let mut before = 0.0;
        let mut after = 0.0;
        for i in 0..48 {
            let t = (i as f64 + 1.0) / 49.0;
            let center = Point {
                x: p[side].x + (p[(side + 1) % 4].x - p[side].x) * t,
                y: p[side].y + (p[(side + 1) % 4].y - p[side].y) * t,
            };
            let gradient = |offset: f64| -> Option<f64> {
                let a = brightness(
                    &preview,
                    center.x + line.nx * (offset - 1.25),
                    center.y + line.ny * (offset - 1.25),
                )?;
                let b = brightness(
                    &preview,
                    center.x + line.nx * (offset + 1.25),
                    center.y + line.ny * (offset + 1.25),
                )?;
                Some((a - b).abs())
            };
            let mut strongest = gradient(0.0).unwrap_or(0.0);
            let base = strongest;
            let mut offset = 0.0;
            for step in -10..=10 {
                let candidate = step as f64 * band / 10.0;
                if let Some(value) = gradient(candidate) {
                    let penalized = value / (1.0 + 0.25 * (candidate / band).powi(2));
                    if penalized > strongest {
                        strongest = penalized;
                        offset = candidate;
                    }
                }
            }
            if strongest >= 6.0 {
                samples.push(Point {
                    x: center.x + line.nx * offset,
                    y: center.y + line.ny * offset,
                });
                before += base;
                after += strongest;
            }
        }
        if samples.len() < 32 {
            continue;
        }
        supported += 1;
        let fitted = fit_line(&samples, line, 0.75);
        if samples
            .iter()
            .filter(|&&p| fitted.residual(p).abs() < 1.0)
            .count()
            * 5
            < samples.len() * 4
        {
            continue;
        }
        if after <= before * 1.15 {
            continue;
        }
        lines[side] = fitted;
        improved += 1;
    }
    let color_samples = std::array::from_fn::<_, 4, _>(|side| {
        color_edge_scores(&preview, [p[side], p[(side + 1) % 4]], band * 3.0)
    });
    if (supported < minimum_supported_sides || needs_complete_support)
        && color_samples
            .iter()
            .any(|samples| samples.supported_positions() < 32)
    {
        return Ok(None);
    }
    if let Some(refined) = refine_color_edges(p, &color_samples, band * 3.0) {
        let source_refined = quad_from_points(refined.map(|p| Point {
            x: p.x / sx,
            y: p.y / sy,
        }));
        if validate_quad(source_refined, extent).is_ok() {
            return Ok(retain_content(refined, source_refined));
        }
    }
    if improved == 0 {
        return Ok(retain_content(p, quad));
    }
    let mut refined = p;
    for i in 0..4 {
        let Some(point) = lines[(i + 3) % 4].intersection(lines[i]) else {
            return Ok(retain_content(p, quad));
        };
        if distance(point, p[i]) > band * 1.5 {
            return Ok(retain_content(p, quad));
        }
        refined[i] = point;
    }
    let source_refined = quad_from_points(refined.map(|p| Point {
        x: p.x / sx,
        y: p.y / sy,
    }));
    if validate_quad(source_refined, extent).is_err() {
        return Ok(retain_content(p, quad));
    }
    Ok(retain_content(refined, source_refined))
}

#[cfg(test)]
mod tests {
    use super::*;

    fn polygon_mask<const N: usize>(p: [Point; N]) -> OpResult<ProbabilityMap> {
        let mut values = Vec::new();
        for y in 0..256 {
            for x in 0..256 {
                let mut covered = 0;
                for dy in [0.125, 0.375, 0.625, 0.875] {
                    for dx in [0.125, 0.375, 0.625, 0.875] {
                        let q = Point {
                            x: x as f64 + dx,
                            y: y as f64 + dy,
                        };
                        if (0..N).all(|i| cross(p[i], p[(i + 1) % N], q) >= 0.0) {
                            covered += 1;
                        }
                    }
                }
                values.push(0.02 + 0.96 * covered as f32 / 16.0);
            }
        }
        ProbabilityMap::new(values, 256, 256)
    }

    #[test]
    fn enclosed_mask_hole_does_not_hide_a_partially_obscured_page() -> OpResult<()> {
        let p = [(40.0, 75.0), (220.0, 75.0), (220.0, 190.0), (40.0, 190.0)]
            .map(|(x, y)| Point { x, y });
        for hole in [false, true] {
            let mut mask = polygon_mask(p)?;
            for y in 177..190 {
                for x in 100..180 {
                    mask.values[y * 256 + x] = 0.02;
                }
            }
            if hole {
                for y in 82..92 {
                    for x in 116..160 {
                        mask.values[y * 256 + x] = 0.02;
                    }
                }
            }
            let quad = locate(&mask, SourceExtent::new(2304, 4096)?, SearchBudget::Capture)
                .quad
                .ok_or(format!("page rejected with enclosed hole: {hole}"))?;
            for (actual, expected) in points(quad.corners).into_iter().zip(p) {
                assert!(distance(actual, expected) < 2.0);
            }
            if hole {
                assert!(quad.needs_complete_source_support);
                let mut source = ImageU8::new(256, 256, 3, vec![30; 256 * 256 * 3])?;
                for y in 20..190 {
                    for x in 40..220 {
                        source.data[(y * 256 + x) * 3..(y * 256 + x + 1) * 3].fill(230);
                    }
                }
                assert!(refine_capture(&source, quad.corners, false)?.is_some());
                assert!(refine_capture(&source, quad.corners, true)?.is_none());
            }
        }
        Ok(())
    }

    #[test]
    fn outer_boundaries_keep_open_and_diagonal_channels() -> OpResult<()> {
        let mut values = vec![0.02; 100];
        for y in 1..9 {
            for x in 1..9 {
                values[y * 10 + x] = 0.98;
            }
        }
        for y in 3..7 {
            for x in 3..7 {
                values[y * 10 + x] = 0.02;
            }
        }
        values[44] = 0.98;
        let mask = ProbabilityMap::new(values, 10, 10)?;
        let regions = background_regions(&mask, 0.5);
        assert_eq!(regions[0], 0);
        assert_ne!(regions[33], 0);
        let mut open = mask;
        for y in 0..4 {
            open.values[y * 10 + 3] = 0.02;
        }
        let regions = background_regions(&open, 0.5);
        assert_eq!(regions[33], 0);
        assert_eq!(regions[66], 0);
        open.values[13] = 0.98;
        open.values[23] = 0.98;
        open.values[11] = 0.02;
        open.values[22] = 0.02;
        assert_eq!(background_regions(&open, 0.5)[33], 0);
        Ok(())
    }

    #[test]
    fn enclosing_rectangles_do_not_override_missing_foreground() -> OpResult<()> {
        let p = [(30.0, 30.0), (226.0, 30.0), (226.0, 226.0), (30.0, 226.0)]
            .map(|(x, y)| Point { x, y });
        for island in [false, true] {
            let mut mask = polygon_mask(p)?;
            for y in 50..206 {
                for x in 50..206 {
                    mask.values[y * 256 + x] = 0.02;
                }
            }
            if island {
                for y in 100..156 {
                    for x in 100..156 {
                        mask.values[y * 256 + x] = 0.98;
                    }
                }
            }
            let before = mask.values.clone();
            let found = components(&mask, 0.5, 4, true);
            assert_eq!(mask.values, before);
            assert_eq!(found.len(), if island { 2 } else { 1 });
            assert_eq!(found[0].pixels.len(), 196 * 196 - 156 * 156);
            if island {
                assert!(!found[1].boundary.is_empty());
            }
            for budget in [SearchBudget::Live, SearchBudget::Capture] {
                assert!(
                    locate(&mask, SourceExtent::new(1200, 1600)?, budget)
                        .quad
                        .is_none()
                );
            }
        }
        Ok(())
    }

    #[test]
    fn dominant_page_inside_a_separate_foreground_ring_keeps_its_boundary() -> OpResult<()> {
        let p = [(50.0, 50.0), (206.0, 50.0), (206.0, 206.0), (50.0, 206.0)]
            .map(|(x, y)| Point { x, y });
        let mut mask = polygon_mask(p)?;
        for y in 10..246 {
            for x in 10..246 {
                if !(12..244).contains(&x) || !(12..244).contains(&y) {
                    mask.values[y * 256 + x] = 0.98;
                }
            }
        }
        for budget in [SearchBudget::Live, SearchBudget::Capture] {
            let quad = locate_with_boundaries(&mask, SourceExtent::new(1200, 1600)?, budget, true)
                .quad
                .ok_or("separate enclosing component hid the page")?;
            for (actual, expected) in points(quad.corners).into_iter().zip(p) {
                assert!(distance(actual, expected) < 2.0);
            }
        }
        Ok(())
    }

    #[test]
    fn outer_boundaries_retain_frame_edges_without_exterior_pixels() -> OpResult<()> {
        for coordinates in [
            [(0.0, 0.0), (256.0, 0.0), (256.0, 256.0), (0.0, 256.0)],
            [(30.0, 0.0), (220.0, 0.0), (220.0, 226.0), (30.0, 226.0)],
            [(0.0, 30.0), (226.0, 30.0), (226.0, 226.0), (0.0, 226.0)],
        ] {
            let p = coordinates.map(|(x, y)| Point { x, y });
            for hole in [false, true] {
                let mut mask = polygon_mask(p)?;
                if hole {
                    for y in 90..110 {
                        for x in 90..110 {
                            mask.values[y * 256 + x] = 0.02;
                        }
                    }
                }
                let found = locate_with_boundaries(
                    &mask,
                    SourceExtent::new(1200, 1600)?,
                    SearchBudget::Capture,
                    true,
                )
                .quad
                .ok_or("frame-edge page rejected")?;
                for (actual, expected) in points(found.corners).into_iter().zip(p) {
                    assert!(distance(actual, expected) < 2.0);
                }
            }
        }
        Ok(())
    }

    #[test]
    fn cut_corner_recovers_intersection_of_supporting_sides() -> OpResult<()> {
        let map = polygon_mask(
            [
                (60.0, 30.0),
                (220.0, 30.0),
                (220.0, 230.0),
                (30.0, 230.0),
                (30.0, 70.0),
            ]
            .map(|(x, y)| Point { x, y }),
        )?;
        let expected = [(30.0, 30.0), (220.0, 30.0), (220.0, 230.0), (30.0, 230.0)]
            .map(|(x, y)| Point { x, y });
        for budget in [SearchBudget::Live, SearchBudget::Capture] {
            let found = locate(&map, SourceExtent::new(1200, 1600)?, budget)
                .quad
                .ok_or("folded page rejected")?;
            for (actual, expected) in points(found.corners).into_iter().zip(expected) {
                assert!(
                    distance(actual, expected) < 2.0,
                    "{actual:?} versus {expected:?}"
                );
            }
        }
        Ok(())
    }

    fn cut_corner(p: [Point; 4], corner: usize, fraction: f64) -> [Point; 5] {
        let interpolate = |a: Point, b: Point| Point {
            x: a.x + (b.x - a.x) * fraction,
            y: a.y + (b.y - a.y) * fraction,
        };
        [
            interpolate(p[corner], p[(corner + 1) % 4]),
            p[(corner + 1) % 4],
            p[(corner + 2) % 4],
            p[(corner + 3) % 4],
            interpolate(p[corner], p[(corner + 3) % 4]),
        ]
    }

    #[test]
    fn supporting_corners_survive_rotation_perspective_and_cut_size() -> OpResult<()> {
        let extent = SourceExtent::new(256, 256)?;
        for coordinates in [
            [(60.0, 40.0), (200.0, 40.0), (200.0, 216.0), (60.0, 216.0)],
            [(61.0, 52.0), (198.0, 40.0), (213.0, 203.0), (43.0, 215.0)],
        ] {
            for angle in [0.0_f64, 0.43, 1.28] {
                let p = coordinates.map(|(x, y)| Point {
                    x: 128.0 + (x - 128.0) * angle.cos() - (y - 128.0) * angle.sin(),
                    y: 128.0 + (x - 128.0) * angle.sin() + (y - 128.0) * angle.cos(),
                });
                for corner in 0..4 {
                    for fraction in [0.08, 0.18, 0.30] {
                        let map = polygon_mask(cut_corner(p, corner, fraction))?;
                        for budget in [SearchBudget::Live, SearchBudget::Capture] {
                            let found = locate(&map, SourceExtent::new(1200, 1600)?, budget)
                                .quad
                                .ok_or_else(|| {
                                format!("rejected angle {angle}, corner {corner}, cut {fraction}")
                            })?;
                            for (actual, expected) in points(found.corners)
                                .into_iter()
                                .zip(points(canonical(p, extent)))
                            {
                                assert!(
                                    distance(actual, expected) < 2.0,
                                    "angle {angle}, corner {corner}, cut {fraction}: {actual:?} versus {expected:?}"
                                );
                            }
                        }
                    }
                }
            }
        }
        Ok(())
    }

    #[test]
    fn large_missing_corners_and_regular_polygons_are_not_completed() -> OpResult<()> {
        let p = [(35.0, 25.0), (225.0, 25.0), (225.0, 235.0), (35.0, 235.0)]
            .map(|(x, y)| Point { x, y });
        let pentagon = std::array::from_fn::<_, 5, _>(|i| {
            let angle = i as f64 * std::f64::consts::TAU / 5.0;
            Point {
                x: 128.0 + angle.cos() * 95.0,
                y: 128.0 + angle.sin() * 95.0,
            }
        });
        let octagon = std::array::from_fn::<_, 8, _>(|i| {
            let angle = i as f64 * std::f64::consts::TAU / 8.0;
            Point {
                x: 128.0 + angle.cos() * 95.0,
                y: 128.0 + angle.sin() * 95.0,
            }
        });
        for map in [
            polygon_mask(cut_corner(p, 0, 0.60))?,
            polygon_mask(pentagon)?,
            polygon_mask(octagon)?,
            polygon_mask(
                [
                    (90.0, 25.0),
                    (170.0, 25.0),
                    (225.0, 80.0),
                    (225.0, 235.0),
                    (35.0, 235.0),
                    (35.0, 80.0),
                ]
                .map(|(x, y)| Point { x, y }),
            )?,
        ] {
            for budget in [SearchBudget::Live, SearchBudget::Capture] {
                assert!(
                    locate(&map, SourceExtent::new(1200, 1600)?, budget)
                        .quad
                        .is_none()
                );
            }
        }
        Ok(())
    }

    #[test]
    fn local_corner_obstruction_preserves_the_four_main_sides() -> OpResult<()> {
        let p = [(35.0, 25.0), (225.0, 25.0), (225.0, 235.0), (35.0, 235.0)]
            .map(|(x, y)| Point { x, y });
        let mut map = polygon_mask(p)?;
        for y in 25..65 {
            for x in 35..75 {
                map.values[y * 256 + x] = 0.02;
            }
        }
        for budget in [SearchBudget::Live, SearchBudget::Capture] {
            let found = locate(&map, SourceExtent::new(1200, 1600)?, budget)
                .quad
                .ok_or("obscured page rejected")?;
            for (actual, expected) in points(found.corners).into_iter().zip(p) {
                assert!(distance(actual, expected) < 2.0);
            }
        }
        Ok(())
    }

    #[test]
    fn completed_corner_still_requires_source_page_edges() -> OpResult<()> {
        let p = [(35.0, 25.0), (225.0, 25.0), (225.0, 235.0), (35.0, 235.0)]
            .map(|(x, y)| Point { x, y });
        let map = polygon_mask(cut_corner(p, 0, 0.25))?;
        let quad = locate(&map, SourceExtent::new(256, 256)?, SearchBudget::Capture)
            .quad
            .ok_or("cut page rejected")?
            .corners;
        let data = map
            .values
            .iter()
            .flat_map(|v| [if *v > 0.5 { 230 } else { 50 }; 3])
            .collect();
        let source = ImageU8::new(256, 256, 3, data)?;
        let refined =
            refine_capture(&source, quad, false)?.ok_or("visible supporting edges rejected")?;
        for (actual, expected) in points(refined).into_iter().zip(p) {
            assert!(distance(actual, expected) < 2.0);
        }
        let unsupported = ImageU8::new(256, 256, 3, vec![230; 256 * 256 * 3])?;
        assert!(refine_capture(&unsupported, quad, false)?.is_none());
        Ok(())
    }

    #[test]
    fn independent_convex_page_fixtures_recover_all_corners() -> OpResult<()> {
        let cases = [
            [(30.0, 20.0), (225.0, 20.0), (225.0, 235.0), (30.0, 235.0)],
            [(63.0, 40.0), (216.0, 17.0), (234.0, 212.0), (20.0, 238.0)],
            [(100.0, 8.0), (153.0, 14.0), (159.0, 240.0), (90.0, 246.0)],
            [(0.0, 20.0), (228.0, 30.0), (223.0, 238.0), (0.0, 246.0)],
            [(0.0, 0.0), (256.0, 0.0), (256.0, 256.0), (0.0, 256.0)],
        ];
        for coordinates in cases {
            let p = coordinates.map(|(x, y)| Point { x, y });
            let map = polygon_mask(p)?;
            for budget in [SearchBudget::Live, SearchBudget::Capture] {
                let found = locate(&map, SourceExtent::new(1200, 800)?, budget)
                    .quad
                    .ok_or("page rejected")?;
                for (actual, expected) in points(found.corners).into_iter().zip(p) {
                    assert!(
                        distance(actual, expected) < 2.0,
                        "{actual:?} versus {expected:?}"
                    );
                }
            }
        }
        Ok(())
    }

    #[test]
    fn noise_and_round_objects_do_not_become_pages() -> OpResult<()> {
        for round in [false, true] {
            let values = (0..256 * 256)
                .map(|i| {
                    let x = (i % 256) as f64 - 128.0;
                    let y = (i / 256) as f64 - 128.0;
                    if round && x * x + y * y < 90.0 * 90.0 {
                        0.98
                    } else if !round && i % 113 == 0 {
                        0.9
                    } else {
                        0.04
                    }
                })
                .collect();
            let map = ProbabilityMap::new(values, 256, 256)?;
            assert!(
                locate(&map, SourceExtent::new(1200, 800)?, SearchBudget::Capture)
                    .quad
                    .is_none()
            );
        }
        Ok(())
    }

    #[test]
    fn separate_components_are_not_enclosed_together() -> OpResult<()> {
        let mut map = polygon_mask(
            [(12.0, 40.0), (100.0, 40.0), (100.0, 220.0), (12.0, 220.0)]
                .map(|(x, y)| Point { x, y }),
        )?;
        for y in 70..180 {
            for x in 150..240 {
                map.values[y * 256 + x] = 0.98;
            }
        }
        for budget in [SearchBudget::Live, SearchBudget::Capture] {
            let found = locate(&map, SourceExtent::new(1200, 800)?, budget)
                .quad
                .ok_or("page rejected")?;
            assert!(points(found.corners).iter().all(|p| p.x < 110.0));
        }
        Ok(())
    }

    #[test]
    fn unsupported_dominant_region_does_not_promote_a_small_island() -> OpResult<()> {
        for foreground in [0.65, 0.98] {
            let mut map = polygon_mask(
                [
                    (213.0, 213.0),
                    (233.0, 213.0),
                    (233.0, 233.0),
                    (213.0, 233.0),
                ]
                .map(|(x, y)| Point { x, y }),
            )?;
            for y in 0..256 {
                for x in 0..256 {
                    if (x as f64 - 100.0).hypot(y as f64 - 100.0) < 75.0 {
                        map.values[y * 256 + x] = foreground;
                    }
                }
            }
            for budget in [SearchBudget::Live, SearchBudget::Capture] {
                assert!(
                    locate(&map, SourceExtent::new(1200, 800)?, budget)
                        .quad
                        .is_none(),
                    "foreground {foreground} yielded a minor interior crop"
                );
            }
        }
        Ok(())
    }

    #[test]
    fn isolated_small_pages_and_narrow_receipts_remain_detectable() -> OpResult<()> {
        for (width, height) in [(16.0, 16.0), (16.0, 40.0), (8.0, 190.0)] {
            let p =
                [(0.0, 0.0), (width, 0.0), (width, height), (0.0, height)].map(|(x, y)| Point {
                    x: x + 100.0,
                    y: y + 30.0,
                });
            let map = polygon_mask(p)?;
            for budget in [SearchBudget::Live, SearchBudget::Capture] {
                let found = locate(&map, SourceExtent::new(1200, 800)?, budget)
                    .quad
                    .ok_or("small page rejected")?;
                for (actual, expected) in points(found.corners).into_iter().zip(p) {
                    assert!(distance(actual, expected) < 2.0);
                }
            }
        }
        Ok(())
    }

    #[test]
    fn ordinary_supported_page_precedes_an_uncertain_competing_fit() -> OpResult<()> {
        let mut map = ProbabilityMap::new(vec![0.02; 256 * 256], 256, 256)?;
        for y in 20..180 {
            for x in 15..105 {
                map.values[y * 256 + x] = 0.75;
            }
        }
        for y in 40..200 {
            for x in 145..235 {
                map.values[y * 256 + x] = 0.98;
            }
        }
        for x in (150..230).step_by(6) {
            for xx in x..x + 2 {
                for y in 40..54 {
                    map.values[y * 256 + xx] = 0.02;
                }
            }
        }
        let found = locate(&map, SourceExtent::new(256, 256)?, SearchBudget::Capture)
            .quad
            .ok_or("supported page rejected")?;
        assert!(points(found.corners).iter().all(|point| point.x < 110.0));
        assert!(!found.needs_complete_source_support);
        let extent = SourceExtent::new(256, 256)?;
        let mut source = ImageU8::new(256, 256, 3, vec![50; 256 * 256 * 3])?;
        for y in 20..180 {
            for x in 15..105 {
                source.data[(y * 256 + x) * 3..(y * 256 + x + 1) * 3].fill(220);
                map.values[y * 256 + x] = 0.02;
            }
        }
        assert!(
            refine_capture(
                &source,
                found.in_source(extent),
                found.needs_complete_source_support
            )?
            .is_some()
        );
        let uncertain = locate(&map, extent, SearchBudget::Capture)
            .quad
            .ok_or("uncertain competing candidate was not exercised")?;
        assert!(uncertain.needs_complete_source_support);
        assert!(
            refine_capture(
                &source,
                uncertain.in_source(extent),
                uncertain.needs_complete_source_support
            )?
            .is_none()
        );
        Ok(())
    }

    #[test]
    fn local_boundary_irregularities_preserve_four_sustained_page_sides() -> OpResult<()> {
        let p = [(40.0, 30.0), (220.0, 30.0), (220.0, 230.0), (40.0, 230.0)]
            .map(|(x, y)| Point { x, y });
        let mut map = polygon_mask(p)?;
        for y in (40..220).step_by(8) {
            for yy in y..y + 2 {
                for x in (40..50).chain(210..220) {
                    map.values[yy * 256 + x] = 0.02;
                }
            }
        }
        for x in (50..210).step_by(8) {
            for xx in x..x + 2 {
                for y in (30..40).chain(220..230) {
                    map.values[y * 256 + xx] = 0.02;
                }
            }
        }
        let extent = SourceExtent::new(256, 256)?;
        let found = locate(&map, extent, SearchBudget::Capture)
            .quad
            .ok_or("page with four sustained sides rejected")?;
        for (actual, expected) in points(found.corners).into_iter().zip(p) {
            assert!(distance(actual, expected) < 4.0);
        }
        let mut source = ImageU8::new(256, 256, 3, vec![50; 256 * 256 * 3])?;
        for y in 30..230 {
            for x in 40..220 {
                source.data[(y * 256 + x) * 3..(y * 256 + x + 1) * 3].fill(220);
            }
        }
        assert!(
            refine_capture(
                &source,
                found.in_source(extent),
                found.needs_complete_source_support
            )?
            .is_some()
        );
        for y in 0..31 {
            for x in 40..220 {
                source.data[(y * 256 + x) * 3..(y * 256 + x + 1) * 3].fill(if y == 30 {
                    30
                } else {
                    220
                });
            }
        }
        assert!(
            refine_capture(
                &source,
                found.in_source(extent),
                found.needs_complete_source_support
            )?
            .is_none()
        );
        Ok(())
    }

    #[test]
    fn canonical_labels_survive_nonsquare_source_scaling() -> OpResult<()> {
        let p = [(0.4, 0.02), (0.9, 0.4), (0.6, 0.95), (0.1, 0.4)].map(|(x, y)| Point { x, y });
        let a = canonical(
            p,
            SourceExtent {
                width: 1.0,
                height: 1.0,
            },
        );
        let b = canonical(
            p.map(|p| Point {
                x: p.x * 2000.0,
                y: p.y * 500.0,
            }),
            SourceExtent::new(2000, 500)?,
        );
        for (a, b) in points(a).into_iter().zip(points(b)) {
            assert!((a.x - b.x / 2000.0).abs() < 1e-12 && (a.y - b.y / 500.0).abs() < 1e-12);
        }
        Ok(())
    }

    #[test]
    fn source_refinement_follows_long_page_edge_without_jumping_to_text() -> OpResult<()> {
        let mut source = ImageU8::new(400, 300, 3, vec![50; 400 * 300 * 3])?;
        for y in 40..260 {
            for x in 60..340 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(235);
            }
        }
        for y in (55..250).step_by(12) {
            for x in 80..320 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(30);
            }
        }
        let before = quad_from_points(
            [(58.0, 38.0), (342.0, 38.0), (342.0, 262.0), (58.0, 262.0)]
                .map(|(x, y)| Point { x, y }),
        );
        let after = refine_capture(&source, before, false)?.ok_or("source boundary rejected")?;
        let expected = [(60.0, 40.0), (340.0, 40.0), (340.0, 260.0), (60.0, 260.0)]
            .map(|(x, y)| Point { x, y });
        let before_error: f64 = points(before)
            .into_iter()
            .zip(expected)
            .map(|(a, b)| distance(a, b))
            .sum();
        let after_error: f64 = points(after)
            .into_iter()
            .zip(expected)
            .map(|(a, b)| distance(a, b))
            .sum();
        assert!(
            after_error < before_error,
            "before {before_error}, after {after_error}"
        );
        Ok(())
    }
}

#[cfg(test)]
mod benchmarks {
    use super::*;
    use std::time::Instant;

    #[test]
    #[ignore = "release stage performance measurements"]
    fn detection_without_inference() -> OpResult<()> {
        let p = [(50.0, 20.0), (226.0, 48.0), (207.0, 230.0), (18.0, 210.0)]
            .map(|(x, y)| Point { x, y });
        let values = (0..256 * 256)
            .map(|i| {
                let point = Point {
                    x: (i % 256) as f64 + 0.5,
                    y: (i / 256) as f64 + 0.5,
                };
                if (0..4).all(|j| cross(p[j], p[(j + 1) % 4], point) >= 0.0) {
                    0.98
                } else {
                    0.02
                }
            })
            .collect();
        let map = ProbabilityMap::new(values, 256, 256)?;
        let extent = SourceExtent::new(4000, 3000)?;
        for (name, budget) in [
            ("live", SearchBudget::Live),
            ("capture", SearchBudget::Capture),
        ] {
            let mut times = Vec::new();
            for _ in 0..101 {
                let start = Instant::now();
                assert!(locate(&map, extent, budget).quad.is_some());
                times.push(start.elapsed().as_secs_f64() * 1000.0);
            }
            let cold = times.remove(0);
            times.sort_by(f64::total_cmp);
            println!(
                "detect {name}: cold_ms={cold:.3}, median_ms={:.3}, p95_ms={:.3}",
                times[50], times[95]
            );
        }
        Ok(())
    }
}

#[cfg(test)]
mod source_evidence_tests {
    use super::*;

    #[test]
    fn biased_header_seed_cannot_remove_printed_content() -> OpResult<()> {
        let mut source = ImageU8::new(400, 600, 3, vec![180; 400 * 600 * 3])?;
        for y in 60..540 {
            for x in 60..340 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(195);
            }
        }
        for y in 63..100 {
            for x in 65..335 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(50);
            }
        }
        let biased = quad_from_points(
            [(60.0, 88.0), (340.0, 88.0), (340.0, 540.0), (60.0, 540.0)]
                .map(|(x, y)| Point { x, y }),
        );
        if let Some(refined) = refine_capture(&source, biased, false)? {
            assert!(
                refined.top_left.y <= 65.0 && refined.top_right.y <= 65.0,
                "printed header lost: {refined:?}"
            );
        }
        Ok(())
    }

    #[test]
    fn tilted_header_seeds_preserve_content_across_rotation_and_paper_tone() -> OpResult<()> {
        for (background, paper, ink) in [
            ([180; 3], [195; 3], [50; 3]),
            ([100; 3], [60; 3], [210; 3]),
            ([180; 3], [195; 3], [35, 130, 165]),
            ([100; 3], [60; 3], [190, 80, 130]),
        ] {
            let mut source = ImageU8::new(400, 600, 3, background.repeat(400 * 600))?;
            for y in 60..540 {
                for x in 60..340 {
                    source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].copy_from_slice(&paper);
                }
            }
            for y in 63..100 {
                for x in 65..335 {
                    source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].copy_from_slice(&ink);
                }
            }
            for y in 0..600 {
                for x in 0..400 {
                    for channel in 0..3 {
                        let index = (y * 400 + x) * 3 + channel;
                        source.data[index] = (source.data[index] as i32 + x as i32 / 20 - 10) as u8;
                    }
                }
            }
            for (left, right) in [(60.0, 88.0), (88.0, 60.0)] {
                for turns in 0..4 {
                    let rotated = crate::cv::rotate_u8(&source, turns * 90)?;
                    let rotate = |(x, y)| match turns {
                        0 => Point { x, y },
                        1 => Point { x: 600.0 - y, y: x },
                        2 => Point {
                            x: 400.0 - x,
                            y: 600.0 - y,
                        },
                        _ => Point { x: y, y: 400.0 - x },
                    };
                    let biased = canonical(
                        [(60.0, left), (340.0, right), (340.0, 540.0), (60.0, 540.0)].map(rotate),
                        SourceExtent::new(rotated.width, rotated.height)?,
                    );
                    let Some(refined) = refine_capture(&rotated, biased, false)? else {
                        continue;
                    };
                    let corners = points(refined);
                    for point in
                        [(66.0, 64.0), (334.0, 64.0), (334.0, 99.0), (66.0, 99.0)].map(rotate)
                    {
                        assert!(
                            (0..4).all(|side| {
                                cross(corners[side], corners[(side + 1) % 4], point)
                                    >= -distance(corners[side], corners[(side + 1) % 4]) * 1.5
                            }),
                            "printed header lost at rotation {turns}: {refined:?}"
                        );
                    }
                }
            }
        }
        Ok(())
    }

    #[test]
    fn plain_margins_and_folded_corners_remain_usable_on_textured_backgrounds() -> OpResult<()> {
        for folded in [false, true] {
            let mut source = ImageU8::new(400, 600, 3, vec![0; 400 * 600 * 3])?;
            for y in 0..600 {
                for x in 0..400 {
                    let paper = (60..340).contains(&x)
                        && (60..540).contains(&y)
                        && (!folded || x + y >= 160);
                    let value = if paper {
                        195 + y / 15
                    } else {
                        80 + (x * 31 + y * 17) % 80
                    };
                    source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(value as u8);
                }
            }
            for turns in 0..4 {
                let rotated = crate::cv::rotate_u8(&source, turns * 90)?;
                let rotate = |(x, y)| match turns {
                    0 => Point { x, y },
                    1 => Point { x: 600.0 - y, y: x },
                    2 => Point {
                        x: 400.0 - x,
                        y: 600.0 - y,
                    },
                    _ => Point { x: y, y: 400.0 - x },
                };
                let seed = canonical(
                    [(60.0, 60.0), (340.0, 88.0), (340.0, 540.0), (60.0, 540.0)].map(rotate),
                    SourceExtent::new(rotated.width, rotated.height)?,
                );
                assert!(
                    refine_capture(&rotated, seed, false)?.is_some(),
                    "plain margin rejected: rotation {turns}, folded {folded}"
                );
            }
        }
        Ok(())
    }

    #[test]
    fn curled_printed_header_keeps_background_above_its_outer_edge() -> OpResult<()> {
        let mut source = ImageU8::new(400, 600, 3, vec![0; 400 * 600 * 3])?;
        for y in 0..600 {
            for x in 0..400 {
                let top = 82.0 - 22.0 * ((x as f64 - 200.0) / 140.0).powi(2);
                let color = if (60..340).contains(&x) && (y as f64) >= top && y < 540 {
                    if y < 112 {
                        [35, 90, 50]
                    } else {
                        [135, 200, 175]
                    }
                } else {
                    [70 + ((x * 13 + y * 7) % 24) as u8; 3]
                };
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].copy_from_slice(&color);
            }
        }
        let seed = quad_from_points(
            [(60.0, 72.0), (340.0, 72.0), (340.0, 540.0), (60.0, 540.0)]
                .map(|(x, y)| Point { x, y }),
        );
        assert!(refine_capture(&source, seed, false)?.is_some());
        Ok(())
    }

    #[test]
    fn broad_printed_panel_does_not_displace_a_supported_outer_page() -> OpResult<()> {
        let mut source = ImageU8::new(400, 300, 3, vec![180; 400 * 300 * 3])?;
        for y in 40..260 {
            for x in 60..340 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(195);
            }
        }
        for y in 45..255 {
            for x in 65..335 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(90);
            }
        }
        for y in [100, 150, 200] {
            for x in 62..65 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(30);
            }
        }
        let quad = quad_from_points(
            [(60.0, 40.0), (340.0, 40.0), (340.0, 260.0), (60.0, 260.0)]
                .map(|(x, y)| Point { x, y }),
        );
        let refined = refine_capture(&source, quad, false)?.ok_or("page rejected")?;
        for (actual, expected) in points(refined).into_iter().zip(points(quad)) {
            assert!(
                distance(actual, expected) < 2.0,
                "{actual:?} vs {expected:?}"
            );
        }
        Ok(())
    }

    #[test]
    fn sustained_chromatic_edges_refine_displaced_page_corners() -> OpResult<()> {
        let mut source = ImageU8::new(400, 300, 3, [80, 140, 200].repeat(400 * 300))?;
        let expected = [(80.0, 40.0), (315.0, 60.0), (340.0, 245.0), (60.0, 265.0)]
            .map(|(x, y)| Point { x, y });
        for y in 0..300 {
            for x in 0..400 {
                let point = Point {
                    x: x as f64,
                    y: y as f64,
                };
                if (0..4).all(|i| cross(expected[i], expected[(i + 1) % 4], point) >= 0.0) {
                    source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3]
                        .copy_from_slice(&[40, 160, 200]);
                }
            }
        }
        let displaced = quad_from_points(
            [(84.0, 45.0), (312.0, 66.0), (344.0, 250.0), (66.0, 260.0)]
                .map(|(x, y)| Point { x, y }),
        );
        let refined = refine_capture(&source, displaced, false)?.ok_or("page rejected")?;
        for (actual, expected) in points(refined).into_iter().zip(expected) {
            assert!(
                distance(actual, expected) < 2.0,
                "{actual:?} vs {expected:?}"
            );
        }
        Ok(())
    }

    #[test]
    fn color_edge_rejects_thin_strokes_without_a_background_step() -> OpResult<()> {
        let mut source = ImageU8::new(400, 300, 3, vec![220; 400 * 300 * 3])?;
        for x in 60..340 {
            source.data[(100 * 400 + x) * 3..(100 * 400 + x + 1) * 3].fill(30);
        }
        let edge = [Point { x: 60.0, y: 100.0 }, Point { x: 340.0, y: 100.0 }];
        assert!(color_edge_scores(&source, edge, 7.2).supported_positions() < 32);
        for y in 100..300 {
            for x in 0..400 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(150);
            }
        }
        assert!(color_edge_scores(&source, edge, 7.2).supported_positions() >= 32);
        Ok(())
    }

    #[test]
    fn chromatic_edges_support_pages_with_equal_luminance() -> OpResult<()> {
        let mut source = ImageU8::new(400, 300, 3, [80, 140, 200].repeat(400 * 300))?;
        for y in 40..260 {
            for x in 60..340 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3]
                    .copy_from_slice(&[200, 140, 80]);
            }
        }
        let quad = quad_from_points(
            [(60.0, 40.0), (340.0, 40.0), (340.0, 260.0), (60.0, 260.0)]
                .map(|(x, y)| Point { x, y }),
        );
        assert!(refine_capture(&source, quad, false)?.is_some());
        Ok(())
    }

    #[test]
    fn nearby_page_edges_support_a_modestly_displaced_mask() -> OpResult<()> {
        let mut source = ImageU8::new(400, 300, 3, vec![160; 400 * 300 * 3])?;
        for y in 40..260 {
            for x in 60..340 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(220);
            }
        }
        for offset in [-5.0, 5.0] {
            let quad = quad_from_points([
                Point {
                    x: 60.0 + offset,
                    y: 40.0 + offset,
                },
                Point {
                    x: 340.0 - offset,
                    y: 40.0 + offset,
                },
                Point {
                    x: 340.0 - offset,
                    y: 260.0 - offset,
                },
                Point {
                    x: 60.0 + offset,
                    y: 260.0 - offset,
                },
            ]);
            assert!(
                refine_capture(&source, quad, false)?.is_some(),
                "offset {offset}"
            );
        }
        Ok(())
    }

    #[test]
    fn visible_but_non_straight_edges_keep_the_detected_page() -> OpResult<()> {
        let mut source = ImageU8::new(400, 300, 3, vec![190; 400 * 300 * 3])?;
        for y in 0..300 {
            for x in 0..400 {
                let horizontal = (x as f64 / 12.0).sin() * 3.5;
                let vertical = (y as f64 / 12.0).sin() * 3.5;
                if x as f64 >= 60.0 + vertical
                    && (x as f64) < 340.0 + vertical
                    && y as f64 >= 40.0 + horizontal
                    && (y as f64) < 260.0 + horizontal
                {
                    source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(210);
                }
            }
        }
        let quad = quad_from_points(
            [(60.0, 40.0), (340.0, 40.0), (340.0, 260.0), (60.0, 260.0)]
                .map(|(x, y)| Point { x, y }),
        );
        assert_eq!(refine_capture(&source, quad, false)?, Some(quad));
        Ok(())
    }

    #[test]
    fn isolated_strong_edge_segments_do_not_support_an_interior_crop() -> OpResult<()> {
        let mut source = ImageU8::new(400, 300, 3, vec![235; 400 * 300 * 3])?;
        for (x0, y0, x1, y1) in [
            (130, 40, 240, 50),
            (330, 110, 340, 190),
            (130, 250, 240, 260),
            (60, 110, 70, 190),
        ] {
            for y in y0..y1 {
                for x in x0..x1 {
                    source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(35);
                }
            }
        }
        let quad = quad_from_points(
            [(60.0, 40.0), (340.0, 40.0), (340.0, 260.0), (60.0, 260.0)]
                .map(|(x, y)| Point { x, y }),
        );
        assert!(refine_capture(&source, quad, false)?.is_none());
        Ok(())
    }

    #[test]
    fn unsupported_interior_text_regions_fall_back_to_the_whole_image() -> OpResult<()> {
        let mut source = ImageU8::new(400, 300, 3, vec![235; 400 * 300 * 3])?;
        for y in (35..270).step_by(15) {
            for x in 40..360 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(35);
            }
        }
        let quad = quad_from_points(
            [(70.0, 50.0), (315.0, 65.0), (295.0, 250.0), (60.0, 240.0)]
                .map(|(x, y)| Point { x, y }),
        );
        assert!(refine_capture(&source, quad, false)?.is_none());
        Ok(())
    }

    #[test]
    fn low_contrast_pages_and_actual_image_borders_remain_supported() -> OpResult<()> {
        let mut source = ImageU8::new(400, 300, 3, vec![200; 400 * 300 * 3])?;
        for y in 40..260 {
            for x in 60..340 {
                source.data[(y * 400 + x) * 3..(y * 400 + x + 1) * 3].fill(208);
            }
        }
        let quad = quad_from_points(
            [(60.0, 40.0), (340.0, 40.0), (340.0, 260.0), (60.0, 260.0)]
                .map(|(x, y)| Point { x, y }),
        );
        assert!(refine_capture(&source, quad, false)?.is_some());
        let extent = SourceExtent::new(400, 300)?;
        assert!(refine_capture(&source, extent.full_frame(), false)?.is_some());
        Ok(())
    }
}