(57)【要約】【課題】  マルチメディアデータ間の類似、非類似の判断における識別性を高める。【解決手段】  ベクトル集合生成手段３により、入力手段２で入力された比較対象マルチメディアデータ２ａ，２ｂそれぞれが解析され、特徴ベクトルが生成され、ベクトル集合３ａ，３ｂが構成される。次に、ベクトルペア生成手段４により、比較対象マルチメディアデータ２ａ，２ｂそれぞれのベクトル集合３ａ，３ｂから特徴ベクトルが１つずつ抽出され、ベクトルペアが生成される。次に、ベクトル間距離算出手段５により、ベクトルペア生成手段４で生成されたベクトルペア毎に、ベクトルペアに含まれる特徴ベクトル間の類似度を示す距離が計算される。次に、類似度算出手段６により、ベクトル間距離算出手段５で計算された距離が合算され、比較対象マルチメディアデータ間の類似度７が算出される。【選択図】  図１
2005234994.tif 000002
【特許請求の範囲】
【請求項１】
マルチメディアデータ間の類似関係を判定するための類似度判定プログラムにおいて、
コンピュータを、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、
２つの比較対象マルチメディアデータを入力する入力手段、
前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、
前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、
前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出する類似度算出手段、
前記類似度算出手段で算出された類似度を出力する出力手段、
として機能させることを特徴とする類似度判定プログラム。
【請求項２】
前記ベクトルペア生成手段は、前記ベクトル集合の前記特徴ベクトルを複数のグループに分類し、グループ毎に合成することで、前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させることを特徴とする請求項１記載の類似度判定プログラム。
【請求項３】
前記ベクトルペア生成手段は、一方の前記特徴ベクトルの集合と他方の前記ベクトル集合とから、最も近い方向を向いた特徴ベクトル同士を選び、それらから前記ベクトルペアとなる部分を繰り返し切り出すことを特徴とする請求項１記載の類似度判定プログラム。
【請求項４】
前記斜交基底ベクトル記憶手段は、前記斜交基底ベクトルの数がｎ（ｎは自然数）であり、前記斜交基底ベクトルの線形独立性がｎ次元内で保てない場合、ｎ＋１次元から２ｎ次元の範囲内の次元で線形独立性を保った前記斜交基底ベクトルが格納されていることを特徴とする請求項１記載の類似度判定プログラム。
【請求項５】
前記ベクトルペア生成手段は、前記特徴ベクトルを分割することで、前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させることを特徴とする請求項１記載の類似度判定プログラム。
【請求項６】
前記ベクトルペア生成手段は、前記ベクトル集合それぞれから前記特徴ベクトルを抽出し、抽出した２つの前記特徴ベクトルから、前記比較対象マルチメディアデータそれぞれの特徴量の合計値の比に応じた長さのベクトルを切り出すことを特徴とする請求項５記載の類似度判定プログラム。
【請求項７】
前記ベクトルペア生成手段は、前記ベクトル集合に含まれる前記特徴ベクトルの数をｍ（ｍは自然数）に一致させたとき、各特徴ベクトルをｍ個に細分化し、細分化されたベクトル同士のベクトルペアを生成することを特徴とする請求項１記載の類似度判定プログラム。
【請求項８】
マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索プログラムにおいて、
コンピュータを、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、
複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合を記憶するベクトル集合記憶手段、
検索条件マルチメディアデータを入力する入力手段、
前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、
前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、
前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出する類似度算出手段、
前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する出力手段、
として機能させることを特徴とするマルチメディアデータ検索プログラム。
【請求項９】
マルチメディアデータ間の類似関係を判定するための類似度判定方法において、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルが斜交基底ベクトル記憶手段に記憶されており、
入力手段が、２つの比較対象マルチメディアデータを入力し、
ベクトル集合生成手段が、前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とし、
ベクトルペア生成手段が、前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成し、
ベクトル間距離算出手段が、前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算し、
類似度算出手段が、前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出し、
出力手段が、前記類似度算出手段で算出された類似度を出力する、
ことを特徴とする類似度判定方法。
【請求項１０】
マルチメディアデータ間の類似関係を判定するための類似度判定装置において、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段と、
２つの比較対象マルチメディアデータを入力する入力手段と、
前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段と、
前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段と、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段と、
前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出する類似度算出手段と、
前記類似度算出手段で算出された類似度を出力する出力手段と、
を有することを特徴とする類似度判定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は類似度判定プログラム、マルチメディアデータ検索プログラム、類似度判定方法、および類似度判定装置に関し、特にマルチメディアデータ間の類似度を判定するための類似度判定プログラム、マルチメディアデータ検索プログラム、類似度判定方法、および類似度判定装置に関する。
【背景技術】
【０００２】
計算機の分野では、従来キーワードなどの文字列や数値による検索が行われてきた。しかし、最近では、インターネットやディジタルカメラ、携帯電話などの普及に伴い、画像や音声、文書などのマルメディアに対する検索に関心が高まっている。
【０００３】
マルチメディアデータの検索方法として、注釈やキーワードによる検索がある。この検索は、次のように行われる。画像を検索する場合、その画像に注釈と呼ばれるキーワード群を付加する。キーワードは、たとえば「沖縄で撮影された真っ青な海」といったテキストや、「沖縄、海」といった単語である。各画像は、付加されたキーワードに基づいてキーワード検索が行われてきた。しかし、この注釈による方法には２つの問題点がある。
【０００４】
１つ目の問題点は、人手で注釈を付加しようとすると人的コストがかかることである。しかも、画像の急増により、注釈付けはさらに難しくなってきている。２つ目の問題点は、画像の特徴を注釈だけでは完全に記述できないことである。実際に、画像には、色や形、模様など多くの特徴があり、それらを完全に文字で特徴づけることはできない。
【０００５】
そこで、マルチメディアデータの特徴を自動抽出し、特徴空間、色ヒストグラム、特徴量を用いて検索を行う方法がある。この検索方法を適用できるマルチメディアデータとして、画像データがある。画像の類似検索では、色や形などの特徴を特徴量と呼ばれる数値として人手を介さず、自動的に抽出する。色の場合、よく用いられる代表的な方法として色ヒストグラムという方法がある。ヒストグラムは柱状グラフを意味する。
【０００６】
色ヒストグラムでは、ピクセル（画素）をｎ色（ｎは自然数）に分類し、その色ごとの画素数を抽出する。そして、画像全体の画素数に対するその色の画素数の割合で、各色の特徴を表現する。この割合のように各特徴を表す量を特徴量と呼ぶ。分類する色の数ｎとしては、たとえば６４といったある程度大きな数が用いられる。
【０００７】
今、簡単のために、まず、ｎ＝３として、色も赤、緑、青のいわゆる三原色とした場合、画像の特徴量を３次元の特量空間内の座標で表すことができる。
図１８は、色ヒストグラムによる画像の特徴量を示す図である。赤、緑、青の特徴量を示す座標軸が互いに直交するように設けられている。ここで、ある画像の赤、緑、青のそれぞれの特徴量（全ピクセル数に対するそれぞれの色の割合）がそれぞれ、０．２，０．５，０．３とする。すると、画像は座標が
【０００８】
【数１】
2005234994.tif 000003
【０００９】
である点Ａとして表される。
図１９は、３つの画像に対応する３点を表した図である。それぞれの座標は、
【００１０】
【数２】
2005234994.tif 000004
【００１１】
【数３】
2005234994.tif 000005
【００１２】
【数４】
2005234994.tif 000006
【００１３】
である。この場合、点Ｂは赤を含んでおらず、また点Ｃは緑も青も含んでいない画像を表している。そして、３つの点の間の距離を考え、より近いものが類似したものと考える。図からもわかるように、点Ａは、点Ｃよりも点Ｂに近いので、点Ｂに類似していると考える。したがって、点Ａに最も類似した画像を検索した場合は、点Ｂが検出される。
【００１４】
このように、画像に対して特徴空間の点を１対１に対応させ、距離が近いものほど似ているものとするのが、類似検索の基本的な考え方である。
このような類似検索は、様々な分野で利用されている。特徴空間を用いた類似検索は、映像を含めた画像の場合に限らず、音声や文書の分野でも広く用いられている。音声の類似検索であれば、あるイントロを入力すると、それに対応する曲を検索するといった場合である。
【００１５】
文書の類似検索では、文書の特徴量として、その文書に含まれる単語の出現頻度と、全文書数をその単語が含まれる文書の数で割った数の対数とを掛けたものがよく使われる。この場合、特徴空間の次元は、母体として考える単語の数になり、特徴空間は非常に高次元となる。このように、特徴量による類似検索は多様なマルチメディアデータで、広い範囲に渡って用いられている。
【００１６】
以上述べたように、類似検索では、マルチメディアデータである画像や文書といった対象物（以下、オブジェクトと呼ぶ）の特徴を特徴空間と呼ばれる多次元空間上のベクトル（点）に対応させる。点の座標が、対応するオブジェクトの特徴量である。特徴量は、一般には浮動小数点数で表されることが多い。すなわち、一般的には、実数値を座標とするｎ次元空間である。
【００１７】
なお、以降では、基底、特徴ベクトルということばをよく使う。まず、このことばについて説明しておく。
［基底、正規直交基底］
よく知られているように、ユークリッド空間を含むいわゆるベクトル空間内の任意のベクトルは、次元数をｎとすると、基底ベクトルと呼ばれるｎ個のベクトルを用いて表現することができる。３次元のユークリッド空間であれば、
【００１８】
【数５】
2005234994.tif 000007
【００１９】
【数６】
2005234994.tif 000008
【００２０】
【数７】
2005234994.tif 000009
【００２１】
という３つのベクトルｅ1，ｅ2，ｅ3が基底ベクトルである。この基底ベクトルを用いて、任意のベクトルνを、
【００２２】
【数８】
2005234994.tif 000010
【００２３】
という、いわゆる線形結合と呼ばれる形で表現することができる。このｎ個の基底ベクトルの組を基底と呼ぶ。このように、座標系に対して、基底が対応しており、逆に基底をもとに座標系を考えることができる。
【００２４】
この例のｅ1，ｅ2，ｅ3は（正規）直交基底と呼ばれる。直交とは、ｅi，ｅj（ｉ，ｊは自然数：ｉ≠ｊ）が互いに直交していることを意味する。また正規とは、各基底ベクトルの長さがすべて１であることを意味する。
【００２５】
［特徴ベクトル］
特徴空間の次元をｎとし、その基底ベクトルをｅ1，ｅ2，ｅ3，・・・，ｅn、オブジェクトの特徴量をｃ1，ｃ2，ｃ3，・・・，ｃnとしたとき、これらの線形結合として表されるベクトル
【００２６】
【数９】
2005234994.tif 000011
【００２７】
をそのオブジェクトに対応する全体特徴ベクトルと呼ぶことにする。全体特徴ベクトルはオブジェクトの全体的な特徴を表すものであり、オブジェクト間の距離はこの全体特徴ベクトル間の距離として測られる。一方、前述のように、特徴量はオブジェクトの各特徴を表す量である。
【００２８】
［直交基底＋ユークリッド距離］
最も基本的な方式は、ｎ個の特徴量をｎ次元のユークリッド空間の点として、
【００２９】
【数１０】
2005234994.tif 000012
【００３０】
と表す方式である。そして、２点間の距離は通常のユークリッド距離として表す。すなわち、もう１点を
【００３１】
【数１１】
2005234994.tif 000013
【００３２】
とした時、２点間の距離ｄは、
【００３３】
【数１２】
2005234994.tif 000014
【００３４】
で与えられる。ただし、この方式は、以下に述べるような問題を持っている。今、色として、１２色を考える。このとき１２の色は、色相環で表される。
図２０は、色相環を示す図である。色相環は、複数の色を隣に似た色がくるように環状にならべたものである。最も似ていないのが、その色の真向かいにある色で補色と呼ばれている（なお、図２０で示した色相環は説明を分かり易くするため、実際のものを簡略化したものであり、色の名前も通常のものとは異なるので注意されたい。たとえば、緑青は、緑がかった青、黄緑は黄色がかった緑、緑黄は緑がかった黄色、黄橙は黄色がかった橙、赤橙は赤みがかった橙を示している）。この場合、画像は色ヒストグラムによる方法で１２次元の特徴空間として表される。今、説明をわかりやすくするために、３つの赤、赤橙、緑の単一色からなる画像を考える。それぞれの画像は、座標では、
【００３５】
【数１３】
2005234994.tif 000015
【００３６】
【数１４】
2005234994.tif 000016
【００３７】
【数１５】
2005234994.tif 000017
【００３８】
と表される。
図２１は、赤、赤橙、緑の単一色からなる画像それぞれの特徴量を示す図である。なお、この図２１では、他の色に関する座標軸は省略している。前述の距離を計算する式を用いて、各画像の間の距離を計算すると、図２１からもわかるように、
赤・緑間＝２1/2
赤・赤橙間＝２1/2
赤橙・緑間＝２1/2
となる（２1/2は、２の１／２乗を示す）。すなわち、どの２つの画像間の距離も同じになり、数値上は同様に似ているものと見なされる。しかし、実際人間が見た場合、青緑と赤は似ていないが、赤と赤橙はよく似ているように見える。すなわち、ここで用いた特徴空間での点の取り方が、人間が感じる類似性を反映していないことになる。
【００３９】
このことは画像ばかりでなく、マルチメディア一般に言える。以下はテキストの例である。
［文書の例］
文書を特徴空間で表す際、次のような１つだけの単語からなる３つの簡単な文書を考えてみる（通常は当然もっと多くの単語を含んでいるが説明のため１つにしている）。
文書１＝｛総理大臣｝
文書２＝｛首相｝
文書３＝｛テニス｝
いま、母体となる単語として、｛総理大臣、首相、テニス｝というものを考えているとする。ｉ次元目の特徴量はｉ番目の単語が現れる数とする。このとき、各文書はベクトルとして、
【００４０】
【数１６】
2005234994.tif 000018
【００４１】
【数１７】
2005234994.tif 000019
【００４２】
【数１８】
2005234994.tif 000020
【００４３】
と表される。この場合、各文書間の距離を計算すると、画像の場合と同様に、
文書１・文書２間＝２1/2
文書２・文書３間＝２1/2
文書３・文書１間＝２1/2
となり、どの文書も同等に似ていることになる。しかし、首相と総理大臣は、同じ意味であり、画像の場合と同様、人間が感じる類似性を反映していないことになる。
【００４４】
［直交基底＋二次形式距離］
「直交基底＋ユークリッド距離」の問題点を解決するためにいろいろな手法が提案されている。基本的には、直交基底を用いるが、２点ｘ，ｙ間の距離を表す距離関数ｄ（ｘ，ｙ）として前述のユークリッド距離を使うのではなく、特徴間の類似性を反映された距離関数を用いるものである。
【００４５】
「直交基底＋ユークリッド距離」で用いたユークリッド距離は計算が容易である。一方、ここで用いられる距離関数は一般に複雑で、計算時間を要する場合が多く、それを解決することが一つの課題となる。
【００４６】
以下、この方式の中でも代表的な二次形式距離について説明する。
二次形式距離においてはベクトルｘを
【００４７】
【数１９】
2005234994.tif 000021
【００４８】
としたとき、その長さ‖ｘ‖を行列Ｓを用いて、
【００４９】
【数２０】
2005234994.tif 000022
【００５０】
で定義する（tｘはベクトルｘの転置ベクトルである。すなわち、ｘが列ベクトルであれば、それを行ベクトルにしたものを意味する）。したがって、ベクトルｘ，ｙ間の距離ｄ（ｘ，ｙ）は、その差ベクトルの長さとして
【００５１】
【数２１】
2005234994.tif 000023
【００５２】
で求められる。行列Ｓは特徴間の類似性を表す行列で、類似行列と呼ぶことにする。行列の要素Ｓijは類似度と呼ばれ、ｉ番目の特徴とｊ番目の特徴の間の類似している度合いを表す。Ｓが単位行列の場合は、通常のユークリッド距離になる。その意味で、この二次形式距離はユークリッド距離の一般化になっている。この方式は米国ＩＢＭ社のＱＢＩＣ（Query By Image Content）（商標）システムで使用されている（たとえば、非特許文献１参照）。
【００５３】
［斜交基底＋ユークリッド距離］
斜交座標を利用した斜交基底による類似度検索も考えられている。数学的にはよく知られているように、斜交基底ベクトルの間の角度は９０°である必要はない。このように、直交するとは限らない斜交基底ベクトルに基づく座標は斜交座標と呼ばれ、数学、物理をはじめ多くの技術分野で広く使われている。この基底を斜交基底と呼ぶことにする。
【００５４】
図２２は、斜交基底の例を示す図である。図２２には、図２１の直交基底を赤と赤橙が類似していることを考慮して、赤橙に対応する斜交基底ベクトルを赤に近づけた斜交基底が表されている。
【００５５】
図２３は、直交座標と斜交座標の関係を説明する図である。今、点Ｐは直交座標では、〔８，７〕と表される。ｅ1，ｅ2を斜交基底ベクトルとする基底を考える。それぞれの直交座標は、
【００５６】
【数２２】
2005234994.tif 000024
【００５７】
【数２３】
2005234994.tif 000025
【００５８】
である。点Ｐを斜交座標で表す場合には、まず、Ｐを通り斜交基底ベクトルｅ2に平行な線と、斜交基底ベクトルｅ1の延長とが交わる点Ａ，およびＰを通り斜交基底ベクトルｅ1に平行な線と、斜交基底ベクトルｅ2の延長とが交わる点Ｂを求める。今後、一般に点Ｘから点ＹへのベクトルをベクトルＸＹと書くことにする。すると、よく知られているように、ベクトルＯＰは、２つのベクトルＯＡ、ベクトルＯＢの和として、ベクトルＯＰ＝ベクトルＯＡ＋ベクトルＯＢと書ける。ベクトルＯＡ＝３ｅ1，ベクトルＯＢ＝２ｅ2であるから、結局、
ベクトルＯＰ＝３ｅ1＋２ｅ2と表される。ここで、ｅ1，ｅ2の係数３，２からできる
【００５９】
【数２４】
2005234994.tif 000026
【００６０】
が点Ｐの斜交座標である。点Ｐの斜交座標と直交座標の間には、
【００６１】
【数２５】
2005234994.tif 000027
【００６２】
という関係がある。ここで、この式の最後は、行列とベクトルの積を表している。この行列を(斜交座標から直交座標への)特徴ベクトル変換行列と呼ぶことにする。この行列をＴとすると、この行列は、上記の例からもわかるように、ｅ1，ｅ2を順に並べることによって、作ることができる。すなわち、Ｔ＝（ｅ1  ｅ2）である。
【００６３】
斜交基底方式の基本的な考え方は、類似性を斜交基底ベクトル間の距離に反映させることである。距離関数はユークリッド距離をそのまま用いる。このことにより、距離の計算が容易になるというメリットがある。また、この方式による２つのオブジェクト間の距離は、二次形式距離と基本的には同じになる。すなわち、精度の面からは両方式は基本的には同等である。ただし、斜交基底の方式で必要な記憶量は、二次形式距離のほぼ半分でよい。記憶量はまた処理スピードにも影響する。その点が斜交基底による方式の利点である。
【００６４】
斜交基底の原型となるアイデアでは、斜交基底による線形結合ではなく、上記の行列Ｔによって直交座標で表された特徴ベクトルを変換して新たな特徴ベクトルを作るという方法が用いられている（非特許文献２参照）。
【００６５】
また、斜交基底を用いた方式については、以下の特許出願をしている。
「画像データの類似検索装置および該類似検索装置における類似判定方法」出願番号：特願２００３−１７２２１７（出願日：平成１５年６月１７日）
また、Earth Mover’s Distance（ＥＭＤ）という類似画像検索技術がある。以下、簡単にこの技術について説明する。
【００６６】
ＥＭＤは、複数の点の間の距離に基づいて画像間の類似度を判断する。この距離の定義を以下、土盛りと穴の比喩を使って簡単に説明することにする。この距離は運搬問題(transportation problem)の解に基づく。それぞれ画像などに対応するシグニチャ(signature)と呼ばれるｘ，ｙを
【００６７】
【数２６】
2005234994.tif 000028
【００６８】
とする。ｘが土盛りの集合に対応し、ｙが穴の集合に対応する。ｍ（ｍは自然数）とｎ（ｎは自然数）は異なっていても構わない。この柔軟性がＥＭＤの特徴の一つである。ｐi、ｑjは任意の距離が定義されている空間内の点とする。各点ｐiには体積がｘiの土が盛られ、各点ｑjには容積がｙjの穴が掘られているとする。土の総体積は穴全部を埋めるのに十分あるものとする。ｄijをｐi,ｑj間の距離、ｆijをｐi,からｑjへ運ばれる土の量とする。このとき、全部の穴を埋めるためのコスト
【００６９】
【数２７】
2005234994.tif 000029
【００７０】
を最小にするｆijを求め、ｘ，ｙ間のＥＭＤを
【００７１】
【数２８】
2005234994.tif 000030
【００７２】
と定義する。分母は正規化のためのものであり、総量が少ないシグニチャが選ばれやすくするのを防ぐ。下記の非特許文献３では、画像の色とテキスチャ（模様）にＥＭＤが適用されている。また、２つのシグニチャの総量が異なる場合は、部分マッチに対応する。この距離は２つの色ヒストグラムの場合とは異なり、ｍ，ｎが任意に指定できるという柔軟性を持ち、距離の下限の計算が容易である（非特許文献３参照）。
【非特許文献１】James Hafner, et al.,Efficient Color Histogram Indexing for Quadratic Form Distance Functions,IEEE Trans. Pattern Anl. Machine Intell. 17(7), pp.729-736, (1995)
【非特許文献２】J.S.N. Jean,A New Distance Measure for Binary Images,Proc. IEEE ICASSP '90, 4 pp.3-6 (1990); Paper#: M5.19
【非特許文献３】Yossi Rubner, et al., A Metric for Distribution with Applications to Image Databases, Proc. IEEE Intl. Conf. On Computer Vision, pp.59-66, (1998)
【発明の開示】
【発明が解決しようとする課題】
【００７３】
しかし、従来の技術では、識別性が欠如していることが問題となる。
図２４は、ＥＭＤを除く従来技術の問題点を整理した図である。図２４の傾向で、似たものを棄却とあるのは、似ているにも関わらず、似ていないと判断する傾向を意味する。この傾向に該当する方式が丸印（○）で示されている。この傾向は、前述のように、直交基底＋ユークリッド距離方式に見られる。
【００７４】
一方、似ていないものを選択というのは、似ていないにも関わらず似ていると判断する傾向を意味している。この傾向に該当する方式が丸印（○）で示されている。この傾向は、特徴間の類似性を導入した、直交基底＋二次形式距離、および斜交基底＋ユークリッド距離の２つの方式に見られる。これらの方式では、極端な場合には、全く違うものを同じものとしてしまう。このことを「識別性の欠如」と呼ぶことにする。この解決がこの発明の一つの目的である。
【００７５】
図２５は、色相環における特徴間の類似性を斜交基底に忠実に反映した図である。ここで、赤と緑の２色だけからなり、しかもそれぞれ同じ量だけ（赤が５０％、緑が５０％）含む画像と、同様に黄色と青だけからなり、それぞれ同じ量だけ含む（黄が５０％、青が５０％）画像の特徴ベクトルは、それぞれ零ベクトルとなってしまう。すなわち、色としては全く異なるのに、類似検索では、全く同じものとして検索されてしまうことになる。この原因は、これら１２個のベクトルが線形独立ではないことにある。したがって、上でｅ1，ｅ2，ｅ3，・・・を基底と言ったが、本来は数学的には基底とは言えない。ただし、こういう場合も基底と呼ぶことにする。
【００７６】
図２４の説明に戻り、識別性の欠如と性能維持との観点により、各方式の利点と欠点とを整理する。図２４では、特徴間類似性、識別性、計算量、記憶量が、各方式に関して示されている。特徴間類似性は、特徴間の類似、非類似の関係が反映されるか否かを示している。識別性は、類似しないオブジェクトを正しく識別できるか否かを示している。計算量は、計算の処理数が少ないか否かを示している。記憶量は、必要なメモリ容量が少ないか否かを示している。それぞれの特性が肯定的であれば丸印（○）、否定的であればばつ印（×）、どちらでもなければ三角印（△）が示されている。
【００７７】
図２４に示すように、特性間の類似性が反映され、且つ良好な識別性を有する方式はない。ここで、「斜交基底＋ユークリッド距離」については、識別性を除いて、良好な結果が得られる。すなわち、「斜交基底＋ユークリッド距離」の現在の性能を損なわずに、識別性を高めることが望まれる。
【００７８】
なお、ＥＭＤでは、２つのシグニチャの総量（特徴量の総数）が異なる場合は、部分マッチとなる。前述の説明と同様に土盛りの集合と穴の集合とで例えれば、全ての土が穴に埋められた場合、埋められていない穴が残っていても、比較処理は終了する。そのため、一方のオブジェクトの特徴が、他方のオブジェクトの特徴に対して部分的に類似していれば、それらのオブジェクト全体で非類似であっても、類似しているものと判断されてしまう。すなわち、比較されるオブジェクト間の特徴量の総数が異なる場合には、部分マッチができるというメリットがある反面、全体としての類似性を問題とする場合、全体として似ていないものを選択する可能性がある（識別性が損なわれる）。
【００７９】
本発明はこのような点に鑑みてなされたものであり、マルチメディアデータ間の全体比較による類似、非類似の判断における識別性を高めた類似度判定プログラム、マルチメディアデータ検索プログラム、類似度判定方法、および類似度判定装置を提供することを目的とする。
【課題を解決するための手段】
【００８０】
本発明では上記課題を解決するために、図１に示すような類似度判定プログラムが提供される。本発明に係る類似度判定プログラムは、マルチメディアデータ間の類似関係を判定するためのものである。この類似度判定プログラムを実行するコンピュータは、図１に示す機能を有する。
【００８１】
斜交基底ベクトル記憶手段１は、マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトル１ａを記憶する、入力手段２は、２つの比較対象マルチメディアデータ２ａ，２ｂを入力する。ベクトル集合生成手段３は、入力手段２で入力された比較対象マルチメディアデータ２ａ，２ｂそれぞれを解析し、属性に応じた情報の含有度を示す特徴量を決定し、属性毎に特徴量を斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合３ａ，３ｂとする。ベクトルペア生成手段４は、比較対象マルチメディアデータ２ａ，２ｂそれぞれのベクトル集合３ａ，３ｂに含まれる特徴ベクトルの数を一致させ、ベクトル集合３ａ，３ｂそれぞれに含まれる特徴ベクトル同士を１対１で対応付けてベクトルペアを生成する。ベクトル間距離算出手段５は、ベクトルペア生成手段４で生成されたベクトルペア毎に、ベクトルペアに含まれる特徴ベクトル間の類似度を示す距離を計算する。類似度算出手段６は、ベクトル間距離算出手段５で計算された距離を合算し、比較対象マルチメディアデータ間の類似度７を算出する。出力手段８は、類似度算出手段で算出された類似度７を出力する。
【００８２】
このような類似度判定プログラムをコンピュータに実行させると、コンピュータ上で、入力手段２により、２つの比較対象マルチメディアデータ２ａ，２ｂが入力される。次に、ベクトル集合生成手段３により、入力手段２で入力された比較対象マルチメディアデータ２ａ，２ｂそれぞれが解析され、属性に応じた情報の含有度を示す特徴量が決定され、属性毎に特徴量を斜交基底ベクトルに乗算して特徴ベクトルが生成され、ベクトル集合３ａ，３ｂが構成される。次に、ベクトルペア生成手段４により、比較対象マルチメディアデータ２ａ，２ｂそれぞれのベクトル集合３ａ，３ｂから特徴ベクトルが１つずつ抽出され、ベクトルペアが生成される。次に、ベクトル間距離算出手段５により、ベクトルペア生成手段４で生成されたベクトルペア毎に、ベクトルペアに含まれる特徴ベクトル間の類似度を示す距離が計算される。次に、類似度算出手段６により、ベクトル間距離算出手段５で計算された距離が合算され、比較対象マルチメディアデータ間の類似度７が算出される。そして、出力手段８により、類似度算出手段で算出された類似度７が出力される。
【００８３】
また、上記課題を解決するために、マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索プログラムにおいて、コンピュータを、前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合を記憶するベクトル集合記憶手段、検索条件マルチメディアデータを入力する入力手段、前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出する類似度算出手段、前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する出力手段、として機能させることを特徴とするマルチメディアデータ検索プログラムが提供される。
【００８４】
このようなマルチメディアデータ検索プログラムをコンピュータに実行させると、コンピュータ上で、入力手段により、検索条件マルチメディアデータが入力される。次に、ベクトル集合生成手段により、前記入力手段で入力された前記検索条件マルチメディアデータが解析され、前記属性に応じた情報の含有度を示す特徴量が決定され、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルが生成され、ベクトル集合とされる。次に、ベクトルペア生成手段により、前記検索条件マルチメディアデータと、前記検索対象マルチメディアデータとのそれぞれの前記ベクトル集合から前記特徴ベクトルが１つずつ抽出され、ベクトルペアが生成される。次に、ベクトル間距離算出手段により、前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離が計算される。次に、類似度算出手段により、前記ベクトル間距離算出手段で計算された前記距離が前記検索対象マルチメディアデータ毎に合算され、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度が算出される。そして、出力手段により、前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報が出力される。
【発明の効果】
【００８５】
以上説明したように本発明では、マルチメディアデータの特徴を複数の特徴ベクトルで表し、比較対象のマルチメディアデータそれぞれの特徴ベクトルを１対１に対応付けたベクトルペア間の距離を合算することで、マルチメディアデータの類似度を判定するようにした。これにより、マルチメディアデータ間の識別性を損なわずに高精度な類似度を算出することができる。
【発明を実施するための最良の形態】
【００８６】
以下、本発明の実施の形態を図面を参照して説明する。
まず、実施の形態に適用される発明の概要について説明し、その後、実施の形態の具体的な内容を説明する。
【００８７】
図１は、実施の形態に適用される発明の概念図である。本発明は、斜交基底ベクトル記憶手段１、入力手段２、ベクトル集合生成手段３、ベクトルペア生成手段４、ベクトル間距離算出手段５、類似度算出手段６、および出力手段８を有している。
【００８８】
斜交基底ベクトル記憶手段１は、マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトル１ａを記憶する。たとえば、マルチメディアデータが画像データの場合、属性として複数の代表色が定義される。代表色は、色相環を構成する色を適用することができる。その場合、たとえば、代表色の位置を指し示す長さ１のベクトルが斜交基底ベクトル１ａとして定義される。
【００８９】
入力手段２は、２つの比較対象マルチメディアデータ２ａ，２ｂを入力する。たとえば、キーボード等の入力装置を介してユーザによって指定された比較対象マルチメディアデータ２ａ，２ｂをベクトル集合生成手段３に対して入力する。
【００９０】
ベクトル集合生成手段３は、入力手段２で入力された比較対象マルチメディアデータ２ａ，２ｂそれぞれを解析し、属性に応じた情報の含有度を示す特徴量を決定する。次に、ベクトル集合生成手段３は、属性毎に特徴量を斜交基底ベクトルに乗算して特徴ベクトルを生成する。そして、ベクトル集合生成手段３は、生成した特徴ベクトルを比較対象マルチメディアデータ２ａ，２ｂ毎にグループ化し、各グループをベクトル集合３ａ，３ｂとする。
【００９１】
たとえば、マルチメディアデータが画像データの場合、ベクトル集合生成手段３は、画像データで表現される画像の色と代表色との対応関係を予め定義しておく。そして、ベクトル集合生成手段３は、代表色に対応する色が画像に占める割合を、属性の特徴量とする。
【００９２】
ベクトルペア生成手段４は、比較対象マルチメディアデータ２ａ，２ｂそれぞれのベクトル集合３ａ，３ｂから特徴ベクトルを１つずつ抽出して、ベクトルペアを生成する。たとえば、ベクトルペア生成手段４は、一方の特徴ベクトルの集合から特徴ベクトルを抽出し、他方のベクトル集合から、先に抽出された特徴ベクトルに最も近い方向を向いている特徴ベクトルを抽出して、ベクトルペアを生成する。２つの特徴ベクトルの向きの近さは、たとえば、２つの特徴ベクトルの長さを１に正規化して内積を計算することで見積もることができる。
【００９３】
また、ベクトルペア生成手段４は、２つのベクトル集合３ａ，３ｂそれぞれに含まれる特徴ベクトルの数が不一致の場合、それぞれの数を一致させる。たとえば、数が少ない方のベクトル集合に含まれる特徴量ベクトルを分割することで数を一致させる。特徴ベクトル数が一致すれば、全ての特徴ベクトルを用いて類似度７の計算を行うことができる。すなわち、一部だけの比較ではなく、全体としての比較が常に行われる。なお、ある特徴ベクトルを分割する際には、たとえば、ペアとなる他の特徴ベクトルと同じ長さに分割する。
【００９４】
ベクトル間距離算出手段５は、ベクトルペア生成手段４で生成されたベクトルペア毎に、ベクトルペアに含まれる特徴ベクトル間の類似度を示す距離を計算する。
類似度算出手段６は、ベクトル間距離算出手段５で計算された距離を合算し、比較対象マルチメディアデータ間の類似度７を算出する。
【００９５】
出力手段８は、類似度算出手段で算出された類似度７を出力する。たとえば、出力手段８は、算出された類似度７の値を画面表示させたり、ハードディスク装置等に保存したりする。
【００９６】
このような構成に基づいて、以下の処理が行われる。まず、入力手段２により、２つの比較対象マルチメディアデータ２ａ，２ｂが入力される。次に、ベクトル集合生成手段３により、入力手段２で入力された比較対象マルチメディアデータ２ａ，２ｂそれぞれが解析され、属性に応じた情報の含有度を示す特徴量が決定され、属性毎に特徴量を斜交基底ベクトルに乗算して特徴ベクトルが生成され、ベクトル集合３ａ，３ｂが構成される。次に、ベクトルペア生成手段４により、比較対象マルチメディアデータ２ａ，２ｂそれぞれのベクトル集合３ａ，３ｂから特徴ベクトルが１つずつ抽出され、ベクトルペアが生成される。次に、ベクトル間距離算出手段５により、ベクトルペア生成手段４で生成されたベクトルペア毎に、ベクトルペアに含まれる特徴ベクトル間の類似度を示す距離が計算される。次に、類似度算出手段６により、ベクトル間距離算出手段５で計算された距離が合算され、比較対象マルチメディアデータ間の類似度７が算出される。そして、出力手段８により、類似度算出手段で算出された類似度７が出力される。
【００９７】
図２は、画像データの類似度判断例を示す模式図である。たとえば、斜交基底ベクトルとして、色相環９ａの赤を示すベクトルｅ1、赤橙を示すベクトルｅ2、黄橙を示すベクトルｅ3、黄を示すベクトルｅ4、緑黄を示すベクトルｅ5、黄緑を示すベクトルｅ6、緑を示すベクトルｅ7、青緑を示すベクトルｅ8、緑青を示すベクトルｅ9、青を示すベクトルｅ10、青紫を示すベクトルｅ11、赤紫を示すベクトルｅ12が定義されているものとする。
【００９８】
ここで、比較対象の２つの画像データ９ｂ，９ｃが入力された場合を考える。ベクトル集合生成手段３には、画像データ９ｂ，９ｃを構成する画素の表示可能色の全てについて、色相環９ａのどの色に近いのかを示す対応関係が定義されている。そして、ベクトル集合生成手段３は、色相環９ａの色毎に、対応する色が画像データ９ｂ，９ｃそれぞれの画像内に占める割合を計算する。図２の例では、画像データ９ｂは、赤が５０％、緑が５０％である。また、画像データ９ｃは、赤橙が５０％、青緑が５０％である。
【００９９】
ベクトル集合生成手段３は、画像データ９ｂ，９ｃ毎に、ベクトル集合９ｄ，９ｅを生成する。図２の例では、画像データ９ｂに対応するベクトル集合９ｄには、０．５ｅ1と０．５ｅ7とが特徴ベクトルとして含まれる。また、画像データ９ｃに対応するベクトル集合９ｅには、０．５ｅ2と０．５ｅ8とが特徴ベクトルとして含まれる。
【０１００】
次に、ベクトルペア生成手段４によって、ベクトルペアが生成される。たとえば、ベクトルペア生成手段４は、ベクトル集合９ｄから特徴ベクトル“０．５ｅ1”を取り出す。そして、ベクトルペア生成手段４は、他方のベクトル集合９ｅから、取り出した特徴ベクトルに最も近い方向を向いた特徴ベクトル“０．５ｅ2”を取り出す。そして、ベクトルペア生成手段４は、取り出した２つの特徴ベクトルにより、ベクトルペアを生成する。同様にして、特徴ベクトル“０．５ｅ7”と“０．５ｅ8”とのベクトルペアが生成される。
【０１０１】
ベクトル間距離算出手段５は、ベクトルペア毎に、特徴ベクトル間の距離ｄ1、ｄ2を算出する。そして、類似度算出手段６は、特徴ベクトル間の距離ｄ1、ｄ2を合算することで、類似度９ｆを算出する。
【０１０２】
このように、比較対象のマルチメディアデータそれぞれの特徴ベクトルで生成されたベクトルペア間の距離を合算することで、マルチメディアデータの類似度を判定するようにした。これにより、マルチメディアデータ間の識別性を損なわずに効率的に類似度を算出することができる。
【０１０３】
しかも、マルチメディアデータの特徴をベクトルで表すため、ベクトルの方向によって類似する他のベクトルを容易に識別することができ、ベクトルペアの生成に係る処理負荷が少なくてすむ。
【０１０４】
図３は、マルチメディアデータ検索装置のハードウェア構成例を示す図である。マルチメディアデータ検索装置１００は、ＣＰＵ(Central Processing Unit)１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０７を介してＲＡＭ(Random Access Memory)１０２、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、および通信インタフェース１０６が接続されている。
【０１０５】
ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ(Operating System)のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。ＨＤＤ１０３には、ＯＳやアプリケーションプログラムが格納される。
【０１０６】
グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１１の画面に表示させる。入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号を、バス１０７を介してＣＰＵ１０１に送信する。
【０１０７】
通信インタフェース１０６は、ネットワーク１０に接続されている。通信インタフェース１０６は、ネットワーク１０を介して、他のコンピュータとの間でデータの送受信を行う。
【０１０８】
以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。
図４は、マルチメディアデータ検索装置の機能構成図である。マルチメディアデータ検索装置１００の機能は、記憶装置１１０と類似検索装置１２０とに大別される。
【０１０９】
記憶装置１１０には、画像ファイル群１１１およびベクトル集合１１２が格納される。画像ファイル群１１１は、検索対象とされる複数の画像データである。画像ファイル群１１１は、検索開始前に予め記憶装置１１０に格納される。ベクトル集合１１２は、画像の特徴を示す特徴ベクトルの集合である。ベクトル集合１１２は、画像ファイル群１１１内の画像毎に生成される。
【０１１０】
類似検索装置１２０は、生成装置１２１、検索装置１２３、および距離計算装置１２４を有する。
生成装置１２１は、記憶装置１１０内の画像ファイル群に未処理の画像ファイルが追加されたとき、および検索装置１２３から検索目的の画像ファイルを渡されたとき、該当する画像ファイルの特徴を示すベクトル集合を生成する。ベクトル集合の生成は、特徴量抽出装置１２１ａとベクトル集合生成装置１２１ｂとによって行われる。
【０１１１】
特徴量抽出装置１２１ａは、処理対象の画像ファイルを取得し、その画像ファイルで示される画像の特徴量を、予め規定された属性毎に抽出する。予め規定された属性とは、たとえば所定の色である。色の属性毎の特徴量を抽出する場合、特徴量抽出装置１２１ａには、画像ファイルで表現可能な色が、属性として指定色（代表色）のどれに類似しているかが予め定義されている。次に、特徴量抽出装置１２１ａは、画像ファイルで表現される画像内の色を、代表色に分類する。そして、特徴量抽出装置１２１ａは、各代表色に対応する領域が画像内に占める割合を、その代表色に対応する属性の特徴量とする。特徴量抽出装置１２１ａは、抽出した特徴量をＲＡＭ１０２等に一時的に格納する。
【０１１２】
ベクトル集合生成装置１２１ｂには、予め斜交基底ベクトルが定義されている。斜交基底ベクトルは、画像ファイルの特徴量を表す属性毎に定義されている。ベクトル集合生成装置１２１ｂは、特徴量抽出装置１２１ａが抽出した特徴量をメモリ１０２から取得し、その特徴量を対応する属性の斜交基底ベクトルに乗算し、特徴ベクトルとする。特徴量抽出装置１２１ａで抽出された特徴量毎の特徴ベクトルの生成が完了すると、ベクトル集合生成装置１２１ｂは、それらの特徴ベクトルの集合（ベクトル集合）を生成する。
【０１１３】
処理対象の画像ファイルが記憶装置１１０から取得された場合、ベクトル集合生成装置１２１ｂは、生成されたベクトル集合１１２を、処理対象の画像ファイルに関連付けて記憶装置１１０に格納する。処理対象の画像ファイルが検索装置１２３から渡された場合、ベクトル集合生成装置１２１ｂは、生成されたベクトル集合１１２を、検索装置１２３に渡す。
【０１１４】
検索装置１２３は、検索目的の画像ファイルの入力を受け付け、その画像ファイルに類似する画像ファイルを記憶装置１１０内の画像ファイル群１１１から検索する。具体的には、検索装置１２３は、入力された画像ファイルを生成装置１２１に渡し、生成装置からベクトル集合を受け取る。次に、検索装置１２３は、記憶装置１１０内の画像ファイル毎のベクトル集合１１２を順次取得する。検索装置１２３は、検索目的の画像ファイルのベクトル集合と記憶装置１１０から取得したベクトル集合とを距離計算装置１２４に渡す。すると、距離計算装置１２４においてベクトル集合間の距離が計算され、検索装置１２３に渡される。
【０１１５】
検索装置１２３は、記憶装置１１０内の各画像ファイルに対応するベクトル集合と、検索目的の画像ファイルのベクトル集合とから画像ファイル間の距離を認識する。検索装置１２３は、検索目的の画像ファイルに対して距離が近い画像ファイルほど類似していると判断し、上位の所定数の画像ファイル（またはその画像ファイルの識別情報）を、検索結果として出力する。
【０１１６】
距離計算装置１２４は、比較対象となっている２つの画像ファイルそれぞれに対応するベクトル集合を検索装置１２３から受け取ると、それらのベクトル集合間の距離を計算する。具体的には、距離計算装置１２４は、入力された２つのベクトル集合それぞれに含まれる特徴ベクトルを１対１で対応付け、複数のベクトルペアを生成する。距離計算装置１２４は、生成したベクトルペア間の距離を算出する。そして、距離計算装置１２４は、各ベクトルペア間の距離を合算して、ベクトル集合間の距離とする。この距離は、画像ファイル間の類似度を示す情報であり、類似度が高いほど距離を示す値が小さくなる。距離計算装置１２４は、算出した距離を検索装置１２３に渡す。
【０１１７】
このような類似検索装置１２０によれば、ユーザにより検索目的となる画像ファイルが入力されると、その画像ファイルが検索装置１２３から生成装置１２１に渡される。生成装置１２１では、渡された画像ファイルのベクトル集合が生成され、検索装置１２３に渡される。すると、検索装置１２３により、記憶装置１１０からベクトル集合１１２が抽出され、抽出したベクトル集合と検索目的の画像ファイルのベクトル集合との距離が距離計算装置１２４で計算される。そして、検索装置１２３により、距離の値が小さいベクトル集合１１２に対応する画像ファイルが類似する画像ファイルとして出力される。
【０１１８】
以下、図４に示すマルチメディアデータ検索装置１００における処理内容を詳細に説明する。
［１  類似行列から斜交基底を求める方式］
マルチメディアデータ検索装置１００では、予め斜交基底を定義しておく必要がある。斜交基底は、類似行列から算出することができる。以下、類似行列からいかに斜交基底を求めるかについて述べる。
【０１１９】
なお、以下で使う用語について説明しておく。正方行列とは、行数と列の数が等しい行列である。正則行列とは、逆行列を持つ正方行列である。正値とは、正方行列の固有値が全て正である場合、その行列を指す。
【０１２０】
［１．１  類似行列が正値である場合］
求めるべき斜交基底を、ｅ1，ｅ2，・・・，ｅnとする。このとき、
【０１２１】
【数２９】
2005234994.tif 000031
【０１２２】
と一般性を失うことなく置くことができる。したがって、特徴量を成分とするベクトルから特徴ベクトルへの変換行列Ｔは、
【０１２３】
【数３０】
2005234994.tif 000032
【０１２４】
である。今、類似行列を
【０１２５】
【数３１】
2005234994.tif 000033
【０１２６】
とする。このとき、斜交基底の満たすべき条件は、以下の４つの条件である。
・条件（Ｃ１）：‖ｅi‖＝１    （１＜ｉ≦ｎ）
・条件（Ｃ２）：（ｅi，ｅj）＝ｓij    （１＜ｉ≦ｊ≦ｎ）
・条件（Ｃ３）：ｅ1，ｅ2，・・・，ｅnは線形独立
・条件（Ｃ４）：全体特徴ベクトル「ｆ＝ｃ1ｅ1＋ｃ2ｅ2＋・・・＋ｃnｅn」によって表されるオブジェクト間の類似度が人間の感覚に合っている。
【０１２７】
なお、条件（Ｃ２）の左辺は、ベクトルの内積を示している。また、条件（Ｃ３）は、ベクトル集合同士で比較する場合の絶対的な条件ではない。すなわち、ベクトル集合によって比較を行えば、線形独立でない斜交基底ベクトルを用いても識別性を獲得することができる。ただし、斜交基底ベクトルが線形独立である方が良好な識別性が得られるため、本実施の形態では条件（Ｃ３）を満たす斜交基底ベクトルを用いるものとする。
【０１２８】
条件（Ｃ４）は人間の主観が入るので評価が難しいが、類似検索における最終目標は、この条件を満たすことである。それに対して、条件（Ｃ１）〜条件（Ｃ３）は数学的な条件で、成り立つかどうかがはっきりしている。ここでは、条件（Ｃ４）を考慮しつつ、まず、条件（Ｃ１）から条件（Ｃ３）の条件を満たす解を求める方法について説明する。
【０１２９】
まず、条件（Ｃ１）より‖ｅ1‖＝１であり、したがって、ｅ11＝１である。このことと条件（Ｃ２）とにより、ｅ1とｅjとの内積
（ｅ1，ｅj）＝ｓ1j
である。したがって、まず変換行列の第１行目が求まった。次に第２行目であるが、まず、
【０１３０】
【数３２】
2005234994.tif 000034
【０１３１】
より、
【０１３２】
【数３３】
2005234994.tif 000035
【０１３３】
である。なお、正確には、
【０１３４】
【数３４】
2005234994.tif 000036
【０１３５】
であるが、＋の方を選んでも条件が満たされるので＋の方を選ぶことにする（以後の計算においても同様）。すでにｅ12の値は求まっているので、ｅ12の値を決めることができる。次に、ｅ2jの値を求める。
【０１３６】
【数３５】
2005234994.tif 000037
【０１３７】
であるが、すでに、ｅ12，ｅ1j，ｅ22は求まっているので、
【０１３８】
【数３６】
2005234994.tif 000038
【０１３９】
によって、ｅ2jの値を決めることができる。ここで、注意すべきことは、ｅ22≠０でなければならないということである。このことについては、後で詳しく述べるが、ここでは、この条件が満たされるという前提で説明を進める。このようにして、順に、ｅijの値を求めていくことができる。具体的には、
【０１４０】
【数３７】
2005234994.tif 000039
【０１４１】
【数３８】
2005234994.tif 000040
【０１４２】
である。
ここで、記憶量について述べておく。実数の範囲で斜交基底ベクトルが求まる場合、１つのベクトルを表すには、実数のバイト数をｗとすると、ｗｎバイトである。
【０１４３】
［１．２虚数の導入 (類似行列が正則でかつ正値でない場合)］
上の説明では、２つの点を抜かしている。このことについて説明する。それは、式（３８）において、平方根の中の値が０、または負になってしまう場合である。それぞれについて、以下説明する。
【０１４４】
（ａ）０になる場合
この場合は、それ以降、計算を進めることができない。この問題に関しては、後節の「１．３  類似行列が正則でない場合」で説明する。
【０１４５】
（ｂ）負になる場合
この場合は、ｅiiの値は虚数になってしまう。本実施の形態ではこの虚数を許す。虚数となったときの演算方式について説明する前に、どういう場合に虚数になるかについて説明しておく。
【０１４６】
以下、方式について説明する。まず、注意しておきたいのは、求めた虚数は、一般的な複素数ではなく、純虚数であるということである。また、ｅiiの値が一旦純虚数になると、同じ列の値、すなわち、ｅij（ｉ＜ｊ≦ｎ）の値は全て、純虚数になるということである。そのため、行列Ｔの各行の値は、実数か純虚数かにはっきり分かれる。ただし、０は実数であると同時に便宜的に純虚数と考えることにする。
【０１４７】
次に注意すべきことは、内積やベクトルの長さ（ノルム）、ベクトル間の距離をどう定義するかということである。通常、複素数を値として持つベクトルの内積やノルムは共役複素数を用いて定義される。すなわち、２つのベクトルを
【０１４８】
【数３９】
2005234994.tif 000041
【０１４９】
としたとき、内積は、
【０１５０】
【数４０】
2005234994.tif 000042
【０１５１】
と定義される。ここで、ａ（オーバーライン付）は複素数α＝α＋βｉの共役複素数α−βｉを表す（添え字で示されないｉは虚数を表す）。また、ベクトルｘの長さは、
【０１５２】
【数４１】
2005234994.tif 000043
【０１５３】
で、また、ベクトルｘ，ｙの間の距離は、
【０１５４】
【数４２】
2005234994.tif 000044
【０１５５】
で表される。このことによって、ベクトルの長さは必ず正または０になることが保証される。しかし、本実施の形態では、この定義を用いず、２つのベクトルの内積を
【０１５６】
【数４３】
2005234994.tif 000045
【０１５７】
と通常の実数と同じように定義する。したがって、ベクトルの長さ、２ベクトル間の距離も同様に、
【０１５８】
【数４４】
2005234994.tif 000046
【０１５９】
【数４５】
2005234994.tif 000047
【０１６０】
と定義する。このように定義する理由は、上記の共役複素数による通常の距離の定義では、条件Ｃ１，Ｃ２を同時に満たすようにすることができない場合があるのに対して、本実施の形態における距離の定義では、同時に満たすことが可能となるからである。なお、このような距離の定義の仕方は、特殊相対論で時空における距離を定義するのに使われている。
【０１６１】
このように定義することにより、ｅiiの値が０にならない限り、条件（Ｃ１）、条件（Ｃ２）、条件（Ｃ３）を同時に満たす解を求めることができる。
《虚数が現れる例（第１の例）》
ここでは、実際に虚数が現れる例を示す。今、マンセルの色立体、その中でも特に、黒、白、灰色について考える。
【０１６２】
図５は、マンセルの色立体を示す図である。マンセルの色立体１５は、色相環に現れる純色以外の色についても立体上に配し、その色の間の類似性を、その色の間の距離で表したものである。
【０１６３】
図６は、色の３要素である色相、明度、彩度との関係を示す図である。色の３要素である色相、明度、彩度との関係は図６のようになっている。すなわち、３次元空間１６の上下方向に明度が示されている。そして、上下方向の軸１７からの水平方向の距離によって彩度が示されている。さらに、上下方向の軸１７からの向きによって色相が示されている。
【０１６４】
図７は、マンセルの色立体上での色の配置を簡略化して表した図である。マンセルの色立体１５を地球に例えると、白は北極に、黒は南極、灰は中心に当たる。すなわち、これらの色は直線状に並んでいる。今、黒および白は完全に独立した特徴と考え、それに対応する斜交基底ベクトルは直交しているものと考える。すなわち、黒と白に対応する基底ベクトル間の距離は２1/2と考える。したがって、灰色と黒、および灰色と白との距離は２1/2／２である。このとき、この距離関係をそのまま反映した類似行列は、
【０１６５】
【数４６】
2005234994.tif 000048
【０１６６】
であり、この類似行列に対する斜交基底ベクトルを求めると、
【０１６７】
【数４７】
2005234994.tif 000049
【０１６８】
となり、ｅ3に純虚数が現れる。すなわち、この基底によって構成される特徴ベクトルの第３次元目の値は純虚数となる。
ここで、虚数を導入することにより、記憶量がどうなるかについて述べておく。実数の場合は、前述のように実数のバイト数をｗバイトとすると、ｗｎバイトであった。虚数を表現するときは、よく複素数が使われる。複素数のバイト数は、通常実数の倍である。したがって、複素数でベクトルを表そうとすると、２ｗｎバイトを要する。しかし、ここで述べた方法では、虚数といっても純虚数であり、また、純虚数が現れる次元も決まっている。したがって、本実施の形態では、何次元目が純虚数になるかだけをベクトルとは別に覚えておく。こうすることにより、記憶量は、類似行列が正値である場合と同様、ｗｎバイトですむ。
【０１６９】
前述の非特許文献２において、変換された後の特徴ベクトルの成分が実数であるときは、ｗｎバイトであることがわかっている。本実施の形態では、変換された後の特徴ベクトルの成分が虚数になる一般の類似行列に対しても、ｗｎバイトですむことを示した。
【０１７０】
［１．３ 類似行列が正則でない場合］
ここでは、ｅiiの値が０になる場合でも解を求めることができる方式について述べる。この方式では、斜交基底ベクトルの次元を２ｎとする。そして、斜交基底ベクトルを次のような形式とする。
【０１７１】
【数４８】
2005234994.tif 000050
【０１７２】
この方式では、ｅiiの値を最初から１とする。すなわち、
ｅii＝１  （１≦ｉ≦ｎ）
である。したがって、ｅiiは当然０とはならない。しかし、この場合、普通に考えると基底の長さは１以上になってしまい、条件（Ｃ１）を満たさないことになる。これを調節するのが、ｎ＋１行目以降のｅn+i,iの項である。これらのｅijの値は、前述の［１．１］、［１．２］と同様にして求めることができる。
【０１７３】
ここで、２ｎ次元にすることにより、記憶量がどうなるかについて述べておく。ｎ次元の場合は、虚数を導入しても前述のように実数のバイト数をｗバイトとすると、ｗｎバイトであった。２ｎ次元の場合は、次元がｎ＋１次元目から２ｎ次元目までが純虚数となる。したがって、ｎ次元の場合と同様に、複素数を使う必要はなく、２ｎ個の実数でベクトルを表現できる。したがって、必要な記憶量は、２ｎｗであり、ｎ次元の場合に比べ、２倍必要である。
【０１７４】
この方式を用いると、記憶量が余分に必要であるが、類似行列が正値、正則を問わず、全ての場合について、斜交基底を求めることができる。
なお、記憶量については、［１．２］とこの節で説明した方式を融合することにより、削減を図ることも可能である。以下、それについて説明する。
【０１７５】
［１．４  次元数の削減］
この方式は、前述の［１．２］の方式と［１．３］の方式を融合する方式である。［１．２］の方式に重点をおくか、［１．３］の方式に重点をおくかでさらに２通りの方式に分かれる。前者を最小次元方式、後者を分離方式と呼ぶことにする。前者が最小の次元ですむこと、また後者は虚数が現れる部分が、ｎ＋１行目以降に分離されていることからこう名づけた。
【０１７６】
具体的には、以下のように行う。なお、配列ａは整数を覚えておくための配列とする。
１）ｍ＝１とする。ｍは虚数になる次元を数えるためのものである。
２）ｉ＝１，２，・・・，ｎに対して以下の処理を行う。
【０１７７】
・ｅij（ｉ＜ｊ）の求め方については、［１．２］と同じである。
・ｅiiについては、最小方式と分離方式で以下のように求め方が異なる。
最小方式の場合
ｅii≠０の場合は、［１．２］の方式を用いる。
ｅii＝０になった場合はｅii＝１とする。そして、ｍ＝ｍ＋１とし、ｉの値をａ［ｍ］＝ｉとして覚えておく。
【０１７８】
分離方式の場合
【０１７９】
【数４９】
2005234994.tif 000051
【０１８０】
の値により次のようにする。
・ｓ＞０の場合は、ｅii＝（１−ｓ）1/2とする。
・ｓ≦０の場合、最小次元方式と同様、ｅii＝１とする。そして、ｍ＝ｍ＋１とし、ｉの値をａ［ｍ］＝ｉとして覚えておく。
【０１８１】
３）ｍ＞０の場合、次の処理を行う。
・斜交基底ベクトルの次元をｎ＋ｍ次元とする。そして、ｋ＝１，２，・・・，ｍに対して、
ｉ＝ａ［ｋ］
【０１８２】
【数５０】
2005234994.tif 000052
【０１８３】
【数５１】
2005234994.tif 000053
【０１８４】
を計算する。
なお、ベクトルのｎ次元目までは実数に、また、ｎ＋１次元からｎ＋ｍ次元までは、純虚数に対応する。以上をまとめて、斜交基底ベクトル は次の形をとる。
【０１８５】
まず、虚数を持たないものは、次の形をとる。
【０１８６】
【数５２】
2005234994.tif 000054
【０１８７】
また、虚数を持つ場合は以下の形をとる。
【０１８８】
【数５３】
2005234994.tif 000055
【０１８９】
以上により、斜交基底ベクトルの数がｎ（ｎは自然数）であり、斜交基底ベクトルの線形独立性がｎ次元内で保てない場合、ｎ＋１次元から２ｎ次元の範囲内の次元で斜交基底ベクトルを定義することで線形独立性を保つことができる。この方式であれば、記憶量は、（ｎ＋ｍ）ｗバイトですむ。
【０１９０】
［２  識別性の欠如への対応］
前述の識別性の欠如の問題への対応について述べる。この問題は直交基底＋ユークリッド距離方式では起きない。というのは、２つのオブジェクトが異なる場合、その間の距離は必ず正の値となり、０とはならないからである。しかし、直交基底＋二次形式距離や斜交基底＋ユークリッド距離方式では、２つのオブジェクトが異なる場合でも、それに対応するベクトルが一致してしまったり、またベクトルが異なっても、その間の距離が０になってしまう場合があるからである。ベクトルが一致してしまうのは、斜交基底ベクトルが線形独立ではないためである。また、異なるオブジェクト間の距離が０になってしまうのは、前述の解に虚数が現れる場合に起こる可能性がある。
【０１９１】
本実施の形態では、次の２つの方法で、この問題の解決を図る。
（ａ）類似行列の変形によるアプローチ
（ｂ）マルチベクトル距離によるアプローチ
（ａ）の基本的な考え方は、上で求めた類似行列を単位行列に近づけることである。また、（ｂ）は類似行列は変形せずに、解決を図る方法である。
【０１９２】
［２．１  識別性の消失］
ここで、識別性がなくなる２つの簡単な例を示す。
《線形独立でない例（第２の例）》
色相環の中から４つの色、赤（red）、黄色（yellow）、緑（green）、青（blue）について考える。それぞれこの順に、色相環の４分点に位置しているものとする。このとき、色相環における距離関係をそのまま反映した類似行列は、
【０１９３】
【数５４】
2005234994.tif 000056
【０１９４】
となる。この類似行列を満たす斜交基底ベクトルは、
【０１９５】
【数５５】
2005234994.tif 000057
【０１９６】
である。これらは、実は線形独立ではなく、本来、基底と呼べるものではない。今、補色同士の赤と青の画素をちょうど半分ずつ持っている画像に対応する特徴ベクトルｆ1と、黄と青の画素をちょうど半分ずつ持っている画像に対応する特徴ベクトルｆ2を計算すると、
【０１９７】
【数５６】
2005234994.tif 000058
【０１９８】
【数５７】
2005234994.tif 000059
【０１９９】
とともに零ベクトル、すなわち、同じベクトルになってしまう。この原因は、ｅ1，ｅ2，ｅ3，ｅ4が線形独立でないことにある。
《線形独立だが、識別性がなくなる例（第３の例）》
ここで、前述の虚数出現例で示した白黒灰の例について考える。今、白と黒の画素をそれぞれちょうど半分ずつ持っている画像の特徴ベクトルをｆ1灰色一色からなる画像の特徴ベクトルをｆ2とする。このとき、
【０２００】
【数５８】
2005234994.tif 000060
【０２０１】
【数５９】
2005234994.tif 000061
【０２０２】
【数６０】
2005234994.tif 000062
【０２０３】
である。ここで、２つの特徴ベクトル間の距離を計算すると、ｄ（ｆ1，ｆ2）2＝０となってしまう。ｅ1，ｅ2，ｅ3は線形独立であるが、識別性を持っていないのである。
識別性がなくなるというのは明らかにまずい問題である。この問題は、直交基底＋ユークリッド距離方式では生じない。この方法では基底は線形独立であり、また距離は距離空間の公理を満たしているからである。実際、線形独立性からオブジェクトが違えば、対応するベクトルも異なる。ベクトルが異なれば、距離の公理から距離が０になることはない。
【０２０４】
第２の識別性消失例で識別性がなくなる原因は、
（Ｒ１）類似行列の設定が間違っている。
（Ｒ２）二次形式距離自体の限界である。
のどちらかである。次に（Ｒ１），（Ｒ２）の各立場から解決を図る。
【０２０５】
まず（Ｒ１）の立場に立ち、二次形式距離のフレームワークの中で、この問題を改善する手段、すなわち、類似行列を変更することを試みる。
識別性と特徴間の類似性の間にはトレードオフの関係があると考えられる。直交基底＋ユークリッド距離方式は、実は斜交基底＋ユークリッド距離方式や二次形式距離の方式に含まれており、対応する類似行列は、単位行列である。したがって、類似行列を単位行列に近づければ、識別性で問題のない直交基底＋ユークリッド距離法に近づけることができる。類似行列の要素Ｓiiの値は１のまま変えない。０≦ａ＜１（ａは実数）として、ｓij ＝ａｓijとすることにより、単位行列に近づける。ａが近づける度合いを制御するためのパラメータとなる。ａ＝１の場合が、最初の状態に、また、ａ＝０の場合が、直交基底＋ユークリッド距離方式に当たる。この方法を類似行列変形法と呼ぶことにする。
【０２０６】
［２．２  類似性の消失］
二次形式距離方式や斜交基底＋ユークリッド距離方式では、特徴間の類似性は、保たれている。すなわち、単独の特徴からなると考えられるオブジェクト間の類似性は保たれている。しかし、０でない複数の特徴量から構成される特徴ベクトル間では、この類似性が失われる場合がある。この節では、この問題について論じる。まず、このような問題が生じる簡単な例を示す。
【０２０７】
《類似性が消失する例（第４の例）》
ここでは、１２色からなる色相環を考える。補色の関係にある２つの色Color1とColor2だけからなり、同じ量の画素を含む画像をColor1+Color2で表したことにする。ここで示す例を簡単に言えば、たとえば、赤＋緑、赤橙＋緑、黄＋青を考えたとき、赤＋緑は黄＋青よりも赤橙＋緑に似ていると人間には感じられる。しかし、上記のただ一つの変数ａをパラメータとする類似行列の変形を行っただけでは、斜交基底＋ユークリッド法あるいはそれと等価な二次形式距離法ではそうならず、みな同等に似たものとなってしまう。
【０２０８】
以下、詳しく説明する。各色は「虚数が現れる例（第１の例）」の場合と同様に、円を均等に１２等分する点に対応するものとする。そして、補色の画素を半分ずつ持つ画像に対応する全体特徴ベクトル、すなわち、
【０２０９】
【数６１】
2005234994.tif 000063
【０２１０】
としたとき、ｄ（ｆ1，ｆ2），（１≦ｉ＜６）とａとの関係を考える。
我々は、ｆi，ｆj間の距離にも特徴間の類似性が反映されるものと予想していた。すなわち、
【０２１１】
【数６２】
2005234994.tif 000064
【０２１２】
が成り立つものと考えていた。それも直交基底＋ユークリッド距離法に対応するａ＝０では、これらの距離は皆等しくなるものの、０＜ａ≦１の範囲では、ａが１に近いほどその距離の差は大きいと考えていた。しかし、実際に計算してみると、ａの値によらず、直交基底＋ユークリッド距離法と同じく、
【０２１３】
【数６３】
2005234994.tif 000065
【０２１４】
となる。これは、直交基底＋ユークリッド距離法における関係と同じであること、すなわち、特徴間の類似性が消失していることを意味している。このことは縮小率ａを０に近づけても変わらない。
【０２１５】
「類似性が消失する例（第４の例）」が起きる場合は、同様に複数のパラメータを使って、行列の変形を行う。このことにより、「類似性が消失する例（第４の例）」で類似性を消失するということはなくなる。
【０２１６】
図８は、ａ＝１の場合の斜交基底の様子を示した図である。この場合、ｆiは全て円の中心に対応するベクトルｃに等しくなってしまう。そして、距離が０になり、識別性も特徴間の類似性も失われてしまうのである。一方、図８のｆiは、式（６１）が示すように、２つのベクトル０．５ｅiと０．５ｅi+6を合成したベクトルであるが、この２つのベクトルを示す線分に着目すると、これらの線分は、類似性を保存している。このことが本実施の形態に適用される多面体距離（ベクトル集合間の距離）のベースとなる。
【０２１７】
［２．３  ベクトル集合間の距離による特徴空間（マルチベクトル特徴空間）］
この章では、（Ｒ２）が正しいとの仮定に基づいて、すなわち、類似行列を変更することなく、識別性や類似性がなくなるという問題を解決する手法を説明する。
【０２１８】
「類似性が消失する例（第４の例）」に示されるように、特徴ベクトルを斜交基底ベクトルから合成すると、識別性や類似性の消失という問題が起きる。しかし、ｃi≠０であるような合成される前の零ベクトルではないベクトル（すなわち、ｃi≠０であるようなｃiｅi（１≦ｉ≦ｎ））に注目すると、これらのベクトルは、特徴量に関する情報も、特徴間の類似性に関する情報も保持している。また、識別性もある。そこで、今、
【０２１９】
【数６４】
2005234994.tif 000066
【０２２０】
というベクトルの集合に注目する。こういったベクトルからなる集合をベクトル集合と呼ぶことにする。ベクトル集合の中には、同じベクトルが含まれていても構わない。その意味で、正確にはマルチ集合（マルチベクトル）である。
【０２２１】
ここで、ベクトル集合を用いた場合の有効性を概念的に理解しやすくするために、ベクトルの値を物質の質点に置き換えて説明する。マルチベクトル特徴空間ではオブジェクトが一般に複数のベクトルで表される。その複数のベクトルに対応する点に同じ質量からなる質点が置かれているものとする。このとき、それらの質点が作る一種の立体が考えられる。この立体間の距離を定義したのが、以下で定義するδ距離となる。その立体の点をいくつかのグループに分け、それぞれのグループの重心（と本質的には同等のもの）で置き換えたものが、特徴集合の近似となる。
【０２２２】
図９は、比較対象となる２つのベクトル集合を示す図である。図９では、２つのベクトル集合Ａ0＝（ａ1，ａ2，ａ3，ａ4）、Ｂ0＝（ｂ1，ｂ2，ｂ3，ｂ4）に対応する立体を表している。各点には同じ質量の質点が置かれているものとする（少なくとも特徴集合においてはそう考えられえる。この例は特徴集合の例ではないが同じ質量の点が置かれているとする）。２つの立体の重心は一般には一致しないが、この例では一致しているものとする。これらの４つの点からなる立体を次のように重心を使って２つの点からなる立体で近似する。
ａ12＝ａ1＋ａ2、ａ34＝ａ3＋ａ4、ｂ14＝ｂ1＋ｂ4、ｂ23＝ｂ2＋ｂ3
ａijはａi、ａjの重心、ｂijはｂi、ｂjの重心を表している。正確には、重心という意味では、ａi＋ａjやｂi＋ｂjを２で割るべきであるが、２で割ることを省けば本質は変わらないので、重心という言い方をすることにする。
【０２２３】
ａ1234やｂ1234についても同様に以下のように表される。
ａ1234＝ａ12＋ａ34＝ａ1＋ａ2＋ａ3＋ａ4
ｂ1234＝ｂ12＋ｂ34＝ｂ1＋ｂ2＋ｂ3＋ｂ4
この場合は元の立体をその重心で近似したことになる。そして、元々重心が一致していたので、ａ1234とｂ1234も一致する。これが識別性の欠如に当たる。
【０２２４】
そこで、本実施の形態では、マルチベクトル特徴空間のベクトル集合を合成せずに、個々のベクトルを１対１で比較することで、立体間の距離という概念を捉える。基本的な考え方は、このベクトル集合同士がどれだけ似ているかを図るため、これらの集合間に距離を定義することである。いろいろな定義の仕方が考えられえるが、以下に基本的な例を示す。
【０２２５】
《マルチベクトル間の距離計算例（第５の例）》
最初に、「類似性が消失する例（第４の例）」と同じ状況について考える。
図１０は、マルチベクトル特徴空間のベクトル集合の例を示す図である。図１０に示すように、赤＋緑それぞれ５０％ずつの画像２０に対して、赤橙＋青緑それぞれ５０％ずつの画像３０と黄＋青それぞれ５０％ずつの画像４０との距離を計算する。この場合、まず、各画像２０，３０，４０の特徴を示すマルチベクトル集合が生成される。
【０２２６】
画像２０のマルチベクトル集合は、赤の方向に長さ０．５のベクトル２１と、緑の方向に長さ０．５のベクトル２２とで構成される。画像３０のマルチベクトル集合は、赤橙の方向に長さ０．５のベクトル３１と、青緑の方向に長さ０．５のベクトル３２とで構成される。画像４０のマルチベクトル集合は、黄の方向に長さ０．５のベクトル４１と、青の方向に長さ０．５のベクトル４２とで構成される。
【０２２７】
ここで、
【０２２８】
【数６５】
2005234994.tif 000067
【０２２９】
とする。そして、ＦiとＦj（ｉ≦ｊ）との間のδ距離を、
【０２３０】
【数６６】
2005234994.tif 000068
【０２３１】
と定義する。ここで、ＭはＦiからＦjへのベクトルの１対１対応全体の集合を表す。Ｆ1とＦ2とは、それぞれｍ個のベクトルからなる。このとき、
【０２３２】
【数６７】
2005234994.tif 000069
【０２３３】
すなわち、δ（Ｆ1，Ｆ2）＝０．７３２、δ（Ｆ1，Ｆ3）＝１．４１４、δ（Ｆ1，Ｆ4）＝２、δ（Ｆ1，Ｆ5）＝１．４１４、δ（Ｆ1，Ｆ6）＝０．７３２が成り立つ。このことは、識別性が保たれ、類似性の消失の問題も解決していることを意味する。また、特徴ベクトル間の類似性ももっともなものとなっている。なお、ここで、｜ａ｜はａの絶対値を表す。
【０２３４】
図１１は、画像間のマルチベクトル距離を示す図である。これは、図１０に示す画像２０と画像３０との間のマルチベクトル距離、および画像２０と画像４０との間のマルチベクトル距離を示している。
【０２３５】
画像２０と画像３０とのδ距離を計算する場合、まず、画像２０のベクトル集合に含まれるベクトル２１と画像３０のベクトル集合に含まれるベクトル３１との距離ｄ1が計算される。同様に、ベクトル２２とベクトル３２との距離ｄ2が計算される。これらの距離ｄ1とｄ2とを加算することで、δ距離が得られる。
【０２３６】
また、画像２０と画像４０とのδ距離を計算する場合、まず、画像２０のベクトル集合に含まれるベクトル２１と画像４０のベクトル集合に含まれるベクトル４１との距離ｄ3が計算される。同様に、ベクトル２２とベクトル４２との距離ｄ4が計算される。これらの距離ｄ3とｄ4とを加算することで、δ距離が得られる。
【０２３７】
図１２は、マルチベクトル距離を用いた画像間のδ距離を示す図である。図１２に示すように、画像２０と画像３０とのδ距離は、画像２０と画像４０とのδ距離よりも近くなる。すなわち、画像２０に対して類似する画像を検索した場合、画像４０よりも画像３０の方が優先的に検出される。
【０２３８】
《線形独立でない例へのアプローチ（第６の例）》
次に、「線形独立でない例（第２の例）」への対応について考える。
図１３は、線形独立でないマルチベクトルの例を示す図である。この例では、白が５０％、黒が５０％の画像５０と、灰色が１００％の画像６０とのマルチベクトル距離を比較する。今、画像５０のベクトル集合Ｆ1と画像６０のベクトル集合Ｆ2とを
Ｆ1＝｛０．５ｅ1，０．５ｅ3｝、Ｆ2＝｛１．０ｅ2｝
とする。この例では、ｅ1は白に対応する斜交基底ベクトル、ｅ3は黒に対応する斜交基底ベクトル、ｅ2は灰色に対応する斜交基底ベクトルである。すなわち、画像５０のベクトル集合には２つのベクトル５１，５２が含まれているが、画像６０のベクトル集合には１つのベクトル６１しか含まれていない。すなわち、２つの集合の要素数が異なっている。そこで、ベクトル６１を０．５ｅ2と０．５ｅ2との２つのベクトルに分ける。
【０２３９】
図１４は、分割されたベクトルを示す図である。図１４に示すように、図１３に示されたベクトル６１が２つのベクトル６２，６３に分割されている。分割後のベクトル集合Ｆ3を次のように定義する。
Ｆ3＝｛０．５ｅ2，０．５ｅ2｝
そして、Ｆ1とＦ3との間の距離を式（６６）によって定義する。この場合、ベクトル５１とベクトル６２との距離ｄ1、およびベクトル５２とベクトル６３との距離ｄ2が加算される。すると、δ距離は正の値になり、識別性の消失の問題は解決される。δ距離の値自体も、人間の見た目による類似判断に近いものである。
【０２４０】
このベクトル集合間の距離をマルチベクトル距離と呼ぶことにする。
［２．４  特徴集合と近似］
極端な例として、
【０２４１】
【数６８】
2005234994.tif 000070
【０２４２】
で定義されるベクトル集合間のマルチベクトル距離を考えることができる。ここでは、式（６４）とは異なり、零ベクトルも含めている。この集合を特徴集合と呼ぶ。しかし、この特徴集合間のマルチベクトル距離を計算することは非常にコストがかかるものと思われる。そこで、この特徴集合をより小さいｍ（１≦ｍ＜ｎ）個のベクトルからなるベクトル集合で、近似することを考え、それをｍ−ベクトル集合と呼ぶ。以下に「類似性が消失する例（第４の例）」に基づく２−ベクトル集合の例を示す。今、
【０２４３】
【数６９】
2005234994.tif 000071
【０２４４】
とする。ここで、
【０２４５】
【数７０】
2005234994.tif 000072
【０２４６】
【数７１】
2005234994.tif 000073
【０２４７】
【数７２】
2005234994.tif 000074
【０２４８】
とする。すると、２−ベクトル集合Ａは、特徴集合Ｆを近似している。「類似性が消失する例（第４の例）」における特徴ベクトルに対応する特徴集合に対する上のＡと同様の２−ベクトル集合をＡi（１≦ｉ≦６）で表したとき、それは、「マルチベクトル間の距離計算例（第５の例）」におけるＦiと一致する。すなわち、２−ベクトル集合間の距離は、式（６７）を使って定義できる。この距離で特徴集合間の距離が近似できる。
【０２４９】
なお、従来の特徴ベクトル間の距離は、この考えに基づくと、１−ベクトル集合による近似と見なすことができる。すなわち、従来の特徴ベクトル間の拡張になっている。
この近似の方法は、斜交基底ベクトルの分割に基づいている。この例では、それらは、
Ｅ1＝｛ｅ1，ｅ2，・・・，ｅ6｝、Ｅ2＝｛ｅ7，ｅ8，・・・，ｅ12｝
という２つのグループに分割されている。ｅ1，ｅ2，・・・，ｅ6は黄色のまわりの暖色系の色であり、ｅ7，ｅ8，・・・，ｅ12は青を中心とした寒色系の色である。このように、斜交基底ベクトルは、それらの類似性に基づいて、近いもの同士まとめられるべきである。その理由は次のとおりである。識別性が消失するといった問題は、近似を使わなければ、すなわち、特徴集合間の距離を使えば、起きない。しかし、近似を使っている場合、やはり起きる可能性がある。ただし、全体にわたって起きるのではなく、部分的に起きるようにローカライズしてくれるようになるからである。上の例で言えば、Ｅ1とＥ2に渡るような識別性の消失ということは起きなくなる。
【０２５０】
次に２つのベクトル集合間の距離ついて一般的に考える。「マルチベクトル間の距離計算例（第５の例）」では、式（６６）の距離の定義でうまくいく。しかし、いつもうまくいくとは限らない。そのような例を以下に示す。
【０２５１】
《非常に類似した特徴へのアプローチ（第７の例）》
以下の２つの２−ベクトル集合について考える。
Ａ1＝｛０．７ｅ1，０．３ｅ3｝、Ａ2＝｛ｅ2，０（零ベクトル）｝
ここで、３つの斜交基底ベクトルｅ1，ｅ2，ｅ3は近接しているものとする。すなわち、それぞれ、灰色よりも少し白っぽい色、灰色、灰色より少し黒っぽい色に対応している。したがって、人間の感覚からすると、Ａ1とＡ2との距離は０に近いはずである。
【０２５２】
しかし、式（６６）と同様の方法を使うと、その距離はｄ（０．７ｅ1，ｅ2）＋ｄ（０．３ｅ3，０（零ベクトル））であり、おおよそ０．６となってしまう。したがって、２つの２−ベクトル集合間の距離を以下のように定義しなおす。
【０２５３】
まず、１つのｍ−ベクトル集合Ａ＝｛ａ1，ａ2，・・・，ａm｝の「ベクトル集合の分割」を次のように定義する。
・ベクトル集合分割の定義
Ａの各要素を次のように分割する。２つのｍ−ベクトル集合を
Ａ＝｛ａ1，ａ2，・・・，ａm｝、Ｂ＝｛ｂ1，ｂ2，・・・，ｂm｝
とする。そして、ベクトルａi，ｂi（１≦ｉ≦ｍ）をそれぞれ、次のように分割する。
ａ1＝ａ11＋ａ12＋・・・＋ａ1m
ａ2＝ａ21＋ａ22＋・・・＋ａ2m
・・・
ａm＝ａm1＋ａm2＋・・・＋ａmm
ａijは零ベクトルでも構わないし、重複していても構わない。この操作を「ベクトル集合の分割」と呼ぶことにし、ρと名づける。そして、この操作ρによって分割されたｍ2個のベクトルからなるベクトル集合を
【０２５４】
【数７３】
2005234994.tif 000075
【０２５５】
で定義する。このベクトル集合の分割方法は無数にあるが、その分割の集合をρ（Ａ）と表すことにする。
このとき、２つのｍ−ベクトル集合
Ａ＝｛ａ1，ａ2，・・・，ａm｝、Ｂ＝｛ｂ1，ｂ2，・・・，ｂm｝
間の「Ｄ距離」を次のように定義する。
【０２５６】
・Ｄ距離の定義
２つのｍ−ベクトル集合間のＤ距離を
【０２５７】
【数７４】
2005234994.tif 000076
【０２５８】
と定義する。
この定義により、「非常に類似した特徴へのアプローチ（第７の例）」の距離は０に近いものとして定義できる。
【０２５９】
ここで、ベクトルの分割方法によるＤ距離の違いを説明する。
図１５は、１つのベクトルを２等分割した例を示す図である。図１５の例では、灰色の画像８０と、画像８０の灰色よりも少し白っぽい色が５０％、画像８０の灰色より少し黒っぽい色が５０％の画像７０とが示されている。これらの画像７０，８０のベクトル集合は、以下のように表されるものとする。
Ｆ1＝｛０．７ｅ1，０．３ｅ3｝、Ｆ2＝｛０．５ｅ2，０．５ｅ2｝
すなわち、灰色１００％の画面８０の特徴を示すベクトルを２等分割している。この場合、ｄ1（０．７ｅ1，０．５ｅ2）＋ｄ2（０．３ｅ1，０．５ｅ2）＞＞０となり、人間の視覚によって感じる類似性と乖離する。
【０２６０】
図１６は、１つのベクトルを不等分割した例を示す図である。この例では、画像７０，８０のベクトル集合を、以下のように表している。
Ｆ1＝｛０．７ｅ1，０．３ｅ3｝、Ｆ2＝｛０．７ｅ2，０．３ｅ2｝
すなわち、灰色１００％の画面８０の特徴を示すベクトルを不等分割している。分割の割合は、比較対象となる画像７０のベクトルの大きさの比率と同じである。この場合、ｄ3（０．７ｅ1，０．７ｅ2）＋ｄ4（０．３ｅ3，０．３ｅ2）がほぼ０となり、人間の視覚によって感じる類似性と一致する。
【０２６１】
［２．５  Ｄ距離の近似計算］
Ｄ距離は上記の定義をそのまま適用したのでは、ベクトルの分割の仕方も無数にあり、計算量が膨大となる。ここでは、Ｄ距離を近似的に求める方式について述べる。
【０２６２】
２つのｍ−ベクトル集合をＡ＝｛ａ1，ａ2，・・・，ａm｝とＢ＝｛ｂ1，ｂ2，・・・，ｂm｝とする。この２つのｍ−ベクトル集合間のＤ距離の近似値を求めるアルゴリズムを以下に示す。以下例では、特徴量が絶対量で表された場合にも適用できるように、Ａ，Ｂの特徴量の絶対値の合計に応じた特徴ベクトルの分割を行う。そこで、Ａ，Ｂの特徴量の絶対値の合計をそれぞれ、α，βで表すことにする。すなわち、
【０２６３】
【数７５】
2005234994.tif 000077
【０２６４】
【数７６】
2005234994.tif 000078
【０２６５】
とする。特徴量が相対量であれば、αとβとは１となる。また、以下変数Ｄは求めるべきＤ距離を表すものとする。なお、以下では、零ベクトルを「ベクトル０」と表す。また、零ベクトルだけからなるベクトル集合をＯで表すことにする。たとえば、｛ベクトル０，ベクトル０，ベクトル０｝といった集合がＯである。
【０２６６】
次に、特徴集合間のＤ距離の近似計算の処理手順について説明する。
図１７は、Ｄ距離の近似計算の処理手順を示すフローチャートである。この処理は、図４に示す距離計算装置１２４で行われる処理である。
【０２６７】
［ステップＳ１１］Ａ＝ＯまたはＢ=Ｏの何れかの条件を満たすか否かが判断される。何れかの条件を満たす場合、処理がステップＳ１２に進められ、そうでなければ処理がステップＳ１５に進められる。
【０２６８】
［ステップＳ１２］Ａ＝Ｏか否かが判断される。Ａ＝Ｏであれば処理がステップＳ１３に進められ、そうでなければ処理がステップＳ１４に進められる。
［ステップＳ１３］Ａ＝Ｏの場合、Ｄ＝βと設定され、その後処理が終了する。
【０２６９】
［ステップＳ１４］Ｂ＝Ｏの場合、Ｄ＝αと設定され、その後処理が終了する。
［ステップＳ１５］Ａ≠ＯかつＢ≠Ｏの場合は、Ｄ＝０と設定される。
［ステップＳ１６］Ａ≠Ｏか否かが判断される。Ａ≠Ｏであれば、処理がステップＳ１７に進められ、Ａ＝Ｏであれば処理が終了する。すなわち、Ａ≠Ｏである間、以降のステップＳ１７〜Ｓ２０の処理が繰り返される。
【０２７０】
［ステップＳ１７］Ａに含まれる零ベクトルでないａiと、Ｂ含まれる零ベクトルでないｂj中で、（ａi，ｂj）／（｜ａi｜｜ｂj｜）が最小となるものが改めてａi，ｂjとされる。
【０２７１】
［ステップＳ１８］｜ａi｜／｜ｂj｜≧α／βの条件が満たされるか否かが判断される。この条件が満たされる場合、処理がステップＳ１９に進められる。条件が満たされない場合、処理がステップＳ２０に進められる。
【０２７２】
［ステップＳ１９］｜ａi｜／｜ｂj｜≧α／βの場合、Ｄ＝Ｄ＋ｄ（αａi／β，ｂj）とする。Ａのαiを（１−（α｜ｂj｜／β｜ａi｜））ａiで、Ｂのｂjを零ベクトルで置き換える。その後、処理がステップＳ１６に進められる。
【０２７３】
［ステップＳ２０］｜ａi｜／｜ｂj｜＜α／βの場合、Ｄ＝Ｄ＋ｄ（ａi，βｂj／α）とする。Ａのαiを零ベクトルで、Ｂのｂjを（１−（β｜ａi｜／α｜ｂj｜））ｂjで置き換える。その後、処理がステップＳ１６に進められる。
【０２７４】
このアルゴリズムの基本的な考え方は次のとおりである。すなわち、ａi，ｂjの中で、（ａi，ｂj）／（｜ａi｜｜ｂj｜）が最小となるもの（すなわち、ａiと同じ方向で長さ１のベクトルと、ｂjと同じ方向で長さ１のベクトルとが最も近いようなａi，ｂj）を選び、それぞれから、長さの比がα対βとなるようにベクトルを切り出す。その際、どちらかのベクトルが使い尽くされるようにする。こうして、切り出されたベクトル同士が対応するものとし、それらの間の距離を距離の総計に加える。一方、切り出されたベクトル分だけ、ａi，ｂjを短くする。一方は使い尽くされているので、零ベクトルとなる。対応される際、長さの比をα対βとしているので、どの対応においても、この比の関係は成り立つ。このため、Ａ，Ｂは同時にＯとなる。
【０２７５】
なお、ここでのベクトルを切り出す操作が、ベクトル集合分割の操作を決めていることになり、その対応関係が、分割されたベクトル間のδ距離における１対１の対応を決めていることになる。
【０２７６】
ａi，ｂjを選ぶとき、上記のように、それぞれの方向の長さ１のベクトルの距離が最小になるように選んでいる。すなわち、一方の特徴ベクトルの集合と他方のベクトル集合とから、最も近い方向を向いた特徴ベクトル同士を選び、それらからベクトルペアとなる部分を繰り返し切り出す処理が行われている。そのため、こうして計算された距離は、Ｄ距離に近いことが期待される。
【０２７７】
特徴集合間の近似はここで定義した距離に基づく。そして、識別性や類似性の問題は近似している限り残るが、ｍの値が大きくなるにつれて、ローカライズされる。また、従来用いられてきた特徴ベクトルは、１−ベクトル集合による近似と同じになる。すなわち、ここで定義した近似による距離は、従来の特徴ベクトル間の距離の一般化になっている。
【０２７８】
［３  検索方式］
マルチベクトル特徴空間における検索方式を説明する。なお、検索は、図４に示す検索装置１２３によって行われる。マルチベクトル特徴空間では、ベクトル集合を前もって生成しておくか、それとも検索時に生成するかによって、大きく次の２つの方式に分かれる。以下、それぞれについて述べる。
【０２７９】
（１）検索時にベクトル集合を生成する方式
前もって、ＨＤＤ１０３等の二次記憶には、画像などのオブジェクトから自動的に抽出した特徴量とオブジェクトの識別子の組を格納しておく。また、斜交基底に関する情報を格納しておく。そして、検索時に、特徴量と斜交基底からｍ−ベクトル集合を生成し、Ｄ距離を計算することにより、類似検索を行う。この検索方式を採用する場合、図４の記憶装置１１０には、特徴量とオブジェクトの識別子との組が更に格納される。
【０２８０】
この方式はベクトル集合を格納しなくてすむため、ｍが２よりも大きいときは、後述の（２）の方式に比べ二次記憶容量は少なくてすむ。ただし、検索時にベクトル集合を生成する必要がある。
【０２８１】
（２）検索前にベクトル集合を生成・格納する方式
ＨＤＤ１０３等の二次記憶には、特徴量と斜交基底から生成したｍ−ベクトル集合を格納しておく。そして、検索時にこのｍ−ベクトル集合とＤ距離を用いて類似検索を行う。本実施の形態は、（２）の検索方式に従って説明している。
【０２８２】
この方式は、ベクトル集合を格納しなければならないため、ｍが２より大きい場合は、その負担が大きくなる。
（１），（２）の方式にはこのようにトレードオフがあるが、一般には、ｍ＝１の場合は（２）を、ｍが２以上の場合は（１）を用いるのが妥当と思われる。
【０２８３】
以上のような処理を行うことで、本実施の形態では以下のような特別な効果が得られる。
・精度と性能の向上
本実施の形態によれば、マルチベクトル特徴空間により、二次形式距離よりもさらに精度を向上させることができる。
【０２８４】
・性能の向上
特徴空間の近似により、性能を向上させることができる。また、Ｄ距離を近似的に求めることにより、性能を向上させることができる。
【０２８５】
・識別性の向上
本実施の形態に従って、マルチベクトル特徴空間によりベクトルペア同士の距離を求めることにより、特徴間類似性を損なうことなく識別性を高めることができる。
【０２８６】
［４  ＥＭＤとの相違点］
ここで、前述の非特許文献３に示されるＥＭＤと上記実施の形態との相違点について説明する。大きな違いは、本実施の形態に係るマルチベクトル特徴空間が部分マッチではなく、常に全体としてのマッチであるのに対し、ＥＭＤでは、２つのシグニチャの総量（特徴量の総量）が異なる場合は、部分マッチとなるという点である。
【０２８７】
画像のヒストグラムの場合、相対量（所定の色が全体に占める割合により特徴量が示される）による場合と、絶対量（所定の色のピクセル数により特徴量が示される）による場合が考えられる。相対量の場合は、全体マッチと考えられるが、絶対量で特徴量である画素数の総量が異なる場合、ＥＭＤでは部分マッチと考えられる。
【０２８８】
一方、本実施の形態に係る方式では、比較対象となる２つのベクトル集合それぞれに含まれる特徴ベクトルの数を常に一致させている。すなわち、少なくとも、特徴ベクトル数が少ないベクトル集合内の一部の特徴ベクトルが分割される。その結果、全ての特徴ベクトルが１対１のベクトルペアに使用され、距離の計算が行われる。これは、特徴量の総量が異なっても、部分マッチではなく全体として比較できることを意味する。
【０２８９】
常に全体マッチができることは、特徴量の絶対量に大きな意味がある場合に特に有効である。たとえば、文書では、絶対量による特徴量の全体マッチが意味を持つ。すなわち、文書の類似検索では、単語ごとの出現頻度あるいはそれに重みをつけたものが特徴量として用いられる。したがって、次元数は単語の数に等しくなる。ただし、単語は全ての単語を対象とするわけではなく、文書の特徴をよく表すようなものが選ばれる。したがって、「これ」、「する」など頻繁に使われるような単語は除かれる。それでも、通常千から１万程度の次元になる。文書では、単語の出現頻度は、後で述べる画像の画素が相対的であるのに比べ、絶対的である。ある単語が頻繁に使われるということはそれ自体が意味を持つ。
【０２９０】
たとえば、ある単語が文書Ｕで１度しか現れないのに、文書Ｖでは１０回現れたとすれば、その単語がその文書Ｖでは重要である、あるいはその文書Ｖを頻度の少ないことばに比べ特徴づけることを意味する。それに対し、文書Ｕでは、１回しか触れられておらず、この単語がそれほど重要でない、あるいはその文書Ｕをそれほど特徴づけていないことを意味する。したがって、文書の場合には、特徴量は絶対量（単語の出現数）で表される。
【０２９１】
本実施の形態の方式であれば、文書の類似検索のように特徴量の総量が異なる（絶対量が意味を持つ）場合にも、部分的な比較ではなく全体として比較できる。全体を比較することで、全体としての類似性を的確に判別できる。
【０２９２】
また、画像の類似検索では、たとえば、黒、白それぞれ１０００画素ずつの画像Ｘと、黒が１０００画素の画像Ｙとを比較する場合を考える。ＥＭＤでは、特徴量の部分的な比較となり、画像Ｘの一部の特徴量（１０００画素の黒）と画像Ｙの全体の特徴量（１０００画素の黒）とが一致する。
【０２９３】
一方、本実施の形態では、図１７のフローチャートに示すように、特徴量の絶対量の比（｜α｜／｜β｜）に応じて、ベクトルペアを構成するそれぞれの特徴ベクトルの長さを縮めている（縮められた分の長さのベクトルが分割されている）。そのため、元の特徴量が絶対量で示されていても、全体としての比較が可能となる。
【０２９４】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、マルチメディアデータ検索装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記録装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ(Digital Versatile Disc)、ＤＶＤ−ＲＡＭ(Random Access Memory)、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)、ＣＤ−Ｒ(Recordable)／ＲＷ(ReWritable)などがある。光磁気記録媒体には、ＭＯ(Magneto-Optical disk)などがある。
【０２９５】
プログラムを流通させる場合には、たとえば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０２９６】
プログラムを実行するコンピュータは、たとえば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０２９７】
（付記１）  マルチメディアデータ間の類似関係を判定するための類似度判定プログラムにおいて、
コンピュータを、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、
２つの比較対象マルチメディアデータを入力する入力手段、
前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、
前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、
前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出する類似度算出手段、
前記類似度算出手段で算出された類似度を出力する出力手段、
として機能させることを特徴とする類似度判定プログラム。
【０２９８】
（付記２）  前記マルチメディアデータは、画像データであることを特徴とする付記１記載の類似度判定プログラム。
（付記３）  前記斜交基底ベクトル記憶手段には、前記属性として複数の代表色が定義されており、
前記ベクトル集合生成手段は、前記画像データで表現される画像の色と前記代表色との対応関係が予め定義されており、前記代表色に対応する色が前記画像に占める割合を、前記属性の前記特徴量とすることを特徴とする付記２記載の類似度判定プログラム。
【０２９９】
（付記４）  前記ベクトルペア生成手段は、前記ベクトル集合の前記特徴ベクトルを複数のグループに分類し、グループ毎に合成することで、前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させることを特徴とする付記１記載の類似度判定プログラム。
【０３００】
（付記５）  前記ベクトルペア生成手段は、一方の前記特徴ベクトルの集合と他方の前記ベクトル集合とから、最も近い方向を向いた特徴ベクトル同士を選び、それらから前記ベクトルペアとなる部分を繰り返し切り出すことを特徴とする付記１記載の類似度判定プログラム。
【０３０１】
（付記６）  前記斜交基底ベクトル記憶手段は、前記斜交基底ベクトルの数がｎ（ｎは自然数）であり、前記斜交基底ベクトルの線形独立性がｎ次元内で保てない場合、ｎ＋１次元から２ｎ次元の範囲内の次元で線形独立性を保った前記斜交基底ベクトルが格納されていることを特徴とする付記１記載の類似度判定プログラム。
【０３０２】
（付記７）  前記ベクトルペア生成手段は、前記特徴ベクトルを分割することで、前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させることを特徴とする付記１記載の類似度判定プログラム。
【０３０３】
（付記８）  前記ベクトルペア生成手段は、前記ベクトル集合それぞれから前記特徴ベクトルを抽出し、抽出した２つの前記特徴ベクトルから、前記比較対象マルチメディアデータそれぞれの特徴量の合計値の比に応じた長さのベクトルに分割することを特徴とする付記７記載の類似度判定プログラム。
【０３０４】
（付記９）  前記ベクトルペア生成手段は、前記ベクトル集合に含まれる前記特徴ベクトルの数をｍ（ｍは自然数）に一致させたとき、各特徴ベクトルをｍ個に細分化し、細分化されたベクトル同士のベクトルペアを生成することを特徴とする付記１記載の類似度判定プログラム。
【０３０５】
（付記１０）  マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索プログラムにおいて、
コンピュータを、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、
複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合を記憶するベクトル集合記憶手段、
検索条件マルチメディアデータを入力する入力手段、
前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、
前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、
前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出する類似度算出手段、
前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する出力手段、
として機能させることを特徴とするマルチメディアデータ検索プログラム。
【０３０６】
（付記１１）  マルチメディアデータ間の類似関係を判定するための類似度判定方法において、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルが斜交基底ベクトル記憶手段に記憶されており、
入力手段が、２つの比較対象マルチメディアデータを入力し、
ベクトル集合生成手段が、前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とし、
ベクトルペア生成手段が、前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成し、
ベクトル間距離算出手段が、前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算し、
類似度算出手段が、前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出し、
出力手段が、前記類似度算出手段で算出された類似度を出力する、
ことを特徴とする類似度判定方法。
【０３０７】
（付記１２）  マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索方法において、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルが斜交基底ベクトル記憶手段に記憶されており、
複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合がベクトル集合記憶手段に記憶されており、
入力手段が、検索条件マルチメディアデータを入力し、
ベクトル集合生成手段が、前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とし、
ベクトルペア生成手段が、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成し、
ベクトル間距離算出手段が、前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算し、
類似度算出手段が、前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出し、
出力手段が、前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する、
ことを特徴とするマルチメディアデータ検索方法。
【０３０８】
（付記１３）  マルチメディアデータ間の類似関係を判定するための類似度判定装置において、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段と、
２つの比較対象マルチメディアデータを入力する入力手段と、
前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段と、
前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段と、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段と、
前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出する類似度算出手段と、
前記類似度算出手段で算出された類似度を出力する出力手段と、
を有することを特徴とする類似度判定装置。
【０３０９】
（付記１４）  マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索装置において、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段と、
複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合を記憶するベクトル集合記憶手段と、
検索条件マルチメディアデータを入力する入力手段と、
前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段と、
前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段と、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段と、
前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出する類似度算出手段と、
前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する出力手段と、
を有することを特徴とするマルチメディアデータ検索装置。
【０３１０】
（付記１５）  マルチメディアデータ間の類似関係を判定するための類似度判定プログラムを記録したコンピュータ読み取り可能な記録媒体において、
コンピュータを、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、
２つの比較対象マルチメディアデータを入力する入力手段、
前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、
前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、
前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出する類似度算出手段、
前記類似度算出手段で算出された類似度を出力する出力手段、
として機能させることを特徴とする類似度判定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【０３１１】
（付記１６）  マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索プログラムを記録したコンピュータ読み取り可能な記録媒体において、
コンピュータを、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、
複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合を記憶するベクトル集合記憶手段、
検索条件マルチメディアデータを入力する入力手段、
前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、
前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、
前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出する類似度算出手段、
前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する出力手段、
として機能させることを特徴とするマルチメディアデータ検索プログラムを記録したコンピュータ読み取り可能な記録媒体。
【図面の簡単な説明】
【０３１２】
【図１】実施の形態に適用される発明の概念図である。
【図２】画像データの類似度判断例を示す模式図である。
【図３】マルチメディアデータ検索装置のハードウェア構成例を示す図である。
【図４】マルチメディアデータ検索装置の機能構成図である。
【図５】マンセルの色立体を示す図である。
【図６】色の３要素である色相、明度、彩度との関係を示す図である。
【図７】マンセルの色立体上での色の配置を簡略化して表した図である。
【図８】ａ＝１の場合の斜交基底の様子を示した図である。
【図９】比較対象となる２つのベクトル集合を示す図である。
【図１０】マルチベクトル特徴空間のベクトル集合の例を示す図である。
【図１１】画像間のマルチベクトル距離を示す図である。
【図１２】マルチベクトル距離を用いた画像間のδ距離を示す図である。
【図１３】線形独立でないマルチベクトルの例を示す図である。
【図１４】分割されたベクトルを示す図である。
【図１５】１つのベクトルを２等分割した例を示す図である。
【図１６】１つのベクトルを不等分割した例を示す図である。
【図１７】Ｄ距離の近似計算の処理手順を示すフローチャートである。
【図１８】色ヒストグラムによる画像の特徴量を示す図である。
【図１９】３つの画像に対応する３点を表した図である。
【図２０】色相環を示す図である。
【図２１】赤、赤橙、緑の単一色からなる画像それぞれの特徴量を示す図である。
【図２２】斜交基底の例を示す図である。
【図２３】直交座標と斜交座標の関係を説明する図である。
【図２４】従来技術の問題点を整理した図である。
【図２５】色相環における特徴間の類似性を斜交基底に忠実に反映した図である。
【符号の説明】
【０３１３】
１  斜交基底ベクトル記憶手段
１ａ  斜交基底ベクトル
２  入力手段
２ａ，２ｂ  マルチメディアデータ
３  ベクトル集合生成手段
４  ベクトルペア生成手段
５  ベクトル間距離算出手段
６  類似度算出手段
７  類似度
８  出力手段
【図１】
2005234994.tif 000079
【図２】
2005234994.tif 000080
【図３】
2005234994.tif 000081
【図４】
2005234994.tif 000082
【図５】
2005234994.tif 000083
【図６】
2005234994.tif 000084
【図７】
2005234994.tif 000085
【図８】
2005234994.tif 000086
【図９】
2005234994.tif 000087
【図１０】
2005234994.tif 000088
【図１１】
2005234994.tif 000089
【図１２】
2005234994.tif 000090
【図１３】
2005234994.tif 000091
【図１４】
2005234994.tif 000092
【図１５】
2005234994.tif 000093
【図１６】
2005234994.tif 000094
【図１７】
2005234994.tif 000095
【図１８】
2005234994.tif 000096
【図１９】
2005234994.tif 000097
【図２０】
2005234994.tif 000098
【図２１】
2005234994.tif 000099
【図２２】
2005234994.tif 000100
【図２３】
2005234994.tif 000101
【図２４】
2005234994.tif 000102
【図２５】
2005234994.tif 000103
【手続補正書】
【提出日】平成16年12月2日(2004.12.2)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は類似度判定プログラム、マルチメディアデータ検索プログラム、類似度判定方法、および類似度判定装置に関し、特にマルチメディアデータ間の類似度を判定するための類似度判定プログラム、マルチメディアデータ検索プログラム、類似度判定方法、および類似度判定装置に関する。
【背景技術】
【０００２】
計算機の分野では、従来キーワードなどの文字列や数値による検索が行われてきた。しかし、最近では、インターネットやディジタルカメラ、携帯電話などの普及に伴い、画像や音声、文書などのマルメディアに対する検索に関心が高まっている。
【０００３】
マルチメディアデータの検索方法として、注釈やキーワードによる検索がある。この検索は、次のように行われる。画像を検索する場合、その画像に注釈と呼ばれるキーワード群を付加する。キーワードは、たとえば「沖縄で撮影された真っ青な海」といったテキストや、「沖縄、海」といった単語である。各画像は、付加されたキーワードに基づいてキーワード検索が行われてきた。しかし、この注釈による方法には２つの問題点がある。
【０００４】
１つ目の問題点は、人手で注釈を付加しようとすると人的コストがかかることである。しかも、画像の急増により、注釈付けはさらに難しくなってきている。２つ目の問題点は、画像の特徴を注釈だけでは完全に記述できないことである。実際に、画像には、色や形、模様など多くの特徴があり、それらを完全に文字で特徴づけることはできない。
【０００５】
そこで、マルチメディアデータの特徴を自動抽出し、特徴空間、色ヒストグラム、特徴量を用いて検索を行う方法がある。この検索方法を適用できるマルチメディアデータとして、画像データがある。画像の類似検索では、色や形などの特徴を特徴量と呼ばれる数値として人手を介さず、自動的に抽出する。色の場合、よく用いられる代表的な方法として色ヒストグラムという方法がある。ヒストグラムは柱状グラフを意味する。
【０００６】
色ヒストグラムでは、ピクセル（画素）をｎ色（ｎは自然数）に分類し、その色ごとの画素数を抽出する。そして、画像全体の画素数に対するその色の画素数の割合で、各色の特徴を表現する。この割合のように各特徴を表す量を特徴量と呼ぶ。分類する色の数ｎとしては、たとえば６４といったある程度大きな数が用いられる。
【０００７】
今、簡単のために、まず、ｎ＝３として、色も赤、緑、青のいわゆる三原色とした場合、画像の特徴量を３次元の特徴空間内の座標で表すことができる。
図１８は、色ヒストグラムによる画像の特徴量を示す図である。赤、緑、青の特徴量を示す座標軸が互いに直交するように設けられている。ここで、ある画像の赤、緑、青のそれぞれの特徴量（全ピクセル数に対するそれぞれの色の割合）がそれぞれ、０．２，０．５，０．３とする。すると、画像は座標が
【０００８】
【数１】
2005234994.tif 000104
【０００９】
である点Ａとして表される。
図１９は、３つの画像に対応する３点を表した図である。それぞれの座標は、
【００１０】
【数２】
2005234994.tif 000105
【００１１】
【数３】
2005234994.tif 000106
【００１２】
【数４】
2005234994.tif 000107
【００１３】
である。この場合、点Ｂは赤を含んでおらず、また点Ｃは緑も青も含んでいない画像を表している。そして、３つの点の間の距離を考え、より近いものが類似したものと考える。図からもわかるように、点Ａは、点Ｃよりも点Ｂに近いので、点Ｂに類似していると考える。したがって、点Ａに最も類似した画像を検索した場合は、点Ｂが検出される。
【００１４】
このように、画像に対して特徴空間の点を１対１に対応させ、距離が近いものほど似ているものとするのが、類似検索の基本的な考え方である。
このような類似検索は、様々な分野で利用されている。特徴空間を用いた類似検索は、映像を含めた画像の場合に限らず、音声や文書の分野でも広く用いられている。音声の類似検索であれば、あるイントロを入力すると、それに対応する曲を検索するといった場合である。
【００１５】
文書の類似検索では、文書の特徴量として、その文書に含まれる単語の出現頻度と、全文書数をその単語が含まれる文書の数で割った数の対数とを掛けたものがよく使われる。この場合、特徴空間の次元は、母体として考える単語の数になり、特徴空間は非常に高次元となる。このように、特徴量による類似検索は多様なマルチメディアデータで、広い範囲に渡って用いられている。
【００１６】
以上述べたように、類似検索では、マルチメディアデータである画像や文書といった対象物（以下、オブジェクトと呼ぶ）の特徴を特徴空間と呼ばれる多次元空間上のベクトル（点）に対応させる。点の座標が、対応するオブジェクトの特徴量である。特徴量は、一般には浮動小数点数で表されることが多い。すなわち、一般的には、実数値を座標とするｎ次元空間である。
【００１７】
なお、以降では、基底、特徴ベクトルということばをよく使う。まず、このことばについて説明しておく。
［基底、正規直交基底］
よく知られているように、ユークリッド空間を含むいわゆるベクトル空間内の任意のベクトルは、次元数をｎとすると、基底ベクトルと呼ばれるｎ個のベクトルを用いて表現することができる。３次元のユークリッド空間であれば、
【００１８】
【数５】
2005234994.tif 000108
【００１９】
【数６】
2005234994.tif 000109
【００２０】
【数７】
2005234994.tif 000110
【００２１】
という３つのベクトルｅ1，ｅ2，ｅ3が基底ベクトルである。この基底ベクトルを用いて、任意のベクトルνを、
【００２２】
【数８】
2005234994.tif 000111
【００２３】
という、いわゆる線形結合と呼ばれる形で表現することができる。このｎ個の基底ベクトルの組を基底と呼ぶ。このように、座標系に対して、基底が対応しており、逆に基底をもとに座標系を考えることができる。
【００２４】
この例のｅ1，ｅ2，ｅ3は（正規）直交基底と呼ばれる。直交とは、ｅi，ｅj（ｉ，ｊは自然数：ｉ≠ｊ）が互いに直交していることを意味する。また正規とは、各基底ベクトルの長さがすべて１であることを意味する。
【００２５】
［特徴ベクトル］
特徴空間の次元をｎとし、その基底ベクトルをｅ1，ｅ2，ｅ3，・・・，ｅn、オブジェクトの特徴量をｃ1，ｃ2，ｃ3，・・・，ｃnとしたとき、これらの線形結合として表されるベクトル
【００２６】
【数９】
2005234994.tif 000112
【００２７】
をそのオブジェクトに対応する全体特徴ベクトルと呼ぶことにする。全体特徴ベクトルはオブジェクトの全体的な特徴を表すものであり、オブジェクト間の距離はこの全体特徴ベクトル間の距離として測られる。一方、前述のように、特徴量はオブジェクトの各特徴を表す量である。
【００２８】
［直交基底＋ユークリッド距離］
最も基本的な方式は、ｎ個の特徴量をｎ次元のユークリッド空間の点として、
【００２９】
【数１０】
2005234994.tif 000113
【００３０】
と表す方式である。そして、２点間の距離は通常のユークリッド距離として表す。すなわち、もう１点を
【００３１】
【数１１】
2005234994.tif 000114
【００３２】
とした時、２点間の距離ｄは、
【００３３】
【数１２】
2005234994.tif 000115
【００３４】
で与えられる。ただし、この方式は、以下に述べるような問題を持っている。今、色として、１２色を考える。このとき１２の色は、色相環で表される。
図２０は、色相環を示す図である。色相環は、複数の色を隣に似た色がくるように環状にならべたものである。最も似ていないのが、その色の真向かいにある色で補色と呼ばれている（なお、図２０で示した色相環は説明を分かり易くするため、実際のものを簡略化したものであり、色の名前も通常のものとは異なるので注意されたい。たとえば、緑青は、緑がかった青、黄緑は黄色がかった緑、緑黄は緑がかった黄色、黄橙は黄色がかった橙、赤橙は赤みがかった橙を示している）。この場合、画像は色ヒストグラムによる方法で１２次元の特徴空間として表される。今、説明をわかりやすくするために、３つの赤、赤橙、緑の単一色からなる画像を考える。それぞれの画像は、座標では、
【００３５】
【数１３】
2005234994.tif 000116
【００３６】
【数１４】
2005234994.tif 000117
【００３７】
【数１５】
2005234994.tif 000118
【００３８】
と表される。
図２１は、赤、赤橙、緑の単一色からなる画像それぞれの特徴量を示す図である。なお、この図２１では、他の色に関する座標軸は省略している。前述の距離を計算する式を用いて、各画像の間の距離を計算すると、図２１からもわかるように、
赤・緑間＝２1/2
赤・赤橙間＝２1/2
赤橙・緑間＝２1/2
となる（２1/2は、２の１／２乗を示す）。すなわち、どの２つの画像間の距離も同じになり、数値上は同様に似ているものと見なされる。しかし、実際人間が見た場合、青緑と赤は似ていないが、赤と赤橙はよく似ているように見える。すなわち、ここで用いた特徴空間での点の取り方が、人間が感じる類似性を反映していないことになる。
【００３９】
このことは画像ばかりでなく、マルチメディア一般に言える。以下はテキストの例である。
［文書の例］
文書を特徴空間で表す際、次のような１つだけの単語からなる３つの簡単な文書を考えてみる（通常は当然もっと多くの単語を含んでいるが説明のため１つにしている）。
文書１＝｛総理大臣｝
文書２＝｛首相｝
文書３＝｛テニス｝
いま、母体となる単語として、｛総理大臣、首相、テニス｝というものを考えているとする。ｉ次元目の特徴量はｉ番目の単語が現れる数とする。このとき、各文書はベクトルとして、
【００４０】
【数１６】
2005234994.tif 000119
【００４１】
【数１７】
2005234994.tif 000120
【００４２】
【数１８】
2005234994.tif 000121
【００４３】
と表される。この場合、各文書間の距離を計算すると、画像の場合と同様に、
文書１・文書２間＝２1/2
文書２・文書３間＝２1/2
文書３・文書１間＝２1/2
となり、どの文書も同等に似ていることになる。しかし、首相と総理大臣は、同じ意味であり、画像の場合と同様、人間が感じる類似性を反映していないことになる。
【００４４】
［直交基底＋二次形式距離］
「直交基底＋ユークリッド距離」の問題点を解決するためにいろいろな手法が提案されている。基本的には、直交基底を用いるが、２点ｘ，ｙ間の距離を表す距離関数ｄ（ｘ，ｙ）として前述のユークリッド距離を使うのではなく、特徴間の類似性を反映された距離関数を用いるものである。
【００４５】
「直交基底＋ユークリッド距離」で用いたユークリッド距離は計算が容易である。一方、ここで用いられる距離関数は一般に複雑で、計算時間を要する場合が多く、それを解決することが一つの課題となる。
【００４６】
以下、この方式の中でも代表的な二次形式距離について説明する。
二次形式距離においてはベクトルｘを
【００４７】
【数１９】
2005234994.tif 000122
【００４８】
としたとき、その長さ‖ｘ‖を行列Ｓを用いて、
【００４９】
【数２０】
2005234994.tif 000123
【００５０】
で定義する（tｘはベクトルｘの転置ベクトルである。すなわち、ｘが列ベクトルであれば、それを行ベクトルにしたものを意味する）。したがって、ベクトルｘ，ｙ間の距離ｄ（ｘ，ｙ）は、その差ベクトルの長さとして
【００５１】
【数２１】
2005234994.tif 000124
【００５２】
で求められる。行列Ｓは特徴間の類似性を表す行列で、類似行列と呼ぶことにする。行列の要素Ｓijは類似度と呼ばれ、ｉ番目の特徴とｊ番目の特徴の間の類似している度合いを表す。Ｓが単位行列の場合は、通常のユークリッド距離になる。その意味で、この二次形式距離はユークリッド距離の一般化になっている。この方式は米国ＩＢＭ社のＱＢＩＣ（Query By Image Content）（商標）システムで使用されている（たとえば、非特許文献１参照）。
【００５３】
［斜交基底＋ユークリッド距離］
斜交座標を利用した斜交基底による類似度検索も考えられている。数学的にはよく知られているように、斜交基底ベクトルの間の角度は９０°である必要はない。このように、直交するとは限らない斜交基底ベクトルに基づく座標は斜交座標と呼ばれ、数学、物理をはじめ多くの技術分野で広く使われている。この基底を斜交基底と呼ぶことにする。
【００５４】
図２２は、斜交基底の例を示す図である。図２２には、図２１の直交基底を赤と赤橙が類似していることを考慮して、赤橙に対応する斜交基底ベクトルを赤に近づけた斜交基底が表されている。
【００５５】
図２３は、直交座標と斜交座標の関係を説明する図である。今、点Ｐは直交座標では、〔８，７〕と表される。ｅ1，ｅ2を斜交基底ベクトルとする基底を考える。それぞれの直交座標は、
【００５６】
【数２２】
2005234994.tif 000125
【００５７】
【数２３】
2005234994.tif 000126
【００５８】
である。点Ｐを斜交座標で表す場合には、まず、Ｐを通り斜交基底ベクトルｅ2に平行な線と、斜交基底ベクトルｅ1の延長とが交わる点Ａ，およびＰを通り斜交基底ベクトルｅ1に平行な線と、斜交基底ベクトルｅ2の延長とが交わる点Ｂを求める。今後、一般に点Ｘから点ＹへのベクトルをベクトルＸＹと書くことにする。すると、よく知られているように、ベクトルＯＰは、２つのベクトルＯＡ、ベクトルＯＢの和として、ベクトルＯＰ＝ベクトルＯＡ＋ベクトルＯＢと書ける。ベクトルＯＡ＝３ｅ1，ベクトルＯＢ＝２ｅ2であるから、結局、
ベクトルＯＰ＝３ｅ1＋２ｅ2と表される。ここで、ｅ1，ｅ2の係数３，２からできる
【００５９】
【数２４】
2005234994.tif 000127
【００６０】
が点Ｐの斜交座標である。点Ｐの斜交座標と直交座標の間には、
【００６１】
【数２５】
2005234994.tif 000128
【００６２】
という関係がある。ここで、この式の最後は、行列とベクトルの積を表している。この行列を(斜交座標から直交座標への)特徴ベクトル変換行列と呼ぶことにする。この行列をＴとすると、この行列は、上記の例からもわかるように、ｅ1，ｅ2を順に並べることによって、作ることができる。すなわち、Ｔ＝（ｅ1  ｅ2）である。
【００６３】
斜交基底方式の基本的な考え方は、類似性を斜交基底ベクトル間の距離に反映させることである。距離関数はユークリッド距離をそのまま用いる。このことにより、距離の計算が容易になるというメリットがある。また、この方式による２つのオブジェクト間の距離は、二次形式距離と基本的には同じになる。すなわち、精度の面からは両方式は基本的には同等である。ただし、斜交基底の方式で必要な記憶量は、二次形式距離のほぼ半分でよい。記憶量はまた処理スピードにも影響する。その点が斜交基底による方式の利点である。
【００６４】
斜交基底の原型となるアイデアでは、斜交基底による線形結合ではなく、上記の行列Ｔによって直交座標で表された特徴ベクトルを変換して新たな特徴ベクトルを作るという方法が用いられている（非特許文献２参照）。
【００６５】
また、斜交基底を用いた方式については、以下の特許出願をしている。
「画像データの類似検索装置および該類似検索装置における類似判定方法」出願番号：特願２００３−１７２２１７（出願日：平成１５年６月１７日）
また、Earth Mover’s Distance（ＥＭＤ）という類似画像検索技術がある。以下、簡単にこの技術について説明する。
【００６６】
ＥＭＤは、複数の点の間の距離に基づいて画像間の類似度を判断する。この距離の定義を以下、土盛りと穴の比喩を使って簡単に説明することにする。この距離は運搬問題(transportation problem)の解に基づく。それぞれ画像などに対応するシグニチャ(signature)と呼ばれるｘ，ｙを
【００６７】
【数２６】
2005234994.tif 000129
【００６８】
とする。ｘが土盛りの集合に対応し、ｙが穴の集合に対応する。ｍ（ｍは自然数）とｎ（ｎは自然数）は異なっていても構わない。この柔軟性がＥＭＤの特徴の一つである。ｐi、ｑjは任意の距離が定義されている空間内の点とする。各点ｐiには体積がｘiの土が盛られ、各点ｑjには容積がｙjの穴が掘られているとする。土の総体積は穴全部を埋めるのに十分あるものとする。ｄijをｐi,ｑj間の距離、ｆijをｐi,からｑjへ運ばれる土の量とする。このとき、全部の穴を埋めるためのコスト
【００６９】
【数２７】
2005234994.tif 000130
【００７０】
を最小にするｆijを求め、ｘ，ｙ間のＥＭＤを
【００７１】
【数２８】
2005234994.tif 000131
【００７２】
と定義する。分母は正規化のためのものであり、総量が少ないシグニチャが選ばれやすくするのを防ぐ。下記の非特許文献３では、画像の色とテキスチャ（模様）にＥＭＤが適用されている。また、２つのシグニチャの総量が異なる場合は、部分マッチに対応する。この距離は２つの色ヒストグラムの場合とは異なり、ｍ，ｎが任意に指定できるという柔軟性を持ち、距離の下限の計算が容易である（非特許文献３参照）。
【非特許文献１】James Hafner, et al.,Efficient Color Histogram Indexing for Quadratic Form Distance Functions,IEEE Trans. Pattern Anl. Machine Intell. 17(7), pp.729-736, (1995)
【非特許文献２】J.S.N. Jean,A New Distance Measure for Binary Images,Proc. IEEE ICASSP '90, April3-6 (1990); Paper#: M5.19
【非特許文献３】Yossi Rubner, et al., A Metric for Distribution with Applications to Image Databases, Proc. IEEE Intl. Conf. On Computer Vision, pp.59-66, (1998)
【発明の開示】
【発明が解決しようとする課題】
【００７３】
しかし、従来の技術では、識別性が欠如していることが問題となる。
図２４は、ＥＭＤを除く従来技術の問題点を整理した図である。図２４の傾向で、似たものを棄却とあるのは、似ているにも関わらず、似ていないと判断する傾向を意味する。この傾向に該当する方式が丸印（○）で示されている。この傾向は、前述のように、直交基底＋ユークリッド距離方式に見られる。
【００７４】
一方、似ていないものを選択というのは、似ていないにも関わらず似ていると判断する傾向を意味している。この傾向に該当する方式が丸印（○）で示されている。この傾向は、特徴間の類似性を導入した、直交基底＋二次形式距離、および斜交基底＋ユークリッド距離の２つの方式に見られる。これらの方式では、極端な場合には、全く違うものを同じものとしてしまう。このことを「識別性の欠如」と呼ぶことにする。この解決がこの発明の一つの目的である。
【００７５】
図２５は、色相環における特徴間の類似性を斜交基底に忠実に反映した図である。ここで、赤と緑の２色だけからなり、しかもそれぞれ同じ量だけ（赤が５０％、緑が５０％）含む画像と、同様に黄色と青だけからなり、それぞれ同じ量だけ含む（黄が５０％、青が５０％）画像の特徴ベクトルは、それぞれ零ベクトルとなってしまう。すなわち、色としては全く異なるのに、類似検索では、全く同じものとして検索されてしまうことになる。この原因は、これら１２個のベクトルが線形独立ではないことにある。したがって、上でｅ1，ｅ2，ｅ3，・・・を基底と言ったが、本来は数学的には基底とは言えない。ただし、こういう場合も基底と呼ぶことにする。
【００７６】
図２４の説明に戻り、識別性の欠如と性能維持との観点により、各方式の利点と欠点とを整理する。図２４では、特徴間類似性、識別性、計算量、記憶量が、各方式に関して示されている。特徴間類似性は、特徴間の類似、非類似の関係が反映されるか否かを示している。識別性は、類似しないオブジェクトを正しく識別できるか否かを示している。計算量は、計算の処理数が少ないか否かを示している。記憶量は、必要なメモリ容量が少ないか否かを示している。それぞれの特性が肯定的であれば丸印（○）、否定的であればばつ印（×）、どちらでもなければ三角印（△）が示されている。
【００７７】
図２４に示すように、特性間の類似性が反映され、且つ良好な識別性を有する方式はない。ここで、「斜交基底＋ユークリッド距離」については、識別性を除いて、良好な結果が得られる。すなわち、「斜交基底＋ユークリッド距離」の現在の性能を損なわずに、識別性を高めることが望まれる。
【００７８】
なお、ＥＭＤでは、２つのシグニチャの総量（特徴量の総数）が異なる場合は、部分マッチとなる。前述の説明と同様に土盛りの集合と穴の集合とで例えれば、全ての土が穴に埋められた場合、埋められていない穴が残っていても、比較処理は終了する。そのため、一方のオブジェクトの特徴が、他方のオブジェクトの特徴に対して部分的に類似していれば、それらのオブジェクト全体で非類似であっても、類似しているものと判断されてしまう。すなわち、比較されるオブジェクト間の特徴量の総数が異なる場合には、部分マッチができるというメリットがある反面、全体としての類似性を問題とする場合、全体として似ていないものを選択する可能性がある（識別性が損なわれる）。
【００７９】
本発明はこのような点に鑑みてなされたものであり、マルチメディアデータ間の全体比較による類似、非類似の判断における識別性を高めた類似度判定プログラム、マルチメディアデータ検索プログラム、類似度判定方法、および類似度判定装置を提供することを目的とする。
【課題を解決するための手段】
【００８０】
本発明では上記課題を解決するために、図１に示すような類似度判定プログラムが提供される。本発明に係る類似度判定プログラムは、マルチメディアデータ間の類似関係を判定するためのものである。この類似度判定プログラムを実行するコンピュータは、図１に示す機能を有する。
【００８１】
斜交基底ベクトル記憶手段１は、マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトル１ａを記憶する、入力手段２は、２つの比較対象マルチメディアデータ２ａ，２ｂを入力する。ベクトル集合生成手段３は、入力手段２で入力された比較対象マルチメディアデータ２ａ，２ｂそれぞれを解析し、属性に応じた情報の含有度を示す特徴量を決定し、属性毎に特徴量を斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合３ａ，３ｂとする。ベクトルペア生成手段４は、比較対象マルチメディアデータ２ａ，２ｂそれぞれのベクトル集合３ａ，３ｂに含まれる特徴ベクトルの数を一致させ、ベクトル集合３ａ，３ｂそれぞれに含まれる特徴ベクトル同士を１対１で対応付けてベクトルペアを生成する。ベクトル間距離算出手段５は、ベクトルペア生成手段４で生成されたベクトルペア毎に、ベクトルペアに含まれる特徴ベクトル間の類似度を示す距離を計算する。類似度算出手段６は、ベクトル間距離算出手段５で計算された距離を合算し、比較対象マルチメディアデータ間の類似度７を算出する。出力手段８は、類似度算出手段で算出された類似度７を出力する。
【００８２】
このような類似度判定プログラムをコンピュータに実行させると、コンピュータ上で、入力手段２により、２つの比較対象マルチメディアデータ２ａ，２ｂが入力される。次に、ベクトル集合生成手段３により、入力手段２で入力された比較対象マルチメディアデータ２ａ，２ｂそれぞれが解析され、属性に応じた情報の含有度を示す特徴量が決定され、属性毎に特徴量を斜交基底ベクトルに乗算して特徴ベクトルが生成され、ベクトル集合３ａ，３ｂが構成される。次に、ベクトルペア生成手段４により、比較対象マルチメディアデータ２ａ，２ｂそれぞれのベクトル集合３ａ，３ｂから特徴ベクトルが１つずつ抽出され、ベクトルペアが生成される。次に、ベクトル間距離算出手段５により、ベクトルペア生成手段４で生成されたベクトルペア毎に、ベクトルペアに含まれる特徴ベクトル間の類似度を示す距離が計算される。次に、類似度算出手段６により、ベクトル間距離算出手段５で計算された距離が合算され、比較対象マルチメディアデータ間の類似度７が算出される。そして、出力手段８により、類似度算出手段で算出された類似度７が出力される。
【００８３】
また、上記課題を解決するために、マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索プログラムにおいて、コンピュータを、前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合を記憶するベクトル集合記憶手段、検索条件マルチメディアデータを入力する入力手段、前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出する類似度算出手段、前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する出力手段、として機能させることを特徴とするマルチメディアデータ検索プログラムが提供される。
【００８４】
このようなマルチメディアデータ検索プログラムをコンピュータに実行させると、コンピュータ上で、入力手段により、検索条件マルチメディアデータが入力される。次に、ベクトル集合生成手段により、前記入力手段で入力された前記検索条件マルチメディアデータが解析され、前記属性に応じた情報の含有度を示す特徴量が決定され、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルが生成され、ベクトル集合とされる。次に、ベクトルペア生成手段により、前記検索条件マルチメディアデータと、前記検索対象マルチメディアデータとのそれぞれの前記ベクトル集合から前記特徴ベクトルが１つずつ抽出され、ベクトルペアが生成される。次に、ベクトル間距離算出手段により、前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離が計算される。次に、類似度算出手段により、前記ベクトル間距離算出手段で計算された前記距離が前記検索対象マルチメディアデータ毎に合算され、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度が算出される。そして、出力手段により、前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報が出力される。
【発明の効果】
【００８５】
本発明では、マルチメディアデータの特徴を複数の特徴ベクトルで表し、比較対象のマルチメディアデータそれぞれの特徴ベクトルを１対１に対応付けたベクトルペア間の距離を合算することで、マルチメディアデータの類似度を判定するようにした。これにより、マルチメディアデータ間の識別性を損なわずに高精度な類似度を算出することができる。
【発明を実施するための最良の形態】
【００８６】
以下、本発明の実施の形態を図面を参照して説明する。
まず、実施の形態に適用される発明の概要について説明し、その後、実施の形態の具体的な内容を説明する。
【００８７】
図１は、実施の形態に適用される発明の概念図である。本発明は、斜交基底ベクトル記憶手段１、入力手段２、ベクトル集合生成手段３、ベクトルペア生成手段４、ベクトル間距離算出手段５、類似度算出手段６、および出力手段８を有している。
【００８８】
斜交基底ベクトル記憶手段１は、マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトル１ａを記憶する。たとえば、マルチメディアデータが画像データの場合、属性として複数の代表色が定義される。代表色は、色相環を構成する色を適用することができる。その場合、たとえば、代表色の位置を指し示す長さ１のベクトルが斜交基底ベクトル１ａとして定義される。
【００８９】
入力手段２は、２つの比較対象マルチメディアデータ２ａ，２ｂを入力する。たとえば、キーボード等の入力装置を介してユーザによって指定された比較対象マルチメディアデータ２ａ，２ｂをベクトル集合生成手段３に対して入力する。
【００９０】
ベクトル集合生成手段３は、入力手段２で入力された比較対象マルチメディアデータ２ａ，２ｂそれぞれを解析し、属性に応じた情報の含有度を示す特徴量を決定する。次に、ベクトル集合生成手段３は、属性毎に特徴量を斜交基底ベクトルに乗算して特徴ベクトルを生成する。そして、ベクトル集合生成手段３は、生成した特徴ベクトルを比較対象マルチメディアデータ２ａ，２ｂ毎にグループ化し、各グループをベクトル集合３ａ，３ｂとする。
【００９１】
たとえば、マルチメディアデータが画像データの場合、ベクトル集合生成手段３は、画像データで表現される画像の色と代表色との対応関係を予め定義しておく。そして、ベクトル集合生成手段３は、代表色に対応する色が画像に占める割合を、属性の特徴量とする。
【００９２】
ベクトルペア生成手段４は、比較対象マルチメディアデータ２ａ，２ｂそれぞれのベクトル集合３ａ，３ｂから特徴ベクトルを１つずつ抽出して、ベクトルペアを生成する。たとえば、ベクトルペア生成手段４は、一方の特徴ベクトルの集合から特徴ベクトルを抽出し、他方のベクトル集合から、先に抽出された特徴ベクトルに最も近い方向を向いている特徴ベクトルを抽出して、ベクトルペアを生成する。２つの特徴ベクトルの向きの近さは、たとえば、２つの特徴ベクトルの長さを１に正規化して内積を計算することで見積もることができる。
【００９３】
また、ベクトルペア生成手段４は、２つのベクトル集合３ａ，３ｂそれぞれに含まれる特徴ベクトルの数が不一致の場合、それぞれの数を一致させる。たとえば、数が少ない方のベクトル集合に含まれる特徴ベクトルを分割することで数を一致させる。特徴ベクトル数が一致すれば、全ての特徴ベクトルを用いて類似度７の計算を行うことができる。すなわち、一部だけの比較ではなく、全体としての比較が常に行われる。なお、ある特徴ベクトルを分割する際には、たとえば、ペアとなる他の特徴ベクトルと同じ長さに分割する。
【００９４】
ベクトル間距離算出手段５は、ベクトルペア生成手段４で生成されたベクトルペア毎に、ベクトルペアに含まれる特徴ベクトル間の類似度を示す距離を計算する。
類似度算出手段６は、ベクトル間距離算出手段５で計算された距離を合算し、比較対象マルチメディアデータ間の類似度７を算出する。
【００９５】
出力手段８は、類似度算出手段で算出された類似度７を出力する。たとえば、出力手段８は、算出された類似度７の値を画面表示させたり、ハードディスク装置等に保存したりする。
【００９６】
このような構成に基づいて、以下の処理が行われる。まず、入力手段２により、２つの比較対象マルチメディアデータ２ａ，２ｂが入力される。次に、ベクトル集合生成手段３により、入力手段２で入力された比較対象マルチメディアデータ２ａ，２ｂそれぞれが解析され、属性に応じた情報の含有度を示す特徴量が決定され、属性毎に特徴量を斜交基底ベクトルに乗算して特徴ベクトルが生成され、ベクトル集合３ａ，３ｂが構成される。次に、ベクトルペア生成手段４により、比較対象マルチメディアデータ２ａ，２ｂそれぞれのベクトル集合３ａ，３ｂから特徴ベクトルが１つずつ抽出され、ベクトルペアが生成される。次に、ベクトル間距離算出手段５により、ベクトルペア生成手段４で生成されたベクトルペア毎に、ベクトルペアに含まれる特徴ベクトル間の類似度を示す距離が計算される。次に、類似度算出手段６により、ベクトル間距離算出手段５で計算された距離が合算され、比較対象マルチメディアデータ間の類似度７が算出される。そして、出力手段８により、類似度算出手段６で算出された類似度７が出力される。
【００９７】
図２は、画像データの類似度判断例を示す模式図である。たとえば、斜交基底ベクトルとして、色相環９ａの赤を示すベクトルｅ1、赤橙を示すベクトルｅ2、黄橙を示すベクトルｅ3、黄を示すベクトルｅ4、緑黄を示すベクトルｅ5、黄緑を示すベクトルｅ6、緑を示すベクトルｅ7、青緑を示すベクトルｅ8、緑青を示すベクトルｅ9、青を示すベクトルｅ10、青紫を示すベクトルｅ11、赤紫を示すベクトルｅ12が定義されているものとする。
【００９８】
ここで、比較対象の２つの画像データ９ｂ，９ｃが入力された場合を考える。ベクトル集合生成手段３には、画像データ９ｂ，９ｃを構成する画素の表示可能色の全てについて、色相環９ａのどの色に近いのかを示す対応関係が定義されている。そして、ベクトル集合生成手段３は、色相環９ａの色毎に、対応する色が画像データ９ｂ，９ｃそれぞれの画像内に占める割合を計算する。図２の例では、画像データ９ｂは、赤が５０％、緑が５０％である。また、画像データ９ｃは、赤橙が５０％、青緑が５０％である。
【００９９】
ベクトル集合生成手段３は、画像データ９ｂ，９ｃ毎に、ベクトル集合９ｄ，９ｅを生成する。図２の例では、画像データ９ｂに対応するベクトル集合９ｄには、０．５ｅ1と０．５ｅ7とが特徴ベクトルとして含まれる。また、画像データ９ｃに対応するベクトル集合９ｅには、０．５ｅ2と０．５ｅ8とが特徴ベクトルとして含まれる。
【０１００】
次に、ベクトルペア生成手段４によって、ベクトルペアが生成される。たとえば、ベクトルペア生成手段４は、ベクトル集合９ｄから特徴ベクトル“０．５ｅ1”を取り出す。そして、ベクトルペア生成手段４は、他方のベクトル集合９ｅから、取り出した特徴ベクトルに最も近い方向を向いた特徴ベクトル“０．５ｅ2”を取り出す。そして、ベクトルペア生成手段４は、取り出した２つの特徴ベクトルにより、ベクトルペアを生成する。同様にして、特徴ベクトル“０．５ｅ7”と“０．５ｅ8”とのベクトルペアが生成される。
【０１０１】
ベクトル間距離算出手段５は、ベクトルペア毎に、特徴ベクトル間の距離ｄ1、ｄ2を算出する。そして、類似度算出手段６は、特徴ベクトル間の距離ｄ1、ｄ2を合算することで、類似度９ｆを算出する。
【０１０２】
このように、比較対象のマルチメディアデータそれぞれの特徴ベクトルで生成されたベクトルペア間の距離を合算することで、マルチメディアデータの類似度を判定するようにした。これにより、マルチメディアデータ間の識別性を損なわずに効率的に類似度を算出することができる。
【０１０３】
しかも、マルチメディアデータの特徴をベクトルで表すため、ベクトルの方向によって類似する他のベクトルを容易に識別することができ、ベクトルペアの生成に係る処理負荷が少なくてすむ。
【０１０４】
図３は、マルチメディアデータ検索装置のハードウェア構成例を示す図である。マルチメディアデータ検索装置１００は、ＣＰＵ(Central Processing Unit)１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０７を介してＲＡＭ(Random Access Memory)１０２、ハードディスクドライブ（ＨＤＤ:Hard Disk Drive）１０３、グラフィック処理装置１０４、入力インタフェース１０５、および通信インタフェース１０６が接続されている。
【０１０５】
ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ(Operating System)のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に必要な各種データが格納される。ＨＤＤ１０３には、ＯＳやアプリケーションプログラムが格納される。
【０１０６】
グラフィック処理装置１０４には、モニタ１１が接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１１の画面に表示させる。入力インタフェース１０５には、キーボード１２とマウス１３とが接続されている。入力インタフェース１０５は、キーボード１２やマウス１３から送られてくる信号を、バス１０７を介してＣＰＵ１０１に送信する。
【０１０７】
通信インタフェース１０６は、ネットワーク１０に接続されている。通信インタフェース１０６は、ネットワーク１０を介して、他のコンピュータとの間でデータの送受信を行う。
【０１０８】
以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。
図４は、マルチメディアデータ検索装置の機能構成図である。マルチメディアデータ検索装置１００の機能は、記憶装置１１０と類似検索装置１２０とに大別される。
【０１０９】
記憶装置１１０には、画像ファイル群１１１およびベクトル集合１１２が格納される。画像ファイル群１１１は、比較対象とされる複数の画像データである。画像ファイル群１１１は、検索開始前に予め記憶装置１１０に格納される。ベクトル集合１１２は、画像の特徴を示す特徴ベクトルの集合である。ベクトル集合１１２は、画像ファイル群１１１内の画像毎に生成される。
【０１１０】
類似検索装置１２０は、生成装置１２１、検索装置１２３、および距離計算装置１２４を有する。
生成装置１２１は、記憶装置１１０内の画像ファイル群に未処理の画像ファイルが追加されたとき、および検索装置１２３から比較目的の画像ファイルを渡されたとき、該当する画像ファイルの特徴を示すベクトル集合を生成する。ベクトル集合の生成は、特徴量抽出装置１２１ａとベクトル集合生成装置１２１ｂとによって行われる。
【０１１１】
特徴量抽出装置１２１ａは、処理対象の画像ファイルを取得し、その画像ファイルで示される画像の特徴量を、予め規定された属性毎に抽出する。予め規定された属性とは、たとえば所定の色である。色の属性毎の特徴量を抽出する場合、特徴量抽出装置１２１ａには、画像ファイルで表現可能な色が、属性として指定色（代表色）のどれに類似しているかが予め定義されている。次に、特徴量抽出装置１２１ａは、画像ファイルで表現される画像内の色を、代表色に分類する。そして、特徴量抽出装置１２１ａは、各代表色に対応する領域が画像内に占める割合を、その代表色に対応する属性の特徴量とする。特徴量抽出装置１２１ａは、抽出した特徴量をＲＡＭ１０２等に一時的に格納する。
【０１１２】
ベクトル集合生成装置１２１ｂには、予め斜交基底ベクトルが定義されている。斜交基底ベクトルは、画像ファイルの特徴量を表す属性毎に定義されている。ベクトル集合生成装置１２１ｂは、特徴量抽出装置１２１ａが抽出した特徴量をメモリ１０２から取得し、その特徴量を対応する属性の斜交基底ベクトルに乗算し、特徴ベクトルとする。特徴量抽出装置１２１ａで抽出された特徴量毎の特徴ベクトルの生成が完了すると、ベクトル集合生成装置１２１ｂは、それらの特徴ベクトルの集合（ベクトル集合）を生成する。
【０１１３】
処理対象の画像ファイルが記憶装置１１０から取得された場合、ベクトル集合生成装置１２１ｂは、生成されたベクトル集合１１２を、処理対象の画像ファイルに関連付けて記憶装置１１０に格納する。処理対象の画像ファイルが検索装置１２３から渡された場合、ベクトル集合生成装置１２１ｂは、生成されたベクトル集合１１２を、検索装置１２３に渡す。
【０１１４】
検索装置１２３は、比較目的の画像ファイルの入力を受け付け、その画像ファイルに類似する画像ファイルを記憶装置１１０内の画像ファイル群１１１から検索する。具体的には、検索装置１２３は、入力された画像ファイルを生成装置１２１に渡し、生成装置からベクトル集合を受け取る。次に、検索装置１２３は、記憶装置１１０内の画像ファイル毎のベクトル集合１１２を順次取得する。検索装置１２３は、比較目的の画像ファイルのベクトル集合と記憶装置１１０から取得したベクトル集合１１２とを距離計算装置１２４に渡す。すると、距離計算装置１２４においてベクトル集合間の距離が計算され、検索装置１２３に渡される。
【０１１５】
検索装置１２３は、記憶装置１１０内の各画像ファイルに対応するベクトル集合と、比較目的の画像ファイルのベクトル集合とから画像ファイル間の距離を認識する。検索装置１２３は、比較目的の画像ファイルに対して距離が近い画像ファイルほど類似していると判断し、上位の所定数の画像ファイル（またはその画像ファイルの識別情報）を、検索結果として出力する。
【０１１６】
距離計算装置１２４は、比較対象となっている２つの画像ファイルそれぞれに対応するベクトル集合を検索装置１２３から受け取ると、それらのベクトル集合間の距離を計算する。具体的には、距離計算装置１２４は、入力された２つのベクトル集合それぞれに含まれる特徴ベクトルを１対１で対応付け、複数のベクトルペアを生成する。距離計算装置１２４は、生成したベクトルペア間の距離を算出する。そして、距離計算装置１２４は、各ベクトルペア間の距離を合算して、ベクトル集合間の距離とする。この距離は、画像ファイル間の類似度を示す情報であり、類似度が高いほど距離を示す値が小さくなる。距離計算装置１２４は、算出した距離を検索装置１２３に渡す。
【０１１７】
このような類似検索装置１２０によれば、ユーザにより比較目的となる画像ファイルが入力されると、その画像ファイルが検索装置１２３から生成装置１２１に渡される。生成装置１２１では、渡された画像ファイルのベクトル集合が生成され、検索装置１２３に渡される。すると、検索装置１２３により、記憶装置１１０からベクトル集合１１２が抽出され、抽出したベクトル集合と比較目的の画像ファイルのベクトル集合との距離が距離計算装置１２４で計算される。そして、検索装置１２３により、距離の値が小さいベクトル集合１１２に対応する画像ファイルが類似する画像ファイルとして出力される。
【０１１８】
以下、図４に示すマルチメディアデータ検索装置１００における処理内容を詳細に説明する。
［１  類似行列から斜交基底を求める方式］
マルチメディアデータ検索装置１００では、予め斜交基底を定義しておく必要がある。斜交基底は、類似行列から算出することができる。以下、類似行列からいかに斜交基底を求めるかについて述べる。
【０１１９】
なお、以下で使う用語について説明しておく。正方行列とは、行数と列の数が等しい行列である。正則行列とは、逆行列を持つ正方行列である。正値とは、正方行列の固有値が全て正である場合、その行列を指す。
【０１２０】
［１．１  類似行列が正値である場合］
求めるべき斜交基底を、ｅ1，ｅ2，・・・，ｅnとする。このとき、
【０１２１】
【数２９】
2005234994.tif 000132
【０１２２】
と一般性を失うことなく置くことができる。したがって、特徴量を成分とするベクトルから特徴ベクトルへの変換行列Ｔは、
【０１２３】
【数３０】
2005234994.tif 000133
【０１２４】
である。今、類似行列を
【０１２５】
【数３１】
2005234994.tif 000134
【０１２６】
とする。このとき、斜交基底の満たすべき条件は、以下の４つの条件である。
・条件（Ｃ１）：‖ｅi‖＝１    （１＜ｉ≦ｎ）
・条件（Ｃ２）：（ｅi，ｅj）＝ｓij    （１＜ｉ≦ｊ≦ｎ）
・条件（Ｃ３）：ｅ1，ｅ2，・・・，ｅnは線形独立
・条件（Ｃ４）：全体特徴ベクトル「ｆ＝ｃ1ｅ1＋ｃ2ｅ2＋・・・＋ｃnｅn」によって表されるオブジェクト間の類似度が人間の感覚に合っている。
【０１２７】
なお、条件（Ｃ２）の左辺は、ベクトルの内積を示している。また、条件（Ｃ３）は、ベクトル集合同士で比較する場合の絶対的な条件ではない。すなわち、ベクトル集合によって比較を行えば、線形独立でない斜交基底ベクトルを用いても識別性を獲得することができる。ただし、斜交基底ベクトルが線形独立である方が良好な識別性が得られるため、本実施の形態では条件（Ｃ３）を満たす斜交基底ベクトルを用いるものとする。
【０１２８】
条件（Ｃ４）は人間の主観が入るので評価が難しいが、類似検索における最終目標は、この条件を満たすことである。それに対して、条件（Ｃ１）〜条件（Ｃ３）は数学的な条件で、成り立つかどうかがはっきりしている。ここでは、条件（Ｃ４）を考慮しつつ、まず、条件（Ｃ１）から条件（Ｃ３）の条件を満たす解を求める方法について説明する。
【０１２９】
まず、条件（Ｃ１）より‖ｅ1‖＝１であり、したがって、ｅ11＝１である。このことと条件（Ｃ２）とにより、ｅ1とｅjとの内積
（ｅ1，ｅj）＝ｓ1j
である。したがって、まず変換行列の第１行目が求まった。次に第２行目であるが、まず、
【０１３０】
【数３２】
2005234994.tif 000135
【０１３１】
より、
【０１３２】
【数３３】
2005234994.tif 000136
【０１３３】
である。なお、正確には、
【０１３４】
【数３４】
2005234994.tif 000137
【０１３５】
であるが、＋の方を選んでも条件が満たされるので＋の方を選ぶことにする（以後の計算においても同様）。すでにｅ12の値は求まっているので、ｅ22の値を決めることができる。次に、ｅ2jの値を求める。
【０１３６】
【数３５】
2005234994.tif 000138
【０１３７】
であるが、すでに、ｅ12，ｅ1j，ｅ22は求まっているので、
【０１３８】
【数３６】
2005234994.tif 000139
【０１３９】
によって、ｅ2jの値を決めることができる。ここで、注意すべきことは、ｅ22≠０でなければならないということである。このことについては、後で詳しく述べるが、ここでは、この条件が満たされるという前提で説明を進める。このようにして、順に、ｅijの値を求めていくことができる。具体的には、
【０１４０】
【数３７】
2005234994.tif 000140
【０１４１】
【数３８】
2005234994.tif 000141
【０１４２】
である。
ここで、記憶量について述べておく。実数の範囲で斜交基底ベクトルが求まる場合、１つのベクトルを表すには、実数のバイト数をｗとすると、ｗｎバイトである。
【０１４３】
［１．２虚数の導入 (類似行列が正則でかつ正値でない場合)］
上の説明では、２つの点を抜かしている。このことについて説明する。それは、式（３８）において、平方根の中の値が０、または負になってしまう場合である。それぞれについて、以下説明する。
【０１４４】
（ａ）０になる場合
この場合は、それ以降、計算を進めることができない。この問題に関しては、後節の「１．３  類似行列が正則でない場合」で説明する。
【０１４５】
（ｂ）負になる場合
この場合は、ｅiiの値は虚数になってしまう。本実施の形態ではこの虚数を許す。虚数となったときの演算方式について説明した後に、どういう場合に虚数になるかについて説明しておく。
【０１４６】
以下、方式について説明する。まず、注意しておきたいのは、求めた虚数は、一般的な複素数ではなく、純虚数であるということである。また、ｅiiの値が一旦純虚数になると、同じ行の値、すなわち、ｅij（ｉ＜ｊ≦ｎ）の値は全て、純虚数になるということである。そのため、行列Ｔの各行の値は、実数か純虚数かにはっきり分かれる。ただし、０は実数であると同時に便宜的に純虚数と考えることにする。
【０１４７】
次に注意すべきことは、内積やベクトルの長さ（ノルム）、ベクトル間の距離をどう定義するかということである。通常、複素数を値として持つベクトルの内積やノルムは共役複素数を用いて定義される。すなわち、２つのベクトルを
【０１４８】
【数３９】
2005234994.tif 000142
【０１４９】
としたとき、内積は、
【０１５０】
【数４０】
2005234994.tif 000143
【０１５１】
と定義される。ここで、ａ（オーバーライン付）は複素数α＝α＋βｉの共役複素数α−βｉを表す（添え字で示されないｉは虚数を表す）。また、ベクトルｘの長さは、
【０１５２】
【数４１】
2005234994.tif 000144
【０１５３】
で、また、ベクトルｘ，ｙの間の距離は、
【０１５４】
【数４２】
2005234994.tif 000145
【０１５５】
で表される。このことによって、ベクトルの長さは必ず正または０になることが保証される。しかし、本実施の形態では、この定義を用いず、２つのベクトルの内積を
【０１５６】
【数４３】
2005234994.tif 000146
【０１５７】
と通常の実数と同じように定義する。したがって、ベクトルの長さ、２ベクトル間の距離も同様に、
【０１５８】
【数４４】
2005234994.tif 000147
【０１５９】
【数４５】
2005234994.tif 000148
【０１６０】
と定義する。このように定義する理由は、上記の共役複素数による通常の距離の定義では、条件Ｃ１，Ｃ２を同時に満たすようにすることができない場合があるのに対して、本実施の形態における距離の定義では、同時に満たすことが可能となるからである。なお、このような距離の定義の仕方は、特殊相対論で時空における距離を定義するのに使われている。
【０１６１】
このように定義することにより、ｅiiの値が０にならない限り、条件（Ｃ１）、条件（Ｃ２）、条件（Ｃ３）を同時に満たす解を求めることができる。
《虚数が現れる例（第１の例）》
ここでは、実際に虚数が現れる例を示す。今、マンセルの色立体、その中でも特に、黒、白、灰色について考える。
【０１６２】
図５は、マンセルの色立体を示す図である。マンセルの色立体１５は、色相環に現れる純色以外の色についても立体上に配し、その色の間の類似性を、その色の間の距離で表したものである。
【０１６３】
図６は、色の３要素である色相、明度、彩度との関係を示す図である。色の３要素である色相、明度、彩度との関係は図６のようになっている。すなわち、３次元空間１６の上下方向に明度が示されている。そして、上下方向の軸１７からの水平方向の距離によって彩度が示されている。さらに、上下方向の軸１７からの向きによって色相が示されている。
【０１６４】
図７は、マンセルの色立体上での色の配置を簡略化して表した図である。マンセルの色立体１５を地球に例えると、白は北極に、黒は南極、灰は中心に当たる。すなわち、これらの色は直線状に並んでいる。今、黒および白は完全に独立した特徴と考え、それに対応する斜交基底ベクトルは直交しているものと考える。すなわち、黒と白に対応する基底ベクトル間の距離は２1/2と考える。したがって、灰色と黒、および灰色と白との距離は２1/2／２である。このとき、この距離関係をそのまま反映した類似行列は、
【０１６５】
【数４６】
2005234994.tif 000149
【０１６６】
であり、この類似行列に対する斜交基底ベクトルを求めると、
【０１６７】
【数４７】
2005234994.tif 000150
【０１６８】
となり、ｅ3に純虚数が現れる。すなわち、この基底によって構成される特徴ベクトルの第３次元目の値は純虚数となる。
ここで、虚数を導入することにより、記憶量がどうなるかについて述べておく。実数の場合は、前述のように実数のバイト数をｗバイトとすると、ｗｎバイトであった。虚数を表現するときは、よく複素数が使われる。複素数のバイト数は、通常実数の倍である。したがって、複素数でベクトルを表そうとすると、２ｗｎバイトを要する。しかし、ここで述べた方法では、虚数といっても純虚数であり、また、純虚数が現れる次元も決まっている。したがって、本実施の形態では、何次元目が純虚数になるかだけをベクトルとは別に覚えておく。こうすることにより、記憶量は、類似行列が正値である場合と同様、ｗｎバイトですむ。
【０１６９】
前述の非特許文献２において、変換された後の特徴ベクトルの成分が実数であるときは、ｗｎバイトであることがわかっている。本実施の形態では、変換された後の特徴ベクトルの成分が虚数になる一般の類似行列に対しても、ｗｎバイトですむことを示した。
【０１７０】
［１．３ 類似行列が正則でない場合］
ここでは、ｅiiの値が０になる場合でも解を求めることができる方式について述べる。この方式では、斜交基底ベクトルの次元を２ｎとする。そして、斜交基底ベクトルを次のような形式とする。
【０１７１】
【数４８】
2005234994.tif 000151
【０１７２】
この方式では、ｅiiの値を最初から１とする。すなわち、
ｅii＝１  （１≦ｉ≦ｎ）
である。したがって、ｅiiは当然０とはならない。しかし、この場合、普通に考えると基底の長さは１以上になってしまい、条件（Ｃ１）を満たさないことになる。これを調節するのが、ｎ＋１行目以降のｅn+i,iの項である。これらのｅijの値は、前述の［１．１］、［１．２］と同様にして求めることができる。
【０１７３】
ここで、２ｎ次元にすることにより、記憶量がどうなるかについて述べておく。ｎ次元の場合は、虚数を導入しても前述のように実数のバイト数をｗバイトとすると、ｗｎバイトであった。２ｎ次元の場合は、次元がｎ＋１次元目から２ｎ次元目までが純虚数となる。したがって、ｎ次元の場合と同様に、複素数を使う必要はなく、２ｎ個の実数でベクトルを表現できる。したがって、必要な記憶量は、２ｎｗであり、ｎ次元の場合に比べ、２倍必要である。
【０１７４】
この方式を用いると、記憶量が余分に必要であるが、類似行列が正値、正則を問わず、全ての場合について、斜交基底を求めることができる。
なお、記憶量については、［１．２］とこの節で説明した方式を融合することにより、削減を図ることも可能である。以下、それについて説明する。
【０１７５】
［１．４  次元数の削減］
この方式は、前述の［１．２］の方式と［１．３］の方式を融合する方式である。［１．２］の方式に重点をおくか、［１．３］の方式に重点をおくかでさらに２通りの方式に分かれる。前者を最小次元方式、後者を分離方式と呼ぶことにする。前者が最小の次元ですむこと、また後者は虚数が現れる部分が、ｎ＋１行目以降に分離されていることからこう名づけた。
【０１７６】
具体的には、以下のように行う。なお、配列ａは整数を覚えておくための配列とする。
１）ｍ＝１とする。ｍは虚数になる次元を数えるためのものである。
２）ｉ＝１，２，・・・，ｎに対して以下の処理を行う。
【０１７７】
・ｅij（ｉ＜ｊ）の求め方については、［１．２］と同じである。
・ｅiiについては、最小次元方式と分離方式で以下のように求め方が異なる。
最小次元方式の場合
ｅii≠０の場合は、［１．２］の方式を用いる。
ｅii＝０になった場合はｅii＝１とする。そして、ｍ＝ｍ＋１とし、ｉの値をａ［ｍ］＝ｉとして覚えておく。
【０１７８】
分離方式の場合
【０１７９】
【数４９】
2005234994.tif 000152
【０１８０】
の値により次のようにする。
・ｓ＞０の場合は、ｅii＝（１−ｓ）1/2とする。
・ｓ≦０の場合、最小次元方式と同様、ｅii＝１とする。そして、ｍ＝ｍ＋１とし、ｉの値をａ［ｍ］＝ｉとして覚えておく。
【０１８１】
３）ｍ＞０の場合、次の処理を行う。
・斜交基底ベクトルの次元をｎ＋ｍ次元とする。そして、ｋ＝１，２，・・・，ｍに対して、
ｉ＝ａ［ｋ］
【０１８２】
【数５０】
2005234994.tif 000153
【０１８３】
【数５１】
2005234994.tif 000154
【０１８４】
を計算する。
なお、ベクトルのｎ次元目までは実数に、また、ｎ＋１次元からｎ＋ｍ次元までは、純虚数に対応する。以上をまとめて、斜交基底ベクトルは次の形をとる。
【０１８５】
まず、虚数を持たないものは、次の形をとる。
【０１８６】
【数５２】
2005234994.tif 000155
【０１８７】
また、虚数を持つ場合は以下の形をとる。
【０１８８】
【数５３】
2005234994.tif 000156
【０１８９】
以上により、斜交基底ベクトルの数がｎ（ｎは自然数）であり、斜交基底ベクトルの線形独立性がｎ次元内で保てない場合、ｎ＋１次元から２ｎ次元の範囲内の次元で斜交基底ベクトルを定義することで線形独立性を保つことができる。この方式であれば、記憶量は、（ｎ＋ｍ）ｗバイトですむ。
【０１９０】
［２  識別性の欠如への対応］
前述の識別性の欠如の問題への対応について述べる。この問題は直交基底＋ユークリッド距離方式では起きない。というのは、２つのオブジェクトが異なる場合、その間の距離は必ず正の値となり、０とはならないからである。しかし、直交基底＋二次形式距離や斜交基底＋ユークリッド距離方式では、２つのオブジェクトが異なる場合でも、それに対応するベクトルが一致してしまったり、またベクトルが異なっても、その間の距離が０になってしまう場合があるからである。ベクトルが一致してしまうのは、斜交基底ベクトルが線形独立ではないためである。また、異なるオブジェクト間の距離が０になってしまうのは、前述の解に虚数が現れる場合に起こる可能性がある。
【０１９１】
本実施の形態では、次の２つの方法で、この問題の解決を図る。
（ａ）類似行列の変形によるアプローチ
（ｂ）マルチベクトル距離によるアプローチ
（ａ）の基本的な考え方は、上で求めた類似行列を単位行列に近づけることである。また、（ｂ）は類似行列は変形せずに、解決を図る方法である。
【０１９２】
［２．１  識別性の消失］
ここで、識別性がなくなる２つの簡単な例を示す。
《線形独立でない例（第２の例）》
色相環の中から４つの色、赤（red）、黄色（yellow）、緑（green）、青（blue）について考える。それぞれこの順に、色相環の４分点に位置しているものとする。このとき、色相環における距離関係をそのまま反映した類似行列は、
【０１９３】
【数５４】
2005234994.tif 000157
【０１９４】
となる。この類似行列を満たす斜交基底ベクトルは、
【０１９５】
【数５５】
2005234994.tif 000158
【０１９６】
である。これらは、実は線形独立ではなく、本来、基底と呼べるものではない。今、補色同士の赤と緑の画素をちょうど半分ずつ持っている画像に対応する特徴ベクトルｆ1と、黄と青の画素をちょうど半分ずつ持っている画像に対応する特徴ベクトルｆ2を計算すると、
【０１９７】
【数５６】
2005234994.tif 000159
【０１９８】
【数５７】
2005234994.tif 000160
【０１９９】
とともに零ベクトル、すなわち、同じベクトルになってしまう。この原因は、ｅ1，ｅ2，ｅ3，ｅ4が線形独立でないことにある。
《線形独立だが、識別性がなくなる例（第３の例）》
ここで、前述の虚数出現例で示した白黒灰の例について考える。今、白と黒の画素をそれぞれちょうど半分ずつ持っている画像の特徴ベクトルをｆ1灰色一色からなる画像の特徴ベクトルをｆ2とする。このとき、
【０２００】
【数５８】
2005234994.tif 000161
【０２０１】
【数５９】
2005234994.tif 000162
【０２０２】
【数６０】
2005234994.tif 000163
【０２０３】
である。ここで、２つの特徴ベクトル間の距離を計算すると、ｄ（ｆ1，ｆ2）2＝０となってしまう。ｅ1，ｅ2，ｅ3は線形独立であるが、識別性を持っていないのである。
識別性がなくなるというのは明らかにまずい問題である。この問題は、直交基底＋ユークリッド距離方式では生じない。この方法では基底は線形独立であり、また距離は距離空間の公理を満たしているからである。実際、線形独立性からオブジェクトが違えば、対応するベクトルも異なる。ベクトルが異なれば、距離の公理から距離が０になることはない。
【０２０４】
第３の例で識別性がなくなる原因は、
（Ｒ１）類似行列の設定が間違っている。
（Ｒ２）二次形式距離自体の限界である。
のどちらかである。次に（Ｒ１），（Ｒ２）の各立場から解決を図る。
【０２０５】
まず（Ｒ１）の立場に立ち、二次形式距離のフレームワークの中で、この問題を改善する手段、すなわち、類似行列を変更することを試みる。
識別性と特徴間の類似性の間にはトレードオフの関係があると考えられる。直交基底＋ユークリッド距離方式は、実は斜交基底＋ユークリッド距離方式や二次形式距離の方式に含まれており、対応する類似行列は、単位行列である。したがって、類似行列を単位行列に近づければ、識別性で問題のない直交基底＋ユークリッド距離法に近づけることができる。類似行列の要素ｓiiの値は１のまま変えない。０≦ａ＜１（ａは実数）として、ｓij ＝ａｓijとすることにより、単位行列に近づける。ａが近づける度合いを制御するためのパラメータとなる。ａ＝１の場合が、最初の状態に、また、ａ＝０の場合が、直交基底＋ユークリッド距離方式に当たる。この方法を類似行列変形法と呼ぶことにする。
【０２０６】
［２．２  類似性の消失］
二次形式距離方式や斜交基底＋ユークリッド距離方式では、特徴間の類似性は、保たれている。すなわち、単独の特徴からなると考えられるオブジェクト間の類似性は保たれている。しかし、０でない複数の特徴量から構成される特徴ベクトル間では、この類似性が失われる場合がある。この節では、この問題について論じる。まず、このような問題が生じる簡単な例を示す。
【０２０７】
《類似性が消失する例（第４の例）》
ここでは、１２色からなる色相環を考える。補色の関係にある２つの色Color1とColor2だけからなり、同じ量の画素を含む画像をColor1+Color2で表したことにする。ここで示す例を簡単に言えば、たとえば、赤＋緑、赤橙＋緑、黄＋青を考えたとき、赤＋緑は黄＋青よりも赤橙＋緑に似ていると人間には感じられる。しかし、上記のただ一つの変数ａをパラメータとする類似行列の変形を行っただけでは、斜交基底＋ユークリッド法あるいはそれと等価な二次形式距離法ではそうならず、みな同等に似たものとなってしまう。
【０２０８】
以下、詳しく説明する。各色は「虚数が現れる例（第１の例）」の場合と同様に、円を均等に１２等分する点に対応するものとする。そして、補色の画素を半分ずつ持つ画像に対応する全体特徴ベクトル、すなわち、
【０２０９】
【数６１】
2005234994.tif 000164
【０２１０】
としたとき、ｄ（ｆ1，ｆi），（１≦ｉ＜６）とａとの関係を考える。
我々は、ｆi，ｆj間の距離にも特徴間の類似性が反映されるものと予想していた。すなわち、
【０２１１】
【数６２】
2005234994.tif 000165
【０２１２】
が成り立つものと考えていた。それも直交基底＋ユークリッド距離法に対応するａ＝０では、これらの距離は皆等しくなるものの、０＜ａ≦１の範囲では、ａが１に近いほどその距離の差は大きいと考えていた。しかし、実際に計算してみると、ａの値によらず、直交基底＋ユークリッド距離法と同じく、
【０２１３】
【数６３】
2005234994.tif 000166
【０２１４】
となる。これは、直交基底＋ユークリッド距離法における関係と同じであること、すなわち、特徴間の類似性が消失していることを意味している。このことは縮小率ａを０に近づけても変わらない。
【０２１５】
「類似性が消失する例（第４の例）」が起きる場合は、同様に複数のパラメータを使って、行列の変形を行う。このことにより、「類似性が消失する例（第４の例）」で類似性を消失するということはなくなる。
【０２１６】
図８は、ａ＝１の場合の斜交基底の様子を示した図である。この場合、ｆiは全て円の中心に対応するベクトルｃに等しくなってしまう。そして、距離が０になり、識別性も特徴間の類似性も失われてしまうのである。一方、図８のｆiは、式（６１）が示すように、２つのベクトル０．５ｅiと０．５ｅi+6を合成したベクトルであるが、この２つのベクトルを示す線分に着目すると、これらの線分は、類似性を保存している。このことが本実施の形態に適用される多面体距離（ベクトル集合間の距離）のベースとなる。
【０２１７】
［２．３  ベクトル集合間の距離による特徴空間（マルチベクトル特徴空間）］
この章では、（Ｒ２）が正しいとの仮定に基づいて、すなわち、類似行列を変更することなく、識別性や類似性がなくなるという問題を解決する手法を説明する。
【０２１８】
「類似性が消失する例（第４の例）」に示されるように、特徴ベクトルを斜交基底ベクトルから合成すると、識別性や類似性の消失という問題が起きる。しかし、零ベクトルではないベクトル（すなわち、ｃi≠０であるようなｃiｅi（１≦ｉ≦ｎ））に注目すると、これらのベクトルは、特徴量に関する情報も、特徴間の類似性に関する情報も保持している。また、識別性もある。そこで、今、
【０２１９】
【数６４】
2005234994.tif 000167
【０２２０】
というベクトルの集合に注目する。こういったベクトルからなる集合をベクトル集合と呼ぶことにする。ベクトル集合の中には、同じベクトルが含まれていても構わない。その意味で、正確にはマルチ集合（マルチベクトル）である。
【０２２１】
ここで、ベクトル集合を用いた場合の有効性を概念的に理解しやすくするために、ベクトルの値を物質の質点に置き換えて説明する。マルチベクトル特徴空間ではオブジェクトが一般に複数のベクトルで表される。その複数のベクトルに対応する点に同じ質量からなる質点が置かれているものとする。このとき、それらの質点が作る一種の立体が考えられる。この立体間の距離を定義したのが、以下で定義するδ距離となる。その立体の点をいくつかのグループに分け、それぞれのグループの重心（と本質的には同等のもの）で置き換えたものが、特徴集合の近似となる。
【０２２２】
図９は、比較対象となる２つのベクトル集合を示す図である。図９では、２つのベクトル集合Ａ0＝（ａ1，ａ2，ａ3，ａ4）、Ｂ0＝（ｂ1，ｂ2，ｂ3，ｂ4）に対応する立体を表している。各点には同じ質量の質点が置かれているものとする（少なくとも特徴集合においてはそう考えられえる。この例は特徴集合の例ではないが同じ質量の点が置かれているとする）。２つの立体の重心は一般には一致しないが、この例では一致しているものとする。これらの４つの質点からなる立体を次のように重心を使って２つの質点からなる立体で近似する。
ａ12＝ａ1＋ａ2、ａ34＝ａ3＋ａ4、ｂ14＝ｂ1＋ｂ4、ｂ23＝ｂ2＋ｂ3
ａijはａi、ａjの重心、ｂijはｂi、ｂjの重心を表している。正確には、重心という意味では、ａi＋ａjやｂi＋ｂjを２で割るべきであるが、２で割ることを省けば本質は変わらないので、重心という言い方をすることにする。
【０２２３】
ａ1234やｂ1234についても同様に以下のように表される。
ａ1234＝ａ12＋ａ34＝ａ1＋ａ2＋ａ3＋ａ4
ｂ1234＝ｂ12＋ｂ34＝ｂ1＋ｂ2＋ｂ3＋ｂ4
この場合は元の立体をその重心で近似したことになる。そして、元々重心が一致していたので、ａ1234とｂ1234も一致する。これが識別性の欠如に当たる。
【０２２４】
そこで、本実施の形態では、マルチベクトル特徴空間のベクトル集合を合成せずに、個々のベクトルを１対１で比較することで、立体間の距離という概念を捉える。基本的な考え方は、このベクトル集合同士がどれだけ似ているかを図るため、これらの集合間に距離を定義することである。いろいろな定義の仕方が考えられえるが、以下に基本的な例を示す。
【０２２５】
《マルチベクトル間の距離計算例（第５の例）》
最初に、「類似性が消失する例（第４の例）」と同じ状況について考える。
図１０は、マルチベクトル特徴空間のベクトル集合の例を示す図である。図１０に示すように、赤＋緑それぞれ５０％ずつの画像２０に対して、赤橙＋青緑それぞれ５０％ずつの画像３０と黄＋青それぞれ５０％ずつの画像４０との距離を計算する。この場合、まず、各画像２０，３０，４０の特徴を示すマルチベクトル集合が生成される。
【０２２６】
画像２０のマルチベクトル集合は、赤の方向に長さ０．５のベクトル２１と、緑の方向に長さ０．５のベクトル２２とで構成される。画像３０のマルチベクトル集合は、赤橙の方向に長さ０．５のベクトル３１と、青緑の方向に長さ０．５のベクトル３２とで構成される。画像４０のマルチベクトル集合は、黄の方向に長さ０．５のベクトル４１と、青の方向に長さ０．５のベクトル４２とで構成される。
【０２２７】
ここで、
【０２２８】
【数６５】
2005234994.tif 000168
【０２２９】
とする。そして、ＦiとＦj（ｉ≦ｊ）との間のδ距離を、
【０２３０】
【数６６】
2005234994.tif 000169
【０２３１】
と定義する。ここで、ＭはＦiからＦjへのベクトルの１対１対応全体の集合を表す。ＦiとＦjとは、それぞれｍ個のベクトルからなる。このとき、
【０２３２】
【数６７】
2005234994.tif 000170
【０２３３】
すなわち、δ（Ｆ1，Ｆ2）＝０．７３２、δ（Ｆ1，Ｆ3）＝１．４１４、δ（Ｆ1，Ｆ4）＝２、δ（Ｆ1，Ｆ5）＝１．４１４、δ（Ｆ1，Ｆ6）＝０．７３２が成り立つ。このことは、識別性が保たれ、類似性の消失の問題も解決していることを意味する。また、特徴ベクトル間の類似性ももっともなものとなっている。なお、ここで、｜ａ｜はａの絶対値を表す。
【０２３４】
図１１は、画像間のマルチベクトル距離を示す図である。これは、図１０に示す画像２０と画像３０との間のマルチベクトル距離、および画像２０と画像４０との間のマルチベクトル距離を示している。
【０２３５】
画像２０と画像３０とのδ距離を計算する場合、まず、画像２０のベクトル集合に含まれるベクトル２１と画像３０のベクトル集合に含まれるベクトル３１との距離ｄ1が計算される。同様に、ベクトル２２とベクトル３２との距離ｄ2が計算される。これらの距離ｄ1とｄ2とを加算することで、δ距離が得られる。
【０２３６】
また、画像２０と画像４０とのδ距離を計算する場合、まず、画像２０のベクトル集合に含まれるベクトル２１と画像４０のベクトル集合に含まれるベクトル４１との距離ｄ3が計算される。同様に、ベクトル２２とベクトル４２との距離ｄ4が計算される。これらの距離ｄ3とｄ4とを加算することで、δ距離が得られる。
【０２３７】
図１２は、マルチベクトル距離を用いた画像間のδ距離を示す図である。図１２に示すように、画像２０と画像３０とのδ距離は、画像２０と画像４０とのδ距離よりも近くなる。すなわち、画像２０に対して類似する画像を検索した場合、画像４０よりも画像３０の方が優先的に検出される。
【０２３８】
《線形独立でない例へのアプローチ（第６の例）》
次に、「線形独立でない例（第２の例）」への対応について考える。
図１３は、線形独立でないマルチベクトルの例を示す図である。この例では、白が５０％、黒が５０％の画像５０と、灰色が１００％の画像６０とのマルチベクトル距離を考察する。今、画像５０のベクトル集合Ｆ1と画像６０のベクトル集合Ｆ2とを
Ｆ1＝｛０．５ｅ1，０．５ｅ3｝、Ｆ2＝｛１．０ｅ2｝
とする。この例では、ｅ1は白に対応する斜交基底ベクトル、ｅ3は黒に対応する斜交基底ベクトル、ｅ2は灰色に対応する斜交基底ベクトルである。すなわち、画像５０のベクトル集合には２つのベクトル５１，５２が含まれているが、画像６０のベクトル集合には１つのベクトル６１しか含まれていない。すなわち、２つの集合の要素数が異なっている。そこで、ベクトル６１を０．５ｅ2と０．５ｅ2との２つのベクトルに分ける。
【０２３９】
図１４は、分割されたベクトルを示す図である。図１４に示すように、図１３に示されたベクトル６１が２つのベクトル６２，６３に分割されている。分割後のベクトル集合Ｆ3を次のように定義する。
Ｆ3＝｛０．５ｅ2，０．５ｅ2｝
そして、Ｆ1とＦ3との間の距離を式（６６）によって定義する。この場合、ベクトル５１とベクトル６２との距離ｄ1、およびベクトル５２とベクトル６３との距離ｄ2が加算される。すると、δ距離は正の値になり、識別性の消失の問題は解決される。δ距離の値自体も、人間の見た目による類似判断に近いものである。
【０２４０】
このベクトル集合間の距離をマルチベクトル距離と呼ぶことにする。
［２．４  特徴集合と近似］
極端な例として、
【０２４１】
【数６８】
2005234994.tif 000171
【０２４２】
で定義されるベクトル集合間のマルチベクトル距離を考えることができる。ここでは、式（６４）とは異なり、零ベクトルも含めている。この集合を特徴集合と呼ぶ。しかし、この特徴集合間のマルチベクトル距離を計算することは非常にコストがかかるものと思われる。そこで、この特徴集合をより小さいｍ（１≦ｍ＜ｎ）個のベクトルからなるベクトル集合で、近似することを考え、それをｍ−ベクトル集合と呼ぶ。以下に「類似性が消失する例（第４の例）」に基づく２−ベクトル集合の例を示す。今、
【０２４３】
【数６９】
2005234994.tif 000172
【０２４４】
とする。ここで、
【０２４５】
【数７０】
2005234994.tif 000173
【０２４６】
【数７１】
2005234994.tif 000174
【０２４７】
【数７２】
2005234994.tif 000175
【０２４８】
とする。すると、２−ベクトル集合Ａは、特徴集合Ｆを近似している。「類似性が消失する例（第４の例）」における特徴ベクトルに対応する特徴集合に対する上のＡと同様の２−ベクトル集合をＡi（１≦ｉ≦６）で表したとき、それは、「マルチベクトル間の距離計算例（第５の例）」におけるＦiと一致する。すなわち、２−ベクトル集合間の距離は、式（６７）を使って定義できる。この距離で特徴集合間の距離が近似できる。
【０２４９】
なお、従来の特徴ベクトル間の距離は、この考えに基づくと、１−ベクトル集合による近似と見なすことができる。すなわち、従来の特徴ベクトル間の拡張になっている。
この近似の方法は、斜交基底ベクトルの分割に基づいている。この例では、それらは、
Ｅ1＝｛ｅ1，ｅ2，・・・，ｅ6｝、Ｅ2＝｛ｅ7，ｅ8，・・・，ｅ12｝
という２つのグループに分割されている。ｅ1，ｅ2，・・・，ｅ6は黄色のまわりの暖色系の色であり、ｅ7，ｅ8，・・・，ｅ12は青を中心とした寒色系の色である。このように、斜交基底ベクトルは、それらの類似性に基づいて、近いもの同士まとめられるべきである。その理由は次のとおりである。識別性が消失するといった問題は、近似を使わなければ、すなわち、特徴集合間の距離を使えば、起きない。しかし、近似を使っている場合、やはり起きる可能性がある。ただし、全体にわたって起きるのではなく、部分的に起きるようにローカライズしてくれるようになるからである。上の例で言えば、Ｅ1とＥ2に渡るような識別性の消失ということは起きなくなる。
【０２５０】
次に２つのベクトル集合間の距離ついて一般的に考える。「マルチベクトル間の距離計算例（第５の例）」では、式（６６）の距離の定義でうまくいく。しかし、いつもうまくいくとは限らない。そのような例を以下に示す。
【０２５１】
《非常に類似した特徴へのアプローチ（第７の例）》
以下の２つの２−ベクトル集合について考える。
Ａ1＝｛０．７ｅ1，０．３ｅ3｝、Ａ2＝｛ｅ2，０（零ベクトル）｝
ここで、３つの斜交基底ベクトルｅ1，ｅ2，ｅ3は近接しているものとする。すなわち、それぞれ、灰色よりも少し白っぽい色、灰色、灰色より少し黒っぽい色に対応している。したがって、人間の感覚からすると、Ａ1とＡ2との距離は０に近いはずである。
【０２５２】
しかし、式（６６）と同様の方法を使うと、その距離はｄ（０．７ｅ1，ｅ2）＋ｄ（０．３ｅ3，０（零ベクトル））であり、おおよそ０．６となってしまう。したがって、２つの２−ベクトル集合間の距離を以下のように定義しなおす。
【０２５３】
まず、１つのｍ−ベクトル集合Ａ＝｛ａ1，ａ2，・・・，ａm｝の「ベクトル集合の分割」を次のように定義する。
・ベクトル集合分割の定義
Ａの各要素を次のように分割する。２つのｍ−ベクトル集合を
Ａ＝｛ａ1，ａ2，・・・，ａm｝、Ｂ＝｛ｂ1，ｂ2，・・・，ｂm｝
とする。そして、ベクトルａi，ｂi（１≦ｉ≦ｍ）をそれぞれ、次のように分割する。
ａ1＝ａ11＋ａ12＋・・・＋ａ1m
ａ2＝ａ21＋ａ22＋・・・＋ａ2m
・・・
ａm＝ａm1＋ａm2＋・・・＋ａmm
ａijは零ベクトルでも構わないし、重複していても構わない。この操作を「ベクトル集合の分割」と呼ぶことにし、ρと名づける。そして、この操作ρによって分割されたｍ2個のベクトルからなるベクトル集合を
【０２５４】
【数７３】
2005234994.tif 000176
【０２５５】
で定義する。このベクトル集合の分割方法は無数にあるが、その分割の集合をρ（Ａ）と表すことにする。
このとき、２つのｍ−ベクトル集合
Ａ＝｛ａ1，ａ2，・・・，ａm｝、Ｂ＝｛ｂ1，ｂ2，・・・，ｂm｝
間の「Ｄ距離」を次のように定義する。
【０２５６】
・Ｄ距離の定義
２つのｍ−ベクトル集合間のＤ距離を
【０２５７】
【数７４】
2005234994.tif 000177
【０２５８】
と定義する。
この定義により、「非常に類似した特徴へのアプローチ（第７の例）」の距離は０に近いものとして定義できる。
【０２５９】
ここで、ベクトルの分割方法によるＤ距離の違いを説明する。
図１５は、１つのベクトルを２等分割した例を示す図である。図１５の例では、灰色の画像８０と、画像８０の灰色よりも少し白っぽい色が５０％、画像８０の灰色より少し黒っぽい色が５０％の画像７０とが示されている。これらの画像７０，８０のベクトル集合は、以下のように表されるものとする。
Ｆ1＝｛０．７ｅ1，０．３ｅ3｝、Ｆ2＝｛０．５ｅ2，０．５ｅ2｝
すなわち、灰色１００％の画面８０の特徴を示すベクトルを２等分割している。この場合、ｄ1（０．７ｅ1，０．５ｅ2）＋ｄ2（０．３ｅ1，０．５ｅ2）＞＞０となり、人間の視覚によって感じる類似性と乖離する。
【０２６０】
図１６は、１つのベクトルを不等分割した例を示す図である。この例では、画像７０，８０のベクトル集合を、以下のように表している。
Ｆ1＝｛０．７ｅ1，０．３ｅ3｝、Ｆ2＝｛０．７ｅ2，０．３ｅ2｝
すなわち、灰色１００％の画面８０の特徴を示すベクトルを不等分割している。分割の割合は、比較対象となる画像７０のベクトルの大きさの比率と同じである。この場合、ｄ3（０．７ｅ1，０．７ｅ2）＋ｄ4（０．３ｅ3，０．３ｅ2）がほぼ０となり、人間の視覚によって感じる類似性と一致する。
【０２６１】
［２．５  Ｄ距離の近似計算］
Ｄ距離は上記の定義をそのまま適用したのでは、ベクトルの分割の仕方も無数にあり、計算量が膨大となる。ここでは、Ｄ距離を近似的に求める方式について述べる。
【０２６２】
２つのｍ−ベクトル集合をＡ＝｛ａ1，ａ2，・・・，ａm｝とＢ＝｛ｂ1，ｂ2，・・・，ｂm｝とする。この２つのｍ−ベクトル集合間のＤ距離の近似値を求めるアルゴリズムを以下に示す。以下例では、特徴量が絶対量で表された場合にも適用できるように、Ａ，Ｂの特徴量の絶対値の合計に応じた特徴ベクトルの分割を行う。そこで、Ａ，Ｂの特徴量の絶対値の合計をそれぞれ、α，βで表すことにする。すなわち、
【０２６３】
【数７５】
2005234994.tif 000178
【０２６４】
【数７６】
2005234994.tif 000179
【０２６５】
とする。特徴量が相対量であれば、αとβとは１となる。また、以下変数Ｄは求めるべきＤ距離を表すものとする。なお、以下では、零ベクトルを「ベクトル０」と表す。また、零ベクトルだけからなるベクトル集合をＯで表すことにする。たとえば、｛ベクトル０，ベクトル０，ベクトル０｝といった集合がＯである。
【０２６６】
次に、特徴集合間のＤ距離の近似計算の処理手順について説明する。
図１７は、Ｄ距離の近似計算の処理手順を示すフローチャートである。この処理は、図４に示す距離計算装置１２４で行われる処理である。
【０２６７】
［ステップＳ１１］Ａ＝ＯまたはＢ=Ｏの何れかの条件を満たすか否かが判断される。何れかの条件を満たす場合、処理がステップＳ１２に進められ、そうでなければ処理がステップＳ１５に進められる。
【０２６８】
［ステップＳ１２］Ａ＝Ｏか否かが判断される。Ａ＝Ｏであれば処理がステップＳ１３に進められ、そうでなければ処理がステップＳ１４に進められる。
［ステップＳ１３］Ａ＝Ｏの場合、Ｄ＝βと設定され、その後処理が終了する。
【０２６９】
［ステップＳ１４］Ｂ＝Ｏの場合、Ｄ＝αと設定され、その後処理が終了する。
［ステップＳ１５］Ａ≠ＯかつＢ≠Ｏの場合は、Ｄ＝０と設定される。
［ステップＳ１６］Ａ≠Ｏか否かが判断される。Ａ≠Ｏであれば、処理がステップＳ１７に進められ、Ａ＝Ｏであれば処理が終了する。すなわち、Ａ≠Ｏである間、以降のステップＳ１７〜Ｓ２０の処理が繰り返される。
【０２７０】
［ステップＳ１７］Ａに含まれる零ベクトルでないａiと、Ｂに含まれる零ベクトルでないｂj中で、（ａi，ｂj）／（｜ａi｜｜ｂj｜）が最小となるものが改めてａi，ｂjとされる。
【０２７１】
［ステップＳ１８］｜ａi｜／｜ｂj｜≧α／βの条件が満たされるか否かが判断される。この条件が満たされる場合、処理がステップＳ１９に進められる。条件が満たされない場合、処理がステップＳ２０に進められる。
【０２７２】
［ステップＳ１９］｜ａi｜／｜ｂj｜≧α／βの場合、Ｄ＝Ｄ＋ｄ（αａi／β，ｂj）とする。Ａのａiを（１−（α｜ｂj｜／β｜ａi｜））ａiで、Ｂのｂjを零ベクトルで置き換える。その後、処理がステップＳ１６に進められる。
【０２７３】
［ステップＳ２０］｜ａi｜／｜ｂj｜＜α／βの場合、Ｄ＝Ｄ＋ｄ（ａi，βｂj／α）とする。Ａのａiを零ベクトルで、Ｂのｂjを（１−（β｜ａi｜／α｜ｂj｜））ｂjで置き換える。その後、処理がステップＳ１６に進められる。
【０２７４】
このアルゴリズムの基本的な考え方は次のとおりである。すなわち、ａi，ｂjの中で、（ａi，ｂj）／（｜ａi｜｜ｂj｜）が最小となるもの（すなわち、ａiと同じ方向で長さ１のベクトルと、ｂjと同じ方向で長さ１のベクトルとが最も近いようなａi，ｂj）を選び、それぞれから、長さの比がα対βとなるようにベクトルを切り出す。その際、少なくともどちらかのベクトルが使い尽くされるようにする。こうして、切り出されたベクトル同士が対応するものとし、それらの間の距離を距離の総計に加える。一方、切り出されたベクトル分だけ、ａi，ｂjを短くする。少なくとも一方は使い尽くされているので、零ベクトルとなる。対応される際、長さの比をα対βとしているので、どの対応においても、この比の関係は成り立つ。このため、Ａ，Ｂは同時にＯとなる。
【０２７５】
なお、ここでのベクトルを切り出す操作が、ベクトル集合分割の操作を決めていることになり、その対応関係が、分割されたベクトル集合間のδ距離における１対１の対応を決めていることになる。
【０２７６】
ａi，ｂjを選ぶとき、上記のように、それぞれの方向の長さ１のベクトルの距離が最小になるように選んでいる。すなわち、一方の特徴ベクトルの集合と他方のベクトル集合とから、最も近い方向を向いた特徴ベクトル同士を選び、それらからベクトルペアとなる部分を切り出す処理が繰り返し行われている。そのため、こうして計算された距離は、Ｄ距離に近いことが期待される。
【０２７７】
特徴集合間の近似はここで定義した距離に基づく。そして、識別性や類似性の問題は近似している限り残るが、ｍの値が大きくなるにつれて、ローカライズされる。また、従来用いられてきた特徴ベクトルは、１−ベクトル集合による近似と同じになる。すなわち、ここで定義した近似による距離は、従来の特徴ベクトル間の距離の一般化になっている。
【０２７８】
［３  検索方式］
マルチベクトル特徴空間における検索方式を説明する。なお、検索は、図４に示す検索装置１２３によって行われる。マルチベクトル特徴空間では、ベクトル集合を前もって生成しておくか、それとも検索時に生成するかによって、大きく次の２つの方式に分かれる。以下、それぞれについて述べる。
【０２７９】
（１）検索時にベクトル集合を生成する方式
前もって、ＨＤＤ１０３等の二次記憶には、画像などのオブジェクトから自動的に抽出した特徴量とオブジェクトの識別子の組を格納しておく。また、斜交基底に関する情報を格納しておく。そして、検索時に、特徴量と斜交基底からｍ−ベクトル集合を生成し、Ｄ距離を計算することにより、類似検索を行う。この検索方式を採用する場合、図４の記憶装置１１０には、特徴量とオブジェクトの識別子との組が更に格納される。
【０２８０】
この方式はベクトル集合を格納しなくてすむため、ｍが２よりも大きいときは、後述の（２）の方式に比べ二次記憶容量は少なくてすむ。ただし、検索時にベクトル集合を生成する必要がある。
【０２８１】
（２）検索前にベクトル集合を生成・格納する方式
ＨＤＤ１０３等の二次記憶には、特徴量と斜交基底から生成したｍ−ベクトル集合を格納しておく。そして、検索時にこのｍ−ベクトル集合とＤ距離を用いて類似検索を行う。本実施の形態は、（２）の検索方式に従って説明している。
【０２８２】
この方式は、ベクトル集合を格納しなければならないため、ｍが２より大きい場合は、その負担が大きくなる。
（１），（２）の方式にはこのようにトレードオフがあるが、一般には、ｍ＝１の場合は（２）を、ｍが２以上の場合は（１）を用いるのが妥当と思われる。
【０２８３】
以上のような処理を行うことで、本実施の形態では以下のような特別な効果が得られる。
・精度の向上
本実施の形態によれば、マルチベクトル特徴空間により、二次形式距離よりもさらに精度を向上させることができる。
【０２８４】
・性能の向上
特徴空間の近似により、性能を向上させることができる。また、Ｄ距離を近似的に求めることにより、性能を向上させることができる。
【０２８５】
・識別性の向上
本実施の形態に従って、マルチベクトル特徴空間によりベクトルペア同士の距離を求めることにより、特徴間類似性を損なうことなく識別性を高めることができる。
【０２８６】
［４  ＥＭＤとの相違点］
ここで、前述の非特許文献３に示されるＥＭＤと上記実施の形態との相違点について説明する。大きな違いは、本実施の形態に係るマルチベクトル特徴空間が部分マッチではなく、常に全体としてのマッチであるのに対し、ＥＭＤでは、２つのシグニチャの数（特徴量の数）が異なる場合は、部分マッチとなるという点である。
【０２８７】
画像のヒストグラムの場合、相対量（所定の色が全体に占める割合により特徴量が示される）による場合と、絶対量（所定の色のピクセル数により特徴量が示される）による場合が考えられる。相対量の場合は、全体マッチと考えられるが、絶対量で特徴量である画素数の総量が異なる場合、ＥＭＤでは部分マッチと考えられる。
【０２８８】
一方、本実施の形態に係る方式では、比較対象となる２つのベクトル集合それぞれに含まれる特徴ベクトルの数を常に一致させている。すなわち、少なくとも、特徴ベクトル数が少ないベクトル集合内の一部の特徴ベクトルが分割される。その結果、全ての特徴ベクトルが１対１のベクトルペアに使用され、距離の計算が行われる。これは、特徴量の数が異なっても、部分マッチではなく全体として比較できることを意味する。
【０２８９】
常に全体マッチができることは、特徴量の絶対量に大きな意味がある場合に特に有効である。たとえば、文書では、絶対量による特徴量の全体マッチが意味を持つ。すなわち、文書の類似検索では、単語ごとの出現頻度あるいはそれに重みをつけたものが特徴量として用いられる。したがって、次元数は単語の数に等しくなる。ただし、単語は全ての単語を対象とするわけではなく、文書の特徴をよく表すようなものが選ばれる。したがって、「これ」、「する」など頻繁に使われるような単語は除かれる。それでも、通常千から１万程度の次元になる。文書では、単語の出現頻度は、後で述べる画像の画素が相対的であるのに比べ、絶対的である。ある単語が頻繁に使われるということはそれ自体が意味を持つ。
【０２９０】
たとえば、ある単語が文書Ｕで１度しか現れないのに、文書Ｖでは１０回現れたとすれば、その単語がその文書Ｖでは重要である、あるいはその文書Ｖを頻度の少ないことばに比べ特徴づけることを意味する。それに対し、文書Ｕでは、１回しか触れられておらず、この単語がそれほど重要でない、あるいはその文書Ｕをそれほど特徴づけていないことを意味する。したがって、文書の場合には、特徴量は絶対量（単語の出現数）で表される。
【０２９１】
本実施の形態の方式であれば、文書の類似検索のように特徴量の数が異なる（絶対量が意味を持つ）場合にも、部分的な比較ではなく全体として比較できる。全体を比較することで、全体としての類似性を的確に判別できる。
【０２９２】
また、画像の類似検索では、たとえば、黒、白それぞれ１０００画素ずつの画像Ｘと、黒が１０００画素の画像Ｙとを比較する場合を考える。ＥＭＤでは、特徴量の部分的な比較となり、画像Ｘの一部の特徴量（１０００画素の黒）と画像Ｙの全体の特徴量（１０００画素の黒）とが一致する。
【０２９３】
一方、本実施の形態では、図１７のフローチャートに示すように、特徴量の絶対量の比（｜α｜／｜β｜）に応じて、ベクトルペアを構成するそれぞれの特徴ベクトルの長さを縮めている（縮められた分の長さのベクトルが分割されている）。そのため、元の特徴量が絶対量で示されていても、全体としての比較が可能となる。
【０２９４】
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、マルチメディアデータ検索装置が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記録装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ(Digital Versatile Disc)、ＤＶＤ−ＲＡＭ(Random Access Memory)、ＣＤ−ＲＯＭ(Compact Disc Read Only Memory)、ＣＤ−Ｒ(Recordable)／ＲＷ(ReWritable)などがある。光磁気記録媒体には、ＭＯ(Magneto-Optical disk)などがある。
【０２９５】
プログラムを流通させる場合には、たとえば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０２９６】
プログラムを実行するコンピュータは、たとえば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、サーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０２９７】
（付記１）  マルチメディアデータ間の類似関係を判定するための類似度判定プログラムにおいて、
コンピュータを、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、
２つの比較対象マルチメディアデータを入力する入力手段、
前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、
前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、
前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出する類似度算出手段、
前記類似度算出手段で算出された類似度を出力する出力手段、
として機能させることを特徴とする類似度判定プログラム。
【０２９８】
（付記２）  前記マルチメディアデータは、画像データであることを特徴とする付記１記載の類似度判定プログラム。
（付記３）  前記斜交基底ベクトル記憶手段には、前記属性として複数の代表色が定義されており、
前記ベクトル集合生成手段は、前記画像データで表現される画像の色と前記代表色との対応関係が予め定義されており、前記代表色に対応する色が前記画像に占める割合を、前記属性の前記特徴量とすることを特徴とする付記２記載の類似度判定プログラム。
【０２９９】
（付記４）  前記ベクトルペア生成手段は、前記ベクトル集合の前記特徴ベクトルを複数のグループに分類し、グループ毎に合成することで、前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させることを特徴とする付記１記載の類似度判定プログラム。
【０３００】
（付記５）  前記ベクトルペア生成手段は、一方の前記特徴ベクトルの集合と他方の前記ベクトル集合とから、最も近い方向を向いた特徴ベクトル同士を選び、それらから前記ベクトルペアとなる部分を繰り返し切り出すことを特徴とする付記１記載の類似度判定プログラム。
【０３０１】
（付記６）  前記斜交基底ベクトル記憶手段は、前記斜交基底ベクトルの数がｎ（ｎは自然数）であり、前記斜交基底ベクトルの線形独立性がｎ次元内で保てない場合、ｎ＋１次元から２ｎ次元の範囲内の次元で線形独立性を保った前記斜交基底ベクトルが格納されていることを特徴とする付記１記載の類似度判定プログラム。
【０３０２】
（付記７）  前記ベクトルペア生成手段は、前記特徴ベクトルを分割することで、前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させることを特徴とする付記１記載の類似度判定プログラム。
【０３０３】
（付記８）  前記ベクトルペア生成手段は、前記ベクトル集合それぞれから前記特徴ベクトルを抽出し、抽出した２つの前記特徴ベクトルから、前記比較対象マルチメディアデータそれぞれの特徴量の合計値の比に応じた長さのベクトルを分割することを特徴とする付記７記載の類似度判定プログラム。
【０３０４】
（付記９）  前記ベクトルペア生成手段は、前記ベクトル集合に含まれる前記特徴ベクトルの数をｍ（ｍは自然数）に一致させたとき、各特徴ベクトルをｍ個に細分化し、細分化されたベクトル同士のベクトルペアを生成することを特徴とする付記１記載の類似度判定プログラム。
【０３０５】
（付記１０）  マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索プログラムにおいて、
コンピュータを、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、
複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合を記憶するベクトル集合記憶手段、
検索条件マルチメディアデータを入力する入力手段、
前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、
前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、
前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出する類似度算出手段、
前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する出力手段、
として機能させることを特徴とするマルチメディアデータ検索プログラム。
【０３０６】
（付記１１）  マルチメディアデータ間の類似関係を判定するための類似度判定方法において、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルが斜交基底ベクトル記憶手段に記憶されており、
入力手段が、２つの比較対象マルチメディアデータを入力し、
ベクトル集合生成手段が、前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とし、
ベクトルペア生成手段が、前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成し、
ベクトル間距離算出手段が、前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算し、
類似度算出手段が、前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出し、
出力手段が、前記類似度算出手段で算出された類似度を出力する、
ことを特徴とする類似度判定方法。
【０３０７】
（付記１２）  マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索方法において、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルが斜交基底ベクトル記憶手段に記憶されており、
複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合がベクトル集合記憶手段に記憶されており、
入力手段が、検索条件マルチメディアデータを入力し、
ベクトル集合生成手段が、前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とし、
ベクトルペア生成手段が、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成し、
ベクトル間距離算出手段が、前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算し、
類似度算出手段が、前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出し、
出力手段が、前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する、
ことを特徴とするマルチメディアデータ検索方法。
【０３０８】
（付記１３）  マルチメディアデータ間の類似関係を判定するための類似度判定装置において、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段と、
２つの比較対象マルチメディアデータを入力する入力手段と、
前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段と、
前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段と、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段と、
前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出する類似度算出手段と、
前記類似度算出手段で算出された類似度を出力する出力手段と、
を有することを特徴とする類似度判定装置。
【０３０９】
（付記１４）  マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索装置において、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段と、
複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合を記憶するベクトル集合記憶手段と、
検索条件マルチメディアデータを入力する入力手段と、
前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段と、
前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段と、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段と、
前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出する類似度算出手段と、
前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する出力手段と、
を有することを特徴とするマルチメディアデータ検索装置。
【０３１０】
（付記１５）  マルチメディアデータ間の類似関係を判定するための類似度判定プログラムを記録したコンピュータ読み取り可能な記録媒体において、
コンピュータを、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、
２つの比較対象マルチメディアデータを入力する入力手段、
前記入力手段で入力された前記比較対象マルチメディアデータそれぞれを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、
前記比較対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、
前記ベクトル間距離算出手段で計算された前記距離を合算し、前記比較対象マルチメディアデータ間の類似度を算出する類似度算出手段、
前記類似度算出手段で算出された類似度を出力する出力手段、
として機能させることを特徴とする類似度判定プログラムを記録したコンピュータ読み取り可能な記録媒体。
【０３１１】
（付記１６）  マルチメディアデータを対象とした検索を行うためのマルチメディアデータ検索プログラムを記録したコンピュータ読み取り可能な記録媒体において、
コンピュータを、
前記マルチメディアデータの特徴を表す複数の属性それぞれに対応付けて設けられ、対応する属性の特徴をベクトルの向きによって表現した斜交基底ベクトルを記憶する斜交基底ベクトル記憶手段、
複数の検索対象マルチメディアデータの特徴を複数の特徴ベクトルで表したベクトル集合を記憶するベクトル集合記憶手段、
検索条件マルチメディアデータを入力する入力手段、
前記入力手段で入力された前記検索条件マルチメディアデータを解析し、前記属性に応じた情報の含有度を示す特徴量を決定し、前記属性毎に前記特徴量を前記斜交基底ベクトルに乗算して特徴ベクトルを生成し、ベクトル集合とするベクトル集合生成手段、
前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれの前記ベクトル集合に含まれる前記特徴ベクトルの数を一致させ、前記ベクトル集合それぞれに含まれる前記特徴ベクトル同士を１対１で対応付けてベクトルペアを生成するベクトルペア生成手段、
前記ベクトルペア生成手段で生成された前記ベクトルペア毎に、前記ベクトルペアに含まれる前記特徴ベクトル間の類似度を示す距離を計算するベクトル間距離算出手段、
前記ベクトル間距離算出手段で計算された前記距離を前記検索対象マルチメディアデータ毎に合算し、前記検索条件マルチメディアデータと前記検索対象マルチメディアデータそれぞれとの間の類似度を算出する類似度算出手段、
前記類似度算出手段で算出された前記類似度のうち、最も高い類似度の前記検索対象マルチメディアデータの識別情報を出力する出力手段、
として機能させることを特徴とするマルチメディアデータ検索プログラムを記録したコンピュータ読み取り可能な記録媒体。
【図面の簡単な説明】
【０３１２】
【図１】実施の形態に適用される発明の概念図である。
【図２】画像データの類似度判断例を示す模式図である。
【図３】マルチメディアデータ検索装置のハードウェア構成例を示す図である。
【図４】マルチメディアデータ検索装置の機能構成図である。
【図５】マンセルの色立体を示す図である。
【図６】色の３要素である色相、明度、彩度との関係を示す図である。
【図７】マンセルの色立体上での色の配置を簡略化して表した図である。
【図８】ａ＝１の場合の斜交基底の様子を示した図である。
【図９】比較対象となる２つのベクトル集合を示す図である。
【図１０】マルチベクトル特徴空間のベクトル集合の例を示す図である。
【図１１】画像間のマルチベクトル距離を示す図である。
【図１２】マルチベクトル距離を用いた画像間のδ距離を示す図である。
【図１３】線形独立でないマルチベクトルの例を示す図である。
【図１４】分割されたベクトルを示す図である。
【図１５】１つのベクトルを２等分割した例を示す図である。
【図１６】１つのベクトルを不等分割した例を示す図である。
【図１７】Ｄ距離の近似計算の処理手順を示すフローチャートである。
【図１８】色ヒストグラムによる画像の特徴量を示す図である。
【図１９】３つの画像に対応する３点を表した図である。
【図２０】色相環を示す図である。
【図２１】赤、赤橙、緑の単一色からなる画像それぞれの特徴量を示す図である。
【図２２】斜交基底の例を示す図である。
【図２３】直交座標と斜交座標の関係を説明する図である。
【図２４】従来技術の問題点を整理した図である。
【図２５】色相環における特徴間の類似性を斜交基底に忠実に反映した図である。
【符号の説明】
【０３１３】
１  斜交基底ベクトル記憶手段
１ａ  斜交基底ベクトル
２  入力手段
２ａ，２ｂ  マルチメディアデータ
３  ベクトル集合生成手段
４  ベクトルペア生成手段
５  ベクトル間距離算出手段
６  類似度算出手段
７  類似度
８  出力手段
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】図２３
【補正方法】変更
【補正の内容】
【図２３】
2005234994.tif 000180