(57)【要約】【課題】大規模映像データベースからの高精度なインスタンスサーチを実現することができる映像検索装置、映像検索方法、及び映像検索プログラムを提供する。【解決手段】単数又は複数の画像クエリに含まれるＶＷ（visual word）を入力し、検索対象とする複数の映像の各々における各ＶＷの出現回数と、予め求めた各ＶＷの出現回数に関する統計情報を用いて算出した各ＶＷの重要度と、に基づいて、画像クエリと複数の映像の各々との適合度を求め、求めた適合度に応じた検索結果ランキングを出力する。【選択図】図１
2018124809.tif 000002
【特許請求の範囲】
【請求項１】
映像検索ランキング部を備えた映像検索装置における映像検索方法であって、
前記映像検索ランキング部が、単数又は複数の画像クエリに含まれるＶＷ（visual word）を入力し、検索対象とする複数の映像の各々における各ＶＷの出現回数と、予め求めた各ＶＷの出現回数に関する統計情報を用いて算出した各ＶＷの重要度と、に基づいて、前記画像クエリと前記複数の映像の各々との適合度を求め、求めた前記適合度に応じた検索結果ランキングを出力するステップ
を含む映像検索方法。
【請求項２】
前記ＶＷの重要度は、前記統計情報に基づいて一般化パレート分布によって算出される
請求項１記載の映像検索方法。
【請求項３】
単数又は複数の画像クエリに含まれるＶＷ（visual word）を入力し、検索対象とする複数の映像の各々における各ＶＷの出現回数と、予め求めた各ＶＷの出現回数に関する統計情報を用いて算出した各ＶＷの重要度と、に基づいて、前記画像クエリと前記複数の映像の各々との適合度を求め、求めた前記適合度に応じた検索結果ランキングを出力する映像検索ランキング部
を含む映像検索装置。
【請求項４】
前記ＶＷの重要度は、前記統計情報に基づいて一般化パレート分布によって算出される
請求項３記載の映像検索装置。
【請求項５】
コンピュータに、請求項１又は２記載の映像検索方法の各ステップを実行させるための映像検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、映像データベースから、インスタンスと呼ばれる特定の人物、物体、場所等が映っている映像を検索し、適合度に応じてユーザに提示する映像検索装置、映像検索方法、及び映像検索プログラムに関する。
【背景技術】
【０００２】
下記特許文献１では、Ｅｘｐｏｎｅｎｔｉａｌ  ＢＭ２５と呼ばれる検索モデルをインスタンスサーチに適用することにより、高精度な検索が実現されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１５−３９４８０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、Ｅｘｐｏｎｅｎｔｉａｌ  ＢＭ２５は、その検索モデル内に設定パラメータがあり、最適な設定が困難であった。パラメータフリーの高精度な検索モデルを用いることにより、大規模映像データベースからの高精度なインスタンスサーチを実現することが求められている。
【０００５】
本発明は、以上のような事情に鑑みてなされたものであり、大規模映像データベースからの高精度なインスタンスサーチを実現することができる映像検索装置、映像検索方法、及び映像検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本発明の映像検索方法は、映像検索ランキング部を備えた映像検索装置における映像検索方法であって、前記映像検索ランキング部が、単数又は複数の画像クエリに含まれるＶＷ（visual word）を入力し、検索対象とする複数の映像の各々における各ＶＷの出現回数と、予め求めた各ＶＷの出現回数に関する統計情報を用いて算出した各ＶＷの重要度と、に基づいて、前記画像クエリと前記複数の映像の各々との適合度を求め、求めた前記適合度に応じた検索結果ランキングを出力するステップを含む。
【０００７】
なお、本発明の映像検索方法では、前記ＶＷの重要度は、前記統計情報に基づいて一般化パレート分布によって算出されるようにしても良い。
【０００８】
上記目的を達成するために、本発明の映像検索装置は、単数又は複数の画像クエリに含まれるＶＷ（visual word）を入力し、検索対象とする複数の映像の各々における各ＶＷの出現回数と、予め求めた各ＶＷの出現回数に関する統計情報を用いて算出した各ＶＷの重要度と、に基づいて、前記画像クエリと前記複数の映像の各々との適合度を求め、求めた前記適合度に応じた検索結果ランキングを出力する映像検索ランキング部、を含む。
【０００９】
なお、本発明の映像検索装置では、前記ＶＷの重要度は、前記統計情報に基づいて一般化パレート分布によって算出されるようにしても良い。
【００１０】
上記目的を達成するために、本発明の映像検索プログラムは、コンピュータに、本発明の映像検索方法の各ステップを実行させるためのプログラムである。
【発明の効果】
【００１１】
本発明によれば、大規模映像データベースからの高精度なインスタンスサーチを実現することが可能となる。
【図面の簡単な説明】
【００１２】
【図１】実施形態に係る映像検索装置の構成を示す機能ブロック図である。
【図２】実施形態に係る画像クエリ記憶部の構成の一例を示す模式図である。
【図３】実施形態に係る映像記憶部の構成の一例を示す模式図である。
【図４】実施形態に係る統計情報記憶部の構成の一例を示す模式図である。
【図５】実施形態に係る映像検索装置により実行される映像検索処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１３】
本発明は映像データベースからインスタンスと呼ばれる特定の人物、物体、場所が映る映像を検索し、適合度順にランキングしてユーザに提示する検索システムに関するものである。
【００１４】
インスタンスサーチシステムにおいて、入力（クエリ）は、インスタンスが写っている単数又は複数の画像であり、出力は、各映像を適合度順に並べた検索結果ランキングである。
【００１５】
クエリを構成する複数枚の画像から取得された局所画像特徴量は、任意のコードブックによりベクトル量子化済み（ｖｉｓｕａｌ  ｗｏｒｄ化済み）であるとする。また、データベースに格納されている各映像に対しても、そのフレーム画像群から取得された局所画像特徴量は、ベクトル量子化済みであるとする。
【００１６】
本実施形態では、コードブックを構成する各ｖｉｓｕａｌ  ｗｏｒｄ（ＶＷ）の映像内における重要度を、ｇｅｎｅｒａｌｉｚｅｄ  Ｐａｒｅｔｏ  ｄｉｓｔｒｉｂｕｔｉｏｎ（ＧＰＤ）に基づく検索モデルから決定する。その結果、検索モデルのパラメータを映像データベースから得られる統計情報に基づき推定することが可能になり、パラメータフリーの高精度なインスタンスサーチが可能になる。
【００１７】
以下、本発明の実施形態について図面を用いて説明する。
【００１８】
図１に示すように、本実施形態に係る映像検索装置１０は、画像クエリ記憶部１２、映像記憶部１４、統計情報計算部１５、統計情報記憶部１６、及び、映像検索ランキング部１８を含んで構成される。
【００１９】
画像クエリ記憶部１２は、ベクトル量子化済みの画像クエリＱの局所画像特徴量の集合を記憶するためのデータベースである。一例として図２に示すように、画像クエリ記憶部１２には、ｉ番目のＶＷｉの画像クエリＱ内における出現回数Ｃ（Ｑ，ＶＷｉ）が、ＶＷｉ毎に格納されている。なお、ＶＷｉの総数をＭとする。
【００２０】
映像記憶部１４は、ベクトル量子化済みの各映像のフレーム画像の局所画像特徴量の集合を記憶するためのデータベースである。一例として図３に示すように、映像記憶部１４には、各ＶＷの、ｊ番目の映像Ｖｊ内の出現回数Ｃ（Ｑ，ＶＷ）が、映像Ｖｊ毎に格納されている。なお、画像クエリＱの総数をＮとする。
【００２１】
統計情報計算部１５は、事前に、映像記憶部１４に記憶されている、全ての映像における全てのＶＷの出現回数の総数Ｌを計算すると共に、映像記憶部１４に記憶されているＶＷｉの出現総数ｌｉ、及びエリート映像内におけるＶＷｉの出現総数Ｌｉを、ＶＷ毎に計算する。なお、エリート映像とは、そのＶＷｉが予め定めた回数（例えば、１回）以上出現する映像である。統計情報計算部１５は、計算により得られた統計情報を統計情報記憶部１６に記憶させる。
【００２２】
統計情報記憶部１６は、統計情報計算部１５により計算された統計情報を記憶するためのデータベースである。一例として図４に示すように、統計情報記憶部１６には、映像記憶部１４に記憶されているＶＷｉの出現回数の総数Ｌと、映像記憶部１４に記憶されているＶＷｉの出現総数ｌｉ、ｉ番目のエリート映像内におけるＶＷｉの出現総数Ｌｉが、映像Ｖｉ毎に記憶されている。統計情報記憶部１６に記憶されている統計情報は、映像検索ランキング部１８で使用される。
【００２３】
映像検索ランキング部１８は、画像クエリ記憶部１２に記憶されたデータ、映像記憶部１４に記憶されたデータ、及び、統計情報記憶部１６に記憶されたデータに基づき、映像記憶部１４に記憶された各映像を、クエリに対する適合度順でランキングする。
【００２４】
ランキングを行うために用いられる、画像クエリと映像との適合度を表すスコアを求める式は、下記（１）式である。画像クエリＱと映像Ｖｉとの適合度を表すスコアｓｃｏｒｅ（Ｑ，Ｖｉ）は、下記（１）式によって映像毎に算出される。
【００２５】
【数１】
2018124809.tif 000003
…（１）
【００２６】
ここで、Ｖｊはｊ番目の映像を表し、
【数２】
2018124809.tif 000004
は、Ｃ（Ｑ，ＶＷｉ）＞０かつＣ（Ｖｊ，ＶＷｉ）＞０のＶＷに関する和、すなわちＱとＶｊ内に両方出現するＶＷでの和を意味する。Ｃ（Ｑ, ＶＷｉ）、Ｃ（Ｖｊ，ＶＷｉ）はそれぞれＱ内、及びＶｊ内におけるＶＷｉの出現回数を表す。
【００２７】
また、上記（１）式のＶＬｊは、
【数３】
2018124809.tif 000005
で表され、ＶｊにおけるＶＷの全出現回数を表す。なお、
【数４】
2018124809.tif 000006
である。
【００２８】
また、上記（１）式の
【数５】
2018124809.tif 000007
は、統計情報を用いて算出したＶＷｉの重要度に相当する。
【００２９】
ξｃｏｎｓｔは、本実施形態で用いる検索モデルのパラメータであって、下記（２）式から推定される。なお、パラメータξｉについては後述する。
【００３０】
【数６】
2018124809.tif 000008
…（２）
【００３１】
ここで、Ｌｉはｉ番目のＶＷの全エリート映像内におけるＶＷの出現総数を表し、ｉ番目のＶＷのエリート映像とは、ｉ番目のＶＷが少なくとも一回出現する映像のことである。上記（２）式により検索モデルのパラメータが推定されるため、本検索モデルは、パラメータフリーであり、様々な検索タスクへの適用が容易になる。
【００３２】
次に、本検索モデル、及びパラメータの推定方法について導出する。
【００３３】
情報検索モデルの代表的なフレームワークであるｓｉｍｐｌｉｆｉｅｄ  ｄｉｖｅｒｇｅｎｃｅ  ｆｒｏｍ  ｒａｎｄｏｍｎｅｓｓを下記（３）式に示すように変更する。
【００３４】
【数７】
2018124809.tif 000009
…（３）
【００３５】
ここで、
【数８】
2018124809.tif 000010
は、キーワードクエリｑと文書ｄ内に両方出現するワードに関する和を表し、ｑｉは、そのワードのキーワードクエリｑ内における出現回数である。ｐ（ｘ≧ｄｉ｜ｄ）は、文書ｄｉの増加と共に減少する。ｐ（ｘ≧ｄｉ｜ｄ）は、ｉ番目のワードが文書ｄ内で出現回数ｄｉ以上を取る確率を表し、ｐ（ｘ≧ｄｉ｜Ｅｉ,ｄ）は、ｉ番目のワードがエリート文書内（Ｅｉ，ｄ）で出現回数ｄｉ以上を取る確率を表す。
【００３６】
ここで、ｉ番目のワードのエリート文書とは、そのワードが１回以上出現する文書を意味し、ｐ（Ｅｉ｜ｄ）は、文書ｄにおいてｉ番目のワードがエリートになる確率となる。なお、
【数９】
2018124809.tif 000011
及び
【数１０】
2018124809.tif 000012
は、非エリート文書内
【数１１】
2018124809.tif 000013
における確率である。上記（３）式のｐ（ｘ≧ｄｉ｜Ｅｉ，ｄ）は、極値統計学の定理（ある閾値より大きいデータ（閾値超過データ）が従う分布は、一般化パレート分布ＧＰＤで近似される）から、下記（４）式のように設定される。ここで、エリート文書の定義から、閾値は０に該当する。また、ｐ（Ｅｉ｜ｄ）は、下記（５）式で設定される。
【００３７】
【数１２】
2018124809.tif 000014
…（４）
【００３８】
【数１３】
2018124809.tif 000015
…（５）
【００３９】
ここで、ｌ’はｉ番目のワードの文書データベース内における出現総数であり、Ｌ’はワードの全出現総数であり、ＤＬは文書Ｄ内のワードの出現総数である。上記（４）式は、ＧＰＤに従うモデルであり、パラメータは、ξｉ、σｉの２つである。
【００４０】
ここで、情報検索の知識、すなわち既存の代表的な検索法との類似から、σｉ＝ｅｉとするのが自然である。ｅｉは、文書ｄ内におけるｉ番目のワードの出現回数の期待値ｅｉ＝（ｌ’ｉ／Ｌ’ｉ）ＤＬである。従って、ξｉの設定が問題になる。
【００４１】
ξｉを推定することは、該当データが少ないため困難である。そこで我々は、以下のように考える。ｐ（ｘ≧ｄｉ｜Ｅｉ, ｄ）は、その意味を考えると、エリート文書内における出現回数がｄｉ以上になる確率を表すため、上記（４）式におけるｄｉの正規化の基準として、通常の出現回数の期待値ｅｉではなく、エリート文書内における出現回数の期待値ｅ＾ｉを採用するほうが自然である。
【００４２】
このｅ＾ｉは、（ｅｉ／ξｉ）とみなすことができ、かつｅ＾ｉ＝（ｌ’ｉ／Ｌ’ｉ）ＤＬ=（ｌ’ｉ／ξｉＬ’）ＤＬであるため、ξｉ、はＬ”ｉ／Ｌ’で推定される。なお、Ｌ’ｉは、ｉ番目のワードの全エリート文書内におけるワードの出現総数を表す。
【００４３】
この式において文書を映像に置き換え、算出されたξｉを全ＶＷに対して平均を取ったものが上記（２）式である。そして、上記（４）式及び（５）式を映像検索、すなわちワードをＶＷに置き換え、文書を映像に置き換えたものが、上記（１）式である。
【００４４】
映像検索ランキング部１８は、上記（１）式で算出される適合度を表すスコアの降順で、映像記憶部１４に記憶されている各映像をランキングし、ランキング結果を検索結果２０としてクエリの入力者に提示する。
【００４５】
ここで、本実施形態に係る映像検索装置１０の性能評価について説明する。
【００４６】
ＴＲＥＣＶＩＤ２０１２のインスタンス検索タスクのデータセットを使用した検索精度の評価結果を載せる。
【００４７】
ＴＲＥＣＶＩＤは、毎年行われている映像検索分野の競争型ワークショップであり、アメリカのＮＩＳＴ（Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ）により主催されている。ＴＲＥＣＶＩＤ２０１２のインスタンス検索タスクでは、２１個のインスタンスが用意され、それぞれに平均約５枚のクエリ画像及びマスク画像が付与された。そして約７万７千本の映像（Ｗｅｂ上のＣＧＭ）が記憶されているデータベースが検索対象になった。
【００４８】
検索結果ランキングの精度は、Ｍｅａｎ  Ａｖｅｒａｇｅ  Ｐｒｅｃｉｓｉｏｎ（ＭＡＰ）という指標で評価される。なお、ＭＡＰ＝１が最高値であり、全適合映像がランキング１位から順に並んだ場合に、ＭＡＰ＝１となる。
【００４９】
上記（１）式のξｃｏｎｓｔを手動で１から０．０００５まで変化させると、ξｃｏｎｓｔ＝０．０５〜０．０１辺りで本手法の最高精度であるＭＡＰ＝０．３２を得た。このＭＡＰ値は、ＴＲＥＣＶＯＤ２０１２の優勝チームのＭＡＰ値であるＭＡＰ＝０．２７よりも高い。また、ξｃｏｎｓｔを表す上記（２）式による推定値は０．０１７８であり、従って、この推定値をパラメータの設定値として採用することで、ＭＡＰ＝０．３２という高い検索精度が得られることがわかった。
【００５０】
このように、本実施形態に係るＧＰＤに基づく検索モデルを適用することで、大規模映像データベースからの高精度なインスタンスサーチを実現することが可能になる。本実施形態で用いた検索モデルのパラメータ値は、映像記憶部１４からの情報に基づき推定可能であり、このパラメータ値を実際に使用することで、高い検索精度が得られることを確認した。
【００５１】
なお、本実施形態に係る映像検索装置１０は、例えば、ＣＰＵ（Central Processing Unit）、ＲＡＭ（Random Access Memory）、各種プログラムを記憶するＲＯＭ（Read Only Memory）を備えたコンピュータ装置で構成される。また、映像検索装置１０を構成するコンピュータは、ハードディスクドライブ、不揮発性メモリ等の記憶部を備えていても良い。本実施形態では、ＣＰＵがＲＯＭ、ハードディスク等の記憶部に記憶されているプログラムを読み出して実行することにより、上記のハードウェア資源とプログラムとが協働し、上述した機能が実現される。
【００５２】
本実施形態に係る映像検索装置１０による映像検索処理の流れを、図５に示すフローチャートを用いて説明する。本実施形態では、映像検索装置１０に、画像クエリの各ＶＷの出現回数が入力されたタイミングで映像検索処理が開始されるが、これに限らず、映像検索処理の実行を開始するための予め定めた情報が入力されたタイミングで映像検索処理が開始されても良い。
【００５３】
ステップＳ１０１では、映像検索ランキング部１８が、画像クエリ記憶部１２に記憶されている画像クエリの各ＶＷの出現回数を読み出すことにより、画像クエリの各ＶＷの出現回数を入力する。なお、本ステップにおいて画像クエリのみを入力した場合には、入力した画像クエリに基づき、画像クエリに含まれるＶＷを抽出し、各ＶＷの出現回数を求める。
【００５４】
ステップＳ１０３では、映像検索ランキング部１８が、統計情報記憶部１６に記憶されている統計情報を読み出すことにより、統計情報を取得する。なお、本ステップにおいて統計情報が取得できない場合には、映像記憶部１４に記憶されている映像に基づき、統計情報を作成する。
【００５５】
ステップＳ１０５では、映像検索ランキング部１８が、上記（１）式に基づき、画像クエリと各映像との適合度を表すスコアを計算する。
【００５６】
ステップＳ１０７では、映像検索ランキング部１８が、各映像を、計算したスコアに応じて降順に並び替え、検索結果ランキングを作成する。
【００５７】
ステップＳ１０９では、映像検索ランキング部１８が、検索結果ランキングを出力して、本映像検索処理のプログラムの実行を終了する。なお、本実施形態では、検索結果ランキングを示すデータをディスプレイ等の表示手段に表示させたり、検索結果ランキングを示すデータを記憶手段に記憶させたりすることにより、検索結果ランキングを出力する。
【００５８】
このようにして、本実施形態では、単数又は複数の画像クエリに含まれるＶＷ（visual word）を入力し、検索対象とする複数の映像の各々における各ＶＷの出現回数と、予め求めた各ＶＷの出現回数に関する統計情報を用いて算出した各ＶＷの重要度と、に基づいて、画像クエリと複数の映像の各々との適合度を求め、求めた適合度に応じた検索結果ランキングを出力する。
【００５９】
なお、本実施形態では、図１に示す機能の構成要素の動作をプログラムとして構築し、映像検索装置１０として利用されるコンピュータにインストールして実行させるが、これに限らず、ネットワークを介して流通させても良い。
【００６０】
また、構築されたプログラムをハードディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールしたり、配布したりしても良い。
【符号の説明】
【００６１】
１０  映像検索装置
１２  画像クエリ記憶部
１４  映像記憶部
１５  統計情報計算部
１６  統計情報記憶部
１８  映像検索ランキング部
２０  検索結果
【図１】
2018124809.tif 000016
【図２】
2018124809.tif 000017
【図３】
2018124809.tif 000018
【図４】
2018124809.tif 000019
【図５】
2018124809.tif 000020