Convolution séparable — économiser un facteur k — exercice corrigé d'informatique (tronc commun des prépas scientifiques) (chapitre 8)

Convolution séparable — économiser un facteur

k

Matrices de pixels et images · niveau 3 (difficile)

Énoncé

Montrer qu'un flou moyenneur $k \times k$ peut s'implémenter de manière séparée en effectuant une passe de moyenne horizontale de taille $k$ puis une passe verticale de même taille. Écrire le code associé et comparer les coûts.

Corrigé

Équivalence mathématique : La moyenne d'un bloc de taille $k \times k$ peut se factoriser sous la forme : $\frac{1}{k ^{2}} a \sum b \sum img [i + a] [j + b] = \frac{1}{k} a \sum (\frac{1}{k} b \sum img [i + a] [j + b])$

def flou_separable(img: list, k: int) -> list:
    n, p = len(img), len(img[0])
    r = k // 2
    # Passe 1 : Moyenne horizontale
    h = [[0] * p for _ in range(n)]
    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 : Moyenne verticale sur la matrice intermédiaire h
    res = [ligne[:] for ligne in h]
    for i in range(r, n - r):
        for j in range(p):
            res[i][j] = sum(h[i + a][j] for a in range(-r, r + 1)) // k
    return res

La convolution bidimensionnelle classique effectue $k^{2}$ lectures par pixel. La version séparable n'effectue que $2 k$ opérations (une moyenne de taille $k$ sur chaque dimension). Pour un grand filtre (ex: $k = 25$ ), le gain est de $2 5^{2} = 625$ opérations contre $2 \times 25 = 50$ , soit une accélération d'un facteur $12, 5$ .

Convolution séparable — économiser un facteur k

Énoncé

Corrigé

Exercices semblables

Convolution séparable — économiser un facteur $k$