Lauren Smith

October 14, 2010

CS342

 

Seam Carving

 

For this assignment,  we implemented Seam Carving.  This program finds an optimal path of pixels, either horizontal or vertical, through an image.  This seam is calculated based on the gradient of the pixels, allowing us to resize the image intelligently, retargeting the image based on the content.

 

Beginning with the given skeleton code, we began by finding horizontal seams using the gradient function.  Once the seam was found, we removed each pixel of the seam by shifting up those below it and cropping off the bottom of the image.  This shrinks the image heightwise.  To locate vertical seams, we simply rotated the image by 90 degrees and ran the horizontal seam code.  Then, before displaying the image, the image must be rotated another 270 degrees to get it back to the original orientation.

 

Results:

 

Vertical Seam Carving:  (Removing 200 seams)

 

Original Image                                                                       Retargeted Image

 

 

 

 

 

 

 

 

 

 

Horizontal Seam Carving:

 

 

 

 

 

 

 

 

 

 

 

 

Images with people:

(Clockwise from top left:  Original, Vertical Seams, Horizontal Seams

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Conclusion: 

For most landscapes, the vertical seam removal was most effective.  It seems that since the most natural seams run from top to bottom, it was easy to remove those without too much distortion in the resulting images.  I believe this is due to the horizon, i.e., those involving the ocean would have a bit of the ocean in each seam, instead of horizontal seams which would be either all ocean water or all sky.  As seen in the palm tree horizontal seam photo, the seams through the sky were chosen for removal since they’re most similar.  Usually, this would be the best idea, but in this image, it essentially cropped off the top.

For the images with people, the success was not so great.  In these photos, the background was especially textured, like rocky cliffs and abandoned pirate ships.  These seams will not be chosen, especially when the human skin is much more uniform.  For this reason, the people in the photos end up extremely distorted and look pretty foolish.  Perhaps on a smooth background surface, this will run better.

 

 

 

 

 

Code:

 

function [J] = seamRemove(I, n, isVertical)

im = I;

%keep a record of number of seams to remove (since n is decreased later)

numremove = n;

 

im = im2double(im);

%save a copy of the original image

firstim = im;

%get dimensions of image

[H,W,D] = size(im);

img = rgb2gray(im);

[fx, fy] = gradient(img);

cmap = abs(fx) + abs(fy);

 

%to find horizontal seams:

if isVertical == 0

   

    %find seam and remove seam, numremove times

    for remloop = 1 : numremove

        [H,W,D] = size(im);

        img = rgb2gray(im);

        [fx, fy] = gradient(img);

        cmap = abs(fx) + abs(fy);

        prev_node = ones(H-2,W)*2;

        ac_im = ones(H,W);

        ac_im(1:H,1) = cmap(1:H,1);

        ac_im(1,:) = 1000;

        ac_im(H,:) = 1000;

       

        %find seam

        for n = 2 : W

            s1 = cmap(2:H-1,n) + ac_im(1:H-2, n-1);

            s2 = cmap(2:H-1,n) + ac_im(2:H-1, n-1);

            s3 = cmap(2:H-1,n) + ac_im(3:H, n-1);

            s = [s1, s2, s3];

            [t, id] = min(s, [], 2);

            prev_node(:,n) = id;

            ac_im(2:H-1,n) = t;

        end

       

        prev_node(prev_node == 1) = -1;

        prev_node(prev_node == 2) = 0;

        prev_node(prev_node == 3) = 1;

       

        sline = [];

        [t, id] = min(ac_im(2:H-1, W));

        sline = [id+1, sline];

        im(id+1:H-1,W,:) = im(id+2:H,W,:);

        cmap(id+1:H-1,W,:) = cmap(id+2:H,W,:);

       

        for n = W-1 : -1 : 1

           

            id = id + prev_node(id, n);

            sline = [id+1, sline];

        end

       

        % remove seams:

        % follow values in s and shift matrix up at each location

        for i = 1 : W

            im(sline(i):H-1, i,:)  = im(sline(i)+1:H, i,:);

        end

        %crop bottom off and repeat

        im = im(1:H-1, :, :);

    end

    J = im;

end

%to find vertical seams:

if isVertical == 1

    % rotate image by 90 degrees and implement horizontal seaming

    R = rot90(im(:,:,1));

    G = rot90(im(:,:,2));

    B = rot90(im(:,:,3));

    im = R;

    im(:,:,2) = G;

    im(:,:,3) = B;

   

    for remloop = 1 : numremove

        %recalculate dimensions after cropping image

        [H,W,D] = size(im);

        img = rgb2gray(im);

        [fx, fy] = gradient(img);

        cmap = abs(fx) + abs(fy);

       

        prev_node = ones(H-2,W)*2;

        ac_im = ones(H,W);

        ac_im(1:H,1) = cmap(1:H,1);

        ac_im(1,:) = 1000;

        ac_im(H,:) = 1000;

       

        for n = 2 : W

            s1 = cmap(2:H-1,n) + ac_im(1:H-2, n-1);

            s2 = cmap(2:H-1,n) + ac_im(2:H-1, n-1);

            s3 = cmap(2:H-1,n) + ac_im(3:H, n-1);

            s = [s1, s2, s3];

            [t, id] = min(s, [], 2);

            prev_node(:,n) = id;

            ac_im(2:H-1,n) = t;

        end

       

        prev_node(prev_node == 1) = -1;

        prev_node(prev_node == 2) = 0;

        prev_node(prev_node == 3) = 1;

       

        sline = [];

        [t, id] = min(ac_im(2:H-1, W));

        sline = [id+1, sline];

        im(id+1:H-1,W,:) = im(id+2:H,W,:);

        cmap(id+1:H-1,W,:) = cmap(id+2:H,W,:);

       

        for n = W-1 : -1 : 1

            id = id + prev_node(id, n);

            sline = [id+1, sline];

        end

        %remove seams

        for i = 1 : W

            im(sline(i):H-1, i,:)  = im(sline(i)+1:H, i,:);

        end

        %crop bottom

        im = im(1:H-1, :, :);

    end

    %rotate image 270 degrees back to original orientation

    R = rot90(im(:,:,1));

    G = rot90(im(:,:,2));

    B = rot90(im(:,:,3));

    R = rot90(R);

    G = rot90(G);

    B = rot90(B);

    R = rot90(R);

    G = rot90(G);

    B = rot90(B);

   

    im = R;

    im(:,:,2) = G;

    im(:,:,3) = B;

    

    J = im;

end

imshow(im);