面向数字印花图像的重复模式发现方法

王 爽 袁苇航

1(江苏经贸职业技术学院 江苏 南京 211168)2(南京大学计算机软件新技术国家重点实验室 江苏 南京 210046)

0 引 言

当前，数码印花作为一种新型的印花方式，凭借其效率高、打样成本低、印制效果好、污染少等优点，越来越能够满足印花消费市场中日趋多样的需求。但是，在数码印花的实际生产过程中，矢量印花图样的设计主要通过艺术家设计或者人工抠图的方式完成，存在成本高、周期慢等问题，制约了数码印花企业生产能力提升。因此，从大量成型印花图像中自动发现满足设计意图的印花图样，并合成提取印花图样，形成新的印花图像，能够大幅度简化印花图像的创作和设计过程，达到为印花企业个性化印染降低设计成本的目的。

本文主要讨论采用重复模式发现的方法从印花图像中自动识别和提取印花图样，尤其是种类和大小分布不均，识别和提取困难较大的印花图样。

已有的重复模式方法在处理框架上主要分为两类。第一类从重复模式的定义出发，利用模式内容的一致性推理重复模式。例如：Liu等[1]将重复模式表示为低层特征点的空间组合，并用贪心的随机自适应搜索对图像的重复模式统一表示进行优化，该方法能够处理非结构性的重复模式空间排列形式，但对于多个对象实例组成的重复模式效率太低。Spinello等[2]根据低层兴趣点和形状特征学习字典，从而分析模式内容的重复性，并用条件随机场推理重复模式的空间排列结构。文献[3-6]通过在图像中采样高层图像块并进行仿射不变的内容一致性分析，检测内容相似的图像块作为重复模式，并基于结构完全场生成重复模式的空间排列结构。这些方法虽然也对检测到的重复模式进行空间分布的推理和发现，但在原理上它们只是将其作为一个后处理过程，难以满足印花图像中多种类型实例检测的需求。

第二类重复模式发现方法从模式的空间分布出发，利用重复模式空间结构的规则性发现重复模式，由于人造图像中重复模式的空间分布结构一般都为二维晶格结构，所以本文只比较基于晶格模型的重复模式发现方法。Schindler等[7]通过随机选取模式基元并建立晶格模型参数候选，通过投票机制确定晶格结构模型。文献[8-11]为了提高对于图像视角变换或失真引起的晶格结构的非刚性形变的鲁棒性，在初始的晶格模型基础上用马尔可夫随机场进行重复模式的优化。这类方法通过模式空间分布的规则性推理模式，虽然可以解决第一类方法中无法解决的多类别问题，但对于模式内容较为复杂的情况，比如出现不同大小的同种类型的对象时，会陷入局部最优，无法满足印花图像的多尺度需求，因此不适用于印花图像的重复模式发现。

为了解决印花图像的多类型多尺度问题，本文提出了针对数字印花图像的重复模式发现方法，将印花图像表示为一个属性图，并将重复模式表示为属性图上特定粒度的子图结构。在建模的基础上，设计了获取对象重复模式的整体流程，通过结构推理和对象内容聚类来分析对象的尺度与类别，再通过图像建模更新对象的空间结构，最后利用重复性空间关系分析得到空间一致性对象，从而生成印花图样。实验验证了本文方法在印花图像集上的有效性，并从定性和定量两方面显示了对比其他方法的优势。

1 重复模式建模

重复模式的宏观定义为包含了图像完整重复性元素的最小粒度对象组合，其中粒度是重复模式的尺度在具体的对象层面上的对应。完整重复性元素是指重复模式的尺度必须包含重复性对象和重复性对象空间分布，因此基于重复模式可以重建印花图像。印花图像间重复模式粒度存在较大差异，主要有两种可能情况：1)单个对象，即重复模式的尺度是前景对象；2)多个对象以特定几何结构的分布，即重复模式的尺度是多个对象实例的空间组合，并且多个对象实例可能属于相同类别但有不同状态，也可能属于多个类别。印花图像的重复模式进行形式化表示，并对模式之间重复性的度量方式进行研究，使其能够统一表示不同类别、尺度、状态的对象所组成的不同粒度重复模式。

1.1 模式表示

本文采用一个有结构的属性图来表示印花图像中的全局对象信息，如图1所示。对于图像i，建立属性图Gi=(Vi,Ei)，对于Vi中的每个节点vj，其属性代表该节点对应的对象j的中心坐标。若两节点在图像空间相邻，则用一条边连接，边集Ei={eab:(va,vb,θab,dab),∀a,b∈Pi,a≠b}，对于Ei中的每条边eab，其属性代表它将顶点va和vb相连，在图像空间由顶点va到vb的角度方向为θab，并且长度为dab。由于构成印花图像的印花图样中组成元素分布均匀的特性，每个对象实例邻接的对象实例在数量和几何拓扑结构上一般也都是相似的。

图1 属性图示例

1.2 模式重复性度量

基于重复模式的属性图表示，较为直观的模式重复性度量方法是通过计算子图之间的同构性对重复模式实例进行两两匹配。通过一个子图匹配过程实现同一个属性图中子图间同构性的度量。

本文用一个匹配度矩阵M来表示属性图中顶点与顶点、边与边的匹配度，其中对角元素(ia,ia)表示顶点对(vi,va)之间的匹配度：

(1)

式中：A(vi,va)代表不同的前景对象i与a之间的相似度，只有当顶点所对应的对象类别、状态一致时才能够进行匹配。

子图匹配问题是一个NP-hard问题，由于本文工作中两两重复模式的重复性度量这一子问题的数据规模较小，所以采用目前较为通用和高效的整数二次规划方法[12](Integer Quadratic Programming)来对其进行优化。每两个子图的匹配过程通过将一对匹配顶点作为初始化状态，并在此基础上推理最优的匹配子图。同时，由于属性图在较为稀疏的情况下即可表示重复对象及其空间分布关系，稀疏性可以作为约束直接对子图匹配优化进行剪枝，以进一步提高子图匹配的效率：

(2)

式中：系数h>1/min(M)，以保证对于任意一对顶点i和j，若M中没有能同时包含这两个顶点的匹配边，则yij直接固定为0。

2 方法设计

本文方法能够自动发现多类型对象构成的印花图像中的多尺度重复模式，主要处理流程可分为如下两个阶段：混合表示生成阶段和重复性对象空间组合分析阶段。算法基本流程如图2所示。

图2 对象重复模式发现方法流程

1)在混合表示生成阶段，首先利用图像的低层特征检测全局的对象实例候选，并以候选的对象实例作为初始化分别进行对象内容的一致性分析和对象空间结构分析。然后通过结合候选对象的内容信息与空间结构信息对候选对象进行过滤，并建立图像的属性图。

2)在重复性对象空间组合分析阶段，基于属性图模型，首先通过基于子图匹配的重复性空间关系分析过程，分析同类对象实例间空间邻接关系的一致性，用匹配的属性子图表示重复性对象空间组合，并将子图匹配过程中的异常配对节点判断为异常节点。其次判断异常节点对所对应的对象实例之间的仿射变换、缺失等状态，在属性图中更新对象实例状态信息，从而迭代地进行对象实例的重复性空间关系分析和状态更新，以优化对象重复性和对象空间分布重复性信息。当图像中的所有异常节点都被确定时，通过一个随机抽样一致算法[13](Random Sample Consensus)估计重复模式的晶格排列结构参数，从而估计重复模式的尺度，并根据模式尺度提取重复模式实例。

利用这两个阶段分别实现了对象的“内容一致性”和“空间结构一致性”，从而满足了印花图像对多类别和多尺度的需求。

3 方法实现

3.1 结构推理

通过计算空间相邻的候选对象之间的局部位置关系，对输入图像建立全局的结构图，并根据候选对象的空间分布及显著性信息估计候选对象的包围框尺寸。由于给定了候选对象的中心位置后拓扑结构合理的空间排列结构不唯一，结构推理的流程类似于基于产生器[4]的结构推理方法。首先统计图像中相邻候选对象之间边的角度，确定空间结构的显著方向。然后根据每种候选排列约束对每个候选对象生成相应的产生器，计算产生器之间的连接生成候选的图像空间结构，并利用候选的结构图结合图像显著性信息估计每个候选对象的包围框，如图3所示。

图3 候选对象包围框

由于构成印花图像的印花图样中组成元素分布均匀的特性，每个对象实例邻接的对象实例在数量和几何拓扑结构上一般也都是相似的，因此本文令印花图像结构图中所有节点的度约束不大于4，从而保证拓扑结构的稀疏性。

3.2 对象内容聚类

由于印花图像中对象的语义性较弱，难以建立统一的类别标注标准，因此已有的有监督对象分类方法均难以适应。所以本文采用基于视觉词袋(Bag-of-visual-word)特征模型和Mean-shift聚类的无监督对象内容一致性分析方法。

首先对输入图像提取低层图像特征SIFT描述子。为了提高特征描述子的尺度，使其能够有效表示候选对象，对每个候选对象建立视觉词袋模型以获得对象尺度的特征。然后使用Torii等[14]提出的软匹配算法和近似K近邻算法[15]，对特征点集中的每个特征点计算临近的视觉单词。

由于单幅印花图像中对象类别数目不确定，因此本文通过自适应确定类别数量的Mean-shift聚类算法判断候选对象的内容一致性。

3.3 图像建模

候选对象的聚类是对候选对象内容信息的检测，因此可以利用该信息对初始候选对象进行过滤，并更新对象的空间结构。根据候选对象的位置、包围框尺寸、类别、空间结构，我们可以对印花图像建立属性图模型。

首先根据候选对象的显著性均值对候选对象的包围框进行非极大值抑制(Non Maximum Suppression, NMS)，将过于临近并且显著度较低的候选对象标记为异常点，并将抑制每个异常点的节点记录为父节点。若异常点与其父节点类别一致，则说明该节点同属于一个前景对象，因此将异常点丢弃；若不一致则保留。

对过滤后的候选对象集合重新建立候选对象空间结构，并在不同顶点度约束候选空间结构中判断最佳空间结构，如图4所示(其中虚线方框内的点代表异常点，k=2时为最优结构)。

