GitCorner

Code

ossartcraftphotocraft🌐
856f865cf98d
//! Panorama stitching for File › Automate › Photomerge and Edit › Auto-Align / Auto-Blend Layers.
//!
//! The pipeline follows M. Brown, D. G. Lowe, *Automatic Panoramic Image Stitching using
//! Invariant Features*, IJCV 2007, with classical parts throughout:
//!
//! 1. **Features**: Harris corners + steered BRIEF ([`crate::features`]).
//! 2. **Pair matching**: ratio-test matches, RANSAC homography, and Brown–Lowe's probabilistic
//!    verification (`inliers > 8 + 0.3·matches`).
//! 3. **Focal length** (for cylindrical / spherical layouts): from the pairwise homographies of
//!    a rotating camera (H. Shum, R. Szeliski, *Construction of Panoramic Image Mosaics with
//!    Global and Local Alignment*, IJCV 2000: `H = K R K⁻¹` makes the columns and rows of
//!    `K⁻¹HK` orthonormal), or from EXIF.
//! 4. **Projection + motion model** per layout: Perspective (plane, homography), Cylindrical
//!    and Spherical (keypoints mapped onto the cylinder / sphere, rigid motion there), Collage
//!    (similarity), Reposition (translation). Auto picks perspective unless the result is too
//!    stretched, then cylindrical or spherical (Photoshop's rule of thumb).
//! 5. **Chained alignment + bundle adjustment**: a maximum spanning tree over the match graph
//!    from the reference image gives initial transforms; Levenberg–Marquardt then minimises
//!    the distance between all matched points in the panorama (optionally refining one radial
//!    distortion coefficient, Photoshop's *Geometric Distortion Correction*, and the focal
//!    length of the cylinder / sphere).
//! 6. **Photometric**: gain compensation (Brown–Lowe §6) jointly with a radial vignetting model
//!    `log V(r) = a·r² + b·r⁴` shared by all images (D. Goldman, *Vignette and Exposure
//!    Calibration and Compensation*, PAMI 2010), solved by linear least squares in log space.
//! 7. **Seams**: per new image, a minimum-cost path (dynamic programming, as in seam carving:
//!    S. Avidan, A. Shamir, SIGGRAPH 2007) through its overlap with the composite on the colour
//!    difference, so seams avoid places where the images disagree (moving objects, parallax).
//! 8. **Multi-band blending**: Laplacian pyramids (P. Burt, E. Adelson, *A Multiresolution
//!    Spline with Application to Image Mosaics*, ACM TOG 1983) of each image (holes filled by
//!    push-pull so edges don't darken) weighted by the Gaussian pyramid of its seam mask.
//!
//! Everything is deterministic. Registration works on luminance in `0..=1` at a reduced scale;
//! [`Placement::scaled`] maps the result back to full resolution.

#![allow(clippy::needless_range_loop)] // index loops mirror the maths (pixels × channels)

use crate::features::{self, Descriptor, Model};
use crate::photo_util::{Normal, Rng, par_map, par_rows, solve_dense};
use crate::transform::Homography;

mod blend;

pub use blend::{BAND_BUDGET, Geometry, Photometric, RoiImage, band_bytes_bound, blend_levels, multiband, photometric, seam_labels, try_multiband_batched};
#[cfg(test)]
use blend::{band_cost, expand, push_pull, reduce};

/// Photomerge layouts.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Layout {
    Auto,
    Perspective,
    Cylindrical,
    Spherical,
    Collage,
    Reposition,
}

impl Layout {
    pub fn parse(s: &str) -> Option<Layout> {
        Some(match s {
            "auto" => Layout::Auto,
            "perspective" => Layout::Perspective,
            "cylindrical" => Layout::Cylindrical,
            "spherical" => Layout::Spherical,
            "collage" => Layout::Collage,
            "reposition" => Layout::Reposition,
            _ => return None,
        })
    }
    pub fn name(self) -> &'static str {
        match self {
            Layout::Auto => "auto",
            Layout::Perspective => "perspective",
            Layout::Cylindrical => "cylindrical",
            Layout::Spherical => "spherical",
            Layout::Collage => "collage",
            Layout::Reposition => "reposition",
        }
    }
    fn projection(self) -> Projection {
        match self {
            Layout::Cylindrical => Projection::Cylinder,
            Layout::Spherical => Projection::Sphere,
            _ => Projection::Plane,
        }
    }
    fn motion(self) -> Motion {
        match self {
            Layout::Auto | Layout::Perspective => Motion::Homography,
            Layout::Cylindrical | Layout::Spherical => Motion::Euclidean,
            Layout::Collage => Motion::Similarity,
            Layout::Reposition => Motion::Translation,
        }
    }
}

/// Surface an image is projected onto before its 2-D motion.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Projection {
    Plane,
    Cylinder,
    Sphere,
}

/// 2-D motion models in projected space.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Motion {
    Translation,
    /// Rotation + translation.
    Euclidean,
    /// Rotation, uniform scale, translation.
    Similarity,
    Homography,
}

impl Motion {
    fn min_points(self) -> usize {
        match self {
            Motion::Translation => 1,
            Motion::Euclidean | Motion::Similarity => 2,
            Motion::Homography => 4,
        }
    }
    fn n_params(self) -> usize {
        match self {
            Motion::Translation => 2,
            Motion::Euclidean => 3,
            Motion::Similarity => 4,
            Motion::Homography => 8,
        }
    }
    fn to_params(self, h: &Homography) -> Vec<f64> {
        let m = h.0.map(|v| v / h.0[8]);
        match self {
            Motion::Translation => vec![m[2], m[5]],
            Motion::Euclidean => vec![m[3].atan2(m[0]), m[2], m[5]],
            Motion::Similarity => vec![m[0], m[3], m[2], m[5]],
            Motion::Homography => m[..8].to_vec(),
        }
    }
    fn to_homography(self, p: &[f64]) -> Homography {
        match self {
            Motion::Translation => Homography([1.0, 0.0, p[0], 0.0, 1.0, p[1], 0.0, 0.0, 1.0]),
            Motion::Euclidean => {
                let (s, c) = p[0].sin_cos();
                Homography([c, -s, p[1], s, c, p[2], 0.0, 0.0, 1.0])
            }
            Motion::Similarity => Homography([p[0], -p[1], p[2], p[1], p[0], p[3], 0.0, 0.0, 1.0]),
            Motion::Homography => Homography([p[0], p[1], p[2], p[3], p[4], p[5], p[6], p[7], 1.0]),
        }
    }
}

