摘要

图像拼贴是可视化图像集合的非常有用的工具。 大多数现有的生成图像拼贴的方法和商业应用都是基于简单的形状设计的，例如矩形和圆形布局。 这极大地限制了图像拼贴在某些艺术和创意环境中的使用。 尽管有一些方法可以生成不规则形状的图像拼贴，但它们经常会遇到严重的图像重叠和过多的空白空间。 这使得此类方法无法成为有效的信息通信工具。 在本文中，我们提出了一种形状切片算法和一种优化方案，可以在给定输入形状和图像集合的情况下，以信息丰富且视觉上令人愉悦的方式创建任意形状的图像拼贴画。 为了克服不规则形状的挑战，我们提出了一种称为形状感知切片的新颖算法，该算法基于中轴和二叉切片树将输入形状划分为单元。 形状感知切片专门针对不规则形状而设计，考虑了人类的感知和形状结构，以生成视觉上令人愉悦的分区。 然后，通过分析输入图像来优化布局，目标是最大化图像的总显着区域。 为了评估我们的方法，我们进行了广泛的实验并将我们的结果与之前的工作进行了比较。 评估表明，我们提出的算法可以有效地在不规则形状上排列图像集合，并创造出比之前的工作和现有商业工具更好的视觉结果。

关键词关键词 图片集可视化、图片拼贴、不规则形状布局

1简介

图1： 图像拼贴是通过我们提出的方法生成的。 使用相同的图像集，我们将其拼贴成各种不规则的形状。

图像被认为是人们通过移动设备可视化他们想要分享的内容的方式。 随着社交媒体平台（例如 Twitter、Instagram、Facebook、Google Photos 等）的发展，分享照片的需求变得越来越有吸引力。 可视化照片集的一种有趣方法是将它们拼贴成有趣或有意义的布局。 结果也可能是人们出于不同目的用来表示其图像集合的视觉摘要的方式，例如，广播广告（例如，使用袋鼠的形状来可视化澳大利亚的一组场景）、纪念（例如，使用心的形状来可视化一系列婚礼场景）。 这样的研究领域被称为图像拼贴。

这个令人兴奋的研究课题很早就通过各种方法进行了研究。 [33,17,21,35]的研究人员专注于保留每个图像的原始长宽比并丢失图像内容。 其他方法[25,31,16]通过尝试仅将每个图像的显着切口尽可能完全地放入画布来考虑图像的内容。 换句话说，他们的系统可以通过重叠图像来生成拼贴画，而不会遮挡显着区域。 然而，大多数这些先前的研究在将图像集合拼贴成任意形状方面都存在同样的困难。 也就是说，它们都仅限于矩形布局。

除了上述方法之外，近年来还发布了一些图像拼贴的商业应用程序，例如 Shape Collage [4]、FigrCollage [26]、ShapeX [ 24] 和 Adob​​e [1]。 有了这些应用程序，无需任何设计经验，人们就可以制作自己的拼贴画，并让他们的创造力将所有美好的回忆融合在一起。 尽管如此，它们仍然受到一些限制。 生成的拼贴画中的图像被严重遮挡[4]。 生成的布局中的单元格太小且太均匀（例如，相同大小的矩形或正方形）[26]。 这个问题使得该方法面临图像尺寸和布局形状精度之间的基本权衡。 也就是说，集合中的图像可能必须显着缩小才能完全适合布局。 这种现象导致拼贴画在视觉上不美观。 在ShapeX [24]中，在输入形状上叠加了均匀的网格，而不考虑形状结构。 因此，该应用程序生成的拼贴不仅具有与 Shape Collage [4] 和 ShapeX [24] 相同的缺点，而且还在边界区域产生令人不快的区域。 Han 等人 [8] 尝试通过首先将图像投影到 2D 圆形区域并在目标区域内局部移动图像来拼贴不规则形状的布局。 因此，他们的方法旨在适用于距离圆形不远的形状，例如一颗心或一个苹果。 此方法不适用于高度不规则的形状（例如中间有孔的形状）。 这些结果如图2所示。

(a) Shape Collage [4]

(b) Han et al. [8]

(c) FigrCollage [26]

(d) ShapeX [24]

图2： 示例拼贴画是由以前的工作和商业应用程序生成的。 拼贴上方的黑色剪影是输入形状。

本文针对上述问题，提出了一种任意形状上的图像拼贴（简写为ICAS)方法，如图1所示。 我们的拼贴技术考虑了给定集合中图像的输入形状和内容信息。 这使得我们的方法能够生成视觉上令人愉悦的拼贴画。 为了实现这一目标，我们提出了一种基于二叉切片树的算法，该算法承担将输入形状划分为区域的任务。 为了提供视觉上令人愉悦的拼贴，我们在拼贴之前通过图像内容分析过程定义图像的主题。 为了评估我们的图像拼贴方法的有效性，我们使用不同的输入形状和图像集合对其进行测试。 我们的评估实验获得了令人信服的结果。 我们进一步将我们的结果与以前的工作和现有商业应用的结果进行比较，以证明我们提出的框架的优势。

我们的贡献总结如下：

• 我们提出了一种新颖的 ICAS 算法。

• 我们开发了一种布局生成方法，形状感知切片，这对于处理不规则形状的凸凹表面特别有用。

• 优化过程 我们在当前的工作中研究使这种图像拼贴方法能够在输入形状、布局设计和图像集合的视觉内容之间建立一座桥梁。

• 对形状和图像集的各种实验表明，我们的方法更易于使用，并且可以产生更有吸引力的结果。 这使得普通用户能够更容易地一起想象他们的美好回忆。

2相关工作

2.1 图像拼贴

我们已经看到，图像拼贴方法可以分为矩形和非矩形或内容感知和非内容感知。 看待这些作品的另一种方式是他们如何排列图像。 许多作品将相似内容的图像组合在一起，并将它们放置在靠近的位置。 Liu 等人[16]使用t-SNE根据特征向量将每个图像嵌入到2D画布上。 Tan 等人[31]根据图像之间的相关性，利用k-means算法对图像进行聚类，并将它们放在同一个单元格内。 Pan等人[21]在放置图像时考虑图像的重要性和美观性，重要的图像放置在靠近拼贴中心的位置。 宋等人[29]强调拼贴整体构图平衡的运用，并根据balance-ware指标来安排图像。 一些工作侧重于图像摘要能力，其中首先从大量图像集中选择代表性图像，然后将其可视化。 Rother等人[25]根据代表性、重要性和物体位置选择排名靠前的图像。 Pan等人[21]考虑简洁性、多样性和美观性，贪婪地选择图像。 最新的工作[35]提出了一种创新的连续树表示来划分画布。 这使得可以通过反向传播来训练端到端拼贴生成模型。 然而，这个公式只能在矩形画布上定义。 另一条工作重点是图像集合的交互式可视化。 Nguyen 和 Worring [19] 提出了针对 10,000 多张图像的可视化方案。 Lekschas 等人[14]提出了一个用于可视化和探索包括大型图像集合在内的小倍数的框架。

与现有方法相比，我们的新方法可以概括为非矩形和内容感知。 显着的物体将根据形状结构被保留和放置。 重要的图像将放置在最显着的位置。

2.2 形状分解

