1 0 0 0 OA 手書き住所読取りのための町名検索アルゴリズム : 文字タグ法
郵便物の宛名住所のようにフリーピッチで書かれた手書き文字列は、字形が多様で、文字サイズにばらつきがあり、文字の接触・入組みなどもよく起きる。したがって、その読取りでは、誤切出し/誤認識によって欠落した正解文字を補完可能な知識処理が不可欠である。現在主流となっている知識処理の枠組みは、まず、各文字位置(セグメント)に複数通りの可能性(候補文字)を許した認識結果文字列と単語辞書とを照合し、さらに、単語の並びとしての妥当性を判定して読取り結果を決定する2段構成である。正解文字の欠落には、1段目の単語照合で虫食い照合を行うことで対処する。しかし、このような従来の枠組みは、フリーピッチ手書き文字列の読取りを正確かつ効率よく行うのに、まだ十分なものとは言えない。第一に、例えば「川崎市宮前区」の「市宮」が接触して1セグメントとされてしまったときなど、単語の境界位置を確定できないようなケースがうまく扱えない。第二に、2段目の単語列探索で最良解が保証されるように、1段目の虫食い照合で正解文字欠落のあらゆる可能性を求めておこうとすると、最悪の場合、単語辞書の全探索あるいは候補文字の組合せ爆発が起きる。そうでなければ、虫食い照合に1文字不一致のみのような制限を付けて、可能性を切り捨てることになる。1段目の単語照合に限ってみれば、各文字位置から単語へのインデックスをもつ松本らの手法が効率よい虫食い照合を可能にしているが、そのままではフリーピッチの単語列読取りには適用できない。本稿では、上記のような問題を解決するたの、従来の2段構成とはまったく異なる知識処理の枠組みとして、「文字タグ法」と名付けた新しいアルゴリズムを提案する。手書き宛名住所から都道府県名・市区郡名・町名の並びを読み取る応用を例に概要を紹介する。
- 著者
- 福島 俊一 下村 秀樹 森 義和
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.37, no.4, pp.500-510, 1996-04-15
- 被引用文献数
- 19
本論文では フリーピッチ手書き文字列の読み取りのために 新しい知識処理アルゴリズムである「文字タグ法」を提案する. 字形が多様で 文字サイズ・文字ピッチにばらつきがあり 文字の接触・入り組みなどもよく起きる手書き文字列の読み取りでは 誤切り出しや誤認識によって欠落した正解文字を補完する知識処理が不可欠である. 従来の知識処理方式は 単語辞書と候補文字列とを照合して単語候補を抽出したうえで その並びの妥当性を判定する2段構成である. このような従来法では 単語境界が不確定なケースをうまく扱えないことや 候補文字列と単語辞書との虫食い照合における組合せ爆発を避けると 強引に候補を切り捨てることになって最良解を保証できないことなどが大きな問題になっている. これに対して 本論文で提案する文字タグ法は 文字を基本単位としてタグを付与し その位置関係をチェックしながら連結していく戦略をとる. 単語内の文字の連結と単語間の文字の連結とを同等に扱って動的計画法を適用することで 最良解を保証し かつ 入力文字列の長さLと候補多重度Mに対してO(L^2・M^2)またはO(L・M^2)の時間計算量を達成している. さらに 手書き宛名住所の地名領域の読み取りに文字タグ法を応用し 文字切り出しや個別文字認識のあらゆる組合せと正解文字欠落の可能性の中から最良解を高速に探索する文字タグ法の能力を確認した.This paper proposes a new algorithm for post-processing in a hand-written character reader. Hand-written characters have such characteristics as various styles, irregularity in size and pitch, frequency of character overlapping, and so on. These characteristics bring difficulty into hand-written character reading systems. Post-processing to correct mis-segmentation and mis-recognition by linguistic information is an important approach to accurate reading. Conventional post-processing methods consist of two steps. In the first step, word candidates are extracted by word dictionary looking-up. In the second step, combinations of words are evaluated. These conventional methods have the following problems. The first problem is that they don't work well when word boundary segmentation is missed. The second one is combinational time complexity, required for examinations of all combinations of character segmentation candidates and character recognition candidates by approximate matching. In the algorithm proposed in this paper, character candidates are tagged with position-in-word information, and the position-in-word tags are connected by a dynamic programming method. This algorithm has the advantage of time complexity O(L^2・M^2) or O(L・M^2) for optimum path search, where L is input length, and M is average number of segmentation and recognition candidates per character. This paper also describes its implementation and evaluation results in hand-written Japanese address reading.