6 slides / page - 生体医用画像研究室 ICB-Laboratory - 奈良先端科学

マルチメディア工学:講義計画
マルチメディア工学
マルチメディアデータの解析
データ圧縮:離散コサイン変換とJPEG
佐藤 嘉伸
• マルチメディアデータの解析
– 基礎数理
– 代表的解析手法
• データ圧縮:離散コサイン変換・JPEG
• データ表現:形状の主成分分析
奈良先端科学技術大学院大学 情報科学研究科
生体医用画像研究室
yoshi@is.naist.jp
http://icb‐lab.naist.jp/members/yoshi/
講義ホームページ: 日本語ページ → 授業の資料 → マルチメディア工学
データ圧縮:JPEG
マルチメディアデータの解析
• 基礎数理
• JPEG圧縮の原理
– 最小二乗法
– 直交変換、直交関数展開
– 離散コサイン変換(DCT)
• アダマール変換
• 8×8離散コサイン変換
• 離散フーリエ変換との比較
• 代表的解析手法
– データ圧縮:離散コサイン変換・JPEG
– データ表現:形状の主成分分析
– (データ認識:隠れマルコフモデル)
– JPEG方式
• 概要
– 画像分割→離散コサイン変換→量子化→エントロピー符号化
• 音声・言語を含む時系列データに対して有効
• 量子化
• エントロピー符号化(ハフマン符号化)
– (音声の独立成分分析)
直交変換:正規直交基底
e2
x2
x' x e'
1
x'1
x'2
x1
e1
x'=Tx
x=TTx'
|x|=|x'|
T
1 1 1 


2 1 1
離散コサイン変換
e'2
1
 0
e1   , e2   
0
 
 1
1
0
e'1 
0
1
1 1
1 1
 , e'2 
 
2 1
2  1
1
1
1
-1
(恒等変換)
-1 0 1
1
直交変換:正規直交基底の例
アダマール変換の直交基底
2次元ベクトル
ek1,k2
ek
k 0
e'k
1
k 0
1

2
-1
k 0 1
1
0
(恒等変換)
k2
0
k1 0
1
2
4次元ベクトル
3
e'k1,k2
k 0 1
1
2
3
k1 0
k2
0
(アダマール変換)
1
1

e'k
1

2
(恒等変換)
1
2×2マトリックス
k1 0
ek1,k2
ek
1
2
=
×
=
×
=
×
=
×
1
(恒等変換)
2
3
k1
0
e'k1,k2
1
2
3
2
3
(4×4マトリックス = 16次元ベクトル)

1
4
-1
0
1
離散コサイン変換の直交基底
(DCT: Discrete Cosine Transform)

e ' k1 , k 2 ( i1 , i 2 )   k1 cos 
N
k
1
for k  0
N
2
for k  0
N
このイメージは、現在表示できません。
e'k1,k2k1 0
k2 0
N= 8
直交条件
N 1 N 1
i1 0 i2 0
k1 , k 2
(i1 , i2 )e'k '1 ,k '2 (i1 , i2 )  0
(for (k1 , k2 )  (k '1 , k '2 ) )
1
2
3
4
5
6
7
1 

 i2   k 2 
2 

低周波
高周波
1 2 3 4 5 6 7 i
1
i1
i2
離散コサイン変換と
離散フーリエ変換の比較
離散コサイン変換が用いられる理由
i2
高周波
 e'
低周波


 



1 

 i1   k1    k 2 cos 
2 

