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