平面形状分解方法可以大致分为两类。 人们试图将形状分解为凸多边形。 另一种尝试根据认知研究模仿人类如何划分形状。

早期的作品[12, 15]通常侧重于将形状分解为凸部分。 传统的严格凸分解是一个经过充分研究的问题，但它并不直接适用于大多数形状分解任务。 缺点之一是它会产生过度分割的零件。 Latecki 和 Lakämper [12] 观察到小于一定尺度的非凸性与人类如何感知形状无关的现象。 因此，他们开发了 DCE 算法来控制非凸性的容忍程度。 Lien 和 Amato [15] 提出近似凸分解，它将形状分解为近似凸的部分。 我们在这项工作中不使用近似凸分解，因为它会产生微小的分区，不适合拼贴生成。

后来的形状分解研究尝试开发基于心理物理学发现的计算模型。 从这些发现中得出的最受认可的规则是最低规则[10],快捷规则[28]，以及部分剪切[27]的定义。 Luo等人[18]提出了一种实现上述规则的优化模型。 Papanelopoulos等人[23]有效地利用了中轴表示并捕获了心理物理学研究提出的大部分规则和显着性度量，包括最小值和捷径规则、凸性和对称性。 Papanelopoulos 等人[23]的工作被称为MAD，它基于严格的数学推理，而不是像早期方法那样严重依赖启发式规则。 因此，我们更容易根据自己的目标调整它，在本例中，生成图像拼贴画。 此外，它不需要像 De Winter 和 Wagemans [6] 的工作那样复杂的优化过程，并且它在公共数据集中比其他工作取得了更好的性能。 我们的形状分解方法利用这个概念作为基线将输入形状分解为凸多边形。 此后，我们研究了一种新颖的切片算法来生成平衡且视觉上令人愉悦的布局.

3系统框架

图3： 系统架构

我们的ICAS系统的框架如图3所示，它由三个主要过程组成：图像内容分析、形状分解和形状感知切片和优化。 所提出的方案将任意形状和图像集合作为输入。 我们的目标是生成信息丰富且排列精美的形状图像拼贴画。

图像内容分析建议在将图像放入布局之前定义图像的重要信息。 此过程可以避免所得拼贴画的美观性较差，例如，重要的对象被裁剪掉。 这种现象被认为是先前方法[4,8,24,26]中的一个缺点。 在我们的方法中，图像集合首先通过显着对象检测模型。 因此，每个图像都与重要性分数相关联。

形状分解负责将高度不规则的形状分割成区域，这些区域是凸多边形。 正如我们在上一届会议中讨论的那样，任意形状的布局具有挑战性，这也是我们当前的方法与以前的工作之间的主要区别。

形状感知切片和优化是我们工作流程中的主要流程。 形状被进一步划分，使得每个区域对应于给定集合中的图像。 我们首先提出基于中轴的二元切片树（MABST）和形状感知切片（SAS）操作作为划分不规则形状画布的新方法来实现这一目标。 然后，我们选择一个可以最大化给定图像集合的重要区域的最佳布局。 最后，应用我们定制的图像变形技术来创建最终的拼贴画。

4方法论

4.1 图像内容分析

为了在图像内容和布局设计之间建立桥梁，我们分析给定集合中的图像内容。 分析给定集合中图像的内容使我们的系统能够理解单个图像的语义和集合的视觉主题。 为了分析集合中图像的内容，我们采用有监督的显着对象检测模型[22]。 每个图像的主题被简化为包含所有显着像素的显着框 $Sb=[b{x}_1,b{y}_1,b{x}_2,b{y}_2]$。 这样的框用于表示图像的重要区域。 我们选择边界框表示而不是直接使用显着图，因为凸多边形内矩形面积的最大化可以通过线性规划有效地解决。 正如我们将在下一节中展示的那样，当我们搜索最佳布局时，我们需要多次计算该值。

我们的拼贴系统的一个优点是，我们允许用户在集合中指定他们最感兴趣的照片。 我们在布局时会考虑这些照片。 因此，我们鼓励用户从视觉上愉悦或审美因素上感性地选择集合中占主导地位的照片。 我们记录用户指定的图像并为其分配高重要性分数。 在用户没有选择的情况下，我们采用NIMA[30]来衡量他们的审美得分。 因此，对于给定的集合，我们有一个集合 $𝐈=\{I_i\},i=0,\mathrm{\dots },N_I$,$N_I$ 是输入图像的数量。 每个$I_i$都是${\beta }_i$和$R_i^m$的元组，分别表示图像的索引和重要性等级。 请注意，仅评估显着框中的图像部分，因为图像在最终拼贴画中通常不完全可见。

从该分析中可以获得三个主要好处。 边界框帮助我们找到适合图像中重要区域的定制单元。 其次，这可以避免图像中的主体被裁剪。 第三，根据审美分数对照片进行排名并将其与布局相结合，以提供语义和视觉上令人愉悦的拼贴结果。

4.2 带中轴的形状分解

形状分解算法将任意输入形状分解为可管理的部分，即凸部分。 分解是通过确定一组部分切割来完成的，这些部分切割定义为将形状分成多个部分的线段。 我们采用基于中轴的最先进的形状分解算法（所谓的MAD），该算法在Papanelopoulos等人[23]中介绍。 在深入研究形状分解算法之前，我们简要概述了其方法中使用的中轴。

给定平面形状 $𝐗\subset {ℝ}^2$，距离图 $D(𝐗):{ℝ}^2\mapsto ℝ$ 是将每个点 $z\in {ℝ}^2$ 映射到的函数

$$D(𝐗)(z)=\underset{x\in \partial 𝐗}{inf}\Vert z-x\Vert ,$$ (1)

其中 $\parallel \parallel$ 表示 $l^2$-范数。 对于$z\in {ℝ}^2$，让

$$\pi (z)=\{z\in \partial 𝐗:\Vert z-x\Vert =D(𝐗)(z)\}$$ (2)

是边界上距 $z$ 最短距离的点集。 这称为$z$在边界上的投影集。 每个 $x\in \pi (z)$ 称为 $z$ 的投影。

形状$𝐗$的中轴是一组具有多个投影点的$𝐗$点，其公式为：

$$M(𝐗)=\{z\in 𝐗:|\pi (z)|>1\}.$$ (3)

该集合可以解释为 ${ℝ}^2$ 中的有限线性图，其中恰好有两个投影的点作为边，其他点作为顶点 [5]。 图4逐步可视化了这些数学定义和MAD算法。 如果某个顶点在图中的度数为 1，则该顶点被称为结束顶点。 类似地，$𝐗$的外部中轴可以定义为其补充${ℝ}^2\setminus 𝐗$的中轴。

图4： MAD 的第一步到第五步的插图。 (a) 和 (b) 是内部中轴和外部中轴。

中轴携带对于分解不规则形状至关重要的信息。 根据最小值规则[10]，部分切割端点应该是形状边界曲率负最小值的点，即形状的凹度。 可以观察到，内（分别为外）中轴的端部顶点对应于凸（分别为凹）角。 更具体地说，仅端部顶点及其投影就可以确定凸面（或凹面）的位置、空间范围、方向和强度。

一旦找到凹角（图4中的步骤2），候选部分切割就可以表示为线段，其端点是内中轴的投影点，起点是投影点在凹角处（图4中的步骤3）。 我们将这种部分切割结果称为原始切割。 优先考虑人类更敏感的原始切割（步骤 4）。 提出了多种措施来量化人体敏感性，即突出强度、平坦度、扩张强度和延伸强度。 其中，切口的突出强度是最关键的指标，并在许多其他论文中使用[11, 36]。 它可以影响拼贴画的最终外观，定义为其长度与沿边界的相应弧长的比率。 特别是，突出强度控制着我们分解的细节水平。 突出强度大于阈值${\tau }_p$的切口被丢弃，如图5所示。 在我们论文中的所有示例中，${\tau }_p=0.75$。 在最后一步（步骤5）中，贪婪地选择候选切割，直到在每个凹角处实现凸性或选择所有候选切割。 最终分解结果如图4第5步所示。

图5： (a) 废弃切口之前，(b) 废弃具有较高突出强度的切口

我们当前应用程序中方法的目标是生成具有定义数量的单元的平衡且视觉上令人愉悦的布局。 借助 MAD，我们可以控制形状上明显的凸凹轮廓。 然而，要将内容多样、图像数量众多的图像集合拼贴在一起，MAD 本身不足以应对这些挑战。 因此，使用 MAD 作为预处理步骤来初始分解输入形状，然后我们寻求一种新颖的方法将分解的部分切片为令人满意的布局。 在接下来的部分中，我们将介绍应对这一挑战的方法。

4.3 形状感知切片

MAD得到的结果部分是凸多边形。 我们用术语补丁来称呼它们中的每一个。 我们通过提出一种在每个补丁上运行的新的形状感知切片方法来解决上述挑战。 令 $N_p$ 为补丁数，$N_I$ 为给定集合中的图像数。 假设$N_I>N_p$。 该方法旨在将 $N_p$ 划分为单元格 ($N_c$)，以便 $N_c=N_I$。 我们的早期实验表明，在大多数情况下$N_I\mathit{>>}{N}_p$。 然而，如果出现对比情况，合并相邻的补丁本身就足以产生合理的布局。

我们的切片方法受到平面设计策略[32]的启发。 这种经典的方法被引入基于切片结构和满二叉树的画布分区。 这种切片结构的目的是通过水平分割和垂直分割将矩形画布递归地分割成更小的矩形。 该策略随后被广泛用于在许多图像拼贴系统中生成布局[33,17,21,35]。

这里的挑战是我们设计当前的系统来处理各种不规则的形状和方向。 简单地应用切片结构算法[32]是不够的，如图6-(a)中的示例。 有些单元很小，有些单元不属于形状的一部分。 因此，我们的 SAS 的设计与现有技术[2,6,28]不同。 据观察，尽管画布可能具有各种形状和方向，但有一个直观的水平和垂直方向。 这些方向与我们在前面部分讨论的中轴概念相对相关。 因此，我们整合给定形状的中轴来构建二叉树，称为基于中轴的二叉切片树(MABST)。

我们利用$𝐗$来定义模拟矩形画布中水平和垂直方向的伪方向. 它们分别称为轴向和横向. 对于每个点$z\in 𝐗$，我们将中轴集合$M(𝐗)$中$z$的最近点定义为：

$$\mathrm{\Phi }(z,M(𝐗))=\underset{m\in M(𝐗)}{\arg \min }\Vert z-m\Vert$$ (4)

因此，$z$的$Axial$和$Crosswise$定义为：

• $Axial(z)$：中轴在$\mathrm{\Phi }\left(z\right)$处的切向量。 这类似于矩形情况下的水平切割。 实际上，任何一个切向量就足够了。

• $Crosswise(z)$：与轴向正交的向量。 这类似于垂直切割。

我们在图8-(a)中可视化伪方向。

图6： 生成布局的比较。 (a) 通过线性切片进行布局，(b) 和 (c) 通过我们的 SAS 算法进行布局。

一旦定义了伪方向，我们就为每个补丁初始化一个 MABST。 我们根据补丁的面积确定分配给某个补丁的图像数量$𝐒$。 给定一个带有一组补丁 $𝐏=\{p_1,\mathrm{\dots },p_{N_p}\}$ 的形状 $𝐗$，我们将补丁 $C_i$ 的 ${𝐒}_i$ 定义为：

$${𝐒}_i=\left[N_I\cdot \frac{Area(p_i)}{Area(𝐗)}\right],$$ (5)

其中 $[]$ 是最接近的整数函数的符号。

对于 MABST，每个叶子代表一个细胞；因此，叶子计数就是匹配 $S_i$ 的单元格数量。 形式上，MABST 是一种递归数据结构。 每个树节点$𝐓$，包含（1）切割方向${𝐃}_{𝐓}$（轴向切割$𝐀$和横向切割$𝐂$)的信息，（2 ) 对应的多边形 ${𝐆}_{𝐓}$，(3) 左子 ${𝔏}_{𝐓}$，以及 (4) 右子 ${\Re }_{𝐓}$。

除了叶子节点的数量之外，我们在初始化MABST时还考虑了树的平衡性。 显然，平衡树会产生大小均匀的单元，反之亦然。 大小不均匀的单元格可用于放置不太重要的图像，例如风景图像。 实际上，分裂命令从根节点传播到叶节点，并将叶节点分裂成两个新的叶节点。 我们从单个节点开始重复此操作 $S_i-1$ 次。 我们根据平衡(${\gamma }^b$)和不平衡(${\gamma }^u$)的概率选择一个分支来传播分裂命令。 ${\gamma }^b$是选择高度最小的分支，即从树的根节点到叶子节点的最长路径上的边数。 同时，${\gamma }^u$是选择高度最大的分支。 然而，我们并不总是希望 MABST 成为退化线性路径。 因此，以更大的概率（即，在我们的实验中，$70\%$)添加一些随机性来选择具有最大高度的分支。 该阶段MABST的两个例子如图7(a)所示。 到目前为止，MABST 尚未完全配置，即剪切方向和图像关联尚未确定。 将图像分配给叶节点的过程将在 4.4 节中讨论。 在4.5节中，我们将讨论如何确定每个节点的切割方向。

图7： 我们的布局生成过程的工作流程。

我们布局生成的核心是形状感知切片算法SAS。 SAS 将 MABST 映射到 2D 拼贴布局。 首先假设我们有一个完全配置的 MABST。 SAS递归地遍历每个节点$T$，并根据切割方向($𝐀$或$𝐂$)划分多边形${𝐆}_T$，借助函数分割多边形 DPG。 DPG 通过用一条穿过多边形质心的线将多边形分成两半，斜率由轴向或横向方向确定。 由于多边形是凸多边形，我们可以确定质心在多边形内部，并且结果恰好有两个多边形。 SAS 操作之后，我们只需从叶节点收集所有多边形作为最终布局。 SAS和DPG算法的伪代码分别在算法1和算法2中给出。 请注意，在SAS算法的第7行和第8行中，我们需要确定一个额外的参数，即两个子节点的顺序。 我们可以将多边形$p_1$分配给左孩子，将多边形$p_2$分配给右孩子，反之亦然。 这会产生两种不同的拼贴布局。 该决定也将在第 4.5 节中讨论。

1 Function SAS($T$, $M\mathit{}\mathrm{(}𝐗\mathrm{)}$):

Input : Tree node: $T$, Medial axis: $M(𝐗)$

