Agrandir une image — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 6)

Agrandir une image

Redimensionner une image : le seam carving · niveau 3 (difficile)

Énoncé

Pour élargir une image d'une colonne, on duplique une couture de coût minimum : dans chaque ligne, on insère juste après le pixel de la couture un nouveau pixel, moyenne de ce pixel et de son voisin de droite.

Écrire la fonction int[][] inserer(int[][] I, int[] col), où col[l] est la colonne de la couture dans la ligne $l$ .
L'appliquer à l'image de l'exercice 6.1.
Pour élargir de $k$ colonnes, pourquoi ne faut-il pas répéter $k$ fois « chercher la couture minimum puis la dupliquer » ? Proposer une meilleure méthode.

Corrigé


static int[][] inserer(int[][] I, int[] col) {
    int L = I.length, C = I[0].length;
    int[][] R = new int[L][C + 1];
    for (int l = 0; l < L; l++) {
        int a = col[l];
        for (int c = 0; c <= a; c++) R[l][c] = I[l][c];                 // R[0:a+1] = I[0:a+1]
        R[l][a + 1] = (a + 1 < C) ? (I[l][a] + I[l][a + 1]) / 2 : I[l][a]; // pixel inséré
        for (int c = a + 1; c < C; c++) R[l][c + 1] = I[l][c];          // R[a+2:C+1] = I[a+1:C]
    }
    return R;
}

La couture minimum est $[0, 1, 0]$ (exercice 6.1) :


couture : [0, 1, 0]
l=2 [10, 10, 10, 80, 80]
l=1 [10, 80, 80, 80, 10]
l=0 [80, 80, 80, 10, 10]


nom : R
valeurs : 10 80 80 80 10
vert : 1
colorier : 2
legende : ligne l = 1 : pixel inséré après la couture, (80 + 80) / 2 = 80

Après la duplication, la zone dupliquée reste peu énergique : la couture minimum suivante serait presque toujours la même, et l'on étirerait $k$ fois la même bande, ce qui crée un artefact très visible. La méthode d'Avidan et Shamir : chercher d'abord les $k$ coutures que l'on retirerait (en les retirant une à une d'une copie de l'image, et en mémorisant leurs positions dans l'image d'origine), puis dupliquer ces $k$ coutures distinctes dans l'image d'origine.