JP3145071B2 - 文字認識方法および装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、階層構造を持つ単
語列の認識にかかわり、特に郵便物の住所を読み取る場
合に好ましい文字認識方法および装置である。

【０００２】

【従来の技術】印刷あるいは筆記された住所などを読み
取るためには、大きく分けて以下の３つの機能が必要で
ある。

【０００３】（１）文字パターンを切り出す。（文字切
り出し） （２）各々の文字パターンの字種を識別する。（文字識
別） （３）文字の識別結果を文字列として解釈する。（文字
列照合） このうち、記載の不備やノイズなどの要因は（１）
（２）では対応しきれない場合がほとんどであり、より
高精度の文字認識のためには（３）の文字列照合におけ
る補完機能が重要である。

【０００４】階層構造を持つ単語列としては、特に住所
文字列の町域部分を代表的な例としてあげることができ
る。この照合方法としては、住所文字列に対し「県」
「市」「町」などのキーとなる文字をもとに住所構造の
候補を求め、階層関係を適用して住所文字列を求める方
式（第４１回情報処理学会全国大会論文集 90 4L-5「住
所の文字認識結果に対する後処理方式の検討」）、住所
を構成する地名を単語照合により抽出し、住所の持つ階
層関係を上位（都道府県）からトップダウンに辿り住所
文字列を求める方式（昭和６４年電子情報通信学会全国
大会 D-465「自由記載住所文字列に対する知識処理」）
などの方法がある。また、情報処理学会論文誌第３５第
６号「手書き漢字住所認識のためのエラー修正アルゴリ
ズム」記載の方法では、オートマトン型単語照合により
候補文字が不完全でも任意の位置にある地名単語を抽出
するとともに、各階層の候補地名をもとに階層関係を下
位の階層から上位の階層へ辿りながら地名間の位置関係
を判定するボトムアップ処理を行うことで、住所表記に
対する柔軟性や補完能力や処理量の問題を解決し、実用
的な方式を実現している。

【０００５】しかし、これらの方式では、文字候補が不
完全な場合単語単位での補完が行われ、ペナルティを付
加することで単語の不完全性を評価しているが、このよ
うな単語補完の結果、ペナルティを科された複数の単語
候補が出現することになり、単語列候補である町域住所
文字列として誤った候補を選択する可能性を大きくして
いることにもなる。

【０００６】

【発明が解決しようとする課題】上記の従来技術では、
読み取り対象となる単語列へのノイズの混入や、文字の
かすれ、手書きによる文字変形などにより不正なパター
ンが発生したり、識別が困難で識別候補文字が不完全な
ものに対しては、単語照合の際に補完した単語候補を出
し、それにみあったペナルティを科すことで対応してい
た。このように単語を最小単位とする照合を行うため、
単語が不完全な場合、候補単語には単語ペナルティが科
されることになり確信度の低い単語候補の中から単語列
を選択しなくてはならず、信頼性に問題があった。

【０００７】本発明が解決しようとする課題は、記載さ
れている単語が文字欠けなどで不完全な場合でも単語を
構成する文字のレベルでの照合を行うことで精度良く信
頼性のある単語列候補を得ることである。

【０００８】

【課題を解決するための手段】上記の課題を解決するた
め、本発明では、本来辞書に存在する単語だけではな
く、単語の一部分を構成する部分文字列をも単語候補と
して用い、文字レベルでの照合を行う。以下では、この
ような単語の一部分を構成する文字列を部分単語、そし
て部分単語による単語照合を部分単語照合と呼ぶことに
する。

【０００９】この部分単語照合は、単語の一部が候補文
字の中から高い信頼度で得られ、さらにこの部分単語に
より候補単語列の選択が可能な場合に行い、この部分単
語を単語候補に加え、階層処理を行うことで、単語列候
補を高い確信度で得ることができる。

【００１０】従来法の補完によっても同じ単語候補が出
ている可能性はあるが、この場合単語に対し文字の一致
度が低い分だけペナルティが過大に科されている。部分
単語は一致度の高い部分だけを用いるため単語ペナルテ
ィが低く、単語列として接続したときにより高い確信度
を得ることができ、単語列候補としての信頼度は高い。

【００１１】

【００１２】

【００１３】

【００１４】

【発明の実施の形態】図１は本発明による文字認識方法
の実施の形態の一例を示す処理の流れである。本例は住
所の記載された面を光電変換して得られた全体画像を入
力とし、読み取り結果の住所文字列を出力とする住所認
識処理である。

