IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Corrélation entre deux nuages de points


Sujet :

Algorithmes et structures de données

  1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2016
    Messages
    27
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2016
    Messages : 27
    Points : 12
    Points
    12
    Par défaut Corrélation entre deux nuages de points
    Bonjour à tous,
    J'ai besoin de vos conseils !!
    Voici la situation :
    Je dispose d'une liste de couples (couples temps/frequence de maxima d'intensité sonore) qui représente une chanson de 30 secondes.
    Je dispose également d'une deuxième liste de couples qui correspond à un échantillon de 5 secondes pris au hasard dans le morceau précédent.
    Or dans cet échantillon de 5 secondes, un bruit de discussion à été placé en arrière fond (ajouté volontairement avec Audacity).
    La seconde liste a donc été perturbée à cause du bruit (plus ou moins en fonction de son amplitude).
    Je voudrais établir une correspondance entre les deux listes (je dispose d'une base de données de morceaux et d'échantillons).

    Pour cela je voudrais établir une sorte de "corrélation entre nuages de points" (l'échantillon et le morceau dont il est tiré auraient une bonne corrélation et l'échantillon aurait une mauvaise corrélation avec les autres morceau de la base).
    Malheureusement je ne trouve pas de méthode allant dans ce sens... J'ai uniquement trouvé des méthodes utilisant des barycentres et des axes d'inertie dans le nuage.

    Auriez vous une idée ?
    Merci par avance,
    Alextoche

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Bonsoir,

    J'avais lu un papier sur un algo qui faisait ce genre de chose (reconnaissance façon Shazam).

    Référence = Morceau original = (t1,f1) (t2,f2) (t3,f3) ...
    Signal = extrait à identifier = (t'1,f'1) (t'2,f'2) (t'3,f'3) ...

    L'idée c'était:
    1. prendre le 1er point du signal: Psig.
    2. trouver un point correspondant (=meme frequence) dans la référence: PRef.
    3. calculer l'offset T entre Pref et PSig
    4. calculer le ratio R = Pref.amplitude / PSig.amplitude
    5. Inspecter tous les autres points du signal et regarder s'il existe une correspondance dans la référence.
    (point correspondant = même frequence, meme ratio R, meme offset T)
    6. pour chaque point ayant une correspondance, augmenter le score de 1 pour la solution (R,T)
    7. Retour à l'étape 2 s'il y avais plusieurs points possibles dans la référence.
    8. Retour à l'étape 1 en prenant le 2nd point dans le signal, et ainsi de suite.

    Note: L'étape 5 consiste à "aligner" la référence et le signal sur un point "commun", et compter combien d'autres points s'alignent.

    Au final, la solution (R,T) avec le plus gros score est la meilleure solution pour cette référence.
    On peut alors calculer un score de correspondance (nombre de correspondance vs nombre de non-correspondance)
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2016
    Messages
    27
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2016
    Messages : 27
    Points : 12
    Points
    12
    Par défaut
    Merci pour votre réponse !!
    J'ai déjà implémenté un algo qui trouve l'offset qui maximise la correspondance entre l'échantillon et le morceau mais je n'avais pas pensé à introduire de ratio !!
    Malheureusement j'ai l'impression que dès que j'ajoute du bruit à mon morceau, l'offset est de moins en moins marqué en terme d'occurences, il est assez difficile à définir car les fréquences bougent pas mal ... C'est pourquoi je cherche une méthode qui analyse le nuage de point dans sa globalité car sa "forme" est assez caractéristique (même à vu d'oeil).
    Merci pour vos idées !
    Alextoche

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Alextoche Voir le message
    l'offset est de moins en moins marqué en terme d'occurences, il est assez difficile à définir car les fréquences bougent pas mal ...

    Tu travailles directement sur le spectrogram brut (issue de la FFT) ? Si oui, essaye de travailler sur un spectrogram filtré.

    Par exemple en calculant la fréquence centrale (spectral centroid) dans des bandes de fréquence (par exemple, dans l'échelle de Mel).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2016
    Messages
    27
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2016
    Messages : 27
    Points : 12
    Points
    12
    Par défaut
    Bonjour à tous !!

    Voici où j'en suis :

    1- Je pars d'un morceau de musique
    2- Je construis un sonagramme (x=instant dans la chanson, y=fréquence, z=amplitude) de ce morceau
    3- Je filtre ce sonagramme en ne gardant que les amplitudes supérieures à une certaine valeur AMPLITUDE_MAX
    4- Le sonagramme filtré est une courbe 3D, je découpe le plan (O,x,y) en carrés identiques et je cherche un maximum local de la courbe sur chacun de ces carrés

    J'obtiens ainsi une liste de couples [temps,fréquence] (je ne garde pas l'amplitude des maxima) qui résume mon morceau

    5- je prends un extrait au hasard dans le morceau
    6- A l'aide d'Audacity je rajoute en arrière plan un bruit de discussion
    7- J'applique le même procédé que précédemment à cet échantillon

    J'obtiens ainsi une liste de couples [temps,fréquence] qui résume mon échantillon bruité

    8- Je détermine l'offset temporel entre les deux listes
    9- Je compte le nombre de couples qui se correspondent (à une tolérance DELTA_fréquence fixée près) entre les deux morceaux
    10- je renvoie le pourcentage de couple reconnu

    Le problème est le suivant :

    Quand l'échantillon n'est pas bruité, la méthode décrite marche très bien !!

    Par exemple avec :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    morceau_15 = [[0, 233], [1, 87], [2, 389], [2, 802], [3, 146], [3, 279], [4, 322], [4, 546], [4, 605], [7, 5], [15, 424], [35, 510], [35, 543], [35, 621], [35, 682], [35, 788], [35, 838], [35, 907], [35, 948], [41, 144], [42, 86], [48, 5], [49, 381], [50, 272], [52, 190], [54, 54], [74, 741], [81, 937], [82, 702], [85, 88], [87, 565], [87, 607], [88, 128], [89, 5], [93, 173], [93, 259], [94, 403], [101, 230], [102, 349], [105, 58], [109, 490], [109, 927], [110, 378], [116, 299], [120, 5], [121, 612], [121, 660], [121, 696], [121, 786], [122, 542], [130, 216], [141, 448], [142, 737], [142, 771], [142, 864], [142, 909], [143, 941], [145, 58], [151, 5], [164, 130], [165, 98], [187, 492], [187, 606], [187, 858], [187, 947], [188, 256], [188, 655], [188, 803], [189, 708], [197, 296], [198, 73], [202, 5], [204, 146], [212, 220], [212, 357], [217, 85], [220, 505], [230, 302], [231, 386], [242, 895], [246, 742], [247, 51], [251, 513], [251, 607], [256, 944], [259, 705], [259, 775], [259, 843], [261, 565], [261, 629], [267, 137], [271, 223], [284, 5], [287, 117], [287, 742], [292, 270], [292, 307], [292, 419], [292, 513], [292, 567], [298, 73], [302, 365], [308, 98], [318, 146], [320, 688], [320, 723], [320, 805], [321, 896], [328, 830], [330, 87], [335, 508], [337, 4], [339, 596], [340, 665], [348, 550], [352, 230], [353, 24], [360, 437], [361, 155], [361, 195], [361, 312], [361, 389], [361, 468], [361, 935], [368, 109], [370, 875], [371, 691], [371, 800], [372, 365], [391, 137], [394, 714], [400, 523], [400, 630], [400, 785], [400, 837], [404, 185], [404, 222], [404, 259], [404, 333], [408, 108], [410, 36], [414, 879], [420, 364], [422, 72], [427, 577], [427, 724], [427, 955], [450, 54], [450, 109], [454, 865], [456, 524], [458, 146], [459, 293], [463, 436], [464, 219], [464, 474], [464, 766], [464, 912], [466, 954], [468, 256], [474, 384], [474, 549], [481, 82], [493, 48], [494, 727], [494, 799], [498, 952], [500, 366], [501, 4], [517, 115], [518, 20], [524, 427], [524, 787], [526, 526], [527, 663], [527, 734], [528, 555], [528, 629], [528, 857], [528, 912], [532, 288], [533, 181], [535, 87], [542, 219], [542, 255], [542, 474], [555, 27], [558, 737], [559, 643], [559, 782], [560, 383], [567, 329], [569, 292], [570, 865], [570, 901], [571, 362], [577, 835], [579, 473], [580, 437], [581, 766], [581, 802], [584, 511], [588, 182], [595, 653], [604, 129], [604, 271], [604, 379], [609, 82], [610, 218], [616, 45], [616, 680], [620, 760], [622, 805], [622, 879], [624, 472], [625, 181], [626, 293], [629, 548], [630, 329], [630, 439], [630, 951], [631, 257], [631, 586], [640, 385], [641, 111]]
    ET
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     
    échantillon_15 = [[2, 147], [2, 183], [7, 233], [8, 87], [9, 389], [9, 802], [10, 279], [11, 322], [11, 546], [11, 605], [14, 5], [22, 425], [22, 513], [42, 543], [42, 621], [42, 682], [42, 788], [42, 838], [42, 907], [42, 948], [48, 144], [48, 260], [49, 86], [55, 5], [56, 381], [59, 190], [61, 54], [81, 741], [88, 937], [92, 88], [94, 607], [95, 128], [96, 5], [100, 173], [100, 259], [100, 834], [101, 403], [104, 513], [104, 566], [104, 687], [108, 230], [109, 349]])
    J'ai les correspondances suivantes entre l'échantillon_15 et les morceaux de 1 à 15 (de gauche à droite) :

    10.0, 8.11, 9.09, 5.26, 7.89, 4.76, 8.82, 6.98, 11.54, 8.33, 9.09, 11.76, 10.34, 11.11, 82.93

    Mais dès que j'ajoute un bruit de fond (même inaudible quand superposé au morceau) les pourcentages chutent tous aux alentours de 3% (même avec le morceau_15) et il m'est impossible d'établir une correspondance morceau-échantillon ...

    Pour étudier le problème, j'ai considéré le morceau_15 et ce même morceau (dans sa totalité) bruité pour voir si j'arrive à les faire correspondre

    J'ai les listes suivantes :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    morceau_15 = [[0, 233], [1, 87], [2, 58], [2, 174], [2, 389], [2, 802], [2, 827], [2, 885], [2, 937], [3, 146], [3, 279], [3, 350], [4, 322], [4, 453], [4, 546], [4, 605], [4, 658], [4, 768], [4, 904], [5, 628], [7, 5], [11, 72], [13, 742], [13, 787], [15, 309], [15, 424], [15, 513], [21, 98], [28, 44], [35, 510], [35, 543], [35, 582], [35, 621], [35, 682], [35, 788], [35, 838], [35, 907], [35, 948], [36, 480], [36, 731], [36, 754], [40, 114], [41, 144], [41, 260], [42, 86], [42, 230], [42, 403], [48, 5], [49, 164], [49, 354], [49, 381], [50, 272], [52, 190], [52, 326], [53, 436], [54, 54], [54, 219], [54, 466], [56, 248], [74, 741], [74, 775], [74, 809], [74, 840], [80, 901], [81, 937], [82, 657], [82, 702], [85, 88], [87, 565], [87, 607], [88, 128], [89, 5], [90, 290], [91, 375], [93, 173], [93, 259], [93, 834], [94, 403], [94, 806], [95, 786], [95, 871], [96, 143], [97, 513], [97, 687], [101, 201], [101, 230], [102, 349], [105, 29], [105, 58], [109, 490], [109, 927], [110, 378], [112, 164], [112, 464], [115, 190], [115, 435], [116, 245], [116, 299], [116, 408], [117, 327], [120, 5], [121, 590], [121, 612], [121, 660], [121, 696], [121, 786], [121, 887], [121, 947], [122, 542], [123, 130], [129, 267], [130, 216], [130, 289], [135, 72], [137, 145], [138, 313], [139, 98], [139, 174], [141, 448], [141, 568], [141, 633], [141, 828], [142, 595], [142, 670], [142, 710], [142, 737], [142, 771], [142, 864], [142, 909], [143, 941], [145, 58], [151, 5], [151, 959], [155, 29], [159, 257], [159, 480], [164, 130], [164, 299], [164, 786], [165, 98], [169, 373], [169, 418], [175, 171], [179, 194], [185, 86], [185, 129], [187, 492], [187, 606], [187, 735], [187, 858], [187, 947], [188, 256], [188, 464], [188, 655], [188, 687], [188, 774], [188, 803], [189, 338], [189, 708], [197, 296], [197, 371], [197, 420], [197, 445], [198, 73], [202, 5], [204, 146], [204, 205], [204, 234], [208, 936], [210, 163], [210, 569], [210, 613], [212, 220], [212, 357], [213, 110], [213, 192], [213, 275], [213, 329], [217, 85], [220, 505], [220, 686], [222, 472], [224, 405], [226, 29], [226, 58], [226, 234], [230, 151], [230, 302], [230, 366], [231, 172], [231, 386], [234, 132], [236, 259], [238, 702], [238, 839], [239, 220], [239, 808], [241, 480], [242, 895], [244, 272], [246, 109], [246, 742], [247, 51], [251, 513], [251, 607], [253, 5], [255, 880], [256, 73], [256, 944], [259, 705], [259, 775], [259, 843], [260, 803], [261, 565], [261, 629], [261, 914], [267, 137], [267, 173], [267, 194], [271, 223], [272, 480], [277, 73], [279, 281], [279, 347], [279, 809], [279, 835], [284, 5], [287, 117], [287, 742], [287, 859], [287, 943], [289, 251], [292, 270], [292, 307], [292, 419], [292, 513], [292, 567], [292, 630], [298, 73], [300, 786], [300, 809], [300, 830], [302, 235], [302, 344], [302, 365], [302, 399], [308, 98], [308, 130], [308, 197], [312, 432], [312, 502], [312, 625], [315, 5], [318, 146], [318, 183], [318, 773], [320, 688], [320, 723], [320, 747], [320, 805], [321, 896], [328, 830], [328, 958], [330, 87], [330, 174], [330, 936], [331, 115], [333, 232], [333, 641], [335, 438], [335, 508], [335, 698], [336, 872], [337, 4], [338, 462], [339, 596], [340, 665], [341, 359], [342, 765], [348, 550], [350, 332], [351, 624], [352, 230], [353, 24], [355, 48], [357, 134], [357, 755], [359, 293], [360, 437], [361, 5], [361, 155], [361, 195], [361, 273], [361, 312], [361, 389], [361, 468], [361, 896], [361, 935], [368, 109], [368, 328], [368, 765], [368, 912], [370, 875], [371, 691], [371, 800], [372, 365], [372, 657], [373, 86], [376, 65], [377, 479], [378, 44], [379, 738], [379, 855], [391, 137], [394, 714], [396, 167], [396, 918], [396, 950], [398, 27], [400, 454], [400, 486], [400, 523], [400, 564], [400, 587], [400, 630], [400, 656], [400, 785], [400, 837], [401, 695], [403, 281], [404, 185], [404, 222], [404, 259], [404, 333], [407, 147], [407, 739], [408, 108], [410, 36], [412, 906], [414, 440], [414, 879], [415, 389], [419, 461], [420, 364], [422, 72], [427, 504], [427, 534], [427, 577], [427, 642], [427, 694], [427, 724], [427, 755], [427, 794], [427, 828], [427, 926], [427, 955], [429, 597], [436, 19], [438, 148], [439, 375], [443, 83], [444, 349], [445, 243], [449, 331], [450, 54], [450, 109], [452, 700], [453, 729], [453, 813], [454, 865], [455, 367], [456, 524], [458, 146], [459, 183], [459, 293], [463, 436], [464, 219], [464, 474], [464, 766], [464, 912], [465, 401], [466, 954], [468, 256], [470, 720], [474, 384], [474, 549], [476, 111], [481, 82], [481, 274], [482, 574], [483, 146], [484, 247], [489, 29], [493, 48], [494, 508], [494, 630], [494, 727], [494, 751], [494, 799], [495, 436], [496, 828], [496, 929], [497, 387], [498, 952], [499, 172], [499, 484], [500, 341], [500, 366], [500, 464], [500, 878], [501, 4], [501, 291], [502, 196], [502, 221], [517, 115], [518, 20], [524, 391], [524, 427], [524, 787], [524, 944], [525, 49], [526, 526], [526, 687], [527, 663], [527, 734], [528, 5], [528, 488], [528, 555], [528, 582], [528, 629], [528, 857], [528, 912], [529, 311], [529, 349], [532, 288], [533, 181], [535, 87], [538, 110], [538, 366], [541, 146], [541, 329], [541, 439], [542, 65], [542, 219], [542, 255], [542, 474], [544, 874], [545, 803], [555, 27], [558, 737], [558, 956], [559, 521], [559, 551], [559, 643], [559, 782], [560, 56], [560, 164], [560, 383], [560, 716], [561, 192], [562, 246], [567, 130], [567, 329], [568, 37], [568, 110], [569, 219], [569, 292], [570, 865], [570, 901], [570, 937], [571, 362], [577, 835], [579, 473], [580, 437], [580, 546], [581, 584], [581, 766], [581, 802], [584, 511], [585, 389], [585, 728], [587, 73], [588, 182], [588, 871], [588, 944], [589, 908], [595, 609], [595, 653], [604, 129], [604, 271], [604, 352], [604, 379], [604, 407], [605, 489], [605, 523], [606, 164], [609, 82], [609, 245], [609, 326], [610, 218], [611, 193], [613, 110], [615, 650], [616, 45], [616, 680], [617, 714], [617, 931], [620, 760], [622, 805], [622, 879], [623, 829], [624, 472], [624, 908], [625, 181], [625, 508], [626, 73], [626, 293], [629, 548], [630, 329], [630, 439], [630, 951], [631, 257], [631, 586], [631, 659], [631, 772], [637, 84], [637, 633], [640, 385], [641, 111], [641, 137], [642, 685], [644, 273]]
     
    morceau_bruité = [[0, 214], [1, 160], [2, 53], [2, 80], [2, 463], [2, 738], [2, 811], [2, 860], [3, 134], [4, 321], [4, 434], [4, 515], [4, 604], [4, 831], [5, 245], [5, 296], [5, 346], [5, 395], [5, 571], [5, 704], [6, 7], [12, 67], [12, 105], [14, 682], [14, 771], [17, 151], [28, 390], [36, 45], [38, 469], [38, 499], [38, 713], [38, 834], [39, 441], [39, 524], [39, 693], [44, 106], [44, 132], [45, 212], [45, 239], [45, 371], [46, 79], [52, 300], [53, 150], [53, 325], [54, 350], [55, 250], [56, 175], [58, 201], [58, 401], [59, 50], [59, 378], [59, 428], [61, 228], [61, 564], [80, 351], [81, 433], [81, 743], [81, 772], [81, 793], [84, 7], [88, 829], [89, 481], [89, 590], [89, 665], [89, 860], [93, 82], [95, 558], [96, 118], [98, 267], [102, 159], [102, 238], [102, 370], [103, 645], [103, 681], [103, 740], [103, 765], [103, 800], [105, 131], [105, 341], [106, 472], [106, 520], [109, 211], [110, 185], [111, 320], [115, 52], [117, 447], [120, 347], [122, 151], [122, 276], [125, 175], [125, 399], [126, 250], [126, 425], [128, 300], [128, 471], [129, 378], [132, 498], [132, 562], [132, 606], [132, 639], [132, 722], [132, 814], [132, 848], [132, 870], [134, 119], [140, 7], [141, 200], [141, 244], [141, 267], [141, 311], [147, 66], [150, 133], [150, 331], [154, 412], [154, 522], [154, 598], [154, 677], [154, 761], [154, 794], [154, 842], [155, 484], [155, 558], [155, 708], [156, 90], [158, 53], [164, 5], [165, 881], [173, 236], [173, 441], [173, 471], [179, 45], [179, 90], [179, 120], [179, 275], [179, 722], [184, 343], [184, 384], [184, 579], [190, 160], [192, 106], [195, 178], [201, 79], [202, 125], [204, 235], [204, 359], [204, 452], [204, 676], [204, 712], [204, 735], [204, 777], [204, 806], [204, 871], [205, 322], [205, 558], [205, 617], [206, 167], [206, 206], [206, 473], [206, 650], [214, 272], [214, 386], [216, 67], [218, 7], [222, 134], [222, 349], [229, 150], [230, 328], [231, 202], [231, 303], [232, 101], [232, 252], [236, 78], [237, 645], [237, 678], [237, 747], [240, 564], [241, 433], [246, 53], [246, 215], [250, 138], [250, 276], [250, 336], [251, 463], [251, 521], [252, 158], [252, 394], [253, 360], [259, 768], [260, 202], [260, 743], [262, 440], [262, 577], [262, 641], [262, 795], [264, 823], [265, 251], [268, 100], [268, 681], [269, 47], [279, 67], [279, 867], [282, 420], [282, 648], [282, 712], [282, 775], [282, 814], [283, 611], [283, 738], [284, 173], [284, 519], [284, 840], [285, 7], [291, 125], [291, 159], [295, 205], [296, 441], [302, 67], [304, 258], [304, 318], [304, 419], [304, 645], [304, 682], [304, 743], [304, 768], [304, 821], [304, 867], [313, 723], [314, 53], [314, 231], [318, 471], [318, 579], [324, 67], [324, 101], [324, 135], [324, 158], [325, 260], [326, 744], [326, 767], [329, 215], [329, 284], [329, 335], [329, 367], [335, 90], [335, 120], [335, 181], [337, 501], [340, 315], [340, 464], [340, 574], [346, 134], [347, 168], [348, 53], [348, 632], [349, 665], [351, 393], [351, 474], [351, 520], [357, 762], [359, 878], [360, 80], [360, 106], [360, 353], [362, 296], [362, 827], [363, 213], [363, 489], [364, 176], [364, 710], [365, 402], [365, 424], [365, 466], [366, 4], [366, 637], [366, 659], [366, 798], [369, 548], [370, 611], [371, 588], [372, 769], [379, 505], [381, 305], [383, 211], [384, 22], [387, 45], [388, 123], [389, 693], [392, 178], [392, 401], [393, 143], [393, 287], [393, 358], [393, 430], [393, 823], [399, 664], [400, 206], [401, 100], [401, 235], [401, 301], [401, 702], [401, 870], [403, 804], [404, 635], [404, 735], [405, 604], [406, 336], [407, 80], [409, 34], [409, 60], [411, 447], [413, 249], [413, 678], [413, 785], [426, 126], [431, 153], [431, 843], [431, 873], [435, 418], [436, 481], [436, 538], [436, 578], [436, 603], [436, 662], [436, 721], [436, 769], [437, 30], [440, 170], [440, 204], [440, 238], [440, 306], [443, 135], [443, 679], [445, 99], [446, 858], [448, 833], [451, 404], [451, 807], [452, 357], [456, 424], [457, 335], [460, 66], [465, 463], [465, 491], [465, 530], [465, 638], [465, 665], [465, 694], [465, 729], [465, 771], [465, 877], [475, 18], [477, 136], [478, 344], [482, 76], [484, 297], [484, 320], [485, 223], [488, 855], [490, 50], [490, 100], [492, 643], [493, 670], [493, 740], [495, 337], [495, 794], [496, 482], [499, 135], [500, 269], [504, 367], [505, 201], [505, 838], [506, 234], [506, 435], [507, 404], [507, 708], [507, 809], [507, 876], [512, 581], [512, 661], [513, 534], [516, 353], [516, 504], [516, 781], [518, 102], [523, 251], [525, 134], [526, 75], [527, 227], [532, 27], [537, 44], [538, 579], [538, 668], [538, 735], [539, 90], [540, 280], [540, 760], [541, 355], [542, 874], [543, 222], [543, 822], [544, 313], [544, 336], [544, 426], [545, 4], [546, 158], [546, 202], [548, 183], [555, 471], [556, 79], [564, 19], [567, 105], [570, 392], [571, 45], [571, 215], [571, 252], [571, 324], [571, 359], [573, 490], [574, 582], [574, 609], [574, 675], [574, 842], [575, 510], [575, 730], [575, 793], [575, 868], [576, 286], [581, 166], [582, 80], [586, 101], [586, 336], [588, 403], [588, 756], [589, 303], [589, 437], [590, 201], [590, 234], [591, 134], [592, 802], [594, 60], [600, 90], [605, 25], [608, 523], [608, 601], [608, 631], [608, 672], [608, 714], [608, 771], [608, 879], [609, 151], [609, 252], [609, 479], [610, 351], [611, 50], [611, 177], [617, 302], [618, 34], [619, 101], [619, 201], [619, 269], [619, 806], [620, 827], [621, 333], [622, 233], [631, 401], [631, 501], [631, 538], [631, 602], [632, 703], [632, 737], [636, 469], [636, 559], [637, 357], [637, 435], [639, 67], [640, 101], [640, 167], [640, 867], [641, 34], [641, 801], [641, 834], [653, 533], [654, 60], [657, 118], [657, 274], [657, 348], [658, 249], [659, 151], [660, 399], [662, 324], [663, 75], [663, 225], [663, 300], [664, 201], [664, 481], [668, 51], [668, 102], [669, 25], [670, 563], [670, 597], [671, 648], [672, 855], [674, 700], [677, 740], [677, 807], [678, 762], [679, 834], [680, 67], [680, 167], [680, 433], [680, 466], [681, 269], [682, 405], [684, 303], [684, 506], [686, 577], [686, 874], [687, 538], [687, 605], [688, 235], [693, 638], [693, 714], [694, 77], [697, 354], [698, 126], [701, 250], [701, 375], [701, 451]]
    En traçant les nuages de points associés aux listes des morceaux, on remarque facilement à l’œil que le morceau bruité correspond au morceau_15

    Nom : ScatterPlot_1.png
