function [x,y] = contornoBW(BW)
%CONTORNOBW Obtiene el contorno de un objeto en una imagen binaria mediante
%   algoritmo square tracing o tortuga de Papert.
%   [x,y] = contornoBW(BW)
%   Devuelve vector x y vector y con las coord x e y de todos los puntos
%   del contorno
%   -------->Y
%   |
%   |
%   |
%   v  X
%   Recorre solo un objeto y este debe estar en blanco. No recorre
%   contornos interiores (agujeros).

% NOMBRE DEL FICHERO:    contornoBW.m                                  %
% RECIBE: Imagen binaria BW                                            %
% DEVUELVE:  [x,y] matriz con las coord (x,y) de los pix.del contorno  %
% ALGORITMO EMPLEADO: square tracing. Recorre el contorno por dentro   %
% VARIABLES:   BW = imagen introducida                                 %
%              numPix = num. de pixeles de contorno                    %
%              filas = numero de filas de BW                           %
%              columnas = numero de columnas de BW                     %
%              i = variable contador para recorrer las filas de la img.%
%              j = variable contador para recorrer las columnas        %
%              x() coordenadas x de los pixeles de contorno            %
%              y() coordenadas y de los pixeles de contorno            %
%              direccion0 = direccion de entrada primer pixel          %
%              pix0 = coordenadas del primer pixel encontrado          %
%              pixObjeto = coord de un pixel sobre el objeto           %
%              nvoPix = guarda coord pixeles en el seguimiento         %
%              direccion: direc. entrada en pixel del seguidor         %
%               este  = 0;                                             %
%               sur   = 1;                                             %
%               oeste = 2;                                             %
%               norte = 3;                                             %
% BUGS: Ojo con protuberancias filiformes de 1 pixel a veces           %
%       no las recorre completas porque solo funciona bien sobre pix   %
%       4 conectados.                                                  %
% SUPOSICIONES : El fondo debe ser negro y el objeto blanco            %
%                preasigna hasta LONG_MAX_CONT para el contorno        %
% LIBRO: VISION ARTIFICIAL INDUSTRIAL. UNIVERSIDAD DE VALLADOLID 2012  %   
% TEMA 4 IMAGENES BINARIAS Algoritmo 4.5 pág 75                        %
% AUTORES: Eusebio de la Fuente y Félix Miguel Trespaderne             %
%______________________________________________________________________%
%  Ejemplo de ejecucion:                                               %
% >> I = imread('llavefija3.bmp');                                     %
% >> B = binauto(I);        %binariza con nuestra funcion binauto
% >> B = ~B;                %pone objeto en blanco
% >> imshow(B);                                                        %     
% >> hold on;                                                          %
% >> [x, y] = contornoBW(B);                                           %
% >> plot(y,x,'r-');                                                   %
%______________________________________________________________________%
% Con funciones MATLAB:                                                %
% >> I = imread('llavefija3.bmp');                                     %
% >> umbralOpt=graythresh();      %busca umbral optimo                 %
% >> BW = ~im2bw(I,umbralOpt);     %binariza                           %
% >> C=bwboundaries(BW);                                               %
% >> imshow(BW);                                                       %
% >> hold on;                                                          %
% >> plot(C{1,1}(:,2),C{1,1}(:,1),'r-');                               %
 
LONG_MAX_CONT=10000;      %consideraremos contornos de hasta 10.000 pix
x=zeros(1,LONG_MAX_CONT); %Asignación previa memo para ejecución más rápida
y=zeros(1,LONG_MAX_CONT); %Vector para guardar la coord y de cada pixel.
llego_inicio = 0;         %flag que controla el bucle principal

%Primero ponemos un marco negro de 1 pixel para que si el objeto está en 
%contacto con algún borde de la imagen, el seguidor no se salga de imagen
%originando un error
BW=EnmarcaEnNegro(BW);      
%Buscamos un primer punto del objeto. 
pix0=BuscaPrimerPunto(BW);
direccion0 = 0;   %Direc.punto inicio:lo ha encontrado yendo de izda a dcha
pixObjeto=pix0;
direccion=direccion0;
numPix=1;

