Abstracts

Automatic Reconstruction of the Arterial and Venous Trees on Volumetric Chest CT

Seyoun Park, Sang Min Lee, Namkug Kim, Joon Beom Seo, Hayong Shin

Medical Physics, vol. 40(7), 071906

Abstract

Purpose: This paper introduces a novel approach to classify pulmonary arteries and veins from volumetric chest computed tomography (CT) images. Although there is known to be a relationship between the alteration of vessel distributions and the progress of various pulmonary diseases, there has been relatively little research on the quantification of pulmonary vessels in vivo due to morphological difficulties. In particular, there have been few efforts to quantify the morphology and distribution of only arteries or veins through automated algorithms despite the clinical importance of such work. In this study, the authors classify different types of vessels by constructing a tree structure from vascular points while minimizing the construction cost using the vascular geometries and features of CT images.

Methods: First, a vascular point set is extracted from an input volume and the weights of the points are calculated using the intensity, distance from the boundaries, and the Laplacian of the distance field. The tree construction cost is then defined as the summation of edge connection costs depending on the vertex weights. As a solution, the authors can obtain a minimum spanning tree whose branches correspond to different vessels. By cutting the edges in the mediastinal region, branches can be separated. From the root points of each branch, the cut region is regrouped toward the entries of pulmonary vessels in the same framework of the initial tree construction. After merging branches with the same orientation as much as possible, it can be determined manually whether a given vessel is an artery or vein. Our approach can handle with noncontrast CT images as well as vascular contrast enhanced images.

Results: For the validation, mathematical virtual phantoms and ten chronic obstructive pulmonary disease (COPD) noncontrast volumetric chest CT scans with submillimeter thickness were used. Based on experimental findings, the suggested approach shows 9.18 ± 0.33 (mean ± SD) visual scores for ten datasets, 91% and 98% quantitative accuracies for two cases, a result which is clinically acceptable in terms of classification capability.

Conclusions: This automatic classification approach with minimal user interactions may be useful in assessing many pulmonary disease, such as pulmonary hypertension, interstitial lung disease and COPD.

Hybrid Grid Generation for Viscous Flow Analysis

Seyoun Park, Byungduk Jeong, Jin-Gyu Lee, Hayong Shin*

International Journal for Numerical Methods in Fluids, vol. 71(7), pp. 891-909, 2013

Abstract

Cartesian grid with cut-cell method has drawn attention of CFD researchers due to its simplicity. However, it suffers from the accuracy near the boundary of objects especially when applied to viscous flow analysis. Hybrid grid consisting of Cartesian grid in the background, body-fitted layer near the object, and transition layer connecting the two is an interesting alternative. In this paper, we propose a robust method to generate hybrid grid in 2D and 3D space for viscous flow analysis. In the first step, body-fitted layer made of quadrangles (in 2D) or prisms (in 3D) is created near the object’s boundary by extruding front nodes with a speed function depending on the minimum normal curvature obtained by quadric surface fitting. To solve global interferences effectively, a level set method is used to find candidates of colliding cells. Then, axis-aligned Cartesian grid (quadtree in 2D or octree in 3D) is filled in the rest of the domain. Finally, the gap between body-fitted layer and Cartesian grid is connected by transition layer composed of triangles (in 2D) or tetrahedrons (in 3D). Mesh in transition layer is initially generated by constrained Delaunay triangulation from sampled points based on size function and is further optimized to provide smooth connection. Our approach to automatic hybrid grid generation has been tested with many models including complex geometry and multi-body cases, showing robust results in reasonable time.

Efficient Generation of Adaptive Cartesian Mesh for Computational Fluid Dynamics using GPU

Seyoun Park, Hayoung Shin*

International Journal for Numerical Methods in Fluids, vol 70(11), pp.1393-1404, 2012

Abstract

Mesh generation has been frequently the most time consuming step in typical CFD analysis studies. In the past two decades, adaptive Cartesian mesh methods have gained increasing popularity among CFD researches, mainly because of its simplicity and the possibility of automating mesh generation step. In contrast to body-fitted mesh, cells in Cartesian mesh are aligned with coordinate axes. In adaptive Cartesian mesh, cells near the objects’ boundary are recursively refined using quad-tree (two-dimensional) or octree (three-dimensional). Then, cells intersecting the objects’ boundary are clipped by the surfaces, leaving numerous small irregular shaped cells, called cut-cells. Most of the computational efforts required to generate adaptive Cartesian mesh is concentrated on the cut-cell clipping operation. To achieve the computational accuracy in the subsequent numerical solver, the number of cut-cells can be easily over millions, demanding substantial amount of computation time. Reducing mesh generation time matters more especially for unsteady flow simulation involving moving objects, which requires frequent regeneration of meshes for varied postures of the object. In this paper, we report an efficient novel approach to generating adaptive Cartesian mesh by parallelization using the graphics processing unit. The proposed method consists of the following three steps: (1) computing cross-sectional curves of object boundary, (2) octree refinement based on the section curves, and (3) cut-cell clipping. Because each step is designed to be highly parallelizable, we also implemented it on a graphics processing unit, showing orders of magnitude faster performance than the CPU version.

Machining Tool Path Generation for Point Set

Seyoun Park, Hayong Shin*

International Journal of CAD/CAM, vol. 8, 2008

Abstract

As the point sampling technology evolves rapidly, there has been increasing need in generating tool path from dense point set without creating intermediate models such as triangular meshes or surfaces. In this paper, we present a new tool path generation method from point set using Euclidean distance fields based on Algebraic Point Set Surfaces (APSS). Once an Euclidean distance field from the target shape is obtained, it is fairly easy to generate tool paths. In order to compute the distance from a point in the 3D space to the point set, we locally fit an algebraic sphere using moving least square method (MLS) for accurate and simple calculation. This process is repeated until it converges. The main advantages of our approach are : (1) tool paths are computed directly from point set without making triangular mesh or surfaces and their offsets, and (2) we do not have to worry about no local interference at concave region compared to the other methods using triangular mesh or surface model. Experimental results show that our approach can generate accurate enough tool paths from a point set in a robust manner and efficiently.

Voronoi Diagram of a Polygon in Chessboard Metric and Maskless Lithographic Applications

Hayong Shin*, Seyoun Park, Eonjin Park, Deok-Soo Kim

International Journal of Computational Geometry and Applications, vol. 18(4), pp.357-371, 2007

Abstract

Lithography using photomasks has been the major workhorse in manufacturing printed circuit boards, semiconductors, and flat panel display devices. However, the cost of photomask is so high that it often becomes the bottleneck, especially when the production volume is low. For this reason, maskless lithography technology is recently gaining more attention, and hence, the computation of efficient lithography path becomes of greater importance than ever in order to obtain high throughput of lithography process. The target machine of this paper has a numerically controlled XY table on which a substrate is located and a variable size (square-shape) aperture in front of the light source. In this paper, we present an approach to efficient lithography path generation using Voronoi diagram and medial axis transform in chessboard metric. The properties and construction method of Voronoi diagram of a polygonal object in chessboard metric are examined. Then, lithography path generation scheme is explained. The proposed idea can also be applied to the fabrication of photomask itself and the rapid prototyping of a 3D model via layered lithography.