(57)【特許請求の範囲】
【請求項１】
コンピュータにおいてディジタルインクとして捕獲される手書きノートに対するインデックスを発生する方法であって、
前記方法は、
前記手書きノートから複数のインクワードを識別するステップと、
所定の閾値内でペアワイズ距離を有する少なくとも二つのインクワードを有する前記インクワードの少なくとも一つの等価クラスを発生するステップと、
前記等価クラスのインデックスワードの少なくとも一つを前記コンピュータ手書きノートに対するインデックス用語として選択するステップと、
前記インデックス用語が位置される前記手書きノートの位置への等価クラスの前記インデックス用語からのリンクを発生するために、選択された前記インデックス用語に対するインデックスを発生するステップと、
を備える手書きノート用インデックス発生方法。
【請求項２】
前記インクワードの少なくとも一つの等価クラスを発生する前記ステップは、
前記手書きノートの生データのストロークの時間距離と空間距離に基づいて、複数の特徴シーケンスを発生するステップと、
前記特徴シーケンスに基づいて、前記ペアのインクワードに対する前記ペアワイズ距離を発生するステップと、
前記ペアワイズ距離に基づいて前記インクワードを前記等価クラスにクラスタリングするステップと、
を備える請求項１に記載の方法。
【請求項３】
前記インクワードを前記等価クラスにクラスタリングする前記ステップは、
前記インクワードの各々を初期クラスタとして識別するステップと、
一つの単一のクラスタを発生するために、最も近接するペアワイズ距離よりなる二つのクラスタを選択するステップと、
最大ペアワイズ距離を定義するために閾値を選択するステップと、
一つの単一のクラスタを発生するために、前記最も近接するペアワイズ距離が前記閾値を超えるまで、最も近接するペアワイズ距離よりなる二つのクラスタを選択する前記ステップを繰り返すステップと、
を備える請求項２に記載の方法。
【請求項４】
閾値を選択する前記ステップは、
ペアワイズ距離と前記インクワードの複数のペアの発生回数との関係を表す分布カーブを発生するステップと、
前記分布カーブの急激な変化点τを識別するステップであって、前記分布カーブ全体に亘って、０から前記急激な変化点τまでの傾きの第１のラインと前記急激な変化点τから一定の傾きを有する第２のラインとに前記分布カーブを近似することによってなされるステップと、
前記閾値として、前記分布カーブの急激な変化点τによって近似された前記ペアワイズ距離を選択するステップと、
を備える請求項３に記載の方法。
【請求項５】
インデックス用語として前記等価クラスのインクワードの内の少なくとも一つを選択する前記ステップは、前記手書きノートの複数の場所に現れるが、該手書きノートの全体に亘って均一には現れないインデックス用語を選択するステップを備える、請求項１に記載の方法。
【請求項６】
前記手書きノートに対する前記インデックスを出力ディスプレイ上にディスプレイするステップをさらに備え、
インデックスを発生する前記ステップは、前記インデックス用語に対する前記手書きノートのページ番号を発生するステップを有し、
インデックスをディスプレイする前記ステップは、インデックス用語とともに前記ページ番号をディスプレイするステップを有する、
請求項１に記載の方法。
【請求項７】
コンピュータによって実行される時に、手書きノートから複数のインクワードを識別するステップと、
所定の閾値内でペアワイズ距離を有する少なくとも二つのインクワードを有する前記インクワードの少なくとも一つの等価クラスを発生するステップと、
インクワードの前記等価クラスの内の少なくとも一つを前記コンピュータ手書きノートに対するインデックス用語として選択するステップと、
前記インデックス用語が位置される前記手書きノートの位置への等価クラスの前記インデックス用語からのリンクを発生するために、選択された前記インデックス用語に対するインデックスを発生するステップと、
を前記コンピュータに実行させる複数の命令を備えるコンピュータリーダブル媒体。
【請求項８】
前記インクワードの少なくとも一つの等価クラスを発生する前記ステップは、
前記手書きノートの生データのストロークの時間距離と空間距離に基づいて、複数の特徴シーケンスを発生するステップと、
前記特徴シーケンスに基づいて、前記ペアのインクワードに対する前記ペアワイズ距離を発生するステップと、
前記ペアワイズ距離に基づいて前記インクワードを前記等価クラスにクラスタリングするステップと、
を備える請求項７に記載のコンピュータリーダブル媒体。
【請求項９】
前記インクワードを前記等価クラスにクラスタリングする前記ステップは、
前記インクワードの各々を初期クラスタとして識別するステップと、
単一のクラスタを発生するために、最も近接するペアワイズ距離よりなる二つのクラスタを選択するステップと、
最大ペアワイズ距離を定義するために閾値を選択するステップと、
単一のクラスタを発生するために、前記最も近接するペアワイズ距離が前記閾値を超えるまで、最も近接するペアワイズ距離よりなる二つのクラスタを選択する前記ステップを繰り返すステップと、
を備える請求項８に記載のコンピュータリーダブル媒体。
【請求項１０】
閾値を選択する前記ステップは、
ペアワイズ距離と前記インクワードの複数のペアの発生回数との関係を表す分布カーブを発生するステップと、
前記分布カーブの急激な変化点τを識別するステップであって、前記分布カーブ全体に亘って、０から前記急激な変化点τまでの傾きの第１のラインと前記急激な変化点τから一定の傾きを有する第２のラインとに前記分布カーブを近似することによってなされるステップと、
前記閾値として、前記分布カーブの急激な変化点τによって近似された前記ペアワイズ距離を選択するステップと、
を備える請求項９に記載のコンピュータリーダブル媒体。
【請求項１１】
インデックス用語として前記等価クラスのインデックスワードの内の少なくとも一つを選択する前記ステップは、前記手書きノートの複数の場所に現れるが、該手書きノートの全体に亘って均一には現れないインデックス用語を選択するステップを備える、請求項７に記載のコンピュータリーダブル媒体。
【請求項１２】
前記手書きノートに対する前記インデックスを出力ディスプレイ上にディスプレイするステップをさらに備え、
インデックスを発生する前記ステップは、前記インデックス用語に対する前記手書きノートのページ番号を発生するステップを有し、
インデックスをディスプレイする前記ステップは、インデックス用語と共に前記ページ番号をディスプレイするステップを有する、
請求項７に記載のコンピュータリーダブル媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ディジタルインクを捕獲するコンピュータシステムの分野に関し、より詳細には、手書きノートに対するインデックスの自動発生に関する。
【０００２】
【従来の技術】
パーソナルディジタルアシスタント（ＰＤＡ）を含む幾つかのコンピュータシステムによって、ユーザは、手書きのものをコンピュータに入力出来る。本質的に、これらのコンピュータ及びＰＤＡは、ユーザが手書きのものを表面に書き込むことが出来、手書きのものやノートは、連続的に”ディジタルインク”にサンプリングされる。これらのコンピュータシステムの一用途は、ユーザが電子ノート取りを出来ることである。
【０００３】
紙へのノート取りに比較して電子ノート取りの一潜在的利点は、電子ノート取りにおいて、インデックスを生成する能力である。一般に、インデックスは、手書きノート内で特定の情報を検出する手段を提供する。紙へのノート取りでは、このようなインデックスは、手作業で作られなければならない。この手作業は困難なために、紙へノートを取る者は、アンダーラインを引いたり、円で囲んだり、重要なものへ続くアステリスクを付けることによって重要な用語やキーワードをマークする傾向がある。このタイプのハイライティング（強調）は、ユーザが、ノートをブラウジングしながら重要な情報を検出するのを助けるが、インデックスを提供しない。
【０００４】
電子ドキュメントやテキストシステム（即ち、テキストがそのシステムによって経験的事実認識に基づいて認識される）において、自動”巻末”インデックス生成する技術がある（１９９８年の会報COMPUTERM，ACL  ColingのH.  Schutze氏の”The  Hypertext  Concordance:  A  Better  Back-Of-The-Book  Index”を参照のこと）。これらの巻末インデックスによって、ユーザは、インデックス中のキーワードリストを走査してそのテキスト中のインデックス用語の発生を検出出来る。いかしながら、これらの電子テキストシステムは、キーボードから等により、ユーザがテキストをそのシステムに直接入力することに基づく。
【０００５】
他の電子テキストシステムにおいて、情報検索技術がテキストドキュメントのインデックス付けを自動的に行うために使用される。例えば、一つのそのようなシステムにおいて、インデックス用語は、用語発生の相対頻度に基づいて、ウエブ（Web）ページに対して選択される（１９９８年の会報COMPUTERM，ACL  ColingのH.  Schutze氏の”The  Hypertext  Concordance:  A  Better  Back-Of-The-Book  Index”を参照のこと）。しかしながら、これらの技術は、ディジタルインク中のワードが経験的事実認識的に識別されないので、直接的にはディジタルインクへ適用しない。理論的には、文字認識を使用してディジタルインクをテキストへ変換する試みが行われてもよい。しかしながら、文字認識は、手書きでデータに関しては正確ではない。従って、文字認識を行うことなく、ディジタルインクとしてコンピュータへ入力された手書きデータから自動的にインデックスを発生することが望ましい。
【０００６】
ユーザの手作業によるインデックス付けは、テキストよりもディジタルインクを使用する電子システムにおいて可能である。一例は、FX  Palo  Alto  Laboratory  （ゼロックス社、パロアルト研究所）で開発され、Dynomite  System  （ダイノマイトシステム）によって提供されるような、及び  Marquis  （K.  Weber氏とA.  Poon氏のCHIN  94の”Marquis:  A  Tool  For  Real-Time  Video  Logging"を参照のこと）によって提供されるような、電子ノートのセクションへのキーワードの適用である。しかしながら、インデックスを発生するためにユーザが手作業でキーワードを識別することが必要であることは、ノートを取っている間中ユーザのその部分への認識努力を必要とする。
【０００７】
ユーザの手作業によるディジタルインクのインデックス付けに対する他の適用は、ダイノマイトシステムにおけるインク特性の発展に起因する。インク特性は、選択されたディジタルインクへ適用されるデータタイプであり、そのインクが連続的にタイプによって検索され得る。データタイプの例は、”名前（ｎａｍｅ）”や”すべき（ｔｏ  ｄｏ）”用語を含む。所与のインク特性に対するインクインデックスページは、ユーザによってその特性を含む全てのノートのすばやい走査を可能とするために生成される。更に、インデックスページ上のノートは、それらのノート内の元の位置へハイパーリンクされる。ディジタルインクシステムに対するインデックスを発生するためのキーワードとインク特性の両方の手作業によるアプローチに関連する一つの顕著な問題は、それらのアプローチにはユーザの大きな認識努力が必要である。その結果、これらの技術は、ユーザがそうするために一般に十分に訓練されていないために、実用的ではない。
【０００８】
歴史的手書きのドキュメント画像を手作業によるインデックス付けのためのシステムは、１９９６年ACM  Digital  LibrariesのR.  Manmatha氏、Chengfeng  Han氏、E.M.  Riseman氏、W.B.  Croft氏の”Indexing  Handwriting  Using  Word  Matching”に記述されている。この技術において、画像は、ワードにセグメント化し、ワード等価クラスがワード同士間のマッチスコアを閾値化することによって検出される。この技術は、ワード等価クラスを指定するためにユーザが手作業によるワード入力を必要とする。次に、インデックス用語が、最も大きなワード等価クラスから選択される。更に、ストップワードが手作業で削除される。手書きデータ上のストローク情報が利用されないので、マッチスコアがワード画像のみに基づいて演算される。従って、ユーザの努力無しに、手書きディジタルインクに対するインデックスを自動的に生成することが望ましい。
【０００９】
スクリブル（scribble）マッチングと呼ばれる技術が、CHI９５のA.  Poon氏、T.  Cass氏の”Scribbler:  A  Tool  For  Searching  Digital  Ink”に記述されている。一般に、スクリブルマッチングは、手書きドキュメントの所与のワードの発生回数を検出することを含む。この技術は、そのドキュメント中の所与の手書きワードとワード間のスコアを演算するためにダイナミックプログラミングを使用することに基づく。また、同様の方法は、１９９４年１２月のFourth  International  Workshop  on  Frontier  of  Handwriting  RecognitionのD.  Lopresti氏、A.  Tomkins氏の”On  The  Searchability  Of  Electronic  Ink"に記述されている。
【００１０】
【発明が解決しようとする課題】
以下に十分に記述されるように、本発明は、ディジタルインクのストロークに基づいて、手書きノートに対するインデックスを自動的に発生するシステムを提供することをその課題とする。
【００１１】
【課題を解決するための手段】
システムは、コンピュータにおいてディジタルインクとして捕獲される手書きノートに対するインデックスを自動的に発生する。このノートのワードに大まかに対応するインクワードが識別される。それらのインクワードの特徴が演算され、二つのインクワード間の特徴における距離を測定するペアワイズ距離又はマッチスコアが計算される。このペアワイズ距離に基づいて、インクワードの等価クラスがインクワードをクラスタリングすることから決定される。手書きノートに対するインデックスに現れるインデックス用語が、インクワードの等価クラスから選択される。このシステムは、インデックス用語が現れる手書きノート中の位置を識別するインデックス用語に対する位置情報を発生する。インデックス用語のインデックスがこの位置情報で表示される。一実施の形態において、ノートインデックスは、インデックス用語に続いて表示されるページ番号を含み、インデックス用語が現れる手書きノート中のページを識別する。他の実施の形態において、インデックスは、ハイパーリンクされたインデックス用語を含む。
【００１２】
システムは、手書きノート中のインデックス用語の等価クラスを識別する技術を含む。閾値は、インクワードのクラスタリングに対する最大ペアワイズ距離を識別するために発生される。具体的に、手書きノート中のインクワークの複数のペアの発生回数とペアワイズ距離との関係を表す分布カーブが発生される。分布カーブの急激な変化点（ｋｎｅｅ）τは、分布カーブ上のペアワイズ距離全体に亘って、０からτの傾きの第１のラインと急激な変化点τからの一定の傾きより成る第２のラインで近似される。分布カーブの急激な変化点τは、クラスタリングのための閾値として選択される。
次に、本発明の具体的態様を記述する。
第１の態様は、コンピュータにおいてディジタルインクとして捕獲される手書きノートに対するインデックスを発生するための方法であって、前記方法は、
コンピュータにおいてディジタルインクとして捕獲された手書きノートに対する生のデータのストロークを処理して、少なくとも一つのインクワードを有するインテックス用語として識別するステップと；
前記インデックス用語を前記インデックス用語が位置される前記手書きノートの位置へリンクすることによって前記インデックス用語に対するインデックスを発生するステップと、
前記手書きノートに対する前記インデックスを出力ディスプレイ上にディスプレイするステップと、
を備える。
第２の態様は、第１の態様において、インデックスを発生する前記ステップは、前記インデックス用語に対する前記手書きノートのページ番号を発生するステップを有し、
インデックスをディスプレイする前記ステップは、インテックス用語と共に前記ページ番号をディスプレイするステップを有する。
第３の態様は、第１の態様において、インデックスを発生する前記ステップは、前記インデックス用語を前記手書きノートの位置へリンクするためにハイパーリンクされたインデックス用語を発生するステップを有し、
インデックスをディスプレイする前記ステップは、ハイパーリンクされたテキストとしてインデックス用語をディスプレイするステップを有する。
第４の態様は、コンピュータにおいてディジタルインクとして捕獲される手書きノートに対するインデックスを発生する方法であって、前記方法は、
前記手書きノートから複数のインクワードを識別するステップと、
所定の閾値内でペアワイズ距離を有する少なくとも二つのインクワードを有する前記インクワードの少なくとも一つの等価クラスを発生するステップと、
前記等価クラスのインデックスワードの少なくとも一つを前記コンピュータ手書きノートに対するインデックス用語として選択するステップと、
前記インデックス用語が位置される前記手書きノートの位置への等価クラスの前記インデックス用語からのリンクを発生するために、選択された前記インデックス用語に対するインデックスを発生するステップと、
を備える。
第５の態様は、第４の態様において、前記インクワードの少なくとも一つの等価クラスを発生する前記ステップは、
前記手書きノートの生データのストロークの時間距離と空間距離に基づいて、複数の特徴シーケンスを発生するステップと、
前記特徴シーケンスに基づいて、前記ペアのインクワードに対する前記ペアワイズ距離を発生するステップと、
前記ペアワイズ距離に基づいて前記インクワードを前記等価クラスにクラスタリングするステップと、
を備える。
第６の態様は、第５の態様において、前記インクワードを前記等価クラスにクラスタリングする前記ステップは、
前記インクワードの各々を初期クラスタとして識別するステップと、
一つの単一のクラスタを発生するために、最も近接するペアワイズ距離よりなる二つのクラスタを選択するステップと、
最大ペアワイズ距離を定義するために閾値を選択するステップと、
一つの単一のクラスタを発生するために、前記最も近接するペアワイズ距離が前記閾値を超えるまで、最も近接するペアワイズ距離よりなる二つのクラスタを選択する前記ステップを繰り返すステップと、
を備える。
第７の態様は、第６の態様において、閾値を選択する前記ステップは、
ペアワイズ距離と前記インクワードの複数のペアの発生回数との関係を表す分布カーブを発生するステップと、
前記分布カーブの急激な変化点τを識別するステップであって、前記分布カーブ全体に亘って、０から前記急激な変化点τまでの傾きの第１のラインと前記急激な変化点τから一定の傾きを有する第２のラインとに前記分布カーブを近似することによってなされるステップと、
前記閾値として、前記分布カーブの急激な変化点τによって近似された前記ペアワイズ距離を選択するステップと、
を備える。
第８の態様は、第４の態様において、インデックス用語として前記等価クラスのインクワードの内の少なくとも一つを選択する前記ステップは、前記手書きノート全体に亘って、非均一に発生するインデックス用語を選択するステップを備える。
第９の態様は、コンピュータに入力された手書きノートのインクワードの等価クラスを識別する方法であって、前記方法は、
手書きノートから複数のインクワードを識別するステップと、
前記インクワードの複数の特徴を識別するステップと、
前記特徴に基づいて、前記インクワード間のペアワイズ距離を発生するステップと、
ペアワイズ距離と手書きノートの前記インクワードの複数のペアの発生回数との関係を表す分布カーブを発生するステップと、
前記分布カーブの急激な変化点τを識別するステップであって、前記分布カーブ全体に亘って、０から前記急激な変化点τまでの傾きの第１のラインと前記急激な変化点τから一定の傾きを有する第２のラインとに前記分布カーブを近似することによってなされるステップと、
クラスタリングするための閾値として、前記分布カーブの急激な変化点τによって近似された前記ペアワイズ距離を選択するステップと、
前記閾値のペアワイズ距離内で前記インクワードのクラスタを発生することによって前記インクワードの少なくとも一つの等価クラスを識別するステップと、
を備える。
第１０の態様は、コンピュータによって実行される時に、
コンピュータにおいてディジタルインクとして捕獲された手書きノートに対する生のデータのストロークを処理して、少なくとも一つのインクワードを有するインテックス用語を識別するステップと、
前記インデックス用語を前記インデックス用語が位置される前記手書きノートの位置へリンクすることによって前記インデックス用語に対するインデックスを発生するステップと、
前記手書きノートに対する前記インデックスを出力ディスプレイ上にディスプレイするステップと、
を前記コンピュータに実行させる複数の命令を備えるコンピュータリーダブル媒体である。
第１１の態様は、第１０の態様において、インデックスを発生する前記ステップは、前記インデックス用語に対する前記手書きノートのページ番号を発生するステップを有し、
インデックスをディスプレイする前記ステップは、インテックス用語と共に前記ページ番号をディスプレイするステップを有する。
第１２の態様は、第１０の態様において、インデックスを発生する前記ステップは、前記インデックス用語を前記手書きノートの位置へリンクするためにハイパーリンクされたインデックス用語を発生するステップを有し、
インデックスをディスプレイする前記ステップは、ハイパーリンクされたテキストとしてインデックス用語をディスプレイするステップを有する。
第１３の態様は、コンピュータによって実行される時に、
手書きノートから複数のインクワードを識別するステップと、
所定の閾値内でペアワイズ距離を有する少なくとも二つのインクワードを有する前記インクワードの少なくとも一つの等価クラスを発生するステップと、
インクワードの前記等価クラスの内の少なくとも一つを前記コンピュータ手書きノートに対するインデックス用語として選択するステップと、
前記インデックス用語が位置される前記手書きノートの位置への等価クラスの前記インデックス用語からのリンクを発生するために、選択された前記インデックス用語に対するインデックスを発生するステップと、
を前記コンピュータに実行させる複数の命令を備えるコンピュータリーダブル媒体である。
第１４の態様は、第１３の態様において、前記インクワードの少なくとも一つの等価クラスを発生する前記ステップは、
前記手書きノートの生データのストロークの時間距離と空間距離に基づいて、複数の特徴シーケンスを発生するステップと、
前記特徴シーケンスに基づいて、前記ペアのインクワードに対する前記ペアワイズ距離を発生するステップと、
前記ペアワイズ距離に基づいて前記インクワードを前記等価クラスにクラスタリングするステップと、
を備える。
第１５の態様は、第１４の態様において、前記インクワードを前記等価クラスにクラスタリングする前記ステップは、
前記インクワードの各々を初期クラスタとして識別するステップと、
単一のクラスタを発生するために、最も近接するペアワイズ距離よりなる二つのクラスタを選択するステップと、
最大ペアワイズ距離を定義するために閾値を選択するステップと、
単一のクラスタを発生するために、前記最も近接するペアワイズ距離が前記閾値を超えるまで、最も近接するペアワイズ距離よりなる二つのクラスタを選択する前記ステップを繰り返すステップと、
を備える。
第１６の態様は、第１５の態様において、閾値を選択する前記ステップは、
ペアワイズ距離と前記インクワードの複数のペアの発生回数との関係を表す分布カーブを発生するステップと、
前記分布カーブの急激な変化点τを識別するステップであって、前記分布カーブ全体に亘って、０から前記急激な変化点τまでの傾きの第１のラインと前記急激な変化点τから一定の傾きを有する第２のラインとに前記分布カーブを近似することによってなされるステップと、
前記閾値として、前記分布カーブの急激な変化点τによって近似された前記ペアワイズ距離を選択するステップと、
を備える。
第１７の態様は、第１３の態様において、インデックス用語として前記等価クラスのインデックスワードの内の少なくとも一つを選択する前記ステップは、前記手書きノート全体に亘って、非均一に発生するインデックス用語を選択するステップを備える。
第１８の態様は、コンピュータによって実行される時に、前記コンピュータに、
手書きノートから複数のインクワードを識別するステップと、
前記インクワードの複数の特徴を識別するステップと、
前記特徴に基づいて、前記インクワード間のペアワイズ距離を発生するステップと、
ペアワイズ距離と手書きノートの前記インクワードの複数のペアの発生回数との関係を表す分布カーブを発生するステップと、
前記分布カーブの急激な変化点τを識別するステップであって、前記分布カーブ全体に亘って、０から前記急激な変化点τまでの傾きの第１のラインと前記急激な変化点τから一定の傾きを有する第２のラインとに前記分布カーブを近似することによってなされるステップと、
クラスタリングするための閾値として、前記分布カーブの急激な変化点τによって近似された前記ペアワイズ距離を選択するステップと、
前記閾値のペアワイズ距離内で前記インクワードのクラスタを発生することによって前記インクワードの少なくとも一つの等価クラスを識別するステップと、
を実行させる複数の命令を備えるコンピュータリーダブル媒体である。
第１９の態様は、コンピュータであって、手書きノートから生のデータのストロークを受信するためのユーザ入力ペンベースデバイスと、
前記ユーザ入力ペンベースデバイスに連結され、各々が少なくとも一つのインクワードを有する複数のインデックス用語を識別するために、手書きノートに対する生データの前記ストロークを処理し、且つ前記インデックス用語を前記インデックス用語が位置する前記手書きノートの位置へリンクすることによって前記インデックス用語に対するインデックスを発生するためのプロセッサユニットと、
前記プロセッサユニットに連結され、前記手書きノートに対する前記インデックスをディスプレイするための出力ディスプレイと、を備える。
【００１３】
【発明の実施の形態】
システムの概略
図１は、手書きインクノートシステムの自動インデックス発生のための一実施の形態を示すブロック図である。好ましい実施の形態において、自動インデックス付けシステム１００は、パーソナルディジタルアシスタント（ＰＤＡ）のようなコンピュータで実施される。システム１００は、ＰＤＡ/コンピュータペンベースのインターフェース１１０を含む。ＰＤＡ/コンピュータペンベースのインターフェース１１０は、ユーザから手書きノートを受信し、ディジタルインクノート１２０を発生する。あらゆるタイプのペンベースのインターフェースがディジタルインクノート１２０を発生するために使用され得る。ディジタルインクノート１２０は、ユーザによってペンベースのインターフェース１１０上に発生されるジェスチャー及びストロークのディジタルバージョンを含む。
【００１４】
一般に、システム１００は、ディジタルインクノート１１０を処理してノートインデックス１３０を発生する。ノートインデックス１３０は、ディジタルインクノート１２０に対する、”インデックス用語”と呼ばれる用語を含むインデックスである。ノートインデックス１３０は、これらのインデックス用語が位置されるディジタルインクノート１２０中の位置にインデックス用語をリンクするための情報を提供する。この実施の形態において、ノートインデックス１３０を発生するために、システムは、インクワード処理部１４０、距離処理部１７０、階層クラスタ分析部１８０、閾値推定処理部１５０、インデックス用語選択処理部１９０、及びインデックス発生部１６０を含む。
【００１５】
図２は、手書きノートに対するインデックスを自動的に発生する一実施の形態を示すフロー図である。この実施の形態において、システム１１０（図１）は、ディジタルノート１２０に事前処理してノートインデックス１３０を発生する。具体的には、インクワードが識別される（図２のブロック２００及び図１のインクワード処理部１４０）。以下により詳細に記述されるように、ディジタルインクノート１２０中の実際のワードに略対応するインクワードは、時間的及び空間的グループ化に基づく。特徴がインクワードに対して演算される（図２のブロック２０５と図１のインクワード処理部１４０）。以下に十分に記述されるように、特徴は、各インクワード毎の生のデータのインクストロークの特徴を識別する。ダイナミックプログラミングは、インクワードのペアに対するペアワイズ距離又はマッチスコアを演算するために使用される（図２のブロック２１０と図１の距離処理部１７０）。一般に、ペアワイズ距離は、二つのインクワードワード間の特徴の距離を測定する。
【００１６】
図１と図２の実施の形態において、階層クラスタ分析がインクワードの等価クラスを識別するために実行される（図２のブロック２３０と図１の階層クラスタ分析部１８０）。一般に、インクワードの等価クラスは、同様な特徴を有するディジタルインクノート１２０からこれらのインクワードを定義する。大部分の事例では、同じ等価クラス中のインクワードは、同じワードであってもよい。しかしながら、他の事例では、ワード中に僅かな違いがあってもよい（例えば、”ｐｏｉｎｔｉｎｇ”と”ｐａｉｎｔｉｎｇ”は、図９に示されるように、同じ等価クラスにあってもよい）。階層クラスタ分析を効果的に適用して等価クラスを識別するために、閾値が演算される（図２のブロック２２０と図１の閾値推定処理部１５０）。閾値推定処理部１５０は、インクワードを等価クラスにクラスタリングするために使用される最大ペアワイズ距離を定義するために閾値を推定する。一般に、本発明の新規な閾値推定処理は、ディジタルインクノート１２０に対する対応するペアワイズ距離（即ち、マッチスコア）と発生回数との間の関係を描く分布カーブを発生し（例えば、図７参照）、この分布カーブの急激な変化点を閾値と推定する。この閾値を使用して、階層クラスタリング技術がインクワードの等価クラスを識別する（図２のブロック２３０と図１の階層クラスタ分析部１８０）。
【００１７】
インデックス用語が、インクワードの等価クラスから選択される（図２のブロック２４０と図１のインデックス用語選択処理部１９０）。一般に、インデックス用語処理部１９０は、ディジタルインクノート１２０におけるインクワードの分布が不均一である場合、インクワードの等価クラスを選択する。このように、ドキュメントの複数の場所に現れるがドキュメントの全体に亘って均一には現れない（例えば、その用語が全てのページには現れない）インデックス用語は、用語をインデックス付けするための最良の選択を行う。
【００１８】
ディジタルインクノート１２０は、選択されたインデックス用語を使用してインデックス付けされる（図２のブロック２５０と図１のインデックス発生部１６０）。ノートインデックスを発生するために、インデックス用語は、そのインデックス用語が現れるディジタルインクノート１２０中の位置を指す。例えば、一実施の形態において、各インデックス用語は、その用語が現れるディジタルインクノートのページを識別するためにラベル付けされる。また、インデックス用語は、その用語が現れるディジタルインクノートのページにハイパーリンクされる。他の実施の形態において、インデックス用語は、それらがノートページに現れると、肉太字体にされる。従って、ノートインデックス１３０によって、システムのユーザがディジタルインクノート１２０内のインデックス用語を容易に検出可能となる。
【００１９】
インクワード事前処理
一般に、インクワード再処理は、ディジタルインクノートの再サンプリング、再サンプリングされたディジタルインクノートのインクワードへの解析、インクワードに対する特徴シーケンスの発生、及びインクワードのペアに対するペアワイズ距離即ちマッチスコアの計算を含む。インクワードは、最初に生のデータインクストロークを”インクワード”にグループ化することによって解析される。インクワードは、ディジタルインクノート中のワードに大まかに対応する。これらのグループ化は、”インクワード”と呼ばれ、ノートの実際のワードからそれらを区別する。当該技術のおいて公知であるように、ディジタルインクノート１２０中のインクワードの各ストロークに対する生のデータは、時間に関して等しく分割された軌線上の一連のサンプリングされた点である。インクワード処理部１４０は、サンプル点が時間と空間距離に基づくように、ディジタルインクノート１２０のストロークを再サンプリングする。本発明の一実施の形態に従う再サンプリングの更なる説明は、参照により明白にここに組み込まれる、T.  Tenev氏、L.  Wilcox氏、T.  Cass氏の”A  System  And  Method  For  Recognizing  User  Specified  Pen-Based  Gestures  Using  Hidden  Markov  Models"と題する米国特許出願シリアル番号第０９／１２８，２５５を参照のこと。この再サンプリングは、距離処理部１７０の堅牢性を改良する。
【００２０】
インクワードに対する特徴は、再サンプリングされた点を使用して演算される。図３は、特徴シーケンスを識別するための座標を有する例示の再サンプリングされたインクワード”ｗｏｒｄ”を示す。この実施の形態に対して、演算された特徴は、
１）タンジェント角θn
２）現在のタンジェント角δθnの導関数
３）現在のタンジェント角δ2θnの２次導関数
４）タンジェント角ｓｉｎθnのｓｉｎ
５）タンジェント角ｃｏｓθnのｃｏｓｉｎ
再サンプリングされた点（Ｘn，Ｙn）に対するθnを測定するための基準角が図３に示される。各ストロークは、一つの特徴ベクトルシーケンスを生成する。一つのインクワードから成る、ストロークのグループにおける全ての特徴シーケンスは、共に結合されて各インクワードに対する単一の特徴シーケンスを生成する。本発明は、上述の特徴シーケンスを使用して記述されるが、インクワードの特徴を十分に記述するあらゆる特徴シーケンスが、本発明の精神及び範囲を逸脱することが無い限り、使用され得る。
【００２１】
インクワードに対するマッチスコア
ダイナミックプログラミングがインクワードのペアに対するマッチスコアを演算するために使用される。長さＭとＮの二つの特徴シーケンスが与えれれると、それらの間のスコアマッチングが、初期化ステップ、反復ステップ、終了ステップ、及びスコアマッチングステップで、以下のように演算される。
初期化
Φ（１，１）＝  ｜ｆ11−ｆ12｜2
ｆ11は、シーケンス lのｉ番目の要素を示し、｜ｆ11−ｆ12｜2は、ｗｏｒｄ１（ワード１）のｉ番目の位置とｗｏｒｄ２のｊ番目の位置の特徴ベクトル同士間のユークリッド距離である。
反復
【数１】
0003931519.tif 000002
ここで、ｋは、図４に示されるように、許容パスを示す。
（ακ，βκ）は、パスｋに対する一対の座標増分に対応する。οκは、パスｋのオフセットコスト値であり、ωκは、パスｋに対する重みである。
｛α1,α2,α3,α4,α5｝＝｛1,2,3,4,5｝
｛β1,β2,β3,β4,β5｝＝｛0,1,1,2,1｝
｛ο1,ο2,ο3,ο4,ο5｝＝｛1,0,0,0,1｝
｛ω1,ω2,ω3,ω4,ω5｝＝｛1,2,1,2,1｝
ｊ＝１又はｊ＝Ｎの時に、ｋ＝１が採用される。ｉ＝１又はｉ＝Ｍの時にｋ＝５が採用される。不適切なパスは削除される。例えば、ｉ＝２の時のｋ＝２である。
終了
【数２】
0003931519.tif 000003
スコアマッチング
マッチスコアは、長さによって正規化されたＤＰの最終マッチから演算される。
【数３】
0003931519.tif 000004
【００２２】
階層クラスタリング
閾値の推定の後、階層クラスタリングがインクワードに実行される（図２のブロック２２０と２３０）。図５は、ノートインデックスの自動発生に対する階層クラスタリングのための一実施の形態を示すフロー図である。一般に、閾値は、以下十分に議論されるように（図５のブロック５００と５１０）、発生回数とペアワイズ距離との間の関係に対する分布カーブの急激な変化点から推定される。初めに、階層クラスタリングのために、各インクワードは、クラスタとして識別される（図５のブロック５２０）。二つのクラスタ間の最短ペアワイズ距離（即ち、スコアマッチング）が計算される。例えば、最初に、クラスタは、最短ペアワイズ距離を有する二つのインクワードを含むように識別される。このように、この反復のために、これらの二つのインクワードが単一のクラスタを形成する。二つを越えるインクワードを含む二つのクラスタ間の距離を演算する時、ペアワイズ距離を計算するために、各々が異なるクラスタからの二つのインクワードの全ての組合せの平均距離が使用される。
【００２３】
識別された最短ペアワイズ距離が閾値と比較される（図５のブロック５４０）。最短ペアワイズ距離が閾値未満の場合、識別された最短ペアワイズ距離を有する二つのクラスタが新たなクラスタを発生するために組み合わされる（図５のブロック５５０）。クラスタを最短ペアワイズ距離と組合せる処理は、識別され得る最短ペアワイズ距離が閾値よりも大きくなるまで続けられる（図５のブロック５３０、５４０及び５５０）。識別された最短ペアワイズ距離が閾値よりも大きいと、クラスタ組合せ処理が停止し、インクワードの等価クラスがクラスタから識別される（図５のブロック５６０）。
【００２４】
図６は、階層クラスタリングの簡単化された例を示す図である。この例に対して、図６の”クラスタ（ｃｌｕｓｔｅｒ）２”とラベル付けされたクラスタは、最初、インクワード４と５を含む。次に、インクワード３は、”クラスタ２”を発生するために、インクワード４と５のクラスタと組み合わされる。インクワード１、７、８及び９より成るクラスタ３がクラスタアルゴリズムの３回の繰り返しで発生された。最初に、インクワード７と９は、一つのクラスタを形成するために組み合わされ、次に、インクワード８がインクワード７と９のクラスタと組み合わされて一つの新たなクラスタを形成した。最後に、インクワード１がインクワード７，８及び９のクラスタと組み合わされて”クラスタ３”を形成した。図６の例において、インクワード２とインクワード６に対応するクラスタ１とクラスタ４は夫々他の一つのインクワークと組み合わされなかった。一つの単一のインクワードのみを含むクラスタは、インクワードの等価クラスからインデックス用語を選択するために使用されない。
【００２５】
閾値推定
一実施の形態において、階層クラスタリングをストップするための閾値は、以下のように推定される。全てのインクワード間のペアワイズ距離が演算され、その距離がγによって量子化され、分布カーブが発生される。次に、カーブの急激な変化点τは、このカーブを、０からτの傾きの第１のラインとτ以降の一定の傾きの第２のラインとに近似することによって検出される。この近似は、ラインセグメントの各々に対して二乗誤差の和を最小にすることによってなされる。上述の手順は、二つのステップを有する。第１に、制約条件Ｓ＝Ｓ1+Ｓ2（０＜Ｓ1,０＜Ｓ2）下で、連続するＳ2を有する分布シーケンスＤ’の第１のＳ1値を使用してシーケンスＤを作る。
Ｄ＝｛ｄ1，ｄ2，．．．ｄS1｝
Ｄ’＝｛ｄ’1，ｄ’2，．．．ｄ’S2｝
第２に、カーブの急激な変化点、τ、は、以下の等式を最小化することによって検出される。
【数４】
0003931519.tif 000005
【数５】
0003931519.tif 000006
【数６】
0003931519.tif 000007
【数７】
0003931519.tif 000008
【００２６】
図７は、階層クラスタリングのための閾値を推定するための例示の分布カーブを示す。図７に示すように、垂直軸は、ディジタルインクノート中での発生回数を示し、水平軸は、インクワードのペア同士間のペアワイズ距離を示す。図７に示されるように、距離が増加すると（水平軸上を左から右に移動すると）、発生回数が実質的に増加し始める距離がある。二つのラインセグメントによって推定されるこの点は、閾値に対する推定を提供する。図７の例では、図７上の７１０と７２０とラベル付けされた二つのラインから成る。ライン７１０は、０からτまでの傾きの第１のラインを表し、ライン７２０は、τからτよりも大きな距離までの一定の傾きの第２のラインを表す。図７でτとラベル付けされたカーブの急激な変化点は、閾値の推定である。従って、閾値は、インクワードが同じ等価クラスに対して割り当てられる特徴シーケンス中の最大差や距離を表す。
インデックス用語選択
【００２７】
インクワードのクラスタが識別されると、インデックス用語が選択される。一つよりも多くの単一のインクワードを含むクラスタのみが潜在的なインデックス用語と考えられる。一般に、インデックス用語は、インデックスノート全体に亘って、不均一な分布を有する用語である。分布の不均一性の一つの尺度は、カイ二乗統計である。一実施の形態において、カイ二乗統計は、インデックス付けのために有用なインデックス用語を選択するために使用される。また、短いインクワードを含むクラスタは、それらの用語が”ストップワード（ｓｔｏｐ  ｗｏｒｄ）”である傾向があるので、削除される。
【００２８】
Ｌをノートページのトータル数とし、ｆiを用語がｉ番目のノートページに発生する回数とする。その用語の発生のトータル数は、ｆであり、そこで
【数８】
0003931519.tif 000009
【００２９】
その用語がノートページを介して均一に分布された場合、その用語が各ノートページで発生すると期待された回数は、ｆ／Ｌである。カイ二乗（ＣＨＩ−ｓｑｕａｒｅ）統計は、以下のように平均からの偏差を測定する。
【数９】
0003931519.tif 000010
【００３０】
インデックス用語を選択するために、ページ当りの用語数が指定される。一実施の形態において、ページ当り略３個の用語が適切である。次に、インデックス用語は、最大のカイ二乗値を有する３Ｌ用語として選択される。或いは、インデックス用語は、各ページ毎にピックアップされてもよい。この場合、ページ当りの用語数が指定され、そのカイ二乗は、上述と同じである（即ち、二つのノートページがあると仮定すると、当該ページと他の全てのページである）。この方法は、ページ当り一定数の用語を生成する利点がある。
【００３１】
ノートインデックス
図８は、太字でハイライトされたインデックス用語を有するノートページを示す。ノートページ中のハイライト化（強調）や太字化により、ユーザがノートページをブラウジングするのが容易となる。図８の例示のノートページに対するインデックス用語は、”Ｃｏｐｉｅｒ”、”Ｈｕｍａｎ”、”Ｌａｂ”、”Ｓｕｒｆａｃｅ”、及び”Ｍａｉｌｔｏ”である。図９は、太字でハイライトされたインデックス用語を有する第２のノートページを示す。この例では、インデックス用語は、”Ａｐｐｌｅ”、”Ｌｉｓａ”、及び”Ｄｒａｇ”である。
【００３２】
図１０は、本発明の一実施の形態に従って構成された手書きノートに対するインデックスを示す。この実施の形態では、各インデックス用語は、対応するインデックス用語が現れるページの識別番号（ＩＤ）でラベル付けされる。例えば、ページ番号４は、第１の等価クラスの第１の三つの事例”３−Ｄ”と関連付けられる。更に、インデックス用語は、元のノートページへハイパーリンクされる。これを達成するために、各インクワード毎に参照されてそのインクワードが現れた手書きノートのページ上のそのインクワードを識別する。また、これらの参照は、インデックス用語からノートページ上の対応する位置へのハイパーリンクを発生するために使用される。
【００３３】
この実施の形態に対して、インデックスの各ラインは、一つの等価クラスに対応する。例えば、省略形”３−Ｄ”は、そのノートの４個所で識別された。”３−Ｄ”の４つの事例は、一つの単一の等価クラスを構成する。図９は、本発明のインデックスをディスプレイするための一例を示しているが、本発明の精神と範囲から逸脱しない限り、あらゆるフォーマットが使用できる。
【００３４】
インクワードの等価クラスへの割り当ての用途
インクワードの等価クラスへの割り当ては、種々のディジタルインクベースのシステムへの用途を有する。例えば、インクワードの等価クラスへの識別は、概略化、抄録（抜粋）化、及び要旨化する用途を有する。また、手書きノートに対する自動インデックス発生は、注釈のために使用されるシンボルとワードの両方が解析されてインデックス形態で提示される注釈システムでの用途がある。また、インクワードを等価クラスへ割り当てる技術は、文字認識や画像コンテンツのデコーディングを行うことなくドキュメントの顕著な態様（アスペクト）を検出するための用途を有する。例えば、この技術は、意味的に顕著な画像を選択するためにワードとフレーズの頻度を決定して、ドキュメントについてのサマリーを発生するために使用され得る。
【００３５】
コンピュータ−パーソナルディジタルアシスタント
図１１は、本発明の手書きノートシステムの自動生成が実施され得る汎用コンピュータやパーソナルディジタルアシスタントの高レベルブロック図を示す。コンピュータシステム１０００は、プロセッサユニット１００５、主メモリ１０１０、及び相互接続バス１０２５を含む。プロセッサユニット１００５は、単一のマイクロプロセッサを含んでもよいし、マルチプロセッサシステムのようなコンピュータシステム１０００を構成するための複数のマイクロプロセッサを含んでもよい。主メモリ１０１０は、プロセッサユニット１００５によって実行するための命令とデータを部分的に格納する。主メモリ１０１０は、動作時に手書きノートシステムの自動生成のための実行可能コードを格納する。主メモリ１０１０は、高速キャッシュメモリと共にダイナミックランダムアクセスメモリ（ＤＲＡＭ）のバンクを含んでもよい。
【００３６】
更に、コンピュータシステム１０００は、マス（大容量）記憶デバイス（単数又は複数）１０２０、周辺デバイス（単数又は複数）１０３０、ポータブル記憶媒体ドライブ（単数又は複数）１０４０、入力制御デバイス（単数又は複数）１０７０、グラフィックサブシステム１０５０、及び出力ディスプレイ１０６０を含む。簡略化のため、コンピュータシステム１０００の全ての構成要素がバス１０２５を介して接続されているものとして図１１に示されている。しかしながら、コンピュータシステム１０００は、一つ又は複数のデータ搬送手段を介して接続されてもよい。例えば、プロセッサユニット１００５と主メモリ１０１０は、ローカルマイクロプロセッサバスを介して接続されてもよく、またマス記憶デバイス１０２０、周辺デバイス（単数又は複数）１０３０、ポータブル記憶媒体ドライブ（単数又は複数）１０４０及びグラフィックサブシステム１０５０は、一つ又は複数の入／出力（Ｉ／Ｏ）バスを介して接続されてもよい。磁気ディスクドライブや光学ディスクドライブで実施され得るマス記憶デバイス１０２０は、プロセッサユニット１００５による使用のためのデータと命令を格納するための不揮発性記憶デバイスである。ソフトウエアの実施の形態では、マス記憶デバイス１０２０は、主メモリ１０１０へロードするための手書きノートシステムソフトウエアの自動生成を格納する。
【００３７】
ポータブル記憶媒体ドライブ１０４０は、フロピーディスクやコンパクトディスク読出し専用メモリ（ＣＤ−ＲＯＭ）のようなポータブル不揮発性記憶媒体と共に動作し、データとコードをコンピュータへの入力及びそれからの出力を行う。一実施の形態において、手書きノートシステムソフトウエアの自動生成がそのようなポータブル媒体に格納され、ポータブル記憶媒体ドライブ１０４０を介してコンピュータシステム１０００へ入力される。周辺デバイス（単数又は複数）１０３０は、追加の機能性をコンピュータシステム１０００へ追加するために、入／出力（Ｉ／Ｏ）インターフェースのようなあらゆるタイプのコンピュータ支援デバイスを含んでもよい。例えば、周辺デバイス（単数又は複数）１０３０は、コンピュータシステム１０００をネットワークへインターフェースするためにネットワークインターフェースカードを含んでもよい。手書きノート（即ち、ディジタルインク）は、コンピュータシステムによる処理のためにポータブル記憶媒体やネットワークを介してコンピュータシステム１０００へ入力され得る。
【００３８】
入力制御デバイス（単数又は複数）１０７０は、コンピュータシステム１０００のユーザに対してユーザインターフェースの一部を提供する。入力制御デバイス（単数又は複数）１０７０は、英数字と他のキー情報を入力するための英数字キーパッド、マウス、トラックボール、スタイラスやカーソル方向キーのようなカーソル制御デバイスを含んでもよい。上述のように、コンピュータやＰＤＡは、ユーザから手書きノートを受け取るためのペンベースの入力デバイスを含む。テキスト及びグラフィック情報をディスプレイするために、コンピュータシステム１０００は、グラフィックスサブシステム１０５０と出力ディスプレイ１０６０を含む。出力ディスプレイ１０６０は、陰極線管（ＣＲＴ）や液晶ディスプレイ（ＬＣＤ）を含んでもよい。グラフィックスサブシステム１０５０は、テキストとグラフィック情報を受け取り、出力ディスプレイ１０６０への出力のためにその情報を処理する。コンピュータシステム１０００に含まれる構成要素は、汎用コンピュータシステムで一般的に見られる物であり、実際、これらの構成要素は、当該技術で公知であるそのようなコンピュータ構成要素の広いカテゴリーを表すことが意図される。
【００３９】
手書きノートシステムの自動生成は、ソフトウエアやハードウエアで実施され得る。ソフトウエア実施の場合、手書きノートシステムの自動生成は、汎用コンピュータシステムで実行されるための複数のコンピュータ実行可能命令を含むソフトウエアである。汎用コンピュータシステムへのローディングに先立って、手書きノートシステムソフトウエアの自動生成は、符号化された情報として、磁気フロピーディスク、磁気テープ及びコンパクトディスク読出し専用メモリ（ＣＤ−ＲＯＭ）のようなコンピュータ読出し可能媒体上に常駐してもよい。一つのハードウエア実施の場合、手書きノートシステムの自動生成は、ここで記述された機能を実施するためのプロセッサ命令を含む専用プロセッサを備えてもよい。また、回路が、ここで記述される機能を実施するために開発されてもよい。
【００４０】
本発明は、特定の例示の実施の形態に関して記述されたが、本発明の精神と範囲から逸脱しない限り、当業者は、種々の変更や代替えを提供できる。
【図面の簡単な説明】
【図１】手書きインクノートシステムの自動インデックス発生のための一実施の形態を示すブロック図である。
【図２】手書きノートに対するインデックスを自動的に発生するための一実施の形態を示すフロー図である。
【図３】特徴シーケンスを識別するための座標を有する例示の再サンプリングされたインクワード”ワード（ｗｏｒｄ）”を示す。
【図４】ダイナミックプログラミングのための許容パスを示す図である。
【図５】ノートインデックスの自動発生のための階層クラスタリングの一実施の形態を示すフロー図である。
【図６】階層クラスタリングの一例を示す図である。
【図７】階層クラスタリングのための閾値を推定するための例示の分散カーブである。
【図８】ボールド（太字）でハイライトされたインデックス用語を有するノートページを示す。
【図９】ボールドでハイライトされたインデックス用語を有する第２のノートページを示す。
【図１０】本発明の一実施の形態に従って構成された手書きノートに対するインデックスを示す。
【図１１】汎用コンピュータ又はパーソナルディジタルアシスタント（ＰＤＡ）のハイレベルブロック図である。
【図１】
0003931519.tif 000011
【図２】
0003931519.tif 000012
【図３】
0003931519.tif 000013
【図４】
0003931519.tif 000014
【図５】
0003931519.tif 000015
【図６】
0003931519.tif 000016
【図７】
0003931519.tif 000017
【図８】
0003931519.tif 000018
【図９】
0003931519.tif 000019
【図１０】
0003931519.tif 000020
【図１１】
0003931519.tif 000021