JP5580295B2 - 規則的点ネットワークにおけるベクトルをカウントする方法 - Google Patents

Description

本発明は、デジタルデータの圧縮、検索、比較又は解凍などのアプリケーションのためのデジタルデータ処理の技術分野に関する。本発明は、オーディオビジュアルデータの処理、より一般的には、全てのタイプのデジタルデータの処理に関する。本発明の目的は、処理時間を削減し、コンピューティングパワー、メモリの容量に関する情報処理リソースの必要性を削減することである。

アプリケーションは、全てではないが、表示に大量のデータを必要とする画像処理に関係する。記憶に必要なサイズと伝送時間を削減するためには、ビデオ情報を抽出処理し、コード化して、情報圧縮を行う。このコード化された情報は、コード化のパフォーマンスに有害なリダンダンシーを避け、周波数と空間に関して、最適な再構成可能な状態にする必要がある。そのために、ウェーブレット変換技術が知られている。その座標は、ベクトルラティスを構成するもので、ベクトル量子化が行われる。

ベクトル量子化（ＶＱ）の原理は、各サンプルを個別にコード化する代わりに、ベクトルを形成するサンプルのシーケンスをコード化することである。コード化は、ベクトルによりシーケンスを近似することによって行われる。通常"コードブック"と呼ばれるカタログに属するベクトルを使ってコード化する。コードブックの各ベクトルには、インデックスが付けられる。コード化する時に、それを表わすために使用するのは、コード化するサンプルシーケンスに最も近いベクトルのインデックスである。

公知の解決法では、各ベクトルを決定すること、それをメモリに記憶させること、更に、ベクトル全体に対し処理することが、必要である。ベクトルの基底(base)は、数ギガバイトを必要とする可能性がある。同様に大きい基底の計算には長時間が必要である。本発明の目的は、これらの欠点を回避する、カウント方法とインデキシング方法を提供することである。

従来技術
従来技術として、国際特許出願WO9933185が公知である。このコード化方法は、予め決められた順序で、量子化ベクトルと同一の成分を有するベクトル（リーダー(代表)ベクトル：vecteur leader）を決定するステップと、前記リーダーベクトルと同一成分を持ち、前記グループにおいて予め決められた順序で並べられているベクトルにより形成された前記グループにおける量子化されたベクトルのオーダー(ordre)又はランク(rang)のレベルを決定するステップからなる。前記方法は、一方では前記決められたリーダーベクトルを表わすインデックスから、他方、前記ランクを表わすインデックスから一つのコードを形成する。

圧縮のためのベクトル量子化の設計における重大な問題は、規則的点ラティス（le reseau regulier de points）（量子化辞書を形成する）におけるベクトルのカウントとインデキシングの問題である。本発明は、このために、一般ガウス分布のソース（source：例えば、ウェーブレット係数など）のケースで、これら問題を解決するための解決法を提供する。

代数的ベクトル量子化（La quantification vectorielle algebrique）：
量子化については、数十年に亘って研究されてきた。これら研究は、今日、レート歪理論に関して、多くの成果をもたらしている。特に、ベクトル量子化（QV）は、固定長のコード化が要求される場合には、スカラ量子化（QS）に比べて多くの利点を持っていることが証明された。また、シャノンは、n次元ベクトル量子化が十分に大きい場合は、QVのパフォーマンスは最適な理論的パフォーマンスに近いことを証明した。

しかし、高度に複雑な計算を犠牲にして、ＱＶを、最適なパフォーマンスに近づけようとすることに注意しなければならない；この複雑さは、ベクトルの次元と共に、指数関数的に増加する。通常、ＱＶは、ソース（学習シーケンス）を表わす統計データから構成される非構造化辞書（dictionnaire non structure）を使って実行される。この場合において、複雑さと辞書のサイズによる記憶容量は、圧縮アプリケーションに対して阻害的要因となる。

また、辞書のロバスト性(robustesse)の問題がある。辞書は、与えられたトレーニングシーケンス用に最適化されているので、トレーニングシーケンス以外の画像に対し、パフォーマンスが低い。これら問題を克服するための解決法は、代数的ベクトル量子化（QVA）、又は、点の規則的ラティス（reseaux reguliers）に対しベクトル量子化等の構造化されたｎ次元のQVを使用することである。辞書のベクトルは構造化された規則的ラティスに属するようになっているので、QVAのパフォーマンスは一般的に非構造化QAのパフォーマンスより低い。

