A common approach to approximating the medial axis decides the presence of medial points in a region of nonzero size by analyzing the gradient of the distance transform at a finite number of locations in this region. In general, algorithms of this type do not guarantee completeness. In this paper, we consider a novel medial axis approximation algorithm of this type and present an analysis in the 2D case that reveals the geometric relationship between the quality of the medial axis approximation and the number and distribution of samples of the gradient of the distance transform. We use an extension of this algorithm to 3D to compute qualitatively accurate medial axes of polyhedra, as well as Voronoi diagrams of lines. Our results suggest that medial axis approximation algorithms based on sampling of the distance transform are theoretically well-motivated.
The medial axis transform is valuable for shape representation as it is complete and captures part structure. However, its exact computation for arbitrary 3D models is not feasible. We introduce a novel algorithm to approximate the medial axis of a polyhedron with a dense set of medial points, with a guarantee that each medial point is within a specified tolerance from the medial axis. Given this discrete approximation to the medial axis, we use Damon’s work on radial geometry (Damon, 2005 ) to design a numerical method that recovers surface curvature of the object boundary from the medial axis transform alone. We also show that the number of medial sheets comprising this representation may be significantly reduced without substantially compromising the quality of the reconstruction, to create a more useful part-based representation.
Medial surfaces are popular representations of 3D objects in vision, graphics and geometric modeling. They capture relevant symmetries and part hierarchies and also allow for detailed differential geometric information to be recovered. However, exact algorithms for their computation from meshes must solve high-order polynomial equations, while approximation algorithms rarely guarantee soundness and completeness. In this article we develop a technique for computing the medial surface of an object with a polyhedral boundary, which is based on an analysis of the average outward flux of the gradient of its Euclidean distance function. This analysis leads to a coarse-to-fine algorithm implemented on a cubic lattice that reveals at each iteration the salient manifolds of the medial surface. We provide comparative results against a state-of-the-art method in the literature.
We introduce a novel algorithm to compute a dense sample of points on the medial locus of a polyhedral object, with a guarantee that each medial point is within a specified tolerance ¿ from the medial surface. Motivated by Damon's work on the relationship between the differential geometry of the smooth boundary of an object and its medial surface, we then develop a computational method by which boundary differential geometry can be recovered directly from this dense medial point cloud. Experimental results on models of varying complexity demonstrate the validity of the approach, with principal curvature values that are consistent with those provided by an alternative method that works directly on the boundary. As such, we demonstrate the richness of a dense medial point cloud as a shape descriptor for 3D data processing.
DOI : 10.1109/iccvw.2009.5457508 Anahtar Kelimeler :
Computational geometry, Solid modeling, Surface reconstruction, Computer vision, Computer science, Clouds, Shape, Path planning, Conferences, Euclidean distance, computational geometry, differential geometry, sampled medial loci, boundary differential geometry, polyhedral object, dense medial point cloud, principal curvature value, shape descriptor, 3D data processing
This thesis presents a particular set of spheres as new representation of the shape of a 3D solid. The spheres considered are maximal inscribed spheres in the solid and their centres are chosen in such a way that at most one sphere centre lies in a cubic region of space.The shape representation proposed is a discretization of the medial surface transform of a solid. Part I of this thesis presents algorithms for the computation of this representation given a boundary representation of a solid by approximating its medial surface transform. Properties of those medial spheres that are not detected by our algorithm in 3D are described and a complete characterization of those medial circles that are not detected by a 2D version of our algorithm is given. In Part II, recent results from differential geometry are used to compute principal curvatures and principal curvature directions on the boundary of the smooth solid represented using the union of medial spheres. This computation is performed using only the medial sphere centres and a pair of points on each medial sphere that lies on the surface of the solid being modeled. It is shown how the union of medial spheres allows a part-based description of the solid, with a significance measure associated with each part. In Part III, it is shown that our shape representation can offer a tight volumetric fit to a polyhedron, using a small number of spheres. The spheres used in our representation can be quickly updated as the solid undergoes a certain class of deformations. It is shown how our set of medial spheres allows efficient and accurate proximity queries between polyhedra.
We study the problem of computing the medial surface of a polyhedral solid. As this problem is difficult to solve exactly, we consider an approximate solution that locates regions of space through which the medial surface passes. The algorithm we design is based on the measure of the average outward flux of the gradient of the Euclidian distance transform of the polyhedron through the surface of a spherical region shrinking to a point. We extend previous methods by developing a completeness criterion that adopts this measure for spheres of non-zero size. As a result, we obtain a coarse-to-fine algorithm that reveals those voxels that contain sections of the medial surface. Such an implementation has the advantage that digital thinning with homotopy type preservation can be borrowed from past work. We argue that the error due to discrete flux computations is bounded.
We study connectivity relations among points, where the precise location of each input point lies in a region of uncertainty. We distinguish two fundamental scenarios under which uncertainty arises. In the favorable Best-Case Uncertainty, each input point can be chosen from a given set to yield the best possible objective value. In the unfavorable Worst-Case Uncertainty, the input set has worst possible objective value among all possible point locations, which are uncertain due, for example, to imprecise data. We consider these notions of uncertainty for the bottleneck spanning tree problem, giving rise to the following Best-Case Connectivity with Uncertainty problem: given a family of geometric regions, choose one point per region, such that the longest edge length of an associated geometric spanning tree is minimized. We show that this problem is NP-hard even for very simple scenarios in which the regions are line segments or squares. On the other hand, we give an exact solution for the case in which there are \(n+k\) regions, where k of the regions are line segments and n of the regions are fixed points. We then give approximation algorithms for cases where the regions are either all line segments or all unit discs. We also provide approximation methods for the corresponding Worst-Case Connectivity with Uncertainty problem: Given a set of uncertainty regions, find the minimal distance r such that for any choice of points, one per region, there is a spanning tree among the points with edge length at most r.