N
(8×8マトリックス = 64次元ベクトル)
i1
i2
離散コサイン変換の目的
離散コサイン変換の目的
• 画像を、空間領域(直交基底ek1,k2の係数)から周波数
領域(直交基底e‘k1,k2の係数)に変換して、情報源のエ
ントロピーを小さくする。(直交基底e‘k1,k2が三角関数系のと
• 情報源符号化の際、平均符号長は、情報源のエントロ
ピーより小さくすることはできない。すなわち、エントロ
ピーを小さくすれば、圧縮効果は高まる。よって、エン
トロピーの低減はキーポイントである。
き、変換後の空間は周波数領域と呼ばれる。)
– 空間領域の画像では、どの画素値も同じビット数で表現され
る。これは、どの画素においても、とりうる画素値の確率分
布が同じと仮定しなければならないからである。→ エントロ
ピーが大きい。
– 周波数領域の画像では、一部の画素(低周波成分)を除い
て、とりうる画素値の確率分布幅を大幅に小さくできる。→
エントロピーを小さくできる。
空間領域
周波数領域
周波数領域では、真中あたり(低
周波成分)を除いて、0に近い値の
みをとる確率が極めて高くなる。
→ エントロピーが小さくなる。
• 離散コサイン変換も、離散フーリエ変換も、画像を空
間領域から周波数領域に変換するという点では同じで
ある。
• しかし、離散コサイン変換は、離散フーリエ変換より、
エントロピーを小さくする、すなわち、低周波成分への
集中度を高めることができる。それは、なぜか?
• その理由を理解するには、それぞれの連続空間にお
ける数学的意味の検討が必要である。
2
フーリエ変換・展開の整理
フーリエ変換
• (連続関数の)フーリエ変換
• フーリエ変換
– 入力(空間)




F (u )   f ( x)e iux dx   f ( x){cos(ux)  i sin(ux)}dx
– 関数 f(x) と直交関数系である三角関数系の複素数
表記 e‐iux = cos(ux) ‐ i sin(ux) との内積をとる。
– 直交変換後の関数は、周波数 u の関数 F(u) となる。
– F(u) の実数(Re) 成分がcos成分、虚数(Im) 成分が
sin成分がとなる。
– xが実数の場合、F(u) = F*(‐u) である。(*は複素共役)
f(x): 連続・無限
(定義域-∞から∞(無限区間)の連続関数)
– 出力(周波数) F(u): 連続・無限
(定義域-∞から∞(無限区間)の連続関数)
• フーリエ級数展開 (周期的連続関数のフーリエ変換)
– 入力(空間)
f(x): 連続・周期 (周期的連続関数)
– 出力(周波数) cn: 離散・無限 (離散値の無限系列)
• 離散フーリエ変換 (有限長の標本値系列のフーリエ変換)
– 入力(空間)
xn: 離散・有限 (離散値の有限系列)
– 出力(周波数) cn: 離散・有限 (離散値の有限系列)
フーリエ変換・展開の整理
フーリエ級数展開
フーリエ変換
• (連続関数の)フーリエ変換
– 入力(空間)
f(x): 連続・無限
(定義域-∞から∞(無限区間)の連続関数)
– 出力(周波数) F(u): 連続・無限
(定義域-∞から∞(無限区間)の連続関数)
• フーリエ級数展開 (周期的連続関数のフーリエ変換)
– 入力(空間)
f(x): 連続・周期 (周期的連続関数)
– 出力(周波数) cn: 離散・無限 (離散値の無限系列)
離散フーリエ変換
• 離散フーリエ変換 (有限長の標本値系列のフーリエ変換)
– 入力(空間)
xn: 離散・周期(有限) (離散値の周期的系列)
– 出力(周波数) cn: 離散・周期(有限) (離散値の周期的系列)
http://en.wikipedia.org/wiki/Relations_between_Fourier_transforms_and_Fourier_series
離散フーリエ変換の
連続空間における数学的意味
• デジタル信号のフーリエ変換(離散フーリエ変換)
– 入出力:離散・有限(離散値の有限系列)
i1
k1
空間領域
周波数領域
x=xi1i2
c=ck1k2
i2
離散フーリエ変換の
連続空間における数学的意味
• 離散フーリエ変換の連続空間における意味
– 入出力: 有限の定義域区間を周期とする(無限区間の)周期
関数を一定間隔で標本化したもの → 離散・周期
(空間領域) f(x)
離散
周期
周期
離散
F(u) (周波数領域)
k2
e2
x2
c2
c x e'
1
c1
x1
e'k1,k2は三角関数系
c = Tx
e1 x = TTc
|x| = |c|
e'2
3
離散フーリエ変換(DFT)と離散コサイン変換(DCT)
コサイン変換
連続空間における数学的意味
• コサイン変換
– 右の画像を上下左右に並べて
いき周期関数にしたものをフー
リエ変換したものに等価。

Fc (u )   f ( x) cos(ux)dx
0
– 区間[0,∞]で定義される関数 f(x) を原点に関して鏡
像変換して得られる(偶)関数 f'(x) (f'(x) = f'(‐x))を
フーリエ変換した結果(の1/2)と等価である。
Fc (u )  

