Intelligent Sensing Laboratory, Chukyo University

第19回 画像センシングシンポジウム
チュートリアル講演会
2013年6月12日

テンプレートマッチングの魅力～ 物体検出・位置決めの定番技術 ～中京大学 工学部 橋本 学
mana@isl.sist.chukyo-u.ac.jp
http://isl.sist.chukyo-u.ac.jp/

Googleテンプレートマッチング 48万件，Template Matching 981万件

本日の話題

1. テンプレートマッチングの基本
2. テンプレートマッチングのロバスト化技術
3. テンプレートマッチングの高速化技術
4. 最近の取り組み紹介
参照データの戦略的削減によるマッチング～ CPTMを核として ～Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 20132

産業上の応用例 ・・・ 部品の位置決め

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 20133

産業上の応用例 ・・・ 画像の位置合わせ

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 20134

Intelligent Sensing Laboratory, Chukyo University

テンプレートマッチングのポジショニング

パターン・対象物体検出法
1. 図形の幾何学的なモデルを利用する方法
2. 画像中のローカルな特徴点を利用する方法
3. 画像パターンそのものを利用する方法

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 20136

パターン・対象物体検出法
1. 図形の幾何学的なモデルを利用する方法
2. 画像中のローカルな特徴点を利用する方法
3. 画像パターンそのものを利用する方法[Hough1962], [Ballard1981][Merlin1975][Lamdan1988][Koshimizu1991]

見つけたい対象の幾何学モデルや図形そのものを利用し，投票によって検出する．
パラメータ空間に投票するもの（Hough変換[Hough61]，一般化Hough[Ballard81]）○図形を数学モデルで表現できるときに有効．隠蔽や途切れに強い．
△任意形状にはやや不向き．変形にもあまり頑健ではない．
画像空間に投票するもの（Merlin法[Merlin1975]）○パラメータ空間に変換する必要がない．隠蔽や途切れに強い．
△テンプレートを図形として持つ必要がある．

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 20137

Hough変換 ・・・ パラメータ空間での投票[Hough1962], [Ballard1981]

画像空間

xi cosパラメータ空間yi sin

点

sin曲線

直線

（集積）点

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 20138

Merlinの方法 ・・・ 画像空間での投票
テンプレート図形

代表点を始点とする
全ベクトルを考える

代表点を設定[Merlin1975]

180度回転させる
全てのベクトルが逆向きになる

v1
v2

代表点

v3

- v3

- v2

- v1

1.

入力画像（線画）

構成点
2.

3.
Hashimoto Laboratory, Chukyo University

代表点以外の全ての構成点
を入力画像に投票する．→その中には，入力画像中の代表点位置を通る画素が必ず含まれる．（代表点を終点とするベクトルが存在するため）

テンプレート代表
点を入力画像中の各点に重ねる．

集積点

得られた集積点は，検出された図形の代表点である．

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 20139

パターン・対象物体検出法
1. 図形の幾何学的なモデルを利用する方法
2. 画像中のローカルな特徴点を利用する方法
3. 画像パターンそのものを利用する方法[Lowe2004][Bay2006]

キーポイント照合： SIFT，SURF・・・○スケーリング，回転にも対応．照明変動に頑健．高速．
△ある程度テクスチャリッチなパターンが必要．
△連続画像の場合は，毎回キーポイント検出が必要．

SIFT キーポイントの例
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201310

パターン・対象物体検出法
1. 図形の幾何学的なモデルを利用する方法
2. 画像中のローカルな特徴点を利用する方法
3. 画像パターンそのものを利用する方法
画素ベースマッチング （画素をそのまま利用）
代表例： テンプレートマッチング○特徴的な点やテクスチャの多さにあまり左右されない．
○アルゴリズムがシンプルなので，実装しやすい．
×一般的には演算量が多い．
△明るさ変動や変形にはやや弱い．

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201311

物体検出・認識に関する文献数の推移
信学論+電学論+SSII+MIRU
25
Template matching

20

Image matching（画像照合）

15

Object recognition（物体認識）

10

Object detection（物体検出）

5

SIFT

0

物体認識

物体検出

SURF

200
150
100

IEEE Xplore

160 Journals + 1200 Proceedings

物体検出
物体認識

50
1979
1981
1983
1985
1987
1989
1991
1993
1995
1997
1999
2001
2003
2005
2007
2009
2011

0

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201312

Intelligent Sensing Laboratory, Chukyo University

テンプレートマッチングの基本と主な研究動向テンプレートマッチングの基本原理
画素どうしの比較によって，類似度最大の位置を見つける．

[Rosenfeld1969](dx,dy)テンプレートf (i, j )Step1:SCORR(dx , d y )Step2:

入力画像類似性を評価する．
（ex. 正規化相互相関）{(g(dx i, d y(g(dx i, d y

j)

j)
2
g)

g )( f (i, j)

Hashimoto Laboratory, Chukyo University

最大値

f )}

( f (i, j)

類似性が最大になる点を探索し，(dx, dy) を決定する．

g (i, j )2f)

類似度マップ SCORR(d x , d y )第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201314

類似度マップと検出結果

①
⑤

②

③

⑥

④

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201315

類似度尺度① 正規化相互相関
Normalized Cross-Correlation

正規化相互相関M

領域 h(i, j )dx, dymnN

テンプレート画像 f (i, j )入力画像 g (i, j )SNCC(dx , d y )cos( ){g(dx i, d y(g(dx i, d y

f h
f h

j) f (i, j)}j))2( f (i, j))2f (i, j )h(i, j )（内積の定義）

2つの画像領域が似ているほどθが小さい．
n x m 次元空間
すなわち，cos(θ)は１に近づく．
h(i, j ) の長さ（ゲイン）変動を吸収できる（同じ類似度を出力する）．
ただし，2つの画像領域の平均値が異なるときには，類似度は１にならない．
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201316

類似度尺度② 相互相関係数
Zero-means Normalized Cross-Correlation

相互相関係数（統計量）

f (i, j ) と h(i, j ) を，それぞれ画像領域内の濃度値分布と考え，統計量としての相互相関係数を類似度尺度とする．
SZNCC(dx , d y )

f

，

g

{(g(dx i, d y(g(dx i, d y

j)

j)
g

g

)2

)( f (i, j)f( f (i, j)

)}
f

)2

は，それぞれ領域内の濃度値の平均値

データ群 f と g の各平均からのずれを表すベクトルがなす角の余弦である．
ベクトル間距離ではなく角度をみているから，正規化相互相関（NCC）と同様にゲイン変動に強い．
平均値を引いているので，2つの画像領域の平均値が異なっていても類似度が１になる（平均明るさ変動を吸収できる）．
一般的には，NCCよりもZNCCがよく使われる．

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201317

類似度尺度② 相互相関係数の計算量削減
f と g の共分散{(g(dx i, d y

SZNCC(dx , d y )(g(dx i, d y

j)

j)
g

g

)( f (i, j))2f( f (i, j)

)}
f

)2

f と g それぞれの標準偏差プログラムによる実行時には，平均値を求めるために１パス，さらにそれを用いてZNCC値を計算するために１パス，合計2回の2重ループ計算が必要．
分母，分子は，標準偏差または分散値になっているから，よく知られた以下の公式により計算量を削減できる．
分散 ＝ 標準偏差の2乗 ＝ （データの2乗の平均値）ー（データの平均値の2乗）

V

2

1 N
1 N
2
( xk ) (xk ) 2
N k1
Nk1

この式は，分散値と標準偏差を，同時に１パス（1回のループ処理）で計算できることを示している．
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201318

類似度尺度③ 差の２乗和，差の絶対値和
差の２乗和

Sum of Squared Difference

SSSD(dx , d y )差の絶対値和(g(dx i, d y2j) f (i, j))

Sum of Absolute Difference

SSAD(dx , d y )| g(dx i, d y

似ているほど小さな値になるので相違度と呼ばれる．

j) f (i, j) |SSDは正規化項を含まないので，NCCやZNCCより計算量が少ない．
SADは乗算を含まないので，さらに計算負荷が小さい．
いずれの尺度も，明るさ変動には弱い傾向がある．

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201319

類似度尺度の関係
Mdx, dymn
テンプレート画像
f (i, j )N

入力画像 g (i, j )f (i, j )SNCC

領域 h(i, j )SSSD

h(i, j )(cos )SSAD

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201320

類似度尺度の比較 （画像例）

テンプレート画像

明るさオフセット変化あり

元画像（加工なし）

ゲイン変化ありゲイン＋明るさオフセット変化あり

シェーディングあり

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201321

類似度尺度の比較 （画像＝加工なし）
40000040000000

20000

2000000

0

0

○SAD

○SSD

1.0

1.0

0.0

0.0

-1.0

-1.0

○NCC
Hashimoto Laboratory, Chukyo University○ZNCC
第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201322

類似度尺度の比較 （画像＝ゲイン変化あり）
46000050000000

23000

2500000

0

0

×SAD

×SSD

1.0

1.0

0.0

0.0

-1.0

-1.0

○NCC
Hashimoto Laboratory, Chukyo University○ZNCC
第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201323

類似度尺度の比較 （画像＝明るさオフセット変化あり）
44000044000000

22000

2200000

0

0

×SAD

×SSD

1.0

1.0

0.0

0.0

-1.0

-1.0

○NCC
Hashimoto Laboratory, Chukyo University○ZNCC
第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201324

類似度尺度の比較 （画像＝ゲイン＋明るさオフセット変化あり）
50000080000000

25000

4000000

0

0

×SAD

×SSD

1.0

1.0

0.0

0.0

-1.0

-1.0

×NCC
Hashimoto Laboratory, Chukyo University○ZNCC
第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201325

類似度尺度の比較 （画像＝シェーディングあり）
50000060000000

25000

3000000

0

0

×SAD

×SSD

1.0

1.0

0.0

0.0

-1.0

-1.0

×NCC
Hashimoto Laboratory, Chukyo University○ZNCC
第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201326

TMの類似度尺度の計算コスト比較

テンプレート画像（71x55）
入力画像（600x400）

マッチングに要した処理時間[ms]
手法

XP32

Win7-32

Win7-64

Ubuntu10.04

Ubuntu12.10

SAD

1609

1230

982

926

935

SSD

1328

980

780

1695

717

NCC

1703

1491

1216

695

688

ZNCC

2828

2291

1856

3017

1829

ZNCC（簡略化）

1921

2061

1372

739

861

※言語：C言語，コンパイラ：gcc （最適化オプション –O使用），SSE機能使用せず
コンパイラ詳細： XP32 : gcc ver.4.5.3 Win7-32 : gcc ver.4.5.3 Win7-64 : gcc ver.4.5.3
Ubuntu 10.04 : gcc ver.4.4.3 Ubuntu 12.10 : gcc ver.4.7.2
Hashimoto Laboratory, Chukyo University

WinはCygwin上で動作

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201327

テンプレートマッチングの主な課題

1. ロバスト化
2. 高速化3. 高精度化Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201328

本日の話題

1. テンプレートマッチングの基本
2. テンプレートマッチングのロバスト化技術
3. テンプレートマッチングの高速化技術
4. 最近の取り組み紹介
参照データの戦略的削減によるマッチング～ CPTMを核として ～Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201329

ロバスト化に関する課題

対応しにくいことがある．

テンプレート

照明変動

回転

部分的隠蔽

拡大・縮小

類似物

アフィン変形

幾何学変形
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201330

ロバスト化の基本的な考え方
変動の影響が少ない特徴量で抽象化する．
画素（濃度値）同士の照合から特徴量同士の照合へ
照明変動

特徴量
画像を
抽象化して
照合する
特徴量

回転

特徴量

テンプレート類似物

特徴量の設計が重要

Hashimoto Laboratory, Chukyo University

特徴量

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201331

ロバスト化に関する主な研究例
単純な抽象化の例
画像の2値化

2値化[Tubbs1989]

その他の主な研究
1. Transformation Ring Projection
2. Local Binary Patterns
3. ３値輪郭表現
4. 定性的3値表現
5. 増分符号相関
6. 確率的増分符号相関7. 選択的正規化相関8. 方向符号照合
9. Radial Reach Correlation（Filter）
10. 部分テンプレートの幾何学的組み合わせ
11. 統計的リーチ特徴
12. Dominant Orientation Templates
13. SRFによるサンプル学習型画像照合
14. Grayscale Arranging Pairs
15. 固有値分解テンプレート法
16. Diverse Density に基づくキーポイント抽出法

Hashimoto Laboratory, Chukyo University[Tang1991][Ojala1994][Sumi1995][Yamaguchi2002][Murase2000][Mita2005][Satoh2001][Ullah2001][Sato2003][Okuda2004][Iwata2009][Hinterstoisser2010][Ozaki2010][Zhao2011][Kouotaki2011][Yuasa2013, Yoshioka2011]

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201332

3値輪郭表現[Sumi1993]

DoG（Difference of Gaussian）フィルタ＋ ３値化（－１，０，＋１） の組み合わせ
輪郭付近の有用情報を保持したままデータ圧縮 （Band-pass特性）

原画像

DOGカーネル

３値化

３値輪郭表現

参考文献：鷲見和彦, 橋本学, 3値化BLOBを中間表現に持つシーン認識手法, 情報処理学会論文誌, Vol.34, No.10, pp.2085-2095, 1993.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201333

増分符号相関（ISC : Increment Sign Correlation）
水平方向の輝度値の増減を2値符号で表現し，画像化する．

[Murase2000]

増分符号画像b(i, j )Image A10

if f (i 1, j )otherwisef (i, j ) 0

Image B
影や日照による
輝度変化

250
200

増分符号画像（Image A）

Image B

輝 150
度 100
値
50

Image A00

5

10 15 20 25 30 35 40 45 50 55 60 65 70

座標

輝度プロファイルの比較

増分符号画像（Image B）
符号の一致性を評価することで照明変動にロバスト

参考文献：村瀬一朗，金子俊一，五十嵐悟，“増分符号相関によるロバスト画像照合” ，信学論D-II，Vol.J83-D-II，No.5，pp.1323-1331，2000.
使用データ：PETS2001 DATASET3
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201334

増分符号表現[Murase2000]

増分符号画像元画像
濃度ヒストグラムシェーディング
大きさ＝45濃度ヒストグラムシェーディング
大きさ＝75濃度ヒストグラム

参考文献：村瀬一朗，金子俊一，五十嵐悟，“増分符号相関によるロバスト画像照合” ，信学論D-II，Vol.J83-D-II，No.5，pp.1323-1331，2000.
使用データ：PETS2001 DATASET3
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201335

方向符号照合（OCM : Orientation Code Matching）[Ullah2001]

輝度勾配の方向を量子化して符号化
5
8

3
4
7
8

2
5

4 3

3
8
4
2

6

9
8

7

1
0

8

15
9
10

5
4

11
8

11 12

3
2

13

8
0

15
8

14

13
8

入力画像

7
4

方向符号（16分割の場合）

方向符号画像

参考文献：F. Ullah, S. Kaneko, and S. Igarashi, “Orientation code matching for robust object search”, IEICE Trans. Inf. & Syst., Vol.E84-D,
No.8, pp.999–1006, 2001.
使用データ：PETS2001 DATASET3
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201336

方向符号表現
注目画素の近傍情報をもとに，勾配方向をコード化

Gif (i , j )
,
i

Gi

Gj

(i, j )Gjf (i, j )jtan 1 (G j / Gi )(i, j )c(i, j )N

Hashimoto Laboratory, Chukyo University

if Gi（画像の1次微分値）（最大濃度勾配方向）

Gjotherwise（コントラスト確保のためのしきい値）2
N（方向分割ピッチ）

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201337

Radial Reach Correlation[Satoh2003]

各画素から8方向に伸ばした腕上の濃度変化符号をコード化
1. しきい値以下または以上になるまで腕を伸ばす．
2. 濃度変化の符号を2値で表現し，8ビットの各ビットに割り当てる．

＋

＋
5

6

7
0
4
3 2 1

-

＋
＋

7
1

6
1

5
0

4
0

3
0

2
1

1
1

0
1

各画素ごとに濃度変化符号を格納→テクスチャを表現（リーチ長情報は，コード列には載っていない）＋
参考文献：佐藤雄隆，金子俊一，丹羽義典，山本和彦，“Radial Reach Filter (RRF) によるロバストな物体検出，”信学論(D-II)，vol.J86-D-II，no.5，
pp.616-624，May 2003.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

38

DOT : Dominant Orientation Templates[Hinterstoisser2010]

テンプレートと入力画像それぞれを小領域に分割し，主勾配方向を求めてコード化．これらの一致度をもとに照合する．
勾配方向は8種類（7方向+無勾配フラグ）に量子化して，1/0 で表現．
ビット演算による高速照合．
７

小領域に分割された入力画像 （例：小領域の大きさは７ｘ７）７

4つの小領域に分割された
テンプレート：入力画像の主勾配方向（１つ）：テンプレートの主勾配方向（複数可）：マッチした勾配方向：ミスマッチした勾配方向

参考文献： S. Hinterstoisser, V. Lepetit, S. Illic, P. Fua, N. Navab, “Dominant Orientation Templates for Real-Time Detection of Texture-Less
Objects”, Computer Vision and Pattern Recognition （CVPR）, pp.2257–2264, 2010.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201339

本日の話題

1. テンプレートマッチングの基本
2. テンプレートマッチングのロバスト化技術
3. テンプレートマッチングの高速化技術
4. 最近の取り組み紹介
参照データの戦略的削減によるマッチング～ CPTMを核として ～Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201340

高速化の基本的な考え方
TMの基本ステップ

3つのアプローチ

Step 1： 類似度マップを生成
1. 計算量が少ない類似性尺度

SCORR(dx , d y ){(g(dx i, d y(g(dx i, d yj)j)g )( f (i, j)

2g)

類似度マップf )}( f (i, j)

2f)

2. 全ての画素を使わない（画素の取捨選択）

3. 類似度マップ作成を省略する≒山登り探索型

Step 2： 類似度マップからピーク位置を検出
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201341

