第76回 ロボット工学セミナー

Intelligent Sensing Laboratory, Chukyo University

2013年5月16日

本日の話題
第1部 2次元画像センシング

高速物体検出～ ロボットに使える2次元・3次元センシング ～1.

テンプレートマッチングの基礎技術

2.

テンプレートマッチングのロバスト化と高速化

3.

研究紹介 ～参照データの戦略的削減とその展開～

第2部 3次元画像センシング
中京大学

橋本 学

mana@isl.sist.chukyo-u.ac.jp
http://isl.sist.chukyo-u.ac.jp/

1.

3次元物体認識の動向および主要な技術

2.

研究紹介 ～データの独自性に着目した物体認識～

Intelligent Sensing Laboratory, Chukyo University

Intelligent Sensing Laboratory, Chukyo University

2

第 76回 ロボット工学セミナー May 16, 2013

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

[Rosenfeld1969](dx,dy)第1部

2次元画像センシング
テンプレートf (i, j )Step1:SCORR(dx , d y ) g (i, j )最大値

{(g(d  i, d  j)   )( f (i, j)   )}(g(d  i, d  j)   ) ( f (i, j)   )xx

Step2:

入力画像類似性を評価する．
（ex. 正規化相互相関）
y

y

g

g

2

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

Intelligent Sensing Laboratory, Chukyo University

f

f

2

類似度マップ SCORR(d x , d y )第 76回 ロボット工学セミナー May 16, 20134

類似度マップと検出結果

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

正規化相互相関

M

①
⑤

③

②

m

⑥

n

④

領域 h(i, j )dx , d yN

テンプレート画像 f (i, j )入力画像 g (i, j )SNCC(dx , d y ) {g(d  i, d  j) f (i, j)}(g(d  i, d  j)) ( f (i, j))
x

2

x

 
f h
cos( )   f hf (i, j )y2yh(i, j )

（内積の定義）

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

第 76回 ロボット工学セミナー May 16, 20135

類似度尺度② 相互相関係数
相互相関係数（統計量）

SZNCC

{(g(d  i, d  j)   )( f (i, j)   )}(d , d ) (g(d  i, d  j)   ) ( f (i, j)   )
x

g

y

y

g

y

g

f

2

y

g

2

f

f と g それぞれの
標準偏差
2

f

 プログラムによる実行時には，平均値を求めるために１パス，さらにそれを用いてZNCC値を計算するために１パス，合計2回の2重ループ計算が必要．

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

 分母，分子は，標準偏差または分散値になっているから，よく知られた以下の公式により計算量を削減できる．

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

分散 ＝ 標準偏差の2乗 ＝ （データの2乗の平均値）ー（データの平均値の2乗）

V  2 

第 76回 ロボット工学セミナー May 16, 2013

1 N
1 N
2
( xk )  (  xk ) 2N k 1
N k 1

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

一般的には，NCCよりもZNCCがよく使われる．

Intelligent Sensing Laboratory, Chukyo University

x

y

f

2

x

x

x

の相互相関係数を類似度尺度とする．
SZNCC

6

f と g の共分散

{(g(d  i, d  j)   )( f (i, j)   )}(d , d ) (g(d  i, d  j)   ) ( f (i, j)   )f (i, j ) と h(i, j ) を，それぞれ画像領域内の濃度値分布と考え，統計量としてy

第 76回 ロボット工学セミナー May 16, 2013

類似度尺度② 相互相関係数の計算量削減

Zero-means Normalized Cross-CorrelationxIntelligent Sensing Laboratory, Chukyo University

7Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 20138

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

類似度尺度の関係
M

Sum of Squared Difference

差の２乗和

m

SSSD(dx , d y )  (g(dx  i, d y  j)  f (i, j))n2

差の絶対値和dx , d y

Sum of Absolute DifferenceN

テンプレート画像
f (i, j )似ているほど小さな値になるので相違度と呼ばれる．

入力画像 g (i, j )SSSD

f (i, j )SSAD(dx , d y )   | g(dx  i, d y  j)  f (i, j) |h(i, j )SNCC(cos )

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

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 20139

計算コスト比較Intelligent Sensing Laboratory, Chukyo University

領域 h(i, j )



SSAD

第 76回 ロボット工学セミナー May 16, 201310

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

1. ロバスト化
2. 高速化

テンプレート画像（71x55）

3. 高精度化

入力画像（600x400）

手法

処理時間 [ms]

SAD

926

SSD

1695

NCC

695

ZNCC

3017

ZNCC（計算量削減）

739※CPU：Intel®CORE™i7（3.40GHz），システムメモリ：16GB，OS：Ubuntu10.04，
言語：C言語，コンパイラ：gcc ver.4.4.3 （最適化オプション-O あり），SSE機能使用せず．
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201311

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201312

ロバスト化に関する課題

ロバスト化の基本的な考え方
照明変動

変動の影響が少ない特徴量で抽象化する．
画素（濃度値）同士の照合から特徴量同士の照合へ

回転

照明変動

特徴量
部分的隠蔽

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

拡大・縮小

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

回転

特徴量

特徴量

テンプレート類似物

アフィン変形
テンプレート
類似物

特徴量

特徴量の設計が重要
幾何学変形Intelligent Sensing Laboratory, Chukyo University

13

第 76回 ロボット工学セミナー May 16, 201314

第 76回 ロボット工学セミナー May 16, 2013

増分符号相関（ISC : Increment Sign Correlation）

ロバスト化に関する主な研究例
単純な抽象化の例
画像の2値化Intelligent Sensing Laboratory, Chukyo University

水平方向の輝度値の増減を2値符号で表現し，画像化する．

[Murase2000]

増分符号画像2値化

1
b(i, j )  
0[Tubbs1989]

if f (i  1, j )  f (i, j )  0
otherwise

その他の主な研究
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 に基づくキーポイント抽出法[Tang1991][Ojala1994][Sumi1995][Yamaguchi2002][Murase2000][Mita2005][Satoh2001][Ullah2001][Sato2003][Okuda2004][Iwata2009][Hinterstoisser2010][Ozaki2010][Zhao2011][Kouotaki2011][Yuasa2013, Yoshioka2011]

Image A

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 DATASET3Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201315

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201316

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

増分符号表現[Murase2000][Ullah2001]

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

増分符号画像

5

8

3

4

元画像

7

8

濃度ヒストグラム59
8

濃度ヒストグラム

8

15
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

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

第 76回 ロボット工学セミナー May 16, 2013

4

7

10



2

9

濃度ヒストグラムIntelligent Sensing Laboratory, Chukyo University

4 3

3

8

1
0

5

4 11

8

シェーディング
大きさ＝752

6



シェーディング
大きさ＝45



17Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

18

DOT : Dominant Orientation Templates

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

Gi
Gj

Gi 

f (i, j )
,
i

Gj 

f (i, j )j (i, j )  tan 1 (G j / Gi )テンプレートと入力画像それぞれを小領域に分割し，主勾配方向を求めてコード化．これらの一致度をもとに照合する．


勾配方向は8種類（7方向+無勾配フラグ）に量子化して，1/0 で表現．
ビット演算による高速照合．

（画像の1次微分値）

７

小領域に分割された入力画像 （例：小領域の大きさは７ｘ７）７（最大濃度勾配方向）

 (i, j ) 
