情報通信システム（8） http://www10. plala. or 情報通信システム（8） http://www10.plala.or.jp/katofmly/chiba-u/ 2016年6月21日　火曜日 　午後4時10分～5時40分 NTT-IT Corp. 加藤 洋一

課題１ 今までの講義や見学、あるいは、情報通信に関して普段から疑問に思っていることなどから、各自質問を３つ用意し、EMailにて講師に提出すること。 期限は、7月5日とします。 講師のメールアドレスは、kato（ドット）yoichi (アットマーク) ntt-it（ドット）co（ドット）jp です。 質問は、対象の理解を深めることにつながるようなものを期待しています。

（復習）情報を送るということ たとえば、文字を送りましょう 一般化すると、 送信側 How are you? 001001010010…. 一文字読み取る 文字に符号を割り当てる 符号を送る 001001010010…. 受信側 符号を受け取る 符号から文字を再現する 提示（再生）する 001001010010…. How are you? 一般化すると、 送信側（蓄積側） 事象が起きる 事象に符号を割り当てる 送る（蓄積する） 受信側（再生側） 符号を受け取る 符号から事象を再現する 提示（再生）する 事象をなんとするか？ 一文字、音楽の一サンプル、画像の一画素、、、二文字、三文字、、

一文字あたりの符号量を如何に小さくするか？ 符号量はどうなるか？ 送信側 How are you? 一文字読み取る 文字に符号を割り当てる 符号を送る 001001010010…. 受信側 符号を受け取る 符号から文字を再現する 提示（再生）する 001001010010…. How are you? 総符号量 ＝ 伝送する事象の数 × 一事象あたりの符号量 一文字あたりの符号量を如何に小さくするか？ 場合の数（上記の場合には、文字の種類の数）をNとする。 となる最小の長さ m の固定長符号で表現可能（一文字あたりm ビット） ただし、通常固定長符号は総符号量を最小にする符号ではない！

符号には固定長の他に、可変長符号がある。 （復習）効率的な符号化（可変長符号化） 符号には固定長の他に、可変長符号がある。 例： 袋には4種類の玉が入っている。赤と黒は10個ずつ、 白は20個、黄色は、40個とする。全部で80個。玉をひとつ取り出したときの発生 確率は、黄色 50%、白25%、赤12.5%、黒12.5%である。 以下のような符号を割り振る。 黄色 0 白 10 赤 110 黒 111 玉を16回取り出したところ（出したら元に戻してかきまぜる） 黄 白 黒 黄 黒 白 黄 赤 黄 白 黄 白 黄 赤 黄 黄 とでた。これを符号化すると、 0 10 111 0 111 10 0 110 0 10 0 10 0 110 0 0 となる。詰めて表示すると、 0101110111100110010010011000 (total 28bit) これを復号してみる。左のビットから順番に見ていくと、まず0なので直ちに決まって黄、次は1なので決まらずさらに次を見ると10つまり白、というように、正しく復号できる。 場合の数は4なので、固定長符号なら2ビット、16シンボル分では32ビットとなる。可変長符号化の場合には28ビットだったので、効率が上がったことが分かる。 （黄8回、白4回、赤2回、黒2回 発生確率どおりです）

（復習）情報量、情報エントロピー、可変長符号化 ある事象の生起確率が p のとき、その事象が生起したときの情報量は -log p と定義される。 0＜p ＜1 なので、情報量は正の実数となる。 情報エントロピーとは、情報量の期待値。即ち、 bit 対数の底が2のとき、単位はbit（びっと）という P=0.5のとき1ビット p

（復習）エントロピーの性質 赤黒の生起確率は0.5のとき情報エントロピーは1bit entropy ２つの事象の生起確率とエントロピー 生起確率が 赤 0.9 黒0.1のとき p1 ( = 1 – p2) 一般に、場合の数をNとすると、それぞれの事象の発生確率が1/Nのとき（即ち、全て同じとき）、エントロピーが最大となり、その値は、log2(N)となる。逆に、発生確率が「片寄る」と、エントロピーは減る。

発生確率を偏らせる 例えば、画像を画素ごとにその画素値を符号化する場合 頻度 頻度 …. …. ０ 例えば、画像を画素ごとにその画素値を符号化する場合 順に差分を符号化する場合（受信側で一つ前の画素の値と加算すれば元の値に戻る）

