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. Let us set up a recurrence for the number of valid seams as a function of $m$. Suppose we are in the process of carving out a seam row by row, starting from the first row. Let the last pixel carved out be $A[i, j]$. How many choices do we have for the pixel in row $i + 1$ such that the pixel continues the seam? If the last pixel $A[i, j]$ were on the column boundary ($i = 1$ or $i = n$), then there would be two choices for the next pixel. For example, when $i = 1$, the two choices for the next pixel are $A[i + 1, j]$ and $A[i + 1, j + 1]$. Otherwise, there would be three choices for the next pixel: $A[i + 1, j - 1], A[i + 1, j], A[i + 1, j + 1]$. Thus, for a general pixel $A[i, j]$, there are at least two possible choices for a pixel $p$ in the next row such that $p$ continues a seam ending in $A[i, j]$. Let $T(i)$ denote the number of possible seams from row $1$ to row $i$. Then, for $i = 1$, we have $T(i) = n$, and for $i > 1$,

$$T(i) \ge 2T(i - 1).$$

It is easy to guess that $T(i) \ge n2^{n - 1}$, which we verify by direct substitution. For $i = 1$, we have $T(i) = n \ge n \cdot 2^0$. For $i > 1$, we have

$$ \begin{aligned} T(i) & \ge 2T(i - 1) \\ & \ge 2 \cdot n 2^{i - 1} \\ & = n 2^{i - 1}. \end{aligned} $$

Thus, the total number $T(m)$ of seams is at least $n2^{m - 1}$. We conclude that the number of seams grows at least exponentially in $m$.

b. As proved in the previous part, it is infeasible to systematically check every seam, since the number of possible seams grows exponentially.

The structure of the problem allows us to build the solution row by row. Consider a pixel $A[i, j]$. We ask the question: 'If $i$ were the first row of the picture, what is the minimum disruptive measure of seams that start with the pixel $A[i, j]$?'

Let $S^*$ be a seam of minimum disruptive measure among all seams that start with pixel $A[i, j]$. Let $A[i + 1, p]$, where $p \in \{j - 1, j, j + 1\}$, be the pixel of $S^*$ in the next row. Let $S'$ be the sub-seam of $S^*$ that starts with $A[i + 1, p]$. We claim that $S'$ has the minimum disruptive measure among seams that start with $A[i + 1, p]$. Why? Suppose there exists another seam $S''$ that starts with $A[i + 1, p]$ and has disruptive measure less than that of $S'$. By using $S''$ as the sub-seam instead of $S'$, we can obtain another seam that starts with $A[i, j]$ and has a disruptive measure which is less than that of $S^*$. Thus, we obtain a contradiction to our assumption that $S^*$ is a seam of minimum disruptive measure.

Let $disr[i, j]$ be the value of the minimum disruptive measure among all seams that start with pixel $A[i, j]$. For row $m$, the seam with the minimum disruptive measure consists of just one point. We can now state a recurrence for $disr[i, j]$ as follows. In the base case, $disr[m, j] = d[m, j]$ for $j = 1, 2, \ldots, n$. In the recursive case, for $j = 1, 2, \ldots, n$,

$$disr[i, j] = d[i, j] + \min_{k \in K}{dist[i + i, j + k]},$$

where the set $K$ of index offsets is

$$ K = \begin{cases} {0, 1} & \text{if $j = 1$}, \\ {-1, 0, 1} & \text{if $1 < j < m$}, \\ {-1, 0} & \text{if $j = n$}. \end{cases} $$

Since every seam has to start with a pixel of the first row, we simply find the minimum $disr[1, j]$ for pixels in the first row to obtain the minimum disruptive measure.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
COMPRESS-IMAGE(d)
    m = d.rows
    n = d.columns
    let disr[1..m, 1..n] and next[1..m, 1..n] be new tables
    for j = 1 to n
        disr[m, j] = d[m, j]
    for i = m - 1 downto 1
        for j = 1 to n
            low = max(-1, 1 - j)
            high = min(1, n - j)
            disr[i, j] = 
            for k = low to high
                if disr[i + 1, j + k] < disr[i, j]
                    disr[i, j] = disr[i + 1, j + k]
                    next[i, j] = j + k
            disr[i, j] = disr[i, j] + d[i, j]
    val = 
    start = 1
    for j = 1 to n
        if disr[1, j] < val
            val = disr[1, j]
            start = j
    print "The minimum value of the disruptive measure is" val
    for i = 1 to m
        print "cup point at" (i, start)
        start = next[i, start]

The procedure $\text{COMPRESS-IMAGE}$ is simply an implementation of this recurrence in a bottom-up fashion.

We first carry out the initialization of the base cases, which are the cases when row $i = m$. The minimum disruptive measure for the base cases is simply $d[m, j]$.

The next for loop runs down from $m - 1$ to $1$. Thus, $disr[i + 1, j]$ is already available before computing $dist[i, j]$ for pixels of row $i$.

The assignments to $low$ and $high$ allow the index offset $k$ to range over the correct set $K$ from above. We set $low$ to $0$ when $j = 1$ and to $-1$ when $j > 1$, and we set $high$ to $0$ when $j = n$ and to $1$ when $j < n$. The innermost for loop sets $dist[i, j]$ to the minimum value of $disr[i + 1, j + k]$ for all $k \in K$, and the line that follows this loop adds in $d[i, j]$.

We use the $next$ table to reconstruct the actual seam. For a given pixel, it records which pixel was used as the next pixel. Specifically, for a pixel $A[i, j]$, if $next[i, j] = p$, where $p \in {j - 1, j, j + 1}$, then the next pixel of the seam is $A[i + 1, p]$.

The last line of the for loop adds the disruptive measure of the current pixel to the disruptive measure of the seam.

The next for loop finds the minimum disruptive measure of pixels in the first row. We print the minimum disruptive measure as the answer.

The rest of the code reconstructs the actual seam, using the information stored in the $next$ array.

Noting that the innermost for loop runs over at most three values of $k$, we see that the running time of $\text{COMPRESS-IMAGE}$ is $O(mn)$. The space requirement is also $O(mn)$. We can improve upon the space requirement by observing that row $i$ of the $disr$ table depends on only row $i + 1$. Therefore, we can store just two rows at any time. Thus, we can improve the space requirement of $\text{COMPRESS-IMAGE}$ to $O(n)$.