手写识别：回到未来 (2016)

# GRAIL 文本识别器 来源：https://jackschaedler.github.io/handwriting-recognition/ *五十年前*，兰德公司（RAND corporation）开发了图形输入语言软件系统 \(GRAIL\)。在 1966 年的一份兰德备忘录中，GRAIL 的既定目标是：“研究用户如何能够直接、自然且轻松地处理\[他们\]的问题。”用户通过一种类似笔的仪器和数位板与 GRAIL 进行交流。GRAIL 没有鼠标、没有键盘、没有按钮、没有操纵杆，也没有我们通常与现代计算联系起来的其他附属设备。当用户想要屏幕上出现一个方框时，他们*绘制*这个方框。当用户想要屏幕上出现文本时，他们*手写*这段文本。今天，当你观看该系统的演示（https://youtu.be/p2LZLYcu_JY?t=24m30s）时，它依然感觉优雅而神奇。借用托尼·霍尔（Tony Hoare）的一句话，GRAIL 在许多方面都优于其后几乎所有继任者。 “这种识别方案实现了其主要目标——让任何用户都能自然地与计算机交流。用户不会被任何操作机制分心，而是可以专注于\[他们\]的问题。” —— Gabriel Groner（1966） 上图描绘的是 20 世纪 60 年代的某个时候，汤姆·埃利斯（Tom Ellis）使用兰德数位板与屏幕上的图像进行交互。埃利斯是兰德数位板和 GRAIL 软件系统的发明者之一，也是项目负责人。这张图片以及许多其他图片可以在计算机历史博物馆（http://www.computerhistory.org/collections/search/?s=Rand+Tablet）的网站上找到。在这篇互动文章中，我们将重新审视 Gabriel Groner 对 GRAIL 项目的贡献。Groner 开发了一个非常巧妙的程序，能够识别手写的字母、数字、标点符号和几何图形。该程序效率高到足以在 IBM System/360（https://en.wikipedia.org/wiki/IBM_System/360）计算机上实时运行，并且足够稳健，能够正确识别*90%*的首次使用者绘制的符号。Groner 在 1966 年兰德公司关于*手写文本的实时识别*（http://www.rand.org/pubs/research_memoranda/RM5016.html）的备忘录中记录了他的方法。 读完这篇文章后，你应该能准确理解 Groner 的手写识别方案是如何工作的。更确切地说，你将会*看到*Groner 的方法是如何运作的，并对其各种操作和阶段形成直观的理解。最好将这篇文章作为 Groner 原始备忘录（http://www.rand.org/pubs/research_memoranda/RM5016.html）的动态伴侣来阅读。当 Groner 描述一种算法或启发式方法时，这篇文章会为你提供一个可以探索的交互式实现。当文本直接摘自 Groner 的备忘录时，会以另一种字体呈现。原始备忘录中描述的识别方案能够识别各种各样的符号、形状、数字、字母，甚至标点符号。在这篇文章中，我将展示 Groner 识别器的一个简化版本，它只能识别大写数字和字母。 这篇文章的所有源代码都可以在 Github（https://github.com/jackschaedler/handwriting-recognition）上公开获取。请将所有错误、拼写问题和建议提交到问题跟踪器（https://github.com/jackschaedler/handwriting-recognition/issues）。如果你对这篇文章有任何问题或评论，欢迎在 Twitter 上联系我（https://twitter.com/jackschaedler）。 事实上，你可以阅读 Groner 的*完整程序*（http://www.rand.org/pubs/research_memoranda/RM5550.html）的源代码，他用 IBM 360 汇编语言编写了该程序。 “当今的用户-计算机交互机制所提供的通信远非最佳，这大大降低了机器或用户的能力得到充分利用的可能性……人们认为，探索人类在使用自由、类似笔的仪器于水平表面（如便签本）上时所具备的现有灵活性，将会是富有成效的。” —— M.R Davis 和 T.O. Ellis（1964） 人类通过*兰德数位板*（https://en.wikipedia.org/wiki/RAND_Tablet）与 GRAIL 进行交互。系统的所有输入都是使用类似笔的仪器*绘制*到兰德数位板表面上的。这块 10.24 英寸 × 10.24 英寸的数位板分辨率为每英寸 100 线，能够精确数字化超过一百万个离散的笔位置。笔尖内安装了一个压力敏感开关，每当用户希望在屏幕上留下标记时，只需将笔按在书写表面上即可。触控笔的位置每隔四毫秒以一对*\(x, y\)*坐标的形式报告给 GRAIL。 下面，你会找到一个*虚拟*数位板，可以在上面涂画和书写。与兰德数位板一样，这个虚拟数位板的表面是离散化的。这意味着书写表面被划分为一个*网格*，所有笔位置都作为该网格上的坐标报告。虽然兰德数位板的分辨率是每英寸 100 线，但我们的虚拟数位板分辨率要低得多，约为每英寸 20 线。因此，最好把我们的虚拟数位板想象成兰德数位板的*一小部分*，放大了大约 500%。在数位板上书写时请记住这一点。绘制字母和数字时，要让它们填满数位板可用高度的 70% 左右。画大些！ 要开始绘制，请将指针移到数位板上并按下鼠标按钮。这模拟了将触控笔按在数位板表面上的动作。在按住鼠标按钮的同时，将指针在数位板表面上移动以留下标记。当你对标记满意时，松开鼠标按钮。试着通过在数位板上绘制一些无需将笔从表面抬起即可完成的数字（2、3、6）和字母（C、M、S）来感受一下。一旦你对在虚拟数位板上涂画感到自如，就滚动到下一部分。 “用户通过兰德数位板配合阴极射线管（CRT）显示器与计算机进行交流。数位板硬件包括一个水平的 10 英寸方形书写表面和一支类似笔的书写仪器…… 当他将笔按在数位板书写表面上时，笔中的一个开关闭合，从而通知中央处理单元（CPU）发生了‘落笔动作’…… 当笔被抬起时，笔开关断开，从而通知 CPU 发生了‘抬笔’动作……当笔在书写表面上移动时，识别方案每隔 4 毫秒被告知其位置。” 关于*灵活性*：参见 Bret Victor 的《对未来交互设计的简短抱怨》（http://worrydream.com/#!/ABriefRantOnTheFutureOfInteractionDesign）。对于 1963 年来说，这绝对是超酷的技术。你可以在这里（http://www.rand.org/pubs/research_memoranda/RM4122.html）阅读兰德公司关于设计和实现细节的备忘录。如果你对兰德数位板的更多轶事信息感兴趣，可以观看 Alan Kay 讨论兰德数位板的这段视频（https://youtu.be/pUoBSC3uoeo?t=36m50s）。 我在这里使用了一些不太理想的术语，因为我不知道你可能会用什么设备来阅读这篇文章。我相当确定——即使现在还没有——像*鼠标*和*点击*这样的词很快就会像*回车*一样显得过时。这意味着，如果你恰好使用的是不带鼠标的设备，如触控板、触摸屏或数位板，你就得进行一些即时转换。 你可能已经注意到，你在数位板上留下的标记在屏幕上显示时会出现难看的微小扰动和锯齿（https://en.wikipedia.org/wiki/Jaggies）。这是因为数位板只能报告位于离散网格上的笔位置。这意味着，即使是平滑绘制的曲线，在被数位板捕获后也必然会产生小的凸起和拐角。这些锯齿看起来很难看，但更重要的是，它们会向笔位置列表中添加不需要的*噪声*。为了去除这种噪声，Groner 决定*平滑*数位板的输出。 “该方案通过将新到达的数据点与先前已平滑的数据点进行平均来平滑数据，从而减少由于数位板所测得的笔位置离散性而产生的噪声。” Groner 所说的*离散性导致的噪声*，你可能会称之为*像素化*。下图可以让你直观感受像素化或*离散化*对平滑绘制笔画的影响。按下*绘制*按钮查看绘制平滑曲线时笔所经过的“真实”路径。曲线绘制完成后，按下*吸附*按钮查看强制每个点位于离散网格上的效果。注意，离散化会在原本平滑的曲线上引入许多小凸起、拐角和平坦段。 幸运的是，我们可以*平滑*数位板的输出来将这些点从固定网格的束缚中解放出来。平滑操作通过将每个新的量化数据点的位置与最近一个已平滑数据点的位置进行*平均*来执行。我们可以通过在每个*量化数据点*和最近*已平滑数据点*之间绘制一条*直线*，在几何上执行这种平均。然后沿着这条直线将量化点*滑动*到更靠近先前平滑点的位置。点滑动得越远，平滑效果就被强调得越明显。你可以使用下面的可视化工具来直观理解这种平滑算法。量化数据点以蓝色绘制，平滑后的点将以黑色绘制。三个按钮允许你指定每个点应沿引导线滑动的距离。百分比越高，曲线越平滑。 这种简单的平滑方案使我们能够去除数据中不需要的凸起和锯齿，同时仍保持笔画整体的*手势*特征。但请注意，平滑是一个破坏性的过程。笔的细微花饰会被平滑消除。因此，选择一个合适的平滑因子至关重要。 在下面的数位板上绘制，看看这种平滑方案会如何影响更有趣的输入。你可以通过拖动可视化右侧的滑块来改变每个笔画被平滑的程度。花些时间在数位板上绘制字母、数字和简单形状。我建议你首先从数位板的左下角向右上角画一条直线。完成此操作后，慢慢拖动滑块，观察随着平滑程度的变化，笔画是如何被变换的。 平滑基于以下方程： XSi = XSi-1 + XRi YSi = YSi-1 + YRi XRi, YRi = 第 i 个原始点的坐标 XSi, YSi = 第 i 个平滑点的坐标 平滑因子： 这种噪声被称为*量化噪声*（https://en.wikipedia.org/wiki/Quantization_(signal_processing)）。量化是将连续值近似为一组离散值的过程。当连续值与用于表示它的离散值不匹配时，这种量化行为会引入一些误差或噪声。有时，这种误差会通过真正引入更多随机噪声来抵消！这是一个被称为抖动（https://en.wikipedia.org/wiki/Dither）的过程。Groner 没有对数位板输出进行抖动，而是选择简单地平滑它。Groner *不会*将这些笔画称为“像素感”，因为基于像素的图形直到 20 世纪 60 年代末才被发明。Groner 是在前像素世界中操作的，就像 Ivan Sutherland 构建他的 Sketchpad（https://youtu.be/6orsmFndx_o）系统时一样。 如果你想更深入地研究这种平滑方案背后的数学原理，有必要知道这是*无限脉冲响应*（https://en.wikipedia.org/wiki/Infinite_impulse_response）滤波器的一个应用。精确的公式在下一个可视化中交互式地展示。 我喜欢这个可视化，因为它揭示了这种平滑方案的一个令人惊讶的特性：当使用较大的平滑因子平滑曲线时，曲线会开始迅速向内坍缩。如果你习惯阅读公式，你可能很容易在使用 100% 平滑因子时预见到这种“黑洞效应”，但需要非常有“模拟计算机运行”能力的人才能理解，当平滑因子超过 80% 时，这种效应会急剧加速。我对这一特性感到惊讶，我想这是因为人类并不擅长理解递归过程（反正我不擅长）。敏锐的读者会注意到，滑块是非线性缩放的，以应对黑洞效应。 你可能已经注意到，有可能生成大量数据点，尤其是当你的指针在数位板上移动得非常缓慢时。因为我们只对每个笔画的大致形状感兴趣，所以大多数数据点实际上是不必要的。Groner 采用了一种非常简单的*细化*方案来去除这些不必要的点。它可以几何描述如下：在第一个数据点周围画一个*正方形*。所有位于该正方形内的后续点都将被丢弃。然后，正方形被重新定位在下一个落在正方形之外的点周围，并重复该过程。正方形的大小决定了笔画被细化的积极程度。这种细化方案在下面可视化。 “细化是从笔迹中移除部分数据点的过程。这是通过将新的平滑数据点的位置与细化轨迹中最后一个点的位置进行比较来实现的。如果这些点距离足够远，分析方案就接受该平滑点作为细化轨迹的一部分；否则，它将被丢弃。细化消除了轨迹中的微小扰动，并通过大幅减少数据点的数量来降低数据处理需求。” 下一个数位板允许你在任意输入上试验这种细化方案。原始数据点以蓝色绘制，细化后的点以黑色绘制。“细化正方形”以粉红色绘制在最近细化点周围。首先在数位板上绘制一个符号，然后通过拖动图形右下角的滑块来改变细化的积极程度。你应该会注意到，即使进行相当积极的细化，大多数笔画的基本形状也能得以保留。Groner 发现，即使丢弃大约*百分之七十*的原始数据点，他也能获得令人满意的结果！ 细化描述如下： XTj = XSi， YTj = YSi 如果以下任一条件成立： |XSi - XTj-1| >= |YSi - YTj-1| >= XTj, YTj = 第 j 个细化点的坐标 细化大小 = “*曲率*是最明显的轨迹特征，它独立于位置和大小，却能描述轨迹的形状。Freeman 提出，对曲率的一个有用近似是细化轨迹中的点所生成的量化方向段序列。Kuhl 和 Bernstein 在其字符识别方案中使用了这种近似。事实上，Bernstein 发现没有必要使用每个量化方向的持续时间，而只需列出量化方向的变化。Kuhl 和 Bernstein 都使用了八个可能的方向，而这里描述的识别方案只使用四个。四个方向与其他特征结合使用，足以提供识别所需的描述，而且比八个方向产生的符号变体更少。” 由于该矩形比其高度更宽，并且位于前一个点的右侧，因此分配的方向是***右***