画像処理論
第8回
佐藤洋一
生産技術研究所
情報理工学系研究科電子情報学専攻／情報学環
http://www.hci.iis.u-tokyo.ac.jp/~ysato/
本日の講義の内容

2値画像の処理


モルフォロジーによる各種操作
クラスタリング

階層的クラスタリング

分割最適化クラスタリング

教師付きクラスタリング
Boundary extraction

正方形の構造要素でErodeしたものと元の連結成分との差
β ( A) = A − ( A − B)

構造要素サイズにより境界の太さを調整可能
Region filling

領域内の点から開始し、操作の繰り返しにより実現
X k = ( X k −1 ⊕ B)  AC

この例のように、範囲を限定しながら行うdilationの操作を
“conditional dilation”と呼ぶ
連結成分の抽出

連結成分中の画素pから、下記処理の繰り返し
X k = ( X k −1 ⊕ B)  A
Thinning

構造要素 Bi （特定方向画素）を連続的に用いて細線化する
A ⊗ {B} = (( (( A ⊗ B1 ) ⊗ B 2 ) ) ⊗ B n )
ただし
A ⊗ B = A − ( A ∗ B) 複合処理の例： Pruning

文字認識に伴うthinningやskeltoningで生じる小さな“ヒ
ゲ”の除去など
“a”の例
複合処理の例：Pruning

ヒゲの長さがn以下である場合
1.
ヒゲも含めて線の端点をnだけ短縮
2.
1.の結果得られた細線の端点をnだけ伸張
Pruning

端点からの縮小

以下のthinning操作をn回適用
X 1 = A ⊗ {B}
Pruning

端点からの伸長

構造要素{B}によるHit-or-Miss変換により端点を検出
8
X 2 =  ( X1 ∗ Bk )
k =1

Aによるconditional dilationにより端点からnだけ伸ばす
X3 = (X2 ⊕ H )  A

処理の結果
X 4 = X1  X 3
A
郵便番号認識の前処理

複数文字の結合、ストロークの分断、ヒゲ、などへの対応
組み立て部品の分類
input
thinning
differencing, thinning end-point thinning,
hit-or-miss
end point thinning
dilation
dilation
プリント基板の各要素の分類
input
filling, differencing
differencing
Hit-or-miss
thinning
クラスタリング
セグメンテーション

画像を意味のある領域に分割する処理

どうやって“意味のある”領域に分割するのか？
クラスタリングによる画像分割

クラスタリング


分布対象の集合を部分集合に分割
画像では全画素（分布対象の集合）を領域（部分集合）に分割
特徴空間

分類対象の特徴量を表現する空間


特徴空間（R-G平面）
色で分類⇒(r,g,b)
色と場所で分類⇒（x,y,r,g,b)
特徴空間への射影

クラスタリングとは、特徴空間内の分布から群（クラスタ）を
見つける処理
要素間距離：ユークリッド距離

ユークリッド距離（Euclidean distance）を利用

L2-normと同じ
 
  t  
d ( x , mc ) = ( x − mc ) ( x − mc )
2
E

m2

m1
 
d E ( x , m1 )
 
d E ( x , m2 )

x
階層的クラスタリング

最初にN個のクラスタが与えられたとし、クラスタの数がCに
減少するまで最も類似した２つを融合

Cを事前に決定

クラスタ間の類似度の決め方に依存
クラスタ間の距離（1）
重心間距離
D(C1 , C2 ) = D( x1 , x2 )
群平均距離
1
D(C1 , C2 ) =
n1n2
∑ ∑ D( x , x )
x1∈C1 x2 ∈C 2
1
2
クラスタ間の距離（2）
最長距離
最短距離
D(C1 , C2 ) =
min
x1∈C1 , x2 ∈C 2
D( x1 , x2 )
D(C1 , C2 ) = max D( x1 , x2 )
x1∈C1 , x2 ∈C 2
※特徴空間内にクラスタが散在しやすい
※連鎖クラスタを生じやすい
連鎖クラスタ
ウォード法

クラスタを融合したとき、クラスタの重心位置からの二乗距離
和の増加量ΔSを最小にするクラスタ２つを選択する方法
∆S = S c − ( S a + S b)
   
ただし、S = ∑ ( xi − m) t ( xi − m)
N
i =1

要素数が極端に大きいクラスタを生成しない傾向
分割最適化クラスタリング


分割の良さの評価指標をもとに、最適な分割を繰り返し探索

最初からN個のサンプルデータをC個のクラスタに分割し、
その分割の仕方を徐々に修正していく

近い2つを統合していく階層クラスタリングとの違い
最も代表的な手法はk-平均法
K-平均法
K-平均法の性質


メモリ効率の良さ

階層的クラスタリング→N(N-1)/2 組の距離

K-平均法→C個のクラスタの平均ベクトル
計算コストの高さ


各データに対して最近傍のクラスを探索
最終的なクラスタリングの結果が種子点に依存

