5.0 | 2 ratings Rate this file 25 Downloads (last 30 days) File Size: 8.34 MB File ID: #37556 Version: 1.1
image thumbnail

A Fast Image Segmentation using Delaunay Triangulation (Revisited)


Abbas Cheddad (view profile)


18 Jul 2012 (Updated )

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

| Watch this File

File Information

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


Required Products Image Processing Toolbox
MATLAB release MATLAB 7.14 (R2012a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (10)
10 Apr 2014 Shirin

Shirin (view profile)

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

10 Feb 2014 Abbas Cheddad

Abbas Cheddad (view profile)

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.

Comment only
11 Dec 2013 Amani

Amani (view profile)

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 ?

Comment only
14 Nov 2012 Abbas Cheddad

Abbas Cheddad (view profile)

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

Comment only
14 Nov 2012 Abbas Cheddad

Abbas Cheddad (view profile)

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!

Comment only
12 Nov 2012 nik

nik (view profile)

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.

30 Aug 2012 Abbas Cheddad

Abbas Cheddad (view profile)

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.

Comment only
20 Aug 2012 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.

Comment only
19 Jul 2012 Abbas Cheddad

Abbas Cheddad (view profile)

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

Comment only
19 Jul 2012 Abbas Cheddad

Abbas Cheddad (view profile)

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.

Comment only
26 Jul 2012 1.1

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.

Contact us