Méthodes de comparaison shazam

[bachintosh]

Bonsoir,

Je cherche à programmer un logiciel de reconnaissance musicale, en suivant principalement la méthode d'Avery Wang (Shazam) :
http://www.ee.columbia.edu/~dpwe/pap...g03-shazam.pdf

J'arrive à obtenir la constellation représentant les empreintes de mon morceau, cependant j'ai ensuite des difficultés à comprendre la façon de gérer ces empreintes.

Actuellement, un morceau est défini par une matrice à deux colonnes (temps et fréquence). Donc pour retrouver un morceau parmi ma base de donnée, je compare cette matrice à toutes les matrices de ma base. Le problème c'est que je n'arrive pas à trouver une méthode assez robuste pour détecter quelle matrice à la plus similaire à mon échantillon.
J'ai testé des méthodes avec la distance de Hausdorff, et les DTW mais rien de performant (la matrice de mon échantillon étant bruitée et décalée temporairement)

Donc si quelqu'un pouvait m'expliquer de façon assez détaillée la méthode utilisée par Avery Wang (détaillée sur les figures 1.C et 1.D du lien posté plus haut) ou m'indiquer d'autres méthodes permettant d'estimer la "ressemblance" entre deux matrices, ça serait super sympa !

Merci d'avance

[pseudocode]

J'ai regardé rapidement le document, et il me semble qu'il cherche les co-occurences dans la "constellation". Ces co-occurences sont utilisées comme caractéristiques de l'échantillon, et stockées sous forme de hash (clé,valeur) = (f1:f2t, t1).

La détection se fait en cherchant les hash communs entre 2 échantillons, et en regardant si les valeurs forment une droite (= il y a un offset constant entre les hash des 2 échantillons).


Comme j'ai lu ca rapidement, je ne suis pas 100% sur de ce que j'avance.

[bachintosh]

Envoyé par pseudocode

J'ai regardé rapidement le document, et il me semble qu'il cherche les co-occurences dans la "constellation". Ces co-occurences sont utilisées comme caractéristiques de l'échantillon, et stockées sous forme de hash (clé,valeur) = (f1:f2t, t1).

La détection se fait en cherchant les hash communs entre 2 échantillons, et en regardant si les valeurs forment une droite (= il y a un offset constant entre les hash des 2 échantillons).


Comme j'ai lu ca rapidement, je ne suis pas 100% sur de ce que j'avance.

Oui c'est à peu près ce que j'avais compris également, mais je n'arrive pas à traduire ce raisonnement sous forme de code (ou déjà de pseudo code)

Déjà, pour générer les hash d'un échantillon, il faut définir un "anchor point" et une "target zone" et ensuite calculer les hash entre l'anchor point et chaque empreinte contenu dans la target zone. Mais j'ai plein de questions sans réponse. Genre, est-ce que la target zone est fixe pour une constallation? Est-ce qu'on choisit la target zone de façon aléatoire? Est-ce l'anchor point est choisit arbitrairement, ou bien est-ce que chaque empreinte de la constellation est tour à tour un anchor point? Etc etc, bref j'ai vraiment du mal à me représenter les étapes permettant de coder cette approche, même si j'ai à peu près compris l'idée générale.

Et ensuite, une fois la hash table obtenu, je ne sais pas non plus comment détecter les hash communs entre 2 échantillons, ni comment détecter un offset

[pseudocode]

Mais j'ai plein de questions sans réponse. Genre, est-ce que la target zone est fixe pour une constallation? Est-ce qu'on choisit la target zone de façon aléatoire?

Je suppose qu'elle est fixe : on cherche des fréquences voisines dans un bref laps de temps suivant l'anchor.

C'est en gros équivalent à rechercher les notes suivantes dans la portée musicale : on cherche des notes dans le meme octave (fréquences voisines) et qui suivent la note actuelle.

Est-ce l'anchor point est choisit arbitrairement, ou bien est-ce que chaque empreinte de la constellation est tour à tour un anchor point?

Chaque point est tour à tour un anchor point.

Et ensuite, une fois la hash table obtenu, je ne sais pas non plus comment détecter les hash communs entre 2 échantillons

ils ont la même clé (= le meme hash)

ni comment détecter un offset

Je pense qu'avec un simple accumulateur ca devrait marcher.

hash_sample1 = (f1:f2:dt , time1)
hash_sample2 = (f1:f2:dt , time2)

les 2 hash ont la même clé => il y a correspondance.

Offset = time2-time1
Accumulator[ offset ] = Accumulator[ Offset ] + 1

[bachintosh]

Envoyé par pseudocode

Je suppose qu'elle est fixe : on cherche des fréquences voisines dans un bref laps de temps suivant l'anchor.

C'est en gros équivalent à rechercher les notes suivantes dans la portée musicale : on cherche des notes dans le meme octave (fréquences voisines) et qui suivent la note actuelle.

Mais les résultats dépendent beaucoup de la façon dont on choisit cette target zone non?
Puisque nos hash sont calculés par rapport à des points de cette target zone, si on n'a pas la même zone d'un morceau à l'autre, on ne peut pas trouver des similarités dans les hash (même si les morceaux sont en fait les mêmes)

Envoyé par pseudocode

Chaque point est tour à tour un anchor point.

Ok merci, c'est vrai que ça paraît plus logique.