異なる種子点で複数回クラスタリングを行い、
適当なものを選ぶなどの工夫が必要
K-平均法の適用例
Image
Clusters on intensity
Clusters on color
K-means clustering using intensity alone and color alone
画像のグラフ表現
グラフ分割による画像セグメンテーション
スペクトラルクラスタリング

ノード間の類似度を表現した類似度行列の解析に
もとづいたクラスタリング手法
類似度行列A
ai , j = a j ,i = ノードiとjの類似度
類似度の例
輝度値の近さ
距離の近さ
色の近さ
スペクトラルクラスタリングの概要
Data
Similarities
Block-Detection
ノード⇒クラスタの結合度と要素間類似度


k個のノードのあるクラスタへの結合度をk次元ベクトルwで
表現
ノード⇒クラスタ結合度と要素間類似度の合計
T
w Aw
∑{[ノードiの結合度]×∑{[ノードiとノードjの類似度] ×[ノードjの結合度]}}
類似度行列A
重みベクトルw
要素1
ノード⇒クラスタの結合度と要素間類似度


k個のノードのあるクラスタへの結合度をk次元ベクトルwで
表現
ノード⇒クラスタ結合度と要素間類似度の合計
T
w Aw
∑{[ノードiの結合度]×∑{[ノードiとノードjの類似度] ×[ノードjの結合度]}}
類似度行列A
重みベクトルw
ノード1
ノードk
結合度と類似度の最大化

ノード→クラスタの結合度、要素間の類似度の合計の最大化
T
w Aw の最大化

重みベクトルの正規化を条件として
wT Aw + λ ( wT w − 1) の最大化

wに関する微分＝0より固有値問題に帰着
Aw = λw
固有ベクトルとブロック
Block matrices have block eigenvectors:
λ1 = 2

λ2 = 2
1
1
0
0
.71
0
1
1
0
0
.71
0
0
0
1
1
0
.71
0
0
1
1
0
.71
eigensolver
λ3 = 0
λ4 = 0
Near-block matrices have near-block eigenvectors:
λ1= 2.02 λ2= 2.02 λ3= -0.02 λ4= -0.02

1
1
.2
0
.71
0
1
1
0
-.2
.69
-.14
.2
0
1
1
.14
.69
0
-.2
1
1
0
.71
eigensolver
Spectral Space

Can put items into blocks by eigenvectors:
1
1
.2
0
.71
0
1
1
0
-.2
.69
-.14
.2
0
1
1
.14
.69
0
-.2
1
1
0
.71
e1
e2

Clusters clear regardless of row ordering:
1
.2
1
0
.71
0
.2
1
0
1
.14
.69
1
0
1
-.2
.69
-.14
0
1
-.2
1
0
.71
e1
e2
e1
e2
e1
e2
スケールの影響
データ分布
固有値列
小←大
スペクトラルクラスタリングの欠点

類似度行列の複数の固有値が等しい場合
固有値列
データ分布
４つの固有ベクトル
Normalized cuts


Current criterion evaluates within cluster similarity, but not
across cluster difference
Instead, we’d like to maximize the within cluster similarity
compared to the across cluster difference

Write graph as V, one cluster as A and the other as B

Maximize
N assoc =
V
assoc( A, A) assoc(B, B )
+
assoc( A,V ) assoc( B,V )
assoc(A,A) : the sum of weights of all edges within A
assoc(A,V): the sum of weights of all edges that have one end in A
Nassoc and Ncut

Consider Ncut instead of Nassoc
N assoc
assoc( A, A) assoc(B, B )
=
+
assoc( A,V ) assoc( B,V )
N cut
V
cut ( A, B )
cut ( A, B )
=
+
Assoc( A, V ) Assoc( B,V )
Cut(A,B) : the sum of weights of all edges that have one end in A and the other in B

The cost Ncut is related to Nassoc as Ncut=2- Nassoc .
Finding Minimum Normalized-Cut

It can be shown that min N cut
y T (D − W )y
= min y
y T Dy
such that y (i ) ∈ {1,−b}, 0 < b ≤ 1, and y T D1 = 0


If y(i)=1, then i-th node belongs to one cluster, otherwise the
other cluster.
D is N x N diagonal matrix where
D(i, i ) = ∑ W (i, j )
j

If y is allowed to take real values then the minimization can
be done by solving the generalized eigenvalue system
(D − W )y = λDy
Normalized Cut: Overview

Compute matrices W & D

Solve

for eigen vectors
Use the eigen vector with second smallest eigen value to
bipartition the graph. (The smallest one is always zero.)


(D − W )y = λDy
Threshold for y(i) can be chosen s.t.
y T (D − W )y
y T Dy
is minimized.
Recursively partition the segmented parts if necessary.
Normalized Cutによる分割の例
本日の講義内容のまとめ

2値画像の処理



モルフォロジーによる各種操作
クラスタリング

階層的クラスタリング

分割最適化クラスタリング

スペクトラルクラスタリング
参考資料

Gonzalez&Woods 8.4章

Forsyth & Ponce, Chapter 14.5

画像処理標準テキスト4章