Code covered by the BSD License  

Highlights from
Skeletonization using voronoi

5.0
5.0 | 4 ratings Rate this file 60 Downloads (last 30 days) File Size: 3.99 KB File ID: #27543
image thumbnail

Skeletonization using voronoi

by

Yohai (view profile)

 

09 May 2010 (Updated )

An efficient skeletonization (thinning) which uses the Voronoi diagram.

| Watch this File

File Information
Description

voronoiSkel uses only the pixel on the boundary of the objects, and therefore is very efficient for thick objects (efficiency scales with the object's radius, rather than its area). However, it might be sensitive to small defects, if they are on the boundaries (or small holes inside the object).

Also, the function analytically calculates the topology of the skeleton, and can give as an output the vertices and edges of the skeleton graph.

The function uses qhull (www.qhull.org, free download), and therefore qhull must be executable from the command line in the current directory. In order to enable that, you can either add qhull to your OS path, or keep a copy of it in the working directory.

MATLAB release MATLAB 7.9 (R2009b)
Other requirements The function uses qhull (www.qhull.org, free download), which must be executable from the command line in the current directory.
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (24)
20 Jun 2014 mika

mika (view profile)

How to display(plot it) the centroid of each cell and determine the coordinates please!

any ideas.
thanks

Comment only
03 Jun 2014 mika

mika (view profile)

How to display(plot it) the centroid of each cell and determine the coordinates please!

any ideas.
thaks

Comment only
02 Jun 2014 mika

mika (view profile)

How to display(plot it) the centroid of each cell please!

any ideas.
thak you

Comment only
02 Jun 2014 mika

mika (view profile)

How to display(plot it) the centroid please!

Comment only
02 Apr 2014 cao

cao (view profile)

couldn't be more nice! It works and meets my need of the programme!

29 Mar 2014 Yohai

Yohai (view profile)

bwmorph, with option 'skel'

Comment only
28 Mar 2014 Ilya

Ilya (view profile)

Nilimb said: "its slower than the matlab's inbuilt"
But what's the MATLAB's inbuilt? Is there any inbuilt function in MATLAB that does the same?

Comment only
16 Mar 2014 Abinaya

I am working on Matlab 7.5.0(R2007b). Will this work for me?

Comment only
16 Mar 2014 Abinaya

Though I have the qhull-2012.1 folder in my current directory. Error is returned as 'qhull is not recognised as an internal or external command,operable program, batch file. How should I fix it. Please help me.

Comment only
21 Feb 2014 mika

mika (view profile)

 
19 Feb 2014 Yohai

Yohai (view profile)

The idea is pretty simple: Take all the points on the area's boundary, and calculate their Voronoi diagram. Each segment in the Voronoi diagram is equidistant from two boundary points, so it is a candidate of being in the skeleton. However, this results in a giant skeleton that you need to "Trim".

Try looking here:
http://stackoverflow.com/questions/16741337/from-voronoi-diagram-to-skeleton

http://www.cse.ohio-state.edu/~tamaldey/paper/medial.pdf

http://www.sci.utah.edu/~gerig/CS7960-S2010/handouts/voronoi.pdf

Comment only
19 Feb 2014 mika

mika (view profile)

I'm no longer trying to understand the Voronoi skeleton code in matlab
but in vain because i'm just starting with matlab .
Can you please provide me with the Algorithm
or the mathematical model or even a real execution example
I'm so interested .

Thank you.

Comment only
20 Jan 2014 dapo

dapo (view profile)

I need a mathematical equation for delaunay triangulation and voronoi diagram

Comment only
16 Nov 2011 Nilimb

Nilimb (view profile)

i have tried it with the 'fast' option. Still slower though for an image with many small objects. I guess its doing a lot of calcs in the .exe file.

Comment only
15 Nov 2011 Yohai

Yohai (view profile)

The running time scales with the length of the white object's boundary. This is better that MATLAB's functions that scales with its area, if your object's boundary is not fractal-like.

As explained in the file, you can improve speed on the expense of accuracy using the 'fast' option. For example,
voronoiSkel(BW,'fast',3)
uses only every 3rd point on the boundary, giving less accurate results but faster calcualation.

Comment only
15 Nov 2011 Nilimb

Nilimb (view profile)

the results are pretty good. can you do something about the speed of execution though. its slower than the matlab's inbuilt (but the accuracy is better)

30 May 2010 Yohai

Yohai (view profile)

Where are you sending it to?

Comment only
29 May 2010 ntenson

Thanks so much.

I am no longer having the error message. However I think that the number of vertices is too high and may result in a degenrate voronoi diagram. I am therfore sending you the image file for verification

Comment only
28 May 2010 Yohai

Yohai (view profile)

I think I know what the problem is.
I updated the file, changing line 249 to

e=double(cell2mat(textscan(s,'%d %d %d %d %d',Ne)));

(casting to double instead of int32 or whatever it is)

I hope that's the bug. If the problem persists, try sending my the data so I can reproduce the problem

Comment only
28 May 2010 ntenson

I came out with this message trying to use the program:
??? Error using ==> minus
Integers can only be combined with integers of the same class, or scalar doubles.

Error in ==> voronoiSkel at 205
e(:,1)=e(:,1)-inds(e(:,1))';
Please let me know: is it because of my inconsistent Qhull with win7-bits?
Thanks in advance
ntenson

Comment only
12 May 2010 Yohai

Yohai (view profile)

I'm sure there is, but I couldn't figure out how.
If you find out how to to use the matlab function voronoi (or delaunay, voronoin,...) and to get as output the centres of the voronoi cells, I can use that to make it work. But, as I said, I couldn't figure out how to do that.

Comment only
12 May 2010 Steve

Steve (view profile)

Works perfect! Thanks! Is there any chance to run this without downloading qhull?

12 May 2010 Yohai

Yohai (view profile)

of course...

Comment only
11 May 2010 Danila

Danila (view profile)

www.qhull.org, not www.qhull.com

Comment only
Updates
11 May 2010

better input check.

11 May 2010

Fixed file reading bug.

12 May 2010

qhull.org!

12 May 2010

qhull.org!

28 May 2010

changed indices from int to double

Contact us