JPH06501800A - 手書き数字認識装置及び方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】

手書き数字認識装置及び方法 発明の分野 本発明の技術分野は、光学文字認識、そして特に手書き数字の認識に関する。 発明の背景 互換性のあるコンピュータで読取り可能な書式では得ることができない文書の、 コンピュータで読取り可能な書式を提供することが、有益または望ましい多くの 例がある。通常、それは、文書が手書きまたはタイプ打ちしたもので、そのため コンピュータで読取り可能な書式が存在しないため、またはコンピュータで読取 り可能な書式が得られないために、当該文書が機械で読取り可能な書式では得ら れない場合である。ある場合には、「異質」な文書、即ち既存のコンピュータ読 取り可能書式ではあるが、文書が互換性のないコンピュータシステム上で生成さ れたものであることがある。ある場合には、ファクシミリ送信のように、文書の 単純な光学スキャンで、必要な書式を生成することができる。はとんどの場合、 後の使用及び決定のために最も有用な書式は、文書の各文字が、別々に示されて いることである。 光学文字認識分野は、印刷したまたは手書きの文字の分離及び指示の問題に対処 している。光学文字認識では、文書がある方法でスキャンされて、当該文書の記 号の電気的画像を生成する。この記号の画像がコンピュータによって分析されて 、文書の各文字の指示を生成する。多くのタイプ打ちの及び印刷した文書で、比 較的誤りのない指示を生成するのは、現在の先端技術におけることである。従来 技術の最良のシステムは、多くの異なるタイプフォントを適切に区別することか できる。 一方、制約のない手書き文字は、現在の光学システムでは、満足に位置を突きと め認識されてはいない。制約のない手書き文字を適切に読取る問題は、文字の広 い変化性のため困難である。人は、同一文字をいつでも正確に同一に書くことは てきない。異なる人が書く同一文字間の変化性は、−人の人の変化性より更に広 くなる。文字自体の変化性に加えて、手書き文は、しばしば明瞭に筆記されない ことかある。したがって、文字か水平方向に重なり合うこともある。ループやデ センダ（ｄｅｓｃｅｎｄｅｒ）は、垂直方向に重なり合うこともある。２つの文 字が共に繋かったり、１つの文字のス）・ローフが同一文字の他のストロークと 離れていることもある。更に、個々に書かれた行が斜めになっていたり、不規則 な輪郭を有することもある。手書きの異なる部分は、大きさか異なることもある 。このように、手書き文字の認識は、困難な作業である。 手書き文字の認識か非常に貴重な分野の一例は、手紙の区分けである。手紙の１ 通毎に、目的地の住所によって分類しなくてはならない。現在、大量のタイプ打 ちの及び印刷された手紙が、従来技術の光学文字認識技術を用いて、読み取られ そして区分けされている。現在、約１’５％の現米国郵便物の住所が手書きされ ている。現在の技術は、自動化されたコンベアシステムを用いて、−回に１通ず つこれらの郵便物を操作者に渡し、住所を見て目的地のコードを記入する。これ は、郵便物区分は作業中、最も労働集約的で、最も遅く、結果的に最も高価な部 分である。 更に、郵便番号（ＺＩＰコード）の誤識別や、郵便物の間違った郵便局への送出 は、高くつくものである。一旦郵便物が受信郵便局に差し向けられると、その受 信郵便局は、その郵便番号には、一致する住所も受信人もいないことを認める。 そして、その郵便物は、再び区分けされ、正しい郵便局に再度送られることにな る。誤配された郵便物に伴う高い出費のため、自動化されたシステムが非常に高 い精度をもってしても郵便番号を判別できない場合、システムに郵便物を拒絶さ せるほうが望ましいのである。拒絶された郵便物は、次に送出局において手作業 で区分けすることができるし、或いは、池の対策を取って誤配達の経費を根絶ま たは低減させることができる。 手書き郵便物の区分けは、特異な特徴の集合を有する領域である。第１に、ユー ザの受入れの問題のために、住所に更に制限を加えるのは、現実的でない。した がって、認識作業を画一化するのに有用な、住所行または個個の文字枠は、除外 される。一方、比較的制約された部分か、現行の住所には既に存在する。大多数 の手書きされた目的地の住所に用いられている郵便番号は、最初の区分は作業に 必要とされる全ての情報を提供するものである。郵便番号には９桁の長い郵便番 号を用いているものもあるが、殆との手書きされた郵便番号は、５桁でフォーマ ットされている。郵便番号は５或いは９桁でのみ構成されているので、この情報 は比較的制約されているものである。加えて、郵便番号は、通常目的地住所の最 後の行の最後に位置しているか、時として最後の行にそれ自体のみか配置されて いることかある。 手書き数字を認識するための種々のシステムか考案されている。しかしなから、 これらのシステムの多くは、数字の位置か既に分っていて、分離されていること を前提としており、問題は手書きされた数字かどの数字を表わすかを判別するこ とのみである。多くの場合、これらのシステムは、数字を個々の枠内に書くこと を要求している。 コンピュータか、典型的に封筒において見られる住所欄内の手書き郵便番号の手 書きされた数字を分析しかつ認識するためには、郵便番号を含む数字群は、先ず １つの集合として、首尾よくその位置が見出されなければならない。 数字の数及び位置として上述の制約か存在するが、郵便番号の位置を突止めるた めの以前の試みには、問題点が見出されている。手書きを首尾よく認識するため に一般的に存在する同じ問題が、郵便番号の位置を突止めるための問題となって いる。手書きの住所欄の行を数えるための、以前の試みは、ループ、デセンダ、 行の傾斜、または他の行の不規則性によって、困難となった。 必要とされるのは、郵便番号の数字の分析の前に、住所欄の郵便番号の位置を正 確に突止める、信頼性の高いシステムである。 発明の概要 本発明の１つの態様によれば、コンピュータシステムがデジタル化された住所欄 から郵便番号の位置を突止めるように、設計されている。住所欄は、住、所が書 かれた封筒、集蓄、またはその他のラベルから、光学スキャニングによって、得 ることかできる。デジタル化された住所欄は、マトリクス状に配列された画素か ら成るものである。好ましくは、デジタル住所欄は、二進であり、画素は前面画 像の一部または背面画像の一部のいずれかである。 前記コンピュータシステムは、同一行内にある前面画像の、連続しているか分離 されている画素間の水平方向距離を計算するための機構を備えている。前記コン ピュータシステムは、続いて、ストローク間距離として指定される、距離の発生 における第１の大きなピークを編集し、そして判別する。予測される用途では、 前面画像は、住所欄の文字ストロークを表わす。ストロークは、ストローフ間距 離を基に、単語に組み立てられる。 単語は、次に、集合化（ｇｒｏｕｐｉｎｇ）即ちブロックに、フォーマットされ る。住所欄の異なる行間の垂直方向の繋がりは、ストロークの水平方向の浸食（ ｅｒｏｓｉｏｎ）によって、分解される。単語プロ・ツクは次に削ぎ落とされて （ｓｋｅｌｅｔｏｎｉｚｅｄ）、水平方向のスケルトンのみを残す。サブシステ ムが、得られた水平方向スケルトンを垂直方向に広げて枠に入れる。各枠は均一 な高さを存している。そして、それら枠を水平方向に広げ、水平方向に重なりあ っている枠を共に合併させて行画像を形成するようにする。この行画像に、画像 の最上部から唯一の名称を付け（即ち付番する）、行番号を生成する。別のサブ システムか、次に各行画像の中実軸を決定し、行番号が付けられた中実軸を、元 のデジタル化された住所欄に重ね合わせる。 望ましくは、コンピュータシステムは、次に各中実軸から行番号ラベルを抽出（ ｂｌｅｅｄ）して、この中実軸に繋かれている全てのストロークを識別する。２ 本の水平軸に繋がれているストロークは、上の行または下の行のいずれかに分類 される。この機能は、いずれの中実軸とも繋がれていない前面画像の画素を識別 し、そしてそれらの画素を後続の行のカウントから除外する。郵便番号を含むこ とかできる程十分に広い、望まれている最終行が選択され、ストローク間距離及 びいずれの中実軸とも接触していない識別された前面画像の画素から、最終行の 可能性のある単語分割を判断する。１つの単語分割部が選択され、その分割部か らの単語を、郵便番号位置として識別する。 好ましくは、デジタル化された住所欄の境界枠を作成する機構を備え、この境界 枠内の画素にのみ処理を施すことによって、コンピュータの動作時間を短縮する 。更に、前記境界枠内の画素を、ダウンサンプル（ｄ　ｏｗｎｓａｍｐｌｅ）し て、必要な計算及び処理を行ないつつ、コンピュータ時間を更に短縮する。 好ましくは、前記コンピュータシステムは、並列処理システムを組み込んでいる 。計算時間は、したがって、受は入れ可能なレベルにまで短縮され、一方、十分 に強力な汎用コンピュータの費用が避けられる。 本発明のより広い一面によれば、本発明は、手書きまたは機械印刷文字から得ら れる文字画像を形成する画素の、より広い選択の中で、所定の画素群の位置を突 止めるための、コンピュータシステム及び方法に関するものである。前記コンピ ュータシステムは、同一行にある分離された前面画像の画素間の水平方向距離を 計算して、ストローク間距離と名付けられた距離長の第１のピークを判定する。 前記コンピュータシステムは、ストローク間距離を用いて、住所−の画像を別個 の行画像に分離してブロックを形成し、そのブロックを水平方向に浸食して、行 に跨がるストロークを分解し、ブロックを削ぎ落とし、そしてその後削ぎ落とし たブロックを広げて手書きされた画像の行を形成する。次に、ストローク間距離 と各行のいずれの中実軸とも接続していない識別された前面画素とを用いて、特 定の行にある画素群か選択され４、

