Andrzej Szymczak's Publications

Selected Publications

	Andrzej Szymczak Morse Connection Graphs for Piecewise Constant Vector Fields on Surfaces Computer Aided Geometric Design, to appear We describe an algorithm for constructingMorse Connection Graphs (MCGs) of Piecewise Constant (PC) vector fields on surfaces. The main novel aspect of our algorithm is its way of dealing with false positives that could arise when computing Morse sets from an inexact graph representation. First, our MCG does not contain trivial Morse sets that may not contain any vector field features, or contain features that cancel each other. Second, we provide a simple criterion that can be used to rigorously verify MCG edges, i.e. to determine if a respective connecting chain of trajectories indeed exists. We also introduce an adaptive refinement scheme for the transition graph that aims to minimize the number of MCG arcs that the algorithm is not able to positively verify.
	Andrzej Szymczak and Nicholas Brunhart-Lupo Nearly Recurrent Components in 3D Piecewise Constant Vector Fields Computer Graphics Forum, to appear; to be presented at EUROVIS 2012 We present an algorithm for computing nearly recurrent components, that represent areas of close to circulating or stagnant flow, for 3D piecewise constant (PC) vector fields defined on regular grids. Using a number of analytical and simulated data sets, we demonstrate that nearly recurrent components can provide interesting insight into the topological structure of 3D vector fields. Our approach is based on prior work on Morse decompositions for PC vector fields on surfaces and extends concepts previously developed with this goal in mind to the case of 3D vector fields defined on regular grids. Our contributions include a description of trajectories of 3D piecewise constant vector fields and an extension of the transition graph, a finite directed graph that represents all trajectories, to the 3D case. Nearly recurrent components are defined by strongly connected components of the transition graph.
	Andrzej Szymczak and Eugene Zhang Robust Morse Decompositions of Piecewise Constant Vector Fields, Appendices IEEE Transactions on Visualization and Computer Graphics, to appear In this paper, we introduce a new approach to computing a Morse decomposition of a vector field on a triangulated manifold surface. The basic idea is to convert the input vector field to a piecewise constant (PC) vector field, whose trajectories can be computed using simple geometric rules. To overcome the intrinsic difficulty in PC vector fields (in particular, discontinuity along mesh edges), we borrow results from the theory of differential inclusions. The input vector field and its PC variant have similar Morse decompositions. We introduce a robust and efficient algorithm to compute Morse decompositions of a PC vector field. Our approach provides sub-triangle precision for Morse sets. In addition, we describe a Morse set classification framework which we use to color code the Morse sets in order to enhance the visualization. We demonstrate the benefits of our approach with three well-known simulation data sets, for which our method has produced Morse decompositions that are similar to or finer than those obtained using existing techniques, and is over an order of magnitude faster.
	Andrzej Szymczak Stable Morse Decompositions for Piecewise Constant Vector Fields on Surfaces Supplementary material Computer Graphics Forum 30 (3), 851-860, 2011 Numerical simulations and experimental observations are inherently imprecise. Therefore, most vector fields of interest in scientific visualization are known only up to an error. In such cases, some topological features, especially those not stable enough, may be artifacts of the imprecision of the input. This paper introduces a technique to compute topological features of user-prescribed stability with respect to perturbation of the input vector field. In order to make our approach simple and efficient, we develop our algorithms for the case of piecewise constant (PC) vector fields. Our approach is based on a super-transition graph, a common graph representation of all PC vector fields whose vector value in a mesh triangle is contained in a convex set of vectors associated with that triangle. The graph is used to compute a Morse decomposition that is coarse enough to be correct for all vector fields satisfying the constraint. Apart from computing stableMorse decompositions, our technique can also be used to estimate the stability of Morse sets with respect to perturbation of the vector field or to compute topological features of continuous vector fields using the PC framework.
	Guoning Chen, Qingqing Deng, Andrzej Szymczak, Robert Laramee and Eugene Zhang Morse Set Classification and Hierarchical Refinement Using Conley Index IEEE Transactions on Visualization and Computer Graphics 18 (5), 767-782, 2012 Reliable analysis of vector elds is crucial for the rigorous interpretation of the ow data stemming from a wide range of engineering applications. Morse decomposition of a vector field has proven a useful topological representation that is more numerically stable than previous vector field skeletons. In this paper, we enhance the procedure of Morse decomposition and propose an automatic refinement scheme to construct the Morse Connection Graph (MCG) of a given vector eld in a hierarchical fashion. Our framework allows a Morse set to be re ned through a local update of the flow combinatorialization, which leads to a more detailed MCG. This refined MCG has consistent topology with the original MCG because the refinement is conducted locally. The computation is faster than the original t-map approach because we reuse the previous tracing information and perform only local updates. The classification of the exetracted Morse sets is a crucial step for the construction of MCG. In this work, we advocate the use of Conley index for the classification. Conley index is a more general characteristic than Poincare index for the classi cation of flow dynamics. We present a framework to compute the Conley index of an isolating block in a flow. In addition, an efficient algorithm for computing an upper bound of the Conley index of any given Morse set is introduced to assist the automatic refinement process. Furthermore, an improved visualization technique for MCG is described which conveys the classification information of different Morse sets with the aid of the visualization of their Conley indices. Finally, we apply the proposed techniques to a number of synthetic and simulation data sets to demonstrate their utility.
	Andrzej Szymczak A Categorical Approach to Contour, Split and Join Trees with Application to Airway Segmentation In: Topological Methods in Data Analysis and Visualization Pascucci, V.; Tricoche, X.; Hagen, H.; Tierny, J. (Eds.), 205-216, 2011 Contour, split and join trees can be defined as functors acting on the category of scalar fields, whose morphisms are value-preserving functions. The categorical definition provides a natural way to eficiently compute a variety of topological properties of all contours, sublevel or superlevel components in a scalar field. The result is a labeling of the contour, split or join tree and can be used to find all contours, sublevel or superlevel sets with desired properties. We describe an algorithm for airway segmentation from Computed Tomography (CT) scans based on this paradigm. It computes all sublevel components in thick slices of the input image that have simple topology and branching structure. The output is a connected component of the union of all such sublevel components. This procedure can be viewed as a local thresholding approach, where the local thresholds are determined based on topological analysis of sublevel sets.
	Andrzej Szymczak, William Hoff and Mohamed Mahfouz 3D Shape from Silhouette Points in Registered 2D Images Using Conjugate Gradient Method Medical Imaging 2010: Image Processing. Proceedings of the SPIE, Volume 7623, pp. 762316-762316-8, 2010 We describe a simple and robust algorithm for estimating 3D shape given a number of silhouette points obtained from two or more viewpoints and a parametric model of the shape. Our algorithm minimizes (in the least squares sense) the distances from the lines obtained by unprojecting the silhouette points to 3D to their closest silhouette points on the 3D shape. The solution is found using an iterative approach. In each iteration, we locally approximate the least squares problem with a degree-4 polynomial function. The approximate problem is solved using a nonlinear conjugate gradient solver that takes advantage of its structure to perform exact and global line searches. We tested our algorithm by applying it to reconstruct patient-specific femur shapes from simulated biplanar X-ray images.
	Michiel Schaap, Coert T. Metz, Theo van Walsum, Alina G. van der Giessen, Annick C. Weustink, Nico R. Mollet, Christian Bauer, Hrvoje Bogunovic, Carlos Castro, Xiang Deng, Engin Dikici, Thomas O'Donnell, Michel Frenay, Ola Friman, Marcela Hernandez Hoyos, Pieter H. Kitslaar, Karl Krissian, Caroline Kuhnel, Miguel A. Luengo-Oroz, Maciej Orkisz, Orjan Smedby, Martin Styner, Andrzej Szymczak, Huseyin Tek, Chunliang Wangr, Simon K. Warfield, Sebastian Zambal, Yong Zhang, Gabriel P. Krestin and Wiro J. Niessen Standardized evaluation methodology and reference database for evaluating coronary artery centerline extraction algorithms Medical Image Analysis, 13, 701-714, 2009 Efficiently obtaining a reliable coronary artery centerline from computed tomography angiography data is relevant in clinical practice. Whereas numerous methods have been presented for this purpose, up to now no standardized evaluation methodology has been published to reliably evaluate and compare the performance of the existing or newly developed coronary artery centerline extraction algorithms. This paper describes a standardized evaluation methodology and reference database for the quantitative evaluation of coronary artery centerline extraction algorithms. The contribution of this work is fourfold: (1) a method is described to create a consensus centerline with multiple observers, (2) well-defined measures are presented for the evaluation of coronary artery centerline extraction algorithms, (3) a database containing 32 cardiac CTA datasets with corresponding reference standard is described and made available, and (4) 13 coronary artery centerline extraction algorithms, implemented by different research groups, are quantitatively evaluated and compared. The presented evaluation framework is made available to the medical imaging community for benchmarking existing or newly developed coronary centerline extraction algorithms.
	Jaeil Choi and Andrzej Szymczak Fitting Solid Meshes to Animated Surfaces using Linear Elasticity ACM Transactions on Graphics, 28(1), 1-10, 2009 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.
	James Vanderhyde and Andrzej Szymczak Topological simplification of isosurfaces in volumetric data using octrees Graphical Models 70 (1-2), 16-31, 2008 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.
	Andrzej Szymczak, Arthur Stillman, Allen Tannenbaum and Konstantin Mischaikow Coronary vessel cores from 3D imagery: a topological approach Medical Image Analysis, 10(4), 548-559, 2006 We propose a simple method for reconstructing vascular trees from three-dimensional images. Our algorithm extracts persistent maxima of the intensity on all axis-aligned two-dimensional slices of the input image. The maxima concentrate along onedimensional intensity ridges, in particular along blood vessels. We build a forest connecting the persistent maxima with short edges. The forest tends to approximate the blood vessels present in the image, but also contains numerous spurious features and often fails to connect segments belonging to one vessel in low contrast areas. We improve the forest by applying simple geometric filters that trim short branches, fill gaps in blood vessels and remove spurious branches from the vascular tree to be extracted. Experiments show that our technique can be applied to extract coronary trees from heart CT scans.
	Andrzej Szymczak and James Vanderhyde Simplifying the topology of volume datasets: an opportunistic approach Technical Report GIT-GVU-05-09, 2005 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.
	Andrzej Szymczak Subdomain-aware contour trees and contour tree evolution in time-dependent scalar fields Shape Modeling International 2005, 136-144 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 Optimized Edgbreaker Encoding for Large and Regular Triangle Meshes Visual Computer 19(4), 271-278, 2003 A paper containing theoretical analysis of this prediction scheme: Andrzej Szymczak, Davis King and Jarek Rossignac An Edgebreaker-based efficient compression scheme for regular meshes Computational Geometry 20(1-2), 53-68, 2001 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, Proc. IEEE Visualization'2003, 67-74 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 Proc. Eurographics'2003, 343-348 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 Graphical Models 64(3-4), 183-198, 2002 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 Computer-Aided Design. 32(8-9), 527-538, 2000 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.