狠狠撸

2020年度秋学期　画像情報処理
浅野　晃
関西大学総合情報学部
主成分分析とKarhunen-Loève変換
第７回

2020年度秋学期　画像情報処理　第7回　主成分分析とKarhunen-Loève変換 (2020. 11. 6)

312020年度秋学期　画像情報処理　／　関西大学総合情報学部　浅野　晃
画像情报圧缩の必要性
3
この画像では，１画素の明るさを0?255の整数で表す
カラー画像ならば，３倍の１５メガバイト必要
１画素に，２進数８桁 = ８ビット = １バイト必要
５００万画素のデジカメの画像は，約５メガバイト必要
こういう画像は，１画素 = １６ビットで，２倍の１０メガバイト
必要なこともある
動画ならば，(1/30)秒でこれだけのデータ量！

JPEG方式による画像圧縮
4
画像を波の重ね合わせで表わし，一部を省略して，データ量を減らす

4
8×8ピクセルずつの
セルに分解

4
ひとつのセルを，
これらの波の重ね合わせで表す8×8ピクセルずつの
セルに分解

4
セルに分解
細かい部分は，どの画像でも大してかわら
ないから，省略しても気づかない

4
セルに分解
細かい部分は，どの画像でも大してかわら
ないから，省略しても気づかない
省略すると，データ量が減る

画像情报圧缩の例
5
データ量：80KB データ量：16KB

画像情报圧缩の例
5
データ量：80KB データ量：16KB
（８×８ピクセルのセルが見える）

ところで，本当に「波」でいいんですか？

ところで，本当に「波」でいいんですか？
まあ，結局「波」でいいんですけどね…

もっと根本的な原理から説明します。

もっと根本的な原理から説明します。
「主成分分析」と「直交変換」

重要な成分と，そうでない成分
9
しばらく，画素が２つしかない画像を考える
たくさんの２画素画像を考える
ひとつの２画素画像は，
この図の１つの点で表される
++
+
+ +
+
+
x1
x2
画素１の値
画素２の値
（散布図という）

どちらかの画素値を省略できるか？
10
たくさんの２画素画像が
こんなふうに散らばって（分布して）いたら
++
+
+ +
+
+
x1
x2
画素１の値
画素２の値

10
各画像の違いを表現するのには，
どちらの画素も省略することはできない
++
+
+ +
+
+
x1
x2
画素１の値
画素２の値

10
どちらの画素値の分散も大きい
各画像の違いを表現するのには，
どちらの画素も省略することはできない
++
+
+ +
+
+
x1
x2
画素１の値
画素２の値

こんな分布なら
11
各画像の違いを表現するのに，
画素２はそれほど必要ない
画素２の値は，どの画像でもあまり変わりない
（分散が小さい）
画素１の値
画素２の値
x1
x2
++
+
+
+
+
+

11
画素２の値は，それらの平均に置きかえてしまってもそれほど変わらない
画素１の値
画素２の値
x1
x2
++
+
+
+
+
+
　
++ + + + + +

11
画素２の値は，それらの平均に置きかえてしまってもそれほど変わらない
画素１の値
画素２の値
x1
x2
++
+
+
+
+
+
　
++ + + + + +
画素２の値はいちいち記録しなくてもいいから，データ量が半分に減る

そういう都合のいい分布に変換できないの？
12
++
+ + +
+
+
x1
x2
画素１の値
画素２の値

12
散布図上である方向に広がっているなら
（x1, x2に相関があるなら）できます。こうすればいい
++
+ + +
+
+
x1
x2
画素１の値
画素２の値

12
+
+ +
+
+ + +
x2
画画
素
２
の
値
z(2)
z(1)

12
+
+ +
+
+ + +
x2
画画
素
２
の
値
z(2)
z(1)
x1, x2を回転して，新たにz(1) , z(2) とすればよい

12
+
+ +
+
+ + +
x2
画画
素
２
の
値
z(2)
z(1)
z(1) の分散がもっとも大きくなるように回転する

