Robust Structure‐Based Shape Correspondence

We present a robust method to find region‐level correspondences between shapes, which are invariant to changes in geometry and applicable across multiple shape representations. We generate simplified shape graphs by jointly decomposing the shapes, and devise an adapted graph‐matching technique, from which we infer correspondences between shape regions. The simplified shape graphs are designed to primarily capture the overall structure of the shapes, without reflecting precise information about the geometry of each region, which enables us to find correspondences between shapes that might have significant geometric differences. Moreover, due to the special care we take to ensure the robustness of each part of our pipeline, our method can find correspondences between shapes with different representations, such as triangular meshes and point clouds. We demonstrate that the region‐wise matching that we obtain can be used to find correspondences between feature points, reveal the intrinsic self‐similarities of each shape and even construct point‐to‐point maps across shapes. Our method is both time and space efficient, leading to a pipeline that is significantly faster than comparable approaches. We demonstrate the performance of our approach through an extensive quantitative and qualitative evaluation on several benchmarks where we achieve comparable or superior performance to existing methods.     

Verification of multi-linked heaps

We define the class of single-parent heap systems, which rely on a singly-linked heap in order to model destructive updates on tree structures. This encoding has the advantage of relying on a relatively simple theory of linked lists in order to support abstraction computation. To facilitate the application of this encoding, we provide a program transformation that, given a program operating on a multi-linked heap without sharing, transforms it into one over a single-parent heap. It is then possible to apply shape analysis by predicate and ranking abstraction. The technique has been successfully applied on examples with lists (reversal and bubble sort) and trees with of fixed arity (balancing of, and insertion into, a binary sort tree).     

A data dependence test based on the projection of paths over shape graphs

We propose a data dependence detection test based on a new conflict analysis algorithm for C codes which make intensive use of recursive data structures dynamically allocated in the heap. This algorithm requires two pieces of information from the code section under analysis (a loop or a recursive function): (i) abstract shape graphs that represent the state of the heap at the code section; and (ii) path expressions that collect the traversing information for each statement. Our algorithm projects the path expressions on the shape graphs and checks over the graphs to ascertain whether one of the sites reached by a write statement matches one of the sites reached by another statement on a different loop iteration (or on a different call instance in a recursive function), in which case a conflict between the two statements is reported. Although our algorithm presents exponential complexity, we have found that in practice the parameters that dominate the computational cost have very low values, and to the best of our knowledge, all the other related studies involve higher costs. In fact, our experimental results show reductions in the data dependence analysis times of one or two orders of magnitude in some of the studied benchmarks when compared to a previous data dependence algorithm. Thanks to the information on uncovered data dependences, we have manually parallelized these codes, achieving speedups of 2.19 to 3.99 in four cores.     

A low-level memory model and an accompanying reachability predicate

Reasoning about program heap, especially if it involves handling unbounded, dynamically heap-allocated data structures such as linked lists and arrays, is challenging. Furthermore, sound analysis that precisely models heap becomes significantly more challenging in the presence of low-level pointer manipulation that is prevalent in systems software. The reachability predicate has already proved to be useful for reasoning about the heap in type-safe languages where memory is manipulated by dereferencing object fields. In this paper, we present a memory model suitable for reasoning about low-level pointer operations that is accompanied by a formalization of the reachability predicate in the presence of internal pointers and pointer arithmetic. We have designed an annotation language for C programs that makes use of the new predicate. This language enables us to specify properties of many interesting data structures present in the Windows kernel. We present our experience with a prototype verifier on a set of illustrative C benchmarks.     

Partial 3‐D Correspondence from Shape Extremities

We present a 3‐D correspondence method to match the geometric extremities of two shapes which are partially isometric. We consider the most general setting of the isometric partial shape correspondence problem, in which shapes to be matched may have multiple common parts at arbitrary scales as well as parts that are not similar. Our rank‐and‐vote‐and‐combine algorithm identifies and ranks potentially correct matches by exploring the space of all possible partial maps between coarsely sampled extremities. The qualified top‐ranked matchings are then subjected to a more detailed analysis at a denser resolution and assigned with confidence values that accumulate into a vote matrix. A minimum weight perfect matching algorithm is finally iterated to combine the accumulated votes into an optimal (partial) mapping between shape extremities, which can further be extended to a denser map. We test the performance of our method on several data sets and benchmarks in comparison with state of the art.     

Detecting the intersection of two convex shapes by searching on the 2-sphere

We take a look at the problem of deciding whether two convex shapes intersect or not. We do so through the well known lens of Minkowski sums and with a bias towards applications in computer graphics and robotics. We describe a new technique that works explicitly on the unit sphere, interpreted as the sphere of directions. In extensive benchmarks against various well-known techniques, ours is found to be slightly more efficient, much more robust and comparatively easy to implement. In particular, our technique is compared favorably to the ubiquitous algorithm of Gilbert, Johnson and Keerthi (GJK), and its decision variant by Gilbert and Foo. We provide an in-depth geometrical understanding of the differences between GJK and our technique and conclude that our technique is probably a good drop-in replacement when one is not interested in the actual distance between two non-intersecting shapes.     

Cost analysis of object-oriented bytecode programs

Cost analysis statically approximates the cost of programs in terms of their input data size. This paper presents, to the best of our knowledge, the first approach to the automatic cost analysis of object-oriented bytecode programs. In languages such as Java and C#, analyzing bytecode has a much wider application area than analyzing source code since the latter is often not available. Cost analysis in this context has to consider, among others, dynamic dispatch, jumps, the operand stack, and the heap. Our method takes a bytecode program and a cost model specifying the resource of interest, and generates cost relations which approximate the execution cost of the program with respect to such resource. We report on COSTA, an implementation for Java bytecode which can obtain upper bounds on cost for a large class of programs and complexity classes. Our basic techniques can be directly applied to infer cost relations for other object-oriented imperative languages, not necessarily in bytecode form.     

