Download

画像圧縮
有村秀孝
1
画像圧縮の意義
二次元または三次元であり、さらに時間変化も含めると四次元。
カラー画像なら３倍のデータ量
＝＞データ量は膨大
＝＞圧縮は不可欠
例：マルチスライスＣＴ画像＝512×512×2×300＝150MB
150MB×20人／日＝３０００ＭＢ＝２．９ＧＢ／日
３０００ＭＢ×２６０日＝７６２ＧＢバイト
2
画像圧縮
圧縮 → 解凍
可逆 → 元に戻る
非可逆→ 元に戻らない（でも圧縮率が高い）
可１/2 ～ 1/3
非 1/10 ～ 1/100
JPEG（ジェイペグ）、Wavelet(ウェーブレット)
DCT → DFTの親戚
Wavelet → FTの親戚だけど、直交関数系が異なる。
3
画像符号化
画像情報を表現するためのデータ量を圧縮する手法
符号化(coding, encoding)：画像信号に含まれる本質的な情報をなるべく保
持しつつ、データ量を圧縮すること。
復号(decoding)：圧縮された画像から元の画像を再現すること。
4
画像符号化
冗長度削減部
●予測符号化：隣接画素から現画素を予測
●変換符号化：空間周波数領域で冗長な部分を取り除く
●ベクトル量子化：隣接した複数の画素を一括して量子化。ベクトルデータの
次数を落とす方法。
5
画像情報の冗長度
種類
符号化手法
画像そのものに含まれる冗長度
●統計的冗長度
－空間的冗長度
予測符号化、変換符号化、ベクトル量子化
－時間的冗長度
フレーム間予測、動き補償
人間の視覚特性に起因する冗長度
非線形量子化、ビット配分
符号の生起確率の偏りによる冗長度
●エントロピー的冗長度
エントロピー符号化
6
予測符号化
通常の画像では空間的・時間的に隣接した画素の値が互いに似ている（相
関が高い）ことを利用した符号化。
隣接する画素の差を伝送。
隣接する画素との相関係数
は０．９～０．９５．
7
予測符号化の枠組み
一つ前の符号化済みの画素値(xi-1’)とその差(xi-1’-xi’)を用いて、現画素（xi’）を予測する
方法。元データと比較して、差の値には少ない量子化レベルを割り当てる。
qi：量子化誤差。qi=0のとき、可逆符号化（可逆圧縮）またはロスレス符号化。
qi≠0のとき、非可逆符号化（非可逆圧縮）またはロッシー符号化。
d:１画素遅延回路。一つ前の画素xi-1が保存される。
8
時間軸方向での予測
フレーム間予測
現フレーム♯ｋ中の画素xi,kの値を、一つ前のフレーム＃ｋ－１の画素xi,k-1の
値から予測。動きの少ない動画（会議風景）では効率的に圧縮できる。
同じ位置の画素から予測
9
動き補償予測
動き補償フレーム間予測
フレーム間での動きを求め、動きの分だけ前のフレームの対象物の位置をず
らして予測。動きベクトルを求めるための方法：ブロックマッチング法など。
10
変換符号化
周波数空間での符号化
低周波数領域＝＞大きなエネルギー（画像上重要な周波数成分）が集中
＝＞細かく量子化して情報を伝送
高周波数領域＝＞小さいエネルギー
＝＞粗く量子化して情報を伝送
11
変換符号化
変換係数：各周波数の振幅に相当
直交変換：離散コサイン変換、ウェーブレット変換など
８×８が
一般的
12
離散コサイン変換
cos波だけで、各周波数の振幅を求める。
13
変換係数のエネルギー分布
低周波成分：大きなエネルギーが集中。分散大
高周波成分：小さなエネルギー、分散小
14
変換係数の量子化
量子化ビット割り当て
直流成分：量子化ビットは８ビット（以上）
低周波成分：２－７ビット程度に量子化
高周波成分：１－２ビット程度に量子化
15
変換係数の走査
大きなエネルギーの
低周波数の変換係数
を優先的に読み出す
EOB (end of block)：
EOBコードの後はすべ
てゼロであることを示す。
たくさんのゼロを符号化
する代わりにＥＯＢを置
く。＝＞圧縮
16
エントロピー符号化
可変長符号化
シンボル（離散的な情報量）の生起確率によって、符号語の割り当てを変える
符号化の方法。
高い生起確率のシンボル－＞短い符号語
低い生起確率のシンボル－＞長い符号語
情報量 I
I   log 2 P(ai )
P(ai): シンボルaiの生起確率
エントロピー（平均情報量） H
N
H   P(ai ) log 2 P(ai )
i 1
17
エントロピー(1)
●エントロピー関数（連続関数）は常に正。
●エントロピーはすべての事象の確率が等しいときに最大になり、その値は
次のようになる。
log 2 N
●エントロピーは不確定さの程度または衝撃度。
確率が小さい出来事が起きると衝撃度は大きい。
競馬：興奮度。すべての馬の勝つ確率が等しいときに最も興奮度が大きい。
しかし、１頭だけ飛びぬけて強い馬がいると、あまり面白くない。
レースの予想の立場から考えると、もし、出走馬に関する情報が事前に何もわかっ
ていないと、どの馬が勝つかは「等確率」となる。しかし、「この馬はまず勝てない」と
か「この馬は本命」といった情報を聞くと、各馬が勝つ確率が等確率からずれる。そう
すると、情報エントロピーが小さくなる。
18
問題確率事象系{a1, a2, a3}の各事象の生起確率がそれぞれ{0.5, p, 0.5
－p}であるとき、この事象系の最大エントロピーはどれか。（情処３）
H  {0.5  p log 2 p  (0.5  p) log 2(0.5  p)}
dH
(0.5  p)
 log 2
