如何使用JavaScript生成lowpoly风格图像？

在指定区域内，生成类似三角形网格 并着色的算法，怎么实现？
试了好久，水平有限，希望大神们不吝赐教

回复内容：

===== 更新 =====
算法已发表论文：
Zhang, Wenli; Xiao, Shuangjiu; Shi, Xin, "Low-poly style image and video processing," in Systems, Signals and Image Processing (IWSSIP), 2015 International Conference on , vol., no., pp.97-100, 10-12 Sept. 2015
URL: IEEE Xplore Abstract
==============

被邀请挺久了，一直忍着没答！
在做完 百度 IFEOvilia/Polyvia · GitHub 项目之后，在 小结博客 里也没细说算法，因为我当时正准备在发论文。现在论文已经被接收了（等正式发表了我来补引用和 PDF），所以来仔细说说我的算法，也正好让大家提提改进的意见，因为我觉得还有很大改进空间。

本文主要就算法层面进行讨论，不涉及具体的 WebGL 实现细节和着色器编程知识，希望有点编程经验的同学都能无障碍阅读。

不允许转载，保留所有权利。不允许未经许可以任何形式使用本文的图。

题目的描述比较模糊，首先明确一下解决的问题。其他答案中给出的 wagerfield/flat-surface-shader · GitHub 和 qrohlf/trianglify · GitHub 这些项目，都是针对生成带有渐变效果的 low-poly 图，更像是纹理生成。而我研究的是，如何通过一张输入图像，输出其对应的 low-poly 图，这一问题显然比纹理生成难得多。
比如对于以下输入图（摄影作者： @正一 是论文三作）
输出的效果是：
当然，仔细看可以看到很多瑕疵，比如左边靠下蓝绿色中间的边缘没有很好地被保留下来等等。但是整体的效果应该还算比较美观的，对于细节比较丰富的地方，取的三角形比较多，反之则反。

在我做这个项目之前已经发现了一些类似的实现，其中我觉得最有效的是：timbennett/delaunay · GitHub ，我觉得从结果上来说已经比较接近完美了，那还有什么做的必要呢？我当时也是这么问作为 IFE 导师的 @沈毅 的，我不记得他当时的回答了……反正就记得不是很有说服力哈哈。然后过了几天我想到，可以做一个在浏览器内获取本地摄像头图像处理后的视频版，于是我就开始做这个项目了。
为了回答这个问题，我特地跟 timbennett 的效果图对比了一下（想要试玩的话在 GitHub 上下载他的项目放在本地服务器下，他给的链接挂了），用的还是上面的输入图，同样取 1000 个点组成三角形，他的输出是这样的：
看起来还是我的算法略胜一筹捏哈哈~（我的评价标准是边缘信息更好地被保留下来，且具有更好的艺术性。可能还是有一定主观因素在内，但是我想应该还是我的效果更好一点吧？）

聪明的同学已经发现了，效果的好坏主要取决于选了什么位置的点组成三角形。如果你是完全随机选的，那么效果就可能是这样的：

看我算法的效果图应该可以猜到，取图像边缘上的点更容易获得更好的效果，这是因为如果边上的两个点被选中了，那么丢给后面的 Delaunay 三角化步骤生成的三角形的一条边就会在边缘上，那就没有上图随机取点造成的这种感觉了。

好，既然我们要取边缘上的点，那么很容易想到可以先用 Sobel 之类的边缘检测算法获取边缘，得到的结果是这样的：（使用 WebGL 着色器加速运算：Polyvia/three.js.EdgeShader.js at gh-pages · Ovilia/Polyvia · GitHub）

那么怎么取边缘上的点呢？显然不能每个点都取，否则就太多了，low-poly 本来就是要取更少的点达到更抽象的效果。这里我觉得是我可以改进的地方，因为我的方法比较简单粗暴，就是在边缘上随机取点，这样的方法实现起来简单，效果也不差。但是如果能够更有规律地取点，还是可以有效改善最终效果的，这点稍后再说。

能不能只取边缘上的点作为组成三角形的点呢？
通常这不是一个好主意。因为它使得很多三角形退化成非常尖锐的锐角三角形。