高速化に関する研究例
計算量が小さい類似度尺度を採用する
差の絶対値の総和（相違度）

SSAD(d x , d y )| g (d x i, d yj)f (i, j) |類似度マップ作成を省略する
1.
2.
3.

SSDA（類似度計算の打ち切り）
ピラミッド探索（Coarse-to-Fine探索）
アクティブ探索[Barnea1972][Tanimoto1975, Rosenfeld1977][Murase1998]

すべての画素を使わない （有効画素の選択）
1. Chamfer Matching
2. Oriented Chamfer Matching
3. Boosting Chamfer Matching
4. 輪郭情報を用いたマッチング
5. 自己相関類似度マップを元にした画素選択
6. 分散階層化テンプレートマッチング
7. 全画素使用時と同等性能になる画素選択
8. 粗テンプレートマッチング
9. 顕著点同士の照合
10. 独自性の高い周波数成分の利用
11. 濃度共起確率を用いた画素選択
12. 画像間共起確率を用いた安定画素選択
13. 周辺の偽物体との識別性を考慮した画素選択
Hashimoto Laboratory, Chukyo University[Barrow1977][Jamie2008][Ma2010][Hashimoto1991][Hashimoto1995][Hirooka1997][Saito2001][Matsubara2005][Lee2011][Wu2011][Hashimoto2011][Hashimoto2011, Saito2013][Sakuramoto2012]

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201342

Sequential Similarity Detection Algorithm[Barnea1972]

相違度の累積値がしきい値を超えた場合，以降の累積を中止
しきい値は，それまでに現れた相違度の最小値として随時更新
最適解が保証される．
SSAD(d x , d y )| g (d x i, d yj)f (i, j) |相違度： SADやSSDを利用する．

残差（これをしきい値と比較する．しきい値は小さい方がよい．）

相違度

相違度

テンプレート画像 f

7000000
6000000
5000000
4000000
3000000
2000000
1000000
0

しきい値
削減
0

入力画像 g

300

600

900

1200 1500 1800

計算回数

参考文献：D.I. Barnea, and H.F. Silverman, “A class of algorithms for fast digital image registration”, IEEE Trans. on Computers, Vol.C-21,
No.2, pp.179-186, 1972.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201343

SSDA法の実装上の工夫①打ち切りしきい値制御・・・その時点での最小残差を次回からのしきい値とする．
相違度A
相違度B

相違度Bが大局的な解であるためには以前の局所解（相違度A）より小さい相違度を取る必要がある．

テンプレート画像

入力画像②渦巻き探索・・・画像の中心部から渦巻き状に探索
検出対象は画像の中央部にあることが多いと仮定する．
探索の早い段階で解が見つかる
ので，しきい値の降下速度が速くなり，打ち切り時刻も早まる．

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

44

SSDA法の関連研究[Hashimoto1991]

残差累積型SSDAを，増加型類似度にも適用できるように拡張
S (k )N

M ( f (k ), g (k ))

M

k 1

1

f と g が一致したとき

0

それ以外のときS(k)1.0

k=N の時点の類似度を予測：
k=k1 のときに●であったなら，それ以降の全ての点がマッチしてもこの類似度を超えることはない．
→打ち切るかどうかを判断する．
0.0

k1

N

k

出典：橋本，鷲見，坂上，川戸，“輪郭点情報を用いた高速テンプレートマッチングアルゴリズム”，電子情報通信学会論文誌 D-II, Vol.J74-D-II, No.10,
pp.1419-1427, 1991.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201345

ピラミッド探索（粗精探索）
低解像度画像で探索を開始し，その結果近傍のみで高解像度探索をおこなう．（Coarse-to-Fine探索）[Tanimoto1975][Rosenfeld1977]

粗サーチ
１／４
中サーチ

１／２

精サーチ
テンプレート

原画像（１／１）
入力画像

実装においては，ステージ数に加え，各ステージでの探索範囲，候補数，検出しきい値の調整が必要．
粗サーチでは「全画素＋山登り法」，精サーチでは「エッジ＋総当たり法」で探索するなどの戦略が考えられる．
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201346

アクティブ探索法[Murase1998]

色ヒストグラムの代数的な性質を利用した高速化手法．
ある位置での計算済みの類似度をもとに，その近傍について，類似度を計算すべきかどうかを判定し，不要ならば省略する．
例：領域Aの類似度 SAM が計算済みのとき，領域Bの計算要否を判定する．
M

A
S AM

S AM ：AとMの類似度値
S BM ：BとMの類似度値
A B ：AとBの共通領域
R：領域Rの面積（画素数）

S BM

B

Step1: SAM および A と B の位置関係から，Bにおける類似度 SBM の上限値 SUP を計算する．

SUP

min S AM A , A

B

B A

B

Step2: もし SUP が，探索開始以降に得られている最大類似度より大きければ，SBM を新たに計算する価値がある．そうでなければ，SBM の計算を省略してよいということになる．
参考文献：村瀬洋, V.V.Vinod, “局所色情報を用いた高速物体探索―アクティブ探索法―”, 信学論D-II, Vol.J81-D-II, No.9, pp.2035-2042, 1998.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201347

アクティブ探索法の効果

検出結果

Hashimoto Laboratory, Chukyo University

探索点（黒画素は類似度が計算された部分．白画素は省略
された部分．）

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

48

高速化に関する研究例
計算量が小さい類似度尺度を採用する
差の絶対値の総和（相違度）

類似度マップ作成を省略する
1.
2.
3.

SSDA（類似度計算の打ち切り）
ピラミッド探索（Coarse-to-Fine探索）
アクティブ探索[Barnea1972][Tanimoto1975, Rosenfeld1977][Murase1998]

すべての画素を使わない （有効画素の選択）
1. Chamfer Matching
2. Oriented Chamfer Matching
3. Boosting Chamfer Matching
4. 輪郭情報を用いたマッチング
5. 自己相関類似度マップを元にした画素選択
6. 分散階層化テンプレートマッチング
7. 全画素使用時と同等性能になる画素選択
8. 粗テンプレートマッチング
9. 顕著点同士の照合
10. 独自性の高い周波数成分の利用
11. 濃度共起確率を用いた画素選択
12. 画像間共起確率を用いた安定画素選択
13. 周辺の偽物体との識別性を考慮した画素選択
Hashimoto Laboratory, Chukyo University[Barrow1977][Jamie2008][Ma2010][Hashimoto1991][Hashimoto1995][Hirooka1997][Saito2001][Matsubara2005][Lee2011][Wu2011][Hashimoto2011][Hashimoto2011, Saito2013][Sakuramoto2012]

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201349

Chamfer Matching[Barrow1977]

エッジと距離変換を用いた高速マッチング手法
相違度の勾配情報から探索の方向と移動量を決定

エッジ画像

0
0
0
1
0
0

0
0
0
1
0
0

0
0
0
1
0
0

0
0
1
0
0
0

0
1
0
0
0
0

1
0
0
0 距離
変換
0
0
距離変換画像

2
2
1
0
1
2

2
1
1
0
1
2

1
1
0
1
1
2

1
0
1
1
2
2

0
1
1
2
2
3

相違度

相違度

S
テンプレートエッジ画像 TE

3
2
1
0
1
2

探索ウインドウの移動
距離変換画像 IDT

N 1M 1TE (i, j ) I DT (i, j )j 0 i 0探索方向と移動量の推定により，探索効率を向上

参考文献：H. Barrow, J. Tenenbaum, R. Bolles and H. Wolf, “Parametric correspondence and chamfer matching: Two new techniques forimage matching”, In Int’l Joint Conf. of Artif. Intel., pp. 659–663, 1977.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201350

輪郭テンプレートマッチング[Hashimoto1991]

認識対象の輪郭のみを1次元アレイに格納して使用．
エッジ画像の重み付き膨張と方向勾配コードの利用により，信頼性を確保．
テンプレート全画素を用いる手法と比べて，約20倍の高速化．

参考文献：橋本，鷲見，坂上，川戸，“輪郭点情報を用いた高速テンプレートマッチングアルゴリズム”，電子情報通信学会論文誌 D-II, Vol.J74-D-II,
No.10, pp.1419-1427, 1991.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201351

輪郭テンプレートマッチングの応用例
ウエハ欠陥検査

位置合わせ
差異検出

エッジマッチング

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201352

自己相関類似度マップをもとにした画素選択[Hashimoto1995]

全画素から少数画素を選ぶ ＝ 画素の組合せ最適化問題

128x128「最適」の定式化
類似度の分布がピーク付近で急峻
自己相関マップのピーク鮮鋭性

点数が少ない組合せ爆発の解決
例：

689
128x128C64 ≒10！

GA（遺伝的アルゴリズム）を用いて近似的に解を求める．
参考文献：橋本，鷲見，広岡，奥田，“自己相関マップ最適化に基づく分散テンプレート選択手法”，信学全大，D-604, pp.330, 1995.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201353

分散階層化テンプレートマッチング[Hirooka1997]

ピラミッドマッチングを適用し，階層ごとに最適な画素群を選択
16x16画素32x32画素

64x64画素

128x128画素

25%

6.4%

1.5%

0.4%