2 if $T$ is not a leaf then

3 if $D_T$ is $A$ then

/* A split */

4 $p_1,p_2\leftarrow$DPG(${𝐆}_T$, $M\mathit{}\mathrm{(}𝐗\mathrm{)}$, $A$);

5

6 else

/* C split */

7 $p_1,p_2\leftarrow$DPG(${𝐆}_T$, $M\mathit{}\mathrm{(}𝐗\mathrm{)}$, $C$);

8

9 ${𝔏}_T$.$𝐆\leftarrow p_1$ ;

10 ${\Re }_T$.$𝐆\leftarrow p_2$;

11 SAS(${𝔏}_T$, $M\mathit{}\mathrm{(}𝐗\mathrm{)}$);

12 SAS(${\Re }_T$, $M\mathit{}\mathrm{(}𝐗\mathrm{)}$);

13

14

15

Algorithm 1 SAS function

(a)

(b)

图8： (a) 伪方向的可视化（黄色箭头），以及 (b) 寻找中心过程的可视化。 黑点位于中轴上。 它们的投影分别为 $v_1$、$v_2$、$v_3$ 和 $v_4$。 可以看出，中心、$v_3$和$v_4$的投影具有最大的Chord残差。

1 Function DPG($G$, $M\mathit{}\mathrm{(}𝐗\mathrm{)}$, $D$):

Input : Polygon: $G$, Medial axis: $M(𝐗)$, Cutting direction: $D$

Output : Two polygons $p_1$, $p_2$ result from the division

2 if $D$ is A then

3 $ct\leftarrow G.centroid$;

4 $slope\leftarrow Axial(ct)$;

5 $dividing\mathrm{\_}line\leftarrow$ a line pass through $ct$ with $slope$;

6 $p_1,p_2\leftarrow G$ divided by $dividing\mathrm{\_}line$;

7 return $p_1,p_2$

8 else

/* $D$ is C */

9 $ct\leftarrow G.centroid$;

10 $slope\leftarrow Crosswise(ct)$;

11 $dividing\mathrm{\_}line\leftarrow$ a line pass through $ct$ with $slope$;

12 $p_1,p_2\leftarrow G$ divided by $dividing\mathrm{\_}line$;

13 return $p_1,p_2$

14 end if

15

16

Algorithm 2 DPG function

我们在图6中展示了我们的 SAS 算法在两个示例形状（例如字符 C 和熊猫）中生成的两种布局。 我们可以看到，SAS 在字符 C 的形状上比经典切片算法表现得更好。特别是，熊猫是一个具有挑战性的形状，因为它具有较大的凸凹轮廓。 即便如此，SAS 仍然产生平衡且视觉上令人愉悦的布局。 特别是，生成的布局中的元素，即所谓的单元，被相对均匀地划分，并且特定区域（例如，耳朵或腿）被很好地切片。 更多结果和比较将在后面的实验结果部分展示。

到目前为止，我们已经介绍了 MABST 的概念以及从树到布局的映射。 $N_p$ MABST 被初始化，使得每个 MABST 都有 $S_i$ 叶节点。 在我们到达最终的切片树之前，我们需要考虑图像属性，即长宽比。 我们将在 4.4 节中讨论如何将图像分配给 MABST。

4.4 图像分配

当我们将图像分配给 MABST 的叶子时，我们考虑两个因素：（1）树中位置越高的叶子节点越大。 重要性得分较高的图像应分配给较大的单元格，这些单元格更加突出。 （2）重要性得分较高的图像应放置在靠近形状中心的位置，以吸引人类的注意力。 比如熊猫造型的耳朵和脚就不那么突出了。 我们通过根据到形状中心的反距离对 MABST 进行排名来实现这个想法。

直观上，树中越高的叶节点越大。 但是要定义哪个节点更高，我们不能直接使用树节点的高度定义，因为每个叶节点的高度为零。 相反，我们定义一个称为节点elevation的量，它被定义为整个树的高度减去该节点的深度。 图7(a)中的数字显示了两棵树中节点的高程。

比较所有 MABST 中叶节点的高程。 我们进一步根据相应斑块到中心的距离对具有相同高程的叶节点进行排序。 确定任意形状的中心并非易事。 例如，形状的质心不一定位于形状内部。 因此，我们采用Chord残差[20]来确定任意形状的中心。 给定形状内的一条线段，连接形状边界$𝐁$上的两点$v_i$和$v_j$（如图8 -(b))，它们的和弦残差公式为：

$$CR(v_i,v_j)=dis{t}^B(v_i,v_j)-Length(\overline{v_i{v}_j}),$$ (6)

其中$dis{t}^B$表示沿边界$𝐁$的距离。 因此，给定形状的中轴，形状的中心公式为：

$$center=\underset{m\in M(X)}{\arg \max }CR(v_i,v_j)\mid v_i,v_j\in \pi (m),$$ (7)

其中 $\pi (m)$ 是投影集，这在前面的 4.2 节中已经讨论过。 我们注意到，当我们沿着中轴远离中心时，弦残差会减少，如图8-(b)所示。

某个斑块$\mathrm{𝐏𝐏}$的突出度（以及相应的MABST的突出度）可以用到中心的距离的倒数来表达。 距离项是两个距离之和： (1) 面片的质心 $p_i$，用 $p_i^e$ 表示，它在中轴 $\mathrm{\Phi }(p_i^e)$ 上的投影， (2) 沿中轴从 center 到 $\mathrm{\Phi }(p_i^e)$ 的距离。 正式写为：

$$\mathrm{𝐏𝐏}(p_i)=\frac{1}{Length(\overline{p_i^e\mathrm{\Phi }(p_i^e)})+dis{t}^{M(X)}(center,\mathrm{\Phi }(p_i^e)},$$ (8)

其中$dis{t}^{M(X)}$表示沿形状$𝐗$的中轴的距离； $\mathrm{\Phi }(.)$ 是方程（4）中的函数。

给定图像重要性等级$R^m$，我们贪婪地从所有MABST中选择一个海拔最高的叶节点，并将最重要的图像分配给它。 我们通过补丁突出$\mathrm{𝐏𝐏}$打破平局。 如果标高和斑块突出度相等，则图像按从左到右的顺序分配。 这将导致相似重要性的图像被放置在一起，从而可以提高信息量。 分配图像的MABST如图7(b)所示。

4.5 最优树搜索

我们现在找到了切片树的最佳配置。 树$T$的配置$𝒪$指两点：（1）切割方向${𝐃}_{𝐢}$；（2）$S_T-1$内部节点的两个子节点${𝐊}_{𝐢}$的顺序，其中$S_T$是$T$的叶节点数。我们的目标是找到一种布局结构，使所有图像的最大突出框 $S{b}^{*}$ 的总面积最大。 该问题如图9所示。 可以看出，图9中的右下布局具有最大的目标值，因为两个显着框被最大化。 形式上，优化步骤确定最佳配置${𝒪}^{*}$

$${𝒪}^{*}=\underset{{𝐃}_{𝐢},{𝐊}_{𝐢}}{\arg \max }{E}_{area},$$ (9)

在哪里

$$E_{area}=\sum _{i=1}^{S_T}Area(S{b}_i^{*})$$ (10)

图9： 搜索树的最佳配置的过程。 树的四个实例与相应的布局一起显示。 树节点上的$A$和$C$表示切割方向，我们使用较粗的边来表示较大的多边形。

请注意，查找 $S{b}_i^{*}$ 本身就是一个优化问题。 $S{b}_i^{*}$定义为完全位于凸多边形内部且长宽比与$S{b}_i$相同的最大尺寸矩形，如图9所示>。 通过将凸多边形表示为半平面的交集，可以使用线性规划有效地解决此问题。

为了找到最佳的树配置${𝒪}^{*}$，我们需要遍历所有可能的配置并找到具有最大$E_{area}$的最佳决策变量集。 然而，对于$S$-leaf-node树，有$4^{S-1}$种方式来配置树，因为每个非叶节点（内部节点）有四种可能的配置（图9)。 换句话说，搜索空间随着叶节点的数量呈指数增长，即使对于适度的 $S$ 也会变得棘手。

