{"id":7532,"date":"2016-07-01T09:09:39","date_gmt":"2016-07-01T13:09:39","guid":{"rendered":"https:\/\/blogs.mathworks.com\/pick\/?p=7532"},"modified":"2016-07-03T12:19:15","modified_gmt":"2016-07-03T16:19:15","slug":"skeletonizing-an-image-in-3d","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/pick\/2016\/07\/01\/skeletonizing-an-image-in-3d\/","title":{"rendered":"Skeletonizing an Image in 3D"},"content":{"rendered":"

Brett<\/a>'s Pick this week is Skeleton3D<\/tt><\/a>, by Philip Kollmansberger<\/a>.<\/p>

A couple years ago, I put together a demo to show how to use MATLAB to calculate the tortuosity<\/a>, or “twistedness,” of blood vessels. There are different formulas for measuring that property, but perhaps the easiest way of determining tortuosity of a path is using the arc-chord ratio—i.e., the length of the curve divided by the distance between its endpoints.<\/p>

In my demo, I assumed the vessels were 2-dimensional, and then used some Image Processing Toolbox<\/a> functionality to: 1) skeletonize<\/a> the vessels of interest using bwmorph<\/tt>\/skel<\/a>, and 2) determine the endpoints of the segment (facilitated by a call to bwmorph<\/tt>\/endpoints<\/a>. Then, using one or both endpoints of the segment, respectively, to 3) calculate the geodesic distance transform of the vessel (bwdistgeodesic<\/tt><\/a>), the maximum value of which provides the arc-length; and 4) calculate the distance the endpoints. (You can find a discussion of this approach in a recorded webinar<\/a> at mathworks.com.)<\/p>

This approach is reasonably straightforward when you assume planarity, but in 3D, it gets much more challenging—because bwmorph doesn’t currently support the analysis of 3D images. That leaves us struggling to do the skeletonization- and endpoint-detection steps.<\/p>

Enter Philip’s Skeleton3D<\/tt> function. Using an algorithm (properly cited in the code) based on “3-D medial surface\/axis thinning algorithms,” Skeleton3D<\/tt> finds axial values that can be subsequently analyzed for the determination of tortuosity.<\/p>

load testvol<\/span>\r\ninds = find(testvol);\r\n[y,x,z] = ind2sub(size(testvol),inds);\r\ns = scatter3(x,y,z,100,...<\/span>\r\n  'Marker'<\/span>,'o'<\/span>,...<\/span>\r\n  'MarkerEdgeColor'<\/span>,'none'<\/span>,...<\/span>\r\n  'MarkerFaceAlpha'<\/span>,0.3,...<\/span>\r\n  'MarkerFaceColor'<\/span>,'c'<\/span>);\r\nxlabel('x'<\/span>);\r\nylabel('y'<\/span>);\r\nzlabel('z'<\/span>);\r\ntitle('Test Volume'<\/span>)\r\n<\/pre>
\"\" <\/p>
Now we can extract and display points along the skeleton of this test volume:<\/p>
skel = Skeleton3D(testvol);\r\ninds = find(skel);\r\n[yskel,xskel,zskel] = ind2sub(size(skel),inds);\r\nhold on<\/span>\r\np2 = scatter3(xskel,yskel,zskel,20,...<\/span>\r\n    'Marker'<\/span>,'o'<\/span>,...<\/span>\r\n    'MarkerEdgeColor'<\/span>,'none'<\/span>,...<\/span>\r\n    'MarkerFaceColor'<\/span>,'r'<\/span>);\r\n<\/pre>
\"\" <\/p>
For tortuosity determinations, there's still some more work to be done--we still need to detect endpoints and arclengths, for instance. Those are topics for a different day.<\/p>
For Philip, an implementation comment: Skeleton3D<\/tt> is considerably slower than it needs to be. It relies on looping over indices where vectorized approaches<\/a> can be much faster. And converting to logical indexing<\/a> for comparisons can also speed things up. For instance:<\/p>
In the determination of \"candidate foreground voxels,\" you can replace:<\/p>
cands = intersect(find(cands(:)==1),find(skel(:)==1));\r\n<\/pre>
with<\/p>
cands = find(cands & skel);\r\n<\/pre>
(Admittedly, that buys just a little improvement in performance, but I find it more elegant.)<\/p>
More pointedly, if you were to profile<\/a> your code, you'd find a large percentage of time spent calculating the skeleton of your testvol reflects nearly 87,000 calls to p_oct_label<\/tt>. That code could be greatly sped up by replacing successive indx(row) = find(cube(row,:)==1)<\/tt> calls in the analysis of 'cube' with something along the lines of<\/p>
[row,col] = ind2sub(size(cube),cube==1);\r\nindx(row) = col(row == 1);\r\n<\/pre>
and iterating over values of row<\/tt>.<\/p>
Nonetheless, this provides a good start to anyone needing to skeletonize structures in 3D. Thanks, Philip, for this very nice contribution!<\/p>
As always, I welcome your thoughts and comments<\/a>.<\/p>