Parcours de matrices

Principe

Comme pour le parcours d'un tableau "simple" il y a également deux méthodes, qui utilisent toutes les deux deux boucles imbriquées :

Parcours par valeur


matrice = [[0,1,2,3],[4,5,6,7],[8,9,10,11]]

for ligne in matrice :  # boucle sur les "lignes"
	for element in ligne : # boucles sur les éléments de chacune des "lignes"
		print(element, end =' ')	
	
>>> 0 1 2 3 4 5 6 7 8 9 10 11

On retrouve la même structure que pour la construction de matrices par compréhension :

la boucle "extérieure" parcourt la matrice ligne par ligne
la boucle "intérieure" parcourt la ligne colonne par colonne

Parcours par indice


matrice = [[0,1,2,3],[4,5,6,7],[8,9,10,11]]

lignes = len(matrice) # nombre d'éléments dans la matrice = nombre de "lignes"
colonnes = len(matrice[0])  # nombre d'éléments dans le premier sous-tableau = nombre de "colonnes" !

for l in range(lignes) :  # boucle sur les "lignes"
	for c in range(colonnes) : # boucles sur les "colonnes"
		print(matrice[l][c])	# affichage de l'élément à la ligne l et à la colonne c
	
>>> 0 1 2 3 4 5 6 7 8 9 10 11

La deuxième méthode semble plus compliquée, mais c'est la seule qui permette en plus de modifier les éléments de la matrice ( c'est impossible avec la première méthode ).

Exercices

Affichages multiples

Pour cet exercice, on travaillera avec une matrice quelconque, par exemple celle ci-dessous :


m = [[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11],[12, 13, 14, 15]]

On rappelle que pour afficher des éléments sur une même ligne, il faut rajouter un argument dans la fonction print() :


print(x, end =' ') # affiche la valeur de x sans revenir à la ligne

Pour sauter une ligne, il suffit d'un print() sans aucun argument :


print() # saute une ligne

A partir de la matrice créée à la deuxième question de l'exercice 2.4.1 :

afficher la matrice ligne par ligne


[0, 1, 2, 3]
[4, 5, 6, 7]
[8, 9, 10, 11]
[12, 13, 14, 15]

afficher la matrice élément par élément mais en les présentant en lignes et en colonnes
```
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
					
```
afficher la matrice colonne par colonne ( plus dur ! )
```
0 4 8 12
1 5 9 13
2 6 10 14
3 7 11 15
					
```

m = [[0,1,2,3],[4,5,6,7],[8,9,10,11],[12,13,14,15]]

Lien vers les RÉPONSES

Inverser les zéros et les uns

Dans cet exercice, une fonction doit muter une matrice, c'est à dire qu'elle la prend en paramètre, et la modifie.

Parcours par valeur ou par indice dans ce cas ?

Compléter la fonction inverser_0_et_1 qui :

prend en paramètres une matrice mat d'entiers égaux à 0 ou à 1,
mute mat afin d'en inverser toutes les valeurs : les 0 sont transformés en 1, et les 1 sont transformés en 0.


[[0, 1, 1, 0],				[[1, 0, 0, 1],	
[1, 0, 1, 0],		=>		[0, 1, 0, 1],
[0, 0, 0, 1]]				[1, 1, 1, 0]]

def inverser_0_et_1(mat): pass

Lien vers les RÉPONSES

Maximum/Minimum d'une matrice

Objectif : adapter l'algorithme de la recherche du maximum/minimum dans un tableau, à la recherche dans une matrice.

Parcours par valeur ou parcours par indice ??

écrire une fonction maximum_matrice qui prend en paramètre une matrice m d'entiers, et renvoie la valeur du maximum dans cette matrice.
écrire une fonction minimum_matrice qui prend en paramètre une matrice m d'entiers, et renvoie la valeur du minimum dans cette matrice.

