(57)【要約】      （修正有）【課題】キーワードによる画像検索（ＴＢＩＲ）を精度よく行う手法を提供する。【解決手段】画像、画像特徴量、索引語、前記索引語−前記索引語間の関連度および前記画像特徴量−前記索引語間の関連度が格納されたデータベースから対象画像を検索する方法で、検索質問としてテキストを入力させ、複数の供給地から需要地へ対象物を供給するときの総コストを与えるアース・ムーバーズ・ディスタンス（ＥＭＤ）を適用すべく、（１）検索質問を供給地とし各画像の索引語および画像特徴量を需要地とするか、または検索質問を需要地とし各画像の索引語および画像特徴量を供給地とし、（２）前記関連度を用いて各供給地から需要地への各コストを決定し、前記（１）および（２）に基づき、各画像についてその画像と検索質問との間のＥＭＤを算出し、算出されたＥＭＤを検索質問と各画像との類似度を示す尺度とし、検索結果とすべき画像を決定する画像検索方法を用いる。【選択図】図４
2008181296.tif 000002
【特許請求の範囲】
【請求項１】
画像、画像特徴量、索引語、前記索引語−前記索引語間の関連度および前記画像特徴量−前記索引語間の関連度が格納されたデータベースから対象画像を検索する方法であって、
各画像には、その特徴を示す前記画像特徴量および前記索引語が予め付与され、データベース中の索引語-索引語間の関連度および画像特徴量-索引語の間の前記関連度が予め決定されてなり、
コンピュータを用いて、検索質問としてテキストを入力させ、
複数の供給地から需要地へ対象物を供給するときの総コストを与えるアース・ムーバーズ・ディスタンス（EMD）を適用すべく、
（１）検索質問を供給地とし各画像の索引語および画像特徴量を需要地とするか、または検索質問を需要地とし各画像の索引語および画像特徴量を供給地とし、
（２）前記関連度を用いて各供給地から需要地への各コストを決定し、
前記（１）および（２）に基づき、各画像についてその画像と検索質問との間のEMDを算出し、
算出されたEMDを検索質問と各画像との類似度を示す尺度とし、検索結果とすべき画像を決定する画像検索方法。
【請求項２】
各関連度は、その対象である索引語または画像特徴量が一つの画像に共に付与されている度合いに基づいて決定される請求項１記載の画像検索方法。
【請求項３】
前記画像特徴量は、各画像の色に係る特徴を示す請求項１記載の画像検索方法。
【請求項４】
前記画像特徴量は、各画像に所定の色が所定の割合以上で含まれているか否かに基づいて決定される請求項３記載の画像検索方法。
【請求項５】
各供給地から需要地へのコストがいずれも予め定められた閾値よりも低い画像については、EMDを算出することなく前記画像を検索結果の対象外とする請求項１記載の画像検索方法。
【請求項６】
索引語の総数をｎ、画像特徴量の総数をｍとするとき、各索引語に対応するｎ次元のベクトルとして検索質問を表し、各索引語および各画像特徴量に対応するｎ＋ｍ次元のベクトルとして各画像を表し、
検索質問を表すベクトルの各要素の値を、その要素に対応する索引語が検索質問に一致するか否かに基づいて決定し、
画像を表すベクトルのうち索引語についての要素の値を、その要素に対応する索引語が画像に付与されているか否かに基づいて決定し、画像特徴量についての要素の値を、その要素に対応する画像特徴量が画像に付与されているか否かに基づいて決定する請求項１記載の画像検索方法。
【請求項７】
画像、画像特徴量、索引語、前記索引語−前記索引語間の関連度および前記画像特徴量−前記索引語間の関連度が格納されたデータベースから対象とする画像を検索するためのプログラムであって、
各画像には、その特徴を示すように前記画像特徴量および前記索引語が予め付与され、データベース中の索引語-索引語間の関連度および画像特徴量-索引語の間の前記関連度が予め決定されてなり、
検索質問としてテキストを入力させる手順と、
複数の供給地から需要地へ対象物を供給するときの総コストを与えるEMDを適用するため、
（１）検索質問を供給地とし各画像の索引語および画像特徴量を需要地とするか、または検索質問を需要地とし各画像の索引語および画像特徴量を供給地とする手順と、
（２）前記関連度を用いて各供給地から需要地への各コストを決定する手順と、
前記（１）および（２）に基づき、各画像についてその画像と検索質問との間のEMDを算出する手順と、
算出されたEMDを検索質問と各画像との類似度を示す尺度とし、検索結果とすべき画像を決定する手順とをコンピュータに実行させるための画像検索プログラム。
【請求項８】
各供給地から需要地へのコストがいずれも予め定められた閾値よりも低い画像については、EMDを算出することなく前記画像を検索結果の対象外とする請求項７記載の画像検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、画像検索方法および画像検索プログラムに関する。より詳細には、キーワードに基づく画像検索を行う方法およびプログラムに関する。
【背景技術】
【０００２】
近年のデジタルカメラやインターネットの普及に伴い、Web上に大量の画像が存在している。これらの大量の画像の中からユーザーが必要とする画像を得る手段としての画像検索が注目されている。
画像検索には、画像の特徴量（画像特徴量）を用いて類似画像を検索する手法(Content-Based Image RetrievalあるいはCBIRともいう)と、画像に対してあらかじめ対応付けられたテキストに基づいてキーワード検索を行う手法(Text-Based Image RetrievalあるいはTBIRともいう)とが存在する。この発明は、それらのうち、主としてTBIRに関する。
【０００３】
TBIRを実現するためには、画像に対して予めキーワードを付与しておく必要がある。多様なキーワードを用いて検索可能にするためには、一つの画像に複数のキーワード（索引語）を対応付ける必要がある。この必要に応えるために、画像に対して自動で索引付けをする研究がすでになされている（例えば、非特許文献１〜４参照）。特に、Webページから画像説明文を抽出し、画像に付与する研究（例えば、非特許文献１、２参照）や、ユーザー自身が画像に索引語を付与するfolksonomy（例えば、非特許文献５参照）と呼ばれる技術などによって、豊富なキーワードによって索引付けされた画像が大量に存在するという環境が整いつつある。我々は、キーワードを検索質問としてインターネット上のデータを検索することに慣れている。画像の検索においても、画像を検索質問とするCBIR（例えば、非特許文献６参照）だけでなく、キーワードを検索質問とするTBIRが今後さらに多用されると思われる。
【０００４】
ところで、TBIRでは、前述した手法などによって索引付けされたキーワードと検索質問との類似度をどのように測るかが重要である。この点、従来のTBIRは、情報検索の技術を用いて類似度を測定している。しかしながら、索引付けの段階で必ずしも正しいキーワードが画像に付与されているわけではないため、結果としてキーワードのみによる検索の精度には課題を残している。例えば、文書情報検索の代表的な技術とし、ベクトル空間法(VSMともいう。例えば、非特許文献７参照）がある。VSMでは、各単語が異なる次元に割り当てられた高次元のベクトルを用いて索引語や検索質問を表現する。そして、前記ベクトルを用いて演算を行う。ところが、VSMにおいては、異なる単語は異なる次元に割り当てられるので、似た意味の単語でもその間の類似度が0とされる。例えば、「car」と「automobile」とは別物である。一方の索引語から他方の索引語を持つ画像が検索できない。その結果、検索に失敗する画像が多く、検索精度が十分とはいえない。これを改善するため、高次元空間にあるベクトルを低次元空間に射影し、検索精度の改善を図る手法が提案されている（例えば、非特許文献８〜１１参照）。索引語のベクトルをより低次元のベクトルに射影することにより、索引語間の隠れた類似性を捉えようとする手法である。ただし、これらの手法では、射影する空間の次元の決定が試行錯誤的であるという点に課題を残している。
【０００５】
一方のCBIRは、画像から色、模様や形などの特徴量を抽出し、特徴量が類似している画像を検索するものである。ところが、画像から得られる特徴量と人間の感覚は異なるため、こちらも検索精度に課題を残していた。検索精度の向上のため、画像特徴量の類似度に加え索引語の類似度を用いる手法も提案されている（例えば、非特許文献１２参照）。ただし、前記の手法では前記の2つの類似度は並列的に用いられているだけであり、索引語と画像特徴量の関係については考慮されていない。
【０００６】
ところが、近年、CBIRの分野においてアース・ムーバーズ・ディスタンス（Earth Mover's Distance、あるいはEMD。例えば、非特許文献１３参照)と呼ばれる尺度が提案され、これが、他の尺度より人間の感覚に近いことで注目されている。EMDは、需要地(供給地)の重みと需要地と供給地の間のコストを定義すればどのような問題にも適用できるため、CBIRに限らず、さまざまな分野で用いられつつある。例を挙げると、文書間の類似度の測定にEMDを用いることができ、ベクトル空間法による類似度と比較して高性能であることが実験により証明されたとの報告がなされている（例えば、非特許文献１４参照）。なお、非特許文献１４では、EMDを適用するにあたり、英語の概念辞書として知られているWordNetの内容に基づいて単語間のコストを定義している。
【０００７】
【非特許文献１】竹内謹冶，黄瀬浩一，“類似画像とキーワードを利用したweb画像の説明文抽出”，情報処理学会研究報告，NL-171, pp.7-12, Jan., 2006.
【非特許文献２】出原博，藤本典幸，竹野浩，萩原兼一，“WWW画像検索における画像周辺のHTML構文構造を考慮した画像説明文の抽出手法”，信学技報，DE2005-136，2005.
【非特許文献３】相良直樹，砂山渡，谷内田正彦，“HTMLテキストの重要文を用いた画像ラベリング手法”，信学論（D)，vol. J87-D-1, no.2, pp.145-153, 2004.
【非特許文献４】柳井啓司，“キーワードと画像特徴を利用したWWWからの画像収集システム”，情処学論，vol.42, no.SIG10(TOD 11), pp.79-91, 2001.
【非特許文献５】A.Mathes，“Folksonomies: Cooperative classification and communication through shared metadata”, Technical Report LIS590CMC, University of Illinois Urbana-Champaign, 2004.
【０００８】
【非特許文献６】Y. Rui, T. Huang and S. Chang, “Image retrieval: current techniques，promising directions and open issues”, Journal of Visual Communication and Image Representation, vol. 10, no. 4, pp.39-62, 1999.
【非特許文献７】G.Salton, A. Wong and C. S. Yang, "A vector space model for automatic indexing",  Comm. ACM, vol.18, no.11, pp.613-620, 1975.
【非特許文献８】S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas and R. A. Harshman, "Indexing by latent semantic analysis",  Journal of the American Society of Information Science, vol.41, no.6, pp.391-407, 1990.
【非特許文献９】T. Hofmann，“Probabilistic latent semantic indexing”, Research and Development in Information Retrieval, pp.50-57, 1999.
【０００９】
【非特許文献１０】黒岩眞吾，柘植覚，田仁宏典，T. Xiaoying，獅々堀正幹，北研二，“Simple pcaを用いたベクトル空間情報検索モデルの次元削減”，情処学NL研報，NL-144，pp.61-66, 2001.
【非特許文献１１】柘植覚，獅々堀正幹，北研二，“Non-negative matrix factorizationを用いた情報検索”，情処学NL研報，NL-142，pp.1-6, 2001.
【非特許文献１２】S. Sclaroff, M. L. Cascia, S. Sethi and L. Taycher, “Combining textual and visual cues for content-based image retrieval on the world wide web”，Computer Vision and Image Understanding, vol.75, nos.1/2, July/August, pp.86-98, 1999.
【非特許文献１３】Y. Rubner, C.Tomasi and L.Guibas, “The earth mover’s distance as a metric for image retrieval”,  International Journal of Computer Vision, vol.40，pp.99-121, 2000.
【非特許文献１４】X.Wan and Y.Peng, "The earth mover's distance as a semantic measure for document similarity", CIKM '05: Proceedings of the 14th ACM International conference on Information and Knowledge Management, New York, NY, USA, ACM Press, pp.301-302, 2005.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
前述のように、TBIRの検索精度は、索引語が正しく付与されているかどうかに依存するといえる。もし、索引語に依存しない特徴量を利用することができれば、検索性能を改善することができると考えられる。そこで、TBIRの検索精度を改善するためのアプローチとして、キーワードの他に画像自体から抽出した特徴量（画像特徴量）を利用することが考えられる。
【００１１】
そこで、キーワードと画像特徴量を扱う手法として、前述のEarth Mover's Distanceに基づくTBIR手法を考える。EMDを用いることにより、キーワードと画像特徴量を統一的に扱える可能性がある。しかし、これまで、TBIRの分野にEMDを適用した例は、ほとんど報告されていない。これは、EMDに基づく検索手法が、前述のVSMに比べて非常に長い処理時間を要することがこの分野で常識とされていたためと考えられる。ところが、TBIRで検索精度の改善を図るにつれて、処理時間が結果的に犠牲となり、もはや、EMDに基づく検索手法に対する優位性があると一概にいえない状況にあることに発明者らは気付いた。そして、検索精度と処理時間の相反する要求をTBIRにおいて両立させるためには、画像特徴量を用いることが有効ではないかという着想に至った。発明者らは、前記着想に基づいて鋭意検討を重ねた結果、この発明に至った。即ち、この発明は、文書情報検索技術の改善によってTBIRの検索精度向上を図るだけでなく、画像特徴量をも用いてTBIRの検索精度向上を図る手法を提供するものである。
【００１２】
なお、画像特徴量をTBIRに適用する手法には、種々のものが考え得る。しかし、それらの全てが良好な結果、即ち、短時間で高精度の検索結果を与えるものではない。検索手法の成否は、画像特徴量として何を対象とするか、それをどのように検索に用いるか、どのような検索技術を適用するかといった点に依存する。
【００１３】
前述のように、EMDは、需要地(供給地)の重みと需要地と供給地の間のコストさえ定義できればどのような問題に対しても求めることができる。たとえば、需要地(供給地)にテキストと画像特徴量が混在しているとしても、それぞれの重みとコストを定義することができればEMDを求めることができる。そこで、これらを具体的に定義し、実験によりその有効性を検証した。この発明の本質は、テキストと画像特徴量を統一的に扱うことのできる画像検索手法にある。
【課題を解決するための手段】
【００１４】
この発明は、画像、画像特徴量、索引語、前記索引語−前記索引語間の関連度および前記画像特徴量−前記索引語間の関連度が格納されたデータベースから対象画像を検索する方法であって、各画像には、その特徴を示す前記画像特徴量および前記索引語が予め付与され、データベース中の索引語-索引語間の関連度および画像特徴量-索引語の間の前記関連度が予め決定されてなり、コンピュータを用いて、検索質問としてテキストを入力させ、複数の供給地から需要地へ対象物を供給するときの総コストを与えるアース・ムーバーズ・ディスタンス（EMD）を適用すべく、（１）検索質問を供給地とし各画像の索引語および画像特徴量を需要地とするか、または検索質問を需要地とし各画像の索引語および画像特徴量を供給地とし、（２）前記関連度を用いて各供給地から需要地への各コストを決定し、前記（１）および（２）に基づき、各画像についてその画像と検索質問との間のEMDを算出し、算出されたEMDを検索質問と各画像との類似度を示す尺度とし、検索結果とすべき画像を決定する画像検索方法を提供する。
【００１５】
また、異なる観点から、この発明は、画像、画像特徴量、索引語、前記索引語−前記索引語間の関連度および前記画像特徴量−前記索引語間の関連度が格納されたデータベースから対象とする画像を検索するためのプログラムであって、各画像には、その特徴を示すように前記画像特徴量および前記索引語が予め付与され、データベース中の索引語-索引語間の関連度および画像特徴量-索引語の間の前記関連度が予め決定されてなり、検索質問としてテキストを入力させる手順と、複数の供給地から需要地へ対象物を供給するときの総コストを与えるEMDを適用するため、（１）検索質問を供給地とし各画像の索引語および画像特徴量を需要地とするか、または検索質問を需要地とし各画像の索引語および画像特徴量を供給地とする手順と、（２）前記関連度を用いて各供給地から需要地への各コストを決定する手順と、前記（１）および（２）に基づき、各画像についてその画像と検索質問との間のEMDを算出する手順と、算出されたEMDを検索質問と各画像との類似度を示す尺度とし、検索結果とすべき画像を決定する手順とをコンピュータに実行させるための画像検索プログラムを提供する。
【発明の効果】
【００１６】
この発明の画像検索方法および画像検索プログラムは、検索質問を供給地（あるいは需要地）とし各画像の索引語および画像特徴量を需要地（あるいは供給地）とし、各画像についてその画像と検索質問との間のEMDを算出し、算出されたEMDを検索質問と各画像との類似度を示す尺度として検索結果とすべき画像を決定するので、本来、異質であるキーワードと画像特徴量を統一的に扱うことができる。これによって、キーワードと画像特徴量を並列的に扱う手法に比べて、検索の工程が単純化される。引いては、検索の処理時間短縮に寄与すると考えられる。
換言すれば、この発明は、EMDを用いることによって、テキストと画像を統合的に扱えるプラットフォームを提供する。画像に付与された索引語と画像特徴量との間に関連があることを利用して、検索質問として入力されたテキストから画像を精度よく検索することができる。また、検索質問と索引語、あるいは検索質問と画像特徴量の関連度を考慮した柔軟な検索が可能である。
【００１７】
この発明の好ましい態様として、各関連度は、その対象である索引語または画像特徴量が一つの画像に共に付与されている度合いに基づいて決定されてもよい。即ち、共起の度合い（共起頻度）を用いてもよい。このようにすれば、検索対象のデータベースが決まると、それに含まれる各テキストおよび各特徴量から各関連度が算出できる。また、各関連度は、検索質問が入力される前に予め算出しておくことが可能である。
EMDでは、コストをいかに定義するかが、検索性能に大きな影響を与える。コストとして共起の度合いを用いることにより、LSIやPLSIなどの従来手法と同等の処理時間で精度のよい検索を行うことができる。さらに、コストの算出に要する時間が、LSIやPLSIに比べて少ないこともこの発明の特徴の一つである。
【００１８】
また好ましくは、前記画像特徴量は、各画像の色に係る特徴を示すものであってもよい。
【００１９】
さらに好ましくは、前記画像特徴量は、各画像に所定の色が所定の割合以上で含まれているか否かに基づいて決定されてもよい。このようにすれば、CBIRの分野で多用されている「色」についての特徴をTBIRに適用し、検索精度を向上させることができる。
【００２０】
また好ましくは、各供給地から需要地へのコストがいずれも予め定められた閾値よりも低い画像については、EMDを算出することなく前記画像を検索結果の対象外としてもよい。このようにすれば、検索精度を大きく落とすことなくEMDの計算対象を減らすことができる。即ち、検索精度を大きく犠牲にすることなく検索の処理時間を大幅に短縮することができる。
【００２１】
さらにまた、好ましくは、データベースに格納された索引語の総数をｎ、画像特徴量の総数をｍとするとき、各索引語に対応するｎ次元のベクトルとして検索質問を表し、各索引語および各画像特徴量に対応するｎ＋ｍ次元のベクトルとして各画像を表し、検索質問を表すベクトルの各要素の値を、その要素に対応する索引語が検索質問に一致するか否かに基づいて決定し、画像を表すベクトルのうち索引語についての要素の値を、その要素に対応する索引語が画像に付与されているか否かに基づいて決定し、画像特徴量についての要素の値を、その要素に対応する画像特徴量が画像に付与されているか否かに基づいて決定するようにしてもよい。
【００２２】
また、この発明の画像検索プログラムの好ましい態様は、各索引語と検索質問との間の各コストが予め定められた閾値よりも低い画像についてはEMDを計算せず、かつ、前記画像を検索結果としないものであってもよい。
好ましい各態様は、組み合わせることができる。
【発明を実施するための最良の形態】
【００２３】
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。まず、EMDについて説明する。次に、実際にEMDをどのようにTBIRに用いるのかについて説明する。
【００２４】
Earth Mover's Distance（EMD）
Earth Mover's Distanceは、線形計画問題の1つであるヒッチコック型輸送問題の解に基づく尺度である。
ヒッチコック型輸送問題とは供給地と供給量の集合
【００２５】
【数１】
2008181296.tif 000003
需要地と需要量の集合
【００２６】
【数２】
2008181296.tif 000004
及び、各供給地、需要地間の輸送コスト（あるいは、輸送距離）
【００２７】
【数３】
2008181296.tif 000005
【００２８】
が定義されたとき、供給地、需要地間の総輸送コスト（総輸送距離）の最小値を求める問題である。
ここで、piは、集合Pのn個の各要素を示す値、rpiは、各供給地の供給能力（より一般的には、各要素の重み）、qjは、集合Qのm個の各要素を示す値、rqjは、各需要地の総需要量（より一般的には、各要素の重み）である。また、cijは、pi、qj間の輸送コスト、fijは、pi、qj間の輸送量である。
ヒッチコック型輸送問題は、以下のような最適化問題として定式化できる。
【００２９】
【数４】
2008181296.tif 000006
【００３０】
【数５】
2008181296.tif 000007
【数６】
2008181296.tif 000008
【数７】
2008181296.tif 000009
【００３１】
【数８】
2008181296.tif 000010
式（２）は、PからQへ非可逆的な供給が行われることを表している。式（３）は、各供給地piからの輸送量が、その重みrpi以下に制限されることを示している。式（４）は、各需要地の受容量が、その重みrqi以下に制限されることを示している。式（５）は、可能な範囲内で最大量の輸送が行われることを示している。
このとき、P、Q間のEarth Mover's Distanceは以下の式で与えられる。
【００３２】
【数９】
2008181296.tif 000011
式（６）の分母は総輸送量を表し、分子は総輸送コスト（総輸送距離）を表す。
【００３３】
EMDのTBIRへの適用
EMDをTBIRに適用するには、需要地(供給地)、需要量(供給量)、輸送コスト（以下、単にコストともいう）を定義する必要がある。
まず、需要地、供給地をどのように定義するのかについて説明する。需要地（あるいは供給地）としては検索質問の各単語を、供給地（あるいは需要地）としては画像の索引語および画像特徴量を割り当てる。そして、ベクトル空間法と同様に高次元のベクトルを用いて検索質問と索引語および画像特徴量とを表現する。検索質問の各要素は、データベース中の各索引語に対応する。このように定義すると、需要地は、検索質問をベクトルで表現したときの0でない要素に相当する。つまり、検索質問qは、前記集合Qを簡略化したn次元のベクトル、
【００３４】
【数１０】
2008181296.tif 000012
【００３５】
と表現できる。ここで、tqjは単語wjが検索質問中の語であるとき1、それ以外のときは0とする。一方、供給地は、前記集合Pを簡略化し、n次元ベクトルにm個の画像特徴量の次元を加えたベクトルで表現する。つまり、画像Iiは、
【００３６】
【数１１】
2008181296.tif 000013
【００３７】
という(n+m)次元のベクトルで表現する。なお、Tは、ベクトルの転置を表す。式（７）、（８）の場合は、ベクトルqおよびIiが、それらの要素を縦方向に並べたベクトルであることをそれぞれ示している。
このように考えることにより、需要地の重みtqjおよび供給地の重みtij,cikとして、従来の情報検索の重みを与えることができる。以下に、重みの具体的な与え方について説明する。
まず、2進重みを与える場合について説明する。tijは、単語wjが画像Iiの索引語のとき1、それ以外は0とする。また、cikは、対応する画像特徴量が画像Iiをよく表していれば1、そうでなければ0とする。たとえば、画像特徴量として色を用いる場合、画像Iiに対してある色が閾値以上の割合で含まれている場合は1、そうでない場合は0とする。後述する実験では、画像特徴量として、均等量子化により8色に減色した色を用いた。
次に、重みとしてIDF重みを与える場合について説明する。まず、索引語に係る重みtijを以下の式で定義する。
【００３８】
【数１２】
2008181296.tif 000014
【００３９】
ここで、lijは前述した2進重みを表している。また、Nはデータベースの画像の総数、Njはlij=1である画像Iiの総数、即ち、その索引語が付与された画像の総数（Document Frequency）を表している。なお、IDFは、Inverse Document Frequencyの略であり、単語の出現頻度の逆数の意味である。画像特徴量に係る重みcikに関しても、同様の式で定義する。
今、検索質問qに関しても、画像特徴量の次元が全て0であると考えれば(n+m)次元のベクトルとして考えられる。今後は、qも(n+m)次元のベクトルであると考える。以下、qを検索質問ベクトル、Iiを画像ベクトルと呼ぶことにする。
【００４０】
最後に輸送コストについて説明する。輸送コストとしては、単語間あるいは単語-画像特徴間の関連度を利用する。関連度としては、共起の度合いを用いる。共起は画像データベースから計算する。ここで共起とは、画像ベクトルIiにおいて、同時に0でない要素になっていること、換言すれば、共に画像の索引語または画像特徴量になっていることである。このとき、輸送コストを以下の式で定義する。
【００４１】
【数１３】
2008181296.tif 000015
【００４２】
ただし、nijはwiとwjの共起頻度、ni、njはwi、wjの出現頻度である。ここで、共起頻度は、データベース中の各画像のうち、単語wiとwjとが共に索引語となっている画像の数である。出現頻度は、単語wiあるいはwjが索引語になっているそれぞれの画像の数である。
式(10)は単語間のコストの定義であるが、単語-画像特徴量間のコストに関しても同様の式で定義する。即ち、共起頻度nijを、画像特徴量ciと単語wjとが共に対応付けられている画像の数とする。また、出現頻度ni、njを、画像特徴量ciおよび単語wjがそれぞれ対応付けられた画像の数とする。式（１０）で、wiとwjとが全く関連しない（関連度がゼロ）場合は、nij=0になり、輸送コストは、1（最大）になる。wiとwjとの関連が強く、必ず共起する場合は、nij=1、かつ、ni=njになる。従って、このときの輸送コストは、ゼロになる。
さて、TBIRを実現するには、これらを用いて検索質問とデータベース中の全画像とのEMDを求め、EMDが小さい画像から順にユーザーに提示すればよい。
【００４３】
実験
実施形態に係る手法の有効性を検証するため、従来手法と性能比較実験を行った。
【００４４】
1．実験データおよび実験環境
まず、実験データについて示す。実験では、写真共有サイトflickrから収集した12295枚の画像（収集に使った検索質問としては、http://www.flickr.com/photos/tags/に掲載されている All times most popular tagsの145種類を用いた。）、それらに付与されている8565個の索引語を使用した。この画像集合からデータベースを構築し、画像検索を行い、その性能を評価した。表1に、検索に用いた検索質問を示す。
【００４５】
【表１】
2008181296.tif 000016
【００４６】
ここで、実験の評価には、leave-one-out法によって得られる平均適合率および検索時間を用いた。具体的には、14個の検索質問を用いて最良の平均適合率が得られるパラメータを求め、残り1つの検索質問における性能を評価した。パラメータの詳細については後述する。ここで、leave-one-out法は、公正な評価結果を得るためのパラメータ決定手法の一つである（例えば、石井健一郎ほか著、わかりやすいパターン認識、第１版、株式会社オーム社、1998年8月、p.69-70  参照）。
次に、正解データの作成手順について説明する。まず、実験意図を知らない情報工学系の大学院生3人が、個別に検索質問に適合する画像をデータベースから探した。次に、この結果において3人中2人が正解とした画像を検索質問に対する正解画像であるとした。
最後に、実験環境について説明する。実験に使用した計算機としては、CPUがAMD Opteron 2.8GHz、メモリが16GBのものを用いた。また、プログラミング言語としてはMATLABを用いた。
【００４７】
2．実施形態に係る手法および比較手法の設定
実験では、比較手法としてベクトル空間法(以下VSM)、擬似関連フィードバック(以下PRF。詳細は、C. Buckley, A. Singhal, M.Mitra and G. Saltonm, "New retrieval approaches using smart", Proceedings of Text Retrieval Conference，pp.25-48, 1996参照)、LSI（非特許文献８参照）およびPLSI（非特許文献９参照）を用いた。本節では、実施形態に係る手法および前記の比較手法のパラメータ等について説明する。
【００４８】
まず、全手法で共通する設定について説明する。これらの手法で用いる重み付けとしては、2進重みとIDF重みの両方で実験を行い、良好な結果が得られた重みを採用した。その結果、実施形態に係る手法は2進重みを、その他の手法ではIDF重みを採用した。ただしユークリッドノルムで正規化したものを用いた。
次にパラメータの決定方法について説明する。まず、PRFについて説明する。実験ではPRFを以下のように考えた。まず、検索質問拡張のための文書集合Eは以下の式で定義した。
【００４９】
【数１４】
2008181296.tif 000017
ここで、qは元の検索質問ベクトルである。このとき、拡張した検索質問ベクトルを以下の式で定義した。
【００５０】
【数１５】
2008181296.tif 000018
【００５１】
【数１６】
2008181296.tif 000019
【００５２】
ここで、τについては、0.7から0.99まで0.01刻みで実験を行い、最良の結果が得られたものを採用した。また、λについては、1と2で実験を行い、良好な結果が得られたものを採用した。
次に、LSIについて説明する。LSIの次元としては、200次元から400次元まで5次元刻みで実験を行い、最良の結果が得られた次元d1を採用した。
【００５３】
最後に、PLSIについて説明する。PLSIとしては、非特許文献９で提案されているPLSI-Qを用いて200次元から400次元まで50次元刻みで実験を行い、最良の結果が得られた次元d2を採用した。なお、PLSIはEMアルゴリズムの初期値によって結果が異なるので、10回検索を行い、その結果の平均を結果とした。
【００５４】
3．実験1:単語のみによる検索（実施形態１）
まず、検索質問ベクトル、画像ベクトルとして、画像特徴量を用いず、テキストのみを用いた検索を行った（実施形態１）。実施形態１に係る手法（本手法１）による性能を従来手法と比較した。実験1におけるパラメータの平均、標準偏差を表2に示す。実験結果として、平均適合率を表3に、各手法の検索時間（秒）を表4にそれぞれ示す。ここで、平均適合率は、検索手法の性能を示す指標の一つであり、その値が大きいほど検索性能が高いことを示している。
【００５５】
【表２】
2008181296.tif 000020
【００５６】
【表３】
2008181296.tif 000021
【００５７】
【表４】
2008181296.tif 000022
【００５８】
表3に示すように、平均適合率では、本手法１が最良の結果を得た。本手法１は、15検索質問中13検索質問で最良の結果が得られた。これらのことから、本手法１は、多くの検索質問に対して検索性能が優れているということがいえる。本手法１で最良の結果が得られなかった検索質問は、「house cat」、「wedding」であり、これらに対してはLSIが優れていた。
また、表4が示すように、検索質問あたりの平均検索時間ではVSMが最も優れていた。これは、VSMにおいては、検索質問ベクトル、画像ベクトルが疎なベクトルであるためと考えられる。本手法１の検索時間は0.18秒であり、4番目の結果であった。
【００５９】
一般に、検索性能と検索時間はトレードオフの関係にある。しかしながら、実験では、本手法１は、LSIやPLSIとほとんど変わらない検索時間で、これらを上回る検索性能が得られるということが分かった。これは、本手法１の優れた特徴であるといえる。
【００６０】
4．実験2:画像特徴量を考慮した検索（実施形態２）
実験2では、画像特徴量を考慮して検索を行った（実施形態２）。実施形態２に係る手法（本手法２）による検索性能の向上を検証した。まず、表5に、実験2における各手法のパラメータの平均、標準偏差を示す。
【００６１】
【表５】
2008181296.tif 000023
【００６２】
画像特徴量としては、均等量子化によって8色に減色した色を用いた。具体的には、ある色が対象画像における全画素の2割以上を占めている場合、その色が画像をよく表していると考える。
実験2の結果として、平均適合率を表6に示す。
【００６３】
【表６】
2008181296.tif 000024
【００６４】
平均適合率は、本手法２、VSM、PRFにおいて向上がみられた。一方、LSI、PLSIでは、平均適合率が低下した。また、実験１と同様に、本手法２が最も良い結果だった。本手法２は、15検索質問中11検索質問で最良の結果が得られた。これらのことから、画像特徴量を用いた場合において、本手法２は本手法１や他の手法よりも検索性能が優れているといえる。
【００６５】
図1に、各手法の再現率-適合率グラフを示す。ここで、再現率と適合率とは、情報検索の性能を示す２つの指標として知られたものである。適合率は、検索によって得られた結果に含まれる正解の割合である。適合率が１に近いほど、検索結果に誤りが少ない。また、再現率は、データベース中の正解のうち、検索結果として抽出されたものの割合である。再現率が１に近いほど、検索結果に漏れが少ない。一般に、再現率と適合率が両立することは難しい。再現率をＸ軸、適合率をＹ軸にとり、ある検索手法の評価結果をプロットすると、Ｘ軸が１に近い領域で適合率が０に近い値をとり、Ｙ軸が１に近い領域で再現率が０に近い値をとる。原点からより離れてプロットされるものが、優れた検索手法といえる。
特に、我々が日常多用しているインターネット検索では、再現率よりも適合率が重視される。即ち、正解をより多く抽出することより、抽出された結果の中に含まれる正解の割合が重視される。しかし、例えば、判例の検索などでは、再現率が重視される。即ち、正解を漏らさず抽出することがより重要視される。抽出結果の中にある程度の不正解が含まれていても許容される。このように、検索の目的によって重視される指標が異なる。なお、前述の平均適合率は、再現率-適合率グラフのＸ軸（再現率）上の複数の点における適合率の平均値として算出される値である。
図1に示すように、再現率0.1付近では本手法２が他の手法と比べてかなり優れている。一方、高再現率では、全ての手法において満足な結果が得られなかった。画像特徴量を考慮しない場合と比べて検索結果が向上したことと、この結果とをふまえると、画像の色は確かに画像を表す有効な特徴であるが、識別性能としては必ずしも満足なものではないということがいえる。検索性能をさらに向上させるには、識別性能の高い画像特徴を利用する必要があると考えられる。
次に、実験２の結果として、各手法における検索時間を表7に示す。
【００６６】
【表７】
2008181296.tif 000025
【００６７】
表7に示すように、本手法２、VSMおよびPRFでは、検索時間の増加がみられた。特に、本手法２は、約0.02秒と、約10%の増加がみられた。一方、LSI、PLSIにおいては、検索時間の増加はみられなかった。本手法２の時間が他と比べて大幅に増加した理由としては、１つの類似度を求めるのに輸送問題を解く必要があるからであると考えられる。
【００６８】
ヒッチコック型の輸送問題では、需要地の数をm、供給地の数をnとしたとき、その解を求めるには、O((nm)4)の計算量を要する（simplex法で解く場合）。したがって、今後、検索性能を向上させるために画像特徴量を増やすことを考える場合、検索時間の増加に対処する必要がある。
【００６９】
次に、実施形態２で、コンピュータが実行する画像検索の処理手順を説明する。図４は、この実施形態に係る画像検索の手順の概要を示すフローチャートである。検索質問としてのテキストがユーザーによって入力されたとき、コンピュータは、図４に示す処理を実行する。入力可能なテキストは、1語以上である。ところで、前述の実験では、検索対象のデータベースに8565個の索引語が存在している。従って、検索質問ベクトルqは、8565次元のベクトルとして定義される(n=8565)。テキストが入力されると、コンピュータは、検索質問ベクトルqを格納する領域をコンピュータのメモリ上に割り当てる（ステップS13）。図５は、検索質問ベクトルqと画像ベクトルIiとそれらの間に定義されるコストcijとの関係を示す説明図である。例えば、表1の"flower"と"red"の2語が検索質問として入力されると、コンピュータは、ベクトルqの要素として、"flower"と"red"に一致する要素の値のみを1とし、他を0にする（ステップS15）。ただし、これは、2進重みを用いる場合である。IDF重みの場合は、式（９）を用いて要素の値を計算する。このようにして、検索質問ベクトルqの各要素が決定される。なお、ベクトルqのどの要素とも一致しない検索質問が入力された場合、コンピュータは、その検索質問に対し、ベクトルqのいずれの要素の値も変えない。
次に、コンピュータは、EMDの計算に用いるコストcijを取得する（ステップS17）。ここで、各画像ベクトルIiと、データベース中の各索引語および各画像特徴量の間のコストとは、データベースに画像が登録されたときに予め求められている。コストは、式（１０）の説明の要領で算出される。例えば、上記検索質問"flower","red"に該当する画像の画像ベクトルIiは、図５のように、索引語として"flower","april"が付けられており、赤色の画像特徴量を有している。
コンピュータは、検索質問ベクトルqの0でない要素と、画像ベクトルIiの各要素との間のコストを、予め算出されたコストから取得する。検索質問ベクトルqの各要素は、データベース中の各索引語、即ち、画像ベクトルIiの索引語としての要素に対応しているので、コストcijに対応する値は、予め計算されたコストの中に見出すことができる。
コンピュータは、取得されたコストcijを用いて、データベース中の各画像についてEMDを算出する（ステップS19）。式（６）に示すように、EMDは、fijとcijから算出される。ここで、fijは、式（５）を用いて算出される。式（５）のrpiは、画像ベクトルIiの各要素（tijまたはcik）の値である。それらの値も、予め算出されている。また、式（５）のrqjは、検索質問ベクトルqの各要素tqjの値である。
コンピュータは、各画像についてEMDを算出した後、その値の小さい順にEMDに係る画像を特定する（ステップS21）。そして、特定した順に、検索結果としての画像を出力（ユーザーに提示）する（ステップS23）。
【００７０】
5．本手法の近似方法に関する検討（実施形態３）
本節では、本手法の検索時間を短縮するための近似方法について検討する。具体的な近似の方針として、検索対象をあらかじめ絞り込むことについて考える。本手法では、検索質問と画像の索引の間に定義された単語間のコストが全て1であるとき、検索質問と画像のEMDは1になる。そこで、このような画像に対してはEMDを計算しないことにすれば、計算速度の向上が期待できる。加えて、単語間のコストが1に近いような場合、そのコストを近似的に1と見なすことで計算量の削減がさらに見込める（実施形態３）。このことを実験的に確かめる。
まず、単語間のコストを次のように定義し直す。
【００７１】
【数１７】
2008181296.tif 000026
ここで、tは閾値であって、0以上、1以下の値をとる。そして、
【００７２】
【数１８】
2008181296.tif 000027
【００７３】
がt以上の場合、単語wiとwj間のコストを１とする。上式（１４）のコストを用いて、画像検索を行い、平均適合率、及び、EMD計算対象となる画像の割合を調べた。実験は、t=0.1から0.1刻みで1まで行った。実施形態３に係る手法（本手法３）の実験結果を図2、3に示す。図2は、各閾値に対する平均適合率を示すグラフである。図3は、各閾値に対し、EMDの計算対象となる画像の割合を示すグラフである。図2、3に示すように、t=0.8のとき、EMDの計算対象となる画像の割合が約8%であるにもかかわらず、0.14程度の平均適合率が得られた。このことは、LSI程度の検索性能を保ちながら、計算量を8%程度に削減できることを意味している。
【００７４】
さらに、類似度を高速に計算する方法について次のことが考えられる。実験のデータでは、需要地と供給地の間のコストの内の9割程度が1、即ち、共起回数が0であった。このようなコストが１になる経路は、いわばノイズとして働いていると考えられる。従って、もし、ヒッチコック型の輸送問題を解く代わりに、前記のようなコストが1の経路を無視した輸送問題を解くことができれば、検索時間の大幅な削減が見込める上、検索性能もあまり変わらないのではないかと考えられる。
【００７５】
以上のように、本手法の有効性を確認するため、12295枚の画像を対象にして、LSI、PLSIなどの従来手法との比較実験を行った結果、本手法１，２において、平均適合率において、最良の結果が得られた。また、処理の高速化のために、近似方法を検討した結果、本手法３において、LSIと同程度の検索性能を保ちながら、理想的には計算量を約8%に削減できることが分かった。
【００７６】
この実施形態では、均等量子化により8色に減色した色がそれぞれ閾値以上の割合で含まれているか否かの条件を画像特徴量として用いた。しかし、本手法が適用可能な画像特徴量は、これに限定されない。異なる画像特徴を用いることによって検索精度が向上する可能性がある。また、実施形態３として、近似による検索時間短縮の一例を示したが、他の近似手法を適用することにより、あるいは、Earth Mover's Distanceの計算方法を工夫することにより、さらに処理時間を短縮できる可能性がある。
【００７７】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【図面の簡単な説明】
【００７８】
【図１】画像を考慮した場合における再現率-適合率グラフである。
【図２】実施形態３の近似手法において、各閾値に対する平均適合率を示すグラフである。
【図３】実施形態３の近似手法において、各閾値に対し、EMDの計算対象となる画像の割合を示すグラフである。
【図４】実施形態２に係る画像検索の手順の概要を示すフローチャートである。
【図５】検索質問ベクトルqと画像ベクトルIiとそれらの間に定義されるコストcijとの関係を示す説明図である。
【符号の説明】
【００７９】
ｑ    検索質問ベクトル
Ｉi    画像ベクトル
ｃij   コスト
【図４】
2008181296.tif 000028
【図５】
2008181296.tif 000029
【図１】
2008181296.tif 000030
【図２】
2008181296.tif 000031
【図３】
2008181296.tif 000032