(57)【要約】【課題】画像を含む文書群から、目的の画像、目的の画像を含む文書、目的の文書に関連する画像を高精度で検索する。【解決手段】文書中の各図を、当該図の特徴量を量子化した擬似単語と、当該図の説明箇所から抽出された用語とで表現した第１のインデックスを生成する。擬似単語及び／又は用語の共起頻度に基づいて、擬似単語及び／又は用語間の関係性の強さと擬似単語及び／又は用語の重要度とを計算する。その後、重要度を付した擬似単語及び／又は用語を重み付きノードとし、擬似単語及び／又は用語間の関係性の強さを付したエッジを重み付きエッジとして第２のインデックスを生成する。かかる前処理で生成された第２のインデックスを検索対象とし、重み付きノードと重み付きエッジで表現した加工済みクエリーとの類似度を表すスコア値を計算する。【選択図】図２
2011248596.tif 000002
【特許請求の範囲】
【請求項１】
文書中の各図について、当該図の特徴量を量子化した擬似単語と、当該図の説明箇所から抽出された用語とで表現される第１のインデックスを生成する機能部と、
擬似単語及び／又は用語の共起頻度に基づいて、擬似単語及び／又は用語間の関係性の強さと擬似単語及び／又は用語の重要度とを計算する機能部と、
前記重要度を付した擬似単語及び／又は用語を重み付きノードとし、擬似単語及び／又は用語間の関係性の強さを付したエッジを重み付きエッジとして第２のインデックスを生成する機能部と、
検索クエリーから、重み付きノードと重み付きエッジで構成される加工済みクエリーを生成する機能部と、
重み付きノードと重み付きエッジで構成される前記第２のインデックスと前記加工済みクエリーとの類似度を表すスコアを計算することにより、検索クエリーに類似する図及び／又は文書を検索する機能部と
を有することを特徴とする検索システム。
【請求項２】
請求項１に記載の検索システムにおいて、
前記擬似単語及び／又は用語間の共起頻度に基づいて計算される遷移確率行列の固有ベクトルを解くことにより、擬似単語及び／又は用語間の関係性の強さと用語及び／又は擬似単語の重要度を計算する
ことを特徴とする検索システム。
【請求項３】
請求項１に記載の検索システムにおいて、
前記重み付きエッジには遷移方向が規定されており、各ノードのエッジからの重みの流入量と流出量が同じである
ことを特徴とする検索システム。
【請求項４】
請求項１に記載の検索システムにおいて、
検索クエリーを、前記第２のインデックスに対応するネットワーク上で隣接するノード及びエッジまで拡張する機能部
を更に有することを特徴とする検索システム。
【請求項５】
請求項４に記載の検索システムにおいて、
拡張後の検索クエリーでは、拡張されたノードとエッジの重みとして、拡張前の重みに拡張元の検索クエリーからの伝搬確率を乗算した値を用いる
ことを特徴とする検索システム。
【請求項６】
請求項２に記載の検索システムにおいて、
前記遷移確率行列は、検索対象とする文書の分野に応じて作成される
ことを特徴とする検索システム。
【請求項７】
請求項１に記載の検索システムにおいて、
前記第２のインデックスに対応するネットワークをユーザインタフェース画面上に表示すると共に、当該第２のインデックスに対応する特徴点を対応する図に重ねて表示する機能部
を更に有することを特徴とする検索システム。
【請求項８】
請求項１に記載の検索システムにおいて、
検索された図に対応する第２のインデックスのネットワーク構成をユーザインタフェース画面上に表示すると共に、スコアの計算対象となったノードとエッジをユーザインタフェース画面上で強調表示する機能部
を更に有することを特徴とする検索システム。
【請求項９】
請求項１に記載の検索システムにおいて、
検索結果としてユーザインタフェース画面に表示された図のうちユーザが選択した領域部分を、新たな検索クエリーとして受け付ける機能部
を更に有することを特徴とする検索システム。
【請求項１０】
文書中の各図について、当該図の特徴量を量子化した擬似単語と、当該図の説明箇所から抽出された用語とで表現される第１のインデックスを生成する処理と、
擬似単語及び／又は用語の共起頻度に基づいて、擬似単語及び／又は用語間の関係性の強さと擬似単語及び／又は用語の重要度とを計算する処理と、
前記重要度を付した擬似単語及び／又は用語を重み付きノードとし、擬似単語及び／又は用語間の関係性の強さを付したエッジを重み付きエッジとして第２のインデックスを生成する処理と、
検索クエリーから、重み付きノードと重み付きエッジで構成される加工済みクエリーを生成する処理と、
重み付きノードと重み付きエッジで構成される前記第２のインデックスと前記加工済みクエリーとの類似度を表すスコアを計算することにより、検索クエリーに類似する図及び／又は文書を検索する処理と
を有することを特徴とする検索方法。
【請求項１１】
請求項１０に記載の検索方法において、
前記擬似単語及び／又は用語間の共起頻度に基づいて計算される遷移確率行列の固有ベクトルを解くことにより、擬似単語及び／又は用語間の関係性の強さと用語及び／又は擬似単語の重要度を計算する
ことを特徴とする検索方法。
【請求項１２】
請求項１０に記載の検索方法において、
検索クエリーを、前記第２のインデックスに対応するネットワーク上で隣接するノード及びエッジまで拡張する処理
を更に有することを特徴とする検索方法。
【請求項１３】
請求項１２に記載の検索方法において、
拡張後の検索クエリーでは、拡張されたノードとエッジの重みとして、拡張前の重みに拡張元の検索クエリーからの伝搬確率を乗算した値を用いる
ことを特徴とする検索方法。
【請求項１４】
請求項１０に記載の検索方法において、
前記第２のインデックスに対応するネットワークをユーザインタフェース画面上に表示すると共に、当該第２のインデックスに対応する特徴点を対応する図に重ねて表示する処理
を更に有することを特徴とする検索方法。
【請求項１５】
請求項１０に記載の検索方法において、
検索された図に対応する第２のインデックスのネットワーク構成をユーザインタフェース画面上に表示すると共に、スコアの計算対象となったノードとエッジをユーザインタフェース画面上で強調表示する処理
を更に有することを特徴とする検索方法。
【請求項１６】
請求項１０に記載の検索方法において、
検索結果としてユーザインタフェース画面に表示された図のうちユーザが選択した領域部分を、新たな検索クエリーとして受け付ける処理
を更に有することを特徴とする検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像とその画像を含む文書中のテキスト情報を利用して、画像（例えば図）を含む文書（例えば論文、Web）から目的とする画像や類似画像を検索するための技術に関する。
【背景技術】
【０００２】
近年、科学技術論文のオープン化及び世の中の情報公開の潮流の下、各種文書のウェブ（Web）上での公開が増加している。これに伴い、画像（図）を含む文書の検索の重要がますます増加している。その中でも、画像に情報が集約する分野、テキスト部分に記述されない情報が画像に含まれ易い分野においては、画像とテキストを関連づけた検索が重要である。
【０００３】
現在、画像のみを対象とする検索には、画像解析の結果を利用するデジタル写真や医療画像の類似検索技術などが使用されている。一方、テキストのみを対象とする検索には、クエリーに含まれる用語を含む文書検索、クエリーとして与えられた文書と類似する文書を検索する類似文書検索などが用いられている。なお、これらのテキスト検索では、単語や概念認識した用語ごとのインデックスを文書ごとに予め用意する手法が用いられる。また、画像とテキストを融合する検索では、画像周りに存在するテキストを利用して画像を検索する方法、画像の特徴量とテキスト情報を利用する方法などが用いられる。なお、画像とテキストを融合する検索では、テキスト検索の後に画像検索を実行する方法などもある（非特許文献１及び２）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Kherfi, M.L., Ziou, D. and Bernardi, Learning from Negative Example in Relevance Feedback for Content-Based Image Retrieval, 16th International Conference on Pattern Recognition (ICPR'02) - (2002).
【非特許文献２】Athitsos, V. and Swain, MJ. Distinguishing photograph and graphics on the World Wide Web, In Proc. of the IEEE Workshop on Content-Based access of Image and Video Libraries (San Juan, Puerto Rico), 10-17 (1997).
【非特許文献３】T. Hoffman , Learning and representing topic. A hierarchical mixture model for word occurrence in document databases. In Workshop on learning from text and the web, CMU., 1998.
【非特許文献４】Tuytelaars, T. and Gool, LC. Wide Baseline Stereo Matching based on Local, Affinely Invariant Regions, BMVC pp.412-415, 2000.
【非特許文献５】Matas, J. Chum, O.Urban, M. and Pajdla, T. Robust wide baseline stereo from maximally stable extremal regions. In BMVC pp.384-393, 2002.
【非特許文献６】Lowe, D. Object Recognition from Local Scale-Invariant Features. Proc. of IEEE International Conference on Computer Vision (ICCV) pp1150-1157, 1999.
【非特許文献７】Kadir, T., Zisserman, A., and Brady, M. An affine invariant salient region detector. In Proc. of the 8th Eur. Conf. on Comp. Vision, Prague, Czech Republic, pp.345-457, 2004.
【非特許文献８】Belongie, S. Malik, and J. Shape, Matching and Object. Recognition Using Shape Contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24 (24), pp509-522, 2002.
【非特許文献９】Lowe, D.G. Object recognition from local scale-invariant features. In Int. Conf. on Comp. Vision, Corfu, Greece, pp. 1150-1157, 1999.
【非特許文献１０】Ke, Y.. PCA-SIFT: A More Distinctive Representation for Local Image Descriptors.  IEEE Comp. Soc. Conf. on Comp. Vision and Pattern Recognition (CVPR'04) pp.511-517, 2004．
【非特許文献１１】Schaffalitzky, F. and Zisserman, A.,“Multi-View Matching for Unordered Image Sets,” Proc. Seventh European Conf. Computer Vision, pp. 414-431, 2002.
【非特許文献１２】Van Gool, L., Moons, T. and Ungureanu, D., “Affine/Photometric Invariants for Planar Intensity Patterns,” Proc. Fourth European Conf. Computer Vision, pp. 642-651, 1996.
【非特許文献１３】Brin, S. and Page, L. The anatomy of a large-scale hypertextual Web search engine,  Computer Networks and ISDN Systems, 30(1-7) 1998.
【非特許文献１４】Stephen E. Robertson, Steve Walker, and Micheline Hancock-Beaulieu. Okapi at TREC-7. In Proceedings of the Seventh Text REtrieval Conference. Gaithersburg,  USA, November 1998.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ある文書に含まれる画像に近い画像を目的画像として検索したい場合がある。この場合、文書に含まれる画像の情報だけを利用すると、画像周りの文脈が無視される。このため、画像自体は類似しても、意味が異なる画像が検索される可能性がある。それでも、検索対象とする画像の数が少なければ、検索された画像が問題になることは少ない。しかし、検索対象とする画像の数が多くなると、目的とする画像の発見自体が困難となる。一方、画像周りのテキスト情報だけを利用する場合、画像周りの文脈は意図する画像に近くても、目的とする画像を得ることは困難となる。
【０００６】
この他、画像情報とテキスト情報の両方を利用する方法の適用が考えられる。この場合、図の周囲に位置する説明文を対象にテキスト検索を実行し、当該検索結果を利用して画像検索が実行される。ただし、この方法では、同義語などの問題でテキスト検索が不適切に終わる場合がある。また、この方法は、用語の曖昧性等の問題により、意味の異なる用語がヒットする場合がある。これらの場合、テキスト検索の結果が、画像検索に適した画像を含まない可能性がある。この場合には、画像情報とテキスト情報の両方を利用したとしても、十分な検索精度を確保することができない。
【０００７】
また、画像情報とテキスト情報を同時に扱う方式には、画像から特徴量を取り出して量子化し、テキストを構成する用語と同様にインデックス化して目的の画像を画像周りの説明文と共に検索する方法が考えられる。しかし、この方法だと、量子化された画像の特徴量をテキスト検索の場合における単語と同列に扱うため、複数の量子化された特徴量の集合によって画像の特徴が初めて現される場合を考慮することができない。すなわち、量子化された特徴量の組み合わせ効果を十分に考慮することができない。従って、この場合も、画像の類似度を十分な精度で検索できないことがある。
【０００８】
さらに、画像情報とテキスト情報を同時に扱う方式には、テキストと画像を潜在的意味インデクシング（ＬＳＩ：latent semantic indexing）により計算し、テキスト情報と画像情報を融合させる方法が考えられる。この種の方法は、文書群全体での整合性を計算する。このため、個々の画像の類似度レベルでの関連性をＬＳＩで表すことが難しい。
【０００９】
また、テキストと用語自身を関連づける方法には、multi-modal Hierarchical Aspect Modelsのように、図に付加（annotation）するテキスト用語自身が一般的でない語彙となるように工夫する方法もある（非特許文献３）。しかし、この方法は、テキストと図の関係性を見ることはできても、複数の図の間の類似性を明らかにできない。
【課題を解決するための手段】
【００１０】
前述したように、各画像から抽出された特徴量を量子化して擬似単語とし、テキスト情報と同様に検索する場合、テキスト情報のみの場合と同様に、単純に画像と文書を検索するだけでは十分な検索精度で類似画像を検索することができない。
【００１１】
そこで、本発明者は、用語・擬似単語の重要度で重みづけられたノードと、用語・擬似単語の関係性で重み付けられたエッジとから構成されるネットワーク（第２のインデックス）を生成し、当該ネットワークのノードの重みとエッジの重みを利用して、図又は文書を検索する手法を提案する。
【００１２】
また、本発明者は、クエリーが与えられた場合、エッジの強さやサブグラフを使用してクエリーを拡張し、目的とする画像や文書のスコア付けにおいて、ノードだけでなくエッジの重みを利用する手法を提案する。このクエリーの拡張時には、元のクエリー用語・擬似単語由来の重みから派生したノード及びエッジの重みを計算する。すなわち、クエリーの拡張時には、最初から与えられたノード、エッジの重みを使うのではなく、元のクエリーから伝搬（遷移）してきた割合と最初から与えられた重みとの積を利用する。これにより、用語及び擬似単語間の複数の組み合わせの効果を適切に計算することができる。
【００１３】
このように、本発明においては、画像の類似度を表すときに、画像を構成する各擬似単語及び画像説明文の各構成用語を独立に扱って類似性を計算するのではなく、擬似単語及び用語の組み合わせを考慮した類似度を評価する。このため、より精度の高い検索を実現できる。
【００１４】
また、前述したネットワーク（第２のインデックス）の生成時には、ノード（例えば用語・擬似単語）間の関係性の強さを表現した遷移確率行列の固有値問題を解くことにより、ノードの重みとエッジの強さを決定することが望ましい。各遷移確率は、例えばノード間の文書・画像中の共起頻度を利用して（例えば、tf（単語の出現頻度）*idf（逆出現頻度）を利用して）計算することができる。また、擬似単語間の関係性の強さの計算時には、画像内における擬似単語間の物理的距離を出現頻度と同時に考慮することにより、より類似検索の精度を上げることができる。
【発明の効果】
【００１５】
本発明は、文書を構成する用語及び／又は画像の特徴量に基づいて計算した擬似単語そのものの重要度だけでなく、それらの用語及び／又は擬似単語間の関係性の強さに基づいて類似文書検索、類似画像検索、説明文付画像検索を行う。また、本発明は、必要に応じ、ノードの重要度だけでなく、ノード間の関係の強さに基づいて、検索動作の実行前にクエリーを拡張する。
【００１６】
本発明によれば、用語及び擬似単語の独立した重要度だけでなく、それらとエッジの強さとを組み合わせた条件にて画像の類似度を評価することができる。特に、画像検索においては、ノードの情報を単独で用いたのでは、図の特徴を十分に表すことができない。このため、ノードの重みにエッジの強さを組み合わせた条件にて検索処理を実行することにより、検索精度を従来技術に比して向上させることができる。
【００１７】
また、本発明においてクエリーを拡張する場合には、拡張先のノード及びエッジの重みを元のクエリーからの伝搬を考慮して変更することにより、拡張後のクエリーが有するノード間の構造を検索結果に反映させることができる。
【００１８】
また、本発明においてノード間の関係性の強さを表現した遷移確率行列を固有値問題として解く場合には、用語と擬似単語の重要度を共通の条件にて計算することができる。すなわち、相対的な重みを用いる場合よりも検索精度を向上させることができる。
【図面の簡単な説明】
【００１９】
【図１】検索システムの概念構成を示す図。
【図２】検索システムで実行される検索動作の概要を説明する図。
【図３】(a)〜(e)は、画像から擬似単語を作成する例を説明する図。(a)は元の画像を示す図。(b)は画像から検出された特徴点を示す図。(c)は特徴点から計算された特徴量の結果を示す図。(d)は特徴量をクラスタリングして量子化し、擬似単語化した結果を示す図。(e)は画像の擬似単語による表現例を示す図。
【図４】(a)及び(b)はインデックスの一例を示す図。(a)は画像のインデックス例と画像の説明文のインデックス例を示す図。(b)は文書のインデックス例を示す図。
【図５】各用語・擬似単語の重要度を示す図と、擬似単語間、用語間、擬似単語−用語間の関係性の強さを示す図。
【図６−１】画像・文書検索システムのインターフェースの図。(a)はクエリーの画面例を示す図。(b)は検索結果の画面例を示す図。
【図６−２】画像・文書検索システムのインターフェースの図。(c)は検索結果の表示画面例を示す図。(d)は検索結果の図に特徴量を表示した画面例を示す図。(e)は重み付きのノードと重み付のエッジで構成されるネットワークに検索結果を表示した図。(f)はユーザが検索結果から図の一部を利用して検索する場合に使用する画面例を示す図。
【図７】ある文書・画像群を構成する擬似単語及び用語間の関係を示す図。(a)は遷移確率をエッジに有する有向グラフの例を示す図。(b)は遷移確率行列を解くことによりノードを構成する擬似単語・用語の各重要度を計算した結果を示す図。
【図８−１】図７の文書・画像群に対応する文書インデックス例を示す図。
【図８−２】図７の文書・画像群に対応する画像インデックス例を示す図。
【図８−３】図７の文書・画像群に対応するネットワーク上のノード（用語・擬似単語）の重みとエッジの重みのインデックス例を示す図。
【図９】クエリーがTerm B, Term C, Term Dで与えられた場合に、クエリー拡張を行なわない場合における文書・擬似文書（図）の検索例を説明する図。
【図１０】(a)はクエリーがTerm Bで与えられた場合において、１段階のクエリー拡張を行った場合の文書・擬似文書（図）の検索結果を示す図。(b)はクエリーがterm Bで与えられた場合において、２段階のクエリー拡張を行った場合の文書・擬似文書（図）の検索結果を示す図。
【図１１】(a)はクエリーがterm Bで与えられる場合において、図に関してだけ１段階のクエリー拡張を行う例を説明する図。(b)はクエリーがterm Bで与えられる場合において、用語に関してだけ１段階のクエリー拡張を行う例を説明する図。
【図１２】(a)はクエリーがF1, F4, F8の場合において、クエリー拡張を行わない例を説明する図。(b)はクエリーがF1, F4, F8の場合において、図に関してだけ１段階のクエリー拡張を行う例を説明する図。
【図１３】(a)はクエリーがterm AとF1, F3, F8との組み合わせで与えられる場合において、クエリー拡張を行わない例を説明する図。(b)はクエリーがterm AとF1, F3, F8との組み合わせで与えられる場合において、図及び用語に関して１段階のクエリー拡張を行う例を説明する図。
【図１４】図の類似度を説明する図。(a)はある図Ａを量子化した特徴量を黒くハイライト表示した図。(b)はある図Ｂを量子化した特徴量を黒くハイライト表示した図。
【図１５】(a)はある図Ａの遷移確率行列の固有値問題を解いて擬似単語間の関係性を表示した図。(b)はある図Ｂの遷移確率行列の固有値問題を解いて擬似単語間の関係性を表示した図。
【図１６】クエリーがterm Bで与えられる場合において、図と用語に関して１段階のクエリー拡張を行う例を説明する図。
【発明を実施するための形態】
【００２０】
以下、図面に基づいて、本発明の実施例を説明する。なお、後述する装置構成や処理動作の内容は発明を説明するための一例である。本発明には、後述する装置構成や処理動作を組み合わせた発明、後述する装置構成や処理動作に既知の技術を組み合わせた発明、後述する装置構成や処理動作の一部を既知の技術と置換した発明も含まれる。
【００２１】
（検索システムの構成）
図１に、画像、用語、文書を検索対象とする検索システム１０の構成例を示す。検索システム１０は、ストレージ２０と計算機３０で構成される。ストレージ２０は、画像を含む文書、テキスト文書、画像をデジタルデータとして格納する。計算機３０は、不図示の入力装置を通じて与えられたクエリーに基づいてストレージ２０を検索し、検索結果をユーザに提示する。計算機３０は、いわゆるコンピュータ構成を有する。すなわち、計算機３０は、演算装置、記憶装置、入出力装置及び制御装置で構成される。なお、計算機３０には、不図示の入力装置（例えばマウス、キーボード、ポインティングデバイス）や出力装置（例えば表示装置）が接続される。
【００２２】
検索動作に関連する信号処理は、コンピュータ上で実行されるプログラムの処理機能を通じて実現される。もっとも、信号処理の全てが１台のコンピュータ上で実行される必要は無い。すなわち、後述する信号処理は、複数台のコンピュータの協働により実行しても良い。また、後述する信号処理の一部は、ハードウェア上で実行しても良い。
【００２３】
また、検索システム１０を構成するストレージ２０は１台に限る必要はなく、複数台のストレージ２０で構成されていても良い。また、ストレージ２０と計算機３０との接続は、一般には、ネットワーク経由での接続を想定する。ネットワークは、イントラネットでも良く、インターネットでも良い。
【００２４】
（検索システムの基本動作）
図２に、検索システム１０で実行される検索動作の概要を示す。当該検索動作は、前処理１００と、クエリーの入力処理１０８と、入力されたクエリーから検索に適した情報を抽出する前処理１０９と、抽出された情報（加工済みクエリーと呼ぶ）１１０を用いた検索処理１０７と、検索結果（解）を提示する処理１１１とで構成される。なお、検索処理１０７では、加工済みクエリーを必要に応じて拡張することがある。
【００２５】
以下、検索用のプログラムを通じて実現される各処理の詳細内容を説明する。
（前処理）
まず、前処理１００の内容を説明する。前処理１００では、画像入り文書ＤＢ１０１に含まれる画像と文書のそれぞれから特徴量を抽出する処理と、抽出された特徴量から検索用のインデックスを作成する処理が実行される。ここでの画像入り文書ＤＢ１０１はストレージ２０上に構築される。
【００２６】
まず、前処理１００においては、プログラムは、画像入り文書ＤＢ１０１の文書を画像とその説明文に分割する。次に、プログラムは、画像から特徴量を抽出し、抽出された特徴量を量子化する。量子化により、特徴量は擬似単語化される（１０３）。特徴点の検出には、Intensity based regions （非特許文献４）、Maximum stable extremal Regions detector (MSER)（非特許文献５）、Hessian-affine（非特許文献６）、Entropy-based regions (salient regions)（非特許文献７）、その他の多様な方法を利用できる。検出した特徴点の特徴量の計算には、shape context（非特許文献８）、Gradient orientation histogram - SIFT (Lowe’99)（非特許文献９）、PCA-SIFT （非特許文献１０）、Complex filters（非特許文献１１）、Moment invariants（非特許文献１２）、その他の多様な方法を利用できる。どの手法が最適かは、画像群の質に依存する。このため、画像群に適した手法を選択する必要がある。これらの手法によって得られた特徴量を量子化する方法には、k-means クラスタリングなどがある。クラスターの数も、類似検索に適した量子化値となるように、テストする必要がある。
【００２７】
図３の（ａ）〜（ｅ）に、画像（図）の特徴量の抽出から特徴量の量子化までの処理イメージを示す。ここで、図３の（ａ）が元の画像（図）２０１である。図３の（ｂ）は、画像２０１から特徴点（楕円で囲んで示す）を検出した状態２０２を示す図である。図３の（ｃ）は、特徴点から特徴量を計算した結果２０３の一例を示す図である。図３の（ｄ）は、各特徴量をクラスタリングして量子化し、多次元の特徴量（擬似単語）に変換した状態２０４を示す図である。ここでのCL*（＊は１、２…Ｎ）は、特徴点に対応付けられた擬似単語を示す。図３の（ｅ）は、画像を量子化された特徴量（擬似単語）の集合として表した状態２０５を示す図である。
【００２８】
一方、プログラムは、文中の用語を認識し、画像の説明文から用語を取り出す（１０２）。この実施例の場合、画像の説明文を、画像の周囲にレイアウトされた文として定義する。周囲の範囲は、検索結果の精度等を考慮して適宜設定する。ここで、用語は、辞書データ等を用いることにより、同義語を同じ概念として認識することが望ましい。また、必要に応じ、文脈を判断し、用語的曖昧性を解決することが望ましい。
【００２９】
次に、プログラムは、擬似単語と図を説明している用語を画像毎に組み合わせてインデックスを作成する（１０４）。すなわち、擬似文書化を作成する。図４の（ａ）及び（ｂ）にインデックスの作成例を示す。図４の（ａ）は画像のインデックス３００の例であり、図４の（ｂ）は文書のインデックス３０３の例である。画像のインデックス３００は、各画像に関連する用語（Term）の頻度の集合３０１と、画像から抽出された特徴点の頻度の集合３０２で構成される。一方、文書のインデックス３０３は、各文書に関連する用語（Term）の頻度の集合３０４と、文書に関連する画像から抽出された特徴点の頻度の集合３０５で構成される。ここでのインデックスが特許請求の範囲における第１のインデックスに対応する。
【００３０】
この後、プログラムは、ノード（用語や擬似単語）の重要度を計算すると共に、エッジ（用語同士間、擬似単語同士間、用語と擬似単語間）の関係性の強さを計算する（１０５）。すなわち、重み付きノードと強度付きエッジで構成されるネットワークを生成する。この後、プログラムは、計算された重み付きノード（擬似単語や用語の重要度）と、強度付きエッジ（ノード間の関係性の強さ情報を付したエッジ）を組み合わせた検索用のインデックスを作成する（１０６）。ここでのインデックスが特許請求の範囲における第２のインデックスに対応する。
【００３１】
図５に、ネットワークを構成するノードの重み４０１とエッジの重み４０２の組み合わせで構成されるインデックス例を示す。ノードの重み４０１やエッジの重み４０２を与える重要度は、一般的に分野ごとに異なる。換言すると、分野毎に重みの数値が異なる。従って、ノードの重み４０１やエッジの重み４０２は、分野ごとに計算することが望ましい。また、１つの文書毎に文書を構成する用語と図のネットワーク（インデックス）を計算し、当該文書のネットワークとクエリーのネットワークとの類似度合い（スコア）を計算しても良い。すなわち、文書とクエリーとの類似具合を検索しても良い。
【００３２】
前述したネットワークの生成方法には幾つかの方法がある。以下に、一例を示す。例えば用語、擬似単語間の遷移確率行列を作成し、その固有値問題を解くことにより生成することができる。この場合、擬似単語や用語をネットワークのノードとして扱い、ノードの関係性をネットワークのエッジとして扱う。また、擬似単語や用語の重要度をノードの重みとして扱い、擬似単語と用語の関係性の強さがエッジの重みとして扱われる。ここで、エッジの重みは、エッジと遷移確率の積として定義する。
【００３３】
例えばノード間の遷移確率行列Ｔは、ある用語又は擬似単語を起点としたときのtf*idfや共起頻度等の文書検索システムのスコアSij（ここで、i，jは用語又は擬似単語）を用い、次式（式１）を要素とする行列の転置行列として規定する。
【００３４】
【数１】
2011248596.tif 000003
【００３５】
ここで、Pij （ここで、ｉとｊは用語又は擬似単語）は、エッジEij（ノードｉからノードｊへのエッジ）の遷移確率である。Pij は、次式（式２）の関係を満たす。
【００３６】
【数２】
2011248596.tif 000004
【００３７】
コンピュータは、この遷移確率行列Ｔの固有値問題（式３）を既知の演算処理により解く。
【００３８】
【数３】
2011248596.tif 000005
【００３９】
ここで、λは固有値、Vは固有ベクトルである。ｉ番目のノードの重みは固有ベクトルVのi番目の要素となる。規格化する場合は、ノードの重みを、固有ベクトルVのi番目の要素*1/固有ベクトル要素の総和とする。エッジEijの強さはノードの重みと遷移確率Pijの積として規定する。
【００４０】
図７の（ａ）に、遷移確率行列Ｔを構成する要素の関係を有向エッジで表したネットワーク形式で表現した例を示す。図中、５２１はノードであり、５２２は遷移確率付きのエッジである。図７の（ｂ）に、ノードｉの重みWi とエッジEijの重みTijをネットワーク上にマッピングした例を示す。重みWi は、遷移確率行列Ｔの固有値問題を解くことで算出される。図中、５２３は重み付きノードであり、５２４は関係性の強さ付きのエッジである。
【００４１】
なお、固有値が複数存在して固有ベクトルが一意に決まらない場合には、例えば次式（式４）に示すように、Pijのデフォルト値として1/Mを追加する等してグラフを強連結構造とし、固有ベクトルが一意に決まるようにする。
【００４２】
【数４】
2011248596.tif 000006
【００４３】
ここで、遷移確率行列Ｔの要素には、Sij（＝tf*idf）のスコア、Okapi BM25（非特許文献１４）や超幾何分布等のスコアを利用できる。なお、Sij のスコアを与えるtfは、i番目の用語又は擬似単語をクエリーとして部分文書集合を得る場合における部分文書集合中におけるj番目の用語又は擬似単語の出現頻度である。一方、idfは、log10（データベース中に現れる文書又は擬似文書の数／j番目の用語又は擬似単語が現れる文書・擬似文書の数）により算出される。
【００４４】
なお、前述したように遷移確率行列Ｔを固有値と固有ベクトルについて解く代わりに、以下の漸化式（式５又は式６）を解くことによりノードの重要度とエッジの強さを算出しても良い（非特許文献１３）。
【００４５】
【数５】
2011248596.tif 000007
【００４６】
【数６】
2011248596.tif 000008
【００４７】
前式において、I(Ni)はｉ番目のノードの重要度である。また、Out(Nj)は、ｊ番目のノードからｋ番目のノードに遷移するｋ番目のノードの全ての組を示す。In(Ni)は、ｊ番目のノードからｉ番目のノードに遷移するｊ番目のノードの全ての組を示す。さらに、dは定数であり、0.8-0.99程度の値を採る。スコアSijには、前述したように、tf*idf、Okapi BM25等のスコア値を使用できる。さらに、他の方法を用いてエッジの重みT とノードの重みW を決めても良い。なお、あるノードに対するエッジからの流入量と流出量は同じであることが望ましい。すなわち、次式（数７）が成立することが望ましい。
【００４８】
【数７】
2011248596.tif 000009
【００４９】
（操作画面）
続いて、クエリーの入力と検索結果の表示に関するプログラムの処理を説明する。なお、後述する画面は、クエリー入力処理１０８と検索結果（解）を提示する処理１１１で表示される操作画面に対応する。
【００５０】
本実施例において、プログラムは、テキスト、手元の図又は文書をクエリーとする。また、プログラムは、付随テキスト情報と図の複合文書、文書のみ、図のみのいずれかを検索対象とする。図６−１の（ａ）に、クエリーの入力時に使用する検索システムの画面５０１の表示例を示す。画面５０１は、テキストクエリーの入力欄５０２、図クエリーの入力欄５０３、文書クエリーの入力欄５０４、検索対象選択欄５０５、検索開始ボタン５０６、アップロードボタン５０６Ａで構成される。これらのうち入力欄５０４に対応する文書クエリーは、付属テキスト情報と図の複合文書をクエリーとするものをいう。文書クエリーの入力は、文書ＩＤの入力によっても、対応文書のアップロードによっても行うことができる。検索対象選択欄５０５の○印は、検索対象の選択及び選択状態を示すボタンである。検索対象が選択されると、例えば○印は●印に変化する。アップロードボタン５０６Ａは、計算機３０が内部に格納する図や文書（図と説明文）をクエリーとして取り込むためのボタンである。
【００５１】
次に、解の提示（すなわち、クエリーに対する検索結果の表示）に関するプログラムの処理を説明する。なお、必要であれば、検索結果として表示された図や文書のうち目的とする図や文書に近いものをクエリーとして選択し、新たに設定されたクエリーについて再度検索を行うこともできる。図６−１の（ｂ）に、検索結果表示画面５０７の表示例を示す。検索結果表示画面５０７は、類似度が高いとして検索された図の表示欄５０９と図に関連するテキストの表示欄５１０、各表示欄に表示された図やテキストを新たなクエリーとしてプログラムに入力するための選択ボタン５０８、画面内で新たに指定されたクエリーを用いた検索（relevance feedback）の実行を指示する検索開始ボタン５１１で構成される。なお、検索結果表示画面５０７には、図と関連するテキストを特徴付けるネットワーク構造を表示するための詳細表示ボタン５１２と、表示欄５０９に表示された各図の一部分を新たなクエリーとして指定するための部分画像選択ボタン５１３も表示される。
【００５２】
図６−２に、検索結果表示画面５０７に表示される画像の内容やボタンとの関係を示す。なお、図６−２は、検索対象を「図＋説明文」としたときの検索結果の例である。図６−２の（ｃ）は、図６−１の（ｂ）と同じ図である。図６−２の（ｄ）は、詳細表示ボタン５１２が操作された場合に、検索された図に追加的に表示される特徴量の表示例である。図６−２の（ｅ）は、詳細表示ボタン５１２が操作された場合に表示されるネットワーク構造の表示例である。ネットワーク構造には、対応する図、文書又は図と文書の重み付きノードと重み付きエッジの関係が示されている。図６−２の場合、クエリーがヒットしたノードとエッジが着色と太線の組み合わせで示される。この画面表示により、検索に使用されたノードとノード間の関係をネットワーク上で確認することができる。また、この表示は、relevance feedbackの選択の参考にすることもできる。また、最初にどのようなクエリーを入れるべきかの参考にも使用できる。図６−２の（ｆ）は、部分画像選択ボタン５１３が操作された場合に表示される画面例である。図中、太線で囲んだ部分が新たなクエリーとして使用される画像領域を示す。図６−２の（ｆ）において検索開始ボタン５１１を操作すると、インタラクティブに選択された部分画像を新たなクエリーとした検索が実行される。
【００５３】
なお、図６−１の（ａ）には、部分画像選択ボタン５１３を表していないが、最初のクエリーを入力する画面にも部分画像選択ボタン５１３を表示しても良い。また、クエリーを入力する際に、図６−１の（ａ）及び（ｂ）の中間画面としてクエリーに対する特徴量を表示した図６−２の（ｄ）や（ｅ）を表示しても良い。
【００５４】
（検索前処理と検索処理）
次に、クエリーが与えられた後のプログラムの処理を説明する。クエリー拡張がない場合、プログラムは、文書／画像中のクエリーノードの重みと、クエリーノード間の重みを利用して目的とする文書／画像を検索する。一方、クエリー拡張がある場合、プログラムは、有向グラフの場合はグラフの向きに沿ってクエリーを拡張し、無向グラフの場合にはグラフの向きとは無関係に隣接するエッジに伝搬させるようにクエリーを拡張する。これらの処理は、クエリー用の前処理１０９から処理１１１までの処理内容に対応する。
【００５５】
検索には、ノードの重みだけでなくエッジの重みも利用し、検索対象である文書／画像をスコアリングする。
【００５６】
なお、クエリーの拡張時には、元のクエリーの重みからの伝搬（遷移）も利用する。このため、拡張されたクエリーにおいては、個々のノードやエッジ自身の数値だけでなく、これらの値に伝搬（遷移）確率を乗算したノードとエッジの重みを利用する。
【００５７】
例えばクエリー拡張がない場合、各文書、擬似文書（画像）のスコアは、次式（式８）で与えられる。
【００５８】
【数８】
2011248596.tif 000010
【００５９】
これに対し、１段階のクエリー拡張がある場合、各文書、擬似文書（画像）のスコアは、次式（式９）で与えられる。なお、１段階のクエリー拡張とは、元のクエリーを構成する各要素に対してネットワーク上の接続関係を有するエッジとノードにまでクエリーの構成要素を拡張することを意味する。
【００６０】
【数９】
2011248596.tif 000011
【００６１】
式８及び式９において、Ij はノードjの重みを示し、Ejkはノードj,k間のエッジの重みを示し、freq(tk)はノードk(k番目の用語又は擬似単語)の文書及び／又は擬似文書中の出現頻度を示し、Pijはノードiとノードj間の遷移確率を示す。クエリーの拡張が２段階の場合も同様に、元のエッジとノードの各重みに元のクエリーからの遷移確率の積をとる。２段目の拡張エッジと拡張ノードには、元のクエリーから延びる２つのエッジの各遷移確率を乗算した後の値が用いられる。なお、スコアリングの方法は式９の内容に限らない。また、MinとMaxなどの取り方も適宜変えることができる。
【００６２】
なお、実際の検索処理の実行前には、クエリー用の前処理１０９において、与えられたクエリーの特徴量が検索用に抽出される。例えばクエリーが画像（文書の画像部分を含む）の場合、プログラムは、画像の解析処理を実行し、画像が有する特徴量を量子化して擬似単語に変換する（１０３）。一方、クエリーがテキスト（文書のテキスト部分を含む。）の場合、プログラムは、テキストを構成する用語を取り出す（１０２）。このように、擬似単語化された又は抽出された用語によって、検索処理用の加工済みクエリー１１０が生成される。プログラムは、この加工済みクエリー１１０又は必要に応じて拡張されたクエリーを使用して、文書及び／又は擬似文書（図）を検索する検索処理１０７を実行し、検索結果（解）を画面上に提示する。
【００６３】
（実施例１）
続いて、前述した検索システムで使用するインデックスの実施例を説明する。図８−１に、画像を含む文書のインデックス例を示す。図８−１では、文書中の画像を画像解析することにより取り出した特徴量を量子化したものをF1,…, FNで示す。また、用語をTermA, TermB,…で示す。なお、擬似単語や用語には、それぞれが画像又は図面中に出現する出現頻度を関連付けられている。文書１に複数の画像が含まれており、かつ、それら複数の画像に擬似単語F1….FNが含まれる場合、F1….FNの出現頻度は各画像の出現頻度の和で与えられる。図８−２は、各画像の特徴量を量子化した結果（擬似単語）の出現頻度をインデックス化した例を示す。図中、６０１は、画像に関連する用語・擬似単語のノードと出現頻度との関係を示す表である。また、６０２は、画像に関連する用語・擬似単語間の遷移確率と出現頻度との関係を示す表である。図８−３は、ある画像入り文書群における用語又は擬似単語の重み、ノード間の関係性の強さ、ノード間の遷移確率の関係を示したものである。図中、６０３は、用語又は擬似単語と重みとの関係を示している。６０４は、ノード間の関係性の強さと遷移確率との関係を示している。６０３と６０４の値は、遷移確率行列Ｔの固有値問題の解として又は他の手法により算出され、ストレージ上に蓄積される。
【００６４】
（実施例２）
図９に、図８−３に示す重み構造を有する画像入り文書集合のネットワーク構造を示す。ここでは、図８−２に示すインデックスを有する画像と、Term B、Term C及びTerm Dで構成されるクエリーとのスコアを算出する場合を考える。クエリー拡張がない場合、図９に示すように、Term BからTerm Cの間とTerm CからTerm Dの間にエッジが存在する。このため、画像入り文書のスコアは、例えば次式（式１０）で計算することができる。
【００６５】
【数１０】
2011248596.tif 000012
【００６６】
（実施例３）
図１０の（ａ）は、実施例２と同様の条件下で、Term Bに対してクエリーを一段階拡張した状態を示す図である。この場合、画像入り文書のスコアは、例えば次式（式１１）で計算することができる。
【００６７】
【数１１】
2011248596.tif 000013
【００６８】
（実施例４）
図１０の（ｂ）は、実施例２と同様の条件下で、Term Bに対してクエリーを２段階拡張した状態を示す図である。２段階目の拡張部分のエッジを破線で示す。この場合、画像入り文書のスコアは、例えば次式（式１２）で計算することができる。
【００６９】
【数１２】
2011248596.tif 000014
【００７０】
（実施例５）
図１１の（ａ）は、実施例２と同様の条件下で、クエリー（Term B）を図に関してだけ一段階拡張した状態を示す図である。図中、グレーが濃いノードと太いエッジが検索におけるスコアリングの計算対象となる。
【００７１】
（実施例６）
図１１の（ｂ）は、実施例２と同様の条件下で、クエリー（Term B）を用語に関してだけ一段階拡張した状態を示す図である。図中、グレーが濃いノードと太いエッジが検索におけるスコアリングの計算対象となる。
【００７２】
（実施例７）
図１２の（ａ）は、実施例２と同様の条件下で、図をクエリーとする例である。なお、図の構成擬似単語F1, F4, F8をクエリーとし、拡張なしで検索する例を示している。図中、グレーが濃いノードと太いエッジが検索におけるスコアリングの計算対象となる。
【００７３】
（実施例８）
図１２の（ｂ）は、実施例２と同様の条件下で、図をクエリーとする例である。なお、図の構成擬似単語F1, F4, F8をクエリーとする点は実施例７と同じであるが、本実施例ではクエリーを各ノードから図に関してのみ一段階拡張した例を示している。図中、グレーが濃いノードと太いエッジが検索におけるスコアリングの計算対象となる。
【００７４】
（実施例９）
図１３の（ａ）は、実施例２と同様の条件下で、クエリーが「図＋説明文」で与えられる場合、具体的にはクエリーがterm AとF1, F3, F8の組み合わせで与えられる場合において、クエリーを拡張しないときの例である。図中、グレーが濃いノードと太いエッジが検索におけるスコアリングの計算対象となる。
【００７５】
（実施例１０）
図１３の（ｂ）は、実施例２と同様の条件下で、クエリーが「図＋説明文」で与えられる場合、具体的にはクエリーがterm AとF1, F3, F8で与えられる場合において、クエリーを一段階拡張するときの例である。図中、グレーが濃いノードと太いエッジが検索におけるスコアリングの計算対象となる。
【００７６】
（実施例１１）
図１４の（ａ）及び（ｂ）は、ある図に含まれる特徴量と特徴量間の関係を黒くハイライト表示した例を示す。エッジが太い部分は、図１４の（ａ）と（ｂ）とで共通する部分である。このように、サブグラフの一致度をみることにより、部分的な類似検索も可能である。検索の際には、このようなサブグラフをクエリーに用いることもできる。
【００７７】
また、このような図だけでの計算の場合には、最初に遷移確率行列を計算する際に元となるスコアSij の計算において、一定の距離以内に存在する擬似単語間ijの関係性のみを計算対象としても良い。すなわち、一定の距離を超えるノード（擬似単語）間にエッジは張らないようにしても良い。
【００７８】
（実施例１２）
図１５の（ａ）及び（ｂ）は、画像毎に式３の固有値問題を解き、ネットワークを生成した例を示している。図１５の（ａ）及び（ｂ）は、全ての画像を解析し、図５に示すようにノードとエッジの重みをインデックス化することで生成できる。例えばクエリーが図１５の（ａ）の全体で与えられるものとする。この場合、（ａ）と（ｂ）の共通部分（図中、グレーが濃いノードと太いエッジの部分）が（ｂ）を検索対象（処理対象）とする場合におけるスコアリングの計算対象となる。
【００７９】
（実施例１３）
図１６は、実施例３と同様の条件で、クエリー（term B）を一段階拡張した例を示す。図１６のネットワークは無向グラフである。このため、エッジの向きは関係なく、term Bに隣接する全てのエッジに伝搬してクエリーを拡張する。図中、グレーが濃いノードと太いエッジが検索におけるスコアリングの計算対象となる。
【００８０】
（まとめ）
以上説明したように、形態例に係る検索システム及び方法の場合には、ノードの重み（重要度）とエッジの強さ（ノード間の関係の強さ）を組み合わせて検索動作を実行する。このため、用語や擬似単語の独立した重要度だけで画像を検索する場合に比して、検索される画像の類似度を高めることができる。
【００８１】
また、クエリーを拡張する場合には、元のクエリーを構成する用語や擬似単語との派生関係に基づいて拡張先のノードやエッジの重みを再計算することにより、クエリーを構成するノードとエッジのネットワーク構造を正確に反映させた検索動作が可能になる。
【００８２】
また、遷移確率行列を固有値問題として解いたり、ノードとエッジの関係を漸化式として解くことにより、用語・擬似単語間の重要度を共通の条件にて計算できる。このため、相対的な重みを使用する場合に比してノードやエッジの重みの精度を従来技術に比して高めることができる。
【符号の説明】
【００８３】
10       検索システム
20       ストレージ
30       計算機
100      前処理
101      画像入り文書ＤＢ
107      検索処理
108      クエリーの入力処理
109      クエリー用の前処理
110      加工済みクエリー
201      元の画像（画像A）
202      画像Aの特徴点を認識した結果を示す画像
203      画像Aの特徴点を計算した結果を示す例
204      画像Aの特徴点を量子化した後の結果を示す例
205      量子化した特徴点を使って画像Aを表した例
300      画像のインデックス
301      用語の出現頻度のインデックス
302      画像の量子化された特徴量の出現頻度のインデックス
303      文書のインデックス
304      用語の頻度のインデックス
305      画像の量子化された特徴量の出現頻度のインデックス
401      用語の頻度のインデックス
402      用語の関係性の強さのインデックス
501      検索システムの画面
502      テキストクエリーの入力欄
503      図クエリーの入力欄
504      文書クエリーの入力欄
505      検索対象選択欄
506      検索開始ボタン
506Ａ    アップロードボタン
507      検索結果表示画面
508      選択ボタン
509      図の表示欄
510      テキストの表示欄
511      検索開始ボタン
512      詳細表示ボタン
513      部分画像選択ボタン
521      ノード
522      遷移確率
523      重み付きノード
524      関係性の強さを示すエッジ
【図１】
2011248596.tif 000015
【図２】
2011248596.tif 000016
【図３】
2011248596.tif 000017
【図４】
2011248596.tif 000018
【図５】
2011248596.tif 000019
【図６−１】
2011248596.tif 000020
【図６−２】
2011248596.tif 000021
【図７】
2011248596.tif 000022
【図８−１】
2011248596.tif 000023
【図８−２】
2011248596.tif 000024
【図８−３】
2011248596.tif 000025
【図９】
2011248596.tif 000026
【図１０】
2011248596.tif 000027
【図１１】
2011248596.tif 000028
【図１２】
2011248596.tif 000029
【図１３】
2011248596.tif 000030
【図１４】
2011248596.tif 000031
【図１５】
2011248596.tif 000032
【図１６】
2011248596.tif 000033