相関関数について学び、実際の画像の自己相関関数を求めた。画像の自己相関は大きいことを確認した。 前回の講義 画像の基本的な統計的性質を調べた。 平均、分散、エントロピー、RGBからYUVへの変換 相関関数について学び、実際の画像の自己相関関数を求めた。画像の自己相関は大きいことを確認した。 相関が大きいということは、「冗長である」ということ。ここに、情報量圧縮の可能性がある。 「冗長性」を減らす方法として、予測符号化について学習した。予測誤差信号は元の画像に比べ自己相関が大幅に減少することを確かめた。 予測方式を用いて実際に画像情報量圧縮を行った。4分の1程度の圧縮では画像の劣化はほとんど認識されなかったが、10分の1以上の圧縮では、画像の顕著な劣化が見られた。 しかし、JPEG方式には及ばない

予測符号化の原理 既に符号化した（伝送した）画素から次の画素を予測する。 受信側でも同じ計算ができる（予測は、既に送った画素から行うので） Y(i-1, j-1) Y(i, j-1) Y(i-1, j) Y(i, j) 既に符号化した（伝送した）画素から次の画素を予測する。 符号化済み これから符号化 Y’(I, j) = Y(i-1, j) or Y’(I, j) = Y(i-1, j) + Y(I, j-1) – Y(i-1, j-1) 受信側でも同じ計算ができる（予測は、既に送った画素から行うので） 予測誤差 E (I ,j) = Y (I, j) – Y’(I, j) 予測誤差のみ送れば、受信側でも同じ値を再現できる。 （予測誤差は量子化して送る）

量子化も含めた予測符号化 Y (I, j) E (I, j) Eq (I, j) 予測誤差 量子化された予測誤差 画素値を順に入力 量子化 出力（予測誤差のみ伝送する。量子化インデックスをエントロピー符号化） 送信側 予測値 Y’ (I, j) 入力 Y (I, j) 予測誤差 Y ‘(I, j) 再生値 Yr (I, j) 過去に再生された画素値から次の画素値を予測する 予測値 Yr (I, j) = Y’ (I, j) + Eq (I, j) Yr (I-1, j-2), Yr (I, j-1), Yr (I-1, j) …. 受信側 Eq (I, j) Yr (I, j) Yr (I, j) = Y’ (I, j) + Eq (I, j) 量子化された予測誤差（量子化インデックスを復号） 再生した画素値 Y’ (I, j) 過去に再生された画素値から次の画素値を予測する 予測値 Yr (I-1, j-2), Yr (I, j-1), Yr (I-1, j) ….

圧縮符号化の構成（再掲） 音声、音楽、画像の各標本値は、他の近隣の標本値と関連がある。即ち、冗長性がある。最初に、信号の性質に着目して、冗長性を削減することで情報量を減らす。 予測、直交変換など 音声や画像では、完全に再生できなくても支障がない場合が多い。「完全に再生する」ことをあきらめる事で、さらに情報量を削減する。 量子化 最終的に得られた値（シンボル）を効率よくビット列にする。 エントロピー符号化 「完全に再生できない」場合の元信号との差を「符号化雑音」という。これを目立たせないように、復号の後で何らかの処理を加える。 ポストフィルター

予測符号化方式についてもう少し詳しく調べる 圧縮率を高める、あるいは、画像の劣化を低減するような何か良い工夫はないか？ 出力画像を良く見てみる。 予測誤差出力を良く見てみる。 まず、再生画像は、空の平坦な部分の劣化が激しいことに注目。これはなぜか？人間の視覚特性は、なだらかに変化する部分では敏感だが、急激に変化する部分ではそうでもない 量子化の工夫。なだらかに変化する、つまり、予測誤差が小さい。急激に変化する、つまり、予測誤差が大きい。 予測誤差が小さいときには細かな量子化、予測誤差が大きいときには粗い量子化をしたらどうか？

予測誤差の量子化方法を改良する 量子化出力 量子化出力 量子化代表値 ： 真値 （予測誤差） 真値 （予測誤差） 一様量子化 一様でない量子化 予測誤差が大きいときには粗く、小さいときには細かく量子化できる

