(57)【要約】【課題】ゼロサーチ、ゼロメモリベクトル量子化を実施するための方法を開示すること。【解決手段】本発明は、如何なる明示的なコードブックおよびサーチも存在しない、すなわち、コードブックメモリおよび関連したサーチ計算が、削除される、ベクトル量子化に類似する不可逆的データ圧縮のための方法を有する。多少のメモリおよび計算は、なお要求されるが、これらは、この方法を活用しないシステムと比較して劇的に減少する。この理由から、この方法のメモリおよび計算の両方の要求は、同等の本発明を活用しない方法より、指数関数的に、より少ない。格納またはサーチされるべき明示的なコードブックが存在しないので、このようなコードブックは、生成される必要もない。このことは、この方法を、圧縮システムが、処理するのために存在するデータの統計に適応する適応コーディング方式によく適合させる：適応のために実行されるアルゴリズムの複雑性、および送信側と受信側を同期させるために伝送されるデータの量の両方は、同等の既存の方法より、指数関数的に、さらに少ない。【選択図】図２【特許請求の範囲】
【請求項１】
データ圧縮のための方法であって：
原点に関して対称的に配置される、ベクトルの暗示的に定義されたセット（以下、「コードポイント」と呼ぶ）を有する、暗示的コードブックを定めるステップであって、
当該コードポイントが、超立方体半径ベクトル
2007526669.tif 000172
により、暗示的に表され；当該コードポイントが、情報要素を表すために使用され、当該情報要素が、圧縮されるべきデータを構成し、および当該情報要素もまた、ベクトルである、ところのステップと；
当該情報要素が何れかのオーサントに位置するかを決定し、このことによって、当該情報要素を表すために前記暗示的コードブックの前記暗示的コードポイントを決定するために、当該情報要素の前記符号を検討することと；
当該情報要素に対してそのように選択された、前記関連した暗示的コードポイントのインデックスを決定することとにより、
当該情報要素に対して、圧縮関数を計算するステップと
を有する方法。
【請求項２】
デジタル化された人間の音声を圧縮するステップと；
当該圧縮された、デジタル化された人間の音声を、通信チャンネルを介して伝送するステップと；
当該圧縮された、デジタル化された人間の音声を、当該通信チャンネルを介して受信するステップと；
当該圧縮された、デジタル化された人間の音声を伸張するステップと；
当該デジタル化された人間の音声を自動音声認識システムで処理するステップと
をさらに有する請求項１に記載の方法。
【請求項３】
可逆関数を圧縮されるべき情報要素に適用するステップをさらに有し、当該関数が、圧縮されるべき典型的なデータの集合体が原点に中心があるＤ−次元の球の範囲内の一様な分布に近づくであろうように決定される請求項１に記載の方法。
【請求項４】
対称化変換を見つけるステップをさらに有する請求項３に記載の方法。
【請求項５】
最適なＤ−超立方体コードブックを見つけるステップをさらに有する請求項１に記載の方法。
【請求項６】
典型的な変換されたデータに関して、最適なＤ−超立方体コードブックを見つけるステップをさらに有する請求項３に記載の方法。
【請求項７】
当該対称化変換が、白色化変換をさらに有する請求項６に記載の方法。
【請求項８】
全てのデータをＤ−１−次元の空間に投影するステップと；
結果として生じるデータのセットを処理するステップとをさらに有し；
Ｄ−１ビットのみが、処理される各ベクトルに対して伝送される請求項７に記載の方法。
【請求項９】
前記白色化変換を、当該行列がそのＤ個の非ゼロ要素のみにより表される対角行列および直交行列の積として、メモリの効率的な方法で表すステップをさらに有し；それ故に、この変換の逆が、前記オリジナルのＤ個の非ゼロ要素のＤの逆数の対角行列および前記オリジナルの直交行列の前記転置行列の、逆の順序での、前記積として得られる、請求項７に記載の方法。
【請求項１０】
最適な超立方体半径ベクトル
2007526669.tif 000173
を決定するステップをさらに有し、このベクトルが、圧縮されるべき典型的なデータに対して、全てのＤ−超立方体コードブックの中で最小の平均二乗コーディング歪みをもたらす当該超立方体コードブックを定義する、請求項６に記載の方法。
【請求項１１】
2007526669.tif 000174
ら、各次元ｉ＝ｌ，…，Ｄに対して，前記和がＥにおける全てのベクトルｖの範囲で実行するように取られる、前記量
2007526669.tif 000175
を計算することにより、最適な超立方体半径ベクトル
2007526669.tif 000176
を計算するステップを、さらに有する請求項１０に記載の方法。
【請求項１２】
最適超立方体半径ベクトル
2007526669.tif 000177
を決定するステップをさらに有し、このベクトルが、典型的な変換されたデータに関して、全てのＤ−超立方体コードブックの中で、最小の平均二乗コーディング歪みをもたらす当該超立方体コードブックを定義する、請求項６に記載の方法。
【請求項１３】
2007526669.tif 000178
ベクトルｖから成る、代表例データ集合εから、
2007526669.tif 000179
を計算することにより、最適な超立方体半径ベクトル
2007526669.tif 000180
を、計算するステップをさらに有する請求項１２に記載の方法。
【請求項１４】
圧縮用のベクトル
2007526669.tif 000181
を得るステップと；
Ｄ−ビットのバイナリ数ｉをビットごとの連結；ｉ＝ｍ（ｖＤ）ｍ（ｖＤ−１）…ｍ（ｖ２）ｍ（ｖ１）（ここで、ｉのｊ番目のビットは、ｖｊがゼロまたは正の場合、０であり、それが負の場合、１である）として形成するステップと、
ｉを伝送するステップとをさらに有するベクトル
2007526669.tif 000182
を圧縮するための請求項１に記載の方法。
【請求項１５】
圧縮用のベクトルｖを得るためのステップと；
ｕ＝Ｔｖ（ここで、ｕは、
2007526669.tif 000183
を示し；Ｔは、前記対称化変換である）を計算するためのステップと；
Ｄ−ビットのバイナリ数ｉをビットごとの連結
ｉ＝ｍ（ｕＤ）ｍ（ｕＤ−１）…ｍ（ｕ２）ｍ（ｕ１）（ここで、ｉのｊ番目のビットは、ｕｊがゼロまたは正の場合、０であり、それが負の場合、１である）として形成するステップと、
ｉを伝送するステップとをさらに有するベクトルｖを圧縮するための請求項４に記載の方法。
【請求項１６】
伸張用のインデックスｉを得るためのステップと；
2007526669.tif 000184
から成る前記ベクトルを戻すステップとをさらに有する前記超立方体半径ベクトル
2007526669.tif 000185
に関して、圧縮により得られた、インデックスｉを伸張するための請求項１に記載の方法。
【請求項１７】
伸張用のインデックスｉを得るためのステップと；
2007526669.tif 000186
るかに依存する）をセットするステップと；
2007526669.tif 000187
に関して、圧縮により得られたインデックスｉを伸張するための請求項４に記載の方法。
【請求項１８】
歪みを小さくするために、回転を前記対称化変換に組み込むステップ、または前記超立方体コードブックを等価に回転するステップをさらに有する請求項３に記載の圧縮方法。
【請求項１９】
前記回転された超立方体コードブックに対して、最適な超立方体半径ベクトルを見つけるステップをさらに有する請求項１８に記載の方法。
【請求項２０】
超立方体の数を増加させることにより、多くの暗示的コードポイントを増加させるステップをさらに有し、圧縮が一群の超立方体コードブックに関して行われる請求項１に記載の圧縮方法。
【請求項２１】
各超立方体がその関連した超立方体半径ベクトル
2007526669.tif 000188
により決定される、一群の超立方体Ａを使用し、
対称化変換Ｔを適用して、ｕ＝Ｔｖを得るステップをさらに有し、当該対称化変換が、
圧縮すべきベクトルｖが与えられた場合、ｕ＝Ｔｖを見つけるステップと；
ｉ＝ｍ（ｕＤ）ｍ（ｕＤ−１）…ｍ（ｕ１）としてエンコードされたｕの前記オーサントを見つけるステップと；
2007526669.tif 000189
立方体インデックスｋを見つけるステップと；
当該サーチの結果を、そのように決定された前記当該超立方体インデックスｋの前記形で、前記オーサントの前記識別ｉと一緒に、受信側へ伝送するステップとを有する請求項２０に記載の圧縮方法。
【請求項２２】
多数の超立方体Ａを使用し、超立方体半径ベクトルにおいて、オリエンテーションにおいて、または両方において、お互いに関して変化し；当該オリエンテーションが、各超立方
2007526669.tif 000190
あり；および
圧縮するべきベクトルｖが与えられた場合、
各ｕｋ＝ＲｋＴｖ，を見つけるステップと、
ｕｋの前記オーサントインデックスｉを見つけるステップと、
明示的サーチにより前記関連したオーサントの範囲内で、前記最も近い回転された超立方体の超立方体インデックスｋを見つけるステップと、
当該サーチの結果を、そのように決定された前記当該超立方体インデックスｋの前記形で、前記オーサントの前記識別ｉと一緒に、受信側へ伝送するステップとをさらに有する請求項２１に記載の方法。
【請求項２３】
2007526669.tif 000191
ことにより、超立方体インデックスｋおよびオーサントインデックスｉから成る前記対を伸張するステップと；
2007526669.tif 000192
討するステップとをさらに有し、
当該頂点が、それから
2007526669.tif 000193
記載の方法。
【請求項２４】
2007526669.tif 000194
ことにより、超立方体インデックスｋおよびオーサントインデックスｉから成る前記対を伸張するステップと；
2007526669.tif 000195
討するステップとをさらに有し、
当該頂点が、それから
2007526669.tif 000196
記載の方法。
【請求項２５】
完全な超立方体コードブックの集合Ａを見つけるための方法であって：変換された代表例データに対して小さい平均コーディング歪みをもたらす完全な超立方体コードブックの集合Ｋ  を見つけるために、オーサントＫ−ｍｅａｎｓアルゴリズムを適用するステップをさらに有する方法。
【請求項２６】
圧縮方法であって、
圧縮用のベクトルｖを得るステップと；
ｕ＝Ｔｖ（ここで、ｕは、
2007526669.tif 000197
により示される）を計算するステップと；
2007526669.tif 000198
を形成するステップと；
2007526669.tif 000199
のセットから引き出され、
2007526669.tif 000200
い頂点を有する超立方体コードブックの前記インデックスであるステップと；
前記Ｄ−ビットのバイナリ数ｉを前記ビットごとの連結
2007526669.tif 000201
（ここで、ｉの前記ｊ番目のビットは、ｕｊがゼロまたは正の場合、０であり、それが負の場合、１である）として形成するステップと；
2007526669.tif 000202
【請求項２７】
伸張方法であって、
2007526669.tif 000203
超立方体半径ベクトル
2007526669.tif 000204
の前記セットから
2007526669.tif 000205
を選択するステップと；
2007526669.tif 000206
は１であるかに依存する）をセットするステップと；
2007526669.tif 000207
【請求項２８】
Ｋの超立方体コードブックの一群Ａを見つけるための方法であって：
2007526669.tif 000208
前記セット
2007526669.tif 000209
をもたらす、前記マップ
2007526669.tif 000210
により、マッピングするステップと；
Ｋ個の半径ベクトルの初期のセット
2007526669.tif 000211
を選択するステップと；
反復カウントｉを０にセットするステップと；
実行された反復の前記数；
2007526669.tif 000212
当該依存が、
2007526669.tif 000213
として表現される、前の反復に関する統計の前記改善の１つ以上に依存する、終了条件τ、を定めるステップと：
2007526669.tif 000214
をテストするステップであって；
2007526669.tif 000215
つ停止する；
2007526669.tif 000216
を、記号で、
2007526669.tif 000217
をセットする；ように計算する、
2007526669.tif 000218
をテストするステップと、
前記反復カウントｉをインクリメントし；かつ当該テストするステップに戻すステップとを有する方法。
【請求項２９】
データ圧縮用の方法であって、
情報要素に対して圧縮関数を計算するステップと：
暗示的コードブックのどの象限において、対応する暗示的コードポイントが、位置するかを決定するために、当該情報要素の前記符号を検討するステップと；
該情報要素に対して、関連した暗示的コードポイントのインデックスを決定するステップとを有する方法。
【請求項３０】
対称化変換を最初に適用し、次に、前記変換されたベクトルを圧縮することにより、データソースから発生するベクトルを圧縮するステップをさらに有する請求項２９に記載の方法。
【請求項３１】
歪みを小さくするために、当該超立方体コードブックを回転する、または、圧縮されるべき前記データを等価に回転し、および次に、請求項２４に記載の前記方法により前記変換されたベクトルを圧縮するステップをさらに有する請求項２９に記載の方法。
【請求項３２】
歪みを小さくするために、回転を前記対称化変換に組み込むステップ、または前記超立方体コードブックを等価に回転するステップをさらに有する請求項３０に記載の方法。
【請求項３３】
前記原点に関して対称的に配置される、この後コードポイントと呼ばれる、ベクトルの暗示的に定義されたセットを有する、暗示的コードブックを定めるステップをさらに有し；当該コードポイントが、当該コードポイントが、情報要素を表すために使用される請求項２９に記載の方法。
【請求項３４】
超立方体の数を増加させることにより、多くのコードポイントを増加させるステップをさらに有し、圧縮が一群の超立方体コードブックに関して行われ、および一旦、圧縮されるべき前記ベクトルの前記オーサントが決定されると、前記好適な超立方体が、明示的サーチにより見つけられる請求項２９に記載の方法。
【請求項３５】
超立方体の数を増加させることにより、多くのコードポイントを増加させるステップをさらに有し、圧縮が一群の超立方体コードブックに関して行われ、および一旦、圧縮されるべき前記ベクトルの前記オーサントが決定されると、前記好適な超立方体が、明示的サーチにより見つけられる請求項３０に記載の方法。
【請求項３６】
超立方体の数を増加させることにより、多くのコードポイントを増加させるステップをさらに有し、
圧縮が、超立方体コードブックの一群Ａに関して行われ、前記超立方体が、超立方体半径ベクトルにおいて、オリエンテーションにおいて、または両方において、お互いに関して変化し；
各超立方体に対して、前記選択された超立方体およびオーサントインデックスが、明示的サーチにより、各超立方体の前記好適な頂点から成るセット中で見つけられ、各超立方体の前記好適な頂点が、圧縮されるべき前記ベクトルと前記同じオーサント内に位置する前記１つである、請求項２９に記載の方法。
【請求項３７】
超立方体の前記数を増加させることにより多くのコードポイントを増加させるステップをさらに有し、圧縮が、超立方体コードブックの一群Ａに関して行われ、各超立方体に対して、前記選択された超立方体およびオーサントインデックスが、明示的サーチにより、各超立方体の前記好適な頂点から成るセット中で見つけられ、各超立方体の前記好適な頂点が、圧縮されるべき前記ベクトルと前記同じオーサント内に位置する前記１つである、請求項３０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、データ圧縮に関する。さらに詳細には、本発明は、ゼロサーチ、ゼロメモリベクトル量子化と称される新規なデータ圧縮技術に関する。
【背景技術】
【０００２】  本発明の課題は、本明細書内で、ゼロサーチ、ゼロメモリベクトル量子化と称される、データ圧縮のための新しい技術である。ベクトル量子化は、周知でかつ広く実践されている不可逆的データ圧縮の方法である。「データ圧縮」は、（記憶用の）或るメモリ容量または（伝送用の）通信帯域幅を要求する、或るデータ本体、典型的には或る固定された次元のベクトルのシーケンスが、より少ない量のデータに変換されることを意味する。データの圧縮形と通常称される、この変換された表現から、オリジナルのデータ本体の合理的な複製は、適切な伸張アルゴリズムにより、再構成可能である。この方法により再構成されるデータが、そのオリジナルに正確に一致することができないので、この方式は、不可逆的であると言われる。それに反して、オリジナルデータが常にその圧縮された表現から正確に再構成可能である特性を有する圧縮方式は、可逆的あると言われる。【０００３】  ベクトル量子化は、導入されたシステムにより処理されるであろうそれらを代表する、コードブックと呼ばれるベクトルの小さいセットを定めることにより、演算する。圧縮用のベクトルが、存在する時、計算は、それに最も近いコードブックエントリを決定し、およびベクトル自体ではなく、コードブック内のこのエントリのインデックスが、入力のプロキシとして伝送される（または、格納される）。インデックスｉを受取り（またはリードバック）次第、入力データは、ｉ番目のエントリをコードブックから抽出し、かつこのベクトルをオリジナルの複製として示すことにより、再構成される。それは、極めて高い圧縮率を実現することができるが、この方法の２つの重大な欠点は、以下の通りである：
（１）コードブックを格納する必要（システムが、データ伝送のために使用される場合、このことは、送信側と受信側の両方で行われなければならない）、および
（２）入力ベクトルに対する最も近い一致を見つけるために、送信側がコードブックをサーチする必要。【０００４】
【非特許文献１】Ａｌｌｅｎ  Ｇｅｒｓｈｏ  ａｎｄ  Ｒｏｂｅｒｔ  Ｍ．Ｇｒａｙ．Ｖｅｃｔｏｒ  Ｑｕａｎｔｉｚａｔｉｏｎ  ａｎｄ  Ｓｉｇｎａｌ  Ｃｏｍｐｒｅｓｓｉｏｎ，Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｓ，１９９２
【非特許文献２】Ｈｏｗａｒｄ  Ａｎｔｏｎ，Ｅｌｅｍｅｎｔａｒｙ  Ｌｉｎｅａｒ  Ａｌｇｅｂｒａ，Ｊｏｈｎ  Ｗｉｌｅｙ  ａｎｄ  Ｓｏｎｓ，１９７３
【非特許文献３】Ｐａｕｌ  Ｇ．Ｈｏｅｌ，Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｍａｔｈｅｍａｔｉｃａｌ  Ｓｔａｔｉｓｔｉｃｓ，Ｊｏｈｎ  Ｗｉｌｅｙ  ａｎｄ  Ｓｏｎｓ，Ｎｅｗ  Ｙｏｒｋ，ＮＹ，５ｔｈ  ｅｄｉｔｉｏｎ，１９８４
【非特許文献４】Ｍｏｒｔｏｎ  Ｌ．Ｃｕｒｔｉｓ，Ｍａｔｒｉｘ  Ｇｒｏｕｐｓ．Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，Ｎｅｗ  Ｙｏｒｋ，ＮＹ，ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ，１９８４
【非特許文献５】Ｈｏｗａｒｄ  Ａｎｔｏｎ，Ｅｌｅｍｅｎｔａｒｙ  Ｌｉｎｅａｒ  Ａｌｇｅｂｒａ，Ｊｏｈｎ  Ｗｉｌｅｙ  ａｎｄ  Ｓｏｎｓ，１９７３；Ｔｈｅｏｒｅｍｓ  ６．７  ａｎｄ  ６．８
【非特許文献６】Ｗｉｌｌｉａｍ  Ｈ．Ｐｅｓｓ，Ｓａｕｌ  Ａ．Ｔｅｕｋｏｌｓｋｙ，Ｗｉｌｌｉａｍ  Ｔ．Ｖｅｔｔｅｒｌｉｎｇ，ａｎｄ  Ｂｒｉａｎ  Ｐ．Ｆｌａｎｎｅｒｙ，Ｎｕｍｅｒｉｃａｌ  Ｒｅｃｉｐｅｓ  ｉｎ  Ｃ＋＋：Ｔｈｅ  Ａｒｔ  ｏｆ  Ｓｃｉｅｎｔｉｆｉｃ  Ｃｏｍｐｕｔｉｎｇ，Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ，２００２
【非特許文献７】Ｈｏｗａｒｄ  Ａｎｔｏｎ，Ｅｌｅｍｅｎｔａｒｙ  Ｌｉｎｅａｒ  Ａｌｇｅｂｒａ，Ｊｏｈｎ  Ｗｉｌｅｙ  ａｎｄ  Ｓｏｎｓ，１９７３；ｐａｇｅ  ６８  ｐｒｏｐｅｒｔｙ  ｉｖ
【非特許文献８】Ｈｏｗａｒｄ  Ａｎｔｏｎ，Ｅｌｅｍｅｎｔａｒｙ  Ｌｉｎｅａｒ  Ａｌｇｅｂｒａ，Ｊｏｈｎ  Ｗｉｌｅｙ  ａｎｄ  Ｓｏｎｓ，１９７３；Ｔｈｅｏｒｅｍ  １．６
【非特許文献９】Ｗｉｌｌｉａｍ  Ｈ．Ｐｒｅｓｓ，Ｓａｕｌ  Ａ．Ｔｅｕｋｏｌｓｋｙ，Ｗｉｌｌｉａｍ  Ｔ．Ｖｅｔｔｅｒｌｉｎｇ，ａｎｄ  Ｂｒｉａｎ  Ｐ．Ｆｌａｎｎｅｒｙ，Ｎｕｍｅｒｉｃａｌ  Ｒｅｃｉｐｅｓ  ｉｎ  Ｃ＋＋：Ｔｈｅ  Ａｒｔ  ｏｆ  Ｓｃｉｅｎｔｉｆｉｃ  Ｃｏｍｐｕｔｉｎｇ，Ｃａｍｂｒｉｄｇｅ  Ｕｎｉｖｅｒｓｉｔｙ  Ｐｒｅｓｓ，ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ，２００２，Ｓｅｃｔｉｏｎ  １１．１
【非特許文献１０】Ｒｉｃｈａｒｄ  Ｏ．Ｄｕｄａ，Ｐｅｔｅｒ  Ｅ．Ｈａｒｔ，ａｎｄ  Ｄａｖｉｄ  Ｇ．Ｓｔｏｒｋ，Ｐａｔｔｅｒｎ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ，Ｊｏｈｎ  Ｗｉｌｅｙ  ａｎｄ  Ｓｏｎｓ，  Ｎｅｗ  Ｙｏｒｋ，  ＮＹ，  ｓｅｃｏｎｄ  ｅｄｉｔｉｏｎ
【発明の開示】
【課題を解決するための手段】
【０００５】  本明細書において、これらの欠点を取り除く、既存のベクトル量子化技術に類似するがそれとは異なる、データ圧縮のための方法が、開示される。如何なる明示的なコードブックおよびサーチも存在しない；コードブックメモリおよび関連したサーチ計算は、削除される。多少のメモリおよび計算は、なお要求されるが、これらは、この方法を活用しないシステムと比較して劇的に減少する。この方法は、要求の厳しい、実際のデータ圧縮のタスクにおいて、妥当性が確認され、および再構成の優れた忠実度を維持しながら、（本発明を活用しないシステムと比較して）、計算において３０分の１を超える低減、およびメモリにおいて３００分の１を超える低減をもたらすことが分かった。本発明は、圧縮のための様々なアルゴリズムを教示する；これらは、全て、計算時間およびメモリの使用の両方において、本発明を活用しない方法より、指数関数的に、さらに効率的である。【０００６】  格納またはサーチされるべき明示的なコードブックが存在しないので、このようなコードブックは、生成される必要もない。このことは、圧縮システムが、処理のために存在するデータの統計に適応する適応コーディング方式に、この方法をよく適合させる。適応のために実行されるアルゴリズムの複雑性、および送信側と受信側を同期させるために伝送されるデータの量の両方は、既存の方法より、指数関数的に、さらに効率的である。
【発明を実施するための最良の形態】
【０００７】  本明細書において、ゼロサーチ、ゼロメモリベクトル量子化を実施するための方法が、開示される。如何なる明示的なコードブックおよびサーチも存在しない；コードブックメモリおよび関連したサーチ計算は、削除される。多少のメモリおよび計算は、なお要求されるが、これらは、この方法を活用しないシステムと比較して劇的に減少する。この方法は、要求の厳しい、実際のデータ圧縮のタスクにおいて、妥当性を確認され、および再構成の優れた忠実度を維持しながら、（本発明を活用しないシステムと比較して）、計算において３０分の１を超える低減、およびメモリにおいて３００分の１を超える低減をもたらすことが分かった。【０００８】  格納またはサーチされるべき明示的なコードブックが存在しないので、このようなコードブックは、生成される必要もない。このことにより、この方法は、圧縮システムが、処理のために存在するデータの統計に適応する適応コーディング方式によく適合する。適応のために実行されるアルゴリズムの複雑性、および送信側と受信側を同期させるために伝送されるデータの量の両方は、既存の方法より、指数関数的に、さらに効率的である。【０００９】  ベクトル量子化は、非特許文献１に、詳細に記載され、および読者は、課題の完全な取り扱いのためにこの本を参照することが勧められる。それにもかかわらず、完全のために、本明細書は、読者が、我々の発明の演算、その利点、およびそれが現行の方法とどのように異なるかを理解するために十分な背景を提供する。読者は、線形代数および多変量統計、特に、固有ベクトルおよび共分散の概念の基礎知識を、非特許文献２および非特許文献３の参照のそれぞれのレベルで有すると仮定される。基本的な方法への拡張を確実に理解することは、非特許文献４のレベルで、連続群のリー理論のかなりの熟知を要求する。【００１０】  本明細書で示される素材は、通信チャンネルを通して伝送され、次に、自動音声認識（ＡＳＲ）システムにより処理され、デジタル化された人間の音声の圧縮に関して構成される。これは、本発明が開発された、かつそれが現在適用されている状況である。しかしながら、本発明において、そのアプリケーションを、音声に限って、またはデータ伝送に限って制限するものはない。例えば、本発明は、映像、または任意の他のデジタル化された信号の伝送および記憶に適用可能である。【００１１】ベクトル量子化の概観
我々は、各ベクトルが、Ｄ個の要素からなり、かつ各要素は、ｂビットを有する、一連のＮ個のベクトルｖ０…ｖＮ−１として示される、圧縮されるべきデータＶの本体を有すると仮定しよう。Ｖを送信側から受信側へ伝送するために、任意のデータ圧縮方法を適用しないことは、我々に或るＮｘ  Ｄｘ  ｂビットのデータを通信チャンネルを通して伝播することを要求する。通信にはエラーがないと仮定すると、このことは、無損失伝送である：受信側は、Ｖの正確なコピーを得る。【００１２】  実際、通信している当事者は、伸張されたデータがオリジナルの正確なコピーであることを要求しないことがよくある。合理的な複製は、それが、適切に低価格および／または高速で得ることが可能であり、および受信されたコピーが、本物に十分に近いならば、十分である場合がある。それを別の方法に置き換えるために、送信側および受信側は、より安い電話料金および／または、より少ない伝送時間のために、或る程度の忠実度を犠牲にすることをいとわない場合がある。【００１３】  そう仮定し、さらに、Ｖのベクトルｖ０…ｖＮ−１は、それらが、相対的に小さい数のクラスタに自然に分かれるように、分布されると仮定されたい。図１は、或る２００個の２次元ベクトルが、８つのクラスタに分かれるように見える、このような分布を表す。【００１４】  今、必ずしもクラスタに属するポイントからから引き出されるわけではない、各クラスタの名目中心ポイントを選ぶ。これらのポイントを、ｃ０〜ｃ７と呼ぶ。その中心ポイントのまわりの各クラスタの散布度が、あまり大きくない場合、我々は、データを以下のように圧縮することができる：
我々が伝送したい各ベクトルｖに対して、我々は、ｖに最も近い、クラスタ中心ｃｉのインデックスｉを送る。【００１５】  一般に、この方式が、合計Ｋ個のクラスタ、従ってＫ個の関連したクラスタ中心と共に、適用される場合、このことは、送られる各ベクトルに対してわずか
2007526669.tif 000002
ビットの伝送を必要とする。インデックスの伝送は、それ自体、エントロピーの圧縮方式に対する課題となる場合がある；以下を参照されたい。【００１６】  ｌｏｇ２Ｋが、１つの圧縮されていないベクトルのビットのサイズであるＤｘ  ｂと比較して小さい場合、このことは、伝送されるデータ量の相当な低減を伴なう。例えば、Ｄ＝２である、図１の場合、各ベクトル要素は、３２−ビットの浮動小数点数であると仮定されたい。次に、ベクトル当りＤｘ  ３２＝６４ビットを伝送する代わりに、我々は、ベクトル当りｌｏｇ２Ｋ＝ｌｏｇ２８＝３ビットのみ送って、要求された帯域幅において２０分の１より大きい低減；をやり遂げることができる。受信端で、インデックスｉが到着する時、受信側は、エントリｃｉをコード
2007526669.tif 000003
【００１７】  この方式は、ベクトル量子化として公知である。Ｋ個のクラスタ中心のセット
2007526669.tif 000004
は、コードブックとして公知である；このクラスタ中心は、それら自体、コードワードまたはコードポイントとも称される。ベクトル量子化が、高率の圧縮をもたらすことができる一方、このことは、比較的高価となるであろう。【００１８】  第一に、送信側は、メモリを、コードブックを格納することに充てなければならない；我々は、このことを送信側のコードブックコストと呼ぶであろう。【００１９】  第二に、伝送されるべき各ベクトルｖｌに対して、送信側は、計算により、ｖｌに最も近いクラスタ中心ｃｉのインデックスｉを決定しなければならない；我々は、このことを送信側のサーチコストと呼ぶであろう。【００２０】  第三に、受信側は、同様に、インデックスｉを受取り次第、クラスタ中心ｃｉが、コードブ
2007526669.tif 000005
ように、コードブックを格納しなければならない；我々は、このことを受信側のコードブックコストと呼ぶであろう。【００２１】  第四に、通信している当事者は、或る程度の忠実度を断念した。受信側は、
2007526669.tif 000006
ではなく
2007526669.tif 000007
を獲得する。その中心のまわりの各クラスタの微細な構造は、消去された。我々は、このことをコーディング歪みと呼ぶであろう。【００２２】  ベクトル量子化は、簡潔に、圧縮用および伸張用の２つの関数に関して、表現可能である。
2007526669.tif 000008
をＫ個のコードポイントのセットとし、
2007526669.tif 000009
出されると仮定されたい。次に、圧縮アルゴリズムは、以下に定義される、関数
2007526669.tif 000010
により表現される。
2007526669.tif 000011
【００２３】
2007526669.tif 000012
る。（正確ではない）逆の伸張アルゴリズムは、同様に、以下に定義される、関数
2007526669.tif 000013
により表現される。
2007526669.tif 000014
【００２４】  我々は、上記（１）および（２）を圧縮および伸長の式とそれぞれ呼ぶ。ベクトルｖからその再
2007526669.tif 000015
あろう。このことが、
2007526669.tif 000016
であるので、ｇＫとｈＫを用いた合成によりきちんと提供されることに留意されたい。我々は、
2007526669.tif 000017
を示すであろう；すなわち、
2007526669.tif 000018
である。【００２５】
2007526669.tif 000019
【００２６】本発明により解決された問題
上記我々の教育的な具体例は、合計８個の中心ｘ２個の要素／中心ｘ３２ビット／要素＝５１２ビットとなる、小さなコードブックを有する。少ない数のエントリ、および短いベクトル長さに起因して、最も近いコードワードに対して、このコードブックをサーチすることは、容易である。【００２７】  しかしながら、これは、典型的ではない。実際のデータ圧縮タスクの特徴に対する或る程度感じを与えるために、我々は、本発明に動機を与えたアプリケーション：１２−次元のメル周波数ケプストラム係数（ＭＦＣＣ）ベクトルのシーケンスとして表された、人間の音声の圧縮を考慮する。本発明を導入する前に、このアプリケーションは、送信側および受信側の両方で、各々が４０９６コードワードを含み、各ベクトル要素が、４−バイトの浮動小数点数である、２つの別個のコードブックを含んだベクトル量子化方式を使用した。各対のコードブックに対するメモリは、それゆえ、２個のコードブックｘ４０９６個のベクトル／コードブックｘ１２個の要素／ベクトルｘ３２ビット／要素＝３，１４５，７２８ビットである。さらに、送信側のサーチコストは、圧縮されるべきデータを生成していたＭＦＣＣ計算のコストより、３分の１ないし５分の１だけ、優位を占めた。このアプリケーションにおいて実現された圧縮は、３８４ビットのベクトルを２４ビットのデータに圧縮することである。【００２８】  これらのコストの削除は、本発明が解決する、中心的な問題である。本明細書において、我々は、送信側および受信側コードブックコストをゼロに、かつ送信側のサーチコストをゼロに減少させる、データ圧縮のための方法を開示する。圧縮のためにサーチされるべき如何なる明示的なコードブックも存在しないし、かつ如何なるものも、再構成のために使用されない、その結果、これらのコストの全ては、簡単に削除される。さらに、この方法は、それが適用可能な時、実現される圧縮の程度を著しくは減少させない、または、コーディング歪みを増加させない。すぐ前で議論された実際の具体例において、本発明は、適用される時、再び、３８４ビットのベクトルを２４ビットの圧縮されたデータに減少する、同一の圧縮をもたらした。さらに、再構成されたデータの忠実度は、自動音声認識システムにより、従来の、費用のかかる圧縮方式により実現される結果に一致する、ワード当りの認識精度を実現するために、十分良質であった。【００２９】  コードブックおよびサーチのコストの代わりに、我々の発明は、送信側および受信側の両方に、変換記憶および計算のコストを課す。これらのコストは、それらが、無視できると考えて良いほど、非常に低く−典型的なサーチおよびコードブックのコストの１０２分の１ないし１０３分の１程度である。【００３０】距離、コードブックおよびボロノイ図
続く議論において考慮するであろう、ベクトル量子化の幾つかの細かいポイントは、本明細書で留意されなければならない。【００３１】  第一に、我々は、これまでは、まさに何がデータポイントのクラスタを構成するのか、または、どのコードポインドが、所定のベクトルに最も近いかを決定するために、実際、どのような測定が使用されるべきかの問題を回避してきた。図１ａおよび１ｂは、圧縮用のデータを示す。ここで、図１ａは、各々がドットにより印を付けられ、かつ８つのクラスタに自然に分かれるように見える、２００個のプロットされた二次元ベクトルを示し、および図１ｂは、各々が星印により印を付けられる名目クラスタ中心と一緒に、プロットされた同じデータを示す。図１ａおよび１ｂを用いて概念を示すことにより、我々は、適切な距離として、ユークリッド・ノルムを暗示的に支持してきた。しかしながら、エンコードされたデータが、いくつかの実際の測地学的測定から発生しない限り−例えば、ドライビングコース上の集められていないゴルフボールの分布−この測定を使用する如何なる固有の理由も実際には存在しない。実際、ＭＦＣＣベクトルのコーディングのような、抽象的設定において、マハラノビス・ノルムをむしろ選ぶ相当な理由が存在する。我々は、この議題を以下でさらに議論する。今のところ、我々は、圧縮式（１）に現れる距離が、任意であると理解されることを留意する。【００３２】  第二に、我々は、コードブックに関する多数の実際の詳細、特に、どのように送信側および受信側が共通のコードブックを定めるか、どの程度近く、コードブックが、圧縮用に意図された特定のデータのセットに結び付けられるか、どのようにクラスタが見つけられるか、およびどのようにクラスタ中心ポイント（すなわち、コードワード）が、選ばれるか、に触れなかった。このことを具体的に説明するために、我々は、これらの議題に関して、或る単純化した仮定を行うであろう；我々は、基本的な考えを示した後、これらの仮定に関するバリエーションを調べるであろう。【００３３】  特に、我々は、システムの設計者が、システムを導入する時、固定されたコードブックを送信側および受信側へ提供すると仮定するであろう。このコードブックは、各々が、次元Ｄであり、作業中に一度だけ、導入されたシステムに示されるであろう種類の典型的なデ
2007526669.tif 000020
の検討により開発される。すなわち、導入されたシステムにより処理されたデータの特性は、少なくとも、ベクトル量子化に重要な特徴に関して、εのそれらと近接して一致すると仮定される。εは、非常に大きい；特に、Ｅ≫Ｄ（ベクトルの次元）と仮定される。我々は、εの要素を代表例ポイント（ｅｘａｍｐｌｅ  ｐｏｉｎｔｓ）またはトレーニングデータ（ｔｒａｉｎｉｎｇ  ｄａｔａ）とさまざまに呼ぶ。【００３４】  コードブックを作成するための方法に関して、我々は、今、簡単に、広く使用されている反復Ｋ−ｍｅａｎｓアルゴリズム記載するであろう。この方法は、それが、コードブックのシーケンスを、トレーニングデータをＫ個のクラスタの集合に繰り返して分割し、次に新しいコードブックのコードワードをクラスタ構成要素の算術平均として決定することにより、反復して定めるので、このように名付けられる。アルゴリズムの詳細は、図２に、見られる。【００３５】  以下の議論において、我々は、Ｋ−ｍｅａｎｓアルゴリズムの分割するステップに関係するの概念、ボロノイ図を利用するであろう。図２は、従来のＫ−ｍｅａｎｓアルゴリズムを示す。これは、ベクトル量子化コードブックを決定するために、広く使用されているアルゴリズムである。図２において議論されるように、各反復ステップ６ａで、Ｋ−ｍｅａｎｓアルゴリズムは、コードポイントのセットに関して、εの要素を分割し、このことによって、εを互いに素の部分集合の集合に分解する。全く同様に、εの要素が引き出される、全ての可能なデータベクトルの空間は、それ自体、所定のコードブックに関して、ボロノイセル（Ｖｏｒｏｎｏｉ  ｃｅｌｌｓ）と呼ばれる、オーバーラップしない領域に、分割可能であろう。コードポイント当り１つのセルが存在する；各セルは、空間内の、任意の他のものより所定のコードポイントにより近い、これらのポイントから構成される。この分割は、同様に、使用中の特定の距離に依存する；この議論において、我々は、ユークリッド距離を使用するであろう。これらのセル間の境界−この境界は、２つ以上のコードポイントから等距離のポイントにより構成される−を表す図はボロノイ図として公知である。【００３６】  図３ａは、ボロノイ図である。示されるコードポイントの集合は、暗示的に、平面を、コードポイント当り１つのオーバーラップしないセルに分ける。コードポイントｃｉに対するセ
2007526669.tif 000021
イントから構成される。このボロノイ図は、隣接するセルのコードポイントから等距離のその平面上のポイントである、セル境界を示す。図３ｂは、加えられたデータポイントを有するボロノイ図を示す。これは、このボロノイ図が、どのように圧縮関数を暗示的に表すかを示す。図３ａは、図１のコードポイントに対するボロノイ図である。対称性を考慮すると、任意の２つの隣接するセル間の境界が、常に、各セルと関連したコードポイントを結ぶ線分の垂直二等分線であることに留意されたい。【００３７】
2007526669.tif 000022
ノイ図の概念は、任意のノルム、有限次元のベクトル空間において、明確に定義されている。
2007526669.tif 000023
ある。さらに、我々は、前のパラグラフの最後で、この所見を一般化する：ユークリッド距離の場合、隣接するセル間の境界は、２つの関連したコードポイントを結ぶ線を二等分し、かつ直交する超平面（の部分）で構成される。【００３８】  ボロノイ図およびベクトル量子化は、以下のように、密接に関係する。所定のコードブ
2007526669.tif 000024
2007526669.tif 000025
クトルｖが特定のボロノイセルに位置することを知る場合、そのセルの関連したコードポイ
2007526669.tif 000026
である。この考えは、図３ｂにおいて、表わされる。【００３９】  図４ａおよび４ｂは、隣接したコードポイントの対称性および関連したセル境界を示す。これら２つの具体例が示すように、隣接したボロノイセル間の境界は、それぞれのセルのコードポイントを結ぶ線の垂直二等分線である。【００４０】基本的な考え
本発明の基本的な考えは、以下の所見である：平面内で、４つのコードポイントのセットが、原点に中心がある、辺が座標軸に直交する正方形の頂点に位置するように、選ばれる場合、以下の通りであり、
2007526669.tif 000027
この時、この関連したボロノイセルは、従来のデカルト座標システムの４つの象限（ｑｕａｄｒａｎｔ）であり、およびそのセル境界は、座標軸自体である。【００４１】  図５ａおよび５ｂは、完全なボロノイ図を示す。図５ａは、正方形およびそのボロノイ図を示す。図５ｂは、各々が（同じ）完全なボロノイ図を有する、様々な長方形を示す。図５ａは、
2007526669.tif 000028
す。図５ａは、このコードブックおよび我々が、完全なボロノイ図と称するであろう、その関連したボロノイ図を表す。我々は、そのセル境界がプロットの座標軸と正確に対応するので、そのボロノイ図が完全であると言う。【００４２】  専門用語をわずかな濫用するが、我々は、図５ａの正方形は、それが従来の意味で半径１を有する円を囲むので、半径１を有すると言うであろう。【００４３】  この主張の多少の一般化は、可能である。前のセクションにおいて議論された対称性考慮の結果として、同じ完全なボロノイ図は、正方形の次元に関係なく、得られる。実際、図は、正方形である必要さえない。その長方形が、原点に中心があり、かつその長方形のサイドが座標軸と直交すれば、それは、任意の辺の長さの長方形であることが可能である。関連したボロノイ図は、常に、完全であろう；このことは、図５、右パネルに、表わされる。【００４４】
2007526669.tif 000029
のが問題にならないことである。ｖの要素の符号のみを検討することにより、どの象限（ｑｕａｄｒａｎｔ）−従って、どのボロノイセル−内に、そのベクトルが、位置するかを決定すること、および、このことによって、関連したコードポイントのインデックスを決定することは、可能である。如何なるサーチそれ自体も、含まれず、および如何なるコードブックも決して参照されない。さらに、最も近いコードポイントは、正確に、知られている。【００４５】  全てのこれらの所見は、２次元からＤ次元へ、以下のような、一般化を有する。関連した図は、その頂点がコードブックを構成する、Ｄ−次元の超立方体、または略してＤ−超立方体である。原点に中心がある、座標軸と直交する面を有する、半径１のＤ−超立方体の頂点は、ｐ膚の直積として決定される。
2007526669.tif 000030
ここで、ダブルトン｛＋１，−１｝は、この積に、Ｄ回現れる。この図は、２Ｄ個のエントリを有するコードブック対応する、２Ｄ個の頂点を有する（表記２Ｄは、整数２のＤ乗を示し、指数関数的に、Ｄとともに増加する関数である）。この構成によりもたらされる利点が、Ｄが増加するに従って、ますます大きくなることに留意されたい。概念的なコードブックのサイズに関して、従って、関連したサーチの作業負荷は、両方とも、Ｄと共に、指数関数的に増加する。さらに、コードブックおよびサーチの両方を、無しで済ますことが可能である：所定のベクト
2007526669.tif 000031
置き換えられる。【００４６】  図６は、Ｄ＝３に対する、完全な超立方体コードブックを示す。このコードブックの半径ベクトルは、
2007526669.tif 000032
である。【００４７】
2007526669.tif 000033
の超立方体コードブックであると言うであろう。【００４８】  二次元の場合、正方形および長方形の両方が、完全なボロノイ図を有する。同様に、Ｄ次元に対する適切な一般化が存在する。Ｄ次元において、各セル境界が、Ｄ−１の座標軸のスパンである、Ｄ−１次元の超平面から構成される場合かつその場合に限って、ボロノイ図は、完全である。今、
2007526669.tif 000034
を厳密に正の要素を有するベクトルとする。次に、再び、対称性の考慮により、
2007526669.tif 000035
により定義されるコードブックも、また、完全なボロノイ図を有する。このことは、図５ａ
2007526669.tif 000036
ルと称するであろう。【００４９】
2007526669.tif 000037
性をもたらす。【００５０】
2007526669.tif 000038
する。この意味で、超立方体コードブックの暗示的な表現は、明示的なバージョンより、指数関数的に小さい。【００５１】  任意の超立方体コードブックが、所定の圧縮タスクに対して、適切に、小さい歪みを提供するであろうという保証は存在しない。驚くことに、適切な超立方体コードブックは、多くのデータ圧縮タスクに対して、本発明の第２の要素により、見つけられる。我々は、今、この第２の要素の背景にある考えを説明する。【００５２】  必要な直感を開発するために、我々は、我々の注意を、今、二次元の場合に集中し、および圧縮されるべきデータが、原点に中心があるディスク内に、一様に、分布させられると仮定する。半径２の円の範囲内の一様な分布からサンプリングされた１０００個のポイントがらなる、このようなデータのセットの具体例は、図７ａに表示され、サンプリングされた対称データを示す。ここで、１０００個のポイントが、半径２のディスク上の一様な分布からサンプリングされる。【００５３】  この特別な場合において、４つのコードポイントの最適な可能な配置は、コーディング歪みを最小にする観点から、それらが、正方形の頂点に位置し、さらに、原点に中心がある時に、得られることを示すことができる。実験的な検証は、図７ｂに提供され、４つの要素のコードブックを決定するために実行された、１００個のＫ−ｍｅａｎｓ反復の結果を示す。コードポイントの位置は、原点に中心がある正方形の頂点に近づく。実際、最適な可能なコードブックが、その図のその次元に近い、
2007526669.tif 000039
の辺長さを有する正方形であることを解析的に示すことは、可能である。【００５４】  今、鍵となる所見に近づく。我々は、コードブックが原点に中心がある正方形から形成される、データポイントの対称ディスクの仮定的な場合を考慮し続ける。このコードブックで得られる歪みは、正方形のオリエンテーションと無関係である。このことは、対称性の議論の結果として生じる：圧縮されるべきデータが、仮定により、ディスクの範囲内に一様に分布させられるので、コードブックを定義する正方形を向けるべき如何なる好適な方向も存在する可能性はない。この考えは、図８ａおよび８ｂに示される。【００５５】  これは、我々が、コーディング歪みにおいて、何らかの不利益を被ることなく、または、反対に、何らかの改善を実現することなく、我々が望むようにオリエンテーションを選ぶことができる、場合である。特に、我々は、そのボロノイ図が完全であるように、正方形を向ける。我々がそうする場合、および正方形が上記の最適な辺長さを有する場合、我々は、任意の４−要素コードブックに対して、サーチも明示的なコードブックも要求せず、また最も少ない可能な歪みを実現するベクトル量子化方式を得る。この選択は、図９に表わされる。【００５６】  これは、全て、データが、原点に中心がある円の範囲内に、一様に分布するという推定、極めて人工的およびありそうにないように思われる条件に依存する。しかし、このことは、次に、すぐに、次の一般的な方式を提案する：Ｄ−次元のベクトル量子化問題が与えられた場合、変換されたデータのセットが、Ｄ−次元の球の範囲内の一様な分布に近づくであろうように、その関連した代表例データのセットεに適用可能である、簡単な、可逆関数を捜してみよう。我々は、次に、適切なＤ−超立方体コードブックに関して、それらを量子化することにより、データソースから発生する変換されたベクトルを、圧縮することができる。我々は、所望の関数を、対称化変換と称するであろう。【００５７】  この提案は、特に、それを見つけ出す方法に対する指示は言うまでも無く、このような変換のどのような形を取るかについての如何なるヒントも、提供しないという点において、不完全である。それは、コードブックに対する半径ベクトルも供給しない。しかしながら、これらは、我々が説明するであろう本発明の次の２つの要素：所望の変換を見つけるためのアルゴリズム、および関連したコードブックの半径ベクトルを決定するためのアルゴリズムである。【００５８】  ２つの重要な警告が、言及されなければならない。【００５９】
2007526669.tif 000040
素のコードブックに対して最小の歪みを実現するであろうという保証は、存在しない。このことは、圧縮されるべきベクトルが、実際、Ｄ−球内に一様に分布させられる場合でさえ、そうである。それにもかかわらず、実際、本発明の方法は、極めて効果的であることを証明した。【００６０】  第二に、たとえ所定のコードブックが、固定された数のコードワードに対して最小の歪みを達成するという意味において、そのサイズに最適であっても、再構成されたデータが、オリジナルに対して十分に高い忠実度を表わすであろうという保証は存在しない。【００６１】  次の２つのセクションにおいて、我々は、対称化変換、および最適なＤ−超立方体コードブックを、それぞれ、計算する方法を説明する。【００６２】対称化変換を見つける
ここで、我々は、要求される、対称化変換を見つける方法を説明する。我々が開発するであろう技術は、唯一可能な問題へのアプローチではない。この特定の方法と無関係に、我々は、このまたは任意の他の技術により決定される対称化変換を用いた、または任意の変換ステップを全く無しに、Ｄ−超立方体コードブックを介した、効率的なベクトル量子化の一般的な考えに関する優先権を請求する。【００６３】変換を見つける
仮定により、我々は、導入において生じるであろうデータと同じ統計を表す大きな代表例データのセット
2007526669.tif 000041
が供給される。一般性の損失無しに、我々は、εが、ゼロ平均を有する；すなわち、
2007526669.tif 000042
であり、および拡張により、同じことが、ソースデータ自体に当てはまることをさらに仮定することができる。そうでない場合、我々は、新しい代表例の集合
2007526669.tif 000043
から平均
2007526669.tif 000044
【００６４】
2007526669.tif 000045
い。逆が、明確に真ではない−それに対する共分散行列がスケール変更された単位行列である、球対称ではない、ゼロ平均データのセットが存在するが−我々は、それにもかかわらず、以下の方式を採用する：我々は、
2007526669.tif 000046
のような線形変換
2007526669.tif 000047
を捜す。我々は、次に、Ｔを対称化変換として使用する。ここで、Ｉは、Ｄｘ  Ｄ単位行列を示し、かつ表記Ｔεは、各ベクトルにＴを適用した
2007526669.tif 000048
のコピーである
2007526669.tif 000049
を意味する。意図されたＴの効果は、図１０ａおよび１０ｂに示される。図１０ａは、変換前のデータ（ε、楕円内に分布する１０００個のポイント）を示す；図１０ｂは、変換後のデータ（Ｔε、Ｔにより変換された同じ１０００個のポイント）を示す。【００６５】  我々は、続けて、まさに採用された対称性基準と一致するＴを見つけるためのアルゴリズムを開発する。ここで、異なる変換におそらく導くであろう他の基準が使用可能であることは、注目に値する。この方法は、線形代数において、いわゆる白色化（ｗｈｉｔｅｎｉｎｇ）変換をもたらす標準操作である；本発明の１つの新規な観点は、我々がこの技術を適用する方法の中に位置する。【００６６】  ゼロ−平均データのセットεの共分散行列の定義
2007526669.tif 000050
を思い出されたい。【００６７】  仮定より、εの各要素ｖは、Ｄ−要素の列ベクトルであり；ｖｌは、その転置の行−ベクトルを
2007526669.tif 000051
が、対称であり、非負定値行列であることに留意されたい。従って、スペクトル定理（非特許文献５を参照）によって、関連した実数の、非負の固有値
2007526669.tif 000052
を有する、Ｄ固有ベクトル、
2007526669.tif 000053
の正規直交の集合が存在する。定義により、これらは、列ベクトルであり、かつ
2007526669.tif 000054
を満足する。【００６８】  固有ベクトルおよび関連した固有値は、数値線形代数の任意の選ばれた方法により、見つけられる；詳細は、非特許文献６を参照されたい。【００６９】  今、その行が、転置された固有ベクトルである、行列Ｓを作成すると、
2007526669.tif 000055
である。線は、ベクトルが行列内で延在する方向を示すためのものである。【００７０】
2007526669.tif 000056
2007526669.tif 000057
を得る。ここで、第２の等式は、（８）から得られる。【００７１】
2007526669.tif 000058
である。【００７２】  従って
2007526669.tif 000059
言い換えると、結果は、関連した固有値が対角線上に順に現れ、かつ他はどこでも、ゼロ
2007526669.tif 000060
【００７３】  このことは、以下のように、我々を、我々が望む変換に直接導く。（１１）の左端および右
2007526669.tif 000061
を掛けることにより、我々は、
2007526669.tif 000062
を得る。（ここで、最後の等式は、３つの示された行列の積を単に計算することにより、得られる。）（７）からのＺ（ε）の定義をこれに代入すると、
2007526669.tif 000063
となる。ここで、最後の等式は、乗算に対して適合した任意の行列に対して、恒等式（ＡＢ）ｔ＝ＢｔＡｔから導かれる。（非特許文献７を参照。）【００７４】次に、
2007526669.tif 000064
ゼロ平均を有する：
2007526669.tif 000065
なぜなら、Ｔが、線形変換であり、かつεは、ゼロ平均を有するからである。（１６）からピックアップすると、
2007526669.tif 000066
は、明らかである。なぜなら、左端の和が、εの変換された要素から形成された外積を結合し、および右端が、同じ変換された要素から形成されたこれらの同じ外積を結合するか
2007526669.tif 000067
分散行列としてＩを有するデータのセットをもたらし、それ故、Ｔは、我々が捜す変換である。【００７５】縮退の場合
2007526669.tif 000068
厳密であることを保証されないことに留意されたであろう。すなわち、１つ以上の値のｉに
2007526669.tif 000069
可能であるので、本明細書で議論された方法を、明らかに、妨げる。【００７６】
2007526669.tif 000070
内の全てのベクトル、および拡張により、導入において生じるすべてのベクトルが、εが代表的であると仮定されるので、対応する固有ベクトルＺｉと直交することを意味する。従って、圧縮されるべきデータは、全て、Ｄ−１−次元の超平面内に位置する。我々は、それ故に全て、データを適切なＤ−１−次元の空間（特に、ｚと直交する超平面）に投影することができ、かつ続けて我々の方法を結果として生じるデータのセットに適用することができる。このことは、Ｄ−１ビットのみが、処理される各ベクトルに対して、伝送されるので、より高率な圧縮さえもたらす。１つ以上の固有値がゼロである場合、この手順は、非ゼロ固有値のみが残るまで、反復可能である。【００７７】ＴおよびＴ−１の効率的な結合表現
行列Ｔ−１は、伸張ステップを実行するために、必要とされる；それは、また、いわゆる閉ループ（ｃｌｏｓｅｄ−ｌｏｏｐ）圧縮、不可逆的データ圧縮方法と共通に併用して使われる技術のために必要とされる。ＴおよびＴ−１を両方格納することは、明示的に、２・Ｄ２・Ｆビットを要求する（ここで、Ｆが、行列エントリ当りのビットの数である）。これは、典型的なベクトル量子化コードブックより非常に小さい一方、それは、なお著しい量のメモリを消費するかもしれない。【００７８】  この理由から、我々は、今、両方の行列を表わすために、ＴおよびＴ−１を代数形式を活用した方法を記載するが、これは、２つの行列を明示的に格納する上で、約２分の１だけ、メモリ低減をもたらす。この方法と関連したプログラムサイズおよび計算のわずかな増加が存在する。しかしながら、それは、メモリコストを計算コストと交換する効果的な方法である。【００７９】  開始するために、我々は、Ｔ−１の形を定める。上記の式（１７）から、我々は、
2007526669.tif 000071
を得る。
2007526669.tif 000072
ということになる（非特許文献８を参照）。簡単な計算は、Ｓ正規直交の固有ベクトルの行列であり、
2007526669.tif 000073
を示し、それゆえ
2007526669.tif 000074
である。さらに、我々が、
2007526669.tif 000075
を定義する場合、
2007526669.tif 000076
であることは、明らかであり、それゆえ
2007526669.tif 000077
である。従って
2007526669.tif 000078
【００８０】  このことは、これらの後半の３つの行列のみを、メモリの（Ｄ２＋２Ｄ）・Ｆビットのコストで格納することが、十分であることを意味する。このことは、各対角行列が、そのＤの非ゼロ要素のみにより、表されることが可能であると理由が、起こる。さらに、必要な場合、対角行列の何れか１つは、対応する対角要素が、まさに、互いの逆数であるので、無しで済ますことができる；このことは、さらに、そのコストを（Ｄ２＋Ｄ）・Ｆビットに減少させる。【００８１】最適な半径ベクトルを見つける
このセクションにおいて、我々は、最適なＤ−超立方体コードブックに対する半径ベクト
2007526669.tif 000079
全てのＤ−超立方体コードブック中で、最小の平均二乗コーディング歪みをもたらすという
2007526669.tif 000080
径ベクトルと称する。【００８２】  次のヘルパー関数
2007526669.tif 000081
を定義することは、有益であろう：
2007526669.tif 000082
である。【００８３】
2007526669.tif 000083
である。【００８４】
2007526669.tif 000084
【００８５】  式（２６）で使用されるノルムが、変換された空間で計算された、標準ユークリッド距離であることに留意されたい。我々は、このポイントに関して以下でさらに述べなければなら
2007526669.tif 000085
しかし、
2007526669.tif 000086
は、ｉ＝ｊでない場合、０であり、そうである場合、それは、１である。従って、内側の和は、ｊ＝ｉ項に対してのみ折りたため、および我々には、我々が、最適の条件として、それを０と等しいとする、
2007526669.tif 000087
が残される。定数をクリアするためにＵ／２を掛け、減算される項を右辺へ移行すると、我々は、等価に、
2007526669.tif 000088
可能であるという事実を活用した。）。しかし、上記したように、
2007526669.tif 000089
である。従って、我々は、
2007526669.tif 000090
を得る。しかし、左側の和は、１のＵ個のコピーを合計した結果であり、従って、それ自身は、Ｕに等しい。Ｕで割ると、
2007526669.tif 000091
を得る。各々に対して、ｉ＝１，…，Ｄである。このことは、最適なＤ−超立方体コードブックを定義する。【００８６】  このアルゴリズムの漸近的コストは、以下のように、決定される。我々は、対称化変換Ｔ
2007526669.tif 000092
【００８７】  式（３２）の単一の事例は、絶対値関数のＵ回の適用、Ｕ−１回の加算、および１回の除算を要求
2007526669.tif 000093
のＤ回の適用により、完全に決定されるので、アルゴリズムの漸近的コストは、０（ＤＵ）である。【００８８】
2007526669.tif 000094
この乗算のコストは、ｕの各要素が０（Ｄ）の算術演算を有するＤ回の乗算およびＤ−１回の加算により決定されるので、０（Ｄ２）であり、および計算するための、ｕのＤの要素が存在する。それ故、ｕを形成する漸近的コストは、０（Ｄ２Ｕ）回の演算である。【００８９】  対称化変換Ｔを見つけるコストは、使用されるアルゴリズムに依存する。Ｔを見つけるための典型的なアルゴリズムは、非特許文献９に記載されるヤコビ回転の方法である。この方法の漸近的コストは、それが、反復アルゴリズムであるので、その正確な実行時間は、データに依存するにもかかわらず、０（Ｄ３）である。従って、ｕおよびＴの生成が計算に入れられても、Ｄ−最適な超立方体アルゴリズムは、ＤおよびＵの両方において多項式である、０（Ｄ２（Ｕ＋Ｄ））回以下の演算コストですむ。【００９０】  ここで議論された手順が、暗示的に、２Ｄ個のコードポイントを定義する、全部のＤ−超立方体コードブックを決定することに留意されたい。比較により、図２のＫ−ｍｅａｎｓアルゴリズムは、等しいサイズ（すなわち、Ｋ＝２Ｄ）のコードブックを作成するために、少なくとも、０（ＵＤ２Ｄ）回の演算の漸近的コストを有する。これは、Ｋ−ｍｅａｎｓアルゴリズムが、２Ｄ個のコードポイ
2007526669.tif 000095
εの各要素を各対象コードポイントと比較しなければならないからである。【００９１】  我々は、等しいサイズのコードブックを計算する時、それらの漸近的コストの比率を調べることにより、２つのアプローチの効率を比較することができる；すなわち、
（Ｋ−ｍｅａｎｓアルゴリズムのコスト）／（最適な半径ベクトルアルゴリズムのコスト）。【００９２】  この比率は、（ＵＤ２Ｄ）／Ｄ２（Ｕ＋Ｄ））である。この関数が指数関数的に、Ｄとともに増大するので、最適な半径ベクトルアルゴリズムは、等しいサイズのコードブックを作成する時、Ｋ−ｍｅａｎｓアルゴリズムより、指数関数的に、さらに効率的である。【００９３】圧縮および伸張
必要な機械が、今、全て適所にある場合、我々は、完全な圧縮および伸張アルゴリズムを示すことができる。【００９４】基本的なアルゴリズム
我々は、前の２つのセクションに与えられた手順に従って、我々が、ＴおよびＴ−１
2007526669.tif 000096
Ｄ−超立方体コードブックを見つけたと仮定する。【００９５】  議論を明確にするために、我々は、数個の“ヘルパー”関数を以下のように定義する。
2007526669.tif 000097
ある。
2007526669.tif 000098
言い換えると、その引数が負の場合、ｍは、値１となり、およびその引数がゼロまたは正の場合、０となる。【００９６】
2007526669.tif 000099
により定義する（ここで、ビットは、ｎの最も小さい有効なビットとして、ビット０で番号を付けられる）。【００９７】  圧縮および伸張のためのアルゴリズムは、図１１および１２にそれぞれ与えられる。【００９８】  図１１は、ベクトルｖを圧縮するためのアルゴリズムを示す。Ｔは、対称化変換である。関数ｍ（ｘ）は、本明細書で定義される。このアルゴリズムは、コードブックが、どこにも、明
2007526669.tif 000100
【００９９】
2007526669.tif 000101
書で定義される。行列Ｔ−１は、式（２０）によって与えられる、対称化変換の逆である。このアルゴリズムは、コードブックが、どこにも、明示的に構成されない、または調査されない
2007526669.tif 000102
クコストが、懸念でない場合、テーブルルックアップ演算に換算可能である。【０１００】距離考察
2007526669.tif 000103
演算することは、この時点までの議論から明らかであるはずである。Ｔが最大階数の仮定に
2007526669.tif 000104
暗示的に、本明細書において他の場所で議論により定義されるように、変換された空間内
2007526669.tif 000105
今、示すように、このことは、変換されていない空間内で共分散行列Ｚ（ε）して計算された、マハラノビス・ノルムを使用することに対応する。抽象ベクトルデータに対する固有の１つ、すなわち、ユークリッド空間において座標測定から導出されないベクトルである、マハラノビス・ノルムの議論は、非特許文献１０に見出だされる。【０１０１】  我々は、続けて、マハラノビス・ノルムに関して所望の結果を定める。開始するために、
2007526669.tif 000106
ｄ２（ｕ，ｗ）が、
2007526669.tif 000107
により与えられることに留意されたい。Ｔが、線形変換であるので、我々は、（ｕ−ｗ）＝（Ｔｖ−Ｔｓ）＝Ｔ（ｖ−ｓ）を得る、従って、我々は、
2007526669.tif 000108
と書くことができる。【０１０２】  今、上記の式（１１）は、さらに簡潔に、
2007526669.tif 000109
として書くことが可能で、これから、
2007526669.tif 000110
となる（ここで、上記実証したＳ−１＝Ｓｔという事実を使用した）。今、Ｚ（ε）が、可逆行列である場合、（４４）の両辺を反転すると、我々は、
2007526669.tif 000111
を得る。【０１０３】  上記（４３）を代入すると、我々は、
2007526669.tif 000112
を得る。これは、共分散行列Ｚ（ε）に関して、オリジナル空間におけるマハラノビス・ノルムである。【０１０４】拡張
このセクションにおいて、我々は、コーディング歪みを減少させる、基本的な方法の一連の拡張を説明する。この開発は、３つの部分に続く。【０１０５】  我々は、先ず、回転方法を説明する。これは、歪みを減少させることができるが、そうすることを保証可能ではない基本的な方法の改良である。この拡張の鍵となる利点は、この方法が、圧縮システムにおけるメモリおよび計算の要求において、増加を要求しない、またはきわめて少なめの増加のみを要求し、かつ圧縮されるデータのサイズ（または、等価な、圧縮されたデータを伝送するために必要とされる帯域幅）における増加を伴わない一方で、コーディング歪みを減少させることができることである。【０１０６】  次に、我々は、複数の超立方体方法を説明する。これは、同様に、歪みがゼロでない場合、コーディング歪みを減少させることを保証する、基本的な方法の改良である。しかしながら、（バーチャルな）コードブックを強化することに基づく、この方法は、システムのメモリ、帯域幅および計算の要求を増加させる。幸運にも、我々が実証するように、これらは、全て、超立方体コードポイントの合計数と共に、極めてゆっくりと、単に対数的にのみ増加する。【０１０７】  最後に、我々は、これらの２つの技術を結合し、かつさらに小さい歪みを提供できる、代替サーチ方法を説明する。【０１０８】  各方法は、圧縮および伸張用、および以下に詳細に説明されるこの方法に現れる様々のパラメータの決定用の様々の関連したアルゴリズムを有する。これらのアルゴリズムは、新規であり、かつ本発明の部分を構成する。【０１０９】回転方法
上記我々の方法の根底をなす基本的な考えを開発する場合、我々は、対称性の議論を使用し、以下のことを定めた：圧縮されるべきデータが、球内に、一様に分布する場合、よ
2007526669.tif 000113
とをとりわけ簡単にするオリエンテーションを自由に選ぶことができる。【０１１０】  正しい一方、この議論は、圧縮されるべきデータの分布が、対称化変換Ｔの適用の後でさえ、実際、球対称であろうという非現実的な仮定に依存する。従って、超立方体コードブックを回転することが、歪みを小さくすることが可能なのかという疑問が生じる。我々が、このセクションにおいて続いて実証し、次に系統的に活用するように、この疑問に対する答えは、イエスである。【０１１１】  回転された超立方体コードブックは、もはや、完全ではないであろう−すなわち、必然的
2007526669.tif 000114
効率的な計算を可能にするこの特性であるので、任意の他のオリエンテーションを使用することは、方法の鍵となる利点を削除すると思われるであろう。しかし、我々が、まもなく実証することになるように、実際、任意のオリエンテーションの超立方体に対応することは、方法の計算の効率またはメモリ使用量に影響を与えることなく、可能である。【０１１２】動機を与える代表例
このセクションにおいて、我々は、超立方体コードブックを回転する考えに動機を与える。このことは、代表例データのセットεを表し、その対称化変換Ｔを計算し、変換された
2007526669.tif 000115
れる。【０１１３】  図１３ａおよび１３ｂは、このような代表例を表す。図１３ａに示される、開始データのセットεは、特定の対称性を有さない。上記手順に従うと、我々は、図１３ｂに示されるＴεをもたらす、ゼロ−平均および対称化変換を見つける。驚く程のことではないが、Ｔεは、見たところでは、より球状の外観を有する；さらに、構成により、その共分散行列は、恒等式である。【０１１４】
2007526669.tif 000116
成により、結果として生じる超立方体コードブックは、完全である。図１３ａおよび１３ｂにお
2007526669.tif 000117
【０１１５】  コーディング歪みの超立方体のオリエンテーションへの依存を実証すために、我々は、
2007526669.tif 000118
名目の全回転空間をサーチすることは、必要ない：任意の超立方体面に平行な任意の平面において、それを、その中心の周りに正確にπラジアンまで回転することは、コードポイントのインデックスを変更するが、それらの位置を変更しない。従って、時計方向のθラジ
2007526669.tif 000119
分である。【０１１６】  結果として生じるデータは、超立方体回転角度に対する一要素当たりの歪みを示す、図１４にグラフ化される。約−１ラジアンでの局所極小が、約＋０．２８ラジアンでの真の極小と同程度には深くないことに留意されたい。歪みは、極小から極大まで、約１１％の全変動を表す。
2007526669.tif 000120
ンによる、超立方体の反時計方向の回転に対応することを決定する。このことは、回転されない超立方体に関して、歪みを、要素当り０．６１３２二乗歪み単位、約４％の低減に至らせる。回転された超立方体は、図１５ａに表わされる。【０１１７】  ここで、以下の簡単、しかし本質的な双対性は、注目に値する。コーディング歪みに関
2007526669.tif 000121
何れの場合も、同じ長さであり、従って、歪みは、同一であろう。完全な端末間データ圧縮システムを構成する場合、圧縮アルゴリズム内にその回転される位置に対してデータの適切な回転、および伸張アルゴリズム内に再構成されたベクトルの逆の回転を組み込むことが、必要なだけである。我々が以下に実証するように、両方とも、ゼロの計算または記憶のオーバーヘッドで、達成可能である。【０１１８】  データを回転する利点は、超立方体に対して、回転されない超立方体のボロノイ図が、完全であることであり、故に、我々は、すでに記載されたアルゴリズムの利点を全て保証
2007526669.tif 000122
2007526669.tif 000123
て、図１５ｂに表わされる。我々は、この双対性をさらに以下で議論するであろう。【０１１９】  この考えに対する拡張は、超立方体のオリエンテーションばかりでなく、所定のオリエンテーションで半径ベクトルも変化させることである。回転の無いケースに対して計算さ
2007526669.tif 000124
由はない。この疑問は、上記図１４をもたらした同じ技術により、各サンプリングされた回
2007526669.tif 000125
グラフは、一要素当たりの歪みに対する超立方体回転角度を示す、図１６に現れる。このグ
2007526669.tif 000126
れたような同じデータおよび方法で準備された。２つの極小が等しい深さであることに留
2007526669.tif 000127
およびこの回転での歪みは、０．６１３２から０．６１３０二乗歪み単位まで減少する。しかしながら、原則として、この拡張は、ある程度の改善もたらすことができ、故に、我々は、それを、ここに記録する。【０１２０】回転方法の実施
回転方法を実施する時、表面上対称化変換Ｔに従う、所望の回転Ｒは、Ｔに組み込み可能である。すなわち、対称にされたベクトルｕ＝Ｔｖを圧縮する代わりに（ここで、Ｔは、先に議論された対称化変換である）、圧縮は、回転された、対称にされたベクトルｕ＝ＲＴｖに関して行われる。この式は、表面上２つの演算を示す：ベクトルｖに行列Ｔを掛け、次に、その計算の結果に別の行列Ｒを掛ける。この第二の乗算は、表面上、追加の記憶および計算の両方を要求する。【０１２１】  しかしながら、任意の圧縮を実行することに先立って、単一な行列積Ｍ＝ＲＴを形成し、次に、基本的な方法により、回転された、対称にされたベクトルｕ＝Ｍｖを圧縮することにより、歪みの所望の低減は、メモリ、計算または帯域幅の増加を伴なわず、実現可能である。これは、行列ＲおよびＴを別々に表すことに関連したメモリが、今、基本的な方法において、Ｔ単独を表すのと同じコストで、単一な行列を表すＭ＝ＲＴに合体されるからである。同様に、Ｔによる乗算を、続くＲによる乗算と別々に実行することに関連した計算は、今、基本的な方法においてＴ単独を掛けるのと同じコストで、単一な行列Ｍによる乗算に合体される。【０１２２】  閉じた超立方体頂点のインデックスをベクトルｕ＝Ｍｖに対して見つけ、および伝送することは、基本的な方法におけるように、正確に進行し、従って、これらのステップと関連したコストは、変更されない。【０１２３】  適用される実際の回転および対称化変換は、そのために異なるが、回転および対称化の順序は、交替可能である。【０１２４】複数の超立方体方法
このセクションにおいて、我々は、提供することがもはやゼロではない、期待される平均コーディング歪みを小さくすることを保証される方法を記載する。前のセクションの回転方法と異なり、この技術は、システムのメモリおよび計算の要求、並びにアップストリーム帯域幅を増加させる。【０１２５】  この方法の考えは、一文において記載可能である：歪みを減少させるために、超立方体の数を増加させることにより、コードポイントの数を増加させることである。このことは、追加の超立方体半径ベクトルを格納するためのメモリを要求し、さらに、圧縮アルゴリズムに明示的距離計算を加えることを我々に強制する。しかしながら、追加のメモリおよび計算の要求の増加の費用は、追加のコードポイントが加えられる費用と比較して、非常に小さい；特に、それらは、コードブックの効果的なサイズと共に対数的に増えるだけである。【０１２６】  この議論は、以下のように、整理される：【０１２７】第一に、我々は、その方法を記載し、およびその圧縮および伸張アルゴリズムを供給する。【０１２８】  次に、我々は、それが、平均コーディング歪みを小さくすることを保証する方法を示し、さらに、それがメモリおよび計算のリソースを対数的に増やすことのみを要求することを実証する。【０１２９】  最後に、我々は、その方法において使用可能な、一群の超立方体コードブックを見つけるために、効率的なアルゴリズムを記載する。【０１３０】説明および基本的なアルゴリズム
2007526669.tif 000128
び伸張は、それらの関連した半径ベクトルのセット
2007526669.tif 000129
により定義される一群のＫ個の別個のＤ−超立方体コードブックに関して、行われる。そのセットＡと関連した（暗示的）コードポイントの合計数がＫ・２Ｄ個であることに留意されたい。各半径ベクトルが、その各頂点がコードポイントであるＤ−超立方体を記載し、かつＤ−超立方体の２Ｄ個の頂点が存在するので、このことは、結果としておこる。より多くのコードポイントが存在するので、各有限のボロノイセルのボリュームは、より小さく、従って、平均コーディング歪みは、減少する。【０１３１】  超立方体コードブックの集合に関して、ベクトルｖを圧縮することは、上記の基本的なものよりわずかに複雑なアルゴリズムを要求する。単一な超立方体コードブックで圧縮する時のように、我々は、対称化変換Ｔを適用することにより開始し、ｕ＝Ｔｖを得る。同様に、単一な超立方体コードブックで圧縮する時のように、ｕに最も近いコードポイントのオーサント（ｏｒｔｈａｎｔ）は、公知である。特に、それは、超立方体の全てが完全であり、従って、正確にオーサント自体から成る同じボロノイセル構造を共有するので、ｕ自身のオーサントでなければならない。しかしながら、今、選択されたオーサント範囲内に位置するその各々が頂点を有する、Ｋ個の別個の超立方体コードブックが存在する。Ｋ個の可能性内の、オーサントの範囲内の最も近い超立方体頂点の識別は、定められなければならず、従って、少量の明示的サーチは、今、圧縮のために要求される。【０１３２】  事例に基づいて、圧縮アルゴリズムは、今、以下のようになる：
１．圧縮するベクトルｖが与えられた場合、ｕ＝Ｔｖを見つける；
２．正確に、図１１におけるようにｉ＝ｍ（ｕＤ）ｍ（ｕＤ−１）…ｍ（ｕ１）としてエンコードされたｕのオーサントを見つける；
2007526669.tif 000130
ｋを見つける。（このサーチは、また、変換されたベクトルｕを以下に定義されるマップｐによりこのオーサント内へマッピングし、かつ正のオーサント内の頂点の中で、最も近い超立方体のインデックスｋのためのサーチを実行することにより、正のオーサント内でも実行可能である。この結果は、同一であろう。）【０１３３】このサーチの結果は、オーサントの識別ｉと一緒に、受信側に伝送されなければならない；従って、わずかに大きなアップストリーム帯域幅を要求する。伸張するために、受信側は、
2007526669.tif 000131
【０１３４】  複数の超立方体を用いた圧縮および伸張のためのアルゴリズムは、図１８および１９にそれぞれ詳細に記載される。ここで、図１８は、複数の超立方体方法によりベクトルｖを圧縮するためのアルゴリズムを示す（関数ｍ（ｘ）は、本明細書において定義される）；および図１９は、
2007526669.tif 000132
本明細書において、定義される）。【０１３５】  この説明は、ここで詳述されるいくつかの特殊な専門語を利用する。我々は、非負の実
2007526669.tif 000133
により定義する。【０１３６】
2007526669.tif 000134
により定義する。【０１３７】  超立方体半径ベクトルのセットＡに関して演算する、圧縮および伸張アルゴリズムの合成
2007526669.tif 000135
を圧縮し、次に伸張する結果を示す。【０１３８】  圧縮アルゴリズムの演算は、グラフィカルに図１７に表わされる。図１７は、陰影を付けられたｕ＝Ｔｖのオーサントを示す；これは、完全な超立方体の各々の共通のボロノイセルに
2007526669.tif 000136
つけるために、サーチされる必要がある。陰影を付けられたオーサントは、その範囲内に
2007526669.tif 000137
近いコードポイントを見つけるために、明示的にサーチされる必要がある。【０１３９】歪み低減；対数的リソース要求
我々は、今、超立方体の適切な選択により、この方法が、平均の期待されるコーディング歪みにおける低減を保証することができることを示す。我々は、我々が今示すであろう技術が、歪みの低減を保証するものの、幾分非効率的であるので、用語「超立方体の適切な選択（ａｐｐｒｏｐｒｉａｔｅ  ｃｈｏｉｃｅ  ｏｆ  ｈｙｐｅｒｃｕｂｅｓ）」を慎重に使用する。以下の議論において、我々は、超立方体を選択する、優れた方法、オーサントＫ−ｍｅａｎｓアルゴリズムを記載する。しかしながら、後者の方法は、重大な利点を提供するものの、歪みの低減を保証しない。このポイントは、後半のアルゴリズムの開発において、さらに議論される。
2007526669.tif 000138
であることを思い出されたい。【０１４０】
2007526669.tif 000139
であると仮定する。
2007526669.tif 000140
とし、
2007526669.tif 000141
をセットする。この時、明らかに、
2007526669.tif 000142
であり、従って、
2007526669.tif 000143
たらすかの何れかである。【０１４１】  今、Δ（Ａ）は、
2007526669.tif 000144
関してのみ進行することに留意されたい。）同様に、Δ（Ａ’）は、正確に同じ方法で、書か
2007526669.tif 000145
る、Δ（Ａ）とΔ（Ａ’）の差を取ると、我々は、
2007526669.tif 000146
を得る。最後の不等式は、厳密であり、従って、請求されるように
2007526669.tif 000147
である。【０１４２】  （暗示的に、定義される）２Ｄ個のコードポイントをコードブックに結び付けるこの方法のコストは、まさに、Ｋ個の別個のＤ−超立方体半径ベクトルの集合Ａにおける、任意のベクト
2007526669.tif 000148
【０１４３】
2007526669.tif 000149
ために、全ての超立方体を使用し、それによって、コーディング歪みを減少させるという
2007526669.tif 000150
ディング歪みを説明するための、如何なる試みもなされない。これらの弱点は、次のセクションのアルゴリズム、オーサントＫ−ｍｅａｎｓアルゴリズムにより、修復される。【０１４４】オーサントＫ−ｍｅａｎｓアルゴリズム
2007526669.tif 000151
たらすＫ個の完全な超立方体コードブックの集合を効率的に見つける、オーサントＫ−ｍｅａｎｓアルゴリズムを記載する。続くテキスト内で、我々は、この方法の背後にある直感を説明する。アルゴリズムの正確な説明は、図２３に現れる。このアルゴリズムは、変換された代
2007526669.tif 000152
個の別個のＤ−超立方体コードブックの集合を決定する。このアルゴリズムは、新規であり、かつ本発明の一部を構成する。【０１４５】
2007526669.tif 000153
ド化するために、最小の−歪み基準に関して最適な単一な完全なＤ−超立方体コードブックを
2007526669.tif 000154
さらに歪みを減少させる、Ｋ＞１の完全なＤ−超立方体の集合を見つけることである。【０１４６】  この問題は、典型的には、Ｋ個のコードポイントのセットを定めるために、図２に上記された、Ｋ−ｍｅａｎｓアルゴリズムを使用するであろう、従来のベクトル量子化コードブックの設計者に直面するものに類似している。我々の目的に対する、このアルゴリズムに関する問題は、捜したコードポイントの数（すなわちＫの値）が、適切な２の複数乗である場合でさえ、選択されたコードポイントが、一般的には、完全な超立方体の頂点に位置しない。このことは、８つのコードポイントを生成するために従来のＫ−ｍｅａｎｓアルゴリズムを示されたデータに適用する効果を示す、図２０ａおよび２０ｂで表わされた代表例において明らかである。図２０ａおよび２０ｂは、従来のＫ−ｍｅａｎｓアルゴリズムを示す。ここで、図２０ａは、変換された代
2007526669.tif 000155
す。【０１４７】  従来のＫ−ｍｅａｎｓアルゴリズムを適用することに対する障害は、それが見つけるコードポイントが、１つ以上の完全な超立方体の頂点に位置することを強いられないことである。実際、トレーニングデータの要素の範囲内の単一の超立方体を発見する方法さえ、すぐに明らかではない。すなわち、その要素が全て、或る完全な超立方体コードブックの頂点近く
2007526669.tif 000156
関して超立方体配置に位置する、１つのポイントセットの特性は、明らかに非局所的である。
2007526669.tif 000157
る他の要素を調べることにより、発見可能である特性ではない。オーサントＫ−ｍｅａｎｓアルゴリズムは、次の所見を活用することにより、この障害を解決する。式（６）により定義された
2007526669.tif 000158
2007526669.tif 000159
【０１４８】  このことは、以下の重要な結果を有する。我々が、変換されたトレーニングデータを正
2007526669.tif 000160
において、それぞれ明らかである。ここで、完全な２−超立方体頂点にまたは近くに位置す
2007526669.tif 000161
ピングされる時、自然に、２つのクラスタに分かれるように思われる。【０１４９】
2007526669.tif 000162
は、図２２ｂに表わされる。幾つかの超立方体頂点が、コードポイントとして効果的に使われていないことは、そこで、明らかである。しかし、このことは、実現された歪みが、それにもかかわらず、全く小さく、かつ完全な超立方体技術の使用が、前に議論されたメモリおよび計算の要求の大きな効率を有するので、問題ではない。【０１５０】  この洞察は、本発明の一部であり、かつ図２３に詳細に記載される、オーサントＫ−ｍｅａｎｓア
2007526669.tif 000163
折りたたむことによって得られるので、折りたたまれたデータ（ｆｏｌｄｅｄ  ｄａｔａ）と称される。折りたたまれたデータは、次に、Ｋ個のクラスタを見つけるために、従来のＫ−ｍｅａｎｓアルゴリズム内に見つけられるものに類似する反復技術により処理される。従来のバージョンお
2007526669.tif 000164
2007526669.tif 000165
トルは、次に、構成により、完全なＤ−超立方体頂点に位置しなければならない、所望のＫ・２Ｄ個のコードポイントを暗示的に定義する。【０１５１】  Ｋ・２Ｄ個のコードポイントを従来のＫ−ｍｅａｎｓアルゴリズムにより得ることが、Ｋ・２Ｄ個の対象コードポイントのセットを維持し、かつ反復して、アップデートすることを要求するであろうことに留意されたい；漸近的コストは、０（Ｕ・Ｄ・２Ｄ・Ｋ）の演算である。比較により、Ｋ・２Ｄ個の暗示的コードポイントのコードブックを同様に生成する、オーサントＫ−ｍｅａｎｓアルゴリズムは、ちょうど０（Ｕ・Ｄ・Ｋ）の演算の漸近的コストを有する。前のように、我々は、比較されるアルゴリズムのコストの比率、この場合、（従来のＫ−ｍｅａｎｓアルゴリズムのコスト）／（オーサントＫ−ｍｅａｎｓアルゴリズムのコスト）を調べる。【０１５２】  この比率は、（Ｕ・Ｄ・２Ｄ・Ｋ）／（Ｕ・Ｄ・Ｋ）であり、したがって、我々は、オーサントＫ−ｍｅａｎｓアルゴリズムが、その従来の等価物より、指数関数的にさらに効率的であることを理解する。同様の議論は、２つのアルゴリズムの比較に関するメモリ要求に適応される。従って、オーサントＫ−ｍｅａｎｓアルゴリズムは、その従来の等価物より、相当に速く演算するであろう。このことは、暗示的コードブックの再計算がリアルタイムで発生しなければならない、本発明の適応可能な、動的なアプリケーションにおいて、重大な利点である。【０１５３】  さらに、オーサントＫ−ｍｅａｎｓアルゴリズムは、固定されたＫおよびＵに対して、それが、０（２Ｄ）の暗示的コードポイントをコードブックの効果的なサイズにおいて（Ｄに関して）単に対数的であるコストで生成する限り、本質的に効率的である。【０１５４】  両方の場合において８個のコードポイントを生成するために、従来のおよびオーサントＫ−ｍｅａｎｓアルゴリズムの両方を適用する効果は、図２０ａ、２０ｂ；２１ａ、２１ｂ；および２２ａ、２２ｂに表わされる。【０１５５】  図２０ａおよび２０ｂは、従来のＫ−ｍｅａｎｓアルゴリズムの効果を示す（ここで、図２０ａは、変換
2007526669.tif 000166
ムの結果を示す）。【０１５６】  図２１ａおよび２１ｂは、オーサントＫ−ｍｅａｎｓアルゴリズムの効果を示す。ここで、図２１ａは、
2007526669.tif 000167
応する）。【０１５７】  図２２ａおよび２２ｂは、従来のＫ−ｍｅａｎｓおよびオーサントＫ−ｍｅａｎｓの比較を示し（ここで、図２２ａは、従来のＫ−ｍｅａｎｓからのコードポイントを示す）、および図２２ｂは、オーサントＫ−ｍｅａｎｓからのコードポイントを示す。図２２ｂにおいてポイントが、２−超立方体頂点に位置し；図２２ａにおけるそれらは、そうでないことに留意されたい。【０１５８】  本発明が、好適な実施例を参照して本明細書に記載されたにもかかわらず、当業者は、本明細書において本発明の精神および範囲から逸脱することなく、他のアプリケーションが本明細書に示されるそれらと置き換えることができることを容易に理解するであろう。したがって、本発明は、添付の請求の範囲によってのみ制限されるべきである。
【図面の簡単な説明】
【０１５９】
【図１ａ】各々がドットにより印を付けられ、かつ８つのクラスタに自然に分かれるように見える、２００個のプロットされた二次元ベクトルを示す圧縮用のデータを示す。
【図１ｂ】各々が星印により印を付けられた名目クラスタ中心と一緒に、プロットされた同じデータを示す、圧縮用のデータを示す。
【図２】広く使用されているベクトル量子化コードブックを決定するためのアルゴリズムである、従来のＫ−ｍｅａｎｓアルゴリズムを示す。
【図３ａ】隣接するセルのコードポイントから等距離のその平面上のポイントであるセル境界を示す、ボロノイ（Ｖｏｒｏｎｏｉ）図である。
【図３ｂ】加えられたデータポイントを有するボロノイ図である。
【図４ａ】隣接したコードポイントの対称性および関連したセル境界を示す。
【図４ｂ】隣接したコードポイントの対称性および関連したセル境界を示す。
【図５ａ】正方形およびそのボロノイ図を示す。
【図５ｂ】各々が（同じ）完全なボロノイ図を有する、様々な長方形を示す。
【図６】Ｄ＝３に対する完全な超立方体コードブックを示す。
【図７ａ】１０００個のポイントが半径２のディスク上の一様な分布からサンプリングされる、サンプリングされた対称データを示す。
【図７ｂ】４−ポイントのコードブックが、１００回のＫ−ｍｅａｎｓ反復により計算される、Ｋ−ｍｅａｎｓソリューションを示す。
【図８ａ】２つの回転で、等価なコードブックおよびボロノイ図を示す。
【図８ｂ】２つの回転で、等価なコードブックおよびボロノイ図を示す。
【図９】完全なボロノイ図を有する最適なコードブックを示す。
【図１０ａ】対称化変換の意図された効果を示し、変換を適用する前のデータ（ε、楕円内に分布する１０００個のポイント）を示す。
【図１０ｂ】対称化変換の意図された効果を示し、変換を適用した後のデータ（ε、Ｔにより変換された同じ１０００個のポイント）を示す。
【図１１】ベクトルｖを圧縮するためのアルゴリズムを示す。
【図１２】インデックスｉを伸張するためのアルゴリズムを示す。
【図１３ａ】特定の対称性を有さないデータを示し、かつオリジナルデータのセットε（２つの非整列の、オーバーラップする楕円間にランダムに分布する１０００個のデータポイント）を示す。
2007526669.tif 000168
【図１４】一要素当たりの歪みに対する超立方体回転角度を示す。
2007526669.tif 000169
【図１６】一要素当たりの歪みに対する超立方体回転角度を示す。
【図１７】複数の超立方体圧縮を示す。
【図１８】複数の超立方体方法によりベクトルｖを圧縮するためのアルゴリズムを示す。
2007526669.tif 000170
【図２０ｂ】従来のＫ−ｍｅａｎｓアルゴリズムの効果を示し、Ｋ＝８に対するＫ−ｍｅａｎｓアルゴリズムを示す。
2007526669.tif 000171
【図２２ａ】従来とオーサントＫ−ｍｅａｎｓとの比較を示し、従来のＫ−ｍｅａｎｓからのコードポイントを示す。
【図２２ｂ】従来とオーサントＫ−ｍｅａｎｓとの比較を示し、オーサントＫ−ｍｅａｎｓからのコードポイントを示す。
【図２３】オーサントＫ−ｍｅａｎｓアルゴリズムを示す。
【図１ａ】
2007526669.tif 000219
【図１ｂ】
2007526669.tif 000220
【図２】
2007526669.tif 000221
【図３ａ】
2007526669.tif 000222
【図３ｂ】
2007526669.tif 000223
【図４ａ】
2007526669.tif 000224
【図４ｂ】
2007526669.tif 000225
【図５ａ】
2007526669.tif 000226
【図５ｂ】
2007526669.tif 000227
【図６】
2007526669.tif 000228
【図７ａ】
2007526669.tif 000229
【図７ｂ】
2007526669.tif 000230
【図８ａ】
2007526669.tif 000231
【図８ｂ】
2007526669.tif 000232
【図９】
2007526669.tif 000233
【図１０ａ】
2007526669.tif 000234
【図１０ｂ】
2007526669.tif 000235
【図１１】
2007526669.tif 000236
【図１２】
2007526669.tif 000237
【図１３ａ】
2007526669.tif 000238
【図１３ｂ】
2007526669.tif 000239
【図１４】
2007526669.tif 000240
【図１５ａ】
2007526669.tif 000241
【図１５ｂ】
2007526669.tif 000242
【図１６】
2007526669.tif 000243
【図１７】
2007526669.tif 000244
【図１８】
2007526669.tif 000245
【図１９】
2007526669.tif 000246
【図２０ａ】
2007526669.tif 000247
【図２０ｂ】
2007526669.tif 000248
【図２１ａ】
2007526669.tif 000249
【図２１ｂ】
2007526669.tif 000250
【図２２ａ】
2007526669.tif 000251
【図２２ｂ】
2007526669.tif 000252
【図２３】
2007526669.tif 000253
【国際調査報告】
2007526669.tif 000254
2007526669.tif 000255