Lauren Smith

October 25, 2010

CS342

 

Seam Carving for Image Enlargement and Object Removal

 


For part II of Assignment 2, the task was to use the idea of finding seams to accurately enlarge a photo by increasing along optimal seams in the image.  Building off of the Seam Carving code, we implemented a new program to insert any number of seams either horizontally or vertically.  These seams are intelligently inserted, based on the content of the image, ideally to places where it would be less noticeable – thus preserving the content of the image but providing a larger size.

 

Using the code developed last week, we had to create a way to repeatedly find the seams in optimal order.  The reason for this is because if we continually found the best seam and added the average between it and the entries below it, over time it would take the appearance of just a repeated row or column of pixels, without looking aesthetically pleasing.  For this reason, we found it best to remove the seams as the previous assignment, but save then in an array.  Then, we could add them back in to their location and also add in a similar second seam to enlarge the photo.

 

To modify the code to allow for object removal, we utilized the Matlab function roipoly(), which allows user input to select a polygon of interest.  After selecting a region, we created a mask, mapping the image as all zeros except for the designated region as ones.  By applying this mask to the original image, we marked the ROI in the image as zeros to encourage these pixels to be carved out.  Here was an interesting problem though, we couldn’t actually change the pixels in case there weren’t enough seams to carve out the entire region.  Thus we had to keep track the region in one image, but perform the actual seam carving in a duplicate image.  Once the region was artificially marked as less important, the code from the previous week would select out the marked region and produce an image without the object, as desired.

 

Results

 

Image Enlargement:

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

 

 

   

 

 

   

 

 

   

 

 

  

 

 

(Below:  Clockwise from upper left:  Original, Add 80 Vertical Seams, Add 180 Vertical Seams, Add 80 Horizontal Seams)

 

       

 

  

 


Object Removal:

(Left to Right:  Original, Removed)

 

  

 

  

 

 

Conclusion:

 

As evident in the photos included, this method worked pretty well.  Similar to the last assignment, this was most effective on landscapes.  The image with the Barcelona Team demonstrates that adding seams to objects of known size (i.e. the human body) is more discernable versus adding them to scenic landscapes.  This is evident as each of the players seem to have gained a little weight with the vertical seams added.  Regardless, in the landscape photos there are some abnormalities noticeable, like the tree photo or the man under the arch.  Overall though, these results are pretty effective way to enlarge an image while preserving the content.

 

The object removal also worked well.  As seen in the photos above, we were able to remove two individuals from the scenes, leaving a pretty much unchanged image otherwise.  We noticed better results by selecting a region especially tall (in the vertical seam direction) or extra wide (to remove horizontal seams).  This would encourage the program to remove the “right” seams by boosting up the number of zero pixels in the region.  Overall, both programs ran pretty quickly for smaller pictures and not too slow for larger photos.  Decreasing the time complexity would be optimal for the future.

 

 

Code:

 

Seam Insertion:

 

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

im = I;

%save a copy of the number of seams to remove (since n is used later)

numremove = n;

im = im2double(im);

%save a copy of the original image

firstim = im;

%get size of image

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

originalh = H;

originalw = W;

img = rgb2gray(im);

[fx, fy] = gradient(img);

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

%if the seaming is horizontal

if isVertical == 0

    %create array for list of seams

    slinearray = zeros(numremove, W);

   

    %repeat 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

        % to remove seams, follow values in s and shift matrix up at each

        % location

        % newimage = zeros(H+1, W);

        for i = 1 : W

            % im(sline(i):H, i, :);

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

        end

        % crop bottom

        slinearray(remloop, :) = sline;

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

    end

    J = im;

   

    %for each seam, find the average it and the entry above it, and insert

    %another seam in to enlarge the image

    for p = 1: numremove

        [h,w] = size(firstim);

        originalh = h;

        %originalw = w;

        cim = zeros(originalh+1, originalw, 3);

        sline = slinearray(p,:);

        for i = 1 : originalw

            sval = sline(i) + p - 1;

            avg = zeros(1,1,3);

            avg = firstim(sval,i, :);

            avg = avg + firstim(sval - 1, i, :);

            avg = avg / 2;

            cim(1:sval, i, :) = firstim(1:sval, i, :);

            cim(sval+1, i, :) = avg;

            cim(sval+2: originalh+1, i, :) = firstim(sval + 1: originalh, i, :);

        end

        firstim = cim;

    end

    im = firstim;

end

if isVertical == 1

    % rotate image by 90 degrees

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

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

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

    im = R;

    im(:,:,2) = G;

    im(:,:,3) = B;

    firstim = im;

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

    slinearray = zeros(numremove, W);

    for remloop = 1 : numremove

        %recalculate dimensions after cropped image

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

        originalw = W;

        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

        size(sline);

        %remove seams

        % remove seams

        % to 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

        slinearray(remloop, :) = sline;

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

    end

   

   

    %for each seam, find the average it and the entry above it, and insert

    %another seam in to enlarge the image

    for p = 1: numremove

        [h,w] = size(firstim);

        originalh = h;

        %originalw = w;

        cim = zeros(originalh+1, originalw, 3);

        sline = slinearray(p,:);

        for i = 1 : originalw

            sval = sline(i) + p - 1;

            avg = zeros(1,1,3);

            avg = firstim(sval,i, :);

            avg = avg + firstim(sval - 1, i, :);

            avg = avg / 2;

            cim(1:sval, i, :) = firstim(1:sval, i, :);

            cim(sval+1, i, :) = avg;

            cim(sval+2: originalh+1, i, :) = firstim(sval + 1: originalh, i, :);

        end

        firstim = cim;

    end

    im = firstim;

    %rotate image 270 degrees: back to original position

  

    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);

 

 

 

 

 

Object Removal:

 

 

 

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

im = I;

%save a copy of the number of seams to remove (since n is used later)

numremove = n;

im = im2double(im);

%create duplicate of the original image to use the mask later

firstim = im;

finalim = im;

%get size of image

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

img = rgb2gray(im);

[fx, fy] = gradient(img);

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

% before seams are removed, using roipoly function select area to be

% removed from the image

[mask, xi, yi] = roipoly(im);

 

%mark the pixels in the ROI as zero so they will be carved out later

for i = 1 : W

    for j = 1 : H

        if mask(j,i) == 1

            im(j,i,:) = 0;

        end

    end

end

 

%if the seaming is horizontal

if isVertical == 0

    %repeat 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

        % to remove seams, follow values in s and shift matrix up at each

        % location

        for i = 1 : W

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

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

        end

        %crop bottom

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

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

    end

    im = finalim;

    J = finalim;

end

if isVertical == 1

    % rotate image by 90 degrees

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

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

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

    im = R;

    im(:,:,2) = G;

    im(:,:,3) = B;

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

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

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

    finalim = R;

    finalim(:,:,2) = G;

    finalim(:,:,3) = B;

   

    for remloop = 1 : numremove

        %recalculate dimensions after cropped 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

        % remove seams

        % to 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,:);

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

        end

        %crop bottom

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

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

    end

    %rotate image 270 degrees: back to original position

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

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

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

    R = rot90(R);

    G = rot90(G);

    B = rot90(B);

    R = rot90(R);

    G = rot90(G);

    B = rot90(B);

   

    finalim = R;

    finalim(:,:,2) = G;

    finalim(:,:,3) = B;

   

    J = im;

    im = finalim;

end

imshow(im);