レート歪み理論

レート歪み理論は、非可逆データ圧縮の理論的基礎を提供する情報理論の主要分野です。レートRで測定される、チャネルを介して通信されるべきシンボルあたりの最小ビット数を決定する問題に対処します。これにより、ソース (入力信号) は、予想される歪みD を超えることなく、受信機 (出力信号) で近似的に再構築されます。

レート歪み理論は、非可逆圧縮方式を使用してどの程度の圧縮が達成できるかを解析的に表現します。既存のオーディオ、音声、画像、ビデオの圧縮技術の多くには、レート歪み関数の一般的な形状を利用した変換、量子化、ビットレート割り当て手順があります。

レート歪み理論は、情報理論の基礎研究の中で クロード・シャノンによって考案されました。

レート歪み理論では、レートは通常、保存または送信されるデータサンプルあたりのビット数として理解されています。歪みの概念は、継続的な議論の対象です。^[1]最も単純なケース（ほとんどの場合に実際に使用されている）では、歪みは、入力信号と出力信号の差の2乗の期待値（つまり、平均二乗誤差）として定義されます。ただし、ほとんどの非可逆圧縮技術は、人間の消費者（音楽を聴いたり、画像やビデオを視聴したり）が知覚するデータに対して機能することがわかっているため、歪みの尺度は、人間の知覚、場合によっては美的感覚に基づいてモデル化するのが望ましいです。可逆圧縮での確率の使用と同様に、歪みの尺度は、ベイズ推定や決定理論で使用される損失関数と最終的に同一視できます。オーディオ圧縮では、知覚モデル（したがって知覚歪みの尺度）は比較的よく開発されており、 MP3やVorbisなどの圧縮技術で日常的に使用されていますが、レート歪み理論に含めるのは簡単ではないことがよくあります。画像およびビデオの圧縮では、人間の知覚モデルが十分に開発されておらず、組み込みは主にJPEGおよびMPEG の重み付け (量子化、正規化) マトリックスに限定されています。

歪み関数は、近似シンボルによってシンボルを表現するコストを測定します。一般的な歪み関数には、ハミング歪みと二乗誤差歪みがあります。 ${\displaystyle x}$${\displaystyle {\hat {x}}}$

${\displaystyle d(x,{\hat {x}})={\begin{cases}0&{\text{if }}x={\hat {x}}\\1&{\text{if }}x\neq {\hat {x}}\end{cases}}}$

${\displaystyle d(x,{\hat {x}})=\left(x-{\hat {x}}\right)^{2}}$

レートと歪みを関連付ける関数は、次の最小化問題の解として見つかります。

${\displaystyle \inf _{Q_{Y\mid X}(y\mid x)}I_{Q}(Y;X){\text{ subject to }}D_{Q}\leq D^{*}.}$

ここで、テストチャネルと呼ばれることもある は、与えられた入力（元の信号）に対する通信チャネル出力（圧縮信号）の条件付き確率密度関数（PDF）であり、 はとの間の相互情報量であり、次のように定義される。 ${\displaystyle Q_{Y\mid X}(y\mid x)}$ ${\displaystyle Y}$${\displaystyle X}$${\displaystyle I_{Q}(Y;X)}$${\displaystyle Y}$${\displaystyle X}$

${\displaystyle I(Y;X)=H(Y)-H(Y\mid X)\,}$

ここで、およびはそれぞれ、出力信号Yのエントロピーと、入力信号が与えられたときの出力信号の 条件付きエントロピーです。${\displaystyle H(Y)}$${\displaystyle H(Y\mid X)}$

${\displaystyle H(Y)=-\int _{-\infty }^{\infty }P_{Y}(y)\log _{2}(P_{Y}(y))\,dy}$

${\displaystyle H(Y\mid X)=-\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }Q_{Y\mid X}(y\mid x)P_{X}(x)\log _{2}(Q_{Y\mid X}(y\mid x))\,dx\,dy.}$

この問題は、与えられたレート制約に対して達成可能な歪みの最小値を求める歪み率関数として定式化することもできます。関連する式は次のとおりです。