しかし、ほとんどのアプリケーションでは、この小さな欠点は、QVAに対しては、辞書を作成される、又は、記憶される必要はないということ、及び、コード化の複雑さが軽減されるということによって埋め合わされる。

規則的点ラティスによる量子化は、一様なスカラ量子化の一般化と見なすことができる。非構造化ＱＶの場合のように、本書では、用語ＱＶＡは、ベクトル量子化を意味するように、又は、ベクトル量子化器（quantificateur vectoriel）を意味するように、使用される。 ＱＶＡは、分割ゲイン及び形状と、ベクトルの係数の間で、空間依存性を考慮に入れる。ソース分布がどのようなものであろうと、ＱＶＡはＱＳより常に効率が良い。

空間R^ｎの内の規則的ラティスは、基本的なラティスである線形独立ベクトルの集合の全ての組み合わせによって構成されている。これは、ラティスの基底(base)を形成する。｛y│y = u₁a₁ + u₂a₂ + … u_na_n｝。但し、係数ｕ_ｉは整数である。空間の分割は、規則的であって、選択された基底ベクトルのみに依存する。各基底は、異なる点の規則的なラティスを定義する。

ＱＶＡを使うと、一般化Lloydアルゴリズムに基づくアルゴリズムを使って設計された、１つのＱＶに関する計算コストと記憶に関するコストを大幅に削減できる可能性がある。確かに、量子化ベクトルのような規則的ラティスベクトルを使用すると、辞書の構築操作を削減できる：辞書は、選択したラティス構造により暗黙的に構築される。
Conway と Sloaneの論文「Fast quantizing and decoding algorithms for lattice quantizers and codes」（IEEE Trans . On Information Theory, vol. 28, no.2 , pp.227-232 mars 1982）には、n次元ベクトルのみに依存する丸め込み操作（operations d'arrondis）を単純に使う高速なアルゴリズムについて説明されている。 1979年、Gershoは、（高フローに対し）１つのレート歪み性能（performances debit-distorsion）は、ほぼ最適である、と予想した。

しかしながら、ＱＶＡは数学的に低フローに対し最適化されていない。しかし、このような量子化要素（quantificateurs）によりもたらされる複雑さを低減させることにより、大きい次元のベクトルを使用することができ、与えられたフローの実験のパフォーマンスを向上させる。エントロピーコーダ（un codeur entropique）とＱＶＡとを組み合わせて、レート歪みについての良好な性能を得ることができる。これにより、ウェーブレット分野における、ＱＶＡの研究に対するモーティベーションが高まった。ＱＡに対する多くの研究がガウシアン、ラプラシアンソース（sources Gaussienne et Laplacienne）に対して行われた。しかし、１より小さい減衰パラメータをもつ一般ガウシアンタイプのソースの場合は、レート歪に関して、キュービック ラティスＺ^ｎは、ラティスＥ_８、Leechラティスと比べると性能が良いことが証明された。この結果は、ウェーブレット変換とＱＶＡとを組合せる我々の研究に刺激を与えた。

国際特許出願WO9933185

「Fast quantizing and decoding algorithms for lattice quantizers and codes」（IEEE Trans . On Information Theory, Conway、Sloane、 vol. 28, no.2 , pp.227-232 mars 1982）

本発明により処理される課題
ＱＶＡによる量子化が複雑である場合には、辞書の規則的幾何学的構造のために、その実装はすぐには行われない。漸近モデルの場合、過負荷ノイズは無視される。可変長符号化と無限大の辞書の使用を想定しているからである。これは、計算と記憶の観点から、具体的な複数の問題を提起する。特に、計算と記憶に関してである。これら二つの基本的な問題は、ＱＶＡの設計において、重要である。

ａ）インデキシング
インデキシングは、各量子化ベクトルに対して、インデックスを、割り当てることであり、量子化とは別の操作である。一旦コード化されると、インデックスは、デコーダーまでチャネルを介して送信される。この操作は圧縮チェーンにおいて基本的である。それは、ビットレートを決定し、曖昧さのないベクトル復号化を可能にする。公知の方法によると、一般的にメモリについては極めて安価になるが、計算については、かなり複雑になる（再帰的アルゴリズム）。又は、特別な場合（ラティスタイプ又は特別のトランケーション）にだけ動作するものである。本発明は、一般化ガウス形分布に対しインデキシングすることを可能にし、一般的なアプローチに関するもので、メモリコスト/計算コストの妥協を実現する。第１特許はこの課題に対する解決法を提案する。

