(57)【要約】方法は、位置復号用の装置において、センサによって記録されたように位置コード化パターンの画像のシーケンスから位置のシーケンスを抽出するために動作する。コンピュータ読み取り可能記憶媒体上のコンピュータプログラムとして具現化されてよい該方法は、少なくとも一つの基準位置（Ｐ１、Ｐ１’）を検索するステップと、該画像のそれぞれから取得される情報を、該基準位置（複数の場合がある）との既定の直接的または間接的な空間関係のある該位置コード化パターンの既知の部分集合を表す、対応するパターン基準領域（ＭＡ）にマッチングすることよってのみ該位置のシーケンスを抽出するステップに関する。
2006525593.tif 000002
【特許請求の範囲】
【請求項１】
センサによって記録されるように、位置のシーケンスが位置コード化パターンの画像のシーケンスから抽出される位置復号のための方法であって、
少なくとも一つの基準位置を取り出すステップと、
前記画像のそれぞれから得られる情報を、前記基準位置に既定の空間関係のある位置コード化パターンの既知の部分集合を表す、対応するパターン基準領域とマッチングすることによってのみ位置の前記シーケンスを抽出するステップと、
を特徴とする方法。
【請求項２】
位置の前記シーケンスの中の各位置が、前記パターン基準領域内の前記情報と前記パターン基準領域の間の一致の相対位置を決定し、前記相対位置によって前記空間関係を調整し、それにより前記位置を引き出すことによって抽出される請求項１に記載の方法。
【請求項３】
各画像に前記パターン基準領域を生成するステップとをさらに備える請求項１または２に記載の方法。
【請求項４】
前記空間関係が予測位置により指定され、前記方法が、前記少なくとも一つの基準位置に基づいて前記予測位置を推定するステップを備える任意の前記請求項に記載の方法。
【請求項５】
前記パターン基準領域が前記予測位置に対して既定の位置関係をもって生成される請求項４に記載の方法。
【請求項６】
前記予測位置が位置コード化パターンの既知の部分集合に含まれる請求項５に記載の方法。
【請求項７】
推定する前記ステップが画像ごとに達成され、予測位置のシーケンスを生成する請求項４から６のどれか一つに記載の方法。
【請求項８】
予測位置の前記シーケンスが、マッチングにより抽出する前記ステップによって、位置の前記シーケンスに変換される請求項７に記載の方法。
【請求項９】
各予測位置が前記少なくとも一つの基準位置及び／または位置の前記シーケンスから選択される少なくとも二つの先行する位置に基づいて推定される請求項４から８のどれか一つに記載の方法。
【請求項１０】
前記予測位置が、前記少なくとも二つの先行する位置の多項式補外によって推定される請求項９に記載の方法。
【請求項１１】
マッチングにより抽出する前記ステップとは別の方法で前記位置コード化パターンの画像に基づいて位置を計算することによって各基準位置が取り出される任意の前記請求項に記載の方法。
【請求項１２】
位置を計算する前記ステップが、画像の前記シーケンスに先行する隔離された画像からシンボルデータを抽出することと、位置コード化パターンの根本的なコード化データを含む一つまたは複数のデータ構造内で、前記シンボルデータを使用して一つまたは複数のルックアップ動作を達成することによって位置データを引き出すことと、及び／または絶対位置の明示的な計算のために数式に前記シンボルまたは位置データを入力することとを含む請求項１１に記載の方法。
【請求項１３】
前記少なくとも一つの基準位置を位置の前記シーケンスとマージするステップとをさらに備える任意の前記請求項に記載の方法。
【請求項１４】
前記少なくとも一つの基準位置を更新または置換するために、取り出す前記ステップが間欠的に達成され、前記このようにして取り出された基準位置は、画像の以後のシーケンスについてマッチングすることによって抽出する以後のステップで使用される任意の前記請求項に記載の方法。
【請求項１５】
画像の前記シーケンスの内で個々の画像のために、対応するパターン基準領域が、前記個々の画像の位置コード化パターンによって表される位置に複数のそれぞれの候補を定める複数の部分的な領域を含む任意の前記クレームに記載の方法。
【請求項１６】
マッチングによって前記抽出するステップが、前記個々の画像から取得される情報を、対応するパターン基準領域内に含まれる前記複数の部分的な領域のそれぞれと比較することを含む請求項１５に記載の方法。
【請求項１７】
マッチングすることによって抽出する前記ステップが、画像の前記シーケンスの内の個々の画像について、前記比較するステップが前記個々の画像から得られる情報と前記複数の部分的な領域の間の対応を示す、前記複数のそれぞれの候補の一つを選択することを含む請求項１６に記載の方法。
【請求項１８】
前記位置コード化パターンが複数のマークを備え、それぞれのマークが少なくとも一つの次元で少なくとも二つの異なる値の一方をコード化する任意の前記請求項に記載の方法。
【請求項１９】
マッチングによって抽出する前記ステップが、前記個々の画像の中に含まれ、前記サブエリア内のマークごとに一つの行列要素を含む位置コード化パターンのサブエリアを表す確率行列を生成することによって画像の前記シーケンスの間で個々の画像から前記情報を取得することを含み、各行列要素がそれのマークの最もありそうな推定値を表す値、またはそれのマークには何の値も推定されないことを表す値のどちらかを記憶するように適応される請求項１８に記載の方法。
【請求項２０】
最もありそうな推定値を表す前記値が整数値である請求項１９の方法。
【請求項２１】
各マークが第一の次元で二進値を、第二の次元で二進値をコード化し、第一の確率行列が生成され、これが前記第一の寸法の前記マークの値について生成され、第二の確率行列が前記第二の次元のマークの値について生成される請求項１９または２０に記載の方法。
【請求項２２】
マッチングによって抽出する前記ステップが、前記または各確率行列を、前記対応するパターン基準領域内に含まれる前記複数の部分的な領域のそれぞれと比較することを含む請求項１９から２１のどれか一つ、及び請求項１６から１７のどれか一つに記載の方法。
【請求項２３】
位置コード化パターンのそれぞれの次元が周期性の主数列のシフトに基づいており、第一の所定の長さまたはさらに長い任意の部分列が前記周規制の主数列内の明白に決定される位置を有し、位置コード化パターンの前記主数列の組の間のシフトの差異を表す差数のシーケンスに基づいて、差数の前記シーケンスの、第二の所定の長さまたはさらに長い任意の部分列が差数の前記シーケンス内に明らかに決定される位置を有し、マッチングによって抽出する前記ステップが、
前記パターン基準領域について差数の第一の集合を取得するステップと、
前記確率行列または各確率行列から差数の第二の集合を取得するステップと、
差数の前記第二の集合を、差数の前記第一の集合にマッチングするステップと、
前記マッチングステップから、一致から前記寸法で前記位置コード化パターンの位置を抽出するステップと、
を含む請求項１９から２１のどれか一つに記載の方法。
【請求項２４】
差数の第二の集合を取得する前記ステップが、
前記または各確率行列のそれぞれの行または列を、前記行または列の主数列位置を推定するために前記主数列とマッチングすることと、
前記または各確率行列の行または列の組について、推定された主数列位置を差し引くことによって前記第二の集合の差数を引き出すことと、
含む請求項２３に記載の方法。
【請求項２５】
位置の前記シーケンスが電子手書きツールを手段として実行される手書きストロークの少なくとも一部を表す任意の前記クレームに記載の方法。
【請求項２６】
画像の前記シーケンスが電子手書きツールを手段として記録され、前記予測位置が、前記少なくとも一つの基準位置と、所定のまたは検出された移動の方向、前記手書きツールの速度または加速度の少なくとも一つに基づいて推定される請求項４から１０のどれか一つに記載の方法。
【請求項２７】
センサによって記録される、位置コード化パターンの部分的な領域から取得される情報に基づいて位置を決定することによる位置復号のための方法であって、前記位置コード化パターンが複数のマークを備え、各マークは少なくとも一つの次元で少なくとも二つの異なる値の一方をコード化し、
前記部分的な領域内のマークごとに一つの行列要素を含む確率行列を生成するステップであって、各行列要素がそれのマークの最もありそうな推定値を表す値、またはそれのマークについて値が推定されていないことを表す値のどちらかを記憶するように適応されるステップと、
前記確率行列を、位置コード化パターンが前記位置コード化パターンのパターン基準領域内でどのように構成されるのかについての情報とマッチングするステップであって、前記パターン基準領域が前記部分的な領域より広く、前記部分的な領域を含むステップと、
決定される前記位置として、前記マッチングステップが前記確率行列と前記パターン基準領域の間の対応を示す、前記パターン基準領域により画定される前記位置の内の一つを選択するステップと、
によって特徴付けられる方法。
【請求項２８】
最もありそうな推定値を表す前記確率行列の行列要素の前記値が整数値である請求項２７に記載の方法。
【請求項２９】
各マークが第一の次元の二進値と、第二の次元の二進値をコード化し、前記確率行列が前記第一の次元の前記マークの前記値のための第一の確率行列、及び前記第二の次元の前記マークの前記値のための第二の確立行列とによって形成される請求項２７または２８に記載の方法。
【請求項３０】
コンピュータ内で実行されると、前記コンピュータに、請求項１から２６または請求項２７から２９のどれか一つによる方法を実施させるプログラムコードを備えるコンピュータプログラム。
【請求項３１】
コンピュータ内で実行されると、前記コンピュータに、請求項１から２６または請求項２７から２９のどれか一つによる方法を実行させるコンピュータプログラムが記憶されるコンピュータ読み取り可能記憶媒体。
【請求項３２】
センサにより記録されるように位置コード化パターンの画像のシーケンスから位置のシーケンスを抽出するように適応される信号処理装置を備える位置復号のための装置であって、前記信号処理装置がさらに、
少なくとも一つの基準位置を取り出し、
前記画像のそれぞれから取得される情報を、前記基準位置に既定の空間関係のある前記位置コード化パターンの既知の部分集合を表す、対応するパターン基準領域とマッチングすることによってのみ位置の前記シーケンスを抽出する、
ようにさらに適応されることを特徴とする位置復号のための装置。
【請求項３３】
センサによって記録されるような、位置コード化パターンの部分的な領域から取得される情報に基づいて、位置を決定するように適応される信号処理装置を備える位置復号のための装置であって、前記位置コード化パターンが複数のマークを備え、各マークが少なくとも一つの次元で少なくとも二つの異なる値の内の一方をコード化し、
前記信号処理装置が、
前記部分的な領域内のマークごとに一つの行列要素を含む確率行列を生成し、各行列要素が、それのマークの最もありそうな推定値を表す値、またはそれのマークに値が推定されなかったことを表す値のどちらかを記憶するように適応され、
前記確率行列を、前記位置コード化パターンが前記位置コード化パターンのパターン参照領域内でどのように構成されるのかについての情報とマッチングし、前記パターン基準領域が前記部分的な領域より広く、前記部分的な領域を含み、
決定される前記位置として、前記マッチングステップが前記確率行列と前記パターン基準領域の間の対応を示す前記パターン基準領域により画定される前記位置の内の前記一方を選択する、
ようにさらに適応されることを特徴とする位置復号のための装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概して位置コード化パターンの復号（ｄｅｃｏｄｉｎｇ）に関し、さらに詳細には、位置のシーケンスがセンサにより記録されるように位置コード化パターンの画像のシーケンスから抽出される位置復号のための方法に関する。
【０００２】
本発明は位置コード化パターンを復号するために使用できる装置、コンピュータプログラム及び記憶媒体にも関する。
【背景技術】
【０００３】
所定の最小サイズの位置コード化パターンの部分的な領域のための位置コード化パターンの中の絶対位置が、該部分的な領域内の情報及び所定のアルゴリズムによって計算できるというプロパティを有する位置コード化パターンは既知である。このような位置コード化パターンの例は、それぞれの位置がシンボルによってコード化される米国第５,４７７,０１２号（Ｏ．Ｓｅｋｅｎｄｕｒ）、及びそれぞれの位置が複数のシンボルによってコード化される、国際公開第９２／１７８５９号パンフレット（ヒューレットパッカード社（Ｈｅｗｌｅｔｔ Ｐａｃｋａｒｄ Ｃｏ．）、米国第６,５７０,１０４号（Ａｎｏｔｏ ＡＢ）、米国第６,６７４,４２７号（Ａｎｏｔｏ ＡＢ）、米国第６,６６７,６９５号（Ａｎｏｔｏ ＡＢ），米国第２００３／００１２４５５号（Ａｎｏｔｏ ＡＢ）及び米国第５,９７３,１１０号（ゼロックス社（Ｘｅｒｏｘ Ｃｏｒｐ）に開示されている。
【０００４】
この種の位置コード化パターンは、例えば、位置コード化パターンを与えられたベース上のユーザ装置によって手で作成される、及び／または描画される情報のデジタル記録のために使用できる。ユーザ装置を移動する間、位置コード化パターンの画像はユーザ装置の先端で局所的に連続記録される。画像のそれぞれの中の一つまたは複数のシンボルが位置に復号される。該復号された位置はともにユーザ装置のベース上での移動のデジタル記述を構成する。
【０００５】
記録された画像の中の位置コード化パターン（ｐｏｓｉｔｉｏｎ−ｃｏｄｉｎｇｐａｔｔｅｒｎ）はさまざまな方法で復号できる。例えば、前述の米国第２００３／００１２４５５号は、位置コード化パターンの記録領域内で特定されるシンボルが、複数の異なる可能な復号値のどれかを取る確率（ｐｒｏｂａｂｉｌｉｔｉｅｓ）を計算することを必要とする復号方法を開示している。これらの確率は、確率行列の中の実（流動的な精度（ｆｌｏａｔｉｎｇ  ｐｒｅｃｉｓｉｏｎ））数として記憶され、該特定されたシンボルを位置コード化パターンの中の位置の座標に復号するための異なる可能な復号値とともに使用される。
【０００６】
前述された米国第６,６７４,４２７号及び米国第６,６６７,６９５号は、位置コード化パターンの記録された画像から位置を復号するまたは決定する他の方法を開示する。
【０００７】
既知の位置復号方法は、シンボルデータが復号される画像のシーケンスの中の隔離された画像から抽出される、位置データが該位置コード化パターンの根本的なコード化データを含む一つまたは複数のデータ構造の中で該シンボルデータを使用して一つまたは複数のルックアップ動作を達成することによって引き出される、及び／または該シンボルまたは位置データは絶対位置の明示的な計算のための数式に対する入力データとして使用されるという共通の特徴を有していると見なされてよい。
【０００８】
本願の出願日にはまだ公に入手できなかったが、後に米国第２００３／０１２８１９４号として公開された出願人の係属中の米国出願番号第１０／２８２,００１号は、位置コード化パターンの記録領域のための位置が、例えば前述の米国第２００３／００１２４５５号に従って既知の方法で計算される位置復号のための方法を開示している。しかしながら、前記位置について復号エラーが検出される場合、全体としての該位置について、またはそれの座標の内の一つについて、追加の演算が「最後の手段」として実行される。つまり該記録領域から求められる情報は、位置コード化パターンが無事に復号された近傍位置の周辺の一致領域においてどのように構成されるのかについての情報と比較またはマッチングされる。既知の一致領域の最良の一致部分が選択され、対応する位置が復号済み位置として決定される。このようにして、要約すれば、米国第２００３／０１２８１９４号は、復号が失敗した場合には追加マッチング演算が続けて行われる、記録領域からの位置の計算による復号の必須使用を開示している。
【特許文献１】米国第５,４７７,０１２号
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、位置コード化パターンの記録画像からの位置復号の既知の方法に代替策を提供することである。
【００１０】
さらに具体的には、本発明の目的は、位置コード化パターンの高速で効率的、その上堅牢な復号を可能にすることである。
【００１１】
一般的には、本発明の目的は、少なくとも部分的に、独立クレームによる方法、装置、コンピュータプログラム及び記憶媒体によって達成され、好適実施形態は従属クレームにより定められる。
【００１２】
本発明の第一の態様は、位置のシーケンスがセンサによって記録されるように位置コード化パターンの画像のシーケンスから抽出される、位置符号化のための方法である。該方法は、少なくとも一つの基準位置を検索するステップと、前記画像のそれぞれから取得される情報を、前記基準位置と既定の空間関係にある該位置コード化パターンの既知の部分集合を表す対応するパターン基準領域にマッチングすることによってのみ位置の前記シーケンスを抽出するステップとを含む。
【００１３】
位置の前記シーケンスが前記画像のそれぞれからの情報を前記対応するパターン参照領域にマッチングすることによってのみ抽出されるとは、該方法が、前述のマッチングすることによって抽出する以外の別の方法で位置を計算する試みがなされる任意の前記ステップに基づいていないことを意味する。
【００１４】
位置の前記シーケンスの中のそれぞれの位置は、前記パターン基準領域の中で、前記情報と前記パターン参照領域の一致（ｍａｔｃｈ）の相対的なロケーションを決定することと、前記相対的なロケーションによって前記空間関係を調整し、それにより前記位置を引き出すことにより抽出されることができる。このようにして、位置の該シーケンスは高速且つ効率的な方法で抽出されることができる。
【００１５】
位置コード化パターンの既知の部分集合を表すパターン基準領域は、各画像が復号されるために生成されることができる。代わりに、パターン基準領域は間欠的にのみ生成されてもよく、したがって画像のシーケンスの中の複数の連続画像の復号で使用される。
【００１６】
前記少なくとも一つの基準位置に対するパターン基準領域の既定の空間関係は、各パターン基準領域の空間的なロケーションが基準位置（複数の場合がある）から直接的に定義または計算されるという点で直接的、あるいは空間的なロケーションが一つまたは複数の先行する位置から定められるまたは計算されるという点で間接的のどちらかであってよく、先行する位置とはマッチングの前記ステップにより抽出されたという意味で先行している。このようなそれぞれの先行する位置が、再び参照位置（複数の場合がある）に関して直接的にまたは間接的に、定められた空間的なロケーションを有する。
【００１７】
空間関係は、前記少なくとも一つの参照位置に基づいて推定される予測位置によって、及び前記予測位置への既定の位置関係をもって生成されている前記パターン基準領域によって与えられてよい。好ましくは、予測位置はパターン基準領域によって表されるような位置コード化パターンの既知の部分集合に含まれる。それにより、マッチングは予測位置の周辺で達成されることができる。
【００１８】
予測位置を推定するステップは、次にマッチングにより抽出する前記ステップによって位置の前記シーケンスに変換されてよい予測位置のシーケンスを生成するために画像ごとに達成されることができる。変換は予測位置のグループについて、あるいは以後の予測位置を推定する前に復号位置へのマッチングによって変換される各予測位置によって準じに達成されることができる。
【００１９】
各予測位置は、前記少なくとも一つの基準位置、及び／または位置の前記シーケンスから選択される少なくとも二つの先行する位置に基づいて推定されている。さらに、それぞれの予測位置は、前記少なくとも二つの先行する位置の一次などの多項式の補外によって推定されている。
【００２０】
基準位置は、位置復号または計算の従来の方法に従って前記位置コード化パターンの画像に基づいて位置を計算することによって取り出されている。このような計算は、通常、画像の前記シーケンスに先行する隔離された画像からシンボルデータを抽出することと、前記シンボルデータを使用して、位置コード化パターンの根本的なコード化データを含む一つまたは複数のデータ構造の中で、一つまたは複数のルックアップ動作を達成することによって位置データを引き出すことと、及び／または絶対位置の明示的な計算のための数式に前記シンボルデータまたは位置データを入力することを含む。
【００２１】
取り出すステップは、前記少なくとも一つの基準位置を更新または置換するために間欠に達成されてよく、該このようにして取り出された基準位置（複数の場合がある）は画像の以後のシーケンスのためのマッチングによって抽出する以後のステップで使用されている。取り出しは、固定されたサンプリング間隔で、あるいはこのような取り出しに対するニーズ、または取り出しの機会が検出されるたびに達成されてよい。位置コード化ベース上での書き込み用具の移動をデジタル化する際、単一の手書きストロークは位置の複数の連続するシーケンスによって表現されてよく、それぞれがマッチングにより抽出される。方法は、移動の真の表現を形成するために、位置の前記シーケンス（複数の場合がある）と前記少なくとも一つの基準位置をマージするステップとを適切に含んでよい。
【００２２】
ある実施形態では、画像の前記シーケンスの内の個々の画像のための対応するパターン基準領域は、前記個別画像の位置コード化パターンにより表現される位置に対する複数のそれぞれの候補を画定する複数の部分的な領域を含む。この実施形態では、マッチングによって抽出するステップは前記個々の画像から取得される情報を対応するパターン基準領域に含まれる前記複数の部分的な領域のそれぞれと比較することを含んでよい。抽出するステップは、該比較するステップが前記個々の画像から取得される情報と前記複数の部分的な領域のどれかの間の対応を示す候補を選択することをさらに含んでよい。
【００２３】
位置符号化について前述された方法は、Ａｎｏｔｏ ＡＢによって開発され、例えば米国第６,６７４,４２７号または米国第６，６６７,６９５号に説明される位置コード化パターンのどれかとともに有利に使用できる。したがって、位置コード化パターンは複数のマークを備えてよく、各マークが少なくとも一つの次元で少なくとも二つの異なる値の内の一方をコード化する。
【００２４】
前記種類の位置コード化パターンとともに使用するために適応されるある実施形態では、マッチングによって抽出するステップは、前記個々の画像内に含まれる位置コード化パターンのサブエリアを表現し、前記サブエリア内のマークごとに一つの行列要素を含む、確率行列を生成することにより画像の前記シーケンスの中の個々の画像から前記情報を取得することを含み、各行列要素はそれのマークの最もありそうな推定値を表す値、またはそれのマークには値が推定されていないことを表す値のどちらかを記憶するように適応される。最もありそうな推定値を表す値は、好ましくは整数値である。確率行列で二進などの整数値を使用すると、パターン基準領域との高速且つ効率的なマッチングが可能になる。整数で実行される行列演算は、例えば実数についてより実行するのが速い。
【００２５】
各マークが第一の次元でのバイナリ値と第二の次元でのバイナリ値をコード化する前記種類の位置コード化パターンの場合、第一の確率行列は、前記第一の次元内のマークの値について生成されてよく、第二の確率行列は前記第二の次元のマークの値について生成されている。
【００２６】
ある実施形態では、マッチングにより抽出する前記ステップは、該または各確率行列を対応するパターン基準領域に含まれる前記複数の部分的な領域のそれぞれと比較することを含む。これは、確率行列の一次元内容と、それぞれ等しいサイズとされた部分的な領域の同じ次元の内容の間のビットごとの相関により実行されている。
【００２７】
別の実施形態は、特に位置コード化パターンとともに使用するために適応されており、その各次元は周期的な主数列のシフトに基づいており、前記周期的な主数列の、第一の所定の長さまたはさらに長い任意の部分列は、前記周期的な主数列内に、位置コード化パターンの中の前記主数列の組の間のシフトの差異を表す差数のシーケンスに基づいて明らかに決定された位置を有し、前記差数シーケンスの第二の所定の長さまたはさらに長い任意の部分列は前記差数シーケンス内に明らかに決定された位置を有する。このパターンは前記に参照された種類であってよい。この実施形態では、マッチングによって抽出するステップは、前記パターン基準領域について差数の第一の集合を取得することと、該または各確率行列から差数の第二の集合を取得することと、差数の前記第一の集合に差数の前記第二の集合をマッチングすることと、前記次元において前記マッチングステップから、一致からの前記位置コード化パターンの位置を抽出することとを含む。
【００２８】
差数の第二の集合は、該または各確率行列のそれぞれの行または列を、前記行または列について主数列位置を推定するために前記主数列とマッチングし、該または各確率行列の行または列の組について推定された主数列位置を差し引くことによって差数の前記第二の集合の差数を引き出すことによって取得されている。
【００２９】
本発明の第二の態様は、センサによって記録される、位置コード化パターンの部分的な領域から取得される情報に基づいて位置を決定することによる位置復号のための方法であり、位置コード化パターンは複数のマークを備え、各マークは少なくとも一つの次元の少なくとも二つの異なる値の内の一方をコード化する。この方法は、前記部分的な領域のマークごとに一つの行列要素を含み、各行列要素が、それのマークの最もありそうな推定値を表す値、またはそれのマークに何の値も推定されていないことを表す値のどちらかを記憶するように適応される確率行列を生成するステップと、前記位置コード化パターンのパターン参照領域で位置コード化パターンがどのように構成されるのかについての情報と前記確率行列をマッチングし、前記パターン基準領域が前記部分的な領域より大きく、前記部分的な領域を含むステップと、決定される位置として、前記マッチングステップが、前記確率行列と前記マッチング領域の間の対応を示す前記パターン基準領域によって定められる位置の内の一つを選択するステップとを含む。
【００３０】
前述された方法は、ハードウェアまたはソフトウェア内で達成できる。したがって、本発明の第三の態様は、コンピュータ内で実行されると、コンピュータに第一の態様または第二の態様による方法を実行させるプログラムコードを備えるコンピュータプログラムである。
【００３１】
コンピュータプログラムは、位置が復号されなければならない部分的な領域を映像化するセンサと同じ装置内に、あるいは別の装置の中に配置されるプロセッサによって実行できる。
【００３２】
コンピュータプログラムはＲＡＭ、ＳＲＡＭ、ＤＲＡＭ、ＳＤＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ等、光ディスク、磁気ディスク、またはテープの記憶媒体あるいは市販されている他の記憶媒体の形で記憶、分散できる。記憶媒体は伝搬信号である場合もある。
【００３３】
第四の態様によれば、本発明は、第一あるいは第二の態様に従って方法を実行するように適応された単一処理装置を備える装置に関する。
【００３４】
単一処理装置は、ＡＳＩＣ（特定用途向け集積回路）またはＦＰＧＡ（フィールドプログラマブルゲートアレイ）などの、特に適応されたハードウェアによって、デジタル回路またはアナログ回路によって、あるいはその任意の組み合わせによって適切にプログラミングされたプロセッサによって実現されてよい。
【００３５】
本発明の他の目的、特徴及び優位点は、本発明の以下の詳細な説明から、添付請求項から、及び図面から明らかである。
【００３６】
本発明のさまざまな実施形態の特徴が一つの同じ実施形態で結合されてよいことは言うまでもない。
【００３７】
一般的に、請求項で使用されるすべての用語は、ここに明示的に別段に定められる場合を除き、技術分野におけるそれらの通常の意味に従って解釈されるべきである。「一つの（ａ／ａｎ）／該（前記）［要素、装置、構成要素、手段、ステップ等］に対するすべての参照は、特にそれ以外に明白に述べられない限り、前記要素、装置、構成要素、手段、ステップ等の少なくとも一つの例を指していると解釈されるべきである。ここに開示される任意の方法のステップは明示的に別段に定められる場合を除き、開示されている正確な順序で実行される必要はない。
【実施例】
【００３８】
図１は、本発明を使用できる情報管理のためのシステムを示している。システムは、用紙の形をとるベース１、ユーザ装置２、及び外部装置３を備える。用紙には位置コード化パターンが備えられ、その小さい部分４だけが倍尺で概略表示されている。ユーザ装置２は、通常のペンを用いた場合と同様に用紙１の上に書き、書かれている内容をデジタル形式で同時に記録するために使用できる。デジタルで記録された情報は、自動的に（オンラインで）あるいはユーザによって命令されるとそれを送信できるユーザ装置２及び／または外部装置３で処理できる。デジタルで記録される情報が用紙上の情報を正確に反映するためには、位置復号が可能な限り正確に且つ完全に行われることが重要である。
【００３９】
さらに詳細に後述される位置コード化パターンは、所定の規則に従って配列または設計されるグラフィックシンボルから構成されている。つまり位置コード化パターンの部分的な領域が正確に映像化されると、所定の最小サイズを有する前記部分的な領域、つまり位置コード化パターンの中の部分的な領域の位置を、映像化された部分的な領域内の一つまたは複数のシンボル及び所定の復号アルゴリズムによって明白に決定できる。位置は直交座標系または別の座標系の一組の座標として取得できる。
【００４０】
ユーザが用紙１の上でユーザ装置２によって書くと、ユーザ装置はユーザ装置の先端にある位置コード化パターンの部分的な領域の画像を連続記録する。各画像は位置に復号される。その結果、このような復号された位置のシーケンスが用紙上のユーザ装置２の移動の、ひいては用紙上に書かれていることのデジタル表現を構成する。
【００４１】
位置コード化パターンの復号は、ユーザ装置２で、外部装置３で、あるいは多かれ少なかれ処理された形で位置コード化パターンの画像が送信される先の他の何らかの装置で発生することがある。
【００４２】
前述されたように、部分的な領域の情報は所定の復号アルゴリズムによって復号される。これは部分的な領域が正しく映像化される限りうまく機能する。しかしながら、現状では、例えば不十分な照明状態のため、あるいは部分的な領域を大局的に映像化させる傾いた位置でユーザがペンを保持するとき、あるいは記録された画像が映像化機構によって、あるいは信号雑音などの他の外乱によって変形する場合に、ユーザ装置は多くの場合部分的な領域を完全に正確に映像化することができない。復号アルゴリズムがシンボルを誤って解釈する、あるいはシンボルを見失い、それによって位置を正確に復号するのがさらに困難になる場合がある。位置コード化パターンが用紙上であまり正確に複製されないが、用紙に適用されているときある程度までは変形した場合にエラーが発生する場合もある。一定の条件下では、例えば位置コード化パターンがエラー検出を可能にする冗長な情報を含んでいる場合、あるいは復号された位置が過去に復号された位置または以後に復号される位置に関して適切でない場合など、エラーを発見できる。
【００４３】
図２及び図３は、位置コード化パターンの部分的な領域の画像を復号することによって位置を決定する、本発明の一般的な方法を示す。この方法は、位置コード化パターンの部分的な領域の中のすべてのシンボルを無事に記録、解釈することがたとえ可能でなかったとしても、高速で効率的、かつ信頼できる復号に対処する。用紙１は、明確にするために図２には図示されない位置コード化パターンＰを備える。しかしながら、位置コード化パターンＰの小さな部分は、図４に２０で示されている。以下にさらに詳細に説明されるように、位置コード化パターンは、パターンのコードシンボルを部分的に構成する複数のマーク２２を備える。
【００４４】
図２に見られるように、位置コード化パターンＰのコード位置Ｐ１とＰ１’の二つの部分的な領域ＰＡ１とＰＡ１‘がそれぞれ位置Ｐ１とＰ１’をコード化する。図２では、位置Ｐ１とＰ１’が任意の適用可能な復号方法を手段として部分的な領域ＰＡ１とＰＡ１’の記録された画像から無事に復号されたと仮定される。次に図３のステップ３１０では、対応する位置Ｐ２を復号することが所望される新しい部分的な領域ＰＡ２の画像（図２には明示的に図示されていない）が記録される。記録された画像は続くステップ３３０について適切な入力を形成するために、マーク２２が特定され、仮想ラスタ２１が該マークに適合されるステップ３２０で事前に処理される。ステップ３２０と３３０は、フィルタリング、二値化、または閾値化、及び例えば米国第６,５４８,７６８号及び米国第２００２／００４４１３８号に説明されるように、ドットのさまざまな組の間の距離の活用、またはフーリエ変換の活用などの技術で周知である技法を手段として実行されてよい。
【００４５】
ステップ３２０と３３０に続き、実際の復号がステップ３４０と３５０で発生する。最初に、以下でｘ−ＢＯＰＭとｙ−ＢＯＰＭと呼ばれる一組の行列がｘ次元とｙ次元の部分的な領域ＰＡ２のマーク２２によって表される値を推定することにより参照される。これらの行列により保持される情報は、次に、マッチング領域ＭＡにおいて位置コード化パターンＰがどのように構成されるのかについての情報とのマッチングのために使用される。マッチング領域ＭＡの情報はマッチングによるただ一つの位置の復号専用に生成されてよい。図２に見られるように、及びさらに詳細に後述されるように、マッチング領域ＭＡは部分的な領域ＰＡ２より大きく、部分的な領域ＰＡ２の予測ＰＡ２ｐｒｅｄｉｃｔｅｄに対して既定の位置関係を有する。予測ＰＡ２ｐｒｅｄｉｃｔｅｄは前に復号された部分的な領域ＰＡ１とＰＡ１’の位置Ｐ１とＰ１’から決定される予測位置Ｐ２ｐｒｅｄｉｃｔｅｄに一致する。位置Ｐ１とＰ１’は、このようにして本書の概要の項で参照される「少なくとも一つの参照位置」の例であり、マッチング領域ＭＡは「パターン基準領域」の例である。
【００４６】
マッチング領域ＭＡのサイズは通常の手書き速度またはデフォルトの手書き速度を反映する定数値である。例えば、マッチング領域ＭＡは３２×３２のコードシンボルを含んでよい。代わりに、マッチング領域ＭＡのサイズは現在の手書き速度などの適切な入力データに応じて動的に調整されてよい。部分的な領域ＰＡ２のサイズはマッチング領域ＭＡのサイズを考慮して、及び記録された画像のサイズにも応じて選ばれてよい。部分的な領域ＰＡ２は記録される画像の全体的な部分を占有する必要はない。部分的な領域は明白な位置決定のために前述された最小サイズを有する必要もない。一般的に言えば、復号プロセスの堅牢性が部分的な領域のサイズが拡大するにつれて強まるのに対し、復号プロセスの速度及び効率は部分的な領域のサイズが縮小するにつれて高まる。現在、部分的な領域ＰＡ２には１６×１６のコードシンボルのサイズが使用される。
【００４７】
ステップ３４０と３５０の結果は、マッチング領域ＭＡの均等なサイズにされたサブエリアにもっともよく適合する部分的な領域ＰＡ２ｍａｔｃｈｅｄ、及びマッチング領域ＭＡに関する、ひいては予測位置Ｐ２ｐｒｅｄｉｃｔｅｄに関するＰＡ２ｍａｔｃｈｅｄの相対的なロケーションである。したがって、結果として生じる部分的な領域ＰＡ２ｍａｔｃｈｅｄにより定められる位置ＰＡ２ｍａｔｃｈｅｄは、この相対的なロケーションを予測位置Ｐ２ｐｒｅｄｉｃｔｅｄに単に追加することによってのみ決定されてよい。図２に見られるように、実際には予測された部分的な領域Ｐ２ｐｒｅｄｉｃｔｅｄは記録された部分的な領域ＰＡ２と正確に一致しないであろうが、適合した部分的な領域ＰＡ２ｍａｔｃｈｅｄは一致するであろう。したがって、復号方法の結果は、求められていた位置Ｐ２と同一である位置Ｐ２ｍａｔｃｈｅｄとなるであろう。決定された位置はステップ３６０で検証されてよい。
【００４８】
本発明による位置復号が実施されてよい装置――電子ペンの形をとる――の簡略な説明が図６と図７に関してここに示される。
【００４９】
図６と図７の装置は、図１のユーザ装置２を構成できる。それは、ペンとほぼ同じ形状を有するケーシング２０１１を備える。ケーシングの一つの短辺には開口部２０１２がある。該短辺は、位置決定が行われる表面に当接する、または表面から短い距離で離れて設置されることを目的とする。
【００５０】
ケーシングは、本来、光学パーツ、電子回路網パーツ及び電源を含む。
【００５１】
光学パーツは、映像化されることになる表面を照明するための発光ダイオード２０１３、及び二次元画像を記録するためのＣＣＤ（電荷結合素子）またはＣＭＯＳ（相補型金属酸化膜半導体）センサなどのセンサ２０１４を備える。装置は、鏡及び／またはレンズ系等の光学システムも備えてよい。発光ダイオードは赤外線発光ダイオードである場合があり、センサは赤外線に敏感である場合がある。
【００５２】
一般的に言えば、画像センサ２０１４はマークの画像が白黒で、グレースケールで、あるいはカラーで取得されるように位置コード化パターンを映像化するために適した任意の種類のセンサによって置換されてよい。このようなセンサは、任意の適切な波長範囲における電磁放射に敏感であるソリッドステート単一デバイスまたはマルチチップデバイスである場合がある。例えば、センサはＣＣＤ素子、ＣＭＯＳ素子、またはＣＩＤ素子（電荷注入装置）を含んでよい。代わりに、センサはマークの磁気特性の検出のために磁気センサアレイを含んでよい。なおさらに、センサはマークの化学的性質、音響特性、容量特性、または誘導特性の画像を形成するように設計されてよい。
【００５３】
装置の電源はケーシングの分離したコンパートメントに取り付けられる電池２０１５から得られる。電源は、外部電源（不図示）からケーブルを介して得ることもできる。
【００５４】
電子回路網パーツ２０１６は、作業メモリとプログラムメモリだけではなく、センサから画像を読み取り、これらの画像に基づいて位置計算、マッチング、及び検証を実行するためにプログラムされてよいプロセッサ付きのプロセッサ装置も備える。
【００５５】
さらに、図示されている実施形態では、装置はペンポイント２０１７を備え、それを手段として、位置決定が実施されることになる表面上に通常の染料をベースにしたインクを書き込むことができる。ペンポイント２０１７は延長可能且つ格納可能であり、その結果ユーザはそれが使用されるべきかどうかを制御できる。特定の用途では、装置はまったくペンポイントを有する必要がない。
【００５６】
マークは赤外線を吸収するが、染料をベースにしたインクは赤外線に対して透明である種類であるのが適切である。赤外線を発する発光ダイオード及び赤外線に敏感であるセンサを使用することにより、前述された書き込みと位置コード化パターンの間で干渉を受けずにパターンの検出が行われる。
【００５７】
さらに、装置はユーザがそれによって装置を起動、制御するボタン２０１８も備えてよい。装置は、例えばケーブル、赤外光、電波、または超音波を使用する装置への、及び装置からの情報の有線伝送または無線伝送のためにトランシーバ２０１９も備える。装置は位置、記録される情報または他の情報をユーザに示すためのディスプレイ２０２０も備えることができる。
【００５８】
装置は、異なる物理的なケーシングに分割できる。位置復号を実施するために必要である信号処理装置及び他の構成部品は第二のケーシングに配置されてよい一方、位置コード化パターンの画像を捕捉するため、及びそれらを送信するために必要であるセンサ及び他の構成要素は第一のケーシングに配置されてよい。
【００５９】
図７は、図６に図示される装置の電子回路網パーツ２０１６及び画像センサ２０１４の概略ブロック図である。ＡＳＩＣ７００は電子回路網パーツ２０１６を実現し、電子回路網のメインコントローラとしてＣＰＵ７２０を含む。ＣＰＵ７２０はオンチップデータバス７６０を通してメモリ７３０にアクセスできる。画像センサ２０１４は、ＡＳＩＣ７００のデータバス７６０に接続され、約１００Ｈｚの周波数で９６×９６ピクセル、２５６レベルのグレイスケールデジタル画像を生成できるＣＭＯＳ領域センサ７５０として実現される。ＡＳＩＣ７００上の画像プリプロセッサ７１０は図３のステップ３２０に従って画像センサ７５０から受信された画像を操作し、メモリ７３０に前処理された画像を記憶する。ＣＰＵ７２０はｘ−ＢＯＰＭ行列とｙ−ＢＯＰＭ行列を生成し、部分的な領域の位置への復号も実行するであろう。マッチングユニット７４０はこれらのタスクでＣＰＵ７２０を補助する。代替実施形態では、ＡＳＩＣ７００は前処理された画像を中間記憶することなく動作するように設計されてよい。
【００６０】
以下では、位置復号が、出願人によって作成され、とりわけ米国第６，６６７，６９５号に完全に説明される特定の位置コード化パターンを参照してさらに詳しく例証され、説明されるであろう。類似する種類の位置コード化パターンは、国際公開第０１／１６６９１号パンフレット、米国第６,６６３,００８号、及び米国第６,６７４,４２７号に詳細に説明される。代替の位置コード化パターンは米国第６,５７０,１０４号に示されている。
【００６１】
位置コード化は、以下で差数シーケンスと呼ばれる数値列に基づいている。この差数シーケンスには、例えば五個の差数がある部分的なシーケンスなど、所定の長さの任意の部分的なシーケンスを取ると、この部分的なシーケンスがつねに差数シーケンス内に明示的に決定されたロケーションを有するという特性がある。言い換えると、それは差数シーケンスにおいてただ一回であるように見え、したがって位置決定に使用できる。さらに具体的には、差数シーケンスは位置コード化パターンのｙ軸に沿ってだけではなく、ｘ軸に沿っても「通る」。
【００６２】
実際の位置コード化パターンは四個の異なる値０から３を取ることができる簡略なグラフィックシンボル２２から構成される。図４と図５に見られるように、各シンボル２２は、例えばドットの形状を有する場合があり、名目位置２３またはラスタポイントを基準にして異なる四方向の内の一つで距離２４を変位（ｄｉｓｐｌａｃｅｄ）できるマークを含んでいる。名目位置２３は、領域センサにとって完全にまたは部分的に可視であるラスタ線によって仮想、すなわちペン、つまり現物の中の領域センサにとっては不可視であってよいグリッド内のラスタ線２１の間の交差点にある。シンボルの値は変位の方向で求められる。各シンボル値０から３は、ｘ座標をコード化するために使用される１ビットとｙ座標をコード化するために使用される１ビットに、つまりビットの組、（０，０）、（０，１）、（１，０）、及び（１，１）に変換できる。このようにして、コード化はｘ方向とｙ方向で別々に行われるが、グラフィックコード化はｘビットとｙビットに共通であるシンボルで行われる。
【００６３】
距離２４は、二本の隣接するラスタ線２１間の距離の約１／８以上であり、約１／４以下であり、好ましくは約１／６であることが適切である。距離は、例えば約３００ミクロンまたは約２５４ミクロンである場合がある。後者の距離は、多くの場合１００ｄｐｉ（１インチあたりドット）の倍数である解像度を有するプリンタとスキャナに特に適している。
【００６４】
各位置は、該位置のｘ座標の場合６＊６ビットの行列に、ｙ座標の場合６＊６ビットの行列に変換できる６＊６シンボルによってコード化される。ｘビット行列が考慮される場合、これはそれぞれ６ビットから成る六列に分割できる。一列内のビットの各シーケンスは、長さ６ビットの部分的なシーケンスが選択されると、これが主数列内に明白に決定された場所を有するという特性がある６３ビット長の周期的な主数列内の部分的なシーケンスを構成する。したがって、六列は六個の位置番号つまり主数列内の六箇所に相当するシーケンス値に変換できる。これらの六個の位置番号の間では、組で五個の差数を形成することができ、これが差数シーケンスの部分的なシーケンスを構成し、このようにして同じ組の中で明白に決定された場所、そして結果的にｘ軸に沿って明白に決定された場所を有する。他方、特定のｘ座標の場合、位置番号はｙ座標に応じて変化するであろう。位置番号はつねに全体的な位置コード化パターンの中の列で周期的に繰り返される主数列に従って変化するため、差数はｙ座標に無関係に同じとなるであろう。
【００６５】
これに対して、ｙビット行列内の六行は主数列内の六個の位置番号を定める。これら六個の位置番号は、差数シーケンスの部分的なシーケンスを構成し、したがってｙ軸に沿って明白に決定された場所を有する五個の差数を定める。
【００６６】
位置コード化パターンが使用されると、位置コード化パターンのさまざまな部分の画像が、前述されたように記録される。通例、画像は６＊６シンボルよりはるかに多くを含む。したがって、復号は画像内の最良のｎ＊ｍ個のシンボルに基づいてよく、ｎとｍは６以上に等しい任意の数のシンボルである。例えば、復号は、最良の８＊８個のシンボルまたは１６＊１６個のシンボルに基づいてよい。とりわけエラー検出及び／または補正のために余分なシンボルが使用される。
【００６７】
以下において、前述された位置コード化パターンに基づいた位置復号は図面に関して説明される。位置復号は、好ましくはプロセッサ及び図１のユーザ装置２または外部装置３またはなんらかの他の装置内で使用できる適切なプログラムコードによって実施される。
【００６８】
位置コード化パターンは必ずしも完全に表面で再生されるわけではなく、ユーザ装置はイメージング中に位置コード化パターンを変形することがあるため、ドットの変位、したがってシンボルの値をきわめて安全に求めることは困難である可能性がある。代わりに、シンボルごとに、シンボルが四つの異なる可能な値のどれかを取るという確率が求められてよい。本発明の実施形態に従って、前述の二つの行列は、映像化された部分的な領域ＰＡ――列に一つ（ｘ座標符号化）及び行に一つ（ｙ座標符号化）――について図３のステップ３４０で生成される。これらの二つの行列のそれぞれの各行列要素はそれぞれｘ方向とｙ方向のシンボルの推定二進値を表す整数値を含んでよい。これは、例えば、各行列要素がそれぞれシンボル値「０」と「１」の確率を表す二個の実数（流動的な精度値）を含んでいた、前述された米国第２００３／００１２４５５号従来の技術と対照的である。これら二つの行列は、バイナリオフセット確率行列（ＢＯＰＭ）と呼ばれてよく、図中では「ｘ−ＢＯＰＭ」と「ｙ−ＢＯＰＭ」として特定される。
【００６９】
さらに、ｘ−ＢＯＰＭ行列とｙ−ＢＯＰＭ行列のそれぞれの行列要素は、例えば、問題のマーク２２が取る該四つの考えられる変位位置（図５）のどれを決定するのかがなんらかの確実性のレベルで可能でなかったために、シンボルに二進値が推定されなかったことを示している可能性がある。
【００７０】
したがって、ｘ−ＢＯＰＭ行列とｙ−ＢＯＰＭ行列の中の各行列要素は、値「０」、「１」または「−」のどれかを含み、後者はシンボルに二進値が推定されなかったことを表している。
【００７１】
可能な場合――マーク２２の変位によって示されるような――ｘ方向とｙ方向のシンボルの二進値を推定し、それ以外の場合には不確実性値「−」によってシンボルを表すために記録され、前処理される画像を分析するときに多様な方法が利用されてよい。
【００７２】
例えば、特定されたマークごとに、それが図５に示される理想的な四つの変位位置のどれかの周辺の、特定の「安全な」ゾーン内にあるのかどうかが調べられてよい。このような「安全な」ゾーンは、例えば、四つの理想的な変位位置の内の代表的な位置にその中心を有し、所定の半径を有する円形の領域によって画定されてよい。したがって、マークがこのような「安全な」ゾーン内にあることが判明すると、シンボルは「安全な」ゾーンの中心を形成する理想的な変位位置によって表される値を有するように保持される。
【００７３】
代わりに「本格的な」（ｆｕｌｌ−ｓｃａｌｅ）実数の確率行列は、理想的な変位位置からマークの変位に基づいた実数確率値を出力する距離関数に基づいて計算されてよい。このような計算の例は、前述の米国第２００３／００１２４５５号に示されている。次に、確率閾値が実数確率行列に適用されてよく、その結果、例えばこのような確率行列が、特定のマークが、閾値である０．８を超える確率で「０」または「１」を符号化することを示す場合に、次にｘ−ＢＯＰＭ行列またはｙ−ＢＯＰＭ行列の中の対応する行列要素は「０」または「１」に設定され、それ以外の場合は、行列要素は「−」に設定される。
【００７４】
さらに代替策として、マークの符号化が、ラスタポイント２３（例えば、図５の位置ｂとｃ）を通る対角線上にある二つの理想的な位置だけではなく、このような対角線の下にある他の二つ（例えば図５の位置ａとｄ）にも同じｘ値（ｙ値）が使用されるようである場合、特定されるマークのロケーションと、このような対角線に対するそれの距離は問題のシンボルの二進値を推定するために使用されてよい。
【００７５】
このようにして生じたｘ−ＢＯＰＭ行列とｙ−ＢＯＰＭ行列は、記録された画像の部分的な領域ＰＡの中のパターンによってコード化された位置を復号するために、開示される実施形態による二つの異なる方法で図３のステップ３５０で使用される。
【００７６】
図８から図１０に関して説明される第一の実施形態では、パターン近傍マッチング（Ｐａｔｔｅｒｎ Ｎｅｉｇｈｂｏｒｈｏｏｄ Ｍａｔｃｈｉｎｇ）（ＰＮＭ）と呼ばれる方法が（ｘ−ＢＯＰＭ行列とｙ−ＢＯＰＭ行列によって表されるような）記録された部分的な領域ＰＡを、位置コード化パターンの中の予測位置の周辺で生成される位置コード化パターンのより大きなマッチング領域MAとマッチングするために使用される。予測位置は、位置コード化パターンの先行する部分的な領域によって画定された先行する位置から生じる。ここでは、記録された部分的な領域ＰＡと生成されたマッチング領域ＭＡの間の完全なビット単位の相関が実行される。したがって、この方法は、記録された部分的な領域ＰＡがいくつかの不確実なシンボル、または不正確に推定されたシンボルを含む場合にも無事に復号できるであろう。
【００７７】
図１１から図１３に関して説明される第二の実施形態は、パターンシーケンスマッチング（Ｐａｔｔｅｒｎ Ｓｅｑｕｅｎｃｅ Ｍａｔｃｈｉｎｇ）（ＰＳＭ）と呼ばれる方法に関する。ここでは、記録された部分的な領域ＰＡとマッチング領域ＭＡの間の完全なビット単位の相関は実行されない。代わりに、記録された部分的な領域ＰＡで発見される階差数列（ｄｉｆｆｅｒｅｎｃｅ  ｓｕｂｓｅｑｕｅｎｃｅｓ）と、位置コード化パターンの予測位置周辺で再び生成されるより大きなマッチング領域MAのための階差数列の間でマッチングが行われる。この方法は、実行される一致の数がＰＮＭ方法の場合より少ないため、より高速となる（理想的には、実行時間は辺長の積と比較してマッチング領域の辺長の合計に比例するであろう）。しかしながら、多くの不確実なシンボルまたは不正確に推定されたシンボルのある部分的な領域を復号するその能力は低い。
【００７８】
パターン近傍マッチング
前述されたように、位置コード化パターンはｘ符号化とｙ符号化の合成である。したがて、復号は二つの次元に別々に処理される可能性がある。図８は、１０×１０のラスタ交差点及びそれぞれの交差点からさまざまな変位に配置されるドットから構成される記録された部分的な領域８００を概略して示している。各列（及び各行）に、ドットが四つの可能な理想的な変位――例えばラスタセルサイズの１／６、「右」、「上方」、「左」または「下方」――の内の一つに十分近くに位置することを特定することによって、符号化されたｘ（及びそれぞれｙ）個の値のいくつかが求められてよい。例えば、ドット８４０は変位「左」を表し、それによりコード化凡例８３０に従って（ｘ，ｙ）＝（１，０）を生じさせるために決定されてよい。他方、いくつかのラスタ交差点では、もしあれば、近傍のドットが何を符号化するのかを決定することは可能ではないであろう。例えば、ドット８５０はそれのラスタ交差点に近すぎて位置し、交差点８６０ではドットはまったく存在しない。これらのケースでは、ｘ値もｙ値も推定できない。したがって、ｘ次元及び／またはｙ次元で特定のラスタ交差点での値について不確実性を表すというニーズがある。
【００７９】
前述されたように、及び図３のステップ３４０に従って、記録された部分的な領域の列と行を詳しく検討する（ｔｒａｖｅｒｓｉｎｇ）、列の符号化（例えば図８の８２０）と行の符号化（例えば図８の８１０）の解釈を表すために三つの文字、つまり値「０」、「１」、及び「−」が使用されてよく、「−」はドット変位についての不確実性を表す。
【００８０】
すでに言及されたように、このプロセスは、列のために一つ（ｘ座標符号化）、及び行のために一つ（ｙ座標符号化）、すなわちバイナリオフセット確率行列ｘ−ＢＯＰＭとｙ−ＢＯＰＭの二つの行列を生じさせる。ｙ−ＢＯＰＭ例は図１０の１０１０で示される。ある意味では、ｘ−ＢＯＰＭとｙ−ＢＯＰＭは、二進値に加えて、不確実性を表す一つの値も有するため、それらは二つの部分からなるというよりは三つの部分からなる。
【００８１】
ｘ−ＢＯＰＭとｙ−ＢＯＰＭはメモリ７３０に記憶されてよい。さらに詳細には、行列の各行は、「特定の」値「０」と「１」を表す第一のｎビットデータレジスタ（ｎは一つの次元での行列のサイズである）に、及び不確実性が第一のｎビットデータレジスタ内の対応する値に適用するかどうかに関するビットフラグを表す第二のｎビットデータレジスタに記憶されてよい。ビットフラグが第二のデータレジスタにセットされると、これは、対応するビット値が使用されるべきではないこと、及び問題の行列セルが「−」値を有することを意味する。
【００８２】
図９は、本実施形態のために復号ステップ３５０と検証ステップ３６０を実現するパターン近傍マッチング方法９００を図解する。この方法のための入力データは、図２の二つの先行する位置Ｐ１とＰ１’だけではなく、図３のステップ３４０で生成されるような前述された二つのバイナリオフセット確率行列ｘ−ＢＯＰＭとｙ−ＢＯＰＭでもある。
【００８３】
ステップ９１０では、該二つの先行する位置Ｐ１とＰ１’に基づいて、次の位置Ｐ２ｐｒｅｄｉｃｔｅｄが位置Ｐ１とＰ１’から一次補外によって引き出される。代替策として、二つより多い先行する位置が次の位置を予測するために使用されてよく、多項式補外などの任意の既知の運動予測モデルが使用されてよい。さらに代替策として、予測が例えば移動方向、ユーザ装置２の速度または加速度、あるいは予想手書き速度に関するデフォルトまたは所定の情報などの他の有効な情報などに関する運動データ入力と結合される場合にただ一つの先行する位置が使用されてよい。ただ一つの先行する位置は、マッチング領域ＭＡのサイズが続く位置を含むほど十分に大きく設定される場合にも使用されてよい。このようなマッチング領域は先行する位置を中心に置くのが適切である。前記代替策は、例えば復号プロセスのさまざまな段階で使用されている先行する位置の異なる数によって結合されてもよい。
【００８４】
該または各先行する位置Ｐ１、Ｐ１’は、さまざまな方法で決定されてよい。例えば、ペンストロークのまさに始まりでは、Ｐ１，Ｐ１’は、すべてがここで参照することにより組み込まれる、前述された米国第６,６６７,６９５号、米国第２００３／００１２４５５号、及び米国第６,６７４,４２７号を含むがそれらに限定されない、任意の従来の方法に従って計算されてよい。次に、新しい位置は本発明によるマッチングによって復号されているので、それらは新しい位置Ｐ２の予測の基礎を形成するために先行する位置Ｐ１、Ｐ１’として使用されてよい。
【００８５】
ステップ９２０では、位置コード化パターンのマッチング領域ＭＡ（図２）が予測位置を中心に生成される。生成されたマッチング領域の例は図１０の１０００に示される。例えば、前述の米国第６,６６７,６９５号は、位置コード化パターンの領域が既定の位置からどのようにして生成されてよいのかを、１１段５７行目から１５段１４行目において、及びその図６において詳細に説明している。
【００８６】
ステップ９３０では、バイナリオフセット確率行列の一つ、例えばｙ−ＢＯＰＭが、対応する次元、例えばｙ次元内の生成されたマッチング領域の内容とマッチングされる。この目的のため、マッチングユニット７４０が、ｙ−ＢＯＰＭとマッチング領域のそれぞれの等しいサイズにされた部分的な領域の間でビット単位の相関を実行するであろう。このようなビット単位の相関ごとに、マッチングユニット７４０はｙ−ＢＯＰＭと部分的な領域の中の対応するビットの数をカウントするであろう。ビットがｙ−ＢＯＰＭにおいて不確実性の値「−」に設定されると、この位置は単に免除され（ｄｉｓｐｅｎｓｅｄ  ｗｉｔｈ）、言うまでもなくこの位置に対応するビットはクレジット（ｃｒｅｄｉｔｅｄ）されないであろう。
【００８７】
いったんｙ−ＢＯＰＭがマッチング領域全体とマッチングされると、ＣＰＵ７２０はｙ−ＢＯＰＭと最良の一致が発生した部分的な領域の内の一つを決定するであろう（図２のＰＡ２ｍａｔｃｈｅｄを参照すること）。図１０では、マッチング領域１０００の最良のマッチングの部分的な領域は１０２０で示されている。
【００８８】
ステップ９４０では、結果として生じる位置（図２のＰ２ｍａｔｃｈｅｄを参照すること）が、最良のマッチングの部分的な領域から計算される。位置コード化パターンのマッチング領域ＭＡの絶対開始位置はすでに既知である（予測位置Ｐ２ｐｒｅｄｉｃｔｅｄによって指定さている）ため、この位置は容易に決定される。したがって、結果として生じる位置は、予測位置の絶対値座標を生じさせるために、マッチング領域ＭＡの既知の絶対開始位置に対する相対的な位置として追加される。
【００８９】
この実施形態は、ｙ−ＢＯＰＭマッチングでの行パターンから完全に復号された位置（ｘ座標とｙ座標の両方）を生じさせることが認められなければならない。それにも関わらず、ステップ９５０と９６０においてマッチング領域とのｘ−ＢＯＰＭマッチングを実行することによっても、ステップ９３０と９４０の結果は堅牢性を獲得するために検証されてよい。つまり、最良の相関が両方の座標で一致するとき且つそのときに限り、結果はステップ９７０で受け入れられる。したがってステップ９５０と９６０は図３の検証ステップ３６０を実現してよい。
【００９０】
ステップ９５０と９６０のこのような別々の検証動作に対する代替策として、二つの一致行列、つまりｙ−ＢＯＰＭマッチングのための一つと、ｘ−ＢＯＰＭマッチングのための一つがステップ９３０と９４０で平行して生成されてよい。これらの一致行列のそれぞれにおける行列要素は、マッチング領域ＭＡ内のその行列要素の位置で開始する部分的な領域ＰＡのマッチングｘ／ｙビット値の数を表すであろう。これら二つのマッチ行列を要素ごとに追加することによって、ＣＰＵ７２０は求められているマッチング済み位置Ｐ２ｍａｔｃｈｅｄとして、結果として生じる最高の合計を有する特定の要素位置を選択してよい。したがって、このケースでは検証はマッチング動作において固有である。
【００９１】
前記検証方法の代わりに、または加えて、マッチング基準が満たされる場合に、位置決定のためにｘ−ＢＰＯＭ及び／またはｙ−ＢＯＰＭとの最良の相関のある部分的な領域（複数の場合がある）だけが使用されてよい。マッチング基準は、一致（つまりビット対応）の数が所定の閾値を超える、及び／または可能な一致の数に対する一致の数の比率が所定の閾値を超えることを含んでよい。可能な一致の数はそれぞれｘ−ＢＯＰＭとｙ−ＢＯＰＭの「確実な」値（つまり、不確実性値「−」に設定されない）の数によって示されてよい。
【００９２】
パターンシーケンスマッチング
この方法は、位置が二つの一次元の階差数列に基づいて位置コード化パターンでコード化されるという事実を利用している。したがって、マッチングは一つの二次元の問題というよりむしろ二つの一次元の問題として処理されてよい。これは、マッチングに必要とされる検索時間が二次（ｏｒｄｏ（ｎ＊ｍ））の代わりに、一次（ｏｒｄｏ（ｎ＋ｍ））であることを意味し、ｎとｍはマッチング領域の辺長である。
【００９３】
図１３に関して、パターンシーケンスマッチング（ＰＳＭ）方法１３００は、次の位置Ｐ２ｐｒｅｄｉｃｔｅｄを予測するステップ１３１０で開始する。ステップ１３１０は、図９のステップ９１０について前述されたのと同じように実行されてよい。
【００９４】
ステップ１３２０では、マッチング差数部分列ＭＳｘとＭＳｙ（図１２の１２２０を参照すること）が、予測位置Ｐ２ｐｒｅｄｉｃｔｅｄの周辺のマッチング領域ＭＡ（図１２の１２００を参照すること）について生成される。しかしながら、第一の実施形態とは対照的に実際のマッチング領域自体が生成される。前述の米国第６,６６７,６９５号は、１１段５７行目から１５段１４行目において、及びその図６において、差数部分列が既定の位置からどのようにして計算できるのかを説明している。
【００９５】
ステップ１３３０は、ステップ１３２０で生じる予測マッチング差数部分列ＭＳｘとＭＳｙとマッチングされる、記録された部分的な領域ＰＡ２について差数ＳｘとSｙの集合を引き出す。最初に、図１１に関して、ｙ−ＢＯＰＭ／ｘ−ＢＯＰＭの各行／列１１１０について、主数列１１００の中の最良のマッチング主数部分列（ｍａｉｎ ｎｕｍｂｅｒ ｓｕｂｓｅｑｕｅｎｃｅ）１１２０が決定される。これは、六個の連続する正確なビット値（推定値「０」または「１」を有するが、「−」は有さない）がＢＯＰＭ内で検出されると、六個の値のこの組み合わせは本質的に主数列内に一意の位置を有するであろうという事実に基づいて、高速マッチングアルゴリズムによって実行されてよい。この一意の主数列位置は、メモリ７３０に好都合に記憶され、主数列１１００の六十三通りの異なる周期性シフトから構成されるルックアップテーブルから直接的に得られてよい。次に、ｙ−ＢＯＰＭ／ｘ−ＢＯＰＭの特定の行／列１１１０の他の正確な位置は、フックアップテーブルからの特定の主数列シフトに突き合わされ、これらも一致すると判明すると、引き出された主数列位置は正しいと考えられる。一致しない場合、ｙ−ＢＯＰＭ／ｘ−ＢＯＰＭの特定の行／列１１１０とルックアップテーブルの中の六十三すべての主数列シフトの間で完全ビット単位マッチングが行われ、その行／列１１１０に対して引き出された主数列位置として最良の一致が選択される。同時に、主数列一致レートがｙ−ＢＯＰＭ／ｘ−ＢＯＰＭの特定の行／列１１１０に対するマッチングビット値の総数の形で登録される。
【００９６】
次に、ステップ１３３０は、隣接する行／列について引き出された主数列位置を差し引くことにより差数Ｓ■とＳｙ（図１２の１２３０）の集合を引き出すことによって続行する。また、各差数には、例えば関係する行／列の主数列一致レートを加重する（例えば合計するまたは平均する）ことによって、あるいはその最小を選択することによって差数一致レートが割り当てられる。
【００９７】
ここで、ステップ１３４０では、差数ＳｘとＳｙのこのようにして引き出された（つまり観察された）集合が、図１２の１２２０で示されるように、予測された差数部分列ＭＳｘとＭＳｙとマッチングされる。部分列ＭＳｘとＭＳｙの最良の一致は、任意的に差数一致レートの最高総計を有するその組み合わせを選択することによりさらに区別される最高の一致数を生じさせる、差数のそれぞれの連続組み合わせとして選択されてよい。代わりに、最良の一致は、一致の数とは関係なく、差数一致レートの最高の合計を生じさせるマッチング差数の組み合わせとして選択されてよい。
【００９８】
ステップ１３５０では、結果として生じる位置Ｐ２ｍａｔｃｈｅｄが、ステップ１３４０の結果として生じる最良の一致から決定される。図９のステップ９４０について前述の説明に示される理由に類似する理由のため、この結果として生じる位置は容易に計算される。
【００９９】
ステップ１３６０では、結果として生じる位置Ｐ２ｍａｔｃｈｅｄが、例えば位置Ｐ２ｍａｔｃｈｅｄを中心とする位置コード化パターンの局所検証領域を生じさせ、このビット単位をｘ−ＢＯＰＭとｙ−ＢＯＰＭと相関させることによって検証される。この検証は、マッチング基準を含む必要がある。前述されたパターン近傍マッチングの場合と同様に、一致基準は、一致（つまり、ビット対応）の数が所定の閾値を超えなければならないこと、及び／または可能な一致の数に対する一致の数の比率が所定の閾値を超えなければならないことを含んでよい。Ｐ２ｍａｔｃｈｅｄを中心とした完全な局所検証領域を生成する代わりに、ステップ１３３０で実行される計算が利用されてよい。選択された結果として生じる位置Ｐ２ｍａｔｃｈｅｄが最良の一致のある位置であるため、引き出された差数の多くは予測されたものと一致する可能性が高い。これらの対応する差数の根底にある最良のマッチング主数列のための一致の数は、前述された主数列一致レートを介してすでに既知である。したがって、局所検証領域は、一致しない差数についてだけ生成される必要がある。
【０１００】
パターンシーケンスマッチングとパターン近傍マッチングの組み合わせ
二つの実施形態は、例えば、図１４に関して説明されるように結合されてよい。
【０１０１】
１４００で見られるように、マッチングは生成されたｘ−ＢＯＰＭとｙ−ＢＯＰＭ、及び予測位置を通して取得されるマッチング領域情報に基づいて実行される。最初に、パターンシーケンスマッチング１４０２が実行される。復号が無事に行われると、１４１０で検証が実行される。他方、パターンシーケンスマッチング１４０２が失敗すると、次にパターン近傍マッチング１４０４が実行される。これが成功すると、１４１０で検証が行われる。しかしながら、パターン近傍マッチング１４０４も失敗した場合、他の既知の方法により位置を解決する試みが１４２０で行われる。このような方法は前述した米国第６,６６７,６９５号、米国第２００３／００１２４５５号、及び米国第６,６７４,４２７号に記述されるもののどれかを必要とする可能性がある。本発明によるマッチング方法が失敗した場合にも、このような方法が成功することを期待する状況がある。一つの例は、マッチング領域ＭＡのサイズが小さすぎて、高速で書くユーザに「追いつく」ことができない場合である。別の例は、例えばペンストロークがある位置コード化ベースから別の位置コード化ベースへ描画されるときなど、ペンが位置コード化パターンの位置の切れ目の上で移動されるときである。位置が１４２０で無事に解かれると、結果は１４１０で検証される。
【０１０２】
マッチング１４００の結果の検証が失敗すると、１４２０で位置を解決するための追加の試みがなされてよい。この試みも失敗した場合には、すべての使用可能な方法が試されるまで別の既存の位置解決方法が１４２０で試されてよい。
【０１０３】
本発明はおもにいくつかの実施形態に関して前述されてきた。しかしながら、当業者により容易に理解されるように、前記に開示された実施形態以外の他の実施形態は、添付の請求項により定義されるように、本発明の範囲内で等しく可能である。
【図面の簡単な説明】
【０１０４】
本発明はここで添付図面に関してさらに詳細に説明される。
【図１】本発明を使用できるシステムの概略図である。
【図２】位置コード化パターンの部分的な領域の復号及びマッチングの概略図である。
【図３】位置コード化パターンの部分的な領域の画像を復号することにより位置を決定する、本発明による一般的な方法を示す流れ図である。
【図４】本発明に従って復号されてよい位置コード化パターンの概略図である。
【図５】位置コード化パターンの中のマークの四つの理想的なロケーションを示す。
【図６】本発明による位置復号が実施されてよい電子ペンの形の装置の概略図である。
【図７】図６に示される装置内の電子回路網パーツと画像センサの概略ブロック図である。
【図８】二進オフセット確率行列が生じる方法を立証する概略図である。
【図９】本発明による復号方法の第一の実施形態の流れ図である。
【図１０】第一の実施形態の動作原理を説明するために、生成された局所位置コード化パターン及び二進オフセット確率行列を示す。
【図１１】第二の実施形態の説明を裏付けるための概略図である。
【図１２】第二の実施形態の説明を裏付けるための概略図である。
【図１３】第二の実施形態の説明を裏付けるための概略図である。
【図１４】第一の、及び第二の実施形態の両方ともが利用される代替実施形態を示す。
【図１】
2006525593.tif 000003
【図２】
2006525593.tif 000004
【図３】
2006525593.tif 000005
【図４】
2006525593.tif 000006
【図５】
2006525593.tif 000007
【図６】
2006525593.tif 000008
【図７】
2006525593.tif 000009
【図８】
2006525593.tif 000010
【図９】
2006525593.tif 000011
【図１０】
2006525593.tif 000012
【図１１】
2006525593.tif 000013
【図１２】
2006525593.tif 000014
【図１３】
2006525593.tif 000015
【図１４】
2006525593.tif 000016
【国際調査報告】
2006525593.tif 000017
2006525593.tif 000018
2006525593.tif 000019