JPH09504146A - 可変ワード長を有する符号器用ビットバジェットの評価法及び評価装置 - Google Patents

Abstract

(57)【要約】 本発明はデジタルデータ、特にデジタルテレビジョン信号を圧縮する回路においてビットバジェットを評価する方法に関する。該方法は信号がＮビットの符号化されたサンプルで表され、該評価が信号のＭ個のサンプルを表すＭ個の二値ワードの中から所定の値（０又は１）を有し所定の次数のビットを取り出す確率に基づいており、エントロピーの計算はＮビットに対応した前記確率に基づいて行われ、全てのエントロピーの和は所要の評価に対応している。本発明は更に該方法を実現する装置にも関している。本発明はデータ圧縮の分野に適用される。

Description

【発明の詳細な説明】 可変ワード長を有する符号器用ビットバジェット の評価法及び評価装置 本発明は、可変ワード長を有する符号器用ビットバジェットを評価する方法の 他に、該方法を実現する画像圧縮装置にも関する。 画像圧縮の分野において、特に高精細テレビジョンの分野において、圧縮され る画像は種々の処理操作（動き評価、例えばＤＣＴ（“離散コサイン変換”）に よる周波数領域への変換）が行われ、その後このようにして得られたデータは符 号化され伝送される。情報の完全性を保ちながら冗長性のあるデータを評価する ため、可変ワード長を有する符号化法（“可変長符号化”即ちＶＬＣ）が使用さ れている場合がある。頻繁に現れるワードは短い二値のワードにより符号化され 、めったに現れないワードは長い二値ワードにより符号化される。これにより平 均ワード長が短くなる、即ち伝送されるビット数が少なくなる。 このような可変長符号化を使用した装置の例を以下に記載する。 図１に示す圧縮回路の簡単な例によれば、ＲＧＢビデオ信号はアナログ／デジ タル変換器１でデジタル化され、出力がピクチャアメモリ３に接続されるＲＧＢ ／ＹＵ Ｖ変換マトリクス２に送られる。入力バッファ４はピクチャアメモリ３と動き評 価器５との間のインターフェイスを構成している。この結果即ちこれらの評価値 は、図１に図示していない回路により処理される。信号は、更に係数を量子化す る適当な回路６により離散コサイン変換（ＤＣＴ）が行われる。これらの係数即 ち非ゼロの係数と一連の非ゼロの係数の長さを組み合わせたものは、最初に周知 のタイプの可変長符号化法により、例えばハフマン法により符号化される（回路 Ｂ）。 バッファ９は符号器から出て、更に図１には示していない伝送チャネルの容量 の関数として出力する圧縮信号を取り入れている。バッファ９が空の時、よりす ばやく満たされる場合問題が生ずる。ある場合には、これにより前記のバッファ にオーバーフローが生じ、これによりデータにロスが生ずる。この問題を避ける ため、スループット調整フィードバックループ１０により、ＤＣＴの係数の量子 化、更に従ってバッファ９に対するデータのスループットが制御される。それ故 、当該ビットバジェット即ち信号即ち圧縮された形の信号部分を符号化するため 、必要なビット数を確かめることができる前にデータのＶＬＣ符号化を行う必要 がある。 この方策は、一番目の状態がビットバジェットの一番目の評価に対するもので あり、二番目の状態が一番目の状態の結果により左右される訂正を有するそれ自 体の符号化に対するものである二つの状態で符号化が行われる 時、多数の無意味な計算を行う必要があるので、この方策は不十分である。これ により回路の複雑性が増す他に時間とエネルギーの損失が生ずる。 本発明の目的はこれらの欠点を避けることである。 本発明の目的は、更には符号器から出たデータのスループットの評価を行うこ と、更に可変ワード長符号化の前で該評価を行うことである。 本発明の主題は、デジタルデータ、特にデジタル化されたテレビジョン信号を 圧縮する回路内でビットバジェットを評価する方法であって、前記信号はＮビッ トのサンプルで表され、評価は信号のＭ個のサンプルを表わすＭ個の二値ワード から所定の値を有する所定の次数のビットを取り出す確率に基づいており、エン トロピーの計算はＮ個のビットに対応する前記の確率に基づいて行われ、全ての エントロピーの和は所要の評価に対応していることを特徴としている。 エントロピーにより構成される下限についてある符号化法を行うことが知られ ている。ハフマン符号化法の場合、信号のサンプルを符号化するため必要なビッ トの平均の数はエントロピーよりたかだが１ビット大きいことが知られている。 エントロピーを知ると、即ち少なくともエントロピーを評価することにより、ス ループット、即ち期待されるスループットを少なくとも評価することを符号化の 前でも知ることができる。 本発明による方法では、信号のＭ個のサンプルの中の 同じ次数のビットの間の相関はサンプル自体の間の相関を直接考慮するより以上 に考慮されている。このようにして得られた評価は従来のエントロピーの計算を 通して決定される値より必ず大きい。しかし、計算に必要な比較器及びカウンタ の数は評価の場合の各サンプル内のビット数まで少なくなり、これは２^N個の比 較器とカウンタを必要とする従来の計算と比較してハードウエアがかなり節約で きることを示している（サンプルに対する可能な値に対し１個の比較器と１個の カウンタ）。 本発明の主題は、更に前記の方法を実現する装置である。 本発明に基づく方法を特別に使用することによれば、ビットバジェットの評価 は符号器から出たデータのスループットを予測することに役立つ。 本発明を特別に使用することによれば、ビットバジェットを評価することはビ デオバッファの充填の程度を調整すること、及びそれ故符号化を伝送チャネルの スループットに適合させることに役立つ。 本発明による方法は、時間又は周波数領域であらゆる種類のデータに適用する ことができる。 本発明の他の利点は以下に示す添付の図により表された非制限的な好ましい実 施態様から明らかになる。 図１は既に記載したテレビジョン信号圧縮回路の部分的な動作図を示しており 、 図２は本発明による方法のレイアウトの例の動作図を 示しており、 図３は次数２ⁱのビットに対応したエントロピーを計算する回路の動作図を示 しており、前記回路は図２で使用されている。 長さがＮの二値ワードにより表わされるサンプルは次の形を取る： ｂ_N-1ｂ_N-2…ｂ_i…ｂ₁ｂ₀ ｂ_iは次数２ⁱ（０≦ｉ≦Ｎ−１）のビットであり、各ビットは値０又は１を取 る。 各ビットｂ_iに対し、このビットがＭ個のサンプルの中で値１を取る回数Ｃ_iを 決定する。ｂ_iが値１を取る確率はｐ_i＝Ｃ_i／Ｍである。ｂ_iが値０を取る確率は 明らかにｑ_i＝１−Ｃ_i／Ｍである。 このビットに対しエントロピーは従来の通り次式を用いて計算される： Ｈ_i＝−ｐ_iLog₂ｐ_i−ｑ_iLog₂ｑ_i この式は次式に等しい： Ｈ_i＝−（Ｃ_i／Ｍ）Log₂（Ｃ_i／Ｍ_i） −（１−Ｃ_i／Ｍ）Log₂（１−Ｃ_i／Ｍ） エントロピーは次に全てのビットｂ_iに対し加算される。Ｍ個のサンプルにつ いて加算することにより、ビットバジェットの評価が得られる。Ｍで割り算する ことにより、評価はワードを符号化するため必要なビットの平均数から得られる ： 図２はＭ個のビットのサンプルにより表わされる信号を符号化するため必要な ビット数を評価する回路の動作図を示している。該回路はバス１２の上でデータ の周波数に同期したクロック１１を備えている。クロック１１はデータがバス１ ２の上に用意される時、ストローブを出す。 バス１２の各ラインは信号を表わすサンプルのビットｂ_iに対応しており、ビ ットがＬ個のカウンタ１４ｉの入力１５ｉに接続されている。カウンタ１４ｉは 少なくともＭまで計数できるカウンタである。Ｌはそれ故、２（^L-2）＜Ｍ≦２ （^L-1）の様に選択される。前記カウンタは、更にゼロリセット入力１７ｉの他 にクロック入力１６ｉも有している。クロック入力１７ｉはクロック１２に接続 されており、ゼロリセット入力は回路１３の出力に接続されている。 前記のカウンタ１３にはカウンタと比較器が含まれており、Ｍ個のクロック信 号が計数される毎に出力に信号を出力する。 カウンタ１４ｉは、入力１６ｉのクロック１２の立ち上がり端で入力１５ｉが １であるならば１単位増加される。 評価段階の開始において、全てのカウンタ（カウンタ１４ｉ及び回路１３のカ ウンタ）はゼロである。デジタル信号に対応したデータがバス１２の上に生ずる 毎に、クロック１１はパルスを送出する。カウンタ１４ｉはその入力１５ｉがハ イならば増加する。回路１３のカウンタはクロックにより与えられるパルスの数 を計数する。この数がＭを越えるならば、回路１３により自身のカウンタ及びカ ウンタ１４ｉがゼロにリセットされる。 他の実施態様によれば、回路１３のカウンタの状態はＭ個のワードが計数され る時信号を発生する図示しない回路に送出され、修正結果が出力２１及び２２で 利用される回数を通知する。このような実施態様を実現する方法は当業者の技術 の範囲内にある。 各カウンタ１４ｉの出力は、後述する当該回路１８ｉの入力に接続されている 。回路１８ｉはそれぞれビットｂ_iに対応するエントロピーを出力する。エント ロピーは加算装置１９により加算される。その結果は加算装置２０により式（１ ）の一定項ＮLogＭから差し引かれる。出力２１又は出力２２は評価がＭ個のサ ンプルを符号化する必要のあるビットのトータル数又はサンプル当たりのビット の平均数のいずれかを希望するかにより選択される。出力２１は加算装置２０の 出力に直接対応しており、出力２２はＭによる割り算器２３を通した出力に対応 している。 図３は回路１８ｉの一方に対応した動作図を示してい る。この回路は入力としてＭの値の他に、ビットｂ_iがＭ個のサンプル内で１で ある回数に対応したＣ_iの値を有している。 該回路は原理的に基数２に対する対数テーブル２４と２５を備えている。これ らの回路の特別な特徴はゼロの対数が通常は定義されていないが、ゼロが入力に ある時出力がゼロとなることである。 テーブル２４の入力は項Ｍ−Ｃｉを受け、テーブル２５は項Ｃｉを受ける。テ ーブルの出力はそれぞれ乗算器に行き、該乗算器はそれぞれＭ−Ｃｉ及びＣｉを 更に受ける。二つの乗算器からの出力は加算され回路１８ｉからの出力を与える 。 他の実施態様によれば、単独の対数メモリが全ての回路１８ｉに使用されてお り、マイクロプロセッサ又は同様のものがこのメモリからの値を与えるため使用 されている。 他の実施態様によれば、回路１３には、必要な時間に信号を該回路の入力に加 えることにより、評価を開始したいサンプルから詳細に選択できるゼロリセット が含まれている。 得られた評価は次に圧縮装置の他の回路により使用され、特に圧縮されたデー タのバッファの充填度を調整し、又は係数の量子化に適合する。本発明による評 価装置と、それ自体で調整を行う他に設置される装置全体との相互作用は、当業 者に周知なレイアウトの１つにより行 われる。 特別な実施態様によれば、ビットバジェットの評価は符号器の一番目の状態の 中で行われ、当該結果は二番目の状態の間係数の量子化に適応させるため使用さ れ所要のビット速度を得ており、前記二番目の状態は実際のＶＬＣ符号化により 終了され、一番目の状態は本発明による方法に基づきビットバジェットの評価に より終了される。 特別な実施態様によれば、本発明に基づく方法による評価はデータがＤＣＴ変 換によりウォルシューハダマード変換に従って行われた後得られる。ウォルシュ ーハダマード変換はＤＣＴ変換より実現が容易で、加算と減算のみが必要で乗算 は必要でない。ウォルシューハダマード変換の後本発明に基づく方法により得ら れる評価を使用し、ＤＣＴにより得られる係数の量子化に適応させることが可能 である。 前述に与えた方法以外の方法を実現することは勿論可能である。特に、マイク ロプロセッサによりあるステップを実現することが可能である。 ビットバジェット評価法は可変長符号器を含む他の応用には明らかに使用でき ない。

