山下研の常識
画像符号化

山下幸彦
大学院理工学研究科
東京工業大学
平成２２年１２月２１日(平成２３年１０月２０日修正)1

発表内容 (1/2)

1. はじめに• 画像の情報量• 非可逆符号化と可逆符号化
2. 画像符号化の基盤技術• エントロピー符号化– ハフマン符号化– 算術符号化
レンジコーダQ-coder• ランレングス符号化• 予測符号化• 変換符号化
2

発表内容 (1/2)

4. 標準的画像符号化法• JPEG• MPEG 2• MPEG 4 AVC
5. 離散コサイン変換を用いない画像符号化• ウェーブレット変換• JPEG 2000
• サブバンド変換• サブバンド画像符号化– Generalized variable length lapped transform– サブバンド動画像符号化
6. まとめ3画像符号化の重要性
画像の情報量• 画像の情報量は大きい。
SDTV (Standard Television) の例：– 色： 3 (R, G, B)– 明るさ： 8 [bit]– 横： 720 [画素]– 縦： 480 [画素]– 時間 ： 30 [frame/s]
3 × 8 × 720 × 480 × 30 ' 248.8[Mbit/s]
HDTV (High Deﬁnition Television)
3 × 8 × 1920 × 1080 × 30' 1.48[Gbit/s]• 地上波テレビ：18 [Mbit/s] 程度⇒ データ量を圧縮する必要がある。
4

非可逆符号化 vs. 可逆符号化
非可逆符号化 (lossy)• 原画像が復号画像と異なる。
• その差は人間の目には分かりにくいようにする。
• ブロック歪み，リンギング (モスキート雑音)• データ圧縮率に優れる。
• 一般に用いられる画像符号は非可逆符号化
可逆符号化 (無歪み符号化) (lossless)• 原画像が復号画像が全く同じ。
• 圧縮率は 1/2 程度• 医用画像などに用いられる (データの保存が法律で必要)。
今回は，非可逆符号化を扱う。
5

エントロピー符号化• 符号化：アルファベット (整数) 列を 0, 1 の系列に直すこと。
• 符号：1 つのアルファベットに割り当てられた 0, 1 の系列
例：
符号：0 → 00, 1 → 01, 2 → 1001
アルファベット列：2011 → 1001000101• エントロピー：平均情報量 (符号の出現確率で決まる量)• 平均符号長はエントロピー以下にはできない。
• エントロピー符号化：平均符号長をエントロピーに近づける符号化• 原則：
頻繁に現れるアルファベットに短い符号あまり現れないアルファベットに長い符号を割り当てる。
• コンパクト符号：平均符号長が最小になる符号

6ハフマン (Huﬀman) 符号化• アルファベットの出現確率が与えられたときに，コンパクト符号を作ることができる。
• 符号化テーブルを使って符号を決める。
• 画像符号化では，本当に確率を使って符号を決めるのではなく，符号化テーブルを使って符号を決める方法一般に使われている。
• 具体的な符号化テーブルの例は，JPEG で説明する。

ハフマン符号の符号化構成法
平均符号長：
0.5 × 1 + 0.25 × 2 + 0.125 × 3+0.125 × 3 = 1.75

7

算術符号化• MIT の P. Elias によって提案• IBM の G. G. Langdon, J. J. Rissanen が完成 (特許)• JPEG2000 の MQ coder に使われている。
• 符号化アルゴリズム (原理)：1. 初期の対象区間：[0, 1)
2. 現在の対象区間を，シンボルの確率に比例させた長さの区間に分割
3. 符号化するシンボルに対応する区間を対象区間とする。
4. 2 へもどる• 区間に含まれる 1 つの小数でその区間を表す。
• シンボル列の出現確率が高い方が，長い区間になる。
⇒ 一般には長い区間には桁数の短い小数が含まれる。
⇒ アルファベット列の出現確率が高いほど短い符号になる。
• 復号は小数が含まれる区間を，アルファベットの順番で調べる。
8

算術符号化の原理• 0 が出る確率：0.7• 1 が出る確率：0.3• 000 を表す：0.0 (0 bit)
• 010 を表す：0.5 (1, 1 bit)• 100 を表す：
0.75 (11, 2 bit)• 110 を表す：
0.9375 (1111, 4 bit)9

算術符号化の例• Dmitry Subbotin のレンジコーダ (の 1 bit 版)– 全体区間を下端 (low) と区間範囲 (range) で表現– 符号化：最後アルファベットで分割した後の low の値を送る。
– アルゴリズムが簡単である。特許がない。
• 処理の基本の区間を [0, 31] の 5 bit (処理には 6 bit 必要) として説明
初期状態では，0 は 0.0, 32 が 1.0 を表している。
• 今回の説明：アルファベット列の終了は実装しない。
– 符号化したものより長いアルファベットが復号される可能性がある。
– 符号化したアルファベット列と復号されたアルファベット列は，符号化したところまでは一致する。
– 通常は，入力アルファベットとして終了記号を加える。または，アルファベット列から終了が分かる。
(学習用の Java のソースコードが，http://www.ide.titech.ac.jp/~yamasita/yylab/index.html から取得できる。)
10

基本

11

区間拡大の基本 (保留がないとき)• range が 15 以下になると，区間を拡大する。
• low+range が 15 以下の場合：
それ以降の分割によらず，最上位ビットが 0 と決まる。
0 を出力し，区間を 2 倍に拡大する。
• low が 16 以上の場合：
1 を出力し，low から 16 を引いて (最上位ビットを 0 にする)，区
間を 2 倍に拡大する。
• 上記操作は，左ビットシフト
12区間拡大の基本 (保留)• low が 15 以下，low+range が 16 以
上の時は，最上位ビットが決まらないため，保留とする。
出力はしない。
• その最上位ビットを 0 と仮定して処理を続ける。
• 保留中の拡大時に，low が 31 以
下，low+range が 32 以上の時は，先の最上 bit が確定しないので，再度保留する。
•連続して保留した回数を数える。
13

保留の解決• 区間の長さに関わらず，• 保留中に，low が 32 以上の場合，保留を始めた最上位ビットが 1 であったことが確定する。
1 と (保留した回数 −1 個) の 0 を出力し，low から 32 引く。
• 保留中に，low+range が 31 以下の場合，保留を始めた最上位ビットが 0 であったことが確定する。
0 と (保留した回数 −1 個) の 1 を出力する。
• 保留状態を解除する。
14

保留の例

15

保留解決の例 (オーバーフローなし)

16

保留解決の例 (オーバーフローあり)

17Q-coder• 通常の算術符号化では，アルファベットを 1 つ処理するごとに乗算の計算が 1 回必要。
⇒ 処理として重い。(少なくとも 2000 年ごろは)• Q-coder は，乗算をしない binary (入力が 0 or 1) の算術符号化• JPEG 2000 の MQ-coder は Q-coder を元にしている。
• 確率の和を，1.0 でなく，0.75 以上 1.5 未満で考える。
• 下側を必ず出現確率が少ない入力アルファベット (0 or 1) とする。
• 処理中に，上側区間が小さくなる場合は，入れ替えを行う。
• 記号：
Qe : 下側区間長 (下側アルファベットの出現確率に対応する整数)
A : 全体区間長 (整数，レンジコーダの range に相当)
C : 区間の下側位置 (レンジコーダの low に相当)
最後アルファベットで分割した後のこの値を送る)
18

