数値データの処理方法
本発明は、ｄ次元空間において、少なくともベクトル（複数）の一部分１に対し、少なくとも一つのベクトルインデックスI１（英語でリーダーという）を計算するための量子化ステップを有するデジタルデータ処理方法に関する。前記ベクトル（複数）１は、入力データの記述子を構成し、前記方法は、前記リーダーベクトルインデックスI１が、リーダーベクトル全体の決定ステップをもつことなく、逆辞書順序で、前記リーダーベクトル１に先行するベクトルの数に対応することを特徴とする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータの圧縮、検索、比較又は解凍などのアプリケーションのためのデジタルデータ処理の技術分野に関する。本発明は、オーディオビジュアルデータの処理、より一般的には、全てのタイプのデジタルデータの処理に関する。本発明の目的は、処理時間を削減し、コンピューティングパワー、メモリの容量に関する情報処理リソースの必要性を削減することである。
【背景技術】
【０００２】
アプリケーションは、全てではないが、表示に大量のデータを必要とする画像処理に関係する。記憶に必要なサイズと伝送時間を削減するためには、ビデオ情報を抽出処理し、コード化して、情報圧縮を行う。このコード化された情報は、コード化のパフォーマンスに有害なリダンダンシーを避け、周波数と空間に関して、最適な再構成可能な状態にする必要がある。そのために、ウェーブレット変換技術が知られている。その座標は、ベクトルラティスを構成するもので、ベクトル量子化が行われる。
【０００３】
ベクトル量子化（ＶＱ）の原理は、各サンプルを個別にコード化する代わりに、ベクトルを形成するサンプルのシーケンスをコード化することである。コード化は、ベクトルによりシーケンスを近似することによって行われる。通常"コードブック"と呼ばれるカタログに属するベクトルを使ってコード化する。コードブックの各ベクトルには、インデックスが付けられる。コード化する時に、それを表わすために使用するのは、コード化するサンプルシーケンスに最も近いベクトルのインデックスである。
【０００４】
公知の解決法では、各ベクトルを決定すること、それをメモリに記憶させること、更に、ベクトル全体に対し処理することが、必要である。ベクトルの基底(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が、逆辞書順序で、前記リーダーベクトル１に先行するベクトルの数に対応することを特徴とする。
【００２５】
前記処理方法は、計算において、リーダーベクトル以外の、どのようなリーダーベクトルを決定するステップを含まないことが好ましい。
【００２６】
【化１】
【００２７】
【化２】
【００２８】
【化３】
【００２９】
別の変形例では、リーダーベクトルインデックスＩ１を算出するステップは、“前記リーダーベクトル１(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)を算出することを特徴としている。また、全リーダーベクトルを決定するステップなしに、逆辞書順序で、前記リーダーベクトル１に先行するベクトルの数に対応するインデックスＩ１を持つリーダーベクトル１をサーチする処理に、一つのインデックスＩ１を付加することを特徴としている。
【００３６】
【化４】
この加算は、和が前記インデックスＩ１より大きくなるまで行われる。前記サーチされた座標xiは、前記インデックスＩ１を超過するものであり、前記方法では、座標Xi-1に対して、値Ｉ１から加算が継続される。但し、Ｉ１は、前記インデックスを超過する前の、値Ｉ１に先行する値である。
【００３７】
【化５】
また、前記関数F(A)を適用して、カウントステップの結果の加算が行われる。この加算は、和が前記インデックスＩ１より大きくなるまで行われる。前記サーチされた座標xiは、前記インデックスＩ１を超過するものであり、前記方法では、座標Xi+1に対して、値Ｉ１から加算が継続される。但し、Ｉ１は、前記インデックスを超過する前の、値Ｉ１に先行する値である。
【００３８】
【化６】
再構成するためには、昇順にソートする場合、座標xdに対して、及び、降順にソートする場合、座標xｌに対して、I1' = 0とする。
【図面の簡単な説明】
【００３９】
本発明は、図面を参照し、非制限的な実施例を読むことにより、よりよく理解されるであろう。
【図１】本発明に基づくデータ処理システムの基本を示す図である。
【図２】
【化７】
【図３】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）の上にあるラティスベクトルの全数”との比較を表している。
【００５２】
【表１】
【００５３】
この文献によると、suffixeのインデキシングは、通常、２つの異なるやり方で行われている。
【００５４】
最初のアプローチは、超曲面上にあるベクトルの全数（cardinalite:基数）を考慮して、１つのインデックスを割り当てることである。第２のアプローチは、リーダーベクトルの概念を使って、ラティスの対称性を利用することである。ノルムlｐのエンベロープの(複数)リーダーは、ラティスの(複数)ベクトルに対応している。そのベクトルを基にして、前記の対応するエンベロープに存在する他の全てのラティスベクトルは、それら座標の置換（permutation）、符号変化により、得ることができる。これら２つのアプローチは、isotropicソースに対し、同様のレート−歪パフォーマスを示す。
【００５５】
しかしながら、ラティスのインデキシングについての多くの研究は、ラプラス分布又はガウス分布に対する解法を提案している。これら分布は、それぞれ、形状パラメータｐ＝１、ｐ＝２を持つGG(ｐ)の特別なケースである。ｐ＝0.5という特別なケースに対する解法を提案する研究者もいる。しかし、このカウント方法では、プロダクトコードを構成することはできず、実際には、インデキシングの方法も極めて複雑である。特に、高次元、大きいノルムをもつｐ≠0.5、１又は２の場合は複雑である。
【００５６】
本発明は、0＜p≦2を持つエンベロープＧＧ（ｐ）の上にあるラティスベクトルＺｎに対する新規な代替案を提案する。提案する解決法は、ベクトルに基礎を置いて、分割理論を使う。
【００５７】
分割理論（la theorie des partitions）を使うと、前記複雑性、必要な記憶容量の問題を解決でき、リーダーベクトルを生成し、ベクトルにインデックスを付与することができる。本発明は、変換テーブルを使うことなく、suffixeインデックスを、素早く割り当てることができる、経済的なインデキシングアルゴリズムを提案する。
【００５８】
以下の説明において、最初の章では、ＬＶＱの原則を説明してから、インデキシング問題について説明する。次の章では、形状パラメータｐがどのようなものであろうとも、インデキシングの例を以って、極めて大きいコードブックLVQにインデックスを付与するための効率的なやり方を提案する。続いて、提案されたアプローチの、メモリ、演算のコストについて説明する。更に、実効的な実データ インデキシングに対するパフォーマンス値について説明する。
【００５９】
ラティスベクトルのインデキシング
ラティスの定義
ＲｎにおけるラティスΛは、線形独立ベクトルａｉ（ラティスの基底）の集合の全部の組合せで、次のように構成される。
Λ = ｛x│x = u1a1 + u2a2 + … unan｝ （１）
【００６０】
【化８】
【００６１】
１つのラティスの各ベクトルｖは、一定ノルムｌｐを持つベクトルを含む表面又は超平面に属していると見なすことができ、次式で与えられる。：
【００６２】
【数１】
【００６３】
プロダクトコード（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のベクトルは、次の条件を満足するベクトルである。：
【数２】
【００７４】
分割理論との関係
ノルムｌ1の場合、セクション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の２つの要件を満たすノルムｒ＝５とｄ＝５のハイパーピラミッドにおける唯一のベクトル（複数）である。
【００７７】
しかし、ｄ次元のラティスにおいて、ｒに等しいノルム11のエンベロープは重要である。但し、ｒ≠ｄとする。この場合、関数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）が与えられたハイパーピラミッドの上のリーダーの全数を与えるのみならず、同式は、変換テーブルを使うことなく、リーダーに対し唯一の一群のインデックスを割り当てるのに使うことができる。
インデックス アルゴリズムの原理を説明するために、次のようにハイパーピラミッドのリーダーが、次のように逆辞書式順序で分類されていると仮定する。
【００８０】
【表２】
【００８１】
したがって、リーダー1のインデックスは、これに先行するリーダーの数に対応している。上記例では、リーダー（0、...、1、1、ｒｎ−２）にはインデックス３が割り当てられる。
【００８２】
第１命題（proposition）では、リーダーのインデキシング アルゴリズムが記述されている。
【００８３】
第１命題
ｖ＝（ｖ1、ｖ2、…、ｖｎ）は、一定ノルムｌ1の１つのエンベロープ上の１つのリーダーベクトルｌ＝（ｘ１、ｘ２、…、ｘｎ）を持つラティスベクトルＺｎであるとする。リーダーのインデックスＩ１は次式で与えられる。：
【００８４】
【数４】
【００８５】
【化９】
【００８６】
証明。
【化１０】
逆辞書式順序でリーダーをソートしているから、１より前の第１リーダー群は、ｎ番目の成分が、ｘｎより大きい全リーダー（即ち、ｘｎ＋１≦ｇｎ≦ｒｎを満たす最大座標ｇｎを持つ全リーダー）から構成されている。
【００８７】
それら全てをリスト化せずに、第１グループのリーダーの数をカウントするために、分割関数ｑ（ｒ、ｄ）が使われる。なぜなら、ｎ番目の座標がｇｎに等しいリーダーの数は、次の注（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より大きい部分を持つこともあるからである（この場合セクション３．１.１の条件２が満たされていない）。
【００９０】
【化１１】
【００９１】
【化１２】
よって、n＋１からｒnに至るｇｎの変化を使うと、最大座標がｘｎより大きいリーダー数を、次式から決定することができる。
【００９２】
【数５】
【００９３】
【化１３】
【００９４】
先行するリーダーベクトルｌの第２グループは、第ｎ番の座標がｘｎに等しい全ベクトルからなる。但し、第ｎ−１番の座標はｘｎ−１より大きいとする。リーダーベクトルのこの数をカウントするために、上記の注（remarque）を使うが、今回は、次元ｎ−１に応用する。
【化１４】
関数minは、ノルムｒｎとオーダーｇｎ−１≦ｇｎ＝ｘｎが満足されることを保証する。
【００９５】
結果を追加次元（dimensions additionnelles）に拡張することにより、最大座標がｘｎに等しいベクトルであって、１に先行するベクトルの数は、次式で与えられる。
【００９６】
【数６】
【００９７】
式（5）、（6）を組合せて、一般式を導き、１より前に位置するリーダーベクトルの全数を計算し、従って、１のインデックスＩＩを計算することができる（式（４））。
【００９８】
【数７】
【００９９】
但し、ｊ＝０に対し、ｘｎ＋１＝＋∞
【０１００】
【化１５】
【０１０１】
【化１６】
【０１０２】
【化１７】
【０１０３】
一つのベクトルのノルムｌｐは、精度δを持つことが知られており、次式で得られる。
【０１０４】
【数８】
【０１０５】
【化１８】
【０１０６】
【化１９】
【０１０７】
【化２０】
【０１０８】
第２命題：
ベクトルν = (v1, v2, …, vn)を、一定ノルムｌｐの一つのエンベロープの上にある１つのリーダーベクトル1 = (x1, x2, …, xn)を持つ１つのラティスベクトルＺｎであるとする。リーダーベクトルＩ１のインデックスは次式により与えられる。
【０１０９】
【数９】
【０１１０】
【化２１】
【０１１１】
証明：
【化２２】
【０１１２】
【化２３】
【０１１３】
【化２４】
【０１１４】
【化２５】
【０１１５】
【化２６】
【０１１６】
【数１０】
【０１１７】
【化２７】
【０１１８】
式（９）において、ｊを０からｎ−２に亘って変化させると、ｘｎからｘ２までの座標に対する先行するリーダーベクトル１の数を正確にカウントすることができる。
【化２８】
【０１１９】
【数１１】
【０１２０】
【化２９】
【０１２１】
【化３０】
【０１２２】
【化３１】
【０１２３】
【化３２】
【０１２４】
【化３３】
セクション3.1で導入した原則を使うと、これは、次のように分割Ｎｐの数を計算することと同じである：
【０１２５】
【数１２】
【０１２６】
そして、ｉ（Np > I1）の最初の値をｘｎに割り当てる。次のステップで、xn-1をデコードする。
【０１２７】
【化３４】
次に、Xn-1をデコードするために、式（11）のメカニズムに類似したメカニズムを使ってＮｐをカウントする。しかし、今回は、（ｎ−１）番目の座標に関係して行う。
【０１２８】
この場合、Np > I1であるから、最初に、分割カウンタＮｐの値を最初のリーダーベクトル（ｘｎに等しい第ｎ成分を持つ）に戻して、パラメータＮｐを先行する値にしなければならない。以後、これをNpbckpと呼ぶことにする（“先行する値”とは、Np < I1で、Ｎｐの中で一番大きい値に対応する。即ち、ｉの最後の値が和に含まれる前のＮｐの値である）。
【化３５】
【０１２９】
このプロセスは、次元について、次式で一般化される。
【０１３０】
【数１３】
【０１３１】
【化３６】
【０１３２】
【化３７】
ただし、前記２つともに、厳密に同一の計算結果であることが前提である。
【０１３３】
【化３８】
次のセクションでは、リーダーベクトルのコーディング、デコーディングの例を説明する。
【０１３４】
コーディングとデコーディングの例
v = (-20, 16, 15, -40) を、インデキシングしなければならない形状ファクターｐ＝0.3の、一般化ガウス分布を持つ一つのソースの量子化された１つのラティスベクトルとする。置換と符号のインデックスの計算は、この研究の範囲内ではないので、また、[5,13]を使いながら簡単に実行することができるので、ここでは、リーダーベクトルのインデキシングを中心に説明する。ベクトルｖに対応するリーダーベクトルは、l = (15, 16, 20, 40)である。
コーディングとデコーディングのアルゴリズムは、以下の原則に基づく。
【０１３５】
コーディング ステップ：
１）初期設定
ｐ＝0.3、精度δ＝0.1とする。リーダーベクトルのインデックスをＩ1＝０とする。
２）次式のように、精度δを持つベクトルｌのノルムｌｐを計算する。
【０１３６】
【数１４】
３）これら演算を実行する。
最初にｆ（101）を決める。この場合、ｆ（101）＝2264である。次に、ｊ＝0に対して式（８）を使う。但し、ｉは４１（即ち、40+1）から2264（即ち、min（＋∞、2264）。次式が得られる。
【０１３７】
【数１５】
【０１３８】
４） 先行するリーダーベクトルｌの先行する数を計算する。但し、最大成分ｇ４が40であるとする。このことは、３部分の総和を、次のように計算することを意味する。
【０１３９】
【数１６】
【０１４０】
f(71) = 704, j = 1、 iは21から40 (即ち、 min(40, 704))まで変化する)として、式（８）を使うと、次式を得る。
【０１４１】
【数１７】
【０１４２】
５）先行するベクトルｌの数を計算する。但し、最大成分ｇ４が40、ｇ３が20であるとする。この場合、２部分において、和を次式で計算しなければならない。
【０１４３】
【数１８】
【０１４４】
f(46) = 167, j = 2 、 iは、17 乃至 20 (即ち min(20, 167))まで変化するとして、式（８）を使うと、次式を得る。
【０１４５】
【数１９】
【０１４６】
６）最後のステップにおいて、次の式を計算して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である。付属資料におけるアルゴリズムｌは、全てのコーディングプロセスをコンパイルしたものである。
【０１４８】
【化３９】
２）f(101) ＝ 2264を計算する。
３）ｘ４をデコードする。この場合、ｊ＝０として式(12)を使って、次式を得る。
【０１４９】
【数２０】
【０１５０】
【化４０】
【０１５１】
【化４１】
【０１５２】
【数２１】
【０１５３】
【化４２】
【０１５４】
【化４３】
【０１５５】
【数２２】
【０１５６】
【化４４】
【０１５７】
【化４５】
= min(f(23), 16) −(100775 −100774)
= min(17, 16) − (100775 − 100774)
= 15.
【０１５８】
従って、1 = (15, 16, 20, 40)が得られる。付属資料のアルゴリズム２はデコーディングプロセス全体をコンパイルしたものである。
【０１５９】
メモリコスト及び演算コスト
必要なメモリ容量
【化４６】
【０１６０】
【化４７】
【０１６１】
【化４８】
【０１６２】
【化４９】
したがって、コーディング/デコーディングのステップのためのメモリコストの上限は次式で与えられる：
【０１６３】
【数２３】
【０１６４】
メモリ容量は、主として、エンベロープのノルムと次元に依存していることに留意すべきである。ベクトルの数がＢの選択を決定する。
【０１６５】
【化５０】
必要なメモリ容量は、ｐ＝１、δ＝１，Ｂ＝４（整数タイプのデータ）として、半径ｒに応じて、式（13）に基づいて表わされ、[５]で説明したように、ベクトルに基づく従来の方法のメモリの上限と比較される。１つの次元と１つの半径がそれぞれ16,20程度に小さい場合、従来の方法では、10ギガバイト以上のメモリは必要としていなかった。これに対し、本発明で提案する方法では、必要な容量は100キロバイト以下である。
【０１６６】
必要とするメモリ容量が非常に低いこと及び全てのベクトルを知る必要がないという事実があるので、64, 128, 256, 512のように大きい次元のラティスベクトルに対しても、インデキシングすることができる。従前の研究においては、実際のアプリケーションでは、次元が１６に制限されていた。
【０１６７】
【化５１】
【０１６８】
【化５２】
式（8）とアルゴリズム（1）及び（2）（付属資料、参照）に基づくと、必要な操作は、加算／減算（A）及び比較論理演算（LC）であることが推測される。メモリアクセスは無視する。前記２タイプの演算よりも、かなりコストが低いからである。
【０１６９】
次に、本発明のインデキシング アルゴリズムのコーディング/デコーディング コストについて評価する。デコーディング アルゴリズム２は、コーディングアルゴリズムの逆であって、ほぼ同一の演算数となる。コーディング/デコーディングアルゴリズムの複雑性は、アルゴリズム１の演算回数を次のようにカウントすることにより評価される。
【０１７０】
１）（ｎ−１）Ａを実行した総和
２）“if/break”テストのために、最初の《for》（《ｊ》 の上の）が、約nnz(1)回実行される。但し、nnz(1)は、１の非０の値の数を意味する。
３）最初の《for》の各ループに対して、次のものを有している。
i. 最初の《if》のために、IＡおよび7ＬＣ 。
ii．関数《min》のために、１LC。
【化５３】
4）最後の"if"と続く行を使って，２Ａと２ＬＣを計算する。
【０１７１】
したがって、加算、論理演算、比較に関する、コーディング/デコーディングのアルゴリズムの総コストは、次の式により与えられる。
【０１７２】
【数２４】
【０１７３】
【化５４】
【０１７４】
本発明によれば、ラティスベクトルのインデキシングは、対応するレーダーベクトルのインデキシング、置換及び符号変化になる。本発明は、如何なる変換テーブルを必要とすることなくベクトルをインデキシングし、メモリの使用及び全ベクトルの生成の複雑さを低減する方法を提案する。
また、この解決法は、形状パラメータ0＜ p≦ 2を持つ一般化ガウス分布ソースに対して役立つ。本発明の方法は、分析的で、本方法を使うと、高次ベクトル次元の使用を可能にする。
【０１７５】
【表３】
【０１７６】
【表４】
【技術分野】
【０００１】
本発明は、デジタルデータの圧縮、検索、比較又は解凍などのアプリケーションのためのデジタルデータ処理の技術分野に関する。本発明は、オーディオビジュアルデータの処理、より一般的には、全てのタイプのデジタルデータの処理に関する。本発明の目的は、処理時間を削減し、コンピューティングパワー、メモリの容量に関する情報処理リソースの必要性を削減することである。
【背景技術】
【０００２】
アプリケーションは、全てではないが、表示に大量のデータを必要とする画像処理に関係する。記憶に必要なサイズと伝送時間を削減するためには、ビデオ情報を抽出処理し、コード化して、情報圧縮を行う。このコード化された情報は、コード化のパフォーマンスに有害なリダンダンシーを避け、周波数と空間に関して、最適な再構成可能な状態にする必要がある。そのために、ウェーブレット変換技術が知られている。その座標は、ベクトルラティスを構成するもので、ベクトル量子化が行われる。
【０００３】
ベクトル量子化（ＶＱ）の原理は、各サンプルを個別にコード化する代わりに、ベクトルを形成するサンプルのシーケンスをコード化することである。コード化は、ベクトルによりシーケンスを近似することによって行われる。通常"コードブック"と呼ばれるカタログに属するベクトルを使ってコード化する。コードブックの各ベクトルには、インデックスが付けられる。コード化する時に、それを表わすために使用するのは、コード化するサンプルシーケンスに最も近いベクトルのインデックスである。
【０００４】
公知の解決法では、各ベクトルを決定すること、それをメモリに記憶させること、更に、ベクトル全体に対し処理することが、必要である。ベクトルの基底(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が、逆辞書順序で、前記リーダーベクトル１に先行するベクトルの数に対応することを特徴とする。
【００２５】
前記処理方法は、計算において、リーダーベクトル以外の、どのようなリーダーベクトルを決定するステップを含まないことが好ましい。
【００２６】
【化１】
【００２７】
【化２】
【００２８】
【化３】
【００２９】
別の変形例では、リーダーベクトルインデックスＩ１を算出するステップは、“前記リーダーベクトル１(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)を算出することを特徴としている。また、全リーダーベクトルを決定するステップなしに、逆辞書順序で、前記リーダーベクトル１に先行するベクトルの数に対応するインデックスＩ１を持つリーダーベクトル１をサーチする処理に、一つのインデックスＩ１を付加することを特徴としている。
【００３６】
【化４】
この加算は、和が前記インデックスＩ１より大きくなるまで行われる。前記サーチされた座標xiは、前記インデックスＩ１を超過するものであり、前記方法では、座標Xi-1に対して、値Ｉ１から加算が継続される。但し、Ｉ１は、前記インデックスを超過する前の、値Ｉ１に先行する値である。
【００３７】
【化５】
また、前記関数F(A)を適用して、カウントステップの結果の加算が行われる。この加算は、和が前記インデックスＩ１より大きくなるまで行われる。前記サーチされた座標xiは、前記インデックスＩ１を超過するものであり、前記方法では、座標Xi+1に対して、値Ｉ１から加算が継続される。但し、Ｉ１は、前記インデックスを超過する前の、値Ｉ１に先行する値である。
【００３８】
【化６】
再構成するためには、昇順にソートする場合、座標xdに対して、及び、降順にソートする場合、座標xｌに対して、I1' = 0とする。
【図面の簡単な説明】
【００３９】
本発明は、図面を参照し、非制限的な実施例を読むことにより、よりよく理解されるであろう。
【図１】本発明に基づくデータ処理システムの基本を示す図である。
【図２】
【化７】
【図３】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）の上にあるラティスベクトルの全数”との比較を表している。
【００５２】
【表１】
【００５３】
この文献によると、suffixeのインデキシングは、通常、２つの異なるやり方で行われている。
【００５４】
最初のアプローチは、超曲面上にあるベクトルの全数（cardinalite:基数）を考慮して、１つのインデックスを割り当てることである。第２のアプローチは、リーダーベクトルの概念を使って、ラティスの対称性を利用することである。ノルムlｐのエンベロープの(複数)リーダーは、ラティスの(複数)ベクトルに対応している。そのベクトルを基にして、前記の対応するエンベロープに存在する他の全てのラティスベクトルは、それら座標の置換（permutation）、符号変化により、得ることができる。これら２つのアプローチは、isotropicソースに対し、同様のレート−歪パフォーマスを示す。
【００５５】
しかしながら、ラティスのインデキシングについての多くの研究は、ラプラス分布又はガウス分布に対する解法を提案している。これら分布は、それぞれ、形状パラメータｐ＝１、ｐ＝２を持つGG(ｐ)の特別なケースである。ｐ＝0.5という特別なケースに対する解法を提案する研究者もいる。しかし、このカウント方法では、プロダクトコードを構成することはできず、実際には、インデキシングの方法も極めて複雑である。特に、高次元、大きいノルムをもつｐ≠0.5、１又は２の場合は複雑である。
【００５６】
本発明は、0＜p≦2を持つエンベロープＧＧ（ｐ）の上にあるラティスベクトルＺｎに対する新規な代替案を提案する。提案する解決法は、ベクトルに基礎を置いて、分割理論を使う。
【００５７】
分割理論（la theorie des partitions）を使うと、前記複雑性、必要な記憶容量の問題を解決でき、リーダーベクトルを生成し、ベクトルにインデックスを付与することができる。本発明は、変換テーブルを使うことなく、suffixeインデックスを、素早く割り当てることができる、経済的なインデキシングアルゴリズムを提案する。
【００５８】
以下の説明において、最初の章では、ＬＶＱの原則を説明してから、インデキシング問題について説明する。次の章では、形状パラメータｐがどのようなものであろうとも、インデキシングの例を以って、極めて大きいコードブックLVQにインデックスを付与するための効率的なやり方を提案する。続いて、提案されたアプローチの、メモリ、演算のコストについて説明する。更に、実効的な実データ インデキシングに対するパフォーマンス値について説明する。
【００５９】
ラティスベクトルのインデキシング
ラティスの定義
ＲｎにおけるラティスΛは、線形独立ベクトルａｉ（ラティスの基底）の集合の全部の組合せで、次のように構成される。
Λ = ｛x│x = u1a1 + u2a2 + … unan｝ （１）
【００６０】
【化８】
【００６１】
１つのラティスの各ベクトルｖは、一定ノルムｌｐを持つベクトルを含む表面又は超平面に属していると見なすことができ、次式で与えられる。：
【００６２】
【数１】
【００６３】
プロダクトコード（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のベクトルは、次の条件を満足するベクトルである。：
【数２】
【００７４】
分割理論との関係
ノルムｌ1の場合、セクション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の２つの要件を満たすノルムｒ＝５とｄ＝５のハイパーピラミッドにおける唯一のベクトル（複数）である。
【００７７】
しかし、ｄ次元のラティスにおいて、ｒに等しいノルム11のエンベロープは重要である。但し、ｒ≠ｄとする。この場合、関数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）が与えられたハイパーピラミッドの上のリーダーの全数を与えるのみならず、同式は、変換テーブルを使うことなく、リーダーに対し唯一の一群のインデックスを割り当てるのに使うことができる。
インデックス アルゴリズムの原理を説明するために、次のようにハイパーピラミッドのリーダーが、次のように逆辞書式順序で分類されていると仮定する。
【００８０】
【表２】
【００８１】
したがって、リーダー1のインデックスは、これに先行するリーダーの数に対応している。上記例では、リーダー（0、...、1、1、ｒｎ−２）にはインデックス３が割り当てられる。
【００８２】
第１命題（proposition）では、リーダーのインデキシング アルゴリズムが記述されている。
【００８３】
第１命題
ｖ＝（ｖ1、ｖ2、…、ｖｎ）は、一定ノルムｌ1の１つのエンベロープ上の１つのリーダーベクトルｌ＝（ｘ１、ｘ２、…、ｘｎ）を持つラティスベクトルＺｎであるとする。リーダーのインデックスＩ１は次式で与えられる。：
【００８４】
【数４】
【００８５】
【化９】
【００８６】
証明。
【化１０】
逆辞書式順序でリーダーをソートしているから、１より前の第１リーダー群は、ｎ番目の成分が、ｘｎより大きい全リーダー（即ち、ｘｎ＋１≦ｇｎ≦ｒｎを満たす最大座標ｇｎを持つ全リーダー）から構成されている。
【００８７】
それら全てをリスト化せずに、第１グループのリーダーの数をカウントするために、分割関数ｑ（ｒ、ｄ）が使われる。なぜなら、ｎ番目の座標がｇｎに等しいリーダーの数は、次の注（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より大きい部分を持つこともあるからである（この場合セクション３．１.１の条件２が満たされていない）。
【００９０】
【化１１】
【００９１】
【化１２】
よって、n＋１からｒnに至るｇｎの変化を使うと、最大座標がｘｎより大きいリーダー数を、次式から決定することができる。
【００９２】
【数５】
【００９３】
【化１３】
【００９４】
先行するリーダーベクトルｌの第２グループは、第ｎ番の座標がｘｎに等しい全ベクトルからなる。但し、第ｎ−１番の座標はｘｎ−１より大きいとする。リーダーベクトルのこの数をカウントするために、上記の注（remarque）を使うが、今回は、次元ｎ−１に応用する。
【化１４】
関数minは、ノルムｒｎとオーダーｇｎ−１≦ｇｎ＝ｘｎが満足されることを保証する。
【００９５】
結果を追加次元（dimensions additionnelles）に拡張することにより、最大座標がｘｎに等しいベクトルであって、１に先行するベクトルの数は、次式で与えられる。
【００９６】
【数６】
【００９７】
式（5）、（6）を組合せて、一般式を導き、１より前に位置するリーダーベクトルの全数を計算し、従って、１のインデックスＩＩを計算することができる（式（４））。
【００９８】
【数７】
【００９９】
但し、ｊ＝０に対し、ｘｎ＋１＝＋∞
【０１００】
【化１５】
【０１０１】
【化１６】
【０１０２】
【化１７】
【０１０３】
一つのベクトルのノルムｌｐは、精度δを持つことが知られており、次式で得られる。
【０１０４】
【数８】
【０１０５】
【化１８】
【０１０６】
【化１９】
【０１０７】
【化２０】
【０１０８】
第２命題：
ベクトルν = (v1, v2, …, vn)を、一定ノルムｌｐの一つのエンベロープの上にある１つのリーダーベクトル1 = (x1, x2, …, xn)を持つ１つのラティスベクトルＺｎであるとする。リーダーベクトルＩ１のインデックスは次式により与えられる。
【０１０９】
【数９】
【０１１０】
【化２１】
【０１１１】
証明：
【化２２】
【０１１２】
【化２３】
【０１１３】
【化２４】
【０１１４】
【化２５】
【０１１５】
【化２６】
【０１１６】
【数１０】
【０１１７】
【化２７】
【０１１８】
式（９）において、ｊを０からｎ−２に亘って変化させると、ｘｎからｘ２までの座標に対する先行するリーダーベクトル１の数を正確にカウントすることができる。
【化２８】
【０１１９】
【数１１】
【０１２０】
【化２９】
【０１２１】
【化３０】
【０１２２】
【化３１】
【０１２３】
【化３２】
【０１２４】
【化３３】
セクション3.1で導入した原則を使うと、これは、次のように分割Ｎｐの数を計算することと同じである：
【０１２５】
【数１２】
【０１２６】
そして、ｉ（Np > I1）の最初の値をｘｎに割り当てる。次のステップで、xn-1をデコードする。
【０１２７】
【化３４】
次に、Xn-1をデコードするために、式（11）のメカニズムに類似したメカニズムを使ってＮｐをカウントする。しかし、今回は、（ｎ−１）番目の座標に関係して行う。
【０１２８】
この場合、Np > I1であるから、最初に、分割カウンタＮｐの値を最初のリーダーベクトル（ｘｎに等しい第ｎ成分を持つ）に戻して、パラメータＮｐを先行する値にしなければならない。以後、これをNpbckpと呼ぶことにする（“先行する値”とは、Np < I1で、Ｎｐの中で一番大きい値に対応する。即ち、ｉの最後の値が和に含まれる前のＮｐの値である）。
【化３５】
【０１２９】
このプロセスは、次元について、次式で一般化される。
【０１３０】
【数１３】
【０１３１】
【化３６】
【０１３２】
【化３７】
ただし、前記２つともに、厳密に同一の計算結果であることが前提である。
【０１３３】
【化３８】
次のセクションでは、リーダーベクトルのコーディング、デコーディングの例を説明する。
【０１３４】
コーディングとデコーディングの例
v = (-20, 16, 15, -40) を、インデキシングしなければならない形状ファクターｐ＝0.3の、一般化ガウス分布を持つ一つのソースの量子化された１つのラティスベクトルとする。置換と符号のインデックスの計算は、この研究の範囲内ではないので、また、[5,13]を使いながら簡単に実行することができるので、ここでは、リーダーベクトルのインデキシングを中心に説明する。ベクトルｖに対応するリーダーベクトルは、l = (15, 16, 20, 40)である。
コーディングとデコーディングのアルゴリズムは、以下の原則に基づく。
【０１３５】
コーディング ステップ：
１）初期設定
ｐ＝0.3、精度δ＝0.1とする。リーダーベクトルのインデックスをＩ1＝０とする。
２）次式のように、精度δを持つベクトルｌのノルムｌｐを計算する。
【０１３６】
【数１４】
３）これら演算を実行する。
最初にｆ（101）を決める。この場合、ｆ（101）＝2264である。次に、ｊ＝0に対して式（８）を使う。但し、ｉは４１（即ち、40+1）から2264（即ち、min（＋∞、2264）。次式が得られる。
【０１３７】
【数１５】
【０１３８】
４） 先行するリーダーベクトルｌの先行する数を計算する。但し、最大成分ｇ４が40であるとする。このことは、３部分の総和を、次のように計算することを意味する。
【０１３９】
【数１６】
【０１４０】
f(71) = 704, j = 1、 iは21から40 (即ち、 min(40, 704))まで変化する)として、式（８）を使うと、次式を得る。
【０１４１】
【数１７】
【０１４２】
５）先行するベクトルｌの数を計算する。但し、最大成分ｇ４が40、ｇ３が20であるとする。この場合、２部分において、和を次式で計算しなければならない。
【０１４３】
【数１８】
【０１４４】
f(46) = 167, j = 2 、 iは、17 乃至 20 (即ち min(20, 167))まで変化するとして、式（８）を使うと、次式を得る。
【０１４５】
【数１９】
【０１４６】
６）最後のステップにおいて、次の式を計算して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である。付属資料におけるアルゴリズムｌは、全てのコーディングプロセスをコンパイルしたものである。
【０１４８】
【化３９】
２）f(101) ＝ 2264を計算する。
３）ｘ４をデコードする。この場合、ｊ＝０として式(12)を使って、次式を得る。
【０１４９】
【数２０】
【０１５０】
【化４０】
【０１５１】
【化４１】
【０１５２】
【数２１】
【０１５３】
【化４２】
【０１５４】
【化４３】
【０１５５】
【数２２】
【０１５６】
【化４４】
【０１５７】
【化４５】
= min(f(23), 16) −(100775 −100774)
= min(17, 16) − (100775 − 100774)
= 15.
【０１５８】
従って、1 = (15, 16, 20, 40)が得られる。付属資料のアルゴリズム２はデコーディングプロセス全体をコンパイルしたものである。
【０１５９】
メモリコスト及び演算コスト
必要なメモリ容量
【化４６】
【０１６０】
【化４７】
【０１６１】
【化４８】
【０１６２】
【化４９】
したがって、コーディング/デコーディングのステップのためのメモリコストの上限は次式で与えられる：
【０１６３】
【数２３】
【０１６４】
メモリ容量は、主として、エンベロープのノルムと次元に依存していることに留意すべきである。ベクトルの数がＢの選択を決定する。
【０１６５】
【化５０】
必要なメモリ容量は、ｐ＝１、δ＝１，Ｂ＝４（整数タイプのデータ）として、半径ｒに応じて、式（13）に基づいて表わされ、[５]で説明したように、ベクトルに基づく従来の方法のメモリの上限と比較される。１つの次元と１つの半径がそれぞれ16,20程度に小さい場合、従来の方法では、10ギガバイト以上のメモリは必要としていなかった。これに対し、本発明で提案する方法では、必要な容量は100キロバイト以下である。
【０１６６】
必要とするメモリ容量が非常に低いこと及び全てのベクトルを知る必要がないという事実があるので、64, 128, 256, 512のように大きい次元のラティスベクトルに対しても、インデキシングすることができる。従前の研究においては、実際のアプリケーションでは、次元が１６に制限されていた。
【０１６７】
【化５１】
【０１６８】
【化５２】
式（8）とアルゴリズム（1）及び（2）（付属資料、参照）に基づくと、必要な操作は、加算／減算（A）及び比較論理演算（LC）であることが推測される。メモリアクセスは無視する。前記２タイプの演算よりも、かなりコストが低いからである。
【０１６９】
次に、本発明のインデキシング アルゴリズムのコーディング/デコーディング コストについて評価する。デコーディング アルゴリズム２は、コーディングアルゴリズムの逆であって、ほぼ同一の演算数となる。コーディング/デコーディングアルゴリズムの複雑性は、アルゴリズム１の演算回数を次のようにカウントすることにより評価される。
【０１７０】
１）（ｎ−１）Ａを実行した総和
２）“if/break”テストのために、最初の《for》（《ｊ》 の上の）が、約nnz(1)回実行される。但し、nnz(1)は、１の非０の値の数を意味する。
３）最初の《for》の各ループに対して、次のものを有している。
i. 最初の《if》のために、IＡおよび7ＬＣ 。
ii．関数《min》のために、１LC。
【化５３】
4）最後の"if"と続く行を使って，２Ａと２ＬＣを計算する。
【０１７１】
したがって、加算、論理演算、比較に関する、コーディング/デコーディングのアルゴリズムの総コストは、次の式により与えられる。
【０１７２】
【数２４】
【０１７３】
【化５４】
【０１７４】
本発明によれば、ラティスベクトルのインデキシングは、対応するレーダーベクトルのインデキシング、置換及び符号変化になる。本発明は、如何なる変換テーブルを必要とすることなくベクトルをインデキシングし、メモリの使用及び全ベクトルの生成の複雑さを低減する方法を提案する。
また、この解決法は、形状パラメータ0＜ p≦ 2を持つ一般化ガウス分布ソースに対して役立つ。本発明の方法は、分析的で、本方法を使うと、高次ベクトル次元の使用を可能にする。
【０１７５】
【表３】
【０１７６】
【表４】
【特許請求の範囲】
【請求項１】
ｄ次元空間において、少なくともベクトル（複数）の一部分１に対し、少なくとも一つのリーダーベクトルインデックスI１を計算するための量子化ステップを有するデジタルデータ処理方法であって、
前記ベクトル（複数）１は、入力データの記述子を構成し、
前記方法は、前記リーダーベクトルインデックスI１が、リーダーベクトル全体の決定ステップをもつことなく、逆辞書順序で、前記リーダーベクトル１に先行するベクトルの数に対応することを特徴とする処理方法。
【請求項２】
前記処理方法は、計算において、リーダーベクトル１以外のベクトルを決定するステップを含まないことを特徴とする請求項１に記載の処理方法。
【請求項３】
rδpdに等しい前記リーダーベクトル１のノルムlpを算出するステップが、リーダーベクトルlの各座標(x1, x2, ..., xd)に関数Tを適用することを特徴とする請求項１乃至２のいずれか１項に記載の処理方法。
但し、rδpdは、１とｄとの間を変化するｉに対し前記関数Ｔ（ｘi）の結果の総和に等しく、前記関数Ｔ（ｘi）は、精度ファクタ デルタにより冪乗ｐに高められた座標ｘiの商(division)を出力し、前記商は、一番近い整数に丸められる。
【請求項４】
リーダーベクトル インデックスI1を算出する前記ステップが、前記リーダーベクトルl(x1, x2, ...xd)の前記ノルムrδpdを計算するステップ（但し、x1 乃至 xdは、増加する順序に並べられている）、及び、ｄと１の間の変数ｉを持つ座標ｘi上で再帰的カウントステップを有すること特徴とする請求項１乃至３のいずれか１項に記載の処理方法。
但し、前記カウントステップは、座標ｘiがｘｉ+１とMIN(xi+1,Ｆ（rδpd)）との間に含まれているベクトルをカウントするもので、インデックスIlは、カウントステップの結果の和に等しく、F(Ａ)は、整数値ｗを出力する１つの関数であり、その値Ｔ（ｗ）は前記関数Ｆの引数(argument)Ａに等しい又はより小さい。
【請求項５】
リーダーベクトル インデックスI1を算出する前記ステップが、前記リーダーベクトル１(x1, x2, ...xd)のノルムrδpdの算出ステップ（但し、x1 乃至 xdは、減少する順序に並べられている）、及び、１とｄの間の変数ｉを持つ座標ｘi上で再帰的カウントステップを有すること特徴とする請求項１乃至３のいずれか１項に記載の処理方法。
但し、前記カウントステップは、座標ｘｉがｘｉ+１とMIN(xi-1,Ｆ（rδpd)）との間に含まれているベクトルをカウントするもので、インデックスIlは、カウントステップの結果の和に等しく、Ｆ(Ａ)は、整数値ｗを出力する１つの関数であり、その値Ｔ（ｗ）は前記関数Fの引数(argument)Ａに等しい又はより小さい。
【請求項６】
リーダーベクトル インデックスI1を算出する前記ステップが、前記リーダーベクトル １(x1, x2, ...xd)のノルムrの算出ステップ（但し、x1 乃至 xdは、増加する順序に並べられている）、及び、ｄと１の間の変数ｉを持つ座標ｘi上で再帰的カウントステップを有すること特徴とする請求項１乃至３のいずれか１項に記載の処理方法。
但し、前記カウントステップは、座標ｘｉがｉｘｉ+１とMIN(xi+1,ｒ-ｘi+1）との間に含まれているベクトルをカウントするもので、インデックスIlは、カウントステップの結果の和に等しく、インデックスＩ１は、カウントステップの結果の和に等しい。
【請求項７】
リーダーベクトル インデックスI1を算出する前記ステップが、前記リーダーベクトル１(x1, x2, ...xd)のノルムrの算出ステップ（但し、x1 乃至 xdは、増加する順序に並べられている）、及び、ｄと１の間の変数ｉを持つ座標ｘi上で再帰的カウントステップを有すること特徴とする請求項１乃至３のいずれか１項に記載の処理方法。
但し、前記カウントステップは、座標ｘｉがｉｘｉ+１とMIN(xi-1, ｒ-ｘi-1）との間に含まれているベクトルをカウントするもので、インデックスIlは、カウントステップの結果の和に等しく、インデックスＩ１は、カウントステップの結果の和に等しい。
【請求項８】
インデックスＩ１のバイナリコード化の結果並びに少なくとも一つの符合インデックスＩｓ、ノルムインデックスＩｎ及び置換インデックスＩｐを登録する、ベクトルデータの圧縮のための、請求項１ないし７のいずれか１項に記載の方法のアプリケーション。
【請求項９】
前記ベクトルデータは、デジタル画像であることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１０】
前記ベクトルデータは、デジタルビデオシーケンスであることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１１】
前記ベクトルデータは、デジタルオーディオデータであることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１２】
前記ベクトルデータは、デジタル３次元オブジェクトであることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１３】
前記ベクトルデータは、デジタルアニメ３次元オブジェクトであることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１４】
前記ベクトルデータは、前記ベクトルデータは変換に由来する複数係数（例：ＤＣＴ係数、ウェーブレット係数）であることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１５】
前記ベクトルデータは、データベースにおいて登録された情報であることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１６】
ベクトルデータベースにおいてサーチすることは、１つのインデックスIｌ,ref 、及び、少なくとも一つの符号インデックスIs,ref、ノルムインデックスIn,ref及び置換インデックスIp,refを、参照情報として、算出すること、及び、同一インデックスを付加されたデータをサーチすること、からなる請求項１ないし７のいずれか1項に記載の方法のアプリケーション。
【請求項１７】
前記ベクトルデータが、デジタル画像であることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項１８】
前記ベクトルデータが、デジタルビデオシーケンスであることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項１９】
前記ベクトルデータが、デジタルオーディオデータであることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項２０】
前記ベクトルデータが、デジタル３次元オブジェクトであることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項２１】
前記ベクトルデータが、デジタルアニメ３次元オブジェクトであることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項２２】
前記ベクトルデータが、テキストデータベースにおいて登録された情報であることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項２３】
前記ベクトルデータが、前記ベクトルデータの変換に由来する複数係数（例：ＤＣＴ係数、ウェーブレット係数）であることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項２４】
少なくとも請求項１乃至７のいずれか１項に適合する方法に基づいて算出されたリーダーベクトル インデックスＩ１から、デジタルデータを再構成する方法であって、
１つのリーダーベクトルの座標(xl, x2, ..., xd)を算出すること、及び、全リーダーベクトルを決定するステップを経ることなしに、逆辞書順序で、前記リーダーベクトル１に先行するベクトルの数に対応するインデックスＩ１を持つリーダーベクトル１をサーチする処理に、一つのインデックスＩ１を付加することを特徴とする再構成する方法。
【請求項２５】
請求項２４に基づいてデジタルデータを再構成する方法であって、
ｄと１との間で変化する変数ｉの再帰的な処理を行い、前記処理は、MIN (xi+1, F (rPδ,i))から0のへ変化するxiを持つ座標xiに対して行われ、また、前記関数F(A)を適用して、カウントステップの結果の加算を、和が前記インデックスＩ１より大きくなるまで行うこと、及び、前記サーチされた座標xiは、前記インデックスＩ１を超過することを特徴とする方法。
なお、前記方法は、座標Xi-1に対して、値Ｉ１に基づく加算を継続する（但し、Ｉ１は、前記インデックスを超過する前の、値Ｉ１に先行する値である）。
【請求項２６】
請求項２４に基づいてデジタルデータを再構成する方法であって、
ｄと１との間で変化する変数ｉの再帰的な処理を行い、前記処理は、MIN (xi-1, F (rPδ,i))と0との間に含まれるxiを持つ座標xiに対して行われ、また、前記関数F(A)を適用して、カウントステップの結果を加算し、その和が前記インデックスＩ１より大きくなるまで加算すること、前記サーチされた座標xiは、前記インデックスＩ１を超過することを特徴とする方法。
なお、前記方法は、座標Xi+1に対して、値Ｉ１に基づく加算を継続する（但し、Ｉ１は、前記インデックスを超過する前の、値Ｉ１に先行する値である）。
【請求項１】
ｄ次元空間において、少なくともベクトル（複数）の一部分１に対し、少なくとも一つのリーダーベクトルインデックスI１を計算するための量子化ステップを有するデジタルデータ処理方法であって、
前記ベクトル（複数）１は、入力データの記述子を構成し、
前記方法は、前記リーダーベクトルインデックスI１が、リーダーベクトル全体の決定ステップをもつことなく、逆辞書順序で、前記リーダーベクトル１に先行するベクトルの数に対応することを特徴とする処理方法。
【請求項２】
前記処理方法は、計算において、リーダーベクトル１以外のベクトルを決定するステップを含まないことを特徴とする請求項１に記載の処理方法。
【請求項３】
rδpdに等しい前記リーダーベクトル１のノルムlpを算出するステップが、リーダーベクトルlの各座標(x1, x2, ..., xd)に関数Tを適用することを特徴とする請求項１乃至２のいずれか１項に記載の処理方法。
但し、rδpdは、１とｄとの間を変化するｉに対し前記関数Ｔ（ｘi）の結果の総和に等しく、前記関数Ｔ（ｘi）は、精度ファクタ デルタにより冪乗ｐに高められた座標ｘiの商(division)を出力し、前記商は、一番近い整数に丸められる。
【請求項４】
リーダーベクトル インデックスI1を算出する前記ステップが、前記リーダーベクトルl(x1, x2, ...xd)の前記ノルムrδpdを計算するステップ（但し、x1 乃至 xdは、増加する順序に並べられている）、及び、ｄと１の間の変数ｉを持つ座標ｘi上で再帰的カウントステップを有すること特徴とする請求項１乃至３のいずれか１項に記載の処理方法。
但し、前記カウントステップは、座標ｘiがｘｉ+１とMIN(xi+1,Ｆ（rδpd)）との間に含まれているベクトルをカウントするもので、インデックスIlは、カウントステップの結果の和に等しく、F(Ａ)は、整数値ｗを出力する１つの関数であり、その値Ｔ（ｗ）は前記関数Ｆの引数(argument)Ａに等しい又はより小さい。
【請求項５】
リーダーベクトル インデックスI1を算出する前記ステップが、前記リーダーベクトル１(x1, x2, ...xd)のノルムrδpdの算出ステップ（但し、x1 乃至 xdは、減少する順序に並べられている）、及び、１とｄの間の変数ｉを持つ座標ｘi上で再帰的カウントステップを有すること特徴とする請求項１乃至３のいずれか１項に記載の処理方法。
但し、前記カウントステップは、座標ｘｉがｘｉ+１とMIN(xi-1,Ｆ（rδpd)）との間に含まれているベクトルをカウントするもので、インデックスIlは、カウントステップの結果の和に等しく、Ｆ(Ａ)は、整数値ｗを出力する１つの関数であり、その値Ｔ（ｗ）は前記関数Fの引数(argument)Ａに等しい又はより小さい。
【請求項６】
リーダーベクトル インデックスI1を算出する前記ステップが、前記リーダーベクトル １(x1, x2, ...xd)のノルムrの算出ステップ（但し、x1 乃至 xdは、増加する順序に並べられている）、及び、ｄと１の間の変数ｉを持つ座標ｘi上で再帰的カウントステップを有すること特徴とする請求項１乃至３のいずれか１項に記載の処理方法。
但し、前記カウントステップは、座標ｘｉがｉｘｉ+１とMIN(xi+1,ｒ-ｘi+1）との間に含まれているベクトルをカウントするもので、インデックスIlは、カウントステップの結果の和に等しく、インデックスＩ１は、カウントステップの結果の和に等しい。
【請求項７】
リーダーベクトル インデックスI1を算出する前記ステップが、前記リーダーベクトル１(x1, x2, ...xd)のノルムrの算出ステップ（但し、x1 乃至 xdは、増加する順序に並べられている）、及び、ｄと１の間の変数ｉを持つ座標ｘi上で再帰的カウントステップを有すること特徴とする請求項１乃至３のいずれか１項に記載の処理方法。
但し、前記カウントステップは、座標ｘｉがｉｘｉ+１とMIN(xi-1, ｒ-ｘi-1）との間に含まれているベクトルをカウントするもので、インデックスIlは、カウントステップの結果の和に等しく、インデックスＩ１は、カウントステップの結果の和に等しい。
【請求項８】
インデックスＩ１のバイナリコード化の結果並びに少なくとも一つの符合インデックスＩｓ、ノルムインデックスＩｎ及び置換インデックスＩｐを登録する、ベクトルデータの圧縮のための、請求項１ないし７のいずれか１項に記載の方法のアプリケーション。
【請求項９】
前記ベクトルデータは、デジタル画像であることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１０】
前記ベクトルデータは、デジタルビデオシーケンスであることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１１】
前記ベクトルデータは、デジタルオーディオデータであることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１２】
前記ベクトルデータは、デジタル３次元オブジェクトであることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１３】
前記ベクトルデータは、デジタルアニメ３次元オブジェクトであることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１４】
前記ベクトルデータは、前記ベクトルデータは変換に由来する複数係数（例：ＤＣＴ係数、ウェーブレット係数）であることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１５】
前記ベクトルデータは、データベースにおいて登録された情報であることを特徴とする請求項８に記載の圧縮アプリケーション。
【請求項１６】
ベクトルデータベースにおいてサーチすることは、１つのインデックスIｌ,ref 、及び、少なくとも一つの符号インデックスIs,ref、ノルムインデックスIn,ref及び置換インデックスIp,refを、参照情報として、算出すること、及び、同一インデックスを付加されたデータをサーチすること、からなる請求項１ないし７のいずれか1項に記載の方法のアプリケーション。
【請求項１７】
前記ベクトルデータが、デジタル画像であることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項１８】
前記ベクトルデータが、デジタルビデオシーケンスであることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項１９】
前記ベクトルデータが、デジタルオーディオデータであることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項２０】
前記ベクトルデータが、デジタル３次元オブジェクトであることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項２１】
前記ベクトルデータが、デジタルアニメ３次元オブジェクトであることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項２２】
前記ベクトルデータが、テキストデータベースにおいて登録された情報であることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項２３】
前記ベクトルデータが、前記ベクトルデータの変換に由来する複数係数（例：ＤＣＴ係数、ウェーブレット係数）であることを特徴とする請求項１６に記載のサーチアプリケーション。
【請求項２４】
少なくとも請求項１乃至７のいずれか１項に適合する方法に基づいて算出されたリーダーベクトル インデックスＩ１から、デジタルデータを再構成する方法であって、
１つのリーダーベクトルの座標(xl, x2, ..., xd)を算出すること、及び、全リーダーベクトルを決定するステップを経ることなしに、逆辞書順序で、前記リーダーベクトル１に先行するベクトルの数に対応するインデックスＩ１を持つリーダーベクトル１をサーチする処理に、一つのインデックスＩ１を付加することを特徴とする再構成する方法。
【請求項２５】
請求項２４に基づいてデジタルデータを再構成する方法であって、
ｄと１との間で変化する変数ｉの再帰的な処理を行い、前記処理は、MIN (xi+1, F (rPδ,i))から0のへ変化するxiを持つ座標xiに対して行われ、また、前記関数F(A)を適用して、カウントステップの結果の加算を、和が前記インデックスＩ１より大きくなるまで行うこと、及び、前記サーチされた座標xiは、前記インデックスＩ１を超過することを特徴とする方法。
なお、前記方法は、座標Xi-1に対して、値Ｉ１に基づく加算を継続する（但し、Ｉ１は、前記インデックスを超過する前の、値Ｉ１に先行する値である）。
【請求項２６】
請求項２４に基づいてデジタルデータを再構成する方法であって、
ｄと１との間で変化する変数ｉの再帰的な処理を行い、前記処理は、MIN (xi-1, F (rPδ,i))と0との間に含まれるxiを持つ座標xiに対して行われ、また、前記関数F(A)を適用して、カウントステップの結果を加算し、その和が前記インデックスＩ１より大きくなるまで加算すること、前記サーチされた座標xiは、前記インデックスＩ１を超過することを特徴とする方法。
なお、前記方法は、座標Xi+1に対して、値Ｉ１に基づく加算を継続する（但し、Ｉ１は、前記インデックスを超過する前の、値Ｉ１に先行する値である）。
【図１】
【図２】
【図３】
【図２】
【図３】
【公表番号】特表２０１１−５２５７２８（Ｐ２０１１−５２５７２８Ａ）
【公表日】平成２３年９月２２日（２０１１．９．２２）
【国際特許分類】
【出願番号】特願２０１１−５１２１６４（Ｐ２０１１−５１２１６４）
【出願日】平成２１年５月２７日（２００９．５．２７）
【国際出願番号】ＰＣＴ／ＦＲ２００９／０００６１６
【国際公開番号】ＷＯ２００９／１５６６０５
【国際公開日】平成２１年１２月３０日（２００９．１２．３０）
【出願人】（５０１０８９８６３）サントル ナシオナル ドゥ ラ ルシェルシェサイアンティフィク（セエヌエールエス） (173)
【出願人】（５１０３１９６７２）ユニベルシテ ドゥ ニース ソフィア アンティポリ (3)
【Ｆターム（参考）】
【公表日】平成２３年９月２２日（２０１１．９．２２）
【国際特許分類】
【出願日】平成２１年５月２７日（２００９．５．２７）
【国際出願番号】ＰＣＴ／ＦＲ２００９／０００６１６
【国際公開番号】ＷＯ２００９／１５６６０５
【国際公開日】平成２１年１２月３０日（２００９．１２．３０）
【出願人】（５０１０８９８６３）サントル ナシオナル ドゥ ラ ルシェルシェサイアンティフィク（セエヌエールエス） (173)
【出願人】（５１０３１９６７２）ユニベルシテ ドゥ ニース ソフィア アンティポリ (3)
【Ｆターム（参考）】
[ Back to top ]