From 5ac571d8d16a307cea2922587185557bc773e8ed Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 2 May 2020 13:52:28 -0400 Subject: frontier: New trait for choosing color locations --- src/frontier.rs | 18 ++++++++++++++++++ 1 file changed, 18 insertions(+) create mode 100644 src/frontier.rs (limited to 'src/frontier.rs') diff --git a/src/frontier.rs b/src/frontier.rs new file mode 100644 index 0000000..2c6f43a --- /dev/null +++ b/src/frontier.rs @@ -0,0 +1,18 @@ +//! Frontiers on which to place pixels. + +use crate::color::Rgb8; + +/// A frontier of pixels. +pub trait Frontier { + /// The width of the image. + fn width(&self) -> u32; + + /// The height of the image. + fn height(&self) -> u32; + + /// The number of pixels currently on the frontier. + fn len(&self) -> usize; + + /// Place the given color on the frontier, and return its position. + fn place(&mut self, rgb8: Rgb8) -> Option<(u32, u32)>; +} -- cgit v1.2.3 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 (limited to 'src/frontier.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 From dd2336f76bfaff01ccb5b57f4453629ff62016b3 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 2 May 2020 13:57:30 -0400 Subject: frontier/min: Implement min selection --- src/frontier.rs | 61 +++++++++++++++++++++ src/frontier/min.rs | 150 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 211 insertions(+) create mode 100644 src/frontier/min.rs (limited to 'src/frontier.rs') diff --git a/src/frontier.rs b/src/frontier.rs index 1c5a173..e1b6528 100644 --- a/src/frontier.rs +++ b/src/frontier.rs @@ -1,6 +1,7 @@ //! Frontiers on which to place pixels. pub mod image; +pub mod min; use crate::color::{ColorSpace, Rgb8}; use crate::metric::kd::Cartesian; @@ -8,6 +9,7 @@ use crate::metric::soft::SoftDelete; use crate::metric::Metric; use std::cell::Cell; +use std::rc::Rc; /// A frontier of pixels. pub trait Frontier { @@ -85,3 +87,62 @@ impl SoftDelete for Pixel { self.deleted.get() } } + +impl> Metric<[f64]> for Rc> { + type Distance = C::Distance; + + fn distance(&self, other: &[f64]) -> Self::Distance { + (**self).distance(other) + } +} + +impl Metric>> for C { + type Distance = C::Distance; + + fn distance(&self, other: &Rc>) -> Self::Distance { + self.distance(&other.color) + } +} + +impl Metric for Rc> { + type Distance = C::Distance; + + fn distance(&self, other: &Self) -> Self::Distance { + (**self).distance(&**other) + } +} + +impl Cartesian for Rc> { + fn dimensions(&self) -> usize { + (**self).dimensions() + } + + fn coordinate(&self, i: usize) -> f64 { + (**self).coordinate(i) + } +} + +impl SoftDelete for Rc> { + fn is_deleted(&self) -> bool { + (**self).is_deleted() + } +} + +/// Return all the neighbors of a pixel location. +fn neighbors(x: u32, y: u32) -> [(u32, u32); 8] { + let xm1 = x.wrapping_sub(1); + let ym1 = y.wrapping_sub(1); + let xp1 = x + 1; + let yp1 = y + 1; + + [ + (xm1, ym1), + (xm1, y), + (xm1, yp1), + (x, ym1), + (x, yp1), + (xp1, ym1), + (xp1, y), + (xp1, yp1), + ] +} diff --git a/src/frontier/min.rs b/src/frontier/min.rs new file mode 100644 index 0000000..b22b290 --- /dev/null +++ b/src/frontier/min.rs @@ -0,0 +1,150 @@ +//! Minimum selection frontier. + +use super::{neighbors, Frontier, Pixel}; + +use crate::color::{ColorSpace, Rgb8}; +use crate::metric::soft::SoftKdForest; +use crate::metric::NearestNeighbors; + +use rand::Rng; + +use std::rc::Rc; + +/// A pixel on a min frontier. +#[derive(Debug)] +struct MinPixel { + pixel: Option>>, + filled: bool, +} + +impl MinPixel { + fn new() -> Self { + Self { + pixel: None, + filled: false, + } + } +} + +/// A [Frontier] that places colors on a neighbor of the closest pixel so far. +#[derive(Debug)] +pub struct MinFrontier { + rng: R, + pixels: Vec>, + forest: SoftKdForest>>, + width: u32, + height: u32, + x0: u32, + y0: u32, + len: usize, + deleted: usize, +} + +impl MinFrontier { + /// Create a MinFrontier with the given dimensions and initial pixel location. + pub fn new(rng: R, width: u32, height: u32, x0: u32, y0: u32) -> Self { + let size = (width as usize) * (height as usize); + let mut pixels = Vec::with_capacity(size); + for _ in 0..size { + pixels.push(MinPixel::new()); + } + + Self { + rng, + pixels, + forest: SoftKdForest::new(), + width, + height, + x0, + y0, + len: 0, + deleted: 0, + } + } + + fn pixel_index(&self, x: u32, y: u32) -> usize { + debug_assert!(x < self.width); + debug_assert!(y < self.height); + + (x + y * self.width) as usize + } + + fn free_neighbor(&mut self, x: u32, y: u32) -> Option<(u32, u32)> { + // Pick a pseudo-random neighbor + let offset: usize = self.rng.gen(); + + let neighbors = neighbors(x, y); + for i in 0..8 { + let (x, y) = neighbors[(i + offset) % 8]; + if x < self.width && y < self.height { + let i = self.pixel_index(x, y); + if !self.pixels[i].filled { + return Some((x, y)); + } + } + } + + None + } + + fn fill(&mut self, x: u32, y: u32, color: C) -> Option<(u32, u32)> { + let i = self.pixel_index(x, y); + let pixel = &mut self.pixels[i]; + if pixel.filled { + return None; + } + + let rc = Rc::new(Pixel::new(x, y, color)); + pixel.pixel = Some(rc.clone()); + pixel.filled = true; + + if self.free_neighbor(x, y).is_some() { + self.forest.push(rc); + self.len += 1; + } + + for &(x, y) in &neighbors(x, y) { + if x < self.width && y < self.height && self.free_neighbor(x, y).is_none() { + let i = self.pixel_index(x, y); + if let Some(pixel) = self.pixels[i].pixel.take() { + pixel.delete(); + self.deleted += 1; + } + } + } + + if 2 * self.deleted >= self.len { + self.forest.rebuild(); + self.len -= self.deleted; + self.deleted = 0; + } + + Some((x, y)) + } +} + +impl Frontier for MinFrontier { + 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); + let (x, y) = self + .forest + .nearest(&color) + .map(|n| n.item.pos) + .map(|(x, y)| self.free_neighbor(x, y).unwrap()) + .unwrap_or((self.x0, self.y0)); + + self.fill(x, y, color) + } +} -- cgit v1.2.3 From b58924b5a2534f845b996a2d58ab618301f1d450 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sat, 2 May 2020 13:58:14 -0400 Subject: frontier/mean: Implement mean selection --- src/frontier.rs | 1 + src/frontier/mean.rs | 140 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 141 insertions(+) create mode 100644 src/frontier/mean.rs (limited to 'src/frontier.rs') diff --git a/src/frontier.rs b/src/frontier.rs index e1b6528..7143cb7 100644 --- a/src/frontier.rs +++ b/src/frontier.rs @@ -1,6 +1,7 @@ //! Frontiers on which to place pixels. pub mod image; +pub mod mean; pub mod min; use crate::color::{ColorSpace, Rgb8}; diff --git a/src/frontier/mean.rs b/src/frontier/mean.rs new file mode 100644 index 0000000..889c5ba --- /dev/null +++ b/src/frontier/mean.rs @@ -0,0 +1,140 @@ +//! Mean selection frontier. + +use super::{neighbors, Frontier, Pixel}; + +use crate::color::{ColorSpace, Rgb8}; +use crate::metric::soft::SoftKdForest; +use crate::metric::NearestNeighbors; + +use std::iter; +use std::rc::Rc; + +/// A pixel on a mean frontier. +#[derive(Debug)] +enum MeanPixel { + Empty, + Fillable(Rc>), + Filled(C), +} + +impl MeanPixel { + fn filled_color(&self) -> Option { + match self { + Self::Filled(color) => Some(*color), + _ => None, + } + } +} + +/// A [Frontier] that looks at the average color of each pixel's neighbors. +pub struct MeanFrontier { + pixels: Vec>, + forest: SoftKdForest>>, + width: u32, + height: u32, + len: usize, + deleted: usize, +} + +impl MeanFrontier { + /// Create a MeanFrontier with the given dimensions and initial pixel location. + pub fn new(width: u32, height: u32, x0: u32, y0: u32) -> Self { + let size = (width as usize) * (height as usize); + let mut pixels = Vec::with_capacity(size); + for _ in 0..size { + pixels.push(MeanPixel::Empty); + } + + let pixel0 = Rc::new(Pixel::new(x0, y0, C::from(Rgb8::from([0, 0, 0])))); + let i = (x0 + y0 * width) as usize; + pixels[i] = MeanPixel::Fillable(pixel0.clone()); + + Self { + pixels, + forest: iter::once(pixel0).collect(), + width, + height, + len: 1, + deleted: 0, + } + } + + fn pixel_index(&self, x: u32, y: u32) -> usize { + debug_assert!(x < self.width); + debug_assert!(y < self.height); + + (x + y * self.width) as usize + } + + fn fill(&mut self, x: u32, y: u32, color: C) { + let i = self.pixel_index(x, y); + match &self.pixels[i] { + MeanPixel::Empty => {} + MeanPixel::Fillable(pixel) => { + pixel.delete(); + self.deleted += 1; + } + _ => unreachable!(), + } + self.pixels[i] = MeanPixel::Filled(color); + + let mut pixels = Vec::new(); + for &(x, y) in &neighbors(x, y) { + if x < self.width && y < self.height { + let i = self.pixel_index(x, y); + match &self.pixels[i] { + MeanPixel::Empty => {} + MeanPixel::Fillable(pixel) => { + pixel.delete(); + self.deleted += 1; + } + MeanPixel::Filled(_) => continue, + } + let color = C::average( + neighbors(x, y) + .iter() + .filter(|(x, y)| *x < self.width && *y < self.height) + .map(|(x, y)| self.pixel_index(*x, *y)) + .map(|i| &self.pixels[i]) + .map(MeanPixel::filled_color) + .flatten(), + ); + let pixel = Rc::new(Pixel::new(x, y, color)); + self.pixels[i] = MeanPixel::Fillable(pixel.clone()); + pixels.push(pixel); + } + } + + self.len += pixels.len(); + self.forest.extend(pixels); + + if 2 * self.deleted >= self.len { + self.forest.rebuild(); + self.len -= self.deleted; + self.deleted = 0; + } + } +} + +impl Frontier for MeanFrontier { + 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); + let (x, y) = self.forest.nearest(&color).map(|n| n.item.pos)?; + + self.fill(x, y, color); + + Some((x, y)) + } +} -- cgit v1.2.3