Q-coder• 全体区間長に関わらず，下側のアルファベットのための区間長は Qe とする。上側のアルファベットのための区間長は A − Qe となる。
下側区間：[C, C + Qe)
上側区間：[C + Qe, C + A)
• 誤差：
Qe に乗算を用いないため，下側アルファベットの出現確率に対して，
Qe による区間幅は，1/1.5 ∼ 1/0.75 倍の誤差を含む。
• Q-coder は，基本的には 16 bit で演算する (以下，16 進数で表記)。
• A は，8000 (0.75) から FFFF (1.5 未満の最大数) の範囲となる。
• C も，オーバーフローしないときは FFFF 以下の値になる。
• A の値が 8000 未満になったら，再正規化する (拡大する)。
Aを2倍C の最上位ビットを送り，左ビットシフトする。
• 再正規化時に生じる 1 bit の出力は，1 byte (8 bit) にまとめて出力する。
19

Q-coder のオーバーフローの処理• 再正規化時にオーバーフローが生じる可能性があるときでも，レンジ
コーダのような保留処理を行わず，オーバーフローしないものとして処理を続ける。
• オーバーフローが生じたときは，出力のために蓄積している 1 byte のデータに 1 を加算することによって行う。
• 1 byte を越えるオーバーフローに対しては，その byte に対してオーバーフローしたとのフラグを立てる。
• 一通り符号化が終わった後に，出力の最後の byte から調べて行き，オー
バーフローしている byte がある場合は，その直前の byte に対して 1 を加算する処理を行う。
• 加算された byte がオーバーフローした場合は，その前 byte に加算することを繰り返す。

20

算術符号化による適応符号化• 符号化するアルファベット列に適応して区間幅を変更する。
0 が続くようならば，0 に対する区間幅を長くする。
• 算術符号化の符号列は，区間に含まれる小数を表している。
• 復号時には，復号するアルファベットまでの区間が分かっていれば，復号できる。
• 既に送ったアルファベットに依存して区間幅を変えても，区間幅を変更するアルゴリズムを符号化器，復号器で共有していれば，復号器でも変更した区間幅が構成できる。
• 1 bit ごとの適応的な符号化器の作成が可能• この原理が JPEG2000 の MQ-coder で使われている。
• 符号化するビットのコンテキスト (文脈) が，すでに送ったデーターから分かる場合は，コンテクストごとに異なる確率を使うことができる。

21

算術符号化による適応符号化 (非適応符号化の例)• p0：0 が出る確率• p1：1 が出る確率• 固定
p0 = 0.7
p1 = 0.322算術符号化による適応符号化• p0：0 が出る確率• p1：1 が出る確• 初期
p0 = 0.7
p1 = 0.3• 直前の符号が 0
p0 → p0 + 0.1
p1 → p1 − 0.1• 直前の符号が 1p0 → p0 − 0.1
p1 → p1 + 0.1• p0 or p1 の値が 0.1 以下の場合は，値を変えない。
23

ランレングス (run lenght) 符号• 画像符号化では，符号化したいアルファベットに 0 が続くことが多い。
zero run• 連続している 0 の個数 (ゼロランレングス) を情報とする。
0 → 1, 00 → 2, 000 → 3, 0000 → 4, · · ·• 連続して 0 が続く回数の出現確率は，その値の種類に依存する。
⇒ 0 が続く値もエントロピー符号化する。
• 残りがすべて 0 のときのための，専用の符号を割り当てる。
• 具体的な例は，JPEG で説明する。

24

量子化

• 画像の画素値やその変換係数は一般には連続量• 符号化するために，整数値に変換する。
• 線形量子化Q : 量子化係数
u : 入力連続値
v : 量子化された値
(
)
u
+ 0.5
v = ﬂoorQ• 逆量子化：
uO = Qv : 出力連続値• u と uO には，± 12 Q の誤差が生じる。
• デッドゾーン (0 にする範囲を広くする。)
0 を符号化する効率が良いためである。
25

線形量子化• Q が大きいと，送信する整数が小さくなり誤差が大きくなる。
26

線形量子化 (デッドゾーンあり)• デッドゾーン がある線形量子化 (JPEG 2000)27非線形量子化• 音が大きいところでは誤差が分かりにくいため，量子化係数を大きくする。
• 画像符号化ではあまり使わない。

28

予測符号化• 差分符号化 (最も簡単な例)– 直前の値を予測値とする。
– x1, x2, x3, · · · を送りたい信号列とする。
– xn+1 と xn の差は小さいことが多い。
– xn+1 − xn を送る。
値が小さいため，少ない bit 数で送ることができる。
nx0 x1 x 2 x3 x4 x5 x6 x7 x 8
入力値 120 130 134 137 140 144 138 142 134
差分
120 10 4 3 3 4 -6 4 -829

局所復号器 (ローカルデコーダ) 1/2• 予測符号化で量子化を行う場合は，注意が必要• 不完全な情報を送っている。
• 先の例で量子化係数 10 で量子化する場合：
nx 0 x 1 x2 x3 x4 x5 x6 x 7 x 8
入力値
120 130 134 137 140 144 138 142 134
差分
120 10 4 3 3 4 -6 4 -8差分の量子化 120 10 0 0 0 0 -10 0 -10
復号結果
120 130 130 130 130 130 120 120 110• 誤差が累積してしまう。

30

局所復号器 (ローカルデコーダ) 2/2• 符号器側で復号結果を再構成しその差分を量子化して送る。
差分 = 入力値 − 局所復号器出力
送信データ = 差分を量子化したもの
nx 0 x1 x2 x3 x4 x5 x 6 x 7 x8
入力値
120 130 134 137 140 144 138 142 134
局所復号結果との差分 120 10 4 7 0 4 -2 2 -6差分の量子化結果
120 10 0 10 0 0 0 0 -10
局所復号結果120 130 130 140 140 140 140 140 130
復号結果
120 130 130 140 140 140 140 140 13031変換符号化 (1/4)• ベクトル値を符号化するときに，各要素を符号化するのではなく，線形変換 (直交変換) してから，係数を符号化する。
• si (0 ≤ i ≤ N )：N 次元ベクトル s の第 i 要素の値
• σi：si の標準偏差 (分散の平方根)• si は連続値であるので，その値を完全に送ることはできない。
• si を符号化するとき，精度を一定とすると，その値を送るための平均
符号長の下限は以下のようになる。
log2 σi + const[bit]• 従って，ベクトルの平均符号長の下限は以下のようになる。
N∑

log2 σi + const

i=1

32

[bit]

変換符号化 (2/4)• 画像を直交行列変換 U することを考える。
t = UsU は等長変換である。
kU sk = ksk– 座標値の精度と画像の精度の関係は s と U s で変わらない。
– σi0 ：ti の標準偏差 (座標値の標準偏差は変化する。)• si を画素 i における画素値と考える。
• 画像の統計的性質は移動不変であるから，画素値の分散 σi の値は全て等しい。
σ1 = σ2 = σ3 = · · · = σN
• しかし，σi0 は等しいとは限らない。
33

変換符号化 (3/4)σ1 = σ2
σ10 6= σ2034

