Explicit vascular reconstruction based on adjacent vector projection

ABSTRACT

Blood vascular reconstruction plays an important role in vessel disease diagnosis and prognosis, treatment planning and surgery. Based on adjacent vector projection, a simple and robust explicit algorithm is presented for vascular reconstruction. It generates the base mesh and utilizes the Loop algorithm for perceptual refinement by mesh subdivision. In the end, the reconstructed vascular tree is rendered for volumetric visualization and localization of vascular malformations. Experimental results on the Aneurisk database have validated the capacity of the proposed algorithm in generating smooth surface and natural transition of high tortuosity in real time, while on clinical cases has verified its accuracy on pinning vascular stenosis.

KEYWORDS:

• loop subdivision
• up-vector
• vascular reconstruction
• vascular malformations

Introduction

Vascular reconstruction is the most straightforward and convincing way to localize vascular malformations and deliver treatment of stent placement.^1-3 In particular, volumetric visualization of reconstructed vascular trees gives physicians and doctors an insight into the vessel topology and guarantees the accuracy of diagnosis and staging so as to provide more proper treatment planning.^3-5 In addition, it is helpful in modeling biological vascular system, clinical education and other related applications.^4-7

Algorithms for blood vascular reconstruction can be generally grouped into implicit and explicit methods.¹ The implicit algorithms are model-free in a direct manner,^8-13 such as Marching Cube⁸ and Multilevel Partition of Unity Implicits (MPUI).¹² Marching Cube is widely used but parameter sensitive. Meanwhile, filling the void volume with the linear interpolation reduces vascular visual quality. MPUI makes use of piecewise quadratic functions and captures the local shape of the surface. After that, weighting functions (the partitions of unity) blend these local shape functions together. In the end, it adapts Octree subdivision to variations in view of the local shapes describing the vascular structure. The factors that limit its applications include the low rendering speed, high computation complexity and parameter-dependency. On the contrary, explicit methods only rely on vessel information, such as the centerline and radius.^14-17 Convolution Surfaces, an explicit method, utilizes the vascular axis and the local radius to generate smooth transition curved surfaces with high perceptual quality.¹⁷ However, it needs to define a proper kernel function.

In most possible situations, real-time vascular reconstruction is critical, although it is difficult and challenging. Because of high computational complexity, a trade-off between real-time ability and high-quality visualization is always achieved. Wu et al. proposed an up-vector algorithm that transfers the bending degree and avoids distortion in vessel surface and branches.¹⁴ This algorithm runs fast, but the up-vector is derived from random generation and lacks of robustness. In this paper, we present a simple and effective method for up-vector generation. The proposed method reconstructs vascular structure in real-time speed and guarantees the smoothness in volumetric rendering. More importantly, it is accurate on localizing the malformations in clinical cases of vascular stenosis disease.

Materials and methods

