骰子作画的算法
jopen 13年前
程序员 Scott MacDonald 做了一个很有趣的项目---- <a href="/misc/goto?guid=4958201365583890872" target="_blank">骰子作画</a>。 <p>他用黑底白点的骰子。</p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/4bfd630eb8345ce7f05a662757dd6546.jpg" width="300" height="219" /></p> <p>模拟出一张人像照片。</p> <p style="text-align:center;"><img style="width:565px;height:301px;" alt="" src="https://simg.open-open.com/show/a7b7198abb1bd0bd1613bd23d44d2208.jpg" /></p> <p>把图像放大，就可以看得更清楚。</p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/27950676d161a2960aee8fd3fe1ac165.jpg" width="500" height="250" /></p> <p>他一共用了2500多颗骰子。</p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/4716ed0e766108ce39c0ae3bd6f5051e.jpg" width="550" height="413" /></p> <p>最后的成品就是这样。</p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/123efb8673779656c27c2a84acc4a265.jpg" width="450" height="448" /></p> <p><strong>任何一张图片都可以用骰子模拟出来，算法非常简单：将图片分成若干个区域，每个区域经过计算以后，用1-6之间的一个整数表示，代表骰子的一个面。</strong>这种将连续的量转化成不连续的整数的算法，属于 <a href="/misc/goto?guid=4958201366354055953" target="_blank">vector quantization</a>（矢量量化）的一个应用。</p> <p>具体来说，</p> <p>第一步，将图片分割成16像素 x16 像素的小方块。</p> <blockquote> <p>for (int i=0; i < (pic_width/16); ++i) {</p> <p>for (int j=0; j < (pic_height/16); ++j) {</p> <p>patch = cropped_img.get (i*16, j*16, 16, 16);</p> <p>}</p> <p>}</p> </blockquote> <p>第二步，每个小方块内共有256个像素，将每个像素点的灰度值，存入一个数组。</p> <blockquote> <p>for (int k=0; k < patch.pixels.length; ++k) {</p> <p>x[k] = rgb2gray (patch.pixels[k]);</p> <p>}</p> <p>int rgb2gray (int argb) {</p> <p>int _alpha = (argb >> 24) & 0xFF;</p> <p>int _red = (argb >> 16) & 0xFF;</p> <p>int _green = (argb >> 8 ) & 0xFF;</p> <p>int _blue = (argb) & 0xFF;</p> <p>return int (0.3*_red + 0.59*_green + 0.11*_blue);</p> <p>}</p> </blockquote> <p>第三步，计算该数组的平均值，并用1-6之间的一个整数来表示。</p> <blockquote> <p>int dice_num = six_step_gray (mean (x));</p> <p>int mean (int[] x) {</p> <p>float m = 0;</p> <p>for (int i=0; i < x.length; ++i) {</p> <p>m += x[i];</p> <p>}</p> <p>m = m/x.length;</p> <p>return int (m);</p> <p>}</p> <p>int six_step_gray (int x) {</p> <p>if (0 <= x && x <= 41) return 1;</p> <p>if (41 < x && x <= 83) return 2;</p> <p>if (83 < x && x <= 124) return 3;</p> <p>if (124 < x && x <= 165) return 4;</p> <p>if (165 < x && x <= 206) return 5;</p> <p>if (x < 206 && x <= 247) return 6;</p> <p>else return 6;</p> <p>}</p> </blockquote> <p>整数1，表示骰子朝上的一面有1个白点；整数2，表示有2个白点；以此类推。白点越少，表示这个区域越接近全黑；白点越多，表示越接近全白。根据白点值，将骰子依次放入，就能模拟出全图。</p> <p>这种算法早在1981年就有人<a href="/misc/goto?guid=4958201367085001368" target="_blank">提出</a>，当时用的是1~9个白点的多米诺骨牌。</p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/a0d09626990f882ce5ac99a511669ab3.jpg" width="464" height="224" /></p> <p>如果区域划分得越小，模拟图的生成效果就越好。</p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/10019fa50fcedbd5ccc8e4c115640f2e.jpg" width="205" height="241" /></p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/f3cbb858c69e57ceb4735e56ece74d82.jpg" width="202" height="222" /></p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/d932d4ae4674ff1431cb5fc0355aafb3.jpg" width="202" height="222" /></p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/8bf9dbcda1b9065d0412f82b238fc676.jpg" width="202" height="222" /></p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/13ec33aba5b74f2fc0cdd9c6b5bda5ee.jpg" width="202" height="222" /></p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/4185d8c093b36c472caaa54d4b598357.jpg" width="204" height="225" /></p> <p>此外，不用编程，使用 <a href="/misc/goto?guid=4958201367821580299" target="_blank">Photoshop</a> 也可以得到类似效果。</p> <p style="text-align:center;"><img alt="" src="https://simg.open-open.com/show/2b0d640e3bd2f70bc091d8371a31fe58.jpg" width="500" height="300" /></p> 来自: <a id="link_source2" href="/misc/goto?guid=4958201368546002276" target="_blank">阮一峰的网络日志</a>