0
f (x)
• 離散フーリエ変換
1 
f ( x) cos(ux)dx   f ' ( x)e iux dx
2 
– Fc(u) は実数(Re) 成分のみとなる。
– Fc (u) = F(‐u) である。
連続空間における数学的意味
(Re)
(Im)
i2
(Re)
• 離散コサイン変換
i2
f'(x)
– 上下左右の鏡像変換画像を並
べた右の画像を、さらに、上下
左右に並べていき周期関数に
したものをフーリエ変換したも
のに等価。(偶関数になってい
ることに注意!)
i1
i2
離散フーリエ変換(DFT)と離散コサイン変換(DCT)
• 離散フーリエ変換 i1
• 離散コサイン変換
i1
お知らせ
• 授業改善のためのアンケートが、KOANで実
施されます.回答期間は7/16〜8/30です。
• 清川先生担当分のレポート課題をCLEに設定
しました。7/26締切に設定しています。
• 今年度のマルチメディア工学の講義は、本日
が、最終回です。
i1
i2
離散フーリエ変換(DFT)と離散コサイン変換(DCT)
連続空間における数学的意味
• 離散フーリエ変換 i1
i2
(Re)
(Im)
離散フーリエ変換
(DFT: Discrete Fourier Transform)
対称性のため情報は半分だけ
• 離散コサイン変換
i1
i2
さらなる対称性のため情報は1/4だけ
4
離散コサイン変換
(DCT: Discrete Cosine Transform)
離散フーリエ変換
(DFT: Discrete Fourier Transform)
不連続(継ぎ目)がある。
離散フーリエ変換(DFT)・離散コサイン変換(DCT)
離散コサイン変換
(DCT: Discrete Cosine Transform)
• 連続系で解釈すれば、
– 離散フーリエ変換は、有限の離散画像を単純に並べて周期化
したものを、連続フーリエ変換したものである。
• 画像の境界で不連続が発生する(本来の画像には無い高周波数成分
が発生してしまう)。
• これにより、低周波数成分への集中が弱まりエントロピーが大きくなる。
– 離散コサイン変換は、有限の離散画像を(縦・横それぞれ)鏡
像変換しながら並べて周期化したものである。
• 鏡像変換することにより画像境界が連続的につながる(離散フーリエ変
換のような高成分が発生しない)。
不連続(継ぎ目)がない。
DFT
DCT
JPEG方式の概要
JPEG方式
本資料ではモノクロ画像(輝度成分)
のみを対象とする。
• 画像を8×8画素のブロック分割を行う。
• 8×8画素毎に以下の圧縮符号化を行う。
– 離散コサイン変換(DCT)によりエントロピーを低減する。
– DCTの各係数値を量子化する.
– 量子化した各係数値を以下の手順で符号化する。
• 8×8の2次元的配列を、ジグザグスキャンにより、
低周波成分から高周波成分に並ぶよう1次元系列
化にする。
• 1次元系列となった係数値に対して、差分符号化(直
流成分)、ランレングス符号化を行う。
• さらにハフマン符号化を行う.
5
JPEG方式の概要
8×8画素ブロック
画像
8×8画素の
ブロックに分割
離散コサイン
変換 (DCT)
ブロック毎のDCT係数
変換後各係数の
量子化
ジグザグ
スキャン による
ジグザグスキャン
1次元系列化
• 画像を8×8画素のブロック分割を行う。
• 8×8画素毎に以下の圧縮符号化を行う。
– 離散コサイン変換によりエントロピーを低減する。
– DCTの各係数値を量子化する.
– 量子化した各係数値を以下の手順で符号化する。
• 8×8の2次元的配列を、ジグザグスキャンにより
、低周波成分から高周波成分に並ぶよう1次元系
列化にする。
• 1次元系列となった係数値に対して、差分符号化
(直流成分)、ランレングス符号化を行う。
• さらにハフマン符号化を行う.
1次元系列の
符号化
JPEG方式の概要
1次元系列
8×8ブロック分割
8×8ブロック分割
8×8ブロック
8×8ブロック分割
8×8ブロック
8×8ブロック分割
8×8ブロック
6
JPEG方式の概要
離散コサイン変換 (DCT)
8×8 画素値 x
• 画像を8×8画素のブロック分割を行う。
• 8×8画素毎に以下の圧縮符号化を行う。
– 離散コサイン変換によりエントロピーを低減する。
– DCTの各係数値を量子化する.
– 量子化した各係数の値を以下の手順で符号化する
。
• 8×8の2次元的配列を、ジグザグスキャンにより
、低周波成分から高周波成分に並ぶよう1次元系
列化にする。
内積 (x, e'00)
8×8 画素値 x
DCT係数 x'
内積 (x, e'10)
k2
e'00
直流成分(平均輝度)
e'k1,k2
離散コサイン変換 (DCT)
8×8 画素値 x
DCT係数 x'
内積 (x, e'20)
DCT基底 k1
(Re) DFT (Im)
DCT基底 k1
(Re) DFT (Im)
• 1次元系列となった係数値に対して、差分符号化
(直流成分)、ランレングス符号化を行う。
• さらにハフマン符号化を行う.
離散コサイン変換 (DCT)
DCT係数 x'
DCT基底 k1
(Re) DFT (Im)
e'10
k2
e'k1,k2
離散コサイン変換 (DCT)
8×8 画素値 x
DCT係数 x'
内積 (x, e'20)
e'20
e'k1,k2
離散コサイン変換 (DCT)
8×8 画素値 x
DCT係数 x'
内積 (x, e'20)
DCT基底 k1
(Re) DFT (Im)
k2
DCT基底 k1
(Re) DFT (Im)
e'20
k2
e'k1,k2
e'20
k2
e'k1,k2
7
離散コサイン変換 (DCT)
8×8 画素値 x
JPEG方式の概要
DCT係数 x'
内積 (x, e'20)
DCT基底 k1
(Re) DFT (Im)
e'20
k2
e'k1,k2
• 画像を8×8画素のブロック分割を行う。
• 8×8画素毎に以下の圧縮符号化を行う。
– 離散コサイン変換によりエントロピーを低減する。
– DCTの各係数値を量子化する.
– 量子化した各係数値を以下の手順で符号化する。
• 8×8の2次元的配列を、ジグザグスキャンにより
、低周波成分から高周波成分に並ぶよう1次元系
列化にする。
• 1次元系列となった係数値に対して、差分符号化
(直流成分)、ランレングス符号化を行う。
• さらにハフマン符号化を行う.
DCT係数の特性
DCT係数の特性
• 浮動小数点の数値データである。
• 不動小数点の数値データである。
• 通常の画像では、高周波成分(青領域)は、直流(赤枠)・低周
波成分(ピンク領域)にくらべはるかに小さな数値(無視できる
程度の数値/ほぼゼロ)となる。
• 通常の画像では、高周波成分(青領域)は、直流(赤枠)・低周
波成分(ピンク領域)にくらべはるかに小さな数値(無視できる
程度の数値/ほぼゼロ)となる。
8×8 画素値
直流成分 低周波成分
8×8 画素値
(境界付近が含まれている場合)
DCT係数
直流成分 低周波成分
(濃淡値変化が小さい場合)
DCT係数
高周波成分
高周波成分
• DCTの各係数を、予め与えられた量子化テーブルの数値で割り
算し、小数点以下を丸める。(高周波数成分の多くは、ゼロになる。)
• DCTの各係数を、予め与えられた量子化テーブルの数値で割り
算し、小数点以下を丸める。(高周波数成分の多くは、ゼロになる。)
量子化テーブル
量子化テーブル
k1
0.12832
0
77
408 .0
 26
16
低周波成分
高周波成分
k2
k1
k2
[JPEG Standard Annex K]
この(推奨)量子化テーブルの
値は人間の視覚特性に基づい
て定められたものである。すな
わち、感度のよい周波数帯によ
り小さな値が設定されている。
DCT係数
[JPEG Standard Annex K]
絶対値が小さい傾向にある高周波数成分ほど大きな値で割り算され、さらに小さな値となる。
8
量子化
DCT係数
DCT係数
テーブル値
量子化DCT係数
量子化
DCT係数
(濃淡値変化が小さい場合)
量子化テーブル
DCT係数
テーブル値
量子化DCT係数
量子化テーブル
直流成分以外、一部の低周波成
分が比較的大きナ値をもつが、そ
れでも多くの成分がゼロ
直流成分以外、ごく一部の低周波
成分を除いて、ほとんどがゼロ
ジグザグスキャン
JPEG方式の概要
• 画像を8×8画素のブロック分割を行う。
• 8×8画素毎に以下の圧縮符号化を行う。
– 離散コサイン変換によりエントロピーを低減する。
– DCTの各係数値を量子化する.
– 量子化した各係数値を以下の手順で符号化する。
• 直流成分を出発点として、低周波から高周波成分まで、ジグザグ
スキャンにより、量子化されたDCT係数を1次元の数値系列に変
換する。
k1
量子化された
DCT係数
ck1,k2
• 8×8の2次元的配列を、ジグザグスキャンにより
、低周波成分から高周波成分に並ぶよう1次元系
列化にする。
• 1次元系列となった係数値に対して、差分符号化
(直流成分)、ランレングス符号化を行う。
• さらにハフマン符号化を行う.
k2
1次元系列化されたDCT係数
c00,c10, c01,c02, c11,c20, c30,c21, c12,c03, c04,c13,c22,c31,c40,c50,…….., c75,c76, c67,c77
直流 低周波
高周波
ジグザグスキャン
ジグザグスキャン
• 8×8画素ブロック内において濃淡変化が小さい場合
k1
量子化
DCT係数
(濃淡値変化が大きい場合)
k2
• 8×8画素ブロック内において濃淡変化が大きい場合
k1
量子化
DCT係数
k2
1次元系列化されたDCT係数
1次元系列化されたDCT係数
26,0,1,0,1,-1,-1, -1, -1,0,0,0, …............……..........…,0, 0, 0, 0
49,18,8,6,4,3,-1,0,-1,-1,1,-2,-3,-1,1,0,0,-1,0, 0,0,…...,0, 0, 0, 0
直流 低周波
高周波
直流 低周波
高周波
9
JPEG方式の概要
• 画像を8×8画素のブロック分割を行う。
• 8×8画素毎に以下の圧縮符号化を行う。
– 離散コサイン変換によりエントロピーを低減する。
– DCTの各係数値を量子化する.
– 量子化した各係数値を以下の手順で符号化する。
差分符号化(直流成分)
• 隣り合う3つのブロックの量子化係数値系列
濃淡変化が比較的
小さい場合
• 8×8の2次元的配列を、ジグザグスキャンにより
、低周波成分から高周波成分に並ぶよう1次元系
列化にする。
• 1次元系列となった係数値に対して、差分符号化
(直流成分)、ランレングス符号化を行う。
• さらにハフマン符号化を行う.
32  26  6
27  32  5
隣接するブロックの平均輝度値は近いので、前ブロックの直流成分と
の差分を用いることにより、値の可変範囲(エントロピー)を低減する。
(26,32,27,…. のかわりに、(26),6,-5,….. を記憶する。)
差分符号化(直流成分)
1次元量子化DCT係数系列の特徴
• 隣り合う3つのブロックの量子化係数値系列
ジグザグスキャンにより1次元系列化された量子化DCT係数値の例
濃淡変化が
大きい場合
50,-23,-9,-1,0,0,1,2,2,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,-1,0,0,0,0,0,-1,0,0,0,0,0,0,0,0,1,0,0,0,……….0,0,0
92  50  42
49  92  43
27,-2,0,0,-1,1,2,-2,1,0,0,0,-1,0,1,0,0,-1,1,0,0,0,0,0,-1,10,0,0……………………………………..0,0,0
濃淡変化が大きい場合には、必ずしも、隣接ブロックの直流成分値
は近いとは言えないが、それでも、成分値そのものよりも差分値の可
変範囲は小さい。
0 が続く傾向にあるので、0については、0が続く数(ランレングス)
を記憶させる。( “0000000” よりも “0が7回” のほうが短い。)
ランレングス符号化
JPEG方式の概要
• 符号化の方針
– 直流成分は、差分符号化する。
– その他の成分は、0以外の値が出現した時点で、その値
が出現する直前までに0が続いた数と、その値のペアとし
て、符号化する。
– 0以外の値がそれ以降出現しなければ、EOB として、その
ブロックの符号化を完了する。
• 符号化の例 (直流成分以外)
50, -23,-9,-1,0,0,1,2,2,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,-1,
0,0,0,0, 0,-1, 0,0,0,0,0,0,0,0,1,0,0,0,……….0,0,0
(0,-23) (0,-9) (0,-1) (2,1) (0,2) (0,2) (2,1) (0,1) (0,1)
(11,-1) (5,-1) (8,1) EOB
(Run, Coef) の意味: 0 が Run 回続いた後、(0以外の)Coef が出現
• 画像を8×8画素のブロック分割を行う。
• 8×8画素毎に以下の圧縮符号化を行う。
– 離散コサイン変換によりエントロピーを低減する。
– DCTの各係数値を量子化する.
– 量子化した各係数値を以下の手順で符号化する。
• 8×8の2次元的配列を、ジグザグスキャンにより
、低周波成分から高周波成分に並ぶよう1次元系
列化にする。
• 1次元系列となった係数値に対して、差分符号化
(直流成分)、ランレングス符号化を行う。
• さらにハフマン符号化を行う.
10
ハフマン符号の復習
ハフマン符号とJPEG
• 前提条件
• エントロピー符号
– 情報源(シンボル列の有限空間とその上の確率分布)を、シ
ンボル毎の出現確率に基づいた符号語長を用いて符号化す
る。出現確率・大(小)→符号語長・短(長)を割り当てることに
より高い圧縮効果を得る。
– 平均符号長はエントロピーより小さくすることはできない。
• エントロピー:情報源を表現するのに必要な平均ビット数
– 各シンボルの出現確率が既知である。
• アルゴリズム
– 以下のペア化の処理を繰り返す。
• 最も出現確率の低い2つのシンボルをペアにする。
• これら2つのシンボルを新しい1つのシンボルとみなす。
– 以上の処理により2分木が構成される。
– 2分木の各分岐に0/1を割り当てる。
– 根から各分岐の0/1を連結することにより符号を得る。
0
00 A 0.2
0
0.425
1.0
01 B 0.225
1
0
1
10 C 0.3
0.575
0
110 D 0.175
0.275
1
111 E 0.1
1
– ハフマン符号は、コンパクト符号(一意複号可能で平均符号
長を最小化する符号)である。
• JPEGにおけるハフマン符号
– 直流成分に対する差分符号(の数値)、その他の成分(交流
成分)に対するランレングス符号(の数値列)のそれぞれに
対して、異なるハフマン符号が定義される。
直流(DC)成分差分のサイズ分類と
そのハフマン符号
• 直流成分の差分符号化における仮定
– 隣接ブロックの直流成分(平均輝度値)は近い値である。
– 差分値 0 の出現頻度が最も高く、差分値の絶対値が大きくなるにし
たがい、出現頻度は低下する。
• 差分値をsize分類符号テーブルに従って符号化
•
直流(DC)成分差分のサイズ分類と
そのハフマン符号
具体例
–
–
–
–
差分値 0: Size 0 (Code 00), Additional Bits ‐  Huffman Code: 00
差分値 ‐1: Size 1 (010), Additional Bits 0  Huffman Code: 010 0
差分値 4: Size 3 (100), Additional Bits 100 Huffman Code 100 100
差分値 ‐15: Size 4 (101), Additional Bits 0000  Huffman Code 101 0000
DC Coef Difference Size Typical Huffman codes for Size Additional Bits (in binary) DC Coef Difference Size Typical Huffman codes for Size 0 0 00 ‐
0 0 00 Additional Bits (in binary) ‐
‐1,1 1 010 0,1 ‐1,1 1 010 0,1 ‐3,‐2,2,3 2 011 00,01,10,11 ‐3,‐2,2,3 2 011 00,01,10,11 ‐7,…,‐4,4,…,7 3 100 000,…,011,100,…111 ‐7,…,‐4,4,…,7 3 100 000,…,011,100,…111 ‐15,…‐8,8,…,15 4 101 0000,…,0111,1000,…,111
1 ‐15,…‐8,8,…,15 4 101 0000,…,0111,1000,…,111
1 ⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
‐1023,…‐512,512,…,1023 10 1111 1110 00 0000 0000,…,11 1111 1111 ‐1023,…‐512,512,…,1023 10 1111 1110 00 0000 0000,…,11 1111 1111 ‐2047,…‐
1024,1024,…2047 11 1 1111 1110 000 0000 0000,…,111 1111 1111 ‐2047,…‐
1024,1024,…2047 11 1 1111 1110 000 0000 0000,…,111 1111 1111 Kingsbury
http://cnx.org/content/m11096/latest/
直流(DC)成分差分のハフマン符号
Kingsbury
交流(AC)成分のハフマン符号
• 交流成分は、ランレングス符号 (Run, Coef) の系列
• 差分値出現頻度分布の実例
– (Run, Coef) : 0 が Run 回続いた後、係数値 Coef が出現
– 例:(0,‐23) (0,‐9) (0,‐1) (2,1) (0,2) (0,2) (2,1) (0,1) (0,1) (11,‐1) (5,‐1) (8,1) EOB
– エントロピー
• 差分符号なし: 6.42 bits
• 差分符号あり: 6.07 bits
• (Run, Coef) のハフマン符号
– (Run, Coef の Size) のハフマン符号と付加ビットで表現する。Coef の Size 分
類については、DC 成分と同じ分類に基づく。
差分符号なし
差分符号あり
Kingsbury
http://cnx.org/content/m11096/latest/
http://cnx.org/content/m11096/latest/
Kingsbury
(Run,Size) Code Byte (hex) Code Word (binary) (Run,Size) Code Byte (hex) Code Word (binary) (0,1) 01 00 (0,6) 06 1111000 (0,2) 02 01 (1,3) 13 1111001 (0,3) 03 100 (5,1) 51 (EOB) 00 1010 (6,1) 61 1111011 (0,4) 04 1011 (0,7) 07 11111000 1111010 (1,1) 11 1100 (2,2) 22 (0,5) 05 11010 (7,1) 71 11111010 (1,2) 12 11011 (1,4) 14 111110110 (ZRL) F0 (2,1) 21 11100 (3,1) 31 111010 (4,1) 41 111011 11111001 ⋮
11111111001 ⋮
http://cnx.org/content/m11096/latest/
11
交流(AC)成分のハフマン符号
交流成分係数の出現頻度
• 具体例
– (Run, Coef)= (0,‐7) : (Run Size)=(0,3) + 付加ビット000  100 000
(Run Size)=(0,1)
– (Run, Coef)= (1,3): (Run, Size) = (1,2) + 付加ビット11  11011 11
(Run Size)=(0,2)
(Run,Size) Code Word (binary) (0,1) 00 (0,2) AC Coef
0 Size Additional Bits (in binary) 0 ‐
01 (0,3) 100 (EOB) 1010 (0,4) 1011 ‐1,1 1 0,1 (1,1) 1100 ‐3,‐2,2,3 2 00,01,10,11 (0,5) 11010 ‐7,…,‐4,4,…,7 3 000,…,011,100,…111 (1,2) 11011 (2,1) 11100 8×8画素
DCT係数
• ブロック単位の
離散コサイン変換 (DCT) によるエントロピー削減
– 人間視覚の周波数感度特性を考慮したDCT係数の量子化
– ジグザグスキャンによる量子化DCT係数の1次元化(直流、低
周波~高周波数数成分)
– (直流成分の)差分符号化、(交流成分の)ランレングス符号化
ジグザグスキャン
• ハフマン符号化
(0,-23) (0,-9) (0,-1) (2,1) (0,2) (0,2) (2,1)
(0,1) (0,1) (11,-1) (5,-1) (8,1) EOB
ハフマン符号
テーブル
ハフマン符号
Kingsbury
http://cnx.org/content/m11096/latest/
画像直交変換・JPEG関連の有用なウェブページ
JPEG方式まとめ
• 8×8画素ブロック分割
(Run Size)=(1,1)
• 信州大学・井澤先生のホームページ
– http://laputa.cs.shinshu‐u.ac.jp/~yizawa/InfSys1/basic/index.htm
– http://laputa.cs.shinshu‐u.ac.jp/~yizawa/InfSys1/advanced/index.htm
– http://laputa.cs.shinshu‐u.ac.jp/~yizawa/InfSys1/ref_contents/index.htm
• 広島大学・浅野先生のホームページ
– http://kuva.mis.hiroshima‐u.ac.jp/~asano/Kougi/01a/Tokuron/
• スタンフォード大Prof. Bernd Girod のImage Communication I 講義資料
– http://www.stanford.edu/class/ee398a/handouts.htm
• JPEG Entropy Coding and 2D‐DCT by Nick Kingsbury – http://cnx.org/content/m11096/latest/
– http://cnx.org/content/m11094/latest/
• Wikipedia
– JPEG, 離散コサイン変換
12