CV Reading Matching Local Self-Similarities across Image and Videos

CV Reading
Matching Local Self-Similarities across Image and Videos
永橋知行
2009 年 4 月 21 日
1
はじめに
テンプレート画像が入力画像中のどこにあるかを見つける問題は，コンピュータビジョンの初
期から行われている重要な問題の１つである．現在までに，これらの問題を扱った手法が数多
く提案されている．しかし，多くの手法はテンプレート画像と入力画像が同じ物体を対象とし
ている．そのため，物体の構造が同じであっても色，テクスチャ，エッジが異なる場合の検出
は難しい．このような構造が同じ物体の検出に対して，Shechtman らは自己相関を用いた特徴
量記述法である Self-similarity descriptor を提案している [1]．また，この手法は動画像にも拡
張かのであることを示している．
今回は，CVPR2007 で発表された “Matching Local Self-Similarities across Image and Videos”
について述べる．
2
従来法とその問題点
画像や動画像のマッチング手法やそれに用いられる特徴量として以下のものが提案されている．
• 輝度/色情報を用いた手法 [2][3][4]
• テクスチャフィルタ [5]，フィルタの応答 [6]
• 小領域による記述 [7]
• 微分を用いた記述 [8]
• シェイプ，エッジによる記述 [9]
これらの手法は，テンプレートと入力の画像的に同一の属性を持っているという仮定に基づい
ている．しかし，図 1 のように，同じ「ハート」の形でも色，テクスチャ，エッジが異なる画
像では，上記の手法のマッチングは困難である．しかし，人間はこれらの画像は「ハート」と
いう形で構成されていることを認識することができる．これは，
「ハート」という構造を認識し
ているからだと考えられる．この構造は，局所的なパターンの集合により構成されており，局
1
FLAB Work Document Apr, 2009
2
図 1: ハート形の物体
所パターンの配置によりその構造を理解している．これらの局所パターンを自己相関により記
述することで，色，テクスチャ，エッジに頑健な特徴を記述することができると考えられる．
3
局所自己相関を用いた画像マッチング
局所自己相関を用いた画像マッチングについて述べる．テンプレート画像を F (x, y)(動画像は
F (x, y, t))，入力画像を G(x, y)(動画像は G(x, y, t)) とし，この２つの比較を行う．
図 2 に，手法の流れを示す．ピクセル q を中心としたパッチと大きな領域（半径 40 ピクセル）
を作成し，領域内のパッチと q を中心としたパッチとの相関を求める．この領域内の相関を
さらに極座標系の小領域へ変換する．極座標系へ変換されたものを特徴量としたものを local
self-similarity descriptor dq とする．この dq を用いて F と G のマッチングを行う．
図 2: 手法の流れ
以下に，local self-similarity descriptor とそれを用いたマッチング手法について述べる．
FLAB Work Document Apr, 2009
3.1
3
Local Self-similarity Descriptor
ピクセル q を中心とした 40 × 40 の領域から local self-similarity descriptor を計算する．は
じめに，ピクセル q を中心とした 5 × 5 ピクセルのパッチと領域内のパッチを比較する．比較
には CIEL*a*b*の sum of square differences(SSD)SSDq (x, y) に基づいた correlation surface
Sq (x, y) を以下の式で計算する．
(
)
SSDq (x, y)
Sq (x, y) = exp −
(1)
max(varnoise , varauto (q))
ここで，varnoise 相関を求める際の許容範囲を決める定数で，varauto (q) は q を中心としたパッ
チと領域内のパッチの相関の最大値である．求めた領域内の Sq (x, y) を q を中心とした極座標
系へ変換する．極座標系に基づいて，80bin(方向:20, 半径:4) の小領域に分割する，各小領域内
の Sq (x, y) の最大値をその領域の値とし，それらを local self-similarity descriptor ベクトル dq
とする．最後に，dq を 0 から 1 に正規化する．
図 3 に，local self-similarity descriptor の抽出例を示す．図 3 のように，同じ構造の対応する
図 3: local self-similarity descriptor の抽出例
位置で同じ特徴量が抽出されていることがわかる．
3.2
Local Self-similarity Descriptor を用いた大域マッチング
テンプレート F と入力 G の local self-similarity descriptor の比較をすることで，対象物体の位
置を検出する．local self-similarity descriptor は局所特徴量なため，物体構造のマッチングを行
う際には画像中のすべての local self-similarity descriptor とマッチングする必要がある．そのた
め，計算量が非常に多くなる．この問題を解決する方法として，ensemble matching algorithm[3]
を用いている．また，イメージピラミッドによりスケール変化に対応している．
FLAB Work Document Apr, 2009
4
4
実験結果
実験として，テンプレート画像を用いた物体検出と従来法との比較，テンプレートにスケッチ
画像を用いた物体検出実験，動画像への拡張として動作検出実験を行う．
4.1
物体検出
図 4 に 1 つのテンプレート画像を用いての物体検出結果を示す．このように，テンプレート画
図 4: 物体検出例
像が 1 つであるが，画像中の花の位置を検出できていることがわかる．
また，テンプレートベースの物体検出の従来法との比較を図 5 に示す．図 5 より，テンプレー
トと入力画像が異なるテクスチャ，色，エッジが存在する場合でも，物体の構造が似ている位
置を検出できているのがわかる．
4.2
実画像とスケッチのマッチング
図 6 に，テンプレートにスケッチ画像を用いて検出実験を行った結果を示す．SIFT などの従
来法では，スケッチ画像と実画像とのマッチングは困難である．しかし，local self-similarity
descriptor では，スケッチをテンプレートとするだけで，実画像とのマッチングだけでなく，ロ
ゴなどとのマッチングも可能となる．
FLAB Work Document Apr, 2009
5
図 5: 従来法との比較
4.3
動作検出
local self-similarity descriptor は静止画のフレームワークを動画像へ拡張することができる．図
7 にテンプレートビデオの動作を入力ビデオ中から検出している結果を示す．このように，動
画像も静止画と同様のフレームワークで検出が可能となる．
5
おわりに
今回は，CVPR2007 で発表された “Matching Local Self-Similarities across Image and Videos”
についての文献調査を行った．
参考文献
[1] E. Shechtman and M. Irani: “Matching local self-similarities across images and videos”,
IEEE Conference on Computer Vision and Pattern Recognition 2007 (CVPR’07) (2007).
[2] L. Wolf, X. Huang, I. Martin and D. Metaxas: “Patch-based texture edges and segmentation”, ECCV06, pp. II: 481–493 (2006).
FLAB Work Document Apr, 2009
6
図 6: スケッチを用いた物体検出
[3] O. Boiman and M. Irani: “Detecting irregularities in images and in video”, Int. J. Comput.
Vision, 74, 1, pp. 17–31 (2007).
[4] S. Ullman, E. Sali and M. Vidal-Naquet: “A fragment-based approach to object representation and classification”, IWVF-4: Proceedings of the 4th International Workshop on
Visual Form, London, UK, Springer-Verlag, pp. 85–102 (2001).
[5] J. Malik, S. Belongie, J. Shi and T. Leung: “Textons, contours and regions: Cue integration in image segmentation”, ICCV ’99: Proceedings of the International Conference
on Computer Vision-Volume 2, Washington, DC, USA, IEEE Computer Society, p. 918
(1999).
[6] B. Schiele and J. L. Crowley: “Recognition without correspondence using multidimensionalreceptive field histograms”, Int. J. Comput. Vision, 36, 1, pp. 31–50 (2000).
[7] D. G. Lowe: “Distinctive image features from scale-invariant keypoints”, Int. J. Comput.
Vision, 60, 2, pp. 91–110 (2004).
[8] I. Laptev: “On space-time interest points”, Int. J. Comput. Vision, 64, 2-3, pp. 107–123
(2005).
FLAB Work Document Apr, 2009
7
図 7: 動作検出結果
[9] S. Belongie, J. Malik and J. Puzicha: “Shape matching and object recognition using shape
contexts”, IEEE Trans. Pattern Anal. Mach. Intell., 24, 4, pp. 509–522 (2002).