More about the algorithm

1 files changed, 31 insertions, 12 deletions

diff --git a/docs/yuv-dither.txt b/docs/yuv-dither.txt
index bc8e0690..b47acbb9 100644
--- a/docs/yuv-dither.txt
+++ b/docs/yuv-dither.txt
@@ -1,10 +1,3 @@
-New algorithm:
-
-First generate white triangular sRGB noise. Then, convert to
-s-CIELAB. Then swap pixels until the s-CIELAB error metric is a
-minimal distance from a black image. Ie., direct binary search for the
-blackest image.
-
 Details:
 
 /* In making a dither table of size n x n, we want to:
@@ -39,8 +32,12 @@ Details:
  * The sum_i f_i * G(u - i) is equivalent to filtering the HVS filtered array
  * with the HVS function once again. Convolution is associative, so this is
  * equivalent to filtering with the G convolved with itself. We will denote
- * this new filter by U = G * G. The array resulting from convolving
- * A with U is denoted F.
+ * this new filter by U = G * G. Note that U(0) = rho and that U(a) =
+ * U(-a) if G is symmetric.
+ *
+ * The array resulting from convolving A with U is denoted F:
+ *
+ *                 F = A * U
  *
  * The Delta E expression can now be written:
  *
@@ -51,7 +48,7 @@ Details:
  * add x_a at position b. Then subtract x_b at position b, and finally add
  * x_b at position a. Note that subtracting a value causes changes to
  * the F array that must be accounted for in subsequent Delta
- * computations. Note that U(0) = rho.
+ * computations.
  *
  * D_1E = (x_a ^ 2) * rho - 2 * x_a * F(a)
  *
@@ -76,10 +73,23 @@ Details:
  *       2 * x_b * (F(a) - F(b)) +
  *       2 * x_a * x_b (U(b - a) + U(a - b) - 2 * rho)
  *
+ * Since U is symmetric, we know that U(b - a) = U(a - b). Call this value u.
+ * By setting d = x_a - x_b and f = F(a) - F(b), the above expression
+ * now simplifies to:
+ *
+ *     Delta_E = 2 * (rho - u) * d^2 + 2 * f * d
+ *
+ * FIXME: Add note that in principle we should compute the error as:
+ *
+ *           Sum_i  (f_i - level)^2
+ *
+ * but that level disappears in f = F(a) - F(b).
+ *
  * We can now sketch the algorithm:
  *
  *   (a) compute the filter U which is HVS convolved with itself
- *   (b) compute rho, the sum of the squares of all entries in HVS
+ *   (b) compute rho, the sum of the squares of all entries in HVS (or
+ *       take it from U(0)).
  *   (c) maintain A, the unfiltered array that starts out as random noise
  *   (d) maintain F, which is A filtered by U
  *   (e) maintain E
@@ -91,7 +101,16 @@ Details:
  */
 
 
-Older algorithm:
+
+
+Old algorithm:
+
+First generate white triangular sRGB noise. Then, convert to
+s-CIELAB. Then swap pixels until the s-CIELAB error metric is a
+minimal distance from a black image. Ie., direct binary search for the
+blackest image.
+
+Even older algorithm:
 
 We must choose a box in YUV space. The edges of that box decide how
 much noise to add in each of the three dimensions. If we assume HVS