• amit

    Very nice explaination. Can you please elaborate on the last equation T(r,c), specially the cost function and how to remove a seam (veritical/horizontal)

    • Eric

      Hey Amit!

      Concerning that T(r, c) equation, I meant, for an image, with initial size(n*m), we want remove r rows and c columns, and make it a new image which has size(n-r, m-c). In this situation, we want optimize our algo by minimizing the cost. For a certain step, we want to know whether to remove a column or a row, we make the decision by comparing the costs and choose the lower cost step (and the T(r, c) equation is just the reverse statement of the above move).

      With regard to remove a seam, let’s assume we’re going to remove a line, say, a column. By the gradient calculations, we already have the energy map of the image, so as I mentioned in the post, the problem changes into a dynamic programming problem.

      From the upper most row, we build a matrix downward, for each pixel, we do: (We define ‘val’ to be the value of each pixel in this new matrix, it is not the actual grayscale value.)
      1. Find minof (thispixel.upperleft.val, thispixel.upper.val, thispixel.upperright.val), and let this pixel’s path to be the one which have min val.
      2. Set this pixel’s val to be its path’s val + the grayscale value of itself.
      After building this matrix, we can find a min cost path by find min val in the last row of matrix, retrieve and get this path, the pixels in this path are exactly the pixels we wanna remove.

      Hope the above explanation helps. If you have any question, feel free to let me know. Thanks!


      • amit

        Great explanation once again :)if i got it right you are traversing downward and setting the “val” of each pixel as
        val (i,j) = min ( val(i-1,j-1,) val(i,j-i), val(i+1,j-1)).
        what will be the values for the top most row which will be pre filled. (i guess those will be zero).
        Also do i need to recompute this matrix everytime i want to delete a row or col. or only one time comoutation can be used later for any number of rows/cols removal.

        • Eric

          Hey Amit,

          1. For the top most row, I used exactly the grayscale value as the value, of course, it’s OK to use zero.
          2. I re-compute this matrix every time, because I think after delete each certain single row/col, we are dealing with a new image. I did try to do that only once, and delete rows using the ranked path, but when doing that, I found some pixels in the path I was going to delete has already deleted by previous process, means paths share pixels.
          It’s truly an expensive method, but maybe there is better way, so please tell me if you find some way cheaper.

          Have a good day!