12
+
+ +
+
+ + +
x2
画画
素
２
の
値
z(2)
z(1)
このとき z(1) とz(2) の相関がなくなる

12
+
+ +
+
+ + +
x2
画画
素
２
の
値
z(2)
z(1)
これをするのが主成分分析
このとき z(1) とz(2) の相関がなくなる

主成分分析
13
x1, x2から次の式で zを求めるものとし，
zの分散V(z)が最大になるa1, a2を求める
z = a1x1 + a2x2

主成分分析
13
x1, x2から次の式で zを求めるものとし，
zの分散V(z)が最大になるa1, a2を求める
z = a1x1 + a2x2
V(z)を求めるために，次の量を用いる
?x1, ?x2， x1, x2の全画像にわたる平均
x1i, x2i n枚中のi番目の画像の，x1, x2の値
s11, s22，x1, x2の分散

さらに共分散も用いる
14
s12 = s21 =
1
n
n
i=1
(x1i ? x1)(x2i ? x2)
　　
x1, x2の共分散

14
s12 = s21 =
1
n
n
i=1
(x1i ? x1)(x2i ? x2)
　　
x1, x2の共分散
++
+ + +
+
+
x1
x2
x2
x1
< 0
< 0
> 0
> 0
( x1i
– x1
)( x2i
– x2
) ( x1i
– x1
)( x2i
– x2
)
( x1i
– x1
)( x2i
– x2
)( x1i
– x1
)( x2i
– x2
)

14
s12 = s21 =
1
n
n
i=1
(x1i ? x1)(x2i ? x2)
　　
x1, x2の共分散
++
+ + +
+
+
x1
x2
x2
x1
< 0
< 0
> 0
> 0
( x1i
– x1
)( x2i
– x2
) ( x1i
– x1
)( x2i
– x2
)
( x1i
– x1
)( x2i
– x2
)( x1i
– x1
)( x2i
– x2
)
共分散の正負＝相関の正負

14
s12 = s21 =
1
n
n
i=1
(x1i ? x1)(x2i ? x2)
　　
x1, x2の共分散
++
+ + +
+
+
x1
x2
x2
x1
< 0
< 0
> 0
> 0
( x1i
– x1
)( x2i
– x2
) ( x1i
– x1
)( x2i
– x2
)
( x1i
– x1
)( x2i
– x2
)( x1i
– x1
)( x2i
– x2
)
共分散の正負＝相関の正負
（共分散を x1, x2 の標準偏差で
割ったものが相関係数）

さて，zの分散V(z)は
15
(3)式
V (z) =
1
n
n
i=1
(zi ? z)2
i 1
= a2
1s11 + 2a1a2s12 + a2
2s22

15
(3)式
V(z)が最大になるa1, a2を求める
V (z) =
1
n
n
i=1
(zi ? z)2
i 1
= a2
1s11 + 2a1a2s12 + a2
2s22

15
(3)式
V (z) =
1
n
n
i=1
(zi ? z)2
i 1
= a2
1s11 + 2a1a2s12 + a2
2s22
xからzへの変換は「回転」（伸び縮みしない）→

15
(3)式
V (z) =
1
n
n
i=1
(zi ? z)2
i 1
= a2
1s11 + 2a1a2s12 + a2
2s22
xからzへの変換は「回転」（伸び縮みしない）→ a2
1 + a2
2 = 1

固有値問題
16
が得られる（付録1）
a1s11 + a2s12 = a1λ
a2s22 + a1s12 = a2λ
s11 s12
s12 s22
a1
a2
= λ
a1
a2
行列で書くと
分散共分散行列
固有ベクトル固有値
固有値?固有ベクトルを求める問題を
「固有値問題」という（解き方は略）
定数λを使って

第１主成分
17
固有ベクトル
( )
a1
a2
新し画
固有値 λ
が２組得られて，しかも

第１主成分
17
固有ベクトル
V (z) = λ となる
（付録2）
( )
a1
a2
新し画
固有値 λ