我们观察到树中较高的节点对应于最终布局中较粗的切割。 这种较粗的切割对叶节点的最终形状的贡献较小，特别是对于每个深叶节点。 例如，当我们打算在该形状内放入 50 个单元格时，我们为第一次切割选择轴向切割还是横向切割并不重要。 利用这一观察结果，我们提出了一种简单的策略，通过预先配置海拔高于 ${\tau }_e$ 的内部节点来减少搜索空间，其中 ${\tau }_e$ 可根据权衡进行调整质量和速度。 显然，${\tau }_e$ 越高，越接近原始的暴力搜索，反之亦然。

为了预先配置内部节点的切割方向，我们沿轴向和横向轴投影与该节点关联的多边形，并比较它们在这两个方向上的尺寸。 如果轴向轴的尺寸较大，则使用$𝐂$切割。 否则，使用 $𝐀$ 剪切。 这类似于在矩形情况下用水平线分割高矩形以及用垂直线分割宽矩形。 这可以防止生成的矩形具有极端的纵横比，这可能不利于单元的质量。 图10表明，使用该策略可以大大加快搜索时间并取得良好的目标值。 从实验来看，设置${\tau }_e=3$可以在所有叶节点数上一致达到90%以上的最优结果，这比完全随机配置（图10 本文后半部分的结果均采用此设置。

三角罚球。 使用 SAS 生成的单元通常是四边形（边界上的单元除外）。 但有时会出现三角形，这些三角形细胞往往会从其他形状中脱颖而出，这会对细胞的均匀性产生负面影响。 因此，我们在目标函数中添加了一个三角形惩罚项 $p_{triangle}$，以阻止优化函数选择三角形单元。 我们在实验中凭经验将此惩罚设置为 0.8，以获得任意输入形状的平衡布局。

(11)

我们通过 $p_{triangle}$ 来惩罚目标函数中的面积项：

$$E_{area}=\sum _{i=1}^{S_T}(Area(S{b}_i^{*})\cdot p_{triangle}(𝐆)),$$ (12)

其中 $𝐆$ 是与该叶节点关联的多边形。

对于时间复杂度来说，暴力搜索是$O(4^n)$。 使用我们的策略，我们可以将其减少到$O(n)$，图10中的线性趋势验证了这一点。 例如，如果我们有一棵八叶树，并且设置了${\tau }_e=1$，那么我们只需要配置紧邻叶子节点之上的$8/2$内部节点。 每个内部节点有 4 个配置。 由于这四个节点是独立的，因此总搜索空间为 $4^1\cdot 8/2$。 对于 $n$ 叶节点树，搜索空间为 $4^1\cdot n/2$。 对于${\tau }_e=2$，数字是$4^3\cdot n/4$。 一般来说，搜索空间的大小为$4^{2^{{\tau }_e}-1}\cdot n/2^{{\tau }_e}$，与$n$呈线性关系。

图10： 不同搜索策略的执行时间和解决方案质量的权衡。 最优表示使用暴力搜索。

4.6细胞填充

图11： 优化结果：(a) 集合中带有检测到的边界框 $Sb$ 的图像（蓝色矩形）； (b) 估计单元格中的框 $T$ 以使 $Sb$ 适合 $T$； (c) 通过扭曲填充单元格。 (d) 和 (e) 是未经优化的失败结果：图像中的对象被剪切以适合单元格 (d)；无法将定制的单元格分配给图像 (e)。

本次会议的目标是用分配的图像填充单元格，同时保留估计框中图像的主要主题。 例如，在图11中，变形后，(a)中的猫仍然与(c)中的猫相似，但(c)中猫的邻近区域被变形以填充细胞。 由于优化已经成功地找到了最适合图像的单元格，并最大化了单元格上显着框 $T_i$ 的面积，因此轻量级策略可以解决此处填充单元格的问题。 我们考虑两种情况：(1) 单元格被图像内容填充，(2) 相反的情况。 对于第一种情况，我们简单地沿着单元格的边界裁剪图像，如图12-(c)所示。 对于第二种情况，我们采用仿射变换的变形将图像内容填充到单元格的其余部分。 我们详细阐述如下。

我们将覆盖图像$𝐈$的矩形表示为具有四个顶点${𝐕}_1,{𝐕}_2,{𝐕}_3,{𝐕}_4$的$𝐃$；图像 $𝐈$ 有一个边界框 $S{b}_i=[b{x}_1,b{y}_1,b{x}_2,b{y}_2]$。 我们为$S{b}_i$和$𝐃$的边形成的凸包生成德劳内三角剖分，见图12-(a)。 我们将这个三角形集合表示为${𝐀}^i=\{a_k\},k=1,\mathrm{\dots },8$。 在 $𝐈$ 的相应单元 $C$ 中，我们构建了一个矩形 $𝐇$（有四个顶点 ${𝐇}_1,{𝐇}_2,{𝐇}_3,{𝐇}_4$），该矩形根据凸顶点覆盖 $C$（图 12-(b)）。 类似地，我们生成由 $T$ 和 $𝐇$ 的边缘形成的凸包的 delaunay 三角剖分。 我们将这个三角形集合表示为${𝐀}^c=\{a{c}_k\}$。 为了将图像填充到单元格中，我们的目标是将 $a_k$ 扭曲为 $a{c}_k$。 理论上，像素$p^{\prime }\in a{c}_k$的纹理可以表述为：

$$p^{\prime }(x^{\prime },y^{\prime })=\zeta (p(x,y)),$$ (13)

其中$p(x,y)\in a_k$,$\zeta (.)$ 是仿射变换的扭曲函数，将$a_k$扭曲为$a{c}_k$。

图 12： 充填细胞两例。 将 (a) 中的三角形 $a_k$ 扭曲为 (b) 中的 $a{c}_k$。 (c) 是裁剪的示例情况，其中边界框位于单元格内，并且单元格内不存在任何空白空间。

5实验结果

5.1 实验参数

