Thiago M. Paix˜ao∗1,2, Rodrigo F. Berriel2, Maria C. S. Boeres2, Alessandro L. Koerich3,Claudine Badue2, Alberto F. De Souza2 and Thiago Oliveira-Santos21143430通过自我监督的深度非对称度量学习实现碎纸文本文件的快速（更快）重建01巴西圣埃斯皮里图联邦学院（IFES），塞拉2巴西圣埃斯皮里图联邦大学（UFES），维多利亚3加拿大蒙特利尔高等技术学院（´ETS）0摘要0碎纸文件的重建是将纸片（碎片）按顺序排列以重新组装这些文件的原始外观。这项任务对于支持法医调查尤为重要，因为文件可能包含犯罪证据。作为费时费力的手动过程的替代方案，一些研究人员一直在研究自动数字重建的方法。自动重建碎纸文件的一个核心问题是对碎片进行成对兼容性评估，尤其是对于二进制文本文档。在这种情况下，深度学习在机械撕碎文档领域的准确重建方面取得了巨大进展。然而，一个敏感的问题是当前的深度模型解决方案在评估一对碎片时需要进行推理。本文提出了一种可扩展的深度学习方法，用于测量成对兼容性，其中推理次数与碎片数量呈线性（而不是平方）比例增长。深度模型不直接预测兼容性，而是利用深度模型将原始碎片内容非对称地投影到一个公共度量空间中，其中距离与兼容性成比例。实验结果表明，我们的方法在准确性上与最新技术相当，对于一个包含505个碎片（来自不同文档的20个混合碎纸页）的测试实例，速度提高了约22倍。01. 引言0纸质文件在法医学中具有很大的价值，因为它们可能包含犯罪调查的支持证据。0� 通讯作者：paixao@gmail.com。0纸质文件在法医学中具有很大的价值，因为它们可能包含犯罪调查的支持证据。然而，这些文件的损坏可能会妨碍甚至阻止它们的分析，特别是在化学破坏的情况下。然而，最近的新闻[9]显示，文件仍然被手撕或使用专用纸碎机（机械撕碎）进行物理损坏。在这种情况下，通常需要法医文件鉴定人员（FDE）来重建原始文件以进行进一步的分析。0为了完成这项任务，通常需要法医文件鉴定人员手动处理纸片（碎片），逐步验证碎片的兼容性并逐步将其分组。尽管这一手动过程具有重要性，但它耗时、费力，并且可能对碎片造成损坏。出于这些原因，自上世纪以来，自动数字重建的研究已经出现。传统上，手撕和机械撕碎的情况被不同地处理，因为后者的碎片形状往往不那么重要。相反，碎片的兼容性几乎完全由外观特征决定，例如碎片边缘周围的颜色相似性。0与机械撕碎一样，也开发了临时策略来处理二进制文本文档，以应对缺乏有区别的颜色信息[6, 11, 16,30]。最近，Paix˜ao等人[22]在纵向剪切的文本文档（即仅在纵向剪切的文档）的重建准确性方面实质性地改进了最新技术。然而，时间效率是一个瓶颈，因为碎片的兼容性需要昂贵的字符形状相似性评估。在后续工作中[21]，该团队提出了一种基于深度学习的兼容性度量方法，进一步提高了重建的准确性和时间效率。在[21]中，通过CNN在自我监督的方式下对碎片的兼容性进行成对估计。̸̸C(πS) =n−1�i=1c(sπi, sπi+1).(1)143440从完整（未碎裂）的文档中恢复。学习过程的任何阶段都不需要人工标注。然而，一个敏感的问题是，每当需要评估一对碎片时，都需要进行模型推断。尽管对于少量的碎片来说这不是关键问题，但对于包含来自不同来源的数百/数千个碎片的更现实的情况，可扩展性会受到影响。为了解决这个问题，我们提出了一种模型，其中推断的数量与碎片的数量成线性比例增长，而不是二次比例增长。为此，将每个碎片的原始内容投影到一个距离度量与兼容性成比例的空间中。投影是通过使用度量学习方法训练的深度模型来执行的。度量学习的目标是学习一个特定任务的距离函数。它已经在多个领域中使用，从Siamese网络在签名验证中的开创性工作[5]，到三元组损失在人脸验证[28]中的应用，到提升的结构化损失[20]，到与互信息最大化[31]的最新联系以及其他许多领域。然而，与大多数这些工作不同的是，所提出的方法不会对语义上不同的样本使用相同的模型。在我们的情况下，右侧和左侧的碎片由两个不同的模型（非对称地）投影到一个共同的空间中。之后，测量右侧和左侧碎片之间的距离，构建兼容性矩阵，并传递给实际的重建过程。为了进行公平比较，实际的重建是通过将兼容性评估方法与外部优化器耦合来完成的。实验结果表明，我们的方法在准确性上与最先进的方法（97.22%）相当，同时仅需3.73分钟即可重建20个混合页面，包含505个碎片，而[21]需要1小时20分钟，即加速了约22倍。总之，我们的工作的主要贡献是：01.本文提出了一种利用度量学习和问题的非对称性进行兼容性评估的方法；02.所提出的方法不需要手动标签（以自我监督的方式进行训练），也不需要真实数据（模型使用人工数据进行训练）；03.实验方案从单页扩展到更现实和耗时的多页多文档重建；04.我们的方法将推断的复杂度线性扩展，而不是像当前最先进的方法那样二次扩展，对于505个碎片，速度提升约22倍，对于更多的碎片速度提升更大；0排列搜索0兼容性评估0输入碎片0重建0负面积极0图1.自动文档重建的经典方法。碎片的兼容性被逐对评估，然后进行优化搜索过程（基于兼容性值），以找到最能代表原始文档的碎片排列。02. 问题定义0为了简单起见，让我们首先考虑所有碎片属于同一页的情况：条带碎纸文档的单页重建。设 S = { s 1 , s 2 , . . . , s n }表示由纵向撕碎（条带切割）单页得到的 n个碎片的集合。假设索引确定了碎片的真实顺序： s 1是最左边的碎片， s 2 是 s 1 的右邻居，依此类推。一对( s i , s j ) - 表示 s j 放在 s i 右边 - 如果 j = i + 1，则称为“正面”，否则称为“负面”。重建问题的解可以表示为碎片集合 S 的排列 π S = ( s π 1 , s π 2 , . . . , s πn ) 。完美的重建是对于所有 i = 1 , 2 , . . . , n ，都有 π i= i 。自动重建经典上被表述为一个优化问题[18,24]，其目标函数来自逐对兼容性（图1）。兼容性或成本，根据不同的视角，由一个函数 c : S × S → R给出，该函数量化了将两个碎片并排放置时的（不）适配程度（顺序很重要）。假设成本解释， c ( s i , s j ) ， i � = j，表示将 s j 放在 s i 右边的成本。理论上，当 j = i +1 时（正面对）， c ( s i , s j )应该很低，其他情况下（负面对）应该很高。通常，由于重建问题的非对称性质， c ( s i , s j ) � = c ( s j , s i )。成本值是搜索过程的输入，旨在找到最佳排列 π � S，即最能类似原始文档的碎片排列。要最小化的目标函数 C是仅对解中连续碎片计算的累积成本：0相同的优化模型可以应用于从一个或多个文档中重建多个碎纸页（多页重建）。在更严格的公式化中，这种情况下的完美解决方案可以表示为一系列碎片，它们在每一页中都遵守地面真实顺序，以及页面本身的预期顺序（如果有的话）。如果页面顺序不重要（或不适用），则可以放宽对碎片的正对定义，例如，如果s i和sj分别是不同页面的最后一个和第一个碎片，即使j ≠ i +1，也可以将一对（s i，sj）视为正对。最小化方程1的优化问题已在文献中广泛研究，主要使用遗传算法[4, 10, 11,35]和其他元启发式算法[2, 25,27]。然而，本文的重点是碎片之间的兼容性评估（即函数c），这对于准确重建至关重要。̸�c(si, sj) ∝ φ(ei, ej),(2)143450图2.用于碎片兼容性评估的度量学习方法。从兼容区域生成的嵌入应该在嵌入空间中更接近，而来自不匹配区域的嵌入应该相距较远。0本文正是解决可扩展性问题。尽管我们的自监督方法与他们的工作有一些相似之处，但训练范式完全不同，因为这里的深度模型不提供兼容性（或成本）值。相反，深度模型用于将像素转换为嵌入表示，以便可以应用简单的距离度量来衡量碎片的兼容性。下一节将对此进行详细说明。0为了解决文本文档的问题，文献从像素级相似度度量的应用[3, 11,17]开始演变，这些方法快速但不准确，逐渐发展到笔画连续性分析[12, 23]和符号级匹配[22,34]。然而，由于物理碎纸损坏了碎片的边界，无法确保碎片之间的笔画连续性。基于符号级特征的技术往往更加稳健。然而，它们可能难以在复杂文档中分割符号，并且难以有效处理符号形状和大小的广泛变化。这些问题在[21]中得到了解决，其中深度学习成功地用于准确重建条带碎纸文件。然而，对于多页重建，兼容性评估所需的大量网络推理限制了可扩展性。0所提出的兼容性评估方法的一般直觉如图2所示。基本假设是，如果两个并排的碎片在接触边界上局部匹配，那么它们在全局上是兼容的。局部方法依赖于从边界区域裁剪的小样本（用x表示）。样本首先通过将它们投影到一个公共嵌入空间Rd上来转换为中间表示（用e表示）。投影是通过两个模型（CNN）完成的：f left和f right，f •：x →e，分别专门用于左边界和右边界。假设这些模型经过适当的训练，边界样本（在图2中用橙色和蓝色区域表示）然后被投影，从而在这个度量空间中，由兼容区域生成的嵌入应该更接近，而不匹配区域的嵌入应该更远。因此，一对碎片的全局兼容性是根据相应嵌入之间的距离来衡量的。更正式地说，方程1中的成本函数如下：03. 通过深度度量学习进行兼容性评估0所提出的兼容性评估方法的一般直觉如图2所示。基本假设是，如果两个并排的碎片在接触边界上局部匹配，那么它们在全局上是兼容的。局部方法依赖于从边界区域裁剪的小样本（用x表示）。样本首先通过将它们投影到一个公共嵌入空间Rd上来转换为中间表示（用e表示）。投影是通过两个模型（CNN）完成的：f left和f right，f •：x →e，分别专门用于左边界和右边界。假设这些模型经过适当的训练，边界样本（在图2中用橙色和蓝色区域表示）然后被投影，从而在这个度量空间中，由兼容区域生成的嵌入应该更接近，而不匹配区域的嵌入应该更远。因此，一对碎片的全局兼容性是根据相应嵌入之间的距离来衡量的。更正式地说，方程1中的成本函数如下：0其中 e • 表示与碎片 s • 相关联的嵌入，φ是一个距离度量（例如，欧氏距离）。这个评估过程的有趣特性是，投影步骤可以与距离计算分离开来。换句话说，该过程的规模是线性的，因为每个碎片只被每个模型处理一次，并且可以使用生成的嵌入进行成对评估。在深入了解评估的细节之前，我们首先描述这些模型的自监督学习。然后，将介绍更详细的评估视图，包括在方程1中组成目标函数的成本函数的正式定义。03.1. 学习投影模型0为了生成碎片的嵌入，模型 f left 和 f right 同时使用小的 s × s样本进行训练。这两个模型具有相同的完全卷积架构：一个用于特征提取的基础网络，附加一个卷积层。添加的层在基础网络输入 s × s样本时，被设计为工作在全连接层的方式。然而，由于模型专门处理碎片的不同侧面，因此禁用了权重共享，从而实现了深度非对称度量学习。基础网络包括 SqueezeNet [13]架构的前三个卷积块（即直到 fire3 块）。SqueezeNet在区分上下文中的有效和无效符号模式方面已被有效使用。然而，初步评估表明，度量学习方法在较浅的模型上更有效，这解释了仅使用前三个块的原因。为了将其投影到 R d空间，基础网络上添加了一个具有 d 个尺寸为 s/4 × s/4（当基础网络输入 s × s样本时）的卷积层和 sigmoid激活函数。图3概述了从数字文档中提取样本进行自监督学习的模型。首先，模拟碎纸过程，将数字文档切割成形状相等的矩形“虚拟”碎片。接下来，将同一页的碎片并排放置，并沿着接触边从上到下提取样本对：一个样本来自左侧碎片的最右侧的 s个像素（r-样本），另一个样本来自右侧碎片的最左侧的 s个像素（l-样本）。由于虚拟碎纸提供了碎片的邻接关系，样本对可以自动标记为“正面”（绿色框）或“负面”（红色框）。自监督正是因为标签是通过利用数据的内在属性自动获取的。训练数据包括元组 ( x r , x l , y ) ，其中 x r 和 x l 分别表示样本对的 r-样本和l-样本，y 是相关的真实标签：如果样本对是正面的，则 y = 1 ，否则 y = 0。训练使用对比损失函数 [7] 进行驱动：... ...... ...L(fleft, fright, xl, xr, y) =12{(1 − y) · dist2+y · [max(0, m − dist)]2},(3)111143460文件0正面的0负面的0训练样本提取0虚拟碎纸0训练好的模型0图3. 从数字文档中提取样本进行自监督学习的模型。0兼容性评估中有效和无效符号模式之间的区分。然而，初步评估表明，度量学习方法在较浅的模型上更有效，这解释了仅使用前三个块的原因。为了将其投影到 R d空间，基础网络上添加了一个具有 d 个尺寸为 s/4 ×s/4（当基础网络输入 s × s 样本时）的卷积层和 sigmoid激活函数。图3概述了从数字文档中提取样本进行自监督学习的模型。首先，模拟碎纸过程，将数字文档切割成形状相等的矩形“虚拟”碎片。接下来，将同一页的碎片并排放置，并沿着接触边从上到下提取样本对：一个样本来自左侧碎片的最右侧的 s个像素（r-样本），另一个样本来自右侧碎片的最左侧的 s个像素（l-样本）。由于虚拟碎纸提供了碎片的邻接关系，样本对可以自动标记为“正面”（绿色框）或“负面”（红色框）。自监督正是因为标签是通过利用数据的内在属性自动获取的。训练数据包括元组 ( x r , x l , y ) ，其中 x r 和 xl 分别表示样本对的 r-样本和 l-样本，y是相关的真实标签：如果样本对是正面的，则 y = 1 ，否则y = 0 。训练使用对比损失函数 [7] 进行驱动：0其中 dist = ∥ f left ( x l ) − f right ( x r ) ∥ 2 ，m是边界参数。为了更好地理解，图4提供了一个示例。模型处理一个正面的样本对，这两个样本组成了“word”模式。由于是正面的（ y = 1 ），如果生成的嵌入在 R d中接近，损失值将很低，否则将很高。请注意，权重共享会导致交换样本（模式“rdwo”）的损失值相同，这对于重构应用是不可取的。样本提取和训练过程的实现细节在实验方法（第4.3节）中描述。0wo rd0rd0wo0损失0图4.用于碎片兼容性评估的学习投影模型。这些模型与由对比损失函数引导的样本对共同训练。损失函数的输入向量被编码为1 × 1 ×d张量。0距离0图5. 一对碎片的兼容性评估。局部嵌入由h' × 1 ×d张量L和R沿边界区域提取。兼容性是由L和R之间的平方欧氏距离（在展平的张量上计算）给出的实数值。03.2. 兼容性评估0在兼容性评估中，碎片的嵌入和距离计算是两个解耦的步骤。图5展示了这两个步骤的联合视图，以更好地理解模型的运作方式。完全卷积模型隐式执行分步滑动窗口。为了实现这一点，从碎片的边界上裁剪出两个垂直居中的h ×s感兴趣区域（s是样本大小）：Xr，包括左碎片的最右边的s个像素，以及Xl，包括右碎片的最左边的s个像素。对模型进行推断会产生h' × 1 × d特征体积，由张量L = fleft(Xl)（左嵌入）和R = fright(Xr)（右嵌入）表示。从张量的顶部到底部的h'行正好表示图2中所示的d维局部嵌入的自上而下的顺序。如果假设碎片之间的垂直不对齐不重要，可以通过简单地计算∥R -L∥2来获得兼容性。为了更稳健地定义，可以在图像域中将碎片垂直“移动”以考虑不对齐[21]。或者，我们建议将张量L“向上”和“向下”移动δ个单位（限制为δ max）以确定最佳配对，即产生最低成本的配对。这种形式有助于节省时间，因为它不需要对模型进行新的推断。给定一个张量T = (T i,j,k) h' × 1 × d，令T a:b = (T i,j,k) a ≤ i ≤ b, j= 1, 1 ≤ k ≤ d表示从第a行到第b行的垂直切片。0a to b . 让R(i)和L(j)分别表示一对碎片(s i, sj)的r嵌入和l嵌入。当偏移量为c↑(si, sj) =min0≤δ≤δmax143470限制在向上方向，兼容性由以下函数定义：0��� R(i) 1:1+ n rows - L(j) 1+ δ:1+ n0(4) 其中 n rows = h' - δ max是用于距离计算的有效行数。类似地，对于向下方向：0��� 2 (5)最后，所提出的成本函数是方程（4）和（5）的直接组合：0c(s i, s j) = min(c↑(s i, s j), c↓(s i, s j)). (6)0请注意，如果将δ max 设置为0（即不允许偏移），则nrows = h'，因此：0c(i, j) = c↑(i, j) = c↓(i, j) = ��� R(i) - L(j) ��� 2. (7)04. 实验方法0实验旨在评估所提方法的准确性和时间性能，以及与Paix˜ao等人提出的深度学习方法[21]（以下简称为Paix˜ao-b）在文档重建方面的文献进行比较。为此，我们遵循[22]中提出的基本协议，将方法与精确优化器耦合，并在两个数据集（D1和D2）上进行测试。这里考虑了两种不同的情景：单页和多页重建。04.1. 评估数据集0D1. 由Marques和Freitas[17]制作，包含60个扫描分辨率为300dpi的碎纸页。大多数页面来自学术文献（例如书籍和论文），其中部分页面属于同一文档。此外，39个实例仅包含文本内容，而其他21个实例包含一些图形元素（例如表格、图表、照片）。尽管使用了真实的机器（CadenceFRG712），但碎片的尺寸和形状几乎是均匀的。此外，大多数情况下文本方向几乎是水平的。0D2。这个数据集由Paix˜ao等人制作[22]，包括来自ISRI-TkOCR收藏品[19]的20个单页文档（法律文件和商业信函）。这些页面是用Leadership7348条带切割机切碎的，它们的碎片被排列在一张黄色支撑纸上，以便一次扫描，并且可以很容易地从背景中分割出来。与D1相比，D2的碎片形状不太均匀，边界明显更多0由于机器刀片磨损，D2的碎片可能会受损。此外，在扫描之前处理碎片会导致碎片之间轻微的旋转和（垂直）不对齐。与D1相比，这些因素使D2成为一个更加真实的数据集。04.2. 准确度度量0与邻居比较度量[1]类似，解的准确性在这里被定义为相邻碎片对中“正”的比例。对于多重重建，假设“正”的放松定义如第2节所讨论的那样，即页面出现的顺序是无关紧要的。更正式地说，令πS=（sπ1，sπ2，...，sπn）为一组碎片S的重建问题的解。然后，计算πS的准确性为0accuracy(πS) = 10n - 10i = 1 1 [(sπi，sπi +0(8)其中1[∙]表示0-1指示函数。04.3. 实现细节0样本提取。训练数据由从IIT-CDIP测试集合1.0[15]的100个二进制文档（表格，电子邮件，备忘录等）中提取的32×32个样本组成。对于采样，页面被纵向分割为30个虚拟碎片（估计的常规A4纸碎纸机数量）。接下来，使用Sauvola算法[26]对碎片进行个别阈值处理，以应对原始图像像素值的小波动。样本对是逐页提取的，这意味着一对样本来自同一文档。提取过程从相邻碎片开始，以收集正样本对（每个文档限制为1000对）。随后收集负样本对，但限制为正样本对的数量。在提取过程中，从上到下扫描碎片，每两个像素裁剪一个样本。具有超过80％空白像素的对被认为是模糊的，然后被丢弃以供将来训练。最后，通过在r样本的最右两个像素和l样本的最左两个像素上应用盐和胡椒随机噪声，粗略模拟机械碎纸造成的损坏。0训练。训练阶段利用从100个数字文档集合中提取的样本对。从整个集合中，随机选择的10个文档的样本对被保留用于验证，最佳时期模型应该被选择。默认情况下，嵌入维度d设置为128。模型从头开始训练（即权重随机初始化）进行100个时期的随机梯度下降（SGD）训练，学习率为10-1，小批量大小为1https://github.com/thiagopx/deeprec-cvpr20.143480256。每个时期结束后，模型的状态被存储，并且训练数据被重新洗牌以进行新的时期（如果有的话）。最佳时期模型选择基于将正样本对在嵌入空间中投影得更近，负样本对则远的能力。这通过标准化的均值差异（SMD）度量[8]来量化，具体如下：对于给定的时期，将f left和fright模型分别用验证样本对进行馈送，并测量相应嵌入之间的距离。然后，将距离值分为两组：dist+，包括计算正样本距离的距离，和dist-，用于负样本。理想情况下，两组的均值之间的差异应该很大，而组内的标准差应该很小。由于这些假设在SMD中得到了解决，最佳的f left和f right被认为是最大化SMD(dist+，dist -)的模型。04.4. 实验0实验依赖于训练好的模型f left和fright，以及Paix˜ao-b的深度模型。后者在CDIP文档上进行了重新训练（按照[21]中描述的过程），以避免使用相同集合（ISRIOCR-Tk）的文档进行训练和测试。实际上，使用这种方法对重建准确性没有明显变化。评估数据集的碎片也被二值化[26]，以保持与训练样本的一致性。所提出方法的默认参数包括d = 128和δ max =3。在三个进行的实验中，考虑了非默认分配，如下一小节中更详细地描述。0单页重建。该实验旨在展示所提出方法是否能够以与Paix˜ao-b相似的准确性单独重建页面，并且当启用垂直位移功能时，两种方法的时间性能如何受到影响，因为它增加了成对评估的数量。为此，使用所提出的方法和Paix˜ao-b方法分别对D1和D2的碎片页面进行了单独重建，首先使用它们的默认配置，然后禁用垂直位移（在我们的情况下，等同于设置δ max =0）。每次运行都测量了时间和准确性。为了进行更详细的分析，对于每个重建阶段都进行了时间测量：投影（pro）-仅适用于所提出的方法-，成对兼容性评估（pw）和优化搜索（opt）。0多页重建。该实验重点是在增加多页重建的碎片数量时，与时间的可扩展性。除了时间性能外，确认两种方法的准确性是否保持可比性也是至关重要的。0方法 D1 ∪ D2 D1 D20所提出的方法 93.71 ± 11.60 93.14 ± 12.93 95.39 ± 6.02 Paix˜ao-b [21] 96.28± 5.15 96.78 ± 4.44 94.78 ± 6.78 Paix˜ao et al. [22] 74.85 ± 22.50 71.85 ±23.14 83.83 ± 18.12 Marques and Freitas [17] 23.90 ± 17.95 29.18 ± 17.438.05 ± 6.600表1. 单页重建性能：平均准确性±标准差（%）。0与单个页面相比，该实验中有两个大型重建实例：D1的1,370个混合碎片和D2的505个混合碎片。每个实例都使用所提出的方法和Paix˜ao-b方法进行重建，但现在只使用它们的默认配置（即启用垂直位移）。测量了准确性和时间（按阶段分段）。此外，根据观察到的D2的平均经过时间，估计了不同实例大小的处理时间。0敏感性分析。最后一个实验评估了不同嵌入维度（d）（2，4，8，...，512）对所提出方法的影响（时间和准确性）。请注意，这要求对每个d重新训练f left和fright。训练后，分别重建了D1和D2实例，然后测量了准确性和处理时间。04.5. 实验平台0实验在一台配备有16GB RAM的Intel Core i7-4770 CPU@ 3.40GHz上运行的Linux Ubuntu16.04系统中进行，配备了一块12GB内存的TITAN X(Pascal) GPU。实现1使用Python3.5编写，使用Tensorflow进行训练和推断，使用OpenCV进行基本图像处理。05. 结果与讨论05.1. 单页重建0将单页重建条带碎片文档与文献进行比较的结果总结在表1中。鉴于性能的明显改进，接下来的讨论将重点放在与[21]的比较上。图6中的箱线图显示了所提出方法和Paix˜ao-b在单页重建中获得的准确性分布。与[21]类似，我们也观察到垂直位移仅影响D2，因为D1的碎片在垂直方向上几乎对齐。对于数据集D2，两种方法的准确性没有显著差异。然而，对于D1，Paix˜ao-b略优于我们的方法：默认配置（启用垂直位移）的所提出方法的准确性为93.14 ±12.88%（算术平均值±标准差），而Paix˜ao-b达到了96.78 ± 4.44%。我们的方法的变异性较高。02040608010000.51.01.502.55.07.510020406080143490垂直偏移开关0准确率（%）0D10垂直偏移开关0D20方法0提出的Paix˜ao-b0图6.使用提出的方法和Paix˜ao-b方法进行单页重建的准确性分布。准确性按文档计算，红色虚线表示平均值。0提出的Paix˜ao-b方法0时间（秒）0垂直偏移（关闭）0提出的Paix˜ao-b方法0垂直偏移（开启）0阶段0propwopt0图7.单页重建的时间性能。堆叠的柱状图表示每个重建阶段的平均耗时：投影（pro）、两两兼容性评估（pw）和优化搜索（opt）。0主要是由于存在大面积由填充图形元素（如照片和彩色图表）覆盖的文档（在训练中不存在）所致。通过排除这些情况（60个样本中的12个），我们的方法的准确率提高到95.88％，标准差降低到3.84％。时间性能如图7所示。堆叠的柱状图表示每个重建阶段的平均耗时（秒）：投影（pro）、两两兼容性评估（pw）和优化搜索（opt）。在禁用垂直偏移的情况下（左图），提出的方法在生成嵌入（1.075秒）方面花费的时间比两两评估（0.063秒）和优化（0.092秒）要多得多。尽管Paix˜ao-b没有嵌入投影的成本，但两两评估花费了1.481秒，大约是我们方法中相同阶段所花费时间的23倍。当两两评估的数量增加时，这种差异变得更加显著（在绝对值上），如右图所示。在这种情况下，我们方法的两两评估花费了0.389秒，而Paix˜ao-b花费了10.197秒（大约慢26倍）。包括投影阶段的执行时间，我们的方法在兼容性评估方面加快了近7倍的速度。请注意，如果没有垂直偏移，Paix˜ao-b的准确率将下降0提出的Paix˜ao-b方法0时间（分钟）0n = 5050阶段0propwopt030 100 200 300 400 500 n0≈ 1页0n = 1, 2, ..., 5050方法0提出的Paix˜ao-b0图8.多页重建的时间性能。左图：重建D2（505个碎片）所需的每个阶段的时间。右图：预测的处理时间与碎片数量的关系。0D2的准确率从94.77％下降到86.74％。最后，我们展示了嵌入空间可能的样子，通过展示一个局部样本及其三个最近邻。如图9所示，模型倾向于形成类似真实的配对。值得注意的是，即使在样本略微向上或向下偏移且字母仅出现在一半的情况下，样本在垂直方向上仍然非常对齐（请参阅补充材料中的更多样本）。05.2. 多页重建0对于多页重建，提出的方法分别在D1和D2上实现了94.81％和97.22％的准确率，而Paix˜ao-b分别实现了97.08％和95.24％。总体而言，两种方法都能以较高的准确性（约±2个百分点的差异）进行高质量的重建，这表明它们的准确性不受实例增加的影响。然而，就时间效率而言，两种方法明显不同，如图8所示。左图显示了处理D2的505个碎片所需的每个阶段的平均耗时。在这种情况下，随着碎片数量的增加，优化成本相对于两两评估所需的时间变得可以忽略。值得注意的是，Paix˜ao-b需要超过80分钟才能完成评估，而我们的方法只需不到4分钟（加速约22倍）。根据投影和两两评估的平均时间，绘制了估计曲线（右图），指示了预测的处理时间与碎片数量（n）的关系。从比较的角度来看，提出的方法的曲线增长似乎是线性的，尽管两两评估时间（而不是推理次数）与n的平方成正比。总之，碎片数量越多，加速比越高。05.3. 敏感性分析0图10显示了单页重建中准确性和处理时间（页面平均值）如何变化808590951001.52.02.5143500图9.本地样本最近邻。在顶部一行中，最大的正方形是“查询”样本（二值化之前），下面是其二值化版本和其三个最近邻样本并排显示（最接近的样本在顶部一行）。蓝色和橙色样本分别由f right和f left投影。底部一行显示了一些由f left投影的示例。01 2 3 4 5 6 7 8 9 log 2 (d)0准确率（%）0数据集0D1D20处理时间0图10.关于嵌入维度（d）的敏感性分析。最佳准确率观察到的是d=8：D1和D2分别为94.57%和97.27%。这种减小的嵌入尺寸减少了处理时间的23%。0受嵌入维度（d）的影响。值得注意的是，投影到2维空间（d =2）就足以实现平均准确率超过90%。最高准确率观察到的是d = 8：D1和D2分别为94.57%和97.27%。此外，当d =8时，平均重建时间为1.224秒，相对于默认值（128）减少了近23%。对于更高的维度，准确率趋于缓慢下降（除了d=256）。总体而言，结果表明通过关注较小的d值可以改善准确性和处理时间，这将在未来的工作中进行更深入的研究。06. 结论0本研究解决了机械碎纸文档重建的问题，更具体地说是评估碎片之间的兼容性的关键部分。我们关注的是评估的时间性能。为了改进它，我们提出了一种基于深度度量学习的方法作为兼容性函数，其中的数量是0推理的数量与重建实例的碎片数量呈线性而不是二次比例[21]。此外，所提出的方法是通过人工生成的数据进行训练的（即不需要真实世界的数据），并且是自我监督的（即不需要注释）。对于单页重建的比较实验表明，所提出的方法在兼容性评估上可以达到与最先进方法相当的准确性，速度提升约为7倍。此外，本研究将实验协议扩展到了更现实的场景：多页多文档重建。在这种情况下，所提出方法的好处更大：我们的兼容性评估方法在20页的情况下只需不到4分钟，而当前最先进方法的近似时间为1小时20分钟（80分钟）（即加速约为22倍），同时保持高准确性（97.22%）。此外，我们还表明嵌入维度对我们方法的性能并不关键，尽管更仔细的调整可以提高准确性和时间性能。未来的工作应包括将所提出的方法推广到其他类型的切割（例如交叉切割和手撕切割），以及其他与拼图问题相关的问题[1]。0致谢0本研究部分资金由巴西高等教育协调委员会（CAPES）资助（资助代码001）。我们感谢NVIDIA提供用于此研究的GPU。我们还感谢巴西国家科学和技术发展委员会（CNPq）支持的研究生产力奖学金（311120/2016-4和311504/2017-5）。143510参考文献0[1] F. Andal´o, G. Taubin, and S. Goldenstein. PSQP:二次规划解决拼图问题. IEEE Trans. Patt. Anal. Mach. Intell. ,39(2):385–396, 2017. [2] H. Badawy, E. Emary, M. Yassien, andM. Fathi. 用于重建碎纸文档的离散灰狼优化. In高级智能系统和信息国际会议 , pages 284–293, 2018. [3] J.Balme. 在没有形状信息的情况下重建碎纸文档. 技术报告,工作论文, 耶鲁大学计算机科学系, 美国, 2007. [4] B. Biesinger, C.Schauer, B. Hu, and G. Raidl.使用解决方案存档增强遗传算法以重建交叉切割碎纸文本文档. In计算机辅助系统理论国际会议 , pages 380–387, 2013. [5] J.Bromley, I. Guyon, Y. LeCun, E. S¨ackinger, and R. Shah.使用“Siamese”时延神经网络进行签名验证. In神经信息处理进展国际会议 , 1994. [6] G. Chen, J. Wu, C. Jia, andY. Zhang. 用于重建交叉碎纸英文文档的流水线. In图像、视觉和计算国际会议 , pages 1034–1039, 2017. [7] S.Chopra, R. Hadsell, and Y. LeCun.通过辨别性学习相似度度量，应用于人脸验证. In计算机视觉和模式识别会议(CVPR) , pages 539–546, 2005. [8] J.Cohen. 行为科学的统计功效分析. 技术统计学 , 31(4):499–500,1988. [9] J. Delk. FBI正在重建Cohen突击搜查中获得的碎纸文档.The Hill , 2018年5月. [10] Y. Ge, Y. Gong, W. Yu, X. Hu, and J.Zhang. 重建交叉切割碎纸文本文档:一种具有拼接驱动繁殖的遗传算法. In遗传和进化计算国际会议(GECCO) , pages 847–853, 2015. [11] Y.Gong, Y. Ge, J. Li, J. Zhang, and W. Ip.一种基于拼接驱动的记忆算法用于重建交叉切割碎纸文本文档.应用软件计算 , 45:163–172, 2016. [12] S. Guo, S. Lao, J. Guo,and H. Xiang.用于重建交叉切割碎纸文本文档的半自动解决方案存档. In图像和图形国际会议 , pages 447–461, 2015. [13] F. Iandola, S.Han, M. Moskewicz, K. Ashraf, W. Dally, and K. Keutzer.SqueezeNet:具有50倍少参数和<0.5MB模型大小的AlexNet级别准确性.arXiv预印本 arXiv:1602.07360 , 2016. [14] E. Justino, L. Oliveira,and C. Freitas. 通过特征匹配重建碎纸文档. 法医科学国际 ,160(2):140–147, 2006. [15] D. Lewis, G. Agam, S. Argamon, O.Frieder, D. Grossman, and J. Heard.为复杂文档信息处理构建测试集合. In信息检索研究和发展国际会议 , pages 665–666, 2006. [16] H. Linand W. Fan-Chiang. 基于图像特征匹配的碎纸文档重建.专家系统与应用 , 39(3):3324–3332, 2012. [17] M. Marques andC. Freitas. 文档解密-恢复: 基于颜色的条带碎纸文档重建.IEEE拉丁美洲交易 , 11(6):1359–1365, 2013. [18] W. Morandell.条带碎纸文本文档的评估和重建. 硕士论文,维也纳工业大学计算机图形和算法研究所, 2008.0[19] T. Nartker, S. Rice, and S. Lumos.用于研究和测试页面阅读OCR系统的软件工具和测试数据. InElectron. Imag. , 2005. [20] H. Oh Song, Y. Xiang, S. Jegelka,and S. Savarese. 基于提升结构特征嵌入的深度度量学习. In计算机视觉和模式识别会议(CVPR) , pages 4004–
我的内容管理
展开
