(57)【要約】【課題】２つのベクトル間のパターンマッチングを高速に行う。【解決手段】類似ベクトル検出装置２において、ベクトル変換部２０，２１は、登録ベクトルｇ及び入力ベクトルｆに対して、順序行列による変換、離散コサイン変換、離散フーリエ変換、ウォルシュ−アダマール変換、或いはカルーネン−レーベ変換を施す。階層的距離演算部２３は、２つのベクトル間の距離計算を、有意性の高いベクトル成分、すなわち、上述の変換で分散や固有値の大きい成分、或いは低周波成分から順に階層的に行う。そして、ある階層までに計算された距離の積算値が閾値判定部２４において距離の閾値Ｓを上回ったと判定された場合、閾値Ｓを上回ったことのみを出力して距離計算を打ち切る。【選択図】　図６
2004046370.tif 000002
【特許請求の範囲】
【請求項１】
２つの入力ベクトル間の類似度を求める類似度算出方法であって、
上記２つの入力ベクトル間の距離算出を階層的に行う階層的距離算出工程と、上記階層的距離算出工程の各階層で算出された距離の積算値を予め設定された閾値と比較する閾値比較工程と、
上記閾値比較工程における比較結果に応じて、上記階層的距離算出工程における距離算出を制御する制御工程と、
最後の階層までに算出された距離の積算値を上記類似度として出力する出力工程とを有し、
上記制御工程では、上記閾値比較工程において、ある階層までに算出された距離の積算値が上記閾値を上回った場合、距離算出を打ち切るように制御すること
を特徴とする類似度算出方法。
【請求項２】
上記階層的距離算出工程では、上記２つの入力ベクトルを構成する各成分間の距離算出が階層的に行われ、ある階層までに算出された距離の積算値が上記閾値を下回った場合、次の成分間の距離算出が行われることを特徴とする請求項１記載の類似度算出方法。
【請求項３】
上記２つの入力ベクトルに対して所定の変換を施す変換工程を有し、
上記階層的距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、上記所定の変換に基づく所定の順序で行われること
を特徴とする請求項２記載の類似度算出方法。
【請求項４】
上記所定の変換は、上記２つの入力ベクトルを構成する各成分の順序を当該各成分の分散の大きさに従って並べ替える変換であり、
上記階層的距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、分散の大きな成分から順に行われること
を特徴とする請求項３記載の類似度算出方法。
【請求項５】
上記所定の変換は、離散コサイン変換又は離散フーリエ変換であり、
上記階層的距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、低周波成分から順に行われること
を特徴とする請求項３記載の類似度算出方法。
【請求項６】
上記所定の変換は、ウォルシュ−アダマール変換であり、
上記階層的距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、低交番数成分から順に行われること
を特徴とする請求項３記載の類似度算出方法。
【請求項７】
上記所定の変換は、カルーネン−レーベ変換であり、
上記階層的距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、固有値の大きな成分から順に行われること
を特徴とする請求項３記載の類似度算出方法。
【請求項８】
上記変換工程にて変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を上記所定の順序で取り出して階層的な複数の部分ベクトルに分割する分割工程を有し、
上記階層的距離算出工程では、最上位階層の部分ベクトルから順に部分ベクトルを構成する各成分間の距離算出が階層的に行われ、ある階層までの部分ベクトルを構成する全ての成分間について算出された距離の積算値が上記閾値を下回った場合、一階層下位の部分ベクトルを構成する各成分間の距離算出が行われること
を特徴とする請求項３記載の類似度算出方法。
【請求項９】
上記入力ベクトルは、音響信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記音響信号の所定の時区間内のパワースペクトル係数をベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項１０】
上記入力ベクトルは、音響信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記音響信号の所定の時区間内の線形予測係数をベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項１１】
上記入力ベクトルは、符号化音響信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記符号化音響信号の各フレーム内の周波数成分の強さを表すパラメータをベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項１２】
上記入力ベクトルは、映像信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記映像信号の所定の時区間内の代表画像、上記所定の時区間内のフレーム画像の平均画像、又は上記代表画像若しくは上記平均画像を所定のブロック単位に分割した小画像の信号値をベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項１３】
上記入力ベクトルは、映像信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記映像信号の所定の時区間内のフレーム画像の、輝度及び／又は色に対するヒストグラムをベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項１４】
上記入力ベクトルは、符号化映像信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記符号化映像信号の所定の時区間の直近にあるフレーム内符号化画像の符号化単位となる各ブロックのＤＣ成分の信号値をベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項１５】
２つの入力ベクトル間の類似度を求める類似度算出装置であって、
上記２つの入力ベクトル間の距離算出を階層的に行う階層的距離算出手段と、上記階層的距離算出手段によって各階層で算出された距離の積算値を予め設定された閾値と比較する閾値比較手段と、
上記閾値比較手段による比較結果に応じて、上記階層的距離算出手段による距離算出を制御する制御手段と
最後の階層までに算出された距離の積算値を上記類似度として出力する出力手段とを備え、
上記制御手段は、上記閾値比較手段による比較の結果、ある階層までに算出された距離の積算値が上記閾値を上回った場合、距離算出を打ち切るように制御すること
を特徴とする類似度算出装置。
【請求項１６】
上記階層的距離算出手段は、上記２つの入力ベクトルを構成する各成分間の距離算出を階層的に行い、ある階層までに算出した距離の積算値が上記閾値を下回った場合、次の成分間の距離算出を行うことを特徴とする請求項１５記載の類似度算出装置。
【請求項１７】
上記２つの入力ベクトルに対して所定の変換を施す変換手段を備え、
上記階層的距離算出手段は、上記変換手段によって変換された上記２つの入力ベクトル間の距離算出を、上記所定の変換に基づく所定の順序で行うこと
を特徴とする請求項１６記載の類似度算出装置。
【請求項１８】
上記変換手段によって変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を上記所定の順序で取り出して階層的な複数の部分ベクトルに分割する分割手段を備え、
上記階層的距離算出手段は、最上位階層の部分ベクトルから順に部分ベクトルを構成する各成分間の距離算出を階層的に行い、ある階層までの部分ベクトルを構成する全ての成分間について算出した距離の積算値が上記閾値を下回った場合、一階層下位の部分ベクトルを構成する各成分間の距離算出を行うこと
を特徴とする請求項１７記載の類似度算出装置。
【請求項１９】
２つの入力ベクトル間の類似度を求める類似度算出処理をコンピュータに実行させるプログラムであって、
上記２つの入力ベクトル間の距離算出を階層的に行う階層的距離算出工程と、上記階層的距離算出工程の各階層で算出された距離の積算値を予め設定された閾値と比較する閾値比較工程と、
上記閾値比較工程における比較結果に応じて、上記階層的距離算出工程における距離算出を制御する制御工程と
最後の階層までに算出された距離の積算値を上記類似度として出力する出力工程とを有し、
上記制御工程では、上記閾値比較工程において、ある階層までに算出された距離の積算値が上記閾値を上回った場合、距離算出を打ち切るように制御すること
を特徴とするプログラム。
【請求項２０】
上記階層的距離算出工程では、上記２つの入力ベクトルを構成する各成分間の距離算出が階層的に行われ、ある階層までに算出された距離の積算値が上記閾値を下回った場合、次の成分間の距離算出が行われることを特徴とする請求項１９記載のプログラム。
【請求項２１】
上記２つの入力ベクトルに対して所定の変換を施す変換工程を有し、
上記階層的距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、上記所定の変換に基づく所定の順序で行われること
を特徴とする請求項２０記載のプログラム。
【請求項２２】
上記変換工程にて変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を上記所定の順序で取り出して階層的な複数の部分ベクトルに分割する分割工程を有し、
上記階層的距離算出工程では、最上位階層の部分ベクトルから順に部分ベクトルを構成する各成分間の距離算出が階層的に行われ、ある階層までの部分ベクトルを構成する全ての成分間について算出された距離の積算値が上記閾値を下回った場合、一階層下位の部分ベクトルを構成する各成分間の距離算出が行われること
を特徴とする請求項２１記載のプログラム。
【請求項２３】
２つの入力ベクトル間の類似度を求める類似度算出処理をコンピュータに実行させるプログラムが記録されたコンピュータ読み取り可能な記録媒体であって、
上記２つの入力ベクトル間の距離算出を階層的に行う階層的距離算出工程と、上記階層的距離算出工程の各階層で算出された距離の積算値を予め設定された閾値と比較する閾値比較工程と、
上記閾値比較工程における比較結果に応じて、上記階層的距離算出工程における距離算出を制御する制御工程と
最後の階層までに算出された距離の積算値を上記類似度として出力する出力工程とを有し、
上記制御工程では、上記閾値比較工程において、ある階層までに算出された距離の積算値が上記閾値を上回った場合、距離算出を打ち切るように制御すること
を特徴とするプログラムが記録された記録媒体。
【請求項２４】
上記階層的距離算出工程では、上記２つの入力ベクトルを構成する各成分間の距離算出が階層的に行われ、ある階層までに算出された距離の積算値が上記閾値を下回った場合、次の成分間の距離算出が行われることを特徴とする請求項２３記載の記録媒体。
【請求項２５】
上記プログラムは、上記２つの入力ベクトルに対して所定の変換を施す変換工程を有し、
上記階層的距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、上記所定の変換に基づく所定の順序で行われること
を特徴とする請求項２４記載の記録媒体。
【請求項２６】
上記プログラムは、上記変換工程にて変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を上記所定の順序で取り出して階層的な複数の部分ベクトルに分割する分割工程を有し、
上記階層的距離算出工程では、最上位階層の部分ベクトルから順に部分ベクトルを構成する各成分間の距離算出が階層的に行われ、ある階層までの部分ベクトルを構成する全ての成分間について算出された距離の積算値が上記閾値を下回った場合、一階層下位の部分ベクトルを構成する各成分間の距離算出が行われること
を特徴とする請求項２５記載の記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、２つのベクトル間のパターンマッチングを高速に行う類似度算出方法及び装置、並びにプログラム及び記録媒体に関する。
【０００２】
【従来の技術】
従来より、既知のパターンと略々同じパターンを未知の入力信号から検出したり、２つの信号間の類似性を評価したりするため、音響処理技術、画像処理技術、通信技術、レーダ技術など、信号処理が関係するあらゆる技術分野でデータの類似性や一致性の判定が行われている。一般に、類似データの検出には、データを特徴ベクトル化し、その距離又は角度（相関）の大きさによって類似性を判定する手法が用いられている。
【０００３】
特に、入力値と全ての候補それぞれとの類似度を求めた上で最も距離の近いものを決定する、いわゆる全探索（ｆｕｌｌ　ｓｅａｒｃｈ）が、最もシンプル且つ検出漏れのない手法であり、データ量が少ない場合によく用いられている。しかしながら、例えば大量に蓄積された映像や音声から、入力映像や入力音声と類似する部分を検索する場合には、毎秒あたりの特徴ベクトル次元が大きく、また、それらが数十乃至数百時間分蓄積されたものに対しての検索が行われるため、このような単純な全探索を行うと、検索時間が膨大なものとなる問題がある。
【０００４】
一方、大量のデータを検索するためには、例えば文書検索等の記号化されたデータの完全一致検索を行う場合などに、二分木法（ｂｉｎａｒｙ　ｔｒｅｅ　ｓｅａｒｃｈ）やハッシュ法などの高速化技術が用いられる。これは、予めデータを順序立てて格納し、検索時には入力データと異なる枝或いはテーブルの比較を省略することで高速化するものである。しかしながら、例えば映像や音声等の物理信号を対象とする場合、データには本質的に歪みやノイズがあるため、記号化されたデータが完全に一致することは稀であり、多数の検出漏れが発生してしまう。また、データが本質的に多次元であることから、予めデータに一意の順序付けを施しておくことが困難であるという問題がある。
【０００５】
そこで、特開平８−１２３４６０号公報には、データ登録時に距離の近い複数のベクトルをグループ化して１つの代表ベクトルで代表させる処理を行い、検索時に先ず入力ベクトルと代表ベクトルとの間の距離を計算し、その距離が近いもののみグループ内の全てのベクトルとの比較を行うことで、類似ベクトル検索を高速化し、且つ、多次元でベクトルの歪みを反映させることのできる技術が提案されている。
【０００６】
また、特開２００１−１３４５７３号公報には、ベクトルを符号化して短い符号により索引付けすることで、距離計算回数の増加を抑制し、高速な類似データ検索を可能とする技術が提案されている。
【０００７】
【発明が解決しようとする課題】
しかしながら、上述した特開平８−１２３４６０号公報に記載された技術では、登録時に適切なグループ分けと代表ベクトルの選択が必要とされ、登録操作が煩雑になるという問題があった。また、検索時においても、例えば入力ベクトルと最小距離にある登録ベクトルが、入力ベクトルと最小距離にある代表ベクトルが代表するグループに属しているとは限らないため、検索すべきグループを決定する操作が煩雑になるという問題があった。
【０００８】
また、上述した特開２００１−１３４５７３号公報に記載された技術では、符号化する際にベクトル間の距離関係が失われるか、又は非加算的若しくは非単調で複雑な距離関係となり、登録や検索の仕組みが煩雑になるという問題があった。
【０００９】
ここで、映像や音声は本質的に時系列であるため、登録は実時間で行われることが望ましく、また、検索時には、時間順序を反映できるものであることが望ましい。言い換えれば、上述の特開平８−１２３４６０号公報や特開２００１−１３４５７３号公報に記載された技術のように、時系列を入れ替えるような登録操作を必要としたり、更新時に既登録のデータや索引に対する配置替えを必要とするような手法は、時系列データの検索には適切でない。
【００１０】
すなわち、
（ａ）全探索の構造的シンプルさ、歪みに対する頑健さを失わず、
（ｂ）登録や削除が実時間以内で行われ、
（ｃ）登録や削除によって他の既登録データに対する操作を必要としない
という条件を満たしつつ、全探索よりも遙かに短時間に検索が行われるような仕組みが望まれている。
【００１１】
本発明は、このような従来の実情に鑑みて提案されたものであり、上述の条件を満たしつつ、２つのベクトル間のパターンマッチングを高速に行う類似度算出方法及び装置、並びにその類似度算出処理をコンピュータに実行させるプログラム及びそのようなプログラムが記録されたコンピュータ読み取り可能な記録媒体を提供することを目的とする。
【００１２】
【課題を解決するための手段】
上述した目的を達成するために、本発明に係る類似度算出方法は、２つの入力ベクトル間の類似度を求める類似度算出方法であって、上記２つの入力ベクトル間の距離算出を階層的に行う階層的距離算出工程と、上記階層的距離算出工程の各階層で算出された距離の積算値を予め設定された閾値と比較する閾値比較工程と、上記閾値比較工程における比較結果に応じて、上記階層的距離算出工程における距離算出を制御する制御工程と、最後の階層までに算出された距離の積算値を上記類似度として出力する出力工程とを有し、上記制御工程では、上記閾値比較工程において、ある階層までに算出された距離の積算値が上記閾値を上回った場合、距離算出を打ち切るように制御する。
【００１３】
このような類似度算出方法は、２つのベクトル間の距離算出を階層的に行い、ある階層までに算出された距離の積算値が所定の閾値を上回るものについては閾値以上であることのみを検出して実際の距離を算出しないことにより、演算を高速化する。
【００１４】
また、この類似度算出方法は、上記２つの入力ベクトルに対して所定の変換を施す変換工程を有していてもよく、この場合、上記階層的距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、上記所定の変換に基づく所定の順序で行われる。ここで、上記所定の変換とは、例えば、入力ベクトルを構成する各成分の順序を当該各成分の分散の大きさに従って並べ替える変換、離散コサイン変換、離散フーリエ変換、ウォルシュ−アダマール変換、或いはカルーネン−レーベ変換である。
【００１５】
さらに、この類似度算出方法は、上記変換工程にて変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を上記所定の順序で取り出して階層的な複数の部分ベクトルに分割する分割工程を有していてもよく、この場合、上記階層的距離算出工程では、最上位階層の部分ベクトルから順に部分ベクトルを構成する各成分間の距離算出が階層的に行われ、ある階層までの部分ベクトルを構成する全ての成分間について算出された距離の積算値が上記閾値を下回った場合、一階層下位の部分ベクトルを構成する各成分間の距離算出が行われる。
【００１６】
また、上述した目的を達成するために、本発明に係る類似度算出装置は、２つの入力ベクトル間の類似度を求める類似度算出装置であって、上記２つの入力ベクトル間の距離算出を階層的に行う階層的距離算出手段と、上記階層的距離算出手段によって各階層で算出された距離の積算値を予め設定された閾値と比較する閾値比較手段と、上記閾値比較手段による比較結果に応じて、上記階層的距離算出手段による距離算出を制御する制御手段と、最後の階層までに算出された距離の積算値を上記類似度として出力する出力手段とを備え、上記制御手段は、上記閾値比較工程による比較の結果、ある階層までに算出された距離の積算値が上記閾値を上回った場合、距離算出を打ち切るように制御する。
【００１７】
このような類似度算出装置は、２つのベクトル間の距離算出を階層的に行い、ある階層までに算出された距離の積算値が所定の閾値を上回るものについては閾値以上であることのみを検出して実際の距離を算出しないことにより、演算を高速化する。
【００１８】
また、この類似度算出装置は、上記２つの入力ベクトルに対して所定の変換を施す変換手段を備えていてもよく、この場合、上記階層的距離算出手段は、上記変換手段によって変換された上記２つの入力ベクトル間の距離算出を、上記所定の変換に基づく所定の順序で行う。ここで、上記所定の変換とは、例えば、入力ベクトルを構成する各成分の順序を当該各成分の分散の大きさに従って並べ替える変換、離散コサイン変換、離散フーリエ変換、ウォルシュ−アダマール変換、或いはカルーネン−レーベ変換である。
【００１９】
さらに、この類似度算出装置は、上記変換手段によって変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を上記所定の順序で取り出して階層的な複数の部分ベクトルに分割する分割手段を備えていてもよく、この場合、上記階層的距離算出手段は、最上位階層の部分ベクトルから順に部分ベクトルを構成する各成分間の距離算出を階層的に行い、ある階層までの部分ベクトルを構成する全ての成分間について算出した距離の積算値が上記閾値を下回った場合、一階層下位の部分ベクトルを構成する各成分間の距離算出を行う。
【００２０】
また、本発明に係るプログラムは、上述した類似度算出処理をコンピュータに実行させるものであり、本発明に係る記録媒体は、そのようなプログラムが記録されたコンピュータ読み取り可能なものである。
【００２１】
【発明の実施の形態】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。この実施の形態は、本発明を、複数の登録ベクトルの中から入力ベクトルに類似するベクトルを高速に検出する類似ベクトル検出方法及びその装置に適用したものである。
【００２２】
具体的には、本実施の形態における類似ベクトル検出方法及びその装置では、２つのベクトル間の距離を算出するにあたり、その距離が所定の閾値を下回るものについてはその距離を算出し、所定の閾値を上回るものについては閾値以上であることのみを検出して実際の距離を算出しないことにより、類似ベクトル検出の演算を高速化する。なお、本実施の形態における類似ベクトル検出装置では、距離が閾値を上回る場合には、便宜上−１を出力することとする。
【００２３】
以下、距離を算出する２つのベクトルｆ及びベクトルｇを、以下の式（１）、（２）のように表記する。
【００２４】
【数１】
2004046370.tif 000003
【００２５】
ここで、式（１）において、ｆ［１］，ｆ［２］，…は、ベクトルｆの各成分を表し、式（２）においてｇ［１］，ｇ［２］，…は、ベクトルｇの各成分を表す。また、ｔは転置を表し、Ｎはベクトルの次元を表す。
【００２６】
（１）第１の実施の形態
第１の実施の形態における類似ベクトル検出装置の概略構成を図１に示す。図１に示すように、類似ベクトル検出装置１は、ベクトルｆ、ベクトルｇを入力してそのベクトル間の自乗距離（又は−１）を出力するものであり、記録部１０と、階層的距離演算部１１と、閾値判定部１２とから構成される。
【００２７】
この類似ベクトル検出装置１における登録時の処理を図２のフローチャートを用いて説明する。先ずステップＳ１において、記録部１０（図１）は、予め登録ベクトルｇを入力する。一般にベクトルｇは複数であり、膨大な数になることが多い。そして、続くステップＳ２において、記録部１０は、入力したベクトルｇを記録する。
【００２８】
このように、第１の実施の形態では、登録時に特別な操作を行う必要がないため簡便であり、実時間での処理に適する。なお、記録部１０は、例えば磁気ディスク、光ディスク、或いは半導体メモリ等である。
【００２９】
続いて、類似ベクトル検出装置１における検索時の処理を図３のフローチャートを用いて説明する。先ずステップＳ１０において、閾値判定部１２（図１）は、距離の閾値Ｓを設定し、続くステップＳ１１において、階層的距離演算部１１は、ベクトルｆを入力すると共に、記録部１０に記録されているベクトルｇを１つ取得する。
【００３０】
続いてステップＳ１２において、階層的距離演算部１１は、内部変数である成分番号ｉを１に、距離の積算値ｓｕｍを０にそれぞれセットし、ステップＳ１３において、ベクトルｆの第ｉ成分ｆ［ｉ］とベクトルｇの第ｉ成分ｇ［ｉ］との間で、以下の式（３）で示すような積算演算を行う。
【００３１】
【数２】
2004046370.tif 000004
【００３２】
ステップＳ１４において、閾値判定部１２は、積算値ｓｕｍが閾値Ｓ未満であるか否かを判別する。積算値ｓｕｍが閾値Ｓ未満である場合（Ｙｅｓ）にはステップＳ１６に進み、積算値ｓｕｍが閾値Ｓ以上である場合（Ｎｏ）にはステップＳ１５で閾値判定部１２が−１を出力して処理を終了する。ここで、出力される−１は、上述したように、入力されたベクトルｆと取得されたベクトルｇとの距離が閾値Ｓを上回り、このベクトルｇが棄却されたことを示す便宜的な数値である。このように、閾値判定部１２は、閾値Ｓを設け、積算演算の途中の階層で積算値ｓｕｍが閾値Ｓを上回った場合に階層的距離演算部１１での積算演算を打ち切ることで、処理の高速化を図っている。
【００３３】
ステップＳ１６では、成分番号ｉがベクトルｆ、ベクトルｇの次元数Ｎ以下であるか否かが判別される。成分番号ｉがＮ以下である場合（Ｙｅｓ）には、ステップＳ１７でｉをインクリメントしてステップＳ１３に戻る。一方、成分番号ｉがＮよりも大きい場合（Ｎｏ）には、ベクトルｆ、ベクトルｇの最後の成分まで積算演算が終了しているため、ステップＳ１８で閾値判定部１２が積算値ｓｕｍを出力して処理を終了する。なお、このときの積算値ｓｕｍは、ベクトル間距離の自乗となる。
【００３４】
以上、図３のフローチャートでは、１つの登録ベクトルｇに対する処理を示したが、実際には登録されている全てのベクトルｇについて同様の処理を行い、ベクトルｆとの距離の積算値ｓｕｍが閾値Ｓを下回った全てのベクトルｇを、ベクトルｆに類似するベクトルとして出力する。
【００３５】
以上説明した第１の実施の形態における処理を直観的に説明すると、図４に黒丸で示す多数の登録ベクトルについて、図中×で示す入力ベクトルからの距離が半径√Ｓの超球の範囲内の登録ベクトルに対してのみ正確な距離を算出し、範囲外の登録ベクトルに対しては、各軸毎の距離の積算値が半径を上回った時点で棄却する処理を行っていることに相当する。
【００３６】
なお、上述の説明ではベクトル間の自乗距離を用いたが、自乗距離に限らず、任意の距離尺度に対して同様の手法を用いることができる。但し、自乗距離を用いる場合には、積算値ｓｕｍが各成分間距離の積算値に対して単調に増加するため、誤棄却を発生させることがない。また、各成分間の距離の総和はベクトル間の距離に一致するため、距離が閾値√Ｓ以下であるベクトルｆ、ベクトルｇに関しては、単純な全探索法と全く同じ距離が出力され、誤差が発生することがない。
【００３７】
さらに、この手法では、時系列関係を崩す参照テーブル等を作成する必要がないため、データの更新や削除を時系列順序に従って行うことができ、処理や管理が容易である。また、時系列順序に従って検索を行うことや、検索する時系列範囲を指定することも容易に可能である。
【００３８】
（２）第２の実施の形態
上述した第１の実施の形態では、距離の閾値Ｓを設定することで、全検索と同等の検索を高速に行うことができたが、この手法では、どのベクトル成分から検索を行うかはベクトルの並び順に依存するため、この並び順によって検索速度に差が生じる。例えば、図５のように特徴空間内のベクトルの分布に偏りがあるような場合には、ｆ［１］軸とｆ［２］軸とのどちらを先に積算するかによって検索速度が大きく異なる。この例では、ｆ［２］軸を先に評価する方が余計な積算が少なくなり高速化できる。
【００３９】
そこで、以下に説明する第２の実施の形態では、以下の式（４）、（５）に示すように、入力ベクトルｆ、登録ベクトルｇに対して正規直交変換行列Ｕを乗算して直交変換を行い、この直交変換後のベクトルｆ’、ベクトルｇ’を用いて有意性の高い順に検索を行うことで、さらに検索を高速化する。
【００４０】
【数３】
2004046370.tif 000005
【００４１】
なお、以下の式（６）に示すように、正規直交変換行列Ｕによっては２つのベクトルｇ、ベクトルｆ間の自乗距離ｄ２は変わらない。
【００４２】
【数４】
2004046370.tif 000006
【００４３】
第２の実施の形態における類似ベクトル検出装置の概略構成を図６に示す。図６に示すように、類似ベクトル検出装置２は、ベクトルｆ、ベクトルｇを入力してそのベクトル間の距離（又は−１）を出力するものであり、ベクトル変換部２０，２１と、記録部２２と、階層的距離演算部２３と、閾値判定部２４とから構成される。ここで、ベクトル変換部２０，２１は、それぞれベクトルｇ、ベクトルｆに対して同様の変換を施すものである。また、記録部２２は、例えば磁気ディスク、光ディスク、或いは半導体メモリ等である。
【００４４】
この類似ベクトル検出装置２における登録時の処理を図７のフローチャートを用いて説明する。先ずステップＳ２０において、ベクトル変換部２０（図６）は、予め登録ベクトルｇを入力し、続くステップＳ２１において、上述した式（５）のようにベクトルｇを変換し、ベクトルｇ’を生成する。そして、ステップＳ２において、記録部１０は、変換されたベクトルｇ’を記録する。
【００４５】
続いて、類似ベクトル検出装置２における検索時の処理を図８のフローチャートを用いて説明する。先ずステップＳ３０において、閾値判定部２４（図６）は、距離の閾値Ｓを設定し、続くステップＳ３１において、ベクトル変換部２１がベクトルｆを入力すると共に、階層的距離演算部２３が記録部２２に記録されているベクトルｇ’を１つ取得する。
【００４６】
続いてステップＳ３２において、ベクトル変換部２１は、上述した式（４）のようにベクトルｆを変換し、ベクトルｆ’を生成する。
【００４７】
ステップＳ３３において、階層的距離演算部２３は、内部変数である成分番号ｉを１に、距離の積算値ｓｕｍを０にそれぞれセットし、ステップＳ３４において、ベクトルｆ’の第ｉ成分ｆ’［ｉ］とベクトルｇ’の第ｉ成分ｇ’［ｉ］との間で、以下の式（７）で示すような積算演算を行う。
【００４８】
【数５】
2004046370.tif 000007
【００４９】
ステップＳ３５において、閾値判定部２４は、積算値ｓｕｍが閾値Ｓ未満であるか否かを判別する。積算値ｓｕｍが閾値Ｓ未満である場合（Ｙｅｓ）にはステップＳ３７に進み、積算値ｓｕｍが閾値Ｓ以上である場合（Ｎｏ）にはステップＳ３６で閾値判定部２４が−１を出力して処理を終了する。
【００５０】
ステップＳ３７では、成分番号ｉがベクトルｆ’、ベクトルｇ’の次元数Ｎ以下であるか否かが判別される。成分番号ｉがＮ以下である場合（Ｙｅｓ）には、ステップＳ３８でｉをインクリメントしてステップＳ３４に戻る。一方、成分番号ｉがＮよりも大きい場合（Ｎｏ）には、ベクトルｆ’、ベクトルｇ’の最後の成分まで積算演算が終了しているため、ステップＳ３９で閾値判定部２４が積算値ｓｕｍを出力して処理を終了する。なお、このときの積算値ｓｕｍは、ベクトル間距離の自乗となる。
【００５１】
以上、図８のフローチャートでは、１つの登録ベクトルｇ’に対する処理を示したが、実際には登録されている全てのベクトルｇ’について同様の処理を行い、ベクトルｆ’との距離の積算値ｓｕｍが閾値Ｓを下回った全てのベクトルｇ’を、ベクトルｆ’に類似するベクトルとして出力する。
【００５２】
ここで、上述した正規直交変換行列Ｕとしては、種々のものを用いることができるが、以下では、具体的に４つの例を挙げて説明する。
【００５３】
（２−１）直交変換の具体例
（２−１−１）
直交変換の最も簡単なものとして順序行列が挙げられる。これは、単純にベクトル成分の順序を並べ替えるものであり、例えば８次の順序行列Ｐは、以下の式（８）に示すような形で表される。
【００５４】
【数６】
2004046370.tif 000008
【００５５】
上述した図５のようにベクトルの各成分の分布が異なる場合、明らかに分散の大きな成分ほど距離に対する寄与が大きい。したがって、並べ替えの順序を決定する際には、予め十分な数（Ｉ個）のサンプルベクトルｇｉを用意し、以下の式（９）で計算される分散ベクトルＶの大きい順に並ぶような順序行列を設定するのが最適である。
【００５６】
【数７】
2004046370.tif 000009
【００５７】
なお、この順序行列を用いた直交変換は、各ベクトル成分の広がり方が異なるような場合に有効であり、並べ替えのみでよく乗除算や条件分岐が必要ないため高速である。
【００５８】
（２−１−２）
映像特徴量や音響特徴量など、隣接成分間の相関関係が大きい特徴量では、特徴ベクトルを離散信号とみなした場合のエネルギが低周波成分に偏る。
【００５９】
そこで、直交変換として、以下の式（１０）、（１１）で表される離散コサイン変換（Ｄｉｓｃｒｅｔｅ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｒｍ：ＤＣＴ）や、以下の式（１２）、（１３）で表される離散フーリエ変換（Ｄｉｓｃｒｅｔｅ　Ｆｏｕｒｉｅｒ　Ｔｒａｎｓｆｏｒｍ：ＤＦＴ）を用い、低周波成分から順に積算を行うことで、有意性の高い成分から順に積算することができ、距離計算が高速化される。
【００６０】
【数８】
2004046370.tif 000010
【００６１】
【数９】
2004046370.tif 000011
【００６２】
ここで、離散コサイン変換や離散フーリエ変換には高速変換法を用いることができ、また変換行列も全部を保持する必要がないため、計算機で実現する場合のメモリ使用量や演算速度は、行列の全計算を行う場合よりも遙かに有利である。
【００６３】
（２−１−３）
ウォルシュ−アダマール（Ｗａｌｓｈ−Ｈａｄａｍａｒｄ）変換は、変換行列の各要素が±１のみで構成される直交変換であり、変換時に乗算が必要ないため、高速な変換に適する。ここで、周波数に近い概念として交番数（ｓｅｑｕｅｎｃｙ）を用い、低交番数の成分から順に並べることで、上述した離散コサイン変換や離散フーリエ変換と同様に、隣接成分間の相関関係が大きなベクトルに対して距離計算の高速化が図られる。
【００６４】
ウォルシュ−アダマール変換行列は、フーリエ変換行列の符号に従って構成するか、又は行列の再帰的拡大演算によって構成する。一例として、交番数順に並べた８次のウォルシュ−アダマール変換行列Ｗを以下の式（１４）に示す。
【００６５】
【数１０】
2004046370.tif 000012
【００６６】
（２−１−４）
予め十分な数のサンプルベクトルが収集され、また、変換演算に多少のコストをかけてもよい場合には、直交変換として最適なカルーネン−レーベ（Ｋａｒｈｕｎｅｎ−Ｌｏｅｖｅ）変換（以下、ＫＬ変換という。）を用いることが有効である。
【００６７】
ＫＬ変換行列Ｔは、サンプルベクトルの分散行列Ｖを固有値分解する固有行列であり、固有値をλ１，…，λＮとした場合に、以下の式（１５）のように定義される。
【００６８】
【数１１】
2004046370.tif 000013
【００６９】
ここで、ＫＬ変換は、各成分間の相関関係を完全に取り除く直交変換行列であり、変換されたベクトル成分の分散が固有値λｉとなる。したがって、固有値λｉを大きい順に並べるようにＫＬ変換行列Ｔを構成することで、全ての成分を統合し重複する情報を取り除いた上で、最も分散の大きい軸から距離の積算を行うことができる。
【００７０】
なお、このＫＬ変換を用いた手法では、演算時にＫＬ変換行列Ｔを原則として全次元に亘って保持する必要があり、また、全てのベクトルに対して全次数の行列演算を行う必要があるため、演算コストがかかる。しかしながら、この演算は登録時に行うものであるため、特に高速化が要求される検索処理に要する時間を増やすものではない。
【００７１】
また、若干の精度の劣化は伴うものの、固有値の大きいベクトル成分のみを抽出して保持し、固有値の小さいベクトル成分は保持しないようにすることで、ベクトル自体を圧縮し、記録部２２（図６）の記憶領域やデータ読み込み時間を低減することもできる。
【００７２】
（３）第３の実施の形態
上述した第１、第２の実施の形態では、距離計算の高速化により検索演算を高速化したが、検索する際には、例えばハードディスク等の記録部からのデータ読み込み時間も大きなオーバーヘッドの要因となる。
【００７３】
ここで、上述した第２の実施の形態におけるＫＬ変換は、多変量解析分野で主成分分析と呼ばれる分析法にあたり、ベクトルを構成する主要な成分を抽出する演算となっている。そこで、以下に説明する第３の実施の形態では、第２の実施の形態で得られた変換後のベクトルｇ’の主要成分を索引ベクトルｇ１、残りの成分を詳細ベクトルｇ２として記録する。検索時には、先ず索引ベクトルｇ１を参照して距離計算を行い、その結果が閾値Ｓ未満である場合にのみ詳細ベクトルｇ２を取得してさらに距離計算を行うことで、データ読み込み時間の短縮化を図ることができる。
【００７４】
第３の実施の形態における類似ベクトル検出装置の概略構成を図９に示す。図９に示すように、類似ベクトル検出装置３は、ベクトルｆ、ベクトルｇを入力してそのベクトル間の自乗距離（又は−１）を出力するものであり、ベクトル変換部３０，３１と、索引記録部３２と、詳細記録部３３と、階層的距離演算部３４と、閾値判定部３５とから構成される。ここで、ベクトル変換部３０，３１は、それぞれベクトルｇ、ベクトルｆに対して上述した第２の実施の形態と同様の変換を施すものである。また、索引記録部３２、詳細記録部３３は、例えば磁気ディスク、光ディスク、或いは半導体メモリ等である。
【００７５】
この類似ベクトル検出装置３における登録時の処理を図１０のフローチャートを用いて説明する。先ずステップＳ４０において、ベクトル変換部３０（図９）は、予め登録ベクトルｇを入力し、続くステップＳ４１において、上述した式（５）のようにベクトルｇを変換し、ベクトルｇ’を生成する。さらにベクトル変換部３０は、成分番号の小さいもの、すなわち上述した変換で分散や固有値の大きい成分、或いは低周波成分から順に、所定数Ｍ（１≦Ｍ＜Ｎ）の成分を持つ索引ベクトルｇ１と、残りの成分を持つ詳細ベクトルｇ２とに分割する。そしてステップＳ４２において、索引記録部３２が索引ベクトルｇ１を記録し、ステップＳ４３において、詳細記録部３３が詳細ベクトルｇ２を記録する。
【００７６】
続いて、類似ベクトル検出装置３における検索時の処理を図１１のフローチャートを用いて説明する。先ずステップＳ５０において、閾値判定部３５（図９）は、距離の閾値Ｓを設定し、続くステップＳ５１において、ベクトル変換部３１がベクトルｆを入力すると共に、階層的距離演算部３４が索引記録部３２に記録されている索引ベクトルｇ１を１つ取得する。
【００７７】
続いてステップＳ５２において、ベクトル変換部３１は、上述した式（４）のようにベクトルｆを変換し、ベクトルｆ’を生成する。さらにベクトル変換部３１は、成分番号の小さいものから順に、所定数Ｍ（１≦Ｍ＜Ｎ）の成分を持つ索引ベクトルｆ１と、残りの成分を持つ詳細ベクトルｆ２とに分割する。
【００７８】
ステップＳ５３において、階層的距離演算部３４は、内部変数である成分番号ｉを１に、距離の積算値ｓｕｍを０にそれぞれセットし、ステップＳ５４において、ベクトルｆ’の第ｉ成分ｆ’［ｉ］とベクトルｇ’の第ｉ成分ｇ’［ｉ］との間で、以下の式（１６）で示すような積算演算を行う。
【００７９】
【数１２】
2004046370.tif 000014
【００８０】
ステップＳ５５において、閾値判定部３５は、積算値ｓｕｍが閾値Ｓ未満であるか否かを判別する。積算値ｓｕｍが閾値Ｓ未満である場合（Ｙｅｓ）にはステップＳ５７に進み、積算値ｓｕｍが閾値Ｓ以上である場合（Ｎｏ）にはステップＳ５６で閾値判定部３５が−１を出力して処理を終了する。ここで、出力される−１は、上述したように、距離が閾値を上回り棄却されたことを示す便宜的な数値である。
【００８１】
ステップＳ５７では、成分番号ｉが索引ベクトルｆ１、索引ベクトルｇ１の次元数Ｍ以下であるか否かが判別される。成分番号ｉがＭ以下である場合（Ｙｅｓ）には、ステップＳ５８でｉをインクリメントしてステップＳ５４に戻る。一方、成分番号ｉがＭよりも大きい場合（Ｎｏ）には、階層的距離演算部３４は、詳細記録部３３に記録されている詳細ベクトルｇ２を１つ取得する。
【００８２】
ステップＳ６０において、階層的距離演算部３４は、ベクトルｆ’の第ｉ成分ｆ’［ｉ］とベクトルｇ’の第ｉ成分ｇ’［ｉ］との間で、上述の式（１６）で示すような積算演算を行う。
【００８３】
ステップＳ６１において、閾値判定部３５は、積算値ｓｕｍが閾値Ｓ未満であるか否かを判別する。積算値ｓｕｍが閾値Ｓ未満である場合（Ｙｅｓ）にはステップＳ６３に進み、積算値ｓｕｍが閾値Ｓ以上である場合（Ｎｏ）にはステップＳ６２で閾値判定部３５が−１を出力して処理を終了する。
【００８４】
ステップＳ６３では、成分番号ｉがベクトルｆ’、ベクトルｇ’の次元数Ｎ以下であるか否かが判別される。成分番号ｉがＮ以下である場合（Ｙｅｓ）には、ステップＳ６４でｉをインクリメントしてステップＳ６０に戻る。一方、成分番号ｉがＮよりも大きい場合（Ｎｏ）には、ベクトルｆ’、ベクトルｇ’の最後の成分まで積算が終了しているため、ステップＳ６５で閾値判定部３５が積算値ｓｕｍを出力して処理を終了する。このとき積算値ｓｕｍは、ベクトル間距離の自乗となる。
【００８５】
以上、図１１のフローチャートでは、１つの登録ベクトルｇ’に対する処理を示したが、実際には登録されている全てのベクトルｇ’について同様の処理を行い、ベクトルｆ’との距離の積算値ｓｕｍが閾値Ｓを下回った全てのベクトルｇ’を、ベクトルｆ’に類似するベクトルとして出力する。
【００８６】
上述した第３の実施の形態では、第１、第２の実施の形態と比較して記憶容量や精度は変わらず、演算速度も殆ど変わらないが、大半の比較が索引ベクトルｇ１の段階で棄却され詳細ベクトルｇ２を取得する必要が少ない場合に、データアクセスによるオーバーヘッドが解消される。
【００８７】
なお、上述の説明では、ベクトルを索引ベクトルと詳細ベクトルとの２段階に分割するものとしたが、同様に索引ベクトルをさらに上位の索引ベクトルと詳細な索引ベクトルに分割して３段構成にするなど、多段化への拡張が可能であることは勿論である。
【００８８】
（４）特徴ベクトルの抽出
以下では、音響信号や映像信号から特徴ベクトルを抽出する手法について説明する。後述のようにして音響特徴ベクトル及び／又は映像特徴ベクトルを抽出し、これを上述したベクトルｆ、ベクトルｇとして用いることで、音響信号や映像信号が入力された場合に、上述の第１乃至第３の実施の形態の手法を用いて、登録された音響信号や映像信号から、類似する音響信号や映像信号を高速に検索することができる。
【００８９】
（４−１）音響特徴ベクトルの抽出
（４−１−１）
音響信号に関する特徴量としてパワースペクトル係数を用いる場合の例について、図１２のフローチャートと図１３を用いて説明する。先ずステップＳ７０において、図１３に示すように、対象時区間内の音響信号から時間区間Ｔ毎の音響信号を取得する。
【００９０】
次にステップＳ７１では、取得した音響信号に対して例えば高速フーリエ変換等のスペクトル演算を施し、短時間区間毎にパワースペクトル係数Ｓｑ（ｑ＝０，１，…，Ｑ−１）を求める。ここで、ｑは離散周波数を表すインデックスであり、Ｑは最大離散周波数である。
【００９１】
続いてステップＳ７２では、対象時区間内の計算を終えたか否かが判別され、終えている場合（Ｙｅｓ）にはステップＳ７３に進み、終えていない場合（Ｎｏ）にはステップＳ７０に戻る。
【００９２】
ステップＳ７３では、求めたパワースペクトル係数Ｓｑの平均スペクトルＳ’ｑを計算し、ステップＳ７４においてこの平均スペクトルＳ’ｑをベクトル化し、音響特徴ベクトルａを生成する。この音響特徴ベクトルａは、例えば以下の式（１７）のように表される。
【００９３】
【数１３】
2004046370.tif 000015
【００９４】
なお、上述の例では、対象時区間内の音響信号を時間区間Ｔ毎に区切るものとして説明したが、対象時区間が短い場合には、時間区間Ｔ毎に区切らずにスペクトル演算を施すようにしても構わない。
【００９５】
また、上述の例では、パワースペクトル係数を用いた例について説明したが、これに限定されるものではなく、例えば等価な情報を持つケプストラム係数等を用いることもできる。さらに、フーリエ変換ではなくＡＲ（Ａｕｔｏ−Ｒｅｇｒｅｓｓｉｖｅ）モデルを用いる線形予測係数によっても同様の効果を得ることができる。
【００９６】
（４−１−２）
音響信号は膨大であるため、圧縮符号化されて記録、或いは伝送されることが多い。符号化された音響信号を復号してベースバンドに戻した後、上述の手法を用いて音響特徴ベクトルａを抽出することも可能であるが、部分的な復号のみで音響特徴ベクトルａを抽出できれば、抽出処理を効率化、高速化することができる。
【００９７】
ここで、一般的に用いられる符号化法である変換符号化では、図１４に示すように、原音となる音響信号が時間区間Ｔ毎にフレームに区切られる。そして、そのフレーム毎の音響信号に対して変更離散コサイン変換（Ｍｏｄｉｆｉｅｄ　Ｄｉｓｃｒｅｔｅ　Ｃｏｓｉｎｅ　Ｔｒａｎｓｆｏｒｍ：ＭＤＣＴ）等の直交変換が施され、その係数が量子化されて符号化される。この際、周波数帯域毎に、大きさの正規化係数であるスケールファクタが抽出され、別途符号化される。そこで、このスケールファクタのみを復号することにより、音響特徴ベクトルａとして用いることができる。
【００９８】
このように、音響信号に関する特徴量としてスケールファクタを用いる場合の例について、図１５のフローチャートと図１６を用いて説明する。先ずステップＳ８０において、対象時区間における時間区間Ｔ内の符号化音響信号が取得され、ステップＳ８１において、フレーム毎のスケールファクタが部分的に復号される。
【００９９】
続いてステップＳ８２では、対象時区間内の復号を終えたか否かが判別され、終えている場合（Ｙｅｓ）にはステップＳ８３に進み、終えていない場合（Ｎｏ）にはステップＳ８０に戻る。
【０１００】
ステップＳ８３では、対象時区間内のスケールファクタの中から各帯域毎に最大のスケールファクタを検出し、ステップＳ８４においてそれらをベクトル化し、音響特徴ベクトルａを生成する。
【０１０１】
このようにして、符号化音響信号を完全に復号することなく、上述と等価な音響特徴ベクトルａを高速に抽出することができる。
【０１０２】
（４−２）映像特徴ベクトルの抽出
（４−２−１）
映像信号に関する特徴量として輝度情報及び色情報を用いる場合の例について、図１７のフローチャート及び図１８を用いて説明する。先ずステップＳ９０において、図１８に示すように、対象時区間Ｔ内の映像信号から映像フレームを取得する。
【０１０３】
次にステップＳ９１では、取得した全ての映像フレームに基づいて、時間平均画像を作成する。
【０１０４】
続いてステップＳ９２では、作成された時間平均画像を横縦Ｘ×Ｙ個の小ブロックに分割し、各ブロック内の画素値を平均したブロック平均画像を作成する。
【０１０５】
そしてステップＳ９３では、これらを例えば左上から右下へ向かってＲ，Ｇ，Ｂの順に並べて、１次元の映像特徴ベクトルｖを生成する。この映像特徴ベクトルｖは、例えば以下の式（１８）のように表される。
【０１０６】
【数１４】
2004046370.tif 000016
【０１０７】
なお、上述の例では、時間平均画像を分割したブロック平均画像の画素値を並べ替えて１次元の映像特徴ベクトルｖを生成する例について説明したが、これに限定されるものではなく、ブロック平均画像を作成せずに、時間平均画像の画素値を並べ替えて１次元の映像特徴ベクトルｖを生成するようにしても構わない。
【０１０８】
また、通常、映像信号の時間変化はあまり激しくないため、時間平均画像を作成せずに、対象時区間内の１フレームを代表画像として選択して代用しても、ほぼ同様の効果を得ることができる。
【０１０９】
（４−２−２）
全く同一な映像信号でなくても、例えばニュース映像の同じアングルから撮影されたスタジオ映像など、全画像に対する色の分布が類似する映像には何らかの関連があることが多く、これらを同一視して検索する要求もある。このような場合には、画像の空間依存性を排除し、色分布のヒストグラムを作成して比較すると効果的である。
【０１１０】
そこで、このように色分布のヒストグラムを特徴量として用いる場合の例について、図１９のフローチャート及び図２０を用いて説明する。先ずステップＳ１００において、図２０に示すように、対象時区間Ｔ内の映像信号から映像フレームを取得する。
【０１１１】
次にステップＳ１０１では、各映像フレームの信号値から、各色、例えばＲ，Ｇ，Ｂの信号値に対するヒストグラムを作成する。
【０１１２】
そしてステップＳ１０２では、これらを例えばＲ，Ｇ，Ｂの順に並べて、１次元の映像特徴ベクトルｖを生成する。この映像特徴ベクトルｖは、例えば以下の式（１９）のように表される。
【０１１３】
【数１５】
2004046370.tif 000017
【０１１４】
なお、上述の例では、Ｒ，Ｇ，Ｂの信号値に対するヒストグラムを作成するものとして説明したが、輝度（Ｙ）、色差（Ｃｂ、Ｃｒ）の信号値に対するヒストグラムを作成するようにしても、同様の効果を得ることができる。
【０１１５】
（４−２−３）
映像信号は膨大であるため、圧縮符号化されて記録、或いは伝送されることが多い。符号化された映像信号を復号してベースバンドに戻した後、上述の手法を用いて映像特徴ベクトルｖを抽出することも可能であるが、部分的な復号のみで映像特徴ベクトルｖを抽出できれば、抽出処理を効率化、高速化することができる。
【０１１６】
ＭＰＥＧ１（Ｍｏｖｉｎｇ　Ｐｉｃｔｕｒｅ　Ｅｘｐｅｒｔｓ　Ｇｒｏｕｐ　１）又はＭＰＥＧ２で圧縮符号化された映像信号から映像特徴ベクトルｖを抽出する場合の例について、図２１のフローチャートと図２２を用いて説明する。先ずステップＳ１１０において、ベクトル化する対象時区間Ｔに対して、その直近の符号化グループ（Ｇｒｏｕｐ　ｏｆ　Ｐｉｃｔｕｒｅｓ：ＧＯＰ）の符号化映像信号を取得し、そのＧＯＰ内のフレーム内符号化ピクチャ（Ｉピクチャ）を取得する。
【０１１７】
ここで、フレーム画像は、マクロブロック（１６×１６画素、又は８×８画素）を単位として符号化されており、また、離散コサイン変換（ＤＣＴ）が用いられている。このＤＣＴ変換されたＤＣ係数は、マクロブロック内画像の画素値の平均値にあたる。
【０１１８】
そこで、ステップＳ１１１では、このＤＣ係数を取得し、続くステップＳ１１２では、これらを例えばＹ，Ｃｂ，Ｃｒの順に並べて、１次元の映像特徴ベクトルｖを生成する。この映像特徴ベクトルｖは、例えば以下の式（２０）のように表される。
【０１１９】
【数１６】
2004046370.tif 000018
【０１２０】
このようにして、符号化映像信号を完全に復号することなく、映像特徴ベクトルｖを高速に抽出することができる。
【０１２１】
なお、上述の例では、ＭＰＥＧ１又はＭＰＥＧ２で圧縮符号化された映像信号を用いるものとして説明したが、他の圧縮符号化方式にも適用可能である。
【０１２２】
（５）その他
以上説明したように、本実施の形態によれば、ベクトル間の距離に基づいて類似ベクトルを検出する際に、階層的な距離積算演算を行い、予め設定された距離に対する閾値を上回った時点で打ち切ることで、類似ベクトルを高速に検出することができる。特に、大量の登録ベクトルの中から、入力ベクトルと類似するベクトルを検出するような場合には、殆どの登録ベクトルは非類似であり閾値を上回ってしまうため、距離計算を早期に打ち切ることができ、検出時間を大幅に短縮することができる。
【０１２３】
また、予めベクトルに対して順序変換、離散コサイン変換、離散フーリエ変換、ウォルシュ−アダマール変換、或いはＫＬ変換を施し、有意性の高いベクトル成分、すなわち、上述の変換で分散や固有値の大きい成分、或いは低周波成分から順に積算演算を行うようにすることで、ベクトル成分の分布を考慮して、効率的且つ高速に類似するベクトルを検出することができる。
【０１２４】
したがって、音響信号や映像信号の検索を行う際にも、予め音響特徴ベクトル及び／又は映像特徴ベクトルを抽出して登録しておくことで、任意の音響信号や映像信号が入力された場合に、全検索と同様の構造的シンプルさや検索精度を保持したまま、類似する音響信号や映像信号を高速に検索することができる。
【０１２５】
なお、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【０１２６】
例えば、上述の実施の形態では、ハードウェアの構成として説明したが、これに限定されるものではなく、任意の処理を、ＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）にコンピュータプログラムを実行させることにより実現することも可能である。この場合、コンピュータプログラムは、記録媒体に記録して提供することも可能であり、また、インターネットその他の伝送媒体を介して伝送することにより提供することも可能である。
【０１２７】
【発明の効果】
以上詳細に説明したように本発明に係る類似度算出方法は、２つの入力ベクトル間の類似度を求める類似度算出方法であって、上記２つの入力ベクトル間の距離算出を階層的に行う階層的距離算出工程と、上記階層的距離算出工程の各階層で算出された距離の積算値を予め設定された閾値と比較する閾値比較工程と、上記閾値比較工程における比較結果に応じて、上記階層的距離算出工程における距離算出を制御する制御工程と、最後の階層までに算出された距離の積算値を上記類似度として出力する出力工程とを有し、上記制御工程では、上記閾値比較工程において、ある階層までに算出された距離の積算値が上記閾値を上回った場合、距離算出を打ち切るように制御する。
【０１２８】
このような類似度算出方法によれば、２つのベクトル間の距離算出を階層的に行い、ある階層までに算出された距離の積算値が所定の閾値を上回るものについては閾値以上であることのみを検出して実際の距離を算出しないことにより、演算を高速化することができる。特に、大量の登録ベクトルの中から、入力ベクトルと類似するベクトルを検出するような場合には、殆どの登録ベクトルは非類似であり閾値を上回ってしまうため、距離算出を早期に打ち切ることができ、検出時間を大幅に短縮することができる。
【０１２９】
また、この類似度算出方法は、上記２つの入力ベクトルに対して所定の変換を施す変換工程を有していてもよく、この場合、上記階層的距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、上記所定の変換に基づく所定の順序で行われる。ここで、上記所定の変換とは、例えば、入力ベクトルを構成する各成分の順序を当該各成分の分散の大きさに従って並べ替える変換、離散コサイン変換、離散フーリエ変換、ウォルシュ−アダマール変換、或いはカルーネン−レーベ変換である。
【０１３０】
このような変換を予め入力ベクトルに施し、有意性の高いベクトル成分、すなわち、上述の変換で分散や固有値の大きい成分、或いは低周波成分から順に積算演算を行うようにすることで、ベクトル成分の分布を考慮して、効率的且つ高速に類似するベクトルを検出することができる。
【０１３１】
さらに、この類似度算出方法は、上記変換工程にて変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を上記所定の順序で取り出して階層的な複数の部分ベクトルに分割する分割工程を有していてもよく、この場合、上記階層的距離算出工程では、最上位階層の部分ベクトルから順に部分ベクトルを構成する各成分間の距離算出が階層的に行われ、ある階層までの部分ベクトルを構成する全ての成分間について算出された距離の積算値が上記閾値を下回った場合、一階層下位の部分ベクトルを構成する各成分間の距離算出が行われる。
【０１３２】
このように複数の部分ベクトルに分割し、最上位階層の部分ベクトルから順に階層的に距離算出を行うことで、大半の比較が上位の階層で棄却され下位の階層を取得する必要が少ない場合に、データアクセスによるオーバーヘッドを解消することができる。
【０１３３】
また、本発明に係る類似度算出装置は、２つの入力ベクトル間の類似度を求める類似度算出装置であって、上記２つの入力ベクトル間の距離算出を階層的に行う階層的距離算出手段と、上記階層的距離算出手段によって各階層で算出された距離の積算値を予め設定された閾値と比較する閾値比較手段と、上記閾値比較手段による比較結果に応じて、上記階層的距離算出手段による距離算出を制御する制御手段と、最後の階層までに算出された距離の積算値を上記類似度として出力する出力手段とを備え、上記制御手段は、上記閾値比較工程による比較の結果、ある階層までに算出された距離の積算値が上記閾値を上回った場合、距離算出を打ち切るように制御する。
【０１３４】
このような類似度算出装置によれば、２つのベクトル間の距離算出を階層的に行い、ある階層までに算出された距離の積算値が所定の閾値を上回るものについては閾値以上であることのみを検出して実際の距離を算出しないことにより、演算を高速化することができる。特に、大量の登録ベクトルの中から、入力ベクトルと類似するベクトルを検出するような場合には、殆どの登録ベクトルは非類似であり閾値を上回ってしまうため、距離算出を早期に打ち切ることができ、検出時間を大幅に短縮することができる。
【０１３５】
また、この類似度算出装置は、上記２つの入力ベクトルに対して所定の変換を施す変換手段を備えていてもよく、この場合、上記階層的距離算出手段は、上記変換手段によって変換された上記２つの入力ベクトル間の距離算出を、上記所定の変換に基づく所定の順序で行う。ここで、上記所定の変換とは、例えば、入力ベクトルを構成する各成分の順序を当該各成分の分散の大きさに従って並べ替える変換、離散コサイン変換、離散フーリエ変換、ウォルシュ−アダマール変換、或いはカルーネン−レーベ変換である。
【０１３６】
このような変換を予め入力ベクトルに施し、有意性の高いベクトル成分、すなわち、上述の変換で分散や固有値の大きい成分、或いは低周波成分から順に積算演算を行うようにすることで、ベクトル成分の分布を考慮して、効率的且つ高速に類似するベクトルを検出することができる。
【０１３７】
さらに、この類似度算出装置は、上記変換手段によって変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を上記所定の順序で取り出して階層的な複数の部分ベクトルに分割する分割手段を備えていてもよく、この場合、上記階層的距離算出手段は、最上位階層の部分ベクトルから順に部分ベクトルを構成する各成分間の距離算出を階層的に行い、ある階層までの部分ベクトルを構成する全ての成分間について算出した距離の積算値が上記閾値を下回った場合、一階層下位の部分ベクトルを構成する各成分間の距離算出を行う。
【０１３８】
このように複数の部分ベクトルに分割し、最上位階層の部分ベクトルから順に階層的に距離算出を行うことで、大半の比較が上位の階層で棄却され下位の階層を取得する必要が少ない場合に、データアクセスによるオーバーヘッドを解消することができる。
【０１３９】
また、本発明に係るプログラムは、上述した類似度算出処理をコンピュータに実行させるものであり、本発明に係る記録媒体は、そのようなプログラムが記録されたコンピュータ読み取り可能なものである。
【０１４０】
このようなプログラム及び記録媒体によれば、上述した類似度算出処理をソフトウェアにより実現することができる。
【図面の簡単な説明】
【図１】第１の実施の形態における類似ベクトル検出装置の概略構成を説明する図である。
【図２】同類似ベクトル検出装置におけるベクトル登録時の処理を説明するフローチャートである。
【図３】同類似ベクトル検出装置におけるベクトル検索時の処理を説明するフローチャートである。
【図４】第１の実施の形態における処理を直観的に説明するための図である。
【図５】特徴空間内のベクトルの分布に偏りがある例を示す図である。
【図６】第２の実施の形態における類似ベクトル検出装置の概略構成を説明する図である。
【図７】同類似ベクトル検出装置におけるベクトル登録時の処理を説明するフローチャートである。
【図８】同類似ベクトル検出装置におけるベクトル検索時の処理を説明するフローチャートである。
【図９】第３の実施の形態における類似ベクトル検出装置の概略構成を説明する図である。
【図１０】同類似ベクトル検出装置におけるベクトル登録時の処理を説明するフローチャートである。
【図１１】同類似ベクトル検出装置におけるベクトル検索時の処理を説明するフローチャートである。
【図１２】音響信号から音響特徴ベクトルを抽出する処理の一例を説明するフローチャートである。
【図１３】音響信号から音響特徴ベクトルを抽出する処理の一例を説明する図である。
【図１４】音響信号における変換符号化を説明する図である。
【図１５】符号化音響信号から音響特徴ベクトルを抽出する処理の一例を説明するフローチャートである。
【図１６】符号化音響信号から音響特徴ベクトルを抽出する処理の一例を説明する図である。
【図１７】映像信号から映像特徴ベクトルを抽出する処理の一例を説明するフローチャートである。
【図１８】映像信号から映像特徴ベクトルを抽出する処理の一例を説明する図である。
【図１９】映像信号から映像特徴ベクトルを抽出する処理の他の例を説明するフローチャートである。
【図２０】映像信号から映像特徴ベクトルを抽出する処理の他の例を説明する図である。
【図２１】符号化映像信号から映像特徴ベクトルを抽出する処理の他の例を説明するフローチャートである。
【図２２】符号化映像信号から映像特徴ベクトルを抽出する処理の他の例を説明する図である。
【符号の説明】
１，２，３　類似ベクトル検出装置、１０，２２　記録部、１１，２３，３４階層的距離演算部、１２，２４，３５　閾値判定部、２０，２１，３０，３１ベクトル変換部、３２　索引記録部、３３　詳細記録部
【図１】
2004046370.tif 000019
【図２】
2004046370.tif 000020
【図３】
2004046370.tif 000021
【図４】
2004046370.tif 000022
【図５】
2004046370.tif 000023
【図６】
2004046370.tif 000024
【図７】
2004046370.tif 000025
【図８】
2004046370.tif 000026
【図９】
2004046370.tif 000027
【図１０】
2004046370.tif 000028
【図１１】
2004046370.tif 000029
【図１２】
2004046370.tif 000030
【図１３】
2004046370.tif 000031
【図１４】
2004046370.tif 000032
【図１５】
2004046370.tif 000033
【図１６】
2004046370.tif 000034
【図１７】
2004046370.tif 000035
【図１８】
2004046370.tif 000036
【図１９】
2004046370.tif 000037
【図２０】
2004046370.tif 000038
【図２１】
2004046370.tif 000039
【図２２】
2004046370.tif 000040