Le moyen le plus efficace d'extraire les composantes de fréquence du signal audio avec une précision proche de l'homme en temps réel

J'essaie de trouver comment (si possible) extraire les composantes de fréquence d'un échantillon audio arbitraire (généralement de la musique) d'une manière similaire à la FFT, mais dans mes recherches sur l'algorithme FFT, j'apprends qu'il en souffre restrictions sévères à cet effet.

La FFT présente 3 problèmes:

1. Parce que la résolution bin FFT est équivalente à la taille de votre fenêtre, pour obtenir une précision assez raisonnable (disons 1 Hz), vous avez besoin d'une fenêtre déraisonnablement longue (disons 1 seconde). Cela signifie que vous ne pouvez pas détecter rapidement les transitoires ou les fréquences nouvellement introduites. Cela signifie également que le problème ne peut pas être résolu avec un processeur plus rapide et un taux d'échantillonnage plus élevé - la restriction est intrinsèquement liée au temps.

2. Les humains perçoivent la fréquence de façon logarithmique, mais les bacs FFT sont espacés linéairement. Par exemple, une différence de 20 Hz à l'extrémité inférieure de notre audition est énorme , alors qu'une différence de 20 Hz à l'extrémité supérieure est imperceptible. Donc, pour obtenir la précision dont nous avons besoin à basses fréquences, nous devons calculer beaucoup plus que ce dont nous avons besoin à hautes fréquences.

3. Certains de ces problèmes peuvent être résolus par interpolation entre les bacs FFT. Cela peut fonctionner pour beaucoup d'audio musical, car les fréquences sont souvent espacées assez loin et donc pas plus d'une fréquence ne fuit dans une paire de casiers. Mais ce ne sera pas toujours le cas, en particulier pour les sons inharmoniques comme les instruments à percussion. L'interpolation n'est donc qu'une conjecture.

D'après ce que je comprends de l'algorithme DFT / FFT, les sorties (amplitudes bin) sont effectivement la corrélation du sinus / cosinus à la fréquence de chaque bin. Il me semble que si l'algorithme pouvait être repensé de façon à ce que les fréquences de bac soient espacées de manière non linéaire (c'est-à-dire que nous corrélons un ensemble différent de sinus / cosinus), alors nous pourrions atteindre une résolution pyschoacoustiquement égale à toutes les fréquences. Est-ce possible, ou est-ce un rêve chimérique basé sur ma compréhension incomplète des mathématiques impliquées?

Je suppose que je pourrais également résoudre le problème avec la force brute, en corrélant les sinus / cosinus à chaque fréquence qui m'intéresse. Je ne suis pas trop informé sur les mathématiques ici. Est-ce possible? Quelle sorte d'efficacité? Cela résoudrait-il mon problème?

Existe-t-il une manière différente d'obtenir une décomposition de fréquence plus précise et en temps réel d'un signal? L'efficacité du processeur est une préoccupation, mais pas la préoccupation majeure - je suis en partie intéressé à savoir si cela peut théoriquement être fait du tout. Cependant, quelque chose qui est réalisable en temps réel sur une machine de bureau moderne serait idéal.

Comme je l'ai commenté dans un article précédent, la méthode d'analyse temps-fréquence connue sous le nom de "transformée de Fourier à court terme" est équivalente à une banque de filtres, analysant votre signal x . Pour une fenêtre d'analyse donnée w n , de taille N , le filtre à fréquence k / N est: h n = w - n e j 2 π n $X$$x$$w_n$$N$$k/N$

$1/N$$k$

$f_k$$f_{k+1} = 2^{1/12} f_k$$\frac{2^{1/12} - 1}{2} f_k$

Vous pouvez trouver des implémentations du CQT ici et là, une récente du professeur Klapuri, avec un inverse plutôt décent, peut être trouvée ici . Le groupe Audio de Telecom ParisTech a également une implémentation par le professeur Prado, mais je ne l'ai pas encore essayé.

[Brown91] J. Brown, "Calcul d'une transformation spectrale Q constante", Journal of the Acoustical Society of America, 1991, 89, 425-434

EDIT 20121014: quelques réponses et commentaires à vos questions (bryhoyt).