4階層全体としての高速化は，従来比 約40倍

参考文献：M. Hirooka, K. Sumi, M. Hashimoto, H. Okuda, S. Kuroda, “Hierarchical Distributed Template Matching”, Proceeding of SPIE
Symposium on Electronic Imaging & Science and Technology, Vol.3029, pp.176-182, 1997.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201354

粗テンプレートマッチング
画像に2種類のモデルを仮定し，各々の場合に応じてテンプレート点を選択する．

[Matsubara2005]

連続領域モデルの場合： 画像濃度分布の極大値，極小値画素を選択する．

極小点
極大点

不連続境界モデルの場合： 境界ダイポール画素を選択する．
境界に垂直な直線上の2点を選択する．

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201355

テンプレートマッチングの性能評価の観点
基本性能
1. ロバスト性（照明，アフィン，隠蔽，背景変動・・・）

2. 高速性Trade-offTrade-off

3. 精度

実用化において無視できない性能
4. 省メモリ
5. 類似度マップの探索しやすさ （研究例が少ない）
6. パラメータの少なさ，調整の容易さ
7. 汎用性（どんな画像にも対応，画像サイズ，テクスチャの多寡・・・）

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201356

テンプレートマッチング研究マップ ～ロバスト化と高速化の観点から～正規化相互相関[Rosenfeld69][Rosenfeld1969] A.Rosenfeld, "Picture Processing by Computer", Academic Press, Inc., 1969.

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201357

テンプレートマッチング研究マップ ～ロバスト化と高速化の観点から～
幾何学変形

ロバスト性向上

分離度フィルタ併用[Hayashi01]
ドライバ脇見検知(01)サブテンプレート[Li86]

Diverse Densityに基づくキーポイント抽出法[Yuasa2013]

部分テンプレート[Okuda04]

濃度変化不変尺度 汎用センサ(01)RelCom[Venkatraman10]
定性的3値表現 OCM[Ullah01]
3値輪郭表現[Yamaguchi02]
確率的増分符号[Sumi94]
標本化順位相関 [Mita06][Ryugo02]
基板位置決め(87)
印刷物検査(98)
SRF[Iwata08]
ISC[Murase00]
ロボット視覚(95)Phase Only Correlation[Kuglin75]

正規化相互相関[Rosenfeld69]

Shape Based Eigen Templates[Koutaki13]固有値分解テンプレート法[Koutaki11]

Grayscale Arranging Pairs[Zhao11]RRC[Satoh01]
大局的検証
Local Ternary Patterns[Tan10][Hashimoto99] Color Invariance 回転不変OCM
Local Quantized Patterns[Geusebroek01][Ullah04]
LBP[Ojala94]
Parametric Template Vector[Hussain12][Lin08]
Rotation Invariant Phase Only Correlation
サンプル学習SRF
回転照合[Ritter96]
Selective Correlation Coefficient (SCC)[Goshtasby85][Ozaki10][Satoh01]
SCC高速化[Itoh04]
DOT[Hinterstoisser10]
Transformation Ring Projection[Tang01]
パラメトリックテンプレート [Tanaka00]

前処理最適化
解像度制御[Muramatsu00] 探索しきい値最適化[Oomori09][Kanatani02]
Coarse-to-Fine
アクティブ探索[Murase98]
探索回数制限2段探索[Tanimoto75]
Multilevel Successive Elimination Algorithm[Goshtasby84][Rosenfeld77]
探索順序制御[Gao00]Fine Granularity Successive Elimination[Vanderbrug77][Nagel72]
Successive Elimination Algorithm (SEA)[Zhu05]
CORR単調関数化[Barnea95]
Strict Multilevel Successive Elimination Algorithm
探索打ち切り(SSDA)[Ikeda00][Song07][Barnea72]
Enhanced Bounded Correlation
Block Sum Pyramid Algorithm[Mattoccia08][Lee97]
Chamfer Matching
地表画像分析(02)[Barrow77]
H/W化[Muramatsu00] ブロック単位選択
参照データ数削減
探索信頼度利用 [Kaneko02][Saito01]
輪郭1次元テンプレート
共起確率テンプレート[Hashimoto91] ステレオビジョン(97)粗テンプレート[Hashimoto09]
高識別テンプレート
データ[Matsubara05]2値照合
ウエハ外観検査(91)
基板位置決め(99)[Sakuramoto12]
形式変換[Tubbs89]
汎用センサ(96)モデル照合度利用
自己相関値利用安定画素テンプレート[Cristinacce06]
ランレンクス[Hashimoto95][Saito13][Margalit88]
階層化離散点マッチング[Hirooka96]
探索順序制御[Gold84]

照合の高速化
TopicsCPU

OpenCV－α版公開

MIST
OpenCV1.0

OpenCV2.0
Kinect発売

Motorola 68000（16bit）
Intel 8080（8bit）
Intel 80386（32bit） Intel Pentium（32bit）
Intel Core 2 Duo（32bit）
Intel 80286（16bit）
Motorola 6800（8bit）
Intel Pentium III（32bit） Intel Core 2 Quad（32bit）
Intel i486（32bit）
Intel 8086（16bit） Motorola 68020（32bit）
AMD Am386（32bit）
Intel Core i7（32bit）
AMD Athlon 64（32bit）

特徴点とその照合

Moravec[Moravec79]

HarrisSUSAN
SIFT[Harris88] [Smith97] [Lowe99]

Hashimoto Laboratory, Chukyo University

PCA-SIFT[Ke04]SURF
FAST[Bay06] [Rosten06]

Intel Core i7（64bit）
AMD Fusion（64bit）

BRIEF
BRISK
CARD
FREAK
[Calonder10] [Leutenegger11] [Ambai11] [Alahi12]

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201358

本日の話題

1. テンプレートマッチングの基本
2. テンプレートマッチングのロバスト化技術
3. テンプレートマッチングの高速化技術
4. 最近の取り組み紹介
参照データの戦略的削減によるマッチング～ CPTMを核として ～Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201359

Intelligent Sensing Laboratory, Chukyo University

最近の取り組み紹介

参照データの戦略的削減によるマッチング

戦略的データ削減によるさまざまな物体認識

濃度共起確率に基づく
画素数削減とテンプレート
マッチングの高速化（CPTM）
2009～2011

Hashimoto Laboratory, Chukyo University

2次元画像照合のロバスト化・高機能化①画像間共起に基づく照明ロバスト化(2011)②周辺類似物との識別性能強化(2012)

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201361

Intelligent Sensing Laboratory, Chukyo University

濃度共起確率に基づく画素数削減とテンプレートマッチングの高速化～共起確率を用いた画素の削減～
CPTM : Co-Occurrence Probability-based Template Matching

Hashimoto, et al.：Extraction of Unique Pixels based on Co-occurrence Probability for High-speed Template Matching, ISOT2010, MVI-3, 2010.
橋本ほか： 濃度共起確率に基づくユニークな画素群を用いた高速画像マッチング，電気学会論文誌D, Vol.131, No.4, 2011.

研究の目的

目的
できるだけロバスト性を低下させずに超高速化を図る．

前提
画素単位の照合を扱う
1枚のテンプレート画像のみを使用する．

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

63

高速化の基本戦略
テンプレート画像内の全ての点を使わない．
厳選された画素だけを使用する．
テンプレート画像を代表できる画素を選択する．
＝ 独自性の高い画素

画素選択

照合

濃度発生確率に基づいて画素（群）の独自性を評価
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201364

最も簡単な濃度共起ヒストグラム （2画素の場合）
始点と終点からなるパターンを考え，濃度ペアの発生頻度を共起ヒストグ
ラム h2(p, q) として表現する （Co-occurrence matrix）．
h2 ( p, q, d)

i

O

j

d R2

vq

終点画素 Q（濃度値 q ）vp
diff (v p )pf (vq )

q

then

2

1

2

0

else
vq

vp d

q

始点画素 P（濃度値 p ）変位ベクトル d ：共起性を測る方向と距離を指定

2・・・

h2 ( p, q )

・・・

p

・・・
・・・
：

：

：

：

：
・・・

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201365

共起ヒストグラム h2 の例（発生確率分布）水平2画素の共起ヒストグラムの場合
始点
frequencyd

終点

濃度差が小さいので対角要素が大きい

データが分散

q

LSI

p

d

( 1,0)

背景画素

Parts

d

( 4,0)d( 16,0)垂直エッジ部分

前景画素( 1,0)

Hashimoto Laboratory, Chukyo Universitydd( 4,0)d( 16,0)

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201366

画素選択アルゴリズム

n画素の共起確率分布を生成
画素間の関係を変化
・方向・画素間距離複数パターンの共起確率分布を合成
画素の選ばれやすさをマップで表現
マップをもとに画素を選択
候補群からランダムに選択
類似の値をもつ画素候補が複数存在

YES

NO

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201367

実験 マッチング性能の評価

magnified(a) Parts

M=97 (0.7%)

Hashimoto Laboratory, Chukyo University(b) Rabbit

M=5 (0.05%)(c) Traffic Sign M=235 (3.0%)

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

68

