次元ベクトルおよび可変解像度量子化
本発明は、特に可変解像度を定義するベクトル可変レート量子化による、デジタル信号の圧縮符号化および/または復号化に関する。この目的のために、推進ディクショナリは、所定の次元に対する、相互の内部に埋め込まれている増加解像度ディクショナリと、所定の次元に対する、あらかじめ決められた挿入規則(Fl)の最終集合に従って最終集合(A)から取り出された要素をより小さい次元のコードベクトルに挿入することにより生成されたコードベクトルの全体(D'i;<SP>N</SP>と、挿入規則の前記集合に従ったより小さい次元コードベクトルへの挿入により得られないコードベクトル(Y')の第2の全体との和集合を備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、格納および/または送信のためのオーディオ信号、ビデオ信号、および一般にマルチメディア信号などのデジタル信号の圧縮符号化および/または復号化に関する。
【背景技術】
【０００２】
デジタル信号の圧縮において非常に幅広く普及している解決策は、ベクトル量子化である。ベクトル量子化を使用する第1の動機は、符号化されるベクトルの次元を高めることによってより優れたパフォーマンスを達成できる、Shannonによって開発されたブロック符号化理論に見出すことができる。ベクトル量子化は、有限集合から選択された同様の次元のベクトルによって入力ベクトルを表すことを備えている。したがって、Mレベル(またはコードベクトル)を備える量子化器を提供することは、入力ベクトルの集合(一般にn次元のユークリッド実空間Rn、あるいはRnの部分集合)からRnの有限部分集合Yへの非全単射マッピングを作成することを意味する。部分集合Yは、以下のようにM個の個別要素から成る。
Y={y1,y2,...yM}
【０００３】
Yは、複製アルファベット、あるいはディクショナリ、あるいはディレクトリと呼ばれる。Yの要素は、「コードベクトル」、「コードワード」、「出口点」、あるいは「代表」と呼ばれる。
【０００４】
量子化器の次元(r)当たりのレート(またはその「解像度」)は、以下の式によって定義される。
【０００５】
【数１】
【０００６】
ベクトル量子化において、n個のサンプルのブロックは、次元nのベクトルとして処理される。ベクトルは、M個のコードベクトルのディクショナリから、最も「類似する」コードベクトルを選択することによって符号化される。一般に、全数検索は、ディクショナリのすべての要素の間で行われ、要素と入力ベクトルとの間の距離に対する測度を最小化するディクショナリの要素を選択する。
【０００７】
情報源符号化の定理によれば、次元が大きくなりすぎた場合、ベクトル量子化のパフォーマンスは、「情報源の速度-歪みの境界」と呼ばれる限界に到達する。空間の次元数は別として、ベクトル量子化は、例えば非線形および/または線形従特性、あるいは確率分布の形状など、符号化される情報源の特性を使用することもできる。一般に、ベクトル量子化器のディクショナリは、一般化ロイドアルゴリズム(GLAと呼ばれる)のような統計的手法に基づいて設計される。このアルゴリズムは周知であり、ベクトル量子化の最適性の必要条件に基づいている。符号化される情報源および初期ディクショナリを表すトレーニングシーケンスに基づいて、ディクショナリは反復して構築される。各反復は、以下の2つのステップで構成される。
- 最近傍の規則に従うトレーニングシーケンスの量子化による量子化の領域の構築
- (セントロイドの規則に従い)古いコードベクトルを領域のセントロイドに置き換えることによるディクショナリの改良
【０００８】
この決定性反復アルゴリズムの極小への収束を避けるため、シミュレーションアニーリングの技法に発想を得た「確率緩和」という名称の変種(「Stochastic K-means algorithm(確率K平均アルゴリズム)」の略語でSKAと示される)が、セントロイドを構築するステップおよび/またはクラスを構築するステップにランダム性を導入することによって提案されてきた。このようにして得られる統計的ベクトル量子化器は、何らかの構造を所持しないので、大量の計算およびメモリを必要とする点からそれらの探索を高価なものにする。具体的には、符号化および格納のいずれも複雑さは、n.2nrに比例する。ベクトルの次元およびレートに応じたこの指数関数的増加は、非構造化ベクトル量子化器の使用を、リアルタイムで埋め込むことができるように、小さい次元および/または低レートに制限する。
【０００９】
サンプルを個別に量子化するスカラー量子化は、情報源の確率分布の形状および線形従特性しか使用することができないので、ベクトル量子化ほど効果的ではない。しかし、スカラー量子化は、計算およびメモリに関しては、ベクトル量子化ほど高価ではない。さらに、エントロピー符号化に関連付けられているスカラー量子化は、適度な解像度においても良好なパフォーマンスを達成することができる。
【００１０】
サイズおよび次元の制約を回避するために、基本ベクトル量子化のいくつかの変種が研究された。彼らは、ディクショナリの構造の不在を改善しようと試み、品質の損失に至る複雑さの軽減を成し遂げようとした。しかし、パフォーマンス/複雑さの妥協が改善され、それによりベクトル量子化が、計算またはメモリのコスト面からも効果的に適用できるような解像度および/または次元のスパンを増大することが可能になる。
【００１１】
構造化ベクトル量子化器の多くの方式が、文献において提案されてきた。主なものは以下のとおりである。
- ディクショナリに階層ツリー構造を課すツリーベクトル量子化器。検索手順は単純化されるが、量子化器にはさらに多くの記憶装置が必要になる。
- より少ないレベルのベクトル量子化器をカスケードする多段ベクトル量子化器。ディクショナリはサイズが減少し、計算時間およびメモリのコストについても同様のことがいえる。
- より小さい次元およびサイズのNクラシカルベクトル量子化器の「デカルト積」と呼ばれるベクトル量子化器。入力ベクトルはN個のサブベクトルに分解され、各サブベクトルは相互に独立して量子化される。
- 「ゲイン/方位」ベクトル量子化器は、「デカルト積」ベクトル量子化器の特別な事例を構成する。一方はスカラー量子化器、もう一方はベクトル量子化器である2つの量子化器が提供される。これらは単独にせよそうでないにせよ、(正規化入力ベクトルを考慮することにより)ベクトルのゲイン(またはノルム)とその方位を個別に符号化する。この種のベクトル量子化はまた、「球形」ベクトル量子化または「極性」ベクトル量子化とも呼ばれる。
- 「置換コード」ベクトル量子化器。そのコードベクトルはリーダーベクトルの成分の置換と置換コードの合成(または和集合)へのその一般化とによって得られる。
【００１２】
前述の技法はすべて、統計的手法の範囲内にある。
【００１３】
もう1つの根本的に異なる手法も提案された。それは代数ベクトル量子化であり、点の正規格子またはエラーコレクターコードから生じる高度に構造化されたディクショナリを使用するものである。それらのディクショナリの代数的特性により、代数ベクトル量子化器は、実装が簡単であり、メモリに格納される必要はない。これらのディクショナリの正規構造の使用は実際に、最適かつ高速な検索アルゴリズムの開発と、特に索引を(例えば公式を通じて)対応するコードベクトルに関連付けるためのメカニズムの開発とを可能にする。代数ベクトル量子化は、実装がさほど複雑ではなく、必要なメモリも少なくてすむ。しかし、これらは(空間内、あるいは超球の表面上の)情報源の均一な分布についてのみ最適である。均一スカラー量子化器の一般化であるが、代数ベクトル量子化は、いわゆる「圧伸」技法を通じて情報源の分布に合わせて調整することがより困難である。さらに、コードベクトルの索引付け(または番号付け)および逆の操作(復号化)では、これらの操作がテーブルからの簡単な読み取りによって行われる統計ベクトル量子化器の場合に比べて、さらに多くの計算が必要となることも思い起こされる。
【００１４】
可変次数量子化の特定の態様および遭遇する問題は、これ以降で提示される。
【００１５】
最初に、ベクトル量子化が既知であり、固定長のサンプルのブロックを符号化するための効果的な技法であることが示される。しかし、デジタル信号圧縮の多くの適用において、符号化される信号は、可変長のパラメータのシーケンスによってモデル化される。可変次元のこれらのベクトルの効果的な圧縮は、スピーチまたはオーディオ符号器(「MBE」符号器、調波符号器、正弦波符号器、変換ベースの符号器、原型波形の補間に基づく符号器)など多くのマルチメディア符号器の設計に不可欠である。
【００１６】
正弦波符号器において、抽出される正弦波の数は、信号中に検出される正弦波スパイクの数に基づくが、その数はオーディオ信号の特性に応じて時間の経過と共に変化する。
【００１７】
さらに、音声圧縮の多くの技法は、信号の長期的周期性を利用する。このことは、話者の基本周期の高調波である一連の周波数のスペクトル成分が符号化される調波符号器の場合も同様である。この基本周期は、話者(通常、子供は大人よりも声帯の振動周波数が高い)および時間の経過と共に変化するので、スペクトル調波スパイクの数は基本周波数に反比例するが、量子化される成分の数も時間の経過と共にフレームごとに変化する。
【００１８】
このことはまた、原型波形がピッチの期間と等しい長さのセグメントにわたり抽出され、そのため時間的に可変でもある、PWI符号器(「Prototype Waveform Interpolation」の略)の場合も同様である。PWI符号器において、これらの可変長の波形の量子化は、ゲイン(または「Root-Mean-Square(二乗平均平方根)」の略語である「RMS」)と、自身がREW波形(「Rapidly Evolving Waveform」)およびSEW波形(「Slowly Evolving Waveform」)という同じ可変長の2つの波形に分解される正規化波形とを個別に符号化することによって達成される。固定長のフレームの場合、原型の数は可変であり、そのためREWおよびSEW波形の次元と同様に、ゲインの数、REWおよびSEWの数も同様に可変である。
【００１９】
変換ベースのオーディオ符号器など、他の種類の符号器において、固定長フレーム長にわたって取得された変換係数の数が課されるが、これらの係数をそれらの量子化のために周波数帯域にグループ化することが通例である。従来、この分割は、耳の臨界帯域に従うことによって人間聴覚の心理音響的な特性を利用するように、不均等な幅の帯域に行われる。変換係数のこれらのベクトルの次元の変化の範囲は通常、広帯域符号器(50Hz〜7000Hz)において3(低周波数帯域の場合)から15(高周波数帯域の場合)まで変化し、FM帯域符号器(20Hz〜16000Hzの可聴範囲に及ぶ)において24まで変化する。
【００２０】
理論的には、可変次元の最適なベクトル量子化器は、入力ベクトルの可能な次元ごとに1つ、固定次元のディクショナリのセットを利用することであろう。例えば、60〜450Hzのピッチ期間で、電話帯域の調波スパイクの数が高ピッチの音声(子供)の7から低ピッチの音声(大人)の52まで変化する調波符号器において、46(46=52-7)ベクトル量子化器を構築し、メモリに配置して実装することが必要になる。各ディクショナリの設計には、入力ベクトルの統計を正確に表す十分な長さの学習シーケンスが必要である。さらに、すべてのディクショナリの格納は、メモリ内では実際的ではないか、または非常に高価であることが判明する。したがって、可変次元の場合、記憶装置の制約及びトレーニングシーケンスの制約にも応じながら、同時にベクトル量子化の利点を活用することは困難であることが分かる。
【００２１】
以下に提示されるのは、可変解像度による量子化の特定の態様および遭遇する問題である。
【００２２】
第1に、入力信号の変動性は、符号化されるパラメータの数における変化を通じてのみ顕在化するのではなく、所定の品質で送信されるバイナリ情報の量における変化を通じても顕在化することが指摘される。例えばスピーチにおいて、頭子音、有声音、および無声音は、同一品質の同じレートを必要とはしない。比較的予測不能な頭子音には、さらに安定し、その定常性がレートを減少させることのできる「予測子」によって活用されうる有声音よりも高いレートが必要になる。最後に、無声音は、高い符号化精度を必要とせず、そのためほとんどレートを必要としない。
【００２３】
音声またはビデオのようなマルチメディア信号の特性の一時的な変動を利用するため、可変レート符号器を設計することが賢明である。これらの可変レート符号器は、インターネット、ATMなどのような、パケット的な格子にわたる通信に特に適している。
【００２４】
具体的には、パケット交換は、情報ビットをさらに柔軟な方法で扱いかつ処理することができるので、平均レートを減少することによってチャネルの容量を増加させることができるようにする。変数レート符号器の使用はさらに、システムの輻輳を抑制する効果的な手段および/またはアクセス条件の多様性に対応する効果的な手段でもある。
【００２５】
マルチメディア通信においては、可変レート量子化器はまた、以下のようなレートの分布を最適化することも可能にする。
- 情報源およびチャネル符号化間。AMR(「Adaptive Multi Rate(適応マルチレート)」)の概念におけるように、レートは、トラフィックおよびチャネルエラー条件に動的に適合されるように各20msフレームで切り替えることができる。このようにしてスピーチの全体的な品質は、エラーに対する良好な保護を確実にし、同時にチャネルが機能低下した場合に情報源の符号化のレートを減少することによって改善される。
- 様々な種類のメディア信号間(テレビ会議アプリケーションにおける音声およびビデオなど)。
- 同一の信号の様々なパラメータ間。変換ベースのオーディオ符号器において、例えば、スペクトル包絡線と係数の様々な帯域との間でビットを動的に分散することが通例である。多くの場合、包絡線のエントロピー符号化が最初に実行され、その目的は、可変長コードをコードワードに割り当てることによりコードワードの非均一な分散を使用して、最も可能性の高いものは最も可能性の低いものよりも短い長さを持ち、それによりコードワードの平均長の最小化を導くことである。さらに、人間の耳の心理音響的な特性を利用するために、残りの(可変)レートが係数の周波数帯域にそれらの知覚有意性に応じて動的に割り振られる。
【００２６】
マルチメディア符号化の新しいアプリケーション(オーディオおよびビデオなど)は、次元およびレートの両方において極めて柔軟な量子化を必要とする。レートの範囲はさらに高品質を達成できるようにしなければならないので、これらの多次元および多解像度の量子化器は高解像度をめざす必要がある。これらのベクトル量子化器によってもたらされる複雑な障壁は、新技術の処理能力および記憶容量の増大にもかかわらず、それ自体が依然として達成すべきパフォーマンスであり続ける。
【００２７】
以下の説明から分かるように、提案されている情報源符号化技法の多くは、可変次元に関連する問題、または可変解像度に関連する問題を解決することを目的としている。これらの2つの問題を共に解決できるようにする技法は、今日までほとんど提案されていない。
【００２８】
既知の可変次元によるベクトル量子化に関しては、符号化されるパラメータの次元の可変性それ自体がベクトル量子化の使用の障壁を構成する。したがって、変換ベースの符号器の最初のバージョンは、Lloyd-Maxスカラー量子化器を採用する。「TDAC」と呼ばれるこのタイプの符号器は、本出願者によって開発され、特に以下の文献において説明されている。
- 「High Quality Audio Transform Coding at 64 kbit/s」Y.Mahieux、J.P.Petit共著、IEEE Trans.Commun、Vol.42、No.11、3010〜3019頁、1994年11月
【００２９】
この可変次元ベクトル量子化の問題を解決するために、他の解決策が提案されてきた。「IMBE」符号器は、可変バイナリ割り振りおよびスカラー/ベクトル混成量子化を備える複雑な符号化体系を使用する。
【００３０】
可変次元のベクトルを量子化するため広く一般的に使用される手法は、量子化前に可変次元のベクトルを別の固定次元のベクトルに変換するように前処理することにある。次元変換に関連付けられるこのベクトル量子化技法の変種はいくつかある(この種のベクトル量子化は「Dimension Conversion Vector Quantization」の略語であるDCVQと示される)。
【００３１】
提案された様々な次元変換手順の中で、切捨て、副標本、補間、「長さワーピング」について特に言及される。
【００３２】
正弦波スピーチ符号器つまりMBEの場合、スペクトル係数が固定された順序の全極モデルによって近似され、その後モデルのパラメータの固定次元のベクトル量子化が実行されることが提案された。非正方行列変換によるベクトル量子化のもう1つの技法は、固定次元K(K<L)のベクトル量子化を非正方行列一次変換(L×K)と組み合わせることにより、可変次元Lのベクトル量子化の問題を解決する。
【００３３】
さらに、依然として固定次元Kのベクトル量子化を使用するが、入力ベクトルと同じ次元を有するコードベクトルを取得するために次元変換がコードベクトルに適用される次元変換に関連付けられているベクトル量子化のもう1つの種類がある。
【００３４】
次元変換に関連付けられたベクトル量子化の欠点は、全歪みが、量子化による成分および次元変換による成分という2つの成分を有することである。次元変換によるこの歪みを回避するため、可変次元のベクトル量子化のもう1つの手法は、可変次元Lの各入力ベクトルを次元K(L<K)の「基礎をなす」ベクトルの成分の部分集合から形成されると見なすこと、および入力ベクトルの次元の全範囲に及ぶ固定次元Kの単一の「ユニバーサル」ディクショナリのみを設計して使用し、入力ベクトル間の対応は選択子によってもたらされることを備えている。しかし、他の低次元のディクショナリをすべて網羅するこの「ユニバーサル」ディクショナリは、最低次元に最適であるとは考えられない。特に、次元当たりの最大解像度rmaxは、格納の制約およびパラメータのベクトル当たりのレートによって制限されている。サイズ2Krmaxのディクショナリの場合、このディクショナリを格納するために必要なメモリ量はK2Krmax値であり、そのパラメータのベクトル当たりのレートはKrmaxである。したがって、同一のサイズのディクショナリ(したがってパラメータのベクトル当たりおよびフレーム当たり同一のレート)の場合、次元L(L<K)のベクトルは、K/L倍大きい解像度(または次元当たりのレート)、およびK/L倍小さい格納される情報量を有することができる。
【００３５】
既知の可変解像度によるベクトル量子化に関しては、簡単な解決策は、可変次元によるベクトル量子化の場合に関して、例えばTDAC変換ベースの符号器の第1のバージョンにおけるように、スカラー量子化を使用することにある。
【００３６】
しかし、サンプル当たりの整数解像度の使用は、動的バイナリ割り振り手順の有効性を妨げる係数の帯域当たりの解像度の粗い細分性を必然的に伴う。したがって、符号化索引を結合バイナリ列として配置する手順と組み合わせて、再構築レベルの奇数の整数によるスカラー量子化の使用が提案された。さらに細かい解像度の細分性が提供され、バイナリ割り振り手順にさらに好都合になり、索引を組み合わせるアルゴリズムの複雑さを犠牲にして、品質を改善することが可能になった。このアルゴリズムは、バイナリ列への配置をレートに関して効果的にするために必要であった。それにもかかわらず、多数の係数を有する高い周波数帯域に対して、スカラー量子化に起因する、サンプル当たりの整数のレベルの制約は、依然として帯域当たりの解像度の細分性が粗すぎることを通じて顕在化されている。
【００３７】
ベクトル量子化は、サンプル当たりの多くの整数レベルのこの制約を回避できるようにし、使用可能な解像度の微細な細分性を可能にする。一方、ベクトル量子化の複雑さは多くの場合、使用可能なレートの数を制限する。例えば、周知のACELP技術に基づくAMR-NBマルチレートスピーチ符号器は、各々が情報源符号化とチャネル符号化との間のレートの異なる分散によりエラーに対する異なるレベルの保護を有する、12.2kbit/sから4.75kbit/sの範囲の8つの固定レートを備えている。ACELP符号器のパラメータ(LSP、LTP遅延器、励起ゲイン、固定励起)のそれぞれについて、異なる解像度のディクショナリが構築された。しかし、これらのパラメータの各々に使用可能なレートの数は、非代数ベクトル量子化器の格納の複雑さにより制限されている。さらに、6.60から23.85kbit/sの範囲の9つのレートを備えるAMR-WBマルチレート符号器において、基本的に、レートの変動は、格納を必要としない代数励起ディクショナリによって保証される。8つのディクショナリがあるので、固定励起に8つのレートがあるが、一方確率ディクショナリを使用する他のパラメータ(LSP、ゲイン、絶対および差分遅延)は2つの可能なレートしか持たない。
【００３８】
AMRマルチレート符号器に使用される確率ベクトル量子化器が、制限付きの構造(デカルト積および多段)によるベクトル量子化器であることが示されている。可変レート量子化器の大きなファミリーは、実際、多段、デカルト積を有する前述の量子化器、あるいはツリーベースのベクトル量子化器などの制約付き構造ベクトル量子化器を基にすることもできる。可変レート符号化へのこれらのツリーベースの量子化器の使用は、数多くの研究の主題を形成してきた。バイナリツリーベースのベクトル量子化器は、最初に導入されたものであった。これは、トレーニングシーケンスの重心である「ルート」ノードに基づくセントロイドの連続分割によりベクトル量子化器を設計するためのLBGアルゴリズムから必然的に派生する。変種のツリータイプベクトル量子化器は、枝刈りすることに基づき、あるいは逆にツリーの特定のノードを、非バイナリおよび/または非平衡のツリーベースのベクトル量子化器に至るそれらの歪み、それらのノードの分布などの特性に従って分岐することに基づいて提案されてきた。
【００３９】
図1aおよび1bは、ツリー構造のベクトル量子化器を表している。具体的には、図1aは平衡バイナリツリーを表し、一方図1bは非バイナリの非平衡ツリーを表している。
【００４０】
複数解像度のベクトル量子化器は、望ましい様々な解像度に対応するノード数を選択することにより、ツリータイプのベクトル量子化器に基づいて容易に構築される。ツリータイプの階層構造は、訴求力があり、検索手順を単純化する。一方、これは、次善の検索を伴い、また中間レベルのすべてのノードを介するルートノードから端末ノードまでツリーのすべてのノードが格納される必要があるため、必要なメモリの大幅な増加を伴う。さらに、低解像度のディクショナリのノードのセットは高解像度のディクショナリに含まれないので、ベクトル量子化器のレートの増加に応じた量子化エラーの減少は、局所的には保証されない。
【００４１】
さらに、代数コードに基づいて可変解像度量子化器を構築する方法、特に8次元の正則Gosset格子の球形コードの部分集合を使用するEAVQ（埋め込み代数ベクトル量子化器）を構築する方法は知られている。
【００４２】
以下の文献において、
- 「A 16,24,32 kbit/s wideband speech codec based on ACELP」P.Combescure、J.Schnitzler、K.Fischer、R.Kircherr、C.Lamblin、A.Le Guyader、D.Massaloux、C.Quinquis、J.Stegmann、P.Vary共著、Proceedings IEEE International Conference on Acoustics, Speech, and Signal Processing、Vol.1、5〜8ページ、1999年
この埋め込み代数ベクトル量子化の手法は、様々な次元の代数コードを使用して可変次元量子化まで拡大された。たとえこのEAVQ量子化の一般化が、可変解像度で可変次元のベクトルを量子化できるようにするとしても、これには欠点がある。
【００４３】
入力ベクトルの分布は均一である必要がある。しかし、この制約に情報源の分布を適合させることは、非常に困難な作業である。正則格子に基づく代数量子化の設計はまた、望ましい様々な解像度を得るために様々な正則格子の領域を切り捨てて調整し、それを様々な次元に対して行うという問題も引き起こす。
【非特許文献１】「High Quality Audio Transform Coding at 64 kbit/s」Y.Mahieux、J.P.Petit共著、IEEE Trans.Commun、Vol.42、No.11、3010〜3019頁、1994年11月
【非特許文献２】「A 16,24,32 kbit/s wideband speech codec based on ACELP」P.Combescure、J.Schnitzler、K.Fischer、R.Kircherr、C.Lamblin、A.Le Guyader、D.Massaloux、C.Quinquis、J.Stegmann、P.Vary共著、Proceedings IEEE International Conference on Acoustics, Speech, and Signal Processing、Vol.1、5〜8ページ、1999年
【非特許文献３】「Algorithme de Quantification Vectorielle Algebrique Spherique par le Reseau de Gosset E8」、C.Lamblin、J.P.Adoul、Annales Des Telecommunications、no 3-4、1988年["Spherical algebraic vector quantization algorithm by the E8 Gosset lattice"]
【発明の開示】
【発明が解決しようとする課題】
【００４４】
本発明は、この状況を改善することを目的としている。
【００４５】
本発明の目的の1つは、一般的に、可変次元のベクトルの可変レート量子化の問題に効果的かつ経済的な解決策(特に記憶装置に関して)を提案することである。
【００４６】
本発明のもう1つの目的は、非限定的な意味で、特にスピーチおよび/またはオーディオ信号の、調波符号器のスペクトル振幅および/または周波数符号器の変換係数の量子化を使用してデジタル信号の符号化および復号化を有利に提供するベクトル量子化を提供することである。
【課題を解決するための手段】
【００４７】
この目的を達するために、本発明は、可変次元のコードベクトルを備え、可変解像度を定義する可変レートのベクトル量子化により、デジタル信号の圧縮符号化および/または復号化のために装置において使用することを意図されたディクショナリを提案し、ディクショナリは、
- 一方においては、所定の次元に対して、解像度増加の中間埋め込みディクショナリと、
- 一方においては、所定の次元に対して、
・あらかじめ決められた挿入規則の有限コレクタに従って、実数の有限集合から取り出された要素を、低次元のディクショナリのコードベクトルに挿入することによって構築されたコードベクトルから成る第1の集合と、
・挿入規則の前記収集に従って前記有限集合の要素の低次元のコードベクトルへの挿入によって取得できないコードベクトルから成る第2の集合との和集合を備えている。
【００４８】
好ましくは、挿入規則の前記収集は、ベクトルの所定の位置において成分を装って実数の有限集合の単一要素を挿入するステップを備える基本規則に基づいて定式化される。
【００４９】
各基本規則は、
- 前記有限集合の要素の位の正整数と、
- 挿入の位置の正整数とを示す上記2つの正整数の組によって定義されることが好ましい。
【００５０】
このようにして特徴付けられた挿入規則は、本発明の意義の範囲内でディクショナリの実際の構造から直接に読み取られ推定されることを理解されよう。
【００５１】
もちろん、純粋に可逆的に、低次元N(N<N')を得るように所定の次元N'の有限集合の1つまたは複数の要素を削除するステップを備える削除規則を定義することができる。
【００５２】
本発明はさらに、本発明によるディクショナリを形成する方法を目的としている。所定の次元に対して、
a)第1の集合は、あらかじめ決められた挿入/削除規則の有限収集に従って、実数の有限集合から取り出された低/高次元要素のディクショナリのコードベクトルに/から挿入/削除することによって形成されたコードベクトルから成り、
b)第1の中間のディクショナリは、前記所定の次元に対して、少なくとも前記第1の集合が構築されることを備え、
c)前記ディクショナリを少なくとも1つの所定の解像度で使用するように適合するため、第2の最終的なディクショナリが、中間ディクショナリに基づいて、増加/減少解像度のディクショナリの埋め込み/単純化により構築され、増加解像度のディクショナリは、最小解像度のディクショナリから最大解像度のディクショナリまで中間埋め込みされる。
【００５３】
もちろん、「集合Aの集合Bへの埋め込み」という用語は、集合Aが集合Bに含まれることを意味するよう意図されている。さらに、「集合Bを得るための集合Aの単純化」という用語は、集合Aが集合Bを含むことを意味するよう意図されている。
【００５４】
変種または補足により、一方でステップa)およびb)、一方でステップc)は、コードベクトルの所定の次元Nで使用するように前記ディクショナリを適合するため、実質上逆転することができることを理解されたい。
【００５５】
この場合、
- ステップc)において、依然として次元N'であるがより高い/低い解像度rNである第1の中間のディクショナリが、前記第1のディクショナリの解像度rNを実質的に獲得するように、増加/減少解像度のディクショナリの埋め込み/単純化により、解像度rNおよび次元N'の初期ディクショナリに基づいて構築され、
- ステップa)において、所定の次元Nを獲得するため、第1の集合は、あらかじめ決められた挿入/削除規則の有限収集に従って、実数の有限集合から取り出された前記所定の次元N要素よりも低い/高い次元N'の第1のディクショナリのコードベクトルに/から挿入/削除することによって形成されたコードベクトルから成り、
- ステップb)において、解像度rNへの最終的な適合の可能なステップに続いて、少なくとも前記第1の集合からなる第2の最終のディクショナリは、前記所定の次元Nに対して構築されることを備える。
【００５６】
連続次元を増加することによりステップa)を実装することができる。この場合、所定の次元Nに対して、
a0)前記所定の次元Nよりも低い初期次元nの初期ディクショナリが取得され、
a1)あらかじめ決められた挿入規則の有限収集に従って、実数の有限集合から取り出された要素を初期ディクショナリのコードベクトルに挿入することによって形成された次元n+iのコードベクトルから成る第1の集合が構築され、
a2)挿入規則の前記収集による前記有限集合の要素の初期ディクショナリのコードベクトルへの挿入によって取得できない次元n+iのコードベクトルから成る第2の集合が提供され、
a3)前記第1の集合および前記第2の集合の和集合から成る次元n+iの中間ディクショナリが構築され、
ステップa1)からa3)は、前記中間ディクショナリが初期ディクショナリを装い、前記所定の次元Nまで、多くともN-n-1回繰り返され、この場合(i=1)である。
【００５７】
また、連続次元を減少することによりステップa)を実装することもできる。この場合、所定の次元Nに対して、
a'0)前記所定の次元Nよりも高い初期次元nの初期ディクショナリが取得され、
a'1)次元n-iの第1の集合は、あらかじめ決められた削除規則の有限収集に従って、次元nのディクショナリからの次元n-iの可能なコードベクトルの選択および抽出により構築され、
a'2)削除規則の前記収集による前記有限集合の要素の初期ディクショナリのコードベクトルからの削除によって単純に取得できない次元n-iのコードベクトルから成る第2の集合が提供され、
a'3)前記第1の集合および前記第2の集合の和集合から成る次元n-iの中間ディクショナリが構築され、
ステップa'1)からa'3)は、前記中間ディクショナリが初期ディクショナリを装い、前記所定の次元Nまで、多くともn-N-1回繰り返され、この場合(i=1)である。
【００５８】
連続次元1からNまでの複数のNディクショナリを取得するために、好ましくは次元n(n<N)の初期ディクショナリに基づいて、次元n+1からNに対するステップa1)からa3)の繰り返しの実装を通じ、次元n-1から1に対するステップa'1)からa'3)の繰り返しの実装を通じて、ステップa1)からa3)およびステップa'1)からa'3)を組み合わせることが可能である。
【００５９】
このようにして、最大の次元のディクショナリが次元Nを有するNディクショナリの全体または一部を取得する。
【００６０】
連続次元のディクショナリの構築に役立つ有限集合および挿入/削除規則の収集は、以下のように定義することができる。
- 量子化される情報源の分析により、ディクショナリを構築する前に、演繹的に、
- ディクショナリの構築後に、好ましくは連続解像度のディクショナリの埋め込み/単純化により、帰納的に。この構築の後には、このように構築されるこれらのディクショナリの統計的分析が続く。
【００６１】
量子化される情報源は好ましくは学習シーケンスによってモデル化され、有限集合および挿入/削除規則の収集の「演繹的」定義は、好ましくは情報源の統計的分析によって達成されることが示されている。前述の有限集合は、好ましくは量子化される情報源の単一次元の確率密度の推定によって選択される。
【００６２】
有限集合および挿入規則の演繹的および帰納的定義を組み合わせることにより、
- 挿入/削除規則の第1の集合および第1の収集は、1つまたは複数の中間ディクショナリを形成するように、学習シーケンスの分析により有利に演繹的に選択することができ、
- 前記第1の集合および/または挿入/削除規則の前記第1の収集の少なくとも一部は、1つまたは複数の前記中間ディクショナリの帰納的分析によって更新され、
- 必要に応じて、前記1つまたは複数の前記中間ディクショナリを形成するコードベクトルの集合の少なくとも一部も更新される。
【００６３】
好ましくは、所定の解像度への適合のステップc)は、増加解像度を達成するために、以下の操作を備えている。
c0)前記所定の解像度rNよりも低い初期解像度rnの初期ディクショナリが取得され、
c1)初期ディクショナリに基づいて、初期解像度rnよりも高い解像度rn+1の中間ディクショナリが構築され、
c2)所定の解像度rNが達成されるまで、操作c1)が繰り返される。
【００６４】
有利なことに、操作c1)の繰り返しごとに、クラスおよびセントロイドの構造が提供され、そこで現行解像度riよりも高い解像度のディクショナリに少なくとも属しているセントロイドが再計算されて更新される。さらに、現行解像度riよりも低い解像度のディクショナリに属しているセントロイドは、低い解像度のすべてのディクショナリの全歪みが1つの更新からその次の更新で減少する場合に限り、好ましく更新される。
【００６５】
補足または変種を経て、ステップc)は、減少解像度を達成するために、以下の操作を備えている。
c'0)前記所定の解像度rNよりも高い初期解像度rnの初期ディクショナリが取得され、
c'1)初期ディクショナリに基づき、初期ディクショナリをあらかじめ決められた基準に従って順序付けられた複数の部分集合に区分化することによって、初期解像度rnよりも低い解像度rn-1の中間ディクショナリが構築され、
c'2)所定の解像度rNが達成されるまで、操作c'1)が繰り返される。
【００６６】
有利なことに、この分割化は、実装された挿入/削除規則の少なくとも一部を使用し、ステップa)およびb)の意義の範囲内の制御された拡張による部分的合成を使用することができる。
【００６７】
解像度r1およびrNの間の中間解像度rnの初期ディクショナリに基づいて、それぞれの解像度r1からrNの複数のNの連続ディクショナリを取得するために、増加解像度rn+1からrNに対してステップc1)の繰り返しを実装し、減少解像度rn-1からr1に対してステップc'1)の繰り返しを実装することが有利に可能である。
【００６８】
有限集合および挿入/削除規則の収集は、望ましい次元および解像度の、本発明の意義の範囲内のディクショナリを形成するため、このように取得された様々な解像度および次元のディクショナリの統計の帰納的な検討を通じて有利に選択されうることが理解されよう。
【００６９】
本発明により提供される利点の1つによれば、符号化/復号化の実装に必要な記憶装置は、大幅に減少させることができる。具体的には、有利なことに、各々索引によって識別された挿入/削除規則の前記収集は、これを最後にメモリ内に格納されており、かつ所定の次元に対して、
- 前記第2の集合は、所定の次元よりも低い/高い次元のコードベクトルへの挿入/削除規則の適用により取得することができないコードベクトルを備え、
- さらに、少なくとも1つの対応するテーブルは、挿入/削除規則の索引および前記第2の集合の要素を識別する索引を使用して、所定の次元のディクショナリの任意のコードベクトルを再構成できるようにする。
したがって、前記所定の次元のディクショナリの完全な格納は、前記第2の集合の要素およびリンクを、これらの要素および関連付けられている挿入/削除規則へのアクセスのために対応するテーブルに単に格納することによって回避される。
【００７０】
それゆえに、所定の次元に対して、前述の第2の集合は、前記所定の次元よりも低い次元の「第2の」部分集合を有利に備えることができることが理解されよう。
【００７１】
1つの実施形態において、挿入/削除メカニズム自体はプログラムルーチンを装って格納することができるが、挿入/削除パラメータは、所定の挿入/削除規則に対して、この所定の挿入/削除規則の索引と組み合わせて、一般対応テーブル(原則として前述の対応テーブルとは異なる)に格納することができる。
【００７２】
好ましくは、対応テーブルは、以下のものを表す3つの整数スカラー値の集計を通じて、現行次元の第2の集合内の現行索引の要素に基づいて再構築することのできる所定の次元のディクショナリのコードベクトルの索引ごとに、前もって定式化される。
- 前記第2の集合の現行次元
- 第2の集合の要素の現行索引
- 挿入/削除規則の索引
この挿入/削除規則は少なくとも、前記現行索引および前記現行次元に対応する要素に挿入/削除を適用することによって、所定の次元のディクショナリの前記コードベクトルを再構成することに寄与する。
【００７３】
これらの後者の特性は、以下に説明されるように、圧縮符号化/復号化方法において有利に実装することができる。
【００７４】
この点において、本発明はさらに、可変解像度を定義する可変レートでのベクトル量子化によって、デジタル信号を圧縮符号化/復号化するために、本発明により、また前述のステップの実装を通じて得られるディクショナリを使用することも目的としている。特に、所定の次元jのディクショナリ内の入力ベクトルy=(y0,...,yk,...,yj-1)の最近傍であるコードベクトルについて検索が行われる。この使用は次に、以下のステップを実装する。
CO1)検索される前記コードベクトルの現行索引に対し、対応するテーブルに表示される索引の読み取りと、必要に応じて前記ディクショナリを作成できるようにする第2の集合の要素の読み取りとを少なくとも通じて、前記現行索引に対応する索引のコードベクトルの少なくとも部分的な再構築であって、
符号化/復号化ステップを適正に続行する方法は、
CO2)少なくとも符号化において、入力ベクトルとステップC01)において再構成されたコードベクトルとの間の距離の計算と、
CO3)少なくとも符号化において、前記ディクショナリのすべての現行索引に対して、ステップC01)およびC02)の繰り返しと、
CO4)少なくとも符号化において、ステップC02)の繰り返しの1つの過程で計算された入力ベクトルとの距離が最も小さい、少なくとも部分的に再構成されたコードベクトルの索引の識別と、
CO5)少なくとも復号化において、索引がステップC04)において識別されたコードベクトルを装った入力ベクトル(y)の最近傍の決定とを備えている。
【００７５】
前述のように、「第2の」上記の集合は、好ましくは第2の集合の所定の次元よりも低い次元の「第2の」部分集合を備えていることが思い起こされる。
【００７６】
特定の実施形態において、ステップC01)は、少なくとも復号化の際に、
C011)対応テーブル内での、前記第2の集合および挿入規則へのリンクを表す索引の読み取りであって、
- 前記第2の集合の部分集合の現行次元の索引と、
- 前記部分集合の要素の現行索引と、
- 前記要素に基づき、所定の次元のディクショナリのコードベクトルの構築のための適切な挿入規則の索引とを含む索引の読み取り、
C012)現行次元によって識別される部分集合内での、その現行索引によって識別される前記要素の読み取り、
C013)ステップC012)において読み取られた前記要素に、ステップC011)において読み取られたその索引によって識別された適切な挿入規則を適用することによる、前記所定の次元へのコードベクトルの完全な再構成を備えている。
【００７７】
特定の実施形態において、符号化の際に、
* ステップC01)は、
C011)対応テーブル内での、前記第2の集合および挿入規則へのリンクを表す索引の読み取りであって、
- 前記第2の集合の部分集合の現行次元の索引と、
- 前記部分集合の要素の現行索引と、
- 前記要素に基づき、所定の次元のディクショナリのコードベクトルの構築のための適切な挿入規則の索引とを含む索引の読み取り、
C012)現行次元によって識別される部分集合内での、その現行索引によって識別される前記要素の読み取り、
* ステップC02)において、前記距離は、
- 前記挿入規則と、
- 前記要素との関数として推定される歪み基準の関数として計算される。
【００７８】
したがって、単に復号化のために完全な再構築を保持しておくことによって、ステップC01)の前記所定の次元をコードベクトルの部分的な再構築のみに提供することが可能である。
【００７９】
有利な実施形態において、置換コードの和集合に従って補足構造化特性がさらに提供され、置換コードのこの和集合の索引は以下のステップの実装に使用される。
CP1)入力信号に基づき、絶対ベクトル|y|=(|y0|,...,|yk|,...,|yj-1|)および符号ベクトルε=(ε0,...,εk,...,εj-1)、εk=±1によって定義される入力ベクトルy=(y0,...,yk,...,yj-1)が形成され、
CP2)ベクトル|y|の成分は、リーダーベクトル
【００８０】
【数２】
【００８１】
を取得するため、置換によって、値を減少することによりランク付けされ、
CP3)次元jのディクショナリDjiのリーダーベクトルの中からリーダーベクトル
【００８２】
【数３】
【００８３】
の最近傍xj'が判別され、
CP4)ディクショナリDjiの前記最近傍xj'のランクの索引が判別され、
CP5)符号化/復号化の実効値は、ステップCP4)において判別された前記索引、ステップCP2)において判別された前記置換、およびステップCP1)において判別された前記符号ベクトルに依存している入力ベクトルに適用される。
【００８４】
本発明のもう1つの有利な態様によれば、符号化/復号化および場合によっては1つまたは複数のディクショナリの構築に対して、対応テーブルおよび前述の第2の集合の要素を、特に圧縮符号化/復号化装置のメモリに格納する備えがある。
【００８５】
この点について、本発明はさらに、そのような符号化/復号化装置を目的としている。
【００８６】
本発明はさらに、処理装置、特にコンピュータまたは携帯端末のメモリ、あるいは取り外し可能記憶媒体上に格納されることを意図され、処理装置の読取機構と連携することを意図されたコンピュータプログラム製品を目的としており、このプログラムは前述のディクショナリを構築する方法の実装のための命令を備えている。
【００８７】
本発明はさらに、この種類のプログラムを目的としており、特に、処理装置、特に符号化/復号化装置を組み入れるコンピュータまたは携帯端末のメモリ、あるいは取り外し可能記憶媒体上に格納されることを意図され、処理装置の読取機構と連携することを意図されたコンピュータプログラム製品を目的としており、このプログラムは前述の圧縮符号化/復号化への適用の実装のための命令を備えている。
【００８８】
本発明のその他の特性および利点は、以下の詳細な説明と、図1aおよび図1b以外の上記で説明されている添付の図面を検討すれば明らかとなろう。
【発明を実施するための最良の形態】
【００８９】
最初に図2aおよび図2bを参照すると、本発明の意義の範囲内でディクショナリDiNの2つの主要特性が示されている。
【００９０】
図2aにおいて、所定の次元Nに対して、それぞれ増加解像度r1、r2、...、riのディクショナリD1N、D2N、...、DiNは、相互の内部に埋め込まれている。したがって、最大解像度riのディクショナリDiNは、以下で明らかになるように、低解像度rj(j<i)のディクショナリDjNを判別可能にしうる。PRと示されるこの第1の特性は、以下で「埋め込み特性」と呼ばれている。
【００９１】
ここで図2bを参照すると、所定の次元Nおよび解像度riの任意のディクショナリDiNは、以下の2つの互いに素な集合の和集合である。
○ 挿入規則{Rm}の有限収集に従って、実数の有限集合Aから取り出された(矢印F2)要素xjの低次元N-1のディクショナリDiN-1をコードベクトルYN-1に挿入することにより構築された(矢印F3)コードベクトルYNから成る第1の集合D'iNであって、挿入規則R'(j,k)は、挿入される要素xj(矢印F1)およびこれらを挿入する方法(例えば構築中のベクトルYNの位置kにおいて)を判別する集合
○ 挿入規則の前述の収集に従ってこの有限集合の要素を低次元のコードベクトルに挿入することよって取得できないベクトルY'から成る第2の集合
【００９２】
【数４】
【００９３】
PDと示されるこの第2の特性は、以下で「制御された拡張による部分合成の特性」と呼ばれている。
【００９４】
図2aおよび図2b、さらに前述の本発明の要約において、解像度および/または次元の索引は、一例として、整数1から始まり所定の整数(i、n、または場合によってはN)までである。プログラミングの技術分野、特にC++言語の当業者は、これらの索引がむしろ0から始まり、状況に応じてi-1、n-1、またはN-1に達しうることを理解するであろう。したがって、以下で説明される図3の例において、到達する最大解像度は0から始まりNj-1である。
【００９５】
以下で説明されるのは、2つの構造化特性PRおよびPDを有するディクショナリを構築する方法であり、特にそのように構築されたこれらのディクショナリを構築するアルゴリズムである。2つの構造化特性によって導かれるリンクは、「GLA」または「SKA」のような一般に使用され上記で説明されている繰り返し構築アルゴリズムを適合することによってそのようなディクショナリを構築するアルゴリズムを開発するために有利に使用される。
【００９６】
一般的に、以下のことが示される。
- 異なる解像度および同じ次元の相関関係にあるディクショナリは、埋め込み特性PRを使用して連続的に構築される
- 補足または変種として、制御された拡張による部分合成の特性PDによって相関関係にある異なる次元のディクショナリが構築される
- したがって、2つの構造化特性PDおよびPRを有する様々な次元および解像度のディクショナリが得られる。
【００９７】
一般的に、所定の次元の解像度を増加することにより埋め込みディクショナリを構築するため(PR)、3つの構築の手法が提案される。
【００９８】
第1の手法は、(最小解像度から最大解像度まで)解像度の増加に従ってディクショナリを構築することを備えている。
【００９９】
第2の手法は逆に、(最大解像度から最小解像度まで)解像度の減少に従ってディクショナリを構築することを備えている。
【０１００】
第3の手法は、最小解像度まで解像度を減少し、最大解像度まで解像度を増加することにより中間解像度のディクショナリに基づいてディクショナリを構築することを備えている。このプロセスは、可変解像度のベクトル量子化器の公称解像度が前述の中間解像度である場合に、特に有利である。
【０１０１】
次元jの、ディクショナリの埋め込みの特性PRは、最終的に以下の式によって伝達される。
D0j⊂D1j⊂...Dij⊂Dji+1...⊂DjNj-1
ここで、
- Njは、次元jの解像度の数(または可変レート符号器において可能なレート)である
- 次元jの解像度の集合は
Rj={r0j,r1j,...,rij,rji+1,...,rjNj-1}
ただし、r0j<r1j<...<rij<rji+1<...<rjNj-1
- Dijは、解像度rijの次元jのディクショナリ
- Tijは、解像度
【０１０２】
【数５】
【０１０３】
のディクショナリのサイズ
【０１０４】
図3は、解像度増加に応じたディクショナリの埋め込みを示している。
【０１０５】
低解像度のディクショナリを再更新しない増加解像度に従った構築のアルゴリズムを示す流れ図は、図5に示されている。
【０１０６】
図5を参照すると、最初にi=0およびループ反復索引iter=0に固定する初期化ステップ51および52に続いて、最低解像度のディクショナリD0jを最初に構築する。次いで、最低解像度のディクショナリD0jが固定され、すぐ上の解像度D1jのディクショナリが、以下で説明される従来の構築アルゴリズムの変種を用いて構築される。方法はその後、最大解像度DjNj-1のディクショナリが構築されるまで繰り返される。
【０１０７】
このようにして、ステップ53において、反復プロセスにより、低解像度ri-1のディクショナリDi-1jに(Tij-Ti-1j)ベクトルを付加することにより形成された、初期ディクショナリDij(0)に基づいてディクショナリDijの構築が試みられる。
【０１０８】
クラスを構築するアルゴリズム54は、従来のアルゴリズムと同じであるが、Tijセントロイドを構築するアルゴリズム55は変更される。具体的には、低解像度のディクショナリに属していない(Tij-Ti-1j)セントロイドは再計算されて更新されるが、低解像度のディクショナリの(Ti-1j)セントロイドは再更新されない。変種は、低解像度のすべてのディクショナリの全歪みが減少するかまたは一定を保つ場合に、低解像度のディクショナリのセントロイドの再更新を可能にする。この場合、低解像度のディクショナリは、それに応じて変更される。
【０１０９】
ループ索引iterはその後、i番目の解像度および次元jに依存している(テスト57)数値Niter(i,j)まで増分される(ステップ56)。望ましい解像度Njに到達すると(テスト58)、この解像度Njでディクショナリを取得し(終了ステップ59)、したがって1からNjに及ぶiに対して解像度riのディクショナリDijの集合を取得する。
【０１１０】
解像度減少に従ってディクショナリを構築するため、最初に最高解像度のディクショナリを構築する。次いで後者が固定されると、後者を特定の基準に従って順序付けられているいくつかの部分集合に区分化する。いくつかの基準は、区分化を順序付ける役割を果たすことができる。例えば、それらの基数、学習シーケンス内のそれらの呼び出し(つまりそれらの量子化領域の基数)、全歪みまたはさらに正確にはその歪みの減少へのそれらの寄与に従って部分集合を順序付けることが可能である。様々な基準を組み合わせ、それぞれの重要度に重み付けすることが明らかに可能である。同様に、ディクショナリの区分化は、単純な区分化(各部分集合に1つの要素)からより緻密な区分化まで、様々な方法で実行することができる。この順序付き区分化は、その順序付きクラスの漸進的和集合による埋め込みディクショナリの構築の基礎にある。
【０１１１】
好ましくは、区分化は、(おそらくはその集合自体と等しい)挿入規則の収集の部分集合に基づいた同一のコードベクトルの拡張に基づいて要素を一緒にグループ化することにより制御された拡張による部分合成の特性PDを基にすることができる。
【０１１２】
様々な手順を交互に入れ替えることによって、複数の反復を行うことが可能であることに留意されたい。例えば、埋め込みディクショナリは、解像度増加の手順に従って構築され、次いで解像度減少の手順が適用される。上記の2つの方法を組み合わせることにより、解像度により埋め込まれたディクショナリは、中間解像度riのディクショナリに基づいて構築される。したがって、このi番めのディクショナリは、最初に構築される。次いで、このディクショナリに基づいて、解像度減少による第2の方法を用いて低解像度のディクショナリが構築され、解像度増加による第1の方法を用いて高解像度のディクショナリが構築される。
【０１１３】
一般に、制御された拡張による部分合成による(特性PD)様々な次元のディクショナリを構築するための3つの手法も提案される。
【０１１４】
第1の手法は、次元を増加することである。もう1つの手法は、次元を減少することである。最終的に、最後の手法は、中間次元のディクショナリの構築から始まり、次元の連続的な増加および減少により高次元および低次元のディクショナリを構築することである。制御された拡張による部分合成は、以下で説明される実数および挿入規則の収集の有限集合を判別する手順の微調整をもたらした。ここで、好ましくは、「拡張された」要素の比率(ディクショナリの基数に関して第1の集合の要素の数)が次元と共に増加し、それにより、次元と共に増加する第2の集合の格納のコストを軽減できるようにすることが簡単に示されている。この比率は、アプリケーションの複雑な制約(メモリ/計算処理能力)により先験的に固定されていても、あるいは「自由」のままであってもよい。後者の場合、有利なことに構築アルゴリズムは、以下に示されるように、制御された拡張によって得られた要素から成る第1の集合の要素にとって好都合に働く。
【０１１５】
したがって、制御された拡張による部分合成の第2の特性PDは、最終的に以下の式によって伝達される。
【０１１６】
【数６】
【０１１７】
ここで、
- D'jiは、挿入規則{Rm}の収集に従って、Rの有限集合Aから取り出された要素を低次元のディクショナリのコードベクトルに挿入することによって得られるDijのコードベクトルの集合であり、
-
【０１１８】
【数７】
【０１１９】
は、Djiのその補集合、つまり挿入規則{Rm}の収集に従って、Aの要素を低次元のコードベクトルに挿入することによって得ることのできないDijのコードベクトルの集合である。
【０１２０】
以下で説明されるのは、第2の特性PDを検証するための挿入規則の例である。
【０１２１】
最初に、基本挿入規則の収集が定義される。各基本規則は、ベクトルの所定の位置において成分として実数Aの有限集合の唯一の要素を挿入することである。各基本規則は、2つの正整数の組によって与えられ、一方の整数は、有限集合内の要素の位を示し、もう一方の整数は、挿入の位置を示す。基本規則のこの収集に基づいて、成分を挿入するためのさらに詳細な規則を作成することが可能である。
【０１２２】
もちろん、純粋に可逆的に、低次元N-nに達するように所定の次元Nの有限集合の1つまたは複数の要素を削除することを備える削除規則を定義することができる。
【０１２３】
挿入規則を定義するため、以下のように指定する。
- Naは、Aの基数であり、aiは、そのi番目の要素である。A={a0,a1,...,ai,..,aNa-1},
- R'(im,pm)は、位置pmにおいてaimを挿入することを備える基本挿入規則である。
【０１２４】
したがって、最大次元がjmaxである場合、可能な基本規則の数はNa*jmaxである。例えば、Na=2およびjmax=3の場合、全部で6つの基本規則が数えられる。
R'(0,0):位置0においてa0を挿入
R'(1,0):位置0においてa1を挿入
R'(0,1):位置1においてa0を挿入
R'(1,1):位置1においてa1を挿入
R'(0,2):位置2においてa0を挿入
R'(1,2):位置2においてa1を挿入
【０１２５】
規則R'(0,0)およびR'(0,1)の合成は、位置0および1においてa0を挿入するという規則をもたらす。これは、したがって次元jのコードベクトルに基づいて次元j+2のコードベクトルを取得するできるようにする。
【０１２６】
規則R'(1,0)およびR'(0,2)の合成は、位置0においてa1を、位置2においてa0を挿入するという規則をもたらす。これは、したがって次元jのコードベクトルに基づいて次元j+2のコードベクトルを取得することができるようにする。
【０１２７】
さらに一般的に、n基本規則R'(im,pm)の合成に対して(m=0からn-1)、R(n,{(im,pm)}m=0,n=1)を定義するが、これは次元jのコードベクトルに基づいて次元j+nのコードベクトルを取得することができるようにする。imは必ずしも異なっている必要はなく、対照的にn位置pmが相異なることに留意されたい。好ましくは、位置pmは、例えば以下のような昇順に配置される。すなわち、
Po<P1...<pm...<pn-1
【０１２８】
図4は、低次元のディクショナリのコードベクトルおよび挿入規則に基づくディクショナリのコードベクトルの合成を示している。
【０１２９】
2つの互いに素な集合の和集合である様々な次元のディクショナリを構築するためのいくつかの実施形態も提供され、第1の集合は、挿入規則収集に従って実数の有限集合から取り出された要素を低次元のディクショナリのコードベクトルで挿入することにより構築されたコードベクトルから成り、第2の集合は、挿入規則のこの収集に従って実数のこの有限集合の要素を低次元のコードベクトルで挿入することにより得ることができないベクトルから成る。
【０１３０】
第1の集合は、実数の有限集合(つまりその基数およびその値)とさらに挿入規則の収集の判別を必要とする。
【０１３１】
この有限集合の構築と挿入規則の収集の形成とが以下のように実行される。
- 「演繹的に」:有限集合および挿入規則の収集は、ディクショナリを構築する前に判別される。この選択は、情報源の統計の分析に基づいて、例えば学習シーケンスによって量子化、モデル化されることが好ましい。例えば、有限集合の選択は、情報源の単一次元の確率密度(またはそのヒストグラム)を基にすることができる。
- あるいは「帰納的に」:最初に、制御された拡張による部分合成の規則に従う必要性を課さないすべての次元の解像度によって埋め込まれたディクショナリを構築する。有限集合および挿入規則の収集の選択は、これらの「初期」ディクショナリの統計の検討によって行われる。
【０１３２】
2つの解決策「演繹法」または「帰納法」は、連続および/または組み合わせて使用することができる。例えば、第1の集合および挿入規則の第1の収集は、学習シーケンスの分析によって選択され、次いで、ディクショナリの最初の構築後、これらのディクショナリの分析は、集合Aおよび/または挿入規則の収集の全体的または部分的更新を導くことができる。
【０１３３】
さらに、有限集合および/または挿入規則の収集が、次元に依存する場合も、あるいは依存しない場合もあることに留意されたい。次に、次元の各組(j,j')に固有の収集および/または集合、あるいは次元の相異により固有の収集および/または集合を判別することも、またグローバルな集合を判別することも可能である。繰り返すが、選択は、先験的に、または学習シーケンスおよび/またはディクショナリの統計的分析の後に行われる。
【０１３４】
解像度増加に従ってディクショナリを構築するため、前述のような、ベクトル量子化設計の従来の手順によって最低次元のディクショナリを構築する。次いで、このディクショナリが構築され、すぐ上の次元のディクショナリが、従来の構築アルゴリズムの変種を用いて構築される。低次元のディクショナリに基づいて、すべての可能な初期コードベクトルが、挿入規則を適用することによって作成され、このディクショナリには場合により「自由な」コードベクトル(つまり拡張によっては得られないもの)が補足されることもある。この初期ディクショナリのサイズは、望ましいサイズよりも大きくなりうることに留意されたい。初期ディクショナリに基づいて、ベクトル量子化器を構築する反復アルゴリズムの変種が適用される。クラスは、学習シーケンスの量子化によって構築され、セントロイドは、第1の集合のコードベクトルの制御された拡張の制約に従って更新される。第1の集合のこれらのコードベクトルに対して、挿入によって得られた成分を再計算しないことも、あるいは挿入規則によって得られた成分を戻すように、すべての成分を再計算してこのように得られたコードベクトルを変更することもできる。従ってディクショナリのサイズが望ましいサイズよりも大きい場合、空クラスを除去する。アルゴリズムの最後で、ディクショナリのサイズが望ましい解像度よりも大きい場合、ディクショナリの要素を分類する手順は、第1のコードベクトルのみを保持するように適用される。反復アルゴリズムは、場合によっては再実行される。次いで、高次元のディクショナリの構築に移り、初期ディクショナリは、2つの最小次元の2つのディクショナリに基づいて制御された拡張により構築され、「自由な」コードベクトルが補足されて、ベクトル量子化器を構築する反復アルゴリズムの変種が適用される。次に方法は、最大サイズのディクショナリが構築されるまで繰り返される。
【０１３５】
変種として、減少解像度に従ってディクショナリを構築するため、最初に最大次元のディクショナリを構築する。次に、後者が固定されると、低次元の可能なコードベクトルが抽出される。有利なことに、抽出手順は、これらのコードベクトルの成分としてAの要素を取り出すように、高次元のコードベクトルを変更することによって容易になる。
【０１３６】
補足的な変種において、いくつかの反復が、一方では増加次元に従って、またはもう一方では減少次元に従って、2つの構築を交互に入れ替えることによって有利に実行される。
【０１３７】
制御された拡張の手順を容易にするため、本発明はさらに、コードベクトルの成分の変換を実行することができる。模範的な変換は、高解像度におけるスカラー量子化である。低次元の「ディクショナリ」を構築することは、たとえそれらの次元がベクトル量子化によって直接には使用されない場合であっても、有益である。例えば、スカラー量子化が使用されない場合でも、次元1で始めることが可能である。同様に、中間次元のディクショナリを構築することが有利な場合もある。これらの「ディクショナリ」は、格納および計算の複雑さを軽減するために、制御された拡張の手順によってさらに一層有利に使用される。
【０１３８】
さらに、解像度による埋め込みにより(PR)、ディクショナリを構築するアルゴリズムを、制御された拡張による部分合成によって(PD)構築するアルゴリズムと公正に組み合わせることによって、いくつかの構築方法が開発されうることが示される。アルゴリズムが反復型である場合、様々な技法を交互に入れ替えることができることに留意されたい。例えば、最小次元の最大解像度のディクショナリを構築することによって始め、このディクショナリから解像度減少(特性PR)によって埋め込まれたディクショナリを推定し、次いで特性PDに基づいてすぐ上の次元の最大解像度のディクショナリを構築し、この次元に対して、解像度により埋め込まれたディクショナリを構築し、最大次元のディクショナリ(解像度により埋め込み)が得られるまで繰り返す。
【０１３９】
以下で説明される実施形態において、次元増加および解像度減少に従ってディクショナリの集合{Dji}i=0,...,Nj-1,j=jmin,...,jmaxを構築するためにディクショナリ構築の技法を組み合わせる優先構築が使用される。
【０１４０】
以下で説明されるのは、本発明の意義の範囲内でディクショナリを使用する、デジタル信号(オーディオ、ビデオなど)の圧縮符号化/復号化であり、特にディクショナリの構造(埋め込みおよび制御された拡張による部分合成)を利用する符号化および復号化アルゴリズムである。一般に、符号器および/または復号器におけるメモリ/計算間の妥協の最適化は、アプリケーションの制約に従って取り組まれることが理解されよう。
【０１４１】
一例として、以下で考察されるのは、16kHzでサンプリングされるデジタルオーディオ信号(広帯域)を符号化するために使用される「TDAC符号器」と呼ばれるオーディオ符号器である。この符号器は、様々なレートで動作することができる変換ベースの符号器である。特に、レートは、通信の確立前に固定されるか、または通信の過程でフレームによって異なっていてもよい。
【０１４２】
図6は、このTDAC符号器のブロック図を示している。7kHzで制限され、16kHzでサンプリングされたオーディオ信号x(n)帯域は、320サンプル(20ms)のフレームに分割される。変形離散コサイン変換61は、50%のオーバーラップで640サンプルの入力信号のブロックに適用される(つまり、20msごとのMDCT分析のリフレッシュ)。得られたスペクトルy(k)は、最後の31係数をゼロ化することにより7225Hzに制限される(最初の289係数のみが0と異なる)。マスキングカーブは、マスキングされた係数のゼロ化を行うマスキングモジュール62によって判別される。スペクトルは、不等な幅の32の帯域に分割される。マスキングされた帯域がある場合、それらは信号x(n)の変換された係数の関数として判別される。スペクトルの帯域ごとに、MDCT係数のエネルギーが計算される(基準化因数と呼ばれる)。32の基準化因数は、その後量子化され、符号化されてフレームで送信される信号のスペクトル包絡線を構成する(ブロック63)。この量子化およびこの符号化では、ハフマン符号化を使用する。次いで、可変レートでのスペクトル包絡線の量子化後に残ったビットの可変数が計算される。これらのビットは、スペクトルのMDCT係数のベクトル量子化65に分配される。量子化解除スペクトル包絡線は、帯域的なマスキングしきい値のセットを計算するのに役立ち、このマスキングカーブは、ビットの動的な割り振り64を判別する。帯域ごとおよび量子化スペクトル包絡線に基づくこのマスキングカーブの計算は、バイナリ割り振りに関連する補助情報の送信を回避する。具体的には、復号器は、符号器と同様の方法でビットの動的割り振りを計算する。MDCT係数は、それらの帯域の量子化解除基準化因数によって正規化され、次いで可変次数および可変レートのベクトル量子化器によって量子化される。最後に、スペクトル包絡線およびこれらの符号化されてフレームで送信された帯域正規化係数に関する情報の多重化66によってバイナリ列が構築される。図6における参照67および68はそれぞれ、有声または無声信号x(n)の検出、およびトーンの検出(トーン周波数の判別)の既知のステップ自体に対応することが示されている。
【０１４３】
以下で説明されるのは、TDAC符号器におけるMDCT係数の不等な幅の帯域に基づく可変レートのベクトル量子化器である。帯域的に正規化されたMDCT係数の量子化では、特に、本発明により構築されたディクショナリを使用する。不等な幅の帯域への分割は、実際に、様々な次元のベクトルをもたらす。使用された帯域分割を与える図7aの配列図はさらに、結果として生じた係数のベクトルの次元、つまり第3列に示されるように、係数の数を示している。
【０１４４】
スペクトル包絡線のハフマン符号化後に残ったビットの可変数は、様々な帯域に動的に割り振られる。図7bの配列図は、1から15の範囲にわたる次元jについて、解像度Njの数および次元jの帯域当たりのレートj*Rj(ゆえに帯域当たりの解像度の値)の集合を示している。制御された拡張による部分合成の構造化特性を有利に利用するため、ベクトル量子化器が次元1、2、6、11で構築されたにもかかわらず、これらは任意の帯域幅には対応しないが、その要素はより大きい次元のコードベクトルの作成に役立つことに留意されたい。さらに、大きい次元であっても解像度の細分性が細密であることに留意されたい。
【０１４５】
モジュール62におけるマスキングされた係数のゼロ化は、正規化MDCT係数の分析中に、開始集合A={0}としておよび挿入規則の収集として、基本挿入規則のすべての可能な合成の選択を導く。これは、任意の位置においてゼロを挿入することになる。
【０１４６】
しかし、より細密な分析は、すべての置換およびすべての符号が許可されるタイプIIの、正規化置換コードの和集合で形成されるディクショナリを使用することにより、ディクショナリに追加の構造的制約を課す。タイプIIの各置換コードに対して、最大ベクトルは、辞書学的な意味で、絶対リーダーと呼ばれ、成分の絶対値を降順に順序付けることによって得られる。ディクショナリの構築は、それらの正規化絶対リーダーを判別することになる。制御された拡張をこれらの絶対リーダーに適用することは、最後の成分としてゼロをこれらに挿入することである。
【０１４７】
さらに、歪み基準が固定される。好ましくは、選択される歪み基準はここで、ユークリッド距離である。ディクショナリが正規化されると、量子化される入力ベクトルとのユークリッド距離を最小化するコードベクトルの検索は、結果として、この入力ベクトルとのスカラー積を最大化するコードベクトルを検索することになる。さらに、ディクショナリが置換コードの和集合であれば、入力ベクトルとのスカラー積を最大化するコードベクトルの検索は、結果として、この入力ベクトルの絶対リーダーとのスカラー積を最大化するコードベクトル(降順にランク付けるようにその成分の絶対値を置換することによっても得られる)をディクショナリの絶対リーダーの中で検索することになる。
【０１４８】
以下で定義されているのは、本発明の意義の範囲内の、ベクトル量子化器の設計のための学習シーケンスである。前述のように、量子化器の設計のための学習シーケンスを判別することが好ましい。帯域の基準化因数によって正規化された289のMDCT係数のフレームから成る長いシーケンスは、最初に、広帯域オーディオ信号の多数のサンプルに基づいて取得される。次に、係数の各正規化ベクトルに対して、その絶対リーダーが推定される。様々な次元の絶対リーダーの集合に基づいて、多次元学習シーケンスの2つのカテゴリS0およびS1が作成される。
- S0={S0j}j∈[1,15]、S0jは、j非ゼロ係数を有する絶対リーダーの最初のj成分によって形成されるすべてのベクトルの集合である。したがってS0jは、ゼロ係数をまったく有していない次元jの絶対リーダー、単一のゼロ係数を有する次元j+1の絶対リーダー、2つのゼロ係数を有する次元j+2の絶対リーダー、...15-jのゼロ係数を有する次元15の絶対リーダーから成る。
- S1={S1j}j∈[3,4,5,7,8,9,10,12,13,14,15]、S1jは、j係数を有する帯域のすべての絶対リーダーの集合である。
【０１４９】
例えば、係数(0.;0.6;0.;0.;0.8)の正規化ベクトルに基づいて、シーケンスS15に属するその絶対リーダー(0.8;0.6;0.;0.;0.)およびその絶対リーダーの最初の2つの非ゼロ成分によって形成されるS02の要素(0.8;0.6)を推定する。
【０１５０】
第1のシーケンスのカテゴリは、好ましくは
【０１５１】
【数８】
【０１５２】
のリーダーの初期ディクショナリを判別するために使用される。第2のカテゴリは、好ましくは2つの構造化特性を有する多次元および多解像度のディクショナリを構築するために使用される。
【０１５３】
シーケンスの第1のカテゴリS0に基づいて、いわゆる「k平均アルゴリズム」のような従来のアルゴリズムをシーケンスS0jに適用することにより、各次元j(jは1から15の範囲)の正規化絶対リーダーの最初のディクショナリを取得する。正の実数成分を持つこれらのリーダーは、第1の成分(つまり最大の成分)に関して、成分をあらかじめ決められたしきい値よりも低く抑えることによって変更される。このいわゆる「センタークリッピング」手順は、有利なことに、ゼロを取り出して、低次元のゼロ成分を持たない絶対リーダーを抽出できるようにする。制御された拡張にさらに好都合に働くように、これらの抽出されたリーダーの成分の変換が適用される。この目的のため、整数再構築レベルで間隔1の均一スカラー量子化が後に続くその最小非ゼロ成分によって各リーダーの正規化を使用する(これは各リーダーの成分を最も近い整数に四捨五入することになる)。この変換では、修正正規化因数を距離計算に導入することにより整数の形で絶対リーダーを格納することができるので、さらにメモリにかなりの量の削減をもたらす。取得された、あるいは様々なシーケンスS0jに基づく異なる実数リーダーは、同一の整数リーダーに変換できることに留意されたい。次いで、可能な冗長を除去するため、およびすべての絶対リーダーの集合
【０１５４】
【数９】
【０１５５】
を非ゼロ整数成分で形成するための手順が提供される。ここで、L'0jは、次元jのこれらのリーダーから成る部分集合である。L'0を構築するこの技法は、次元減少に従って、制御された拡張による部分的作成によってディクショナリを構築する技法からその発想を得ている。さらに、事前に行われた集合Aの選択は、L'0のすべてのリーダーが最後の成分として少なくとも1つの「1」を有しているので、そこに要素「1」を付加するように、事後的に検討できることにも留意されたい。
【０１５６】
集合L'0は、埋め込みPRと制御された拡張による部分合成PDとの、2つの構造化特性を所有する、複数の次元および解像度によるベクトル量子化器の設計のためのリーダーの初期ディクショナリの構成の基礎をなす。シーケンスS1に基づいて、これらの量子化器を構築するアルゴリズムは、次元増加および解像度減少を通じて進行する。
【０１５７】
次元jの場合、リーダーの初期ディクショナリL'1jは、L'0jのすべてのリーダーと、集合L'0jのリーダーに(j-j')ゼロを挿入することにより低次元j'(j'<j)のリーダーの制御された拡張によって得られるすべてのリーダーとにより形成される。例えば次元3において、リーダーのディクショナリは、L'03のリーダーが補足されたL'01={(1)},L'02={(11),(21),(31),(41),(51),(91)}に基づく制御された拡張によって構成される。
【０１５８】
各次元jに対して、L'1jによって特徴付けられる置換コードの和集合は、おそらくは望ましい最大解像度よりも大きい、高解像度のディクショナリを構成する。したがって、これらの置換コードは、このディクショナリの自然区分化を実行し、この区分の各クラスは、そのリーダーによって代表される置換コードである。次に、この区分のクラスに対応する最近傍の領域の構築は、シーケンスS1の量子化によって実行される。区分化は、置換コードの基数の増加に従って順序付けられる。置換コードの基数の等式の場合、制御された拡張によって得られたリーダーのコードは、前述のように、L'0jのリーダーのコードに関して好都合である。同じ集合(
【０１５９】
【数１０】
【０１６０】
または
【０１６１】
【数１１】
【０１６２】
のいずれか)に属している2つのクラスの基数の等式の場合、クラスは、それらの量子化領域の基数と全歪みの減少へのそれらの寄与とを組み合わせた基準に従って順序付けられる。そのように順序付けられた置換コードの基数の集合体は、ベクトル当たりの対応するレートと同様に、置換コードごとに計算される。このように順序付けられたL'1jのリーダーの集合をL1jで表す。符号化された索引を、結合したバイナリ列として配置する手順を回避するため、整数の解像度のみを使用するように選択する。
【０１６３】
したがって、図7cの配列を参照すると、解像度により埋め込まれた多解像度ディクショナリは、基数の集合体のレートがすぐ上の整数に最近傍である異なる解像度ごとの最後の置換コードとして選択することによって構成される。L1jによって特徴付けられるディクショナリの解像度が、望ましい最大解像度よりも高い場合、最後の未使用の置換コードは、除去される。DjNj-1のリーダーの最終順序付き集合をLj(⊆L'j)で表す。次元の反復の最後に、L'0の特定のリーダーが{Li}j∈{3,4,5,7,8,9,10,12,13,14,15}のリーダーを構成するために使用されない場合、集合L'0は、それらを除去することにより更新される。この集合を
【０１６４】
【数１２】
【０１６５】
と記す。
【０１６６】
図7cから7eの配列図は、埋め込み特性と制御された拡張による部分合成の特性とによってもたらされるメモリの節約を示している。図7cの配列図は、様々な次元の多解像度によるベクトル量子化器を比較している。第1の量子化器は、単に置換コードの和集合として構築され、第2の量子化器は、その上に解像度による埋め込みの特性を備えている。
【０１６７】
図7cにおいて、
- j:次元
- Nj:次元jの解像度の数
-
【０１６８】
【数１３】
【０１６９】
:ディクショナリDjiのリーダーの数
-
【０１７０】
【数１４】
【０１７１】
:ディクショナリDjnj-1のリーダーの数
-
【０１７２】
【数１５】
【０１７３】
:埋め込み特性のない次元jですべてのディクショナリのリーダーを格納するために必要なメモリ(ワード数単位)
-
【０１７４】
【数１６】
【０１７５】
:埋め込み特性のある次元jですべてのディクショナリのリーダーを格納するために必要なメモリ
【０１７６】
図7dの配列図は、多次元に使用されるこれらの後者の量子化器を、制御された拡張による部分合成の構造化特性も有する量子化器と比較している。
【０１７７】
図7dにおいて、
- j:次元
-
【０１７８】
【数１７】
【０１７９】
:ディクショナリDjnj-1のリーダーの数
-
【０１８０】
【数１８】
【０１８１】
:次元1からjの最大解像度のディクショナリのリーダーの数の和
-
【０１８２】
【数１９】
【０１８３】
:制御された拡張による部分合成の特性のないこれらのリーダーを格納するために必要なメモリ
- Lj:集合L0jのリーダーの数
-
【０１８４】
【数２０】
【０１８５】
:1次元からjのそれらの和
-
【０１８６】
【数２１】
【０１８７】
:制御された拡張による部分合成の特性のある次元1からjのすべてのディクショナリのリーダーを格納するために必要なメモリ
【０１８８】
図7eの配列図は、多解像度および次元によるベクトル量子化器を比較している。第1の量子化器は、単に置換コードの和集合として構築され、第2の量子化器は、その上に解像度による埋め込みと制御された拡張による部分合成との構造化特性を備えている。
【０１８９】
図7eにおいて、
- j:次元
- Nj:次元jの解像度の数
【０１９０】
-
【０１９１】
【数２２】
【０１９２】
:埋め込みの特性または制御された拡張による部分合成の特性のないNj解像度に対して格納される次元jのリーダーの数
【０１９３】
-
【０１９４】
【数２３】
【０１９５】
:これらの2つの特性のない次元jですべてのディクショナリのこれらのリーダーを格納するために必要なメモリ(ワード数単位)
【０１９６】
-
【０１９７】
【数２４】
【０１９８】
:これらの2つの特性のない次元1からjのすべてのディクショナリのリーダーを格納するために必要なメモリ(ワード数単位)
Lj:集合L0jのリーダーの数
【０１９９】
-
【０２００】
【数２５】
【０２０１】
:1次元からjのそれらの和
【０２０２】
-
【０２０３】
【数２６】
【０２０４】
:埋め込みと制御された拡張による部分合成との2つの特性のある次元1からjのすべてのディクショナリのリーダーを格納するために必要なメモリ
【０２０５】
3つの配列図において、最後の列は、メモリ減少係数の有意性を示している。埋め込み特性のみでは、次元3において3、次元7において5、次元15において7よりも大きい係数によってメモリを減少できるようにする。埋め込み特性により、次元jの解像度の集合に対してDjiのすべてのリーダーを格納するのではなく、DjNj-1(Ljのリーダー)のリーダーのみを格納する。図7dの配列図の最後の列に示されているように、制御された拡張による部分合成の追加により、メモリをさらに減少できるようになる。この特性によりもたらされるさらなる節約は、以下のようになる。
- 次元4において1.5倍
- 次元8において3倍
- 次元15において7倍
【０２０６】
図7eにより示されているように、単に置換コードの和集合として構築された量子化器に関して、その上に解像度による埋め込みと制御された拡張による部分合成との2つの構造化特性を備えている量子化器の使用により、次元3において4分の1、次元7において13分の1、次元11を超える次元については35分の1以上メモリを減少させることができる。
【０２０７】
制御された拡張による部分合成特性により、L0のリーダーのみが格納される必要があり、{Lj}のリーダーは、Ljのリーダーの索引からL0のリーダーの索引への対応するテーブルから取り出される。
【０２０８】
ここで、ベクトル量子化器を効果的に実装する方法について説明する。
【０２０９】
次元jおよび解像度riのベクトル量子化器を実装するには、以下の3つの問題を解決することが必要である。
- Djiにおける入力ベクトルの最近傍の検索
- Djiのコードベクトルの索引の検索
- さらに相互の、その索引に基づくDjiのコードベクトルの検索
【０２１０】
索引付けに関する限り、ディクショナリのコードベクトル、タイプIIの置換コードの和集合を索引付けするいくつかの既知の方法があることが示されている。実施形態において採用された番号付けは、Gosset格子の球形コードに索引付けをするために使用された番号付けからその発想を得ている。
【０２１１】
任意の次元j(j∈{3,4,5,7,8,9,10,12,13,14,15})に対して、DjNj-1の各コードベクトルは、その置換コード、その符号の組合せを与えるバイナリ索引、およびその置換コードのその位のオフセット特性によって索引付けされる。置換コードのオフセットは、DjNj-1においてそれに先行する置換コードの基数の集合体である。置換に番号付けする定式の中で、いわゆるSchalkwijk式を選択した。
【０２１２】
DjNj-1のコードベクトルのこの従来の番号付けに加え、Ljのリーダーの索引からL0のリーダーの索引への対応テーブルを使用する。L0のリーダーが格納されると、L0の索引付けの大きな自由がもたらされる。例えば、次元を増加させることにより、非ゼロ整数成分を持つこれらのリーダーを分類することができる。Ljのリーダーxjの各索引mjには、L0のリーダーxj'の索引lmが関連付けられる。この索引lmに基づいて、リーダーxj'の次元j'およびリーダー自体を取り出す。次いでリーダーxjは、xj'の最後の成分として(j-j')ゼロを挿入することにより取り出される。
【０２１３】
図7fの配列図は、L0の最初の23リーダーを示している。図7gの配列図は、各リーダーx3について、これを得るために拡張された次元j'(j'≦j)のL0j'のリーダーxj'を示すことにより、次元3のディクショナリの置換コードのリーダーを示している。付随的に、j=j'であれば、xj'=x3であることが指摘される。
【０２１４】
図7fにおいて、
- l:L0におけるリーダーの索引(516の中から)
- j:その次元
- lj:L0jのリーダーのその索引
【０２１５】
図7gにおいて、
- m3:D3N3の23リーダーの中のリーダーx3の索引
- i:リーダーが属する最小解像度のディクショナリの索引(つまり
【０２１６】
【数２７】
【０２１７】
)
- jri:このディクショナリD3iのベクトル当たりのレート
- j':L0のリーダーxj'の次元(非ゼロ成分の数)
- lm:L0の516リーダーの中からのxj'の索引
【０２１８】
以下で説明されているのは、一般の場合に適した符号化および復号化アルゴリズムであり、追加の構造的制約(置換コードの和集合)が追加された特に有利な事例を後に検討することになる。
【０２１９】
最近傍検索アルゴリズムの複雑さを軽減することを可能にする制御された拡張の特性により、特に導びかれたディクショナリ構造を優先的に使用することが、最初に示されている。特に、同じ挿入規則を有するコードベクトルを一緒にグループ化することができる。例えば以下で詳細に説明されるユークリッド距離の歪み基準の場合、ディクショナリDjiの次元jのLコードベクトル{xjl,l=0,1,...,L-1}が、ディクショナリDi'j-nの次元j-nのLコードベクトルxlj-nに基づいて、同じ挿入規則R(n,{(im,pm)}m=0,n-1)によって取得される場合、入力ベクトルyからのコードベクトルxjlのL距離の計算:
【０２２０】
【数２８】
【０２２１】
は、最初に項
【０２２２】
【数２９】
【０２２３】
を計算し、次にn成分ypmをyに高めることによって得られる次元(j-n)のベクトルy'からコードベクトルxlj-nのL距離を計算:
【０２２４】
【数３０】
【０２２５】
することにより、迅速化することができる。
【０２２６】
前述のように、各次元に対して、格納される必要があるのは最大解像度のディクショナリの一部だけであり、他のコードベクトルは、低次元の最大解像度のディクショナリから取り出された要素と挿入規則とに基づいて推定される。
【０２２７】
これ以降、本発明によるディクショナリ作成方法の使用における圧縮符号化/復号化の詳細な模範的実施形態が示される。
【０２２８】
検討されるすべての次元jについて、すべてのディクショナリの集合{Djl}i=1,...,Njを格納するのではなく、
【０２２９】
【数３１】
【０２３０】
と対応テーブルのみを格納することが、最初に示されている。これらのテーブルは、その索引に基づいてDjNjのコードベクトルを再構築できるようにする。前述のように、これらのテーブルを公式化し、それらを格納するいくつかの方法がある。例えば、検討されるすべての次元jについて、(DjNjのコードベクトルxjの)索引mjごとに、j'、m'、およびlrという3つのスカラー整数値を表にすることができる。ここで、lrは
【０２３１】
【数３２】
【０２３２】
の集合の索引m'の要素に適用される制御された拡張による部分合成によってxjを再構築できるようにする挿入規則の数である。これで対応テーブルは、
【０２３３】
【数３３】
【０２３４】
ワードを格納する必要があるだけである(Tijは、ディクショナリDijのサイズであることが思い起こされる)。多解像度および次元によるベクトル量子化器のディクショナリに適切な格納に関する限り、解像度による埋め込みと拡張による部分合成との2つの構造化特性を備えていないベクトル量子化器の場合は
【０２３５】
【数３４】
【０２３６】
ワードが必要とされるが、これらの2つの構造化特性を備えるベクトル量子化器のディクショナリの格納には、1つの
【０２３７】
【数３５】
【０２３８】
ワードしか必要とされない。つまり、集合
【０２３９】
【数３６】
【０２４０】
のサイズは
【０２４１】
【数３７】
【０２４２】
である。しかし、一般的には、当然ながら集合
【０２４３】
【数３８】
【０２４４】
に対して集合D'jNjが支持されるので、
【０２４５】
【数３９】
【０２４６】
はTjNjよりもはるかに小さい。記憶域の節約についてのいくつかの数値的な例は、後に説明される実施形態において示される。
【０２４７】
入力ベクトルy=(y0,...,yk,...,yj-1)のDjiの最近傍xjを検索することを備える符号化アルゴリズムは、優先的に以下のステップを備えている。
【０２４８】
ステップCO0)は、
すべての索引mj∈[0,Tji[に対して
dmin=VALMAX;mmin=-1;mj=0
である初期化ステップを備えている。
【０２４９】
次のステップCO1)は、索引mjのコードベクトルxjの再構築を備え、優先的に以下のように実行される。
a)DjNjに関連付けられている対応テーブルの3つの索引j'、m'、およびlrの読み取り
b)次元j'および索引m'のベクトルxjの集合
【０２５０】
【数４０】
【０２５１】
の読み込み
c)索引lrの挿入の規則に従って制御された拡張による部分合成の特性のxj'への適用によるコードベクトルxjの再構成
【０２５２】
ステップCO2)は、選択された歪み基準に従ってyとxjとの間の距離d(y,xj)を計算することを備えている。
【０２５３】
次のステップCO3)およびCO4)は、操作CO1)およびCO2)を繰り返して、入力ベクトルからの距離が最小であるベクトルの索引を識別することを備えている。したがって、
* d(y,xj)<dminであればdmin=d(y,xj)かつmmin=mj
* 次にmjを増分する:mj=mj+1
* 終了テストが行われる:
mj<TjiであればステップCO1)に進む
それ以外の場合:停止
【０２５４】
終了ステップCO5)において、入力ベクトルyとの最小距離dminに対応して索引mminが識別されたコードベクトルを装った入力ベクトルyの最近傍であるコードベクトルを判別する。
【０２５５】
したがって、アルゴリズムはステップCO5)に進む:
* 終了
Djiにおけるyの最近傍xjは、索引mminのコードベクトルである。
【０２５６】
Djiのコードベクトルをその索引に基づいて検索することを備える復号化アルゴリズムは、符号化アルゴリズムのステップCO1)によって示されている。特に、復号化は、復号化される索引にはかかわりなく、ステップCO1)のコードベクトルxj(操作c)の完全な再構成を伴うことが示されている。
【０２５７】
一方、符号化では、この再構成は部分的であってもよい。具体的には、ステップCO2)の距離計算における歪み基準を以下の2つの項に分解できる場合、これは省略できることもある。
- 挿入規則の索引にのみ依存しているもの
- もう1つはコードベクトルxj'
【０２５８】
例えば、ユークリッド距離の歪み基準の場合、初期化ステップCO0)において、Djiに使用される索引lrの各挿入規則に対し、距離
【０２５９】
【数４１】
【０２６０】
を事前計算することが可能である(索引lrの挿入規則が位置Pmをめざして(mは0からj-j'-1の範囲)j-j'成分aimを挿入することを備える場合)。ステップCO2)のyとベクトルxj(j',m',lr)との間の距離の計算は、距離
【０２６１】
【数４２】
【０２６２】
を計算することになる。ここで、
- xj'は、ステップCO1)の操作b)において得られたベクトルであり、
- y'は、j-j'成分ypmをyに高めることにより得られる次元j'のベクトルであり、
- 距離d(y,xj)は、単純な合計d(y,xj)=dlr+d(y',xj')によって得られる。
【０２６３】
これは、上記で、符号化プロセス中に、(完全に再構築されたコードベクトルxjの次元となるであろう)次元jよりも低い次元j'のコードベクトルxj'の再構築を「部分的」と定義した理由である。
【０２６４】
さらに、ベクトルxj'が(様々な挿入規則により)Dijのコードベクトルの合成に数回介入する場合、初期化ステップにおいて項d(y',xj')を事前計算することもできる。したがって、格納(一時)/符号化の複雑さの間の妥協は、アプリケーションの要件に従って調整することができる。
【０２６５】
同様に、索引付けの格納/複雑さの間の妥協も、アプリケーションの要件に合わせて調整することが得きる。
【０２６６】
符号化に関しては、前述のような置換コードの和集合の追加の制約の場合、次元8の通常のGosset格子の球形コードに対して、最近傍検索アルゴリズムは、タイプIIの置換コードの和集合により、これらのディクショナリに単純化することによって容易に一般化する。
【０２６７】
そのような検索アルゴリズムは、特に以下の文献において説明されている。
- 「Algorithme de Quantification Vectorielle Algebrique Spherique par le Reseau de Gosset E8」、C.Lamblin、J.P.Adoul、Annales Des Telecommunications、no 3-4、1988年["Spherical algebraic vector quantization algorithm by the E8 Gosset lattice"]
【０２６８】
第1の単純化は、奇数成分を持つGosset格子の置換コードによって所有されないタイプIIの置換コードの符号の「自由さ」によってもたらされる。第2の単純化は、スカラー積の計算のための各リーダーの非ゼロ成分の数の検討によってもたらされる。これは、符号化アルゴリズムによって制御された拡張による部分合成の特性により生じた構造の利用を示している。最後の変更は、L0のリーダーの整数形式での格納を考慮し、それにより、厳密に正整数成分を持つこれらのリーダーのユークリッドのノルムの逆数と等しい修正係数のスカラー積の計算への導入に至る。
【０２６９】
以下に説明されるのは、ディクショナリDijの次元jの入力ベクトルyの最近傍の検索が、本発明の2つの構造化特性に加えて、置換コードの和集合として前述の構造を使用する実施形態である。
【０２７０】
3つの追加のステップが、グローバルに提供される。
- 符号化されるベクトルの絶対リーダー
【０２７１】
【数４３】
【０２７２】
および符号ベクトルεを判別する(ステップCP1)およびCP2))ための(前述の再構築ステップCO1)の前の)2つの予備ステップ
- ディクショナリのその最近傍の位を計算する(ステップCP5))ための最後のステップ
【０２７３】
前述の検索は、もはやDijのTijコードベクトルの中ではなく(つまり、もはやmj∈[0,Tji[ではなく)、DijのLDjiリーダーの集合Lj(i)にわたってのみ実行される(mj∈[0,
【０２７４】
【数４４】
【０２７５】
、
【０２７６】
【数４５】
【０２７７】
はDijのリーダーまたは置換コードの数)。
この実施形態において、Dijのyの最近傍の検索は、(Ljの
【０２７８】
【数４６】
【０２７９】
最初のリーダーの中から)集合Lj(i)の
【０２８０】
【数４７】
【０２８１】
の最近傍を最初に検索することになる。前述のように、これらのリーダーを完全に再構築する必要はなく(ステップCO1)の操作c))、歪み基準(ここでは変更されたスカラー積)が各リーダーの非ゼロ成分についてのみ計算される。したがって、各リーダーに対して、L0のリーダーxj'の索引lmとLjのリーダーxjの各索引mjとを関連付けるLjのリーダーの索引からL0のリーダーの索引への対応テーブルを使用して、L0の対応するリーダーを判別すれば十分である。
【０２８２】
次いでアルゴリズムは、優先的に、以下の例に従って実行する。
* ステップCP1):
【０２８３】
入力ベクトルy=(y0,...,yk,...,yj-1)の、その絶対ベクトル|y|=(|y0|,...,|yk|,...,|yj-1|)への通過、およびその符号ベクトルε=(ε0,...,εk,...,εj-1)(yk≧0の場合εk=1、それ以外の場合εk=-1)への通過。
* ステップCP2):
【０２８４】
成分を降順に配置するようにその成分を置換することによる|y|のリーダー
【０２８５】
【数４８】
【０２８６】
の検索
* ステップCP3):
* ステップCo0'):初期化:
すべての索引mj∈[0,
【０２８７】
【数４９】
【０２８８】
に対して
【０２８９】
【数５０】
【０２９０】
* ステップCO1'):索引mjのリーダーの再構築:
a)L0のリーダーとLjのリーダーとを関連付ける対応テーブルにおいて、Ljの索引mjのリーダーに関連付けられているリーダーxjの索引lmの読み取り、次いでリーダーxj'の次元j'の判別および修正係数αの読み取り(
【０２９１】
【数５１】
【０２９２】
)
b)次元j'および索引lmのリーダーxj'の集合L0の読み込み
* ステップCO2')
【０２９３】
【数５２】
【０２９４】
とxj'の間の変更されたスカラー積の計算:
【０２９５】
【数５３】
【０２９６】
次のステップは、操作CO1')およびCO2')を繰り返して、入力ベクトルの絶対リーダーとの変更されたスカラー積が最大であるコードリーダーの索引を識別することを備えている。したがって:
【０２９７】
【数５４】
【０２９８】
であれば、
【０２９９】
【数５５】
【０３００】
かつmmax=mj
* 次に、mjを増分する:mj=mj+1
* 終了テスト
【０３０１】
【数５６】
【０３０２】
であればステップCO1')に進む、それ以外の場合は停止
【０３０３】
この終了ステップにおいて、ステップCP3)で見出された置換コードmmaxの数、ステップCP2)で実行された置換の位、およびステップCP1)で判別された符号ベクトルに基づいて、置換コードの和集合の索引付けの手順により、Djiのyの最近傍の索引を計算する。
【０３０４】
ステップCP2)は迅速化できることに留意されたい。具体的には、nijがLj(i)のリーダーの非ゼロ成分の最大数である場合、|y|のnij最大成分を検索することで十分である。望ましい格納/複雑さの妥協に応じて、ステップCP3)のいくつかの変種がある。計算の数を最小化したい場合には、L0のすべてのリーダーに対して、単にそれらの次元j'およびそれらの修正係数を表形式にすることができる。ステップCP3)で言及された次元j'の判別は、この場合、対応テーブルを読み取ることを備えている。逆に、メモリを軽減することを望む場合、この判別は、索引lmに基づいて実行される。同様に、修正係数は、リーダーxj'の読み取り後に計算することができる。
【０３０５】
したがって、置換コードの和集合としての構造を使用して、ディクショナリDijの次元jの入力ベクトルyの最近傍を検索するアルゴリズムは、優先的に以下のように要約することができる。
CP1)入力ベクトルy=(y0,...,yk,...,yj-1)から、その絶対ベクトル|y|=(|y0|,...,|yk|,...,|yj-1|)へ、およびその符号ベクトルε=(ε0,...,εk,...,εj-1)(yk≧0の場合εk=1、それ以外の場合εk=-1)へ通過する
CP2)成分を降順に配置するようにその成分を置換することによって|y|のリーダー
【０３０６】
【数５７】
【０３０７】
を検索する
CP3)Dijのリーダーの集合Lj(i)の(実際は、MijをDijの置換コードの数に置き換えることによりLjのMji最初のリーダーの中から)
【０３０８】
【数５８】
【０３０９】
の最近傍を検索する。前述のように、このステップは、Ljのリーダーの索引からL0のリーダーの索引への対応するテーブルによって示されるL0のMijリーダーのリストの中で変更されたスカラー積を最大化するL0のリーダーを検索することになる。L0のリーダーxj'の次元がj'(j'がj以上)である場合、
【０３１０】
【数５９】
【０３１１】
とのそのスカラー積の計算は、
【０３１２】
【数６０】
【０３１３】
の最初のj'成分でのみ実行され、次いでxj'のユークリッドのノルムの逆数が乗じられる。
CP4)以前のステップで見出された置換コードの数、ステップCP2)で実行された置換の位、およびステップCP1)で判別された符号ベクトルに基づいて、置換コードの和集合の索引付けの手順により、Dijのyのこの最近傍の位の索引を計算する。
【０３１４】
要するに、ステップCP2)は迅速化することができる。具体的には、nijがLj(i)のリーダーの非ゼロ成分の最大数である場合、|y|のnij最大成分を検索することで十分である。
【０３１５】
ここで、一般的な意味の範囲内で、前述の置換コード和集合索引付けを有利な実施形態として必ずしも限定的に使用することなく、復号化アルゴリズムについて説明する。復号化アルゴリズムは、優先的に、以下の形式をとる。
【０３１６】
受け取った索引mjに基づいて、この索引が
【０３１７】
【数６１】
【０３１８】
またはD’jNj-1に属しているコードベクトルに対応するかどうかを判別する。
【０３１９】
第1の場合、mjは
【０３２０】
【数６２】
【０３２１】
の一意の索引に関連付けられており、コードベクトルは、対応テーブルの簡単な読み取りを通じて取得される。
【０３２２】
第2の場合、mjは要素
【０３２３】
【数６３】
【０３２４】
および挿入規則を指し示す。
【０３２５】
xjmjがD'jNj-1またはその補集合のいずれに属しているかの判別は、様々な方法で実行することができる。例えば、索引ごとにバイナリ表示を使用することができる。各解像度riに対して、D'jiに属する制御された拡張により得られた要素で始まり、
【０３２６】
【数６４】
【０３２７】
に属する「自由な」要素が後に続く、Djiの補集合Dji-1の要素を索引付けすることも可能である。次いでD'jNj-1または
【０３２８】
【数６５】
【０３２９】
における帰属関係は、簡単なテストを通じて開始される。同様に、挿入規則は、明示的に索引付けされるか、あるいはそれ以外である。
【０３３０】
例えば、以下で説明される実施形態において、挿入規則は、索引に基づいて黙示的に取り出される。さらに、格納/索引付けの複雑さの妥協は、アプリケーションの要件に応じて調整することができることも理解されよう。
【０３３１】
ここで、置換コードの和集合により定義される追加の制約の特殊な事例に戻る。
【０３３２】
優先的に、復号化アルゴリズムは、さらにLjのリーダーの索引からL0のそれまでの対応テーブルを使用して、以下の文献からその発想を得ている。
- 「Algorithme de Quantification Vectorielle Algebrique Spherique par le Reseau de Gosset E8」、C.Lamblin、J.P.Adoul、Annales Des Telecommunications、No.3-4、1988年
【０３３３】
Djiのコードベクトルの索引に基づいて、Lj(i)のそのリーダーの索引、その置換コードのその位、およびその非ゼロ成分の符号を判別する。次いで、対応テーブルは、メモリに格納されているテーブルの簡単な読み取りを通じて得られるL0のリーダーの索引、および復号化コードベクトルを正規化できるようにするその正規化係数をもたらす。
【０３３４】
本発明のもう1つの模範的な実装は、以下に示される。この例はまた、TDACタイプ変換ベース符号器に基づいているが、16kHzでサンプリングされるデジタルオーディオ信号を符号化するために広帯域のTDAC符号器を使用する前述の例に反して、32kHzでサンプリングされ帯域幅15kHz(FM帯域)のデジタルオーディオ信号を符号化するために使用するものである。
【０３３５】
この符号器の原理は、16kHzのTDAC広帯域符号器の原理と類似している。16kHzで帯域制限され、32kHzでサンプリングされたオーディオ信号はさらに、20msのフレームに分割される。これは、MDCT変換後に、640の係数の取得をもたらす。スペクトルは、不均等の幅の52帯域に分割され、広帯域の分割は、広帯域TDAC符号器によって行われる分割と同一である。
【０３３６】
図8aの配列図は、使用された帯域分割、および結果として生じた係数のベクトルの次元(第3列に示される係数の数に対応)を示している。
【０３３７】
スペクトル包絡線の量子化はさらに、ハフマン符号化を使用し、残りの可変レートは、このスペクトル包絡線の量子化解除バージョンに基づいて係数に動的に割り振られる。
【０３３８】
MDCT係数の量子化では、本発明により構築されたディクショナリを使用する。前述の場合のように、ディクショナリは、置換コードの和集合としても構築される。15未満の次元については、ベクトル量子化器は、広帯域のベクトル量子化器と同様である。したがって、次元16、17、18、19、20、および24のディクショナリを構築する。次元24の場合、この構造はさらに、デカルト積の構造と組み合わされた。24係数の最後の上位帯域は、次元12の2つのベクトルに分割される。一方は偶数係数から成り、もう一方は偶数係数から成る。ここで、次元12に対して構築されたベクトル量子化器が使用された。
【０３３９】
図8bの配列図は、異なる解像度の数、および次元1から24に対するそれらの値を示している。
【０３４０】
したがって本発明は、可変レートおよび可変次元におけるベクトル量子化の問題に効果的な解決策を提供する。本発明は同時に、様々な次元および解像度に対して、ディクショナリが前述の構造化特性PRおよびPDを備えるベクトル量子化器を提供することにより、可変解像度および可変次元の2つの問題を解決する。
【０３４１】
所定の次元に対して、ディクショナリの埋め込みは、一方では、解像度の関数として歪みの局所的減少を保証し、もう一方では、低解像度のディクショナリを格納する必要がないので格納に必要とされるメモリの量を著しく減少し、これらのディクショナリのすべての要素は、実際に最大解像度のディクショナリ内にある。図1aおよび図1bのツリーとして構築されたベクトル量子化器と比較すると、ディクショナリを埋め込むという選択は、したがってすでに、解像度増加に応じた局所的歪みの減少の保証、および格納の軽減という2つの利点をもたらしている。さらに、必要に応じて、ビットよりも小さい細分性による解像度の優れた精密さを可能にし、必ずしも2乗とは等しくないサイズのディクショナリの選択を容易にする。この解像度の精密な細分性は、可変次元および/または可変解像度の複数のベクトルが、索引をバイナリ列として配置するアルゴリズムをこれらの非整数ベクトルベースのレート量子化器に関連付けることによってフレームごとに量子化される場合に、特に有利である。
【０３４２】
ディクショナリの埋め込み特性PRは、最大解像度のディクショナリを格納することのみが必要であることを意味している。第2の特性PDにより、記憶装置の量はより一層減少する。具体的には、最大解像度のディクショナリの要素の一部は、あらかじめ決められた挿入規則{Rm}を考慮して最大解像度であるが低次元のディクショナリから取り出される要素から推定されるので格納される必要はない。このように構造化された要素の比率は、容易に適合可能であり、記憶装置の量を微細に調整できるようになる。
【０３４３】
これらの2つの特性PRおよびPDにより導かれた構造はゆえに、必要な記憶装置を有利に減少させることができる。前述の従来技術を参照して導入部ですでに言及してあるような、追加の構造的制約をディクショナリに課すことによって、記憶装置の減少はさらに一層顕著となる。好ましい実施形態において、例えば球面ベクトル量子化器の使用、前述のデカルト積構造と適宜組み合わされた置換コードの和集合などの提供がある。
【０３４４】
代数ベクトル量子化器と比較すると、2つの特性によって導かれるディクショナリのこの構造は、次元の選択に関しても、解像度の選択に関しても、膨大な設計の柔軟性をもたらす。さらに、これらのベクトル量子化器は、符号化される情報源の統計に適合するので、これにより代数ベクトル量子化において必須である「ベクトル圧伸」の扱いにくい設計の問題を回避して、符号化される情報源の分布が均一になる。
【図面の簡単な説明】
【０３４５】
【図１Ａ】ツリー構造のベクトル量子化器を表す図である。
【図１Ｂ】ツリー構造のベクトル量子化器を表す図である。
【図２Ａ】所定の次元Nに対して、本発明の意義の範囲内でディクショナリの埋め込みの特性を示す図である。
【図２Ｂ】本発明の意義の範囲内でディクショナリの制御された拡張による部分的合成の特性を示す図である。
【図３】解像度増加に応じたディクショナリの埋め込みを示す図である。
【図４】低次元のディクショナリのコードベクトルおよび挿入規則に基づくディクショナリのコードベクトルの合成を示す図である。
【図５】低解像度のディクショナリを再更新しない埋め込みディクショナリの解像度増加に従う構築を示す図である。
【図６】「TDAC」符号器を示すブロック図である。
【図７Ａ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、32の帯域への分割を示す配列図である。
【図７Ｂ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、次元ごとの解像度を示す配列図である。
【図７Ｃ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、埋め込み特性により提供されるメモリゲインを示す配列図である。
【図７Ｄ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、埋め込みおよび制御された拡張の2つの特性により提供されるメモリゲインを示す配列図である。
【図７Ｅ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、これらの2つの特性を使用しないディクショナリの格納に必要なメモリサイズに関し、それぞれ次元およびレートに応じて2つの構造化特性によって提供されるメモリゲインを示す配列図である。
【図７Ｆ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、次元1、2、および3の集合L0の第1のリーダーを示す配列図である。
【図７Ｇ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、次元3のディクショナリの置換コードのリーダーを示す配列図である。
【図８Ａ】ＦMバンドTDAC符号器について、52の帯域への分割を示す配列図である。
【図８Ｂ】ＦMバンドTDAC符号器について、次元ごとの解像度を示す配列図である。
【符号の説明】
【０３４６】
53 初期ディクショナリDij(0)を構築 ディクショナリDi-1jに(Tij-Ti-1j)ベクトルを追加
54 クラスの構築
55 (Tij-Ti-1j)セントロイドを構築
59 終了
62 マスキング
63 スペクトル包絡線の符号化
64 ビットの動的割り振り
65 係数の量子化
67 v/nv検出
68 トーンの検出
【図１ａ】
【図１ｂ】
【図２ａ】
【図２ｂ】
【技術分野】
【０００１】
本発明は、格納および/または送信のためのオーディオ信号、ビデオ信号、および一般にマルチメディア信号などのデジタル信号の圧縮符号化および/または復号化に関する。
【背景技術】
【０００２】
デジタル信号の圧縮において非常に幅広く普及している解決策は、ベクトル量子化である。ベクトル量子化を使用する第1の動機は、符号化されるベクトルの次元を高めることによってより優れたパフォーマンスを達成できる、Shannonによって開発されたブロック符号化理論に見出すことができる。ベクトル量子化は、有限集合から選択された同様の次元のベクトルによって入力ベクトルを表すことを備えている。したがって、Mレベル(またはコードベクトル)を備える量子化器を提供することは、入力ベクトルの集合(一般にn次元のユークリッド実空間Rn、あるいはRnの部分集合)からRnの有限部分集合Yへの非全単射マッピングを作成することを意味する。部分集合Yは、以下のようにM個の個別要素から成る。
Y={y1,y2,...yM}
【０００３】
Yは、複製アルファベット、あるいはディクショナリ、あるいはディレクトリと呼ばれる。Yの要素は、「コードベクトル」、「コードワード」、「出口点」、あるいは「代表」と呼ばれる。
【０００４】
量子化器の次元(r)当たりのレート(またはその「解像度」)は、以下の式によって定義される。
【０００５】
【数１】
【０００６】
ベクトル量子化において、n個のサンプルのブロックは、次元nのベクトルとして処理される。ベクトルは、M個のコードベクトルのディクショナリから、最も「類似する」コードベクトルを選択することによって符号化される。一般に、全数検索は、ディクショナリのすべての要素の間で行われ、要素と入力ベクトルとの間の距離に対する測度を最小化するディクショナリの要素を選択する。
【０００７】
情報源符号化の定理によれば、次元が大きくなりすぎた場合、ベクトル量子化のパフォーマンスは、「情報源の速度-歪みの境界」と呼ばれる限界に到達する。空間の次元数は別として、ベクトル量子化は、例えば非線形および/または線形従特性、あるいは確率分布の形状など、符号化される情報源の特性を使用することもできる。一般に、ベクトル量子化器のディクショナリは、一般化ロイドアルゴリズム(GLAと呼ばれる)のような統計的手法に基づいて設計される。このアルゴリズムは周知であり、ベクトル量子化の最適性の必要条件に基づいている。符号化される情報源および初期ディクショナリを表すトレーニングシーケンスに基づいて、ディクショナリは反復して構築される。各反復は、以下の2つのステップで構成される。
- 最近傍の規則に従うトレーニングシーケンスの量子化による量子化の領域の構築
- (セントロイドの規則に従い)古いコードベクトルを領域のセントロイドに置き換えることによるディクショナリの改良
【０００８】
この決定性反復アルゴリズムの極小への収束を避けるため、シミュレーションアニーリングの技法に発想を得た「確率緩和」という名称の変種(「Stochastic K-means algorithm(確率K平均アルゴリズム)」の略語でSKAと示される)が、セントロイドを構築するステップおよび/またはクラスを構築するステップにランダム性を導入することによって提案されてきた。このようにして得られる統計的ベクトル量子化器は、何らかの構造を所持しないので、大量の計算およびメモリを必要とする点からそれらの探索を高価なものにする。具体的には、符号化および格納のいずれも複雑さは、n.2nrに比例する。ベクトルの次元およびレートに応じたこの指数関数的増加は、非構造化ベクトル量子化器の使用を、リアルタイムで埋め込むことができるように、小さい次元および/または低レートに制限する。
【０００９】
サンプルを個別に量子化するスカラー量子化は、情報源の確率分布の形状および線形従特性しか使用することができないので、ベクトル量子化ほど効果的ではない。しかし、スカラー量子化は、計算およびメモリに関しては、ベクトル量子化ほど高価ではない。さらに、エントロピー符号化に関連付けられているスカラー量子化は、適度な解像度においても良好なパフォーマンスを達成することができる。
【００１０】
サイズおよび次元の制約を回避するために、基本ベクトル量子化のいくつかの変種が研究された。彼らは、ディクショナリの構造の不在を改善しようと試み、品質の損失に至る複雑さの軽減を成し遂げようとした。しかし、パフォーマンス/複雑さの妥協が改善され、それによりベクトル量子化が、計算またはメモリのコスト面からも効果的に適用できるような解像度および/または次元のスパンを増大することが可能になる。
【００１１】
構造化ベクトル量子化器の多くの方式が、文献において提案されてきた。主なものは以下のとおりである。
- ディクショナリに階層ツリー構造を課すツリーベクトル量子化器。検索手順は単純化されるが、量子化器にはさらに多くの記憶装置が必要になる。
- より少ないレベルのベクトル量子化器をカスケードする多段ベクトル量子化器。ディクショナリはサイズが減少し、計算時間およびメモリのコストについても同様のことがいえる。
- より小さい次元およびサイズのNクラシカルベクトル量子化器の「デカルト積」と呼ばれるベクトル量子化器。入力ベクトルはN個のサブベクトルに分解され、各サブベクトルは相互に独立して量子化される。
- 「ゲイン/方位」ベクトル量子化器は、「デカルト積」ベクトル量子化器の特別な事例を構成する。一方はスカラー量子化器、もう一方はベクトル量子化器である2つの量子化器が提供される。これらは単独にせよそうでないにせよ、(正規化入力ベクトルを考慮することにより)ベクトルのゲイン(またはノルム)とその方位を個別に符号化する。この種のベクトル量子化はまた、「球形」ベクトル量子化または「極性」ベクトル量子化とも呼ばれる。
- 「置換コード」ベクトル量子化器。そのコードベクトルはリーダーベクトルの成分の置換と置換コードの合成(または和集合)へのその一般化とによって得られる。
【００１２】
前述の技法はすべて、統計的手法の範囲内にある。
【００１３】
もう1つの根本的に異なる手法も提案された。それは代数ベクトル量子化であり、点の正規格子またはエラーコレクターコードから生じる高度に構造化されたディクショナリを使用するものである。それらのディクショナリの代数的特性により、代数ベクトル量子化器は、実装が簡単であり、メモリに格納される必要はない。これらのディクショナリの正規構造の使用は実際に、最適かつ高速な検索アルゴリズムの開発と、特に索引を(例えば公式を通じて)対応するコードベクトルに関連付けるためのメカニズムの開発とを可能にする。代数ベクトル量子化は、実装がさほど複雑ではなく、必要なメモリも少なくてすむ。しかし、これらは(空間内、あるいは超球の表面上の)情報源の均一な分布についてのみ最適である。均一スカラー量子化器の一般化であるが、代数ベクトル量子化は、いわゆる「圧伸」技法を通じて情報源の分布に合わせて調整することがより困難である。さらに、コードベクトルの索引付け(または番号付け)および逆の操作(復号化)では、これらの操作がテーブルからの簡単な読み取りによって行われる統計ベクトル量子化器の場合に比べて、さらに多くの計算が必要となることも思い起こされる。
【００１４】
可変次数量子化の特定の態様および遭遇する問題は、これ以降で提示される。
【００１５】
最初に、ベクトル量子化が既知であり、固定長のサンプルのブロックを符号化するための効果的な技法であることが示される。しかし、デジタル信号圧縮の多くの適用において、符号化される信号は、可変長のパラメータのシーケンスによってモデル化される。可変次元のこれらのベクトルの効果的な圧縮は、スピーチまたはオーディオ符号器(「MBE」符号器、調波符号器、正弦波符号器、変換ベースの符号器、原型波形の補間に基づく符号器)など多くのマルチメディア符号器の設計に不可欠である。
【００１６】
正弦波符号器において、抽出される正弦波の数は、信号中に検出される正弦波スパイクの数に基づくが、その数はオーディオ信号の特性に応じて時間の経過と共に変化する。
【００１７】
さらに、音声圧縮の多くの技法は、信号の長期的周期性を利用する。このことは、話者の基本周期の高調波である一連の周波数のスペクトル成分が符号化される調波符号器の場合も同様である。この基本周期は、話者(通常、子供は大人よりも声帯の振動周波数が高い)および時間の経過と共に変化するので、スペクトル調波スパイクの数は基本周波数に反比例するが、量子化される成分の数も時間の経過と共にフレームごとに変化する。
【００１８】
このことはまた、原型波形がピッチの期間と等しい長さのセグメントにわたり抽出され、そのため時間的に可変でもある、PWI符号器(「Prototype Waveform Interpolation」の略)の場合も同様である。PWI符号器において、これらの可変長の波形の量子化は、ゲイン(または「Root-Mean-Square(二乗平均平方根)」の略語である「RMS」)と、自身がREW波形(「Rapidly Evolving Waveform」)およびSEW波形(「Slowly Evolving Waveform」)という同じ可変長の2つの波形に分解される正規化波形とを個別に符号化することによって達成される。固定長のフレームの場合、原型の数は可変であり、そのためREWおよびSEW波形の次元と同様に、ゲインの数、REWおよびSEWの数も同様に可変である。
【００１９】
変換ベースのオーディオ符号器など、他の種類の符号器において、固定長フレーム長にわたって取得された変換係数の数が課されるが、これらの係数をそれらの量子化のために周波数帯域にグループ化することが通例である。従来、この分割は、耳の臨界帯域に従うことによって人間聴覚の心理音響的な特性を利用するように、不均等な幅の帯域に行われる。変換係数のこれらのベクトルの次元の変化の範囲は通常、広帯域符号器(50Hz〜7000Hz)において3(低周波数帯域の場合)から15(高周波数帯域の場合)まで変化し、FM帯域符号器(20Hz〜16000Hzの可聴範囲に及ぶ)において24まで変化する。
【００２０】
理論的には、可変次元の最適なベクトル量子化器は、入力ベクトルの可能な次元ごとに1つ、固定次元のディクショナリのセットを利用することであろう。例えば、60〜450Hzのピッチ期間で、電話帯域の調波スパイクの数が高ピッチの音声(子供)の7から低ピッチの音声(大人)の52まで変化する調波符号器において、46(46=52-7)ベクトル量子化器を構築し、メモリに配置して実装することが必要になる。各ディクショナリの設計には、入力ベクトルの統計を正確に表す十分な長さの学習シーケンスが必要である。さらに、すべてのディクショナリの格納は、メモリ内では実際的ではないか、または非常に高価であることが判明する。したがって、可変次元の場合、記憶装置の制約及びトレーニングシーケンスの制約にも応じながら、同時にベクトル量子化の利点を活用することは困難であることが分かる。
【００２１】
以下に提示されるのは、可変解像度による量子化の特定の態様および遭遇する問題である。
【００２２】
第1に、入力信号の変動性は、符号化されるパラメータの数における変化を通じてのみ顕在化するのではなく、所定の品質で送信されるバイナリ情報の量における変化を通じても顕在化することが指摘される。例えばスピーチにおいて、頭子音、有声音、および無声音は、同一品質の同じレートを必要とはしない。比較的予測不能な頭子音には、さらに安定し、その定常性がレートを減少させることのできる「予測子」によって活用されうる有声音よりも高いレートが必要になる。最後に、無声音は、高い符号化精度を必要とせず、そのためほとんどレートを必要としない。
【００２３】
音声またはビデオのようなマルチメディア信号の特性の一時的な変動を利用するため、可変レート符号器を設計することが賢明である。これらの可変レート符号器は、インターネット、ATMなどのような、パケット的な格子にわたる通信に特に適している。
【００２４】
具体的には、パケット交換は、情報ビットをさらに柔軟な方法で扱いかつ処理することができるので、平均レートを減少することによってチャネルの容量を増加させることができるようにする。変数レート符号器の使用はさらに、システムの輻輳を抑制する効果的な手段および/またはアクセス条件の多様性に対応する効果的な手段でもある。
【００２５】
マルチメディア通信においては、可変レート量子化器はまた、以下のようなレートの分布を最適化することも可能にする。
- 情報源およびチャネル符号化間。AMR(「Adaptive Multi Rate(適応マルチレート)」)の概念におけるように、レートは、トラフィックおよびチャネルエラー条件に動的に適合されるように各20msフレームで切り替えることができる。このようにしてスピーチの全体的な品質は、エラーに対する良好な保護を確実にし、同時にチャネルが機能低下した場合に情報源の符号化のレートを減少することによって改善される。
- 様々な種類のメディア信号間(テレビ会議アプリケーションにおける音声およびビデオなど)。
- 同一の信号の様々なパラメータ間。変換ベースのオーディオ符号器において、例えば、スペクトル包絡線と係数の様々な帯域との間でビットを動的に分散することが通例である。多くの場合、包絡線のエントロピー符号化が最初に実行され、その目的は、可変長コードをコードワードに割り当てることによりコードワードの非均一な分散を使用して、最も可能性の高いものは最も可能性の低いものよりも短い長さを持ち、それによりコードワードの平均長の最小化を導くことである。さらに、人間の耳の心理音響的な特性を利用するために、残りの(可変)レートが係数の周波数帯域にそれらの知覚有意性に応じて動的に割り振られる。
【００２６】
マルチメディア符号化の新しいアプリケーション(オーディオおよびビデオなど)は、次元およびレートの両方において極めて柔軟な量子化を必要とする。レートの範囲はさらに高品質を達成できるようにしなければならないので、これらの多次元および多解像度の量子化器は高解像度をめざす必要がある。これらのベクトル量子化器によってもたらされる複雑な障壁は、新技術の処理能力および記憶容量の増大にもかかわらず、それ自体が依然として達成すべきパフォーマンスであり続ける。
【００２７】
以下の説明から分かるように、提案されている情報源符号化技法の多くは、可変次元に関連する問題、または可変解像度に関連する問題を解決することを目的としている。これらの2つの問題を共に解決できるようにする技法は、今日までほとんど提案されていない。
【００２８】
既知の可変次元によるベクトル量子化に関しては、符号化されるパラメータの次元の可変性それ自体がベクトル量子化の使用の障壁を構成する。したがって、変換ベースの符号器の最初のバージョンは、Lloyd-Maxスカラー量子化器を採用する。「TDAC」と呼ばれるこのタイプの符号器は、本出願者によって開発され、特に以下の文献において説明されている。
- 「High Quality Audio Transform Coding at 64 kbit/s」Y.Mahieux、J.P.Petit共著、IEEE Trans.Commun、Vol.42、No.11、3010〜3019頁、1994年11月
【００２９】
この可変次元ベクトル量子化の問題を解決するために、他の解決策が提案されてきた。「IMBE」符号器は、可変バイナリ割り振りおよびスカラー/ベクトル混成量子化を備える複雑な符号化体系を使用する。
【００３０】
可変次元のベクトルを量子化するため広く一般的に使用される手法は、量子化前に可変次元のベクトルを別の固定次元のベクトルに変換するように前処理することにある。次元変換に関連付けられるこのベクトル量子化技法の変種はいくつかある(この種のベクトル量子化は「Dimension Conversion Vector Quantization」の略語であるDCVQと示される)。
【００３１】
提案された様々な次元変換手順の中で、切捨て、副標本、補間、「長さワーピング」について特に言及される。
【００３２】
正弦波スピーチ符号器つまりMBEの場合、スペクトル係数が固定された順序の全極モデルによって近似され、その後モデルのパラメータの固定次元のベクトル量子化が実行されることが提案された。非正方行列変換によるベクトル量子化のもう1つの技法は、固定次元K(K<L)のベクトル量子化を非正方行列一次変換(L×K)と組み合わせることにより、可変次元Lのベクトル量子化の問題を解決する。
【００３３】
さらに、依然として固定次元Kのベクトル量子化を使用するが、入力ベクトルと同じ次元を有するコードベクトルを取得するために次元変換がコードベクトルに適用される次元変換に関連付けられているベクトル量子化のもう1つの種類がある。
【００３４】
次元変換に関連付けられたベクトル量子化の欠点は、全歪みが、量子化による成分および次元変換による成分という2つの成分を有することである。次元変換によるこの歪みを回避するため、可変次元のベクトル量子化のもう1つの手法は、可変次元Lの各入力ベクトルを次元K(L<K)の「基礎をなす」ベクトルの成分の部分集合から形成されると見なすこと、および入力ベクトルの次元の全範囲に及ぶ固定次元Kの単一の「ユニバーサル」ディクショナリのみを設計して使用し、入力ベクトル間の対応は選択子によってもたらされることを備えている。しかし、他の低次元のディクショナリをすべて網羅するこの「ユニバーサル」ディクショナリは、最低次元に最適であるとは考えられない。特に、次元当たりの最大解像度rmaxは、格納の制約およびパラメータのベクトル当たりのレートによって制限されている。サイズ2Krmaxのディクショナリの場合、このディクショナリを格納するために必要なメモリ量はK2Krmax値であり、そのパラメータのベクトル当たりのレートはKrmaxである。したがって、同一のサイズのディクショナリ(したがってパラメータのベクトル当たりおよびフレーム当たり同一のレート)の場合、次元L(L<K)のベクトルは、K/L倍大きい解像度(または次元当たりのレート)、およびK/L倍小さい格納される情報量を有することができる。
【００３５】
既知の可変解像度によるベクトル量子化に関しては、簡単な解決策は、可変次元によるベクトル量子化の場合に関して、例えばTDAC変換ベースの符号器の第1のバージョンにおけるように、スカラー量子化を使用することにある。
【００３６】
しかし、サンプル当たりの整数解像度の使用は、動的バイナリ割り振り手順の有効性を妨げる係数の帯域当たりの解像度の粗い細分性を必然的に伴う。したがって、符号化索引を結合バイナリ列として配置する手順と組み合わせて、再構築レベルの奇数の整数によるスカラー量子化の使用が提案された。さらに細かい解像度の細分性が提供され、バイナリ割り振り手順にさらに好都合になり、索引を組み合わせるアルゴリズムの複雑さを犠牲にして、品質を改善することが可能になった。このアルゴリズムは、バイナリ列への配置をレートに関して効果的にするために必要であった。それにもかかわらず、多数の係数を有する高い周波数帯域に対して、スカラー量子化に起因する、サンプル当たりの整数のレベルの制約は、依然として帯域当たりの解像度の細分性が粗すぎることを通じて顕在化されている。
【００３７】
ベクトル量子化は、サンプル当たりの多くの整数レベルのこの制約を回避できるようにし、使用可能な解像度の微細な細分性を可能にする。一方、ベクトル量子化の複雑さは多くの場合、使用可能なレートの数を制限する。例えば、周知のACELP技術に基づくAMR-NBマルチレートスピーチ符号器は、各々が情報源符号化とチャネル符号化との間のレートの異なる分散によりエラーに対する異なるレベルの保護を有する、12.2kbit/sから4.75kbit/sの範囲の8つの固定レートを備えている。ACELP符号器のパラメータ(LSP、LTP遅延器、励起ゲイン、固定励起)のそれぞれについて、異なる解像度のディクショナリが構築された。しかし、これらのパラメータの各々に使用可能なレートの数は、非代数ベクトル量子化器の格納の複雑さにより制限されている。さらに、6.60から23.85kbit/sの範囲の9つのレートを備えるAMR-WBマルチレート符号器において、基本的に、レートの変動は、格納を必要としない代数励起ディクショナリによって保証される。8つのディクショナリがあるので、固定励起に8つのレートがあるが、一方確率ディクショナリを使用する他のパラメータ(LSP、ゲイン、絶対および差分遅延)は2つの可能なレートしか持たない。
【００３８】
AMRマルチレート符号器に使用される確率ベクトル量子化器が、制限付きの構造(デカルト積および多段)によるベクトル量子化器であることが示されている。可変レート量子化器の大きなファミリーは、実際、多段、デカルト積を有する前述の量子化器、あるいはツリーベースのベクトル量子化器などの制約付き構造ベクトル量子化器を基にすることもできる。可変レート符号化へのこれらのツリーベースの量子化器の使用は、数多くの研究の主題を形成してきた。バイナリツリーベースのベクトル量子化器は、最初に導入されたものであった。これは、トレーニングシーケンスの重心である「ルート」ノードに基づくセントロイドの連続分割によりベクトル量子化器を設計するためのLBGアルゴリズムから必然的に派生する。変種のツリータイプベクトル量子化器は、枝刈りすることに基づき、あるいは逆にツリーの特定のノードを、非バイナリおよび/または非平衡のツリーベースのベクトル量子化器に至るそれらの歪み、それらのノードの分布などの特性に従って分岐することに基づいて提案されてきた。
【００３９】
図1aおよび1bは、ツリー構造のベクトル量子化器を表している。具体的には、図1aは平衡バイナリツリーを表し、一方図1bは非バイナリの非平衡ツリーを表している。
【００４０】
複数解像度のベクトル量子化器は、望ましい様々な解像度に対応するノード数を選択することにより、ツリータイプのベクトル量子化器に基づいて容易に構築される。ツリータイプの階層構造は、訴求力があり、検索手順を単純化する。一方、これは、次善の検索を伴い、また中間レベルのすべてのノードを介するルートノードから端末ノードまでツリーのすべてのノードが格納される必要があるため、必要なメモリの大幅な増加を伴う。さらに、低解像度のディクショナリのノードのセットは高解像度のディクショナリに含まれないので、ベクトル量子化器のレートの増加に応じた量子化エラーの減少は、局所的には保証されない。
【００４１】
さらに、代数コードに基づいて可変解像度量子化器を構築する方法、特に8次元の正則Gosset格子の球形コードの部分集合を使用するEAVQ（埋め込み代数ベクトル量子化器）を構築する方法は知られている。
【００４２】
以下の文献において、
- 「A 16,24,32 kbit/s wideband speech codec based on ACELP」P.Combescure、J.Schnitzler、K.Fischer、R.Kircherr、C.Lamblin、A.Le Guyader、D.Massaloux、C.Quinquis、J.Stegmann、P.Vary共著、Proceedings IEEE International Conference on Acoustics, Speech, and Signal Processing、Vol.1、5〜8ページ、1999年
この埋め込み代数ベクトル量子化の手法は、様々な次元の代数コードを使用して可変次元量子化まで拡大された。たとえこのEAVQ量子化の一般化が、可変解像度で可変次元のベクトルを量子化できるようにするとしても、これには欠点がある。
【００４３】
入力ベクトルの分布は均一である必要がある。しかし、この制約に情報源の分布を適合させることは、非常に困難な作業である。正則格子に基づく代数量子化の設計はまた、望ましい様々な解像度を得るために様々な正則格子の領域を切り捨てて調整し、それを様々な次元に対して行うという問題も引き起こす。
【非特許文献１】「High Quality Audio Transform Coding at 64 kbit/s」Y.Mahieux、J.P.Petit共著、IEEE Trans.Commun、Vol.42、No.11、3010〜3019頁、1994年11月
【非特許文献２】「A 16,24,32 kbit/s wideband speech codec based on ACELP」P.Combescure、J.Schnitzler、K.Fischer、R.Kircherr、C.Lamblin、A.Le Guyader、D.Massaloux、C.Quinquis、J.Stegmann、P.Vary共著、Proceedings IEEE International Conference on Acoustics, Speech, and Signal Processing、Vol.1、5〜8ページ、1999年
【非特許文献３】「Algorithme de Quantification Vectorielle Algebrique Spherique par le Reseau de Gosset E8」、C.Lamblin、J.P.Adoul、Annales Des Telecommunications、no 3-4、1988年["Spherical algebraic vector quantization algorithm by the E8 Gosset lattice"]
【発明の開示】
【発明が解決しようとする課題】
【００４４】
本発明は、この状況を改善することを目的としている。
【００４５】
本発明の目的の1つは、一般的に、可変次元のベクトルの可変レート量子化の問題に効果的かつ経済的な解決策(特に記憶装置に関して)を提案することである。
【００４６】
本発明のもう1つの目的は、非限定的な意味で、特にスピーチおよび/またはオーディオ信号の、調波符号器のスペクトル振幅および/または周波数符号器の変換係数の量子化を使用してデジタル信号の符号化および復号化を有利に提供するベクトル量子化を提供することである。
【課題を解決するための手段】
【００４７】
この目的を達するために、本発明は、可変次元のコードベクトルを備え、可変解像度を定義する可変レートのベクトル量子化により、デジタル信号の圧縮符号化および/または復号化のために装置において使用することを意図されたディクショナリを提案し、ディクショナリは、
- 一方においては、所定の次元に対して、解像度増加の中間埋め込みディクショナリと、
- 一方においては、所定の次元に対して、
・あらかじめ決められた挿入規則の有限コレクタに従って、実数の有限集合から取り出された要素を、低次元のディクショナリのコードベクトルに挿入することによって構築されたコードベクトルから成る第1の集合と、
・挿入規則の前記収集に従って前記有限集合の要素の低次元のコードベクトルへの挿入によって取得できないコードベクトルから成る第2の集合との和集合を備えている。
【００４８】
好ましくは、挿入規則の前記収集は、ベクトルの所定の位置において成分を装って実数の有限集合の単一要素を挿入するステップを備える基本規則に基づいて定式化される。
【００４９】
各基本規則は、
- 前記有限集合の要素の位の正整数と、
- 挿入の位置の正整数とを示す上記2つの正整数の組によって定義されることが好ましい。
【００５０】
このようにして特徴付けられた挿入規則は、本発明の意義の範囲内でディクショナリの実際の構造から直接に読み取られ推定されることを理解されよう。
【００５１】
もちろん、純粋に可逆的に、低次元N(N<N')を得るように所定の次元N'の有限集合の1つまたは複数の要素を削除するステップを備える削除規則を定義することができる。
【００５２】
本発明はさらに、本発明によるディクショナリを形成する方法を目的としている。所定の次元に対して、
a)第1の集合は、あらかじめ決められた挿入/削除規則の有限収集に従って、実数の有限集合から取り出された低/高次元要素のディクショナリのコードベクトルに/から挿入/削除することによって形成されたコードベクトルから成り、
b)第1の中間のディクショナリは、前記所定の次元に対して、少なくとも前記第1の集合が構築されることを備え、
c)前記ディクショナリを少なくとも1つの所定の解像度で使用するように適合するため、第2の最終的なディクショナリが、中間ディクショナリに基づいて、増加/減少解像度のディクショナリの埋め込み/単純化により構築され、増加解像度のディクショナリは、最小解像度のディクショナリから最大解像度のディクショナリまで中間埋め込みされる。
【００５３】
もちろん、「集合Aの集合Bへの埋め込み」という用語は、集合Aが集合Bに含まれることを意味するよう意図されている。さらに、「集合Bを得るための集合Aの単純化」という用語は、集合Aが集合Bを含むことを意味するよう意図されている。
【００５４】
変種または補足により、一方でステップa)およびb)、一方でステップc)は、コードベクトルの所定の次元Nで使用するように前記ディクショナリを適合するため、実質上逆転することができることを理解されたい。
【００５５】
この場合、
- ステップc)において、依然として次元N'であるがより高い/低い解像度rNである第1の中間のディクショナリが、前記第1のディクショナリの解像度rNを実質的に獲得するように、増加/減少解像度のディクショナリの埋め込み/単純化により、解像度rNおよび次元N'の初期ディクショナリに基づいて構築され、
- ステップa)において、所定の次元Nを獲得するため、第1の集合は、あらかじめ決められた挿入/削除規則の有限収集に従って、実数の有限集合から取り出された前記所定の次元N要素よりも低い/高い次元N'の第1のディクショナリのコードベクトルに/から挿入/削除することによって形成されたコードベクトルから成り、
- ステップb)において、解像度rNへの最終的な適合の可能なステップに続いて、少なくとも前記第1の集合からなる第2の最終のディクショナリは、前記所定の次元Nに対して構築されることを備える。
【００５６】
連続次元を増加することによりステップa)を実装することができる。この場合、所定の次元Nに対して、
a0)前記所定の次元Nよりも低い初期次元nの初期ディクショナリが取得され、
a1)あらかじめ決められた挿入規則の有限収集に従って、実数の有限集合から取り出された要素を初期ディクショナリのコードベクトルに挿入することによって形成された次元n+iのコードベクトルから成る第1の集合が構築され、
a2)挿入規則の前記収集による前記有限集合の要素の初期ディクショナリのコードベクトルへの挿入によって取得できない次元n+iのコードベクトルから成る第2の集合が提供され、
a3)前記第1の集合および前記第2の集合の和集合から成る次元n+iの中間ディクショナリが構築され、
ステップa1)からa3)は、前記中間ディクショナリが初期ディクショナリを装い、前記所定の次元Nまで、多くともN-n-1回繰り返され、この場合(i=1)である。
【００５７】
また、連続次元を減少することによりステップa)を実装することもできる。この場合、所定の次元Nに対して、
a'0)前記所定の次元Nよりも高い初期次元nの初期ディクショナリが取得され、
a'1)次元n-iの第1の集合は、あらかじめ決められた削除規則の有限収集に従って、次元nのディクショナリからの次元n-iの可能なコードベクトルの選択および抽出により構築され、
a'2)削除規則の前記収集による前記有限集合の要素の初期ディクショナリのコードベクトルからの削除によって単純に取得できない次元n-iのコードベクトルから成る第2の集合が提供され、
a'3)前記第1の集合および前記第2の集合の和集合から成る次元n-iの中間ディクショナリが構築され、
ステップa'1)からa'3)は、前記中間ディクショナリが初期ディクショナリを装い、前記所定の次元Nまで、多くともn-N-1回繰り返され、この場合(i=1)である。
【００５８】
連続次元1からNまでの複数のNディクショナリを取得するために、好ましくは次元n(n<N)の初期ディクショナリに基づいて、次元n+1からNに対するステップa1)からa3)の繰り返しの実装を通じ、次元n-1から1に対するステップa'1)からa'3)の繰り返しの実装を通じて、ステップa1)からa3)およびステップa'1)からa'3)を組み合わせることが可能である。
【００５９】
このようにして、最大の次元のディクショナリが次元Nを有するNディクショナリの全体または一部を取得する。
【００６０】
連続次元のディクショナリの構築に役立つ有限集合および挿入/削除規則の収集は、以下のように定義することができる。
- 量子化される情報源の分析により、ディクショナリを構築する前に、演繹的に、
- ディクショナリの構築後に、好ましくは連続解像度のディクショナリの埋め込み/単純化により、帰納的に。この構築の後には、このように構築されるこれらのディクショナリの統計的分析が続く。
【００６１】
量子化される情報源は好ましくは学習シーケンスによってモデル化され、有限集合および挿入/削除規則の収集の「演繹的」定義は、好ましくは情報源の統計的分析によって達成されることが示されている。前述の有限集合は、好ましくは量子化される情報源の単一次元の確率密度の推定によって選択される。
【００６２】
有限集合および挿入規則の演繹的および帰納的定義を組み合わせることにより、
- 挿入/削除規則の第1の集合および第1の収集は、1つまたは複数の中間ディクショナリを形成するように、学習シーケンスの分析により有利に演繹的に選択することができ、
- 前記第1の集合および/または挿入/削除規則の前記第1の収集の少なくとも一部は、1つまたは複数の前記中間ディクショナリの帰納的分析によって更新され、
- 必要に応じて、前記1つまたは複数の前記中間ディクショナリを形成するコードベクトルの集合の少なくとも一部も更新される。
【００６３】
好ましくは、所定の解像度への適合のステップc)は、増加解像度を達成するために、以下の操作を備えている。
c0)前記所定の解像度rNよりも低い初期解像度rnの初期ディクショナリが取得され、
c1)初期ディクショナリに基づいて、初期解像度rnよりも高い解像度rn+1の中間ディクショナリが構築され、
c2)所定の解像度rNが達成されるまで、操作c1)が繰り返される。
【００６４】
有利なことに、操作c1)の繰り返しごとに、クラスおよびセントロイドの構造が提供され、そこで現行解像度riよりも高い解像度のディクショナリに少なくとも属しているセントロイドが再計算されて更新される。さらに、現行解像度riよりも低い解像度のディクショナリに属しているセントロイドは、低い解像度のすべてのディクショナリの全歪みが1つの更新からその次の更新で減少する場合に限り、好ましく更新される。
【００６５】
補足または変種を経て、ステップc)は、減少解像度を達成するために、以下の操作を備えている。
c'0)前記所定の解像度rNよりも高い初期解像度rnの初期ディクショナリが取得され、
c'1)初期ディクショナリに基づき、初期ディクショナリをあらかじめ決められた基準に従って順序付けられた複数の部分集合に区分化することによって、初期解像度rnよりも低い解像度rn-1の中間ディクショナリが構築され、
c'2)所定の解像度rNが達成されるまで、操作c'1)が繰り返される。
【００６６】
有利なことに、この分割化は、実装された挿入/削除規則の少なくとも一部を使用し、ステップa)およびb)の意義の範囲内の制御された拡張による部分的合成を使用することができる。
【００６７】
解像度r1およびrNの間の中間解像度rnの初期ディクショナリに基づいて、それぞれの解像度r1からrNの複数のNの連続ディクショナリを取得するために、増加解像度rn+1からrNに対してステップc1)の繰り返しを実装し、減少解像度rn-1からr1に対してステップc'1)の繰り返しを実装することが有利に可能である。
【００６８】
有限集合および挿入/削除規則の収集は、望ましい次元および解像度の、本発明の意義の範囲内のディクショナリを形成するため、このように取得された様々な解像度および次元のディクショナリの統計の帰納的な検討を通じて有利に選択されうることが理解されよう。
【００６９】
本発明により提供される利点の1つによれば、符号化/復号化の実装に必要な記憶装置は、大幅に減少させることができる。具体的には、有利なことに、各々索引によって識別された挿入/削除規則の前記収集は、これを最後にメモリ内に格納されており、かつ所定の次元に対して、
- 前記第2の集合は、所定の次元よりも低い/高い次元のコードベクトルへの挿入/削除規則の適用により取得することができないコードベクトルを備え、
- さらに、少なくとも1つの対応するテーブルは、挿入/削除規則の索引および前記第2の集合の要素を識別する索引を使用して、所定の次元のディクショナリの任意のコードベクトルを再構成できるようにする。
したがって、前記所定の次元のディクショナリの完全な格納は、前記第2の集合の要素およびリンクを、これらの要素および関連付けられている挿入/削除規則へのアクセスのために対応するテーブルに単に格納することによって回避される。
【００７０】
それゆえに、所定の次元に対して、前述の第2の集合は、前記所定の次元よりも低い次元の「第2の」部分集合を有利に備えることができることが理解されよう。
【００７１】
1つの実施形態において、挿入/削除メカニズム自体はプログラムルーチンを装って格納することができるが、挿入/削除パラメータは、所定の挿入/削除規則に対して、この所定の挿入/削除規則の索引と組み合わせて、一般対応テーブル(原則として前述の対応テーブルとは異なる)に格納することができる。
【００７２】
好ましくは、対応テーブルは、以下のものを表す3つの整数スカラー値の集計を通じて、現行次元の第2の集合内の現行索引の要素に基づいて再構築することのできる所定の次元のディクショナリのコードベクトルの索引ごとに、前もって定式化される。
- 前記第2の集合の現行次元
- 第2の集合の要素の現行索引
- 挿入/削除規則の索引
この挿入/削除規則は少なくとも、前記現行索引および前記現行次元に対応する要素に挿入/削除を適用することによって、所定の次元のディクショナリの前記コードベクトルを再構成することに寄与する。
【００７３】
これらの後者の特性は、以下に説明されるように、圧縮符号化/復号化方法において有利に実装することができる。
【００７４】
この点において、本発明はさらに、可変解像度を定義する可変レートでのベクトル量子化によって、デジタル信号を圧縮符号化/復号化するために、本発明により、また前述のステップの実装を通じて得られるディクショナリを使用することも目的としている。特に、所定の次元jのディクショナリ内の入力ベクトルy=(y0,...,yk,...,yj-1)の最近傍であるコードベクトルについて検索が行われる。この使用は次に、以下のステップを実装する。
CO1)検索される前記コードベクトルの現行索引に対し、対応するテーブルに表示される索引の読み取りと、必要に応じて前記ディクショナリを作成できるようにする第2の集合の要素の読み取りとを少なくとも通じて、前記現行索引に対応する索引のコードベクトルの少なくとも部分的な再構築であって、
符号化/復号化ステップを適正に続行する方法は、
CO2)少なくとも符号化において、入力ベクトルとステップC01)において再構成されたコードベクトルとの間の距離の計算と、
CO3)少なくとも符号化において、前記ディクショナリのすべての現行索引に対して、ステップC01)およびC02)の繰り返しと、
CO4)少なくとも符号化において、ステップC02)の繰り返しの1つの過程で計算された入力ベクトルとの距離が最も小さい、少なくとも部分的に再構成されたコードベクトルの索引の識別と、
CO5)少なくとも復号化において、索引がステップC04)において識別されたコードベクトルを装った入力ベクトル(y)の最近傍の決定とを備えている。
【００７５】
前述のように、「第2の」上記の集合は、好ましくは第2の集合の所定の次元よりも低い次元の「第2の」部分集合を備えていることが思い起こされる。
【００７６】
特定の実施形態において、ステップC01)は、少なくとも復号化の際に、
C011)対応テーブル内での、前記第2の集合および挿入規則へのリンクを表す索引の読み取りであって、
- 前記第2の集合の部分集合の現行次元の索引と、
- 前記部分集合の要素の現行索引と、
- 前記要素に基づき、所定の次元のディクショナリのコードベクトルの構築のための適切な挿入規則の索引とを含む索引の読み取り、
C012)現行次元によって識別される部分集合内での、その現行索引によって識別される前記要素の読み取り、
C013)ステップC012)において読み取られた前記要素に、ステップC011)において読み取られたその索引によって識別された適切な挿入規則を適用することによる、前記所定の次元へのコードベクトルの完全な再構成を備えている。
【００７７】
特定の実施形態において、符号化の際に、
* ステップC01)は、
C011)対応テーブル内での、前記第2の集合および挿入規則へのリンクを表す索引の読み取りであって、
- 前記第2の集合の部分集合の現行次元の索引と、
- 前記部分集合の要素の現行索引と、
- 前記要素に基づき、所定の次元のディクショナリのコードベクトルの構築のための適切な挿入規則の索引とを含む索引の読み取り、
C012)現行次元によって識別される部分集合内での、その現行索引によって識別される前記要素の読み取り、
* ステップC02)において、前記距離は、
- 前記挿入規則と、
- 前記要素との関数として推定される歪み基準の関数として計算される。
【００７８】
したがって、単に復号化のために完全な再構築を保持しておくことによって、ステップC01)の前記所定の次元をコードベクトルの部分的な再構築のみに提供することが可能である。
【００７９】
有利な実施形態において、置換コードの和集合に従って補足構造化特性がさらに提供され、置換コードのこの和集合の索引は以下のステップの実装に使用される。
CP1)入力信号に基づき、絶対ベクトル|y|=(|y0|,...,|yk|,...,|yj-1|)および符号ベクトルε=(ε0,...,εk,...,εj-1)、εk=±1によって定義される入力ベクトルy=(y0,...,yk,...,yj-1)が形成され、
CP2)ベクトル|y|の成分は、リーダーベクトル
【００８０】
【数２】
【００８１】
を取得するため、置換によって、値を減少することによりランク付けされ、
CP3)次元jのディクショナリDjiのリーダーベクトルの中からリーダーベクトル
【００８２】
【数３】
【００８３】
の最近傍xj'が判別され、
CP4)ディクショナリDjiの前記最近傍xj'のランクの索引が判別され、
CP5)符号化/復号化の実効値は、ステップCP4)において判別された前記索引、ステップCP2)において判別された前記置換、およびステップCP1)において判別された前記符号ベクトルに依存している入力ベクトルに適用される。
【００８４】
本発明のもう1つの有利な態様によれば、符号化/復号化および場合によっては1つまたは複数のディクショナリの構築に対して、対応テーブルおよび前述の第2の集合の要素を、特に圧縮符号化/復号化装置のメモリに格納する備えがある。
【００８５】
この点について、本発明はさらに、そのような符号化/復号化装置を目的としている。
【００８６】
本発明はさらに、処理装置、特にコンピュータまたは携帯端末のメモリ、あるいは取り外し可能記憶媒体上に格納されることを意図され、処理装置の読取機構と連携することを意図されたコンピュータプログラム製品を目的としており、このプログラムは前述のディクショナリを構築する方法の実装のための命令を備えている。
【００８７】
本発明はさらに、この種類のプログラムを目的としており、特に、処理装置、特に符号化/復号化装置を組み入れるコンピュータまたは携帯端末のメモリ、あるいは取り外し可能記憶媒体上に格納されることを意図され、処理装置の読取機構と連携することを意図されたコンピュータプログラム製品を目的としており、このプログラムは前述の圧縮符号化/復号化への適用の実装のための命令を備えている。
【００８８】
本発明のその他の特性および利点は、以下の詳細な説明と、図1aおよび図1b以外の上記で説明されている添付の図面を検討すれば明らかとなろう。
【発明を実施するための最良の形態】
【００８９】
最初に図2aおよび図2bを参照すると、本発明の意義の範囲内でディクショナリDiNの2つの主要特性が示されている。
【００９０】
図2aにおいて、所定の次元Nに対して、それぞれ増加解像度r1、r2、...、riのディクショナリD1N、D2N、...、DiNは、相互の内部に埋め込まれている。したがって、最大解像度riのディクショナリDiNは、以下で明らかになるように、低解像度rj(j<i)のディクショナリDjNを判別可能にしうる。PRと示されるこの第1の特性は、以下で「埋め込み特性」と呼ばれている。
【００９１】
ここで図2bを参照すると、所定の次元Nおよび解像度riの任意のディクショナリDiNは、以下の2つの互いに素な集合の和集合である。
○ 挿入規則{Rm}の有限収集に従って、実数の有限集合Aから取り出された(矢印F2)要素xjの低次元N-1のディクショナリDiN-1をコードベクトルYN-1に挿入することにより構築された(矢印F3)コードベクトルYNから成る第1の集合D'iNであって、挿入規則R'(j,k)は、挿入される要素xj(矢印F1)およびこれらを挿入する方法(例えば構築中のベクトルYNの位置kにおいて)を判別する集合
○ 挿入規則の前述の収集に従ってこの有限集合の要素を低次元のコードベクトルに挿入することよって取得できないベクトルY'から成る第2の集合
【００９２】
【数４】
【００９３】
PDと示されるこの第2の特性は、以下で「制御された拡張による部分合成の特性」と呼ばれている。
【００９４】
図2aおよび図2b、さらに前述の本発明の要約において、解像度および/または次元の索引は、一例として、整数1から始まり所定の整数(i、n、または場合によってはN)までである。プログラミングの技術分野、特にC++言語の当業者は、これらの索引がむしろ0から始まり、状況に応じてi-1、n-1、またはN-1に達しうることを理解するであろう。したがって、以下で説明される図3の例において、到達する最大解像度は0から始まりNj-1である。
【００９５】
以下で説明されるのは、2つの構造化特性PRおよびPDを有するディクショナリを構築する方法であり、特にそのように構築されたこれらのディクショナリを構築するアルゴリズムである。2つの構造化特性によって導かれるリンクは、「GLA」または「SKA」のような一般に使用され上記で説明されている繰り返し構築アルゴリズムを適合することによってそのようなディクショナリを構築するアルゴリズムを開発するために有利に使用される。
【００９６】
一般的に、以下のことが示される。
- 異なる解像度および同じ次元の相関関係にあるディクショナリは、埋め込み特性PRを使用して連続的に構築される
- 補足または変種として、制御された拡張による部分合成の特性PDによって相関関係にある異なる次元のディクショナリが構築される
- したがって、2つの構造化特性PDおよびPRを有する様々な次元および解像度のディクショナリが得られる。
【００９７】
一般的に、所定の次元の解像度を増加することにより埋め込みディクショナリを構築するため(PR)、3つの構築の手法が提案される。
【００９８】
第1の手法は、(最小解像度から最大解像度まで)解像度の増加に従ってディクショナリを構築することを備えている。
【００９９】
第2の手法は逆に、(最大解像度から最小解像度まで)解像度の減少に従ってディクショナリを構築することを備えている。
【０１００】
第3の手法は、最小解像度まで解像度を減少し、最大解像度まで解像度を増加することにより中間解像度のディクショナリに基づいてディクショナリを構築することを備えている。このプロセスは、可変解像度のベクトル量子化器の公称解像度が前述の中間解像度である場合に、特に有利である。
【０１０１】
次元jの、ディクショナリの埋め込みの特性PRは、最終的に以下の式によって伝達される。
D0j⊂D1j⊂...Dij⊂Dji+1...⊂DjNj-1
ここで、
- Njは、次元jの解像度の数(または可変レート符号器において可能なレート)である
- 次元jの解像度の集合は
Rj={r0j,r1j,...,rij,rji+1,...,rjNj-1}
ただし、r0j<r1j<...<rij<rji+1<...<rjNj-1
- Dijは、解像度rijの次元jのディクショナリ
- Tijは、解像度
【０１０２】
【数５】
【０１０３】
のディクショナリのサイズ
【０１０４】
図3は、解像度増加に応じたディクショナリの埋め込みを示している。
【０１０５】
低解像度のディクショナリを再更新しない増加解像度に従った構築のアルゴリズムを示す流れ図は、図5に示されている。
【０１０６】
図5を参照すると、最初にi=0およびループ反復索引iter=0に固定する初期化ステップ51および52に続いて、最低解像度のディクショナリD0jを最初に構築する。次いで、最低解像度のディクショナリD0jが固定され、すぐ上の解像度D1jのディクショナリが、以下で説明される従来の構築アルゴリズムの変種を用いて構築される。方法はその後、最大解像度DjNj-1のディクショナリが構築されるまで繰り返される。
【０１０７】
このようにして、ステップ53において、反復プロセスにより、低解像度ri-1のディクショナリDi-1jに(Tij-Ti-1j)ベクトルを付加することにより形成された、初期ディクショナリDij(0)に基づいてディクショナリDijの構築が試みられる。
【０１０８】
クラスを構築するアルゴリズム54は、従来のアルゴリズムと同じであるが、Tijセントロイドを構築するアルゴリズム55は変更される。具体的には、低解像度のディクショナリに属していない(Tij-Ti-1j)セントロイドは再計算されて更新されるが、低解像度のディクショナリの(Ti-1j)セントロイドは再更新されない。変種は、低解像度のすべてのディクショナリの全歪みが減少するかまたは一定を保つ場合に、低解像度のディクショナリのセントロイドの再更新を可能にする。この場合、低解像度のディクショナリは、それに応じて変更される。
【０１０９】
ループ索引iterはその後、i番目の解像度および次元jに依存している(テスト57)数値Niter(i,j)まで増分される(ステップ56)。望ましい解像度Njに到達すると(テスト58)、この解像度Njでディクショナリを取得し(終了ステップ59)、したがって1からNjに及ぶiに対して解像度riのディクショナリDijの集合を取得する。
【０１１０】
解像度減少に従ってディクショナリを構築するため、最初に最高解像度のディクショナリを構築する。次いで後者が固定されると、後者を特定の基準に従って順序付けられているいくつかの部分集合に区分化する。いくつかの基準は、区分化を順序付ける役割を果たすことができる。例えば、それらの基数、学習シーケンス内のそれらの呼び出し(つまりそれらの量子化領域の基数)、全歪みまたはさらに正確にはその歪みの減少へのそれらの寄与に従って部分集合を順序付けることが可能である。様々な基準を組み合わせ、それぞれの重要度に重み付けすることが明らかに可能である。同様に、ディクショナリの区分化は、単純な区分化(各部分集合に1つの要素)からより緻密な区分化まで、様々な方法で実行することができる。この順序付き区分化は、その順序付きクラスの漸進的和集合による埋め込みディクショナリの構築の基礎にある。
【０１１１】
好ましくは、区分化は、(おそらくはその集合自体と等しい)挿入規則の収集の部分集合に基づいた同一のコードベクトルの拡張に基づいて要素を一緒にグループ化することにより制御された拡張による部分合成の特性PDを基にすることができる。
【０１１２】
様々な手順を交互に入れ替えることによって、複数の反復を行うことが可能であることに留意されたい。例えば、埋め込みディクショナリは、解像度増加の手順に従って構築され、次いで解像度減少の手順が適用される。上記の2つの方法を組み合わせることにより、解像度により埋め込まれたディクショナリは、中間解像度riのディクショナリに基づいて構築される。したがって、このi番めのディクショナリは、最初に構築される。次いで、このディクショナリに基づいて、解像度減少による第2の方法を用いて低解像度のディクショナリが構築され、解像度増加による第1の方法を用いて高解像度のディクショナリが構築される。
【０１１３】
一般に、制御された拡張による部分合成による(特性PD)様々な次元のディクショナリを構築するための3つの手法も提案される。
【０１１４】
第1の手法は、次元を増加することである。もう1つの手法は、次元を減少することである。最終的に、最後の手法は、中間次元のディクショナリの構築から始まり、次元の連続的な増加および減少により高次元および低次元のディクショナリを構築することである。制御された拡張による部分合成は、以下で説明される実数および挿入規則の収集の有限集合を判別する手順の微調整をもたらした。ここで、好ましくは、「拡張された」要素の比率(ディクショナリの基数に関して第1の集合の要素の数)が次元と共に増加し、それにより、次元と共に増加する第2の集合の格納のコストを軽減できるようにすることが簡単に示されている。この比率は、アプリケーションの複雑な制約(メモリ/計算処理能力)により先験的に固定されていても、あるいは「自由」のままであってもよい。後者の場合、有利なことに構築アルゴリズムは、以下に示されるように、制御された拡張によって得られた要素から成る第1の集合の要素にとって好都合に働く。
【０１１５】
したがって、制御された拡張による部分合成の第2の特性PDは、最終的に以下の式によって伝達される。
【０１１６】
【数６】
【０１１７】
ここで、
- D'jiは、挿入規則{Rm}の収集に従って、Rの有限集合Aから取り出された要素を低次元のディクショナリのコードベクトルに挿入することによって得られるDijのコードベクトルの集合であり、
-
【０１１８】
【数７】
【０１１９】
は、Djiのその補集合、つまり挿入規則{Rm}の収集に従って、Aの要素を低次元のコードベクトルに挿入することによって得ることのできないDijのコードベクトルの集合である。
【０１２０】
以下で説明されるのは、第2の特性PDを検証するための挿入規則の例である。
【０１２１】
最初に、基本挿入規則の収集が定義される。各基本規則は、ベクトルの所定の位置において成分として実数Aの有限集合の唯一の要素を挿入することである。各基本規則は、2つの正整数の組によって与えられ、一方の整数は、有限集合内の要素の位を示し、もう一方の整数は、挿入の位置を示す。基本規則のこの収集に基づいて、成分を挿入するためのさらに詳細な規則を作成することが可能である。
【０１２２】
もちろん、純粋に可逆的に、低次元N-nに達するように所定の次元Nの有限集合の1つまたは複数の要素を削除することを備える削除規則を定義することができる。
【０１２３】
挿入規則を定義するため、以下のように指定する。
- Naは、Aの基数であり、aiは、そのi番目の要素である。A={a0,a1,...,ai,..,aNa-1},
- R'(im,pm)は、位置pmにおいてaimを挿入することを備える基本挿入規則である。
【０１２４】
したがって、最大次元がjmaxである場合、可能な基本規則の数はNa*jmaxである。例えば、Na=2およびjmax=3の場合、全部で6つの基本規則が数えられる。
R'(0,0):位置0においてa0を挿入
R'(1,0):位置0においてa1を挿入
R'(0,1):位置1においてa0を挿入
R'(1,1):位置1においてa1を挿入
R'(0,2):位置2においてa0を挿入
R'(1,2):位置2においてa1を挿入
【０１２５】
規則R'(0,0)およびR'(0,1)の合成は、位置0および1においてa0を挿入するという規則をもたらす。これは、したがって次元jのコードベクトルに基づいて次元j+2のコードベクトルを取得するできるようにする。
【０１２６】
規則R'(1,0)およびR'(0,2)の合成は、位置0においてa1を、位置2においてa0を挿入するという規則をもたらす。これは、したがって次元jのコードベクトルに基づいて次元j+2のコードベクトルを取得することができるようにする。
【０１２７】
さらに一般的に、n基本規則R'(im,pm)の合成に対して(m=0からn-1)、R(n,{(im,pm)}m=0,n=1)を定義するが、これは次元jのコードベクトルに基づいて次元j+nのコードベクトルを取得することができるようにする。imは必ずしも異なっている必要はなく、対照的にn位置pmが相異なることに留意されたい。好ましくは、位置pmは、例えば以下のような昇順に配置される。すなわち、
Po<P1...<pm...<pn-1
【０１２８】
図4は、低次元のディクショナリのコードベクトルおよび挿入規則に基づくディクショナリのコードベクトルの合成を示している。
【０１２９】
2つの互いに素な集合の和集合である様々な次元のディクショナリを構築するためのいくつかの実施形態も提供され、第1の集合は、挿入規則収集に従って実数の有限集合から取り出された要素を低次元のディクショナリのコードベクトルで挿入することにより構築されたコードベクトルから成り、第2の集合は、挿入規則のこの収集に従って実数のこの有限集合の要素を低次元のコードベクトルで挿入することにより得ることができないベクトルから成る。
【０１３０】
第1の集合は、実数の有限集合(つまりその基数およびその値)とさらに挿入規則の収集の判別を必要とする。
【０１３１】
この有限集合の構築と挿入規則の収集の形成とが以下のように実行される。
- 「演繹的に」:有限集合および挿入規則の収集は、ディクショナリを構築する前に判別される。この選択は、情報源の統計の分析に基づいて、例えば学習シーケンスによって量子化、モデル化されることが好ましい。例えば、有限集合の選択は、情報源の単一次元の確率密度(またはそのヒストグラム)を基にすることができる。
- あるいは「帰納的に」:最初に、制御された拡張による部分合成の規則に従う必要性を課さないすべての次元の解像度によって埋め込まれたディクショナリを構築する。有限集合および挿入規則の収集の選択は、これらの「初期」ディクショナリの統計の検討によって行われる。
【０１３２】
2つの解決策「演繹法」または「帰納法」は、連続および/または組み合わせて使用することができる。例えば、第1の集合および挿入規則の第1の収集は、学習シーケンスの分析によって選択され、次いで、ディクショナリの最初の構築後、これらのディクショナリの分析は、集合Aおよび/または挿入規則の収集の全体的または部分的更新を導くことができる。
【０１３３】
さらに、有限集合および/または挿入規則の収集が、次元に依存する場合も、あるいは依存しない場合もあることに留意されたい。次に、次元の各組(j,j')に固有の収集および/または集合、あるいは次元の相異により固有の収集および/または集合を判別することも、またグローバルな集合を判別することも可能である。繰り返すが、選択は、先験的に、または学習シーケンスおよび/またはディクショナリの統計的分析の後に行われる。
【０１３４】
解像度増加に従ってディクショナリを構築するため、前述のような、ベクトル量子化設計の従来の手順によって最低次元のディクショナリを構築する。次いで、このディクショナリが構築され、すぐ上の次元のディクショナリが、従来の構築アルゴリズムの変種を用いて構築される。低次元のディクショナリに基づいて、すべての可能な初期コードベクトルが、挿入規則を適用することによって作成され、このディクショナリには場合により「自由な」コードベクトル(つまり拡張によっては得られないもの)が補足されることもある。この初期ディクショナリのサイズは、望ましいサイズよりも大きくなりうることに留意されたい。初期ディクショナリに基づいて、ベクトル量子化器を構築する反復アルゴリズムの変種が適用される。クラスは、学習シーケンスの量子化によって構築され、セントロイドは、第1の集合のコードベクトルの制御された拡張の制約に従って更新される。第1の集合のこれらのコードベクトルに対して、挿入によって得られた成分を再計算しないことも、あるいは挿入規則によって得られた成分を戻すように、すべての成分を再計算してこのように得られたコードベクトルを変更することもできる。従ってディクショナリのサイズが望ましいサイズよりも大きい場合、空クラスを除去する。アルゴリズムの最後で、ディクショナリのサイズが望ましい解像度よりも大きい場合、ディクショナリの要素を分類する手順は、第1のコードベクトルのみを保持するように適用される。反復アルゴリズムは、場合によっては再実行される。次いで、高次元のディクショナリの構築に移り、初期ディクショナリは、2つの最小次元の2つのディクショナリに基づいて制御された拡張により構築され、「自由な」コードベクトルが補足されて、ベクトル量子化器を構築する反復アルゴリズムの変種が適用される。次に方法は、最大サイズのディクショナリが構築されるまで繰り返される。
【０１３５】
変種として、減少解像度に従ってディクショナリを構築するため、最初に最大次元のディクショナリを構築する。次に、後者が固定されると、低次元の可能なコードベクトルが抽出される。有利なことに、抽出手順は、これらのコードベクトルの成分としてAの要素を取り出すように、高次元のコードベクトルを変更することによって容易になる。
【０１３６】
補足的な変種において、いくつかの反復が、一方では増加次元に従って、またはもう一方では減少次元に従って、2つの構築を交互に入れ替えることによって有利に実行される。
【０１３７】
制御された拡張の手順を容易にするため、本発明はさらに、コードベクトルの成分の変換を実行することができる。模範的な変換は、高解像度におけるスカラー量子化である。低次元の「ディクショナリ」を構築することは、たとえそれらの次元がベクトル量子化によって直接には使用されない場合であっても、有益である。例えば、スカラー量子化が使用されない場合でも、次元1で始めることが可能である。同様に、中間次元のディクショナリを構築することが有利な場合もある。これらの「ディクショナリ」は、格納および計算の複雑さを軽減するために、制御された拡張の手順によってさらに一層有利に使用される。
【０１３８】
さらに、解像度による埋め込みにより(PR)、ディクショナリを構築するアルゴリズムを、制御された拡張による部分合成によって(PD)構築するアルゴリズムと公正に組み合わせることによって、いくつかの構築方法が開発されうることが示される。アルゴリズムが反復型である場合、様々な技法を交互に入れ替えることができることに留意されたい。例えば、最小次元の最大解像度のディクショナリを構築することによって始め、このディクショナリから解像度減少(特性PR)によって埋め込まれたディクショナリを推定し、次いで特性PDに基づいてすぐ上の次元の最大解像度のディクショナリを構築し、この次元に対して、解像度により埋め込まれたディクショナリを構築し、最大次元のディクショナリ(解像度により埋め込み)が得られるまで繰り返す。
【０１３９】
以下で説明される実施形態において、次元増加および解像度減少に従ってディクショナリの集合{Dji}i=0,...,Nj-1,j=jmin,...,jmaxを構築するためにディクショナリ構築の技法を組み合わせる優先構築が使用される。
【０１４０】
以下で説明されるのは、本発明の意義の範囲内でディクショナリを使用する、デジタル信号(オーディオ、ビデオなど)の圧縮符号化/復号化であり、特にディクショナリの構造(埋め込みおよび制御された拡張による部分合成)を利用する符号化および復号化アルゴリズムである。一般に、符号器および/または復号器におけるメモリ/計算間の妥協の最適化は、アプリケーションの制約に従って取り組まれることが理解されよう。
【０１４１】
一例として、以下で考察されるのは、16kHzでサンプリングされるデジタルオーディオ信号(広帯域)を符号化するために使用される「TDAC符号器」と呼ばれるオーディオ符号器である。この符号器は、様々なレートで動作することができる変換ベースの符号器である。特に、レートは、通信の確立前に固定されるか、または通信の過程でフレームによって異なっていてもよい。
【０１４２】
図6は、このTDAC符号器のブロック図を示している。7kHzで制限され、16kHzでサンプリングされたオーディオ信号x(n)帯域は、320サンプル(20ms)のフレームに分割される。変形離散コサイン変換61は、50%のオーバーラップで640サンプルの入力信号のブロックに適用される(つまり、20msごとのMDCT分析のリフレッシュ)。得られたスペクトルy(k)は、最後の31係数をゼロ化することにより7225Hzに制限される(最初の289係数のみが0と異なる)。マスキングカーブは、マスキングされた係数のゼロ化を行うマスキングモジュール62によって判別される。スペクトルは、不等な幅の32の帯域に分割される。マスキングされた帯域がある場合、それらは信号x(n)の変換された係数の関数として判別される。スペクトルの帯域ごとに、MDCT係数のエネルギーが計算される(基準化因数と呼ばれる)。32の基準化因数は、その後量子化され、符号化されてフレームで送信される信号のスペクトル包絡線を構成する(ブロック63)。この量子化およびこの符号化では、ハフマン符号化を使用する。次いで、可変レートでのスペクトル包絡線の量子化後に残ったビットの可変数が計算される。これらのビットは、スペクトルのMDCT係数のベクトル量子化65に分配される。量子化解除スペクトル包絡線は、帯域的なマスキングしきい値のセットを計算するのに役立ち、このマスキングカーブは、ビットの動的な割り振り64を判別する。帯域ごとおよび量子化スペクトル包絡線に基づくこのマスキングカーブの計算は、バイナリ割り振りに関連する補助情報の送信を回避する。具体的には、復号器は、符号器と同様の方法でビットの動的割り振りを計算する。MDCT係数は、それらの帯域の量子化解除基準化因数によって正規化され、次いで可変次数および可変レートのベクトル量子化器によって量子化される。最後に、スペクトル包絡線およびこれらの符号化されてフレームで送信された帯域正規化係数に関する情報の多重化66によってバイナリ列が構築される。図6における参照67および68はそれぞれ、有声または無声信号x(n)の検出、およびトーンの検出(トーン周波数の判別)の既知のステップ自体に対応することが示されている。
【０１４３】
以下で説明されるのは、TDAC符号器におけるMDCT係数の不等な幅の帯域に基づく可変レートのベクトル量子化器である。帯域的に正規化されたMDCT係数の量子化では、特に、本発明により構築されたディクショナリを使用する。不等な幅の帯域への分割は、実際に、様々な次元のベクトルをもたらす。使用された帯域分割を与える図7aの配列図はさらに、結果として生じた係数のベクトルの次元、つまり第3列に示されるように、係数の数を示している。
【０１４４】
スペクトル包絡線のハフマン符号化後に残ったビットの可変数は、様々な帯域に動的に割り振られる。図7bの配列図は、1から15の範囲にわたる次元jについて、解像度Njの数および次元jの帯域当たりのレートj*Rj(ゆえに帯域当たりの解像度の値)の集合を示している。制御された拡張による部分合成の構造化特性を有利に利用するため、ベクトル量子化器が次元1、2、6、11で構築されたにもかかわらず、これらは任意の帯域幅には対応しないが、その要素はより大きい次元のコードベクトルの作成に役立つことに留意されたい。さらに、大きい次元であっても解像度の細分性が細密であることに留意されたい。
【０１４５】
モジュール62におけるマスキングされた係数のゼロ化は、正規化MDCT係数の分析中に、開始集合A={0}としておよび挿入規則の収集として、基本挿入規則のすべての可能な合成の選択を導く。これは、任意の位置においてゼロを挿入することになる。
【０１４６】
しかし、より細密な分析は、すべての置換およびすべての符号が許可されるタイプIIの、正規化置換コードの和集合で形成されるディクショナリを使用することにより、ディクショナリに追加の構造的制約を課す。タイプIIの各置換コードに対して、最大ベクトルは、辞書学的な意味で、絶対リーダーと呼ばれ、成分の絶対値を降順に順序付けることによって得られる。ディクショナリの構築は、それらの正規化絶対リーダーを判別することになる。制御された拡張をこれらの絶対リーダーに適用することは、最後の成分としてゼロをこれらに挿入することである。
【０１４７】
さらに、歪み基準が固定される。好ましくは、選択される歪み基準はここで、ユークリッド距離である。ディクショナリが正規化されると、量子化される入力ベクトルとのユークリッド距離を最小化するコードベクトルの検索は、結果として、この入力ベクトルとのスカラー積を最大化するコードベクトルを検索することになる。さらに、ディクショナリが置換コードの和集合であれば、入力ベクトルとのスカラー積を最大化するコードベクトルの検索は、結果として、この入力ベクトルの絶対リーダーとのスカラー積を最大化するコードベクトル(降順にランク付けるようにその成分の絶対値を置換することによっても得られる)をディクショナリの絶対リーダーの中で検索することになる。
【０１４８】
以下で定義されているのは、本発明の意義の範囲内の、ベクトル量子化器の設計のための学習シーケンスである。前述のように、量子化器の設計のための学習シーケンスを判別することが好ましい。帯域の基準化因数によって正規化された289のMDCT係数のフレームから成る長いシーケンスは、最初に、広帯域オーディオ信号の多数のサンプルに基づいて取得される。次に、係数の各正規化ベクトルに対して、その絶対リーダーが推定される。様々な次元の絶対リーダーの集合に基づいて、多次元学習シーケンスの2つのカテゴリS0およびS1が作成される。
- S0={S0j}j∈[1,15]、S0jは、j非ゼロ係数を有する絶対リーダーの最初のj成分によって形成されるすべてのベクトルの集合である。したがってS0jは、ゼロ係数をまったく有していない次元jの絶対リーダー、単一のゼロ係数を有する次元j+1の絶対リーダー、2つのゼロ係数を有する次元j+2の絶対リーダー、...15-jのゼロ係数を有する次元15の絶対リーダーから成る。
- S1={S1j}j∈[3,4,5,7,8,9,10,12,13,14,15]、S1jは、j係数を有する帯域のすべての絶対リーダーの集合である。
【０１４９】
例えば、係数(0.;0.6;0.;0.;0.8)の正規化ベクトルに基づいて、シーケンスS15に属するその絶対リーダー(0.8;0.6;0.;0.;0.)およびその絶対リーダーの最初の2つの非ゼロ成分によって形成されるS02の要素(0.8;0.6)を推定する。
【０１５０】
第1のシーケンスのカテゴリは、好ましくは
【０１５１】
【数８】
【０１５２】
のリーダーの初期ディクショナリを判別するために使用される。第2のカテゴリは、好ましくは2つの構造化特性を有する多次元および多解像度のディクショナリを構築するために使用される。
【０１５３】
シーケンスの第1のカテゴリS0に基づいて、いわゆる「k平均アルゴリズム」のような従来のアルゴリズムをシーケンスS0jに適用することにより、各次元j(jは1から15の範囲)の正規化絶対リーダーの最初のディクショナリを取得する。正の実数成分を持つこれらのリーダーは、第1の成分(つまり最大の成分)に関して、成分をあらかじめ決められたしきい値よりも低く抑えることによって変更される。このいわゆる「センタークリッピング」手順は、有利なことに、ゼロを取り出して、低次元のゼロ成分を持たない絶対リーダーを抽出できるようにする。制御された拡張にさらに好都合に働くように、これらの抽出されたリーダーの成分の変換が適用される。この目的のため、整数再構築レベルで間隔1の均一スカラー量子化が後に続くその最小非ゼロ成分によって各リーダーの正規化を使用する(これは各リーダーの成分を最も近い整数に四捨五入することになる)。この変換では、修正正規化因数を距離計算に導入することにより整数の形で絶対リーダーを格納することができるので、さらにメモリにかなりの量の削減をもたらす。取得された、あるいは様々なシーケンスS0jに基づく異なる実数リーダーは、同一の整数リーダーに変換できることに留意されたい。次いで、可能な冗長を除去するため、およびすべての絶対リーダーの集合
【０１５４】
【数９】
【０１５５】
を非ゼロ整数成分で形成するための手順が提供される。ここで、L'0jは、次元jのこれらのリーダーから成る部分集合である。L'0を構築するこの技法は、次元減少に従って、制御された拡張による部分的作成によってディクショナリを構築する技法からその発想を得ている。さらに、事前に行われた集合Aの選択は、L'0のすべてのリーダーが最後の成分として少なくとも1つの「1」を有しているので、そこに要素「1」を付加するように、事後的に検討できることにも留意されたい。
【０１５６】
集合L'0は、埋め込みPRと制御された拡張による部分合成PDとの、2つの構造化特性を所有する、複数の次元および解像度によるベクトル量子化器の設計のためのリーダーの初期ディクショナリの構成の基礎をなす。シーケンスS1に基づいて、これらの量子化器を構築するアルゴリズムは、次元増加および解像度減少を通じて進行する。
【０１５７】
次元jの場合、リーダーの初期ディクショナリL'1jは、L'0jのすべてのリーダーと、集合L'0jのリーダーに(j-j')ゼロを挿入することにより低次元j'(j'<j)のリーダーの制御された拡張によって得られるすべてのリーダーとにより形成される。例えば次元3において、リーダーのディクショナリは、L'03のリーダーが補足されたL'01={(1)},L'02={(11),(21),(31),(41),(51),(91)}に基づく制御された拡張によって構成される。
【０１５８】
各次元jに対して、L'1jによって特徴付けられる置換コードの和集合は、おそらくは望ましい最大解像度よりも大きい、高解像度のディクショナリを構成する。したがって、これらの置換コードは、このディクショナリの自然区分化を実行し、この区分の各クラスは、そのリーダーによって代表される置換コードである。次に、この区分のクラスに対応する最近傍の領域の構築は、シーケンスS1の量子化によって実行される。区分化は、置換コードの基数の増加に従って順序付けられる。置換コードの基数の等式の場合、制御された拡張によって得られたリーダーのコードは、前述のように、L'0jのリーダーのコードに関して好都合である。同じ集合(
【０１５９】
【数１０】
【０１６０】
または
【０１６１】
【数１１】
【０１６２】
のいずれか)に属している2つのクラスの基数の等式の場合、クラスは、それらの量子化領域の基数と全歪みの減少へのそれらの寄与とを組み合わせた基準に従って順序付けられる。そのように順序付けられた置換コードの基数の集合体は、ベクトル当たりの対応するレートと同様に、置換コードごとに計算される。このように順序付けられたL'1jのリーダーの集合をL1jで表す。符号化された索引を、結合したバイナリ列として配置する手順を回避するため、整数の解像度のみを使用するように選択する。
【０１６３】
したがって、図7cの配列を参照すると、解像度により埋め込まれた多解像度ディクショナリは、基数の集合体のレートがすぐ上の整数に最近傍である異なる解像度ごとの最後の置換コードとして選択することによって構成される。L1jによって特徴付けられるディクショナリの解像度が、望ましい最大解像度よりも高い場合、最後の未使用の置換コードは、除去される。DjNj-1のリーダーの最終順序付き集合をLj(⊆L'j)で表す。次元の反復の最後に、L'0の特定のリーダーが{Li}j∈{3,4,5,7,8,9,10,12,13,14,15}のリーダーを構成するために使用されない場合、集合L'0は、それらを除去することにより更新される。この集合を
【０１６４】
【数１２】
【０１６５】
と記す。
【０１６６】
図7cから7eの配列図は、埋め込み特性と制御された拡張による部分合成の特性とによってもたらされるメモリの節約を示している。図7cの配列図は、様々な次元の多解像度によるベクトル量子化器を比較している。第1の量子化器は、単に置換コードの和集合として構築され、第2の量子化器は、その上に解像度による埋め込みの特性を備えている。
【０１６７】
図7cにおいて、
- j:次元
- Nj:次元jの解像度の数
-
【０１６８】
【数１３】
【０１６９】
:ディクショナリDjiのリーダーの数
-
【０１７０】
【数１４】
【０１７１】
:ディクショナリDjnj-1のリーダーの数
-
【０１７２】
【数１５】
【０１７３】
:埋め込み特性のない次元jですべてのディクショナリのリーダーを格納するために必要なメモリ(ワード数単位)
-
【０１７４】
【数１６】
【０１７５】
:埋め込み特性のある次元jですべてのディクショナリのリーダーを格納するために必要なメモリ
【０１７６】
図7dの配列図は、多次元に使用されるこれらの後者の量子化器を、制御された拡張による部分合成の構造化特性も有する量子化器と比較している。
【０１７７】
図7dにおいて、
- j:次元
-
【０１７８】
【数１７】
【０１７９】
:ディクショナリDjnj-1のリーダーの数
-
【０１８０】
【数１８】
【０１８１】
:次元1からjの最大解像度のディクショナリのリーダーの数の和
-
【０１８２】
【数１９】
【０１８３】
:制御された拡張による部分合成の特性のないこれらのリーダーを格納するために必要なメモリ
- Lj:集合L0jのリーダーの数
-
【０１８４】
【数２０】
【０１８５】
:1次元からjのそれらの和
-
【０１８６】
【数２１】
【０１８７】
:制御された拡張による部分合成の特性のある次元1からjのすべてのディクショナリのリーダーを格納するために必要なメモリ
【０１８８】
図7eの配列図は、多解像度および次元によるベクトル量子化器を比較している。第1の量子化器は、単に置換コードの和集合として構築され、第2の量子化器は、その上に解像度による埋め込みと制御された拡張による部分合成との構造化特性を備えている。
【０１８９】
図7eにおいて、
- j:次元
- Nj:次元jの解像度の数
【０１９０】
-
【０１９１】
【数２２】
【０１９２】
:埋め込みの特性または制御された拡張による部分合成の特性のないNj解像度に対して格納される次元jのリーダーの数
【０１９３】
-
【０１９４】
【数２３】
【０１９５】
:これらの2つの特性のない次元jですべてのディクショナリのこれらのリーダーを格納するために必要なメモリ(ワード数単位)
【０１９６】
-
【０１９７】
【数２４】
【０１９８】
:これらの2つの特性のない次元1からjのすべてのディクショナリのリーダーを格納するために必要なメモリ(ワード数単位)
Lj:集合L0jのリーダーの数
【０１９９】
-
【０２００】
【数２５】
【０２０１】
:1次元からjのそれらの和
【０２０２】
-
【０２０３】
【数２６】
【０２０４】
:埋め込みと制御された拡張による部分合成との2つの特性のある次元1からjのすべてのディクショナリのリーダーを格納するために必要なメモリ
【０２０５】
3つの配列図において、最後の列は、メモリ減少係数の有意性を示している。埋め込み特性のみでは、次元3において3、次元7において5、次元15において7よりも大きい係数によってメモリを減少できるようにする。埋め込み特性により、次元jの解像度の集合に対してDjiのすべてのリーダーを格納するのではなく、DjNj-1(Ljのリーダー)のリーダーのみを格納する。図7dの配列図の最後の列に示されているように、制御された拡張による部分合成の追加により、メモリをさらに減少できるようになる。この特性によりもたらされるさらなる節約は、以下のようになる。
- 次元4において1.5倍
- 次元8において3倍
- 次元15において7倍
【０２０６】
図7eにより示されているように、単に置換コードの和集合として構築された量子化器に関して、その上に解像度による埋め込みと制御された拡張による部分合成との2つの構造化特性を備えている量子化器の使用により、次元3において4分の1、次元7において13分の1、次元11を超える次元については35分の1以上メモリを減少させることができる。
【０２０７】
制御された拡張による部分合成特性により、L0のリーダーのみが格納される必要があり、{Lj}のリーダーは、Ljのリーダーの索引からL0のリーダーの索引への対応するテーブルから取り出される。
【０２０８】
ここで、ベクトル量子化器を効果的に実装する方法について説明する。
【０２０９】
次元jおよび解像度riのベクトル量子化器を実装するには、以下の3つの問題を解決することが必要である。
- Djiにおける入力ベクトルの最近傍の検索
- Djiのコードベクトルの索引の検索
- さらに相互の、その索引に基づくDjiのコードベクトルの検索
【０２１０】
索引付けに関する限り、ディクショナリのコードベクトル、タイプIIの置換コードの和集合を索引付けするいくつかの既知の方法があることが示されている。実施形態において採用された番号付けは、Gosset格子の球形コードに索引付けをするために使用された番号付けからその発想を得ている。
【０２１１】
任意の次元j(j∈{3,4,5,7,8,9,10,12,13,14,15})に対して、DjNj-1の各コードベクトルは、その置換コード、その符号の組合せを与えるバイナリ索引、およびその置換コードのその位のオフセット特性によって索引付けされる。置換コードのオフセットは、DjNj-1においてそれに先行する置換コードの基数の集合体である。置換に番号付けする定式の中で、いわゆるSchalkwijk式を選択した。
【０２１２】
DjNj-1のコードベクトルのこの従来の番号付けに加え、Ljのリーダーの索引からL0のリーダーの索引への対応テーブルを使用する。L0のリーダーが格納されると、L0の索引付けの大きな自由がもたらされる。例えば、次元を増加させることにより、非ゼロ整数成分を持つこれらのリーダーを分類することができる。Ljのリーダーxjの各索引mjには、L0のリーダーxj'の索引lmが関連付けられる。この索引lmに基づいて、リーダーxj'の次元j'およびリーダー自体を取り出す。次いでリーダーxjは、xj'の最後の成分として(j-j')ゼロを挿入することにより取り出される。
【０２１３】
図7fの配列図は、L0の最初の23リーダーを示している。図7gの配列図は、各リーダーx3について、これを得るために拡張された次元j'(j'≦j)のL0j'のリーダーxj'を示すことにより、次元3のディクショナリの置換コードのリーダーを示している。付随的に、j=j'であれば、xj'=x3であることが指摘される。
【０２１４】
図7fにおいて、
- l:L0におけるリーダーの索引(516の中から)
- j:その次元
- lj:L0jのリーダーのその索引
【０２１５】
図7gにおいて、
- m3:D3N3の23リーダーの中のリーダーx3の索引
- i:リーダーが属する最小解像度のディクショナリの索引(つまり
【０２１６】
【数２７】
【０２１７】
)
- jri:このディクショナリD3iのベクトル当たりのレート
- j':L0のリーダーxj'の次元(非ゼロ成分の数)
- lm:L0の516リーダーの中からのxj'の索引
【０２１８】
以下で説明されているのは、一般の場合に適した符号化および復号化アルゴリズムであり、追加の構造的制約(置換コードの和集合)が追加された特に有利な事例を後に検討することになる。
【０２１９】
最近傍検索アルゴリズムの複雑さを軽減することを可能にする制御された拡張の特性により、特に導びかれたディクショナリ構造を優先的に使用することが、最初に示されている。特に、同じ挿入規則を有するコードベクトルを一緒にグループ化することができる。例えば以下で詳細に説明されるユークリッド距離の歪み基準の場合、ディクショナリDjiの次元jのLコードベクトル{xjl,l=0,1,...,L-1}が、ディクショナリDi'j-nの次元j-nのLコードベクトルxlj-nに基づいて、同じ挿入規則R(n,{(im,pm)}m=0,n-1)によって取得される場合、入力ベクトルyからのコードベクトルxjlのL距離の計算:
【０２２０】
【数２８】
【０２２１】
は、最初に項
【０２２２】
【数２９】
【０２２３】
を計算し、次にn成分ypmをyに高めることによって得られる次元(j-n)のベクトルy'からコードベクトルxlj-nのL距離を計算:
【０２２４】
【数３０】
【０２２５】
することにより、迅速化することができる。
【０２２６】
前述のように、各次元に対して、格納される必要があるのは最大解像度のディクショナリの一部だけであり、他のコードベクトルは、低次元の最大解像度のディクショナリから取り出された要素と挿入規則とに基づいて推定される。
【０２２７】
これ以降、本発明によるディクショナリ作成方法の使用における圧縮符号化/復号化の詳細な模範的実施形態が示される。
【０２２８】
検討されるすべての次元jについて、すべてのディクショナリの集合{Djl}i=1,...,Njを格納するのではなく、
【０２２９】
【数３１】
【０２３０】
と対応テーブルのみを格納することが、最初に示されている。これらのテーブルは、その索引に基づいてDjNjのコードベクトルを再構築できるようにする。前述のように、これらのテーブルを公式化し、それらを格納するいくつかの方法がある。例えば、検討されるすべての次元jについて、(DjNjのコードベクトルxjの)索引mjごとに、j'、m'、およびlrという3つのスカラー整数値を表にすることができる。ここで、lrは
【０２３１】
【数３２】
【０２３２】
の集合の索引m'の要素に適用される制御された拡張による部分合成によってxjを再構築できるようにする挿入規則の数である。これで対応テーブルは、
【０２３３】
【数３３】
【０２３４】
ワードを格納する必要があるだけである(Tijは、ディクショナリDijのサイズであることが思い起こされる)。多解像度および次元によるベクトル量子化器のディクショナリに適切な格納に関する限り、解像度による埋め込みと拡張による部分合成との2つの構造化特性を備えていないベクトル量子化器の場合は
【０２３５】
【数３４】
【０２３６】
ワードが必要とされるが、これらの2つの構造化特性を備えるベクトル量子化器のディクショナリの格納には、1つの
【０２３７】
【数３５】
【０２３８】
ワードしか必要とされない。つまり、集合
【０２３９】
【数３６】
【０２４０】
のサイズは
【０２４１】
【数３７】
【０２４２】
である。しかし、一般的には、当然ながら集合
【０２４３】
【数３８】
【０２４４】
に対して集合D'jNjが支持されるので、
【０２４５】
【数３９】
【０２４６】
はTjNjよりもはるかに小さい。記憶域の節約についてのいくつかの数値的な例は、後に説明される実施形態において示される。
【０２４７】
入力ベクトルy=(y0,...,yk,...,yj-1)のDjiの最近傍xjを検索することを備える符号化アルゴリズムは、優先的に以下のステップを備えている。
【０２４８】
ステップCO0)は、
すべての索引mj∈[0,Tji[に対して
dmin=VALMAX;mmin=-1;mj=0
である初期化ステップを備えている。
【０２４９】
次のステップCO1)は、索引mjのコードベクトルxjの再構築を備え、優先的に以下のように実行される。
a)DjNjに関連付けられている対応テーブルの3つの索引j'、m'、およびlrの読み取り
b)次元j'および索引m'のベクトルxjの集合
【０２５０】
【数４０】
【０２５１】
の読み込み
c)索引lrの挿入の規則に従って制御された拡張による部分合成の特性のxj'への適用によるコードベクトルxjの再構成
【０２５２】
ステップCO2)は、選択された歪み基準に従ってyとxjとの間の距離d(y,xj)を計算することを備えている。
【０２５３】
次のステップCO3)およびCO4)は、操作CO1)およびCO2)を繰り返して、入力ベクトルからの距離が最小であるベクトルの索引を識別することを備えている。したがって、
* d(y,xj)<dminであればdmin=d(y,xj)かつmmin=mj
* 次にmjを増分する:mj=mj+1
* 終了テストが行われる:
mj<TjiであればステップCO1)に進む
それ以外の場合:停止
【０２５４】
終了ステップCO5)において、入力ベクトルyとの最小距離dminに対応して索引mminが識別されたコードベクトルを装った入力ベクトルyの最近傍であるコードベクトルを判別する。
【０２５５】
したがって、アルゴリズムはステップCO5)に進む:
* 終了
Djiにおけるyの最近傍xjは、索引mminのコードベクトルである。
【０２５６】
Djiのコードベクトルをその索引に基づいて検索することを備える復号化アルゴリズムは、符号化アルゴリズムのステップCO1)によって示されている。特に、復号化は、復号化される索引にはかかわりなく、ステップCO1)のコードベクトルxj(操作c)の完全な再構成を伴うことが示されている。
【０２５７】
一方、符号化では、この再構成は部分的であってもよい。具体的には、ステップCO2)の距離計算における歪み基準を以下の2つの項に分解できる場合、これは省略できることもある。
- 挿入規則の索引にのみ依存しているもの
- もう1つはコードベクトルxj'
【０２５８】
例えば、ユークリッド距離の歪み基準の場合、初期化ステップCO0)において、Djiに使用される索引lrの各挿入規則に対し、距離
【０２５９】
【数４１】
【０２６０】
を事前計算することが可能である(索引lrの挿入規則が位置Pmをめざして(mは0からj-j'-1の範囲)j-j'成分aimを挿入することを備える場合)。ステップCO2)のyとベクトルxj(j',m',lr)との間の距離の計算は、距離
【０２６１】
【数４２】
【０２６２】
を計算することになる。ここで、
- xj'は、ステップCO1)の操作b)において得られたベクトルであり、
- y'は、j-j'成分ypmをyに高めることにより得られる次元j'のベクトルであり、
- 距離d(y,xj)は、単純な合計d(y,xj)=dlr+d(y',xj')によって得られる。
【０２６３】
これは、上記で、符号化プロセス中に、(完全に再構築されたコードベクトルxjの次元となるであろう)次元jよりも低い次元j'のコードベクトルxj'の再構築を「部分的」と定義した理由である。
【０２６４】
さらに、ベクトルxj'が(様々な挿入規則により)Dijのコードベクトルの合成に数回介入する場合、初期化ステップにおいて項d(y',xj')を事前計算することもできる。したがって、格納(一時)/符号化の複雑さの間の妥協は、アプリケーションの要件に従って調整することができる。
【０２６５】
同様に、索引付けの格納/複雑さの間の妥協も、アプリケーションの要件に合わせて調整することが得きる。
【０２６６】
符号化に関しては、前述のような置換コードの和集合の追加の制約の場合、次元8の通常のGosset格子の球形コードに対して、最近傍検索アルゴリズムは、タイプIIの置換コードの和集合により、これらのディクショナリに単純化することによって容易に一般化する。
【０２６７】
そのような検索アルゴリズムは、特に以下の文献において説明されている。
- 「Algorithme de Quantification Vectorielle Algebrique Spherique par le Reseau de Gosset E8」、C.Lamblin、J.P.Adoul、Annales Des Telecommunications、no 3-4、1988年["Spherical algebraic vector quantization algorithm by the E8 Gosset lattice"]
【０２６８】
第1の単純化は、奇数成分を持つGosset格子の置換コードによって所有されないタイプIIの置換コードの符号の「自由さ」によってもたらされる。第2の単純化は、スカラー積の計算のための各リーダーの非ゼロ成分の数の検討によってもたらされる。これは、符号化アルゴリズムによって制御された拡張による部分合成の特性により生じた構造の利用を示している。最後の変更は、L0のリーダーの整数形式での格納を考慮し、それにより、厳密に正整数成分を持つこれらのリーダーのユークリッドのノルムの逆数と等しい修正係数のスカラー積の計算への導入に至る。
【０２６９】
以下に説明されるのは、ディクショナリDijの次元jの入力ベクトルyの最近傍の検索が、本発明の2つの構造化特性に加えて、置換コードの和集合として前述の構造を使用する実施形態である。
【０２７０】
3つの追加のステップが、グローバルに提供される。
- 符号化されるベクトルの絶対リーダー
【０２７１】
【数４３】
【０２７２】
および符号ベクトルεを判別する(ステップCP1)およびCP2))ための(前述の再構築ステップCO1)の前の)2つの予備ステップ
- ディクショナリのその最近傍の位を計算する(ステップCP5))ための最後のステップ
【０２７３】
前述の検索は、もはやDijのTijコードベクトルの中ではなく(つまり、もはやmj∈[0,Tji[ではなく)、DijのLDjiリーダーの集合Lj(i)にわたってのみ実行される(mj∈[0,
【０２７４】
【数４４】
【０２７５】
、
【０２７６】
【数４５】
【０２７７】
はDijのリーダーまたは置換コードの数)。
この実施形態において、Dijのyの最近傍の検索は、(Ljの
【０２７８】
【数４６】
【０２７９】
最初のリーダーの中から)集合Lj(i)の
【０２８０】
【数４７】
【０２８１】
の最近傍を最初に検索することになる。前述のように、これらのリーダーを完全に再構築する必要はなく(ステップCO1)の操作c))、歪み基準(ここでは変更されたスカラー積)が各リーダーの非ゼロ成分についてのみ計算される。したがって、各リーダーに対して、L0のリーダーxj'の索引lmとLjのリーダーxjの各索引mjとを関連付けるLjのリーダーの索引からL0のリーダーの索引への対応テーブルを使用して、L0の対応するリーダーを判別すれば十分である。
【０２８２】
次いでアルゴリズムは、優先的に、以下の例に従って実行する。
* ステップCP1):
【０２８３】
入力ベクトルy=(y0,...,yk,...,yj-1)の、その絶対ベクトル|y|=(|y0|,...,|yk|,...,|yj-1|)への通過、およびその符号ベクトルε=(ε0,...,εk,...,εj-1)(yk≧0の場合εk=1、それ以外の場合εk=-1)への通過。
* ステップCP2):
【０２８４】
成分を降順に配置するようにその成分を置換することによる|y|のリーダー
【０２８５】
【数４８】
【０２８６】
の検索
* ステップCP3):
* ステップCo0'):初期化:
すべての索引mj∈[0,
【０２８７】
【数４９】
【０２８８】
に対して
【０２８９】
【数５０】
【０２９０】
* ステップCO1'):索引mjのリーダーの再構築:
a)L0のリーダーとLjのリーダーとを関連付ける対応テーブルにおいて、Ljの索引mjのリーダーに関連付けられているリーダーxjの索引lmの読み取り、次いでリーダーxj'の次元j'の判別および修正係数αの読み取り(
【０２９１】
【数５１】
【０２９２】
)
b)次元j'および索引lmのリーダーxj'の集合L0の読み込み
* ステップCO2')
【０２９３】
【数５２】
【０２９４】
とxj'の間の変更されたスカラー積の計算:
【０２９５】
【数５３】
【０２９６】
次のステップは、操作CO1')およびCO2')を繰り返して、入力ベクトルの絶対リーダーとの変更されたスカラー積が最大であるコードリーダーの索引を識別することを備えている。したがって:
【０２９７】
【数５４】
【０２９８】
であれば、
【０２９９】
【数５５】
【０３００】
かつmmax=mj
* 次に、mjを増分する:mj=mj+1
* 終了テスト
【０３０１】
【数５６】
【０３０２】
であればステップCO1')に進む、それ以外の場合は停止
【０３０３】
この終了ステップにおいて、ステップCP3)で見出された置換コードmmaxの数、ステップCP2)で実行された置換の位、およびステップCP1)で判別された符号ベクトルに基づいて、置換コードの和集合の索引付けの手順により、Djiのyの最近傍の索引を計算する。
【０３０４】
ステップCP2)は迅速化できることに留意されたい。具体的には、nijがLj(i)のリーダーの非ゼロ成分の最大数である場合、|y|のnij最大成分を検索することで十分である。望ましい格納/複雑さの妥協に応じて、ステップCP3)のいくつかの変種がある。計算の数を最小化したい場合には、L0のすべてのリーダーに対して、単にそれらの次元j'およびそれらの修正係数を表形式にすることができる。ステップCP3)で言及された次元j'の判別は、この場合、対応テーブルを読み取ることを備えている。逆に、メモリを軽減することを望む場合、この判別は、索引lmに基づいて実行される。同様に、修正係数は、リーダーxj'の読み取り後に計算することができる。
【０３０５】
したがって、置換コードの和集合としての構造を使用して、ディクショナリDijの次元jの入力ベクトルyの最近傍を検索するアルゴリズムは、優先的に以下のように要約することができる。
CP1)入力ベクトルy=(y0,...,yk,...,yj-1)から、その絶対ベクトル|y|=(|y0|,...,|yk|,...,|yj-1|)へ、およびその符号ベクトルε=(ε0,...,εk,...,εj-1)(yk≧0の場合εk=1、それ以外の場合εk=-1)へ通過する
CP2)成分を降順に配置するようにその成分を置換することによって|y|のリーダー
【０３０６】
【数５７】
【０３０７】
を検索する
CP3)Dijのリーダーの集合Lj(i)の(実際は、MijをDijの置換コードの数に置き換えることによりLjのMji最初のリーダーの中から)
【０３０８】
【数５８】
【０３０９】
の最近傍を検索する。前述のように、このステップは、Ljのリーダーの索引からL0のリーダーの索引への対応するテーブルによって示されるL0のMijリーダーのリストの中で変更されたスカラー積を最大化するL0のリーダーを検索することになる。L0のリーダーxj'の次元がj'(j'がj以上)である場合、
【０３１０】
【数５９】
【０３１１】
とのそのスカラー積の計算は、
【０３１２】
【数６０】
【０３１３】
の最初のj'成分でのみ実行され、次いでxj'のユークリッドのノルムの逆数が乗じられる。
CP4)以前のステップで見出された置換コードの数、ステップCP2)で実行された置換の位、およびステップCP1)で判別された符号ベクトルに基づいて、置換コードの和集合の索引付けの手順により、Dijのyのこの最近傍の位の索引を計算する。
【０３１４】
要するに、ステップCP2)は迅速化することができる。具体的には、nijがLj(i)のリーダーの非ゼロ成分の最大数である場合、|y|のnij最大成分を検索することで十分である。
【０３１５】
ここで、一般的な意味の範囲内で、前述の置換コード和集合索引付けを有利な実施形態として必ずしも限定的に使用することなく、復号化アルゴリズムについて説明する。復号化アルゴリズムは、優先的に、以下の形式をとる。
【０３１６】
受け取った索引mjに基づいて、この索引が
【０３１７】
【数６１】
【０３１８】
またはD’jNj-1に属しているコードベクトルに対応するかどうかを判別する。
【０３１９】
第1の場合、mjは
【０３２０】
【数６２】
【０３２１】
の一意の索引に関連付けられており、コードベクトルは、対応テーブルの簡単な読み取りを通じて取得される。
【０３２２】
第2の場合、mjは要素
【０３２３】
【数６３】
【０３２４】
および挿入規則を指し示す。
【０３２５】
xjmjがD'jNj-1またはその補集合のいずれに属しているかの判別は、様々な方法で実行することができる。例えば、索引ごとにバイナリ表示を使用することができる。各解像度riに対して、D'jiに属する制御された拡張により得られた要素で始まり、
【０３２６】
【数６４】
【０３２７】
に属する「自由な」要素が後に続く、Djiの補集合Dji-1の要素を索引付けすることも可能である。次いでD'jNj-1または
【０３２８】
【数６５】
【０３２９】
における帰属関係は、簡単なテストを通じて開始される。同様に、挿入規則は、明示的に索引付けされるか、あるいはそれ以外である。
【０３３０】
例えば、以下で説明される実施形態において、挿入規則は、索引に基づいて黙示的に取り出される。さらに、格納/索引付けの複雑さの妥協は、アプリケーションの要件に応じて調整することができることも理解されよう。
【０３３１】
ここで、置換コードの和集合により定義される追加の制約の特殊な事例に戻る。
【０３３２】
優先的に、復号化アルゴリズムは、さらにLjのリーダーの索引からL0のそれまでの対応テーブルを使用して、以下の文献からその発想を得ている。
- 「Algorithme de Quantification Vectorielle Algebrique Spherique par le Reseau de Gosset E8」、C.Lamblin、J.P.Adoul、Annales Des Telecommunications、No.3-4、1988年
【０３３３】
Djiのコードベクトルの索引に基づいて、Lj(i)のそのリーダーの索引、その置換コードのその位、およびその非ゼロ成分の符号を判別する。次いで、対応テーブルは、メモリに格納されているテーブルの簡単な読み取りを通じて得られるL0のリーダーの索引、および復号化コードベクトルを正規化できるようにするその正規化係数をもたらす。
【０３３４】
本発明のもう1つの模範的な実装は、以下に示される。この例はまた、TDACタイプ変換ベース符号器に基づいているが、16kHzでサンプリングされるデジタルオーディオ信号を符号化するために広帯域のTDAC符号器を使用する前述の例に反して、32kHzでサンプリングされ帯域幅15kHz(FM帯域)のデジタルオーディオ信号を符号化するために使用するものである。
【０３３５】
この符号器の原理は、16kHzのTDAC広帯域符号器の原理と類似している。16kHzで帯域制限され、32kHzでサンプリングされたオーディオ信号はさらに、20msのフレームに分割される。これは、MDCT変換後に、640の係数の取得をもたらす。スペクトルは、不均等の幅の52帯域に分割され、広帯域の分割は、広帯域TDAC符号器によって行われる分割と同一である。
【０３３６】
図8aの配列図は、使用された帯域分割、および結果として生じた係数のベクトルの次元(第3列に示される係数の数に対応)を示している。
【０３３７】
スペクトル包絡線の量子化はさらに、ハフマン符号化を使用し、残りの可変レートは、このスペクトル包絡線の量子化解除バージョンに基づいて係数に動的に割り振られる。
【０３３８】
MDCT係数の量子化では、本発明により構築されたディクショナリを使用する。前述の場合のように、ディクショナリは、置換コードの和集合としても構築される。15未満の次元については、ベクトル量子化器は、広帯域のベクトル量子化器と同様である。したがって、次元16、17、18、19、20、および24のディクショナリを構築する。次元24の場合、この構造はさらに、デカルト積の構造と組み合わされた。24係数の最後の上位帯域は、次元12の2つのベクトルに分割される。一方は偶数係数から成り、もう一方は偶数係数から成る。ここで、次元12に対して構築されたベクトル量子化器が使用された。
【０３３９】
図8bの配列図は、異なる解像度の数、および次元1から24に対するそれらの値を示している。
【０３４０】
したがって本発明は、可変レートおよび可変次元におけるベクトル量子化の問題に効果的な解決策を提供する。本発明は同時に、様々な次元および解像度に対して、ディクショナリが前述の構造化特性PRおよびPDを備えるベクトル量子化器を提供することにより、可変解像度および可変次元の2つの問題を解決する。
【０３４１】
所定の次元に対して、ディクショナリの埋め込みは、一方では、解像度の関数として歪みの局所的減少を保証し、もう一方では、低解像度のディクショナリを格納する必要がないので格納に必要とされるメモリの量を著しく減少し、これらのディクショナリのすべての要素は、実際に最大解像度のディクショナリ内にある。図1aおよび図1bのツリーとして構築されたベクトル量子化器と比較すると、ディクショナリを埋め込むという選択は、したがってすでに、解像度増加に応じた局所的歪みの減少の保証、および格納の軽減という2つの利点をもたらしている。さらに、必要に応じて、ビットよりも小さい細分性による解像度の優れた精密さを可能にし、必ずしも2乗とは等しくないサイズのディクショナリの選択を容易にする。この解像度の精密な細分性は、可変次元および/または可変解像度の複数のベクトルが、索引をバイナリ列として配置するアルゴリズムをこれらの非整数ベクトルベースのレート量子化器に関連付けることによってフレームごとに量子化される場合に、特に有利である。
【０３４２】
ディクショナリの埋め込み特性PRは、最大解像度のディクショナリを格納することのみが必要であることを意味している。第2の特性PDにより、記憶装置の量はより一層減少する。具体的には、最大解像度のディクショナリの要素の一部は、あらかじめ決められた挿入規則{Rm}を考慮して最大解像度であるが低次元のディクショナリから取り出される要素から推定されるので格納される必要はない。このように構造化された要素の比率は、容易に適合可能であり、記憶装置の量を微細に調整できるようになる。
【０３４３】
これらの2つの特性PRおよびPDにより導かれた構造はゆえに、必要な記憶装置を有利に減少させることができる。前述の従来技術を参照して導入部ですでに言及してあるような、追加の構造的制約をディクショナリに課すことによって、記憶装置の減少はさらに一層顕著となる。好ましい実施形態において、例えば球面ベクトル量子化器の使用、前述のデカルト積構造と適宜組み合わされた置換コードの和集合などの提供がある。
【０３４４】
代数ベクトル量子化器と比較すると、2つの特性によって導かれるディクショナリのこの構造は、次元の選択に関しても、解像度の選択に関しても、膨大な設計の柔軟性をもたらす。さらに、これらのベクトル量子化器は、符号化される情報源の統計に適合するので、これにより代数ベクトル量子化において必須である「ベクトル圧伸」の扱いにくい設計の問題を回避して、符号化される情報源の分布が均一になる。
【図面の簡単な説明】
【０３４５】
【図１Ａ】ツリー構造のベクトル量子化器を表す図である。
【図１Ｂ】ツリー構造のベクトル量子化器を表す図である。
【図２Ａ】所定の次元Nに対して、本発明の意義の範囲内でディクショナリの埋め込みの特性を示す図である。
【図２Ｂ】本発明の意義の範囲内でディクショナリの制御された拡張による部分的合成の特性を示す図である。
【図３】解像度増加に応じたディクショナリの埋め込みを示す図である。
【図４】低次元のディクショナリのコードベクトルおよび挿入規則に基づくディクショナリのコードベクトルの合成を示す図である。
【図５】低解像度のディクショナリを再更新しない埋め込みディクショナリの解像度増加に従う構築を示す図である。
【図６】「TDAC」符号器を示すブロック図である。
【図７Ａ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、32の帯域への分割を示す配列図である。
【図７Ｂ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、次元ごとの解像度を示す配列図である。
【図７Ｃ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、埋め込み特性により提供されるメモリゲインを示す配列図である。
【図７Ｄ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、埋め込みおよび制御された拡張の2つの特性により提供されるメモリゲインを示す配列図である。
【図７Ｅ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、これらの2つの特性を使用しないディクショナリの格納に必要なメモリサイズに関し、それぞれ次元およびレートに応じて2つの構造化特性によって提供されるメモリゲインを示す配列図である。
【図７Ｆ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、次元1、2、および3の集合L0の第1のリーダーを示す配列図である。
【図７Ｇ】本発明の意義の範囲内で、ベクトル量子化器を使用するブロードバンドTDAC符号器について、次元3のディクショナリの置換コードのリーダーを示す配列図である。
【図８Ａ】ＦMバンドTDAC符号器について、52の帯域への分割を示す配列図である。
【図８Ｂ】ＦMバンドTDAC符号器について、次元ごとの解像度を示す配列図である。
【符号の説明】
【０３４６】
53 初期ディクショナリDij(0)を構築 ディクショナリDi-1jに(Tij-Ti-1j)ベクトルを追加
54 クラスの構築
55 (Tij-Ti-1j)セントロイドを構築
59 終了
62 マスキング
63 スペクトル包絡線の符号化
64 ビットの動的割り振り
65 係数の量子化
67 v/nv検出
68 トーンの検出
【図１ａ】
【図１ｂ】
【図２ａ】
【図２ｂ】
【特許請求の範囲】
【請求項１】
可変次元のコードベクトルを備え、可変解像度を定義する可変レートにおけるベクトル量子化により、デジタル信号の圧縮符号化および/または復号化のための装置において使用することを意図されたディクショナリであって、
- 一方においては、所定の次元に対して、解像度増加の中間埋め込みディクショナリと、
- 一方においては、所定の次元に対して、
・あらかじめ決められた挿入規則の有限収集に従って、実数の有限集合から取り出された要素を、低次元のディクショナリのコードベクトルに挿入することによって構築されたコードベクトルから成る第1の集合と、
・挿入規則の前記収集に従って前記有限集合の要素の低次元のコードベクトルへの挿入によって取得できないコードベクトルから成る第2の集合との和集合を備えることを特徴とするディクショナリ。
【請求項２】
挿入規則の前記収集は、ベクトルの所定の位置において成分を装って実数の有限集合の単一要素を挿入することを備える基本規則に基づいて定式化されることを特徴とする請求項1に記載のディクショナリ。
【請求項３】
各基本規則は、
- 前記有限集合の要素の位と、
- 挿入の位置とを表す2つの正整数の組によって定義されることを特徴とする請求項2に記載のディクショナリ。
【請求項４】
前記ディクショナリは、可変次元のコードベクトルを備え、可変解像度を定義する可変レートにおけるベクトル量子化により、デジタル信号の圧縮符号化および/または復号化のために装置において使用することを意図され、
所定の次元に対して、
a)第1の集合は、あらかじめ決められた挿入/削除規則の有限収集に従って、実数の有限集合から取り出された低/高次元要素のディクショナリのコードベクトルに/から挿入/削除することによって形成されたコードベクトルから成り、
b)第1の中間のディクショナリは、前記所定の次元に対して、少なくとも前記第1の集合が構築されることを備え、
c)前記ディクショナリを少なくとも1つの所定の解像度で使用するように適合するため、第2の最終的なディクショナリが、中間ディクショナリに基づいて、増加/減少解像度のディクショナリの埋め込み/簡略化により構築され、増加解像度のディクショナリは最小解像度のディクショナリから最大解像度のディクショナリまで中間埋め込みされる、請求項1から3のいずれか一項に記載のディクショナリを形成する方法。
【請求項５】
所定の次元Nに対して、
aO)前記所定の次元Nよりも低い初期次元nの初期ディクショナリが取得され、
a1)あらかじめ決められた挿入規則の有限収集に従って、実数の有限集合から取り出された要素を初期ディクショナリのコードベクトルに挿入することによって形成された次元n+iのコードベクトルから成る第1の集合が構築され、
a2)挿入規則の前記収集による前記有限集合の要素の初期ディクショナリのコードベクトルへの挿入によって取得できない次元n+iのコードベクトルから成る第2の集合が提供され、
a3)前記第1の集合および前記第2の集合の和集合から成る次元n+iの中間ディクショナリが構築され、
ステップa1)からa3)は、前記中間ディクショナリが初期ディクショナリを装い、前記所定の次元Nまで、多くともN-n-1回繰り返される、請求項4に記載の方法。
【請求項６】
所定の次元Nに対して、
a'0)前記所定の次元Nよりも高い初期次元nの初期ディクショナリが取得され、
a'1)次元n-iの第1の集合は、あらかじめ決められた削除規則の有限収集に従って、次元nのディクショナリからの次元n-iの可能なコードベクトルの選択および抽出により構築され、
a'2)削除規則の前記収集による前記有限集合の要素の初期ディクショナリのコードベクトルからの削除によって取得できない次元n-iのコードベクトルから成る第2の集合が提供され、
a'3)前記第1の集合および前記第2の集合の和集合から成る次元n-iの中間ディクショナリが構築され、
ステップa'1)からa'3)は、前記中間ディクショナリが初期ディクショナリを装い、前記所定の次元Nまで、多くともn-N-1回繰り返される請求項4に記載の方法。
【請求項７】
それぞれ次元1からNまでのN個の連続するディクショナリは、次元nの初期ディクショナリに基づいて、次元n+1からNに対するステップa1)からa3)の繰り返しの実装を通じ、次元n-1から1に対するステップa'1)からa'3)の繰り返しの実装を通じて取得される請求項5および6に記載の方法。
【請求項８】
挿入/削除規則の前記収集は、ベクトルの所定の位置において成分を装って実数の有限集合の単一要素を挿入/削除することを備える基本規則に基づいて定式化される請求項4から7のいずれか一項に記載の方法。
【請求項９】
各基本規則は、
- 前記有限集合の要素の位と、
- 挿入/削除の位置とを表す2つの正整数の組によって定義される請求項8に記載の方法。
【請求項１０】
前記有限集合および挿入/削除規則の前記収集は、量子化される情報源の分析によりディクショナリを構築する前に、演繹的に定義される請求項4から9のいずれか一項に記載の方法。
【請求項１１】
前記情報源は好ましくは学習シーケンスによってモデル化され、前記有限集合および挿入/削除規則の前記収集の定義は前記情報源の統計的分析によって達成される請求項10に記載の方法。
【請求項１２】
前記有限集合は前記情報源の単一次元の確率密度の推定によって選択される請求項10および11のいずれか一項に記載の方法。
【請求項１３】
前記有限集合および挿入/削除規則の前記収集は、ディクショナリの構築後に、連続解像度のディクショナリの埋め込み/単純化により帰納的に定義され、後にはこのように構築されるこれらのディクショナリの統計的分析が続く請求項4から9のいずれか一項に記載の方法。
【請求項１４】
-挿入/削除規則の第1の集合および第1の収集は、1つまたは複数の中間ディクショナリを形成するように、学習シーケンスの分析により演繹的に選択され、
-前記第1の集合および/または挿入/削除規則の前記第1の収集の少なくとも一部は、前記1つまたは複数の中間ディクショナリの帰納的分析によって更新され、
-必要に応じて、前記1つまたは複数の中間ディクショナリを形成するコードベクトルの集合の少なくとも一部も更新される請求項10および13に記載の方法。
【請求項１５】
ステップc)は、
c0)前記所定の解像度rNよりも低い初期解像度rnの初期ディクショナリが取得される操作と、
c1)初期ディクショナリに基づいて、初期解像度rnよりも高い解像度rn+1の中間ディクショナリが構築される操作と、
c2)所定の解像度rNが達成されるまで、操作c1)が繰り返される操作とを備えている請求項4から14のいずれか一項に記載の方法。
【請求項１６】
操作c1)の繰り返しごとに、クラスおよびセントロイドの構造が提供され、そこで現行解像度riよりも高い解像度のディクショナリに少なくとも属しているセントロイドが再計算されて更新される請求項15に記載の方法。
【請求項１７】
現行解像度riよりも低い解像度のディクショナリに属しているセントロイドは、低い解像度のすべてのディクショナリの全歪みが1つの更新からその次の更新で減少する場合に限り更新される請求項16に記載の方法。
【請求項１８】
ステップc)は、
c'0)前記所定の解像度rNよりも高い初期解像度rnの初期ディクショナリが取得される操作と、
c'1)初期ディクショナリに基づき、初期ディクショナリをあらかじめ決められた基準に従って順序付けられた複数の部分集合に分割することによって、初期解像度rnよりも低い解像度rn-1の中間ディクショナリが構築される操作と、
c'2)所定の解像度rNが達成されるまで、操作c'1)が繰り返される操作とを備えている請求項4から14のいずれか一項に記載の方法。
【請求項１９】
前記あらかじめ決められた基準は、部分集合の基数、学習シーケンス内の部分集合の呼び出し、全歪みまたは好ましくはその歪みの減少に対する部分集合の寄与の中から選択される請求項18に記載の方法。
【請求項２０】
前記区分化では前記挿入/削除規則の少なくとも一部を使用する請求項18および19のいずれか一項に記載の方法。
【請求項２１】
それぞれの解像度r1からrNのN個の連続ディクショナリは、中間解像度rnの初期ディクショナリに基づいて、解像度増加rn+1からrNに対してステップc1)の繰り返し実装により、解像度減少rn-1からr1に対してステップc'1)の繰り返し実装を通じて取得される請求項15および18に記載の方法。
【請求項２２】
コードベクトルの所定の次元Nで使用するように前記ディクショナリを適合するため、一方でステップa)およびb)、一方でステップc)は、実質上逆転され、
- ステップc)において、依然として次元N'であるがより高い/低い解像度rNである第1の中間のディクショナリが、前記第1のディクショナリの解像度rNを実質的に獲得するように、増加/減少解像度のディクショナリの埋め込み/簡略化により、解像度rnおよび次元N'の初期ディクショナリに基づいて構築され、
- ステップa)において、所定の次元Nを獲得するため、あらかじめ決められた挿入/削除規則の有限収集に従って、実数の有限集合から取り出された前記所定の次元N要素よりも低い/高い次元N'の第1のディクショナリのコードベクトルに/から挿入/削除することによって形成されたコードベクトルから成る第1の集合が構築され、
- ステップb)において、解像度rNへの最終的な適合の可能なステップに続いて、少なくとも前記第1の集合からなる第2の最終のディクショナリが前記所定の次元Nに対して構築されるようになっている請求項4から21のいずれか一項に記載の方法。
【請求項２３】
各々索引(lr)によって識別された挿入/削除規則の前記収集は、これを最後にメモリ内に格納されており、所定の次元に対して、
- 前記第2の集合は、挿入/削除規則の前記収集に従って、所定の次元よりも低い/高い次元のコードベクトルへの挿入/削除の適用により取得することができないコードベクトルを備え、
- さらに、少なくとも1つの対応するテーブルは、挿入/削除規則の索引および前記第2の集合の要素を識別する索引を使用して、所定の次元のディクショナリの任意のコードベクトルを再構成できるようにし、
それにより、前記所定の次元のディクショナリの完全な格納は、前記第2の集合の要素およびリンクを、これらの要素および関連付けられている挿入/削除規則へのアクセスのために対応するテーブルに単に格納することによって回避できるようにする請求項4から22のいずれか一項に記載の方法。
【請求項２４】
対応テーブルは、以下のものを表す3つの整数スカラー値の集計を通じて、現行次元(j')の第2の集合内の現行索引(m')の要素に基づいて再構築することのできる所定の次元(j)のディクショナリ(DjNj)のコードベクトル(xj)の索引(mj)ごとに、前もって定式化され、
- 前記第2の集合の現行次元(j')
- 第2の集合の要素の現行索引(m')
- 挿入/削除規則の索引(lr)
この挿入/削除規則は少なくとも、前記現行索引(m')および前記現行次元(j')の要素に挿入/削除を適用することによって、所定の次元(j)のディクショナリ(DjNj)の前記コードベクトル(xj)を再構成することに寄与する請求項23に記載の方法。
【請求項２５】
可変解像度を定義する可変レートにおけるベクトル量子化により、デジタル信号の圧縮符号化/復号化において、所定の次元(j)のディクショナリ(Dij)内の入力ベクトルy=(y0,...,yk,...,yj-1)の最近傍であるコードベクトル(x')について検索が行われ、
CO1)検索される前記コードベクトル(xj)の現行索引(mj)に対し、前記ディクショナリを定式化できるようにする対応テーブルに表示される索引(j',m',lr)の事前読み取りを少なくとも通じて、前記現行索引(mj)に対応する索引(m')のコードベクトルの少なくとも部分的な再構築と、
CO2)少なくとも符号化において、入力ベクトルとステップC01)において再構成されたコードベクトルとの間の距離の計算と、
CO3)少なくとも符号化において、前記ディクショナリのすべての現行索引に対して、ステップC01)およびC02)の繰り返しと、
CO4)少なくとも符号化において、ステップC02)の繰り返しの1つの過程で計算された入力ベクトルとの距離(Dmin)が最も小さい、少なくとも部分的に再構成されたコードベクトルの索引(mmin)の識別と、
CO5)少なくとも復号化において、索引(mmin)がステップC04)において識別されたコードベクトル(xj)を装った入力ベクトル(y)の最近傍の決定のステップとを備える請求項23および24のいずれか一項に記載の方法の実装を通じて取得されるディクショナリの使用。
【請求項２６】
ステップCO1)は、少なくとも復号化において、
C011)対応テーブル内での、前記第2の集合および挿入/削除規則へのリンクを表す索引の読み取りであって、
- 前記第2の集合の部分集合の現行次元の索引と、
- 前記部分集合の要素の現行索引と、
- 前記要素に基づき、所定の次元のディクショナリのコードベクトルの構築のための適切な挿入/削除規則の索引とを含む索引の読み取りとを含む読み取りと、
CO12)現行次元によって識別される部分集合内での、その現行索引によって識別される前記要素の読み取りと、
CO13)ステップC012)において読み取られた前記要素に、ステップC011)において読み取られたその索引によって識別された適切な挿入/削除規則を適用することによる、前記所定の次元へのコードベクトルの完全な再構成とを備える請求項25に記載の使用。
【請求項２７】
符号化において、
* ステップC01)は、
CO11)対応テーブル内での、前記第2の集合および挿入/削除規則へのリンクを表す索引の読み取りであって、
- 前記第2の集合の部分集合の現行次元の索引と、
- 前記部分集合の要素の現行索引と、
- 所定の次元のディクショナリのコードベクトルの構築のための適切な挿入/削除規則の索引とを含む読み取りと、
C012)現行次元によって識別される部分集合内での、その現行索引によって識別される前記要素の読み取りとを備え、
* ステップC02)において、前記距離は、
- 挿入/削除規則の索引と、
- その現行索引によって識別される部分集合の要素の関数として推定された歪み基準の関数として計算され、
これにより、単に復号化のために完全な再構築を保持しておくことによって、ステップC01)の前記所定の次元を有するコードベクトルの部分的な再構築のみを可能にする請求項25に記載の使用。
【請求項２８】
置換コードの和集合に従って補足構造化特性がさらに提供され、置換コードの前記和集合の索引が使用され、
CP1)入力信号に基づき、絶対ベクトル|y|=(|y0|,...,|yk|,...,|yj-1|)および符号ベクトルε=(ε0,...,εk,...,εj-1)、εk=±1によって定義される入力ベクトルy=(y0,...,yk,...,yj-1)が形成され、
CP2)ベクトル|y|の成分は、リーダーベクトル
【数１】
を取得するため、置換によって、値を減少することによりランク付けされ、
CP3)次元jのディクショナリDjiのリーダーの中からリーダーベクトル
【数２】
の最近傍xj'が判別され、
CP4)ディクショナリDjiの前記最近傍xj'のランクの索引が判別され、
CP5)符号化/復号化の実効値は、ステップCP4)において判別された前記索引、ステップCP2)において判別された前記置換、およびステップCP1)において判別された前記符号ベクトルに依存している入力ベクトルに適用される請求項25から27のいずれか一項に記載の使用。
【請求項２９】
少なくとも前記対応テーブルは符号化/復号化装置のメモリに格納される請求項25から28のいずれか一項に記載の使用。
【請求項３０】
処理装置、特にコンピュータまたは携帯端末のメモリ、あるいは取り外し可能な記憶媒体上に格納されることを意図され、かつ処理装置の読取機構と連携することを意図され、請求項4から24のいずれか一項に記載の方法の実装のための命令を備えることを特徴とするコンピュータプログラム製品。
【請求項３１】
処理装置、特に符号化/復号化装置を組み入れたコンピュータまたは携帯端末のメモリ、あるいは取り外し可能な記憶媒体上に格納されることを意図され、かつ処理装置の読取機構と連携することを意図され、請求項25から29のいずれか一項に記載の圧縮符号化/復号化へのアプリケーションの実装のための命令を備えることを特徴とするコンピュータプログラム製品。
【請求項１】
可変次元のコードベクトルを備え、可変解像度を定義する可変レートにおけるベクトル量子化により、デジタル信号の圧縮符号化および/または復号化のための装置において使用することを意図されたディクショナリであって、
- 一方においては、所定の次元に対して、解像度増加の中間埋め込みディクショナリと、
- 一方においては、所定の次元に対して、
・あらかじめ決められた挿入規則の有限収集に従って、実数の有限集合から取り出された要素を、低次元のディクショナリのコードベクトルに挿入することによって構築されたコードベクトルから成る第1の集合と、
・挿入規則の前記収集に従って前記有限集合の要素の低次元のコードベクトルへの挿入によって取得できないコードベクトルから成る第2の集合との和集合を備えることを特徴とするディクショナリ。
【請求項２】
挿入規則の前記収集は、ベクトルの所定の位置において成分を装って実数の有限集合の単一要素を挿入することを備える基本規則に基づいて定式化されることを特徴とする請求項1に記載のディクショナリ。
【請求項３】
各基本規則は、
- 前記有限集合の要素の位と、
- 挿入の位置とを表す2つの正整数の組によって定義されることを特徴とする請求項2に記載のディクショナリ。
【請求項４】
前記ディクショナリは、可変次元のコードベクトルを備え、可変解像度を定義する可変レートにおけるベクトル量子化により、デジタル信号の圧縮符号化および/または復号化のために装置において使用することを意図され、
所定の次元に対して、
a)第1の集合は、あらかじめ決められた挿入/削除規則の有限収集に従って、実数の有限集合から取り出された低/高次元要素のディクショナリのコードベクトルに/から挿入/削除することによって形成されたコードベクトルから成り、
b)第1の中間のディクショナリは、前記所定の次元に対して、少なくとも前記第1の集合が構築されることを備え、
c)前記ディクショナリを少なくとも1つの所定の解像度で使用するように適合するため、第2の最終的なディクショナリが、中間ディクショナリに基づいて、増加/減少解像度のディクショナリの埋め込み/簡略化により構築され、増加解像度のディクショナリは最小解像度のディクショナリから最大解像度のディクショナリまで中間埋め込みされる、請求項1から3のいずれか一項に記載のディクショナリを形成する方法。
【請求項５】
所定の次元Nに対して、
aO)前記所定の次元Nよりも低い初期次元nの初期ディクショナリが取得され、
a1)あらかじめ決められた挿入規則の有限収集に従って、実数の有限集合から取り出された要素を初期ディクショナリのコードベクトルに挿入することによって形成された次元n+iのコードベクトルから成る第1の集合が構築され、
a2)挿入規則の前記収集による前記有限集合の要素の初期ディクショナリのコードベクトルへの挿入によって取得できない次元n+iのコードベクトルから成る第2の集合が提供され、
a3)前記第1の集合および前記第2の集合の和集合から成る次元n+iの中間ディクショナリが構築され、
ステップa1)からa3)は、前記中間ディクショナリが初期ディクショナリを装い、前記所定の次元Nまで、多くともN-n-1回繰り返される、請求項4に記載の方法。
【請求項６】
所定の次元Nに対して、
a'0)前記所定の次元Nよりも高い初期次元nの初期ディクショナリが取得され、
a'1)次元n-iの第1の集合は、あらかじめ決められた削除規則の有限収集に従って、次元nのディクショナリからの次元n-iの可能なコードベクトルの選択および抽出により構築され、
a'2)削除規則の前記収集による前記有限集合の要素の初期ディクショナリのコードベクトルからの削除によって取得できない次元n-iのコードベクトルから成る第2の集合が提供され、
a'3)前記第1の集合および前記第2の集合の和集合から成る次元n-iの中間ディクショナリが構築され、
ステップa'1)からa'3)は、前記中間ディクショナリが初期ディクショナリを装い、前記所定の次元Nまで、多くともn-N-1回繰り返される請求項4に記載の方法。
【請求項７】
それぞれ次元1からNまでのN個の連続するディクショナリは、次元nの初期ディクショナリに基づいて、次元n+1からNに対するステップa1)からa3)の繰り返しの実装を通じ、次元n-1から1に対するステップa'1)からa'3)の繰り返しの実装を通じて取得される請求項5および6に記載の方法。
【請求項８】
挿入/削除規則の前記収集は、ベクトルの所定の位置において成分を装って実数の有限集合の単一要素を挿入/削除することを備える基本規則に基づいて定式化される請求項4から7のいずれか一項に記載の方法。
【請求項９】
各基本規則は、
- 前記有限集合の要素の位と、
- 挿入/削除の位置とを表す2つの正整数の組によって定義される請求項8に記載の方法。
【請求項１０】
前記有限集合および挿入/削除規則の前記収集は、量子化される情報源の分析によりディクショナリを構築する前に、演繹的に定義される請求項4から9のいずれか一項に記載の方法。
【請求項１１】
前記情報源は好ましくは学習シーケンスによってモデル化され、前記有限集合および挿入/削除規則の前記収集の定義は前記情報源の統計的分析によって達成される請求項10に記載の方法。
【請求項１２】
前記有限集合は前記情報源の単一次元の確率密度の推定によって選択される請求項10および11のいずれか一項に記載の方法。
【請求項１３】
前記有限集合および挿入/削除規則の前記収集は、ディクショナリの構築後に、連続解像度のディクショナリの埋め込み/単純化により帰納的に定義され、後にはこのように構築されるこれらのディクショナリの統計的分析が続く請求項4から9のいずれか一項に記載の方法。
【請求項１４】
-挿入/削除規則の第1の集合および第1の収集は、1つまたは複数の中間ディクショナリを形成するように、学習シーケンスの分析により演繹的に選択され、
-前記第1の集合および/または挿入/削除規則の前記第1の収集の少なくとも一部は、前記1つまたは複数の中間ディクショナリの帰納的分析によって更新され、
-必要に応じて、前記1つまたは複数の中間ディクショナリを形成するコードベクトルの集合の少なくとも一部も更新される請求項10および13に記載の方法。
【請求項１５】
ステップc)は、
c0)前記所定の解像度rNよりも低い初期解像度rnの初期ディクショナリが取得される操作と、
c1)初期ディクショナリに基づいて、初期解像度rnよりも高い解像度rn+1の中間ディクショナリが構築される操作と、
c2)所定の解像度rNが達成されるまで、操作c1)が繰り返される操作とを備えている請求項4から14のいずれか一項に記載の方法。
【請求項１６】
操作c1)の繰り返しごとに、クラスおよびセントロイドの構造が提供され、そこで現行解像度riよりも高い解像度のディクショナリに少なくとも属しているセントロイドが再計算されて更新される請求項15に記載の方法。
【請求項１７】
現行解像度riよりも低い解像度のディクショナリに属しているセントロイドは、低い解像度のすべてのディクショナリの全歪みが1つの更新からその次の更新で減少する場合に限り更新される請求項16に記載の方法。
【請求項１８】
ステップc)は、
c'0)前記所定の解像度rNよりも高い初期解像度rnの初期ディクショナリが取得される操作と、
c'1)初期ディクショナリに基づき、初期ディクショナリをあらかじめ決められた基準に従って順序付けられた複数の部分集合に分割することによって、初期解像度rnよりも低い解像度rn-1の中間ディクショナリが構築される操作と、
c'2)所定の解像度rNが達成されるまで、操作c'1)が繰り返される操作とを備えている請求項4から14のいずれか一項に記載の方法。
【請求項１９】
前記あらかじめ決められた基準は、部分集合の基数、学習シーケンス内の部分集合の呼び出し、全歪みまたは好ましくはその歪みの減少に対する部分集合の寄与の中から選択される請求項18に記載の方法。
【請求項２０】
前記区分化では前記挿入/削除規則の少なくとも一部を使用する請求項18および19のいずれか一項に記載の方法。
【請求項２１】
それぞれの解像度r1からrNのN個の連続ディクショナリは、中間解像度rnの初期ディクショナリに基づいて、解像度増加rn+1からrNに対してステップc1)の繰り返し実装により、解像度減少rn-1からr1に対してステップc'1)の繰り返し実装を通じて取得される請求項15および18に記載の方法。
【請求項２２】
コードベクトルの所定の次元Nで使用するように前記ディクショナリを適合するため、一方でステップa)およびb)、一方でステップc)は、実質上逆転され、
- ステップc)において、依然として次元N'であるがより高い/低い解像度rNである第1の中間のディクショナリが、前記第1のディクショナリの解像度rNを実質的に獲得するように、増加/減少解像度のディクショナリの埋め込み/簡略化により、解像度rnおよび次元N'の初期ディクショナリに基づいて構築され、
- ステップa)において、所定の次元Nを獲得するため、あらかじめ決められた挿入/削除規則の有限収集に従って、実数の有限集合から取り出された前記所定の次元N要素よりも低い/高い次元N'の第1のディクショナリのコードベクトルに/から挿入/削除することによって形成されたコードベクトルから成る第1の集合が構築され、
- ステップb)において、解像度rNへの最終的な適合の可能なステップに続いて、少なくとも前記第1の集合からなる第2の最終のディクショナリが前記所定の次元Nに対して構築されるようになっている請求項4から21のいずれか一項に記載の方法。
【請求項２３】
各々索引(lr)によって識別された挿入/削除規則の前記収集は、これを最後にメモリ内に格納されており、所定の次元に対して、
- 前記第2の集合は、挿入/削除規則の前記収集に従って、所定の次元よりも低い/高い次元のコードベクトルへの挿入/削除の適用により取得することができないコードベクトルを備え、
- さらに、少なくとも1つの対応するテーブルは、挿入/削除規則の索引および前記第2の集合の要素を識別する索引を使用して、所定の次元のディクショナリの任意のコードベクトルを再構成できるようにし、
それにより、前記所定の次元のディクショナリの完全な格納は、前記第2の集合の要素およびリンクを、これらの要素および関連付けられている挿入/削除規則へのアクセスのために対応するテーブルに単に格納することによって回避できるようにする請求項4から22のいずれか一項に記載の方法。
【請求項２４】
対応テーブルは、以下のものを表す3つの整数スカラー値の集計を通じて、現行次元(j')の第2の集合内の現行索引(m')の要素に基づいて再構築することのできる所定の次元(j)のディクショナリ(DjNj)のコードベクトル(xj)の索引(mj)ごとに、前もって定式化され、
- 前記第2の集合の現行次元(j')
- 第2の集合の要素の現行索引(m')
- 挿入/削除規則の索引(lr)
この挿入/削除規則は少なくとも、前記現行索引(m')および前記現行次元(j')の要素に挿入/削除を適用することによって、所定の次元(j)のディクショナリ(DjNj)の前記コードベクトル(xj)を再構成することに寄与する請求項23に記載の方法。
【請求項２５】
可変解像度を定義する可変レートにおけるベクトル量子化により、デジタル信号の圧縮符号化/復号化において、所定の次元(j)のディクショナリ(Dij)内の入力ベクトルy=(y0,...,yk,...,yj-1)の最近傍であるコードベクトル(x')について検索が行われ、
CO1)検索される前記コードベクトル(xj)の現行索引(mj)に対し、前記ディクショナリを定式化できるようにする対応テーブルに表示される索引(j',m',lr)の事前読み取りを少なくとも通じて、前記現行索引(mj)に対応する索引(m')のコードベクトルの少なくとも部分的な再構築と、
CO2)少なくとも符号化において、入力ベクトルとステップC01)において再構成されたコードベクトルとの間の距離の計算と、
CO3)少なくとも符号化において、前記ディクショナリのすべての現行索引に対して、ステップC01)およびC02)の繰り返しと、
CO4)少なくとも符号化において、ステップC02)の繰り返しの1つの過程で計算された入力ベクトルとの距離(Dmin)が最も小さい、少なくとも部分的に再構成されたコードベクトルの索引(mmin)の識別と、
CO5)少なくとも復号化において、索引(mmin)がステップC04)において識別されたコードベクトル(xj)を装った入力ベクトル(y)の最近傍の決定のステップとを備える請求項23および24のいずれか一項に記載の方法の実装を通じて取得されるディクショナリの使用。
【請求項２６】
ステップCO1)は、少なくとも復号化において、
C011)対応テーブル内での、前記第2の集合および挿入/削除規則へのリンクを表す索引の読み取りであって、
- 前記第2の集合の部分集合の現行次元の索引と、
- 前記部分集合の要素の現行索引と、
- 前記要素に基づき、所定の次元のディクショナリのコードベクトルの構築のための適切な挿入/削除規則の索引とを含む索引の読み取りとを含む読み取りと、
CO12)現行次元によって識別される部分集合内での、その現行索引によって識別される前記要素の読み取りと、
CO13)ステップC012)において読み取られた前記要素に、ステップC011)において読み取られたその索引によって識別された適切な挿入/削除規則を適用することによる、前記所定の次元へのコードベクトルの完全な再構成とを備える請求項25に記載の使用。
【請求項２７】
符号化において、
* ステップC01)は、
CO11)対応テーブル内での、前記第2の集合および挿入/削除規則へのリンクを表す索引の読み取りであって、
- 前記第2の集合の部分集合の現行次元の索引と、
- 前記部分集合の要素の現行索引と、
- 所定の次元のディクショナリのコードベクトルの構築のための適切な挿入/削除規則の索引とを含む読み取りと、
C012)現行次元によって識別される部分集合内での、その現行索引によって識別される前記要素の読み取りとを備え、
* ステップC02)において、前記距離は、
- 挿入/削除規則の索引と、
- その現行索引によって識別される部分集合の要素の関数として推定された歪み基準の関数として計算され、
これにより、単に復号化のために完全な再構築を保持しておくことによって、ステップC01)の前記所定の次元を有するコードベクトルの部分的な再構築のみを可能にする請求項25に記載の使用。
【請求項２８】
置換コードの和集合に従って補足構造化特性がさらに提供され、置換コードの前記和集合の索引が使用され、
CP1)入力信号に基づき、絶対ベクトル|y|=(|y0|,...,|yk|,...,|yj-1|)および符号ベクトルε=(ε0,...,εk,...,εj-1)、εk=±1によって定義される入力ベクトルy=(y0,...,yk,...,yj-1)が形成され、
CP2)ベクトル|y|の成分は、リーダーベクトル
【数１】
を取得するため、置換によって、値を減少することによりランク付けされ、
CP3)次元jのディクショナリDjiのリーダーの中からリーダーベクトル
【数２】
の最近傍xj'が判別され、
CP4)ディクショナリDjiの前記最近傍xj'のランクの索引が判別され、
CP5)符号化/復号化の実効値は、ステップCP4)において判別された前記索引、ステップCP2)において判別された前記置換、およびステップCP1)において判別された前記符号ベクトルに依存している入力ベクトルに適用される請求項25から27のいずれか一項に記載の使用。
【請求項２９】
少なくとも前記対応テーブルは符号化/復号化装置のメモリに格納される請求項25から28のいずれか一項に記載の使用。
【請求項３０】
処理装置、特にコンピュータまたは携帯端末のメモリ、あるいは取り外し可能な記憶媒体上に格納されることを意図され、かつ処理装置の読取機構と連携することを意図され、請求項4から24のいずれか一項に記載の方法の実装のための命令を備えることを特徴とするコンピュータプログラム製品。
【請求項３１】
処理装置、特に符号化/復号化装置を組み入れたコンピュータまたは携帯端末のメモリ、あるいは取り外し可能な記憶媒体上に格納されることを意図され、かつ処理装置の読取機構と連携することを意図され、請求項25から29のいずれか一項に記載の圧縮符号化/復号化へのアプリケーションの実装のための命令を備えることを特徴とするコンピュータプログラム製品。
【図３】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図７ｃ】
【図７ｄ】
【図７ｅ】
【図７Ｆ】
【図７Ｇ】
【図８Ａ】
【図８ｂ】
【図４】
【図５】
【図６】
【図７Ａ】
【図７Ｂ】
【図７ｃ】
【図７ｄ】
【図７ｅ】
【図７Ｆ】
【図７Ｇ】
【図８Ａ】
【図８ｂ】
【公表番号】特表２００７−５２３５３０（Ｐ２００７−５２３５３０Ａ）
【公表日】平成１９年８月１６日（２００７．８．１６）
【国際特許分類】
【出願番号】特願２００６−５５０２１８（Ｐ２００６−５５０２１８）
【出願日】平成１６年１月３０日（２００４．１．３０）
【国際出願番号】ＰＣＴ／ＦＲ２００４／０００２１９
【国際公開番号】ＷＯ２００５／０８３８８９
【国際公開日】平成１７年９月９日（２００５．９．９）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
【公表日】平成１９年８月１６日（２００７．８．１６）
【国際特許分類】
【出願日】平成１６年１月３０日（２００４．１．３０）
【国際出願番号】ＰＣＴ／ＦＲ２００４／０００２１９
【国際公開番号】ＷＯ２００５／０８３８８９
【国際公開日】平成１７年９月９日（２００５．９．９）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
[ Back to top ]