论文翻译：历史文档字体的参数化复刻概念验证
字体排印的逆向工程（第一阶段）：
从历史文档中提取字体参数的概念验证
摘要
本文报告了一个完全逆向工程方法的第一阶段，该方法旨在构建一套完整一致的排印参数，这些参数定义了均质印刷文本中使用的字体。应强调的是，不能理所应当地期望这一流程是完全自动的，流程设计中需包括与人的交互。尽管字体设计受制于一组相当坚固合理的几何规则，但它仍严重依赖主观的人类理解。此外，应用于普遍规则的不同参数实际上可能会导致非常相似的、在视觉上难以区分的字体，这会使这个逆向工程成为一个条件受制的逆问题——一旦出现了（与打印或扫描过程有关的）形状变形的话。
这项工作是一个长期迭代过程的第一阶段，在此过程中，我们将从最适合我们问题的最新技术中逐步研究和评估，并在其被证明不适用时探索新的方向。作为第一步，本文更像是一种对可行性的概念验证，使我们能够明确在后续迭代中需要进行更深入研究的项目。
1. 介绍
1.1 背景与动机
这项工作的最初动机是 “数字人文科学”，以及对十五和十六世纪的早期印刷品的研究。文字排印的物理约束——受制于当时的排印工艺，以及书法和既有铅字字形的影响——决定了在文字排印初期最早的字体是如何开发出来的，而在此期间诞生的设计规则，仍然主宰着现代字体设计使用的几何规则。
试图从现存原始文档中回溯字体参数，对历史学家和字体设计师来说是有价值的，可有效应用于数字图书馆的文档编码和压缩。对于历史学家来说，可以从字形的演变以及各种印刷细节或特征中很好地观察到，不同的早期印刷者和字体设计师之间的影响，以及这项工艺如何发展成熟。它提供了有价值的信息，说明技术如何演化以及它们如何受到其他影响或如何影响了未来的发展。它指出欧洲文艺复兴时期的交流、艺术流动或迁移的迹象。对于现代字体设计师来说，重新审视现有字体的起源可能是灵感的来源，也是一个促进新字体创意和设计的研究领域。将扫描的印刷文本直接简易转换为可用字体的工具目前还不存在，但这会有巨大的前景，并为现代设计师带来生产力的飞跃。就数字图书馆而言，明显的优势是能够为上下文可视化提供适当的文档编码[1]。这个工具既不提供历史印刷品的扫描像素图版本，也不提供在视觉上不能代表原始文本的 OCR（经过光学字符识别的）版本，而是重新创造一套视觉上令人满意的原始字体的现代版本，从而极大地增强用户的阅读体验。例如，Marc Smith 分辨了历史文档可转录的四个级别[2]。我们将这些发现转换到历史数字化文档的用户交互环境中去:
• 传真摹本：与原始文件保持最大的相似性（包括纸张上的缺陷或污点等），通常通过高分辨率扫描获取；
• 如实或保守的转录：提供一个 OCR、可搜索的文本，通常没有原始文档中最明显的缺陷，但意在试图提供一种与原始文档接近的视觉呈现（尤其是在字体和字符方面，并保持拼写和特殊字符使用不变）；
• 当代转录：使用当代拼写，纠正可能存在的拼写错误或重新解读已不再使用的特殊符号或字符，偏向可读性，而不一定保持与原文的视觉相似性;
• 翻译：使用当代词语转译。
我们的做法处于 “如实或保守的转录” 级。图 1 举例了对米歇尔·德·蒙田（Michel de Montaigne）《随笔集》（Essays）的多种可能转录[3]。在本文中，我们将使用此版本的节选。
图1. 给定文档[2]的不同转录级别（这里是蒙田1635年版的《随笔集》）。从上到下：传真摹本、OCR、当代转录和翻译
1.2 最新技术
1.2.1 文档图像分析
字体分析是文档图像分析中很少涉及的一个主题，但有两个值得注意的例外：OCR[4][5]的字体多样性处理和字体识别（主要用于文档内容分类），前者是试图把字体结构的元素提供给 OCR 引擎，使其在处理不同字符形状时更可靠；后者是识别已知字体的实例[6]–[9] ，与我们在此要实现的目标完全不同。第一种情况，主要目的更多是从某些字体（typeface）及它们各自的字型（font）中提取足够的不变特征，以确定如何最好描述每个字符。换句话说，OCR 中字体多样性的主要目的是忽略字体之间的区别。在第二种情况下，目的是根据一组已知字体对文本进行判别。在这种情况下，事实上并不一定要显示字体特征，而是要确定字体实例之间的距离度量。
这些方法不能解决我们试图在这里讨论的问题。我们的主要目的是从被扫描的字符形状中提取字体排印上的重要信息，并尽可能地重建整个字型的（或者可能的话字体的）描述。这种尝试非常罕见[10]–[12]。
我们的方法更接近于此[12]。它不仅通过探讨基本的排印指标，还通过研究更细致的大小和形状关系结构来扩展其范围，不只恢复与总体字符形状大小有关的可识别特征，而且还为字体形状和形式进行逆向工程奠定了基础。
1.2.2 排版
虽然字体设计无疑是一个依赖于创作者感性的创作过程，也是一个艺术过程，但它是建立在一套一致的规则和度量标准之上的，可以作为图像分析的基础。反过来说，这些规则不能被认为是普遍适用的或有效的，因为艺术创作必然会将颠覆式创新与既定的规则结合起来。因此，以下不变量或度量的列表只能被视为一组通用的指导方针，而不是一个绝对的规则。这也解释了为什么我们的目标是一个集成用户反馈的整体过程，而不是期望开发一个完全自动化的算法。
图2. 排在铅版上铅字图片。这是由 Stanley Morison 在 1932 年为 Monotype 设计的 Times New Roman 铅字
1. 版面高度通常是字体最可靠的固定属性。字体的版高直接来自于排版的原始约束，其中铅字被排在版面上，并且内部需要保持对齐。这在图 2 中有所说明，显示了带有实际排印用铅字字型的铅板。人们可以清楚地分辨出各个字块，它们都具有相同的高度，因此可以完美地水平排列。
版高与字面高直接相关，并引入了强制性的限制条件，即最大允许的上升部和下降部高度以及行间距。
2. 作为上一点的结果，可以得出许多支持字体的主要尺寸的辅助线[13]。如图 3 所示。
3. 一旦确定了主要的高度和宽度，字体的许多结构特征将会在在所有字符上都具有一致的展现。如图 4 所示，笔画宽度、弧线的曲率、字干倾斜、衬线等共享属性，使字体平衡、清晰。对于类似的字符（例如 “n” 和 “m”，或 “b”、“d” 和 “p”）可以重复使用相同的几何特征，因此可以很容易地派生。[11]
图3. 主要印刷尺寸，如[13]
图4. 各种特征部分的参数（宽度、长度、倾斜度……）决定了字体
尽管字体设计有良好的结构基础，并可以用几何的方式描述字体，但是对印刷实例的逆向工程仍处境艰难。Erik Van Blokland 的实验为这样的处境提供了一个经验证明。该实验请大量专业的字体设计师对某字体进行逆向工程[14]。他们被给予一种特定字体的印刷实例，并被要求构思该实例的数字化版本。数字化版本由一系列模拟字体轮廓的贝塞尔曲线组成。图 5 显示了其结果之一，其中叠加了大约 50 个字母 “n” 的重构：灰色线是贝塞尔曲线轮廓，深橙色点是控制点，浅橙色点是相应的左右切线控制手柄点。考虑到所有参与者都是专业的字体设计师，观察他们各自理解的差异是非常有趣的，也很容易从这些结果中推断出没有强烈的人类共识。我们可以很明显地观察到控制点的 “簇”，它们往往出现在曲率很强的区域，但不同之处仍然相当大。这些结果也强调了字体设计中不应忽视的一个方面：对印刷物的转录常常发生在重新使用和重新设计的情况下，而不一定是为了完全相同地再现原始形状。因此，我们需要提供一个工具，使人们能够与自动提取的排印参数进行交互。
图5. Erik Van Blokland 的实验结果，要求专业的字体设计师对给定的字体进行逆向工程；圆点是控制点和切线控制手柄点。
译注：同一个 n 的 80 个数字化轮廓的原始位置和标准化处理后的补间动画。[原始视频来源：vimeo.com/60901905]
在接下来的部分中，我们将详细描述如何提取对印刷具有重要意义的度量和形状，这将帮助字体设计师和排版人员使用扫描的字符实例来构建基于原始文本的现代矢量字体。
2. 过程描述
我们将要实现的整个过程如图 6 所示。读者应该明确的是，这目前只是一个概念的证明，将逐步加强和发展。一般的基本思路是设想一个迭代过程，它将依赖于人的交互来指导自动过程，特别是在执行或放宽 §1.2.2 中讨论的一些排版规则方面。
当前版本的操作方式如下:
1. 从扫描的原始文档中，我们使用由法国图尔大学的 Ramel 等人开发的 Agora 和 Retro 软件[15]–[17]。此步骤使我们可以提取文档中使用的所有字符实例，并将它们分组，以获得 “a”、“b”……
该工具在每个提取的字符的页面中提供边界框和位置。所获得的边界框主要取决于原始图像的质量，并且不同的字符实例中将会存在几个像素的差异。此外，生成的剪切图像具有与原始文档相同的分辨率（可能相对较低）。
2. 提取的每个字符，我们将图像放大到更高的分辨率，然后计算所有实例的平均形状。这一部分将在 §3 中更详细地讨论。使用平均图像将平滑由于打印缺陷、老化、渗墨或分割错误造成的噪点和形状变形（参见图 6 中的 y₂、y₄、y₅ 和 y₆）。
图6. 蒙田的《随笔集》页面，在 1635 年第三版中，从中提取出所有印刷字符的实例，并按形状进行分组。对于每个组，计算一个高分辨率的平均形状，从中可以得出与图 4 中的那些有关的进一步具有印刷意义的重要指标。
3. 由于我们的目标是为字体提供丰富的印刷描述，以供设计师随后使用，因此我们需要提取用于字体表示的信息。存在多种表示字体的方法[18][19]，但可以分为三大类：基于轮廓的、基于骨架的和基于组件的。因此，我们计算平均形状的轮廓（§4）和骨架（§5）。然后，这些进一步允许我们开始测量特征形状特征，例如垂直笔划（字干）或曲线（字碗）以及线的粗细及其随笔划的演变。这些信息在图 6 中的 y 字母图形中表示。
一旦执行了这些步骤，我们就可以评估我们方法的稳定性。从那里可提取与字体结构有关的更细节的信息，例如字干和衬线检测，字碗的曲率厚度估计等。这些问题将在§7中说明。
3. 平均图像计算
主要的挑战之一是为所提取的字符计算出一个稳定且分辨率足够高的图像，以便能够获得有用的字体排印信息。如图 6 所示，在 300 或 400dpi 分辨率下扫描的单个字符的质量不足以通过图像分析算法进行直接处理。虽然这在视觉上可能不是很明显，但是提取的字符的平均大小是 22×43 像素，这就不允许对形状参数进行稳定的估计。这不仅仅是扫描分辨率的原因。可以看出，通常在历史文献中发现的许多其他缺陷会影响形状质量：纸张和墨水质量、老化、污点、渗墨…
3.1 图像插值
我们首先通过双线性图像放大来人为地提高图像分辨率。在我们当前的环境中，一方面由于这是一个概念验证阶段，另一方面由于我们知道初始数据是有噪点的，并将在后续阶段进行过滤，另一方面，我们不需要复杂的放大方法。因此，给定一个原始 𝑛 × 𝑚 图像 𝐼，我们将放大的 2𝑛 × 2𝑚 图像 Î 定义为
这种方法可以推广到所需要的任何放大倍数。
3.2 平均图像
为了补偿每个字符在不同形状之间的巨大差异，我们计算了所有实例的平均灰度图像。提高分辨率与平均形状计算的复合结果如图 7 所示。很明显，平均计算极大地改善了形状的规律性，消除轮廓的不平整度，但仍有两个副作用需要观察。
图7. 单个字符实例及其更高分辨率（平均计算对应的字符）之间的比较
首先，我们可以在平均图像的顶部看到伪像。这是由于字符提取过程中产生的切割问题。实际上，各个边界框未进行标准化，并且可能（也可能不会）接触印刷形状。这需要平均算法来推断边界上的像素，对此我们目前尚未实现平滑算法。这个问题将在以后的工作中解决，并且仅与低分辨率图像处理有关。
其次，还有一个 “语义上的” 副作用，它可能对所提取形状文字排印上的理解产生更大的影响。效果在 d 的衬线处最明显。平滑效果有利于消除形状的整体粗糙度，也平滑了字体更突出的特征。由于我们正在处理的文档似乎已经在字母 “d” 中混合了两种略有不同的字体类型（请注意，图 6 中的衬线存在或不存在倾斜：d₁ 和 d₃ 中衬线是水平的；d₂ 和 d₄ 中则是倾斜的），这一事实使情况更加恶化。平均过程将趋于创建两者的平滑组合，这变得与原始版本不一致。对于图 7 中的 “n”，效果则并不明显。
4. 轮廓近似
现在，我们有了清晰和足够一致的数据来处理（不考虑前面提到的字母 “d” 的问题），我们可以开始提取可以描述字体特征的信息。第一步包括使用 B 样条进行字体轮廓矢量化[20][21]。为了实现这一点，我们使用了 Potrace，一个免费的工具，专门针对字符矢量化进行了调整[22]。结果如图 8 所示。它存储为 SVG 格式，可以很容易地导入到字体设计软件中。
图8. 平均形状的 SVG 轮廓近似
在这时，字体设计者可以编辑和校正形状伪像，或调整出先前观察到的平滑效果。正如我们将在 §7 中展示的那样，这些编辑可以进一步用于调整分割和提取过程。观察图8中字母 “n” 的矢量化并将其与 §1.2.2 中所述的实验联系起来也很有趣。事实上，控制点位于人类字体设计师所标识的一般区域中。在这一阶段，不可能进一步评估矢量化相对于人可接受性的感知质量，因为正如我们前面指出的那样，一方面，人的解释标准存在很大差异，另一方面，它们通常与特定的应用环境息息相关。接下来的工作将整合人对该矢量化感知质量的评价。
5. 骨架提取
由于我们需要计算的许多特性（见§1.2.2），甚至像 METAFONT 这样的字体描述语言[23]，都依赖于它们的骨架和相关的笔画宽度所描述的笔画，因此我们还使用 ImageJ 库实现了对平均形状的标准骨架检测[24][25]。结果如图 6 所示。骨架（和相关的距离变换）为笔画宽度计算和字干定位提供了基础。图 6 的下半部分是最大笔画宽度的区域，以及可以识别为直线的骨架部分。
到现在，我们有了所有需要的信息来计算更详细的排印参数，如平均笔划宽度、弧线，字碗
的动态、字干的斜度，等等。
6. 基线计算
分割和字符提取软件的一个缺点是提取的图像片段并不是一致对齐的[15][17]。这反过来又为 §3 中的平均形状计算产生模糊的副作用。
图9. 基线提取算法的说明。红色：平均基线；绿色：中位基线。放大显示的图中，右上反映了中位基线的计算略有优势，而右下则反映了页面曲率的影像。
正如前面所提到的，我们的目标是最终成功地开发一个可交互的过程，这个过程能够在用户所给出文本的指导下，根据之前消除的歧义、错误或不完整数据来完善其各种处理方法。我们的基线计算算法就是这样一个例子。由于之前的提取算法[15][17]已经进行了低级的基线提取，我们可以在此基础上，通过考虑更具体的排印信息来细化结果 。对于历史文档而言，最初提取的基线通常不精确。在我们的案例中，有着很强的过度分割趋势（例如，图 9 中的文档使用标准的提取参数生成 73 个文本行块)，另一方面，它很好地成功地提取了单个字符。
为了完善基线检测，我们的算法通过以下步骤对提取的字符边界框的所有 y 坐标进行 k 均值聚类，步骤如下:
• 检索所有提取的字符边界框的底部 y 坐标，
• 在所有的 y 坐标上进行 k 均值聚类，k 设置为（过度分段的）文本行数[15]-[17]，
• 过滤掉数量较少的分组（在我们的例子中是 < 25）；它们对应着下降部，
• 对于每个剩余的分组，计算 y 的平均值或中位数。
所得结果如图 9 所示。可以注意到，中位数（绿色）比平均值（红色）稍微精确一些。需要注意的是，这种方法假设被扫描文档中的基线是直线，且文档是放在平面上的。在右下角的图 9 中可以看到这种假设的效果，这里的页面曲率影响提取的基线的精度。
7. 讨论及进一步工作
在本文中，我们展示了一组工具的初始概念证明，这组工具最终可从扫描文档中提取字体文字排印上的重要特征。此处展示的平台可用于实验和测试，并将在后续的研究阶段得到扩展。
当前版本扫描目录以查找不同扫描的相似字符的子例，然后对其进行处理提取其平均形状、轮廓、B 样条近似，骨架提取和过滤，以及一些基本的测量值，如最大宽度值和位置。
当然，这并不能算作一个完整的字体逆向工程平台。我们目前正就以下课题进行研究:
1. 如 §6 所述，与计算平均图像相关的主要困难之一是提取的片段并不总是正确对齐。这会导致形状的扩展平滑，使其比预期的更厚，更模糊。使用基线（及其计算的细化）对提取的字符进行对齐是我们正在进行的扩展之一，并结合了基于全局能量最小化的更复杂的对齐算法。
2. 从性能评估的角度来看，我们将使用现代印刷字体对我们的方法进行详尽的评估，为此，我们可以通过将数字字体与使用相同字体的高质量印刷实例中提取的数据进行比较来获得基准真相。从而消除了与文档老化，扫描缺陷，着墨效果和页面弯曲有关的所有误差。
3. 平均图像计算的另一个增强功能是使用中值，而不是平均值。这可以与稳健的离群点检测相结合，期望的结果是能够过滤掉图 6 中字母 “d” 的多次字体冲突所观察到的效果。
4. 更普遍地说，使用精细化和稳定的平均形状或中值形状，可以进一步用于单个字符的差异测量，或用于计算一般文档质量统计数据。然后，这些数据可以反馈到全局图像分析过程，并为检测和提取细化提供一个良性循环。
5. 当前版本只考虑相同字符的类别。然而，从排印的角度来看，在整个字体上都存在一致性，其中涉及到曲率，厚度和倾斜度。因此，我们需要整合字符间约束传播和一致性。可以将所得数据用于循环机制中，以完善和使整个提取和识别过程更可靠。
6. 更深入的研究和后续的图像退化效果建模(与油墨吸收、老化等已知影响有关)可以用于改进的轮廓分割和后续的细化测量过程[26][27]。
[1] Le Bourgeois, F. and Emptoz, H., “DEBORA: Digital AccEss to BOoks of the RenAissance,” International Journal of Document Analysis and Recognition (IJDAR) 9(2-4), 193–221 (2007).
[2] Smith, M., “La typographie face aux écritures anciennes : entre reproduction et transcodage,” Introductory talk at the colloque international Gestion informatisée des écritures anciennes, Université de Tours, Centre d’études supérieures de la Renaissance. (May 2013).
[3] de Montaigne, M., [Les Essais], A Paris, Chez Pierre Rocolet, Imp. & Libraire ordinaire du Roy, au Palais, en la des prisonniers, Paris, 15 juin 1635, chez Toussainct du Bray, ruë Sainct Jacques, aux Espies-meurs et Pierre Ricolet ed. (1580).
[4] Kahan, S., Pavlidis, T., and Baird, H., “On the recognition of printed characters of any font and size,” Pattern Analysis and Machine Intelligence, IEEE Transactions on PAMI-9, 274–288 (March 1987).
[5] Cao, H. and Natarajan, P., “Machine-printed character recognition,” in [Handbook of Document Image Processing and Recognition], Doermann, D. and Tombre, K., eds., 331–358, Springer London (2014).
[6] Wayner, P. and Huttenlocher, D., “Image analysis to obtain typeface information,” (Oct. 12 1993). US Patent 5,253,307.
[7] Zramdini, A. W. and Ingold, R., “Optical font recognition using typographical features,” IEEE Trans. Pattern Anal. Mach. Intell. 20(8), 877–882 (1998).
[8] Zhu, Y., Tan, T., and Wang, Y., “Font recognition based on global texture analysis,” Pattern Analysis and Machine Intelligence, IEEE Transactions on 23, 1192–1200 (Oct 2001).
[9] Jeong, C., Kwag, H., Kim, S., Kim, J., and Park, S., “Identification of font styles and typefaces in printed korean documents,” in [Digital Libraries: Technology and Management of Indigenous Knowledge for Global Access], Sembok, T., Zaman, H., Chen, H., Urs, S., and Myaeng, S.-H., eds., Lecture Notes in Computer Science 2911, 666–669, Springer Berlin Heidelberg (2003).
[10] Shamir, A. and Rappoport, A., “Extraction of typographic elements from outline representations of fonts,” Computer Graphics Forum (proceedings, Eurographics) 15(3), 259–268 (1996).
[11] Herz, I., Coherent Processing of Typographic Shapes, PhD thesis, École Polytechnique Fédérale de Lausanne (1997).
[12] LiVolsi, R., Zanibbi, R., and Bigelow, C. A., “Collecting historical font metrics from google books.,” in [Proceedings of the 21st International Conference on Pattern Recognition, ICPR 2012, Tsukuba, Japan, November 11-15], 351–355, IEEE Computer Society (2012).
[13] Brógáin, S. O., “Typographic measurement: a critique and a proposal,” Professional Printer: Journal of Institute of Printing 27(5), 9–14 (1983).
[14] Van Blokland, E., “On digitization: analysis of the different approaches of several type designers from one single model,” in [Automatic Type Design], Atelier National de Rercherche Typographique, ARTEM, Nancy (6–7 May 2014).
[15] Ramel, J. Y., Busson, S., and Demonet, M. L., “Agora: the interactive document image analysis tool of the BVH project,” in [Document Image Analysis for Libraries, 2006. DIAL ’06. Second International Conference on], 11 pp.–155 (April 2006).
[16] Roy, P. P., Ramel, J.-Y., and Ragot, N., “Word retrieval in historical document using character-primitives,” in [ICDAR], 678–682, IEEE (2011).
[17] Ramel, J.-Y., Sidere, N., and Rayar, F., “Interactive layout analysis, content extraction, and transcription of historical printed books using pattern redundancy analysis,” LLC 28(2), 301–314 (2013).
[18] Haralambous, Y. and Horne, P., [Fonts & Encodings], O’Reilly Series, O’Reilly Media (2007).
[19] Hassan, T., Hu, C., and Hersch, R. D., “Next generation typeface representations: revisiting parametric fonts,” in [Proceedings of the 10th ACM symposium on Document engineering], 181–184, ACM (2010).
[20] Yang, H.-M., Lu, J.-J., and Lee, H.-J., “A bezier curve-based approach to shape description for chinese calligraphy characters,” in [Document Analysis and Recognition, 2001. Proceedings. Sixth International Conference on], 276–280 (2001).
[21] Sarfraz, M. and Khan, M., “An automatic algorithm for approximating boundary of bitmap characters,” Future Generation Computer Systems 20(8), 1327 – 1336 (2004). Computer Graphics and Geometric Modeling.
[22] Selinger, P., “Potrace: a polygon-based tracing algorithm,” (2003). Potrace (online), http://potrace. sourceforge.net/potrace.pdf (2009-07-01).
[23] Knuth, D. E., [The Metafont Book], Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA (1986).
[24] di Baja, G. S. and Thiel, E., “Skeletonization algorithm running on path-based distance maps,” Image and Vision Computing 14(1), 47 – 57 (1996). Image and Vision Computing Journal on Vision-Based Aids for the Disabled.
[25] Choi, W.-P., Lam, K.-M., and Siu, W.-C., “Extraction of the euclidean skeleton based on a connectivity criterion,” Pattern Recognition 36(3), 721 – 729 (2003).
[26] Barney Smith, E. H. and Qiu, X., “Statistical image differences, degradation features, and character distance metrics,” IJDAR 6(3), 146–153 (2003).
[27] Likforman-Sulem, L., Darbon, J., and Barney Smith, E. H., “Enhancement of historical printed document images by combining total variation regularization and non-local means filtering,” Image Vision Com- put. 29(5), 351–363 (2011).
— 过往内容 —