/// Least-squares fit of `motion` mapping `src[i]` → `dst[i]`.
pub fn fit_motion(motion: Motion, src: &[[f64; 2]], dst: &[[f64; 2]]) -> Option<Homography> {
    match motion {
        Motion::Translation => features::fit(Model::Translation, src, dst),
        Motion::Similarity => features::fit(Model::Similarity, src, dst),
        Motion::Homography => features::fit(Model::Homography, src, dst),
        Motion::Euclidean => {
            let n = src.len();
            if n < 2 {
                return None;
            }
            let nf = n as f64;
            let cs = src.iter().fold([0.0, 0.0], |a, p| [a[0] + p[0] / nf, a[1] + p[1] / nf]);
            let cd = dst.iter().fold([0.0, 0.0], |a, p| [a[0] + p[0] / nf, a[1] + p[1] / nf]);
            let (mut sxx, mut sxy) = (0.0, 0.0);
            for (s, d) in src.iter().zip(dst) {
                let (a, b) = ([s[0] - cs[0], s[1] - cs[1]], [d[0] - cd[0], d[1] - cd[1]]);
                sxx += a[0] * b[0] + a[1] * b[1];
                sxy += a[0] * b[1] - a[1] * b[0];
            }
            let th = sxy.atan2(sxx);
            let (s, c) = th.sin_cos();
            Some(Homography([c, -s, cd[0] - (c * cs[0] - s * cs[1]), s, c, cd[1] - (s * cs[0] + c * cs[1]), 0.0, 0.0, 1.0]))
        }
    }
}

/// RANSAC over [`Motion`] models; returns the refit model and its inlier indices.
pub fn ransac_motion(motion: Motion, src: &[[f64; 2]], dst: &[[f64; 2]], iters: usize, threshold: f64, seed: u64) -> Option<(Homography, Vec<usize>)> {
    let k = motion.min_points();
    let n = src.len();
    if n < k {
        return None;
    }
    let mut rng = Rng(seed ^ 0x5EED_0FA1);
    let inliers_of = |h: &Homography| -> Vec<usize> {
        (0..n)
            .filter(|&i| {
                let (x, y) = h.apply(src[i][0], src[i][1]);
                x.is_finite() && (x - dst[i][0]).hypot(y - dst[i][1]) <= threshold
            })
            .collect()
    };
    let mut best: Option<(Homography, Vec<usize>)> = None;
    for _ in 0..iters.max(1) {
        let mut idx: Vec<usize> = Vec::with_capacity(k);
        if n == k {
            idx = (0..k).collect();
        }
        while idx.len() < k {
            let i = rng.below(n);
            if !idx.contains(&i) {
                idx.push(i);
            }
        }
        let (s, d): (Vec<[f64; 2]>, Vec<[f64; 2]>) = idx.iter().map(|&i| (src[i], dst[i])).unzip();
        let Some(h) = fit_motion(motion, &s, &d) else { continue };
        let inl = inliers_of(&h);
        if best.as_ref().is_none_or(|(_, b)| inl.len() > b.len()) {
            best = Some((h, inl));
        }
    }
    let (h, inl) = best?;
    if inl.len() < k {
        return None;
    }
    let (s, d): (Vec<[f64; 2]>, Vec<[f64; 2]>) = inl.iter().map(|&i| (src[i], dst[i])).unzip();
    let h2 = fit_motion(motion, &s, &d).unwrap_or(h);
    let inl2 = inliers_of(&h2);
    Some(if inl2.len() >= inl.len() { (h2, inl2) } else { (h, inl) })
}

/// Where one image lands in the panorama: image px → (undistort) → projection → 2-D motion.
#[derive(Clone, Debug, PartialEq)]
pub struct Placement {
    pub projection: Projection,
    /// Focal length in px (the projection radius).
    pub focal: f64,
    /// Projection centre in image px (the image centre).
    pub center: [f64; 2],
    /// Radial distortion `k1` on radii normalised by the focal length (0 = none).
    pub k1: f64,
    /// Projected coordinates → panorama coordinates.
    pub h: Homography,
}

impl Placement {
    /// Image px → projected coordinates (centred, in px of the focal length).
    pub fn project(&self, x: f64, y: f64) -> [f64; 2] {
        let (mut dx, mut dy) = (x - self.center[0], y - self.center[1]);
        if self.k1 != 0.0 {
            let s = 1.0 + self.k1 * (dx * dx + dy * dy) / (self.focal * self.focal);
            dx *= s;
            dy *= s;
        }
        let f = self.focal;
        match self.projection {
            Projection::Plane => [dx, dy],
            Projection::Cylinder => [f * dx.atan2(f), f * dy / dx.hypot(f)],
            Projection::Sphere => [f * dx.atan2(f), f * dy.atan2(dx.hypot(f))],
        }
    }

    /// Projected → image px (`None` outside the valid hemisphere).
    pub fn unproject(&self, a: f64, b: f64) -> Option<(f64, f64)> {
        let f = self.focal;
        let (mut dx, mut dy) = match self.projection {
            Projection::Plane => (a, b),
            Projection::Cylinder => {
                let th = a / f;
                if th.abs() >= 1.55 {
                    return None;
                }
                (f * th.tan(), b / th.cos())
            }
            Projection::Sphere => {
                let (th, ph) = (a / f, b / f);
                if th.abs() >= 1.55 || ph.abs() >= 1.55 {
                    return None;
                }
                (f * th.tan(), f * ph.tan() / th.cos())
            }
        };
        if self.k1 != 0.0 {
            // Invert r_u = r_d (1 + k1 r_d² / f²) by Newton steps on r_d.
            let ru = dx.hypot(dy);
            if ru > 1e-9 {
                let mut rd = ru;
                for _ in 0..8 {
                    let g = rd * (1.0 + self.k1 * rd * rd / (f * f)) - ru;
                    let dg = 1.0 + 3.0 * self.k1 * rd * rd / (f * f);
                    if dg.abs() < 1e-9 {
                        break;
                    }
                    rd -= g / dg;
                }
                if !(rd.is_finite() && rd > 0.0) {
                    return None;
                }
                dx *= rd / ru;
                dy *= rd / ru;
            }
        }
        Some((dx + self.center[0], dy + self.center[1]))
    }

