(57)【特許請求の範囲】
【請求項１】
蓄積された多数のオブジェクトの中から、利用者が指定したオブジェクトである参照オブジェクトに類似したオブジェクトを、類似度の高い順にある数だけ取り出して利用者に提示する類似オブジェクト検索方法であって、
蓄積されたオブジェクトの各種類の特徴量を計算して、個々の特徴量種類毎に多次元ベクトル空間のポイントとして蓄積しておき、かつ、各特徴量種類の多次元ベクトル空間では、データ検索に必要なインデクスを計算しておく段階と、
検索観点である特徴量の種類の間の重みを取得する段階と、
前記参照オブジェクトの特徴量を種類毎に算出する段階と、
特徴量の種類毎に、参照オブジェクトと蓄積された各オブジェクトとの間の多次元ベクトル空間における距離に関して、前記インデクスを利用して参照オブジェクトに対する近傍のオブジェクトを特定の数だけ求める近傍オブジェクト検索段階と、
特徴量の種類毎に求められた近傍オブジェクトを全ての特徴量種類についてまとめることで類似オブジェクトの候補を作り、その候補について参照オブジェクトとの距離に前記重みを加味して類似度を求める類似度計算段階と、
前記類似度に従い前記候補オブジェクトを順序付けして、利用者が指定した数に合わせて最終結果を求める段階と、
前記最終結果を利用者に提示する段階
とを有する類似オブジェクト検索方法。
【請求項２】
前記近傍オブジェクト検索段階および前記類似度計算段階では、近傍オブジェクトの各特徴量種類の多次元ベクトル空間での参照オブジェクトからの距離を計算し、全ての特徴量種類から求められた近傍オブジェクトをまとめて候補オブジェクトを求めた時点で、各候補オブジェクトについて距離が求まっていない特徴量種類について、その特徴量種類の多次元ベクトル空間での参照オブジェクトからの距離を計算し、その後、全候補オブジェクトについて参照オブジェクトとの距離に重みを加味して類似度を計算する、請求項１記載の類似オブジェクト検索方法。
【請求項３】
前記近傍オブジェクト検索段階および前記類似度計算段階では、近傍オブジェクトの各特徴量種類の多次元ベクトル空間での参照オブジェクトからの距離を計算せず、全ての特徴量種類から求められた近傍オブジェクトをまとめて候補オブジェクトを求めた時点で、各候補オブジェクトについて各特徴量種類の多次元ベクトル空間での距離を計算し、その後、全候補オブジェクトについて参照オブジェクトとの距離に重みを加味して類似度を計算する、請求項１記載の類似オブジェクト検索方法。
【請求項４】
前記近傍オブジェクト検索段階では、各特徴量種類の多次元ベクトル空間での検索された近傍オブジェクトについて、その段階で着目している種類の特徴量での参照オブジェクトからの距離のみでなく、全ての種類の特徴量について参照オブジェクトからの距離を計算し、しかし、各オブジェクトついて、一度距離計算したものは印をつけて距離計算が重複しないようにする、請求項１記載の類似オブジェクト検索方法。
【請求項５】
蓄積された多数のオブジェクトの中から、利用者が指定したオブジェクトである参照オブジェクトに類似したオブジェクトを、類似度の高い順にある数だけ取り出して利用者に提示する類似オブジェクト検索装置であって、
オブジェクトデータを蓄積するオブジェクトデータ蓄積手段と、
利用者が前記参照オブジェクトを入力するための参照オブジェクト入力手段と、
結果として欲しい類似オブジェクトの数を利用者が指定するオブジェクト数指定手段と、
検索観点である特徴量の種類の間の重みを取得する手段と、
蓄積された各オブジェクトおよび参照オブジェクトについて、各種類毎の特徴量を算出する特徴量算出手段と、
前記算出された特徴量のうち、あらかじめ蓄積されたオブジェクトの特徴量について、個々の特徴量種類毎に多次元ベクトル空間のポイントとして格納しておくための特徴量格納手段と、
前記算出された特徴量のうち、あらかじめ蓄積されたオブジェクトの特徴量について、各特徴量種類の多次元ベクトル空間では、データ検索に必要なインデクスを計算して、そのインデクスを格納しておくためのインデクス生成・格納手段と、
特徴量の種類毎に、参照オブジェクトと蓄積された各オブジェクトとの間の多次元ベクトル空間における距離に関して、前記インデクスを利用して参照オブジェクトに対する近傍のオブジェクトを特定の数だけ求める近傍オブジェクト検索手段と、
特徴量の種類毎に求められた近傍オブジェクトを全ての特徴量種類についてまとめることで類似オブジェクトの候補を作り、その候補について前記重みを加味して類似度を求める類似度計算手段と、
前記類似度に従い前記候補オブジェクトを順序付けして、利用者が指定した数に合わせて最終結果を求める手段と、
最終結果を利用者に提示するオブジェクト提示手段
とを有する類似オブジェクト検索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、電子博物館や電子カタログなどのディジタル化されたオブジェクト（画像、音声、音楽、テキストなど）を多数蓄積したものから、利用者が何らかの手段で入力したオブジェクト（参照オブジェクト）と類似したオブジェクトを類似していると判定された順に上位幾つかを検索結果として提示する類似オブジェクト検索装置に関する。
【０００２】
【従来の技術】
従来、利用者が指定した参照オブジェクトに類似したオブジェクトを検索して表示する類似オブジェクト検索装置では、オブジェクトについて、いくつかの特徴量を計算し、オブジェクト間でその特徴量の近さ（距離）を計算することで、類似度を求め、類似度により順位付けをしている。この際、オブジェクトを数量化するのに用いる特徴量の種類には、例えばオブジェクトが画像であれば色調、明度、彩度や、画中の線の方向などさまざまなものが用いられている。
【０００３】
距離の計算は、個々の特徴量の種類毎に多次元ベクトルで表された特徴量間のユークリッド距離等として計算され、さらに、同一のオブジェクトの組み合わせに対して複数の種類の特徴量の距離に重み付けをすることで類似性に対する利用者の観点（例えば、色が似ているという観点で類似の画像オブジェクトを検索したい）を加味して、最終的な類似性を判断するようになっている。この際、特徴量の距離の重みは、利用者が、検索条件入力手段から入力するようになっている。
【０００４】
この方法では、上記特徴量の種類毎の距離計算は、蓄積された全オブジェクトに対して行われ、各オブジェクトに対して、特徴量の種類毎の距離評価値をもとに重み付けした最終的な類似度を計算して、順位付けを行い上位のオブジェクトを返すということを行っていた。
【０００５】
または、特徴量の種類毎に距離計算を分けずに、全ての種類の特徴量をまとめたひとつの多次元ベクトル空間として扱い、そこでの距離計算を行う方法をとるものもある。この場合、利用者の検索観点である重みの反映は、利用者が指定する重みのパターンをあらかじめ限定しておき、そのパターンに従って、多次元ベクトルの個々のベクトル成分についてその重みを加味しておくという方法で行う。
【０００６】
この方法では、検索の高速化のため、重みをあらかじめ加味した多次元ベクトル空間に対して、インデクスを計算しておき、検索時には、そのインデクスを利用して、候補を絞り込むことができる。
【０００７】
【発明が解決しようとする課題】
上記のような従来の、類似度計算による類似オブジェクト検索装置では、全オブジェクトに対して特徴量の種類毎に距離計算を行わなければならないため、計算コストがかかるという問題があった。
【０００８】
また、決められたパターンに対して特徴量の多次元ベクトル空間に重みをあらかじめ加味しておくという方法では、インデクスを付与して候補の絞り込みを行うため、計算コストは押さえることができるが、決められたパターンの重み全てに対してインデクスを持っていなければならないことと、それでも限られたパターンにだけしか重みを指定できないという問題があった。
【０００９】
本発明の目的は、従来の技術における上述した問題を解消し、全てのオブジェクトに対して距離計算を行う手間を省き、かつ任意の重みで類似オブジェクトを検索することを可能にする類似オブジェクト検索方法および装置を提供することである。
【００１０】
【課題を解決するための手段】
本発明の類似オブジェクト検索方法は、
蓄積されたオブジェクトの各種類の特徴量を計算して、個々の特徴量種類毎に多次元ベクトル空間のポイントとして蓄積しておき、かつ、各特徴量種類の多次元ベクトル空間では、データ検索に必要なインデクスを計算しておく段階と、
検索観点である特徴量の種類の間の重みを取得する段階と、
前記参照オブジェクトの特徴量を種類毎に算出する段階と、
特徴量の種類毎に、参照オブジェクトと蓄積された各オブジェクトとの間の多次元ベクトル空間における距離に関して、前記インデクスを利用して参照オブジェクトに対する近傍のオブジェクトを特定の数だけ求める近傍オブジェクト検索段階と、
特徴量の種類毎に求められた近傍オブジェクトを全ての特徴量種類についてまとめることで類似オブジェクトの候補を作り、その候補について前記重みを加味して類似度を求める類似度計算段階と、
前記類似度に従い候補オブジェクトを順序付けして、利用者が指定した数に合わせて最終結果を求める段階と、
最終結果を利用者に提示する段階とを有する。
【００１１】
本発明は、特徴量種類毎の計算の分割と、個々の特徴量多次元ベクトル空間でのインデクスを利用した近傍オブジェクトの絞り込みと、全ての種類の特徴量多次元ベクトル空間からあがってきた近傍オブジェクトをまとめた候補に対する距離計算と、重みによる類似度計算を行う処理を行う。
【００１２】
本発明の請求項２によれば、近傍オブジェクト検索段階および類似度計算段階では、近傍オブジェクトのその特徴量種類の多次元ベクトル空間での距離を計算し、全ての特徴量種類から求められた近傍オブジェクトをまとめて候補オブジェクトを求めた時点で、各候補オブジェクトについて距離の求まっていない特徴量種類について、その特徴量種類の多次元ベクトル空間での距離を計算し、その後、全候補オブジェクトについて重みを加味して類似度を計算する。
【００１３】
本発明の請求項３によれば、近傍オブジェクト検索段階および類似度計算段階では、近傍オブジェクトのその特徴量種類の多次元ベクトル空間での距離を計算せず、全ての特徴量種類から求められた近傍オブジェクトをまとめて候補オブジェクトを求めた時点で、各候補オブジェクトについて各特徴量種類の多次元ベクトル空間での距離を計算し、その後、全候補オブジェクトについて重みを加味して類似度を計算する。
【００１４】
本発明の請求項４によれば、近傍オブジェクト検索段階で、各特徴量種類の多次元ベクトル空間での検索された近傍オブジェクトについて、その段階で着目している種類の特徴量での参照オブジェクトからの距離のみでなく、全ての種類の特徴量について参照オブジェクトからの距離を計算し、しかし、各オブジェクトついて、一度距離計算したものは印をつけて距離計算が重複しないようにする。
【００１５】
オブジェクトが画像オブジェクトである場合を例に簡単に説明する。特徴量の種類として色相、明度、彩度を用いるとする。今、色相の特徴量多次元ベクトル空間から近傍オブジェクトＡ，Ｂ，Ｃが、明度の空間から近傍オブジェクトＢ，Ｃ，Ｄが、彩度の空間から近傍オブジェクトＣ，Ｄ，Ｅが各々得られたとする。これらをまとめた候補オブジェクトはＡ，Ｂ，Ｃ，Ｄ，Ｅとなる。これらの各々について、色相の空間、明度の空間、彩度の空間の３種類の距離を求め、これを重み付けして、最終的な類似度を計算するわけであるが、請求項２の場合は、近傍オブジェクトＡ，Ｂ，Ｃについては、色相の距離は近傍オブジェクトを求める段階で計算しておくということである。他も同様である。「各候補オブジェクトについて距離の求まっていない特徴量種類について、・・・距離を計算し」というのは、近傍オブジェクトＡについては明度、彩度の距離が求まっておらず、近傍オブジェクトＢについては、彩度の距離が求まっていないわけで、これを求める。近傍オブジェクトＣについては全ての距離が求まっている。このような求まっていない距離を求めるものである。
【００１６】
請求項３では、候補オブジェクトＡ，Ｂ，Ｃ，Ｄ，Ｅを求めた段階で、距離を全て求めていないということである。請求項２では、部分的には求まっていて、欠けている部分の距離を後から求めるわけであるが、請求項３では、後から距離を全部求める。
【００１７】
請求項４では、色相の空間から近傍オブジェクトＡ，Ｂ，Ｃを求めた段階で、近傍オブジェクトＡ，Ｂ，Ｃについて、色相、明度、彩度全ての距離を求める。こうすると、候補オブジェクトＡ，Ｂ，Ｃ，Ｄ，Ｅを求めた段階で、５つのオブジェクト全てについて、３種類の特徴空間の距離が求まっていることになる。
【００１８】
本発明の類似オブジェクト検索装置は、
オブジェクトデータを蓄積するオブジェクトデータ蓄積手段と、
利用者が前記参照オブジェクトを入力するための参照オブジェクト入力手段と、
結果として欲しい類似オブジェクトの数を利用者が指定するオブジェクト数指定手段と、
検索観点である特徴量の種類の間の重みを取得する手段と、
蓄積された各オブジェクト及び参照オブジェクトについて、各種類毎の特徴量を算出する特徴量算出手段と、
前記算出された特徴量のうち、あらかじめ蓄積されたオブジェクトの特徴量について、個々の特徴量種類毎に多次元ベクトル空間のポイントとして格納しておくための特徴量格納手段と、
前記算出された特徴量のうち、あらかじめ蓄積されたオブジェクトの特徴量について、各特徴量種類の多次元ベクトル空間では、データ検索に必要なインデクスを計算して、そのインデクスを格納しておくためのインデクス生成・格納手段と、
特徴量の種類毎に、参照オブジェクトと蓄積された各オブジェクトとの間の多次元ベクトル空間における距離に関して、前記インデクスを利用して参照オブジェクトに対する近傍のオブジェクトを特定の数だけ求める近傍オブジェクト検索手段と、
特徴量の種類毎に求められた近傍オブジェクトを全ての特徴量種類についてまとめ、類似オブジェクトの候補を作り、その候補について前記重みを加味して類似度を求める類似度計算手段と、
前記類似度に従い、候補オブジェクトを順序付けして、利用者が指定した数に合わせて最終結果を求める手段と、
最終結果を利用者に提示するオブジェクト提示手段とを有する。
【００１９】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【００２０】
図１は本発明の一実施形態の類似オブジェクト検索装置の構成図、図２はその動作を示す流れ図である。
【００２１】
本実施形態の類似オブジェクト検索装置は、デジタル化されたオブジェクトデータＯｂ１〜Ｏｂｍを蓄積するオブジェクトデータ蓄積部１０と、オブジェクトＯｂ１〜Ｏｂｍの特徴量を計算する特徴量算出部１１と、その特徴量と別途生成されるインデクスを格納する特徴量・インデクス格納部１２と、利用者が、参照オブジェクトを新たに外部から入力するための参照オブジェクト入力部１３１、利用者が、オブジェクト間の類似度をはかるための観点である重みを指定する重み指定部１３２、利用者が、結果として得られるオブジェクトの数を指定するオブジェクト数指定部１３３、オブジェクトを利用者に提示するためのオブジェクト提示部１３４を含む、利用者とのインタフェース部１３と、特徴量の種類毎に多次元ベクトル空間のインデクスを生成するインデクス生成部１４と、特徴量の種類毎に、多次元ベクトル空間において、参照オブジェクトに対して、その多次元ベクトル空間での距離で近傍であるオブジェクトを求める近傍オブジェクト検索部１５と、利用者からの検索要求を受けて、参照オブジェクトの特徴量を特徴量種類に分けて、特徴量種類毎に近傍オブジェクト検索部１５に検索要求を引渡し、返って来た結果をまとめて候補オブジェクトとし、各候補オブジェクトについて、必要ならば不足している参照オブジェクトからの特徴量種類毎の距離を求めて、重みを加味して類似度を計算し、上位のオブジェクトから指定された数だけ類似オブジェクトとして結果を返すコーディネータ部１６と、中間結果を一時的に蓄積しておく一時データ蓄積部１７とで構成されている。
【００２２】
なお、インデクスは、多次元空間で特定の位置にあるポイントを検索したり、指定した位置の近傍にあるポイントを高速に検索するための補助データ構造である。代表的にはＲ−ｔｒｅｅやｋ−ｄｔｒｅｅがある。これらのインデクスは、ポイントの位置によって階層的なデータ構造を作り、それを元（ルートノード）から手操ることで、検索を行う。身近な例では、道路地図（２次元空間）などにある縦横でメッシュがきってあり、この観光スポットは縦Ｄ横３にある、というように検索する時に使うものも一種のインデクスといえる。
【００２３】
次に、本実施形態の動作を図２の流れ図により説明する。
【００２４】
オブジェクトＯｂ１の特徴量Ｏｂ１１，Ｏｂ１２，．．．，Ｏｂ１ｎ，オブジェクトＯｂ２の特徴量Ｏｂ２１，Ｏｂ２２，．．．，Ｏｂ２ｎ，．．．，オブジェクトＯｂｍの特徴量Ｏｂｍ１，Ｏｂｍ２，．．．，Ｏｂｍｎ（ｎは特徴量の種類の数）が特徴量算出部１１によりあらかじめ算出され、特徴量・インデクス格納部１２に格納されている。各オブジェクトＯｂ１〜Ｏｂｍ自体はオブジェクトデータ蓄積部１０に格納されている。また、各特徴量種類の多次元ベクトル空間において、検索のためインデクスがインデクス生成部１４により生成される。このインデクスは特徴量・インデクス格納部１２に格納される。
【００２５】
まず、利用者は参照オブジェクト入力部１３１から参照オブジェクトを、重み指定部１３２から重みｗ１，．．．，ｗｎを、オブジェクト数指定部１３３からオブジェクト数Ｋを入力する。重みｗ１〜ｗｎとオブジェクト数Ｋは、利用者からの入力がない場合はデフォルトの値を用いる（ステップ２１）。次に、参照オブジェクトの特徴量ＶＲ１，．．．，ＶＲｎを特徴量算出部１１により計算する（ステップ２２）。
【００２６】
次に、コーディネータ部１６は、特徴量種類毎に特徴量の種類ｉと参照オブジェクトのｉ番目の種類の特徴量ＶＲｉと、近傍オブジェクト数を指定する数（Ｋの関数）ｆ（Ｋ）（ただしＫ以上の数）を指定して、近傍オブジェクト検索部１５に近傍オブジェクト検索を要求する（ステップ２３）。
【００２７】
要求を受けた近傍オブジェクト検索部１５は各特徴量種類ｉ毎に、その多次元ベクトル空間内で、参照オブジェクトに対応するポイントにその空間の距離で近いものｆ（Ｋ）個を、インデクスを用いて求め、コーディネータ部１６に返却する（ステップ２４）。
【００２８】
近傍オブジェクトを返されたコーディネータ部１６は、全ての特徴量種類について返却された近傍オブジェクトをまとめて、候補オブジェクト群を作る（ステップ２５）。候補オブジェクト群は例えば近傍オブジェクトの和集合として求められる。この場合、候補オブジェクトの数は最大ｆ（Ｋ）×ｎ（各特徴量種類についての近傍オブジェクトに全く重複がない場合）、最小ｆ（Ｋ）（各特徴量種類について近傍オブジェクトが全く同じ場合）になる。
【００２９】
次に、候補オブジェクトＯｂｋについて、特徴量種類毎の参照オブジェクトに対応するポイントＶＲｉとＯｂｋｉとの距離ｄｋｉ（ｉは特徴量の種類）が求まっていない場合は、不足分を計算する（ステップ２６）。
【００３０】
各候補オブジェクトＯｂｋについて、ＶＲ１とＯｂｋ１との距離ｄｋ１，．．．，ＶＲｎとＯｂｋｎとの距離ｄｋｎが求まったところで、重みｗ１，．．．，ｗｎを加味して類似度を計算する（ステップ２７）。例えばｗ１／ｄｋ１＋・・・＋ｗｎ／ｄｋｎのように類似度を計算する。
【００３１】
次に、求まった類似度の大きい順に候補オブジェクトを並べて、上位Ｋ個を結果として返す（ステップ２８）。
【００３２】
コーディネータ部１６から結果が返されると、オブジェクト提示部１３４が結果を利用者に提示する（ステップ２９）。
【００３３】
なお、以上で、重みが０と指定された特徴量種類については、近傍オブジェクト検索や距離計算は省略することができる。また、重みは、必ずしも、利用者が指定したものを直接用いるだけでなく、指定されたものから、何らかの方法で求めた重みを利用することも考えられる。また、ステップ２４，２６はそれぞれ特徴量種類に関して並列に処理を行うことができる。
【００３４】
本発明の他の実施態様によれば、上記ステップ２６での距離計算を、ステップ２４での近傍オブジェクトを求める段階で合わせて行う。この場合は、ステップ２６は不要である。
【００３５】
【発明の効果】
以上説明したように、本発明は、特徴量の種類毎に、インデクスを利用して、参照オブジェクトの近傍オブジェクトを絞り込み、これら近傍オブジェクトから類似オブジェクトの候補を作り、これら候補に対する距離計算と、重みによる類似度の計算を行うので、全てのオブジェクトに対して距離計算を行う手間を省き、かつ任意の重みで類似オブジェクトを検索することが可能になる。
【図面の簡単な説明】
【図１】本発明の一実施形態の類似オブジェクト検索装置の構成図である。
【図２】図１の類似オブジェクト検索装置の動作を示す流れ図である。
【符号の説明】
１０    オブジェクトデータ蓄積部
１１    特徴量算出部
１２    特徴量・インデクス格納部
１３    インタフェース部
１３１    参照オブジェクト入力部
１３２    重み指定部
１３３    提示オブジェクト数指定部
１３４    オブジェクト提示部
１４    インデクス生成部
１５    近傍オブジェクト検索部
１６    コーディネータ部
１７    一時データ蓄積部
２１〜２９    ステップ
【図１】
0003571162.tif 000002
【図２】
0003571162.tif 000003