{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1><center>  Rotation d'un quart de tour d'une image</center> </h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Une image est un tableau à 2 dimensions composé de *pixels*. Un *pixel* est, dans le codage **RGB**, un triplet d'entiers compris entre 0 et 255.  \n",
    "Les nombres correspondent à l'intensité respectives du rouge *red* , du vert *green* et du bleu *blue*.  \n",
    "Exemples :\n",
    "- un pixel de valeur `[0,0,0]` est noir\n",
    "- un pixel de valeur `[255,255,255]` est blanc\n",
    "- un pixel de valeur `[255,0,0]` est rouge\n",
    "- un pixel de valeur `[0,255,0]` est rouge\n",
    "- un pixel de valeur `[255,0,255]` est violet\n",
    "- un pixel de valeur `[0,0,155]` est bleu foncé"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Le module PIL\n",
    "\n",
    "Nous utiliserons le module `PIL` (Python Image Library) qui permet de gérer les images facilement. La partie qui nous interesse peut être importée par le code :\n",
    "`from PIL import Image`  \n",
    "\n",
    "* On ouvre une image à l'aide de `img = Image.open(nom_du_fichier)` le nom du fichier sera une chaîne de caractère et le fichier sera placé dans le même dossier que le notebook.\n",
    "\n",
    "* Les dimensions de l'image affectée à la variable `img` peuvent être récupérée par `img.size` (on récupère ainsi l'*attribut* `size` de l'objet Image). C'est un tuple.\n",
    "\n",
    "* La valeur du pixel d'abscisse $x$ et d'ordonnée $y$ peut être récupérée par  la méthode `getpixel(x,y)`  \n",
    "Dans l'exemple suivant `img.getpixel(2,15)` on récupère la valeur du pixel de coordonnées $(2,15)$\n",
    "\n",
    "On précise que la première coordonnée corespond à l'abscisse et la seconde à l'ordonnée, l'origine du repère étant en haut à gauche de l'image, les axes allant vers la droite et le bas.\n",
    "![Axes des images](https://i.stack.imgur.com/t4AiI.png)\n",
    "\n",
    "* On peut affecter le triplet `(r,g,b)` au pixel de coordonnées `(x,y)` à l'aide de :\n",
    "`img.putpixel((x,y),(r,g,b))`\n",
    "\n",
    "* L'image peut être sauvegardée à l'aide de la méthode `save` : `img.save(nom_du_fichier)`.   \n",
    "Par exemple : `img.save(\"ma_nouvelle_image.jpg\")`\n",
    "\n",
    "* Elle peut être affichée à l'aide de `img.show()`\n",
    "\n",
    "* Enfin, une nouvelle image (noire par défaut et qui sera modifiée par la suite) peut être créée à l'aide de `nouvelle_image = Image.new(\"RGB\", (largeur,hauteur))`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "# exemple\n",
    "from PIL import Image\n",
    "img_test=Image.open(\"image_test.png\")\n",
    "img_test.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>Utilisation des commandes de PIL</h2>\n",
    "<div class=\"alert alert-block alert-warning\">\n",
    "    <li>    1. obtenir le pixel situé à x=5 et y=10 </li>\n",
    "    <li> 2. changer ce pixel en noir </li>\n",
    "    <li>3. afficher l'image pour vérifier</li>\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Partie A : algorithme simple de rotation d'un quart de tour."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">     \n",
    "    \n",
    "## Exercice 1 :  \n",
    "    \n",
    "\n",
    "1. Ouvrir l'image de la joconde et l'afficher\n",
    "2. Afficher les dimensions de cette image.\n",
    "3. Créer un nouvelle image, de mêmes dimensions, qui sera noire au début. Elle servira à stocker l'image obtenue par rotation.\n",
    "4. <strong>Propriété </strong>: Pour une image carrée de taille $n \\times n$, l'image obtenue par rotation d'un quart de tour dans le sens des aiguilles d'une montre a pour pixel $(x,y)$ le pixel initialement en $(y,n-1-x)$.  \n",
    "    Ecrire une suite d'instructions qui stocke dans la nouvelle image celle obtenue par rotation de la joconde.  \n",
    "5. Enregistrez l'image dans le fichier `joconde_2.jpg`.  Afficher cette nouvelle image\n",
    "\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "from PIL import Image\n",
    "# question 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#question 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#question 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "# question 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# question 5\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">     \n",
    "    \n",
    "## Exercice 2 :  \n",
    "    \n",
    "\n",
    "\n",
    "Pour une image de taille $n \\times n$, quelle est la taille de la mémoire utilisée par cet algorithme ?\n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Votre réponse : ..............."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> Rotation d'un quart de tour d'une image avec le principe du Diviser pour Régner </h2>\n",
    "\n",
    "Dans la suite de ce notebok, nous allons faire le quart de tour mais en utilisant une méthode récursive. <br>\n",
    "<h5> Dans toute cette partie, on se contentera de faire tourner une image carrée dont la taille est une puissance de 2.</h5>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">     \n",
    "    \n",
    "## Exercice 3 :  \n",
    "    \n",
    "\n",
    "\n",
    "1. Ecrire une procédure (une fonction sans retour) `echange_pix(image, x0, y0, x1, y1)` qui échange les pixels de coordonnées $(x0,y0)$ et $(x1,y1)$ de l'image passée en paramètres.\n",
    "    \n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def echange_pix(image:Image, x0:int, y0:int, x1:int , y1:int):\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ouverture d'une image test\n",
    "test=Image.open(\"image_test.png\")\n",
    "test.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# choix des pixels à echanger\n",
    "x0 , y0 = 10,10  \n",
    "x1 , y1 = 45,10\n",
    "pixel0 = test.getpixel((x0,y0)) \n",
    "pixel1 = test.getpixel((x1,y1))\n",
    "\n",
    "#test de la fonction echange_pix\n",
    "echange_pix(test,x0,y0,x1,y1)\n",
    "assert test.getpixel((x0,y0)) == pixel1\n",
    "assert test.getpixel((x1,y1)) == pixel0\n",
    "test.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans la suite de cet exercice, nous allons adopter une stratégie de type *diviser pour régner*  \n",
    "\n",
    "L'image est divisée en 4 cadrans. Chaque cadrant est tourné récursivement puis une permutation circulaire est effectuée.\n",
    "\n",
    "![rotations récursives](https://nc-lycees.netocentre.fr/s/ajsRdy2sGj9GHTB/download)\n",
    "\n",
    "La permutation de chaque cadrant est réalisée en enchaînant plusieurs échanges de cadrans.\n",
    "\n",
    "![rotations récursives](https://nc-lycees.netocentre.fr/s/pHPqgzHNifrDiE3/download)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">     \n",
    "    \n",
    "## Exercice 4 :  \n",
    "    \n",
    "\n",
    "\n",
    "Ecrire une procédure (une fonction sans retour) `echange_cadrans(image, x0, y0, x1, y1,n)` qui échange deux cadrants carrés de taille `n` de coordonnées de départ (x0,y0) et le second de coordonnées (x1,y1).\n",
    "    \n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def echange_cadrans(image:Image, x0:int, y0:int, x1:int, y1:int, n:int):\n",
    "    pass\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "# test de echange_cadrans du cadran 1 du cadran 2\n",
    "test=Image.open(\"image_test.png\")\n",
    "echange_cadrans(test,0,0,31,0,32)\n",
    "test.show()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# re échanger les cadrans 1 et 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# tests echange du cadran  3 du cadran 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">     \n",
    "    \n",
    "## Exercice 5 :  \n",
    "    \n",
    "\n",
    "Ecrire une procédure récursive `tourne_cadrans(image,x0,y0,n)` qui prend en paramètres l'image considérée, les coordonées de départ (x0,y0) et la taille `n` du cadran.\n",
    "Cette procédure doit appliquer récursivement les rotations à chaque cadran puis applique les permutations circulaires échangeant les 4 cadrans pour finaliser la rotation.\n",
    "    \n",
    "*Indice : le cas de base se produit quand n vaut 1, dans ce cas la rotation est très simple ...*\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tourne_cadrans(image,x0,y0,n):\n",
    "    \n",
    "    if n>1:\n",
    "        pass\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">     \n",
    "    \n",
    " \n",
    "   \n",
    "Pour vérifier votre procédure `tourne_cadrans` , lancer la procédure `tourne_image(image)` effectuant la rotation d'un quart de tour de l'image via cette méthode récursive, \n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "def tourne_image(image : Image):\n",
    "    n,p = image.size\n",
    "    assert n == p\n",
    "    tourne_cadrans(image,0,0,n)\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# tester tourne_image avec image_test\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# tester tourne_image avec l'image de la joconde (\"joconde.jpg\") et l'enregistre sous joconde3.jpg\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-block alert-warning\">     \n",
    "    \n",
    "## Exercice 6 :  \n",
    "    \n",
    "\n",
    "Pour une image de taille 𝑛×𝑛, quelle est la taille de la mémoire utilisée par cet algorithme ?\n",
    "    \n",
    "</div>"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "**Votre réponse ici** :............."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2> Résumé </h2>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous avons vu deux algorithmes permettant de tourner une image carrée de taille une puissance de 2.\n",
    "\n",
    "<ol> <li> Algorithme naif : </li>\n",
    "    <ul>\n",
    "        <li>la complexité en temps de l'algorithme naïf est en O(n²) ( 2 boucles pour imbriquées) </li>\n",
    "        <li> Par contre, lors de cet algorithme naïf, il a fallu construire une seconde image de même taille pixel par pixel. Cela conduit donc à une complexité en mémoire en O(n²). </li>\n",
    "    </ul><br>\n",
    "    <li> Algorithme suivant le paradigme diviser pour régner </li>\n",
    "        <ul>\n",
    "<li> Diviser : on découpe l'image en images de taille divisée par 2,</li>\n",
    "<li> Régner : on effectue la rotation de manière récursive de chaque image de taille réduite: concrétement on ne modifie pas le pixel</li>\n",
    "<li> Combiner : on échange les cadrans lors des appels récursifs.</li>\n",
    "</ul>\n",
    "         <ul>\n",
    "        <li> Premièrement, la complexité en temps. Si on étudie la procédure récursive tourne_cadrans, elle fait appel 4 fois à elle-même sur des images de taille réduite de 2 mais il y a aussi 3 appels à une procédure echange_cadrans. Cette procédure echange_cadrans contient 2 boucles for imbriquées. Sa complexité est en O(n²)<br>\n",
    "Dès lors, on peut montrer par un calcul mathématique que la complexité en temps de la procédure tourneCarre est en O(n²×log2(n))\n",
    "Cette complexité en temps est donc (un peu) moins bonne que celle de l'algorithme naïf.</li>\n",
    "    <li>Par contre, dans cette procédure, il n'y a pas de création d'une nouvelle image mais de simples permutations de pixels, un à un. La complexité en mémoire est donc ici en O(1).\n",
    "Cette complexité en mémoire en donc bien meilleure que celle de l'algorithme naïf.</li>\n",
    "</ul>\n",
    "</ol>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}