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

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

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

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

演示源碼github，歡迎交流。

人們使用RAND平板與圣杯互動(dòng)，一個(gè)壓力敏感開關(guān)安裝在筆的頂端。所有的輸入都會(huì)轉(zhuǎn)化為xy平面坐標(biāo)系的點(diǎn)。據(jù)記錄，觸控筆的位置每四毫秒為一對(duì)（x，y）坐標(biāo)。

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

你可能已經(jīng)注意到，在平板上面的標(biāo)記會(huì)出現(xiàn)一些難看的鋸齒，并且滑動(dòng)速度越快拐點(diǎn)越明顯，這個(gè)是因?yàn)槊克暮撩胗涗浺粋€(gè)坐標(biāo)。為了消除這些鋸齒格羅納決定使平板電腦的輸出平滑。

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

平滑操作是通過將每個(gè)新量化的數(shù)據(jù)點(diǎn)的位置與最后平滑的數(shù)據(jù)點(diǎn)的位置進(jìn)行平均來執(zhí)行的。我們可以通過在每一個(gè)量化的數(shù)據(jù)點(diǎn)和最近平滑的數(shù)據(jù)點(diǎn)之間畫一條直線來幾何平均地執(zhí)行這個(gè)平均值。然后，我們沿著這條線將量化點(diǎn)滑動(dòng)到先前平滑的點(diǎn)。我們進(jìn)一步滑動(dòng)點(diǎn)，我們?cè)綇?qiáng)調(diào)平滑的效果。你可以使用下面的畫板直觀體驗(yàn)。量化的數(shù)據(jù)點(diǎn)用藍(lán)色繪制，平滑點(diǎn)將用黑色繪制。這三個(gè)按鈕允許您指定每個(gè)點(diǎn)應(yīng)該沿著指南滑動(dòng)多遠(yuǎn)。更高的百分比將導(dǎo)致更平滑的曲線。

這個(gè)簡單的平滑方案使我們能夠擺脫不想要的數(shù)據(jù)，同時(shí)仍然保持筆劃的總體姿態(tài)。但是平滑是一個(gè)破壞性的過程，因此，選擇合適的平滑因子至關(guān)重要。

繪制下面的畫板觀察這個(gè)平滑方案將如何影響?？梢酝ㄟ^拖動(dòng)右邊的滑塊來改變每個(gè)筆劃平滑的程度。我建議你在畫板的左下方到右上方畫一條直線，然后慢慢地拖動(dòng)滑塊，看看筆畫是如何隨著平滑量的變化而變換的。

Smoothing Factor: 0.43  滑動(dòng)系數(shù)
XSi = 0.43XSi-1 + 0.57XRi 
YSi = 0.43YSi-1 + 0.57YRi 
XRi,YRi = coordinates of ith raw point  畫板中的原始點(diǎn)
XSi,YSi = coordinates of ith smoothed point 平滑之后的點(diǎn) 

【圖三】

您應(yīng)該注意到上面的案例生成了大量的數(shù)據(jù)，特別是當(dāng)指針在平板電腦上緩慢移動(dòng)時(shí)。因?yàn)槲覀冎粚?duì)每個(gè)筆畫的一般形狀感興趣，所以這些數(shù)據(jù)點(diǎn)（太密集）實(shí)際上是不必要的。格羅納采用了一個(gè)非常簡單的細(xì)化方案來去除這些不必要的點(diǎn)。它可以幾何描述如下：在第一數(shù)據(jù)點(diǎn)周圍畫一個(gè)正方形。在這個(gè)方塊內(nèi)的所有后續(xù)點(diǎn)都將被丟棄。然后，方塊被重新定位在下一個(gè)點(diǎn)并且這個(gè)過程被重復(fù)。正方形的大小決定了需要細(xì)化的程度。這種細(xì)化方案在下面叫做可視化。

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

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

Thinning Size = 0.30 細(xì)化系數(shù)
|XSi - XTj-1| >= 0.30 絕對(duì)值大于系數(shù)的保留
|YSi - YTj-1| >= 0.30

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

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

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

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

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

角檢測是以相對(duì)簡單的方式實(shí)現(xiàn)的。我們給每個(gè)輸入點(diǎn)分配一個(gè)基數(shù)方向，格羅納也給每個(gè)點(diǎn)分配16個(gè)可能方向。當(dāng)筆在相同的方向上移動(dòng)兩個(gè)段，改變方向至少90°時(shí)檢測到拐角。

在下面的平板上畫一些數(shù)字、字母和基本形狀，以查看動(dòng)作中的角點(diǎn)檢測算法。識(shí)別器將用粉紅色十字標(biāo)記角。你可以使用在平板電腦右邊的滑塊來測試90°以外的閾值?；ㄒ恍r(shí)間繪制字符，其中角是一個(gè)有區(qū)別的特征（5，s，C，G，方和圓），然后緩慢地調(diào)整滑塊。

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

