enveloppe principale

[Julien Arlandis]

Bonjour,

Soit une fonction discrète f(x_i) définie sur un intervalle de points
régulièrement espacés entre [0;1] et qui prend ses valeurs dans [0;1].
Je cherche un algorithme pour caractériser le barycentre de l'enveloppe
principale, graphiquement on peut se représenter f(x_i) comme une série
d'enveloppes raccordées entre elles par des segments disjoints,
l'enveloppe que je cherche est celle dont l'intégrale moyennée sur son
segment est maximale. J'ai une vague intuition géométrique de
l'algorithme mais je ne parviens pas à le traduire mathématiquement.
En écrivant ce post, j'ai pensé à la méthode suivante :
1) on ne considère que les points dont les images dépassent un certain
seuil, soit tous les x_i dont f(x_i) > s
2) on applique un algorithme de regroupement (k-mean 1D) sur les points
restants.
3) J'identifie le cluster principal (celui où somme(x_i * y_i)/N est
maximal) et je calcule son barycentre.

D'autres idées ?

[efji]

Post by Julien Arlandis
Bonjour,
Soit une fonction discrète f(x_i) définie sur un intervalle de points
régulièrement espacés entre [0;1] et qui prend ses valeurs dans [0;1].
Je cherche un algorithme pour caractériser le barycentre de l'enveloppe
principale, graphiquement on peut se représenter f(x_i) comme une série
d'enveloppes raccordées entre elles par des segments disjoints,
l'enveloppe que je cherche est celle dont l'intégrale moyennée sur son
segment est maximale. J'ai une vague intuition géométrique de
l'algorithme mais je ne parviens pas à le traduire mathématiquement.
1) on ne considère que les points dont les images dépassent un certain
seuil, soit tous les x_i dont f(x_i) > s
2) on applique un algorithme de regroupement (k-mean 1D) sur les points
restants.
3) J'identifie le cluster principal (celui où somme(x_i * y_i)/N est
maximal) et je calcule son barycentre.
D'autres idées ?

Peux-tu préciser un peu plus?
Je sais ce qu'est l'enveloppe d'une famille de courbes, mais pas
"l'enveloppe principale". Et ici on n'a pas de courbes. Tu veux
l'enveloppe de tous les segments [(x_i,f(x_i)),(x_j,f(x_j))] ?

La phrase "graphiquement on peut se représenter f(x_i) comme une série
d'enveloppes raccordées entre elles par des segments disjoints" me
laisse perplexe.

[Julien Arlandis]

Post by efji

Post by Julien Arlandis
Bonjour,
Soit une fonction discrète f(x_i) définie sur un intervalle de points
régulièrement espacés entre [0;1] et qui prend ses valeurs dans [0;1].
Je cherche un algorithme pour caractériser le barycentre de l'enveloppe
principale, graphiquement on peut se représenter f(x_i) comme une série
d'enveloppes raccordées entre elles par des segments disjoints,
l'enveloppe que je cherche est celle dont l'intégrale moyennée sur son
segment est maximale. J'ai une vague intuition géométrique de
l'algorithme mais je ne parviens pas à le traduire mathématiquement.
1) on ne considère que les points dont les images dépassent un certain
seuil, soit tous les x_i dont f(x_i) > s
2) on applique un algorithme de regroupement (k-mean 1D) sur les points
restants.
3) J'identifie le cluster principal (celui où somme(x_i * y_i)/N est
maximal) et je calcule son barycentre.
D'autres idées ?

Peux-tu préciser un peu plus?
Je sais ce qu'est l'enveloppe d'une famille de courbes, mais pas
"l'enveloppe principale". Et ici on n'a pas de courbes. Tu veux
l'enveloppe de tous les segments [(x_i,f(x_i)),(x_j,f(x_j))] ?
La phrase "graphiquement on peut se représenter f(x_i) comme une série
d'enveloppes raccordées entre elles par des segments disjoints" me
laisse perplexe.

Je veux expliquer mon objectif ce sera plus concret.
Je voudrais créer un algorithme pour faire du string art 3D. Pour se
faire on part de la photo d'un visage en niveau de gris et d'une seconde
image en 2.5D de même dimension toujours en niveau de gris où cette fois
l'intensité du pixel représente la hauteur z de chaque point.
Ce que je voudrais c'est associer à chaque ligne une hauteur z pour
recréer une illusion de profondeur.
Si un segment de fil intersecte à la fois un morceau de bouche, un oeil
et un bout du nez, il faut que je fasse un choix pour déterminer quelle
partie du visage le segment contribue le plus à représenter. Dans mon
exemple je vais donc avoir 3 enveloppes pour les 3 parties mentionnées et
je dois ensuite déterminer celle qui est la plus représentative. Peut
être que ce choix doit se faire de façon globale et non pas séparément
pour chaque segment.
Pour l'instant j'obtiens ceci mais je ne me sers pas encore de l'image en
2.5D :
https://lab2.3dmap.fr/sandbox/test1/

[Julien Arlandis]

Post by efji

Post by Julien Arlandis
Bonjour,
Soit une fonction discrète f(x_i) définie sur un intervalle de points
régulièrement espacés entre [0;1] et qui prend ses valeurs dans [0;1].
Je cherche un algorithme pour caractériser le barycentre de l'enveloppe
principale, graphiquement on peut se représenter f(x_i) comme une série
d'enveloppes raccordées entre elles par des segments disjoints,
l'enveloppe que je cherche est celle dont l'intégrale moyennée sur son
segment est maximale. J'ai une vague intuition géométrique de
l'algorithme mais je ne parviens pas à le traduire mathématiquement.
1) on ne considère que les points dont les images dépassent un certain
seuil, soit tous les x_i dont f(x_i) > s
2) on applique un algorithme de regroupement (k-mean 1D) sur les points
restants.
3) J'identifie le cluster principal (celui où somme(x_i * y_i)/N est
maximal) et je calcule son barycentre.
D'autres idées ?

Peux-tu préciser un peu plus?
Je sais ce qu'est l'enveloppe d'une famille de courbes, mais pas
"l'enveloppe principale". Et ici on n'a pas de courbes. Tu veux
l'enveloppe de tous les segments [(x_i,f(x_i)),(x_j,f(x_j))] ?
La phrase "graphiquement on peut se représenter f(x_i) comme une série
d'enveloppes raccordées entre elles par des segments disjoints" me
laisse perplexe.

Je veux expliquer mon objectif ce sera plus concret.
Je voudrais créer un algorithme pour faire du string art 3D. Pour se
faire on part de la photo d'un visage en niveau de gris et d'une seconde
image en 2.5D de même dimension toujours en niveau de gris où cette fois
l'intensité du pixel représente la hauteur z de chaque point.
Ce que je voudrais c'est associer à chaque ligne une hauteur z pour
recréer une illusion de profondeur.
Si un segment de fil intersecte à la fois un morceau de bouche, un oeil
et un bout du nez, il faut que je fasse un choix pour déterminer quelle
partie du visage le segment contribue le plus à représenter. Dans mon
exemple je vais donc avoir 3 enveloppes pour les 3 parties mentionnées et
je dois ensuite déterminer celle qui est la plus représentative. Peut
être que ce choix doit se faire de façon globale et non pas séparément
pour chaque segment.
Pour l'instant j'obtiens ceci mais je ne me sers pas encore de l'image en
2.5D :
https://lab2.3dmap.fr/sandbox/test1/

Il faut pivoter l'image à la souris pour se déplacer dans le modèle 3D.

[Julien Arlandis]

Post by efji

Post by Julien Arlandis
Bonjour,
Soit une fonction discrète f(x_i) définie sur un intervalle de points
régulièrement espacés entre [0;1] et qui prend ses valeurs dans [0;1].
Je cherche un algorithme pour caractériser le barycentre de l'enveloppe
principale, graphiquement on peut se représenter f(x_i) comme une série
d'enveloppes raccordées entre elles par des segments disjoints,
l'enveloppe que je cherche est celle dont l'intégrale moyennée sur son
segment est maximale. J'ai une vague intuition géométrique de
l'algorithme mais je ne parviens pas à le traduire mathématiquement.
1) on ne considère que les points dont les images dépassent un certain
seuil, soit tous les x_i dont f(x_i) > s
2) on applique un algorithme de regroupement (k-mean 1D) sur les points
restants.
3) J'identifie le cluster principal (celui où somme(x_i * y_i)/N est
maximal) et je calcule son barycentre.
D'autres idées ?

Peux-tu préciser un peu plus?
Je sais ce qu'est l'enveloppe d'une famille de courbes, mais pas
"l'enveloppe principale". Et ici on n'a pas de courbes. Tu veux
l'enveloppe de tous les segments [(x_i,f(x_i)),(x_j,f(x_j))] ?
La phrase "graphiquement on peut se représenter f(x_i) comme une série
d'enveloppes raccordées entre elles par des segments disjoints" me
laisse perplexe.

Ce que je cherchais c'est précisément la fonction findpeaks sous matlab
:
https://fr.mathworks.com/help/signal/ref/findpeaks.html

[efji]

Post by Julien Arlandis

Post by efji

