En se promenant dans un bois obscur Sacha et Ondine ont cru entendre au loin les cris de deux Pokémons. Ils soupçonnent que ceux-ci viennent d'être capturés par une Team adverse. Ondine a eu le temps d'enregistrer une partie de chacun de leurs cris. Vous pouvez les télécharger ici et là. Ils souhaiteraient lancer un avis de recherche mais pour cela ils doivent pouvoir déterminer à quels Pokémons appartiennent ces cris. Or les enregistrements sont trop courts pour qu'ils puissent les reconnaître à l'oreille.
Ils décident donc de développer un programme informatique qui va leur permettre de comparer ces deux enregistrements aux cris de Pokémons enregistrés dans la base nationale des cris de Pokémons que vous pouvez télécharger ici. La base contient beaucoup de cris... Vous n'avez pas à tous les considérer. Les enregistrements ayant été faits dans la région de Kalos, vous savez que les deux cris appartiennent à deux des 45 premiers Pokémons.
Chaque cri est enregistré dans un fichier dont le nom correspond au numéro national du Pokémon associé.
Par exemple, le fichier 015.wav correspond au cri de Dardargnan. Vous pouvez trouver la correspondance
entre les numéros et les noms dans le
pokédex national de Poképédia.
Vous n'avez donc qu'à considérer les fichiers 001.wav à 045.wav.
Les cris sont enregistrés au format audio WAV codé en PCM 16 bits sur 2 canaux (c'est-à-dire en stéréo) dont vous pouvez trouver une description sommaire ici.
Un moyen simple de comparer deux signaux audio comportant le même nombre d'échantillons est de calculer la somme d des écarts en valeur absolue des échantillons des deux signaux. Plus cette valeur sera faible plus les deux signaux seront semblables et vice-versa.
Supposons que nous ayons les deux signaux suivants :
s1 : 10 9 7 4 -1 2
s2 : 11 8 5 -1 2 4
alors dans ce cas d = 1 + 1 + 2 + 5 + 3 + 2 = 14
Mais, s'agissant d'extraits de cris, les signaux audio que vous recherchez comporteront moins d'échantillons que les signaux audio de la base qui contiennent, eux, les cris complets des Pokémons. Il faut donc calculer d entre tous les blocs consécutifs du signal de la base de même taille que le signal audio recherché pour trouver le bloc qui ressemble le plus au signal audio recherché.
Supposons par exemple que notre signal audio à rechercher soit le suivant :
r : 1 2 3
et que les signaux de la base soient les suivants :
s1 : 4 5 7 1 8 9 3
s2 : 2 4 5 1 3 8 2
s3 : 1 4 1 2 3 5 6
s4 : 7 8 6 3 2 4 1
les valeurs des distances d1, d2, d3, d4 respectives calculées pour les blocs consécutifs des signaux s1, s2, s3 et s4 sont alors :
d1 : 10 11 12 12 14
d2 : 5 8 5 6 9
d3 : 4 5 0 4 8
d4 : 15 11 7 3 5
la valeur minimale des valeurs minimales des valeurs d1, d2, d2 et d3 est :
min(10,5,0,3) = 0
Elle est obtenue pour le signal s3 qui serait, pour cet exemple, le signal recherché.
Mais en réalité les signaux recherchés et les signaux de la base de données audio comportent bien plus d'éléments.
Validation du défi
Pour valider le défi, indiquez (dans n'importe quel ordre) quels sont les noms des deux Pokémons recherchés dont les extraits de cris vous sont donnés. Par exemple :
BULBIZARRE OSSATUEUR
