Discussion :

[kamel.bensaid]

bonjour,
est ce que quelqu'un peut m'expliquer les algorithmes SAPA (Scan-Along Polygonal Approximation) qui servent à compresser les courbes 2d avec perte ?
merci d'avance

[kamel.bensaid]

salut,
on m'a donné l'article original décrivant cette méthode :
http://ieeexplore.ieee.org/xpl/login...mber%3D4121537
je l'ai ensuite implémenté en MATLAB, au cas où cela intéresse quelqu’un :

Code MATLAB :

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
%x et y ont la même taille, eps est l'erreur souhaitée, r va contenir les indices des points retenus
function r = SAPA2(x, y, eps)
 r = 1;
 n = size(x, 2);
 i = 1;
 while i <= n
  maxLowSlp = -inf;
  minUppSlp = inf;
  j = i + 1;
  while j <= n 
   lowSlp = (y(j) - y(i) - eps) / (x(j) - x(i)); 
   if lowSlp > maxLowSlp
    maxLowSlp = lowSlp;    
   end             
   uppSlp = (y(j) - y(i) + eps) / (x(j) - x(i));
   if uppSlp < minUppSlp  
    minUppSlp = uppSlp;    
   end   
   cntrSlp = (y(j) - y(i)) / (x(j) - x(i));
   if cntrSlp < maxLowSlp || cntrSlp > minUppSlp
    temp = r;
    r = [temp j - 1];
    break
   else
    j = j + 1;
   end   
  end
  i = j;
 end
 if r(size(r, 2)) ~= n
  temp = r;
  r = [temp n];
 end 
end
 
%rx et ry sont les sous-vecteurs obtenus par la restriction r
function [rx, ry] = restrict(x, y ,r)
 rx = r;
 ry = r;
 for i = 1 : size(r, 2)
  rx(i) = x(r(i));
  ry(i) = y(r(i));
 end
end

• pour les courbes 1D il faut que y = f(x) (une fonction)
• pour les courbes 2D il faut que :
  • les points suivent un ordre particulier (horaire ou anti-horaire)
  • le dernier point soit égal au premier (cas d'une courbe fermée)