A Fast Image Segmentation using Delaunay Triangulation (Revisited)

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

Description

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

http://www.mathworks.nl/matlabcentral/fileexchange/28330-a-fast-image-segmentation-using-delaunay-triangulation

• Required Products: Image Processing Toolbox
• MATLAB release: MATLAB 7.14 (R2012a)

[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!

[nik]

Hi, what a great share!

I found error:

>> DSNew
Undefined function or variable "P".

Error in DSNew (line 174)
P3=P;

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. 7.13.0.564 (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));
ind2=ind2(1);
dis=sqrt(ind.^2+ind2.^2);
x(j)=x(j)*dis;
end

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