第１主成分
17
固有ベクトル
V (z) = λ となる
（付録2）
( )
a1
a2
新し画
固有値 λ
第１主成分という
大きい方の λ(λ(1)とする）に対応する固有ベクトル
求めた z（ z(1) とする）が，求めたかった z
a1(1)
a2(1)
を使って

主成分分析と直交変换

このときz(1)とz(2)は無相関
19
++
+
+ +
+
+
x1
x2
画素１の値
画素２の値
x1, x2を回転して，新たにz(1) , z(2) とする

19
+
+ +
+
+ + +
x1
x2
画
素
１の
値
画
素
２
の
値
z(2)
z(1)

19
+
+ +
+
+ + +
x1
x2
画
素
１の
値
画
素
２
の
値
z(2)
z(1)
z(1) , z(2) は無相関。
なぜなら

相関がないときは
20
共分散＝０
先ほど求めた
z(1) , z(2) はこうなっている
→本当？
z1
z2
++
+
+
+
+
+z2
z1
相関がない→ の正負がつりあう( z1i – z1)( z2i – z2)

主成分分析と分散共分散行列
21
固有値のうち，大きい方を λ(1)，小さい方を λ(2)
対応する固有ベクトル a1(1)
a2(1)
　　　
a1(2)
a2(2)

主成分分析と分散共分散行列
21
固有値のうち，大きい方を λ(1)，小さい方を λ(2)
対応する固有ベクトル a1(1)
a2(1)
　　　
a1(2)
a2(2)
　　　
これらは
s11 s12
s21 s22
a1(1)
a2(1)
= λ(1)
a1(1)
a2(1)
s11 s12
s21 s22
a1(2)
a2(2)
= λ(2)
a1(2)
a2(2) をみたす

分散共分散行列の対角化
22
まとめると
s11 s12
s21 s22
a1(1) a1(2)
a2(1) a2(2)
=
a1(1) a1(2)
a2(1) a2(2)
λ(1) 0
0 λ(2)

22
まとめると
s11 s12
s21 s22
a1(1) a1(2)
a2(1) a2(2)
=
a1(1) a1(2)
a2(1) a2(2)
λ(1) 0
0 λ(2)
S P
P Λ

22
まとめると
つまり
s11 s12
s21 s22
a1(1) a1(2)
a2(1) a2(2)
=
a1(1) a1(2)
a2(1) a2(2)
λ(1) 0
0 λ(2)
S
SP = PΛ
すなわち
（分散共分散行列の）対角化という
Λ = P?1
SP, S = PΛP?1
P
P Λ

対称行列の対角化
23
分散共分散行列 S は
対称行列
直交行列の逆行列は転置行列（逆回転）
すなわち
s11 s12
s21 s22
s12 = s21
共分散
対称行列の固有ベクトルは直交する（詳細略）
Pは直交行列 a1(1) a1(2)
a2(1) a2(2)
S = PΛP ,

対角化の意味
24
分散共分散行列は
P′で変換し
そこでは分散共分散行列が Λ で
P で戻る
λ(1) 0
0 λ(2)
Λ =
あの世では共分散が０
→相関がない
「この世」「あの世」
S = PΛP ,

P′で変換された「あの世」とは？
25
だから
z(1) = a1(1) a2(1)
x1
x2
z(2) = a1(2) a2(2)
x1
x2
z(1)
z(2)
=
a1(1) a2(1)
a1(2) a2(2)
x1
x2
直交行列で変換するから
直交変換という

25
だから
z(1) = a1(1) a2(1)
x1
x2
z(2) = a1(2) a2(2)
x1
x2
z(1)
z(2)
=
a1(1) a2(1)
a1(2) a2(2)
x1
x2
これが P′

25
だから
つまり， x から z に変換すると，
z(1) とz(2) の共分散が０→相関がない
z(1) = a1(1) a2(1)
x1
x2
z(2) = a1(2) a2(2)
x1
x2
z(1)
z(2)
=
a1(1) a2(1)
a1(2) a2(2)
x1
x2
これが P′

たしかにz(1)とz(2)は無相関
26
++
+ + +
+
+
x1
x2
画素１の値
画素２の値

26
+
+ +
+
+ + +
x1
x2
画
素
１の
値
画
素
２
の
値
z(2)
z(1)

26
+
+ +
+
+ + +
x1
x2
画
素
１の
値
画
素
２
の
値
z(2)
z(1)
このときたしかに
z(1) , z(2) は無相関

画素がp個あっても同じ
27
?
?
?
?
?
?
z(1)
z(2)
...
z(p)
?
?
?
?
?
?
=
?
?
?
?
?
?
a1(1) a2(1) · · · ap(1)
a1(2) a2(2) · · · ap(2)
...
...
a1(p) a2(p) · · · ap(p)
?
?
?
?
?
?
?
?
?
?
?
?
x1
x2
...
xp
?
?
?
?
?
?
= P
?
?
?
?
?
?
x1
x2
...
xp
?
?
?
?
?
?
　
xからzへの，P′による直交変換
Pは固有値問題の解
?
?
?
?
?
?
s11 s12 · · · s1p
s12 s22 · · · s2p
...
...
sp1 sp2 · · · spp
?
?
?
?
?
?
?
?
?
?
?
?
a1
a2
...
ap
?
?
?
?
?
?
= λ
?
?
?
?
?
?
a1
a2
...
ap
?
?
?
?
?
?
S
?
?
?
?
?
?
a1(1) a1(2) · · · a1(p)
a2(1) a2(2) · · · a2(p)
...
...
ap(1) ap(2) · · · ap(p)
?
?
?
?
?
?
=
?
?
?
?
?
?
a1(1) a1(2) · · · a1(p)
a2(1) a2(2) · · · a2(p)
...
...
ap(1) ap(2) · · · ap(p)
?
?
?
?
?
?
?
?
?
?
?
?
λ(1) 0
λ(2)
...
0 λ(p)
?
?
?
?
?
?

27
?
?
?
?
?
?
z(1)
z(2)
...
z(p)
?
?
?
?
?
?
=
?
?
?
?
?
?
a1(1) a2(1) · · · ap(1)
a1(2) a2(2) · · · ap(2)
...
...
a1(p) a2(p) · · · ap(p)
?
?
?
?
?
?
?
?
?
?
?
?
x1
x2
...
xp
?
?
?
?
?
?
= P
?
?
?
?
?
?
x1
x2
...
xp
?
?
?
?
?
?
　
?
?
?
?
?
?
s11 s12 · · · s1p
s12 s22 · · · s2p
...
...
?
?
?
?
?
?
?
?
?
?
?
?
a1
a2
...
ap
?
?
?
?
?
?
= λ
?
?
?
?
?
?
a1
a2
...
ap
?
?
?
?
?
?
S
?
?
?
?
?
?
a1(1) a1(2) · · · a1(p)
a2(1) a2(2) · · · a2(p)
...
...
ap(1) ap(2) · · · ap(p)
?
?
?
?
?
?
=
?
?
?
?
?
?
a1(1) a1(2) · · · a1(p)
a2(1) a2(2) · · · a2(p)
...
...
ap(1) ap(2) · · · ap(p)
?
?
?
?
?
?
?
?
?
?
?
?
λ(1) 0
λ(2)
...
0 λ(p)
?
?
?
?
?
?
分散共分散行列S

27
?
?
?
?
?
?
z(1)
z(2)
...
z(p)
?
?
?
?
?
?
=
?
?
?
?
?
?
a1(1) a2(1) · · · ap(1)
a1(2) a2(2) · · · ap(2)
...
...
a1(p) a2(p) · · · ap(p)
?
?
?
?
?
?
?
?
?
?
?
?
x1
x2
...
xp
?
?
?
?
?
?
= P
?
?
?
?
?
?
x1
x2
...
xp
?
?
?
?
?
?
　
?
?
?
?
?
?
s11 s12 · · · s1p
s12 s22 · · · s2p
...
...
?
?
?
?
?
?
?
?
?
?
?
?
a1
a2
...
ap
?
?
?
?
?
?
= λ
?
?
?
?
?
?
a1
a2
...
ap
?
?
?
?
?
?
S
?
?
?
?
?
?
a1(1) a1(2) · · · a1(p)
a2(1) a2(2) · · · a2(p)
...
...
ap(1) ap(2) · · · ap(p)
?
?
?
?
?
?
=
?
?
?
?
?
?
a1(1) a1(2) · · · a1(p)
a2(1) a2(2) · · · a2(p)
...
...
ap(1) ap(2) · · · ap(p)
?
?
?
?
?
?
?
?
?
?
?
?
λ(1) 0
λ(2)
...
0 λ(p)
?
?
?
?
?
?
分散共分散行列S
P P Λ

Karhunen-Loève変換（KL変換）
28
画像を主成分に変換してから伝送する
p画素の画像
1
p
第１～第p / 2
主成分だけを
伝達する
主成分に
変換
もとの画
素に戻す
p画素の画像
（情報の損失が最小）
もどすときは，データ量が半分でも
情報の損失は最小

Karhunen-Loève変換（KL変換）
29
もどすときは
伝送されて来なかった主成分は，
平均に置き換えておく
?
?
?
?
?
?
x1
x2
...
xp
?
?
?
?
?
?
(P )?1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
z(1)
z(2)
...
z(p/2)
z(p/2+1)
...
z(p)
?
?
?
?
?
?
?
?
?
?
?
?
?
?
= P
?
?
?
?
?
?
?
?
?
?
?
?
?
?
z(1)
z(2)
...
z(p/2)
z(p/2+1)
...
z(p)
?
?
?
?
?
?
?
?
?
?
?
?
?
?

KL変換の大問題
30
主成分を求めるには，分散共分散行列が必要
分散共分散行列を求めるには，
「いまから取り扱うすべての画像」が
事前にわかっていないといけない
そんなことは不可能。

続きは
31
分散共分散行列がわからないから，
どういう直交変換をしたらいいかもわからない
画像をベクトルではなく，２次元のまま行列で表して
「行列の直交変換」を考え，
直交変換のようすが目に見えるようにする。
経験的にうまくいく直交変換を行う
適切な直交変換を選ぶ（実は結局フーリエ変換とその変形）

狠狠撸

2020年度秋学期　画像情報処理　第7回　主成分分析とKarhunen-Loève変換 (2020. 11. 6)

Recommended

More Related Content

What's hot (20)

Similar to 2020年度秋学期　画像情報処理　第7回　主成分分析とKarhunen-Loève変換 (2020. 11. 6) (20)

More from Akira Asano (20)

Recently uploaded (6)

2020年度秋学期　画像情報処理　第7回　主成分分析とKarhunen-Loève変換 (2020. 11. 6)

狠狠撸

2020年度秋学期 画像情報処理 第7回 主成分分析とKarhunen-Loève変換 (2020. 11. 6)

Recommended

More Related Content

What's hot (20)

Similar to 2020年度秋学期 画像情報処理 第7回 主成分分析とKarhunen-Loève変換 (2020. 11. 6) (20)

More from Akira Asano (20)

Recently uploaded (6)

2020年度秋学期 画像情報処理 第7回 主成分分析とKarhunen-Loève変換 (2020. 11. 6)

2020年度秋学期　画像情報処理　第7回　主成分分析とKarhunen-Loève変換 (2020. 11. 6)

Similar to 2020年度秋学期　画像情報処理　第7回　主成分分析とKarhunen-Loève変換 (2020. 11. 6) (20)

2020年度秋学期　画像情報処理　第7回　主成分分析とKarhunen-Loève変換 (2020. 11. 6)