Tag Archives: Seam Carving

Examples of Dynamic Programming with C++ and Matlab

In this tutorial, I will give you examples of using dynamic programming for solving the following problems:

1)Minimum number of coins for summing X.

 

2)The most (least) costly path on a grid (dynamic time warping).

 

3)Levenshtein edit distance.

 

4)Seam Carving. I have written a tutorial on that here and the recursive part is in the following lines:

 

The examples are taken from “Competitive Programmer’s Handbook” written by Antti Laaksonen.

Seam Carving Algorithm for Content-Aware Image Resizing with Matlab Code

Seam carving is an algorithm for resizing images while keeping the most prominent and conspicuous pixels in the image. The important pixels in an image are usually those who are located over horizontal or vertical edges, so to throw away some pixels we first find horizontal and vertical edges and store their magnitude as pixel energy. Then we use dynamic programming to find a path which contains the minimum energy level and we drop those pixels. We iteratively do this until we got our image in the desired size.

our image is 720×480,

let’s drop some rows and resize it to 640×480:

we can drop some columns and resize it to 720×320: