edt/

lib.rs

//! # edt
//!
//! An implementation of 2D EDT ([Euclidean distance transform](https://en.wikipedia.org/wiki/Distance_transform)) with Saito's algorithm in pure Rust
//!
//! There are also [other](https://crates.io/crates/distance-transform)
//! [crates](https://crates.io/crates/dt) that implements EDT,
//! but I would like to reinvent a wheel that has these advantages:
//!
//! * No dependencies (except example codes)
//! * Intuitive to use (accepts a numerical slice and a shape)
//!
//! Performance was not the priority, but I would like to explore more optimizations.
//!
//! EDT is the basis of many algorithms, but it is hard to find in a general purpose image processing library,
//! probably because the algorithm is not trivial to implement efficiently.
//! This crate provides an implementation of EDT in fairly efficient algorithm presented in the literature.
//!
//! The algorithm used in this crate (Saito's algorithm) is O(n^3), where n is the number of pixels along one direction.
//! Naive computation of EDT would be O(n^4), so it is certainly better than that, but there is also fast-marching based
//! algorithm that is O(n^2).
//!
//!
//! ### Fast Marching Method
//!
//! Fast Marching method is a strategy of algorithms that use expanding wavefront
//! (sometimes called grassfire analogy).
//! Tehcnically, it is a method to solve Eikonal PDE with known margin of error.
//! It is especially useful with EDT, because it has O(n^2) complexity, which is beneficial in large images.
//!
//! In my specific environment with 1024 x 1024 pixels image, it has significant
//! difference like below.
//!
//! * Exact EDT: 2900ms
//! * Fast Marching EDT: 93.7ms
//!
//! However, it has downside that it cannot produce exact (true) EDT.
//! That said, FMM has enough accuracy for most applications.
//!
//! The library has a function with progress callback that you can use to produce nice animation like below.
//!
//! ![Rust-logo-fmm](https://raw.githubusercontent.com/msakuta/msakuta.github.io/master/images/showcase/Rust_logo_animated.gif)
//!
//! The difference between exact and Fast Marching versions can be visualized like below (see
//! [example-edt](https://github.com/msakuta/rust-edt/blob/master/examples/edt.rs))
//! which can be run by
//!
//! ```bash
//! cargo r --release --example edt -- Rust_logo.png -d
//! ```
//!
//! ![Rust-logo-edt](https://raw.githubusercontent.com/msakuta/rust-edt/master/Rust_logo_diff.png)
//!
//!
//! ## Usage
//!
//! Add dependency
//!
//! ```toml
//! [dependencies]
//! edt = "0.2.1"
//! ```
//!
//! Prepare a binary image as a flattened vec.
//! This library assumes that the input is a flat vec for 2d image.
//! You can specify the dimensions with a tuple.
//!
//! ```rust
//! let vec: Vec<bool> = vec![/*...*/];
//! let dims = (32, 32);
//! ```
//!
//! If you want to read input from an image, you can use [image](https://crates.io/crates/image) crate.
//! Make sure to put it to your project's dependencies in that case.
//!
//! ```rust
//! use image::GenericImageView;
//! let img = image::open("Rust_logo.png").unwrap();
//! let dims = img.dimensions();
//! let img2 = img.into_luma8();
//! let flat_samples = img2.as_flat_samples();
//! let vec = flat_samples.image_slice().unwrap();
//! ```
//!
//! Call edt with given shape
//!
//! ```rust
//! # let vec: Vec<bool> = vec![false; 32 * 32];
//! # let dims = (32, 32);
//! use edt::edt;
//!
//! let edt_image = edt(&vec, (dims.0 as usize, dims.1 as usize), true);
//! ```
//!
//! Save to a file if you want.
//! The code below normalizes the value with maximum value to 8 bits grayscale image.
//!
//! ```rust
//! # use edt::edt;
//! # let vec: Vec<bool> = vec![false; 32 * 32];
//! # let edt_image = edt(&vec, (32, 32), true);
//! use image::{ImageBuffer, Luma};
//!
//! let max_value = edt_image.iter().map(|p| *p).reduce(f64::max).unwrap();
//! let edt_img = edt_image
//!     .iter()
//!     .map(|p| (*p / max_value * 255.) as u8)
//!     .collect();
//!
//! let edt_img: ImageBuffer<Luma<u8>, Vec<u8>> =
//!     ImageBuffer::from_vec(32, 32, edt_img).unwrap();
//!
//! // Write the contents of this image to the Writer in PNG format.
//! edt_img.save("edt.png").unwrap();
//! ```
//!
//! See [examples](https://github.com/msakuta/rust-edt/tree/master/examples) folder for more.
//!
//! ## Literature
//!
//! ### 2D Euclidean Distance Transform Algorithms: A Comparative Survey
//!
//! This paper is a great summary of this field of research.
//!
//! doi=10.1.1.66.2644
//!
//! <https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.2644&rep=rep1&type=pdf>
//!
//! Section 7.7
//!
//!
//! ### Saito and Toriwaki \[1994\] (Original paper)
//!
//! <https://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Saito94.pdf>
//!
//!
//! ### An introduction to Fast Marching Method
//!
//! [Dijkstra and Fast Marching Algorithms (tutorial in Matlab)](https://www.numerical-tours.com/matlab/fastmarching_0_implementing/)

mod exact_edt;
mod fast_marcher;
mod primitive_impl;

/// A trait for types that can be interpreted as a bool.
///
/// Primitive numerical types (integers and floats) implement this trait,
/// so you don't have to implement this by yourself.
/// However, you could implement it for your own custom type, if you want.
///
/// We don't use [num](https://crates.io/crates/num) crate because it is overkill for our purposes.
pub trait BoolLike {
    fn as_bool(&self) -> bool;
}

pub use exact_edt::{edt, edt_sq};
pub use fast_marcher::{edt_fmm, edt_fmm_cb, FMMCallbackData, GridPos};

#[cfg(test)]
mod test_util;