b）カウント
インデックス法は、通常、ラティス数の増大に基づいている。したがって、ソースの分布に依存する、ｎ次元面（又はボリューム内）のラティスベクトルをカウントできなければならない。カウントについての従来のアプローチは、生成された級数の使用に基づいている。この手順で、関数Nuが導入された。それらを使うと、ピラミッド上で（即ち、ラプラス分布の場合）カウントすることが可能になる。

本発明は、特に、メモリコスト/計算コストの間の良好な妥協をもたらす、一般化ガウス分布上のカウントステップに関する。本発明の第二の発明は、この課題を解決するものである。発明は、主として、カウントとインデキシング、及び、画像又はビデオの圧縮アプリケーションにおけるＱＶＡの実装を対象とする。これら2つのアプローチ及びQVAは、オーディオ信号（サウンド、音声、音楽）の圧縮のために使用される。

従って、本発明は、広い意味で、次元（dimension）ｄのr_δ ^p _dに等しく、その座標がｋより小さいか、kに等しいノルムｌ_ｐのリーダーベクトル（vecteurs leaders）の数の推定方法に関する。r_δ ^p _dは関数Ｔ（ｘ_i）の結果（計算結果）の総和により決定される。但し、ｉは１とｄの間の値をとる変数である。前記関数Ｔ（ｘ_i）は、少なくとも前記リーダーベクトルの一部分（partie）に対し、精度ファクタδ（un facteur de precision delta）による冪乗ｐの座標ｘiの商(division)を出力し（retouner）、前記商は、一番近い整数に丸み込まれる（例えば、四捨五入される）。本方法はリーダーベクトルを決定するステップを含んでいない。

本発明は、また、データ圧縮のフローの推定のため、又は、リーダーベクトルのインデキシングのための、推定法のアプリケーションに関するものである。

本発明の理解は、図面を参照して、非制限的な実施例を読むことにより、深めることができる。

必要なメモリ容量に関して、通常の方法とｐ＝１、δ＝１、B=４に対して提案する本発明の方法との比較を示す。

付属資料１，２は、本発明の実施に関するアルゴリズムとカウント方法の２つの実施例を示す。

ラティスベクトルのインデキシングは、ラティスの量子化アプリケーションにおける重要な問題である。本発明は、ラティス リーダーベクトルとパーティション理論を使って、この問題に対するソリューションを与えるものである。一般化ガウス分布のソースに対して、それを使うことができ、それを使うと、プロダクトコードを使うことができる。また、それを使うと、高次元のベクトルのインデキシングが可能になる。

ベクトルの次元がかなり高い場合は、ベクトル量子化（ＱＶ）を使うと、最適理論のパフォーマスを得ることができる。しかし、残念なことではあるが、ＬＢＧ等の、最適に構造化（non structuree optimale）されていないＱＶ計算の複雑さは、次元が高くなるにつれ、指数関数的に高まる。加えて、記憶容量が極めて重要になる。次元に関する問題を解決するためには、ラティスベクトル量子化（ＬＶＱ）のような拘束型ＱＶ（QV contrainte）を使用すればよい。

ＬＶＱアプローチによると、コードベクトルが空間に規則的に分布している一つの構造化辞書を設計することになる。その結果、空間におけるベクトルの位置を最適化する代わりに、ラティスベクトルをインデキシングして、分布の形状に応じてソースを適合させることができる。大半の実データのソースに対して、プロダクトコードを使って、これを効率的に実行することができ、対称的ユニモーダルソース分布（des distributions de sources unimodales symetriques）に対して、レート-歪を最適な値に導くことができる。

ソースの分布に応じて、これらの分布を、同一形状を持つ同心超曲面（hypersurface concentrique）の集合として解釈することができる。それぞれの面のノルム（半径）に対応する第１インデックス（prefixe）を割り当て、同一面に属するベクトルのカウントに対応する第２単一インデックス（suffixe）を割り当て、ラティスコードワードにインデックスを付与することができる。

