JP4217577B2 - 受動的な埋め込み対話符号化 - Google Patents

Description

本発明は、デジタルペンを使用した紙との対話に関する。より詳細には、本発明は、デジタルペンによって紙の表面に付された注釈の位置を判定することに関する。

コンピュータユーザは、パーソナルコンピュータと対話する一方式としてマウスとキーボードを使用することに慣れている。パーソナルコンピュータは、紙に書かれた文書を上回るいくつかの利点を提供するが、ユーザの大半は、一定の機能は引き続き印刷した紙を用いて行っている。そのような機能の一部には、紙に書かれた文書を読み、注釈を書き込むことがある。注釈の場合、印刷された文書は、ユーザによって付された注釈のためにより高い意義を持つ。

しかし、印刷した文書に注釈を書き込むことに伴う問題の１つは、後にその注釈をその文書の電子形態に再度入力する必要性である。これを行うには、注釈を書き込んだユーザか別のユーザが注釈を読み取り、それをパーソナルコンピュータに入力することが必要となる。場合によっては、ユーザが注釈と元のテキストをスキャナで読み込むことにより新しい文書を作成する。こうした複数回のステップのために、印刷文書とその文書の電子バージョンとの対話を繰り返し扱うことが難しくなっている。さらに、スキャナで取り込んだ画像はしばしば修正することができない。元のテキストから注釈を分離する手段がない可能性がある。このため、注釈を使用することが難しくなっている。したがって、注釈を扱う改良された方式が必要とされる。

本発明の態様は、上述の問題の少なくとも１つに対する解決法を提供し、それにより認識された画像上の１つまたは複数の位置を判定することを可能にする。この位置を知ることにより、ユーザは、物理的な文書に注釈を書き込み、その注釈をその物理的文書の電子バージョンに関連付けることができる。本発明の態様の一部は、物理的な文書の符号化に使用される各種の技術に関連する。他の態様は、符号化された文書をサーチ可能な形態に編成することに関連する。

本発明のこれらおよびその他の態様は、以下の図面とそれに関連する説明を通じて明らかになろう。

前述の本発明の課題を解決するための手段と以下の好ましい実施形態の詳細な説明は、添付図面と併せて読むことにより一層理解される。図面は、本発明に関する限定ではなく、例として含める。

本発明の態様は、取り込まれた画像の位置をより大きな画像との関係で判定することに関する。ここに記載する位置の判定方法およびシステムは、複数機能ペンと組み合わせて使用することができる。この複数機能ペンは、固定された文書に付された手書きの注釈を取り込み、固定された文書上の情報によりその注釈の位置を判定できるようにする能力を提供する。固定された文書は、印刷した文書であっても、コンピュータ画面上にレンダリングした文書であってもよい。

読者が本発明の各種態様を理解する助けとなるように以下の説明はいくつかのサブセクションに分ける。このサブセクションには、用語、汎用コンピュータ、取り込んだ画像の位置判定、符号化、コードブック生成、および候補サーチが含まれる。

用語
ペン−インクを貯蔵する能力を備えても、備えなくともよい任意の筆記用具。事例によっては、本発明の実施形態により、インクを貯蔵する能力を持たないスタイラスをペンとして使用することができる。
カメラ−画像取り込みシステム。
符号化−（物理的な紙の形態からスキャナで取り込むか、電子形態からレンダリングするか）またはカメラから画像を取り込み、その画像を何らかの方式で変更することによるプロセス。
コードブック−符号化した画像または符号化したサブイメージを格納するストレージ。

汎用コンピュータ
図１は、本発明の各種態様を実装するために使用できる従来の汎用デジタルコンピューティング環境の一例の機能ブロック図である。図１で、コンピュータ１００は、処理装置１１０、システムメモリ１２０、およびシステムメモリを含む各種のシステム構成要素を処理装置１１０に結合するシステムバス１３０を含む。システムバス１３０は、各種のバスアーキテクチャの任意のものを使用したメモリバスまたはメモリコントローラ、ペリフェラルバス、およびローカルバスを含む数タイプのバス構造のいずれでもよい。システムメモリ１２０は、読み取り専用メモリ（ＲＯＭ）１４０およびランダムアクセスメモリ（ＲＡＭ）１５０を含む。

起動時などにコンピュータ１００内の要素間の情報転送を助ける基本ルーチンを含む基本入出力システム１６０（ＢＩＯＳ）は、ＲＯＭ１４０に記憶される。コンピュータ１００は、ハードディスク（図示せず）の読み取りまたは書き込みを行うハードディスクドライブ１７０、取り外し可能な磁気ディスク１９０の読み取りまたは書き込みを行う磁気ディスクドライブ１８０、およびＣＤ−ＲＯＭや他の光学媒体などの取り外し可能な光ディスク１９１の読み取りまたは書き込みを行う光ディスクドライブ１９１も含む。ハードディスクドライブ１７０、磁気ディスクドライブ１８０、および光ディスクドライブ１９１は、それぞれ、ハードディスクドライブインタフェース１９２、磁気ディスクドライブインタフェース１９３、および光ディスクドライブインタフェース１９４によってシステムバス１３０に接続される。これらのドライブとそれに付随したコンピュータ記憶媒体は、パーソナルコンピュータ１００のコンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータの不揮発性の記憶を提供する。当業者には、磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ベルヌーイカートリッジ、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）など、コンピュータからのアクセスが可能なデータを格納することができる他のタイプのコンピュータ可読媒体も例示的動作環境で使用できることが理解されよう。

