Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: 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: References: 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: 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 : >>> >>> >> >> 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.