Is there a way to significantly reduce the time for calculating centerlines?

Hello, everyone,

I’m interested in smoothing the centerlines of the cerebral arteries.

I segmented the MRA images and extracted the voxels of arteries. Using VTK’s marching cubes, I created a mesh and further performed Taubin smoothing and remeshing with pymeshlab.

After that, I attempted to extract centerlines using vmtkcenterlines. The sources are 2 points on the internal carotid artery and 1 point on the basilar artery, while the targets are peripheral points (approximately 150 points). I’m using Apple silicon, M3pro, with an Intel version of conda in a virtual environment (Python 3.10.13). The centerlines extraction takes about 12 hours at the fastest, which is too long. Is there a good way to shorten this?

I tried keeping the sources as the 3 points and selecting 3 random points as targets for the same centerlines extraction, but it still took over 10 hours. I also tried using a supercomputer, but it did not lead to a reduction in time.

The code I used is as follows:

def vmtk_extract_centerline(file_name, sources, targets):
# vmtk_extract_centerline(mesh, sources, targets, seedselector=“pointlist”):
# args: mesh: 3D mesh (vtkPolydata)
# sources: 3D coordinates of source points (numpy.ndarray)
# targets: 3D coordinates of target points (numpy.ndarray)
# seedselector: Options include “pickpoint”, “openprofiles”, “carotidprofiles”, “profileidlist”, “idlist” and “pointlist”.
# returns: centerlines (vtkPolyData)
source_points = sources.flatten().tolist()
target_points = targets.flatten().tolist()

# Read the input surface mesh from a file
file_extension = os.path.splitext(file_name)[1].lower()
if file_extension == ".vtp":
    reader = vtk.vtkXMLPolyDataReader()
elif file_extension == ".ply":
    reader = vtk.vtkPLYReader()
    raise ValueError(f"Unsupported file extension: {file_extension}")

mesh = reader.GetOutput()

# Extract centerline
centerline_extractor = vmtkscripts.vmtkCenterlines()
centerline_extractor.Surface = mesh

# Define source and target points
centerline_extractor.SeedSelectorName = "pointlist"
centerline_extractor.SourcePoints = source_points 
centerline_extractor.TargetPoints = target_points

centerlines = centerline_extractor.Centerlines
return centerlines

Any advice would be greatly appreciated.
Thank you.

If you use the ‘Extract centerline’ module in Slicer, it has a ‘Preprocess input surface’ option than may significantly reduce processing time. It will still be long since you have so many end points, and it is not clear whether it’s a single surface or if it has distinct islands.

Probably the mesh has serveral magnitudes more points than necessary. Try the Extract Centerline module in 3D Slicer as @chir.set suggested to make sure you properly preprocess your mesh.

Network extraction should take just a couple of seconds. Since brain vasculature does not have a tree topology (it has circles), this may be your only option to get a full centerline graph anyway.

You can still use centerline curve extraction for a few selected branches, if you need more realistic shape at branching points or you want to search for shortest path between two points in the vasculature.

@ chir.set

Thank you for your response.

As I always processed in Python on VS Code, I am not familiar with 3D Slicer, and it took me some time to get used to it, which caused my delayed response.

As you pointed out, the Extract Centerline in 3D Slicer significantly reduced the processing time (what took over 10 hours on Python was done in less than a minute). The difficulty lies in understanding the extent of decimation and subdivision in the 3D Slicer preprocess. However, even when I used a very detailed mesh preprocessed with a different script for centerline extraction in 3D Slicer, the processing time was still very short.

I wonder why the processing time is so much longer when using the same VMTK library in Python, but so much shorter in 3D Slicer?

Anyway, thank you very much.

@ lassoan

Thank you for your response.

As you and @Chir.set mentioned, using 3D Slicer allowed me to perform centerline extraction extremely quickly. I wonder why the processing time is so much longer when using the same VMTK library in Python, but so much shorter in 3D Slicer?

Anyway, it was really helpful. Thank you very much.

There is one more thing I would like to ask.

I found that auto-detecting endpoints in 3D Slicer is very useful.

However, in the image, the artifact areas (the red circles in Figure 1) are not vessels, yet the centerline extraction still extracts centerlines through them, despite not specifying them as endpoints.

Is there a way to prevent this?

I used auto-detect for the endpoints, and unchecked the inlet area as shown in Figure 2 (though I’m not sure if this is correct).

I implemented smart preprocessing in the 3D Slicer module, which makes the centerline extraction practically usable on meshes created by 3D image segmentation. I made the source code publicly available on github with a permissive license (anybody can freely use it for any purpose without restrictions), so you are free to take it and use it anywhere. However, if you want to implement a VTK-based application that is readily usable in clinical workflows then your best option is probably to develop it within 3D Slicer (by adding a custom Python scripted module that guides the user through your entire workflow with a simplified user interface).

This is the ‘Network’ centerline, which as I understood, is based on geometry and is always extractible and fast. Have you tried the ‘Tree’ centerline. This one accounts for blood flow, is heavily dependent on the quality of the mesh and may not give expected results.

I will make sure to read the GitHub page carefully.

As you mentioned, selecting Tree resulted in the extraction of the centerline as I imagined, taking the branching into account. However, what could be the difference between the blood vessels where the centerline is successfully extracted and those where it is not, as shown in the figure?

I thought the issue might be that the blood vessels are too thin, so I moved the endpoints and the regions in the figure to relatively thicker parts of the blood vessels, but the result did not change.

When centerline extraction cannot find a path then indeed you need to move the desired endpoints closer to thicker branches. If path is still not found then you need to move the endpoints even further so that there is a sufficiently thick path connecting them. You can also trying increasing the number of points from 5000 to 10000 or more. If you select an output model for the Voronoi surface then you can see the surface where the path is searched along.


Thank you for your advice.
I will try various approaches based on your suggestions.