tester les fonctions avec le jeu de test suivant :

	
mat_a = [[0,  7,  8,  9,  5,  3,  2,  12], 
         [13, 6,  7,  8,  3,  15, 16, 4], 
         [-2, 6,  8,  21, 5,  6,  8,  4]]
maximum_matrice(mat_a) == 21
minimum_matrice(mat_a) == -2

mat_b = [[2, 3, 4], 
         [5, 6, 7], 
         [8, 9, 8], 
         [7, 6, 5]]
maximum_matrice(mat_b) == 9
minimum_matrice(mat_b) == 2

mat_c = [[-5, -7, -8],
         [-4, -2, -9],
         [-1, -2, -7]]
maximum_matrice(mat_c) == -1	
maximum_matrice(mat_c) == -9

def maximum_matrice(m): pass def minimum_matrice(m): pass

Lien vers les RÉPONSES

Multiplier des matrices

En machine learning, et particulièrement dans l'utilisation de réseaux de neurones, une des opérations les plus fréquemment réalisée est la multiplication de deux matrices entre elles.

Ce genre d'opération appartient à la branche des mathématiques appelé algèbre linéaire.

Principe

Le produit de deux matrices M1 et M2 se note M1⬩M2

Il faut que les dimensions des matrices soient "compatibles" : en l'occurrence, il faut que le nombre de colonnes de la première matrice soit égal au nombre de ligne de la deuxième.

Par exemple :

on peut multiplier une matrice de 4 lignes x 3 colonnes par une matrice de 3 lignes x 5 colonnes,
mais on ne pourra pas multiplier une matrice de 4 lignes x 3 colonnes par une de 5 lignes x 3 colonnes.

Écrire une fonction matrices_compatibles, qui prend deux matrices en paramètre, et qui renvoie un booléen indiquant si les deux matrices peuvent être multipliées entre elles.

def matrices_compatibles(M1, M2): pass M1 = [[1, 0], [-2, 3]] M2 = [[2, -1], [4, -3]] M3 = [[5, 1, 3], [2, 1, 4]] M4 = [[1, 2], [3, 4], [5, 6]]

Lien vers les RÉPONSES

Le produit d'une matrice de m lignes x n colonnes par une matrice de n lignes x p colonnes est lui-même une matrice, de m lignes x p colonnes.
On peut retenir : (m x n)⬩(n x p) = m x p.

Voila comment le produit se fait, dans le cas du produit d'une matrice 2x2 par une matrice 2x2 :

[\begin{matrix} 1 & 0 \\ - 2 & 3 \end{matrix}] \cdot [\begin{matrix} 2 & - 1 \\ 4 & - 3 \end{matrix}] = [\begin{matrix} 1 \times 2 + 0 \times 4 & 1 \times - 1 + 0 \times - 3 \\ - 2 \times 2 + 4 \times 3 & - 2 \times - 1 + 3 \times - 3 \end{matrix}] = [\begin{matrix} 2 & - 1 \\ 8 & - 7 \end{matrix}]

Chaque élément de la matrice produit est donc égal à la somme des produits des éléments d'une ligne de la première matrice, par les éléments d'une colonne de la deuxième :

ligne 0, colonne 0 : on fait la somme des produits des éléments de la ligne 0 de la première matrice, par ceux de la colonne 0 de la deuxième;
ligne 1, colonne 0 : ligne 1 de la première, colonne 0 de la deuxième,
ligne 0, colonne 1 : ligne 0 de la première, colonne 1 de la deuxième,
etc...
en résumé : en (i, j) de la matrice produit, on a la somme des produits des éléments de la ligne i de la première matrice par ceux de la colonne j de la deuxième.

Déterminer le produit des deux matrices suivantes : $(\begin{array}{cc} - 2 & 1 \\ 2 & - 3 \end{array}) . (\begin{array}{cc} 2 & - 1 \\ - 2 & 3 \end{array}) =$ ?
Vérifier le résultat suivant : $(\begin{array}{cc} 4 & 2 \\ 1 & 3 \end{array}) . (\begin{array}{ccc} 5 & 1 & 3 \\ 2 & 1 & 4 \end{array}) =$ $(\begin{array}{ccc} 24 & 6 & 20 \\ 11 & 4 & 15 \end{array})$