【図面の簡単な説明】

次に、添付図面に言及するか、ここで、第１図は、本発明の好適実施例において 用いられた郵便番号位置検出プロセスを、流れ図形式で示す。 第２図は、サンプル住所欄とその境界枠を概略的に示す。　第３図は、前面画像 の２つの連続しているが分離されている画素間の水平距離を概略的に示す、境界 枠内の住所欄の拡大図である。 第４囚は、第３図に示されたストローク間距離に基つく、ストロークの単語ブロ ックへの配置を概略的に示す。 第５図は、デセンダ及び行間の垂直方向の接続の分解、及び凸状外郭（ｈｕｌｌ ）の形成を、概略的に示す。 第６図は、凸状外郭の削ぎ落としを、概略的に示す。 第７図は、水平方向に行内に広げられた単語枠領域か、垂直方向に広げられ様子 、及び各行に形成された中実軸を示す。 第８図は、第７図に示された各行の中実軸の、第２図に示された元の境界を規定 されダウンサンプルされた住所欄・＼の重ね合わせ、及び中実軸からの文字の抽 出を示す。 第９図は、先のステップによって判別された最終行の選択を示す。 第１０図は、単語の選択された分割の１一つを開示する。 第１１図は、単語の選択された分割の別のものを開示する。 第１２図は、郵便番号に対して選択された、好適な選択された単語を開示する。 第１３図は、第１２図において選択された単語に相関する郵便番号を開示する。 第１４図は、本発明の好適実施例において用いられる、形懸学盟コンピュータを ブロック図形式で開示する。及び、　第１５図は、第１４図に示された形態字型 コンピュータの近傍処理段階の１つを、ブロック図形式て示す。 好適実施例の詳細な説明 第１図に示された方法を実施する、本発明の郵便番号位置検出システムは、住所 欄内の郵便番号の位置を突止めることかできるものである。第２〜１３１１は、 第１図に描かれたステップの例示を行なうもので、第１図の記載が進行するにつ れて、この例を参照することにする。 第２図に示された手書きの架空の見本は、手書き住所において起こり得る幾つか の問題を示している。この手書き見本は単なる例であり、以下に記載する同一の 方法は、示されたものとは全く別個でしかも非常に異なることもあり得る他の手 書き文字にも、同様に適用可能であることは、理解すべきである。 示された例は、種々の従来技術のシステムに対して指摘された問題と共通の幾つ かの問題を存している。最初の行のｒＪｏｈｎＪにおける「Ｊ」は、２番目の行 の中実軸の下にまで達している。更に、中間イニシャルの「ｐ」は、実際その下 の行のｒｎＪ　と繋がれている。中央行内の「Ｓ」及び［ｔＪは、その下の行の 郵便番号の先頭の下まで延びている。「Ｓ」の下部は、更に郵便番号の最初の「 ０」の延長部と繋がれている。２番目の「ＮＹ」は傾斜しており、それゆえ該「 ＮＹ」の上部か、垂直方向に、その上の行の単語ｒＳｔｒｅｅｔＪの「Ｓ］、「 ｔ」及びｒｒＪの下部より上に位置している。 単語ｒＭａｉｎ」は、単語ｒｓｔｒｅｅｔ」に対して非常に高く位置しており、 それゆえ住所のこの行は非常に波打ってしまっている。文字はまた大きさかまち まちである。例えば、２つの大文字のｒ　Ｍ　Ｊを比較されたい。 更に、例えば、ｒＭａｉｎ」のｒＭ」、イニシャル「Ｐ」、及び郵便番号の最初 のｒＯＪのように、文字は余分なループを存している。更に、ストロークは比較 的角張って（ｊａｇｇｅｄ）おり、郵便番号は、ｒｔＪの侵入、及び２番目の「 ０」とｒ７Ｊとの間のより広い空間によって、一様に分離されていない。 第２図に示されるデジタル化された住所欄２１は、システムへの入力２０を形成 する。欄２１は、元来光学スキャンによって得ることかできるか、或いは先にデ ジタル化し、ディスク上にまたは他のコンピュータ記憶技術によって記憶するこ とかできる。住所１１２＋は、水平方向及び垂直方向に行及び列に割り振られた 画素の配列状て、デジタル形状で入力される。住所欄の画素は、背景状態または 画像状態を有することができる。画像状態は、間引きした構成要素、終点、結合 、及び「肉（ｆｌｅｓｈ）」、即ち間引き中に除去された画像部分の状態をあげ ることかできる。住所１１２１は、先ず、雑音、欠落、不連続のストローク、及 び画像の分析に影響を与え得る画像処理の欠陥を含む、その質について分析され る（ステップ２４）。欠陥は、次に定量化され、そして画像はある質２２として 分類される。供給される住所欄２１は、次に、所望の程度に雑音及び欠落がろ過 される（ステップ２６）。第２図に示されるような境界枠２３か決定される（ス テップ２８）。境界枠は、第２図の例によって示されるように、画像のストロー クの最も右、左、上及び下の広かりによって決定される。前記画像は、ステップ ３０によって示されるように、境界枠２３内でダウンサンプルされる。境界枠か 形成され、ダウンサンプルされるのはコンピュータ時間を短縮するためである。 次に、住所１１２１は、第３図に概略的に示されるように、その水平ストローク の分離が計算される（ステップ３２）。連続するか分離されており、かつ水平方 向に整列された２つの間の水平方向間隔が計算される。連続するが分離された異 なるものの間の間隔は、異なる長さの空間２５．２７．２９及び３１によって、 例示されている。共通な印刷及び手書きは、３１と付番されたストローク距離に よって示されるように、最も隣接した垂直ストローク間の間隔に共通の範囲かあ ることを規定する。大幅に狭いギヤツブ距離は、ストローク距離３１よりも生し る頻度か少ない。水平方向に隣接する画像単語間のギャップ距離２５にほぼ等し い距離は、より狭いストローク距離よりも生しる頻度か少ない。加えて、ストロ ーク距離３１よりわずかに広い水平方向ギャップの数は減少し、コンピュータか 、ストローク間距離と名付けられた、距離３１とほぼ等しいストローク距離の第 １のピークを計算することかできるようになっている。 住所１１２１に対して計算されたストローク間距離３１を規準として、ストロー クを単語内に配置していく（ステップ３４）。単語３５は、第３図におけるスト ローク間距＃１３１と、より広い距離２５及び２９によって、判断される。集合 化ステップ３４の結果が、第４図に示される。ブロック３５は、各単語の集合化 を概略的に表わしている。行間の垂直方向ストロークの繋がりは、水平方向の拡 張、及び文字の薄いデセンダ及び長い延長部３７が除去される、文字の水平方向 に対する後続の浸食によって、分解されている（ステップ３６）。デセンダ及び 延長部３７の除去は、２つの隣接する住所の行間の繋がりを、分解するものであ る。 単語３５の各ブロックは、次に完全に分離され、そしてこれらの群ブロック３５ は、浸食された画像について凸状外郭に形成される。外郭３３は、次にステップ ３８に示されるように削ぎ落とされて、第６図に示されるようなスケルトンセグ メント３９となる。ステップ４０に示されるように、ブロック３５は、更に水平 方向に集合化されて、住所行が得られる。これは、スケルトンセグメント３９か ら、削ぎ落とされたセグメントを垂直方向に拡張し、均一な垂直方向の厚さの枠 状領域４１を形成することによって、達成される。第７図に示されるように、枠 状領域４１は、次に、領域４３において示されるように、１つの領域４１の隣接 領域４１との水平方向の重複が、いずれも満たされるように、水平方向に拡張さ れる。 次のステップ４４は、行番号にしたがって、ストロークを分類することである。 これは、第７図に示される各行ｌ、２及び３に対する中実軸４５を決定し、そし て第８図に示されるように、行番号を付けられた中実軸４５を住所ブロック２Ｉ の元のダウンサンプルされた画像上に重ね合わせることによって、達成される。 繋がり状態（ｃｏｎｎｅｃｔ　１ｖｉｔｙ）に基づいた行番号抽出過程が行なわ れる。抽出過程は、行番号を付けられた中実軸において開始する。直接中実軸に 繋がれている文字（Ｉｅｔｔｅｒｉｎｇ）または中実軸に接触しているストロー クに繋かれているストロークは、いずれも行ｌ、２または３のいずれかの中実軸 に属するものとして識別される。例えば、単語ｒｓｔｒｅｅｔＪの「ｔＪのデセ ンダは、それが３行めの「０」の上部及び「７」の上部の下にあるが、２行目の 一部として識別される。 ｒＭｒＪのｒｒＪは、中実軸４４の下に位置しているか、ｒＭ＋に繋がれており 、行番号抽出は「Ｍ」からｒｒＪに生じるので、第１行の一部として識別される 。 抽出は、また、互に繋がれている異なる２本の線の文字を定義する助けにもなる 。中間イニシャルの「Ｐ」の延長部、及びｒＭａ　ｉｎ」のｒｎＪの延長部は、 そのように繋がれており、更に、単語ｒｓｔｒｅｅｔ」の「Ｓ」及び３行目の「 ０」が繋がれでいる。これらの文字は、夫々の文字の抽出によって、別個に分割 される。 異なる行の抽出は、点５１において一致する。当然、点５１より上のいかなる画 像の画素も、上部の文字と共に識別され、そして点５１より下のいかなる画像の 画素も下部の文字と共に識別される。終止符５３及びコンマ５５は、いずれの軸 にも繋がれておらず、それゆえ分類されずに句読点記号として指定される。 抽出、句読点、及びストローク間距離に基つき、ステップ４４に示されるように 、ストロークは行内の単語に集合化される。我々はここで行に集合化された単語 候補を得たのである。そして、ステップ４６は、不可能に短い線を破棄するか、 あるいは、それらの線の間に水平方向の重なり合いか在れば、ステップ４８に示 されるように、その短い線を一緒に併合する。第９図に示される最後即ち一番下 の行５７は、ステップ４９に示されるように選択される。しかしなから、最後の 行は、上の行のｒｓｔｒｅｅｔ」のｒｔＪの一番下の延長を含まず、更にそれは 点５１より上の最初の「０」の部分を何も含まない。 最終行５７は、ステップ５０に示されるように、単語に分割される。第１０図は 、３つの単語への分割を示しており、句読点記号５５の前のｒＮＹ」が１つの単 語５９を形成し、第３図に示されるように、２番目の「ＮＹ」が句読点記号５５ の後で比較的広いギャップ２７の前の単語６１を形成している。ｒｌｏ０７３」 は第３の単語６３を形成している。第１１図に示されるような、別の分割も行な われる。この別の４単語分割では、「ｌＯＯ」が６５と付番された１つの単語、 そして「７３」が６７と付番された第２の単語となっている。 この分割は、２番目の「０」と「７」との間の少し広めの距離の結果である。し かしながら、例えば、単語６７の大きさが郵便番号にしては、そしてストローク 間距離を基にするにはそれ自体小さすぎること等、他の制約のために、第１０図 に示されるような単語分割が第１１図に示される単語分割よりも好ましい。単語 ６３は、次に、郵便番号の位置として、そして第１２図に示されるように、選択 される。 ステップ５２は、単語６３０対応する文字６９が、第１３図に示されるように、 全解像度で示されることを規定する。ステップ２２において示された画質の等級 に基づいて、単語６３内の雑音、しみ及び欠落が、ステップ７０に示されるよう に修復される。じみや雑音がステップ７２で分類され、単語６３内の画像の画素 か、ステップ７４てスクリーン上に示される。郵便番号は、次にステップ７６に おいて、数字分離器に転送され、そこで郵便番号数字群か区分され、そしてステ ップ７８で数字認識器を用いて数字か分析され認識される。偶然９桁の郵便番号 か用いられていると、その９桁の郵便番号か検出され、そして数字分離器は、５ 個の数字ではなく、９個の数字を判別する。 郵便番号位置検出過程で用いられるコンピュータシステムは、好ましくは、１９ ７９９７９年９月１１日スターンバーブｅｒｎｂｅｒｇ）に発行された、「自動 画像処理装置Ｊと題された、米国特許第４１６７７２８号にしたがって構成され 、商業的に「サイトコンピュータ（Ｃｙｔｏｃｏｍｐｕｔｅｒ）Ｊ　として知ら れている、形態学型コンピュータであることが好ましい。米国特許第４１６７７ ２８号の教示を、ここに参考として取り入れる。要約してその構成を、第１４及 び１５図に関連して説明する。形態学型コンピュータ７０の全体構成は、第１４ 図に示されており、そして１つの近傍処理段階８０の構成か第１５図に示されて いる。 一般的に、形態学型コンピュータ７０は、複数の近傍処理段階８０．８２．、． ８４のパイプラインを備えている。最初の近傍処理段階８０は、ラスクスキャン 状で供給される住所欄としての二進画像の個々の画素に対応するデータ流を、そ の入力として受け取る。供給される住所欄の画像は、複数の行及び列に配列され た個々の画素に対応するデータを含んでいる。ラスタスキャンデータ流は、最も 左側の画素から最も右側の画素までの最上行から始まって、左から右の順で次の 行が続き、同様に各連続する行が続く順序の画素から成る。 一方、近傍処理段階８０は、これもラスタスキャンシーケンス状の変形された画 像の個々の画素に対応する出力データ流を生成する。この出力データ流の各画素 は、入力データ流の特定の画素に対応する。近傍処理段階８０は、対応する入力 画素の値及び８個の対応する隣接画素の値を基に、出力データ流の各画素を形成 する。このように、出力データ流の各画素は、対応する入力画素の近傍に対応す る。各近傍処理段階８０．８２．、、の出力は、次に続く段階の入力に供給され る。最後の近傍処理段階８４の出力は、形態学型コンピュータ７０の出力を形成 する。 各近傍処理段Ｆｉ８０．８２．、．８４によって行なわれる特定の変形即ち近傍 処理は、変形制御器９０によって制御される。各近傍処理段階８０．８２゜２． ８４は、唯一のデジタルアドレスを有する。変形制御器９０は、アドレス線９２ 上に特定のアドレスを指定し、そしてコマンド線８４上に特定の変形に対応する コマンドを指定する。指定されたアドレスを有する近傍処理段階８０．８２、、 ．８４は、そのコマンドを記憶する。各段階は、次に、それが最後に受け取った コマンドに対応する変形を行なう。 第１５図は、より詳しく、近傍処理段階８０の一例の構成を示すものである。近 傍処理段階８０は、画素素子１００−１０８及びシフトレジスタ遅延線１１０及 び１１２によって形成される遅延線と共に動作する。画素素子１００−１０８は 各々、入力された画像の１つの画素データに対応するビットを記憶することがで きる。 標準的な拡張及び削ぎ落としは、５つの状態、即ち背景、間引きされた構成要素 、終点、結合、及び「肉」の１つに、各画素を定義する必要があるので、最も予 測可能な使用において、８ヒツトまたは１６ビノトの画素で十分てあろう。シフ トレジスタ遅延線１１０及び１１２は、画像の各ライン内の画素数より３少ない 長さを存している。このシフトレジスタ遅延線１１０及び１１２の長さは、画素 素子＋００．１０３及び１０６が入力画像内の垂直方向に隣接した画素に対応す るデータを記憶することを保証するように選択されたものである。同様に、デー タ及び画素素子１０Ｌ１０４．１０７は、垂直方向に隣接する画素に対応し、画 素素子１０２．１０５．１０８内のデータは垂直方向に隣接する画素に対応する 。 画素データは、ラスクスキャン状で、近傍処理段階８０の入力に供給される。画 素はまず画素素子１００内に記憶される。次の画素を受け取った時に、画素素子 ｌＯＯ内に記憶されている画素は、画素素子１０１にソフトされ、新しい画素か 画素素子１００に記憶される。 次の画素を受け取ると、最初の画素を画素素子１０２に、そして２番目の画素を 画素素子１０１にシフトし、受は取ったばかりの画素か画素素子１００に記憶さ れる。遅延線に沿ってデータをシフトするこの過程は、第１５図に見られる矢印 の方向に、続けられる。一旦画素が画素素子１０８に到達すると、次の画素を受 け取った時にそれは破棄される。 近傍処理段階８０は、適切な画素データを組合せ回路１１４に与えることによっ て、動作する。一旦シフト遅延線１１２及び１１０が満たされると、画素素子１ ００−１０８は、元の画像において隣接する画素要素の３ｘ３マトリクスを記憶 することに、注意されたい。画素素子１０４か中央の画素を表わす場合、画素素 子１００．１０１１１０２．１０３．１０５．１０６．１０７．１０８は、８つ の直に隣接する画素を表わす。この組合せ回路１１４は、９個の画素のある組合 せを形成する。そのような組合せは、多くの形状を取ることができよう。 画素出力データは、形成された組合せによって、入力データより多い或いは少な いビットを有することがある。 また、組合せ回路１１４は１つ以上の画素間、または１つの画素と変形制御器９ ０から受け取った定数との間の比較を行なうことも、実現可能である。重要な点 は、組合せ回路１１４が、画素素子＋００−１０８内に記憶されている画素のあ る組合せから、１つの出力画素を形成することである。 第１４及び１５図の構成の、画像処理に対する利点は明白である。各近傍処理段 階８０、ｓ２．、、ｓ４は、データかメモリから呼び出されるのと同し速さで、 受は取った画像データに近傍処理を施す。各段階は、それが画素を受け取るのと 同じ速度で対応する出力画素流を生成する前に、画像のライン長に関する固定さ れた遅延が必要なだけである。何十、何方、何千ものこれら近傍処理段階を、鎖 状に配置することができる。各近傍処理段階は比較的単純な１つの機能のみを行 なうのであるが、このような段階の長い鎖を設けることにより、短い時間枠の中 で大量の画像処理が可能となる。これまでの説明から分るように、郵便番号の位 置検出は、デセンダ、傾斜した線、及び角張った線、不規則な間隔、中断したス トローク、相互に繋かれた文字及び線、及びインクのしみ、そしてその他の画像 の雑音のような、手書きされた郵便番号に固有の多くの問題のために、複雑で大 量な計算が必要である。典型的な手書き住所欄を処理してその欄内の郵便番号の 位置を突止める計算能力を得るためには、上述のようなハードウェアシステムが 必要とされる。 添付の４Ｈ’Ｆ請求の範囲に規定された本発明の範囲及び精神から逸脱すること なく、本発明の変容及び変更か可能である。 ニ】＝匡＝＝、工工 二＝＝＝土二 国際調査報告

