关于javascript:实现SLIC算法生成像素画

前言

像素风最早呈现在 8bit 的电子游戏中，受制于电脑内存大小以及显示色调繁多，只能应用大量像素来出现内容，却成就了不少经典的像素游戏。随着内存容量与屏幕分辨率的晋升，内存与显示媒介的限度不再是问题，而像素风也缓缓演变成一种独特的创作格调。

像素画的个别的绘制流程包含了勾线、填色等，而一一像素的绘制须要大量工夫。一些风行的艺术形式，比方线描与绘画畛域，都逐步呈现了自动化或半自动化生成的办法。本文将从零开始实现 SLIC[1] 算法，并实现一款生成像素画工具。

什么是 SLIC 算法

像素画的绘制之所以不简略，是因为间接的下采样并不能精确的捕捉要害像素，且容易导致失落边缘信息，生成的像素画往往不尽人意。手工的勾线、填色，都是为了选取适合的像素点。由此，咱们的问题变成了如何选取适合的像素点进行填色。

首先，引入一个概念——超像素。超像素是 2003 年 Xiaofeng Ren 提出和倒退起来的图像宰割技术，是指具备类似纹理、色彩、亮度等特色的相邻像素形成的有肯定视觉意义的不规则像素块[1]。

通过将图片宰割为超像素，能够失去类似的像素簇，类似的像素应用同一个色彩进行填充，失去的像素画会更正当。

超像素点宰割的办法包含了提取轮廓、聚类、梯度回升等多种。论文 [1] 提出的 SLIC 超像素点宰割算法（简略线性迭代聚类，simple linear iterative clustering）就是其中一种，它基于 K-means 聚类算法，依据像素的色彩和间隔特色进行聚类来实现良好的宰割后果，与若干种超像素点宰割算法相比，SLIC具备简略灵便、成果好、处理速度快等劣势。

如何实现 SLIC 算法

SLIC的根本流程如下：

1. 图像预处理。

   将图像从 RGB 色彩空间转换到 CIE-Lab 色彩空间，Lab色彩空间更合乎人类对色彩的视觉感知。这个空间里的间隔能反映人感觉到的色彩差异，相干计算更为精确。

   Lab色彩空间同样具备三个通道，别离是 l，a，b，其中l 代表亮度，数值范畴为 [0,100]，a 示意从绿色到红色的重量，数值范畴为 [-128,127]，b 示意蓝色到黄色的重量，数值范畴为[-128,127]。

   RGB和 LAB 之间没有间接的转换公式，须要将 RGB 转为 XYZ 色彩空间再转为LAB，代码见文末残缺代码。

2. 初始化聚类核心。

   依据参数确定超像素的数目，也就是须要划分为多少个区域。假如图片有 N 个像素点，预计宰割为 K 个超像素，每个超像素大小为 N/K，相邻核心间隔为S=Sqr(N/K)，失去K 个聚类坐标。

3. 优化初始聚类核心。在聚类核心的 3*3 邻域内抉择梯度最小的像素点作为新的聚类核心。

   把图像看成二维离散函数，梯度也就是这个函数的求导，当相邻像素值有变动就会存在梯度，而在边缘上的像素点的梯度最大。将聚类核心挪到梯度最小的中央能够防止其落到边缘轮廓上，影响聚类成果。

   离散梯度的梯度计算这里不做具体推导了，因为其中蕴含了若干平方与开方，计算量较大，个别会简化为用绝对值来近似平方和平方根的操作。简化后的计算坐标为 (i,j) 的像素点的梯度公式为：

   其中 （i+1,j） 与（i,j+1）为像素右侧点与像素下方点的坐标。l(a,b)为 （a，b） 坐标上像素的亮度通道值l。

4. 计算像素点与聚类核心的间隔。

   在聚类核心间隔 S 的区域内 2S*2S的邻域内计算像素点与每个聚类核心的间隔。

   这里的间隔应用的是欧式间隔，总间隔 D 由dc色彩间隔与 ds 空间间隔两局部组成。公式如下：

   如果间接将 l，a，b，x，y 拼接成一个矢量计算间隔，当超像素的大小变动时，x，y的值能够取到十分大，比方如果一张图 1000*1000，空间间隔能够达到1000*Sqr(2)，而色彩间隔最大仅10*Sqr(2)，导致最终计算失去的间隔值中，空间间隔ds 权重占比过大。

   所以须要进行归一化，除以最大值即超像素点的初始宽度S，将值映射到[0,1]。

   而色彩空间间隔也会给到一个固定的值 m 来调节色彩间隔与空间间隔的影响权重，m取值范畴为[1,40]。

   间隔公式即变成了

   当 m 越大，色彩空间除以 m 后的值越小，即空间间隔的权重越大，生成的像素会更为形态规定，当 m 越小，色彩间隔权重更大，超像素会在边缘更为紧凑，而形态大小较为不规则。

