画像処理・実習第一回：

画像処理・実習
第十一回：フーリエ変換（続き）とパターン認識
東海大学
電子情報学部情報メディア学科
濱本和彦
今回の内容
直交変換の実習（先週の続き）

フーリエ変換を利用したフィルタ処理
5. パターン認識
5.1 マッチングの原理
 5.2 テンプレートマッチング
 実習


相互相関とテンプレートマッチング
実習
image_processing12.cとimgfft.hを利用します。
void fft2(int flag)





二次元FFTの関数です。
原点（直流成分）は，中心[128][128]です。
flag : 0 フーリエ変換
flag : 1 逆フーリエ変換
フーリエ変換時は，パワースペクトルを出力します。
lena.rawとlenan20.raw（ノイズ有り）のパワース
ペクトルを比較しましょう。
逆変換することで元の画像が得られることを確
認しましょう。
Lenaのパワースペクトル
低周波部
にエネル
ギーが集中
高周波部にも均等にエネルギーが分布
低域通過フィルタ
高域を強制的に0としてカットします。
？
void lpf(void)を実行し結果を確認しなさい。
lpf()は，必ずfft2(0)の後に実行すること。
低域通過フィルタ結果
縦，横
とも20で
カット
縦，横
とも50で
カット
ほぼ移動平均平滑化に等しい
高域通過フィルタ
低域を強制的に0としてカットします。ただし，直
流分は残します。
？
void hpf(void)を実行し結果を確認しなさい。
hpf()は，必ずfft2(0)の後に実行すること。
高域通過フィルタ
縦方向，横方向とも均等に低域カットした場合の
画像を求めなさい。
縦方向の高域のみ（横方向は全てカット），横方
向の高域のみ（縦方向は全てカット），それぞれ
の画像を求めなさい。
直流分が無くなったらどのような画像になります
か？
ノイズがある場合にこの処理を施したらどのよう
な結果になるでしょうか？
高域通過フィルタ結果
均等にカットした場合
縦，横ともに5でカット
縦，横ともに10でカット
より低域が少なくなり，
エッジが目立つ画像と
なる。
高域通過フィルタ結果
縦方向高域のみ（横方向全カット）横方向高域のみ（縦方向全カット）
縦方向は5でカット
横方向は5でカット
横線のエッジのみ抽出
縦線のエッジはほぼ消滅
縦線のエッジのみ抽出
横線のエッジはほぼ消滅
高域通過フィルタ結果
縦，横ともに10でカット
直流分あり
縦，横ともに10でカット
直流分なし
エッジだけの画像となる
高域通過フィルタ結果
ノイズがある場合
縦，横とも
10でカット
ごま塩状の雑音はほぼそのまま
残ってしまっている
周波数空間におけるX,Y方向微分
N 1 M 1
f (m, n)    F (k , l )W1 W2
 km
ln
l 0 k 0
 2

 2 
   F (k , l ) exp j
km  exp j
ln 
 M

 N 
l 0 k 0
N 1 M 1
f (m, n) N 1 M 1
2
 km
ln
   F (k , l ) j
k W1 W2
M
l 0 k 0
x方向（離散m方向）微分 m
これを逆変換すればX方向微分になる
f (m, n) N 1 M 1
2
 km
ln
  F (k , l ) j
l W1 W2
n
N
l 0 k 0
y方向（離散n方向）微分
同様に
周波数空間におけるX,Y方向微分
X方向フィルタ関数（Y方向も同様）
Ax(k)
-M/2
M/2
k
2
Ax (k )  j
k
M
微分処理実習
x方向微分の関数 void x_diffrentiation(void)
y方向微分の関数 void y_diffrentiation(void)
を完成させなさい。フィルタ関数が複素数であ
る事に注意しなさい。複素数と複素数の乗算に
なります。
lena.rawについて，それぞれの微分処理を
行った画像を出力しなさい。
微分処理結果
X方向微分
縦方向のエッジ抽出
Y方向微分
横方向のエッジ抽出
周波数空間におけるラプラシアン
f (m, n) N 1 M 1
2
 km
ln
   F (k , l ) j
k W1 W2
m
M
l 0 k 0
 f (m, n)
 2
  F (k , l )  j
2
m
 M
l 0 k 0
2
同様に
N 1 M 1
2

 km
ln
k  W1 W2

 f (m, n)
 2 
km
ln
  F (k , l )  j
l  W1 W2
2
n
 N 
l 0 k 0
2
N 1 M 1
∴ ラプラシアン＝
2
 2 f (m, n)  2 f (m, n)

