摘要：格羅納發明了一個非常聰明的程序，它識別手印的字母數字標點符號和幾何圖形。在這篇文章中，我將介紹一個簡單的格羅納識別器，它只能夠識別大寫字母和大寫字母。和伯恩斯坦在他們的字符識別方案中使用了這種近似。

阮一峰推特更新推薦一篇外文,閑來無聊，就（工具）翻譯一波，菜鳥英文歡迎指正。原文鏈接
文中包含大量演示案例，如果有人關注這篇文章可以給我留言，我將繼續整合中文版代碼演示案例。翻譯原文

上圖湯姆·艾利斯在20世紀60年代使用RAND平板電腦與屏幕上的圖像進行交互。

在這篇文章中，我們將重溫Gabriel Groner 對圣杯計劃的貢獻。格羅納發明了一個非常聰明的程序，它識別手印的字母、數字、標點符號和幾何圖形。該程序能夠正確識別第一時間用戶繪制的90%個符號。格羅納在一個1966蘭德的備忘錄中記錄了他的方法，用于實時識別手寫文本。在這篇文章中，我將介紹一個簡單的格羅納識別器，它只能夠識別大寫字母和大寫字母。

演示源碼github，歡迎交流。

人們使用RAND平板與圣杯互動，一個壓力敏感開關安裝在筆的頂端。所有的輸入都會轉化為xy平面坐標系的點。據記錄，觸控筆的位置每四毫秒為一對（x，y）坐標。

下面我們模擬了一個畫板：移動指針并按下鼠標，這模擬了將手寫筆壓在平板表面上的動作。在不釋放鼠標的情況下，將指針移動到平板表面，以形成標記。當你對標記滿意時，釋放鼠標按鈕。試著通過繪制一些數字（2, 3, 6）和字母（C，M，S）來獲得在平板電腦上工作的感覺。

你可能已經注意到，在平板上面的標記會出現一些難看的鋸齒，并且滑動速度越快拐點越明顯，這個是因為每四毫秒記錄一個坐標。為了消除這些鋸齒格羅納決定使平板電腦的輸出平滑。

該方案通過對新到達的數據點與先前平滑的數據點進行平均來平滑數據，從而減少由于由平板測量的筆位置的離散性引起的噪聲。即((x1-x)n,(y1-y)n)

平滑操作是通過將每個新量化的數據點的位置與最后平滑的數據點的位置進行平均來執行的。我們可以通過在每一個量化的數據點和最近平滑的數據點之間畫一條直線來幾何平均地執行這個平均值。然后，我們沿著這條線將量化點滑動到先前平滑的點。我們進一步滑動點，我們越強調平滑的效果。你可以使用下面的畫板直觀體驗。量化的數據點用藍色繪制，平滑點將用黑色繪制。這三個按鈕允許您指定每個點應該沿著指南滑動多遠。更高的百分比將導致更平滑的曲線。

這個簡單的平滑方案使我們能夠擺脫不想要的數據，同時仍然保持筆劃的總體姿態。但是平滑是一個破壞性的過程，因此，選擇合適的平滑因子至關重要。

繪制下面的畫板觀察這個平滑方案將如何影響。可以通過拖動右邊的滑塊來改變每個筆劃平滑的程度。我建議你在畫板的左下方到右上方畫一條直線，然后慢慢地拖動滑塊，看看筆畫是如何隨著平滑量的變化而變換的。

Smoothing Factor: 0.43  滑動系數
XSi = 0.43XSi-1 + 0.57XRi 
YSi = 0.43YSi-1 + 0.57YRi 
XRi,YRi = coordinates of ith raw point  畫板中的原始點
XSi,YSi = coordinates of ith smoothed point 平滑之后的點 

【圖三】

您應該注意到上面的案例生成了大量的數據，特別是當指針在平板電腦上緩慢移動時。因為我們只對每個筆畫的一般形狀感興趣，所以這些數據點（太密集）實際上是不必要的。格羅納采用了一個非常簡單的細化方案來去除這些不必要的點。它可以幾何描述如下：在第一數據點周圍畫一個正方形。在這個方塊內的所有后續點都將被丟棄。然后，方塊被重新定位在下一個點并且這個過程被重復。正方形的大小決定了需要細化的程度。這種細化方案在下面叫做可視化。

“Thinning”是從筆跡中刪除一些數據點的過程。這是通過比較一個新的平滑數據點的位置與在細化軌道上的最后一點的位置來完成的。如果這些點相距甚遠，則分析方案接受作為平滑軌跡的一部分的平滑點；否則，將被丟棄。細化消除了軌道中的小干擾，并通過大幅減少數據點的數量來減少數據處理要求。【圖四】

