针织品的逆向程序化建模

Elena Trunz, Sebastian Merzbach, Jonathan Klein, Thomas SchulzeMichael Weinmann, Reinhard KleinInstitute of Computer Science II, University of Bonn, Germany{trunz,merzbach,kleinj,mw,rk}@cs.uni-bonn.de, s6tsschu@uni-bonn.de86300逆向程序化建模的针织品0摘要0近年来，对布料的分析和建模受到了广泛关注。虽然最近的方法主要集中在机织布料上，但我们提出了一种新颖的实用方法，可以从仅有一张没有附加注释的图像中推断出更复杂的针织结构以及相应的针织说明。针织品是通过重复使用相同的图案来制作的，这些图案由一小组基本针迹类型的网格状排列组成。我们的框架解决了出现的针迹类型的识别和定位问题，由于外观变化巨大，这是一项具有挑战性的任务。得到的粗略定位的针迹类型用于推断底层网格结构，并用于提取图案重复的针织说明，同时考虑到格式塔原理的原则。最后，得到的说明可以用于复制针织结构，可以通过渲染或实际编织来实现，这在几个示例中得到了证明。01. 引言0织物是我们日常生活中的重要物品。与机织品相比，针织服装由各种针织操作形成的复杂针迹结构在视觉上更加突出，每种针迹结构都具有独特的外观。此外，各种类型的针织服装仍然属于一种由社会中较大群体掌握的手工艺，涵盖了各个年龄段的人群。其中一个原因可能是人们对使用针织图案制作自己的服装的兴趣，以满足个人主观偏好。虽然有一些书籍和网站提供了各种图案及其相应的制作说明，但希望能够根据提供的图像（例如通过Google等标准搜索引擎提供的图像）来复制图案，而这些图像缺乏相应的针织说明。不幸的是，仅通过“阅读”一张图像来推断其中的针织图案是非常具有挑战性的。0即使对于专家来说，针迹的视觉外观也呈现出很大的多样性，因为相邻的针迹可能会遮挡它们或产生阴影。基本针迹类型的外观变化进一步增加了由使用的纱线的特性（如厚度、纱线类型等）或不同人的个体编织风格引起的各种变形，如拉伸、孔洞和松紧针迹。因此，即使是专家也经常倾向于通过拉伸物品并从两侧进行检查来可靠地推断针织说明，包括被遮盖的针迹。当分析单张照片中的针织织物时，这些操作是不可能的。0逆向程序化建模是过去十年中受到广泛关注的研究领域，它可以从仅有几个甚至一个示例中推导出对象的模型。相关应用包括为植物、编织物、建筑和立面推导生产规则。然而，这些方法都是针对特定应用定制的，不能轻易地转化为推断编织图案的方法。0在本文中，我们首次从仅有一张没有注释的图像中推断出复杂的针织结构和相应的针织说明。这意味着解决标记问题，即从输入照片中复杂的视觉外观中识别出现的针迹类型并正确定位它们。为此，我们引入了一个新的流程，包括四个主要组成部分：（1）在整个图像中搜索各个针迹类型，（2）从前一步骤中粗略定位的针迹推断出底层网格结构，（3）通过错误校正和图案尺寸检测步骤确定所需图案的尺寸，并纠正第一步骤中的标记错误，最后（4）根据找到的图案尺寸和纠正后的底层网格结构推导出最终的针织说明（类似于针织书中的说明），并应用对称法则和普兰岑法则[5]考虑人类感知的直觉。这些86310图1：针织（上）和针织反面（下）的外观变化示例。0派生的指令允许使用可能不同的纱线类型复制编织图案，如几个示例所示。总之，本文的主要贡献包括：0•  一种从单张图像中逆向过程建模针织品的新方法。0•从最初确定的针迹类型粗略定位的假设中推导出底层最优规则网格结构。0•一种纠错技术，确定编织图案的正确尺寸并纠正可能的识别错误。0•从推导出的网格结构中按照人类直觉进行编织指令的最终归纳。02. 背景0编织只依赖于一组相对较小的基本动作，它们的组合可以生成各种图案的底层编织结构[34]。因此，即使是儿童也可以学会制作帽子、围巾或隔热垫。这些基本动作及其组合产生了许多针迹类型，通过重复和不同的顺序使用这些针迹类型可以生成各种各样的编织设计。本文重点研究了两种基本的针迹类型：针织和针织反面（见图1）。针织的常见形状类似于“v”的结构。如果上方或下方（或两者都有）有针织反面，则针织变得部分被针织反面覆盖。此外，针织的宽度比如果它的上方和/或下方有其他针织，则会变小。针织反面通常呈现波浪结构。如果下方和上方有针织，则这个波浪会变宽。然而，如果针织反面的右侧或左侧（或两者都有）有针织，则针织反面会被部分覆盖。图1展示了针织反面和针织的一些外观/形状变化。请注意，所示的针迹变化仅通过以不同的顺序排列基本针迹类型来引起。此外，这些外观变化严重依赖于所使用纱线的属性，以及由主观编织风格引起的针迹变形，使得手工编织织物的几乎每一针都是独特的。03. 相关工作0我们逆向建模针织品的框架的主要组成部分包括在图像中寻找用户标记的基本针迹类型的出现，基于针迹候选和底层重复模式推断网格结构。因此，我们简要回顾了模板匹配和逆向过程建模领域的发展。我们不详细讨论针织织物的可视化，只参考了Yuksel等人的工作[34]。模板匹配：传统的在图像中高效搜索查询补丁的技术通常基于使用平方和距离（SSD）、绝对值和距离（SAD）或归一化互相关（NCC）。随后的工作解决了它们在处理噪声[10]和光照变化[13]方面的不足。随后的改进来自于使用鲁棒误差函数[6, 22, 21,18]。之后，Barnes等人[2,3]引入了PatchMatch算法，用于在平移、旋转和缩放之间进行最近邻匹配。然而，所有这些技术只允许模板和查询区域之间的一对一映射，并且依赖于模板补丁和目标补丁之间的严格刚性几何变形。因此，它们无法处理我们预期的包含编织原语（针织和针织反面）的补丁的几何变形。为了处理材料识别的外观变化，其他方法依靠通过考虑不同描述符（例如[20]）提取的直方图在分类框架中进行不同图像的匹配。此外，已经探索了基于集合的匹配，以允许更稳健地匹配基于纹理外观空间的纹理[14,31]。其他方法被设计为明确处理参数变形，如2D仿射变换[16]或更一般的非刚性畸变[29]。然而，尽管对于底层几何的要求是参数畸变模型，但这些技术也依赖于查询和目标补丁之间的一对一映射的假设，在存在遮挡或背景杂乱的情况下容易出错。进一步的工作探索了目标和查询补丁之间的双向相似性。Simakov等人[23]用一组补丁和考虑的双向相似性（BDS）度量来表示图像，该度量考虑了第一张图像中的补丁与第二张图像中最近邻补丁之间的距离之和，反之亦然。为了区分由所考虑补丁的前景/背景部分引起的内点和外点，提出了最佳伙伴相似性（BBS）[7]，它基于计数最佳伙伴对，并因此仅隐含地使用实际距离。因此，与BDS相比，它具有更高的鲁棒性。86320已实现。Talmi等人[26]通过强制互相最近邻匹配的多样性，并明确考虑最近邻场的变形，扩展了这项工作。为了加快匹配过程，他们使用了近似最近邻搜索。虽然任何模板匹配技术都可以应用于推导出我们方法所需的某些基本原语的定位的概率图，但我们使用基于BBS的模板匹配，因为它已被证明对于预期发生在编织原语中的变形具有鲁棒性。我们通过使用额外的梯度信息改进了BBS技术。在评估中，我们比较了几种模板匹配技术，并展示了扩展的BBS方法在我们特定问题的背景下优于其他技术。基于图像的纹理模式检测：布料建模迄今为止受到了很多关注。特别是从图像中检测纹理模式的方法与我们的工作密切相关。特别是，Schr¨oder等人[19]和Guarnera等人[11]所采用的以纱线为级别的编织布料的完全逆向工程已被证明是当前最先进的技术。虽然这些方法对于分析编织布料非常强大，但它们并不适用于处理针织物。针织服装本质上是3D的，而针对特别是手工制作的针迹的最终形状并不具备纬线和经线的相似性和规律性，其中必须考虑到纱线的遮挡和非刚性变形，以便能够在图像中找到针迹的实际位置和类型。据我们所知，我们是第一个解决从单个图像中检测编织图案和相应编织指令的问题的人。逆向过程建模：逆向过程建模（IPM）是推断给定模型的一组参数[28,30]甚至整个过程描述的问题。早期对将逆向过程建模应用于图形应用的研究包括对3D网格[4]和2D矢量设计[24]的工作，但在这个研究领域已经取得了很多进展。与此同时，逆向过程建模被广泛使用，并已应用于各种目的，从推断3D设计模式[27]到植物建模[25,17]，再到建筑点云的编辑[8]以及推断建筑立面的过程描述[32, 33, 9,17]和逆向工程编织布料[19]。关于逆向过程建模的详细和广泛调查，我们参考Aliaga等人的报告[1]。04. 针迹模式推断方法0在本节中，我们介绍了从单个输入图像中推断编织图案和相应指令的方法。初始预处理0该步骤补偿了所描绘的针织图案的非轴对齐性，因此使我们的框架能够处理倾斜的针织品图像。在下一步中，用户通过直观的界面提供特定基本针迹类型（如针织或针织）的示例。随后，在整个图像中搜索包含这些针迹类型的图像块，并使用得到的粗略定位来推断底层的网格结构。此外，错误校正过程允许补偿网格中可能出现的针迹类型错误分类，并检测重复图案的大小。找到的大小和优化的网格结构然后用于找到图案的起始位置，从而完成针迹模式推断的过程。最后，我们推导出底层的生成规则，并将其转换为相应的编织指令，以实现对输入图像中所描绘的编织图案的复制。有关所涉及组件的详细信息，请参阅以下各节。04.1. 预处理0在允许用户为图像中的相关拼接类型指定模板之前，我们执行预处理步骤以便于注释过程。为了补偿与轴对齐的偏差，我们使用梯度方向直方图（HOG）来确定照片中最主要的方向，这是合理的，因为生产过程产生的固有网格结构。这允许通过旋转来将网格结构与轴对齐，从而使我们的算法能够处理非轴对齐的输入模式。相关示例在补充材料中展示。04.2. 交互选择相关的拼接类型0可能可以使用完全自动的流程来检测拼接类型。然而，这将需要大量的注释数据库，其中显示了可能发生的拼接类型以及具有不同属性的纱线（纱线厚度，反射行为等）在不同照明条件下的各种拼接邻域和扭曲。据我们所知，这样的数据库尚未公开提供，因此我们不依赖完全自动的方法来基于机器学习技术检测图像中的拼接类型。相反，我们让用户通过为输入图像中出现的每种拼接类型提供一个样本来引导寻找拼接类型的搜索，以尽量减少用户交互。为此，我们实现了一个易于使用的界面，允许用户通过简单地在拼接上绘制一个矩形来选择每种拼接类型的样本。考虑到出现的拼接可能存在较大的变化，随后需要应用鲁棒的模板匹配技术。863304.3. 拼接定位假设的推导0在图像中找到特定的拼接类型是复杂的，因为它们的外观可能会因为邻近拼接的部分遮挡、使用的纱线类型（包括其反射行为、厚度和毛细度）的变化以及制造过程中个体编织风格的变化（如紧密或松散的拼接）而显著变化。为了能够基于给定的模板在图像中找到拼接类型，处理扭曲和部分匹配成为推导出拼接类型位置假设的重要先决条件。最佳伙伴相似度（BBS）基于模板匹配[7]已经针对这些目标进行了设计，证明在这方面优于大多数先前的技术。因此，我们将这种技术应用于检测个体拼接类型（如针织或编织）的假设。根据Dekel等人[7]，从局部图像区域和模板中提取的两个点集P = {pi}Ni = 1和Q = {qi}Mi = 1之间的BBS定义如下：0BBS(P, Q) = 10min(M, N)0N是0i = 10j = 1 bb(pi, qj, P, Q). (1)0这里，0bb(pi, qj, P, Q) =01，如果NN(pi, Q) = qj且NN(qj,P) = pi，否则为0（2）0作为受最近邻定义和距离度量影响的指示函数0NN(pi, Q) = argmin q ∈ Q d(pi, q) (3)0和距离度量0d(p, q) = ||p(A)i - q(A)j||^2 + λG||p(G)i - q(G)j||^20+ λL||p(L)i - q(L)j||^2. (4)0与原始实现[7]相比，我们在补丁中扩展了基于RGB的外观（A）和空间距离（L），并加入了额外的梯度约束（G），以强制在补丁内具有相似的梯度。根据几个示例，我们确定 λG = 100 适用于我们的目的，并且在使用 λ L = 2和将图像和模板分解为 k × k的补丁时，遵循原始实现，其中 k = 3。结果，我们获得了BBS似然图，指示了各个拼接类型的（粗略）定位。最后，我们将获得的不同拼接类型的似然图合并为一个结果似然图，该图包含每个像素获得的各个拼接类型的最大似然以及相应的最可能的拼接类型。这些图的示例如图2所示。0图2：用户指定的针脚模板(左)和相应的似然图(中)。颜色表示似然值，即颜色越浅，概率越高。右侧的图像显示了包括针脚类型分配(编织=橙色，针织=蓝色)的最大似然图。04.4. 推断针脚的网格结构0在上一步中检索到的最大似然图包含了关于各个针脚类型在局部位置上的粗略像素级似然。从这个粗略的定位中，我们需要确定每个个体针脚的精细排列和相应的类别。为此，我们利用编织过程引起的基础网格状结构的存在，以考虑个体针脚的空间扩展限制它们的位置。一般来说，后者不会等距分布，网格可能由于非理想的人工制造过程或织物的处理而出现显著的扭曲。为了模拟这种行为，我们将针脚的中心与一组标记点关联起来，这些点按照2D网格状结构排列。这些点必须满足以下属性：0• 每个点被赋予代表某种针脚类型(如编织或针织)的高概率(P1)。0•相邻点之间必须保持最小距离(与针脚原型的数量级相当)(P2)。0• 相邻点之间的距离不能超过一个针脚类型的最大扩展(P3)。0• 点集具有规则的近似矩形网格结构(P4)。0找到满足上述属性的最优点集可以用点选择问题来表达。04.4.1 针脚定位作为点选择问题0为了推断出各个针脚中心的位置，我们解决了一个可以用整数线性规划(ILP)来表达的点选择问题。设P为输入图像的所有可能点(像素)的集合。此外，设Popt为与我们优化问题的解对应的点集。用�oi =In order to force the points of the optimal solution to havea grid-like structure (P4), we subdivide the input image intor · c grid cells Gk ⊂ P with the width wic (1 − uw) and�∀i:pi∈Poi = r · c.(9)To determine the number of columns in the grid, we use theposition of one of the stitch samples selected by the userduring the initial step of the inference approach and selectthe region around the stitch position within the likelihoodmap. The height of the selected region corresponds to theheight of the selected template with some additional toler-ance and the respective width is given by the image width.To account for possible distortions, the height is allowed todeviate up to uy in each direction from the center of the cho-sen stitch sample (in our experiments, we use uy = 25%).Using the data of this truncated map, we apply a similar ILPformulation as before with slight changes. In contrast to theoptimization described before, the point variables consist ofthe pixels from the chosen strip. The objective functionaland all constraints except for the row and the column num-ber constraints remain unmodified. The number r of rowsis set to 1. Now we compute the possible minimal value ofthe number of columns c as cmin =wiWmax , where Wmaxdenotes the maximal width of both templates, since we donot yet know the correct stitch labelings of this strip. To ac-count for possible stitch occlusions, we compute the maxi-Because of occlusions and different deformations thestitches vary from each other in size. Additional variationsare induced by the use of different yarn types and incon-sistencies of the knitter. We implicitly take these aspectsinto account by analyzing the strips extracted from the pre-vious step to estimate uncertainties in the spatial extensionsof the stitches. First, we compute the average width wa andheight ha of the stitches taken from the four strips (two foreach sample). By computing the maximum absolute devi-ation for the width (dw) and height (dh) separately, we get86340像素p i ∈P的似然值根据前一步的似然图和得分(i)使用二进制变量来确定是否分配给某种针脚类型的概率：0� 0，如果p i不属于P opt；1，如果pi属于P opt (5)0决定点p i是否分配给最优解，我们最大化函数�0根据前述属性P2、P3和P4的约束条件。为了确保属性P2和P3，我们确定每个像素p j ∈ P的两个相应的矩形区域P minj � P和P max j �P，表示网格结构中相邻点位置的不确定性。P minj的宽度为w min，高度为hmin，表示拼接的最小估计范围，P max j的宽度为wmax，高度为hmax，表示拼接的最大估计范围。相应的扩展大小值和不确定性的计算在第4.4.3节中讨论。为了考虑属性P2，我们限制每个区域P min j最多包含一个最优点p ∈ Popt，为了考虑属性P3，每个区域P maxj被限制为至少有一个点p ∈ P opt，即：�0o i  ≤  1，且�0r (1  −  u h )，其中w i和hi分别表示图像的宽度和高度，c和r分别表示网格的行数和列数。这些值是预先计算的，如第4.4.2节所述。用u w和uh表示针脚在x和y方向上的空间扩展的不确定性，这里用于允许单元格的重叠。u w和uh的值是根据第4.4.3节中描述的计算得出的。我们限制最优解至少包含每个网格单元中的一个点。此外，解中的点数被限制为等于r∙c。这两个约束条件确保了属性P4，同时允许单元格的重叠：�0G 表示所有网格单元的集合。为了解决这个整数线性规划问题，我们使用Gurobi 求解器 [12]。从包含在0根据得到的最优解，我们按照以下方式构建网格：我们根据像素的 x 坐标对所有点进行排序，并为网格的每一行分配 c个点。分配给各个点的针迹类型存储在一个矩阵 M r × c中。04.4.2 计算行数和列数0W min ，其中 W min  表示两个模板的最小宽度。我们从 cmin  到 c max的可能列数进行迭代，并将每个最优解的结果目标函数除以当前列数。最后，我们得到归一化目标函数最大值所对应的列数 num- ber  c  作为最优解。行数相应地确定。04.4.3 相邻针迹位置的不确定性0h a ，得到宽度的值 w min  =  w a  −  u w  和  w max  =w a  +  u w ，以及高度的类似值 h min  和  h max，然后用于优化。86350为了计算行数和列数，我们使用用户选择的模板的实际大小的平均值，并将不确定性值 u x  和 u y设置为平均模板大小的25%。请注意，较大的不确定性值会导致在优化过程中变量数量的增加，从而显著增加计算时间。04.5. 错误修正和重复大小检测0在从上一步推断出的基础网格结构 M后，我们的目标是找到一个直观的最小重复模式。为此，我们假设感兴趣的编织图案至少完全包含在图像中两次，但也可能出现未完成的重复。为了找到模式，我们首先确定正确的大小，然后确定模式的起始位置。由于从网格优化步骤得到的针迹类型矩阵 M可能仍然包含一些错误识别的针迹类型，因此必须同时进行矩阵 M中的模式大小的识别以及潜在的错误修正。虽然可以使用 Wu等人提出的区域生长方法从不带标签错误的针迹类型的矩阵 M 中推导出重复结构的大小[33]，但是如果矩阵 M中存在错误，则我们必须对所有可能的重复大小进行穷举搜索，并计算每个可能的重复大小的错误分数。最后，假设具有最小错误分数的大小是正确的大小。设 r 和 c分别表示可能的重复的行数和列数。假设图像中至少有两个模式的出现，我们只考虑满足以下条件之一的重复大小 s = ( r, c ) ： r ≤ R02 。更详细地说，我们将 M 完全分割成一组不重叠的子矩阵 M s ，每个可能的重复大小 s= ( r, c ) 都有一个子矩阵 M s i ∈  M  s ，其大小为s（如果在边界上描绘未完成的重复，则可能更小）。在 M 的不同位置（ m, n）处评估这些分区，其中 m = r k 且 n = c h ，其中 k = 1 , . . . ,  � R0r �  和 h  = 1 , . . . ,  � C0c � ，分别。随后，我们根据它们的索引对所有的 M s i ∈M  s 进行对齐，并计算矩阵 M s max，该矩阵包含每个子矩阵相同索引位置上出现次数最多的针迹类型。然后，我们计算每个 M s i 与 M s max之间的汉明距离 D i。所有汉明距离的总和得到当前重复大小 s 的总距离 D s。我们将具有最小距离的大小和底层针迹类型矩阵 M s max视为结果模式大小。如果有多个具有相同编辑距离的大小，则选择具有最小值 r + c的大小，因为否则存在另一个重复在重复内。如果由于相等而无法确定索引位置上出现次数最多的类型0在该位置的针迹类型数量之后，我们比较这些类型所对应的像素的相似度值，以确定最终的类型。如果得到的最优重复的距离与零有偏差，说明矩阵M中存在错误。在这种情况下，确定相应的M s max具有正确的针迹标签，并根据M smax对所有子矩阵进行校正。04.6. 重复位置确定0最后，需要计算出基础网格结构中一个尽可能直观的重复图案的定位以及重复图案的大小。为了选择一个直观的图案重复，我们从人类感知中汲取灵感，并利用Gestalt理论中的两个基本定律[5]。对称定律表明，对称元素倾向于被视为一个统一的群体。考虑到这一点，我们在图案的x方向上搜索对称性。如果存在对称性，我们在选择重复的起始位置时会考虑到它。如果重复结构中没有对称性，我们应用Pr¨agnanz定律。根据这个定律，人类更喜欢简单和有序的状态，这些状态需要较少的认知努力，因此可以比复杂的结构更快地处理。在我们的情况下，这意味着从所有可能的位置中选择图案的起始位置，使得计算所涉及的每两行和每两列之间的针迹类型变化之和最小。这确保了图案中出现的个别结构（如方块或圆形）不会被破坏。05. 结果与讨论0样本选择：为了测试我们的方法，我们选择了25张照片和扫描件，这些照片和扫描件展示了具有不同图案的编织样品，并使用了各种类型和颜色的纱线制作而成。其中八张照片来自互联网，一张照片描绘了一件机器编织的作品，十六张照片描绘了手工编织织物。我们专注于手工样品，是因为这些样品的变化程度更高，因此比机器编织的样品更具挑战性。性能分析：表1提供了本文选取的四个示例的计算时间和问题规模的概述。更多具有相应运行时间的示例显示在补充材料中。由于计算相似度图与BBS以及使用Gurobi求解器[12]求解最优解是耗时最长的操作，我们仅报告这些步骤的计算时间。其他步骤所需的时间可以忽略不计。所有计算都是在一个未经优化的实现上进行的，使用的是Intel(R) Core(TM)i7-5820K CPU，主频为3.30 GHz。1673× 257102.5311.029×54×21/4502690×37031.938.1315×117×61/16503803×844219.7962.0211×178×84/18704516×347137.744.787×63×400SADNCCDDISBBSBBSgeP x0.4220.4530.2160.3420.194eG0.6330.0870.0620.0710.040eP0.2680.0560.0510.0460.02986360计算是在一台未经优化的Intel(R) Core(TM) i7-5820KCPU，主频为3.30 GHz的计算机上执行的。0表1：列包含图像大小（IS），BBS和ILP的运行时间（以秒为单位），以及网格（GS）和图案（PS）的大小。e G和eP分别表示经过错误校正后整个网格和图案中错误分类的针迹类型的比例。0ID IS BBS ILP GS PS e G e P0视觉质量：图3展示了流水线的四个示例纺织品的各个步骤的结果。对于第二行示例中的一个输入图像中的一针（底行中从左数第六针）实际上是错误的（织而不是针织）。我们的方法识别并纠正了这个错误。为了获得所示的逼真渲染效果（最后一列），我们使用Zhao等人的程序模型[35]合成纱线。然后，我们根据发现的编织指令对纱线进行变形，并将得到的纤维几何形状离散化为体素网格，存储每个体素的平均密度和纤维方向[15]。然后，使用体积光线追踪器[15]对这种基于体素的表示进行渲染。此外，图4显示了在应用我们的方法对磨损的服装进行处理时获得的推断网格结构的结果。对模板选择的敏感性：为了评估对于各个针迹类型的模板选择的鲁棒性，我们进行了一项研究，让10名年龄从10岁到67岁的人提供相应的注释。结果显示，只要测试者遵循选择两个与同一类型的其他针迹相似的模板的简单指导（图1），结果没有显著差异（见补充材料）。0表2：几种模板匹配技术的性能比较：行包含误分类像素的比例 e P x ，整体网格的针织类型 e G ，以及纠错后的图案e P。对于第一项度量的计算，我们排除了在不同针织类型之间的过渡区域内的像素。在32%的测试中，基于SAD似然图的优化未能成功检测到正确的网格行数和/或列数。这些情况被排除在报告的SAD的 e G 和 e P 值之外。0不同模板匹配方案的适用性：我们评估了不同模板匹配方案用于生成各个针织类型的似然图的适用性。为此，我们将我们的BBS技术的扩展版本与附加梯度信息的BBSg进行了比较，与归一化互相关(NCC)、绝对差值之和(SAD)、原始BBS方法[7]（不包括提出的扩展）以及可变形的多样性相似性(DDIS)方法[26]。表2总结了各自的结果。为了获得有意义的结果，输入图像的分辨率需要足够高，以至于最小模板尺寸不小于30×30像素。计算效率：为了找到针的最终中心位置，我们应用了一个被表述为整数线性规划问题的全局优化方法。由于整数线性规划问题被认为是NP难问题，计算时间可能不切实际。为了加速对大尺寸图像的最优网格推断，我们将相应的似然图缩小了0.5倍。缩小尺寸显著减少了优化的计算时间，同时仍然产生与不缩小时相似的结果（关于缩放的评估请参考补充材料）。减少计算时间的另一种可能性是选择一些迭代的局部最优方法而不是全局优化。为了进行比较，我们使用模板匹配步骤中的似然度和针织类型分配作为选择相邻针中心的贪婪策略的起始点，我们还利用了模板尺寸的不确定性。首先，我们取似然度的最大值来找到针的最有可能的位置，并定义一个最小距离，在该距离范围内不允许出现其他针。在从似然度中删除相应区域后，我们继续搜索下一个最高的似然度，放置一个针中心，并再次从似然度中删除该区域。这个过程迭代进行，直到无法再放置更多的针中心或剩余的似然度低于某个阈值t（我们使用t=0.2）。如图3所示，这种方法不能得到可接受的针中心假设，因为它是迭代的局部优化。此外，这种方法不能自动计算不确定性，而是需要为每个织物样本手动指定。相比之下，我们的全局优化技术能够以更高的质量得到针中心的假设。图案搜索：原则上，一旦找到了重复图案的大小和正确的标记，就可以复制初始的编织示例，因为编织是周期性的。然而，当编织整个衣物时，衣物的边界应该是吸引人的。因此，我们需要确定正确或最佳的起始位置。86370输入编织图案针织图案贪婪的我们渲染0图3：从左到右：输入图像，两种针织类型的似然度，通过贪婪方法推导出的针中心假设和通过我们的方法推断出的网格结构，相应的编织指令（从底部到顶部计数行，空单元格对应奇数行的针织，偶数行的针织对应带有条纹的单元格），以及渲染结果。0图4：人穿着的针织品的一般、无限制的设置（左）和一些感兴趣区域的检测到的网格结构（右）。0至少有一个漂亮的图案。在补充材料中，我们说明了选择直观图案的问题。通过我们的图案搜索过程，我们试图避免破坏图案的现有结构，如三角形或棋盘图案，从而遵循Gestalt原则。局限性：在本文中，我们将我们的方法限制在两种基本的针织类型：针织和针织。然而，针织类型的数量并不严格限制为两种。在补充材料中，我们还提供了一个包含三种针织类型的示例。然而，包括使得图案的网格状结构变形的针织类型（例如孔），需要包括额外的约束条件，这是我们希望在未来的工作中追求的。此外，如果输入图像质量较低或几乎完全遮挡0针数太多，以至于粗略定位无法产生有意义的结果，优化技术将无法产生正确的标签。06. 结论和未来工作0我们提出了一种新颖的实用框架，用于从单个图像中推断针织品的复杂结构以及相应的编织说明。用户提供的各个针织类型的模板在整个图像中粗略定位，并通过在整数线性规划中优化底层网格结构来进一步细化得到的针织位置。重复图案的大小是通过在结果网格的顶点处得到的针织标签计算的。随后，我们应用Gestalt理论中的对称法则和Pr¨agnanz法则来找到直观的图案重复并得到相应的编织说明。虽然我们的方法已经证明可以推导出多种不同的针织品的编织说明，但仍然存在一些需要未来研究解决的挑战。将更多的针织类型纳入框架以及通过将大量的针织类型与其相应的外观变化和机器学习技术相结合来进一步减少用户交互的程度是一个有前途的研究方向，我们计划在未来的工作中继续探索。0参考文献0[1] D. G. Aliaga,  ˙ I. Demir, B. Benes, and M. Wand.逆向程序化建模用于虚拟世界的3D模型。在ACM中86380SIGGRAPH 2016课程，SIGGRAPH'16，第16页：1-16：316，纽约，纽约，美国，2016年ACM。[2]C. Barnes，E. Shechtman，A. Finkelstein和D. B. Gold-man。PatchMatch：一种用于结构图像编辑的随机对应算法。ACM图形学交易（SIGGRAPH会议） ，28（3），2009年8月。[3] C.Barnes，E. Shechtman，D. B. Goldman和A. Finkel-stein。广义PatchMatch对应算法。在第11届欧洲计算机视觉会议计算机视觉会议的论文集的第III部分，ECCV'10，第29-43页，柏林，海德堡，2010年。斯普林格出版社。[4] M. Bokeloh，M.Wand和H.-P.Seidel。部分对称性与逆向程序化建模之间的联系。ACM Trans.Graph. ，29（4）：104：1-104：10，2010年7月。[5] S.Bradley。设计原则：视觉感知和Gestalt原则。https://www.smashingmagazine.com/2014/03/design-principles-visual-perception-and-the-principles-of-gestalt/，2014年。[6] J.-H. Chen，C.-S. Chen和Y.-S.Chen。具有M-估计的鲁棒模板匹配的快速算法。IEEE信号处理交易，51（1）：230-243，2003年1月。[7] T. Dekel，S.Oron，M. Rubinstein，S. Avidan和W. T. Free-man。最佳伙伴相似性用于鲁棒模板匹配。在2015年IEEE计算机视觉和模式识别会议（CVPR） ，第2021-2029页，2015年6月。[8]I. Demir，D. G. Aliaga和B.Benes。用于编辑3D建筑点云的程序化方法。在IEEE国际计算机视觉会议论文集上的论文，第2147-2155页，2015年。[9] I.Demir，D. G. Aliaga和B.Benes。用于编辑3D建筑模型的程序化方法。在2016年第四届国际三维视觉会议（3DV） ，第194-202页，2016年10月。[10] E.Elboher和M.Werman。非对称相关：一种用于模板匹配的噪声鲁棒相似度度量。IEEE图像处理交易，22（8）：3062-3073，2013年8月。[11]G. C. Guarnera，P. Hall，A. Chesnais和M.Glencross。从单个图像创建编织织物模型。ACM Trans. Graph.，36（5）：165：1-165：13，2017年10月。[12] GurobiOptimization公司。Gurobi优化器参考手册，2016年。[13] Y.Hel-Or，H. Hel-Or和E.David。通过色调映射进行匹配：光度不变模板匹配。IEEE模式分析与机器智能交易，36（2）：317-330，2014年2月。[14] D. P.Huttenlocher，G. A. Klanderman和W. J. Ruck-lidge。使用Hausdorff距离比较图像。IEEE模式分析与机器智能交易，15（9）：850-863，1993年9月。[15] W. Jakob，A.Arbree，J. T. Moon，K. Bala和S.Marschner。用于渲染具有各向异性结构的材料的辐射传输框架。在ACM图形学交易（TOG） ，卷29，第53页。ACM，2010年。0[16] S. Korman, D. Reichman, G. Tsur, and S. Avidan. FasT-Match:快速仿射模板匹配。在2013年IEEE计算机视觉和模式识别会议上，页码2331-2338，2013年6月。[17] S. Li