講義スライド

画像処理論
第7回
佐藤洋一
生産技術研究所
情報理工学系研究科電子情報学専攻／情報学環
http://www.hci.iis.u-tokyo.ac.jp/~ysato/
前回講義内容の復習

RANSAC

対象領域の抽出

2値化処理

Deformable contours
RANSACによるモデル当てはめ

S個の点により定義されるモデルの場合
１．ランダムなサンプリング

データ点からS点をランダムに選択

選択したS点からモデルパラメタを計算
２．サポートの検証

データ点のうち、モデルに十分近い点（サポート）を選択

十分なサポートがあれば終了、or 以上の手順を十分な回数繰り返し
３．終了処理

モデルパラメタのサポート点を用いて、モデルパラメタを再推定
対象領域の抽出

閾値処理

ヒストグラムにもとづく閾値決定法

p-tile法

モード法

分散比最大化（Ohtsu’s method)
Deformable contour models

segmentation

tracking
Deformable contourのエネルギー関数



E  ai Econt ( pi )  bi Esmooth ( pi )  ci Eedge ( pi )
N
i 1
internal
external

 
Econt ( pi )  (d  pi  pi 1 ) 2


 
Esmooth ( pi )  pi 1  2 pi  pi 1


Eedge ( pi )   I ( pi )

2
Edge attraction
Continuity
Greedy アルゴリズムによるEの最小化
Smoothness
連続系での表現
Energy Functional is defined as:
E  (a ( s ) Econt ( s )  b( s ) Esmooth( s ) c( s ) Eedge ( s )) ds
2
2 2

d p
dp
  (a( s)
 b( s ) 2 c( s )(  I ( p ) )) ds
ds
ds
internal
external
where a,b,c are “weights” to control influence.
Edge attraction
Continuity
Smoothness
本日の講義の内容

2値画像における領域と処理

モルフォロジー処理
領域の連結性

領域の属性を考える前に、領域の連結性を定義


4近傍
４連結と８連結
連結成分（connected component）
⇒連結したひとまとまりの画素
8近傍
連結成分のラベリング

連結成分ごとに異なるラベル（番号）を付与

ラベリングは連結成分の属性解析に必要
2値画像のラベリング

http://homepages.inf.ed.ac.uk/rbf/HIPR2/labeldem
o.htm
ラベル付けのアルゴリズム
1.
L=0とし、順方向ラスタスキャン開始
2.
ラベルの無い画素 f(m,n) において、既走査の４隣接画素
（下図の○）のラベル値を調べる
全て0（背景）ならば、L=L+1とし、g(m,n)=L
ラベル値が1種類ならば、g(m,n)=L
ラベル値が2種類でL, L’(L<L’)ならば（ラベルの衝突、下図の①と④）、
g(m,n)=Lとし、ラベルL’の既走査画素をLに変更
領域の特徴量
連結成分とホール

ホール


単連結（simply connected）


一つの連結成分中に存在し、背景と連結しない0連結成分
ホールのない連結成分
多重連結（multiply connected）

ホールを１つ以上含む連結成分
単連結
ホール
多重連結
オイラー数

連結成分のトポロジカルな性質


位相的な不変量であり、図形を連続的に変化させても不変
オイラー数

E＝（連結成分の個数）－（ホールの個数）
連結成分のモーメント

図形的特徴量としてよく用いられる

2次元関数 g(x,y) の p+q次モーメント
m pq   x p y q g ( x, y )dxdy

連結成分のモーメント
m pq 
p q
x
 y
( x , y )R
面積と重心

面積：0次モーメント
m00 

0 0
x
 y 
( x , y )R
1
( x , y )R
重心：１次モーメントを0次モーメントで正規化
 m10   x1 y 0   x

( x , y )R
( x , y )R

0 1

m
x
y  y

 01
( x , y )R
( x , y )R

m10
m01
xG 
, yG 
m00
m00
重心モーメントと慣性モーメント

重心モーメント（重心周りのモーメント）
M pq 

