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 :

Re: 25/3

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

Oui, les programmes d'Anthony sont tres bien!

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

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 10:02 am

-TM6 Je ne sais pas comment va réagir réellement une image à ce traitement pas je peux essayer de prendre un vecteur aléatoire et regarder succéssivement les erreurs relatives lors d'une compression puis décompression :
Reprenons les vecteur t = [154,155,149,152,155,154,153,149,157,156,152,151,152,153,153,150] de la boite d'execution 15 :
notons c = la valeur max que l'on rammène à 0 :
c = 0.51 on avait pour erreur [-0.8125,0.1875,-0.3125,-0.3125,0.4375,-0.5625,-0.0625,-0.0625,0.6875,-0.3125,0.6875,-0.3125,0.1875,1.1875,-0.3125,-0.3125]
c= 0.5 erreur = [-0.3125,-0.3125,-0.3125,-0.3125,-0.0625,-0.0625,-0.0625,-0.0625,0.1875,0.1875,0.1875,0.1875,0.1875,0.1875,0.1875,0.1875]
c = 1 erreur = [-0.8125,0.1875,-0.3125,-0.3125,0.4375,-0.5625,-0.0625,-0.0625,0.6875,-0.3125,0.6875,-0.3125,0.1875,1.1875,-0.3125,-0.3125]
c= 2 erreur = [-0.8125,0.1875,-1.8125,1.1875,2.1875,1.1875,-1.8125,-1.8125,1.6875,0.6875,1.6875,0.6875,-0.8125,0.1875,0.1875,-2.8125]

Les erreurs restent faible, d'autant plus que l'on va certainement prendre des valeurs entières pour coder les couleurs, si l'on rammène à l'entier le plus proche on retombe très souvent sur la même couleur même pour c=1. Et si c'est un autre couleur il y a au plus une différence égale à 3 ce qui reste faible pour une difference de couleur.

Anthony

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

Re: 25/3

Message par parisse » mer. mars 25, 2020 10:11 am

Bon, TM6 est une question difficile, surtout en option C.
Voila ma réponse:
Comme on fait des sommes, une estimation sur les erreurs relatives est sans doute très difficile à obtenir, travailler sur des erreurs absolues est plus pertinent. Si le vecteur à l'arrivée a toutes ses composantes avec une erreur absolue majorée par epsilon, alors l'erreur absolue sur invd2_tot sera de epsilon*(1+log2(n)) car il y a log2(n) étapes, et à chaque étape on additionne une quantité obtenue précédamment avec une quantité donnée dont l'erreur absolue est de epsilon au plus.
Vérification avec l'arithmétique d'intervalle
l16:=seq([-0.5..0.5],16)
ceci crée une liste de 16 intervalles de longueur 1 (un intervalle représente n'importe quel réel compris entre ses bornes, ici -0.5 et 0.5)
invd2_tot(l16);
l16:=seq([-0.5..0.5],32);
invd2_tot(l32);

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

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 10:12 am

Comme il est 11h je vais passer aux questions de Bernard Parisse.

- BP1 Je me suis trompé au début, j'ai changé la matrice Aortho sur le programme mais j'ai oublié de la changer sur mes notes. La bonne matrice est la matrice Aortho du programme. En effet elle fait bien la somme de deux coordonnées succéssives et la place au bon endroit dans notre nouveau vecteur.

- BP2 La méthode du texte n'exploite pas du tout le fait que la photo soit un objet en 2D. Pour adapter il faudrait choisir une suite de pixels cohérente qui couvre toute la photo donc soit que des lignes, soit que des colonnes soit que des diagonales. On pourrait tester entre les trois quel suite permet d'avoir le plus de fois des suites consécutives de couleurs proche et prendre la liste de pixels correspondante.


Anthony

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

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 10:18 am

-BP3 Je ne sais pas cexactement comment fonctionne les méthodes par transformation de Fourier donc il m'est difficile de fournir une réponse cohérente à cette question. Je pense que cela pourrait venir du fait que la méthode pas transformation de Fourier ne prend pas en compte le fait qu'on ait une succession de couleurs proches et qu'ici c'est ce qui fait l'éfficacité de notre compression.

Anthony

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

Re: 25/3

Message par parisse » mer. mars 25, 2020 10:20 am

Pour conclure sur TM6:
Dans la modélisation du texte, on s'attend à avoir n de l'ordre de 2^20, donc log2(n)+1 vaut un peu plus que 20, si epsilon vaut 0.5, ca fait une erreur possible allant jusqu'à 10, ce que l'on peut commencer à trouver genant pour un entier entre 0 et 255. Mais l'estimation d'erreur est valable dans le cas le pire, en pratique on s'attend plutot à une erreur moyenne en epsilon*sqrt(log2(n)) (somme d'erreurs indépendantes), donc une erreur de 1% environ.

