ゼロ 値予測に基づいたDCT演算削減手法の提案とその評

ゼロ値予測に基づくDCT
演算数削減手法の提案とその評価
○西田 敬宏
井上 弘士
Vasily G. Moshnyaga
発表の流れ
1.背景・目的
2.DCT/量子化処理
3.ゼロ値予測に基づくDCT演算数削減手法
4.実験評価
5.まとめ・今後の課題
背景
デジタルカメラ、携帯電話、PDAなどの普及
バッテリ-駆動時間の延長
チップ発熱の抑制
低消費エネルギー化は重要!
目的
画像圧縮符号化器(MPEG)の低消費エネルギー化を実現
DCT処理に着目
ゼロ値予測に基づくDCT演算数削減手法の
提案とその評価
MPEG符号化器
bit control
Video
Input
-
DCT
Q
IQ
IDCT
+
ME
Frame
Memory
VLC
buffer
Coded
bit
Stream
DCT:離散コサイン変換
IDCT:逆DCT
Q:量子化
IQ:逆量子化
VLC:可変長符号化
DCTの特徴
出現頻度に偏りが生じる
情報省略を行いやすい
79
75
79
82
82
86
94
94
619
-29
8
2
1
-3
0
1
76
78
76
82
83
86
85
94
22
-6
-4
0
7
0
-2
-3
72
75
67
78
80
78
74
82
11
0
5
-4
-3
4
0
-3
74
76
75
75
86
80
81
79
2
-10
5
0
0
7
3
2
73
70
75
67
78
78
79
85
6
2
-1
-1
-3
0
0
8
69
63
68
69
75
78
82
80
1
2
1
2
0
2
-2
-2
76
76
71
71
67
79
80
83
-8
-2
-4
1
2
1
-1
1
72
77
78
69
75
75
78
78
-3
1
5
-2
1
-1
1
-3
入力データ(画素値)
DCT
出力データ(DCT係数)
2次元DCT(8×8)
7
g k , j   C k ( 2i 1) xi , j
(1)
i 0
8×64+8×64=1024
7
X k ,l   C l ( 2 j 1) g k , j
(2)
j 0
1 / 2 2
Cn  
 cos[n / 16] / 2