ハードディスクドライブ１７０、磁気ディスク１９０、光ディスク１９２、ＲＯＭ１４０、またはＲＡＭ１５０には複数のプログラムモジュールを格納することができ、これにはオペレーティングシステム１９５、１つまたは複数のアプリケーションプログラム１９６、他のプログラムモジュール１９７、およびプログラムデータ１９８が含まれる。ユーザは、キーボード１０１およびポインティングデバイス１０２などの入力装置を通じてコンピュータ１００にコマンドと情報を入力することができる。この他の入力装置（図示せず）には、マイクロフォン、ジョイスティック、ゲームパッド、衛星受信アンテナ、スキャナなどが含まれる。これらおよびその他の入力装置は、システムバスに結合されたシリアルポートインタフェース１０６を通じて処理装置１１０に接続することが多いが、パラレルポート、ゲームポート、あるいはユニバーサルシリアルバス（ＵＳＢ）など他のインタフェースによって接続することも可能である。さらに、これらの装置は、適切なインタフェース（図示せず）を介して直接システムバス１３０に結合してもよい。モニタ１０７またはその他のタイプの表示装置も、ビデオアダプタ１０８などのインタフェースを介してシステムバス１３０に接続される。モニタに加えて、パーソナルコンピュータは通例、スピーカやプリンタなど他の周辺出力装置（図示せず）を含む。好ましい実施形態では、手書きの入力をデジタル的に取り込むために、ペンデジタイザ１６５およびそれに付随するペンまたはスタイラス１６６が提供される。図にはペンデジタイザ１６５とシリアルポートの直接接続を示しているが、実際には、ペンデジタイザ１６５は、当技術分野で知られるように、パラレルポートまたはその他のインタフェースおよびシステムバス１３０を介して直接処理装置１１０に結合してもよい。さらに、図ではデジタイザ１６５がモニタ１０７と別になっているが、デジタイザ１６５の使用可能な入力領域がモニタ１０７の表示領域と重なる（ｃｏｅｘｔｅｎｓｉｖｅ）ことが好ましい。さらに、デジタイザ１６５は、モニタ１０７の中に組み込んでも、あるいはモニタ１０７の上に重なるか、その他の形でモニタ１０７に付加される別個のデバイスとして存在してもよい。

コンピュータ１００は、リモートコンピュータ１０９など１つまたは複数のリモートコンピュータとの論理接続を使用したネットワーク環境で動作することができる。リモートコンピュータ１０９は、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、あるいはその他の一般的なネットワークノードでよく、また図１にはメモリ記憶装置１１１しか示していないが、通例は上記でコンピュータ１００に関して挙げた要素の多くまたはすべてを含む。図１に示す論理接続には、ローカルエリアネットワーク（ＬＡＮ）１１２およびワイドエリアネットワーク（ＷＡＮ）１１３が含まれる。このようなネットワーキング環境は、オフィス、企業内のコンピュータネットワーク、イントラネット、およびインターネットに一般的に見られる。

ＬＡＮネットワーキング環境で使用する場合、コンピュータ１００は、ネットワークインタフェースまたはアダプタ１１４を通じてローカルネットワーク１１２に接続する。ＷＡＮネットワーキング環境で使用する場合、パーソナルコンピュータ１００は通例、インターネットなどのワイドエリアネットワーク１１３を通じて通信を確立するためのモデム１１５またはその他の手段を含む。モデム１１５は、内蔵型であっても外付け型であってもよく、シリアルポートインタフェース１０６を介してシステムバス１３０に接続される。ネットワーク環境では、パーソナルコンピュータ１００との関連で図に示すプログラムモジュールまたはその一部を遠隔のメモリ記憶装置に格納することができる。

図のネットワーク接続は例証的なものであり、コンピュータ間に通信リンクを確立する他の技術を使用できることは理解されよう。ＴＣＰ／ＩＰ、イーサネット（登録商標）、ＦＴＰ、ＨＴＴＰなど各種のよく知られるプロトコルの任意のものの存在が想定され、システムをクライアントサーバ構成で作動させて、ユーザがウェブベースのサーバからウェブページを取り出すことを可能にすることができる。各種の従来のウェブブラウザの任意のものを使用して、ウェブページのデータを表示し、操作することができる。

取り込んだ画像の位置判定
本発明の態様には、符号化したバージョンの文書をサーチ可能な形態で格納することが含まれる。注釈デバイス（例えば文書のサブイメージを取り込むためにカメラが付属したペン）を使用して注釈を書き込むと、このシステムでは、カメラの位置を判定することができる。このカメラの位置の判定を使用して、注釈が付された位置を判定することができる。本発明の一部の態様では、このペンはインクペンであり、紙に書く。他の態様では、ペンはスタイラスであり、ユーザはコンピュータディスプレイの表面に書き込みを行う。この後者の例では、コンピュータ画面に書かれた注釈を、コンピュータ画面に表示された文書をサポートするシステムに再度提供することができる。カメラの位置を繰り返し取り込むことにより、システムは、ユーザによって制御されているスタイラスの動きを追跡することができる。

取り込んだ画像の位置を判定するには、３つのプロセスを使用することができる。ただし、実際には、これら３つのプロセスの態様を組み合わせて２つ以下のプロセスとするか、あるいは３つのプロセスを分離して４つ以上のプロセスとしてもよい。第１のプロセスは、画像をサーチ可能な形態に符号化することに関連する。一例では、画像をサーチ可能な形態に符号化し、その画像の位置（例えば画像の中心座標）に関連付ける。取り込まれた画像の中心の位置は、文書画像のどの場所にあってもよい。任意のサブイメージ（その中心が文書画像の任意の場所にある）を符号化することができる。これにより、（取り込まれた画像の位置を判定することができる）任意の可能な位置がコードブックを格納し、サーチすることができるように、文書画像の様々な場所を符号化できるという利点が得られる。

第２のプロセスは、符号化した画像またはサブイメージをコンパイルしてサーチ可能な構造にすることに関する。第３のプロセスは、符号化された情報のセットをサーチして元の文書との関係でカメラによる画像の位置を判定することに関する。それに続く処理を使用して、カメラからの画像との関係でスタイラスペンの先端の位置を判定することができる。

