IPSJ SIG Technical Report Vol.2017-CVIM-205 No /1/ Content-based Image Retrieval(CBIR) CBIR RANSAC (Local feature hashing) 1000 A geo

Size: px

Start display at page:

Download "IPSJ SIG Technical Report Vol.2017-CVIM-205 No /1/ Content-based Image Retrieval(CBIR) CBIR RANSAC (Local feature hashing) 1000 A geo"

あおしとどろき
5 years ago
Views:

1 - - Content-based Image Retrieval(CBIR) CBIR RANSAC (Local feature hashing) A geometric consistency checking method for keypoint matching -Application to image retrieval- Okura Yuto Wada Toshikazu Abstract: Content-based Image Retrieval(CBIR) is a problem of finding similar images to a given query image out of the image database. In CBIR, various methods using codebook obtained from local features are widely used. However the local feature based image retrieval without using codebook is much faster than this method. When we employ the codebook-less image retrieval method, we can examine the coordinate values of the corresponding points in the query and database images and geometrically meaningless matching should be ignored. For checking this geometric consistency, RANSAC based rigid body transformation estimation can be applied, but this method requires considerable amount of time for random sampling. In this report, we propose Local Feature Hashing(LFH) that estimates similarity transformation between input and database images just from two corresponding keypoints. We perform voting to transformation parameters for all corresponded keypoints to obtain a reliable. If a salient peak is formed in the voting space after the voting to an image entry in the database, we can verify the retrieval, otherwise not. In the experiment, real-time image retrieval can be realized for the database consisting of images, and we confirmed that the method can suppress erroneous retrieval. Keywords: Image retrieval,similarity transform,parameter estimation,voting Wakayama University Graduate school of systems engineering c 27 Information Processing Society of Japan

2 情報処理学会研究報告. はじめに Content-based Image Retrieval(CBIR) とは画像をクエリとして与える画像検索問題であり多くのアプリケーションで利用されている例えばポスター等の展示物を撮影した画像を与え催し物のホームページの URL を検索する仕組みなど実世界への情報の埋め込みといった用途が考えられる CBIR では画像の色テクスチャ輪郭など様々の特徴を用いて検索を行うことができその中でも SIFT[] や SURF[2] などのキーポイント検出手法で表現される局所特図 Number-of-Match アプローチの概念図 Fig. Illustration of Number-of-Match approach 徴ベクトルが被写体の隠れ回転照明変化に対して頑健であり高速かつ安定な画像検索に効果的であることが連続してクエリとして与えて似た画像を fps 程度のス多くの研究によって実証されている局所特徴を用いた画ループットで検索するリアルタイム処理を行う画像検索像検索の手法は以下の 2 つのアプローチに大別されるシステムでは Number-of-Match アプローチを用いた方が ( ) Bag-of-Features(BoF) アプローチ有利である本研究ではこのアプローチでの画像検索法の BoF アプローチでは画像をつの高次元かつスパー改良に取り組むスな BoF ベクトルで表現する BoF ベクトルは画像前述の通り Number-of-Match アプローチでは画像かから得られる局所特徴をクラスタリングしクラスタら検出されたキーポイントの対応付けに基づいて投票が中心である Visual Words ごとの出現回数をカウント行われるが異なる画像間でのキーポイントの対応付けすることで生成される BoF ベクトルを用いた画像検の中には画像間での相似変換アフィン変換あるいは索はデータベース画像から生成した BoF ベクトル Homography 変換などの剛体変換に合致しない対応付けがとクエリ画像から生成した BoF ベクトルとの距離計存在する場合があるこれはキーポイントの対応付けが算によって行われクエリ画像から作成した BoF ベ画像から抽出された局所特徴ベクトル間の距離に基づいてクトルに最も近い BoF ベクトルの画像が検索結果と行われるからであるそのため誤った対応付けに基づくなる投票が行われてしまいクエリ画像と全く似ていない画像 ( 2 ) Number-of-Match アプローチが検索されるという問題がある Number-of-Match による画像検索はクエリ画像からこの問題を解決するためには画像間の剛体変換を推定抽出された局所特徴 (クエリ特徴) とデータベース画像しキーポイント同士の対応付けに幾何学的一貫性があるから抽出された局所特徴 (インデックス特徴) の間で最かどうかをチェックする必要があるこのとき画像間の近傍探索を行い最も距離が近いものを対応付ける剛体変換を推定する方法としてキーポイント間の対応付そして対応付けられたインデックス特徴をもつ画像けから RANSAC を用いて剛体変換を推定する方法があに対して投票を行い最も投票数が多い画像が検索結るしかし RANSAC ではノイズが存在するサンプルから果となる手法である図に Number-of-Match アプパラメータを推定するために多数回のランダムサンプリローチの概念図を示すングが必要になるこのランダムサンプリングに時間がかこれら 2 つのアプローチを比較すると BoF アプローチは BoF ベクトルがスパースであるため BoF ベクトル間かるためリアルタイムの画像検索システムには RANSAC を用いることはできないの距離計算を行う際にある VisualWord を持つベクトル本報告では画像間で対応付けられた組のキーポインとそうでないベクトルではベクトル間の距離が大きくなトから RANSAC を用いずにキーポイントのスケールりクエリ画像に似た画像を早い段階で絞り込めるためオリエンテーションを利用することによって画像間の剛大規模な画像検索問題に向くただしクラスタリングな体変換を推定し剛体変換に従う対応付けを求める方法をどの事前処理を必要とするため計算コストが大きくな提案するまた提案手法を実際の画像検索システムに実るといった問題があるそれに対して Number-of-Match 装し速度や投票数にどのような影響を与えるかというこアプローチはクラスタリングなどの事前処理が不要であとについても検討するるため計算コストが少なく高速であるただしデータベースの画像の量が増えるとその分だけインデックス特 2. 関連研究徴の量も増えるため大規模な画像検索に適用すること画像検索の分野では D.Lowe による SIFT[] や,H.Bay は難しいといった問題がある以上のことから動画像をらの SURF[2] などの局所特徴がよく用いられている中 27 Information Processing Society of Japan 2