    /// Image px → panorama px.
    pub fn forward(&self, x: f64, y: f64) -> (f64, f64) {
        let p = self.project(x, y);
        self.h.apply(p[0], p[1])
    }

    /// Panorama px → image px.
    pub fn inverse(&self, u: f64, v: f64) -> Option<(f64, f64)> {
        let inv = self.h.inverse()?;
        let m = &inv.0;
        let w = m[6] * u + m[7] * v + m[8];
        if w <= 1e-12 {
            return None;
        }
        let (a, b) = inv.apply(u, v);
        self.unproject(a, b)
    }

    /// The same placement for images `k×` larger (registration ran at `1/k` scale).
    pub fn scaled(&self, k: f64) -> Placement {
        let s = Homography([k, 0.0, 0.0, 0.0, k, 0.0, 0.0, 0.0, 1.0]);
        let si = Homography([1.0 / k, 0.0, 0.0, 0.0, 1.0 / k, 0.0, 0.0, 0.0, 1.0]);
        Placement {
            projection: self.projection,
            focal: self.focal * k,
            center: [self.center[0] * k, self.center[1] * k],
            k1: self.k1,
            h: s.mul(&self.h).mul(&si),
        }
    }

    /// Shifted in the panorama.
    pub fn translated(&self, dx: f64, dy: f64) -> Placement {
        let t = Homography([1.0, 0.0, dx, 0.0, 1.0, dy, 0.0, 0.0, 1.0]);
        Placement { h: t.mul(&self.h), ..self.clone() }
    }

    /// Bounds `[x0, y0, x1, y1]` of a `w × h` image in the panorama (sampled along its edges).
    pub fn bounds(&self, w: f64, h: f64) -> [f64; 4] {
        let mut b = [f64::MAX, f64::MAX, f64::MIN, f64::MIN];
        let n = 32;
        for i in 0..=n {
            let t = i as f64 / n as f64;
            for (x, y) in [(t * w, 0.0), (t * w, h), (0.0, t * h), (w, t * h)] {
                let (u, v) = self.forward(x, y);
                if u.is_finite() && v.is_finite() {
                    b = [b[0].min(u), b[1].min(v), b[2].max(u), b[3].max(v)];
                }
            }
        }
        b
    }
}

/// Keypoints and descriptors of one image (registration scale).
#[derive(Clone, Debug, Default)]
pub struct ImageFeatures {
    pub w: usize,
    pub h: usize,
    pub points: Vec<[f64; 2]>,
    pub desc: Vec<Descriptor>,
}

/// Detects up to `max` corners of a `w × h` luminance image and describes them.
pub fn detect(w: usize, h: usize, luma: &[f32], valid: Option<&[bool]>, max: usize) -> ImageFeatures {
    let min_dist = (w.max(h) as f32 / 70.0).clamp(3.0, 20.0);
    let corners = features::harris(w, h, luma, max, min_dist, valid);
    let desc = features::describe(w, h, luma, &corners, false);
    ImageFeatures { w, h, points: corners.iter().map(|c| [c.x as f64, c.y as f64]).collect(), desc }
}

/// One image for [`detect_many`]: `(w, h, luma, valid)`.
pub type PreparedImage = (usize, usize, Vec<f32>, Option<Vec<bool>>);

/// [`detect`] for several images `(w, h, luma, valid)` in parallel.
pub fn detect_many(imgs: &[PreparedImage], max: usize) -> Vec<ImageFeatures> {
    par_map(imgs.len(), |i| {
        let (w, h, l, v) = &imgs[i];
        detect(*w, *h, l, v.as_deref(), max)
    })
}

/// A verified image pair: point correspondences (image `a` px, image `b` px).
#[derive(Clone, Debug)]
pub struct PairMatch {
    pub a: usize,
    pub b: usize,
    pub pts_a: Vec<[f64; 2]>,
    pub pts_b: Vec<[f64; 2]>,
    /// Homography `b → a` in image px.
    pub homography: Homography,
}

/// Matches every pair and keeps those that pass RANSAC + the Brown–Lowe verification.
pub fn match_pairs(feats: &[ImageFeatures]) -> Vec<PairMatch> {
    let n = feats.len();
    let pairs: Vec<(usize, usize)> = (0..n).flat_map(|a| (a + 1..n).map(move |b| (a, b))).collect();
    let out = par_map(pairs.len(), |k| {
        let (a, b) = pairs[k];
        let (fa, fb) = (&feats[a], &feats[b]);
        if fa.points.len() < 6 || fb.points.len() < 6 {
            return None;
        }
        let m = features::match_descriptors(&fb.desc, &fa.desc, 0.8);
        if m.len() < 8 {
            return None;
        }
        let src: Vec<[f64; 2]> = m.iter().map(|&(i, _)| fb.points[i]).collect();
        let dst: Vec<[f64; 2]> = m.iter().map(|&(_, j)| fa.points[j]).collect();
        let thr = (fa.w.max(fa.h) as f64 / 300.0).clamp(1.5, 4.0);
        let (hm, inl) = ransac_motion(Motion::Homography, &src, &dst, 1200, thr, (a * 131 + b) as u64)?;
        if (inl.len() as f64) < 8.0 + 0.3 * m.len() as f64 || inl.len() < 10 {
            return None;
        }
        Some(PairMatch { a, b, pts_a: inl.iter().map(|&i| dst[i]).collect(), pts_b: inl.iter().map(|&i| src[i]).collect(), homography: hm })
    });
    out.into_iter().flatten().collect()
}