図２を参照すると、ステップ２０３で文書の画像を受け取る。ステップ２０３で受け取る文書の画像は、ステップ２０１における紙の文書のスキャンから得られたものでよい。あるいは、ステップ２０３の画像は、ステップ２０２のアプリケーションで生成されたものでもよい。

ステップ２０４で、画像を解析してサブイメージにする。ステップ２０５で、サブイメージに対応する位置を付加する、すなわちいくつかの位置とコードの対を得て、サブイメージをサーチ可能な形態に変換する。したがって、整数のピクセル単位を有する各位置は、対応するコードを有する。ステップ２０６で、ステップ２０５の位置とコードの対を有する、符号化したデータセットをサーチ可能なコードブックに配置し、コードブックはコードのプロパティでインデックスを付ける。

図３を参照すると、カメラからの画像に対応する画像があるかどうかコードブックをサーチする。カメラからの画像は、より大きな画像のサブイメージとほぼ同じサイズでよい。サブイメージのサイズをカメラからの画像とほぼ同じサイズにすることにより、より高速のサーチが可能になる。そうでない場合は、カメラの画像をサブイメージのサイズに合わせて拡大縮小する、サブイメージをカメラの画像サイズに合わせて拡大縮小する、あるいは両タイプの拡大縮小の何らかの組み合わせを使用して画像を比較することができる。ステップ３０４で、ステップ３０２のカメラからの画像とコードブック３０１のデータセットとを比較する。ステップ３０４の比較は、コードブックデータ３０１と取り込まれた画像３０２との間の閾値を超えるＮ個の最良のコードを見つけることを含んでもよい。ステップ３０２のカメラからの画像は、ステップ３０４で直接使用しても、あるいはステップ３０３で前処理および符号化を行ってもよい。ステップ３０３の前処理は、グレースケール画像を２進の白黒画像に変換することを含むことができる。前処理では、回転、スキュー、ホワイトレベル調整、量子化誤差、遠近法の補正などを補償することができる。ステップ３０３の符号化は、ステップ２０５と同様の処理をカメラからの画像（ステップ３０２）に適用することを意味する。

次いで、ステップ３０５で、見つかった（閾値を超える）Ｎ個のコードの位置の候補を判定する。ステップ３０３から得たコードをコードブック中のコードと比較し、ステップ３０３のコードと最も一致するコードを保持する。ステップ３０５で判定された画像の位置から、ステップ３０６でペン先の位置を判定する。任意選択で、点線の枠で示すように、ステップ３０７で新しい注釈を処理し、ステップ３０８でコードブックを更新してもよい。注釈を追加するプロセスは、ユーザが既に存在する注釈の上に、あるいはその近くに書き込みを行う際にシステムがカメラフレームの位置を判定する能力を向上させることができる。

この取り込まれた画像の位置の判定を使用して、ユーザによる紙、媒体、またはディスプレイ画面との対話の位置を判定することができる。本発明のいくつかの態様では、ペンは紙の上に書くインクペンでよい。他の態様では、ペンはスタイラスでよく、ユーザはコンピュータディスプレイの表面に書き込みを行う。文書上の符号化された透かしの知識を持つ、またはコンピュータ画面に表示された文書をサポートするシステムにどの対話も戻すことができる。カメラの位置を繰り返し取り込むことにより、システムは、ユーザによって制御されるスタイラスの動きを追跡することができる。

図４Ａおよび図４Ｂに、カメラ４０３を備えるペン４０１の例証的な例を示す。ペン４０１は、インク容器を含んでも含まなくともよい先端４０２を含む。カメラ４０３は、表面４０７から画像４０４を取り込む。ペン４０１はさらに、点線の枠４０６で表す追加的なセンサおよび／またはプロセッサを含むことができる。これらのセンサおよび／またはプロセッサ４０６は、別のペン４０１および／またはパーソナルコンピュータに（例えばＢｌｕｅｔｏｏｔｈ（登録商標）やその他の無線プロトコルを介して）情報を送信する能力も含むことができる。

図４Ｂは、カメラ４０３から見た画像を表す。例証的な一例では、カメラ４０３の視野は３２×３２ピクセル（Ｎ＝３２）である。したがって、図４Ｂは、縦３２ピクセル、横３２ピクセルの視野を示している。Ｎのサイズは、求められる画像解像度の程度に基づいて調整することができる。また、ここでは例証のためにカメラ４０３の視野を正方形として示しているが、視野は当技術分野で知られる他の形も含むことができる。

カメラ４０３からペン４０１への入力は、画像フレームの連続｛Ｉｉ｝，ｉ＝１，２，．．．，Ａと定義することができ、Ｉｉは、サンプリング時間ｔｉにペン４０１によって取り込まれる。サンプリングレートは固定しても、文書サイズに応じて可変にしてもよい。取り込む画像フレームのサイズは、文書のサイズと必要とされる正確度に応じて、大きくしても小さくしてもよい。また、カメラ画像のサイズは、サーチする文書のサイズに基づいて決定することができる。

カメラ４０３によって取り込まれる画像は、処理システムによって直接使用しても、事前フィルタリングを行ってもよい。この事前フィルタリングは、ペン４０１の内部で行っても、ペン４０１の外部（例えばパーソナルコンピュータ）で行ってもよい。

図４Ｂの画像サイズは３２×３２ピクセルである。各符号化単位のサイズが３×３ピクセルである場合は、取り込まれる符号化単位の数はおよそ１００単位になる。符号化単位のサイズが５×５ピクセルである場合は、取り込まれる符号化された単位の数はおよそ３６になる。