3 J.Sivic Vido Google[3] k-means (Vocabulary tree) [4] Shen [] [6] Multiple Instance Learning Diverse Density 3. Local Feature Hashing RANSAC 2 P = [x y ] K = (P, cosθ, sinθ, s ) P 2 = [x 2 y 2 ] K 2 = (P 2, cosθ 2, sinθ 2, s 2 ) θ, θ 2 s, s 2 C 2 T K K 2 x 2 cos θ sin θ x y 2 = s sin θ cos θ y / s = T x y x y () T x, y s θ T s, θ, x, y 4 Fig. 2 2 DB Corresponded Keypoints between DB and Query image θ = θ 2 θ, s = s 2 /s x, y () [ x y ] = [ x2 y 2 ] s [ cos θ sin θ sin θ cos θ ] [ x y ] (2) (2) x, y 2 bin s, θ 4 4 bin 4 2 x, y c 27 Information Processing Society of Japan 3

情報処理学会研究報告 (a)img (a)query (b)img2 (b)query2 (c)query3 (d)query4 図実験で用いたクエリ画像 (c)img3 (d)img4 図 3 Graﬃti 画像セット

幾何学的一貫性の評価法に関する実験 Local Feature Hashing による幾何学的一貫性のチェックによって幾何学的に正しいキーポイントの対応付けをることができたしかし視点変化の激しい画像間の対応付けでは

