15-8 Image compression by seam carving

We are given a color picture consisting of an $m \times n$ array $A[1..m, 1..n]$ of pixels, where each pixel specifies a triple of red, green, and blue (RGB) intensities. Suppose that we wish to compress this picture slightly. Specifically, we wish to remove one pixel from each of the $m$ rows, so that the whole picture becomes one pixel narrower. To avoid disturbing visual effects, however, we require that the pixels removed in two adjacent rows be in the same or adjacent columns; the pixels removed form a "seam" from the top row to the bottom row where successive pixels in the seam are adjacent vertically or diagonally.

a. Show that the number of such possible seams grows at least exponentially in $m$, assuming that $n > 1$.

b. Suppose now that along with each pixel $A[i, j]$, we have calculated a real-valued disruption measure $d[i, j]$, indicating how disruptive it would be to remove pixel $A[i, j]$. Intuitively, the lower a pixel's disruption measure, the more similar the pixel is to its neighbors. Suppose further that we define the disruption measure of a seam to be the sum of the disruption measures of its pixels.

Give an algorithm to find a seam with the lowest disruption measure. How efficient is your algorithm?

a. If $n > 1$ then for every choice of pixel at a given row, we have at least $2$ choices of pixel in the next row to add to the seam ($3$ if we're not in column $1$ or $n$). Thus the total number of possibilities is bounded below by $2^m$.

b. We create a table $D[1..m, 1..n]$ such that $D[i, j]$ stores the disruption of an optimal seam ending at position $[i, j]$, which started in row $1$. We also create a table $S[i, j]$ which stores the list of ordered pairs indicating which pixels were used to create the optimal seam ending at position $(i, j)$. To find the solution to the problem, we look for the minimum $k$ entry in row $m$ of table $D$, and use the list of pixels stored at $S[m, k]$ to determine the optimal seam. To simplify the algorithm $\text{Seam}(A)$, let $\text{MIN}(a, b, c)$ be the function which returns $−1$ if a is the minimum, $0$ if $b$ is the minimum, and $1$ if $c$ is the minimum value from among $a$, $b$, and $c$. The time complexity of the algorithm is $O(mn)$.

SEAM(A)
    let D[1..m, 1..n] be a table with zeros
    let S[1..m, 1..n] be a table with empty lists
    for i = 1 to n
        S[1, i] = (1, i)
        D[1, i] = d_{1i}
    for i = 2 to m
        for j = 1 to n
            if j == 1 // left-edge case
                if D[i - 1, j] < D[i - 1, j + 1]
                    D[i, j] = D[i - 1, j] + d_{ij}
                    S[i, j] = S[i - 1, j].insert(i, j)
                else
                    D[i, j] = D[i - 1, j + 1] + d_{ij}
                    S[i, j] = S[i - 1, j + 1].insert(i, j)
            else if j == n // right-edge case
                if D[i - 1, j - 1] < D[i - 1, j]
                    D[i, j] = D[i - 1, j - 1] + d_{ij}
                    S[i, j] = S[i - 1, j - 1].insert(i, j)
                else
                    D[i, j] = D[i - 1, j] + d_{ij}
                    S[i, j] = S[i - 1, j].insert(i, j)
            x = MIN(D[i - 1, j - 1], D[i - 1, j], D[i - 1, j + 1])
            D[i, j] = D[i - 1, j + x]
            S[i, j] = S[i - 1, j + x].insert(i, j)
    q = 1
    for j = 1 to n
        if D[m, j] < D[m, q]
            q = j
    print(S[m, q])