Seam Carving an image using Dijkstra algorithm in C++

Question

I am trying to implement Seam carving using Dijkstra's algorithm.

So far, I have converted the image to grayscale and using a 2D array, I've found out the energy function of the image. Now, to implement Dijkstra, I need to convert this 2D array into a graph and give a source and sink to the Dijsktra function.

I would like to know how to change this 2D array into a graph, as the 2D array, being a matrix of MxN, where M,N both can be very huge numbers, could give rise to possibly a huge number of graphs possible, and decide the sink for it.

Answer 1

You don't have to convert the image into a graph. All you have to do is use dynamic programming for computing seams and then finding the the seam with the minimum energy. To be more precise, to calculate S[i,j] (seam for pixel (i,j)):

1. For the first row, assign the energy value as seam value of the pixels S[1,j] = E[1,j]

2. For the next rows, propagate the minimum seam from the neighbors of the pixel downwards: S[i,j] = E[i,j] + min( S[i-1,j-1], S[i-1,j], S[i-1,j+1] )

3. Start from the element with minimum value in the last row of S and climb up by choosing neighbors with minimum seam values. Store each step.

4. The path you have stored is the seam with minimum energy.

I've also find a nice article with explains thoroughly the algorithm with MATLAB source code:

https://kirilllykov.github.io/blog/2013/06/06/seam-carving-algorithm/