拼贴画的生成属于可视化与图形学的交叉领域，其领域学者就拼贴画问题提出不同思路。图形学领域学者将该问题视作一个打包问题：先利用形状描述符对输入的图形进行相似度分析，然后将全局或局部轮廓相似的图形进行拼接;抑或是使用轮廓细分与匹配的方法，将目标轮廓按一定规则细分成格子后，将与格子相似的图形填充到格子中。可视化领域学者侧重如何传递信息，即如何将输入数据中包含的信息与拼贴画元素进行映射：将输入的图形抽象为特征向量，从而与最终可视化的位置进行映射，更好地展现图形特征数据;抑或是在可视化文本中，将带有词频的文字视作图形输入，通过算法将填充文字与目标轮廓进行映射，从而生成信息量与美观度俱佳的结果。
2形式化定义
如图1所示为常见的3种拼贴画形式，首先对拼贴画自动生成技术进行形式化定义——拼贴画生成的输入集主要分为两部分：
第一个输入集为目标外轮廓约束，一般分为两种：一种为强外轮廓约束，如复杂图形、照片等，填充时需要充分考虑外轮廓的约束，使填充图形的边缘尽可能贴合强外轮廓约束的边缘，这属于较复杂问题;另一种约束为弱外轮廓约束，如矩形、圆形、简单字母等，填充时外轮廓的约束较小，只需考虑边界问题即可。
表1拼贴画生成算法结构表
(a)图片马赛克(b)词云(c)传统拼贴画图1常见的拼贴画设计
3自顶向下的生成技术
自顶向下的生成技术思路是从生成的目标轮廓分析或是从填充图形的整体分析，先确定填充图形在轮廓的粗略位置，再小范围地改动图形的细节、角度、位置以得到更优的结果。
3.1基于轮廓细分与匹配算法
基于轮廓细分与匹配算法常由3个步骤构成：首先对目标轮廓进行细分，将轮廓分成多个规则或不规则的单元格;然后给每个单元格匹配最合适的填充图形;最后对每个单元格的填充图形进行调整以增强效果。
Finkelstein在1998年提出ImageMosaics技术，其针对的问题为：如何将用户输入的一组图片拼接到另一张目标图片中，产生近距离看是一组图片，远距离看是目标图片的效果。在算法上，首先将目标图片分割成规律的矩形，利用基于小波变换的图形匹配算法对每个矩形匹配最相似的输入图片;然后对矩形内图片的亮度、灰度值进行调整，从而使结果更接近目标图片。但由于其在分割目标图片时，将图片仅简单地分割为规则的矩形，而未考虑图片本身的特点，故被分割图片不能很好地呈现目标图片的轮廓。
Haeberli引入Voronoi算法，将不规则图形(如油画的笔触或多边形)随机地摆放并填充至目标区域，以达到转换输入图片风格的目的。其思路是将油画的笔触或者多边形抽象成填充图形，并在填充至目标图片过程中，先使用Voronoi算法细分目标图片，再将笔触填充至网格内。在这一过程中，为了使笔触更接近真实油画效果，Haeberli引入根据输入图片计算梯度方向的方式来引导笔触的填充方向，使其更接近手绘效果。但该方法忽略了原始图片中物体的边缘(如人物图片的人物轮廓、物体图片中不同物体的边缘)，没有使填充图形贴合或者表达原图片中的轮廓，导致生成结果中的轮廓不清晰。而清晰的轮廓可以帮助用户迅速感知图片本体，所以该方法生成的结果辨识度不佳。
在Haeberli方法基础上，Hausner引入基于重心的泰森多边形图(CentroidalVoronoiDiagram，CVD)，其针对的目标问题为：使用多边形填充目标图片，着重表现输入图片中的边缘与轮廓，来增强结果的辨识度。传统的CVD图使用欧式距离度量，通过多次迭代使全局欧式距离最小，导致计算出来的区块趋近于六边形。在Hausner的研究中，通过将度量修改为曼哈顿距离使最终区块接近正方形，并用于填充。此外，也可以通过修改度量的方向来影响CVD图中格子的方向。为了高效地生成带方向度量的CVD图，该研究借鉴了Hoff提出的生成技术。并在Hoff生成技术的基础上，将欧式距离替换成曼哈顿距离。为了提取原始图片中的方向信息，Hausner引入了方向场，从原始图片的轮廓中产生方向场来指导带方向度量的CVD图的生成。结果显示，作为填充图形的小正方形可以很好地表达原始图片中的边缘，用户可以非常迅速地辨认仅由带色彩的正方形组成的拼贴画。该方法有足够的创新性，产生了具有强大表现力的拼贴画。但缺陷在于其构成要素仅为正方形，很难表现更为复杂的图片，这很大程度上限制了输入图形的类型，普适性较差。
3.1.2代表性算法介绍
Kim提出一种基于最小化能量函数的生成技术，与Hausner方法相比，更具有普适性：将填充图形从简单的多边形，扩充到任意的输入图形，并填充到任意的目标轮廓中。该算法属于基于轮廓细分与匹配算法中较有代表性的算法，综合了该线路上前人的研究结果。如借鉴Hausner的思路，使用CVD图来辅助拼接等，在此基础上将问题抽象成能量函数最优化的过程，并结合多种优化方式来加速生成。同时，Kim将输入集的范围扩充到任意图形，进一步扩大了算法的适用范围。具体来说，能量化定义的优势就是可以通过增减或调整各能量项的权重使最终的结果呈现不同的风格，其能量E定义为：
其中，能量E由各项的加权和构成;颜色项Ec为图形颜色与当前位置目标容器颜色不符的程度，wc为权重;间隙项EG为最终结果中空白区域的大小，wG为权重;重叠项Eo为最终结果中图形之间的重叠程度，wo为权重;变形项ED为图形过度变形的程度，wD为权重。
拼接时，是在不对图形进行变形的前提下减少间隙和重叠，并使图形的颜色与目标容器位置的颜色保持一致，从而得到图形的初步匹配结果。为使每次拼接操作后，更新的容器更便于下一次拼接。在每次拼接之前，借鉴Hausner的思路，按图形的平均大小对容器构建CVD图，随机选择邻居数量最少的位置，从而减少拼接后容器产生突出或不连通的问题，便于后续的拼接。如图2所示，构建CVD邻接图后，图中绿色点为被选中的位置，其仅有2个邻居，拼贴在此位置对网格的影响最小。
当某一步无法找到合适的图形去填充目标容器时，算法需要退回上一能量最小处。为减少这种回溯，Kim借鉴Russell的思想，使用超前技术，惩罚拼接之后无法放置图形的小面积区域。
前文所述，在不对图形变形的情况下进行拼接，尽可能形成少重叠和少间隙填充的目标容器的布局。但其中仍会出现很多空隙与重叠，导致生成结果并不美观。为此，该研究借鉴了Kass的思路，使各个图形可以在保持原始形状和最小化能量E之间平衡，通过微小的变形来取得更好的结果。在CVD图的变形过程中，初始拼接得到的CVD结果，会造成较多的重叠与空隙。经过优化过程，重叠与空隙有一定程度的减少。最终，在各个CVD格子变化程度较小的前提下，减少了格子之间的重叠与空隙，达到控制变形程度与提高结果填充率、降低重叠率之间的平衡。
图2使用CVD邻接图选择拼接位置
因拼贴画的生成过程中需要考虑多种因素，如美观度、空隙等，所以基于最小化能量函数的生成技术在拼贴画的生成中非常常见。其大致流程为将拼贴画生成中多种因素抽象为能量函数中的参数项，并赋予不同的权重以形成能量函数，之后通过算法最小化该能量函数。Xu提出的Calligraphicpacking算法亦是如此，其将拼贴画生成的范围扩展到书法中，将任意文字作为拼贴画生成算法的输入，通过倾斜、扭曲等操作使文字填充到任意给定的图形中，形成有美感的书法艺术作品。并在能量函数中引入风格因素，算法可以根据不同的风格调整能量函数中各项的参数，生成不同风格的输出结果。
3.2基于特征提取算法
基于特征提取的方法一般分为3个步骤：首先对输入图形进行特征提取;然后处理特征信息，并进行初步布局;最后对布局进行优化调整，以减少重叠和间隙。
鉴于使用参数控制图形的分布十分困难，Hurtut提出一种基于结果统计的方式。其针对的问题为：如何从用户输入的拼贴画学习拼贴画结构，并以该结构为基础，生成更大范围的拼贴画结果。算法输入一张包含多种图形的拼贴画，系统使用基于图形外观的分类算法将原始拼贴画中的组成图形根据外观分类，并抽象出布局。系统通过构建统计学习模型，从输入的布局中学习同类别内部以及不同类别之间的布局关系，从而在输入布局的基础上扩充出更大范围的结果。其缺点是不能像传统拼贴画的构造过程，输入足够的图形与轮廓生成指定的结果。并且，由于采用了基于统计的生成方式，因此无法控制生成结果的风格，也很难根据不同的情景生成不同的结果，使用户对结果的控制力大大下降。
在特征提取上，Maharik等将特征提取的对象转移到轮廓，其针对的问题为：如何将输入的文本以流线的形式填充到目标轮廓上。该系统首先在目标轮廓中生成矢量场;进而生成符合代表目标轮廓的流线，并使其接近正常阅读方式;再在生成的流线上填充文本，从而使文本既能够较好地填充目标轮廓，又具有较强的可读性。其结果在文本对目标轮廓的表现力以及文本的可读性之间取得了较好的平衡。
基于特称提取的算法也被应用在其他类型的可视化中，如Afzal等提出的TypographicMaps，其针对的问题为：如何将文本依照地理信息填充到地图中。该系统以地图中提取的信息和用户的约束作为特征填充文本，即以输入地理信息作为布局文本的主要依据，同时接受用户定义的视觉属性和约束条件。从地图中提取的特征为文本布局的位置提供了基础，而文本又给地图提供了更多的信息，最终提高了可视化信息传递的效率。
3.2.2代表性算法介绍
Hurtut[15]和ztireli都认为利用参数控制图形的分布是非常困难的，但他们都选择基于统计的方式来布局。而Reinert提出一种不基于统计数据的方法，即从用户的输入中推导布局规则。基于特征提取算法中，具有代表性的Reinert算法摒弃了以往使用参数或基于统计的布局方式，将拼贴问题形式化为从每个图形的高维特征空间映射到二维的布局问题。同时，通过在系统中引入交互，用户可以使用图钉固定一部分图形的位置，系统从用户确定的子集中计算出用户期望的布局，并影响图形的最终布局。
表示MEN个不同的特征。特征是由程序自动获取的视觉特征，如：大小、形状、亮度、纹理等。通过公式(2)，将高维特征空间降维为二维坐标矩阵X：
平衡临近图形的距离可以产生良好的最终布局，但从高维特征空间映射到二维坐标时，每个图形被看作一个特征向量，并未考虑图形之间的重叠与间隙。即映射时未考虑图形在空间上的相互关系，故需在映射之后，对图形的布局进行优化。
在布局上，系统也使用了基于CVD图的方式，通过逐步迭代目标函数来达到优化目的。在目标函数中，使用图形边界与CVD区域边界的差值的平方和来衡量布局X偏离平衡的程度：
交互时，系统首先生成一个初始结果，用户可以使用图钉工具在界面中固定一部分图形的位置;随后，系统根据用户指定图形的特征向量，推测用户期望的布局，并将其应用到全局。
4自底向上生成技术
自底向上生成技术的思路为从每个图形出发，依次向已有的图形上拼接最合适的图形，最终逐步填充整个目标轮廓。
4.1基于形状描述符匹配算法
在自底向上的拼接过程中，由于每当系统将一个图形拼接到拼贴画中，必须不断地对图形进行角度、比例的调整，并评估两者的匹配程度，因此需要高效的局部形状匹配。这个过程涉及巨大的搜索空间——大量的图形，且对于每个图形又有无限个角度、位置、比例的组合。现有的描述符，如基于曲率比例空间(CurvatureScaleSpace)、形状上下文(ShapeContext)、三角区域表示(Triangle-areaRepresentation)，可以很好地测量形状之间的整体相似度，但不能直接应用到拼贴画的生成中。拼贴画的生成核心在于两个图形的局部形状的拼接，而并不考虑两个图形的整体相似度，且全局描述符带来的巨大搜索空间会导致拼接效率极速下降。
Kaplan提出一种利用给定的封闭图形在平面上进行紧密平铺的算法，其使用模拟退火算法优化参数化抽象后的拼接问题，生成“埃舍尔”风格的拼贴画。但其对输入、输出的限制均比较大，只能输入单一的封闭图形，很难限制与自定义输出，这些缺点较大地限制拼贴画的多样性。并且其算法只对图形进行旋转，而不考虑比例缩放等操作，从而影响输出结果的丰富性，很难满足用户多元的需求。
Kwan提出的算法可以对任意填充元素与任意指定的轮廓进行拼贴画生成，并支持对输入元素进行旋转与比例缩放来优化填充结果，极大地扩展了算法的应用场景。该算法在拼贴画生成领域具有开创性，引入了以局部图形描述符为基础，在填充图形中搜索最适合填充的图形。相比于传统的形状描述符在匹配时需要考虑位置、角度和比例的组合，Kwan提出的PAD(PyramidofArclengthDescriptor)描述符在匹配时比例和角度不变，这意味着在匹配最相似的图形时，无需计算角度和比例。通过该描述符确定最优匹配图形以及最优匹配点之后，可使用较小的搜索代价确定该图形的角度和缩放。PAD描述符也可以通过改变参考点的数量，动态调整PAD向量的描述能力和计算复杂度。
PAD描述符的核心是一个基于角度和比例不变域的塔式描述符。首先算法确定一个缩放比例不变域，此处使用的是绝对曲率的积分。给定一段曲线，对t、s点的绝对曲率积分的定义为：
但仅使用绝对曲率的积分并不能准确地表达图形，或者说，不能依靠绝对曲率的积分来进行形状匹配。所以研究中引入了弧长这一形状信息来辅助形状匹配。弧长并不是对缩放比例不变的，但可以通过简单的变形来解决。
其中，li和ri为p点的左侧和右侧在同样的绝对曲率的积分变化率的间隔弧长;n可以根据需要进行调整，来获得更高的准确度。则点的描述向量为：
图3PAD拼接示意图
可以通过计算两点的PAD向量之间的距离，来计算两图形轮廓上两点的相似度。其距离公式为：
通过弧长与曲率的结合，对图形局部轮廓进行特征描述，并计算图形局部的相似度，可取得较优的拼接效果。但这样可能会陷入仅考虑轮廓的局部而忽略了整体的问题，从而导致图形局部匹配度较高，但全局相对较差。该方法通过引入对候选位置打分的方式来选择最优的拼接，一定程度上缓解了这个问题。但从本质上来说，PAD的生成过程是贪婪的，并不能得到全局最优的结果。
4.2基于螺旋线算法
基于螺旋线算法将从文本中提取的核心词作为主要的输入图形，文本的大小代表权重，最终拼接成完整的拼贴画，其主要用于词云可视化中。Viegas最初提出使用阿基米德螺旋线来生成词云，将单词沿着以画布为中心的螺旋线按照权重从大到小的顺序依次拼接，生成最终结果。词云作为经典的文本可视化工具，可以迅速生成美观且信息量丰富的可视化结果。但在生成词云的过程中，并不会考虑目标轮廓，所以生成的结果不能很好地填充目标轮廓，不适合生成有目标轮廓的拼贴画。故许多研究者在词云算法的基础上进行了诸多改进，使词云可以有效填充目标轮廓。
Buchin提出GeoWordClouds算法，其输入是一个在每个位置均有文本标签的目标轮廓。首先，采用聚类的方式对输入的文本进行分组;然后，根据填充词的频率，在填充目标轮廓时尽可能使大小合适、不重叠的文本靠近。这一定程度上解决了词云不能很好地填充目标轮廓的问题，并且取得了相对不错的效果。但其对用户的输入要求比较高，需要目标轮廓的各个位置带有文本标签，不具有普适性。
4.2.2代表性算法介绍
Wang提出一种具有轮廓约束的词云算法，降低了用户使用的门槛——仅需要用户输入普通的文本和目标轮廓，而无需额外的信息即可得到填充率高且美观的结果。该算法复杂度较低、生成速度较快，适合大规模的文本可视化生成。
具体来说，系统首先提出了形状感知的阿基米德螺旋线(如图4所示)，其核心在于将目标轮廓的距离场和阿基米德螺旋线结合起来。传统的螺旋线是以画布中心为原点，沿着圆的切线方向逐步扩大半径而绘制出来。在这个过程中，螺旋线的方向一直是圆的切线方向，所以绘制结果与目标轮廓无关。而引入距离场后，距离场可以很好地反映目标轮廓的信息。在绘制螺旋线时，以距离场的极点为原点，每一点的前进方向并非一直是圆的切线方向，而是根据每一点的距离场信息确定，由距离场引导生成符合目标轮廓的螺旋线。
为了使算法更具有普适性，系统加入了对复杂图形的处理。为了防止极端情况下，以中心为原点的螺旋线不能很好地对轮廓边缘进行处理，算法引入了图形切割的步骤。在输入图形后系统会首先检测目标轮廓内的所有分区，并为每个分区生成单独的距离场;然后使用一个迭代的梯度下降过程，在每个分区中定位出局部最大值;最后生成单独的螺旋线来排布单词。其效果如图5所示，(a)中图形仅被分为两个区域，填充效果较差，
(b)为ShapeWordle所采用的图形切割后的分区结果，(c)为在新的分区结果上使用形状感知的螺旋线所产生的效果。结果表明，经过分区后，螺旋线对目标轮廓的贴合能力得到提升，实现了文本填充目标轮廓。但基于螺旋线算法的限制在于，螺旋线的排布适合规则的输入，如矩形文本或常规且相似的图形，而难以对不规则的输入图形进行排布。
图4形状感知的阿基米德螺旋线
5发展趋势与创新研究
在生成算法上，自顶向下的生成技术和自底向上的生成技术各自取得了相当优秀的结果，但也存在一些的问题尚待解决。
图5ShapeWordle分区方式对比
在自顶向下的生成技术中，Hurtut和Reinert将不同的思路引入拼贴画生成中。Hurtut借助统计模型，将用户生成的拼贴画进行扩展，这种方式非常适合墙纸、瓷砖等需要重复图案生成的应用场景。其问题也相对明显，用户对生成结果的控制力较差，不能有效地对结果进行定制。在该思路的基础上可以尝试拓展可控的参数，增加用户对生成过程的参与度或对结果的可操作性，从而有效提高算法的适用范围。Reinert的创新之处在于，从用户的输入中推导布局，将拼贴画生成看作每个图形的高维特征向量降维到二维坐标的问题，在降维之后进行局部的微变以优化最终结果。该思路与常规的解决方式有较大区别，可以迅速确定图形的大概位置，但系统中微调的算法只能减少重叠问题，而不能提高图形之间的匹配度，造成结果的填充率较低。该算法的缺点在于，初始降维时图形轮廓完全被忽略。因此，可以在特征向量中进一步引入对图形轮廓的描述符，降维时将图形相似或可拼接的图形尽可能靠近，并在降维后小范围内引入图形描述符来进行局部图形的位置调整。也可以进一步对局部图形的位置进行小范围的再分配，改变其角度与缩放比例，完善局部图形的拼贴效果。
而对于基于螺旋线算法，目前Wang的形状感知的螺旋线在实现将文本填充到目标轮廓上取得了较为不错的效果，且能够移植到其他类矩形的填充图形上。但由于沿螺旋线的初始布局过程中仅考虑了矩形之间简单的重叠避免，不适用于复杂图形的重叠避免与局部轮廓拼接。同时，形状感知的螺旋线在将图形填充到目标轮廓中的价值很大，可以有效地提高填充算法对目标轮廓的感知能力。且其算法复杂度较低，可与其他算法结合，增强其他算法对目标轮廓的感知能力。如先用包围盒算法将图形抽象成易于计算重叠的简单图形，然后使用形状感知的螺旋线将图形拼接到目标轮廓中，以此为基础进行微调，提高局部轮廓的匹配度，从而充分发挥其算法对轮廓的感知能力。
5.3智能算法
随着智能算法的发展和应用，越来越多学者尝试将智能算法引入拼贴画领域。根据目的，将应用于拼贴画自动生成的智能算法简单分为两类：第一种是将智能算法应用在对输入图形的预处理中，如提取图片的核心区域、人脸等，或对图形的特征进行提取，并根据提取的特征进行降维，从而确定图形的初始位置;第二种则直接将智能算法应用于确定图形的最终位置，即应用于拼接，如根据统计学习对已有的拼贴画进行扩展。
5.3.1应用于预处理
而使用智能算法进行核心区域与人脸的提取，常应用于图片拼贴中，可以有效去除图片中无效的背景区域，使拼贴算法的重心处于图片中的核心区域。
5.3.2应用于拼接
5.4交叉领域
5.5创新趋势
在设计拼贴画生成算法之外，扩大拼贴画算法的适用范围也是发展该领域的重要方向。如Xu将拼贴画的输入扩展到书法领域，通过应用拼贴画算法的思想将文字填充生成艺术性较强的文字画。基于这一思路，可将拼贴画的输入扩大到其他元素，从而产生创意性的结果。将算法的输出载体扩展到其他领域亦是如此，如Gal将拼贴这一概念扩展到三维空间，使三维的物体拼接到三维的轮廓中，增强了结果的表现能力与表现空间。在拓展维度方面，也可以在不同载体上做更多的尝试，如将载体扩展到3D打印、虚拟现实技术与增强现实技术等方向。
6总结
本文从自顶向下与自底向上两种思路归纳概述了计算机用于拼贴画自动生成的研究进展,对其中较有创新性的算法进行了分析，并对该技术的未来发展趋势进行了总结和展望。
随着社交电商与社交互联网的发展，工业界对自动生成较为复杂的设计需求将持续增长，而拼贴画自动生成技术作为结合了图形学与可视化两个领域的自动技术，可在可视信息表达与图形展示效果之间取得良好平衡。目前，该领域仍然存在许多重要的问题和挑战，需要更多的研究人员继续进行深入研究与探索。
2022年第1期
传动网-工业自动化与智能制造的全媒体“互联网+”创新服务平台