予測誤差の量子化方法の改良 量子化ステップ値 （非一様の場合は、最小のステップ値）

予測誤差信号（量子化済み）をさらに詳しく調べる 画像を確認（量子化ステップ８のとき） ゼロがたくさん続く場合が多い ０の長さを「事象」として捉える。 ランレングス符号化という 今回は、０のランレングスと次の非ゼロの予測誤差を結合したものをシンボルとして符号化する 普通に可変長符号化する場合 1 0 0 2 3 0 0 0 5 0 1 0 0 0 0 0 2 0 0 4 0 0 5 0 0 0 2 1 0 0 0 1 (32事象) ランレングス符号化を使う場合 1 2-0 2 3 3-0 5 1-0 1 5-0 2 2-0 4 2-0 5 3-0 2 1 3-0 1 (19事象) ０のランレングス＋次の非ゼロを結合してシンボルとする場合 0-1 2-2 0-3 3-5 1-1 5-2 2-4 2-5 3-2 0-1 3-1 (11事象) 「0が連続して生起しやすい」という「冗長性」を削減することができる。 （ランレングスを使うことで、事象の数を減らしたことになる）

ランレングスによる改善（非一様量子化） 量子化ステップ値 同じ量子化（即ち、全く同じ再生画像）でも圧縮率を上げることができた

２画素ずつ対にして、その値を２次元平面上にプロットしてみる。 「冗長性」を減らす別の方法＝直交変換 ２画素ずつ対にして、その値を２次元平面上にプロットしてみる。 a b b ２画素ずつ対にして値の分布を見る。 a 隣り合う画素値は近いので上記のようになるだろう

2次元の直交変換 a b α β 45度

2次元の直交変換 b α β －45度 a

2次元の直交変換 画素 ａ のヒストグラム α のヒストグラム 座標変換 (座標軸を45度回転) β のヒストグラム α のヒストグラム 座標変換 (座標軸を45度回転) 画素 ｂ のヒストグラム β のヒストグラム βのヒストグラムは、頻度が偏っている即ち、エントロピーは小さい

画素を２つずつペアにして2次元空間上で表したとき、45度座標を回転させると情報量圧縮の効果がありそうなことが分かった。 Ｎ次元の直交変換 画素を２つずつペアにして2次元空間上で表したとき、45度座標を回転させると情報量圧縮の効果がありそうなことが分かった。 もっと多くの画素をグループにして、同様なことができないか？ 鍵は、Ｎ次元の座標軸回転で、有意義な回転方法を探すことである。

Ｎ次元の直交変換 Ｎ次元の直交座標の回転を考える 各軸の直交性を保ったまま回転する 座標軸上の単位ベクトルを考える 各座標軸上の単位ベクトル間の内積は０（座標軸は互いに直交しているから） N次元空間上の一点をベクトルで表す。そのベクトルの各座標軸の成分は、そのベクトルと、各座標軸の単位ベクトルの内積で与えられる。 (a,b)・(0.707,0.707)=0.707(a+b)=α (a,b) ・(-0.707,0.707)=0.707(-a+b)=β (a, b) b (a, b) (a,b)・(1,0)=a (a,b) ・(0,1)=b α (0,1) (0.707, 0.707) (-0.707, 0.707) a β (1,0)

Ｎ次元の直交変換

内積が分からない人はいないでしょうが。。。

Ｎ次元直交変換の条件

離散フーリエ変換はどうか？

離散コサイン変換（ＤＣＴ）

画像は2次元信号であるため、2次元DCTを適用する。 8×8画素からなる画像の2次元DCTの例。 平均値分 終わり まず、画素を横方向にひとまとめにし、それぞれの行にDCTをかける。 次に、横方向1次元DCTの計算結果を縦方向にひとまとめにし、それぞれの列に再度DCTをかける。 DCT後により計算されたベクトル、あるいは行列をDCT係数という

2次元DCTの基底 8個の要素 N=8のとき 合計、８＊８＝６４個の基底がある 左上の基底と入力ブロックの内積を計算することは、入力ブロックの平均値を計算することに等しい。 フーリエ変換のように色々な（空間）周波数成分があることが分かる

