25/3

Forum pour les étudiants de la préparation agreg option C de Grenoble

Modérateur : xcasadmin

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

25/3

Message par parisse » mer. mars 18, 2020 11:32 am

Anthony s'est porté volontaire pour travailler sur un des textes suivants:
https://agreg.org/Textes/public2016-C2.pdf ou https://old.agreg.org/Textes/public2013-C1.pdf
Plus d'infos d'ici mercredi prochain.

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: 25/3

Message par etuagreg » mar. mars 24, 2020 9:03 am

Bonjour à tous,

Pour le texte, j'avais les quelques questions/remarques suivantes :
- pour l'introduction :
- TM1 en quoi les "variations de formes" ont-elles une incidence sur l'efficacité de la méthode ?
- TM2 peut-on légitimer le choix de la méthode de compression utilisée pour des photos ? est-ce qu'elle pourrait être utilisée pour des vecteurs aléatoires quelconques ?
- TM3 quelle est la différence de coût entre stocker n zéros brutalement, et en donnant juste le nombre de zéros stockés ?

- sur la transformation D2 :
- TM4 vérifier quelques complexités avec les algorithmes développés sur Xcas (prendre un grand vecteur aléatoire et lui appliquer l'algorithme de compression) ;
- TM5 vérifier avec le vecteur de l'énoncé que l'on retrouve bien le même chiffrement ;
- TM6 calculer l'erreur relative après suppression des détails à 0.51 ; et faire varier l'écart pour voir l'évolution de l'erreur sur l'image ;
- TM7 est-ce que l'on pourrait changer légèrement la méthode, et, au lieu de supprimer les petits détails, arrondir les détails (par exemple au demi-entier le plus proche) ; quel changements se font alors sur l'erreur et sur le coût en stockage de l'image compressée ?

- sur l'inversion de D2 :
- TM8 est-ce que l'on peut faire agir une matrice sur Ap pour la transformer en une matrice diagonale en blocs 2x2 ?
- TM9 cette transformation permet-elle de voir que (à un scalaire près) la matrice Ap est orthogonale ?
- TM10 quelle est la complexité pour retrouver l'image de départ à partir des matrices Ap,i et de l'image compressée ? (avec la formule juste avant la conclusion)
- TM11 comparer à la complexité en calculant un vecteur par ses projections sur une base orthonormée.

A demain pour parler de tout ça,
Thomas

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 25/3

Message par parisse » mar. mars 24, 2020 1:04 pm

J'ai édité le message de Thomas pour mettre des références aux questions qu'il pose, ce qui facilitera les réponses. Comme Thomas a déjà posé pas mal de questions, j'ajoute mes propres questions ci-dessous, si vous en avez d'autres, n'hésitez pas à les poser, sinon chacun peut réfléchir aux réponses à apporter.
Vous pouvez vous inscrire sur le forum si vous voulez une discussion plus facile à suivre (sinon il va y avoir des etuagreg qui ne sont pas tous de la meme personne). D'autre part, si la possibilité d'écrire des maths vous manque sur ce forum, on peut basculer ici http://www.les-mathematiques.net/phorum/list.php?68 pour les prochaines séances. J'espère qu'on pourra fonctionner avec le forum, je n'ai pas de connexion Internet fixe (et c'est peut-etre le cas d'autres ici), donc je privilégie un mode de fonctionnement qui nécessite peu de ressources reseau.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 25/3

Message par parisse » mar. mars 24, 2020 1:25 pm

Questions:
BP1/ La matrice renvoyée par Aortho n'est pas la meme que la matrice Ap des notes du II, laquelle est la bonne?
BP2/ La méthode du texte exploite-t-elle le fait qu'une photo est un objet en 2 dimensions? Pourrait-on l'adapter?
BP3/ Le résumé du texte dit que les transformations présentées sont souvent plus efficaces que les méthodes traditionnelles basées sur la transformée de Fourier. Pouvez-vous commenter?
BP4/ Le texte parle de stocker un pixel avec 3 octets, un par couleur, donc un entier entre 0 et 255 pour représenter l'intensité de chaque couleur. Mais ensuite, les exemples du texte utilisent des valeurs décimales et non des valeurs entières. Vous avez utilisé des rationnels dans vos illustrations.
Que pouvez-vous dire de l'impact du choix du type de données sur le cout du stockage en mémoire, sur le cout des opérations arithmétiques de base de la transformation D2 et sur le cout total de la transformation D2?
BP5/ Page 4 du texte on lit "mais les coefficients comportent alors d'inesthétiques sqrt(2)". Pourquoi une telle réserve?
BP6/ La suite du texte propose des méthodes permettant de mieux gérer des données dépendant linéairement (ou polynomialement) de leur position. On a envie de faire un parallèle avec des methodes numériques d'intégration. Quel serait les analogues des méthodes D2 et D4?

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 9:06 am

Du coup je vais commencer par répondre aux questions de Thomas:
-TM1 Selon moi les variations de forme et de couleurs sont très corélées. En fait on ne voit bien les variations de forme que si cela induit un variation de couleurs. Mais dans un sens on cherche à avoir le plus possible de pixels de couleurs proche qui se suivent. Si l'on prend les valeurs des pixels par lignes on voudrait idéalement qu'un ligne soit toujours de la même couleur. C'est en ce sens qu'on ne veut pas trop de variation de forme.

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 9:11 am

-TM2 On légitime justement cette methode par le fait que lorsqu'on a une photo il est peu probable que l'on alterne un pixel rouge puis bleu puis rouge puis bleu... On a souvent des pixels de couleur proche qui se suivent, du moins on a presque toujours une série de plusieurs pixels avec une couleur proche.
-TM3 Stocker n 0 les une à la suite te donne une complexité de stockage de n tandis que stocker n zéros en écrivant juste le nombre qu'ils sont cela revient à 1 bit près à stocker le nombre n en base 2. On passe donc d'une complexité de stockage en O(n) à une complexité en O(log_2(n))

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 25/3

Message par parisse » mer. mars 25, 2020 9:19 am

TM3: oui, on peut meme dire que stocker n occupera une taille fixe (disons 4 octets), on ne va pas travailler avec des données de taille supérieure à 4 giga-octets.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 25/3

Message par parisse » mer. mars 25, 2020 9:21 am

TM2: et pour un vecteur aléatoire?

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 9:24 am

-TM4 voici les résultats que j'ai obtenu :
test1=randvector(100000,255) ;test2=randvector(1000000,255) ;test3=randvector(10000000,255)
time(d2_tot(test1)) = [0.000124,0.0001091285]
time(d2_tot(test2)) = [0.00022,0.0001765578]
time(d2_tot(test3)) = [7.05e-05,8.464615e-05]

Les résulats ne semblent pas cohérents avec les calculs que j'ai fait.

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 25/3

Message par parisse » mer. mars 25, 2020 9:27 am

Il me semble que d2_tot devrait prendre une liste de longueur une puissance de 2, non?

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 9:30 am

- TM2 Pour un vecteur aléatoire cette méthode peut s'appliquer mais on ne pourrait pas arrondir les valeurs de différence à 0 car il est peu probable qu'elle soient assez petites pour être ammenées à 0 sans grosse pertes. En revanche on est sur que les valeurs de difference seront très certainement plus petites que les valeurs de depart (au moins en module) donc cela pourrait permettre de les stocker plus facilement. Cela permet quand même une légère compression.

Anthony ( j'ai oublié de signer mais c'est bien moi qui ai répondu aux questions de Thomas depuis ce matin)

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 9:34 am

-TM4 Oui en effet je recommence avec les bonnes tailles.
test1=randvector(2^10,255) ;test2=randvector(2^11,255) ;test3=randvector(2^12,255)
time(d2_tot(test1)) = [0.000125,0.0001020275]
time(d2_tot(test2)) = [0.000141,0.0001237881]
time(d2_tot(test3)) = [0.000126,0.0001215005]

Les résultats ne semblent toujours pas coller à la complexité que j'ai calculé. Peut-être que cela vient du fait que j'ai négligé les complexité de copy et concat alors qu'on ne devait pas.

Anthony

parisse
Messages : 5731
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: 25/3

Message par parisse » mer. mars 25, 2020 9:39 am

Oui, pour les vecteurs aléatoires.
De toutes facons, je pense qu'il va etre impossible de mettre en évidence la complexité optimale en O(n), parce que d2 fait des coies de listes, qui prennent en compte les n éléments de la liste de départ. On peut espérer un O(n*log2(n)) au mieux. Mais ce n'est pas grave, car il va est très difficile de distinguer expérimentalement entre O(n) et O(n*log2(n)) en prenant n=2^10, 2^11 et 2^12.
Je viens de tester de mon cote pour les timings, j'obtiens 0.005, 0.009 et 0.016, ce qui est plutot cohérent.

etuagreg
Messages : 24
Inscription : mar. mars 17, 2020 3:55 pm

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 9:46 am

-TM5
vect1=[123,122,124,124,128,129,134,137,140,142,145,147,153,155,156,155]
approx(d2_tot(vect1)) = [138.375,-10.75,-4.375,-5.625,-0.75,-3.5,-2.5,-0.75,0.5,0.0,-0.5,-1.5,-1.0,-1.0,-1.0,0.5]
l'énoncé nous donnait 138.375,−10.75,−4.375,−5.625,−0.75,−3.5,−2.5,−0.75,0.5,0,−0.5,−1.5,−1,−1,−1,0.5
On a bien la même transformation et si l'on essaye de revenir à l'échantillon de départ on trouve
invd2_tot((d2_tot(vect1))) = [123,122,124,124,128,129,134,137,140,142,145,147,153,155,156,155]
Le programme semble en accord avec les résultats de l'énoncé.

Anthony

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: 25/3

Message par megarbane » mer. mars 25, 2020 9:48 am

J'avais fait le test pour celui-là avec ton programme en fait.

Répondre