Post by Julien Arlandis
Bonjour,
Soit une fonction discrète f(x_i) définie sur un intervalle de points
régulièrement espacés entre [0;1] et qui prend ses valeurs dans
[0;1]. Je cherche un algorithme pour caractériser le barycentre de
l'enveloppe principale, graphiquement on peut se représenter f(x_i)
comme une série d'enveloppes raccordées entre elles par des segments
disjoints, l'enveloppe que je cherche est celle dont l'intégrale
moyennée sur son segment est maximale. J'ai une vague intuition
géométrique de l'algorithme mais je ne parviens pas à le traduire
mathématiquement.
1) on ne considère que les points dont les images dépassent un
certain seuil, soit tous les x_i dont f(x_i) > s
2) on applique un algorithme de regroupement (k-mean 1D) sur les
points restants.
3) J'identifie le cluster principal (celui où somme(x_i * y_i)/N est
maximal) et je calcule son barycentre.
D'autres idées ?

Peux-tu préciser un peu plus?
Je sais ce qu'est l'enveloppe d'une famille de courbes, mais pas
"l'enveloppe principale". Et ici on n'a pas de courbes. Tu veux
l'enveloppe de tous les segments [(x_i,f(x_i)),(x_j,f(x_j))] ?
La phrase "graphiquement on peut se représenter f(x_i) comme une série
d'enveloppes raccordées entre elles par des segments disjoints" me
laisse perplexe.

https://fr.mathworks.com/help/signal/ref/findpeaks.html

D'accord. Rien à voir avec la notion mathématique d'enveloppe :)
Tu cherchais les maxima locaux sur un segment. Pas trop difficile à
programmer.

[Olivier Miakinen]

Post by Julien Arlandis
Soit une fonction discrète f(x_i) définie sur un intervalle de points
régulièrement espacés entre [0;1] et qui prend ses valeurs dans [0;1].

Du coup, tu as n+1 points de la forme (i/n, f(i/n)) où i ∈ ⟦0,n⟧ ?

[Julien Arlandis]

Post by Olivier Miakinen

Post by Julien Arlandis
Soit une fonction discrète f(x_i) définie sur un intervalle de points
régulièrement espacés entre [0;1] et qui prend ses valeurs dans [0;1].

Du coup, tu as n+1 points de la forme (i/n, f(i/n)) où i ∈ ⟦0,n⟧ ?

Oui c'est ça.

[Michel Talon]

Post by Julien Arlandis

Post by Olivier Miakinen

Post by Julien Arlandis
Soit une fonction discrète f(x_i) définie sur un intervalle de points
régulièrement espacés entre [0;1] et qui prend ses valeurs dans [0;1].

Du coup, tu as n+1 points de la forme (i/n, f(i/n)) où i ∈ ⟦0,n⟧ ?

Oui c'est ça.

Il s'agit d'un problème d'enveloppe convexe. L'algorithme naif est
d'ordre O(N^2)
mais il existe des algorithmes d'ordre O(N log(N)). Ce qui suit en est
un, particulièrement simple, tiré de l'algo python de même nom dans
https://www.geeksforgeeks.org/convex-hull-in-python, qui contient tous
les algos classiques.
J'en ai fait une version dans le langage maxima, en tenant compte des
simplifications autorisées par le problème en question.

Comme les autres algos on utilise le produit vectoriel vp(p1,p2,p)
pour savoir si p est au dessus ou au dessous de la ligne p1p2 et avoir
sa distance à
la ligne. On choisit le point au dessus de la ligne à la plus grande
distance. Ensuite
on applique récursivement ceci comme dans l'algorithme quicksort. A la fin
on trie les points extrémaux et on retire les doublons. J'ai testé
l'algo un bon nombre de fois, N=1000 donne encore une réponse rapide.
N=10000 prend
quelques secondes.

hull:[]$

vp(p1,p2,p) := block([val],
val: (p[2] - p1[2]) * (p2[1] - p1[1]) - (p2[2] - p1[2]) * (p[1] - p1[1]),
[sign(val),abs(val)])$

quickhull(a,n1,n2) := block([index:-1,max_dist:0,temp],
for i from n1+1 thru n2-1 do (
temp:vp(a[n1],a[n2],a[i]),
if ( temp[1] = pos and temp[2] > max_dist ) then (index:i,
max_dist:temp[2])),
if (index = -1) then (
hull:append([n1,n2],hull),return),
else (quickhull(a,n1,index), quickhull(a,index,n2)))$

printhull(a) := block([N:length(a)],
quickhull(a,1,N),
hull:listify(setify(hull)),
map(lambda([n],a[n]),hull))$

/* Test du programme */

N:10$
a:[]$
for i from 0 thru N do a:endcons([float(i/N),random(1.0)],a)$
b:printhull(a);
plot2d([[discrete,a],[discrete,b]]);