File Exchange

image thumbnail

A Fast Image Segmentation using Delaunay Triangulation (Revisited)

version (8.34 MB) by Abbas Cheddad
This is a tuned version of the old post on Delaunay-based image segmentation.


Updated 26 Jul 2012

View License

This is a tuned version of the old post on Delaunay-based image segmentation.

Comments and Ratings (10)


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.

Thanks in advance for your help

I have already sent you an email

Dear Amani, Will it be possible to share with me the image which has generate such an error, I don't seem to have such problem with the program I have.


I changed this
[ind2 ~]=find(x==x(j));
[ind2 ind_out]=find(x==x(j));
but still having this error

Undefined function or variable "P".

Error in DSNew (line 174)
what should I do ?

...calculates vertices of the Voronoi diagram [Delaunay Triangulation]'s outer graph (formally known as the convex hull)

Hi Nik,

First of all thank you for your sweet comment. I am also using R2012a version and have no problem with the script.

What the program does is it calculates vertices of the Voronoi diagram's outer graph (formally known as the convex hull) and that is applied on the image histogram. The vertices are calculated twice:
Once from the histogram giving the vector P
and another time from the invert of the histogram yielding vector P3.
Sometimes P3 cannot be achieved due to co-linearity, so the program works on P instead of P3.

As for your problem, since you said P does have a value then I don't understand why you obtained "Undefined function or variable "P"."??

It would be helpful to show me the image you have been working on so that I can see exactly where the problem is -if any-.

Have a nice day!


Hi, what a great share!

I found error:

>> DSNew
Undefined function or variable "P".

Error in DSNew (line 174)

I am using matlab r2012a, what does it mean? i can see that P do have value and have been used before.

Hope you dont mind explaining this to me. Thank you.

Hi again Darlis,

I have rechecked the program and it runs fine without any errors. I am running Matlab Ver. (R2011b).
I suspect, though not sure, the problem you are facing with the older version is because it does not like a neglected output "~" as in [ind2 ~]=find(x==x(j));
Therefore, you probably need to change that to
[ind2 ind_out]=find(x==x(j));

Now, the description of the code is as follows:

% Getting the global maxima in x (histogram of the image)
[ind1 ind]=max(x);

%Retrieving the distance between each index in the histogram and the global maxima's index "ind". Then we multiply each index's count by its respective weight which is but the calculated relative distance.

for j=1:256
[ind2 ~]=find(x==x(j));

%This portion of the program locates the 2nd largest and furthest peak from the global maxima in the histogram. After this has been attained, we apply the Voronoi diagram as described in the paper.

I hope that has answered your question.

??? Error: File: DSNew.m Line: 91 Column: 8
Unbalanced or unexpected parenthesis or bracket.

line 91: [ind2 ~]=find(x==x(j));
I use matlab 7.6.0 (R2008), what does the [ind2 ~] mean ?
Thx so much for the response.

One more note on the newly introduced iterative function. It is just a recursive call for the main function and is not stable yet, I set the number of clusters N to 3 (the condition N==3 although it is worth changing it to N<=3 since clusters aggregation is not guaranteed to be sequential).

Anyhow, that is just a bonus function and you can always resort to using the main one:
[Segmented, Clusters]=DSNew(A,1,0,1,1);

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.

Please keep in mind that this function is meant to segment a given image
without having access to priori information on the number of clusters. It approximates a
good segmentation but I don't claim it is the optimum. One, however, could use the number of clusters that it arrives
at as an input to a more sphisticated (time consuming) segmentation algorithms like the K-means or region growing algorithms for example. I will be more than happy to receive your constructive comments or to report any bug in the program to allow further improvements.


In the DSIterate.m file


if length(Clusters2)==3 % Setting the min to 5 clusters

Changed to:

if length(Clusters2)<=5 % Setting the minimum number of clusters to 5


Changed the screenshot image.

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

Discover Live Editor

Create scripts with code, output, and formatted text in a single executable document.

Learn About Live Editor