Affichages : 479
Taille : 15,8 Ko morceau_15
    Nom : ScatterPlot_2.png
Affichages : 606
Taille : 15,4 Ko morceau_bruité
    Nom : ScatterPlot_superposition.png
Affichages : 681
Taille : 25,6 Ko superposition

    Avez vous des idées pour établir les correspondances morceau-échantillon quand ces derniers sont bruité ??
    J'ai pensé à des corrélations entre nuages de points mais je ne sais pas bien quelle méthode utiliser et les nombre de points (différent entre le morceau et sa version bruitée) semble poser un problème ...

    Merci d'avance pour votre aide et vos idées !!

  6. #6
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 329
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 329
    Points : 2 562
    Points
    2 562
    Billets dans le blog
    9
    Par défaut Corrélation entre deux nuages de points
    Bonjour,

    On observe effectivement des correspondances locales entre les deux nuages de points; cependant la hauteur du second est manifestement moindre, et le décalage paraît suffisant pour neutraliser tout test de concordance.
    Il faut donc ré-hausser tous les points de la séquence bruitée en multipliant leurs ordonnées (yj) par un facteur (Ky) supérieur à l'unité.
    Celui-ci peut être obtenu de la façon suivante: pour chacun des nuages
    a) déterminer la plus grande ordonnée (Ymax);
    b) inventorier les ordonnées des points les plus élevés, dépassant un seuil arbitraire - par exemple:
    yk > 0.8 * Ymax ;
    c) en déduire la moyenne des valeurs sélectionnées: Hm1 pour le premier nuage, Hm2 pour le second (terme inférieur au précédent).
    Le facteur correctif sera donné par le rapport: Ky = Hm1 / Hm2 > 1 .

    Ton test de superposition devrait ainsi fournir une réponse plus nette.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  7. #7
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 329
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 329
    Points : 2 562
    Points
    2 562
    Billets dans le blog
    9
    Par défaut Corrélation entre deux nuages de points
    En y regardant de plus près, j'ai l'impression que l'on va probablement retrouver, après transformation, un léger excès de points bleus (séquence d'origine) à la limite inférieure des nuages.

    D'où la nécessité d'un calcul plus complexe, mais faisant appel à des procédés standard:
    a) déterminer pour l'ensemble des points de chacun des nuages les moyennes des ordonnées (Ym1, Ym2) et les écarts-types correspondants (Sy1, Sy2);
    b) en déduire le facteur de dilatation Ky = Sy1 / Sy2 ;
    c) superposer le second nuage au premier en imposant aux ordonnées la transformation affine: y'k = Ym1 + Ky * (yk - Ym2) ,
    qui traduit la superposition d'une affinité verticale de facteur (Ky) et d'un translation de même direction, de décalage Dy = Ym1 - Ym2 .

    L'isobarycentre du nouveau nuage obtenu (N'2) coïncide avec celui du nuage initial:

    Moy(y'k) = Moy(Ym1) + Ky * (Moy(yk) - Moy(Ym2)) = Ym1 + Ky * (Ym2 - Ym2) = Ym1

    et ce nuage présente la même dispersion, puisque: y'k - Moy(y'k) = y'k - Ym1 = Ky * (yk - Ym2) ,

    ce qui donne en passant aux écarts-types: S'y2 = Ky * Sy2 = Sy1 .


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  8. #8
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2016
    Messages
    27
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2016
    Messages : 27
    Points : 12
    Points
    12
    Par défaut
    Bonjour,

    Merci pour votre réponse !!
    J'ai en effet remarqué que certaines transformations du plan (homothétie et translation) rendaient la coïncidence "à l’œil" meilleure mais c'est justement cette dernière que je n'arrive pas à traduire ... En fait je cherche ce fameux test de superposition dont vous parlez Et puis dans le cas présent, il y a effectivement un décalage des ordonnées mais le bruit pourrait tout simplement ajouter des points "au dessus du nuage sans bruit". Dans ce cas la translation que vous proposez rendra la superposition moins bonne qu'un superposition directe ...
    Auriez vous une idée ? Comment traduire que "deux nuages se superposent bien" ?
    Merci d'avance !

  9. #9
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 329
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 329
    Points : 2 562
    Points
    2 562
    Billets dans le blog
    9
    Par défaut Corrélation entre deux nuages de points
    Je croyais ton test fonctionnel, et le défaut de réponse dû à un changement d'échelle.

    Citation Envoyé par Alextoche Voir le message
    ... J'ai en effet remarqué que certaines transformations du plan ... rendaient la coïncidence "à l’œil" meilleure mais c'est justement cette dernière que je n'arrive pas à traduire ... En fait je cherche ce fameux test de superposition dont vous parlez ...
    Comment traduire que "deux nuages se superposent bien" ? ...
    Laissons de côté les transformations précédentes, et envisageons deux nuages de points d'effectifs comparables (N1, N2), uniformément répartis dans le même domaine rectangulaire défini par les conditions:
    Xmin <= xk <= Xmax et Ymin <= yk <= Ymax .

    Les deux bornes inférieures sont ici nulles (Xmin = 0 , Ymin = 0), mais cela n'a pas d'importance.

    Les (N1) points du premier nuage occupant le rectangle de dimensions: Lx = (Xmax - Xmin) , Ly = (Ymax - Ymin) et d'aire S = (Lx * Ly) ,
    on peut attribuer à chacun d'eux une surface élémentaire d'aire moyenne S1 = (S / N1) ,
    de contour rectangulaire et de dimensions Dx = (Lx / Sqrt(N1)) , Dy = (Ly / Sqrt(N1)) .

    Ceci posé, on peut admettre qu'un point M2j(x2j, y2j) du second nuage se trouve en quasi superposition avec l'un de ceux du premier M1i(x1i, y1i) s'il se trouve à l'intérieur du rectangle élémentaire centré sur ce dernier, donc si sont simultanément vérifiées les conditions:
    Abs(x2j - x1i) < (Dx / 2) et Abs(y2j - y1i) < (Dy / 2) ; ainsi réapparaît la notion de "tolérance" que tu as évoquée.
    Dès lors que chacun des points (et un seul) du second nuage se trouve à proximité de l'un de ceux du premier, on dénombrera par le test précédent un certain nombre de coïncidences Nc <= Min(N1, N2) .
    Le "taux de superposition" sera représenté par le réel Ts = Nc / N1 , compris entre (0) et (1); il devient égal à l'unité dans le cas limite de deux nuages identiques.

    Il n'est pas évident que ce taux devienne très faible (Ts < 0.5) dans le cas d'un nuage aléatoire (N2), totalement indépendant du précédent - je pense (doute horrible !) au paradoxe des anniversaires; il faudra probablement imposer une sélection plus stricte, par les conditions:
    Abs(x2j - x1i) < (Tx * Dx) et Abs(y2j - y1i) < (Ty * Dy)
    mettant en jeu deux coefficients (Tx, Ty) inférieurs à (0.5).

    Il sera prudent de faire des essais progressifs, en commençant pas des séquences musicales à très faible niveau de bruit.
    La question du redimensionnement du second nuage reste toujours en suspens; le recours aux outils statistiques (#7) me paraît la meilleure solution.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  10. #10
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2016
    Messages
    27
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2016
    Messages : 27
    Points : 12
    Points
    12
    Par défaut
    Bonjour,

    Merci beaucoup pour votre réponse j'aime beaucoup l'idée !! Je vais implémenter et creuser la méthode que vous proposez

    Sinon, une solution fonctionnelle et assez simple (sortie de nul part ) m'a été proposée. Je viens de l’implémenter et elle fonctionne même avec des bruits importants !!

    Étant donné deux nuages de points X = (x1, x2, ..., xn) et Y = (y1, y2, ..., ym) la "distance de Chamfer" (qui pas une distance au sens mathématique du terme) entre X et Y est donnée par :

    d(X,Y) = \sum_{x\in X} \min_{y\in Y} \Vert x-y\Vert + \sum_{y\in Y} \min_{x\in X} \Vert x-y\Vert

    cette distance mesure la proximité entre deux nuages de points : plus elle est faible plus les nuages sont proches (nulle si identiques) inversement si elle augmente.

    Merci beaucoup pour vos aides respectives !!

    Alextoche

  11. #11
    Membre émérite

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    Décembre 2010
    Messages
    1 329
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 77
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : Décembre 2010
    Messages : 1 329
    Points : 2 562
    Points
    2 562
    Billets dans le blog
    9
    Par défaut Distance de chanfrein
    C'est une autre façon d'aborder le sujet, plus directe ...
    ... Je viens de l’implémenter et elle fonctionne même avec des bruits importants !!
    et tu sais t'adapter rapidement
    Il te faudra, pour ce type de distance, évaluer les seuils de bruitage faible, moyen ou élevé.

    Il y a des sources en français sur le sujet - pour autant que tu en aies besoin!


    Telecom ParisTech


    U Strasbourg


    HAL INRIA

    U Aix-Marseille


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  12. #12
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2016
    Messages
    27
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Octobre 2016
    Messages : 27
    Points : 12
    Points
    12
    Par défaut
    Bonjour,
    Merci pour les sources, ça m’intéresse beaucoup
    Je vais tracer la courbe d'évolution de la distance de chanfrein (je pensais que M.Chamfer était un mathématicien mais non ) en fonction de l'intensité du bruit que j'ajoute à mon morceau pour voir.
    Merci encore !!
    Alextoche

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Transformation entre deux nuages de points
    Par EaudeRoche dans le forum Mathématiques
    Réponses: 2
    Dernier message: 21/05/2015, 16h55
  2. Surface entre deux nuages de points
    Par jerrrrrrr dans le forum MATLAB
    Réponses: 5
    Dernier message: 22/12/2014, 11h38
  3. [scatter] Superposition de deux nuages de points
    Par momo032114 dans le forum MATLAB
    Réponses: 3
    Dernier message: 01/08/2008, 12h56
  4. [Débutant] Problème de corrélation entre deux vecteurs vitesses
    Par sydneya dans le forum Signal
    Réponses: 2
    Dernier message: 29/08/2007, 09h08

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo