JPH04502526A - 像認識 - 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. （１９）ビットマップ上に表された像を分割するための装置であって、像に対応 している形状を検出するためにビットマップ上を走査する走査手段と、該検出さ れた形状を規定するビットマップ上の画素の位置を記録するための記憶手段とを 有し、該記憶手段に位置が記録されていなかったビットマップの画素に対しての み該走査手段が感応することを特徴とする装置。