Sur TM7: L'estimation d'erreur absolue reste vraie si on arrondit au lieu de tronquer. L'intéret d'arrondir les détails c'est qu'au lieu de stocker et travailler avec des nombres flottants (4 ou 8 octets), on peut travailler avec des entiers entre 0 et 255 (1 octet).

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

Re: 25/3

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

etuagreg a écrit :
mer. mars 25, 2020 10:18 am
-BP3 Je ne sais pas cexactement comment fonctionne les méthodes par transformation de Fourier donc il m'est difficile de fournir une réponse cohérente à cette question. Je pense que cela pourrait venir du fait que la méthode pas transformation de Fourier ne prend pas en compte le fait qu'on ait une succession de couleurs proches et qu'ici c'est ce qui fait l'éfficacité de notre compression.

Anthony
Ma question était plutot de comparer le cout des algorithmes.
Sinon, pour la compression à base de FFT, on peut utiliser la meme technique que pour D2, on ramène à 0 tous les coefficients de la FFT qui sont de module plus petits qu'un epsilon donné, ce qui permet de stocker des paires numero de coefficient de Fourier, valeur complexe de la FFT (pour les coefficients non tronqués à 0), au lieu de stocker tous les coefficients du vecteur de base ou de la FFT. Ca marche plutot bien pour le son (on voit apparaitre des coefficients non nuls pour la fréquence du son et ses harmoniques).

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

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 10:26 am