Demo
使用した画素数 ＝313画素（全体の1.5%）
入力画像サイズ ＝640x480
フレームレート＝約32fps※微小回転には対応，スケーリングには未対応

Click →

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

69

物体追跡への応用
1

PRMUアルゴリズムコンテスト2010

2

3

性能評価結果4
Hashimoto Laboratory, Chukyo University

サンプル

追跡精度※
[%]

追跡成功率※[%]

処理時間（平均）[s]

1

96.2

100

0.018

2

96.0

100

0.020

3

98.3

100

0.014

4

94.6

100

0.015

5

96.0

100

0.011

平均

96.2

100

0.016

5
第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201370

PRMUアルコンにおける追跡失敗例
非公開の評価用データ
最初の1フレーム目で追跡に失敗した．
テンプレート移動物体

前景画像が繰り返しパターン → ユニークな画素は背景に多かった．
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201371

Intelligent Sensing Laboratory, Chukyo University

画像間共起確率に基づく
照明変動にロバストなテンプレートマッチング

・・・

M. Saito, M. Hashimoto, Robust Image Matching for Irregular Illumination Variation based on Spatio-Temporal Analysis of Image Intensity,
Proceeding of International Symposium on Optomechatronic Technologies (ISOT), 2012.
斎藤正孝，橋本学，濃度共起分析に基づく安定画素テンプレートを用いた照明変動にロバストな高速画像照合，電気学会論文誌C部門，
Vol.133,No.5, pp.1010-1016, 2013.

CPTMの問題点
テンプレートマッチング
全画素によるマッチング
テンプレート画像

入力画像

CPTM
少数画素による
マッチング

独自性の高い画素を抽出
共起確率1%の参照画素100倍高速多様な照明変動に追従できない
テンプレート画像1枚のみから参照画素を選択することの限界
複数のテンプレート画像から安定した参照画素を選択する
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201373

画素安定性推定のアイデア
一定間隔で切り出されたテンプレート画像
類似

類似した値 -> 安定

同一座標の画素相違

類似していない値 -> 不安定

断面図

対角線

p1

p2

投票

同一座標

正規分布
近似

p1

p2

(p1, p2)
画像間共起ヒストグラム

平均 μ

p1

[kita2010]
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201374

安定かつ独自画素の選択アルゴリズム
ft 4

ft 3

ft 2

ft 1

ft

テンプレート
画像群(1) CPTM法(2) 提案手法
hi

hi

hi

hi

画像間共起
ヒストグラム画像間共起
ヒストグラム
S

S

安定率

S

hs
S

安定率
空間共起確率マップ
M s (i, j )安定率マップ M t (i, j )時間的安定性

空間共起
ヒストグラム

時空間共起確率マップ M ts (i, j )（選ばれ易さマップ）

空間的独自性

空間的に独自性が高くかつ時間的に安定した参照画素を選択可能
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201375

実験に用いた連続写真（プリント基板）+ artificial regular disturbanceHashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201376

関連手法との比較
参照画素数[pixel](1) SSD
26825(2) ZNCC
26825(3) ISC
26680(4) SIFT
27 [point](5) SURF
27 [point](6) Random
27(7) Gradient27(8) Canny
27(9) IRFET（事前にコントラスト拡張）
27(10) CPTM
27(11) Stability
27(12) Proposed method
27
画素選択方法

認識率[%]
61.2
100.0
100.0
94.2
84.5
68.1
85.4
88.6
88.6
69.5
92.8
97.7

処理時間[msec]
5896
8829
3806
2044
628
15
15
15
15
15
15
15

※CPU：Intel®CORE™i7（2.80GHz），システムメモリ：8GB，OS：Windows 7

提案手法は同じ参照画素数を用いた手法の中で最も認識成功率が高い
全画素を用いた手法と比べて200倍以上高速
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201377

物体検出結果（LSIチップ部品）
従来法（CPTM法）

提案手法

Click to demo.
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201378

参照画素数と認識成功率の関係
100

認識成功率 Pｒ [%]

90
80
70
60
50

テンプレート画像例

40(1) ISC-CPTM

30(2) CPTM

20(3) Stability

10(4) Proposed method

0
10

100

1000

参照画素数 M [pixel]

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201379

汎用性の評価(a) QFP IC(b) セラミック DIP IC

認識成功率 [%]

画素数 [pixel](画素割合 [%])

CPTM

提案手法

(a) QFP IC

45 (0.3)

61.0

93.5

(b) Ceramic DIP IC

33 (0.3)

60.0

99.1

(c) Metal plate

67 (0.4)

73.0

94.3

(d) Reflective label

25 (0.1)

68.3

91.3

対象物体

(d) 反射性ラベル(c) 金属部品

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

80

物体検出結果（食品ラベル）

従来法（CPTM）
Hashimoto Laboratory, Chukyo University

提案手法
第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201381

Intelligent Sensing Laboratory, Chukyo University

識別に有効な画素を用いる
テンプレートマッチング

櫻本，斎藤，橋本，対象物と類似物の識別性能を最大化する画素群を用いた高速テンプレートマッチング，第15回画像の認識・理解シンポジ
ウム（MIRU2012），IS1-75, 2012/8．
櫻本，斎藤，橋本，対象物体の顕著性分析による周辺類似物との分離度を最大化する高速物体検出，DIA2012, pp.44-49, 2012/3.

課題
紛らわしい類似物に囲まれた目的物体の検出

対象物

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201383

基本アイデア
１．テンプレート画像中からごく少数の画素群を選択
処理速度向上選択
109×91画素

100画素

２．対象物のみを特徴づける画素群を選択
識別性能向上

参照画素群
入力画像

入力画像

（周辺物が対象と似ていない場合）

Hashimoto Laboratory, Chukyo University

参照画素群（周辺物が対象と似ている場合）

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201384

識別に有効な画素選択アルゴリズム

候補選択
テンプレート画像
100×100

候補画素群

サンプル画像群

繰り返し（GA利用）
ポジティブ
サンプル群

ネガティブ
サンプル群

参照画素群の識別性能を評価
最適参照画素群
50画素
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201385

識別性能の評価
頻度

D ： クラス分離度…
ポジティブサンプル群

参照画素群
を用いて類
似度を計算

ネガティブ
サンプル群

Cn

…

w1

S

重複面積
Hashimoto Laboratory, Chukyo University

類似度

Cp ： ポジティブサンプル群の代表値
Cn ： ネガティブサンプル群の代表値

識別性能を表す目的関数

F

Cp
S ： 重複面積

ネガティブサンプル群

1

ポジティブ
サンプル群

w2 D

最大化

クラス分離度

w1,w2 は重み係数

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

86

実験結果

パズルのピース

カード

将棋の駒

M=30点(0.3%)

M=30点(0.5%)

M=30点(0.3%)

検出成功例

検出成功例

検出成功例

手法

パズルのピース

カード

将棋の駒

提案手法

99%（99枚/100枚）

99%（99枚/100枚）

99%（99枚/100枚）

全画素法

93%（93枚/100枚）

100%（100枚/100枚）

100%（100枚/100枚）

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

87

実験結果

109×91

実験画像（600×400）
1.0

0.8

画素選択方法

参照画素数[pixel]

認識率
[%]

処理時間
[sec]

(1) 全画素法

9919

60.0

1985

(2) SIFT[3]60 [point]

1.0

478

(3) SURF[4]60 [point]

0.0

253

(4) ランダム A

500

39.0

109

(5) ランダム B

150

71.0

32

(6) CPTM法

500

76.0

109

(7) CLAFIC法

60[次元]688769(8) 提案手法

60

94

0.008

再現率 Rr※CPU：Intel®CORE™i7（3.40GHz），システムメモリ：16GB
0.6

全画素法
ランダム A

0.4

ランダム B
0.2

CPTM
CLAFIC法 （部分空間法）

0.0
0.0

0.2

0.4

0.6

適合率 RpHashimoto Laboratory, Chukyo University

0.8

1.0

提案手法

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201388GA（遺伝的アルゴリズム）のふるまい

類似物

対象物
1

1

0

0

-1

-1
(a) 1世代目(a) 1世代目(c) 200世代目(b) 100世代目(d) 400世代目

参照画素群（30画素）(b) 100世代目

1

1

0

0

-1

-1
(c) 200世代目(d) 400世代目

類似度マップHashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201389

関連手法との比較

・・・徐々に周辺物を増やした場合（500画像）

Processing time 0.008 [sec]Processing time 8769 [sec]Processing time 0.008 [sec]Processing time 1.985 [sec]Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201390

戦略的データ削減によるさまざまな物体認識
戦略的データ削減
戦略的画素削減
濃度共起確率に基づく
画素数削減とテンプレート
マッチングの高速化（CPTM）
2009～2011

2次元画像照合のロバスト化・高機能化①画像間共起に基づく照明ロバスト化(2011)②周辺類似物との識別性能強化(2012)③画像の周波数構造に基づく画素選択(2012)④投票処理に基づくCPTMの回転対応(2013)⑤異種画像統合による高信頼物体認識(2013)⑥CPTMの3値増分符号化(2012)

3次元物体認識

