VOL. J103-D NO. 4
APRIL 2020
本PDFの扱いは、電子情報通信学会著作権規定に従うこと。
なお、本PDFは研究教育目的（非営利）に限り、著者が第三者に直接配布することができる。著者以外からの配布は禁じられている。

論

文

領域画像マッチングのための目標領域特徴量による初期位置探索法
山下幸彦† a)

若原徹†† b)

Initial Location Search Method using Target Region Features for Region-Based
Image Matching
Yukihiko YAMASHITA†a) and Toru WAKAHARA††b)

あらまし 画像マッチングは，画像処理におけるもっとも重要な手法の一つであり，特徴画像マッチングと領域画像マッチングに大別される．領域画像マッチングは高精度なマッチング能力を有するが，whole-to-part マッ
チングに適用する場合，マルチスケールでスライド窓探索を行うと処理時間が膨大化するという問題がある．本
論文では領域画像マッチングのための高精度かつ高速な初期位置探索の実現を目指す．具体的には，画像劣化や幾何学的変換に頑健となるようにスライディング離散フーリエ変換を工夫した目標領域特徴量に基づく初期位置
探索法を提案する．特徴画像マッチングの代表的手法である ASIFT/ASURF と RANSAC の組合せによる初期位置探索と提案手法の比較実験を行い，提案手法の優位性を示す．
キーワード

画像マッチング，特徴画像マッチング，領域画像マッチング，初期位置探索

1. ま え が きの組合せは，実用的で頑健な特徴画像マッチングを可画像マッチングは，物体検出，パターン認識などに応ス平滑化や固有値展開によりパターン変動を吸収し用され，画像処理における最も重要な手法の一つであた飯島による複合類似度 [7] や，変形パラメータを陽る．画像マッチングを実用的なものにするためには，入に反復解法で求める Lucas-Kanade アルゴリズム [8]力画像での照明条件の変化，物体位置の変化や回転なに始まり，現在でもその性能を高めるべく研究が続

どの幾何学的変換，更には物体の非剛体変形に対して，けられている [9]．若原らによる GAT/GPT (Global

テンプレート画像のマッチングが頑健である必要があAﬃne Transformation/Global Projection Transfor-

る．そのために，多くの画像マッチング手法が提案されmation) 相関法 [9]〜[11] は，アフィン変換/2 次元射ている．それらは大きく分けて，画像から特徴点を抽出

影変換パラメータを含む正規化相互相関を目的関数

し，それら特徴点の整合性を評価する特徴画像マッチ

として，それを微分して得られる非線形方程式を線形

ングと，画像領域の整合性を直接評価する領域画像マッ

近似して解き，それを繰り返す反復解法で最適変換パ能にしている．一方，領域画像マッチングでは，ガウチングの二つに大別される．特徴画像マッチングでは，ラメータを決定している．領域画像マッチングは高精Scale-Invariant Feature Transform (SIFT) [1], [2] や度なマッチングが可能であり，認識タスクでも高い性

Speeded-Up Robust Features (SURF) [3], [4] に基づ能が報告されている．GPT 相関法に同一エッジ方向

く手法が広く用いられている．特に，SIFT を Aﬃne

平均最小距離を用いた kNN による MNIST の手書き変換に関して頑健にした ASIFT [5] と RANSAC [6]†東京工業大学，東京都
Tokyo Institute of Technology, 2–12–1, O-okayama, Meguro-

法政大学，小金井市
Hosei University, 3–7–2 Kajino-cho, Koganei-shi, 184–8584

能で優位に立てても，処理時間が膨大化する問題があった．実際，反復解法を用いる場合はなおさら，入Japana) E-mail: yamasita@ide.titech.ac.jp

力画像中に埋め込まれた物体を検出するためには，テb) E-mail: wakahara@hosei.ac.jp
DOI:10.14923/transinfj.2019JDP7056

330

なっている．
しかし，領域画像マッチングの場合，マッチング性

ku, Tokyo, 152–8552 Japan††

数字認識 [10] では認識率 99.7%が達成されており，これは kNN に基づく手法 [12] としては非常に高い値と電子情報通信学会論文誌

ンプレート画像をマルチスケールのスライド窓探索

c 一般社団法人電子情報通信学会 2020
D Vol. J103–D No. 4 pp. 330–340 

論文／領域画像マッチングのための目標領域特徴量による初期位置探索法

でマッチングする処理が必要となり，処理時間が増える．特に，マルチスケールでのスライド窓探索の時間を短縮するには，効率的な初期位置探索が有力であとする提案手法の有効性を示す．

2. 有限区間三角関数の畳み込み和による
ガウス平滑化法

る．初期位置探索には特徴画像マッチングを用いるのが自然である．ただし，特徴画像マッチングが有効に本章では，有限区間三角関数の畳み込み和によるガ

働くような画像マッチングのタスクに対して，特徴画

ウス平滑化法 [19] において，微分画像に対する誤差，

像マッチングで得られた結果を敢えて領域画像マッチ

及び GPU での実装を視野に入れた単精度計算におけングと組み合わせることには余り意味がない．特徴画

る誤差，についての詳細な定量的評価を行う．こうし像マッチングで対応が難しいようなタスクを解決でき

