(57)【要約】  Ｑ個の特徴を有する入力ベクトルにより表されるデータの圧縮方法であって、ここで、Ｑは１より大きな整数であり、１）インデックス付きＱ特徴基準ベクトルからなる部分集合、及び所定の特徴について前記部分集合に関連付けられたしきい値を含んだベクトルコードブックを得る工程と；２）前記所定の特徴に対応する入力ベクトルの特徴の値を前記部分集合に関連付けられた前記しきい値と漸次比較することによって、前記部分集合から基準ベクトルの部分集合を特定する工程と；３）工程２）で特定した部分集合内で前記入力ベクトルに対して最小歪みを与える基準ベクトルを特定する工程と；を含む方法。
2008507718.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ個の基準ベクトルの集合からなるベクトルコードブックから開始し、データ圧縮の計算労力を低減するベクトルコードブックを生成する方法であって、ここで、各基準ベクトルはＱ個の特徴からなり、ＮとＱは１より大きい正の整数であり、該方法が、
ａ）前記Ｎ個の基準ベクトルの集合を、前記Ｎ個の基準ベクトルの集合の所定の特徴の値に関して昇順又は降順にソートする工程と；
ｂ）ソートした基準ベクトルの集合を部分集合に分割する工程と；
ｃ）前記部分集合の各々と前記所定の特徴についての夫々のしきい値とを関連付ける工程と；
を含むことを特徴とする方法。
【請求項２】
前記Ｎ個の基準ベクトルの集合を更に分割する工程を含み、前記更に分割する工程が、
ｄ）前記部分集合の各々の基準ベクトルを、前記Ｎ個の基準ベクトルの集合の更なる所定の特徴の値に関して昇順又は降順にソートする工程と；
ｅ）ソートした基準ベクトルの前記部分集合の各々を更なる部分集合に分割する工程と；
ｆ）前記更なる部分集合の各々と前記更なる所定の特徴についての夫々の更なるしきい値とを関連付ける工程と；
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記更に分割する工程を、該更なる分割の前の実行で得られた前記更なる部分集合を部分集合と毎回考えて、前記工程ｄ）及びｆ）を実行するため前記Ｎ個の基準ベクトルの集合の別の更なる所定の特徴について所定の回数繰り返すことを特徴とする請求項２に記載の方法。
【請求項４】
工程ｂ）で得た前記部分集合の少なくとも１つを、隣接部分集合の少なくとも１つの基準ベクトルを用いて拡張する工程ｇ）を更に含む、請求項１に記載の方法。
【請求項５】
工程ａ）でソートした前記集合において上部の部分集合の直ぐ下にある基準ベクトルに対応する少なくとも１つの基準ベクトルを前記部分集合の下部に加えることにより、工程ａ）でソートした前記集合の上部にある工程ｂ）で得た前記部分集合を拡張することによって前記工程ｇ）を実行する請求項４に記載の方法。
【請求項６】
工程ａ）でソートした前記集合において下部の部分集合の直ぐ上にある基準ベクトルに対応する少なくとも１つの基準ベクトルを前記部分集合の上部に加えることにより、工程ａ）でソートした前記集合の下部にある工程ｂ）で得た前記部分集合を拡張することによって前記工程ｇ）を実行する請求項４に記載の方法。
【請求項７】
工程ｂ）でソートした前記集合において中央の部分集合の直ぐ上及び直ぐ下にある基準ベクトルに対応する少なくとも１つの基準ベクトルを前記部分集合の上部及び下部に加えることにより、工程ｂ）で得た他の中央部分集合を拡張することによって前記工程ｇ）を実行する請求項４に記載の方法。
【請求項８】
工程ｂ）で得た前記部分集合の少なくとも１つを、隣接部分集合の少なくとも１つの基準ベクトルを用いて拡張する前記工程ｇ）を更に含み、工程ｇ）により拡張した前記部分集合について工程ｄ）及びｅ）を実行する請求項２に記載の方法。
【請求項９】
前記更に分割する工程が、工程ｅ）の後、工程ｅ）で得た前記更なる部分集合の少なくとも１つを、隣接する更なる部分集合の少なくとも１つの基準ベクトルを用いて拡張する工程ｈ）も含む請求項８に記載の方法。
【請求項１０】
ソートした対応する拡張部分集合において上部の更なる部分集合の直ぐ下にある基準ベクトルに対応する少なくとも１つの基準ベクトルを、前記更なる部分集合の下部に加えることにより、工程ｄ）でソートした対応する拡張部分集合の上部にある工程ｅ）で得た各更なる部分集合を拡張することによって前記工程ｈ）を実行する請求項９に記載の方法。
【請求項１１】
ソートした対応する拡張部分集合において下部の更なる部分集合の直ぐ上にある基準ベクトルに対応する少なくとも１つの基準ベクトルを、前記更なる部分集合の上部に加えることにより、工程ｄ）でソートした対応する拡張部分集合の下部にある工程ｅ）で得た各更なる部分集合を拡張することによって前記工程ｈ）を実行する請求項９に記載の方法。
【請求項１２】
工程ｄ）でソートした対応する拡張部分集合において工程ｅ）で得た他の中央の更なる部分集合の直ぐ上及び直ぐ下にある基準ベクトルに対応する少なくとも１つの基準ベクトルを、前記更なる部分集合の上部及び下部に加えることにより、前記中央の更なる部分集合を拡張することによって前記工程ｈ）を実行する請求項９に記載の方法。
【請求項１３】
前記更に分割する工程が、工程ｅ）の後に、工程ｅ）で得た前記更なる部分集合の少なくとも１つを隣接した更なる部分集合の少なくとも１つの基準ベクトルを用いて拡張する工程ｈ）も含み、前記更に分割する工程を、工程ｈ）の前の実行により前記拡張された更なる部分集合を部分集合と毎回考えて繰り返す、請求項３に記載の方法。
【請求項１４】
電子処理システム上でプログラムを実行する際に請求項１〜１３のいずれか一項に記載の方法の工程を実行するよう適合したプログラム命令からなるコンピュータプログラム。
【請求項１５】
Ｑ個の特徴を有する入力ベクトルにより表されるデータの圧縮方法であって、ここで、Ｑは１より大きな整数であり、
１）請求項１〜１３のいずれか一項に記載の方法で生成されるように、インデックス付きＱ特徴基準ベクトルからなる部分集合、及び所定の特徴について前記部分集合に関連付けられたしきい値を含んだベクトルコードブックを得る工程と；
２）前記所定の特徴に対応する入力ベクトルの特徴の値を前記部分集合に関連付けられた前記しきい値と漸次比較することによって、前記部分集合から基準ベクトルの部分集合を特定する工程と；
３）工程２）で特定した部分集合内で前記入力ベクトルに対して最小歪みを与える基準ベクトルを特定する工程と；
を含む方法。
【請求項１６】
前記入力ベクトルからの距離が最小の基準ベクトルを特定することによって工程３）を実行する請求項１５に記載の方法。
【請求項１７】
工程３）で特定した前記基準ベクトルのインデックスを前記入力ベクトルと関連付ける工程を更に含む請求項１５に記載の方法。
【請求項１８】
請求項２〜１３のいずれか一項に記載の方法により生成されるように、工程１）において、インデックス付きＱ特徴基準ベクトルからなる更なる部分集合、及び更なる所定の特徴について前記更なる部分集合に関連付けられた更なるしきい値をも、基準ベクトルの各部分集合に対して得る、請求項１５に記載の方法。
【請求項１９】
前記更なる所定の特徴に対応した前記入力ベクトルの更なる特徴の値を前記更なる部分集合に関連付けられた前記更なるしきい値と漸次比較することによって、工程２）で特定した前記部分集合に対応する前記更なる部分集合から更なる部分集合を特定する工程４）を更に含み、工程３）は工程４）で識別した前記更なる部分集合内で実行する請求項１８に記載の方法。
【請求項２０】
請求項４〜１３のいずれか一項に記載の方法の工程ｇ）により生成されるように、工程１）において拡張部分集合を得、工程２及び３）は該拡張部分集合に対して実行する請求項１５に記載の方法。
【請求項２１】
請求項９〜１３のいずれか一項に記載の方法の工程ｈ）により生成されるように、工程１）において拡張された更なる部分集合を得、工程４及び３）は該拡張された更なる部分集合に対して実行する請求項１９に記載の方法。
【請求項２２】
電子処理システム上でプログラムを実行する際に請求項１５〜２１のいずれか一項に記載の方法の工程を実行するよう適合したプログラム命令からなるコンピュータプログラム。
【請求項２３】
-  デジタル入力データを処理してＱ特徴ベクトルを得る特徴抽出装置（８０２）であって、ここでＱは１より大きな整数である特徴抽出装置（８０２）と；
-  ソートしたインデックス付きＱ特徴基準ベクトルからなる所定の部分集合と、前記所定の部分集合に関連付けられた所定のしきい値とからなる少なくとも１つのベクトルコードブックを記憶するためのメモリ装置（８０６）と；
-  前記特徴抽出装置（８０２）により得た各入力Ｑ特徴ベクトルについて、前記入力ベクトルの所定の特徴を前記所定のしきい値と比較することによって、前記所定の部分集合の一つを特定すると共に、前記特定した部分集合内で前記入力特徴ベクトルに関して歪みが最小の基準ベクトルを特定するためのデータ圧縮装置（８０４）と；
を備えたデータ圧縮用装置（８１０）。
【請求項２４】
前記データ圧縮装置（８０４）がまた、最小歪みを与える前記基準ベクトルのインデックスと前記入力Ｑ特徴ベクトルを関連付ける請求項２３に記載の装置。
【請求項２５】
前記データ圧縮装置（８０４）が請求項１５〜２１のいずれか一項に記載の方法の工程を実行する請求項２３に記載の装置。
【請求項２６】
前記メモリ装置（８０６）がソートしたインデックス付きＱ特徴基準ベクトルからなる前記部分集合、前記しきい値、及び請求項１〜１３のいずれか一項に記載の方法により生成した更なるしきい値を記憶する請求項２３に記載の装置。
【請求項２７】
前記メモリ装置（８０６）がソートしたインデックス付きＱ特徴基準ベクトルからなる更なる部分集合、前記しきい値、及び請求項１〜１３のいずれか一項に記載の方法により生成したすべての更なるしきい値を記憶する請求項２３に記載の装置。
【請求項２８】
請求項１〜１３のいずれか一項に記載の方法の工程を実行すると共に、前記部分集合、しきい値、及び前記メモリ装置（８０６）において前記方法により生成した更なるしきい値を記憶するコードブック処理装置を更に含む請求項２３に記載の装置。
【請求項２９】
請求項１〜１３のいずれか一項に記載の方法の工程を実行すると共に、更なる部分集合、しきい値、及び前記メモリ装置（８０６）において前記方法により生成したすべての更なるしきい値を記憶するコードブック処理装置を更に含む請求項２３に記載の装置。
【請求項３０】
入力音声信号をデジタル音声データに変換して前記特徴抽出装置（８０２）に与えるための変換装置（８０１）を更に備える請求項２３に記載の装置。
【請求項３１】
-  請求項２３〜３０のいずれか一項によるユーザー装置（８１０）と；
-  前記デジタル入力データを再構成するための認識装置（８２０）と；
-  前記ユーザー装置（８１０）と前記認識装置（８２０）との間でデータを伝送するためのデータ伝送路（８０５）と；
を備える分散型音声認識システム（８００）。
【請求項３２】
前記ユーザー装置（８１０）が、前記入力Ｑ特徴ベクトルと共に最小歪みを与える前記基準ベクトルのインデックスを前記認識装置（８２０）に伝送する請求項３１に記載の分散型音声認識システム（８００）。
【請求項３３】
請求項１〜１３のいずれか一項に記載の方法の工程を実行すると共に、前記部分集合、しきい値、及びメモリ装置（８０６）において前記方法により生成した更なるしきい値を記憶するコードブック処理装置を更に備える請求項３１に記載の分散型音声認識システム（８００）。
【請求項３４】
請求項１〜１３のいずれか一項に記載の方法の工程を実行すると共に、更なる部分集合、しきい値、及びメモリ装置（８０６）において前記方法により生成したすべての更なるしきい値を記憶するコードブック処理装置を更に備える請求項３１に記載の分散型音声認識システム（８００）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータ圧縮方法に関する。特に、本発明は分散型音声認識システムにおいて特徴ベクトルを圧縮する方法に関する。
【背景技術】
【０００２】
多くの用途で音声認識技術が利用されている。例として、下記のものが挙げられる。
-  銀行や証券会社の取引などのように「機密」情報の音声認識に基づいた双方向音声応答（ＩＶＲ）サービス。音声認識の特徴は将来の人物確認のため、又は手続上の要件を満たすために記憶しておいてもよい。
-  配備された音声認識システムから集められた音声データベースにおける発話の人物確認。このデータベースはシステム性能を向上させるべくモデルを再訓練し調整するのに使用できる。
-  機械と人間の認識が混合した用途（例えば人間補助式のディクテーション）。
【０００３】
音声認識の応用例はＵＳ５９４６６５３にも開示されている。ＵＳ５９４６６５３には、音声（による）命令を認識し、認識した音声命令に基づいてターゲットシステムに刺激を加えることによってターゲットシステムを制御する技術が記載されている。ユーザーが命令を言うことによりターゲットシステム又はアプリケーションを制御できることで、操作がさらに容易になり、ユーザーが感じるユーザーフレンドリな使いやすさが改善されるので、音声命令を用いてターゲットシステム及びソフトウエアアプリケーションを制御するのが望ましい。
【０００４】
代表的な音声認識システムでは、入力音声をマイクロフォンで受けて、サンプリングして元の入力音声のデジタル表現に変換する。このデジタル化した音声を（いわゆる「特徴抽出」又は「フロントエンド」処理に従って）処理して特徴ベクトルを生成する。この特徴ベクトルはよりコンパクトな形式の音声表現を与える。次に、この特徴ベクトルをパターン認識及び／又は再構成システム（一般に「バックエンド」という）に送信又は伝送し、入ってきた特徴ベクトルを音声テンプレートと比較して入力音声を再構成する。
【０００５】
一般にバックエンドにおける音声認識及び／又は再構成では、多量のメモリ及びＣＰＵサイクルを使用する検索アルゴリズムが必要とされる。
【０００６】
音声処理の当該技術においては、下記の３つの主要なアプローチが知られている。
-  サーバ側：オーディオ信号を当該装置によってデータ伝送路を介してサーバに送る。サーバはすべてのオーディオ信号処理を行い、認識処理の結果を該装置に送り返す。このアプローチでは、グラフィック表示がなく、また装置とサーバとの接続が不安定であるという限界がある。低分解能のアナログ-デジタル変換、トランスコーディング損失、伝送損失、及びあらゆる無線技術に固有のすべての誤差があるので、デジタル化したオーディオ信号の品質はしばしば音声認識の成功には不十分である。
-  クライアント側：音声処理をユーザーの装置において完全に行なう。このアプローチはオーディオ伝送路の問題を解決するが、クライアント装置が大きな処理能力とメモリ容量を有すると共に低消費量でなくてはならない。しかし、パーソナル・デジタル・アシスタント（ＰＤＡ）、携帯電話、及び他の組み込み装置などの無線ハンドヘルド装置には、一般に計算、メモリ、及び電池エネルギーに限界がある。よって、上述の資源の限界ゆえに、これらの従来装置において複雑な検索アルゴリズムを行なうのは難しい。
-  分散型音声認識（ＤＳＲ）：音声認識タスクを一部はクライアント装置で実行し一部はサーバで実行する。クライアント装置がユーザーのデジタル化された音声について特定の特徴を抽出し、これらのデジタル表現をサーバに送る。サーバは、抽出された情報をサーバに記憶された言語モデル及び語彙リストと比較することによってこの処理を完了させるので、無線装置のメモリの制約が小さい。このアプローチのその他の利点は、厳しいハードウエア要件を課すことなく様々なモバイル機器に音声インターフェースを加えることができること、サービス、コンテンツ及びコードを容易に更新できること、誤差に対する感度が低いことである（一般に、これらのシステムは音声認識精度に有害な影響を与えることなく最大で１０％までのデータパケット損失に対処できる）。
【０００７】
したがって、分散型音声認識（ＤＳＲ）システムでは、フロントエンド処理のみを無線ハンドヘルド装置において行い、計算及びメモリの集約されるバックエンド処理を遠隔のサーバにおいて行なう（例えば、ＥＰ１３９５９７８参照）。
【０００８】
また、当該技術においては通信チャネルの帯域幅を節約するため、ＤＳＲシステムのフロントエンド処理において抽出した特徴ベクトルを、バックエンド処理のために遠隔のサーバに伝送する前に圧縮することが提案されてきた。当該技術において、この圧縮を一般に「ベクトル量子化」又は「ベクトル圧縮」という。
【０００９】
そうゆうわけで、欧州通信規格協会（ＥＴＳＩ）がＤＲＳ特徴抽出及び圧縮アルゴリズムの規格（「Ａｕｒｏｒａ」）（ＥＴＳＩ  ＥＳ  ２０２．０５０、ＥＳ  ２０２  ２１２、ＥＳ  ２０２  １０８及びＥＳ  ２０２  ２１１）を公表した。
【００１０】
Ａｕｒｏｒａ  ＥＴＳＩ規格の特徴抽出アルゴリズムに従い、デジタル化された入力音声をフィルタリングし、ハミング窓を用いて各音声フレームをウインドウ生成し、高速フーリエ変換（ＦＦＴ）を用いて周波数領域に変換する。次に、メル周波数領域変換とそれに続く処理工程を実行して、音声データの各時間フレームに対して１４個の特徴（すなわち、１２個の静的メルケプストラム係数Ｃ（１）〜Ｃ（１２）と零ケプストラム係数Ｃ（０）と対数エネルギー項ｌｎＥ）からなるベクトルを得る（ＥＰ１３９５９７８も参照）。
【００１１】
Ａｕｒｏｒａ  ＥＴＳＩ規格の圧縮アルゴリズムによると、次に、この１４個の特徴をペアでグループ化して、音声データの各時間フレームに対して７個の二特徴ベクトルを得る。次に、７個の夫々の所定のコードブックを用いて、これらの二特徴ベクトルを圧縮する。
【００１２】
コードブックは、特徴ベクトルにより表された元の情報を表すように選択された所定のインデックス付き基準ベクトルのセットである。Ａｕｒｏｒａ  ＥＴＳＩ規格により規定されているように、コードブックにおける基準ベクトルの分布は一様でなくてよい。
【００１３】
圧縮又は量子化は、入力ベクトルを、最小歪みを与える基準ベクトルのインデックスに置き換えることによって行なう。
【００１４】
確かに、インデックスは０〜Ｎ−１の正の整数値であるから（ここでＮはコードブックにおける基準ベクトルの数）、Ｑ個の特徴（ここでＱ≧２）からなる入力特徴ベクトルよりもコンパクトな情報によって表すことができる。
【００１５】
ＥＴＳＩアルゴリズムによると、入力ベクトルと夫々のコードブックの各基準ベクトルとの間の重み付きユークリッド距離を求めることによって最小歪みを見つける。いったん最も近い基準ベクトルを見つけたら、その基準ベクトルのインデックスを用いてその入力ベクトルを表す。
【００１６】
二特徴ベクトルのユークリッド距離で計算した最小距離の値Ｄｍｉｎは次式で表される。
【数１】
2008507718.tif 000003
ここで、Ｎはコードブックにおけるベクトルの数であり、（ＸＡ，ＸＢ）は入力ベクトルであり、Ｃｉ＝（Ｃｉ，Ａ，Ｃｉ，Ｂ）はコードブックのｉ番目ベクトルである。
【００１７】
上記の式によると、従来のＥＴＳＩ圧縮アルゴリズム（網羅的な計算）ではＮ回の距離計算が必要であり、これは、２Ｎ回の平方と３Ｎ回の加算の値を求めることに等しい（平方根の計算は最小値Ｄｍｉｎの探索結果に影響しないので、省略できる）。これらの演算には、Ｎに比例した高いプロセッサ能力が必要である。
【００１８】
例えば、ＥＰ０４９６５４１、ＵＳ５９４６６５３、ＵＳ６３８９３８９に記載されているように、当該技術において圧縮アルゴリズムを改善する試みが行われている。
【００１９】
しかし、これらの文献に記載の技術では、入力ベクトルから最小距離を有するコードブックのベクトルを見つけるのに要する計算労力を効率的に削減できない。
【００２０】
ＵＳ４９５８２２５には別のベクトル量子化技術（この場合はビデオデータ圧縮）が提案されている。特に、この特許は入力ベクトルに最も近接して一致するコードブックベクトルのセットの１つを特定するためにベクトル量子化を用いてビデオデータを圧縮する方法を開示している。一態様によると、この方法は以下の工程を含む。１）入力ベクトルＩのノルムを計算する；２）入力ベクトルのノルムに最も近いノルムを有する基準コードブックベクトルＡｊを特定する；３）入力ベクトルＩと基準コードブックベクトルＡｊとの間の距離ｈＩ，Ｊを計算する；４）入力ベクトルＩの周りの限定体積のベクトル空間からのコードブックベクトル（例えば、｜Ｉ｜−ｈＩ，Ｊから｜Ｉ｜＋ｈＩ，Ｊまでの範囲のノルムを有するベクトル）から成るコードブックベクトルの部分集合Ｓを特定する；５）入力ベクトルまでの距離が最小であるコードブックベクトルについて部分集合Ｓを探し；６）入力ベクトルまでの距離が最小のコードブックベクトルを選択する。工程４）における部分集合Ｓの特定により、工程５）において最小距離計算のために求めなければならないベクトルの数が削減される。
【００２１】
しかし、出願人は、この方法は入力ベクトルと基準ベクトルとの間で計算しなければならない距離計算の回数を、部分集合Ｓに含まれる基準ベクトルの数まで減らすが、依然として工程１〜６において多数の計算と命令を実行する必要があることに注目する。また、すべての基準コードブックベクトルのノルムだけが予めオフラインで計算してメモリに記憶でき、後で工程２）を実行しなければならないときに使用する。したがって、この方法で必要とされるオンラインでの計算労力は依然として大きい。
【特許文献１】ＵＳ５９４６６５３
【特許文献２】ＥＰ１３９５９７８
【特許文献３】ＥＰ０４９６５４１
【特許文献４】ＵＳ６３８９３８９
【特許文献５】ＵＳ４９５８２２５
【発明の開示】
【発明が解決しようとする課題】
【００２２】
よって、出願人は特徴ベクトルの圧縮に必要な計算労力を低減するという技術的な問題に取り組んだ。
【００２３】
特に、出願人はＤＳＲシステムにおける特徴ベクトルの圧縮に要するオンライン計算の労力を低減するという技術的な問題に取り組んだ。
【課題を解決するための手段】
【００２４】
出願人は、コードブックを処理してコードブックを所定の領域に分割すること（該領域の各々はコードブックの基準ベクトルの部分集合からなる）；及び、生成したアクセス情報を用いてその入力ベクトルをより良く表す領域を特定し、特定した領域（コードブックの数より少ない幾つかの基準ベクトルを含む）内でのみ最小歪みを与える基準ベクトルを探すことによって（新しい入力ベクトルを受信する度にオンラインで実行しなければならない）ベクトル圧縮を実行できるように、所定の領域への所定のアクセス情報を生成すること；により上記問題を解決できることを見いだした。よって、特徴ベクトルの圧縮に必要なオンラインでの計算労力が低減される。また、所与のコードブックについて１回だけコードブック処理をオフラインで実行できるので、オンライン処理に対して負担はそれほどでもない。
【００２５】
したがって、本発明の第１の態様は、Ｎ個の基準ベクトルの集合からなるベクトルコードブックから開始し、データ圧縮の計算労力を低減するベクトルコードブックを生成する方法であって、ここで、各基準ベクトルはＱ個の特徴からなり、ＮとＱは１より大きい正の整数であり、該方法が、
ａ）前記Ｎ個の基準ベクトルの集合を、前記Ｎ個の基準ベクトルの集合の所定の特徴の値に関して昇順又は降順にソートする工程と；
ｂ）ソートした基準ベクトルの集合を部分集合に分割する工程と；
ｃ）前記部分集合の各々と前記所定の特徴についての夫々のしきい値とを関連付ける工程と；
を含むことを特徴とする方法である。
【００２６】
この明細書及び特許請求の範囲において、「ベクトル」なる用語はスカラーの順序集合を示すのに用いられる。ベクトルの次元は順序集合のスカラー要素の数である。例えば、２次元ベクトルは｛ａｌ，ａ２｝として示すことができ、ここで、ａ１はベクトルの最初のスカラー要素であり、ａ２は２番目のスカラー要素である。
【００２７】
また、「特徴」なる用語はスカラーを示すのに用いられる。例えば、音声認識システムの場合、「特徴」なる用語は特徴抽出アルゴリズムによって入力音声から抽出された係数を示すのに用いられる。
【００２８】
従属請求項は本発明の特定の態様に関する。
有利には、この方法は更に、前記Ｎ個の基準ベクトルの集合を更に分割する工程を含み、前記更に分割する工程が、
ｄ）前記部分集合の各々の基準ベクトルを、前記Ｎ個の基準ベクトルの集合の更なる所定の特徴の値に関して昇順又は降順にソートする工程と；
ｅ）ソートした基準ベクトルの前記部分集合の各々を更なる部分集合に分割する工程と；
ｆ）前記更なる部分集合の各々と前記更なる所定の特徴についての夫々の更なるしきい値とを関連付ける工程と；
を含む。
【００２９】
一態様によると、前記更に分割する工程を、該更なる分割の前の実行で得られた前記更なる部分集合を部分集合と毎回考えて、前記工程ｄ）及びｆ）を実行するため前記Ｎ個の基準ベクトルの集合の別の更なる所定の特徴について所定の回数繰り返す。
【００３０】
更に分割する上記工程は、上記記憶工程でまだ考慮していない基準ベクトル集合の残りの特徴のどれかについて繰り返すことができる。好ましくは、基準ベクトル集合の残りの特徴のすべてについて繰り返す。
【００３１】
工程ｃ）では、有利には、そのしきい値は、Ｎ個の基準ベクトルの集合の所定の（prefixed）特徴の値に依存して選択する。
【００３２】
工程ｃ）では、有利には、各しきい値は、夫々の部分集合に含まれる基準ベクトルの所定の特徴の値に依存して選択する。
【００３３】
工程ｃ）では、各しきい値は、夫々の部分集合の最後の基準ベクトルの所定の特徴の値から次の部分集合の最初の基準ベクトルの所定の特徴の値までの間に含まれる値に設定できる（もし存在すれば）。好ましくは、各しきい値は、夫々の部分集合の最後の基準ベクトルの所定の特徴の値に等しい値に設定する。
【００３４】
工程ｆ）では、有利には、上記更なるしきい値は、Ｎ個の基準ベクトル集合の上記更なる所定の特徴の値に依存して選択する。
【００３５】
工程ｆ）では、有利には、更なるしきい値の各々は、夫々の更なる部分集合に含まれる基準ベクトルの上記更なる所定の特徴の値に依存して選択する。
【００３６】
工程ｆ）では、更なるしきい値の各々は、夫々の更なる部分集合の最後の基準ベクトルの上記更なる所定の特徴の値から次の更なる部分集合の最初の基準ベクトルの上記更なる所定の特徴の値までの間に含まれる値に設定できる（もし存在すれば）。好ましくは、工程ｆ）の更なるしきい値の各々は、夫々の更なる部分集合の最後の基準ベクトルの上記更なる所定の特徴の値に等しい値に設定する。
【００３７】
工程ｄ）は、工程ａ）で用いられる順序とは独立に、昇順又は降順にて実行できる。
【００３８】
工程ｂ）では、記憶された集合をＮｆｉｒｓｔ個の部分集合に分割する。ここで、Ｎｆｉｒｓｔは２≦Ｎｆｉｒｓｔ≦Ｎが成り立つ正の整数である。
【００３９】
有利には、工程ｂ）で得られた部分集合は実質的に同数の基準ベクトルを含む。すなわち、ほとんどすべての部分集合について、部分集合の基準ベクトルの数はＮ／Ｎｆｉｒｓｔに等しい。
【００４０】
「部分集合は実質的に同数の基準ベクトルを含む」なる上記表現は、除算Ｎ／Ｎｆｉｒｓｔの剰余がゼロとは異なるとき部分集合の基準ベクトルの数がすべての部分集合についてはＮ／Ｎｆｉｒｓｔに等しくできない場合を含意することに留意されたい。
【００４１】
好ましくは、工程ｅ）では、各部分集合を更なる部分集合の数Ｎｓｅｃｏｎｄ（同数）で分割する。ここで、Ｎｓｅｃｏｎｄは１より大きい正の整数である。また、好ましくは、Ｎｓｅｃｏｎｄは、基準ベクトルの数が最小である部分集合の基準ベクトルの数以下である。
【００４２】
有利には、工程ｅ）では、各部分集合を、実質的に同数の基準ベクトルを含んだ更なる部分集合に分割する。
【００４３】
後で詳細に説明するように、実質的に同数の基準ベクトルを含んだ更なる部分集合により、入力ベクトルが含まれるコードブックの領域とは独立に、受信したすべての入力ベクトルに対して実質的に同じ計算労力とすることができる。
【００４４】
有利には、この方法は更に、工程ｂ）で得た前記部分集合の少なくとも１つを、隣接部分集合の少なくとも１つの基準ベクトルを用いて拡張する工程ｇ）を更に含む。
【００４５】
有利には、工程ａ）でソートした前記集合において上部の部分集合の直ぐ下にある基準ベクトルに対応する少なくとも１つの基準ベクトルを前記部分集合の下部に加えることにより、工程ａ）でソートした前記集合の上部にある工程ｂ）で得た前記部分集合を拡張することによって前記工程ｇ）を実行する。
【００４６】
有利には、工程ａ）でソートした前記集合において下部の部分集合の直ぐ上にある基準ベクトルに対応する少なくとも１つの基準ベクトルを前記部分集合の上部に加えることにより、工程ａ）でソートした前記集合の下部にある工程ｂ）で得た前記部分集合を拡張することによって前記工程ｇ）を実行する。
【００４７】
有利には、工程ｂ）でソートした前記集合において中央の部分集合の直ぐ上及び直ぐ下にある基準ベクトルに対応する少なくとも１つの基準ベクトルを前記部分集合の上部及び下部に加えることにより、工程ｂ）で得た他の中央部分集合を拡張することによって前記工程ｇ）を実行する。
【００４８】
後で詳細に説明するように、工程ｇ）では隣接する部分集合間の重なりを生成し、これにより、本発明の方法で生成されたコードブックを用いるベクトル圧縮方法において、部分集合で表されるコードブックの隣接領域の境界近くに位置する入力ベクトルについての最小歪み計算での誤差を低減できる。
【００４９】
有利には、工程ｇ）を実行するとき、工程ｄ）及びｅ）を拡張された部分集合に実行する。
【００５０】
有利には、工程ｇ）において、部分集合をその上部及び／又は下部にて同数の基準ベクトルだけ拡張する。
【００５１】
有利には、前記更に分割する工程が、工程ｅ）の後、工程ｅ）で得た前記更なる部分集合の少なくとも１つを、隣接する更なる部分集合の少なくとも１つの基準ベクトルを用いて拡張する工程ｈ）も含む。
【００５２】
有利には、ソートした対応する拡張部分集合において上部の更なる部分集合の直ぐ下にある基準ベクトルに対応する少なくとも１つの基準ベクトルを、前記更なる部分集合の下部に加えることにより、工程ｄ）でソートした対応する拡張部分集合の上部にある工程ｅ）で得た各更なる部分集合を拡張することによって前記工程ｈ）を実行する。
【００５３】
有利には、ソートした対応する拡張部分集合において下部の更なる部分集合の直ぐ上にある基準ベクトルに対応する少なくとも１つの基準ベクトルを、前記更なる部分集合の上部に加えることにより、工程ｄ）でソートした対応する拡張部分集合の下部にある工程ｅ）で得た各更なる部分集合を拡張することによって前記工程ｈ）を実行する。
【００５４】
有利には、工程ｄ）でソートした対応する拡張部分集合において工程ｅ）で得た他の中央の更なる部分集合の直ぐ上及び直ぐ下にある基準ベクトルに対応する少なくとも１つの基準ベクトルを、前記更なる部分集合の上部及び下部に加えることにより、前記中央の更なる部分集合を拡張することによって前記工程ｈ）を実行する。
【００５５】
有利には、工程ｈ）を実行するとき、前記更に分割する工程を、工程ｈ）の前の実行により拡張された前記更なる部分集合を部分集合と毎回考えて繰り返す。
【００５６】
後で詳しく説明するように、工程ｈ）では隣接する更なる部分集合間の重なりを生成し、それにより、本発明の方法により生成されたコードブックを用いるベクトル圧縮方法において、上記更なる部分集合により表されるコードブックの隣接領域の境界近くに位置する入力ベクトルについての最小歪み計算における誤差を低減できる。
【００５７】
有利には、工程ｈ）において、上記更なる部分集合を上部及び／又は下部にて同数の行だけ拡張する。
【００５８】
第２の態様では、本発明は、ベクトルコードブックを生成してデータ圧縮の計算労力を低減する電子処理システムに関するものであり、本発明の第１の態様による方法の工程を実行する手段を備える。
【００５９】
この電子処理システムは、例えばパーソナルコンピュータ、コンピュータネットワーク、又は無線ハンドヘルド装置としての組み込み装置（例えばＰＤＡや携帯電話）とし得る。
【００６０】
第３の態様では、本発明は、電子処理システム上でプログラムを実行する際に本発明の第１の態様による方法の工程を実行するよう適合したプログラム命令からなるコンピュータプログラムに関する。
【００６１】
有利には、このコンピュータプログラムはコンピュータ読出し可能媒体に組み込まれる。
【００６２】
例えば、このコンピュータ読出し可能媒体は読み出し専用メモリ又は磁気記録手段である。読み出し専用メモリの代表的な例は、ＣＤ-ＲＯＭ又は半導体ＲＯＭである。磁気記録手段の代表的な例は、フロッピーディスク又はハードディスクである。
【００６３】
一態様によると、このコンピュータプログラムは、例えばインターネットなどのコンピュータネットワーク内で転送される際にはキャリヤ信号にて伝えられる。
【００６４】
一般に、このキャリヤ信号は電気信号又は光信号である。例えば、モデムにより生成された電波信号又は電気信号とし得る。このようなキャリヤ信号は、例えば電気ケーブルや光ケーブル、電波、又は他の従来の伝送手段によって送ることができる。
【００６５】
第４の態様では、本発明は、Ｑ個の特徴を有する入力ベクトルにより表されるデータの圧縮方法であって、ここで、Ｑは１より大きな整数であり、
１）本発明の第１の態様による方法で生成されるように、インデックス付きＱ特徴基準ベクトルからなる部分集合、及び所定の特徴について前記部分集合に関連付けられたしきい値を含んだベクトルコードブックを得る工程と；
２）前記所定の特徴に対応する入力ベクトルの特徴の値を前記部分集合に関連付けられた前記しきい値と漸次比較することによって、前記部分集合から基準ベクトルの部分集合を特定する工程と；
３）工程２）で特定した部分集合内で前記入力ベクトルに対して最小歪みを与える基準ベクトルを特定する工程と；
を含む方法に関するものである。
【００６６】
本発明によると、ベクトル圧縮は、簡単な比較工程を行い（工程２）、特定部分集合（コードブックより少ない数の基準ベクトルを含む）内でのみ最小歪みを与える基準ベクトルを特定することによって実行できる。したがって、ベクトル圧縮に要する計算労力は低減される。
【００６７】
また、本発明の第１の態様によるコードブックの生成は、所与のコードブックに対して１回だけオフラインで実行できる。したがって、入力ベクトルを受信する度にオンラインで実行しなければならない本圧縮方法に対して負荷をかけ過ぎない。
【００６８】
一般に、この歪みは、歪みを表すスカラーを得るように２個以上の入力ベクトルを処理する関数によって計算する。一般に、この関数はユークリッド距離を導入する。しかし、別の任意の種類の距離を導入することができる。
【００６９】
有利には、前記入力ベクトルからの距離が最小の基準ベクトルを特定することによって工程３）を実行する。一般に、これは、入力ベクトルと工程２）で特定した部分集合に含まれる各基準ベクトルとの間の距離を計算することによって実行する。
【００７０】
有利には、この圧縮方法は更に、工程３）で特定した前記基準ベクトルのインデックスを前記入力ベクトルと関連付ける工程を更に含む。
【００７１】
有利には、本発明の第１の態様による方法により生成されるように、工程１）において、インデックス付きＱ特徴基準ベクトルからなる更なる部分集合、及び更なる所定の特徴について前記更なる部分集合に関連付けられた更なるしきい値をも、基準ベクトルの各部分集合に対して得る。
【００７２】
有利には、この圧縮方法は更に、前記更なる所定の特徴に対応した前記入力ベクトルの更なる特徴の値を前記更なる部分集合に関連付けられた前記更なるしきい値と漸次比較することによって、工程２）で特定した前記部分集合に対応する前記更なる部分集合から更なる部分集合を特定する工程４）を更に含み、工程３）は工程４）で識別した前記更なる部分集合内で実行する。
【００７３】
有利には、本発明の第１の態様による方法の工程ｇ）により生成されるように、工程１）において拡張部分集合を得、工程２及び３）は該拡張部分集合に対して実行する。
【００７４】
有利には、本発明の第１の態様による方法の工程ｈ）により生成されるように、工程１）において拡張された更なる部分集合を得、工程４及び３）は該拡張された更なる部分集合に対して実行する。
【００７５】
第５の態様では、本発明は本発明の第４の態様による方法の工程を実行する手段を備えたデータ圧縮用の電子処理システムに関する。
【００７６】
この電子処理システムは、例えば、パーソナルコンピュータ、コンピュータネットワーク、無線ハンドヘルド装置としての組み込み装置（例えば、ＰＤＡや携帯電話）、又は特にＤＳＲシステムのユーザー装置とし得る。
【００７７】
別の態様では、本発明は、電子処理システム上でプログラムを実行する際に本発明の第４の態様による方法の工程を実行するよう適合したプログラム命令からなるコンピュータプログラムに関する。
【００７８】
コンピュータプログラムの特徴に関しては、本発明の第３の態様について記載した事項を参照されたい。
【００７９】
別の態様では、本発明は、
-  デジタル入力データを処理してＱ特徴ベクトルを得る特徴抽出装置であって、ここでＱは１より大きな整数である特徴抽出装置と；
-  ソートしたインデックス付きＱ特徴基準ベクトルからなる所定の部分集合と、前記部分集合に関連付けられた所定のしきい値とからなる少なくとも１つのベクトルコードブックを記憶するためのメモリ装置と；
-  前記特徴抽出装置により得た各入力Ｑ特徴ベクトルについて、前記入力ベクトルの所定の特徴を前記所定のしきい値と比較することによって、記憶された部分集合の一つを特定すると共に、前記特定した部分集合内で前記入力特徴ベクトルに関して歪みが最小の基準ベクトルを特定するためのデータ圧縮装置と；
を備えたデータ圧縮用装置に関するものである。
【００８０】
有利には、前記データ圧縮装置がまた、最小歪みを与える前記基準ベクトルのインデックスと前記入力Ｑ特徴ベクトルを関連付ける。
【００８１】
有利には、前記データ圧縮装置が本発明の第４の態様による方法の工程を実行する。
【００８２】
有利には、前記メモリ装置がソートしたインデックス付きＱ特徴基準ベクトルからなる前記（拡張された）部分集合又は（拡張された）更なる部分集合、前記しきい値、及び本発明の第１の態様による方法により生成した更なるしきい値を記憶する。
【００８３】
有利には、この装置は更に、本発明の第１の態様による方法の工程を実行すると共に、前記（拡張された）部分集合又は（拡張された）更なる部分集合、しきい値、及び前記メモリ装置において前記方法により生成した更なるしきい値を記憶するコードブック処理装置を更に備える。
【００８４】
有利には、この装置は更に、入力音声信号をデジタル音声データに変換して前記特徴抽出装置に与えるための変換装置を更に備える。
【００８５】
別の態様では、本発明は
-  本発明の前の態様によるユーザー装置と；
-  前記デジタル入力データを再構成するための認識装置と；
-  前記ユーザー装置と前記認識装置との間でデータを伝送するためのデータ伝送路と；
を備える分散型音声認識システムに関するものである。
【００８６】
有利には、前記ユーザー装置が、前記入力Ｑ特徴ベクトルと共に最小歪みを与える前記基準ベクトルのインデックスを前記認識装置に伝送する。
【００８７】
有利には、分散型音声認識システムが、本発明の第１の態様による方法の工程を実行すると共に、（拡張された）部分集合又は（拡張された）更なる部分集合、しきい値、及びメモリ装置において前記方法により生成したすべての更なるしきい値を記憶するコードブック処理装置を更に備える。
【００８８】
以下、添付図面に非限定的な例として示された態様について本発明の特徴と利点を説明する。
【発明を実施するための最良の形態】
【００８９】
図９は本発明によるデータ圧縮方法のフローチャートを表す。
この方法は、例えば音声認識システムのクライアント側で使用できる。
この方法はブロック９００にて開始し、セットアップ段階とランタイム段階とを含む。
【００９０】
このセットアップ段階はブロック９０１で表されるコードブック生成工程（又は領域フォーマッティング工程）を含み、所定のコードブックを所定の領域に分割する。
【００９１】
ランタイム段階は、各入力特徴ベクトルに対して実行し、領域選択工程と最小歪み探索工程（又は最小歪み探索・マッピング工程）とを含み、それぞれブロック９０２とブロック９０３により表される。領域選択工程では、最小歪みを入力ベクトルに与えるコードブックベクトルを含んだコードブックの領域を特定する。最小歪み探索工程では、最小歪みを入力ベクトルに与えるコードブックベクトルを、特定した領域内で見つけ、特定したコードブックベクトルのインデックスを用いて入力ベクトルをマッピングする。
【００９２】
ブロック９０４では、新しい特徴ベクトルを処理しなければならないか否かを調べる。否であれば、プロセスが終了する（ブロック９０５）。
以下、本発明の方法をさらに詳しく説明する。
【００９３】
データ圧縮の計算労力を低減する本発明のコードブック生成方法によると、コードブックを所定の領域に分割して、その各々が基準ベクトルの部分集合からなるようにすると共に、この所定の領域へのアクセス情報を生成するように、各基準ベクトルがＱ個の順序付けられた特徴を有するＮ個の基準ベクトルの集合からなるコードブックを処理する。
【００９４】
１つのコードブックはＮ行Ｑ列からなるテーブルにより表すことができ、その各列はコードブックのベクトルを表す。
この表現に従うと、Ｑ列とテーブル行の部分集合とからなるサブテーブルが、コードブック基準ベクトルの対応する部分集合から成るコードブック空間の領域を表す。
【００９５】
このテーブルは、所定のサブテーブルとサブテーブルへのアクセス情報とを得るようにテーブルの行の分割及びソートの反復操作を行なうことによって処理する。
【００９６】
図１のフローチャートは上記コードブック生成工程の好ましい態様を概略的に示す。この生成工程は、ここで考慮している例では、Ｎ個の二特徴ベクトル（すなわちＱ＝２）：｛Ｃ１，Ａ；Ｃ１，Ｂ｝、｛Ｃ２，Ａ；Ｃ２，Ｂ｝…｛ＣＮ，Ａ；ＣＮ，Ｂ｝を有する非一様コードブックについて実行し、ここで、１、２…Ｎは基準ベクトルのインデックスを示し、Ａ及びＢはそれぞれ該ベクトルの第１及び第２の特徴を示す。
【００９７】
図２は６４個の基準ベクトル（すなわち、Ｑ＝２及びＮ＝６４）からなる非一様二次元コードブックの例を示し、ＤＳＲ圧縮アルゴリズムのＥＴＳＩ「Ａｕｒｏｒａ」規格に規定されている。
【００９８】
図１のフローチャートによると、この手順はブロック１００にて開始し、ブロック１０１にて非一様コードブックをテーブルに変換する。
【００９９】
図３はブロック１０１で形成したテーブルの例を示し、Ｎ個の二特徴ベクトル｛Ｃ１，Ａ；Ｃ１，Ｂ｝、｛Ｃ２，Ａ；Ｃ２，Ｂ｝…｛ＣＮ，Ａ；ＣＮ，Ｂ｝からなる。
【０１００】
ブロック１０２では、この２列の一方を選択し、テーブルのベクトルのすべてを、選択した列に含まれる特徴値について昇順（又は降順）に行ごとにソートし、ベクトルの特徴すべての間の対応を維持する。
【０１０１】
ブロック１０３では、ソートして得られたＮ行のテーブルを、好ましくは複数の行（最も考えられるのは互いに等しい、すなわち、最も考えられるのはＮ／Ｎｆｉｒｓｔに等しい）を有するＮｆｉｒｓｔ個の二列サブテーブルに分割する。
【０１０２】
もちろん、このＮｆｉｒｓｔ個のサブテーブルは、除算Ｎ／Ｎｆｉｒｓｔの剰余がゼロの場合はＮ／Ｎｆｉｒｓｔに等しい同じ行数を有することができる。
【０１０３】
簡単のため、以下の説明では上記剰余をゼロと仮定する。
ブロック１０４では、ブロック１０３で得たＮｆｉｒｓｔ個サブテーブルを特定するＮｆｉｒｓｔ個の第１しきい値を定める。
【０１０４】
このＮｆｉｒｓｔ個の第１しきい値は、例えば、対応するサブテーブルの選択された列に含まれる最後の値と、次のサブテーブルの選択された列に含まれる最初の値との間に含まれる値に設定できる（もし存在すれば）。好ましくは、Ｎｆｉｒｓｔ個の第１しきい値は、対応するサブテーブルの選択された列に含まれる最後の値に等しくなるように設定する。
【０１０５】
ブロック１０５では、好ましくは、各サブテーブルを、その上部及び／又は下部に、記憶されたテーブル中で該サブテーブルに先行及び後続するＭｆｉｒｓｔ行（もしあれば）に対応するＭｆｉｒｓｔ行を加えることによって拡張する。ここで、Ｍｆｉｒｓｔ≦Ｎ／Ｎｆｉｒｓｔである。このようにして、Ｐｆｉｒｓｔ，ｉ行からなる拡張サブテーブルを得る。ここで、Ｐｆｉｒｓｔ，ｉは以下の値をとることを仮定できる。
テーブルの上部及び下部の拡張サブテーブルについて：Ｐｆｉｒｓｔ，１＝（Ｎ／Ｎｆｉｒｓｔ）＋Ｍｆｉｒｓｔ
テーブルの他の中央拡張サブテーブルすべてについて：Ｐｆｉｒｓｔ，２＝（Ｎ／Ｎｆｉｒｓｔ）＋２Ｍｆｉｒｓｔ
【０１０６】
ブロック１０６では、前にブロック１０２で用いた順とは独立に、ベクトルの特徴すべての間の対応を維持しつつ、各拡張サブテーブルのベクトルをもう一方の列に含まれる特徴値について昇順（又は降順）でソートする。
【０１０７】
ブロック１０７では、Ｐｆｉｒｓｔ，ｉ行を有するソートした各拡張サブテーブルを、Ｎｓｅｃｏｎｄ個の更なる二列サブテーブルに分割し、その結果、該更なるサブテーブルの行数はＰｆｉｒｓｔ，ｉ／Ｎｓｅｃｏｎｄとなる。それらは低次元なので、上部及び下部拡張サブテーブルは、もう一方の拡張サブテーブルよりも少ない行数を有することになる。
【０１０８】
もちろん、各拡張サブテーブルから得たこれらＮｓｅｃｏｎｄ個の更なるサブテーブルは、除算Ｐｆｉｒｓｔ，ｉ／Ｎｓｅｃｏｎｄの剰余がゼロの場合、Ｐｆｉｒｓｔ，ｉ／Ｎｓｅｃｏｎｄに等しい同じ行数を有し得る。
【０１０９】
簡単のため、以下の説明では上記剰余をゼロと仮定する。
ブロック１０８では、Ｎｆｉｒｓｔ個の拡張サブテーブルの各々に対してブロック１０７で得たＮｓｅｃｏｎｄ個の更なるサブテーブルを特定するＮｓｅｃｏｎｄ個の第２しきい値を定める。
【０１１０】
したがって、Ｎｆｉｒｓｔ・（Ｎｓｅｃｏｎｄ）個のしきい値の総計を得る。
Ｎｓｅｃｏｎｄ個の第２しきい値は、例えば、第１しきい値を定めるために上記説明したのと同じ基準で定義できる。
【０１１１】
ブロック１０９では、好ましくは、次元Ｐｆｉｒｓｔ，ｉ／Ｎｓｅｃｏｎｄの更なるの各サブテーブルを、その上部及び／又は下部に、ソートした対応する拡張サブテーブル中で該更なるサブテーブルに先行及び後続するＭｓｅｃｏｎｄ行（もしあれば）に対応するＭｓｅｃｏｎｄ行を加えることによって拡張する。ここで、Ｍｓｅｃｏｎｄ≦（Ｐｆｉｒｓｔ，ｉ／Ｎｓｅｃｏｎｄ）である。このようにして、Ｐｓｅｃｏｎｄ，ｊ行からなる拡張された更なるサブテーブルを得る。ここで、Ｐｓｅｃｏｎｄ，ｊは以下の別個の値をとることを仮定できる。
上部及び下部拡張サブテーブルの更なる上部及び下部拡張サブテーブルについて：
Ｐｓｅｃｏｎｄ，１＝（Ｐｆｉｒｓｔ，１／Ｎｓｅｃｏｎｄ）＋Ｍｓｅｃｏｎｄ
上部及び下部拡張サブテーブルの一方の更なる中央拡張サブテーブルすべてについて：
Ｐｓｅｃｏｎｄ，２＝（Ｐｆｉｒｓｔ，１／Ｎｓｅｃｏｎｄ）＋２・Ｍｓｅｃｏｎｄ
一方の中央拡張サブテーブルすべての更なる上部及び下部拡張サブテーブルについて：
Ｐｓｅｃｏｎｄ，３＝（Ｐｆｉｒｓｔ，２／Ｎｓｅｃｏｎｄ）＋Ｍｓｅｃｏｎｄ
一方の中央拡張サブテーブルすべての一方の更なる中央拡張サブテーブルすべてについて：
Ｐｓｅｃｏｎｄ，４＝（Ｐｆｉｒｓｔ，２／Ｎｓｅｃｏｎｄ）＋２・Ｍｓｅｃｏｎｄ
【０１１２】
ブロック１１０では、生成した拡張サブテーブルと第１及び第２しきい値をメモリに記憶し、後でベクトル圧縮方法において使用できるようにする。
【０１１３】
留意すべきは、ブロック１０５及び１０９で行なう拡張工程は本発明のコードブック生成方法の（必要ではないが）好ましい工程であり、サブテーブルと更なるサブテーブルとの間の重なりを与えることにより、上述の（更なる）サブテーブルにより表されるコードブックの隣接領域の境界近くに位置する入力ベクトルに対しても、ベクトル圧縮における誤差を大きく低減できる。
【０１１４】
いったん本発明の方法により所定のコードブックを生成したなら、新しい入力ベクトルを受信するたびに、その入力ベクトルを上記所定のコードブック内で最小歪みを与える基準ベクトルのインデックスと置き換えることによってベクトル圧縮を実行できる。
【０１１５】
特に、本発明によるベクトル圧縮方法は、領域選択及び最小歪み探索からなる上記２つの手順を含む。
【０１１６】
図４のフローチャートは、図１について説明した事項に基づいて処理した二特徴入力ベクトル｛ＸＡ，ＸＢ｝及び二次元コードブックについての領域選択手順の好ましい態様を概略的に示す。
【０１１７】
ブロック４０１にて手順が開始し、Ｎｆｉｒｓｔ個の第１しきい値とＮｓｅｃｏｎｄ個の第２しきい値をメモリから抽出し（ブロック４０２）、新しい入力ベクトル｛ＸＡ，ＸＢ｝を受信する（ブロック４０３）。
【０１１８】
ブロック４０４ではパラメータｉ及びｊを１に初期化する。
ブロック４０５では、入力ベクトルのＸＡ特徴をｉ番目の第１しきい値（ＦＩＲＳＴ＿ＴＨｉ）と比較する。ＸＡ≦ＦＩＲＳＴ＿ＴＨｉならば、ブロック４０８にてｉ番目のサブテーブルを選択する。ＸＡ＞ＦＩＲＳＴ＿ＴＨｉならば、ブロック４０６にてｉパラメータをＮｆｉｒｓｔと比較する。ｉ＜Ｎｆｉｒｓｔならば、ブロック４０７にてｉを１だけインクリメントし（ｉ＝ｉ＋１）、ブロック４０５に戻る。そうでなければ、ブロック４０８にてｉ番目のサブテーブルを選択する。
【０１１９】
換言すれば、ブロック４０５〜４０８では、入力ベクトルが含まれるサブテーブルを特定するために、入力ベクトル｛ＸＡ，ＸＢ｝の最初の特徴（すなわちＸＡ）を、Ｎｆｉｒｓｔ個の第１しきい値と漸次比較する。
【０１２０】
次に、ブロック４０９〜４１２では、ブロック４０８で選択したｉ番目のサブテーブル内で、入力ベクトルが含まれる更なるサブテーブルを特定するために、入力ベクトル｛ＸＡ，ＸＢ｝の二番目の特徴（すなわちＸＢ）をＮｓｅｃｏｎｄ個の第２しきい値と漸次比較する。
【０１２１】
特に、ブロック４０９では、入力ベクトルのＸＢ特徴をｊ番目の第２しきい値（ＳＥＣＯＮＤ＿ＴＨ＿ｉｊ）と比較する。ＸＢ≦ＳＥＣＯＮＤ＿ＴＨ＿ｉｊならば、ブロック４１２にてブロック４０８で選択したｉ番目のサブテーブルのｊ番目の更なるサブテーブルを選択する。ＸＢ＞ＳＥＣＯＮＤ＿ＴＨ＿ｉｊならば、ブロック４１０にてｊパラメータをＮｓｅｃｏｎｄと比較する。ｊ＜Ｎｓｅｃｏｎｄならば、ブロック４１１にてｊを１だけインクリメントし（ｊ＝ｊ＋ｌ）、ブロック４０９に戻る。そうでなければ、ブロック４１２にてブロック４０８で選択したｉ番目のサブテーブルのｊ番目の更なるサブテーブルを選択する。ブロック４１３にてこの手順が終了する。
【０１２２】
図４に示す態様では、コードブック生成方法のブロック１０２及び１０６で行なうソートが昇順で行われたものと仮定している。ブロック１０２及び／又はブロック１０６において降順が用いられている場合には、ブロック４０５及び／又はブロック４０９にて特徴ＸＡ及び／又はＸＢが（しきい値より小さいことをチェックする代わりに）しきい値より大きいことをチェックする。
【０１２３】
また、図４に示す態様では、入力ベクトルの最初の特徴ＸＡを第１しきい値と漸次比較し、入力ベクトルの二番目の特徴ＸＢを第２しきい値と漸次比較しているが、コードブック生成方法において、この第１しきい値がテーブルの第１列に対して関連付けられ、第２しきい値が第２列に対して関連付けられたものと仮定される。
【０１２４】
しかし、一般に、しきい値の集合がコードブックテーブルのｑ番目の列に関して定められた場合には、入力ベクトルのｑ番目の特徴は上記しきい値の集合と漸次比較されるものであることに留意されたい。
【０１２５】
図１０は本発明による領域選択手順を概略的に示し、二特徴入力ベクトルと第１列ＣＡ及び第２列ＣＢを有する二次元テーブルにより表される二次元コードブックとに対して実行する。図示された例では、第３拡張サブテーブルＳの第２の拡張された更なるサブテーブルが最小歪み探索手順の領域選択手順によって特定されている。
【０１２６】
図５のフローチャートは最小歪み探索手順の好ましい態様を概略的に示しており、入力ベクトルからの距離が最小の基準ベクトルを特定することによって最小歪みを計算する。
【０１２７】
この手順によると、この最小距離基準ベクトルを、領域選択手順のブロック４１２で選択したｉ番目のサブテーブルのｊ番目の拡張された更なるサブテーブル内で探索する。次に、受信した入力ベクトルを、特定された基準ベクトルのインデックスを用いてマッピングする。
【０１２８】
具体的には、ブロック５０１にてこの手順が開始する。
ブロック５０２では、パラメータＢＥＳＴ＿ＤＩＳＴを当該コードブックの２つのポイント間の最大距離以上の値に等しい値ＭＡＸ＿ＤＩＳＴに初期化し；パラメータｋを、領域選択手順のブロック４１２で選択した拡張された更なるサブテーブルに含まれる第１基準ベクトルのインデックスに等しい値ｍに初期化し；上記拡張された更なるサブテーブルの行数Ｐｓｅｃｏｎｄ，ｊをロードする。
【０１２９】
ブロック５０３では、ブロック４１２で選択した拡張された更なるサブテーブルのＰｓｅｃｏｎｄ，ｊ基準ベクトル｛ＣＫ，Ａ，ＣＫ，Ｂ｝すべてが処理されたか否かを調べる。すなわち、ｋがｍ＋（Ｐｓｅｃｏｎｄ，ｊ−１）より大きいか否かを調べる。
【０１３０】
肯定の場合には、手順を終了する（ブロック５０９）。否定の場合には、ブロック５０４にて入力ベクトル｛ＸＡ，ＸＢ｝と現在の基準ベクトル｛ＣＫ，Ａ，ＣＫ，Ｂ｝との間の距離ＤＩＳＴを計算する。
【０１３１】
ブロック５０５では、計算した距離ＤＩＳＴとＢＥＳＴ＿ＤＩＳＴパラメータとを比較する。ＤＩＳＴ＜ＢＥＳＴ＿ＤＩＳＴならば、ブロック５０６にてパラメータＢＥＳＴ＿ＤＩＳＴを上記計算した距離ＤＩＳＴに設定し、そうでなければ、ブロック５０８にてパラメータｋを１だけインクリメントし（ｋ＝ｋ＋１）、ブロック５０３に戻る。
【０１３２】
ブロック５０７では、受信したベクトル｛ＸＡ，ＸＢ｝を、現在の基準ベクトル｛ＣＫ，Ａ，ＣＫ，Ｂ｝のインデックスで置き換え、ブロック５０８に戻る。
【０１３３】
本発明によると、この最小歪み探索手順は、Ｐｓｅｃｏｎｄ，ｊに等しい数の要素を含んだ拡張された更なるサブテーブル内で実行する。
【０１３４】
この最小歪み探索手順は、例えば（重み付き）ユークリッド距離計算によって実行できる。
【０１３５】
入力ベクトルがテーブルの中央サブテーブルから得られた更なる中央サブテーブル内に位置するとき、距離計算の最大回数（ＤＮＭ）について最悪の場合が起こる。実際、この場合に、更なるサブテーブルと対応サブテーブルとの両方が上部及び下部にて拡張される。
【０１３６】
特に、この最悪の場合には、ブロック５０４で行なう距離計算の最大回数は次式により与えられる。
ＤＮＭ＝Ｐｓｅｃｏｎｄ，４＝（Ｐｆｉｒｓｔ，２／Ｎｓｅｃｏｎｄ）＋２・Ｎｓｅｃｏｎｄ
ここで、Ｐｆｉｒｓｔ，２＝（Ｎ／Ｎｆｉｒｓｔ）＋２・Ｍｆｉｒｓｔ
【０１３７】
したがって、距離計算の最大回数（ＤＮＭ）は次式により与えられる。
【数２】
2008507718.tif 000004
【０１３８】
例として、６４個の二基準ベクトルからなる非一様コードブック（Ｎ＝６４、Ｑ＝２）を考える。６４行２列の対応コードブックテーブルを、例えば４で分割する（Ｎｆｉｒｓｔ＝４）。（Ｎ／Ｎｆｉｒｓｔ）＝６４／４＝１６行を有する４個のサブテーブルが得られる。次に、このサブテーブルを８行だけ拡張する（Ｍｆｉｒｓｔ＝８）。このようにして、拡張サブテーブルの行数は下記のようになる。
・最初と最後（上部と下部）の拡張サブテーブルについて：
Ｐ（１）＝Ｐ（４）＝Ｐｆｉｒｓｔ，１＝（Ｎ／Ｎｆｉｒｓｔ）＋Ｍｆｉｒｓｔ＝２４
・中央拡張サブテーブルについて：
Ｐ（２）＝Ｐ（３）＝Ｐｆｉｒｓｔ，２＝（Ｎ／Ｎｆｉｒｓｔ）＋２・Ｍｆｉｒｓｔ＝３２
【０１３９】
次に、各拡張サブテーブルを４個の更なるサブテーブル（Ｎｓｅｃｏｎｄ＝４）に分割することで、Ｎｆｉｒｓｔ・Ｎｓｅｃｏｎｄ＝４・４＝１６に等しい総数の更なるサブテーブルが得られ、下記の行数を有する。
・最初と最後のサブテーブルから得られた更なるサブテーブルについて：
Ｐｆｉｒｓｔ，１／Ｎｓｅｃｏｎｄ＝２４／４＝６
・他のすべての更なるサブテーブルについて：
Ｐｆｉｒｓｔ，２／Ｎｓｅｃｏｎｄ＝３２／４＝８
【０１４０】
次に、この更なるサブテーブルを３行だけ拡張する（Ｍｓｅｃｏｎｄ＝３）。このようにして、拡張された更なるサブテーブルの行数は下記のようになる。
・最初と最後の拡張サブテーブルに関する最初と最後の拡張された更なるサブテーブルについて：
Ｐ（１，１）＝Ｐ（１，４）＝Ｐ（４，１）＝Ｐ（４，４）＝（Ｐｆｉｒｓｔ，１／Ｎｓｅｃｏｎｄ）＋Ｍｓｅｃｏｎｄ＝９
・最初と最後の拡張サブテーブルに関する他のすべての更なる中央拡張サブテーブルについて：
Ｐ（１，２）＝Ｐ（１，３）＝Ｐ（４，２）＝Ｐ（４，３）＝（Ｐｆｉｒｓｔ，１／Ｎｓｅｃｏｎｄ）＋２・Ｍｓｅｃｏｎｄ＝１２
・中央拡張サブテーブルに関する最初と最後の拡張された更なるサブテーブルについて：
Ｐ（２，１）＝Ｐ（２，４）＝Ｐ（３，１）＝Ｐ（３，４）＝（Ｐｆｉｒｓｔ，２／Ｎｓｅｃｏｎｄ）＋Ｍｓｅｃｏｎｄ＝１１
・中央拡張サブテーブルに関する他のすべての更なる中央拡張サブテーブルについて：
Ｐ（２，２）＝Ｐ（２，３）＝Ｐ（３，２）＝Ｐ（３，３）＝（Ｐｆｉｒｓｔ，２／Ｎｓｅｃｏｎｄ）＋２・Ｍｓｅｃｏｎｄ＝１４
【０１４１】
この例では、１４に等しい距離計算の最大回数ＤＮＭが得られた。この値は、上述した関係によって下記の通り得ることができる。
【数３】
2008507718.tif 000005
【０１４２】
したがって、本発明により実行する距離計算の最大回数は、従来のＥＴＳＩ圧縮アルゴリズム（網羅的な計算）で行なわなければならない距離計算の回数（Ｎに等しい）よりも少ない。
【０１４３】
本発明のコードブック生成方法では、しきい値がサブテーブル及び更なるサブテーブルに関連付けられるが、好ましくは最小歪み探索手順は拡張された更なるサブテーブル内で実行されることに更に留意されたい。このことにより、入力ベクトルが上記更なるサブテーブルにより表されるコードブック領域の境界近くに位置する場合でさえ、ベクトル圧縮における誤差を有利に低減できる。
【０１４４】
本発明のコードブック生成方法で用いる上述のパラメータＮｆｉｒｓｔ、Ｍｆｉｒｓｔ、Ｎｓｅｃｏｎｄ及びＭｓｅｃｏｎｄの選択については、例えば、次の近似手順により実行できる。すなわち、これらのパラメータは、まず多数の行を有するサブテーブル（更なるサブテーブル）を使用し、入力ベクトルの所与の集合（例えばアプリケーションから得られるか、又はランダムに生成する）についてのベクトル圧縮方法の結果を調べ、そして、該圧縮方法の誤差が該アプリケーションに依存する許容可能な予め設定されたしきい値より小さくなるまで、サブテーブル（更なるサブテーブル）の行数を漸次減少させることによって選択できる。
【０１４５】
これに関し、上述のパラメータは高い柔軟性で選択できることが分かる。実際、種々のサブテーブルは互いに異なる行数を有することができ、かつ／又は異なる行数（例えば、各サブテーブルに対して異なるＭｆｉｒｓｔ）だけ拡張できる。同様に、種々の更なるサブテーブルは互いに異なる行数を有することができ、かつ／又は異なる行数（例えば、各更なるサブテーブルに対して異なるＭｓｅｃｏｎｄ）だけ拡張できる。例えば、有利には、これらのパラメータは、奇数個の基準ベクトルを有するか又は２の累乗数でない基準ベクトルを有する非一様コードブックの場合でさえ、ほぼ同じ行数を有する更なるサブテーブルを得るように選択できる。
【０１４６】
出願人は、最小歪み探索手順の複雑さ及び精度に関して上述のパラメータの選択手順を最適化する方法を見いだした。
【０１４７】
提案する方法では、最小歪み探索手順で必要とされる計算労力が、受信入力ベクトルが含まれる領域とは独立に、受信入力ベクトルすべてについてほぼ同じとなるように、ほぼ同数の基準ベクトルを含んだ非一様コードブック空間内の領域（すなわちほぼ同数の行を有するコードブックテーブルの拡張された更なるサブテーブル）を生成することを目指す。このように、非一様コードブック空間をほぼ同数のポイントを有する異なる次元の領域に分割する。
【０１４８】
提案する最適化方法では、以下の条件が課される。
・テーブルと各拡張サブテーブルを、（（更なる）サブテーブルが一方の側でのみ拡張されたより小さい次元を有する極端な状態を考えて）ほぼ同数の行（それぞれＮ／ＮｆｉｒｓｔとＰｆｉｒｓｔ，ｉ／Ｍｓｅｃｏｎｄに等しい）を含んだサブテーブルと更なるサブテーブルとにそれぞれ分割する；
・サブテーブルを同じ行数Ｍｆｉｒｓｔだけ拡張し、更なるサブテーブルを同じ行数Ｍｓｅｃｏｎｄだけ拡張する；
・基準ベクトルの数Ｎは２の累乗に等しい：Ｎ＝２ｎ。コードブック中の基準ベクトルの数が２の累乗でない場合には、２の累乗に等しい行数を得るため、ダミーの基準ベクトル（例えばコードブック最低又は最大ベクトルに等しい集合）からなるテーブルの下部又は上部にいくつかの行を加えることができる。次に、最小歪み探索手順の実行からダミーベクトルを除外する。上述した「ＡＵＲＯＲＡ」ＥＴＳＩ規格により定められたコードブックはすべて、下記の通り２の累乗に等しいＮ数個の基準ベクトルを有することが分かる。
・Ｎｆｉｒｓｔは２の累乗である：Ｎｆｉｒｓｔ＝２ｒ；
・Ｍｆｉｒｓｔの最大値はＮ／Ｎｆｉｒｓｔである；
・Ｎｓｅｃｏｎｄの最大値はＰｆｉｒｓｔ，１である；
・Ｎｓｅｃｏｎｄは２の累乗である：Ｎｓｅｃｏｎｄ＝２ｔ；
・Ｍｓｅｃｏｎｄの最大値はＰｆｉｒｓｔ，１／Ｎｓｅｃｏｎｄである；
・次の関係を満たさなければならない：
【数４】
2008507718.tif 000006
ここで、ｒ、ｓ、ｔ、ｕは負でない整数であり、ｍｏｄはモジュロ演算子である（すなわち、「ｘ  ｍｏｄ  ｙ」は除算「ｘ／ｙ」の剰余である）。
【０１４９】
図６のフローチャートはパラメータ最適化方法の好ましい態様を概略的に示す。この方法では、上述した条件が満たされること、及び最終的な解が複雑さ関数ＣＰＸ（後で定義）の最小に対応し、かつ誤差が所定のしきい値ＴＨＲ＿ＥＲＲ（最終的にはゼロに設定）より小さくなることを検証することによって、値ＢＥＳＴ＿Ｎｆｉｒｓｔ、ＢＥＳＴ＿Ｍｆｉｒｓｔ、ＢＥＳＴ＿Ｎｓｅｃｏｎｄ、ＢＥＳＴ＿Ｍｓｅｃｏｎｄの最適な組を計算する。
【０１５０】
図６のフローチャートによると、４つの組み込みループを実行する。
ブロック７０１にて手順を開始する。
ブロック７０２にてパラメータＢＥＳＴ＿ＣＰＸをＮに初期化する（複雑さ関数ＣＰＸの最悪の場合）。
【０１５１】
ブロック７０３にて、パラメータｒを１に初期化し（すなわちＢＥＳＴ＿Ｎｆｉｒｓｔ＝２ｒ＝２）、パラメータＢＥＳＴ＿Ｎｆｉｒｓｔを設定することを目的とする最も外側の最初のループを開始する。
【０１５２】
ブロック７０４では、このｒパラメータ値をｎと比較する。ｒ＝ｎ（すなわち、ＢＥＳＴ＿Ｎｆｉｒｓｔ＝２ｒ＝Ｎ）ならば、ブロック７０８にて最適化手順を終了する。ｒ≠ｎならば、ブロック７０５を実行する。
【０１５３】
ブロック７０５では、パラメータｓをＮ／Ｎｆｉｒｓｔ（すなわちＢＥＳＴ＿Ｍｆｉｒｓｔ＝Ｎ／Ｎｆｉｒｓｔ）に初期化し、パラメータＢＥＳＴ＿Ｍｆｉｒｓｔを設定することを目的とする第２ループを開始する。
【０１５４】
ブロック７０６では、このｓパラメータ値をゼロと比較する。ｓ＝０（すなわち、ＢＥＳＴ＿Ｍｆｉｒｓｔ＝０）ならば、ブロック７０７にてパラメータｒを１だけインクリメントし（ｒ＝ｒ＋１）、ブロック７０４に戻る。ｓ≠０ならば、ブロック７０９にてパラメータｔをｌｏｇ２（Ｐｆｉｒｓｔ，１）に設定し、パラメータＢＥＳＴ＿Ｎｓｅｃｏｎｄを設定することを目的とする第３のループを開始する。
【０１５５】
ブロック７１０では、このｔパラメータ値を１と比較する。ｔ＝１（すなわち、ＢＥＳＴ＿Ｎｓｅｃｏｎｄ＝２ｔ＝１）ならば、ブロック７１１にてパラメータｓを１だけ減じ（ｓ＝ｓ?１）、ブロック７０６に戻る。ｔ≠１ならば、ブロック７１２にて以下の条件を調べる。すなわち、条件とは、Ｐｆｉｒｓｔ，１  ｍｏｄ  Ｎｓｅｃｏｎｄ≠０；Ｐｆｉｒｓｔ，２  ｍｏｄ  Ｎｓｅｃｏｎｄ≠０である。この条件のうち１つが満たされるならば、ブロック７１３にてパラメータｔを１だけ減じ（ｔ＝ｔ?１）、ブロック７１０に戻る。上記条件のどれも満たさなければ、ブロック７１４にてパラメータｕをＰｆｉｒｓｔ，１／Ｎｓｅｃｏｎｄ（すなわち、ＢＥＳＴ＿Ｍｓｅｃｏｎｄ＝Ｐｆｉｒｓｔ，１／Ｎｓｅｃｏｎｄ）に設定し、パラメータＢＥＳＴ＿Ｍｓｅｃｏｎｄを設定することを目的とする第４ループを開始する。
【０１５６】
ブロック７１５では、このｕパラメータ値をゼロと比較する。ｕ＝０（すなわち、ＢＥＳＴ＿Ｍｓｅｃｏｎｄ＝０）ならば、ブロック７１３にてパラメータｔを１だけ減じ（ｔ＝ｔ−１）、ブロック７１０に戻る。ｕ≠１ならば、ブロック７１６にて複雑さ関数ＣＰＸを計算する。
【０１５７】
複雑さ関数ＣＰＸは、最小歪み探索手順によって最小歪み基準ベクトルを見つけるためにランタイムに実行しなければならない距離計算の回数を表す。例えば、複雑さ関数は、各領域（各拡張された更なるサブテーブル）内に含まれる基準ベクトルの平均数として定義され、コードブックを分割したすべての領域（すべての拡張された更なるサブテーブル）を考慮に入れて計算する。すなわち、次式の通りである。
【数５】
2008507718.tif 000007
【０１５８】
ブロック７１７では、ブロック７１６にて計算したＣＰＸ値をＢＥＳＴ＿ＣＰＸパラメータと比較する。ＣＰＸ≧ＢＥＳＴ＿ＣＰＸならば、ブロック７１３にてパラメータｔを１だけ減じ（ｔ＝ｔ−１）、ブロック７１０に戻る。ＣＰＸ＜ＢＥＳＴ＿ＣＰＸならば、ブロック７１８にて誤差パラメータＥＲＲを計算する。
【０１５９】
ブロック７１９では、ブロック７１８にて計算したＥＲＲ値をＴＨＲ＿ＥＲＲと比較する。ＥＲＲ＞ＴＨＲ＿ＥＲＲならば、ブロック７１３にてパラメータｔを１だけ減じ（ｔ＝ｔ−１）、ブロック７１０に戻る。ＥＲＲ≦ＴＨＲ＿ＥＲＲならば、ブロック７２０にてパラメータＢＥＳＴ＿Ｎｆｉｒｓｔ、ＢＥＳＴ＿Ｍｆｉｒｓｔ、ＢＥＳＴ＿Ｎｓｅｃｏｎｄ、ＢＥＳＴ＿Ｍｓｅｃｏｎｄ、ＢＥＳＴ＿ＣＰＸをそれぞれ２ｒ、ｓ、２ｔ、ｕ及びＣＰＸに等しくなるように設定する。それから、ブロック７２１にて、パラメータｕを１だけ減じ（ｕ＝ｕ−１）、ブロック７１５に戻る。ＣＰＸ＜ＢＥＳＴ＿ＣＰＸであるときだけ、ブロック７１８で誤差パラメータＥＲＲを計算することが分かる。すなわち、複雑さ関数ＣＰＸの新しい極小が、ブロック７２０の最後の実行で設定したパラメータＢＥＳＴ＿Ｎｆｉｒｓｔ、ＢＥＳＴ＿Ｍｆｉｒｓｔ、ＢＥＳＴ＿Ｎｓｅｃｏｎｄ、ＢＥＳＴ＿Ｍｓｅｃｏｎｄ、ＢＥＳＴ＿ＣＰＸの値を用いて見つかった場合にのみ、誤差パラメータＥＲＲを計算する。このことにより、有利には最適化手順の計算回数が有利に低減される。
【０１６０】
ブロック７１８では、入力ベクトルの集合（アプリケーションに依存するか又はランダムに生成）に対して本発明による最小歪み探索手順を実行し、そのようにして得た結果を従来の網羅的計算アルゴリズムにより得られた結果と比較することによって、この誤差パラメータＥＲＲを得ることができる。
【０１６１】
ブロック７１９で用いるしきい値ＴＨＲ＿ＥＲＲはユーザーが事前に定め、アプリケーションに依存し、ゼロに設定することもできる。
【０１６２】
図６に示す態様では、パラメータＮｆｉｒｓｔを設定することを目的としブロック７０４にて開始する最も外側のループは、最小値２から最大値Ｎまで変化するＮｆｉｒｓｔについて実行することが分かる。よって、パラメータ最適化手順では、まずＮｆｉｒｓｔの小さい値を用いて調べることで、有利には本発明のコードブック生成方法において形成するサブテーブルの数を少なくし、よって記憶すべきサブテーブルの数を減らすことができる。
【０１６３】
パラメータＭｆｉｒｓｔを設定することを目的としブロック７０５にて開始するループに関しては、最大値Ｎ／Ｎｆｉｒｓｔから最小値０まで変わるＭｆｉｒｓｔについて実行する。このように、パラメータ最適化手順は、複雑さを最大値から最小値まで調べることにより実行する。
【０１６４】
パラメータＮｓｅｃｏｎｄを設定することを目的としブロック７０９にて開始するループに関しては、最大値Ｐｆｉｒｓｔ，１から最小値２まで変わるＮｓｅｃｏｎｄについて実行する。このように、パラメータ最適化手順では、まずＮｓｅｃｏｎｄの大きな値について調べることで、有利には本発明のコードブック生成方法において形成すべき基準ベクトルの数を少なくし更なるサブテーブルの数を多くできるので、複雑さ関数を低減できる。
【０１６５】
パラメータＭｓｅｃｏｎｄを設定することを目的としブロック７１４にて開始するループに関しては、最大値Ｐｆｉｒｓｔ，１／Ｎｓｅｃｏｎｄから最小値０まで変わるＭｓｅｃｏｎｄについて実行する。このように、ＥＲＲパラメータがＭｓｅｃｏｎｄの現在の値を有するしきい値ＴＨＲ＿ＥＲＲ以上であるならば、Ｍｓｅｃｏｎｄのうちより小さい値は調べず、Ｎｓｅｃｏｎｄの別の値を用いて手順を繰り返す。有利には、このことにより、最適化手順の計算を削減できる。
【０１６６】
二次元コードブック（Ｑ＝２）に関してパラメータ最適化手順を説明してきたが、二次元の場合の上記説明から当業者に明らかなように、Ｑ次元コードブック（Ｑ＞２）の場合にも拡張できる。
【０１６７】
本発明のコードブック生成方法のように、本発明のパラメータ最適化手順もまた、所与のコードブックに対して１回だけオフラインで実行できることが分かる。
【０１６８】
パラメータ最適化手順は、所定のアプリケーションに与えられたコードブックのＮｆｉｒｓｔ、Ｍｆｉｒｓｔ、Ｎｓｅｃｏｎｄ及びＭｓｅｃｏｎｄパラメータの最適値を該アプリケーションに対して選択するためだけでなく、何らかの理由で該アプリケーションに与えられたコードブックが変わるとき、上記パラメータの新しい最適値を選択するためにも用いることができることも分かる。
【０１６９】
二次元コードブック（Ｑ＝２）についての図１、４及び５のフローチャートに関して、本発明のコードブック生成方法及び圧縮方法を上記説明した。しかし、本発明の方法はＮ行Ｑ列からなるＱ次元コードブック（Ｑは２より大）にも適用できる。
【０１７０】
この場合、図７に概略的示されるように、二列コードブックテーブルについて開示したコードブック生成方法のソート、分割及び拡張工程を、Ｑ列コードブックテーブルの各列について反復して実行することができる。
【０１７１】
特に、有利にはコードブックテーブルの各列に対して以下の工程を繰り返さなければならない。
・テーブルの行又は前のサイクルで得られた各（拡張）サブテーブルの行を、現在考慮中の列に含まれる特徴値に対して昇順又は降順にソートする；
・テーブル、又は前のサイクルで得られた各（拡張）サブテーブルを所定数のサブテーブルに分割する；
・現在考慮中の列について１つのしきい値を各サブテーブルに関連つける；
・テーブルの別の列（もし存在すれば）を考慮し、各サブテーブルを所定数の行だけ適宜拡張することで、次のサイクルで処理すべき拡張サブテーブルを生成する。
【０１７２】
生成した（拡張）サブテーブル又は更なる（拡張）サブテーブル、及び生成したすべてのしきい値は、後で、領域選択手順及び上記説明したものと類似の最小歪み探索手順において使用できるように、メモリに記憶する。
【０１７３】
一般に、上述の工程の最後の実行によって生成した（拡張）サブテーブル又は（拡張）更なるサブテーブルのみをメモリに記憶できることが分かる。
【０１７４】
拡張工程が実行されない場合には、これは上述の工程の最後の実行で得られる際にソートされる基準ベクトルと共にテーブルをメモリに記憶することに対応する。
【０１７５】
確かに、拡張工程を実行する場合、最後から二番目の対象列に関して実行される分割及び拡張工程で生成して最後の列に関してソートした（更なる）拡張サブテーブルをメモリに記憶するのが有利である。最後の対象列に関して実行されるソート、分割及び拡張工程で生成した拡張された更なるサブテーブル（領域選択手順及び最小歪み探索手順で使用される）は、適当なポインタによってアクセスできる。
【０１７６】
最後から二番目の対象列に関して実行される分割及び拡張工程で生成した（更なる）拡張サブテーブルは全体として、最後の対象列に関して実行されるソート、分割及び拡張工程で生成する更なるサブテーブルと比べて少ない数の基準ベクトルを含むので、メモリ空間を節約できる。
【０１７７】
図７では、影付き長方形が、図４に関して開示したものと類似の領域選択手順により受信入力ベクトルについて漸次特定できる（拡張）サブテーブルの例を表す。
【０１７８】
図７から明らかなように、コードブックテーブルの列が増えれば、最小歪み探索手順により最後に選択したサブテーブル６０１内で計算しなければならない距離計算の回数が減る。
【０１７９】
確かに、図示された例では、第１列から最後の列まで影付き拡張サブテーブルの行数が減少している。最小歪み探索手順を適用するのに用いるサブテーブルは最後の列中にあるので、本発明では、列数を増すことにより、特徴ベクトル圧縮で必要な計算労力をいっそう削減できる。
【０１８０】
本発明によるコードブック生成方法、領域選択手順、最小歪み探索手順、及びパラメータ最適化手順は、適当なハードウエア、ファームウエア及び／又はソフトウエアの実装によりパーソナルコンピュータ、組み込み装置又はコンピュータネットワークなどの電子処理システムによって実行できる。
【０１８１】
上記実装は、本明細書から当業者には明らかな原理に従って本発明の範囲から逸脱することなく設計される。
【０１８２】
本発明の方法は、よりコンパクトなフォーマットにて情報を伝送又は記憶するためにデータ圧縮が必要とされるときにはいつでも使用できる。例えば、画像処理システムにおける画像信号の圧縮、又は分散型音声認識システムにおける音声信号の圧縮に使用できる。
【０１８３】
例として、図８は、本発明により実現される分散型音声認識システム８００の一態様のブロック図である。
【０１８４】
システム８００は特徴抽出及びデータ圧縮のためのユーザー装置８１０と、最終的な信号認識のための認識システム８２０（又は「バックエンド」）とを備える。ユーザー装置８１０と認識システム８２０は、それぞれ携帯電話と遠隔サーバ８２０とし得る。
【０１８５】
システム８００は、データネットワーク８０５を更に備え、ユーザー装置８１０と認識システム８２０との間でのデータ交換のためにデータ伝送路を構成する。
【０１８６】
図８に示すブロック図では、ユーザー装置８１０は変換装置８０１を備え、変換装置８０１では、入力音声をサンプリングして元の入力音声のデジタル表現に変換する。変換装置８０１は電気音響装置であり、音圧波形をデジタル信号に変換するすべての装置、例えばマイクロフォン変換器、アナログフィルター、自動利得制御器及びアナログ・デジタル変換器などが挙げられる。
【０１８７】
ユーザー装置８１０は更に特徴抽出装置８０２（又は「フロントエンド」）を備え、特徴抽出装置８０２では、デジタル化した音声を特徴抽出アルゴリズムで処理して一連の特徴ベクトルを生成する。この特徴抽出アルゴリズムは上述の「ＡＵＲＯＲＡ」ＥＴＳＩ規格に従って実行でき、入力音声の各時間フレームに対して１４特徴ベクトルを生成する。
【０１８８】
分割装置８０３は、１４特徴をペアでグルーピングすることによって各１４特徴ベクトルを７個の二特徴ベクトルに分割する。
【０１８９】
圧縮装置８０４は、本発明のコードブック生成方法により生成した７個の夫々の所定コードブックを用いることにより、これら７個の二特徴ベクトルの各々を本発明のベクトル圧縮方法により圧縮する。好ましくは、本発明のコードブック生成方法で用いるパラメータＮｆｉｒｓｔ、Ｍｆｉｒｓｔ、Ｎｓｅｃｏｎｄ、及びＭｓｅｃｏｎｄは、本発明のパラメータ最適化手順により予め選択する。メモリ装置８０６は、本発明のコードブック生成方法により得た（更なる）サブテーブル及びしきい値を記憶する。
【０１９０】
ベクトル圧縮ブロック８０４から出力されたインデックスは、データ伝送路８０５を介して認識システム８２０に送り、認識システム８２０が、従来技術により入力音声の認識及び／又は再構成を行なうべく入ってくるインデックスを処理する。このデータ伝送路は例えば４．８ｋｂｉｔ／ｓの無線データチャンネルとし得る。
【０１９１】
モバイル機器は計算、メモリ、及び電池エネルギーについて制限されているので、本発明のコードブック生成方法及びパラメータ最適化方法は、有利には例えばパーソナルコンピュータなどのモバイル機器の外部の電子処理システムによってオフラインで実行できる。その場合、ベクトル圧縮装置８０４により使用すべく生成した（更なる）拡張サブテーブル及びしきい値は、モバイル機器のメモリ（例えば、メモリ装置８０６）に記憶する。
【０１９２】
このようにして、上述したように必要とされる計算労力の少ない本発明のベクトル圧縮方法を、限定的な資源に負荷をかけ過ぎることなくモバイル機器で実行する。
【図面の簡単な説明】
【０１９３】
【図１】本発明のコードブック生成方法を概略的に説明するフローチャートである。
【図２】二特徴基準ベクトルからなる非一様コードブックの例を示す。
【図３】Ｎ個の二特徴ベクトルを有するコードブックを表すテーブルの例を示す。
【図４】本発明による領域選択手順の好ましい態様を概略的に説明するフローチャートである。
【図５】本発明による最小歪み探索手順の好ましい態様を概略的に説明するフローチャートである。
【図６】本発明のコードブック生成方法で用いるパラメータＮｆｉｒｓｔ、Ｍｆｉｒｓｔ、Ｎｓｅｃｏｎｄ、Ｍｓｅｃｏｎｄについて最適値セットを計算するパラメータ最適化手順の好ましい態様を概略的に説明するフローチャートである。
【図７】本発明のコードブック生成方法により処理したＱ次元テーブルを概略的に示す。
【図８】本発明の一態様によるＤＳＲシステムを概略的に示す。
【図９】本発明によるデータ圧縮方法を概略的に説明するフローチャートである。
【図１０】二次元テーブル上で実行される本発明の領域選択手順を概略的に表す。
【図１】
2008507718.tif 000008
【図２】
2008507718.tif 000009
【図３】
2008507718.tif 000010
【図４】
2008507718.tif 000011
【図５】
2008507718.tif 000012
【図６】
2008507718.tif 000013
【図７】
2008507718.tif 000014
【図８】
2008507718.tif 000015
【図９】
2008507718.tif 000016
【図１０】
2008507718.tif 000017
【手続補正書】
【提出日】平成19年4月13日(2007.4.13)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
そうゆうわけで、欧州通信規格協会（ＥＴＳＩ）がＤＲＳ特徴抽出及び圧縮アルゴリズムの規格（「Ａｕｒｏｒａ」）（ＥＴＳＩ  ＥＳ  ２０２．０５０、ＥＳ  ２０２  ２１２、ＥＳ  ２０１  １０８及びＥＳ  ２０２  ２１１）を公表した。
【国際調査報告】
2008507718.tif 000018
2008507718.tif 000019