Frequence d'apparition d'un motif dans un tableau

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 :roll:

Merci d'avance pour votre aide ;)

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 ?

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 :roll:

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

Citation:

---

Envoyé par Julian21

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??

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+

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-).

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?

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 !!

Citation:

---

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 !!

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 !!

Citation:

---

Envoyé par 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.

---

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

Merci poukill pour l'info !! ;)

Citation:

---

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 :aie:

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++

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

Merci !!

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

Je vais regarder le nouveau lien!!

Bon app!! ;)

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 ?

Citation:

---

Envoyé par 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 ?

---

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

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,

Citation:

---

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:P ) en pièce jointe permettra de mieux comprendre mon problème !!

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

Citation:

---

Envoyé par Julian21

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 ! ;)

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 !!;)

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 :P

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+

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. :?

Citation:

---

Envoyé par 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. :?

---

Je pense que tu dois maintenant voir comment procéder...
Ce que tu peux faire en plus de ce qu'on t'a déjà dit, c'est stocker toutes les valeurs de périodes que tu trouves (entre deux maximas), et forcément tu vas voir par toi même des choses....
Certains points vont etre aberrants, d'autres vont etre juste...
Avec un simple petit traitement, tu devrais trouver rapidement ! ;)

Bon courage !

voila rapidement l'algo auquel je pense pour calculer la fréquence d'une courbe stockée dans un tableau :mouarf: :

je cherche le maximum entre début et fin
j'enregistre son itérateur
je cherche le maximum toujours entre début et fin mais sans chercher dans la zone du premier maximum (zone que je peux définir)
j'enregistre son itérateur
je cherche le maximum toujours entre début et fin mais sans chercher dans la zone du premier maximum, ni du deuxième
j'enregistre son itérateur
.....
à chaque nouvel itérateur enregistré dans mon tableau de maxima, je le trie,
ensuite je calcule la moyenne des maximums dont l'itérateur est enregistré.
....
Et dès que je trouve un maximum qui est bien en dessous de la moyenne des maximas enregistrés, j'arrete.

Mais avant, pour avoir plus de précision, il faudrait que j'élimine les premiers maximums du à l'apparition de pics dans le signal (s'ils existent),
je pense que c'est possible en utilisant la moyenne comme précédemment, ca me permettra d'avoir une moyenne de maximums plus réel.

Cette technique me permettrait de récupérer tous les extremums "potables" de la courbe.
Ensuite je n'ai plus qu'à regarder l'écart entre deux maximums successifs et de faire la moyenne de ces écarts, si les deux maximums ne sont pas séparés par un pic.

enfin fini :scarymov:

J'ai peur que sa prenne beaucoup de temps :(
Vous en pensez quoi si je fais le test sur un tableau de 60 000 points ??? :|

un des problèmes de l'application que je développe est l'acquisition en temps réels. Je n'aurai cependant à faire ce calcul là seulement toute les deux mimutes. ;)

encore une petite question pour toi poukill ;)

tu crois que c'est compliqué à mettre en place la CImg Library ??

C'est pas uniquement pour les images celle-ci ??:(

Parce que la transformée de fourier me permettrai de faire un filtrage logiciel de mon signal (éliminer le 50 Hz) !! Mais la j'espère peut être un peu trop :mrgreen:

Merci encore !!:P

Citation:

---

Envoyé par Julian21

je cherche le maximum entre début et fin
j'enregistre son itérateur
je cherche le maximum toujours entre début et fin mais sans chercher dans la zone du premier maximum (zone que je peux définir)

---

Ton problème va justement être celui-ci. Car t'éloigner de cette zone suppose que tu aies déjà une info a priori sur ton signal...

Imagine une seconde que la fréquence est deux fois plus grande que celle attendue??? Tu peux faire de graves erreurs sur ce point... Je connais personnellement des personnes qui se sont déjà cassé les dents sur point.:aie:

Citation:

---

Envoyé par Julian21

encore une petite question pour toi poukill ;)

tu crois que c'est compliqué à mettre en place la CImg Library ??

C'est pas uniquement pour les images celle-ci ??:(

---

Non, c'est pas uniquement pour les images !!! Enfin, à la base si ! :mrgreen:
Mais une image de dimension 400 x 1, c'est un buffer... Et un buffer, c'est un signal.
Donc ça peut s'utiliser comme ça...