た評価はこれまでなされたことはなく，これにより本るような領域画像マッチングにおける初期位置探索が論文で提案する目標領域特徴量抽出への適用可能性を課題である．その意味で，特徴画像マッチング自身の確認する．

性能向上が必要となる．特に，特徴点のスケールが目

2. 1 ガウス平滑化の近似実現

標領域のスケールにより小さい場合に画像劣化に対1 次元離散点上の関数で記述する．ガウス関数はする頑健性が不足となる．近年，ボケやブレに頑健な

標準偏差の数倍で急速に 0 に近づくため，有限区間

特徴点抽出法 [13] や特徴量 [14] も提案されているが，[−K, K] で考え，G[n] = e−(πn/K) /(2σ ) による平様々な変形や劣化に対する性能検証が十分になされて滑化を考える．σ は，区間両端を π ，−π と考えたとき

2

2

いるとはいえない．また，一般物体認識の先駆的研の標準偏差で，画像上での標準偏差は σK/π である．

究として，dense SIFT [15] を用いたピラミッド型記関数 f [n] に対して，ガウス平滑化やその 1 階，2 階微述により ROI (Region of Interest) マッチングを実現

分の近似を求めるためには，次の値が求まれば良い．

するアプローチがある．更にその発展形として denseKASIFT [16] や SIFT Flow [17] が提案されているが，これらは画像検索や Optical Flow 推定を目的としており，本研究が目指す領域画像マッチングのための初

k=−K
K


本論文では，SIFT 特徴量の考えに基づいた目標領

k=−K
K


域特徴量による，領域画像マッチングのための初期位k=−K

期位置探索とは目的が異なる．

置探索法を新たに提案する．目標領域特徴量に基づく
手法は，スケールが大きく様々な劣化に対して頑健であるという利点があるが，初期位置探索法としての研究例はない．提案手法ではスライディング離散フーリ
エ変換を用いたガウス平滑化 [18]〜[21] を利用した高速計算法 [22] を活用する．これにより，計算量のオーG[k]f [n − k](1)kG[k]f [n − k](2)k2 G[k]f [n − k](3)

簡単のため，β = π/K とおき，次の近似を考える．

G[k] 

ap cos(βpk)

p=0kG[k] P


bp sin(βpk)

p=1

ダーが平滑化量に依存せず，画素数に比例したものになる．特に，初期位置探索に設定するパラメータ数をP

k2 G[k] P

dp cos(βpk)

p=0

最小化し，更に条件分岐がほとんどないループの単純構成によるアルゴリズムのスリム化を追求し，なおか

P は計算量を減らすため，DFT を打ち切る次数であつ計算量が対象画像の内容にほとんど依存しないといる．ここでは，P として 2 から 4 程度を想定している．

う汎用性も実現している．計算機実験では，提案手法

有限区間三角関数の畳み込み和を次式で定義すれば，に対して，ASIFT/ASURF と RANSAC を組み合わせた手法による初期位置探索の性能を比較した．比較

cp [n] =内容は，1) ガウス平滑化，移動平均，白色加法性雑音の重畳による入力画像の劣化に対する頑健性，2) 特徴
点数が少ないテンプレート画像に対する頑健性，3) 計
算時間，である．実験結果より，初期位置探索を目的

sp [n] =

K

k=−K
K


f [n − k] cos(βpk)
f [n − k] sin(βpk)

k=−K

式 (1)-(3) の近似は，次式で表すことができる．
331電子情報通信学会論文誌 2020/4 Vol. J103–D No. 4K

G[k]f [n − k] 

kG[k]f [n − k] K ，p を整数倍した場合への，積分値の再利用はでき

P


なくなる．
杉本ら [21] は 2 次のフィルタを使うことを提案して

bp sp [n]

p=1

k=−K
K


もできる．こうする方が数値計算精度は向上するが，ap cp [n]

p=0

k=−K
K


P


k2 G[k]f [n − k] 

P


いる．

v[n + 1] = 2 cos(βp)v[n] + v[n − 1]

dp cp [n]+ f [n + 1] − eiβp f [n]

p=0

k=−K

図 1 に，標準画像 Lenna を，有限区間三角関数の畳み込み和によりガウス平滑化した結果を示す．

(9)

この式では，実数部と虚数部が分離しているため，

cp [n] と sp [n] を別々に計算することが可能である．し2. 2 有限区間三角関数の畳み込み和の高速計算

たがって，cp [n] だけが欲しい場合などに計算量を削簡単のために，複素指数関数を使って表す．Kober

減することができる．しかしながら，2 階の微分方程[18] は，カーネル積分
u[n] =n

式を解く形になっており，単精度浮動小数点演算で計算したときに，計算精度に問題が生じる場合が考えら

f [k]eiβpk

(4)

k=1

れる．

2. 3 打ち切り誤差を使って，有限区間三角関数の畳み込み和 cp [n] とsp [n] を，次式で求めた．

区間長や次数を P で打ち切るため，ガウス関数の近似に誤差が生じる．画像上での標準偏差は σK/π を一定にしても，K と σ に自由度が生じるが，打切り誤