Aneurisk database (http://ecm2.mathcs.emory.edu/aneuriskweb/index) and clinical cases are involved in this study. Aneurisk is a publicly available repository and provides prior vascular information of the centerline coordinates and the local radius. The clinical cases were approved by the Institutional Review Board of Shenzhen Institutes of Advanced Technology. Written informed consent was obtained from all participants. These data could only be accessed to the physicians and researchers to ensure participant confidentiality.

The proposed method consists of bash mesh generation and the Loop subdivision algorithm for refinement. Each step is described as below.

Base mesh

Generating the base mesh to form a vascular tree is the first step for vascular reconstruction. In order to determine the coordinates of each 4 vertices of the quadrilateral base mesh, the directional vector and its normal vector are computed and illustrated in Fig. 1.

Figure 1. Adjacent vector projections for the coordinate computation of each 4 vertices in the quadrilateral base mesh. (A) illustrates the directional and the normal vectors, and (B) is the up-vector for the vascular centerline.

Suppose $n$ points $\{P_0,P_1,\mathrm{\dots },P_{n-1}\}$ constitute a vessel segment as shown in Fig. 1(A). How to calculate the directional and the normal vectors is respectively in Eq. 1(1) $\overrightarrow{di{r}_i}={(P_{i+1}-P_i)}^0$(1) and Eq. 2(2) $\begin{array}{l}\overrightarrow{n_0}={\overrightarrow{di{r}_0}}^{\perp }\\ \overrightarrow{n_j}=(\overrightarrow{di{r}_{j+1}}+\overrightarrow{di{r}_j}{)}^{\perp }\\ \overrightarrow{n_{n-1}}={\overrightarrow{di{r}_{n-1}}}^{\perp }\end{array}$(2) , where $A^0$ stands for the normalization operation, and $\perp$ indicates perpendicular operation.

1. Directional vector. Based on $\{P_0,P_1,\mathrm{\dots },P_{n-1}\}$, the directional vector for each adjacent point pair is computed in Eq. 1(1) $\overrightarrow{di{r}_i}={(P_{i+1}-P_i)}^0$(1) where $i=0,\mathrm{\dots },n-2$.(1) $\overrightarrow{di{r}_i}={(P_{i+1}-P_i)}^0$(1)

2. Normal vector. The normal vectors are computed based on derived directional vectors of $\{\overrightarrow{di{r}_0},\mathrm{\dots },\overrightarrow{di{r}_{n-2}}\}$ as shown in Eq. 2(2) $\begin{array}{l}\overrightarrow{n_0}={\overrightarrow{di{r}_0}}^{\perp }\\ \overrightarrow{n_j}=(\overrightarrow{di{r}_{j+1}}+\overrightarrow{di{r}_j}{)}^{\perp }\\ \overrightarrow{n_{n-1}}={\overrightarrow{di{r}_{n-1}}}^{\perp }\end{array}$(2) where $j=0,\mathrm{\dots },n-2$.(2) $\begin{array}{l}\overrightarrow{n_0}={\overrightarrow{di{r}_0}}^{\perp }\\ \overrightarrow{n_j}=(\overrightarrow{di{r}_{j+1}}+\overrightarrow{di{r}_j}{)}^{\perp }\\ \overrightarrow{n_{n-1}}={\overrightarrow{di{r}_{n-1}}}^{\perp }\end{array}$(2)

Because of the extrusion of viscera and near-by tissues, blood vessels are prone to large deformation or distortions. To avoid distortions of vessel surface and branches in the process of vascular reconstruction, up-vector is introduced. The up-vector of last plane is projected to its next plane and then an up-vector is computed in the next plane. It ensures that 2 adjacent cross-sections form a truncated cone. The same operation is used in each vascular segment and branch that can effectively avoid discontinuity or distortion problems in high-curvature branches.

The whole process of up-vector implementation is described as following. Select a unit length vector $\overrightarrow{u}=(u_0,u_1,u_2)$ that is perpendicular to a normal vector $\overrightarrow{n}=(n_0,n_1,n_2)$. Since $\overrightarrow{u}$ has a zero component, we choose $\overrightarrow{u}=(u_0,u_1,0)$ for simplicity. Because $⟨\overrightarrow{u},\overrightarrow{n}⟩=0=u_0{n}_0+u_1{n}_1$, $\overrightarrow{u}$ can be expressed as a vector of unit length, i.e., $\overrightarrow{u}=\frac{(n_0,n_1,0)}{\sqrt{{(n_0)}^2+{(n_1)}^2}}$ where $n_0$ and $n_1$ are not all zero. It is observed that the unit vector $\overrightarrow{u}$ is determined by the normal vector $\overrightarrow{n}$. It is also found choosing the zero component of $\overrightarrow{u}$ based on the vector $\overrightarrow{n}$ is comparatively reasonable. So if $n_0\le n_1$,$u_0=0$, $u_1=n_2$ and $u_2=-n_1$; or else, $u_0=n_2$, $u_1=0$ and $u_2=-n_0$. While the third vector $\overrightarrow{v}$ is determined by $\overrightarrow{v}=\overrightarrow{u}\times \overrightarrow{n}$, the up-vector $\overrightarrow{uv}$ is equal to $\overrightarrow{uv}=r(\overrightarrow{u}+\overrightarrow{v})$ where $r$ is the radius of vascular slice.

According to the parameter equation of the plane, the parameters of the quadrilateral vertex coordinates are determined by Eq. 3(3) $\begin{array}{l}{V}_0=C+r(\overrightarrow{u}+\overrightarrow{v})\\ V_1=C-r(\overrightarrow{u}-\overrightarrow{v})\\ V_2=C-r(\overrightarrow{u}+\overrightarrow{v})\\ V_2=C-r(\overrightarrow{u}-\overrightarrow{v})\end{array}$(3) , in which $C$ is the center coordinates.(3) $\begin{array}{l}{V}_0=C+r(\overrightarrow{u}+\overrightarrow{v})\\ V_1=C-r(\overrightarrow{u}-\overrightarrow{v})\\ V_2=C-r(\overrightarrow{u}+\overrightarrow{v})\\ V_2=C-r(\overrightarrow{u}-\overrightarrow{v})\end{array}$(3)

Loop subdivision

The Loop subdivision algorithm is utilized to form the base mesh surface of blood vessel.¹⁸ Surface generated by Loop subdivision has demonstrated that the formation of Loop subdivision algorithm reaches $G_2$ continuity on non-singular points and achieves $G_1$ continuity at singular points. According to the vertex coordinates of base mesh, the new edge point and the new vertex can be computed by Loop subdivision algorithm in Eq. 4 and Eq. 5, respectively.

(1)

New edge point. Suppose that there are 2 vertices in polygon internal edges and the edge is shared by the triangles of $(v_0,v_1,v_2)$ and $(v_0,v_1,v_3)$. New edge point $v_{edge}$ is computed by Eq. 4(4) $v_{edge}=\frac{3}{8}(v_0+v_1)+\frac{1}{8}(v_2+v_3)$(4) .(4) $v_{edge}=\frac{3}{8}(v_0+v_1)+\frac{1}{8}(v_2+v_3)$(4)

(2)

New vertices. Suppose that internal vertex is $v$ and its adjacent vertexes are $\{v_0;v_1;\mathrm{\dots };v_n\}$. So the new vertex $v_{vert}$ is computed in Eq. 5(5) $v_{vert}=(1-n{\beta }_n)v+{\beta }_n{\displaystyle \sum _{i=1}^{n-1}{v}_i}$(5) . When $n=3$, ${\beta }_n=\frac{3}{16}$, while when $n>3$, ${\beta }_n=\frac{3}{8n}$.(5) $v_{vert}=(1-n{\beta }_n)v+{\beta }_n{\displaystyle \sum _{i=1}^{n-1}{v}_i}$(5)

The new edge vertex on the boundary edge $(v_0,v_1)$ is taken the midpoint position $v_{edge}=\frac{1}{2}(v_0+v_1)$. And if the adjacent vertex of $v_{vert}$ on boundary edge is vertices $(v_0,v_1)$, then the new vertex is computed as $v_{vert}=\frac{1}{8}(v_0+v_1+6v)$.

Results

Based on Aneurisk, an online database, the proposed algorithm is systematically verified. The procedure of blood vascular reconstruction and its real-time capacity are demonstrated. Then reconstructed vascular trees with high-tortuosity segments are highlighted and compared with the rendering results from Aneurisk. Moreover, the capacity of pinning the malformations in clinical cases of vascular stenosis disease is presented.

Loop subdivision

The procedure of a vessel segment with iterative Loop subdivision is shown in Fig. 2, where (A) presents the base meshes of blood vessel, (B), (C) and (D) corresponds to the subdivision results after the first, the second and the third iteration. In contrast to the base mesh, vascular surface progressively becomes smooth and vascular deformation is naturally transformed. After the third Loop subdivision, the morphology and the structure of the vascular segment get plump.

Figure 2. Loop subdivision. The reconstructed results are shown from the base mesh (A), the first subdivision (B), the third subdivision (C), and the fourth subdivision (D).

Real-time capacity

In each iteration step, the number of vertices and triangles increase dramatically, and the computing time prolongs (Table 1). Total time spent on blood vascular reconstruction is about 300 ms after the third Loop subdivisions. Through auxiliary hardware acceleration and parallel programming implementation, this method can be further speeded up and meets the real-time requirements of clinical applications.

For real-time requirements, 3 iteration subdivisions are suggested for this algorithm, not only achieving high perceptual quality with smooth surface, but also satisfying the real-time rendering when the number of triangles increases greatly.

Perceived vascular segment quality

Five reconstructed segments are perceived in Fig. 3. Several vessels are with large curvatures on the bifurcation position, such as the branches. In (A), the first point on the vessel centerline generates the up-vector which is transmitted to its following vascular structure without distortion. (B), (C) and (D) indicate that the up-vector can be naturally transmitted to each connected branch. It is observed that the proposed method avoids vascular distortions and warrants smooth transition of vessels in the high curvature regions in the subdivision process. Note that a branch with spatial continuity is useful in topology preservation and shape modeling.

Figure 3. Perceived vascular qualities of 5 segments with high tortuosity. The topology information is well preserved and transmitted between different vascular bifurcations.

Vessel tree visualization

The volumetric visualization of the reconstructed vessel structures is shown in Fig. 4 where the left column shows the vascular maps from Aneurisk, the middle presents the generated vascular trees with our method and displays the vessels from 3 different angles, and the right column displays 2 Amplified segments with large curvatures in the middle column. Compared to Aneurisk, the proposed algorithm reveals better rendering quality of the radius, curvature information and structure topology of vessel trees.

Figure 4. Vessel tree visualization. The left is vascular maps from Aneurisk, the middle presents the generated vascular trees with the proposed method from 3 different angles, and the right displays the amplified segments for observation purpose.

Localization of vascular stenosis

One clinical case of vascular stenosis is shown in Fig. 5 where black arrows direct to the position of the vascular stenosis. The estimated vascular centerline, the generated bash mesh and the reconstructed vascular tree are presented from the left to the right, respectively.

Figure 5. A clinical case of reconstructed vascular stenosis. (A) Estimated vascular centerline, (B) the generated bash mesh and (C) vascular reconstruction with Loop subdivision.

Furthermore, a performance comparison between the proposed method and MUPI is show in Fig. 6 where (A) is the visualization from VolView (www.kitware.com/opensource/volview.html); (B) is from the proposed method, and (C) is from MPUI.

Figure 6. Comparison between the proposed up-vector algorithm and MPUI.

The proposed algorithm outperforms MPUI from 3 aspects. First, the proposed algorithm is more accurate. Comparing subplot 3 and 3’ shows that a discontinuity is missed by MPUI while our method clearly unearths it for clinical observation. Moreover, it takes about 300 ms to finish the vascular reconstruction with the up-vector method, while more than 25 s with MPUI. In addition, the proposed algorithm is based on direct computation while MPUI depends on proper parameter settings.

Discussion

Precise localization of vascular stenosis is a fundamental task in disease diagnosis and stents placement. This paper proposed a simple and robust algorithm for precise localization of vascular malformations based on adjacent vector projection and prior knowledge. The algorithm can reconstruct the vascular structure with preserved morphology and topology consistency in real time. It benefits accurate pinning of the hemadostenosis and wide applications. In the future work, we will refine this algorithm and quantitatively compare it with other methods.

Table 1. Real-time capacity when Loop subdivision carried out.

	Time (ms)	Number of vertices	Number of triangles
Bash mesh	0	1,192	2,368
After 1^st Loop	31	4,752	9,472
After 2^nd Loop	94	18,976	37,888
After 3^rd Loop	297	75,840	151,552

Disclosure of potential conflicts of interest

No potential conflicts of interest were disclosed.

Funding

This work is supported by grants from National Natural Science Foundation of China (Grant No. 81501463), Guangdong Innovative Research Team Program (Grant No. 2011S013), National 863 Programs of China (Grant No. 2015AA043203) and Shenzhen Fundamental Research Program (Grant Nos. JCYJ20140417113430726, JCYJ20140417113430665 and JCYJ201500731154850923) and Beijing Center for Mathematics and Information Interdisciplinary Sciences.