Discussion :

[Julian21]

Bonjour tout le monde !!

Je cherche une librairie qui serait capable de trouver la frequence d'apparition d'un motif dans un tableau.

Je ne connais pas le motif, par contre il se répète très souvent. Les données du tableau sont des floats.

Pour être plus précis, il s'agit d'une courbe proche d'une sinusoïde dont la période et l'amplitude sont quasi constantes.
Le problème, c'est que je ne connais pas ces deux caractéristiques.

J'espère que ce message est assez claire

Merci d'avance pour votre aide

[KiLVaiDeN]

Bonjour,

Je ne comprend pas trop en quoi une librairie serait necessaire pour faire ce "calcul statistique" sur ton tableau;

Si je comprend bien, tu as des valeurs qui se "répètent" dans ton tableau et tu souhaiterais trouver leur fréquence de répétition, ceci avec une "tolérance" près ?

Je me trompe peut-être ?

[Julian21]

non,
mais disons que la suite qui se répète n'est jamais la meme
pour être plus clair, je donne un exemple :

1 2 3 3 4 4 5 6 5 8 9 9 8 9 8 7 7 6 5 5 4 3 2 1 0 1 0 0 1 0 1 2 3 4 5 6 6 5 7 8 9 9 9 8 7 8 7 6 5 4 3 2 2 1 0 0 1 0 1 0 1 2 3 4 5 5 6 7 8 9 20 7 6 5 5 4 3 2 1 1 0 0 ...


j'espère que c'est compréhensible

c'est facile à trouver pour l'amplitude (ici 9) par contre pour la période, c'est moins facile.

