Matrices de pixels et images

Première partie : [[0, 7, 0], [0, 7, 0]] — les deux lignes sont la même liste, modifier l'une « modifie l'autre ». Correction : [[0] 3 for _ in range(2)]. Seconde partie : [[5, 0], [0, 0]] — ligne n'est pas une copie mais un alias de la première ligne : toute affectation nom = liste partage, ne copie pas. Pour copier une ligne : ligne = list(compteur[0]) (ou compteur[0][:]). (Les deux pièges sont le même phénomène — plusieurs noms pour une seule liste — vu à la création puis à l'affectation ; le diagnostic en une question : « combien de listes distinctes ai-je réellement créées ? ».)*

def moyennes_lignes(M: list) -> list:
    return [sum(ligne) / len(ligne) for ligne in M]

def moyennes_colonnes(M: list) -> list:
    n, p = len(M), len(M[0])
    return [sum(M[i][j] for i in range(n)) / n for j in range(p)]

M = [[10, 14], [12, 18]]
assert moyennes_lignes(M) == [12.0, 15.0]      # par élève
assert moyennes_colonnes(M) == [11.0, 16.0]    # par devoir

Chaque fonction lit chaque case une fois : $O(np)$. La version colonnes illustre le parcours « $j$ externe, $i$ interne » du cours — ou, en une ligne, la somme sur $i$ à $j$ fixé. (Élèves/devoirs, villes/mois, pixels : la matrice est la structure des données croisées, et les deux familles de moyennes sont ses deux lectures.)

def eclaircir(img: list, delta: int) -> list:
    n, p = len(img), len(img[0])
    return [[min(255, max(0, img[i][j] + delta)) for j in range(p)]
            for i in range(n)]

img = [[250, 100]]
assert eclaircir(img, 30) == [[255, 130]]       # 280 aurait débordé !
aller_retour = eclaircir(eclaircir(img, 30), -30)
assert aller_retour == [[225, 100]]             # 250 est PERDU : 255 - 30 = 225

Sans écrêtage, le pixel $280$ sortirait du format — affiché n'importe comment, ou pire, stocké modulo $256$ comme $24$ : un point brûlé devenu noir. Et l'aller-retour montre que l'écrêtage détruit de l'information : tous les pixels au-dessus de $225$ sont devenus $255$, indiscernables — l'éclaircissement n'est pas inversible. (Une transformation d'image n'est pas une bijection en général ; quand on retouche, on garde l'originale — version photographique de « copier avant de muter ».)

def transpose(M: list) -> list:
    n, p = len(M), len(M[0])
    return [[M[i][j] for i in range(n)] for j in range(p)]

def rotation_horaire(img: list) -> list:
    return miroir(transpose(img))               # transposer PUIS miroir g-d

def rotation_antihoraire(img: list) -> list:
    return transpose(miroir(img))               # miroir PUIS transposer

import random
for essai in range(200):
    n, p = random.randint(1, 6), random.randint(1, 6)
    img = [[random.randint(0, 255) for _ in range(p)] for _ in range(n)]
    r = rotation_horaire(img)
    assert len(r) == p and len(r[0]) == n        # dimensions échangées
    q = rotation_horaire(rotation_horaire(rotation_horaire(r)))
    assert q == img                              # quatre quarts = identité

Vérifions la composée sur un pixel : transpose envoie la source $(a,b)$ en $(b,a)$ ; le miroir gauche-droite envoie $(b,a)$ en $(b,n-1-a)$ — donc le pixel résultat $(i,j)=(b,n-1-a)$ vient de $(a,b)=(n-1-j,i)$ : c'est exactement la formule directe du cours. (Composer deux transformations simples et sûres plutôt qu'inventer une formule d'indices : moins rapide d'un facteur deux, mais beaucoup plus difficile à rater — un arbitrage légitime tant que le profil de coût reste $O(np)$.)

def cherche_motif(motif: list, img: list):
    m, q = len(motif), len(motif[0])
    n, p = len(img), len(img[0])
    for i in range(n - m + 1):
        for j in range(p - q + 1):
            # le motif coïncide-t-il en (i, j) ?
            ok = True
            for a in range(m):
                for b in range(q):
                    if img[i + a][j + b] != motif[a][b]:
                        ok = False
                        break
                if not ok:
                    break
            if ok:
                return (i, j)
    return None