変換符号化 (4/4)• 例：√
σ1 = σ2 = · · · = σ11 = 100 =1
σ10 = 10, σ20 = σ30 = · · · = σ11
分散の合計は同じ。
2 = 110σ12 = σ22 + · · · + σ110 )2 = 110(σ10 )2 + (σ20 )2 + (σ30 )2 + · · · + (σ11
• 平均符号長の下限の差は以下のようになる。
[√ ]11 log2 10 − [log2 10 + 10 log2 1] ' 14.9[bit]• 信号の分散 (パワー) を少ない成分に集めると，平均符号長が短くなる。
• このための最適な変換は，Karhunen-Loève transform (KLT).

35

Karhunen-Loève transform (KL 変換)• X ：信号を表す N 次元の確率変数のベクトル• {φn}Nn=1：正規直交基底• PK ：φ1, . . . , φK で張られる部分空間への正射影行列 (K ≤ N )• 任意の K に対して次式を最小化するように {φn}Nn=1 を選ぶ。
EX kPK X − Xk2
低い次元の部分空間で，元の信号を近似する。
• 初めの方の変換係数に，エネルギーが集約されている。
• 信号 x に対する，Karhunen-Loève transform の変換係数は，
hx, φ1i, hx, φ2i, . . . , hx, φN i となる。
• しかし，直接この KL 変換を使うことは難しい。
確率分布が分からない。計算量が多い。
• KL 変換の代わりに，離散コサイン変換を用いることが多い。
36

画像符号化の標準規格

JPEG• Joint Picture Experts Group– ISO (International Organization for Standardization，国際標準化機構)– ITU-T (International Telecommunication Union，国際電気通信連合)(Telecommunication Standardization Sector，電気通信標準化部門)• 静止画像のための規格
パソコン，ディジタルカメラ
MPEG• Moving Picture Experts Group• 動画像のための規格
ビデオ CD，DVD，ディジタル放送• ITU の，H.261 ∼ H.264 とほぼ同様
37

静止画像符号化方式の標準 (JPEG)• 色変換:
RGB 空間から，YCrCb 空間へ変換• 離散コサイン変換 (DCT)• 量子化 : DCT 係数の量子化• ハフマン・ランレングス符号化 :量子化された係数の符号化• ビットストームの組み立て :各種符号列 (画像のサイズ，テーブル，係数) を 1 つのストリームにする。

38

色変換

• 人間は色に関する分解能が明度に関する分解能よりも低い。
– 錐体：明るさを感じる。密度が高い (1.2∼1.4 億個)。
– 杆体：色を感じる。密度が低い。
(500∼600 万個，赤 60%，緑 30%，青 10%)
• 明るさの成分と色の成分を分けて処理する。
• RGB–YCbCr 変換
Y = 0.29900R + 0.58700G + 0.11400B
Cb = −0.16874R − 0.33126G + 0.50000B + 128
Cr = 0.50000R − 0.41869G − 0.08131B + 128• 色に関するデータ (Cb と Cr) は間引く (1/2 × 1/2)。

39

ブロック分割
縦 8× 横 8 画素のブロックに分割する

以降，基本的にはそれぞれ の ブ ロック を独 立 に 処
理する。
40

DCT
• 信号のエネルギーを少数の成分に集める。
• DCT 基底 (正規直交基底)：
(
)}
{
1
1
π
n
m n+
,
fDCT(m) = Cn √ cos
N
2
N
where
{
1√ (n = 0)
Cn =.
2 (n 6= 0)• DCT 係数 = 信号と f nDCT の内積• DCT を表す A = [f 0 f 1 . . . f N −1]T は，直交行列• 入力画像を表すベクトルを x とすれば，変換係数 y は次のようになる。
y = Ax• 高速計算法が存在する。
41

DCT 基底

n=0

n=1

n=2

n=3

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

42

n=4

n=5

n=6

n=7

DCT と DFT (1/2)

原信号

DCT

DFT
43

DCT と DFT (2/2)• y = x を，DCT, DFT 共にはじめの 5 項で近似
44

DCT と KLT• Xi，Xj :第 i 成分と第 j 成分を表す確率変数• Xi と Xj の相関
EXi,Xj XiXj
• この相関が，ρ(< 1) を定数として，|i − j| の指数関数 ρ|i−j| で与えられるとき，ρ → 1 の極限で，KLT は DCT で与えられる• 現実的にも画素間の相関は高い。
• DCT を用いる問題：ブロック歪み (Block distortion)– 変換ブロック境界に見える不連続性– 視覚的に目立つ。
– 復号画像に対して画像処理 (エッジ抽出など) をするときに誤差が生じる。
45

2 次元 DCT

46

ブロック歪み

原画像

JPEG
47

量子化

• 線形量子化を用いる。
• DCT 係数の周波数成分によって，異なる量子化係数を使う。
高周波成分の誤差は低周波成分に比べて目立たない。
• Y と CbCr には異なる量子化係数を使う。
• 量子化テーブル：各係数に対する基準となる量子化係数のテーブル• 量子化テーブルの値に定数を乗算して，実際の量子化係数とする。
• 標準の量子化テーブルの値は決められているが，JPEG データの中に独自の量子化テーブルを埋め込むことが可能

48

量子化テーブル (輝度成分, Y)

V＼H 0 1 2 3 4 5 6 7
0
16 11 10 16 124 140 151 161
112 12 14 19 126 158 160 155
2
14 13 16 24 140 157 169 156
3
14 17 22 29 151 187 180 162
418 22 37 56 168 109 103 177
524 35 55 64 181 104 113 192
649 64 78 87 103 121 120 101
772 92 95 98 112 100 103 199

49

量子化テーブル (色差成分, CbCr)

V＼H 0 1 2 3 4 5 6 7
0
17 18 24 47 99 99 99 99
1
18 21 26 66 99 99 99 992
24 26 56 99 99 99 99 99
3
47 66 99 99 99 99 99 99
4
99 99 99 99 99 99 99 99
5
99 99 99 99 99 99 99 99
6
99 99 99 99 99 99 99 99
7
99 99 99 99 99 99 99 99

50

画像 (1 ブロック)V＼H 0 1 2 3 4 5 6 7
0
123 71 82 129 180 171 171 186
1
128 100 110 140 164 161 176 1952
148 139 151 162 170 179 181 194
3
173 177 182 184 187 194 191 192
4
183 184 188 189 183 189 179 177
5187 183 186 183 175 177 181 1726183 182 181 183 172 176 183 170
7173 170 165 164 158 163 164 156

51

DCT 変換係数
V＼H
0
1
2
3
4
5
6
7
0
1343.80 -75.40 1.22 20.43 22.00 10.22 4.90 1.92
1-83.81 -112.16 1.56 23.44 40.38 -5.45 7.17 8.55
2
-97.00 -42.23 8.17 22.50 24.42 3.17 -3.14 6.69
3
-54.82 -2.59 -5.68 13.94 10.55 2.80 -0.70 4.09
40.75
2.12 -8.46 12.25 2.00 -5.34 2.42 -0.59
5
21.78 -3.74 -4.44 4.79 -1.96 0.32 -0.85 0.86
6
-8.79
1.67 -0.39 3.42 0.16 -0.69 3.57 1.04
7
-0.78
0.54 -4.23 1.48 0.38 0.09 2.75 -2.61

52

DCT 変換係数 (量子化後)
DCT V ＼ H 0 1
0
84 -7
1
-7 -9
2
-70 -3
3
0 0
4
0 0
5
1 0
6
0 0
7
0 0

2
9
0
0
0
0
0
0
0

53

3
1
1
0
0
0
0
0
0

4
0
0
0
0
0
0
0
0

5
0
0
0
0
0
0
0
0

6
0
0
0
0
0
0
0
0

7
0
0
0
0
0
0
0
0

DC 係数のハフマン符号化• 対象：DC 係数 (0, 0) を量子化した整数• 差分符号化：直前のブロックの値との差を送る。
• 出現確率に基づく本当のハフマン符号化ではない。
• その整数を表すための bit 長がカテゴリになる。
• カテゴリに符号を割り振る。
• 1 つの整数は，カテゴリの符号と値 (+極性) を表すものの bit 列となる。
• 標準のハフマンコードブック (符号化テーブル) が決まっている。
次ページ：DC 係数差分 (輝度成分) のハフマンコードブック• JPEG データの中に独自のコードブックを埋め込むことが可能
カテゴリーは変えることはできない。

54

DC 係数差分 (輝度成分) のハフマンコードブック
量子化値

カテゴリー

0
-1, 1
-3, -2, 2, 3,-7, ..., -4, 4, ..., 7-15, ..., -8, 8, ..., 15-31, ..., -16, 16, ..., 31-63, ..., -32, 32, ..., 63-127, ..., -64, 64, ..., 127-255, ..., -128, 128, ..., 255-511, ..., -256, 256, ..., 511-1023, ..., -512, 512, ..., 1023
-2047, ..., -1024, 1024, ..., 2047

0
1
2
3
4
5
6
7
8
9
10
11

符号

付加ビット

00
なし
010
0, 1
011
00, 01, 10, 11
100000, ..., 111
1010000, ..., 1111
110
00000, ..., 11111
1110
000000, ..., 111111
11110
0000000, ..., 1111111
11111000000000, ..., 11111111
1111110000000000, ..., 111111111
11111110 0000000000, ..., 1111111111
111111110 00000000000, ..., 11111111111

例: 0 → 00, 10 → 1011010, −27 → 11000100

55

AC 係数のランレングスハフマン符号化• 対象：AC 係数 ((0, 0) 以外) を量子化した整数
• ジグザグスキャン：右図• 0 が多く続く⇒ ランレングス符号化• ジグザグスキャン中に 0 でない値が現れたときに，– それまで続いてきた 0 の数
– 自身の値の bit 数 (サイズ)に対して 1 つの符号を与える (2 次元ハフマン符号)。
• その符号の後に自身の値 (+極性) を表す付加ビットを出力する。
• 走査の残りが全て 0 の場合は，そのための符号を出力して，そのブロックに対する出力を終了する。
56

動画像符号化 (MPEG)• 動画像：時系列上の複数の画像• MPEG = 動き補償予測 + JPEG
• 動き補償予測– 時間的に近い画像間の類似性が高い。⇒ 予測符号化– 対象画像 (target image)：これから符号化する画像– 参照画像 (reference image)：対象画像を符号化する前に送信済みで，対象画像を符号化するときに利用できる画像– 予測画像：参照画像から生成する対象画像を予測した画像– 参照画像そのものを予測画像とすると，画像の内の動きによる誤差が無視できない。
– 動きを補償して予測画像を生成する。
• 基本的には復号のための規格 (符号化器の設計には自由度がある)
57

動き補償予測• 動き補償予測画像の生成法– 対象画像をブロックで分割する (MPEG 2 では，16×16 画素)。
– 参照画像の中から上記の各ブロックの画像と似ている領域 (ブロックと同じ大きさ) を探す。
– 動きベクトル：ブロックの座標と似ている部分の座標の差• 符号器側では，参照画像は復号済みなので，動きベクトルさえあれば，予測画像を生成できる。
• 動きベクトルはハフマン符号化によって送る。
• 動きベクトル：1 画像，1/2 画素単位58

動き補償予測

参照画像

対象画像

予測画像

参照画像

対象画像

差分画像

59

動きベクトル60

動き補償予測 (実画像)

参照画像

予測画像

対象画像

対象画像 − 参照画像

対象画像 (with MV) 対象画像 − 予測画像
61

MPEG エンコーダのブロック図62

I, P, B ピクチャ (フレーム)I

B B B P B B B P B B B P• I ピクチャ：動き予測補償を行わない．
• P ピクチャ：前の I または P ピクチャで動き予測補償• B ピクチャ：前後の I または P ピクチャで動き予測補償
前のフレームでは隠れていた部分も補償できる．
63

B ピクチャ (フレーム)• 中央のフレームの予測画像を生成する。
• 時間的に後のフレームを使うことによって，前のフレームでは隠れていた部分の情報を使うことができる．

64

MPEG4 AVC(Advance Video Coding) H.264• MPEG 1 (H.261)：ビデオ CD (1.5Mbit/s)• MPEG 2 (H.262)：DVD，地上ディジタル放送• MPEG 4 (H.263)：携帯電話• MPEG 4 AVC (H.264)：Blu-ray，ワンセグ，ビデオカメラ– MPEG2 に比べて，同じ画質でデータ量を半分にできる。
(できない場合もある。)– 遅れて地上ディジタル放送を始める国は，MPEG 4 AVC 方式を用いている (日本より綺麗な画像を見ている)。
– MPEG 4 HVC (High-Performance Video Coding) (H.265)
が策定中。
ただ，しらばくは MPEG 4 AVC が最新機器の主流

65

H.264 の I ピクチャの処理• DCT を使わず，フレーム内予測を利用する。
• 画像に変化があるところ：4 × 4 のブロック• 画像に変化がないところ：16 × 16 のブロック• 予測方向を与える。
(4 × 4 場合 8 種類，16 × 16 のブロックの場合 4 種類)

66

H.264 の動き補償予測• ブロックサイズが可変
16 × 16，16 × 8，8 × 16，8 × 8，8 × 4，4 × 8，4 × 4• 1/4 画素精度の動きベクトル• 動きベクトルの予測• 複数 (2 つ以上の) 画像を参照画像とすることが可能• 参照画像 (復号画像) の生成にデブロッキング (ブロック歪み除去) フィ
ルタを用いることができる。
• デブロッキングフィルタは標準化されている，参照画像を生成する予測ループ内に入れる。
• 予測画像にはブロック歪みが残る。(後述)67

H.264 の差分画像の処理• 4 × 4 の DCT– 8 × 8 の方が符号化効率が良い場合も多い。
• 整数係数 DCT– 16bit 演算で規定されている。
– 符号化器のローカルデコーダと復号器間の齟齬の問題を解決– 差分量子化の場合，齟齬が蓄積していく可能性があった。
• 変換係数の符号化のために，2 種類のエントロピー符号化が規定されている。
– ハフマン符号化– 算術符号化68

H.264 のエントロピー符号化• 指数ゴロム符号– 基本的なシンタックス要素に利用する。
– 整数の符号化において，1 の前に続く 0 の数でその整数の桁数を表す。
• CAVLC (Context-Adaptive Variable Length Coding)(コンテキストについては，JPEG 2000 で説明)
– DCT 係数の符号化に利用する。
– ジグザグスキャン– 0 ランの情報，最後の絶対値 1 のランの情報を加えるが，値とランの情報は分けて格納する。
• CABAC (Context-Adaptive Binary Arithmetic Coding)– 整数値を binary に変換– Q-coder 系 (64 種類の Qe)
69

多重解像度解析• φ(t) : スケーリング関数 (解像度 0)• φ(2−it − n) は，幅を φ(t) を幅を 2i 倍に伸ばして，t 軸方向に 2in だけ平行移動した関数。
• i が小さいほど細かい。
• Vi : φ(2−it − n) (n = 0, ±1, ±2, . . .) で張られる部分空間• φ(2−it − n) は，Vi の基底関数• Vi は i が小さいほど解像度が高い。
• Vi+1 は Vi に含まれる。
解像度の低い空間は，解像度の高い空間に含まれる。
• Vi = Vi+1 + Wi+1 となる空間が存在する。
Wi : ψ(2it − n) (n = 0, ±1, ±2, . . .) で張られる部分空間• ψ(t) : ウェーブレット関数70離散双直交ウェーブレット変換• φ̃(t) を φ(t) の双直交基底，ψ̃(t) を ψ(t) の双直交基底とする。
hφ(t − k), φ̃(t − l)i = δk−lhψ(t − k), ψ̃(t − l)i = δk−lhφ(t − k), ψ̃(t − l)i = 0hψ(t − k), φ̃(t − l)i = 0• Dilation equation
φ(t) =
φ̃(t) =

∞
∑
m=−∞
∞
∑
m=−∞

71

h(m)φ(2t − m)(1)h̃(m)φ̃(2t − m)(2)

ψ(t) =
ψ̃(t) =

∞
∑
m=−∞
∞
∑

g(m)φ(2t − m)(3)g̃(m)φ̃(2t − m)

(4)

m=−∞

• V−1 の任意の信号 f−1(t) を考える。
f−1(t) =∞∑a(−1, k)φ(2t − k)k=−∞

• V−1 = V0 + W0 より，f0(t) ∈ V0 と g0(t) ∈ W0 が存在して，
f−1(t) = f0(t) + g0(t)
となる。

72

(5)

• それぞれ，以下のように展開できる。
∞∑
f0(t) =a(0, n)φ(t − n)g0(t) =n=−∞∞∑b(0, n)ψ(t − n)n=−∞

• 双直交基を使うと，hg0(t), φ̃(t − n)ii = 0, hf0(t), ψ̃(t − n)ii = 0 より，
a(0, n) = hf0(t), φ̃(t − n)i = hf0(t) + g0(t), φ̃(t − n)i= hf−1(t), φ̃(t − n)iおよびb(0, n) = hg0(t), ψ̃(t − n)i = hf0(t) + g0(t), ψ̃(t − n)i= hf−1(t), ψ̃(t − n)iが成立する。
73従って，式 (5)，(2)，(4) より，a(0, n) = hf− n)i
* −1(t), φ̃(t ∞+∑= f−1(t),h̃(m)φ̃(2t − 2n − m)
=
=
=

* ∞
∑

m=−∞

a(−1, k)φ(2t − k),

m=−∞

k=−∞
∞
∑

a(−1, 2n + m)h̃(m)

m=−∞
∞
∑

∞
∑

a(−1, m)h̃(m − 2n)

m=−∞

74

+
h̃(m)φ̃(2t − 2n − m)およびb(0, n) = *hf−1(t), ψ̃(t − n)i+∞∑= f−1(t),g̃(m)φ̃(2t − 2n − m)
=
=
=

* ∞
∑

m=−∞

a(−1, k)φ(2t − k),∞∑+g̃(m)φ̃(2t − 2n − m)

m=−∞

k=−∞
∞
∑

a(−1, 2n + m)g̃(m)

m=−∞
∞
∑

a(−1, m)g̃(m − 2n)m=−∞が成立する。
• この式は，a(−1, n) から a(0, n)，b(0, n) へ信号を分解していることを表
している。
75

• a(−1, n) と h̃(n) または g̃(n) との畳み込み和は，
c(n) =
d(n) =

∞
∑
m=−∞
∞
∑

a(−1, m)h̃(m − n)a(−1, m)g̃(m − n)m=−∞となる。a(0, n), b(0, n) は，c(n) と d(n) の偶数点で構成されている。
⇒ a(−1, n) に対して，h̃(n)，g̃(n) というフィルタをかけてから，
ダウンサンプリング (間引き) をしたものに等しい。
• 画像符号化では，a(−1, n) を画素値と考え，a(0, n) をその低周波分，b(0, n)
をその高周波分と考える。
• 低周波分に信号のパワーが集まっているため，変換符号化の原理でデー
タ量を圧縮できる。
• a(0, n) と b(0, n) から，a(−1, n) を再構成できる (次ページ)。
76• 逆に，f−1(t) = f0(t) + g0(t) より，次式が成立∞∑
f−1(t) =a(−1, k)φ(2t − k)
=
=

k=−∞
∞
∑
n=−∞
∞
∑

a(0, n)φ(t − n) +∞∑b(0, n)ψ(t − n)n=−∞a(0, n)h(m)φ(2t − 2n − m)n=−∞ m=−∞
∞
∞
∑
∑

+
=

∞
∑

b(0, n)g(m)φ(2t − 2n − m)n=−∞ m=−∞∞∞∑∑a(0, n)h(m − 2n)φ(2t − m)m=−∞ n=−∞
∞
∞
∑
∑

+

m=−∞ n=−∞77b(0, n)g(m − 2n)φ(2t − m)• 従って，次式が成立する。
∞∞∑∑
a(−1, k) =a(0, n)h(k − 2n) +b(0, n)g(k − 2n)
=

n=−∞
∞
∑

au(0, n)h(k − n) +

n=−∞

n=−∞
∞
∑

bu(0, n)g(k − n)n=−∞

• ここで，au(0, n) と bu(0, n) は，a(0, n) と b(0, n) をアップサンプリング(値と次の値の間に 0 を挿入する処理) をしたものである。
{
a(0, n/2) (n : even)au(0, n) =0
(n : odd){b(0, n/2) (n : even)bu(0, n) =0
(n : odd)78

離散双直交ウェーブレット変換のフィルタ特性• 双直交関係式に，diliation equation を代入すると，次式が成立する。
∞
∑
m=−∞
∞
∑
m=−∞
∞
∑
m=−∞
∞
∑

h(m + 2n)h̃(m) = δ(n)/2g(m + 2n)g̃(m) = δ(n)/2h(m + 2n)g̃(m) = 0
g(m + 2n)h̃(m) = 0

m=−∞

79

離散双直交ウェーブレット変換のフィルタ特性• H(ω)，H̃(ω)，G(ω)，G̃(ω) を，h(n)，h̃(n)，g(n)，g̃(n) を離散フーリエ変換したものとする。
∞∑
離散フーリエ変換： F (ω) =f (n)e−iωnn=−∞• 先の関係を離散フーリエ変換すると，次式が成立する。
H(ω)∗H̃(ω) + H(ω + π)∗H̃(ω + π) = 1
G(ω)∗G̃(ω) + G(ω + π)∗G̃(ω + π) = 1
H(ω)∗G̃(ω) + H(ω + π)∗G̃(ω + π) = 0
G(ω)∗H̃(ω) + G(ω + π)∗H̃(ω + π) = 0• ウェーブレット変換係数は，信号に対してこのような周波数特性をもつフィルタを施したものと考えることができる。
• 一般に，h(n) はローパスフィルタ，g(n) はハイパスフィルタになる。
80

ウェーブレットの例• Haar ウェーブレット (1 と −1 で構成されている)• CDF97 (Cohen, Daubechies, Feauvea の 9-7) フィルタ– 線形位相 (位相変化が周波数に比例する。)
フィルタ係数が対称画像処理では必要な性質(音声処理では，人間の聴覚は位相を認識できないので不要)– 画像符号化で利用されることが多い。
n
h(n)
g(n)
0
0.6029490182363579
1.115087052456994±1 0.2668641184428723 −0.5912717631142470±2 −0.07822326652898785 −0.05754352622849957±3 −0.01686411844287495 0.09127176311424948±4 0.02674875741080976
81ウェーブレットフィルタバンクの例

低周波の信号は繰り返し低周波と高周波に分解する (上図は 3 段の例)。
82

ウェーブレット変換

83JPEG2000 (ウェーブレットを用いる符号化方式)• JPEG の約 2 倍の効率もつ符号化方式として標準化された。
特に低ビットレート時の符号化性能が良い。
• 符号化手順：– 色変換– 離散ウェーブレット変換– 量子化 (デッドゾーン＋線形量子化)– EBCOT (Embedded Block Coding with Optimal Truncation)– MQ-coder (算術符号化器)• レイト歪み最適化 (Rate-distortion optimizer)• 性能は良いが普及しなかった。
– ストレージ，通信が進歩して JPEG で満足– (平均 2 乗誤差は小さいか) ボケている感じがする。
– (サブマリン) 特許の問題
84ビットプレーン処理
量子化値 5 3 12 8 7 0 31 21
4 bit
0 0 0 0 0 0 1 1
3 bit
0 0 1 1 0 0 1 0
2 bit
1 0 1 0 1 0 1 1
1 bit
0 1 0 0 1 0 1 0
0 bit
1 1 0 0 1 0 1 1• ビットプレーン：2 進数表現における 1 つの桁の 0/1 の 2 次元配列
• 上位 bit から処理 (符号化) してゆく。
• 周波数が低いバンドで 0 の場合は，画像上で対応する位置の高いバン
ドでも 0 の可能性が高い。
• ある値の近傍で，上位ビットが 1 になっているものがあり，自分の上位ビットはすべて 0 である場合，そのビットが 1 になる可能性が高い。
• これらの情報を，エントロピー符号化の確率に反映する。
85

EBCOT (Embedded Block Coding with Optimal Truncation)• Embedded coding：符号列を途中で打ちきっても，精度は落ちるが復号可能な符号 (ビットプレーン)• ビットプレーンをコードブロック (例えば，64×64) に分ける。
• 量子化係数を全て符号化するのではなく，コードブロックごとに打ち切り行う。
• コードブロック内をスキャンする順番 (処理の容易さを考えて決定)。

86

EBCOT の符号化パス• 3 つの符号化パス– Signiﬁcance propagation : 有意である係数の周囲にある有意でない係数の符号化– Magnitude reﬁnement : すでに有意である係数の符号化– Cleanup : それ以外の符号化• EBCOT はビットと共に，そのコンテキストを MQ-coder に送る。
コンテキストは既に送られた情報から分かるもの。
– Signiﬁcance propagation に含まれるビットで，近傍にある有意の係数の数。
– 極性 (±) のビットで，周囲の有意である係数の極性の状況
有意になったときに極性も送る。
– Cleanup で 1 列 (4 係数) がすべて 0 かどうか。

87

MQ-coder• Q-coder 系– 乗算が不要– ハードウエア (論理回路) での実装が可能– 確率 0.75 が 8000 (16 進数) に相当する。
• Qe の値を 46 通りに決めている。(Qe，A − Qe)• 符号化するビットに応じて，Qe の値の状態を遷移させる。
• Qe の値の状態は，コンテキストごとに保持している。
• Q-coder であるため，確率の和が 0.75 から 1.5 という誤差が生じる。
– 実際上の問題は生じていない。
– この確率の精度を上げたい場合は，A の値に応じて数通りの Qe を用
意すれば良い。

88ウェーブレット変換を使った動画像符号化• Motion JPEG 2000
– 基本的には，JPEG 2000 で順次符号化していく。
– ビットストリームが決まっている。
• Dirac (BBC が開発，NHK 技研が参加)• ウェーブレット変換：CDF97– 重複動き補償予測
対象画像を動き補償予測するためのブロックが隣接するブロックとオーバーラップしている。
オーバーラップ部は，それぞれの結果の平均を値とする。
– 整数係の数算術符号化 (計算量は多い)– レートディストーションオプティマイザー
– 同じビットレートでの PSNR では H.264 には及ばない。
– ﬀmpeg (オープンソフト) に実装され公開されている。
89

サブバンド変換• ウェーブレットより 1 回で分解する周波数帯域が多い。
• 解析 (Analysis, Decomposition)
1. 信号に対して複数の解析フィルタで変換し，変換係数を得る。
2. (フィルタ or 基底関数) タップ数：フィルターの長さ
3. それぞれの変換係数をダウンサンプリング (間引き) する。
4. デシメーションファクタ：信号を取り出す割合(通常フィルタの数と一致)• 合成 (Synthesis)
1. それぞれのアップサンプリングする。
係数列に (デシメーションファクタ −1) 個の 0 を挿入する。
2. それぞれの合成フィルタで変換して，結果を足し合わせる。
• フィルターが重複 (オーバーラップ) している。
ブロック歪みが減少する。× リンギングが拡散する。
90

サブバンド変換 (フィルタバンク)

91

DCT の行列表示92サブバンド変換の行列表示 (解析)• 変換基底関数の長さ (フィルタタップ数) : 32

93

サブバンド変換の行列表示 (合成)• 変換基底関数の長さ (フィルタタップ数) : 32

94

完全再構成 (Perfect reconstruction, PR)

2 つの行列の積が単位行列になる。
B0A0 = O
B1A0 + B0A1 = O
B2A0 + B1A1 + B0A2 = O
B3A0 + B2A1 + B1A2 + B0A3 = I

95

B3A1 + B2A2 + B1A3 = O
B3A2 + B2A3 = O
B3A3 = Oポリフェーズ表現を，A(z) = A0 + A1z −1 + A1z −2 + A1z −3

と表す。
96

完全再構成 (ポリフェーズ表現)
解析：

A(z) =N∑

Ak z −kk=0

合成：

B(z) =

N∑

Bk z −kk=0

Reversal matrix J

0 0 ··· 0 1
0 0 ··· 1 0
0 0 · 0 0
0 1 ··· 0 0
1 0 ··· 0 097D : 次の条件を満たす対称行列{+1 フィルタ関数が対称−1 フィルタ関数が反対称

Dii =完全再構成条件

線形位相条件B(z)A(z) = z −N I

A(z) = z −N DA(z −1)JAT ：A の転置行列
パラコンジュゲートの定義

Ã(z) =

N
∑
k=0
98

ATN −k z −k

線形位相完全再構成フィルタバンク (LPPRFB)• A(z) がパラユニタリーであるとは，次式を満たすこと。
Ã(z)A(z) = z −N I
– A(z) と Ã(z) でサブバンド変換とその逆変換になっている。
– 重複直交変換• Ã(z) を N 次の解析側の LPPRFB とする。このとき，A(z) = G(z)F (z)と分解できる。ここで，– F (z) は N − 1 次の LPPRFB– G(z) は可逆な 1 次の FB(フィルタバンク) で，次式を満たす。
G(z) = DG(z −1)D
99

(6)

LPPRFB の構成• A(z) は，次のように分解できる。
A(z) = GN (z)GN −1(z) · · · G1(z)A0– G1(z), G2(z), . . . , GN (z) は，式 (6) を満たす可逆な 1 次の FB– A0 は可逆な行列で，次式を満たす。
A0 = DA0J• 重複双直交変換• 式 (6) を満たす Gi(z) は次のように書くことができる。
)(
)(
)(
)
(
I I
I O
I I
Ui O
Gi(z) =I −I
O z −1II −I
O Vi
Ui，Vi は可逆行列
100

LPPRFB の構成• A0 は次のように書くことができる。
(
)(
)
U0 O
I J
A0 =
O V0
J −I
U0，V0 は可逆行列• 合成フィルタは次のように書くことができる。
−1G (z)−1z −1G (z)−1 · · · z −1G (z)−1A(z) = A−1
z
1
2
N
0

ここで，

(

)(

)

U0−1 OO V0−1
(
)(
)(
)(
)
−1 O
−1I O
1
I
I
z
I
I
U
i
z −1Gi(z)−1 =O I
I −I
4 I −IO Vi−1
1
1
A0 =
2

I J
J −I

101

LPPRFB の設計• A0 は DCT を使って構成できる。
• 可逆行列 U1, V1, U2, V2, . . . , UN , VN を決めるだけ。
• これらが可逆行列ならば，LPPRFB になる。
• 行列を SVD を使った表現でパラメタライズして，(非線形) 最適化によってパラメータを求める。
• 最適化条件– Stop band：
周波数帯域をフィルタ数で分け，自分の帯域以外は通さない。
– エントロピー最小化：
信号の相関を仮定して ρ|i−j|，変換係数の分散の対数和を最小化す
る (変換符号化)。
– No DC leakage：
最低周波数のバンドだけで，DC 成分は完全に再構成できる。
102

画像符号化に関するサブバンド変換の文献• Wavelet : Daubechies, 1988 [1], 1992 [2].
• Lapped orthogonal transform (LOT) : Malvar et al., 1989 [3].
• Generalized LOT (GenLOT) : Queiroz et al., 1996 [4].
• Generalized lapped transform (GLT) : Chan, 1995. [5]Lapped biorthogonal transform (LBT) : Malvar et al., 1998 [6].
• Generalized LBT (GLBT) : Tran et al., 2000 [7].
• Variable length LOT (VLLOT) : Tran et al., 1999 [8].
Generalized unequal length LOT (GulLOT) : Nagai et al., 2000 [9].
• VLGLBT : Tran et al., 1998 [10].
• Adaptive LT (ALT) : Tanaka and Yamashita, 2002 [11].
• GVLLT : Tanaka, Hirasawa, and Yamashita, 2006 [12].

103GenLOT (48 taps)

n=0

n=1

n=2

n=3

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

104

n=4

n=5

n=6

n=7

GulLOT (48-16 taps)

n=0

n=1

n=2

n=3

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

0.4

0.4

0.2

0.2

0

0

-0.2

-0.2

-0.4

-0.4

105

n=4

n=5

n=6

n=7

サブバンド変換の例

106サブバンド変換係数の符号化• 変換係数に空間的な冗長性が残されている– 空間的に近い変換係数は類似した値– 低周波成分の変換係数が小さい場合は，対応する点の高周波成分の変換係数も小さい。
⇒ ビットプレーンの走査で低い周波数で打ち切ることが可能.
• 木構造を生成する。
– Embedded zero tree (EZW) : Shapiro, 1993 [13].
– Set Partitioning in Hierarchical Trees (SPIHT) : Said et al., 1996 [14].
• コンテキストモデリングによる予測– Embedded Block Coding with Optimal Truncation (EBCOT) :JPEG 2000

107

ウェーブレット変換108

係数の木構造109

SPIHT
ノード (i, j) の処理で利用する集合• O(i, j)：ノード (i, j) の子供• D(i, j)：ノード (i, j) の子孫• L(i, j) = D(i, j) − O(i, j).
• 木の根のノードの集合
処理全体で利用する集合• LSP : 有意なノード (i, j) の集合• LIP : 有意でないノード (i, j) の集合• LSP : 有意でない集合を表す (i, j) の集合– type A : D(i, j) を表す– type B : L(i, j) を表す• ci,j : 符号化する係数110• Sn(i, j)：ノード (i, j) の 2n に対する有意性{
1 (|ck,l | ≥ 2n)Sn(i, j) =0 (else)• Sn(A)：ノードの集合 A の 2n に対する有意性{
1 ({max(k,l)∈A |ck,l |} ≥ 2n)
Sn(A) =
0 (else)111

SPIHT のアルゴリズム
1. 初期化j()k• n = log2 max(i,j){|ci,j |}• LSP を空集合にする。
• LIP を H のすべのノードとする。
• LIS を H で子孫を持つすべのノードとする (type A)。
2. Sorting Pass(a) LIP のすべての (i, j) に対して次の処理を実行
i. Sn(i, j) を出力
ii. Sn(i, j) = 1 ならば，(i, j) を LSP に加え，ci,j の極性を出力

112

(b) LIS のすべての (i, j) に対して次の処理を実行
i. その要素が type A ならば，• Sn(D(i, j)) を出力する。
• Sn(D(i, j)) = 1 ならば，すべての (k, l) ∈ O(i, j) に対して次の処理を実行する。
– Sn(k, l) を出力する。
– Sn(k, l) = 1 ならば，(k, l) を LSP に加え，ck,l の極性を出力– Sn(k, l) = 0 ならば，(k, l) を LIP に加える。
– L(i, j) 6= φ ならば，(i, j) を LIS に type B ノードとして加える。
– (i, j) を LIS から取り除く。
ii. その要素が type B ならば，• Sn(L(i, j)) を出力する。
• もし Sn(L(i, j)) = 1 ならば，次の処理を実行する。
– すべての (k, l) ∈ O(i, j) を，type A として LIS に加える。
– (i, j) を LIS から取り除く。
113

3. Reﬁnement Pass:
この Sorting pass の前にあった LSP のノード (i, j) に対して，|ci,j | の nbit
目を出力する。
4. Quantization-Step Update: n ← n − 1 とする。
SPIHT の特徴
• アルゴリズムが簡単• ハフマン符号化や算術符号化を使わなくても高い符号化性能(EBCOT には少し劣るがそれほどでもない。)

114

Generalized variable length lapped transform• 低い周波数帯のフィルタには長い基底関数⇐ ブロック歪みを抑制する。
• 高い周波数帯のフィルタには短い関数⇐ リンギングの拡散を抑える。
• 直交 (双直交) の条件は強く，フィルタの形が自由に選べない。
ブロック境界でエッジを持つ関数になる。
⇒ 復号画像は合成フィルタの関数の線形和になる。
合成フィルタの関数は重要• 解析フィルタは繰り返しで実現される。

115

実験結果 (原画像)116

実験結果 (繰り返し回数)100
barbara mu=1
boat mu=1
lenna mu=1
barbara mu=0.8
boat mu=0.8
lenna mu=0.8

90
80
70
MSE

60
50
40
30
20
10
0
0

5

10
Number of Iterations

117

15

20

PSNR と bit rate
• PSNR (Peak Signal to Noise Ratio)
原画像と復号画像の画素値に関する平均 2 乗誤差
PSNR = −10 log10(画素値の最大値)2• ビットレート
画像を表すためのデータ量 (bit)bit rate =画像のピクセル数118

実験結果 (PSNR vs. bit rate)
38

36

34

PSNR[dB]

32

30

28

26
combination1
combination2
combination3
GenLOTGLBTGULLOT
VLLBTWavelet

24

22

20
0

0.2

0.4

0.6
Bitrate[bpp]

0.8

119

1

1.2

実験結果 (復号画像)

GenLOT

GVLLT

120

実験結果 (拡大画像)

GenLOT

GVLLT

121

サブバンド動画像符号化
目的：ブロック歪みの少ない動画像符号化
ブロック歪みの原因と対策：
1. ブロック変換⇒ サブバンド変換 (重複変換) の適用
2. ブロック単位の動き保証予測⇒ 適応デブロッキングフィルタの適用
参照画像を切り貼りして予測画像を作成すときにブロック歪みが生じる。
ブロック歪みが生じる前の参照画像を使うことができる。
⇒ ブロック境界のエッジが本当のエッジかブロック歪みかわかる。
⇒ 適応デブロッキングフィルタが効率的に働く。
× 通常のブロック変換を使う方法では参照画像に既にブロック変換から生じるブロック歪みが生じている。
⇒ 画像のエッジを検出することが難しい。
122

MPEG エンコーダのブロック図123

提案手法のエンコーダのブロック図124

エッジ適応デブロッキングフィルタ

125

実験

Original image (Intersection)126

実験結果 (PSNR vs. bit rate)

Intersection: MPEG-2 vs Proposed method (I,P,...,P)
36

32

PSNR

PSNR

34

30
28

I-picture
MPEG-2
proposed method

26
0.3 0.4 0.5 0.6 0.7 0.8 0.9
bpp

1

1.1

Intersection: MPEG-2 vs Proposed method (I,P,...,P)
36
35
34
33
32
31
30
29
P-picture
MPEG-228
proposedmethod27
0.05

I-Frame

0.1

0.15
bpp

P-Frame

127

0.2

0.25

実験結果

MPEG2 (ﬀmpeg)

Proposed128

実験結果 (拡大画像)

MPEG2 (ﬀmpeg)

Proposed129

まとめ• 画像符号化の基盤技術– エントロピー符号化– 予測符号化– 変換符号化 (DCT，KL 変換)• 標準的画像符号化法– JPEG– MPEG, MPEG 4 AVC (H.264)• 離散コサイン変換を用いない画像符号化– ウェーブレット変換– サブバンド変換 (重複変換)• 画像符号化は情報技術の集大成• マルチメディア社会のなかで高い重要性
130

参考文献
[1] I. Daubechies, “Orthonormal bases of compactly supported wavelets,” Communications on Pure and Applied Mathematics,
vol.41, no.7 pp.909–996, Oct. 1988.
[2] M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies, “Image coding using wavelet transform,” IEEE Transactions on
Image Processing, vol.1, no.2, pp.205–220, Apr 1992.
[3] H.S. Malvar and D.H. Staelin, “The LOT: transform coding without blocking eﬀects,” IEEE Transactions on Acoustics,
Speech and Signal Processing, vol.37, no.4, pp.553-0559, Apr 1989.
[4] R.L. de Queiroz, T.Q. Nguyen, and K.R. Rao, “The GenLOT: generalized linear-phase lapped orthogonal transform, ”IEEE Transactions on Signal Processing, vol.44, no.3 pp.497–507, Mar 1996.
[5] S.C. Chan, “The generalized lapped transform (GLT) for subband coding applications,” Proceedings of 1995 IEEE International Conference on Proceedings of the Acoustics, Speech, and Signal Processing, vol.2, pp.1508–1511, 9–12 May
1995.
[6] H.S. Malvar, “Biorthogonal and nonuniform lapped transforms for transform coding with reduced blocking and ringing
artifacts,” IEEE Transactions on Signal Processing, vol.46, no.4, pp.1043-1053, Apr 1998.
[7] T.D. Tran, R.L. de Queiroz, T.Q. Nguyen, “Linear-phase perfect reconstruction ﬁlter bank: lattice structure, design, andapplication in image coding,” IEEE Transactions on Signal Processing vol.48, no.1, pp.133–147, Jan 2000.
[8] T.D. Tran, M. Ikehara, and T.Q. Nguyen, “Linear phase paraunitary ﬁlter bank with ﬁlters of diﬀerent lengths and its
application in image compression,” IEEE Transactions on Signal Processing, vol.47, no.10, pp.2730–2744, Oct. 1999.
[9] T. Nagai, M. Ikehara, M. Kaneko, and A. Kurematsu, “Generalized unequal length lapped orthogonal transform for
subband image coding,” IEEE Transactions on Signal Processing, vol.48, no.12, pp.3365–3378, Dec. 2000.
131

[10] T.D. Tran, R.L. de Queiroz, and T.Q. Nguyen, “The variable-length generalized lapped biorthogonal transform,” Proceedings of 1998 IEEE International Conference on Image Processing, vol.3, pp.697–701, 4–7 Oct. 1998.
[11] T. Tanaka and Y. Yamashita, “An adaptive lapped biorthogonal transform and its application in orientation adaptive
image coding,” Signal Processing, vol.82, no.11, pp.1633–1647, Nov. 2002.
[12] T. Tanaka, Y. Hirasawa, and Y. Yamashita, “Variable-length lapped transform with combination of multiple synthesis
ﬁlter banks for image coding,” IEEE Transactions Image Processing, vol.15, no.1, pp.81–88, Jan. 2006.
[13] J.M. Shapiro, “Embedded image coding using zerotrees of wavelet coeﬃcients,” IEEE Transactions on Signal Processing,vol.41, no.12 pp.3445–3462, Dec. 1993.
[14] A. Said and W.A. Pearlman, “A new fast and eﬃcient image codec based on set partitioning in hierarchical trees,” IEEE
Transactions on Circuits and Systems for Video Tech., vol.6, pp.243–250, June 1996.
[15] Nasharuddin Zainal, Toshihisa Tanaka and Yukihiko Yamashita, “Moving picture coding by lapped transform and edge
adaptive deblocking ﬁlter with zero pruning SPIHT,” IEICE Trans. on Information and Systems, vol. E93-D, no. 6,
pp.1608–1617, June, 2010.
[16] 小野定康, 鈴木純司, “わかりやすい JPEG2000 の技術,” オーム社, 2003.
[17] 大久保榮, 角野眞也, 菊池義浩, 鈴木輝彦, “H.264/AVC 教科書,” インプレス, 2004.
[18] Telecommunication standarization sector of ITU, “Advanced video coding for generic audiovisual services,” ITU, 2007.

132