JP2017135708A - バイナリデータを圧縮および復元する方法および装置 - Google Patents

Abstract

【課題】バイナリデータを圧縮および復元する方法および装置を提供する。【解決手段】本発明は、全てが同じ数であるＢ個のビットでコード化された入力バイナリデータ値ｘの組を、全てがより少ない数であるｂ個のビットでコード化された出力データ値ｘ’の対応する組に圧縮する方法であって、量子化の刻み幅ｄｑを計算するステップと、値の範囲［０，２Ｂ−１［を２ｂ個の部分範囲、・［０，ＩＮＴ（ｄｑ／２）［である第１の部分範囲、・［ＩＮＴ（（ｉ−３／２）＊ｄｑ）＋１，ＩＮＴ（（ｉ−１／２）*ｄｑ）［である第ｉの部分範囲（ここで、ｉは２〜２ｂである）に分割するステップとを有する。【選択図】図５

Description

本発明は、バイナリデータを圧縮および復元する方法および装置、ならびに前記圧縮および復元方法を用いて画像またはビデオデータストリームの格納／取り出しまたは送信／受信を行う方法に関する。

視聴覚情報の市場は、超高解像度（８１９２×４３２０ピクセル）およびより高いフレームレートに向けて急激に進化している。リアルタイムハードウェアシステムは、従って、更に高いピクセルレートでデータを処理することが求められる。ビデオ画像の格納に要する記憶容量および／またはビデオ画像を送信する帯域幅を制限する必要がある。この課題に対処するために、公知の解決策は、バイナリ値のコード化に用いるビット数を減らすことである。Ｂ個のビットでコード化された値のビット数をｂ個のビットでコード化された値に減らす（ここで、Ｂ＞ｂである）演算は、量子化と呼ばれる。

数値を量子化する公知の方法について以下に述べる。特定の値の特徴に適合された他の方法があり、例えば対数または指数値を量子化するものである。ここで、一般的なケースについて述べる。［０、Ｎ_ｍａｘ［が量子化対象の任意の値の間隔境界、ｄｑが量子化の刻みサイズ（量子化された組の２個の連続した値同士のギャップ）であれば、値ｘは次式のように値ｘ’に量子化される。

ここで、

演算子は「最小整数への切り捨て」を意味する。区間は（Ｎ_ｍａｘ／ｄｑ）＋１個の部分範囲に区分され、その各々が量子化された値に対応する。項１／２は部分範囲を各々の部分区間の中心に合わせるものである。量子化値ｘ’は次式のように値ｘ”に逆量子化される。

図１は横軸のｘの値を示しており、ｘの値は０〜１２７の整数、すなわちＮ_ｍａｘ＝１２８である。量子化の刻み幅、すなわち量子化された組の２個の連続する値同士のギャップｄｑは１６に等しい。区間［０、１２８［は９個の部分範囲に区分されている。実線は逆量子化値ｘ”を表す。破線は、元の未量子化値を表す。ｘの値０〜７は逆量子化値０に対応する。ｘの値８〜２３は逆量子化値１６に対応し、以下同様に、ｘの値１２０〜１２７は逆量子化値１２８に対応する。値が符号付きである場合も同じ原理である。量子化対象の値が、区間］−Ｎ_ｍａｘ，Ｎ_ｍａｘ［の範囲内にあるため、符号ｘ_ｓは絶対値ｙから分離されて上述のように次式が得られる。
ｙ＝｜ｘ｜
ｘ_ｓ＝ｓｉｇｎ（ｘ）

図２は、ｘとｘ”との対応関係を示す。逆量子化は元の領域における値ｘ”を再構築する。精度がある程度低下しているため、結果的に得られた値は異なっていて、この差異は切り捨て誤差ε（実線と破線とのギャップ）と呼ばれる。
ｘ”＝ｘ_ｓ・ｙ’・ｄｑ
ε＝ｘ”−ｘ

入出力データがバイナリ値である場合、以下の状況になる。整数値ｘをＢ＋１ビットでコード化するために、１ビットを用いて符号（例えば正は０、負は１）を表し、Ｂ個のビットを用いてｘの絶対値を表す。同様に、量子化された絶対値ｙ’のコード化にＢ個のビットを使用し、１ビットｘ_ｓを用いて符号を表す。
Ｎ_ｍａｘ＝２^Ｂ

ｙ＝｜ｘ｜
ｘ_ｓ＝ｓｉｇｎ（ｘ）

ここで、＜＜および＞＞演算子は各々、左右方向へのバイナリシフトを表す。右方向へのバイナリシフトの結果として得られるビットは２^０−重みビットの右側に留まる、すなわち分数値が得られる。量子化値は、元の値を単純にＢ−ｂビットだけ右方向にバイナリシフトし、続いて最も近い整数に丸めることにより得られる。

式（１）の項「１／２」は、量子化値をコード化するために余分な１ビットを必要とし、量子化では、Ｂ−ｂ個のビットを除去するのではなく、Ｂ−ｂ−１個のビットを除去する。図１から分かるように、０〜８の範囲でｙ’の９個の値に対応する９個の部分範囲があり、量子化値のコード化に４ビットが必要である。図２では、−８〜＋８の範囲のｙ’の１７個の値に対応する１７個の部分範囲があり、ｘの値に依存してコード化に５ビットを必要とする。これは、圧縮で求められる特性が、量子化値のコード化に何個のビットが必要であるかを値の送信または格納前に正確に判定する能力であるため、望ましくない。この必要とされる余分なビットは、量子化のレベル（何個のビットを除去するか）が、目標出力レート（何個のビットが出力されるか）の関数として選択される場合に影響が大きい。隣接する値は往々にして相関を有しており、同一範囲に含まれているため、圧縮アルゴリズムは、この特徴を利用して同一ビット数でコード化されたブロックにこれらの値を再グループ化する。この個数は、これらの値がゼロを中心としていると仮定して、最大の絶対値により設定される。各ブロックに一意な量子化の刻み幅ｄｑを用いることで、量子化値の復元に量子化の刻み幅ｄｑを取得することが必要な逆量子化手順における圧縮符号ストリームに追加される情報の量が減る。従って、この量子化の刻み幅を選択した後で出力ビット数を変更すれば、レートが不正確になるか、またはレートを制御化に保つために反復的な処理が必要になる。例えば、ｂ＜ｄｉｇｉｔｓ＞が値のバイナリ表現であり、４個の４ビット値のブロックを考える場合、次式が得られる。

