0000000000535620
AUTHOR
Elmar Schömer
CUDA-Accelerated Alignment of Subsequences in Streamed Time Series Data
Euclidean Distance (ED) and Dynamic Time Warping (DTW) are cornerstones in the field of time series data mining. Many high-level algorithms like kNN-classification, clustering or anomaly detection make excessive use of these distance measures as subroutines. Furthermore, the vast growth of recorded data produced by automated monitoring systems or integrated sensors establishes the need for efficient implementations. In this paper, we introduce linear memory parallelization schemes for the alignment of a given query Q in a stream of time series data S for both ED and DTW using CUDA-enabled accelerators. The ED parallelization features a log-linear calculation scheme in contrast to the naive …
Voxel-based General Voronoi Diagram for Complex Data with Application on Motion Planning
One major challenge in Assembly Sequence Planning (ASP) for complex real-world CAD-scenarios is to find appropriate disassembly paths for all assembled parts. Such a path places demands on its length and clearance. In the past, it became apparent that planning the disassembly path based on the (approximate) General Voronoi Diagram (GVD) is a good approach to achieve these requirements. But for complex real-world data, every known solution for computing the GVD is either too slow or very memory consuming, even if only approximating the GVD.We present a new approach for computing the approximate GVD and demonstrate its practicability using a representative vehicle data set. We can calculate a…
A method for automatic forensic facial reconstruction based on dense statistics of soft tissue thickness.
In this paper, we present a method for automated estimation of a human face given a skull remain. The proposed method is based on three statistical models. A volumetric (tetrahedral) skull model encoding the variations of different skulls, a surface head model encoding the head variations, and a dense statistic of facial soft tissue thickness (FSTT). All data are automatically derived from computed tomography (CT) head scans and optical face scans. In order to obtain a proper dense FSTT statistic, we register a skull model to each skull extracted from a CT scan and determine the FSTT value for each vertex of the skull model towards the associated extracted skin surface. The FSTT values at p…
Completely randomized RRT-connect: A case study on 3D rigid body motion planning
Nowadays sampling-based motion planners use the power of randomization to compute multidimensional motions at high performance. Nevertheless the performance is based on problem-dependent parameters like the weighting of translation versus rotation and the planning range of the algorithm. Former work uses constant user-adjusted values for these parameters which are defined a priori. Our new approach extends the power of randomization by varying the parameters randomly during runtime. This avoids a preprocessing step to adjust parameters and moreover improves the performance in comparison to existing methods in the majority of the benchmarks. Our method is simple to understand and implement. …
Interactive simulation of one-dimensional flexible parts
Computer simulations play an ever growing role for the development of automotive products. Assembly simulation, as well as many other processes, are used systematically even before the first physical prototype of a vehicle is built in order to check whether particular components can be assembled easily or whether another part is in the way. Usually, this kind of simulation is limited to rigid bodies. However, a vehicle contains a multitude of flexible parts of various types: cables, hoses, carpets, seat surfaces, insulations, weatherstrips... Since most of the problems using these simulations concern one-dimensional components and since an intuitive tool for cable routing is still needed, w…
High quality conservative surface mesh generation for swept volumes
We present a novel, efficient and flexible scheme to generate a high quality mesh that approximates the outer boundary of a swept volume. Our approach comes with two guarantees. First, the approximation is conservative, i.e., the swept volume is enclosed by the generated mesh. Second, the one-sided Hausdorff distance of the generated mesh to the swept volume is upper bounded by a user defined tolerance. Exploiting this tolerance the algorithm generates a mesh that is adapted to the local complexity of the swept volume boundary, keeping the overall output complexity remarkably low. The algorithm is two-phased: the actual sweep and the mesh generation. In the sweeping phase we introduce a gen…
High Precision Conservative Surface Mesh Generation for Swept Volumes
We present a novel, efficient, and flexible scheme to generate a high-quality mesh that approximates the outer boundary of a swept volume. Our approach comes with two guarantees. First, the approximation is conservative, i.e., the swept volume is enclosed by the generated mesh. Second, the one-sided Hausdorff distance of the generated mesh to the swept volume is upper bounded by a user defined tolerance. Exploiting this tolerance the algorithm generates a mesh that is adapted to the local complexity of the swept volume boundary, keeping the overall output complexity remarkably low. The algorithm is two-phased: the actual sweep and the mesh generation. In the sweeping phase, we introduce a g…
Conservative swept volume boundary approximation
We present a novel technique for approximating the boundary of a swept volume. The generator given by an input triangle mesh is rendered under all rigid transformations of a discrete trajectory. We use a special shader program that creates offset geometry of each triangle on the fly, thus guaranteeing a conservative rasterization and correct depth values. Utilizing rasterization mechanisms and the depth buffer we then get a conservative voxelization of the swept volume (SV) and can extract a triangle mesh from its surface. This mesh is simplified maintaining conservativeness as well as an error bound measured in terms of the one-sided Hausdorff distance. For this we introduce a new techniqu…
A Complete, Exact and Efficient Implementation for Computing the Edge-Adjacency Graph of an Arrangement of Quadrics
International audience; We present a complete, exact and efficient implementation to compute the edge-adjacency graph of an arrangement of quadrics, i.e. surfaces of algebraic degree 2. This is a major step towards the computation of the full 3D arrangement. We enhanced an implementation for an exact parameterization of the intersection curves of two quadrics, such that we can compute the exact parameter value for intersection points and from that the edge-adjacency graph of the arrangement. Our implementation is complete in the sense that it can handle all kinds of inputs including all degenerate ones, i.e. singularities or tangential intersection points. It is exact in that it always comp…
GEM
The widespread use of digital sensor systems causes a tremendous demand for high-quality time series analysis tools. In this domain the majority of data mining algorithms relies on established distance measures like Dynamic Time Warping (DTW) or Euclidean distance (ED). However, the notion of similarity induced by ED and DTW may lead to unsatisfactory clusterings. In order to address this shortcoming we introduce the Gliding Elastic Match (GEM) algorithm. It determines an optimal local similarity measure of a query time series Q and a subject time series S. The measure is invariant under both local deformation on the measurement-axis and scaling in the time domain. GEM is compared to ED and…
Alignment of cone beam computed tomography data using intra-oral fiducial markers.
This article illustrates a new method to align and merge two partially overlapping volumes each of them generated by cone beam computed tomography (CBCT). The aggregate volume covers a larger area of investigation and is determined by localizing one fixed LEGO brick in both of the primal volumes. Based on the LEGO brick an approximate registration of the volumes is determined. Afterwards we improve the transformation by minimizing the difference in overlapping space. In this paper we present a method which automates these two steps and provides an aligned volume.
Local-Area-Learning Network: Meaningful Local Areas for Efficient Point Cloud Analysis
Research in point cloud analysis with deep neural networks has made rapid progress in recent years. The pioneering work PointNet offered a direct analysis of point clouds. However, due to its architecture PointNet is not able to capture local structures. To overcome this drawback, the same authors have developed PointNet++ by applying PointNet to local areas. The local areas are defined by center points and their neighbors. In PointNet++ and its further developments the center points are determined with a Farthest Point Sampling (FPS) algorithm. This has the disadvantage that the center points in general do not have meaningful local areas. In this paper, we introduce the neural Local-Area-L…
Complete, Exact and Efficient Implementation for Computing the Adjacency Graph of an Arrangement of Quadrics
The original publication is available at www.springerlink.com ; ISBN 978-3-540-75519-7 ; ISSN 0302-9743 (Print) 1611-3349 (Online); International audience; We present a complete, exact and efficient implementation to compute the adjacency graph of an arrangement of quadrics, \ie surfaces of algebraic degree~2. This is a major step towards the computation of the full 3D arrangement. We enhanced an implementation for an exact parameterization of the intersection curves of two quadrics, such that we can compute the exact parameter value for intersection points and from that the adjacency graph of the arrangement. Our implementation is {\em complete} in the sense that it can handle all kinds of…
An exact and efficient approach for computing a cell in an arrangement of quadrics
AbstractWe present an approach for the exact and efficient computation of a cell in an arrangement of quadric surfaces. All calculations are based on exact rational algebraic methods and provide the correct mathematical results in all, even degenerate, cases. By projection, the spatial problem is reduced to the one of computing planar arrangements of algebraic curves. We succeed in locating all event points in these arrangements, including tangential intersections and singular points. By introducing an additional curve, which we call the Jacobi curve, we are able to find non-singular tangential intersections. We show that the coordinates of the singular points in our special projected plana…
Saliency Features for 3D CAD-Data in the Context of Sampling-Based Motion Planning
In this paper, we consider disassembly scenarios for real-world 3D CAD-data, where each component is defined by a triangle mesh. For a fast construction of collision-free disassembly paths, common approaches use sampling-based rigid body motion planning which is well studied in the literature. One fact that has so far received little attention is that in industrial disassembly scenarios components are often attached to each other with flexible fastening elements like clips. In the planning process, the fastening elements show the following characteristics: 1) They can cause complex non-linear disassembly paths. 2) They are often deformable. 3) They are usually modeled in a relaxed state and…
Packing a trunk - Now with a twist!
In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure. No really satisfactory automated solution for this problem has been known in the past. In spite of its NP hardness, combinatorial optimization techniques, which consider only grid-aligned placements, produce solutions which are very close to the one achievable by a human expert in several hours of tedious work. The remaining gap is mostly due to the constrain…
Collision detection for 3D rigid body motion planning with narrow passages
In sampling-based 3D rigid body motion planning one of the major subroutines is collision detection. Especially for problems with narrow passages many samples have to be checked by a collision detection algorithm. In this application, the runtime of the motion planning algorithm is dominated by collision detection and the samples have the very specific characteristic that many of them are in collision and have small penetration volumes. In our work, we introduce a data structure and an algorithm that makes use of this characteristic by combining well-known data structures like a distance field and an octree with the swap algorithm by Llanas et al. For 3D rigid body motion planning with narr…
Expansive Voronoi Tree: A Motion Planner for Assembly Sequence Planning
One major challenge in Assembly Sequence Planning (ASP) for complex real-world CAD-scenarios is to find an appropriate disassembly path for each assembled part. Complex real-world scenes are characterized by a large installation space. There each part has many different possible disassembly paths that differ in length and clearance. However, due to tight packing in the installation space, these paths can contain narrow passages. Therefore a motion planner is needed that is able to globally search for a reasonable path and to locally overcome narrow passages. Moreover, since motion planning requests are executed in the ASP context over and over again for many parts, both for those that can b…
Lagrangian Description of Air Masses Associated with Latent Heat Release in Tropical Storm Karl (2016) during Extratropical Transition
Abstract Extratropical transition (ET) of tropical cyclones involves distinct changes of the cyclone’s structure that are not yet well understood. This study presents for the first time a comprehensive Lagrangian description of structure change near the inner core. A large sample of trajectories is computed from a convection-permitting numerical simulation of the ET of Tropical Storm Karl (2016). Three main airstreams are considered: those associated with the inner-core convection, inner-core descent, and the developing warm conveyor belt. Analysis of these airstreams is performed both in thermodynamic and physical space. Prior to ET, Karl is embedded in weak vertical wind shear and its int…
Packing a Trunk
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to pack as many identical boxes of size 4 × 2 × 1 units as possible into the interior of the trunk. This measure is important for car manufacturers, because it is a standard in the European Union.
Parallel Collision Queries on the GPU
We present parallel algorithms to accelerate collision tests of rigid body objects for a high number of independent transformations as they occur in sampling-based motion planning and path validation problems. We compare various GPU approaches with a different level of parallelism against each other and against a parallel CPU implementation. Our algorithms require no sophisticated load balancing schemes. They make no assumption on the distribution of the input transformations and require no pre-processing. Yet, we can perform up to 1 million collision tests per second with our best GPU implementation in our benchmarks. This is about 2.5X faster than our reference multi-core CPU implementati…
The Role of Wind Speed and Wind Shear for Banner Cloud Formation
Abstract Banner clouds are clouds that appear to be attached to the leeward face of a steep mountain. This paper investigates the role of wind speed and wind shear for the formation of banner clouds. Large-eddy simulations are performed to simulate the flow of dry air past an idealized pyramid-shaped mountain. The potential for cloud formation is diagnosed through the Lagrangian vertical parcel displacement, which in the case of a banner cloud shows a plume of large values in the lee of the mountain. In addition, vortical structures are visualized through streamlines and their curvature. A series of sensitivity experiments indicates that both the flow and the banner cloud occurrence are lar…
Trunk Packing Revisited
For trunk packing problems only few approximation schemes are known, mostly designed for the European standard DIN 70020 [6] with equally sized boxes [8, 9, 11, 12]. In this paper two discretized approaches for the US standard SAE J1100 [10] are presented, which make use of different box sizes. An exact branch-and-bound algorithm for weighted independent sets on graphs is given, using the special structure of the SAE standard. Another branch-and-bound packing algorithm using linear programs is presented. With these algorithms axis-oriented packings of different box sizes in an arbitrary trunk geometry can be computed efficiently.
Detection, tracking and event localization of jet stream features in 4-D atmospheric data
We introduce a novel algorithm for the efficient detection and tracking of features in spatiotemporal atmospheric data, as well as for the precise localization of the occurring genesis, lysis, merging and splitting events. The algorithm works on data given on a four-dimensional structured grid. Feature selection and clustering are based on adjustable local and global criteria, feature tracking is predominantly based on spatial overlaps of the feature's full volumes. The resulting 3-D features and the identified correspondences between features of consecutive time steps are represented as the nodes and edges of a directed acyclic graph, the event graph. Merging and splitting events appear in…
Ultrametricity property of energy landscapes of multidisperse packing problems
We consider the problem of finding the densest closed packing of hard disks with proposed different radii in a circular environment, such that the radius of the circumcircle is minimal. The subspace of the quasioptimum configurations of this problem exhibits the property of ultrametricity.
Exacus: Efficient and Exact Algorithms for Curves and Surfaces
We present the first release of the Exacus C++ libraries. We aim for systematic support of non-linear geometry in software libraries. Our goals are efficiency, correctness, completeness, clarity of the design, modularity, flexibility, and ease of use. We present the generic design and structure of the libraries, which currently compute arrangements of curves and curve segments of low algebraic degree, and boolean operations on polygons bounded by such segments.
Real-Time Monocular Pose Estimation of 3D Objects Using Temporally Consistent Local Color Histograms
We present a novel approach to 6DOF pose estimation and segmentation of rigid 3D objects using a single monocular RGB camera based on temporally consistent, local color histograms. We show that this approach outperforms previous methods in cases of cluttered backgrounds, heterogenous objects, and occlusions. The proposed histograms can be used as statistical object descriptors within a template matching strategy for pose recovery after temporary tracking loss e.g. caused by massive occlusion or if the object leaves the camera’s field of view. The descriptors can be trained online within a couple of seconds moving a handheld object in front of a camera. During the training stage, our approac…
Real-Time Monocular Segmentation and Pose Tracking of Multiple Objects
We present a real-time system capable of segmenting multiple 3D objects and tracking their pose using a single RGB camera, based on prior shape knowledge. The proposed method uses twist-coordinates for pose parametrization and a pixel-wise second-order optimization approach which lead to major improvements in terms of tracking robustness, especially in cases of fast motion and scale changes, compared to previous region-based approaches. Our implementation runs at about 50–100 Hz on a commodity laptop when tracking a single object without relying on GPGPU computations. We compare our method to the current state of the art in various experiments involving challenging motion sequences and diff…
IWAL–An Interactive Weather Analysis Laboratory
Abstract Complementary key elements of meteorological education are the provision of a thorough theoretical understanding of the physical laws governing atmospheric motions, and the hands-on investigation and visualization of specific weather systems. However, the latter task is technically challenging, because specific skills must be acquired for flexibly handling meteorological data. Some examples are superimposing satellite pictures and reanalysis fields, producing an isentropic potential vorticity (PV) map, and visualizing a vertical section across a flow feature of interest. Although learning these technical issues has its own merits, it can distract students from investigating the com…
Projection-based improvement of 3D reconstructions from motion-impaired dental cone beam CT data.
Purpose Computed tomography (CT) and, in particular, cone beam CT (CBCT) have been increasingly used as a diagnostic tool in recent years. Patient motion during acquisition is common in CBCT due to long scan times. This results in degraded image quality and may potentially increase the number of retakes. Our aim was to develop a marker-free iterative motion correction algorithm that works on the projection images and is suitable for local tomography. Methods We present an iterative motion correction algorithm that allows the patient's motion to be detected and taken into account during reconstruction. The core of our method is a fast GPU-accelerated three-dimensional reconstruction algorith…
Total Variation Regularization in Digital Breast Tomosynthesis
We developed an iterative algebraic algorithm for the reconstruction of 3D volumes from limited-angle breast projection images. Algebraic reconstruction is accelerated using the graphics processing unit. We varied a total variation (TV)-norm parameter in order to verify the influence of TV regularization on the representation of small structures in the reconstructions. The Barzilai-Borwein algorithm is used to solve the inverse reconstruction problem. The quality of our reconstructions was evaluated with the Quart Mam/Digi Phantom, which features so-called Landolt ring structures to verify perceptibility limits. The evaluation of the reconstructions was done with an automatic LR detection a…
Workflow-centred open-source fully automated lung volumetry in chest CT
Aim To develop a robust open-source method for fully automated extraction of total lung capacity (TLC) from computed tomography (CT) images and to demonstrate its integration into the clinical workflow. Materials and methods Using only open-source software, an algorithm was developed based on a region-growing method that does not require manual interaction. Lung volumes calculated from reconstructions with different kernels (TLCCT) were assessed. To validate the algorithm calculations, the results were correlated to TLC measured by pulmonary function testing (TLCPFT) in a subgroup of patients for which this information was available within 3 days of the CT examination. Results A total of 28…
Application of clustering techniques to electron-diffraction data: determination of unit-cell parameters.
A new approach to determining the unit-cell vectors from single-crystal diffraction data based on clustering analysis is proposed. The method uses the density-based clustering algorithm DBSCAN. Unit-cell determination through the clustering procedure is particularly useful for limited tilt sequences and noisy data, and therefore is optimal for single-crystal electron-diffraction automated diffraction tomography (ADT) data. The unit-cell determination of various materials from ADT data as well as single-crystal X-ray data is demonstrated.
Complete, exact, and efficient computations with cubic curves
The Bentley-Ottmann sweep-line method can be used to compute thearrangement of planar curves provided a number of geometricprimitives operating on the curves are available. We discuss themathematics of the primitives for planar algebraic curves of degreethree or less and derive efficient realizations. As a result, weobtain a complete, exact, and efficient algorithm for computingarrangements of cubic curves. Conics and cubic splines are specialcases of cubic curves. The algorithm is complete in that it handles all possibledegeneracies including singularities. It is exact in that itprovides the mathematically correct result. It is efficient in thatit can handle hundreds of curves with a quart…
An exact, complete and efficient implementation for computing planar maps of quadric intersection curves
We present the first exact, complete and efficient implementation that computes for a given set P=p1,...,pn of quadric surfaces the planar map induced by all intersection curves p1∩ pi, 2 ≤ i ≤ n, running on the surface of p1. The vertices in this graph are the singular and x-extreme points of the curves as well as all intersection points of pairs of curves. Two vertices are connected by an edge if the underlying points are connected by a branch of one of the curves. Our work is based on and extends ideas developed in [20] and [9].Our implementation is complete in the sense that it can handle all kind of inputs including all degenerate ones where intersection curves have singularities or pa…
A Region-based Gauss-Newton Approach to Real-Time Monocular Multiple Object Tracking
We propose an algorithm for real-time 6DOF pose tracking of rigid 3D objects using a monocular RGB camera. The key idea is to derive a region-based cost function using temporally consistent local color histograms. While such region-based cost functions are commonly optimized using first-order gradient descent techniques, we systematically derive a Gauss-Newton optimization scheme which gives rise to drastically faster convergence and highly accurate and robust tracking performance. We furthermore propose a novel complex dataset dedicated for the task of monocular object pose tracking and make it publicly available to the community. To our knowledge, it is the first to address the common and…
Cluster Analysis Tailored to Structure Change of Tropical Cyclones Using a Very Large Number of Trajectories
AbstractMajor airstreams in tropical cyclones (TCs) are rarely described from a Lagrangian perspective. Such a perspective, however, is required to account for asymmetries and time dependence of the TC circulation. We present a procedure that identifies main airstreams in TCs based on trajectory clustering. The procedure takes into account the TC’s large degree of inherent symmetry and is suitable for a very large number of trajectories . A large number of trajectories may be needed to resolve both the TC’s inner-core convection as well as the larger-scale environment. We define similarity of trajectories based on their shape in a storm-relative reference frame, rather than on proximity in …
A motion planning algorithm for the invalid initial state disassembly problem
Sampling-based motion planners are able to plan disassembly paths at high performance. They are limited by the fact that the input triangle sets of the static and dynamic object need to be free of collision in the initial and all following states. In real world applications, like the disassembly planning in car industry, this often does not hold true. Beside data inaccuracy, this is mainly caused by the modeling of flexible parts as rigid bodies, especially fixture elements like clips. They cause the invalid initial state disassembly problem. In the literature there exists no algorithm that is able to calculate a reasonable disassembly path for an invalid initial state. Our novel algorithm …
High-Speed and Robust Monocular Tracking
In this paper, we present a system for high-speed robust monocular tracking (HSRM-Tracking) of active markers. The proposed algorithm robustly and accurately tracks multiple markers at full framerate of current high-speed cameras. For this, we have developed a novel, nearly co-planar marker pattern that can be identified without initialization or incremental tracking. The pattern also encodes a unique ID to identify different markers. The individual markers are calibrated semi-automatically, thus no time-consuming and error-prone manual measurement is needed. Finally we show that the minimal spatial structure of the marker can be used to robustly avoid pose ambiguities even at large distanc…
Alignment of Noisy and Uniformly Scaled Time Series
The alignment of noisy and uniformly scaled time series is an important but difficult task. Given two time series, one of which is a uniformly stretched subsequence of the other, we want to determine the stretching factor and the offset of the second time series within the first one. We adapted and enhanced different methods to address this problem: classical FFT-based approaches to determine the offset combined with a naive search for the stretching factor or its direct computation in the frequency domain, bounded dynamic time warping and a new approach called shotgun analysis, which is inspired by sequencing and reassembling of genomes in bioinformatics. We thoroughly examined the strengt…
Exact, efficient, and complete arrangement computation for cubic curves
AbstractThe Bentley–Ottmann sweep-line method can compute the arrangement of planar curves, provided a number of geometric primitives operating on the curves are available. We discuss the reduction of the primitives to the analysis of curves and curve pairs, and describe efficient realizations of these analyses for planar algebraic curves of degree three or less. We obtain a complete, exact, and efficient algorithm for computing arrangements of cubic curves. Special cases of cubic curves are conics as well as implicitized cubic splines and Bézier curves.The algorithm is complete in that it handles all possible degeneracies such as tangential intersections and singularities. It is exact in t…
Packing a multidisperse system of hard disks in a circular environment.
We consider the problem of finding the densest closed packing of hard disks with proposed different radii in a circular environment, such that the radius of the circumcircle is minimal. With our approach, we are able to find denser packings for various problem instances than known from the literature. Both for the dynamics of the simulation and for the optimum values of the radii of the circumcircles, we find various scaling laws.
Metal artifact reduction in x-ray computed tomography: Inpainting versus missing value
A comparison of algorithms for reduction of metal artifacts in x-ray cone beam computed tomography (CBCT) is presented. In the context of algebraic reconstruction techniques (ART) several inpainting algorithms in the image domain are evaluated against missing data strategies. A GPU-based iterative framework is employed for a meaningful comparison of both. Simulation results from an extended Shepp-Logan phantom and real world dental data are given.