2 画像検索システムへの実装セット (図 3) で壁と正対して撮影された画像 (図 3.a) 画像検索システムに提案手法による幾何学的一貫性のと別の視点から撮影された画像 (図 3.b-図 3.

クエリ画像からキーポイントを検出たキーポイント検出のアルゴリズムには SIFT を用い ( 2 ) クエリ特徴とインデックス特徴を最近傍探索によって投票空間 x, y の bin サイズはとしている

枚の画像を検索候補としそれらす img と img2 の対応付けでは投票のマップを見るとに対して幾何学的一貫性のチェックを行い正しい対投票空間内のある bin に投票が集中しピークが出現してい

データベースの画像の中からある程度候補セットに付属している homography 行列を用いて確認しを絞っているがこれは提案手法を全てのデータベース画たところすべての対応付けが正しいことが確認できた

キーポイント検出のアルゴリズムには SURF を高速化しなっているが依然として投票空間にピークが現れピーた整数化 SURF[8] を使用しデータベースに保存されていクの bin

投票が投票空間全体に散っており局所的たデータベース画像に対する投票数が少ない場合クエなピークも見られないため剛体変換の推定及び幾何学的リ画像と似ていると判断することは妥当ではないのであ

4 情報処理学会研究報告 (a)img (a)query (b)img2 (b)query2 (c)query3 (d)query4 図実験で用いたクエリ画像 (c)img3 (d)img4 図 3 Graﬃti 画像セット Fig. Query images Fig. 3 Graﬃti image set 4. 幾何学的一貫性の評価法に関する実験 Local Feature Hashing による幾何学的一貫性のチェックによって幾何学的に正しいキーポイントの対応付けをることができたしかし視点変化の激しい画像間の対応付けでは幾何学的一貫性の評価が行えないという結果になった求めることができるか確認するための実験を行った実験は Aﬃne Covariant Rigions Dataset[7] の Graﬃti 画像 4.2 画像検索システムへの実装セット (図 3) で壁と正対して撮影された画像 (図 3.a) 画像検索システムに提案手法による幾何学的一貫性のと別の視点から撮影された画像 (図 3.b-図 3.d) とのマッチェックを実装して実験を行った画像検索実験の手順はチングを行い投票の分布と投票によって求められた対以下の通り応付けが幾何学的に正しい対応付けであるか確認を行っ ( ) クエリ画像からキーポイントを検出たキーポイント検出のアルゴリズムには SIFT を用い ( 2 ) クエリ特徴とインデックス特徴を最近傍探索によって投票空間 x, y の bin サイズはとしているマッチングを行った画像間のすべての対応付けから x, y を求め投票を行った際の投票マップを図 4 に示対応付け対応づいたインデックス特徴を持つ DB 画像に対して投票を行う ( 3 ) 投票数が多い上位枚の画像を検索候補としそれらす img と img2 の対応付けでは投票のマップを見るとに対して幾何学的一貫性のチェックを行い正しい対投票空間内のある bin に投票が集中しピークが出現してい応付けのみに基づく投票を行うることが確認できるまたこのピークの bin に対して投 ( 4 ) 最も投票数が多い画像を検索結果とする票を行った対応付けが正しい対応付けであるかを画像 (3) の部分でデータベースの画像の中からある程度候補セットに付属している homography 行列を用いて確認しを絞っているがこれは提案手法を全てのデータベース画たところすべての対応付けが正しいことが確認できた像との対応付けに関して行うとシステムの実行速度の低次に img と img3 の対応付けでは img2 との対応付けの下を招く可能性があるからであるときと比較するとピークの bin に対する投票数が少なくキーポイント検出のアルゴリズムには SURF を高速化しなっているが依然として投票空間にピークが現れピーた整数化 SURF[8] を使用しデータベースに保存されていクの bin に対して投票を行った対応付けがすべて正しい対る画像の枚数は枚幾何学的一貫性のチェックを行応付けであることが確認できた最後に img と img4 のう際の投票空間の bin サイズはとしているま対応付けでは投票が投票空間全体に散っており局所的たデータベース画像に対する投票数が少ない場合クエなピークも見られないため剛体変換の推定及び幾何学的リ画像と似ていると判断することは妥当ではないのであ一貫性のチェックは行えなかったる一定の投票数に満たなければ似た画像がデータベースこれらの実験の結果から提案手法が画像間の剛体変換として相似変換を想定していながら視点変化が発生してに存在しないと判定する閾値を設ける必要があるこの実験ではその閾値を 4 と設定しているいるような画像間でのキーポイント対応付けでも幾何学クエリ画像として 4 枚の画像 (Query - Query4) を与的一貫性の評価が行うことができ正しい対応付けも求めえ似た画像の検索を行い幾何学的一貫性のチェックを 27 Information Processing Society of Japan 4

情報処理学会研究報告 3 2 2 - -2-2 - dx 'grafto3' -2-3 2-2 - dx 4 3 - -2 2-3 'grafto4' 3 2 (a)img と img2 の対応づけ 6 4-3 4 7 dy dy 8 2 dy 'grafto2' 2 2-4 - 2-4 -3-2 - (b)img と img3 の対応づけ dx 2 3 4 (c)img と img4

像が検索されてしまっているところが幾何学的一貫性の結果に注目した Query,Query2 はクエリ画像中にデーのチェックを行うことで全ての検索候補の画像に対するタベース内に登録されている画像が写っているものとなっ投票数が減少し投票数が閾値より低くなったためクエており Query3,Query4 はデータベースに登録されていな

5 情報処理学会研究報告 dx 'grafto3' dx 'grafto4' 3 2 (a)img と img2 の対応づけ dy dy 8 2 dy 'grafto2' (b)img と img3 の対応づけ dx (c)img と img4 の対応づけ図 4 画像間の対応点による投票マップ (a)query での投票数のグラフと検索結果 (b)query2 での投票数のグラフと検索結果 (c)query3 での投票数のグラフ (検索結果はなし) (d)query4 での投票数のグラフ (検索結果はなし) 図 6 幾何学的一貫性のチェックを行う前後の投票数と検索結果行う前後での検索候補の画像に対する投票数と画像検索像が検索されてしまっているところが幾何学的一貫性の結果に注目した Query,Query2 はクエリ画像中にデーのチェックを行うことで全ての検索候補の画像に対するタベース内に登録されている画像が写っているものとなっ投票数が減少し投票数が閾値より低くなったためクエており Query3,Query4 はデータベースに登録されていなリ画像に似た画像がデータベースに存在しないと判定でい画像が写っている画像となっているまた検索システきたムの動作速度は提案手法実装前と変わらず fps ほどのスループットで検索できていることを確認した実験の結果から提案手法実装前と比べてデータベースに存在する画像と似た画像を与えたときの検索結果に変幾何学的一貫性のチェックを行う前後での各検索候わりはなかったデータベースに似た画像が存在しない画補の画像に対する投票数を図 6 のグラフで示している像をクエリとして与えたとき全く関係のない画像を検索 Query をクエリとして与えて画像検索を行った結果正結果として返すことなくクエリ画像と似た画像がデータ解の画像に対する投票数が幾何学的一貫性のチェックをベースに存在しないと判定することが出来たことから提行う前に比べて減少してはいるが検索候補の中で最も投案手法により誤った検索を抑止できることが確認できた票数が多いため正しい検索が行われていることが確認できた Query2 に関しても同様に幾何学的一貫性チェッ. おわりにクの後に投票数が減少したが正しい検索が行われている本報告では画像間のキーポイントの対応付けからことが確認できた Query3,Query4 に関しては幾何学的 RANSAC を用いずキーポイントのスケールオリエン一貫性のチェックを行う前では検索候補の画像の投票数テーションの情報を利用し高速に相似変換を求め求めたが閾値を上回っているためデータベースに存在しない画相似変換のパラメータに対して投票を行うことで幾何学像をクエリとしているにも関わらずデータベース内の画的に正しい対応付けを求める方法を提案した 27 Information Processing Society of Japan

6 Homography fps [] Lowe, D. G.: Distinctive Image Features from Scale- Invariant Keypoints, International Journal of Computer Vision, Vol. 6, No. 2, pp. 9 (24). [2] Bay, H., Tuytelaars, T. and Van Gool, L.: Surf: Speeded up robust features, European conference on computer vision, Springer, pp (26). [3] Sivic, J. and Zisserman, A.: Video Google: A text retrieval approach to object matching in videos, Computer Vision, 23. Proceedings. Ninth IEEE International Conference on, IEEE, pp (23). [4] Nister, D. and Stewenius, H.: Scalable recognition with a vocabulary tree, 26 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 6), Vol. 2, IEEE, pp (26). [] Shen, X., Lin, Z., Brandt, J., Avidan, S. and Wu, Y.: Object retrieval and localization with spatially-constrained similarity measure and k-nn re-ranking, 22 IEEE Conference on Computer Vision and Pattern Recognition, pp (22). [6] Yuasa, K. and Wada, T.: Keypoint Reduction for Smart Image Retrieval, Multimedia (ISM), 23 IEEE International Symposium on, IEEE, pp (23). [7] : vgg/data/data-aff.html. [8] FPGA SURF Technical report of IEICE. HIP, Vol. 9, No. 47, pp (2). c 27 Information Processing Society of Japan 6

(MIRU2008) HOG Histograms of Oriented Gradients (HOG)

(MIRU2008) HOG Histograms of Oriented Gradients (HOG) (MIRU2008) 2008 7 HOG - - E-mail: katsu0920@me.cs.scitec.kobe-u.ac.jp, {takigu,ariki}@kobe-u.ac.jp Histograms of Oriented Gradients (HOG) HOG Shape Contexts HOG 5.5 Histograms of Oriented Gradients D Human