カメラ４０３の出力をコードブック中の符号化された情報と比較することができる。コードブックは、カラー、グレースケール、あるいは白黒の画像スキャンから作成することができる。あるいは、コードブックは、アプリケーションから出力された画像または受け取った画像から生成することもできる。コードブックとシーケンス｛Ｉｉ｝との比較の出力は、シーケンス｛Ｐｉ｝，ｉ＝１，２，．．．，Ａと表すことができ、Ｐｉは、サンプリング時間ｔｉにおける、文書ビットマップ中のペン先４０２のすべての可能な場所の候補を表す。

図４Ａは、位置４０４からのパターンの画像４１０が形成されるイメージ平面４０９も示す。物体平面４０７上のパターンから受け取られる光は、レンズ４０８によって焦点が合わせられる。レンズ４０８は、単レンズでも、複合レンズシステムであってもよいが、ここでは説明を簡単にするために単レンズとして表している。画像取り込みセンサ４１１は、画像４１０を取り込む。

画像センサ４１１は、画像４１０を取り込むのに十分な大きさにすることができる。あるいは、画像センサ４１１は、位置４１２におけるペン先４０２の画像を取り込むのに十分な大きさにしてもよい。参照のために、位置４１２における画像を仮想ペン先と呼ぶ。ペン先、レンズ４０８、および画像センサ４１１の関係が一定なので、画像センサ４１１に対する仮想ペン先の位置が固定されることに留意されたい。仮想ペン先４１２の位置（Ｌ_{ｖｉｒｔｕａｌ−ｐｅｎｔｉｐ}によって表す）から実際のペン先４０２の位置（Ｌ_{ｐｅｎｔｉｐ}で表す）への変換なので、取り込んだ画像４１０との関係で実際のペン先の位置を求めることができる。

次の変換Ｆ_Ｓ→Ｐで、カメラによって取り込まれた画像を紙の上の実際の画像に変換する。
Ｌ_{ｐａｐｅｒ}＝Ｆ_Ｓ→Ｐ（Ｌ_{Ｓｅｎｓｏｒ}）
書く際にペン先と紙は同じ平面上にある。したがって、仮想のペン先から実際のペン先への変換もＦ_Ｓ→Ｐになる。
Ｌ_{ｐｅｎｔｉｐ}＝Ｆ_Ｓ→Ｐ（Ｌ_{ｖｉｒｔｕａｌ−ｐｅｎｔｉｐ}）
変換Ｆ_Ｓ→Ｐは透視変換と称することができる。これは次のようにＦ_Ｓ→Ｐの推定として簡潔になり

Θ、ｓ_ｘおよびｓ_ｙは、位置４０４で取り込まれたパターンの２つの方向の回転およびスケールである。さらに、取り込んだ画像を紙の上の対応する背景画像と一致させることにより、Ｆ’_Ｓ→ＰをＦ_Ｓ→Ｐに精緻化することができる。「精緻化」とは、再帰法と称するある種の最適化アルゴリズムにより、より正確な透視行列Ｆ_Ｓ→Ｐ（８個のパラメータ）を得ることを意味する。再帰法では行列Ｆ’_Ｓ→Ｐを初期値として扱う。Ｆ_Ｓ→Ｐは、Ｆ’_Ｓ→Ｐよりも正確にＳとＰの変換を記述する。
次いで、較正により仮想ペン先の位置を求めることができる。

ペン先４０２を紙の上の知られた位置Ｌ_{ｐｅｎｔｉｐ}に置く。次いでペンを傾けて、カメラ４０３が様々なペンの姿勢で一続きの画像を取り込めるようにする。取り込まれる画像ごとに、変換Ｆ_Ｓ→Ｐを受け取ることができる。この変換から、ペン先の仮想画像の位置Ｌ_{ｖｉｒｔｕａｌ−ｐｅｎｔｉｐ}を得ることができる。
Ｌ_{ｖｉｒｔｕａｌ−ｐｅｎｔｉｐ}＝Ｆ_Ｐ→Ｓ（Ｌ_{ｐｅｎｔｉｐ}）
そして
Ｆ_Ｐ→Ｓ＝１／Ｆ_Ｓ→Ｐ
となる。

あらゆる画像から受け取るＬ_{ｖｉｒｔｕａｌ−ｐｅｎｔｉｐ}を平均することにより、仮想ペン先Ｌ_{ｖｉｒｔｕａｌ−ｐｅｎｔｉｐ}の正確な位置を判定することができる。

この時点で仮想ペン先Ｌ_{ｖｉｒｔｕａｌ−ｐｅｎｔｉｐ}の位置が分かっている。取り込まれた画像から、変換Ｆ_Ｓ→Ｐも得ることができる。そして、この情報を使用して、実際のペン先の位置Ｌ_{ｐｅｎｔｉｐ}を求めることができる。
Ｌ_{ｐｅｎｔｉｐ}＝Ｆ_Ｓ→Ｐ（Ｌ_{ｖｉｒｔｕａｌ−ｐｅｎｔｉｐ}）

符号化
符号化する画像は、文書をスキャンするスキャナから取り込むことができる。あるいは、符号化する画像は、固定された電子形態（例えば読み取りの特権のみを有する固定された表示サイズの電子ファイル）とすることもできる。カメラの位置を判定するために文書は実際に修正できるようにしてもよいが、符号化したバージョンは、一般に、カメラ４０３から見た文書に対応することができる。そうでない場合でも相関はなお生じることができるが、コードブックが、スキャンした文書とカメラから取り込んだ画像との類似性ほど正確でないものになる可能性がある。

画像を解析してサブイメージにする。各サブイメージを容易に検索できる形態に符号化する。サブイメージは、カメラ４０３からの出力と同じサイズに設定することができる。これにより、カメラ４０３からの出力とコードブックに格納された情報とのサーチ比較がおよそ等しくなるという利益が得られる。この結果得られる位置に続く処理を行って、スキャンされた画像に基づいて入力画像上の注釈の位置を判定するか、かつ／またはコンピューティングシステムのその他の動作を制御することができる。

