4.8 | 4 ratings Rate this file 59 Downloads (last 30 days) File Size: 9.91 MB File ID: #28330
image thumbnail

A Fast Image Segmentation using Delaunay Triangulation



29 Jul 2010 (Updated )

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

| Watch this File

File Information

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.

Required Products Image Processing Toolbox
MATLAB release MATLAB 7.10 (R2010a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (18)
03 Apr 2014 Abbas Cheddad

Hi Vandita,

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

03 Apr 2014 Vandita

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:)

11 Apr 2013 Abbas Cheddad

A tuned version is available from:


10 Apr 2013 javed patel  
04 Sep 2012 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.

04 Sep 2012 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.

04 Sep 2012 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 (http://www.mathworks.com/help/techdoc/rn/bsk8h3i-1.html#bsljqrp-1)
The simplify option for convhull provides the option of removing vertices that do not contribute to the area or volume of the convex hull.

03 Sep 2012 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.


03 Sep 2012 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,

30 Aug 2012 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:


30 Aug 2012 Darlis Herumurti

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

26 Jul 2012 Abbas Cheddad

Please, consider taking a look also at the the following entry:


19 Jul 2012 Abbas Cheddad

Please have a look at the following tuned version:



03 Jul 2012 Abbas Cheddad

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

10 Aug 2010 Priyanka Sharma  
05 Aug 2010 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));

30 Jul 2010 Samir

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

30 Jul 2010 Samir  
29 Jul 2010

Revised the description and added some tags.

05 Aug 2010

Mistake at the end of the script.

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

05 Aug 2010

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

06 Aug 2010

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

15 Aug 2010

Update to description and screen shot

15 Aug 2010

Updated screen shot and description

16 Aug 2010

Updated description and screenshot

14 Jun 2011

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

06 Aug 2011

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

Contact us