📘

Contour Smoothing via Dynamic Programming (1D)

MediumDynamic Programming, Image Processing 📚 CV - 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:

For each target label k:
Sₙ(-1) = U(-1) + min{S_{n-1}(-1)+0, S_{n-1}(0)+1, S_{n-1}(1)+2}
- = 2.0 + min{3.0, 3.0, 6.0} = 2.0 + 3.0 = 5.0
Sₙ(0) = U(0) + min{S_{n-1}(-1)+1, S_{n-1}(0)+0, S_{n-1}(1)+1}
- = 1.0 + min{4.0, 2.0, 5.0} = 1.0 + 2.0 = 3.0
Sₙ(1) = U(1) + min{S_{n-1}(-1)+2, S_{n-1}(0)+1, S_{n-1}(1)+0}
- = 5.0 + min{5.0, 3.0, 4.0} = 5.0 + 3.0 = 8.0

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

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

👑

Continue the full explanation

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

🔒

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

0/0

Run code to see test results.