color: Implement color spaces

4 files changed, 580 insertions, 0 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 45602e1..7f81f15 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1,18 +1,120 @@
 # This file is automatically @generated by Cargo.
 # It is not intended for manual editing.
 [[package]]
+name = "adler32"
+version = "1.0.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5d2e7343e7fc9de883d1b0341e0b13970f764c14101234857d2ddafa1cb1cac2"
+
+[[package]]
 name = "autocfg"
 version = "1.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "f8aac770f1885fd7e387acedd76065302551364496e46b3dd00860b2f8359b9d"
 
 [[package]]
+name = "bitflags"
+version = "1.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
+
+[[package]]
+name = "bytemuck"
+version = "1.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "37fa13df2292ecb479ec23aa06f4507928bef07839be9ef15281411076629431"
+
+[[package]]
+name = "byteorder"
+version = "1.3.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "08c48aae112d48ed9f069b33538ea9e3e90aa263cfa3d1c24309612b1f7472de"
+
+[[package]]
 name = "cfg-if"
 version = "0.1.10"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "4785bdd1c96b2a846b2bd7cc02e86b6b3dbf14e7e53446c4f54c92a361040822"
 
 [[package]]
+name = "color_quant"
+version = "1.0.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0dbbb57365263e881e805dc77d94697c9118fd94d8da011240555aa7b23445bd"
+
+[[package]]
+name = "crc32fast"
+version = "1.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "ba125de2af0df55319f41944744ad91c71113bf74a4646efff39afe1f6842db1"
+dependencies = [
+ "cfg-if",
+]
+
+[[package]]
+name = "crossbeam-deque"
+version = "0.7.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9f02af974daeee82218205558e51ec8768b48cf524bd01d550abe5573a608285"
+dependencies = [
+ "crossbeam-epoch",
+ "crossbeam-utils",
+ "maybe-uninit",
+]
+
+[[package]]
+name = "crossbeam-epoch"
+version = "0.8.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "058ed274caafc1f60c4997b5fc07bf7dc7cca454af7c6e81edffe5f33f70dace"
+dependencies = [
+ "autocfg",
+ "cfg-if",
+ "crossbeam-utils",
+ "lazy_static",
+ "maybe-uninit",
+ "memoffset",
+ "scopeguard",
+]
+
+[[package]]
+name = "crossbeam-queue"
+version = "0.2.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c695eeca1e7173472a32221542ae469b3e9aac3a4fc81f7696bcad82029493db"
+dependencies = [
+ "cfg-if",
+ "crossbeam-utils",
+]
+
+[[package]]
+name = "crossbeam-utils"
+version = "0.7.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c3c7c73a2d1e9fc0886a08b93e98eb643461230d5f1925e4036204d5f2e261a8"
+dependencies = [
+ "autocfg",
+ "cfg-if",
+ "lazy_static",
+]
+
+[[package]]
+name = "deflate"
+version = "0.8.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e7e5d2a2273fed52a7f947ee55b092c4057025d7a3e04e5ecdbd25d6c3fb1bd7"
+dependencies = [
+ "adler32",
+ "byteorder",
+]
+
+[[package]]
+name = "either"
+version = "1.5.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "bb1f6b1ce1c140482ea30ddd3335fc0024ac7ee112895426e0a629a6c20adfe3"
+
+[[package]]
 name = "getrandom"
 version = "0.1.14"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -24,20 +126,145 @@ dependencies = [
 ]
 
 [[package]]
+name = "gif"
+version = "0.10.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "471d90201b3b223f3451cd4ad53e34295f16a1df17b1edf3736d47761c3981af"
+dependencies = [
+ "color_quant",
+ "lzw",
+]
+
+[[package]]
+name = "hermit-abi"
+version = "0.1.12"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "61565ff7aaace3525556587bd2dc31d4a07071957be715e63ce7b1eccf51a8f4"
+dependencies = [
+ "libc",
+]
+
+[[package]]
+name = "image"
+version = "0.23.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9117f4167a8f21fa2bb3f17a652a760acd7572645281c98e3b612a26242c96ee"
+dependencies = [
+ "bytemuck",
+ "byteorder",
+ "gif",
+ "jpeg-decoder",
+ "num-iter",
+ "num-rational",
+ "num-traits",
+ "png",
+ "scoped_threadpool",
+ "tiff",
+]
+
+[[package]]
+name = "inflate"
+version = "0.4.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1cdb29978cc5797bd8dcc8e5bf7de604891df2a8dc576973d71a281e916db2ff"
+dependencies = [
+ "adler32",
+]
+
+[[package]]
+name = "jpeg-decoder"
+version = "0.1.19"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5b47b4c4e017b01abdc5bcc126d2d1002e5a75bbe3ce73f9f4f311a916363704"
+dependencies = [
+ "byteorder",
+ "rayon",
+]
+
+[[package]]
 name = "kd-forest"
 version = "2.0.0"
 dependencies = [
+ "image",
  "ordered-float",
  "rand",
 ]
 
 [[package]]
