Discussion :

[souviron34]

Bonjour à tous..

J'ai une petite question qui pourra sembler un peu bizarre, mais bon.. je la pose...

Dans les algos de simplification comme Douglas-Peucker, on sélectionne une tolérance.

En général, quel degré de simplification - en termes de compression de points par exemple - vous apparaît - ou apparaîtrait - comme satisfaisant, ou comme un objectif à atteindre ? (c'est à dire qu'il reste 5%, 10%, 15% des points ?)

Avez-vous déjà expérimenté ces algos, et avez-vous déduits des seuils, des valeurs limites en dessous desquelles il ne fallait pas descendre, etc ??

Merci d'avance du partage de vos expériences..

[pseudocode]

En général, quel degré de simplification - en termes de compression de points par exemple - vous apparaît - ou apparaîtrait - comme satisfaisant, ou comme un objectif à atteindre ? (c'est à dire qu'il reste 5%, 10%, 15% des points ?)

Personnellement, je met plutôt une tolérance sur l'erreur mesurée/perçue entre la courbe simplifiée et la courbe originale.

Le taux de compression est généralement une contrainte externe qui fixe une limite haute (volumétrie max, temps de transfert max, ...). Je ne m'en sert pas comme "tolérance" pour la simplification.

Si cette limite haute est atteinte alors que l'erreur mesurée est encore supérieure à la tolérance, ca signifie que la courbe originale est trop complexe pour être simplifiée sans erreur tolérable.

[souviron34]

OK..


Je pose la question pace que la question de tolérance m'est apparue relativement "floue"...

Le taux de compression est généralement une contrainte externe qui fixe une limite haute (volumétrie max, temps de transfert max, ...). Je ne m'en sert pas comme "tolérance" pour la simplification.

C'est à dire , qu'utilises-tu ?

Si cette limite haute est atteinte alors que l'erreur mesurée est encore supérieure à la tolérance, ca signifie que la courbe originale est trop complexe pour être simplifiée sans erreur tolérable.

ça t"es arrivé ? Tu as un exemple ?


En fait, c'est parce que j'ai une série d'algos qui eux, se basent purement sur un objectif de réduction.. Mais bien évidemment la plus forte réducton/simplification n''est pas 100%. Je me demandais quelles seraient des valeurs traditionnelles de simplification pour avoir, comme tu dis, des courbes qui gardent une cohérence..

J'arrive facilement à une fourchette de 8 à 14% de points restants avec la plus grande simplification, mais j'ai l'impression qu'on peut faire mieux... Si la fourchette de compression max est entre 16 et 20%, j'ai la cohérence de toutes mes courbes... Je peux arriver autour de 2.5-6% pour toutes les courbes, en gardant leur aspect général, mais ça n'est pas encore tout à fait parfait...

Mais je me demande quelle serait une valeur acceptée pour "une courbe simplifiée au maximum"... J'ai vu que dans quelques articles on citait des taux de 5% pour un Douglas-Peucker encore "signficatif".... Je me demande donc si cette valeur de 5% est valable, ou si c'était juste cet article et ce cas particulier de courbe...

En fait, c'est le fond de ma question : pour vous, que serait la signification de "une courbe simplifiée au maximum" ?

[pseudocode]

C'est à dire , qu'utilises-tu ?

La métrique dépend grandement de ce qu'on considère comme une erreur acceptable pour le problème. La plupart du temps, j'utilise la "Sum of Squared Differences" (SSD), ou la distance de Fréchet.

ça t"es arrivé ? Tu as un exemple ?

Ah oui, ca m'arrive très souvent.
Typiquement, si j'ai un signal d'environ 100Hz échantillonné a 10kHz, je devrais être capable de réduite le nombre de points d'un facteur 10 avec une erreur acceptable. Si ce n'est pas le cas, c'est que le signal d'origine n'était pas a 100hz. Ca fait un très bon indicateur de faux positif.

En fait, c'est le fond de ma question : pour vous, que serait la signification de "une courbe simplifiée au maximum" ?

Pour moi, une courbe simplifiée doit garder les mêmes caractéristiques que celle de départ (allure générale, courbure, moments, ... tout dépend du problème). Dés que la courbe simplifiée perd l'une des caractéristiques, c'est qu'on est allé trop loin.