/// Focal length (px) of a rotating camera from a homography between two of its images (image
/// px, both centred at `c`), or `None` when the homography doesn't constrain it.
pub fn focal_from_homography(h: &Homography, ca: [f64; 2], cb: [f64; 2]) -> Option<f64> {
    let ta = Homography([1.0, 0.0, -ca[0], 0.0, 1.0, -ca[1], 0.0, 0.0, 1.0]);
    let tb = Homography([1.0, 0.0, cb[0], 0.0, 1.0, cb[1], 0.0, 0.0, 1.0]);
    let m = ta.mul(h).mul(&tb).0;
    let pick = |c1: (f64, f64), c2: (f64, f64)| -> Option<f64> {
        // Each candidate is (numerator, denominator) of f²; prefer the better-conditioned one.
        let ok = |(n, d): (f64, f64)| (d.abs() > 1e-12 && n / d > 0.0).then_some((n / d, d.abs()));
        match (ok(c1), ok(c2)) {
            (Some(a), Some(b)) => Some(if a.1 >= b.1 { a.0 } else { b.0 }),
            (Some(a), None) | (None, Some(a)) => Some(a.0),
            _ => None,
        }
    };
    // Columns of K⁻¹HK orthogonal and of equal norm (focal of b) …
    let f1 = pick((-(m[0] * m[1] + m[3] * m[4]), m[6] * m[7]), (m[1] * m[1] + m[4] * m[4] - m[0] * m[0] - m[3] * m[3], m[6] * m[6] - m[7] * m[7]));
    // … rows likewise (focal of a).
    let f0 = pick((-(m[2] * m[5]), m[0] * m[3] + m[1] * m[4]), (m[5] * m[5] - m[2] * m[2], m[0] * m[0] + m[1] * m[1] - m[3] * m[3] - m[4] * m[4]));
    match (f0, f1) {
        (Some(a), Some(b)) => Some((a * b).sqrt().sqrt()),
        (Some(a), None) | (None, Some(a)) => Some(a.sqrt()),
        _ => None,
    }
}

/// Options for [`align`].
#[derive(Clone, Debug)]
pub struct AlignOptions {
    pub layout: Layout,
    /// Focal length in registration px (EXIF); estimated when `None`.
    pub focal: Option<f64>,
    /// Image that stays put (`None`: the best-connected one).
    pub reference: Option<usize>,
    /// Refine a radial distortion coefficient (Geometric Distortion Correction).
    pub geometric: bool,
}

/// Result of [`align`].
#[derive(Clone, Debug)]
pub struct Alignment {
    /// The layout actually used (Auto resolved).
    pub layout: Layout,
    pub reference: usize,
    /// Per image; `None` for images that couldn't be connected.
    pub placements: Vec<Option<Placement>>,
    pub focal: f64,
    pub k1: f64,
    /// Verified pairs `(a, b, inliers)`.
    pub pairs: Vec<(usize, usize, usize)>,
    /// RMS reprojection error (px, registration scale) after bundle adjustment.
    pub rms: f64,
}

struct PairData {
    a: usize,
    b: usize,
    pa: Vec<[f64; 2]>,
    pb: Vec<[f64; 2]>,
}

fn base_placement(f: &ImageFeatures, projection: Projection, focal: f64, k1: f64) -> Placement {
    Placement { projection, focal, center: [f.w as f64 / 2.0, f.h as f64 / 2.0], k1, h: Homography::IDENTITY }
}

/// Aligns images from their features. `None` when fewer than two images connect.
pub fn align(feats: &[ImageFeatures], matches: &[PairMatch], opts: &AlignOptions) -> Option<Alignment> {
    let n = feats.len();
    if n < 2 || matches.is_empty() {
        return None;
    }
    let focal = opts.focal.filter(|f| *f > 1.0).unwrap_or_else(|| {
        let mut fs: Vec<f64> = matches
            .iter()
            .filter_map(|m| {
                let (fa, fb) = (&feats[m.a], &feats[m.b]);
                focal_from_homography(&m.homography, [fa.w as f64 / 2.0, fa.h as f64 / 2.0], [fb.w as f64 / 2.0, fb.h as f64 / 2.0])
            })
            .filter(|f| f.is_finite())
            .collect();
        let side = feats.iter().map(|f| f.w.max(f.h)).max().unwrap_or(1) as f64;
        fs.retain(|f| *f > side * 0.2 && *f < side * 20.0);
        fs.sort_by(f64::total_cmp);
        if fs.is_empty() { side } else { fs[fs.len() / 2] }
    });
    if opts.layout != Layout::Auto {
        return align_layout(feats, matches, opts, opts.layout, focal);
    }
    // Auto: perspective unless it is too stretched (Photoshop's rule of thumb), then cylindrical,
    // or spherical when the panorama is also tall.
    if let Some(a) = align_layout(feats, matches, opts, Layout::Perspective, focal)
        && !too_stretched(feats, &a)
    {
        return Some(Alignment { layout: Layout::Perspective, ..a });
    }
    let cyl = align_layout(feats, matches, opts, Layout::Cylindrical, focal)?;
    let (mut y0, mut y1) = (f64::MAX, f64::MIN);
    for (p, f) in cyl.placements.iter().zip(feats) {
        if let Some(p) = p {
            let b = p.bounds(f.w as f64, f.h as f64);
            y0 = y0.min(b[1]);
            y1 = y1.max(b[3]);
        }
    }
    if (y1 - y0) / cyl.focal > 1.4 {
        return align_layout(feats, matches, opts, Layout::Spherical, cyl.focal);
    }
    Some(cyl)
}

/// A perspective panorama is too stretched when an image grows or shrinks a lot, flips, or
/// the field of view exceeds about 110°.
fn too_stretched(feats: &[ImageFeatures], a: &Alignment) -> bool {
    let (mut x0, mut x1) = (f64::MAX, f64::MIN);
    for (p, f) in a.placements.iter().zip(feats) {
        let Some(p) = p else { continue };
        let (w, h) = (f.w as f64, f.h as f64);
        let c: Vec<(f64, f64)> = [(0.0, 0.0), (w, 0.0), (w, h), (0.0, h)].iter().map(|&(x, y)| p.forward(x, y)).collect();
        // Signed area (shoelace); orientation must be preserved.
        let area: f64 = (0..4).map(|i| c[i].0 * c[(i + 1) % 4].1 - c[(i + 1) % 4].0 * c[i].1).sum::<f64>() / 2.0;
        let ratio = area / (w * h);
        if !ratio.is_finite() || !(0.3..=3.0).contains(&ratio) {
            return true;
        }
        let m = &p.h.0;
        for &(x, y) in &[(0.0, 0.0), (w, 0.0), (w, h), (0.0, h)] {
            let q = p.project(x, y);
            if m[6] * q[0] + m[7] * q[1] + m[8] <= 0.0 {
                return true;
            }
        }
        for (u, _) in &c {
            x0 = x0.min(*u);
            x1 = x1.max(*u);
        }
    }
    // Horizontal field of view through the reference's focal length.
    let fov = 2.0 * ((x1 - x0) / 2.0 / a.focal).atan();
    fov > 110f64.to_radians()
}

