(57)【特許請求の範囲】
【請求項１】
ツリー構造を用いて分類された画像データに対応するノード間の距離を計算するためのノード間距離計算部と、ノード間での画像類似度に基づく類似度距離を算出する類似度計算部と、合計部とを備えており、
前記ノード間距離計算部は、
距離計算対象となる二つの対象ノードについて、トップのノードから前記対象ノードまでのそれぞれのカテゴリパスを特定するカテゴリパス特定部と、
前記カテゴリパスどうしの間における非共通ノードを特定するノード特定部と、
前記ツリー構造における階層が下がるほど小さくなる重みを、最も低い階層に達するカテゴリパスに属する前記非共通ノードについて算出する重み算出部と、
前記非共通ノードについて算出された前記重みを加算することにより、ノード間距離を算出する加算部と
を備えており、
前記合計部は、前記ノード間距離計算部により算出されたノード間距離と、前記類似度計算部により算出された類似度距離とを合計することにより、両方の距離を統合した統合距離を算出する構成となっている
ことを特徴とする、統合距離計算装置。
【請求項２】
前記重み算出部は、下記式に従って前記重みを算出する構成となっている、請求項１に記載の統合距離計算装置：
１／ａ（ｋ−１）
ここで、
ａ：１より大きい任意の実数；
ｋ：トップのノードから、重み付与の対象であるノードまでの階層の深さを示す自然数；
である。
【請求項３】
前記ａは２である、請求項２に記載の統合距離計算装置。
【請求項４】
前記ノード特定部は、前記カテゴリパスどうしの間における共通ノードをさらに特定する構成となっている、請求項１〜３のいずれか１項に記載の統合距離計算装置。
【請求項５】
前記重み算出部は、最も低い階層に達するカテゴリパスを特定した後に、当該最も低い階層に達するカテゴリパスに属する前記非共通ノードについて、前記重みを算出する構成となっている
請求項１〜４のいずれか１項に記載の統合距離計算装置。
【請求項６】
ツリー構造を用いて分類された画像データに対応するノード間の距離を計算するためのノード間距離計算を利用した装置における統合距離計算方法であって、
距離計算対象となる二つの対象ノードについて、トップのノードから前記対象ノードまでのそれぞれのカテゴリパスを特定するカテゴリパス特定ステップと、
前記カテゴリパスどうしの間における非共通ノードを特定するノード特定ステップと、
前記ツリー構造における階層が下がるほど小さくなる重みを、最も低い階層に達するカテゴリパスに属する前記非共通ノードについて算出する重み算出ステップと、
前記非共通ノードについて算出された前記重みを加算することにより、ノード間距離を算出する加算ステップと
ノード間での画像類似度に基づく類似度距離を算出する類似度計算ステップと、
前記加算ステップにおいて算出されたノード間距離と、前記類似度計算ステップにおいて算出された類似度距離とを合計することにより、両方の距離を統合した統合距離を算出する合計ステップと
を備えることを特徴とする、統合距離計算方法。
【請求項７】
請求項６に記載の各ステップをコンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分類ツリーにより分類された画像データに対応するノード間の距離を算出するための技術に関するものである。
【背景技術】
【０００２】
例えば、ウエブサイト上で商品検索を行うためのバックグラウンド動作として、商品を特定するための画像データを、分類ツリーを用いて分類しておくことがある。より具体的には、商品を、その属性（例えば男性用、女性用、大人用、子供用、夏向き、冬向きなど）によって、ツリー構造で分類することができる。そして、商品検索のための分類情報を検索システムが受け取ると、検索システムは、この分類情報を分類ツリーに適用して、ユーザの意図に近い商品を検索することができる。
【０００３】
一方、検索クエリとして、分類情報付きのクエリ画像が用いられることがある。これを商品検索に用いる場合には、分類情報を用いて分類ツリーで検索をするだけでなく、クエリ画像と登録画像（いわゆる学習画像）との、画像特徴量による類似度を用いた検索を行うことができる。例えば被服を検索する場合、被服の分類情報とクエリ画像（例えば被服の写真）とを用いて検索することができる。
【０００４】
しかしながら、このように、分類ツリーによる検索と画像特徴量による検索という２種類の検索を個別に行うのでは、検索時間が長くなってしまうという問題がある。さらに、二つの検索による検索結果を適切に統合する方法がなく、検索精度の劣化が危惧されるという問題もある。
【０００５】
なお、分類ツリーにおいて分類されているノード（登録画像に相当）間の距離を、ユークリッド距離を用いて算出し、この距離と、画像特徴量による距離とを融合させることも、一応は考えられる。しかしながら、このように算出されたユークリッド距離は、分類ツリーにおける分類の特徴を反映しないため、検索精度の向上には寄与しにくいと考えられる。
【０００６】
下記特許文献１〜３には、分類ツリーにおけるノード間の距離を得るための手法が記載されている。しかしながら、これらはいずれも、画像特徴量を用いて得られる、画像データ間の距離との融合を意図したものではない。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平６−３１８２２３号公報
【特許文献２】特開２００４−１７８３４３号公報
【特許文献３】特開２００９−２５８５８３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、前記した状況に鑑みてなされたものである。本発明の主な目的は、分類ツリーにより分類されている画像データ間の距離を、画像特徴量による画像間の距離との融合に適するように算出することが可能な装置又は方法を提供することである。
【課題を解決するための手段】
【０００９】
本発明は、以下のいずれかの項目に記載の構成とされている。
【００１０】
（項目１）
ツリー構造を用いて分類された画像データに対応するノード間の距離を計算するためのノード間距離計算装置であって、
距離計算対象となる二つの対象ノードについて、トップのノードから前記対象ノードまでのそれぞれのカテゴリパスを特定するカテゴリパス特定部と、
前記カテゴリパスどうしの間における非共通ノードを特定するノード特定部と、
前記ツリー構造における階層が下がるほど小さくなる重みを、最も低い階層に達するカテゴリパスに属する前記非共通ノードについて算出する重み算出部と、
前記非共通ノードについて算出された前記重みを加算することにより、ノード間距離を算出する加算部と
を備えることを特徴とする、ノード間距離計算装置。
【００１１】
（項目２）
前記重み算出部は、下記式に従って前記重みを算出する構成となっている、項目１に記載のノード間距離計算装置：
１／ａ（ｋ−１）
ここで、
ａ：１より大きい任意の実数；
ｋ：トップのノードから、重み付与の対象であるノードまでの階層の深さを示す自然数；
である。
【００１２】
（項目３）
前記ａは２である、項目２に記載のノード間距離計算装置。
【００１３】
（項目４）
前記ノード特定部は、前記カテゴリパスどうしの間における共通ノードをさらに特定する構成となっている、項目１〜３のいずれか１項に記載のノード間距離計算装置。
【００１４】
（項目５）
項目１〜４のいずれか１項に記載のノード間距離計算装置と、ノード間での画像類似度に基づく類似度距離を算出する類似度計算部と、合計部とを備えており、
前記合計部は、前記ノード間距離計算装置により算出されたノード間距離と、前記類似度計算部により算出された類似度距離とを合計することにより、両方の距離を統合した統合距離を算出する構成となっている
統合距離計算装置。
【００１５】
（項目６）
ツリー構造を用いて分類された画像データに対応するノード間の距離を計算するためのノード間距離計算方法であって、
距離計算対象となる二つの対象ノードについて、トップのノードから前記対象ノードまでのそれぞれのカテゴリパスを特定するカテゴリパス特定ステップと、
前記カテゴリパスどうしの間における非共通ノードを特定するノード特定ステップと、
前記ツリー構造における階層が下がるほど小さくなる重みを、最も低い階層に達するカテゴリパスに属する前記非共通ノードについて算出する重み算出ステップと、
前記非共通ノードについて算出された前記重みを加算することにより、ノード間距離を算出する加算ステップと
を備えることを特徴とする、ノード間距離計算方法。
【００１６】
（項目７）
項目６に記載の各ステップをコンピュータに実行させるためのコンピュータプログラム。
【００１７】
このコンピュータプログラムは、適宜な記録媒体（例えばＣＤ−ＲＯＭやＤＶＤディスクのような光学的な記録媒体、ハードディスクやフレキシブルディスクのような磁気的記録媒体、あるいはＭＯディスクのような光磁気記録媒体）に格納することができる。このコンピュータプログラムは、インターネットなどの通信回線を介して伝送されることができる。
【発明の効果】
【００１８】
本発明によれば、分類ツリーにより分類されている画像データ間の距離を、画像特徴量による画像間の距離との融合に適するように算出することが可能となる。
【図面の簡単な説明】
【００１９】
【図１】本発明の一実施形態の検索装置を利用した検索システムの全体的なブロック図である。
【図２】ノード間距離の計算に用いる分類ツリーの一例を示す説明図である。
【図３】検索システム全体の動作の概略を説明するためのフローチャートである。
【図４】登録画像による学習方法の一例を説明するためのフローチャートである。
【図５】統合距離の計算方法の一例を説明するためのフローチャートである。
【図６】ノード間距離の計算方法の一例を説明するためのフローチャートである。
【図７】検索クエリに基づく検索方法の一例を説明するためのフローチャートである。
【発明を実施するための形態】
【００２０】
（本実施形態の構成）
本発明の一実施形態におけるノード間距離計算装置を含む検索システムの一例を、図１を参照しながら説明する。
【００２１】
本実施形態の検索システムは、登録画像を用いて学習を行う学習装置１と、クエリ画像を用いて検索を行う検索装置２と、画像間（つまりノード間）の距離計算を行う統合距離計算部３とを備えている。
【００２２】
（学習装置）
学習装置１は、登録画像取得部１１と、特徴量抽出部１２と、インデックス生成部１３とを備えている。
【００２３】
登録画像取得部１１は、登録されるべき画像（つまり学習画像）と、それが属するべきカテゴリの情報（分類ツリーにおけるノード）とを取得する構成となっている。これらの画像及びカテゴリ情報は、適宜なデータベースあるいはネットワーク上から取得できるが、取得経路に制約はない。また、画像が属する色空間についても、特に制約はない。分類ツリーの一例を図２に示す。分類ツリーの情報は、例えば、統合距離計算部３に保存されているが、必要に応じて参照可能であれば、どこに保存されていてもよい。また、分類ツリーとしては、上位の階層から下位の階層に辿ることができるものであればよい。
【００２４】
特徴量抽出部１２は、登録画像取得部１１で取得した画像について、その画像特徴量を抽出する構成となっている。画像特徴量は、通常、多次元のベクトルとして記述される。ベクトルを用いた画像特徴量の記述方法は良く知られているので、詳しい説明は省略する。
【００２５】
本実施形態における特徴量抽出部１２は、抽出された画像特徴量とカテゴリ情報とを、当該画像に付された画像ＩＤに対応付けて、画像ＤＢ４に送る。画像ＤＢ４では、統合距離計算部３のカテゴリパス特定部３１１（後述）により特定されるカテゴリパスと共に、画像特徴量とカテゴリパスとを格納する。画像ＤＢ４に格納されるデータの一例を、図１において符号４１で示す。さらに、特徴量抽出部１２は、画像ＩＤと画像特徴量とカテゴリ情報とを、インデックス生成部１３に送る。
【００２６】
インデックス生成部１３は、特徴量抽出部１２から送られた画像特徴量とカテゴリ情報とを統合距離計算部３に送り、さらに、統合距離計算部３で算出された統合距離を取得するようになっている。そして、インデックス生成部１３は、得られた統合距離を用いて、検索用の距離空間インデックス（例えば、vp-treeやM-Treeなど）を生成するようになっている。距離空間インデックスの生成方法としては、統合距離を通常の距離とみなせば、既存の手法を用いることができるので、詳しい説明は省略する。なお、この明細書においては、距離空間インデックスを単にインデックスと称することがある。
【００２７】
インデックス生成部１３は、生成されたインデックスに従い、リンク元の画像ＩＤと、リンク先の画像ＩＤと、それらの間の統合距離とを、インデックスＤＢ５に格納する。インデックスＤＢ５に格納されるデータの一例を、図１において符号５１で示す。
【００２８】
（検索装置）
本実施形態の検索装置２は、検索クエリ取得部２１と、特徴量抽出部２２と、検索部２３と、検索結果出力部２４とを備えている。
【００２９】
検索クエリ取得部２１は、クエリとなる画像と、その画像が属するカテゴリの情報とを取得する構成となっている。クエリとなる画像の取得方法としては、特に制約されないが、例えば、
・システム側に予め登録されているクエリ画像をユーザに提示し、ユーザが指定する方法；
・ユーザが用意した画像をシステム側にアップロードする方法
が考えられる。また、画像が属するカテゴリの取得方法としては、特に制約されないが、例えば、
・システム側に予めクエリ画像が登録されている場合には、クエリ画像に対応して、カテゴリ情報を付随させておく方法；
・ユーザがクエリ画像を準備する場合には、ユーザによりカテゴリを指定させるか、あるいは、所定のアルゴリズムによって自動的にカテゴリを特定する方法
が考えられる。
【００３０】
特徴量抽出部２２は、学習装置１の特徴量抽出部１２と同様に、クエリ画像について、その画像特徴量を抽出する処理を行う構成となっている。特徴量抽出部２２の具体的な処理は、学習装置１の特徴量抽出部１２と基本的に同様なので、詳しい説明は省略する。また、特徴量抽出部２２として独立の機能要素を設けることは必須ではなく、特徴量抽出部２２と特徴量抽出部１２とを兼用することは可能である。例えば、一つのプログラムモジュールを両方の用途に利用することができる。
【００３１】
検索部２３は、特徴量抽出部２２から送られた画像特徴量とカテゴリ情報とを統合距離計算部３に送り、さらに、統合距離計算部３で算出された統合距離を取得するようになっている。そして、検索部２３は、統合距離を用いて、インデックスＤＢ５を検索し、検索結果に対応する画像を検索ＤＢ４から得て、それを検索結果出力部２４に送る構成となっている。インデックスＤＢを用いた検索手法自体としては、既存の手法を用いることができるので、これについての詳しい説明は省略する。
【００３２】
検索結果出力部２４は、検索部２３において得られた検索結果を出力する構成となっている。出力先としては、例えば、検索を行うユーザであるが、他に、検索結果を利用するシステムや、何らかのデータベースに出力することも可能である。ユーザに検索結果を出力する場合は、検索結果出力部２４においてＨＴＭＬ文書を生成して、ユーザ端末上のブラウザによって表示させるという手段も可能である。
【００３３】
（統合距離計算部）
統合距離計算部３は、ノード間距離計算部３１と、類似度計算部３２と、合計部３３とを備えている。統合距離計算部３は、本発明の統合距離計算装置の一実施形態に相当する。
【００３４】
ノード間距離計算部３１は、ツリー構造を用いて分類された画像データに対応するノード間の距離を計算するものであって、本発明におけるノード間距離計算装置の一実施形態に相当する。本実施形態のノード間距離計算部３１は、カテゴリパス特定部３１１と、ノード特定部３１２と、重み算出部３１３と、加算部３１４とを備えている。
【００３５】
カテゴリパス特定部３１１は、距離計算対象となる二つの対象ノードについて、トップのノードから対象ノードまでのそれぞれのカテゴリパスを特定する構成となっている。ここで、カテゴリパスとは、トップノードから対象ノードまでの経路を特定するための情報である。すなわち、カテゴリパス特定部３１１は、画像（学習画像又はクエリ画像）が属するカテゴリ（ノード）の情報と、図２に例示する分類ツリーの情報とを用いて、トップノードから、当該画像に対応するノードまでのカテゴリパスを抽出する。例えば、図２の分類ツリーにおいて、ノードＪに対応するカテゴリパスは、Ａ−Ｂ−Ｄ−Ｊとなる。したがって、このパスは、以下のベクトルデータとして記述できる。
【００３６】
｛Ａ，Ｂ，Ｄ，Ｊ}
【００３７】
一般に、任意のノードへのカテゴリパスは、以下のベクトルＩで表現できる。
【００３８】
ベクトルＩ＝{ｉ１，ｉ２，ｉ３，ｉ４，ｉ５}
【００３９】
この例では、ベクトルの要素数が５となっているが、ベクトルの要素数は、パスを構成するノードの数に対応して変化する。なお、カテゴリパス特定部３１１は、三つ以上のノードについて並行してカテゴリパスを特定する構成であってもよい。
【００４０】
ノード特定部３１２は、カテゴリパスどうしの間における非共通ノードを特定する構成となっている。さらに、本実施形態では、カテゴリパスどうしの間における共通ノードもノード特定部３１２が特定する構成となっている。
【００４１】
重み算出部３１３は、図２に示すようなツリー構造における階層が下がるほど小さくなる重みを、最も低い階層に達するカテゴリパスに属する非共通ノードについて算出する構成となっている。
【００４２】
本実施形態の重み算出部３１３は、下記式に従って重みを算出する構成となっている：
【００４３】
１／ａ（ｋ−１）
【００４４】
ここで、
ａ：１より大きい任意の実数；
ｋ：トップのノードから、重み付与の対象であるノードまでの階層の深さを示す自然数（すなわち、カテゴリパスを構成するベクトルにおける要素の順番）；
である。
【００４５】
より具体的には、前記ａは例えば２である。
【００４６】
加算部３１４は、非共通ノードについて算出された重みを加算することにより、ノード間距離を算出する構成となっている。
【００４７】
本実施形態のノード間距離計算部３１におけるノード間距離は、より具体的に説明すれば、下記式によって算出できる。
【００４８】
0005450715.tif 000002
【００４９】
ただし、
Ｄ：ノード間距離；
ｎ：最長のカテゴリパスを構成するベクトルにおける要素の個数（つまりベクトルの次数）である。
【００５０】
また、ｆ（ik,jk）は、関数であり、本例では以下の値をとる。
ik=jkのとき、ｆ（ik,jk）=0
ik≠jkのとき、ｆ（ik,jk）=1
【００５１】
前記式（１）に実質的に相当する処理を実行することは、すなわち、本実施形態における重み算出部３１３及び加算部３１４の構成と備えたこととなる。前記（１）式において、ik=jkのとき、ｆ（ik,jk）=0とすることは、共通ノードにおける重みの影響を排除することに相当する。また、ik≠jkのとき、ｆ（ik,jk）=1とすることは、非共通ノードにおける重みを取得することに相当する。したがって、ik≠jkのとき、ｆ（ik,jk）の値を、１より大きい実数とすることは可能である。ノード間距離計算部３１における詳しい動作例は後述する。
【００５２】
類似度計算部３２は、ノード間での画像類似度に基づく類似度距離を算出する構成となっている。このような類似度距離の算出手法としては既存のものを用いることができるので、詳細についての説明を省略する。
【００５３】
合計部３３は、ノード間距離計算部３１により算出されたノード間距離と、類似度計算部３２により算出された類似度距離とを合計することにより、両方の距離を統合した統合距離を算出する構成となっている。算出に際して、どちらかの距離に重みを付すことは可能である。
【００５４】
（本実施形態の動作）
以下、本実施形態の検索システムの動作を、図３〜図７をさらに参照しながら説明する。
【００５５】
（検索システム全体の動作）
まず、検索システム全体としての動作を図３に基づいて説明し、その後、各処理の詳細を説明する。
【００５６】
（図３のＳＡ−１）
まず、学習装置１が、登録画像（つまり学習画像）を用いて、学習を行い、検索用のインデックス（つまりインデックスＤＢ５）を生成する。また、学習装置１は、画像ＤＢ４に画像ＩＤと画像特徴量とを格納する。
【００５７】
（図３のＳＡ−２）
ついで、検索装置２が、検索クエリ（つまり検索用画像）とインデックスＤＢ５とを用いて、既定の距離内にある画像を検索する。
【００５８】
（図３のＳＡ−３）
ついで、得られた検索結果を、検索装置２の検索結果出力部２４により出力する。
【００５９】
（学習動作）
次に、図４をさらに参照して、学習動作の詳細を説明する。
【００６０】
（図４のステップＳＢ−１）
まず、登録画像取得部１１が、登録画像と、それが属するカテゴリ情報とを取得する。登録画像とカテゴリ情報を取得する経路は特に制約されないが、例えば、適宜なデータベースから、あるいは使用者の入力により取得することができる。
【００６１】
（図４のステップＳＢ−２）
ついで、特徴量抽出部１２が、登録画像における特徴量（つまり画像特徴量）を取得する。画像特徴量の取得方法としては、既存の手法を利用できるので、詳しい説明を省略する。
【００６２】
（図４のステップＳＢ−３）
ついで、特徴量抽出部１２は、取得した画像特徴量を、画像ＤＢ４に格納する。画像ＤＢ４では、画像を特定する画像ＩＤに関連付けて、画像特徴量を登録する。さらに、画像ＤＢ４では、後述する手順で得られるカテゴリパスも、画像ＩＤに関連付けて登録する。
【００６３】
（図４のステップＳＢ−４）
さらに、特徴量抽出部１２は、インデックス生成部１３に画像特徴量と所属カテゴリ情報とを送る。インデックス生成部１３は、これらの情報を、統合距離計算のために、統合距離計算部３に送る。
【００６４】
（図４のステップＳＢ−５）
統合距離計算部３では、インデックス生成部１３から受け取った画像特徴量と所属カテゴリ情報とを用いて、統合距離を計算する。この計算の方法については、図５及び図６を用いて後述する。
【００６５】
（図４のステップＳＢ−６及びＳＢ−７）
ついで、インデックス生成部１３では、統合距離計算部３から受け取った統合距離を用いて、検索のためのインデックスを生成して、インデックスＤＢに格納する。インデックス生成の手法自体は、既述したように、既存手法を利用できるので、これについての詳しい説明は省略する。
【００６６】
（統合距離の計算方法）
つぎに、統合距離計算部３における統合距離の計算手順を、図５に基づいて説明する。
【００６７】
（図５のステップＳＣ−１）
まず、距離の比較対象となる二つの画像データ（つまり、分類ツリーにおけるノード）を特定する。この特定は、統合距離計算部３での処理を要求するインデックス生成部１３や検索部２３において行われており、統合距離計算部３は、その特定に従って動作する。例えば、検索クエリに基づく検索の場合（検索については後述する）であれば、検索クエリである画像と、画像ＤＢ４に格納されている学習画像との間での距離計算が行われる。ただし、何らかのアルゴリズムに従って、統合距離計算部３において、距離を測定されるべき二つの画像データを特定することは可能である。
【００６８】
（図５のステップＳＣ−２）
次に、統合距離計算部３の類似度計算部３２は、受け取った画像特徴量を用いて、画像の類似度距離（類似度に基づく距離）を計算する。この類似度距離の計算手法としては、既述の通り、既存のものを利用できるので、これについての詳しい説明は省略する。
【００６９】
（図５のステップＳＣ−３）
一方、ノード間距離計算部３１は、インデックス生成部１３から受け取った所属カテゴリの情報を用いて、図２の分類ツリーにおけるカテゴリパスを特定し、ノード間距離を算出する。ノード間距離の算出の詳細については後述する。
【００７０】
（図５のステップＳＣ−４）
ついで、合計部３３は、得られた類似度距離とノード間距離とを統合することにより、統合距離を算出する。類似度距離とノード間距離との統合において、どちらかあるいは両方に適宜な重みを付与することができる。
【００７１】
本実施形態の手法で算出されたノード間距離は、距離の公理を満たしているので、ノード間距離と類似度距離とを統合して得られる統合距離を用いて、適切な検索が可能となる。この点についてはさらに後述する。
【００７２】
（ノード間距離の計算方法）
次に、図６を参照しながら、ノード間距離の計算方法を詳しく説明する。
【００７３】
（図６のステップＳＤ−１）
ノード間距離計算部３１のカテゴリパス特定部３１１は、インデックス生成部１３あるいは検索部２３から受け取った所属カテゴリの情報を用いて、図２のような分類ツリーにおけるカテゴリパスを特定する。既述のように、カテゴリパスとは、トップノードから対象ノードまでの経路を特定するための情報である。例えば、図２において、ノードＬまでのカテゴリパスは、（Ａ，Ｂ，Ｆ，Ｌ）となる。カテゴリパスの特定は、距離測定の対象となる各画像データ（つまりノード）について行われる。カテゴリパス特定部３１１で生成されるカテゴリパスは、学習時においては、画像ＤＢ４に送られて、画像ＩＤと関連付けて登録される。また、検索時には、カテゴリパスは、検索部２３に送られる。
【００７４】
（図６のステップＳＤ−２）
ついで、ノード特定部３１２は、特定された二つのカテゴリパスにおいて、共通するノード（共通ノード）と共通しないノード（非共通ノード）とを特定する。
【００７５】
（図６のステップＳＤ−３）
ついで、重み算出部３１３は、カテゴリパス中の各ノードについて、重みを算出する。重みは、階層が低くなるほど小さい値とされる。
【００７６】
（図６のステップＳＤ−４）
ついで、加算部３１４は、最も低い階層に達するカテゴリパスにおける非共通ノードについて、それらに付された重みを加算する。重みの算出及び加算についての具体的な算出例は、前記式（１）に示した通りである。
【００７７】
（図６のステップＳＤ−５）
重みの加算により、ノード間距離を得ることができる。得られたノード間距離は、距離の公理を満たすものとされる。この点についてはさらに後述する。
【００７８】
（具体的な計算例）
前記した式（１）を用いた具体的なノード間距離の計算方法を、以下において説明する。なお、図２には、各ノードにおける重みを付記しておいた。
【００７９】
・ノードＤとノードＥとの間の距離：
ノードＤのカテゴリパス：（Ａ，Ｂ，Ｄ）
ノードＥのカテゴリパス：（Ａ，Ｂ，Ｅ）
共通ノード：（Ａ，Ｂ）
最も下層に達する非共通ノード：（Ｄ）又は（Ｅ）
ノード間距離：０．２５
【００８０】
・ノードＢとＣとの間の距離
ノードＢのカテゴリパス：（Ａ，Ｂ）
ノードＣのカテゴリパス：（Ａ，Ｃ）
共通ノード：（Ａ）
最も下層に達する非共通ノード：（Ｂ）又は（Ｃ）
ノード間距離：０．５
【００８１】
・ノードＬとＣとの間の距離
ノードＬのカテゴリパス：（Ａ，Ｂ，Ｆ，Ｌ）
ノードＣのカテゴリパス：（Ａ，Ｃ）
共通ノード：（Ａ）
最も下層に達する非共通ノード：（Ｂ，Ｆ，Ｌ）
ノード間距離：０．８７５
【００８２】
同様に計算すると、
ノードＤ−Ｈ間：０．７５
ノードＫ−Ｌ間：０．１２５
ノードＩ−Ｌ間：０．３７５
という距離になる。
【００８３】
（検索クエリに基づく検索の手順について）
ついで、図７を参照して、検索クエリに基づく検索の手順を説明する。
【００８４】
（図７のステップＳＥ−１）
まず、検索装置２の検索クエリ取得部２１が、検索クエリとなる画像と、この画像が属する所属カテゴリの情報とを取得する。
【００８５】
（図７のステップＳＥ−２）
ついで、特徴量抽出部２２は、検索クエリ画像における画像特徴量を抽出する。
【００８６】
（図７のステップＳＥ−３）
ついで、検索部２３は、検索クエリ画像と所属カテゴリ情報とを統合距離計算部３に送り、画像ＤＢ４中の学習画像（登録画像）との統合距離を取得する。統合距離の計算方法は、前記と同様なので、詳しい説明は省略する。すなわち、統合距離計算部３は、検索クエリのカテゴリパスを、カテゴリパス特定部３１１により取得できる。
【００８７】
（図７のステップＳＥ−４）
ついで、検索部２３は、得られた統合距離を用いて、インデックスＤＢ５を検索し、得られた検索結果に対応する画像を、画像ＤＢ４から取得することができる。インデックスを用いた検索手法は、従来と同様でよいので、詳しい説明を省略する。
【００８８】
（図７のステップＳＥ−５）
ついで、検索結果出力部２４は、検索部２３によって得られた検索結果を出力する。出力先は、例えば、ユーザ端末や、所定の記録媒体であるが、特に制約されない。また、出力形態としては、例えば、得られた画像そのものを出力することや、その画像へのリンクを出力することが考えられるが、何らかの用途に利用できるのであれば、出力形態は特に制約されない。
【００８９】
本実施形態によれば、分類ツリーにより分類されている画像データ間の距離（つまりノード間距離）を、画像特徴量による画像間の距離との融合に適するように、つまり、後述の距離の公理を満たすように算出することが可能になるという利点がある。
【００９０】
ノード間距離が距離の公理を満たすことにより、以下の利点を得ることができる。
・従来のノード間距離は、距離の公理を満たさないので、距離空間インデックスを用いた高速な検索が困難である。本実施形態のノード間距離は、距離の公理を満たすので、画像特徴量の検索と同様に、距離空間インデックスを用いて高速な検索が可能となる。
・分類カテゴリによる検索と、画像類似度による検索という、２種類の検索を行うと、高速化の支障となるだけでなく、得られた結果の精度が劣化するおそれがある。これに対して、本実施形態では、画像特徴量による類似度距離と、カテゴリパスによるノード間距離との両方を、単一の距離空間に統合化できる。すなわち、本実施形態では、統合距離を用いた単一の距離空間インデックスを生成して、それを用いて検索を行うことが可能となる。このため、本実施形態によれば、画像特徴量とカテゴリ情報の両者を利用して、高速かつ高精度の類似画像検索が可能になる。
【００９１】
（ノード間距離が距離の公理を満たすことについて）
以下、前記したノード間距離が距離の公理を満たすことについて、補足して説明する。前記した式（１）で得られる距離Ｄが、距離の定義のうち以下の三つを満足することは明白である。
【００９２】
D≧0（非負性）；
i=jのときD=0（非退化性）；
D(i,j)=D(j,i)（対称性）
【００９３】
次に、距離Ｄが以下の三角不等式を満足することを示す。
D(x,y)+D(y,z)≧D(x,z) ・・・(2)
【００９４】
この式（２）から、以下の式を得られる。
D(x,y)+D(y,z)-D(x,z)≧0 ・・・(3)
【００９５】
この式（３）が成り立つことを証明する。
【００９６】
式（１）から、
【００９７】
0005450715.tif 000003
【００９８】
となる。また、
【００９９】
0005450715.tif 000004
【０１００】
あるから、
【０１０１】
0005450715.tif 000005
【０１０２】
である。
【０１０３】
この式の
【０１０４】
0005450715.tif 000006
【０１０５】
の項について次のように書き換える。
【０１０６】
0005450715.tif 000007
【０１０７】
この式（５）において、fは0又は1なので、この式が成り立たないのは、f(xk, zk)が１のときしかない。したがって、
【０１０８】
xk≠zk        （６）
【０１０９】
となる。しかし、
【０１１０】
0005450715.tif 000008
【０１１１】
になるには、f(xk, yk)、f(yk, zk)が共に0のときのみである。これらが共に0になるのは、
【０１１２】
xk=yk=zk
【０１１３】
のときであり、これは前記の式（６）に反する。したがって、式（５）が成り立つ。
【０１１４】
式（５）が成り立つので式（４）は
【０１１５】
0005450715.tif 000009
【０１１６】
である。したがって、式（３）が成り立つので式（２）を常に満たす。
【０１１７】
以上より、式（１）により得られる距離Ｄは距離の公理を満たす。以上の説明は、式（１）における「２」を、２以外の正の実数としても成り立つ。ただし、「２」とすることにより、距離の最大値がほぼ１になることが保証されるので、正規化が簡易となるという利点がある。
【０１１８】
前記した各実施形態の動作は、コンピュータに適宜のコンピュータソフトウエアを組み込むことにより実施することができる。
【０１１９】
なお、本発明の内容は、前記実施形態に限定されるものではない。本発明は、特許請求の範囲に記載された範囲内において、具体的な構成に対して種々の変更を加えうるものである。
【０１２０】
例えば、前記した各構成要素は、機能ブロックとして存在していればよく、独立したハードウエアとして存在しなくても良い。また、実装方法としては、ハードウエアを用いてもコンピュータソフトウエアを用いても良い。さらに、本発明における一つの機能要素が複数の機能要素の集合によって実現されても良く、本発明における複数の機能要素が一つの機能要素により実現されても良い。
【０１２１】
また、機能要素は、物理的に離間した位置に配置されていてもよい。この場合、機能要素どうしがネットワークにより接続されていても良い。グリッドコンピューティング又はクラウドコンピューティングにより機能を実現し、あるいは機能要素を構成することも可能である。
【０１２２】
また、前記の実施形態では、統合距離計算部３のカテゴリパス特定部３１１が、必要に応じてカテゴリパスを特定する構成とした。しかしながら、カテゴリパスも特徴量なので、特徴量抽出部１２あるいは２２において、画像特徴量とカテゴリパスとを共に抽出して、その後の処理に用いる構成とすることも可能である。また、カテゴリパス抽出用の一つのモジュールを、特徴量抽出部１２及び２２において共用することも可能である。特徴量抽出部１２あるいは２２においてカテゴリパスを抽出する場合の処理手順は、前記から理解可能なので、それについての詳しい説明を省略する。
【符号の説明】
【０１２３】
１  学習装置
１１  登録画像取得部
１２  特徴量抽出部
１３  インデックス生成部
２  検索装置
２１  検索クエリ取得部
２２  特徴量抽出部
２３  検索部
２４  検索結果出力部
３  統合距離計算部
３１  ノード間距離計算部
３１１  カテゴリパス特定部
３１２  ノード特定部
３１３  重み算出部
３１４  加算部
３２  類似度計算部
３３  合計部
４  画像ＤＢ
５  インデックスＤＢ
【図１】
0005450715.tif 000010
【図３】
0005450715.tif 000011
【図４】
0005450715.tif 000012
【図５】
0005450715.tif 000013
【図６】
0005450715.tif 000014
【図７】
0005450715.tif 000015
【図２】
0005450715.tif 000016