[souviron34]

OK, merci...

Quand tu dis :

Pour moi, une courbe simplifiée doit garder les mêmes caractéristiques que celle de départ (allure générale, courbure, moments, ... tout dépend du problème). Dés que la courbe simplifiée perd l'une des caractéristiques, c'est qu'on est allé trop loin.

penses-tu qu'il y aurait un intérêt à avoir un algo qui prenne en paramètre d'entrée non pas un degré de tolérance mais un degré de simplification ?

Bien évidemment, les courbures particulières pour des régions très tourmentées seraient très lissées dans le cadre de la simplification maximum, mais l'alllure générale serait préservée...

Ce que j'ai en tête c'est par exemple : 100% de simplification permet d'avoir le minimum de points pour représenter "schématiquement" la courbe, comme par exemple pour la déplacer avec un "drag & drop". Ensuite, il y a pratiquement correspondance entre pourcentage de simplification et nombre de points restants (avec un décalage parce que 100% ne correspond pas à 0% des points).... Mais entre 80 et 90% on a l'allure générale, y compris les "features" donnant les courbures (donc avec environ 20% des points).. etc...

Penses-tu que ça aurait un intérêt ? (aussi, l'algo est linéaire)

[pseudocode]

OK, merci...

Quand tu dis :



penses-tu qu'il y aurait un intérêt à avoir un algo qui prenne en paramètre d'entrée non pas un degré de tolérance mais un degré de simplification ?

Bien évidemment, les courbures particulières pour des régions très tourmentées seraient très lissées dans le cadre de la simplification maximum, mais l'alllure générale serait préservée...

Ce que j'ai en tête c'est par exemple : 100% de simplification permet d'avoir le minimum de points pour représenter "schématiquement" la courbe, comme par exemple pour la déplacer avec un "drag & drop". Ensuite, il y a pratiquement correspondance entre pourcentage de simplification et nombre de points restants (avec un décalage parce que 100% ne correspond pas à 0% des points).... Mais entre 80 et 90% on a l'allure générale, y compris les "features" donnant les courbures (donc avec environ 20% des points).. etc...

Penses-tu que ça aurait un intérêt ? (aussi, l'algo est linéaire)

Si c'est un paramètre que doit donner l'utilisateur, autant rester sur ton idée de départ: régler un taux de compression. C'est ce qu'on fait avec les encodeurs mp3, jpeg, ...

C'est l'utilisateur qui jugera de la qualité visuelle du résultat.

Pour aider l'utilisateur, tu peux lui afficher le "taux de simplification" obtenu sous forme d'indicateur qualitatif (0-25%:très bon, 25-50%: bon, 50-75%:moyen, 75-100% bas).

[souviron34]

Si c'est un paramètre que doit donner l'utilisateur, autant rester sur ton idée de départ: régler un taux de compression. C'est ce qu'on fait avec les encodeurs mp3, jpeg, ...

C'est l'utilisateur qui jugera de la qualité visuelle du résultat.

Pour aider l'utilisateur, tu peux lui afficher le "taux de simplification" obtenu sous forme d'indicateur qualitatif (0-25%:très bon, 25-50%: bon, 50-75%:moyen, 75-100% bas).

Je suis d'accord que c'est l'utilisateur qui détermine : c'est bien d'ailleurs le cas avec la tolérance...

Mais là où c'est un peu plus compliqué, c'est que justement suivant les courbes le taux de compression n'est pas fixe, mais approché... Car c'est le taux de simplification qui est fixe : une courbe à simplification max peut contenir entre x% et y% des points suivant sa complexité... et que 100% de compression ne veut rien dire : on n'aura pas 0% des points...

En fait, c'est l'inverse que je peux faire : indiquer une fourchette de taux de compression obtenus en fonction du degré de simplification...

C'est pour ça qu'il me semblait logique de replacer une tolérance par un degré de simplification : en fait la tolérance est relative (en écart), mais exprimée en absolu, tout comme le taux de compression l'est (en nombre). La "simplification" est (à mon sens) plus "absolue", dans la mesure où, à 100%, on n'obtient que le "squelette de la forme"... (bien qu'évidemment on puisse toujours discuter sur ce qui est le squelette...)


Je te met un exemple....