Contour Smoothing via Dynamic Programming (1D)

Problem Statement

Active Contour Models (Snakes) or Dynamic Time Warping techniques often use Dynamic Programming (DP) to minimize an energy function across a sequence of points. This is equivalent to finding the minimum cost path in a chain graph.

Problem Setup

We consider a simplified 1D contour segmentation problem represented by a chain of pixels $w_1, w_2, \ldots, w_n$, where $w_n \in \{-1, 0, 1\}$ represents the relative vertical shift of the contour at position $n$.

The total cost $S$ of a contour assignment $w$ is:

$S(w) = \sum_n U_n(w_n) + \sum_n P_{n,n-1}(w_n, w_{n-1})$

where:

• $U_n$ is the unary cost (e.g., closeness to an edge/data likelihood)
• $P_{n,n-1}$ is the pairwise cost (smoothness)

Your Task

Implement the core recurrence relation of the DP solution (Viterbi algorithm) to find the minimum cumulative cost $S_{n,k}$ of reaching pixel $n$ with label $k$:

$S_{n,k} = U_n(w_n = k) + \min_l [S_{n-1,l} + P_{n,n-1}(w_n = k, w_{n-1} = l)]$

Given the cumulative costs $S_{n-1}$ for the previous column and the costs $U_n$, calculate the minimum cumulative costs $S_n$ for the current column.

Pairwise Cost

The smoothness cost $P_{n,n-1}$ is defined by the ℓ₁ norm (Manhattan distance) between adjacent labels:

$P_{n,n-1}(k, l) = |k - l|$