【００１５】ここでは、本文字認識方法を、宛名の住所
のうち都道府県から町名までの町域部分の単語列の読み
取りに適用し、候補文字ラティスが不完全になる例とし
て図２のような消印が町域部分に掛かった郵便を想定す
る。

【００１６】郵便物などの宛名記載面を撮像手段（スキ
ャナ部）により画像入力１０１として取り込み、まず、
文字行抽出処理１０２により全体画像から住所文字行を
抽出する。

【００１７】次に、パターン切り出し処理１０３は、文
字となり得るパターン候補を住所文字行から抽出する。

【００１８】文字識別処理１０４は、抽出されたパター
ン候補それぞれについて文字識別辞書１０５を用いて文
字識別を行い、複数の候補文字と各候補文字の類似度を
出力する。

【００１９】文字切り出し処理１０６は、各パターン候
補の文字識別類似度やパターン間の位置関係等をもとに
パターンの取捨選択を行い、一ないしは複数のパターン
列を生成し文字切り出し候補として出力する。

【００２０】単語照合処理１０７は、文字切り出し結果
と各パターンの識別候補文字を組み合わせた候補文字ラ
ティスの中から町域住所辞書１０８の中の単語を検索
し、見つかった辞書の中の単語と候補文字ラティスの該
当部分を比較し、各文字の一致度にみあったペナルティ
を算出して単語候補として出力する。このようにして得
られた単語候補と、それぞれの単語候補の持つ位置情報
から単語候補ラティスが作られる。

【００２１】町域住所辞書１０８には各階層の単語と階
層間の接続関係の情報が格納されており、住所の町域単
語列の生成のために参照される。

【００２２】階層処理１０９は、単語候補ラティス上で
町域住所辞書１０８の最下位にあたる階層から接続関係
を基に上位階層の単語を順に単語候補を探し単語列を生
成する。接続した単語の位置関係の妥当性を接続ペナル
ティとし、単語ペナルティとあわせて単語列としての確
信度を算出し、町域の候補単語列とする。

【００２３】階層処理１０９において、単語ペナルティ
が充分低いにもかかわらず接続すべき上位単語として妥
当なものが見つからない場合、部分単語照合処理１１０
を行う。部分単語照合処理１１０は、接続し得る上位単
語を町域住所辞書１０８から検索してきてこれらの単語
の部分文字列のうち町域住所文字列を同定できるものに
ついては候補文字ラティス上で単語照合を行うものであ
る。この結果、部分単語が候補としてあがり、単語ペナ
ルティと接続関係が妥当なものであるならこれを町域の
候補単語列とする。

【００２４】読み取り結果選択処理１１１は、町域住所
の候補単語列としてあげられたものの中から確信度をも
とに町域部分の認識結果として最も確信度の高いものを
選択する。

【００２５】町域候補が選択された後、候補文字ラティ
スの各町域候補の末尾に続く位置からそれぞれ丁目・番
地を表す街区番号の読み取り１１２を行い、最終的な住
所読み取り結果１１３として出力する。

【００２６】次に、図１の各処理の詳細を説明する。

【００２７】文字行抽出処理１０２は、郵便物の宛名面
の画像２０１から住所文字行を抽出する処理である。住
所文字行とは、宛名の都道府県名、市町村名から、丁目
・番地までを含む矩形領域２０２を表す。宛名が複数行
に及ぶ場合は行数分だけの矩形領域を出力する。住所文
字行の抽出方法としては、例えば、特開平９−１６１０
１３に記述のあるような方法を用いる。

【００２８】パターン切り出し処理１０３を、図３を用
いて説明する。パターン切り出し処理は、住所文字行２
０２上の黒画素の塊（連結成分）もとにして文字の境界
の候補を抽出し、文字となり得るパターンの組み合わせ
を複数通りあげ、文字パターン候補とする。この時、接
触した文字パターンの切断処理なども行う。３０１は住
所文字行２０２をパターン切り出ししたものをグラフで
表現した図である。以下、これを切り出しグラフと呼
ぶ。

【００２９】文字識別処理１０４は、パターンマッチン
グや構造解析といった既知の方式を用いて実現する。文
字識別により、図４のように抽出されたパターン候補そ
れぞれに対して複数の候補文字と文字識別辞書１０５内
の標準パターンに対する類似度が得られるものとする。