( x , y )R
２次の重心モーメント（慣性モーメント）
M 20 

p
q
(
x

x
)
(
y

y
)

G
G
 (x  x
( x , y )R
G
) 2 , M 02 
(y  y
( x , y )R
連結成分の主軸方向
1
2
  arctan(
2 M 11
)
M 20  M 02
G
) 2 , M 11 
 (x  x
( x , y )R
G
)( y  yG )
慣性モーメント量の利用
正規化重心モーメントと不変量

正規化重心モーメント
0次モーメントで正規化した重心モーメント

 pq 

M pq
M 00

pq
,  
1
2
回転・平行移動・拡大縮小に対する不変量
2～3次モーメントで7つの不変量

1   20   02
2  ( 20   02 ) 2  4112
3  (30  312 ) 2  (3 21   03 ) 2
4  ( 03  12 ) 2  ( 21   03 ) 2

不変量の例
縮小
反転
注）ここでは濃淡図形のモーメント
元の図形
回転
回転
領域の特徴的な点
内部点と境界点

境界点


2値画像の領域で背景と接している経路をなす点
内部点

2値画像の領域で境界点以外の点


8連結の場合の内部点：4近傍に背景がない
4連結の場合の内部点：8近傍に背景がない
境界線追跡

ある境界点からスタートし、順に境界点を追跡

注目画素を中心に常に一方向で3X3の近傍を調べ、
背景→前景に変わる点を見つける

追跡開始点にたどりついたら探索を終了
2値画像の画素の分類：連結数

境界線追跡をしたとき、その画素を通過する回数
4連結の場合
NC
[ 4]
1
8連結の場合
NC
[8 ]
2
連結数にもとづく画素の分類

連結数0：孤立点または内部点

連結数1：端点

連結数2: 連結点
（例 (f)のN8, (j)のN4）

連結数3：分岐点
（例 (h)のN8）

連結数4：交差点
（例 (l)のN8）
（例 (a), (k)のN8）
（例 (i)）
連結数の計算

連結数は次式により求めることができる
NC
NC
[ 4]

( f
k4近傍
[8 ]

( f
k4近傍
k
k
 f k f k 1 f k  2 )
 f k f k 1 f k  2 )
x4 x3 x2
x5 x0 x1
x6 x7 x8
ただし、k  8ならk  k  8とする
f  1 f
距離変換と細線化
連結成分の距離変換

距離変換（distance transformation）

連結成分の各画素に対して、背景の最小距離を計算
4-近傍距離と8-近傍距離

連結性に応じて2種類：４近傍距離と8近傍距離

連結成分の画素(m,n)から背景画素(k,l)への距離
d ( 4 ) (m, n)  min ( m  k  n  l )
k ,l
d (8) (m, n)  min{max( m  k , n  l )}
k ,l
距離変換の方法


手順
1.
境界点となる画素の距離値を１にセット
2.
画素の近傍点を調べ、近傍点に距離がセットされている場合に
は、その距離+1にセット
3.
全画素に距離が割り当てられるまで2を繰り返す
最大距離回数だけ全画素を走査するため非効率
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
X
X
X
1
1
2
2
2
1
1
2
2
2
1
1
X
X
X
1
1
2
X
2
1
1
2
3
2
1
1
X
X
X
1
1
2
2
2
1
1
2
2
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
ラスタ走査2回による距離変換

順方向と逆方向のラスタ走査の組合せで距離変換
距離変換の例

http://www.dai.ed.ac.uk/HIPR2/distancedemo.htm
連結成分の細線化

連結性を保ったまま、連結成分の画素を除去

3X3の局所領域における処理の繰り返しにより実現
細線化アルゴリズム（8連結）

右側境界→上側境界→左側境界→下側境界の順に、
画素を取り除けるかどうか調べていく

基本的な考え方

