Watershed Partitioning

Watershed Partitioning is a digital image processing algorithm for pattern recognition. A monochrome image is first developed. This could be of pixel values (to find bright spots) or gradient values (for line detection).

Then imagine inverting the image, so bright spots are the lowest points on a three dimensional surface. By filling the lowest points with "water" first, you create new partitions, which then grow until they bump into neighboring partitions. The pixel in common is then marked as a boundary point.

Some sample matlab code:

function {PartList} = WaterPart(ImageMono) 


%  Replace all curly brackets with reg brackets... 
%  I didn't Want them to appear as e2 links! 
%     Pseudo Code:  
%
%    Order all pixels by gray-scale intensity.
%    Initial Intensity Range of { 1- magic_number_1, 1}
%    While CandidateIndex is empty:
%       For each pixel in Intensity Range: 
%          If Adjacent to pixel in any partition, 
%             Add to Partition 
%          Elseif farther than magic_number_2  from any existing partition:
%             start a new partition.
%          Else Carry Over into next intensity iteration.
%       Intensity Range = { old_bottom - magic_number_1, 1};
%    EndWhile
%    For All Partitions with less than magic_number_3 members:
%        Attach to smallest neighbor.

DeltaPix = 3/255; 	% Magic number 1
MinDist	 =   	5;		% Magic number 2
Pthresh  =   .15; 	% Magic number 4
VerCol   = 1; 	HorCol = 2; 	PixCol = 3; 	PartCol = 4; % column indices: 

   
%    Order all pixels by gray-scale intensity.
LightList = ;
iVerMax = size(ImageMono,1);	iHorMax = size(ImageMono,2);
%for iVer = 1 : iVerMax;
%   for iHor = 1 : iHorMax;
%      if ImageMono(iVer,iHor) > Pthresh;
%         NumPixels = NumPixels+1;
%         LightList(NumPixels,HorCol) = iHor ;
%         LightList(NumPixels,VerCol) = iVer ;
%         LightList(NumPixels,PixCol) = ImageMono(iVer,iHor);
%         LightList(NumPixels,PartCol) = 0;
%      end;
%   end;
%end;
LightList(:,VerCol),LightList(:,HorCol) = find(ImageMono>Pthresh); 
NumPixels = size(LightList,1);
for i = 1:NumPixels; 
   LightList(i,PixCol) = ImageMono(LightList(i,VerCol),LightList(i,HorCol)); 
end; 
{ Dummy_Neg_Pix_Values, Indices} =  sort(-LightList(:,PixCol));    
LightList = LightList(Indices,:);


LowestIntensity  = LightList(NumPixels,PixCol) ;
LoIntensity 	= LightList(1,PixCol) ;
CandidateIndex 	= {};
LeftOverIndex 	= {}
PartList	= {};
PartCnt		= 1;
PartPixCnt	= 1;
PartList(1,:)	= LightList(1,:);
PartList(1,PartCol)= PartCnt;
UnUsedMark = 1 ;

while UnUsedMark < size(LightList,1);
   LoIntensity = LoIntensity - DeltaPix;   
   % Add New Canditates to UnusedList:
   CandidateIndex 	= LeftOverIndex;
   LeftOverIndex 	= {};
   if (LoIntensity <= LowestIntensity)
      CandidateIndex = { CandidateIndex, {UnUsedMark+1:NumPixels}};
      UnUsedMark  = NumPixels;
   else
      while LightList(UnUsedMark+1,PixCol) >= LoIntensity;
         UnUsedMark  =  UnUsedMark +1 ;
         CandidateIndex =  {CandidateIndex, {UnUsedMark}};
      end
   end;
   
   for iCand = 1: size(CandidateIndex,2);
      POI = LightList(CandidateIndex(iCand),:); % Pixel Of Interest
      neighbors = find( ...
         ( abs(PartList(:,HorCol)-POI(HorCol)) <= 1 ) & ...
         ( abs(PartList(:,VerCol)-POI(VerCol)) <= 1 ) )   ; 
      if ~isempty(neighbors);
         % If Multiple neighbors, just assign to top one, for now.
         PartPixCnt 							= PartPixCnt + 1;
         PartList(PartPixCnt,1:3) 		= POI; 
         PartList(PartPixCnt,PartCol) 	= PartList(neighbors(1),PartCol);
      else
         if min(abs(PartList(:,HorCol)-POI(HorCol))+abs(PartList(:,VerCol)-POI(VerCol))) > MinDist;
            PartPixCnt 	= PartPixCnt + 1;
            PartCnt 	= PartCnt +1;
            PartList(PartPixCnt,1:3) 	= POI; 
            PartList(PartPixCnt,PartCol) = PartCnt;
         else
            LeftOverIndex = {LeftOverIndex, CandidateIndex(iCand)};
         end
      end
   end
end