cp [n] − isp [n]= e−iβpn (u[n + K] − u[n − K − 1])(5)

この u[n] は，次の漸化式で計算することができる．

差は σ に大きく依存し，K にはあまり依存しない．
図 2 は，P = 2 と P = 4 のときの，G[n]，nG[n]，LoG の近似誤差を，平均 2 乗誤差ともとの関数の 2 乗
平均の比の平方根で示したものである．

u[n] = u[n − 1] + f [n]eiβpn(6)

P = 2 の場合，σ = 1.1 とすれば，誤差はガウス関

この式では，三角関数を 1 周期分記憶して，信号にか数で 1.1%，微分ガウス関数で 5.3%，LoG で 8.2%程

けていく必要がある．少し変形して，IIR フィルタの度となる．P = 4 の場合，σ = 0.85 とすれば，それ形にする．

ぞれで，0.049%，0.32%，0.68%程度となる．

2. 4 単精度浮動小数点演算誤差

v[n] = e−iβp v[n − 1] + f [n](7)とすれば，cp [n] と sp [n] は，次式で求まる．

倍精度浮動小数点演算を使えば，有限区間三角関数の畳み込み和の計算は十分な精度で計算できるが，今後重要になる安価な GPU は単精度浮動小数点演算器

cp [n] − isp [n]しか積んでいないため，単精度浮動小数点演算によ= (−1)p (v[n + K] − v[n − K] + x[n − K]) (8)る精度評価を行う．標準画像 Lenna と Barbara をそ

また，積分値でなく，直接，区間和を計算すること

512 × 512 × 2) 次元のベクトルを入力とした．図 3 に，れぞれ，1 次元信号として考え，連結した 524288 (=

図1

332

三角関数のスライディング畳み込み和によるガウス平滑化法

論文／領域画像マッチングのための目標領域特徴量による初期位置探索法

図2

打ち切り誤差（Interval：区間打ち切り，Order：次数打ち切り．
）

図 3 単精度計算誤差（Kernel：カーネル積分（式 (6)）
，IIR：1 次 IIR（式 (7)）
，2ndIIR：
2 次 IIR（式 (9)）．B を付加したものは，区間積分で計算．
）

K = 256 のときの，c1 [n] の区間長 10,000 での最大する．また，特に，回転共変性に注目する．続いて，誤差と，同区間での対象信号の 2 乗平均の平方根との提案手法の要となる目標領域特徴量について説明し，比を示す．

具体的な計算法を示す．最後に，目標領域特徴量に基単精度浮動小数点の計算では，2 次 IIR では，初めの 1 万点で 2%程度の誤差があり，十分とは言えない．

3. 提 案 手 法
本章では，まず基本となるフーリエ記述エッジ方向

づく初期位置探索の手順を説明する．

3. 1 フーリエ記述エッジ方向ヒストグラム
エッジ方向ヒストグラム D(θ) は，ある領域内の θ
方向のエッジの強さの（重み付き）和である．これを，Q 次のフーリエ級数で記述する．

ヒストグラム [23] について説明するが，提案手法ではGPU での実装を視野に入れ，三角関数やその逆関数，
更に条件分岐を行わない簡便な計算方法を新たに導入

D(θ) =

Q

dq eiqθ

(10)

q=−Q

333

電子情報通信学会論文誌 2020/4 Vol. J103–D No. 4

ここで，d−q = dq が成立するため，係数 dq の実数でに関して説明する．ただし，回転・スケール不変な目の自由度は 2Q + 1 である．

標領域特徴量の抽出について計算量の観点から汎用的

入力画像 I(x, y) をガウス平滑化し，横と縦方向に
I1 (x, y) = (IX (x, y))2 + (IY (x, y))2に論じたのは本研究が初めてである．
入力画像 I の点 (x, y) において，スケール S の目標

微分した画像を IX (x, y)，IY (x, y) とする．

(11)

領域特徴量を記述する．S は，ガウス関数の標準偏差で，その領域のおよその半径である．まず，P = 4 ととおけば，点 (x, y) におけるヒストグラムは，ディラッ

した有限区間三角関数の畳み込み和によるガウス平滑

クのデルタ関数 δ(θ) を使って，I1 (x, y)δ(θ−θ(x, y))化法により，I からスケール S/8 でガウス平滑化し，である．このとき，IX (x, y) = I1 (x, y) cos θ(x, y)，

横と縦方向に微分した画像 IX ，IY を求める．正弦成IY (x, y) = I1 (x, y) sin θ(x, y) が成立する．文献 [23]分を使うことにより，ガウス平滑化と微分は同時に行

では，arctan，sin，cos 関数と条件分岐を使って各点うことができる．そして，画像の各点で，式 (12) をのフーリエ係数を求めている．本研究では，使って，フーリエ記述エッジ方向ヒストグラムを求め

1
dq =
2π

 π

−π

I1 (x, y)δ(θ − θ(x, y))e−iqθ dθ1I1 (x, y)e−iqθ(x,y)
=
2π
q


I1 (x, y)2 + ε IX (x, y) − iIY (x, y)2πI1 (x, y)2 + ε

る．その 2Q + 1 の係数を，P = 2 とした有限区間三角関数の畳み込み和によるガウス平滑化法により，スケールを S 及び S/4 として平滑化したものをそれぞれ求める．
提案手法の特徴として，画像からこのフーリエ記述
エッジ方向ヒストグラムの計算まで，繰り返しのためを使って求める．ここで，ε は 0 による除算を防ぐた以外に条件分岐を必要とせず，平滑化のための係数をめの定数である（実験では，ε = 10−12 ）．この式を使テーブルにしておけば三角関数の計算も不要で，簡単

えば，平方根の計算は必要であるが，量子化や三角関

なアルゴリズムで実装することができることである．

数の計算を行うことなく，フーリエ記述エッジ方向ヒ
ストグラムを求めることができる．

(x, y) におけるスケール S のフーリエ係数から，一周を L 等分した θ = 2πl/L (l = 0, 1, . . . , L − 1) にまた，エッジの基準方向を θ0 回転したとき，回転おけるヒストグラムの値を求め，それが極大となる方したヒストグラムの係数 dq は，次式で得ることがで向を，ヒストグラムの値が大きい方から二つ求める．

きる．

それぞれの角度がその対象領域の基準角度であり，特dq = dq e−iqθ0

徴量はその角度で正規化して求める．両者のヒストグ(12)

ラムの値の比が 1 に近いときには，二つの角度に対す

ガウス平滑化を使ってエッジ方向ヒストグラムをる特徴量をそれぞれ求める．比が 1 から離れているとフーリエ記述する利点は，回転に対する共変性である．

きには，最大の角度に対してだけ特徴量を求める．

例えば，ヒストグラムの最大位置を検出する場合，画(x, y) での基準角度の一つを，θ0 とする．提案する像を 1 度回転させれば，検出最大位置もちょうど 1 度

目標領域特徴量は，θ0 で正規化したときの，(x, y) のずれることになる．その最大位置は次数による分解能

周りの M 点における，スケール S/4 でガウス平滑化の制限のため本当の最大位置とは限らないが，位置検したフーリエ記述エッジ方向ヒストグラムを並べたも出の基準方向のためには共変性で十分である．また，のである．

SIFT では特徴点抽出時に，基準方向を求めるために

図 4 は，特徴量記述に使う原点を中心とした周辺の

36 方向に量子化するが，これを提案手法に直接適用す

M 点の正規化座標 (xm , ym ) (m = 1, 2, . . . , M ) をるとヒストグラムを求めるためには平滑化を 36 回行

図示したものである．実際にヒストグラムを特徴量とう必要がある．フーリエ記述で Q = 4 とすれば，係) (m = 1, 2, . . . , M )する点の画像上の座標 (xm , ym

数の数は 9 個であり，9 回の平滑化ですむことになり，は，次式で与えられる．

計算量を削減することができる．この回転共変性については，4.1 の実験で確かめる．

3. 2 目標領域特徴量
SIFT の特徴量の考え方に基づいた目標領域特徴量334xm = S(xm cos θ0 − ym sin θ0 ) + x(13)= S(xm sin θ0 + ym cos θ0 ) + y
ym

(14)

スケール S/4 のフーリエ記述エッジ方向ヒストグラム

論文／領域画像マッチングのための目標領域特徴量による初期位置探索法

Algorithm 1 目標領域特徴量計算法

図4

ヒストグラムを特徴量とする点の位置

Require: 入力画像 I ，初期スケール S0 ，スケール更新比 rS ，最大スケール SMax ，スケール S において特徴量を求める点の集合 TS ，特徴量となるヒストグラムを利用する点の特徴量を求める点からの正規化座標 (xm , ym ) (m = 1, 2, . . . , M )S ⇐ S0while S ≤ SMax do
I をスケール S/8 でガウス平滑化し，横と縦方向に微分した画像 IX ，IY を求める．
画像の各点でフーリエ記述エッジ方向ヒストグラムの係数を求める．
2Q + 1 個の係数を，スケール S 及び S/4 でガウス平滑化
する．
for (x, y) ∈ TS do
スケール S で平滑化した係数を使って，基準方向を（複数）求める．
for θ0 ∈ (得られた基準方向の集合) do
基準方向 θ0 に対して，式 (13)，(14) を使い，ヒスト
グラムを利用する点の座標を求める．
それらの点におけるスケール S/4 のフーリエ記述エッ
ジ方向ヒストグラムを，式 (12) で回転させ，並べて
M (2Q + 1) 次元のベクトルを得る．
得られたベクトルのノルムを 1 に正則化して，(x, y)
における特徴量の一つとして記憶する．
end forend forS ⇐ rS S
end while

は全ての点で計算済みであるため，その値を抽出し，しかしながら，画像の変形量が大きいときには，特角度正規化のためにヒストグラムを式 (12) で回転さ

徴ベクトルが異なってしまい，位置検出精度が下がる

せる．これらの係数を並べ，M (2Q + 1) 次元のベクことが考えられる．そこで，ASIFT の考え方を使っトルが得られる．このベクトルをノルムを 1 に正規化て，画像を Aﬃne 変換し，特徴量を抽出して位置検したものが，(x, y) での最終的な特徴量となる．

出させることを考える．入力画像を変形させると，全特徴量を求める点 (x, y) は，S に比例 (比例係数は0.2 程度) した値で画像中を格子点状に走査する．
画像から特徴量を求めるアルゴリズムを Alogrithm

1 にまとめる．

体の特徴抽出の計算時間が，変形しない場合の計算時間に変形パターン数をかけた値になってしまう．そこ
で，ここでは入力テンプレートだけ変形させることにする．そして，対象物体に対する特徴量を複数個用意

3. 3 目標領域特徴量に基づく初期位置探索法

し，入力画像の特徴量との内積を計算し，最大となる

提案する目標領域特徴量に基づく初期位置探索法のものを選び出す．内積の計算時間が増えることになる

基本的方法は以下のとおりである．テンプレート画像

が，全体の計算時間が大きく変わることはない．

の抽出したい物体領域の中心を，特徴量を抽出する点

また，スケールに関しても，入力画像のスケールの(x, y) とし，そのおよその半径をスケール S として，種類におよそ比例して特徴抽出の計算時間が増加する．

特徴量抽出を行い，その特徴量を記憶する．その特徴

そこで，スケールの小さな変化に関してはテンプレー

量をテンプレート特徴量と呼ぶ．入力画像を複数ス

トの方で対応することにする．例えば，実験では，入ケールと格子点走査で特徴量を求め，その中から，テ力画像に対するスケール変化は 2 倍 (rS = 2) とし，

ンプレート特徴量との内積が大きい特徴量を出力した

テンプレートでは，S0 と座標を，検出位置とする．また，両者の基準角の差は，を用いる．このようにすると，厳密には初期位置探索

物体領域の回転角と考えることできる．後段処理のたのための目標領域の大きさが多少異なることになるが，めに，1 点ではなく複数の候補点の抽出を行いたい場

スケールを

合は，内積が大きい順番に複数個の特徴量を抽出する

きる．

√

√

2S0 の 2 種類のスケール

2 ずつ変化させた初期位置探索が実現でこともできる．
335

電子情報通信学会論文誌 2020/4 Vol. J103–D No. 4

4. 計算機実験
4. 1 フーリエ記述エッジ方向ヒストグラムの回転
共変性の領域，Bark では左上の突出した領域，UBC では中
心の窓の領域とするために，検出目標座標及び初期ス
ケールを，それぞれ，(430, 310) 及び 150，(425, 340)
及び 200，(350, 255) 及び 100，(410, 240) 及び 100

3.1 で説明した，フーリエ記述エッジ方向ヒストグとした．そして，テンプレート画像に，検出目標位置

ラムの回転共変性を，最大位置検出の実験で示す．画を中心として無変換も含めて 9 種類の Aﬃne 変換を

像には Lenna を使い，線形補間による座標変換で画施し，初期スケールとその像を 1 度づつ回転させ，中心座標 (256, 256)，スケーて特徴量を求めた．入力画像には，img2〜img6 を用√

2 倍のスケールを用い

ル 60 画素で Q = 4 のフーリエ記述エッジ方向ヒスト

いた，4 種類のデーターベースの入力画像に対するス

グラムの最大位置を，1/16 度の精度で検出した．そのケールの組は，それぞれ，{80, 160}，{75, 150, 300}，

結果を図 5 に示す．Lenna の原画像において，1/16{25, 50, 100}，{50, 100, 200} で，同じデータベースの度の精度で検出した Q = 4 のフーリエ記述エッジ方

画像に対しては同じスケールの組を用いた．特徴量を向ヒストグラムの最大位置は 31.0625 度である．した求める中心点をスケールの 0.2 倍の幅で移動させ，特がって，画像を回転させたときに検出される最大位置

徴量を求めた．ASIFT/ASURF+RANSAC のテンプが，31.0625 と回転角を加算したものになれば，回転レート画像は，img1 から切り出した．それぞれのテ共変性が示されたことになる．図 5 から，フーリエ記

ンプレート画像を図 6〜9 の (a) に示す．入力画像は，

述エッジ方向ヒストグラムによる最大位置検出に回転提案手法と同じである．ASIFT/ASURF+RANSAC

共変性があることが確認できる．また，検出した最大は，OpenCV (Version 3.4.1) の ASIFT/ASURF と点の角度と画像回転角の差は，31.0625 ± 0.0625 に収RANSAC をライブラリーとして使う python の公開

まっている．

されているプログラム [25] を，パラメータを含めてほ4. 2 初期位置探索

ぼそのまま利用したが，計算時間短縮のために，テン

提案手法の性能を調べるために，画像を探索し目標プレートに対してだけアフィン変換を行い，入力画像とする領域のおよその位置を検出する実験を行った．

に対しては変換を行わなかった．

また，その結果を ASIFT/ASURF+RANSAC と比較

図 6〜9 の (b)〜(f) に，提案手法によって特徴量のした．ASURF は，SIFT に対する ASIFT と同様に，相関が最も大きくなった，中心点とスケールを図示すAﬃne 変換した画像を利用することによって，SURF

る．図中の線分は，エッジ方向ヒストグラムが最大にによるマッチングを Aﬃne 変換に関して頑健にしたもなる基準方向を示している．この方向が物体に対してのである．実験に用いる画像データセットは，Graﬃti

一定していない理由は，複数種類あるテンプレートの(800×640 画素)，Boat (850×680)，Bark (765×512

基準方向が物体に対して異なるためである．

画素)，UBC (800 × 640) [24] である．Graﬃti は，グ

検出位置の評価には，検出位置をデータベースに記レイスケール画像に変換して用いた．それぞれ，6 種類載されているホモグラフィー行列で逆変換し，テンプの画像 (img1〜img6) からなる．目標領域は，Graﬃti

レート画像上での検出位置とその目標位置との誤差をでは img1 の人物の領域，Boat では img1 のボート用いた．この誤差が，走査ステップ幅に相当するテン
プレート画像の最大スケールの 0.2 倍以内であるとき，正しい検出とした．提案手法と ASIFT+RANSAC では，この実験の全ての画像に対して，位置を正しく検出できた．ASURF+RANSAC では，Bark の最も難しい画像 img6 に対しては検出位置が画像範囲をはみ出し，正しく位置検出ができなかった．
表 1 に，計算時間とその標準偏差を示す．使用
した計算機の CPU は，Intel(R) Core(TM) i5-6400

CPU @ 2.70GHz である．表中の値は，提案手法，
図5336

フーリエ記述エッジ方向ヒストグラムによる最大位
置の回転共変性ASIFT/ASURF+RANSAC ともに，テンプレートの 作 成 時 間 は 除 い た も の で あ る ．こ の 結 果 か ら ，

論文／領域画像マッチングのための目標領域特徴量による初期位置探索法

図 6 Graﬃti の初期探索結果（(b)–(f) の円の中心が検出位置，半径が検出したスケー
ルを表す．
）

図 7 Boat の初期探索結果（(b)–(f) の円の中心が検出位置，半径が検出したスケールを
表す．
）

図8

Bark の初期探索結果（(b)–(f) の円の中心が検出位置，半径が検出したスケールを表す．
）

図 9 UBC の初期探索結果（(b)–(f) の円の中心が検出位置，半径が検出したスケールを表す．
）
表1
データセット名 \ 初期位置検出手法
Graﬃti
Boat
Bark
UBC

計算時間 (second)

ASIFT+RANSAC
1.47±0.20
11.9±3.4
0.686±0.034
1.09±0.27

ASURF+RANSAC
0.60±0.04
1.49±0.51
0.131±0.009
0.277±0.007

提案手法
0.611±0.007
0.853± 0.008
0.834± 0.012
0.871± 0.010

ASURF+RANSAC は多くの画像で提案手法よりも像内容に対してほとんど依存しないため，データセッ

高速であるが，Boat の場合には，平均で提案手法のト内での計算時間の標準偏差が 1.5%以下となった．

1.5 倍以上の時間がかかっており，必ず高速というこ

4. 3 劣化した入力画像に対する初期位置探索とはできない．ASIFT+RANSAC に対しては，Bark

入力画像に対して，標準偏差 6 画素のガウス平滑化，で多少劣っている以外は提案手法の方が高速である．

角度 π/6 rad の長さ 25 画素ので移動平均，標準偏差特に，Boat に関しては提案手法よりも計算時間が平80 の加法性白色ガウス雑音の 3 種類の劣化を施した入均で 10 倍以上となった．そして，提案手法では画素数

力画像に対して初期位置探索を行った．表 2 は，劣化とスケールだけで計算量/時間がほとんど決まり，画がない場合を含めて，その結果をまとめたものである．
337

電子情報通信学会論文誌 2020/4 Vol. J103–D No. 4
表 2 劣化した入力画像に対する初期位置探索
劣化
初期位置検出手法 DN \ INO
ASIFT
Graﬃti+RANSAC
Boat
Bark
UBC
ASURF
Graﬃti+RANSAC
Boat
Bark
UBC
提案手法
Graﬃti
Boat
Bark
UBC

2













3













なし
4
5
 
 
 
 
 
 
 
 
 
 
 
 

6





×







2

×
×
×

×
×






ガウス平滑化3
4
5
6
 × × × × × ×× × × ××   ×
 × × ×× × × ×
 × × ×            ×   

2

×

×


×






移動平均
3
4
5
× × 
  ×
× × ×
× × ×
×  ×
× × 
 × ×
  
  
  
  
  

6
×

×

×
×
×



×


加法性白色ガウス雑音
2
3
4
5
6
       ×
 × × ××       ×   ×× × × ××               ×    

(DN: データセット名，INO：画像番号．：e ≤ 0.2s，：0.2s < e ≤ s，×：それ以外．
ここで，e は検出誤差，s はテンプレート画像での最大スケール．)

表3
初期位置検出手法
SIFT+RANSACSURF+RANSAC
提案手法

文字を埋め込んだ入力画像に対する初期位置検出率 (%)

精度 \ 検出対象数字

+

+

+

0
16
22
0
0
92
100

1
0
0
0
0
50
84

2
16
24
0
0
90
94

3
14
16
0
0
86
92

4
6
8
0
0
74
78

5
0
8
0
0
76
82

6
4
6
0
0
86
88

7
2
4
0
0
90
92

8
8
10
0
0
78
82

9
0
0
0
0
70
90

全平均
6.6
9.8
0.0
0.0
79.2
88.2

(：e ≤ 0.2s， + ：e ≤ s．ここで，e は検出誤差，s はテンプレート画像での最大スケール．
)

（正しい検出），（ほぼ正しい検出），×（誤検出/検出不可）は，それぞれ，位置検出誤差がテンプレー
ト画像上でその最大スケールの 0.2 倍以内，0.2 倍より大きく最大スケール以内，最大スケールより大きいか検出されないことを表している．表 2 から，3 種類の劣化に対して提案手法が ASIFT/ASURF+RANSAC
よりも頑健であることがわかる．特徴点に基づく方法

図 10

手書き数字 (0) を埋め込んだ入力画像の例

が劣化に対する頑健性が劣る理由は，特徴点のスケー
ルが目標領域のスケールより小さく，平滑化する領域が狭く特徴点の位置や特徴量の変動が大きくなるため枚の画像を入力画像とした．テンプレート画像は埋めと考えられる．

込んだ数字だけの画像とした．画像を変形しないため，

4. 4 特徴点数が少ないテンプレート画像に対する初期位置探索各手法ともテンプレート画像を変形せずに初期位置探索を行った．提案手法で用いたスケールはテンプレー√

特徴点数が少ないテンプレート画像対する提案手法

ト画像で 8, 8 2，入力画像で 27, 54 とした．テンプの優位性を示すため，手書き数字の初期位置探索を行っレート画像の 8 に対応するスケールは入力画像で 32た．ここでの Bark に手書き数字を埋め込むという設となるが，その値からは 1/21/4 倍程度ずらした．画

定は，岩石や砂に覆われた自然情景の中に特定の対象像の例を図 10 に，実験結果を表 3 に示す． 及びが紛れているような，例えば岩肌に書かれた相対的に +  の行は，それぞれ，目標位置をスケールの 0.2

小さな手書き文字図形など，人間でも検出が難しい状倍以内及びスケール以内の誤差で検出できた割合であ況での初期位置探索の実行を想定している．MNISTる．表 3 から，次のことがわかる．SURF+RANSACの各カテゴリーの訓練画像 (28×28 画素) から最初のでは全く検出できなかった．SIFT+RANSAC の場合，10 個づつを取り出し，時計回りに 0.2π rad 回転，4 倍スケール以内の検出誤差でも平均 9.8%の検出率となっに拡大し，Bark の img2〜img6 に埋め込んだ計 500

た．提案手法では，検出誤差がスケールの 0.2 倍以内

338

論文／領域画像マッチングのための目標領域特徴量による初期位置探索法

で平均 79.2%，スケール以内で平均 88.2%となり，特sensus: A paradigm for model ﬁtting with applica-

徴点の少ないテンプレート画像に対して，提案手法がtions to image analysis and automated cartography,”Commun. ACM, vol.24, no.6, pp.381–395, June 1981.

有効であることがわかる．

5. む す び[7]

飯島泰蔵，パターン認識理論，森北出版，東京，日本，
1989.

[8]

S. Baker and I. Matthews, “Lucas-kanade 20 years
on: A unifying framework,” Int. J. Comput. Vis.,

マッチングにおける領域画像マッチングの手法は，
特徴画像マッチングの手法と比較して，より高精度なvol.56, no.3, pp.221–255, Feb. 2004.
[9]

T. Wakahara, Y. Kimura, and A. Tomono, “Aﬃne-

マッチング性能の可能性をもつものの処理時間が膨大

invariant recognition of gray-scale characters us-

化するという課題がある．特に，whole-to-part の物

ing global aﬃne transformation correlation,” IEEE

体探索に用いる場合，マルチスケールでのスライド窓

Trans. Pattern Anal. Mach. Intell., vol.24, no.4,

探索の処理負担が大きい．この課題を解決するため，

pp.384–395, April 2001.
[10]

Y.

Yamashita

andT.

Wakahara,“Aﬃne-

本論文では領域画像マッチングのための目標領域特transformation and 2D-projection invariant k-NN

徴量を用いた高速な初期位置探索の手法を提案した．

classiﬁcation of handwritten characters via a newmatching measure,” Pattern Recognition, vol.52,

特徴画像マッチングの手法である ASIFT/ASURF とRANSAC の組合せによる初期位置探索との比較実験

pp.459–470, April 2016.
[11]

S. Zhang, T. Wakahara, and Y. Yamashita, “Imageを行った結果，抽出される特徴点数が少ない場合や

matching using GPT correlation associated with sim-

画像劣化が大きい場合に提案手法の優位性が明らか

pliﬁed HOG patterns,” Proceedings of 2017 SeventhInternational Conference on Image Processing The-となった．また，初期位置探索に要する時間について

ory, Tools and Applications, vol.1, pp.1–6, Nov.–Dec.

も，提案手法は，特徴画像マッチング手法とほぼ同等であり，画像内容にほとんど依存しなかった．今後の

2017.
[12]

DATABASE of handwritten digits”.

課題は，領域画像マッチングとの組合せであり，例えば，GAT/GPT 相関法の初期位置探索としての実装

Y. LeCun, C. Cortes, and C.J. Burges, “The MNIST
http://yann.lecun.com/exdb/mnist/[13]

Q. Tong and T. Aoki, “A blur-invariant interest pointがある．

detector based on momentsymmetry for motion and

謝辞

gaussian blurred image matching,” International J.

本研究は JSPS 科研費 17K00250, 17H01760

Signal Processing, vol.2, pp.96–106, 2017.

の助成を受けたものである．
文
[1]

献

[14]

for motion blurred image matching,” Proceedings of

D.G. Lowe, “Distinctive image features from scale-

SPIE 10420, Ninth International Conference on Dig-invariant keypoints,” International Journal of Computer Vision, vol.60, no.2, pp.91–110, Nov. 2004.
[2]

ital Image Processing, pp.104201E–1–6, May 2017.
[15]

siﬁcation using random forests and ferns,” Proceed-

tinctive representation for local image descriptors,”

ings of the 2007 IEEE 11th International Conference

Conference on Computer Vision and Pattern Recog-on Computer Vision, pp.1–8, Oct. 2007.
[16]

nition, pp.506–513, CVPR’04, IEEE Comput. Soci.,
citation.cfm?id=1896300.1896374

demic Publishing, Jan. 2014.
[17]

Dense correspondence across scenes and its appli-

up robust features,” Computer Vision -ECCV 2006,

cations,” IEEE Trans. Pattern Anal. Mach. Intell.,H. Bay, A. Ess, T. Tuytelaars, and L. Van Gool,vol.33, pp.978–994, Jan. 2011.
[18]

V. Kober, “Fast algorithms for the computation of“Speeded-up robust features (SURF),” Computer Vi-

sliding discrete sinusoidal transforms,” IEEE Trans.

sion and Image Understanding, vol.110, no.3, pp.346–

Signal Process., vol.52, no.6, pp.1704–1710, June

359, June 2008.
J.-M. Morel and G. Yu, “ASIFT: A new framework

2004.
[19]

E. Elboher and M. Werman, “Cosine integral images

for fully aﬃne invariant image comparison,” SIAM

for fast spatial and range ﬁltering,” Proceedings ofJournal on Imaging Sciences, vol.2, no.2, pp.438–469,

2011 18th IEEE International Conference on Image

April 2009.
[6]

C. Liu, J. Yuen, and A. Torralba, “SIFT Flow:

H. Bay, T. Tuytelaars, and L.V. Gool, “Surf: Speeded
pp.404–417, 2006.

[5]

P. Podbreznik and B. Potocnik, Dense feature matching method based on ASIFT, LAP LAMBERT Aca-

Washington, DC, USA, 2004. http://dl.acm.org/[4]

A. Bosch, A. Zisserman, and X. Muñoz, “Image clas-

Y. Ke and R. Sukthankar, “PCA-SIFT: A more disProceedings of the 2004 IEEE Computer Society[3]

Q. Tong and T. Aoki, “A blur-invariant local feature

M.A. Fischler and R.C. Bolles, “Random sample con-

Processing, pp.89–92, Sept. 2011.
[20]

K. Sugimoto and S.-I. Kamata, “Compressive bilat-339

電子情報通信学会論文誌 2020/4 Vol. J103–D No. 4eral ﬁltering,” IEEE Trans. Image Process., vol.24,
no.11, pp.3357–3369, Nov. 2015.
[21]

杉本憲治郎，京地清介，鎌田清一郎，“離散コサイン変換に基づく定数時間ガウシアンフィルタの包括的性能解析，”
信学技報，vol.117, no.48, IE2017-4, pp.19–24, May

[22]

2017.
山下幸彦，若原 徹，“領域画像マッチングのための初期” 信学技報，PRMU2018-53, Sept. 2018.
探索法，

[23]

U.A. Ahmad, K. Kidiyo, and R. Joseph, “Texture features based on local fourier histogram: selfcompensation against rotation,” IEEE Trans. Image Process., vol.17, no.3, pp.(030503–1)–(030503–3),
July–Sept. 2000.

[24]

Visual Geometry Group,

University of Oxford,“Aﬃne covariant features”.
http://www.robots.ox.ac.uk/˜vgg/research/aﬃne/[25]

A. Alekhin, “Aﬃne invariant feature-based image
matching sample”. https://github.com/opencv/
opencv/blob/master/samples/python/asift.py（2019 年 6 月 26 日受付，10 月 8 日再受付，
12 月 13 日早期公開）

山下

幸彦

（正員）

昭和 58 東工大・工・電子電気工学科，昭和 60 同大・理工・情報工学修士修了．同
年日本原子力研究所入社．昭和 63 年 (株)アイザック入社，現在，東工大・環境社会・融合理工准教授．画像処理の研究に従事．
博士（工学）．

若原

徹

（正員）

昭 50 東大・工・物理工学卒．昭 52 同大
大学院修士課程了．同年日本電信電話公社（現 NTT）入社．平 13 から法政大学情報科学研究科教授，現在に至る．文字・図形
認識，画像マッチングの研究に従事．工博．

340