1. Juste des idées générales sur vos propres commentaires à la question principale: vous semblez être intéressé par de nombreuses applications qui ne sont pas, à mes yeux, des problèmes tout à fait triviaux à traiter. La «modélisation du timbre» me semble plus liée à la reconnaissance vocale ou similaire, pour laquelle la résolution ou la précision de la hauteur ou de la fréquence n'est pas vraiment un problème (considérez comment les MFCC sont généralement calculés).

   Considérez également le nombre de chercheurs de haut niveau ( F. Pachet et l'équipe repmus de l'IRCAM, France , pour n'en citer que quelques-uns) qui travaillent sur le thème de l'improvisation automatique et de l'accompagnement: la tâche n'est pas impossible, mais nécessite une expertise dans de nombreux domaines. Pour résumer, un système typique doit imiter le système auditif humain (au moins), mettre en œuvre la perception du son / de la musique / de la hauteur / du rythme, connaître la théorie musicale et prendre des décisions basées sur les estimations de toutes les étapes précédentes. La transformée de Fourier, ou n'importe quelle représentation de signal, n'est qu'un (petit) pas vers l'objectif final - et potentiellement, à mon avis, le mieux compris jusqu'à présent.

   Cela dit, il est toujours possible que tout le monde regarde bien au-delà de ce qui se passe réellement, et que vous puissiez le réprimer dans une solution simple, donc élégante! N'oubliez pas de publier à ce sujet une fois terminé! :-)

2. un échantillon de 0,1 s à 44 kHz est suffisant pour contenir une vaste gamme de fréquences

   $F_s / N = 44100/4410 = 10Hz$

3. La FFT ne peut pas détecter cela pour les basses et hautes fréquences, mais vous dites que d'autres algorithmes peuvent: quel est le compromis?

   Réponse courte: lisez ma thèse sur l'estimation de la mélodie!

   Pour élaborer un peu plus: de nombreux algorithmes d'estimation de hauteur dépassent les limites du FT, grâce à des hypothèses sur les sons à traiter. Nous nous attendons à ce que les notes des sons naturels (voix humaine, hautbois, saxophone, piano ...) soient plus complexes que les sinusoïdes simples. La plupart des sons pitchés sont plus ou moins harmoniques, ce qui signifie qu'ils peuvent être modélisés comme des sommes de sinusoïdes dont la fréquence est un multiple de la fréquence fondamentale.

   Il est donc utile de prendre en compte ces harmoniques lors de l'estimation du pitch, avec des méthodes utilisant des fonctions de détection telles que des sommes spectrales, des produits spectraux ou des fonctions d'auto-corrélation. Quelqu'un a récemment commencé un sujet connexe .

4. Quels sont les compromis? Plus précisément, à quel niveau de précision de fréquence puis-je m'attendre pour une fenêtre raisonnablement courte? (Je comprends que la taille de la fenêtre dans CQT est variable - combien?) Plus précisément encore, à quelle distance pourrai-je me rapprocher de mon env. objectif de 0,5% de différence de fréquence avec une fenêtre de 0,005 s?

   Comme indiqué précédemment, avec une fenêtre de 0,005 s, vous pouvez vous attendre à quelque chose comme 200 Hz de "fuite de fréquence". C'est vraiment un problème uniquement lorsque vous avez 2 sinusoïdes avec des fréquences plus proches que 200 Hz, de sorte que le FT ne pourra pas montrer qu'il s'agit de 2 sinusoïdes différentes. Eh bien, nous sommes loin de votre 0,5% (au fait, un demi-ton est à 6% de la fréquence!) Et 0,005s est vraiment un peu petit pour votre objectif. Cependant, si vous souhaitez fournir une estimation toutes les 0,005 s, vous pouvez toujours traiter des trames qui se chevauchent plus longtemps, comme cela se fait habituellement dans le traitement de la parole / musique. C'est vraiment ce que tu veux?

   $$N_k = \frac{F_s}{f_k (2^{1/B} - 1)}$$ $B$$B=48$$f_k=100Hz$nécessitent environ 0,7 s de fenêtres longues. Ce n'est rien pour dire qu'on perd alors un peu de la résolution temporelle ... Mais comme évoqué plus haut, ce n'est un problème que si l'on oublie la structure du son. De plus, la psychoacoustique considère qu'en dessous de 500 Hz, les humains ne distinguent pas vraiment bien les sinusoïdes: même les humains y sont mis au défi. Bien sûr, nous pouvons espérer que nos ordinateurs peuvent faire mieux que nous, mais ici, nous sommes confrontés à un problème difficile!

   Enfin, notez qu'il existe d'autres façons de calculer une représentation temps-fréquence d'un son, pensez par exemple aux bancs de filtres gammatone. L'avantage du CQT que j'ai mentionné précédemment est qu'il existe un logiciel pour la transformée et son inverseur. Personnellement, je reste fidèle au STFT, cependant, pour sa simplicité et parce que, jusqu'à présent, je n'ai jamais eu besoin d'une meilleure résolution dans les basses fréquences, même pour la séparation des sources.

   [Schoerkhuber2010] Schoerkhuber, C. et Klapuri, A., "Constant-Q transform toolbox for music processing", 7e conférence Sound and Music Computing, Barcelone, Espagne, 2010.

Tout d'abord, avec l'approche classique de la transformée de Fourier à court terme, il existe une alternative à l'interpolation - en particulier des techniques utilisant des informations de phase pour récupérer la fréquence instantanée ( voir cette question ) qui peuvent vous donner très précisément la position d'un pic spectral sans augmentation de la taille FFT. L'inconvénient, comme vous l'avez dit à juste titre, est que vous n'augmentez pas la capacité du système à discriminer les pics adjacents - mais c'est déjà une grande amélioration par rapport à l'utilisation de la fréquence centrale de l'indice FFT bin.

$\frac{sr}{FFT\_size}$) car il "sonde" le signal avec des exponentielles complexes qui ont une intégrale nulle sur la fenêtre d'analyse - et celles-ci doivent avoir une période qui est une division entière de la longueur de la fenêtre d'analyse. Si vous essayez naïvement d'utiliser la même approche pour "sonder" des fréquences à d'autres rapports, cela ne fonctionnera pas parce que vous "sonderez" votre signal avec des fonctions qui ne contiennent pas de cycle complet. Si vous vouliez le faire fonctionner, vous devriez augmenter votre fenêtre d'analyse au multiple le moins commun des périodes de tous les signaux de votre recherche par force brute, et c'est précisément ce que vous voulez éviter!

