Yandexがマイクの音楽を認識する方法

音楽カタログの検索は、ユーザーの観点からも技術的にも、さまざまな方法で解決できるタスクです。 Yandexは、曲名と歌詞の両方で検索することをかなり長い間学びました。 また、 Yandexで音声による音楽クエリに回答することもできます。iOSとAndroidを検索しますが、今日はオーディオ信号、より具体的にはマイクから録音された楽曲の検索に焦点を当てます。 この関数は、 Yandex.Musicモバイルアプリケーションに組み込まれています 。



世界には、音楽トラックの認識に専門的に従事している専門企業はわずかしかありません。 私たちが知る限り、検索会社のうち、Yandexはこのタスクでロシアのユーザーを支援した最初の企業です。 まだやることがたくさんあるという事実にもかかわらず、認識の質はすでにこの分野のリーダーと同等です。 また、オーディオフラグメントによる音楽の検索は、Runetで最も単純で明るいトピックではありません。 多くの人が詳細を知りたがっていることを願っています。


技術的には、タスクは次のように定式化されます：スマートフォンに記録された音声信号の10秒の断片（要求と呼びます）がサーバーに到着します。その後、わかっているトラックの中で、断片が記録されたトラックを正確に見つける必要があります。 フラグメントが既知のトラックに含まれていない場合、および音楽レコードではない場合は、「何も見つかりませんでした」と答える必要があります。 完全に一致しない場合に、音で最も類似したトラックに答える必要はありません。

トラックベース

Web検索の場合と同様に、適切に検索するには、ドキュメント（この場合はトラック）の大規模なデータベースが必要であり、それらを正しくマークアップする必要があります。各トラックについて、名前、アーティスト、アルバムを知る必要があります。 おそらく既に推測されているように、このような基盤がありました。 まず、これはYandex.Musicの膨大な数のレコードであり、著作権所有者によって正式にリスニング用に提供されています。 第二に、インターネットに投稿された音楽トラックのセレクションを編集しました。 そのため、ユーザーが最も興味を持っている600万トラックを取得しました。

見込みのないアプローチ

フラグメントとトラックを比較する最良の方法は何ですか？ 明らかに不適切なオプションはすぐに破棄してください。

1. ビットごとの比較 。 デジタルプレーヤーの光出力から直接信号を受信した場合でも、トランスコーディングにより不正確さが生じます。 また、信号の伝送中には、他の多くの歪みの原因があります。音源のスピーカー、部屋の音響、マイクの不均一な周波数応答、マイクからのデジタル化です。 これにより、ファジーなビット単位の比較でさえも適用できなくなります。
2. 透かし 。 Yandex自身が音楽をリリースしたり、ラジオ、カフェ、ディスコで再生されるすべての録音のリリースの制作サイクルに参加した場合、 「透かし」のサウンドアナログをトラックに埋め込むことができます。 これらのラベルは人間の耳には見えませんが、アルゴリズムによって簡単に認識されます。
3. スペクトログラムの非厳密な比較。 厳密な比較を行う方法が必要です。 元のトラックと記録されたフラグメントのスペクトログラムを見てみましょう。 それらを画像と見なし、すべてのトラックの画像から最も類似するものを検索することは非常に可能です（たとえば、 L²などのよく知られたメトリックの1つを使用してベクトルとして比較する）。
   
   しかし、この方法を「正面から」適用することには2つの困難があります。
   a）600万枚の写真との比較-明らかに、高価な操作。 一般に信号の特性を保存するフルスペクトログラムの粗大化でさえ、数メガバイトの非圧縮データを提供します。
   b）いくつかの違いが他のものよりも明らかになっていることがわかります。

その結果、トラックごとに、最も特徴的な（つまり、トラックを簡潔かつ正確に説明する）最小限の数の標識が必要になります。

どのような兆候が歪みを恐れていませんか？

主な問題は、信号源からマイクからのデジタル化までのノイズと歪みのために発生します。 さまざまなトラックについて、オリジナルと異なる人為的にノイズの多い条件で記録されたフラグメントを比較し、多くの例でどの特性が最もよく保存されているかを確認できます。 スペクトログラムのピークはうまく機能し、何らかの方法で強調表示されます。たとえば、極大振幅のポイントとして。 ピークの高さは適切ではありません（マイクの周波数応答によってピークが変化します）が、ノイズが多い場合、周波数-時間グリッド上の位置はほとんど変化しません。 この観察は、 何らかの形で、多くのよく知られたソリューションで使用されています-例えばEchoprintで 。 平均して、トラックごとに約30万のピークが得られます。このデータ量は、クエリの完全なスペクトログラムよりも、データベース内の数百万のトラックと比較するとはるかに現実的です。


ただし、ピーク位置のみが取得された場合でも、クエリと元のセグメント間の複数のピークの同一性は不十分な基準です。 私たちに知られている断片の大部分によって、彼は何も見つけません。 その理由は、リクエストの記録エラーです。 ノイズはいくつかのピークを追加し、他のピークを減衰させます。 信号伝送媒体全体の周波数応答により、ピーク周波数がシフトすることさえあります。 したがって、多くのピークの厳密でない比較になります。