3X3近傍に２つ以上の連結成分が存在すれば保存
（抽出点条件）
→その画素を取り除いてしまうと連結性を変えてしまうため
細線化アルゴリズム（8連結）
1.
繰り返し回数 k=0 とする
2.
flag=0
3.
k=k+1
4.
画像中に境界条件C(k)を満たす値1の画素pがあればflag=1とし、次の
処理をする

pが抽出点条件を満たしていればf(p)=2としその画素を永久保存点とする
満たしていなければf(p)=3とする
5.
f(p)=3の画素全てをf(p)=0とし消去する
6.
k<4ならば3.へ
7.
flag=0なら終了。そうでなければ1.へ
細線化の例
モルフォロジー処理
input
filling, differencing
differencing
Hit-or-miss
thinning
モルフォロジー処理
2値画像のモルフォロジー処理

Mathematical morphologyにもとづく幾何構造処理

一般的にn次元のデータに対して定義


濃淡画像や3次元ボリュームデータにも拡張可能
基本4操作

Dilation

Erosion

Opening

Closing
基本定義（１）


連結成分A

Z2（2次元の整数）で定義される集合

原点が１つ定義される

Aの構成要素（画素）はa=(a1,a2)
Translation of A by x （平行移動）
( A) x  {c c  a  x, for　a  A}
基本定義（２）

Reflection of B（反転）
Bˆ  {x x  b　for　b  B}

Complement of set A（補集合）
AC  {x x  A}

Difference of two sets A and B（差分）
A  B  {x x  A, x  B}  A  B C
Dilationオペレータ（膨張）
 dilation

of A by B
B：構造要素
A  B  {x ( Bˆ )  A  }
x
A
Bˆ  B
A B
Erosionオペレータ（収縮）
 erosion
of A by B
A  B  {x ( B) x  A}
DilationとErosionの双対関係

Erosionの補集合は
( A  B)  {x ( B) x  A}
C

C
( B) x が A に含まれるということは ( B) x  AC  
( A  B )  {x ( B ) x  A  }
C
C
C
C
C
(
B)

A


(
B)

A
  となる x

を満たすxの補集合は
x
x
( A  B )C  {x ( B) x  AC  }  AC  Bˆ
Openingオペレータ
 opening

of A by B
細い所を削除する性質
A  B  ( A  B)  B
Closing
 closing

of A by B
細い溝を埋める性質
A  B  ( A  B)  B
Openingオペレータの解釈

構成要素BをAの中に収まるようにスライドさせた時にBによ
り走査される領域
A  B  {( B) x ( B) x  A}
Closingオペレータの解釈

zを含むようにBをスライドさせた場合、必ずBとAが重なりを持
つような z はA・Bの要素となる
OpeningとClosingの性質



Opening  とclosing はcomplementationとreflectionに
関して双対関係
( A  B) C  ( AC  Bˆ )
Openingの性質

A  B はAのサブセット

もしCがDのサブセットならば、 C  B は D  B のサブセット

( A  B)  B  A  B
Closingの性質

Aは A  B のサブセット

もしCがDのサブセットならば、 C  B は D  B のサブセット

( A  B)  B  A  B


http://homepages.inf.ed.ac.uk/rbf/HIPR2/morops.
htm
http://www.cs.bris.ac.uk/~majid/mengine/morph.
html
Morphological filter

基本オペレータの組合せで各種処理を実現

細かなゴミの除去の例
Hit-or-Miss Transform (1)

テンプレートマッチング

入力画像Aの中で対象Xを検出

ここで B は X にもとづくテンプレート
B  ( B1 , B2 )  ( X ,W  X )
Hit-or-Miss Transform (2)
A  B  ( A  X )  [ AC  (W  X )]

AとACのErosion

Erosionの結果を統合→Xの検出
Hit-or-Miss Transform (3)

Hit-or-Miss変換 *
A  B  ( A  X )  [ A  (W  X )]
C


