email:
(303) 384-2135
Research interests
|
|
Andrzej Szymczak, Arthur Stillman and Allen Tannenbaum
We propose an algorithm for building 3D models of the airway tree from Computed Tomographic (CT) images. Our procedure first computes a set of core points that tend to concentrate along the centerlines of the airway tree branches. This point set, after a filtering step, is used to build a set of wall points that concentrate on the walls of the airways. Finally, a triangulated surface is build from the wall points using a Delaunay-based reconstruction procedure. |
|
|
|
Jaeil Choi and Andrzej Szymczak
Computing correspondence between the time frames of a time-dependent 3D surface is essential for the understanding of its motion and deformation. In particular, it can be a useful tool in compression, editing, texturing or analysis of the physical or structural properties of deforming objects. The correspondence information is usually explicitly present in synthetic animations, but it is not in experimentally acquired 3D animations, such as visual hull data (typically represented as either a binary occupancy grid or as a sequence of meshes of varying connectivity). In this paper we present a new non-rigid fitting method that can compute such correspondence information for objects that do not undergo large volume or topological changes, like living creatures or humans. Experimental results show that it is robust enough to handle realistic visual hull data, allowing one to convert it into a constant connectivity mesh with vertices moving in time. Our procedure first creates a rest state mesh from one of the input frames. That rest state mesh is then fitted to the consecutive frames. We do that by iteratively displacing its vertices so that a combination of surface distance and elastic potential energy is minimized. |
|
|
|
Andrzej Szymczak and James Vanderhyde
The paper describes a simple algorithm that allowing one to compute a perturbation of a regularly sampled volume dataset that simplifies its topological structure while being bounded by a user-defined threshold. The resulting volume has smaller number of critical points, its isosurfaces (for all isovalues) tend to be topologically simpler (i.e. have smaller Betti numbers). The contour trees of the volume become simpler and therefore easier to comprehend. |
|
|
|
James Vanderhyde and Andrzej Szymczak
Volumetric data, such as output from laser range scans and CT scans, often contain topological noise-small handles and holes that are not present in the original model. Because this noise can significantly degrade the performance of other geometric processing algorithms, we present a volumetric method that removes the topological noise and patches holes in undefined regions for a given isovalue in the volume. We start with a surface completely inside the model and a surface completely outside the model. Then the surfaces are expanded and contracted, respectively, on a voxelby- voxel basis. Changes in topology of the surfaces are prevented at every step using a local topology test. The result is a pair of surfaces that accurately reflect the model but have simple topology. We represent the model in an octree format for improved performance in space and time. |
|
 |
For time-dependent scalar fields, one is often interested in topology changes of contours in time. In this paper, we focus on describing how contours split and merge over a certain time interval. Rather than attempting to describe all individual contour splitting and merging events, we focus on the simpler and therefore more tractable in practice problem: describing and querying the cumulative effect of the splitting and merging events over a user-specified time interval. Using our system one can, for example, find all contours at time t_0 that continue to two contours at time t_1 without hitting the boundary of the domain. Experimental results show that our method can handle large 3D (2 space dimensions plus time) and 4D (3D+time) datasets. Both preprocessing and query algorithms can easily be parallelized. |
|
 |
Andrzej Szymczak, Allen Tannenbaum and Konstantin Mischaikow
Our algorithm first extracts persistent maxima of the intensity on all axis-aligned two-dimensional slices through the input volume. Those maxima tend to concentrate along one-dimensional intensity ridges, in particular along blood vessels. We build a minimum forest based on the persistent maxima that uses only short edges and apply simple geometric operations to clean up its short or spurious branches and build connections through gaps in the blood vessels. The algorithm is applied to reconstruct coronary vessel trees from CT scans. |
|
|
|
Nathanael Berglund and Andrzej Szymczak,
We describe a simple and efficient algorithm for computing a variant of contour tree that carries information about the number of connected components of the intersection of a contour and a fixed simply connected subdomain (i.e. simplicial subcomplex of the domain). The algorithm requires O(n+tlog t) time, where n is the size of the input grid $t$ is the sum of numbers of critical points in the domain and the subdomain. We show how to use our algorithm to label the edges of the contour tree of a 3D scalar field with complete information on the topology of the corresponding contours in time O(n+t log t). |
|
 |