while llego_inicio == 0
    %El algoritmo square tracing puede pasar dos veces por un mismo punto
    %Por eso antes de añadirle a la lista de puntos de contorno voy a
    %comprobar. Si el  pixel es igual que el ultimo guardado no lo apunto
    if numPix>1 && pixObjeto(1)== x(numPix-1) && pixObjeto(2)==y(numPix-1)
        numPix=numPix-1; %porque ya le habíamos contabilizado
    else %Si es el  pixel es distinto del ultimo guardado lo apunto
        x(numPix)=pixObjeto(1);
        y(numPix)=pixObjeto(2);
    end
    
    %Estoy en pixel del objeto por tanto giro a la izda
    [nvoPix, direccion] = GiraIzda(pixObjeto, direccion);  
    %mientras estemos en píxeles de fondo giramos a la dcha
    while BW(nvoPix(1),nvoPix(2)) == 0
        [nvoPix, direccion] = GiraDcha(nvoPix, direccion);
    end
    %ya estamos en un pixel del objeto
    numPix = numPix+1;
    pixObjeto(1)=nvoPix(1);
    pixObjeto(2)=nvoPix(2);
    %Comprobamos la condición de parada para el seguimiento del contorno
    %Chequea si hemos llegado al pixel inicial y con la misma dirección
    if pix0(1)==nvoPix(1) && pix0(2)==nvoPix(2) && direccion == direccion0
        llego_inicio = 1; %la condicion bucle seguimiento no se cumple ya
        numPix=numPix-1; %hemos contabilizado el pix de inicio dos veces
        %Ahora tengo que reajustar los vectores x e y con el tamaño real
        %del contorno. Ahora tienen LONG_MAX_CONT de longitud y contienen
        %ceros en las últimas posiciones
        x=x(1:numPix);
        y=y(1:numPix);
    else 
        llego_inicio = 0; %condicion bucle seguimiento sigue cumpliéndose
    end
end


function BW = EnmarcaEnNegro(BW)
%Ponemos un marco negro de 1 pixel para que si el objeto %está en contacto 
% con el borde de la imagen, el seguidor no se salga de la imagen generando
% un error al intentar acceder a posiciones fuera de la imagen BW
[filas,columnas] = size(BW);
BW(1,1:columnas) = 0; %primera fila en negro
BW(filas,1:columnas) = 0; %ultima fila en negro
BW(1:filas,1) = 0; %primera columna en negro
BW(1:filas,columnas) = 0; %primera fila en negro


function pix0 = BuscaPrimerPunto(BW)
% Busqueda del primer punto del objeto barriendo la imag.de dcha a izda y
% de arriba a abajo. Devuelve el primer punto que encuentra
[filas,columnas] = size(BW);
for i = 1:filas
    for j = 1:columnas
        if BW(i,j) ~= 0
            pix0 = [i,j];
            return;
        end
    end
end


function [nvoPix, nvaDirec] = GiraIzda(pix, direcEntrada)
%Proporciona las nuevas coord y nueva direc cuando la tortuga gira a la izda
%Como hemos numerado los cuatro puntos cardinales en sentido antihorario
%girar a la izda supone restar 1 (aplicando mod 4)
%si entra con dirección norte 3  nos desplazamos hacia el oeste 2
%si entra con dirección oeste 2 nos desplazamos hacia el sur 1
%si entra con dirección sur 1 nos desplazamos hacia el este 0
%si entra con dirección este 0 nos desplazamos hacia el norte 3
nvaDirec = mod(direcEntrada - 1 , 4);
%Actualizamos posición pixel según direccion en que nos hemos desplazado
switch nvaDirec
    case 3 %nos hemos movido hacia el norte
        nvoPix(1) = pix(1) - 1;
        nvoPix(2) = pix(2);       
    case 2 %nos hemos movido hacia el oeste
        nvoPix(1) = pix(1);
        nvoPix(2) = pix(2) - 1;      
    case 1 %nos hemos movido hacia el sur
        nvoPix(1) = pix(1) + 1;
        nvoPix(2) = pix(2);   
    case 0 %nos hemos movido hacia el este
        nvoPix(1) = pix(1);
        nvoPix(2) = pix(2) + 1;
end


function [nvoPix, nvaDirec] = GiraDcha(pix, direcEntrada)
%Proporciona las nuevas coord y nueva direc cuando la tortuga gira a dcha
%Como hemos numerado los cuatro puntos cardinales en sentido antihorario
%girar a la dcha supone sumar 1 (aplicando mod 4)
%si entra con dirección este 0 nos desplazamos hacia  el sur 1
%si entra con dirección sur 1 nos desplazamos hacia el el oeste 2
%si entra con dirección oeste 2 nos desplazamos hacia el norte 3
%si entra con dirección norte 3  nos desplazamos hacia el este 0
nvaDirec = mod(direcEntrada + 1 , 4);
switch nvaDirec
    case 0 %nos hemos movido hacia el este
        nvoPix(1) = pix(1);
        nvoPix(2) = pix(2) + 1;
    case 1 %nos hemos movido hacia el sur
        nvoPix(1) = pix(1) + 1;
        nvoPix(2) = pix(2);    
    case 2 %nos hemos movido hacia el oeste
        nvoPix(1) = pix(1);
        nvoPix(2) = pix(2) - 1;   
    case 3 %nos hemos movido hacia el norte
        nvoPix(1) = pix(1) - 1;
        nvoPix(2) = pix(2);
end