ここでBはXにもとづくテンプレート
B  ( B1 , B2 )  ( X , W  X )
erosionとdilationの双対関係と差分の定義より
A  B  ( A  B1 )  ( AC  B2 )
すなわち
A  B  ( A  B1 )  ( A  Bˆ 2 )
本日の講義内容のまとめ

2値画像における領域と処理

連結性とラベリング処理

オイラー数

モーメントと図形特徴

境界線と連結数

距離変換

細線化

モルフォロジー処理

参考資料



Trucco&Verri 5.4章
谷口 7.1～7.4章
Gonzalez&Woods 8.4章
講義に関するメモ

平成14年度

追加すべき項目


平成16年度

分量がやや多すぎ





Gray-scale morphological operations
Convex HullとThickeningを割愛する
質問事項

なぜDilationの構造要素を反転するのか

Convex HullがConvex Hullになっていない理由⇒第2版を確認

Thinningの最後のステップを確認
平成18年度

Convex hullをカット

各種処理部分が単調すぎ⇒一部を減らし、濃淡モルフォロジーを追加すべき
平成20年度
 連結成分記述からスタート
 画素の連結数の説明を復活
 モルフォロジーの説明を分割
 各操作の説明にアプレットを利用する
http://homepages.inf.ed.ac.uk/rbf/HIPR2/morops.htm
平成24年度

Hit-or-Missの前までで終了
オイラー数の計算
方法１．境界を追跡した場合の向きによりホールを検出
方法２．凸画素と凹画素の数え上げ

方法１
ある方向を考えた場合に、
オイラー数E＝(# convex pixels)-(# concave pixels)
方法２
近傍画素からのオイラー数の計算

4連結 E(4) = V – E + F

8連結 E(8) = V – E – D + T – F
V: 画素数
V=23, E=15, D=2, T=11, F=0
チェーンコードによる線図形の表現

輪郭の方向コードにより形を表現


境界線追跡や細線化処理などにより求めた線図形を効率よく記
述する方法
平行移動に対して不変だが、回転に対しては変化
→Derivativeの利用
フーリエ記述子による線図形の表現
 輪郭形状を各周波数成分の和で表現
s (k )  x(k )  jy (k ) ただしk  0,  , N  1
この時、フーリエ変換とフーリエ逆変換は
1
a (u ) 
N
N 1
 s(k ) exp[ j 2uk / N ]
k 0
N 1
s (k )   a(u ) exp[ j 2uk / N ]
u 0

一部の隠れなどで係数が大幅に変化してしまう問題
フーリエ記述子による形状の近似

M（M＜N)次元までの係数を利用することにより
概略形状を表現
M 1
sˆ(k )   a (u ) exp[ j 2uk / N ]
k 0
フーリエ記述子による形状表現の例
フーリエ記述子の変換

元図形の回転、平行移動、拡大縮小、開始点の変更は係数
の簡単な変換で表現
回転
sr (k )  s (k ) exp[ j ]
ar (u )  a(u ) exp[ j ]
平行移動
st (k )  s (k )  t x  jt y
at (u )  a (u )  (t x  jt y ) (u )
拡大縮小
s s ( k )  s ( k )
as (u )  a(u )
開始点の変更
s p (k )  s(k  k0 )
a p (u )  a(u ) exp[ j 2k0u / N ]
デモ：フーリエ記述子

http://www.s2.chalmers.se/research/image/Java/N
ewApplets/FourierDescriptor/index.htm
Convex hull

連結成分Sに対し、Sを内包する最小の凸形状HをSの
convex hull（凸包）と呼ぶ

連結成分の形状を表現するものとして有効な特徴


D=H-Sはconvex deficiencyと呼ばれ、D/Hは連結成分の凹度
合いを表す
境界の分割に利用
細線の特徴点

細線化後の各点を端点、分岐点、孤立点、通過点に分類
線画像のベクトル化(1)

端点と分岐点をもとに線分に分割
線画像のベクトル化(2)

画素列を再帰的に分割

両端点を結ぶ直線から最も遠い点で
分割

全ての点がある距離以内に収まった
段階で終了

Download Report