大量のデータソース(例えば、特に、ウェーブレット変換によって得られた、画像の係数と音声サブバンド等）は、一般化ガウス分布によってモデル化することができる。この分布のファミリーは、一変数(univariee)確率変数に対して、１つのシェープファクタp（ＧＧ（p））によってパラメータ化される。分布（ＧＧ（ｐ））を持つソースの興味深い性質は、ノルムｌｐのエンベロープが一定確率面に対応していることである。
これは、効率的なプロダクトコードの開発につながる。

prefixeの計算が簡単である場合でも、suffixeは、超曲面（hypersurface）上のラティスベクトルのカウント及びインデキシングが必要である。また、空間の次元が増大すると、インデキシング及びカウント操作が非常に複雑になる。その理由は、次の表に示されるように、１つのエンベロープ上に存在するベクトルの数が、ノルムと共に大きく増加するからである。表には、一つのラティスＺ^ｎと複数の次元とノルム値に関して、１つのノルムｌ _１の場合における、１つの与えられた超曲面のベクトルの数と、このハイパーピラミッド（cardinality）の上にあるラティスベクトルの全数との比較が記載されている。

文献では、サフィックスのインデキシングは、通常異なる２つの技術に基づいて行われている。

最初のアプローチは、超曲面上にあるベクトルの全数（cardinalite:基数）を考慮して、１つのインデックスを割り当てることである。第２のアプローチは、リーダーベクトルの概念を使って、ラティスの対称性を利用することである。ノルムlｐのエンベロープの(複数)リーダーは、ラティスの(複数)ベクトルに対応している。そのベクトルを基にして、前記の対応するエンベロープに存在する他の全てのラティスベクトルは、それら座標の置換（permutation）、符号変化により、得ることができる。これら２つのアプローチは、isotropicソースに対し、同様のレート−歪パフォーマスを示す。

しかしながら、ラティスのインデキシングについての多くの研究は、ラプラス分布又はガウス分布に対する解法を提案している。これら分布は、それぞれ、形状パラメータｐ＝１、ｐ＝２を持つGG(ｐ)の特別なケースである。ｐ＝0.5という特別なケースに対する解法を提案する研究者もいる。しかし、このカウント方法では、プロダクトコードを構成することはできず、実際には、インデキシングの方法も極めて複雑である。特に、高次元、大きいノルムをもつｐ≠0.5、１又は２の場合は複雑である。

本発明は、0＜p≦2を持つエンベロープＧＧ（ｐ）の上にあるラティスベクトルＺ^ｎに対する新規な代替案を提案する。提案する解決法は、ベクトルに基礎を置いて、分割理論を使う。
分割理論（la theorie des partitions）を使うと、前記複雑性、必要な記憶容量の問題を解決でき、リーダーベクトルを生成し、ベクトルにインデックスを付与することができる。
本発明は、リーダーのインデキシング、他のものの間のフローの推定等のアプリケーションのために、半径ｒ、次元ｄ、より大きい座標（coordonnee plus forte）ｋのエンベロープ上のリーダー数をカウントする経済的なカウントアルゴリズムをここに提案する。

以下の説明において、最初の部分では、ＬＶＱの原則を示して、インデキシング/カウントの問題について説明する。次の部分では、形状パラメータｐがどのようなものであろうとも、極めて大きいコードブックLVQをカウントするための効率的な解法を提案する。次に、提案されたアプローチの、メモリコストについて説明する。

２．ラティスベクトルのインデキシング
２．１ ラティスの定義
Ｒ^ｎにおけるラティスΛは、線形独立ベクトルａ_ｉ（ラティスの基底）の集合の全部の組合せで、次のように構成される。
Λ = ｛x│x = u₁a₁ + u₂a₂ + … u_na_n｝ （１）
但し、ｕ_ｉは整数である。空間分割は、規則的で、選ばれた基底ベクトルａ_ｉεＲ^ｍ（ｍ≧ｎ）に一意的に従属している。基底ベクトルの各集合は、異なるラティスを定義することに注意すべきである。

１つのラティスの各ベクトルｖは、一定ノルムｌｐを持つベクトルを含む表面又は超平面（hypersurface)に属していると見なすことができ、次式で与えられる。：

プロダクトコード（code produit）を使って、指定したラティスのベクトルをコード化することができる。ソースベクトルの分布がラプラシアン分布であるならば、適切なプロダクトコードは、“１つのベクトルのノルムｌ _１に対応するprefixe”及び“問題とするノルム１_１に等しい１つの半径を持つハイパーピラミッド上の位置に対応するsuffixe”から構成されていることは、明らかである。 一定のノルムｌ_１の超曲面は、ハイパーピラミッドと呼ばれる。