+name = "lazy_static"
+version = "1.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
+
+[[package]]
 name = "libc"
 version = "0.2.69"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "99e85c08494b21a9054e7fe1374a732aeadaff3980b6990b94bfd3a70f690005"
 
 [[package]]
+name = "lzw"
+version = "0.10.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "7d947cbb889ed21c2a84be6ffbaebf5b4e0f4340638cba0444907e38b56be084"
+
+[[package]]
+name = "maybe-uninit"
+version = "2.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "60302e4db3a61da70c0cb7991976248362f30319e88850c487b9b95bbf059e00"
+
+[[package]]
+name = "memoffset"
+version = "0.5.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "b4fc2c02a7e374099d4ee95a193111f72d2110197fe200272371758f6c3643d8"
+dependencies = [
+ "autocfg",
+]
+
+[[package]]
+name = "miniz_oxide"
+version = "0.3.6"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "aa679ff6578b1cddee93d7e82e263b94a575e0bfced07284eb0c037c1d2416a5"
+dependencies = [
+ "adler32",
+]
+
+[[package]]
+name = "num-integer"
+version = "0.1.42"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3f6ea62e9d81a77cd3ee9a2a5b9b609447857f3d358704331e4ef39eb247fcba"
+dependencies = [
+ "autocfg",
+ "num-traits",
+]
+
+[[package]]
+name = "num-iter"
+version = "0.1.40"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "dfb0800a0291891dd9f4fe7bd9c19384f98f7fbe0cd0f39a2c6b88b9868bbc00"
+dependencies = [
+ "autocfg",
+ "num-integer",
+ "num-traits",
+]
+
+[[package]]
+name = "num-rational"
+version = "0.2.4"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "5c000134b5dbf44adc5cb772486d335293351644b801551abe8f75c84cfa4aef"
+dependencies = [
+ "autocfg",
+ "num-integer",
+ "num-traits",
+]
+
+[[package]]
 name = "num-traits"
 version = "0.2.11"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -47,6 +274,16 @@ dependencies = [
 ]
 
 [[package]]
+name = "num_cpus"
+version = "1.13.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "05499f3756671c15885fee9034446956fff3f243d6077b91e5767df161f766b3"
+dependencies = [
+ "hermit-abi",
+ "libc",
+]
+
+[[package]]
 name = "ordered-float"
 version = "1.0.2"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -56,6 +293,18 @@ dependencies = [
 ]
 
 [[package]]
+name = "png"
+version = "0.16.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "2c68a431ed29933a4eb5709aca9800989758c97759345860fa5db3cfced0b65d"
+dependencies = [
+ "bitflags",
+ "crc32fast",
+ "deflate",
+ "inflate",
+]
+
+[[package]]
 name = "ppv-lite86"
 version = "0.2.6"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -103,6 +352,53 @@ dependencies = [
 ]
 
 [[package]]
+name = "rayon"
+version = "1.3.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "db6ce3297f9c85e16621bb8cca38a06779ffc31bb8184e1be4bed2be4678a098"
+dependencies = [
+ "crossbeam-deque",
+ "either",
+ "rayon-core",
+]
+
+[[package]]
+name = "rayon-core"
+version = "1.7.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "08a89b46efaf957e52b18062fb2f4660f8b8a4dde1807ca002690868ef2c85a9"
+dependencies = [
+ "crossbeam-deque",
+ "crossbeam-queue",
+ "crossbeam-utils",
+ "lazy_static",
+ "num_cpus",
+]
+
+[[package]]
+name = "scoped_threadpool"
+version = "0.1.9"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "1d51f5df5af43ab3f1360b429fa5e0152ac5ce8c0bd6485cae490332e96846a8"
+
+[[package]]
+name = "scopeguard"
+version = "1.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "d29ab0c6d3fc0ee92fe66e2d99f700eab17a8d57d1c1d3b748380fb20baa78cd"
+
+[[package]]
+name = "tiff"
+version = "0.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "002351e428db1eb1d8656d4ca61947c3519ac3191e1c804d4600cd32093b77ad"
+dependencies = [
+ "byteorder",
+ "lzw",
+ "miniz_oxide",
+]
+
+[[package]]
 name = "wasi"
 version = "0.9.0+wasi-snapshot-preview1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index 5a93cf5..902c3a3 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -5,5 +5,6 @@ authors = ["Tavian Barnes <tavianator@tavianator.com>"]
 edition = "2018"
 
 [dependencies]
+image = "0.23.4"
 ordered-float = "1.0.2"
 rand = "0.7.3"