【００３０】文字切り出し処理１０６は、文字識別処理
１０４で得られた各パターン候補の識別候補文字の類似
度やパターン間の位置関係等をもとにパターンの取捨選
択を行い、図５のように一ないしは複数のパターン列を
生成し文字切り出し候補として出力する。パターンの取
捨選択は、類似度やパターン間の位置関係等により重み
付けされた弧を持つ切り出しグラフ上の最適経路探索問
題とみなすことができる。

【００３１】町域住所辞書１０８の構成を図６を用いて
説明する。

【００３２】町域住所辞書１０８は単語照合処理１０
７、階層処理１０９、および部分単語照合処理１１０の
際に参照される辞書であり、図６のように4階層の地名
単語辞書６０１〜６０４から構成される。各階層の地名
単語は上位の階層の地名単語への接続情報を持ってお
り、住所の町域単語列は第３あるいは第４階層の核とな
る単語からボトムアップで接続情報に従って単語を接続
していくことで得られる。単語照合処理１０７では各階
層の地名単語が参照され、単語候補が作られる。階層処
理１０９では、核となる地名単語を参照し、この単語の
接続情報によって上位階層の地名単語辞書へ順に辿って
いくことで単語同士を接続し町域単語列候補を得てい
る。また、部分単語照合処理１１０では、核となる単語
の参照、上位接続単語の探索、および部分単語作成のた
めの単語情報の取得を、町域住所辞書１０８を用いて行
っている。

【００３３】単語照合処理１０７、階層処理１０９、お
よび読み取り結果選択処理１１１は、情報処理学会論文
誌第３５第６号「手書き漢字住所認識のためのエラー修
正アルゴリズム」記載の方式に準じて実現する。

【００３４】単語照合処理１０７では、図７のように、
文字切り出し候補５０１（および５０２）と各パターン
の識別候補文字からなる候補文字ラティス７０１の中の
各候補文字から辞書単語を探索し、１文字目または２文
字目が一致する辞書単語を候補単語としてあげる。「寺
田町」「寺田」「寿町」「中町」「中山」「本宿町」
「本町」「本多」「木野下」は、１文字目が一致する単
語であり、「府中市」「府中町」は２文字目が一致する
単語である。このとき、各候補単語に対し候補文字ラテ
ィス７０１上の各対応文字との一致度を考慮してペナル
ティが算出される。この単語ペナルティは単語の全文字
候補が１位の場合０となる。このようにして得られた単
語候補と、それぞれの単語候補の記載位置に関する位置
情報から単語候補ラティス７０２が作られる。７０２の
例では、例えば「本町」７０３に対しては全て１位の文
字候補があるので単語ペナルティは０となり、「本多」
７０４では「本」が１位で「多」が候補になく、「多」
に対して大きなペナルティが科される。また、「府中
市」７０５に対しては「中」が２位候補のうえ「府」お
よび「市」に対応する候補文字が見当らないため、単語
ペナルティはさらに大きくなる。

【００３５】階層処理１０９は、単語候補ラティス７０
２の最下位にあたる階層の単語（例えば、「本宿町」や
「本町」）を核にして、町域住所辞書１０８の接続関係
をもとに、上位階層の単語を順に単語候補ラティス７０
２から探索し住所の町域単語列を生成する。接続した単
語の記載位置に関する位置関係の妥当性を接続ペナルテ
ィとし、単語ペナルティとあわせて単語列としての確信
度を算出し、町域の候補単語列とする。図８は単語候補
ラティス７０２における階層処理の様子を表したもので
ある。核となる単語はこの場合第３階層であり、接続可
能な上位階層単語はは第２階層の「府中市」のみであ
る。接続関係をもとにしてできる単語列は「府中市寿
町」、「府中市府中町」、「府中市本町」、および「府
中市本宿町」となるが、ここで単語境界のずれを一文字
分だけ許容する場合、位置関係として妥当性のあるもの
は「府中市本町」および「府中市本宿町」となる。しか
しこれらも「府中市」の単語ペナルティが大きい上に、
第２階層単語と第３階層単語に重なりがある分だけ接続
ペナルティも加わり、単語列としての確信度は小さくな
っている。

【００３６】部分単語照合処理１１０を図９および図１
０を用いて説明する。

