Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: efji <efji@efi.efji>
Newsgroups: fr.sci.maths
Subject: =?UTF-8?Q?Re=3A_Alg=C3=A8bre_lin=C3=A9aire_et_string_art?=
Date: Wed, 22 Jan 2025 21:56:33 +0100
Organization: A noiseless patient Spider
Lines: 113
Message-ID: <vmrm21$16rf0$1@dont-email.me>
References: <A9bEoEV28vfRo7310cGKP1UxNmk@jntp> <vml6k9$31l7r$1@dont-email.me>
 <UkIBPlw1ZkO4EbuSELmygF1mdk8@jntp>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Wed, 22 Jan 2025 21:56:34 +0100 (CET)
Injection-Info: dont-email.me; posting-host="75e501f54246c9105ea8086895371b9a";
	logging-data="1273312"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/zetzFHFDsrLZSvEiblNBN"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:q67lV3gh4LBfKquUfvwe2zNwwwQ=
In-Reply-To: <UkIBPlw1ZkO4EbuSELmygF1mdk8@jntp>
Content-Language: fr, en-US
Bytes: 6517

Le 22/01/2025 à 21:32, Julien Arlandis a écrit :
> 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

Ah mince, très mauvaise image. Tu n'avais pas de photo du docteur Hachel?

> 
> Méthode radon, 18000 segments :
> https://ibb.co/NtMbJn9
> 
> Méthode itérative, 4000 segments :
> https://ibb.co/phyC2Yw
> 

Intéressant. Le rendu est vraiment très différent. Clairement Radon est 
plus "proche" de l'image de départ, mais l'autre méthode donne un rendu 
plus agréable je trouve. En particulier il n'y a pas cette singularité 
au centre ni la concentration sur les bords.

-- 
F.J.