Generalization of void/cluster

1 files changed, 16 insertions, 0 deletions

diff --git a/docs/yuv-dither.txt b/docs/yuv-dither.txt
index 3b1e7cfc..34be7382 100644
--- a/docs/yuv-dither.txt
+++ b/docs/yuv-dither.txt
@@ -32,6 +32,22 @@ sidesteps the issue of gray-levels.
 The noise quality of doing this may not be good enough though, so it
 could still be useful to do the whole graylevel optimization.
 
+Generalization of void-and-cluster: 
+
+    - Generate white noise
+    - Maintain array with noise, and array with perceptually filtered
+      noise
+    - find pair (a, b) such that (noise[a] > noise[b]) and
+      (filtered[a] - filtered[b]) is maximal.
+    - swap them
+
+repeat until it converges. Note that we can maintain a sorted version
+of the filtered array, and then starting from each end of that,
+compare the corresponding noise entries, and if those don't satisfy
+the noise[a] > noise[b] condition, move the pointer that would change
+the filtered difference the least. Repeat until the pointers meat.
+
+(Why do we not want to use a perceptual filter for binary void/cluster?)
 
 Finally, convert to RGB. (Maybe do subpixel sampling?)