Il existe une autre approche par force brute qui fonctionne: "sondez" vos signaux avec une exponentielle complexe fenêtrée (ondelettes de Gabor). Ceux-ci sont caractérisés par une fréquence centrale, un temps central et une bande passante (qui mesure la façon dont l'ondelette est répartie dans le temps ou sur la fréquence). Vous devrez évaluer de nombreuses corrélations entre votre signal et ces ondelettes à autant de décalages temporels, de fréquences et de bandes passantes que vous le souhaitez. Le résultat sera le même qu'un STFT "en mosaïque" très flexible dans lequel une taille de fenêtre optimale est sélectionnée pour chaque plage de temps et chaque bande de fréquence. Outre le coût de calcul, l'inconvénient est qu'il n'y a pas d'algorithme efficace et pas d'algorithme causal (vous devrez connaître à l'avance autant d'échantillons que l'ondelette la plus longue de votre dictionnaire). Si vous voulez expérimenter ces techniques,MPTK .

Une dernière classe d'approches qui fonctionnent assez bien pour les signaux musicaux sont les méthodes de suivi / haute résolution dans l'espace. Ils travaillent le problème sous un angle d'estimation du modèle - "en supposant que ce signal est une somme de$k$ quelles sinusoïdes à amortissement exponentiel, quelles sont les meilleures amplitudes / fréquences donnant le moins d'erreur quadratique? ", et en tant que tel, le nombre d'échantillons requis pour obtenir une estimation précise ne dépend que du niveau de bruit. Il y a quelques obstacles à leur fonctionnement, bien que :