图4 候选空间结构

3.4 重复性空间关系分析

重复模式包括重复对象及重复性对象空间分布，基于图像属性图提出的子图匹配算法度量图像中任意粒度的重复性对象空间分布关系，获得子图形式表示的重复性对象空间组合，从而确定同类对象实例之间空间邻接关系一致性，提高重复性分析的粒度，以辅助重复模式尺度的发现。

根据图像的属性图建立n×n维匹配度矩阵M，对每类重复对象集合建立一个亲和度矩阵以统计同类对象间的空间邻接关系的一致性，同时减少重复计算。迭代地计算对象间重复性空间关系，得到子图匹配结果。异常节点对为匹配的子图中匹配的节点对相邻接的无法匹配的节点对，如图5所示(上下两个连通区域中对应的点为匹配节点，不对应的节点为异常节点)。

图5 重复性对象空间关系分布示意图

4 实验结果与分析

本文数码印花数据集由印染厂商提供并整理的509幅印花图像。对象实例标注采用人工指定实例中心以及设置重复模式的尺度。使用者只需标注图像设计模式尺度内的对象实例，标注的对象实例可按照晶格模型延伸到整个图像空间，从而降低人工标注的成本。

4.1 方法定性分析

为验证本文方法的有效性，分别对非遮挡对象组成的印花图像集中单类单尺度、多类单尺度和多类多尺度对象组成的印花图像进行了重复模式发现，最终检测并提取的重复模式实例如图6所示。其中一个连通子图代表一个重复模式实例，灰色矩形框代表了重复模式尺度。可以看出，对于多类实例对象中不同类别和尺度重复对象组成的多尺度重复模式，本文算法都能准确发现模式尺度，并提取重复模式实例。

图6 重复模式发现结果

4.2 方法定量分析

已有重复模式发现方法主要分为利用模式内容的一致性与利用重复模式空间结构的规则性两类，分别选择具有代表性的文献[8]和文献[3]方法，设计实验进行模式实例检测有效性和算法执行效率的比较。

由于有效重复模式实例不唯一，难以直接与Ground-Truth标注的模式实例对比从而验证模式实例检测的有效性，而已有重复模式发现方法中，文献[9]提出的同质性(Homogeneity score，H-score)指标可以有效测量检测的重复模式实例之间的内容一致性，从而对重复模式实例的检测结果进行评价。对于每幅图像中检测的不同重复模式实例，其包围框尺寸可能不一致，本文将其通过仿射变换统一映射为50×50的图像块。计算每幅印花图像中重复模式实例的同质性得分为：

H=median{std(I(1)),std(I(2)),…,std(I(m))}

(3)

式中：std(I(i))为图像I中重复模式实例之间第i个像素值的标准差；归一化的重复模式实例图像块共有m个像素；median{}表示输出中值的函数。对不同方法中对象尺度匹配成功的重复模式实例进行有效性检测，对重复模式实例的图像块中所有像素的标准差取中位数作为该图像的H-score，并对每类数据集计算H-score的均值和标准差，实验结果如表1所示。

表1 本文方法与已有方法的平均成功率比较 %

可以看出，本文提出的重复模式发现方法在三类子集上的H-score均低于已有方法，表示本文方法发现的重复模式实例内容一致性更高。由于文献[8]算法无法区分重复对象之间可能的状态信息，因此它容易将内容近似的对象作为重复模式，导致重复模式实例之间内容差异较大。而文献[3]方法在初始化重复模式实例邻域内搜索内容相似图像块并更新重复模式实例，容易陷入局部最优(如图6中多尺度多类别对象构成的重复模式检测结果所示)。因为本文算法基于重复对象及其空间分布关系发现重复模式实例，所以对于对象子集中不同图像的检测结果较为鲁棒，H-score的标准差均低于已有方法。而由于人工标注Ground-Truth存在误差，本文方法对于多类多尺度对象的H-score均值和单类单尺度对象的H-score标准差均低于Ground-Truth的标注结果。

同时，我们通过度量不同算法在不同数据集的平均执行时间来评价重复模式发现方法的效率。实验结果如表2所示。由于本文算法的平均执行时间与重复模式尺度以及图像中的对象实例数量正相关，而单类单尺度对象和多类单尺度对象组成的印花图像大多对象实例数量较少，并且重复模式尺度较小，因此算法的平均执行时间得到了一定的改善，而对于多类多尺度对象，本文方法的平均执行时间也与效率较高的已有算法大致近似。

表2 与已有方法的平均执行时间比较

5 结 语

本文提出了一种同时利用对象实例的重复性与对象实例之间空间分布的重复性共同发现重复模式尺度并检测模式实例的方法，不仅能检测由实例对象组成的印花图像中可能存在的多类和多尺度重复对象，还能基于图像中的对象实例信息高效自动地发现重复模式的尺度，并有效提取图像中由对象实例之间空间组合而成的重复模式实例。本文方法为重复模式发现提供了一个新思路，并且为基于重复模式的印花图样创作提供了一个新途径，避免了从无到有的高成本印花图样创作过程。