(57)【要約】【課題】ＥＭＤを用いて高い精度を維持しつつ、高速化を図る。【解決手段】登録音楽データ蓄積手段３２に蓄積された登録音楽データ及び入力音楽データ入力手段１０から入力された入力音楽データを、各々固定長で一以上のメロディ片及び入力片に分割し、メロディ片及び入力片内に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片及び入力片毎の音楽特徴量を算出する特徴量演算手段２０と、入力片特徴量保持手段４２に保持された入力音楽データに含まれる入力片の入力片特徴量と、メロディ片特徴量蓄積手段３４に蓄積されたメロディ片毎の音楽特徴量について、供給地から需要地への最小輸送コストを計算するＥＭＤの距離計算で得られた類似度を同じ距離尺度で比較することにより、入力音楽データと全体の曲調が類似した登録音楽データを抽出する類似度演算手段２２と、検索結果出力手段５０とを備える。【選択図】図１
2009015535.tif 000002
【特許請求の範囲】
【請求項１】
検索対象となる登録音楽データを複数登録した登録音楽データ蓄積手段と、
検索対象の入力音楽データを入力するための入力音楽データ入力手段と、
前記登録音楽データ蓄積手段に蓄積された登録音楽データ及び前記音楽データ入力手段から入力された入力音楽データを、各々固定長で一以上のメロディ片及び入力片に分割し、メロディ片及び入力片内に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片及び入力片毎の音楽特徴量を算出する特徴量演算手段と、
前記特徴量演算手段で演算されたメロディ片毎の音楽特徴量を、元の音楽データと対応させて登録したメロディ片特徴量蓄積手段と、
前記特徴量演算手段で演算された入力片の音楽特徴量を保持する入力片特徴量保持手段と、
前記入力片特徴量保持手段に保持された入力音楽データに含まれる入力片の入力片特徴量と、前記メロディ片特徴量蓄積手段に蓄積されたメロディ片毎の音楽特徴量について、輸送問題の解法に基づき、供給地から需要地への最小輸送コストを計算するＥＭＤの距離計算で得られた類似度を同じ距離尺度で比較することにより、入力音楽データと全体の曲調が類似した登録音楽データを抽出する類似度演算手段と、
前記類似度演算手段で抽出された一以上の登録音楽データの検索結果をマージするマージ手段と、
前記マージ手段でマージされた登録音楽データを検索結果として出力するための検索結果出力手段と、
を備えることを特徴とする類似音楽検索装置。
【請求項２】
請求項１に記載の類似音楽検索装置において、
メロディ片に含まれる音符の特徴量がさらに、２つ前の音符との音高差情報を含むことを特徴とする類似音楽検索装置。
【請求項３】
請求項１又は２に記載の類似音楽検索装置において、さらに、
前記登録音楽データ蓄積手段に蓄積された個々の登録音楽データに関する付随情報を、音楽データと関連付けて蓄積する付随情報蓄積手段を備え、
前記検索結果出力手段がさらに、検索結果を表示する表示手段を備え、
前記検索手段により検索された音楽データに対応して、前記付随情報蓄積手段に記憶されている付随情報を読み出し、読み出した付随情報を検索結果として、前記表示手段に表示させてなることを特徴とする類似音楽検索装置。
【請求項４】
請求項１から３のいずれか一に記載の類似音楽検索装置において、さらに、
検索対象の音楽データをＭＩＤＩデータに変換する音楽データ変換手段を備えることを特徴とする類似音楽検索装置。
【請求項５】
請求項１から４のいずれか一に記載の類似音楽検索装置において、
前記特徴量演算手段が登録音楽データ及び入力音楽データをメロディ片に分割する際、一定長さのウインドウ長を、ウインドウ長より短いスライド幅でスライドさせて分割することを特徴とする類似音楽検索装置。
【請求項６】
請求項１から５のいずれか一に記載の類似音楽検索装置において、
前記登録音楽データ蓄積手段が、ＶＰ−ｔｒｅｅに基づく索引化を施されてなることを特徴とする類似音楽検索装置。
【請求項７】
予め複数の登録音楽データが登録されると共に、各登録音楽データについて、固定長で一以上のメロディ片に分割して、各メロディ片に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片毎の音楽特徴量を算出して、該メロディ片の音楽特徴量を元の音楽データと対応させてメロディ片特徴量蓄積手段に登録された類似音楽検索システムにおいて、該予め登録された登録音楽データの中から、入力された入力音楽データと類似する音楽データを検索する類似音楽検索方法であって、
入力音楽データを固定長で一以上の入力片に分割する工程と、
入力片内に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片及び入力片毎の音楽特徴量を算出する工程と、
入力音楽データに含まれる入力片の入力片特徴量と、前記メロディ片特徴量蓄積手段に蓄積されたメロディ片毎の音楽特徴量について、輸送問題の解法に基づき、供給地から需要地への最小輸送コストを計算するＥＭＤの距離計算で得られた類似度を同じ距離尺度で比較することにより、入力音楽データと全体の曲調が類似した登録音楽データを抽出する工程と、
抽出された一以上の登録音楽データの検索結果を出力する工程と、
を含むことを特徴とする類似音楽検索方法。
【請求項８】
請求項７に記載の類似音楽検索方法において、
音楽特徴量としてさらに、２つ前の音符との音高差情報を含むことを特徴とする類似音楽検索方法。
【請求項９】
請求項７又は８に記載の類似音楽検索方法において、
入力音楽データと類似する登録音楽データを抽出する工程において、音符間の最小輸送コストを計算する際、各音符の音楽特徴ベクトルの出現時間に重みパラメータを設定し、音符順番の差の大きい音符間の輸送コストを大きくするよう重みパラメータを調整することを特徴とする類似音楽検索方法。
【請求項１０】
請求項７から９のいずれか一に記載の類似音楽検索方法において、
入力音楽データと類似する登録音楽データを抽出する工程において、
分配フローを決定し、総輸送量計算時に音符順番の差に応じて、音符の順番の差が大きいほど大きくなるようなペナルティを付加することを特徴とする類似音楽検索方法。
【請求項１１】
請求項７から１０のいずれか一に記載の類似音楽検索方法において、さらに、
入力音楽データと類似する登録音楽データを抽出する工程に続き、
抽出された一以上の登録音楽データの検索結果を曲毎にマージし、さらにＥＭＤの値に応じて全体の検索結果をマージすることを特徴とする類似音楽検索方法。
【請求項１２】
予め複数の登録音楽データが登録されると共に、各登録音楽データについて、固定長で一以上のメロディ片に分割して、各メロディ片に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片毎の音楽特徴量を算出して、該メロディ片の音楽特徴量を元の音楽データと対応させてメロディ片特徴量蓄積手段に登録された類似音楽検索システムにおいて、該予め登録された登録音楽データの中から、入力された入力音楽データと類似する音楽データを検索する類似音楽検索プログラムであって、
入力音楽データを固定長で一以上の入力片に分割する機能と、
入力片内に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片及び入力片毎の音楽特徴量を算出する機能と、
入力音楽データに含まれる入力片の入力片特徴量と、前記メロディ片特徴量蓄積手段に蓄積されたメロディ片毎の音楽特徴量について、輸送問題の解法に基づき、供給地から需要地への最小輸送コストを計算するＥＭＤの距離計算で得られた類似度を同じ距離尺度で比較することにより、入力音楽データと全体の曲調が類似した登録音楽データを抽出する機能と、
抽出された一以上の登録音楽データの検索結果を出力する機能と、
をコンピュータに実現させることを特徴とする類似音楽検索プログラム。
【請求項１３】
請求項１２に記載されるプログラムを格納したコンピュータで読み取り可能な記録媒体又は記録した機器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベース等に記録された音楽，楽曲，歌等の音楽データ中から、所望の音楽データを検索するための類似音楽検索装置、類似音楽検索方法、類似音楽検索プログラム及びコンピュータで読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
近年、情報の電子化が進むと共に、蓄積された情報の分量が膨大となって、必要な情報を取り出すための検索システムが求められている。例えば、ローカルのハードディスク等の記録媒体に記録されたデータや、インターネット等のネットワーク接続されたシステムに記録されたデータの中から、所望のデータを抽出する検索システムの研究が進められている。このような検索システムとしては、テキスト検索や画像検索、音楽検索などが研究、実用化されている。この内、音楽データの検索システムについては、近年、ＨＤＤやコンパクトフラッシュ（登録商標）等の記憶装置の大容量化によって、音楽等のコンテンツを大量に蓄積しておくことができるようになったため、携帯音楽プレーヤーや携帯電話、ＨＤＤカーナビ等の登場によってＣＤ・ＭＤ等のメディアを持ち運ばなくても大量の楽曲が聴けるようになっている。またインターネットの普及に伴い、楽曲配信サービスを行うサイトも多数出現し、ユーザは容易に様々な音楽データをダウンロードできるようになった。このように、極めて多数の音楽データの携帯が可能になったため、音楽をより簡単に検索できる検索システムが求められている。
【０００３】
しかしながら、音楽データの検索は容易でなく、従来は曲名、歌手名や歌詞等を入力するキーワード型の検索方式が一般的である。この方法では曲名や歌手、歌い出し等、少なくとも一部の情報をユーザが記憶している必要がある。また、曲名が同じでも異なる曲が存在したり、歌手や歌詞を指定しても所望の曲以外のデータが検索される等、使い勝手はよくない。例えば、音楽のダウンロード販売サイトの利用時において、膨大な音楽データから必要なデータのみを見つけ出すことは困難であり、音楽データに打する効率の良い検索手法が求められている。
【０００４】
これに対し、メロディやリズム等、音を直接入力して検索するコンテンツ型の検索方式は、より汎用的と考えられ、この分野での研究も進められている。例えばＭＩＤＩ音楽データを対象とするコンテンツ型音楽検索手法としては、音楽データのリズムや音高の変化を特徴ベクトル化し、特徴ベクトル間の類似性をユークリッド距離を用いて判定する手法や、音楽データの音長、音高の変化の類似性を判定するＤＰマッチング手法が提案されている。また特許文献１には、図２１のブロック図に示すリズム入力による音楽検索装置が開示される。ここでは、リズムデータ生成部２０２が、音楽データ蓄積部２０１から入力した音楽データを受け、音楽を検索するときの検索キーとして使用されるリズムデータを音楽毎に生成してリズムデータ蓄積部２０３に登録する。また時系列信号入力部２０５で、オン状態とオフ状態とを交互に繰り返す時系列信号を入力する。類似リズム検索部２０６は、時系列信号入力部２０５に入力された時系列信号と同一又は類似した変動パターンを有するリズムデータを、リズムデータ蓄積部２０３に蓄積されている複数のリズムデータの中から検索する。音楽付随情報蓄積部２０４は、リズムデータに対応する音楽に付随する音楽付随情報をリズムデータに対応付けて蓄積する。検索結果生成部２０７は、検索されたリズムデータに対応して記憶されている前記音楽付随情報（曲名などの情報）をもちいて検索結果を生成し、検索結果出力部２０８を介して出力する。しかしながら、これらいずれの方法においても、検索精度は実用上不十分といわざるを得ず、さらなる検索精度向上が求められていた。
【０００５】
そこで本発明者らは、距離尺度にＥＭＤ（Earth Mover's Distance）を用いたハミングによる類似音楽検索手法を先に提案した（非特許文献１）。この手法は、音長、音符の出現時間、音高差を特徴量として用い、輸送問題の解に基づきＥＭＤを計算することにより、高精度な類似音楽検索を可能としている。ＥＭＤは輸送問題における輸送コストの最適解であり、輸送問題における各供給地が有する資源量を各音符の音長、輸送コストを各音符の出現時間と音高差情報から算出することで、音楽データが有するリズムと音程との類似度を同じ距離尺度で測り、全体の曲調が類似した音楽を検索する。
【特許文献１】特開２００６−１０６８１８号公報
【非特許文献１】大西泰代，獅々堀正幹，柘植覚，北研二「距離尺度にEarth Mover's Distanceを用いたハミングによる類似音楽検索手法」第４回情報科学技術フォーラム（電子情報処理学会）平成１７年９月７日Ｇ−００３
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、ＥＭＤを用いた検索処理では、検索精度が向上する反面、検索精度が遅いという欠点があり、実用化への妨げとなっていた。特にＥＭＤの問題点として、計算量が音符数に対して指数関数的に増加するため、すべてのメロディ片に対して距離計算を行うと、多大な計算時間が必要になる。
【０００７】
本発明は、このような問題点に鑑みてなされたものであり、その主な目的は、ＥＭＤを用いて高い精度を維持しつつ、高速化を図ることで実用性を高めた類似音楽検索装置、類似音楽検索方法、類似音楽検索プログラム及びコンピュータで読み取り可能な記録媒体を提供することにある。
【課題を解決するための手段及び発明の効果】
【０００８】
上記の目的を達成するために、本発明の類似音楽検索装置は、検索対象となる登録音楽データを複数登録した登録音楽データ蓄積手段と、検索対象の入力音楽データを入力するための入力音楽データ入力手段と、前記登録音楽データ蓄積手段に蓄積された登録音楽データ及び前記音楽データ入力手段から入力された入力音楽データを、各々固定長で一以上のメロディ片及び入力片に分割し、メロディ片及び入力片内に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片及び入力片毎の音楽特徴量を算出する特徴量演算手段と、前記特徴量演算手段で演算されたメロディ片毎の音楽特徴量を、元の音楽データと対応させて登録したメロディ片特徴量蓄積手段と、前記特徴量演算手段で演算された入力片の音楽特徴量を保持する入力片特徴量保持手段と、前記入力片特徴量保持手段に保持された入力音楽データに含まれる入力片の入力片特徴量と、前記メロディ片特徴量蓄積手段に蓄積されたメロディ片毎の音楽特徴量について、輸送問題の解法に基づき、供給地から需要地への最小輸送コストを計算するＥＭＤの距離計算で得られた類似度を同じ距離尺度で比較することにより、入力音楽データと全体の曲調が類似した登録音楽データを抽出する類似度演算手段と、前記類似度演算手段で抽出された一以上の登録音楽データの検索結果をマージするマージ手段と、前記マージ手段でマージされた登録音楽データを検索結果として出力するための検索結果出力手段とを備える。これにより、ＥＭＤを利用したより高精度な類似音楽検索が可能となる。
【０００９】
また、第２の類似音楽検索装置は、メロディ片に含まれる音符の特徴量がさらに、２つ前の音符との音高差情報を含むことができる。これにより、基準音符間の音高差を特徴量に加えることで、メロディ片の長さを維持しつつ音楽特徴量内の音符数を削減することができるので、トータルの時間計算量の低減して高速化を図ることができる。
【００１０】
さらに、第３の類似音楽検索装置はさらに、前記登録音楽データ蓄積手段に蓄積された個々の登録音楽データに関する付随情報を、音楽データと関連付けて蓄積する付随情報蓄積手段を備え、前記検索結果出力手段がさらに、検索結果を表示する表示手段を備え、前記検索手段により検索された音楽データに対応して、前記付随情報蓄積手段に記憶されている付随情報を読み出し、読み出した付随情報を検索結果として、前記表示手段に表示させることができる。これにより、検索された音楽データの曲名、アーティスト名、歌詞、ジャケットイメージなどの、音楽データに関する付随情報を表示手段に表示させて、音楽そのものを再生せずとも検索された音楽をよりイメージしやすいよう、ユーザに提示できる。
【００１１】
さらにまた、第４の類似音楽検索装置はさらに、検索対象の音楽データをＭＩＤＩデータに変換する音楽データ変換手段を備えることができる。
【００１２】
さらにまた、第５の類似音楽検索装置は、前記特徴量演算手段が登録音楽データ及び入力音楽データをメロディ片に分割する際、一定長さのウインドウ長を、ウインドウ長より短いスライド幅でスライドさせて分割することができる。このようにスライディングウィンドウ方式にて分割することで、連続する分割されたメロディ片は互いに重なりのあるデータとなり、検索する部分に関して自由度が増す。さらに登録音楽データの情報量と、入力音楽データの情報量とを等しくすることで、効率よく類似度演算を行える。
【００１３】
さらにまた、第６の類似音楽検索装置は、前記登録音楽データ蓄積手段が、ＶＰ−ｔｒｅｅに基づく索引化を施すことができる。これにより、距離空間内のデータを索引化することで検索速度の向上が図られる。
【００１４】
さらにまた、第７の類似音楽検索方法は、予め複数の登録音楽データが登録されると共に、各登録音楽データについて、固定長で一以上のメロディ片に分割して、各メロディ片に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片毎の音楽特徴量を算出して、該メロディ片の音楽特徴量を元の音楽データと対応させてメロディ片特徴量蓄積手段に登録された類似音楽検索システムにおいて、該予め登録された登録音楽データの中から、入力された入力音楽データと類似する音楽データを検索する類似音楽検索方法であって、入力音楽データを固定長で一以上の入力片に分割する工程と、入力片内に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片及び入力片毎の音楽特徴量を算出する工程と、入力音楽データに含まれる入力片の入力片特徴量と、前記メロディ片特徴量蓄積手段に蓄積されたメロディ片毎の音楽特徴量について、輸送問題の解法に基づき、供給地から需要地への最小輸送コストを計算するＥＭＤの距離計算で得られた類似度を同じ距離尺度で比較することにより、入力音楽データと全体の曲調が類似した登録音楽データを抽出する工程と、抽出された一以上の登録音楽データの検索結果を出力する工程とを含むことができる。これにより、ＥＭＤを利用したより高精度な類似音楽検索が可能となる。
【００１５】
さらにまた、第８の類似音楽検索方法は、音楽特徴量としてさらに、２つ前の音符との音高差情報を含むことができる。これにより、基準音符間の音高差を特徴量に加えることで、メロディ片の長さを維持しつつ音楽特徴量内の音符数を削減することができるので、トータルの時間計算量の低減して高速化を図ることができる。
【００１６】
さらにまた、第９の類似音楽検索方法は、入力音楽データと類似する登録音楽データを抽出する工程において、音符間の最小輸送コストを計算する際、各音符の音楽特徴ベクトルの出現時間に重みパラメータを設定し、音符順番の差の大きい音符間の輸送コストを大きくするよう重みパラメータを調整することができる。これにより、ＥＭＤでトータルコストを計算する際、音符の出現時間に応じて時間軸方向の制約を強める。すなわち、音符順番の差の大きい音符間については、輸送コストを大きくするように音符間の分配フローに制御を加えることで、従来、出現時間が大きく異なる音符間に分配フローが生成される結果、誤ったメロディ片が検索されていた問題を解消でき、より高精度な類似音楽検索が実現される。
【００１７】
さらにまた、第１０の類似音楽検索方法は、入力音楽データと類似する登録音楽データを抽出する工程において、分配フローを決定し、総輸送量計算時に音符順番の差に応じて、音符の順番の差が大きいほど大きくなるようなペナルティを付加することができる。これにより、音符の順番の差が大きいほどペナルティも大きく、すなわち給輸送量が大きくなるので、誤り曲のメロディ片とのＥＭＤの値を大きくすることができ、誤検出を低減できる。
【００１８】
さらにまた、第１１の類似音楽検索方法はさらに、入力音楽データと類似する登録音楽データを抽出する工程に続き、抽出された一以上の登録音楽データの検索結果を曲毎にマージし、さらにＥＭＤの値に応じて全体の検索結果をマージすることができる。これにより、入力ハミングを分割してできる複数の部分入力片の検索結果において、正解曲のメロディ片が多く出現していることを利用し、正解曲を効率的に利用して精度を高めた類似音楽検索が実現される。
【００１９】
さらにまた、第１２の類似音楽検索プログラムは、予め複数の登録音楽データが登録されると共に、各登録音楽データについて、固定長で一以上のメロディ片に分割して、各メロディ片に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片毎の音楽特徴量を算出して、該メロディ片の音楽特徴量を元の音楽データと対応させてメロディ片特徴量蓄積手段に登録された類似音楽検索システムにおいて、該予め登録された登録音楽データの中から、入力された入力音楽データと類似する音楽データを検索する類似音楽検索プログラムであって、入力音楽データを固定長で一以上の入力片に分割する機能と、入力片内に含まれる音符の出現時間、音長、音高推移情報を少なくとも含む特徴量に基づき、メロディ片及び入力片毎の音楽特徴量を算出する機能と、入力音楽データに含まれる入力片の入力片特徴量と、前記メロディ片特徴量蓄積手段に蓄積されたメロディ片毎の音楽特徴量について、輸送問題の解法に基づき、供給地から需要地への最小輸送コストを計算するＥＭＤの距離計算で得られた類似度を同じ距離尺度で比較することにより、入力音楽データと全体の曲調が類似した登録音楽データを抽出する機能と、抽出された一以上の登録音楽データの検索結果を出力する機能とをコンピュータに実現させることができる。これにより、ＥＭＤを利用したより高精度な類似音楽検索が可能となる。
【００２０】
また第１３のコンピュータで読み取り可能な記録媒体は、上記プログラムを格納するものである。記録媒体には、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＣＤ−ＲＷやフレキシブルディスク、磁気テープ、ＭＯ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＤＶＤ−Ｒ、ＤＶＤ＋Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ＋ＲＷ、Ｂｌｕ−ｒａｙ、ＨＤ  ＤＶＤ（ＡＯＤ）等の磁気ディスク、光ディスク、光磁気ディスク、半導体メモリその他のプログラムを格納可能な媒体が含まれる。またプログラムには、上記記録媒体に格納されて配布されるものの他、インターネット等のネットワーク回線を通じてダウンロードによって配布される形態のものも含まれる。さらに記録媒体にはプログラムを記録可能な機器、例えば上記プログラムがソフトウェアやファームウェア等の形態で実行可能な状態に実装された汎用もしくは専用機器を含む。さらにまたプログラムに含まれる各処理や機能は、コンピュータで実行可能なプログラムソフトウエアにより実行してもよいし、各部の処理を所定のゲートアレイ（ＦＰＧＡ、ＡＳＩＣ、ＤＳＰ）等のハードウエア、又はプログラムソフトウエアとハードウェアの一部の要素を実現する部分的ハードウエアモジュールとが混在する形式で実現してもよい。
【発明を実施するための最良の形態】
【００２１】
以下、本発明の実施の形態を図面に基づいて説明する。ただし、以下に示す実施の形態は、本発明の技術思想を具体化するための類似音楽検索装置、類似音楽検索方法、類似音楽検索プログラム及びコンピュータで読み取り可能な記録媒体を例示するものであって、本発明は類似音楽検索装置、類似音楽検索方法、類似音楽検索プログラム及びコンピュータで読み取り可能な記録媒体を以下のものに特定しない。また、本明細書は特許請求の範囲に示される部材を、実施の形態の部材に特定するものでは決してない。特に実施の形態に記載されている構成部品の寸法、材質、形状、その相対的配置等は特に特定的な記載がない限りは、本発明の範囲をそれのみに限定する趣旨ではなく、単なる説明例にすぎない。なお、各図面が示す部材の大きさや位置関係等は、説明を明確にするため誇張していることがある。さらに以下の説明において、同一の名称、符号については同一もしくは同質の部材を示しており、詳細説明を適宜省略する。さらに、本発明を構成する各要素は、複数の要素を同一の部材で構成して一の部材で複数の要素を兼用する態様としてもよいし、逆に一の部材の機能を複数の部材で分担して実現することもできる。
【００２２】
本明細書において類似音楽検索システムまたは類似音楽検索装置とこれに接続される操作、制御、入出力、表示、その他の処理等のためのコンピュータ、プリンタ、外部記憶装置その他の周辺機器との接続は、例えばＩＥＥＥ１３９４、ＲＳ−２３２ｘ、ＲＳ−４２２、ＲＳ−４２３、ＲＳ−４８５、ＵＳＢ等のシリアル接続、パラレル接続、あるいは１０ＢＡＳＥ−Ｔ、１００ＢＡＳＥ−ＴＸ、１０００ＢＡＳＥ−Ｔ等のネットワークを介して電気的に接続して通信を行う。接続は有線を使った物理的な接続に限られず、ＩＥＥＥ８０２．１ｘ、ＯＦＤＭ方式等の無線ＬＡＮやＢｌｕｅｔｏｏｔｈ（登録商標）等の電波、赤外線、光通信等を利用した無線接続等でもよい。さらに検索対象のテキストや画像データの保存やデータベース構築、検索等に関する設定の保存等を行うための記録媒体には、メモリカードや磁気ディスク、光ディスク、光磁気ディスク、半導体メモリ等が利用できる。
（類似音楽検索システム）
【００２３】
図１に、本発明の一実施の形態に係る類似音楽検索システムのブロック図を示す。この図に示す類似音楽検索システム１００は、入力音楽データ入力手段１０と、音楽データ変換手段１２と、特徴量演算手段２０と、登録音楽データ蓄積手段３２と、メロディ片特徴量蓄積手段３４と、付随情報蓄積手段３６と、特徴量演算手段２０と、メモリ手段４０と、類似度演算手段２２と、検索結果マージ手段２４と、検索結果出力手段５０とを備える。本実施の形態では、このような類似音楽検索システム１００をスタンドアロンで構築する他、ネットワーク上で接続されたサーバ、クライアントシステムで構築することもできる。例えば、サーバ側プログラムで、予め登録された登録音楽データ中から、入力音楽データに類似するものを検索して出力する態様が利用できる。一例として、ユーザがインターネットサイト上で音楽をダウンロード購入する際に、ユーザが望む音楽を検索するために、携帯電話やパーソナルコンピュータなどの端末から、検索したい音楽の一部をハミングして入力し、検索結果をサーバから端末に返す。この場合、入力音楽データ入力手段１０は、ユーザの携帯電話からインターネット、一般電話等のネットワーク回線を通じて、入力音楽データを取得する。音楽データ変換手段１２は、入力音楽データをＭＩＤＩ形式に変換する。特徴量演算手段２０は、ＭＩＤＩ形式の入力音楽データを、固定長で一以上の入力片に分割し、さらに入力片内に含まれる各音符の出現時間、音長、音高推移情報、２つ前の音符との音高差情報等の特徴量に基づき、入力片毎の音楽特徴量を算出する。算出された入力片毎の音楽特徴量は、メモリ手段４０の入力片特徴量保持手段４２に保持される。
【００２４】
一方、検索対象の登録音楽データは、予め登録音楽データ蓄積手段３２に蓄積されている。各音楽データは、同様に特徴量演算手段２０によって、固定長で一以上のメロディ片に分割して、各メロディ片に含まれる音符の出現時間、音長、音高推移情報、２つ前の音符との音高差情報等の特徴量に基づき、メロディ片毎の音楽特徴量を算出して、これらメロディ片音楽特徴量は、メロディ片を含む元の音楽データと対応させて、メロディ片特徴量蓄積手段３４に蓄積されている。そして類似度演算手段２２が、入力片特徴量保持手段４２に保持される入力片の音楽特徴量と、メロディ片特徴量蓄積手段３４に蓄積されたメロディ片の音楽特徴量について、輸送問題の解法に基づき、供給地から需要地への最小輸送コストを計算するＥＭＤの距離計算を行う。これにより得られたＥＭＤを類似度として、同じ距離尺度で比較することにより、入力音楽データと全体の曲調が類似した登録音楽データを抽出する。このようにして抽出された複数の登録音楽データの検索結果は、必要に応じて検索結果マージ手段２４によりマージされる。さらに、マージされた登録音楽データは、検索結果として検索結果出力手段５０から出力される。例えば、表示手段５２に検索結果を表示させたり、あるいは検索結果のデータを検索結果出力手段５０がユーザの端末側に送信し、端末側のモニタに表示させる。
（登録音楽データ蓄積手段３２；メロディ片特徴量蓄積手段３４；付随情報蓄積手段３６）
【００２５】
登録音楽データ蓄積手段３２、メロディ片特徴量蓄積手段３４、付随情報蓄積手段３６は、いずれもデータベースで構成できる。登録音楽データ蓄積手段３２は、検索対象となる登録音楽データを所定のフォーマットで記録する。例えばＭＩＤＩ形式や、ＭＰＥＧ１ ＡＵＤＩＯ Ｌａｙｅｒ３形式、リニアＰＣＭ符号化音声形式、着信音楽の一種である「．ｍｍｆ」形式の着信メロディ、音声データである「着うた（登録商標）」形式、ＳＭＡＦ形式の着信メロディなどの形式で音楽データを蓄積する機能を有する。またメロディ片特徴量蓄積手段３４は、後述するメロディ片毎の特徴量を、メロディ片を含む元の登録音楽データと関連付けて記録する。さらに付随情報蓄積手段３６は、個々の登録音楽データに関する付随情報を、音楽データと関連付けて蓄積している。付随情報としては、音楽データの曲名、演奏者名、作曲者名、曲の長さ、データサイズ、歌詞、ジャケットイメージなどの、音楽データに関する情報である。これら登録音楽データ蓄積手段３２、メロディ片特徴量蓄積手段３４、付随情報蓄積手段３６は、例えばハードディスクやメモリ等の記録媒体により実現する。
（特徴量演算手段２０）
【００２６】
特徴量演算手段２０は、予め登録音楽データ蓄積手段３２に蓄積された登録音楽データから、所定の特徴量を抽出する。ここでは、各登録音楽データを、固定長で一以上のメロディ片に分割し、メロディ片内に含まれる音符の特徴量に基づき、メロディ片の音楽特徴量を算出する。メロディ片への分割は、分割領域（ウィンドウ）を所定の間隔でずらすスライディングウィンドウ方式で行う。また特徴量としては、出現時間、音長、音高推移情報、２つ前の音符との音高差情報等の特徴量が利用できる。このようにして取得されたメロディ片特徴量は、上述したメロディ片特徴量蓄積手段３４に記録される。メロディ片特徴量蓄積手段３４に記録されたメロディ片特徴量は、登録音楽データ蓄積手段３２に記録された登録音楽データの内、該メロディ片を含む元の登録音楽データと関連付けられる。関連付けは、ルックアップテーブルを利用するなど、既知の方法が適宜利用できる。これによって、後述するように類似するメロディ片がメロディ片特徴量蓄積手段３４中から検索されると、該メロディ片を含む登録音楽データが登録音楽データ蓄積手段３２から呼び出される。また必要に応じて、登録音楽データと更に関連付けられた付随情報を付随情報蓄積手段３６から呼び出すことにより、検索された音楽データに関する詳細な情報も取得できる。
（入力音楽データ入力手段１０）
【００２７】
ユーザは、検索したい音楽データを入力音楽データ入力手段１０により入力する。例えば、ユーザが携帯電話やＰＤＡ、パーソナルコンピュータ等の端末から、ネットワークを介して類似音楽検索システムと接続し、端末のマイクロホンなどを用いて、ユーザが検索したい音楽の一部をハミングで入力する。マイクロホンは、メロディの音声波形を取得する。音声波形は、例えばリニアＰＣＭ符号化音声形式であるＷＡＶＥファイル等、適切なファイル形式に変換され、ネットワークを介して入力音楽データ入力手段１０が入力音楽データとして取得する。ただ、この方法に限られず、例えばユーザの周囲で流れている音楽を、その音源にマイクロホンなどをかざして音を入力する方法や、鍵盤楽器などの演奏情報を入力する方法、例えばドレミファといったように文字列で階名を表記した音階列を入力する方式、音楽のコード進行（Ｃ、Ｇ７などの和声の系列）を入力することでそのコード進行を含む音楽を入力する方法等も適宜利用できる。また、ネットワーク接続を介した入力に限られず、スタンドアロンで類似音楽検索システムを構築している場合は、入力音楽データ入力手段１０自体をマイクロホンとしてハミングを直接入力することもできる。
（音楽データ変換手段１２）
【００２８】
音楽データ変換手段１２は、入力音楽データ入力手段１０で取得された入力音楽データを、適切な音声データ形式に変換する。本実施の形態においては、音声波形データをＭＩＤＩ形式データに変換する。例えばＷＡＶＥファイルからＭＩＤＩデータを生成するには、音声のスペクトル分析をして機械的変換を行えばよく、例えばソフトウェアとしては、株式会社メディア・ナビゲーション製「鼻歌ミュージシャン２」、「MuseBook（Ｒ） Wav2Midi Version 1.0（http://www.musebook.com/?page=mbwav2midi）」、「採譜の達人」(http://www.pluto.dti.ne.jp/~araki/soft/)等で実施されている。
【００２９】
このようにして得られた入力音楽データを、同様に特徴量演算手段２０で入力片に分割し、さらに入力片の特徴量を取得し、メモリ手段４０に保持する。メモリ手段４０は、一時的に入力片特徴量を保持する入力片特徴量保持手段４２を有している。ここでは、メモリ手段４０をＲＡＭなどで構成し、入力片特徴量を保持する領域を確保している。以下、本実施の形態では、ハミングを入力してＭＩＤＩ形式の音楽データを検索する類似音楽検索システムについて説明する。
（類似度演算手段２２）
【００３０】
類似度演算手段２２は、入力片であるハミング片の音楽特徴量及びメロディ片特徴量を比較し、ＥＭＤを用いた類似音楽検索を行う。具体的には、ハミング片特徴量とメロディ片特徴量を比較し、入力音楽データと全体の曲調が類似した登録音楽データを抽出する。抽出する登録音楽データの数は、例えば類似度の高い順に上位から所定の数を抽出したり、あるいは類似度が閾値を超えるものをすべて抽出するなどの方法が適宜利用できる。検索結果の登録音楽データは、必要に応じて付随情報蓄積手段３６から付随情報を取得する。さらに、検索結果は必要に応じて検索結果マージ手段２４でマージされる。これらの詳細については後述する。また、上述した特徴量演算手段２０、類似度演算手段２２、検索結果マージ手段２４などは、例えばマイクロプロセッサ（ＭＰＵ）やＣＰＵ、ＬＳＩ、ＦＰＧＡやＡＳＩＣといったゲートアレイ等のハードウエアや、ソフトウエア、あるいはこれらの混在により実現できる。また必ずしも各構成要素が図１に示した構成と同一でなくてもよく、その機能が実質的に同一であるもの、及び一つの要素が図１に示す構成における複数の要素の機能を備えるものは、本発明に含まれる。
（検索結果出力手段５０）
【００３１】
このようにして抽出された複数の登録音楽データの検索結果を出力データとして、検索結果として検索結果出力手段５０で出力する。例えば検索の問い合わせを行ったユーザの端末である携帯電話等に対し、テキスト情報として検索結果を送信したり、上位の登録音楽データを演奏する。
（類似音楽検索方法）
【００３２】
次に、類似音楽検索方法の概要を説明する。類似音楽検索手法では、ユーザが検索したい曲の特徴を入力し、これに類似した楽曲を検索する。ここでは、ユーザが曲の一部をハミングして入力する。図２に、類似音楽検索システム１００の全体の流れを示す。この図に示すように、ユーザは検索したい曲の一部をハミングする。その後、ハミングを採譜ソフトでＭＩＤＩ音楽データに変換した後、システムに入力する。一方、検索対象の登録音楽データに対しては、予め抽出した主旋律に対する登録音楽データ蓄積手段３２を作成し、入力ハミングの音楽特徴量との距離計算を類似度演算手段２２で行い、距離の近い類似したメロディを持つ曲を検索する。特に、登録音楽データの任意の部分を検索可能にするため、検索対象の登録音楽データを予めスライディングウインドウ方式によって分割しておく。スライディングウインドウ方式とは、図３のように、一定のウインドウ長を「拍」を単位として、所定量ずつスライドさせて分割する方法である。スライド幅をウインドウ長より短くすることで、連続する分割されたメロディ片は互いに重なりのあるデータとなり、検索する部分に関して自由度が増す。同様に入力音楽データも、スライディングウインドウ方式で分割する。このように、曲のデータを細かく分割して、それぞれを類似度演算の対象とすることで、類似音楽検索システムを構築することができる。また、登録音楽データ蓄積手段３２内の各データが保持している情報量と、ハミング片から作られるデータが保持している情報量は「拍」を単位に等しくなるので、効率的な類似度演算が可能となる。
（類似音楽検索プログラム）
【００３３】
さらに、類似音楽検索プログラムのユーザインターフェース画面２００の例を、図４〜図６に示す。ここでは、既に入力音楽データとしてＭＩＤＩ音楽データとして予め複数収録されており、これらを選択することで、類似する登録音楽データを検索するシステムとして説明する。図４はシステムのスタート画面を示しており、左フレーム内の入力音楽データ指定欄２１０に収録済みのハミングデータが入力音楽データとして列挙される。また図５は、入力音楽データ指定欄２１０から「どんぐりころころ」を入力音楽データとして選択した際の画面例を示している。この画面から、上部の「試聴」ボタン２２０を押下すると「どんぐりころころ」のハミングデータが試聴できる。また、ハミングの全体検索欄には、「フレーズ形式検索」ボタン２３０と、「曲目形式検索」ボタン２３２が設けられている。「フレーズ形式検索」ボタン２３０は、ハミングを分割したフレーズ毎に検索し、結果をマージせずに、フレーズ毎の検索結果を出力する。また「曲目形式検索」ボタン２３２は、フレーズ毎に検索した結果を更にマージして、曲目毎の検索結果を出力する。さらに「ハミングの部分指定検索」欄２４０には、選択したハミングデータを複数のフレーズに分割したデータが列挙されており、いずれかのフレーズを押下すれば、そのフレーズだけを用いて検索する。さらに図６は、図５の画面から「曲目形式検索」ボタン２３２を押下した後の出力結果を示しており、検索結果表示欄２５０には検索結果上位から類似度順に登録音楽データ蓄積手段３２内の曲目が表示される。
【００３４】
なお、この類似音楽検索プログラムのユーザインターフェース画面２００の例において、各入力欄や各ボタン等の配置、形状、表示の仕方、サイズ、配色、模様等は適宜変更できることはいうまでもない。デザインの変更によってより見やすく、評価や判断が容易な表示としたり操作しやすいレイアウトとすることもできる。例えば検索結果を別ウィンドウで表示させる、複数画面を同一表示画面内で表示する等、適宜変更できる。またこれらのプログラムのユーザインターフェース画面において、仮想的に設けられたボタン類や入力欄に対するＯＮ／ＯＦＦ操作、数値や命令入力等の指定は、類似音楽検索プログラムを組み込んだコンピュータに接続された入力部で行う。本明細書において「押下する」とは、ボタン類に物理的に触れて操作する他、入力部によりクリックあるいは選択して擬似的に押下することを含む。操作を行う入出力デバイスはコンピュータと有線もしくは無線で接続され、あるいはコンピュータ等に固定されている。一般的な入力部としては、例えばマウスやキーボード、スライドパッド、トラックポイント、タブレット、ジョイスティック、コンソール、ジョグダイヤル、デジタイザ、ライトペン、テンキー、タッチパッド、アキュポイント等の各種ポインティングデバイスが挙げられる。またこれらの入出力デバイスは、プログラムの操作のみに限られず、類似音楽検索装置等のハードウェアの操作にも利用できる。さらに、インターフェース画面を表示する表示手段のディスプレイ自体にタッチスクリーンやタッチパネルを利用して、画面上をユーザが手で直接触れることにより入力や操作を可能としたり、または音声入力その他の既存の入力手段を利用、あるいはこれらを併用することもできる。
【００３５】
本実施の形態においては、類似度演算のための距離尺度にＥＭＤ（Earth Mover's Distance）を用いる。この手法は、音長、音符の出現時間、音高差を特徴量として用い、輸送問題の解に基づきＥＭＤを計算することにより、高精度な類似音楽検索を可能としている。ＥＭＤは輸送問題における輸送コストの最適解であり、本実施の形態においては、輸送問題における各供給地が有する資源量を各音符の音長、輸送コストを各音符の出現時間と音高情報から算出することで、音楽データが有するリズムと音程との類似度を同じ距離尺度で測り、全体の曲調が類似した音楽を検索する。ここでは、音楽データを固定長のメロディ片に分割した後、メロディ片内の各音符を供給地、音符の音長を供給地の資源量とみなし、各音符の出現時間、音高等の特徴量から輸送コストを算出する。この音楽特徴量をＥＭＤで距離計算することで、リズムと音程との類似度を同じ距離尺度で計り、全体の曲調が類似したメロディを検索する。
（ＥＭＤ）
【００３６】
ここで、ＥＭＤの詳細について説明する。ＥＭＤは、線形計画問題の一つである輸送問題における輸送コストの最適解を求めるアルゴリズムである。このようにＥＭＤは、輸送問題の解に基づいて計算される距離尺度であり、２つの離散分布において、一方の分布を他方の分布に変換するための最小コストとして定義される。輸送問題とは、需要地の需要を満たすように供給地から需要地へ輸送を行う場合の最小輸送コストを解く問題である。ここでＰ、Ｑをそれぞれ供給地、需要地としてＥＭＤを計算する場合を考える。はじめに、Ｐ、Ｑの各要素に対する単位輸送あたりの輸送コスト（ｄij）を計算すると、次式で表現できる。
【００３７】
【数１】
2009015535.tif 000003
【００３８】
本実施の形態においては、輸送距離として各ベクトル要素ｐiとｑjのユークリッド距離を用いる。つぎに、ｐiとｑjのすべての組み合わせを考慮し、総輸送コストを計貫する。総輸送コストは、ＰからＱへの輸送量（フロー）（Ｆ＝｛ｆij｝）を決定する以下の輸送問題の解を用いて計算する。ここで、任意の供給地・需要地の組み合わせによる総輸送量（ＷＯＲＫ）は、次式で表現できる。
【００３９】
【数２】
2009015535.tif 000004
【００４０】
この目的関数は、ｉ、ｊ間の輸送量に単位輸送コストを乗算し、和をとることで総輸送コストが計算されることを示している。なお、ここでは総輸送コストを計算する場合、以下の制約条件１〜４（数３〜数６）を具備するものとする。
【００４１】
制約条件１：供給地から需要地の一方向にしか輸送されない
【００４２】
【数３】
2009015535.tif 000005
【００４３】
制約条件２：供給地ｉから供給できる容量は供給量ωpiを超過しない
【００４４】
【数４】
2009015535.tif 000006
【００４５】
制約条件３：需要地ｊが受け取れる容量はωqj以下である
【００４６】
【数５】
2009015535.tif 000007
【００４７】
制約条件４：供給地から移動する輸送量（総フロー）は、次式で表現される
【００４８】
【数６】
2009015535.tif 000008
【００４９】
最終的にＥＭＤ（Ｐ、Ｑ）は、上記の輸送問題の最適値、すなわち総輸送コストの最小値として、ＷＯＲＫ（Ｐ、Ｑ）を総フローで除算し、次式で演算できる。
【００５０】
【数７】
2009015535.tif 000009
【００５１】
ＥＭＤの計算処理の例を図７に示す。図７の例では、２台のトラックを供給地、３個の枡目を需要地として、各々の図で示す荷物が割り当てられる。供給量、需要量の総和は、どちらも１０個で同数である。供給地から需要地への経路は矢印の数字で示され、輸送経路を実線矢印で示している。また、それぞれの輸送コストも示している。図７でのＥＭＤの計算は、次式で演算できる。
【００５２】
輸送コスト＝距離×輸送量
ＥＭＤ＝総輸送コスト÷総輸送量
ＥＭＤ＝（９＋２＋５）÷１０＝１．６
（音楽特徴量）
【００５３】
ＥＭＤを類似音楽検索手法に適用するにあたり、スライディングウインドウ方式により分割されたメロディ片毎に特徴量を作成する。単作輸送コストを求めるための特徴量は、各音符のＮｏｔｅ−ｏｎ開始時刻、前音との音高差、音高推移特徴とした。図８に、ＥＭＤに適用する音楽特徴量の生成例として、（ａ）のようなメロディ片に対し、（ａ）４分音符を１拍とした音楽特徴量と、（ｂ）８分音符を１拍とした音楽特徴量を、それぞれ示す。ここで、開始時間と音長は拍数で表し、音高差は半音高い音を１、半音低い音を−１としている。
【００５４】
図８（ｂ）、（ｃ）に示す音楽特徴量データにおいて、１行目はメロディ片内の音符の数を表し、２行目以降は、出現音符に対する特徴量を示している。すなわち、図８（ａ）の例では音符１〜４の４個の各音符に対して、（音長、出現時間、音高差、音高推移）が特徴量として表示される。例えば図８（ｂ）は４分音符を１拍とした場合であり、第１音の音符１は、１：（音長、出現時間、音高差、音高推移）＝（１、０、０、−１）となる。また図８（ｃ）は８分音符を１拍とした場合であり、同じく音符１の特徴量は（音長、出現時間、音高差、音高推移）＝（２、０、０、−１）となる。ここで、音高差は前音符との音高差であるため、第１音のように対応する前音が無い場合は、０とする。このようにして、個々の音符に対して、音長情報も考慮した特徴量が生成される。
【００５５】
抽出した音楽特徴量をＥＭＤの定義に当てはめると、音長が供給量ωpi（需要量ωqj）となり、また開始時間、音高差、音高推移が供給地（需要地）を表す特徴ベクトルｐi，ｑjとなる。またメロディ片間の距離ＥＭＤは、個々の音符を供給地、需要地と定義し、ＥＭＤの定義式に従い計算する。
（ＥＭＤを用いた検索処理の問題点）
【００５６】
ここで、ＥＭＤを用いた検索処理では、検索速度が遅いことが実用化において障害となる。検索速度が遅い理由としては、（１）距離計算回数が多い、（２）時間計算量が大きい、の２点が挙げられる。ここで、距離計算回数が多くなる理由は、メロディ片の数に起因する。すなわち、曲をメロディ片に分割しているため、１曲が複数のメロディ片に分割されることになる。その結果、メロディ片数は膨大になり、すべてのメロディ片に対して距離計算を行うと、多大な計算時間が必要となる。
【００５７】
また、時間計算量が大きくなる理由は、音符数に起因する。すなわち、ＥＭＤの計算には一般にシンプレックス法が用いられるため、音符数をＮとすると、Ｎに対して指数関数的に時間計算量が増加する。メロディ片内には音符数が多く、多大な計算時間が必要となる（本発明の実験データでは、２小節のメロディ片内での平均音符数は約１４であった）。そこで、これらの問題点の解決を図るため、検索手法に改良を加えた実施例について、以下順次説明する。
（実施例１  ＶＰ−ｔｒｅｅを用いた距離計算回数の低減）
【００５８】
まず実施例１として、「距離計算回数が多い」問題に対しては、登録音楽データ蓄積手段３２の索引化手法（インデキシング）を適用する。従来の音高推移特徴ベクトルを用いた手法では、ユークリッド空間内のデータを索引化するＳＲ−ｔｒｅｅを採用している。一方、ＥＭＤはユークリッド空間では表現されないため、同様の索引化手法は適用できない。そこで実施例１として、ＥＭＤが距離の３公理を満たす点に着目し、距離空間内のデータを索引化するＶＰ−ｔｒｅｅを採用した類似音楽検索とすることで、検索速度の向上が図られる。なお距離の３公理については、Yianilos, P.N.: Data structures and algorithms for nearest neighbor search in general metric spaces, Proc. of the ACM-SIAM SODA’93, pp. 311.321 (1993).に、ＶＰ−ｔｒｅｅについては、Fu, A.W.-C., Chan, P.M.S., Cheung, Y.-L. and Moon, Y.S.: Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances, VLDB Journal, pp.2.8 (2000).に、それぞれ説明されており、これらの技術を適用できる。
（実施例２  音楽特徴量内の音符数削減による時間計算量の低減）
【００５９】
次に、「時間計算量が大きい」問題に対しては、音楽特徴量内の音符数を削減する必要がある。音楽特徴量内の音符数を削減させるためには、メロディ片の長さを単に短くすることが考えられる。しかしながら、メロディ片を短くすると情報量が減少し、検索精度が低下することが容易に想像できる。そこで実施例２として、メロディ片の長さ（スライディングウィンドウのウインドウ長）を変化させずに、すなわちメロディ片内の情報量を減少させずに、音楽特徴量内の音符数だけを削減させた類似音楽検索システムとする。この手法では、図９に示すように、メロディ片の長さを変えずにスライディングウィンドウ内で偶数番目に出現する音符（スキップ音符）の特徴量を削除し、スキップ音符の音長を前の音符（基準音符）の音長に加算する。更に、スキップ音符が本来存在しなかったメロディ片と区別するため、輸送コストを求める特徴量に基準音符間の音高差、ここでは２つ前の音符との音高差を加える。最終的に各音符の特徴量を次式のように変更し、スキップ音符の特徴を補う音楽特徴量を作成する。
【００６０】
（基準音符の音長＋スキップ音符の音長、基準音符の出現時間、基準音符とスキップ音符間の音高差、基準音符の音高推移、基準音符間の音高差）
【００６１】
このようにして音符数を削減し、検索システムの高速化を実現した。図９に示すように、ウインドウ長は変えずに偶数個めの音符（スキップ音符）の特徴量を削除し、重みだけを前の音符（基準音符）の重みに付加する。このときの特徴量としては、（音長、出現時間、音高差、音高推移）に加えて、２つ前の音符との音高差（基準音符間の音高差）を特徴量に加えることにより、スキップ音符の特徴を補うことができる。図９のメロディでは、改良後の音符は基準音符だけの特徴が残り、１：（２、０、０、−１、０）、２：（２、２、−２、２、−３）となるのでスキップ音符の要素が削減できている。また、スキップ音符の音長を重みとして、基準音符の音長に加えているため、重みの和は一定である。
（実施例２の評価）
【００６２】
このようにして、音符を削除して特徴量を削減し高速化を図った類似音楽検索システムを有用性を評価すべく、実験を行い、部分ハミング片の検索結果毎に分析した。その結果、誤検索が生じているものについては、ＥＭＤを計算する際、音符の順番が大きく異なる分配フローが生じる結果、誤検索を生じていることが判明した。音符の並びについては、輸送コストを計算する際、出現時間を音楽特徴量に加えることにより、音符の順番の近い音符に対して重み付けが分配できるように設定している。しかしながら、その他の特徴量、例えば音高差や音高推移の影響を強く受けた場合には、音符の順番が大きく異なるフローが生成されてしまい、部分ハミング片と誤り曲のメロディ片との間のＥＭＤが、正解曲のメロディ片よりも小くなって、誤検出を生じていた。
【００６３】
図１０に、すべての部分ハミング片（８８４個）の検索結果上位１位について、正解曲のメロディ片が検索できた場合と、誤検索となった場合のメロディ片において、分配フローが生成された音符間の出現順位の差（音符間距離）の分布を示す。この図より、正解曲のメロディ片に対しては、音符の順番の比較的近い音符について分配フローが生じていることが判る。これに対して、誤り曲のメロディ片に対しては、音符の順番の遠い音符への分配フローの割合が大きい。この結果から、音符の並びを重視した分配フロー決定の手法が必要であると考えられる。
（部分ハミング片ＯＲ検索方法）
【００６４】
図１０で示した評価試験で適用した検索方法は、部分ハミング片ＯＲ検索方法を用いた。この検索方法では、入力ハミングｈをスライディングウインドウ方式でｍ個に分割した部分ハミング片をｈj、登録音楽データ蓄積手段３２の曲ａを同じくスライディングウインドウ方式でｎ個に分割した部分メロディ片をａiとした場合、曲ａに対する距離Ｄ（ａ，ｈ）は、次式で演算できる。
【００６５】
【数８】
2009015535.tif 000010
【００６６】
その他の曲に対しても同様に距離を計算し、その距離を用いて曲ごとの類似度を計算し、曲ごとの類似度を計算し、順位付けを行った。類似度は距離の逆数として計算した。この計算方法では、入力ハミングを分割した複数の部分ハミング片のうち、一つでも登録音楽データ蓄積手段３２中の音楽データに含まれる部分メロディ片とのＥＭＤが小さければ、類似度が高くなり、検索結果の上位にリストアップされることになる。このように、部分ハミング片ＯＲ検索方法は、複数ある部分ハミング片のうち一部分のみにしか着目していない検索方法であり、ハミング片全体を考慮していない。
【００６７】
上述した実施例２の評価試験で誤検索となった入力ハミングに対し、部分ハミング片ごとの検索結果上位５０件の正解曲のメロディ片、および誤検索となった曲のメロディ片の割合を調査したところ、正解曲のメロディ片は検索結果の５２％であり、検索結果１位（誤検索）である曲のメロディ片は３５％であった。このことから、検索結果に多くの正解曲のメロディ片を含んでいたとしても、部分ハミング片の内、一つでも距離が小さいものが存在すると類似度が高くなってしまい、誤検索となることが判明した。よって、部分ハミング片ＯＲ検索方法は適切といえず、各曲の出現率も考慮した類似度計算が必要であると考えられる。
【００６８】
そこで、このような問題点を解決し、更なる精度向上を目的として鋭意研究した結果、音楽特徴量の追加、ＥＭＤ計算の改良、類似度計算の改良が有効であることが判明した。以下、これらを順次説明する。
（実施例３  ２つ前の音符との音高差を音楽特徴量として追加）
【００６９】
先の評価試験では、音楽特徴量として出現時間、音高差特徴量、音高推移特徴量を用いた。更なる精度向上のため、上述した２つ前の音符との音高差を音楽特徴量として更に追加する。この様子を、図１１に示す。この図は、図８（ａ）のメロディ片と同じメロディ片図１１（ａ）に対して、出現時間、前音との音高差、音高推移特徴に加えて、更に２つ前の音符との音高差を追加した音楽特徴量を示している。比較のため、図１１（ｂ）には先の評価試験での音楽特徴量を示し、図１１（ｃ）に実施例３に係る検索手法の音楽特徴量を示す。図１１（ｃ）は、８分音符を１拍とした場合の音楽特徴量を示しており、第１音である音符１は、（音長、出現時間、音高差、音高推移、２つ前の音符との音高差）＝（２、０、０、−１、０）となる。なお第２音目までは、２つ前の音符が判らないので、特徴量は０とする。第３音目の２つ前の音との音高差は第１音との音高差であるので、−３となる。
（音符の並びを重視した分配フロー決定方法）
【００７０】
次に、音符の並びを考慮した分配フローの制限を加えたＥＭＤ計算方法として、以下の２つの実施例を説明する。
（実施例４  輸送コスト計算内重み付けＥＭＤ）
【００７１】
実施例４に係る類似音楽検索システムは、時間軸方向への制約を強める方法である。この方法は、音符順番の差の大きい音符間については、輸送コストを大きくする。音符間の輸送コストは、数１の音楽特徴ベクトルのユークリッド距離を計算して求める。そこで、各音符の音楽特徴ベクトルの出現時間に重みパラメータを設定し、パラメータを調整することで出現時間に応じて時間軸方向の制約を強め、音符順番の差の大きい音符間の輸送コストを大きくする。これは数１を、次式数９に改良することにより実現できる。
【００７２】
【数９】
2009015535.tif 000011
【００７３】
数９におけるαkの重みパラメータは、各音楽特徴量毎にベクトル内で設定する。
（実施例５  総輸送量計算内重み付けＥＭＤ）
【００７４】
上記の実施例４は、分配フロー決定処理内での改良であるのに対して、実施例５では分配フロー決定後、音符順番の差の大きい音符へフローができている場合に対して、ペナルティを加える方法である。この方法は、まず分配フローを決定し、総輸送量計算時に音符順番の差に応じたペナルティを付与する。音符の順番の差が大きいほど、ペナルティも大きくなり、その結果、給輸送量が大きくなる。誤り曲のメロディ片では、音符順番の差の大きい音符へ分配フローが多く生成されているので、この方法によれば誤り曲のメロディ片とのＥＭＤの値を大きくすることができる。一方、正解曲のメロディ片に対しては、音符順番の差の小さい音符へ分配フローが生成される傾向が強いので、ペナルティが小さくなる。これは、上記数２で示した総輸送量計算を、次式数１１に変更することにより実現できる。
【００７５】
【数１０】
2009015535.tif 000012
【００７６】
上記数１０においてβは、音符順番の差のペナルティ値である。数１０では、音符の順番の差が大きくなるほど、総輸送量が大きくなる。図１０に示したように、誤り曲のメロディ片に対しては、音符順番の差が大きい音符にフローが分配されていることが多く、本実施例５により、これらのフローに対しペナルティを加えることができる。その結果、誤り曲のメロディ片の順位を下げることができ、正解曲のメロディ片が上位にランクでき、検索精度を向上させることができる。
（実施例６  検索結果マージ方法）
【００７７】
次に実施例６として、検索結果上位のメロディ片内に正解曲のメロディ片が多く含まれていることに着目し、正解曲を効率的に利用するための検索結果のマージ方法を説明する。この検索結果マージ方法は、入力ハミングｈをスライディングウインドウ方式でｍ個に分割した部分ハミング片を、ｈj毎にＥＭＤの値が小さい上位ｌ件を検索する。この検索結果に対して、部分ハミング片ｈjの曲ａに対する距離ｄを、以下の式から求める。
【００７８】
【数１１】
2009015535.tif 000013
【００７９】
その後、すべての部分ハミング片の曲毎の結果より、曲毎の類似度を次式で計算し、順位付けを行う。
【００８０】
【数１２】
2009015535.tif 000014
（評価）
【００８１】
上記で説明した実施例４〜５の有効性を検証するための実験を行った。本実験では検索対象の登録音楽データ蓄積手段３２として、童謡、Ｊ−ｐｏｐ、演歌等のジャンルが含まれるカラオケ用ＭＩＤＩ音楽データ４８３曲を使用した。これら市販のＭＩＤＩ音楽データは、指定のチャネルに主旋律が格納されているため、機械的に主旋律のデータのみを自動抽出した。その後、主旋律のデータに対して、スライディングウインドウ方式を適用して、メロディ片を生成する。
【００８２】
ここでスライディングウインドウの条件としては、８分音符を１拍とし、ウインドウ長１６拍、スライド長４拍として、計８４５５４のメロディ片を生成した。メロディ片内の各音符に対しては、８分音符の長さを１とした音長、出現時間、音高差特徴量、音高差推移特徴量を用いて、特徴量演算手段２０で音楽特徴量を作成した。
【００８３】
検索入力には、男女１０名が歌ったハミングを、市販の採譜ソフトでＭＩＤＩ形式に変換した５０曲を用いた。採譜方法としては、ハミングの長さが最低でもウインドウ長を超える条件を義務付けた。なおハミングの際には、正確なハミングは要求せず、その曲を知っている人が聞いて分かるレベルの入力とした。そのため、入力ハミングにはリズム、音程のずれが生じた。
（実施例６の評価）
【００８４】
まず、実施例６に係る検索結果マージ方法の有効性を確認するため、本発明に係るＥＭＤと、従来のＤＰマッチングに対して、各検索結果に対して部分ハミング片ＯＲ検索を用いた場合と、実施例６に係る検索結果マージ方法を用いた場合の検索結果を図１２に示す。この図より、部分ハミングＯＲ検索と、実施例６に係る手法の検索結果とを比較すると、ＥＭＤを用いた検索では、５位までの検索結果が８６％から２％向上し、４０位までにはすべてのハミングに対して正解の曲をすべて検索できた。この結果から、ＥＭＤを用いた検索では、実施例６の手法が有効であることが確認された。
【００８５】
ただ、ＤＰマッチングにおいては、検索精度の向上はそれ程確認できなかった。この原因を分析するために、実施例６及びＤＰマッチングにおいて、それぞれ１０位以内に正解曲を検索できなかった６曲のハミングについて、それらの検索結果を調査した。するとＤＰマッチングを用いた検索では、部分ハミング片の検索の上位に目的のメロディ片が全く検索できておらず、本実施の形態に係る検索結果マージ方法の効果が現れていなかった。特に、これらの部分ハミング片には音程の大きなズレが生じており、ＤＰマッチングが大きな音程のズレに頑健でないために、検索結果の上位に正解曲が検索できなかったためと思われる。一方、ＥＭＤを用いた場合には、大きな音程のズレを局所的に含む入力ハミングに対しても、上位に目的のメロディ片を検索できていたため、実施例６に係る検索結果マージ方法を用いると精度が向上した。このことから、正解曲が上位に検索できている場合は、実施例６の検索結果マージ方法が有効に働くといえる。以下の評価試験では、実施例６に係る検索結果マージ方法を適用している。
（実施例４の評価）
【００８６】
次に、実施例４に係る輸送コスト計算内重み付けＥＭＤ改良手法の検索精度評価を行った。図１３に、輸送コスト計算内重み付けＥＭＤの精度比較グラフを示す。この図は、出現時間のパラメータの値をα＝４で固定し、音高差特徴量、音高推移特徴量のパラメータの値をα＝１としたときの検索精度である。また従来法での各特徴量のパラメータの値は、すべて１である。この図から、正解データを上位に検索できていることが確認できた。
【００８７】
次に、出現時間のパラメータαを変化させた場合の検索精度を評価する。図１４に出現時間パラメータα＝１〜３、図１５にα＝４〜６における、検索精度の変化をそれぞれ示す。図１４によれば、出現時間のパラメータ値を大きくすることにより５位から２０位までの検索精度が向上した。またいずれの図でも、２０位以上の検索精度に変化がみられなかった。２０位に正解曲が検索できなかったハミングは、各パラメータとも共通していた。検索できなかったハミング（２曲）について試聴し、正解曲と比較した締果、リズムに大きなズレが生じていることが判明した。リズムにズレが生じたハミングに対しては、出現時間を重視した実施例４に係る手法では輸送コスト計算に出現時間が反映できなかったためと考えられる。
【００８８】
また図１５より、パラメータ値α＝６の時の検索精度が一部において低下している。この原因として、出現時間のパラメータ値が大きくなったことによって、音高差特徴と音高推移特徴が反映されなかったものと考えられる。ここで、入力ハミングに対して詳細な分析を行った。表１に、従来（α＝１）の入力ハミングの順位を基準に、各パラメータ毎の順位の向上曲数と下落曲数を示す。
【００８９】
【表１】
2009015535.tif 000015
【００９０】
この表より、順位が向上したデータはパラメータ値４で頭打ち（５０曲中７件）となっており、下落したデータ数はパラメータ値が大きくなると増加している。このことから、出現時間パラメータの設定に際しては、音高差特徴量と音高推移特徴量も反映できるように考慮する。また、類似度演算手段２２によりＥＭＤ計算内のパラメータの値の自動設定することもできる。
（実施例５の評価）
【００９１】
次に、実施例５に係る総輸送量計算内重み付けＥＭＤ改良手法に対する検索精度の評価を行う。図１６に、総輸送量計算内重み付けＥＭＤの精度を比較したグラフを示す。ここでは、総輸送量計算内での音符順番の差に対応したペナルティβを、１／５、１／２としたときの精度と、従来手法としてβ＝０のときの精度を、各々比較している。この図から、ペナルティβを与えることによって、正解曲が上位に検索でき、精度が向上していることが確認できた。β＝１／２では、検索件数２５位までにすべての入力ハミングに対して正解曲が検索できた。
【００９２】
次に、ペナルティβの値の違いにおける精度を検証する。図１７に、βを０、１／１０、１／５、１／２、１と変更したときの検索精度を表している。この図より、βの値を変更すると、検索精度に違いが生じた。β＝１／１０では、従来手法のβ＝０と比較すると検索精度は変化が少ない。これは、ペナルティの値が小さく総輸送量計算の際、ペナルティの影響が小さく検索精度にも影響しなかったためと考えられる。また、β＝１／５、β＝１／２では、従来手法より精度が向上したことが確認できた。
【００９３】
なお、ペナルティをβ＝１にした際、検索精度は従来手法より低下した。これは、正解曲のメロディ片においても音符の差の大きいところに分配フローを生成しているため、正解曲のメロディ片に対してもペナルティが大きくなり、順位を下げる結果となったものと考えられる。このとき上位に上がったデータは、部分ハミング片に含まれる音符数がほぼ等しい、誤ったメロディ片が誤検索されていた。表２に、従来手法の入力ハミングの順位を基準に、各ペナルティ毎の順位の向上曲数と下落曲数を示す。
【００９４】
【表２】
2009015535.tif 000016
【００９５】
この表より、ペナルティを大きくすると順位が向上した曲が増えることが確認できる。実験によればペナルティ値β＝１／２のとき、向上曲数が最大となった。また、β＝１、β＝２では下落した曲が向上曲数を上回る結果となり、図１７からも判るようにペナルティが大き過ぎると精度低下の原因となる。本実験データに対しては、β＝１／５、β＝１／２がペナルティ値として最適であるといえる。
（実施例３の評価）
【００９６】
次に、ＥＭＤ距離計算に用いる音楽特徴量として、出現時間、音高差特徴量、音高推移特徴量に加えて、２つ前の音符との音高差特徴量を用いて検索を行った実施例３に係る検索方法の精度を評価する。図１８に、２つ前の音符との音高差を追加した際の検索精度を示している。この図より、検索順位５位までの検索精度は従来手法より６％向上した。音楽特徴量を追加することにより、正解メロディを正確に特定しやすくなったためと考えられる。
（実施例７の評価）
【００９７】
最後に、上記実施例３〜６の手法を組み合わせた実施例７として、その検索結果を従来手法と比較したグラフを図１９に示す。この図より、実施例７に係る手法での上位５位までの検索精度は、従来手法の検索精度を８６％から９４％へ向上させており、実施例７の有用性が確認された。また、本実験で用いたハミングにおいては、検索順位２５位までに正解曲を検索できた。これらの結果から、本発明に係る手法の有効性を確認することができた。
【００９８】
また図２０に、楽曲は同じであるが、異なる人間がハミングした場合の検索精度の変化を示す。この図において、ハミングＡ、ハミングＢは異なる人間が同じメロディをハミングしたものであり、異なる人間がハミングすると音長、音程にばらつきがあることがわかる。この２つのハミングを入力とし、ＤＰマッチング、及び実施例７に係る手法を用いて検索を行った。ＤＰマッチングを用いた検索では、ハミングＡでは検索結果１位に正解のメロディを検索できたが、ハミングＢでは検索結果５０位までに正解メロディを模索できず、誤検索となった。これに対し、実施例７に係る手法ではハミングＡ、ハミングＢ共に検索結果１件に同じ正解メロディを検索できた。
【００９９】
ＤＰマッチングにおいて誤検索となった原因としては、ハミングＢでは音程のズレた音符が複数含まれているため、ＤＰマッチング距離計算において、音程のずれた音符のペナルティが距離に加算されたためと考えられる。このことから、ＤＰマッチングでは正確なハミングに対しては頑健な模索が可能であるが、音程のズレた音符が複数含まれるハミングに対しては検索が困難であるといえる。
【０１００】
一方、実施例７に係る手法では、音程のズレにも対応した検索が可能である。これは、音程のズレた音符の音長を、輸送コストが小さくなるように分配することで、音程のズレに対するコストの増加を抑えることができるためと考えられる。このように、ＥＭＤを用いた手法を改良することで、音長、音程のばらつきを考慮した柔軟な検索が可能であるといえる。
【０１０１】
以上のように、距離尺度としてＥＭＤを用いたハミングによる類似音楽検索を改良することで、検索精度を向上させることができる。特に、ＥＭＤ計算内の改良と検索結果のマージ方法を適用することで、実際のハミングデータを用いた評価実験では、従来のＥＭＤを用いた検索手法に比べ検索精度を向上できることが確認された。さらに、ＥＭＤ計算内のパラメータの値を自動設定したり、輸送コスト計算内ＥＭＤ改良手法と総輸送量計算内ＥＭＤ改良手法の両方を組み合わせることでも、より高速化、高精度化を図ることが期待される。
【産業上の利用可能性】
【０１０２】
本発明の類似音楽検索装置、類似音楽検索方法、類似音楽検索プログラム及びコンピュータで読み取り可能な記録媒体は、音楽ダウンロードサイトにおいて、ユーザが所望の音楽検索をする際にハミングで入力して、類似する音楽を検索する用途に好適に適用できる。
【図面の簡単な説明】
【０１０３】
【図１】本発明の一実施の形態に係る類似音楽検索システムを示すブロック図である。
【図２】ハミング入力による類似音楽検索システムの全体の流れを示す概念図である。
【図３】スライディングウインドウ方式によりメロディを分割する様子を示す概念図である。
【図４】類似音楽検索プログラムの起動時のユーザインターフェース画面を示すイメージ図である。
【図５】類似音楽検索プログラムの検索時のユーザインターフェース画面を示すイメージ図である。
【図６】類似音楽検索プログラムの検索結果のユーザインターフェース画面を示すイメージ図である。
【図７】ＥＭＤの計算処理の例を示す概念図である。
【図８】ＥＭＤに適用する音楽特徴量の生成例を示す概念図である。
【図９】音楽特徴量内の音符数を削減する様子を示す概念図である。
【図１０】分配フロー毎の音符間距離の分布を示すグラフである。
【図１１】音楽特徴量として２つ前の音符との音高差を追加する例を示す概念図である。
【図１２】実施例６に係る検索結果マージ方法と、従来のＤＰマッチングに部分ハミング片ＯＲ検索を用いた場合の検索結果を示すグラフである。
【図１３】実施例４に係る輸送コスト計算内重み付けＥＭＤの検索精度を従来例と比較したグラフである。
【図１４】図１３において出現時間パラメータαを１〜３に変化させた場合の検索精度を比較したグラフである。
【図１５】図１３において出現時間パラメータαを４〜６に変化させた場合の検索精度を比較したグラフである。
【図１６】実施例５に係る総輸送量計算内重み付けＥＭＤ改良手法に対する検索精度を従来例と比較したグラフである。
【図１７】ペナルティβを変化させた場合の検索精度を比較したグラフである。
【図１８】実施例３に係る２つ前の音符との音高差特徴量を用いた検索方法の検索精度を従来例と比較したグラフである。
【図１９】実施例７の検索結果を従来例と比較したグラフである。
【図２０】同じ楽曲を異なる人間がハミングした場合の検索精度の変化を示す概念図である。
【図２１】従来のリズム入力による音楽検索装置の構成を示すブロック図である。
【符号の説明】
【０１０４】
１００…類似音楽検索システム
２００…類似音楽検索プログラムのユーザインターフェース画面
１０…入力音楽データ入力手段
１２…音楽データ変換手段
２０…特徴量演算手段
２２…類似度演算手段
２４…検索結果マージ手段
３２…登録音楽データ蓄積手段
３４…メロディ片特徴量蓄積手段
３６…付随情報蓄積手段
４０…メモリ手段
４２…入力片特徴量保持手段
５０…検索結果出力手段
５２…表示手段
２０１…音楽データ蓄積部
２０２…リズムデータ生成部
２０３…リズムデータ蓄積部
２０４…音楽付随情報蓄積部
２０５…時系列信号入力部
２０６…類似リズム検索部
２０７…検索結果生成部
２０８…検索結果出力部
２１０…入力音楽データ指定欄
２２０…「試聴」ボタン
２３０…「フレーズ形式検索」ボタン
２３２…「曲目形式検索」ボタン
２４０…「ハミングの部分指定検索」欄
２５０…検索結果表示欄
【図１】
2009015535.tif 000017
【図３】
2009015535.tif 000018
【図７】
2009015535.tif 000019
【図８】
2009015535.tif 000020
【図９】
2009015535.tif 000021
【図１０】
2009015535.tif 000022
【図１１】
2009015535.tif 000023
【図１２】
2009015535.tif 000024
【図１３】
2009015535.tif 000025
【図１４】
2009015535.tif 000026
【図１５】
2009015535.tif 000027
【図１６】
2009015535.tif 000028
【図１７】
2009015535.tif 000029
【図１８】
2009015535.tif 000030
【図１９】
2009015535.tif 000031
【図２１】
2009015535.tif 000032
【図２】
2009015535.tif 000033
【図４】
2009015535.tif 000034
【図５】
2009015535.tif 000035
【図６】
2009015535.tif 000036
【図２０】
2009015535.tif 000037