2
m
n 2
ラプラシアンフィルタ関数
 2
A(k , l )   j
 M
  2
k  j
  N
2
  Ax (k )   Ay (l ) 
2
2

l

2
ラプラシアンフィルタ実習
ラプラシアンフィルタ関数
void f_laplacian(void) を完成させなさい。
lena.rawに対する処理結果を求めなさい。
ラプラシアン結果
パターン認識
人が目で見て判断する内容
・人を見分ける
・文字を読む
など
コンピュータに代行させる
＝
パターン認識
マッチングの原理
人が目で見て判断するという事は？
目で見た内容が頭の中の記憶と一致する
かどうかを考えること。
一致するものを探す＝マッチングをとる
マッチングを取るには？
各点におけるデータの差を計算し積算する。
結果が０であれば，マッチングしている。
マッチング（類似度）を計算してみよう
関数f(x)と関数g(x)の類似度の計算
差を計算して，それを積算（積分）

b
a
f ( x)  g ( x) dx
これが小さいほどよく似ている，ということ。
この二つはマッチングしている？
類似度は？
１３１０７２０！
見た目では同じ
パターンなのに，
類似度は。。。！
つまり，こういうこと。
濃
淡
値
レベルを合わせて比較
Ｂ
平均値を引いてから類似度
を計算する！
Ａ
F ( x)  f ( x)  f
G ( x)  g ( x)  g
座標
パターンＡとパターンＢは，
形（パターン）は同じだが，
レベル（平均値）が異なる

b
a
平
均
値
F ( x)  G( x) dx
他の類似度計算方法
a F ( x)  G( x) dx
b
b
2
b
残差二乗和
b
  F ( x)dx   G ( x)dx  2 F ( x)G( x)dx
a
2
2
a
F(x)，G(x)に関する定数であり，二
つの関数の違いを表す量ではない
a
この項が大きいほど
二つの関数は良く
一致する！
一般的なマッチングの尺度
フーリエ変換を
思い出してみよう
b
s   F ( x)G( x)dx
a
ある座標における関数値の積の総和＝関数の内積
それぞれの関数の大きさで正規化すると次のようなります。
R

b
a

b
a
2
F ( x)G( x)dx
F ( x)dx

b
a
G 2 ( x)dx
一般的なマッチングの尺度
R

b
a

b
a
2
F ( x)G( x)dx
F ( x)dx
b
G
a
2
これは-1～+1の値をもち，
cosΘで表現されます。
 cos 
( x)dx
相互相関係数
Θは関数間の角度。
二つの関数をベクトル
表現した時のベクトル
が作る角度になます。
演習5.1
f(x)，g(x)ともに平均値は０であるため，
f(x)，g(x)をそのまま用いて計算する。

b
a


1
f ( x)dx   sin x    cos 2 x  1dx


2
2
2

1 1
1

   sin 2 x  x        
2 2
2
 

演習5.1

b
a


1
g ( x)dx   sin x   dx    cos2 x  2   1dx


2

1 
   cos 2x   dx   dx


2  
1 
 
   cos 2 x  cos 2  sin 2 x  sin 2dx  x 

2  
1
        
2
2
2
演習5.1

b
a

1 
f ( x) g ( x)dx   sin x  sin(x   )dx    cos2 x     cos  dx

2 
1 
   cos2 x     cos dx
2 
1

 cos  x
2
1
 cos    cos     cos  
2
演習5.1
 R  cos 
cos  
 
 cos
  
二つの関数が作る角＝位相差が相互相関の結果です。
つまり，θだけ関数をずらせばぴったり一致する，
Θだけずれているから類似度はcosθ，と言うわけです。
（θ＝０の時はcosθは１，つまり一致しているということ）
ディジタルデータの相互相関係数
二つのデジタルデータ → ベクトルデータとして考える
 f1 , f 2 
g1, g2 

 f

g
相互相関係数は，ベクトルの内積を用いて次のように表現する。
 
 
f , g  f  g cos
であるから，
 
f,g
R  cos   
f  g

f1 g1  f 2 g 2
f1  f 2
2
2
g1  g 2
2
2
ディジタルデータの相互相関係数
一般にN次元ベクトルの場合には次のように表される。
N 1
f
R  cos 
k 0
N 1
 fk
2
k 0
k
gk
N 1
 gk
2
k 0
実際の場合は平均値を引く必要があるため次のようになる。
f
N 1
R  cos 
k 0
f
N 1
k 0
k
 f g k  g 
 f
2
k
N 1
2


g

g
 k
