Changeset 2215
- Timestamp:
- Jan 25, 2008, 1:18:37 AM (15 years ago)
- Location:
- www/study
- Files:
-
- 21 added
- 9 deleted
- 21 edited
- 10 copied
- 29 moved
Legend:
- Unmodified
- Added
- Removed
-
www/study/fig5-1-1.svg
r2214 r2215 17 17 version="1.0" 18 18 sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study" 19 sodipodi:docname="fig 4-1-1.svg"19 sodipodi:docname="fig5-1-1.svg" 20 20 inkscape:output_extension="org.inkscape.output.svg.inkscape" 21 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig 4-1-1.png"21 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig5-1-1.png" 22 22 inkscape:export-xdpi="90" 23 23 inkscape:export-ydpi="90"> -
www/study/fig5-1-2.svg
r2214 r2215 17 17 version="1.0" 18 18 sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study" 19 sodipodi:docname="fig 4-1-2.svg"19 sodipodi:docname="fig5-1-2.svg" 20 20 inkscape:output_extension="org.inkscape.output.svg.inkscape" 21 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig 4-1-2.png"21 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig5-1-2.png" 22 22 inkscape:export-xdpi="90" 23 23 inkscape:export-ydpi="90"> -
www/study/fig5-1-3.svg
r2214 r2215 17 17 version="1.0" 18 18 sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study" 19 sodipodi:docname="fig 4-1-3.svg"19 sodipodi:docname="fig5-1-3.svg" 20 20 inkscape:output_extension="org.inkscape.output.svg.inkscape" 21 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig 4-1-3.png"21 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig5-1-3.png" 22 22 inkscape:export-xdpi="90" 23 23 inkscape:export-ydpi="90"> -
www/study/fig5-3-1.svg
r2214 r2215 15 15 inkscape:version="0.45.1" 16 16 sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study" 17 sodipodi:docname="fig 4-3-1.svg"17 sodipodi:docname="fig5-3-1.svg" 18 18 inkscape:output_extension="org.inkscape.output.svg.inkscape" 19 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig 4-3-1.png"19 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig5-3-1.png" 20 20 inkscape:export-xdpi="30" 21 21 inkscape:export-ydpi="30"> -
www/study/fig6-1-7.svg
r2214 r2215 17 17 version="1.0" 18 18 sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study" 19 sodipodi:docname="fig 5-1-7.svg"19 sodipodi:docname="fig6-1-7.svg" 20 20 inkscape:output_extension="org.inkscape.output.svg.inkscape" 21 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig 5-1-7.png"21 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig6-1-7.png" 22 22 inkscape:export-xdpi="90" 23 23 inkscape:export-ydpi="90"> … … 56 56 inkscape:current-layer="svg83" /> 57 57 <image 58 xlink:href="out/fig 5-1-1.png"59 sodipodi:absref="out/fig 5-1-1.png"58 xlink:href="out/fig6-1-1.png" 59 sodipodi:absref="out/fig6-1-1.png" 60 60 width="128" 61 61 height="128" … … 64 64 y="-432" /> 65 65 <image 66 xlink:href="out/fig 5-1-2c.png"67 sodipodi:absref="out/fig 5-1-2c.png"66 xlink:href="out/fig6-1-2c.png" 67 sodipodi:absref="out/fig6-1-2c.png" 68 68 width="128" 69 69 height="128" … … 72 72 y="-432" /> 73 73 <image 74 xlink:href="out/fig 5-1-3a.png"75 sodipodi:absref="out/fig 5-1-3a.png"74 xlink:href="out/fig6-1-3a.png" 75 sodipodi:absref="out/fig6-1-3a.png" 76 76 width="128" 77 77 height="128" … … 80 80 y="-288" /> 81 81 <image 82 xlink:href="out/fig 5-1-3b.png"83 sodipodi:absref="out/fig 5-1-3b.png"82 xlink:href="out/fig6-1-3b.png" 83 sodipodi:absref="out/fig6-1-3b.png" 84 84 width="128" 85 85 height="128" … … 88 88 y="-288" /> 89 89 <image 90 xlink:href="out/fig 5-1-3c.png"91 sodipodi:absref="out/fig 5-1-3c.png"90 xlink:href="out/fig6-1-3c.png" 91 sodipodi:absref="out/fig6-1-3c.png" 92 92 width="128" 93 93 height="128" … … 96 96 y="-288" /> 97 97 <image 98 xlink:href="out/fig 5-1-4a.png"99 sodipodi:absref="out/fig 5-1-4a.png"98 xlink:href="out/fig6-1-4a.png" 99 sodipodi:absref="out/fig6-1-4a.png" 100 100 width="128" 101 101 height="128" … … 104 104 y="-144" /> 105 105 <image 106 xlink:href="out/fig 5-1-4b.png"107 sodipodi:absref="out/fig 5-1-4b.png"106 xlink:href="out/fig6-1-4b.png" 107 sodipodi:absref="out/fig6-1-4b.png" 108 108 width="128" 109 109 height="128" … … 112 112 y="-144" /> 113 113 <image 114 xlink:href="out/fig 5-1-4c.png"115 sodipodi:absref="out/fig 5-1-4c.png"114 xlink:href="out/fig6-1-4c.png" 115 sodipodi:absref="out/fig6-1-4c.png" 116 116 width="128" 117 117 height="128" … … 120 120 y="-144" /> 121 121 <image 122 xlink:href="out/fig 5-1-5a.png"123 sodipodi:absref="out/fig 5-1-5a.png"122 xlink:href="out/fig6-1-5a.png" 123 sodipodi:absref="out/fig6-1-5a.png" 124 124 width="128" 125 125 height="128" … … 135 135 inkscape:export-ydpi="90" /> 136 136 <image 137 xlink:href="out/fig 5-1-2b.png"138 sodipodi:absref="out/fig 5-1-2b.png"137 xlink:href="out/fig6-1-2b.png" 138 sodipodi:absref="out/fig6-1-2b.png" 139 139 width="128" 140 140 height="128" … … 151 151 inkscape:export-ydpi="90" /> 152 152 <image 153 xlink:href="out/fig 5-1-2a.png"154 sodipodi:absref="out/fig 5-1-2a.png"153 xlink:href="out/fig6-1-2a.png" 154 sodipodi:absref="out/fig6-1-2a.png" 155 155 width="128" 156 156 height="128" … … 167 167 inkscape:export-ydpi="90" /> 168 168 <image 169 xlink:href="out/fig 5-1-6.png"170 sodipodi:absref="out/fig 5-1-6.png"169 xlink:href="out/fig6-1-6.png" 170 sodipodi:absref="out/fig6-1-6.png" 171 171 width="128" 172 172 height="128" … … 247 247 style="stroke-width:3;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none" /> 248 248 <image 249 xlink:href="out/fig 5-1-5b.png"250 sodipodi:absref="out/fig 5-1-5b.png"249 xlink:href="out/fig6-1-5b.png" 250 sodipodi:absref="out/fig6-1-5b.png" 251 251 width="128" 252 252 height="128" … … 264 264 style="stroke-linejoin:miter;stroke-width:3;stroke-miterlimit:4;stroke-dasharray:none" /> 265 265 <image 266 xlink:href="out/fig 5-1-5c.png"267 sodipodi:absref="out/fig 5-1-5c.png"266 xlink:href="out/fig6-1-5c.png" 267 sodipodi:absref="out/fig6-1-5c.png" 268 268 width="128" 269 269 height="128" -
www/study/fig7-3-1.svg
r2214 r2215 16 16 inkscape:version="0.45.1" 17 17 sodipodi:docbase="/home/sam/debian/pkg-misc/unstable/libcaca/www/study" 18 sodipodi:docname="fig 6-3-1.svg"18 sodipodi:docname="fig7-3-1.svg" 19 19 inkscape:output_extension="org.inkscape.output.svg.inkscape" 20 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig 6-3-1.png"20 inkscape:export-filename="/home/sam/debian/pkg-misc/unstable/libcaca/www/study/fig7-3-1.png" 21 21 inkscape:export-xdpi="90" 22 22 inkscape:export-ydpi="90"> -
www/study/index.html
r2211 r2215 100 100 </ul> 101 101 </li> 102 <li> <a href="part4.html">4. Greyscaledithering</a>102 <li> <a href="part4.html">4. Model-based dithering</a> 103 103 <ul> 104 <li> 4.1. Introducing gamma </li> 105 <li> 4.2. Gamma correction </li> 106 <li> 4.3. Greyscale sub-block error diffusion </li> 104 <li> 4.1. TODO </li> 107 105 </ul> 108 106 </li> 109 <li> <a href="part5.html">5. Colourdithering</a>107 <li> <a href="part5.html">5. Greyscale dithering</a> 110 108 <ul> 111 <li> 5.1. Separate-space dithering </li> 112 <li> 5.2. Accounting for other dimensions </li> 113 <li> 5.3. Reducing visual artifacts </li> 114 <li> 5.4. Colour sub-block error diffusion </li> 109 <li> 5.1. Introducing gamma </li> 110 <li> 5.2. Gamma correction </li> 111 <li> 5.3. Greyscale sub-block error diffusion </li> 115 112 </ul> 116 113 </li> 117 <li> <a href="part6.html">6. Photographic mosaics</a>114 <li> <a href="part6.html">6. Colour dithering</a> 118 115 <ul> 119 <li> 6.1. Image classification </li> 120 <li> 6.2. Error diffusion </li> 121 <li> 6.3. Colour ASCII art </li> 116 <li> 6.1. Separate-space dithering </li> 117 <li> 6.2. Accounting for other dimensions </li> 118 <li> 6.3. Reducing visual artifacts </li> 119 <li> 6.4. Colour sub-block error diffusion </li> 120 </ul> 121 </li> 122 <li> <a href="part7.html">7. Photographic mosaics</a> 123 <ul> 124 <li> 7.1. Image classification </li> 125 <li> 7.2. Error diffusion </li> 126 <li> 7.3. Colour ASCII art </li> 122 127 </ul> 123 128 </li> -
www/study/part3.html
r2211 r2215 29 29 </div> 30 30 <div style="float: right;"> 31 <a href="part4.html">>>> Greyscaledithering</a>31 <a href="part4.html">>>> Model-based dithering</a> 32 32 </div> 33 33 <div style="text-align: center;"> … … 616 616 </p> 617 617 618 <h3> 3.7. Direct binary search </h3>619 620 <p> We have already seen that standard error diffusion methods do not go back621 to pixels that have been set. <b>Direct binary search</b> [4] (DBS) is an622 iterative method that processes the image a fixed number of times, or until the623 error can no longer be minimised: </p>624 625 <ul>626 <li> Generate an initial dithered image </li>627 <li> Repeat until no changes can be applied:628 <ul>629 <li> Compute the global error between the original and the dithered630 images </li>631 <li> For each pixel in the dithered image:632 <ul>633 <li> Compute the effect on the error of toggling the value of the634 current pixel </li>635 <li> Compute the effect on the error of swapping the current pixel636 with one of its immediate neighbours </li>637 <li> If the error can be reduced, perform the corresponding638 action </li>639 </ul>640 </li>641 </ul>642 </li>643 </ul>644 645 <p> DBS relies on a <b>human visual system</b> model: instead of considering a646 local, pixel-bound error value, it tries to figure what the human eye really647 sees, by applying a filter to both the source and destination images, and then648 computes the error between these filtered signals. </p>649 650 <p> The efficiency and quality of DBS depend on many implementation details,651 starting with the HVS model. Also, the initial image used as iteration zero652 will give poor results if pattern artifacts are already present. And the order653 in which pixels are processed is important, too. Unfortunately, despite its654 very high-quality results, DBS is usually a very slow algorithm. </p>655 656 <p> Below is an example of the algorithm results. We use a 7×7 convolution657 kernel to approximate the human visual system, using a simplified luminance658 spatial frequency response formula:659 <i>e<small><sup> -sqrt(x²+y²)</sup></small></i>. The initial image is660 randomly thresholded, and pixels are processed in raster order. Iterations 1,661 2 and 5 are shown: </p>662 663 <p style="text-align: center;">664 <img src="out/lena3-7-1.png" width="256" height="256"665 class="inline" alt="direct binary search, iteration 0" />666 <img src="out/grad3-7-1.png" width="32" height="256"667 class="inline" alt="direct binary search, iteration 0 gradient" />668 <img src="out/lena3-7-2.png" width="256" height="256"669 class="inline" alt="direct binary search, iteration 1" />670 <img src="out/grad3-7-2.png" width="32" height="256"671 class="inline" alt="direct binary search, iteration 1 gradient" />672 </p>673 674 <p style="text-align: center;">675 <img src="out/lena3-7-3.png" width="256" height="256"676 class="inline" alt="direct binary search, iteration 2" />677 <img src="out/grad3-7-3.png" width="32" height="256"678 class="inline" alt="direct binary search, iteration 2 gradient" />679 <img src="out/lena3-7-4.png" width="256" height="256"680 class="inline" alt="direct binary search, iteration 5" />681 <img src="out/grad3-7-4.png" width="32" height="256"682 class="inline" alt="direct binary search, iteration 5 gradient" />683 </p>684 685 618 <div style="float: left;"> 686 619 <a href="part2.html">Halftoning <<<</a> 687 620 </div> 688 621 <div style="float: right;"> 689 <a href="part4.html">>>> Greyscaledithering</a>622 <a href="part4.html">>>> Model-based dithering</a> 690 623 </div> 691 624 <div style="text-align: center;"> -
www/study/part4.html
r2204 r2215 9 9 <meta name="GENERATOR" content="vim" /> 10 10 <meta name="Author" content="sam@zoy.org (Sam Hocevar)" /> 11 <meta name="Description" content="Libcaca study - 4. Greyscaledithering" />11 <meta name="Description" content="Libcaca study - 4. Model-based dithering" /> 12 12 <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" /> 13 <title>Libcaca study - 4. Greyscaledithering</title>13 <title>Libcaca study - 4. Model-based dithering</title> 14 14 <link rel="icon" type="image/x-icon" href="/favicon.ico" /> 15 15 <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" /> … … 29 29 </div> 30 30 <div style="float: right;"> 31 <a href="part5.html">>>> Colourdithering</a>31 <a href="part5.html">>>> Greyscale dithering</a> 32 32 </div> 33 33 <div style="text-align: center;"> … … 35 35 </div> 36 36 37 <h2> 4. Greyscaledithering </h2>37 <h2> 4. Model-based dithering </h2> 38 38 39 <p> At first sight, generalising dithering to three grey scales seems pretty 40 straightforward: just add grey 0.5 in the middle of the palette and dither 41 pixels in the [0, 0.5] range with black and grey, and pixels in the [0.5, 1] 42 range with grey and white. Here are two different results with 8×8 Bayer 43 ordered dithering and with serpentine Floyd-Steinberg error diffusion: </p> 39 <p> TODO </p> 44 40 45 <p style="text-align: center;"> 46 <img src="out/lena4-0-1.png" width="256" height="256" 47 class="inline" alt="8×8 Bayer ordered dithering, 3 colours" /> 48 <img src="out/grad4-0-1.png" width="32" height="256" 49 class="inline" alt="8×8 Bayer ordered dithering gradient, 3 colours" /> 50 <img src="out/lena4-0-2.png" width="256" height="256" 51 class="inline" alt="serpentine FS error diffusion, 3 colours" /> 52 <img src="out/grad4-0-2.png" width="32" height="256" 53 class="inline" alt="serpentine FS error diffusion gradient, 3 colours" /> 54 </p> 41 <h3> 4.2. Direct binary search </h3> 55 42 56 <p> These are pretty much the images that imaging software such as The Gimp 57 would give (using “positioned” and “Floyd-Steinberg” dithering modes). </p> 58 59 <p> Unfortunately the result is not as good as expected: the white pattern 60 on Lena’s cheeks is visually disturbing, and there is a lot of 0.5 grey in 61 the image. Also, the whole image looks darker than with pure black-and-white 62 dithering, but these previous dithering results looked a lot brighter than 63 the original image anyway. </p> 64 65 <p> All these issues have to do with the output media’s <b>gamma</b>. </p> 66 67 <h3> 4.1. Introducing gamma </h3> 68 69 <p> If you are reading this document on a computer screen, you may have 70 noticed that the black and white 50% pattern was closer to a 0.73 greyscale 71 (left) than to the intuitively expected 0.5 value (right). If you are reading 72 a printed copy, it might be a different matter. </p> 73 74 <p style="text-align: center;"> 75 <img src="out/pat4-1-1.png" width="240" height="80" 76 class="inline" alt="introducing gamma" /> 77 </p> 78 79 <p> The mapping linking greyscale steps to intensities is called <b>gamma 80 correction</b>. An approximate law for gamma correction is given as 81 <i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour 82 value (between 0 and 1), <i>I</i> is the perceived colour intensity (between 83 0% and 100%) and <i>γ</i> is the gamma. A pattern made of even-numbered 84 0%-intensity pixels and 100%-intensity pixels has an intensity of 50% by 85 definition. But the corresponding greyscale depends on the gamma value. </p> 86 87 <p> Most modern computer systems use the sRGB gamma model close to the law 88 with <i>γ = 2.2</i>. As can be seen, it is highly non-linear: </p> 89 90 <p style="text-align: center;"> 91 <img src="fig4-1-1.png" width="460" height="256" alt="introducing gamma" /> 92 </p> 93 94 <p> Éric Brasseur wrote <a 95 href="http://www.4p8.com/eric.brasseur/gamma.html">a pretty comprehensive 96 essay</a> [16] about why on a computer screen a 50% black and white pattern 97 should be scaled down to a grey value of 0.73 instead of 0.5 and how major 98 computer graphics software totally misses the point. Conversely, it clearly 99 means that a grey value of 0.5 should not be emulated with a 50% dither 100 pattern. </p> 101 102 <p> The following figure shows the gamma curve for the naïve three-colour 103 greyscale gradient we saw above (red curve) compared to the two-colour 104 gradient (blue curve). Two major observations can be made: the new curve is 105 far closer to a perfect, linear gradient, but there is a singularity in the 106 middle of the curve, meaning a break in the gradient’s smoothness. </p> 107 108 <p style="text-align: center;"> 109 <img src="fig4-1-2.png" width="460" height="256" alt="3-colour gamma" /> 110 </p> 111 112 <p> There are three possible ways to reduce the singularity and make the 113 gradient smoother and/or closer to the original colours: </p> 43 <p> We have already seen that standard error diffusion methods do not go back 44 to pixels that have been set. <b>Direct binary search</b> [4] (DBS) is an 45 iterative method that processes the image a fixed number of times, or until the 46 error can no longer be minimised: </p> 114 47 115 48 <ul> 116 <li> Choose a different middle grey value, for instance choosing grey 0.73 117 will cancel the singularity and match the two-colour gradients we have 118 been using so far. This is not always possible if the output palette 119 is fixed. </li> 120 <li> Don’t place the grey value at the middle of the gradient, for instance 121 a value of around 25% intensity will again match the previous two-colour 122 gradients. </li> 123 <li> <b>Gamma-correct</b> input pixels before assigning them an output 124 value. This ensures that the resulting gradient is perfectly linear 125 and has no singularity. 126 </li> 49 <li> Generate an initial dithered image </li> 50 <li> Repeat until no changes can be applied: 51 <ul> 52 <li> Compute the global error between the original and the dithered 53 images </li> 54 <li> For each pixel in the dithered image: 55 <ul> 56 <li> Compute the effect on the error of toggling the value of the 57 current pixel </li> 58 <li> Compute the effect on the error of swapping the current pixel 59 with one of its immediate neighbours </li> 60 <li> If the error can be reduced, perform the corresponding 61 action </li> 62 </ul> 63 </li> 64 </ul> 65 </li> 127 66 </ul> 128 67 129 <h3> 4.2. Gamma correction </h3> 68 <p> DBS relies on a <b>human visual system</b> model: instead of considering a 69 local, pixel-bound error value, it tries to figure what the human eye really 70 sees, by applying a filter to both the source and destination images, and then 71 computes the error between these filtered signals. </p> 130 72 131 <p> Gamma correction consists in converting pixel values into intensity values 132 before performing operations on them, then reconverting them to pixel values 133 before displaying them. The exact same algorithms can be used, they just 134 operate on slightly different data. </p> 73 <p> The efficiency and quality of DBS depend on many implementation details, 74 starting with the HVS model. Also, the initial image used as iteration zero 75 will give poor results if pattern artifacts are already present. And the order 76 in which pixels are processed is important, too. Unfortunately, despite its 77 very high-quality results, DBS is usually a very slow algorithm. </p> 135 78 136 <p style="text-align: center;"> 137 <img src="fig4-1-3.png" width="460" height="256" alt="3-colour gamma coorection" /> 138 </p> 139 140 <p> Here are the results of gamma-correcting input pixels before doing 141 any computation on them, then using serpentine Floyd-Steinberg error 142 diffusion: </p> 79 <p> Below is an example of the algorithm results. We use a 7×7 convolution 80 kernel to approximate the human visual system, using a simplified luminance 81 spatial frequency response formula: 82 <i>e<small><sup> -sqrt(x²+y²)</sup></small></i>. The initial image is 83 randomly thresholded, and pixels are processed in raster order. Iterations 1, 84 2 and 5 are shown: </p> 143 85 144 86 <p style="text-align: center;"> 145 87 <img src="out/lena4-2-1.png" width="256" height="256" 146 class="inline" alt=" serpentine FS, 2 colours, gamma-corrected" />88 class="inline" alt="direct binary search, iteration 0" /> 147 89 <img src="out/grad4-2-1.png" width="32" height="256" 148 class="inline" alt=" serpentine FS, 2 colours, gamma-correctedgradient" />90 class="inline" alt="direct binary search, iteration 0 gradient" /> 149 91 <img src="out/lena4-2-2.png" width="256" height="256" 150 class="inline" alt=" serpentine FS, 3 colours, gamma-corrected" />92 class="inline" alt="direct binary search, iteration 1" /> 151 93 <img src="out/grad4-2-2.png" width="32" height="256" 152 class="inline" alt=" serpentine FS, 3 colours, gamma-correctedgradient" />94 class="inline" alt="direct binary search, iteration 1 gradient" /> 153 95 </p> 154 155 <p> Two-colour dithering is not visually satisfying: dark areas lack much156 detail because the gamma curve is very flat at low intensities. However,157 the result itself is far more accurate that previously. The problem, while158 still visible, is even less important with three-colour dithering: the image159 on the right is superior to what The Gimp or Adobe Photoshop are able to160 come up with. </p>161 162 <p> Finally, this is gamma-corrected 4-colour dithering: </p>163 96 164 97 <p style="text-align: center;"> 165 98 <img src="out/lena4-2-3.png" width="256" height="256" 166 class="inline" alt=" serpentine FS, 4 colours, gamma-corrected" />99 class="inline" alt="direct binary search, iteration 2" /> 167 100 <img src="out/grad4-2-3.png" width="32" height="256" 168 class="inline" alt="serpentine FS, 4 colours, gamma-corrected gradient" /> 169 </p> 170 171 <h3> 4.3. Greyscale sub-block error diffusion </h3> 172 173 <p> Support for greyscale and gamma correction is trivially added to our 174 sub-block error diffusion method. Best-tile choosing is done in contrast 175 space, while error diffusion is done in intensity space. </p> 176 177 <p> The following picture uses all possible 4-greyscale 2×2 tiles. The 178 output quality is very close to what standard, pixel-per-pixel error diffusion 179 achieves: </p> 180 181 <p style="text-align: center;"> 182 <img src="out/lena4-3-1.png" width="256" height="256" 183 class="inline" alt="sub-block FS, full 4-grey tiles" /> 184 <img src="out/grad4-3-1.png" width="32" height="256" 185 class="inline" alt="sub-block FS, full 4-grey tiles gradient" /> 186 </p> 187 188 <p> And finally, this picture only uses 4-greyscale combinations of the 189 “lines” tiles seen previously: </p> 190 191 <p style="text-align: center;"> 192 <img src="fig4-3-1.png" width="307" height="253" 193 class="matrix" alt="list of 4-grey 2×2 pixel blocks" /> 194 <img src="out/lena4-3-2.png" width="256" height="256" 195 class="inline" alt="sub-block FS, lines 4-grey tiles" /> 196 <img src="out/grad4-3-2.png" width="32" height="256" 197 class="inline" alt="sub-block FS, lines 4-grey tiles gradient" /> 101 class="inline" alt="direct binary search, iteration 2 gradient" /> 102 <img src="out/lena4-2-4.png" width="256" height="256" 103 class="inline" alt="direct binary search, iteration 5" /> 104 <img src="out/grad4-2-4.png" width="32" height="256" 105 class="inline" alt="direct binary search, iteration 5 gradient" /> 198 106 </p> 199 107 … … 202 110 </div> 203 111 <div style="float: right;"> 204 <a href="part5.html">>>> Colourdithering</a>112 <a href="part5.html">>>> Greyscale dithering</a> 205 113 </div> 206 114 <div style="text-align: center;"> -
www/study/part5.html
r2204 r2215 9 9 <meta name="GENERATOR" content="vim" /> 10 10 <meta name="Author" content="sam@zoy.org (Sam Hocevar)" /> 11 <meta name="Description" content="Libcaca study - 5. Colourdithering" />11 <meta name="Description" content="Libcaca study - 5. Greyscale dithering" /> 12 12 <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" /> 13 <title>Libcaca study - 5. Colourdithering</title>13 <title>Libcaca study - 5. Greyscale dithering</title> 14 14 <link rel="icon" type="image/x-icon" href="/favicon.ico" /> 15 15 <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" /> … … 26 26 27 27 <div style="float: left;"> 28 <a href="part4.html"> Greyscaledithering <<<</a>28 <a href="part4.html">Model-based dithering <<<</a> 29 29 </div> 30 30 <div style="float: right;"> 31 <a href="part6.html">>>> Photographic mosaics</a>31 <a href="part6.html">>>> Colour dithering</a> 32 32 </div> 33 33 <div style="text-align: center;"> … … 35 35 </div> 36 36 37 <h2> 5. Colour dithering </h2> 38 39 <p> Dithering colour images means dithering three-dimensional elements (RGB 40 pixels) instead of one-dimensional grey values. It is very complex and 41 depends on the output media even more than greyscale dithering. </p> 42 43 <h3> 5.1. Separate-space dithering </h3> 44 45 <p> In some cases it is possible to perform three one-dimensional dithering 46 operations instead of one three-dimensional one. Consider for instance the 47 following palette: 48 </p> 49 50 <p style="text-align: center;"> 51 <img src="out/pat5-1-1.png" width="512" height="64" 52 class="inline" alt="8-colour RGB palette" /> 53 </p> 54 55 <p> It is made of the eight possible red/green/blue combinations made of 0 56 and 1 values: </p> 57 58 <div style="text-align: center;"> 59 <table style="margin: auto;"> 60 <tr> 61 <td><b>Red</b></td> 62 <td>0</td> <td>0</td> <td>1</td> <td>1</td> 63 <td>0</td> <td>0</td> <td>1</td> <td>1</td> 64 </tr> <tr> 65 <td><b>Green</b></td> 66 <td>0</td> <td>0</td> <td>0</td> <td>0</td> 67 <td>1</td> <td>1</td> <td>1</td> <td>1</td> 68 </tr> <tr> 69 <td><b>Blue</b></td> 70 <td>0</td> <td>1</td> <td>0</td> <td>1</td> 71 <td>0</td> <td>1</td> <td>0</td> <td>1</td> 72 </tr> 73 </table> 74 </div> 75 76 <p> One way of dithering an image using this palette is to convert the image 77 into three greyscale images (separating the red, green and blue channels), 78 dither each subimage to two colours separately and recombine the images into 79 three channels. For instance, if at a given pixel the red channel is dithered 80 to 1 and the green and blue channels are dithered to 0, the final pixel will 81 be [1 0 0] which is the colour red. </p> 82 83 <p> Separate-space dithering works by splitting the image into three red, 84 green and blue channels. Each of this channel is treated as a greyscale image 85 that is then dithered to black and white using any dithering method seen 86 previously. The resulting images are then treated again as three red, green 87 and blue channels and recombined into the final image: </p> 88 89 <p style="text-align: center;"> 90 <img src="fig5-1-7.png" width="704" height="560" 91 class="matrix" alt="separate-space dithering" /> 92 </p> 93 94 <p> Here are the results with serpentine Floyd-Steinberg dithering applied to 95 each channel. On the left, no colour correction, as The Gimp or Photoshop would 96 do; on the right, gamma-corrected dithering: </p> 97 98 <p style="text-align: center;"> 99 <img src="out/lena5-1-1.png" width="256" height="256" 100 class="inline" alt="serpentine FS, 8 colours" /> 101 <img src="out/grad5-1-1.png" width="64" height="256" 102 class="inline" alt="serpentine FS, 8 colours gradient" /> 103 <img src="out/lena5-1-2.png" width="256" height="256" 104 class="inline" alt="serpentine FS, 8 colours, gamma-corrected" /> 105 <img src="out/grad5-1-2.png" width="64" height="256" 106 class="inline" alt="serpentine FS, 8 colours, gamma-corrected gradient" /> 107 </p> 108 109 <h3> 5.2. Accounting for other dimensions </h3> 110 111 <p> The previous palette was suitable for separate-space dithering. Such a 112 palette is called <b>separable</b> or <b>orthogonal</b>. </p> 113 114 <p> Here is a palette that cannot be used in the same way: </p> 115 116 <p style="text-align: center;"> 117 <img src="out/pat5-2-2.png" width="512" height="128" 118 class="inline" alt="8-colour RGB palette" /> 119 </p> 120 121 <p> As can be seen, it does not have the [0.5 0.5 0.5] grey colour, or the 122 [1 0.5 0] orange colour, for instance, despite having other combinations of 123 0, 0.5 and 1 values: </p> 124 125 <div style="text-align: center;"> 126 <table style="margin: auto; border: 1px;"> 127 <tr> 128 <td><b>Red</b></td> 129 <td>0</td> <td>0</td> <td>0.5</td> <td>0.5</td> 130 <td>0</td> <td>0</td> <td>0.5</td> <td>0.7</td> 131 <td>0.3</td> <td>0</td> <td>1</td> <td>1</td> 132 <td>0</td> <td>0</td> <td>1</td> <td>1</td> 133 </tr> <tr> 134 <td><b>Green</b></td> 135 <td>0</td> <td>0</td> <td>0</td> <td>0</td> 136 <td>0.5</td> <td>0.5</td> <td>0.5</td> <td>0.7</td> 137 <td>0.3</td> <td>0</td> <td>0</td> <td>0</td> 138 <td>1</td> <td>1</td> <td>1</td> <td>1</td> 139 </tr> <tr> 140 <td><b>Blue</b></td> 141 <td>0</td> <td>0.5</td> <td>0</td> <td>0.5</td> 142 <td>0</td> <td>0.5</td> <td>0</td> <td>0.7</td> 143 <td>0.3</td> <td>1</td> <td>0</td> <td>1</td> 144 <td>0</td> <td>1</td> <td>0</td> <td>1</td> 145 </tr> 146 </table> 147 </div> 148 149 <p> It is no longer possible to compute the closest colour in each colourspace 150 and combine them into an RGB colour, since that colour might not be available 151 in the palette. So we need to determine what the “closest colour” means when 152 dealing with the whole colour spectrum. </p> 153 154 <p> The following examples show gamma-corrected Floyd-Steinberg using the 155 above 16-colour palette and two different definitions of distance: the <b>sum 156 of absolute differences</b> and the <b>euclidian distance</b>. The sum of 157 absolute differences performs pretty poorly because it does not penalise wide 158 disparities: </p> 37 <h2> 5. Greyscale dithering </h2> 38 39 <p> At first sight, generalising dithering to three grey scales seems pretty 40 straightforward: just add grey 0.5 in the middle of the palette and dither 41 pixels in the [0, 0.5] range with black and grey, and pixels in the [0.5, 1] 42 range with grey and white. Here are two different results with 8×8 Bayer 43 ordered dithering and with serpentine Floyd-Steinberg error diffusion: </p> 44 45 <p style="text-align: center;"> 46 <img src="out/lena5-0-1.png" width="256" height="256" 47 class="inline" alt="8×8 Bayer ordered dithering, 3 colours" /> 48 <img src="out/grad5-0-1.png" width="32" height="256" 49 class="inline" alt="8×8 Bayer ordered dithering gradient, 3 colours" /> 50 <img src="out/lena5-0-2.png" width="256" height="256" 51 class="inline" alt="serpentine FS error diffusion, 3 colours" /> 52 <img src="out/grad5-0-2.png" width="32" height="256" 53 class="inline" alt="serpentine FS error diffusion gradient, 3 colours" /> 54 </p> 55 56 <p> These are pretty much the images that imaging software such as The Gimp 57 would give (using “positioned” and “Floyd-Steinberg” dithering modes). </p> 58 59 <p> Unfortunately the result is not as good as expected: the white pattern 60 on Lena’s cheeks is visually disturbing, and there is a lot of 0.5 grey in 61 the image. Also, the whole image looks darker than with pure black-and-white 62 dithering, but these previous dithering results looked a lot brighter than 63 the original image anyway. </p> 64 65 <p> All these issues have to do with the output media’s <b>gamma</b>. </p> 66 67 <h3> 5.1. Introducing gamma </h3> 68 69 <p> If you are reading this document on a computer screen, you may have 70 noticed that the black and white 50% pattern was closer to a 0.73 greyscale 71 (left) than to the intuitively expected 0.5 value (right). If you are reading 72 a printed copy, it might be a different matter. </p> 73 74 <p style="text-align: center;"> 75 <img src="out/pat5-1-1.png" width="240" height="80" 76 class="inline" alt="introducing gamma" /> 77 </p> 78 79 <p> The mapping linking greyscale steps to intensities is called <b>gamma 80 correction</b>. An approximate law for gamma correction is given as 81 <i>I = v<small><sup>γ</sup></small></i> where <i>v</i> is the coded colour 82 value (between 0 and 1), <i>I</i> is the perceived colour intensity (between 83 0% and 100%) and <i>γ</i> is the gamma. A pattern made of even-numbered 84 0%-intensity pixels and 100%-intensity pixels has an intensity of 50% by 85 definition. But the corresponding greyscale depends on the gamma value. </p> 86 87 <p> Most modern computer systems use the sRGB gamma model close to the law 88 with <i>γ = 2.2</i>. As can be seen, it is highly non-linear: </p> 89 90 <p style="text-align: center;"> 91 <img src="fig5-1-1.png" width="460" height="256" alt="introducing gamma" /> 92 </p> 93 94 <p> Éric Brasseur wrote <a 95 href="http://www.4p8.com/eric.brasseur/gamma.html">a pretty comprehensive 96 essay</a> [16] about why on a computer screen a 50% black and white pattern 97 should be scaled down to a grey value of 0.73 instead of 0.5 and how major 98 computer graphics software totally misses the point. Conversely, it clearly 99 means that a grey value of 0.5 should not be emulated with a 50% dither 100 pattern. </p> 101 102 <p> The following figure shows the gamma curve for the naïve three-colour 103 greyscale gradient we saw above (red curve) compared to the two-colour 104 gradient (blue curve). Two major observations can be made: the new curve is 105 far closer to a perfect, linear gradient, but there is a singularity in the 106 middle of the curve, meaning a break in the gradient’s smoothness. </p> 107 108 <p style="text-align: center;"> 109 <img src="fig5-1-2.png" width="460" height="256" alt="3-colour gamma" /> 110 </p> 111 112 <p> There are three possible ways to reduce the singularity and make the 113 gradient smoother and/or closer to the original colours: </p> 114 115 <ul> 116 <li> Choose a different middle grey value, for instance choosing grey 0.73 117 will cancel the singularity and match the two-colour gradients we have 118 been using so far. This is not always possible if the output palette 119 is fixed. </li> 120 <li> Don’t place the grey value at the middle of the gradient, for instance 121 a value of around 25% intensity will again match the previous two-colour 122 gradients. </li> 123 <li> <b>Gamma-correct</b> input pixels before assigning them an output 124 value. This ensures that the resulting gradient is perfectly linear 125 and has no singularity. 126 </li> 127 </ul> 128 129 <h3> 5.2. Gamma correction </h3> 130 131 <p> Gamma correction consists in converting pixel values into intensity values 132 before performing operations on them, then reconverting them to pixel values 133 before displaying them. The exact same algorithms can be used, they just 134 operate on slightly different data. </p> 135 136 <p style="text-align: center;"> 137 <img src="fig5-1-3.png" width="460" height="256" alt="3-colour gamma coorection" /> 138 </p> 139 140 <p> Here are the results of gamma-correcting input pixels before doing 141 any computation on them, then using serpentine Floyd-Steinberg error 142 diffusion: </p> 159 143 160 144 <p style="text-align: center;"> 161 145 <img src="out/lena5-2-1.png" width="256" height="256" 162 class="inline" alt=" Floyd-Steinberg, sum of absolute differences" />163 <img src="out/grad5-2-1.png" width=" 64" height="256"164 class="inline" alt=" Floyd-Steinberg, sum of absolute differencesgradient" />146 class="inline" alt="serpentine FS, 2 colours, gamma-corrected" /> 147 <img src="out/grad5-2-1.png" width="32" height="256" 148 class="inline" alt="serpentine FS, 2 colours, gamma-corrected gradient" /> 165 149 <img src="out/lena5-2-2.png" width="256" height="256" 166 class="inline" alt="Floyd-Steinberg, euclidian distance" /> 167 <img src="out/grad5-2-2.png" width="64" height="256" 168 class="inline" alt="Floyd-Steinberg, euclidian distance gradient" /> 169 </p> 170 171 <p> Distances can be computed in another space. For instance, the <b>HSV 172 space</b> allows to give colour variations a smaller influence than brightness 173 variations simply by changing the HSV cone’s height. On the left is spatial 174 Floyd-Steinberg using the euclidian distance in an HSV cone of height 1 and 175 base radius 1. On the right is the same distance within a cone of height 3 and 176 base radius 1: </p> 150 class="inline" alt="serpentine FS, 3 colours, gamma-corrected" /> 151 <img src="out/grad5-2-2.png" width="32" height="256" 152 class="inline" alt="serpentine FS, 3 colours, gamma-corrected gradient" /> 153 </p> 154 155 <p> Two-colour dithering is not visually satisfying: dark areas lack much 156 detail because the gamma curve is very flat at low intensities. However, 157 the result itself is far more accurate that previously. The problem, while 158 still visible, is even less important with three-colour dithering: the image 159 on the right is superior to what The Gimp or Adobe Photoshop are able to 160 come up with. </p> 161 162 <p> Finally, this is gamma-corrected 4-colour dithering: </p> 177 163 178 164 <p style="text-align: center;"> 179 165 <img src="out/lena5-2-3.png" width="256" height="256" 180 class="inline" alt="Floyd-Steinberg, 1×1 HSV cone" /> 181 <img src="out/grad5-2-3.png" width="64" height="256" 182 class="inline" alt="Floyd-Steinberg, 1×1 HSV cone gradient" /> 183 <img src="out/lena5-2-4.png" width="256" height="256" 184 class="inline" alt="Floyd-Steinberg, 3×1 HSV cone" /> 185 <img src="out/grad5-2-4.png" width="64" height="256" 186 class="inline" alt="Floyd-Steinberg, 3×1 HSV cone gradient" /> 187 </p> 188 189 <h3> 5.3. Reducing visual artifacts </h3> 190 191 <p> The following patterns show four ways to dither the same colour using 192 our 8-colour palette: </p> 193 194 <ul> 195 <li> 1/2 black, 3/8 blue, 1/8 white </li> 196 <li> 1/2 blue, 3/8 black, 1/8 yellow </li> 197 <li> 3/8 black, 3/8 blue, 1/8 red, 1/8 cyan </li> 198 <li> 1/2 blue, 1/4 black, 1/8 red, 1/8 green </li> 199 </ul> 200 201 <p> All patterns visually blend to the same shade, but the last one is 202 the most visually appealing: </p> 203 204 <p style="text-align: center;"> 205 <img src="out/pat5-2-1.png" width="320" height="160" 206 class="inline" alt="3 ways to dither the same colour" /> 207 </p> 208 209 <p> Shaked, Arad, Fitzhugh and Sobel introduce the <b>minimum brightness 210 variation criterion</b> (MBVC), stating that in order to reduce halftone noise, 211 the halftone set which should be used to render the desired colour should be 212 the one whose brightness variation is minimal [25]. Similarly, Klassen <i>et 213 al.</i> suggest the selection of low-contrast colour combiation wherever 214 possible [24]. </p> 215 216 <h3> 5.4. Colour sub-block error diffusion </h3> 217 218 <p> Adapting sub-block error diffusion to colour images is almost 219 straightforward. The major problem is proper weighting in the block-choosing 220 step. It is a crucial part of the algorithm, and we have yet to find an 221 efficient method to perform it. </p> 222 223 <p> The images below shows the result using our now well-known “lines” tile 224 list, using respectively the 8-colour palette and the 16-colour palette: </p> 225 226 <p style="text-align: center;"> 227 <img src="out/lena5-4-1.png" width="256" height="256" 228 class="inline" alt="8-colour sub-block error diffusion" /> 229 <img src="out/grad5-4-1.png" width="64" height="256" 230 class="inline" alt="8-colour sub-block error diffusion gradient" /> 231 <img src="out/lena5-4-2.png" width="256" height="256" 232 class="inline" alt="16-colour sub-block error diffusion" /> 233 <img src="out/grad5-4-2.png" width="64" height="256" 234 class="inline" alt="16-colour sub-block error diffusion gradient" /> 235 </p> 236 237 <p> Speed is starting to become a problematic issue. A 16-colour palette can 238 generate 65,536 unique 2×2 blocks. Exhaustive search to determine the best 239 tile is no longer realistic, and we need to find better ways to find the 240 best matching block. </p> 166 class="inline" alt="serpentine FS, 4 colours, gamma-corrected" /> 167 <img src="out/grad5-2-3.png" width="32" height="256" 168 class="inline" alt="serpentine FS, 4 colours, gamma-corrected gradient" /> 169 </p> 170 171 <h3> 5.3. Greyscale sub-block error diffusion </h3> 172 173 <p> Support for greyscale and gamma correction is trivially added to our 174 sub-block error diffusion method. Best-tile choosing is done in contrast 175 space, while error diffusion is done in intensity space. </p> 176 177 <p> The following picture uses all possible 4-greyscale 2×2 tiles. The 178 output quality is very close to what standard, pixel-per-pixel error diffusion 179 achieves: </p> 180 181 <p style="text-align: center;"> 182 <img src="out/lena5-3-1.png" width="256" height="256" 183 class="inline" alt="sub-block FS, full 4-grey tiles" /> 184 <img src="out/grad5-3-1.png" width="32" height="256" 185 class="inline" alt="sub-block FS, full 4-grey tiles gradient" /> 186 </p> 187 188 <p> And finally, this picture only uses 4-greyscale combinations of the 189 “lines” tiles seen previously: </p> 190 191 <p style="text-align: center;"> 192 <img src="fig5-3-1.png" width="307" height="253" 193 class="matrix" alt="list of 4-grey 2×2 pixel blocks" /> 194 <img src="out/lena5-3-2.png" width="256" height="256" 195 class="inline" alt="sub-block FS, lines 4-grey tiles" /> 196 <img src="out/grad5-3-2.png" width="32" height="256" 197 class="inline" alt="sub-block FS, lines 4-grey tiles gradient" /> 198 </p> 241 199 242 200 <div style="float: left;"> 243 <a href="part4.html"> Greyscaledithering <<<</a>201 <a href="part4.html">Model-based dithering <<<</a> 244 202 </div> 245 203 <div style="float: right;"> 246 <a href="part6.html">>>> Photographic mosaics</a>204 <a href="part6.html">>>> Colour dithering</a> 247 205 </div> 248 206 <div style="text-align: center;"> -
www/study/part6.html
r2206 r2215 9 9 <meta name="GENERATOR" content="vim" /> 10 10 <meta name="Author" content="sam@zoy.org (Sam Hocevar)" /> 11 <meta name="Description" content="Libcaca study - 6. Photographic mosaics" />11 <meta name="Description" content="Libcaca study - 6. Colour dithering" /> 12 12 <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" /> 13 <title>Libcaca study - 6. Photographic mosaics</title>13 <title>Libcaca study - 6. Colour dithering</title> 14 14 <link rel="icon" type="image/x-icon" href="/favicon.ico" /> 15 15 <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" /> … … 26 26 27 27 <div style="float: left;"> 28 <a href="part5.html"> Colourdithering <<<</a>28 <a href="part5.html">Greyscale dithering <<<</a> 29 29 </div> 30 30 <div style="float: right;"> 31 <a href=" biblio.html">>>> Bibliography</a>31 <a href="part7.html">>>> Photographic mosaics</a> 32 32 </div> 33 33 <div style="text-align: center;"> … … 35 35 </div> 36 36 37 <h2> 6. Photographic mosaics </h2> 38 39 <p> Photographic mosaics are montages of smaller images creating the illusion 40 of a bigger image. </p> 41 42 <p> Since we don’t have many images at our disposal, we will simply cut Lena 43 into small chunks (called <b>tiles</b>) and use these parts to create mosaics. 44 This is our <b>tile database</b>: </p> 45 46 <p style="text-align: center;"> 47 <img src="out/lena6-0-1.png" width="408" height="288" 48 class="inline" alt="Patterns taken from Lena" /> 49 </p> 50 51 <p> Generating a photomosaic consists in subdividing the original picture 52 into <i>x</i> rectangular cells and find <i>x</i> tiles in the database 53 (with or without duplicates, depending on the set of rules that is decided) 54 so that when recombined the resulting image resembles the original picture. 55 By the way, this technique is covered by Runaway Technology Inc.’s 56 <a href="http://www.freepatentsonline.com/6137498.html">U.S. patent 57 6137498</a> [9]. </p> 58 59 <p> Picking the right tile for the right cell in the grid is a very 60 expensive and complicated operation. One of the biggest problems is the 61 cost of a database lookup: comparing each tile area pixel-by-pixel 62 is an O(N) operation where N is the size of the database. We can resort 63 to <b>image classification</b> in order to speed up database lookups. </p> 64 65 <h3> 6.1. Image classification </h3> 66 67 <p> One of the simplest image classification techniques is the storage of 68 each tile’s <b>average colour</b> into a separate database that is used for 69 best match lookups. Of course, this computation should be gamma-corrected: 70 </p> 71 72 <p style="text-align: center;"> 73 <img src="out/lena6-1-1.png" width="168" height="120" 74 class="inline" alt="1 feature extracted from Lena patterns" /> 75 </p> 76 77 <p> When creating the mosaic, we then only need to check the average colour 78 instead of comparing each pixel one by one. Below is the result of the 79 technique applied on a portion of the Lena picture: </p> 80 81 <p style="text-align: center;"> 82 <img src="out/lena6-1-2.png" width="80" height="80" 83 class="inlinetop" alt="Lena (detail)" /> 84 <img src="out/lena6-1-3.png" width="416" height="416" 85 class="inline" alt="Mosaic created from Lena’s detail" /> 86 </p> 87 88 <p> Better results can be achieved by storing <b>four colour values</b>, one 89 for each corner of the tile: </p> 90 91 <p style="text-align: center;"> 92 <img src="out/lena6-1-4.png" width="248" height="176" 93 class="inline" alt="4 features extracted from Lena patterns" /> 94 </p> 95 96 <p> Having 12 values per tile (4 RGB triplets) is still a lot less than the 97 original count of 3072 (for 32×32 tiles), and the results show clear 98 improvement. For instance the feathers-hat frontier is now a lot smoother: </p> 99 100 <p style="text-align: center;"> 101 <img src="out/lena6-1-2.png" width="80" height="80" 102 class="inlinetop" alt="Lena (detail)" /> 103 <img src="out/lena6-1-5.png" width="416" height="416" 104 class="inline" alt="Mosaic created from Lena’s detail" /> 105 </p> 106 107 <h3> 6.2. Error diffusion </h3> 108 109 <p> TODO </p> 110 111 <h3> 6.3. Colour ASCII art </h3> 112 113 <!-- 114 <p> We 115 116 There are many ways to tackle the problem of colour ASCII art 117 118 , also referred to as ANSI art, 119 --> 120 121 <p style="text-align: center;"> 122 <img src="fig6-3-1.png" width="395" height="196" 123 class="matrix" alt="ASCII art tiles" /> 124 </p> 37 <h2> 6. Colour dithering </h2> 38 39 <p> Dithering colour images means dithering three-dimensional elements (RGB 40 pixels) instead of one-dimensional grey values. It is very complex and 41 depends on the output media even more than greyscale dithering. </p> 42 43 <h3> 6.1. Separate-space dithering </h3> 44 45 <p> In some cases it is possible to perform three one-dimensional dithering 46 operations instead of one three-dimensional one. Consider for instance the 47 following palette: 48 </p> 49 50 <p style="text-align: center;"> 51 <img src="out/pat6-1-1.png" width="512" height="64" 52 class="inline" alt="8-colour RGB palette" /> 53 </p> 54 55 <p> It is made of the eight possible red/green/blue combinations made of 0 56 and 1 values: </p> 57 58 <div style="text-align: center;"> 59 <table style="margin: auto;"> 60 <tr> 61 <td><b>Red</b></td> 62 <td>0</td> <td>0</td> <td>1</td> <td>1</td> 63 <td>0</td> <td>0</td> <td>1</td> <td>1</td> 64 </tr> <tr> 65 <td><b>Green</b></td> 66 <td>0</td> <td>0</td> <td>0</td> <td>0</td> 67 <td>1</td> <td>1</td> <td>1</td> <td>1</td> 68 </tr> <tr> 69 <td><b>Blue</b></td> 70 <td>0</td> <td>1</td> <td>0</td> <td>1</td> 71 <td>0</td> <td>1</td> <td>0</td> <td>1</td> 72 </tr> 73 </table> 74 </div> 75 76 <p> One way of dithering an image using this palette is to convert the image 77 into three greyscale images (separating the red, green and blue channels), 78 dither each subimage to two colours separately and recombine the images into 79 three channels. For instance, if at a given pixel the red channel is dithered 80 to 1 and the green and blue channels are dithered to 0, the final pixel will 81 be [1 0 0] which is the colour red. </p> 82 83 <p> Separate-space dithering works by splitting the image into three red, 84 green and blue channels. Each of this channel is treated as a greyscale image 85 that is then dithered to black and white using any dithering method seen 86 previously. The resulting images are then treated again as three red, green 87 and blue channels and recombined into the final image: </p> 88 89 <p style="text-align: center;"> 90 <img src="fig6-1-7.png" width="704" height="560" 91 class="matrix" alt="separate-space dithering" /> 92 </p> 93 94 <p> Here are the results with serpentine Floyd-Steinberg dithering applied to 95 each channel. On the left, no colour correction, as The Gimp or Photoshop would 96 do; on the right, gamma-corrected dithering: </p> 97 98 <p style="text-align: center;"> 99 <img src="out/lena6-1-1.png" width="256" height="256" 100 class="inline" alt="serpentine FS, 8 colours" /> 101 <img src="out/grad6-1-1.png" width="64" height="256" 102 class="inline" alt="serpentine FS, 8 colours gradient" /> 103 <img src="out/lena6-1-2.png" width="256" height="256" 104 class="inline" alt="serpentine FS, 8 colours, gamma-corrected" /> 105 <img src="out/grad6-1-2.png" width="64" height="256" 106 class="inline" alt="serpentine FS, 8 colours, gamma-corrected gradient" /> 107 </p> 108 109 <h3> 6.2. Accounting for other dimensions </h3> 110 111 <p> The previous palette was suitable for separate-space dithering. Such a 112 palette is called <b>separable</b> or <b>orthogonal</b>. </p> 113 114 <p> Here is a palette that cannot be used in the same way: </p> 115 116 <p style="text-align: center;"> 117 <img src="out/pat6-2-2.png" width="512" height="128" 118 class="inline" alt="8-colour RGB palette" /> 119 </p> 120 121 <p> As can be seen, it does not have the [0.5 0.5 0.5] grey colour, or the 122 [1 0.5 0] orange colour, for instance, despite having other combinations of 123 0, 0.5 and 1 values: </p> 124 125 <div style="text-align: center;"> 126 <table style="margin: auto; border: 1px;"> 127 <tr> 128 <td><b>Red</b></td> 129 <td>0</td> <td>0</td> <td>0.5</td> <td>0.5</td> 130 <td>0</td> <td>0</td> <td>0.5</td> <td>0.7</td> 131 <td>0.3</td> <td>0</td> <td>1</td> <td>1</td> 132 <td>0</td> <td>0</td> <td>1</td> <td>1</td> 133 </tr> <tr> 134 <td><b>Green</b></td> 135 <td>0</td> <td>0</td> <td>0</td> <td>0</td> 136 <td>0.5</td> <td>0.5</td> <td>0.5</td> <td>0.7</td> 137 <td>0.3</td> <td>0</td> <td>0</td> <td>0</td> 138 <td>1</td> <td>1</td> <td>1</td> <td>1</td> 139 </tr> <tr> 140 <td><b>Blue</b></td> 141 <td>0</td> <td>0.5</td> <td>0</td> <td>0.5</td> 142 <td>0</td> <td>0.5</td> <td>0</td> <td>0.7</td> 143 <td>0.3</td> <td>1</td> <td>0</td> <td>1</td> 144 <td>0</td> <td>1</td> <td>0</td> <td>1</td> 145 </tr> 146 </table> 147 </div> 148 149 <p> It is no longer possible to compute the closest colour in each colourspace 150 and combine them into an RGB colour, since that colour might not be available 151 in the palette. So we need to determine what the “closest colour” means when 152 dealing with the whole colour spectrum. </p> 153 154 <p> The following examples show gamma-corrected Floyd-Steinberg using the 155 above 16-colour palette and two different definitions of distance: the <b>sum 156 of absolute differences</b> and the <b>euclidian distance</b>. The sum of 157 absolute differences performs pretty poorly because it does not penalise wide 158 disparities: </p> 159 160 <p style="text-align: center;"> 161 <img src="out/lena6-2-1.png" width="256" height="256" 162 class="inline" alt="Floyd-Steinberg, sum of absolute differences" /> 163 <img src="out/grad6-2-1.png" width="64" height="256" 164 class="inline" alt="Floyd-Steinberg, sum of absolute differences gradient" /> 165 <img src="out/lena6-2-2.png" width="256" height="256" 166 class="inline" alt="Floyd-Steinberg, euclidian distance" /> 167 <img src="out/grad6-2-2.png" width="64" height="256" 168 class="inline" alt="Floyd-Steinberg, euclidian distance gradient" /> 169 </p> 170 171 <p> Distances can be computed in another space. For instance, the <b>HSV 172 space</b> allows to give colour variations a smaller influence than brightness 173 variations simply by changing the HSV cone’s height. On the left is spatial 174 Floyd-Steinberg using the euclidian distance in an HSV cone of height 1 and 175 base radius 1. On the right is the same distance within a cone of height 3 and 176 base radius 1: </p> 177 178 <p style="text-align: center;"> 179 <img src="out/lena6-2-3.png" width="256" height="256" 180 class="inline" alt="Floyd-Steinberg, 1×1 HSV cone" /> 181 <img src="out/grad6-2-3.png" width="64" height="256" 182 class="inline" alt="Floyd-Steinberg, 1×1 HSV cone gradient" /> 183 <img src="out/lena6-2-4.png" width="256" height="256" 184 class="inline" alt="Floyd-Steinberg, 3×1 HSV cone" /> 185 <img src="out/grad6-2-4.png" width="64" height="256" 186 class="inline" alt="Floyd-Steinberg, 3×1 HSV cone gradient" /> 187 </p> 188 189 <h3> 6.3. Reducing visual artifacts </h3> 190 191 <p> The following patterns show four ways to dither the same colour using 192 our 8-colour palette: </p> 193 194 <ul> 195 <li> 1/2 black, 3/8 blue, 1/8 white </li> 196 <li> 1/2 blue, 3/8 black, 1/8 yellow </li> 197 <li> 3/8 black, 3/8 blue, 1/8 red, 1/8 cyan </li> 198 <li> 1/2 blue, 1/4 black, 1/8 red, 1/8 green </li> 199 </ul> 200 201 <p> All patterns visually blend to the same shade, but the last one is 202 the most visually appealing: </p> 203 204 <p style="text-align: center;"> 205 <img src="out/pat6-2-1.png" width="320" height="160" 206 class="inline" alt="3 ways to dither the same colour" /> 207 </p> 208 209 <p> Shaked, Arad, Fitzhugh and Sobel introduce the <b>minimum brightness 210 variation criterion</b> (MBVC), stating that in order to reduce halftone noise, 211 the halftone set which should be used to render the desired colour should be 212 the one whose brightness variation is minimal [25]. Similarly, Klassen <i>et 213 al.</i> suggest the selection of low-contrast colour combiation wherever 214 possible [24]. </p> 215 216 <h3> 6.4. Colour sub-block error diffusion </h3> 217 218 <p> Adapting sub-block error diffusion to colour images is almost 219 straightforward. The major problem is proper weighting in the block-choosing 220 step. It is a crucial part of the algorithm, and we have yet to find an 221 efficient method to perform it. </p> 222 223 <p> The images below shows the result using our now well-known “lines” tile 224 list, using respectively the 8-colour palette and the 16-colour palette: </p> 225 226 <p style="text-align: center;"> 227 <img src="out/lena6-4-1.png" width="256" height="256" 228 class="inline" alt="8-colour sub-block error diffusion" /> 229 <img src="out/grad6-4-1.png" width="64" height="256" 230 class="inline" alt="8-colour sub-block error diffusion gradient" /> 231 <img src="out/lena6-4-2.png" width="256" height="256" 232 class="inline" alt="16-colour sub-block error diffusion" /> 233 <img src="out/grad6-4-2.png" width="64" height="256" 234 class="inline" alt="16-colour sub-block error diffusion gradient" /> 235 </p> 236 237 <p> Speed is starting to become a problematic issue. A 16-colour palette can 238 generate 65,536 unique 2×2 blocks. Exhaustive search to determine the best 239 tile is no longer realistic, and we need to find better ways to find the 240 best matching block. </p> 125 241 126 242 <div style="float: left;"> 127 <a href="part5.html"> Colourdithering <<<</a>243 <a href="part5.html">Greyscale dithering <<<</a> 128 244 </div> 129 245 <div style="float: right;"> 130 <a href=" biblio.html">>>> Bibliography</a>246 <a href="part7.html">>>> Photographic mosaics</a> 131 247 </div> 132 248 <div style="text-align: center;"> -
www/study/part7.html
r2214 r2215 9 9 <meta name="GENERATOR" content="vim" /> 10 10 <meta name="Author" content="sam@zoy.org (Sam Hocevar)" /> 11 <meta name="Description" content="Libcaca study - 6. Photographic mosaics" />11 <meta name="Description" content="Libcaca study - 7. Photographic mosaics" /> 12 12 <meta name="Keywords" content="libcaca, ASCII, ASCII ART, console, text mode, ncurses, slang, AAlib, dithering, thresholding" /> 13 <title>Libcaca study - 6. Photographic mosaics</title>13 <title>Libcaca study - 7. Photographic mosaics</title> 14 14 <link rel="icon" type="image/x-icon" href="/favicon.ico" /> 15 15 <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico" /> … … 26 26 27 27 <div style="float: left;"> 28 <a href="part 5.html">Colour dithering <<<</a>28 <a href="part6.html">Colour dithering <<<</a> 29 29 </div> 30 30 <div style="float: right;"> … … 35 35 </div> 36 36 37 <h2> 6. Photographic mosaics </h2>37 <h2> 7. Photographic mosaics </h2> 38 38 39 39 <p> Photographic mosaics are montages of smaller images creating the illusion … … 45 45 46 46 <p style="text-align: center;"> 47 <img src="out/lena 6-0-1.png" width="408" height="288"47 <img src="out/lena7-0-1.png" width="408" height="288" 48 48 class="inline" alt="Patterns taken from Lena" /> 49 49 </p> … … 63 63 to <b>image classification</b> in order to speed up database lookups. </p> 64 64 65 <h3> 6.1. Image classification </h3>65 <h3> 7.1. Image classification </h3> 66 66 67 67 <p> One of the simplest image classification techniques is the storage of … … 71 71 72 72 <p style="text-align: center;"> 73 <img src="out/lena 6-1-1.png" width="168" height="120"73 <img src="out/lena7-1-1.png" width="168" height="120" 74 74 class="inline" alt="1 feature extracted from Lena patterns" /> 75 75 </p> … … 80 80 81 81 <p style="text-align: center;"> 82 <img src="out/lena 6-1-2.png" width="80" height="80"82 <img src="out/lena7-1-2.png" width="80" height="80" 83 83 class="inlinetop" alt="Lena (detail)" /> 84 <img src="out/lena 6-1-3.png" width="416" height="416"84 <img src="out/lena7-1-3.png" width="416" height="416" 85 85 class="inline" alt="Mosaic created from Lena’s detail" /> 86 86 </p> … … 90 90 91 91 <p style="text-align: center;"> 92 <img src="out/lena 6-1-4.png" width="248" height="176"92 <img src="out/lena7-1-4.png" width="248" height="176" 93 93 class="inline" alt="4 features extracted from Lena patterns" /> 94 94 </p> … … 99 99 100 100 <p style="text-align: center;"> 101 <img src="out/lena 6-1-2.png" width="80" height="80"101 <img src="out/lena7-1-2.png" width="80" height="80" 102 102 class="inlinetop" alt="Lena (detail)" /> 103 <img src="out/lena 6-1-5.png" width="416" height="416"103 <img src="out/lena7-1-5.png" width="416" height="416" 104 104 class="inline" alt="Mosaic created from Lena’s detail" /> 105 105 </p> 106 106 107 <h3> 6.2. Error diffusion </h3>107 <h3> 7.2. Error diffusion </h3> 108 108 109 109 <p> TODO </p> 110 110 111 <h3> 6.3. Colour ASCII art </h3>111 <h3> 7.3. Colour ASCII art </h3> 112 112 113 113 <!-- … … 120 120 121 121 <p style="text-align: center;"> 122 <img src="fig 6-3-1.png" width="395" height="196"122 <img src="fig7-3-1.png" width="395" height="196" 123 123 class="matrix" alt="ASCII art tiles" /> 124 124 </p> 125 125 126 126 <div style="float: left;"> 127 <a href="part 5.html">Colour dithering <<<</a>127 <a href="part6.html">Colour dithering <<<</a> 128 128 </div> 129 129 <div style="float: right;"> -
www/study/study.py
r2211 r2215 1727 1727 ERROR_SUBFS33[y][x][y][1 + x] = -1 1728 1728 1729 # Output 3.7.1: direct binary search, iteration 0 1730 # Output 3.7.2: direct binary search, iteration 1 1731 # Output 3.7.3: direct binary search, iteration 2 1732 # Output 3.7.4: direct binary search, iteration 5 1733 def test37x(src): 1729 ############################################################################## 1730 if chapter(4): 1731 print "Chapter 4. Model-based dithering" 1732 1733 # Output 4.2.1: direct binary search, iteration 0 1734 # Output 4.2.2: direct binary search, iteration 1 1735 # Output 4.2.3: direct binary search, iteration 2 1736 # Output 4.2.4: direct binary search, iteration 5 1737 def test42x(src): 1734 1738 random.seed(0) 1735 1739 (w, h) = src.size() … … 1741 1745 return dest 1742 1746 1743 def test 37y(src, dest):1747 def test42y(src, dest): 1744 1748 threshold = 0.4 1745 1749 kernel = Matrix(6, 6, 0.) # have a border of zeroes … … 1834 1838 return dest 1835 1839 1836 if chapter( 3):1837 tmp = test 37x(grad256bw)1838 tmp.save("out/grad 3-7-1.png")1839 tmp = test 37y(grad256bw, tmp)1840 tmp.save("out/grad 3-7-2.png")1841 tmp = test 37y(grad256bw, tmp)1842 tmp.save("out/grad 3-7-3.png")1843 tmp = test 37y(grad256bw, tmp)1844 tmp = test 37y(grad256bw, tmp)1845 tmp = test 37y(grad256bw, tmp)1846 tmp.save("out/grad 3-7-4.png")1847 1848 if chapter( 3):1849 tmp = test 37x(lena256bw)1850 tmp.save("out/lena 3-7-1.png")1851 tmp = test 37y(lena256bw, tmp)1852 tmp.save("out/lena 3-7-2.png")1853 tmp = test 37y(lena256bw, tmp)1854 tmp.save("out/lena 3-7-3.png")1855 tmp = test 37y(lena256bw, tmp)1856 tmp = test 37y(lena256bw, tmp)1857 tmp = test 37y(lena256bw, tmp)1858 tmp.save("out/lena 3-7-4.png")1840 if chapter(4): 1841 tmp = test42x(grad256bw) 1842 tmp.save("out/grad4-2-1.png") 1843 tmp = test42y(grad256bw, tmp) 1844 tmp.save("out/grad4-2-2.png") 1845 tmp = test42y(grad256bw, tmp) 1846 tmp.save("out/grad4-2-3.png") 1847 tmp = test42y(grad256bw, tmp) 1848 tmp = test42y(grad256bw, tmp) 1849 tmp = test42y(grad256bw, tmp) 1850 tmp.save("out/grad4-2-4.png") 1851 1852 if chapter(4): 1853 tmp = test42x(lena256bw) 1854 tmp.save("out/lena4-2-1.png") 1855 tmp = test42y(lena256bw, tmp) 1856 tmp.save("out/lena4-2-2.png") 1857 tmp = test42y(lena256bw, tmp) 1858 tmp.save("out/lena4-2-3.png") 1859 tmp = test42y(lena256bw, tmp) 1860 tmp = test42y(lena256bw, tmp) 1861 tmp = test42y(lena256bw, tmp) 1862 tmp.save("out/lena4-2-4.png") 1859 1863 1860 1864 ############################################################################## 1861 if chapter( 4):1862 print "Chapter 4. Greyscale dithering"1863 1864 # Output 4.0.1: 4x4 Bayer dithering, 3 colours1865 def test 401(src, mat):1865 if chapter(5): 1866 print "Chapter 5. Greyscale dithering" 1867 1868 # Output 5.0.1: 4x4 Bayer dithering, 3 colours 1869 def test501(src, mat): 1866 1870 (w, h) = src.size() 1867 1871 dest = Image((w, h)) … … 1878 1882 return dest 1879 1883 1880 if chapter( 4):1881 test 401(grad256bw, DITHER_BAYER88).save("out/grad4-0-1.png")1882 test 401(lena256bw, DITHER_BAYER88).save("out/lena4-0-1.png")1883 1884 # Output 4.0.2: standard Floyd-Steinberg, 3 colours1885 def test 402(src, mat, serpentine):1884 if chapter(5): 1885 test501(grad256bw, DITHER_BAYER88).save("out/grad5-0-1.png") 1886 test501(lena256bw, DITHER_BAYER88).save("out/lena5-0-1.png") 1887 1888 # Output 5.0.2: standard Floyd-Steinberg, 3 colours 1889 def test502(src, mat, serpentine): 1886 1890 (w, h) = src.size() 1887 1891 dest = Image((w, h)) … … 1920 1924 return dest 1921 1925 1922 if chapter( 4):1923 test 402(grad256bw, ERROR_FSTEIN, True).save("out/grad4-0-2.png")1924 test 402(lena256bw, ERROR_FSTEIN, True).save("out/lena4-0-2.png")1925 1926 # Pattern 4.1.1: gamma-corrected 50% grey, black-white halftone, 50% grey1927 if chapter( 4):1926 if chapter(5): 1927 test502(grad256bw, ERROR_FSTEIN, True).save("out/grad5-0-2.png") 1928 test502(lena256bw, ERROR_FSTEIN, True).save("out/lena5-0-2.png") 1929 1930 # Pattern 5.1.1: gamma-corrected 50% grey, black-white halftone, 50% grey 1931 if chapter(5): 1928 1932 dest = Image((240, 80)) 1929 1933 for y in range(80): … … 1935 1939 for x in range(160, 240): 1936 1940 dest.setGray(x, y, 0.5) 1937 dest.save("out/pat 4-1-1.png")1938 1939 # Output 4.2.1: gamma-corrected 2-colour Floyd-Steinberg1940 # Output 4.2.2: gamma-corrected 3-colour Floyd-Steinberg1941 # Output 4.2.3: gamma-corrected 4-colour Floyd-Steinberg1942 def test 42x(src, mat, serpentine, threshold):1941 dest.save("out/pat5-1-1.png") 1942 1943 # Output 5.2.1: gamma-corrected 2-colour Floyd-Steinberg 1944 # Output 5.2.2: gamma-corrected 3-colour Floyd-Steinberg 1945 # Output 5.2.3: gamma-corrected 4-colour Floyd-Steinberg 1946 def test52x(src, mat, serpentine, threshold): 1943 1947 (w, h) = src.size() 1944 1948 dest = Image((w, h)) … … 1977 1981 return dest 1978 1982 1979 if chapter( 4):1980 test 42x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto2).save("out/grad4-2-1.png")1981 test 42x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto2).save("out/lena4-2-1.png")1982 test 42x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto3).save("out/grad4-2-2.png")1983 test 42x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto3).save("out/lena4-2-2.png")1984 test 42x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto4).save("out/grad4-2-3.png")1985 test 42x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto4).save("out/lena4-2-3.png")1986 1987 # Output 4.3.1: full 4-colour block error diffusion1983 if chapter(5): 1984 test52x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto2).save("out/grad5-2-1.png") 1985 test52x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto2).save("out/lena5-2-1.png") 1986 test52x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto3).save("out/grad5-2-2.png") 1987 test52x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto3).save("out/lena5-2-2.png") 1988 test52x(grad256bw, ERROR_FSTEIN, True, Gamma.Cto4).save("out/grad5-2-3.png") 1989 test52x(lena256bw, ERROR_FSTEIN, True, Gamma.Cto4).save("out/lena5-2-3.png") 1990 1991 # Output 5.3.1: full 4-colour block error diffusion 1988 1992 GREY22 = [] 1989 1993 for n in range(4*4*4*4): … … 1992 1996 GREY22.append([[vals[a], vals[b]], [vals[c], vals[d]]]) 1993 1997 1994 if chapter( 4):1998 if chapter(5): 1995 1999 subblock(grad256bw, GREY22, 1996 ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/grad 4-3-1.png")2000 ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/grad5-3-1.png") 1997 2001 subblock(lena256bw, GREY22, 1998 ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/lena 4-3-1.png")1999 2000 # Output 4.3.2: 4-colour block error diffusion with only line tiles2002 ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/lena5-3-1.png") 2003 2004 # Output 5.3.2: 4-colour block error diffusion with only line tiles 2001 2005 GREYLINES22 = [] 2002 2006 for n in range(4*4*4*4): … … 2007 2011 GREYLINES22.append([[vals[a], vals[b]], [vals[c], vals[d]]]) 2008 2012 2009 if chapter( 4):2013 if chapter(5): 2010 2014 subblock(grad256bw, GREYLINES22, 2011 ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/grad 4-3-2.png")2015 ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/grad5-3-2.png") 2012 2016 subblock(lena256bw, GREYLINES22, 2013 ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/lena 4-3-2.png")2017 ERROR_SUBFS22, DIFF_WEIGHTED22, True).save("out/lena5-3-2.png") 2014 2018 2015 2019 ############################################################################## 2016 if chapter( 5):2017 print "Chapter 5. Colour dithering"2018 2019 # Pattern 5.1.1: 8-colour palette2020 if chapter( 5):2020 if chapter(6): 2021 print "Chapter 6. Colour dithering" 2022 2023 # Pattern 6.1.1: 8-colour palette 2024 if chapter(6): 2021 2025 dest = Image((512, 64)) 2022 2026 for x in range(512): … … 2027 2031 for y in range(64): 2028 2032 dest.setRgb(x, y, r, g, b) 2029 dest.save("out/pat 5-1-1.png")2030 2031 # Figure 5.1.1: 128x128 Lena2032 # Figure 5.1.2a: red channel2033 # Figure 5.1.2b: green channel2034 # Figure 5.1.2c: blue channel2035 # Figure 5.1.3a: red channel promoted to greyscale2036 # Figure 5.1.3b: green channel promoted to greyscale2037 # Figure 5.1.3c: blue channel promoted to greyscale2038 # Figure 5.1.4a: dithered red channel2039 # Figure 5.1.4b: dithered green channel2040 # Figure 5.1.4c: dithered blue channel2041 # Figure 5.1.5: combined dithered channels2042 if chapter( 5):2033 dest.save("out/pat6-1-1.png") 2034 2035 # Figure 6.1.1: 128x128 Lena 2036 # Figure 6.1.2a: red channel 2037 # Figure 6.1.2b: green channel 2038 # Figure 6.1.2c: blue channel 2039 # Figure 6.1.3a: red channel promoted to greyscale 2040 # Figure 6.1.3b: green channel promoted to greyscale 2041 # Figure 6.1.3c: blue channel promoted to greyscale 2042 # Figure 6.1.4a: dithered red channel 2043 # Figure 6.1.4b: dithered green channel 2044 # Figure 6.1.4c: dithered blue channel 2045 # Figure 6.1.5: combined dithered channels 2046 if chapter(6): 2043 2047 tmp = gammascale(lena256, 2) 2044 tmp.save("out/fig 5-1-1.png")2048 tmp.save("out/fig6-1-1.png") 2045 2049 (w, h) = tmp.size() 2046 2050 dst = [Image((w, h), True) for i in range(3)] … … 2050 2054 dst[1].setRgb(x, y, 0, rgb[1], 0) 2051 2055 dst[2].setRgb(x, y, 0, 0, rgb[2]) 2052 dst[0].save("out/fig 5-1-2a.png")2053 dst[1].save("out/fig 5-1-2b.png")2054 dst[2].save("out/fig 5-1-2c.png")2056 dst[0].save("out/fig6-1-2a.png") 2057 dst[1].save("out/fig6-1-2b.png") 2058 dst[2].save("out/fig6-1-2c.png") 2055 2059 for x, y in rangexy(w, h): 2056 2060 for i in range(3): 2057 2061 rgb = dst[i].getRgb(x, y) 2058 2062 dst[i].setRgb(x, y, rgb[i], rgb[i], rgb[i]) 2059 dst[0].save("out/fig 5-1-3a.png")2060 dst[1].save("out/fig 5-1-3b.png")2061 dst[2].save("out/fig 5-1-3c.png")2063 dst[0].save("out/fig6-1-3a.png") 2064 dst[1].save("out/fig6-1-3b.png") 2065 dst[2].save("out/fig6-1-3c.png") 2062 2066 for i in range(3): 2063 dst[i] = test 42x(dst[i], ERROR_FSTEIN, True, Gamma.Cto2)2064 dst[0].save("out/fig 5-1-4a.png")2065 dst[1].save("out/fig 5-1-4b.png")2066 dst[2].save("out/fig 5-1-4c.png")2067 dst[i] = test52x(dst[i], ERROR_FSTEIN, True, Gamma.Cto2) 2068 dst[0].save("out/fig6-1-4a.png") 2069 dst[1].save("out/fig6-1-4b.png") 2070 dst[2].save("out/fig6-1-4c.png") 2067 2071 for x, y in rangexy(w, h): 2068 2072 for i in range(3): … … 2070 2074 rgb[i] = (dst[i].getRgb(x, y))[i] 2071 2075 dst[i].setRgb(x, y, *rgb) 2072 dst[0].save("out/fig 5-1-5a.png")2073 dst[1].save("out/fig 5-1-5b.png")2074 dst[2].save("out/fig 5-1-5c.png")2076 dst[0].save("out/fig6-1-5a.png") 2077 dst[1].save("out/fig6-1-5b.png") 2078 dst[2].save("out/fig6-1-5c.png") 2075 2079 for x, y in rangexy(w, h): 2076 2080 rgb = [0., 0., 0.] … … 2078 2082 rgb[i] = (dst[i].getRgb(x, y))[i] 2079 2083 tmp.setRgb(x, y, *rgb) 2080 tmp.save("out/fig 5-1-6.png")2081 2082 # Output 5.1.1: 8-colour Floyd-Steinberg RGB dithering2083 # Output 5.1.2: 8-colour gamma-corrected Floyd-Steinberg RGB dithering2084 def test 51x(src, mat, func):2084 tmp.save("out/fig6-1-6.png") 2085 2086 # Output 6.1.1: 8-colour Floyd-Steinberg RGB dithering 2087 # Output 6.1.2: 8-colour gamma-corrected Floyd-Steinberg RGB dithering 2088 def test61x(src, mat, func): 2085 2089 (w, h) = src.size() 2086 2090 dest = Image((w, h)) … … 2097 2101 return dest 2098 2102 2099 def test 51y(src, mat, serpentine, threshold):2103 def test61y(src, mat, serpentine, threshold): 2100 2104 return test3xx(src, mat, serpentine) 2101 2105 2102 if chapter( 5):2103 test 51x(grad256, ERROR_FSTEIN, test51y).save("out/grad5-1-1.png")2104 test 51x(lena256, ERROR_FSTEIN, test51y).save("out/lena5-1-1.png")2105 test 51x(grad256, ERROR_FSTEIN, test42x).save("out/grad5-1-2.png")2106 test 51x(lena256, ERROR_FSTEIN, test42x).save("out/lena5-1-2.png")2107 2108 # Pattern 5.2.1: different colours give the same result2109 if chapter( 5):2106 if chapter(6): 2107 test61x(grad256, ERROR_FSTEIN, test61y).save("out/grad6-1-1.png") 2108 test61x(lena256, ERROR_FSTEIN, test61y).save("out/lena6-1-1.png") 2109 test61x(grad256, ERROR_FSTEIN, test52x).save("out/grad6-1-2.png") 2110 test61x(lena256, ERROR_FSTEIN, test52x).save("out/lena6-1-2.png") 2111 2112 # Pattern 6.2.1: different colours give the same result 2113 if chapter(6): 2110 2114 dest = Image((320, 160)) 2111 2115 for x in range(80): … … 2153 2157 b = DITHER_BAYER44[y % 4][(x + 2) % 4] > 13 2154 2158 dest.setRgb(x, y, b, g, r) 2155 dest.save("out/pat 5-2-1.png")2156 2157 # Pattern 5.2.2: 16-colour palette2158 if chapter( 5):2159 dest.save("out/pat6-2-1.png") 2160 2161 # Pattern 6.2.2: 16-colour palette 2162 if chapter(6): 2159 2163 dest = Image((512, 128)) 2160 2164 for x, y in rangexy(64, 64): … … 2175 2179 for y in range(64): 2176 2180 dest.setRgb(x, y, r, g, b) 2177 dest.save("out/pat 5-2-2.png")2178 2179 # Output 5.2.1: gamma-corrected Floyd-Steinberg with ANSI palette (sigma-abs)2180 # Output 5.2.2: gamma-corrected Floyd-Steinberg with ANSI palette (euclidian)2181 def test 52x(src, mat, cpal, distance, serpentine):2181 dest.save("out/pat6-2-2.png") 2182 2183 # Output 6.2.1: gamma-corrected Floyd-Steinberg with ANSI palette (sigma-abs) 2184 # Output 6.2.2: gamma-corrected Floyd-Steinberg with ANSI palette (euclidian) 2185 def test62x(src, mat, cpal, distance, serpentine): 2182 2186 (w, h) = src.size() 2183 2187 ipal = [[Gamma.CtoI(c[i]) for i in range(3)] for c in cpal] … … 2264 2268 return r*r + g*g + b*b 2265 2269 2266 if chapter( 5):2267 test 52x(grad256, ERROR_FSTEIN,2268 ANSI_PALETTE, distmax, True).save("out/grad 5-2-1.png")2269 test 52x(lena256, ERROR_FSTEIN,2270 ANSI_PALETTE, distmax, True).save("out/lena 5-2-1.png")2271 test 52x(grad256, ERROR_FSTEIN,2272 ANSI_PALETTE, disteuclidian, True).save("out/grad 5-2-2.png")2273 test 52x(lena256, ERROR_FSTEIN,2274 ANSI_PALETTE, disteuclidian, True).save("out/lena 5-2-2.png")2270 if chapter(6): 2271 test62x(grad256, ERROR_FSTEIN, 2272 ANSI_PALETTE, distmax, True).save("out/grad6-2-1.png") 2273 test62x(lena256, ERROR_FSTEIN, 2274 ANSI_PALETTE, distmax, True).save("out/lena6-2-1.png") 2275 test62x(grad256, ERROR_FSTEIN, 2276 ANSI_PALETTE, disteuclidian, True).save("out/grad6-2-2.png") 2277 test62x(lena256, ERROR_FSTEIN, 2278 ANSI_PALETTE, disteuclidian, True).save("out/lena6-2-2.png") 2275 2279 2276 2280 def rgb2hsv(r, g, b): … … 2306 2310 return 9*d1*d1 + d2*d2 + d3*d3 2307 2311 2308 if chapter( 5):2309 test 52x(grad256, ERROR_FSTEIN,2310 ANSI_PALETTE, disthsv, True).save("out/grad 5-2-3.png")2311 test 52x(lena256, ERROR_FSTEIN,2312 ANSI_PALETTE, disthsv, True).save("out/lena 5-2-3.png")2313 test 52x(grad256, ERROR_FSTEIN,2314 ANSI_PALETTE, disthsv3, True).save("out/grad 5-2-4.png")2315 test 52x(lena256, ERROR_FSTEIN,2316 ANSI_PALETTE, disthsv3, True).save("out/lena 5-2-4.png")2317 2318 # Output 5.4.1: colour sub-block error diffusion2312 if chapter(6): 2313 test62x(grad256, ERROR_FSTEIN, 2314 ANSI_PALETTE, disthsv, True).save("out/grad6-2-3.png") 2315 test62x(lena256, ERROR_FSTEIN, 2316 ANSI_PALETTE, disthsv, True).save("out/lena6-2-3.png") 2317 test62x(grad256, ERROR_FSTEIN, 2318 ANSI_PALETTE, disthsv3, True).save("out/grad6-2-4.png") 2319 test62x(lena256, ERROR_FSTEIN, 2320 ANSI_PALETTE, disthsv3, True).save("out/lena6-2-4.png") 2321 2322 # Output 6.4.1: colour sub-block error diffusion 2319 2323 def colorsubblock(src, tiles, propagate, diff): 2320 2324 (w, h) = src.size() … … 2384 2388 [RGB_PALETTE[c], RGB_PALETTE[d]]]) 2385 2389 2386 if chapter( 5):2390 if chapter(6): 2387 2391 colorsubblock(grad256, RGBLINES22, 2388 ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/grad 5-4-1.png")2392 ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/grad6-4-1.png") 2389 2393 colorsubblock(lena256, RGBLINES22, 2390 ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/lena 5-4-1.png")2394 ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/lena6-4-1.png") 2391 2395 2392 2396 ANSILINES22 = [] … … 2398 2402 [ANSI_PALETTE[c], ANSI_PALETTE[d]]]) 2399 2403 2400 if chapter( 5):2404 if chapter(6): 2401 2405 colorsubblock(grad256, ANSILINES22, 2402 ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/grad 5-4-2.png")2406 ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/grad6-4-2.png") 2403 2407 colorsubblock(lena256, ANSILINES22, 2404 ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/lena 5-4-2.png")2408 ERROR_SUBFS22, DIFF_WEIGHTED22).save("out/lena6-4-2.png") 2405 2409 2406 2410 ############################################################################## 2407 if chapter( 6):2408 print "Chapter 6. Photographic mosaics"2409 2410 # Output 6.0.1: create a mosaic from Lena2411 if chapter(7): 2412 print "Chapter 7. Photographic mosaics" 2413 2414 # Output 7.0.1: create a mosaic from Lena 2411 2415 def mosaic_split(src, tnw, tnh): 2412 2416 random.seed(0) … … 2435 2439 return coeffs 2436 2440 2437 def test 601(tnlist, cols):2441 def test701(tnlist, cols): 2438 2442 (tnw, tnh) = tnlist[0].size() 2439 2443 dw = cols … … 2446 2450 return dest 2447 2451 2448 if chapter( 6):2452 if chapter(7): 2449 2453 tnlist = mosaic_split(lena256, 32, 32) 2450 test 601(tnlist, 10).save("out/lena6-0-1.png")2451 2452 # Output 6.1.1: extract 1 colour feature from mosaic tiles2453 # Output 6.1.2: crop Lena2454 # Output 6.1.3: generate a mosaic from the 1-feature database2455 # Output 6.1.4: extract 4 colour features from mosaic tiles2456 # Output 6.1.5: generate a mosaic from the 4-feature database2457 def test 61x(coeffs, cols, tnw, tnh):2454 test701(tnlist, 10).save("out/lena7-0-1.png") 2455 2456 # Output 7.1.1: extract 1 colour feature from mosaic tiles 2457 # Output 7.1.2: crop Lena 2458 # Output 7.1.3: generate a mosaic from the 1-feature database 2459 # Output 7.1.4: extract 4 colour features from mosaic tiles 2460 # Output 7.1.5: generate a mosaic from the 4-feature database 2461 def test71x(coeffs, cols, tnw, tnh): 2458 2462 dx = len(coeffs[0][0]) 2459 2463 dy = len(coeffs[0]) … … 2469 2473 return dest 2470 2474 2471 def test 61y(src, sqw, sqh, tnlist, coeffs):2475 def test71y(src, sqw, sqh, tnlist, coeffs): 2472 2476 (w, h) = src.size() 2473 2477 (tnw, tnh) = tnlist[0].size() … … 2503 2507 return dest 2504 2508 2505 if chapter( 6):2509 if chapter(7): 2506 2510 coeffs1x1 = mosaic_analyse(tnlist, 1, 1) 2507 test 61x(coeffs1x1, 10, 8, 8).save("out/lena6-1-1.png")2508 out 612 = lena256.getRegion(100, 90, 80, 80)2509 out 612.save("out/lena6-1-2.png")2510 test 61y(out612, 6, 6, tnlist, coeffs1x1).save("out/lena6-1-3.png")2511 test71x(coeffs1x1, 10, 8, 8).save("out/lena7-1-1.png") 2512 out712 = lena256.getRegion(100, 90, 80, 80) 2513 out712.save("out/lena7-1-2.png") 2514 test71y(out712, 6, 6, tnlist, coeffs1x1).save("out/lena7-1-3.png") 2511 2515 2512 2516 coeffs2x2 = mosaic_analyse(tnlist, 2, 2) 2513 test 61x(coeffs2x2, 10, 16, 16).save("out/lena6-1-4.png")2514 test 61y(out612, 6, 6, tnlist, coeffs2x2).save("out/lena6-1-5.png")2517 test71x(coeffs2x2, 10, 16, 16).save("out/lena7-1-4.png") 2518 test71y(out712, 6, 6, tnlist, coeffs2x2).save("out/lena7-1-5.png") 2515 2519 2516 2520 ##############################################################################
Note: See TracChangeset
for help on using the changeset viewer.