【手続補正書】特許法第１８４条の８ 【提出日】１９９５年５月１７日 【補正内容】 （翻訳文第１頁と第２頁の差し替え） 可変ワード長を有する符号器用ビットバジェット の評価法及び評価装置 本発明は、可変ワード長を有する符号器用ビットバジェットを評価する方法の 他に、該方法を実現する画像圧縮装置にも関する。 画像圧縮の分野において、特に高精細テレビジョンの分野において、圧縮され る画像は種々の処理操作（動き評価、例えばＤＣＴ（“離散コサイン変換”）に よる周波数領域への変換）が行われ、その後このようにして得られたデータは符 号化され伝送される。情報の完全性を保ちながら冗長性のあるデータを評価する ため、可変ワード長を有する符号化法（“可変長符号化”即ちＶＬＣ）が使用さ れている場合がある。頻繁に現れるワードは短い二値のワードにより符号化され 、めったに現れないワードは長い二値ワードにより符号化される。これにより平 均ワード長が短くなる、即ち伝送されるビット数が少なくなる。文献ＥＰ−Ａ− ０４１９１４１には可変長符号化法が記載されている。 このような可変長符号化を使用した装置の例を以下に記載する。 図１に示す圧縮回路の簡単な例によれば、ＲＧＢビデオ信号はアナログ／デジ タルに変換器１でデジタル化され、出力がピクチャアメモリ３に接続されるＲＧ Ｂ／Ｙ ＵＶ変換マトリクス２に送られる。入力バッファ４はピクチャアメモリ３と動き 評価器５との間のインターフェイスを構成している。この結果即ちこれらの評価 値は、図１に図示していない回路により処理される。信号は、更に係数を量子化 する適当な回路６により離散コサイン変換（ＤＣＴ）が行われる。これらの係数 即ち非ゼロの係数と一連の非ゼロの係数の長さを組み合わせたものは、最初に周 知のタイプの可変長符号化法により、例えばハフマン法により符号化される（回 路Ｂ）。 バッファ９は符号器から出て、更に図１には示していない伝送チャネルの容量 の関数として出力する圧縮信号を取り入れている。バッファ９が空の時、よりす ばやく満たされる場合問題が生ずる。ある場合には、これにより前記のバッファ にオーバーフローが生じ、これによりデータにロスが生ずる。この問題を避ける ため、スループット調整フィードバックループ１０により、ＤＣＴの係数の量子 化、更に従ってバッファ９に対するデータのスループットが制御される。それ故 、当該ビットバジェット即ち信号即ち圧縮された形の信号部分を符号化するため 、必要なビット数を確かめることができる前にデータのＶＬＣ符号化を行う必要 がある。 この方策は、一番目の状態がビットバジェットの一番目の評価に対するもので あり、二番目の状態が一番目の状態の結果により左右される訂正を有するそれ自 体の符号化に対するものである二つの状態で符号化が行われる （翻訳文第５頁〜第７頁の差し替え） 示しており、 図３は次数２ⁱのビットに対応したエントロピーを計算する回路の動作図を示 しており、前記回路は図２で使用されている。 長さがＮの二値ワードにより表わされるサンプルは次の形を取る： ｂ_N-1ｂ_N-2…ｂ_i…ｂ₁ｂ₀ ｂ_iは次数２ⁱ（０≦ｉ≦Ｎ−１）のビットであり、各ビットは値０又は１を取 る。 各ビットｂ_iに対し、このビットがＭ個のサンプルの中で値１を取る回数Ｃ_iを 決定する。ｂ_iが値１を取る確率はｐ_i＝Ｃ_i／Ｍである。ｂ_iが値０を取る確率は 明らかにｑ_i＝１−Ｃ_i／Ｍである。 このビットに対しエントロピーは従来の通り次式を用いて計算される： Ｈ_i＝−ｐ_iLog₂ｐ_i−ｑ_iLog₂ｑ_i この式は次式に等しい： Ｈ_i＝−（Ｃ_i／Ｍ）Log₂（Ｃ_i／Ｍ_i） −（１−Ｃ_i／Ｍ）Log₂（１−Ｃ_i／Ｍ） エントロピーは次に全てのビットｂ_iに対し加算される。Ｍ個のサンプルにつ いて加算することにより、ビットバジェットの評価が得られる。Ｍで割り算する ことにより、評価はワードを符号化するため必要なビットの平均数が得られる： 図２はＭ個のビットのサンプルにより表わされる信号を符号化するため必要な ビット数を評価する回路の動作図を示している。該回路はバス１２の上でデータ の周波数に同期したクロック１１を備えている。クロック１１はデータがバス１ ２の上に用意される時、ストローブを出す。 バス１２の各ラインは信号を表わすサンプルのビットｂ_iに対応しており、ビ ットがＬ個のカウンタ１４_iの入力１５_iに接続されている。カウンタ１４_iは少 なくともＭまで計数できるカウンタである。Ｌはそれ故、２^(L-2)＜Ｍ≦２^(L-1) の様に選択される。前記カウンタは、更にゼロリセット入力１７ｉの他にクロッ ク入力１６ｉも有している。クロック入力１７ｉはクロック１２に接続されてお り、ゼロリセット入力は回路１３の出力に接続されている。 前記のカウンタ１３にはカウンタと比較器が含まれており、Ｍ個のクロック信 号が計数される毎に出力に信号に出力する。 カウンタ１４ｉは、入力１６ｉのクロック１２の立ち上がり端で入力１５ｉが １であるならば１単位増加される。 評価段階の開始において、全てのカウンタ（カウンタ１４ｉ及び回路１３のカ ウンタ）はゼロである。デジタル信号に対応したデータがバス１２の上に生ずる 毎に、クロック１１はパルスを送出する。カウンタ１４ｉはその入力１５ｉがハ イならば増加する。回路１３のカウンタはクロックにより与えられるパルスの数 を計数する。この数がＭを越えるならば、回路１３により自身のカウンタ及びカ ウンタ１４ｉがゼロにリセットされる。 他の実施態様によれば、回路１３のカウンタの状態はＭ個のワードが計数され る時信号を発生する図示しない回路に送出され、修正結果が出力２１及び２２で 利用される回数を通知する。このような実施態様を実現する方法は当業者の技術 の範囲内にある。 各カウンタ１４ｉの出力は、後述する当該回路１８ｉの入力に接続されている 。回路１８ｉはそれぞれビットｂ_iに対応するエントロピーを出力する。エント ロピーは加算装置１９により加算される。その結果は加算装置２０により式（１ ）の一定項ＮLogＭから差し引かれる。出力２１又は出力２２は評価がＭ個のサ ンプルを符号化する必要のあるビットのトータル数又はサンプル当たりのビット の平均数のいずれかを希望するかにより選択される。出力２１は加算装置２０の 出力に直接対応しており、出力２２はＭによる割り算器２３を通した出力に対応 している。 図３は回路１８ｉの一方に対応した動作図を示してい （翻訳文第１０頁と第１１頁の差し替え） 請求の範囲 １．デジタルデータ、特に信号がＮビットの符号化されたサンプルで表されるデ ジタルテレビジョン信号を圧縮する回路においてビットバジェットを評価する方 法であって、該評価は信号のＭ個のサンプルを表すＭ個の二値ワードから所定の 値（０又は１）を有する所定の次数のビットを取り出す確率に基づいており、エ ントロピーの計算は所要の評価に対応した前記確率に基づいて行われていること を特徴とする評価法。 ２．所定の次数のビットが前記所定の値を有する項Ｃｉ（０≦ｉ≦Ｎ−１）の数 が信号のＭ個のサンプルから決定され、この決定から該ビットのエントロピーＨ ｉが導かれることを特徴とする請求項１に記載の方法。 ３．Ｍ個の二値ワードが処理される時、エントロピーＨｉがビットバジェットの 所要の評価を得るため加算されることを特徴とする前述の請求項のいずれか１つ に記載の方法。 ４．ワードを符号化するため必要なビットの平均数の評価が、 で与えられることを特徴とする前述の請求項のいずれか１つに記載の方法。 ５．前述の請求項のいずれか１つの方法を実現する装置であって、２^(L-2)＜Ｍ ≦２^(L-1)となるようなＬを有したＮ個のＬビットカウンタ（１４ｉ）を備え、 ビットｂ_iがＭ個の二値ワードの中から前記の所定の値を有する回数Ｃｉを該カ ウンタ（１４ｉ）のそれぞれが計数し、該装置が更に各カウンタに対し入力が一 方はＣｉに他方はＭ−Ｃｉに加えられ基数を２とする二つの対数のテーブル（２ ４、２５）を備え、前記テーブル（２４、２５）が出力として当該対数又は入力 がゼロならば値ゼロを出力し、各テーブルからの前記出力が入力で該値と掛け算 され、これらの２Ｎ個の乗算の結果が一定の項ＮLogＭから引き算されるように 加え合わされていることを特徴とする装置。 ６．周波数領域変換回路（６）と、可変長符号器（８）と、出力バッファ（９） とを備えたテレビジョン信号を圧縮する装置であって、請求項１から４のいずれ か１つに基づく方法を実現する評価手段（１１から２５）を備え、これによる評 価が前記信号に対する圧縮率を適用することにより前記出力バッファ（９）に向 けられた圧縮信号のスループットを調整するためスループット調整回路（１０） により使用されていることを特徴とする装置。