k 0
実習：演習5.2
image_processing12.cとimgpattern.hを
利用します。
imgpattern.hのvoid Ensyu5_2(void)を完
成させなさい。
相関の結果が演習5.1の通りになることを
確認しなさい。
画像の相互相関関数
データが二次元の画像（N×N）の場合も，同様な処理で
相互相関係数が求まります。
  f [k ][l ]  f t[k ][l ]  t 
N 1 N 1
R
l 0 k 0
  f [k ][l ]  f   t[k ][l ]  t 
N 1 N 1
l 0 k 0
2
N 1 N 1
l 0 k 0
2
実習：画像の相互相関係数
void Cross_correlation(void)を完成させなさい。
この関数の実行時は，Input_image()や
Output_image()は必要ありません。関数内で２
つの画像をオープンします。
lena.raw同士，lena.rawとlenan20.raw(雑音が
ある場合)，lena.rawとlenai.raw(白黒反転)の組
合せで相互相関係数を求め，考察しなさい。
実習：画像の相互相関係数
-1.0
1.0
0.835
相互相関でこんなことができます。
簡単な人物認証
濱本研メンバーDB
こういう人がやってきました
Ａ 0.434
Ｂ 0.548
Ｃ 0.652
相互相関係数を求めます。
Ｅさんと判断されました。
Ｄ 0.512
Ｅ 0.746
Ｆ 0.564
研究室への入室が許可されます。
相互相関でこんなことができます。
簡単な人物認証
濱本研メンバーDB
こういう人がやってきました
Ａ 0.321
Ｂ 0.619
Ｃ 0.836
相互相関係数を求めます。
Ｃさんと判断されました。
Ｄ 0.650
Ｅ 0.698
Ｆ 0.537
研究室への入室が許可されます。
相互相関でこんなことができます。
簡単な人物認証
濱本研メンバーDB
こういう人がやってきました
Ａ 0.186
Ｂ -0.089 Ｃ -0.046
相互相関係数を求めます。
どのデータとも相関が高くありません。
Ｄ -0.190 Ｅ -0.134 Ｆ -0.080
研究室への入室が許可されません。
テンプレートマッチング
入力画像の中から，テンプレート（標準パターン）
に一致する位置を検出します。


パターン位置の検出
動いた物体の追跡
方法



画像にテンプレートを重ね相互相関係数を計算します。
テンプレートの位置をずらして再度相互相関係数を計
算します。
これを繰り返して，相互相関係数が最大になる位置を
探します。
テンプレートマッチング
テンプレートを移動しな
がら，相互相関を計算
相互相関が最大になっ
た位置が，テンプレートの
パターンと同じ図形となる
位置である。
テンプレートマッチング
テンプレートサイズをm×nとし，画像上の位置(i, j)における
相互相関係数は次の式で求められます。これは，式5.16に
平均値処理と正規化を加えたものです。相互相関関数と呼
ばれます。



l 0 k 0 
n 1 m 1
R[i ][ j ] 
 m
 n 
f i   k   j   l  
2 
 2

  m

 n 
f
i


k
j


l

f



 2
  2 
l 0 k 0 

n 1 m 1
2

f t[k ][l ]  t 

n 1 m 1
2


t
[
k
][
l
]

t

l 0 k 0
・テンプレートの中心が(i, j)と一致するようにしています。
・平均値は，m×n領域内での平均値です。
・式5.16では正確な処理を行うことは出来ません（何故？）
実習：テンプレートマッチング
void Template_matching(void)を実行し，テンプレート
マッチングの処理を確認しましょう。
テンプレートのサイズは，幅40，高さ48です。
テンプレート画像は，この関数内で入力処理を行います。
対象画像の入力は，Input_image()で行ってください。
相互相関が最大になった位置とその時の相関値を出力
します。
相関係数がどのように分布しているかを画像として出力
します。これを相互相関関数と呼びます。
入力画像：characters3.raw
テンプレート：characters3a.raw
実習：テンプレートマッチング
＝‘Ａ’の文字はこの
最大値：
x=50, y=69, R=1.00 位置にある！
実習：テンプレートマッチング
void Template_matching2(void)は，式
5.16によるものです。正しい結果が得られ
ないことを確認してください。
それは一体何故でしょうか？
こういうことができます
は，どこにいるでしょう？
最大値：
x=179, y=25
課題
教科書p.76の式5.17によりテンプレート
マッチングを行うプログラムを完成させ，
characters3.rawとcharacters3a.rawを用
いた実行結果を示してください。
提出期限は7/31，23:59とします。
i-collaboから提出してください。

Download Report