(57)【要約】本発明は、テーブル・ルックアップ・オペレーションのシーケンスを組み込むステート・マシンを使用するパターン認識のための技術を提供する。入力パラメータのシーケンスは、アプリケーションに特有のアルゴリズムに従って導出され、これらのオペレーションのための対応するメモリ・アドレスのシーケンスを生成する。メモリ・テーブルは、入力シーケンスに対応する階層構造において編成される。テーブル・データは、特定の入力パターンのライブラリを認識するように設計される。入力シーケンスが入力特有のパスを、メモリ・テーブルを通じてトレースし、これはライブラリにおけるパターンの１つが認識される（５７８）まで、あるいは入力シーケンスがライブラリ・パターンのいずれかと矛盾すると決定されるまで行われる。各ライブラリ・パターンについて、テーブル・データが、アプリケーションに特有である入力値における変化に対応するように設計される（たとえば、雑音および／または許容差による変化）。テーブル・データを、解析、シミュレーション、学習またはこれらの方法の組み合わせによって導出することができる。本発明は、リアルタイム・アプリケーションにおけるニューラル・ネットワークまたはＤＳＰ相関技術に取って代わることができる。これは非常に高いパフォーマンスを、入力シーケンスをライブラリにおけるすべてのパターンと同時に比較することによって達成する。本発明を使用して、フラットパネル表示技術を使用するカリグラフィック表示システムのイメージ品質を向上させることができる。イメージ・メモリを使用して、コンピュータにより生成されたイメージをリフレッシュする表示システムのパフォーマンスを向上させるための方法も開示される。
2004537768.tif 000002
【特許請求の範囲】
【請求項１】
パターンを認識するための方法であって、
メモリ・アドレスのシーケンスを導出するステップであって、前記メモリ・アドレスは、少なくとも１つのメンバ・パターンを有する少なくとも１つの既知のパターン・セットに比較されるべきである入力を反映する値を含むことを特徴とする、ステップと、
前記メモリ・アドレスのシーケンスを、対応するメモリ・テーブル・ルックアップ・オペレーションのシーケンスに適用して結果を生じるステップと、
前記メモリ・テーブル・ルックアップ・オペレーションの前記結果に従って、前記入力が前記少なくとも１つの既知のパターン・セットのいずれかのメンバ・パターンへの推定合致であるとして認識されるかどうかを決定するステップと、
を含む方法。
【請求項２】
前記入力が、前記少なくとも１つの既知のパターン・セットのいずれかのメンバ・パターンへの推定合致であるとき、複数のメモリ・テーブルに、予想されたメモリ・アドレス値のシーケンスを反映するデータをロードするステップをさらに含み、少なくとも一部の前記複数のメモリ・テーブルが、前記メモリ・テーブル・ルックアップ・オペレーションのシーケンスにおいて使用されることを特徴とする、請求項１に記載の方法。
【請求項３】
前記メモリ・アドレスのシーケンスを適用する前記ステップが、前記メモリ・アドレスのシーケンスを、前記複数のメモリ・テーブルからなる、かつ少なくとも１つのメモリ・テーブルを各レベルで有する多数のレベルを有するメモリ・テーブルの構造に適用するステップを含み、前記メモリ・テーブル・ルックアップ・オペレーションのシーケンスのために使用された対応するメモリ・テーブルのシーケンスが、前記メモリ・テーブルの構造の少なくとも一部の前記複数のレベルを通じて進行することを特徴とする、請求項２に記載の方法。
【請求項４】
前記メモリ・テーブル・ルックアップ・オペレーションの前記結果に従って、前記入力が前記少なくとも１つの既知のパターン・セットのうち少なくとも１つのメンバへの合致である確率を反映する少なくとも１つの値を確かめるステップをさらに含み、複数のメモリ・テーブルにデータをロードする前記ステップが、前記入力が前記少なくとも１つの既知のパターン・セットのうち少なくとも１つのメンバへの合致である前記確率を反映する結果を提供するためのデータのロードを含むことを特徴とする、請求項３に記載の方法。
【請求項５】
少なくとも１つのメンバ・パターンを有する前記少なくとも１つの既知のパターン・セットが、単一のパターンを含むことを特徴とする、請求項３に記載の方法。
【請求項６】
少なくとも１つのメンバ・パターンを有する前記少なくとも１つの既知のパターン・セットが多数のパターンを含み、前記メモリ・アドレスのシーケンスを適用する前記ステップが、前記メモリ・テーブルのシーケンスを含む前記特定のメモリ・テーブルを、少なくとも部分的には前記メモリ・アドレスの前記値から、前記テーブル・ルックアップ・オペレーションの前記結果によって選択することを含むことを特徴とする、請求項３に記載の方法。
【請求項７】
前記テーブル・ルックアップ・オペレーションの前記結果に従って、前記入力が前記少なくとも１つの既知のパターン・セットのいずれかのメンバ・パターンへの推定合致であるとして認識される場合についての前記入力への推定合致である、前記少なくとも１つの既知のパターン・セットのうち少なくとも１つの特定のメンバを識別するステップをさらに含む、請求項６に記載の方法。
【請求項８】
前記メモリ・テーブル・ルックアップ・オペレーションの前記結果に従って、前記入力が前記少なくとも１つの既知のパターン・セットのうち少なくとも１つのメンバへの合致である確率を反映する少なくとも１つの値を確かめるステップをさらに含み、複数のメモリ・テーブルにデータをロードする前記ステップが、前記入力が前記少なくとも１つの既知のパターン・セットのうち少なくとも１つのメンバへの合致である前記確率を反映する結果を提供するためのデータの前記ロードを含むことを特徴とする、請求項７に記載の方法。
【請求項９】
パターン認識装置であって、
メモリ・アドレスのシーケンスを生成するための変換システムであって、前記メモリ・アドレスは、少なくとも１つのメンバ・パターンを含む少なくとも１つの既知のパターン・セットに比較されるべきである入力を反映する値を含むことを特徴とする、変換システムと、
少なくとも１つの物理記憶装置内に存在する複数のメモリ・テーブルと、
前記メモリ・アドレスのシーケンスを、前記複数のメモリ・テーブルからの対応するメモリ・テーブルのシーケンスのアドレス入力に適用して、結果を生じるためにメモリ・テーブル・ルックアップ・オペレーションのシーケンスを実行するためのアドレス指定回路と、
前記メモリ・テーブル・ルックアップ・オペレーションのシーケンスからの前記結果に従って、前記入力が前記少なくとも１つの既知のパターン・セットのいずれかのメンバ・パターンへの推定合致であるとして認識されるかどうかを決定するための出力回路と、
を含む装置。
【請求項１０】
少なくとも１つのセットのデータ値が前記複数のメモリ・テーブルに格納され、前記少なくとも１つのセットのデータ値が、前記少なくとも１つの既知のパターン・セットのいずれかのメンバ・パターンへの推定合致である前記入力についての、予想されたメモリ・アドレス値のシーケンスを反映することを特徴とする、請求項９に記載の装置。
【請求項１１】
前記複数のメモリ・テーブルは、多数のレベルを有するメモリ・テーブルの構造を含み、前記複数のメモリ・テーブルのうち少なくとも１つを前記多数の各レベルで有し、前記メモリ・テーブルのシーケンスが、前記メモリ・テーブルの構造の少なくとも一部の前記複数のレベルを通じて進行することを特徴とする、請求項１０に記載の装置。
【請求項１２】
データを前記複数のメモリ・テーブルに格納するための格納回路をさらに含み、前記データが前記少なくとも１つのセットのデータ値を含むことを特徴とする、請求項１１に記載の装置。
【請求項１３】
前記少なくとも１つのセットのデータ値のうち少なくとも１つが、前記変換システムによって、少なくとも１つの既知のパターン・セットに合致する入力から生成される前記メモリ・アドレス値のシーケンスから導出されることを特徴とする、請求項１１に記載の装置。
【請求項１４】
前記メモリ・テーブル・ルックアップ・オペレーションのシーケンスからの前記結果がさらに、前記入力が前記少なくとも１つの既知のパターン・セットのうち少なくとも１つのメンバへの合致である確率を定量化する少なくとも１つの出力値を含むことを特徴とする、請求項１１に記載の装置。
【請求項１５】
メモリ・テーブル・ルックアップ・オペレーションを、前記メモリ・テーブルの構造の前記各多数のレベルで同時に実行するためのルックアップ回路と、
前記メモリ・アドレスのシーケンスを進めるための少なくとも１つのコントロール・クロック信号と、
前記少なくとも１つのコントロール・クロック信号に応答して、新しいテーブル・ルックアップ・オペレーションのシーケンスを開始するためのシーケンシング回路であって、前記メモリ・アドレスのシーケンスにおける各位置が、前記メモリ・アドレスのシーケンスを前記少なくとも１つの既知のパターン・セットと比較するための、可能な開始位置として使用されることを特徴とする、請求項１１に記載の装置。
【請求項１６】
前記パターン認識装置が少なくとも１つの集積回路を含むことを特徴とする、請求項１１に記載の装置。
【請求項１７】
少なくとも１つのメンバ・パターンを有する前記少なくとも１つの既知のパターン・セットが、単一のパターンを含むことを特徴とする、請求項１１に記載の装置。
【請求項１８】
少なくとも１つのメンバ・パターンを含む前記少なくとも１つの既知のパターン・セットが多数のパターンを含み、前記メモリ・テーブル・ルックアップ・オペレーションのシーケンスからの前記結果が、前記メモリ・アドレスの前記値を反映し、これが、前記メモリ・テーブルのシーケンスを含む特定のメモリ・テーブルの決定において使用されることを特徴とする、請求項１１に記載の装置。
【請求項１９】
前記入力が認識された場合、前記入力への推定合致である、前記少なくとも１つの既知のパターン・セットのうち少なくとも１つの特定のメンバが、前記メモリ・テーブル・ルックアップ・オペレーションの前記結果によって識別されることを特徴とする、請求項１８に記載の装置。
【請求項２０】
メモリ・アドレスのシーケンスを生成するための前記変換システムがさらに翻訳システムを含むことを特徴とする、請求項１９に記載の装置。
【請求項２１】
メモリ・アドレスのシーケンスを生成するための前記変換システムがさらにスケーリング・システムを含むことを特徴とする、請求項１９に記載の装置。
【請求項２２】
メモリ・アドレスのシーケンスを生成するための前記変換システムがさらにベクトル回転システムを含むことを特徴とする、請求項１９に記載の装置。
【請求項２３】
メモリ・アドレスのシーケンスを生成するための前記変換システムがさらに、少なくとも１つの離散高速フーリエ変換を含むことを特徴とする、請求項１９に記載の装置。
【請求項２４】
データを前記複数のメモリ・テーブルに格納するための格納回路をさらに含み、前記データが前記少なくとも１つのセットのデータ値を含むことを特徴とする、請求項１９に記載の装置。
【請求項２５】
前記少なくとも１つのセットのデータ値のうち少なくとも１つが、前記変換システムによって、少なくとも１つの既知のパターン・セットに合致する入力から生成される前記メモリ・アドレス値のシーケンスから導出されることを特徴とする、請求項１９に記載の装置。
【請求項２６】
前記メモリ・テーブル・ルックアップ・オペレーションのシーケンスからの前記結果が、さらに、前記入力が前記少なくとも１つの既知のパターン・セットのうち少なくとも１つのメンバへの合致である確率を定量化する少なくとも１つの出力値を含むことを特徴とする、請求項１９に記載の装置。
【請求項２７】
メモリ・テーブル・ルックアップ・オペレーションを、前記メモリ・テーブルの構造の前記各多数のレベルで同時に実行するためのルックアップ回路と、
前記メモリ・アドレスのシーケンスを進めるための少なくとも１つのコントロール・クロック信号と、
前記少なくとも１つのコントロール・クロック信号に応答して、新しいテーブル・ルックアップ・オペレーションのシーケンスを開始するためのシーケンシング回路であって、前記メモリ・アドレスのシーケンスにおける各位置が、前記メモリ・アドレスのシーケンスを前記少なくとも１つの既知のパターン・セットと比較するための、開始位置として使用されることを特徴とする、シーケンス回路と、
を含む、請求項１９に記載の装置。
【請求項２８】
前記パターン認識装置が少なくとも１つの集積回路を含むことを特徴とする、請求項１９に記載の装置。
【請求項２９】
表示システム装置であって、
少なくとも１つの表示ピクセルの２次元アレイを含む表示デバイスと、
特定の表示イメージを反映するピクセル値を格納する、少なくとも１つの２次元イメージ・メモリと、
前記表示デバイスを、前記少なくとも１つの２次元イメージ・メモリに格納された前記ピクセル値からリフレッシュする回路と、
少なくとも１つの入力信号からなる信号入力セットであって、前記信号入力セットのための入力値の経時的な変化が、前記表示デバイス上に表示するためのシンボルを反映することを特徴とする、信号入力セットと、
前記信号入力セットからの第１のシンボル・セットの前記シンボルを認識し、さらに前記第１のシンボル・セットの認識されたシンボルを識別する出力を含む、パターン認識装置と、
第２のシンボル・セットの前記シンボルのうちいずれかを前記少なくとも１つの２次元イメージ・メモリに、独立してレンダリングするレンダリング回路と、
前記パターン認識装置からの前記出力に応答して、前記レンダリング回路による前記第２のシンボル・セットからの前記シンボルのレンダリングを命令する、インターフェイシング回路と、
を含む装置。
【請求項３０】
前記信号入力セットが、アナログＸ偏向入力、アナログＹ偏向入力、および少なくとも１つのビデオ入力信号を含むことを特徴とする、請求項２９に記載の装置。
【請求項３１】
前記アナログＸ偏向入力のタイムサンプリングされた値を、Ｘデジタル値のシーケンスに変換する第１の回路と、
前記アナログＹ偏向入力のタイムサンプリングされた値を、Ｙデジタル値のシーケンスに変換する第２の回路と、
前記少なくとも１つのビデオ入力信号および前記Ｘデジタル値のシーケンスおよび前記Ｙデジタル値のシーケンスを、アドレス値のシーケンスに変換し、前記アドレス値のシーケンスを入力として前記パターン認識装置に提供する、第３の回路と、
を含む、請求項３０に記載の装置。
【請求項３２】
前記信号入力セットがラスタ・ビデオを含むことを特徴とする、請求項２９に記載の装置。
【請求項３３】
前記第１のシンボル・セットおよび前記第２のシンボル・セットが同じであることを特徴とする、請求項３０に記載の装置。
【請求項３４】
前記信号入力セットの前記入力値の前記経時的な変化が、前記第１のシンボル・セットのシンボルであるとして認識されないシンボルを反映するとき、前記少なくとも１つのビデオ入力信号を反映するピクセル値を少なくとも１つの２次元イメージ・メモリに、前記アナログＸ偏向入力および前記アナログＹ偏向入力によって決定された位置で書き込む、直接格納手段をさらに含む、請求項３０に記載の装置。
【請求項３５】
前記パターン認識装置がさらに、
少なくとも１つの物理記憶装置内に存在する複数のメモリ・テーブルと、
前記アドレス値のシーケンスを、前記複数のメモリ・テーブルからの対応するメモリ・テーブルのシーケンスのアドレス入力に適用して、前記第１のシンボル・セットのうち認識されたシンボルを識別する前記出力を含む結果を生じるために、メモリ・テーブル・ルックアップ・オペレーションのシーケンスを実行するためのアドレス指定回路と、
をさらに含む、請求項３０に記載の装置。
【請求項３６】
データ値のセットが前記複数のメモリ・テーブルに格納され、前記データ値のセットが、前記信号入力セットについての前記入力値が前記第１のシンボル・セットのいずれかのシンボルへの推定合致である場合についての、前記予想されたアドレス値のシーケンスを反映することを特徴とする、請求項３５に記載の装置。
【請求項３７】
前記複数のメモリ・テーブルは、多数のレベルの構造に編成され、前記複数のメモリ・テーブルのうち少なくとも１つを前記多数の各レベルで有し、前記メモリ・テーブルのシーケンスが、前記構造の前記多数のレベルを通じて進行することを特徴とする、請求項３６に記載の装置。
【請求項３８】
少なくとも１つの表示ピクセルの２次元アレイを含む表示デバイスと、
特定の表示イメージを反映するピクセル・データを格納するための少なくとも１つの２次元アレイをそれぞれ含む、少なくとも３つのイメージ・メモリと、
前記表示デバイスを、前記少なくとも３つのイメージ・メモリのうち１つに格納された前記ピクセル・データからリフレッシュするためのリフレッシュ回路と、
前記少なくとも３つのイメージ・メモリのうち１つに格納された前記ピクセル・データをクリアするためのリセット回路と、
更新されたピクセル・データを前記少なくとも３つのイメージ・メモリのうち１つに書き込むための更新回路であって、前記更新されたピクセル・データは、更新された表示イメージを反映することを特徴とする、更新回路と、
前記少なくとも３つのイメージ・メモリの機能を周期的に交換するためのコントロール回路であって、直前に更新されたイメージ・メモリが使用されて前記表示デバイスがリフレッシュされ、前記表示デバイスをリフレッシュするために先に使用されたイメージ・メモリがクリアされ、更新されたピクセル・データが、クリアされるイメージ・メモリに書き込まれることを特徴とする、コントロール回路と、
を含む表示システム装置。
【発明の詳細な説明】
【０００１】
発明の背景
発明の分野
本発明は一般にパターン認識の分野に関する。より詳細には、本発明は、リアルタイム・アプリケーションにおいて使用可能なパターンまたはシンボル認識のためのシステム、方法および装置に関する。
背景技術
パターン認識には、いくつかのアプリケーションおよび手法がある。たとえば、ニューラル・ネットワークを、文字認識に使用することができる。しかし、ニューラル・ネットワーク用の大量のオフザシェルフ半導体デバイスは使用可能ではない。したがって、ニューラル・ネットワークを使用する実施は相対的に高価になる可能性があり、これらにより使用されるパーツが陳腐化するようになる可能性があるという固有のリスクが生じる。また、通常、ニューラル・ネットワーク・デバイスのコストを下げるために行われる折り合いのため、これらがいくつかのリアルタイム・アプリケーションのためのパフォーマンス要件を満たさない可能性もある。同様に、デジタル信号プロセッサ（ＤＳＰ）もパターン認識に使用することができる（たとえば、時間または周波数領域において実行された相関オペレーションによる）。しかし、ＤＳＰも高価になる可能性があり、いくつかのリアルタイム・アプリケーションによって必要とされるパフォーマンス・レベルを達成しない可能性がある。したがって、高パフォーマンスを相対的に低コストで、パーツが陳腐化する著しいリスクがなく達成することができる、パターン認識の代替手法を有することが有用となる。
【０００２】
多数の表示システムは陰極線管（ＣＲＴ）を使用するが、新しいＣＲＴは必ずしも、修理あるいはこれらの表示システムと置き換えることができるわけではない。したがって、これらのディスプレイを、新たに設計された表示システムで置き換えるための要求があり、これは液晶ディスプレイ（ＬＣＤ）技術など、フラットパネル表示技術を利用するものである。しかし、既存のＣＲＴベースのディスプレイへの電気的インターフェイスはしばしば、ＬＣＤベースのディスプレイの要件との互換性がなく、これは、これら２つの技術の間の違いのためである。これら２つの技術の主な非互換性は、各表示タイプの個々のピクセルが照度について選択される方法である。ＬＣＤ技術が、離散的に個々のピクセルを選択するためのメカニズムを使用するのに対して、ＣＲＴ技術はアナログ電圧信号を使用して１つまたは複数の電子ビームを表示面上で位置付ける。
【０００３】
エビオニクス表示など、リアルタイム・アプリケーションのための表示処理システムは一般に、ハードウェア・ベクトル生成（すなわち、線画）機能を組み込んでいる。このハードウェアは、Ｘ（水平）およびＹ（垂直）表示画面位置を選択するためのデジタル出力、および、選択された強度および／または色を指定するためのデジタルビデオを提供する。分離したビデオ・オン／オフ出力も提供することができる。カリグラフィック／ストローク・タイプのＣＲＴディスプレイでは、Ｘ、Ｙおよびビデオ信号がアナログに変換されて、ＣＲＴ電子ビームの位置および強度が直接コントロールされる。次いで、シンボル・ジェネレータ・ハードウェアが、そのコマンドを約６０ＨＺのレートで実行することによって、表示を直接リフレッシュする。動的な表示フォーマットでは、コマンド・ライン／プログラムが、シンボロジのスムーズな動きを達成するために十分高いレートで更新されるべきである。これには、２０または３０ＨＺの更新レートが必要となる可能性がある。
【０００４】
ＬＣＤ技術では、あるいはラスタ・タイプのＣＲＴベースのディスプレイでは、表示画面が２次元フレーム・バッファ・メモリ、すなわち「イメージ・メモリ」からリフレッシュされる。イメージ・メモリは、表示画面のピクセルの厳密な２Ｄマッピングにすることができ、これにより各メモリ位置が、その対応するピクセルの色／強度を決定するコードを保持する。次いで、シンボル・ジェネレータのデジタルＸおよびＹ出力が使用されて、２Ｄイメージ・メモリがアドレス指定される。ベクトルは、直接表示画面上ではなくイメージ・メモリに書き込まれ／描かれる。リアルタイム・アプリケーションでは、シンボル・ジェネレータが使用されて、あるイメージ・メモリにおける表示フォーマットが更新され、以前の更新を含む別のイメージ・メモリが同時に使用されて表示画面がリフレッシュされる。いくつかのＣＲＴベースのディスプレイは、ストロークとラスタの間でハイブリッド・モードにおいて交替するように設計され、これはストローク・シンボロジをラスタ・ビデオ上にオーバーレイするためである。
【０００５】
エビオニクス表示システムはしばしば、表示機能およびシンボル・ジェネレータ／プロセッサ機能のための、別々の物理ユニットを使用する。ストロークおよびハイブリッドＣＲＴディスプレイはアナログ・インターフェイスを、シンボル・ジェネレータと表示ユニットの間で利用することができる。このようなＣＲＴベースのディスプレイが新しいＬＣＤベースのユニットで置き換えられた場合、シンボル・ジェネレータを置き換えるためにもひどく高いコストがかかる可能性がある。次いで、新しいＬＣＤベースの表示ユニットを、既存のアナログ・インターフェイスにより機能するように設計するべきである。しかし、ＬＣＤ技術は離散的タイプのピクセル・アドレス指定メカニズムを使用するので、これは表示されたシンボロジの品質を落とす傾向がある。
【０００６】
ストローク・タイプのアナログ入力を有するＬＣＤベースの表示ユニットの設計のための従来の手法は、ＣＲＴベースのディスプレイのオペレーションを本質的に真似るか、あるいはシミュレートすることである。アナログのＸおよびＹ偏向入力がデジタルに変換され、これを使用して２Ｄイメージ・メモリがアドレス指定され、ここにデジタル／デジタル化されたビデオが書き込まれる。したがって、ストローク入力が使用されて、シンボロジが直接ＣＲＴ表示画面上ではなく、イメージ・メモリに書き込まれる。次いで、このイメージ・メモリが続いてスキャンされ、読み取られて、ＬＣＤ画面をリフレッシュするためのビデオが提供される。デジタル化入力が、あるイメージ・メモリに書き込むために使用されるが、第２のメモリ（以前の更新を格納するもの）が、表示をリフレッシュするために使用される。この設計手法では、アナログ・インターフェイスが、表示されたイメージへの誤り／異常に寄与する。これらは、１）アナログＸおよびＹ信号上で、外部および内部ソースから誘導された電磁干渉（ＥＭＩ）、２）アナログ回路内で生成された広帯域の熱雑音、３）サンプリング・オペレーションにおける位相雑音、および４）アナログ−デジタル（Ａ−Ｄ）変換からの量子化雑音の結果生じる。
【０００７】
これらのすべての雑音源は、表示されたシンボロジの品質を劣化させる傾向がある。ＥＭＩの重大度は、個々の応用例によって決まる。低域プレフィルタがサンプリングＡ−Ｄ変換オペレーションの前に使用されて、高周波ＥＭＩによる関心のある帯域幅へのエイリアシングが防止されることが好ましいが、より低周波のＥＭＩは、表示されたシンボロジの品質を劣化させる。熱雑音は、アナログ偏向入力のデジタル化されたサンプルにおいて、小さいランダムなずれを引き起こし、これはガウス分布をノルムの周囲に示す。熱雑音の影響は、入力をオーバーサンプリングし（すなわち、ダウンストリーム・オペレーションによって要求されるよりも高いレートでサンプリングする）、かつ次いで低域デジタル・フィルタを使用することによって、最小限にすることができる。位相雑音は、サンプリング時間におけるジッタの結果生じ、これはＡ−Ｄコンバータ回路内で、またサンプリング・クロックにおけるジッタからも生じる可能性がある。しかしこの応用例では、より著しい誤りが、シンボル・ジェネレータにおけるクロックと相対的に、サンプリング・クロックの一貫性のない位相から生じる可能性がある（すなわち、表示フォーマットの異なる更新における）。量子化雑音の結果生じる表示の異常は、高解像度のＡ−Ｄコンバータを使用することによって最小限にすることができる（たとえば、１２ビット・コンバータは、ディスプレイのピクセル解像度より著しく高い解像度を提供することができる）。
【０００８】
表示の異常を、静的または動的として類別することができる。あらゆる表示更新において同じである雑音またはひずみは、静的として類別される。その位置は、表示画面または表示画面上のシンボルに相対的に固定される（すなわち、シンボル自体が動いている可能性がある）。静的異常の一実施例は、個々のシンボルに対するひずみであり、これは偏向入力の攻撃的な低域フィルタリングの結果生じる（たとえば、ひどく丸みのある角を有するシンボルという結果となる）。動的異常は、画面全体で、かつ／またはシンボロジを通じて移動する雑音またはひずみである可能性がある。これも特定の画面または特定のシンボル位置に位置付けることができ、周期的あるいはランダムに示すことができる。人は動き／変化の検出に熟達しているので、動的異常は静的異常より好ましくない可能性がある。低域フィルタリングの量が増すと、ＥＭＩの結果生じる動的異常を低減することができる。しかしこれにより、シンボロジについての静的ひずみのレベルが増大する。
【０００９】
アナログ入力を有するＬＣＤベースのカリグラフィック表示のためのこの従来の設計手法では、好ましくない表示異常を生じる結果となるので、この問題を有していないある他の設計手法を使用することが有益となる。
発明の簡単な概要
以下の本発明の概要は、本発明に固有の革新的な特徴のいくつかを理解しやすくするために提供し、完全な記載となるように意図するものではない。本発明には多数の応用例があるが、この概要はカリグラフィック表示の応用例に焦点を置く。本発明の様々な態様の完全な理解は、明細書全体、特許請求の範囲、図面および要約書を全体として取り扱うことによって得ることができる。
【００１０】
本発明は、半導体記憶装置を使用して実施することができる、パターン認識ソリューションを提供する。メモリ・チップは、非常に低コストで入手可能である、非常に大量の商品パーツである。さらに、メモリ・チップの密度（すなわち、単一の集積回路におけるビット数）は、半導体技術における進歩により劇的に増大してきており、場合によってはこの増大が続くであろう。したがって、本発明は、非常に高レベルのパフォーマンスを相対的に低コストで達成する、パターン認識問題のソリューションを提供する。
【００１１】
本発明は、表示されたシンボロジの品質を向上させる、ＬＣＤベースのカリグラフィック表示ユニットの設計の代替手法を提供する。この代替手法では、アナログ偏向入力のデジタル化されたサンプルが、ビデオ入力と共に、表示されるべきである個々のシンボルを認識するために監視される。次いで、これらのシンボルを表示ユニット内で、完全にデジタル手段を使用して再生することができ、これにより、表示されたシンボロジにおける、アナログ・インターフェイスでの雑音および低域フィルタリングからのいかなる劣化も回避することができる。この手法は、表示ユニットへのアナログ偏向およびビデオ入力からの個々の表示シンボルの信頼性のある認識のためのメカニズムを、雑音がこれらの入力上に存在するときでさえ、必要とする。シンボル認識機能はリアルタイムで、表示ユニットへの入力により動作するので、本発明はソフトウェアを介してではなく、この応用例用のハードウェアを介して実施されることが好ましい。リアルタイム・パフォーマンスのための必要性でも、表示入力を同時のベースで、シンボル・ライブラリにおけるシンボルのいずれか１つについての予想された入力と比較するソリューションが必要であるようになる（すなわち、一度に１つのライブラリ・シンボルとの順次の比較ではない）。本発明は、このリアルタイム・アプリケーションの厳しい要件を満たすことができる、シンボル／パターン認識問題のための低コストのソリューションである。
【００１２】
本発明の一実施形態は、パターン認識機能を、テーブル・ルックアップ・オペレーションのシーケンスを使用するステート・マシンによって実施し、これらは入力のシーケンスにおけるパターンを認識するように設計される。認識されるパターン（すなわち、パターンのライブラリ）は、テーブル・ルックアップ・オペレーションによって使用されるメモリ・テーブルにおいて格納されたデータの導出において、使用される。テーブルは階層またはツリー状の構造において編成され、これはこの構造の各レベルについて一意のセットのメモリ・テーブルを有する。このパターン認識メカニズムへの入力は、メモリ・アドレスのタイムシーケンスを含み、これを、１つまたは複数のアナログ入力信号の、タイムサンプリングかつデジタル化された値から導出することができる。これは、アナログＸおよびＹ入力を有する、ＬＣＤベースのカリグラフィック表示ユニットの応用例の場合となる。他の応用例は、このメモリ・アドレスのシーケンスを異なる手段によって導出することができる。
【００１３】
ＬＣＤベースのカリグラフィック表示では、ＸおよびＹ入力値が通常、各表示シンボルのレンダリング前のある期間に渡って一定である（すなわち、雑音による小さい変化を除く）。これは、古いＣＲＴベースの表示ユニットによって、それらのアナログ偏向増幅器の安定化を可能にするために必要とされた。この状態を検出し、新しい表示シンボルがレンダリングされる前にシンボル認識メカニズムをリセットするために使用することができる。加えて、デジタル化されたＸおよびＹ入力を、この間隔中にフィルタリング／平均化することができる。これらのフィルタリング値は、保存され、レンダリングされるシンボルのための正確な表示画面位置を提供する。
【００１４】
デジタル化されたＸ、Ｙおよびビデオ入力サンプルのすべてが、シンボル認識メカニズムのためのメモリ・アドレスのタイムシーケンスの生成において使用される必要があるのではない。たとえば、これらのアドレスを生成するための１つのアルゴリズムは、ビデオ入力が状態を変更するすべての入力サンプル、および、ビデオ入力におけるこれらの変更の間の間隔において選択された数の入力サンプルを使用する。これらの各サンプルについて、次いで関連付けられたメモリ・アドレスを、１）サンプルの直前のビデオ状態を表す値、２）サンプリングされたＸ入力の相対的値、および３）サンプリングされたＹ入力の相対的値の連結によって導出することができる。シンボルのレンダリングの前に、ＸおよびＹ表示画面位置が保存されることを想起されたい。次いで、各Ｘ入力サンプルについての相対的Ｘ位置を、入力サンプルのＸ値から保存されたＸシンボル位置を差し引くことによって導出することができる。相対的Ｙ値を、類似の方法で導出することができる。したがって、次いで、選択された入力サンプルが、対応するメモリ・アドレスのタイムシーケンスを生成するために使用される。次いで、このメモリ・アドレスのシーケンスが、シンボル認識オペレーションへの入力として使用される。
【００１５】
シーケンスにおける第１のメモリ・アドレスが、メモリ・テーブルの階層における第１のレベルに存在する単一のメモリ・テーブルをアドレス指定するために使用される。このアドレスの値、およびよってそれが表すサンプルのための入力の値が、ライブラリにおける１つまたは複数のシンボルのレンダリングと無矛盾である場合、メモリ・テーブルのこのアドレスからの出力が、特定のレベル２テーブルをポイントし、これにより、無矛盾のシンボルの可能な認識が可能となる。次いで、シーケンスにおける次のメモリ・アドレスが、階層における第２のレベルでのこの指定されたテーブルをアドレス指定するために使用される。このプロセスが進行するにつれて、入力サンプルのシーケンスは、それらの関連付けられたメモリ・アドレスにより、メモリ・テーブルの構造を通じてパスを向け、これはシンボルが認識されるまで、あるいは、入力シーケンスがライブラリ・シンボルのいずれかと矛盾することが決定されるまで行われる。
【００１６】
３つのタイプの出力が、メモリ・テーブルについて可能である。完了された入力シーケンスが、曖昧でなく、ライブラリにおけるシンボルの１つに相関するものとして認識されたとき、そのシンボルのためのコードがメモリから出力される。不完全な入力シーケンスが、シーケンスにおけるそのポイントまで、１つまたは複数のライブラリ・シンボルに無矛盾であるとき、メモリ出力が、階層における次のレベルでの特定のテーブルをポイントし、これが入力シーケンスの次のサンプルをこの可能性に対してテストする。所与の入力サンプルが、入力シーケンスにおけるいずれかのポイントで、入力シーケンスがいずれかのライブラリ・シンボルに無矛盾でないことを確立したとき、メモリ・テーブルの出力がこの状態を指示する。入力シーケンスが、いずれかのライブラリ・シンボルと矛盾するように決定されたとき、デジタル化された入力サンプルを、シンボルをイメージ・メモリに直接レンダリングするために使用することができる（すなわち、シンボル再生メカニズムを効果的にバイパスする）。しかし、動的表示異常を生じる可能性をなくすため、シンボル認識メカニズムは、すべてのライブラリ・シンボルを（すなわち、雑音が入力上に存在するときでさえ）信頼性を有して、かつ無矛盾に認識する必要がある。これには、テーブルが、最悪の場合の雑音状態下で遭遇する可能性のある入力サンプルの値における変化を可能にするように、設計されることが必要である。
【００１７】
本発明の新しい特徴は、当業者には、以下の本発明の詳細な説明の考察において明らかになり、あるいは本発明の実施によって知ることができる。しかし、本発明の詳細な説明および提示した特定の実施例は、本発明のある実施形態を指示するが、例示のためにのみ提供されるものであり、これは、本発明の精神および範囲内の様々な変更および修正が、以下に続く本発明の詳細な説明および特許請求の範囲から、当業者に明らかになるからであることを理解されたい。
【００１８】
添付の図面では、類似の参照番号はいくつかの図を通じて等しいかあるいは機能的に類似の要素を指し、これらは本明細書に組み込まれ、その一部を形成し、さらに本発明を例示し、本発明の詳細な説明と共に、本発明の原理を説明するための機能を果たす。
発明の詳細な説明
本発明は、パターン認識のためのシステム、方法および装置を提供する。本発明をいくつかの応用例において使用することができるが、以下の詳細な説明は、アナログ偏向入力を有するＬＣＤベースのカリグラフィック（ｃａｌｉｇｒａｐｈｉｃ）表示ユニットに関する。アナログ偏向入力をビデオ入力と共に監視することによって、表示されるべきシンボロジを認識することができ、次いで表示ユニット内に、完全なデジタル手段によって再生することができる。これにより、アナログ入力での雑音および低域フィルタリングからのシンボロジにおける異常およびひずみがなくなる。本発明を、この特定の応用例における使用に関して記載するが、本発明を、パターンまたはシンボル認識を必要とする他の応用例における使用のために適合できることを理解されたい。
【００１９】
カリグラフィック表示の応用例では、デジタル化されたＸおよびＹ偏向値がビデオと共に使用されて、レンダリングされた各シンボル上のポイントのシーケンスが選択される。次いで、このポイントのシーケンスが、表示ユニットに格納されるライブラリにおけるすべてのシンボルについての予想されたポイントのシーケンスに対して比較される。入力シーケンスが、ライブラリにおけるこれらのシンボルの１つのレンダリングであるとして認識された場合、デジタル化された入力サンプルのストリームを廃棄することができ、シンボルを、表示ユニット内に格納されたベクトルのリストからレンダリングすることができる。入力シーケンスが、内部に格納されたライブラリにおけるシンボルの１つであるとして認識されなかった場合、シンボルを直接イメージ・メモリに、デジタル化された入力サンプルからレンダリングすることができる。これには、デジタル化された入力サンプル（偏向およびビデオ）がＦＩＦＯバッファに保存されることが必要であり、これはシンボル認識オペレーションのための時間を考慮するためである。シンボル・ライブラリにあるものとして認識されるシンボルは、表示ユニット内でデジタル・ハードウェアにより完全に再レンダリングされる。したがって、これらの表示されたシンボルの品質は、アナログ・インターフェイスでの雑音によって、あるいは低域フィルタリングによって劣化されない。
【００２０】
図１は、カリグラフィック表示の応用例のための本発明の一実施形態を示す。この表示ユニットは、フラットパネルＬＣＤ３４４を組み込むが、水平および垂直表示画面位置を選択するためにアナログ偏向入力を使用するＣＲＴベースの表示ユニットに置き換えられるように設計される。水平またはＸ偏向の入力信号２１８から高周波雑音が、直列レジスタ３０２および並列キャパシタ３０４からなる低域フィルタによって除去される。直列レジスタ３０６および並列キャパシタ３０８を有する類似の低域フィルタは、垂直またはＹ偏向の入力信号２１６上の高周波雑音を除去する。フィルタリングされた入力がサンプリングされ、周期的に偏向インターフェイス３１０でデジタル値に変換される。高サンプリング・レート（すなわち、オーバーサンプリング）が使用され、次いでサンプリングされた値のストリームが低域デジタル・フィルタ３１２によって処理される。ビデオ入力２２０は多数の信号からなることができ、アナログ、デジタル、またはアナログおよびデジタルの混合にすることができる。ビデオ・インターフェイス３１６が、ビデオ入力２２０の「オフからオン」および「オンからオフ」への移行を検出する。これらの移行が使用されて、表示ユニット内の様々なオペレーションが同期化かつコントロールされる。ビデオ・インターフェイス３１６はまた、ビデオおよび偏向入力のタイミングにおけるいかなる格差も補償する。このような格差は、ＣＲＴベースのディスプレイに合わせて設計されたインターフェイスについて存在する可能性がある。ＣＲＴベースのディスプレイの偏向増幅器のための帯域幅は通常、ビデオ回路の帯域幅よりはるかに低い。したがって、表示画面で偏向を同期化させるために入力でのビデオの、ＣＲＴベースのディスプレイへの移行はしばしば遅延される。この場合、ビデオ・インターフェイス３１６がビデオ・タイミングを調節して、効果的にこの補償を除去する。
【００２１】
ストローク・タイプのＣＲＴベースのディスプレイの場合のように、シンボロジを直接表示画面上に書き込むのではなく、図１に示すディスプレイは、シンボロジをイメージ・メモリ３３６に書き込む。イメージ・メモリは２次元アレイとして編成され、これがしばしば１対１毎に、表示画面上のピクセルのアレイに対応する。したがって、イメージ・メモリへの入力アドレスは、水平またはＸの値および垂直またはＹの値からなる。いくつかの実現において、次いで、メモリにおける各位置が、表示画面の単一の対応するピクセルについてのビデオ情報を格納する。このビデオ情報は、ピクセル強度およびピクセル色を含むことができる。３つのイメージ・メモリ３３６、３３８、３４０の合計が使用される。シンボロジがイメージ・メモリのうちの１つ３３６に書き込まれている間、ＬＣＤ３４４が、先の表示リフレッシュ・サイクル上で書き込まれたシンボロジを保持する別のイメージ・メモリ３４０におけるビデオ・データによってリフレッシュされる。第３のイメージ・メモリ３３８から同時にシンボロジをクリアして、次のリフレッシュ・サイクル上で更新されたシンボロジを書き込むためにこれを使用できるようにすることができる。次いで、イメージ・メモリの機能が、各表示リフレッシュ・サイクルの最初に、循環ベースで交換される。
【００２２】
表示システムは従来２つのイメージ・メモリしか使用しておらず、それによりいかなる所与の時点でも、第２のイメージ・メモリが新しいシンボロジにより更新されている間に、一方のイメージ・メモリが表示のリフレッシュに使用される。更新オペレーションが完了した後、これらの２つのイメージ・メモリの機能が交換される。いくつかのシステムは、すべてではないが、この交換を表示リフレッシュ・オペレーションの完了に同期化させる。交換の後に続いて、更新オペレーションが最初にイメージ・メモリから、先に更新されたシンボロジ／イメージをクリアし、次いで、新しいシンボロジをイメージ・メモリに書き込む。このクリア・オペレーションが、書き込みオペレーションに続いて順次に実行される（すなわち、同時ではない）ので、これによりシステム・パフォーマンスが制限される。最低待ち時間（すなわち、更新されたシンボロジを表示するための時間遅延）および最大更新レートが、これら２つのオペレーションを順次に実行する要件によって制約される。
【００２３】
３つのイメージ・メモリを使用することによって、３つのイメージメモリ・オペレーション（すなわち、表示のリフレッシュ、イメージ・メモリから先のシンボロジをクリアすること、および新しいシンボロジを書き込むこと）をすべて同時に実行することができる。これにより、表示システムが、より低い待ち時間およびより高い更新レートを達成することができる。３つのイメージ・メモリを利用してパフォーマンスを向上させるこの技術は、ＬＣＤベースのカリグラフィック表示の応用例に限定されず、これを、コンピュータによりイメージ・メモリから生成されたシンボロジ／グラフィックスを有するディスプレイをリフレッシュするいかなる表示システムにおいても、使用できることを理解されたい。本発明のこの特徴は、このようなすべての表示システムの応用例を包含することを意図する。
【００２４】
図１の表示システムでは、２つの異なるメカニズムが、シンボロジをイメージ・メモリに書き込むために使用される。これらのうち１つにおいて、アドレス値をイメージ・メモリ３３６に供給するためにサンプリングかつデジタル化されたＸおよびＹ入力値がＦＩＦＯパイプライン３２８およびセレクタ３２４を通過するようにされる。ビデオ・データ入力をイメージ・メモリ３３６に供給するためにサンプリングされたビデオ入力がＦＩＦＯパイプライン・バッファ３２６およびセレクタ３３０を通過するようにされる。ビデオ・データ入力がオンである（すなわち、オフ／ブランク状態でない）とき、これがイメージ・メモリ３３６へ、選択されたＸ／Ｙ位置で書き込まれる。この手法は、ＣＲＴベースのディスプレイのオペレーションをエミュレートするが、シンボロジは表示画面上に直接ではなく、イメージ・メモリに書き込まれる。しかし、表示されたシンボロジの品質は、アナログ偏向入力２１８および２１６上の雑音の結果として、この手法により損なわれる可能性がある。
【００２５】
シンボロジをイメージ・メモリに書き込むための第２のメカニズムにより、アナログ入力上の雑音の結果生じる表示品質の劣化がなくなる。イメージ・メモリに直接書き込むのではなく、サンプリングされた入力のデータ・ストリームが監視されて、表示されるべき特定のシンボルが検出される。次いで、検出されたシンボルが、表示ユニット内のデジタル手段によって再生される。したがって、これらが、アナログ・インターフェイスの結果生じる可能性のある異常なしに、レンダリングされる。
【００２６】
デジタル化されたＸおよびＹ値のストリーム、および対応するビデオ・データのストリームが最初にポイント選択メカニズム３１４に入力される。データ・ストリームにおけるあらゆるサンプル（すなわち、シンボル上のあらゆるポイント）が、シンボルを識別するために処理される必要はない。したがって、ポイント選択メカニズム３１４が使用されて、シンボル検出メカニズム３１８へ入力されるデータの量が低減される。ポイント選択アルゴリズムが、データ・ストリームにおいて、ビデオにおける移行が起こる（たとえば、ビデオがオフからオンへ、あるいはオンからオフへ切り替わる）サンプル／ポイントのすべてを選択する。相対的に長い間隔がビデオ移行の間に生じるとき、追加のポイントが選択される（たとえば、アルゴリズムが、ビデオ移行の間の間隔中にデータ・ストリームにおける４サンプル／ポイント毎に選択することができる）。選択されるポイントの数を十分高くして、シンボル・ライブラリにおけるすべてのシンボルの曖昧な検出が保証されるようにするべきである。
【００２７】
特定のライブラリ・シンボルが検出されるとき、ベクトル生成メカニズム３２０が使用されて、シンボルが、内部に格納されたライブラリにおける情報から再生される。これはベクトル・コマンドのシーケンスをレンダ・メカニズム３２２に出力する。次いで、レンダ・メカニズム３２２がこれらの各ベクトルをイメージ・メモリ３３６にレンダリングする。これはＸ／Ｙアドレスのシーケンスを、セレクタ３２４を介して、イメージ・メモリ３３６のアドレス入力に出力し、これはビデオ・データを、セレクタ３３０を介して、イメージ・メモリ３３６のデータ入力に出力する。ビデオ・データがイメージ・メモリへ、アドレス指定された各位置で、ベクトルのパスに沿って書き込まれる。所与のシンボルを生成するためのベクトル・コマンドが、ベクトルのエンドポイントの位置を表示上のシンボルの位置に相対的に指定する。各ベクトルのパスに沿ったポイントも、最初に相対的な位置として生成される。したがって、イメージ・メモリへの絶対的なＸおよびＹアドレスを生成するためにレンダリング・メカニズムがシンボルの画面位置をこれらの相対的な値に追加する。
【００２８】
表示されるべきシンボルが、ライブラリにおけるシンボルのうち１つであるとして認識されなかったとき、Ｘ、Ｙのデータ・ストリーム、およびビデオ・サンプルが使用されて、シンボルが直接イメージ・メモリ３３６へ、ＦＩＦＯパイプライン・バッファ３２６および３２８を介してレンダリングされる。ＦＩＦＯバッファ３２６および３２８は、シンボルを識別するか、あるいはシンボルがライブラリにないことを決定するために必要とされる間隔中に、データ・サンプルのストリームを保存するために必要とされる。
【００２９】
図１のブロック図に明示的に示さないが、ＬＣＤ技術に基づいたディスプレイは一般に、エイリアス除去機能の実施を必要とする。表示されたイメージは実際には、所望のイメージの空間的にサンプリングされた表現であり、表示されたイメージの品質は、シンボロジの空間解像度／周波数とディスプレイのピクセル解像度（すなわち、空間サンプリング周波数）の間のエイリアシング効果によって劣化される可能性がある。エイリアシングはストロークＣＲＴディスプレイでは問題ではなく、これは、ピクセル・アドレス指定のアナログ偏向メカニズムに固有である低域空間フィルタリングのためである。しかし、ＬＣＤベースのディスプレイは一般にエイリアス除去回路を組み込み、これは高品質のイメージを提供するためである。このために、ＸおよびＹ入力値のアナログ−デジタル変換は、ＬＣＤ画面のピクセル解像度よりも高い解像度を使用する。したがって、図１に示したデジタル・フィルタ３１２からの各ＸおよびＹ値は、整数および小数ビットを有する。これらの値の整数部が、イメージ・メモリ３３６をアドレス指定するために使用され、少数ビットは、エイリアシング除去のために使用されるサブピクセル・アドレス指定情報を表す。エイリアシング除去のための１つの手法は、ＸおよびＹサブピクセル／小数アドレス指定情報をイメージ・メモリ３３６に、ビデオ・データと共に書き込むことである。次いで、エイリアシング除去アルゴリズムを表示のリフレッシュのために生成されたビデオ上で実施するために、イメージ・メモリがスキャン／読み取られるとき、この情報を処理することができる。第２の手法は、エイリアシング除去機能を、イメージ・メモリの入力側で実施することである。この手法には、イメージ・メモリ３３６における追加の位置への書き込みオペレーションが必要である。整数ＸおよびＹの値によってトレースされるものに隣接あるいは近い位置に、より低い強度のビデオが書き込まれる。
【００３０】
図１に示す本発明の実施形態が、本発明を記載するための手段でしかなく、これは本発明のこの特定の応用例の単一の実施例のみを表すことを理解されたい。いくつかの設計は、たとえば、検出されたシンボルの再レンダリングにおける弧ならびにベクトルのための能力を含むことができる。また、いくつかの表示ユニットは、コンピュータにより生成されたシンボロジをカメラ・ビデオ上でオーバーレイできるように設計される。
【００３１】
図１に示す本発明の実施形態により、シンボルを、非常に高い品質を有する、内部で格納されたライブラリからレンダリングすることができる。しかし、表示画面上のこれらのシンボルの位置が、多数の表示の更新に渡って安定することが等しく重要である。不安定なシンボル位置では、動的な表示異常が生じる。幸いにも、ストローク表示のオペレーションは、正確にシンボル位置を決定することができる空間フィルタリング・オペレーションの実施と互換性がある。シンボル・ジェネレータがＸおよびＹ偏向を新しいシンボルの初期／開始の位置に再位置付けするとき、これはシンボルのレンダリング前に休止し、ＣＲＴベースのストローク表示ユニットの偏向増幅器が応答して正しい出力電圧を安定させるために十分な時間を有するようにする。この安定したＸおよびＹ入力値の時間間隔（すなわち、雑音レベル内の安定）を検出することができ、入力サンプルをこの期間中にフィルタリングして、多数の更新に渡って安定するＸおよびＹ位置の値を提供することができる。いくつかのストローク表示システムでは、英数字シンボルのストリングを単一の休止のみ（すなわち、ストリングにおける最初のシンボルの前のみの休止）によりレンダリングすることができる。この場合、表示ユニットを、追加のシンボルをストリングにおける第１のシンボルの位置に相対的に位置付けるように設計することができ、それにより、ストリングにおけるすべてのシンボルについて安定した画面位置を提供する。シンボルのレンダリング前のこの安定したＸおよびＹ偏向入力の期間の検出を使用して、シンボル認識メカニズムをリセットすることもでき、これはステート・マシンとして動作する。
【００３２】
動的異常の発生をなくすために、シンボル認識メカニズムが、最悪の場合の雑音状態下で、ライブラリにおけるいかなるシンボルも無矛盾に認識するべきである。加えて、これはいくつかの他の入力シーケンスを、ライブラリにおけるシンボルの１つと間違えるべきではない。すなわち、いかなる入力シーケンス（ライブラリ・シンボルまたは非ライブラリ・シンボル）も、最悪の場合の雑音状態下でさえ、ライブラリにおけるシンボルの１つの検出／認識のためのしきい値レベルに到達するべきではない。シンボル認識機能はリアルタイムで、デジタル化された入力サンプルのストリームにより動作することが必要とされるので、この機能をソフトウェアではなくハードウェアで実施することが必要である可能性がある。リアルタイム・パフォーマンスの必要性でも、入力ポイントのシーケンスを、同時のベースで、ライブラリにおけるすべてのシンボルについて予想されたシーケンスと比較する（すなわち、一度に１つのライブラリ・シンボルとの順次の比較ではない）ソリューションを必要とするようである。本発明は、上のすべての要件と互換性のあるパターン認識の方法である。
【００３３】
パターン／シンボル認識メカニズムを、英数字シンボル「Ｎ」を検出するためのプロセスを示す一実施例によって説明する。このプロセスの最初のステップは、入力データ・ストリームから、レンダリングされているシンボル上の選択されたポイントに対応するサンプルを選択することである。これらが使用されて、シンボル認識メカニズムへの入力として使用されるメモリ・アドレスのシーケンスが生成される。図２は、２つの英数字シンボルの、各シンボルの標準の向きについて、かつ各シンボルの回転された向きについてのレンダリングを示す。図２Ａは、標準の正しい向きにおけるシンボル「Ｎ」４００のレンダリングを示し、図２Ｂは、標準の正しい向きにおけるシンボル「Ｌ」４２０のレンダリングを示す。図２はまた、２つの座標系の重ね合わせも示す。直交座標系は、水平軸Ｘおよび垂直軸Ｙによって示される。半径座標ｒおよび角座標θは、重ねあわされた極座標系を示す。
【００３４】
図２Ａの記号「Ｎ」４００は５つのベクトルによって描画され、また図２Ａ中の参照符号は、これらベクトルの終点を示している。記号「Ｎ」４００が描画される前、図２Ａの点４０２におけるディスプレイへのＸおよびＹの偏向の入力は、ノイズを除いては安定している。先に言及したように、この安定した状態は、フィルタリング後の点４０２のＸおよびＹの値を得るために検出する。記号の認識機構もリセットされる。この場合には点４０２である、記号を描画する際の初期／開始点が記号の位置を定義する。この点は、記号を回転させて描画する際には回転の中心としても使用される。
【００３５】
記号「Ｎ」４００は、まず図２Ａの点４０２から点４０４に空のベクトルを描画することによって描画される。「空のベクトル」はビデオをオフ状態にして描く。このベクトルは、ビデオがオフであることを表すために図２Ａでは点線で示す。ビデオをオンに切り替える３つの連続したベクトルが、この最初の空のベクトルの後に続く。ベクトルは、点４０４から点４０６に、点４０６から点４０８に、そして点４０８から点４１０へと描画される。最後に、もう１つの空のベクトルを点４１０から点４１２に描画する。この後者のベクトルは、英数文字ストリングの描画との互換性のために含まれ、これは、ストリングの次の記号の位置への偏向の位置を決定する。図２Ｂは、記号「Ｌ」４２０の描画を示している。この記号は点４２２に位置し、まず点４２２から点４２４に空のベクトルを描画することによって描画される。これに続き、ビデオがオンの状態で２つのベクトルを描画する。点４２４から点４２６に描画されたベクトルの後に、点４２６から点４２８へのベクトルが続く。この後に点４２８から４３０への空のベクトルが続き、これはストリング中の次の記号への偏向の位置を決定する。
【００３６】
記号認識機能への入力を生成するために、描画された記号上の点を選択するのには、様々なアルゴリズムを用いることができる。効果的な技術は、まずビデオ遷移が起こる（すなわち、オフからオンへの遷移、またはオンからオフへの遷移）入力ストリームですべてのサンプルを選択することである。この結果、図２Ａの描画された「Ｎ」４００の点４０４と４１０が選択されることになる。記号の描画後に中断が発生した場合は、サンプリングしたＸおよびＹの偏向のこの安定した期間の検出を使用して、記号の終点（すなわち図２Ａの点４１２）を選択することができる。次いで、最初に選択したこれらの点の間に追加の点を選択する。単純で効果的なアルゴリズムは、周期的に追加の点を選択するものである。例えば、ビデオ遷移に続いて４つごとにサンプルを選択することができる。しかし、別のアルゴリズムが可能である。１つの可能性は、連続したベクトル間の頂点を選択するものである。この結果、図２Ａの点４０６と点４０８が選択される。頂点の選択と周期的な点の選択の組み合わせを使用するアルゴリズムも考案することができる。
【００３７】
図２Ａのベクトル間の頂点は、サンプリングしたＸおよびＹの入力値の変化を時間にわたって監視することによって（すなわち、ΔＸ／ΔｔとΔＹ／Δｔの値を監視することによって）検出することができる。これらの値は基本的に、ノイズと、アナログ−デジタル変換の際の制限された解像度を除いては、所与のベクトルを描画する間一定である。しかし、これらの「速度値」は、描画されたベクトルの方向を反映する。これらの値の１つまたは両方の変化を使用して、２つのベクトル間の頂点／隅の位置を検出することができ、したがって描画した記号上の追加点を選択することができる。
【００３８】
記号「Ｎ」４００の各頂点は、実質的に異なる方向を有するベクトルの対によって形成される。これにより、これら頂点の検出が容易になる。ほぼ同じ方向を有する２つのベクトルの頂点の検出はこれに比べると難しく、同じ記号の複数の描画における点の選択の整合性が低くなりかねない。特にノイズがある場合にはこのことが当てはまる。したがって、本発明の実際的な実装では、周期的な追加点の選択の手法が好ましいと思われる。ただし、平易さを考えて、この例では頂点選択のアルゴリズムを使用する。このアルゴリズムを用いると、図２Ａの描画された「Ｎ」４００で、点４０４、４０６、４０８、４１０、および４１２が選択されることになる。
【００３９】
記号認識プロセスの次のステップは、メモリ・アドレスのシーケンスを生成することである。選択されたそれぞれの点から、単一のメモリ・アドレスを得る。次いで記号認識プロセスは、一連のテーブル・ルックアップ・オペレーションのために、このアドレス入力のシーケンスを使用する。この動作のためのメモリ・テーブルは階層状のレベルに構成され、この構造の各レベルには１つまたは複数のテーブルがあり、また入力シーケンスの各メモリ・アドレスに対して別個のレベルがある。入力シーケンスの最初のアドレスは、この構造の第１レベルにあるメモリ・テーブルのアドレス指定に使用される。描画された記号で最初に選択される点の位置がライブラリの１つまたは複数の記号と整合する場合、アドレス指定されたメモリ・テーブルの出力は、この可能性を見込んだ構造のレベル２にある特定のテーブルをポイントすることになる。次いで、入力シーケンスの２番目のアドレスを使用して、構造のレベル２にあるこの指定されたテーブルをアドレス指定する。このプロセスは、メモリ・テーブルの階層中の経路を指示する、対応するメモリ・アドレスを使用して、描画された記号で選択される点とともに進行する。
【００４０】
メモリ・テーブルは、少なくとも３タイプの出力が可能である。点／アドレスのシーケンスが、ライブラリ中の１つまたは複数の記号と整合する限り、各メモリ・テーブルは、階層中の次のレベルにある特定のテーブルをポイントする「テーブル・アドレス」を出力する。そして、描画された記号上の対応する点をテストするために、入力シーケンス中の次のアドレスを使用してその指定されたテーブルをアドレス指定する。その点が、可能なライブラリ記号のどれとも整合性がない場合、メモリ・テーブルの出力は、描画された記号を認識できなかったことを知らせる。しかし、メモリ・アドレスの完全なシーケンスがライブラリ記号の１つと整合する場合、最後のメモリ・テーブルからの出力は、その描画記号のコードになる。その後、表示装置によって記号を再描画することができる。
【００４１】
描画された記号上で選択された各点について、それに対応するメモリ・アドレスは、その点の相対的なＸ値、その点の相対的なＹ値、および単一のビデオ・ビットからなる。図２Ａの記号「Ｎ」４００の場合、所与の点の相対的なＸ値は、その点のＸ値から点４０２のＸ値を減算することによって得る。所与の点の相対的Ｙ値は、その点のＹ値から、点４０２のＹ値を減算することによって得る。メモリ・アドレスの単一のビデオ・ビットは、所与の点をサンプリングする時間の前にビデオが「オン」（すなわち非ブランク状態）であるか否かを示す。描画された記号の完全なビデオ情報（すなわち、描画された記号の輝度および／または色）は、その記号を正確に再描画するのに必要であるが、記号を認識する際に必要なのはビデオの「オン−オフ」状態だけである。
【００４２】
図２Ａの記号「Ｎ」４００の記号認識プロセスを、図３に図解する。図３のアドレス５０２は、図２Ａの点４０４から得る。アドレス５０２は、点４０４の相対的なＸ位置ΔＸ１  ５０６と、相対的なＹ位置ΔＹ１  ５０８の両者、および単一のビデオ・ビットＶ５０４からなる。ビデオ・ビットＶ５０４の状態は、サンプリングされた点４０４の前にビデオがブランクであったことを表す。アドレス５０２は、記号認識プロセスの最初のテーブル・ルックアップ・オペレーションに使用される。このアドレスは、図３のメモリ・テーブル５１０からの出力を決定する。図３のメモリ・テーブルの構造の第１レベルは、この１つのメモリ・テーブル５１０からなる。この構造のレベル２は、テーブル５２０、５２２、５２４、５２６と、恐らくは、図３には明示していない追加のテーブルからなる。レベル３は、テーブル５３０、５３２、５３４、５３６、５３８と、恐らくは、明示していない追加のテーブルからなる。同様に、レベル４も、テーブル５４０、５４２、５４４、５４６、５４８、５４９と、恐らくは追加のテーブルからなる。レベル５は、テーブル５５０、５５２、５５４、５５６、５５８、５５９と、恐らくは追加のテーブルからなる。「Ｎ番目の」レベルと表せるこの構造の最後のレベルは、テーブル５６０、５６２、５６４と、恐らくは追加のテーブルからなる。このメモリ・テーブルの構造は、図３には明示していないが、レベル５と最後のレベルの間に存在するレベルをさらに含むことができる。
【００４３】
図２Ａの記号「Ｎ」４００の記号認識動作では、図２Ａの点４０４、４０６、４０８、４１０、および４１２から連続的に得られる５つのアドレスのシーケンスを用いる。これらのアドレスはそれぞれ、図３のメモリ構造の対応するレベルにおけるテーブル・ルックアップ・オペレーションで使用される。図３には、このシーケンスの最初のアドレス（すなわち点４０４から得たアドレス５０２）だけを明示している。（点４０２に相対的な）点４０４の位置と、点４０４の前のブランクのビデオ状態はどちらも、複数の可能な記号の描画との整合性がある。この可能な記号には、記号Ａ、Ｂ、Ｄ、Ｆ、Ｈ、Ｋ、Ｍ、Ｎ、Ｐ、Ｒ、およびＸがいずれも含まれる。したがって、メモリ・テーブル５１０は、入力されたアドレス５０２に応答して、これらの記号の可能性をすべて見込むように設計されたレベル２のテーブル５２０へのポインタ５７０を出力するように設計する。次いで、点４０６から得たシーケンス中の次のアドレスを、テーブル５２０によるテーブル・ルックアップ・オペレーションに使用する。点４０６の位置は、記号「Ａ」または「Ｘ」の描画との整合性はない。したがって、テーブル５２０の出力５７２はレベル３のテーブル５３６をポイントし、このテーブルは、点４０４および点４０６の両方となお整合性がある記号だけを見込むように設計されている。この時点で整合性のある記号には、記号Ｂ、Ｄ、Ｆ、Ｈ、Ｋ、Ｍ、Ｎ、ＰおよびＲが含まれる。次いで、点４０８から得たアドレスを、メモリ・テーブル５３６に対するテーブル・ルックアップ・オペレーションに使用する。しかし、点４０８は、記号Ｂ、Ｄ、Ｆ、Ｈ、Ｋ、Ｍ、Ｐ、およびＲのいずれの描画とも整合しない。記号「Ｎ」のみが可能性として残る。したがって、テーブル５３６の出力５７４はレベル４のテーブル５４４をポイントし、このテーブルはこの最後の可能性に照らして点４１０をテストするように設計されている。点４１０は、実際に記号「Ｎ」と整合性がある。したがって、点４１０から得たアドレスに応答して、テーブル５４４の出力５７６はレベル５のテーブル５５２をポイントし、このテーブルは、記号「Ｎ」との整合性について点４１２をテストするように設計されている。これが該当するので、テーブル５５２は記号「Ｎ」のコード５７８を出力して、その記号が認識されたことを示す。点４１２の位置が記号「Ｎ」４００の描画と整合しない場合、テーブル５５２は、描画された記号がライブラリにあるどの記号とも整合しないことを示すコードを出力する。
【００４４】
メモリ・テーブルの内容は、記号ライブラリにある記号をいずれも認識するように設計する。一部の応用例では、ライブラリの各記号についてのメモリ・アドレスのシーケンスは、メモリ・テーブル構造中で単一の固有の経路をたどることができる。しかし、これが常にあてはまるわけではない。次のような例を考えられたい。一部の特定の応用例では、描画された記号で選択されたある点の位置が、例えば記号「Ｓ１」と記号「Ｓ２」など、２つの異なるライブラリ記号と整合する可能性がある。ただし、その点が、おそらくはノイズが原因でわずかに異なる位置にある場合、その点は記号「Ｓ１」とは整合するが、記号「Ｓ２」とは整合しないことが考えられる。この場合は、構造の次のレベルが、記号「Ｓ１」の可能な認識を見込んだ２つのメモリ・テーブルを含んでいることになる。２つのテーブルの１つは、「Ｓ１」と「Ｓ２」の両方を見込み、もう一方のテーブルは「Ｓ１」だけを見込む。そしてこの応用例では、少なくとも２つのパスがメモリ・テーブルの構造中に存在し、その結果記号「Ｓ１」が認識される。
【００４５】
ここに記載するパターン認識の方法は、ニューラル・ネットワークの手法と似た部分がある。例えば、この２つの手法はどちらも、入力のシーケンスをライブラリにあるすべてのパターンと同時に比較する（すなわち、一度に１つのライブラリ・パターンと逐次比較するのに対して）。ただし、ハードウェアおよびソフトウェアどちらの実装においても、本発明は、より高レベルのパフォーマンスを達成することができる。ハードウェア実装の場合、本発明は一般に、ニューラル・ネットワークの手法に比べてコストの低い解決法を提供する。また、本発明では、標準的な市販のメモリ・デバイスを利用することができるので、ニューラル・ネットワークの手法に伴う、将来の部品の旧型化というリスクも回避される。ニューラル・ネットワークの手法と同様に、本発明は、基本的な設計を専用アプリケーションへと適合する学習法を取り入れることもできる。
【００４６】
本発明のメモリ・テーブル中のデータは、分析、シミュレーション、学習法、あるいはこれらの技術の組み合わせによって得ることができる。学習法の場合、データは、ライブラリ記号の実際の描画から集めることができる（例えば、図１のブロック図の点選択機能３１４の出力から）。このデータを、最終製品の実際の現実世界の環境で収集すると、その環境の実際のノイズ状態を反映するものになる。そして、コンピュータ・プログラムを使用した自動化プロセスでそれを分析し、描画された各記号で選択された点の名目値と、実際のノイズ環境におけるこれらの値の標準的な偏向の両方を求めることができる。テーブル・データの生成には、標準的な統計的方法を用いることができる。例えば、記号認識機能における特定エラーの確率についてこのデータを生成することができる。このテーブル・データを得る手法は、ニューラル・ネットワーク特有のあくまでも経験に基づく学習手法を上回る大きな利点を提供する。ニューラル・ネットワークの解決法では、ノイズ・マージンとエラーの確率は経験的にしか知ることができず、またその確度もはるかに低い。
【００４７】
本発明の特定の応用例で必要とされるメモリ量は、容易には求められない。例えば、所与の構造レベルに必要とされるメモリ・テーブルの数は応用例に依存するが、一般には、ライブラリ中の記号（またはパターン）の数とともに増加する。ここに記載する応用例では、メモリ構造中のレベルの数は、ライブラリにある任意の記号を描画するために選択される点／サンプルの最大数によって決まる。しかし、大半の記号では、選択される点の数はこの最大数よりも少ない。したがって、ライブラリ記号の大半は、構造のレベルをすべて利用することはない。描画された記号で選択する点の数は、あいまいでない記号認識を行うのに十分な数でなければならないが、追加の／冗長な点を選択するとメモリ・サイズが不必要に増大する。このような複雑性はあるものの、本発明の可能なメモリ要件を考察することはやはり有用である。
【００４８】
ライブラリが１２８個の記号を含み、描画された記号で最大３３個の点が選択される設計に必要なメモリを考えてみたい。このメモリ構造はしたがって、３３のレベルを含むことになり、最初のレベルは単一のテーブルからなる。残りの３２レベルについては、「平均的な」テーブル数の妥当な上限は６４、すなわち記号数の半分になると考えられる。多くの記号に類似性があることから、構造の最初の方のレベルが必要とするテーブルは比較的少ない。また、描画される記号の大半では、選択される点の数は最大の選択される点の数よりも少ないので、構造の最後の方のレベルも比較的少ないテーブルを有する。どのレベルでも、テーブルの数は一般に、ライブラリ記号の総数である１２８よりもやや少ない数になる。したがって、３２のレベルそれぞれにある平均６４個のテーブル（すなわち合計２０４８個のテーブル）が、実際のメモリ要件の上限を表すことができる。ΔＸ値およびΔＹ値それぞれを６ビットと想定し、単一のビデオ・ビットを考慮に入れると、１３ビットのアドレスが与えられ、このアドレスはメモリ・テーブル１つにつき８１９２ワードを必要とする。（ΔＸおよびΔＹを６ビットにすると、比較的大きな英数字記号に対応することができる。）
このメモリ・テーブルには、８ビット／１バイトの出力語で十分である可能性がある。この出力中の単一ビットで、残りの７ビットが７ビットの記号コードであることを表すことにより符号化された記号の認識を示すか、あるいは残りの７ビットが７ビットの「テーブルアドレスコード」であることを表すことができる。各レベルを最大で１２７個のテーブルに制限する場合は、次のレベルのテーブルの１つを選択するか、または描画された記号の認識の失敗を表すのには、７ビットのテーブルアドレスコードで十分である。（この全体的なメモリ・アドレス指定方式ではレベル番号も用いる。）この結果、合計１２８Ｍｂｉｔのメモリが必要になる（すなわち、３２レベル・６４のテーブル・８１９２ワード・８ビット＝１２８Ｍｂｉｔ）。現在の技術を用いると、このメモリは単一のＦＬＡＳＨタイプのメモリ・チップを用いて実装することができる。
【００４９】
応用例によっては、大きな全画面のシンボロジを表示することが必要となる。本発明を用いて小さな英数字記号だけを認識し、再描画した場合、大きな記号は再描画せずに直接画像メモリに書き込むことになる。しかし本発明は、全画面のシンボロジを認識するように適合することもできる。これを実用化する手法の１つは、メモリ・アドレスで使用されるΔＸ値およびΔＹ値をより低い解像度に合わせてスケーリングすることである。さもないと、メモリ・テーブルのサイズが著しく大きくなってしまう。応用例によっては、この値を、表示画面のピクセル解像度の１／８または１／１６に縮小する。これと同じスケール係数、またはこれと類似の係数を、描画された記号における点選択の頻度にも適用する。全画面の記号と小さな英数字記号の両方を認識し、再描画するように設計されたシステムでは、記号の認識に２つの独立した回路を使用することができる。この２つの回路は並行して動作することができ、１つの回路を英数字シンボロジの認識に使用し、もう一方の回路を大きなシンボロジの認識に使用する。大きな記号を処理するための代替の手法は、メモリ・アドレスで使用されるΔＸ値およびΔＹ値の計算に使用するアルゴリズムを修正することである。この手法では、描画された記号で最初に選択される点だけを、その記号の開始位置の基準とする。残りの点については、ΔＸとΔＹの値を、そのシーケンス中でその１つ前に選択された点の位置の基準とする。この代替手法は、大きな記号の認識により高い解像度を利用できるという利点を有する。この手法は小さなシンボロジにも使用することができるが、通例大きなシンボロジにはより低い点選択の頻度が用いられるので、小さい記号と大きな記号には独立した記号認識機構を用いるのが有利である。応用例によっては、大きな記号と小さい記号の混合を取り込んだ、特定の表示形式の限定されたセットしか表示しないものもある。このような応用例では、２つの記号認識回路を併せて使用して、描画された記号の混合および／またはシーケンス化によって特定の表示形式を識別することができる。
【００５０】
多くのシステムでは、英数字記号の基本的なセットを複数のサイズで表示することができる。この記号認識機構は、所与の記号の各サイズを、完全に異なる記号として扱うことができる。先の例における合計１２８個の異なる記号は、基本的な記号セットの２つまたは３つの異なるサイズの認識を可能にすることができる。この手法は、複数サイズのシンボロジを扱う方法の中で最も費用効果の高いものであると思われる。ただし、この記号認識機構が、時間分割式に複数のデータ・ストリームを処理するのに十分な速さを有するのであれば、複数の記号サイズを認識する別の手法が可能である。メモリ・テーブルは、メモリ・アドレスの最初のストリームを介して「通常サイズ」の記号を認識するように設計することができる。その後、ΔＸとΔＹの値を代替サイズから「通常」サイズにスケーリングすることにより、各代替記号サイズについて追加のデータ・ストリームを生成することができる。すると、この記号認識機構が、このデータ・ストリームすべてによって時間分割式に使用される。次いで、特定のデータ・ストリームのスケール係数から、認識された記号の実際のサイズを求めることができる。代替の手法は、単一のデータ・ストリームだけから、複数サイズの記号を認識することを可能にする。この手法では、描画された各記号上の特定の点（例えば、最初のビデオ遷移がある点）を固定値にスケーリングし、同じスケール係数をその描画記号で選択されるすべての点に適用する。（この手法を簡潔にするために、スケール係数は、ΔＸまたはΔＹのうち大きい方を固定値にスケーリングすることによって得てもよい。）次いで、描画された点で使用したスケーリング・アルゴリズムと整合する記号固有のスケール係数とともに、各ライブラリ記号をテーブルに記憶する。そして、テーブルのスケール係数と、描画された点に適用されたスケール係数から、認識された記号の実際のサイズを得ることができる。
【００５１】
本発明は、回転された記号の認識にも用いることができる。最適な実時間のパフォーマンスのために、記号認識機構は、入力された点のシーケンスをすべてのライブラリ記号について同時にテストするだけでなく、これらの記号を任意の可能な方向で認識するように設計すべきである。ライブラリ記号の回転させたバージョンをメモリ・テーブルに含めると、メモリ・サイズが著しく増大する。しかし、図３に示す記号認識機構を修正すると、メモリを増加させずに、回転した記号を認識することが可能になる。この修正を加えた手法では、描画された記号の上で選択される点はそれぞれの極座標によって定義される。所与の点のΔＸおよびΔＹの値は、テーブル・ルックアップ・オペレーションによって、それに対応する極座標の値（ｒとθ）に変換することができる。先の例では、ΔＸとΔＹはともに、６ビットの符号付きの値である。これらの値は、ｒについては５ビットの大きさの値に、θについては７ビットの角度値に変換することができる。ΔＸおよびΔＹの値と同様に、これらの極座標値も記号の位置に相対的にすることができる。したがって図２Ａの記号「Ｎ」４００では、この２つの値を点４０２の基準とし、図２Ｂの記号「Ｌ」４２０では、この２つの値を点４２２の基準とする。この結果、記号認識に使用されるメモリ・アドレスは、単一ビットのビデオ値、ｒの値、およびθの値からなる。したがって、ライブラリ記号を反映する、メモリ・テーブルに記憶されたデータは極座標系に一致する。
【００５２】
回転を扱うアルゴリズムでは、「描画されるオフセット角度」の減算によって、メモリ・アドレス・シーケンス中のθ値を、描画された記号上のそれに対応する点のθ値から修正する必要がある。このオフセット角度により、描画された記号を、記号認識機構に入力される前に効果的に回転させる。描画された記号で最初に選択される点の角度は保存して、描画されるオフセット角度の値に使用する。したがって、その実際の方向に関係なく、描画されたライブラリ記号は常に同じ方向で記号認識機構に提示されることになる（すなわち、「０」に等しい最初に選択された点の角度で）。したがって、メモリ・テーブルは、各ライブラリ記号の１つの方向だけを記憶すればよく、メモリ・テーブル中の所与の記号の方向は、その特定の記号に固有であることができる。（このメモリ・アドレス中の角度ビットは常に「０」なので、構造のレベル１にある単一のメモリ・テーブルは、他のテーブルよりも小さくてよいことに留意されたい。）
ここでは、通常の、すなわち回転されない所与のライブラリ記号の方向は、「０」に等しい回転角度に対応するものと定義する。図２Ａは、位置４０２におけるその通常方向での（すなわち「０」に等しい回転角度による）記号「Ｎ」４００の描画を示している。この記号で最初に選択される点（すなわち点４０４）の角度は、角度θＮで示している。図２Ｃは、位置４４２における方向−θＮでの記号「Ｎ」４４０の描画を示す。これは、メモリ・テーブルに記憶され、記号認識機構への入力時に提示される記号「Ｎ」の方向である。図２Ｂは、回転させない方向で位置４２２に描画した記号「Ｌ」４２０を示す。記号「Ｌ」４２０で最初に選択される点（すなわち点４２４）は角度θＬを有する。図２Ｄは、点４５２に方向−θＬで描画された記号「Ｌ」４５０を示す。これは、メモリ・テーブル中にある記号「Ｌ」の方向であり、記号認識機構の入力に提示される方向である。このように、各ライブラリ記号は、描画された記号で最初に選択される点に角度「０」を与える方向に対応する、その記号に特有の「テーブルオフセット角度」とともにメモリ・テーブルに記憶される。（記号「Ｎ」のテーブルオフセット角度は−θＮに等しく、記号「Ｌ」のテーブルオフセット角度は−θＬに等しい。）記号を認識する際、描画された記号の実際の方向は、描画されるオフセット角度とテーブルオフセット角度の合計によって与えられる。したがって記号はこの方向で再描画することができる。
【００５３】
記号を描画する前のＸとＹの偏向が比較的安定した期間中に、記号の位置を得るために、サンプリングしたＸとＹの値をフィルタリングすることを思い出されたい。これは、複数回の表示の更新にわたって安定した／一貫性のある記号の位置を提供し、それにより動的な表示の異常を防ぐ。回転された記号の動的な異常を回避するには、複数回の更新にわたって安定した正確な回転角度も得る必要がある。上記の回転されたシンボロジを認識する手法は、記号の位置を求めるのに２つの記号点のみに依拠する。これら２点の最初の点、すなわち記号の位置が正確であると分かっている場合でも、第２の点（例えば図２Ａの記号「Ｎ」４００の点４０４）の座標はノイズを受けやすい。したがって、求めた回転角度が、記号認識に適するものであっても、動的な表示の異常を回避するのに十分な安定性を複数回の更新にわたって持たないことがある。ただし、図１の点選択機構３１４へのデジタル化されたＸおよびＹの入力はすべて、ＦＩＦＯパイプライン・バッファ３２８に保存される。これを保存することにより、ある記号がライブラリの記号の１つとして認識されないときに、画像メモリに直接描画することが可能になる。描画された記号のこれらの点の一部を、後処理操作（すなわち記号の認識後の処理）で使用して、描画記号のより正確な方向角度を得ることができる。サンプリング・シーケンス中の記号に固有の点である可能性がある複数の点は、記号の方向角度の複数の計算を提供するのに使用することができる。  記号を回転させずに描画する場合、所与の点の予測される角度を、サンプリングした点の実際の角度から減算する。次いでこの複数の記号の方向のサンプルを平均化して、より正確な方向角度を提供することができる。
【００５４】
表示形式によっては、大きなシンボロジと小さいシンボロジの両方に同じ回転角度を使用するものがある（例えば、一部の実時間のアビオニクスの表示形式がそうである）が、この回転角度の値は、より大きなシンボロジからの方が正確に得ることができる。先に指摘したように、描画されたシンボロジの混合および／またはシーケンスから表示形式を識別することができる。このような場合、より大きなシンボロジから求めた回転角度の値を、より小さなシンボロジの再描画に適用することができる。
【００５５】
本発明のこの例示的な応用例は、本発明を説明する手段として使用しているのであり、本発明を制限するものでないことは理解されたい。この応用例の範囲内でも、本発明の実装と使用の変形例が可能である。例えば、回転された記号を認識する手法を、複数の記号サイズを認識する手法と併せて、かつ／または大きな全画面のシンボロジを認識する手法と併せて使用することができる。また、認識した記号をそれが最初に描画された際と同じ形で再描画する必要はない。例えば、異なるサイズや異なるスタイルのフォントで描画することができる。また、認識した記号を完全に異なる記号として再描画する、「記号の置き換え」を実装することも可能である。
【００５６】
本発明は、文字がすでに２次元空間に描画されている（例えばラスタ・ビデオ信号から文字が描画されているような）文字認識に見られる旧来の問題のために使用することもできる。このような文字は、単一のビデオ・ビットを用いる２Ｄビットマップを使用して定義することができる。そしてこのビットマップから、記号認識機構へのメモリ・アドレス入力を直接生成することができる（例えばビットマップの最上行をレベル１のアドレスに使用し、第２行をレベル２のアドレスに使用するなど）。比較的大きなビットマップの場合は、必要とされる各メモリ・テーブルのサイズを縮小するために、ビットマップの各行から２つ以上のメモリ・アドレス入力を得ることができる。言うまでもなく、この操作の前に、文字サイズの正規化（すなわちＸおよびＹのスケーリング）と、水平線または垂直線を選択するため、または垂直方向および／または水平方向の対称性を最大にするための回転によって、ビットマップを前処理してもよい。
【００５７】
多くのシステムでは、サンプリングしたデータ・パラメータの連続的な実時間のストリームでパターンを認識する必要がある。データ・サンプルは、パターン認識機構に入力するために、それに対応するメモリ・アドレスのストリームに変換するか、またはそのために直接使用することができる。そしてメモリ・アドレスの連続的なストリームを使用して、ライブラリ・パターンのセットを含む有限シーケンスのセットと、実時間入力のシーケンスとを比較する。メモリ・テーブルの構造に記憶されるデータは、ライブラリ・パターンのセットから得る。（ライブラリ・パターンのセットは、パターン中のサンプル数によって、異なる長さのシーケンスを含むことができる。メモリ・テーブルの構造中のレベル数は、最も長いライブラリ・パターン中のサンプル数に対応する。）このような応用例の多くでは、ライブラリ・パターンの開始部と一致する可能性のある、入力データ・ストリーム中の特定の位置を（事前に）識別することはできない。したがって、この記号認識機構を、リセット操作を介して可能なデータ・ストリーム・パターンの始まりに同期化させることはできない。したがって、入力データ・ストリームからの所与のメモリ・アドレスが、ライブラリ・パターンのシーケンス中の任意の位置（例えば、メモリ・テーブル構造中の最初のレベルに対応する第１の位置を含む）と一致することは可能である。また、メモリ構造中の各レベルは、ライブラリ・パターン中のそれに対応するサンプル位置と関連付けられるので、メモリ構造のあらゆるレベルで、テーブル・ルックアップ・オペレーションによって各メモリ・アドレスの入力をテストする必要がある。本発明のハードウェアの実施形態を用いると、メモリ構造のあらゆるレベルで、各メモリ・アドレス入力について同時にテーブル・ルックアップ・オペレーションを実行することができる。したがって、入力データ・ストリーム中のパターンの開始位置を事前に識別できないことによってパフォーマンスが犠牲となる必要はない。
【００５８】
メモリ構造の各レベルに別個の独立したメモリを有する本発明のハードウェア実装を考えてみたい。この場合は、これらのメモリのすべてに同時にアクセスすることが可能である（例えば制御クロック信号の周期ごとなどに）。この各メモリへのアドレス入力は２つの部分からなる。１つの部分は、パターン認識回路へのメモリ・アドレス入力のストリームによって提供される（すなわち、現在のメモリ・アドレス入力がすべてのメモリに供給される）。アドレスのこの部分は、選択されたテーブルで特定の項目を選択するのに使用される。各アドレスの第２の部分は、各メモリ内で特定のテーブルを選択するのに使用される。各メモリ／レベルへのテーブル・アドレスは、その１つ前のクロック・サイクルの出力により、構造中で次に高いレベルのメモリから提供される（構造のレベル１が単一のメモリ・テーブルしか持たない可能性があることを除いては）。
【００５９】
次に、ここでサイクル「ｉ」と呼ぶクロック・サイクルで開始するこのパターン認識回路の動作を考えてみたい。このクロック・サイクル中に、各メモリ／レベルにおけるテーブル・ルックアップ・オペレーションのために、実時間の入力パラメータのサンプル「ｉ」に対応するメモリ・アドレス入力が使用される。レベル１のテーブル・ルックアップ・オペレーションを使用して、記憶された各ライブラリ・パターンのシーケンス中の最初のサンプルとの整合性について、入力サンプル「ｉ」をテストする。その入力が、パターン中の最初のサンプルだけに基づいてライブラリ・パターンの１つまたは複数と整合する場合、レベル１のメモリ・テーブルは、この可能性を見込んだレベル２の特定のテーブルを選択するテーブル・アドレスを出力する。次いで次のクロック・サイクルでは、この指定されたレベル２のテーブルにおけるテーブル・ルックアップ・オペレーションに入力アドレス「ｉ＋１」が使用される。（このアドレスは、他のレベルのテーブル・ルックアップ・オペレーションにも使用される。例えば、このアドレスは、レベル１で、各ライブラリ・パターンの最初のサンプルとの可能な一致を求めて、入力サンプル「ｉ＋１」をテストするのに使用される。しかし、ここでは、入力サンプル「ｉ」で始まる可能なパターン一致だけを対象とする。）レベル２のテーブル・ルックアップでは、可能な一致として残っているライブラリ・パターンの各シーケンス中の２番目のサンプルに照らして、入力サンプル「ｉ＋１」をテストする（すなわち、サンプル「ｉ」をシーケンス中の最初のサンプルとする）。このテストで、この２つの入力サンプルのシーケンスに対して、１つまたは複数のライブラリ・パターンが可能な一致として残っていると判定された場合、レベル２のテーブルの出力は、この可能性を見込んだレベル３のテーブルを選択するテーブル・アドレスになる。次のクロック・サイクルで、可能な一致として残っている各ライブラリ・パターンのシーケンス中の３番目のサンプルに照らして、３番目のシーケンス入力サンプルをテストするために、この指定されたレベル３のテーブルにおけるテーブル・ルックアップ・オペレーションに、入力サンプル「ｉ＋２」のメモリ・アドレスが使用される。このプロセスは継続し、クロック・サイクルごとにメモリ・テーブル構造を１ステップずつ下へと進む。所与のクロック・サイクルで、対応するいずれかのメモリ構造レベルにおいて、入力サンプルが残りのライブラリ・パターンと整合しない場合は、それがメモリ・テーブルの出力によって示される。この場合、サンプル「ｉ」で始まる入力サンプルのシーケンスは、ライブラリ中のどのパターンとも一致しないことになる。しかし、プロセスがテーブル構造中を進んでライブラリ・パターンの最後のサンプルまで達し、かつ、対応する入力サンプルが、そのライブラリ・パターンの最後のサンプルと一致することが分かった場合は、メモリ出力は、その入力シーケンス（サンプル「ｉ」で始まる）がそのライブラリ・パターンと一致することを示す。
【００６０】
上記から、一回のクロック・サイクルごとに新しい比較動作が開始され、この比較動作は、新しい入力が、ライブラリ・パターンの１つと一致するシーケンス中の最初のサンプルである可能性に基づくことが理解される。開始すると、この比較動作はそれぞれ、一致が見つかるか、またはそのシーケンスがライブラリ・パターンのどれとも一致しないことが判定されることによって中止（ｒｅｔｉｒｅ）されるまで、その後のクロック・サイクルとともに継続する。特定の応用例では、この基本的な回路の異なる実装が必要とされうることは理解されたい。例えば、可能なパターンの開始部で何らかのパラメータの値を使用する前処理操作によって入力メモリ・アドレスが修正される場合（例えば、スケーリングや回転によって修正される場合）には、構造の各レベルで異なる前処理の値が必要になる。（これは、所与のクロック・サイクルで、構造の各レベルが入力データ・ストリーム中の異なる開始位置のデータ・パターンをテストすることによる。）したがって、回路中の各レベル／メモリには、入力メモリ・アドレスを前処理するための独立したハードウェアが必要となる。
【００６１】
上記のパターン認識回路、あるいはこの回路の一部は、単一の集積回路デバイスとして実装することもできる。このデバイスは、構造の各レベルのための独立したメモリと、これらのメモリをアドレス指定する手段を含む（すなわち、メモリ構造中のテーブル・アドレスの経路指定を含む）。このようなデバイスは、メモリ・テーブルのサイズ、各レベルのメモリに相対的な利用可能メモリの割り当て、およびレベルの総数に関して、ある程度のメモリ構造の再構成を可能にするように設計することができる。また、複数のこのようなデバイスからシステムを構成するのを可能にするために、拡張に対応するように設計することもできる。
【００６２】
一部の応用例は、メモリ・テーブルにＲＡＭを使用することによって益を得ることができる。これは、新しいライブラリ・パターンのセットを反映した、新しいテーブル・データのダウンロードが可能になるためである。例えば、これにより、ノイズ・マージンを適応型のシステムによって実時間で修正することが可能になる。これは、メモリ・テーブルからの出力に追加的情報を含めることによって助長することができる。例えば、追加の出力ビットを使用して、あるパターンが認識されたのが何らかのノイズ・マージン内であったか、またはその外側であったかを示すことができる。（実装に関して、これは、ライブラリ中のパターン／記号の数を単に２倍にするのに相当すると見なすことができる。）テーブルは、確率の値を出力して、認識される各パターン／記号ごとに信頼度係数を生成することができるように設計してもよい。無論、これらの技術は、非適応型のシステムにとっても価値があるものになりうる（例えば、システムの自己監視や、障害の検出／予測に使用することができる）。一部の適応型システムは、テーブル・データを得るための学習法も利用することができる。また、システムで複数のパターン認識回路を使用する場合、他の回路をオンラインの状態にしたまま、これらの回路の１つに新しいテーブル・データをロードすることができる。
【００６３】
本発明が、一般的なパターン認識の問題に対して非常に幅広い応用性を有することが示され、また本発明は多くの異なる応用例で使用することができる。実時間のパフォーマンスを改善する、かつ／またはコストを低減するために、本発明を、ニューラル・ネットワークに代えて、あるいはＤＳＰ相関技術に代えて使用することができる。入力データの前処理とメモリ・アドレス入力のシーケンスの生成に使用される入力パラメータの数と、方法およびアルゴリズムは一般には応用例に固有である。前処理には、離散高速フーリエ変換（ＤＦＦＴ）などのＤＳＰ操作を含むことができる。実証したように、入力データの適切な前処理（例えば、スケーリング／正規化、および／または座標変換や回転による）を使用することにより、必要なメモリ・テーブルのサイズおよび／または数を最小にすることができる。こうした前処理技術は、３次元空間でのパターン認識や、２次元平面への３次元物体の投影の認識を必要とする応用例でも使用することができる。ある応用例が、相互に独立したパラメータ、あるいは前処理によって独立させることができるパラメータを有する場合には、この独立したパラメータのために独立したパターン認識機構を実装することができる。この機構からの出力は相関させることができる。この手法は、すべてのパラメータ値を単一のメモリ・アドレスに含める手法に比べて、合計のメモリ・サイズを大幅に減らすことができる。
【００６４】
本発明の他の応用例は、記号と文字の認識以外にも、音声認識、脅威の検出および識別、自動化された製造および検査システム、および視覚／画像の処理システム（例えば製造で使用されるロボットによるピックアンドプレース機など）を含むことができる。当業者には、本発明のこの他多くの応用例と、本発明の多数の他の実施形態形態が明らかになろうことが理解される。頭記の特許請求の範囲は、本発明の真の精神と範囲内に含まれるすべての応用例と実施形態を包含するものと解釈されたい。
【００６５】
ここに示す実施形態および実施例は、本発明とその実際的な応用例を最も明確に説明するために、そして当業者が本発明を作成し、利用することを可能にするために提示する。本発明の範囲は、あらゆる面からの同等形態の完全な認識を提供する、添付の特許請求の範囲によって定義するものとする。
【図面の簡単な説明】
【図１】
本発明による、古いＣＲＴタイプのカリグラフィック表示のための置換システムのブロック図を示す図である。
【図２】
本発明による、シンボル「Ｎ」および「Ｌ」が回転なしにレンダリングされる方法、および、これらがメモリ・テーブルにおいて、回転されたシンボロジの認識が可能となるように方向付けられるときの一実施例を示す図である。
【図３】
本発明によるシンボル認識メカニズムのオペレーションの一実施例を示す図である。
【図１】
2004537768.tif 000003
【図３】
2004537768.tif 000004
【国際公開パンフレット】
2004537768.tif 000005
2004537768.tif 000006
2004537768.tif 000007
2004537768.tif 000008
2004537768.tif 000009
2004537768.tif 000010
2004537768.tif 000011
2004537768.tif 000012
2004537768.tif 000013
2004537768.tif 000014
2004537768.tif 000015
2004537768.tif 000016
2004537768.tif 000017
2004537768.tif 000018
2004537768.tif 000019
2004537768.tif 000020
2004537768.tif 000021
2004537768.tif 000022
2004537768.tif 000023
2004537768.tif 000024
2004537768.tif 000025
2004537768.tif 000026
2004537768.tif 000027
2004537768.tif 000028
2004537768.tif 000029
2004537768.tif 000030
2004537768.tif 000031
2004537768.tif 000032
2004537768.tif 000033
2004537768.tif 000034
2004537768.tif 000035
2004537768.tif 000036
2004537768.tif 000037
2004537768.tif 000038
2004537768.tif 000039
2004537768.tif 000040
2004537768.tif 000041
2004537768.tif 000042
2004537768.tif 000043
2004537768.tif 000044
2004537768.tif 000045
2004537768.tif 000046
2004537768.tif 000047
2004537768.tif 000048
2004537768.tif 000049
2004537768.tif 000050
2004537768.tif 000051
2004537768.tif 000052
2004537768.tif 000053
2004537768.tif 000054
2004537768.tif 000055
2004537768.tif 000056
2004537768.tif 000057
2004537768.tif 000058
2004537768.tif 000059
2004537768.tif 000060
2004537768.tif 000061
2004537768.tif 000062
2004537768.tif 000063
2004537768.tif 000064
2004537768.tif 000065
2004537768.tif 000066
2004537768.tif 000067
2004537768.tif 000068
【国際公開パンフレット（コレクトバージョン）】
2004537768.tif 000069
【国際調査報告】
2004537768.tif 000070
2004537768.tif 000071
2004537768.tif 000072
2004537768.tif 000073