|
|
|
|
Introduction 對於手寫字辨識,相信大家一定都不陌生,例如連接電腦的手寫板,PDA上的手寫區,甚或郵政系統中利用機器來判讀信封上的郵遞區號...等等,但是他們背後是用甚麼原理來做到這件事呢? 我們接下來就會根據以下兩篇paper來介紹手寫字辨識的基本概念. [1]Cheng-Yuan Liou and Hsin-Chang Yang (1996), “Handprinted character recognition based on spatial topology distance measurement,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol.18, no.9, pp. 941-945, 1996 [2]Cheng-Yuan Liou and Hsin-Chang Yang(1999), “Selective feature-to-feature adhesion for recognition of cursive handprinted characters,” IEEE Trans. on Pattern Analysis and Machine Intelligence, vol. 21, no. 2, pp. 184-191, 1999 在Introduction的部分,我們會用淺顯易懂的方式讓你了解HCR(Handprinted Character Recognition)的大致原理;你可以在Usage中下載此手寫字辨識軟體實際演練看看,若你對這些原理有更深的興趣,歡迎你到Advanced中,那裡有更深入的進階原理介紹. Method 在介紹我們的方法之前,大家不妨先想想,如果是你,你會如何完成手寫字的辨識呢?是研究筆劃順序?還是拆解手寫字的字根?然而這些方法都有它們已知的缺點,因此我們的方法是:計算手寫字中,每一個字根發生的可能性.當我們找到最有可能構成此手寫字的一些字根後,再加上了解這些字根的連結關係,我們就能夠達成手寫字辨識的目的. 而為了要實行這個方法,我們必須從該手寫字中找出一些有用的特徵與拓普上的次序(topological orders: 也就是圖形中頂點之間的線性次序). 首先,在字樣特徵上面,我們使用了[2]中介紹的bended ellipse features,這是一個五維的向量,裡面記錄了如下圖的資訊:
其中,我們如(a)圖一樣找一個頂點p(也稱做seed),然後再找出p點的相關資訊,如(b)圖所示,包括:
p點座標 在記錄了手寫字的特徵後,我們就必須了解如何斷定它的topological order(或者你也可以稱它作 feature-to-feature (FTF) order).這個做法其實很簡單,我們只要根據上一段紀錄的bended-ellipse feature資料,看看任意兩邊是否互為對方的"鄰居",如果是的話,我們就把這兩個邊接在一起,就如同下圖所描述的情形:
每一對互為鄰居的兩邊就好像每一副獨特的鎖與鑰匙一樣,跟你不相關的"邊"是永遠無法跟你連在一起的,而這個想法的由來是來自生物界中不同細胞只會跟特定不同物質作用的概念,也就好像你把上圖左邊的"零件"丟到一個瓶子裡搖一搖,結果出來的就是一個有意義的"水"字了.在這裡,我們將這種鄰居關係寫成一個矩陣,如下圖所示:
Classification 在我們做完以上兩步前置工作後,接下來就是重頭戲了:也就是找出與手寫字最相符的字根.我們將該手寫字與所有的字根做比對,而比對的方式是看手寫字是否與字根有相同的FTF
order, 這個部分又可分為1.比對兩者間的特徵向量(feature
vectors),此比對稱做inter-feature similarity; 2.比對兩者是否在某兩點間都有連線(也就是兩者的FTF
order 矩陣是否相似),此比對稱做inter-link similarity,(請見Advanced的深入介紹),而通常在我們做這樣的比對前會先將手寫字與字根都轉換成圖學上的表示方式(G=(V,
E) 等),而比對的過程也是採部分比對的方式(subgraph matching),我們將這些過程寫成公式
Simulation 在了解了手寫字辨識的基本概念後,我們就來看看這個方法實際應用的情形,請下載並解壓縮這個程式 hcr_demo.zip,而後執行其中的hcr.exe檔案,在這個程式中,我們預設輸入Charmingishere1234 這一串由英文文字與數字組成的手寫字,並且以標準字型0~9, A~Z, a~z當作做比對時的基礎(supported character),你可以清楚地由程式中看到比對時的過程與結果. 最後比對的結果如下圖所示:
如果你想要看到更多手寫字辨識的例子,請到Usage,裡面有各種情況下手寫字辨識的結果,你可以自行下載程式後操作看看,也可以更動其中的一些變數來看辨識結果有何不同.
All Rights Reserved by Cheng-Yuan, Liou, 最近更新日期：07/08/03
|
, 兩邊夾角角度
,
平分此角度的單位向量
,與p點兩邊的長度
,
.(
,並透過Hopfield
network來讓這公式有最大值.(也就是表示此時的字根最符合該手寫字),因此,在做完了這些找出bended-ellipse
features和比對FTF order的工作之後,我們就稱得上是達成了手寫字辨識的目標.(請見