dp
p
dH
 0とすると、p  0.25
dp
問題確率事象系{a1, a2, a3}の各事象の生起確率がそれぞれ{0.5, p, 0.5－
p}であるとき、この事象系のエントロピーが最小となるpはどれか。（情処４）
選択肢：０．０５、０．１０、０．１５、０．２０、０．２５
エントロピーHは上に凸の関数で、最大値はｐ＝０．２５のときなので、０．２
５から最も離れたｐのときにHは最小となる。したがって、ｐ＝０．０５のとき
に最小となる。
19
エントロピー(2)
●２つの事象A,Bにおいて２つの事象が同時に起こる結合事象(ai, bj)が
起こる結合確率がP(ai, bj)であるとき、結合事象の自己情報量I(ai, bj)は
次のようになる。
I (ai, bj )   log 2 P(ai , bj )
●I(ai, bj)の平均値を結合エントロピーという。
N
M
H ( A, B)   P(ai , bj ) log 2 P(ai , bj )
i 1 j 1
20
エントロピー(3)
●２つの事象A,Bにおいて、条件bjの下で事象aiが起こる確率がP(ai | bj)であるとき
の条件付き自己情報量I(ai | bj)は次のようになる。
I (ai | bj )   log 2 P(ai | bj )
●I(ai|bj)の平均値を条件付エントロピーという。一方の情報源Bについて知識を得
た後で情報源Aにまだ残っている不確定度。
N
M
H ( A | B)   P(ai, bj ) log 2 P(ai | bj )
i 1 j 1
●事象Bを知ったときにAについて知る情報量、すなわち平均相互情報量（または
相互エントロピー）I(A;B)は以下のようになる。多少関係のある情報源ＸとＹにおいて，
A（またはB）を知ったことによって，得られるB（またはA）に関する情報量。
I ( A; B)  H ( A)  H ( A | B)  H ( B)  H ( B | A)
N M
P(ai | bj ) N M
P(ai, bj )
  P(ai, bj ) log 2
  P(ai, bj ) log 2
P(ai )
P(ai ) P(bi )
i 1 j 1
i 1 j 1
21
エントロピー符号化
N
平均符号長 L
L   LiP(ai )
i 1
P(ai): シンボルaiの生起確率
Li:
シンボルaiの符号語の長さ
エントロピーと平均の符号長との関係
LH
平均符号長がエントロピーに近づくように符号化を行う
＝＞エントロピー符号化（例：ハフマン符号化）
22
ハフマン符号化方法
（１）情報源のシンボルを生起確率の高いものから順に並べる。
（２）生起確率の最も小さいシンボルと２番目に小さいシンボルに対し、一方
に０、他方に１を割り当てる。どちらかにするかは任意。（ただし、物理士の
試験では確率の低い方が１）
（３）この二つのシンボルをまとめて１つのシンボルとし、合成確率を求める。
（４）これを新たな情報源シンボルとし（シンボルの総数が１つ減る）、改めて
生起確率の大きいものから順に並べる。
（５）（２）～（４）の操作を、シンボルが１つになるまで繰り返す。
（６）各シンボルに対して（２）で割り当てた０と１の系列を逆順に読んだもの
がシンボルの符号語となる。
23
ハフマン符号化の例
通報｛s1,s2, s3, s4, s5}の生起確率は、それぞれ{0.18, 0.27, 0.36, 0.04,
0.15}である。この通報をHuffman符号化法によって２元符号化しなさい。
（情処７，８）
s3 0.36
0
s2 0.27
1
s1 ：11
0.63
0
0 0.37 1
1
s1 0.18
s5 0.15
0 0.19
s4 0.04
1
1.0
s2 : 01
s3 : 00
s4 :101
s5 :100
平均符号長　N
L   LiP(ai )  2  0.18  2  0.27  2  0.36  3  0.04  3  0.15
i 1
 2.19
24
実用的な画像符号化方式
静止画
JPEG: DCTに基づいた画像圧縮技術
JPEG2000:ウェーブレット変換に基づいた画像圧縮技術
動画
MPEG:
1.5Mbit/秒程度の記録速度を想定
MPEG-2: 3-10Mbit/秒程度（標準テレビ）と15-30Mbit/秒（高精細テレビ）
MPEG-4: マルチメディア全般
ＪＰＥＧ方式の基本的な枠組み
25
ランレングス符号化
ランレングスに対して、さらにハフマン符号化を行うことにより
さらに圧縮できる
26

Download Report