Document

光学勉強会
1
All images are compressed.
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
宮崎大輔（池内研）
光学勉強会
2
固有空間法による画像認識
宮崎大輔（池内研）
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
宮崎大輔（池内研）
本日の内容
• 松山隆司，久野義徳，井宮淳
「コンピュータビジョン技術評論と将来展望」
第14章固有空間法による画像認識
宮崎大輔（池内研）
光学勉強会
3
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
光学勉強会
4
前提知識
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
宮崎大輔（池内研）
予備知識：主成分分析
• 主成分分析(PCA: Principal Component Analysis)
• 別名：KL展開(Karhunen-Loeve展開)
• データを少ない成分であらわすこと
– 100次元空間のデータを10次元空間のデータで表したい
• これを使って
– データ圧縮
• 少ない成分で表せれば保存するデータが少なくて済む
– 認識
• 認識に不要なデータを除いて、認識に必要なデータだけ
を使って認識をしたほうが認識性能がよくなる
宮崎大輔（池内研）
光学勉強会
5
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
例１
病気かどうか
病気である
病気ではない
熱の有無
熱がない熱がある
２次元のデータ
１次元で表現したほうがデータ量が少なくなる
熱があって病気である、か、熱がなくて病気ではない
宮崎大輔（池内研）
光学勉強会
6
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
例２
e2
y
(x,y)=(8,6)
e1
(e1,e2)=(4,-1)
x
50%の圧縮
宮崎大輔（池内研）
光学勉強会
7
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
主成分分析の実装
分散 s (1次元)
共分散行列 A (d次元)
1 n
T
A
X
X

i i
X: データ (d次元)
n  1 i 1
データはn個
または n
Ax  x
宮崎大輔（池内研）
光学勉強会
8
λ: 固有値
x: 固有ベクトル
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
実際の計算の例
2次元の点が2つ
共分散行列
固有値問題：
1, 2
1,  2
1  1 2   1 2   2 4 
  
  

A

2  1  2 4   2 4   4 8 
Ax  x
4  2
2  
    10  0
det( A  I)  det
 4 8
k 
 2 4  x 
 x
  8 4  x   0 
 

   10 

    
 2k 
 4 8  y 
 y
 4  2  y   0 
1
1 1
1   2
 
 
   5x1
x1 
x2 
5  2
5 1 
 2
 5 , 5 
データ圧縮： 1,2,1,2
宮崎大輔（池内研）
光学勉強会
9
  10, 0
1 1
 
5  2
 1 
    5x1
  2
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
分散と共分散行列
• 共分散行列って何？その前に分散って何？
• １次元の正規分布（ガウス分布）は、平均と分散（スカ
ラー値）で表される
 x   2 
1

exp 
2

2
s
2 s


宮崎大輔（池内研）
光学勉強会
10
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
共分散行列とは？
• ２次元のガウス分布は、２次元の平均と、２×２行列
の分散共分散行列Sで表される
1
 2 
m
 1 0

S  
 0 1
宮崎大輔（池内研）
光学勉強会
 1

exp  x  μT S 1 x  μ
 2

S
 2 0

S  
 0 1
11
 2 1

S  
 1 2
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有値と固有ベクトルとは？
• 固有値の一つは 1  10
• その固有値に対する固有ベクトル
は
1 1
• 以下を満たすλを固有値、xを固有
ベクトルと言う
Ax  x
x1 
• このとき
Ax1  1x1
が成り立つことは代入すればすぐ
確かめられる
• もう一つは 2  0
• その固有値に対する固有ベクトル
は
1   2
• 先程の例にあるように
x2 
 2 4

A  
4 8
• このとき
 
5 1 
Ax 2  2 x2
が成り立つことは代入すればすぐ
確かめられる
が与えられたとき
宮崎大輔（池内研）
光学勉強会
 
5  2
12
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
正規直交基底とは？
• あるN次元空間の「軸」たちのこと
• いわゆる、ユークリッド空間では、x軸・y軸・z軸という
正規直交基底で空間が張られている
– 正規直交基底は(1 0 0),(0 1 0), (0 0 1)という３つのベクト
ルとなる
• 例：(0.7 0.7)(-0.7 0.7)という２つのベクトルも２次元平
面での正規直交基底である
• 正規直交基底は、すべてのベクトルが直交して（９
０°で）単位ベクトルである
• N個の正規直交基底で張られるN次元空間では、N次
元空間の中のすべての点を表現することができる
宮崎大輔（池内研）
光学勉強会
13
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
行列の言葉の定義
• 以下のとき，つまりAT=A-1の
とき，その行列は直交という
• 以下のとき，その行列は対
称という
1
0
1
1
0
宮崎大輔（池内研）
光学勉強会
14
1
1
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
行列の対角化
• 行列Aの相似変換はある変換行列Zにより以下のよう
に変換されることをいう
行列の固有値は不変
• 固有値を求めるには
のような相似変換でAを対角行列へ変換する
すると固有ベクトルは
XRは固有ベクトルを列にして作られた行列
宮崎大輔（池内研）
光学勉強会
15
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
実対称行列のJacobi法
•
Jacobi回転
• a’pq=0となる回転角φは
tan 
•
sgn( )
|  |   2 1

aqq  a pp
2a pq
• 最終的に対角行列Dが求ま
る（対角要素が固有値）
この回転により非対角要素を0にしていく
これでAを変換:
※Aは対称
Vは
Piは個々のJacobi回転行列
で，Vの列は固有ベクトル
• 左上から右下に消していく
P12,P13,…,P1n,P23,P24,…
宮崎大輔（池内研）
光学勉強会
16
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
QR法
• Jacobi法ではなくQR法で実装するのが普通
– 説明は省略します
• Jacobi法もQR法も対称行列
– 非対称行列に対する方法の説明は省略
• 固有値が求まっていて，小数の固有ベクトルを求めた
い場合は逆反復法を使う
– 説明は省略します
• 正方行列でないときや，行列が特異なときは，特異値
分解を使う
– 説明は省略します
宮崎大輔（池内研）
光学勉強会
17
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
主成分分析の実装
• Numerical Recipes in C(技術評論社)という本に，
Jacobi法，QR法，逆反復法，特異値分解，のC言語
によるプログラムが掲載されています
• C言語による最新アルゴリズム事典(技術評論社)とい
う本にも，累乗法とJacobi法とQR法のC言語による
プログラムが掲載されています
– 累乗法は，絶対値の大きい固有値を数個求めたいときに使
う
– この本には主成分分析のプログラム(?)も掲載されています
（固有値・固有ベクトルの計算にはQR法を使っています）
宮崎大輔（池内研）
光学勉強会
18
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
寄与率
• 主成分分析の利点は、データを少ない次元（主成分）で表せること
• 固有ベクトルのことを主成分と言い、固有値の大きい順に、第１主成分、第
２主成分、・・・と呼ぶ
• 固有ベクトルは正規直交基底なので、主成分で張られる空間で、データの
すべてを表現できる
• しかし、そのデータは若い主成分のほうがよく表していて、若い主成分だけ
を使ってデータを近似的に表しても結構うまく表現できる
y  a1u1  a2u2   ak uk
• ここで、固有値の大きい物からk個の主成分だけを使った場合、固有値を
使って累積寄与率というものが計算できる
 k 
  j 
 j 1 


 d 
  j 
 j 1 


• 簡単に言うと、どれだけそのデータを表せるか、というもの
宮崎大輔（池内研）
光学勉強会
19
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
近似
• パターンXを以下で表現できる→KL展開
N
X  Wn  n
n1
• 固有ベクトルを正規化したもの
 ,, 
