(57)【要約】  デジタル・インク入力を圧縮する方法が開示される。デジタル・インクは一連のストロークを含み、各々のストロークは、ｘおよびｙ座標を表す一連のデジタル・ワードとして表される。圧縮されたデジタル・インク・データは、各々のストロークについて、絶対項で表された少なくとも１つの参照座標を含み、後続の座標は、線形予測を使用して推定された座標からのオフセットによって表され、所与の座標は、式（Ｉ）のように先行ｍ個の座標に基づいて決定される。ここで、ｃｉはデジタル・インクの性質に依存した係数であり、αはｘまたはｙ座標を表す。
2005509385.tif 000002
【特許請求の範囲】
【請求項１】
一連のストロークを含むデジタル・インク入力を圧縮する方法であって、各々のストロークがｘおよびｙ座標を表す一連のデジタル・ワードとして表され、圧縮されたデジタル・インク・データが、各々のストロークについて、絶対項で表された少なくとも１つの参照座標を含み、後続の座標が線形予測を使用して推定された座標からのオフセットによって表され、所与の座標が、
【数１】
2005509385.tif 000027
のように、先行ｍ個の座標に基づいて推定され、ここでｃｉがデジタル・インクの特性をモデル化するために選択された係数であり、αがｘまたはｙ座標を表している、
前記方法。
【請求項２】
ｍが２であり、所与の座標が、
【数２】
2005509385.tif 000028
によって定義される、請求項１に記載の方法。
【請求項３】
Ｃ１＞０およびＣ２＜０である、請求項２に記載の方法。
【請求項４】
１≦Ｃ１≦３および
−２≦Ｃ２≦１である、
請求項３に記載の方法。
【請求項５】
Ｃ１＝２およびＣ２＝−１である、請求項４に記載の方法。
【請求項６】
ｘ座標の係数値（Ｃｉ）が、ｙ座標の係数とは異なる、請求項１〜４のいずれか一項に記載の方法。
【請求項７】
ｘ座標について、
Ｃ１＝１．８５７
Ｃ２＝−０．８５６であり、
ｙ座標について、
Ｃ１＝１．９１２
Ｃ２＝−０．９１３である、
請求項６に記載の方法。
【請求項８】
ｍが３であり、所与の座標が、
【数３】
2005509385.tif 000029
によって定義される、請求項１に記載の方法。
【請求項９】
Ｃ１＞０およびＣ２＜０およびＣ３＜１である、請求項８に記載の方法。
【請求項１０】
ｘ座標の係数値（Ｃｉ）がｙ座標の係数とは異なる、請求項８または９に記載の方法。
【請求項１１】
ｘ座標について、
Ｃ１＝１．７９９
Ｃ２＝−０．７２２
Ｃ３＝−０．０７８  であり、
ｙ座標について、
Ｃ１＝２．００９
Ｃ２＝−１．１０７
Ｃ３＝−０．０９８  である、
請求項１０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタル・インクを圧縮する方法に関し、具体的には線形予測符号化スキームを使用する圧縮方法に関する。
【背景技術】
【０００２】
携帯用ペン・ベース・コンピューティング・デバイス、例えばＰＤＡの使用が発達すると、時間およびデータ記憶を効率化する方法で入力「ストローク」データを処理したいという要望が増えている。従来技術の手法は、適切なタッチスクリーン上で文字を書くスタイラスによって入力される入力ストローク・データを、コンピュータ可読またはＡＳＣＩＩテキストへ変換することを含む。
【０００３】
こうして、ユーザが手書きデータを入力すると、それは、一般的に、プレーンＡＳＣＩＩテキストの形式でデバイスのデータ・ストレージに記憶される。したがって、ユーザがそのデータ内の或るワードの探索を実行したい場合、そのユーザは手書きのワードを入力する必要がある。手書きのワードは、文字認識手法を使用してプレーンＡＳＣＩＩテキストへ再び変換され、それによってコンピュータは記憶されたワードを突き止めることができ、そのワードはコンピュータ生成タイプフェースまたはフォントで表示される。
【０００４】
手書きデータ・エントリーをＡＳＣＩＩテキストへ変換するステップは不必要なステップであるという考えが、次第に増えてきている。しかしながら、現在のところ、それは大量のデータを記憶する最も効率的な方法である。これは、手書きデータを画像ファイルとして記憶することが、メモリの負担が大きくて許容されないという理由からである。ストロークを一連のｘ−ｙ座標として記憶しても、大量のメモリを消費する可能性がある。
【０００５】
一般的に、デジタル・インクは一連のストロークとして構成される。これらのストロークは、ペン・デバイスが記入面と接触したときに始まり、ペン・デバイスが持ち上げられたときに終わる。各々のストロークは、ペンが記入面と接触している間にペンの動きを定義するサンプル座標のセットを含む。
【０００６】
前述したように、ペン・コンピューティングの使用の増加、およびネットワーク・コンピューティング・リソースへのペーパー・ベース・インタフェースの出現は、デジタル・インクを圧縮する手法の必要性にハイライトを当てている。これは、アノトによる報道機関向けの発表“Ａｎｏｔｏ，Ｅｒｉｃｓｓｏｎ，ａｎｄ  Ｔｉｍｅ  Ｍａｎａｇｅｒ  Ｔａｋｅ  Ｐｅｎ  ａｎｄ  Ｐａｐｅｒ  ｉｎｔｏ  ｔｈｅ  Ｄｉｇｉｔａｌ  Ａｇｅ  ｗｉｔｈ  ｔｈｅ  Ａｎｏｔｏ  Ｔｅｃｈｎｏｌｏｇｙ”，６ｔｈ  Ａｐｒｉｌ，２０００）で例示される。書かれたインクはテキストよりも表現に富んで柔軟なフォーマットであるから、ペン・コンピューティング・システムは、生のデジタル・インクの記憶、検索、および再生をサポートするのが望ましい。しかしながら、デジタル・インクの情報表現は、多くの場合、対応する従来の表現よりもはるかに大きいので（例えば、手書き文字を表すデジタル・インクは、対応するＡＳＣＩＩテキストよりもはるかに大きい）、このデータ・タイプの効率的な伝送および記憶を確保するためデジタル・インクの圧縮が必要である。
【０００７】
電話の分野では、電話品質音声信号を圧縮するデルタ符号化が知られている。差分パルス符号変調（ＤＰＣＭ）は、音声信号のエネルギーの大部分が低周波数で起こり、したがって十分に高いサンプリング・レートが与えられると、連続したサンプル間の差分がサンプル自身の大きさよりも一般的に小さくなる事実を利用する。より複雑な圧縮スキームである適応差分パルス符号変調（ＡＤＰＣＭ）は、６４Ｋｂ／ｓの音声信号を１６Ｋｂ／ｓのビットレートへ圧縮するために使用される。この手法は、ＩＴＵ標準Ｇ．７２６（国際電気通信連合（ＩＴＵ）、「４０、３２、２４、１６Ｋビット／ｓ適合差分パルス符号変調（ＡＤＰＣＭ）」、ＩＴＵ−Ｔ勧告Ｇ．７２６）で定義され、音声信号の短期フレームの統計的解析に基づいてデルタ・ステップ・サイズの大きさを適合化する。
【０００８】
同様に、電話品質の音声を非常に低いビットレートへ圧縮するためには、線形予測符号化（ＬＰＣ）が使用されてきた。一般的に、ＬＰＣオーディオ圧縮は、非可逆的であり、著しい歪みを導入する。１つの例は、低品質合成サウンド圧縮音声を２．４Ｋｂ／ｓで生成するＬＰＣ−１０ｅ標準である。ＬＰＣに基づくもっと複雑な圧縮スキームが開発されたが、このスキームは、はるかに高い品質信号を、対応的に高いビットレートで生成する（例えば、ＩＴＵ標準Ｇ．７２３．１（国際電気通信連合（ＩＴＵ）、「５．３および６．３Ｋビット／ｓで伝送するマルチメディア電気通信用デュアルレート音声符号器」、ＩＴＵ−Ｔ勧告Ｇ．７２３．１）で説明される符号励振線形予測（ＣＥＬＰ）圧縮スキーム）。
【０００９】
米国特許第６，２１２，２９５号は、「元のデータの或る関数である値の増分を累積する」ことによって、手書きダイナミックスを再構成する手順を説明する。この手法は、非線形関数を使用して元の信号の速度成分を強調し、それを手書き署名検証システムで使用する。
【００１０】
多数の商業的ベンダが、非可逆的デジタル・インク圧縮を実行する製品を開発してきた。コミュニケーションズ・インテリジェンス社（Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  Ｃｏｒｐｏｒａｔｉｏｎ）は、「圧縮された画像よりもはるかに少ない高解像度電子インクを記憶する」製品であるＩＮＫＳｈｒＩＮＫを提供する。この製品は、サイズと再構成画像品質とを相殺する６レベルの最適化を提供する。ベジエ曲線を使用する近似に基づく他のインク圧縮スキームは、ＪＯＴ標準、即ちＳｌａｔｅ  Ｃｏｒｐｏｒａｔｉｏｎ，“ＪＯＴ−Ａ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ  ｆｏｒ  ａｎ  Ｉｎｋ  Ｓｔｏｒａｇｅ  ａｎｄ  Ｉｎｔｅｒｃｈａｎｇｅ  Ｆｏｒｍａｔ”，Ｍａｙ  １９９３）で説明される。
【００１１】
これらの従来技術の文献は、デジタル・インクによって提供される可能性を利用するため効率的で簡単な圧縮スキームが必要であることを示している。本発明は、この問題に対処することを目的とする。
【発明の開示】
【００１２】
本発明は、デジタル・インクをストリーム可能および可逆的に圧縮する手法を含む。本件分野での関連成果が、デジタル・インクのデルタ符号化および線形予測符号化の多数のアルゴリズムと一緒に呈示される。最良実現圧縮スキームのワーストケースの動作に関する論説と共に、アルゴリズムの圧縮結果が示される。
【００１３】
本発明の焦点は、デジタル・インクの圧縮である。更に、圧縮手法は、ストリーム可能であって、最小のメモリおよび処理リソースを利用するように設計され、低コスト埋め込み環境に適したものにしている。本発明の実施形態は、可逆または非可逆圧縮を可能にし、その区別は処理系の特徴で決定される。
【００１４】
本発明の広い形態によれば、一連のストロークを含むデジタル・インク入力を圧縮する方法であって、各々のストロークがｘおよびｙ座標を表す一連のデジタル・ワードとして表され、圧縮されたデジタル・インク・データが、各々のストロークについて、絶対項で表された少なくとも１つの参照座標を含み、後続の座標が、線形予測を使用して推定された座標からのオフセットによって表され、所与の座標が、
【数１】
2005509385.tif 000003
のように先行ｍ個の座標に基づいて決定される方法が提供される。ここで、ｃｉはデジタル・インクの特性をモデル化するために選択された係数であり、αはｘまたはｙ座標を表す。
【００１５】
ｘおよびｙ座標は平面空間を参照し、ｘは手書きの方向を表す。
【００１６】
好ましくは、ｍは２であり、所与の座標は、
【数２】
2005509385.tif 000004
によって定義される。
【００１７】
好ましくは、Ｃ１＞０およびＣ２＜０である。これらの限界は、許容されるパフォーマンスを提供するように経験的に発見される。
【００１８】
好ましくは、１≦Ｃ１≦３および−２≦Ｃ２≦１である。これらのより狭いレンジは、前に宣言されたレンジよりも向上したパフォーマンスを提供する。
【００１９】
好ましくは、Ｃ１＝２およびＣ２＝−１である。これらの値は、許容されるパフォーマンスを提供し、それら値が整数であることから、実施するのに早くて簡単である。
【００２０】
代替的に、ｘ座標の係数値（Ｃｉ）は、ｙ座標の係数とは異なる。ｘおよびｙ座標を符号化するためには異なった係数が好ましい。それは、大部分の手書きが非対称であるからである。例えば、ｘ方向よりもｙ方向でストロークが長くなる傾向がある。それは、「ｙ」、「ｇ」のような字句にはテールがあり、「ｋ」、「ｌ」、「ｂ」、「ｄ」のような字句は比較的長い垂直要素を有するからである。
【００２１】
好ましくは、ｘ座標について、Ｃ１＝１．８５７、Ｃ２＝−０．８５６であり、ｙ座標について、Ｃ１＝１．９１２、Ｃ２＝−０．９１３である。これらの値は、最適パフォーマンスを提供するように経験的に発見される。
【００２２】
好ましくは、ｍ＝３であり、所与の座標は、
【数３】
2005509385.tif 000005
によって定義される。
【００２３】
３つの先行する座標を使用すると、向上した予測能力が提供され、したがって符号化が改善される。
【００２４】
好ましくは、Ｃ１＞０およびＣ２＜０およびＣ３＜１である。
【００２５】
好ましくは、ｘ座標の係数値（Ｃｉ）は、ｙ座標の係数とは異なる。
【００２６】
好ましくは、ｘ座標について、Ｃ１＝１．７９９、Ｃ２＝−０．７２２、Ｃ３＝−０．０７８であり、ｙ座標について、Ｃ１＝２．００９、Ｃ２＝−１．１０７、Ｃ３＝−０．０９８である。
【発明を実施する形態】
【００２７】
本発明は、添付の図面と関連づけて記述される本発明の好ましいが非限定的な実施形態の単なる例として示される以下の説明から明らかになるであろう。
【００２８】
次の形態は、本発明の主題の正確な理解を提供するために、記述および添付の特許請求の範囲に適用されるものとして記載される。
【００２９】
本発明は、デジタル・インクの圧縮を提供する幾つかの実施形態を提供する。本発明の特徴を示すため組み込まれた図面において、同様の参照番号は図面を通して同様の部分を識別するために使用される。
【００３０】
好ましいが非限定的な本発明の実施形態が、図１に示される。
【００３１】
プロセスは処理システムを使用して実行可能である。処理システムの例は図１に示される。
【００３２】
具体的には、図示されるように、処理システム１０は、一般的に少なくとも、バス２４を介して相互に結合されたプロセッサ２０、メモリ２１、入力デバイス２２、例えばグラフィックス・タブレットおよび／またはキーボード、出力デバイス２３、例えばディスプレイを含む。処理システムをストレージ１１、例えばデータベースへ結合するため、２５で示されるような外部インタフェースも設けられる。
【００３３】
使用に当たって、処理システムは、データベース１１へデータを記憶し、および／またはデータベース１１からデータを検索するように構成される。これによって、プロセッサは、入力を介してデータを受け取ることができ、ストレージの中に記憶されたデータを使用してデータを処理することができる。これは、他方では、処理システムが入力デジタル・インク・データの圧縮バージョンを生成することを可能にする。これにより、処理システム１０は任意の形式の処理システム、例えばコンピュータ、ラップトップ、サーバ、特殊のハードウェアなどであってよいことが分かるであろう。
【００３４】
以下の例は、本発明の１つの実施形態の、より詳細なアウトラインを提供する。これらの例は、単なる例であり、本発明の範囲の限定を意図するものではない。
【００３５】
以下の説明で、デジタル・インクはストロークのアレーとして表され、ストロークの各々は、ペンの降下事象で始まり、対応するペンの上昇事象まで続く。ストローク内の点は、１００Ｈｚでサンプリングされた３２ビットのＸおよびＹ座標として記憶される。もちろん、他の解像度およびサンプリング・レートが可能であり、これらの値は単なる例にすぎない。トライアルでは、サンプルのデジタル・インクはＷａｃｏｍディジタイザを使用して収集され、筆記体の手書き文字、印刷されたテキスト、および手書き画像の混合を含む。サンプルのデジタル・インクは２つのばらばらのデータベースへ分けられた。１つのデータベースはトレーニングに使用され（必要な場合）、他のデータベースはテストに使用された。
【００３６】
特に断らない限り、ＸおよびＹ座標は同じ手順を使用して符号化され、したがってＹ座標を符号化および復号する方程式は、Ｘ座標を符号化および復号する方程式から機械的に引き出すことができる。他のインク表現は、ストロークのダイナミックス、例えばペンの圧力および方向に関する追加情報を含むことに注意されたい。この情報は、以下で説明するような手法と同一または類似の手法を使用して、成功裏に圧縮可能であることが予想される。
【００３７】
［デルタ符号化］
このセクションは、デルタ符号化を使用したデジタル・インク圧縮のアルゴリズムおよび実験結果を詳細に説明し、エントロピ符号化を使用したデルタ符号の圧縮を説明する。
【００３８】
［単純デルタ符号化］
インク・ストローク内の連続した点の間の差分は、一般的に、点座標自身のサイズよりもはるかに小さいことを観察することによって、単純デジタル・インク圧縮スキームを使用することができる。その結果、サンプル自身ではなく個々のサンプル間の差分を伝送または記憶することによって、デジタル・インク・ストリームの圧縮が可能となるであろう。データを符号化するため、最初の点がフル精度（即ち、３２ビット）で伝送され、連続する各々の点が、先行する点からの一対のＸおよびＹオフセット（即ち、ＸおよびＹデルタ）として符号化される。
【数４】
2005509385.tif 000006
【００３９】
サンプルのデルタは、サンプル自身よりもはるかに小さいから、デルタはより少ないビットを使用して符号化され得る。圧縮されたストリームを復号するには、
【数５】
2005509385.tif 000007
【００４０】
デルタ符号化のシグナルフローグラフが、図２に示されている。１６ビットのデルタ符号化を使用して、テスト・データベースは１．９７（４９．２４％）の因数で圧縮された。この因数は、近似的に、アレー・サイズおよび開始点伝送のオーバーヘッドが与えられたときの期待値である。
【００４１】
［適応デルタ符号化］
圧縮中に引き出されたデルタを吟味すると、通常、前述したビット数よりもはるかに少ないビットを使用して、それらのデルタを符号化できることが分かる。しかしながら、高速セグメント（即ち、サンプル間の位置の大きな変化、したがって大きなデルタ）を含むストロークは、符号化するのにより多くのビットを必要とするであろう。ストローク内のデルタのダイナミックレンジを測定することによって、ビットの最適数を選択してデルタ符号化を行うことができる。
【数６】
2005509385.tif 000008
【数７】
2005509385.tif 000009
ここで、ΔｘｍｉｎおよびΔｘｍａｘは、ストリーム内の最小および最大のサンプル・デルタであり、Δｘｂｉｔｓは、レンジΔｘｍａｘおよびΔｘｍｉｎを符号化するために必要なビット数を含む。信号を符号化するためには、フル精度を使用して最初のサンプルが伝送され、その次にΔｘｂｉｔｓ（したがって、復号器は各々のデルタについて幾つのビットを受け取るかを知り）およびΔｘｍｉｎが続く（したがって、復号器はｘｎの元の値を作り出すことができる）。次に、Δｘｂｉｔｓを使用してΔｘｎサンプル・デルタが符号化されて伝送される。
【００４２】
伝送を復号するためには、ΔｘｂｉｔｓおよびΔｘｍｉｎの値が読み取られ、ストロークは、
【数８】
2005509385.tif 000010
を使用して再構成される。
【００４３】
このスキームを使用して、データベースは７．４３（８６．５４％）の因数で圧縮された。注意すべきことに、この圧縮スキームは、圧縮が起こる前にダイナミックレンジ計算で利用可能なストローク内の全ての点を必要とし、したがってバッファリングなしに点のストリームを圧縮することはできない。ストリーム可能適応デルタ符号化スキームは、デルタの符号化に最適数のビットを推定するためには、短期統計を使用して実現されることができよう。
【００４４】
［改善された適応デルタ符号化］
前述した圧縮スキームにおいて、各々のストロークの開始点のフル精度符号化およびアレー・サイズを伝送するオーバーヘッドは、ビット・ストリームの有意の部分を含む。このオーバーヘッドを縮小するためには、開始ストローク点は、先行するストローク内の最後の点からのオフセットに基づいてデルタ符号化することができる。これらのオフセットの大多数は小さいが（隣接したストロークは空間的に併置される傾向がある）、大きなオフセットは有意のオーバーヘッドなしに適応させなければならないので、値は可変サイズの数値を使用して符号化される。
【００４５】
これを行うためには、ｎビットの数値が伝送され、次に、値が完了しているか（即ち、値がｎビットによって完全に定義されているか）、または値を完了するために更にビットが必要であるかを示す単一のビット・フラグが続く。ビットが必要であれば、他のｎビットが伝送され、再び完了フラグが続く。このスキームを使用すると、小さな値を少数のビットで符号化し、大きな値を合理的な効率で表すことができる。ストローク・アレーおよび点アレー・サイズを伝送するために、この同じスキームが使用される。以下の全ての圧縮スキームは、特に指示されない限り、これらの手法を使用して開始点およびアレー・サイズを符号化する。このスキームを使用して、テスト・データベースは８．２０（８７．８０％）の因数で圧縮された。
【００４６】
［適応ハフマン・デルタ符号化］
適応デルタ符号化は、全ダイナミックレンジを符号化するのに必要な最小ビット数を使用してデルタを符号化することによって圧縮を著しく改善したが、ストローク内の全てのデルタは、ストリーム内での頻度に関わらず同数のビットを使用して符号化される。図５は、トレーニング・データベース内のデジタル・インクから引き出されたデルタのヒストグラム、および次式を使用して計算された分布の対応するエントロピ値を示す。
【数９】
2005509385.tif 000011
【００４７】
明らかに、デルタ値はランダムに分布していないので、デルタ値をエントロピ符号化することによって、更なる圧縮ゲインが可能であろう。ハフマン符号化によって構成されるような可変長ソース・コードを使用する結果として、多くの場合、前述したように使用された固定長符号よりも少ないソース値当たりのビットを使用することができる。これを行うため、適応ハフマン符号化スキーム（Ｊ．Ｖｉｔｔｅｒ−“Ｄｅｓｉｇｎ  ａｎｄ  Ａｎａｌｙｓｉｓ  ｏｆ  Ｄｙｎａｍｉｃ  Ｈｕｆｆｍａｎ  Ｃｏｄｅｓ”−Ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  ＡＣＭ，３４，８２５〜８４５頁，１９８７）を参照）を使用して点デルタを符号化した。適応ハフマン符号化は、ソース・メッセージ確率の移動推定に基づいてソース・メッセージからコードワードへのマッピングを決定する。選択されたコードワードは、常に更新されて、現在の確率推定のために最適に維持される。
【００４８】
デジタル・インク・ストリームを符号化するため、ハフマン符号化のアルファベットは、−１６…１６のレンジにあるデルタのセット、このレンジの外にある値を表すエスケープコード、およびストロークの終わりを示す終了コードとして定義された。各々の点のＸおよびＹデルタが計算され、適応ハフマン符号化器を使用して符号化され、伝送された。デルタの絶対値が１６よりも大きければ、エスケープコードが伝送され、続いてデルタが１６ビット値として伝送される。全ての点が伝送されたとき、ストロークの終わりを示す終了コードが送られる。エントロピ符号化デルタ圧縮のシグナルフローグラフが、図３に示されている。このスキームを使用して、データベースは９．６６（８９．６５％）の因数で圧縮された。
【００４９】
［静的ハフマン・デルタ符号化］
適応ハフマン符号化によって使用されるコードワードは、符号化中に動的に生成される。その結果、ビット・ストリームは、圧縮されないアルファベット・エントリーがストリーム内で遭遇するように、該アルファベット・エントリーを含まなければならない。トレーニング・データのセットから生成された所定の静的ハフマン表を使用してデルタを圧縮すると、このオーバーヘッドを縮小することができる。なぜなら、表エントリーの伝送は必要でないからである。しかしながら、生成されたコードワードはトレーニング・データベースを全体として圧縮するには最適であるが、恣意的な個々のストロークについては最適でないかも知れない。その結果、デルタの最適圧縮に達しない圧縮が生じる可能性がある。
【００５０】
デジタル・インクを符号化するため、下記の表１で示されるように、トレーニング・データベースを使用してデルタ値のハフマン表が計算された。このスキームを使用して、データベースは、９．６９（８９．６８％）の因数で圧縮された。これは、適応ハフマン符号化スキームの非常に小さい改善である。
【表１】
2005509385.tif 000012
【００５１】
［線形予測符号化］
線形予測（例えば、Ｊ．Ｓｔｅｉｎ，Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ−Ａ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  Ｐｅｒｓｐｅｃｔｉｖｅ，Ｊｏｈｎ  Ｗｈｉｌｅｙ  ＆  Ｓｏｎｓ  Ｉｎｃ．，２０００で説明される）は、過去のサンプルの線形補間に基づいて、観察された信号の次のサンプルを推定するプロセスである。ランダムでない信号は、
【数１０】
2005509385.tif 000013
を使用して、先行するｍ個のサンプルに基づいてほぼ線形的に予測可能である。
【００５２】
残留誤差は、推定されたサンプル値と観察されたサンプル値との間の差分である。
【数１１】
2005509385.tif 000014
【００５３】
圧縮に線形予測（ＬＰ）を使用するためには、予測モデルおよび先行サンプルを使用して次のサンプルの推定が発見され、その推定の残留誤差が伝送される。したがって、推定が正確になれば、それだけ残留誤差は小さくなり、伝送に必要なビットは少なくなるであろう。
【００５４】
［単純線形予測］
線形予測を実行するためには、係数のセット｛ｃ１，．．．，ｃｍ｝が決定されなければならない。ｍ＝２ であるとき（即ち、次のサンプルは、先行する２つのサンプルに基づいて予測される）、次のサンプルは先行サンプルｘｎ−１に先行デルタｘｎ−１−ｘｎ−２を加えたものに等しいと仮定することによって、係数の単純なセットを引き出すことができる。
【数１２】
2005509385.tif 000015
【００５５】
こうして、係数｛ｃ１＝２，ｃ２＝−１｝が選択される。これらの係数の予測能力をテストおよび比較するため、トレーニング・データベース内のデジタル・インクのＸおよびＹ成分の平均二乗残留誤差が計算された。それは下記の表２に示される。
【００５６】
線形予測のＸおよびＹ残留成分のヒストグラムは、これらの分布のエントロピと共に図８および図９で示される。これらの残留値のエントロピにおける縮小は、同じデータベースから引き出されたＸおよびＹデルタのヒストグラム（図６および図７を参照）と比較したとき明らかであり、線形予測を使用することによって更なる圧縮が可能であることを示す。
【００５７】
トレーニング・データベースにおけるデジタル・インクの線形予測推定残留誤差を使用して静的ハフマン表が生成された。デジタル・インクを符号化するため、開始点が伝送され、次に後続の点について、予測値のハフマン符号化残留誤差が続く。この手順のシグナルフローグラフは図４で示される。このスキームを使用して、テスト・データベースは１４．３０（９３．０１％）の因数で圧縮された。これは最良のデルタ符号化スキームよりも著しく改善されている。
【００５８】
［改善された線形予測］
前に使用されたＬＰ係数は、次のサンプルが前のサンプルに前のデルタを加えたものと仮定して発見された。しかしながら、潜在的に優れた係数をトレーニング・データから導き出すことができる。この係数は、手書きの生成プロセスに本来備わっているバイアスを、より正確にモデル化する。
【００５９】
一連のサンプル｛ｘ１，．．．，ｘｎ｝が与えられたとすれば、最小二乗の意味で誤差を最小にして前のデータ点ｘｉ−２およびｘｉ−１からｘｉを予測する係数ｃ１およびｃ２を発見する必要がある。これを行うため、予測値の二乗和誤差Ｓが最小になるような係数を発見する。このアプローチは、Ｐ．Ｄｅｖｉｊｖｅｒ  ａｎｄ  Ｊ．Ｋｉｔｔｌｅｒ，Ｐａｔｔｅｒｎ  Ｒｅｃｏｇｎｉｔｉｏｎ−Ａ  Ｓｔａｔｉｓｔｉｃａｌ  Ａｐｐｒｏａｃｈ，Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，１９８２から導き出される。
【数１３】
2005509385.tif 000016
ここで、予測誤差は次のように計算される。
【数１４】
2005509385.tif 000017
【００６０】
理想的には、Ｓはゼロでなければならない（即ち、各々の点は誤差なしに予測される）。ｃが係数の２次元ベクトルであり、
【数１５】
2005509385.tif 000018
ｘが観察された信号値のｎ−２次元ベクトルであり、
【数１６】
2005509385.tif 000019
Ａが予測に使用されたサンプルの２×（ｎ−２）マトリックスであった場合、
【数１７】
2005509385.tif 000020
Ｓ＝０を解くため、次の式を解く：
Ａｃ＝ｘ
【００６１】
以下の古典的解：
【数１８】
2005509385.tif 000021
は明らかに有効ではない。なぜなら、Ａ−１はｎ≠４について存在しないからである。ｎ＞４について、マトリックスＡは、方程式の数が未知数の数よりも大きいことから優決定である。（Ｒ．Ｐｅｎｒｏｓｅ，“Ａ  Ｇｅｎｅｒａｌｉｚｅｄ  Ｉｎｖｅｒｓｅ  ｆｏｒ  Ｍａｔｒｉｃｅｓ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｃａｍｂｒｉｄｇｅ  Ｐｈｉｌｏｓｏｐｈｉｃａｌ  Ｓｏｃｉｅｔｙ，５１，４０６〜４１３頁，１９５５、で教示されるように）Ａの疑似反形Ａ†を使用して、最小二乗の意味で誤差を最小にする解を発見することができる。
【数１９】
2005509385.tif 000022
【００６２】
Ａの中で列と行との間に線形従属性が存在しているか、或いはＡが正方形ではなかった場合でも、疑似反形Ａ†は常に存在するであろう。計算は特異値分解に基づき、特定の閾値δよりも小さい特異値はゼロとして処理される。
【数２０】
2005509385.tif 000023
ここで、ノルム（Ａ）はＡの最大特異値であり、εは小さな数値である（以下の計算では１ｅ−１６に設定される）。
【００６３】
この手順を使用して、Ｘ係数｛ｃ１＝１．８５６５３４，ｃ２＝−０．８５６１３０｝およびＹ係数｛ｃ１＝１．９１２４８２，ｃ２＝−０．９１２９０７｝が導き出された。これらの係数を使用して、平均二乗残留誤差は、元の係数の誤差よりも低いことが発見された。以下の表２を参照されたい。これは、最適化された係数を使用して、より大きな正確度で点が予測されたことを示す。このスキームを使用して、テスト・データベースは１４．３５（９３．０３％）の因数で圧縮された。これは元の線形予測スキームよりも少しだけ改善されている。
【００６４】
［３つの点を使用する線形予測］
これまで説明した線形予測手法は、次の点の推定を計算するとき２つだけの先行サンプルを使用する。しかしながら、より多くのサンプルを使用して次の点を予測すると、更に正確な予測が可能である。先行する３つの点に基づいて線形予測を実行するとき、次のサンプルの推定は次のようになる。
【数２１】
2005509385.tif 000024
【００６５】
最適係数を計算する前述の手法を使用して、Ｘ係数｛ｃ１＝１．７９９３６３，ｃ２＝−０．７２１５１９，ｃ３＝−０．０７７５７０｝およびＹ係数｛ｃ１＝２．００８５２３，ｃ２＝−１．１０６５７６，ｃ３＝０．０９７６７４｝が導き出された。平均二乗残留誤差は、前のスキームの誤差より低いことが発見されたが（表２を参照）、このスキームの使用は、デルタ量子化のため圧縮因数の改善を生じなかった。
【表２】
2005509385.tif 000025
【００６６】
［ワーストケースの動作］
線形予測システムの場合、信号の方向が急激に変化するとき、ワーストケースの動作が起こる。なぜなら、推定手順は方向の変化を予測できず、方向変化の地点でオーバーシュートするからである。デジタル・インクの場合、これは鋭い方向変化を頻繁に繰り返して急激に走り書きする（例えば、多数の迅速な弾道的上昇および下降運動を含むただ１つのストロークを使用して、或る領域をインクで塗りつぶす）ことに対応する。
【００６７】
ワーストケース・シナリオにおける線形予測圧縮の動作をテストするため、多数のデジタル・インク走り書きが作成され、改善された線形予測スキームを使用して圧縮された。その結果は１１．９２（９１．６１％）の圧縮因数であった。これは、より一般的なインク・サンプルで達成された圧縮率よりも低いが、それでも合理的に高レベルの圧縮を与える。これは、弾道的ストロークが、一般的に、方向変化の前にゼロ速度へ減速し、その結果、速度（したがって、次のサンプルへのデルタの推定値）が低いため、方向変化の時点で小さな予測誤差を生じる事実が大きな原因である。
【００６８】
本発明は多数の実施形態を含み、それらのパフォーマンスが評価された。結果の要約は、下記の表３に示されている。線形予測符号化に基づく最良の圧縮手法は、デジタル・インクの大きなデータベース上で、１４．３５（９３．０３％）の圧縮因数を達成する。この圧縮スキームの動作は、病的条件のもとで評価され、許容できる結果を生じることが発見された。
【表３】
2005509385.tif 000026
【００６９】
本発明は、更に、個別的または集合的に本願の明細書で言及または指摘された部分、要素、および特徴にあり、これら部分、要素、または特徴の２つ以上の任意または全ての組み合わせにあると広く言うことができ、本発明が関連を有する技術で既知の同値を有する特定の整数が言及されている場合は、そのような既知の同値は、あたかも個々に記載されているかのように、ここに組み込まれていると考えられる。
【００７０】
好適な実施形態を詳細に説明してきたが、これまで説明し、且つ特許請求の範囲に記載したような本発明の範囲から逸脱することなく、当業者による様々な変更、置換、および代替が可能であることを理解すべきである。
【図面の簡単な説明】
【００７１】
【図１】本発明の実施形態に従った方法を実行するのに適したプロセッサを示す。
【図２】本発明の実施形態に従ったデルタ符号化器のシグナルフローグラフを示す。
【図３】本発明の実施形態に従った適応ハフマン・デルタ（Ｈｕｆｆｍａｎ  Ｄｅｌｔａ）符号化器のシグナルフローグラフを示す。
【図４】本発明の実施形態に従った線形予測符号化器のシグナルフローグラフを示す。
【図５】トレーニング・データベース内のデジタル・インクから引き出されたデルタのヒストグラムおよび対応するエントロピ値を示す。
【図６】トレーニング・データベース内のデジタル・インクから引き出されたｘデルタのヒストグラムおよび対応するエントロピ値を示す。
【図７】トレーニング・データベース内のデジタル・インクから引き出されたｙデルタのヒストグラムおよび対応するエントロピ値を示す。
【図８】線形予測を使用するｘ残差のヒストグラムおよび対応するエントロピ値を示す。
【図９】線形予測を使用するｙ残差のヒストグラムおよび対応するエントロピ値を示す。
【図１】
2005509385.tif 000030
【図２】
2005509385.tif 000031
【図３】
2005509385.tif 000032
【図４】
2005509385.tif 000033
【図５】
2005509385.tif 000034
【図６】
2005509385.tif 000035
【図７】
2005509385.tif 000036
【図８】
2005509385.tif 000037
【図９】
2005509385.tif 000038
【国際調査報告】
2005509385.tif 000039
2005509385.tif 000040
2005509385.tif 000041