665bfac0b339
flow.rs
//! Optical flow by block matching, and motion-compensated frame interpolation (the Pixel Motion
//! mode of frame blending).
//!
//! The method is the textbook hierarchical block matcher used in video coding and frame-rate
//! conversion: build a luma pyramid of both frames; at the coarsest level, find for each block of
//! frame A the integer displacement into frame B with the smallest sum of absolute differences
//! (SAD) in a search window; at each finer level, start from the doubled coarse vectors (and the
//! neighbours' vectors) and refine in a small window; finish with a sub-pixel parabola fit of the
//! SAD around the best vector and a 3×3 vector median to remove outliers.
//!
//! Interpolation at a fraction `w` between the frames warps both towards the in-between time —
//! A forward by `w·F`, B back by `(1 − w)·F` — and cross-fades them, so moving detail stays sharp
//! instead of double-exposing as with a plain frame mix.
use rayon::prelude::*;
use crate::Image;
/// A block motion field: one vector per `block × block` tile of frame A (in pixels, A → B).
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Flow {
pub width: u32,
pub height: u32,
pub block: u32,
/// Tiles across / down.
pub cols: usize,
pub rows: usize,
pub v: Vec<[f32; 2]>,
}
impl Flow {
/// The motion at pixel position (x, y), bilinearly interpolated between tile centres.
pub fn at(&self, x: f64, y: f64) -> [f32; 2] {
if self.v.is_empty() {
return [0.0; 2];
}
let b = self.block as f64;
let fx = (x / b - 0.5).clamp(0.0, (self.cols - 1) as f64);
let fy = (y / b - 0.5).clamp(0.0, (self.rows - 1) as f64);
let (x0, y0) = (fx.floor() as usize, fy.floor() as usize);
let (x1, y1) = ((x0 + 1).min(self.cols - 1), (y0 + 1).min(self.rows - 1));
let (tx, ty) = ((fx - x0 as f64) as f32, (fy - y0 as f64) as f32);
let g = |c: usize, r: usize| self.v[r * self.cols + c];
let mut o = [0.0; 2];
for i in 0..2 {
let top = g(x0, y0)[i] + (g(x1, y0)[i] - g(x0, y0)[i]) * tx;
let bot = g(x0, y1)[i] + (g(x1, y1)[i] - g(x0, y1)[i]) * tx;
o[i] = top + (bot - top) * ty;
}
o
}
}
/// The `Plane::luma` of `a` and `b` packed into one image (`a` in the red channel, `b` in the
/// green; the rest zero). A device block matcher takes this as its input rather than computing
/// the luma itself: the weighted sum is not reproducible on a device, which may contract
/// `a·b + c` into a fused multiply-add, and the search's near-tie choices would then differ.
pub fn luma_pair(a: &Image, b: &Image) -> Image {
let luma = |p: &[f32; 4]| 0.2126 * p[0] + 0.7152 * p[1] + 0.0722 * p[2] + 0.25 * p[3];
let mut out = Image::new(a.width, a.height);
out.data.par_iter_mut().enumerate().for_each(|(i, q)| {
let la = a.data.get(i).map(luma).unwrap_or(0.0);
let lb = b.data.get(i).map(luma).unwrap_or(0.0);
*q = [la, lb, 0.0, 0.0];
});
out
}
/// A single-channel plane.
struct Plane {
w: usize,
h: usize,
d: Vec<f32>,
}
impl Plane {
fn luma(img: &Image) -> Plane {
let d = img.data.par_iter().map(|p| 0.2126 * p[0] + 0.7152 * p[1] + 0.0722 * p[2] + 0.25 * p[3]).collect();
Plane { w: img.width as usize, h: img.height as usize, d }
}
fn half(&self) -> Plane {
let (w, h) = ((self.w / 2).max(1), (self.h / 2).max(1));
let d = (0..w * h)
.into_par_iter()
.map(|i| {
let (x, y) = (i % w * 2, i / w * 2);
let g = |dx: usize, dy: usize| self.d[(y + dy).min(self.h - 1) * self.w + (x + dx).min(self.w - 1)];
(g(0, 0) + g(1, 0) + g(0, 1) + g(1, 1)) * 0.25
})
.collect();
Plane { w, h, d }
}
#[inline]
fn get(&self, x: i64, y: i64) -> f32 {
self.d[y.clamp(0, self.h as i64 - 1) as usize * self.w + x.clamp(0, self.w as i64 - 1) as usize]
}
}
/// SAD of the `bs` block at (bx, by) in `a` against `b` displaced by (dx, dy).
fn sad(a: &Plane, b: &Plane, bx: i64, by: i64, bs: i64, dx: i64, dy: i64) -> f32 {
let mut s = 0.0;
for y in by..by + bs {
for x in bx..bx + bs {
s += (a.get(x, y) - b.get(x + dx, y + dy)).abs();
}
}
s
}
/// Block-matching flow from `a` to `b` (same size). `block` is the tile size at full resolution;
/// `radius` the search range at the coarsest level (motion up to about `radius · 2^levels`).
pub fn block_flow(a: &Image, b: &Image, block: u32, radius: i32) -> Flow {
block_flow_window(a, b, block, block, radius)
}
/// Largest coarse search radius honoured (the effects use at most 64).
const MAX_RADIUS: i32 = 1024;
/// Upper bound on the pixel comparisons of one motion search (about 4·10¹²: minutes of work on
/// many cores). A finer vector grid than this allows is made coarser, by doubling the tile.
const MAX_SEARCH_WORK: f64 = 4.4e12;
/// The pixel comparisons [`block_flow_window`] makes for tiles of `bs`: every tile, at every
/// pyramid level, tries its candidate vectors with a `window`-sized block, then refines.
/// The pyramid depth follows the requested tile `fine`, not the coarsened one, so a coarser vector
/// grid keeps the full search range.
fn search_work(w: usize, h: usize, bs: usize, fine: usize, win: i64, radius: i64) -> f64 {
let tiles = (w.div_ceil(bs).max(1) as f64) * (h.div_ceil(bs).max(1) as f64);
let reach = (fine as i64).max(win) as usize * 2;
let (mut lw, mut lh, mut top) = (w, h, 0u32);
while top < 3 && lw / 2 >= reach && lh / 2 >= reach {
(lw, lh, top) = (lw / 2, lh / 2, top + 1);
}
let mut per_tile = 5.0 * (win * win) as f64;
for level in 0..=top {
let lbs = (win >> level).max(4) as f64;
let (seeds, r) = if level == top { (1.0, radius as f64) } else { (6.0, 1.0) };
per_tile += seeds * (2.0 * r + 1.0).powi(2) * lbs * lbs;
}
tiles * per_tile
}
/// The tile size and radius to search with: `tile`, doubled (while it still fits the frame) and
/// then, if that is not enough, the radius halved, until the search is within [`MAX_SEARCH_WORK`].
fn planned(w: usize, h: usize, tile: usize, win: i64, radius: i64) -> (usize, i64) {
let (mut bs, mut r) = (tile, radius);
while bs * 2 <= w.min(h) && search_work(w, h, bs, tile, win, r) > MAX_SEARCH_WORK {
bs *= 2;
}
while r > 1 && search_work(w, h, bs, tile, win, r) > MAX_SEARCH_WORK {
r /= 2;
}
(bs, r)
}
/// [`block_flow`] with separate vector spacing and matching window: one vector per
/// `tile × tile` tile, each matched with the `window × window` block centred on its tile
/// (Timewarp's Vector Detail and Block Size).
pub fn block_flow_window(a: &Image, b: &Image, tile: u32, window: u32, radius: i32) -> Flow {
// The matching cost per vector grows with the window's area; 512 is far above any block size the effects offer.
let win = i64::from(window.clamp(4, 512));
let radius = radius.min(MAX_RADIUS);
let fine = tile.max(2) as usize;
let (bs, radius) = planned(a.width as usize, a.height as usize, fine, win, i64::from(radius));
let coarse = bs != fine;
// Window origin relative to the tile origin.
let wo = bs as i64 / 2 - win / 2;
let (w, h) = (a.width as usize, a.height as usize);
// A coarsened grid's last (partial) tiles keep their window inside the frame.
let origin = |c: i64, dim: usize| {
let o = c * bs as i64 + wo;
if coarse { o.clamp(0, (dim as i64 - win).max(0)) } else { o }
};
let cols = w.div_ceil(bs).max(1);
let rows = h.div_ceil(bs).max(1);
let mut flow = Flow { width: a.width, height: a.height, block: bs as u32, cols, rows, v: vec![[0.0; 2]; cols * rows] };
if a.width != b.width || a.height != b.height || w < bs || h < bs || (w as i64) < win || (h as i64) < win {
return flow;
}
// Pyramids (level 0 = full resolution); stop while blocks still fit.
let mut pa = vec![Plane::luma(a)];
let mut pb = vec![Plane::luma(b)];
while pa.len() < 4 && pa.last().is_some_and(|p| p.w / 2 >= (fine as i64).max(win) as usize * 2 && p.h / 2 >= (fine as i64).max(win) as usize * 2) {
let (na, nb) = (pa.last().map(Plane::half), pb.last().map(Plane::half));
pa.extend(na);
pb.extend(nb);
}
let top = pa.len() - 1;
// Integer vectors at the current level, per full-resolution tile.
let mut cur: Vec<[i64; 2]> = vec![[0, 0]; cols * rows];
for level in (0..=top).rev() {
let (la, lb) = (&pa[level], &pb[level]);
let k = 1i64 << level;
// The block covers the tile's footprint at this level (at least 4 pixels).
let lbs = (win / k).max(4);
let r = if level == top { radius } else { 1 };
let prev = cur.clone();
cur = (0..cols * rows)
.into_par_iter()
.map(|i| {
let (c, rr) = ((i % cols) as i64, (i / cols) as i64);
let bx = origin(c, w) / k;
let by = origin(rr, h) / k;
// Candidates: this tile's and its neighbours' vectors from the coarser level.
let mut seeds: Vec<[i64; 2]> = vec![[0, 0]];
if level != top {
for (dc, dr) in [(0, 0), (-1, 0), (1, 0), (0, -1), (0, 1)] {
let (nc, nr) = (c + dc, rr + dr);
if nc >= 0 && nr >= 0 && (nc as usize) < cols && (nr as usize) < rows {
let v = prev[nr as usize * cols + nc as usize];
seeds.push([v[0] * 2, v[1] * 2]);
}
}
}
seeds.sort_unstable();
seeds.dedup();
let mut best = ([0i64, 0i64], f32::INFINITY);
for s in seeds {
for dy in -r..=r {
for dx in -r..=r {
let d = [s[0] + dx, s[1] + dy];
// A tiny bias towards short vectors breaks ties in flat areas.
let e = sad(la, lb, bx, by, lbs, d[0], d[1]) + 1e-4 * (d[0].abs() + d[1].abs()) as f32;
if e < best.1 {
best = (d, e);
}
}
}
}
best.0
})
.collect();
}
// Sub-pixel refinement (parabola through the SAD of the neighbours) at full resolution.
let (la, lb) = (&pa[0], &pb[0]);
let wsi = win;
let fine: Vec<[f32; 2]> = (0..cols * rows)
.into_par_iter()
.map(|i| {
let (bx, by) = (origin((i % cols) as i64, w), origin((i / cols) as i64, h));
let d = cur[i];
let e0 = sad(la, lb, bx, by, wsi, d[0], d[1]);
let fit = |em: f32, ep: f32| {
let den = em - 2.0 * e0 + ep;
if den > 1e-6 { (0.5 * (em - ep) / den).clamp(-0.5, 0.5) } else { 0.0 }
};
let sx = fit(sad(la, lb, bx, by, wsi, d[0] - 1, d[1]), sad(la, lb, bx, by, wsi, d[0] + 1, d[1]));
let sy = fit(sad(la, lb, bx, by, wsi, d[0], d[1] - 1), sad(la, lb, bx, by, wsi, d[0], d[1] + 1));
[d[0] as f32 + sx, d[1] as f32 + sy]
})
.collect();
// 3×3 vector median (component-wise) against outliers.
flow.v = (0..cols * rows)
.into_par_iter()
.map(|i| {
let (c, r) = ((i % cols) as i64, (i / cols) as i64);
let mut xs = Vec::with_capacity(9);
let mut ys = Vec::with_capacity(9);
for dr in -1..=1 {
for dc in -1..=1 {
let (nc, nr) = (c + dc, r + dr);
if nc >= 0 && nr >= 0 && (nc as usize) < cols && (nr as usize) < rows {
let v = fine[nr as usize * cols + nc as usize];
xs.push(v[0]);
ys.push(v[1]);
}
}
}
xs.sort_by(f32::total_cmp);
ys.sort_by(f32::total_cmp);
[xs[xs.len() / 2], ys[ys.len() / 2]]
})
.collect();
flow
}
/// Cross-fade of two frames: `a·(1 − w) + b·w` (Frame Mix).
pub fn mix(a: &Image, b: &Image, w: f32) -> Image {
if a.width != b.width || a.height != b.height {
return if w < 0.5 { a.clone() } else { b.clone() };
}
let mut out = a.clone();
out.data.par_iter_mut().zip(b.data.par_iter()).for_each(|(p, q)| {
for c in 0..4 {
p[c] += (q[c] - p[c]) * w;
}
});
out
}
/// Motion-compensated frame at fraction `w` (0 = `a`, 1 = `b`) between two frames (Pixel Motion).
pub fn interpolate(a: &Image, b: &Image, w: f32) -> Image {
if a.width != b.width || a.height != b.height {
return mix(a, b, w);
}
let flow = block_flow(a, b, 8, 4);
let mut out = Image::new(a.width, a.height);
let wd = w as f64;
out.rows_mut().for_each(|(y, row)| {
let cy = y as f64 + 0.5;
for (x, px) in row.iter_mut().enumerate() {
let cx = x as f64 + 0.5;
let f = flow.at(cx, cy);
let (fx, fy) = (f[0] as f64, f[1] as f64);
let pa = a.sample_bilinear_clamped(cx - wd * fx, cy - wd * fy);
let pb = b.sample_bilinear_clamped(cx + (1.0 - wd) * fx, cy + (1.0 - wd) * fy);
for c in 0..4 {
px[c] = pa[c] + (pb[c] - pa[c]) * w;
}
}
});
out
}
#[cfg(test)]
mod tests {
use super::*;
/// A textured image shifted right by `dx` pixels.
fn texture(w: u32, h: u32, dx: f64) -> Image {
let mut img = Image::new(w, h);
img.rows_mut().for_each(|(y, row)| {
for (x, p) in row.iter_mut().enumerate() {
let (u, v) = (x as f64 - dx, y as f64);
let s = 0.5 + 0.2 * (u * 0.21 + v * 0.07).sin() + 0.15 * (u * 0.05 - v * 0.19).cos() + 0.1 * (u * 0.013 * v * 0.011).sin();
let s = s as f32;
*p = [s, s * 0.8, 1.0 - s, 1.0];
}
});
img
}
fn mae(a: &Image, b: &Image, margin: u32) -> f32 {
let mut s = 0.0;
let mut n = 0;
for y in margin..a.height - margin {
for x in margin..a.width - margin {
let (p, q) = (a.get(x as i64, y as i64), b.get(x as i64, y as i64));
s += (0..3).map(|c| (p[c] - q[c]).abs()).sum::<f32>();
n += 3;
}
}
s / n as f32
}
#[test]
fn a_fine_vector_grid_with_a_huge_window_is_made_coarser() {
// 8K frame, a vector per 2 px, a 512-px window and a 1024-px search: far past the budget.
let (t, r) = super::planned(7680, 4320, 2, 512, 1024);
assert!(t > 2 && t <= 4320 && super::search_work(7680, 4320, t, 2, 512, r) <= super::MAX_SEARCH_WORK, "{t} {r}");
// The tile stays inside the frame, and the pyramid (search range) follows the requested tile.
let (t, _) = super::planned(7680, 4320, 2, 512, 710);
assert!(t <= 4320);
// Pixel Motion Blur's finest grid with its largest search keeps its grid on a 1080p frame.
assert_eq!(super::planned(1920, 1080, 2, 16, 64), (2, 64));
assert_eq!(super::planned(1920, 1080, 8, 64, 4), (8, 4));
}
#[test]
fn a_huge_matching_window_is_held_to_the_cap() {
let (a, b) = (texture(520, 520, 0.0), texture(520, 520, 2.0));
let capped = block_flow_window(&a, &b, 260, 512, 2);
assert_eq!(block_flow_window(&a, &b, 260, u32::MAX, 2).v, capped.v);
}
#[test]
fn flow_finds_translation() {
let a = texture(128, 96, 0.0);
let b = texture(128, 96, 6.0);
let f = block_flow(&a, &b, 8, 4);
let m = f.at(64.0, 48.0);
assert!((m[0] - 6.0).abs() < 0.3 && m[1].abs() < 0.3, "{m:?}");
}
#[test]
fn pixel_motion_beats_frame_mix_on_translation() {
let a = texture(128, 96, 0.0);
let b = texture(128, 96, 6.0);
let truth = texture(128, 96, 3.0);
let pm = mae(&interpolate(&a, &b, 0.5), &truth, 12);
let fm = mae(&mix(&a, &b, 0.5), &truth, 12);
assert!(pm < fm * 0.25, "pixel motion {pm} vs frame mix {fm}");
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.