下一個畫板允許您在任意輸入下對這種細化方案進行實驗。原始數據點用藍色繪制，稀疏點用黑色繪制。在最近變薄的點上，“稀疏平方”畫成粉紅色。首先在平板電腦上畫一個符號，然后通過拖動圖右下角的滑塊來改變細化系數。你應該注意到，即使在非常劇烈地細化下，也可以保持大多數筆觸的基本形狀。格羅納發現，即使丟棄了百分之七十的原始數據，他也能獲得令人滿意的結果。

Thinning Size = 0.30 細化系數
|XSi - XTj-1| >= 0.30 絕對值大于系數的保留
|YSi - YTj-1| >= 0.30

曲率是最明顯的軌道特性，它不依賴于位置和大小，而是描述了軌道的形狀。Freeman已經提出了一個有用的近似曲率是由細化軌道中的點產生的量化方向段的序列。KuHL和伯恩斯坦在他們的字符識別方案中使用了這種近似。事實上，伯恩斯坦發現不需要使用每個量化方向的持續時間，而是簡單地列出量化方向上的變化。而KuHL和伯恩斯坦都使用八個可能的方向，這里所描述的識別方案僅使用四個。與其他特征結合使用已經提供了足夠的特征來識別。

在平滑和細化處理之后，每個數據點被分配一個方向。有點令人震驚的是，格羅納發現僅僅在描述筆畫曲率時只考慮基數方向就足夠了。因此，每個點被認為是向上、向下、向左或向右移動的結果。我們可以通過兩個點形成的矩形來判斷方向：如果這個矩形寬大于高，那么這個點是代表一個向左或向右的運動。如果矩形高大于寬，則點是向上或向下移動的結果。你可以用右視圖來確定基數方向的確定。

if |XTj - XTj-1| >= |YTj - YTj-1|
right if XTj - XTj-1 >= 0
left if XTj - XTj-1 < 0 

if |XTj - XTj-1| < |YTj - YTj-1|
up if YTj - YTj-1 >= 0
down if YTj - YTj-1 < 0

盡管每個點都被分配了一個基本方向，但是格羅納字符識別器只使用方向的變化。這允許我們丟棄冗余數據點，并且實現每個筆畫曲率的非常緊湊的表示。在該平板上，方向的變化以黑色繪制，冗余方向以淺灰色呈現。

雖然每個筆畫的曲率可以用于對用戶意圖做出猜測，但是一些符號不能僅使用方向信息彼此區分。例如，“5”和“S”的繪制，這兩個方向都會產生相同的方向段。格羅納決定用拐角的存在或不存在來解決這些歧義。例如，一個“5”通常會在符號的左手邊畫上一個或兩個角，而一個“S”一般會在沒有任何角的情況下畫出來。

角檢測是以相對簡單的方式實現的。我們給每個輸入點分配一個基數方向，格羅納也給每個點分配16個可能方向。當筆在相同的方向上移動兩個段，改變方向至少90°時檢測到拐角。

在下面的平板上畫一些數字、字母和基本形狀，以查看動作中的角點檢測算法。識別器將用粉紅色十字標記角。你可以使用在平板電腦右邊的滑塊來測試90°以外的閾值。花一些時間繪制字符，其中角是一個有區別的特征（5，s，C，G，方和圓），然后緩慢地調整滑塊。

平板上的每一個標記都被包裝成筆畫描述。筆劃描述是記錄中顯著特征的表示。這個描述使我們能夠輕松地回答問題：“用戶是否在左上角畫了這個符號，然后在右下角停止繪圖？”“如果這個問題的答案是肯定的，那么用戶很有可能畫出2或Z。”用戶是否把筆從表面上提起，離他們開始畫的地方很近？如果是這樣的話，用戶可能會畫出像O或8那樣的閉合行程。筆畫描述還捕捉筆劃的簡單特征，如寬度、高度和縱橫比。這些特征使我們能夠回答這樣的問題：“你能把這個符號形容為胖還是瘦？”“這個問題的答案可能有助于我們區分7和1。

當畫出筆畫時，其X（水平）和Y（垂直）極值不斷更新。當筆被抬起到指示筆畫完成時，分析方案使用這些極端來計算符號的高度和寬度以英寸的分數、其縱橫比（高度與寬度的比率）以及其相對于原點的中心。它將由符號極值定義的矩形區域劃分為4×4網格。然后，開始（筆下）和結束（筆向上）點以及拐角位置，每個被編碼為位于這16個區域中的一個區域，從而相對于符號定位它們。