データベース全体で、クエリに最も類似したトラックのセグメントを見つける必要があります。 それは：

• まず、各トラックで、最大数のピークがリクエストと一致する時間オフセットを見つけます。
• 次に、すべてのトラックから、マッチが最大であることが判明したトラックを選択します。

これを行うには、ヒストグラムを作成します。クエリとトラックの両方に存在する各ピーク周波数について、一致したオフセットでY軸に沿って+1を延期します。

ヒストグラムで最も高い列を持つトラックが最も関連性の高い結果です。この列の高さは、クエリとドキュメントの間の近さの尺度です。

検索精度の戦い

経験上、すべてのピークを均等に検索すると、間違ったトラックが見つかることがよくあります。 ただし、ドキュメントピークのセット全体だけでなく、任意のサブセット（たとえば、最も再現性の高い（歪みに強い）のみ）にも同じ近接度を適用できます。 同時に、各ヒストグラムの作成がより安価になります。 これが、このようなピークを選択する方法です。

時間の選択：最初に、同じ周波数内で、録音の開始から終了までの時間軸に沿って、仮想の「落下刃」を開始します。 ブレードの現在の位置よりも高い各ピークを検出すると、「トップ」、つまりブレードの位置と新たに検出されたピークの高さの差を切り取ります。 次に、ブレードはこのピークの元の高さまで上昇します。 ブレードがピークを「検出」しない場合、ブレードは自重でわずかに低下します。


周波数の多様性：最も多様な周波数を優先するために、次のピークの周波数だけでなく、（程度は低いが）隣接する周波数でもブレードを上げます。

周波数選択：次に、1つの時間間隔内で、すべての周波数の中で、最もコントラストの高いピークを選択します。 カット「トップ」の中で最大の局所的最大値。

ピークを選択する場合、いくつかのパラメーターがあります。ブレードの速度低下、各時間間隔で選択されたピークの数、およびピークが近隣に及ぼす影響の近傍です。 そして、それらの組み合わせをピックアップしました。この組み合わせでは、最小数のピークが残りますが、ほとんどすべてのピークは歪みに対して耐性があります。

検索の高速化

そのため、歪みに対して十分な耐性を持つ近接メトリックが見つかりました。 検索の精度は高くなりますが、検索がユーザーに迅速に応答するようにする必要もあります。 最初に、トラックの徹底的な検索を回避するために、メトリックを計算するための非常に少数の候補トラックを選択する方法を学ぶ必要があります。

キーの一意性の改善 ：インデックスを作成できます
→ (, ) 。
残念ながら、可能な周波数の「辞書」はあまりにも貧弱です（256の「単語」-周波数範囲全体を分割する間隔）。 ほとんどのリクエストには、このような「単語」のセットが含まれており、600万件のドキュメントのほとんどに含まれています。 より多くの識別キーを見つける必要があります。これらのキーは、関連するドキュメントにあり、小さなキーは無関係なドキュメントにある可能性が最も高くなります。

これには、密集したピークのペアが適しています。 各ペアはあまり一般的ではありません。
このゲインには代償があります-歪んだ信号で再現する可能性が低くなります。 個々のピークの平均がPである場合、ペアの場合はP ² （つまり、明らかに少ない）です。 これを補正するために、一度に複数のペアの各ピークを含めます。 これにより、インデックスのサイズがわずかに増加しますが、無駄と見なされるドキュメントの数が大幅に減少します（ほぼ3桁）。



ペアを使用して少数のドキュメントを選択したら、それらのランキングに進むことができます。 ヒストグラムはピークのペアにも等しく適用でき、1つの周波数の一致をペアの両方の周波数の一致に置き換えます。

2段階検索 ：計算量をさらに削減するために、検索を2段階に分割しました。

1. 最も対照的なピークの非常にまばらなセットで、トラックの予備選択（プルーニング）を行います。 選択パラメータは、ドキュメントの範囲をできる限り狭めるように選択されますが、それらの中で最も関連性の高い結果を維持します。
2. 最良の答えが選択されることが保証されます-選択されたトラックについて、異なる構造を持つインデックスについては、より完全なピークの選択について、正確な関連性が考慮されます：
   → ( , ) 。
   

このような2段階により、検索が10倍に加速されました。 興味深いことに、ケースの80％で、第1段階でのより粗いランキングの結果は、第2段階で得られた最も関連性の高い答えと一致します。

説明したすべての最適化の結果、検索に必要なデータベース全体がトラックファイル自体の15倍になりました。

メモリ内のインデックス ：最後に、各リクエストに対してディスクがアクセスされるのを待たないために、インデックス全体がRAMに配置され、多くのサーバーに分散されます。 テラバイトかかります。

何も見つかりませんか？

