Changeset 1930Tweet

Timestamp:

11/11/07 13:27:40 (6 years ago)

Author:

sam

Message:

• Introducing dither matrices.

Location:

www/study

Files:

• fig001.png (added)
• fig001.svg (added)
• fig002.png (added)
• fig002.svg (added)
• fig003.png (added)
• fig003.svg (added)
• fig004.png (added)
• fig004.svg (added)
• grad007.png (modified) (previous)
• grad008.png (added)
• grad009.png (added)
• gradient256bw.png (added)
• index.html (modified) (5 diffs)
• out007.png (modified) (previous)
• out008.png (added)
• out009.png (added)
• pat004.png (modified) (previous)
• study.py (modified) (5 diffs)

www/study/index.html

@@ -40 +40 @@
   <img src="lenna256bw.png" width="256" height="256"
        class="inline" alt="Lenna (256x256BW)" />
+  <img src="gradient256bw.png" width="32" height="256"
+       class="inline" alt="gradient" />
 </p>
 
@@ -106 +108 @@
 </p>
 
-<p> Still not very good. Obviously something better is needed. </p>
+<p> Choosing the best thresholding value for a given image is called
+<b>average dithering</b>. But even with the best value, the results will
+not improve tremendously. </p>
 
 <h3> 1.2. Grayscale thresholding </h3>
@@ -172 +176 @@
 </p>
 
-<!--<p> Even if the shades -->
-
-<h3> 2.3. Introducing gamma </h3>
-
-<p> More importantly, if you are reading this document on a computer
+<p> Obviously the middle pattern looks far better to the human eye on a
+computer screen. Optimising patterns so that they look good to the human
+eye and don't create artifacts is a crucial element of a dithering
+algorithm. Here is another example of two patterns that approximate to
+the same shade of gray but may look slightly different from a distance: </p>
+
+<p style="text-align: center;">
+  <img src="pat004.png" width="320" height="80"
+       class="inline" alt="two different 25% patterns" />
+</p>
+
+<h3> 2.3. Ordered dither </h3>
+
+<p> A generalisation of the dithering technique we just saw that uses a
+certain family of patterns is called <b>ordered dither</b>. It is based on
+a <b>dither matrix</b> such as the following one: </p>
+
+<p style="text-align: center;">
+  <img src="fig001.png" width="128" height="128" alt="2x2 dither matrix" />
+</p>
+
+<p> This matrix is then repeated all over the image, and the cells are used
+as threshold values. In this case, pixels (0,0), (0,2), (0,4) etc. will be
+thresholded with a value of 0.2. Pixels (0,1), (0, 3), (0, 4) etc. will be
+thresholded with a value of 0.8, and so on, resulting in the image seen
+in 2.1. </p>
+
+<p> Different matrices can give very different results. This is a 4×4
+Bayer ordered dither matrix: </p>
+
+<p style="text-align: center;">
+  <img src="fig002.png" width="160" height="160"
+       style="margin-right: 30px;" alt="4x4 Bayer matrix" />
+  <img src="out007.png" width="256" height="256"
+       class="inline" alt="4x4 Bayer dithering" />
+  <img src="grad007.png" width="32" height="256"
+       class="inline" alt="4x4 Bayer dithering gradient" />
+</p>
+
+<p> This 4×4 cluster dot matrix creates dot patterns that mimic the
+halftoning techniques used by newspapers: </p>
+
+<p style="text-align: center;">
+  <img src="fig003.png" width="160" height="160"
+       style="margin-right: 30px;" alt="4x4 cluster dot matrix" />
+  <img src="out008.png" width="256" height="256"
+       class="inline" alt="4x4 cluster dot dithering" />
+  <img src="grad008.png" width="32" height="256"
+       class="inline" alt="4x4 cluster dot dithering gradient" />
+</p>
+
+<p> This unusual 5×3 matrix creates artistic vertical line artifacts: </p>
+
+<p style="text-align: center;">
+  <img src="fig004.png" width="200" height="120"
+       style="margin-right: 30px;" alt="4x4 cluster dot matrix" />
+  <img src="out009.png" width="256" height="256"
+       class="inline" alt="4x4 cluster dot dithering" />
+  <img src="grad009.png" width="32" height="256"
+       class="inline" alt="4x4 cluster dot dithering gradient" />
+</p>
+
+<!--
+<h3> 3. Introducing gamma </h3>
+
+<p> If you are reading this document on a computer
 screen, you may have noticed that the above 50% pattern was closer to a 0.73
 grayscale (left) than to the intuitively expected 0.5 value (right). If you
@@ -195 +260 @@
 
 <p style="text-align: center;">
-  <img src="fig001.png" width="256" height="230" alt="introducing gamma" />
+  <img src="fig001.png" width="300" height="240" alt="introducing gamma" />
 </p>
 
@@ -227 +292 @@
   <img src="grad007.png" width="32" height="256"
        class="inline" alt="gamma-aware 3-pattern halftoning gradient" />
-  <img src="out008.png" width="32" height="256"
-       class="inline" alt="gamma-aware 6.25%, 25% and 50% halftoning" />
-</p>
+</p>
+-->
 
 <!--
+<h3> Gamma with more gray levels </h3>
+
+<p> As seen above, the smoothest dithering pattern that can be created with
+black and white is by uniformly alterning the two colours. However, the
+resulting colour (0.73) it is not evenly situated on the gray scale. </p>
+
   <img src="out008.png" width="256" height="256"
        class="inline" alt="gamma-aware 6.25%, 25% and 50% halftoning" />

www/study/study.py