Lien vers les RÉPONSES

Une fonction de multiplication

Compléter le code de la fonction produit_matrices ci-dessous, qui prend comme paramètre deux matrices M1 et M2, utilise la fonction matrices_compatibles codée précédemment pour vérifier que les deux matrices peuvent être multipliées, et renvoie la matrice produit de M1 et M2.

A l'aide des exemples précédents, vérifier que la fonction renvoie un résultat correct.

def produit_matrices(M1, M2): assert matrices_compatibles(M1, M2), "Les deux matrices ne peuvent pas être multipliées entre elles." m = ... # nombre de lignes de M1 p = ... # nombre de colonne de M2 produit = [[0 for j in range(...)] for i in range(...)] # matrice produit ne contenant pour l'instant que des 0 for i in range(...): # pour chaque ligne i de la matrice produit, for j in range(...): # pour chaque colonne j de la matrice produit, somme = 0 for n in range(len(...)): # 'n' = dimension "commune" à M1 et M2 somme += M1[...][...]*M2[...][...] # calcul du produit des éléments de la ligne i de M1 par ceux de la colonne j de M2 produit[i][j] = somme return produit

Manipulation d'images plus poussées

Il va s'agir maintenant d'utiliser de "vraies" images ( des photos, quoi...), pour les manipuler comme on le ferait avec un logiciel de retouche d'images.

Choisissez une image quelconque ( mais pas trop grande ! ) en couleur au format .jpg ou .png.

Pour manipuler les images facilement, vous pourrez utiliser le module images.py ( clic droit > Enregistrer ), qui s'appuie aussi sur le module PIL.

Une fois importé, ce module propose deux fonctions :

get_pixels(nom_fichier) qui permet d'ouvrir un fichier image et de renvoyer la matrice de ses pixels codés sous forme de tuples (R,V,B).
show_image(data) qui permet d'afficher une image en lui passant comme argument une matrice de tuples (R,V,B).

Par exemple, pour ouvrir et afficher une image à partir d'un fichier image :


from images import *

data = get_pixels("fichier_image.jpg")

show_image(data)

Attention, la fonction get_pixels renvoie toujours une matrice de tuples (R, V, B), que l'image soit en niveau de gris ou en couleurs.

avec Pyzo, pensez à enregistrer les fichiers images et le module images.py dans le même répertoire que les scripts que vous allez écrire.
avec les éditeurs de la page, pensez à installer le module PIL, et à placer dans le système de fichiers virtuel le module images.py et les fichiers images.

Vous écrirez les fonctions qui permettront de transformer la matrice des valeurs de pixels pour obtenir l'effet recherché.

Le programme principal de votre script devra :

récupérer la matrice des valeurs de pixels
appeler la fonction que vous avez écrite en lui passant la matrice comme argument, puis en récupérant la matrice transformée
afficher la nouvelle image correspondant à la matrice transformée

La fonction devra au préalable faire une copie de la matrice des pixels d'origine, et ne travailler ensuite que sur cette copie. On évitera ainsi les effets de bord et on ne perdra pas les données de l'image de départ.

Revoir la page expliquant comment faire une "vraie" copie de tableau/matrice.


from images import *
import copy

def ma_fonction(matrice):
    """
    Fonction qui modifie une matrice de pixels pour obtenir un certain effet
    Entrée :
        la matrice des valeurs de pixels de l'image
        d'autres paramètres si besoin...
    Sortie :
        une matrice des valeurs de pixels modifiées	
    """
    
    copie = copy.deepcopy(matrice) # copie de la matrice d'origine
    ....... # modification de la matrice des valeurs de pixels
    .......
    .......
    
    return copie
	
	