实验数据 在我们的实验中，我们收集了 73 个不同的形状和 6 个图像集合。 这些形状来自 MPEG-7 核心实验 CE-Shape-1 测试集 [13]，这是形状研究中常用的数据集 [3, 34, 9]。 MPEG-7 包含属于 70 个类别的 1,400 个形状。 由于每个类别中的形状相似，因此我们从每个类别中选择一个形状作为测试形状。 不适合作为拼贴轮廓的形状，例如含有太多破碎或小碎片的被去除。 由于 MPEG-7 数据集中的大多数形状不美观且不直观，因此我们另外考虑了 11 种常用形状，例如狗和汽车。 补充材料中提供了 73 种形状。 对于图像收集，我们使用Yu等人[35]提出的AIC数据集，该数据集拥有超过500个图像集合，超过18,000张图像。 该数据集中每个集合的大小范围为 10 到 100。 在 AIC 中，每张图像都与一个类别和一个显着掩模相关联，这对于进行我们的实验很有用。 我们仅使用 AIC 数据集的一小部分，该数据集也在补充材料中列出。

实现细节图像首先由[22]和[30]分析，在NVIDIA GTX1080Ti上每张图像通常需要一秒。 我们系统的其余部分运行在具有 32GB RAM 的 Intel Core i7-8700 上。 时间统计如图13所示。 生成一幅拼贴画的总体执行时间范围为 10 到 20 秒，具体取决于图像集合的大小。 我们的 SAS 和优化步骤需要不到六秒的时间，并且随着输入图像的数量呈线性增长。 另外两个步骤，即 MAD 和细胞填充总共需要大约 10 秒，并且对于所有图像计数保持（接近）恒定。 要访问我们的结果和数据集，请访问我们的项目网站 http://graphics.csie.ncku.edu.tw/shapedimagecollage/。

图 13： 我们方法的各个步骤的执行时间，包括 MAD、SAS 和优化以及单元格填充。

5.2 我们的结果和讨论

为了评估我们的方法，我们在图21中展示了生成的拼贴结果。 其中一些形状已用于先前的研究和商业应用。 然而，在我们的研究中，通过我们的 SAS 算法生成布局，可以在平衡且视觉上令人愉悦的拼贴画中生成吸引人的结果。 此外，通过我们的拼贴策略，即在优化时同时考虑图像内容和输入形状，可以在细胞中很好地捕获和保存图像的主题。 我们将在接下来的小节中直观地展示我们的系统与之前工作结果的竞争能力。

布局均衡。 这项工作取得吸引人结果的有趣因素之一是我们提出的 SAS 算法。 SAS 在各个方面都表现出色。 首先，生成具有挑战性形状的逼真布局：让我们以 Panda（图14)为例。 先前的工作将形状线性地划分为矩形和正方形，这导致边界处的伪影，即边界单元以其他单元的一小部分的形式出现。 这就是边界周围存在一些无用的微小单元的原因，因为它们太小而无法拼贴有意义的内容（我们在图14-(a)中的红色矩形中突出显示了这种现象）。 相反，我们的 SAS 算法在对形状进行切片时会考虑多边形的凸性和凹性；因此，生成的布局更加真实并消除了无用的单元。 例如，熊猫的耳朵被很好地切片并且不会太小而无法可视化该细胞中的内容。 其次，单元格的样式在整个布局中保持一致。 由于MAD和SAS都是基于中轴，因此它们具有一致的分区风格。 相反，如果使用不了解中轴的任何其他镶嵌技术，则会出现冲突的单元格样式。 例如，图15-(a)是MAD后应用质心Voronoi曲面细分[7]生成的单元。 可以明显看出两个不同的过程，即 MAD 的线性划分风格和 Voronoi 细分的蜂窝风格，而 SAS 与 MAD 无缝集成，如 15-(b) 所示。 第三，可以精确控制细胞数量并与集合的精确体积相匹配。 这方面归功于在构造MABST时了解每个明确定义的区域中的面积。 如果没有清楚地了解形状，以前的方法会使用无限数量的图像来填充画布。 这就是为什么在之前的工作中生成的拼贴图中存在多次出现的多个图像（图14-(a)中的黄色矩形）。 相反，我们生成的布局中的单元格数量等于集合的体积；因此，拼贴画可以充分可视化给定收藏的故事。

图 14： 在 Panda 布局上可视化线性切片 (a) 和我们的 SAS 算法 (b) 生成的布局的拼贴结果差异。

图 15： (a) 应用质心 Voronoid 细分代替 SAS。 (b) 使用 SAS。

语义拼贴。 我们提出的方案与先前的工作和商业应用之间的主要区别在于图像内容和布局结构之间关系的整合。 这使我们的系统能够以和谐且视觉上令人愉悦的方式生成结果。 当吸引人类焦点的区域由对集合具有更高兴趣的图像拼贴而成时，展示了平衡和视觉上令人愉悦的方面。 如图14所示，现有方法的结果未能将集合的语义与布局联系起来。 也就是说，以黄色突出显示的区域是由以背景为主的图像拼贴而成，而具有主要对象的图像则放置在边界处。 因此，图像中的重要对象被裁剪在这些单元格中（以蓝色矩形突出显示）。 相比之下，在我们的结果中，较高兴趣的图像被拼贴在吸引人类焦点的区域，而风景场景则放置在边界区域。

适应各种形状、细胞数量和尺寸的图像采集。 能够一致地处理任意形状是具有挑战性的。 例如，Voronoi 曲面细分在凹面形状上的定义不明确。 与此形成鲜明对比的是，借助 MAD，我们的方法可以将形状分解为凸部分。 另一个影响因素是我们的树切片结构。 我们的树切片结构允许我们灵活地控制单元的数量和每个单元的相对大小。 这方面解释了为什么基于树的方法是图像拼贴研究的标准。 然而，不同之处在于我们将其推广到不规则画布。 图20展示了这些有趣的结果。 特别是，在相同的输入形状上，我们可以生成均匀大小和不均匀大小的布局，同时保持所得拼贴的平衡。 或者，同样在这种形状上，我们可以制作具有不同大小的集合的吸引人的拼贴画（例如，本例中使用了 15 张图像和 25 张图像。）

参数设置的效果。 我们布局的平衡是影响最终拼贴结果的方面之一。 为了将给定形状划分为平衡布局，我们的方案集成了两种算法：MAD 和 SAS。 对这些算法中的不同参数敏感是我们在配置系统时考虑的问题。 更具体地说，MAD 中的突出强度阈值和 SAS 中的 ${\gamma }^u$ 概率的变化会对结果产生影响。 尽管对 MAD 和 SAS 的影响都很小，但这些参数的变化对我们的布局生成有一些明显的影响。 图16-(a)是我们的SAS中不平衡${\gamma }^u$的结果。 图16-(b)是MAD中的突出强度阈值$\tau$从0.75增加到0.9时的结果，允许分解更多细节。 可以看到喇叭细节更加明显（箭头所指）。 然而，对于具有大量细节的形状，例如树叶，${\tau }_p$ 应设置得较低，以避免过多的噪音。 在图 16-(c) 中，${\gamma }^u$（在 SAS 中）的概率从 70% 增加到 90%，从而在单元尺寸上产生更高的对比度，即在中间和微小的细胞用红色突出显示。 不过，不鼓励用户将 ${\gamma }^u$ 设置为高于 90%，因为这会创建太小而无法看到的单元格。 最后，在选择这些参数时，用户还可以考虑图像集合的重要性分布。 例如，如果图像集合中有大量不太重要的图像，我们可以使用为这些图像创建较小单元的参数，如前所述。

图 16： (a) 我们在鹿形状上使用 Unbalanced ${\gamma }^u$ 得到的结果。 (b) 将突出强度阈值$\tau$增加到0.9时的结果。 (c) 将 ${\gamma }^u$ 概率从 70% 增加到 90%。

