使用以鬆弛法配對之隨機圖形模式來作手寫字辨認

Abstract

本論文提出一個手寫阿拉伯數字與部份手寫中文字辨認系統。本系統分成兩部份：前 處理與辨認處理。在前處理中，文件由掃描器讀入成二維影像，基於跑長度之編碼（ run length encoding） 我們提出一特徵截取器（feature extractor ）來抽取字的 直線筆劃、曲線筆劃與單元（僅對中文字而言），這些特徵可充分代表一個手寫字的 特徵與結構。使用這些特徵為基元，代表一個字的一階（對中文字而言為二階）的屬 性圖形（attributed graph）被建構起來。由於隨機圖形（random graph）包含了結 構與機率性的資訊，並且可由許多相似結構的屬性圖形合成而來的，另外鬆弛法配對 可應用於屬性圖形與隨機圖形之間的圖形配對，達到polynomial的時間，其結果亦近 似最佳化。因此，利用上述之特性，我們發展了辨認處理。這辨認處理主要分成二部 份：學習階段與辨認階段。在學習階段中，鬆弛法配對技巧被使用來把屬於相同的字 由於手寫的變形而有不同的屬性圖形合到一個一階（或二階）的隨機圖形，如此我們 可建構一參考資料模式以作為往後辨認字的資料庫。在辨認階段中，基於屬性圖形是 否為隨機圖形的可能結果，我們提出一個在它們之間的相似度測量，利用此相似度測 量與鬆弛法技巧，從屬性圖形到隨機圖形之圖形配對被發展。藉此，使用最大相似度 測量，一輸入字最後能被類到某一特定的參考字。實驗結果手寫阿拉伯數字辨認率達 ９９％以上，手寫中文字辨認率達９６％以上，這證明了本論本所提出的方法的確可 行。