この特定のｘブロックは、各値のコード化に３ビットを必要とする。アルゴリズムが、出力ストリーム内で２ビットでコード化された値をブロックに入れると決定した（通常、品質対コスト基準に応じて決定される）場合、次式が得られる。
Ｂ＝３，ｂ＝２⇒ｄｑ＝２

最も近い整数に丸めることにより、ｘ_２＝７から３ビットに量子化された値ｙ’_２＝４が得られることが分かる。これが課題となるのは、先の決定がブロックの各値に対して２ビット、すなわち９ビットではなく合計８ビットを出力するものであったからである。

固定幅量子化（方法１）
固定幅量子化（方法１）を行う公知の方法によれば、上述の課題を回避して、ビット数を一定に保つことができる。これは量子化における項１／２を割愛することで行われる。

対応する逆量子化では、順方向量子化における簡略化に起因するバイアスを補償するために補正項を導入する。

ｘ”＝ｘ_ｓ・ｙ”
これは、量子化値を単にＢ−ｂ−１ビットだけ左方向にバイナリシフトするものである。ｙ’の値は１６個であるため、ｙ’を４ビットで、すなわち余分なビットなしで表すことができる。図３に示すように、出力値は依然として中心付近にあるが、出力値にゼロ値は存在しない。補正項により、値が−ｄｑ／２からｄｑ／２までジャンプしている。ゼロを中心とする小さい値が存在するため、上記により量子化された「チェッカーフラグ」パターン（＋ｄｑ／２、−ｄｑ／２、＋ｄｑ／２、−ｄｑ／２、＋ｄｑ／２、−ｄｑ／２、．．．）が生じるが、これらは殆どの場合に望ましくない。図１０は、全てが破線で表す小さい値（−２、−１、０、＋１、＋２）を有するバイナリ値ｘの組から、＋８または−８（実線）の何れかである逆量子化値が得られる例を示す。

デッドゾーン（方法２）
ゼロを中心とするデッドゾーンを有する公知の方法（方法２）はゼロ値を許すものであり、方法１の課題を解決する。逆量子化においてデッドゾーンを導入する（図４参照）。−１６〜＋１６のｘの全ての入力値から、ゼロの逆量子化値が得られる。ｙ’の値の個数は１５であるため、ｙ’は４ビットであり、すなわち余分なビットなしで表すことができる。

丸め演算の性質により、符号付きの値の場合、ゼロを中心とするビンの幅は他のビンの２倍であるため、大きい平坦領域が得られる。その結果、デッドゾーン付近の刻みは他の刻みよりも高さが１．５倍である。これは、この技術を用いるコーデックの出力における信号の品質に悪影響を及ぼす。

バイナリ値量子化の上述の２つの方法は、ソフトウェアまたは論理ゲートにより効率的に実装できるものの、別の課題を抱えている。切り捨てた値のコード化に必要なビット数が切り捨てレベルに依存して変化し得るため、逆演算（方法１）ではゼロを正しく再構築できないか、またはゼロを中心とするデッドゾーン（方法２）を逆量子化に導入するかの何れかである。

（特許文献１）は、制御可能なデッドゾーンを有する量子化方法を用いて、フィルム粒度情報を含むビデオデータをコード化および復号化する方法が開示している。最小係数値に対する量子化の刻み幅が調整されており、従って量子化は不均一である。量子化係数に利用できるビット数に関する量子化の刻み幅の選択については触れられていない。

文献「（非特許文献１）」は量子化方法について述べている。１つの量子化方法は、２のベキ乗（式５、９２８ページ参照）に制限された量子化区間に関するものであり、従って上述の方法の短所を有している。別の量子化方法（式６、９２９ページ参照）はより複雑であり、ＭＰＥＧ−２用に設計されている。

（特許文献２）は、バイナリ入力データ値の組に対してバイアス値を選択し、バイアス値からのオフセットのみを、入力データ値よりも少ないビット数でコード化されたバイナリ出力値として出力する量子化方法を開示している。

より良好な圧縮の実現を図る多くのコード化方法が知られている。しかし、これらの方法は計算および記憶要件の増大が見込まれるため、高解像度および高フレームレートに適用し難い。

米国公開特許第２００７０１６０１３８号明細書 欧州特許第２８１９４１２号明細書

Ｎｅａｒ−ｌｏｓｓｌｅｓｓ ｃｏｍｐｌｅｘｉｔｙ−ｓｃａｌａｂｌｅ ｅｍｂｅｄｄｅｄ ｃｏｍｐｒｅｓｓｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｃｏｓｔ ｒｅｄｕｃｔｉｏｎ ｉｎ ＤＴＶ ｒｅｃｅｉｖｅｒｓ，ｖａｎ ｄｅｒ Ｓｃｈａａｒ，Ｍ．ｅｔ ａｌ．，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｎｓｕｍｅｒ Ｅｌｅｃｔｒｏｎｉｃｓ ａｒｃｈｉｖｅ Ｖｏｌｕｍｅ ４６ Ｉｓｓｕｅ ４，Ｎｏｖｅｍｂｅｒ ２０００ Ｐａｇｅ ９２３−９３