1
• これをK項（K≦N）までで打ち切り
N
K
X  Wk  k
k 1
• 固有値λkを大きい順に並べて
1  2    N  1
• λkに対応する固有ベクトルをμkとしたとき、上の打ち切ったXは
最も良い近似を与える
宮崎大輔（池内研）
光学勉強会
20
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
近似の例
N=10の学習パターン
□標準基底
○固有ベクトル
宮崎大輔（池内研）
光学勉強会
21
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有テクスチャ法
カラー画像
幾何モデル
固有空間
合成
圧縮
宮崎大輔（池内研）
光学勉強会
仮想物体
22
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有テクスチャ法の原理
k個の固有テクスチャ
係数
合成画像
aM,0×
+ aM,1×
+ aM,3×
=
線形和
宮崎大輔（池内研）
光学勉強会
23
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
クラス分類
•
•
•
•
物体がどのクラスに属するか分類すること
例：病気かどうか（体温、心拍数）
例：リンゴ、バナナ、メロン（色）
例：文字認識（画像のピクセルを並べてベクトル化）
色度・赤
バナナ
その分布を学習する
リンゴ
メロン
未知の入力ベクトルが
どの分布に近いかを調べる
その入力がどのクラスに
分類されるかが分かる
色度・緑
宮崎大輔（池内研）
光学勉強会
特徴ベクトルを決める
この例の場合は色ベクトル
24
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
テンプレートマッチング
この文字は何？
木
学習データと照合
本
太
林
歪
木
大
禾
禿
ホ
不
最も近い物を選ぶ
木
宮崎大輔（池内研）
光学勉強会
25
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
光学勉強会
26
理論
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
宮崎大輔（池内研）
主成分分析
•
•
•
•
•
•
d次元特徴ベクトル x  x1, x2 ,, xd 
平均 m  Ex
平均を引いた特徴ベクトル x  x  m
共分散行列 S  E xxT
T
 
固有値問題を解く Su  u
k個の固有ベクトルによって張られる部分空間
u1, u2 ,, uk
• 特徴ベクトルをその部分空間に射影
y  u1, u2 ,, uk  x
T
宮崎大輔（池内研）
光学勉強会
27
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
主成分分析
• d次元特徴ベクトルをより低次元のk次元特徴ベクトルで表せる
– パターン認識で，計算量を減らせる
– 重要な特徴のみを取り出すので，認識性能が上がる
• 重要な特徴のみを取り出すので，非常に効率的な画像圧縮が可能
– 実用的にはほとんど利用されていない
• 固有ベクトルの計算量が多い
• 固有ベクトルも送信する必要がある
– JPEGやMPEGなどの離散コサイン変換では，コサイン関数という基底ベクトル
が分かっているので，送信する必要がない
• 共分散行列 S  Ex  mx  mT  と自己相関行列 S  ExxT の２種類がある
– 平均を引くかどうかの違い
– どちらがいいかは応用分野による
• コンピュータビジョンでは基本的に共分散行列，と思いこんでおけばいい
宮崎大輔（池内研）
光学勉強会
28
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
判別分析
• パターン認識
– クラス内分散が小さい
– クラス間分散が大きい
• Fisherの判別分析法（2クラスの問題）
• 重判別分析法（多クラスの問題）
宮崎大輔（池内研）
光学勉強会
29
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
重判別分析法
• 簡単のため，各クラスの出現確率は同じだとする
– 例：リンゴ・バナナ・メロンの３つのクラスに分類したいとする．
このとき，リンゴとバナナとメロンが出現する確率が全て1/3
であるような簡単な場合のみを考える
宮崎大輔（池内研）
光学勉強会
30
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
クラス内分散
• クラス内分散行列

 Ex
 Ex
T 
T



m
x

m
バナナ
バナナ
バナナ
バナナ 
T




m
x

m
メロン
メロン
メロン
メロン
SW  E xリンゴ  mリンゴ xリンゴ  mリンゴ
リンゴ
バナナ
メロン
x: データ
m: 平均
宮崎大輔（池内研）
光学勉強会
31
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
クラス間分散
• クラス間分散行列
S B  mリンゴ  m全体 mリンゴ  m全体 T
 mバナナ  m全体 mバナナ  m全体 T
 mメロン  m全体 mメロン  m全体 T