以下の説明では、コードブックの生成に使用することができるいくつかの異なる符号化のオプションを提示する。以下の符号化法の１つを使用して、ペン４０１の使用中にカメラから取り込まれる画像を符号化してコードブックの情報とカメラからの符号化情報の比較を容易にすることもできる。各種の符号化システムが可能である。ここでは３つのシステムを提供するが、この他の符号化技術を使用することも可能である。

単純な符号化
第１のタイプの符号化は、受け取った画像を解析したサブイメージ自体がコードとして働くように使用することを含む。図５にこのプロセスの一例を示す。ステップ５０２で入力画像５０１を解析してサブイメージにする。このサブイメージ（５０３で表す）を画像５０１中の各自の位置に関連付け、コードブック５０５に格納する。コードブック５０５のサーチ時に、カメラ４０３からの画像が、コードブック５０５に格納された１つまたは複数のサブイメージと比較される。この比較から１つまたは複数の候補を得ることができる。さらに、ペン先４０２の位置を判定することができる。

サイズ縮小符号化
別の符号化の例には、各サブイメージのサイズを縮小することが含まれる。初めに画像６０１を受け取る。画像６０１は、画像ブロックＩと表すことができる。事例によっては、画像ブロックＩに閾値を適用することにより画像ブロックＩをバイナリ画像Ｉ_ｂに変換することができる。次いで、各サブイメージのサイズをｍ＊ｍとしてサブイメージをまとめてＫ_ｘ＊Ｋ_ｙと表すことができる。図６の例ではｍ＝４である。別の例ではｍ＝３２であり、この場合は図４Ｂのグリッドと同様にサブイメージを３２＊３２のグリッドに分割する。

さらに、各サブイメージの再分割ｍは、カメラの画像解像度に直接対応する必要はない。例えば、再分割ｍは、より小さな再分割の組み合わせまたは部分的な組み合わせとすることができる。ここでは、より小さな再分割数が３２であり、ｍ＝４（図６から）である場合、各再分割ｍは８ピクセルを含むことができる。

次いで、再分割の内容の規則に基づく分析または閾値６０４（例えば真偽テスト）を適用することができる。サブイメージ６０３の各再分割に適用する閾値または規則の例には、各再分割中に連続した３つの白いカラムがあるかどうかの判定を含むことができる。言うまでもなく、この例の代わりに、あるいはこの例と併用してこの他の規則に基づく分析を使用することができる。

この分析６０４の結果に基づき、行列６０５を生成することができる。行列６０５は、サブイメージ６０３の各再分割に閾値６０４を適用した結果の一例を示す。Ｋ行列（幅Ｋ_ｘ、高さＫ_ｙ）は、値０／１を有し、１は真を意味し、０は偽を意味する。この結果得られるＫ行列は、画像ブロックＩの

と表すことができ、ｋ−ｗｉｎは、この符号化法を指す別の方式である。

は、行列６０５としてのサブイメージマップの一例を用いると等式（１）と表すことができる。

このタイプの符号化は、第１の行列と、カメラ４０３から取り込まれた画像から形成された行列との距離を求めることによってサーチすることができる。２つの行列間の距離は、等式（２）で表す２つの行列のハミング距離である。

（２） Ｄｉｓｔ^ｈａｍ（Ｃ_１，Ｃ_２）＝Ｈａｍ（Ｃ_１，Ｃ_２）
Ｈａｍ（ａ，ｂ）が、行列ａと行列ｂとのハミング距離になる。

半径方向の符号化
半径方向の符号化と称する別のタイプの符号化について図７を参照して説明する。画像７０１を受け取り、ステップ７０２で解析してサブイメージにする。７０３で、サブイメージの中心を中心にして方向ＳにベクトルＴだけ回転することによりサブイメージをサンプリングする。７０３のサブイメージで得られる情報をアンラップ（ｕｎｗｒａｐｐｅｄ）画像７０４によって表す。すなわち、７０３のサブイメージブロックは、極座標でサンプリングする。

７０３のサブイメージの中心ピクセル（あるいは領域）を原点として扱い、サンプリング角度をＳ、サンプリングベクトルの大きさをＴとする。３２×３２ピクセルの領域の場合はＳ＝３２、Ｔ＝１６になる。

各サンプリング点（ｔ，ｓ），ｔ＝０，１，．．．，Ｔ−１，ｓ＝０，１，．．．，Ｓ−１で、デカルト座標におけるその位置は、（ｘ_ｔ，ｓ，ｙ_ｔ，ｓ）になり、ｘ_ｔ，ｓおよびｙ_ｔ，ｓは、それぞれ等式（３）と（４）によって表される。

点（ｔ，ｓ）のグレーレベル値は、等式（５）によって表される。
（５） Ｇ_ｔ，ｓ＝Ｆ（ｘ_ｔ，ｓ，ｙ_ｔ，ｓ）
Ｆは、等式（６）によって表される２Ｄのガウスフィルタである。

Ｐ（ｘ，ｙ）は、位置（ｘ，ｙ）のピクセルのグレーレベル値を意味し、括弧「［］」は、実際の値の最も近い整数を意味し、σおよびｑはフィルタパラメータである。フィルタパラメータの例は、σ＝１．１５、ｑ＝１などである。これらの値は、アルゴリズムを経験的にテストして所与の環境に対してどの値が最も有効であるかを判定することによって求める。

７０３に示すように極座標を使用してサブイメージブロックを分析すると、その分析結果は、カメラフレームとサブイメージとの回転の差を扱う際により高い堅牢性を有する。コードブックの情報と比較するカメラ画像の回転は、７０４で画像の移動に変換する、取り込まれたカメラ画像の回転ほど複雑な問題ではない。