本発明の目的は、入力バイナリデータ値の組を、より少ない数のビットでコード化された出力データ値の対応する組に圧縮する、上述の方法の短所を解消した方法および装置、ならびに入力バイナリデータ値の組を復元する対応する方法および装置を提供することである。

本発明は、独立請求項により規定される。従属請求項は有利な実施形態を規定する。

本発明の第１の態様によれば、全てが同じ数であるＢ個のビットでコード化された入力バイナリデータ値ｘの組であって、入力バイナリデータ値が負値を含む場合は符号ビットがカウントされない、入力バイナリデータ値ｘの組を、全てがより少ない数であるｂ個のビットでコード化された出力データ値ｘ’の対応する組であって、符号ビットがカウントされない、出力データ値ｘ’の対応する組に圧縮する方法であって、
ａ）入力バイナリデータ値の組が負値を含む場合、
・各入力バイナリデータ値ｘに対して、ｘの絶対値であるｙ、およびｘの符号であり、１ビットでコード化されたｘ_ｓを決定するステップと、
ｂ）入力バイナリデータ値の組が負値を含まない場合、
・各入力バイナリデータ値ｘに対して、ｘの値であるｙを決定ステップと、
ｃ）量子化の刻み幅ｄｑ

を計算するステップと、
ｄ）ｙの値の範囲を２^ｂ個の部分範囲、
・［０，ＩＮＴ（ｄｑ／２）［である第１の部分範囲、
・［ＩＮＴ（（ｉ−３／２）＊ｄｑ）＋１，ＩＮＴ（（ｉ−１／２）*ｄｑ）［である第ｉの部分範囲（ここで、ｉは２〜２^ｂである）
に分割するステップと、
ｅ）ｙの各値に対して、ｙが要素である部分範囲ｉを決定し、およびｙ’＝ｉ−１を計算するステップと、
ｆ）入力バイナリデータ値の組が負値を含む場合、
・各入力バイナリデータ値ｘに対して、ｘ_ｓと共にｙ’の値であるｘ’を決定するステップと、
ｇ）入力バイナリデータ値の組が負値を含まない場合、
・各入力バイナリデータ値ｘに対して、ｙ’の値であるｘ’を決定するステップと
により得られる方法を提供する。ｙの値の範囲は、区間［０，２^Ｂ］である。本発明の一実施形態において、出力データ値ｘ’の組は上述のステップにより得られる。本発明の他の実施形態において、出力データ値ｘ’の組は、以下のレジスタシフト法または参照表法により得られる。部分範囲は「ビン」とも呼ばれ、この方法は「ビン法」と呼ばれる。

一実施形態において、ステップｃ）、ｄ）およびｅ）の結果は、
・ｙをＢ−ｂビットだけ右方向にシフトし、第１の結果を得るステップと、
・ｙをＢ＋１ビットだけ右方向にシフトし、第２の結果を得るステップと、
・第１の結果から第２の結果を減算し、第３の結果を得るステップと、
・０，５を加算し、第４の結果を得るステップと、
・第４の結果の正およびゼロの重み、すなわち分数ではないビットを選択し、ｙ’を得るステップと
を実行することにより均等に得ることができる。右方向へのシフト演算において、分数の重みビットは保持される。両方法とも均等である。値ｙ’は、ｂ個のビットでコード化される。

別の実施形態において、本方法は、
・ｙの２^Ｂ個の値の各々に対して、ｙ’の対応する値を含む参照表を取得するステップと、
・前記組のｙの各値に対して、前記表の索引ｙにおけるｙ’の対応する値を決定するステップと
を含む。

本発明の第２態様によれば、入力バイナリデータ値を含む入力バイナリデータを、ある限度より小さいボリュームを有する出力バイナリデータに圧縮する方法であって、本方法は、
・前記入力バイナリデータ値をＮ_ＧＣＬＩ個の入力バイナリデータ値の組にグループ化するステップと、
・前記Ｎ_ＧＣＬＩ個の入力バイナリデータ値の組の各々に対して、
− 前記組における最大非ゼロビットであって、符号ビットがカウントされない、最大非ゼロビットの指数であるＧＣＬＩを決定するステップと、
・全ての前記入力バイナリデータ値に対してＧＣＬＩ−ＧＴＬＩビットをカウントすることにより、前記限度よりも小さいボリュームを有する出力バイナリデータを生成するようにＧＴＬＩの値を選択するステップと、
・前記Ｎ_ＧＣＬＩ個の入力バイナリデータ値の組の各々に対して、
− Ｂ＝ＧＣＬＩかつｂ＝ＭＡＸ（ＧＣＬＩ−ＧＴＬＩ，０）の条件で請求項１乃至３の何れか１項に記載の方法を適用するステップと、
・ＧＴＬＩを含む出力バイナリデータと、前記Ｎ_ＧＣＬＩ個の入力バイナリデータ値の組の各々に対して、ＧＣＬＩの値およびＮ_ＧＣＬＩ個の量子化値ｘ’とを生成するステップと
を含む。

本発明の第２態様の方法の実行で生じ得るｂ＝０の自明なケースでは、出力データの値は０であるため、０ビットでコード化される。この場合、この組の出力バイナリデータはＧＣＬＩのみを含んでいる。

本方法は、有利な特徴として、前記入力バイナリデータがビデオデータの非相関的な変換から得られる場合に適用される。

Ｎ_ＧＣＬＩは４〜１６に含まれ、好ましくは４に等しい。

本発明の第３の態様によれば、全てが同じ数であるｂ個のビットでコード化された入力バイナリデータ値ｘ’の組であって、可能な符号ビットがカウントされない、入力バイナリデータ値ｘ’の組を、全てがより多い数であるＢ個のビットでコード化された出力データ値ｘ”の対応する組であって、可能な符号ビットがカウントされない、出力データ値ｘ”の対応する組に復元する方法であって、
ａ）

