Protéger ou supprimer un objet — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 6)

Protéger ou supprimer un objet

Redimensionner une image : le seam carving · niveau 2

Énoncé

On veut qu'aucune couture ne traverse une zone rectangulaire donnée (un visage, par exemple). Comment modifier les énergies ?
Inversement, comment faire pour qu'un objet soit retiré en priorité ?
Le vérifier sur l'image du chapitre : protéger les colonnes $[2 : 5]$ , puis forcer la suppression de la colonne $6$ .

Corrigé

On donne aux pixels de la zone une énergie énorme (par exemple $100000$ , bien plus que le coût de toute couture ordinaire) : une couture qui la traverse coûte plus cher que n'importe quelle autre, et n'est jamais retenue tant qu'il existe une couture qui l'évite.
On donne aux pixels de l'objet une énergie très négative ( $- 100000$ ) : les coutures de coût minimum passent par lui. On retire des coutures jusqu'à ce que l'objet ait disparu, puis on peut réélargir l'image (exercice 6.9).
On modifie une copie du tableau des énergies avant de calculer $M$ :


static int[][] modifier(int[][] E, int l1, int l2, int c1, int c2, int v) {
    int[][] F = new int[E.length][];
    for (int l = 0; l < E.length; l++) F[l] = E[l].clone();
    for (int l = l1; l < l2; l++) for (int c = c1; c < c2; c++) F[l][c] = v;
    return F;
}


sans contrainte : [3, 4, 4, 4, 3]
zone [2:5] protégée : [1, 1, 1, 1, 1]
colonne 6 à supprimer : [6, 6, 6, 6, 6]

La couture optimale passait par les colonnes $3$ et $4$ ; une fois la zone protégée, elle se reporte sur la colonne $1$ .