JPS6340507B2 - - Google Patents
Info
- Publication number
- JPS6340507B2 JPS6340507B2 JP10051682A JP10051682A JPS6340507B2 JP S6340507 B2 JPS6340507 B2 JP S6340507B2 JP 10051682 A JP10051682 A JP 10051682A JP 10051682 A JP10051682 A JP 10051682A JP S6340507 B2 JPS6340507 B2 JP S6340507B2
- Authority
- JP
- Japan
- Prior art keywords
- vector
- output
- distortion
- output vector
- input
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/008—Vector quantisation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/90—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using coding techniques not provided for in groups H04N19/10-H04N19/85, e.g. fractals
- H04N19/94—Vector quantisation
Landscapes
- Engineering & Computer Science (AREA)
- Multimedia (AREA)
- Signal Processing (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Image Processing (AREA)
- Analogue/Digital Conversion (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
- Transmission Systems Not Characterized By The Medium Used For Transmission (AREA)
Description
【発明の詳細な説明】
この発明は、入力信号の振幅確率密度関数に従
つて最小歪となる様に信号系列を量子化する量子
化器に関するものである。
つて最小歪となる様に信号系列を量子化する量子
化器に関するものである。
従来のこの種量子化器は入力信号を１サンプル
毎に対応する出力信号レベルに量子化するスカラ
ー量子化によるものであつた。
毎に対応する出力信号レベルに量子化するスカラ
ー量子化によるものであつた。
第１図に従来のスカラー量子化器を示す。図
中、１は順次入力される信号系列x1，x2，…，
xK（Ｋは整数）、２はスカラー量子化器、３は入
力信号系列１の１サンプル毎に対応した量子化レ
ベルに変換された出力信号系列y1，y2，…yKであ
る。
中、１は順次入力される信号系列x1，x2，…，
xK（Ｋは整数）、２はスカラー量子化器、３は入
力信号系列１の１サンプル毎に対応した量子化レ
ベルに変換された出力信号系列y1，y2，…yKであ
る。
今、入力信号系列１の振幅確率密度が原点を中
心としてGauss分布をとるものとする。この場合
入力信号系列１と出力信号系列２の歪を最小とす
る従来のスカラー量子化特性は、第２図に示す如
く、原点から離れるに従つて量子化レベルが粗く
なる。しかし、入力信号系列１の各サンプル間に
相関がある場合、従来の如き、１サンプル毎に最
小歪となる量子化を施こしても出力信号系列２は
最適に量子化されたことにならない。
心としてGauss分布をとるものとする。この場合
入力信号系列１と出力信号系列２の歪を最小とす
る従来のスカラー量子化特性は、第２図に示す如
く、原点から離れるに従つて量子化レベルが粗く
なる。しかし、入力信号系列１の各サンプル間に
相関がある場合、従来の如き、１サンプル毎に最
小歪となる量子化を施こしても出力信号系列２は
最適に量子化されたことにならない。
この発明は従来のスカラー量子化器による量子
化損失を除去するためになされたもので、入力信
号系列を所定サンプル毎にブロツク化して、まと
めて出力信号系列のブロツクに高速に変換するベ
クトル量子化器を提供することを目的としてい
る。
化損失を除去するためになされたもので、入力信
号系列を所定サンプル毎にブロツク化して、まと
めて出力信号系列のブロツクに高速に変換するベ
クトル量子化器を提供することを目的としてい
る。
次に、ベクトル量子化の原理について説明す
る。相関のある入力信号系列Ｋ個（但しＫは２以
上の整数）からなるブロツク、すなわち入力ベク
トルＸ＝｛x1，x2，…，xK｝に対し、これに対応
する出力信号系列Ｋ個からなる１ブロツク、すな
わち出力ベクトルをyi＝｛yi1，yi2，…，yiK｝とす
る。
る。相関のある入力信号系列Ｋ個（但しＫは２以
上の整数）からなるブロツク、すなわち入力ベク
トルＸ＝｛x1，x2，…，xK｝に対し、これに対応
する出力信号系列Ｋ個からなる１ブロツク、すな
わち出力ベクトルをyi＝｛yi1，yi2，…，yiK｝とす
る。
今、すべての入力ベクトルＸを含むＫ次元ユー
クリツド信号空間RKを仮定する。このとき、ベ
クトル量子化は出力ベクトルの有限個のセツトＹ
＝｛y1，y2，…yN｝へのRKのマツピングとして定
義される。RKのＮ個の分割を各R1，R2，…RNと
すると、ベクトル量子化Ｑは次の如く表わされ
る。
クリツド信号空間RKを仮定する。このとき、ベ
クトル量子化は出力ベクトルの有限個のセツトＹ
＝｛y1，y2，…yN｝へのRKのマツピングとして定
義される。RKのＮ個の分割を各R1，R2，…RNと
すると、ベクトル量子化Ｑは次の如く表わされ
る。
Ｑ：RK→Ｙ
ここで、
Ri＝Q-1（yi）＝｛Ｘ∈RK：Ｑ（Ｘ）＝yi｝
N
Ｕi=1
Ri＝RK，Ri∩Rj＝０（ｉ≠ｊ）
結局、ベクトル量子化Ｑは符号化Ｃと復号化Ｄ
の継続接続とみなすことができる。この時、符号
化ＣはRKのＹのインデツクスセツトＪ＝｛１，
２，…Ｎ｝へのマツピングであり、復号化ＤはＪ
からＹへのマツピングである。
の継続接続とみなすことができる。この時、符号
化ＣはRKのＹのインデツクスセツトＪ＝｛１，
２，…Ｎ｝へのマツピングであり、復号化ＤはＪ
からＹへのマツピングである。
Ｃ：RK→Ｊ Ｄ：Ｊ→Ｙ Ｑ＝Ｄ・Ｃ
前記ベクトル量子化は、入力ベクトルＸの元に
相関がある場合、効率の良い量子化が実現でき
る。第３図に２次元のベクトル量子化における信
号空間と出力ベクトルの配列を示す。入力信号x1
とx2が相関があるとき、振幅分布はx1＝x2の近傍
に集中する。それ故、入力ベクトルと出力ベクト
ルの誤差ベクトルの総和が最小となる分割Riとそ
の代表点（例えば重心）yiがクラスタリングによ
り第３図の例の如く最適化される。このとき分割
Riに含まれる入力ベクトルは出力ベクトルyiにベ
クトル量子化される。第３図においてx1，x2＞０
としている。
相関がある場合、効率の良い量子化が実現でき
る。第３図に２次元のベクトル量子化における信
号空間と出力ベクトルの配列を示す。入力信号x1
とx2が相関があるとき、振幅分布はx1＝x2の近傍
に集中する。それ故、入力ベクトルと出力ベクト
ルの誤差ベクトルの総和が最小となる分割Riとそ
の代表点（例えば重心）yiがクラスタリングによ
り第３図の例の如く最適化される。このとき分割
Riに含まれる入力ベクトルは出力ベクトルyiにベ
クトル量子化される。第３図においてx1，x2＞０
としている。
第４図にこの発明に係るベクトル量子化器の符
号化部、第５図に復号化部の一実施例である構成
図を示す。
号化部、第５図に復号化部の一実施例である構成
図を示す。
図中、４は入力ベクトルＸ、５は入力ベクトル
レジスタ、６は出力ベクトルのコードテーブルア
ドレスカウンタ、７は出力ベクトルコードテーブ
ル、８は出力ベクトルレジスタ、９は減算器、１
０は絶対値補正器、１１は最大要素歪検出器、１
２は最小歪出力ベクトル検出器、１３は最小歪と
なる出力ベクトルのインデツクスラツチからなる
出力回路１４は最小歪となる出力ベクトルのイン
デツクス信号、１５は出力ベクトルである。
レジスタ、６は出力ベクトルのコードテーブルア
ドレスカウンタ、７は出力ベクトルコードテーブ
ル、８は出力ベクトルレジスタ、９は減算器、１
０は絶対値補正器、１１は最大要素歪検出器、１
２は最小歪出力ベクトル検出器、１３は最小歪と
なる出力ベクトルのインデツクスラツチからなる
出力回路１４は最小歪となる出力ベクトルのイン
デツクス信号、１５は出力ベクトルである。
次にこの発明に係るベクトル量子化器の動作に
ついて説明する。
ついて説明する。
第３図に示す符号化部において、信号源から入
力する信号系列はＫ個毎にブロツキングされＫ次
元入力ベクトルＸ＝｛x1，x2，…，xK｝（各元は
サンプル値に対応する。）として入力ベクトルレ
ジスタ５にラツチされる。この時点において、あ
らかじめ入力信号の確率モデルあるいは標準画像
データから、例えば文献Y.Linde，A.Buzo，and
R.M.Gray“An algorithm for vector quantizer
design”IEEE Trans.Commun.，vol.COM―28，
PP.84―95.Jan.1980に示されているクラスタリン
グを用いて求められた最小歪となる出力ベクトル
yiのセツトＹ＝｛y1，y2，…yN｝が書き込まれた
出力ベクトルコードテーブル７から、順次出力ベ
クトルyiを読み出す。なお、クラスタリングとは
一般には、対象について類似したものをを集めて
クラスタ（群）を作り、各クラスタ内の類似性と
各クラスタ間の相違に基き対象の構造を記述する
手法における一つの操作である。出力ベクトルyi
はｉ＝１，２，…Ｎの順に出力ベクトルレジスタ
８に送られ、入力ベクトルＸと各元毎に減算器９
と絶対値補正器１０を通して差の絶対値（以下要
素歪Dilとして定義する）を計算する。この要素
歪Dil＝｛Di1，Di2，…DiK｝の最大要素歪検出器１
１にて検出する。最大要素歪検出演算は要素歪
Dilの各元間でトーナメント方式で比較すればよ
い。次に最小歪出力ベクトル検出器１２でDi＝
｛D1，D2，…DN｝のうち最小歪Ｄを検出する。こ
れはコードテーブルアドレスカウンタ６がｉ＝
１，２，…Ｎと順次変化するタイミングで過去の
最小歪を入れかえながら比較検出される。
力する信号系列はＫ個毎にブロツキングされＫ次
元入力ベクトルＸ＝｛x1，x2，…，xK｝（各元は
サンプル値に対応する。）として入力ベクトルレ
ジスタ５にラツチされる。この時点において、あ
らかじめ入力信号の確率モデルあるいは標準画像
データから、例えば文献Y.Linde，A.Buzo，and
R.M.Gray“An algorithm for vector quantizer
design”IEEE Trans.Commun.，vol.COM―28，
PP.84―95.Jan.1980に示されているクラスタリン
グを用いて求められた最小歪となる出力ベクトル
yiのセツトＹ＝｛y1，y2，…yN｝が書き込まれた
出力ベクトルコードテーブル７から、順次出力ベ
クトルyiを読み出す。なお、クラスタリングとは
一般には、対象について類似したものをを集めて
クラスタ（群）を作り、各クラスタ内の類似性と
各クラスタ間の相違に基き対象の構造を記述する
手法における一つの操作である。出力ベクトルyi
はｉ＝１，２，…Ｎの順に出力ベクトルレジスタ
８に送られ、入力ベクトルＸと各元毎に減算器９
と絶対値補正器１０を通して差の絶対値（以下要
素歪Dilとして定義する）を計算する。この要素
歪Dil＝｛Di1，Di2，…DiK｝の最大要素歪検出器１
１にて検出する。最大要素歪検出演算は要素歪
Dilの各元間でトーナメント方式で比較すればよ
い。次に最小歪出力ベクトル検出器１２でDi＝
｛D1，D2，…DN｝のうち最小歪Ｄを検出する。こ
れはコードテーブルアドレスカウンタ６がｉ＝
１，２，…Ｎと順次変化するタイミングで過去の
最小歪を入れかえながら比較検出される。
すなわち入力ベクトルＸと出力ベクトルyiの最
小歪Ｄは Ｄ＝ Mio ｉ〔 Max ｌ｜yil−xl｜〕 として求められる。このときのインデツクスｉを
符号出力回路１３にてとり込み、インデツクス信
号ｉ１４として符号化部出力とする。
小歪Ｄは Ｄ＝ Mio ｉ〔 Max ｌ｜yil−xl｜〕 として求められる。このときのインデツクスｉを
符号出力回路１３にてとり込み、インデツクス信
号ｉ１４として符号化部出力とする。
次に、第５図に示す復号化部では、前記インデ
ツクス信号ｉ１４をインデツクスラツチからなる
符号入力回路１６にとり込み、これをアドレス信
号として出力ベクトルyiが記憶された出力ベクト
ルコードテーブル７を参照すれば、インデツクス
信号ｉに対応する出力ベクトルyiが出力信号１５
として得られる。
ツクス信号ｉ１４をインデツクスラツチからなる
符号入力回路１６にとり込み、これをアドレス信
号として出力ベクトルyiが記憶された出力ベクト
ルコードテーブル７を参照すれば、インデツクス
信号ｉに対応する出力ベクトルyiが出力信号１５
として得られる。
ここで、この発明によるベクトル量子化器にお
ける符号化部のインデツクス信号１４を伝送ある
いはメモリへの記録に用いれば高能率符号化が実
現できる。
ける符号化部のインデツクス信号１４を伝送ある
いはメモリへの記録に用いれば高能率符号化が実
現できる。
この発明によるベクトル量子化器の符号化効率
ηは入力信号系列x1，x2，…xKさらにＮ＝2Mと
するとη＝Ｍ／Ｋビツト／サンプルとなる。それ
故、本ベクトル量子化器は相関のあるサンプル系
列をブロツク化して符号化する画像・音声等のデ
ータの高能率符号化に利用できる。
ηは入力信号系列x1，x2，…xKさらにＮ＝2Mと
するとη＝Ｍ／Ｋビツト／サンプルとなる。それ
故、本ベクトル量子化器は相関のあるサンプル系
列をブロツク化して符号化する画像・音声等のデ
ータの高能率符号化に利用できる。
更に、この発明において、最小歪の計算に出力
ベクトルコードテーブル参照方式、ベクトル演算
の並列化およびミニマツクス近似歪検出方式を採
用しているので高速ベクトル量子化器が実現でき
る。
ベクトルコードテーブル参照方式、ベクトル演算
の並列化およびミニマツクス近似歪検出方式を採
用しているので高速ベクトル量子化器が実現でき
る。
更にマイクロプロセツサの導入により本ベクト
ル演算を各元毎にシーケンシヤル処理してもよい
ことは勿論である。
ル演算を各元毎にシーケンシヤル処理してもよい
ことは勿論である。
また出力ベクトルコードテーブルを本構造とし
て入力ベクトルとのミニマツクス照合を木探索方
式としてもよい。
て入力ベクトルとのミニマツクス照合を木探索方
式としてもよい。
更にカラー画像信号の如く３チヤンネルの並列
信号系列があるときチヤンネル間にまたがつて信
号系列をブロツキングして入力ベクトルとしても
よいことは勿論である。
信号系列があるときチヤンネル間にまたがつて信
号系列をブロツキングして入力ベクトルとしても
よいことは勿論である。
以上のようにこの発明によると入力信号系列を
ブロツク化してまとめてベクトル化し、ミニマツ
クス近似にて最小歪となる出力信号系列のブロツ
クへ変換するように符号化器と復号化器の継続接
続としてベクトル量子化器を構成したので、入力
信号の高能率符号化が実現できる利点がある。
ブロツク化してまとめてベクトル化し、ミニマツ
クス近似にて最小歪となる出力信号系列のブロツ
クへ変換するように符号化器と復号化器の継続接
続としてベクトル量子化器を構成したので、入力
信号の高能率符号化が実現できる利点がある。
第１図は従来のスカラー量子化器の説明図、第
２図は従来のスカラー量子化器の量子化特性の説
明図、第３図はこの発明によるベクトル量子化器
の量子化特性の説明図、第４図はこの発明による
ベクトル量子化器の符号化部の一実施例を示す構
成図、第５図はこの発明によるベクトル量子化器
の復号化部の一実施例を示す構成図である。 図中、２はスカラー量子化器、５は入力ベクト
ルレジスタ、６はコードテーブルアドレスカウン
タ、７は出力ベクトルコードテーブル、８は出力
ベクトルレジスタ、９は減算器、１０は絶対値補
正器、１１は最大要素歪検出器、１２は最小歪出
力ベクトル検出器、１３は符号出力回路である。
なお図中、同一符号は同一又は相当部分を示す。
２図は従来のスカラー量子化器の量子化特性の説
明図、第３図はこの発明によるベクトル量子化器
の量子化特性の説明図、第４図はこの発明による
ベクトル量子化器の符号化部の一実施例を示す構
成図、第５図はこの発明によるベクトル量子化器
の復号化部の一実施例を示す構成図である。 図中、２はスカラー量子化器、５は入力ベクト
ルレジスタ、６はコードテーブルアドレスカウン
タ、７は出力ベクトルコードテーブル、８は出力
ベクトルレジスタ、９は減算器、１０は絶対値補
正器、１１は最大要素歪検出器、１２は最小歪出
力ベクトル検出器、１３は符号出力回路である。
なお図中、同一符号は同一又は相当部分を示す。
Claims (1)
- １ 入力信号系列をＫ個（但しＫは２以上の整
数）ブロツク化した入力ベクトルのＫ次元ユーク
リツド信号空間における分布に対し、最小歪とな
るように信号空間を分割してその代表点となる複
数個の出力ベクトルを記憶した出力ベクトルコー
ドテーブルと、前記出力ベクトルコードテーブル
から順次読み出される出力ベクトルと入力ベクト
ルとの各元の差を求める減算器と、前記減算器の
出力を各元毎に絶対値に変換して各元毎の歪を求
める絶対値補正器と、前記各元毎に比較された歪
の最大値を求める最大要素歪検出器と、前記入力
ベクトルと順次照合される出力ベクトルの各元毎
の歪の最大値が最小となる出力ベクトルを検出す
る最小歪出力ベクトル検出器と、前記最小歪とな
る出力ベクトルに対応する前記出力ベクトルコー
ドテーブルのアドレスを符号化して出力する符号
出力回路とからなる符号化部と、前記出力ベクト
ルコードテーブルアドレスの符号化出力を復号化
して入力ベクトルに最小歪となるように対応する
出力ベクトルを読み出す復号化部とを備えたこと
を特徴とするベクトル量子化器。
Priority Applications (8)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57100516A JPS58218244A (ja) | 1982-06-11 | 1982-06-11 | ベクトル量子化器 |
| DE3382796T DE3382796T2 (de) | 1982-06-11 | 1983-06-10 | Vorrichtung zur Zwischenbildkodierung. |
| EP91107886A EP0444717B1 (en) | 1982-06-11 | 1983-06-10 | Vector quantizer |
| DE3382806T DE3382806T2 (de) | 1982-06-11 | 1983-06-10 | Vektorquantisierer |
| EP90117175A EP0411675B1 (en) | 1982-06-11 | 1983-06-10 | Interframe coding apparatus |
| DE8383105713T DE3382478D1 (de) | 1982-06-11 | 1983-06-10 | Vektor-groessenwandler. |
| EP83105713A EP0097858B1 (en) | 1982-06-11 | 1983-06-10 | Vector quantizer |
| US06/503,474 US4560977A (en) | 1982-06-11 | 1983-06-13 | Vector quantizer |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP57100516A JPS58218244A (ja) | 1982-06-11 | 1982-06-11 | ベクトル量子化器 |
Related Child Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP16210189A Division JPH0256119A (ja) | 1989-06-23 | 1989-06-23 | ベクトル量子化器の符号化回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS58218244A JPS58218244A (ja) | 1983-12-19 |
| JPS6340507B2 true JPS6340507B2 (ja) | 1988-08-11 |
Family
ID=14276110
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP57100516A Granted JPS58218244A (ja) | 1982-06-11 | 1982-06-11 | ベクトル量子化器 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS58218244A (ja) |
-
1982
- 1982-06-11 JP JP57100516A patent/JPS58218244A/ja active Granted
Non-Patent Citations (1)
| Title |
|---|
| IEEE TRANSACTIONS ON COMMUNICATIONS=1980 * |
Also Published As
| Publication number | Publication date |
|---|---|
| JPS58218244A (ja) | 1983-12-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3978478B2 (ja) | 推定画素値により固定速度のブロック単位の画像圧縮を行うための装置及び方法 | |
| EP0097858B1 (en) | Vector quantizer | |
| KR101678223B1 (ko) | 멀티미디어 서명 코딩 및 디코딩 | |
| US6411231B1 (en) | Encoding, decoding, and probability estimation method | |
| US4560977A (en) | Vector quantizer | |
| US5818877A (en) | Method for reducing storage requirements for grouped data values | |
| US4558350A (en) | Vector quantizer | |
| US5481627A (en) | Method for rectifying channel errors in a transmitted image signal encoded by classified vector quantization | |
| US20030103573A1 (en) | Method and apparatus for encoding and decoding data | |
| CN112398484A (zh) | 一种编码方法及相关设备 | |
| KR20220045920A (ko) | 머신비전을 위한 영상의 처리 방법 및 장치 | |
| RU2313174C2 (ru) | Адаптивный способ и система для отображения значений параметров в индексы кодовых слов | |
| Zheng et al. | Design of vector quantization codebooks using a genetic algorithm | |
| EP0457362B1 (en) | Vector quantizer | |
| CN116208171A (zh) | 数据压缩和解压缩方法、装置、电子设备及存储介质 | |
| Cheng et al. | Robust zero-redundancy vector quantization for noisy channels | |
| CN100459460C (zh) | 对数据进行编码和译码的方法和装置 | |
| JPS6340507B2 (ja) | ||
| JPS6340506B2 (ja) | ||
| Chang | Gradient match and side match fractal vector quantizers for images | |
| JPH0621828A (ja) | ベクトル量子化復号化器 | |
| JPH0327670A (ja) | 画像データのベクトル量子化器 | |
| JPH0256119A (ja) | ベクトル量子化器の符号化回路 | |
| JP2755464B2 (ja) | 画像データ圧縮方式 | |
| JPH027232B2 (ja) |