を計算するステップと、
ｂ）入力バイナリデータ値の組が負値を含む場合、各入力バイナリデータ値ｘ’に対して、ｘの絶対値であるｙ’、およびｘ’の符号であり、１ビットでコード化されたｘ’_ｓを決定するステップと、
ｃ）入力バイナリデータ値の組が負値を含まない場合、各入力バイナリデータ値ｘ’に対して、ｘ’の値であるｙ’を決定するステップと、
ｄ）各ｙ’に対して、

を計算するステップと
ｅ）入力バイナリデータ値の組が負値を含む場合、各入力バイナリデータ値ｙ’に対して、ｘ’_ｓと共にｙ”の値であるｘ”を決定するステップと、
ｆ）入力バイナリデータ値の組が負値を含まない場合、各入力バイナリデータ値ｘ’に対して、ｙ”の値であるｘ”を決定するステップと
を含む、方法を提供する。

上述の復元方法において、前記ステップｄ）は、
ｉ．ｙ’をＢ−ｂビットだけ左方向にシフトし、第１の結果を得るステップと、
ｉｉ．第１の結果をｂ＋１ビットだけ右方向にシフトし、第２の結果を得るステップと、
ｉｉｉ．第１の結果に第２の結果を加算し、合算結果を得るステップと、
ｉｖ．第２の結果を第１の結果にコピーするステップと、
ｖ．第２の結果がゼロを下回るまでステップｉｉ．〜ｉｖ．を繰り返すステップと、
ｖｉ．合算結果の整数部分としてｙ”を計算するステップと
を含むことができる。

上述の復元方法において、前記ステップｄ）はまた、
ｉ．ｙ’をＢ−ｂビットだけ左方向にシフトし、第１の結果を得るステップと、
ｉｉ．第１の結果をｂ＋１ビットだけ右方向にシフトし、第２の結果を得るステップと、
ｉｉｉ．第１の結果に第２の結果を加算し、合算結果を得るステップと、
ｉｖ．合算結果の整数部分としてｙ”を計算するステップと
を含むことができる。

上述の復元方法は、
・ｙ’の２^ｂ個の値の各々に対して、ｙ”の対応する値を含む参照表を取得するステップと、
・前記組のｙ’の各値に対して、前記表の索引ｙ’におけるｙ”の対応する値を決定するステップと
を含むことができる。

本発明の第４の態様によれば、Ｎ_ＧＣＬＩ個の入力バイナリデータ値の組を含む入力バイナリデータを復元する方法が提供され、各組は、復元されたバイナリデータ値のビット数であるＢの値と、前記入力バイナリデータ値の個数であって、可能な符号ビットがカウントされない、前記入力バイナリデータ値の個数であるｂの値とを含み、本方法は、
・復元されたバイナリデータ値を得るために、請求項７〜１０の何れか１項に記載の方法を適用するステップと、
・前記復元されたバイナリデータ値を含む出力バイナリデータを生成するステップと
を含む。

前記復元されたバイナリデータ値は、所与の長さを有するワードを得るために「０」個のビットで補完されていてよい。

本発明はまた、本発明の圧縮方法により得られる入力バイナリデータ値ｘ’の組を復元するための、本発明による復元方法の使用にも関する。

本発明はまた、全てが同じ数のビットでコード化された入力バイナリデータ値ｘの組を、全てがより少ない数のビットでコード化された出力データ値ｘ’の対応する組に圧縮する装置であって、本発明の圧縮方法を実行するプログラムコードを含む、装置に関する。

本発明はまた、全てが同じ数のビットでコード化された入力バイナリデータ値ｘの組を、全てがより少ない数のビットでコード化された出力データ値ｘ’の対応する組に圧縮する装置であって、本発明の圧縮方法を実行するハードウェアを含む、装置に関する。

本発明はまた、全てが同じ数のビットでコード化された入力バイナリデータ値ｘ’の組を、全てがより多い数のビットでコード化された出力データ値ｘ”の対応する組に復元する装置であって、本発明の復元方法を実行するプログラムコードを含む、装置にも関する。

本発明はまた、全てが同じ数のビットでコード化された入力バイナリデータ値ｘ’の組を、全てがより多い数のビットでコード化された出力データ値ｘ”の対応する組に復元する装置であって、本発明の復元方法を実行するハードウェアを含む、装置に関する。

本発明の方法は、全ての正整数値を有する入力バイナリデータ値の組と、正および負値を有する入力バイナリデータ値とに適用できる。後者の場合、負値が符号ビットおよび大きさ（絶対値）により表されると仮定する。別の表現、例えば１の補数または２の補数を用いる場合、入力バイナリデータ値をそれらの符号−大きさ表現に変換することは当業者に公知の直接的演算である。

本発明の上記および更なる態様について、添付図面を参照しながら以下に例示的に詳述する。

図１は、自然数に適用可能な公知の量子化方法により、元の値ｘの関数として、再構築された値ｘ”を実線、元の値ｘを破線で示す（Ｎ_ｍａｘ＝１２８、ｄｑ＝１６）。 図２は、符号付きの値に適用可能な公知の量子化方法により、元の値ｘの関数として、再構築された値ｘ”を実線、元の値ｘを破線で示す。 図３は、固定幅量子化（方法１）を用いるバイナリの符号付きの値に適用可能な公知の量子化方法により、元の値ｘの関数として、再構築された値ｘ”を実線、元の値ｘを破線で示す。 図４は、デッドゾーン（方法２）を用いるバイナリの符号付きの値に適用可能な公知の量子化方法により、元の値ｘの関数として、再構築された値ｘ”実線、元の値ｘを破線で示す。 図５は、本発明による圧縮方法により、元の値ｘの関数として、再構築された値ｘ”を実線、元の値ｘを破線で示す。 図６は、本発明の一実施形態による圧縮方法で用いる量子化装置を概略的に示す。 図７は、本発明の一実施形態による復元方法で用いる逆量子化装置を概略的に示す。 図８は、本発明の好適な一実施形態による方法を概略的に示す。 図９は、本発明の方法が適用される例示的なデータの組を示す。 図１０は、上述のような固定幅量子化（方法１）における課題を示す。

