Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #1 - 24-04-2012 19:57:37

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

des cercles décenttalisés: analyse vs algèbre

Aujourd'hui coloriage! smile

Prenons une feuille, choisissons un centre et affectons à chaque points une couleur dont l'intensité augmente proportionnellement à r² : On observera un dégradé radiale.

Maintenant, si la couleur revient à une intensité de 0 chaque fois qu'elle dépasse un certain seuil: l'intensité du point est donné par r² modulo (Rmax+1), qu'observera-t-on?

I) Un point de vu analytique:
    On observera des bandes circulaires dégradés. La largeur des bandes sera de plus en plus fine à mesure qu'on s'éloigne du centre (car r² a une dérivés croissante égale à 2r)

II) Un point de vu algébrique:
   Prenons des points de coordonnées entières (des pixels) et une intensité variant de 0 à 255:

for (x=0;x<largeur;x++)
for (y=0;y<hauteur;y++)
      couleur[x][y] = (x*x+y*y) % 256;

Observera-t-on toujours la même chose?
Réfléchissez bien avant de révéler l'image lol
Spoiler : [Afficher le message] http://www.prise2tete.fr/upload/w9Lyl6n-motif_cercle_bleu.PNG

On observe un motif périodique carré de 128 pixels de coté. Le motif analytique décrit précédemment se retrouve au niveau de chaque disque noir, chacun d'eux pourrait être le centre sans que le motif soit changé.
On observe également de multiples motifs secondaires similaires, mais striés, et de largeurs variables. 
 


L'énigme : expliquez ce que l'on observe big_smile

Oui, c'est faisable. Pendant longtemps je n'avais pas cherché à comprendre, mais en m'y plongeant sérieusement il s'avère que le problème est beaucoup plus simple qu'il n'y parait, l'algèbre de base avec les modulos suffit.

Bonne, réflexion wink

  • |
  • Répondre

#0 Pub

 #2 - 24-04-2012 20:31:06

Franky1103
Elite de Prise2Tete
Enigmes résolues : 49
Messages : 3222
Lieu: Luxembourg

Des cercles déceentralisés: analyse vs algèbre

Bonjour,
Ne serait-ce pas dû à un phénomène dinterférences similaires aux "franges de Fresnel" que l'on a tous expérimentées au lycée (superposition de deux courbes sinusoïdes) ?
Bonne soirée.

 #3 - 24-04-2012 20:50:40

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

des cerclrs décentralisés: analyse vs algèbre

Franky : Je concède que ce motif fait penser à des interférences, mais je ne crois pas qu'il y ait d'interprétation du problème qui les fasses intervenir.
   Il faut bien comprendre que le motif nait de l'imperfection de l'image quand les bandes de couleurs deviennent moins large qu'un pixel. Au contraire, quand on étudie des interférences la résolutions sur l'écran est théoriquement infinie.

 #4 - 24-04-2012 23:53:20

irmo322
Professionnel de Prise2Tete
Enigmes résolues : 36
Messages : 203

des cercles décentralisés: analyse vs alhèbre

C'est trop fort! J'aime bien tes énigmes sur les dessins faits par ordi.

L'image est surprenante.

Après réflexion, la périodicité n'est pas un mystère.
Par contre, l'apparition des formes secondaires en cercles et pentagonales me laissent perplexe...
J'attends de voir la suite.

 #5 - 25-04-2012 18:46:07

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Des cercles déecntralisés: analyse vs algèbre

Je trouve l'énigme très intéressante néanmois moi pas comprends toi dans cette phrase :

On observera des bandes circulaires dégradés. La largeur des bandes sera de plus en plus fine à mesure qu'on s'éloigne du centre (car r² a une dérivés croissante égale à 2r)

yikes

Shadock smile


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #6 - 29-04-2012 01:48:34

Cédric-29
Habitué de Prise2Tete
Enigmes résolues : 16
Messages : 17

des cercleq décentralisés: analyse vs algèbre

Rien ne sert d'opposer point de vue analytique et algébrique. Il manque juste les contraintes d'affichage (sous échantillonnage) dans les explications du point de vue analytique.

On observe un effet de repliement de spectre assez courant (pour peu que l'on fasse un peu de traitement du signal/image). Il manque un filtrage d'anti-repliement (anti-aliasing) qui aurait masqué cette périodisation de l'image.

Une démonstration de cet effet en une dimension est plus simple.

On dispose d'une fonction continue [latex]f\(t\)=t^2[/latex] sur laquelle on applique un modulo, ce qui se traduit par :
[TeX]f_m\(t\)=t^2-E\(\frac{t^2}{D}\)D[/TeX]
En considérant un pas d'échantillonnage de 1, la fonction échantillonnée devient :
[TeX]f_m\(p\)=p^2-E\(\frac{p^2}{D}\)D[/TeX]
avec p entier relatif.

On montre facilement, en supposant D entier, que [latex]f_m\(p\)=f_m(p[/latex]+ [latex]D) [/latex] et donc que la fonction est périodique et de période D.

(J'ai un problème avec les + qui ne s'affichent pas sous Latex, vous aussi ?)

 #7 - 30-04-2012 11:05:37

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

Des cercles décentralisés: analyse vs algèèbre

Cédric : J'ai donné dans le cadre l'algo exacte qui génère l'image, l'information sur la fréquence d’échantillonnage est dedans. D'autre part, comme tu as pu le comprendre, appliquer un anti-crénelage à l'image n'est pas le sujet de l'énigme. Maintenant que tu as mis à jours la périodicité, saurais tu expliquer l'apparition des motifs secondaires?

 #8 - 02-05-2012 00:28:40

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

Des cercles décentralisés: analyse vs agèbre

Bon, il n'y a pas eu beaucoup de personnes inspirées par cette énigme.
Ça doit être les mots algèbre et analyse dans le titre qui font fuir les gens smile

   Je parts du principe que le point de vu analytique (qui correspond à une résolution  infinie) a été compris.
Maintenant intéressons nous spécifiquement à l'image pixelisée.

I) La périodicité


   La périodicité de 128 pixels peut paraitre surprenante quand on la découvre, mais elle saute aux yeux dans la formulation mathématique:
(i+128xk)²+(j+128xl)² modulo 256
= i²+j²+256ki + 128²k² + 256lj+ 128²l² modulo 256
= i²+j² modulo 256

   Cette périodicité explique la répétition du motif principale. Ce motif est fidèle à la description analytique tant que la largeur des anneaux est plus large qu'un pixels, ensuite les anneaux deviennent invisible et des motifs secondaires apparaissent.

II) les motifs secondaires


   Premièrement remarquons que les motifs secondaires sont similaire au principal mais sont plus striés et ont l'air rétrécis.

Rappelons que a = b modulo (kxl)     implique a = b modulo k

   Posons c = i²+j², alors la couleur du point i j est congrue à c à toutes les puissance de 2 inférieur à 256:
i²+j² = c modulo 128 ; i²+j² = c modulo 64 ; .... i²+j² = c modulo 4;i²+j² = c modulo 2;
   Prendre un nombre binaire modulo une puissance de 2 revient à sélectionner ses bits de poids faibles.
Cela démontre que le motif principal est recopié pour les bits de poids faibles avec une périodicité doublant de 2 à 64 pixels.
   Bien sûr, les bits de poids fort s'ajoute par dessus les motifs et les décalent. Suivant chaque valeur des bits fort on verra une image entrelacée différente. Le nombre d'images entrelacées double chaque fois que la périodicité double: pour 64 pixels il y a 2 images entrelacés différentes, pour 32 pixels 4 images...
  Notons également que les bits de poids fort quand ils sont tous à 1 sont responsable de la largeur du motifs secondaire: en décalant vers le claire le disque centrale, le premier saut de couleur se produit plus tôt et le disque est moins large.

  La manière dont les motifs secondaires sont entrelacés est facilement démontrable pour n=64 pixels:
(i + 64k)² + (j + 64l)² modulo 256
= i² + j² + 128k*i + 128l*j modulo 256
Suivant que k et l valent 0 ou 1, il y aura un saut de couleur verticalement ou horizontalement ou les deux si k=l=1 ou pas de saut si k=l=0.


   Le type de raisonnement que j'ai fait ici se généralisent facilement à tout type de polynôme en i,j. Si le degré du polynôme est égale à 2 le motif principale sera une conique (ellipse, hyperbole ou parabole):

Exemples pour:
1) i*i-10*j                  2) i*j
3) i*i+5*j*j-i*j           4) i*j+j*j+10*i
http://www.prise2tete.fr/upload/w9Lyl6n-periode_256.PNG

 #9 - 03-05-2012 22:39:02

Cédric-29
Habitué de Prise2Tete
Enigmes résolues : 16
Messages : 17

DDes cercles décentralisés: analyse vs algèbre

Merci pour la réponse détaillée, je regrette de ne pas y avoir passé plus de temps.

 #10 - 03-05-2012 22:58:12

SHTF47
Imprnnçbl de Prs2Tt
Enigmes résolues : 39
Messages : 1629
Lieu: Autre nom du colin

Des cercles déecntralisés: analyse vs algèbre

struc de ouf ! yikes


La musique est une mathématique sonore, la mathématique une musique silencieuse. [Edouard HERRIOT]

 #11 - 03-05-2012 23:22:19

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

des cercles décentramisés: analyse vs algèbre

A bah ça va c'était pas très difficile en fait, en revanche malgré çà je n'ai toujours pas compris : On observera des bandes circulaires dégradés. La largeur des bandes sera de plus en plus fine à mesure qu'on s'éloigne du centre (car r² a une dérivés croissante égale à 2r)

Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline

 #12 - 03-05-2012 23:55:04

w9Lyl6n
Professionnel de Prise2Tete
Enigmes résolues : 26
Messages : 220

Des cercles décentraisés: analyse vs algèbre

Analyse mieux détaillée à la demande de shadock wink

  Si on suit une ligne partant du centre de l'image, on peut définir la fonction :
f(r) = r² modulo Rmax
   Cette fonction donne les couleurs le long de la ligne (ou du rayon) pour un point à la distance "r" du centre.
   Cette fonction est dérivable par morceaux (là où elle n'est pas discontinue à cause du modulo). Sur chaque morceaux le modulo retire une constante: -k*Rmax.
   La dérivé de cette fonction est donc tout simplement f'(r) = 2r + 0

   Cela montre que sur chaque bande (j'appelle bande un intervalle où la fonction est continue, ce qui correspond à une bande circulaire dégradé sur l'image), plus la bande est éloigné du centre (plus r est grand) plus f' augmente, donc plus la couleur s’éclaircira vite et atteindra vite la limite Rmax.

Conclusion : les bandes sont de plus en plus minces en s'éloignant du centre.

 #13 - 04-05-2012 18:58:48

shadock
Elite de Prise2Tete
Enigmes résolues : 39
Messages : 3334

Des cercles décentralissé: analyse vs algèbre

OK merci big_smile

Shadock


"L'expérience est une lanterne qui n'éclaire que celui qui la porte." L-F. Céline
 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete