a_sixel/
dither.rs

1//! A collection of various dithering algorithms that can be used with the
2//! [`SixelEncoder`](crate::SixelEncoder) to dither the result.
3//!
4//! Most of the dithering algorithms are based on the ones described in
5//! [this article](https://tannerhelland.com/2012/12/28/dithering-eleven-algorithms-source-code.html).
6//! There is also an implementation of the Bayer matrix dithering algorithm
7//! and a Sobol sequence based dithering algorithm.
8
9use dilate::DilateExpand;
10use image::RgbImage;
11use kiddo::float::kdtree::KdTree;
12use palette::{
13    color_difference::EuclideanDistance,
14    Lab,
15};
16use rayon::{
17    iter::{
18        IndexedParallelIterator,
19        IntoParallelIterator,
20        ParallelIterator,
21    },
22    slice::ParallelSliceMut,
23};
24use sobol_burley::sample;
25
26use crate::{
27    private,
28    rgb_to_lab,
29};
30
31/// Each struct in this module implements this trait and can be combined with
32/// the [`SixelEncoder`](crate::SixelEncoder) struct to dither the result.
33pub trait Dither: private::Sealed {
34    const KERNEL: &[(isize, isize, f32)];
35    const DIV: f32;
36
37    /// Take the input image and convert it to the input palette, applying a
38    /// dithering algorithm to the result.
39    fn dither_and_palettize(image: &RgbImage, in_palette: &[Lab]) -> Vec<usize> {
40        let pixels = image.pixels().copied().map(rgb_to_lab).collect::<Vec<_>>();
41
42        let mut palette = KdTree::<_, _, 3, 257, u32>::with_capacity(in_palette.len());
43
44        for (idx, color) in in_palette.iter().enumerate() {
45            palette.add(color.as_ref(), idx);
46        }
47
48        let mut result = vec![0; image.width() as usize * image.height() as usize];
49
50        let mut spills = vec![[0.0; 3]; image.width() as usize * image.height() as usize];
51
52        for (idx, p) in pixels.iter().copied().enumerate() {
53            let pixel = <Lab>::new(
54                p.l + spills[idx][0],
55                p.a + spills[idx][1],
56                p.b + spills[idx][2],
57            );
58
59            let palette_idx =
60                palette.nearest_one::<kiddo::SquaredEuclidean>(&[pixel.l, pixel.a, pixel.b]);
61
62            let error0 = pixel.l - in_palette[palette_idx.item].l;
63            let error1 = pixel.a - in_palette[palette_idx.item].a;
64            let error2 = pixel.b - in_palette[palette_idx.item].b;
65            let spill = [error0, error1, error2];
66
67            result[idx] = palette_idx.item;
68
69            for (dx, dy, m) in Self::KERNEL {
70                let x = idx as isize % image.width() as isize + dx;
71                let y = idx as isize / image.width() as isize + dy;
72                if x < 0 || y < 0 || x >= image.width() as isize || y >= image.height() as isize {
73                    continue;
74                }
75
76                let jdx = y * image.width() as isize + x;
77                let target = &mut spills[jdx as usize];
78                *target = [
79                    target[0] + (spill[0] * m) / Self::DIV / 2.0,
80                    target[1] + (spill[1] * m) / Self::DIV / 2.0,
81                    target[2] + (spill[2] * m) / Self::DIV / 2.0,
82                ];
83            }
84        }
85
86        result
87    }
88}
89
90/// Do not perform dithering. This is the fastest possible palette encoding
91/// option.
92pub struct NoDither;
93impl private::Sealed for NoDither {}
94impl Dither for NoDither {
95    const DIV: f32 = 1.0;
96    const KERNEL: &[(isize, isize, f32)] = &[];
97
98    fn dither_and_palettize(image: &RgbImage, in_palette: &[Lab]) -> Vec<usize> {
99        let pixels = image.pixels().copied().map(rgb_to_lab).collect::<Vec<_>>();
100
101        let mut palette = KdTree::<_, _, 3, 32, u32>::with_capacity(in_palette.len());
102
103        for (idx, color) in in_palette.iter().enumerate() {
104            palette.add(color.as_ref(), idx);
105        }
106
107        let mut result = vec![0; image.width() as usize * image.height() as usize];
108        pixels
109            .into_par_iter()
110            .zip(&mut result)
111            .for_each(|(p, dest)| {
112                *dest = palette
113                    .nearest_one::<kiddo::SquaredEuclidean>(&[p.l, p.a, p.b])
114                    .item;
115            });
116
117        result
118    }
119}
120
121pub struct Sierra;
122impl private::Sealed for Sierra {}
123impl Dither for Sierra {
124    const DIV: f32 = 32.0;
125    // _ _ X 5 3
126    // 2 4 5 4 2
127    // _ 2 3 2 _
128    const KERNEL: &[(isize, isize, f32)] = &[
129        (1, 0, 5.0),
130        (2, 0, 3.0),
131        //
132        (-2, 1, 2.0),
133        (-1, 1, 4.0),
134        (0, 1, 5.0),
135        (1, 1, 4.0),
136        (2, 1, 2.0),
137        //
138        (-1, 2, 2.0),
139        (0, 2, 3.0),
140        (1, 2, 2.0),
141    ];
142}
143
144pub struct Sierra2;
145impl private::Sealed for Sierra2 {}
146impl Dither for Sierra2 {
147    const DIV: f32 = 16.0;
148    // _ _ X 4 3
149    // 1 2 3 2 1
150    // _ 1 2 1 _
151    const KERNEL: &[(isize, isize, f32)] = &[
152        //x y  m
153        (1, 0, 4.0),
154        (2, 0, 3.0),
155        //
156        (-2, 1, 1.0),
157        (-1, 1, 2.0),
158        (0, 1, 3.0),
159        (1, 1, 2.0),
160        (2, 1, 1.0),
161    ];
162}
163
164pub struct SierraLite;
165impl private::Sealed for SierraLite {}
166impl Dither for SierraLite {
167    const DIV: f32 = 4.0;
168    //  _ X 2
169    //  1 1 _
170    const KERNEL: &[(isize, isize, f32)] = &[
171        //x y  m
172        (1, 0, 2.0),
173        //
174        (-1, 1, 1.0),
175        (0, 1, 1.0),
176    ];
177}
178
179pub struct FloydSteinberg;
180impl private::Sealed for FloydSteinberg {}
181impl Dither for FloydSteinberg {
182    const DIV: f32 = 16.0;
183    // _ X 7
184    // 3 5 3
185    const KERNEL: &[(isize, isize, f32)] = &[
186        //x y  m
187        (1, 0, 7.0),
188        //
189        (-1, 1, 3.0),
190        (0, 1, 5.0),
191        (1, 1, 1.0),
192    ];
193}
194
195pub struct JJN;
196impl private::Sealed for JJN {}
197impl Dither for JJN {
198    const DIV: f32 = 48.0;
199    // _ _ X 7 5
200    // 3 5 7 5 3
201    // 1 2 5 3 1
202    const KERNEL: &[(isize, isize, f32)] = &[
203        //x y  m
204        (1, 0, 7.0),
205        (2, 0, 5.0),
206        //
207        (-2, 1, 3.0),
208        (-1, 1, 5.0),
209        (0, 1, 7.0),
210        (1, 1, 5.0),
211        (2, 1, 3.0),
212        //
213        (-2, 2, 1.0),
214        (-1, 2, 2.0),
215        (0, 2, 5.0),
216        (1, 2, 3.0),
217        (2, 2, 1.0),
218    ];
219}
220
221pub struct Stucki;
222impl private::Sealed for Stucki {}
223impl Dither for Stucki {
224    const DIV: f32 = 42.0;
225    // _ _ X 8 4
226    // 2 4 8 4 2
227    // 1 2 4 2 1
228    const KERNEL: &[(isize, isize, f32)] = &[
229        //x y  m
230        (1, 0, 8.0),
231        (2, 0, 4.0),
232        //
233        (-2, 1, 2.0),
234        (-1, 1, 4.0),
235        (0, 1, 8.0),
236        (1, 1, 4.0),
237        (2, 1, 2.0),
238        //
239        (-2, 2, 1.0),
240        (-1, 2, 2.0),
241        (0, 2, 4.0),
242        (1, 2, 2.0),
243        (2, 2, 1.0),
244    ];
245}
246
247pub struct Atkinson;
248impl private::Sealed for Atkinson {}
249impl Dither for Atkinson {
250    const DIV: f32 = 8.0;
251    // _ X 1 1
252    // 1 1 1 _
253    // _ 1 _ _
254    const KERNEL: &[(isize, isize, f32)] = &[
255        //x y  m
256        (1, 0, 1.0),
257        (2, 0, 1.0),
258        //
259        (-1, 1, 1.0),
260        (0, 1, 1.0),
261        (1, 1, 1.0),
262        //
263        (0, 2, 1.0),
264    ];
265}
266
267pub struct Burkes;
268impl private::Sealed for Burkes {}
269impl Dither for Burkes {
270    const DIV: f32 = 32.0;
271    // _ _ X 8 4
272    // 2 4 8 4 2
273    const KERNEL: &[(isize, isize, f32)] = &[
274        //x y  m
275        (1, 0, 8.0),
276        (2, 0, 4.0),
277        //
278        (-2, 1, 2.0),
279        (-1, 1, 4.0),
280        (0, 1, 8.0),
281        (1, 1, 4.0),
282        (2, 1, 2.0),
283    ];
284}
285
286pub struct Bayer;
287impl private::Sealed for Bayer {}
288impl Dither for Bayer {
289    const DIV: f32 = 0.0;
290    const KERNEL: &[(isize, isize, f32)] = &[];
291
292    fn dither_and_palettize(image: &RgbImage, in_palette: &[Lab]) -> Vec<usize> {
293        let matrix_size = image.width().max(image.height()).ilog2().max(2) as usize;
294        let mut matrix = vec![0.0; matrix_size * matrix_size];
295
296        (0..matrix_size as u32)
297            .into_par_iter()
298            .zip(matrix.par_chunks_mut(matrix_size))
299            .for_each(|(y, row)| {
300                for (x, cell) in row.iter_mut().enumerate() {
301                    let x = x as u32;
302                    let bits = (x ^ y).dilate_expand::<2>().value()
303                        | (y.dilate_expand::<2>().value() << 1);
304                    let bits = bits.reverse_bits() >> bits.leading_zeros();
305                    *cell = bits as f32 / matrix_size.pow(2) as f32;
306                }
307            });
308
309        let mut palette = KdTree::<_, _, 3, 257, u32>::with_capacity(in_palette.len());
310        for (idx, color) in in_palette.iter().enumerate() {
311            palette.add(color.as_ref(), idx);
312        }
313
314        let mut result = vec![0; image.width() as usize * image.height() as usize];
315        let pixels = image.pixels().copied().map(rgb_to_lab).collect::<Vec<_>>();
316
317        pixels
318            .into_par_iter()
319            .enumerate()
320            .zip(&mut result)
321            .for_each(|((idx, p), dest)| {
322                let x = (idx % image.width() as usize) % matrix_size;
323                let y = (idx / image.width() as usize) % matrix_size;
324
325                let [l1, l2] = palette
326                    .nearest_n::<kiddo::SquaredEuclidean>(p.as_ref(), 2)
327                    .try_into()
328                    .unwrap();
329
330                let p_dist = in_palette[l1.item].distance_squared(in_palette[l2.item]);
331                let t = ((l1.distance - l2.distance + p_dist) / (2.0 * p_dist)).clamp(0.0, 1.0);
332
333                let m_idx = x + y * matrix_size;
334                if t > matrix[m_idx] {
335                    *dest = l2.item;
336                } else {
337                    *dest = l1.item;
338                }
339            });
340
341        result
342    }
343}
344
345/// Uses the Sobol sequence to perturb the colors in a quasi-random manner. This
346/// is somewhere between ordered dithering and stochastic dithering. The results
347/// are generally decent, although they may appear textured like paper.
348pub struct Sobol;
349impl private::Sealed for Sobol {}
350impl Dither for Sobol {
351    const DIV: f32 = 0.0;
352    const KERNEL: &[(isize, isize, f32)] = &[];
353
354    fn dither_and_palettize(image: &RgbImage, in_palette: &[Lab]) -> Vec<usize> {
355        let mut palette = KdTree::<_, _, 3, 257, u32>::with_capacity(in_palette.len());
356        for (idx, color) in in_palette.iter().enumerate() {
357            palette.add(color.as_ref(), idx);
358        }
359
360        let mut result = vec![0; image.width() as usize * image.height() as usize];
361        let pixels = image.pixels().copied().map(rgb_to_lab).collect::<Vec<_>>();
362
363        pixels
364            .into_par_iter()
365            .enumerate()
366            .zip(&mut result)
367            .for_each(|((idx, p), dest)| {
368                let thresh = sample(idx as u32 % (1 << 16), 0, idx as u32 / (1 << 16));
369
370                let [l1, l2] = palette
371                    .nearest_n::<kiddo::SquaredEuclidean>(p.as_ref(), 2)
372                    .try_into()
373                    .unwrap();
374
375                let p_dist = in_palette[l1.item].distance_squared(in_palette[l2.item]);
376                let t = ((l1.distance - l2.distance + p_dist) / (2.0 * p_dist)).clamp(0.0, 1.0);
377
378                if t > thresh {
379                    *dest = l2.item;
380                } else {
381                    *dest = l1.item;
382                }
383            });
384
385        result
386    }
387}
a_sixel/dither.rs

a_sixel/
dither.rs