Je l'utilise pour l'imagerie moi. C'est vrai que c'est surement pas le plus pratique pour toi!;)

Citation:

---

Envoyé par Julian21

Parce que la transformée de fourier me permettrai de faire un filtrage logiciel de mon signal (éliminer le 50 Hz) !! Mais la j'espère peut être un peu trop :mrgreen:
Merci encore !!:P

---

Oui, c'est vrai que tu peux faire un filtrage en fourier....
Pourquoi éliminer le 50Hz?

Le problème c'est qu'en filtrant, tu risques de couper un peu ton signal. Mais c'est une bonne idée: un filtrage passe-bas te permet de couper toutes les hautes fréquences de ton signal, y compris les pics qui t'embetent!

De tout façon, je suis obligé de m'éloigner de cette zone,
j'ai tellement d'échantillons que j'ai plusieurs "maximums" pour le maximum de la courbe :koi: (j'espère ke c'est clair !!:? )

La période du motif peut faire au minimum 150 points dans mon tableau et au maximum 600 points, il donc possible de trouver une zone de +/- 75 points. ;)

Citation:

---

Non, c'est pas uniquement pour les images !!! Enfin, à la base si !
Mais une image de dimension 400 x 1, c'est un buffer... Et un buffer, c'est un signal.
Donc ça peut s'utiliser comme ça...

---

C'est plutôt cool ça !! :mouarf:

Pour le filtrage, j'aimerai filtrer le 50Hz parce que les échantillons que j'obtiens viennent d'une carte d'acquisition "faite maison" et que j'obtiens un peu de parasites (visiblement du 50Hz) sur ma courbe.
Pour les pics, ce n'est pas du 50Hz, en fait, la courbe représente la pression ventriculaire d'un coeur de souris (rat ou lapin) et les pics que l'on peut observer proviennent simplement d'une arythmie du coeur, mais il ne faut pas les prendre en compte.

Citation:

---

Envoyé par Julian21

De tout façon, je suis obligé de m'éloigner de cette zone,
j'ai tellement d'échantillons que j'ai plusieurs "maximums" pour le maximum de la courbe :koi: (j'espère ke c'est clair !!:? )

---

C'est TRES clair!
C'est pour ça que je dis que c'est pas facile, mine de rien!
Maintenant, si c'est un battement de coeur, alors OUI !!!
Tu as une connaissance a priori sur ton signal, ça va marcher...;)

EDIT : pour supprimer des pics, renseigne toi sur le Web pour la filtrage médian: c'est ce qu'il te faut ;)

C'est des battements de coeur que tu veux capter?

Citation:

---

Maintenant, si c'est un battement de coeur, alors OUI !!!

---

En fait, c'est pas un battement de coeur (ElectroCardioGramme), ça à vraiment la tete de ce ke j'ai essayé de dessiner en piece jointe.

Mais effectivement, je connais l'allure du signal, quoi que j'ai deux différentes pressions et un ECG (mais celui-là, je verai plus tard, il est plus complexe mais bien filtré).

L'algo risque parfois de ne pas marcher si le coeur ne marche pas trop bien, mais ce n'est pas grave, je permettrai un recalcul de la frequence par selection d'un bout de courbe par l'utilisateur.

je ne veux pas supprimer les pics dû au mauvais fonctionnement du coeur, il est important de les garder, par contre il faut que je les oublie dans mes calculs.

Je réalise le calcul de la fréquence cardiaque par l'intermédiare de la pression ventriculaire (contraction et décontraction du ventricule).
J'ai également d'autres calculs à effectuer, tel que le calcul de dérivée sur le motif... mais ça roule. ;)

Ok, tiens nous au courant ;)
Et pense au :resolu:

J'avais dû mettre sur pause ce petit problème parce que j'avais des choses plus urgentes à faire. Bref, j'ai fini par terminer d'implémenter l'algo que j'avais posté plus haut :mrgreen: .

J'ai pas encore eu le temps de tester sur des courbes très irrégulières mais l'algo fonctionne très bien pour le fonctionnement normal, déjà une bonne chose :mouarf: .

Encore merci pour votre aide

++ :yaisse1: