Rust-edt

使用Saito算法在纯Rust中实现2D EDT（欧几里得距离变换）

还有其他crate实现了EDT，但我希望重新设计一个具有以下优点的轮子

• 无依赖（除了示例代码）
• 使用直观（接受数值切片和形状）

性能不是首要任务，但我希望探索更多的优化。

EDT是许多算法的基础，但在通用图像处理库中很难找到，可能是因为该算法难以高效实现。这个crate提供了一种在文献中提出的相当高效的算法实现的EDT。

这个crate使用的算法（Saito算法）的时间复杂度是O(n^3)，其中n是沿一个方向像素的数量。直观的EDT计算将是O(n^4)，因此它肯定比这要好，但还有基于快速行进的算法，其时间复杂度是O(n^2)。

快速行进法

快速行进法是一种使用扩展波前（有时称为草火类比）的算法策略。技术上，它是一种解决Eikonal PDE并具有已知误差界限的方法。它特别适用于EDT，因为它具有O(n^2)的复杂度，这对于大图像来说是有益的。

在我具体的1024 x 1024像素图像环境中，它具有以下显著差异。

• 精确EDT：2900ms
• 快速行进EDT：93.7ms

然而，它的缺点是不能生成精确的（真实）EDT。话虽如此，FMM对于大多数应用来说已经足够准确。

库有一个带有进度回调的功能，你可以用它来生成如下所示的动画。

精确版和快速行进版之间的差异可以如下可视化（见示例-edt），可以通过

cargo r --release --example edt -- Rust_logo.png -d

用法

添加依赖项

[dependencies]
edt = "0.2.1"

准备一个二值图像作为平坦的vec。这个库假设输入是一个二维图像的平坦vec。您可以使用元组指定维度。

let mut vec: Vec<bool> = vec![/*...*/];
let dims = (32, 32);

如果您想从图像中读取输入，可以使用image包。在这种情况下，请确保将其添加到您项目的依赖中。

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();

使用给定的形状调用edt。

use edt::edt;

let edt_image = edt(&vec, (dims.0 as usize, dims.1 as usize), true);

如果您想保存到文件，下面的代码将使用最大值将值归一化到8位灰度图像。

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(dims.0, dims.1, edt_img).unwrap();

// Write the contents of this image to the Writer in PNG format.
edt_img.save("edt.png").unwrap();

有关更多信息，请参阅示例文件夹。

文献

二维欧几里得距离变换算法：比较调查

这篇论文是该研究领域的一个很好的总结。

doi=10.1.1.66.2644

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.2644&rep=rep1&type=pdf

第7.7节

Saito和Toriwaki [1994]（原始论文）

https://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Saito94.pdf

快速行进法简介

迪杰斯特拉和快速行进算法（Matlab教程）