5. 像素点分类。

   标记每个像素点的类别为间隔其最小的聚类核心的类别。

6. 从新计算聚类核心。

   计算属于同一个聚类的所有像素点的均匀向量值，重新得到聚类核心。

7. 迭代 4～6 的过程。

   直到旧聚类核心与新聚类核心的间隔小于肯定阈值或者达到肯定迭代次数，一般来说，当迭代次数达到10，算法可能达到收敛。

8. 聚类优化。

   迭代到最初，可能会呈现与聚类核心不属于同一连通域的孤立像素点，能够应用到连通算法将其调配到最近的聚类标签。

   论文中并未给出具体的实现算法。而本文的利用场景是生成像素画，会对像素进行下取样，并不会细化到每个像素，由此，本文不做聚类优化解决。

小小总结一下，SLIC 算法流程大体与 K-means 是统一的，一直迭代计算间隔最小的聚类簇，不同的是只对聚类核心的 S 间隔内像素点进行计算，缩小了不少的计算量。

生成像素画

基于 SLIC 算法，咱们曾经能够把一张图划分为 N 个超像素点。每个超像素中像素都是相近的。也就是说，每个像素都被归类为一个超像素，有一个聚类核心。那么将像素的色彩赋值为其聚类核心的色彩即失去咱们想要的成果。

设定肯定步长 stride，应用Canvas，每隔stride 个像素，将像素赋值为其聚类核心的色彩，即失去最终的像素化后果。

而每个人对于像素画的主观感触是不统一的，为了让用户有更多的抉择，失去本人称心的后果。能够裸露更多的人工干预参数，比方勾销聚类优化的终止条件，改为由用户来设置迭代次数，以及最终取像素值的步长。人工设定的参数包含了

• 超像素点大小 blocksize；blocksize 越小，超像素点宰割越细腻。
• 迭代次数 iters；iters 越大，宰割后果更精准，计算工夫越长。
• 色彩空间权重 weight；weight 越大，色彩对于宰割后果的影响越大。
• 取像素点步长 stride；stride 越小，生成的像素图越靠近超像素点，也就越细腻。

实现用户交互界面

作为一个工具，天然须要用户交互界面，前端界面基于 HTML/Javascript/CSS 搭建，应用 Canvas API 绘制图像内容，而用户交互面板抉择的是 dat.gui [3] 库。dat.gui 是一个轻量级的图像化界面库，十分实用于参数的批改，罕用作可视化 Demo 的演示。反对的参数类型包含了Number、String、Boolean、自定义函数等。能够为不同的属性绑定相应的响应事件，当属性值扭转时主动触发事件。

为生成像素化工具增加以下属性与事件：

• 当 iters、stride、blockSize、weight（色彩空间权重 m）参数变动时从新进行SLIC 算法的计算，并从新绘制计算结果；
• 增加 Upload image 与Export image 按钮，反对用户上传图片与下载像素化后的图片；

在绘制图像的 Canvas 画布层上叠加一层 Canvas 画布，对算法的后果进行可视化，增加以下性能

• grid开关管制是否绘制像素网格；
• Centers开关管制是否显示聚类核心；
• Contours开关管制是否显示聚类边缘轮廓；

其中聚类中心点 Centers 的绘制间接应用ctx.fillRect 传入中心点坐标即可。

超像素轮廓 Contours 的绘制则须要先计算失去轮廓点。

能够对每个像素点与四周的 8 个像素点进行比拟，如果聚类核心不同的像素点个数大于2，则代表着这个像素点四周有两个以上不同类别的点，则这个点为轮廓。成果如下：

最初，就失去一个简略的生成像素画工具了。

体验地址

完整版代码地址（JS 版）

参考文献

[1] Achanta R, Shaji A, Smith K, Lucchi A, Fua P, Su ̈sstrunk S. SLIC superpixels. Technical Report. IVRG CVLAB; 2010.

[2] Gerstner T , Decarlo D , Alexa M , et al. Pixelated image abstraction with integrated user constraints[J]. Computers & graphics, 2013.

[3] https://github.com/dataarts/d…

欢送关注凹凸实验室博客：aotu.io

或者关注凹凸实验室公众号（AOTULabs），不定时推送文章。