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 Version History

View License

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

Cite As

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

Comments and Ratings (11)

fsdgh fiboo

hi abbas
i have a problem: Undefined function or variable 'P'.

Error in DSNew (line 174)


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

Abbas Cheddad

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 ?

Abbas Cheddad

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

Abbas Cheddad

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.

Abbas Cheddad

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.

Darlis Herumurti

??? 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.

Abbas Cheddad

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

Abbas Cheddad

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.

MATLAB Release Compatibility
Created with R2012a
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!