(57)【要約】【課題】  文書の画像を符号化し、その画像に基づいて位置を見つけるシステムおよび方法を提供すること。【解決手段】  文書ページを符号化して、その文書ページの様々な位置に関連付けられたコードにする。このコードを編成してコードブックにする（３０１）。次いで、取り込まれた画像を同様に符号化し（３０２，３０３）、コードブックのコードに照らしてサーチする（３０４）。１つまたは複数のコードとそれに関連付けられた位置を戻すことができ（３０５）、それにより取り込まれた画像の１つまたは複数の可能な位置を得る（３０６）。【選択図】  図３
2004153798.tif 000002
【特許請求の範囲】
【請求項１】
文書の画像を符号化する符号化システムであって、
前記文書の前記画像を受け取る入力と、
前記画像をサブイメージに解析するパーサ（parser）と、
前記サブイメージをコードに符号化するエンコーダと、
前記画像との関係で前記サブイメージの位置に関連付けた前記コードを格納するストレージと
を備えることを特徴とする符号化システム。
【請求項２】
前記エンコーダは、前記サブイメージの部分に基づいて符号化することを特徴とする請求項１に記載の符号化システム。
【請求項３】
前記エンコーダは、前記サブイメージの半径方向の分析に基づいて符号化することを特徴とする請求項１に記載の符号化システム。
【請求項４】
コードブックを作成するシステムであって、
画像のサブイメージに関連付けられたコードを受け取る入力と、
前記画像との関係で前記サブイメージの位置に関連付けられた前記コードを編成して前記コードブックにするプロセッサと、
前記コードブックを格納するストレージと
を備えることを特徴とするシステム。
【請求項５】
前記プロセッサは、前記コードを前記コードの線形リストに編成することを特徴とする請求項４に記載のコードブックを作成するシステム。
【請求項６】
前記プロセッサは前記コードを２分木に編成することを特徴とする請求項４に記載のコードブックを作成するシステム。
【請求項７】
前記２分木は、前記コードブックの重心からの前記コードの距離に基づいて前記コードを分離することを特徴とする請求項６に記載のコードブックを作成するシステム。
【請求項８】
前記２分木はさらに、前記コードブックのサブセクションの重心からの前記コードの距離に基づいて前記コードを分離することを特徴とする請求項７に記載のコードブックを作成するシステム。
【請求項９】
コードブックをサーチするシステムであって、
画像のサブイメージに関連付けられたコードと、前記画像の前記サブイメージの位置に関連する情報とを有するコードブックを受け取る第１の入力と、
ペンに付随するカメラから画像を受け取る第２の入力と、
前記カメラからの前記画像を符号化し、前記カメラ画像に関連付けられたコードを出力するエンコーダと、
前記カメラ画像に関連付けられた前記コードに類似する１つまたは複数のコード候補を求めて前記コードブックをサーチするプロセッサと、
前記１つまたは複数のコード候補に関連付けられた１つまたは複数の位置を出力する出力と
を備えることを特徴とするシステム。
【請求項１０】
文書画像からの情報を符号化する情報符号化方法であって、
前記文書画像を受け取るステップと、
前記文書をサブイメージに解析するステップと、
前記サブイメージに関連する情報をコードブックに追加するステップと
を含むことを特徴とする情報符号化方法。
【請求項１１】
前記サブイメージが前記文書画像のどこに位置するかに関連する位置情報に前記サブイメージを関連付けるステップをさらに含むことを特徴とする請求項１０に記載の情報符号化方法。
【請求項１２】
前記サブイメージの少なくとも１つを処理し、それにより前記サブイメージの前記１つについてより少ない情報を有するデータセットを作成するステップをさらに含むことを特徴とする請求項１０に記載の情報符号化方法。
【請求項１３】
前記サブイメージの少なくとも１つを半径方向の符号化によって処理するステップをさらに含むことを特徴とする請求項１０に記載の情報符号化方法。
【請求項１４】
前記サブイメージを画像処理するステップをさらに含むことを特徴とする請求項１０に記載の情報符号化方法。
【請求項１５】
コードブックを作成する方法であって、
サブイメージに関する符号化された情報を受け取るステップと、
前記サブイメージがより大きな画像中のどこに位置するかに関する位置情報を受け取るステップと、
前記符号化された情報を前記位置情報に関連付けるステップと、
前記関連付けた情報を前記コードブックとして格納するステップと
を含むことを特徴とする方法。
【請求項１６】
前記格納するステップはさらに、前記コードブックを線形リストとして格納するステップを含むことを特徴とする請求項１５に記載の方法。
【請求項１７】
前記格納するステップはさらに、前記コードブックを２分木として格納するステップを含むことを特徴とする請求項１５に記載の方法。
【請求項１８】
前記２分木に格納するために前記符号化された情報のサイズを縮小するステップをさらに含むことを特徴とする請求項１７に記載の方法。
【請求項１９】
前記符号化された情報の重心を見つけるステップと、
前記重心から最も遠い前記符号化された情報の第１のコードを見つけるステップと、
前記第１のコードから最も遠い前記符号化された情報の第２のコードを見つけるステップと、
前記符号化された情報を、前記第１のコードにより近い１つのデータセットと、前記第２のコードにより近いもう１つのデータセットの２つのデータセットに分離するステップと
をさらに含むことを特徴とする請求項１７に記載の方法。
【請求項２０】
バイナリが実現されるまで前記符号化された情報を分離することを通じて重心を見つけるステップを繰り返すステップをさらに含むことを特徴とする請求項１９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルペンを使用した紙との対話に関する。より詳細には、本発明は、デジタルペンによって紙の表面に付された注釈の位置を判定することに関する。
【背景技術】
【０００２】
コンピュータユーザは、パーソナルコンピュータと対話する一方式としてマウスとキーボードを使用することに慣れている。パーソナルコンピュータは、紙に書かれた文書を上回るいくつかの利点を提供するが、ユーザの大半は、一定の機能は引き続き印刷した紙を用いて行っている。そのような機能の一部には、紙に書かれた文書を読み、注釈を書き込むことがある。注釈の場合、印刷された文書は、ユーザによって付された注釈のためにより高い意義を持つ。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、印刷した文書に注釈を書き込むことに伴う問題の１つは、後にその注釈をその文書の電子形態に再度入力する必要性である。これを行うには、注釈を書き込んだユーザか別のユーザが注釈を読み取り、それをパーソナルコンピュータに入力することが必要となる。場合によっては、ユーザが注釈と元のテキストをスキャナで読み込むことにより新しい文書を作成する。こうした複数回のステップのために、印刷文書とその文書の電子バージョンとの対話を繰り返し扱うことが難しくなっている。さらに、スキャナで取り込んだ画像はしばしば修正することができない。元のテキストから注釈を分離する手段がない可能性がある。このため、注釈を使用することが難しくなっている。したがって、注釈を扱う改良された方式が必要とされる。
【課題を解決するための手段】
【０００４】
本発明の態様は、上述の問題の少なくとも１つに対する解決法を提供し、それにより認識された画像上の１つまたは複数の位置を判定することを可能にする。この位置を知ることにより、ユーザは、物理的な文書に注釈を書き込み、その注釈をその物理的文書の電子バージョンに関連付けることができる。本発明の態様の一部は、物理的な文書の符号化に使用される各種の技術に関連する。他の態様は、符号化された文書をサーチ可能な形態に編成することに関連する。
【０００５】
本発明のこれらおよびその他の態様は、以下の図面とそれに関連する説明を通じて明らかになろう。
【０００６】
前述の本発明の課題を解決するための手段と以下の好ましい実施形態の詳細な説明は、添付図面と併せて読むことにより一層理解される。図面は、本発明に関する限定ではなく、例として含める。
【発明を実施するための最良の形態】
【０００７】
本発明の態様は、取り込まれた画像の位置をより大きな画像との関係で判定することに関する。ここに記載する位置の判定方法およびシステムは、複数機能ペンと組み合わせて使用することができる。この複数機能ペンは、固定された文書に付された手書きの注釈を取り込み、固定された文書上の情報によりその注釈の位置を判定できるようにする能力を提供する。固定された文書は、印刷した文書であっても、コンピュータ画面上にレンダリングした文書であってもよい。
【０００８】
読者が本発明の各種態様を理解する助けとなるように以下の説明はいくつかのサブセクションに分ける。このサブセクションには、用語、汎用コンピュータ、取り込んだ画像の位置判定、符号化、コードブック生成、および候補サーチが含まれる。
【０００９】
用語
ペン−インクを貯蔵する能力を備えても、備えなくともよい任意の筆記用具。事例によっては、本発明の実施形態により、インクを貯蔵する能力を持たないスタイラスをペンとして使用することができる。
カメラ−画像取り込みシステム。
符号化−（物理的な紙の形態からスキャナで取り込むか、電子形態からレンダリングするか）またはカメラから画像を取り込み、その画像を何らかの方式で変更することによるプロセス。
コードブック−符号化した画像または符号化したサブイメージを格納するストレージ。
【００１０】
汎用コンピュータ
図１は、本発明の各種態様を実装するために使用できる従来の汎用デジタルコンピューティング環境の一例の機能ブロック図である。図１で、コンピュータ１００は、処理装置１１０、システムメモリ１２０、およびシステムメモリを含む各種のシステム構成要素を処理装置１１０に結合するシステムバス１３０を含む。システムバス１３０は、各種のバスアーキテクチャの任意のものを使用したメモリバスまたはメモリコントローラ、ペリフェラルバス、およびローカルバスを含む数タイプのバス構造のいずれでもよい。システムメモリ１２０は、読み取り専用メモリ（ＲＯＭ）１４０およびランダムアクセスメモリ（ＲＡＭ）１５０を含む。
【００１１】
起動時などにコンピュータ１００内の要素間の情報転送を助ける基本ルーチンを含む基本入出力システム１６０（ＢＩＯＳ）は、ＲＯＭ１４０に記憶される。コンピュータ１００は、ハードディスク（図示せず）の読み取りまたは書き込みを行うハードディスクドライブ１７０、取り外し可能な磁気ディスク１９０の読み取りまたは書き込みを行う磁気ディスクドライブ１８０、およびＣＤ−ＲＯＭや他の光学媒体などの取り外し可能な光ディスク１９１の読み取りまたは書き込みを行う光ディスクドライブ１９１も含む。ハードディスクドライブ１７０、磁気ディスクドライブ１８０、および光ディスクドライブ１９１は、それぞれ、ハードディスクドライブインタフェース１９２、磁気ディスクドライブインタフェース１９３、および光ディスクドライブインタフェース１９４によってシステムバス１３０に接続される。これらのドライブとそれに付随したコンピュータ記憶媒体は、パーソナルコンピュータ１００のコンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータの不揮発性の記憶を提供する。当業者には、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ベルヌーイカートリッジ、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）など、コンピュータからのアクセスが可能なデータを格納することができる他のタイプのコンピュータ可読媒体も例示的動作環境で使用できることが理解されよう。
【００１２】
ハードディスクドライブ１７０、磁気ディスク１９０、光ディスク１９２、ＲＯＭ１４０、またはＲＡＭ１５０には複数のプログラムモジュールを格納することができ、これにはオペレーティングシステム１９５、１つまたは複数のアプリケーションプログラム１９６、他のプログラムモジュール１９７、およびプログラムデータ１９８が含まれる。ユーザは、キーボード１０１およびポインティングデバイス１０２などの入力装置を通じてコンピュータ１００にコマンドと情報を入力することができる。この他の入力装置（図示せず）には、マイクロフォン、ジョイスティック、ゲームパッド、衛星受信アンテナ、スキャナなどが含まれる。これらおよびその他の入力装置は、システムバスに結合されたシリアルポートインタフェース１０６を通じて処理装置１１０に接続することが多いが、パラレルポート、ゲームポート、あるいはユニバーサルシリアルバス（ＵＳＢ）など他のインタフェースによって接続することも可能である。さらに、これらの装置は、適切なインタフェース（図示せず）を介して直接システムバス１３０に結合してもよい。モニタ１０７またはその他のタイプの表示装置も、ビデオアダプタ１０８などのインタフェースを介してシステムバス１３０に接続される。モニタに加えて、パーソナルコンピュータは通例、スピーカやプリンタなど他の周辺出力装置（図示せず）を含む。好ましい実施形態では、手書きの入力をデジタル的に取り込むために、ペンデジタイザ１６５およびそれに付随するペンまたはスタイラス１６６が提供される。図にはペンデジタイザ１６５とシリアルポートの直接接続を示しているが、実際には、ペンデジタイザ１６５は、当技術分野で知られるように、パラレルポートまたはその他のインタフェースおよびシステムバス１３０を介して直接処理装置１１０に結合してもよい。さらに、図ではデジタイザ１６５がモニタ１０７と別になっているが、デジタイザ１６５の使用可能な入力領域がモニタ１０７の表示領域と重なる（ｃｏｅｘｔｅｎｓｉｖｅ）ことが好ましい。さらに、デジタイザ１６５は、モニタ１０７の中に組み込んでも、あるいはモニタ１０７の上に重なるか、その他の形でモニタ１０７に付加される別個のデバイスとして存在してもよい。
【００１３】
コンピュータ１００は、リモートコンピュータ１０９など１つまたは複数のリモートコンピュータとの論理接続を使用したネットワーク環境で動作することができる。リモートコンピュータ１０９は、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、あるいはその他の一般的なネットワークノードでよく、また図１にはメモリ記憶装置１１１しか示していないが、通例は上記でコンピュータ１００に関して挙げた要素の多くまたはすべてを含む。図１に示す論理接続には、ローカルエリアネットワーク（ＬＡＮ）１１２およびワイドエリアネットワーク（ＷＡＮ）１１３が含まれる。このようなネットワーキング環境は、オフィス、企業内のコンピュータネットワーク、イントラネット、およびインターネットに一般的に見られる。
【００１４】
ＬＡＮネットワーキング環境で使用する場合、コンピュータ１００は、ネットワークインタフェースまたはアダプタ１１４を通じてローカルネットワーク１１２に接続する。ＷＡＮネットワーキング環境で使用する場合、パーソナルコンピュータ１００は通例、インターネットなどのワイドエリアネットワーク１１３を通じて通信を確立するためのモデム１１５またはその他の手段を含む。モデム１１５は、内蔵型であっても外付け型であってもよく、シリアルポートインタフェース１０６を介してシステムバス１３０に接続される。ネットワーク環境では、パーソナルコンピュータ１００との関連で図に示すプログラムモジュールまたはその一部を遠隔のメモリ記憶装置に格納することができる。
【００１５】
図のネットワーク接続は例証的なものであり、コンピュータ間に通信リンクを確立する他の技術を使用できることは理解されよう。ＴＣＰ／ＩＰ、イーサネット（登録商標）、ＦＴＰ、ＨＴＴＰなど各種のよく知られるプロトコルの任意のものの存在が想定され、システムをクライアントサーバ構成で作動させて、ユーザがウェブベースのサーバからウェブページを取り出すことを可能にすることができる。各種の従来のウェブブラウザの任意のものを使用して、ウェブページのデータを表示し、操作することができる。
【００１６】
取り込んだ画像の位置判定
本発明の態様には、符号化したバージョンの文書をサーチ可能な形態で格納することが含まれる。注釈デバイス（例えば文書のサブイメージを取り込むためにカメラが付属したペン）を使用して注釈を書き込むと、このシステムでは、カメラの位置を判定することができる。このカメラの位置の判定を使用して、注釈が付された位置を判定することができる。本発明の一部の態様では、このペンはインクペンであり、紙に書く。他の態様では、ペンはスタイラスであり、ユーザはコンピュータディスプレイの表面に書き込みを行う。この後者の例では、コンピュータ画面に書かれた注釈を、コンピュータ画面に表示された文書をサポートするシステムに再度提供することができる。カメラの位置を繰り返し取り込むことにより、システムは、ユーザによって制御されているスタイラスの動きを追跡することができる。
【００１７】
取り込んだ画像の位置を判定するには、３つのプロセスを使用することができる。ただし、実際には、これら３つのプロセスの態様を組み合わせて２つ以下のプロセスとするか、あるいは３つのプロセスを分離して４つ以上のプロセスとしてもよい。第１のプロセスは、画像をサーチ可能な形態に符号化することに関連する。一例では、画像をサーチ可能な形態に符号化し、その画像の位置（例えば画像の中心座標）に関連付ける。取り込まれた画像の中心の位置は、文書画像のどの場所にあってもよい。任意のサブイメージ（その中心が文書画像の任意の場所にある）を符号化することができる。これにより、（取り込まれた画像の位置を判定することができる）任意の可能な位置がコードブックを格納し、サーチすることができるように、文書画像の様々な場所を符号化できるという利点が得られる。
【００１８】
第２のプロセスは、符号化した画像またはサブイメージをコンパイルしてサーチ可能な構造にすることに関する。第３のプロセスは、符号化された情報のセットをサーチして元の文書との関係でカメラによる画像の位置を判定することに関する。それに続く処理を使用して、カメラからの画像との関係でスタイラスペンの先端の位置を判定することができる。
【００１９】
図２を参照すると、ステップ２０３で文書の画像を受け取る。ステップ２０３で受け取る文書の画像は、ステップ２０１における紙の文書のスキャンから得られたものでよい。あるいは、ステップ２０３の画像は、ステップ２０２のアプリケーションで生成されたものでもよい。
【００２０】
ステップ２０４で、画像を解析してサブイメージにする。ステップ２０５で、サブイメージに対応する位置を付加する、すなわちいくつかの位置とコードの対を得て、サブイメージをサーチ可能な形態に変換する。したがって、整数のピクセル単位を有する各位置は、対応するコードを有する。ステップ２０６で、ステップ２０５の位置とコードの対を有する、符号化したデータセットをサーチ可能なコードブックに配置し、コードブックはコードのプロパティでインデックスを付ける。
【００２１】
図３を参照すると、カメラからの画像に対応する画像があるかどうかコードブックをサーチする。カメラからの画像は、より大きな画像のサブイメージとほぼ同じサイズでよい。サブイメージのサイズをカメラからの画像とほぼ同じサイズにすることにより、より高速のサーチが可能になる。そうでない場合は、カメラの画像をサブイメージのサイズに合わせて拡大縮小する、サブイメージをカメラの画像サイズに合わせて拡大縮小する、あるいは両タイプの拡大縮小の何らかの組み合わせを使用して画像を比較することができる。ステップ３０４で、ステップ３０２のカメラからの画像とコードブック３０１のデータセットとを比較する。ステップ３０４の比較は、コードブックデータ３０１と取り込まれた画像３０２との間の閾値を超えるＮ個の最良のコードを見つけることを含んでもよい。ステップ３０２のカメラからの画像は、ステップ３０４で直接使用しても、あるいはステップ３０３で前処理および符号化を行ってもよい。ステップ３０３の前処理は、グレースケール画像を２進の白黒画像に変換することを含むことができる。前処理では、回転、スキュー、ホワイトレベル調整、量子化誤差、遠近法の補正などを補償することができる。ステップ３０３の符号化は、ステップ２０５と同様の処理をカメラからの画像（ステップ３０２）に適用することを意味する。
【００２２】
次いで、ステップ３０５で、見つかった（閾値を超える）Ｎ個のコードの位置の候補を判定する。ステップ３０３から得たコードをコードブック中のコードと比較し、ステップ３０３のコードと最も一致するコードを保持する。ステップ３０５で判定された画像の位置から、ステップ３０６でペン先の位置を判定する。任意選択で、点線の枠で示すように、ステップ３０７で新しい注釈を処理し、ステップ３０８でコードブックを更新してもよい。注釈を追加するプロセスは、ユーザが既に存在する注釈の上に、あるいはその近くに書き込みを行う際にシステムがカメラフレームの位置を判定する能力を向上させることができる。
【００２３】
この取り込まれた画像の位置の判定を使用して、ユーザによる紙、媒体、またはディスプレイ画面との対話の位置を判定することができる。本発明のいくつかの態様では、ペンは紙の上に書くインクペンでよい。他の態様では、ペンはスタイラスでよく、ユーザはコンピュータディスプレイの表面に書き込みを行う。文書上の符号化された透かしの知識を持つ、またはコンピュータ画面に表示された文書をサポートするシステムにどの対話も戻すことができる。カメラの位置を繰り返し取り込むことにより、システムは、ユーザによって制御されるスタイラスの動きを追跡することができる。
【００２４】
図４Ａおよび図４Ｂに、カメラ４０３を備えるペン４０１の例証的な例を示す。ペン４０１は、インク容器を含んでも含まなくともよい先端４０２を含む。カメラ４０３は、表面４０７から画像４０４を取り込む。ペン４０１はさらに、点線の枠４０６で表す追加的なセンサおよび／またはプロセッサを含むことができる。これらのセンサおよび／またはプロセッサ４０６は、別のペン４０１および／またはパーソナルコンピュータに（例えばＢｌｕｅｔｏｏｔｈやその他の無線プロトコルを介して）情報を送信する能力も含むことができる。
【００２５】
図４Ｂは、カメラ４０３から見た画像を表す。例証的な一例では、カメラ４０３の視野は３２×３２ピクセル（Ｎ＝３２）である。したがって、図４Ｂは、縦３２ピクセル、横３２ピクセルの視野を示している。Ｎのサイズは、求められる画像解像度の程度に基づいて調整することができる。また、ここでは例証のためにカメラ４０３の視野を正方形として示しているが、視野は当技術分野で知られる他の形も含むことができる。
【００２６】
カメラ４０３からペン４０１への入力は、画像フレームの連続｛Ｉｉ｝，ｉ＝１，２，．．．，Ａと定義することができ、Ｉｉは、サンプリング時間ｔｉにペン４０１によって取り込まれる。サンプリングレートは固定しても、文書サイズに応じて可変にしてもよい。取り込む画像フレームのサイズは、文書のサイズと必要とされる正確度に応じて、大きくしても小さくしてもよい。また、カメラ画像のサイズは、サーチする文書のサイズに基づいて決定することができる。
【００２７】
カメラ４０３によって取り込まれる画像は、処理システムによって直接使用しても、事前フィルタリングを行ってもよい。この事前フィルタリングは、ペン４０１の内部で行っても、ペン４０１の外部（例えばパーソナルコンピュータ）で行ってもよい。
【００２８】
図４Ｂの画像サイズは３２×３２ピクセルである。各符号化単位のサイズが３×３ピクセルである場合は、取り込まれる符号化単位の数はおよそ１００単位になる。符号化単位のサイズが５×５ピクセルである場合は、取り込まれる符号化された単位の数はおよそ３６になる。
【００２９】
カメラ４０３の出力をコードブック中の符号化された情報と比較することができる。コードブックは、カラー、グレースケール、あるいは白黒の画像スキャンから作成することができる。あるいは、コードブックは、アプリケーションから出力された画像または受け取った画像から生成することもできる。コードブックとシーケンス｛Ｉｉ｝との比較の出力は、シーケンス｛Ｐｉ｝，ｉ＝１，２，．．．，Ａと表すことができ、Ｐｉは、サンプリング時間ｔｉにおける、文書ビットマップ中のペン先４０２のすべての可能な場所の候補を表す。
【００３０】
図４Ａは、位置４０４からのパターンの画像４１０が形成されるイメージ平面４０９も示す。物体平面４０７上のパターンから受け取られる光は、レンズ４０８によって焦点が合わせられる。レンズ４０８は、単レンズでも、複合レンズシステムであってもよいが、ここでは説明を簡単にするために単レンズとして表している。画像取り込みセンサ４１１は、画像４１０を取り込む。
【００３１】
画像センサ４１１は、画像４１０を取り込むのに十分な大きさにすることができる。あるいは、画像センサ４１１は、位置４１２におけるペン先４０２の画像を取り込むのに十分な大きさにしてもよい。参照のために、位置４１２における画像を仮想ペン先と呼ぶ。ペン先、レンズ４０８、および画像センサ４１１の関係が一定なので、画像センサ４１１に対する仮想ペン先の位置が固定されることに留意されたい。仮想ペン先４１２の位置（Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐによって表す）から実際のペン先４０２の位置（Ｌｐｅｎｔｉｐで表す）への変換なので、取り込んだ画像４１０との関係で実際のペン先の位置を求めることができる。
【００３２】
次の変換ＦＳ→Ｐで、カメラによって取り込まれた画像を紙の上の実際の画像に変換する。
Ｌｐａｐｅｒ＝ＦＳ→Ｐ（ＬＳｅｎｓｏｒ）
書く際にペン先と紙は同じ平面上にある。したがって、仮想のペン先から実際のペン先への変換もＦＳ→Ｐになる。
Ｌｐｅｎｔｉｐ＝ＦＳ→Ｐ（Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ）
変換ＦＳ→Ｐは透視変換と称することができる。これは次のようにＦＳ→Ｐの推定として簡潔になり
【００３３】
【数１】
2004153798.tif 000003
【００３４】
Θ、ｓｘおよびｓｙは、位置４０４で取り込まれたパターンの２つの方向の回転およびスケールである。さらに、取り込んだ画像を紙の上の対応する背景画像と一致させることにより、Ｆ’Ｓ→ＰをＦＳ→Ｐに精緻化することができる。「精緻化」とは、再帰法と称するある種の最適化アルゴリズムにより、より正確な透視行列ＦＳ→Ｐ（８個のパラメータ）を得ることを意味する。再帰法では行列Ｆ’Ｓ→Ｐを初期値として扱う。ＦＳ→Ｐは、Ｆ’Ｓ→Ｐよりも正確にＳとＰの変換を記述する。
次いで、較正により仮想ペン先の位置を求めることができる。
【００３５】
ペン先４０２を紙の上の知られた位置Ｌｐｅｎｔｉｐに置く。次いでペンを傾けて、カメラ４０３が様々なペンの姿勢で一続きの画像を取り込めるようにする。取り込まれる画像ごとに、変換ＦＳ→Ｐを受け取ることができる。この変換から、ペン先の仮想画像の位置Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐを得ることができる。
Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ＝ＦＰ→Ｓ（Ｌｐｅｎｔｉｐ）
そして
ＦＰ→Ｓ＝１／ＦＳ→Ｐ
となる。
【００３６】
あらゆる画像から受け取るＬｖｉｒｔｕａｌ−ｐｅｎｔｉｐを平均することにより、仮想ペン先Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐの正確な位置を判定することができる。
【００３７】
この時点で仮想ペン先Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐの位置が分かっている。取り込まれた画像から、変換ＦＳ→Ｐも得ることができる。そして、この情報を使用して、実際のペン先の位置Ｌｐｅｎｔｉｐを求めることができる。
Ｌｐｅｎｔｉｐ＝ＦＳ→Ｐ（Ｌｖｉｒｔｕａｌ−ｐｅｎｔｉｐ）
【００３８】
符号化
符号化する画像は、文書をスキャンするスキャナから取り込むことができる。あるいは、符号化する画像は、固定された電子形態（例えば読み取りの特権のみを有する固定された表示サイズの電子ファイル）とすることもできる。カメラの位置を判定するために文書は実際に修正できるようにしてもよいが、符号化したバージョンは、一般に、カメラ４０３から見た文書に対応することができる。そうでない場合でも相関はなお生じることができるが、コードブックが、スキャンした文書とカメラから取り込んだ画像との類似性ほど正確でないものになる可能性がある。
【００３９】
画像を解析してサブイメージにする。各サブイメージを容易に検索できる形態に符号化する。サブイメージは、カメラ４０３からの出力と同じサイズに設定することができる。これにより、カメラ４０３からの出力とコードブックに格納された情報とのサーチ比較がおよそ等しくなるという利益が得られる。この結果得られる位置に続く処理を行って、スキャンされた画像に基づいて入力画像上の注釈の位置を判定するか、かつ／またはコンピューティングシステムのその他の動作を制御することができる。
【００４０】
以下の説明では、コードブックの生成に使用することができるいくつかの異なる符号化のオプションを提示する。以下の符号化法の１つを使用して、ペン４０１の使用中にカメラから取り込まれる画像を符号化してコードブックの情報とカメラからの符号化情報の比較を容易にすることもできる。各種の符号化システムが可能である。ここでは３つのシステムを提供するが、この他の符号化技術を使用することも可能である。
【００４１】
単純な符号化
第１のタイプの符号化は、受け取った画像を解析したサブイメージ自体がコードとして働くように使用することを含む。図５にこのプロセスの一例を示す。ステップ５０２で入力画像５０１を解析してサブイメージにする。このサブイメージ（５０３で表す）を画像５０１中の各自の位置に関連付け、コードブック５０５に格納する。コードブック５０５のサーチ時に、カメラ４０３からの画像が、コードブック５０５に格納された１つまたは複数のサブイメージと比較される。この比較から１つまたは複数の候補を得ることができる。さらに、ペン先４０２の位置を判定することができる。
【００４２】
サイズ縮小符号化
別の符号化の例には、各サブイメージのサイズを縮小することが含まれる。初めに画像６０１を受け取る。画像６０１は、画像ブロックＩと表すことができる。事例によっては、画像ブロックＩに閾値を適用することにより画像ブロックＩをバイナリ画像Ｉｂに変換することができる。次いで、各サブイメージのサイズをｍ＊ｍとしてサブイメージをまとめてＫｘ＊Ｋｙと表すことができる。図６の例ではｍ＝４である。別の例ではｍ＝３２であり、この場合は図４Ｂのグリッドと同様にサブイメージを３２＊３２のグリッドに分割する。
【００４３】
さらに、各サブイメージの再分割ｍは、カメラの画像解像度に直接対応する必要はない。例えば、再分割ｍは、より小さな再分割の組み合わせまたは部分的な組み合わせとすることができる。ここでは、より小さな再分割数が３２であり、ｍ＝４（図６から）である場合、各再分割ｍは８ピクセルを含むことができる。
【００４４】
次いで、再分割の内容の規則に基づく分析または閾値６０４（例えば真偽テスト）を適用することができる。サブイメージ６０３の各再分割に適用する閾値または規則の例には、各再分割中に連続した３つの白いカラムがあるかどうかの判定を含むことができる。言うまでもなく、この例の代わりに、あるいはこの例と併用してこの他の規則に基づく分析を使用することができる。
【００４５】
この分析６０４の結果に基づき、行列６０５を生成することができる。行列６０５は、サブイメージ６０３の各再分割に閾値６０４を適用した結果の一例を示す。Ｋ行列（幅Ｋｘ、高さＫｙ）は、値０／１を有し、１は真を意味し、０は偽を意味する。この結果得られるＫ行列は、画像ブロックＩの
【００４６】
【数２】
2004153798.tif 000004
【００４７】
と表すことができ、ｋ−ｗｉｎは、この符号化法を指す別の方式である。
【００４８】
【数３】
2004153798.tif 000005
【００４９】
は、行列６０５としてのサブイメージマップの一例を用いると等式（１）と表すことができる。
【００５０】
【数４】
2004153798.tif 000006
【００５１】
このタイプの符号化は、第１の行列と、カメラ４０３から取り込まれた画像から形成された行列との距離を求めることによってサーチすることができる。２つの行列間の距離は、等式（２）で表す２つの行列のハミング距離である。
【００５２】
（２）      Ｄｉｓｔｈａｍ（Ｃ１，Ｃ２）＝Ｈａｍ（Ｃ１，Ｃ２）
Ｈａｍ（ａ，ｂ）が、行列ａと行列ｂとのハミング距離になる。
【００５３】
半径方向の符号化
半径方向の符号化と称する別のタイプの符号化について図７を参照して説明する。画像７０１を受け取り、ステップ７０２で解析してサブイメージにする。７０３で、サブイメージの中心を中心にして方向ＳにベクトルＴだけ回転することによりサブイメージをサンプリングする。７０３のサブイメージで得られる情報をアンラップ（ｕｎｗｒａｐｐｅｄ）画像７０４によって表す。すなわち、７０３のサブイメージブロックは、極座標でサンプリングする。
【００５４】
７０３のサブイメージの中心ピクセル（あるいは領域）を原点として扱い、サンプリング角度をＳ、サンプリングベクトルの大きさをＴとする。３２×３２ピクセルの領域の場合はＳ＝３２、Ｔ＝１６になる。
【００５５】
各サンプリング点（ｔ，ｓ），ｔ＝０，１，．．．，Ｔ−１，ｓ＝０，１，．．．，Ｓ−１で、デカルト座標におけるその位置は、（ｘｔ，ｓ，ｙｔ，ｓ）になり、ｘｔ，ｓおよびｙｔ，ｓは、それぞれ等式（３）と（４）によって表される。
【００５６】
【数５】
2004153798.tif 000007
【００５７】
点（ｔ，ｓ）のグレーレベル値は、等式（５）によって表される。
（５）      Ｇｔ，ｓ＝Ｆ（ｘｔ，ｓ，ｙｔ，ｓ）
Ｆは、等式（６）によって表される２Ｄのガウスフィルタである。
【００５８】
【数６】
2004153798.tif 000008
【００５９】
Ｐ（ｘ，ｙ）は、位置（ｘ，ｙ）のピクセルのグレーレベル値を意味し、括弧「［］」は、実際の値の最も近い整数を意味し、σおよびｑはフィルタパラメータである。フィルタパラメータの例は、σ＝１．１５、ｑ＝１などである。これらの値は、アルゴリズムを経験的にテストして所与の環境に対してどの値が最も有効であるかを判定することによって求める。
【００６０】
７０３に示すように極座標を使用してサブイメージブロックを分析すると、その分析結果は、カメラフレームとサブイメージとの回転の差を扱う際により高い堅牢性を有する。コードブックの情報と比較するカメラ画像の回転は、７０４で画像の移動に変換する、取り込まれたカメラ画像の回転ほど複雑な問題ではない。
【００６１】
７０４の画像は、表７０５に示すように、ベクトルＴにわたる各角度Ｓについて２進表現に変換することができる。この度は、ｓの範囲が０からＳ−１のとき２π・ｓ／Ｓになる。画像またはサブイメージ（７０１、７０２、７０３、７０４）は、最初にスキャンしたとき、あるいは受け取ったとき、取り込んだときに既にバイナリ画像に変換していない場合は、複数の位置でバイナリ（白黒）画像に変換することができる。
【００６２】
グレーレベル値の行列｛Ｇｔ，ｓ｝（ｔ＝０，１，．．．，Ｔ−１、ｓ＝０，１，．．．，Ｓ−１）は、グレーレベル行列の値に閾値を適用することにより、バイナリ行列
【００６３】
【数７】
2004153798.tif 000009
【００６４】
（等式（７）に示す）に変換することができる。
【００６５】
【数８】
2004153798.tif 000010
【００６６】
次いでこのコードをコンパイルして、より大きな画像中のサブイメージの位置に関する情報を含むコードブックにすることができる。
【００６７】
コードブックにある異なるコードでカメラ画像の位置を判定するために、カメラ画像ともう一方のコード表現との距離を求めることができる。候補までの最も短い距離または最も短い距離のセットが、各種位置のうち最良の選択肢を表すことができる。この距離は、カメラ画像と現在のサブイメージとのハミング距離によって計算することができる。
【００６８】
先に述べたように、カメラから取り込まれた画像からの距離を、コードブックの１つまたは複数のコードセグメントと比較することができる。半径方向のコードには、一般的なハミング距離と回転不変距離の少なくとも２つのタイプの距離を使用することができる。この他の距離の判定を使用することもできる。
【００６９】
等式（８）に示すように、一般的なハミング距離を使用して、コードブックのコードと、カメラ画像に関連付けられたコードとの距離を求めることができる。
【００７０】
（８）      Ｄｉｓｔｈａｍ（Ｃ１，Ｃ２）＝Ｈａｍ（Ｃ１，Ｃ２）
使用することが可能な別のタイプの距離には、回転不変距離がある。回転不変距離を使用することの利点は、等式（９）に示すようにカメラの回転に対応することである。
【００７１】
【数９】
2004153798.tif 000011
【００７２】
【数１０】
2004153798.tif 000012
【００７３】
は、等式（１０）に示すように定義される。
【００７４】
【数１１】
2004153798.tif 000013
【００７５】
コードブック生成
コードブックは、画像から取られ、その画像中の各自の位置に関連付けられたサブイメージに関連するコードを格納する。コードブックは、カメラ４０３で画像を取り込む前に作成することができる。あるいは、コードブックは、使用中に作成するか、あるいは少なくとも追加することもできる。例えば、カメラは動作中に画像を取り込むことができる。５０１、６０１、および７０１で示すように、ユーザが既にある情報の上に書き込みをするだけの場合は、ここで説明するようにコードブックを使用して、カメラによって取り込まれた画像の位置を判定することができる。しかし、ユーザが新しい注釈を上書きした場合は、コードブックは上書きの前ほど正確なものではなくなる。したがって、ペン４０１で新しい注釈が追加されると、その注釈をコードブックに組み込んで、後に書き込まれる注釈がその画面上の表現とより正確に相関するようにする。
【００７６】
コードブックの生成は以下のように行うことができる。５０３、６０３、および７０３に示すサブイメージを符号化法によって符号化する。次いで、位置とコードの対を編成してコードブックを作成する。少なくとも２タイプの編成法を使用してコードブックを作成することができる。無論、他の方法を使用してコードブックを作成することもできる。これら２つの方法は、単なる例証的な例として提示する。
【００７７】
第１の方法は、位置とコードの対を線形のリストに入れるものであり、リスト中で各コードはコードと位置のシーケンスを含み、すべての位置がそのコードにマッピングされる。するとコードブックは等式（１１）のように表すことができる。
（１１）      Ω＝｛Ψｉ，ｉ＝１，２，．．．，ＮΩ｝
Ψは、Ψ＝｛ＣΨ，ＰΨ｝と定義され、ＰΨは、その文書のビットマップ中にあるすべての位置のセットであり、そのコードは等式（１２）に示すようにＣである。
（１２）      ＰΨ＝｛ｐｉ｜位置ｐｉにおけるコードはＣΨ，ｉ＝１，２，．．．｝
次いで、セットΩを各メンバーΨのコードによってアルファベット順にソートすることができ、それにより線形リストタイプのコードブックが得られる。
【００７８】
第２の方法は、対応する位置を有するコードを２分木に入れるものである。
この２分木は、図８に表すようにコード間のハミング距離に基づくことができる。初めに、コードセットΩ全体の重心Ｃｃ０を見つける。次に、重心Ｃｃ０までのハミング距離が最大のコードＣ０を見つける。次いで、コードＣ０との距離が最大のコードＣ１を見つける。
【００７９】
次いでコードセットＣを２つのサブセットΩ０とΩ１に分割する。Ω０の内容は等式（１３）で表すことができ、Ω１の内容は等式（１４）で表すことができる。
【００８０】
【数１２】
2004153798.tif 000014
【００８１】
次いで、サブセットΩ０およびΩ１について、重心を見つけ、重心までの距離が最大のコードを見つけ、重心から最も遠いそのコードまでの距離が最大のコードを見つけ、そしてサブセットを分割するステップをサブセットのメンバーの数が１になるまで繰り返す。
【００８２】
候補のサーチ
カメラから取り込まれたフレームの位置の候補は、コードブックをサーチすることによって決定することができる。カメラによって取り込まれた各フレームＩｉに対して、ペン先４０２の候補位置を次のように求めることができる。
１）コードブックの生成に使用した方法と同じ符号化法でカメラからのフレームＩｉを符号化する。
２）符号化したフレームＥＩｉとコードブックの情報を比較する。符号化フレームＥＩｉとコードブックの符号化された情報との距離を求める。符号化フレームＥＩｉとの距離が最小であるコードブック中の符号化情報を位置の候補として、あるいは位置の候補の１つとして使用する。これらの候補から、最も一致するものを選択する。
【００８３】
最良の候補の選択は、いくつかの異なる分析を含むことができる。初めに、最も近く一致する（コードＥＩｉとの距離が最小）の候補を選び出すことができる。あるいは、最も最近の候補セットと最近の候補のシーケンスを比較し、時間の経過にわたってフレームを比較することもできる。この比較により、互いに最も近い一連の位置が得られるはずである。この結果が予想されるのは、ペン先が時間の経過に伴い可能な限りわずかに移動したことを示すためである。これに代わる結果は、ペン先が非常に短い時間の間にそのページ内でジャンプしたことを示す可能性がある（この可能性は先の例に比べて低い）。
【００８４】
コードブックのサーチには以下の方法を使用することができる。取り込まれた各画像Ｉについて、コードＣＩで、等式（１５）のように最も一致するコードセットＳ（ＣＩ）を定義する。
【００８５】
【数１３】
2004153798.tif 000015
【００８６】
半径方向のコードを使用する場合、距離関数はＤｉｓｔｒ−ｉ（・，・）にすべきである。
Ｎｓ＞Ｎｔｈｒｅｓｈである場合は、Ｓ（ＣＩ）の距離がより小さいＮｔｈｒｅｓｈコードだけを保持し、カメラの性能に応じてｄｔｈｒｅｓｈおよびＮｔｈｒｅｓｈを選択する。
画像Ｉの位置候補のセットを等式（１６）で表すことができる。
【００８７】
【数１４】
2004153798.tif 000016
【００８８】
特許請求の範囲を使用して本発明を定義したが、本発明はここに記載する要素およびステップを任意の組み合わせまたはサブコンビネーションで包含することを意図するため、この特許請求の範囲は例証的なものである。したがって、本発明を定義する任意数の代替の組み合わせがあり、その組み合わせは、この説明、特許請求の範囲、および図面を含む本明細書の１つまたは複数の要素を各種の組み合わせまたはサブコンビネーションで組み込む。当業者には、本明細書に鑑みて、本発明の態様の代替の組み合わせを単独で、あるいはここに定義する１つまたは複数の要素またはステップと組み合わせて、本発明または本発明の一部の修正形態または代替形態として利用できることは明らかであろう。本明細書に含まれる記載する本発明の説明は、そのような修正形態および代替形態をすべて包含することを意図することができる。
【図面の簡単な説明】
【００８９】
【図１】本発明の実施形態と併せて使用することができるコンピュータを示す略図である。
【図２】本発明の実施形態により、受け取った画像を解析し、コードブックを作成するプロセスを示す流れ図である。
【図３】本発明の実施形態により、カメラからの画像の１つまたは複数の可能な位置を判定するプロセスを示す流れ図である。
【図４Ａ】本発明の実施形態によるペンおよび画像取り込みシステムの可能なビューを示す図である。
【図４Ｂ】本発明の実施形態によるペンおよび画像取り込みシステムの可能なビューを示す図である。
【図５】本発明の実施形態により画像を符号化する第１のプロセスを示す説明図である。
【図６】本発明の実施形態により画像を符号化する第２のプロセスを示す説明図である。
【図７】本発明の実施形態により画像を符号化する第３のプロセスを示す説明図である。
【図８】本発明の実施形態によるコードブックの構築を示す説明図である。
【符号の説明】
【００９０】
１００、１０９  コンピュータ
１０１  キーボード
１０２  ポインティングデバイス
１０６  シリアルポートインタフェース
１０７  モニタ
１０８  ビデオアダプタ
１１０  処理装置
１１１  メモリ記憶装置
１１２  ＬＡＮ
１１３  ＷＡＮ
１１４  ネットワークインタフェース
１１５  モデム
１２０  システムメモリ
１３０  システムバス
１４０  ＲＯＭ
１５０  ＲＡＭ
１６０  ＢＩＯＳ
１６５  ペンデジタイザ
１６６  スタイラス
１７０  ハードディスクドライブ
１８０  磁気ディスクドライブ
１９０  磁気ディスク
１９１  光ディスクドライブ
１９２  光ディスク
１９３  磁気ディスクドライブインタフェース
１９４  光ディスクドライブインタフェース
１９５  オペレーティングシステム
１９６  アプリケーションプログラム
１９７  プログラムモジュール
１９８  プログラムデータ
４０１  ペン
４０２  ペン先
４０３  カメラ
４０４、４１０、５０１、６０１、７０１、７０４  画像
４０６  センサ（プロセッサ）
４０７  表面
４０８  レンズ
４０９  イメージ平面
４１１  画像取り込みセンサ
５０３、６０３、７０３、７０４  サブイメージ
５０５  コードブック
６０５  行列
【図１】
2004153798.tif 000017
【図２】
2004153798.tif 000018
【図３】
2004153798.tif 000019
【図４Ａ】
2004153798.tif 000020
【図４Ｂ】
2004153798.tif 000021
【図５】
2004153798.tif 000022
【図６】
2004153798.tif 000023
【図７】
2004153798.tif 000024
【図８】
2004153798.tif 000025