5.3消融研究

验证MAD的有效性。 我们使用 MAD 作为处理复杂形状的第一步。 我们在不使用 MAD 的情况下测试我们的系统。 结果如图17所示。 可以看到，许多对象都被严重裁剪（以红色突出显示），尤其是在凹角处。 此外，如果没有 MAD，我们就无法精确估计每个区域有多少张图像。 结果是细胞最终可能具有非常不同的大小。 以绿色突出显示的单元格比其他较大的单元格小得多。

图 17： (a) 没有 MAD 的结果。 (b) 我们的 MAD 结果。

验证 SAS 中的轴向和横向方向。 SAS 的主要特征之一是使用中轴。 我们测试 SAS 时没有使用轴向和横向，而是使用水平和垂直方向。 使用平衡策略，其他一切保持不变。 差异如图18所示。 如果不使用Axial和Crosswise方向，算法很难找到最直观的方式来切片C形和勺形，导致细胞大小不太均匀。 此外，它具有与 Voronoi 曲面细分相同的缺点，即不同的分区样式。 例如，在图18-(b)中，有一些切口从其他切口中脱颖而出，因为它们不在垂直和水平方向上（由箭头指出）。

图 18： (a) 在 C 形上使用轴向和横向方向。 (b) 在 C 形上不使用轴向和横向方向。 (c) 在 MPEF7 数据集中的勺子形状上使用轴向和横向方向。 (d) 不使用 MPEF7 数据集中勺子形状的轴向和横向方向。

图像分配和优化 图像分配步骤和优化步骤对于我们结果的最终质量至关重要。 为了分析它们对最终结果的影响，我们分别删除它们并将它们的结果与完整配置中的结果进行比较。 可视化如图19所示。 在图19(b)中，我们将图像随机分配给叶节点，而不考虑重要性。 不太重要的图像可能会放置在更突出的位置，在这种情况下，背景图像放置在中心（由黑色箭头指出）。 我们的优化有两个目标：显着性最大化和三角形惩罚。 显着性最大化项同时创建并匹配最适合受试者的细胞。 我们在图19(c)中创建了未经优化的结果（即随机配置MABST）。 有大量形状怪异的单元格（以红色突出显示），很难放置物体。 此外，图19(c)中的主要对象显得较小。 这意味着我们无法找到定制的细胞。 与图19(d)中的结果相比，我们的方法能够抑制原本出现在中间的三角形单元（以红色突出显示）。 请注意，我们的方法并不总是能够完全删除三角形。 对于像心形这样具有弯曲中轴的形状，有时需要三角形。 然而，我们的方法能够减少三角形的数量和大小，或者至少将三角形结构推向边界。

(a) Result with all the components

(b) w/o image assignment

(c) w/o saliency maximization

(d) w/o triangle penalty

图 19： 消融结果的视觉比较。

5.4评估

5.4.1定性评估

在这里，我们通过将我们的结果与四个基线进行视觉比较来定性评估结果。 第一个基线 TB[8] 是与我们最相关的工作。 第二种方法是广泛使用的商业软件Shape Collage (SHP)[4]。 由于图像拼贴中的大多数作品都是矩形布局，因此我们与当前最先进的 SoftCollage(SC)[35] 进行比较。 SC仅适用于矩形布局；我们进一步通过将形状掩模应用于SC（SC+掩模）进行实验。 图21概述了这种比较。 补充材料中提供了更多比较。

(a) Even-sized layout

(b) Uneven-sized layout

(c) Collage of 15 images

(d) Collage of 25 images

图 20： 展示了我们的方法在布局设计和图像集合的不同尺寸方面具有灵活性。

图 21： 比较不同方法产生的结果。 输入的形状是树、婴儿、情侣和船，由黑色轮廓表示。

将我们的结果与 TB 的[8]进行比较，TB 还解决了 ICAS 问题。 图像首先通过双曲投影嵌入到 2D 画布中，以保持图像相关性。 然后，他们逐步调整图像位置以使其符合目标形状。 然而，调整过程是局部完成的，并没有考虑整体形状。 因此，他们的方法仅适用于类似于圆形的形状。 从示例中可以看出，图 21 中的树形状比其他树形状效果更好。 此外，他们的方法仅确保每个图像的中心都移动到形状内部。 如果图像很小，这个假设就很有效。 但在图像较大的情况下，图像的大部分可能位于目标区域之外，例如图21中，婴儿的手或夫妇的脚。 这给我们识别形状带来了困难。 相比之下，我们很容易识别结果的形状。

SHP [4]是一种流行的图像拼贴软件，在多篇论文[35,21,8]中用作基线模型。 SHP 与 TB 的不同之处在于它允许更多图像与图像旋转重叠。 它可以提高某些部位的形状精度，例如婴儿的头部或情侣形状中女人的头发。 然而，SHP 有更多的空白空间和图像重叠，使其无法有效地可视化集合中的整个故事。 与我们的结果相比，SHP 具有与 TB 类似的缺点，即对象超出边界。 此外，SHP 无法准确估计每个区域中有多少图像，例如情侣造型中男方的腿没有形象。 同时，第一列中显示的结果表明，我们的方法在控制每个区域的图像数量方面优于比较方法。

矩形图像拼贴的优点是保留图像的完整内容。 最先进的 SC 在保留每张图像的原始长宽比方面做得很好。 然而，与异形拼贴相比，矩形拼贴缺乏多样性，例如图21-SC中的四个示例具有相似的视觉结构，仅图像内容不同。 相比之下，我们的结果更有趣，正如我们将在用户研究中展示的那样，人们认为我们的结果更美观。

在 SC+Mask 的情况下，结果会受到我们在上一节中提到的边界单元的缺点的影响。 我们可以看到边界处的几个单元格，其中图像中的重要对象几乎被剪切掉，甚至没有出现在拼贴画中。 因为 SC+Mask 不像我们的方法那样考虑形状结构，所以它会生成不自然的切口，例如树中间的垂直裂缝或超出婴儿头部的大图像。

总之，我们的方法在表示形状的同时保留图像集合的内容的能力方面优于比较方法。 图像以视觉上令人愉悦的方式布局。 所有这些特性都极大地增强了用户在观看我们的拼贴画时的观看体验。

5.4.2定量评价

除了定性比较之外，我们还定量评估我们提出的方法。 我们使用三种基线方法 TB、SHP 和 SC+Mask 生成多个图像拼贴。 我们在这个实验中不考虑 SC，因为比较不同布局（即形状布局和矩形布局）上的一些指标是不公平的。 这些竞争对手生成的结果的质量是根据图像拼贴文献中通常考虑的五个指标来衡量的，包括最先进的 SoftCollage [35]。 其中，非重叠约束$M_o$、相关性保持$M_n$和显着性损失$M_s$与[35]相同。 紧凑性$M_c$ 类似，但泛化为不规则形状。 我们进一步提出了一个新的指标：显着区域$M_a$。 五个指标描述如下：

• 显着区。 该指标衡量最大化画布上显着对象的拼贴能力，其定义为显着对象覆盖的总形状的比例。

  $$M_a=\frac{|{\bigcup }_i{S}_i|}{P_{𝐗}},$$ (14)

  . 其中 ${\bigcup }_i{S}_i$ 是通过将拼贴中的每个图像替换为相应的显着性掩模而获得的拼贴掩模。 $S_i$是图像$i$的显着性掩模。 $|.|$ 表示掩模的显着区域。 $P_{𝐗}$ 是输入形状的像素数。