Envoyé par pseudocode

ils ont la même clé (= le meme hash)

Oui mais comment tu fais pour établir qu'ils ont la même clé? Une fois les morceaux définis par des hash tables (eux-même définis par le choix de la target zone si j'ai bien tout compris), on a donc une base de donnée sur la forme :

Morceau X :
f1:f2:dt, t1 => Anchor Point 1, premier point de la target zone
f1':f2':dt, t1 => Anchor Point 1, deuxième point de la target zone
f1'':f2'':dt, t1 => Anchor Point 1, troisième point de la target zone
...
f3:f4:dt, t2 => Anchor Point 2, premier point de la target zone
f3':f4':dt, t2 => Anchor Point 2, deuxième point de la target zone
etc etc pour toutes les empreintes du morceau (qui seront tour à tour les anchor point) par rapport à tous les points de la target zone

Et tous les morceaux sont construits sur ce modèle non? A partir de là, comment établir qu'un bout de morceau (inconnu) est tiré d'un morceau (connu) répertorié dans la base de donnée?
En répertoriant tous les hash commun entre notre échantillon et le morceau de la base (donc en fait en notant toutes les lignes communes entre deux matrices)? Et si il y a un offset (détecté grâce à la méthode qui tu m'as indiqué précédemment) ça veut dire que c'est le même morceau?
Si c'est ça, j'ai quand même du mal à comprendre la logique qui fait que cette approche fonctionne

Merci de prendre le temps de m'aider en tout cas

[pseudocode]

Envoyé par bachintosh

Mais les résultats dépendent beaucoup de la façon dont on choisit cette target zone non?
Puisque nos hash sont calculés par rapport à des points de cette target zone, si on n'a pas la même zone d'un morceau à l'autre, on ne peut pas trouver des similarités dans les hash (même si les morceaux sont en fait les mêmes)

?

Les dimensions de la zone sont toujours les mêmes.

Une fois qu'on a choisi un anchor-point P1, la zone est clairement identifiée : c'est le rectangle à droite de P1.

Oui mais comment tu fais pour établir qu'ils ont la même clé? Une fois les morceaux définis par des hash tables (eux-même définis par le choix de la target zone si j'ai bien tout compris), on a donc une base de donnée sur la forme :

Morceau X :
f1:f2:dt, t1 => Anchor Point 1, premier point de la target zone
f1':f2':dt, t1 => Anchor Point 1, deuxième point de la target zone
f1'':f2'':dt, t1 => Anchor Point 1, troisième point de la target zone
...
f3:f4:dt, t2 => Anchor Point 2, premier point de la target zone
f3':f4':dt, t2 => Anchor Point 2, deuxième point de la target zone
etc etc pour toutes les empreintes du morceau (qui seront tour à tour les anchor point) par rapport à tous les points de la target zone

Si tu parles bien du même Anchor Point 1, alors f1=f1'=f1''.

Et tous les morceaux sont construits sur ce modèle non? A partir de là, comment établir qu'un bout de morceau (inconnu) est tiré d'un morceau (connu) répertorié dans la base de donnée?

Et bien il y aura un laps de temps avec beaucoup de "hash" en commun.

Morceau inconnu:
...
50:80:09 -> 00
50:90:18 -> 00
80:120:17 -> 10
80:90:11 -> 10
90:120:09 -> 20
...

Morceau connu:
40:90:15 -> 110
80:120:17 -> 120
80:90:11 -> 120
90:120:09 -> 130
120:80:12 -> 140


En commun:
80:120:17 -> offset = 120-10 = 110
80:90:11 -> offset = 120-10 = 110
90:120:09 -> offset = 130-20 = 110

--> suspicion que le morceau inconnu apparaisse a t=110 dans le morceau connu.

(toutes les valeurs sont au pif, bien sur)

[bachintosh]

Envoyé par pseudocode

?

Les dimensions de la zone sont toujours les mêmes.

Une fois qu'on a choisi un anchor-point P1, la zone est clairement identifiée : c'est le rectangle à droite de P1.

Aaaahhh donc la target zone n'est pas fixée pour un morceau, elle est définie différemment pour chaque anchor point ?
Mais dans tous les cas, je ne comprends pas comment choisir cette zone Genre en prenant les 5 ou 6 points les plus proches de l'anchor ça devrait pouvoir le faire?

Envoyé par pseudocode

Si tu parles bien du même Anchor Point 1, alors f1=f1'=f1''.

Exact, merci

Envoyé par pseudocode

Et bien il y aura un laps de temps avec beaucoup de "hash" en commun.

Morceau inconnu:
...
50:80:09 -> 00
50:90:18 -> 00
80:120:17 -> 10
80:90:11 -> 10
90:120:09 -> 20
...

Morceau connu:
40:90:15 -> 110
80:120:17 -> 120
80:90:11 -> 120
90:120:09 -> 130
120:80:12 -> 140


En commun:
80:120:17 -> offset = 120-10 = 110
80:90:11 -> offset = 120-10 = 110
90:120:09 -> offset = 130-20 = 110

--> suspicion que le morceau inconnu apparaisse a t=110 dans le morceau connu.

(toutes les valeurs sont au pif, bien sur)

Ok, merci je commence à comprendre un peu mieux cette histoire de hash et d'offset