(57)【特許請求の範囲】
【請求項１】
コードブックを構成する複数のベクトルと上記各ベクトルに個々に対応した識別符号との配置を決定するコードブック配置方法において、
上記複数のベクトル間の距離を求め、
上記複数のベクトル間の距離の平均距離を元に上記複数のベクトル間の距離を、長い距離についてはより長く、短い距離についても長くするように変更した距離尺度を求め、
上記距離尺度に基づいて、当該距離尺度が短い各ベクトルに対して、上記識別符号を構成する複数ビットのうちの１ビットが異なる各識別符号を割り当てて配置するために、シミュレーテッドアニーリング法を用いる
ことを特徴とするコードブック配置方法。
【請求項２】
コードブックを構成する複数のベクトルと上記各ベクトルに個々に対応した識別符号との配置を決定するコードブック配置装置において、
上記複数のベクトル間の距離を求め、上記複数のベクトル間の距離の平均距離を元に上記複数のベクトル間の距離を、長い距離についてはより長く、短い距離についても長くするように変更した距離尺度を求める演算手段と、
上記各ベクトルに対してそれぞれ識別符号を割り当て配置する割り当て配置手段とを有し、
上記割り当て配置手段は、上記距離尺度に基づいて、当該距離尺度が短い各ベクトルに対して、上記識別符号を構成する複数ビットのうちの１ビットが異なる各識別符号を割り当てて配置するために、シミュレーテッドアニーリング法を用いる
ことを特徴とするコードブック配置装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、音声や画像の符号化において多く用いられているコードブック（符号帳）の配置方法及び装置に関し、特に、コードブックを構成するコードベクトルの識別符号（インデクス）を非保護にするような場合に好適なコードブック配置方法及び装置に関する。
【０００２】
【従来の技術】
音声や画像の符号化においては、信号をコードブックを用いてモデル化することにより、それら音声や画像の情報量を圧縮することが多い。
【０００３】
以下に、例えばいわゆるベクトル量子化によって画像の情報量を圧縮する場合を例に挙げて、上記コードブックを用いた圧縮技法について簡単に説明する。
【０００４】
画像のベクトル量子化では、入力画像をブロックに分割し、各ブロックの画素を成分とする１つのベクトルに対して量子化を行う。具体的には、予め定めたブロックに対し、発生頻度が大きいと思われる代表的な画像パターンに対応するコードベクトルを幾つか定めておき、それらに識別符号（インデクス）をつけて符号器内に記録しておく。このコードベクトルと識別符号との対応表をコードブック（符号帳）という。符号器側では、画像が入力されると、ブロック毎にその画像パターンに最も似たコードベクトルをコードブックから検索し、その識別符号を送出する。一方、受信側では、符号器と同じコードブックを用意しておき、受け取った識別符号から該当するコードベクトルを選び出してブロックの画像を復元する。一例として、４×４画素のブロックに対して１０２４個のコードベクトルを用意するものとすると、その識別にはブロック毎１０ビットの符号を送信すればよい。入力画像のデータ量が８ビット／画素とすれば、１０／（４×４×８）≒１／１３のデータ圧縮が達成されることになる。
【０００５】
ここで、効率のよいベクトル量子化を実現するには、コードブックの設計が問題になる。一般的には、入力画像を代表するような複数のテスト画像を定め、これらに対して符号化歪みを最小にするようなコードベクトルの組を逐次的に求める方法をとる。この代表的な手法にいわゆるＬＢＧアルゴリズムがある。このようにして最適なコードブックを用意しても実際の入力画像に対しては、しばしば代表ベクトルの不整合を生ずる。この問題を改善する方法として、原画像信号に対して、ブロック毎にその画素値の分散で正規化したり、離散コサイン変換（ＤＣＴ）による変換を行ったり、或いは波形成分と振幅成分を分離するなど、信号の統計的性質の変動を小さくするような変換処理を施した後、ベクトル量子化を行う方法などがある。
【０００６】
【発明が解決しようとする課題】
ところで、音声や画像信号を上述したようにコードブックでモデル化することによって情報量を圧縮する技法には多々あるが、例えば伝送時における伝送ビット数の関係（例えば伝送可能なビット数の制限など）から、知覚的影響が少なかったり重要度の比較的低いコードベクトルの識別符号（インデクス）を、非保護とするような技法が存在する。
【０００７】
ところが、このように知覚的影響が少なかったり重要度の比較的低いコードベクトルの識別符号を非保護とする技法を採用した場合、当該識別符号は様々な要因により発生するビット誤りに対して弱くなり、その結果として最終的に復元される信号の品質低下を招く虞がある。すなわち、例えば識別符号を伝送する際に当該識別符号にビット誤りが発生すると、受信器側では当該識別符号が本来指すべきコードベクトルとは異なるコードベクトルを指し示すことになるが、このときコードブック内の各コードベクトルが不規則に配置されていると、当該誤った識別符号が指すコードベクトルは本来のコードベクトルとは全く無関係なコードベクトルになる虞があり、この場合、当該受信器側で復元された信号は本来の信号とは全く異なるものとなってしまい、その結果、意図しない信号品質の低下を招いてしまう。
【０００８】
そこで、本発明はこのような状況に鑑みてなされたものであり、コードベクトルの識別符号を非保護にするような場合において、識別符号のビット誤りに対する影響を少なくし、信号品質の低下を防止することが可能なコードブック配置方法及び装置を提供することを目的とする。
【０００９】
【課題を解決するための手段】
本発明に係るコードブック配置方法は、コードブックを構成する複数のベクトルと上記各ベクトルに個々に対応した識別符号（インデクス）との配置を決定するコードブック配置方法において、複数のベクトル間の距離を求め、上記複数のベクトル間の距離の平均距離を元に上記複数のベクトル間の距離を、長い距離についてはより長く、短い距離についても長くするように変更した距離尺度を求め、距離尺度に基づいて、当該距離尺度が短い各ベクトルに対して、識別符号を構成する複数ビットのうちの１ビットが異なる各識別符号を割り当てて配置するために、シミュレーテッドアニーリング法を用いることにより、上述した課題を解決する。
【００１０】
本発明に係るコードブック配置装置は、コードブックを構成する複数のベクトルと上記各ベクトルに個々に対応した識別符号（インデクス）との配置を決定するコードブック配置装置において、複数のベクトル間の距離を求め、上記複数のベクトル間の距離の平均距離を元に上記複数のベクトル間の距離を、長い距離についてはより長く、短い距離についても長くするように変更した距離尺度を求める演算手段と、各ベクトルに対してそれぞれ識別符号を割り当て配置する割り当て配置手段とを有し、割り当て配置手段は、距離尺度に基づいて、当該距離尺度が短い各ベクトルに対して、識別符号を構成する複数ビットのうちの１ビットが異なる各識別符号を割り当てて配置するために、シミュレーテッドアニーリング法を用いることにより、上述した課題を解決する。
【００１１】
【発明の実施の形態】
本発明の好ましい実施の形態について、図面を参照しながら説明する。
【００１２】
本実施の形態の内容説明の前に、コードブックを構成する一般的なコードベクトルについて簡単に説明する。
【００１３】
コードブックは、一般に種々のベクトル（コードベクトル）の集まりで構成され、そのサイズは２のＮ乗に相当するものが多い。ここで、コードブック内の例えばｎ番目のコードベクトルＶｎは、式（１）のように表すことができる。同様に、コードブック内の例えばｍ番目のコードベクトルＶｍは、式（２）のように表すことができる。なお、式（１）及び式（２）中のＤはベクトルの要素数である。
【００１４】
Ｖｎ＝（ｖｎ(0)，ｖｎ(1)，・・・，ｖｎ(D-1)）          （１）
Ｖｍ＝（ｖｍ(0)，ｖｍ(1)，・・・，ｖｍ(D-1)）          （２）
上記ｎ番目のコードベクトルＶｎとｍ番目のコードベクトルＶｍとの差のベクトルＶｄは、式（３）のように表すことができる。
【００１５】
0003882344.tif 000002
なお、コードベクトルの要素毎に重要度が異なる場合、上記差のベクトルＶｄは、式（４）に示す重みベクトルＶｗを導入して、式（５）のように表すこともできる。
【００１６】
0003882344.tif 000003
さらに、上記差のベクトルＶｄの距離ｄは、式（６）のように表すことができる。
【００１７】
【数１】
0003882344.tif 000004
【００１８】
さてここで、上記差のベクトルＶｄの距離ｄが小さい場合、上記ｎ番目のコードベクトルＶｎとｍ番目のコードベクトルＶｍは、一般的に相似であると考えられる。
【００１９】
したがって、このように差のベクトルＶｄの距離ｄが小さく、コードベクトルＶｎとコードベクトルＶｍが相似であるような場合には、例えば上記ｎ番目コードベクトルＶｎを指示するための識別符号のうちの何れかの１ビットに誤りが発生して、上記ｍ番目のコードベクトルＶｍを指示する識別符号になってしまい、本来ならばコードベクトルＶｎとなるべきところがコードベクトルＶｍになったとしても、その影響は少ないと考えることができる。
【００２０】
そこで、本発明実施の形態では、識別符号に１ビット誤りが発生したとしても、当該誤った識別符号にて指示されるコードベクトルが、本来の識別符号（誤りがなかったときの識別符号）にて指示されるコードベクトルと相似したコードベクトルとなるように、各コードベクトルと各識別符号とを対応付けるようにしている。すなわち本実施の形態は、例えば前述したように知覚的影響が少なかったり重要度の比較的低いコードベクトルの識別符号を非保護とする技法を採用した場合のように、当該非保護とされた識別符号に誤りが発生し易い環境に対して好適なものであり、互いに距離が近い相似の各コードベクトルに対して、それぞれ例えば１ビット異なる識別符号を予め割り当てておくことにより、伝送時などに識別符号に１ビット誤りが発生したとしても、相似したコードベクトルが得られるようになり、その結果として信号の品質劣化を低減可能にしている。
【００２１】
以下、本発明実施の形態のコードブック配置方法及び装置について、具体的に説明する。
【００２２】
例えば、サイズが２のＮ乗のＮビットのコードブックを想定し、予め全てのコードベクトル間の距離ｄを計算し、それら各コードベクトル間の距離ｄを、式（７）に示すように配列ｄ（ｍ，ｎ）にセットする。なお、ｍとｎは、０≦ｍ≦２のＮ乗−１、０≦ｎ≦２のＮ乗−１、ｍ≠ｎである。
【００２３】
【数２】
0003882344.tif 000005
【００２４】
また、初期条件の配列として、当該コードブック内の個々のコードベクトルの識別符号（インデクス）ｉを、式（８）に示すように配列ａ(i)にセットする。なお、ｉは０≦ｉ≦２のＮ乗−１である。
【００２５】
ａ(i)＝ｉ                                              （８）
ここで、当該コードブックにおいて、１ビット誤った識別符号が指すコードベクトルと、誤っていない識別符号が指すコードベクトルとの距離を小さくするということは、このコードブック内の個々のコードベクトルそれぞれに対して、１ビット誤った識別符号が指すコードベクトルとの距離の和ｓｄ(i)を小さくすることと解することができる。
【００２６】
また、ある識別符号ｉと、当該識別符号ｉに対して１ビットのみ異なる識別符号ｊとの関係は、式（９）のように表すことができる。
【００２７】
ｊ＝ｉ^（１<<ｋ）    （０≦ｋ≦Ｎ−１）                （９）
さらに、識別符号ｉに対応する配列ａ(i)と距離の和ｓｄ(i)との関係は、式（１０）のように表すことができる。
【００２８】
【数３】
0003882344.tif 000006
【００２９】
この距離の和ｓｄ(i)を短くする方法の一例としては、識別符号ｉと別の識別符号ｉ’とを交換した場合に、それら識別符号が示すコードベクトル間の合計距離が小さくなるなら当該交換を行い、そうでないならば交換しないというような方法が考えられる。式（１１），式（１２），式（１３）には、別の識別符号ｉ’に対する上記距離の和ｓｄ(i')、識別符号を交換した時の上記距離の和ｓｄ'(i)，ｓｄ'(i')を示す。
【００３０】
【数４】
0003882344.tif 000007
【００３１】
ところで、場合によっては、上記別の識別符号ｉ’がｉ’＝ｉ^（１<<ｋ）になることがあるので、そのような配列ｄ( )は省くようにすることもできる。当該配列ｄ( )を省くと、式（１４）を満たすとき、上記交換を行うことになる。
【００３２】
ｓｄ(i)＋ｓｄ(i')＞ｓｄ'(i)＋ｓｄ'(i')                （１４）
上記交換では、識別符号ｉの配列ａ(i)を識別符号ｉ’の配列ａ(i')に、識別符号ｉ’の配列ａ(i')を識別符号ｉの配列ａ(i)にセットする。
【００３３】
ここで、通常は、上記識別符号ｉ，ｉ’共に乱数を発生させてそのなかから選択し、多数の試行を経ても上記式（１４）が満たされなくなったらば中止し、得られた配列ａ(i)をコードベクトルの配列とする。
【００３４】
しかし、この方法では、局所的な収束点に陥ることがままあるので、いわゆるシミュレーテッドアニーリング（焼き鈍し）法を用いることが望ましい。なお、シミュレーテッドアニーリング法とは、例えば鉄を溶解した時に温度を急激に下げると分子配列が不規則になるが、徐々に温度を下げると分子配列が規則的になることを計算に応用したものである。以下、このシミュレーテッドアニーリング法を採用した計算について説明する。
【００３５】
上記式（１４）において、左辺と右辺の差ｄｅを式（１５）のようにして求める。
【００３６】
ｄｅ＝ｓｄ'(i)＋ｓｄ'(i')−｛ｓｄ(i)＋ｓｄ(i')｝        （１５）
この式（１５）より、ｄｅ＜０ならば無条件で識別符号を交換するが、ｄｅ≧０でも、ある値ｔ（ｔはシミュレーテッドアニーリング法の温度に相当する）に対しては０〜１の乱数ｒについて式（１６）が満たされるならば識別符号を交換する。
【００３７】
ｒ＜ｅｘｐ（−ｄｅ／ｔ）
なお、式（１６）の右辺ｅｘｐ（−ｄｅ／ｔ）は、シミュレーテッドアニーリング法の熱伝導式に相当するものである。
【００３８】
そして、式（１５）、式（１６）の誤行を多数回繰り返した後、値ｔを下げ、また繰り返すという技法で、これを多数回の試行を経ても、ある値ｔで交換が成立しなくなった時、その配列ａ(i)をコードベクトルの配列とする。
【００３９】
例として、Ｎ＝７、つまり２のＮ乗＝１２８のサイズのコードブックで要素数を２とし、それらをＸ(i)，Ｙ(i)としたときのものを、図１に示す。また、図２には、図１の各コードベクトルより、アニーリングを使用したものと使用しないものの平均距離の収束過程を示す。この図２から、アニーリングをすると、より低い収束点を得られることが判る。
【００４０】
ところで、式（１５）では、各識別符号についてのコードベクトルの距離の総和をとることにより最適化をしている。この場合、長い距離と短い距離が含まれていると、全体として平均化されてしまうが、例えば、コードベクトル間の距離が長くなるような識別符号がビット誤りによって選択されてしまうと、後の復号結果に悪影響を及ぼすことがないとは限らない。
【００４１】
そこで、本実施の形態では、実際の距離より長い距離については長く、短い距離についても長くするような距離尺度ｄ’を導入する。
【００４２】
実際には、平均的距離ｄａを元に、式（１７）、式（１８）のようにする。
【００４３】
ｄ’＝ｇ（ｄ−ｄａ）＋ｄａ      （ｄ≦ｄａ）            （１７）
ｄ’＝（ｄ−ｄａ）／ｇ＋ｄａ    （ｄ＞ｄａ）            （１８）
これを図示すると図３のようになる。ここで、平均的距離ｄａは本来の距離ｄを用いた収束時の平均距離（図３の例では０．２２０）で、勾配が０≦ｇ＜１（図３の例では０．８）とする。
【００４４】
この距離尺度ｄ’を元に、各コードベクトルについて平均距離と最大距離を図１のコードブックを元に求め、ソートしたものを図４及び図５に示す。
【００４５】
この図４及び図５の実線は本来の距離を、点線は式（１７），式（１８）より求めた距離尺度であり、これら図４及び図５から、距離変更したものの方が全体的に平均化され、最悪値の良化が実現されていることが判る。なお、図中Ｘ軸の数字は平均あるいは最大距離の短い順にソートされた個々のコードベクトルに対応する。
【００４６】
図６にはコードブック配置方法の実際の手順を表すフローチャートを示し、図７にはコードブック配置装置のブロック構成を示し、以下に、これら図６及び図７を用いて本実施の形態のコードブック配置方法及び装置の動作説明を行う。
【００４７】
図６及び図７において、ステップＳＴ１では、距離計算部１で全てのコードベクトル間の距離を前記式（７）より計算する。また、距離尺度を導入する場合、式（１７），式（１８）より計算する。
【００４８】
ステップＳＴ２では、配列初期化部２で、前記式（８）より配列ａ(i)を初期化する。
【００４９】
ステップＳＴ３では、値ｔの初期値ｔ0をセットする。なお、初期値ｔ0は、コードブックの個々のコードベクトル間の距離を元に決められるが、この値により収束点が変化することも多いので、より良い収束点を得るには何種類かのｔ0でテストすることが必要になることもある。
【００５０】
ステップＳＴ４では、コードブックサイズNCB＝２のＮ乗を元に、試行回数NTEST、その値ｔの式（１４），式（１６）が成立した回数の上限NLIMITを決定する。ここで、Ｃ0，Ｃ1は定数で、例えばＣ0＝１００，Ｃ1＝１０である。なお、ステップＳＴ３、ステップＳＴ４は各種設定部３にて設定される。
【００５１】
ステップＳＴ５ではカウンタｎを０に初期化し、ステップＳＴ６ではカウンタｓ，ｍを０に初期化する。
【００５２】
ステップＳＴ７では、符号発生部４において、テストされる識別符号ｉ，ｉ’を０〜NCB−１の範囲でランダムに発生する。
【００５３】
ステップＳＴ８では、距離差分計算部５にて距離差分ｄｅを式（１５）より求める。
【００５４】
ステップＳＴ９では、交換判定部６にて式（１４），式（１６）が成立するか否かを判定し、何れか一方が成立するならステップＳＴ１０に進み、逆に成立しないならばステップＳＴ１２に進む。
【００５５】
ステップＳＴ１０では、符号交換部７にて配列ａ(i)とａ(i')の内容を交換し、次のステップＳＴ１１でカウンタＳの値を１増やす。
【００５６】
また、ステップＳＴ１２では、カウンタＳの値が成立上限NLIMITに達したことを成立回数検出部８にて検出したならば、ステップＳＴ１５に進み、一方、カウンタＳが成立上限LIMITに達していないならば、ステップＳＴ１３に進む。
【００５７】
ステップＳＴ１３では、カウンタｍを１増やす。
【００５８】
次のステップＳＴ１４では、試行回数検出部９にてカウンタｍが試行回数NTESTに達したか否かの判定を行い、達したことを検出したならばステップＳＴ１５に進み、達していないならばステップＳＴ６に戻る。
【００５９】
ステップＳＴ１５では、無成立判定部１０にて成立回数のカウンタＳの値が０か否かの判定を行い、０ならばステップＳＴ１９に進み、０でないならばステップＳＴ１６に進む。
【００６０】
ステップＳＴ１６では、カウンタｎの値を１増やす。
【００６１】
次のステップＳＴ１７では、終了判定部１１が値ｔの制御回数の上限NENDにカウンタｎの値が達したか否かを判定し、達したならばステップＳＴ１９に進み、達していないならばステップＳＴ１８に進む。
【００６２】
ステップＳＴ１８では、値ｔ制御部１２において値ｔに定数Ｃ2（０＜Ｃ2＜１）を乗じて下げた値を新しいｔとして、ステップＳＴ６に戻る。
【００６３】
ステップＳＴ１９では、コードブック再配置部１３にて配列ａ(i)に従ってコードブックを再配置し、処理を終了する。
【００６４】
上述したように、本実施の形態によれば、信号等の符号化の際のコードブックによるモデル化において、重要度の低いとされるコードベクトルの識別符号が非保護ビットとされた場合に、起こり得るビット誤りに対して誤って選択されたコードベクトルが本来のコードベクトルと相似したものになるように、少なくとも１ビット誤りを想定してコードブックの再配置を行うようにしているので、例えば伝送時などに識別符号に１ビット誤りが発生したとしても、相似したコードベクトルが得られるようになり、その結果として信号の品質劣化が低減される。
【００６５】
【発明の効果】
以上の説明で明らかなように、本発明のコードブック配置方法及び装置においては、相似度が高い各単位情報に対して、少なくとも１ビットのみが異なる各識別符号を割り当てて配置することにより、例えば伝送時に識別符号を非保護にするような場合において、識別符号のビット誤りに対する影響を少なくでき、信号品質の低下を防止できる。
【図面の簡単な説明】
【図１】１２８ビットのサイズのコードブックで要素数を２とした場合のコードベクトルのテストポイントの説明に用いる図である。
【図２】アニーリングを使用したものと使用しないものの平均距離の収束の説明に用いる図である。
【図３】距離の変更の説明に用いる図である。
【図４】コードベクトルのソートによる平均的距離の説明に用いる図である。
【図５】コードベクトルのソートによる最大距離の説明に用いる図である。
【図６】本実施の形態のコードブック配置方法の手順を示すフローチャートである。
【図７】本実施の形態のコードブック配置装置のブロック図である。
【符号の説明】
１  距離計算部、  ２  配列初期化部、  ３  各種設定部、  ４  符号発生部、  ５  距離差分計算部、  ６  交換判定部、  ７  符号交換部、  ８  成立回数検知部、  ９  試行回数検知部、  １０  無成立判定部、  １１  終了判定部、  １２  値ｔ制御部、  １３  コードブック再配置部
【図１】
0003882344.tif 000008
【図２】
0003882344.tif 000009
【図３】
0003882344.tif 000010
【図４】
0003882344.tif 000011
【図５】
0003882344.tif 000012
【図６】
0003882344.tif 000013
【図７】
0003882344.tif 000014