(1)
0
1024回の積和処理が必要
(n  0)
(n  0)
x方向 1次元DCT
i
7
0
(2)
k
7
0
0
j
l
7
7
y方向 1次元DCT
量子化処理
高周波成分の値を0に近似
情報量の削減
量子化入力値
量子化出力値=
量子化ステップ
量子化ステップ=16
619
-29
8
2
1
-3
0
1
39
-2
1
0
0
0
0
0
22
-6
-4
0
7
0
-2
-3
1
0
0
0
0
0
0
0
11
0
5
-4
-3
4
0
-3
1
0
0
0
0
0
0
0
2
-10
5
0
0
7
3
2
0
-1
0
0
0
0
0
0
6
2
-1
-1
-3
0
0
8
0
0
0
0
0
0
0
1
1
2
1
2
0
2
-2
-2
0
0
0
0
0
0
0
0
-8
-2
-4
1
2
1
-1
1
-1
0
0
0
0
0
0
0
-3
1
5
-2
1
-1
1
-3
0
0
0
0
0
0
0
0
入力データ(DCT係数)
量子化
出力データ
1ブロック、64回の除算が必要
ゼロ値予測に基づくDCT演算数削減手法
•量子化後、多くの高周波成分の値は0
•自然画像で周波数が急激に変化する場面は少ない
DCT処理中に高周波成分が0となる部分を予測
DCT出力結果が連続N個0となった場合
残りのDCT係数を全て0と予測
例
ゼロ値予測開始点
0連続数N=2の場合
0
1
2
3
4
5
6
7
0
619
-29
8
2
1
-3
0
1
1
22
-6
-4
0
7
0
-2
-3
2
11
0
5
-4
-3
4
0
-3
3
2
-10
5
0
0
7
3
2
4
6
2
-1
-1
-3
0
0
8
5
1
2
1
2
0
2
-2
-2
6
-8
-2
-4
1
2
1
-1
1
7
-3
1
5
-2
1
-1
1
-3
例
ゼロ値予測開始点
0連続数N=2の場合
0
1
2
3
4
5
6
7
0
619
-29
8
2
1
-3
0
1
1
22
-6
-4
0
7
0
-2
-3
2
11
0
5
-4
-3
4
0
-3
3
2
-10
5
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
35個のDCT係数
DCT処理
0連続数N=2の場合
ゼロ値予測開始点
従来手法
8×64+8×64=1024回
619
-29
8
2
1
-3
0
1
22
-6
-4
0
7
0
-2
-3
1024回の積和
11
0
5
-4
-3
4
0
-3
提案手法
2
-10
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
35個のDCT係数演算削減
8×64+8×29=744回
280回の積和処理削減
ゼロ値予測対象DCT係数
量子化処理
量子化入力値
量子化出力値=
量子化ステップ
量子化ステップ=16
従来手法
提案手法
39
-2
1
0
0
0
0
0
39
-2
1
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
除算64回
除算29回
35回演算削減
提案手法の利点、欠点
利点
ゼロ値予測成功の場合、画質の劣化なしに演算削減
欠点
ゼロ値予測ミスの場合、画質の劣化
実験環境
実験データ
missa (176×144)
150Frame
foreman (176×144)
298Frame
carphone (176×144)
382Frame
salesman (352×288)
300Frame
実験1
0
1
2
3
4
5
6
7
様々な適用方式を検討
ゼロ値予測
輝度成分(Y)
色差成分(Cr,Cb)
C
×
○
Y0+C
○
○
Y3+C
3行目以降 ○
○
Y4+C
4行目以降 ○
○
DCT演算数(N=9)
0連続数N=9
輝度ブロック4、色差ブロック(Cr、Cb)2
DCT演算数
carphone
100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%
C
foreman
Y0+C
missa
Y3+C
手法別
salesman
Y4+C
量子化演算数(N=9)
量子化演算数
0連続数N=9
100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%
輝度ブロック4、色差ブロック(Cr、Cb)2
carphone
foreman
C
Y0+C
missa
Y3+C
手法別
salesman
Y4+C
PSNR(N=9)
0連続数N=9
輝度ブロック4、色差ブロック(Cr、Cb)2
carphone
foreman
missa
salesman
70
PSNR(dB)
60
50
40
30
20
10
0
従来手法
C
Y0+C
手法別
Y3+C
Y4+C
結論(適用方式)
どの部分にゼロ値予測を適用するのか
演算数、画質(PSNR)、回路制御の3点を考慮
Y0+C方式を適用
実験2
ゼロ値予測の正確さの調査
画質の劣化は、いかにゼロ値予測を正しく行えるかに依存
最適なN値を選択
0連続数Nの値を変化
N=1
N=2
N=3
N=4
N=5
N=6
N=7
N=8
N=9
N=10
N=11
N=12
N=13
N=14
N=15
N=16
N=17
N=18
N=19
N=20
DCT演算削減率
DCT演算削減率(N=1~20)
carphone
foreman
missa
0連続数
salesman
50%
40%
30%
20%
10%
0%
N=1
N=2
N=3
N=4
N=5
N=6
N=7
N=8
N=9
N=10
N=11
N=12
N=13
N=14
N=15
N=16
N=17
N=18
N=19
N=20
量子化演算削減率
量子化演算削減率(N=1~20)
carphone
foreman
0連続数
missa
salesman
100%
80%
60%
40%
20%
0%
N=1
N=2
N=3
N=4
N=5
N=6
N=7
N=8
N=9
N=10
N=11
N=12
N=13
N=14
N=15
N=16
N=17
N=18
N=19
N=20
PSNR(dB)
PSNR (N=1~20)
carphone
foreman
0連続数
missa
salesman
70
60
50
40
30
20
10
0
結論(ゼロ値予測の正確さ)
0連続数Nが小さいほど、演算数削減可能
0連続数Nが大きいほど、PSNRは向上
N=9が適している
画質の劣化 平均4.55dB
画像例
従来手法
提案手法
PSNR=53.44dB
PSNR=48.30dB
5.1dB劣化
従来と同じ画質(PSNR)
0連続数Nを増加
DCT演算
削減率(%)
量子化演算
削減率(%)
PSNR
劣化(dB)
N=9
21.06
43.06
4.55
N=17
12.88
26.43
0.86
ほぼ、画質の劣化なしに演算数削減
要求される画質によって、変更できる
まとめ