Coût : $(n-m+1)(p-q+1)$ positions, au plus $mq$ comparaisons chacune — $O(np\cdot mq)$, le produit des tailles, fidèle au $O(np)$ du facteur 1D. Et comme en 1D, l'échec est en pratique très précoce (le premier pixel discordant suffit), mais le pire cas — image unie, motif presque uni — paie le prix entier. (Les bornes n - m + 1 et p - q + 1 sont les mêmes « positions de départ » que le chapitre 3, dans chaque dimension ; ce balayage par fenêtre est aussi la structure de la convolution — la vision par ordinateur cherche ses motifs exactement ainsi, en remplaçant l'égalité stricte par un score de ressemblance.)

$K_1$ est le noyau identité : la somme se réduit à $1\times \text{img}[i][j]$ — l'image est inchangée (le test de base de toute implémentation de convolution !). $K_2$ prélève le voisin de droite : $\text{res}[i][j]=\text{img}[i][j+1]$ — l'image entière se décale d'un pixel vers la gauche. $K_3$ est le filtre de Sobel (vertical) : différence pondérée entre colonnes droite et gauche — nul sur les zones unies, maximal sur les contours verticaux (un mur clair sur fond sombre) ; les contours horizontaux, eux, lui échappent (la somme par colonne est équilibrée) ; son transposé les détecterait. (Lire un noyau : où sont les coefficients positifs et négatifs, leur somme est-elle nulle — détecteur de variations — ou égale à un — moyenne conservée ? Deux questions qui prédisent l'essentiel de l'effet, à vérifier ensuite sur l'image-test : une matrice avec un bord franc.)

def histogramme_image(img: list) -> list:
    h = [0] * 256
    for ligne in img:
        for v in ligne:
            h[v] += 1
    return h