図面の各図は原寸大および一定比率で描画されていない。一般に、図中の同一構成要素は同一参照番号で表記されている。

本発明の第１の構成要素は、画像圧縮の領域で利点をもたらし、余分なビットを必要とせず、上の方法１および方法２に関して述べた課題を解決する量子化アルゴリズムである。この量子化アルゴリズムを「ＧＲＱ」と呼ぶ。

図５は、入力バイナリデータ値が−１２７〜＋１２７のデータ値を含む、本発明による圧縮方法で用いる量子化アルゴリズムを適用した一例を示す。ｘの絶対値をコード化するために用いたビット数は７ビット、すなわちＢ＝７である。絶対量子化値の個数は８であり、すなわち量子化値は３ビットでコード化できるため、ｂ＝３である。本発明によれば、値の範囲は、２^ｂ＋１個の部分範囲（図３の例では１６個の部分範囲）ではなく、２^ｂ＋１−１個の部分範囲（図５の例では１５個の部分範囲）に分割されている。量子化の刻み幅ｄｑは、次式の通りである。

量子化の刻み幅は、従来技術のものよりも僅かに大きい（図１、２、３、４の例では量子化の刻み幅は全て１６である）。以下の表は、ｘの正値（すなわち図５の右上四半分）に対して、結果的に得られた部分範囲を示す。

量子化値は、１を減算することにより部分範囲ｉから得られる。量子化アルゴリズムは、常に量子化値のビットの正確な個数ｂを生成し、従って量子化レベルの関数として予測可能なレートをより高い品質で保証するため、レート割り当てを特徴とする圧縮スキームに適している。これにより、本発明の第２の構成要素であるＧＣＬＩ値（最大コード化ライン指数）と合わせて用いる理想的な量子化アルゴリズムが得られ、段落［００４０］で述べるように効率的なレート割り当て方法が可能になる。

「ビン法」の代替として、次式でも同一量子化値が得られる。

上式の右辺から分かるように、演算は２個の加算および２個のバイナリシフトにより実行可能であり、バイナリシフトは論理ゲートを必要としない。これらの演算を実行するハードウェア構成を図６に示す。シフト演算は、論理ゲートにより容易に実装できる。シフト演算において、分数ビットを保持しなければならない。レジスタシフト法の代替として、参照表により圧縮を実行することができる。参照表法は、Ｂが大き過ぎない場合に最も便利である。参照表は、段落［００１４］の方法を０〜２^Ｂ−１の全ての整数に適用することにより得られる。

逆量子化値は、次式により得られる。

幾何級数から次式が得られる。

興味深いことに、ｙ’はｂ個のビットでコード化されているため、式（２）を簡素化することができる。

ここで、「∨」演算子は「二値論理和」を表す。実際には、上記二値論理和が、ｉ・ｂ位置分シフトされたｂビット値の間で適用されるため、この演算は連続する値のビットの連結に簡略化できる。実際のケースではＢの値はｂの何倍もの大きさにならない。Ｂ＞ｂかつＢ＜２ｂ＋１であれば、図７に示すように、ｙ’＜＜（Ｂ−ｂ）かつｙ’＞＞（２ｂ−Ｂ＋１）のビットを連結するのみでよい。

要約すれば、上の演算は現行技術と同じ複雑度を有している。
・量子化は、｜ｘ｜の２個のシフトされた値を減算し、次いでＬＳＢの後に１ビット加算する。
・逆量子化は、ｙ’のシフトされた値の連結である。
同レベルの量子化であれば、再構築された値の品質の方がより高く、これは本発明により圧縮アルゴリズムの送信における同一ビットレートで品質が向上することを意味する。

典型的なテスト画像の組を方法２（デッドゾーン「ＤＺ」を有する）および本発明に従って圧縮した。圧縮画像と元画像との信号対ノイズ比ＰＳＮＲを１６個のテスト画像に対して比較している。以下の表から、本発明の方法がテスト組の全ての画像について改善が見られることが分かる。

本発明の第２の構成要素は、ビデオストリーム等の入力バイナリデータの圧縮に関する。相関を有する値に対するデータ圧縮方法、典型的には画像圧縮は、以下の２個の特徴を含んでいる。
・データは、格納またはデコーダへ送信するビットの量を減らすために量子化され、
・デコーダが逆量子化の適用を必要とするため、データがどのように量子化されているかに関する情報（Ｂ−ｂ）が量子化データの前に挿入される。結果的に得られる情報はコードストリームと呼ばれる。
例えば、ＤＷＴ（離散的ウェーブレット変換）により生成された係数等のデータはある程度の相関を示すため、これらを再グループ化して、ベクトルまたはブロックに対して共通の量子化レベルを適用してデータの再構築にデコーダが必要とする情報の量を減らすことに利点がある。殆どの場合、送信されるコードストリームの帯域幅は通信チャネルのビットレートにより制約され、または同様に、圧縮ファイルのサイズは記憶媒体の容量に制約される。圧縮率が高いほど再構築されたデータの品質が低くなるため、圧縮アルゴリズムは、最適ビットレートにできるだけ近いコードストリームを生成して利用可能な帯域幅を用いて最高の品質が得られることが重要である。これがレート割り当ての目的であり、所与のビットレートに対して最高の品質が得られるようにデータに適用される量子化レベルを決定する必要がある。レート割り当てにより処理されるデータ構造の選択が最も重要であり、以下の要件を満す必要がある。
・簡潔であること。通常、圧縮はできるだけ速く実現する必要があり、レート割り当てにより処理されるデータの量が多いほど圧縮は遅くなる。
・品質を表すこと。レート割り当ては所与のビットレートの品質を最適化するものであり、品質低下を量子化レベルの関数として推定できなければならない。
・コードストリームに効率的にコード変換可能であること。デコーダは、データの再構築に十分な情報（例えば、各ブロックに正しい逆量子化を適用すること）を必要とする。