画素以外への適用①CPTMの低テクスチャ画像への拡張(2012)②ユニークな線素を用いた物体認識(2012)③特徴的局所領域に基づく物体認識(2012)④特徴的ベクトルペアマッチング（VPM法）(2012)⑤準リアルシーン学習によるVPMの高信頼化(2013)①SIFTキーポイントの効果的削減(2011)②剛体追跡のためのサブトラッカ選択(2011)

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201391

関連する主なソフトウェアライブラリ
OpenCV
ダウンロードhttp://opencv.jp/download

機能
テンプレートマッチング
SSD，正規化相関
cvMatchTemplate（）
ヒストグラム照合
cvCalcBackProjectPatch（）
Chamfer Matching
chamerMatching（）
物体検出
HaarLike特徴量を用いた顔検出 CascadeClassifier（）
HOG特徴量を用いた人検出
HOGDescriptor（）
特徴点検出
Harris
最小固有値
FAST
STAR

Hashimoto Laboratory, Chukyo University

cvCornerHarris（）
cvCornerMinEigenVal（）
FastFeatureDetector（）
StarFeatureDetector（）

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201392

関連する主なソフトウェアライブラリ
SIFT
SURF
MSER
ORB
BRIEF
FREAK

SiftFeatureDetector（）
SiftDescriptorExtractor（）
SurfFeatureDetector（）
SurfDescriptorExtractor（）
MserFeatureDetector（）
OrbFeatureDetector（）
OrbDescriptorExtractor（）
BriefDescriptorExtractor（）
FreakDescriptorExtractor（）

MIST
ダウンロードhttp://mist.murase.m.is.nagoya-u.ac.jp/trac/wiki/Download
機能SSDA
ssda_search（）
POC
mist::poc（）
アクティブ探索active_search（）

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201393

参考文献 （ロバスト化）①[Kuglin1975] C.D.Kuglin, and D.C.Hines, "The phase correlation image alignment method", Proceedings of International Conference on Cybernetics andSociety, pp.163-165, 1975.
[Goshtasby1985] A.Goshtasby, "Template Matching in Rotated Images", IEEE Transactions on Pattern Analysis and Machine Intelligence（PAMI）, Vol.PAMI-7,
No.3, pp.338-344, 1985.
[Li1986] X.Li, M.Ferdousi, M.Chen, and T.T.Nguyen, "Image matching with multiple templates", Proceedings of Computer Vision and Pattern Recognition（CVPR）, pp.610-613, 1986.
[Ritter1996] G.X.Ritter, and J.N.Wilson, "Handbook of Computer Vision Algorithms in Image Algebra", CRC Press Inc, 1996.
[Tang1991] Y.Y.Tang, H.D.Cheng, and C.Y.Suen, "Transformation-ring-projection (TPR) algorithm and its VLSI implementation", International Journal ofPattern Recognition and Artificial Intelligence, Vol.5, pp.25-56, 1991.
[Ojala1994] T.Ojala, M.Pietikäinen, and D.Harwood, "Performance evaluation of texture measures with classification based on Kullback discrimination of
distributions", Proceedings of International Conference on Pattern Recognition (ICPR), Vol.I, pp.582-585, 1994.
[Hashimoto1999] 橋本学, 黒田伸一, 鷲見和彦, 宇佐美照夫, 仲田周次, "シーン仮説と入力画像との大局的画像整合性評価に基づく複数物体の認識", 電子
情報通信学会論文誌D-II, Vol.J82-D-II, No.12, pp.2288-2297, 1999.
[Tanaka2000] 田中弘一, 佐野睦夫, 大原秀一, 奥平雅士, "パラメトリックテンプレート法とその高精度ロバストマッチングへの応用", 電子情報通信学会論文誌
D-II, Vol.J83–D–II, No.4, 2000.
[Muramatsu2000] 村松彰二, 大塚裕史, 小林芳樹, 清水英志, "テンプレートマッチングの高速化戦略とGAによる最適化"，電子情報通信学会D-II, Vol.J83-DII, No.6, pp.1487-1497, 2000.
[Murase2000] 村瀬一朗, 金子俊一, 五十嵐悟, "増分符号相関によるロバスト画像照合", 電子情報通信学会論文誌D-II, Vol.J83–D–II, No.5, pp.1323–1331,
2000.
[Kaneko2002] S.Kaneko, I.Murase, and S.Igarashi, "Robust image registration by increment sign correlation", Transactions on Pattern Recognition（PR）,
Vol.35, No.10, pp.2223–2234, 2002.
[Hayashi2001] 林健太郎, 橋本学, 鷲見和彦, "頑健性と精緻性を備えた顔特徴点追跡による顔方向推定", 電子情報通信学会論文誌D-II, Vol.J84-D-II, No.8,
pp.1762-1771, 2001.
[Geusebroek2001] J.M.Geusebroek, R.V.D.Boomgaard, and A.W.M.Smeulders, "Color Invariance", IEEE Transactions on Pattern Analysis and MachineIntelligence（PAMI）, Vol.23, No.12, pp.1338-1350, 2001.
[Satoh2001] 佐藤雄隆, 金子俊一, 五十嵐悟, "選択的正規化相関によるロバスト画像照合", 電気学会論文誌C, Vol.121, No.4, pp.800–807, 2001.
[Ullah2001] F.Ullah, S.Kaneko, and S.Igarashi, "Orientation Code Matching for Robust Object Search", IEICE Transactions on Information and Systems,
Vol.E84–D, No.8, pp.999–1006, 2001.
[Satoh2001] 佐藤雄隆, 金子俊一, 五十嵐悟, 丹羽義典, 山本和彦, "Radial Reach Filterによるロバスト物体検出", 電子情報通信学会技術研究報告, Vol.101,
No.204, pp.15-22, 2001.
[Satoh2002] Y.Satoh, H.Tanahashi, C.Wang, S.Kaneko, Y.Niwa, and K.Yamamoto, "Robust Event Detection by Radial Reach Filter（RRF）"，Proceedings ofInternational Conference on Pattern Recognition （ICPR）, Vol.2, pp.623-626, 2002.

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201394

参考文献 （ロバスト化）②[Satoh2003] 佐藤雄隆, 金子俊一, 丹羽義典, 山本和彦, "Radial Reach Filter（RRF）によるロバストな物体検出", 電子情報通信学会論文誌D-II, Vol.J86–D–II,
No.5, pp.616-624, 2003.
[Ryugo2002] 流郷達人, 宮本敦, 金子俊一, 五十嵐悟, "標本化順位相関に基づくロバスト画像照合", 画像電子学会誌, Vol.31, No.3, pp.363-369, 2002.
[Yamaguchi2002] 山口修，福井和広, "定性的3値表現に基づく画像マッチング" ,電子情報通信学会技術研究報告, Vol.102, No.156, pp.23-30, 2002.
[Okuda2002] H.Okuda, M.Hashimoto, and K.Sumi, "Robust Picture Matching Using Optimum selection of Partial Template", Proceedings of the SICE Annual
Conference, Vol.1, pp.550-552, 2002.
[Okuda2004] 奥田晴久, 橋本学, 鷲見和彦, 佐々木和則, "部分テンプレート組み合わせ最適化に基づくロバスト画像照合", 電気学会論文誌C, Vol.124, No.3,
pp.629-636, 2004.
[Itoh2004] 伊藤誠也, 金子俊一, "選択的正規化相関による高速なロバスト画像照合", 電気学会論文誌C, Vol.124, No.3, pp.613-620, 2004.
[Ullah2004] F.Ullah, and S.Kaneko, "Using orientation codes for rotation-invariant template matching", Transactions on Pattern Recognition（PR）, Vol.37,
No.2, pp.201–209, 2004.
[Mita2006] T.Mita, T.Kaneko, and O.Hori, "A Probabilistic Approach to Fast and Robust Template Matching and its Application to Object Categorization",
Proceedings of International Conference on Pattern Recognition（ICPR）, Vol.2, pp.597-601, 2006.
[Mita2006] 三田雄志, 金子敏充, 堀修, "個体差のある対象の画像照合に適した確率的増分符号相関", 電子情報通信学会論文誌D-II, Vol.J88–D–II, No. 8,
pp.1614–1623, 2006.
[Lin2008] Y.H.Lin, and C.H.Chen,"Template matching using the parametric template vector with translation, rotation and scale invariance", Transactions on
Pattern Recognition（PR）, Vol.41, No.7, pp.2413–2421, 2008.
[Iwata2008] 岩田健司, 佐藤雄隆, 尾崎竜史, 坂上勝彦, "統計的リーチ特徴法に基づくロバスト背景差分", 電子情報通信学会論文誌D, Vol.J92-D, No.8,
pp.1251-1259, 2009.
[Venkatraman2010] V.Venkatraman, and F.M.Porikli, "RelCom: Relational combinatorics features for rapid object detection", Proceedings of Computer Vision
and Pattern Recognition Workshops, pp.23-30, 2010.
[Ozaki2010] 尾崎竜史, 佐藤雄隆, 岩田健司, 坂上勝彦, "統計的リーチ特徴法に基づくサンプル学習型画像照合", 電気学会論文誌C, Vol.130, No.9, pp.16221629, 2010.
[Hinterstoisser2010] S.Hinterstoisser, V.Lepetit, S.Ilic, P.Fua, and N.Navab, "Dominant Orientation Templates for Real-Time Detection of Texture-Less
Objects", Proceedings of Computer Vision and Pattern Recognition （CVPR）, pp.2257-2264, 2010.
[Hinterstoisser2011] S.Hinterstoisser, S.Holzer, C.Cagniart, S.Ilic, K.Konolige, N.Navab, and V.Lepetit, "Multimodal Templates for Real-Time Detection of
Texture-less Objects in Heavily Cluttered Scenes", International Conference on Computer Vision（ICCV）, 2011.
[Tan2010] X.Tan, and B.Triggs, "Enhanced Local Texture Feature Sets for Face Recognition Under Difficult Lighting Conditions", IEEE Transactions on Image
Processing, Vol.19, pp.1635-1650, 2010.
[Zhao2011] X.Zhao, Y.Satoh, H.Takauji, S.Kaneko, K.Iwata, and R.Ozaki, "Object detection based on a robust and accurate statistical multi-point-pair model",Transactions on Pattern Recognition（PR）, Vol.44, No.6, pp.1296–1311, 2011.

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201395

