SEAMCARVING
BEFORE
AFTER

Based on 3blue1brown's video on Seam Carving.

This project extends 3blue1brown's video by implementing the algorithm in Python and C++. It also features more advanced performance optimizations.

For the complete code see GitHub.

What is Seam Carving?

Seam carving is a image resizing algorithm that resizes images without distorting the important parts of the image. It does this by removing the least important pixels in the image.

How does it work??

  1. Calculate the energy of each pixel in the image.
    1. Use Sobel filter to calculate the edges in the image.
    2. Generate an energy map by giving each pixel an importance score.
  2. Find the seam with the lowest energy.
  3. Remove the seam.
  4. Repeat until the image is the desired size.

Implementation in Python and C++

1. Calculate the energy of each pixel in the image.

We first grayscale the image and scale it to a range of 0 to 1:

python 
def rgb2gray(rgb):
    r, g, b = rgb[:,:,0], rgb[:,:,1], rgb[:,:,2]
    gray = 0.2989 * r + 0.5870 * g + 0.1140 * b
    return gray/255 # scale to 0-1

Then we calculate the energy of each pixel using the sobel filter:

python 
def imageKernel(img):
    img = rgb2gray(img)
    dx = ndimage.sobel(img, 0)  # horizontal derivative
    dy = ndimage.sobel(img, 1)  # vertical derivative
    mag = np.hypot(dx, dy)  # magnitude
    mag *= 255.0 / np.max(mag)  # normalize (Q&D)
    return mag

with corresponding kernels for the self-written implementation:

python 
sobelXYImg = imageKernel(greyImg)
plt.imshow(sobelXYImg,cmap='gray')

This works by simply applying the kernel to each pixel in the image and results in the following images:

Sobel X
Sobel Y

We then combine the two images by calculating the magnitude of the two images:

Sobel XY
Sobel XY (abs)

2. Create an energy map

We then create an energy map by giving each pixel an importance score. This is done by going through the image from bottom to top and giving each pixel the value of the lowest energy pixel below it plus its own energy.

python 
def getEnergyMap(image):
    ySize, xSize = image.shape[:2]
    energyMap = np.zeros(image.shape)

    # lowest row   
    energyMap[0] = image[0]
    
    # from bottom to top
    for y in reversed(range(ySize-1)):
        for x in range(xSize):
            # middle
            best = energyMap[y+1][x]
            # left
            if x>0:
                if energyMap[y+1][x-1] < best:
                    best = energyMap[y+1][x-1]
            #right
            if x<xSize-1:
                if energyMap[y+1][x+1] < best:
                    best = energyMap[y+1][x+1]
                
            energyMap[y][x] = best + image[y][x]
    return energyMap

We can call this function with the sobel image as input:

python 
energyMap = getEnergyMap(sobelXYImg)
plt.imshow(energyMap,cmap='gray',vmin = 0,vmax =5)

3. Find the seam with the lowest energy

We can find the seam with the lowest energy by finding the lowest energy pixel in the top row. Then we can trace the path of the lowest energy pixels from top to bottom.

python 
def greedyPath(image):
    height, width = image.shape[:2]
    minVal = image[0].argmin()
    path = [minVal]
    for y in range(1,height):
        lastPosX = path[y-1]
        nextValues = []
        # left
        if lastPosX > 0:
            nextValues.append(image[y][lastPosX-1])
        # mid
        nextValues.append(image[y][lastPosX])
        # right
        if lastPosX < width-1:
            nextValues.append(image[y][lastPosX+1])
        # find smallest
        minVal = np.argmin(nextValues)
        path.append(minVal+lastPosX-1)
    return path

We can then visualize the path by coloring the pixels in the path:

python 
def DEBUG_PrintImageWithPath(image,path):
    xSize = len(image[0])
    ySize = len(image)
    resImg = [[0 for x in range(xSize)] for y in range(ySize)] 
    for y in range(ySize):
        for x in range(xSize):
            if path[y] == x:
                resImg[y][x] = [255,255,255]
            else:
                resImg[y][x] = image[y][x]
    plt.imshow(resImg)

4. Remove the seam
python 
def deletePath(image,path):
    xSize = len(image[0])
    ySize = len(image)
    newImage = [[0 for x in range(xSize-1)] for y in range(ySize)] 
    for y in range(ySize):
        nx = -1
        for x in range(xSize-1):
            nx+=1
            if path[y] == nx:
                nx +=1
            newImage[y][x] = image[y][nx]
    return newImage

5. Repeat until the image is the desired size

We can repeat the previous steps until the image is the desired size

python 
N = 100
origImg = img
for i in range(N):
    origGreyImg = GreyScale(origImg)
    XImg = imageKernel(origGreyImg,sobelX)
    YImg = imageKernel(origGreyImg,sobelY)
    XYimg = np.array(XImg) + np.array(YImg)
    XYimg = np.abs(XYimg)
    ener = getEnergyMap(XYimg)
    path = greedyPath(ener)
    origImg = deletePath(origImg,path)

plt.subplots(1, figsize=figsize)
plt.imshow(origImg,vmin = 0,vmax =1)
plt.show()

Performance Optimizations

This implementation is very slow. Instead of calculating the grey image, sobel kernels and energy map every iteration, it is possible to calculate them once and then only update the energy map and path.

python 
N = 100
origImg = img
origGreyImg = GreyScale(origImg)
XImg = imageKernel(origGreyImg,sobelX)
XImg = np.abs(np.array(XImg))
YImg = imageKernel(origGreyImg,sobelY)
YImg = np.abs(np.array(YImg))
XYIMG = np.array(XImg) + np.array(YImg)
for i in range(N):
    ener = getEnergyMap(XYIMG)
    path = greedyPath2(np.array(ener))
    origImg = deletePath(origImg,path)
    if i+1 != N:
        XYIMG = deletePath(XYIMG,path)

plt.subplots(1, figsize=figsize)
plt.imshow(origImg,vmin = 0,vmax =1)

The results may slightly differ but the performance is much better as we only have to compute the path and not much more. The old implementation took 2min for 100 iterations while the new implementation only took 1min.