def etire_contraste(img: list) -> list:
    """Précondition : l'image n'est pas uniforme (min < max)."""
    mini = min(min(ligne) for ligne in img)
    maxi = max(max(ligne) for ligne in img)
    n, p = len(img), len(img[0])
    return [[(img[i][j] - mini) * 255 // (maxi - mini) for j in range(p)]
            for i in range(n)]

Sur l'image grisâtre, les niveaux $100$–$140$ sont envoyés affinement sur $0$–$255$ : l'écart entre deux gris voisins est multiplié par $\approx 6$ — les détails noyés dans la brume deviennent visibles. L'histogramme avant (un pic étroit autour de $120$) et après (étalé sur toute la plage) rend l'effet lisible sans même afficher l'image. La précondition exclut l'image uniforme (division par zéro — et qu'attendre d'un contraste sans contraste ?). (Le comptage du chapitre 2 — ici en tableau plutôt qu'en dictionnaire, les clés étant les entiers $0$–$255$ : quand les clés sont de petits entiers denses, le tableau est le dictionnaire du pauvre, et le plus rapide.)

img = [[0] * 21 for _ in range(21)]
img[10][10] = 255                          # un point blanc au centre
for _ in range(10):
    img = convolution(img, FLOU)

Après un flou, le point devient un carré $3\times 3$ d'intensité $255/9\approx 28$ ; après deux, une tache $5\times 5$ aux coins plus sombres ; au fil des itérations, la tache s'élargit et prend un profil en cloche — l'intensité se répartit comme les sommes de dés du chapitre 4, et pour la même raison : chaque passage moyenne des contributions voisines, et la répétition de moyennes fabrique une cloche (le cours de probabilités donnera son nom à ce phénomène). La limite, à image infinie, est un étalement uniforme vers $0$ ; sur l'image bornée avec nos bords figés, une quasi-uniformité.

Pour la miniature : réduire directement d'un facteur $k$ par sous-échantillonnage ne lit qu'un pixel sur $k^2$ — un détail fin (une ligne d'un pixel) peut tomber entre les mailles et disparaître ou produire des escaliers (le crénelage). Flouter d'abord répartit l'information de chaque détail sur un voisinage de la taille de la maille : le pixel conservé « contient » alors un résumé de son bloc — c'est d'ailleurs exactement ce que fait la réduction par moyenne du cours, qui combine les deux étapes en une. (Règle des photographes numériques : on lisse à l'échelle de ce qu'on va jeter. La version théorique — le théorème d'échantillonnage — attendra ; l'intuition expérimentale est déjà la bonne.)

Équivalence : la moyenne sur le bloc $k\times k$ s'écrit

$$\frac{1}{k^2}\sum _a\sum _b\text{img}[i+a][j+b]=\frac{1}{k}\sum _a(\frac{1}{k}\sum _b\text{img}[i+a][j+b])$$

— la somme double se factorise : moyenner d'abord chaque ligne par fenêtres de $k$ (la parenthèse), puis moyenner verticalement ces moyennes. Le noyau moyenneur est dit séparable (produit d'un noyau colonne par un noyau ligne).

def flou_separable(img: list, k: int) -> list:
    n, p = len(img), len(img[0])
    r = k // 2
    # passe 1 : moyennes horizontales (copie : les bords y survivent)
    h = [ligne.copy() for ligne in img]
    for i in range(n):
        for j in range(r, p - r):
            h[i][j] = sum(img[i][j + b] for b in range(-r, r + 1)) // k
    # passe 2 : moyennes verticales sur h (même convention de bords)
    res = [ligne.copy() for ligne in img]
    for i in range(r, n - r):
        for j in range(r, p - r):
            res[i][j] = sum(h[i + a][j] for a in range(-r, r + 1)) // k
    return res

(Les divisions entières successives peuvent différer de la division par $k^2$ d'une unité : l'égalité avec la version directe est à un près.)

Coûts : la version directe fait $k^2$ lectures par pixel ; les deux passes en font $k+k=2k$ — gain d'un facteur $k/2$, soit $\times 12$ pour un flou large $k=25$ (très utilisés en pratique). (Et l'on peut faire mieux encore : la somme d'une fenêtre glissante se met à jour en $O(1)$ — ajouter l'entrant, retirer le sortant, comme la moyenne glissante du chapitre 4 — ramenant le flou à $O(np)$, indépendant de $k$. Trois implémentations, trois coûts, un seul résultat : l'algorithmique du traitement d'image est une affaire de factorisations.)

import random

def image_aleatoire():
    n, p = random.randint(1, 8), random.randint(1, 8)
    return [[random.randint(0, 255) for _ in range(p)] for _ in range(n)]

def copie(img):
    return [ligne[:] for ligne in img]

# 1. unitaires : la matrice 2x3 témoin, tout à la main
T = [[1, 2, 3], [4, 5, 6]]
assert negatif(T) == [[254, 253, 252], [251, 250, 249]]
assert miroir(T) == [[3, 2, 1], [6, 5, 4]]
assert rotation_horaire(T) == [[4, 1], [5, 2], [6, 3]]
assert reduction([[1, 3], [5, 7]], 2) == [[4]]

# 2. propriétés, sur 500 images aléatoires
random.seed(8)
for _ in range(500):
    img = image_aleatoire()
    avant = copie(img)
    assert miroir(miroir(img)) == img                          # involution
    assert negatif(negatif(img)) == img
    r = rotation_horaire(img)
    assert (len(r), len(r[0])) == (len(img[0]), len(img))      # dimensions
    assert rotation_horaire(rotation_horaire(
           rotation_horaire(rotation_horaire(img)))) == img    # 4 quarts
    convolution(img, FLOU)
    assert img == avant                                        # 3. source intacte

Le garde-fou final (3) est testé après chaque fonction : c'est lui qui attrape les [[0]p]n et les écritures dans la source au lieu de la copie — les deux bogues structurels du chapitre, indétectables sur le seul résultat. La conservation de la somme par le flou (somme des coefficients $=1$) se teste hors bords et hors écrêtage, sur des images aux valeurs centrales : chaque propriété s'accompagne de son domaine de validité, comme toute spécification. (Ce banc tient en trente lignes et rejoue en une seconde : c'est lui, plus que la relecture, qui autorise à modifier une fonction six mois plus tard — la définition même d'un livrable, au sens des compétences « mettre en œuvre » et « justifier » du programme.)