2 -- 2 2 2010 5 1 Interest Operator Scale Space Wavelet 1 DP 2-1 Interest Operator 2-1-1 Scale space 2-1-2 Wavelet 2-1-3 SIFT 2-1-4 2-2 2-2-1 DP 2-2-2 2-2-3 c 2012 1/(21)
2 -- 2 -- 2 2--1 2009 9 Interest Operator Scale Space Wavelet SIFT 2--1--1 Interest Operator 2 corner detector 1) SUSAN 3) Harris Shi Tomasi Good features to 2) track SUSAN Smallest Univalue Segment Assimilating Nucleus S p 0 p g t I(p) p SUSAN R(p 0 ) R(p 0 ) = max(0, g n(p 0 )), n(p 0 ) = c(p 0, p), c(p 0, p) = p S 1 if I(p 0 ) I(p) t 0 if I(p 0 ) I(p) > t Harris J. Shi C. Tomasi sum of squared difference, SSD p W v SSD (2 1) c 2012 2/(21)
S (p) = (I(q) I(q + v)) 2 q W (2 2) 1 I(q) x, y I x (q), I y (q) I(q + v) I(q) + [I x (q) I y (q)] v 2 S (p) = v T W Ix 2 W I x I y W I x I y W Iy 2 v = vt H(p) v (2 3) (2 4) H(p) p Harris Shi Tomasi λ 1, λ 2 Harris M = λ 1 λ 2 κ(λ 1 + λ 2 ) 2 = det(h) κ trace 2 (H) (2 5) κ Shi Tomasi M = min(λ 1, λ 2 ) (2 6) 2--1--2 Scale Space cm m nm km A. Witkin 7) scale space 2 1 Gaussian kernel I(x, y) t > 0 L(x, y, t) L : R 2 R + R 6) L t = 0 c 2012 3/(21)
t 2 1 L(x, y, 0) = I(x, y). t > 0 t g t (x, y) = 1 ( 2πt exp x2 + y 2 ) 2t (2 7) (2 8) L(x, y, t) L(x, y, t) = (g t I)(x, y) = g t (u, v)i(x u, y v)dudv. (2 9) t t ( ) L(x, y, t) = x x g t I (x, y) = x g t(u, v)i(x u, y v)dudv (2 10) 2--1--3 Wavelet wavelet 13) D. Gabor 12) g λ,θ,ϕ,σ,γ (x, y) = exp ( x 2 + γ 2 y 2 ) ) cos (2π x 2σ 2 λ + ϕ (2 11) (x, y ) = (x cos θ + y sin θ, x sin θ + y cos θ) (2 12) c 2012 4/(21)
電子情報通信学会 知識の森 http://www.ieice-hbkb.org/ 2 群 2 編 2 章 図 2 2 Gabor フィルタ gλ,θ,ϕ,σ,γ. 左端を標準に 順に σ, λ, θ を変化させた例 を使って信号の局所的な解析を試みた 図 2 2 しかしこの Gabor フィルタは 周波数領 域における広がりが固定されているところに問題があった 一般に L1 及び L2 ノルムが有限 すなわち Z Z Z Z ψ(x, y) 2 dxdy < ψ(x, y) dxdy <, (2 13) を満たす可積分関数 ψ(x, y) をマザーウェーブレットと呼ぶ このとき 1 W s f (x, y) = Z s Z f (u, v) ψ u x v y dudv, s s (2 14) を関数 f (x, y) の連続ウェーブレット変換と呼ぶ A. Grossman と J. Morlet8) は連続ウェーブ レット変換を研究し 最初に地震学上のデータの解析に応用した 図 2 3 Laplacian of Gaussian(左) と Gabor Filter(右) その後 I. Daubechies9) はある程度滑らかでコンパクトな台をもつ つまり値が 0 でない 領域が有界な 正規直交ウェーブレット基底を構成し S. Mallat10, 11) は Y. Meyer とともに 多重解像度解析 multiresolution analysis と呼ばれる ウェーブレット基底を構成する一般 的方法を提案した ウェーブレットは信号処理 画像解析 通信システム レーダ システ ム制御など 多彩な分野で応用されている 特徴点検出で使われる代表的なウェーブレットとして 上記の Gabor フィルタのほかに 次項に述べる SIFT にも使われる Laplacian of Gaussian LoG や Difference of Gaussian 電子情報通信学会 知識ベース c 電子情報通信学会 2012 5/(21)
DoG (2 8) Laplacian ( ) 2 x + 2 g 2 y 2 t (x, y) (2 15) LoG f (x, y) blob 2--1--4 SIFT D. Lowe SIFT Scale-Invariant Feature Transform 5) SIFT 1. 2. 3. 4. SIFT 6) LoG LoG DoG LoG 2 4 X-Y- 3 DoG 2 4 DoG c 2012 6/(21)
DoG D(p) : D 2 x D x D y H = D x D. (2 16) y D 2 x Harris SIFT trace 2 (H)/ det(h) D(p) L m(p) θ(p) : m(p) = (L(p + x) L(p x)) 2 + (L(p + y) L(p y)) 2, (2 17) ( ) L(p + y) L(p y) θ(p) = tan 1. (2 18) L(p + x) L(p x) 36 80% 2 5 SIFT 2 5 8 4 4 c 2012 7/(21)
SIFT 8 4 4 = 128 c 2012 8/(21)
2 -- 2 -- 2 2--2 2009 9 DP 2--2--1 1 Template Matching T M T N T I M I N I 2 6 T I S D (i, j) (i, j) T i j y x template T input I 2 6 cross-correlation S CC (i, j) = (x,y) T I(i + x, j + y)t(x, y) (2 19) T T {[1, M T ] [1, N T ]} S CC I T 180 T FIR matched filter S CC normalized cross-correlation S NCC (i, j) = S CC (x,y) T T 2 (x, y) (x,y) T I 2 (i + x, j + y) (2 20) S CC S NCC T 1 (2 20) T c 2012 9/(21)
D p (i, j) = I(i + x, j + y) T(x, y) p (x,y) T 1/p (2 21) p = 1 p = 2 p = D max (i, j) = max I(i + x, j + y) T(x, y) (2 22) (x,y) T 2 I(i + x, j + y) T(x, y) 0 1 I(i + x, j + y)t(x, y) 0 21) 2 A, B A B 22) A, B 23, 24) MPEG 25) 3 (2 19) S CC I O(M I N I M T N T ) 2 2 a S CC (i, j) M I N I (i, j) S CC (i, j) c 2012 10/(21)
b coarse-to-fine strategy I, T T 2 n O(M I N I M T N T ) 2 4n 2 n+1 I T c SSDA Sequential Similarity Detection Algorithm: SSDA 26, 27) (2 21) p = 1 D 1 (i, j) I(i + x, j + y) T(x, y) θ T D 1 (i, j) M T N T D 1 θ SSDA D 1 D 1 D 1 26) r ( M T N T ) θ r θ r = λ(r + K r) (2 23) K λ T I λ T I 27) d (2 19) (i, j) (i, j) (i, j + 1) (i, j) (i, j + 1) (i, j) (i, j + 1) 28) (i, j) T I T H T (i, j) I M T N T H I,(i, j) c 2012 11/(21)
S H (i, j) = min ( H T (k), H I,(i, j) (k) ) k (2 24) k 0 S H (i, j) 1 S H (i, j ) min (S H(i, j) B, A B ) + A B A (2 25) A, B (i, j ) (i, j) A B A B A B A B A = B A B (2 25) S H (i, j) S H (i, j ) S H (i, j ) S H (i, j ) S H S CC S H S CC e (2 19) S CC T I T I S CC S CC FFT 4 a 29) S CC (i, j) S CC (i, j) 30) b i j 4.5 12.5 0.5 1/2 H.264/AVC 1/4 29) c 2012 12/(21)
電子情報通信学会 知識の森 http://www.ieice-hbkb.org/ 2 群 2 編 2 章 c 弾性マッチング 2 パターンをマッチングする際 一方に微小な歪み ずれ があると整合性が急に悪くな る このため マッチングの際 一方のパターンをゴムのように非線形伸縮させ 最も整合 した時点をマッチング結果とすることがある 要するに画像をゴム膜のように変形させなが らマッチングを図る技術であり これは弾性マッチングと呼ばれる 弾性マッチングの実体 は画素対応関係を表現する線形もしくは非線形写像の最適化であり したがって様々な最適 化手法がこれに利用されている31, 32, 33, 34) 5 特徴点を用いたマッチング 以上のテンプレートマッチングはあくまで画像と画像の照合に基づくものであった これ に対し 両方の画像から複数の特徴点を抽出しておき それら特徴点における特徴量に基づ いてマッチングを求める方法がある すなわち画像 I と T それぞれにおいて 2--1--4 節で述 べた SIFT などによる特徴点を多数抽出し 次に T の特徴点それぞれについて それと最も 類似した特徴量をもつ特徴点を I 上に探索することで I と T の間に点対応を求める その 後 その点対応を用いて 最終的な位置合せ すなわち T に対応する I の領域を求める 図 2 7 は SIFT 特徴点 特徴量を用いた 2 画像 I, T のマッチング結果である ここではテ ンプレート T として I の一部を回転させたものを用いている 回転による誤差で T と I の 間には差異があることに注意されたい 同図右が上述の方法で点対応を求めた結果である ただし その類似度が閾値以下のものは省略している 単純な方法ながら 非常に高い精度 でのマッチング実現されている I T Input and template SIFT keypoints keypoint matching result 図 2 7 特徴点を用いたマッチング 位置合せを行うためには この対応結果を用いて T の移動量や回転量の推定を行うこと になる より一般的に いずれかの画像が射影変換を受けている場合は 射影変換パラメー タの推定することになる 最小二乗法によりパラメータ推定を行うことも考えられる しか し 点対応関係は不安定になることもあり 大きく誤った点対応が 全体的な推定結果に悪 影響を与えることもあり得る このため RANSAC35) のようなロバスト推定法が利用される ことも多い 電子情報通信学会 知識ベース c 電子情報通信学会 2012 13/(21)
2--2--2 DP 1 1 2--2--1(c) Dynamic Programming DP DTW Dynamic Time Warping DP 2 2 8(a) DP 2 pattern Y j pattern Y j j=u i pattern X i pattern X i (a) (b) 2 8 DP 36, 37, DP 1960 1970 38) I J O(IJ) 39, 40) DNA 43, 44) DP DP R.Bellman 41) 42) 2 X = x 1, x 2,..., x i,..., x I, Y = y 1, y 2,..., y j,..., y J x i y j X i x i Y j y j j = u i (i = 1,..., I) d i (u i ) = x i y ui (2 26) c 2012 14/(21)
minimize F = I d i (u i ), i=1 with respect to u 1,..., u I, subject to 0 u i u i 1 2, u 1 = 1, u I = J (2 27) (i) u i u i 1 (ii) u i u i 1 j = u i du i /di 2 2 DP (2 27) min F = min u 1,...,u I 0 u i u i 1 2 i=1 = min u 2,...,u I 0 u i u i 1 2 {} I d i (u i ) I d i (u i ) + d 2(u 2 ) + i=3 min u 1 0 u 2 u 1 2 d 1 (u 1 ) (2 28) g 2 (u 2 ) = d 2 (u 2 ) + min F = min u 2,...,u I 0 u i u i 1 2 min u 1 0 u 2 u 1 2 d 1 (u 1 ) I d i (u i ) + g 2 (u 2 ) i=3 (2 29) (2 30) u 1 (2 29) min u 1 min F = min u 3,...,u I 0 u i u i 1 2 {} I d i (u i ) + d 3(u 3 ) + i=4 min u 2 0 u 3 u 2 2 g 2 (u 2 ) (2 31) g 3 (u 3 ) = d 3 (u 3 ) + min F = min u 3,...,u I 0 u i u i 1 2 min u 2 0 u 3 u 2 2 g 2 (u 2 ) I d i (u i ) + g 3 (u 3 ) i=4 (2 32) (2 33) c 2012 15/(21)
u 2 g i (u i ) = d i (u i ) + min u i 1 0 u i u i 1 2 g i 1 (u i 1 ) (2 34) min F = min u I g I (u I ) (2 35) F u I = J min F = g I (J) DP DP u 1,..., u i,..., u I (2 34) DP DP DP i = 1 I j 2 8(b) I J DP (2 34) Input: Output: Initialization: X = x 1, x 2,..., x i,..., x I, Y = y 1, y 2,..., y j,..., y J min F: Minimum elastic matching distance between X and Y. u 1,..., u i,..., u I : Optimal elastic matching between X and Y. 1: g i ( j) = and b i ( j) = nil for i, j DP Recursion: 2: g 1 (1) = d 1 (1) = x 1 y 1 3: for i = 2 to I do 4: for j = 1 to J do 5: d i ( j) = x i y j 6: g i ( j) = d i ( j) + min i 1( j ) max( j 2,1) j j 7: b i ( j) = argmin max( j 2,1) j j g i 1 ( j ) Termination: 8: min F = g I (J) 9: u I = J 10: for i = I 1 downto 1 do u i = b i+1 (u i+1 ) 2 9 DP DP 2 9 6 DP 10 10 DP min F u I,..., u i,..., u 1 DP c 2012 16/(21)
J I O(IJ) 3 DP DP i g i (u i ) DP g i (u i ) (u i i) 2 9 4 j for j = i ɛ to i + ɛ do ɛ( J) DP 45) DP 46) DNA FASTA BLAST 43, 44) 4 DNA 44) 2 10 DP 2 44) pattern Z pattern Y pattern X 2 10 2--2--3 c 2012 17/(21)
30 2 3 14) G 1 = (V 1, E 1 ), G 2 = (V 2, E 2 ), V i E i u, v V 1 u, v G 1 (u, v) E 1 2 1 1 1 f : V 1 V 2 (2 36) (u, v) E 1 = ( f (u), f (v)) E 2 (u, v) E 1 = ( f (u), f (v)) E 2 (2 37) (2 38) f 1 1 u v f (u) f (v) (2 37)(2 38) 2 11 (2 38) (2 37) f f (2 37) f 2 maximum common subgraph, MCS 2 20) c 2012 18/(21)
MCS J.R. Ullman 15) 2 (2 37) error-correcting error-tolerant H. Bunke MCS 17) W.H. Tsai K.S. Fu 16) M. Fischler R. Elschlager 18) relaxation labeling 19) c 2012 19/(21)
1) S.M. Smith and J.M. Brady, SUSAN - a new approach to low level image processing, Int l J Comput. Vision, vol.23, no.1, pp.45-78, 1997. 2) J. Shi and C. Tomasi, Good Features to Track, Proc. IEEE Comp. Soc. Conf. Comput. Vision and Patt. Recogn., pp.593-600, 1994. 3) C. Harris and M. Stephens, A combined corner and edge detector, Proc. 4th Alvey Vision Conf., pp.147-151, 1988. 4) J. Matas and O. Chum, M. Urba and T. Pajdla, Robust wide baseline stereo from maximally stable extremal regions, Proc. British Machine Vision Conf., pp.384-396, 2002. 5) D. Lowe, Distinctive image features from scale-invariant keypoints, Int l J Comput. Vision, vol.60, no.2, pp.91-100, 2004. 6) Lindeberg, T., Scale-space theory: A basic tool for analysing structures at different scales, J Appl. Stat., vol.21, no.2, pp.224-270, 1994. 7) A. Witkin, Scale-space filtering, Proc. Int l Joint Conf. on Artif. Intell., pp.1019-1022, 1983. 8) A. Grossman and J. Morlet, Decomposition of Hardy functions into square integrable wavelets of constant shapes, SIAM J. Math. Anal., vol.15, no.4, pp.723-736, 1984. 9) I. Daubechies, Orthonormal Bases of Compactly Supported Wavelets, Comm. Pure Appl. Math., vol.41, pp.909-996, 1988. 10) S. Mallat, Multiresolution Approximations and Wavelet Orthonormal Bases of L 2 (R), Trans. Amer. Math. Soc., vol.315, pp.69-87, 1989. 11) S. Mallat, A Theory for Multiresolution Signal Decomposition: The Wavelet Representation, IEEE Trans. Patt. Anal. Mach. Intell., vol.11, no.7, pp.674-693, 1989. 12) D. Gabor, Theory of Communication, J. IEE, vol.93, no.26, pp.429-457, 1946. 13) G. Strang and T. Nguyen, Wavelets and Filter Banks, Cambridge Univ. Press, 1996., I, II, 1999. 14) D. Conte, P. Foggia, C. Sansone and M. Vento, Thirty Years of Graph Matching in Pattern Recognition, Int l J Patt. Recogn., vol.18, no.3, pp.265-298, 2004. 15) J.R. Ullman, An algorithm for subgraph isomorphism, J. Assoc. Comput. Mach., vol.23, pp.31-42, 1976. 16) W.H. Tsai and K.S. Fu, Error-correcting isomorphisms of attributed relational graphs for pattern analysis, IEEE Trans. Syst. Man Cybern., vol.9, pp.757-768, 1979. 17) H. Bunke, On a relation between graph edit distance and maximum common subgraph, Patt. Recogn. Lett., vol.18, pp.689-694, 1997. 18) M. Fischler and R. Elschlager, The representation and matching of pictorial structures, IEEE Trans. Comput., vol.22, pp.67-92, 1973. 19) S. Umeyama, An eigendecomposition approach to weighted graph matching problems, IEEE Trans. Patt. Anal. Mach. Intell., vol.10, pp.695-703, 1988. 20) A.P. Ambler, H.G. Barrow, C.M. Brown, R.M. Burstall and R.J. Popplestone, A versatile computercontrolled assembly system, Proc. Int l Joint Conf. on Artif. Intell., pp.298-307, 1973. 21) J.D. Tubbs, A Note on Binary Template Matching, Patt. Recogn., vol.22, no.4, pp.359-365, 1989. 22),,, vol.60, no.3, pp.313-320, 2006. 23) S.S. Beauchemin and J.L. Barron, The Computation of Optical Flow, ACM Comput. Surv., vol.27, no.3, pp.433-467, 1995. 24),, CVIM, 2006-CVIM-152, 2006. 25),, BP, 1996. c 2012 20/(21)
26) D.I. Barnea and H.F. Silverman, A Class of Algorithms for Fast Digital Image Registration, IEEE Trans. Comput., vol.c-21, no.2, pp.179-186, 1972. 27),,, vol.c-21, no.2, pp.179-186, 1972. 28) V.V. Vinod,, (D), vol.j81-d-ii, no.9, pp.2035-2042, 1998. 29), : 3D,, vol.90, no.8, pp.680-685, 2007. 30) L.G. Brown, A Survey of Image Registration Techniques, ACM Comput. Surv., vol.24, no.4, pp.325-376, 1992.,, bit, pp.78-119, 1994 11 31) A.K. Jain, Y. Zhong and M. -P. Dubuisson-Jolly, Deformable Template Models: A Review, Signal Process., vol.71, no.2, pp.109-129, 1998. 32) C.A. Gralbey and K.V. Mardia, A Review of Image-Warping Methods, J Appl. Stat., vol.25, no.2, pp.155-171, 1998. 33) H. Lester and S.R. Arridge, A survey of hierarchical non-linear medical image registration, Patt. Recogn., vol.32, no.1, pp.129-149, 1999. 34) S. Uchida and H. Sakoe, A survey of elastic matching techniques for handwritten character recognition, IEICE Trans. Inf. & Syst., vol.e88-d, no.8, pp.1781-1790, 2005. 35) M.A. Fischler and R.C. Bolles, Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography, Commun. ACM, vol.24, no.6, pp.381-395, 1981. 36),,, vol.27, no.9, pp.483-490, 1971. 37) H. Sakoe and S. Chiba, A Dynamic Programming Algorithm Optimization for Spoken Word Recognition, IEEE Trans. Acoust. Speech and Signal Proc., vol.assp-26, no.1, pp.43-49, 1978. 38) H. Sakoe, Two-Level DP-Matching Algorithm A Dynamic Programming Based Pattern Matching Algorithm for Continuous Speech Recognition, IEEE Trans. Acoust. Speech and Signal Proc., vol.assp- 27, no.6, pp.588-595, 1979. 39) and,,, vol.30, no.9, pp.1058-1066, 1989. 40), DP,, vol.prmu2006-166, 2006. 41) R. Bellman and S. Dreyfus, Applied Dynamic Programming, Princeton Univ. Press, 1962. 42),,, 1968. POD, 2005 43) R. Durbin, S. Eddy, A. Krogh and G. Mitchison, Biological Sequence Analysis, Cambridge Univ. Press, 1998. 44),,, 2007. 45) C. Raphael, Coarse-to-fine dynamic programming, IEEE Trans. Patt. Anal. Mach. Intell., vol.23, no.2, pp.1379-1390, 2001. 46), DP, (D), vol.j90-d, no.8, pp.2137-2146, 2007. c 2012 21/(21)