Claims (19)

【特許請求の範囲】
1. １．列及び行の配列内に並べられたデジタル画素画像から選択された所定の画素 群の位置を突止めるためのコンピュータシステムであって、前記デジタル画像は 、複数の行内に配列された文字を形成するものであり、水平方向に整列された、 別個の連続画像画素間の水平方向距離を計算し、ストローク間距離と呼ばれる、 距離の発生中の最初の大きなピークを判別する手段と、前記デジタル画素画像を 水平方向に浸食して、前記複数の行における前記文字の垂直方向の分離を強化す る手段と、ストローク間距離と前記文字間のより広い距離を基に、文字を一緒に ブロックに集合化する手段と、前記ブロックを削ぎ落として、各ブロックの水平 方向長にわたる線を得る手段と、 結果的に得られた削ぎ落とされた画像を、垂直方向に拡張して、均一な垂直方向 の厚さの枠領域を作成する手段と、前記結果的に得られた枠領域を水平方向に拡 張して、水平方向に重なり合う枠領域が共に合併されて、行画像を形成する手段 と、 各夫々の行画像の中央軸を決定し、名称を付ける手段と、前記各中央軸から名称 を抽出して、直接または別の画素を介して、ある中央軸と繋がれている画像画素 を識別し、２本の異なる中央軸内にあり、かつ共に撃げられている２つの異なる 名称を付けられた文字を分割し、２本の中央軸の抽出が満たされるようにする手 段と、ストローク間距離から、前記文字と関連する可能性のある文字群の所望の 行を識別する手段と、及びストローク間距離を用いることによって、前記可能性 のある単語群から前記所定群の画像画素を選択する手段と、によって特徴付けら れる、前記システム。
2. ２．請求項１に規定されたシステムであって、更に、前記文字は住所欄を形成し 、及び 前記所定群の画像画素は、前記住所欄の郵便番号を形成することによって特徴付 けられる、前記システム。
3. ３．請求項２に規定されたシステムであって、更に、前記識別手段は、郵便番号 を含むのに十分に広い前記住所欄の最後の行を識別し、及び 前記選択手段は、郵便番号を含むのに十分大きなサイズの前記所望の最終行内の 最後の単語群を選択することによって特徴付けられる、前記システム。
4. ４．請求項１に規定されたシステムであって、更にいずれの中央軸とも繋げられ ておらず、それゆえ前記抽出手段によって抽出されない画像画素を議別する手段 と、前記いずれの中央軸とも撃げられていない画像画素を句読点として用いて、 前記所定の群を選択する、前記手段とによって特徴付けられる、前記システム。
5. ５．請求項１に規定されたシステムであって、更に前記デジタル画像の境界枠を 決定する手段と、及び前記境界枠内の前記デジタル画像をダウンサンプルする手 段とによって特徴付けられる、前記システム。
6. ６．列及び行の配列内に並べられたデジタル画素画像から選択された文字の所定 群の位置を突止めるためのコンピュータシステムであって、前記デジタル画像は 、複数の行内に配列された文字を形成するものであり、各夫々の行の中央軸を決 定する手段と、前記画像上に各夫々の中央軸を重ね合わせ、前記デジタル画像を 形成する画素を各中央軸から抽出して、直接または他の画素を介して前記中央軸 に撃がれている画素を識別し、２本の異なる水平行内にあり、かつ共に繋げられ ている２つの文字を分割し、２本の中央軸の抽出が満たされるようにする手段と 、 所望の行を選択する行選択手段と、 前記所望の行内の前記所望の文字群を選択する群選択手段と、 によって特徴付けられる、前記システム。
7. ７．請求項６に規定されたシステムであって、更に、前記入力文字は住所欄を形 成し、及び 前記所望の文字群は、前記住所欄内の郵便番号を形成することによって特徴付け られる、前記システム。
8. ８．請求項７に規定されたシステムであって、更に、前記行選択手段は、前記住 所欄の最後の行を選択し、及び群選択手段は前記所望の最後の行の最後の群を選 択することによって特徴付けられる、前記システム。
9. ９．請求項６に規定されたシステムであって、更に、前記デジタル画像の境界枠 を決定する手段と、及び前記境界枠内の前記デジタル画像をダウンサンプルする 手段とによって特徴付けられる、前記システム。
10. １０．請求項６に規定されたシステムであって、更に、いずれの中央軸とも繋か れておらず、それゆえ前記抽出手段によって抽出されない画像画素を識別する手 段と、及び前記いずれの中央軸にも撃がれていない画像画素を句読点として用い て、前記所望群を選択する手段とによって特徴付けられる、前記システム。
11. １１．請求項６に規定されたシステムであって、更に、水平方向に整列され分離 された画像画素間の水平方向距離を計算し、ストローク間距離と呼ばれる、距離 の発生の内最初の大きなピークを判別する手段と、及び前記ストローク間距離を 用いて、前記所望の文字群を、１つが前記所望群である群を形成するための１つ の要素として選択する前記手段とによって特徴付けられる、前記システム。
12. １２．請求項１１に規定されたシステムであって、更に、前記デジタル画像の境 界枠を決定する手段と、及び前記境界枠内の前記デジタル画像をダウンサンプル する手段とによって特徴付けられる、前記システム。
13. １３．請求項１１に規定されたシステムであって、更に、状態間距離を基に、文 字を一緒にブロックに集合化する手段と、 前記ブロックを、各ブロックの水平方向長に達する線に、削ぎ落とす手段と、 前記線を垂直方向に拡張し、粋領域を作成する手段と、前記結果的に得られた粋 領域を水平方向に拡張して、水平方向に重なり合う枠領域を共に合併し、各行の 行画像を形成するようにした手段とによって特徴付けられる、前記システム。
14. １４．列及び行の配列内に並べられたデジタル画素画像から選択された所定の画 素群の位置を突止めるためのコンピュータシステムであって、前記デジタル画素 画像は、複数の行内に配列された文字を形成するものであり、水平方向に整列さ れた、別個の連続画像画素間の水平方向距離を計算し、ストローク間距離と呼ば れる、距離の発生中の最初の大きなピークを判別する手段と、及びストローク間 距離を用いることによって、前記複数の行の１つの内の前記所定の文字群を選択 する手段とによって特徴付けられる、前記システム。
15. １５．請求項１４に規定されたシステムであって、更に、前記入力文字は住所欄 を形成し、及び 前記所定の文字群は、前記住所欄内において郵便番号を形成することによって特 徴付けられる、前記システム。
16. １６．請求項１４に規定されたシステムであって、更に、前記デジタル画素画像 の境界枠を決定する手段と、及び前記境界枠内の前記デジタル画素画像をダウン サンプルする手段とによって特徴付けられる、前記システム。
17. １７．列及び行の配列内に並べられたデジタル画素画像から選択された所定の画 素群の位置を突止めるための方法であって、前記デジタル画素画像は、複数の行 内に配列された文字を形成するものであり、 水平方向に整列された、別個の連続画像画素間の水平方向距離を計算し、ストロ ーク間距離と呼ばれる、距離の発生中の最初の大きなピークを判別し、前記文字 を水平方向に浸食して、前記複数の行における前記文字の垂直方向の分離を強化 し、前記複数の行の各々の中央軸を決定し、前記各中央軸から前記文字を抽出し て、直接または別の画素を介して、ある中央軸と撃がっている画像画素を識別し 、２本の異なる中央軸内にあり、かつ互いに繋げられている２つの文字を分割し 、２本の中央軸の抽出が満たされるようにし、及び ストローク間距離を用いることによって、前記所望の文字群を選択すること、 によって特徴付けられる、前記プロセス。
18. １８．請求項１７に規定された方法であって、更に、前記デジタル画素画像の境 界粋を決定し、及び前記計算ステップの前に、前記境界枠内の前記デジタル画素 画像をダウンサンプルすることによって特徴付けられる、前記方法。
19. １９．請求項１７に規定された方法であって、更に、前記複数の行のいずれの中 央軸とも繋がれていない画像画素を識別し、 前記選択ステップは、前記いずれの中央軸にも繋がれていないとして識別された 画像画素を、句読点として選択し、前記所定の文字群を選択するのを補助するこ とによって、特徴付けられる、前記方法。