2次元DCTの考え方 8×8のDCT係数 8×8の画素からなるブロック 8×8（64）次元の空間の直交基底 それぞれの基底との内積を計算（基底も8×8の大きさを持つ） ブロックの平均値成分（DC成分） 各基底ベクトル（行列）に対応する成分（AC成分）

2次元DCTを利用した符号化方式 ブロックに分割（８×８画素） 入力画像 1ブロック（ ８×８ ）

DCT係数にはどれほどの「冗長性」が残っているだろうか？ そのほかの成分（AC成分とも言います）には大きな冗長性はないと考えられる。 量子化の考え方は？ DC成分の量子化が粗いと、なだらかな領域（例えば青空）で、ブロック間の境界が見えてしまう（ブロック雑音といいます）。 AC成分は、DC成分より粗い量子化でも良いと思われる。

画像のDCT係数の性質（標準偏差） Std dev Y 435.061 112.259 70.235 51.515 39.365 31.007 23.230 17.475 113.350 55.339 40.926 32.727 26.289 21.764 17.205 13.880 73.523 41.108 31.240 25.211 21.182 17.574 14.227 11.782 49.819 30.061 23.832 20.728 17.763 14.154 11.489 9.696 38.201 23.288 19.332 16.947 15.460 12.012 9.592 7.907 29.473 17.720 15.089 12.863 11.205 9.678 7.789 6.137 21.159 13.279 11.008 9.517 8.481 7.171 6.169 4.789 14.451 9.087 7.810 6.668 5.913 5.119 4.065 3.326 Std dev U 184.388 26.739 14.236 10.404 8.395 8.278 7.089 7.588 29.582 14.946 10.636 8.279 7.280 6.637 6.090 6.443 16.200 11.386 8.672 7.121 6.686 5.848 5.343 5.654 11.183 9.356 7.624 6.238 5.666 5.292 5.450 5.170 8.874 7.421 6.960 6.109 5.670 5.436 4.827 4.808 8.310 6.845 6.467 5.536 5.688 5.013 5.412 4.886 7.620 6.106 6.256 5.275 5.052 5.020 5.110 5.127 6.638 6.219 6.501 5.553 5.169 5.082 5.133 5.009 左上ほど値が大きい。つまり、低次成分ほどパワーが大きいことを示している。

DCT係数の自己相関 このような見方では、相関はほとんどないことが分かる 1.000 0.003 -0.025 -0.002 -0.006 -0.005 0.003 -0.040 -0.003 0.002 0.001 0.000 -0.001 0.001 0.000 0.001 -0.030 -0.000 0.002 -0.000 -0.000 -0.001 0.001 0.003 -0.002 0.000 -0.000 -0.001 0.000 -0.001 0.000 0.001 -0.007 -0.001 0.000 0.000 0.001 0.001 -0.001 0.001 -0.009 -0.001 0.001 0.000 0.001 0.000 -0.000 0.000 0.004 0.000 0.000 0.001 -0.001 -0.001 0.001 0.001 -0.055 0.000 0.002 0.001 -0.001 0.001 0.000 0.005 このような見方では、相関はほとんどないことが分かる つまり、DCTは、ブロック内の画素間の相関をほとんど取り去るような（うまい）直交変換であることが分かる。

平均値分の自己相関 では、ブロック間の各係数同士の相関はどうであろうか？ 平均値分だけ集めて画像とし、その自己相関を計算してみた 1.000 0.837 0.705 0.618 0.561 0.529 0.492 0.465 0.819 0.729 0.635 0.566 0.519 0.484 0.452 0.433 0.656 0.618 0.556 0.505 0.466 0.434 0.411 0.398 0.580 0.559 0.513 0.471 0.439 0.411 0.393 0.382 0.520 0.506 0.478 0.443 0.417 0.396 0.381 0.369 0.482 0.470 0.449 0.421 0.405 0.392 0.382 0.372 0.439 0.429 0.414 0.400 0.389 0.382 0.373 0.360 0.393 0.386 0.372 0.362 0.354 0.353 0.344 0.326 まだかなりの相関（つまり冗長性ですね）が残っていることが分かる。 DCT係数の（０，０）成分のみ集める ・・・・ 縦横1/8に縮小されたような画像が得られる