リンゴ
バナナ
メロン
m: 平均
宮崎大輔（池内研）
光学勉強会
32
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
次元圧縮
• （次のスライドで説明しますが）固有値問題
SBu  SW u
を解けばOK
• で，k個の大きな固有値に対応する固有ベクトルから
なる行列でd次元特徴ベクトルxをk次元特徴ベクトル
yに次元圧縮する
T
y  u1, u2 ,, uk  x
• この特徴ベクトルでパターン認識をする
宮崎大輔（池内研）
光学勉強会
33
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
重判別分析法の固有値問題
SBu  SW u
っていうのは，つまり
簡単のため
こんな分布で考えてみよう
SBu  u
S S u  u
1
W B
最大固有値に対する固有ベクトル
を緑の矢印で表す
SW u  u
SW1u  u
SW1SBu  u
この次元で見るのが最も分類しやすい
宮崎大輔（池内研）
光学勉強会
34
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
部分空間法：CLAFIC法
•
例として，128x128の画像を特徴ベクトルとして分類を行いたいとする
– 16384次元の特徴ベクトルのデータがあり，例えば72枚の特徴ベクトルで主成分分析を
行ったとする
– 固有値の大きい上位約100個の固有ベクトルを取ってくれば次元圧縮が実現される
•
さて，今，未知の画像を３つのクラス，「リンゴ」「バナナ」「メロン」に分類したいとしよ
う
– まず，「リンゴ」「バナナ」「メロン」だと分かっている画像だけを集めて，それぞれ固有値が
しきい値より大きい固有ベクトルだけを取ると，それぞれ87個，123個，96個だったとしよ
う
– どんなデータも16384次元空間上の点で表すことができるけど，「リンゴ」のデータはここ
で計算されて出てきた87次元空間で近似的に表現できる（次元圧縮）
• この87次元空間は16384次元空間に含まれるので，「部分空間」
•
•
•
で，未知の画像が与えられたとき，その16384次元ベクトルが「リンゴ」の87次元空
間でうまく表現できるか，「バナナ」「メロン」の123次元空間・96次元空間でうまく表
現できるか，をチェックすれば，その未知の画像が「リンゴ」「バナナ」「メロン」のどれ
に分類すればいいかが分かる
これが部分空間法のうちのCLAFIC法(CLAss-Featuring Information
Compression)
・・・え？よく分からない？・・・では次のスライドでもっと分かりやすく説明します
宮崎大輔（池内研）
光学勉強会
35
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
部分空間法：CLAFIC法
•
•
•
簡単のため，特徴ベクトルを3次元とする（RGB色空
間ならぬ赤・黄色・緑空間でも想像してみてくれ）
3つのクラスに分類するとしてそれぞれのクラスをwリン
ゴ，wバナナ，wメロン，とする
それぞれの学習データに対して主成分分析を行い，
固有値があるしきい値のものだけを取り出した所，そ
れぞれp(リンゴ)=1個，p(バナナ)=1個，p(メロン)=1個の固有
ベクトルで大体表現できることが分かったとしよう
メロン
– 3次元空間を1次元空間で表現できる（次元圧縮）
– 3次元空間の中の1次元部分空間，つまり直線で表現で
きる
•
それぞれの固有ベクトルが以下のように計算されたと
する
u1(リンゴ )
1
 0
 
 
(バナナ)
  0  u1
 1
 0
 0
 
 
u1(メロン
)
 0
 
  0
1
 
バナナ
リンゴ
注：ここではただの例なので，簡単のため３つは直交
してるが，通常は直交するとは限らない
宮崎大輔（池内研）
光学勉強会
36
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
部分空間法：CLAFIC法
u(メロン)
x=(8,2,5)
この例の場合では
u(バナナ)
u(リンゴ)

との類似度  x u
との類似度  x u
 =8
 =2
 =5