形状パラメータが１に等しい又は１より小さい、一般化ガウス分布を持つソースの場合、Ｄ_４、Ｅ_８上の立方体的ラティスＺ_ｎ又はLeechラティスの優位性が証明されている[12]。従って、本書の残りの部分では、立方体的ラティスＺ^ｎに基づく１つのＬＶＱの設計を中心に説明する。

２．２ 全カウント数に基づくインデキシング
ガウス分布又はラプラシアン分布について、及び、全カウントの原理に基づく種々のラティスについて、複数のカウント方法が、これまで提案されてきた。特に、ソースがラプラシアン分布の場合、ラティスＺ^ｎに関して、ノルムｌ _１のハイパーピラミッド上にあるラティスのベクトルの全数を計算するための再帰的公式（formule recursive）が知られている。
カウントのこの公式は、０と２の間の形状ファクタｐを使って、ソースの一般化ガウス分布に拡張されている。これら解法を使うと、tranctureノルムｌｐの内部に存在するベクトルの数を計算することができる。
しかしながら、これら解法は、インデックスをラティスＺ^ｎに割り当てるアルゴリズムを提示するものではない。
また、この解法は、超曲面上にあるベクトルの数を決定するものではない。このため、プロダクトコードを使用することは困難である。

従来の研究の中で提案されているアルゴリズムは、０＜ｐ≦２に対するプロダクト コードスキームに基づいて、ベクトル（複数）にインデックスを付与するものである。それは、一般化シータ級数（series theta）に基づいて[４]、ラティス幾何学を使うものである。ｐ＝１または２については、この級数の展開は比較的に単純である。これに対し、ｐがそれ以外の値である場合、この級数は極めて複雑になる。クローズドフォーム（forme fermee）が生成されず、公式（mathematiques formelles）を使用することができないからである。提案された解法によれば、種々の次元及び高次元について、可能なノルム値を決定する必要があるが、一般的には、これを所定時間内に実行することはできない。

また、実施する際に、特に、高次元に対して（前記表を参照）、超曲面の基数（cardinalite)は、急速にnon-tractableな値（扱いにくい値）に達するので、エンベロープの基数に基づくインデキシング技術は、急速にコンピュータの計算精度（precision informatique）を越えてしまう。

２．３ ベクトル（リーダー）に基づくインデキシング
リーダーに基づく方法は、ラティスの対称性を利用する。その方法は、一定ノルムのエンベロープに対する効率的なインデキシング アルゴリズムを使う。ラティスベクトルの全数に基づいてインデックスを割り当てるのではなく、リーダーと呼ばれる、少ない数のベクトルに基づいて割り当てるものである。
ラティスの対称性は、様々であるので、個別に処理される。対称性がない場合には、これは、全カウント法と比べると、より効率的なソースのインデキシング方法である。
また、コード化アルゴリズムにより管理されるインデックスは、エンベロープの基数よりもっと小さい。これを使うと、全カウントに基づく方法ではインデックスを付与できないベクトルに対して、２進数精度（precision binaire)で、インデックスを付与することができる。

プロダクトコードのアーキテクチャでは、ラティスの対称性を別にして、suffixeインデックスは、リーダーの数が少ないインデックスを含んでいる。前記suffixeインデックスに基づいて、超曲面の全ての他のベクトルを割り当てることができる。ラティスＺ^ｎに関して、対称性は、２つの基本的な操作に対応している:即ち、ベクトル座標の“符号変化（changements de signe）”と“置換（permutation）”である。
第１の操作は、ベクトルが存在する一つの象限の変化に対応している。例えば、２次元のベクトル（７，−３）が第４象限にあるとする。これに対し、ベクトル（−７、−３）は第３象限にある。これらベクトルはｙ軸に対して対称である。
第２の操作は、象限内の対称性に対応する。例えば、ベクトル（−７、３）と（−３，７）は、２つ共に第２象限にあり、同象限の２等分線に対して、対称である。
この場合、“これらベクトルは、これらベクトルのリーダーであるベクトル（３，７）の置換及び符号変化から生成されること”が分かる。ベクトル（３，７）は、これらベクトルのリーダーベクトルである。全ての置換と符号変化を使って、リーダー（３，７）は８つのベクトルを代表することができる。
この比は、超曲面の次元と共に急速に大きくなる（表１参照）。