在下面的虛擬平板上畫上一些字母和數字。開始繪圖的位置用藍色圓圈標出，停止繪圖的位置用藍色正方形標記。

“符號的識別基于與數據相關的測試序列。在決策過程中的每一步都有幾個潛在的標識。其中一些通過測試軌道的主要特征而被消除。在任何步驟應用的特定測試取決于該步驟中可能的標識集，以及已經檢查過的軌道的那些特征。因此，決策方案具有樹形結構。它最初的設計是基于對四個用戶的筆跡的檢查。作者改變其結構，以適應額外的符號變化，因為他獲得更多的經驗。”

識別器首先根據筆畫的前四個基本方向生成潛在字符列表。不能直接或不使用這些前四個方向繪制的筆畫立即被忽略。有時，前四個方向提供足夠的信息來精確地識別字符。例如，一個向下、向右、然后停止的筆劃可以立即被識別為L。通常，前四個方向不會導致立即識別，我們將留下一個潛在字符列表。舉例來說，一個開始的行程可能是0，2或3。

我們可以通過測試筆畫描述的其他方面來解決這些歧義。例如，如果筆劃在符號的右下角結束則可以識別為2；在符號的左下角結束為3；起始位置和結束位置都在符號的頂部彼此靠近來識別0。在實踐中，決策過程是通過編寫一個大的IF語句級聯來實現的。在這個過程中沒有“魔術”。并且決策樹需要改進和修改會遇到寫某些字符的新的和意外的方法。

我在本文中提出的識別器能夠識別大寫字母和數字，它們是在一個筆劃中繪制的。換句話說，每一個字符都必須一筆全部畫出來。格羅納的原始識別器能夠識別多筆畫字符，允許用戶以原來習慣的方式輸入文本。格羅納的目標是保持用戶現有習慣，使用戶不需要適應他們的寫作風格。事實上，Alan Kay聲稱，該系統的主要動機之一是排除打字教學的需要。因為我的目標遠沒有那么雄心勃勃——為了解釋格羅納所使用的基本方法——我決定實現一個更簡單的單筆畫變體的識別器。多筆畫識別并不比單筆畫識別復雜得多，但有點復雜。如果你有興趣自己去執行，格羅納的原備忘錄中清楚地闡明了這種方法。

我的約束，所有字符必須在一個筆畫完成，它希望用戶能大致按照下面的詞匯輸入字母和數字。特別是F和X，需要來自用戶的一點不自然的心理扭曲。點擊一個筆畫看到它正在繪制的動畫（翻譯截圖不支持動畫，需要請查看原網址）。

當繪制一個給定的字符時，必須遵循一般的形狀，格羅納的方法是足夠健壯的，以便在繪制字符時允許大量的變化和松弛。例如，所有下列筆劃將被標識為數字3。

體驗識別器-原文，或者給我點贊，有人看我就后期copy到這個文章中
很可能我的識別器會檢測失敗。如果發生這種情況，你不應該責怪格羅納的方法。備忘錄很清楚，第一次用戶在使用他的識別器時，成功識別率為90%。我的決策樹是我自己的，它偏向于我自己的書法風格。然而，我使用格羅納的優勢在于，我可以源源不斷地推動一個持續改進的計劃！如果你得到一個錯誤的標識讓你感到厭煩，請在GITHUB上在項目發布頁面上發布它的截圖。

為什么2016年（這篇文章是2016年寫的）的人要關心上個世紀的手寫識別算法？自從格羅納的備忘錄出版以來，五年已經過去了，圣杯已經從主流節目和HCI社區的經典中消失了，為什么要花時間重讀格羅納的原著，更不用說這篇文章了？

對我來說，格羅納的工作是有趣的，不是因為它允許一個人將文本傳送到計算機系統，而是因為它允許人類通過高帶寬的繪畫媒介與計算機接口。在本文中，我關注的是文本，因為這是格羅納原創作品的一個主要焦點，但我看到這項技術在圖形和類似手勢的識別和處理方面有著更為引人注目的應用。繪畫是一種非常強大的交流方式，我非常喜歡繪畫可以作為一種主要的或輔助的與我們個人電腦進行交流的方法。肯-佩林的ChalTalk是這一原理的一個很好的例子，我強烈推薦你看他的演示，如果你懷疑格羅納的方法應用于文本識別之外的任務。

翻譯自 -Jack Schaedler Berlin, 2016