fn align_layout(feats: &[ImageFeatures], matches: &[PairMatch], opts: &AlignOptions, layout: Layout, focal: f64) -> Option<Alignment> {
    let n = feats.len();
    let projection = layout.projection();
    let motion = layout.motion();
    // Pairwise motions in projected space.
    let mut pairs: Vec<PairData> = Vec::new();
    let mut edges: Vec<(usize, usize, usize, Homography)> = Vec::new();
    for m in matches {
        let (pa, pb) = (base_placement(&feats[m.a], projection, focal, 0.0), base_placement(&feats[m.b], projection, focal, 0.0));
        let qa: Vec<[f64; 2]> = m.pts_a.iter().map(|p| pa.project(p[0], p[1])).collect();
        let qb: Vec<[f64; 2]> = m.pts_b.iter().map(|p| pb.project(p[0], p[1])).collect();
        let thr = (feats[m.a].w.max(feats[m.a].h) as f64 / 250.0).clamp(2.0, 5.0);
        let Some((hm, inl)) = ransac_motion(motion, &qb, &qa, 600, thr, (m.a * 977 + m.b) as u64) else { continue };
        if inl.len() < 8 || (inl.len() as f64) < 0.5 * m.pts_a.len() as f64 {
            continue;
        }
        edges.push((m.a, m.b, inl.len(), hm));
        // Bundle adjustment uses at most 80 evenly spread inliers per pair.
        let step = inl.len().div_ceil(80).max(1);
        let sel: Vec<usize> = inl.iter().step_by(step).copied().collect();
        pairs.push(PairData { a: m.a, b: m.b, pa: sel.iter().map(|&i| m.pts_a[i]).collect(), pb: sel.iter().map(|&i| m.pts_b[i]).collect() });
    }
    if edges.is_empty() {
        return None;
    }
    let mut degree = vec![0usize; n];
    for e in &edges {
        degree[e.0] += e.2;
        degree[e.1] += e.2;
    }
    let reference = opts.reference.filter(|r| *r < n).unwrap_or_else(|| {
        // Best connected; ties go to the middle image.
        (0..n).max_by(|&i, &j| degree[i].cmp(&degree[j]).then_with(|| (j as i64 - n as i64 / 2).abs().cmp(&(i as i64 - n as i64 / 2).abs()))).unwrap_or(0)
    });
    // Maximum spanning tree (Prim) from the reference; transforms map projected → panorama.
    let mut tf: Vec<Option<Homography>> = vec![None; n];
    let rc = [feats[reference].w as f64 / 2.0, feats[reference].h as f64 / 2.0];
    tf[reference] = Some(Homography([1.0, 0.0, rc[0], 0.0, 1.0, rc[1], 0.0, 0.0, 1.0]));
    loop {
        let mut best: Option<(usize, usize, Homography)> = None;
        for e in &edges {
            // e.3 maps b → a.
            let cand = match (tf[e.0], tf[e.1]) {
                (Some(ta), None) => Some((e.1, ta.mul(&e.3))),
                (None, Some(tb)) => e.3.inverse().map(|inv| (e.0, tb.mul(&inv))),
                _ => None,
            };
            if let Some((node, t)) = cand
                && best.as_ref().is_none_or(|b| e.2 > b.1)
            {
                best = Some((node, e.2, t));
            }
        }
        let Some((node, _, t)) = best else { break };
        tf[node] = Some(t);
    }
    let placed: Vec<usize> = (0..n).filter(|&i| tf[i].is_some()).collect();
    if placed.len() < 2 {
        return None;
    }
    // Bundle adjustment (Levenberg–Marquardt, numeric Jacobian).
    let movable: Vec<usize> = placed.iter().copied().filter(|&i| i != reference).collect();
    let mp = motion.n_params();
    let refine_focal = projection != Projection::Plane;
    let n_glob = usize::from(opts.geometric) + usize::from(refine_focal);
    let mut params: Vec<f64> = movable.iter().filter_map(|&i| tf[i].as_ref()).flat_map(|t| motion.to_params(t)).collect();
    if opts.geometric {
        params.push(0.0);
    }
    if refine_focal {
        params.push(focal.ln());
    }
    let n_par = params.len();
    let decode = |p: &[f64]| -> Vec<Option<Placement>> {
        let k1 = if opts.geometric { p[movable.len() * mp] } else { 0.0 };
        let f = if refine_focal { p[n_par - 1].exp() } else { focal };
        (0..n)
            .map(|i| {
                let h = if i == reference {
                    tf[reference]?
                } else {
                    let k = movable.iter().position(|&m| m == i)?;
                    motion.to_homography(&p[k * mp..(k + 1) * mp])
                };
                Some(Placement { h, ..base_placement(&feats[i], projection, f, k1) })
            })
            .collect()
    };
    let residuals = |p: &[f64]| -> Vec<f64> {
        let pl = decode(p);
        let mut r = Vec::new();
        for pd in &pairs {
            let (Some(a), Some(b)) = (&pl[pd.a], &pl[pd.b]) else { continue };
            for (qa, qb) in pd.pa.iter().zip(&pd.pb) {
                let (ua, va) = a.forward(qa[0], qa[1]);
                let (ub, vb) = b.forward(qb[0], qb[1]);
                r.push(ua - ub);
                r.push(va - vb);
            }
        }
        // Soft priors keep the global terms sane when few pairs constrain them.
        if opts.geometric {
            r.push(p[movable.len() * mp] * 20.0);
        }
        if refine_focal {
            r.push((p[n_par - 1] - focal.ln()) * 2.0);
        }
        r
    };
    let cost = |r: &[f64]| r.iter().map(|v| v * v).sum::<f64>();
    let mut cur = residuals(&params);
    let mut lambda = 1e-3;
    if n_par > 0 && !movable.is_empty() {
        for _ in 0..40 {
            let m_res = cur.len();
            let cols: Vec<Vec<f64>> = par_map(n_par, |j| {
                let step = 1e-6 * (1.0 + params[j].abs());
                let mut pp = params.clone();
                pp[j] += step;
                let rp = residuals(&pp);
                pp[j] -= 2.0 * step;
                let rm = residuals(&pp);
                (0..m_res).map(|i| (rp[i] - rm[i]) / (2.0 * step)).collect()
            });
            let mut jtj = vec![0.0; n_par * n_par];
            let mut jtr = vec![0.0; n_par];
            for a in 0..n_par {
                jtr[a] = -cols[a].iter().zip(&cur).map(|(j, r)| j * r).sum::<f64>();
                for b in a..n_par {
                    let v: f64 = cols[a].iter().zip(&cols[b]).map(|(x, y)| x * y).sum();
                    jtj[a * n_par + b] = v;
                    jtj[b * n_par + a] = v;
                }
            }
            let mut improved = false;
            for _ in 0..8 {
                let mut a = jtj.clone();
                for d in 0..n_par {
                    a[d * n_par + d] += lambda * (jtj[d * n_par + d] + 1e-9);
                }
                let Some(delta) = solve_dense(n_par, a, jtr.clone()) else {
                    lambda *= 10.0;
                    continue;
                };
                let trial: Vec<f64> = params.iter().zip(&delta).map(|(p, d)| p + d).collect();
                let rt = residuals(&trial);
                if cost(&rt) < cost(&cur) {
                    let gain = cost(&cur) - cost(&rt);
                    params = trial;
                    cur = rt;
                    lambda = (lambda * 0.3).max(1e-9);
                    improved = gain > 1e-10 * cost(&cur).max(1e-12);
                    break;
                }
                lambda *= 10.0;
            }
            if !improved {
                break;
            }
        }
    }
    let placements = decode(&params);
    let n_res = pairs.iter().map(|p| p.pa.len()).sum::<usize>().max(1);
    let rms = (cost(&cur[..(cur.len() - n_glob).min(cur.len())]) / n_res as f64).sqrt();
    let k1 = if opts.geometric { params[movable.len() * mp] } else { 0.0 };
    let focal = if refine_focal { params[n_par - 1].exp() } else { focal };
    Some(Alignment { layout, reference, placements, focal, k1, pairs: edges.iter().map(|e| (e.0, e.1, e.2)).collect(), rms })
}

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

    /// Smooth random texture: blobs over a gradient (bounded detail so Harris finds corners).
    pub(crate) fn scene(w: usize, h: usize, seed: u64) -> Vec<f32> {
        let mut rng = Rng(seed);
        let mut img: Vec<f32> = (0..w * h).map(|i| 0.25 + 0.2 * ((i % w) as f32 / w as f32)).collect();
        for _ in 0..(w * h / 900).max(40) {
            let cx = (rng.next() % w as u64) as f64;
            let cy = (rng.next() % h as u64) as f64;
            let r = 3.0 + (rng.next() % 9) as f64;
            let v = (rng.next() % 1000) as f32 / 1000.0;
            let sq = rng.next().is_multiple_of(2);
            let (x0, x1) = ((cx - r).max(0.0) as usize, ((cx + r) as usize + 1).min(w));
            let (y0, y1) = ((cy - r).max(0.0) as usize, ((cy + r) as usize + 1).min(h));
            for y in y0..y1 {
                for x in x0..x1 {
                    let (dx, dy) = (x as f64 - cx, y as f64 - cy);
                    if if sq { dx.abs() < r && dy.abs() < r * 0.6 } else { dx.hypot(dy) < r } {
                        img[y * w + x] = v;
                    }
                }
            }
        }
        img
    }

    fn sample(img: &[f32], w: usize, h: usize, x: f64, y: f64) -> Option<f32> {
        if x < 0.0 || y < 0.0 || x > (w - 1) as f64 || y > (h - 1) as f64 {
            return None;
        }
        Some(crate::photo_util::bilinear(img, w, h, 1, 0, x as f32, y as f32))
    }

    /// Crops `tw × th` views of a scene through `map` (view px → scene px).
    fn view(scene: &[f32], sw: usize, sh: usize, tw: usize, th: usize, map: impl Fn(f64, f64) -> (f64, f64)) -> Vec<f32> {
        (0..tw * th)
            .map(|i| {
                let (x, y) = map((i % tw) as f64, (i / tw) as f64);
                sample(scene, sw, sh, x, y).unwrap_or(0.0)
            })
            .collect()
    }

    #[test]
    fn recovers_translations_and_homographies() {
        let (sw, sh) = (640, 300);
        let sc = scene(sw, sh, 3);
        let (tw, th) = (260, 220);
        // Three overlapping crops at known offsets.
        let offs = [(20.0, 30.0), (190.0, 40.0), (360.0, 25.0)];
        let imgs: Vec<Vec<f32>> = offs.iter().map(|&(ox, oy)| view(&sc, sw, sh, tw, th, |x, y| (x + ox, y + oy))).collect();
        let feats: Vec<ImageFeatures> = imgs.iter().map(|im| detect(tw, th, im, None, 700)).collect();
        let matches = match_pairs(&feats);
        assert!(matches.len() >= 2, "{}", matches.len());
        for layout in [Layout::Reposition, Layout::Collage, Layout::Perspective] {
            let a = align(&feats, &matches, &AlignOptions { layout, focal: None, reference: Some(1), geometric: false }).unwrap();
            assert_eq!(a.reference, 1);
            for (i, p) in a.placements.iter().enumerate() {
                let p = p.as_ref().unwrap();
                // A point at image px (50, 60) is scene (50+ox, 60+oy); relative to image 1.
                let (u, v) = p.forward(50.0, 60.0);
                let (eu, ev) = (50.0 + offs[i].0 - offs[1].0, 60.0 + offs[i].1 - offs[1].1);
                assert!((u - eu).abs() < 1.0 && (v - ev).abs() < 1.0, "{layout:?} image {i}: ({u},{v}) vs ({eu},{ev})");
            }
            assert!(a.rms < 1.0, "{layout:?} rms {}", a.rms);
        }
        // A projective view is recovered by the perspective layout.
        let hq = Homography([1.05, 0.03, 180.0, -0.02, 1.0, 35.0, 0.0001, -0.00005, 1.0]);
        let im2 = view(&sc, sw, sh, tw, th, |x, y| hq.apply(x, y));
        let feats2 = vec![feats[0].clone(), detect(tw, th, &im2, None, 700)];
        let m2 = match_pairs(&feats2);
        let a = align(&feats2, &m2, &AlignOptions { layout: Layout::Perspective, focal: None, reference: Some(0), geometric: false }).unwrap();
        let p = a.placements[1].as_ref().unwrap();
        // Points inside the overlap (extrapolation beyond it is loosely constrained).
        for (x, y) in [(20.0, 30.0), (70.0, 180.0), (40.0, 100.0)] {
            let (sx, sy) = hq.apply(x, y);
            let (u, v) = p.forward(x, y);
            assert!((u - (sx - 20.0)).abs() < 1.5 && (v - (sy - 30.0)).abs() < 1.5, "({u},{v}) vs ({},{})", sx - 20.0, sy - 30.0);
        }
    }

    #[test]
    fn rotating_camera_focal_and_cylindrical_layout() {
        // Views of a cylinder-mapped scene from a camera panning by 25° with f = 300 px.
        let f = 300.0f64;
        let (sw, sh) = (1400, 500);
        let sc = scene(sw, sh, 9);
        let (tw, th) = (320, 240);
        let pans = [-25f64, 0.0, 25.0];
        let imgs: Vec<Vec<f32>> = pans
            .iter()
            .map(|&deg| {
                view(&sc, sw, sh, tw, th, |x, y| {
                    let (dx, dy) = (x - tw as f64 / 2.0, y - th as f64 / 2.0);
                    let th_ = dx.atan2(f) + deg.to_radians();
                    let hh = dy / dx.hypot(f);
                    (sw as f64 / 2.0 + f * th_, sh as f64 / 2.0 + f * hh)
                })
            })
            .collect();
        let feats: Vec<ImageFeatures> = imgs.iter().map(|im| detect(tw, th, im, None, 700)).collect();
        let matches = match_pairs(&feats);
        assert_eq!(matches.iter().filter(|m| m.b == m.a + 1).count(), 2);
        let est: Vec<f64> = matches.iter().filter_map(|m| focal_from_homography(&m.homography, [160.0, 120.0], [160.0, 120.0])).collect();
        assert!(est.iter().any(|e| (e - f).abs() / f < 0.15), "focal estimates {est:?}");
        let a = align(&feats, &matches, &AlignOptions { layout: Layout::Cylindrical, focal: None, reference: Some(1), geometric: false }).unwrap();
        assert!((a.focal - f).abs() / f < 0.1, "focal {}", a.focal);
        let p = a.placements[2].as_ref().unwrap();
        // The centre of the right image sits 25° along the cylinder.
        let (u, _) = p.forward(160.0, 120.0);
        let expect = 160.0 + a.focal * 25f64.to_radians();
        assert!((u - expect).abs() < 4.0, "{u} vs {expect}");
        assert!(a.rms < 1.5, "rms {}", a.rms);
        // Round trip through the placement.
        let (u, v) = p.forward(40.0, 200.0);
        let (x, y) = p.inverse(u, v).unwrap();
        assert!((x - 40.0).abs() < 1e-6 && (y - 200.0).abs() < 1e-6);
    }

    #[test]
    fn placement_round_trips_all_projections() {
        for projection in [Projection::Plane, Projection::Cylinder, Projection::Sphere] {
            let p =
                Placement { projection, focal: 400.0, center: [200.0, 150.0], k1: 0.05, h: Homography([0.98, -0.1, 30.0, 0.1, 0.98, -12.0, 0.0, 0.0, 1.0]) };
            for (x, y) in [(0.0, 0.0), (390.0, 20.0), (123.0, 280.0)] {
                let (u, v) = p.forward(x, y);
                let (bx, by) = p.inverse(u, v).unwrap();
                assert!((bx - x).abs() < 1e-6 && (by - y).abs() < 1e-6, "{projection:?}");
            }
            let s = p.scaled(2.0);
            let (u, v) = p.forward(100.0, 50.0);
            let (u2, v2) = s.forward(200.0, 100.0);
            assert!((u2 - 2.0 * u).abs() < 1e-6 && (v2 - 2.0 * v).abs() < 1e-6);
        }
    }

    #[test]
    fn photometric_recovers_gain_and_vignette() {
        // Two half-overlapping views of a flat-ish scene: the second one 30 % brighter.
        let (w, h) = (200usize, 100usize);
        let base = |x: i32, y: i32| 0.3 + 0.2 * ((x as f32 * 0.05).sin() * (y as f32 * 0.07).cos()).abs();
        let mut imgs = Vec::new();
        let mut pls = Vec::new();
        for (k, (x0, g)) in [(0, 1.0f32), (100, 1.3f32)].into_iter().enumerate() {
            let mut px = Vec::new();
            for y in 0..h as i32 {
                for x in 0..w as i32 {
                    px.push(base(x + x0, y) * g);
                }
            }
            imgs.push(RoiImage { x0, y0: 0, w, h, ch: 1, px, alpha: vec![1.0; w * h] });
            pls.push(Placement {
                projection: Projection::Plane,
                focal: 200.0,
                center: [100.0, 50.0],
                k1: 0.0,
                h: Homography([1.0, 0.0, 100.0 + x0 as f64, 0.0, 1.0, 50.0, 0.0, 0.0, 1.0]),
            });
            let _ = k;
        }
        let ph = photometric(&imgs, Some((&pls, &[(w, h), (w, h)])), true, false);
        let ratio = ph.gains[1][0] / ph.gains[0][0];
        assert!((ratio - 1.3).abs() < 0.03, "{ph:?}");
        // With vignetting on, the flat scene (no falloff) gives a near-zero model.
        let pv = photometric(&imgs, Some((&pls, &[(w, h), (w, h)])), true, true);
        assert!(pv.vignette[0].abs() < 0.1, "{pv:?}");
    }

    #[test]
    fn an_oversized_level_count_is_clamped() {
        let (w, h) = (4, 4);
        let img = RoiImage { x0: 0, y0: 0, w, h, ch: 1, px: vec![0.5; w * h], alpha: vec![1.0; w * h] };
        let (out, cov) = multiband(w, h, &[img], &[vec![1.0; w * h]], usize::MAX).unwrap();
        assert_eq!(out.len(), w * h);
        assert!(out.iter().all(|v| (v - 0.5).abs() < 1e-5), "{out:?}");
        assert!(cov.iter().all(|c| *c == 1.0), "{cov:?}");
    }

    #[test]
    fn seams_avoid_disagreement_and_multiband_is_seamless() {
        // Two images over a 120×40 strip, overlapping in 40..80; the second has a bright
        // "moving object" at x 50..58 that the first doesn't.
        let (w, h) = (120usize, 40usize);
        let mut luma = vec![vec![0.5f32; w * h], vec![0.5f32; w * h]];
        let cover: Vec<Vec<bool>> = vec![(0..w * h).map(|i| i % w < 80).collect(), (0..w * h).map(|i| i % w >= 40).collect()];
        for y in 0..h {
            for x in 50..58 {
                luma[1][y * w + x] = 1.0;
            }
        }
        let labels = seam_labels(w, h, &luma, &cover, &[0, 1]);
        // The object column belongs to image 0 (the seam passes to its right), or entirely to 1.
        for y in 0..h {
            let owner: Vec<i32> = (50..58).map(|x| labels[y * w + x]).collect();
            assert!(owner.iter().all(|o| *o == owner[0]), "row {y} split the object: {owner:?}");
        }
        assert_eq!(labels[5], 0);
        assert_eq!(labels[w - 1], 1);
        // Multi-band blend of two flat images at different levels joins smoothly.
        let mk = |x0: i32, v: f32| RoiImage { x0, y0: 0, w: 80, h, ch: 1, px: vec![v; 80 * h], alpha: vec![1.0; 80 * h] };
        let imgs = [mk(0, 0.3), mk(40, 0.7)];
        let wts: Vec<Vec<f32>> = (0..2)
            .map(|k| {
                (0..80 * h)
                    .map(|i| {
                        let x = (i % 80) as i32 + imgs[k].x0;
                        if (x < 60) == (k == 0) { 1.0 } else { 0.0 }
                    })
                    .collect()
            })
            .collect();
        let (out, cov) = multiband(w, h, &imgs, &wts, 4).unwrap();
        let row: Vec<f32> = (0..w).map(|x| out[20 * w + x]).collect();
        assert!((row[2] - 0.3).abs() < 0.02 && (row[w - 3] - 0.7).abs() < 0.02, "{row:?}");
        let max_jump = row.windows(2).map(|p| (p[1] - p[0]).abs()).fold(0.0f32, f32::max);
        assert!(max_jump < 0.1, "max step {max_jump}");
        assert!(cov.iter().all(|c| *c == 1.0));
    }

    #[test]
    fn an_image_wholly_inside_the_composite_still_gets_its_side() {
        // #5745: the first image covers the whole 120×40 grid, the second only its right part
        // (x ≥ 70), all of it overlap. It used to be skipped, so the first image kept everything.
        let (w, h) = (120usize, 40usize);
        let luma = vec![vec![0.5f32; w * h], vec![0.5f32; w * h]];
        let cover: Vec<Vec<bool>> = vec![vec![true; w * h], (0..w * h).map(|i| i % w >= 70).collect()];
        let labels = seam_labels(w, h, &luma, &cover, &[0, 1]);
        for y in 0..h {
            assert_eq!(labels[y * w + 5], 0, "row {y}");
            assert_eq!(labels[y * w + w - 1], 1, "row {y}");
            // The second image's region is one run at the right of its seam.
            let row = &labels[y * w..(y + 1) * w];
            let first = row.iter().position(|l| *l == 1).unwrap();
            assert!(first >= 70 && row[first..].iter().all(|l| *l == 1), "row {y}: {row:?}");
        }
        // The same on the left (x < 50) and on top (y < 15): the seam stays inside the overlap
        // instead of on the image's outer edge, which used to leave it nothing.
        let left: Vec<Vec<bool>> = vec![vec![true; w * h], (0..w * h).map(|i| i % w < 50).collect()];
        let labels = seam_labels(w, h, &luma, &left, &[0, 1]);
        for y in 0..h {
            let row = &labels[y * w..(y + 1) * w];
            assert_eq!(row[0], 1, "row {y}: {row:?}");
            assert_eq!(row[w - 1], 0, "row {y}");
            let last = row.iter().rposition(|l| *l == 1).unwrap();
            assert!(last < 50 && row[..=last].iter().all(|l| *l == 1), "row {y}: {row:?}");
        }
        let (tw, th) = (40usize, 120usize);
        let tluma = vec![vec![0.5f32; tw * th], vec![0.5f32; tw * th]];
        let top: Vec<Vec<bool>> = vec![vec![true; tw * th], (0..tw * th).map(|i| i / tw < 50).collect()];
        let labels = seam_labels(tw, th, &tluma, &top, &[0, 1]);
        for x in 0..tw {
            assert_eq!(labels[x], 1, "column {x}");
            assert_eq!(labels[(th - 1) * tw + x], 0, "column {x}");
        }
        // One column or row wide: the seam can only run through it, and the image keeps it.
        for col in [0, w - 1] {
            let strip: Vec<Vec<bool>> = vec![vec![true; w * h], (0..w * h).map(|i| i % w == col).collect()];
            let labels = seam_labels(w, h, &luma, &strip, &[0, 1]);
            assert!(labels.iter().enumerate().all(|(i, l)| *l == i32::from(i % w == col)), "column {col}: {labels:?}");
        }
        let strip: Vec<Vec<bool>> = vec![vec![true; tw * th], (0..tw * th).map(|i| i / tw == 0).collect()];
        let labels = seam_labels(tw, th, &tluma, &strip, &[0, 1]);
        assert!(labels.iter().enumerate().all(|(i, l)| *l == i32::from(i / tw == 0)), "{labels:?}");
        // An image centred on the composite has no side: the first image keeps the overlap.
        let centred: Vec<Vec<bool>> = vec![vec![true; w * h], (0..w * h).map(|i| (20..100).contains(&(i % w))).collect()];
        assert!(seam_labels(w, h, &luma, &centred, &[0, 1]).iter().all(|l| *l == 0));
        // Two images covering the same cells, likewise.
        let same = vec![vec![true; w * h]; 2];
        assert!(seam_labels(w, h, &luma, &same, &[0, 1]).iter().all(|l| *l == 0));
    }
}

/// The row-parallel `reduce` / `expand` / `push_pull` / `multiband` against the serial code they
/// replaced, kept below verbatim as the reference. Every output must stay bit for bit the same.
#[cfg(test)]
mod parallel_tests;