Contour Smoothing via Dynamic Programming (1D)

mediumPROGraphsDynamic Programming, Image ProcessingCV - DSA

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|$

Example

Input

Unary: [2.0, 1.0, 5.0], Cumulative: [3.0, 2.0, 4.0]

Output

[5.000, 3.000, 8.000]

Reasoning

Inputs: unary_costs_un is $U_n = (2, 1, 5)$ , the data cost of label $-1$ , $0$ or $1$ ; cumulative_costs_sn_1 is $S_{n-1} = (3, 2, 4)$ , the cheapest contour cost so far ending in each label at the previous pixel.
Label $k=-1$ : the candidates $S_{n-1,l} + |k-l|$ are $3+0,\ 2+1,\ 4+2 = 3, 3, 6$ . The best is $3$ (a tie between staying at $-1$ and arriving from $0$ ), so $S_{n,-1} = 2 + 3 = 5$ .
Label $k=0$ : $3+1,\ 2+0,\ 4+1 = 4, 2, 5$ . The best is $2$ , so $S_{n,0} = 1 + 2 = 3$ .
Label $k=1$ : $3+2,\ 2+1,\ 4+0 = 5, 3, 4$ . The best is $3$ , so $S_{n,1} = 5 + 3 = 8$ .
Output: [5.000, 3.000, 8.000], one cumulative cost per label in the order $-1, 0, 1$ , rounded to 3 decimal places. Notice label $1$ prefers to arrive from label $0$ : a smoothness penalty of $1$ is worth paying because the previous cost there is $2$ lower than staying put.

Constraints

The possible labels are k ∈ {-1, 0, 1}
The smoothness cost P_{n,n-1} is defined by |k - l|
Uₙ and S_{n-1} are provided as lists indexed by [-1, 0, 1]
Output costs must be rounded to 3 decimal places

More from CV - DSA

Concept primerPREVIEW

Contour Smoothing via Dynamic Programming: Comprehensive Background

1. Background Knowledge

Active Contour Models (Snakes)

Active contours are curves that evolve to fit image features while maintaining smoothness constraints. They minimize an energy functional combining:

Data fidelity: How well the contour aligns with image edges or features
Smoothness regularization: Penalizing sharp bends or discontinuities

This framework is widely used in medical image segmentation and contour extraction.

Dynamic Programming Fundamentals

Dynamic Programming (DP) solves optimization problems by breaking them into overlapping subproblems and storing intermediate results. Key principles:

Optimal substructure: The optimal solution contains optimal solutions to subproblems
Memoization: Store computed results to avoid redundant calculations
Bottom-up computation: Build solutions from base cases forward

For contour problems, DP finds the minimum-cost path through a chain graph where:

Each position $n$ has multiple possible states (labels $k$ )
Transitions between adjacent positions incur costs
The goal is to find the globally optimal sequence of labels

The Viterbi Algorithm

The Viterbi algorithm is a DP method for finding the maximum likelihood path in Hidden Markov Models (HMMs). It generalizes to finding minimum-cost paths in chain-structured graphs:

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

This recurrence ensures that the cost at each position incorporates:

The unary cost of the current label
The minimum cost from all possible previous labels, including transition penalties

Energy Minimization in Image Processing

The total cost function combines two terms:

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

Unary term $U_n$ : Data attachment (e.g., distance to edges, image intensity)
Pairwise term $P_{n,n-1}$ : Smoothness constraint (e.g., $\ell_1$ or $\ell_2$ norm of label differences)

The $\ell_1$ norm $|k - l|$ penalizes label changes proportionally to their magnitude, encouraging smooth transitions.

2. Algorithm Approach

Viterbi Algorithm for Chain Graphs

The algorithm operates in two phases:

Forward Pass (DP computation):

Initialize $S_{0,k}$ with base costs
For each position $n = 1, 2, \ldots, N$ :

For each label $k$ :
Compute $S_{n,k}$ by finding the minimum over all previous labels $l$

Track backpointers to reconstruct the optimal path

Backward Pass (Path reconstruction):

Starting from the final position, follow backpointers to recover the optimal label sequence

Why DP Works Here

State space: $O(n \times k)$ where $n$ is sequence length and $k$ is number of labels
Transitions: Each state connects to all previous states (dense transitions)
Acyclic structure: Chain graphs have no cycles, enabling DP

3. Step-by-Step Strategy

Step 1: Understand the Input Format

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results