Shape space estimation by higher-rank of SOM

The aim of this study is to develop an estimation method for a shape space. In this work, “shape space” means a nonlinear subspace formed by a class of visual shapes, in which the continuous change in shapes is naturally represented. By using the shape space, various operations dealing with shapes, such as identification, classification, recognition, and interpolation can be carried out in the shape space. This paper introduces an algorithm based on a generative model of shapes. A higher-rank of the self-organizing map (SOM²) is used to implement the shape space estimation method. We use this method to estimate the shape space of artificial contours. In addition, we present results from a simulation of omnidirectional camera images taken from mobile robots. Our technique accurately predicts changes in image properties as the robot’s attitude changes. Finally, we consider the addition of local features to our method. We show that the inclusion of local features solves the correspondence problem. These results suggest the potential of our technique in the future.     

Detecting loop-carried dependences in programs with dynamic data structures

The problem of data dependences detection in codes based on dynamic data structures, is crucial to various compiler optimizations. The approach presented in this paper focuses on detecting data dependences induced by heap-directed pointers on loops that access dynamic data structures. Knowledge about the shape of the data structure accessible from a heap-directed pointer provides critical information for disambiguating heap accesses originating from it. The new approach is based on a previously developed shape analysis that maintains topological information of the connections among the different nodes (memory locations) in the data structure. As a novelty, our approach carries out abstract interpretation of the statements being analyzed, annotating memory locations with read/write information. This information will be later used in a very accurate data dependence test which we describe in this paper. We also discuss its application to several different benchmarks.     

A multiresolution descriptor for deformable 3D shape retrieval

In this paper, we present a spectral graph wavelet framework for the analysis and design of efficient shape signatures for nonrigid 3D shape retrieval. Although this work focuses primarily on shape retrieval, our approach is, however, fairly general and can be used to address other 3D shape analysis problems. In a bid to capture the global and local geometry of 3D shapes, we propose a multiresolution signature via a cubic spline wavelet generating kernel. The parameters of the proposed signature can be easily determined as a trade-off between effectiveness and compactness. Experimental results on two standard 3D shape benchmarks demonstrate the much better performance of the proposed shape retrieval approach in comparison with three state-of-the-art methods. Additionally, our approach yields a higher retrieval accuracy when used in conjunction with the intrinsic spatial partition matching.     

Connection Analysis: A Practical Interprocedural Heap Analysis for C

This paper presents a practical heap analysis technique, connection analysis, that can be used to disambiguate heap accesses in C programs. The technique is designed for analyzing programs that allocate many disjoint objects in the heap such as dynamically-allocated arrays in scientific programs. The method statically estimates connection matrices which encode the connection relationships between all heap-directed pointers at each program point. The results of the analysis can be used by parallelizing compilers to determine when two heap-allocated objects are guaranteed to be disjoint, and thus can be used to improve array dependence and interference analysis. The method has been implemented as a context-sensitive interprocedural analysis in the McCAT optimizing/parallelizing C compiler. Experimental results are given to compare the accuracy of connection analysis versus a conservative estimate based on points-to analysis.     

Taking an object-centric view on dynamic information with object flow analysis

A large body of research analyzes the runtime execution of a system to extract abstract behavioral views. Those approaches primarily analyze control flow by tracing method execution events or they analyze object graphs of heap memory snapshots. However, they do not capture how objects are passed through the system at runtime. We refer to the exchange of objects as the object flow, and we claim that it is necessary to analyze object flows if we are to understand the runtime of an object-oriented application. We propose and detail object flow analysis, a novel dynamic analysis technique that takes this new information into account. To evaluate its usefulness, we present a visual approach that allows a developer to study classes and components in terms of how they exchange objects at runtime. We illustrate our approach on three case studies.     

Automatic construction of 2D shape models

A procedure for automated 2D shape model design is presented. The system is given a set of training example shapes defined by contour point coordinates. The shapes are automatically aligned using Procrustes analysis and clustered to obtain cluster prototypes (typical objects) and statistical information about intracluster shape variation. One difference from previous methods is that the training set is first automatically clustered and shapes considered to be outliers are discarded. In this way, cluster prototypes are not distorted by outliers. A second difference is in the manner in which registered sets of points are extracted from each shape contour. We propose a flexible point matching technique that takes into account both pose/scale differences and nonlinear shape differences. The matching method is independent of the objects' initial relative position/scale and does not require any manually tuned parameters. Our shape model design method was used to learn 11 different shapes from contours that were manually traced in MR brain images. The resulting model was then employed to segment several MR brain images that were not included in the shape-training set. A quantitative analysis of our shape registration approach, within the main cluster of each structure, demonstrated results that compare very well to those achieved by manual registration; achieving an average registration error of about 1 pixel. Our approach can serve as a fully automated substitute to the tedious and time-consuming manual 2D shape registration and analysis     

The pairing heap: A new form of self-adjusting heap

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue) called theFibonacci heap. Although theoretically efficient, Fibonacci heaps are complicated to implement and not as fast in practice as other kinds of heaps. In this paper we describe a new form of heap, called thepairing heap, intended to be competitive with the Fibonacci heap in theory and easy to implement and fast in practice. We provide a partial complexity analysis of pairing heaps. Complete analysis remains an open problem.