File Exchange

image thumbnail

A Fast Image Segmentation using Delaunay Triangulation

version (9.91 MB) by Abbas Cheddad
A fully automated process that does not require initial estimate of number of clusters.


Updated 06 Aug 2011

View Version History

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.

Cite As

Abbas Cheddad (2021). A Fast Image Segmentation using Delaunay Triangulation (, MATLAB Central File Exchange. Retrieved .

Comments and Ratings (20)

Abbas Cheddad

Hej Sonia,
Thank you for your interest. The code (.m) files are freely available here. On the top you can see two tabs, one is “overview” and the other is “functions” which displays the code in plain text.
Else you can click on the download button after you log in to get the files.

Note: There is an updated version of this code at:


Sonia Sonia

Hey Abbas Cheddad,
I would be very grateful if you can send me .m files please.

Abbas Cheddad

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

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.

Darlis Herumurti

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.

Darlis Herumurti

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

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.


Darlis Herumurti

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

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:


Darlis Herumurti

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

Abbas Cheddad

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

Priyanka Sharma

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
[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));


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


MATLAB Release Compatibility
Created with R2010a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!