Retirer $k$ colonnes

-

static int[][] reduire(int[][] I, int k) {
    for (int i = 0; i < k; i++) {                // I a perdu i colonnes
        int[][] M = calculerM(energie(I));
        I = retirer(I, couture(M));              // couture : colonnes du chemin minimum
    }
    return I;
}

• Retirer une couture rapproche des pixels qui n'étaient pas voisins : les énergies des pixels situés le long de la couture changent. Les garder fausserait les coutures suivantes. (Une implémentation fine ne recalcule que les énergies voisines de la couture, mais le tableau $M$ doit, lui, être recalculé en entier.)
• Chaque couture coûte $\Theta (LC)$ (énergies, $M$, retrait), donc $k$ coutures coûtent $\Theta (kLC)$, soit $\Theta (n^3)$ si $L=C=n$ et $k=n/2$ : doubler $n$ doit multiplier le temps par environ $8$.

largeur après 4 coutures : 6
L = C = 200, k = 100 : 0,038 s (largeur finale 100)
L = C = 400, k = 200 : 0,294 s (largeur finale 200)
L = C = 800, k = 400 : 3,152 s (largeur finale 400)

Les rapports observés ($7,7$ puis $10,7$) sont proches de $8$ ; le second est un peu plus grand car les tableaux de $800\times 800$ ne tiennent plus dans les mémoires caches du processeur. Les temps dépendent de la machine.