function [vertices] = binary_contour(bin_image, bg)
% -------------------------------------------------------------------------
% MSc Project - MSc in Communications and Signal Processing
% Department of Electrical and Electronic Engineering
% Imperial College London, 2011
%
% Supervisor  : Dr Pier Luigi Dragotti
% Contributor : Andriy Gelman
% Author      : Jon Onativia Bravo
%
% File       : binary_contour.m
% -------------------------------------------------------------------------
% Extract the contour of a binary image.
%
% [vertices] = binary_contour(bin_image[, bg])
%
% INPUT:
%  - bin_image : Binary image.
%  - bg        : Label of the background. If this argument is not passed,
%                the smalles label will correspond to the background.
%
% OUTPUT:
%  - vertices  : Bidimensional array with the coordinates of the contour.
%


%% Check input arguments

labels = unique(bin_image);

% Check the image is binary
if length(labels) ~= 2
    disp('Invalid input image. The image must be binary.')
    return
end

% If only one argument is passed, consider labels(1) as background
if nargin == 1
    bg = labels(1);
end


%%
[r, c] = size(bin_image);

% Convert into a logical image
bin_image = (bin_image ~= bg);

vertices  = [];
proc_img  = false(r, c);
in_object = false;

for i = 1 : r
    for j = 1 : c
        
        if bin_image(i,j) == true
            
            % Check if the pixel has already been processed
            if proc_img(i,j) == false && in_object == false
                % If not, start a contour from this point
                [vert_buf proc_img] = follow_contour(i, j, bin_image, proc_img);
                vertices = [vertices vert_buf];
                
                in_object = true;

            else
                % If the pixel has already been processed, it belongs to a
                % contour that has already been detected, do not get the
                % contour and go inside the object
                in_object = true;
            end
            
        else
            in_object = false;
        end
        
    end 
end

return


%%
function [vertices proc_img] = follow_contour(k, l, bin_image, proc_img)

[r, c] = size(bin_image);

% Initial point
i = k;
j = l;

% Initialise loop's variables
prev_i         = i;
prev_j         = j;
end_of_contour = false;
vertices       = [i; j];

% Loop that will follow the contour until reaching the initial point
while end_of_contour == false

    neighbors = [i    i+1  i+1  i+1  i    i-1  i-1  i-1;
                 j+1  j+1  j    j-1  j-1  j-1  j    j+1];

    % Find indices of neighbors that are outside the image boundaries and
    % remove them
    ind1      = (neighbors(1,:) >= 1) & (neighbors(1,:) <= r);
    ind2      = (neighbors(2,:) >= 1) & (neighbors(2,:) <= c);
    ind       = ind1 & ind2;
    neighbors = [neighbors(1,ind); neighbors(2,ind)];
    
    tot_neigh = length(neighbors(1,:));

    % Put the previous contour point as the last neighbor
    n = 1;
    while (neighbors(1,n) ~= prev_i || neighbors(2,n) ~= prev_j)
        n = n + 1;
        
        if n == tot_neigh
            break
        end
    end
    neighbors = circshift(neighbors, [0 tot_neigh-n]);
    
    % If the first neighbor is inside the object, reverse the neighbors
    % keeping the previous point as the last neighbor
    if bin_image(neighbors(1,1),neighbors(2,1)) == true && ...
            (prev_i ~= i || prev_j ~= j)
        neighbors = [neighbors(:,tot_neigh-1:-1:1) neighbors(:,tot_neigh)];
    end
    
    % Store current indices for next iteration
    prev_i = i;
    prev_j = j;

    n = 1;
    i = neighbors(1,n);
    j = neighbors(2,n);
    
    while n <= tot_neigh && bin_image(i,j) == false
        n = n + 1;
        i = neighbors(1,n);
        j = neighbors(2,n);
    end
    
    % Check that the neighbor is really an object pixel. It may happen that
    % the initial point is an isolated pixel, so no neighboring pixel
    % belongs to the object.
    if bin_image(i,j) == false
        i = prev_i;
        j = prev_j;
    end

    % Check if we've reached the initial point
    if i == k && j == l
        end_of_contour = true;
    else
        vertices = [vertices [i; j]];
        proc_img(i,j) = true;
    end
end

return