diff --git a/src/color.rs b/src/color.rs
new file mode 100644
index 0000000..a062795
--- /dev/null
+++ b/src/color.rs
@@ -0,0 +1,282 @@
+//! Colors and color spaces.
+
+use crate::metric::kd::{Cartesian, CartesianMetric};
+use crate::metric::{Metric, SquaredDistance};
+
+use image::Rgb;
+
+use std::ops::Index;
+
+/// An 8-bit RGB color.
+pub type Rgb8 = Rgb<u8>;
+
+/// A [color space](https://en.wikipedia.org/wiki/Color_space).
+pub trait ColorSpace: Copy + From<Rgb8> + CartesianMetric {
+    /// Compute the average of the given colors.
+    fn average<I: IntoIterator<Item = Self>>(colors: I) -> Self;
+}
+
+/// [sRGB](https://en.wikipedia.org/wiki/SRGB) space.
+#[derive(Clone, Copy, Debug)]
+pub struct RgbSpace([f64; 3]);
+
+impl Index<usize> for RgbSpace {
+    type Output = f64;
+
+    fn index(&self, i: usize) -> &f64 {
+        &self.0[i]
+    }
+}
+
+impl From<Rgb8> for RgbSpace {
+    fn from(rgb8: Rgb8) -> Self {
+        Self([
+            (rgb8[0] as f64) / 255.0,
+            (rgb8[1] as f64) / 255.0,
+            (rgb8[2] as f64) / 255.0,
+        ])
+    }
+}
+
+impl Metric<[f64]> for RgbSpace {
+    type Distance = SquaredDistance;
+
+    fn distance(&self, other: &[f64]) -> Self::Distance {
+        self.0.distance(other)
+    }
+}
+
+impl Metric for RgbSpace {
+    type Distance = SquaredDistance;
+
+    fn distance(&self, other: &Self) -> Self::Distance {
+        self.0.distance(&other.0)
+    }
+}
+
+impl Cartesian for RgbSpace {
+    fn dimensions(&self) -> usize {
+        self.0.dimensions()
+    }
+
+    fn coordinate(&self, i: usize) -> f64 {
+        self.0.coordinate(i)
+    }
+}
+
+impl ColorSpace for RgbSpace {
+    fn average<I: IntoIterator<Item = Self>>(colors: I) -> Self {
+        let mut sum = [0.0, 0.0, 0.0];
+        let mut len: usize = 0;
+        for color in colors.into_iter() {
+            for i in 0..3 {
+                sum[i] += color[i];
+            }
+            len += 1;
+        }
+        for i in 0..3 {
+            sum[i] /= len as f64;
+        }
+        Self(sum)
+    }
+}
+
+/// [CIE XYZ](https://en.wikipedia.org/wiki/CIE_1931_color_space) space.
+#[derive(Clone, Copy, Debug)]
+struct XyzSpace([f64; 3]);
+
+impl Index<usize> for XyzSpace {
+    type Output = f64;
+
+    fn index(&self, i: usize) -> &f64 {
+        &self.0[i]
+    }
+}
+
+/// The inverse of the sRGB gamma function.
+fn srgb_inv_gamma(t: f64) -> f64 {
+    if t <= 0.040449936 {
+        t / 12.92
+    } else {
+        ((t + 0.055) / 1.055).powf(2.4)
+    }
+}
+
+impl From<Rgb8> for XyzSpace {
+    fn from(rgb8: Rgb8) -> Self {
+        let rgb = RgbSpace::from(rgb8);
+
+        let r = srgb_inv_gamma(rgb[0]);
+        let g = srgb_inv_gamma(rgb[1]);
+        let b = srgb_inv_gamma(rgb[2]);
+
+        Self([
+            0.4123808838268995 * r + 0.3575728355732478 * g + 0.1804522977447919 * b,
+            0.2126198631048975 * r + 0.7151387878413206 * g + 0.0721499433963131 * b,
+            0.0193434956789248 * r + 0.1192121694056356 * g + 0.9505065664127130 * b,
+        ])
+    }
+}
+
+/// CIE D50 [white point](https://en.wikipedia.org/wiki/Standard_illuminant).
+const WHITE: XyzSpace = XyzSpace([0.9504060171449392, 0.9999085943425312, 1.089062231497274]);
+
+/// CIE L\*a\*b\* (and L\*u\*v\*) gamma
+fn lab_gamma(t: f64) -> f64 {
+    if t > 216.0 / 24389.0 {
+        t.cbrt()
+    } else {
+        841.0 * t / 108.0 + 4.0 / 29.0
+    }
+}
+
+/// [CIE L\*a\*b\*](https://en.wikipedia.org/wiki/CIELAB_color_space) space.
+#[derive(Clone, Copy, Debug)]
+pub struct LabSpace([f64; 3]);
+
+impl Index<usize> for LabSpace {
+    type Output = f64;
+
+    fn index(&self, i: usize) -> &f64 {
+        &self.0[i]
+    }
+}
+
+impl From<Rgb8> for LabSpace {
+    fn from(rgb8: Rgb8) -> Self {
+        let xyz = XyzSpace::from(rgb8);
+
+        let x = lab_gamma(xyz[0] / WHITE[0]);
+        let y = lab_gamma(xyz[1] / WHITE[1]);
+        let z = lab_gamma(xyz[2] / WHITE[2]);
+
+        let l = 116.0 * y - 16.0;
+        let a = 500.0 * (x - y);
+        let b = 200.0 * (y - z);
+
+        Self([l, a, b])
+    }
+}
+
+impl Metric<[f64]> for LabSpace {
+    type Distance = SquaredDistance;
+
+    fn distance(&self, other: &[f64]) -> Self::Distance {
+        self.0.distance(other)
+    }
+}
+
+impl Metric for LabSpace {
+    type Distance = SquaredDistance;
+
+    fn distance(&self, other: &Self) -> Self::Distance {
+        self.0.distance(&other.0)
+    }
+}
+
+impl Cartesian for LabSpace {
+    fn dimensions(&self) -> usize {
+        self.0.dimensions()
+    }
+
+    fn coordinate(&self, i: usize) -> f64 {
+        self.0.coordinate(i)
+    }
+}
+
+impl ColorSpace for LabSpace {
+    fn average<I: IntoIterator<Item = Self>>(colors: I) -> Self {
+        let mut sum = [0.0, 0.0, 0.0];
+        let mut len: usize = 0;
+        for color in colors.into_iter() {
+            for i in 0..3 {
+                sum[i] += color[i];
+            }
+            len += 1;
+        }
+        for i in 0..3 {
+            sum[i] /= len as f64;
+        }
+        Self(sum)
+    }
+}
+
+/// [CIE L\*u\*v\*](https://en.wikipedia.org/wiki/CIELUV) space.
+#[derive(Clone, Copy, Debug)]
+pub struct LuvSpace([f64; 3]);
+
+impl Index<usize> for LuvSpace {
+    type Output = f64;
+
+    fn index(&self, i: usize) -> &f64 {
+        &self.0[i]
+    }
+}
+
+/// Computes the u' and v' values for L\*u\*v\*.
+fn uv_prime(xyz: &XyzSpace) -> (f64, f64) {
+    let denom = xyz[0] + 15.0 * xyz[1] + 3.0 * xyz[2];
+    if denom == 0.0 {
+        (0.0, 0.0)
+    } else {
+        (4.0 * xyz[0] / denom, 9.0 * xyz[1] / denom)
+    }
+}
+
+impl From<Rgb8> for LuvSpace {
+    fn from(rgb8: Rgb8) -> Self {
+        let xyz = XyzSpace::from(rgb8);
+
+        let (uprime, vprime) = uv_prime(&xyz);
+        let (unprime, vnprime) = uv_prime(&WHITE);
+
+        let l = 116.0 * lab_gamma(xyz[1] / WHITE[1]) - 16.0;
+        let u = 13.0 * l * (uprime - unprime);
+        let v = 13.0 * l * (vprime - vnprime);
+
+        Self([l, u, v])
+    }
+}
+
+impl Metric<[f64]> for LuvSpace {
+    type Distance = SquaredDistance;
+
+    fn distance(&self, other: &[f64]) -> Self::Distance {
+        self.0.distance(other)
+    }
+}
+
+impl Metric for LuvSpace {
+    type Distance = SquaredDistance;
+
+    fn distance(&self, other: &Self) -> Self::Distance {
+        self.0.distance(&other.0)
+    }
+}
+
+impl Cartesian for LuvSpace {
+    fn dimensions(&self) -> usize {
+        self.0.dimensions()
+    }
+
+    fn coordinate(&self, i: usize) -> f64 {
+        self.0.coordinate(i)
+    }
+}
+
+impl ColorSpace for LuvSpace {
+    fn average<I: IntoIterator<Item = Self>>(colors: I) -> Self {
+        let mut sum = [0.0, 0.0, 0.0];
+        let mut len: usize = 0;
+        for color in colors.into_iter() {
+            for i in 0..3 {
+                sum[i] += color[i];
+            }
+            len += 1;
+        }
+        for i in 0..3 {
+            sum[i] /= len as f64;
+        }
+        Self(sum)
+    }
+}
diff --git a/src/main.rs b/src/main.rs
index 0d7989b..a7bda67 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,3 +1,4 @@
+pub mod color;
 pub mod metric;
 
 fn main() {}