A Fast Image Segmentation using Delaunay Triangulation

A fully automated process that does not require initial estimate of number of clusters.

Description

This function applies the Delaunay-based image segmentation, which is a fully automated process that does not require initial estimate of number of clusters.

The core idea is to apply Delaunay triangulation to the image histogram instead of the image itself. That reduces the sites required to construct the diagram to merely 255 at most (uint8) resulting in a fast image segmentation.

  I don't claim it is the optimal way to segment an image, which is why I will be more than happy receiving constructive comments or reporting any bug in the program for further improvement.

  For a detailed description of the theoretical foundation of the algorithm and for citation purposes please refer to the journal paper -a pre-print copy is included here but it is better to have it in PR layout-:

  - A. Cheddad, D. Mohamad and A. Abd Manaf, "Exploiting Voronoi diagram properties in face segmentation and features extraction," Pattern Recognition, 41 (12)(2008)3842-3859, Elsevier Science.
 - A. Cheddad, J. Condell, K. Curran and P. Mc Kevitt. On Points Geometry for Fast Digital Image Segmentation. The 8th International Conference on Information Technology and Telecommunication IT&T 2008, Ireland 23 – 24 October 2008, pp: 54-61.

 Example:
[Segmented, Array]=DS(Im);
[Segmented, Array]=DS(Im,flag,open,EdHist);

 Inputs,
   Im : The image, class preferable uint8 or uint16, the function
           accepts RGB as well as grayscale images

   flag : (1) segmentation of image complement
            (0) direct segmentation [default]

   open: (1) apply grayscale morphological opening
               (0) don't apply [default]

   EdHist:(1) apply histogram equalization [default]
               (0) don't apply

 Outputs,
   Segmented: the segmented image
   Array: Array containing grayscale values (Delaunay vertices)
   used for segmentation. You can use that to call homogeneous
   regions,

   e.g., imshow(Segmented(:,:,1)==Array(i),[]); %for gray scale

   or Segmented_ntsc=rgb2ntsc(Segmented);
   imshow(Segmented_ntsc(:,:,1)<=Array(i) &
   Segmented_ntsc(:,:,1)>Array(i-1),[]); %for colour images
   Note: NTSC transformation will introduce some changes to
   values in the vector Array.

• Required Products: Image Processing Toolbox
• MATLAB release: MATLAB 7.10 (2010a)

[Samir]

 

[Samir]

Yet another brilliant piece of code from you Abbas! Thank you very much for posting that.

[Abbas Cheddad]

There is a mistake in counting the colour number. I sent the updated file to Matlabcentral but am not sure when they will update it.
Around line 198, please change the if statement to:

if length(size(Im))==3
Im(:,:,1)=im2double(Orig);
Orig=ntsc2rgb(Im);
[x xx]=imhist(Im(:,:,1));
xx(x==0)=0;
Array=xx(xx>0);

else
    
[x xx]=imhist(im2uint8(Orig(:,:,1)));% Corrected! There was a mistake here since it was written as: [x xx]=imhist(Im(:,:,1));
xx(x==0)=0;
Array=xx(xx>0);

end

%%%Please remove the following line 209
[x xx]=imhist(Im(:,:,1));
xx(x==0)=0;
Array=xx(xx>0);

[Priyanka Sharma]