use crate::error::Error;
use crate::lookup::PairLookup;
use crate::pairs::PairGraph;
use crate::types::{PhotoPx, ViewId};
pub const MIN_TRACKS: usize = 500;
#[derive(Clone, Debug)]
pub struct Params {
pub stride: f32,
pub max_residual: f32,
}
impl Default for Params {
fn default() -> Self {
Params {
stride: 8.0,
max_residual: 4.0,
}
}
}
#[derive(Clone, Debug, PartialEq)]
#[non_exhaustive]
pub struct Track {
pub anchor: ViewId,
pub observations: Vec<(ViewId, PhotoPx)>,
pub residual: f32,
}
impl Track {
pub fn len(&self) -> usize {
self.observations.len()
}
pub fn is_empty(&self) -> bool {
self.observations.is_empty()
}
pub fn observation(&self, view: ViewId) -> Option<PhotoPx> {
self.observations
.binary_search_by_key(&view, |&(v, _)| v)
.ok()
.map(|i| self.observations[i].1)
}
}
pub fn build<L: PairLookup>(
graph: &PairGraph<L>,
(width, height): (usize, usize),
params: &Params,
) -> Vec<Track> {
let views = graph.views();
let max_residual = params.max_residual * graph.precision_px();
let stride = params.stride.max(1.0);
let columns = (width as f32 / stride).ceil() as usize;
let rows = (height as f32 / stride).ceil() as usize;
let (max_x, max_y) = (width as f32 - 1.0, height as f32 - 1.0);
let inside = |p: PhotoPx| (0.0..=max_x).contains(&p.x()) && (0.0..=max_y).contains(&p.y());
let cell = |p: PhotoPx| {
let cx = ((p.x() / stride) as usize).min(columns - 1);
let cy = ((p.y() / stride) as usize).min(rows - 1);
cy * columns + cx
};
let mut claimed = vec![vec![false; columns * rows]; views];
let mut tracks = Vec::new();
let mut observations = Vec::with_capacity(views);
for anchor in (0..views as u32).map(ViewId) {
for index in 0..columns * rows {
if claimed[anchor.index()][index] {
continue;
}
let p = PhotoPx::new(
((index % columns) as f32 + 0.5) * stride,
((index / columns) as f32 + 0.5) * stride,
);
if !inside(p) {
continue;
}
observations.clear();
let mut duplicate = false;
for view in (0..views as u32).map(ViewId) {
if view == anchor {
observations.push((view, p));
continue;
}
let Some(q) = graph
.directed(anchor, view)
.and_then(|mapping| mapping.map(p))
.filter(|&q| inside(q))
else {
continue;
};
duplicate |= claimed[view.index()][cell(q)];
observations.push((view, q));
}
if duplicate || observations.len() < 2 {
continue;
}
let Some(residual) = consistency(graph, anchor, &observations) else {
continue;
};
if residual > max_residual {
continue;
}
for &(view, q) in &observations {
claimed[view.index()][cell(q)] = true;
}
tracks.push(Track {
anchor,
observations: observations.clone(),
residual,
});
}
}
tracks
}
fn consistency<L: PairLookup>(
graph: &PairGraph<L>,
anchor: ViewId,
observations: &[(ViewId, PhotoPx)],
) -> Option<f32> {
let mut worst = 0.0f32;
let mut verified = vec![false; observations.len()];
for (i, &(from, p)) in observations.iter().enumerate() {
if from == anchor {
continue;
}
for (j, &(to, q)) in observations.iter().enumerate() {
if i == j {
continue;
}
let Some(mapped) = graph.directed(from, to).and_then(|m| m.map(p)) else {
continue;
};
worst = worst.max((mapped.0 - q.0).norm());
verified[i] = true;
verified[j] = true;
}
}
verified.iter().all(|&v| v).then_some(worst)
}
pub fn require_enough(tracks: &[Track]) -> Result<usize, Error> {
let found = tracks.iter().filter(|t| t.len() >= 3).count();
if found < MIN_TRACKS {
return Err(Error::TooFewTracks {
found,
required: MIN_TRACKS,
});
}
Ok(found)
}
#[cfg(test)]
mod tests {
use super::*;
struct Shift {
offset: f32,
lie: f32,
}
impl PairLookup for Shift {
fn a_to_b(&self, p: PhotoPx) -> Option<PhotoPx> {
Some(PhotoPx::new(p.x() + self.offset + self.lie, p.y()))
}
fn b_to_a(&self, p: PhotoPx) -> Option<PhotoPx> {
Some(PhotoPx::new(p.x() - self.offset, p.y()))
}
fn coverage(&self) -> f32 {
1.0
}
fn native_stride(&self) -> f32 {
8.0
}
fn precision_px(&self) -> f32 {
1.0
}
}
fn graph(lie: f32) -> PairGraph<Shift> {
PairGraph::from_fn(3, |pair| Shift {
offset: 2.0 * (pair.b().0 - pair.a().0) as f32,
lie: if (pair.a().0, pair.b().0) == (0, 2) {
lie
} else {
0.0
},
})
}
#[test]
fn follows_points_through_every_view_once() {
let tracks = build(&graph(0.0), (80, 40), &Params::default());
assert!(!tracks.is_empty());
assert!(tracks.iter().all(|t| t.residual < 1e-4));
let full: Vec<_> = tracks.iter().filter(|t| t.len() == 3).collect();
assert!(!full.is_empty());
for track in &full {
let p0 = track.observation(ViewId(0)).unwrap();
let p2 = track.observation(ViewId(2)).unwrap();
assert_eq!(p2.x() - p0.x(), 4.0);
}
let mut cells: Vec<_> = tracks
.iter()
.filter_map(|t| t.observation(ViewId(0)))
.map(|p| ((p.x() / 8.0) as i32, (p.y() / 8.0) as i32))
.collect();
let before = cells.len();
cells.sort_unstable();
cells.dedup();
assert_eq!(cells.len(), before, "a point was tracked twice");
}
#[test]
fn rejects_tracks_whose_views_disagree() {
let honest = build(&graph(0.0), (80, 40), &Params::default());
let lied = build(&graph(10.0), (80, 40), &Params::default());
assert!(lied.iter().all(|t| t.len() < 3 || t.anchor != ViewId(0)));
assert!(honest.iter().filter(|t| t.len() == 3).count() > 0);
assert!(require_enough(&lied).is_err());
}
}