distance_transform/
dt.rs

1//! This module contains the functions for calculating the distance transform.
2
3pub use super::grid::*;
4use std::f64;
5
6const INF: f64 = f64::MAX;
7
8/* dt of 1d function using squared distance */
9fn dt1d_float(f: &Vec<f64>) -> Vec<f64> {
10    let mut d = vec![0f64; f.len()];
11    let mut v = vec![0i32; f.len()];
12    let mut z = vec![0f64; f.len() + 1];
13    let mut k = 0i32;
14    v[0] = 0;
15    z[0] = -INF;
16    z[1] = INF;
17
18    for q in 1..f.len() {
19        let mut s = ((f[q]+(q*q) as f64)-(f[v[k as usize] as usize]+(v[k as usize]*v[k as usize]) as f64))/(2*q as i32-2*v[k as usize]) as f64;
20        while s <= z[k as usize] {
21            k -= 1;
22            s = ((f[q]+(q*q) as f64)-(f[v[k as usize] as usize]+(v[k as usize]*v[k as usize]) as f64))/(2*q as i32-2*v[k as usize]) as f64;
23        }
24        k += 1;
25        v[k as usize] = q as i32;
26        z[k as usize] = s;
27        z[k as usize + 1] = INF;
28    }
29
30    k = 0;
31    for q in 0..f.len() {
32        while z[k as usize + 1] <= q as f64 {
33            k += 1;
34        }
35        d[q] = ((q as i32-v[k as usize])*(q as i32-v[k as usize])) as f64 + f[v[k as usize] as usize];
36    }
37
38    d
39}
40
41/* dt of 2d function using squared distance */
42fn dt2d_float(im: &FloatGrid) -> FloatGrid {
43    let mut im = im.clone();
44    let width = im.width();
45    let height = im.height();
46    let mut f = vec![0f64; if width > height { width } else { height }];
47
48    // transform along columns
49    for x in 0..width {
50        for y in 0..height {
51            f[y] = *im.get(x, y).unwrap();
52        }
53        let d = dt1d_float(&f);
54        for y in 0..height {
55            im.set(x, y, d[y]);
56        }
57    }
58
59    // transform along rows
60    for y in 0..height {
61        for x in 0..width {
62            f[x] = *im.get(x, y).unwrap();
63        }
64        let d = dt1d_float(&f);
65        for x in 0..width {
66            im.set(x, y, d[x]);
67        }
68    }
69
70    im
71}
72
73/// distance transform of boolean vector using Squared Euclidean distance
74pub fn dt1d(im: &Vec<bool>) -> Vec<f64> {
75    let mut out = Vec::with_capacity(im.len());
76    for x in 0..im.len() {
77        out[x] = if im[x] { 0. } else { INF };
78    }
79
80    dt1d_float(&out)
81}
82
83/// distance transform of binary image using Squared Euclidean distance
84pub fn dt2d(im: &BoolGrid) -> FloatGrid {
85    let width = im.width();
86    let height = im.height();
87
88    let mut out = FloatGrid::new(width, height);
89    for (x, y, &val) in im.iter() {
90        out.set(x, y, if val { 0. } else { INF });
91    }
92
93    dt2d_float(&out)
94}
distance_transform/dt.rs

distance_transform/
dt.rs
