File Exchange

image thumbnail

A Fast Image Segmentation using Delaunay Triangulation

version 1.22 (9.91 MB) by

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



View License

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.

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

   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

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

   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.

Comments and Ratings (18)

Abbas Cheddad

Abbas Cheddad (view profile)

Hi Vandita,

Can you PM me your email address so that I could send you the .m files?


Hi Abbas,
I am more comfortable to use simple code then GUI based. Can you please send me that version instead of the GUI one.
Hope you will respond soon as you have done in past.
Thanks in advance for your help:)

javed patel

Abbas Cheddad

Abbas Cheddad (view profile)

Darlis, I know MATLAB has introduced updates to its built-in function convhull across the different versions since MATLAB Version: 7.01. But thanks for letting me know that and for your suggestion, I will examine it further and see if it is worth adding the "simplify" parameter as an option. However, you are free to modify the code.

However, removing vertices that do not contribute to the area will lead to an improper segmentation result. Alternatively, it can be added as a new parameter to the method.

Thank you so much for your great works.

Yes, it run well, and the the code is wery helpfull.
I've found that, the convhull function yield a different result in version 2008a and 2011b. the convhull(x,y) in version 2008a is similar with convhull(x,y,'simplify',true) in version 2011b.
That's why, the 2008 version run faster than 2011a(without parameter simplify).

From the doc (
The simplify option for convhull provides the option of removing vertices that do not contribute to the area or volume of the convex hull.

Abbas Cheddad

Abbas Cheddad (view profile)

Hello Darlis,

Unfortunately, I don't have access to the 2008 release. But the code works fine on the following releases and IP product's versions:

MATLAB Version: (R2012a)
Image Processing Toolbox Version 8.0 (R2012a)
32bit Machine

MATLAB Version (R2011b)
Image Processing Toolbox Version 7.3 (R2011b)
64bit Machine

I hope that helps.


Thanks again for your answer.
For your information, I've just tried in the different version of matlab (2008a and 2011b). Just wonder that I got the different result with the same code. I don't know why and the 2011b version is slight slower than 2008b.
Thank you for your kind attention.

Sincerely yours,

Abbas Cheddad

Abbas Cheddad (view profile)

You are most welcome Darlis and thank you so much too for the positive rating.
I have answered your question on the other post of mine:


Thank you so much for your sharing code and your great paper.

Abbas Cheddad

Abbas Cheddad (view profile)

This submission will be updated very soon or else it will be linked to a new polished code version.

Abbas Cheddad

Abbas Cheddad (view profile)

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
[x xx]=imhist(Im(:,:,1));

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


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


Samir (view profile)

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


Samir (view profile)



Some bugs in displaying the values in "Array" have been fixed.


- A user friendly GUI creation
- Now the programme exports the segmented image as "Segmented.tif"


Updated description and screenshot


Updated screen shot and description


Update to description and screen shot


- Bug fix (gray colour count in RGB)
- Appended a new screenshot
- Added some useful comments to the script


Bug fixed (grayscale count for RGB images) and file script update


Mistake at the end of the script.

if length(size(Im))==3
[x xx]=imhist(Im(:,:,1));
[x xx]=imhist(im2uint8(Orig(:,:,1)));


Revised the description and added some tags.

MATLAB Release
MATLAB 7.10 (R2010a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video