従って、このインデキシング方法は、超曲面上の全ベクトルに直接インデックスを付与する代わりに、各ベクトルに対し、３つのインデックスのセットを割り当てる：即ち、１つは、リーダーに対応するものであり、他の２つは、リーダーの置換および符号変化に対応するものである。置換と符号のインデックスの計算方法の詳細については、[５]を参照のこと。

３．カウント方法の提案
本発明は、リーダーをカウントする方法を提案する。カウント アルゴリズムの使用を理解するために、リーダーのインデキシングに関する非限定的な実施例を示す。まず、ノルムｌ _１に対するインデキシングについて説明する。次に、ノルムｌ_ｐのより一般的なケースについて例を挙げて説明する。
その後、セクション3.3で、本発明について詳述する。

3.1 ノルムｌ₁に関するリーダーのインデキシング
3.1.1 原理
本発明が提案するカウント アルゴリズムを適用する、リーダーのインデキシング方法は、逆辞書順序（ordre lexicographique inverse）で全リーダーを分類する分類に基づく。また、インデックスを付与しなければならないリーダーに先行するベクトルの数に応じて、インデックスを割り当てる。この場合、インデキシングは、もはやリソースを大量消費する１つのサーチアルゴリズム、又は、直接アドレッシングによるものではなく、むしろ、低コストのカウントアルゴリズムによるものである。これは、それらに関する明らかな知識に依存するものではなく、むしろ、リーダーの量に依存するもので、このようにすれば、変換表を作成しなくてもよくなる。

半径rのハイパーピラミッドは、全てのベクトルv = (v₁, v₂, …, v_d)から構成されている。但し、||ｖ||_１＝ｒである。上述したように、リーダーは、超曲面の基本ベクトルである。置換と符号変化操作によって、そこから、同超曲面上にある他のベクトルを導き出す。確かに、リーダーは、（または降順）昇順でソートされる正の座標を持つベクトルである。したがって、ノルムｒ、次元dのベクトルは、次の条件を満足するベクトルである。：

３．１．２ 分割理論との関係
ノルムｌ₁の場合、セクション3.1.1で説明した条件は数論の分割理論（theorie des partitions）に関連していることに注意しなければならない。確かに、数論では、正の整数rの分割は、正の整数の和（部分（part）とも呼ばれる）としてrを記述する方法である。ｒの別の分割数は、次の分割関数P（ｒ）で与えられる：

これは、級数ｑ[10、16、17]と呼ばれるオイラー関数の逆数（reciproque）に相当する。数学の進歩は、関数Ｐ(ｒ)の表現法を導き、計算の迅速化を可能にしている。

たとえば、ｒ＝５に関して、上記式（2）によって，Ｐ（5）＝７となる。確かに、数５の可能な全分割は、(5)、(1,4)、（2、3）、（1、1、3）、（1、2、2）、（1、1、1、1、1）である。５次元ベクトルとして、これらの分割を書き換えると、（0、0、0、0、5）、（0、0、0、1、4）、（0、0、0、2、3）、（ 0、0、1、1、3）、（0、0、1、2、2）、（0、1、1、1、2）と（1、1、1、1、1）となる。これらが、まさに、ノルムｒ＝５とｄ＝５のハイパーピラミッドのリーダーと対応していることが分かる。つまり、セクション3.1.1の２つの要件を満たすノルムｒ＝５とｄ＝５のハイパーピラミッドにおける唯一のベクトル（複数）である。

しかし、ｄ次元のラティスにおいて、ｒに等しいノルムｌ1のエンベロープは重要である。但し、ｒ≠ｄとする。この場合、関数q（r、d）[10、18]を使うことができる。この関数は、ｄ以下の部分(部分)を持つｒの分割数を計算するものである（分割理論において、これは、部分の数は問わないが、ｄより大きい要素を持たない、ｒの分割数を計算することと同じことである）。
したがって、ノルムｒ＝５と次元ｄ=３のハイパーピラミッドに対して、ｑ（５，３）＝５である。即ち、５つのリーダーは次のとおりである。：（0、0、5） （0、1、4）、（0、2、3）、（1、1、3）、（1、2、2）。

関数ｑ（ｒ、ｄ）は、次の漸化式から計算することができる。
ｑ(ｒ,ｄ) = ｑ(ｒ, ｄ−1) + ｑ(ｒ−ｄ, d) (3)
但し、ｑ（ｒ、ｄ）＝Ｐ（ｒ）で、ｄ≧ｒ、ｑ（１、ｄ）＝１、及び、ｑ（ｒ、0）＝0。