${\displaystyle \inf _{Q_{Y\mid X}(y\mid x)}E[D_{Q}[X,Y]]{\text{ subject to }}I_{Q}(Y;X)\leq R.}$

2 つの定式化により、互いに逆関数となる関数が得られます。

相互情報量は、受信者が送信者の信号について持つ「事前の」不確実性（H（Y））の尺度として理解することができ、送信者の信号に関する情報を受け取った後に残る不確実性（）によって減少します。もちろん、不確実性の減少は、伝達される情報量によるものであり、それは です。 ${\displaystyle H(Y\mid X)}$${\displaystyle I\left(Y;X\right)}$

たとえば、通信がまったく行われない場合は、およびとなります。あるいは、通信チャネルが完全で、受信信号が送信側の信号と同一である場合は、およびとなります。 ${\displaystyle H(Y\mid X)=H(Y)}$${\displaystyle I(Y;X)=0}$${\displaystyle Y}$${\displaystyle X}$${\displaystyle H(Y\mid X)=0}$${\displaystyle I(Y;X)=H(X)=H(Y)}$

レート歪み関数の定義では、およびはそれぞれ、与えられた最大歪みと規定された最大歪みに対するとの間の歪みです。平均二乗誤差を歪みの尺度として使用する場合、次の式が得られます（振幅-連続信号の場合）。 ${\displaystyle D_{Q}}$${\displaystyle D^{*}}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle Q_{Y\mid X}(y\mid x)}$

${\displaystyle D_{Q}=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }P_{X,Y}(x,y)(x-y)^{2}\,dx\,dy=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }Q_{Y\mid X}(y\mid x)P_{X}(x)(x-y)^{2}\,dx\,dy.}$

上記の式が示すように、レート歪み関数を計算するには、PDF の観点から入力を確率的に記述する必要があり、次に、与えられた歪みに対してレートを最小化する条件付き PDF を見つけることを目的とします。これらの定義は、離散ランダム変数と混合ランダム変数も考慮するように測度理論的に定式化できます。 ${\displaystyle X}$${\displaystyle P_{X}(x)}$${\displaystyle Q_{Y\mid X}(y\mid x)}$${\displaystyle D^{*}}$

この最小化問題に対する解析的な解を得ることは、いくつかの例外を除いて難しい場合が多く、そのような例外については次に最もよく知られている例を 2 つ示します。あらゆるソースのレート歪み関数は、いくつかの基本的な特性に従うことが知られています。最も重要なのは、それが連続した単調減少の凸(U)関数であり、したがって例の関数の形状が典型的であることです (実際の測定されたレート歪み関数でさえ、非常によく似た形になる傾向があります)。

この問題に対する解析的な解は少ないが、これらの関数には上限と下限があり、有名なシャノン下限（SLB）は、二乗誤差と記憶のない情報源の場合、有限微分エントロピーを持つ任意の情報源に対して、

${\displaystyle R(D)\geq h(X)-h(D)\,}$

ここで、h ( D ) は分散 D のガウス確率変数の微分エントロピーです。この下限は、メモリやその他の歪み測定を持つソースに拡張できます。SLB の重要な特徴の 1 つは、幅広いソースの歪みが低い領域で漸近的にタイトであり、場合によってはレート歪み関数と実際に一致することです。シャノン下限は、通常、任意の 2 つの数値間の歪みが、これら 2 つの数値の値の差の関数として表せる場合に見つかります。

リチャード・ブラハットが共同発明したブラハット・アリモトアルゴリズムは、任意の有限入力/出力アルファベットソースのレート歪み関数を数値的に取得するための優れた反復手法であり、これをより一般的な問題インスタンスに拡張するための多くの研究が行われてきました。

メモリを備えた定常ソースを扱う場合、レート歪み関数の定義を変更する必要があり、長さが増加するシーケンスで取られる制限の意味で理解する必要があります。

${\displaystyle R(D)=\lim _{n\rightarrow \infty }R_{n}(D)}$

どこ

${\displaystyle R_{n}(D)={\frac {1}{n}}\inf _{Q_{Y^{n}\mid X^{n}}\in {\mathcal {Q}}}I(Y^{n},X^{n})}$

そして

