手書きでないテキストを使用して手書きデータベースを探索する為の方法及びシステム
【課題】利用できる入力メカニズムがテキスト・エントリーだけである時、デジタル・インク・データベースの探索を可能にし、デジタル・インク・データベースの作成者以外の人物がデジタル・インク・データベースを探索できるようにする。
【解決手段】筆跡特徴合成を使用してインク・データベースを探索し、テキスト・ベースのクエリーを使用してデジタル・インク・データベースの探索を可能にするシステムおよび方法が開示される。手書き文字認識システムまたは適切なトレーニング手順から引き出された書き手特有の筆跡モデルを使用して、テキスト・クエリーは、デジタル・インク・データベースの作成者がテキスト・クエリーを手で書いたとすれば抽出されたであろう特徴ベクトルと類似した特徴ベクトルへ変換される。次に、特徴ベクトルはデータベースを探索するために使用される。
【解決手段】筆跡特徴合成を使用してインク・データベースを探索し、テキスト・ベースのクエリーを使用してデジタル・インク・データベースの探索を可能にするシステムおよび方法が開示される。手書き文字認識システムまたは適切なトレーニング手順から引き出された書き手特有の筆跡モデルを使用して、テキスト・クエリーは、デジタル・インク・データベースの作成者がテキスト・クエリーを手で書いたとすれば抽出されたであろう特徴ベクトルと類似した特徴ベクトルへ変換される。次に、特徴ベクトルはデータベースを探索するために使用される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的には、デジタル・プロセッサによって実現される手書き文字の探索または認識システムに関し、具体的には、手書きでないテキストを使用して手書きデータベースを探索する為の方法及びシステムに関する。
【背景技術】
【０００２】
本明細書で使用される「デジタル・インク・データベース」とは、手書きの文字、例えば手書きのレターを形成する手書き文字のストリングを記憶するデータベースを意味する。
【概説】
【０００３】
ペン・ベースのコンピューティング・システムは、人間とコンピュータの交信に便利で柔軟な手段を提供する。ほとんどの人は、ペンと紙を使用することに非常に慣れている。この習慣を、この媒体によって全く自然にサポートされるテキスト、線画、または計算のために、データ入力および記録メカニズムとしてペン状のデバイスを使用する既知のシステムに取り入れている。更に、書かれたインクは、デジタル・テキストよりも表現に富む形式であり、インク・ベースのシステムは言語から独立可能である。
【０００４】
ペン・コンピューティングの使用の増加、およびネットワーク・コンピューティング・リソースへのペーパー・ベース・インタフェースの出現（例えば、Ｐ．Ｌａｐｓｔｕｎ，ＮｅｔｐａｇｅＳｙｓｔｅｍ Ｏｖｅｒｖｉｅｗ，Ｓｉｌｖｅｒｂｒｏｏｋ Ｒｅｓｅａｒｃｈ Ｐｔｙ Ｌｔｄ，６ｔｈ Ｊｕｎｅ，２０００、およびＡｎｏｔｏ，“Ａｎｏｔｏ，Ｅｒｉｃｓｓｏｎ，ａｎｄＴｉｍｅ Ｍａｎａｇｅｒ Ｔａｋｅ Ｐｅｎ ａｎｄ Ｐａｐｅｒ ｉｎｔｏ ｔｈｅ Ｄｉｇｉｔａｌ Ａｇｅ ｗｉｔｈ ｔｈｅ Ａｎｏｔｏ Ｔｅｃｈｎｏｌｏｇｙ”，ＰｒｅｓｓＲｅｌｅａｓｅ，６ｔｈ Ａｐｒｉｌ，２０００を参照されたい）は、（生の）デジタル・インクを記憶、索引、および探索することのできる手法の必要性を表している。ペン・ベース・コンピューティングによって、ユーザは、メモおよび注釈の形式でデータを記憶することができ、後で手書きのクエリーに基づいて、このデータを探索することができる。しかしながら、手書きテキストの探索は、従来のテキスト（例えばＡＳＣＩＩテキスト）の探索よりも困難である。筆跡の生成に一貫性がなく、書き手によってスタイルが変化するからである。
【デジタル・インク・データベースの探索】
【０００５】
デジタル・インク・データベースで手書きデータを探索する従来の方法は、パターン認識手法を使用して、先ずデジタル・インク・データベースおよび対応する探索クエリーを標準テキストへ変換し、次にデータベースの中で、変換された標準テキストとクエリー・テキストを照合することである。手書き文字認識によって生成された誤りに類似した文字誤りの存在のもとでテキスト照合を実行するファジー・テキスト探索方法は既に説明されている。Ｐ．Ｈａｌｌ及び Ｇ．Ｄｏｗｌｉｎｇによる “Ａｐｐｒｏｘｉｍａｔｅ Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ”，Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ，１２（４），３８１〜４０２頁，１９８０年、を参照されたい。
【０００６】
しかしながら、手書き文字認識の正確性は低いままであり、（データベース・エントリーおよび手書きクエリーの双方について）手書き文字認識によって導入された誤りの数は、この手法が良好に働かないことを意味している。手書き情報をテキストへ変換するプロセスは、筆跡の一般的形状およびダイナミック特性に関して、かなりの情報量の喪失を生じる。例えば、ある字句（例えば、「ｕ」と「ｖ」、「ｖ」と「ｒ」、「ｆ」と「ｔ」等）は、手書きの場合、形状が非常に類似する。更に、多くの手書きスタイル（特に筆記体で書く場合）、個々の文字の識別が非常に不明瞭である。
【０００７】
デジタル・インク・データベースを直接探索および索引する様々な手法は、従来技術で知られている。例えば、Ａ．Ｐｏｏｎ，Ｋ．Ｗｅｂｅｒ，及び Ｔ．Ｃａｓｓによる“Ｓｃｒｉｂｂｌｅｒ：ＡＴｏｏｌ ｆｏｒ Ｓｅａｒｃｈｉｎｇ Ｄｉｇｉｔａｌ Ｉｎｋ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ Ｃｏｍｐｕｔｅｒ−Ｈｕｍａｎ Ｉｎｔｅｒａｃｔｉｏｎ，５８〜６４頁，１９９４年、Ｉ．Ｋａｍｅｌによる“ＦａｓｔＲｅｔｒｉｅｖａｌ ｏｆ Ｃｕｒｓｉｖｅ Ｈａｎｄｗｒｉｔｉｎｇ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅｏｎ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｍａｎａｇｅｍｅｎｔ，Ｒｏｃｋｖｉｌｌｅ，ＭＤ ＵＳＡ，Ｎｏｖｅｍｂｅｒ １２〜１６，１９９６、Ｗ．Ａｒｅｆ，Ｄ．Ｂａｒｂｅｒａ，Ｐ．Ｖａｌｌａｂｈａｎｅｎｉによる“ＴｈｅＨａｎｄｗｒｉｔｔｅｎ Ｔｒｉｅ：Ｉｎｄｅｘｉｎｇ Ｅｌｅｃｔｒｏｎｉｃ Ｉｎｋ”，Ｔｈｅ １９９５ ＡＣＭ ＳＩＧＭＯＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅｏｎ Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ，Ｓａｎ Ｊｏｓｅ，Ｃａｌｉｆｏｒｎｉａ，Ｍａｙ １９９５、Ｗ，Ａｒｅｆ，Ｄ．Ｂａｒｂｅｒａ，Ｄ．Ｌｏｐｒｅｓｔｉ 及びＡ.Ｔｏｍｋｉｎｓによる “Ｉｎｋ ａｓ ａ Ｆｉｒｓｔ−Ｃｌａｓｓ Ｄａｔａｔｙｐｅ ｉｎ Ｍｕｌｔｉｍｅｄｉａ Ｄａｔａｂａｓｅｓ”，Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍ−Ｉｓｓｕｅｓａｎｄ Ｒｅｓｅａｒｃｈ Ｄｉｒｅｃｔｉｏｎ，１１３〜１６３頁，１９９６年、およびＲ．Ｍａｎｍａｔｈａ，Ｃ．Ｈａｎ，Ｅ．Ｒｉｓｅｍａｎ 及び Ｗ．Ｃｒｏｆｔによる“ＩｎｄｅｘｉｎｇＨａｎｄｗｒｉｔｉｎｇ Ｕｓｉｎｇ Ｗｏｒｄ Ｍａｔｃｈｉｎｇ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｉｒｓｔ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅｏｎ Ｄｉｇｉｔａｌ Ｌｉｂｒａｒｉｅｓ，１５１〜１５９頁，１９９６年、を参照されたい。
【０００８】
これらのシステムは、クエリー・ペン・ストロークのセットから引き出された特徴ベクトルを、デジタル・インク・データベースから引き出された特徴ベクトルのデータベースと比較するため、類似性計量を使用する。クエリーとの最大類似性を示すデータベースのエントリーは、マッチとして返却される。更に、幾つかのアプローチは、索引を作成するか区分化スキームを使用して、データベースの全てのエントリーを順次に探索することを避ける。例えば、Ｄ．Ｂａｒｂａｒａ，Ｗ．Ａｒｅｆ，Ｉ．Ｋａｍｅｌ及び Ｐ．Ｖａｌｌａｂｈａｎｅｎｉによる“Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｉｎｄｅｘｉｎｇ ａ Ｐｌｕｒａｌｉｔｙ ｏｆ ＨａｎｄｗｒｉｔｔｅｎＯｂｊｅｃｔｓ”，米国特許第５，６４９，０２３号、Ｄ．Ｂａｒｂａｒａ 及び Ｉ．Ｋａｍｅｌによる“Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ ＳｉｍｉｌａｒｉｔｙＭａｔｃｈｉｎｇ ｏｆ Ｈａｎｄｗｒｉｔｔｅｎ Ｄａｔａ Ｏｂｊｅｃｔｓ”，米国特許第５，７１０，９１６号、Ｄ．Ｂａｒｂａｒａ 及び Ｈ．Ｋｏｒｔｈによる“Ｍｅｔｈｏｄａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｓｔｏｒａｇｅ ａｎｄ Ｒｅｔｒｉｅｖａｌ ｏｆ Ｈａｎｄｗｒｉｔｔｅｎ Ｉｎｆｏｒｍａｔｉｏｎ”，米国特許第５，５２４，２４０号、Ｄ．Ｂａｒｂａｒａ及び Ｗ．Ａｒｅｆによる“Ｍｅｔｈｏｄ ｆｏｒ Ｉｎｄｅｘｉｎｇ ａｎｄ Ｓｅａｒｃｈｉｎｇ Ｈａｎｄｗｒｉｔｔｅｎ Ｄｏｃｕｍｅｎｔｓ ｉｎ ａ Ｄａｔａｂａｓｅ”，米国特許第５，５５３，２８４号、Ｒ．Ｈｕｌｌ，Ｄ．Ｒｅｙｎｏｌｄｓ及び Ｄ．Ｇｕｐｔｅｒによる“Ｓｃｒｉｂｂｌｅ Ｍａｔｃｈｉｎｇ”，米国特許第６，０１８，５９１号、Ａ．Ｐｏｏｎ，Ｋ．Ｗｅｂｅｒ 及び Ｔ．Ｃａｓｓによる“Ｓｅａｒｃｈｉｎｇａｎｄ Ｍａｔｃｈｉｎｇ Ｕｎｒｅｃｏｇｎｉｚｅｄ Ｈａｎｄｗｒｉｔｉｎｇ”，米国特許第５，６８７，２５４号、およびＷ．Ａｒｅｆ 及び Ｄ．Ｂａｒｂａｒａによる“ＴｒｉｅＳｔｒｕｃｔｕｒｅ Ｂａｓｅｄ Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｉｎｄｅｘｉｎｇ ａｎｄ Ｓｅａｒｃｈｉｎｇ Ｈａｎｄｗｒｉｔｔｅｎ Ｄａｔａｂａｓｅｓｗｉｔｈ Ｄｙｎａｍｉｃ Ｓｅａｒｃｈ Ｓｅｑｕｅｎｃｉｎｇ”，米国特許第５，７６８，４２３号を参照されたい。
【０００９】
他の研究、即ち、Ｊ．Ｈｏｌｌｅｒｂａｃｈによる“Ａｎ Ｏｓｃｉｌｌａｔｉｏｎ Ｔｈｅｏｒｙ ｏｆ Ｈａｎｄｗｒｉｔｉｎｇ”，Ｂｉｏｌｏｇｉｃａｌ Ｃｙｂｅｒｎｅｔｉｃｓ，１３９〜１５６頁，１９８１年、およびＹ．Ｓｉｎｇｅｒ及び Ｎ．Ｔｉｓｈｂｙによる“Ｄｙｎａｍｉｃａｌ Ｅｎｃｏｄｉｎｇ ｏｆ Ｃｕｒｓｉｖｅ Ｈａｎｄｗｒｉｔｉｎｇ”，ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ＣｏｍｐｕｔｅｒＶｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，１９９３年、は、筆跡合成のために手書きの物理特性をモデル化する努力を説明している。
【本発明の開示】
【００１０】
前に説明したデジタル・インク・データベース探索手法は、デジタル・インク・データベースを作成した書き手によって生成されるインク・クエリーに依存する。しかしながら、デジタル・インク・データベースが、他の入力メカニズム、例えばコンピュータ・キーボードで入力されるか、または音声認識システムによって発話および認識されたテキスト・クエリーを使用して探索できれば有利であろう。あるいは、第三者が、自分の筆跡を使用するか、テキスト・ベースのクエリーを使用してデジタル・インク・データベースを探索したいと望むかも知れない。
【００１１】
筆跡特徴合成を用いたインク・データベース探索は、テキスト・ベースのクエリーを使用してデジタル・インク・データベースを探索することを可能にする。手書き文字認識システムまたは適切なトレーニング手順から引き出された書き手特有の筆跡モデルを使用して、テキスト・クエリーは特徴ベクトルへ変換される。この特徴ベクトルは、デジタル・インク・データベースの作成者がテキスト・クエリーを手で書いたとすれば抽出されたであろう特徴ベクトルに類似している。次に、特徴ベクトルは、例えば従来の手法を使用してデータベースを探索するために使用される。これは、利用できる唯一の入力メカニズムがテキスト入力である時、デジタル・インク・データベースの探索を可能にし、デジタル・インク・データベースの作成者以外の人物がデジタル・インク・データベースを探索することを可能にする。
【００１２】
本発明の広い形態によれば、テキスト・クエリーを用いてデジタル・インク・データベースを探索する方法が提供される。この方法は、
字句シーケンスおよび関連した特徴ベクトルのテーブルを含む辞典の探索を実行し、テキスト・クエリーを生成するように結合できる字句シーケンスを含む辞典エントリーのシーケンスを決定するステップと、
辞典エントリーのシーケンスに対応する特徴ベクトルのセットを取得するステップと、
特徴ベクトルのセットを用いてデジタル・インク・データベースを探索するステップと、
を含む。
【００１３】
本発明の特定の実施形態によれば、辞典は、手書き文字認識の結果を用いてデジタル・インク・データベースの作成者から取得された筆跡モデルの一部分である。
【００１４】
本発明の実施形態において、筆跡モデルは、字句シーケンスから特徴ベクトルへのマッピングを記憶する。好ましくは、辞典は各々の字句シーケンスについて複数の特徴ベクトルを含む。更に好ましくは、辞典エントリーの複数のシーケンスが決定されると、最小数のエントリーを有する辞典エントリーのシーケンスが使用される。
【００１５】
更なる実施形態において、テキスト・クエリーは、手書き文字認識システムを使用して手書き入力をテキストへ変換し、および／または音声認識システムを使用して音声入力をテキストへ変換することによって取得される。
【００１６】
本発明の特定の形態では、手書き文字認識の結果は、
筆跡をサンプリングするステップと、
フィルタを使用して筆跡を平滑化するステップと、
傾斜補正を実行するステップと、
ゾーン推定アルゴリズムを使用して高さの正規化を実行するステップと、
特徴抽出を使用してサブストロークの区分化および特徴ベクトルの生成を実行するステップと、
特徴ベクトルのセットの特徴縮減を使用するステップと、
ベクトル量子化を実行し、特徴ベクトルを集団化してコードワード・ベクトルを生成するステップと、
生成されたテキスト字句から最も可能性の高いワードを辞書から探索するステップと、
によって取得される。
【００１７】
本発明の更に広範な形態によれば、クエリーを用いてデジタル・インク・データベースを探索する装置が提供される。この装置は、
ユーザがクエリーを入力するための入力デバイスと、
クエリーを受け取り、デジタル・インク・データベースと通信することのできるプロセッサと、
クエリーがまだテキスト・クエリーでない場合、クエリーをテキスト・クエリーへ変換する手段と、
辞典の探索を実行し、テキスト・クエリーを生成するために結合できる字句シーケンスを含む辞典エントリーのシーケンスを決定する手段と、
辞典エントリーのシーケンスに対応する特徴ベクトルのセットを取得する手段と、
特徴ベクトルのセットを用いてデジタル・インク・データベースを探索する手段と、
探索の結果をユーザへ表示する出力デバイスと
を備える。
【００１８】
本発明の実施形態の他の態様によれば、テキスト・クエリーは、探索の特徴ベクトルを生成するために使用される筆跡モデルとは異なる筆跡モデルを使用して筆跡から生成される。
【００１９】
本発明の更に広い形態によれば、クエリーを用いてデジタル・インク・データベースを探索する装置が提供される。この装置は、
デジタル・インク・データベースを記憶するストレージと、
辞典の探索を実行し、テキスト・クエリーを生成するために結合できる字句シーケンスを含む辞典エントリーのシーケンスを決定し、
辞典エントリーのシーケンスに対応する特徴ベクトルのセットを取得し、
特徴ベクトルのセットを使用してデジタル・インク・データベースを探索するように構成された
プロセッサと、を備え、
辞典は、手書き文字認識の結果を使用してデジタル・インク・データベースの作成者から取得された筆跡モデルの一部分である。
【本発明を実施する形態】
【００２０】
本発明は、添付の図面と関連づけて記述される本発明の好ましいが非限定的な実施形態の以下の説明から明らかになるであろう。この説明は、単なる例として示されている。
【００２１】
次の形態は、本発明の主題の正確な理解を提供するため、書かれた説明および添付のクレイムに適用されるものとして記述される。
【Ｉ．好ましい実施形態】
【００２２】
本発明は、テキスト・クエリーを使用してデジタル・インク・データベースを探索する方法および装置を提供する。本発明の特徴を示すために組み込まれた図面において、図面の全体にわたって同様の部分を識別するため、同様の参照符号が使用される。
【００２３】
本発明の実施形態は、処理システムを使用して実現することができる。処理システムの１つの例が図１に示される。具体的には、図示されるように、処理システム１０は、一般的に、少なくともバス２４を介して相互に結合されたプロセッサ２０、メモリ２１、入力デバイス２２、例えばグラフィックス・タブレットおよび／またはキーボード、出力デバイス２３、例えばディスプレイを含む。処理システムをデジタル・インク・データベース１１へ結合するため、２５で示されるような外部インタフェースも設けられる。
【００２４】
使用に当たって、処理システム１０は、データが、デジタル・インク・データベース１１の中に記憶され、および／またはそこから検索されるように構成させる。プロセッサ２０は、入力２２を介して手書きデータ、テキスト・クエリー等を受け取る。これにより、処理システム１０は任意の形式の処理システムまたは端末、例えばコンピュータ、ラップトップ、サーバ、特殊のハードウェア等であってよいことが分かるであろう。
【筆跡のモデル化】
【００２５】
書き手特有の筆跡モデルは、特定のユーザの手書きスタイルを記述する。ほとんどのユーザ適合手書き文字認識システムは、個々のユーザのスタイル変化に対処するある種のモデルを生成する。一般的に、これらの筆跡モデルの目的は、入力ペン・ストロークのセットから抽出された特徴ベクトルを、認識されたテキストを表す字句のセットへマップすることである。
【００２６】
しかしながら、デジタル・インクを探索する特徴合成アプローチは、書き手特有の筆跡モデルを使用して、逆マッピングを実行する。即ち、書き手がクエリー・テキストを手で書いたとしたら抽出されたであろう特徴を近似する特徴ベクトルのセットへクエリー・テキストを変換するため、モデルが使用される。図２は、手書きテキスト認識システムにおける一般的ステップの詳細を示す。筆跡は２６でサンプリングされ、生のインク２７が正規化ステップ２８へ渡される。正規化されたインク２９は、区分化ステップ３０を経て、結果のストローク３１は特徴抽出ステップ３２へ渡される。特徴抽出ステップ３２は特徴ベクトル３３を抽出する。次に、筆跡モデル３５を使用して、分類ステップ３４が実行される。このステップはプリミティブ３６を生成する。テキスト認識ステップ３７はプリミティブ３６を受け取り、言語モデル３８および／または筆跡モデル３５を使用して、生のインク２７に対応するテキスト３９を生成する。
【００２７】
特徴合成を使用してインク・データベースを探索するには、追加のステップが必要である。書き手特有の筆跡モデル３５は、テキストをインク特徴へマップする情報を記憶するように修正される必要がある。このマッピングを実行するため、個々の字句および字句グループ（即ち、字句のシーケンス）を特徴へ変換するテーブル（辞典と呼ばれる）が、筆跡モデルの中に含められる。認識が実行された後、出力テキストの中の字句および認識に使用された対応する特徴ベクトルを辞典へ追加することができる。
【００２８】
通常一緒に起こる字句のグループおよび対応する特徴ベクトルは、連結されて辞典へ追加される。これが望ましい理由は、手書きが共結合効果を示し（字句を書く時、前後の字句の形状によって影響される）、よく書かれる字句（例えば、「ｑｕ」、「ｅｄ」、および「ｉｎｇ」）は、共結合を示しやすいからである。字句グループの特徴ベクトルを記憶することによって、ストローク・シーケンスの文脈的効果を考慮したクエリー・インクのより正確なレンダリングを生成することができる。
【００２９】
辞典は、各々の字句シーケンスについて複数の特徴ベクトルを記憶できなければならない。同じ字句が何回も認識され得るから、辞典は、字句を最良に表す特徴ベクトルを選択できなければならない。これは、各々の字句シーケンスについて認識器から出力された全ての特徴ベクトル・シーケンスを、その特徴ベクトル・シーケンスがその字句シーケンスについて発見された回数のカウントと一緒に記憶することによって可能となる。字句シーケンスについて最高のカウント（即ち、発見の頻度が最も高く、したがって最も蓋然的な）特徴ベクトル・シーケンスが、特徴合成の間に使用される。
【００３０】
どの字句グループを記憶するかの選択は、文字遷移統計（例えば、テキスト・コーパスから引き出される）に基づかせることができる。その場合、高い発生確率を有する字句シーケンスが記憶される（例えば、「ｉｎｇ」の確率は「ｉｎｘ」の確率よりも、はるかに大きい）。あるいは、認識の後で全ての可能な字句グループを記憶し、テーブルがあまりに大きくなった時、ある種の選択手順（例えば、最小近時使用）を実行することができる。
【００３１】
辞典の中でワードの終わりを明示的にモデル化することによって、更なる改善を達成することができる。多くの筆記スタイルとして、文字はワードの終わりで不完全に書かれる。これは、特に、手で書かれるワードの接尾辞、例えば「ｉｎｇ」、「ｅｒ」、および「ｅｄ」において明らかである。この行動をモデル化するため、ワード終了文字が字句シーケンスへ付加され（例えば、「ｉｎｇ＃」）、この字句シーケンスがワードの終わりをモデル化することを示す。特徴合成の間、これらのエントリーは、クエリー・ワードを完了するためにのみ使用することができる。
【特徴合成】
【００３２】
デジタル・インク・データベースを探索するため、テキスト・クエリーは、書き手特有の筆跡モデルを使用する特徴合成手順によって、特徴ベクトルのセットへ変換される。次に、これらの特徴ベクトルは、デジタル・インク・データベースを探索するためのクエリータームとして使用される。インク・データベースの探索は、従来のインク・マッチング手法を使用して実行することができる。図３は、この手順を説明している。ステップ４０で、テキストが入力され、テキスト４１は特徴合成ステップ４２へ提供されて、特徴合成ステップ４２は筆跡モデル３５を使用して特徴４３を生成する。特徴４３は、デジタル・インク・データベース１１のインク探索ステップ４４で使用される。これはインク・マッチ４５を生成する。
【００３３】
特徴合成を実行するため、辞典の探索が実行され、結合されてクエリー・テキストを生成できる字句シーケンスを含む辞典エントリーのシーケンスが突き止められる。記憶された特徴ベクトルは、クエリー特徴ベクトルを生成するために連結される。しかしながら、クエリー・テキストを作り出すために使用できる辞典エントリーの異なった組み合わせが多数存在するかも知れない。テキストを生成できる最小数のエントリーが、文脈的効果を最も正確にモデル化するものと仮定する。例えば、次のエントリーが辞典の中に存在すると仮定する。
【００３４】
【表１】
したがって、ワード「ｂｏｒｒｏｗｅｄ」は（ｂｏ）（ｒｒ）（ｏｗ）（ｅｄ）、（ｂｏｒｒ）（ｏｗ）（ｅｄ）、または（ｂｏｒ）（ｒｏｗｅｄ）として作り出すことができ、最後の構成が最も望ましい。なぜなら、最も少ない要素から構成されているからである。
【Ａ＊辞典の探索】
【００３５】
正確な結果を得るため、辞典は非常に大きいことを期待され、ワードに対する辞典エントリーの潜在的組み合わせの数は指数的であろう。長いワードを含むクエリーの場合、全ての順列の完全な列挙は実際的でないかも知れない。字句シーケンスsを探索するために、修正されたＡ＊探索アルゴリズムを使用することができる。Ｓ．Ｒｕｓｓｅｌｌ及び Ｐ．Ｎｏｒｖｉｇ，Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ−Ａ Ｍｏｄｅｒｎ Ａｐｐｒｏａｃｈ，Ｐｒｅｎｔｉｃｅ Ｈａｌｌ，１９９５年、を参照されたい。その場合、パス・コスト関数ｇ（ｓ）は、テキストを作り出すまでに使用された辞典エントリーの数であり、目標までの推定コストは、
ｈ（ｓ）＝１、長さ（ｓ）＜長さ（クエリー）の場合
＝０、他の場合
この発見的方法は、シーケンスがクエリー・ワードよりも少ない字句を有するならば、字句シーケンスを完了するのに少なくとも１つの追加的辞典エントリーが必要であることを記述している。探索ツリーの中のノードは、ｇ（ｓ）＋ｈ（ｓ）によってソートされ（低い得点が優先する）、同じ得点を有するノードはシーケンスにおける字句の数によって順序を決められる（多いものが優先する）。
【００３６】
注意すべきは、ｈ（ｓ）が単調で適格な発見的手法であり（即ち、それは決して目標へ到達するコストを過大に推定しない）、したがって探索は最適解の発見を保証され、最適に効率的である（即ち、最適解を発見することのできる最小数のノードを拡張する）。この結果の証明は、Ｒ．Ｄｅｃｈｔｅｒ及び Ｊ．Ｐｅａｒｌによる“Ｇｅｎｅｒａｌｉｚｅｄ Ｂｅｓｔ−Ｆｉｒｓｔ Ｓｅａｒｃｈ Ｓｔｒａｔｅｇｉｅｓ ａｎｄ ｔｈｅ Ｏｐｔｉｍａｌｉｔｙ ｏｆ Ａ＊”，Ｊｏｕｒｎａｌｏｆ ｔｈｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｍａｃｈｉｎｅｒｙ，３２（３），５０５〜５３６頁，１９８５年、に示されている。
【００３７】
上記の手順の例として、ワード「ｂｏｒｒｏｗｅｄ」の探索が以下に示されている。テーブルの中の各々の行は探索ノードを表し、より高い得点のノードはテーブルの最上部に置かれる。
【００３８】
【表２】
テーブルの最上部にある最も有望なノードが拡張されて、次の結果になる。
【００３９】
【表３】
再び、最も有望なノードが拡張される。
【００４０】
【表４】
最上部のノードが、現在、完了したシーケンスであり、探索中の他のノードは、より良い得点を生成することができず、したがって、このノードが探索結果として選択される。
【ＩＩ．様々な実施形態】
【００４１】
[IIＡ．手書き文字認識を伴わない特徴合成]
特徴合成を使用するインク探索は、手書き文字認識システムを使用しないで実行することができる。この手法は、字句シーケンスおよび関連する特徴ベクトルの辞典を構築して、デジタル・インク・データベースを作成した書き手の筆跡をモデル化する能力を必要とするだけである。
【００４２】
手書き文字認識の結果が、モデル化に利用できなければ、トレーニング手順を使用して、書き手特有の辞典を生成することができる。これを行うため、ユーザは、特定のトレーニング・テキストをコピーすることによって筆跡のサンプルを提供し、次に、このサンプルが辞典を構築するために使用される。トレーニング手順は、完全な手書き文字認識を実行するためには必要でない。なぜなら、筆跡によって表されるテキストは、既に知られているからである。それは、単に、入力を文字およびストロークへ区分化し、ストロークを特徴へ変換し、適切な字句グループおよび関連した特徴ベクトルを辞典の中に記憶するために必要である。
【００４３】
辞典を構築するために使用されるトレーニング・テキストは、個々の字句および字句グループの均衡した例示的セットを提供するように最適化される必要がある。即ち、それは、類似した文字のユニグラム、バイグラム、およびトライグラムの範囲を最大にする必要がある。これに関しては、最も遭遇する可能性が高い字句および字句シーケンスに重点を置いている、Ｊ．Ｐｉｔｒｅｌｌｉ，Ｊ．Ｓｕｂｒａｈｍｏｎｉａ， Ｍ．Ｐｅｒｒｏｎｅ 及び Ｋ．Ｎａｔｈａｎによる“Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ Ｔｒａｉｎｉｎｇ Ｔｅｘｔｓ ｆｏｒ Ｗｒｉｔｅｒ−ＤｅｐｅｎｄｅｎｔＨａｎｄｗｒｉｔｉｎｇ Ｒｅｃｏｇｎｉｔｉｏｎ”，Ａｄｖａｎｃｅｓ ｉｎ Ｈａｎｄｗｒｉｔｉｎｇ Ｒｅｃｏｇｎｉｔｉｏｎ，Ｗｏｒｌｄ Ｓｃｉｅｎｔｉｆｉｃ Ｐｕｂｌｉｓｈｉｎｇ，１９９９年、を参照されたい。
【００４４】
[IIＢ．認識およびインク・マッチングの異なった特徴]
手書き文字認識システムおよびインク・マッチング・アルゴリズムの双方が同じ特徴表現を使用することが望ましい。なぜなら、デジタル・インク・データベースを探索するために使用される特徴は、手書き文字認識の結果から引き出されるからである。
【００４５】
しかしながら、認識特徴を探索特徴へ変換できれば、認識と探索に対して異なった特徴セットを使用することができる。幾つかの特徴セットは、認識特徴から、トレーニング・データのセットから学習される探索特徴への変換を可能にする。
【００４６】
あるいは、多くの特徴セットは、認識特徴からデジタル・インクの近似を再生成することを可能にし、その近似から第２の特徴セットを抽出することができる。即ち、テキスト・クエリーは、特徴合成を使用して特徴ベクトルのセットへ変換され、特徴抽出プロセスの逆変換が特徴へ適用されて、それらをデジタル・インクへ変換し、そのデジタル・インクから探索特徴が抽出される。この手順が、探索特徴の抽出に影響を与えるアーチファクトをデジタル・インクへ決して導入しないように注意しなければならない（例えば、生成されたインクの不連続は、幾つかの特徴抽出手法で問題を生じるかもしれない）。
【００４７】
[IIＣ．第三者のインク探索]
手書き文字認識を使用してインク入力をテキストへ変換し、特徴合成を用いて認識されたテキストをインク探索の特徴へ変換することによって、他の書き手のデジタル・インク・データベースを探索することができる。
【００４８】
図４はこの状況を示し、書き手Ａによって作成されたデジタル・インク・データベースを書き手Ｂが探索する。ステップ４６で、インクが書き手Ｂから受け取られ、ストローク４７が特徴抽出ステップ４８へ渡される。特徴４９が抽出され、認識ステップ５０は言語モデル５１および書き手Ｂのモデル５２を使用して、対応するテキスト５３を生成する。これは、辞典構築ステップ５４で書き手Ｂの辞典を構築するために使用される。字句グループおよび特徴が書き手Ｂのモデル５２へ戻され、モデルを改善／更新する。次に、テキスト５３は特徴合成ステップ４２を経験し、図３を参照して説明した類似のプロセスが実行されて、書き手Ａによって作成されたインク・マッチ４５が検索される。
【ＩＩＩ．更なる例】
【００４９】
次の例は、本発明の一実施形態の更に詳細なアウトラインを提供する。この例は、単なる例として意図され、本発明の範囲を限定するものではない。
【００５０】
このセクションは、特徴合成を使用したインク・データベース探索の実現を詳細に説明する。ワードおよび文字の区分化、および基線方向の正規化を含む多数の前処理ステップが実行されたものと仮定する。これは単に手法を実現する１つの可能な方法であり、プロセスの各々の段階で利用可能な代替方法が存在することに注意されたい。例えば、使用できる多くの異なった区分化スキーム、特徴セット、筆跡モデル、および認識手順が存在する。
【００５１】
特徴合成を使用する手書き文字認識およびインク探索手順は、トレーニング段階および認識または探索段階を必要とする。トレーニング段階の間に、トレーニング・データのセットはストローク特徴へ変換され、ストローク特徴はストローク・プリミティブへ集団化されて筆跡のモデルを作り出すために使用される。認識およびインク探索のために、このモデルは、入力インクをデコードするかインク探索の特徴を合成するために使用される。このプロセスは図５で示される。同じ前処理、正規化、区分化、および特徴抽出手順が、トレーニング、認識、および探索に使用されることに注意されたい。
【００５２】
手書き文字認識システムは、入力インクをストローク・コードワードのセットへマップする。このストローク・コードワードは、マッチするワードを辞典から探索するために使用される。図６は、このプロセスの概略を提供し、個々のステップは以下で詳細に説明される。
【平滑化】
【００５３】
インクは１００Ｈｚの一定レートでサンプリングされる。研究によれば、筆跡は約５Ｈｚでピーク・スペクトル密度を有し、これは約１０Ｈｚでノイズ・レベルへ降下する。Ｈ．Ｔｅｕｌｉｎｇｓ及び Ｆ．Ｍａａｒｓｅによる“Ｄｉｇｉｔａｌ Ｒｅｃｏｒｄｉｎｇ ａｎｄ Ｐｒｏｃｅｓｓｉｎｇ ｏｆ Ｈａｎｄｗｒｉｔｉｎｇ Ｍｏｖｅｍｅｎｔｓ”，ＨｕｍａｎＭｏｖｅｍｅｎｔ Ｓｃｉｅｎｃｅ，３，１９３〜２１７頁，１９８４年、を参照されたい。よって、１０Ｈｚでカットオフを有する低域フィルタは、筆跡信号の関連スペクトル成分に影響を与えることなく高周波ノイズを除去するであろう。
【００５４】
上記の仕様に合致する低域フィルタは、点座標を円形にし、ＦＦＴを実行して高周波成分を除去し、逆ＦＦＴを使用して信号を再生することによって生成できる。しかしながら、簡単な加重平均フィルタも有効に働く。点｛ｐ１．．．ｐｎ｝のシーケンスを平滑化するため、
【００５５】
【数１】
ここで、
【００５６】
【数２】
フィルタの幅kおよびα平滑化係数は、経験的に決定される。
【傾斜補正】
【００５７】
多くの手書きスタイルは、書かれた字句の垂直主軸を有しない（即ち、字句は一貫した傾斜で書かれる）。筆跡傾斜を除去することは、手書き字句の認識を改善できる正規化である。手書きにおいて、ダウンストロークは最も安定および一貫したストロークと考えられ、したがって筆跡傾斜を検出するために有用である。
【００５８】
筆跡傾斜を検出するため、書かれたダウンストロークの点｛ｐ１．．．ｐｎ｝における加重平均方向が推定される。
【００５９】
【数３】
ここで、
【００６０】
【数４】
角度α１およびα２は、どのストローク・セグメントがダウンストロークの一部分として考えられるかを定義し、経験的にそれぞれ４０°および１４０°に設定される（９０°は垂直線を表す）。推定された傾斜が、垂直線からある閾値よりも大きく偏向すれば、傾斜は横ずれ変換を使用して除去される。
【００６１】
【数５】
ここで、ｙｍｉｎおよびｙｍａｘは、インクの境界長方形の最上部と最下部を表す。
【ゾーン推定】
【００６２】
ゾーン推定は、入力インクの高さを正規化するために使用される。英語の字句は３つのゾーン−中間ゾーン（字句、例えば「ａ」、「ｃ」、「ｅ」等の高さに対応する）、および字句、例えば「ｂ」、「ｄ」、「ｇ」、および「ｊ」のアセンダおよびデセンダを含む上方および下方ゾーンを示す。
【００６３】
ゾーン推定は、インク濃度の水平ヒストグラムを使用して実行される。即ち、インクの境界長方形を通過する等間隔の水平線の列について、インク交差の数が決定される。ヒストグラムの中央ピークが発見され、同じようにインク濃度が中央ピーク高のある分数よりも下へ降下するヒストグラムの両側の２つの点が発見される。これらの２つの点は、中間ゾーンの上方および下方境界として選択される。上方および下方ゾーンは、中間ゾーンと境界長方形の垂直極値との間の空間として画成される。
【特徴抽出】
【００６４】
インクは垂直方向の極値（即ち、Ｙ座標の極大および極小）でサブストロークへ区分化される。区分化が起こるためには、選択された区分化点でストロークを分割することによって生成された２つのサブストロークの長さが、前もって計算された最小距離（推定された中間ゾーンの高さの半分に設定される）を超えなければならない。
【００６５】
次に、区分化されたサブストロークは、ストローク軌道に沿って等間隔に置かれた定数のｎ個の点を含むように再サンプリングされる。次に、座標を正規化することによって、特徴ベクトルがサブストロークのために作り出される。
【００６６】
【数６】
【００６７】
【数７】
ここで、
ｘｍｉｎ＝ブストローク境界長方形のＸ最小値、
ｙｍｉｄｄｌｅ＝中間ゾーンの最上部のＹ座標、
ｈ＝中間ゾーンの高さ（即ち、ｙｂａｓｅ−ｙｍｉｄｄｌｅ）。
【００６８】
次に、特徴ベクトルが、正規化された座標からｆｉ＝｛ｘ’１，ｙ’１，．．．，ｘ’ｎ，ｙ’ｎ｝として作り出される。
【特徴の縮減】
【００６９】
結果のベクトルは、多数の高度に相関した特徴を使用してサブストロークを記述する（明らかに、点ｐｉの座標は、点ｐｉ−１に依存する。以下同様である）。ベクトルの次元をｍへ下げるため（ここでｍ＜２ｎ）、カルーネン・レーベ（Ｋａｒｈｕｎｅｎ−Ｌｏｅｖｅ）変換が使用される（「主成分分析」（ＰｒｉｎｃｉｐａｌＣｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ−Ｒ．Ｄｕｄａ，Ｐ．Ｈａｒｔ，ａｎｄ Ｄ．Ｓｔｏｒｋ，Ｐａｔｔｅｒｎ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ，Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ，ＪｏｈｎＷｉｌｅｙ＆Ｓｏｎｓ，Ｉｎｃ．，５６９〜５７０頁，２００１年）を参照）。この手順は、最小自乗の意味で最適のリニアマッピングを使用して、高次元の特徴を低次元へ投影する。
【００７０】
これを行うため、全てのトレーニング特徴ベクトルＸ＝｛ｆ１，．．．，ｆｎ｝のセットについて、次式を使用した共分散（自己相関）マトリックスが計算される。
【００７１】
【数８】
このマトリックスの固有ベクトルおよび固有値が発見され（三重対角ＱＬ陰アルゴリズムを使用する。Ｗ．Ｐｒｅｓｓ，Ｂ．Ｆｌａｎｎｅｒｙ，Ｓ．Ｔｅｕｋｏｌｓｋｙ 及びＷ．Ｖｅｔｔｅｒｌｉｎｇによる Ｗ．Ｔ．，Ｎｕｍｅｒｉｃａｌ Ｒｅｃｉｐｅｓ ｉｎ Ｃ，Ｃａｍｂｒｉｄｇｅ：Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，１９８８年）を参照）、ＰＣＡマトリックスＺを形成するため、最大ｎ個の固有値に対応する固有ベクトルが使用される。次に、特徴ベクトルは、このマトリックスと乗算され、直交無相関軸を有する新しい特徴空間へ特徴ベクトルを変換する。
【００７２】
【数９】
【ベクトルの量子化】
【００７３】
次に、変換された特徴ベクトルは、コホーネン（Ｋｏｈｏｎｅｎ）自己組織化特徴マップ（ＳＯＦＭ（Ｓｅｌｆ−Ｏｒｇａｎｉｚｉｎｇ Ｆｅａｔｕｒｅ Ｍａｐ））を使用して集団化される。Ｔ．Ｋｏｈｏｎｅｎによる“Ｓｅｌｆ−ＯｒｇａｎｉｚｅｄＦｏｒｍａｔｉｏｎ ｏｆ Ｔｏｐｏｌｏｇｉｃａｌｌｙ Ｃｏｒｒｅｃｔ Ｆｅａｔｕｒｅ Ｍａｐｓ”，Ｂｉｏｌｏｇｉｃａｌ Ｃｙｂｅｒｎｅｔｉｃｓ，４３，５９〜６９頁，１９８２年、を参照されたい。この手法は、監督されない学習手順を使用して入力ベクトルを集団化し、ベクトル間の距離および近接関係ができるだけ遠く維持されるようにする。使用されるＳＯＦＭは２次元構造を有し、可視的に類似したコードワード（即ち、クラスタ）は相互に近づけて置かれる。その結果、２つのコードワード間の距離は、コードワード値の間のある距離計量（例えばユークリッド距離）を使用して容易に計算することができる。
【００７４】
ＳＯＦＭトレーニングは、ランダムな重みで開始される簡単な２層ニューラルネットワークを使用して反復的に実行される。正規化された入力トレーニング・ベクトルｘと最良にマッチする出力ニューロンは、最小ユークリッド距離を使用して発見される。
【００７５】
【数１０】
ここで、ｗｉは出力ノードｉの重みベクトルを表す。最高活動値を有するノードおよびそれを取り巻くノードの重み（近傍関数Λによって決定される）は、次式を使用して更新される。
【００７６】
【数１１】
ここで、ηは学習レート関数であり、ηおよびΛは、典型的には、時間tにわたって変化する。トレーニングは、トレーニング・セットの反復中にニューロン重みへの顕著な変化が存在しなくなるまで継続する。
【００７７】
サブストロークのシーケンスをコードワード・ベクトルへ変換するため、各々のサブストローク特徴ベクトルが、トレーニングされたＳＯＦＭを使用して量子化され、コードワード・ベクトルへ付加される。特徴ベクトルは、ＳＯＦＭコードブックの出力ニューロンに対する最大活動値を選択することによって、コードワードへ量子化される。
【００７８】
【数１２】
【筆跡モデル】
【００７９】
筆跡モデルは、ストローク・コードワード・ベクトルから字句へのマッピング（テキスト認識について）、および字句グループからコードワード・ベクトルへの逆マッピング（特徴合成について）を記憶する。筆跡モデルを構築するため、トレーニング・データにおける各々の字句はコードワード・ベクトルへ変換され、このコードワード・ベクトルは、対応する字句と一緒にテーブルの中に記憶される。
【００８０】
特定のコードワード・シーケンスは多数の字句へマップし（例えば、不完全に書かれた「ｕ」は「ｖ」と同じ特徴ベクトルへマップするかも知れない）、個々の字句は多数のコードワード・ベクトルによってマップされることに注意されたい。コードワード・ベクトルが特定の字句を表した回数のカウントを取ることによって、字句ｘｉについてｎ個の辞典エントリーがあれば、ベクトルが字句ｘｉを表す確率は、次のように計算することができる。
【００８１】
【数１３】
ここで、ｃｉは、コードワード・ベクトルが字句ｘｉを表すように遭遇された回数のカウントである。次のテーブルは、仮説のコードワード・ベクトル｛３，４｝を表すテーブルから取られた例示的エントリーである。
【００８２】
【表５】
このテーブルは、コードワード・シーケンス｛３，４｝が入力の中で遭遇されたならば、それが字句「ｕ」を表す確率が０．５４であり、それが「ｖ」を表す確率が０．４１であり、それが「ｒ」を表す確率が０．０５であることを示す。
【００８３】
逆マッピング・テーブルは同じようにして生成され、字句および字句グループに関連づけられたコードワード・ベクトルを記憶する。
【認識】
【００８４】
手書き文字認識を実行するためには、入力インクが前述したように処理され、結果のコードワード・ベクトルは、筆跡モデルを探索して字句仮説を生成するように使用される。派生字句の可能性が最も高いワードを辞典から探索するため、最良・第１探索ストラテジが使用される。プロセスは下記の図７で示される。
【インクの探索】
【００８５】
インクの探索は、手書き文字認識の間に生成された筆跡モデルを使用して、入力クエリー・テキストをコードワードのシーケンスへマップするように実行される。このコードワード・ベクトルは、弾力的マッチング手法を使用してデジタル・インク・データベースを探索するために使用される。類似のインク・マッチング手法の完全な説明は、Ｄ．Ｌｏｐｒｅｓｔｉ及び Ａ．Ｔｏｍｋｉｎｓによる“Ｔｅｍｐｏｒａｌ−Ｄｏｍａｉｎ Ｍａｔｃｈｉｎｇ ｏｆ Ｈａｎｄ−Ｄｒａｗｎ Ｐｉｃｔｏｒｉａｌ Ｑｕｅｒｉｅｓ”，Ｈａｎｄｗｒｉｔｉｎｇａｎｄ Ｄｒａｗｉｎｇ Ｒｅｓｅａｒｃｈ： Ｂａｓｉｃ ａｎｄ Ａｐｐｌｉｅｄ Ｉｓｓｕｅｓ，ＩＯＳ Ｐｒｅｓｓ，３８７〜４０１頁，１９９６年、に記載されている。次いで、結果のクエリーは類似性の順序に従って並べられ、ユーザに提供される。
【００８６】
このように、本発明に従って、テキスト・クエリーを使用してデジタル・インク・データベースを探索する方法および装置が提供された。この方法および装置は、前述した利点を満足させる。
【００８７】
本発明は、更に、個別的または集合的に本願の明細書で言及または指摘された部分、要素、および特徴にあり、これら部分、要素、または特徴の２つ以上の任意または全ての組み合わせにあると広く言うことができ、本発明が関連を有する技術で既知の同等物を有する特定の整数が言及されている場合は、そのような既知の同等物は、あたかも個々に記載されているかのように、ここに組み込まれていると考えられる。
【００８８】
好適な実施形態が詳細に説明されたが、これまで説明され、また特許請求の範囲に記載されるような本発明の範囲から逸脱することなく、当業者による様々な変更、置換、および代替が可能であることを理解すべきである。
【図面の簡単な説明】
【００８９】
【図１】処理システムを示す。
【図２】手書き文字認識方法の概観を示す。
【図３】特徴合成を使用するデジタル・インク・データベースの探索方法を示す。
【図４】第三者のインク・データベースの探索方法を示す。
【図５】トレーニングおよび認識／探索段階を示す。
【図６】手書き文字認識の方法を示す。
【図７】テキスト認識の例を示す。
【技術分野】
【０００１】
本発明は、一般的には、デジタル・プロセッサによって実現される手書き文字の探索または認識システムに関し、具体的には、手書きでないテキストを使用して手書きデータベースを探索する為の方法及びシステムに関する。
【背景技術】
【０００２】
本明細書で使用される「デジタル・インク・データベース」とは、手書きの文字、例えば手書きのレターを形成する手書き文字のストリングを記憶するデータベースを意味する。
【概説】
【０００３】
ペン・ベースのコンピューティング・システムは、人間とコンピュータの交信に便利で柔軟な手段を提供する。ほとんどの人は、ペンと紙を使用することに非常に慣れている。この習慣を、この媒体によって全く自然にサポートされるテキスト、線画、または計算のために、データ入力および記録メカニズムとしてペン状のデバイスを使用する既知のシステムに取り入れている。更に、書かれたインクは、デジタル・テキストよりも表現に富む形式であり、インク・ベースのシステムは言語から独立可能である。
【０００４】
ペン・コンピューティングの使用の増加、およびネットワーク・コンピューティング・リソースへのペーパー・ベース・インタフェースの出現（例えば、Ｐ．Ｌａｐｓｔｕｎ，ＮｅｔｐａｇｅＳｙｓｔｅｍ Ｏｖｅｒｖｉｅｗ，Ｓｉｌｖｅｒｂｒｏｏｋ Ｒｅｓｅａｒｃｈ Ｐｔｙ Ｌｔｄ，６ｔｈ Ｊｕｎｅ，２０００、およびＡｎｏｔｏ，“Ａｎｏｔｏ，Ｅｒｉｃｓｓｏｎ，ａｎｄＴｉｍｅ Ｍａｎａｇｅｒ Ｔａｋｅ Ｐｅｎ ａｎｄ Ｐａｐｅｒ ｉｎｔｏ ｔｈｅ Ｄｉｇｉｔａｌ Ａｇｅ ｗｉｔｈ ｔｈｅ Ａｎｏｔｏ Ｔｅｃｈｎｏｌｏｇｙ”，ＰｒｅｓｓＲｅｌｅａｓｅ，６ｔｈ Ａｐｒｉｌ，２０００を参照されたい）は、（生の）デジタル・インクを記憶、索引、および探索することのできる手法の必要性を表している。ペン・ベース・コンピューティングによって、ユーザは、メモおよび注釈の形式でデータを記憶することができ、後で手書きのクエリーに基づいて、このデータを探索することができる。しかしながら、手書きテキストの探索は、従来のテキスト（例えばＡＳＣＩＩテキスト）の探索よりも困難である。筆跡の生成に一貫性がなく、書き手によってスタイルが変化するからである。
【デジタル・インク・データベースの探索】
【０００５】
デジタル・インク・データベースで手書きデータを探索する従来の方法は、パターン認識手法を使用して、先ずデジタル・インク・データベースおよび対応する探索クエリーを標準テキストへ変換し、次にデータベースの中で、変換された標準テキストとクエリー・テキストを照合することである。手書き文字認識によって生成された誤りに類似した文字誤りの存在のもとでテキスト照合を実行するファジー・テキスト探索方法は既に説明されている。Ｐ．Ｈａｌｌ及び Ｇ．Ｄｏｗｌｉｎｇによる “Ａｐｐｒｏｘｉｍａｔｅ Ｓｔｒｉｎｇ Ｍａｔｃｈｉｎｇ”，Ｃｏｍｐｕｔｉｎｇ Ｓｕｒｖｅｙｓ，１２（４），３８１〜４０２頁，１９８０年、を参照されたい。
【０００６】
しかしながら、手書き文字認識の正確性は低いままであり、（データベース・エントリーおよび手書きクエリーの双方について）手書き文字認識によって導入された誤りの数は、この手法が良好に働かないことを意味している。手書き情報をテキストへ変換するプロセスは、筆跡の一般的形状およびダイナミック特性に関して、かなりの情報量の喪失を生じる。例えば、ある字句（例えば、「ｕ」と「ｖ」、「ｖ」と「ｒ」、「ｆ」と「ｔ」等）は、手書きの場合、形状が非常に類似する。更に、多くの手書きスタイル（特に筆記体で書く場合）、個々の文字の識別が非常に不明瞭である。
【０００７】
デジタル・インク・データベースを直接探索および索引する様々な手法は、従来技術で知られている。例えば、Ａ．Ｐｏｏｎ，Ｋ．Ｗｅｂｅｒ，及び Ｔ．Ｃａｓｓによる“Ｓｃｒｉｂｂｌｅｒ：ＡＴｏｏｌ ｆｏｒ Ｓｅａｒｃｈｉｎｇ Ｄｉｇｉｔａｌ Ｉｎｋ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ Ｃｏｍｐｕｔｅｒ−Ｈｕｍａｎ Ｉｎｔｅｒａｃｔｉｏｎ，５８〜６４頁，１９９４年、Ｉ．Ｋａｍｅｌによる“ＦａｓｔＲｅｔｒｉｅｖａｌ ｏｆ Ｃｕｒｓｉｖｅ Ｈａｎｄｗｒｉｔｉｎｇ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ５ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅｏｎ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｍａｎａｇｅｍｅｎｔ，Ｒｏｃｋｖｉｌｌｅ，ＭＤ ＵＳＡ，Ｎｏｖｅｍｂｅｒ １２〜１６，１９９６、Ｗ．Ａｒｅｆ，Ｄ．Ｂａｒｂｅｒａ，Ｐ．Ｖａｌｌａｂｈａｎｅｎｉによる“ＴｈｅＨａｎｄｗｒｉｔｔｅｎ Ｔｒｉｅ：Ｉｎｄｅｘｉｎｇ Ｅｌｅｃｔｒｏｎｉｃ Ｉｎｋ”，Ｔｈｅ １９９５ ＡＣＭ ＳＩＧＭＯＤ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅｏｎ Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ，Ｓａｎ Ｊｏｓｅ，Ｃａｌｉｆｏｒｎｉａ，Ｍａｙ １９９５、Ｗ，Ａｒｅｆ，Ｄ．Ｂａｒｂｅｒａ，Ｄ．Ｌｏｐｒｅｓｔｉ 及びＡ.Ｔｏｍｋｉｎｓによる “Ｉｎｋ ａｓ ａ Ｆｉｒｓｔ−Ｃｌａｓｓ Ｄａｔａｔｙｐｅ ｉｎ Ｍｕｌｔｉｍｅｄｉａ Ｄａｔａｂａｓｅｓ”，Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍ−Ｉｓｓｕｅｓａｎｄ Ｒｅｓｅａｒｃｈ Ｄｉｒｅｃｔｉｏｎ，１１３〜１６３頁，１９９６年、およびＲ．Ｍａｎｍａｔｈａ，Ｃ．Ｈａｎ，Ｅ．Ｒｉｓｅｍａｎ 及び Ｗ．Ｃｒｏｆｔによる“ＩｎｄｅｘｉｎｇＨａｎｄｗｒｉｔｉｎｇ Ｕｓｉｎｇ Ｗｏｒｄ Ｍａｔｃｈｉｎｇ”，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｆｉｒｓｔ ＡＣＭ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅｏｎ Ｄｉｇｉｔａｌ Ｌｉｂｒａｒｉｅｓ，１５１〜１５９頁，１９９６年、を参照されたい。
【０００８】
これらのシステムは、クエリー・ペン・ストロークのセットから引き出された特徴ベクトルを、デジタル・インク・データベースから引き出された特徴ベクトルのデータベースと比較するため、類似性計量を使用する。クエリーとの最大類似性を示すデータベースのエントリーは、マッチとして返却される。更に、幾つかのアプローチは、索引を作成するか区分化スキームを使用して、データベースの全てのエントリーを順次に探索することを避ける。例えば、Ｄ．Ｂａｒｂａｒａ，Ｗ．Ａｒｅｆ，Ｉ．Ｋａｍｅｌ及び Ｐ．Ｖａｌｌａｂｈａｎｅｎｉによる“Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｉｎｄｅｘｉｎｇ ａ Ｐｌｕｒａｌｉｔｙ ｏｆ ＨａｎｄｗｒｉｔｔｅｎＯｂｊｅｃｔｓ”，米国特許第５，６４９，０２３号、Ｄ．Ｂａｒｂａｒａ 及び Ｉ．Ｋａｍｅｌによる“Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ ＳｉｍｉｌａｒｉｔｙＭａｔｃｈｉｎｇ ｏｆ Ｈａｎｄｗｒｉｔｔｅｎ Ｄａｔａ Ｏｂｊｅｃｔｓ”，米国特許第５，７１０，９１６号、Ｄ．Ｂａｒｂａｒａ 及び Ｈ．Ｋｏｒｔｈによる“Ｍｅｔｈｏｄａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｓｔｏｒａｇｅ ａｎｄ Ｒｅｔｒｉｅｖａｌ ｏｆ Ｈａｎｄｗｒｉｔｔｅｎ Ｉｎｆｏｒｍａｔｉｏｎ”，米国特許第５，５２４，２４０号、Ｄ．Ｂａｒｂａｒａ及び Ｗ．Ａｒｅｆによる“Ｍｅｔｈｏｄ ｆｏｒ Ｉｎｄｅｘｉｎｇ ａｎｄ Ｓｅａｒｃｈｉｎｇ Ｈａｎｄｗｒｉｔｔｅｎ Ｄｏｃｕｍｅｎｔｓ ｉｎ ａ Ｄａｔａｂａｓｅ”，米国特許第５，５５３，２８４号、Ｒ．Ｈｕｌｌ，Ｄ．Ｒｅｙｎｏｌｄｓ及び Ｄ．Ｇｕｐｔｅｒによる“Ｓｃｒｉｂｂｌｅ Ｍａｔｃｈｉｎｇ”，米国特許第６，０１８，５９１号、Ａ．Ｐｏｏｎ，Ｋ．Ｗｅｂｅｒ 及び Ｔ．Ｃａｓｓによる“Ｓｅａｒｃｈｉｎｇａｎｄ Ｍａｔｃｈｉｎｇ Ｕｎｒｅｃｏｇｎｉｚｅｄ Ｈａｎｄｗｒｉｔｉｎｇ”，米国特許第５，６８７，２５４号、およびＷ．Ａｒｅｆ 及び Ｄ．Ｂａｒｂａｒａによる“ＴｒｉｅＳｔｒｕｃｔｕｒｅ Ｂａｓｅｄ Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｉｎｄｅｘｉｎｇ ａｎｄ Ｓｅａｒｃｈｉｎｇ Ｈａｎｄｗｒｉｔｔｅｎ Ｄａｔａｂａｓｅｓｗｉｔｈ Ｄｙｎａｍｉｃ Ｓｅａｒｃｈ Ｓｅｑｕｅｎｃｉｎｇ”，米国特許第５，７６８，４２３号を参照されたい。
【０００９】
他の研究、即ち、Ｊ．Ｈｏｌｌｅｒｂａｃｈによる“Ａｎ Ｏｓｃｉｌｌａｔｉｏｎ Ｔｈｅｏｒｙ ｏｆ Ｈａｎｄｗｒｉｔｉｎｇ”，Ｂｉｏｌｏｇｉｃａｌ Ｃｙｂｅｒｎｅｔｉｃｓ，１３９〜１５６頁，１９８１年、およびＹ．Ｓｉｎｇｅｒ及び Ｎ．Ｔｉｓｈｂｙによる“Ｄｙｎａｍｉｃａｌ Ｅｎｃｏｄｉｎｇ ｏｆ Ｃｕｒｓｉｖｅ Ｈａｎｄｗｒｉｔｉｎｇ”，ＩＥＥＥ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ＣｏｍｐｕｔｅｒＶｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ，１９９３年、は、筆跡合成のために手書きの物理特性をモデル化する努力を説明している。
【本発明の開示】
【００１０】
前に説明したデジタル・インク・データベース探索手法は、デジタル・インク・データベースを作成した書き手によって生成されるインク・クエリーに依存する。しかしながら、デジタル・インク・データベースが、他の入力メカニズム、例えばコンピュータ・キーボードで入力されるか、または音声認識システムによって発話および認識されたテキスト・クエリーを使用して探索できれば有利であろう。あるいは、第三者が、自分の筆跡を使用するか、テキスト・ベースのクエリーを使用してデジタル・インク・データベースを探索したいと望むかも知れない。
【００１１】
筆跡特徴合成を用いたインク・データベース探索は、テキスト・ベースのクエリーを使用してデジタル・インク・データベースを探索することを可能にする。手書き文字認識システムまたは適切なトレーニング手順から引き出された書き手特有の筆跡モデルを使用して、テキスト・クエリーは特徴ベクトルへ変換される。この特徴ベクトルは、デジタル・インク・データベースの作成者がテキスト・クエリーを手で書いたとすれば抽出されたであろう特徴ベクトルに類似している。次に、特徴ベクトルは、例えば従来の手法を使用してデータベースを探索するために使用される。これは、利用できる唯一の入力メカニズムがテキスト入力である時、デジタル・インク・データベースの探索を可能にし、デジタル・インク・データベースの作成者以外の人物がデジタル・インク・データベースを探索することを可能にする。
【００１２】
本発明の広い形態によれば、テキスト・クエリーを用いてデジタル・インク・データベースを探索する方法が提供される。この方法は、
字句シーケンスおよび関連した特徴ベクトルのテーブルを含む辞典の探索を実行し、テキスト・クエリーを生成するように結合できる字句シーケンスを含む辞典エントリーのシーケンスを決定するステップと、
辞典エントリーのシーケンスに対応する特徴ベクトルのセットを取得するステップと、
特徴ベクトルのセットを用いてデジタル・インク・データベースを探索するステップと、
を含む。
【００１３】
本発明の特定の実施形態によれば、辞典は、手書き文字認識の結果を用いてデジタル・インク・データベースの作成者から取得された筆跡モデルの一部分である。
【００１４】
本発明の実施形態において、筆跡モデルは、字句シーケンスから特徴ベクトルへのマッピングを記憶する。好ましくは、辞典は各々の字句シーケンスについて複数の特徴ベクトルを含む。更に好ましくは、辞典エントリーの複数のシーケンスが決定されると、最小数のエントリーを有する辞典エントリーのシーケンスが使用される。
【００１５】
更なる実施形態において、テキスト・クエリーは、手書き文字認識システムを使用して手書き入力をテキストへ変換し、および／または音声認識システムを使用して音声入力をテキストへ変換することによって取得される。
【００１６】
本発明の特定の形態では、手書き文字認識の結果は、
筆跡をサンプリングするステップと、
フィルタを使用して筆跡を平滑化するステップと、
傾斜補正を実行するステップと、
ゾーン推定アルゴリズムを使用して高さの正規化を実行するステップと、
特徴抽出を使用してサブストロークの区分化および特徴ベクトルの生成を実行するステップと、
特徴ベクトルのセットの特徴縮減を使用するステップと、
ベクトル量子化を実行し、特徴ベクトルを集団化してコードワード・ベクトルを生成するステップと、
生成されたテキスト字句から最も可能性の高いワードを辞書から探索するステップと、
によって取得される。
【００１７】
本発明の更に広範な形態によれば、クエリーを用いてデジタル・インク・データベースを探索する装置が提供される。この装置は、
ユーザがクエリーを入力するための入力デバイスと、
クエリーを受け取り、デジタル・インク・データベースと通信することのできるプロセッサと、
クエリーがまだテキスト・クエリーでない場合、クエリーをテキスト・クエリーへ変換する手段と、
辞典の探索を実行し、テキスト・クエリーを生成するために結合できる字句シーケンスを含む辞典エントリーのシーケンスを決定する手段と、
辞典エントリーのシーケンスに対応する特徴ベクトルのセットを取得する手段と、
特徴ベクトルのセットを用いてデジタル・インク・データベースを探索する手段と、
探索の結果をユーザへ表示する出力デバイスと
を備える。
【００１８】
本発明の実施形態の他の態様によれば、テキスト・クエリーは、探索の特徴ベクトルを生成するために使用される筆跡モデルとは異なる筆跡モデルを使用して筆跡から生成される。
【００１９】
本発明の更に広い形態によれば、クエリーを用いてデジタル・インク・データベースを探索する装置が提供される。この装置は、
デジタル・インク・データベースを記憶するストレージと、
辞典の探索を実行し、テキスト・クエリーを生成するために結合できる字句シーケンスを含む辞典エントリーのシーケンスを決定し、
辞典エントリーのシーケンスに対応する特徴ベクトルのセットを取得し、
特徴ベクトルのセットを使用してデジタル・インク・データベースを探索するように構成された
プロセッサと、を備え、
辞典は、手書き文字認識の結果を使用してデジタル・インク・データベースの作成者から取得された筆跡モデルの一部分である。
【本発明を実施する形態】
【００２０】
本発明は、添付の図面と関連づけて記述される本発明の好ましいが非限定的な実施形態の以下の説明から明らかになるであろう。この説明は、単なる例として示されている。
【００２１】
次の形態は、本発明の主題の正確な理解を提供するため、書かれた説明および添付のクレイムに適用されるものとして記述される。
【Ｉ．好ましい実施形態】
【００２２】
本発明は、テキスト・クエリーを使用してデジタル・インク・データベースを探索する方法および装置を提供する。本発明の特徴を示すために組み込まれた図面において、図面の全体にわたって同様の部分を識別するため、同様の参照符号が使用される。
【００２３】
本発明の実施形態は、処理システムを使用して実現することができる。処理システムの１つの例が図１に示される。具体的には、図示されるように、処理システム１０は、一般的に、少なくともバス２４を介して相互に結合されたプロセッサ２０、メモリ２１、入力デバイス２２、例えばグラフィックス・タブレットおよび／またはキーボード、出力デバイス２３、例えばディスプレイを含む。処理システムをデジタル・インク・データベース１１へ結合するため、２５で示されるような外部インタフェースも設けられる。
【００２４】
使用に当たって、処理システム１０は、データが、デジタル・インク・データベース１１の中に記憶され、および／またはそこから検索されるように構成させる。プロセッサ２０は、入力２２を介して手書きデータ、テキスト・クエリー等を受け取る。これにより、処理システム１０は任意の形式の処理システムまたは端末、例えばコンピュータ、ラップトップ、サーバ、特殊のハードウェア等であってよいことが分かるであろう。
【筆跡のモデル化】
【００２５】
書き手特有の筆跡モデルは、特定のユーザの手書きスタイルを記述する。ほとんどのユーザ適合手書き文字認識システムは、個々のユーザのスタイル変化に対処するある種のモデルを生成する。一般的に、これらの筆跡モデルの目的は、入力ペン・ストロークのセットから抽出された特徴ベクトルを、認識されたテキストを表す字句のセットへマップすることである。
【００２６】
しかしながら、デジタル・インクを探索する特徴合成アプローチは、書き手特有の筆跡モデルを使用して、逆マッピングを実行する。即ち、書き手がクエリー・テキストを手で書いたとしたら抽出されたであろう特徴を近似する特徴ベクトルのセットへクエリー・テキストを変換するため、モデルが使用される。図２は、手書きテキスト認識システムにおける一般的ステップの詳細を示す。筆跡は２６でサンプリングされ、生のインク２７が正規化ステップ２８へ渡される。正規化されたインク２９は、区分化ステップ３０を経て、結果のストローク３１は特徴抽出ステップ３２へ渡される。特徴抽出ステップ３２は特徴ベクトル３３を抽出する。次に、筆跡モデル３５を使用して、分類ステップ３４が実行される。このステップはプリミティブ３６を生成する。テキスト認識ステップ３７はプリミティブ３６を受け取り、言語モデル３８および／または筆跡モデル３５を使用して、生のインク２７に対応するテキスト３９を生成する。
【００２７】
特徴合成を使用してインク・データベースを探索するには、追加のステップが必要である。書き手特有の筆跡モデル３５は、テキストをインク特徴へマップする情報を記憶するように修正される必要がある。このマッピングを実行するため、個々の字句および字句グループ（即ち、字句のシーケンス）を特徴へ変換するテーブル（辞典と呼ばれる）が、筆跡モデルの中に含められる。認識が実行された後、出力テキストの中の字句および認識に使用された対応する特徴ベクトルを辞典へ追加することができる。
【００２８】
通常一緒に起こる字句のグループおよび対応する特徴ベクトルは、連結されて辞典へ追加される。これが望ましい理由は、手書きが共結合効果を示し（字句を書く時、前後の字句の形状によって影響される）、よく書かれる字句（例えば、「ｑｕ」、「ｅｄ」、および「ｉｎｇ」）は、共結合を示しやすいからである。字句グループの特徴ベクトルを記憶することによって、ストローク・シーケンスの文脈的効果を考慮したクエリー・インクのより正確なレンダリングを生成することができる。
【００２９】
辞典は、各々の字句シーケンスについて複数の特徴ベクトルを記憶できなければならない。同じ字句が何回も認識され得るから、辞典は、字句を最良に表す特徴ベクトルを選択できなければならない。これは、各々の字句シーケンスについて認識器から出力された全ての特徴ベクトル・シーケンスを、その特徴ベクトル・シーケンスがその字句シーケンスについて発見された回数のカウントと一緒に記憶することによって可能となる。字句シーケンスについて最高のカウント（即ち、発見の頻度が最も高く、したがって最も蓋然的な）特徴ベクトル・シーケンスが、特徴合成の間に使用される。
【００３０】
どの字句グループを記憶するかの選択は、文字遷移統計（例えば、テキスト・コーパスから引き出される）に基づかせることができる。その場合、高い発生確率を有する字句シーケンスが記憶される（例えば、「ｉｎｇ」の確率は「ｉｎｘ」の確率よりも、はるかに大きい）。あるいは、認識の後で全ての可能な字句グループを記憶し、テーブルがあまりに大きくなった時、ある種の選択手順（例えば、最小近時使用）を実行することができる。
【００３１】
辞典の中でワードの終わりを明示的にモデル化することによって、更なる改善を達成することができる。多くの筆記スタイルとして、文字はワードの終わりで不完全に書かれる。これは、特に、手で書かれるワードの接尾辞、例えば「ｉｎｇ」、「ｅｒ」、および「ｅｄ」において明らかである。この行動をモデル化するため、ワード終了文字が字句シーケンスへ付加され（例えば、「ｉｎｇ＃」）、この字句シーケンスがワードの終わりをモデル化することを示す。特徴合成の間、これらのエントリーは、クエリー・ワードを完了するためにのみ使用することができる。
【特徴合成】
【００３２】
デジタル・インク・データベースを探索するため、テキスト・クエリーは、書き手特有の筆跡モデルを使用する特徴合成手順によって、特徴ベクトルのセットへ変換される。次に、これらの特徴ベクトルは、デジタル・インク・データベースを探索するためのクエリータームとして使用される。インク・データベースの探索は、従来のインク・マッチング手法を使用して実行することができる。図３は、この手順を説明している。ステップ４０で、テキストが入力され、テキスト４１は特徴合成ステップ４２へ提供されて、特徴合成ステップ４２は筆跡モデル３５を使用して特徴４３を生成する。特徴４３は、デジタル・インク・データベース１１のインク探索ステップ４４で使用される。これはインク・マッチ４５を生成する。
【００３３】
特徴合成を実行するため、辞典の探索が実行され、結合されてクエリー・テキストを生成できる字句シーケンスを含む辞典エントリーのシーケンスが突き止められる。記憶された特徴ベクトルは、クエリー特徴ベクトルを生成するために連結される。しかしながら、クエリー・テキストを作り出すために使用できる辞典エントリーの異なった組み合わせが多数存在するかも知れない。テキストを生成できる最小数のエントリーが、文脈的効果を最も正確にモデル化するものと仮定する。例えば、次のエントリーが辞典の中に存在すると仮定する。
【００３４】
【表１】
したがって、ワード「ｂｏｒｒｏｗｅｄ」は（ｂｏ）（ｒｒ）（ｏｗ）（ｅｄ）、（ｂｏｒｒ）（ｏｗ）（ｅｄ）、または（ｂｏｒ）（ｒｏｗｅｄ）として作り出すことができ、最後の構成が最も望ましい。なぜなら、最も少ない要素から構成されているからである。
【Ａ＊辞典の探索】
【００３５】
正確な結果を得るため、辞典は非常に大きいことを期待され、ワードに対する辞典エントリーの潜在的組み合わせの数は指数的であろう。長いワードを含むクエリーの場合、全ての順列の完全な列挙は実際的でないかも知れない。字句シーケンスsを探索するために、修正されたＡ＊探索アルゴリズムを使用することができる。Ｓ．Ｒｕｓｓｅｌｌ及び Ｐ．Ｎｏｒｖｉｇ，Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ−Ａ Ｍｏｄｅｒｎ Ａｐｐｒｏａｃｈ，Ｐｒｅｎｔｉｃｅ Ｈａｌｌ，１９９５年、を参照されたい。その場合、パス・コスト関数ｇ（ｓ）は、テキストを作り出すまでに使用された辞典エントリーの数であり、目標までの推定コストは、
ｈ（ｓ）＝１、長さ（ｓ）＜長さ（クエリー）の場合
＝０、他の場合
この発見的方法は、シーケンスがクエリー・ワードよりも少ない字句を有するならば、字句シーケンスを完了するのに少なくとも１つの追加的辞典エントリーが必要であることを記述している。探索ツリーの中のノードは、ｇ（ｓ）＋ｈ（ｓ）によってソートされ（低い得点が優先する）、同じ得点を有するノードはシーケンスにおける字句の数によって順序を決められる（多いものが優先する）。
【００３６】
注意すべきは、ｈ（ｓ）が単調で適格な発見的手法であり（即ち、それは決して目標へ到達するコストを過大に推定しない）、したがって探索は最適解の発見を保証され、最適に効率的である（即ち、最適解を発見することのできる最小数のノードを拡張する）。この結果の証明は、Ｒ．Ｄｅｃｈｔｅｒ及び Ｊ．Ｐｅａｒｌによる“Ｇｅｎｅｒａｌｉｚｅｄ Ｂｅｓｔ−Ｆｉｒｓｔ Ｓｅａｒｃｈ Ｓｔｒａｔｅｇｉｅｓ ａｎｄ ｔｈｅ Ｏｐｔｉｍａｌｉｔｙ ｏｆ Ａ＊”，Ｊｏｕｒｎａｌｏｆ ｔｈｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔｉｎｇ Ｍａｃｈｉｎｅｒｙ，３２（３），５０５〜５３６頁，１９８５年、に示されている。
【００３７】
上記の手順の例として、ワード「ｂｏｒｒｏｗｅｄ」の探索が以下に示されている。テーブルの中の各々の行は探索ノードを表し、より高い得点のノードはテーブルの最上部に置かれる。
【００３８】
【表２】
テーブルの最上部にある最も有望なノードが拡張されて、次の結果になる。
【００３９】
【表３】
再び、最も有望なノードが拡張される。
【００４０】
【表４】
最上部のノードが、現在、完了したシーケンスであり、探索中の他のノードは、より良い得点を生成することができず、したがって、このノードが探索結果として選択される。
【ＩＩ．様々な実施形態】
【００４１】
[IIＡ．手書き文字認識を伴わない特徴合成]
特徴合成を使用するインク探索は、手書き文字認識システムを使用しないで実行することができる。この手法は、字句シーケンスおよび関連する特徴ベクトルの辞典を構築して、デジタル・インク・データベースを作成した書き手の筆跡をモデル化する能力を必要とするだけである。
【００４２】
手書き文字認識の結果が、モデル化に利用できなければ、トレーニング手順を使用して、書き手特有の辞典を生成することができる。これを行うため、ユーザは、特定のトレーニング・テキストをコピーすることによって筆跡のサンプルを提供し、次に、このサンプルが辞典を構築するために使用される。トレーニング手順は、完全な手書き文字認識を実行するためには必要でない。なぜなら、筆跡によって表されるテキストは、既に知られているからである。それは、単に、入力を文字およびストロークへ区分化し、ストロークを特徴へ変換し、適切な字句グループおよび関連した特徴ベクトルを辞典の中に記憶するために必要である。
【００４３】
辞典を構築するために使用されるトレーニング・テキストは、個々の字句および字句グループの均衡した例示的セットを提供するように最適化される必要がある。即ち、それは、類似した文字のユニグラム、バイグラム、およびトライグラムの範囲を最大にする必要がある。これに関しては、最も遭遇する可能性が高い字句および字句シーケンスに重点を置いている、Ｊ．Ｐｉｔｒｅｌｌｉ，Ｊ．Ｓｕｂｒａｈｍｏｎｉａ， Ｍ．Ｐｅｒｒｏｎｅ 及び Ｋ．Ｎａｔｈａｎによる“Ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ Ｔｒａｉｎｉｎｇ Ｔｅｘｔｓ ｆｏｒ Ｗｒｉｔｅｒ−ＤｅｐｅｎｄｅｎｔＨａｎｄｗｒｉｔｉｎｇ Ｒｅｃｏｇｎｉｔｉｏｎ”，Ａｄｖａｎｃｅｓ ｉｎ Ｈａｎｄｗｒｉｔｉｎｇ Ｒｅｃｏｇｎｉｔｉｏｎ，Ｗｏｒｌｄ Ｓｃｉｅｎｔｉｆｉｃ Ｐｕｂｌｉｓｈｉｎｇ，１９９９年、を参照されたい。
【００４４】
[IIＢ．認識およびインク・マッチングの異なった特徴]
手書き文字認識システムおよびインク・マッチング・アルゴリズムの双方が同じ特徴表現を使用することが望ましい。なぜなら、デジタル・インク・データベースを探索するために使用される特徴は、手書き文字認識の結果から引き出されるからである。
【００４５】
しかしながら、認識特徴を探索特徴へ変換できれば、認識と探索に対して異なった特徴セットを使用することができる。幾つかの特徴セットは、認識特徴から、トレーニング・データのセットから学習される探索特徴への変換を可能にする。
【００４６】
あるいは、多くの特徴セットは、認識特徴からデジタル・インクの近似を再生成することを可能にし、その近似から第２の特徴セットを抽出することができる。即ち、テキスト・クエリーは、特徴合成を使用して特徴ベクトルのセットへ変換され、特徴抽出プロセスの逆変換が特徴へ適用されて、それらをデジタル・インクへ変換し、そのデジタル・インクから探索特徴が抽出される。この手順が、探索特徴の抽出に影響を与えるアーチファクトをデジタル・インクへ決して導入しないように注意しなければならない（例えば、生成されたインクの不連続は、幾つかの特徴抽出手法で問題を生じるかもしれない）。
【００４７】
[IIＣ．第三者のインク探索]
手書き文字認識を使用してインク入力をテキストへ変換し、特徴合成を用いて認識されたテキストをインク探索の特徴へ変換することによって、他の書き手のデジタル・インク・データベースを探索することができる。
【００４８】
図４はこの状況を示し、書き手Ａによって作成されたデジタル・インク・データベースを書き手Ｂが探索する。ステップ４６で、インクが書き手Ｂから受け取られ、ストローク４７が特徴抽出ステップ４８へ渡される。特徴４９が抽出され、認識ステップ５０は言語モデル５１および書き手Ｂのモデル５２を使用して、対応するテキスト５３を生成する。これは、辞典構築ステップ５４で書き手Ｂの辞典を構築するために使用される。字句グループおよび特徴が書き手Ｂのモデル５２へ戻され、モデルを改善／更新する。次に、テキスト５３は特徴合成ステップ４２を経験し、図３を参照して説明した類似のプロセスが実行されて、書き手Ａによって作成されたインク・マッチ４５が検索される。
【ＩＩＩ．更なる例】
【００４９】
次の例は、本発明の一実施形態の更に詳細なアウトラインを提供する。この例は、単なる例として意図され、本発明の範囲を限定するものではない。
【００５０】
このセクションは、特徴合成を使用したインク・データベース探索の実現を詳細に説明する。ワードおよび文字の区分化、および基線方向の正規化を含む多数の前処理ステップが実行されたものと仮定する。これは単に手法を実現する１つの可能な方法であり、プロセスの各々の段階で利用可能な代替方法が存在することに注意されたい。例えば、使用できる多くの異なった区分化スキーム、特徴セット、筆跡モデル、および認識手順が存在する。
【００５１】
特徴合成を使用する手書き文字認識およびインク探索手順は、トレーニング段階および認識または探索段階を必要とする。トレーニング段階の間に、トレーニング・データのセットはストローク特徴へ変換され、ストローク特徴はストローク・プリミティブへ集団化されて筆跡のモデルを作り出すために使用される。認識およびインク探索のために、このモデルは、入力インクをデコードするかインク探索の特徴を合成するために使用される。このプロセスは図５で示される。同じ前処理、正規化、区分化、および特徴抽出手順が、トレーニング、認識、および探索に使用されることに注意されたい。
【００５２】
手書き文字認識システムは、入力インクをストローク・コードワードのセットへマップする。このストローク・コードワードは、マッチするワードを辞典から探索するために使用される。図６は、このプロセスの概略を提供し、個々のステップは以下で詳細に説明される。
【平滑化】
【００５３】
インクは１００Ｈｚの一定レートでサンプリングされる。研究によれば、筆跡は約５Ｈｚでピーク・スペクトル密度を有し、これは約１０Ｈｚでノイズ・レベルへ降下する。Ｈ．Ｔｅｕｌｉｎｇｓ及び Ｆ．Ｍａａｒｓｅによる“Ｄｉｇｉｔａｌ Ｒｅｃｏｒｄｉｎｇ ａｎｄ Ｐｒｏｃｅｓｓｉｎｇ ｏｆ Ｈａｎｄｗｒｉｔｉｎｇ Ｍｏｖｅｍｅｎｔｓ”，ＨｕｍａｎＭｏｖｅｍｅｎｔ Ｓｃｉｅｎｃｅ，３，１９３〜２１７頁，１９８４年、を参照されたい。よって、１０Ｈｚでカットオフを有する低域フィルタは、筆跡信号の関連スペクトル成分に影響を与えることなく高周波ノイズを除去するであろう。
【００５４】
上記の仕様に合致する低域フィルタは、点座標を円形にし、ＦＦＴを実行して高周波成分を除去し、逆ＦＦＴを使用して信号を再生することによって生成できる。しかしながら、簡単な加重平均フィルタも有効に働く。点｛ｐ１．．．ｐｎ｝のシーケンスを平滑化するため、
【００５５】
【数１】
ここで、
【００５６】
【数２】
フィルタの幅kおよびα平滑化係数は、経験的に決定される。
【傾斜補正】
【００５７】
多くの手書きスタイルは、書かれた字句の垂直主軸を有しない（即ち、字句は一貫した傾斜で書かれる）。筆跡傾斜を除去することは、手書き字句の認識を改善できる正規化である。手書きにおいて、ダウンストロークは最も安定および一貫したストロークと考えられ、したがって筆跡傾斜を検出するために有用である。
【００５８】
筆跡傾斜を検出するため、書かれたダウンストロークの点｛ｐ１．．．ｐｎ｝における加重平均方向が推定される。
【００５９】
【数３】
ここで、
【００６０】
【数４】
角度α１およびα２は、どのストローク・セグメントがダウンストロークの一部分として考えられるかを定義し、経験的にそれぞれ４０°および１４０°に設定される（９０°は垂直線を表す）。推定された傾斜が、垂直線からある閾値よりも大きく偏向すれば、傾斜は横ずれ変換を使用して除去される。
【００６１】
【数５】
ここで、ｙｍｉｎおよびｙｍａｘは、インクの境界長方形の最上部と最下部を表す。
【ゾーン推定】
【００６２】
ゾーン推定は、入力インクの高さを正規化するために使用される。英語の字句は３つのゾーン−中間ゾーン（字句、例えば「ａ」、「ｃ」、「ｅ」等の高さに対応する）、および字句、例えば「ｂ」、「ｄ」、「ｇ」、および「ｊ」のアセンダおよびデセンダを含む上方および下方ゾーンを示す。
【００６３】
ゾーン推定は、インク濃度の水平ヒストグラムを使用して実行される。即ち、インクの境界長方形を通過する等間隔の水平線の列について、インク交差の数が決定される。ヒストグラムの中央ピークが発見され、同じようにインク濃度が中央ピーク高のある分数よりも下へ降下するヒストグラムの両側の２つの点が発見される。これらの２つの点は、中間ゾーンの上方および下方境界として選択される。上方および下方ゾーンは、中間ゾーンと境界長方形の垂直極値との間の空間として画成される。
【特徴抽出】
【００６４】
インクは垂直方向の極値（即ち、Ｙ座標の極大および極小）でサブストロークへ区分化される。区分化が起こるためには、選択された区分化点でストロークを分割することによって生成された２つのサブストロークの長さが、前もって計算された最小距離（推定された中間ゾーンの高さの半分に設定される）を超えなければならない。
【００６５】
次に、区分化されたサブストロークは、ストローク軌道に沿って等間隔に置かれた定数のｎ個の点を含むように再サンプリングされる。次に、座標を正規化することによって、特徴ベクトルがサブストロークのために作り出される。
【００６６】
【数６】
【００６７】
【数７】
ここで、
ｘｍｉｎ＝ブストローク境界長方形のＸ最小値、
ｙｍｉｄｄｌｅ＝中間ゾーンの最上部のＹ座標、
ｈ＝中間ゾーンの高さ（即ち、ｙｂａｓｅ−ｙｍｉｄｄｌｅ）。
【００６８】
次に、特徴ベクトルが、正規化された座標からｆｉ＝｛ｘ’１，ｙ’１，．．．，ｘ’ｎ，ｙ’ｎ｝として作り出される。
【特徴の縮減】
【００６９】
結果のベクトルは、多数の高度に相関した特徴を使用してサブストロークを記述する（明らかに、点ｐｉの座標は、点ｐｉ−１に依存する。以下同様である）。ベクトルの次元をｍへ下げるため（ここでｍ＜２ｎ）、カルーネン・レーベ（Ｋａｒｈｕｎｅｎ−Ｌｏｅｖｅ）変換が使用される（「主成分分析」（ＰｒｉｎｃｉｐａｌＣｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ−Ｒ．Ｄｕｄａ，Ｐ．Ｈａｒｔ，ａｎｄ Ｄ．Ｓｔｏｒｋ，Ｐａｔｔｅｒｎ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ，Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ，ＪｏｈｎＷｉｌｅｙ＆Ｓｏｎｓ，Ｉｎｃ．，５６９〜５７０頁，２００１年）を参照）。この手順は、最小自乗の意味で最適のリニアマッピングを使用して、高次元の特徴を低次元へ投影する。
【００７０】
これを行うため、全てのトレーニング特徴ベクトルＸ＝｛ｆ１，．．．，ｆｎ｝のセットについて、次式を使用した共分散（自己相関）マトリックスが計算される。
【００７１】
【数８】
このマトリックスの固有ベクトルおよび固有値が発見され（三重対角ＱＬ陰アルゴリズムを使用する。Ｗ．Ｐｒｅｓｓ，Ｂ．Ｆｌａｎｎｅｒｙ，Ｓ．Ｔｅｕｋｏｌｓｋｙ 及びＷ．Ｖｅｔｔｅｒｌｉｎｇによる Ｗ．Ｔ．，Ｎｕｍｅｒｉｃａｌ Ｒｅｃｉｐｅｓ ｉｎ Ｃ，Ｃａｍｂｒｉｄｇｅ：Ｃａｍｂｒｉｄｇｅ Ｕｎｉｖｅｒｓｉｔｙ Ｐｒｅｓｓ，１９８８年）を参照）、ＰＣＡマトリックスＺを形成するため、最大ｎ個の固有値に対応する固有ベクトルが使用される。次に、特徴ベクトルは、このマトリックスと乗算され、直交無相関軸を有する新しい特徴空間へ特徴ベクトルを変換する。
【００７２】
【数９】
【ベクトルの量子化】
【００７３】
次に、変換された特徴ベクトルは、コホーネン（Ｋｏｈｏｎｅｎ）自己組織化特徴マップ（ＳＯＦＭ（Ｓｅｌｆ−Ｏｒｇａｎｉｚｉｎｇ Ｆｅａｔｕｒｅ Ｍａｐ））を使用して集団化される。Ｔ．Ｋｏｈｏｎｅｎによる“Ｓｅｌｆ−ＯｒｇａｎｉｚｅｄＦｏｒｍａｔｉｏｎ ｏｆ Ｔｏｐｏｌｏｇｉｃａｌｌｙ Ｃｏｒｒｅｃｔ Ｆｅａｔｕｒｅ Ｍａｐｓ”，Ｂｉｏｌｏｇｉｃａｌ Ｃｙｂｅｒｎｅｔｉｃｓ，４３，５９〜６９頁，１９８２年、を参照されたい。この手法は、監督されない学習手順を使用して入力ベクトルを集団化し、ベクトル間の距離および近接関係ができるだけ遠く維持されるようにする。使用されるＳＯＦＭは２次元構造を有し、可視的に類似したコードワード（即ち、クラスタ）は相互に近づけて置かれる。その結果、２つのコードワード間の距離は、コードワード値の間のある距離計量（例えばユークリッド距離）を使用して容易に計算することができる。
【００７４】
ＳＯＦＭトレーニングは、ランダムな重みで開始される簡単な２層ニューラルネットワークを使用して反復的に実行される。正規化された入力トレーニング・ベクトルｘと最良にマッチする出力ニューロンは、最小ユークリッド距離を使用して発見される。
【００７５】
【数１０】
ここで、ｗｉは出力ノードｉの重みベクトルを表す。最高活動値を有するノードおよびそれを取り巻くノードの重み（近傍関数Λによって決定される）は、次式を使用して更新される。
【００７６】
【数１１】
ここで、ηは学習レート関数であり、ηおよびΛは、典型的には、時間tにわたって変化する。トレーニングは、トレーニング・セットの反復中にニューロン重みへの顕著な変化が存在しなくなるまで継続する。
【００７７】
サブストロークのシーケンスをコードワード・ベクトルへ変換するため、各々のサブストローク特徴ベクトルが、トレーニングされたＳＯＦＭを使用して量子化され、コードワード・ベクトルへ付加される。特徴ベクトルは、ＳＯＦＭコードブックの出力ニューロンに対する最大活動値を選択することによって、コードワードへ量子化される。
【００７８】
【数１２】
【筆跡モデル】
【００７９】
筆跡モデルは、ストローク・コードワード・ベクトルから字句へのマッピング（テキスト認識について）、および字句グループからコードワード・ベクトルへの逆マッピング（特徴合成について）を記憶する。筆跡モデルを構築するため、トレーニング・データにおける各々の字句はコードワード・ベクトルへ変換され、このコードワード・ベクトルは、対応する字句と一緒にテーブルの中に記憶される。
【００８０】
特定のコードワード・シーケンスは多数の字句へマップし（例えば、不完全に書かれた「ｕ」は「ｖ」と同じ特徴ベクトルへマップするかも知れない）、個々の字句は多数のコードワード・ベクトルによってマップされることに注意されたい。コードワード・ベクトルが特定の字句を表した回数のカウントを取ることによって、字句ｘｉについてｎ個の辞典エントリーがあれば、ベクトルが字句ｘｉを表す確率は、次のように計算することができる。
【００８１】
【数１３】
ここで、ｃｉは、コードワード・ベクトルが字句ｘｉを表すように遭遇された回数のカウントである。次のテーブルは、仮説のコードワード・ベクトル｛３，４｝を表すテーブルから取られた例示的エントリーである。
【００８２】
【表５】
このテーブルは、コードワード・シーケンス｛３，４｝が入力の中で遭遇されたならば、それが字句「ｕ」を表す確率が０．５４であり、それが「ｖ」を表す確率が０．４１であり、それが「ｒ」を表す確率が０．０５であることを示す。
【００８３】
逆マッピング・テーブルは同じようにして生成され、字句および字句グループに関連づけられたコードワード・ベクトルを記憶する。
【認識】
【００８４】
手書き文字認識を実行するためには、入力インクが前述したように処理され、結果のコードワード・ベクトルは、筆跡モデルを探索して字句仮説を生成するように使用される。派生字句の可能性が最も高いワードを辞典から探索するため、最良・第１探索ストラテジが使用される。プロセスは下記の図７で示される。
【インクの探索】
【００８５】
インクの探索は、手書き文字認識の間に生成された筆跡モデルを使用して、入力クエリー・テキストをコードワードのシーケンスへマップするように実行される。このコードワード・ベクトルは、弾力的マッチング手法を使用してデジタル・インク・データベースを探索するために使用される。類似のインク・マッチング手法の完全な説明は、Ｄ．Ｌｏｐｒｅｓｔｉ及び Ａ．Ｔｏｍｋｉｎｓによる“Ｔｅｍｐｏｒａｌ−Ｄｏｍａｉｎ Ｍａｔｃｈｉｎｇ ｏｆ Ｈａｎｄ−Ｄｒａｗｎ Ｐｉｃｔｏｒｉａｌ Ｑｕｅｒｉｅｓ”，Ｈａｎｄｗｒｉｔｉｎｇａｎｄ Ｄｒａｗｉｎｇ Ｒｅｓｅａｒｃｈ： Ｂａｓｉｃ ａｎｄ Ａｐｐｌｉｅｄ Ｉｓｓｕｅｓ，ＩＯＳ Ｐｒｅｓｓ，３８７〜４０１頁，１９９６年、に記載されている。次いで、結果のクエリーは類似性の順序に従って並べられ、ユーザに提供される。
【００８６】
このように、本発明に従って、テキスト・クエリーを使用してデジタル・インク・データベースを探索する方法および装置が提供された。この方法および装置は、前述した利点を満足させる。
【００８７】
本発明は、更に、個別的または集合的に本願の明細書で言及または指摘された部分、要素、および特徴にあり、これら部分、要素、または特徴の２つ以上の任意または全ての組み合わせにあると広く言うことができ、本発明が関連を有する技術で既知の同等物を有する特定の整数が言及されている場合は、そのような既知の同等物は、あたかも個々に記載されているかのように、ここに組み込まれていると考えられる。
【００８８】
好適な実施形態が詳細に説明されたが、これまで説明され、また特許請求の範囲に記載されるような本発明の範囲から逸脱することなく、当業者による様々な変更、置換、および代替が可能であることを理解すべきである。
【図面の簡単な説明】
【００８９】
【図１】処理システムを示す。
【図２】手書き文字認識方法の概観を示す。
【図３】特徴合成を使用するデジタル・インク・データベースの探索方法を示す。
【図４】第三者のインク・データベースの探索方法を示す。
【図５】トレーニングおよび認識／探索段階を示す。
【図６】手書き文字認識の方法を示す。
【図７】テキスト認識の例を示す。
【特許請求の範囲】
【請求項１】
手書きでないテキスト・クエリーと、手書き字句シーケンスを手書き特徴ベクトル・シーケンスに翻訳するテーブルとを用いて、手書き字句シーケンスのデジタルインクバージョンおよび前記手書き字句シーケンスの特徴ベクトル・シーケンスのデータベースを探索する方法において、前記データベースとテーブルにネットワークで接続された処理システムにより実施される、前記方法であって、
手書きでないテキスト・クエリーの手書きでない字句シーケンスを手書きの特徴ベクトル・シーケンスに変換するステップと、
前記テーブルを検索して、手書きでない前記字句シーケンスを生成する組み合わされた手書き字句シーケンスを決定するステップと、
前記テーブルから、決定された手書き字句シーケンスの組合せにより翻訳された手書き特徴ベクトル・シーケンスの組合せを出力するステップと、
出力された手書き特徴ベクトル・シーケンスの組合せに合致する手書き特徴ベクトル・シーケンスの組合せ用データベースを検索するステップと、
を含む、前記方法。
【請求項２】
前記データベースとテーブルの前記手書き字句シーケンスは、手書き認識を用いて生成された同一作成者のものである、請求項１に記載の方法。
【請求項３】
前記手書き認識は、
前記作成者の前記筆跡をサンプリングするステップと、
フィルタを使用して筆跡を平滑化するステップと、
傾斜補正を実行するステップと、
ゾーン推定アルゴリズムを使用して高さの正規化を実行するステップと、
特徴抽出を使用してサブストロークへの区分化および特徴ベクトルの生成を実行するステップと、
特徴ベクトルのセットの特徴縮減を使用するステップと、
ベクトル量子化を実行し、特徴ベクトルを集団化してコードワード・ベクトルを生成するステップと、
生成されたテキスト字句から最も可能性の高いワードを辞書から探索するステップと、
により前記処理システムが実行される、請求項２に記載の方法。
【請求項４】
前記テーブルは、各手書き字句シーケンスを複数の手書き特徴ベクトル・シーケンスに翻訳する、請求項１に記載の方法。
【請求項５】
前記テーブルは、ワードの終わりに対応する手書き字句シーケンスを示すワード終了文字を含む、請求項１に記載の方法。
【請求項６】
前記手書きでない字句シーケンスを生成する手書き字句シーケンスの２つ以上の組合せが決定される場合、前記変換するステップは：
手書き字句シーケンスの最小数を用いて前記手書きでない字句シーケンスを生成する手書き字句シーケンスの組合せを選択する工程と；
前記テーブルから、選択された前記手書き字句シーケンスの組合せにより翻訳された手書き特徴ベクトル・シーケンスの組合せを出力する工程と；
を含む、請求項１に記載の方法。
【請求項７】
前記手書きでないテキスト・クエリーは、前記処理システムのキーボードにより入力される、請求項１に記載の方法。
【請求項８】
前記手書きでないテキスト・クエリーは、音声認識を用いてテキストに変換される音声により入力される、請求項１に記載の方法。
【請求項９】
手書きでないテキスト・クエリーと、手書き字句シーケンスを手書き特徴ベクトル・シーケンスに翻訳するテーブルとを用いて、手書き字句シーケンスのデジタルインクバージョンおよび前記手書き字句シーケンスの特徴ベクトル・シーケンスのデータベースを探索するシステムであって、
前記システムは、前記データベースとテーブルを記憶する為のメモリと、プロセッサとを含み、前記プロセッサは、
前記テーブルを探索して、手書きでない前記字句シーケンスを生成する組み合わされた手書き字句シーケンスを決定し、
決定された前記手書き字句シーケンスの組合せにより翻訳された手書き特徴ベクトル・シーケンスの組合せを前記テーブルから出力することにより、手書きでないテキスト・クエリーの手書きでない字句シーケンスを手書き特徴ベクトル・シーケンスに変換すること、
出力された前記手書き特徴ベクトル・シーケンスに合致する手書き特徴ベクトル・シーケンスの組合せ用データベースを検索すること、
から構成されている、前記システム。
【請求項１】
手書きでないテキスト・クエリーと、手書き字句シーケンスを手書き特徴ベクトル・シーケンスに翻訳するテーブルとを用いて、手書き字句シーケンスのデジタルインクバージョンおよび前記手書き字句シーケンスの特徴ベクトル・シーケンスのデータベースを探索する方法において、前記データベースとテーブルにネットワークで接続された処理システムにより実施される、前記方法であって、
手書きでないテキスト・クエリーの手書きでない字句シーケンスを手書きの特徴ベクトル・シーケンスに変換するステップと、
前記テーブルを検索して、手書きでない前記字句シーケンスを生成する組み合わされた手書き字句シーケンスを決定するステップと、
前記テーブルから、決定された手書き字句シーケンスの組合せにより翻訳された手書き特徴ベクトル・シーケンスの組合せを出力するステップと、
出力された手書き特徴ベクトル・シーケンスの組合せに合致する手書き特徴ベクトル・シーケンスの組合せ用データベースを検索するステップと、
を含む、前記方法。
【請求項２】
前記データベースとテーブルの前記手書き字句シーケンスは、手書き認識を用いて生成された同一作成者のものである、請求項１に記載の方法。
【請求項３】
前記手書き認識は、
前記作成者の前記筆跡をサンプリングするステップと、
フィルタを使用して筆跡を平滑化するステップと、
傾斜補正を実行するステップと、
ゾーン推定アルゴリズムを使用して高さの正規化を実行するステップと、
特徴抽出を使用してサブストロークへの区分化および特徴ベクトルの生成を実行するステップと、
特徴ベクトルのセットの特徴縮減を使用するステップと、
ベクトル量子化を実行し、特徴ベクトルを集団化してコードワード・ベクトルを生成するステップと、
生成されたテキスト字句から最も可能性の高いワードを辞書から探索するステップと、
により前記処理システムが実行される、請求項２に記載の方法。
【請求項４】
前記テーブルは、各手書き字句シーケンスを複数の手書き特徴ベクトル・シーケンスに翻訳する、請求項１に記載の方法。
【請求項５】
前記テーブルは、ワードの終わりに対応する手書き字句シーケンスを示すワード終了文字を含む、請求項１に記載の方法。
【請求項６】
前記手書きでない字句シーケンスを生成する手書き字句シーケンスの２つ以上の組合せが決定される場合、前記変換するステップは：
手書き字句シーケンスの最小数を用いて前記手書きでない字句シーケンスを生成する手書き字句シーケンスの組合せを選択する工程と；
前記テーブルから、選択された前記手書き字句シーケンスの組合せにより翻訳された手書き特徴ベクトル・シーケンスの組合せを出力する工程と；
を含む、請求項１に記載の方法。
【請求項７】
前記手書きでないテキスト・クエリーは、前記処理システムのキーボードにより入力される、請求項１に記載の方法。
【請求項８】
前記手書きでないテキスト・クエリーは、音声認識を用いてテキストに変換される音声により入力される、請求項１に記載の方法。
【請求項９】
手書きでないテキスト・クエリーと、手書き字句シーケンスを手書き特徴ベクトル・シーケンスに翻訳するテーブルとを用いて、手書き字句シーケンスのデジタルインクバージョンおよび前記手書き字句シーケンスの特徴ベクトル・シーケンスのデータベースを探索するシステムであって、
前記システムは、前記データベースとテーブルを記憶する為のメモリと、プロセッサとを含み、前記プロセッサは、
前記テーブルを探索して、手書きでない前記字句シーケンスを生成する組み合わされた手書き字句シーケンスを決定し、
決定された前記手書き字句シーケンスの組合せにより翻訳された手書き特徴ベクトル・シーケンスの組合せを前記テーブルから出力することにより、手書きでないテキスト・クエリーの手書きでない字句シーケンスを手書き特徴ベクトル・シーケンスに変換すること、
出力された前記手書き特徴ベクトル・シーケンスに合致する手書き特徴ベクトル・シーケンスの組合せ用データベースを検索すること、
から構成されている、前記システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００８−２９３５１９（Ｐ２００８−２９３５１９Ａ）
【公開日】平成２０年１２月４日（２００８．１２．４）
【国際特許分類】
【出願番号】特願２００８−１７５８２１（Ｐ２００８−１７５８２１）
【出願日】平成２０年７月４日（２００８．７．４）
【分割の表示】特願２００３−５３６９３５（Ｐ２００３−５３６９３５）の分割
【原出願日】平成１４年１０月１５日（２００２．１０．１５）
【出願人】（３０３０２４６００）シルバーブルック リサーチ ピーティワイ リミテッド (150)
【Ｆターム（参考）】
【公開日】平成２０年１２月４日（２００８．１２．４）
【国際特許分類】
【出願日】平成２０年７月４日（２００８．７．４）
【分割の表示】特願２００３−５３６９３５（Ｐ２００３−５３６９３５）の分割
【原出願日】平成１４年１０月１５日（２００２．１０．１５）
【出願人】（３０３０２４６００）シルバーブルック リサーチ ピーティワイ リミテッド (150)
【Ｆターム（参考）】
[ Back to top ]