How to transform a binary matrix containing a skeleton into a graph ?

Hello !

I'm working on a segmentation project, where I have to create the skeleton of a blood vessels network. Long story short, I have both an incomplete skeleton with no false branches but with part of some vessels missing (no connection to the main artery), and an overdone skeleton, which has all of the vessels well represented, but a lot of false branches due to the skeletonisation process. My objective here is to connect the vessels' parts in the incomplete skeleton using the connections in the overdone skeleton : I can easily recognize the ends of the skeleton's branches (only 1 pixel in the 3x3x3 neighbourhood) and whether or not they are connected in the second skeleton (the bwconncomp function gives me the list of the connected objects in my matrix), but how to get the shortest path between them quickly ?

As the squeleton is a binary matrix with 1 at the center of the vessels ans 0 everywhere else, it's basically a network, and I was thinking of using the graph's function in matlab to obtain quickly the shortest path to use to reconnect every end (function shortestpath, only for graphs).

So my question is : does anybody know how to convert a binary 3D matrix into a graph ? I would prefer not doing it with a for loop, I work with 1000x1000x500 matrix and a lot of operations to do after and before this one, so every shortcut is really welcome.

Thanks for your help !

EDIT : The missing parts in the skeleton are not due to the skeletonisation process but rather to the image thresholding : the two skeleton come from the same process, but with different threshold, and I have no idea on how to improve the quality of the thresholded image (closing and opening the image induce too many false gap/vessels to be useful).

[José-Luis]

What did you use for the skeletonization? Wouldn't it be easier to adjust some parameters there to get the shape you want from the get go?

I'd probably use CGAL instead of Matlab for something like this though.

[Delphine Pommier]

For the skeletonisation, I used this function : http://www.mathworks.com/matlabcentral/fileexchange/43400-skeleton3d

The problem is that the binary image I'm "skeletonising" is not made of perfect shapes : it's the result of a thresholding on an enhanced image (by a frangi filter) and if you decrease too much the threshold, you have noises and not-really-vessels shapes that creates false branches...

And I don't really know CGAL, and I'm not sure of how to transfer the data from it to matlab easily ^^'