７０４の画像は、表７０５に示すように、ベクトルＴにわたる各角度Ｓについて２進表現に変換することができる。この度は、ｓの範囲が０からＳ−１のとき２π・ｓ／Ｓになる。画像またはサブイメージ（７０１、７０２、７０３、７０４）は、最初にスキャンしたとき、あるいは受け取ったとき、取り込んだときに既にバイナリ画像に変換していない場合は、複数の位置でバイナリ（白黒）画像に変換することができる。

グレーレベル値の行列｛Ｇ_ｔ，ｓ｝（ｔ＝０，１，．．．，Ｔ−１、ｓ＝０，１，．．．，Ｓ−１）は、グレーレベル行列の値に閾値を適用することにより、バイナリ行列

（等式（７）に示す）に変換することができる。

次いでこのコードをコンパイルして、より大きな画像中のサブイメージの位置に関する情報を含むコードブックにすることができる。

コードブックにある異なるコードでカメラ画像の位置を判定するために、カメラ画像ともう一方のコード表現との距離を求めることができる。候補までの最も短い距離または最も短い距離のセットが、各種位置のうち最良の選択肢を表すことができる。この距離は、カメラ画像と現在のサブイメージとのハミング距離によって計算することができる。

先に述べたように、カメラから取り込まれた画像からの距離を、コードブックの１つまたは複数のコードセグメントと比較することができる。半径方向のコードには、一般的なハミング距離と回転不変距離の少なくとも２つのタイプの距離を使用することができる。この他の距離の判定を使用することもできる。

等式（８）に示すように、一般的なハミング距離を使用して、コードブックのコードと、カメラ画像に関連付けられたコードとの距離を求めることができる。

（８） Ｄｉｓｔ^ｈａｍ（Ｃ_１，Ｃ_２）＝Ｈａｍ（Ｃ_１，Ｃ_２）
使用することが可能な別のタイプの距離には、回転不変距離がある。回転不変距離を使用することの利点は、等式（９）に示すようにカメラの回転に対応することである。

は、等式（１０）に示すように定義される。

コードブック生成
コードブックは、画像から取られ、その画像中の各自の位置に関連付けられたサブイメージに関連するコードを格納する。コードブックは、カメラ４０３で画像を取り込む前に作成することができる。あるいは、コードブックは、使用中に作成するか、あるいは少なくとも追加することもできる。例えば、カメラは動作中に画像を取り込むことができる。５０１、６０１、および７０１で示すように、ユーザが既にある情報の上に書き込みをするだけの場合は、ここで説明するようにコードブックを使用して、カメラによって取り込まれた画像の位置を判定することができる。しかし、ユーザが新しい注釈を上書きした場合は、コードブックは上書きの前ほど正確なものではなくなる。したがって、ペン４０１で新しい注釈が追加されると、その注釈をコードブックに組み込んで、後に書き込まれる注釈がその画面上の表現とより正確に相関するようにする。

コードブックの生成は以下のように行うことができる。５０３、６０３、および７０３に示すサブイメージを符号化法によって符号化する。次いで、位置とコードの対を編成してコードブックを作成する。少なくとも２タイプの編成法を使用してコードブックを作成することができる。無論、他の方法を使用してコードブックを作成することもできる。これら２つの方法は、単なる例証的な例として提示する。

第１の方法は、位置とコードの対を線形のリストに入れるものであり、リスト中で各コードはコードと位置のシーケンスを含み、すべての位置がそのコードにマッピングされる。するとコードブックは等式（１１）のように表すことができる。
（１１） Ω＝｛Ψ_ｉ，ｉ＝１，２，．．．，Ｎ_Ω｝
Ψは、Ψ＝｛Ｃ_Ψ，Ｐ_Ψ｝と定義され、Ｐ_Ψは、その文書のビットマップ中にあるすべての位置のセットであり、そのコードは等式（１２）に示すようにＣである。
（１２） Ｐ_Ψ＝｛ｐ_ｉ｜位置ｐｉにおけるコードはＣ_Ψ，ｉ＝１，２，．．．｝
次いで、セットΩを各メンバーΨのコードによってアルファベット順にソートすることができ、それにより線形リストタイプのコードブックが得られる。

第２の方法は、対応する位置を有するコードを２分木に入れるものである。
この２分木は、図８に表すようにコード間のハミング距離に基づくことができる。初めに、コードセットΩ全体の重心Ｃｃ_０を見つける。次に、重心Ｃｃ_０までのハミング距離が最大のコードＣ_０を見つける。次いで、コードＣ_０との距離が最大のコードＣ_１を見つける。

次いでコードセットＣを２つのサブセットΩ_０とΩ_１に分割する。Ω_０の内容は等式（１３）で表すことができ、Ω_１の内容は等式（１４）で表すことができる。

次いで、サブセットΩ_０およびΩ_１について、重心を見つけ、重心までの距離が最大のコードを見つけ、重心から最も遠いそのコードまでの距離が最大のコードを見つけ、そしてサブセットを分割するステップをサブセットのメンバーの数が１になるまで繰り返す。

候補のサーチ
カメラから取り込まれたフレームの位置の候補は、コードブックをサーチすることによって決定することができる。カメラによって取り込まれた各フレームＩｉに対して、ペン先４０２の候補位置を次のように求めることができる。
１）コードブックの生成に使用した方法と同じ符号化法でカメラからのフレームＩｉを符号化する。
２）符号化したフレームＥ_Ｉｉとコードブックの情報を比較する。符号化フレームＥ_Ｉｉとコードブックの符号化された情報との距離を求める。符号化フレームＥ_Ｉｉとの距離が最小であるコードブック中の符号化情報を位置の候補として、あるいは位置の候補の１つとして使用する。これらの候補から、最も一致するものを選択する。