为什么这里说退化呢？这是因为后面一步的 Delaunay 三角化的作用就是将输入的一组点尽可能地避免变成锐角三角形，从而达到更好的视觉效果。
所以，除了边缘上的点有一定概率会被选作组成三角形之外，我们另外以一个更小的概率在全图中随机取点。这样就非常有效地避免了非常锐的锐角三角形出现。下图为选中的点的位置。

然后，我们使用 Delaunay 三角化将选中的点组成一个个三角形。Delaunay 三角化是图形学中一种比较常用的算法，具体细节我不展开了，总之它的作用上文已经提到了，就是使得生成的三角形们尽量不是非常锐的锐角三角形。下图为 Delaunay 算法得到的三角形们。使用的 Delaunay 算法是第三方库：ironwallaby/delaunay · GitHub。

最后，就到了给三角形上色的阶段了。当然像 k-means 这种可以获取三角形颜色类别的方法更高大上，但是为了满足实时性需求，我们还是使用简单粗暴的办法就好，而且效果也非常不错。具体的做法就是使用每个三角形重心处的颜色作为三角形的颜色。重心位置的计算是非常简单的，只要把三个顶点的位置求平均数就可以了。然后就能得到上面的结果图了。

这么说下来的逻辑应该挺清楚的吧？不清楚的话再来看这张整体流程图。

以上，就是图像处理的全部流程了，知道原理后其实也不难对吧？我搜来搜去没找到发表的 low-poly 论文，想着可以做鼻祖了！然而评委评论意见里告诉了我这篇 2015 年 4 月份发表的论文：

Gai, Meng, and G. Wang. "Artistic Low Poly rendering for images." The Visual Computer (2015): 1-10

然后我对比了一下，发现这篇论文的效果比我厉害多了……

(a) 是输入图像；(b) 是 iTunes 的 App Store 中的“Art camera TRIGRAFF” 这个软件生成的结果；(c) 是这篇论文的效果；(d) 是我的算法的效果。（前三张图来自这篇论文）
相形见拙啊！！！

主要还是在选择组成三角形的点的算法上，我的随机算法虽然不错，但是跟人家有目的性地在边缘上选取点的方法还是弱了不少的。（这篇论文我还没细看，回头再仔细研究研究）

但是！！！你知道这篇论文生成 500x800 左右的图要多少时间么？4.7 秒！我的呢？0.3 秒！所以呢，也并没有输的那么惨烈对吧~

以上就是图像方面的算法了。下面讲视频相关部分。

视频的每一帧当作图像处理就好了吗？那我也太水了……

主要的问题在于，由于我的点是随机取的，所以每帧取到的点不一样，就表现为屏幕一直在闪烁，因为三角形的位置和颜色变化非常大。为了解决这一问题，我们就希望上一帧被选中的点，如果在这一帧中仍然在边缘，则它被选中的概率将大得多。

这似乎能比较有效地消抖，但是又带来一个新的问题，就是随着时间的进行，越来越多的边缘点被保留下来，那么留给其他地方的点就越来越少了。具体表现为，如果背景有个沙发抱枕，我人在前面晃悠，结果沙发抱枕边缘上的点越取越多，我的脸就变得一片模糊了，因为没多少点留给我的脸了。（欧，我的脸~~你能想象我把这样的图放到论文里去了么……）

解决方法是，设一个 5% 左右的淘汰率，对于上一帧被选中，并且这一帧仍然在边缘上的点，仍然有 5% 的概率在这一帧不被选中，这样就保证了点的流通性，同时也能排除一些抖动的干扰。

说是这么说啦，但实际效果是，抖动的消除还是不是很理想。有兴趣的话你可以自己玩玩看：Polyvia

最后，放一些由于篇幅不够没能放到论文中的效果图。（顺便夸一下 @正一 找的原图很棒~ 原图都是 Public Domain 的）

你自己也来试试吧：Polyvia

如果对于算法方面有些建议的话，欢迎给我反馈：Issues · Ovilia/Polyvia · GitHub 或邮件我 me at zhangwenli.com。