３.１．３ 関数q（r、d）を使用して、リーダーにインデックスを付与する
以下に説明するように、式（3）が与えられたハイパーピラミッドの上のリーダーの全数を与えるのみならず、同式は、変換テーブルを使うことなく、リーダーに対し唯一の一群のインデックスを割り当てるのに使うことができる。
インデックス アルゴリズムの原理を説明するために、次のようにハイパーピラミッドのリーダーが、次のように逆辞書式順序で分類されていると仮定する。

したがって、リーダーｌのインデックスは、これに先行するリーダーの数に対応している。上記例では、リーダー（0、...、1、1、ｒ_ｎ−２）にはインデックス３が割り当てられる。

第１命題（proposition）では、リーダーのインデキシングアルゴリズムが記述されている。

第１命題
ｖ＝（ｖ₁、ｖ₂、…、ｖ_ｎ）は、一定ノルムｌ₁の１つのエンベロープ上の１つのリーダーベクトルｌ＝（ｘ_１、ｘ_２、…、ｘ_ｎ）を持つラティスベクトルＺ^ｎであるとする。リーダーのインデックスＩ_１は次式で与えられる。：

それら全てをリスト化せずに、第１グループのリーダーの数をカウントするために、分割関数ｑ（ｒ、ｄ）が使われる。なぜなら、ｎ番目の座標がｇ_ｎに等しいリーダーの数は、次の注（remarque）を使って簡単に計算することができるからである。

注（Remarque）：
ノルムｒ_ｎ、次元ｎのリーダー（その最大座標がｇ_ｎに等しい）の数の計算は、数r_n-g_n（但し、ｇ_ｎより大きい部分がなく、ｎ−1部分より小さい）の分割数を、計算することに等しい。

ほとんどの場合、q(r_n-g_n,n-1)を適用して、分割数をカウントすることができる。しかし、このアプローチは、r_n-g_n<g_nの場合しか正しくない。この場合、r_n-g_nの全ての分割はｇ_ｎより大きい部分を持っていないと暗黙に仮定されている。しかしながら、一般的な場合、r_n-g_n<g_nは保証されない場合（例えば、ノルムｒ_ｎ＝２０、次元ｎ＝５、最大部分が７のベクトルの数は、ｑ（20-7、５-１）＝ｑ（13、4）を導く場合（但し20−7≪７ではない））、q(r_n-g_n, n-1)の計算は、真(valide)のベクトルの数について誤った値を算出する。r_n-g_n の複数の分割がg_nより大きい部分を持つこともあるからである（この場合セクション３．１.１の条件２が満たされていない）。

結果を追加次元（dimensions additionnelles）に拡張することにより、最大座標がｘ_ｎに等しいベクトルであって、１に先行するベクトルの数は、次式で与えられる。

式（5）、（6）を組合せて、一般式を導き、１より前に位置するリーダーベクトルの全数を計算し、従って、１のインデックスＩ_Ｉを計算することができる（式（４））。

但し、ｊ＝０に対し、ｘｎ＋１＝＋∞

一つのベクトルのノルムｌ_ｐは、精度δを持つことが知られており、次式で得られる。

第２命題：
ベクトルν = (v₁, v₂, …, v_n)を、一定ノルムｌｐの一つのエンベロープの上にある１つのリーダーベクトルｌ = (x₁, x₂, …, x_n)を持つ１つのラティスベクトルＺ^ｎであるとする。リーダーベクトルＩ_１のインデックスは次式により与えられる。

メモリ容量は、主として、エンベロープのノルムと次元に依存していることに留意すべきである。ベクトルの数がＢの選択を決定する。

必要とするメモリ容量が非常に低いこと及び全てのベクトルを知る必要がないという事実があるので、64, 128, 256, 512のように大きい次元のラティスベクトルに対しても、インデキシングすることができる。従前の研究においては、実際のアプリケーションでは、次元が１６に制限されていた。

Claims (5)

1. 
2. 
3. 
4. データ圧縮のレートの推定を行うことを更に含むことを特徴とする請求項１乃至３のいずれか１項に記載の処理方法。
5. リーダーベクトルのインデキシングを行うことを更に含むことを特徴とする請求項１乃至３のいずれか１項に記載の処理方法。

Images