参考文献 （ロバスト化）③[Koutaki2011] 上瀧剛, 内村圭一, "固有値分解テンプレートによる高精度な画像照合", 電気学会論文誌C研究開発レター, Vol.131, No.1, pp.237–238, 2011.
[Koutaki2011] 上瀧剛, 内村圭一, "明るさ変動および雑音に頑健な固有値分解テンプレート法", 電気学会論文誌C, Vol.131, No.9, pp.1625–1632, 2011.
[Hussain2012] S.U.Hussain, and B.Triggs, "Visual Recognition using Local Quantized Patterns", Proceedings of European Conference on Computer Vision（ECCV）, pp.716-729, 2012.
[Yuasa2013] 湯浅圭太, 和田俊和, 大池洋史, 坂田淳, "Diverse Densityに基づく画像データ検索用キーポイント抽出法について", コンピュータビジョンとイメー
ジメディア（CVIM）, Vol.2013-CVIM-185, No.14, pp.1-6, 2013.
[Koutaki2013] G.Koutaki, and K.Uchimura, "Occlusion Robust Pattern Matching Using Shape Based Eigen Templates", IEEJ Transactions on Electronics,
Information and Systems Vol.133, No.1, pp.134–141, 2013.

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201396

参考文献 （高速化）①[Barnea1972] D.I.Barnea, and H.F.Silverman, "A Class of Algorithms for Fast Digital Image Registration", IEEE Transactions on Computers, Vol.C-21, No.2,
pp.179-186, 1972.
[Nagel1972] R.N.Nagel, and A.Rosenfeld, "Ordered Search Techniques in Template Matching", Proceeding of the IEEE, Vol.60, No.2, pp.242-244, 1972.
[Tanimoto1975] S.L.Tanimoto, and T.Pavlidis, "A Hierarchical Data Structure for Picture Processing", Computer Graphics and Image Processing, Vol.4, No.2,
pp.104-119, 1975.
[Tanimoto1981] S.L.Tanimoto, "Template Matching in Pyramids", Computer Graphics and Image Processing, Vol.16, pp.356-369, 1981.
[Rosenfeld1977] A.Rosenfeld, G.J.Vanderbrug, "Coarse-Fine Template Matching", IEEE Transactions on Systems, Man and Cybernetics, Vol.7, No.2, pp.104107, 1977.
[Vanderbrug1977] G.J.Vanderbrug, and A.Rosenfeld, "Two stage template matching", IEEE Transactions on Computer, Vol.C-26, No.4, pp.384-393, 1977.
[Barrow1977] H.G.Barrow, J.M.Tenenbaum, R.C.Bolles, and H.C.Wolf, "Parametric correspondence and chamfer matching: Two new techniques for image
matching", International Joint Conference on Artificial Intelligence, Vol.2, pp.659-663, 1977.
[Gold1984] Y.I.Gold, "On The Order Of Examining Data-Points In Ssd Template Matching", Proceedings of International Conference on Pattern Recognition（ICPR）, Vol.84, pp.1077-1080, 1984.
[Goshtasby1984] A.Goshtasby, S.H.Gage, and J.F.Bartholic, "A two-stage cross correlation approach to template matching", IEEE Transactions on PatternAnalysis and Machine Intelligence（PAMI）, Vol.PAMI-6, No.3, pp.374-378, 1984.
[Tubbs1986] D.Tubbs, "A Note on Binary Template Matching, Pattern Recognition", Vol.22, No.4, pp.359-365, 1989.
[Margalit1988] A.Margalit, and A.Rosenfeld, "Reducing the Expected Computational Cost of Template Matching using Run Length Representation", Technicalreport of CfAR Univ. of MD., CAR-TR-406, 1988.
[Margalit1990] A.Margalit, and A.Rosenfeld, "Reducing the Expected Computational Cost of Template Matching using Run Length Representation", IEEE
Transactions on Pattern Recognition Letters（PRL）, Vol.11, No.4, pp.255-265, 1990.
[Sumi1994] 鷲見和彦, 三木美和子, 橋本学, 奥田晴久, "3値輪郭表現を応用した高速テンプレートマッチング", 電子情報通信学会春季全国大会, No.D-625,
pp.7:361, 1994.
[Sumi1995] K.Sumi, M.Hashimoto, H.Okuda, S.Kuroda, "Three-Level Broad-Edge Matching and its Application to Real-time Vision System", IEICE
Transactions on Information and Systems, Vol.E78-D, No.12, pp.1526-1532, 1995.
[Li1995] W.Li, and E.Salari, "Successive elimination algorithm for motion estimation", IEEE Transactions on Image Processing, Vol.4, No.1, pp.105-107, 1995.
[Hashimoto1991] 橋本学, 鷲見和彦, 坂上義和, 川戸慎二郎, "輪郭点情報を用いた高速テンプレートマッチングアルゴリズム", 電子情報通信学会論文誌D-II,
Vol.J74-D-II, No.10, pp.1419-1427, 1991.
[Hashimoto1992] M.Hashimoto, K.Sumi, Y.Sakaue, and S.Kawato, "High-Speed Template Matching Algorithm using Information of Contour Points", Systems
and Computers in Japan, Vol.23, No.9, pp.78-87, 1992.
[Hashimoto1995] 橋本学, 鷲見和彦, 広岡美和子, 奥田晴久, "自己相関マップ最適化に基づく分散テンプレート選択手法", 電子情報通信学会春季全国大会,
p.330, 1995.

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201397

参考文献 （高速化）②[Hirooka1996] 広岡美和子, 鷲見和彦, 橋本学, 奥田晴久, 黒田伸一, "階層化分散テンプレートマッチング手法", 画像の認識・理解シンポジウム（MIRU）講演
論文集, pp.II-325-330, 1996.
[Lee1997] C.H.Lee, and L.H.Chen, "A fast motion estimation algorithm based on the block sum pyramid", IEEE Transactions on Image Processing, Vol.6,
No.11, pp.1587-1590, 1997.
[Murase1998] 村瀬洋, V.V.Vinod, "局所色情報を用いた高速物体探索―アクティブ探索法―", 電子情報通信学会論文誌D-II, Vol.J81-D-II, No.9, pp.20352042, 1998.
[Muramatsu2000] 村松彰二, 小林芳樹, 高橋一哉, 清水英志, "テンプレートマッチングにおけるハードウェア化と高速化手法の開発", 電子情報通信学会論文
誌D-II，Vol.J83-D-II, No.7, pp.1667-1675, 2000.
[Gao2000] X.Q.Gao, C.J.Duanmu, and C.R.Zou, "A multilevel successive elimination algorithm for block matching motion estimation", IEEE Transactions on
Image Processing, Vol.9, No.3, pp.501-504, 2000.
[Ikeda2000] 池田光二, 吉田昌司, 中島啓介, 浜田長晴, 依田晴夫, "正規化相関演算の単調関数化による高速テンプレートマッチング", 電子情報通信学会論
文誌D-II, Vol.J83–D–II, No.9, pp.1861–1869, 2000.
[Saito2001] 斉藤文彦, "遺伝的アルゴリズムを用いた画素選択テンプレートによる画像マッチング", 電子情報通信学会論文誌D-II, Vol.J84–D–II, No.3,
pp.488–499, 2001.
[Kanatani2002] 金谷健一, 金沢靖, "テンプレートマッチングによる対応探索の自動しきい値設定法", コンピュータビジョンとイメージメディア（CVIM）, Vol.2002,
No.26, pp.23-30, 2002.
[Kaneko2002] 金子敏充, 堀修, "小領域のブロックマッチングを複数用いたロバストなオブジェクト追跡法", 電子情報通信学会論文誌D-II, Vol.J85–D–II, No.7,
pp.1188–1200, 2002.
[Kaneko2003] T.Kaneko, and O.Hori, "Feature Selection for Reliable Tracking using Template Matching", Proceedings of Computer Vision and Pattern
Recognition（CVPR）, Vol.1, pp.796-802, 2003.
[Kaneko2005] 金子敏充, 堀修, "ブロックマッチング誤差の上界に基づく追跡ブロック選択手法", 電子情報通信学会D-II, Vol.J88-D-II, No.3, pp.562-572, 2005.
[Shakunaga2005] T.Shakunaga, Y.Matsubara, and K.Noguchi, "Appearance Tracker Based on Sparse Eigentemplate", Proceeding of International Conference
on Machine Vision & Applications（MVA）, pp.13-17, 2005.
[Matsubara2005] 松原康晴, 尺長健, "疎テンプレートマッチングとその実時間物体追跡への応用", CVIM論文誌, Vol.46, No.SIG09, pp.60-71, 2005.
[Zhu2005] C.Zhu, W.S.Qi, and W.Ser, "Predictive Fine Granularity Successive Elimination for Fast Optimal Block-Matching Motion Estimation", IEEE
Transactions on Image Processing, Vol.14, No.2, 2005.
[Stefano2005] L.D.Stefano, S.Mattoccia, and F.Tombari, "ZNCC-based template matching using bounded partial correlation", IEEE Transactions on Pattern
Recognition Letters（PRL）, Vol.26, Vol.14, pp.2129-2134, 2005.
[Cristinacce2006] D.Cristinacce, and T.Cootes, "Facial Feature Detection and Tracking with Automatic Template Selection", Proceedings of IEEE
International Conference on Automatic Face and Gesture Recognition, pp.429-434, 2006.
[Song2007] Y. Song, Z. Liu, T.Ikenaga, and S.Goto, "Lossy strict multilevel successive elimination algorithm for fast motion estimation", IEICE Transactions
on Fundamentals, Vol.E90-A, No.4, pp.764-770, 2007.

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201398