data = get_pixels("nom_du_fichier_image.XXX") # récupération des données de l'image ( nom à adapter ! )

data2 = ma_fonction(data) # appel de la fonction et récupération de la matrice modifiée

show_image(data2) # affichage de la nouvelle image

Le négatif

Effet très populaire dans les années 70 et 80 : les pixels blancs de l'image sont transformés en pixels noirs, et vice et versa; de manière générale, toutes les valeurs de pixels sont remplacées par leur complément à 255 :

0 devient 255
255 devient 0
donc, de manière générale, une valeur quelconque est remplacée par 255 - valeur

Sur une image en couleurs, il faut donc remplacer chaque tuple (R, V, B) codant un pixel, par le tuple (255-R, 255-V, 255-B).

Chat normal

Chat inversé

from images import * import copy def image_negatif(mat): copie = copy.deepcopy(mat) for ... in ...: for ... in ... : pixel = ... R = ... V = ... B = ... nv_pixel = ... ... = nv_pixel return copie ## Programme principal data = get_pixels("nom_du_fichier_image.XXX") data2 = image_negatif(data) show_image(data2)

Lien vers les RÉPONSES

Le seuil

Effet qui revient à transformer une image en niveaux de gris ou en couleurs en une image en noir et blanc ou en 2 couleurs : tous les pixels en dessous d'une certaine valeur ( appelée "seuil" ) sont transformés en pixels noirs ( valeur = 0 ), et tous les pixels de valeur supérieure au seuil sont transformés en pixels blancs ( valeur = 255 ). Il n'y a donc effectivement plus que deux "couleurs" dans l'image.
Selon la valeur du seuil ( que l'on passera en argument à la fonction ), on obtient des effets différents :

Chat normal

Seuil à 50

Seuil à 150

Seuil à 200

from images import * import copy def image_seuil(mat, seuil): copie = copy.deepcopy(mat) for ... in ...: for ... in ... : pixel = ... R = ... if R > seuil: R = ... else: R = ... V = ... if V > seuil: V = ... else: V = ... B = ... if B > seuil: B = ... else: B = ... nv_pixel = ... ... = nv_pixel return copie ## Programme principal data = get_pixels("nom_du_fichier_image.XXX") data2 = image_seuil(data, 100) # valeur du seuil à expérimenter ! show_image(data2)

Lien vers les RÉPONSES

L'image retournée

Ou comment faire pivoter l'image de 180° ?

Chat normal

Chat renversé

from images import * import copy def image_180(matrice): pass ## Programme principal data = get_pixels("nom_du_fichier_image.XXX") data2 = image_180(data) show_image(data2)

Lien vers les RÉPONSES

Noir et blanc

Comment transformer une image en couleur en image en niveaux de gris ?

Singe en couleurs

Singe gris

Indication : il faut remplacer dans chaque tuple les valeurs (R,V,B) par un nombre identique, égal à la moyenne pondérée de ces trois valeurs, selon la formule suivante :
Gris = 0,2126 × Rouge + 0,7152 × Vert + 0,0722 × Bleu.

from images import * import copy def couleurs_gris(matrice): pass ## Programme principal data = get_pixels("nom_du_fichier_image.XXX") data2 = couleurs_gris(data) show_image(data2)

Lien vers les RÉPONSES

Applications

ASCII Art

L'Ascii Art consiste à réaliser des représentation graphiques à partir de caractères simples. Cette techniques est apparue dans les années 1960, à l'époque où afficher une image sur un écran d'ordinateur n'était pas possible.

On peut trouver sur le web des représentation de signatures ou d'objets :

logo de wikipedia

tux

Mais l'avènement des images sur ordinateur et de la photo numérique n'a pas entraîné la disparition de l'Ascii Art. Ainsi il est possible de transformer une image numérique en Ascii Art et faisant correspondre un caractère à chaque pixel de l'image. On choisira un caractère qui comporte beaucoup "de noir" comme @ pour un pixel noir et moins "de noir" comme . pour un pixel clair.

saturne

Cet exercice devra être réalisé dans Pyzo car il nécessite l'écriture sur le disque dur du fichier Ascii Art au format txt.

Vous pourez cependant rendre votre code dans l'éditeur ci-dessous.

Vous devez coder une fonction qui prend en paramètre le nom d'une image, le tableau de correspondance de caractères Ascii et le nom du fichier txt qui sera écrit sur le disque.
Cette fonction ne renverra rien mais écrira simplement sur le disque dur un fichier au format txt qui contiendra l'Ascii Art correspondant à l'image.

Pour récupérer les valeurs des pixels de l'image dans un tableau de tableau vous utiliserez le module images.py vu précédemment

Pour écrire les caractères de l'Ascii Art dans un fichier vous utiliserez les commandes suivantes :



import codecs #import du module qui permettra d'écrire le fichier 

fichiertexte=codecs.open('toto.txt',"w",'utf-8') #création d'un fichier toto.txt en écriture ('w') dont les caractères seront codés au format UTF-8

fichiertexte.write('@'+'\n') # écriture de @ suivi d'un retour à la ligne dans le fichier

fichiertexte.close() # fermeture du fichier

Pour la correspondance entre pixel et caractères vous pourrez utiliser le tableau ci-dessous :
```
car=['@','#','S','?','%','+',':','*',';','.',' ']
				
```
en notant bien qu'il contient 10 éléments et que les pixels sont codés par des entiers de 0 à 255.

Pour tester votre programme nous vous proposons cette super image de petit chat. Pour un rendu optimal vous pourrez ouvrir votre image dans LibreOffice et choisir les paramètres suivants :

Police : Liberation Monospace (une police à chasse fixe, indispensable pour éviter les décalages entre les lignes)
Taille de police : 4 pour que tout cela passe dans une page
Type de caractères : Gras afin d'augmenter le contraste

lopotichat

chat ascii art

Lien vers les RÉPONSES

Population des communes françaises

Sur la base de l'algorithme de parcours de tableau, nous pouvons également travailler maintenant avec les matrices.

Nous allons utiliser un exemple concret de recherche dans une matrice contenant "beaucoup" de données.
Pour cela téléchargez le fichier liste-des-communes-2019.csv. Il contient la liste des communes françaises, ainsi que leur population en 2019 et leur rang dans le classement des populations, sans ex-æquo.
Le code ci-dessous permet de transférer toutes ces données dans une matrice ( un tableau de tableaux ).


import csv

liste = []
with open("liste-des-communes-2019.csv", 'r', encoding='utf-8') as f:
    lecteur = csv.reader(f, delimiter = ',')
    for ligne in lecteur:
        liste.append([int(ligne[0]), ligne[1], int(ligne[2])])

Chaque "ligne" de la matrice correspond à une ville; les données sont classées dans cet ordre : rang, nom de commune, population.
Un affichage d'un extrait de la matrice donnera :


[11, 'Rennes', 216268]
[12, 'Reims', 183113]
[13, 'Saint-Étienne', 171924]

Vous avez a votre disposition une grande série de données et vous avez vu les algorithmes permettant de calculer une moyenne un maximum (ou un minimum...).
Vous devez coder un programme qui répondra aux questions suivantes :

Quelle est la commune ayant le plus grand nombre d'habitants ?
Quelle est la commune ayant le plus petit nombre d'habitants ?
Quelle est la moyenne d'habitants par commune en France ?

Votre programme devra être structuré en fonctions.

import csv liste = [] with open("liste-des-communes-2019.csv", 'r', encoding='utf-8') as f: lecteur = csv.reader(f, delimiter = ',') for ligne in lecteur: liste.append([int(ligne[0]), ligne[1], int(ligne[2])])

Question :

Quelle est la complexité de la recherche d'une valeur dans une matrice ?

Lien vers les RÉPONSES