DEIM Forum 2012 B5-3 606 8510 E-mail: {zhao,ohshima,tanaka}@dl.kuis.kyoto-u.ac.jp Web, 1. Web Web TinEye 1 Google 1 http://www.tineye.com/ 1 2. 3. 4. 5. 6.
2. 30 Visual Words TF-IDF Lowe [4] Scale-Invarient Feature Transform (SIFT) Bay [1] Speeded Up Robust Features (SURF) SIFT 128 SURF 64 Visual Words Nister [2] SIFT SURF K-means K-means 7 K-means 1,111,111 K-means L1 L2 Visual Words Brown SIFT kd k m m = 6 RANSAC 3. : 1 : 10 (a) (b) (c) ( ) 1 1 2
3. 1 画像の類似性 画像の類似性とは ある画像全体の特徴と 別のある画像 全体の特徴が類似しているということである ある画像集合 In ={img1, img2,..., imgi,..., imgn } があるとする ここで n は画像集合の画像の数である そのうちの 1 つの画像 imgi が入力として与えられたとき 出力として その画像と類似す る他の画像集合が得られるとする この機能は 2 つの画像の (a) Image1 (b) Image2 (c) Image3 (d) Image4 (e) Image5 (f) Image6 類似性を計算する以下のような関数があれば実現される Sim(imgi, imgj ) 1< j =i< = n 1 < =j< = n かつ i = この関数は 実数を返し imgj と imgi の類似性が高いほど 大きな値を返すものとする 3. 2 画像の隣接性 本節では 画像検索における 画像の隣接性について説明 する 例を示しながら説明を行う 図 1 は金閣寺の画像である キー ワードクエリとして 金閣寺 が与えられると 画像検索シス テムからは 図 1 に示したような画像と類似する画像を数多く 検索結果が返される 実際に 金閣寺においてこの写真に写る 湖を周ると 図 1(b) のような光景も見ることができる さら に歩くと 図 1(c) のような光景も目にすることになる 図 1(c) には まだ 少しではあるが 金閣が見えている これは確か に金閣寺の光景であるのだが 人によっては分からないかもし れない さらに 図 1(d) や図 1(e) まで行くと ここがどこか 分かる人はあまりいないと考えられる これらは全て金閣寺に おいて撮影された写真であるのだが これらのどれも 1 枚では 金閣寺の実際の情景や環境を表現できておらず これらを総体 としたときによりよく金閣寺の実情が表現できると考えられる また 昼と夜 季節の変化などによって 情景は変化すること が考えられる 金閣寺の場合 図 1(f) や図 1(g) のような変化 (g) Image7 図 1 (a) 典型的な金閣寺の画像 (b)-(e) あまり典型的ではない金閣 の画像 (f) 秋の紅葉の金閣寺の画像 (g) 冬の雪の金閣寺の画 を見せる これにより 金閣寺の実際の情景といえば 季節や 像 (a) の画像だけ見ても金閣寺の実際の情景が分かるわけでは 時間による変化も含めて考慮する必要があると考えている ない そのため 我々の仮定の基では (b)-(e) の画像も (a) の 画像の隣接性とは ある画像と 別のある画像が部分的に 画像とまとめて扱うべきであるとしている さらに (f) や (g) 一致しており 実世界で隣接することを指す ある画像集合 のように金閣寺が珍しい情景を見せていることもあり これらも In ={img1, img2,..., imgi,..., imgn } があるとする ここで 含めて 金閣寺の実際の情景を表していると考えるべきである n は画像集合の画像の数である そのうちの 1 つの画像 imgi が入力として与えられたとき 出力として その画像と隣接す を用いれば 図中の画像 i1 がクエリとして与えられたときに る他の画像集合が得られるとする この機能は 2 つの画像の それとパノラマ合成可能であるような画像 i2 が存在したとす 隣接性を計算する以下のような関数があれば実現される ると 画像の隣接性を考慮して 画像 i2 を発見することは可能 である さらに 画像 i2 と画像 i3 の隣接性が高いことを考慮 Adj(imgi, imgj ) して 画像 i3 まで発見することも可能である 一方 類似性に 1< j =i< = n 1 < =j< = n かつ i = この関数は 実数を返し imgj と imgi の隣接性が高いほど ついては この場合 残念ながら画像 i1 と類似する画像がな 大きな値を返すものとする 発見することはできない ここまでが 画像の隣接性と類似性 3. 3 画像の類似性と隣接性の同時利用 本節では 画像の類似性と隣接性を同時に利用した場合にど のようなことが可能になるかについて説明する かった つまり クエリが画像 i1 の場合 いかなる類似画像も を別個に利用した場合である 画像の類似性と隣接性を同時に考慮した場合には クエリが 画像 i1 の場合 まず 隣接性を考慮して 画像 i2 が発見され 図 2 は それら 2 つの関係性を考慮することによって どの さらに 画像 i3 も発見することができる ここで 画像 i2 に ようなことが可能になるかを表している 既存の画像検索技術 は類似する画像 j2 と画像 j3 がある 我々の仮定が正しいとす
L1 L2 L1 Nister NisterScore(img i, img j ) = s(q, d) = img i img i img j img j 2 i 1 i 2 i 2 j 2 j 3 i 1 j 2 j 3 i 1 j 2 j 3 4. TextRank TextRank 4. 1 TextRank 4. 1. 1 Nister [2] Nister 1 i w i q i d i q i = n iw i d i = m i w i n i i m i 2 Nister Nister Color Coherence Vectors (CCV) Pass [5] CCV CCV CCV < (α 1, β 1 ),..., (α n, β n ) > CCV α j β j 2 CCV n CCV Score(img i, img j ) = G = (α j α j) + (β j β j) j=1 2 img i img j Sim(img i, img j ) = w 1 NisterScore(img i, img j ) + w 2 CCV Score(img i, img j ) w 1 w 2 w 1 + w 2 = 1 4. 1. 2 [3] 2 2 SURF 2 RANSAC 2 2 img i img j
N cp Adj(img i, img j ) = Min(N imgi, N imgj ) N cp N imgi img i SURF 4. 1. 3 TextRank [6] S(V i ) = (1 d) v i + d V j In(V i ) w ji V k Out(V j ) w S(V j ) jk d 0 1 0.85 In(V i ) V i Out(V j ) V j img i V i v i V i v i = { 1, imgi SI SI 0, img i / SI SI w jk w jk = λ 1 Sim(img j, img k ) + λ 2 Adj(img j, img k ) λ 1 λ 2 λ 1 + λ 2 = 1 4. 2 Web Web Flickr 2 Flickr Flickr TextRank N m m = 10 2 http://www.flickr.com/ 3 N TextRank N img 1 img 3... img n 1 3 k v imgi =(w 1 v 1, w 2 v 2,..., w j v j,..., w m v m ) v imgi img i w j v j m 1 < = i < = m v j = { 1, when it tagged to imgi 0, otherwise v j v seedi co(v j, v seedi ) = Iv j Iv seed i I vj + I vseedi v seedi 1 I vj v j I vseedi v seedi v j w j = N co(v j, v seedi ) i=1 N T Sim(img i, img j ) = v i v j v i v j
T Sim(img i, img j) w ij 4. 1 TextRank N 10 10 5. 232 Flickr 14,366 Mean Average Precision: MAP 0.65 0.41 14 3 10 140 4 3 2 3,,,,,,,,,,,,, 4 3 2 4 2 g b d d e e g e g h 6. 2
TextRank Flickr 7. COE. [1] Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool SURF: Speeded Up Robust Features, Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, pp. 346 359, 2008 [2] D. Nister and H. Stewenius, Scalable Recognition with a Vocabulary Tree, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 2161 2168, 2006 [3] M. Brown and D. G. Lowe, Recognising panoramas, Proceedings of Ninth IEEE International Conference on Computer Vision, Vol. 2, pp. 1218 1225, 2003 [4] David G. Lowe, Distinctive image features from scaleinvariant keypoints, International Journal of Computer Vision, Vol. 60, No. 2, pp. 91 110, 2004 [5] Greg Pass, Ramin Zabih, Justin Miler, Comparing images using color coherence vectors, Proceedings of the Fourth ACM international conference on Multimedia, pp. 65 73, 1996 [6] Rada Mihalcea and Paul Tarau, TextRank: Bringing Order into Texts, Proceedings of EMNLP, pp. 404 411, 2004