File Exchange

image thumbnail

Skeletonization using voronoi

version 1.6 (3.99 KB) by

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

16 Downloads

Updated

View License

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.

Comments and Ratings (31)

Benas S

Problem:

Throws error. I'm using Matlab R2016a x64, Windows 7 x64, Launched from qhull bin folder. Error:

Error using textscan
Name-value pair arguments must come in pairs.

Error in voronoiSkel>costumVoronoi (line 250)
e=double(cell2mat(textscan(s,'%d %d %d %d %d',Ne)));

Quickfix:
change
e=double(cell2mat(textscan(s,'%d %d %d %d %d',Ne)));
to
e=double(cell2mat(textscan(s,'%d %d %d %d %d'))); % Ne

that impacts accuracy, I guess...

EDIT:
the final result is nearly the same as shown in the example, so I guess my fix is good...

Benas S

Throws error. I'm using Matlab R2016a x64, Windows 7 x64, Launched from qhull bin folder. Error:

Error using textscan
Name-value pair arguments must come in pairs.

Error in voronoiSkel>costumVoronoi (line 250)
e=double(cell2mat(textscan(s,'%d %d %d %d %d',Ne)));

Benas S

Launched from qhull bin folder

Yohai

Yohai (view profile)

Hi Siyo

1) The conventional one.
2) I don't know how to do that. I completely agree that it would be better. I'd be glad if you could show me how to implement it and I will update the code.

Siyu Guo

thanks for the codes!

I have two questions, if you could kindly reply.

1. Is the Voronoi diagram used in the algorithm the conventional one, which uses the vertices of the boundary polygon as the sites generating the diagram, or the generalized one using the EDGES of the boundary polygon as the sites?

2. I think there is a qhull instance shipped with matlab\polyfun package, which is wrapped in qhullmx and called in functions such as convhulln. Besides, a voronoi.m is also provided in matlab\specgraph. Why not use these readily available functions in MATLAB rather than a somehow not so elegant dos call?

Poonam zham

I am also facing same error:
Error using textscan
Name-value pair arguments must come in pairs.

Error in voronoiSkel>costumVoronoi
e=double(cell2mat(textscan(s,'%d %d %d %d %d',Ne)));

How to fix this issue any suggestions ?

Thanks

Joe Coolman

I tried the simple example in Matlab 2016 windows 10 with Qhull 2015.2 and I´ve got these errors:
Error using textscan
Name-value pair arguments must come in pairs.

Error in voronoiSkel>costumVoronoi
e=double(cell2mat(textscan(s,'%d %d %d %d %d',Ne)));

How can I fit it? Thanks in advance.

mika

mika (view profile)

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

any ideas.
thanks

mika

mika (view profile)

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

any ideas.
thaks

mika

mika (view profile)

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

any ideas.
thak you

mika

mika (view profile)

How to display(plot it) the centroid please!

cao

cao (view profile)

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

Yohai

Yohai (view profile)

bwmorph, with option 'skel'

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?

Abinaya

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

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.

mika

mika (view profile)

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

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.

dapo

dapo (view profile)

I need a mathematical equation for delaunay triangulation and voronoi diagram

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.

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.

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)

Yohai

Yohai (view profile)

Where are you sending it to?

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

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

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

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.

Steve

Steve (view profile)

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

Yohai

Yohai (view profile)

of course...

Updates

1.6

changed indices from int to double

1.5

qhull.org!

1.3

qhull.org!

1.2

Fixed file reading bug.

1.1

better input check.

MATLAB Release
MATLAB 7.9 (R2009b)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video