if Gi  G j   （コントラスト確保のためのしきい値）c(i, j )    Notherwise2 （方向分割ピッチ）N

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.
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

19

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201320

高速化の基本的な考え方

高速化に関する研究例

TMの基本ステップ

計算量が小さい類似度尺度を採用する

3つのアプローチ

差の絶対値の総和（相違度）

Step 1： 類似度マップを生成
SCORR(dx , d y ) {(g(d  i, d  j)   )( f (i, j)   )}(g(d  i, d  j)   ) ( f (i, j)   )
x

x

y

g

y

g

f

1.
2.
3.

2

類似度マップ

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

SSDA（類似度計算の打ち切り）
ピラミッド探索（Coarse-to-Fine探索）
アクティブ探索1. Chamfer Matching
2. Oriented Chamfer Matching
3. Boosting Chamfer Matching
4. 輪郭情報を用いたマッチング
5. 自己相関類似度マップを元にした画素選択
6. 分散階層化テンプレートマッチング
7. 全画素使用時と同等性能になる画素選択
8. 粗テンプレートマッチング
9. 顕著点同士の照合
10. 独自性の高い周波数成分の利用
11. 濃度共起確率を用いた画素選択
12. 画像間共起確率を用いた安定画素選択
13. 周辺の偽物体との識別性を考慮した画素選択

Step 2： 類似度マップからピーク位置を検出
21

第 76回 ロボット工学セミナー May 16, 2013

Chamfer MatchingIntelligent Sensing Laboratory, Chukyo University

エッジ画像

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
距離変換画像[Barrow1977][Jamie2008][Ma2010][Hashimoto1991][Hashimoto1995][Hirooka1997][Saito2001][Matsubara2005][Lee2011][Wu2011][Hashimoto2011][Hashimoto2011, Saito2013][Sakuramoto2012]

第 76回 ロボット工学セミナー May 16, 2013

22

3
2
1
0
1
2

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

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

相違度

相違度

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

[Barnea1972][Tanimoto1975, Rosenfeld1977][Murase1998][Hashimoto1991]

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

y

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

x

すべての画素を使わない （有効画素の選択）

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

Intelligent Sensing Laboratory, Chukyo University

| g(d  i, d  j)  f (i, j) |類似度マップ作成を省略する

1. 計算量が少ない類似性尺度f2

SSAD(d x , d y ) N 1 M 1

探索ウインドウの移動
距離変換画像 IDTS    TE (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.
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

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

23

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201324

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

テンプレートマッチングの性能評価の観点[Hirooka1997]

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

64x64画素

基本性能

128x128画素

1. ロバスト性
2. 高速性
3. 精度（照明，アフィン，隠蔽，背景変動・・・）

Trade-offTrade-off

実用化において無視できない性能
25%

6.4%

1.5%

4. 省メモリ

0.4%

5. 類似度マップの探索しやすさ （研究例が少ない）
6. パラメータの少なさ，調整の容易さ

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

7. 汎用性（どんな画像にも対応，画像サイズ，テクスチャの多寡・・・）

参考文献：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.
Intelligent Sensing Laboratory, Chukyo University

25

第 76回 ロボット工学セミナー May 16, 2013

幾何学変形

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

戦略的画素数削減

RelCom[Venkatraman10]
定性的3値表現 OCM[Ullah01][Yamaguchi02]
確率的増分符号標本化順位相関 [Mita06][Ryugo02]
基板位置決め(87)
印刷物検査(98)
SRF[Iwata08]
ISC[Murase00]
ロボット視覚(95)3値輪郭表現[Sumi94]

Phase Only Correlation[Kuglin75]

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]
アクティブ探索[Murase98] [Kanatani02]
2段探索Multilevel Successive Elimination Algorithm[Goshtasby84]
探索順序制御[Gao00]Fine
Granularity
Successive Elimination[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]

探索回数制限Coarse-to-Fine[Tanimoto75][Rosenfeld77][Vanderbrug77]

探索順序制御[Gold84]

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

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

CPU

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]

SUSAN
HarrisSIFT[Harris88] [Smith97] [Lowe99]

Intelligent Sensing Laboratory, Chukyo University

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

3次元物体認識①低テクスチャ画像への拡張 2012
②ユニークエッジによるアピアランスベース
3次元物体認識 2012
③CADモデルからの特徴的局所領域の抽出とロボットビジョンへの応用 2012
④特徴的ベクトルペアマッチング 2012
⑤準リアルシーン学習によるベクトルペア
マッチングの高信頼化 2013
画素以外への適用①SIFTキーポイントの効果的削減 2011
②剛体追跡のためのサブトラッカ選択 2011

照合の高速化
Topics26

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

部分テンプレート[Okuda04]

濃度変化不変尺度 汎用センサ(01)正規化相互相関[Rosenfeld69]

第 76回 ロボット工学セミナー May 16, 2013

画素数削減テンプレートマッチング（CPTM）とその展開

テンプレートマッチング研究マップ ～ロバスト化と高速化の観点から～
ロバスト性向上Intelligent Sensing Laboratory, Chukyo University

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

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

第 76回 ロボット工学セミナー May 16, 201327

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201328

研究の目的Intelligent Sensing Laboratory, Chukyo University

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

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

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

～共起確率を用いた画素の削減～
CPTM : Co‐Occurrence Probability 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.

Intelligent Sensing Laboratory, Chukyo University

高速化の基本戦略

最も簡単な濃度共起ヒストグラム （2画素の場合）



テンプレート画像内の全ての点を使わない．
厳選された画素だけを使用する．



テンプレート画像を代表できる画素を選択する．
＝ 独自性の高い画素

O

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

i

dR2

vq

j
画素選択

終点画素 Q  if
（濃度値 q ） 

vp
d

照合

p

第 76回 ロボット工学セミナー May 16, 20132

2  0

q
・・・
・・・

p

・・・
・・・
：

：

：

：

：
・・・

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

Intelligent Sensing Laboratory, Chukyo University

q

else
vq  v p  dh2 ( p, q )変位ベクトル d ：共起性を測る方向と距離を指定

2

f ( v )  p  f ( v )  q then   1

始点画素 P（濃度値 p ）

30

第 76回 ロボット工学セミナー May 16, 201331

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201332

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

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

画素選択アルゴリズム

終点
n画素の共起確率分布を生成

データが分散q

LSI画素間の関係を変化
・方向・画素間距離pd  (4,0)d  (1,0)

背景画素

複数パターンの共起確率分布を合成
画素の選ばれやすさをマップで表現d  (16,0)

マップをもとに画素を選択
垂直エッジ部分

前景画素

候補群から
ランダムに選択
類似の値をもつ画素候補が複数存在

Partsd  (4,0)d  (1,0)Intelligent Sensing Laboratory, Chukyo UniversityNOd  (16,0)

第 76回 ロボット工学セミナー May 16, 2013

YES

33

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

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

Intelligent Sensing Laboratory, Chukyo University

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

M=97 (0.7%)(b) Rabbit

Intelligent Sensing Laboratory, Chukyo University

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

第 76回 ロボット工学セミナー May 16, 201335

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, 2013.

34

CPTMの問題点

画素安定性推定のアイデア

テンプレートマッチング

一定間隔で切り出されたテンプレート画像

全画素による
マッチング

類似

テンプレート画像

類似した値 ‐> 安定