写知乎回答比写论文顺畅多了，论文大概就是故意写得让人看不懂的吧……
等我论文正式发表了，如果心情好的话，可以考虑放视频（里面有我真人解说！深 js 上已经剧透过了啦……不过！还有我的配音！！保证不让你们失望！）。心情好的途径包括第一次回答一个点赞数上万的问题啦，GitHub star 过两百啦 Ovilia/Polyvia · GitHub ~\(^o^)/~

最后，再次感谢 @沈毅 在这个项目中对我的悉心指导，以及 @正一 的各种帮忙~ @羡辙 回答中提到的论文作者羞射前来报到。

算法都在论文中，详细可阅读： Gai M, Wang G. Artistic Low Poly rendering for images[J]. The Visual Computer, 2015: 1-10

主要思路点一下吧：用边缘提取产生约束边进行带约束的Delaunay三角化；用Voronoi迭代优化顶点位置。另外显著区域提取是凑数的可有可无。主要时间开销也是在显著区域提取和CVD迭代两步。单纯做边缘提取Delaunay剖分也是很快的。

结果不是太满意，主要难点在于图像中高层语义信息的保持。而边缘提取等局部算子只能提供低层次信息。

贴几张论文里的大图吧：
低多边形（Low Poly）

继拟物化、扁平化（Flat Design）、长阴影（Long Shadow）之后，低多边形（Low Poly）又火速掀起了最新设计风潮。这种设计风格在早期计算机建模和动效中就被广泛采用，在快要被遗忘之时，突然又流行了一把。Low Poly是一种复古未来派风格设计（它本身也可以称之为新唯美设计The New Aesthetic)，又回到过去，又回到未来，在摇摆不定中寻找美学的平衡。繁荣发展的数字艺术，经历了一代又一代对“逼真”风格的无限追求，可他们永远无法做到逼真，因为他们进行的是模拟，此时，有人厌倦了模拟，他们开始追求抽象化的表达。

Low poly is a polygon mesh in 3D computer graphics that has a relatively small number of polygons. Low poly meshes occur in real-time applications (e.g. games)...

低多边形，在 3D 计算机图形中是多边形网格，它有相当小数量的多边形。低多边形网格出现在实时应用程序中（比如游戏）。

Polygons can, in theory, have any number of sides but are commonly broken down into triangles for display.

在理论上，多边形可以有认识数量的边，但是通常都会分解成三角形来显示。

将平面上的点集进行「三角剖分」，可以使用「德勞內三角剖分（Delaunay Triangulation）」。



德劳内三角剖分（Delaunay Triangulation）

在数学和计算几何领域, 平面上的点集 P 的 Delaunay 三角化是一种三角剖分 DT(P)，使得在 P 中没有点严格处于 DT(P) 中任意一个三角形外接圆的内部。Delaunay 三角化最大化了此三角剖分中三角形的最小角，换句话，此算法尽量避免出现“极瘦”的三角形。 此算法命名来源于鲍里斯 · 德劳内，以纪念他自1934年在此领域的工作。

有许多算法先实现 Delaunay Triangulation，这里说下最简单的（也是最慢的）一种方式，Delaunay triangulation - Flip Algorithms。

If a triangle is non-Delaunay, we can flip one of its edges. This leads to a straightforward algorithm: construct any triangulation of the points, and then flip edges until no triangle is non-Delaunay.

如果一个三角形是一个 non-Delaunay 的，我们可以翻转它的一条边（什么叫翻转在这里有详细解释）。这就引出了一个明确的算法：构造点集的任意三角剖分，并且翻转它的边，直到没有三角形是 non-Delaunay 的。





颜色

再说到着色，一个直观的思路是给左上角一个颜色，右下角一个颜色，然后通过三角形（中点）的坐标获取这两种颜色的差值，然后使用这个颜色给每个三角形上色。



资源

Delaunay Triangulation
https://github.com/ironwallaby/delaunay

trianglify.js
qrohlf/trianglify · GitHub



参考文章

http://baike.baidu.com/view/14780798.htm
http://en.wikipedia.org/wiki/Low_poly
http://en.wikipedia.org/wiki/Delaunay_triangulation

