Tu as ton plan de départ A qui contient des pixels et ton plan d'arrivée B qui contient des pixels, pour décrire la transformation j'introduis des plans A' et B' dont les points ont des vraies coordonnées en nombre réels, et je suis le chemin: A → A' → B' → B.
A → A'
Tu regardes chaque point de ton image (point de A) comme un point de A' avec des coordonnées entières, et marqué d'une couleur, cela te fait un ensemble P de points.
A' → B'
Avec «ta triche» tu sais présenter ta courbe comme y = f(x), tu passes de A' à B' en envoyant le point (ξ,η) sur le point (ξ,η+f(ξ)), sans toucher à sa couleur. Cela te fait un ensemble Q de points colorés, qui est dans B' mais dont les coordonnées ne sont pas de nombres entiers (à cause du terme f(ξ)).
B' → B
Pour pousser B' sur B on regarde chaque point β de B (B est en mode pixel) et on se pose la question «de quelle couleur faut il le colorier?» Pour cela tu peux choisir plusieurs méthodes.
La plus simple consistant à choisir la couleur du point de Q qui est le plus proche de β — sauf si β est assez loin de Q, auquel cas il reste sans couleur.
Une autre méthode consiste à faire une «moyenne» des couleurs des points les plus proches de β. Par exemple, tu peux prendre tous les points situés à distance au plus d de β et leur affecter un coefficient de type 1/(1 + (distance à β)2) qui donne un plus fort poids au points proches de β. À la fin β est colorié par la moyenne des couleurs de ses voisins, pondérée par nos coefficients.
Ce que veux dire moyenne pour les couleurs n'est pas tout à fait clair, mais je pense que si tu fais la moyenne des coordonnées RGB ou CMYK, tu obtiens un résultat raisonnable.
Conclusions
La partie la plus dure est probablement B' → B, et si tu représentes Q par une liste, cela peut commencer à durer un petit peu longtemps de chercher les points proches de β pour chaque β! Par exemple si to image de base fait w par h et ton image d'arrivée W par H, la méthode naïve te donne whWH calculs de distance et un petit nombre de moyennes à calculer. Pour gagner un peu de temps tu peux utiliser un strucure récurrente de type
bout_de_plan (x0, y0, x1, y1):
niveau: nombre entier
case: liste de points
a: bout_de_plan (une moitié de (x0, y0, x1, y1))
b: bout_de_plan (l'autre moitié de (x0, y0, x1, y1))
L'insertion d'un point β se fait:
— dans la case si le niveau est plus grand qu'un seuil fixé (la profondeur de ta structure)
— dans la case si le disque de centre β de rayon d n'est pas contenu entièrement dans a ou dans b.
— dans le bout de pan a si le disque de centre β de rayon d est contenu entièrement dans a
— dans le bout de pan b si le disque de centre β de rayon d est contenu entièrement dans b
La recherche d'un point β se fait comme l'insertion, on regarde où on doit ranger β pour voir s'il y est déjà ou point.
La recherche des points à distance au plus d de β se fait dans la case contenant β, c'est ici qu'on gagne du temps.
Pour construire la structure tu pars d'un bout de plan qui correspond soit à ton A' soit à ton B' puis tu le coupes en 2 dans le sens de la hauteur pour obtenir a et b, chacun est ensuite coupé en 2 dans le sens de la largeur pour obtenir 4 autres bout de plan et ainsi de suite. Si tu choisis une profondeur N cela coupe le plan en 2N+1 cases pour des images une profondeur entre 8 et 12 devrait suffire.
[^] # Re: Algo
Posté par Michaël (site web personnel) . En réponse au message Projeter une image le long d'un chemin. Évalué à 3. Dernière modification le 20 mai 2012 à 12:12.
Voilà ce que je te propose:
Tu as ton plan de départ A qui contient des pixels et ton plan d'arrivée B qui contient des pixels, pour décrire la transformation j'introduis des plans A' et B' dont les points ont des vraies coordonnées en nombre réels, et je suis le chemin: A → A' → B' → B.
A → A'
Tu regardes chaque point de ton image (point de A) comme un point de A' avec des coordonnées entières, et marqué d'une couleur, cela te fait un ensemble P de points.
A' → B'
Avec «ta triche» tu sais présenter ta courbe comme y = f(x), tu passes de A' à B' en envoyant le point (ξ,η) sur le point (ξ,η+f(ξ)), sans toucher à sa couleur. Cela te fait un ensemble Q de points colorés, qui est dans B' mais dont les coordonnées ne sont pas de nombres entiers (à cause du terme f(ξ)).
B' → B
Pour pousser B' sur B on regarde chaque point β de B (B est en mode pixel) et on se pose la question «de quelle couleur faut il le colorier?» Pour cela tu peux choisir plusieurs méthodes.
La plus simple consistant à choisir la couleur du point de Q qui est le plus proche de β — sauf si β est assez loin de Q, auquel cas il reste sans couleur.
Une autre méthode consiste à faire une «moyenne» des couleurs des points les plus proches de β. Par exemple, tu peux prendre tous les points situés à distance au plus d de β et leur affecter un coefficient de type 1/(1 + (distance à β)2) qui donne un plus fort poids au points proches de β. À la fin β est colorié par la moyenne des couleurs de ses voisins, pondérée par nos coefficients.
Ce que veux dire moyenne pour les couleurs n'est pas tout à fait clair, mais je pense que si tu fais la moyenne des coordonnées RGB ou CMYK, tu obtiens un résultat raisonnable.
Conclusions
La partie la plus dure est probablement B' → B, et si tu représentes Q par une liste, cela peut commencer à durer un petit peu longtemps de chercher les points proches de β pour chaque β! Par exemple si to image de base fait w par h et ton image d'arrivée W par H, la méthode naïve te donne whWH calculs de distance et un petit nombre de moyennes à calculer. Pour gagner un peu de temps tu peux utiliser un strucure récurrente de type
bout_de_plan (x0, y0, x1, y1):
niveau: nombre entier
case: liste de points
a: bout_de_plan (une moitié de (x0, y0, x1, y1))
b: bout_de_plan (l'autre moitié de (x0, y0, x1, y1))
L'insertion d'un point β se fait:
— dans la case si le niveau est plus grand qu'un seuil fixé (la profondeur de ta structure)
— dans la case si le disque de centre β de rayon d n'est pas contenu entièrement dans a ou dans b.
— dans le bout de pan a si le disque de centre β de rayon d est contenu entièrement dans a
— dans le bout de pan b si le disque de centre β de rayon d est contenu entièrement dans b
La recherche d'un point β se fait comme l'insertion, on regarde où on doit ranger β pour voir s'il y est déjà ou point.
La recherche des points à distance au plus d de β se fait dans la case contenant β, c'est ici qu'on gagne du temps.
Pour construire la structure tu pars d'un bout de plan qui correspond soit à ton A' soit à ton B' puis tu le coupes en 2 dans le sens de la hauteur pour obtenir a et b, chacun est ensuite coupé en 2 dans le sens de la largeur pour obtenir 4 autres bout de plan et ainsi de suite. Si tu choisis une profondeur N cela coupe le plan en 2N+1 cases pour des images une profondeur entre 8 et 12 devrait suffire.
Bon courage! :)