復習
復習
微分を併用して効果的に圧縮
微分は予測（０次の外挿）
→m
↓
n
64 KB （100%）
原画像 x(n)
原画像 x(n)
微分処理
予測処理
予測誤差+128
y(n,m) = x(n,m) - x(n,m-1)
y(n)= x(n) - x(n-1)
ハフマン符号化
y(n)= x(n) - x(n-1)
n-2
圧縮データ
圧縮データ
-255
輝度値→
角周波数 ω
π
2
予測が
当たる
H ( e j )
0
角周波数 ω
π
Y ( e j )
0
角周波数 ω
分散が
小さくなる
π
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
n
n+1
n は整数
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
データ量を圧縮できる
0
n-1
ヒストグラム
圧縮する＝分散を小さくする
画像の
スペクトル
y(n)
255
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
X ( e j )
予測誤差
ハフマン符号化
↑
頻
度
54 KB （84%） < 94%
x(n)
↓
予測値 x(n-1)
↓
圧縮する＝分散を小さくする
↑
画像の確
率
ヒストグラム
画像の
スペクトル
X ( e j )
データ量を
圧縮できる
H  log 2  y2
輝度値 i →
Y ( e j ) 
予測が
当たる
予測処理
j
Hy 
j
H (e ) X (e )
予測が
当たる
エントロピーと
分布の関係
 y2 
このイメージは、現在表示できません。
分布が
偏る
↑
確
率
1



0




P ( y ) log 2 P ( y ) dy
 2y 
2
Y ( e j ) d 
 min
輝度値 i →

分散が
小さくなる
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
分布が
偏る



P ( y )  y 2 dy
分散とエントロピ
分散とエントロピ
確率密度関数 P(x) が以下である信号 x(n）について、
2 
エントロピー H と分散 σ 2 の関係を示せ。
2
1 / 
P ( x)  
 0


/2 1

2
 

for | x |  / 2

H 
x 2 dx
 2

0
/2
0
for | x |  / 2
P ( x ) x 2 dx
H 
2 






P ( x ) log 2 P ( x ) dx
H  log 2 
P ( x ) x 2 dx
2  x3 
  3  0
2

12
P ( x ) log 2 P ( x ) dx
log 2
0
1
dx

/2
dx
0
分散を小さく
→ データ圧縮
H  log 2 
2

1
log 2  2  log 2 12
2

All Rights Reserved / M.Iwahashi / Nagaoka University of Technology

/2 1

x dx
/2
分散を小さく
→ データ圧縮


2 log 2 


 log 2 
2

ヒント



H  log 2  2
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
最小自乗法とは？
（パラメータが２つ）
最小自乗法（解法）
N 1
I
自乗誤差
データ ● とフィット
するように近似直線
y(x) を決定したい．
 y( x )  y 
i
2
i
2
i
i 0
が最小となるように，
→ (a, b) を求める．
2
i
i
i 0
N 1
I
N 1
 y( x )  y    a  b x  y 
i
y0
y(x0)
y2
y1
x0
x1
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
x2
I
I
 0,
0
a
b
より，連立方程式の解
として (a, b) が求まる．
y ( xi )  a  b xi

df ( g ( x)) df dg


dx
dg dx
より，
I

a

a
I

b

b
N 1
N 1
 a  b x  y  ＝ 2 a  b x  y 
2
i
i
i
i 0
N 1
 0
i
i 0
N 1
 a  b x  y  ＝ 2 a  b x  y  x 
2
i
i
i
i 0
i
0
i
i 0
すなわち，
y(x)= a + b･x

i 0
 N 1

1
 i 0
 N 1

xi

 i 0
以上より，
N 1
 N 1 

y 
 i 0 i 
i 0

    N 1
N 1
b

xi2 
yi 
x
i



i 0
 i 0



  x  a 

 

a
  
b
i
 x   x   y 
 x 1   x   x 1   y x 
1
2
i
i


xi  
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
2
i
i
i
i
i i
最小自乗法とは？
最小自乗法（解法）
（パラメータが１つ）
N 1
I
自乗誤差
データ ● とフィット
するようにパラメータ
a を決定したい．
N 1
I
 a  y 
i 0
 a  y 
2
より，
i
i 0
I

a
が最小となるように，
→ a を求める．

a
N 1
y2
a
x0
0
i
i 0
i 0


yi  0
i 0
以上より，
N 1
より a が求まる．
x1
N 1
2
i
N 1
1 
i 0
I
0
a
y1
N 1
 a  y  ＝ 2 a  y 
すなわち，
a
y0
2
i
a
x2

yi

1
i 0
N 1

1
N
N 1

yi
i 0
i 0
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
最適な予測器
最適な予測器
を設計しよう
を設計しよう
以下の予測処理，
X(z)
y(n) = x(n) + c x(n-1)
分散を
最小化する
予測処理
+
Y(z)
z-1
c
Y ( z )  (1  c z 1 ) X ( z )
最適化する
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
において，与えられた入力信号 “x(n)”
に対する最適な “c” の値を求めたい．
データ量が
最小になる
H  log 2  y2
 2y 
1
N
 y(n)  m 
my 
1
N
 y (n)
y
n
2
予測後のデータ量 ∝ log( 予測誤差の分散 )
⇒ 予測誤差の分散を最小化する
n
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
最適化の方法
３．計算すると

2
c y
１．予測誤差 “y(n)” の分散値を “c” で表す.
 y2


1
N
1
N
y
2

1
N
 2x(n)  c  x(n  1)
平均値＝０
としている
(n)
n
x(n)  c  x(n  1)
my 
2
1
N
n
x(n)  c  x(n  1)
n
 y (n)  0

c

c
x(n)  c  x(n  1)  0
x(n)  c  x(n  1)
x(n)  c  x(n  1) x(n  1)
n
n
0
0
n
 x(n) x(n  1)  c   x (n  1)
2
２．得られた分散値を最小とする “c” は次式を満たす．
n
 2y
0
c
0
n
４．以上より、
以上を解けば最適係数値が決定される．
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
と
自己相関
低域に偏在
f
0
白色雑音
0
2
n
 x(n) x(n  1)
n
自己相関
画像信号の
自己相関
相関は無い
f
白色雑音の
周波数振幅特性
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
と
 x (n  1)
k
0
全帯域に分布
t
周波数振幅特性
 R0 


 R1 

近傍が相似
画像信号の
周波数振幅特性
画像信号
最適な予測係数は
自己相関で決まる
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
周波数振幅特性
t
 R1
c
R0
k
0
白色雑音の
自己相関
画像信号
周波数
振幅特性
(対数表示)
All Rights Reserved / M.Iwahashi / Nagaoka University of Technology
自己相関
（分散で正規化）