856f865cf98d
regions.rs
//! Regions: connected areas of one tone band, and the merge of small ones into their neighbours.
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap};
use std::hash::BuildHasherDefault;
use super::util::{FxHasher, find};
use super::{Px, Settings};
/// 4-connected components of equal labels, numbered in raster order of their first pixel.
pub(super) fn components(labels: &[u8], w: usize, h: usize) -> (Vec<u32>, usize) {
let mut comp = vec![0u32; w * h];
let mut parent: Vec<u32> = Vec::new();
for y in 0..h {
for x in 0..w {
let i = y * w + x;
let up = (y > 0 && labels[i - w] == labels[i]).then(|| comp[i - w]);
let left = (x > 0 && labels[i - 1] == labels[i]).then(|| comp[i - 1]);
comp[i] = match (up, left) {
(Some(a), Some(b)) => {
let (ra, rb) = (find(&mut parent, a), find(&mut parent, b));
let (lo, hi) = (ra.min(rb), ra.max(rb));
parent[hi as usize] = lo;
lo
}
(Some(a), None) | (None, Some(a)) => a,
(None, None) => {
parent.push(parent.len() as u32);
parent.len() as u32 - 1
}
};
}
}
let mut index = vec![u32::MAX; parent.len()];
let mut n = 0u32;
for c in comp.iter_mut() {
let root = find(&mut parent, *c) as usize;
if index[root] == u32::MAX {
index[root] = n;
n += 1;
}
*c = index[root];
}
(comp, n as usize)
}
/// Merges components smaller than the Edge Simplicity area into the neighbour they share the most
/// border with. Returns each pixel's region and each region's mean colour.
pub(super) fn merge_regions(comp: &[u32], n: usize, c: &[Px], w: usize, h: usize, s: &Settings) -> (Vec<u32>, Vec<Px>) {
let mut area = vec![0u32; n];
let mut sum = vec![[0.0f64; 3]; n];
for (&k, p) in comp.iter().zip(c) {
let k = k as usize;
area[k] += 1;
sum[k] = [sum[k][0] + f64::from(p[0]), sum[k][1] + f64::from(p[1]), sum[k][2] + f64::from(p[2])];
}
// Shared border lengths, in cracks.
let mut shared: HashMap<u64, u32, BuildHasherDefault<FxHasher>> = HashMap::default();
for y in 0..h {
for x in 0..w {
let a = comp[y * w + x];
for (nx, ny) in [(x + 1, y), (x, y + 1)] {
if nx < w && ny < h {
let b = comp[ny * w + nx];
if a != b {
*shared.entry((u64::from(a.min(b)) << 32) | u64::from(a.max(b))).or_insert(0) += 1;
}
}
}
}
}
let mut adj: Vec<Vec<(u32, u32)>> = vec![Vec::new(); n];
let mut pairs: Vec<(u64, u32)> = shared.into_iter().collect();
pairs.sort_unstable();
for (key, len) in pairs {
let (a, b) = ((key >> 32) as u32, key as u32);
adj[a as usize].push((b, len));
adj[b as usize].push((a, len));
}
let min_area = s.min_area();
let mergeable = |a: u32| a < min_area;
let mut parent: Vec<u32> = (0..n as u32).collect();
let mut heap: BinaryHeap<Reverse<(u32, u32)>> = (0..n).filter(|&i| mergeable(area[i])).map(|i| Reverse((area[i], i as u32))).collect();
while let Some(Reverse((a, id))) = heap.pop() {
let i = id as usize;
if find(&mut parent, id) != id || area[i] != a || !mergeable(a) {
continue;
}
// The neighbours as they are now, with their total shared border.
let mut nb: Vec<(u32, u32)> = std::mem::take(&mut adj[i]).into_iter().map(|(k, len)| (find(&mut parent, k), len)).filter(|&(k, _)| k != id).collect();
nb.sort_unstable();
nb.dedup_by(|b, a| {
if a.0 == b.0 {
a.1 += b.1;
true
} else {
false
}
});
let Some(&(t, _)) = nb.iter().max_by(|a, b| a.1.cmp(&b.1).then(b.0.cmp(&a.0))) else {
adj[i] = nb;
continue;
};
let ti = t as usize;
parent[i] = t;
area[ti] += area[i];
sum[ti] = [sum[ti][0] + sum[i][0], sum[ti][1] + sum[i][1], sum[ti][2] + sum[i][2]];
// Appended as they are; resolved and summed when `t` itself merges.
adj[ti].extend(nb.into_iter().filter(|&(k, _)| k != t));
if mergeable(area[ti]) {
heap.push(Reverse((area[ti], t)));
}
}
let mut index = vec![u32::MAX; n];
let mut colours = Vec::new();
let mut reg = vec![0u32; comp.len()];
for (r, &k) in reg.iter_mut().zip(comp) {
let root = find(&mut parent, k) as usize;
if index[root] == u32::MAX {
index[root] = colours.len() as u32;
let a = f64::from(area[root].max(1));
colours.push([(sum[root][0] / a) as f32, (sum[root][1] / a) as f32, (sum[root][2] / a) as f32]);
}
*r = index[root];
}
(reg, colours)
}
#[cfg(test)]
mod tests {
use super::*;
fn settings(simplicity: f32) -> Settings {
Settings { levels: 4, simplicity, fidelity: 2.0 }
}
/// Labels drawn as text, one character per pixel.
fn labels(rows: &[&str]) -> (Vec<u8>, usize, usize) {
(rows.iter().flat_map(|r| r.bytes()).collect(), rows[0].len(), rows.len())
}
#[test]
fn components_are_four_connected_and_numbered_in_raster_order() {
let (l, w, h) = labels(&["aab", "abb", "bba"]);
let (comp, n) = components(&l, w, h);
// The top-left `a`s, the `b`s (one area), then the lone `a` (touching the first only
// diagonally), in the order their first pixels come.
assert_eq!(n, 3);
assert_eq!(comp, vec![0, 0, 1, 0, 1, 1, 1, 1, 2]);
// A U shape: both arms are found as separate runs first and joined further down.
let (l, w, h) = labels(&["a.a", "a.a", "aaa"]);
let (comp, n) = components(&l, w, h);
assert_eq!(n, 2);
assert_eq!(comp[0], comp[2]);
}
/// Regions from labels, with one flat colour per label.
fn merged(rows: &[&str], simplicity: f32) -> (Vec<u32>, Vec<Px>) {
let (l, w, h) = labels(rows);
let c: Vec<Px> = l.iter().map(|&b| [f32::from(b - b'a') / 4.0; 3]).collect();
let (comp, n) = components(&l, w, h);
merge_regions(&comp, n, &c, w, h, &settings(simplicity))
}
#[test]
fn small_regions_merge_into_the_neighbour_they_share_most_border_with() {
let rows = ["aaaaaaaaaa", "aaaaaaaaaa", "aacaaaaaaa", "aaccbbbbbb", "aaaabbbbbb", "aaaabbbbbb", "aaaabbbbbb", "aaaabbbbbb"];
// At Edge Simplicity 0 a region needs 25 pixels: the three `c`s go into the `a`s, which
// they share six cracks with (one with the `b`s); the 30 `b`s stay.
let (reg, colours) = merged(&rows, 0.0);
assert_eq!(colours.len(), 2);
assert_eq!(reg[2 * 10 + 2], reg[0]);
assert_ne!(reg[3 * 10 + 4], reg[0]);
// A region's colour is the mean of its pixels: 47 `a`s (0.0) and 3 `c`s (0.5).
let a = colours[reg[0] as usize][0];
assert!((a - 1.5 / 50.0).abs() < 1e-6, "{a}");
// At 4 a region needs 100 pixels, so the `b`s merge too.
assert_eq!(merged(&rows, 4.0).1.len(), 1);
}
}
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.