1. 输入图片的特征分析，提取边缘之类
2. Poisson 采样生成「均匀」的顶点
3. Delaunay triangulation

很久很久前用 OpenCV 做的视频 Delaunay 渲染，画质有点渣
1. goodFeaturesToTrack 找到合适的特征点
1.1 optical flow 寻找视频帧之间连续的特征点（可选项）
2. delaunay 生成三角形
3. 画线
Delaunay 渲染—在线播放—优酷网，视频高清在线观看 http://v.youku.com/v_show/id_XMTE4MDMyMTM2.html?from=s1.8-1-1.2 wagerfield/flat-surface-shader · GitHub qrohlf/trianglify · GitHub @羡辙@盖孟 的实现都非常的棒, 当时看到他们的实现, 我又在给一朋友准备生日礼物, 因此也打算实现一个, 只不过除了完成算法以外更进一步把作品给做了出来, 这里就来简单分享下吧, 献丑了~

之前其实被建议用已有的代码来实现, 但是发现已有的实现的表现力并不是很好, 特别是对于我手上的几张例图, 所以我想的是

不是一个娴熟的C++程序员, 因此采用的是OpenCV Python 的Binding来实现, 核心仍然是 @羡辙 所说的边提取. 我采用了一个Sobel Edge Detection不过加入了调参的部分来可以自己设置以确保最佳分配. 不过我的猜想是通过对输入图片的色域的分布进行分析其实有办法推导出适合的参数, 鉴于我对CV确实不熟悉所以没有更好的实现, 将考虑作为future work.

渲染部分opencv的binding默认用到matplotlib, 不过在我使用中polygon的顶点的alignment会有问题, 此外matplotlib对于此类图片的分辨率支持相当的糟糕, 所以最后我采用了直接渲染svg的方式, 效果很好同时矢量图scalable.

我总结一下, 其实 @羡辙 的实现方式已经可以做到应用了, 不过我发现 @盖孟 的实现的优势在于使用了Voronoi Iteration, 虽然说我到现在没有access到盖孟的论文 (unfortunately I don't have an institution affiliation right now), 不过简单的研究告诉我Voronoi iteration的作用在于对选取点优化, 做更均匀的分布.

其实在做的过程中也反复的思考过怎么可以提升渲染效果, 我能想到的一个很重要的点在于做好点的分布, 其实我在考虑是否可以根据颜色的渐变来用voronoi优化点, 或者说既然我们有艺术家的voronoi成品是否可以learn the techniques from those images via ML and use that for rendering ours. I guess I am just bullshitting but anyway.
以及一张右图的wireframe

就不开源了先, 我打算port到javascript上面, python numpy的速度来做图形处理是在还是太糟糕了, 我打算去看了所谓的OpenGL小红书了用WebGL重写. 到时候做一个前端的能够交互的版本再MIT吧.

当然算法实现虽然说是这次这个project里面最花时间的部分, 但是我觉得最有意义的还是在于把这个做成一个艺术品, 不得不说low-poly image有一种抽象艺术的美感, 就像我原来学国画. (我就不写矫情的东西在这里装逼了)
最后做出来是这样的, 用了很高级的纸, surprisingly我的喷墨打印机的效果竟然出奇的好.

希望朋友会喜欢.

(2015.12.8 1.19AM @Class Chalet, 留学最后一晚, 喝了伏特加, 希望写的东西还能辨识. 明天礼物给她了我再来post这篇吧) 框架的话我用canvas实现过一次，你可以先弄出一个网格，然后每个格连接一条对角线，这就是一堆三角了，把每个交点的位置随机挪动一下，就生成了不规则的三角形网格。


然后着色的话没想出什么好办法，如果只是渐变的话可以距离某个格子哪个距离用哪个颜色。 嘛，看到前面高人的回答，小的厚颜无耻用[timbennett/delaunay](timbennett/delaunay · GitHub)的实现自己改了一个--------[我的工具](kinglisky/lowpoly · GitHub)，原本是想用web workers来提高运算速度的，但效果不太好，算法表示啃不动，求高人指教。嘿嘿给点星星呗