%
% BlobColor.m
%
%   Function performs connected components labeling (blob coloring) on
%   a square binary image.  The largest label assigned by the algorithm
%   is returned.
%
% jph 20 April 2002
%   01/20/14: took out some loops to make it run faster.  jph
%

function [BlobLabels,MaxLabel] = BlobColor(x,size,BlobLabels)

sizeCopy = size + 1;
NextLabel = 1;

%
% init the BlobLabels array
%
BlobLabels(:) = 0;

%
% Make xCopy - a copy of x with one extra row and col prepended
%
xCopy = zeros(sizeCopy,sizeCopy);
xCopy(2:sizeCopy,2:sizeCopy) = x;

% 
%  Loop on rows and columns, color blobs
%   -the xCopy array has a copy of the original binary image x, but with
%    an extra first row of all zeros and an extra first col of all zeros.
%   -we can now loop over rows and cols starting at TWO instead of ONE in the
%    xCopy array and we don't have to worry about addressing off the left 
%    side or the top of the array in doing the algorithm on page 2.44 of the
%    course notes (page 2.31 of the old notes).
%   -doing this requires us to keep track of two sets of row and col counters.
%    One set loops over rows/cols in xCopy starting at TWO.  The other set
%    simultaneoulsy loops over the corresponding points in the BlobLabels
%    array starting each row/col loop at ONE.
% 
rowCopy = 2;
for row=1:size
  colCopy = 2;
  for col=1:size
    if (xCopy(rowCopy,colCopy) == 255)
      if ((xCopy(rowCopy,colCopy-1) == 0) & (xCopy(rowCopy-1,colCopy) == 0))
        % This is case 1 on page 2.44 of the notes:
        %   Neither the upper nor the left neighbor already have labels
        BlobLabels(row,col) = NextLabel;
        NextLabel = NextLabel + 1;
      else                    % else of if case 1
        if ((xCopy(rowCopy,colCopy-1)==0) & (xCopy(rowCopy-1,colCopy)==255))
          % upper neighbor ONLY already labeled; call this case 2
          BlobLabels(row,col) = BlobLabels(row-1,col);
        else                  % else of if case 2
          if ((xCopy(rowCopy,colCopy-1)==255) & (xCopy(rowCopy-1,colCopy)==0))
            % left neighbor ONLY already labeled; call this case 3
            BlobLabels(row,col) = BlobLabels(row,col-1);
          else                % else of if case 3
            %
            % if you are here, then both causal neighbors are already labeled
            %
            BlobLabels(row,col) = BlobLabels(row,col-1);
            if (BlobLabels(row,col-1) ~= BlobLabels(row-1,col))
              %
              % Causal neighbors have different labels
              % Combine the two blobs into a single new blob
              % Keep the label that is smallest numerically
              % Kill the other label.  Shift all labels greater than
              %   the killed label so that the used labels remain
              %   contiguous.
              %
              if (BlobLabels(row,col-1) < BlobLabels(row-1,col))
                KillLabel = BlobLabels(row-1,col);
                KeepLabel = BlobLabels(row,col-1);
              else
                KillLabel = BlobLabels(row,col-1);
                KeepLabel = BlobLabels(row-1,col);
              end
              %
              % Shift labels on all rows before the current row
              %
              for rrow=1:row-1
                for ccol=1:size
                  if (BlobLabels(rrow,ccol) == KillLabel)
                    BlobLabels(rrow,ccol) = KeepLabel;
                  else        % else of if BlobLabels == KillLabel
                    if (BlobLabels(rrow,ccol) > KillLabel)
                      BlobLabels(rrow,ccol) = BlobLabels(rrow,ccol) - 1;
                    end       % if BlobLabels > KillLabel
                  end         % end else of if BlobLabels == KillLabel
                end           % for ccol
              end             % for rrow
              %
              % Shift labels on the current row
              %
              rrow = row;
              for ccol=1:col
                if (BlobLabels(rrow,ccol) == KillLabel)
                  BlobLabels(rrow,ccol) = KeepLabel;
                else        % else of if BlobLabels == KillLabel
                  if (BlobLabels(rrow,ccol) > KillLabel)
                    BlobLabels(rrow,ccol) = BlobLabels(rrow,ccol) - 1;
                  end       % if BlobLabels > KillLabel
                end         % end else of if BlobLabels == KillLabel
              end           % for ccol
              NextLabel = NextLabel - 1;
            end               % if BlobLabels(row,col-1)~=BlobLabels(row-1,col)
          end                 % end else of if case 3
        end                   % end else of if case 2
      end                     % end else of if case 1
    end                       % if (xCopy(rowCopy,colCopy) == 255)
    colCopy = colCopy + 1;
  end                         % for col
  rowCopy = rowCopy + 1;
end                           % for row

MaxLabel = NextLabel-1;

return;