同一座標の画素相違

入力画像

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

CPTM
断面図

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

独自性の高い画素を抽出
1%の参照画素

共起確率

対角線

p1

100倍高速

p2

投票

同一座標

p2

 多様な照明変動に追従できない
 テンプレート画像1枚のみから参照画素を選択することの限界(p1, p2)
画像間共起ヒストグラム

複数のテンプレート画像から安定した参照画素を選択する
Intelligent Sensing Laboratory, Chukyo University

f t 3f t 2f t 1

hi

hi

平均 μ

p1

[kita2010]37

第 76回 ロボット工学セミナー May 16, 2013

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

正規分布
近似

p1

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201338

実験に用いた連続写真（プリント基板）
ft

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

hi

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

S

安定率

hs

S

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

空間共起
ヒストグラムS

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

空間的独自性

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

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

39

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201340

画素選択結果

関連手法との比較

テンプレート画像群の例 （サイズ185x145）

安定率マップ

選択された参照画素（黄点）

画素選択方法(1) SSD(2) ZNCC(3) ISC(4) SIFT(5) SURF(6) Random(7) Gradient(8) Canny(9) IRFET（事前にコントラスト拡張）(10) CPTM(11) Stability(12) Proposed method

参照画素数[pixel]
26825
26825
26680
27 [point]
27 [point]
27
27
27
27
27
27
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

従来法（CPTM法）

提案手法




 安定率マップの効果により安定率の高い参照画素が増加
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201341

Intelligent Sensing Laboratory, Chukyo University

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

第 76回 ロボット工学セミナー May 16, 201342

課題
紛らわしい類似物に囲まれた目的物体の検出識別に有効な画素を用いる
テンプレートマッチング
対象物

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

第 76回 ロボット工学セミナー May 16, 201344

類似物との誤照合の要因

基本アイデア
類似している偽物体

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

100画素

２．対象物のみを特徴づける画素群を選択
識別性能向上テンプレート画像

対象物

入力画像

参照画素群

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

参照画素群

入力画像

CPTM法で選択された画素群は，テンプレート画像の内部では独自性が高いが，周辺の偽物体にも同様の画素が含まれていることがある．

入力画像（周辺物が対象と似ていない場合）

45

識別に有効な画素選択アルゴリズム（周辺物が対象と似ている場合）

Intelligent Sensing Laboratory, Chukyo University

46

第 76回 ロボット工学セミナー May 16, 2013

識別性能の評価
頻度

D ： クラス分離度
候補選択
テンプレート画像
100×100…
ポジティブサンプル群

候補画素群

ポジティブ
サンプル群

サンプル画像群
参照画素群
を用いて類
似度を計算

繰り返し
（GA利用）

Cn

…

ネガティブ
サンプル群

F  w1

最適参照画素群50画素

1
 w2 DS 

重複面積
第 76回 ロボット工学セミナー May 16, 2013

47

類似度

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

識別性能を表す目的関数

参照画素群の識別性能を評価

Cp
S ： 重複面積

ネガティブサンプル群

ポジティブ
サンプル群

Intelligent Sensing Laboratory, Chukyo University

ネガティブ
サンプル群

最大化

クラス分離度Intelligent Sensing Laboratory, Chukyo University

w1,w2 は重み係数
第 76回 ロボット工学セミナー May 16, 2013

48

実験結果

実験結果

109×91パズルのピース

M=30点(0.3%)

カード

M=30点(0.5%)

将棋の駒

M=30点(0.3%)

実験画像（600×400）

画素選択方法