${\displaystyle {\mathcal {Q}}=\{Q_{Y^{n}\mid X^{n}}(Y^{n}\mid X^{n},X_{0}):E[d(X^{n},Y^{n})]\leq D\}}$

ここで、上付き文字はその時点までの完全なシーケンスを示し、下付き文字の 0 は初期状態を示します。

が分散 のガウス確率変数であると仮定し、信号の連続サンプルが確率的に独立している（または同等に、ソースがメモリを持たない、または信号が無相関である）と仮定すると、レート歪み関数の次 の解析式が得られます。${\displaystyle X}$ ${\displaystyle \sigma ^{2}}$${\displaystyle X}$

${\displaystyle R(D)={\begin{cases}{\frac {1}{2}}\log _{2}(\sigma _{x}^{2}/D),&{\text{if }}0\leq D\leq \sigma _{x}^{2}\\0,&{\text{if }}D>\sigma _{x}^{2}.\end{cases}}}$   ^[2]

次の図は、この機能がどのように見えるかを示しています。

レート歪み理論によれば、「グレーゾーン外で動作する圧縮システムは存在しない」とされています。実用的な圧縮システムが赤（下限）境界に近いほど、パフォーマンスは向上します。原則として、この境界はコーディングブロック長パラメータを増やすことによってのみ達成できます。ただし、単位ブロック長でも、レート歪み関数から実用的な距離で動作する優れた（スカラー）量子化器が見つかることがよくあります。^[3]

このレート歪み関数は、ガウス記憶なしソースにのみ適用されます。ガウス ソースは、エンコードするのが最も「難しい」ソースであることが知られています。つまり、与えられた平均二乗誤差に対して、最も多くのビット数が必要になります。たとえば、画像を処理する実際の圧縮システムのパフォーマンスは、示されている下限を下回る場合があります。 ${\displaystyle R\left(D\right)}$

ハミング歪みを伴うベルヌーイ乱数変数のレート歪み関数は次のように表されます。

${\displaystyle R(D)=\left\{{\begin{matrix}H_{b}(p)-H_{b}(D),&0\leq D\leq \min {(p,1-p)}\\0,&D>\min {(p,1-p)}\end{matrix}}\right.}$

ここで はバイナリエントロピー関数を表します。 ${\displaystyle H_{b}}$

レート歪み関数のプロット: ${\displaystyle p=0.5}$

ある情報源に関する情報を、歪みがD を超えない範囲でユーザーに伝送したいとします。レート歪み理論によれば、情報源からの情報は少なくともビット/シンボルでユーザーに届く必要があります。また、シャノンのチャネル符号化定理から、情報源のエントロピーがHビット/シンボルで、チャネル容量がC (ただし) の場合、この情報を特定のチャネルで伝送すると ビット/シンボルが失われることが分かっています。ユーザーが最大歪みDで情報を再構築できるという希望を持つためには、伝送中に失われた情報が最大許容損失ビット/シンボルを超えないという要件を課す必要があります。これは、チャネル容量が少なくとも と同じ大きさでなければならないことを意味します。^[4]${\displaystyle R(D)}$${\displaystyle C<H}$${\displaystyle H-C}$${\displaystyle H-R(D)}$${\displaystyle R(D)}$

• Blahut-Arimoto アルゴリズム – 情報理論におけるアルゴリズムのクラス
• データ圧縮 – デジタルデータのコンパクトなエンコード
• 非相関 – 1つまたは複数の信号内の相関を減らすプロセス
• レート歪み最適化 - ビデオ圧縮で使用される決定アルゴリズムPages displaying wikidata descriptions as a fallback
• 球詰め – 幾何学的構造
• ホワイトノイズ – 信号処理における信号の種類

• Marzen, Sarah; DeDeo, Simon. 「PyRated: レート歪み理論のための Python パッケージ」。PyRatedは、レート歪み理論における最も基本的な計算、つまり、ユーティリティ関数 (歪み行列) とラグランジュ乗数betaが与えられた場合に「コードブック」と伝送レートRを決定する、非常にシンプルな Python パッケージです。
• VcDemo 画像およびビデオ圧縮学習ツール