T
(リンゴ ) 2
2
未知の3次元特徴ベクトルxとwバナナ
T
(バナナ) 2
2
未知の3次元特徴ベクトルxとwメロン
T
(メロン ) 2
2
未知の3次元特徴ベクトルxとwリンゴとの類似度  x u
というわけで，この場合，未知のデータxはwリンゴと分類される
宮崎大輔（池内研）
光学勉強会
37
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有ベクトルの例
学
習
デ
ー
タ
固
有
ベ
ク
ト
ル
宮崎大輔（池内研）
光学勉強会
38
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
部分空間法：複合類似度法
•
CLAFIC法で，固有ベクトルに重みを付けて類似
度を計算する
– 重みとしては固有値を使う
•
今までの例では，p(リンゴ)=1個，p(バナナ)=1個，p(メロ
ン)=1個の固有ベクトルが主成分分析の結果とし
て出てくるとした
– ここで，p(リンゴ)=2個の場合を考える
– それぞれの固有ベクトルが右のようになったとする
– リンゴがまだ熟していない物があり，若干緑がかっ
たリンゴもある，ということだと思って欲しい
•
CLAFIC法だと，緑色の物はメロンなのかリンゴ
なのか区別がつかない
– u1(リンゴ)=赤，u2(リンゴ)=緑，であり，固有ベクトルu1に
対する固有値は1.0で，固有ベクトルu2に対する固
有値が0.1だとする
– u1(メロン)=緑，であり，固有値が1.0だとする
– 固有値で重みを付けて分類すれば，緑色の物はリ
ンゴである確率（類似度）よりもメロンである確率
（類似度）のほうが高い，という分類結果が出る
宮崎大輔（池内研）
光学勉強会
39
1
 
(リンゴ )
u1
  0
 0
 
 0
 
u1(バナナ)   1 
 0
 
 0
 
(リンゴ )
u2
  0
1
 
 0
 
u1(メロン )   0 
1
 
u1(メロン)
u2
(リンゴ)
u1(バナナ)
u1(リンゴ)
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
部分空間法：混合類似度法
•
今まで：未知の特徴ベクトルxがクラス「木」
かクラス「本」かに分類されるかどうかを知
るためには，「xと木の類似度」と「xと本の
類似度」を比較し，類似度が大きいほうを
選ぶ
–
–
•
•
固有ベクトル=u1(1)
•
つまり
•
よって，クラス1の類似度は
•
クラス2=「本」の固有ベクトルの数をp(2)=1
個
–
•
•
また k
と
の似ている度合い
x
と
の似ている度合い
つまり
x

  x v 
2
T
が
クラス1「木」に分類されるためには
固有ベクトル=u1(2)
クラス1の類似度は xT u1(1)
ここで v(1)  k  u(1)
v(1)=
x
以下，具体例（数式は簡略化されてる）
クラス1=「木」の固有ベクトルの数をp(1)=1
個
–
•
この２つの類似度にはあまり差がない
人間が木と本を区別するとき，普通，横線
があるかないかで区別する
•
x
が
にできるだけ似ていて
x
に
ができるだけ存在しない
(1) 2
1
というのが条件
※上記の数式は実際には係数などがかかっている
宮崎大輔（池内研）
光学勉強会
40
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
部分空間法：直交部分空間法
部分空間が直交していないと
部分空間が直交していると
メロン
リンゴ
バナナ
メロン
リンゴ
未知の特徴ベクトルxは
リンゴに近いけどメロンやバナナにも近いなぁ…
未知の特徴ベクトルxは
メロンやバナナと比べて明らかにリンゴに近いぞ！
分類しづらい
分類しやすい
複数のクラス分類では難しいので
以降のスライドでは2クラス分類について説明する
宮崎大輔（池内研）
光学勉強会
バナナ
41
直交部分空間法
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有値・固有ベクトルを求める方法を思い出して欲しい
• 実対称行列Sを直交行列Pで対角化して得られた対
角行列の各要素が固有値で，Pの列が固有ベクトル
Λ  PT SP
λ1
0
λ2
0
λn
PT P  I
e1
e2
e1 e2
en
en
相関行列や共分散行列は実対称行列（定義より明らか）
対称行列とは・・・要素(i,j)と要素(j,i)が同じ
対角行列とは・・・対角成分以外が0の行列
直交行列とは・・・逆行列が転置行列になる行列
宮崎大輔（池内研）
光学勉強会
42
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
数学的な予備知識
1/d1
1/d2
①
0
0
d1
1/dn
0
0
d1
1 d1
1 d2
②
0
1
0
0
dn
d2
0
0
dn
0
1
1
1 d1
1 d2
0
1
0
1
0
1 dn
0
1
A  B  C で，AとBが対角行列なら，Cも対角行列
③
a1
④
1 dn
d2
a2
0
宮崎大輔（池内研）
光学勉強会
0
an
b1
b2
0
0
bn
1
1
0
0
を書き直すと，ak+bk=1
1
43
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
部分空間法：直交部分空間法
クラス1の相関行列 S1
クラス2の相関行列 S2
今まではそれぞれの相関行列を対角化したが
２つの相関行列を足した物を対角化するとどうなるか？
S0  S1  S2 も実対称行列なので直交行列で対角化可能
~T ~
~
P S0 P   ここで P  P1 2 を使うと PT S0 P  I
T
T
つまり P S1P  P S2 P  I
※たぶんPSPは対角化されてるのかもしれないが僕は数学に詳しくないのでよくわからないので対角化されていないとして話を進める
宮崎大輔（池内研）
光学勉強会
44
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
部分空間法：直交部分空間法
前のスライドで PT S1P  PT S2 P  I が得られた
T
T
P
S
P

