How do you find and remove a seam when doing seam carving in Python for image processing?

Posted on 2014-10-26
Last Modified: 2014-10-28
I am implementing the seam carving algorithm in Python, which is used to resize and manipulate images.

See the following links for an explanation of the seam carving algorithm:

The dual_gradient_energy function computes the energy of each pixel of the image.

I am trying to find the horizontal seam of the image.

The function is supposed to return an array of H (height) integers. For each row, it should return the column of the seam.

I am unable to get the find_seam function to work. Instead of returning pixels in integers, the values being returned in the array are in scientific notation. I made sure to check boundary cases so that it does not fill an array with an invalid/nonexistent element.

Plot_seam should plot the seam on the image and highlight it in red. I have it implemented already, but I have not been able to test it since there is no seam to plot. Once the find_seam function is fixed, then a seam can be plotted.

Remove_seam function modifies the image in-place and returns a W-1 (width) x H x 3 (height) slice. In essence, it removes the seam from the image. I am having trouble implementing this because the array indices seem to be out of bounds.

I have provided an image (someimage.png) to use for testing the functions.

I am using Python 2.7.

Required Python libraries (for Windows 32-bit):


What is wrong with my find_seam and remove_seam functions? How can I fix my code?

Note: You may need to close the graph that is generated when you run the source code in order to see the find_seam, plot_seam, and remove_seam function calls.

See my code below:

import numpy
import scipy.misc as scm
from pylab import *
from scipy import ndimage
from skimage import img_as_float, filter

def dual_gradient_energy(img):
    R = img[:, :, 0]
    G = img[:, :, 1]
    B = img[:, :, 2]
    hColorR = filter.hsobel(R)
    vColorR = filter.vsobel(R)
    hColorG = filter.hsobel(G)
    vColorG = filter.vsobel(G)
    hColorB = filter.hsobel(B)
    vColorB = filter.vsobel(B)

    energyArr = hColorR*hColorR+vColorR*vColorR+hColorG*hColorG+vColorG*vColorG+hColorB*hColorB+vColorB*vColorB

    return energyArr

def find_seam(img):

    height,width = img.shape[:2]
    seamFitness = dual_gradient_energy(img)

    #for i in range(0, width):
        #seamFitness[0][i] = img[0][i]
    for x in range(0, width-2):
        for y in range (1, height-2):
                #seamFitness[x][y] = img[x][y]
            if (x>0) and (x<width) and (y==0):
                seamFitness[x][y] += min(seamFitness[x][y-1], seamFitness[x+1][y-1])
                if (x>0) and (x == width-1):
                    seamFitness[x][y] += min(seamFitness[x][y-1], seamFitness[x-1][y-1])
                    if (x!=0):
                        seamFitness[x][y] += min(seamFitness[x-1][y-1], seamFitness[x][y-1], seamFitness[x+1][y-1])

    return seamFitness[y]

def remove_seam(img,seam):
    attempt = 0
    i = 0
    height,width = img.shape[:2]
    seamFitness = np.zeros((height, width))
    for attempt in range(attempt, img.size):
        bestRow = 0
        for i in range(i, height-img.size):
            if (seamFitness[width-1][bestRow] > seamFitness[width-1][i]):
                bestRow = i
    x = width-1
    if (x > 0):
        theMin = seamFitness[x-1][bestRow]
    if (bestRow > 0 and seamFitness[x-1][bestRow-1] <= theMin):
        bestRow = bestRow-1
    elif (bestRow < height-1 and seamFitness[x-1][bestRow+1] <= theMin):
        bestRow = bestRow+1
    return img

def plot_seam(img, seam):
    height,width,dim = img.shape
    for i in xrange(0,len(seam)):
        img[i][seam[i]][0] = 255
        img[i][seam[i]][1] = 0
        img[i][seam[i]][2] = 0

def main():
    img = imread('someimage.png')
    img = img_as_float(img)
    l=dual_gradient_energy(img) #works!
    r = find_seam(img)
    print r
    s = remove_seam(img, r)
    imshow(plot_seam(img, r))

if __name__ == '__main__':

Open in new window
Question by:AttilaB
1 Comment
LVL 45

Accepted Solution

aikimark earned 500 total points
ID: 40406953
I would expect a floating point result, based on the definition of the energy gradient formula definition.  If you need integer results, cast the floating-point values into integer values.

I was curious why your x and y for loops have different starting values and (relative) different ending values.

btw...I'm a big fan of this algorithm and, generally, context sensitive resizing.

Featured Post

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

I. Introduction In a previous article ( (now deprecated), I discussed how to upgrad…
In a previous article published here at Experts Exchange, Signature Image with Transparent Background (, I explained how to cre…
Learn the basics of while and for loops in Python.  while loops are used for testing while, or until, a condition is met: The structure of a while loop is as follows:     while <condition>:         do something         repeate: The break statement m…
The goal of the tutorial is to teach the user how to make his/her own presets while editing so it is easier to edit there photos. Create a preset you like and copy that setting then save it in to your presets folder.

679 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question