参考文献 （高速化）③[Mattoccia2008] S.Mattoccia, F.Tombari, and L.D.Stefano, "Fast Full-Search Equivalent Template Matching by Enhanced Bounded Correlation", IEEE
Transactions on Image Processing, Vol.17, No.4, pp.528-538, 2008.
[Oomori2009] 大盛善啓, "スケールフリーアクティブ探索法：入力画像の解像度を適応的に変更するテンプレート照合の高速化手法", 電子情報通信学会技術報告, Vol.109, No.182, pp.69-74, 2009.

CPTM技術と関連技術[Hashimoto2009] 橋本学, 奥田晴久, 鷲見和彦, "画像の濃度共起情報に基づく画像照合のための参照画素選択手法", コンピュータビジョンとイメージメディア（CVIM）, Vol.2009-CVIM-169, No.43, pp.1-8, 2009.
[Hashimoto2010] M.Hashimoto, T.Fujiwara, H.Koshimizu, H.Okuda, and K.Sumi, "Extraction of Unique Pixels based on Co-occurrence Probability for Highspeed Template Matching", Proceeding of International Symposium on Optomechatronic Technologies (ISOT), MVI-3, 2010.
[Hashimoto2011] 橋本学, 奥田晴久, 鷲見和彦, 藤原孝幸, 輿水大和, "濃度共起確率に基づくユニークな画素群を用いた高速画像マッチング", 電気学会論文
誌D, Vol.131, No.4, pp.531-538, 2011.
[Hashimoto2011] M.Hashimoto, and M.Saito, "High-Speed and Robust Image Matching using Spatially Distinctive and Temporally Stable Pixels", Proceedingsof International Symposium on Optomechatronic Technologies（ISOT）, pp.209-214, 2011.
[Sakuramoto2012] 櫻本泰憲, 斎藤正孝, 橋本学, "類似物との識別に有効な画素群を用いた高速画像照合アルゴリズム", ビジョン技術の実利用ワークショッ
プ（ViEW）, 2012.
[Saito2012] M.Saito, and M.Hashimoto,"Robust Image Matching for Irregular Illumination Variation based on Spatio-Temporal Analysis of Image Intensity",
Proceedings of International Symposium on Optomechatronic Technologies（ISOT）, 2012.
[Saito2013] 斎藤正孝, 橋本学, "濃度共起分析に基づく安定画素テンプレートを用いた照明変動にロバストな高速画像照合", 電気学会論文誌C, Vol.133,
No.5, 2013.

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 201399

参考文献 （特徴点ベースマッチング）[Moravec1979] H.P.Moravec, "Visual mapping by a robot rover", Proceeding of International Joint Conference on Artificial Intelligence（IJCAI）, pp.598-600,
1979.
[Harris1988] C.Harris, and M.Stephens, "A combined corner and edge detector", Proceeding of the 4th Alvey Vision Conference, Vol.15, pp.147-152, 1988.
[Shi1994] J.Shi, and C.Tomasi, "Good features to track", Proceeding of IEEE Computer Vision and Pattern Recognition（CVPR）, pp.593-600, 1994.
[Smith1997] S.M.Smith, and J.M.Brady, "SUSAN - A New Approach to Low Level Image Processing", Internal Journal of Computer Vision（IJCV），Vol.23,
No.1, pp.45-78, 1997.
[Lowe1999] D.G.Lowe, "Object Recognition from Local Scale-Invariant Features", Proceeding of International Conference on Computer Vision（ICCV）, 1999.
[Matas2002] J.Matas, O.Chum, M.Urban, and T.Pajdla, "Robust wide baseline stereo from maximally stable extremal regions," pp.384-393, Proceedings ofBritish Machine Vision Conference（BMVC）, 2002.
[Lowe2004] D.G.Lowe, "Distinctive image features from scaleinvariant keypoints", Internal Journal of Computer Vision（IJCV）, Vol.60, No.2, pp.91-110, 2004.
[Ke2004] Y.Ke, and R.Sukthankar, "PCA-SIFT: A more distinctive representation for local image descriptors", Proceeding of Computer Vision and Pattern
Recognition（CVPR）, Vol.2, pp.511-517, 2004.
[Dalal2005] N.Dalal, and B.Triggs, "Histograms of Oriented Gradients for Human Detection", Proceeding of IEEE Computer Vision and Pattern Recognition（CVPR）, pp.886-893, 2005.
[Rosten2006] E.Rosten, and T.Drummond, "Machine Learning for High-speed Corner Detection", Proceeding of European Conference on Computer Vision（ECCV）, pp.430-443, 2006.
[Bay2006] H.Bay, T.Tuytelaars, and L.V.Gool, "SURF: Speeded Up Robust Features", Proceeding of European Conference on Computer Vision（ECCV）,
Vol.3951, pp.404-417, 2006.
[Calonder2010] M.Calonder, V.Lepetit, C.Strecha, and P.Fua, "BRIEF : Binary Robust Independent Elementary Features", Proceeding of European Conference
on Computer Vision（ECCV）, pp.778-792, 2010.
[Rublee2011] E.Rublee, V.Rabaud, K.Konolige, and G.Bradski, "ORB : An Efficient Alternative to SIFT or SURF", Proceeding of International Conference on
Computer Vision（ICCV）, 2011.
[Leutenegger2011] S.Leutenegger, M.Chli, and R.Y.Siegwart, "BRISK : Binary Robust Invariant Scalable Keypoints", Proceeding of International Conference
on Computer Vision（ICCV）, 2011.
[Yoshioka2011] 吉岡勇太, 和田俊和, "整数化によるSURFアルゴリズムの高速化", ビジョン技術の実利用ワークショップ（VIEW）, pp.137-138, 2011.
[Ambai2011] M.Ambai, and Y.Yoshida, "CARD : Compact and Real-time Descriptors", Proceeding of International Conference on Computer Vision（ICCV）,
2011.
[Alahi2012] A.Alahi, R.Ortiz, and P.Vandergheynst, "FREAK: Fast Retina Keypoint", Proceeding of Computer Vision and Pattern Recognition（CVPR）, pp.510517, 2012.

Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

100

まとめ

1. テンプレートマッチングの基本
2. テンプレートマッチングのロバスト化技術
3. テンプレートマッチングの高速化技術
4. 最近の取り組み紹介
参照データの戦略的削減によるマッチング～ CPTMを核として ～Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013101

本チュートリアルに関する情報
WEBページ
http://isl.sist.chukyo-u.ac.jp/Archives/archives.html
関係する技術の紹介や，
画像データを公開しています．

Special thanks to：
資料作成に協力してくれた研究室のメンバー

M2 秋月秀一 M1 櫻本泰憲
Hashimoto Laboratory, Chukyo University

M2 斎藤正孝

M1 永瀬誠信

B4 武井翔一第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013

102

SSII2013

明日からの関連発表

デモンストレーション
6月13日（木）~14日（金）DS2-06画素削減型高速テンプレートマッチング～過酷な環境下でも，目的の物体を素早く正確に見つけ出す～

インタラクティブ
6月13日（木） 14:15~16:00
IS2-24
全周囲物体認識のためのサーフェスモデル
からの高独自性ベクトルペア選択

6月14日（金） 10:00~12:45
IS3-29
準リアルシーンを用いた3次元特徴量の生成学習に基づくばら積み部品の認識
Hashimoto Laboratory, Chukyo University

第19回 画像センシングシンポジウム チュートリアル講演会 June 12, 2013103

Thank you for your attention!