le tableau comprend au moins 50 motifs!
il peut y avoir des pics en amplitude (dans l'exemple =>20)

En gros, j'ai une courbe "périodique" et je cherche sa fréquence !

Merci

[poukill]

En gros, j'ai une courbe "périodique" et je cherche sa fréquence !

Là j'ai compris !
C'est possible de coder ça avec la STL, non??

[KiLVaiDeN]

Salut,

C'est plutot dans la partie algorithme que tu trouveras une réponse; je ne pense pas qu'il y ait une librairie en C++ pour ce genre de calcul si spécifique.

Mais je pense que le plus "simple", serait de detecter tes amplitudes, puis après de calculer la période par rapport au nombre de passage à cette amplitude de ta courbe; mais c'est pas très précis comme échantillonage, selon tes données, j'espère que tu en as beaucoup plus pour ta courbe !

Peut-être y-a-t'il un moyen meilleur -> post forum algorithmique

A+

[Julian21]

pour la stl, merci pour l'info, je regarde tout de suite !!

par contre pour l'algorithme, j'ai déja essayé.
Je recherche le maximum, je stocke l'itérateur
puis je recherche le maximum entre le début et le premier maximum (ou entre le premier maximum et la fin), je stocke l'itérateur
...
jusqu'à ...? j'ai essayé plein de condition d'arrêt mais sans trop de succès
je trie mon tableau de maxima et je cherche le plus petit écart entre les maxima à chaque boucle

Pour le nombre d'échantillons, il y en a à la pelle :
+ de 100 motifs (plus ou moins potables) sur environ 50 000 points (+ou-).

[poukill]

Tu trouveras rien de tout fait dans la STL....
Par contre, elle va t'aider dans l'algorithmie "de base": tri (sort() ) etc...
Ca va te permettre de mieux gérer tes propres algo...

Question: pourquoi ne pas stocker dans une liste tous les maximas, puis tu cherches l'écart entre eux?

[Julian21]

pour le tri, il y a pas de problème, j'utilise la fonction std::sort() sur mon std::vector(), ca fonctionne très bien !!

je trie mon tableau de maxima et je cherche le plus petit écart entre les maxima à chaque boucle

je cherche justement le plus petit écart entre deux maxima.

Le problème, c'est que je ne sait pas quand m'arreter de chercher les maxima.
Il faut que le maximum soit bien un extremum !!

[Julian21]

j'ai trouvé une piste du coté de la transformée de fourier mais je ne sais absolument pas comment la calculer. Elle me permettrai d'avoir la fréquence du signal.

Si quelqu'un a des infos la dessus (la transformée de fourier) ??
ou sur un algorithme me permettant de pouvoir calculer cette fréquence ??

Merci !!

[poukill]

j'ai trouvé une piste du coté de la transformée de fourier mais je ne sais absolument pas comment la calculer. Elle me permettrai d'avoir la fréquence du signal.

Hé oui, tu fais bien de penser à ça!
TU trouveras ce que tu veux là dedans :http://kogs-www.informatik.uni-hambu...Transform.html

Cependant, je me sens obligé de te dire que ton idée est .... fausse!
CE que tu vas trouver dans le spectre de fourier, c'est bien la fréquence du signal, mais surement pas la fréquence du motif!
De plus, ton spectre sera certainement un spectre large bande, et non pas un spectre de raie...

Même si ce que je te dis te refroidi un peu, je te conseille d'aller quand même jusqu'au bout de ta démarche, et d'essayer! Qui sait, ça va peut-être donner quelque chose à quoi je n'ai pas pensé...

A plus

[Julian21]

Merci poukill pour l'info !!

CE que tu vas trouver dans le spectre de fourier, c'est bien la fréquence du signal, mais surement pas la fréquence du motif!

Je ne comprends pas ce que tu veux dire dans "la frequence du motif" ??
Avec la fréquence du signal, je saurai combien j'ai de motif en 1 seconde et cela me conviens très bien.
Je connais de plus le nombre d'échantillons que j'ai en 1 seconde donc je peux déterminer la période par la suite très simplement.

En cherchant sur la transformée de fourier, je suis tombé sur fftw mais l'utilisation me parait complexe, je n'ai rien compris au .h

Je vais regarder ton info, parce que pour le moment, je n'ai pas tout compris à propos de la distinction entre les différents spectres.

A++

[poukill]

Je t'explique tout à l'heure (je vais manger...)

En attendant, un autre lien (plus sympa sans doute...)

http://cimg.sourceforge.net/referenc...img.html#z7_24

[Julian21]

Merci !!

L'autre lien m'a un peu donner mal à la tête !!
Je trouve ça un peu compliqué pour juste calculer la fréquence !

Je vais regarder le nouveau lien!!

Bon app!!

[Eldered]

Je ne comprend pas ton pb ... avec un algo qui stocke tes maxima, tu peux trouver l'amplitude, on est d'accord, ensuite, tu parses l'intégralité de ton tableau et dans un second tableau tu stockes les périodes (entre cahque amplitude +/- seuil d'erreur). Tu trouves la périodes qui se retrouve le plus souvent et c gagné ?

La condition d'arrêt c la fin de ton tableau ?

[poukill]

Je ne comprend pas ton pb ... avec un algo qui stocke tes maxima, tu peux trouver l'amplitude, on est d'accord, ensuite, tu parses l'intégralité de ton tableau et dans un second tableau tu stockes les périodes (entre cahque amplitude +/- seuil d'erreur). Tu trouves la périodes qui se retrouve le plus souvent et c gagné ?

La condition d'arrêt c la fin de ton tableau ?

Ce serait le plus simple je pense en effet...
La condition d'arrêt, si tu penses que ton tableau est trop "long", pourrait être d'avoir trouvé n périodes identiques (donc ça converge! )

Sinon, pour la transformée de Fourier, il faut savoir que ça décompose ton signal sur la base des exponentielles complexes (sinus et cosinus), et ça te donne donc une réprésentation en fréquence de ton signal !!!!
Mais pas la fréquence globale! Tu vas obtenir dans ce spectre toutes les fréquences de ton signal (instantanées si tu veux). Et ça, ce n'est pas ce que tu veux...