【００３７】部分単語照合処理１１０は、階層処理１０
９において、単語ペナルティが小さいにもかかわらず、
接続すべき上位単語として妥当なものが見つからない場
合、接続し得る単語を町域住所辞書１０８から検索し、
これらの単語の部分文字列を動的に（すなわち、本来、
町域住所辞書に存在しない部分文字列を一時的に）生成
して、部分文字列のうち町域住所文字列を同定できるも
のについては候補文字ラティス７０１上で単語照合を行
うものである。階層処理１０９において単語候補ラティ
ス７０２上で核となる単語のペナルティが小さく、上位
単語が見つからない場合、まずその核となる単語を含む
町域単語列９０２を町域住所辞書１０８の中から選び出
す。町域単語列を選び出すには、図９のように町域住所
辞書の中から核となる単語を見つけ出し、同単語の接続
情報に従い上位単語を接続して行けばよい。次に、この
ようにして得られた町域単語列のうち、核となった単語
とその上位単語によって一意に決定されるものだけを対
象として以下の処理を行う。対象となる町域単語列は、
核となった単語とその上位単語によって町域単語列が同
定できるわけである。そこで、この対象となる町域単語
列に含まれる単語のうち、核となった単語の上位単語の
それぞれについて部分単語による単語照合を行う。本例
では、ペナルティが小さく接続すべき上位単語として妥
当なものがない単語として「本町」９０１がそれにあた
る。「本町」９０１に対し、町域単語列を一意に決定で
きる上位単語として図１０のように「国分寺市」１００
１「府中市」１００２「田無市」１００３があがったも
のとする。ここでは単語の先頭部分の不完全性を考慮し
て１００４のように単語の末尾から１文字分、２文字分
…と部分単語を動的に作り出す。部分単語による町域単
語列決定の一意性を保つために、作成した全ての部分単
語の中から重複したものを除き、残ったものを部分単語
候補とする。この結果、１００５のような四つの有効な
部分単語が動的に生成される。そして、これらの部分単
語について候補文字ラティス７０１上で単語照合を行
う。これらの部分単語に対し単語照合を行うと図７の単
語候補ラティス７０２にその単語照合結果が追加された
図１０の１００６のような単語候補ラティスが得られ
る。１００６では、「分寺市」「寺市」「中市」が追加
されている。「無市」は候補文字ラティス７０１で
「無」が一致しないので、追加されない 。部分単語が候
補としてあがったなら、追加された単語候補ラティス１
００６に基づいて階層処理を行う。この時、部分単語の
接続関係は元の単語のものを継承するが、上位への接続
は必要ない。本例では、追加された単語候補ラティス１
００６に基づいて階層処理を行うので、「本宿町」や
「本多」を核とした場合の接続も再度検討され、図１１
のように「（府）中市本宿町」「（国）分寺市本多」
「（国分）寺市本多」等の接続も有り得るが、核となる
単語「本宿町」「本多」の単語ペナルティが大きいため
これらは採用しない。こうして、部分単語が候補として
あがり単語ペナルティと接続関係が妥当なものであるな
らこれを町域の候補単語列とする。本例の場合、
「（府）中市本町」「（国）分寺市本町」「（国分）寺
市本町」が候補単語列として加わることになる。

【００３８】読み取り結果選択処理１１１は、町域の単
語列候補としてあげられたものの中から確信度をもとに
町域部分の認識結果として最も確信度の高いものを選択
する。本例では、単語ペナルティおよび接続ペナルティ
から最終的に「（国分）寺市本町」が町域単語列として
得られる。

【００３９】町域単語列の候補が選択された後、候補文
字ラティスの各町域候補の末尾に続く位置からそれぞれ
丁目・番地を表す街区番号の読み取り１１２を行い、最
終的な住所読み取り結果１１３として出力する。

【００４０】

【発明の効果】以上の本発明の方法および装置により、
郵便物の住所の町域部分のように階層構造を持つ単語列
の認識において、単語が不完全な場合でも単語を構成す
る文字のレベルでの照合を行うことで精度良く信頼性の
ある単語列候補を得ることが可能となる。

【図面の簡単な説明】

【図１】本名発明の実施の形態の一例を示す構成図。

【図２】郵便宛名面の画像と住所文字行の一例を示す概
念図。

【図３】パターン切り出し処理と切り出しグラフの関係
を示す図。

【図４】各パターンとその文字識別処理の結果を示す
図。

【図５】文字切り出し候補の例を示す図。

【図６】町域住所辞書の構成を示す概念図。

【図７】候補文字ラティスと候補単語ラティスの関係を
示す図。

【図８】階層処理の手順の一例を示す図。

【図９】部分単語を作成する対象を選出する手順を示す
概念図。

【図１０】部分単語を作成する手順と部分単語照合処理
を示す図。

【図１１】部分単語候補による階層処理の手順を示す
図。

【符号の説明】

１０１…入力画像、１０２…文字行抽出処理、１０３…
パターン切り出し処理、１０４…文字識別処理、１０５
…文字識別辞書、１０６…文字切り出し処理、１０７…
単語照合処理、１０８…町域住所辞書、１０９…階層処
理、１１０…部分単語照合処理、１１１…読み取り結果
選択処理、１１２…街区読み取り、１１３…住所読み取
り結果、２０１…郵便宛名面画像、２０２…住所文字
行、３０１…切り出しグラフ、４０１…文字識別結果、
５０１…文字切り出し候補１、５０２…文字切り出し候
補２、６０１…第1階層地名単語辞書、６０２…第２階
層地名単語辞書、６０３…第３階層地名単語辞書、６０
４…第４階層地名単語辞書、７０１…候補文字ラティ
ス、７０２…候補単語ラティス、７０３…候補単語の例
「本町」、７０４…候補単語の例「本多」、７０５…候
補単語の例「府中市」、９０１…部分単語照合処理を起
動するための核となる単語、９０２…部分単語により同
定される町域単語列、１００１…部分単語作成の対象と
なる単語の例「国分寺市」、１００１…部分単語作成の
対象となる単語の例「府中市」、１００１…部分単語作
成の対象となる単語の例「田無市」、１００４…部分単
語、１００５…有効な部分単語。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 丸川 勝美 東京都国分寺市東恋ケ窪一丁目280番地 株式会社日立製作所中央研究所内 (72)発明者 古賀 昌史 東京都国分寺市東恋ケ窪一丁目280番地 株式会社日立製作所中央研究所内 (56)参考文献 特開 平７−39819（ＪＰ，Ａ) 丸川勝美、外３名「手書き漢字住所認 識のためのエラー修正アルゴリズム」情 報処理学会論文誌、Ｖｏｌ．35 Ｎｏ. ６ 1994年６月 情報処理学会 1101頁 〜1110頁 (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06K 9/72

Claims (1)

(57)【特許請求の範囲】
1. 【請求項１】住所の記載された文書上の記載内容を画像
   入力手段により電気信号に変換した情報から文字行を抽
   出する文字行抽出処理と、 上記文字行の文字の境界の候補を抽出し、文字となり得
   るパターンの組み合わせを複数通りあげ、文字パターン
   候補とするパターン切り出し処理と、 上記文字パターン候補のそれぞれに対して複数の候補文
   字と文字識別辞書内の標準パターンに対する類似度を得
   る文字識別処理と、 上記複数の候補文字の上記類似度やパターン間の位置関
   係をもとに一ないしは複数のパターン列を生成し文字切
   り出し候補として出力する文字切り出し処理と、 複数の地名単語辞書を階層とし各階層の地名単語が上位
   の階層の地名単語への接続情報を持つ町域住所辞書の中
   から、上記文字切り出し候補と各パターンの候補文字か
   らなる候補文字ラティスの中の各候補文字について、１
   文字目または２文字目が一致する単語を単語候補として
   抽出し、各単語候補に対し上記候補文字ラティス上の各
   対応文字との一致度を考慮して単語ペナルティを算出す
   るとともに、それぞれの単語候補の記載位置に関する位
   置情報から単語候補ラティスを作成する単語照合処理
   と、 上記単語候補ラティスの最下位にあたる階層の単語を核
   にして、上記町域住所辞書の接続関係をもとに、上位階
   層の単語を順に上記単語候補ラティスから探索し住所の
   町域単語列を生成するとともに、核となる単語に接続し
   た単語の記載位置に関する位置関係の妥当性を接続ペナ
   ルティとし、上記単語ペナルティと合わせて上記町域単
   語列としての確信度を算出する階層処理と、 上記階層処理において上記核となる単語の単語ペナルテ
   ィが小さいにもかかわらず、上記核となる単語に接続す
   べき上位単語として妥当なものが見つからない場合、上
   記核となる単語に接続し得る単語を上記町域住所辞書か
   ら検索し、検索した単語の部分文字列を動的に生成し
   て、生成された部分文字列のうち重複したものを除いた
   ものについて上記候補文字ラティス上で単語照合を行
   い、１文字目または２文字目が上記候補文字ラティス上
   の候補文字と一致する場合に単語候補 として上記単語候
   補ラティスに追加する部分単語照合処理と、 上記部分単語照合処理を行った場合に、部分単語が追加
   された単語候補ラティスに基づいて行う階層処理と、 上記階層処理により生成された町域単語列の中から上記
   確信度の最も高いものを選択する読み取り結果選択処理
   と、 を有することを特徴とする文字認識方法。