@@ -47 +47 @@
     for y in range(256):
         gradient256bw.setGray(x, 255 - y, y / 255.)
+gradient256bw.writePng("gradient256bw.png")
 
 # Output 1: 50% threshold
@@ -143 +144 @@
         dest.setGray(x, y, c)
 dest.writePng("pat003.png")
+
+# Pattern 4: two different 25% patterns
+dest = Image((320, 80))
+for y in range(80):
+    for x in range(80):
+        c = (x / 2 & 1) and (y / 2 & 1)
+        dest.setGray(x, y, c)
+    for x in range(80, 160):
+        c = (x & 1) and (y & 1)
+        dest.setGray(x, y, c)
+    for x in range(160, 240):
+        c = (x & 1) and ((y + x / 2) & 1)
+        dest.setGray(x, y, c)
+    for x in range(240, 320):
+        c = (x / 2 & 1) and ((y / 2 + x / 4) & 1)
+        dest.setGray(x, y, c)
+dest.writePng("pat004.png")
+
+# Output 7: 4x4 Bayer dithering
+def test4(src, mat, name):
+    (w, h) = src.size()
+    dest = Image((w, h))
+    dx = len(mat[0])
+    dy = len(mat)
+    for y in range(h):
+        for x in range(w):
+            c = src.getGray(x, y)
+            threshold = (1. + mat[y % dy][x % dx]) / (dx * dy + 1)
+            c = c > threshold
+            dest.setGray(x, y, c)
+    dest.writePng(name)
+
+mat = [[  0,  8,  3, 11],
+       [ 15,  4, 12,  7],
+       [  2, 10,  1,  9],
+       [ 13,  6, 14,  5]]
+test4(lenna256bw, mat, "out007.png")
+test4(gradient256bw, mat, "grad007.png")
+
+mat = [[ 12,  5,  6, 13],
+       [  4,  0,  1,  7],
+       [ 11,  3,  2,  8],
+       [ 15, 10,  9, 14]]
+test4(lenna256bw, mat, "out008.png")
+test4(gradient256bw, mat, "grad008.png")
+
+mat = [[ 13,  7,  0,  4, 10],
+       [  9,  3,  1,  8, 14],
+       [ 11,  5,  2,  6, 12],]
+test4(lenna256bw, mat, "out009.png")
+test4(gradient256bw, mat, "grad009.png")
+
+##############################################################################
+# Only temporary cruft below this
+import sys
+sys.exit(0)
+
+
+
 
 # Pattern 4: gamma-corrected 50% gray, black-white halftone, 50% gray
@@ -213 +273 @@
 
 
-##############################################################################
-# Only temporary cruft below this
-
 src = lenna256bw
 src = gradient256bw
@@ -224 +281 @@
        [  2, 10,  1,  9],
        [ 13,  6, 14,  5]]
-mat = [[  6,  7,  8,  9],
-       [  5,  0,  1, 10],
-       [  4,  3,  2, 11],
-       [ 15, 14, 13, 12]]
-mat = [[ 12,  5,  9, 13],
-       [  8,  0,  1,  6],
-       [  4,  3,  2, 10],
-       [ 15, 11,  7, 14]]
-mat = [[ 35, 24, 13, 14, 25, 32],
-       [ 31, 12,  5,  6, 15, 26],
-       [ 23,  4,  0,  1,  7, 16],
-       [ 22, 11,  3,  2,  8, 17],
-       [ 30, 21, 10,  9, 18, 27],
-       [ 34, 29, 20, 19, 28, 33]]
-mat = [[  0, 20, 30,  3, 23, 29],
-       [ 12, 32, 18, 15, 35, 17],
-       [ 27,  8,  4, 24, 11,  7],
-       [  2, 22, 28,  1, 21, 31],
-       [ 14, 34, 16, 13, 33, 19],
-       [ 25, 10,  6, 26,  9,  5]]
+#mat = [[  6,  7,  8,  9],
+#       [  5,  0,  1, 10],
+#       [  4,  3,  2, 11],
+#       [ 15, 14, 13, 12]]
+#mat = [[ 12,  5,  9, 13],
+#       [  8,  0,  1,  6],
+#       [  4,  3,  2, 10],
+#       [ 15, 11,  7, 14]]
+size = 4
+#mat = [[ 35, 24, 13, 14, 25, 32],
+#       [ 31, 12,  5,  6, 15, 26],
+#       [ 23,  4,  0,  1,  7, 16],
+#       [ 22, 11,  3,  2,  8, 17],
+#       [ 30, 21, 10,  9, 18, 27],
+#       [ 34, 29, 20, 19, 28, 33]]
+#mat = [[  0, 20, 30,  3, 23, 29],
+#       [ 12, 32, 18, 15, 35, 17],
+#       [ 27,  8,  4, 24, 11,  7],
+#       [  2, 22, 28,  1, 21, 31],
+#       [ 14, 34, 16, 13, 33, 19],
+#       [ 25, 10,  6, 26,  9,  5]]
+#size = 6
 dest = Image((w, h))
 for y in range(h):
@@ -249 +308 @@
         c = src.getGray(x, y)
         i = Gamma.CtoI(c)
-        threshold = mat[x % 6][y % 6]
-        c = math.floor(i * 35.999) > threshold
+        threshold = mat[x % size][y % size]
+        d = math.floor(i * (size * size + .9999)) > threshold
+        if c > 0.95:
+            print c, i, i * (size * size + .9999)
+        c = d
         dest.setGray(x, y, c)
 dest.writePng("out008.png")
-
-import sys
-sys.exit(0)
 
 # Create a dot-matrix pattern