DCT/量子化の演算数削減手法を提案とその評価
0連続数N=9の場合、DCT演算数を平均22%、
量子化演算数を平均46%削減。PSNRは平均
4.55dB劣化
0連続数N=17の場合、DCT演算数を平均13%、
量子化演算数を平均26%削減。PSNRは平均
0.86dB劣化
今後の課題
ゼロ値予測判定コスト
 より詳細な消費電力モデルを用いた評価
 色々な画像データ(サイズの大)を用いた調査

並列処理
1行(N=8以上)全て0が出現した場合
ゼロ値予測を適用
619 -29
8
2
1
-3
0
1
22
-6
-4
0
7
0
-2
-3
11
0
5
-4
-3
4
0
-3
2
-10
5
0
0
7
3
2
6
2
-1
-1
-3
0
0
0
0
0
0
0
0
0
0
0
-8
-2
-4
1
2
1
-1
1
-3
1
5
-2
1
-1
1
-3
2行(N=16以上)全て0が出現した場合
ゼロ値予測を適用
619 -29
8
2
1
-3
0
1
22
-6
-4
0
7
0
-2
-3
11
0
5
-4
-3
4
0
-3
2
-10
5
0
0
7
3
2
6
2
-1
-1
-3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
-3
1
5
-2
1
-1
1
-3
DCT演算数(並列処理)
演算数
1行(N=8~15)
100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%
salesman
carphone
2行(N=16~23)
foreman
画像データ
missa
量子化演算(並列処理)
演算数
1行(N=8~15)
100%
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%
salesman
2行(N=16~23)
carphone
foreman
画像データ
missa
PSNR(並列処理)
従来手法
1行(N=8~15)
2行(N=16~23)
70
PSNR(dB)
60
50
40
30
20
10
0
salesman
carphone
foreman
画像データ
missa
結論(並列処理)
DCT演算
削減率(%)
量子化演算
削減率(%)
PSNR
劣化(dB)
1行(N=8)
19.76
43.40
4.66
2行(N=16)
11.11
25.65
0.89
並列処理でも、ゼロ値予測を適用可能
高速アルゴリズムにも適用可能
高速アルゴリズム
DCT演算
削減率(%)
量子化演算
削減率(%)
PSNR
劣化(dB)
Chen
DCT
1行
15.65
34.76
2.83
2行
7.09
17.44
0.37
高速
DCT
1行
21.98
46.95
4.92
2行
11.73
25.51
0.90
N=1
N=2
N=3
N=4
N=5
N=6
N=7
N=8
N=9
N=10
N=11
N=12
N=13
N=14
N=15
N=16
N=17
N=18
N=19
N=20
成功確率
実際の確率
残り全て0
salesman
carphone
0連続数
foreman
missa
90%
80%
70%
60%
50%
40%
30%
20%
10%
0%
N=1
N=2
N=3
N=4
N=5
N=6
N=7
N=8
N=9
N=10
N=11
N=12
N=13
N=14
N=15
N=16
N=17
N=18
N=19
N=20
成功確率
実際の確率
残り全て±7
salesman
carphone
0連続数
foreman
missa
120%
100%
80%
60%
40%
20%
0%