Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.gegeweb.eu!gegeweb.org!pasdenom.info!from-devjntp
Message-ID: <UkIBPlw1ZkO4EbuSELmygF1mdk8@jntp>
JNTP-Route: nemoweb.net
JNTP-DataType: Article
Subject: Re: =?UTF-8?Q?Alg=C3=A8bre=20lin=C3=A9aire=20et=20string=20art?=
References: <A9bEoEV28vfRo7310cGKP1UxNmk@jntp> <vml6k9$31l7r$1@dont-email.me>
Newsgroups: fr.sci.maths
JNTP-HashClient: 1A6XSw_y7iLu_ChBInOJvC1dp7k
JNTP-ThreadID: ljBVPA3TmpWugZf4HBidAU0WTvQ
JNTP-Uri: https://nemoweb.net/?DataID=UkIBPlw1ZkO4EbuSELmygF1mdk8@jntp
User-Agent: Nemo/1.0
JNTP-OriginServer: nemoweb.net
Date: Wed, 22 Jan 25 20:32:49 +0000
Organization: Nemoweb
JNTP-Browser: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36
Injection-Info: nemoweb.net; posting-host="7ac9f7d2cc9927fe35e096fd866299fdf9a6662b"; logging-data="2025-01-22T20:32:49Z/9183303"; posting-account="1@nemoweb.net"; mail-complaints-to="julien.arlandis@gmail.com"
JNTP-ProtocolVersion: 0.21.1
JNTP-Server: PhpNemoServer/0.94.5
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-JNTP-JsonNewsGateway: 0.96
From: Julien Arlandis <julien.arlandis@gmail.com>

Le 20/01/2025 à 10:56, efji a écrit :
> Amusant, je n'avais jamais entendu parler de ça.
> 
> Le 19/01/2025 à 12:00, Julien Arlandis a écrit :
>> Bonjour,
>> 
>> J'essaye de développer un algorithme rapide et efficace pour représenter 
>> des images en niveaux de gris par le string art. Il s'agit de relier un 
>> ensemble de points (généralement matérialisés par des clous plantés dans 
>> une planche) par un fil tendu jusqu'à s'approcher au plus près de 
>> l'image désirée. Pour la suite, on considèrera que les points sont 
>> régulièrement espacés sur un cercle de rayon R.
>> 
>> Intuitivement, on peut être tenté de modéliser le problème par un espace 
>> vectoriel constitué des N(N-1)/2 segments formés par chaque paire de 
>> points. Cette idée est plus rigoureusement exprimée dans cette vidéo :
>> 
>> <https://www.youtube.com/watch?v=WGccIFf6MF8>
> 
> La vidéo explique très bien tout ce qu'il faut savoir de l'approche 
> "directe", de type algèbre linéaire, et dit pourquoi ça ne marche pas 
> bien. Elle propose à la fin un algo qui marche raisonnablement, mais on 
> pense tout de suite au scanner médical et à la transformée de Radon.
> 
> https://www.youtube.com/watch?v=dBlSmg5T13M
> 
> Bingo! la seconde vidéo développe la méthode utilisant la transformée de 
> Radon de façon super claire. Problem solved. Je ne pense pas qu'on 
> puisse faire mieux.
> 
> Merci d'avoir indiqué cette chaine youtube qui contient plein de choses 
> intéressantes, mais hélas rien sur les nombres complexes pour les 
> débiles mentaux :)
> 
>> 
>> Sous cette approche, le problème se modélise par l'équation matricielle :
>> somme(a_i * x_i) = b
>> où a_i est le i ème vecteur (image matricielle du segment i)
>> x_i est le nombre de fils reliant le segment i
>> b l'image à atteindre.
>> Sachant que la famille de vecteurs a_i ne forment pas une famille 
>> génératrice complète, (il est facile à comprendre qu'une image 
>> constituée d'un cadre blanc périphérique ne pourra pas être générée sans 
>> assombrir la partie blanche), quelle est la limite et la pertinence de 
>> cette approche ?
> 
> Non, ce n'est pas la bonne approche pour deux raisons, bien expliquées 
> dans la video :
> 
> 1/ le passage d'un "fil" à une ligne de pixels ne doit pas se faire 
> naïvement car sinon on privilégie certaines directions. C'est le même 
> problème que l'aliasing en image. La vidéo propose une sorte de profil 
> élargi des fils permettant de traiter ce problème de façon heuristique 
> et "perceptive".
> 
> 2/ même si on néglige le point 1, le problème n'est pas linéaire car on 
> doit chercher des a_i dans {0,1} et pas dans \R. Résoudre de façon 
> classique, par moindres carrés, le problème linéaire surdéterminé que tu 
> indiques va donner des a_i réels quelconques, y compris des négatifs qui 
> n'ont pas de sens. Minimiser ||somme(a_i * x_i) - b||^2 avec la 
> contrainte a_i = 0 ou 1 est un problème appelé "bang-bang" très 
> difficile à résoudre, qui a plein de mauvaises propriétés (en 
> particulier il est non convexe).
> 
>> 
>> Pour ma part j'ai commencé à coder une méthode itérative qui consiste à 
>> partir d'un point arbitraire pour relier le point dont le segment 
>> s'approche au plus près de l'image à construire. Ce n'est pas assez 
> 
> Ca a peu de chances de marcher. On doit même pouvoir construire des 
> images pour lesquelles ça ne marche pas du tout. Et puis "le segment qui 
> s'approche au plus près" ne doit pas être simple à trouver, sauf à 
> tester tout exhaustivement. Ensuite il faut soustraire le segment choisi 
> de l'image et tout recommencer pour l'itération suivante. Un bel algo en 
> n^3 :)

Pour avoir intensivement comparé les deux méthodes depuis 3 jours, les 
deux méthodes présentent des avantages et des inconvénients qui les 
rendent difficiles à partager.
La méthode itérative permet d'atteindre une image visuellement 
reconnaissable beaucoup plus rapidement (en nombre de segments) qu'en 
passant par la transformée de Radon. L'image commence à se former à 
partir de 1000 segments avec la méthode itérative, avec Radon on 
commence à voir un résultat à partir de 10000 segments. Naturellement 
on obtient une résolution plus élevée avec cette méthode alors que le 
contraste se dégrade significativement avec l'approche itérative si on 
se rapproche du nombre de segments nécessaires pour un résultat 
acceptable avec Radon.

Pour mes tests je suis parti sur une résolution de 288 points répartis 
sur un cercle à partir du fichier suivant : 
https://ibb.co/x3qZ6wp

Méthode radon, 18000 segments :
https://ibb.co/NtMbJn9

Méthode itérative, 4000 segments :
https://ibb.co/phyC2Yw


-- 
Ce message a été posté avec Nemo : <https://nemoweb.net/?DataID=UkIBPlw1ZkO4EbuSELmygF1mdk8@jntp>