9015785
Brain Image Analysis Using Spherical Splines
We propose a novel technique based on spherical splines for brain surface representation and analysis. This research is strongly inspired by the fact that, for brain surfaces, it is both necessary and natural to employ spheres as their natural domains. We develop an automatic and efficient algorithm, which transforms a brain surface to a single spherical spline whose maximal error deviation from the original data is less than the user-specified tolerance. Compared to the discrete mesh-based representation, our spherical spline offers a concise (low storage requirement) digital form with high continuity (C n − − 1 continuity for a degree n spherical spline). Furthermore, this representation enables the accurate evaluation of differential properties, such as curvature, principal direction, and geodesic, without the need for any numerical approximations. Thus, certain shape analysis procedures, such as segmentation, gyri and sulci tracing, and 3D shape matching, can be carried out both robustly and accurately. We conduct several experiments in order to demonstrate the efficacy of our approach for the quantitative measurement and analysis of brain surfaces.
483980
Rational spherical splines for genus zero shape modeling
Traditional approaches for modeling a closed manifold surface with either regular tensor-product or triangular splines (defined over an open planar domain) require decomposing the acquired geometric data into a group of charts, mapping each chart to a planar parametric domain, fitting an open surface patch of certain degree to each chart, and finally, trimming the patches (if necessary) and stitching all of them together to form a closed manifold. In this paper, we develop a novel modeling method which does not need any cutting or patching operations for genus zero surfaces. Our new approach is founded upon the concept of spherical splines proposed by Pfeifle and Seidel. Our work is strongly inspired by the fact that, for genus zero surfaces, it is both intuitive and necessary to employ spheres as their natural domains. Using this framework, we can convert genus zero mesh to a single rational spherical spline whose maximal error deviated from the original data is less than a user-specified tolerance. With the rational spherical splines, we can model sharp features and edit both the global shape and the local details with ease. Furthermore, we can accurately compute the differential quantities without resorting to any numerical approximations. We conduct several experiments in order to demonstrate the efficacy of our approach for reverse engineering, shape modeling, and interactive graphics.
5843308
A C1 Globally Interpolatory Spline of Arbitrary Topology
Converting point samples and/or triangular meshes to a more compact spline representation for arbitrarily topology is both desirable and necessary for computer vision and computer graphics. This paper presents a C1 manifold interpolatory spline that can exactly pass through all the vertices and interpolate their normals for data input of complicated topological type. Starting from the Powell-Sabin spline as a building block, we integrate the concepts of global parametrization, affine atlas, and splines defined over local, open domains to arrive at an elegant, easy-to-use spline solution for complicated datasets. The proposed global spline scheme enables the rapid surface reconstruction and facilitates the shape editing and analysis functionality.
807866
Surface reconstruction with triangular B-splines
This paper presents a modeling technique for reconstructing a triangular B-spline surface from a set of scanned 3D points. Unlike existing surface reconstruction methods based on tensor-product B-splines which primarily generate a network of patches and then enforce certain continuity (usually, G/sup 1/ or C/sup 1/) between adjacent patches, our algorithm can avoid the complicated procedures of surface trimming and patching. In our framework, the user simply specifies the degree n of the triangular B-spline surface and fitting error tolerance /spl epsi/. The surface reconstruction procedure generates a single triangular B-spline patch that has C/sup n-1/ continuity over smooth regions and C/sup 0/ on sharp features. More importantly, all the knots and control points are determined by minimizing a linear combination of interpolation and fairness functionals. Examples are presented which demonstrate the effectiveness of the technique for real data sets.
11744887
Harmonic volumetric mapping for solid modeling applications
Harmonic volumetric mapping for two solid objects establishes a one-to-one smooth correspondence between them. It finds its applications in shape registration and analysis, shape retrieval, information reuse, and material/texture transplant. In sharp contrast to harmonic surface mapping techniques, little research has been conducted for designing volumetric mapping algorithms due to its technical challenges. In this paper, we develop an automatic and effective algorithm for computing harmonic volumetric mapping between two models of the same topology. Given a boundary mapping between two models, the volumetric (interior) mapping is derived by solving a linear system constructed from a boundary method called the fundamental solution method. The mapping is represented as a set of points with different weights in the vicinity of the solid boundary. In a nutshell, our algorithm is a true meshless method (with no need of specific connectivity) and the behavior of the interior region is directly determined by the boundary. These two properties help improve the computational efficiency and robustness. Therefore, our algorithm can be applied to massive volume data sets with various geometric primitives and topological types. We demonstrate the utility and efficacy of our algorithm in shape registration, information reuse, deformation sequence analysis, tetrahedral remeshing and solid texture synthesis.
15418267
Incorporating Rigid Structures in Non-rigid Registration Using Triangular B-Splines
For non-rigid registration, the objects in medical images are usually treated as a single deformable body with homogeneous stiffness distribution. However, this assumption is invalid for certain parts of the human body, where bony structures move rigidly, while the others may deform. In this paper, we introduce a novel registration technique that models local rigidity of pre-identified rigid structures as well as global non-rigidity in the transformation field using triangular B-splines. In contrast to the conventional registration method based on tensor-product B-splines, our approach recovers local rigid transformation with fewer degrees of freedom (DOFs), and accurately simulates sharp features (C0 continuity) along the interface between deformable regions and rigid structures, because of the unique advantages offered by triangular B-splines, such as flexible triangular domain, local control and space-varying smoothness modeling. The accurate matching of the source image with the target one is accomplished through the use of a variational framework, in which a composite energy, measuring the image dissimilarity and enforcing local rigidity and global smoothness, is minimized subject to pre-defined point-based constraints. The algorithm is tested on both synthetic and real 2D images for its applicability. The experimental results show that, by accurately modeling sharp features using triangular B-splines, the deformable regions in the vicinity of rigid structures are less constrained by the global smoothness regularization and therefore contribute extra flexibility to the optimization process. Consequently, the registration quality is improved considerably.
29901411
Bin Packing and Covering Problems with Rejection
In this paper we consider the following problems: We are given a set of n items {u1, i¾?, un}, each item ui is characterized by its size wi∈ 0,1] and its penalty/profit pii¾? 0, and a number of unit-capacity bins. An item can be either rejected, in which case we pay/get its penalty/profit, or put into one bin under the constraint that the total size of the items in the bin is not greater/smaller than 1. No item can be spread into more than one bin. The objective is to minimize/maximize the sum of the number of used/covered bins and the penalties/profits of all rejected items. We call the problems bin packing/covering with rejection penalties/profits, and denoted by BPR and BCR respectively. For the online BPR problem, we present an algorithm with an absolute competitive ratio of 2.618 while the lower bound is 2.343, and an algorithm with an asymptotic competitive ratio of arbitrarily close to 7/4 while the lower bound is 1.540. For the offline BPR problem, we present an algorithm with an absolute worst-case ratio of 2 while the lower bound is 3/2, and an algorithm with an asymptotic worst-case ratio of 3/2. For the online BCR problem, we show that no algorithm can have an absolute competitive ratio of greater than 0, and present an algorithm with an asymptotic competitive ratio of 1/2, which is the best possible. For the offline BCR problem, we also present an algorithm with an absolute worst-case ratio of 1/2 which matches the lower bound.
45341657
3-D Reconstruction of Macroscopic Optical Brain Slice Images
We present a method for reconstruction of macroscopic optical images of post-mortem brain slices to form a 3-D volume. This forms a key part of a series of procedures to allow post mortem findings to be accurately registered with MR images, and more generally provides a method for 3-D mapping of the distribution of pathological changes throughout the brain. In this preliminary work, four brains from a study of Creutzfeldt-Jakob disease were examined. After brain fixation, the pathologist cut coronal slices several mm thick through the brain. The anterior and posterior faces of each slice were photographed. We show that the 2-D co-registration of each such pair of images was most effectively obtained if the slice was placed in a jig before photographing. Fiducials on the jig were detected automatically and point-based rigid registration computed. For co-registration between slices, i.e., across a single cut, an intensity-based method for 2-D non-rigid registration is used which provided satisfactory results. By propagating the 2-D registrations through the volume and using the known slice thickness, the 3-D volume was reconstructed.
206892321
Building programmable routing service for sensor networks
Current routing services for sensor networks are application-specific. They are pre-configured into nodes, and thus have difficulty in adapting to different applications and network conditions. This paper describes a framework to build programmable routing services for sensor networks. This framework includes a parameter space that identifies both common and different properties among routing services. With this parameter space, different routing services can be obtained with small programming effort. A programmable routing architecture is proposed to maintain this parameter space and support energy-efficient service deployment. This paper presents implementation details of this programmable framework and shows simulation results.
2201352
On Mitigating Network Partitioning in Peer-to-Peer Massively Multiplayer Games
Recently, peer-to-peer infrastructure has been proposed to support massively multiplayer games in the literature. However, when underlying network partitions due to network outages, the game world will partition into several parallel game worlds and it is difficult and costly to merge them when the network partitions disappear. Existing approaches resort to a centralized server to arbitrate. Aiming at mitigating the effects brought by network partitions, we propose a fully distributed algorithm based on state-stack matching. Our theoretical analysis and numerical results show that our approach can resolve the merging issue at the least loss of game states with high probability.
28965598
A semantic matchmaker service on the grid
A fundamental task on the Grid is to decide what jobs to run on what computing resources based on job or application requirements. Our previous work on ontology-based matchmaking discusses a resource matchmaking mechanism using Semantic Web technologies. We extend our previous work to provide dynamic access to such matchmaking capability by building a persistent online matchmaking service. Our implementation uses the Globus Toolkit for the Grid service development, and exploits the monitoring and discovery service in the Grid infrastructure to dynamically discover and update resource information. We describe the architecture of our semantic matchmaker service in the poster.