665bfac0b339
roto.rs
//! Roto Brush segmentation and propagation, clean-room from published methods:
//!
//! - **Interactive graph-cut segmentation** (Y. Boykov and M.-P. Jolly, "Interactive Graph Cuts
//! for Optimal Boundary & Region Segmentation of Objects in N-D Images", ICCV 2001): the user's
//! foreground / background strokes are hard constraints, every other pixel gets a data cost
//! from colour models and neighbouring pixels a contrast-sensitive smoothness cost; the
//! minimum s–t cut ([`maxflow`], Boykov–Kolmogorov) is the segmentation.
//! - **Iterated colour models** (C. Rother, V. Kolmogorov and A. Blake, "GrabCut", SIGGRAPH
//! 2004): Gaussian mixtures ([`gmm`]) are fitted to the strokes, then re-fitted to the
//! segmentation and the cut repeated; the 8-connected n-link weight is
//! `γ/dist · exp(−β‖Iₚ − I_q‖²)` with `β = 1 / (2⟨‖Iₚ − I_q‖²⟩)`.
//! - **Coarse to fine**: large frames are segmented at a reduced size, then re-cut at full
//! resolution in a narrow band around the upsampled boundary (Lombaert et al., "A Multilevel
//! Banded Graph Cuts Method for Fast Image Segmentation", ICCV 2005).
//! - **Propagation** (in the spirit of X. Bai et al., "Video SnapCut", SIGGRAPH 2009): the
//! previous frame's matte is warped to the next frame by optical flow
//! (`effectcraft_raster::flow::block_flow`), and the frame re-segmented by graph cut only in a
//! band of **Search Radius** pixels around the warped boundary, with the previous frame's
//! colour models and the warped matte as a shape prior. Correction strokes on a frame re-cut
//! the whole frame with the warped matte as a soft prior, and propagation restarts from there.
//!
//! - **Trained models** (optional, swappable: `effectcraft_segment::MaskModel`, e.g. MobileSAM):
//! [`segment_with`] / [`propagate_with`] prompt the model with points along the strokes, or with
//! the warped matte (its box, points deep inside it and the matte itself), and its foreground
//! probability becomes a strong prior for the same graph cut, so strokes stay hard constraints
//! and edges still snap to colour. A model that fails, or whose mask disagrees with the flow, is
//! ignored for that frame.
//!
//! Mattes are in layer pixels at a given scale (1 = full resolution). Strokes are stored in
//! layer pixels ([`RotoData`], serde) and keyed per frame so that each frame's result is a
//! deterministic function of its *chain*: the base frame's strokes, then every frame's strokes
//! on the way out to it ([`RotoData::chain_keys`]).
pub mod bench;
pub mod gmm;
pub mod matting;
pub mod maxflow;
pub mod refine;
pub mod rle;
use std::collections::BTreeMap;
use effectcraft_raster::Image;
use effectcraft_segment::{MaskModel, Prompt};
use rayon::prelude::*;
use serde::{Deserialize, Serialize};
pub use gmm::Gmm;
use maxflow::{Graph, Segment};
/// What a stroke paints.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub enum StrokeKind {
/// Roto Brush (green): foreground.
Fg,
/// Roto Brush with Alt (red): background.
Bg,
/// Refine Edge tool: mark a band for edge matting.
Refine,
/// Refine Edge tool with Alt: remove from the band.
RefineErase,
/// A box around the object (Object Matte): two opposite corners in `points`. Trained models
/// get it as their box prompt; the graph cut ignores it.
Box,
}
impl StrokeKind {
pub fn from_name(s: &str) -> Option<StrokeKind> {
Some(match s.to_ascii_lowercase().as_str() {
"fg" | "foreground" => StrokeKind::Fg,
"bg" | "background" => StrokeKind::Bg,
"refine" | "refineedge" => StrokeKind::Refine,
"refineerase" | "refine-erase" | "erase" => StrokeKind::RefineErase,
_ => return None,
})
}
pub fn is_segmentation(self) -> bool {
matches!(self, StrokeKind::Fg | StrokeKind::Bg)
}
}
/// The most frames a propagation chain reaches on either side of its base frame (about two
/// hours at 24 fps).
const MAX_CHAIN: i64 = 200_000;
/// One stroke: a polyline swept by a disc of `radius` layer pixels, on layer frame `frame`.
#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct Stroke {
pub kind: StrokeKind,
pub frame: i64,
pub radius: f64,
pub points: Vec<[f64; 2]>,
/// Which object of the instance the stroke belongs to (0 for the first, and for every older project).
/// With a tracker each object is followed on its own and the mattes are combined; the classic engine
/// treats all foreground strokes as one object.
#[serde(default, skip_serializing_if = "is_zero")]
pub object: u32,
}
fn is_zero(v: &u32) -> bool {
*v == 0
}
/// A Roto Brush instance's user data: strokes, the base frame and the segmentation span
/// (inclusive layer frames).
#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
#[serde(default, rename_all = "camelCase")]
pub struct RotoData {
pub base: Option<i64>,
pub span: [i64; 2],
pub strokes: Vec<Stroke>,
}
fn fnv(h: &mut u64, bytes: &[u8]) {
for b in bytes {
*h ^= *b as u64;
*h = h.wrapping_mul(0x0100_0000_01b3);
}
}
impl RotoData {
pub fn from_json(s: &str) -> RotoData {
if s.trim().is_empty() {
return RotoData::default();
}
serde_json::from_str(s).unwrap_or_default()
}
pub fn to_json(&self) -> String {
serde_json::to_string(self).unwrap_or_default()
}
pub fn is_empty(&self) -> bool {
self.base.is_none() || !self.strokes.iter().any(|s| s.kind.is_segmentation())
}
pub fn strokes_at(&self, frame: i64) -> Vec<&Stroke> {
self.strokes.iter().filter(|s| s.frame == frame).collect()
}
/// Frames that carry strokes.
pub fn stroke_frames(&self) -> Vec<i64> {
let mut v: Vec<i64> = self.strokes.iter().map(|s| s.frame).collect();
v.sort_unstable();
v.dedup();
v
}
/// The objects that have a foreground stroke, in order.
pub fn objects(&self) -> Vec<u32> {
let mut v: Vec<u32> = self.strokes.iter().filter(|s| s.kind == StrokeKind::Fg).map(|s| s.object).collect();
v.sort_unstable();
v.dedup();
v
}
/// The strokes of `object` on `frame`: its own foreground, background and box strokes, and the Refine Edge
/// strokes (which belong to the whole matte).
pub fn strokes_of(&self, frame: i64, object: u32) -> Vec<&Stroke> {
self.strokes.iter().filter(|s| s.frame == frame && (s.object == object || matches!(s.kind, StrokeKind::Refine | StrokeKind::RefineErase))).collect()
}
/// The stored span cut to at most MAX_CHAIN frames either side of the base: a project's
/// numbers must not make one render build billions of keys. Frames past it have no key.
fn bounded_span(&self, base: i64) -> [i64; 2] {
[self.span[0].max(base.saturating_sub(MAX_CHAIN)), self.span[1].min(base.saturating_add(MAX_CHAIN))]
}
pub fn in_span(&self, f: i64) -> bool {
self.base.is_some_and(|b| {
let span = self.bounded_span(b);
f >= span[0] && f <= span[1]
})
}
/// Add a stroke: the first segmentation stroke sets the base frame and a span of
/// `default_span` frames each side (clamped to `limits`); strokes outside the span extend it.
pub fn add(&mut self, s: Stroke, default_span: i64, limits: [i64; 2]) {
let f = s.frame;
match self.base {
None if s.kind.is_segmentation() => {
self.base = Some(f);
self.span = [(f - default_span).max(limits[0]), (f + default_span).min(limits[1]).max(f)];
}
Some(_) => {
self.span[0] = self.span[0].min(f);
self.span[1] = self.span[1].max(f);
}
None => {}
}
self.strokes.push(s);
}
/// Largest Refine Edge stroke radius (layer pixels).
pub fn refine_radius(&self) -> f64 {
self.strokes.iter().filter(|s| matches!(s.kind, StrokeKind::Refine)).map(|s| s.radius).fold(0.0, f64::max)
}
/// Content key of every frame in the span: the base frame's from `seed` (what the frames
/// and settings are) and its strokes, every other frame's from its neighbour towards the
/// base and its own strokes.
pub fn chain_keys(&self, seed: u64) -> BTreeMap<i64, u64> {
let mut out = BTreeMap::new();
let Some(base) = self.base else { return out };
// The strokes by frame, grouped once (each frame looked through every stroke before).
let mut by_frame: BTreeMap<i64, Vec<&Stroke>> = BTreeMap::new();
for s in &self.strokes {
by_frame.entry(s.frame).or_default().push(s);
}
let key = |prev: u64, f: i64| {
let mut h = prev ^ 0x9e37_79b9_7f4a_7c15;
fnv(&mut h, &f.to_le_bytes());
for s in by_frame.get(&f).into_iter().flatten() {
fnv(&mut h, serde_json::to_string(s).unwrap_or_default().as_bytes());
}
h
};
let k0 = key(seed, base);
out.insert(base, k0);
let mut k = k0;
let span = self.bounded_span(base);
// `base + 1` only when there is a frame after the base (it overflows at i64::MAX).
if base < span[1] {
for f in base + 1..=span[1] {
k = key(k, f);
out.insert(f, k);
}
}
k = k0;
for f in (span[0]..base).rev() {
k = key(k, f);
out.insert(f, k);
}
out
}
/// The neighbour a frame is propagated from (None for the base frame and outside the span).
pub fn source_of(&self, f: i64) -> Option<i64> {
let base = self.base?;
if !self.in_span(f) || f == base {
return None;
}
Some(if f > base { f - 1 } else { f + 1 })
}
}
/// Segmentation settings (the effect's Roto Brush parameters, in frame pixels).
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct SegOpts {
/// Pixels of the matte per layer pixel.
pub scale: f64,
/// Search Radius (layer pixels).
pub search_radius: f64,
/// Motion Threshold / Motion Damping, percent.
pub motion_threshold: f64,
pub motion_damping: f64,
/// Quality ▸ Best.
pub best: bool,
}
impl Default for SegOpts {
fn default() -> Self {
SegOpts { scale: 1.0, search_radius: 15.0, motion_threshold: 10.0, motion_damping: 20.0, best: false }
}
}
/// One frame's segmentation: the binary matte, the Refine Edge band and the colour models.
#[derive(Clone, Debug, Default, PartialEq)]
pub struct FrameSeg {
pub w: usize,
pub h: usize,
pub matte: Vec<u8>,
pub refine: Vec<u8>,
pub fg: Gmm,
pub bg: Gmm,
}
impl FrameSeg {
/// The union of several objects' segmentations of one frame (the largest keeps its colour models). The
/// parts must share one size; any that does not is ignored.
pub fn union(parts: Vec<FrameSeg>) -> FrameSeg {
let Some(first) = parts.first() else { return FrameSeg::default() };
let (w, h) = (first.w, first.h);
let mut parts: Vec<FrameSeg> = parts.into_iter().filter(|p| p.w == w && p.h == h && p.matte.len() == w * h).collect();
parts.sort_by_key(|p| std::cmp::Reverse(p.area()));
let mut it = parts.into_iter();
let Some(mut out) = it.next() else { return FrameSeg::default() };
for p in it {
for (a, b) in out.matte.iter_mut().zip(&p.matte) {
*a = (*a).max(*b);
}
for (a, b) in out.refine.iter_mut().zip(&p.refine) {
*a = (*a).max(*b);
}
}
out
}
pub fn empty(w: usize, h: usize) -> FrameSeg {
let Some(n) = w.checked_mul(h).filter(|n| *n <= rle::MAX_PLANE_BYTES) else {
return FrameSeg::default();
};
FrameSeg { w, h, matte: vec![0; n], refine: vec![0; n], ..Default::default() }
}
pub fn area(&self) -> usize {
self.matte.iter().filter(|v| **v != 0).count()
}
/// Centroid of the matte (pixels), if any.
pub fn centroid(&self) -> Option<[f64; 2]> {
if self.w == 0 || self.w.checked_mul(self.h)? > self.matte.len() {
return None;
}
let (mut sx, mut sy, mut n) = (0.0, 0.0, 0.0);
for (i, v) in self.matte.iter().enumerate() {
if *v != 0 {
sx += (i % self.w) as f64 + 0.5;
sy += (i / self.w) as f64 + 0.5;
n += 1.0;
}
}
(n > 0.0).then(|| [sx / n, sy / n])
}
/// A compact binary form (to ship a segmentation between engine instances, e.g. from a Web
/// Worker to the page): `ECSG`, width, height (u32 LE), the colour models as JSON (length
/// prefixed), then the matte and the Refine Edge band run-length encoded (u16 LE run, byte).
pub fn to_bytes(&self) -> Vec<u8> {
let Some(pixels) = self.w.checked_mul(self.h).filter(|n| *n <= rle::MAX_PLANE_BYTES) else {
return Vec::new();
};
if self.matte.len() != pixels || self.refine.len() != pixels || self.w > u32::MAX as usize || self.h > u32::MAX as usize {
return Vec::new();
}
let models = serde_json::to_vec(&(&self.fg, &self.bg)).unwrap_or_default();
let Some(header_len) = 16usize.checked_add(models.len()) else { return Vec::new() };
let mut out = Vec::new();
if out.try_reserve(header_len.saturating_add(64)).is_err() {
return Vec::new();
}
out.extend_from_slice(b"ECSG");
out.extend_from_slice(&(self.w as u32).to_le_bytes());
out.extend_from_slice(&(self.h as u32).to_le_bytes());
out.extend_from_slice(&(models.len() as u32).to_le_bytes());
out.extend_from_slice(&models);
for plane in [&self.matte, &self.refine] {
let mut i = 0;
while i < plane.len() {
let v = plane[i];
let mut n = 1;
while i + n < plane.len() && plane[i + n] == v && n < u16::MAX as usize {
n += 1;
}
if out.try_reserve(3).is_err() {
return Vec::new();
}
out.extend_from_slice(&(n as u16).to_le_bytes());
out.push(v);
i += n;
}
}
out
}
/// Inverse of [`FrameSeg::to_bytes`] (`None` for malformed input).
pub fn from_bytes(b: &[u8]) -> Option<FrameSeg> {
if b.len() < 16 || &b[..4] != b"ECSG" {
return None;
}
let u = |i: usize| u32::from_le_bytes([b[i], b[i + 1], b[i + 2], b[i + 3]]) as usize;
let (w, h, ml) = (u(4), u(8), u(12));
let n = w.checked_mul(h)?;
if n > rle::MAX_PLANE_BYTES || w == 0 || h == 0 {
return None;
}
let models_end = 16usize.checked_add(ml)?;
let models = b.get(16..models_end)?;
let (fg, bg): (Gmm, Gmm) = serde_json::from_slice(models).ok()?;
let mut rest = b.get(models_end..)?;
// Each run covers at most u16::MAX pixels; refuse before reserving a plane the input can't fill.
if rest.len() < n.div_ceil(usize::from(u16::MAX)).saturating_mul(6) {
return None;
}
let mut plane = || -> Option<Vec<u8>> {
let mut v = Vec::new();
v.try_reserve_exact(n).ok()?;
while v.len() < n {
if rest.len() < 3 {
return None;
}
let run = u16::from_le_bytes([*rest.first()?, *rest.get(1)?]) as usize;
let next = v.len().checked_add(run)?;
if run == 0 || next > n {
return None;
}
let value = *rest.get(2)?;
v.resize(next, value);
rest = rest.get(3..)?;
}
(v.len() == n).then_some(v)
};
let matte = plane()?;
let refine = plane()?;
if !rest.is_empty() {
return None;
}
Some(FrameSeg { w, h, matte, refine, fg, bg })
}
}
/// Straight RGB of an image (transparent pixels are black).
pub fn rgb_of(img: &Image) -> Vec<[f32; 3]> {
img.data.par_iter().map(|p| if p[3] > 1e-6 { [p[0] / p[3], p[1] / p[3], p[2] / p[3]] } else { [0.0; 3] }).collect()
}
/// A stroke's radius and segments at `scale`.
fn segments(s: &Stroke, scale: f64) -> (f64, Vec<([f64; 2], [f64; 2])>) {
let pts: Vec<[f64; 2]> = s.points.iter().map(|p| [p[0] * scale, p[1] * scale]).collect();
let segs = match pts.as_slice() {
[p] => vec![(*p, *p)],
_ => pts.windows(2).map(|w| (w[0], w[1])).collect(),
};
((s.radius * scale).max(0.5), segs)
}
/// Distance from `p` to the segment `a`–`b`.
fn segment_distance(p: [f64; 2], a: [f64; 2], b: [f64; 2]) -> f64 {
let d = [b[0] - a[0], b[1] - a[1]];
let l2 = d[0] * d[0] + d[1] * d[1];
let t = if l2 > 0.0 { (((p[0] - a[0]) * d[0] + (p[1] - a[1]) * d[1]) / l2).clamp(0.0, 1.0) } else { 0.0 };
(p[0] - a[0] - d[0] * t).hypot(p[1] - a[1] - d[1] * t)
}
/// Call `paint` with every pixel `s` covers at `scale`.
fn sweep(s: &Stroke, scale: f64, w: usize, h: usize, mut paint: impl FnMut(usize)) {
let (r, segs) = segments(s, scale);
for (a, b) in segs {
let x0 = (a[0].min(b[0]) - r).floor().max(0.0) as usize;
let x1 = ((a[0].max(b[0]) + r).ceil().max(0.0) as usize).min(w);
let y0 = (a[1].min(b[1]) - r).floor().max(0.0) as usize;
let y1 = ((a[1].max(b[1]) + r).ceil().max(0.0) as usize).min(h);
for y in y0..y1 {
for x in x0..x1 {
if segment_distance([x as f64 + 0.5, y as f64 + 0.5], a, b) <= r {
paint(y * w + x);
}
}
}
}
}
/// Pixels covered by `strokes` (of the given kinds) at `scale`.
pub fn rasterize(strokes: &[&Stroke], kinds: &[StrokeKind], scale: f64, w: usize, h: usize) -> Vec<bool> {
let mut m = vec![false; w * h];
for s in strokes.iter().filter(|s| kinds.contains(&s.kind)) {
sweep(s, scale, w, h, |i| m[i] = true);
}
m
}
/// What a pair of opposing strokes (add / remove) leaves on each pixel.
const ON: u8 = 1;
const OFF: u8 = 2;
/// [`ON`] where an `on` stroke covers a pixel, [`OFF`] where an `off` stroke does, 0 elsewhere.
/// Strokes apply in drawing order, so where they overlap the last one painted wins: a stroke
/// corrects the ones before it.
pub fn resolve(strokes: &[&Stroke], on: StrokeKind, off: StrokeKind, scale: f64, w: usize, h: usize) -> Vec<u8> {
let mut m = vec![0; w * h];
for s in strokes {
let v = if s.kind == on {
ON
} else if s.kind == off {
OFF
} else {
continue;
};
sweep(s, scale, w, h, |i| m[i] = v);
}
m
}
/// Hard constraints: foreground, background, else free.
const HARD_FG: u8 = ON;
const HARD_BG: u8 = OFF;
/// Graph-cut energy weights.
const GAMMA: f64 = 50.0;
const PRIOR: f64 = 1.0;
/// A trained model's matte as a prior: it outweighs the colour models.
const MODEL_PRIOR: f64 = 4.0;
/// Fixed-point scale of the energies.
const K: f64 = 16.0;
const INF: i64 = 1 << 40;
const NB: [(i64, i64, bool); 8] = [(1, 0, true), (0, 1, true), (1, 1, true), (-1, 1, true), (-1, 0, false), (0, -1, false), (-1, -1, false), (1, -1, false)];
fn beta(img: &[[f32; 3]], free: &[bool], w: usize, h: usize) -> f64 {
let (mut s, mut n) = (0.0f64, 0.0f64);
for y in 0..h {
for x in 0..w {
let i = y * w + x;
if !free[i] {
continue;
}
let c = img[i];
for (dx, dy) in [(1usize, 0usize), (0, 1)] {
let (nx, ny) = (x + dx, y + dy);
if nx < w && ny < h {
let q = img[ny * w + nx];
s += ((c[0] - q[0]).powi(2) + (c[1] - q[1]).powi(2) + (c[2] - q[2]).powi(2)) as f64;
n += 1.0;
}
}
}
}
if s <= 1e-12 { 1.0 } else { n / (2.0 * s) }
}
/// One min-cut over the `free` pixels; others keep `labels`. `prior`: P(foreground) per pixel
/// and how much it weighs against the colour models.
fn cut(img: &[[f32; 3]], size: (usize, usize), labels: &mut [u8], free: &[bool], hard: &[u8], models: (&Gmm, &Gmm), prior: Option<(&[f32], f64)>) {
let (w, h) = size;
let (fg, bg) = models;
let mut idx = vec![u32::MAX; w * h];
let mut nodes = vec![];
for i in 0..w * h {
if free[i] {
idx[i] = nodes.len() as u32;
nodes.push(i);
}
}
if nodes.is_empty() {
return;
}
let b = beta(img, free, w, h);
let costs: Vec<(f64, f64)> = nodes
.par_iter()
.map(|&i| {
let c = img[i];
let (mut cf, mut cb) = (fg.cost(c), bg.cost(c));
if let Some((p, wt)) = prior {
let pf = (p[i] as f64).clamp(0.02, 0.98);
cf += wt * -pf.ln();
cb += wt * -(1.0 - pf).ln();
}
(cf, cb)
})
.collect();
let mut g = Graph::new(nodes.len(), nodes.len() * 4);
for (n, &i) in nodes.iter().enumerate() {
let (x, y) = ((i % w) as i64, (i / w) as i64);
let (cf, cb) = costs[n];
let m = cf.min(cb);
let (mut src, mut snk) = (((cb - m) * K).round() as i64, ((cf - m) * K).round() as i64);
match hard[i] {
HARD_FG => (src, snk) = (INF, 0),
HARD_BG => (src, snk) = (0, INF),
_ => {}
}
g.add_tweights(n, src, snk);
let c = img[i];
for (dx, dy, fwd) in NB {
let (nx, ny) = (x + dx, y + dy);
if nx < 0 || ny < 0 || nx >= w as i64 || ny >= h as i64 {
continue;
}
let j = ny as usize * w + nx as usize;
let q = img[j];
let d2 = ((c[0] - q[0]).powi(2) + (c[1] - q[1]).powi(2) + (c[2] - q[2]).powi(2)) as f64;
let dist = if dx != 0 && dy != 0 { std::f64::consts::SQRT_2 } else { 1.0 };
let wt = ((GAMMA / dist * (-b * d2).exp()) * K).round() as i32;
if wt <= 0 {
continue;
}
if idx[j] == u32::MAX {
// Fixed neighbour: disagreeing with it costs the edge.
if labels[j] != 0 {
g.add_tweights(n, wt as i64, 0);
} else {
g.add_tweights(n, 0, wt as i64);
}
} else if fwd {
g.add_edge(n, idx[j] as usize, wt, wt);
}
}
}
g.maxflow();
for (n, &i) in nodes.iter().enumerate() {
labels[i] = (g.segment(n) == Segment::Source) as u8;
}
}
/// Colour samples of the pixels where `sel` holds.
fn samples(img: &[[f32; 3]], sel: impl Fn(usize) -> bool) -> Vec<[f32; 3]> {
img.iter().enumerate().filter(|(i, _)| sel(*i)).map(|(_, c)| *c).collect()
}
const COMPONENTS: usize = 5;
const MAX_SAMPLES: usize = 24_000;
fn fit_models(img: &[[f32; 3]], labels: &[u8]) -> (Gmm, Gmm) {
let fg = samples(img, |i| labels[i] != 0);
let bg = samples(img, |i| labels[i] == 0);
(Gmm::fit(&fg, COMPONENTS, MAX_SAMPLES), Gmm::fit(&bg, COMPONENTS, MAX_SAMPLES))
}
/// Keep the foreground components (8-connected) that touch `seeds`; fill small background
/// holes that touch neither the frame edge nor a background seed.
fn clean(labels: &mut [u8], seeds: &[bool], bg_seeds: &[bool], w: usize, h: usize) {
let n = w * h;
let mut comp = vec![u32::MAX; n];
let mut stack = vec![];
let mut fg_area = 0usize;
for start in 0..n {
if comp[start] != u32::MAX {
continue;
}
let lab = labels[start];
let id = start as u32;
comp[start] = id;
stack.push(start);
let mut members = vec![];
let (mut seeded, mut edge, mut bgs) = (false, false, false);
while let Some(i) = stack.pop() {
members.push(i);
seeded |= seeds[i];
bgs |= bg_seeds[i];
let (x, y) = ((i % w) as i64, (i / w) as i64);
edge |= x == 0 || y == 0 || x == w as i64 - 1 || y == h as i64 - 1;
for (dx, dy, _) in NB {
let (nx, ny) = (x + dx, y + dy);
if nx < 0 || ny < 0 || nx >= w as i64 || ny >= h as i64 {
continue;
}
let j = ny as usize * w + nx as usize;
if comp[j] == u32::MAX && labels[j] == lab {
comp[j] = id;
stack.push(j);
}
}
}
if lab != 0 {
if seeded {
fg_area += members.len();
} else {
for i in members {
labels[i] = 0;
}
}
} else if !edge && !bgs {
// Remember holes as negative candidates (resolved below once fg_area is known).
for i in members {
comp[i] = u32::MAX - 1;
}
}
}
// Fill holes smaller than 2 % of the foreground.
let mut seen = vec![false; n];
for start in 0..n {
if comp[start] != u32::MAX - 1 || seen[start] || labels[start] != 0 {
continue;
}
let mut members = vec![start];
seen[start] = true;
let mut k = 0;
while k < members.len() {
let i = members[k];
k += 1;
let (x, y) = ((i % w) as i64, (i / w) as i64);
for (dx, dy, _) in NB {
let (nx, ny) = (x + dx, y + dy);
if nx < 0 || ny < 0 || nx >= w as i64 || ny >= h as i64 {
continue;
}
let j = ny as usize * w + nx as usize;
if !seen[j] && comp[j] == u32::MAX - 1 && labels[j] == 0 {
seen[j] = true;
members.push(j);
}
}
}
// A hole is enclosed by foreground that survived the component filter.
let enclosed = members.iter().all(|&i| {
let (x, y) = ((i % w) as i64, (i / w) as i64);
NB.iter().all(|(dx, dy, _)| {
let (nx, ny) = (x + dx, y + dy);
if nx < 0 || ny < 0 || nx >= w as i64 || ny >= h as i64 {
return false;
}
let j = ny as usize * w + nx as usize;
labels[j] != 0 || comp[j] == u32::MAX - 1
})
});
if enclosed && (members.len() as f64) < 0.02 * fg_area as f64 {
for i in members {
labels[i] = 1;
}
}
}
}
fn downsample_rgb(img: &[[f32; 3]], w: usize, h: usize, f: usize) -> (Vec<[f32; 3]>, usize, usize) {
let (cw, ch) = (w.div_ceil(f), h.div_ceil(f));
let out = (0..cw * ch)
.into_par_iter()
.map(|i| {
let (cx, cy) = (i % cw, i / cw);
let mut s = [0.0f32; 3];
let mut n = 0.0;
for y in cy * f..((cy + 1) * f).min(h) {
for x in cx * f..((cx + 1) * f).min(w) {
let c = img[y * w + x];
s[0] += c[0];
s[1] += c[1];
s[2] += c[2];
n += 1.0;
}
}
[s[0] / n, s[1] / n, s[2] / n]
})
.collect();
(out, cw, ch)
}
/// What a frame is segmented with besides its strokes: the matte propagated from its neighbour.
pub struct Prior {
/// Warped neighbour matte, soft (0–1).
pub soft: Vec<f32>,
/// The neighbour's colour models.
pub fg: Gmm,
pub bg: Gmm,
/// Warped Refine Edge band.
pub refine: Vec<u8>,
/// How much the prior weighs against the colour models.
pub weight: f64,
}
/// Fit foreground/background colour models from strokes and the propagated matte.
fn initial_models(rgb: &[[f32; 3]], hard: &[u8], fgs: &[bool], strokes: &[&Stroke], prior: Option<&Prior>, opts: &SegOpts, size: (usize, usize)) -> (Gmm, Gmm) {
let (w, h) = size;
// Initial colour models: the strokes (and the propagated matte).
match prior {
Some(p) => {
let fgc = samples(rgb, |i| (hard[i] == HARD_FG) || (hard[i] == 0 && p.soft[i] >= 0.5));
let bgc = samples(rgb, |i| (hard[i] == HARD_BG) || (hard[i] == 0 && p.soft[i] < 0.5));
let f = Gmm::fit(&fgc, COMPONENTS, MAX_SAMPLES);
let b = Gmm::fit(&bgc, COMPONENTS, MAX_SAMPLES);
(if f.is_empty() { p.fg.clone() } else { f }, if b.is_empty() { p.bg.clone() } else { b })
}
None => {
let fgc = samples(rgb, |i| hard[i] == HARD_FG);
let mut bgc = samples(rgb, |i| hard[i] == HARD_BG);
if bgc.is_empty() {
// No background strokes: what is far from the foreground strokes.
let d = matting::distance(fgs, w, h);
let r = strokes.iter().filter(|s| s.kind == StrokeKind::Fg).map(|s| s.radius).fold(1.0, f64::max) * opts.scale;
let far = (4.0 * r).max(0.25 * w.max(h) as f64) as f32;
bgc = samples(rgb, |i| d[i] > far);
if bgc.is_empty() {
bgc = samples(rgb, |i| hard[i] != HARD_FG);
}
}
(Gmm::fit(&fgc, COMPONENTS, MAX_SAMPLES), Gmm::fit(&bgc, COMPONENTS, MAX_SAMPLES))
}
}
}
/// Segment a frame from its strokes (and a propagated prior): GrabCut iterations on a reduced
/// copy, then a full-resolution cut in a band around the boundary.
pub fn segment(img: &Image, strokes: &[&Stroke], prior: Option<&Prior>, opts: &SegOpts, refine_radius: f64) -> FrameSeg {
let (w, h) = (img.width as usize, img.height as usize);
if w == 0 || h == 0 {
return FrameSeg::empty(w, h);
}
let rgb = rgb_of(img);
let hard = resolve(strokes, StrokeKind::Fg, StrokeKind::Bg, opts.scale, w, h);
let fgs: Vec<bool> = hard.iter().map(|v| *v == HARD_FG).collect();
let bgs: Vec<bool> = hard.iter().map(|v| *v == HARD_BG).collect();
// A warped matte is uncertain by about the search radius: blur it. A model's matte is not.
let soft_prior: Option<Vec<f32>> =
prior.map(|p| if p.weight > PRIOR { p.soft.clone() } else { matting::gauss(&p.soft, w, h, (opts.search_radius * opts.scale / 4.0).max(1.0)) });
let pw = prior.map_or(PRIOR, |p| p.weight);
let (fg0, bg0) = initial_models(&rgb, &hard, &fgs, strokes, prior, opts, (w, h));
let iters = if opts.best { 4 } else { 3 };
let work = if opts.best { 960 } else { 480 };
let f = w.max(h).div_ceil(work).max(1);
let mut labels: Vec<u8> = match &soft_prior {
Some(p) => p.iter().map(|v| (*v >= 0.5) as u8).collect(),
None => fgs.iter().map(|v| *v as u8).collect(),
};
for (l, hd) in labels.iter_mut().zip(&hard) {
if *hd != 0 {
*l = (*hd == HARD_FG) as u8;
}
}
let (mut fgm, mut bgm) = (fg0, bg0);
if f > 1 {
let (crgb, cw, ch) = downsample_rgb(&rgb, w, h, f);
let mut chard = vec![0u8; cw * ch];
let mut cprior = soft_prior.as_ref().map(|_| vec![0.0f32; cw * ch]);
for cy in 0..ch {
for cx in 0..cw {
let (mut anyf, mut anyb, mut s, mut n) = (false, false, 0.0f32, 0.0f32);
for y in cy * f..((cy + 1) * f).min(h) {
for x in cx * f..((cx + 1) * f).min(w) {
let i = y * w + x;
anyf |= hard[i] == HARD_FG;
anyb |= hard[i] == HARD_BG;
if let Some(p) = &soft_prior {
s += p[i];
}
n += 1.0;
}
}
chard[cy * cw + cx] = match (anyf, anyb) {
(true, false) => HARD_FG,
(false, true) => HARD_BG,
_ => 0,
};
if let Some(cp) = &mut cprior {
cp[cy * cw + cx] = s / n;
}
}
}
let mut cl: Vec<u8> = match &cprior {
Some(p) => p.iter().map(|v| (*v >= 0.5) as u8).collect(),
None => chard.iter().map(|v| (*v == HARD_FG) as u8).collect(),
};
let free = vec![true; cw * ch];
for it in 0..iters {
cut(&crgb, (cw, ch), &mut cl, &free, &chard, (&fgm, &bgm), cprior.as_deref().map(|c| (c, pw)));
if it + 1 < iters {
let (a, b) = fit_models(&crgb, &cl);
if !a.is_empty() && !b.is_empty() {
(fgm, bgm) = (a, b);
}
}
}
for y in 0..h {
for x in 0..w {
let i = y * w + x;
labels[i] = if hard[i] != 0 { (hard[i] == HARD_FG) as u8 } else { cl[(y / f) * cw + x / f] };
}
}
let (a, b) = fit_models(&rgb, &labels);
if !a.is_empty() && !b.is_empty() {
(fgm, bgm) = (a, b);
}
// Full-resolution band.
let sd = matting::signed_distance(&labels, w, h);
let band = f as f32 + 1.5;
let free: Vec<bool> = sd.iter().map(|d| d.abs() <= band).collect();
cut(&rgb, (w, h), &mut labels, &free, &hard, (&fgm, &bgm), soft_prior.as_deref().map(|c| (c, pw)));
} else {
let free = vec![true; w * h];
for it in 0..iters {
cut(&rgb, (w, h), &mut labels, &free, &hard, (&fgm, &bgm), soft_prior.as_deref().map(|c| (c, pw)));
if it + 1 < iters {
let (a, b) = fit_models(&rgb, &labels);
if !a.is_empty() && !b.is_empty() {
(fgm, bgm) = (a, b);
}
}
}
}
// Keep what the strokes (or the prior's core) select.
let mut seeds = fgs.clone();
if let Some(p) = &soft_prior {
let core = core_of(p, w, h, opts.search_radius * opts.scale);
for (s, c) in seeds.iter_mut().zip(core) {
*s |= c;
}
}
clean(&mut labels, &seeds, &bgs, w, h);
finish(img, &rgb, labels, strokes, prior.map(|p| p.refine.as_slice()), opts, refine_radius)
}
/// Pixels deep inside a soft matte (more than `r` from its edge), else the matte itself.
fn core_of(soft: &[f32], w: usize, h: usize, r: f64) -> Vec<bool> {
let bin: Vec<u8> = soft.iter().map(|v| (*v >= 0.5) as u8).collect();
let sd = matting::signed_distance(&bin, w, h);
let core: Vec<bool> = sd.iter().map(|d| *d as f64 > r).collect();
if core.iter().any(|c| *c) { core } else { bin.iter().map(|v| *v != 0).collect() }
}
/// Final models and Refine Edge band of a segmented frame.
fn finish(_img: &Image, rgb: &[[f32; 3]], labels: Vec<u8>, strokes: &[&Stroke], warped_refine: Option<&[u8]>, opts: &SegOpts, refine_radius: f64) -> FrameSeg {
let (w, h) = (_img.width as usize, _img.height as usize);
let (fg, bg) = fit_models(rgb, &labels);
let painted = resolve(strokes, StrokeKind::Refine, StrokeKind::RefineErase, opts.scale, w, h);
let near: Option<Vec<f32>> = warped_refine.filter(|r| r.iter().any(|v| *v != 0)).map(|_| matting::signed_distance(&labels, w, h));
let rr = (refine_radius * opts.scale + 2.0) as f32;
let refine: Vec<u8> = (0..w * h)
.map(|i| {
let carried = match (warped_refine, &near) {
(Some(r), Some(sd)) => r[i] != 0 && sd[i].abs() <= rr,
_ => false,
};
((carried && painted[i] != OFF) || painted[i] == ON) as u8
})
.collect();
FrameSeg { w, h, matte: labels, refine, fg, bg }
}
/// Warp the previous frame's segmentation onto the next frame by optical flow (next → prev),
/// with Motion Threshold / Damping applied to the vectors.
pub fn warp_prior(prev_img: &Image, prev: &FrameSeg, next_img: &Image, opts: &SegOpts) -> Prior {
let (w, h) = (next_img.width as usize, next_img.height as usize);
let flow = effectcraft_raster::flow::block_flow(next_img, prev_img, 8, 4);
let thr = (opts.motion_threshold / 100.0 * opts.search_radius * opts.scale).max(0.0);
let damp = (1.0 - opts.motion_damping / 100.0).clamp(0.0, 1.0);
let src: Vec<f32> = prev.matte.iter().map(|v| *v as f32).collect();
let pw = prev.w.min(w);
let ph = prev.h.min(h);
let res: Vec<(f32, u8)> = (0..w * h)
.into_par_iter()
.map(|i| {
let (x, y) = ((i % w) as f64 + 0.5, (i / w) as f64 + 0.5);
let v = flow.at(x, y);
let (mut vx, mut vy) = (v[0] as f64, v[1] as f64);
if vx.hypot(vy) < thr {
vx *= damp;
vy *= damp;
}
let (sx, sy) = (x + vx, y + vy);
let soft = if pw == prev.w && ph == prev.h { matting::sample(&src, prev.w, prev.h, sx, sy) } else { 0.0 };
let (ix, iy) = (sx.floor().clamp(0.0, (prev.w.max(1) - 1) as f64) as usize, sy.floor().clamp(0.0, (prev.h.max(1) - 1) as f64) as usize);
let r = prev.refine.get(iy * prev.w + ix).copied().unwrap_or(0);
(soft, r)
})
.collect();
Prior { soft: res.iter().map(|r| r.0).collect(), fg: prev.fg.clone(), bg: prev.bg.clone(), refine: res.iter().map(|r| r.1).collect(), weight: PRIOR }
}
/// The inputs of a band re-cut on one (sub)image of `size`.
struct Band<'a> {
size: (usize, usize),
rgb: &'a [[f32; 3]],
/// The warped soft matte (the prior, before blurring).
soft: &'a [f32],
free: &'a [bool],
seeds: &'a [bool],
}
/// Graph cut of the free pixels with the blurred prior, then [`clean`].
fn cut_band(b: &Band, labels: &mut [u8], sigma: f64, models: (&Gmm, &Gmm)) {
let (w, h) = b.size;
let soft = matting::gauss(b.soft, w, h, sigma);
cut(b.rgb, b.size, labels, b.free, &vec![0u8; w * h], models, Some((&soft, PRIOR)));
clean(labels, b.seeds, &vec![false; w * h], w, h);
}
/// The half-open rectangle `[x0, y0, x1, y1)` around the pixels with `sd >= -r` (the band
/// `|sd| <= r` and the core `sd > r`), grown by `pad` and clipped to the frame; `None` when
/// there are none.
fn band_rect(sd: &[f32], size: (usize, usize), r: f32, pad: usize) -> Option<[usize; 4]> {
let (w, h) = size;
let (mut x0, mut y0, mut x1, mut y1) = (usize::MAX, usize::MAX, 0, 0);
for (i, d) in sd.iter().enumerate() {
if *d >= -r {
let (x, y) = (i % w.max(1), i / w.max(1));
(x0, y0, x1, y1) = (x0.min(x), y0.min(y), x1.max(x), y1.max(y));
}
}
(x0 <= x1).then(|| [x0.saturating_sub(pad), y0.saturating_sub(pad), x1.saturating_add(pad + 1).min(w), y1.saturating_add(pad + 1).min(h)])
}
/// The pixels of `rect` (row-major) of a `w`-wide plane.
fn crop_of<T: Copy>(src: &[T], w: usize, rect: [usize; 4]) -> Vec<T> {
let [x0, y0, x1, y1] = rect;
(y0..y1).flat_map(|y| src.get(y * w + x0..y * w + x1).unwrap_or(&[]).iter().copied()).collect()
}
/// Re-cut the band `|sd| <= r` around the edge of `labels` (the warped matte) with `soft` as the
/// prior; outside it the labels stay. `models`: the colour models, fitted on the whole frame when
/// `None`. With `crop` the cut runs on the bounding box of the band and the core, padded by the
/// reach of the prior blur: outside that box every pixel is background more than `r` from the
/// edge, the free pixels, their neighbours and the seeds are the same, and every free pixel sees
/// the same blur window as on the full frame.
fn recut_band(rgb: &[[f32; 3]], size: (usize, usize), labels: &mut [u8], soft: &[f32], r: f32, models: Option<(&Gmm, &Gmm)>, crop: bool) {
let (w, h) = size;
let fitted;
let models = match models {
Some(m) => m,
None => {
fitted = fit_models(rgb, labels);
(&fitted.0, &fitted.1)
}
};
let sd = matting::signed_distance(labels, w, h);
let free: Vec<bool> = sd.iter().map(|d| d.abs() <= r).collect();
// The seeds of `core_of(soft, ..)`: `labels` is `soft >= 0.5`, so this is its core.
let core: Vec<bool> = sd.iter().map(|d| *d > r).collect();
let seeds: Vec<bool> = if core.iter().any(|c| *c) { core } else { labels.iter().map(|v| *v != 0).collect() };
let sigma = (r as f64 / 4.0).max(1.0);
let full = [0, 0, w, h];
let rect = if crop { band_rect(&sd, size, r, matting::gauss_reach(sigma).max(1)) } else { Some(full) };
// No band and no core: there is no foreground, so nothing is free and `clean` keeps all.
let Some(rect) = rect else { return };
if rect == full {
cut_band(&Band { size, rgb, soft, free: &free, seeds: &seeds }, labels, sigma, models);
return;
}
let [x0, y0, x1, y1] = rect;
let cw = x1 - x0;
let (rgb_c, soft_c, free_c, seeds_c) = (crop_of(rgb, w, rect), crop_of(soft, w, rect), crop_of(&free, w, rect), crop_of(&seeds, w, rect));
let mut cl = crop_of(labels, w, rect);
cut_band(&Band { size: (cw, y1 - y0), rgb: &rgb_c, soft: &soft_c, free: &free_c, seeds: &seeds_c }, &mut cl, sigma, models);
for (y, row) in (y0..y1).zip(cl.chunks(cw.max(1))) {
if let Some(dst) = labels.get_mut(y * w + x0..y * w + x1) {
dst.copy_from_slice(row);
}
}
}
/// Propagate the previous frame's segmentation to the next frame: warp it, then re-cut in a
/// band of Search Radius pixels around the warped boundary. Strokes on the next frame re-cut
/// the whole frame with the warped matte as a soft prior instead.
pub fn propagate(prev_img: &Image, prev: &FrameSeg, next_img: &Image, strokes: &[&Stroke], opts: &SegOpts, refine_radius: f64) -> FrameSeg {
let (w, h) = (next_img.width as usize, next_img.height as usize);
let prior = warp_prior(prev_img, prev, next_img, opts);
if strokes.iter().any(|s| s.kind.is_segmentation()) {
return segment(next_img, strokes, Some(&prior), opts, refine_radius);
}
let rgb = rgb_of(next_img);
let mut labels: Vec<u8> = prior.soft.iter().map(|v| (*v >= 0.5) as u8).collect();
let r = (opts.search_radius * opts.scale).max(2.0) as f32;
let models = (!prev.fg.is_empty() && !prev.bg.is_empty()).then_some((&prev.fg, &prev.bg));
recut_band(&rgb, (w, h), &mut labels, &prior.soft, r, models, true);
finish(next_img, &rgb, labels, strokes, Some(&prior.refine), opts, refine_radius)
}
/// Points spread along a stroke (matte pixels), about one per stroke width, at most `max`.
fn points_along(s: &Stroke, scale: f64, max: usize) -> Vec<[f32; 2]> {
let pts: Vec<[f64; 2]> = s.points.iter().map(|p| [p[0] * scale, p[1] * scale]).collect();
let len: f64 = pts.windows(2).map(|w| (w[1][0] - w[0][0]).hypot(w[1][1] - w[0][1])).sum();
let step = (2.0 * s.radius * scale).max(len / max.max(1) as f64).max(1.0);
let mut out = pts.first().map(|p| vec![[p[0] as f32, p[1] as f32]]).unwrap_or_default();
let mut carry = 0.0;
for w in pts.windows(2) {
let d = (w[1][0] - w[0][0]).hypot(w[1][1] - w[0][1]);
let mut t = step - carry;
while t <= d && out.len() < max {
let f = t / d.max(1e-9);
out.push([(w[0][0] + (w[1][0] - w[0][0]) * f) as f32, (w[0][1] + (w[1][1] - w[0][1]) * f) as f32]);
t += step;
}
carry = (carry + d) % step;
}
out
}
/// A tracker's prompt from a frame's strokes (points along the foreground and background strokes,
/// in frame pixels at `scale`).
///
/// SAM 2 was trained on a handful of clicks: with sixteen or more points it doubts its own mask
/// (measured: confidence 0.25 with 16 points, 0.00 with 32, 0.99 with 1 to 7), so this picks at
/// most [`TRACKER_FG_POINTS`] foreground and [`TRACKER_BG_POINTS`] background points, spread
/// along the strokes. Like [`stroke_prompt`], later corrections win over earlier paint.
pub fn tracker_prompt(strokes: &[&Stroke], scale: f64, w: usize, h: usize) -> Prompt {
let hard = resolve(strokes, StrokeKind::Fg, StrokeKind::Bg, scale, w, h);
let prompt = stroke_prompt(strokes, &hard, scale, w, h);
let mut points = vec![];
for (fg, max) in [(true, TRACKER_FG_POINTS), (false, TRACKER_BG_POINTS)] {
let all: Vec<[f32; 2]> = prompt.points.iter().filter_map(|(p, label)| (*label == fg).then_some(*p)).collect();
let n = all.len().min(max);
// evenly spaced picks, keeping the first and the last
points.extend((0..n).filter_map(|i| all.get(if n > 1 { i * (all.len() - 1) / (n - 1) } else { all.len() / 2 }).map(|p| (*p, fg))));
}
Prompt { points, ..prompt }
}
/// [`tracker_prompt`] plus a box around the classic engine's matte of the same strokes. Clicks alone
/// make SAM 2 pick the part they land on (a torso, not the legs and shoes: measured IoU 0.41 on a
/// multi-part figure, against 1.00 with the box); the box says how far the object reaches. A box
/// stroke the user drew wins over the matte's.
pub fn tracker_prompt_boxed(strokes: &[&Stroke], scale: f64, classic: &FrameSeg) -> Prompt {
let mut p = tracker_prompt(strokes, scale, classic.w, classic.h);
if p.bbox.is_none() {
let (w, h) = (classic.w, classic.h);
let (mut x0, mut y0, mut x1, mut y1) = (usize::MAX, usize::MAX, 0usize, 0usize);
for (i, v) in classic.matte.iter().enumerate() {
if *v != 0 && w > 0 {
let (x, y) = (i % w, i / w);
(x0, y0, x1, y1) = (x0.min(x), y0.min(y), x1.max(x), y1.max(y));
}
}
if x0 <= x1 {
let (mx, my) = (((x1 - x0) as f32 * 0.05).max(4.0), ((y1 - y0) as f32 * 0.05).max(4.0));
p.bbox = Some([(x0 as f32 - mx).max(0.0), (y0 as f32 - my).max(0.0), (x1 as f32 + 1.0 + mx).min(w as f32), (y1 as f32 + 1.0 + my).min(h as f32)]);
}
}
p
}
/// Most foreground / background points a tracker prompt carries.
pub const TRACKER_FG_POINTS: usize = 3;
pub const TRACKER_BG_POINTS: usize = 3;
/// A frame's segmentation from a tracker's probability map: the map is the shape prior of the
/// same graph cut as everywhere else, so the strokes stay hard constraints and the edges snap
/// to colour. An absent object gives an empty matte (strokes on the frame still win); a map of
/// the wrong size is ignored.
pub fn segment_tracked(img: &Image, strokes: &[&Stroke], prob: Vec<f32>, occluded: bool, opts: &SegOpts, refine_radius: f64) -> FrameSeg {
let (w, h) = (img.width as usize, img.height as usize);
if prob.len() != w * h || w == 0 || h == 0 {
return segment(img, strokes, None, opts, refine_radius);
}
let has_fg = strokes.iter().any(|s| s.kind == StrokeKind::Fg);
if (occluded || !prob.iter().any(|p| *p >= 0.5)) && !has_fg {
return FrameSeg::empty(w, h);
}
let prior = Prior { soft: prob, fg: Gmm::default(), bg: Gmm::default(), refine: vec![0; w * h], weight: MODEL_PRIOR };
segment(img, strokes, Some(&prior), opts, refine_radius)
}
/// A model's prompt from the strokes: points along the foreground and background strokes, but
/// not where a later stroke of the other kind painted over them (`hard`, from [`resolve`]), and
/// the box of a [`StrokeKind::Box`] stroke (matte pixels). A stroke painted over at every point
/// sampled along it, but not everywhere, is prompted from the middle of what is left of it.
pub fn stroke_prompt(strokes: &[&Stroke], hard: &[u8], scale: f64, w: usize, h: usize) -> Prompt {
let mut points = vec![];
for (kind, own, other) in [(StrokeKind::Fg, HARD_FG, HARD_BG), (StrokeKind::Bg, HARD_BG, HARD_FG)] {
let ss: Vec<&&Stroke> = strokes.iter().filter(|s| s.kind == kind).collect();
let per = (16 / ss.len().max(1)).max(1);
for s in ss {
let along = points_along(s, scale, per);
let mut kept: Vec<[f32; 2]> = along.iter().copied().filter(|p| owner(hard, w, h, *p) != Some(other)).collect();
if kept.is_empty() && !along.is_empty() {
kept.extend(deepest_owned(s, hard, own, scale, w, h));
}
points.extend(kept.into_iter().map(|p| (p, kind == StrokeKind::Fg)));
}
}
let bbox = strokes.iter().filter(|s| s.kind == StrokeKind::Box).find_map(|s| box_of(s, scale));
Prompt { points, bbox, ..Default::default() }
}
/// The value of `hard` under the point `p` (`None` outside the frame).
fn owner(hard: &[u8], w: usize, h: usize, p: [f32; 2]) -> Option<u8> {
if !(p[0] >= 0.0 && p[1] >= 0.0) {
return None;
}
let (x, y) = (p[0] as usize, p[1] as usize);
if x >= w || y >= h {
return None;
}
hard.get(y * w + x).copied()
}
/// The centre of the pixel deepest inside what `s` still owns (where `hard` is `own` under it),
/// if anything.
fn deepest_owned(s: &Stroke, hard: &[u8], own: u8, scale: f64, w: usize, h: usize) -> Option<[f32; 2]> {
let mut owned = vec![];
sweep(s, scale, w, h, |i| {
if hard.get(i) == Some(&own) {
owned.push((i % w, i / w));
}
});
let (x0, x1) = (owned.iter().map(|p| p.0).min()?, owned.iter().map(|p| p.0).max()?);
let (y0, y1) = (owned.iter().map(|p| p.1).min()?, owned.iter().map(|p| p.1).max()?);
// One pixel of margin all round, so depth is measured to the nearest pixel it doesn't own.
let (cw, ch) = (x1 - x0 + 3, y1 - y0 + 3);
let at = |(x, y): (usize, usize)| (y - y0 + 1) * cw + (x - x0 + 1);
let mut free = vec![true; cw * ch];
for p in &owned {
if let Some(v) = free.get_mut(at(*p)) {
*v = false;
}
}
let depth = matting::distance(&free, cw, ch);
let d = |p: &(usize, usize)| depth.get(at(*p)).copied().unwrap_or(0.0);
let (x, y) = owned.iter().copied().max_by(|a, b| d(a).total_cmp(&d(b)))?;
Some([x as f32 + 0.5, y as f32 + 0.5])
}
/// The box `[x0, y0, x1, y1]` (matte pixels) of a box stroke: its first two points as opposite
/// corners; `None` when they are missing, not finite or the box is empty.
fn box_of(s: &Stroke, scale: f64) -> Option<[f32; 4]> {
let (a, c) = (s.points.first()?, s.points.get(1)?);
let v = [a[0].min(c[0]), a[1].min(c[1]), a[0].max(c[0]), a[1].max(c[1])].map(|v| (v * scale) as f32);
(v.iter().all(|x| x.is_finite()) && v[2] > v[0] && v[3] > v[1]).then_some(v)
}
/// Add a prior matte to a prompt: its box (a little larger; unless the prompt has one), up to
/// four points spread through its core, and the matte itself, all with this frame's strokes
/// (`hard`, from [`resolve`]) painted over it.
fn add_prior_prompt(prompt: &mut Prompt, soft: &[f32], hard: &[u8], w: usize, h: usize) -> bool {
let soft: Vec<f32> = soft
.iter()
.enumerate()
.map(|(i, v)| match hard.get(i) {
Some(&HARD_FG) => 1.0,
Some(&HARD_BG) => 0.0,
_ => *v,
})
.collect();
let bin: Vec<u8> = soft.iter().map(|v| (*v >= 0.5) as u8).collect();
let (mut x0, mut y0, mut x1, mut y1) = (usize::MAX, usize::MAX, 0usize, 0usize);
for (i, v) in bin.iter().enumerate() {
if *v != 0 {
let (x, y) = (i % w, i / w);
(x0, y0, x1, y1) = (x0.min(x), y0.min(y), x1.max(x), y1.max(y));
}
}
if x0 > x1 {
return false;
}
let (mx, my) = (((x1 - x0) as f32 * 0.05).max(4.0), ((y1 - y0) as f32 * 0.05).max(4.0));
// A box the user drew on this frame wins over the prior's.
if prompt.bbox.is_none() {
prompt.bbox = Some([(x0 as f32 - mx).max(0.0), (y0 as f32 - my).max(0.0), (x1 as f32 + 1.0 + mx).min(w as f32), (y1 as f32 + 1.0 + my).min(h as f32)]);
}
// Farthest-point picks among the core (deep inside), starting from the deepest pixel.
let sd = matting::signed_distance(&bin, w, h);
let deep = sd.iter().copied().fold(0.0f32, f32::max);
let core: Vec<usize> = (0..w * h).filter(|i| sd[*i] >= (deep * 0.5).max(1.0)).step_by(((w * h) / 20_000).max(1)).collect();
let mut picks: Vec<usize> = core.iter().copied().max_by(|a, b| sd[*a].total_cmp(&sd[*b])).into_iter().collect();
while picks.len() < 4 {
let far = core.iter().copied().max_by_key(|c| picks.iter().map(|p| (c % w).abs_diff(p % w).pow(2) + (c / w).abs_diff(p / w).pow(2)).min().unwrap_or(0));
match far {
Some(f) if !picks.contains(&f) => picks.push(f),
_ => break,
}
}
prompt.points.extend(picks.into_iter().map(|i| ([(i % w) as f32 + 0.5, (i / w) as f32 + 0.5], true)));
prompt.mask = Some(soft);
true
}
/// [`segment`] with a trained model (if any): its matte for the strokes (and the propagated
/// prior) becomes a strong prior for the cut.
pub fn segment_with(img: &Image, strokes: &[&Stroke], prior: Option<&Prior>, opts: &SegOpts, refine_radius: f64, model: Option<&dyn MaskModel>) -> FrameSeg {
let (w, h) = (img.width as usize, img.height as usize);
let Some(m) = model.filter(|_| w > 0 && h > 0) else { return segment(img, strokes, prior, opts, refine_radius) };
let hard = resolve(strokes, StrokeKind::Fg, StrokeKind::Bg, opts.scale, w, h);
let mut prompt = stroke_prompt(strokes, &hard, opts.scale, w, h);
if let Some(p) = prior {
add_prior_prompt(&mut prompt, &p.soft, &hard, w, h);
}
if !prompt.points.iter().any(|(_, fg)| *fg) {
return segment(img, strokes, prior, opts, refine_radius);
}
match m.segment(&rgb_of(img), w, h, &prompt) {
Ok(soft) if soft.len() == w * h => {
let (fg, bg) = prior.map_or_else(Default::default, |p| (p.fg.clone(), p.bg.clone()));
let refine = prior.map_or_else(|| vec![0; w * h], |p| p.refine.clone());
segment(img, strokes, Some(&Prior { soft, fg, bg, refine, weight: MODEL_PRIOR }), opts, refine_radius)
}
_ => segment(img, strokes, prior, opts, refine_radius),
}
}
/// [`propagate`] with a trained model (if any): the model, prompted with the flow-warped matte,
/// re-segments the frame; when it disagrees with the flow (IoU under 0.5) the classical result
/// stands.
pub fn propagate_with(
prev_img: &Image,
prev: &FrameSeg,
next_img: &Image,
strokes: &[&Stroke],
opts: &SegOpts,
refine_radius: f64,
model: Option<&dyn MaskModel>,
) -> FrameSeg {
let (w, h) = (next_img.width as usize, next_img.height as usize);
let Some(m) = model.filter(|_| w > 0 && h > 0) else { return propagate(prev_img, prev, next_img, strokes, opts, refine_radius) };
let prior = warp_prior(prev_img, prev, next_img, opts);
let hard = resolve(strokes, StrokeKind::Fg, StrokeKind::Bg, opts.scale, w, h);
let mut prompt = stroke_prompt(strokes, &hard, opts.scale, w, h);
if !add_prior_prompt(&mut prompt, &prior.soft, &hard, w, h) {
return propagate(prev_img, prev, next_img, strokes, opts, refine_radius);
}
match m.segment(&rgb_of(next_img), w, h, &prompt) {
Ok(soft) if soft.len() == w * h => {
let a: Vec<u8> = soft.iter().map(|v| (*v >= 0.5) as u8).collect();
let b: Vec<u8> = prior.soft.iter().map(|v| (*v >= 0.5) as u8).collect();
if iou(&a, &b) < 0.5 {
return propagate(prev_img, prev, next_img, strokes, opts, refine_radius);
}
let p = Prior { soft, weight: MODEL_PRIOR, ..prior };
segment(next_img, strokes, Some(&p), opts, refine_radius)
}
_ => propagate(prev_img, prev, next_img, strokes, opts, refine_radius),
}
}
/// Intersection over union of two binary mattes.
pub fn iou(a: &[u8], b: &[u8]) -> f64 {
let (mut i, mut u) = (0usize, 0usize);
for (x, y) in a.iter().zip(b) {
let (x, y) = (*x != 0, *y != 0);
i += (x && y) as usize;
u += (x || y) as usize;
}
if u == 0 { 1.0 } else { i as f64 / u as f64 }
}
#[cfg(test)]
mod tests;
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.