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

**URL:** <https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313>\
**Category:** VMTK\
**Tags:** python\
**Created:** [May 22, 2024, 6:00am UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313 "2024-05-22T06:00:53Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![tomo-akiyama](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/tomo-akiyama/32/69831_2.png) [@tomo-akiyama](https://discourse.slicer.org/u/tomo-akiyama)\
**Post date:** [May 22, 2024, 6:00am UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/1 "2024-05-22T06:00:53Z")

</div>

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()
else:
    raise ValueError(f"Unsupported file extension: {file_extension}")

reader.SetFileName(file_name)
reader.Update()
mesh = reader.GetOutput()

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

# Define source and target points
# http://www.vmtk.org/vmtkscripts/vmtkcenterlines.html
centerline_extractor.SeedSelectorName = "pointlist"
centerline_extractor.SourcePoints = source_points 
centerline_extractor.TargetPoints = target_points
centerline_extractor.Execute()

centerlines = centerline_extractor.Centerlines
return centerlines

```

Any advice would be greatly appreciated.  
Thank you.

 ![スクリーンショット 2024-05-22 14.52.48](https://us1.discourse-cdn.com/flex002/uploads/slicer/original/3X/b/e/be23578038917851c2329af4d02c43183e94ab45.jpeg)

---

<div class="post-metadata">

**Author:** ![chir.set](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/chir.set/32/66982_2.png) [@chir.set](https://discourse.slicer.org/u/chir.set)\
**Post date:** [May 22, 2024, 8:35am UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/2 "2024-05-22T08:35:17Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![lassoan](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/lassoan/32/13_2.png) [@lassoan](https://discourse.slicer.org/u/lassoan)\
**Post date:** [May 23, 2024, 12:41pm UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/3 "2024-05-23T12:41:25Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![tomo-akiyama](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/tomo-akiyama/32/69831_2.png) [@tomo-akiyama](https://discourse.slicer.org/u/tomo-akiyama)\
**Post date:** [May 28, 2024, 2:22am UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/4 "2024-05-28T02:22:34Z")

</div>

@ [chir.set](https://discourse.slicer.org/u/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.

---

<div class="post-metadata">

**Author:** ![tomo-akiyama](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/tomo-akiyama/32/69831_2.png) [@tomo-akiyama](https://discourse.slicer.org/u/tomo-akiyama)\
**Post date:** [May 28, 2024, 2:25am UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/5 "2024-05-28T02:25:21Z")

</div>

@ [lassoan](https://discourse.slicer.org/u/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.

---

<div class="post-metadata">

**Author:** ![tomo-akiyama](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/tomo-akiyama/32/69831_2.png) [@tomo-akiyama](https://discourse.slicer.org/u/tomo-akiyama)\
**Post date:** [May 28, 2024, 3:38am UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/6 "2024-05-28T03:38:12Z")

</div>

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?

 ![Fig 1](https://us1.discourse-cdn.com/flex002/uploads/slicer/original/3X/e/9/e991d9d860565d329681601be2dd9f17280f6f81.jpeg)

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).

 ![Fig 2](https://us1.discourse-cdn.com/flex002/uploads/slicer/original/3X/9/4/94951ded54b5e4d4eec518ab213b170a9a39eded.jpeg)

---

<div class="post-metadata">

**Author:** ![lassoan](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/lassoan/32/13_2.png) [@lassoan](https://discourse.slicer.org/u/lassoan)\
**Post date:** [May 28, 2024, 4:21am UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/7 "2024-05-28T04:21:48Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![chir.set](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/chir.set/32/66982_2.png) [@chir.set](https://discourse.slicer.org/u/chir.set)\
**Post date:** [May 28, 2024, 6:54am UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/8 "2024-05-28T06:54:28Z")

</div>

> [@tomo-akiyama](#):
>
> Is there a way to prevent this?

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.

---

<div class="post-metadata">

**Author:** ![tomo-akiyama](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/tomo-akiyama/32/69831_2.png) [@tomo-akiyama](https://discourse.slicer.org/u/tomo-akiyama)\
**Post date:** [May 28, 2024, 7:30am UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/9 "2024-05-28T07:30:53Z")

</div>

> [@lassoan](#):
>
> 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).

@chir.set  
@lassoan  
Thanks.  
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?

 ![スクリーンショット 2024-05-28 16.32.45](https://us1.discourse-cdn.com/flex002/uploads/slicer/original/3X/4/e/4ed8062f799d4cad7238c63a9c534ba45c865ada.jpeg)  
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.  
 ![スクリーンショット 2024-05-28 16.36.17](https://us1.discourse-cdn.com/flex002/uploads/slicer/original/3X/9/1/91e7f11084451458cf13276eb9b1ed3eb42df4f8.jpeg)

---

<div class="post-metadata">

**Author:** ![lassoan](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/lassoan/32/13_2.png) [@lassoan](https://discourse.slicer.org/u/lassoan)\
**Post date:** [May 31, 2024, 9:13pm UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/10 "2024-05-31T21:13:29Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![tomo-akiyama](https://sea2.discourse-cdn.com/flex002/user_avatar/discourse.slicer.org/tomo-akiyama/32/69831_2.png) [@tomo-akiyama](https://discourse.slicer.org/u/tomo-akiyama)\
**Post date:** [June 2, 2024, 11:46pm UTC](https://discourse.slicer.org/t/is-there-a-way-to-significantly-reduce-the-time-for-calculating-centerlines/36313/11 "2024-06-02T23:46:45Z")

</div>

@lassoan

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