Claims (1)

1. 【特許請求の範囲】 １．デジタルデータ、特にデジタルテレビジョン信号を圧縮する回路においてビ ットバジェットを評価する方法であって、前記信号はＮビットの符号化されたサ ンプルで表され、該評価は信号のＭ個のサンプルを表すＭ個の二値ワードから所 定の値（０又は１）を有する所定の次数のビットを取り出す確率に基づいており 、エントロピーの計算はＮビットに対応した前記確率に基づいて行われており、 全てのエントロピーの和は所要の評価に対応していることを特徴とする評価法。 ２．所定の次数のビットが前記所定の値を有する項Ｃｉ（０≦ｉ≦Ｎ−１）の数 が信号のＭ個のサンプルから決定され、この決定から該ビットのエントロピーＨ ｉが導かれることを特徴とする請求項１に記載の方法。 ３．Ｍ個のサンプルが処理される時、エントロピーＨｉがビットバジェットの所 要の評価を得るため加算されることを特徴とする前述の請求項のいずれか１つに 記載の方法。 ４．ワードを符号化するため必要なビットの平均数の評価が、 で与えられることを特徴とする前述の請求項のいずれか１つに記載の方法。 ５．前述の請求項のいずれか１つの方法を実現する装置であって、２^(L-2)＜Ｍ ≦２^(L-1)となるようなＬを有したＮ個のＬビットカウンタ（１４ｉ）を備え、 ビットｂ_iがＭ個のサンプルの中から前記の所定の値を有する回数Ｃｉを該カウ ンタ（１４ｉ）のそれぞれが計数し、該装置が更に各カウンタに対し入力が一方 はＣｉに他方はＭ−Ｃｉに加えられ基数を２とする二つの対数のテーブル（２４ 、２５）を備え、前記テーブル（２４、２５）が出力として当該対数又は入力が ゼロならば値ゼロを出力し、各テーブルからの前記出力が入力で該値と掛け算さ れ、これらの２Ｎ個の乗算の結果が一定の項ＮLogＭから引き算されるように加 え合わされていることを特徴とする装置。 ６．請求項１から４のいずれか１つに基づく方法を実現し可変長符号器を備えテ レビジョン信号を圧縮する装置であって、前記方法が信号を表すサンプルのあら ゆる線形変換の前に実現され、該方法から得られる評価がデータ圧縮率を伝送チ ャネルの容量に適応させるように使用されていることを特徴とする装置。