要求されたフラグメントについて、データベースに適切なトラックがないか、フラグメントがトラックのレコードではないことがあります。 「最も不適切な」トラックを表示するよりも、「何も見つかりませんでした」と答えた方がよいときに、どのように決定を下すのですか？ 関連性のあるしきい値に従ってカットオフすることはできません。異なるフラグメントでは、しきい値は何度も異なり、すべての場合に単一の値はありません。 ただし、選択したドキュメントを関連性で並べ替えると、その値の曲線の形状が適切な基準となります。 関連する答えがわかっている場合、曲線は関連性の急激な低下（低下）を明確に示しており、逆に、緩やかな曲線は適切なトラックが見つからなかったことを示しています。

次は何ですか

すでに述べたように、私たちは長い旅の始まりにいます。 検索の品質を改善するために、たとえば、テンポの歪みやノイズの増加などの一連の研究と改善が進められています。 機械学習を適用して、より多様な機能セットを使用し、それらから最も効果的な機能を自動的に選択するようにします。

さらに、インクリメンタルな認識、つまり フラグメントの最初の数秒ですでに答えを出します。

その他の音楽オーディオ検索タスク

音楽の情報検索の領域は 、マイクからの断片のタスクによって使い果たされることからほど遠いです。 圧縮のみが行われた「クリーン」でノイズの多い信号を使用すると、広範な音楽コレクション内の重複トラックを見つけることができ、潜在的な著作権侵害を検出できます 。 そして、不正確な一致やさまざまなタイプの類似性の検索は、カバーバージョンやリミックスの検索、推奨事項を作成するための音楽特性（リズム、ジャンル、作曲家）の抽出、盗作の検索など、全体的な方向です。

それとは別に、 歌われたパッセージを検索するタスクを強調します。 音楽レコードの断片による認識とは対照的に、それは根本的に異なるアプローチを必要とします。オーディオ録音の代わりに、原則として、作品の音楽表現、そしてしばしばリクエストが使用されます。 そのようなソリューションの精度は、（少なくともクエリのバリエーションの比類のない広がりのために）はるかに悪いことが判明しているため、最も人気のある作品のみを認識します。

何を読む

• エイブリィ・ワング： 「強力なオーディオ検索アルゴリズム」 Proc。 2003 ISMIR国際シンポジウム、音楽情報検索、メリーランド州ボルチモア、10月 2003.この記事では、初めて（既知の限り）、スペクトログラムのピークとピークのペアを、典型的な信号歪みに抵抗する兆候として使用することを提案しています。
• D.エリス（2009）： 「堅牢なランドマークベースのオーディオフィンガープリント」 この作業では、「減衰しきい値」（私たちの自由な翻訳では「落下刃」）を使用したピークとそのペアの選択の実装の具体例を示します。
• Jaap Haitsma、Ton Kalker（2002）： 「非常に堅牢なオーディオフィンガープリントシステム」 この記事では、オーディオの連続ブロックを32ビットでエンコードすることを提案します。各ビットは、その周波数範囲でのエネルギーの変化を表します。 説明されたアプローチは、オーディオ信号のブロックのシーケンスの任意のコーディングの場合に容易に一般化されます。
• ニックパーマー： 「オーディオフィンガープリントアルゴリズムのレビューとフィンガープリント生成への多面的なアプローチの検討」 このホワイトペーパーの主な関心は、記載されている問題を解決するための既存のアプローチのレビューです。 可能な実装の段階についても説明します。
• シュミート・バルージャ、ミケーレ・コヴェル： 「音声フィンガープリンティング：コンピュータービジョンとデータストリーム処理の組み合わせ」 Googleの同僚が書いた記事では、コンピュータービジョン手法を使用したウェーブレットベースのアプローチについて説明しています。
• Arunan Ramalingam、Sridhar Krishnan： 「オーディオフィンガープリンティングのための短時間フーリエ変換機能を使用したガウス混合モデリング」 （2005）。 この記事では、シャノンのエントロピー、レニーのエントロピー、スペクトル重心、小規模係数などのさまざまな機能の上に、ガウス混合モデルを使用してオーディオフラグメントを記述することを提案します。 認識品質の比較値が示されています。
• Dalibor Mitrovic、Matthias Zeppelzauer、Christian Breiteneder： 「コンテンツベースの音声検索の機能」 音声サインに関する調査作業：それらを選択する方法、それらが持つべき特性、存在する特性。
• ナタリア・ミランダ、ファビアナ・ピッコリ： 「GPUを使用して音声識別のプロセスを高速化します。 」 この記事では、GPUを使用して署名の計算を高速化することを提案しています。
• 浜脇修平、船沢慎太郎、勝藤二郎、石崎博美、保足啓一郎、滝島康弘： 「異なるビットレートでエンコードされたオーディオに対するロバストなコンテンツベースの音楽検索の機能分析と正規化アプローチ」 MMM 2009：298-309。 この記事では、ケプストラム係数（MFCC）に基づいてオーディオ信号の表示の堅牢性を高めることに焦点を当てています。 このために、ケプストラ正規化法（CMN）が使用されます。