Comparaison de courbes

**PadawanDuDelphi** · 11/01/2007, 09h36

Bonjour à tous,

Voilà, j'ai un problème tout simple, comparé deux courbes de puissance en fonction d'un pas d'espace variable (un véhicule avançant).

Le problème, c'est que je n'arrive pas à utiliser un écart absolue ou relatif entre deux points des courbes se situant au même temps, puisque dans 99% des cas où mon véhicule se trouve en phase différente (freinage ou lieu d'acceleration). Du coup j'ai des écart gigantesque (même moyenné), alors qu'en réalité mes deux courbes sont similaires sur la majeure partie.

Quelqu'un connaîtrait-il un moyen simple et efficace de comparer deux courbes sans tenir compte de l'écart entre les deux?

Merci bocoup, et désolé si ce que je demande ne parait pas clair...

@+.

**coyotte507** · 11/01/2007, 18h08

Tu peux montrer un exemple de courbes s'il te plait?

**plegat** · 11/01/2007, 20h13

Salut,

Envoyé par PadawanDuDelphi

Quelqu'un connaîtrait-il un moyen simple et efficace de comparer deux courbes sans tenir compte de l'écart entre les deux?

Tu veux comparer deux courbes sans tenir compte de l'écart entre les deux courbes? Elle est bizarre ta phrase là...

Sinon, essaye en interpolant tes valeurs.
Courbe1, tu as les valeurs à t1_1 et t1_2.
Courbe2, tu as les valeurs à t2_1 et t2_2.
On suppose que t2_1<t1_1<t2_2. Tu calcules la valeur de la courbe 2 à t1_1 en interpolant entre les valeurs t2_1 et t2_2 (interpolation linéaire ou un truc plus subtil en fonction de l'allure de tes courbes).
Ensuite tu peux comparer la valeur de la courbe1 à t1_1, et la valeur interpolée de la courbe2 à t1_1. Ca devrait coller mieux.

Parce que sinon, je ne vois pas trop ce que tu as comparé jusqu'à maintenant...

**Graffito** · 12/01/2007, 08h41

Bonjour,

Si je comprends bien, il faut recaler "l'origine" des 2 courbes en x ou en y sur le même point.

La méthode simple (un peu bourrine, mais pas de problème de performance à envisager) consiste à faire varier pas à pas "l'origine" en x ou y de la deuxiéme courbe afin de minimiser l'écart absolu (surface comprise entre les 2 courbes).

Si il faut caler en x et en y, on fera une double boucle sur x et y

**PadawanDuDelphi** · 12/01/2007, 10h06

Tout d'abord merci pour toute vos réponse,

Pièce jointe 8499 (écart entre la bleue foncée et la rose.)

En fait mon problème c'est qu'il existe deux paramètres principaux jouant sur les courbes. J'ai tracé les l'écart absolue entre mes courbes, et je me suis retrouvé avec des "raies" (normal avec le décalage des courbes). Un des paramètres influent sur la hauteur des courbes, et l'autre influe sur le décalage et donc sur la largeur des raie.

J'ai mit en oeuvre en partie la méthode de Graffito, et ainsi à chaque "décrochage" des deux courbes, je calcul le temps qu'il s'écoule avant qu'il y est "recollage."

Mais quel sera le bon critère générale?

* Dire que les deux courbes sont identiquent à 95% du temps totale ?
* La vitesse de réaction et la valeur limite(un peu comme une étude d'un sysrème asservi en automatique) ?
* L'aire de l'écart absolue?

Merci encore pour tout.

@+.

**Nemerle** · 12/01/2007, 14h27

Normalise tes 2 courbes C1 et C2 pour que Max(C1)=Max(C2)=1. Quid de

sqrt( somme((C1(x)-C2(x))^2)

?

Ou sinon, les aires associées me semblent pas mal.

Dans tous les cas, tu dois choisir à partir de quelle valeur les 2 courbes se ressemblent...

**PadawanDuDelphi** · 15/01/2007, 09h58

ok,

Merci beaucoup pour votre aide. La normalisation est une excellente idée, je vais tenter ta formule et le calcul des aires et voir ce que ça donne.

Encore merci,

@+.

**LadyWasky** · 15/01/2007, 14h26

Pour comparer deux courbe et déterminer si elles sont dissemblantes, tu peux utiliser un dérivé de l'algorithme de Levenshtein qui s'appelle le DTW (Dynamic Time Warping), pour toutes les explications et des algos en veux tu en voilà, tu peux jeter un oeil sur les sources du défi Delphi (sources du défieur et des concurrents) n°2 (reconnaissance gestuelle).

Tu devrais trouver ton bonheur sur wikipedia aussi

**PadawanDuDelphi** · 15/01/2007, 14h58

Merci Waskol,

la technique del'algorithme de Levenshtein parait vraiment adapté à mon problème, maême si ça me donne aussi l'impréssion de vouloir tuer une mouche au bazooka...

Je vais faire des tests...Merci encore à tous,

@+.

**LadyWasky** · 15/01/2007, 15h02

Envoyé par PadawanDuDelphi

Merci Waskol,

la technique del'algorithme de Levenshtein parait vraiment adapté à mon problème, maême si ça me donne aussi l'impréssion de vouloir tuer une mouche au bazooka...

Je vais faire des tests...Merci encore à tous,

@+.

Mais c'est exactement ça : tuer une mouche au bazooka

Efficace hein...

PS : code, exemple et explication (+ ou -) dans le message suivant

**LadyWasky** · 15/01/2007, 15h30

Pour info, voici le code qui permet de comparer deux courbes :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
function Distance(Courbe1,Courbe2:array of TPoint;i,j:integer):Extended;
var P1,P2:TPoint;
    c:Extended;
begin
  P1:=Courbe1[i-1];
  P2:=Courbe2[j-1];
  //distance entre le point n°1 et le point n°2
  c:=sqrt((P1.X-P2.X)*(P1.X-P2.X)+(P1.Y-P2.Y)*(P1.Y-P2.Y));
  result:=c;
end;
 
function Minimum(a,b,c:real):real;
var Mini:real;
begin
  mini:=100000;
  if a<mini then mini:=a;
  if b<mini then mini:=b;
  if c<mini then mini:=c;
  result:=mini;
end;
 
function DistanceDTW(Courbe1,Courbe2:array of TPoint):real;
var d:array of array of real;
    DTW:array of array of real;
    i,j,n,m:integer;
    cout:real;
begin
  n:=High(Courbe1)+1;
  m:=High(Courbe2)+1;
  SetLength(d,n+1,m+1);
  for i:=1 to n do
    for j:=1 to m do
      d[i,j]:=Distance(Courbe1,Courbe2,i,j);
  SetLength(DTW,n+1,m+1);
  for i:=1 to m do DTW[0,i]:=100000;
  for i:=1 to n do DTW[i,0]:=100000;
  DTW[0,0]:=0;
  for i:=1 to n do
    for j:=1 to m do
    begin
       cout:=d[i,j];
       DTW[i,j]:=Minimum(DTW[i-1,j]+cout,DTW[i,j-1]+cout,DTW[i-1,j-1]+2*cout);
    end;
  result:=DTW[n,m];
end;

On utilise cette fonction pour comparer deux listes de points

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

distance:=DistanceDTW(Courbe1,Courbe2);

Imaginons que l'on veuille déterminer si une courbe (qui correspond à un relevé effectué dans une situation réelle) se rapproche plus d'une courbeA ou plus de la courbeB (donc A et B sont deux courbes de référence, stockées ensemble et formant donc un dictionnaire)

On compare successivement notre relevé à nos deux courbes de référence :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
d1:=DistanceDTW(CourbeRelevé,CourbeA);
d2:=DistanceDTW(CourbeRelevé,CourbeB);

la valeur la plus petite d'entre d1 et d2 nous indiquera qu'elle est la courbe la plus proche.

Avant de comparer les courbes entre elles, il ne faut pas oublier de normaliser les courbes afin qu'elles tiennent dans un même rectangle (en gros on effectue un changement de repère pour que les valeurs min et max en X et/ou en Y coincident)

Exemple de normalisation pour que deux courbes tiennent dans un carré de 1000*1000 :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
procedure Normaliser(var Courbe:array of TPoint);
var i:integer;
    Xmini,Xmaxi,Ymini,Ymaxi,LargeurTotale,HauteurTotale:integer;
    APoint:TPoint;
   Count:integer;
begin
  Count:=Length(Courbe);
  if Count<=0 then exit;
  Xmaxi:=-10000;
  Xmini:=10000;
  Ymaxi:=-10000;
  Ymini:=10000;
  for i:=0 to Count-1 do
  begin
    APoint:=Courbe[i];
    if APoint.X<Xmini then Xmini:=APoint.X;
    if APoint.X>Xmaxi then Xmaxi:=APoint.X;
    if APoint.Y<Ymini then Ymini:=APoint.Y;
    if APoint.Y>Ymaxi then Ymaxi:=APoint.Y;
  end;
  LargeurTotale:=XMaxi-Xmini;
  HauteurTotale:=YMaxi-YMini;
 
  for i:=0 to Count-1 do
  begin
    APoint:=point(0,0);
    if LargeurTrace>0 then
       APoint.X:=(Courbe[i].X-Xmini)*1000 div LargeurTotale;
    if HauteurTrace>0 then
       APoint.Y:=(Courbe[i].Y-Ymini)*1000 div HauteurTotale;
    Items[i]:=APoint;
  end;
end;

bon dev

**PadawanDuDelphi** · 15/01/2007, 16h16

Merci beaucoup pour ton aide...

Du coup la mouche n'a plus qu'à se tenir tranquille.

Je vais implémenter le code de ce pas.
Merci encore.

@+.

**LadyWasky** · 15/01/2007, 16h34

Envoyé par PadawanDuDelphi

Merci beaucoup pour ton aide...

Du coup la mouche n'a plus qu'à se tenir tranquille.

Je vais implémenter le code de ce pas.
Merci encore.

@+.

Je ne les aime pas ces petites bêtes, il y en avait vraiment trop cet été

**Nemerle** · 15/01/2007, 17h03

Merci au code de waskhol, c'est bien l'idée de mon post précédent.

Mais attention, la distance quadratique

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

c:=sqrt((P1.X-P2.X)*(P1.X-P2.X)+(P1.Y-P2.Y)*(P1.Y-P2.Y));

n'est pas toujours idéale en fonction de ton type de courbes. Tu peux alors jouer en modifiant la distance:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

c:=sqrt((P1.X-P2.X)^a+(P1.Y-P2.Y)^a);

en prenant a<1, ou a>1 (a=2 ou 3 par exemple). A toi de tester différents trucs pour tomber au mieux.

**ronan99999** · 15/01/2007, 17h40

Tu veux surement parler de la distance Ln?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
c := (  (P1.X-P2.X)^n + (P1.Y-P2.Y)^n )^(1/n);

Juste une question on peut comparer L2 à une mesure d'énergie distance dans le plan etc...
comment interpréter les autres, L3 par exemple qu'apporte-elle de plus que L2, que gagne t'on par rapport à un cout supplémentaire?

**Nemerle** · 15/01/2007, 23h59

oui, tu as raison, j'avais oublié de mettre ^1/N à la place de 1/2

les distances L(N) (on dit Lp pour les puristes) te permettent juste d'avoir un comportement différnet de L2: ca contracte ou dilate différemment les écarts, ce qui te permet de mieux fitter avec ton type de courbes en études...

Comparaison de courbes

Algorithmes et structures de données

Discussions similaires

Partager

Partager