In last week Computational Photography class, Rob showed us a video about seam carving, which is really awesome, like magic. During my last bachelor year, I published a paper with my group named “Semantic aware sport image resizing jointly using seam carving and warping”, I worked for the sport image field detection part. So when I saw this video, I was engaged, thinking that I’m going to try seam carving this time!

I thought seam carving is too hard to try for years until I read the wiki page of seam carving, actually the basic part of this algorithm is really simple, and with help of OpenCV, I can easily get the gradient map of a picture, so let’s do it.

Why we need seam carving?

If we need to resize a picture, usually what we do is simply scaling a picture like this:

But problem raises, if the scale we change vertical and the scale we change horizontal is different, then the result will be some kind of odd, and in this case, seam carving is a good method to deal with it.

Generally what this method do is finding the most unimportant, or, least energy seams(paths) in image, and deletes these seams to reduce image size or inserts new pixels beside these seams to extend the size of image.

First let’s pick a input image, for example the one above.

And using OpenCV, let get its gradient map as the energy map

// Gradient X Sobel( gray, grad_x, ddepth, 1, 0, 3, scale, delta, BORDER_DEFAULT ); convertScaleAbs( grad_x, abs_grad_x ); // Gradient Y Sobel( gray, grad_y, ddepth, 0, 1, 3, scale, delta, BORDER_DEFAULT ); convertScaleAbs( grad_y, abs_grad_y ); addWeighted( abs_grad_x, 0.5, abs_grad_y, 0.5, 0, grad );

The gradient map measures areas that the pixel values changes a lot, that is, area which including more information. It is one of many ways (maybe the most simple way) to measure the energy of pixels, it’s just contrast each pixel with its neighbor pixels, and see the difference between them.

Now I have two methods to reach the goal.

**Dynamic Programming method**:

Assuming we are going to cut one column from a m-width * n-height image.

#define LEFT -1 #define MID 0 #define RIGHT 1 //define a struct like this typedef struct _Node{ long data; int path; }node; //function returns which is min (not min value, but which is min) int which_min(x, y){ if(min(x,y)==x){ return 0; } else{ return 1; } } int which_min(x, y, z){ if(min(x,y,z)==x){ return 0; } elif((min(x,y,z)==y){ return 1; } else{ return 2; } } build a table with node, width is m, and height is n; init whole table with value 0; int t=0; for j=0: height{ for i=0: width{ if(j==0){ //I used gradient map as my energy map. table[i][j].data = energy[i][j]; table[i][j].path = 0; } else{ //most left col, have no upper-left pixel if(i==0){ t = which_min(table[i+MID][j-1].data, table[i+RIGHT][j-1].data); table[i][j].data = energy[i][j] + table[i+MID+t][j-1].data; table[i][j].path = MID+t; } //most right col, have no upper-right pixel elif(i==width-1){ t = which_min(table[i+LEFT][j-1].data, table[i+MID][j-1].data); table[i][j].data = energy[i][j] + table[i+LEFT+t][j-1].data; table[i][j].path = LEFT+t; } else{ t = which_min(table[i+LEFT][j-1].data, table[i+MID][j-1].data, table[i+RIGHT][j-1].data); table[i][j].data = energy[i][j] + table[i+LEFT+t][j-1].data; table[i][j].path = LEFT+t; } } } } sum = copyfrom(table( :height-1)); //now use any sort method to sort the sum array sum = Sort(sum); //and now sum[0] is the min seam energy. path = FindPath(sum[0]);

**Random Walking method**:

Jeky taught me this method yesterday.

typedef struct _pixel{ int value; int x; int y; }pixel; random_walk(){ vector< pixel> path; //first randomly choose a pixel in first row. path[0].x=random_choose(0,width-1); path[0].y=0; path[0].value=energy[x][y]; for(int i=1; i< width-1; i++){ //for each row except first row, //randomly choose a pixel among: //left-down, down, right-down pixels of the pixel of prior row. } return(path); } for (j=0; j< many_times; j++){ path = random_walk(energy); if(!path.empty()){ if(j==0){ bestpath = path; } else{ if(PathValue(path)< PathValue(bestpath)){ bestpath = path; } } } path.clear(); }

This algorithm is based on random walk theory in mathematics. The quality of the best seam you found is related to how many times you tried randomly, and I used the amount of pixels in a row as that “many_times”, and the result is not bad.

If we want cut a lot of seams off, both vertical and horizontal, we must think about the order we cut off those seams, although this can be achieved by first removing vertical seams followed by removal of horizontal seams, but this strategy may not be the optimal order. The optimal order of seam removal is found using dynamic programming.

Assume that we want to resize a (n*m) image to (n’*m’) image where n'<=n and m'<=m.

Let **T(r,c)** denote the cost of obtaining an image of size **(n-r) * (m-c)**. We can arrive at an image of these dimensions by either removing a horizontal seam from an image of dimensions** (n-r+1) * (m-c)** or removing a vertical seam from an image of size **(n-r) * (m-c+1)**.

So for each time,

**T(r,c) = min(T(r-1,c) + E((n-r+1)(m-c)), T(r,c-1) + E((n-r)(m-c+1)));**

In which, **E(a,b)** denotes the cost of removing seam from an image** I(a,b)**.

**Some of tests:**

this is cutting 300 columns from the above image, seams are painted red.

resize this 640*474 bubble image to 320*250.

resize this 1920*1080 beach image to 800*662. And we can see that the divide between sea and sky is sort of strange, but the logo at bottom-right persists nice.

At the end, let’s try the picture on seam carving wiki page, let’s cut 800 columns off.

🙂