(57)【特許請求の範囲】
【請求項１】
ソートの基準となる次元を指定し、指定された次元の代表ベクトルの値に基づいて代表ベクトルをソートすることによりコードブックを並び替えるソーティングステップと、
入力ベクトルと代表ベクトルとのひずみを計算し、次に探索する代表ベクトルのアドレスを計算する第１の演算ステップと、
現在の最小のひずみとその代表ベクトルの番号を保持しており、現在の最小のひずみ をもつ代表ベクトルと上記第１の演算ステップにより計算された代表ベクトルについてひずみを比較し、ひずみが小さい方を現在の最小のひずみとすることにより、符号化される代表ベクトルの候補を決める判定ステップと、
上記判定ステップによる判定結果に基づいて重心計算・平均ひずみ計算・部分ひずみ計算を行う第２の演算ステップと、
上記第２の演算ステップにより得られる部分ひずみを基準としてソートする部分ひずみソーティングステップと、
上記部分ひずみソーティングステップによりソートされた２つの部分ひずみの格差を比較する比較ステップと、
上記比較ステップにおける比較結果に基づいて、部分ひずみの小さい代表ベクトルを部分ひずみの大きい代表ベクトルの近傍に移動させる代表ベクトル移動ステップとを有し、
上記第１の演算ステップにおいて入力ベクトルと代表ベクトルとのひずみを計算し、次に探索する代表ベクトルのアドレスを計算する際に、最初に使用する初期代表ベクトルのアドレスを指定するとともに、ソートの基準となった次元を指示して、上記各ステップを繰り返し行い、最小のひずみを持つ代表ベクトルに入力ベクトルを符号化するベクトル量子化のコードブック生成方法。
【請求項２】
上記第１の演算ステップでは、入力ベクトルと複数の代表ベクトルとのひずみを並列に計算し、次に探索する代表ベクトルのアドレスを計算し、上記判定ステップでは、上記第１の演算ステップにより得られる複数のひずみを比較して符号化される代表ベクトルの候補を決める請求項１記載のベクトル量子化のコードブック生成方法。
【請求項３】
上記比較ステップでは、上記部分ひずみソーティングステップによりソートされた複数個の部分ひずみの格差を比較し、
上記代表ベクトル移動ステップでは、上記比較ステップにおける比較結果に基づいて、複数の部分ひずみの小さい代表ベクトルを部分ひずみの大きい代表ベクトルの近傍に移動させる請求項１又は請求項２のいずれか１項に記載のベクトル量子化のコードブック生成方法。
【請求項４】
入力ベクトル集合を格納する入力ベクトル集合記憶手段と、
コードブックを格納するコードブック記憶手段と、
上記コードブック記憶手段からコードブックを読み出し、指定された次元を基準としてコードブックをソートし、ソートしたコードブックを上記コードブック記憶手段の指定したアドレスに書き込むソーティング手段と、
入力ベクトルと代表ベクトルのひずみを計算し、次に探索する代表ベクトルのアドレスを計算する第１の演算手段と、
現在の最小のひずみとその代表ベクトルの番号を保持しており、現在の最小のひずみをもつ代表ベクトルと上記第１の演算手段より計算された代表ベクトルについてひずみを比較し、ひずみが小さい方を新しい現在の最小のひずみとすることにより、代表ベクトルの候補を決める判定手段と、
上記判定手段による判定結果に基づいて重心計算・平均ひずみ計算・部分ひずみ計算を行う第２の演算手段と、
上記第２の演算手段により得られる部分ひずみを基準としてソートする部分ひずみソーティング手段と、
上記部分ひずみソーティング手段によりソートされた２つの部分ひずみの格差を比較する比較手段と、
上記比較手段による比較結果に基づいて、部分ひずみの小さい代表ベクトルを部分ひずみの大きい代表ベクトルの近傍に移動させる代表ベクトル移動手段と、
上記ソーティング手段、第１の演算手段、判定手段、第２の演算手段、部分ひずみソーティング手段、部分ひずみ比較手段及び代表ベクトル移動手段の処理フローを制御する制御手段とを備え、
上記制御手段は、上記ソーティング手段にソートの基準となる次元を指定し、上記第１の演算手段に、入力ベクトルと代表ベクトルとのひずみを計算して次に探索する代表ベクトルのアドレスを計算する第１の演算処理を行う際に最初に使用する初期代表ベクトルのアドレスを指定するとともに、ソートの基準となった次元を指示し、第２の演算手段に、上記判定手段による判定結果に基づいて重心計算・平均ひずみ計算・部分ひずみ計算を行う第２の演算処理を行う際に最初に使用する任意の初期コードブックの設定を指示して、上記第１の演算手段による第１の演算処理と、上記判定手段による判定処理と、上記ソーティング手段によるソーティング処理と、上記第２の演算手段による第２の演算処理と、上記部分ひずみソーティング手段による部分ひずみソーティング処理と、上記部分ひずみ比較手段による部分ひずみ比較処理と、上記代表ベクトル移動手段による代表ベクトル移動処理を繰り返し行い、最小のひずみを持つ代表ベクトルに入力ベクトルを符号化するベクトル量子化のコードブック生成装置。
【請求項５】
上記第１の演算手段は、入力ベクトルと複数の代表ベクトルとのひずみを並列に計算し、次に探索する代表ベクトルのアドレスを計算し、上記判定手段は、上記第１の演算手段により得られる複数のひずみを比較して符号化される代表ベクトルの候補を決める請求項４記載のベクトル量子化のコードブック生成装置。
【請求項６】
上記比較手段は、上記部分ひずみソーティングステップによりソートされた複数個の部分ひずみの格差を比較し、
上記代表ベクトル移動手段は、上記比較手段における比較結果に基づいて、複数の部分ひずみの小さい代表ベクトルを部分ひずみの大きい代表ベクトルの近傍に移動させる請求項４又は請求項５のいずれか１項に記載のベクトル量子化のコードブック生成装置。
【請求項７】
上記ソーティング手段によりソートしたコードブックの並び順を格納する記憶手段をさらに備えることを特徴とする請求項４乃至請求項６のいずれか１項に記載のベクトル量子化のコードブック生成装置。
【請求項８】
初期の代表ベクトルに前の入力ベクトルが符号化された代表ベクトルを指定することを特徴とする請求項４乃至請求項７のいずれか１項に記載のベクトル量子化のコードブック生成装置。
【請求項９】
初期の代表ベクトルに前回の反復のときに符号化された代表ベクトルを指定することを特徴とする請求項４乃至請求項８のいずれか１項に記載のベクトル量子化のコードブック生成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は，ベクトル量子化技術に関わり，特にパターン認識・計算幾何学・画像信号・音声信号におけるベクトル量子化のコードブック生成装置及び方法に関するものである。
【０００２】
【従来の技術】
ベクトル量子化は、入力空間を有限個の代表ベクトルで符号化する手法である。ベクトル量子化の応用例として、パターン認識の特徴抽出，計算幾何学のポスト配置問題，情報の圧縮，画像や音声などの量子化などが挙げられる。
【０００３】
図３４にベクトル量子化の概念図を示す。
【０００４】
ベクトル量子化には
（１）入力ベクトルの符号化
（２）コードブックの生成
という２つの側面がある。
【０００５】
ベクトル量子化の（１）入力ベクトルの符号化の手続では、入力ベクトルｘ（１０５０）に対してＮ個の代表ベクトル（コードベクトルと呼ばれることもある）からなるコードブックＷ＝｛ｗｉ∈ＲＫ：ｉ＝０，・・・，Ｎ−１｝（１０４０）の中から最も近い代表ベクトルｗｍｉｎを選びだし（１０６０）、その代表ベクトルのインデックスｍｉｎ、又は、その代表ベクトルの値を出力する（１０７０）。
【０００６】
その際、最も近い代表ベクトルを選ぶときの測度として、非負のひずみ測度ｄ（ｘ，ｗｉ）を利用する。すなわち、代表ベクトルの番号を出力したいときの式は、次の（１）式にて表すことができる。
【０００７】
【数１】
0004590747.tif 000002
【０００８】
また、代表ベクトルの値を出力したいときの式は、次の（２）式にて表すことができる。
【０００９】
【数２】
0004590747.tif 000003
【００１０】
また、ベクトル量子化の（２）コードブックの生成では、初期コードブック（１０１０）を設定し、コードブック生成用の入力ベクトル集合Ｘ＝（ｘ（ｔ）：ｔ＝０，・・・，Ｔ−１）（１０３０）を与えて、入力ベクトル集合に合うように代表ベクトルの値を修正することを繰り返して最適化し（１０２０）、最終的に最適なコードブック（１０４０）を得る。コードブック生成用の入力ベクトルは、（１）入力ベクトルの符号化で入力される入力ベクトルと異なっていてもかまわない。
【００１１】
コードブックの評価には、与えられた入力ベクトル集合を対応する代表ベクトルで符号化したときに生じるひずみの期待値（平均ひずみ）を用いて行われる。この平均ひずみは非凸な関数であり、多くの局所的最小値を持つ。最適なコードブックとは、平均ひずみを最小にするコードブックである。すなわち、最適なコードブックを持つベクトル量子化器は、最もひずみの少ない符号化を行うことができる。平均ひずみは、次の（３）式にて定義される。
【００１２】
【数３】
0004590747.tif 000004
【００１３】
ただし、δｔｉはクロネッカーのデルタであり、入力ベクトルｘｔが代表ベクトルｗｉに符号化されたとき１であり、それ以外は０である。
【００１４】
コードブックを生成するアルゴリズムとして、適応修正型の競合学習アルゴリズムや一括修正型のＬＢＧアルゴリズム[Linde,Y., Buzo, A., & Gray, R. M..“An algorithm for vector quantizer design."IEEE Transactions on Communications,28,pp.84-95, 1980.]がよく知られている。
【００１５】
文献[Ueda, N., & Nakano, R..“A new competitive learning approach based on an equidistortion principle for designing optimal vector quantizers." Neural Networks,7, pp.1211-1227, 1994.]によれば，競合学習アルゴリズムはＬＢＧアルゴリズムの適応型になっている。ここでは、ＬＢＧアルゴリズムによるコードブック生成法だけを取り上げるが、適応型の競合学習アルゴリズムにも適用可能である。
【００１６】
ＬＢＧアルゴリズムは、収束条件を満足するまで、次のステップ（ａ），（ｂ）を反復するアルゴリズムである。
【００１７】
（ａ）Ｔ個のコードブック生成用の入力ベクトル集合に対して、現在のコードブックの中から各入力ベクトルｘ（ｔ）に最も近い代表ベクトルｗｍｉｎを探索し、符号化される代表ベクトルの番号ｍｉｎを保存しておく。
【００１８】
（ｂ）入力ベクトル集合と各入力ベクトルが符号化される代表ベクトルの番号を用いて、代表ベクトルの重心を計算しコードブックを更新する。
【００１９】
コードブック生成方法であるＬＢＧアルゴリズムのステップ（ａ）は、各入力ベクトルに対して最もひずみが小さい代表ベクトルを探索し、符号化するステップである。この符号化のステップは、全ての代表ベクトルとのひずみを計算し、最も近い代表ベクトルを選択する全探索が基本であるため、非常に時間がかかる。この操作を全ての入力ベクトルに対して行う必要があるので時間は膨大にかかる。
【００２０】
この問題を解決する手法の一つとして、特開平６−４５９４６号公報に開示されたベクトル量子化方法及びベクトル量子化装置がある。このベクトル量子化技術は、文献［中野恵一，笠原博徳：“ソートされたコードブックを用いた高速ベクトル量子化（Fast Vector Quantization Using Sorted Codebook：VQ-SC）”電子情報通信学会論文誌D-II Vol.J77-D-II No.10 pp.1984-1992,1994］に関連するものであって、ＶＱ−ＳＣは、大雑把に述べると以下のようなアルゴリズムである。
【００２１】
（１）代表ベクトルを各次元ごとにソートし，その順番を記憶しておく。
【００２２】
（２）探索が済んだ代表ベクトルかどうかをしめすフラグをクリアする。
【００２３】
（３）ひずみの下限値となるひずみを計算する。
【００２４】
（４）分枝限定法の原理に基づいて、ひずみの上限値を利用することで解の精度を向上する可能性のない代表ベクトルの探索を省略する。探索が済んだ代表ベクトルはフラグをたてる。ひずみの下限値に使われている代表ベクトルの探索が省略された場合には、ひずみの下限値を更新する。ひずみの上限値とひずみの下限値が一致するまで探索を続ける。次の探索する代表ベクトルの決め方は、ヒューリスティックである。
【００２５】
ひずみの上限値とひずみの下限値を利用することにより、コードブックの一部を調べれば全探索した場合と同じ代表ベクトルが高速に探索できる。
【００２６】
【発明が解決しようとする課題】
しかし、上記の方法には次のような問題点がある。
【００２７】
（１）各次元ごとに代表ベクトルをソートする必要があり、次元が高くなるとソートにかかる時間が大きくなる。
【００２８】
（２）各次元ごとにソートされた代表ベクトルの順番を記憶しておく必要があり、記憶しておくメモリ容量が膨大になる。
【００２９】
（３）各入力ベクトルごとにどの代表ベクトルの探索が済んだかどうかを示すフラグをクリアする必要があり、入力ベクトルが多いと、クリアする時間が膨大になる。また、代表ベクトルの数分、フラグのためのメモリ容量が必要である。
【００３０】
（４）次の探索する代表ベクトルをヒューリスティックに決めてよいため、効率の良い決定方法を考える必要がある。
【００３１】
そこで、本発明の目的は、上記の問題点を解決することができるようにしたベクトル量子化のコードブック生成方法及びコードブック生成装置を提供することにある。
【００３２】
【課題を解決するための手段】
ここで、Ｋ次元の入力ベクトルｘに対して、最小のひずみをもつ代表ベクトルｗｍｉｎを探索するときに、ある次元ｋに対して、次の（４）式となるような代表ベクトルｗｉを探索する必要はない。
【００３３】
【数４】
0004590747.tif 000005
【００３４】
しかし、（４）式は、符号化されるｗｍｉｎが求まっているときの条件であり、（４）式を計算することができない。また、ｋ次元に対する代表ベクトルの値は、規則正しく並んでいるわけではなく、順番がランダムな状態になっているので、探索終了条件を決めることができない。
【００３５】
そこで、本発明では、次のような方法を採用する。
【００３６】
（１）いままでの探索で見つかった最小の代表ベクトルをｗｃｕｒｍｉｎとする。すなわち、探索が終了すれば最終的に得られた代表ベクトルｗｃｕｒｍｉｎが最小のひずみｄｍｉｎ  ＝ｄｃｕｒｍｉｎをもつ代表ベクトルｗｍｉｎ  ＝ｗｃｕｒｍｉｎとなる。
【００３７】
（２）探索を始める前に、ｋ次元の値に応じて代表ベクトルを小さい順（又は大きい順）にソートしておく。（４）式を満足する代表ベクトルが存在したら、ソートしてあるのでそれ以上先の代表ベクトルは最小のひずみを持つ代表ベクトルになる可能性は全くない。すなわち、代表ベクトルをソートをしておくことで、探索の効率を大幅に上げることができる。
【００３８】
（４）式のひずみの計算を考察すると、一般に各次元の代表ベクトルの値のとりうる範囲（レンジ）は異なるはずである。したがって、レンジが最も広いものを選ぶと探索回数は減るはずである。画像の階調変換では、Ｒ，Ｇ，Ｂはどの次元でも０〜２５５の値をとるので、どの次元を選択しても同じような回数になると思われる。
【００３９】
ソートしておくことで探索の打切り方法が決まるが、最低限の回数で探索を打ち切ることが望ましい。そのためには、一番最初に設定する最小の代表ベクトルｗｃｕｒｍｉｎの決め方が重要である。この初期の代表ベクトルの決め方次第で、探索効率が大幅に変わることが予想される。
【００４０】
２つの場合に分けて、探索する初期の代表ベクトルの決め方は、以下のように設定する方法が効率的な選択であると考えられる。
【００４１】
ＬＰＧアルゴリズムなどの設計アルゴリズムを用いてベクトル量子化器を設計するときは、同じ入力データ集合を用いるので、収束間際のサイクルほど前サイクルと同じ代表ベクトルに符号化される可能性が高い。そのため、前サイクルで符号化された代表ベクトルを初期値とする。
【００４２】
あらかじめ決められている代表ベクトルに入力ベクトルを符号化するとき、一般的には、隣の入力データが符号化された代表ベクトルを初期値とする。
【００４５】
本発明は、ソートの基準となる次元を指定し、指定された次元の代表ベクトルの値に基づいて代表ベクトルをソートすることによりコードブックを並び替えるソーティングステップと、入力ベクトルと代表ベクトルとのひずみを計算し、次に探索する代表ベクトルのアドレスを計算する第１の演算ステップと、現在の最小のひずみとその代表ベクトルの番号を保持しており、現在の最小のひずみ をもつ代表ベクトルと上記第１の演算ステップにより計算された代表ベクトルについてひずみを比較し、ひずみが小さい方を現在の最小のひずみとすることにより、符号化される代表ベクトルの候補を決める判定ステップと、上記判定ステップによる判定結果に基づいて重心計算・平均ひずみ計算・部分ひずみ計算を行う第２の演算ステップと、上記第２の演算ステップにより得られる部分ひずみを基準としてソートする部分ひずみソーティングステップと、上記部分ひずみソーティングステップによりソートされた２つの部分ひずみの格差を比較する比較ステップと、上記比較ステップにおける比較結果に基づいて、部分ひずみの小さい代表ベクトルを部分ひずみの大きい代表ベクトルの近傍に移動させる代表ベクトル移動ステップとを有し、上記第１の演算ステップにおいて入力ベクトルと代表ベクトルとのひずみを計算し、次に探索する代表ベクトルのアドレスを計算する際に、最初に使用する初期代表ベクトルのアドレスを指定するとともに、ソートの基準となった次元を指示して、上記各ステップを繰り返し行い、最小のひずみを持つ代表ベクトルに入力ベクトルを符号化することを特徴とする。
【００５７】
また、本発明は、ベクトル量子化装置であって、入力ベクトル集合を格納する入力ベクトル集合記憶手段と、コードブックを格納するコードブック記憶手段と、上記コードブック記憶手段からコードブックを読み出し、指定された次元を基準としてコードブックをソートし、ソートしたコードブックを上記コードブック記憶手段の指定したアドレスに書き込むソーティング手段と、入力ベクトルと代表ベクトルのひずみを計算し、次に探索する代表ベクトルのアドレスを計算する第１の演算手段と、現在の最小のひずみとその代表ベクトルの番号を保持しており、現在の最小のひずみをもつ代表ベクトルと上記第１の演算手段により計算された代表ベクトルについてひずみを比較し、ひずみが小さい方を新しい現在の最小のひずみとすることにより、代表ベクトルの候補を決める判定手段と、上記判定手段による判定結果に基づいて重心計算・平均ひずみ計算・部分ひずみ計算を行う第２の演算手段と、上記第２の演算手段により得られる部分ひずみを基準としてソートする部分ひずみソーティング手段と、上記部分ひずみソーティング手段によりソートされた２つの部分ひずみの格差を比較する比較手段と、上記比較手段による比較結果に基づいて、部分ひずみの小さい代表ベクトルを部分ひずみの大きい代表ベクトルの近傍に移動させる代表ベクトル移動手段と、上記ソーティング手段、第１の演算手段、判定手段、第２の演算手段、部分ひずみソーティング手段、部分ひずみ比較手段及び代表ベクトル移動手段の処理フローを制御する制御手段とを備え、上記制御手段は、上記ソーティング手段にソートの基準となる次元を指定し、上記第１の演算手段に、入力ベクトルと代表ベクトルとのひずみを計算して次に探索する代表ベクトルのアドレスを計算する第１の演算処理を行う際に最初に使用する初期代表ベクトルのアドレスを指定するとともに、ソートの基準となった次元を指示し、第２の演算手段に、上記判定手段による判定結果に基づいて重心計算・平均ひずみ計算・部分ひずみ計算を行う第２の演算処理を行う際に最初に使用する任意の初期コードブックの設定を指示して、上記第１の演算手段による第１の演算処理と、上記判定手段による判定処理と、上記ソーティング手段によるソーティング処理と、上記第２の演算手段による第２の演算処理と、上記部分ひずみソーティング手段による部分ひずみソーティング処理と、上記部分ひずみ比較手段による部分ひずみ比較処理と、上記代表ベクトル移動手段による代表ベクトル移動処理を繰り返し行い、最小のひずみを持つ代表ベクトルに入力ベクトルを符号化することを特徴とする。
【００６７】
【発明の実施の形態】
以下、本発明の実施の形態について図面を参照しながら詳細に説明する。
【００６８】
本発明は、例えば図１に示すような構成のベクトル量子化器のコードブック生成装置１００に適用される。
【００６９】
このコードブック生成装置１００は、入力ベクトル集合メモリ１１０、ソーティング装置１２０、コードブックメモリ１３０、第１の演算装置１４０、判定装置１５０、第２の演算装置１６０及び制御装置１７０から構成される。
【００７０】
このコードブック生成装置１００において、入力ベクトル集合メモリ１１０は、入力ベクトル集合Ｘ＝（ｘ（ｔ）∈ＲＫ：ｔ＝０，・・・，Ｔ−１）を記憶しておくメモリであり、第１の演算装置１４０からアドレスの指定をうけ、対応する入力ベクトルｘ（ｔ）と初期代表ベクトルの番号を第１の演算装置１４０に渡す。また、入力ベクトル集合メモリ１１０は、判定装置１５０から、入力ベクトルｘ（ｔ）の初期代表ベクトルの番号ｍｉｎを受け取り、格納する。
【００７１】
ソーティング装置１２０は、制御装置１７０からのソートの指示とどの次元ｋを基準としてソートするかの指示を受け、コードブックメモリ１３０からコードブックを読み出し、指定された次元を基準としてコードブックをソートする。また、ソーティング装置１２０は、ソートしたコードブックをコードブックメモリ１３０の指定したアドレスに書き込む。
【００７２】
コードブックメモリ１３０は、コードブックＷ（ｐ）＝｛ｗｉ（ｐ）∈ＲＫ：ｉ＝０，・・・，Ｎ−１｝を記憶しておくメモリであり、ひずみ計算・アドレス計算を行う第１の演算装置１４０からアドレスを受け取り、対応する代表ベクトルのデータ（代表ベクトルの値ｗｉ（ｐ），番号ｉ）を第１の演算装置１４０に渡す。また、コードブックメモリ１３０は、重心計算・平均ひずみ計算を行う第２の演算装置１６０から、データ（更新されたコードブックＷ（ｐ＋１））及び書き込むアドレスを受け取り、対応するアドレスにコードブックが書き込まれる。また、コードブックメモリ１３０は、コードブックをソーティング装置１２０に渡す。さらに、コードブックメモリ１３０は、ソーティング装置１２０によりソートされたコードブックと書き込むアドレスを受け取り、指定されたアドレスにコードブックを格納する。
【００７３】
第１の演算装置１４０は、入力ベクトル集合メモリ１１０にアドレスを指定して、対応する入力ベクトルｘ（ｔ）と初期代表ベクトルの番号を受け取る。また、第１の演算装置１４０は、制御装置１７０からひずみ・アドレスの計算の指示を受け、コードブックメモリ１３０に読み込みたい代表ベクトルのアドレスを指定して、対応するデータ（代表ベクトルの値ｗｉ（ｐ），番号ｉなど）を読み込む。また、第１の演算装置１４０は、入力ベクトルと代表ベクトルとのひずみｄ（ｘ（ｔ），ｗｉ（ｐ））を計算する。そして、第１の演算装置１４０は、ひずみｄ（ｘ（ｔ），ｗｉ（ｐ））とデータ（代表ベクトルの番号と値）を判定装置１５０に渡す。また、第１の演算装置１４０は、制御装置１７０からソートの基準となった次元ｋの指示を受け、ｋ次元だけのひずみｄ（ｘｋ（ｔ），ｗｉｋ（ｐ））も判定装置１５０に渡す。さらに、第１の演算装置１４０は、判定装置１５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスを計算する。なお、第１の演算装置１４０は、探索終了を示す情報finishを受けた場合は、次の入力ベクトルｘ（ｔ＋１）の符号化に取りかかる。
【００７４】
判定装置１５０は、現在の最小のひずみｄｃｕｒｍｉｎとその代表ベクトルの番号ｍｉｎを保持しており、現在の最小のひずみｄｃｕｒｍｉｎをもつｍｉｎ番の代表ベクトルと第１の演算装置１４０により計算されたｉ番の代表ベクトルについてひずみｄ（ｘ（ｔ），ｗｉ（ｐ））を比較し、ひずみが小さい方を新しいｍｉｎ番、現在の最小のひずみｄｃｕｒｍｉｎとする。また、判定装置１５０は、制御装置１７０から判定の指示を受け、ｋ次元だけのひずみｄ（ｘｋ（ｔ），ｗｉｋ（ｐ））と現在の最小のひずみｄｃｕｒｍｉｎを比較し、ｄ（ｘｋ（ｔ），ｗｉｋ（ｐ））の方が大きければ、次に探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を変更し、また、ｕｐ／ｄｏｗｎ両方向とも調べ終わった場合には探索終了を示す情報finish を演算装置１４０に渡し、ｄ（ｘｋ（ｔ），ｗｉｋ（ｐ））の方が小さければ、同方向の次の代表ベクトルを調べる情報を第１の演算装置１４０に渡す。また、判定装置１５０は、ｕｐ／ｄｏｗｎ両方向とも調べ終わり探索終了finishになったとき、第２の演算装置１６０に入力ベクトルｘ（ｔ）、現在の最小のひずみを持つ初期代表ベクトルの番号ｍｉｎ及び最小のひずみｄｃｕｒｍｉｎを出力する。さらに、判定装置１５０は、探索終了finishになったとき、現在の最小のひずみを持つ初期代表ベクトルの番号ｍｉｎを入力ベクトルｘ（ｔ）の初期代表ベクトルとして入力ベクトル集合メモリ１１０に格納する。
【００７５】
第２の演算装置１６０は、判定装置１５０から、入力ベクトルｘ（ｔ）と符号化された代表ベクトルの番号ｍｉｎと入力ベクトルを符号化したときのひずみdｃｕｒｍｉｎを受け取る。そして、この第２の演算装置１６０は、代表ベクトル番号ｍｉｎに対応するデータ（分子ｗｍｉｎｎｕｍと分母ｗｍｉｎｄｅｎ、さらに平均ひずみＤｓｕｍ）の計算を次の（５）式、（６）及び（７）式にしたがって行う。
【００７６】
ｗｍｉｎｎｕｍ＋＝ｘ（ｔ）                                （５）
ｗｍｉｎｄｅｎ＋＝１                                      （６）
Ｄｓｕｍ＋＝dｃｕｒｍｉｎ                                （７）
また、この第２の演算装置１６０は、Ｔ個の入力ベクトルに対して、符号化が終了し、上記途中計算が終了したと制御装置１７０から指示を受けたら、代表ベクトル重心ｗｉ（ｐ＋１）、平均ひずみＤの計算を次の（８）式及び（９）式にしたがって行う。
【００７７】
【数５】
0004590747.tif 000006
【００７８】
また、この第２の演算装置１６０は、制御装置１７０からの指示により、全てのデータ（分子ｗｉｎｕｍと分母ｗｉｄｅｎ、さらに平均ひずみＤｓｕｍ，∀ｉ）をクリアする。
【００７９】
また、この第２の演算装置１６０は、データ（更新されたコードブックＷ（ｐ＋１））及び書き込むアドレスを渡し、対応するアドレスに更新されたコードブックを書き込む。
【００８０】
この第２の演算装置１６０は、制御装置１７０からの指示により、任意の初期コードブックをコードブックメモリ１３０に設定する。
【００８１】
制御装置１７０は、ソーティング装置１２０、第１の演算装置１４０、判定装置１５０及び第２の演算装置１６０の処理フローを制御する。また、制御装置１７０は、ソーティング装置１２０にソートの基準となる次元を指定する。また、制御装置１７０は、第１の演算装置１４０に初期代表ベクトルのアドレス（又は番号）を指定し、また、ソートの基準となった次元を指示する。さらに、制御装置１７０は、第２の演算装置１６０に任意の初期コードブックの設定を指示する。
【００８２】
このような構成のコードブック生成装置１００において、本発明では、図２のフローチャートに示すコードブック生成アルゴリズムにしたがってソートされた代表ベクトルを用いた高速ベクトル量子化（Vector Quantization by Searching in Sirted Codebook：ＶＱ−ＳＳＣ）を利用したコードブック生成を行う。
【００８３】
すなわち、このコードブック生成装置１００では、先ず、ステップ（Ｆ１０１）において、代表ベクトル初期配置を設定する。また、代表ベクトルをソートするための基準の次元ｋを指定する。
【００８４】
次のステップ（Ｆ１０２）では、次元ｋの代表ベクトルの値に基づいて代表ベクトルをソートする。ソートされた順番の情報については，以下の２通りのやり方が考えられる。
【００８５】
（１）直接代表ベクトルの順番を入れ替えてしまう。代表ベクトルの番号を変更したくないときは、代表ベクトルの番号の情報を持つ構造体にして入れ替える。直接ならべ変えているので、自分より下位の代表ベクトルの番号ｌｏｗｅｒは、自分の配列の番号−１  とした配列の番号となる。また、自分より上位の代表ベクトルの番号ｕｐｐｅｒは、自分の配列の番号＋１とした配列の番号となる。
【００８６】
（２）ソートしたときの順番を示す配列を用意する場合、各代表ベクトルが保持すべき情報は、自分より下位の代表ベクトルの番号ｌｏｗｅｒと、自分より上位の代表ベクトルの番号ｕｐｐｅｒである。
【００８７】
次のステップ（Ｆ１０３）では、入力ベクトルｘ（ｔ）と初期の代表ベクトルｗｉ（ｐ）とのひずみの計算を行い、このひずみｄ（ｘ（ｔ），ｗｉ（ｐ））を現在の最小のひずみｄｃｕｒｍｉｎとし、番号ｉを符号化の候補として保存しておく。
【００８８】
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｉ（ｐ））            （１０）
ｍｉｎ＝ｉ                                             （１１）
次のステップ（Ｆ１０４）では、初期の代表ベクトルｗｉ（ｐ）  の両隣の代表ベクトルの番号、すなわち、
ｌｏｗｅｒ＝下位方向の隣の代表ベクトルの番号
ｕｐｐｅｒ＝上位方向の隣の代表ベクトルの番号
を保存する。
【００８９】
次のステップ（Ｆ１０５）では、入力ベクトルｘ（ｔ）と代表ベクトルｗｌｏｗｅｒ（ｐ）とのひずみｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｐ））の計算を行い、計算途中のｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｐ））を保存しておく。そして、このステップ（Ｆ１０５）では、計算したひずみｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｐ））が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、
ｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｐ））＜ｄｃｕｒｍｉｎ  （１２）
が成り立つか否かを判定し、この（１２）式が成り立つならば、
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｐ））  （１３）
ｍｉｎ＝ｌｏｗｅｒ                                    （１４）
とする。
【００９０】
次のステップ（Ｆ１０６）では、下位方向の探索を続けるかどうか判断する。
このステップ（Ｆ１０６）において、もし、
ｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｐ））＞ｄｃｕｒｍｉｎ  （１５）
を満足するなら、下位方向の探索は終了で、ステップ（Ｆ１０８）へ移り、さもなければ、次のステップ（Ｆ１０７）へ進む。
【００９１】
ステップ（Ｆ１０７）は、代表ベクトルの番号ｌｏｗｅｒの更新ステップであり、現在のｌｏｗｅｒ番の代表ベクトルの下位方向の隣の代表ベクトルの番号を新しいｌｏｗｅｒとして、ステップ（Ｆ１０５）へ戻る。
【００９２】
ステップ（Ｆ１０８）では、入力ベクトルｘ（ｔ）とｕｐｐｅｒ番の代表ベクトルｗｕｐｐｅｒ（ｐ）  とのひずみｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｐ））の計算を行い、計算途中のｄ（ｘｋ（ｔ），ｗｕｐｐｅｒｋ（ｐ））を保存しておく。このステップ（Ｆ１０８）では、計算したひずみｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｐ））が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、
ｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｐ））＜ｄｃｕｒｍｉｎ  （１６）
が成り立つか否かを判定して、この（１６）式が成り立つならば、
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｐ））  （１７）
ｍｉｎ＝ｕｐｐｅｒ                                    （１８）
とする。
【００９３】
次のステップ（Ｆ１０９）では、上位方向の探索を続けるかどうか判断する。このステップ（Ｆ１０９）では、もし、
ｄ（ｘｋ（ｔ），ｗｕｐｐｅｒｋ（ｐ））＞ｄｃｕｒｍｉｎ  （１９）
を満足するなら、上位方向の探索は終了で、ステップ（Ｆ１１１）へ移り、さもなければ、次のステップ（Ｆ１１０）へ進む。
【００９４】
ステップ（Ｆ１１０）は、代表ベクトル番号ｕｐｐｅｒの更新ステップであり、現在のｕｐｐｅｒ番の代表ベクトルの上位方向の隣の代表ベクトルの番号を新しいｕｐｐｅｒとして、ステップ（Ｆ１０８）へ戻る。
【００９５】
次のステップ（Ｆ１１１）では、入力ベクトルの符号化と代表ベクトルの重心計算・平均ひずみの準備を行う。
【００９６】
このステップ（Ｆ１１１）において、入力ベクトルｘ（ｔ）は、最小のひずみｄｃｕｒｍｉｎを持つ番号ｍｉｎの代表ベクトルｗｍｉｎ（ｐ）に符号化される。
【００９７】
このステップ（Ｆ１１１）では、符号化された代表ベクトルｍｉｎの位置を更新するステップ（Ｆ１１４）において用いる分子ｗｍｉｎｎｕｍ、分母ｗｍｉｎｄｅｎ及び平均ひずみＤｓｕｍの計算を次の（２０）式、（２１）及び（２２）式にしたがって行っておく。
【００９８】
ｗｍｉｎｎｕｍ＋＝ｘ（ｔ）                           （２０）
ｗｍｉｎｄｅｎ＋＝１                                 （２１）
Ｄｓｕｍ＋＝ｄｃｕｒｍｉｎ                        （２２）
次のステップ（Ｆ１１２）では、すべての入力ベクトルの符号化が終了したか否かを判定する。このステップ（Ｆ１１２）では、もし、ｔ＝Ｔ−１が成り立つならば、ステップ（Ｆ１１４）へ移り、さもなければ、次のステップ（Ｆ１１３）へ進む。
【００９９】
ステップ（Ｆ１１３）では、ｔ＝ｔ＋１として、ステップ（Ｆ１０３）に戻り、次の入力ベクトルの探索をする。
【０１００】
ステップ（Ｆ１１４）では、代表ベクトルの重心の計算と平均ひずみの計算を行う。このステップ（Ｆ１１４）は、ＬＢＧアルゴリズムにおける代表ベクトルの重心の更新を行うステップであり、次の（２３）式で表すことができる。
【０１０１】
【数６】
0004590747.tif 000007
【０１０２】
しかし，（２３）式の分子・分母の計算は先のステップ（Ｆ１１１）で済んでいるので、次の（２４）式の計算を行えばよい。
【０１０３】
【数７】
0004590747.tif 000008
【０１０４】
また、平均ひずみＤは、次の（２５）式により計算する。
【０１０５】
【数８】
0004590747.tif 000009
【０１０６】
次のステップ（Ｆ１１５）では、収束判定を行う。このステップ（Ｆ１１５）における収束判定条件を満たさないときは、ステップ（Ｆ１０２）へ戻り、収束判定条件を満たすときは、処理を終了する。
【０１０７】
ここで、このステップ（Ｆ１１５）における収束判定条件には、次のようなものが考えられる。その他のものでも構わない。
【０１０８】
（１）代表ベクトルの更新がなくなったら終了する。
【０１０９】
（２）所望の平均ひずみ以下になったら終了する。
【０１１０】
（３）反復回数で打ち切る。
【０１１１】
ここで、このコードブック生成装置におけるベクトル量子化の符号化アルゴリズム（ＶＱ−ＳＳＣ）の動作について、例題を用いて説明する。
【０１１２】
この例題では、ひずみ測度として二乗誤差ひずみ測度を用いている。
【０１１３】
ｄ（ｘ，ｗ）＝（ｘ−ｗ）２                               （２６）
当然、このほかのひずみ測度を用いた場合も、本発明は有効である。また、次元ごとに違うひずみ測度を用いたときも、本発明は有効である。
【０１１４】
３次元の入力ベクトルｘ＝（１２，１６，１３）に対して、従来どおりすべての代表ベクトルに対してひずみを計算し、ベクトル量子化（符号化）される代表ベクトルを求めた例を図３に示す。この場合、１２個の代表ベクトルに対してひずみを計算しないと、符号化される代表ベクトルが決まらない。今回の例題では、最小ひずみ８を持つ９番の代表ベクトルｗ９＝（１４，１８，３）に符号化される。
【０１１５】
これに対して、このコードブック生成装置におけるベクトル量子化の符号化アルゴリズムでは、ｋ＝１に対して代表ベクトルをソートしてある。わかりやすいようにソートした順に代表ベクトルの番号をつけた状態にしてある。実際は、わざわざ代表ベクトルの番号をつけ直す必要ななく、自分の代表ベクトルの両隣（上位方向・下位方向）の代表ベクトルの番号を保存するようにプログラムすればよい。
【０１１６】
もし、符号化される代表ベクトルが事前にわかっているならば、最小ひずみが８なので、√８以下の最大整数である２以下の範囲を探索すればよい。図３から、１次元で１２±２となる代表ベクトルは、（７），（８），（９）番の３個の代表ベクトルだけを調べればよい。
【０１１７】
しかし、事前に符号化される代表ベクトルがわかるはずがないので、次のようなアルゴリズム（探索０〜探索６）を用いて探索をすることになる。
【０１１８】
すなわち、探索０では、図４に示すように、初期の代表ベクトルを（７）番の代表ベクトルとし、ひずみｄ（ｘ，ｗ７）を計算する。
【０１１９】
ｄ（ｘ，ｗ７）＝１７
ｌｏｗｅｒ＝６
ｕｐｐｅｒ＝８
そして、最小のひずみｄｃｕｒｍｉｎ＝１７とその代表ベクトルの番号ｍｉｎ＝７を保存保存する。
【０１２０】
探索１では、図５に示すように、ｌｏｗｅｒ（６）番の代表ベクトルのひずみｄ（ｘ，ｗｌｏｗｅｒ）を計算する。
【０１２１】
ｄ（ｘ１，ｗｌｏｗｅｒ１）＝９
ｄ（ｘ，ｗｌｏｗｅｒ）＝１８９
そして、ｄ（ｘ，ｗｌｏｗｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも大きいので、最小のひずみｄｃｕｒｍｉｎはそのままの値すなわち
ｄｃｕｒｍｉｎ＝１７
ｍｉｎ＝７
を保持する。また、ｄ（ｘ１  ，ｗｌｏｗｅｒ１）は現在の最小のひずみｄｃｕｒｍｉｎよりも小さいので、次のｌｏｗｅｒ＝５の探索２に移る。
【０１２２】
次の探索２では、図６に示すように、ｌｏｗｅｒ（５）番の代表ベクトルのひずみｄ（ｘ，ｗｌｏｗｅｒ）を計算する。
【０１２３】
ｄ（ｘ１，ｗｌｏｗｅｒ１）＝９
ｄ（ｘ，ｗｌｏｗｅｒ）＝１４
そして、ｄ（ｘ，ｗｌｏｗｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも小さいので、最小のひずみｄｃｕｒｍｉｎを更新して
ｄｃｕｒｍｉｎ＝１４
ｍｉｎ＝５
とする。また、ｄ（ｘ１，ｗｌｏｗｅｒ１）はｄｃｕｒｍｉｎ＝１４よりも小さいので、次のｌｏｗｅｒ＝４の探索３に移る。
【０１２４】
探索３では、図７に示すように、ｌｏｗｅｒ（４）番の代表ベクトルのひずみを計算を行う。
【０１２５】
ｄ（ｘ１，ｗｌｏｗｅｒ１）＝１６
ｄ（ｘ，ｗｌｏｗｅｒ）＝１８６
そして、ｄ（ｘ，ｗｌｏｗｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも大きいので、最小のひずみｄｃｕｒｍｉｎはそのままの値すなわち
ｄｃｕｒｍｉｎ＝１４
ｍｉｎ＝５
を保持する。また、ｄ（ｘ１，ｗｌｏｗｅｒ１）はｄｃｕｒｍｉｎ＝１４よりも大きいので、下位方向の探索は終了し、次にｕｐｐｅｒ＝８の上位方向の探索４に移る。
【０１２６】
探索４では、図８に示すように、ｕｐｐｅｒ（８）番の代表ベクトルのひずみを計算する。
【０１２７】
ｄ（ｘ１，ｗｕｐｐｅｒ１）＝１
ｄ（ｘ，ｗｕｐｐｅｒ）＝４６
そして、ｄ（ｘ，ｗｕｐｐｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも大きいので、最小のひずみｄｃｕｒｍｉｎはそのままの値すなわち
ｄｃｕｒｍｉｎ＝１４
ｍｉｎ＝５
を保持する。また、ｄ（ｘ１，ｗｕｐｐｅｒ１）はｄｃｕｒｍｉｎ＝１４よりも小さいので、次のｕｐｐｅｒ＝９の探索５に移る。
【０１２８】
探索５では、図９に示すように、ｕｐｐｅｒ（９）番の代表ベクトルのひずみを計算する。
【０１２９】
ｄ（ｘ１，ｗｕｐｐｅｒ１）＝４
ｄ（ｘ，ｗｕｐｐｅｒ）＝８
そして、ｄ（ｘ，ｗｕｐｐｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも小さいので、最小のひずみｄｃｕｒｍｉｎを更新して、
ｄｃｕｒｍｉｎ＝８
ｍｉｎ＝９
とする。また、ｄ（ｘ１，ｗｕｐｐｅｒ１）はｄｃｕｒｍｉｎ＝９よりも小さいので、次のｕｐｐｅ０の探索６に移る。
【０１３０】
探索６では、図１０に示すように、ｕｐｐｅｒ（１０）番の代表ベクトルのひずみを計算する。
【０１３１】
ｄ（ｘ１，ｗｕｐｐｅｒ１）＝９
ｄ（ｘ，ｗｕｐｐｅｒ）＝４１
そして、ｄ（ｘ，ｗｕｐｐｅｒ）と現在の最小のひずみｄｃｕｒｍｉｎとを比較すると、ｄ（ｘ，ｗｌｏｗｅｒ）はｄｃｕｒｍｉｎよりも大きいので、最小のひずみｄｃｕｒｍｉｎはそのままの値すなわち
ｄｃｕｒｍｉｎ＝８
ｍｉｎ＝９
を保持する。また、ｄ（ｘ１，ｗｕｐｐｅｒ１）はｄｃｕｒｍｉｎ＝９よりも大きいので、上位方向の探索終了する。
【０１３２】
このようにして下位方向、上位方向、両方とも探索を終了し、最終的に得られた最小のひずみｄｃｕｒｍｉｎ＝８をもつｍｉｎ＝９番の代表ベクトルが入力ベクトルｘ＝（１２，１６，１３）に対する符号化される代表ベクトルである。
【０１３３】
ここで、図１１より、あらかじめ符号化される代表ベクトルがわかっている場合は３個の代表ベクトルを探索すれば十分であるが、一般には無理なので初期代表ベクトルを決めて探索する必要がある。今回の場合、最小ひずみを更新しながら探索したので、７個の代表ベクトルを探索することで最小のひずみを持つ代表ベクトルを得ることができた。これが階調変換では，代表ベクトルの数が２５６個あるので、探索範囲を大幅に制限することが期待できる。
【０１３４】
また、本発明は、ひずみの部分和を用いた高速化手法を組み合わせるとより一層の効果がある。ひずみの部分和を用いた高速化手法は、次の（２７）式で示されるひずみの部分和が現在の最小のひずみｄｃｕｒｍｉｎと比較して大きいときは、次の代表ベクトルを探索する。すなわち、ひずみを最後まで求めるのではなく、計算途中のひずみと現在の最小のひずみを比較することで探索の効率をあげる手法である。
【０１３５】
【数９】
0004590747.tif 000010
【０１３６】
このひずみの部分和を用いた高速化手法は、文献［Bei C-D. & Gray, R. M..“An improvement of minimum distortion encoding algorithm for vector quantization.” IEEE Transactions on Communications, COM-33, pp.1132-1133, 1985.］に詳述されている。
【０１３７】
ここでは、上述の図１に示したコードブック生成装置の変形例として、図１２を参照して差分のみを説明する。
【０１３８】
図１２に示すコードブック生成装置’において、コードブックメモリ１３０は、コードブックとアドレスをソーティング装置１２０に渡す。
【０１３９】
ソーティング装置１２０は、制御装置１７０からのソートの指示とどの次元ｋを基準としてソートするかの指示を受け、コードブックメモリ１３０からコードブックのアドレスとコードブックを読み出し、指定された次元を基準としてコードブックをソートする。そして、そのソートされた代表ベクトルの順番通りに、各代表ベクトルのアドレスを並び替え、ソート順に並んだアドレスをコードブックソート表１８０に書き込む。
【０１４０】
第１の演算装置１４０は、判定装置１５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスをコードブックソート表１８０に参照しに行き、アドレスを受け取る。そして、コードブックメモリ１３０に、そのアドレスを指定して、対応するデータ（代表ベクトルの番号ｉと値ｗｉ（ｐ）など）を読み込む。
【０１４１】
そして、コードブックソート表１８０は、ソーティング装置１２０から受け取ったアドレスを格納する。また、コードブックソート表１８０は第１の、演算装置１４０からの次の探索する代表ベクトルの参照の指示に従って、その代表ベクトルのアドレスを第１の演算装置１４０に渡す。
【０１４２】
ここで、次の文献には、[Gersho,A..“Asymptotically optimal block quantization."IEEE Transactions on Information Theory,25,pp.373-380,1979.]、[Yamada, Y., Tazaki, S. & Gray, R. M..“Asymptotic performance of block quantizers with difference distortion measures." IEEE Transactions on Information Theory},26, pp.6-14, 1980.]、[Ueda, N., & Nakano, R..“A new competitive learning approach based on an equidistortion principle for designing optimal vector quantizers." Neural Networks,7, pp.1211-1227, 1994.]等には、ベクトル量子化の理論的な研究から、ひずみ測度に次の式２８で示されるユークリッド（ｌ２）ノルムのｒ乗を用いた場合の大域的最適解の必要条件である等ひずみ原理が示されている。
【０１４３】
【数１０】
0004590747.tif 000011
【０１４４】
多数の代表ベクトルに対して、入力空間の確率分布が多数の互いに素のクラスタから構成されているとき、最小の平均ひずみとなるベクトル量子化器における代表ベクトルの配置は、各代表ベクトルの部分ひずみが互いに等しくなるように配置された状態になる。
【０１４５】
ｉ番目の代表ベクトルの部分ひずみＤｉ  は，次の（２９）式を用いて計算する。
【０１４６】
【数１１】
0004590747.tif 000012
【０１４７】
ただし、δｉｔはクロネッカーのデルタであり、代表ベクトルｉが最も小さいひずみを持つとき１となる。
【０１４８】
等ひずみ原理の簡単な例を図１３に示す。黒丸は代表ベクトルであり、点線はボロノイ領域である。入力ベクトルが二つの正方形のクラスタから一様に生起する問題に対する代表ベクトルの最適な配置である。そのとき，各代表ベクトルの部分ひずみは等しい状態になっている。
【０１４９】
上述の如くＬＢＧアルゴリズムや競合学習は降下法であるため、コードブックが大域的最小値の近くに配置されたとき大域的最小値を見つけることができる。そこで、本発明では、代表ベクトルの配置を等ひずみ原理で示される配置の近傍に設定することで最適な配置が得られる可能性が高まることに着目し、あらかじめ、代表ベクトルを部分ひずみが等しいような配置の近傍に配置することは困難であるので、更新中に部分ひずみが等しくなるように代表ベクトルを移動させる。
【０１５０】
そこで、本発明では、等ひずみ原理に基づいたMin-Max Order Compare(MMOC) 操作を加えたＬＢＧアルゴリズムを提案する。ＭＭＯＣ操作は、更新中に部分ひずみを計算し、部分ひずみのばらつきを減少させるように代表ベクトルを再配置する。ＭＭＯＣ操作により各代表ベクトルの部分ひずみを互いに等しい状態に近づけることができる。
【０１５１】
例えば図１４に示すような構成のコードブック生成装置２００により、ＶＱ−ＳＳＣによる符号化を利用したＭＭＯＣ操作を加えたＬＢＧアルゴリズムを実行することができる。
【０１５２】
図１４に示すコードブック生成装置２００は、入力ベクトル集合メモリ２１０、ソーティング装置２２０、コードブックメモリ２３０、第１の演算装置２４０、判定装置２５０、第２の演算装置２６０、部分ひずみソーティング装置２６２、部分ひずみ比較装置２６４、代表ベクトル移動装置２６６及び制御装置２７０から構成される。
【０１５３】
このコードブック生成装置２００において、入力ベクトル集合メモリ２１０は、入力ベクトル集合Ｘ＝（ｘ（ｔ）∈ＲＫ：ｔ＝０，・・・，Ｔ−１）を記憶しておくメモリであり、第１の演算装置２４０からアドレスの指定をうけ、対応する入力ベクトルｘ（ｔ）と初期代表ベクトルの番号を第１の演算装置２４０に渡す。また、入力ベクトル集合メモリ２１０は、判定装置２５０から、入力ベクトルｘ（ｔ）の初期代表ベクトルの番号ｍｉｎを受け取り、格納する。
【０１５４】
ソーティング装置２２０は、制御装置２７０からのソートの指示とどの次元ｋを基準としてソートするかの指示を受け、コードブックメモリ２３０からコードブックを読み出し、指定された次元を基準としてコードブックをソートする。また、ソーティング装置２２０は、ソートしたコードブックをコードブックメモリ２３０の指定したアドレスに書き込む。
【０１５５】
コードブックメモリ２３０は、コードブックＷ（ｐ）＝｛ｗｉ（ｐ）∈ＲＫ：ｉ＝０，・・・，Ｎ−１｝を記憶しておくメモリであり、ひずみ計算・アドレス計算を行う第１の演算装置２４０からアドレスを受け取り、対応する代表ベクトルのデータ（代表ベクトルの値ｗｉ（ｐ），番号ｉ）を第１の演算装置２４０に渡す。また、このコードブックメモリ２３０は、代表ベクトル移動装置２６６から、データ（更新されたコードブックＷ（ｐ＋１）と書き込むアドレス）を受け取り、対応するアドレスに更新されたコードブックが書き込まれる。また、コードブックメモリ２３０は、コードブックをソーティング装置２２０に渡す。さらに、コードブックメモリ２３０は、ソーティング装置２２０によりソートされたコードブックと書き込むアドレスを受け取り、指定されたアドレスにコードブックを格納する。
【０１５６】
第１の演算装置２４０は、入力ベクトル集合メモリ２１０にアドレスを指定して、対応する入力ベクトルｘ（ｔ）と初期代表ベクトルの番号を受け取る。また、第１の演算装置２４０は、制御装置２７０からひずみ・アドレスの計算の指示を受け、コードブックメモリ２３０に読み込みたい代表ベクトルのアドレスを指定して、対応するデータ（代表ベクトルの値ｗｉ（ｐ），番号ｉなど）を読み込む。また、第１の演算装置２４０は、入力ベクトルと代表ベクトルとのひずみｄ（ｘ（ｔ），ｗｉ（ｐ））を計算する。そして、第１の演算装置２４０は、ひずみｄ（ｘ（ｔ），ｗｉ（ｐ））とデータ（代表ベクトルの番号と値）を判定装置２５０に渡す。また、第１の演算装置２４０は、制御装置２７０からソートの基準となった次元ｋの指示を受け、ｋ次元だけのひずみｄ（ｘｋ（ｔ）  ，ｗｉｋ（ｐ））も判定装置２５０に渡す。さらに、第１の演算装置２４０は、判定装置２５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスを計算する。なお、第１の演算装置２４０は、探索終了を示す情報finishを受けた場合は、次の入力ベクトルｘ（ｔ＋１）の符号化に取りかかる。
【０１５７】
判定装置２５０は、現在の最小のひずみｄｃｕｒｍｉｎとその代表ベクトルの番号ｍｉｎを保持しており、現在の最小のひずみｄｃｕｒｍｉｎをもつｍｉｎ番の代表ベクトルと第１の演算装置２４０により計算されたｉ番の代表ベクトルについてひずみｄ（ｘ（ｔ），ｗｉ（ｐ））を比較し、ひずみが小さい方を新しいｍｉｎ番、現在の最小のひずみｄｃｕｒｍｉｎとする。また、判定装置２５０は、制御装置２７０から判定の指示を受け、ｋ次元だけのひずみｄ（ｘｋ（ｔ）  ，ｗｉｋ（ｐ））と現在の最小のひずみｄｃｕｒｍｉｎを比較し、ｄ（ｘｋ（ｔ）  ，ｗｉｋ（ｐ））の方が大きければ、次に探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を変更し、また、ｕｐ／ｄｏｗｎ両方向とも調べ終わった場合には探索終了を示す情報finishを第１の演算装置２４０に渡し、ｄ（ｘｋ（ｔ）  ，ｗｉｋ（ｐ））の方が小さければ、同方向の次の代表ベクトルを調べる情報を第１の演算装置２４０に渡す。また、判定装置２５０は、ｕｐ／ｄｏｗｎ両方向とも調べ終わり探索終了finishになったとき、第２の演算装置２６０に入力ベクトルｘ（ｔ）、現在の最小のひずみを持つ初期代表ベクトルの番号ｍｉｎ及び最小のひずみｄｃｕｒｍｉｎを出力する。さらに、判定装置２５０は、探索終了finishになったとき、現在の最小のひずみを持つ初期代表ベクトルの番号ｍｉｎを入力ベクトルｘ（ｔ）の初期代表ベクトルとして入力ベクトル集合メモリ２１０に格納する。
【０１５８】
第２の演算装置２６０は、判定装置２５０から、入力ベクトルｘ（ｔ）  と符号化された代表ベクトルの番号ｍｉｎと入力ベクトルを符号化したときのひずみdｃｕｒｍｉｎを受け取る。そして、この第２の演算装置２６０は、代表ベクトル番号ｍｉｎに対応するデータ（分子ｗｍｉｎｎｕｍと分母ｗｍｉｎｄｅｎ、さらに部分ひずみＤｓｕｍ）の計算を次の（３０）式、（３１）及び（３２）式にしたがって行う。
【０１５９】
ｗｍｉｎｎｕｍ＋＝ｘ（ｔ）                              （３０）
ｗｍｉｎｄｅｎ＋＝１                                    （３１）
Ｄｍｉｎｓｕｍ＋＝dｃｕｒｍｉｎ                         （３２）
また、この第２の演算装置２６０は、Ｔ個の入力ベクトルに対して、符号化が終了し、上記途中計算が終了したと制御装置２７０から指示を受けたら、符号化が終了し、上記途中計算が終了したと制御装置２７０から指示を受けたら、代表ベクトル重心ｗｉ（ｐ＋１）、部分ひずみＤｉ及び平均ひずみＤの計算を次の（３３）式、（３４）及び（３５）式にしたがって行う。
【０１６０】
【数１２】
0004590747.tif 000013
【０１６１】
さらに、この第２の演算装置２６０は、制御装置２７０により、全てのデータ（分子ｗｉｎｕｍと分母ｗｉｄｅｎ、さらに部分ひずみＤｉｓｕｍ，∀ｉ）をクリアする。
【０１６２】
部分ひずみソーティング装置２６２は、第２の演算装置２６０からデータ（更新されたコードブックと部分ひずみ）をもらう。この部分ひずみソーティング装置２６２は、部分ひずみの大きさを基準にして、コードブックと部分ひずみをソートする。また、この部分ひずみソーティング装置２６２は、部分ひずみ比較装置２６４に、データ（ソートされたコードブックと部分ひずみ）を渡す。
【０１６３】
部分ひずみ比較装置２６４は、部分ひずみソーティング装置２６２から、データ（ソートされたコードブックと部分ひずみ）をもらう。この部分ひずみ比較装置２６４は、大きい部分ひずみと小さい部分ひずみを比較する。格差が大きい場合は、代表ベクトル移動装置２６６に小さい部分ひずみを持つ代表ベクトルを大きい部分ひずみを持つ代表ベクトルの近傍に移動させる情報を渡す。さらに、データ（上記移動情報とコードブック）を代表ベクトル移動装置２６６に渡す。
【０１６４】
代表ベクトル移動装置２６６は、部分ひずみ比較装置２６４から、小さい部分ひずみを持つ代表ベクトルを大きい部分ひずみを持つ代表ベクトルの近傍に移動させる情報とコードブックを受け取る。この代表ベクトル移動装置２６６は、上記移動情報に基づいて、小さい部分ひずみを持つ代表ベクトルを大きい部分ひずみを持つ代表ベクトルの近傍に移動させる。そして、この代表ベクトル移動装置２６６は、コードブックメモリ２３０にデータ（更新されたコードブックＷ（ｐ＋１））と書き込むアドレスを渡し、対応するアドレスに更新されたコードブックを書き込む。さらに、この代表ベクトル移動装置２６６は、制御装置２７０からの指示で、任意の初期コードブックをコードブックメモリ２３０に設定する。
【０１６５】
制御装置２７０は、ソーティング装置２２０、第１の演算装置２４０、判定装置２５０、第２の演算装置２６０、部分ひずみソーティング装置２６２、部分ひずみ比較装置２６４及び代表ベクトル移動装置２６６の処理フローを制御する。また、制御装置２７０は、ソーティング装置２２０にソートの基準となる次元を指定する。また、制御装置２７０は、第１の演算装置２４０に初期代表ベクトルのアドレス（又は番号）を指定し、また、ソートの基準となった次元を指示する。さらに、制御装置２７０は、第２の演算装置２６０に任意の初期コードブックの設定を指示する。
【０１６６】
このような構成のコードブック生成装置２００において、本発明では、等ひずみ原理に基づいたMin-Max Order Compare(MMOC) 操作を加えたＬＢＧアルゴリズムにより図１５に示すフローチャートにしたがってコードブック生成を行う。
【０１６７】
すなわち、このベクトル量子化器２００では、先ず、ステップ（Ｆ２０１）において、代表ベクトル初期配置を設定する。また、代表ベクトルをソートするための基準の次元ｋを指定する。さらに、ＭＭＯＣ操作のパラメータＲ，ｍを設定する。
【０１６８】
次のステップ（Ｆ２０２）では、次元ｋの代表ベクトルの値に基づいて代表ベクトルをソートする。ソートされた順番の情報については，以下の２通りのやり方が考えられる。
【０１６９】
（１）直接代表ベクトルの順番を入れ替えてしまう。代表ベクトルの番号を変更したくないときは、代表ベクトルの番号の情報を持つ構造体にして入れ替える。直接ならべ変えているので、自分より下位の代表ベクトルの番号ｌｏｗｅｒは、自分の配列の番号−１  とした配列の番号となる。また、自分より上位の代表ベクトルの番号ｕｐｐｅｒは、自分の配列の番号＋１とした配列の番号となる。
【０１７０】
（２）ソートしたときの順番を示す配列を用意する場合、各代表ベクトルが保持すべき情報は、自分より下位の代表ベクトルの番号ｌｏｗｅｒと、自分より上位の代表ベクトルの番号ｕｐｐｅｒである。
【０１７１】
次のステップ（Ｆ２０３）では、入力ベクトルｘ（ｔ）と初期の代表ベクトルｗｉ（ｐ）とのひずみの計算を行い、このひずみｄ（ｘ（ｔ），ｗｉ（ｐ））を現在の最小のひずみｄｃｕｒｍｉｎとし、番号ｉを符号化の候補として保存しておく。
【０１７２】
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｉ（ｐ））            （３６）
ｍｉｎ＝ｉ                                             （３７）
次のステップ（Ｆ２０４）では、初期の代表ベクトルｗｉ（ｐ）  の両隣の代表ベクトルの番号、すなわち、
ｌｏｗｅｒ＝下位方向の隣の代表ベクトルの番号
ｕｐｐｅｒ＝上位方向の隣の代表ベクトルの番号
を保存する。
【０１７３】
次のステップ（Ｆ２０５）では、入力ベクトルｘ（ｔ）と代表ベクトルｗｌｏｗｅｒ（ｐ）とのひずみｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｐ））の計算を行い、計算途中のｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｐ））を保存しておく。そして、このステップ（Ｆ２０５）では、計算したひずみｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｐ））が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、
ｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｐ））＜ｄｃｕｒｍｉｎ        （３８）
が成り立つか否かを判定し、この（３８）式が成り立つならば、
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｐ））        （３９）
ｍｉｎ＝ｌｏｗｅｒ                                          （４０）
とする。
【０１７４】
次のステップ（Ｆ２０６）では、下位方向の探索を続けるかどうか判断する。
このステップ（Ｆ２０６）において、もし、
ｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｐ））＞ｄｃｕｒｍｉｎ      （４１）
を満足するなら、下位方向の探索は終了で、ステップ（Ｆ２０８）へ移り、さもなければ、次のステップ（Ｆ２０７）へ進む。
【０１７５】
ステップ（Ｆ２０７）は、代表ベクトルの番号ｌｏｗｅｒの更新ステップであり、現在のｌｏｗｅｒ番の代表ベクトルの下位方向の隣の代表ベクトルの番号を新しいｌｏｗｅｒとして、ステップ（Ｆ２０５）へ戻る。
【０１７６】
ステップ（Ｆ２０８）では、入力ベクトルｘ（ｔ）とｕｐｐｅｒ番の代表ベクトルｗｕｐｐｅｒ（ｐ）とのひずみｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｐ））の計算を行い、計算途中のｄ（ｘｋ（ｔ），ｗｕｐｐｅｒｋ（ｐ））を保存しておく。
このステップ（Ｆ２０８）では、計算したひずみｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｐ））が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、
ｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｐ））＜ｄｃｕｒｍｉｎ  （４２）
が成り立つか否かを判定して、この（４２）式が成り立つならば、
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｐ））      （４３）
ｍｉｎ＝ｕｐｐｅｒ                                    （４４）
とする。
【０１７７】
次のステップ（Ｆ２０９）では、上位方向の探索を続けるかどうか判断する。
このステップ（Ｆ２０９）では、もし、
ｄ（ｘｋ（ｔ），ｗｕｐｐｅｒｋ（ｐ））＞ｄｃｕｒｍｉｎ  （４５）
を満足するなら、上位方向の探索は終了で、ステップ（Ｆ２１１）へ移り、さもなければ、次のステップ（Ｆ２１０）へ進む。
【０１７８】
ステップ（Ｆ２１０）は、代表ベクトル番号ｕｐｐｅｒの更新ステップであり、現在のｕｐｐｅｒ番の代表ベクトルの上位方向の隣の代表ベクトルの番号を新しいｕｐｐｅｒとして、ステップ（Ｆ２０８）へ戻る。
【０１７９】
次のステップ（Ｆ２１１）では、入力ベクトルの符号化と代表ベクトルの重心計算・平均ひずみの準備を行う。
【０１８０】
このステップ（Ｆ２１１）において、入力ベクトルｘ（ｔ）は、最小のひずみｄｃｕｒｍｉｎを持つ番号ｍｉｎの代表ベクトルｗｍｉｎ（ｐ）に符号化される。
【０１８１】
このステップ（Ｆ２１１）では、符号化された代表ベクトルｍｉｎの位置を更新するステップ（Ｆ２１４）において用いる分子ｗｍｉｎｎｕｍ、分母ｗｍｉｎｄｅｎ及び部分ひずみＤｍｉｎｓｕｍの計算を次の（４６）式、（４７）及び（４８）式にしたがって行っておく。
【０１８２】
ｗｍｉｎｎｕｍ＋＝ｘ（ｔ）                          （４６）
ｗｍｉｎｄｅｎ＋＝１                                  （４７）
Ｄｍｉｎｓｕｍ＋＝ｄｃｕｒｍｉｎ                      （４８）
次のステップ（Ｆ２１２）では、すべての入力ベクトルの符号化が終了したか否かを判定する。このステップ（Ｆ２１２）では、もし、ｔ＝Ｔ−１が成り立つならば、ステップ（Ｆ２１４）へ移り、さもなければ、次のステップ（Ｆ２１３）へ進む。
【０１８３】
ステップ（Ｆ２１３）では、ｔ＝ｔ＋１として、ステップ（Ｆ２０３）に戻り、次の入力ベクトルの探索をする。
【０１８４】
ステップ（Ｆ２１４）では、代表ベクトルの重心の計算と平均ひずみ及び部分ひずみの計算を行う。このステップ（Ｆ２１４）は、ＬＢＧアルゴリズムにおける代表ベクトルの重心の更新を行うステップであり、次の（４９）式で表すことができる。
【０１８５】
【数１３】
0004590747.tif 000014
【０１８６】
しかし，（４９）式の分子・分母の計算は先のステップ（Ｆ２１１）で済んでいるので、次の（５０）式の計算を行えばよい。
【０１８７】
【数１４】
0004590747.tif 000015
【０１８８】
また、部分ひずみＤｉは、次の（５１）式により計算する。
【０１８９】
【数１５】
0004590747.tif 000016
【０１９０】
そして、平均ひずみＤは次の（５２）式により計算する。
【０１９１】
【数１６】
0004590747.tif 000017
【０１９２】
次のステップ（Ｆ２１５）では、収束判定を行う。このステップ（Ｆ２１５）における収束判定条件を満たさないときは、ステップ（Ｆ２１６）へ移り、収束判定条件を満たすときは、処理を終了する。
【０１９３】
ここで、このステップ（Ｆ２１５）における収束判定条件には、次のようなものが考えられる。その他のものでも構わない。
【０１９４】
（１）代表ベクトルの更新がなくなったら終了する。
【０１９５】
（２）所望の平均ひずみ以下になったら終了する。
【０１９６】
（３）反復回数で打ち切る。
【０１９７】
次のステップ（Ｆ２１６）では、部分ひずみに応じて、代表ベクトルと部分ひずみをソートする。
【０１９８】
そして、次のステップ（Ｆ２１７）及びステップ（Ｆ２１８）において、ＭＭＯＣ操作を実行する。
【０１９９】
すなわち、ステップ（Ｆ２１７）では、図１６に示すように、大きい順にＲ個の部分ひずみＤｍａｘ［ｒ］と小さい順にＲ個の部分ひずみＤｍｉｎ［ｒ］を比較する。
【０２００】
そして、このステップ（Ｆ２１７）における比較の結果、次の（５３）式が成り立ないときは、ステップ（Ｆ２０２）へ移り、（５３）式が成り立つときはステップ（Ｆ２１８）へ進む。
【０２０１】
Ｄｍａｘ［ｒ］＞ｍ×Ｄｍｉｎ［ｒ］，（ｒ＝０，・・・，Ｒ−１）  （５３）
さらに、ステップ（Ｆ２１８）では、次の（５４）式に示すように、小さい順の部分ひずみＤｍｉｎ［ｒ］を持つ代表ベクトルｗｍｉｎ（ｐ＋１）［ｒ］を大きい順の部分ひずみＤｍａｘ［ｒ］を持つ代表ベクトルｗｍａｘ（ｐ＋１）［ｒ］の近傍に再配置して、ステップ（Ｆ２０２）へ戻る。
【０２０２】
ｗｍｉｎ（ｐ＋１）［ｒ］←ｗｍａｘ（ｐ＋１）［ｒ］＋ε      （５４）
ただし、ε（≪１）は摂動項である。一回の反復で最大Ｒ個の移動が可能となる。
【０２０３】
ＭＭＯＣ操作において、現在の反復でＭＭＯＣ操作により移動が行われる個数は前回の反復でＭＭＯＣ操作により移動が行われた個数Ｒ’よりも増えることはほとんど起きない。そこで、ＭＭＯＣ操作は常にＲ個をＭＭＯＣ操作にかけるのではなく、前回の反復での個数Ｒ’個をＭＭＯＣ操作にかけた方が効率的である。最終的にＲ’は零になってしまうので、Ｒ’＝０のときは最低限１個のＭＭＯＣ操作を行うようにする。
【０２０４】
最も単純なＲ＝１とした場合のＭＭＯＣ操作を加えたＬＢＧアルゴリズムの動作の概念図を図１７に示す。また、実際の動作を図１８に示す。
【０２０５】
ここで、図１７を用いてＭＭＣ操作を加えたＬＢＧアルゴリズムの動作を説明する。
【０２０６】
１反復目では、２番の代表ベクトルが符号化に全く使われていない、すなわち部分ひずみＤ２  ＝０である。それに対して、４番の代表ベクトルが符号化に大変よく使われており、部分ひずみＤ４  が最も大きい。そこで、２番の代表ベクトルの部分ひずみＤ２ｍｉｎと４番の代表ベクトルの部分ひずみＤ４ｍａｘを比較した場合、次の（５５）式
Ｄ４ｍａｘ＞ｍ・Ｄ２ｍｉｎ                          （５５）
が成り立つので、２番の代表ベクトルを４番の代表ベクトルの近傍に移動する。
この移動により、部分ひずみの格差が減少する。
【０２０７】
そして、ＬＢＧアルゴリズムを用いて代表ベクトルの配置を修正する。
【０２０８】
２反復目では、１反復目と同様に１番の代表ベクトルの部分ひずみＤ１が最も小さく、４番の代表ベクトルの部分ひずみＤ４が最も大きい。そこで、１番の代表ベクトルの部分ひずみＤ１ｍｉｎと４番の代表ベクトルの部分ひずみＤ４ｍａｘを比較した場合、次の（５６）式
Ｄ４ｍａｘ＞ｍ・Ｄ１ｍｉｎ                          （５６）
が成り立つとすると、１番の代表ベクトルを４番の代表ベクトルの近傍に移動する。この移動により、部分ひずみの格差がさらに減少する。
【０２０９】
そして、ＬＢＧアルゴリズムを用いて代表ベクトルの配置を修正する。
【０２１０】
３反復目では、１番の代表ベクトルの部分ひずみＤ１が最も小さく、５番の代表ベクトルの部分ひずみＤ５が最も大きい。しかし、１番の代表ベクトルの部分ひずみＤ１ｍｉｎと５番の代表ベクトルの部分ひずみＤ４ｍａｘを比較した場合、ほとんど部分ひずみの格差がないため
Ｄ４ｍａｘ＞ｍ・Ｄ１ｍｉｎ                          （５７）
が成り立たない。この代表ベクトルの配置は等ひずみ原理で示した大域的最適解の近傍の配置になっている。
【０２１１】
したがってＬＢＧアルゴリズムを数回繰り返すことで、代表ベクトルの最適な配置を得ることができる。
【０２１２】
また、本発明は、上述の（２７）式で示されるひずみの部分和が現在の最小のひずみｄｃｕｒｍｉｎと比較して大きいときは、次の代表ベクトルを探索するひずみの部分和を用いた高速化手法を組み合わせるとより一層の効果がある。
【０２１３】
ここでは、上述の図１４に示したベクトル量子化器２００の変形例として、図１９を参照して差分のみを説明する。
【０２１４】
図１９に示すベクトル量子化器２００’において、コードブックメモリ２３０は、コードブックとアドレスをソーティング装置２２０に渡す。
【０２１５】
ソーティング装置２２０は、制御装置２７０からのソートの指示とどの次元ｋを基準としてソートするかの指示を受け、コードブックメモリ２３０からコードブックのアドレスとコードブックを読み出し、指定された次元を基準としてコードブックをソートする。そして、そのソートされた代表ベクトルの順番通りに、各代表ベクトルのアドレスを並び替え、ソート順に並んだアドレスをコードブックソート表２８０に書き込む。
【０２１６】
第１の演算装置２４０は、判定装置２５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスをコードブックソート表２８０に参照しに行き、アドレスを受け取る。そして、コードブックメモリ２３０に、そのアドレスを指定して、対応するデータ（代表ベクトルの番号ｉと値ｗｉ（Ｐ）など）を読み込む。
【０２１７】
そして、コードブックソート表２８０は、ソーティング装置２２０から受け取ったアドレスを格納する。また、コードブックソート表２８０は、第１の演算装置２４０からの次の探索する代表ベクトルの参照の指示に従って、その代表ベクトルのアドレスを第１の演算装置２４０に渡す。
【０２１８】
次に、上記ベクトル量子化器２００による静止画像の符号化のシミュレーション結果について説明する。
【０２１９】
テスト画像として、Kodak PHOTOCDに入っている図２０、図２１、図２２及び図２３に示す２４枚のＢＭＰファイルに対して階調変換を行った。
【０２２０】
ＭＭ０Ｃ操作（Ｒ＝１）を加えたＬＢＧアルゴリズムによる全探索とＶＱ−ＳＳＣによる各ＢＭＰファイルに対する階調変換のシミュレーションを行ったところ、図２４に示す結果が得られた。このシミュレーション結果について、図２５の（ａ）には各ＢＭＰファイルに対する全探索による階調変換の実行時間（◆）とＶＱ−ＳＳＣによる階調変換の実行時間（●）を比較して示してあり、また、図２５の（ｂ）には実行時間の改善量として、操作（全探索）の実行時間を操作（ＶＱ−ＳＳＣ）の実行時間で規格化したときの数値を示してある。
【０２２１】
この図２４及び図２５に示す階調変換のシミュレーション結果では、ＬＢＧアルゴリズム（全探索）では平均で１９７回の反復，約２０００秒で収束しているのに対して、ＶＱ−ＳＳＣで符号化を行えば、平均で約２００秒で収束している。この実行時間は、ＶＱ−ＳＳＣなしの場合と比較して平均で１／１０．１に短縮されている。
【０２２２】
また、ＭＭＯＣ操作（Ｒ＝３０）を加えたＬＢＧアルゴリズムによる全探索とＶＱ−ＳＳＣによる各ＢＭＰファイルに対する階調変換のシミュレーションを行ったところ、図２６に示す結果が得られた。このシミュレーション結果について、図２７の（ａ）には各ＢＭＰファイルに対する全探索による階調変換の実行時間（◆）とＶＱ−ＳＳＣによる階調変換の実行時間（●）を比較して示してあり、また、図２７の（ｂ）には実行時間の改善量として、操作（全探索）の実行時間を操作（ＶＱ−ＳＳＣ）の実行時間で規格化したときの数値を示してある。
【０２２３】
この図２６及び図２７に示す階調変換のシミュレーション結果では、ＭＭＯＣ操作（Ｒ＝３０）を加えたＬＢＧアルゴリズム（全探索）では平均で２４回の反復，約２５０秒で収束しているのに対して、ＶＱ−ＳＳＣで符号化を行えば、平均で約３３．３秒で収束している。この実行時間は、ＶＱ−ＳＳＣなしの場合と比較して平均で１／７．６に短縮されている。
【０２２４】
また、本発明は、例えば図２８に示すような構成のコードブック生成装置３００により実施される。
【０２２５】
このコードブック生成装置３００は、入力端子３１０、ソーティング装置３２０、コードブックメモリ３３０、第１の演算装置３４０、判定装置３５０、第２の演算装置３６０及び制御装置３７０から構成される。
【０２２６】
このコードブック生成装置３００は、ＶＱ−ＳＳＣによる符号化を利用した競合学習を行うものであって、入力端子３１０を介して入力ベクトルｘ（ｔ）∈ＲＫが第１の演算装置３４０に入力される。
【０２２７】
ソーティング装置３２０は、制御装置３７０からのソートの指示とどの次元ｋを基準としてソートするかの指示を受け、コードブックメモリ３３０からコードブックを読み出し、指定された次元を基準としてコードブックをソートする。また、ソーティング装置３２０は、ソートしたコードブックをコードブックメモリ３３０の指定したアドレスに書き込む。
【０２２８】
コードブックメモリ３３０は、コードブックＷ（ｔ）＝｛ｗｉ（ｔ）∈ＲＫ：ｉ＝０，・・・，Ｎ−１｝を記憶しておくメモリであり、ひずみ計算・アドレス計算を行う第１の演算装置３４０からアドレスを受け取り、対応する代表ベクトルのデータ（代表ベクトルの値ｗｉ（ｔ），番号ｉ）を第１の演算装置３４０に渡す。また、コードブックメモリ３３０は、重心計算・平均ひずみ計算を行う第２の演算装置３６０から、データ（更新された代表ベクトルの値ｗｍｉｎ（ｔ＋１））及び書き込むアドレスを受け取り、対応するアドレスにコードブックが書き込まれる。また、コードブックメモリ３３０は、コードブックをソーティング装置３２０に渡す。さらに、コードブックメモリ３３０は、ソーティング装置３２０によりソートされたコードブックと書き込むアドレスを受け取り、指定されたアドレスにコードブックを格納する。
【０２２９】
第１の演算装置３４０は、入力端子３１０を介して入力ベクトルｘ（ｔ）を受け取る。この第１の演算装置３４０は、制御装置３７０からひずみ・アドレスの計算の指示を受け、コードブックメモリ３３０に読み込みたい代表ベクトルのアドレスを指定して、対応するデータ（代表ベクトルの値ｗｉ（ｔ），番号ｉなど）を読み込む。また、第１の演算装置３４０は、入力ベクトルと代表ベクトルとのひずみｄ（ｘ（ｔ），ｗｉ（ｔ））を計算する。そして、第１の演算装置３４０は、ひずみｄ（ｘ（ｔ），ｗｉ（ｔ））とデータ（代表ベクトルの番号と値）を判定装置３５０に渡す。また、第１の演算装置３４０は、制御装置３７０からソートの基準となった次元ｋの指示を受け、ｋ次元だけのひずみｄ（ｘｋ（ｔ），ｗｉｋ（ｔ））も判定装置３５０に渡す。さらに、第１の演算装置３４０は、判定装置３５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスを計算する。なお、第１の演算装置３４０は、探索終了を示す情報finishを受けた場合は、次の入力ベクトルｘ（ｔ＋１）の符号化に取りかかる。
【０２３０】
判定装置３５０は、現在の最小のひずみｄｃｕｒｍｉｎとその代表ベクトルの番号ｍｉｎを保持しており、現在の最小のひずみｄｃｕｒｍｉｎをもつｍｉｎ番の代表ベクトルと第１の演算装置３４０により計算されたｉ番の代表ベクトルについてひずみｄ（ｘ（ｔ），ｗｉ（ｔ））を比較し、ひずみが小さい方を新しいｍｉｎ番、現在の最小のひずみｄｃｕｒｍｉｎとする。また、判定装置３５０は、制御装置３７０から判定の指示を受け、ｋ次元だけのひずみｄ（ｘｋ（ｔ），ｗｉｋ（ｔ））と現在の最小のひずみｄｃｕｒｍｉｎを比較し、ｄ（ｘｋ（ｔ），ｗｉｋ（ｔ））の方が大きければ、次に探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を変更し、また、ｕｐ／ｄｏｗｎ両方向とも調べ終わった場合には探索終了を示す情報finishを第１の演算装置３４０に渡し、ｄ（ｘｋ（ｔ），ｗｉｋ（ｔ））の方が小さければ、同方向の次の代表ベクトルを調べる情報を第１の演算装置３４０に渡す。また、判定装置３５０は、ｕｐ／ｄｏｗｎ両方向とも調べ終わり探索終了finishになったとき、第２の演算装置３６０に入力ベクトルｘ（ｔ）、現在の最小のひずみを持つ代表ベクトルのデータ（番号ｍｉｎ及び値ｗｍｉｎ（ｔ））及び最小のひずみdｃｕｒｍｉｎを出力する。さらに、判定装置３５０は、探索終了finishになったとき、現在の最小のひずみを持つ代表ベクトルの番号ｍｉｎを次入力ベクトルｘ（ｔ＋１）の初期代表ベクトルとして第２の演算装置３６０に渡す。
【０２３１】
第２の演算装置３６０は、判定装置３５０から、入力ベクトルｘ（ｔ）  と現在の最小のひずみを持つ代表ベクトルのデータ（番号ｍｉｎ及び値ｗｍｉｎ（ｔ））と最小のひずみdｃｕｒｍｉｎを受け取る。そして、この第２の演算装置３６０は、平均ひずみＤｓｕｍの計算を次の（５８）式にしたがって行う。
【０２３２】
Ｄｓｕｍ＋＝dｃｕｒｍｉｎ                              （５８）
また、この第２の演算装置３６０は、代表ベクトルの値を次の（５９）式にしたがって更新する。
【０２３３】
ｗｍｉｎ（ｔ＋１）＝ｗｍｉｎ（ｔ）＋η（ｔ）［ｘ（ｔ）−ｗｍｉｎ（ｔ）］          （５９）
また、この第２の演算装置３６０は、コードブックメモリ３３０の代表ベクトル番号ｍｉｎのアドレスに更新された代表ベクトルの値ｗｍｉｎ（ｔ＋１）を書き込む。
【０２３４】
また、この演算装置３６０は、Ｔ個の入力ベクトルに対して、符号化が終了し、上記途中計算が終了したと制御装置３７０から指示を受けたら、平均ひずみＤの計算を次の(６０）式にしたがって行う。
【０２３５】
【数１７】
0004590747.tif 000018
【０２３６】
また、この第２の演算装置３６０は、制御装置３７０からの指示により、データ（平均ひずみＤｓｕｍ）をクリアする。
【０２３７】
さらに、この第２の演算装置３６０は、制御装置３７０からの指示により、任意の初期コードブックをコードブックメモリ３３０に設定する。
【０２３８】
制御装置３７０は、ソーティング装置３２０、第１の演算装置３４０、判定装置３５０及び第２の演算装置３６０の処理フローを制御する。また、制御装置３７０は、ソーティング装置３２０にソートの基準となる次元を指定する。また、制御装置３７０は、第１の演算装置３４０に初期代表ベクトルのアドレス（又は番号）を指定し、また、ソートの基準となった次元を指示する。さらに、制御装置３７０は、第２の演算装置３６０に任意の初期コードブックの設定を指示する。
【０２３９】
このような構成のコードブック生成装置３００において、本発明では、図２９のフローチャートに示す符号化アルゴリズムにしたがってコードブック生成を行う。
【０２４０】
すなわち、このコードブック生成装置３００では、先ず、ステップ（Ｆ３０１）において、代表ベクトル初期配置を設定する。また、代表ベクトルをソートするための基準の次元ｋを指定する。
【０２４１】
次のステップ（Ｆ３０２）では、次元ｋの代表ベクトルの値に基づいて代表ベクトルをソートする。２回目以降は、更新された代表ベクトルｗ（ｔ＋１）だけ、対応する場所に入るように修正する。ソートされた順番の情報については、以下の２通りのやり方が考えられる。
【０２４２】
（１）直接代表ベクトルの順番を入れ替えてしまう。代表ベクトルの番号を変更したくないときは、代表ベクトルの番号の情報を持つ構造体にして入れ替える。直接ならべ変えているので、自分より下位の代表ベクトルの番号ｌｏｗｅｒは、自分の配列の番号−１とした配列の番号となる。また、自分より上位の代表ベクトルの番号ｕｐｐｅｒは、自分の配列の番号＋１とした配列の番号となる。
【０２４３】
（２）ソートしたときの順番を示す配列を用意する場合、各代表ベクトルが保持すべき情報は、自分より下位の代表ベクトルの番号ｌｏｗｅｒと、自分より上位の代表ベクトルの番号ｕｐｐｅｒである。
【０２４４】
次のステップ（Ｆ３０３）では、入力ベクトルｘ（ｔ）と初期の代表ベクトルｗｉ（ｔ）とのひずみの計算を行い、このひずみｄ（ｘ（ｔ），ｗｉ（ｔ））を現在の最小のひずみｄｃｕｒｍｉｎとし、番号ｉを符号化の候補として保存しておく。
【０２４５】
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｉ（ｔ））              （６１）
ｍｉｎ＝ｉ                                                （６２）
次のステップ（Ｆ３０４）では、初期の代表ベクトルｗｉ（ｔ）  の両隣の代表ベクトルの番号、すなわち、
ｌｏｗｅｒ＝下位方向の隣の代表ベクトルの番号
ｕｐｐｅｒ＝上位方向の隣の代表ベクトルの番号
を保存する。
【０２４６】
次のステップ（Ｆ３０５）では、入力ベクトルｘ（ｔ）と代表ベクトルｗｌｏｗｅｒ（ｔ）とのひずみｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｔ））の計算を行い、計算途中のｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｔ））を保存しておく。そして、このステップ（Ｆ３０５）では、計算したひずみｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｔ））が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、
ｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｔ））＜ｄｃｕｒｍｉｎ    （６３）
が成り立つか否かを判定し、この（６３）式が成り立つならば、
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｔ））    （６４）
ｍｉｎ＝ｌｏｗｅｒ                                      （６５）
とする。
【０２４７】
次のステップ（Ｆ３０６）では、下位方向の探索を続けるかどうか判断する。
このステップ（Ｆ３０６）において、もし、
ｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｔ））＞ｄｃｕｒｍｉｎ      （６６）
を満足するなら、下位方向の探索は終了で、ステップ（Ｆ３０８）へ移り、さもなければ、次のステップ（Ｆ３０７）へ進む。
【０２４８】
ステップ（Ｆ３０７）は、代表ベクトルの番号ｌｏｗｅｒの更新ステップであり、現在のｌｏｗｅｒ番の代表ベクトルの下位方向の隣の代表ベクトルの番号を新しいｌｏｗｅｒとして、ステップ（Ｆ３０５）へ戻る。
【０２４９】
ステップ（Ｆ３０８）では、入力ベクトルｘ（ｔ）とｕｐｐｅｒ番の代表ベクトルｗｕｐｐｅｒ（ｔ）とのひずみｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｔ））の計算を行い、計算途中のｄ（ｘｋ（ｔ），ｗｕｐｐｅｒｋ（ｔ））を保存しておく。このステップ（Ｆ３０８）では、計算したひずみｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｔ））が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、
ｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｔ））＜ｄｃｕｒｍｉｎ            （６７）
が成り立つか否かを判定して、この（６７）式が成り立つならば、
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｔ））            （６８）
ｍｉｎ＝ｕｐｐｅｒ                                      （６９）
とする。
【０２５０】
次のステップ（Ｆ３０９）では、上位方向の探索を続けるかどうか判断する。
このステップ（Ｆ３０９）では、もし、
ｄ（ｘｋ（ｔ），ｗｕｐｐｅｒｋ（ｔ））＞ｄｃｕｒｍｉｎ      （７０）
を満足するなら、上位方向の探索は終了で、ステップ（Ｆ３１１）へ移り、さもなければ、次のステップ（Ｆ３１０）へ進む。
【０２５１】
ステップ（Ｆ３１０）は、代表ベクトル番号ｕｐｐｅｒの更新ステップであり、現在のｕｐｐｅｒ番の代表ベクトルの上位方向の隣の代表ベクトルの番号を新しいｕｐｐｅｒとして、ステップ（Ｆ３０８）へ戻る。
【０２５２】
次のステップ（Ｆ３１１）では、入力ベクトルの符号化と代表ベクトルの重心計算・平均ひずみの準備を行う。このステップ（Ｆ３１１）において、入力ベクトルｘ（ｔ）は、最小のひずみｄｃｕｒｍｉｎを持つ番号ｍｉｎの代表ベクトルｗｍｉｎ（ｔ）に符号化される。このステップ（Ｆ３１１）では、符号化された代表ベクトルの値を次の（７１）式にしたがって更新する。
【０２５３】
ｗｍｉｎ（ｔ＋１）＝ｗｍｉｎ（ｔ）＋η（ｔ）［ｘ（ｔ）−ｗｍｉｎ（ｔ）］          （７１）
また、このステップ（Ｆ３１１）では、平均ひずみＤｓｕｍの計算を次の（７２）式にしたがって行う。
【０２５４】
Ｄｓｕｍ＋＝dｃｕｒｍｉｎ                                      （７２）
そして、ｔ＝Ｔ−１が成り立つとき、平均ひずみＤの計算を次の(７３）式にしたがって行う。
【０２５５】
【数１８】
0004590747.tif 000019
【０２５６】
次のステップ（Ｆ３１２）では、すべての入力ベクトルの符号化が終了したか否かを判定する。このステップ（Ｆ３１２）では、もし、データが終わりならば処理を終了し、さもなければ、次のステップ（Ｆ３１３）へ進む。
【０２５７】
ステップ（Ｆ３１３）では、ｔ＝ｔ＋１として、ステップ（Ｆ３０２）に戻り、次の入力ベクトルの探索をする。
【０２５８】
また、本発明は、上述の（２７）式で示されるひずみの部分和が現在の最小のひずみｄｃｕｒｍｉｎと比較して大きいときは、次の代表ベクトルを探索するひずみの部分和を用いた高速化手法を組み合わせるとより一層の効果がある。
【０２５９】
ここでは、上述の図２８に示したコードブック生成装置３００の変形例として、図３０を参照して差分のみを説明する。
【０２６０】
図３０に示すコードブック生成装置３００’において、コードブックメモリ３３０は、コードブックとアドレスをソーティング装置３２０に渡す。
【０２６１】
ソーティング装置３２０は、制御装置３７０からのソートの指示とどの次元ｋを基準としてソートするかの指示を受け、コードブックメモリ３３０からコードブックのアドレスとコードブックを読み出し、指定された次元を基準としてコードブックをソートする。そして、そのソートされた代表ベクトルの順番通りに、各代表ベクトルのアドレスを並び替え、ソート順に並んだアドレスをコードブックソート表３８０に書き込む。
【０２６２】
第１の演算装置３４０は、判定装置３５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスをコードブックソート表３８０に参照しに行き、アドレスを受け取る。そして、コードブックメモリ３３０に、そのアドレスを指定して、対応するデータ（代表ベクトルの番号ｉと値ｗｉ（ｔ）など）を読み込む。
【０２６３】
そして、コードブックソート表３８０は、ソーティング装置３２０から受け取ったアドレスを格納する。また、コードブックソート表３８０は、第１の演算装置３４０からの次の探索する代表ベクトルの参照の指示に従って、その代表ベクトルのアドレスを第１の演算装置３４０に渡す。
【０２６４】
また、本発明は、例えば図３１に示すような構成のコードブック生成装置４００により実施される。
【０２６５】
このコードブック生成装置４００は、入力端子４１０、ソーティング装置４２０、コードブックメモリ４３０、第１の演算装置４４０、判定装置４５０、第２の演算装置４６０、部分ひずみソーティング装置４６２、部分ひずみ比較装置４６４、代表ベクトル移動装置４６６、制御装置４７０から構成される。
【０２６６】
このコードブック生成装置４００は、ＶＱ−ＳＳＣによる符号化を利用したＭＭＯＣ操作を加えた競合学習を行うものであって、入力端子４１０を介して入力ベクトルｘ（ｔ）∈ＲＫが第１の演算装置４４０に入力される。
【０２６７】
ソーティング装置４２０は、制御装置４７０からのソートの指示とどの次元ｋを基準としてソートするかの指示を受け、コードブックメモリ４３０からコードブックを読み出し、指定された次元を基準としてコードブックをソートする。また、ソーティング装置４２０は、ソートしたコードブックをコードブックメモリ４３０の指定したアドレスに書き込む。
【０２６８】
コードブックメモリ４３０は、コードブックＷ（ｔ）＝｛ｗｉ（ｔ）∈ＲＫ：ｉ＝０，・・・，Ｎ−１｝を記憶しておくメモリであり、ひずみ計算・アドレス計算を行う第１の演算装置４４０からアドレスを受け取り、対応する代表ベクトルのデータ（代表ベクトルの値ｗｉ（ｔ），番号ｉ）を第１の演算装置４４０に渡す。また、コードブックメモリ４３０は、代表ベクトル移動装置４６６からデータ（更新された、コードブックＷ（Ｔ））及び書き込むアドレスを受け取り、対応するアドレスにコードブックが書き込まれる。また、コードブックメモリ４３０は、代表ベクトル計算・平均ひずみ計算・部分ひずみ計算を行う第２の演算装置４６０から、データ（更新された代表ベクトルの値ｗｍｉｎ（ｔ＋１））及び書き込むアドレスを受け取り、対応するアドレスにコードブックが書き込まれる。また、コードブックメモリ４３０は、コードブックをソーティング装置４２０に渡す。さらに、コードブックメモリ４３０は、ソーティング装置４２０によりソートされたコードブックと書き込むアドレスを受け取り、指定されたアドレスにコードブックを格納する。
【０２６９】
第１の演算装置４４０は、入力端子４１０を介して入力ベクトルｘ（ｔ）を受け取る。この第１の演算装置４４０は、制御装置４７０からひずみ・アドレスの計算の指示を受け、コードブックメモリ４３０に読み込みたい代表ベクトルのアドレスを指定して、対応するデータ（代表ベクトルの値ｗｉ（ｔ），番号ｉなど）を読み込む。また、第１の演算装置４４０は、入力ベクトルと代表ベクトルとのひずみｄ（ｘ（ｔ），ｗｉ（ｔ））を計算する。そして、第１の演算装置４４０は、ひずみｄ（ｘ（ｔ），ｗｉ（ｔ））とデータ（代表ベクトルの番号と値）を判定装置４５０に渡す。また、第１の演算装置４４０は、制御装置４７０からソートの基準となった次元ｋの指示を受け、ｋ次元だけのひずみｄ（ｘｋ（ｔ），ｗｉｋ（ｔ））も判定装置４５０に渡す。さらに、第１の演算装置４４０は、判定装置４５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスを計算する。なお、第１の演算装置４４０は、探索終了を示す情報finishを受けた場合は、次の入力ベクトルｘ（ｔ＋１）の符号化に取りかかる。
【０２７０】
判定装置４５０は、現在の最小のひずみｄｃｕｒｍｉｎとその代表ベクトルの番号ｍｉｎを保持しており、現在の最小のひずみｄｃｕｒｍｉｎをもつｍｉｎ番の代表ベクトルと第１の演算装置４４０により計算されたｉ番の代表ベクトルについてひずみｄ（ｘ（ｔ），ｗｉ（ｔ））を比較し、ひずみが小さい方を新しいｍｉｎ番、現在の最小のひずみｄｃｕｒｍｉｎとする。また、判定装置４５０は、制御装置４７０から判定の指示を受け、ｋ次元だけのひずみｄ（ｘｋ（ｔ），ｗｉｋ（ｔ））と現在の最小のひずみｄｃｕｒｍｉｎを比較し、ｄ（ｘｋ（ｔ），ｗｉｋ（ｔ））の方が大きければ、次に探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を変更し、また、ｕｐ／ｄｏｗｎ両方向とも調べ終わった場合には探索終了を示す情報finishを第１の演算装置４４０に渡し、ｄ（ｘｋ（ｔ），ｗｉｋ（ｔ））の方が小さければ、同方向の次の代表ベクトルを調べる情報を第１の演算装置４４０に渡す。また、判定装置４５０は、ｕｐ／ｄｏｗｎ両方向とも調べ終わり探索終了finishになったとき、第２の演算装置４６０に入力ベクトルｘ（ｔ）、現在の最小のひずみを持つ代表ベクトルのデータ（番号ｍｉｎ及び値ｗｍｉｎ（ｔ））及び最小のひずみdｃｕｒｍｉｎを出力する。さらに、判定装置４５０は、探索終了finishになったとき、現在の最小のひずみを持つ代表ベクトルの番号ｍｉｎを次入力ベクトルｘ（ｔ＋１）の初期代表ベクトルとして第２の演算装置４６０に渡す。
【０２７１】
第２の演算装置４６０は、判定装置４５０から、入力ベクトルｘ（ｔ）  と現在の最小のひずみを持つ代表ベクトルのデータ（番号ｍｉｎ及び値ｗｍｉｎ（ｔ））と最小のひずみdｃｕｒｍｉｎを受け取る。そして、この第２の演算装置４６０は、代表ベクトル番号ｍｉｎに対応するデータ（部分ひずみＤｍｉｎｓｕｍ）の計算を次の（７４）式にしたがって行う。
【０２７２】
Ｄｍｉｎｓｕｍ＋＝dｃｕｒｍｉｎ                                （７４）
また、この第２の演算装置４６０は、代表ベクトルの値を次の（７５）式にしたがって更新する。
【０２７３】
ｗｍｉｎ（ｔ＋１）＝ｗｍｉｎ（ｔ）＋η（ｔ）［ｘ（ｔ）−ｗｍｉｎ（ｔ）］        （７５）
また、この第２の演算装置４６０は、コードブックメモリ３３０の代表ベクトル番号ｍｉｎのアドレスに更新された代表ベクトルの値ｗｍｉｎ（ｔ＋１）を書き込む。
【０２７４】
また、この演算装置４６０は、Ｔ個の入力ベクトルに対して、符号化が終了し、上記途中計算が終了したと制御装置４７０から指示を受けたら、次の（７６）式及び（７７）式にしたがって、部分ひずみＤｉ及び平均ひずみＤを計算する。
【０２７５】
【数１９】
0004590747.tif 000020
【０２７６】
さらに、この第２の演算装置４６０は、制御装置４７０により、全てのデータ（部分ひずみＤｉｓｕｍ，∀ｉ）をクリアする。
【０２７７】
部分ひずみソーティング装置４６２は、第２の演算装置４６０からデータ（更新されたコードブックと部分ひずみ）をもらう。また、この部分ひずみソーティング装置４６２は、コードブックメモリ４３０からアドレスを指定して対応するデータ（コードブックＷ（Ｔ））をもらう。この部分ひずみソーティング装置４６２は、部分ひずみの大きさを基準にして、コードブックと部分ひずみをソートする。また、この部分ひずみソーティング装置４６２は、部分ひずみ比較装置４６４に、データ（ソートされたコードブックと部分ひずみ）を渡す。
【０２７８】
部分ひずみ比較装置４６４は、部分ひずみソーティング装置４６２から、データ（ソートされたコードブックと部分ひずみ）をもらう。この部分ひずみ比較装置４６４は、大きい部分ひずみと小さい部分ひずみを比較する。格差が大きい場合は、代表ベクトル移動装置４６６に小さい部分ひずみを持つ代表ベクトルを大きい部分ひずみを持つ代表ベクトルの近傍に移動させる情報を渡す。さらに、データ（上記移動情報とコードブックＷ（Ｔ））を代表ベクトル移動装置４６６に渡す。
【０２７９】
代表ベクトル移動装置４６６は、部分ひずみ比較装置４６４から、小さい部分ひずみを持つ代表ベクトルを大きい部分ひずみを持つ代表ベクトルの近傍に移動させる情報とコードブックＷ（Ｔ）を受け取る。この代表ベクトル移動装置４６６は、上記移動情報に基づいて、小さい部分ひずみを持つ代表ベクトルを大きい部分ひずみを持つ代表ベクトルの近傍に移動させる。そして、この代表ベクトル移動装置４６６は、コードブックメモリ４３０にデータ（更新されたコードブックＷ（Ｔ））と書き込むアドレスを渡し、対応するアドレスに更新されたコードブックを書き込む。さらに、この代表ベクトル移動装置４６６は、制御装置４７０からの指示で、任意の初期コードブックをコードブックメモリ４３０に設定する。
【０２８０】
制御装置４７０は、ソーティング装置４２０、第１の演算装置４４０、判定装置４５０、第２の演算装置４６０、部分ひずみソーティング装置４６２、部分ひずみ比較装置４６４及び代表ベクトル移動装置４６６の処理フローを制御する。また、制御装置４７０は、代表ベクトル移動装置４６６に任意の初期コードブックの設定を指示する。また、制御装置４７０は、ソーティング装置４２０にソートの基準となる次元を指定する。さらに、制御装置４７０は、第１の演算装置４４０に初期代表ベクトルのアドレス（又は番号）を指定し、また、ソートの基準となった次元を指示する。
【０２８１】
このような構成のコードブック生成装置４００において、本発明では、等ひずみ原理に基づいたMin-Max Order Compare(MMOC) 操作を加えた競合学習により図３２に示すフローチャートにしたがってコードブック生成を行う。
【０２８２】
すなわち、このコードブック生成装置４００では、先ず、ステップ（Ｆ４０１）において、代表ベクトル初期配置を設定する。また、代表ベクトルをソートするための基準の次元ｋを指定する。さらに、ＭＭＯＣ操作のパラメータＲ，ｍを設定する。
【０２８３】
次のステップ（Ｆ４０２）では、次元ｋの代表ベクトルの値に基づいて代表ベクトルをソートする。２回目以降は、更新された代表ベクトルｗ（ｔ＋１）だけ、対応する場所に入るように修正する。ソートされた順番の情報については、以下の２通りのやり方が考えられる。
【０２８４】
（１）直接代表ベクトルの順番を入れ替えてしまう。代表ベクトルの番号を変更したくないときは、代表ベクトルの番号の情報を持つ構造体にして入れ替える。直接ならべ変えているので、自分より下位の代表ベクトルの番号ｌｏｗｅｒは、自分の配列の番号−１とした配列の番号となる。また、自分より上位の代表ベクトルの番号ｕｐｐｅｒは、自分の配列の番号＋１とした配列の番号となる。
【０２８５】
（２）ソートしたときの順番を示す配列を用意する場合、各代表ベクトルが保持すべき情報は、自分より下位の代表ベクトルの番号ｌｏｗｅｒと、自分より上位の代表ベクトルの番号ｕｐｐｅｒである。
【０２８６】
次のステップ（Ｆ４０３）では、入力ベクトルｘ（ｔ）と初期の代表ベクトルｗｉ（ｔ）とのひずみの計算を行い、このひずみｄ（ｘ（ｔ），ｗｉ（ｔ））を現在の最小のひずみｄｃｕｒｍｉｎとし、番号ｉを符号化の候補として保存しておく。
【０２８７】
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｉ（ｔ））                    （７８）
ｍｉｎ＝ｉ                                               （７９）
次のステップ（Ｆ４０４）では、初期の代表ベクトルｗｉ（ｔ）  の両隣の代表ベクトルの番号、すなわち、
ｌｏｗｅｒ＝下位方向の隣の代表ベクトルの番号
ｕｐｐｅｒ＝上位方向の隣の代表ベクトルの番号
を保存する。
【０２８８】
次のステップ（Ｆ４０５）では、入力ベクトルｘ（ｔ）と代表ベクトルｗｌｏｗｅｒ（ｔ）とのひずみｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｔ））の計算を行い、計算途中のｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｔ））を保存しておく。そして、このステップ（Ｆ４０５）では、計算したひずみｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｔ））が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、
ｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｔ））＜ｄｃｕｒｍｉｎ            （８０）
が成り立つか否かを判定し、この（８０）式が成り立つならば、
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｌｏｗｅｒ（ｔ））            （８１）
ｍｉｎ＝ｌｏｗｅｒ                                      （８２）
とする。
【０２８９】
次のステップ（Ｆ４０６）では、下位方向の探索を続けるかどうか判断する。
このステップ（Ｆ４０６）において、もし、
ｄ（ｘｋ（ｔ），ｗｌｏｗｅｒｋ（ｔ））＞ｄｃｕｒｍｉｎ      （８３）
を満足するなら、下位方向の探索は終了で、ステップ（Ｆ４０８）へ移り、さもなければ、次のステップ（Ｆ４０７）へ進む。
【０２９０】
ステップ（Ｆ４０７）は、代表ベクトルの番号ｌｏｗｅｒの更新ステップであり、現在のｌｏｗｅｒ番の代表ベクトルの下位方向の隣の代表ベクトルの番号を新しいｌｏｗｅｒとして、ステップ（Ｆ４０５）へ戻る。
【０２９１】
ステップ（Ｆ４０８）では、入力ベクトルｘ（ｔ）とｕｐｐｅｒ番の代表ベクトルｗｕｐｐｅｒ（ｔ）とのひずみｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｔ））の計算を行い、計算途中のｄ（ｘｋ（ｔ），ｗｕｐｐｅｒｋ（ｔ））を保存しておく。このステップ（Ｆ４０８）では、計算したひずみｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｔ））が現在の最小のひずみｄｃｕｒｍｉｎより小さいか否か、すなわち、
ｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｔ））＜ｄｃｕｒｍｉｎ            （８４）
が成り立つか否かを判定して、この（８４）式が成り立つならば、
ｄｃｕｒｍｉｎ＝ｄ（ｘ（ｔ），ｗｕｐｐｅｒ（ｔ））            （８５）
ｍｉｎ＝ｕｐｐｅｒ                                      （８６）
とする。
【０２９２】
次のステップ（Ｆ４０９）では、上位方向の探索を続けるかどうか判断する。
このステップ（Ｆ４０９）では、もし、
ｄ（ｘｋ（ｔ），ｗｕｐｐｅｒｋ（ｔ））＞ｄｃｕｒｍｉｎ      （８７）
を満足するなら、上位方向の探索は終了で、ステップ（Ｆ４１１）へ移り、さもなければ、次のステップ（Ｆ４１０）へ進む。
【０２９３】
ステップ（Ｆ４１０）は、代表ベクトル番号ｕｐｐｅｒの更新ステップであり、現在のｕｐｐｅｒ番の代表ベクトルの上位方向の隣の代表ベクトルの番号を新しいｕｐｐｅｒとして、ステップ（Ｆ４０８）へ戻る。
【０２９４】
次のステップ（Ｆ４１１）では、入力ベクトルの符号化と代表ベクトルの更新・平均ひずみの準備を行う。  このステップ（Ｆ４１１）において、入力ベクトルｘ（ｔ）は、最小のひずみｄｃｕｒｍｉｎを持つ番号ｍｉｎの代表ベクトルｗｍｉｎ（ｔ）に符号化される。このステップ（Ｆ４１１）では、符号化された代表ベクトルの値を次の（８８）式にしたがって更新する。
【０２９５】
ｗｍｉｎ（ｔ＋１）＝ｗｍｉｎ（ｔ）＋η（ｔ）［ｘ（ｔ）−ｗｍｉｎ（ｔ）］          （８８）
また、このステップ（Ｆ４１１）では、部分ひずみＤｍｉｎｓｕｍの計算を次の（８９）式にしたがって行う。
【０２９６】
Ｄｍｉｎｓｕｍ＋＝dｃｕｒｍｉｎ                                （８９）
そして、ｔ＝Ｔ−１が成り立つとき、部分ひずみＤｉ及び平均ひずみＤの計算を行う。また、部分ひずみＤｉは、次の（９０）式により計算する。
【０２９７】
【数２０】
0004590747.tif 000021
【０２９８】
そして、平均ひずみＤは次の（９１）式により計算する。
【０２９９】
【数２１】
0004590747.tif 000022
【０３００】
次のステップ（Ｆ４１２）では、すべての入力ベクトルの符号化が終了したか否かを判定する。このステップ（Ｆ４１２）では、もし、データが終わりならば処理を終了し、さもなければ、次のステップ（Ｆ４１３）へ進む。
【０３０１】
ステップ（Ｆ４１３）は、ＭＭＯＣモードに入るか否かを判定するステップであり、ｔ＝Ｔ−１が成り立たないときには、ステップ（Ｆ４１４）に進み、ｔ＝Ｔ−１が成り立つときには、ステップ（Ｆ４１５）に進む。
【０３０２】
ステップ（Ｆ４１４）では、ｔ＝ｔ＋１として、ステップ（Ｆ４０２）に戻り、次の入力ベクトルの探索をする。
【０３０３】
また、ステップ（Ｆ４１５）では、部分ひずみに応じて、代表ベクトルと部分ひずみをソートする。
【０３０４】
そして、次のステップ（Ｆ４１６）及びステップ（Ｆ４１７）において、ＭＭＯＣ操作を実行する。
【０３０５】
すなわち、ステップ（Ｆ４１６）では、図１６に示すように、大きい順にＲ個の部分ひずみＤｍａｘ［ｒ］と小さい順にＲ個の部分ひずみＤｍｉｎ［ｒ］を比較する。
【０３０６】
そして、このステップ（Ｆ３０６）における比較の結果、次の（９２）式が成り立ないときは、ステップ（Ｆ４０２）へ戻り、（９２）式が成り立つときはステップ（Ｆ４１７）へ進む。
【０３０７】
Ｄｍａｘ［ｒ］＞ｍ×Ｄｍｉｎ［ｒ］，（ｒ＝０，・・・，Ｒ−１）  （９２）
さらに、ステップ（Ｆ４１７）では、次の（９３）式に示すように、小さい順の部分ひずみＤｍｉｎ［ｒ］を持つ代表ベクトルｗｍｉｎ（Ｔ）［ｒ］を大きい順の部分ひずみＤｍａｘ［ｒ］を持つ代表ベクトルｗｍａｘ（Ｔ）［ｒ］の近傍に再配置して、ステップ（Ｆ４０２）へ戻る。
【０３０８】
ｗｍｉｎ（Ｔ）［ｒ］←ｗｍａｘ（Ｔ）［ｒ］＋ε            （９３）
ただし、ε（≪１）は摂動項である。一回の反復で最大Ｒ個の移動が可能となる。
【０３０９】
また、本発明は、上述の（２７）式で示されるひずみの部分和が現在の最小のひずみｄｃｕｒｍｉｎと比較して大きいときは、次の代表ベクトルを探索するひずみの部分和を用いた高速化手法を組み合わせるとより一層の効果がある。
【０３１０】
ここでは、上述の図３１に示したコードブック生成装置４００の変形例として、図３３を参照して差分のみを説明する。
【０３１１】
図３３に示すコードブック生成装置４００’において、コードブックメモリ４３０は、コードブックとアドレスをソーティング装置４２０に渡す。
【０３１２】
ソーティング装置４２０は、制御装置４７０からのソートの指示とどの次元ｋを基準としてソートするかの指示を受け、コードブックメモリ４３０からコードブックのアドレスとコードブックを読み出し、指定された次元を基準としてコードブックをソートする。そして、そのソートされた代表ベクトルの順番通りに、各代表ベクトルのアドレスを並び替え、ソート順に並んだアドレスをコードブックソート表４８０に書き込む。
【０３１３】
第１の演算装置４４０は、判定装置４５０から、判定結果により探索する代表ベクトルの方向を示すｕｐ／ｄｏｗｎの情報を受け、次の探索する代表ベクトルのアドレスをコードブックソート表４８０に参照しに行き、アドレスを受け取る。そして、コードブックメモリ４３０に、そのアドレスを渡し、対応するデータ（代表ベクトルの番号ｉと値ｗｉ（ｔ）など）を読み込む。
【０３１４】
そして、コードブックソート表４８０は、ソーティング装置４２０から受け取ったアドレスを格納する。また、コードブックソート表４８０は、第１の演算装置４４０からの次の探索する代表ベクトルの参照の指示に従って、その代表ベクトルのアドレスを第１の演算装置４４０に渡す。
【０３１５】
【発明の効果】
以上説明したように、本発明によれば、一部分の代表ベクトルを探索するだけで全探索と同じ代表ベクトルを高速に選択することができる。また、本発明によれば、従来方法と比較して、記憶するメモリが少なくて済む。また、本発明によれば、従来方法と比較して、ソートはいずれかの一次元についてのみ行えばよいので、時間が短縮できる。また、本発明によれば、従来方法と比較して、ソートされた代表ベクトルの順番を記憶しておくメモリが必要ない。また、本発明によれば、従来方法と比較して、代表ベクトルの探索が済んだかどうかを示すフラグのメモリが必要なく、入力ベクトルごとにフラグをクリアする時間も必要ない。
さらに、本発明によれば、次の探索する代表ベクトルの決め方は、一意に決まる。
【図面の簡単な説明】
【図１】本発明を適用したコードブック生成装置の構成を示すブロック図である。
【図２】上記コードブック生成装置において実行されるけるＶＱ−ＳＳＣを用いたＬＢＧアルゴリズム処理を示すフローチャートである。
【図３】全探索による代表ベクトルの探索の例を示す図である。
【図４】上記符号化アルゴリズム（ＶＱ−ＳＳＣ）による代表ベクトルの探索例（探索０）を示す図である。
【図５】同じく代表ベクトルの探索例（探索１）を示す図である。
【図６】同じく代表ベクトルの探索例（探索２）を示す図である。
【図７】同じく代表ベクトルの探索例（探索３）を示す図である。
【図８】同じく代表ベクトルの探索例（探索４）を示す図である。
【図９】同じく代表ベクトルの探索例（探索５）を示す図である。
【図１０】同じく代表ベクトルの探索例（探索６）を示す図である。
【図１１】上記符号化アルゴリズム（ＶＱ−ＳＳＣ）の探索範囲を示す図である。
【図１２】図１に示したコードブック生成装置の変形例の構成を示すブロック図である。
【図１３】等ひずみ原理を例示する図である。
【図１４】本発明を適用したコードブック生成装置の構成を示すブロック図である。
【図１５】上記コードブック生成装置おいてＶＱ−ＳＳＣを用いた等ひずみ原理に基づいたMin-Max Order Compare(MMOC) 操作を加えたＬＢＧアルゴリズムを示すフローチャートである。
【図１６】上記ＬＢＧアルゴリズムにいて、ソートされた昇順の部分ひずみと降順の部分ひずみの比較処理を模式的に示す図である。
【図１７】Ｒ＝１とした場合のＭＭＯＣ操作を加えたＬＢＧアルゴリズムの動作の概念図である。
【図１８】Ｒ＝１とした場合のＭＭＯＣ操作を加えたＬＢＧアルゴリズムの実際の動作を模式的に示す図である。
【図１９】図１４に示したベクトル量子化器の変形例の構成を示すブロック図である。
【図２０】  Kodak PHOTOCD（２４枚）の６枚を示す図である。
【図２１】  Kodak PHOTOCD（２４枚）の６枚を示す図である。
【図２２】  Kodak PHOTOCD（２４枚）の６枚を示す図である。
【図２３】  Kodak PHOTOCD（２４枚）の６枚を示す図である。
【図２４】ＭＭＯＣ操作（Ｒ＝１）を加えたＬＢＧアルゴリズムによる全探索とＶＱ−ＳＳＣによるKodak PHOTOCDに対する階調変換のシミュレーション結果を示す図である。
【図２５】上記シミュレーション結果について、全探索による階調変換の実行時間（◆）とＶＱ−ＳＳＣによる階調変換の実行時間（●）の比較及び実行時間の改善量を示す図である。
【図２６】ＭＭＯＣ操作（Ｒ＝３０）を加えたＬＢＧアルゴリズムによる全探索とＶＱ−ＳＳＣによるKodak PHOTOCDに対する階調変換のシミュレーション結果を示す図である。
【図２７】上記シミュレーション結果について、全探索による階調変換の実行時間（◆）とＶＱ−ＳＳＣによる階調変換の実行時間（●）の比較及び実行時間の改善量を示す図である。
【図２８】本発明を適用したコードブック生成装置を示すブロック図である。
【図２９】上記コードブック生成装置において実行されるＶＱ−ＳＳＣを用いた競合学習処理を示すフローチャートである。
【図３０】図２９に示したコードブック生成装置の変形例の構成を示すブロック図である。
【図３１】本発明を適用したコードブック生成装置を示すブロック図である。
【図３２】上記コードブック生成装置において実行されるＶＱ−ＳＳＣを用いた競合学習処理を示すフローチャートである。
【図３３】図３１に示したコードブック生成装置の変形例の構成を示すブロック図である。
【図３４】ベクトル量子化の概念図である。
【符号の説明】
１００，１００’，２００，２００’  コードブック生成装置、１１０，２１０  入力ベクトル集合メモリ、１２０，２２０  ソーティング装置、１３０，２３０  コードブックメモリ、１４０，２４０  第１の演算装置、１５０，２５０判定装置、１６０，２６０  第２の演算装置、１７０，２７０  制御装置、１８０，２８０  コードブックソート表、２６２  部分ひずみソーティング装置、２６４  部分ひずみ比較装置、２６６  代表ベクトル移動装置、３００，３００’，４００，４００’  コードブック生成装置、１１０，２１０  入力ベクトル集合メモリ、１２０，２２０  ソーティング装置、３１０，４１０  入力端子、３２０，４２０  ソーティング装置、３３０，４３０  コードブックメモリ、３４０，４４０  第１の演算装置、３５０，４５０  判定装置、３６０，４６０  第２の演算装置、３７０，４７０  制御装置、３８０，４８０  コードブックソート表、４６２  部分ひずみソーティング装置、４６４  部分ひずみ比較装置、４６６  代表ベクトル移動装置
【図１】
0004590747.tif 000023
【図２】
0004590747.tif 000024
【図３】
0004590747.tif 000025
【図４】
0004590747.tif 000026
【図５】
0004590747.tif 000027
【図６】
0004590747.tif 000028
【図７】
0004590747.tif 000029
【図８】
0004590747.tif 000030
【図９】
0004590747.tif 000031
【図１０】
0004590747.tif 000032
【図１１】
0004590747.tif 000033
【図１２】
0004590747.tif 000034
【図１３】
0004590747.tif 000035
【図１４】
0004590747.tif 000036
【図１５】
0004590747.tif 000037
【図１６】
0004590747.tif 000038
【図１７】
0004590747.tif 000039
【図１８】
0004590747.tif 000040
【図１９】
0004590747.tif 000041
【図２０】
0004590747.tif 000042
【図２１】
0004590747.tif 000043
【図２２】
0004590747.tif 000044
【図２３】
0004590747.tif 000045
【図２４】
0004590747.tif 000046
【図２５】
0004590747.tif 000047
【図２６】
0004590747.tif 000048
【図２７】
0004590747.tif 000049
【図２８】
0004590747.tif 000050
【図２９】
0004590747.tif 000051
【図３０】
0004590747.tif 000052
【図３１】
0004590747.tif 000053
【図３２】
0004590747.tif 000054
【図３３】
0004590747.tif 000055
【図３４】
0004590747.tif 000056