(57)【特許請求の範囲】
【請求項１】
【化１】
0005584203.tif 000083
【請求項２】
前記処理方法は、計算において、リーダーベクトルｌ以外のベクトルを決定するステップを含まないことを特徴とする請求項１に記載の処理方法。
【請求項３】
【化２】
0005584203.tif 000084
【請求項４】
【化３】
0005584203.tif 000085
【請求項５】
ベクトルデータを圧縮することを更に備え、前記圧縮することは、前記リーダーベクトルインデックスＩｌのバイナリコード化の結果並びに少なくとも一つの符合インデックスＩｓ、ノルムインデックスＩｎ及び置換インデックスＩｐをメモリに記憶することからなる請求項１乃至４のいずれか一項に記載の処理方法。
【請求項６】
前記ベクトルデータは、
デジタル画像、
デジタルビデオシーケンス、
デジタルオーディオデータ、
デジタル３次元オブジェクト、
デジタルアニメ３次元オブジェクト、
前記ベクトルデータは変換に由来する複数係数、及び
データベースにおいて登録された情報からなる群から選択したことを特徴とする請求項５に記載の処理方法。
【請求項７】
ベクトルデータベースにおいてサーチすることを更に備え、前記サーチすることは、一つのインデックスＩｌ，ｒｅｆ並びに少なくとも一つの符号インデックスＩｓ，ｒｅｆ、ノルムインデックスＩｎ，ｒｅｆ及び置換インデックスＩｐ，ｒｅｆを参照情報として算出することと、同一インデックスを付加されたデータをサーチすることと、からなる請求項１乃至４のいずれか一項に記載の処理方法。
【請求項８】
前記ベクトルデータは、
デジタル画像、
デジタルビデオシーケンス、
デジタルオーディオデータ、
デジタル３次元オブジェクト、
デジタルアニメ３次元オブジェクト、
データベースにおいて登録された情報、及び
前記ベクトルデータは変換に由来する複数係数からなる群から選択したことを特徴とする請求項７に記載の処理方法。
【請求項９】
【化４】
0005584203.tif 000086
【請求項１０】
【化５】
0005584203.tif 000087
【請求項１１】
【化６】
0005584203.tif 000088
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータの圧縮、検索、比較又は解凍などのアプリケーションのためのデジタルデータ処理の技術分野に関する。本発明は、オーディオビジュアルデータの処理、より一般的には、全てのタイプのデジタルデータの処理に関する。本発明の目的は、処理時間を削減し、コンピューティングパワー、メモリの容量に関する情報処理リソースの必要性を削減することである。
【背景技術】
【０００２】
アプリケーションは、全てではないが、表示に大量のデータを必要とする画像処理に関係する。記憶に必要なサイズと伝送時間を削減するためには、ビデオ情報を抽出処理し、コード化して、情報圧縮を行う。このコード化された情報は、コード化のパフォーマンスに有害なリダンダンシーを避け、周波数と空間に関して、最適な再構成可能な状態にする必要がある。そのために、ウェーブレット変換技術が知られている。その座標は、ベクトルラティスを構成するもので、ベクトル量子化が行われる。
【０００３】
ベクトル量子化（ＶＱ）の原理は、各サンプルを個別にコード化する代わりに、ベクトルを形成するサンプルのシーケンスをコード化することである。コード化は、ベクトルによりシーケンスを近似することによって行われる。通常"コードブック"と呼ばれるカタログに属するベクトルを使ってコード化する。コードブックの各ベクトルには、インデックスが付けられる。コード化する時に、それを表わすために使用するのは、コード化するサンプルシーケンスに最も近いベクトルのインデックスである。
【０００４】
公知の解決法では、各ベクトルを決定すること、それをメモリに記憶させること、更に、ベクトル全体に対し処理することが、必要である。ベクトルの基底(base)は、数ギガバイトを必要とする可能性がある。同様に大きい基底の計算には長時間が必要である。本発明の目的は、これらの欠点を回避する、カウント方法とインデキシング方法を提供することである。
【０００５】
技術水準
量子化方法は、論文[１]により公知である。
【０００６】
ラティス（reseau：lattice）は、数学的に、加法群（additif）を形成するｎ次元空間のベクトルの集合である。論文[２]は該ラティスについて説明している。
【０００７】
従来技術として、国際特許出願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 = u1a1 + u2a2 + … unan｝。但し、係数ｕｉは整数である。空間の分割は、規則的であって、選択された基底ベクトルのみに依存する。各基底は、異なる点の規則的なラティスを定義する。
【００１６】
ＱＶＡを使うと、一般化Lloydアルゴリズムに基づくアルゴリズムを使って設計された、１つのＱＶに関する計算コストと記憶に関するコストを大幅に削減できる可能性がある。確かに、量子化ベクトルのような規則的ラティスベクトルを使用すると、辞書の構築操作を削減できる：辞書は、選択したラティス構造により暗黙的に構築される。
【００１７】
論文[１]には、ｎ次元ベクトルのみに依存する丸め込み操作（operations d'arrondis）を単純に使う高速なアルゴリズムについて説明されている。 1979年、Gershoは、（高フローに対し）１つのレート歪み性能（performances debit-distorsion）は、ほぼ最適である、と予想した。
【００１８】
しかしながら、ＱＶＡは数学的に低フローに対し最適化されていない。しかし、このような量子化要素（quantificateurs）によりもたらされる複雑さを低減させることにより、大きい次元のベクトルを使用することができ、与えられたフローの実験のパフォーマンスを向上させる。エントロピーコーダ（un codeur entropique）とＱＶＡとを組み合わせて、レート歪みについての良好な性能を得ることができる。これにより、ウェーブレット分野における、ＱＶＡの研究に対するモーティベーションが高まった。ＱＡに対する多くの研究がガウシアン、ラプラシアンソース（sources Gaussienne et Laplacienne）に対して行われた。更に、１より小さい減衰パラメータをもつ一般ガウシアンタイプのソースの場合は、レート歪に関して、キュービック ラティスＺｎは、ラティスＥ８、Leechラティスと比べると性能が良いことが証明された。この結果は、ウェーブレット変換とＱＶＡとを組合せる我々の研究に刺激を与えた。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】国際特許出願WO9933185
【発明の概要】
【発明が解決しようとする課題】
【００２０】
ＱＶＡによる量子化が複雑である場合には、辞書の規則的幾何学的構造のために、その実装はすぐには行われない。漸近モデルの場合、過負荷ノイズは無視される。可変長符号化と無限大の辞書の使用を想定しているからである。これは、計算と記憶の観点から、具体的な複数の問題を提起する。特に、計算と記憶に関してである。これら二つの基本的な問題は、ＱＶＡの設計において、重要である。
【００２１】
ａ）インデキシング
インデキシングは、各量子化ベクトルに対して、インデックスを、割り当てることであり、量子化とは別の操作である。一旦コード化されると、インデックスは、デコーダーまでチャネルを介して送信される。この操作は圧縮チェーンにおいて基本的である。それは、ビットレートを決定し、曖昧さのないベクトル復号化を可能にする。公知の方法によると、一般的にメモリについては極めて安価になるが、計算については、かなり複雑になる（再帰的アルゴリズム）。又は、特別な場合（ラティスタイプ又は特別のトランケーション）にだけ動作するものである。本発明は、一般化ガウス形分布に対しインデキシングすることを可能にし、一般的なアプローチに関するもので、メモリコスト/計算コストの妥協を実現する。
【００２２】
b）カウント
インデックス法は、通常、ラティス数の増大に基づいている。したがって、ソースの分布に依存する、ｎ次元面（又はボリューム内）のラティスベクトルをカウントできなければならない。カウントについての従来のアプローチは、生成された級数の使用に基づいている。この手順で、関数Nuが導入された。それらを使うと、ピラミッド上で（即ち、ラプラス分布の場合）カウントすることが可能になる。
本発明は、一般化ガウス分布上のカウントを可能にする一般的なアプローチを提案し、メモリコスト/演算コストの両立性を実現した。第２の特許では、この問題を解決する。
【００２３】
本発明の目的
本発明の目的は、メモリ容量と時間が削減された情報処理リソースを使って実行可能なベクトル量子化ステップを含む処理方法を提案することである。
【課題を解決するための手段】
【００２４】
この目的で、本発明は、少なくともベクトル（複数）の一部分ｌに対し、ｄ次元空間において、少なくとも一つのリーダーベクトルインデックスI１を計算するための量子化ステップを有するデジタルデータ処理方法に関する。
前記ベクトル（複数）ｌは、入力データの記述子（descripteurs）を構成する。また、前記方法は、リーダーベクトル全体の決定するステップをもつことなく、前記リーダーベクトルのインデックスＩ1が、逆辞書順序で、前記リーダーベクトルｌに先行するベクトルの数に対応することを特徴とする。
【００２５】
前記処理方法は、計算において、リーダーベクトル以外の、どのようなリーダーベクトルを決定するステップを含まないことが好ましい。
【００２６】
【化１】
0005584203.tif 000002
【００２７】
【化２】
0005584203.tif 000003
【００２８】
【化３】
0005584203.tif 000004
【００２９】
別の変形例では、リーダーベクトルインデックスＩ１を算出するステップは、“前記リーダーベクトルｌ(x1, x2, ...xd)のノルムrの算出ステップ（但し、x1 乃至 xdは、増加する順序に並べられている）”及び“ｄと１の間の変数ｉを持つ座標ｘi上で再帰的カウントステップ”を含んでいる。前記カウントステップは、座標ｘｉがｉ+１とMIN(xi+1,ｒ-ｘi+1）との間に含まれているベクトルをカウントするもので、インデックスＩlは、カウントステップの結果の和に等しく、インデックスＩ１は、カウントステップの結果の和に等しい。
【００３０】
別の変形例では、リーダーベクトルインデックスＩ１を算出するステップは、“前記リーダーベクトル１(x1, x2, ...xd)のノルムrの算出ステップ（但し、x1 乃至 xdは、減少する順序に並べられている）”及び“１とｄの間の変数ｉを持つ座標ｘi上で再帰的カウントステップ”を含んでいる。前記カウントステップは、ベクトルをカウントするもので、その座標ｘｉはｘｉ+１とMIN(xi-1, ｒ-ｘi-1）との間に含まれている。インデックスＩlは、カウントステップの結果の和に等しい。
【００３１】
本発明は、インデックスＩ１のバイナリコード化の結果、少なくとも一つの符合インデックスＩｓ、ノルムインデックスＩｎ及び置換（permutation）インデックスＩｐを記憶する、ベクトルデータの圧縮のための、前記方法のアプリケーションに関する。前記ベクトルデータは次のようなものである。
【００３２】
−デジタル画像、
−デジタルビデオシーケンス、
−デジタルオーディオデータ、
−デジタル３次元オブジェクト、
−デジタルアニメ３次元オブジェクト、
−データベースにおいて登録された情報、
−前記ベクトルデータの変換に由来する複数係数（例：ＤＣＴ係数、ウェーブレット係数）。
【００３３】
また、本発明は、参照情報として、インデックスＩｌ,ref 、少なくとも一つの符号インデックスＩs,ref、ノルムインデックスＩn,ref及び巡回インデックスＩp,refを算出し、同一インデックスをもつデータをサーチするためのベクトルデータベースにおいて、サーチするための、前記方法のアプリケーションに関する。
【００３４】
前記ベクトルデータは次のようなものである：
−デジタル画像、
−デジタルビデオシーケンス、
−デジタルオーディオデータ、
−デジタル３次元オブジェクト、
−デジタルアニメ３次元オブジェクト、
−テキストデータベースのオブジェクト、
−データベースにおいて登録された情報、
−前記ベクトルデータの変換に由来する複数係数（例：ＤＣＴ係数、ウェーブレット係数）。
【００３５】
本発明は、また、前記方法に基づいて算出されたリーダーベクトルインデックスＩ１から、デジタルデータを再構成する方法に関する。この方法は、１つのリーダーベクトルの座標(xl, x2, ..., xd)を算出することを特徴としている。また、全リーダーベクトルを決定するステップなしに、逆辞書順序で、前記リーダーベクトルｌに先行するベクトルの数に対応するインデックスＩ１を持つリーダーベクトル１をサーチする処理に、一つのインデックスＩ１を付加することを特徴としている。
【００３６】
【化４】
0005584203.tif 000005
この加算は、和が前記インデックスＩ１より大きくなるまで行われる。前記サーチされた座標xiは、前記インデックスＩ１を超過するものであり、前記方法では、座標Xi-1に対して、値Ｉ１から加算が継続される。但し、Ｉ１は、前記インデックスを超過する前の、値Ｉ１に先行する値である。
【００３７】
【化５】
0005584203.tif 000006
また、前記関数F(A)を適用して、カウントステップの結果の加算が行われる。この加算は、和が前記インデックスＩ１より大きくなるまで行われる。前記サーチされた座標xiは、前記インデックスＩ１を超過するものであり、前記方法では、座標Xi+1に対して、値Ｉ１から加算が継続される。但し、Ｉ１は、前記インデックスを超過する前の、値Ｉ１に先行する値である。
【００３８】
【化６】
0005584203.tif 000007
再構成するためには、昇順にソートする場合、座標xdに対して、及び、降順にソートする場合、座標xｌに対して、I1' = 0とする。
【図面の簡単な説明】
【００３９】
本発明は、図面を参照し、非制限的な実施例を読むことにより、よりよく理解されるであろう。
【図１】本発明に基づくデータ処理システムの基本を示す図である。
【図２】
【化７】
0005584203.tif 000008
【図３】p = 1, δ = 1, B = 4の場合における、通常の方法と提案する方法の間のメモリ容量を比較する図である。−アネックス１は本発明を実施するためのコーディング、デコーディング アルゴリズムの１例である。
【発明を実施するための形態】
【００４０】
データ処理システムは、通常、３つのメインモジュールを備えている。最初のモジュール（1）は、画像に対応するデジタル信号等の入力データを受信し、このサンプリングされた信号に基づいて、公知の方法で、ウェーブレット変換を行う。
【００４１】
本発明の方法により、量子化モジュール（２）は、ウェーブレット係数のベクトル量子化/インデックス化方法を使って、ウェーブレット係数をコード化する。
【００４２】
３番目のモジュールは、公知のロスなしの圧縮方法で、記憶又は送信する情報のサイズを削減するためにコード化を行う。
【００４３】
量子化ステップとインデキシング ステップは、第２番目のモジュール（2）によって実行される。このステップが、本発明の対象である。このステップは、以前の技術において、多くのリソースを必要とした。それは、全リーダーべクトルを決定すること、メモリにそれらを一時的に記憶することを含んでいる。
【００４４】
ラティス上でベクトル量子化する方法は公知である。また、それは、一般的にオーディオ、ビデオ、マルチメディアの圧縮システムで使用されている。ラティス上のベクトル量子化は、一様（uniforme）スカラ量子化を多次元拡張したものである。後者は、例えば、一つの画像の各ピクセルを表す、１つの信号を、個別に、2Nレベルに量子化するものである。但し、Ｎは、量子化器に割り当てられているビット数である。ラティス上のベクトル量子化については、規則的ラティスに関連しており、それにより、問題となるラティスの属する量子化ベクトルが１つ決まる。そのコンポーネントは、コード化信号が取る値を表す。
【００４５】
具体的にいえば、量子化操作は、“各コンポーネントが１つのコード化信号により取られる値を表し、非可算の集合（実数の集合Ｒのような）に属する、１つのオリジナルベクトルの基づいて”、各コンポーネントが相対的数（nombres relatives：整数）の集合Ｚのような可算集合に属する、１つの量子化ベクトルｘを決定することである。
【００４６】
ラティスベクトルのインデキシングは、ラティスの量子化アプリケーションにおける重要な問題である。本発明は、ラティス リーダーベクトルとパーティション理論を使って、この問題に対するソリューションを与えるものである。一般化ガウス分布のソースに対して、それを使うことができ、それを使うと、プロダクトコードを使うことができる。また、それを使うと、高次元のベクトルのインデキシングが可能になる。
【００４７】
ベクトルの次元がかなり高い場合は、ベクトル量子化（ＱＶ）を使うと、最適理論のパフォーマスを得ることができる。しかし、残念なことではあるが、ＬＢＧ等の、最適に構造化（non structuree optimale）されていないＱＶ計算の複雑さは、次元が高くなるにつれ、指数関数的に高まる。加えて、記憶容量が極めて重要になる。次元に関する問題を解決するためには、ラティスベクトル量子化（ＬＶＱ）のような拘束型ＱＶ（QV contrainte）を使用すればよい。
【００４８】
ＬＶＱアプローチによると、コードベクトルが空間に規則的に分布している一つの構造化辞書を設計することになる。その結果、空間におけるベクトルの位置を最適化する代わりに、ラティスベクトルをインデキシングして、分布の形状に応じてソースを適合させることができる。大半の実データのソースに対して、プロダクトコードを使って、これを効率的に実行することができ、対称的ユニモーダルソース分布（des distributions de sources unimodales symetriques）に対して、レート-歪を最適な値に導くことができる。
【００４９】
ソースの分布に応じて、これらの分布を、同一形状を持つ同心超曲面（hypersurface concentrique）の集合として解釈することができる。それぞれの面のノルム（半径）に対応する第１インデックス（prefixe）を割り当て、同一面に属するベクトルのカウントに対応する第２単一インデックス（suffixe）を割り当て、ラティスコードワードにインデックスを付与することができる。
【００５０】
大量のデータソース(例えば、特に、ウェーブレット変換によって得られた、画像の係数と音声サブバンド等）は、一般化ガウス分布によってモデル化することができる。この分布のファミリーは、一変数(univariee)確率変数に対して、１つのシェープファクタp（ＧＧ（p））によってパラメータ化される。分布（ＧＧ（ｐ））を持つソースの興味深い性質は、ノルムｌｐのエンベロープが一定確率面に対応していることである。
これは、効率的なプロダクトコードの開発につながる。
【００５１】
prefixeの計算が簡単である場合でも、suffixeは、超曲面（hypersurface）上のラティスベクトルのカウント及びインデキシングが必要である。また、空間の次元が増大すると、インデキシング操作が非常に複雑になる。その理由は、次の表に示されるように、１つのエンベロープ上に存在するベクトルの数が、ノルムと共に大きく増加するからである。表は、一つのラティスＺｎと複数の次元とノルム値に関して、“１つのノルム１１の場合における、１つの与えられた超曲面のベクトルの数”と、“このハイパーピラミッド（基数：cardinality）の上にあるラティスベクトルの全数”との比較を表している。
【００５２】
【表１】
0005584203.tif 000009
【００５３】
この文献によると、suffixeのインデキシングは、通常、２つの異なるやり方で行われている。
【００５４】
最初のアプローチは、超曲面上にあるベクトルの全数（cardinalite:基数）を考慮して、１つのインデックスを割り当てることである。第２のアプローチは、リーダーベクトルの概念を使って、ラティスの対称性を利用することである。ノルムlｐのエンベロープの(複数)リーダーは、ラティスの(複数)ベクトルに対応している。そのベクトルを基にして、前記の対応するエンベロープに存在する他の全てのラティスベクトルは、それら座標の置換（permutation）、符号変化により、得ることができる。これら２つのアプローチは、isotropicソースに対し、同様のレート−歪パフォーマスを示す。
【００５５】
しかしながら、ラティスのインデキシングについての多くの研究は、ラプラス分布又はガウス分布に対する解法を提案している。これら分布は、それぞれ、形状パラメータｐ＝１、ｐ＝２を持つGG(ｐ)の特別なケースである。ｐ＝0.5という特別なケースに対する解法を提案する研究者もいる。しかし、このカウント方法では、プロダクトコードを構成することはできず、実際には、インデキシングの方法も極めて複雑である。特に、高次元、大きいノルムをもつｐ≠0.5、１又は２の場合は複雑である。
【００５６】
本発明は、0＜p≦2を持つエンベロープＧＧ（ｐ）の上にあるラティスベクトルＺｎに対する新規な代替案を提案する。提案する解決法は、ベクトルに基礎を置いて、分割理論を使う。
【００５７】
分割理論（la theorie des partitions）を使うと、前記複雑性、必要な記憶容量の問題を解決でき、リーダーベクトルを生成し、ベクトルにインデックスを付与することができる。本発明は、変換テーブルを使うことなく、suffixeインデックスを、素早く割り当てることができる、経済的なインデキシングアルゴリズムを提案する。
【００５８】
以下の説明において、最初の章では、ＬＶＱの原則を説明してから、インデキシング問題について説明する。次の章では、形状パラメータｐがどのようなものであろうとも、インデキシングの例を以って、極めて大きいコードブックLVQにインデックスを付与するための効率的なやり方を提案する。続いて、提案されたアプローチの、メモリ、演算のコストについて説明する。更に、実効的な実データ インデキシングに対するパフォーマンス値について説明する。
【００５９】
ラティスベクトルのインデキシング
ラティスの定義
ＲｎにおけるラティスΛは、線形独立ベクトルａｉ（ラティスの基底）の集合の全部の組合せで、次のように構成される。
Λ = ｛x│x = u1a1 + u2a2 + … unan｝    （１）
【００６０】
【化８】
0005584203.tif 000010
【００６１】
１つのラティスの各ベクトルｖは、一定ノルムｌｐを持つベクトルを含む表面又は超平面に属していると見なすことができ、次式で与えられる。：
【００６２】
【数１】
0005584203.tif 000011
【００６３】
プロダクトコード（code produit）を使って、指定したラティスのベクトルをコード化することができる。ソースベクトルの分布がラプラシアン分布であるならば、適切なプロダクトコードは、“１つのベクトルのノルムｌ１に対応するprefixe”及び“問題とするノルムｌ１に等しい１つの半径を持つハイパーピラミッド上の位置に対応するsuffixe”から構成されていることは、明らかである。 一定のノルムｌ１の超曲面は、ハイパーピラミッドと呼ばれる。
１つの超曲面の上のベクトルの位置は、カウントアルゴリズム（algorithme de denombrement）を使って取得することができる。このようなプロダクトコードは、デコーディングの一意性（unicite）を保証する。
【００６４】
形状パラメータが１に等しい又は１より小さい、一般化ガウス分布を持つソースの場合、Ｄ４、Ｅ８上の立方体的ラティスＺｎ又はLeechラティスの優位性が証明されている[12]。従って、本書の残りの部分では、立方体的ラティスＺｎに基づく１つのＬＶＱの設計を中心に説明する。
【００６５】
全カウント数に基づくインデキシング 
ガウス分布又はラプラシアン分布について、及び、全カウントの原理に基づく種々のラティスについて、複数のカウント方法が、これまで提案されてきた。特に、ソースがラプラシアン分布の場合、ラティスＺｎに関して、ノルムｌ１のハイパーピラミッド上にあるラティスのベクトルの全数を計算するための再帰的公式（formule recursive）が知られている。
カウントのこの公式は、０と２の間の形状ファクタｐを使って、ソースの一般化ガウス分布に拡張されている。これら解法を使うと、tranctureノルムｌｐの内部に存在するベクトルの数を計算することができる。
しかしながら、これら解法は、インデックスをラティスＺｎに割り当てるアルゴリズムを提示するものではない。
また、この解法は、超曲面上にあるベクトルの数を決定するものではない。このため、プロダクトコードを使用することは困難である。
【００６６】
従来の研究の中で提案されているアルゴリズムは、０＜ｐ≦２に対するプロダクト コードスキームに基づいて、ベクトル（複数）にインデックスを付与するものである。それは、一般化シータ級数（series theta）に基づいて[４]、ラティス幾何学を使うものである。ｐ＝１または２については、この級数の展開は比較的に単純である。これに対し、ｐがそれ以外の値である場合、この級数は極めて複雑になる。クローズドフォーム（forme fermee）が生成されず、公式（mathematiques formelles）を使用することができないからである。提案された解法によれば、種々の次元及び高次元について、可能なノルム値を決定する必要があるが、一般的には、これを所定時間内に実行することはできない。
【００６７】
また、実施する際に、特に、高次元に対して（前記表を参照）、超曲面の基数（cardinalite)は、急速にnon-tractableな値（扱いにくい値）に達するので、エンベロープの基数に基づくインデキシング技術は、急速にコンピュータの計算精度（precision informatique）を越えてしまう。
【００６８】
ベクトル（リーダー）に基づくインデキシング 
リーダーに基づく方法は、ラティスの対称性を利用する。その方法は、一定ノルムのエンベロープに対する効率的なインデキシング アルゴリズムを使う。ラティスベクトルの全数に基づいてインデックスを割り当てるのではなく、リーダーと呼ばれる、少ない数のベクトルに基づいて割り当てるものである。
【００６９】
ラティスの対称性は、様々であるので、個別に処理される。対称性がない場合には、これは、全カウント法と比べると、より効率的なソースのインデキシング方法である。
また、コード化アルゴリズムにより管理されるインデックスは、エンベロープの基数よりもっと小さい。これを使うと、全カウントに基づく方法ではインデックスを付与できないベクトルに対して、バイナリ精度（precision binaire)で、インデックスを付与することができる。
【００７０】
プロダクトコードのアーキテクチャでは、ラティスの対称性を別にして、suffixeインデックスは、リーダーの数が少ないインデックスを含んでいる。前記suffixeインデックスに基づいて、超曲面の全ての他のベクトルを割り当てることができる。ラティスＺｎに関して、対称性は、２つの基本的な操作に対応している:即ち、ベクトル座標の“符号変化（changements de signe）”と“置換（permutation）”である。
第１の操作は、ベクトルが存在する一つの象限の変化に対応している。例えば、２次元のベクトル（７，−３）が第４象限にあるとする。これに対し、ベクトル（−７、−３）は第３象限にある。これらベクトルはｙ軸に対して対称である。
第２の操作は、象限内の対称性に対応する。例えば、ベクトル（−７、３）と（−３，７）は、２つ共に第２象限にあり、同象限の２等分線に対して、対称である。
この場合、“これらベクトルは、これらベクトルのリーダーであるベクトル（３，７）の置換及び符号変化から生成されること”が分かる。ベクトル（３，７）は、これらベクトルのリーダーベクトルである。全ての置換と符号変化を使って、リーダー（３，７）は８つのベクトルを代表することができる。
この比は、超曲面の次元と共に急速に大きくなる（表１参照）。
【００７１】
従って、このインデキシング方法は、超曲面上の全ベクトルに直接インデックスを付与する代わりに、各ベクトルに対し、３つのインデックスのセットを割り当てる：即ち、１つは、リーダーに対応するものであり、他の２つは、リーダーの置換および符号変化に対応するものである。置換と符号のインデックスの計算方法の詳細については、[５]を参照のこと。
【００７２】
提案するインデキシング方法 
ノルムｌ１の場合に提案するリーダーのインデックス付与方法。
原理 
本発明は、逆辞書順序で、全てのベクトルを分類する分類に基づく解決方法を提案する。また、インデックスを付与しなければならないリーダーに先行するベクトルの数に応じて、インデックスを割り当てる。この場合、インデキシングは、もはやリソースを大量消費する１つのサーチアルゴリズム、又は、直接アドレッシングによるものではなく、むしろ、低コストのカウントアルゴリズムによるものである。これは、それらに関する明らかな知識に依存するものではなく、むしろ、リーダーの量に依存するもので、このようにすれば、変換表を作成しなくてもよくなる。
【００７３】
半径rのハイパーピラミッドは、全てのベクトルv = (v1, v2, …, vd)から構成されている。但し、||ｖ||１＝ｒである。上述したように、リーダーは、超曲面の基本ベクトルである。置換と符号変化操作によって、そこから、同超曲面上にある他のベクトルを導き出す。確かに、リーダーは、（または降順）昇順でソートされる正の座標を持つベクトルである。したがって、ノルムｒ、次元dのベクトルは、次の条件を満足するベクトルである。：
【数２】
0005584203.tif 000012
【００７４】
分割理論との関係 
ノルムｌ1の場合、セクション3.1.1で説明した条件は数論の分割理論（theorie des partitions）に関連していることに注意しなければならない。確かに、数論では、正の整数rの分割は、正の整数の和（partとも呼ばれる）としてrを記述する方法である。ｒの別の分割数は、次の分割関数P（ｒ）で与えられる：
【数３】
0005584203.tif 000013
【００７５】
これは、級数ｑ[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]を使うことができる。この関数は、ｄ以下の部分(parts)を持つｒの分割数を計算するものである（分割理論において、これは、部分の数は問わないが、ｄより大きい要素を持たない、ｒの分割数を計算することと同じことである）。
したがって、ノルムｒ＝５と次元ｄ=３のハイパーピラミッドに対して、ｑ（５，３）＝５である。即ち、５つのリーダーは次のとおりである。：（0、0、5） （0、1、4）、（0、2、3）、（1、1、3）、（1、2、2）。
【００７８】
関数ｑ（ｒ、ｄ）は、次の漸化式から計算することができる。
ｑ(ｒ,ｄ) = ｑ(ｒ, ｄ−1) + ｑ(ｒ−ｄ, d)           (3)
但し、ｑ（ｒ、ｄ）＝Ｐ（ｒ）で、ｄ≧ｒ、ｑ（１、ｄ）＝１、及び、ｑ（ｒ、0）＝0。
【００７９】
３.１．３  関数q（r、d）を使用して、リーダーにインデックスを付与する
以下に説明するように、式（3）が与えられたハイパーピラミッドの上のリーダーの全数を与えるのみならず、同式は、変換テーブルを使うことなく、リーダーに対し唯一の一群のインデックスを割り当てるのに使うことができる。
インデックス アルゴリズムの原理を説明するために、次のようにハイパーピラミッドのリーダーが、次のように逆辞書式順序で分類されていると仮定する。
【００８０】
【表２】
0005584203.tif 000014
【００８１】
したがって、リーダーｌのインデックスは、これに先行するリーダーの数に対応している。上記例では、リーダー（0、...、1、1、ｒｎ−２）にはインデックス３が割り当てられる。
【００８２】
第１命題（proposition）では、リーダーのインデキシング アルゴリズムが記述されている。
【００８３】
第１命題
ｖ＝（ｖ1、ｖ2、…、ｖｎ）は、一定ノルムｌ1の１つのエンベロープ上の１つのリーダーベクトルｌ＝（ｘ１、ｘ２、…、ｘｎ）を持つラティスベクトルＺｎであるとする。リーダーのインデックスＩ１は次式で与えられる。：
【００８４】
【数４】
0005584203.tif 000015
【００８５】
【化９】
0005584203.tif 000016
【００８６】
証明。
【化１０】
0005584203.tif 000017
逆辞書式順序でリーダーをソートしているから、１より前の第１リーダー群は、ｎ番目の成分が、ｘｎより大きい全リーダー（即ち、ｘｎ＋１≦ｇｎ≦ｒｎを満たす最大座標ｇｎを持つ全リーダー）から構成されている。
【００８７】
それら全てをリスト化せずに、第１グループのリーダーの数をカウントするために、分割関数ｑ（ｒ、ｄ）が使われる。なぜなら、ｎ番目の座標がｇｎに等しいリーダーの数は、次の注（remarque）を使って簡単に計算することができるからである。
【００８８】
注（Remarque）：
ノルムｒｎ、次元ｎのリーダー（その最大座標がｇｎに等しい）の数の計算は、数rn-gn（但し、ｇｎより大きい部分がなく、ｎ−1部分より小さい）の分割数を、計算することに等しい。
【００８９】
ほとんどの場合、q(rn-gn,n-1)を適用して、分割数をカウントすることができる。しかし、このアプローチは、rn-gn<gnの場合しか正しくない。この場合、rn-gnの全ての分割はｇｎより大きい部分を持っていないと暗黙に仮定されている。しかしながら、一般的な場合、rn-gn<gnは保証されない場合（例えば、ノルムｒｎ＝２０、次元ｎ＝５、最大部分が７のベクトルの数は、ｑ（20-7、５-１）＝ｑ（13、4）を導く場合（但し20−7≪７ではない））、q(rn-gn, n-1)の計算は、真(valide)のベクトルの数について誤った値を算出する。rn-gn の複数の分割がgnより大きい部分を持つこともあるからである（この場合セクション３．１.１の条件２が満たされていない）。
【００９０】
【化１１】
0005584203.tif 000018
【００９１】
【化１２】
0005584203.tif 000019
よって、n＋１からｒnに至るｇｎの変化を使うと、最大座標がｘｎより大きいリーダー数を、次式から決定することができる。
【００９２】
【数５】
0005584203.tif 000020
【００９３】
【化１３】
0005584203.tif 000021
【００９４】
先行するリーダーベクトルｌの第２グループは、第ｎ番の座標がｘｎに等しい全ベクトルからなる。但し、第ｎ−１番の座標はｘｎ−１より大きいとする。リーダーベクトルのこの数をカウントするために、上記の注（remarque）を使うが、今回は、次元ｎ−１に応用する。
【化１４】
0005584203.tif 000022
関数minは、ノルムｒｎとオーダーｇｎ−１≦ｇｎ＝ｘｎが満足されることを保証する。
【００９５】
結果を追加次元（dimensions additionnelles）に拡張することにより、最大座標がｘｎに等しいベクトルであって、１に先行するベクトルの数は、次式で与えられる。
【００９６】
【数６】
0005584203.tif 000023
【００９７】
式（5）、（6）を組合せて、一般式を導き、ｌより前に位置するリーダーベクトルの全数を計算し、従って、ｌのインデックスＩＩを計算することができる（式（４））。
【００９８】
【数７】
0005584203.tif 000024
【００９９】
但し、ｊ＝０に対し、ｘｎ＋１＝＋∞
【０１００】
【化１５】
0005584203.tif 000025
【０１０１】
【化１６】
0005584203.tif 000026
【０１０２】
【化１７】
0005584203.tif 000027
【０１０３】
一つのベクトルのノルムｌｐは、精度δを持つことが知られており、次式で得られる。
【０１０４】
【数８】
0005584203.tif 000028
【０１０５】
【化１８】
0005584203.tif 000029
【０１０６】
【化１９】
0005584203.tif 000030
【０１０７】
【化２０】
0005584203.tif 000031
【０１０８】
第２命題：
ベクトルν = (v1, v2, …, vn)を、一定ノルムｌｐの一つのエンベロープの上にある１つのリーダーベクトルｌ= (x1, x2, …, xn)を持つ１つのラティスベクトルＺｎであるとする。リーダーベクトルＩ１のインデックスは次式により与えられる。
【０１０９】
【数９】
0005584203.tif 000032
【０１１０】
【化２１】
0005584203.tif 000033
【０１１１】
証明：
【化２２】
0005584203.tif 000034
【０１１２】
【化２３】
0005584203.tif 000035
【０１１３】
【化２４】
0005584203.tif 000036
【０１１４】
【化２５】
0005584203.tif 000037
【０１１５】
【化２６】
0005584203.tif 000038
【０１１６】
【数１０】
0005584203.tif 000039
【０１１７】
【化２７】
0005584203.tif 000040
【０１１８】
式（９）において、ｊを０からｎ−２に亘って変化させると、ｘｎからｘ２までの座標に対する先行するリーダーベクトルｌの数を正確にカウントすることができる。
【０１１９】
【数１１】
0005584203.tif 000041
【０１２０】
【化２９】
0005584203.tif 000042
【０１２１】
【化３０】
0005584203.tif 000043
【０１２２】
【化３１】
0005584203.tif 000044
【０１２３】
【化３２】
0005584203.tif 000045
【０１２４】
【化３３】
0005584203.tif 000046
セクション3.1で導入した原則を使うと、これは、次のように分割Ｎｐの数を計算することと同じである：
【０１２５】
【数１２】
0005584203.tif 000047
【０１２６】
そして、ｉ（Np > I1）の最初の値をｘｎに割り当てる。次のステップで、xn-1をデコードする。
【０１２７】
【化３４】
0005584203.tif 000048
次に、Xn-1をデコードするために、式（11）のメカニズムに類似したメカニズムを使ってＮｐをカウントする。しかし、今回は、（ｎ−１）番目の座標に関係して行う。
【０１２８】
この場合、Np > I1であるから、最初に、分割カウンタＮｐの値を最初のリーダーベクトル（ｘｎに等しい第ｎ成分を持つ）に戻して、パラメータＮｐを先行する値にしなければならない。以後、これをNpbckpと呼ぶことにする（“先行する値”とは、Np < I1で、Ｎｐの中で一番大きい値に対応する。即ち、ｉの最後の値が和に含まれる前のＮｐの値である）。
【化３５】
0005584203.tif 000049
【０１２９】
このプロセスは、次元について、次式で一般化される。
【０１３０】
【数１３】
0005584203.tif 000050
【０１３１】
【化３６】
0005584203.tif 000051
【０１３２】
【化３７】
0005584203.tif 000052
ただし、前記２つともに、厳密に同一の計算結果であることが前提である。
【０１３３】
【化３８】
0005584203.tif 000053
次のセクションでは、リーダーベクトルのコーディング、デコーディングの例を説明する。
【０１３４】
コーディングとデコーディングの例 
v = (-20, 16, 15, -40) を、インデキシングしなければならない形状ファクターｐ＝0.3の、一般化ガウス分布を持つ一つのソースの量子化された１つのラティスベクトルとする。置換と符号のインデックスの計算は、この研究の範囲内ではないので、また、[5,13]を使いながら簡単に実行することができるので、ここでは、リーダーベクトルのインデキシングを中心に説明する。ベクトルｖに対応するリーダーベクトルは、l = (15, 16, 20, 40)である。
コーディングとデコーディングのアルゴリズムは、以下の原則に基づく。
【０１３５】
コーディング ステップ：
１）初期設定
ｐ＝0.3、精度δ＝0.1とする。リーダーベクトルのインデックスをＩ1＝０とする。
２）次式のように、精度δを持つベクトルｌのノルムｌｐを計算する。
【０１３６】
【数１４】
0005584203.tif 000054
３）これら演算を実行する。
最初にｆ（101）を決める。この場合、ｆ（101）＝2264である。次に、ｊ＝0に対して式（８）を使う。但し、ｉは４１（即ち、40+1）から2264（即ち、min（＋∞、2264）。次式が得られる。
【０１３７】
【数１５】
0005584203.tif 000055
【０１３８】
４）  先行するリーダーベクトルｌの先行する数を計算する。但し、最大成分ｇ４が40であるとする。このことは、３部分の総和を、次のように計算することを意味する。
【０１３９】
【数１６】
0005584203.tif 000056
【０１４０】
f(71) = 704, j = 1、 iは21から40 (即ち、 min(40, 704))まで変化する)として、式（８）を使うと、次式を得る。
【０１４１】
【数１７】
0005584203.tif 000057
【０１４２】
５）先行するベクトルｌの数を計算する。但し、最大成分ｇ４が40、ｇ３が20であるとする。この場合、２部分において、和を次式で計算しなければならない。
【０１４３】
【数１８】
0005584203.tif 000058
【０１４４】
f(46) = 167, j = 2 、 iは、17 乃至 20 (即ち min(20, 167))まで変化するとして、式（８）を使うと、次式を得る。
【０１４５】
【数１９】
0005584203.tif 000059
【０１４６】
６）最後のステップにおいて、次の式を計算してI１をアップデートする。
I1 = 100774 + (min(f(x)), x2)− xl)
= 100774 + (min(f(23), 16)−15)
= 100774 + (min(17, 16) −15)
= 100775.
【０１４７】
従って、p = 0.3 、δ = 0.1のときのリーダーベクトルl = (15, 16, 20, 40)のインデックスは、 I1 = 100775である。付属資料におけるアルゴリズムｌは、全てのコーディングプロセスをコンパイルしたものである。
【０１４８】
【化３９】
0005584203.tif 000060
２）f(101) ＝ 2264を計算する。
３）ｘ４をデコードする。この場合、ｊ＝０として式(12)を使って、次式を得る。
【０１４９】
【数２０】
0005584203.tif 000061
【０１５０】
【化４０】
0005584203.tif 000062
【０１５１】
【化４１】
0005584203.tif 000063
【０１５２】
【数２１】
0005584203.tif 000064
【０１５３】
【化４２】
0005584203.tif 000065
【０１５４】
【化４３】
0005584203.tif 000066
【０１５５】
【数２２】
0005584203.tif 000067
【０１５６】
【化４４】
0005584203.tif 000068
【０１５７】
【化４５】
0005584203.tif 000069
= min(f(23), 16) −(100775 −100774)
= min(17, 16) − (100775 − 100774)
= 15.
【０１５８】
従って、1 = (15, 16, 20, 40)が得られる。付属資料のアルゴリズム２はデコーディングプロセス全体をコンパイルしたものである。
【０１５９】
メモリコスト及び演算コスト
必要なメモリ容量
【化４６】
0005584203.tif 000070
【０１６０】
【化４７】
0005584203.tif 000071
【０１６１】
【化４８】
0005584203.tif 000072
【０１６２】
【化４９】
0005584203.tif 000073
したがって、コーディング/デコーディングのステップのためのメモリコストの上限は次式で与えられる：
【０１６３】
【数２３】
0005584203.tif 000074
【０１６４】
メモリ容量は、主として、エンベロープのノルムと次元に依存していることに留意すべきである。ベクトルの数がＢの選択を決定する。
【０１６５】
【化５０】
0005584203.tif 000075
必要なメモリ容量は、ｐ＝１、δ＝１，Ｂ＝４（整数タイプのデータ）として、半径ｒに応じて、式（13）に基づいて表わされ、[５]で説明したように、ベクトルに基づく従来の方法のメモリの上限と比較される。１つの次元と１つの半径がそれぞれ16,20程度に小さい場合、従来の方法では、10ギガバイト以上のメモリは必要としていなかった。これに対し、本発明で提案する方法では、必要な容量は100キロバイト以下である。
【０１６６】
必要とするメモリ容量が非常に低いこと及び全てのベクトルを知る必要がないという事実があるので、64, 128, 256, 512のように大きい次元のラティスベクトルに対しても、インデキシングすることができる。従前の研究においては、実際のアプリケーションでは、次元が１６に制限されていた。
【０１６７】
【化５１】
0005584203.tif 000076
【０１６８】
【化５２】
0005584203.tif 000077
式（8）とアルゴリズム（1）及び（2）（付属資料、参照）に基づくと、必要な操作は、加算／減算（A）及び比較論理演算（LC）であることが推測される。メモリアクセスは無視する。前記２タイプの演算よりも、かなりコストが低いからである。
【０１６９】
次に、本発明のインデキシング アルゴリズムのコーディング/デコーディング コストについて評価する。デコーディング アルゴリズム２は、コーディングアルゴリズムの逆であって、ほぼ同一の演算数となる。コーディング/デコーディングアルゴリズムの複雑性は、アルゴリズム１の演算回数を次のようにカウントすることにより評価される。
【０１７０】
１）（ｎ−１）Ａを実行した総和
２）“if/break”テストのために、最初の《for》（《ｊ》 の上の）が、約nnz(1)回実行される。但し、nnz(1)は、１の非０の値の数を意味する。
３）最初の《for》の各ループに対して、次のものを有している。
i. 最初の《if》のために、IＡおよび7ＬＣ 。
ii．関数《min》のために、１LC。
【化５３】
0005584203.tif 000078
4）最後の"if"と続く行を使って，２Ａと２ＬＣを計算する。
【０１７１】
したがって、加算、論理演算、比較に関する、コーディング/デコーディングのアルゴリズムの総コストは、次の式により与えられる。
【０１７２】
【数２４】
0005584203.tif 000079
【０１７３】
【化５４】
0005584203.tif 000080
【０１７４】
本発明によれば、ラティスベクトルのインデキシングは、対応するレーダーベクトルのインデキシング、置換及び符号変化になる。本発明は、如何なる変換テーブルを必要とすることなくベクトルをインデキシングし、メモリの使用及び全ベクトルの生成の複雑さを低減する方法を提案する。
また、この解決法は、形状パラメータ0＜ p≦ 2を持つ一般化ガウス分布ソースに対して役立つ。本発明の方法は、分析的で、本方法を使うと、高次ベクトル次元の使用を可能にする。
【０１７５】
【表３】
0005584203.tif 000081
【０１７６】
【表４】
0005584203.tif 000082
【図１】
0005584203.tif 000089
【図２】
0005584203.tif 000090
【図３】
0005584203.tif 000091