Combien de coutures ? — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 6)

Combien de coutures ?

Redimensionner une image : le seam carving · niveau 1 (application)

Énoncé

On note $N (l, c)$ le nombre de coutures partielles de la ligne $0$ au pixel $(l, c)$ .

Établir la récurrence des valeurs $N (l, c)$ . Comment obtient-on le nombre total de coutures d'une image $L \times C$ ?
Calculer ce nombre à la main pour une image $3 \times 4$ , puis par programme pour $5 \times 8$ et $100 \times 100$ .
Montrer qu'il est au plus $C \cdot 3^{L - 1}$ .

Corrigé

Une couture partielle vers $(l, c)$ vient de $(l - 1, c - 1)$ , $(l - 1, c)$ ou $(l - 1, c + 1)$ .

Base. $N (0, c) = 1$ pour toute colonne $c$ .

Hérédité. $\forall l \geq 1$ : $N (l, c) = N (l - 1, c - 1) + N (l - 1, c) + N (l - 1, c + 1)$ , les termes hors de l'image omis.

Le nombre total de coutures est $\sum_{c} N (L - 1, c)$ .

Pour $3 \times 4$ : ligne $0$ : $[1, 1, 1, 1]$ ; ligne $1$ : $[2, 3, 3, 2]$ ; ligne $2$ : $[5, 8, 8, 5]$ ; total $26$ .


nom : N
valeurs : 2 3 3 2
vert : 0..2
legende : ligne 1


nom : N
valeurs : 5 8 8 5
colorier : 1
zone : 0..3 total 26
legende : ligne 2


5 x 8 : 502
3 x 4 : 26
100 x 100 : 15116889835751504709361077940682197429012095346416

Une image de $100 \times 100$ pixels compte environ $1, 5 \times 1 0^{49}$ coutures : seule la programmation dynamique permet de trouver la meilleure.

Chaque couture est déterminée par sa colonne de départ ( $C$ choix) et par ses $L - 1$ pas, chacun parmi au plus trois : au plus $C \cdot 3^{L - 1}$ coutures. Pour $5 \times 8$ : $502 \leq 8 \times 81 = 648$ .