Ｎ_ＧＣＬＩ個のデータのベクトルまたはブロックのＧＣＬＩ値は、値の大きさをバイナリ表現でコード化するのに必要な最大ビット数である。従って、−６はｂ１１０（および１個の符号ビット）にコード化され、その絶対値をコード化するために３ビットを必要とする。値（４，９，２，５）を有するブロックは、最大値が９であってｂ１００１にコード化されるため、ＧＣＬＩ＝４である。ゼロのコード化に必要なビット数は０であり、符号を必要としない。更なる例を図９に示す。全てが１５ビットにコード化されて符号ビットを加えた１６個のバイナリデータ値を含む入力バイナリデータを表す。非相関的なデータで生じるように、多くのデータ値は小さく、最上位ビットの大部分はゼロ（グレー領域で表す）である。入力データは、４ワード（Ｎ_ＧＣＬＩ個の＝４）の組にグループ化される。これらの組の各々に対してＧＣＬＩの値が決定される。入力データの組全体に対して、圧縮から得られるデータのサイズ（各組に対して異なるｂの値）が記憶サイズの利用可能な帯域幅の制約を満たすように、ＧＴＬＩの値（ここではＧＴＬＩ＝４）が選択される。これらの組の各々に対して量子化方法が適用されて、結果的に得られたデータがＧＣＬＩの値と共に出力バイナリデータに入れられる。ＧＴＬＩは、データの全ての組で同じ値を有し、一度のみ送信または格納される。ＧＣＬＩ値は上述の要件を十分に満たすため、これらを用いてレート割り当てに際してデータを要約する。推理を示すために、可能なアーキテクチャを図８に示す。すなわち、
・相関するデータをＮ_ＧＣＬＩ個の値のブロックにグループ化し、そこからＧＣＬＩ’を抽出する。
・レート割り当てにおいてＧＣＬＩ値を用いて量子化レベルを決定する。
・データ（ＧＲＱ）に量子化を適用する。
・圧縮データからコードストリーム、および復元に要する情報、本例では、量子化レベルおよびＧＣＬＩを作成する。

ＧＣＬＩは簡潔であり、１個の値で複数の値を含む１個のブロックの最大対数を表すため、コード化に多数のビットを必要としない。典型的に、ＤＷＴの係数をコード化するには１６ビットで十分であり、これは４ビットＧＣＬＩ値が使用できることを意味する。Ｎ_ＧＣＬＩ＝４の場合、レート割り当てにおいて１個の４ビットＧＣＬＩで４個の１６ビット係数を表すことができ、これは１対６４の比率である。これは、隣接値が相関を有しており、大きさが同様であるために効率的であり、従って同一ビット数を用いてこれら全てをコード化することはほぼ最適である。これは、ＧＣＬＩが切り捨てレベルの関数として出力レートを計算するためにレート割り当てに簡潔な情報を提供することを意味する。更に、図９に示すように、ＧＣＬＩ値は実際に局所的な量子化の刻み幅ｄｑを提供する。ＧＴＬＩの切り捨て部分（最大刈り込みレベル指数）が、他のアルゴリズムと同様に各々のサブ帯域に個別に設定されるが、ビットＢの最大数は各ＧＣＬＩにより、従ってＮ_ＧＣＬＩの各グループのデータに対して設定される。この最後の特性により、大きいブロックのゼロより大きい最上位ビットを除去することによりコード化対象であるビット数が減少し、これにより出力ストリームにＧＣＬＩ情報を挿入する（逆量子化に必要）コストを補償することを上回る利点がある。

ＧＣＬＩ法に使用には、段落［０００４］で説明したように、量子化の関数としての予測可能なレートを要する。ＧＲＱ量子化はゼロ値を保持し、量子化値のコード化に要するビット数がｂのままであることを保証するため、レート割り当て処理でのパラメータＧＴＬＩ（各サブ帯域毎の）を介して出力レートを量子化の関数として容易に制御できるようになる。先に示したように、ビットおよびゼロ値の個数を保持する他の量子化スキームのようにデッドゾーンが大きくなる短所がなく、従って復号化に際して平均誤差率が低い。

本発明の方法は、ハードウェア実装が極めて簡単かつ効果的な方法で係数の組を数ステップで圧縮する。圧縮スキームは数ピクセルを同時にコード化するため、提案するコーデックでは複数のピクセルの並列コード化が本質的である。複雑度が低いコーデックで、良好な圧縮効率を維持しながら高いピクセルレートに達することが可能になる。

本発明について、本発明を例示するものであって限定するものでない特定の実施形態の観点から記述してきた。より一般的には、当業者であれば本発明が上で具体的に図示および／または記述した内容に限定されないことが理解されよう。

請求項における参照番号は、請求項の権利保護範囲を限定するものではない。動詞「含む」、「包含する」、「からなる」、その他の任意の類義語、ならびにその各々の活用形を用いた場合であっても、明記した要素以外の要素の存在を排除するものではない。ある要素の前に冠詞「１つの（ａ）」、「１つの（ａｎ）」、または「その」を付与した場合であっても、そのような要素が複数存在することを排除しない。