最良の候補の選択は、いくつかの異なる分析を含むことができる。初めに、最も近く一致する（コードＥ_Ｉｉとの距離が最小）の候補を選び出すことができる。あるいは、最も最近の候補セットと最近の候補のシーケンスを比較し、時間の経過にわたってフレームを比較することもできる。この比較により、互いに最も近い一連の位置が得られるはずである。この結果が予想されるのは、ペン先が時間の経過に伴い可能な限りわずかに移動したことを示すためである。これに代わる結果は、ペン先が非常に短い時間の間にそのページ内でジャンプしたことを示す可能性がある（この可能性は先の例に比べて低い）。

コードブックのサーチには以下の方法を使用することができる。取り込まれた各画像Ｉについて、コードＣ_Ｉで、等式（１５）のように最も一致するコードセットＳ（Ｃ_Ｉ）を定義する。

半径方向のコードを使用する場合、距離関数はＤｉｓｔ^ｒ−ｉ（・，・）にすべきである。
Ｎ_ｓ＞Ｎ_{ｔｈｒｅｓｈ}である場合は、Ｓ（Ｃ_Ｉ）の距離がより小さいＮ_{ｔｈｒｅｓｈ}コードだけを保持し、カメラの性能に応じてｄ_{ｔｈｒｅｓｈ}およびＮ_{ｔｈｒｅｓｈ}を選択する。
画像Ｉの位置候補のセットを等式（１６）で表すことができる。

特許請求の範囲を使用して本発明を定義したが、本発明はここに記載する要素およびステップを任意の組み合わせまたはサブコンビネーションで包含することを意図するため、この特許請求の範囲は例証的なものである。したがって、本発明を定義する任意数の代替の組み合わせがあり、その組み合わせは、この説明、特許請求の範囲、および図面を含む本明細書の１つまたは複数の要素を各種の組み合わせまたはサブコンビネーションで組み込む。当業者には、本明細書に鑑みて、本発明の態様の代替の組み合わせを単独で、あるいはここに定義する１つまたは複数の要素またはステップと組み合わせて、本発明または本発明の一部の修正形態または代替形態として利用できることは明らかであろう。本明細書に含まれる記載する本発明の説明は、そのような修正形態および代替形態をすべて包含することを意図することができる。

本発明の実施形態と併せて使用することができるコンピュータを示す略図である。 本発明の実施形態により、受け取った画像を解析し、コードブックを作成するプロセスを示す流れ図である。 本発明の実施形態により、カメラからの画像の１つまたは複数の可能な位置を判定するプロセスを示す流れ図である。 本発明の実施形態によるペンおよび画像取り込みシステムの可能なビューを示す図である。 本発明の実施形態によるペンおよび画像取り込みシステムの可能なビューを示す図である。 本発明の実施形態により画像を符号化する第１のプロセスを示す説明図である。 本発明の実施形態により画像を符号化する第２のプロセスを示す説明図である。 本発明の実施形態により画像を符号化する第３のプロセスを示す説明図である。 本発明の実施形態によるコードブックの構築を示す説明図である。

符号の説明

１００、１０９ コンピュータ
１０１ キーボード
１０２ ポインティングデバイス
１０６ シリアルポートインタフェース
１０７ モニタ
１０８ ビデオアダプタ
１１０ 処理装置
１１１ メモリ記憶装置
１１２ ＬＡＮ
１１３ ＷＡＮ
１１４ ネットワークインタフェース
１１５ モデム
１２０ システムメモリ
１３０ システムバス
１４０ ＲＯＭ
１５０ ＲＡＭ
１６０ ＢＩＯＳ
１６５ ペンデジタイザ
１６６ スタイラス
１７０ ハードディスクドライブ
１８０ 磁気ディスクドライブ
１９０ 磁気ディスク
１９１ 光ディスクドライブ
１９２ 光ディスク
１９３ 磁気ディスクドライブインタフェース
１９４ 光ディスクドライブインタフェース
１９５ オペレーティングシステム
１９６ アプリケーションプログラム
１９７ プログラムモジュール
１９８ プログラムデータ
４０１ ペン
４０２ ペン先
４０３ カメラ
４０４、４１０、５０１、６０１、７０１、７０４ 画像
４０６ センサ（プロセッサ）
４０７ 表面
４０８ レンズ
４０９ イメージ平面
４１１ 画像取り込みセンサ
５０３、６０３、７０３、７０４ サブイメージ
５０５ コードブック
６０５ 行列

Claims (7)

1. 文書の画像を符号化する符号化システムであって、
   前記文書の前記画像を受け取る入力と、
   前記画像をサブイメージに解析するパーサと、
   前記サブイメージを複数のコードに符号化するエンコーダと、
   前記画像との関係で前記サブイメージの位置に関連付けた前記複数のコードを格納するストレージとを備え、
   前記ストレージはコードブックを包含し、
   前記ストレージは前記コードブック内の前記複数のコードを２分木に格納し、
   該２分木に格納することは、
   前記コードブックを初期コードセットとして、１つの第１のコードセットと、該第１のコードセットとは異なる１つの第２のコードセットとに分離することによって開始し、
   該分離することは、
   （ａ）前記初期コードセットの重心を見つけ、
   （ｂ）前記重心から最も遠い、前記初期コードセットにおける１つの第１のコードを見つけ、
   （ｃ）前記第１のコードから最も遠い、前記初期コードセットにおける、前記第１のコードとは異なる１つの第２のコードを見つけ、
   （ｄ）前記初期コードセットにおける前記複数のコードのうち、前記第２のコードよりも前記第１のコードに近い１つまたは複数のコードをすべて含む前記第１のコードセットと、前記初期コードセットにおける前記複数のコードのうち、前記第１のコードよりも前記第２のコードに近い１つまたは複数のコードをすべて含む前記第２のコードセットとに分離し、
   前記２分木に格納することは続いて、
   前記初期コードセットの代わりに、分離した前記第１のコードセットと前記第２のコードセットとに対してそれぞれ、前記（ａ）〜前記（ｄ）までを、分離されるコードセットに含まれるコードの数が１になるまで再帰的に繰り返す
   ことを特徴とする符号化システム。