- BP 4 On part toujours d'une liste d'entiers en effet compris entre 0 et 255. C'est le programme d'inversion qui devrait faire le boulot de ramener à des entiers (ce que je n'ai pas fait dans mon programme par oubli). Il n'est pas important de travailler avec des rationnels car les rationnels stockés ne représentent pas directement la photo, ils servent juste à stocker efficacement (bien que stocker des rationnels est certainement plus couteux que de stocker des entiers mais je pense que sur un grand vecteur il est quand même bien plus efficace de stocker ces rationnels surtout que les plus petits d'entre eux seront ramenés à 0) Par contre à la fin lors de notre retour à la photo par la fonction invd2_tot j'aurais du arrondir à l'entier le plus proche. En effet la photo va bien être composée de couleurs à valeurs entières ce qui légitime d'autant plus le fait de pouvoir faire des erreurs comme je l'ai expliqué pour la question de Thomas car on va certainement pouvoir revenir à une valeur de couleur égale ou au moins proche de ce que l'on avait.


Anthony

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

Re: 25/3

Message par parisse » mer. mars 25, 2020 10:30 am

BP4: Pensez-vous qu'on puisse travailler avec des nombres flottants, comme le suggère le texte? Est-ce que le résultat de d2 sera approché ou exact? Est-ce que les opérations arithmétiques de base sont en O(1)?

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

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 10:32 am

parisse a écrit :
mer. mars 25, 2020 10:25 am

Ma question était plutot de comparer le cout des algorithmes.
Sinon, pour la compression à base de FFT, on peut utiliser la meme technique que pour D2, on ramène à 0 tous les coefficients de la FFT qui sont de module plus petits qu'un epsilon donné, ce qui permet de stocker des paires numero de coefficient de Fourier, valeur complexe de la FFT (pour les coefficients non tronqués à 0), au lieu de stocker tous les coefficients du vecteur de base ou de la FFT. Ca marche plutot bien pour le son (on voit apparaitre des coefficients non nuls pour la fréquence du son et ses harmoniques).
Je sais seulement que la complexité de la FFT est en O(n) où n= longueur du vecteur. Donc en théorie la FFT serait plus rapide que mon programme qui est en O(n*log(n)).

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

Re: 25/3

Message par parisse » mer. mars 25, 2020 10:34 am

etuagreg a écrit :
mer. mars 25, 2020 10:32 am

Je sais seulement que la complexité de la FFT est en O(n) où n= longueur du vecteur. Donc en théorie la FFT serait plus rapide que mon programme qui est en O(n*log(n)).
Attention, la complexité de la FFT est en O(n*log2(n)), pas en O(n).

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

Re: 25/3

Message par etuagreg » mer. mars 25, 2020 10:40 am

Pour finir sur BP4, il est vrai que prendre des decimaux peut augmenter le coût de stockage et de calcul mais les nombres restent des rationnels. Dans notre cas on voit par contre que même pour un vecteur petit la transformation d2_tot fait apparaitre un numérateur de taille log_2(n) ce qui peut être contraignant si l'on s'intéresse à des liste trop longues. Cela aurait pour effet d'augmenter le coût de stockage mais celui ci serait compenser par l'efficacité de la méthode en terme de stockage. Par contre en terme de coût de calcul cela peut avoir une grande incidence sur le temps de calcul pour les grand vecteurs. Mais d'un autre coté on divise par des puissance de 2 à chaque fois ce qui reste relativement facile à manipuler.


Anthony

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

Re: 25/3

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

BP5 Le sqrt(2) ferait passer les calculs en flottant ce que l'on préfère éviter pour des raisons de complexité de calcul et de stockage. Mais peut-être serait il possible de manipuler ce sqrt(2) de manière symbolique sans l'expliciter ce qui éviterait de manipuler des flottants. Dans ce cas on exprimerait le sqrt(2) seulement lors de la transformation inverse pour revenir à des entiers. Mais je pense qu'il est quand même moins couteux de ne pas manipuler ce sqrt(2) quitte à avoir de 1/2 à la place qui apparaissent, comme on le voit bien dans le calcul de Aortho multiplié par sa transposée.

Anthony

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

Re: 25/3

Message par parisse » mer. mars 25, 2020 10:48 am

etuagreg a écrit :
mer. mars 25, 2020 10:40 am
Pour finir sur BP4, il est vrai que prendre des decimaux peut augmenter le coût de stockage et de calcul mais les nombres restent des rationnels.
En fait je pensais plutot à des flottants (en base 2) qu'à des décimaux (en base 10, peu utilisés sur machine).
Ce qui est amusant, c'est qu'ici on peut travailler avec des flottants tout en faisant du calcul exact (dans la limite de non dépassement de la mantisse)! En effet les calculs se font avec des rationnels dont le dénominateur est une puissance de 2, qui sont représentables exactement par des flottants. Avec des flottants, toutes les opérations arithmétiques de base sont en O(1). Le cout de stockage est proportionnel (en pratique dans Xcas ce sera la meme taille, 8 octets, dans un programme compile il faudra 8 fois plus de place pour des flottants)
Mais d'un autre coté on divise par des puissance de 2 à chaque fois ce qui reste relativement facile à manipuler.
Oui, absolument, en fait le dénominateur est une puissance de 2 plus petite que log2(n) donc ici pas plus que 30, tous les calculs sur les rationnels peuvent donc etre faits en temps O(1). Mais la constante dans le O(1) est significativement plus grande qu'en travaillant avec des flottants.

Donc le mieux à mon avis, c'est de faire tous les calculs avec des flottants, et d'arrondir à des entiers entre 0 et 255 et compresser les 0 pour avoir un stockage optimal en taille.

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

Re: 25/3

Message par parisse » mer. mars 25, 2020 10:51 am

etuagreg a écrit :
mer. mars 25, 2020 10:46 am
BP5 Le sqrt(2) ferait passer les calculs en flottant ce que l'on préfère éviter pour des raisons de complexité de calcul et de stockage.
Pas pour des raisons de complexité, travailler avec des flottants est en O(1) (et il n'y a pas de grosse constante cachée dans le O(1)).
Mais peut-être serait il possible de manipuler ce sqrt(2) de manière symbolique sans l'expliciter ce qui éviterait de manipuler des flottants. Dans ce cas on exprimerait le sqrt(2) seulement lors de la transformation inverse pour revenir à des entiers. Mais je pense qu'il est quand même moins couteux de ne pas manipuler ce sqrt(2) quitte à avoir de 1/2 à la place qui apparaissent, comme on le voit bien dans le calcul de Aortho multiplié par sa transposée.

Anthony
Oui, absolument.
Si on veut travailler en exact, il faut représenter les nombres avec une extension algébrique de Q, donc représenter les nombres par des polynomes de degré 1. Le cout des opérations arithmétiques de base est toujours O(1), mais la constante dans le O(1) est significativement plus grande que si on travaille avec des flottants

Répondre