Coutures horizontales

• Notons $m(l,c)$ le coût minimum d'une couture horizontale partielle de la colonne $0$ au pixel $(l,c)$.

Base. $\forall l,0\le l<L$ : $m(l,0)=e(l,0)$.

Hérédité. $\forall c,1\le c<C$, $\forall l,0\le l<L$ : $m(l,c)=\min \{m(l-1,c-1),m(l,c-1),m(l+1,c-1)\}+e(l,c)$, les termes hors de l'image étant omis. On calcule par colonnes croissantes ; la couture se termine en ${\mathrm{argmin}}_{l}m(l,C-1)$. -

static int[][] calculerMh(int[][] E) {
    int L = E.length, C = E[0].length;
    int[][] M = new int[L][C];
    for (int l = 0; l < L; l++) M[l][0] = E[l][0];            // base : colonne 0
    for (int c = 1; c < C; c++)                                // par colonnes croissantes
        for (int l = 0; l < L; l++) {
            int min = M[l][c - 1];                             // venir de l'Ouest
            if (l > 0) min = Math.min(min, M[l - 1][c - 1]);   // du Sud-Ouest
            if (l < L - 1) min = Math.min(min, M[l + 1][c - 1]); // du Nord-Ouest
            M[l][c] = min + E[l][c];
        }
    return M;
}

static int lignePredecesseur(int[][] M, int l, int c) {
    int L = M.length, lp = l;
    if (l > 0 && M[l - 1][c - 1] < M[lp][c - 1]) lp = l - 1;
    if (l < L - 1 && M[l + 1][c - 1] < M[lp][c - 1]) lp = l + 1;
    return lp;
}

static int[] coutureh(int[][] M) {               // lig[c] : ligne de la couture en colonne c
    int L = M.length, C = M[0].length;
    int[] lig = new int[C];
    int best = 0;
    for (int l = 1; l < L; l++) if (M[l][C - 1] < M[best][C - 1]) best = l;
    lig[C - 1] = best;
    for (int c = C - 1; c > 0; c--) lig[c - 1] = lignePredecesseur(M, lig[c], c);
    return lig;
}

static int[][] reduireImageh(int[][] I, int[] lig) {
    int L = I.length, C = I[0].length;
    int[][] R = new int[L - 1][C];
    for (int c = 0; c < C; c++) {
        for (int l = 0; l < lig[c]; l++) R[l][c] = I[l][c];          // sous la couture
        for (int l = lig[c] + 1; l < L; l++) R[l - 1][c] = I[l][c];  // au-dessus
    }
    return R;
}

• Oui : une couture horizontale de $I$ est une couture verticale de la transposée ${}^{t}I$, l'énergie est symétrique (même voisinage), et les pas NE, E, SE deviennent NE, N, NO. Le détour coûte deux transpositions en $\Theta (LC)$, du même ordre que le calcul lui-même. Sur l'image du chapitre ($5\times 8$) :

couture horizontale (lignes, colonne 0 d'abord) : [1, 0, 1, 1, 2, 2, 1, 1], coût 612
image réduite : 4 lignes, 8 colonnes
transposition : même image réduite ? true