Il y a bien d'autres méthodes existant pour faire ce que tu veux, mais étant donné que tu ne maîtrises apparemment pas la discipline, ça va être difficile pour toi de pondre l'algo...

Essaye simplement de rechercher les maximums (avec un seuil de tolérance), puis mesure les écart entre eux! La STL là dessus est ton amie...

BYE

[Julian21]

salut Eldered

le problème de l'algo qui stocke les maxima, c'est que je ne sais pas quand m'arreter de les stocker !!
J'ai un tableau contenant tous les points de ma courbe et je cherche comment calculer la frequence de ce signal.
Pour ça,

Je recherche le maximum, je stocke l'itérateur
puis je recherche le maximum entre le début et le premier maximum (ou entre le premier maximum et la fin (pour avoir le maximum de points entre mes deux itérateurs), je stocke l'itérateur
...
jusqu'à ...?

Le problème de cette solution, c'est que si je ne m'arrête pas assez tôt, je vais prendre des maximums qui sont entre deux extremum max.

Le petit schéma (fait rapidement ) en pièce jointe permettra de mieux comprendre mon problème !!

J'espère que j'arrive à me faire comprendre !

[poukill]

Le problème de cette solution, c'est que si je ne m'arrête pas assez tôt, je vais prendre des maximums qui sont entre deux extremum max.

Ben non !
1) D'abord tu fais une première boucle pour trouver LE maximum maximorum.

2) Ensuite tu te donne un seuil de tolérance (à 1 près)

3) Tu scannes ton tableau jusqu'à ce que tu trouves n maximas

4) Tu peux éventuellement vérifier que tu n'aies pas de "points débiles" (par exemple deux points très proches alors que tous les autres sont relativement espacés)

5) Tu calcules la période, et donc la fréquence !

[Julian21]

c'est ennuyeux, je n'est pas de vrai screen shot d'une vrai courbe (ptet que je pourrai demain )

Je ne peux pas mettre en dur le nombre de maximum que je souhaite relever car il varie en fonction de plein de paramètre !
Je peux avoir dans le pire des cas moins de 10 motifs et au max je peux en avoir 400 ou meme plus.
Il me faut une bonne précision !! (dans le cas où le signal est beau)

Quelque fois le signal est à +-0 pendant quelques temps et il peut mettre un certain temps pour d'avoir une belle allure, celle dont on veut connaitre la frequence.

Par la suite, le but est de trouver le motif le plus représentatif de cette portion de courbe, ou pourquoi pas faire le motif moyen de cette courbe avec les motifs ayant plus ou moins la meme periode.

Je vais me replonger dans mon algo, vous m'avez donné des idées !!

[KiLVaiDeN]

J'ai une idée pour ton calcul de période; lorsque tu parcours ton tableau la première fois, repère ton maxima et minima.

Tu obtiendras alors normalement ( si on parle d'une sinusoide ) à chaque passage successif de minima->maxima et de maxima->minima une demi période. Pour détecter un passage à un minima ou à un maxima, tu devras surement jouer avec une tolérance;

Tu prends toutes tes demi-périodes dans ta courbe ( tu les stockes ) puis tu fais la moyenne; Tu repasses une deuxième fois sur cette liste de demi-périodes, tu refais une moyenne ( seulement avec les demi périodes se rapprochant de la moyenne premièrement calculée ) -> une sorte de calcul en 2 passes;

Et hop tu auras une demi-période à peu près correcte, qu'il te suffira de multiplier par 2

j'imagine un truc, mais il y a peut-être plus simple; j'ai l'impression que tes points sont presque aléatoire, alors je ne vois pas mieux.... A+

[Julian21]

Merci pour ton aide KiLVaiDeN,
Mais la courbe n'est pas une sinusoïde (cf piece jointe post #16)
et le problème, c'est que je ne peux pas me fier ni au 1er maximum, ni au 2nd, ni au 3e... parce que le signal présente quelques fois des pics amplitude...
Ces motifs là, il faut les bannir.