【手続補正書】
【提出日】平成17年6月30日(2005.6.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
２つの入力ベクトル間の類似度を求める類似度算出方法であって、
上記２つの入力ベクトルに対して所定の変換を施す変換工程と、
上記変換工程にて変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を所定の順序で取り出して複数の部分ベクトルに分割する分割工程と、
上記部分ベクトル毎に、上記２つの入力ベクトル間の距離算出を行う距離算出工程と、
上記距離算出工程で算出された上記部分ベクトル毎の距離の積算値を、予め設定された閾値と比較する閾値比較工程と、
上記閾値比較工程における比較結果に応じて、上記距離算出工程における距離算出を制御する制御工程と、
算出された最後の部分ベクトルまでの距離の積算値を上記類似度として出力する出力工程とを有し、
上記制御工程では、ある部分ベクトルまでに算出された距離の積算値が上記閾値比較工程において上記閾値を上回った場合に距離算出を打ち切るように制御すること
を特徴とする類似度算出方法。
【請求項２】
上記距離算出工程では、ある部分ベクトルまでに算出された距離の積算値が上記閾値を下回った場合、次の部分ベクトルの距離算出が行われることを特徴とする請求項１記載の類似度算出方法。
【請求項３】
上記所定の変換は、上記２つの入力ベクトルを構成する各成分の順序を当該各成分の分散の大きさに従って並べ替える変換であり、
上記距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、分散の大きな成分から順に行われること
を特徴とする請求項１記載の類似度算出方法。
【請求項４】
上記所定の変換は、離散コサイン変換又は離散フーリエ変換であり、
上記距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、低周波成分から順に行われること
を特徴とする請求項１記載の類似度算出方法。
【請求項５】
上記所定の変換は、ウォルシュ−アダマール変換であり、
上記距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、低交番数成分から順に行われること
を特徴とする請求項１記載の類似度算出方法。
【請求項６】
上記所定の変換は、カルーネン−レーベ変換であり、
上記距離算出工程では、上記変換工程にて変換された上記２つの入力ベクトル間の距離算出が、固有値の大きな成分から順に行われること
を特徴とする請求項１記載の類似度算出方法。
【請求項７】
上記入力ベクトルは、音響信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記音響信号の所定の時区間内のパワースペクトル係数をベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項８】
上記入力ベクトルは、音響信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記音響信号の所定の時区間内の線形予測係数をベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項９】
上記入力ベクトルは、符号化音響信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記符号化音響信号の各フレーム内の周波数成分の強さを表すパラメータをベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項１０】
上記入力ベクトルは、映像信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記映像信号の所定の時区間内の代表画像、上記所定の時区間内のフレーム画像の平均画像、又は上記代表画像若しくは上記平均画像を所定のブロック単位に分割した小画像の信号値をベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項１１】
上記入力ベクトルは、映像信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記映像信号の所定の時区間内のフレーム画像の、輝度及び／又は色に対するヒストグラムをベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項１２】
上記入力ベクトルは、符号化映像信号を特徴ベクトル化したものであり、
上記特徴ベクトルは、上記符号化映像信号の所定の時区間の直近にあるフレーム内符号化画像の符号化単位となる各ブロックのＤＣ成分の信号値をベクトル化したものであること
を特徴とする請求項１記載の類似度算出方法。
【請求項１３】
２つの入力ベクトル間の類似度を求める類似度算出装置であって、
上記２つの入力ベクトルに対して所定の変換を施す変換手段と、
上記変換手段によって変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を所定の順序で取り出して複数の部分ベクトルに分割する分割手段と、
上記部分ベクトル毎に、上記２つの入力ベクトル間の距離算出を行う距離算出手段と、
上記距離算出手段によって算出された上記部分ベクトル毎の距離の積算値を、予め設定された閾値と比較する閾値比較手段と、
上記閾値比較手段による比較結果に応じて、上記距離算出手段による距離算出を制御する制御手段と、
算出された最後の部分ベクトルまでの距離の積算値を上記類似度として出力する出力手段とを備え、
上記制御手段は、上記閾値比較手段による比較の結果、ある部分ベクトルまでに算出された距離の積算値が上記閾値を上回った場合に距離算出を打ち切るように制御すること
を特徴とする類似度算出装置。
【請求項１４】
２つの入力ベクトル間の類似度を求める類似度算出処理をコンピュータに実行させるプログラムであって、
上記２つの入力ベクトルに対して所定の変換を施す変換工程と、
上記変換工程にて変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を所定の順序で取り出して複数の部分ベクトルに分割する分割工程と、
上記部分ベクトル毎に、上記２つの入力ベクトル間の距離算出を行う距離算出工程と、
上記距離算出工程で算出された上記部分ベクトル毎の距離の積算値を、予め設定された閾値と比較する閾値比較工程と、
上記閾値比較工程における比較結果に応じて、上記距離算出工程における距離算出を制御する制御工程と、
算出された最後の部分ベクトルまでの距離の積算値を上記類似度として出力する出力工程とを有し、
上記制御工程では、ある部分ベクトルまでに算出された距離の積算値が上記閾値比較工程において上記閾値を上回った場合に距離算出を打ち切るように制御すること
を特徴とするプログラム。
【請求項１５】
２つの入力ベクトル間の類似度を求める類似度算出処理をコンピュータに実行させるプログラムが記録されたコンピュータ読み取り可能な記録媒体であって、
上記２つの入力ベクトルに対して所定の変換を施す変換工程と、
上記変換工程にて変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を所定の順序で取り出して複数の部分ベクトルに分割する分割工程と、
上記部分ベクトル毎に、上記２つの入力ベクトル間の距離算出を行う距離算出工程と、
上記距離算出工程で算出された上記部分ベクトル毎の距離の積算値を、予め設定された閾値と比較する閾値比較工程と、
上記閾値比較工程における比較結果に応じて、上記距離算出工程における距離算出を制御する制御工程と、
算出された最後の部分ベクトルまでの距離の積算値を上記類似度として出力する出力工程とを有し、
上記制御工程では、ある部分ベクトルまでに算出された距離の積算値が上記閾値比較工程において上記閾値を上回った場合に距離算出を打ち切るように制御すること
を特徴とするプログラムが記録された記録媒体。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００１２
【補正方法】変更
【補正の内容】
【００１２】
【課題を解決するための手段】
上述した目的を達成するために、本発明に係る類似度算出方法は、２つの入力ベクトル間の類似度を求める類似度算出方法であって、上記２つの入力ベクトルに対して所定の変換を施す変換工程と、上記変換工程にて変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を所定の順序で取り出して複数の部分ベクトルに分割する分割工程と、上記部分ベクトル毎に、上記２つの入力ベクトル間の距離算出を行う距離算出工程と、上記距離算出工程で算出された上記部分ベクトル毎の距離の積算値を、予め設定された閾値と比較する閾値比較工程と、上記閾値比較工程における比較結果に応じて、上記距離算出工程における距離算出を制御する制御工程と、算出された最後の部分ベクトルまでの距離の積算値を上記類似度として出力する出力工程とを有し、上記制御工程では、ある部分ベクトルまでに算出された距離の積算値が上記閾値比較工程において上記閾値を上回った場合に距離算出を打ち切るように制御する。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
このような類似度算出方法は、２つの入力ベクトル間の各々を複数の部分ベクトルに分割して部分ベクトル毎に２つの入力ベクトル間の距離算出を行い、ある部分ベクトルまでに算出された距離の積算値が所定の閾値を上回るものについては閾値以上であることのみを検出して実際の距離を算出しないことにより、演算を高速化する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
ここで、上記所定の変換とは、例えば、入力ベクトルを構成する各成分の順序を当該各成分の分散の大きさに従って並べ替える変換、離散コサイン変換、離散フーリエ変換、ウォルシュ−アダマール変換、或いはカルーネン−レーベ変換である。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】削除
【補正の内容】
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１６
【補正方法】変更
【補正の内容】
【００１６】
また、上述した目的を達成するために、本発明に係る類似度算出装置は、２つの入力ベクトル間の類似度を求める類似度算出装置であって、上記２つの入力ベクトルに対して所定の変換を施す変換手段と、上記変換手段によって変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を所定の順序で取り出して複数の部分ベクトルに分割する分割手段と、上記部分ベクトル毎に、上記２つの入力ベクトル間の距離算出を行う距離算出手段と、上記距離算出手段によって算出された上記部分ベクトル毎の距離の積算値を、予め設定された閾値と比較する閾値比較手段と、上記閾値比較手段による比較結果に応じて、上記距離算出手段による距離算出を制御する制御手段と、算出された最後の部分ベクトルまでの距離の積算値を上記類似度として出力する出力手段とを備え、上記制御手段は、上記閾値比較手段による比較の結果、ある部分ベクトルまでに算出された距離の積算値が上記閾値を上回った場合に距離算出を打ち切るように制御する。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
このような類似度算出装置は、２つの入力ベクトル間の各々を複数の部分ベクトルに分割して部分ベクトル毎に２つの入力ベクトル間の距離算出を行い、ある部分ベクトルまでに算出された距離の積算値が所定の閾値を上回るものについては閾値以上であることのみを検出して実際の距離を算出しないことにより、演算を高速化する。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００１８
【補正方法】変更
【補正の内容】
【００１８】
ここで、上記所定の変換とは、例えば、入力ベクトルを構成する各成分の順序を当該各成分の分散の大きさに従って並べ替える変換、離散コサイン変換、離散フーリエ変換、ウォルシュ−アダマール変換、或いはカルーネン−レーベ変換である。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００１９
【補正方法】削除
【補正の内容】
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１２７
【補正方法】変更
【補正の内容】
【０１２７】
【発明の効果】
以上詳細に説明したように、本発明に係る類似度算出方法は、２つの入力ベクトル間の類似度を求める類似度算出方法であって、上記２つの入力ベクトルに対して所定の変換を施す変換工程と、上記変換工程にて変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を所定の順序で取り出して複数の部分ベクトルに分割する分割工程と、上記部分ベクトル毎に、上記２つの入力ベクトル間の距離算出を行う距離算出工程と、上記距離算出工程で算出された上記部分ベクトル毎の距離の積算値を、予め設定された閾値と比較する閾値比較工程と、上記閾値比較工程における比較結果に応じて、上記距離算出工程における距離算出を制御する制御工程と、算出された最後の部分ベクトルまでの距離の積算値を上記類似度として出力する出力工程とを有し、上記制御工程では、ある部分ベクトルまでに算出された距離の積算値が上記閾値比較工程において上記閾値を上回った場合に距離算出を打ち切るように制御する。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１２８
【補正方法】変更
【補正の内容】
【０１２８】
このような類似度算出方法によれば、２つの入力ベクトル間の各々を複数の部分ベクトルに分割して部分ベクトル毎に２つの入力ベクトル間の距離算出を行い、ある部分ベクトルまでに算出された距離の積算値が所定の閾値を上回るものについては閾値以上であることのみを検出して実際の距離を算出しないことにより、演算を高速化することができる。特に、大量の登録ベクトルの中から、入力ベクトルと類似するベクトルを検索するような場合には、殆どの登録ベクトルは非類似であり閾値を上回ってしまうため、距離算出を早期に打ち切ることができ、検出時間を大幅に短縮することができる。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１２９
【補正方法】変更
【補正の内容】
【０１２９】
ここで、上記所定の変換とは、例えば、入力ベクトルを構成する各成分の順序を当該各成分の分散の大きさに従って並べ替える変換、離散コサイン変換、離散フーリエ変換、ウォルシュ−アダマール変換、或いはカルーネン−レーベ変換である。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０１３０
【補正方法】変更
【補正の内容】
【０１３０】
このような変換を予め入力ベクトルに施し、有意性の高いベクトル成分、すなわち、上述の変換で分散や固有値の大きい成分、或いは低周波成分から順に積算演算を行うようにすることで、ベクトル成分の分布を考慮して、効率的且つ高速に類似するベクトルを検出することができる。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０１３１
【補正方法】削除
【補正の内容】
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０１３２
【補正方法】削除
【補正の内容】
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０１３３
【補正方法】変更
【補正の内容】
【０１３３】
また、本発明に係る類似度算出装置は、２つの入力ベクトル間の類似度を求める類似度算出装置であって、上記２つの入力ベクトルに対して所定の変換を施す変換手段と、上記変換手段によって変換された上記２つの入力ベクトルの各々について、当該入力ベクトルを構成する各成分を所定の順序で取り出して複数の部分ベクトルに分割する分割手段と、上記部分ベクトル毎に、上記２つの入力ベクトル間の距離算出を行う距離算出手段と、上記距離算出手段によって算出された上記部分ベクトル毎の距離の積算値を、予め設定された閾値と比較する閾値比較手段と、上記閾値比較手段による比較結果に応じて、上記距離算出手段による距離算出を制御する制御手段と、算出された最後の部分ベクトルまでの距離の積算値を上記類似度として出力する出力手段とを備え、上記制御手段は、上記閾値比較手段による比較の結果、ある部分ベクトルまでに算出された距離の積算値が上記閾値を上回った場合に距離算出を打ち切るように制御する。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０１３４
【補正方法】変更
【補正の内容】
【０１３４】
このような類似度算出装置によれば、２つの入力ベクトル間の各々を複数の部分ベクトルに分割して部分ベクトル毎に２つの入力ベクトル間の距離算出を行い、ある部分ベクトルまでに算出された距離の積算値が所定の閾値を上回るものについては閾値以上であることのみを検出して実際の距離を算出しないことにより、演算を高速化することができる。特に、大量の登録ベクトルの中から、入力ベクトルと類似するベクトルを検索するような場合には、殆どの登録ベクトルは非類似であり閾値を上回ってしまうため、距離算出を早期に打ち切ることができ、検出時間を大幅に短縮することができる。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】０１３５
【補正方法】変更
【補正の内容】
【０１３５】
ここで、上記所定の変換とは、例えば、入力ベクトルを構成する各成分の順序を当該各成分の分散の大きさに従って並べ替える変換、離散コサイン変換、離散フーリエ変換、ウォルシュ−アダマール変換、或いはカルーネン−レーベ変換である。
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】０１３６
【補正方法】変更
【補正の内容】
【０１３６】
このような変換を予め入力ベクトルに施し、有意性の高いベクトル成分、すなわち、上述の変換で分散や固有値の大きい成分、或いは低周波成分から順に積算演算を行うようにすることで、ベクトル成分の分布を考慮して、効率的且つ高速に類似するベクトルを検出することができる。
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】０１３７
【補正方法】削除
【補正の内容】
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】０１３８
【補正方法】削除
【補正の内容】