• Le nombre de composants $k$doit idéalement être connu à l'avance. Des méthodes d'estimation d'ordre comme ESTER ont été proposées pour choisir de manière optimale l'ordre du modèle.
• Ils fonctionnent bien en présence de bruit blanc - cela nécessite que le signal soit blanchi avant l'analyse; effectuer l'analyse dans les canaux individuels d'une banque de filtres est également utile.

Ceux-ci sont coûteux en calcul, mais ils peuvent fonctionner en ligne, avec de courtes fenêtres si les commandes de modèles et / ou le bruit sont faibles.

Fréquence ou hauteur? Il existe déjà des tonnes de documents de recherche et de livres sur la perception du pitch humain. Mais, IIRC, les humains ont tendance à être mauvais pour "extraire" précisément les fréquences à moins qu'elles ne soient un élément fondamental. Et plusieurs pics de fréquence dans une "bande critique" ont tendance à être perçus comme du bruit. Ainsi, toute méthode avec une «précision humaine proche» peut également devoir inclure également certains échecs d'estimation perceptive humaine.

Une FFT n'est qu'une banque de filtres qui ne sont pas optimaux à de nombreuses fins, sauf si l'orthogonalité et l'inversibilité sont des exigences. D'autres banques de filtres sont possibles si vous n'avez pas besoin de ces deux (et la perception humaine ne le fait clairement pas), comme une banque de filtres de fréquence MEL. Une fois qu'un pic de fréquence est identifié par un banc de filtres de fréquence MEL, une analyse plus approfondie par interpolation FFT ou techniques de vocodeur de phase peut être utile pour affiner une estimation de fréquence de tout pic de fréquence spectral isolé.

Notez qu'aucune autre information n'est réellement collectée par l'une de ces techniques de filtrage utilisées sur la même durée de données du domaine temporel, par rapport à une FFT. Ce qui se passe pourrait en fait être la perte d'informations pour mieux correspondre à «l'inexactitude» ou aux anomalies du système auditif humain.

Et l'estimation de la hauteur à partir d'un ensemble de fréquences est un problème complètement différent, encore une fois un sujet avec de nombreux articles de recherche et chapitre de livres sur l'audiologie et autres.

La dernière partie de votre question sur les performances peut être un hareng rouge. On peut faire des dizaines de FFT et des dizaines de banques de filtres différentes en temps réel sur un processeur de téléphone portable ces jours-ci. Compte tenu des bibliothèques FFT très efficaces disponibles auprès des fournisseurs de CPU, une FFT avec des milliers de bacs "en excès" peut être plus efficace qu'une banque de filtres significativement plus petite mais plus naïve.

Il existe de nombreuses alternatives, mais cela dépend de ce que vous faites. Physiquement, je dirais que nos oreilles ressemblent plus à une banque de filtres parallèles qu'à une FFT, ce qui leur donne une bonne résolution temporelle, et un processus appelé «focalisation» leur donne une bonne résolution en fréquence. Donc, dans certains cas, vous pourriez théoriquement utiliser une banque de filtres, mais cela nécessite beaucoup de traitement, ce qui vous laisse beaucoup de données à traiter.

Il est possible de voir les ondelettes comme un ensemble de filtres particulièrement efficaces et connexes. Le problème avec les ondelettes pour l'analyse musicale et audio est qu'elles ne vous donnent généralement qu'une résolution de 1 octave (bien que vous puissiez faire diverses choses à ce sujet, je n'ai pas vraiment vu les ondelettes être particulièrement utiles en audio).

Une autre approche consiste à utiliser des fenêtres FFT qui se chevauchent. Vous pouvez augmenter la résolution de fréquence de la FFT en regardant non seulement les informations d'amplitude, mais aussi les informations de phase. Cela vous permet d'utiliser des fenêtres beaucoup plus courtes que celles que vous pourriez utiliser autrement, ce qui se traduit par de meilleures performances et une meilleure résolution temporelle. Les fenêtres qui se chevauchent sont difficiles à resynthétiser correctement, et faire trop d'hypothèses sur la phase peut également être dangereux. Quoi qu'il en soit, ces sortes de trucs sont probablement la base de la résolution de problèmes complexes d'analyse temps-fréquence.

Il existe également un certain nombre d'autres outils pour des applications spécifiques.