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

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

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 $2k$ opérations (une moyenne de taille $k$ sur chaque dimension). Pour un grand filtre (ex: $k=25$), le gain est de $25^2=625$ opérations contre $2\times 25=50$, soit une accélération d'un facteur $12.5$.