DCT係数の自己相関（２） DCT係数の（０，１）成分のみ集めて自己相関を計算した。結構大きな相関が残っている。 1.000 -0.200 -0.003 -0.078 -0.036 0.031 -0.061 0.019 0.523 -0.109 0.017 -0.052 -0.018 0.006 -0.053 0.040 0.201 -0.046 0.029 -0.024 0.006 -0.028 -0.025 0.030 0.082 -0.016 0.027 -0.031 0.007 -0.025 0.016 0.003 0.033 -0.006 0.017 -0.041 0.010 -0.010 0.029 0.004 0.005 0.009 -0.012 -0.053 0.010 0.013 0.010 0.020 0.015 0.024 -0.016 -0.062 0.008 0.030 0.005 0.024 0.022 0.019 0.000 -0.070 0.006 0.015 0.024 -0.001 同様に、DCT係数の（1，0）成分のみ集めて自己相関を計算した。 1.000 0.562 0.376 0.293 0.245 0.218 0.181 0.161 -0.127 -0.052 -0.032 -0.010 -0.006 -0.001 0.001 0.006 -0.139 -0.103 -0.077 -0.054 -0.025 -0.028 -0.020 -0.023 0.044 0.058 0.057 0.031 0.014 0.031 0.028 0.033 -0.016 -0.007 0.014 0.022 0.019 -0.004 -0.018 -0.022 -0.022 -0.037 -0.038 -0.049 -0.036 -0.015 0.007 0.003 -0.034 -0.022 0.012 0.032 0.012 0.006 0.007 0.011 0.058 0.071 0.057 0.054 0.052 0.036 -0.001 -0.016

2次元DCT画像圧縮符号化方式を設計する 知見１： 高次のAC成分は分散が小さい。量子化後は０になる確率が大きい。 予測符号化のときのように、０のランレングス＋次にくる非ゼロの値を セットで事象とし、ハフマン符号化しよう。 知見２： DC成分にはまだ大きな自己相関が残っている。 方針２： DC成分は予測符号化しよう 知見３： DC成分の量子化が粗いと、なだらかに変化する部分で ブロック境界が見えてくる。 方針３： DC成分の量子化は、AC成分の半分の粗さとする 知見4： AC成分でも、（1,0）や(0,1)のような低次の成分にはまだ ある程度の自己相関が残っている。 方針４： このような性質を利用した符号化方式はまだ（講師が知る限り） 報告されていない。今後の研究対象か？

DC成分の予測符号化 このようにして得られた画像上で、予測符号化を行う DCT係数の（０，０）成分（DC成分）のみ集める ・・・・ 縦横1/8に縮小されたような画像が得られる このようにして得られた画像上で、予測符号化を行う

各ブロックのエントロピー符号化 係数（量子化インデックス）ごとのエントロピーを計算 各ブロックのDC成分、各AC成分ごとに量シカゴの大きさのヒストグラムを作り、エントロピーを計算する。 [ 0 2 5 7 11 15 25 34] [ 1 4 9 12 16 21 31 38] [ 3 8 13 18 22 29 36 45] [ 6 14 20 23 28 35 44 50] [10 19 24 30 32 41 47 54] [17 27 33 39 43 48 53 58] [26 37 42 46 51 55 57 61] [40 49 52 56 59 60 62 63] 係数の（量子化インデックスの）エントロピーの大きい順に並べる この順序で、（０ランレングス＋非ゼロ値）をシンボルとして、ハフマン符号化する

圧縮結果 KBytes 量子化ステップサイズ（AC成分用）

少々駆け足だったので消化不良かもしれません。講義資料を読み返したり、実際のPythonプログラムを読んだりして補ってください。 圧縮符号化のまとめ 既存の技術の説明ではなく、圧縮符号化の考え方の方法論を具体例を多く交えて説明しました。また、その中で、ディジタル信号処理に頻繁に現れる事項を学びました。 少々駆け足だったので消化不良かもしれません。講義資料を読み返したり、実際のPythonプログラムを読んだりして補ってください。 なお、本講義で設計、実装した画像符号化方式とJPEG方式はかなり近いです。 講師はJPEG標準化の初期の会合に出席しました。