五分钟科普：什么是骰子作画的算法

以你之姓@ 2021-12-13 03:15 374阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640][]

作者 | 阮一峰

来源 | 阮一峰的博客

今天是周末，给大家分享一个有趣的项目---骰子作画。

程序员 Scott MacDonald 做了一个很有趣的项目----骰子作画。

他用黑底白点的骰子。

![640?wx\_fmt=png][640_wx_fmt_png]

模拟出一张人像照片。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

把图像放大，就可以看得更清楚。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

他一共用了2500多颗骰子。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

最后的成品就是这样。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

任何一张图片都可以用骰子模拟出来，算法非常简单：将图片分成若干个区域，每个区域经过计算以后，用1-6之间的一个整数表示，代表骰子的一个面。这种将连续的量转化成不连续的整数的算法，属于vector quantization（矢量量化）的一个应用。

具体来说，

第一步，将图片分割成16像素x16像素的小方块。

for (int i=0; i < (pic_width/16); ++i) {　　　　for (int j=0; j < (pic_height/16); ++j) {　　　　　　patch = cropped_img.get(i*16, j*16, 16, 16);　　　　}　　}int i=0; i < (pic_width/16); ++i) {
        
    
    　　　　for (int j=0; j < (pic_height/16); ++j) {
        
    
    　　　　　　patch = cropped_img.get(i*16, j*16, 16, 16);
    
    　　　　}
    
    　　}

第二步，每个小方块内共有256个像素，将每个像素点的灰度值，存入一个数组。

for (int k=0; k < patch.pixels.length; ++k) {　　　x[k] = rgb2gray(patch.pixels[k]);　　}　　int rgb2gray(int argb) {　　　　int _alpha = (argb >> 24) & 0xFF;　　　　int _red = (argb >> 16) & 0xFF;　　　　int _green = (argb >> 8 ) & 0xFF;　　　　int _blue = (argb) & 0xFF;　　　　return int(0.3*_red + 0.59*_green + 0.11*_blue);　　}int k=0; k < patch.pixels.length; ++k) {
        
    
    　　　x[k] = rgb2gray(patch.pixels[k]);
    
    　　}
    
    　　int rgb2gray(int argb) {
        
    
    　　　　int _alpha = (argb >> 24) & 0xFF;
    
    　　　　int _red = (argb >> 16) & 0xFF;
    
    　　　　int _green = (argb >> 8 ) & 0xFF;
    
    　　　　int _blue = (argb) & 0xFF;
    
    　　　　return int(0.3*_red + 0.59*_green + 0.11*_blue);
    
    　　}

第三步，计算该数组的平均值，并用1-6之间的一个整数来表示。

int dice_num = six_step_gray(mean(x));　　int mean(int[] x) {　　　　float m = 0;　　　　for (int i=0; i < x.length; ++i) {　　　　　　m += x[i];　　　　}　　　　m = m/x.length;　　　　return int(m);　　}　　int six_step_gray(int x) {　　　　if (0 <= x && x <= 41) return 1;　　　　if (41 < x && x <= 83) return 2;　　　　if (83 < x && x <= 124) return 3;　　　　if (124 < x && x <= 165) return 4;　　　　if (165 < x && x <= 206) return 5;　　　　if (206 < x && x <= 247) return 6;　　　　else return 6;　　}
    
    　　int mean(int[] x) {
        
    
    　　　　float m = 0;
    
    　　　　for (int i=0; i < x.length; ++i) {
        
    
    　　　　　　m += x[i];
    
    　　　　}
    
    　　　　m = m/x.length;
    
    　　　　return int(m);
    
    　　}
    
    　　int six_step_gray(int x) {
        
    
    　　　　if (0 <= x && x <= 41) return 1;
    
    　　　　if (41 < x && x <= 83) return 2;
    
    　　　　if (83 < x && x <= 124) return 3;
    
    　　　　if (124 < x && x <= 165) return 4;
    
    　　　　if (165 < x && x <= 206) return 5;
    
    　　　　if (206 < x && x <= 247) return 6;
    
    　　　　else return 6;
    　　}

整数1，表示骰子朝上的一面有1个白点；整数2，表示有2个白点；以此类推。白点越少，表示这个区域越接近全黑；白点越多，表示越接近全白。根据白点值，将骰子依次放入，就能模拟出全图。

这种算法早在1981年就有人提出，当时用的是1~9个白点的多米诺骨牌。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

如果区域划分得越小，模拟图的生成效果就越好。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 9]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 10]

此外，不用编程，使用Photoshop也可以得到类似效果。

![640?wx\_fmt=png][640_wx_fmt_png 1]

## END ##

## ![640?wx\_fmt=png][640_wx_fmt_png 2] ##

**原 创 热 文 推 荐**

☞[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[☞][Link 2][一道腾讯面试题：厉害了我的杯][Link 3]

[☞][Link 4][十大经典排序算法动画与解析，看我就够了][Link 5]

[☞][Link 4][这或许是东半球分析十大排序算法最好的一篇文章][Link 6]

[☞][Link 4][面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

![640?wx\_fmt=png][640_wx_fmt_png 3] 你点的每个“在看”，我都认真当成了喜欢

[640]: /images/20211210/1a880b13b09e48e6b6b6890d07bf37d0.png
[640_wx_fmt_png]: /images/20211210/5949ef539ca94ab983aab1412efdfaf0.png
[640_wx_fmt_jpeg]: /images/20211210/ccf9a701478349968a3d002a6a6e0094.png
[640_wx_fmt_jpeg 1]: /images/20211210/eb6ea1a10c904a6c9e43e4c9d429e2ac.png
[640_wx_fmt_jpeg 2]: /images/20211210/9b79d4fbaf95435c9c499438a22526f6.png
[640_wx_fmt_jpeg 3]: /images/20211210/cafa80879dcc4d5f8131574cf1be3914.png
[640_wx_fmt_jpeg 4]: /images/20211210/60ebcee418f54f018d9d37a533d2dadb.png
[640_wx_fmt_jpeg 5]: /images/20211210/13bb39d9bfee44ce9c512690884fb9fd.png
[640_wx_fmt_jpeg 6]: /images/20211210/b7563dcf587d4946bfc77337cd1a6fd4.png
[640_wx_fmt_jpeg 7]: /images/20211210/c196c23c761b4856bc2448a0231b116b.png
[640_wx_fmt_jpeg 8]: /images/20211210/e01284b5f54043739573ac1e11ccde11.png
[640_wx_fmt_jpeg 9]: /images/20211210/db368b6b51a64310ad44add721488ddf.png
[640_wx_fmt_jpeg 10]: /images/20211210/3bd3437fb4304fed9c52e7f18f886e31.png
[640_wx_fmt_png 1]: /images/20211210/e998f21e20ec42e98356e929262c2643.png
[640_wx_fmt_png 2]: /images/20211210/d2b84471e19044768dbeaa17afbbc86b.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzA5MzY4NTQwMA==&mid=2651011536&idx=3&sn=fd5ff61a84fe2180a7c21d15acf71659&chksm=8bad8a27bcda03319570ae23d05392d287390a51ca94014422dd199450b25f43467aaaedb59e&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzA5MjcxNjc2Ng==&mid=2650560116&idx=1&sn=f9e86fa3e7b15624177b29ef1a785be4&chksm=88601dc5bf1794d30fd595d413491da189584b44fd2b2e5e40c665e58760e162616585811647&scene=21#wechat_redirect
[Link 5]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 6]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[640_wx_fmt_png 3]: /images/20211210/92a4d72d20024a298eef61d9d716795c.png