Novel 3D Binary Indexed Tree for Volume Computation of 3D Reconstructed Models from Volumetric Data

Quoc-Bao Nguyen-Le, Tuan-Hy Le, Anh-Triet Do · 2024

Read Novel 3D Binary Indexed Tree for Volume Computation of 3D Reconstructed Models from Volumetric Data by Quoc-Bao Nguyen-Le, Tuan-Hy Le, Anh-Triet Do (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-10441.txt.

Introduction

Nguyen-Le, Le and Do present in 2024 an algorithm that computes the volume of 3D models rebuilt from CT or MR scans. It combines the marching cubes method with a 3D binary indexed tree, also called a Fenwick tree. The structure is built in scan-line order alongside reconstruction. That lets users query volumes quickly while slicing or transforming a model.

The team tested accuracy on simple shapes like spheres and cylinders, then on lungs and heart chambers. Errors stayed tiny in their trials. Fast, accurate volume measurement matters for medical imaging, where organ and lesion sizes guide diagnosis and treatment planning.

Catalog record

CREATORQuoc-Bao Nguyen-Le, Tuan-Hy Le, Anh-Triet Do
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-10441

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Novel 3D Binary Indexed Tree for Volume Computation of 3D Reconstructed Models from Volumetric Data Quoc-Bao Nguyen-Le, Tuan-Hy Le, Anh-Triet Do Abstract In the burgeoning field of medical imaging, precise computation of 3D volume holds a significant importance for subsequent qualitative analysis of 3D reconstructed objects. Combining multivariate calculus, marching cube algorithm, and binary indexed tree data structure, we developed an algorithm for efficient computation of intrinsic volume of any volumetric data recovered from computed tomography (CT) or magnetic resonance (MR). We proposed the 30 configurations of volume values based on the polygonal mesh generation method. Our algorithm processes the data in scan-line order simultaneously with reconstruction algorithm to create a Fenwick tree, ensuring query time much faster and assisting users’ edition of slicing or transforming model. We tested the algorithm’s accuracy on simple 3D objects (e.g., sphere, cylinder) to complicated structures (e.g., lungs, cardiac chambers). The result deviated within ± 0.004 ​ cm 3 \pm 0.004\text{cm}^{3} and there is still room for further improvement. 1 Introduction This research is one pivotal component in our larger research project ”Integration of Deep Learning into automatic cardiovascular dissection and reconstruction in simulated 3D space for medical practice”. Therefore, this research is mostly focused on medical volumetric data, especially human cardiac CT scans. In the contemporary landscape of medical imaging, the conversion of tomographic data into precise three-dimensional (3D) models stands as a burgeoning trend of paramount importance. Since three-dimensional surfaces of anatomy offer a valuable medical tool. The 3D representation helps physicians/radiologists with better interpretation of volumetric data [ 1 ] . The evolution in 3D medical imaging necessitates robust post-processing methodologies to ensure the meticulous measurement and analysis of these intricate 3D structures with utmost accuracy and efficiency [ 2 ] . Of particular significance is the quantification of various parameters within the cardiovascular system, including but not limited to the diameter, area, and volume of critical structures such as the aortic duct. These metrics serve as crucial indicators for pathologies such as hypertrophy or stenosis, which pose significant risks to patient well-being. Consequently, the accurate assessment and preoperative planning facilitated by such analyses substantially enhance the clinical efficacy and safety of surgical interventions. While existing software proficiently translates medical tomographic data into comprehensive 3D representations, the capability to perform volumetric analysis remains conspicuously absent, thereby warranting further advancements in this critical domain. 1.1 Data flow in algorithms 3D medical image reconstruction consists of 6 steps. The last feature is optional since it depends on the software application offering user advanced operations. Our software system starts from the second step to the last one. The post processing in consists of many advanced functions for radiologists to control 3D objects both on computer and in vritual reality environment. - Data Acquisition \rightarrow Image Processing \rightarrow Segmentation \rightarrow 3D Reconstruction \rightarrow Rendering & display \rightarrow Post processing 2 Related works Researchers have reported the application of 3D medical images in a variety of areas. The visualization of complex acetabular fractures, craniofacial abnormalities, and intracranial structure illustrate 3D’s potential for the study of complex bone structures. Applications in radiation therapy and surgical planning interactive 3D techniques combined with 3D surface images. Cardiac applications include artery visualization and non-graphic modeling applications to calculate surface area and volume. There is non-graphic modeling applications to calculate the surface area and volume of cardiac models in 1985 [ 3 ] . The Marching Cubes algorithm, proposed by Lorensen in 1987, is commonly used for 3D mesh reconstruction from CT scans. However, it has limitations due to a small lookup table. To address this, Lewiner [ 4 ] proposed an improved version with an extended lookup table, resolving the “cracks” issue. This development requires efficient automatic post analysis, especially measuring important parameters such as volume, surface area, curvature. [ 5 ] presents a system to measure limb volumes using 3D models from an infrared depth sensor. However, this method does not leverage advanced computed imaging (CT, MR) and may be affected by environmental factors. Intrinsic volume measurement techniques directly from digital 3D images have been explored [ 2 ] , but their computational complexity remains a challenge. 3 Methodology Since our main application is in medical imaging, especially cardiac volumetric data, we only focus practical experiment and analysis in this specific field. 3.1 Integral of surface functions Figure 1: Calculating the volume of the aortic duct by integrating the surface function We can determine whether the arterial duct is hypertrophied by comparing its volume to standard parameters. We intersect the aorta with two planes (P),(Q) using a symmetric ray Casting method. The limits a,b on the Ox axis of an object are (x=a,x=b,a\leq b) . A plane perpendicular to the Ox axis at point x and a\leq x\leq b intersects the object with a cross-sectional area of S(x) and the equation S(x) is continuous on the interval [a;b] . Thus, the volume of the upper heart chamber is calculated by the following integral formula: V=\int_{a}^{b}S(x)dx For a set of n slice images, we have S_{i} as the area of the i_{th} slice (1\leq i\leq n) . Approximating a function S(x) is not straightforward. We can use the Lagrange interpolation method. However, this approach has many limitations. Firstly, the approximation is only accurate if n\rightarrow\infty to ensure accuracy. This is practically infeasible because the number of slices n is usually not large enough (300\rightarrow 512) and is limited. Secondly, approximating a function is also a complex task, increasing algorithm’s processing time. 3.2 Inclusion and exclusion principle Double integral problem is an combination of multiple single integral problems. Initially, we divide the curved surface z=f(x,y) into surfaces S_{j},S_{j+1},\dots,S_{m} corresponding to each y_{j},y_{j+1},\dots,y_{m} where each surface S_{j} with fixed y_{j} represents a single integral problem. Finally, we sum up these surfaces S_{j} to calculate the volume V : D=\begin{cases}a\leq x\leq b\\ c\leq y\leq d\end{cases}\\ V=\int_{c}^{d}\begin{pmatrix}\int_{a}^{b}f(x,y)dx\end{pmatrix}dy=\int_{c}^{d}dy\int_{a}^{b}f(x,y)dx With inclusion and exclusion principal, we can measure the volume of predetermined structure. For example, When calculating the volume of the aortic arch, we divide this vessel into two parts: the upper half o_{1} and the lower half o_{2} so the domain D remains the same. The volume of the inner part will be V_{o}=V_{o_{1}}-V_{o_{2}} : V_{o}=V_{o_{1}}-V_{o_{2}}\\ V_{o}=\lim_{\Delta x_{i},y_{j}\rightarrow 0}\Sigma_{j=c}^{j=d}(\Sigma_{i=a}^{i=b}(z^{o_{1}}_{ij}-z^{o_{2}}_{ij})\Delta x_{i})\Delta y_{j} Figure 2: Calculating partial aortic arch volume with double integral Given a list of (x,y,z) vertices, the implementation of this approach computed the volume of tube structures accurately . However, we have to find a midsection to divide the object into two parts. Additionally, current software systems allows radiologists to perform surgical operations (e.g. slicing) or modifies the segmentation result leading to changes in the 3D reconstructed polygonal mesh, so algorithm must reprocess again. If denoting Q as the times of slicing or updating operation is performed, the time complexity will be O(Q\times(M\times N+S)) , where S represents the complexity of finding midsection path. This issue can be optimized with triple integral combined with binary indexed tree. 3.3 Triple integral Figure 3: Calculating the volume of an object with triple integration The concept of triple integration originates from dividing the object volume O into n very small rectangular prisms or cubes O_{i} with lengths, widths, and heights denoted as dx,dy,dz respectively. Approximating the volume of

Read the complete text