• 紧凑性。 紧凑的拼贴画通过最大限度地减少空白来减少空间浪费。 我们将紧致度表述为：

  $$M_c=\frac{P_w}{P_{𝐗}},$$ (15)

  其中 $P_w$ 是空白区域的像素数。

• 非重叠约束。 图像重叠降低了拼贴画的美观性和信息量。 重叠可以计算为

  $$M_o=\frac{P_o}{P_{𝐗}},$$ (16)

  其中 $P_o$ 是任意两个图像的相交像素之和。

• 相关性保存。 将相关图像放在一起可以提高拼贴画的信息量。 该指标表示为：

  $$M_n=\frac{1}{N}\sum _i\Vert (L_i-L_{ci})\Vert ,$$ (17)

  其中$L_i$是图像$i$在拼贴中的位置，$L_{ci}$是类别$ci$的质心位置图像$i$，在AIC数据集中提供。 对于这个指标来说，越低越好。 所有位置坐标均按输入形状的宽度和高度进行标准化。

• 显着性损失。 该指标衡量保留图像中显着区域的能力，定义为

  $$M_s=1-\frac{|{\bigcup }_i{S}_i|}{{\sum }_i|S_i|}.$$ (18)

表格1： 定量评估指标

Method	$M_a$	$M_c$	$M_o$	$M_n$	$M_s$
TB[8]	0.08	0.23	0.01	0.12	0
SHP[4]	0.12	0.29	0.09	0.15	0.06
SC+Mask	0.19	0	0	0.13	0.52
Ours	0.32	0	0	0.17	0

表1显示了上述评价指标的统计情况。 对于第一个指标 $M_a$ 越高越好。 对于所有其他指标，越低越好。 首先要注意的是，我们的方法在第一个指标中实现了较高值，在其他三个指标中实现了最低值，即 $M_c$、$M_o$、$M_s$、同时表现与 $M_n$ 中的竞争对手类似。 较大的显着区域$M_a$意味着我们的方法更有效地使用成形空间。 更好的紧凑性（较低的 $M_c$)反映了我们真实表示输入形状的主要目标。 虽然 SC+Mask 在这个指标上也达到了零，但它远远落后于我们在 $M_s$ 中的方法，因为它最初不是为形状拼贴设计的。 对于非重叠约束$M_o$，SHP 表现最差，因为 SHP 允许重叠。 对于相关性保留 $M_n$，TB 和 SC+Mask 击败了我们的方法和 SHP，因为它们包含图像特征提取组件。 不过，差别并不大。 综上所述，三种基线方法都有明显的缺点。 对于 TB 和 SHP，弱点是紧凑性$M_c$。 对于SC+Mask，弱点是显着性损失$M_s$。 这表明我们的方法是这四种方法中最好的。

5.5用户研究

我们进行了两项用户研究来评估我们结果的有效性。 一是衡量用户对不同方法的偏好，二是衡量我们呈现信息的方法的有效性。 使用 16 个图像集，图像数量从 15 到 40 不等，以及 16 种不同的形状。 对于每个图像集合和形状，我们使用我们的方法和四种基线方法（即 TB、SHP、SC 和 SC+Mask）生成结果。 我们总共招募了 39 名用户来进行用户研究。 他们具有不同的年龄（年龄范围21-31岁）和背景（其中13人具有图形相关背景）。 在第一个用户研究中，要求用户在使用五种方法中的两种生成的两个结果之间进行选择。 并行评价的结果如表2所示。 在并行评估中，我们的方法分别优于所有比较方法 84%、83%、60% 和 43%。 统计结果显示，我们的结果得到了用户的大力支持。 这表明我们的方法可以引起广大公众用户的兴趣。 评估结果显示在补充文件的图5中。 在分析评估结果时，我们发现示例 R5 和 R11 比其他示例获得的票数相对较少。 这是因为这些形状生成的布局由一些狭窄的区域组成。 因此，它们无法受到用户的青睐。 在第二个用户研究中，向用户提供拼贴结果以及该拼贴中出现的四张显着物体的图片。 我们测量用户找到拼贴画中所有四个对象的总时间。 我们的结果在五种方法中检索时间第二短，如表 3 所示。 SC+Mask 的时间最短，因为与其他方法相比，它需要检查的对象要少得多。 我们可以得出结论，我们的方法可以有效地呈现数据，从而使用户可以轻松地消费信息。

表2： 并排用户评估。

	Wins	Equally Good	Losses	$\mathrm{\Delta }$
Ours v.s. TB[8]	91%	2%	7%	84%
Ours v.s. SHP[4]	90%	3%	7%	83%
Ours v.s. SC[35]	77%	6%	17%	60%
Ours v.s. SC+Mask	69%	5%	26%	43%

$\mathrm{\Delta }$ denotes the difference of the win rate and the loss rate. Higher is better.

表3： 信息传达测试。

	Ours	TB[8]	SHP[4]	SC[35]	SC+Mask
Time (s)	18.15	20.03	22.25	18.47	13.40

5.6限制

我们提出了一个系统，可以将各种图像集合拼贴成不同的形状。 然而，对于具有非常长和狭窄区域的形状（如图22-(a）所示），我们的方法可以工作，但结果的视觉质量不太理想。 特别是甲虫腿中的图像内容无法识别。 这源于我们的问题表述。 不同的表述可能更好地处理这种情况，例如拼贴在甲虫形状的补充上。 当图像集合包含风景照片时，会出现另一个限制，我们的方法可能表现不佳（如图22-(b)所示）。 目前，我们的方法采用[22]中介绍的现成的显着目标检测方法来检测图像中的主体。 在风景照片中，斑块的显着值差异很小。 因此，我们的优化方案可能无法估计定制的单元格和目标框来拼贴此类照片。

图 22： 我们系统的局限性的两个例子。 在（a）中，甲虫形状由多个狭窄区域组成。 这会导致图像变小（以红色突出显示）。 在（b）中，风景照片的数量在给定的集合中占主导地位。 我们可能无法准确分析此类照片的主题。 因此，优化步骤可能无法估计正确的单元格和单元格中放置此类风景照片的框。 这就是原因，多个图像的场景被裁剪（以黄色突出显示）。 这最终会损害最终拼贴画的语义和视觉上令人愉悦的因素。

6结论

在本文中，我们介绍了一种以中轴为中心的统一ICAS算法。 该算法包括新颖的形状感知切片算法和最佳拼贴搜索策略。 我们证明所提出的切片方法对于平衡不规则形状上的图像拼贴的布局特别有用。 这使我们的系统能够将图像集合与灵活多样的形状进行拼贴。 此外，通过分析集合中的内容和布局结构之间的相关性，所提出的布局优化可以更好地提供拼贴画。 我们的结果和评估表明，所提出的拼贴方案大大优于先前的工作，并克服了现有商业应用中的缺点。 未来，我们计划研究此类技术来评估风景照片中的语义，以提高优化的准确性，从而提高生成结果的视觉质量。 此外，我们可以考虑针对具有狭长区域的形状使用不同的可视化技术。