From da9b2ad1310e1db0ccb26a53181fa7f9b9033d04 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 2 May 2020 13:56:09 -0400 Subject: frontier/image: Implement image frontiers --- src/frontier.rs | 71 +++++++++++++++++++++++++++++++++++++++++++++++- src/frontier/image.rs | 74 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 144 insertions(+), 1 deletion(-) create mode 100644 src/frontier/image.rs diff --git a/src/frontier.rs b/src/frontier.rs index 2c6f43a..1c5a173 100644 --- a/src/frontier.rs +++ b/src/frontier.rs @@ -1,6 +1,13 @@ //! Frontiers on which to place pixels. -use crate::color::Rgb8; +pub mod image; + +use crate::color::{ColorSpace, Rgb8}; +use crate::metric::kd::Cartesian; +use crate::metric::soft::SoftDelete; +use crate::metric::Metric; + +use std::cell::Cell; /// A frontier of pixels. pub trait Frontier { @@ -16,3 +23,65 @@ pub trait Frontier { /// Place the given color on the frontier, and return its position. fn place(&mut self, rgb8: Rgb8) -> Option<(u32, u32)>; } + +/// A pixel on a frontier. +#[derive(Debug)] +struct Pixel { + pos: (u32, u32), + color: C, + deleted: Cell, +} + +impl Pixel { + fn new(x: u32, y: u32, color: C) -> Self { + Self { + pos: (x, y), + color, + deleted: Cell::new(false), + } + } + + fn delete(&self) { + self.deleted.set(true); + } +} + +impl Metric> for C { + type Distance = C::Distance; + + fn distance(&self, other: &Pixel) -> Self::Distance { + self.distance(&other.color) + } +} + +impl> Metric<[f64]> for Pixel { + type Distance = C::Distance; + + fn distance(&self, other: &[f64]) -> Self::Distance { + self.color.distance(other) + } +} + +impl Metric for Pixel { + type Distance = C::Distance; + + fn distance(&self, other: &Pixel) -> Self::Distance { + self.color.distance(&other.color) + } +} + +impl Cartesian for Pixel { + fn dimensions(&self) -> usize { + self.color.dimensions() + } + + fn coordinate(&self, i: usize) -> f64 { + self.color.coordinate(i) + } +} + +impl SoftDelete for Pixel { + fn is_deleted(&self) -> bool { + self.deleted.get() + } +} diff --git a/src/frontier/image.rs b/src/frontier/image.rs new file mode 100644 index 0000000..3655580 --- /dev/null +++ b/src/frontier/image.rs @@ -0,0 +1,74 @@ +//! Frontier that targets an image. + +use super::{Frontier, Pixel}; + +use crate::color::{ColorSpace, Rgb8}; +use crate::metric::soft::SoftKdTree; +use crate::metric::NearestNeighbors; + +use image::RgbImage; + +/// A [Frontier] that places colors on the closest pixel of a target image. +#[derive(Debug)] +pub struct ImageFrontier { + nodes: SoftKdTree>, + width: u32, + height: u32, + len: usize, + deleted: usize, +} + +impl ImageFrontier { + /// Create an ImageFrontier from an image. + pub fn new(img: &RgbImage) -> Self { + let width = img.width(); + let height = img.height(); + let len = (width as usize) * (height as usize); + + Self { + nodes: img + .enumerate_pixels() + .map(|(x, y, p)| Pixel::new(x, y, C::from(*p))) + .collect(), + width, + height, + len, + deleted: 0, + } + } +} + +impl Frontier for ImageFrontier { + fn width(&self) -> u32 { + self.width + } + + fn height(&self) -> u32 { + self.height + } + + fn len(&self) -> usize { + self.len - self.deleted + } + + fn place(&mut self, rgb8: Rgb8) -> Option<(u32, u32)> { + let color = C::from(rgb8); + + if let Some(node) = self.nodes.nearest(&color).map(|n| n.item) { + let pos = node.pos; + + node.delete(); + self.deleted += 1; + + if 32 * self.deleted >= self.len { + self.nodes.rebuild(); + self.len -= self.deleted; + self.deleted = 0; + } + + Some(pos) + } else { + None + } + } +} -- cgit v1.2.3