Code covered by the BSD License  

Highlights from
Skeletonization using voronoi

5.0

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

Skeletonization using voronoi

by

 

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 (20)
02 Apr 2014 cao

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

29 Mar 2014 Yohai

bwmorph, with option 'skel'

28 Mar 2014 Ilya

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?

16 Mar 2014 Abinaya

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

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.

21 Feb 2014 mika  
19 Feb 2014 Yohai

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

19 Feb 2014 mika

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.

20 Jan 2014 dapo

I need a mathematical equation for delaunay triangulation and voronoi diagram

16 Nov 2011 Nilimb

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.

15 Nov 2011 Yohai

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.

15 Nov 2011 Nilimb

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

Where are you sending it to?

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

28 May 2010 Yohai

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

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

12 May 2010 Yohai

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.

12 May 2010 Steve

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

12 May 2010 Yohai

of course...

11 May 2010 Danila

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

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