2. 前記エンコーダは、前記サブイメージの部分に基づいて符号化することを特徴とする請求項１に記載の符号化システム。
3. 前記エンコーダは、前記サブイメージの半径方向の分析に基づいて符号化することを特徴とする請求項１に記載の符号化システム。
4. コードブックを作成するシステムであって、
   画像のサブイメージに関連付けられた複数のコードを受け取る入力と、
   前記画像との関係で前記サブイメージの位置に関連付けられた前記複数のコードを編成して前記コードブックにするプロセッサと、
   前記コードブックを格納するストレージとを備え、
   前記プロセッサは前記コードブック内の前記複数のコードを２分木に編成し、
   該２分木に編成することは、
   前記コードブックを初期コードセットとして、１つの第１のコードセットと、該第１のコードセットとは異なる１つの第２のコードセットとに分離することによって開始し、
   該分離することは、
   （ａ）前記初期コードセットの重心を見つけ、
   （ｂ）前記重心から最も遠い、前記初期コードセットにおける１つの第１のコードを見つけ、
   （ｃ）前記第１のコードから最も遠い、前記初期コードセットにおける、前記第１のコードとは異なる１つの第２のコードを見つけ、
   （ｄ）前記初期コードセットにおける前記複数のコードのうち、前記第２のコードよりも前記第１のコードに近い１つまたは複数のコードをすべて含む前記第１のコードセットと、前記初期コードセットにおける前記複数のコードのうち、前記第１のコードよりも前記第２のコードに近い１つまたは複数のコードをすべて含む前記第２のコードセットとに分離し、
   前記２分木に格納することは続いて、
   前記初期コードセットの代わりに、分離した前記第１のコードセットと前記第２のコードセットとに対してそれぞれ、前記（ａ）〜前記（ｄ）までを、分離されるコードセットに含まれるコードの数が１になるまで再帰的に繰り返す
   ことを特徴とするシステム。
5. コードブックをサーチするシステムであって、
   画像のサブイメージに関連付けられた複数のコードと、前記画像の前記サブイメージの位置に関連する情報とを有するコードブックを受け取る第１の入力と、
   ペンに付随するカメラから画像を受け取る第２の入力と、
   前記カメラからの前記画像を符号化し、前記カメラ画像に関連付けられたコードを出力するエンコーダと、
   前記カメラ画像に前記関連付けられたコードと類似する１つまたは複数のコード候補を求めて前記コードブックをサーチするプロセッサと、
   前記１つまたは複数のコード候補に関連付けられた１つまたは複数の位置を出力する出力とを備え、
   前記プロセッサは前記コードブック内の前記コードを２分木に編成し、
   該２分木に編成することは、
   前記コードブックを初期コードセットとして、１つの第１のコードセットと、該第１のコードセットとは異なる１つの第２のコードセットとに分離することによって開始し、
   該分離することは、
   （ａ）前記初期コードセットの重心を見つけ、
   （ｂ）前記重心から最も遠い、前記初期コードセットにおける１つの第１のコードを見つけ、
   （ｃ）前記第１のコードから最も遠い、前記初期コードセットにおける、前記第１のコードとは異なる１つの第２のコードを見つけ、
   （ｄ）前記初期コードセットにおける前記複数のコードのうち、前記第２のコードよりも前記第１のコードに近い１つまたは複数のコードをすべて含む前記第１のコードセットと、前記初期コードセットにおける前記複数のコードのうち、前記第１のコードよりも前記第２のコードに近い１つまたは複数のコードをすべて含む前記第２のコードセットとに分離し、
   前記２分木に編成することは続いて、
   前記初期コードセットの代わりに、分離した前記第１のコードセットと前記第２のコードセットとに対してそれぞれ、前記（ａ）〜前記（ｄ）までを、分離されるコードセットに含まれるコードの数が１になるまで再帰的に繰り返す
   ことを特徴とするシステム。
6. コードブックを作成する方法であって、
   サブイメージに関する符号化された複数の情報を受け取るステップと、
   前記サブイメージが、該サブイメージより大きな画像中のどこに位置するかに関する位置情報を受け取るステップと、
   前記符号化された複数の情報を前記位置情報に関連付けるステップと、
   前記関連付けた情報を前記コードブックとして２分木に格納するステップとを有し、
   前記コードブックとして前記２分木に格納するステップは、
   （ａ）前記符号化された複数の情報における重心を見つけるステップと、
   （ｂ）前記重心から最も遠い前記符号化された複数の情報における１つの第１のコードを見つけるステップと、
   （ｃ）前記第１のコードから最も遠い前記符号化された複数の情報における、前記第１のコードとは異なる１つの第２のコードを見つけるステップと、
   （ｄ）前記符号化された複数の情報を、前記第２のコードより前記第１のコードに近い第１のコードセットと、前記第１のコードより前記第２のコードに近い、前記第１のコードセットとは異なる第２のコードセットとの２つのコードセットに分離するステップであって、前記第１のコードセットは、前記符号化された複数の情報のうち、前記第２のコードより前記第１のコードに近い１つまたは複数のコードをすべて含み、前記第２のコードセットは、前記符号化された複数の情報のうち、前記第１のコードより前記第２のコードに近い１つまたは複数のコードをすべて含む、分離するステップと、
   （ｅ）前記コードブックの代わりに、分離した各コードセットに対してそれぞれ、前記ステップ（ａ）から前記ステップ（ｄ）までを、分離されるコードセットに含まれるコードの数が１になるまで再帰的に繰り返すステップと
   を含むことを特徴とする方法。
7. 前記２分木に格納するために前記符号化された情報のサイズを縮小するステップをさらに含むことを特徴とする請求項６に記載の方法。

Images