I

P
S2 P を Q で対角化しよう
ここで
1
T
Q
Q  I より
Q P S1PQ  Q Q  Q P S2 PQ ここで
また，見づらいので R  PQ とおくと
RT S1R  RT S2 R  I
RT S1R が対角化されていて
単位行列 I は対角行列でもあるので RT S2 R も対角行列
つまり S1 と S2 は R により対角化可能
R の列ベクトルが固有ベクトル
T
T
T
T
T
すなわち，２つのクラスで
同じ固有ベクトルを持たせることができたわけだ
宮崎大輔（池内研）
光学勉強会
45
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
部分空間法：直交部分空間法
前のスライドで RT S1R  RT S2 R  I が得られた
RT S1R も RT S2 R も，固有値が並んだ対角行列
クラス1とクラス2の固有値をそれぞれ
(k1) (k2) とすると
RT S1R  RT S2 R  I は (k1)  (k2)  1 と表現できる
つまり，一方のクラスの最大固有値に対する固有ベクトルは，
もう一方のクラスでは最小固有値に対する固有ベクトルになっている
クラス1とクラス2の固有ベクトルは同じ
固有ベクトルは全て直交している
クラス1の最大固有値に対する固有ベクトルと，
クラス2の最大固有値に対する固有ベクトルは，直交している
これが直交部分空間法
宮崎大輔（池内研）
光学勉強会
46
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
光学勉強会
47
応用
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
宮崎大輔（池内研）
固有顔（アイゲンフェース）
•
•
•
•
画像サイズ64×64画素を特徴ベクトル（4096次元）とする
画像60枚から共分散行列4096×4096行列を作る
主成分分析で固有ベクトルを計算
固有値の大きい固有ベクトルほど顔の特徴をよく表しており，
固有値の小さい固有ベクトルは認識が悪い
– 固有値の大きい固有ベクトル100個だけを使い，100次元空間で未知
の特徴ベクトルと学習パターンとの距離により識別する
宮崎大輔（池内研）
光学勉強会
48
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
フーリエ係数を利用した固有顔
• 元々の固有顔は，特徴ベクトルとして画素そのものを
使っていた
• 画像をフーリエ変換して，そのパワーの値を特徴ベク
トルとする方法
• 画像の位置がずれていてもうまく認識できる
宮崎大輔（池内研）
光学勉強会
49
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
図では３次元だが実際は多次元
パラメトリック固有空間法
• 物体や光源を回転させ
た画像を主成分分析す
る
• 回転角による違いは固
有空間で多様体
（manifold,曲面）として
現れる
• 入力画像が与えられた
とき，多様体に最も近
い点の角度を調べれ
ば，物体の向きや光源
の向きを推定すること
ができる
宮崎大輔（池内研）
光学勉強会
50
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
動画像認識
• 歩行のシルエット動画像
を主成分分析
• 固有空間上の軌跡の形
を比較すれば，その歩き
方（歩容,gait）の違いに
より，その人物を特定で
きる
宮崎大輔（池内研）
光学勉強会
51
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有空間法の長所と短所
• 固有空間法はテンプレートマッチングの拡張
– テンプレートマッチングの長所と短所をそのまま受け継いで
いる
• テンプレートマッチング
– 画像の差を利用して２次元図形の検出
• 幾何学的特徴に基づく手法
– 物体の回転や視点に不変な特徴量を利用して回転などに
対してロバストな照合を行う
– ３次元情報を利用して３次元モデルと照合する
宮崎大輔（池内研）
光学勉強会
52
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有空間法の長所と短所
固有空間はグローバル特徴
• 幾何学的な特徴を用いる手法
– ローカルな特徴
• 固有空間法
– 画像全体のグローバルな情報
– 雑音や物体の小さな欠損があっても，画像全体で見ている
ので，画像全体で平均化され，ロバスト
– しかし，物体がほとんど隠れていたり，複雑な背景があった
り，には弱い
宮崎大輔（池内研）
光学勉強会
53
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有空間法の長所と短所
固有空間法は視点の移動にはやや不得意
• ３次元の情報を使って照合
– 物体の回転・移動にロバスト
– ３次元の情報を取り出すのは難しい
• 固有空間法
– ２次元モデルなので物体の回転・移動は不得意
• パラメトリック固有空間法で解決
– あらかじめ多数の画像を用意しないといけない
宮崎大輔（池内研）
光学勉強会
54
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有空間法の長所と短所
固有空間法は大量データからの学習が必要
• 幾何学的な手法
– ３次元モデルが一つあればいい
– 小数の画像列から幾何学的不変特徴を求めればいい
• 固有空間法
– 様々な向きを向いた物体の画像を学習させる
• データが膨大
– 特に学習段階が大変
宮崎大輔（池内研）
光学勉強会
55
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有空間法の長所と短所
固有空間法はブラックボックス
• 物体認識は困難→部分問題に分割
– エッジ抽出，セグメンテーション，ステレオ，領域分割，２値
化
– 全体の目標がなかなか達成できない
• 固有空間法は細かい部分問題に分けないブラック
ボックス
– 処理の内部構造が不明
• エラーが発生したときの原因を解析・説明しにくい
– 例えば，固有ベクトルの物理的な意味
宮崎大輔（池内研）
光学勉強会
56
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有空間法の長所と短所
固有空間法を連続性を仮定
• パラメトリック固有空間法
– 固有空間上での点が連続に変化する，という仮定
• 不連続な要素（スペキュラーなど）があると問題があ
る
宮崎大輔（池内研）
光学勉強会
57
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有空間法の長所と短所
固有空間法は単純処理の繰り返し
• 演算の回数は非常に多いが，一つ一つの演算は単
純なもの
– 並列化がしやすい
宮崎大輔（池内研）
光学勉強会
58
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有空間法の長所と短所
固有ベクトルの計算には時間がかかる
• 次元が大きいので固有ベクトルの計算時間がかかる
宮崎大輔（池内研）
光学勉強会
59
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
固有空間法の長所と短所
固有空間法は追試が容易
• 近年の高度な画像処理手法はアルゴリズムが複雑
すぎて追試が困難
– 論文に現れていないノウハウが隠されていたり，さまざまな
仮定が暗黙に入っている
• 固有空間法は考え方が単純でヒューリスティックな処
理段階も少ないので追試が容易
宮崎大輔（池内研）
光学勉強会
60
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
スパースコーディング
元画像をブロックに切り出す
主成分分析
宮崎大輔（池内研）
光学勉強会
スパースコーディング
61
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
スパースコーディング
• 主成分分析の基底
• スパースコーディングの基
底
– フーリエ変換の基底に似てい
る
– 画像の再現性が低い
宮崎大輔（池内研）
光学勉強会
– ウェーブレット変換の基底に
似ている
– 画像の再現性が高い
62
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
スパースコーディング
きたない画像
元画像
宮崎大輔（池内研）
光学勉強会
主成分分析
63
スパースコーディング
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
光学勉強会
64
(c) Daisuke Miyazaki 2006
All rights reserved.
http://www.cvl.iis.u-tokyo.ac.jp/
宮崎大輔, "固有空間法による画像認識,"
U30ワークショップ, 東京, 2006年11月
Ikeuchi Lab, The University of Tokyo
http://www.cvl.iis.u-tokyo.ac.jp/
宮崎大輔（池内研）

Download Report