本発明はまた、以下のように記述することができる。すなわち、本発明は、全てが同じ数であるＢ個のビットでコード化された入力バイナリデータ値ｘの組であって、入力バイナリデータ値が負値を含む場合は符号ビットがカウントされない、入力バイナリデータ値ｘの組を、全てがより少ない数であるｂ個のビットでコード化された出力データ値ｘ’の対応する組であって、符号ビットがカウントされない、出力データ値ｘ’の対応する組に圧縮する方法であって、
ａ）入力バイナリデータ値の組が負値を含む場合、
・各入力バイナリデータ値ｘに対して、ｘの絶対値であるｙ、およびｘの符号であり、１ビットでコード化されたｘ_ｓを決定するステップと、
ｂ）入力バイナリデータ値の組が負値を含まない場合、
・各入力バイナリデータ値ｘに対して、ｘの値であるｙを決定ステップと、
ｃ）量子化の刻み幅ｄｑ

を計算するステップと、
ｄ）ｙの値の範囲［０，２Ｂ−１［を２^ｂ個の部分範囲、
・［０，ＩＮＴ（ｄｑ／２）［である第１の部分範囲
・［ＩＮＴ（（ｉ−３／２）＊ｄｑ）＋１，ＩＮＴ（（ｉ−１／２）*ｄｑ）［である第ｉの部分範囲（ここで、ｉは２〜２^ｂである）
に分割するステップと、
ｅ）ｙの各値に対して、ｙが要素である部分範囲ｉを決定し、およびｙ’＝ｉ−１を計算するステップと、
ｆ）入力バイナリデータ値の組が負値を含む場合、
・各入力バイナリデータ値ｘに対して、ｘ_ｓと共にｙ’の値であるｘ’を決定するステップと、
ｇ）入力バイナリデータ値の組が負値を含まない場合、
・各入力バイナリデータ値ｘに対して、ｙ’の値であるｘ’を決定するステップと
により得られる方法および装置を提供する。

Ｂ ビット数
ｂ ビット数
ｄｑ 量子化の刻み幅
ｘ 値
ｘ’ 量子化値
ｘ” 逆量子化値
ｙ 絶対値
ｙ’ 量子化絶対値
ｙ” 合算結果の整数部分
ε 誤差

Claims (17)

1. 全てが同じ数であるＢ個のビットでコード化された入力バイナリデータ値ｘの組であって、前記入力バイナリデータ値が負値を含む場合は符号ビットがカウントされない、入力バイナリデータ値ｘの組を、全てがより少ない数であるｂ個のビットでコード化された出力データ値ｘ’の対応する組であって、符号ビットがカウントされない、出力データ値ｘ’の対応する組に圧縮する方法において、
   ａ）前記入力バイナリデータ値の組が負値を含む場合、
   ・各入力バイナリデータ値ｘに対して、ｘの絶対値であるｙ、およびｘの符号であり、１ビットでコード化されたｘ_ｓを決定するステップと、
   ｂ）前記入力バイナリデータ値の組が負値を含まない場合、
   ・各入力バイナリデータ値ｘに対して、ｘの値であるｙを決定ステップと、
   ｃ）量子化の刻み幅ｄｑ
   

   

   を計算するステップと、
   ｄ）ｙの値の範囲［０，２^Ｂ−１［を２^ｂ個の部分範囲、
   ・［０，ＩＮＴ（ｄｑ／２）［である第１の部分範囲、
   ・［ＩＮＴ（（ｉ−３／２）＊ｄｑ）＋１，ＩＮＴ（（ｉ−１／２）*ｄｑ）［である第ｉの部分範囲（ここで、ｉは２〜２^ｂである）
   に分割するステップと、
   ｅ）ｙの各値に対して、ｙが要素である部分範囲ｉを決定し、およびｙ’＝ｉ−１を計算するステップと、
   ｆ）前記入力バイナリデータ値の組が負値を含む場合、
   ・各入力バイナリデータ値ｘに対して、ｘ_ｓと共にｙ’の値であるｘ’を決定するステップと、
   ｇ）前記入力バイナリデータ値の組が負値を含まない場合、
   ・各入力バイナリデータ値ｘに対して、ｙ’の値であるｘ’を決定するステップと
   により得られることを特徴とする、方法。
2. 請求項１に記載の方法において、前記ステップｃ）、ｄ）およびｅ）が、固定小数点バイナリ値に対し、
   ・ｙをＢ−ｂビットだけ右方向にシフトし、第１の結果を得るステップと、
   ・ｙをＢ＋１ビットだけ右方向にシフトし、第２の結果を得るステップと、
   ・第１の結果から第２の結果を減算し、第３の結果を得るステップと、
   ・０，５を加算し、第４の結果を得るステップと、
   ・第４の結果の正およびゼロの重みビットを選択し、ｙ’を得るステップと
   を実行することにより行われることを特徴とする、方法。
3. 請求項１に記載の方法において、
   ・ｙの２^Ｂ個の値の各々に対して、ｙ’の対応する値を含む参照表を取得するステップと、
   ・前記組のｙの各値に対して、前記表の索引ｙにおける前記ｙ’の対応する値を決定するステップと
   を含むことを特徴とする、方法。
4. 入力バイナリデータ値を含む入力バイナリデータを、ある限度より小さいボリュームを有する出力バイナリデータに圧縮する方法において、
   ・前記入力バイナリデータ値をＮ_ＧＣＬＩ個の入力バイナリデータ値の組にグループ化するステップと、
   ・前記Ｎ_ＧＣＬＩ個の入力バイナリデータ値の組の各々に対して、
   − 前記組における最大非ゼロビットであって、符号ビットがカウントされない、最大非ゼロビットの指数であるＧＣＬＩを決定するステップと、
   ・全ての前記入力バイナリデータ値に対してＧＣＬＩ−ＧＴＬＩビットをカウントすることにより、前記限度よりも小さいボリュームを有する出力バイナリデータを生成するようにＧＴＬＩの値を選択するステップと、
   ・前記Ｎ_ＧＣＬＩ個の入力バイナリデータ値の組の各々に対して、
   − Ｂ＝ＧＣＬＩかつｂ＝ＭＡＸ（ＧＣＬＩ−ＧＴＬＩ，０）の条件で請求項１乃至３の何れか１項に記載の方法を適用するステップと、
   ・前記ＧＴＬＩを含む出力バイナリデータと、前記Ｎ_ＧＣＬＩ個の入力バイナリデータ値の組の各々に対して、前記ＧＣＬＩの値およびＮ_ＧＣＬＩ個の量子化値ｘ’とを生成するステップと
   を含むことを特徴とする、方法。