Optimized Edgbreaker
Encoding for Large and Regular Triangle Meshes An Edgebreaker-based
efficient compression scheme for regular meshes
(co-authored by Davis King and Jarek Rossignac) The connectivity of a typical triangle mesh representing a 3D object for a graphics or geometric modeling application exhibits a lot of regularity. While a lot of aspects of triangle mesh regularity have not been formally described, the simplest regularity measure is the compactness of the distribution of vertex degrees. In a regular mesh, most of the vertices have degree 6 or close to 6. In this paper we present a technique designed to improve the compression of the Edgebreaker CLERS string built upon our previous theoretical developments aiming to improve the worst case compression ratios for highly regular meshes. Our algorithm does not alter the Edgebreaker execution path: it only uses a specially designed context based coding to compress the CLERS sequence. Therefore, it is exceptionally simple to implement and can easily incorporated into any existing Edgebreaker implementation which uses the Spirale Reversi algorithm for decompression. We present experimental results showing that our procedure is very fast (600,000 triangles per second on PIII 650MHz for decompression) and leads to compression rates which are, in most cases, superior to those previously reported for large meshes of high regularity. |
|
 |
Andrzej Szymczak and James Vanderhyde Extraction of
topologically simple isosurfaces from volume datasets, There are numerous algorithms in graphics and visualization whose performance is known to decay as the topological complexity of the input increases. On the other hand, the standard pipeline for 3D geometry acquisition often produces 3D models that are topologically more complex than their real forms. We present a simple and effcient algorithm that allows us to simplify the topology of an isosurface by altering the values of some number of voxels. Its utility and performance are demonstrated on several examples, including signed distance functions from polygonal models and CT scans. |
|
 |
Lawrence Ibarria, Peter Lindstrom, Jarek Rossignac and Andrzej Szymczak Out-of-core compression and
decompression of large n-dimensional scalar fields We present a simple method for compressing very large and regularly sampled scalar fields. Our method is particularly attractive when the entire data set does not fit in memory and when the sampling rate is high relative to the feature size of the scalar field in all dimensions. Although we report results for R^3 and R^4 data sets, the proposed approach may be applied to higher dimensions. The method is based on the new Lorenzo predictor, introduced here, which estimates the value of the scalar field at each sample from the values at processed neighbors. The predicted values are exact when the n-dimensional scalar field is an implicit polynomial of degree n-1. Surprisingly, when the residuals (differences between the actual and predicted values) are encoded using arithmetic coding, the proposed method often outperforms wavelet compression in an L-infinity sense. The proposed approach may be used both for lossy and lossless compression and is well suited for out-of-core compression and decompression, because a trivial implementation, which sweeps through the data set reading it once, requires maintaining only a small buffer in core memory, whose size barely exceeds a single (n-1)-dimensional slice of the data. |
|
 |
Andrzej Szymczak, Davis King and Jarek Rossignac Piecewise Regular Meshes:
Construction and Compression We present an algorithm which splits a 3D surface into reliefs, relatively flat regions that have smooth boundaries. The surface is then resampled in a regular manner within each of the reliefs. As a result, we obtain a piecewise regular mesh (PRM), having a regular structure on large regions. Experimental results show that we are able to approximate the input surface with the mean square error of about 0.01-0.02 per cent of the diameter of the bounding box without increasing the number of vertices. We introduce a compression scheme tailored to work with our remeshed models and show that it is able to compress them losslessly (after quantizing the vertex locations) without significantly increasing the approximation error using about 4 bits per vertex of the resampled model. |
|
 |
Andrzej Szymczak and Jarek Rossignac Grow&Fold: Compressing
the Connectivity of Tetrahedral Meshes Standard representations of irregular finite element meshes combine vertex data (sample coordinates and node values) and connectivity (tetrahedron-vertex incidence). Connectivity, specifies how the samples should be interpolated. It may be encoded for each tetrahedron as four vertex-references, which together occupy 128 bits. For simple 3D meshes with a single scalar value per node, non-compressed vertex data occupies 14 times less storage. Our `Grow&fold' format reduces the connectivity storage down to 7 bits per tetrahedron: 3 of these are used to encode the presence of children in a tetrahedron spanning tree; the other 4 constrain sequences of `folding' operations, so that they produce the connectivity graph of the original mesh. Additional bits must be used for each handle in the mesh and for each topological `lock' in the tree. By storing vertex data in an order defined by the tree, we avoid the need to store tetrahedron-vertex references, and facilitate variable coding techniques for the vertex data. We provide the details of simple, loss-less compression and decompression algorithms and describe implementation results. |