當(dāng)畫出筆畫時(shí)，其X（水平）和Y（垂直）極值不斷更新。當(dāng)筆被抬起到指示筆畫完成時(shí)，分析方案使用這些極端來計(jì)算符號(hào)的高度和寬度以英寸的分?jǐn)?shù)、其縱橫比（高度與寬度的比率）以及其相對(duì)于原點(diǎn)的中心。它將由符號(hào)極值定義的矩形區(qū)域劃分為4×4網(wǎng)格。然后，開始（筆下）和結(jié)束（筆向上）點(diǎn)以及拐角位置，每個(gè)被編碼為位于這16個(gè)區(qū)域中的一個(gè)區(qū)域，從而相對(duì)于符號(hào)定位它們。

在下面的虛擬平板上畫上一些字母和數(shù)字。開始繪圖的位置用藍(lán)色圓圈標(biāo)出，停止繪圖的位置用藍(lán)色正方形標(biāo)記。

“符號(hào)的識(shí)別基于與數(shù)據(jù)相關(guān)的測試序列。在決策過程中的每一步都有幾個(gè)潛在的標(biāo)識(shí)。其中一些通過測試軌道的主要特征而被消除。在任何步驟應(yīng)用的特定測試取決于該步驟中可能的標(biāo)識(shí)集，以及已經(jīng)檢查過的軌道的那些特征。因此，決策方案具有樹形結(jié)構(gòu)。它最初的設(shè)計(jì)是基于對(duì)四個(gè)用戶的筆跡的檢查。作者改變其結(jié)構(gòu)，以適應(yīng)額外的符號(hào)變化，因?yàn)樗@得更多的經(jīng)驗(yàn)?！?/p>

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

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

我在本文中提出的識(shí)別器能夠識(shí)別大寫字母和數(shù)字，它們是在一個(gè)筆劃中繪制的。換句話說，每一個(gè)字符都必須一筆全部畫出來。格羅納的原始識(shí)別器能夠識(shí)別多筆畫字符，允許用戶以原來習(xí)慣的方式輸入文本。格羅納的目標(biāo)是保持用戶現(xiàn)有習(xí)慣，使用戶不需要適應(yīng)他們的寫作風(fēng)格。事實(shí)上，Alan Kay聲稱，該系統(tǒng)的主要?jiǎng)訖C(jī)之一是排除打字教學(xué)的需要。因?yàn)槲业哪繕?biāo)遠(yuǎn)沒有那么雄心勃勃——為了解釋格羅納所使用的基本方法——我決定實(shí)現(xiàn)一個(gè)更簡單的單筆畫變體的識(shí)別器。多筆畫識(shí)別并不比單筆畫識(shí)別復(fù)雜得多，但有點(diǎn)復(fù)雜。如果你有興趣自己去執(zhí)行，格羅納的原備忘錄中清楚地闡明了這種方法。

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

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

體驗(yàn)識(shí)別器-原文，或者給我點(diǎn)贊，有人看我就后期copy到這個(gè)文章中
很可能我的識(shí)別器會(huì)檢測失敗。如果發(fā)生這種情況，你不應(yīng)該責(zé)怪格羅納的方法。備忘錄很清楚，第一次用戶在使用他的識(shí)別器時(shí)，成功識(shí)別率為90%。我的決策樹是我自己的，它偏向于我自己的書法風(fēng)格。然而，我使用格羅納的優(yōu)勢在于，我可以源源不斷地推動(dòng)一個(gè)持續(xù)改進(jìn)的計(jì)劃！如果你得到一個(gè)錯(cuò)誤的標(biāo)識(shí)讓你感到厭煩，請(qǐng)?jiān)贕ITHUB上在項(xiàng)目發(fā)布頁面上發(fā)布它的截圖。

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

對(duì)我來說，格羅納的工作是有趣的，不是因?yàn)樗试S一個(gè)人將文本傳送到計(jì)算機(jī)系統(tǒng)，而是因?yàn)樗试S人類通過高帶寬的繪畫媒介與計(jì)算機(jī)接口。在本文中，我關(guān)注的是文本，因?yàn)檫@是格羅納原創(chuàng)作品的一個(gè)主要焦點(diǎn)，但我看到這項(xiàng)技術(shù)在圖形和類似手勢的識(shí)別和處理方面有著更為引人注目的應(yīng)用。繪畫是一種非常強(qiáng)大的交流方式，我非常喜歡繪畫可以作為一種主要的或輔助的與我們個(gè)人電腦進(jìn)行交流的方法?？?佩林的ChalTalk是這一原理的一個(gè)很好的例子，我強(qiáng)烈推薦你看他的演示，如果你懷疑格羅納的方法應(yīng)用于文本識(shí)別之外的任務(wù)。

翻譯自 -Jack Schaedler Berlin, 2016