参照画素数[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

1.0

(6) CPTM法

500

76.0

109

(7) CLAFIC法

60[次元]

68

8769

0.8

(8) 提案手法

60

94

0.008

検出成功例

検出成功例

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

検出成功例

手法

パズルのピース

カード

将棋の駒

提案手法

99%（99枚/100枚）

99%（99枚/100枚）

99%（99枚/100枚）

全画素法

93%（93枚/100枚）

100%（100枚/100枚）

100%（100枚/100枚）

0.6

全画素法
ランダム A

0.4

ランダム B
0.2

CPTM
CLAFIC法 （部分空間法）

0.0
0.0

0.2

0.4

0.6

0.8

1.0

適合率 RpIntelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

Intelligent Sensing Laboratory, Chukyo University

49Intelligent Sensing Laboratory, Chukyo University

提案手法
第 76回 ロボット工学セミナー May 16, 2013

50

3次元物体認識手法
 モデルベース物体認識

第2部

3次元画像センシング

 認識対象のモデルを利用して入力データと照合する．
本セミナーでは，こちらを重点的に紹介します．

 アピアランスベース物体認識
 認識対象をさまざまな視点からみた画像群を準備しておき，入力画像と照合する．

近年では，アピアランスベースでもCADモデルからの学習画像自動生成などが試みられており，両者の明確な区別は難しくなっている．

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201352

モデルベース物体認識

モデルベース物体認識の分類
1. キーポイント利用

モデル：
3次元CADモデルなどが利用される．
入力データ： レンジファインダで撮影された距離画像などが利用される．

Spin Image法
DAI法
Local Surface Patches
Point Feature Histogram
Point Pair Feature
SHOT[Johnson1997][Takeguchi2001][Chen2007][Rusu2008][Drost2010][Tombari2010]

EGI（拡張ガウス像）
3DPO
3Dエッジ
VVV
DGI

[Horn1983][Bolls1986][Lowe1991][Sumi1997][Adan2011]

モデル上のキーポイント単位で照合

2. 非キーポイント利用

レンジファインダ

3-Dモデル

全点，あるいはエッジなど単位で照合

距離画像

 かつては距離画像そのものを使う手法が主流．
 最近は高速化のためにキーポイントベースが増えている．
 特徴記述法が重要．

ばら積みシーン

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

53

1980

1990

2000

2005

2010

Local Surface Patches[Chen2007]
Depth Aspect Image[Takeguchi2001]

点群の位置関係の記述

Spin Image[Johnson1997]
Spherical Spin Image[Ruiz-Correa2001]

3D Shape Contexts[Frome2004]

非キーポイント利用
EGI[Horn1983]
3DPO[Bolls1986]
多面体認識[Shirai1971]

距離・濃淡融合[Hashimoto2001]
VVV[Sumi1997]
COSMOS
Aspect Graph[Dorai1995][Cyr2001]

Local Feature Histogram
3Dモデルのエッジと[Hetzel2001]
濃淡画像の照合[Lowe1991]
大局的シーン解釈[Hashimoto1999]

Point Feature Histogram[Rusu2008]
Fast PFH[Rusu2009]
Scale-Dependent
Local Shape Descriptor[Novatnack2008]

法線方向分布SHOT[Tombari2010]

PPF[Drost2010]

DAI+M-ICP[Kitaaki2007]

Histogram of Oriented Normal Vectors[Tang2011]
CSHOT[Tombari2011]

PPF + Visibility Context[Kim2011]
PPF B2B, S2B, L2L[Choi2012]
2or3点間の位置・ VPM
法線間の関係 [Akizuki2012][Horn1983]

 多面体は離散的に分布する

Viewpoint Feature Histogram[Rusu2010]
Elevation Descriptor[Shih2007]
多段解像度探索[Ulrich2009]

Global Radius-based Surface Descriptor[Marton2010]

EM-ICP
ICP+Cached K-d tree search[Granger2002] TrICP
LM-ICP[Nuchter2007]
重み付けと [Chetverikov2002] [Fitzgibbon2003]
Picky-ICP
射影による対応付け ICP(point-to-point) 外れ値除去
FICP[Besl1992][Zhang1994][ZinBer2003] 距離変換の利用
茶：TOF方式[Yamamoto1991][Phillps2007][Masuda2003]
青：TOF以外のActive計測
point-to-plane
大規模距離画像群の同時位置合わせ
紫：Passive計測
インデックス画像[Chen1991][Nishino2002] M-ICP[Oishi2006]
緑：etc.
[Kaneko2003]

VIVID9i
Cartesia
200Hz小型距離画像センサ
シリコンレンジファインダ[KONICA MINOLTA2004][Tateishi2008][SPACEVISION2004][阪大/ソニー1994]
640x480
640x480
空間コード化法
Swiss Ranger SR3000 Swiss Ranger SR4000
TDS-A[パルステック1997]
Swiss Ranger SR1[Posdamer1982][MESA2005][MESA2008]
441x280[MESA2001]
FZD[Sato1985]
176x144
176x144
ランダムドットパターン投光ステレオ[OMRON2007][Hashimoto1999]
Bumblebee2
Bumblebee XB3Digiclops[Point Grey1999]
液晶レンジファインダ[Point Grey2006] [Point Grey2007]
640x480[Sato1988]
パラメトリック固有空間法
648x488
1280x960[Murase1994]

Intelligent Sensing Laboratory, Chukyo University

 3次元サーフェスモデルの法線方向分布を，ガウス球（Gaussian sphere）に投影する表現法．

Mesh HOG
Normal Aligned Radial Feature[Zaharescu2009] [Steder2010]
DGI
勾配の記述
[Adán2011]
H/Wの工夫GPU利用
MFC利用[Germann2007,Park2010] [Liu, Okuda2010]

 円筒状物体は直径を描くように分布する

精密照合

Topics54

第 76回 ロボット工学セミナー May 16, 2013

Extended Gaussian Image（EGI）表現

モデルベース3-D物体認識研究マップ ～特徴記述法に関して～
キーポイント利用Intelligent Sensing Laboratory, Chukyo University

距離・濃淡の最尤統合[Tateno2011]

MELFA-3D Vision
KinectDepthSense 311[Microsoft2010] [SoftKinetic2011][三菱電機2013]
640x480
約30万point
160x120
DepthSense 325
D-IMager[SoftKinetic2012][Panasonic2010]
320x240160x120LEAP
TVS[Leap Motion2013][三次元メディア2011]
PCL
Point Cloud Library [2009~]

第 76回 ロボット工学セミナー May 16, 201355

参考文献：B. K. P. Horn, ” Extended Gaussian Images”, IEEE, 1983.
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201356

Spin Image

Versatile Volumetric Vision（VVV）[Sumi1997][Johnson1997]

 特徴記述 ステレオカメラによる距離情報の取得から移動物体の追跡まで行うトータルな3次元ビジョンシステム

1. ある注目点の法線に垂直な方向αと法線方向βで表し，βを軸とする円柱
面に周囲の頂点を投票，画像化する（Spin Image）．
2. 全ての点についてSpin Imageを生成して格納しておく．

 距離情報を持つ物体輪郭同士の照合によって位置姿勢を認識
 得られた輪郭は直線・円弧で表現

β

 直線・円弧に近似された物体モデル・シーンを位置合わせする

β

α

α

Efficient M-dimensional
closest point search structure

Spin Image

計測点

θM

Model

Scene M-tuple is close tomatching model M-tupleθD
近似直線（青）

 照合

物体モデル

計測された距離つき輪郭｜θM-θD｜がしきい値以下の形状同士を位置合わせ

 シーンから作成したSpin image
を固有空間上に投影し最近傍
探索

=

S

Projection scene spin-image
onto eigen-spin-images
Scene

参考文献： A.E.Johnson，M.Hebert ,” Surface Registration by Matching Oriented Points, Proceedings ”, 3DIM, pp.121-128, 1997.
A.E.Johnson，M.Hebert ,” Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes ”, PAMI, pp433-449, 1999.

参考文献：角 保志，富田 文明, ”ステレオビジョンによる3次元物体の認識”, 信学論D-II, vol.J80-D-II(5), pp.1105-1112, 1997.
Intelligent Sensing Laboratory, Chukyo University

Create scene
spin-image

Matching model57

第 76回 ロボット工学セミナー May 16, 2013

Depth Aspect Image（DAI）

Intelligent Sensing Laboratory, Chukyo University

Point Pair Feature（PPF）[Takeguchi2001][Drost2010]

 ACFに投影した見かけの距離画像（DAI）による照合

 物体モデル上に設定された法線方向を持った点対特徴

 ACF（Aspect coordinate flame）
 幾何拘束を持つ3点の特徴点の組によって作成された基準座標系

 モデル記述： 物体上の全ての計測点からできる２点ごとにPPFを取り出し，特徴量 F1～F4 をキーとしてHash Tableに登録

 特徴点＝曲率の大きな点

Hash table

n1

F4

DAI生成

特徴点

m1

n2

F2

・・・

m2

Model Descriptionnmr

入力距離画像DAIの生成照合モジュール

認識結果

si
sr
Ts→g

Tm→gmi

mr

y
z

mi

Tm→g

x
Tm→gnrm=Ts→gnrs=e1sr
si①
Fs(sr,si)

mi

mi′
③

mr

②

Model Description

an

・・
・
+1
・・
・ +1
・・
・

④

Accumulator Space

参考文献：B. Drost，M. Ulrich，N. Navab and S. Ilic,”Model Globally, Match Locally: Efficient and Robust 3D Object Recognition”, IEEE Proc.
CVPR, pp.998-1005, 2010.

参考文献：武口 智行，金子 俊一，近藤 司，五十嵐 悟,”距離アスペクト画像の2次元照合によるロバスト物体認識”, 信学論D-II, vol.J84-D-II,no.8,

第 76回 ロボット工学セミナー May 16, 2013

α

a1
mr′

nsr

Ts→gsiIntelligent Sensing Laboratory, Chukyo UniversityA={(m1,m2),(m3,m4),(m5,m6)}F

 投票による認識： 似た属性値のPPF同士を照合し，幾何変換パラメー
タ（mr回りにαの回転）を計算して投票する．最多得票を解とする．
・・・

DAIデータベース

m1
m2
m6
m3
m5
m4

n2

F3
F1

・・・
ACF

58

第 76回 ロボット工学セミナー May 16, 2013

59

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

60

Iterative Closest Point（ICP）

Signature of Histograms of OrienTations （SHOT）[Tombari2010]

 Local Reference Frame（RF）の設定

 データ点群とモデル点群の誤差最小化手法

 注目点の近傍点を用いて，主成分分析により基準座標を設定

1. 最近傍点の対応付け
2. 対応点からの幾何変換の推定
3. 上記２ステップの繰り返しによって，位置合わせ誤差が最小となる剛   T
体変換パラメータ q  qR | qT  を出力

 特徴記述 RFをもとに記述範囲を，xy平面に2分割，球の外側，内側に2分割，z軸に対して8分割する． 合計32次元に分割する．
 基準点の法線 r と分割された各スペース（32個）の法線ベクトル ni の内積を計算し， m ビンのヒストグラムを作成

データ

cos   r・n inixX  { xi }・・・
m ビン θ



32個のヒストグラムを合成した32×m次元の特徴量 （SHOT特徴量）

 照合

N


   21 p f (q )  xi  R(qR ) pi  qT
N p i 1

モデル

頻度

y

誤差


P  { pi }zr[Besl1992][Kaneko2003]

派生手法として，M推定により外れ値にロバストとなったM-ICP等がある．

HOGと同様の勾配ベースの特徴量で姿勢変化に不変

 KNNを用いた最近傍探索により対応点探索
参考文献：F.Tombari, S.Salti, L.D.Stefano ,” Unique Signatures of Histograms for Local Surface Description ”, ECCV, pp.356-369, 2010.
Intelligent Sensing Laboratory, Chukyo University

61

第 76回 ロボット工学セミナー May 16, 2013

アピアランスベース物体認識

参考文献：P. J. Besl and N. D. Mckay, ”A Method for Registration of 3-D Shapes”, IEEE Trans. PAMI, vol.14, no.2, 1992.
S.Kaneko, T.Kondo, A.Miyamoto, Robust matching of 3D contours using iterative closest point algorithm improved by M-estimation, PR,vol.36, pp.2041-2047, 2003.
Intelligent Sensing Laboratory, Chukyo University

62

第 76回 ロボット工学セミナー May 16, 2013

アピアランスベースの代表例： パラメトリック固有空間法[Murase1994]

姿勢既知の学習画像データベース

似た視点＝似た画像

学習画像データベース

θ
・・・

θ=0

・・・

θ=45

・・・

・・・

θ=135

θ=90

・・・

0[deg]
・・・

・・・

・・・

・・・

θ=180

○特別な3次元の入力装置が不要
×保存するデータが膨大になる．
→生成型学習，CGによる自動生成．
×背景混入に弱い

θ=225

θ=270

・・・
θ=45

・・・
θ=180

ターンテーブルIntelligent Sensing Laboratory, Chukyo University

θ=0

・・・
θ=135

θ=90
・・・

θ=225

主成分
分析

・・・
θ=270

θ=315

多数の画像データを
k 次元の固有空間内の多様体で表現k << 元の画像次元

θ=315

照合
主成分
分析

入力画像（姿勢未知）

入力画像（姿勢未知）
第 76回 ロボット工学セミナー May 16, 2013

63

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201364

基本アイデアIntelligent Sensing Laboratory, Chukyo University

 目的 モデルベース認識の高信頼性と高速性の両立

誤対応確率を最小化する3-D特徴点マッチング

 基本アイデア
1. 3次元点群で表現された物体モデル各点について， 独自性を数値化
2. 独自性の高い特徴点だけを使用→処理の高信頼化・高速化
独自性の高い特徴点（珍しい局所形状を持つ）

独自性の低い特徴点（よく似た局所形状が周囲に存在する）

永瀬誠信，秋月秀一，橋本学，誤対応確率を最小化する3‐D特徴点を用いた高速ロボットビジョン，ビジョン技術の実利用ワークショップ（
ViEW2012），pp.IS2-B5, 2012/12．

Intelligent Sensing Laboratory, Chukyo University

提案システムの概要

66

第 76回 ロボット工学セミナー May 16, 2013

法線分布情報に基づく独自性指標の算出

モデル分析モジュール

 全ての点について，局所形状を相互に比較する．

認識モジュール

注目点：n

独自性算出

注目点の法線ベクトル：Nnθ

3次元点群データとして表現された物体モデル

3次元点群データから構成される物体モデル

入力距離画像
特徴記述

．． ．
．

mi

独自性算出結果
特徴記述

半径 r 内の法線
方向ヒストグラム

特徴点マッチング
位置姿勢推定

θ

θ

頻度

特徴点抽出

半径: r

n

θ

比較
θ

法線分布ヒストグラム

独自性指標 Sn1 M 1Sn 
 ( B( pn , qm ))M  1 m 1

特徴点抽出結果
認識結果

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

67

Intelligent Sensing Laboratory, Chukyo University

比較M： 全モデル点数
B： Bhattacharyya距離p，q ： ヒストグラム
第 76回 ロボット工学セミナー May 16, 201368

独自性評価の例
3位
Sn=0.878

1位
Sn=0.903

さまざまな手法によって選択された特徴点
2位
Sn=0.884高Sn=0.864

Sn=0.885

高
独
自
性
指
標
Sn

独
自
性
指
標

Sn=0.867

低物体モデル外観

独自性算出結果

低複雑形状モデル

120

500

100

400

平面

80

稜線

頻度

頻度

多面体モデル

60
40

頂点

特徴点
胴体

角・耳・尾

300
200
100

20

0

0

Sn

Sn

独自性分布

ランダム法によって選択された特徴点

独自性分布Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

69

Cartesia 3D Handy Scanner HS-01 仕様
サイズ

W167 x D115 x H56 mm

重量

560g

撮影範囲

水平垂直 50～200mm, 奥行き250～500mm

測定精度

RMSE 0.3mm

分解能

水平垂直 0.3mm

テクスチャ解像度

640 x 480 画素

撮影時間

0.5秒

曲率法によって選択された特徴点

Intelligent Sensing Laboratory, Chukyo University

70

 ばら積みシーンをそれぞれ約130枚．

物体モデル外観

物体モデル外観

入力距離画像物体A（コンセントプラグ）

3次元点群モデル（1659点）

出典：http://www.space-vision.jp/JP-Handy_Scanner.html

71

3次元点群モデル（2023点）

入力距離画像物体B（ギア）物体モデル外観

物体モデル外観

第 76回 ロボット工学セミナー May 16, 2013

第 76回 ロボット工学セミナー May 16, 2013

実験に用いたモデルと距離画像

3次元点群モデル（1374点）Intelligent Sensing Laboratory, Chukyo University

提案手法によって選択された特徴点

入力距離画像物体C（バー）Intelligent Sensing Laboratory, Chukyo University

3次元点群モデル（1757点）

入力距離画像物体D（ジョイント）第 76回 ロボット工学セミナー May 16, 201372

さまざまなばら積み部品に対する認識率と処理時間
Spin Image[Johnson, PAMI1999]
CorrespondenceGrouping (PCL)
ランダム法

曲率法

提案手法

提案手法による認識結果

物体A

物体B

物体C

物体D

平均

Pr [%]

49.6

50.8

35.2

70.6

51.6

T [sec]

24.95

55.34

31.21

20.68

33.05

Pr [%]

74.4

96.2

65.6

84.9

80.3
38.41

T [sec]

45.41

52.85

29.26

26.10

特徴点数

70

50

30

30

-

Pr [%]

89.1

96.9

85.2

69.8

85.3

T [sec]

5.87

4.77

2.06

1.74

3.61

特徴点数

70

50

30

30

‐

Pr [%]

86.8

76.9

18.0

54.8

59.1

T [sec]

6.01

4.94

2.21

1.97

3.78

特徴点数

70

50

30

30

-

Pr [%]

89.1

97.7

94.5

93.7

93.8

T [sec]

5.83

4.76

2.05

1.76

3.60

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

Intelligent Sensing Laboratory, Chukyo University

73(a) 物体A(b) 物体B(c) 物体C(d) 物体DIntelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201374

基本アイデア1. 少数の特徴点を用いる．（例：全点の１％）
高速化に寄与する．

特徴的ベクトルペアを用いた3次元物体認識
物体モデル（メッシュ表現）

重要なこと…
どのような3次元特徴点が選択されるべきか？
特徴点

ごく少数の
特徴点
[1] S.Akizuki, M.Hashimoto, High-speed and Reliable Object Recognition Using Distinctive 3-D Vector-Pairs ina Range Image, ISOT2012, 2012/10/30.
[2] 秋月秀一，橋本学，特徴的3-Dベクトルペアを用いたばら積み部品の高速位置姿勢認識，第15回画像の認識・理解シンポジウ
ム（MIRU2012），IS1-65, 2012/8．

2. 本研究では，共起発生確率が低い点を選択する．周囲には，これと似た形状が存在しないので，誤認識のリスクが低い．

マッチングデータ
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201376

3次元ベクトルペア

特徴的な3次元ベクトルペアの抽出 3つの3次元点

 共起発生確率が低い3次元ベクトルペア → 独自性が高い．

 3次元姿勢パラメータを決定するためには，3つの3次元点があ
ればよい．

Q1

v1
l1

幾何学的パラメータ
l1 = |v1| = |PQ1|,
l2 = |v2| = |PQ2|,
θ

P
θ

l2

1. 3次元ベクトルペアの共起発生確率を計算する．
2. 各点のShape description value H(sp, sq1, sq2) を計算する．
Shape description value: Shape Index値を使用（Dorai1997）

v2
Q2

発生確率
（発生頻度）

Shape description value
sp, sq1, sq2
3次元レンジファインダで撮影した3次元物体

 視点を共有する2本のベクトル ＝ 3次元ベクトルペア
 この表現により，幾何学的な表現がシンプルになる．

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

このヒストグラムを分析することによって，
3-Dベクトルペアの独自性を評価することができる．
77

特徴抽出： 曲率法 v.s. 提案手法
曲率法

H(p,q1,q2)

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201378

3次元ベクトルペアマッチング
提案手法
累積される

明確な
稜線

面取りした
コーナー部

物体モデル外観

多数のベクトルペアに支持されている位置（累積された重心位置）が，認識結果として出力される．

凹凸の多い物体
浅いくぼみ

Accumulated value of centroid
照合に使用される
Low
High
ベクトルペア（50 ペア）物体モデル重心の候補位置

フラットな物体

3次元ベクトルペアは独自性の高い形状から抽出される．
この3次元ベクトルペアを照合に使う．
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

ベクトルペアが入力画像と照合され，モデル重心が投
票される．

79

Intelligent Sensing Laboratory, Chukyo University

認識結果

第 76回 ロボット工学セミナー May 16, 201380

複雑シーンに対する認識性能

さまざまな物体に対する認識性能

N: 抽出されたベクトルペア数
Pr: 認識成功率
T: 処理時間手法

特徴量N

3種の異なる物体による性能評価

Pr

T(sec)

Spin Image
法

Spin maps

‐

93.7%

20.68

ランダム法

Vector pairs

10

47.6%

8.66

曲率法

Vector pairs

10

77.0%

0.74

提案手法

Vector pairs

10

81.7%

0.21

40

92.9%

1.19

Spin Image法による結果（失敗）NPr

T(sec)

A: 電気プラグ

10

94.6%

0.42

B: 歯車

10

99.2%

0.64

C: 木製の取手

10

79.7%

0.64

物体A

N: 抽出されたベクトルペア数
Pr: 認識成功率
T: 処理時間提案手法による結果（成功）成功
Alignment error
+8mm
±0mm
‐8mm
Intelligent Sensing Laboratory, Chukyo University

物体

第 76回 ロボット工学セミナー May 16, 2013

Intelligent Sensing Laboratory, Chukyo University

準リアルシーンの生成学習とベクトルペア
最適化に基づくばら積み部品の認識

81

物体B

提案手法は，さまざまな形状の物体に対して高い性能を実現した．

Intelligent Sensing Laboratory, Chukyo University

物体C
成功
Alignment error
+8mm
±0mm
‐8mm
第 76回 ロボット工学セミナー May 16, 201382

VPM：ベクトルペアマッチング（従来法）
記述長の短い特徴量を少数使うことで高速化を実現する手法
 照合単位
lq1
sq1

θ
Q1

P
sp

幾何学パラメータ
lq1, lq2, θ

lq2

sq2 Q2

Shape Index(Dorai1997)

sp, sq1, sq2

一つの始点と二つの終点からなる3-Dベクトルペア

 ベクトルペア選択
 s p , sq1 , sq 2の共起発生確率の低いベクトルペア
独自性の高いベクトルペア
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201384

VPM：ベクトルペアマッチング（従来法）

研究の目的

 照合

 問題点
 複数物体間に発生するベクトルペアと誤照合してしまう．

 選択したベクトルペアを入力距離画像に照合

原因：照合に用いるベクトルペアは物体モデルのみから選択

物体モデル外観選択されたベクトルペア
物体モデル

入力距離画像
照合結果

照合結果

 目的
多くのベクトルペアによって支持された姿勢仮説

 物体間との誤照合を低減する高速・高信頼な認識手法の提案

物体の位置姿勢

高速化の観点から，特徴量としてベクトルペアを用いる．
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201385

基本アイデアIntelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201386

提案手法の流れ 従来のベクトルペア選択基準は，物体内で独自性が高いこと．
 これに加え，新たに「物体間には生じにくいベクトルペアであること」という条件を追加する．
＝物体間で発生確率の低いベクトルペア

VPM法（従来）提案手法（追加）
物理モデラーによってリアルなシーンを生成
し，学習画像を生成

3次元物体モデル

物体内で独自性が高いベクトルペアの選択

Intelligent Sensing Laboratory, Chukyo University

学習画像群

誤認識の予測確率

物体内で独自性が高いベクトルペア（従来の選択基準）

物体内では高独自性

物体間ベクトルペアの発生確率を計算

物体間ベクトルペア

かつ高独自性ベクトルペア

照合に使用する
ベクトルペア

物体間では低発生確率
第 76回 ロボット工学セミナー May 16, 2013

ベクトルペアの識別性能評価（峻別）

87Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201388

準リアルシーンと学習画像の生成

物体間ベクトルペアの学習

 シミュレータでリアリティの高いばら積みシーンを生成 外輪郭をまたがって発生するベクトルペアを学習 物理エンジンには SketchyPhysics を使用

 ヒストグラムを生成

probability(frequency)

距離画像

sp,sq1,sq2

物体間ベクトルペアの学習に利用
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

物体間ベクトルペアの発生確率を計算
89

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

識別性能評価実シーンにおける認識実験（実験画像）

 ベクトルペアの「良さ」を評価

 レンジファインダで取得した140枚の画像に対する認識実験

90

実験に使用

発生確率（頻度） PhS
独自性D
物体モデル外観不適

物体内高独自性
ベクトルペア

R

物体モデル
距離画像

s p , sq1 , sq 2

適

s p , sq1 , sq 2

 評価式

CADモデル

物体間ベクトルペア

D
PhS  Rの値の高いベクトルペア（Dが大きく，Phsが小さい）を選択
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

入力シーン外観91

Intelligent Sensing Laboratory, Chukyo University

入力距離画像
第 76回 ロボット工学セミナー May 16, 201392

実シーンにおける認識実験（結果）参考文献 （テンプレートマッチング ロバスト化）①[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.

各手法の認識成功率と処理時間
N

Pr

T(sec)

Spin Image

－

71.4

57.99

曲率法

20

91.4

9.22

VPM法

20

75.7

1.06

提案手法

10 94.3

0.91

CPU：Intel®CORE™i7-2600
システムメモリ：16GB

N：ベクトルペア数
Pr：認識成功率
T：処理時間認識結果

提案手法は従来のVPM法に対して認識成功率が18.6%向上
Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201393Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 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.

[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.

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 201395

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 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.

[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.

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

97

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

98

参考文献 （テンプレートマッチング 高速化）③

参考文献 （特徴点ベースマッチング手法）[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.

[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.

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.

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

99

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013100

参考文献 （3次元認識 キーポイントベース手法）①

参考文献 （3次元認識 キーポイントベース手法）②[Ikeuchi1993] K.Ikeuchi, S.B.Kang, Assembly Plan from Observation, AAAI Technical Report FS-93-04, pp.115-119, 1993.
[Johnson1997] A.E.Johnson，M.Hebert, Surface Registration by Matching Oriented Points, Proceedings. International Conference on Recent Advances in 3-D
Digital Imaging and Modeling, pp.121-128, 1997.
[Johnson1999] A.E.Johnson，M.Hebert, Using Spin Images for Efficient Object Recognition in Cluttered 3D Scenes, IEEE Transactions on Pattern Analysis
and Machine Intelligence (PAMI), pp433-449, 1999.
[Correa2001] S.R-Correa, L.G.Shapiro, M.Melia, A New Signature-Based Method for Efficient 3-D Object Recognition, IEEE Computer Society Conference
onComputer Vision and Pattern Recognition (CVPR), pp.I769-I776 2001.
[Takeguchi2001] 武口智行，金子俊一，近藤司，五十嵐悟, 距離アスペクト画像の2次元照合によるロバスト物体認識, 電学論D-II, Vol.J84-D-II,No.8, pp.17101721, 2001.
[Frome2004] A.Frome, D.Huber, R.Kolluri, T.Bulow, J.Malik, Recognizing Object in Range Data Using Regional Point Descriptors, 8th European Conference on
Computer Vision, Prague, Czech Republic, pp.224-237, 2004.
[Chen2007] H.Chen, B.Bhanu, 3D Free-Form Object Recognition in Range Images Using Local Surface Patches, Pattern Recognition Letters, Vol.28, pp.12521262, 2007.
[Kitaki2007] 北明 靖雄，奥田 晴久，橋本 学，金子 俊一, 距離アスペクト画像照合と階層化ICP照合による3次元物体認識, 電学論(C), Vol.127, No.4, pp.615622, 2007.
[Rusu2008] R.B.Rusu, N.Blodow, Z.C.Marton, M.Beetz, Aligening Pointb Cloud Views using Persistent Feature Histgrams, IEEE/RSJ International Conferenceon Intelligent Robots and System (IROS), pp.22-26, 2008.
[Novatnack2008] J.Novatnack, K.Nishino, Scale-Dependent/Invariant Local 3D Shape Descriptors for Fully Automatic Registration of Multiple Sets of Range
Images, European Conference on Computer Vision (ECCV), pp.440-453, 2008.
[Rusu2008] R.B.Rusu, Z.C.Marton, N.Blodow, M.Beetz, Learning Informative Point Classes for the Acuisition of Object Model Maps, 10th International
Conference on Control, Automation, Robotics and Vision (ICRARCV), pp.643-650, 2008.
[Zaharescu2009] A.Zaharescu, E.Boyer, K.Varanasi, R.Horaud, Surface Feature Detection and Description with Applications to Mesh Matching, IEEE
Conference on Computer Vision and Pattern Recognition (CVPR), pp373-380, 2009.
[Rusu2009] R.B.Rusu, N.Blodow, M.Beetz, Fast Point Feature Histgrams (FPFH) for 3D Registration, The IEEE International Conference on Robotics andAutomation (ICRA), pp3212-3217, 2009.
[Drost2010] B.Drost, M.Ulrich, N.Navab, S.Ilic, Model Globally, Match Locally: Efficient and Robust 3D Object Recognition, 2010 IEEE Conference on
Computer Vision and Pattern Recognition (CVPR), pp.998-1005, 2010.
[Tombari2010] F.Tombari, S.Salti, L.D.Stefano, Unique Signatures of Histograms for Local Surface Description, European Conference on Computer
Vision(ECCV), pp.356-369, 2010.
[Rusu2010] R.B.Rusu, G.Bradski, R.Thibaux, J.Hsu, Fast 3D Recognition and Pose Using the Viewpoint Feature Histogram, IEEE/RSJ International
Conference on Intelligent Robots and System (IROS), pp.2155-2162, 2010.

[Steder2010] B.Steder, R.B.Rusu, K.Konolige, W.Burgard, NARF: 3D Range Image Features for Object Recognition, IEEE/RSJ International Conference onIntelligent Robots and System (IROS), 2010.
[Kim2011] E.Kim, G.Medioni, 3D Object Recognition in Range Images Using Visibility Context, IEEE/RSJ International Conference on Intelligent Robots andSystem (IROS), pp.3800-3807, 2011.
[Steder2011] B.Steder, R.B.Rusu, K.Konolige, W.Burgard, Point Feature Extraction on 3D Range Scans Taking into Account Object Boundaries, International
Conference on Robotics and Automation, pp.2601-2608, 2011.
[Tombari2011] F.Tombari, S.Salti, L.D.Stefano, A Combined Texture-Shape Descriptor For Enhanced 3D Feature Matching, IEEE International Conference on
Image Processing(ICIP), pp.809-812, 2011.
[Akizuki2012] S.Akizuki,M.Hashimoto, High-speed and Reliable Object Recognition using Distinctive 3-D Vector Pairs in a Range Image, International
Symposium on Optmechatronic Technologies (ISOT), pp1-6, 2012
[Choi2012] C.Choi, Y.Taguchi, O.Tuzel, M.Liu, S.Ramalingam, Voting-Based Pose Estimation for Robotic Assembly Using a 3D Sensor, IEEE International
Conference on Robotics and Automation (ICRA), pp.1724-1731, 2012.
[Tang2012] S.Tang, X.Wang, X.Lv, T.X.Han, J.Keller, Z.He, M.Skubic, S.Lao, Histogram of Oriented Normal Vectors for Object Recognition with a Depth Sensor,
The 11th Asian Conference on Computer Vision (ACCV), 2012.

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

101

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

102

参考文献 （3次元認識 非キーポイントベース手法）

参考文献 （精密照合・その他）[Horn1984] B.K.P.Horn, Extended Gaussian Images, Proceedings of the IEEE, Vol.72, No.12, pp.1671-1686, 1984.
[Lowe1991] D.G.Lowe, Fitting Parameterized Three-Dimensional Models to Images, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI),
Vol.13, No.5, pp 441-450, 1991.
[Dorai1995] C.Dorai，A.K.Jain, COSMOS-A Representation Scheme for Free-Form Surfaces, Proceedings. Fifth International Conference on Computer Vision(ICCV), pp.1024-1029, 1995.
[Sumi1997] 角保志，富田文明, ステレオビジョンによる3次元物体の認識，信学論D-II, Vol.J80-D-II, No.5, pp.1105-1112, 1997.
[Hashimoto1999] 橋本 学，黒田 伸一，鷲見 和彦，宇佐美 照夫，仲田 周二, シーン仮説と入力画像の大局的画像整合性評価に基づく複数物体の認識, 電学
論D-II, Vol.J82-D-II(12), pp.2288-2297, 1999.
[Kawamura2000] K.Kawamura, K.Hasegawa, Y.Someya, Y.Sato, K.Ikeuchi, Robust localization for 3D object recognition using local EGI and 3D templatematching with M-estimators, IEEE International Conference on Robotics and Automation (ICRA), pp.1848-1855, 2000.
[Cyr2001] C.M.Cyr, B.B. Kimia, 3D Object Recognition Using Shape Similiarity-Based Aspect Graph, Proceedings. Eighth IEEE International Conference on
Computer Vision (ICCV), Vol.1, pp.254-261, 2001.
[Hetzel2001] G.Hetzel，B.Leibe，P.Levi，B.Schiele, 3D Object Recognition from Range Images using Local Feature Histograms, Computer Vision and Pattern
Recognition, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), pp.II-394-II-399, 2001.
[Shin2007] J.Shih，C.Lee，J.T.Wang, A New 3D Model Retrieval Approach Based on the Elevation Descriptor, Pattern Recognition, Vol.40, pp.283-295, 2007.
[Germann2007] M.Germann，M.D.Breitenstein, I.K.Park, H.Pfister, Automatic Pose Estimation for Range Images on the GPU, International Conference on 3-D
Digital Imaging and Modeling(3DIM), pp.81-90, 2007.
[Ulrich2009] M.Ulrich，C.Wiedemann，C.Steger, CAD-Based Recognition of 3D Objects In Monocular Images, Proceedings. IEEE International Conference on
Robotics and Automation(ICRA), pp.2090-2097, 2009.
[Liu2010] M.Liu, O.Tuzel, A.Veeraraghavan, R.Chellappa, A.Agrawal, H.Okuda, Pose Estimation in Heavy Clutter using a Multi-Flash Camera, IEEE International
Conference on Robotics and Automation (ICRA), pp.2028-2035, 2010.
[Park2010] I.K.Park, M.Germann, M.D.Breitenstein, H.Pfister, Fast and Automatic Object Pose Estimation for Range Images on the GPU, Machine Vision andApplications, Vol.21, No,5, pp.749-766, 2010.
[Marton2010] Z.Marton，D.Pangeric，R.B.Rusu，A.Holzbach，M.Beetz, Hierarchical Object Geometric Categorization and Appearance Classification For Mobile
Manipulation, IEEE-RAS Proc. International Conference on Humanoid Robots (ICHR), pp.365-370, 2010.
[Adan2011] A.Adan，P.Merchan，S.Salamanca, 3D scene retrieval and recognition with Depth Gradient Images, Pattern Recognition Letters, Vol.32, pp.13371353, 2011.

[Chen1991] Y.Chen, G.Medioni, Object Modeling by Registration of Multiple Range Images, Proceedings. IEEE. International Conference on Robotics andAutomation, pp.2724-2729, 1991.
[Yamamoto1991] 山本正信，ピエール・ボランジャー，アンジェロ・ベラルディン，距離動画像を用いた非剛体運動パラメータの直接的推定法，情報処理学会論文誌，Vol.32, No.9, pp.1129-1141, 1991.
[Besl1992] P.J.Besl, N.D.McKay, A Method For Registration Of 3-D Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), Vol.14,
No.2, pp.239-256, 1992.
[Zhang1994] Z.Zhang, Iterative Point Matching for Registration of Free-Form Curves and Surfaces, International Journal of Computer Vision, Vol.13, Issue.2,
pp.119-152, 1994.
[Chetverikov2002] D.Chetverikov,D.Svirko, D.Stepanov, P.Krsek, The Trimmed Iterative Closest Point Algorithm, Proceedings. International Conference on
Pattern Recognition (ICIP), Vol.3, pp.545-548, 2002.
[Granger2002] S.Granger, X.Pennec, Multi-scale EM-ICP:A Fast and Robust Approach for Surface Registration, European Conference on Computer
Vision(ECCV), Vol.2353, pp.418-432, 2002.
[Nishino2002] 西野恒，池内克史, 大規模距離画像群の頑健な同時位置合せ, 電学論. D-II, Vol.J85-D-II, pp.1413-1424, 2002.
[ZinBer2003] T.ZinBer, J.Schmidt, H.Niemann, A Refind ICP Algorithm for Robust 3-D Correspondence Estimation, Proceedings. International Confrence on
Image Processing(ICIP), Vol.3, pp.II-695-8, 2003.
[Fitzgibbon2003] A.W.Fitzgibbon, Robust Registration of 2D and 3D points sets, Image Vision Computing, Vol.21, pp.1145-1153, 2003.
[Kaneko2003] S.Kaneko, T.Kondo, A.Miyamoto, Robust matching of 3D contours using iterative closest point algorithm improved by M-estimation, Pattern
Recognition 36, pp.2041-2047, 2003.
[Masuda2003] 増田健，符号付距離場の一致による複数距離画像からの形状モデル生成，情報処理学会論文誌，Vol.44, No.SIG5, 2003.
[Ohishi2006] 大石 岳史，中澤 篤志，池内 克史, インデックス画像を用いた複数距離画像の高速同時位置合せ, 電学論D, Vol.J89-D, No.3 pp.513-521,
2006.
[Nuchter2007] A.Nuchter, K.Lingemann, J.Hertzberg, Cached K-d Tree Search For ICP Algorithms, International Conference on 3-D Digital Imaging andModeling (3DIM), pp.419-426, 2007.
[Phillps2007] J.M.Phillps, R.Liu, C.Tomasi, Outlier Robust ICP for Minimaizing Fractional RMSD, Sixth International Conference on 3-D Digital Imaging andModeling (3DIM), pp.427-434, 2007.
[Tateno2010] 立野 圭祐，小竹 大輔，内山 晋二, 実部品のピッキングのための距離・濃淡画像を最尤に統合する高精度高安定なモデルフィッティング法, 画像の認識・理解シンポジウム（MIRU2010）, IS2-4, pp.714-721, 2010.
[Murase1994] 村瀬洋，シュリーナイヤー，2次元照合による3 次元物体認識-パラメトリック固有空間法-，電学論D-II，Vol.J77-D-II, No.11, pp.2179-2187, 1994.
[Rusu2011] R.B.Rusu, S.Couins, 3D is here: Point Cloud Library (PCL), IEEE International Conference on Robotics and Automation (ICRA), pp.1-4, 2011.

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013

103

Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013104

本セミナー講演に関する情報
WEBページ
http://isl.sist.chukyo-u.ac.jp/Archives/archives.html
関係するデータなどを公開しています．

Thank you for your attention!

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

M2 秋月秀一

B4 武井翔一M2 斎藤正孝

M1 永瀬誠信

M2 柴田悠太郎

M1 櫻本泰憲Intelligent Sensing Laboratory, Chukyo University

第 76回 ロボット工学セミナー May 16, 2013105