5. 請求項４に記載の方法において、前記入力バイナリデータがビデオデータの非相関的な変換から得られることを特徴とする、方法。
6. 請求項４に記載の方法において、Ｎ_ＧＣＬＩが４〜１６に含まれ、好ましくは４に等しいことを特徴とする、方法。
7. 全てが同じ数であるｂ個のビットでコード化された入力バイナリデータ値ｘ’の組であって、可能な符号ビットがカウントされない、入力バイナリデータ値ｘ’の組を、全てがより多い数であるＢ個のビットでコード化された出力データ値ｘ”の対応する組であって、可能な符号ビットがカウントされない、出力データ値ｘ”の対応する組に復元する方法において、
   ａ）
   

   

   を計算するステップと、
   ｂ）前記入力バイナリデータ値の組が負値を含む場合、各入力バイナリデータ値ｘ’に対して、ｘの絶対値であるｙ’、およびｘ’の符号であり、１ビットでコード化されたｘ’_ｓを決定するステップと、
   ｃ）前記入力バイナリデータ値の組が負値を含まない場合、各入力バイナリデータ値ｘ’に対して、ｘ’の値であるｙ’を決定するステップと、
   ｄ）各ｙ’に対して、
   

   

   を計算するステップと、
   ｅ）前記入力バイナリデータ値の組が負値を含む場合、各入力バイナリデータ値ｙ’に対して、ｘ’_ｓと共にｙ”の値であるｘ”を決定するステップと、
   ｆ）前記入力バイナリデータ値の組が負値を含まない場合、各入力バイナリデータ値ｘ’に対して、ｙ”の値であるｘ”を決定するステップと
   を含むことを特徴とする、方法。
8. 請求項７に記載の方法において、前記ステップｄ）が、
   ｉ．ｙ’をＢ−ｂビットだけ左方向にシフトし、第１の結果を得るステップと、
   ｉｉ．第１の結果をｂ＋１ビットだけ右方向にシフトし、第２の結果を得るステップと、
   ｉｉｉ．第１の結果に第２の結果を加算し、合算結果を得るステップと、
   ｉｖ．第２の結果を第１の結果にコピーするステップと、
   ｖ．第２の結果がゼロを下回るまでステップｉｉ．〜ｉｖ．を繰り返すステップと、
   ｖｉ．合算結果の整数部分としてｙ”を計算するステップと
   を含むことを特徴とする、方法。
9. 請求項７に記載の方法において、ｂ≦Ｂ／２であり、および前記ステップｄ）が、
   ｉ．ｙ’をＢ−ｂビットだけ左方向にシフトし、第１の結果を得るステップと、
   ｉｉ．第１の結果をｂ＋１ビットだけ右方向にシフトし、第２の結果を得るステップと、
   ｉｉｉ．第１の結果に第２の結果を加算し、合算結果を得るステップと、
   ｉｖ．合算結果の整数部分としてｙ”を計算するステップと
   を含むことを特徴とする、方法。
10. 請求項７に記載の方法において、
    ・ｙ’の２^ｂ個の値の各々に対して、ｙ”の対応する値を含む参照表を取得するステップと、
    ・前記組のｙ’の各値に対して、前記表の索引ｙ’における前記ｙ”の対応する値を決定するステップと
    を含むことを特徴とする、方法。
11. Ｎ_ＧＣＬＩ個の入力バイナリデータ値の組を含む入力バイナリデータを復元する方法であって、各組が、復元されたバイナリデータ値のビット数であるＢの値と、前記入力バイナリデータ値の個数であって、可能な符号ビットがカウントされない、前記入力バイナリデータ値の個数であるｂの値とを含む、方法において、
    ・復元されたバイナリデータ値を得るために、請求項７に記載の方法を適用するステップと、
    ・前記復元されたバイナリデータ値を含む出力バイナリデータを生成するステップと
    を含むことを特徴とする、方法。
12. 請求項１１に記載の方法において、前記復元されたバイナリデータ値が、所与の長さを有するワードを得るために「０」個のビットで補完されていることを特徴とする、方法。
13. 請求項７に記載の復元方法の使用において、請求項１乃至６の何れか１項に記載の圧縮方法により得られる入力バイナリデータ値ｘ’の組を復元するためであることを特徴とする、使用。
14. 全てが同じ数のビットでコード化された入力バイナリデータ値ｘの組を、全てがより少ない数のビットでコード化された出力データ値ｘ’の対応する組に圧縮する装置において、請求項１に記載の方法を実行するプログラムコードを含むことを特徴とする、装置。
15. 全てが同じ数のビットでコード化された入力バイナリデータ値ｘの組を、全てがより少ない数のビットでコード化された出力データ値ｘ’の対応する組に圧縮する装置において、請求項２に記載の方法を実行するハードウェアを含むことを特徴とする、装置。
16. 全てが同じ数のビットでコード化された入力バイナリデータ値ｘ’の組を、全てがより多い数のビットでコード化された出力データ値ｘ”の対応する組に復元する装置において、請求項７に記載の方法を実行するプログラムコードを含むことを特徴とする、装置。
17. 全てが同じ数のビットでコード化された入力バイナリデータ値ｘ’の組を、全てがより多い数のビットでコード化された出力データ値ｘ”の対応する組に復元する装置において、請求項７に記載の方法を実行するハードウェアを含むことを特徴とする、装置。

Images