Search

The convexity of a set can be generalized to the two weaker notions of positive reach and r-convexity; both describe the regularity of a set's boundary. For any compact subset of R d , we provide methods for computing upper bounds on these quantities from point cloud data. The bounds converge to the respective quantities as the sampling scale of the point cloud decreases, and the rate of convergence for the bound on the reach is given under a weak regularity condition. We also introduce the β -reach, a generalization of the reach that excludes small-scale features of size less than a parameter β ∈ [ 0 , ∞) . Numerical studies suggest how the β -reach can be used in high-dimension to infer the reach and other geometric properties of smooth submanifolds. [ABSTRACT FROM AUTHOR]

We present a novel and efficient pore-network extraction (PNE) platform that utilizes a seamless merging algorithm to extract core-sized pore networks directly from high-resolution segmented micro-computed tomography images of rock samples. This platform has the distinct advantage of being parallel friendly, allowing the entire computational workload of the extraction process to be distributed across multiple compute nodes. The superior computational efficiency of this approach paves the way for the extraction of deterministic pore networks with physical dimensions that are comparable to those of core samples employed in conventional core-flooding experiments. Sensitivity analysis studies are performed on digital replicates of Berea and Bentheimer sandstone rock samples. To illustrate the role of a user-defined adjustment coefficient on the extraction process, a set of conventional-sized pore networks are extracted and analyzed for both rock samples. To ascertain the quality of these pore networks, comparisons are made with equivalent pore networks extracted using a well-characterized open-source pore-network extractor. After rigorous examination of these conventional-sized pore networks, the validated PNE platform is applied to extract miniature-core-sized pore networks, and their relevant statistics and petrophysical properties are presented. In addition, these networks are extensively utilized in both quasi-static and dynamic pore-network modeling (PNM) simulations of two-phase flow processes. The predicted two-phase flow properties of the rock samples are benchmarked against the corresponding experimental data and the results are presented in both the current and the second volume of this work. [ABSTRACT FROM AUTHOR]

A procedure for reconstructing the central axis from diagnostic image processing is presented here, capable of solving the widespread problem of stepped shape effect that characterizes the most common algorithmic tools for processing the central axis for diagnostic imaging applications through the development of an algorithm correcting the spatial coordinates of each point belonging to the axis from the use of a common discrete image skeleton algorithm.The procedure is applied to the central axis traversing the vascular branch of the cerebral system, appropriately reconstructed from the processing of diagnostic images, using investigations of the local intensity values identified in adjacent voxels. The percentage intensity of the degree of adherence to a specific anatomical tissue acts as an attraction pole in the identification of the spatial center on which to place each point of the skeleton crossing the investigated anatomical structure.The results were shown in terms of the number of vessels identified overall compared to the original reference model.The procedure demonstrates high accuracy margin in the correction of the local coordinates of the central points that permits to allocate precise dimensional measurement of the anatomy under examination.The reconstruction of a central axis effectively centered in the region under examination represents a fundamental starting point in deducing, with a high margin of accuracy, key informations of a geometric and dimensional nature that favours the recognition of phenomena of shape alterations ascribable to the presence of clinical pathologies.

This article introduces the new problem of planning spatially distributed lanes for supporting multi‐agent navigation applications in 3D environments. Our proposed approach computes the max‐flow of a 3D medial axis representation of the environment in order to globally compute collision‐free lanes exploring the entire free space of the volumetric scene. Our method addresses agent clearance and path dispersion in order to provide a comprehensive solution to globally compute lanes to be used by multiple agents in 3D environments. By selecting the desired lane dispersion our approach offers an intuitive and powerful way to explore variations in the computed collections of lanes. Dispersion is addressed with a combination of new techniques based on max flow computation, clearance‐based path separation, and adaptive shortcut‐based smoothing. [ABSTRACT FROM AUTHOR]

This paper establishes a relation between the tangent cone of the medial axis of X at a given point a ∈ R n and the medial axis of the set of points m(a) in X realising the Euclidean distance d(a, X). As a consequence, a lower bound for the dimension of the medial axis of X in terms of the dimension of the medial axis of m(a) is obtained. This formula appears to be the missing link to the full description of the medial axis' dimension. An extended study of potentially troublesome points on the frontier of the medial axis is also provided, resulting in their characterisation by the recently introduced by Birbrair and Denkowski reaching radius whose definition we simplify. [ABSTRACT FROM AUTHOR]

This paper presents a new method for the computation of the generalized Voronoi diagram of planar polygons. First, we show that the vertices of the cut locus can be computed efficiently. This is achieved by enumerating the tripoints of the polygon, a superset of the cut locus vertices. This is the set of all points that are of equal distance to three distinct topological entities. Then our algorithm identifies and connects the appropriate tripoints to form the cut locus vertex connectivity graph, where edges define linear or parabolic boundary segments between the Voronoi regions, resulting in the generalized Voronoi diagram. Our proposed method is validated on complex polygon soups. We apply the algorithm to represent the exact signed distance function of the polygon by augmenting the Voronoi regions with linear and radial functions, calculating the cut locus both inside and outside. • Efficient algorithm for computing generalized Voronoi diagrams for polygon soups. • Our method constructs tripoints by embedding the polygon in a Delaunay triangulation. • Algorithm correctness is argued with a number of geometric theorems and a conjecture. • Exact algorithm utilizes closed-form geometric formulas and graph transformations. • Our robust Matlab implementation performs in O(n log(n)) time for most inputs. [ABSTRACT FROM AUTHOR]

The objective of the present study is to justify the possibility of constructive and analytic solution to the inverse problem of cyclographic modeling of a curve of space R3 and development of a respective algorithm. The orthogonal projection and the two components of the cyclographic projection of a spatial curve form a triad of elements in plane z=0. These elements are the result of the direct problem solution and constitute the basis for the inverse problem solution. The direct problem consists in construction in plane z=0 of a cyclographic projection (a model) of a given spatial curve, while the inverse problem consists in determination of a spatial curve given its cyclographic projection. Insufficient knowledge on the inverse problem as well as its relevance in practical applications, e.g. in cutting tool trajectory calculation for pocket machining of mechanical engineering products on NC units, make urgent the definition and the solution of the inverse problem. In the present paper a simple convex closed curve is considered as the given cyclographic projection. It is proven that there exists a unique spatial curve, for which the given curve constitutes a cyclographic projection. The algorithm for the inverse problem solution is demonstrated on examples.

Nowadays the amount of gathered raw data emphasizes the importance of further data processing done by skilled engineers aided by computer algorithms. Researchers develop new algorithms for the automated determination of geometrical features, such as symmetry and main axes, skeleton lines, etc. This paper presented a new algorithm to compute an unbranched axis. It was based on the Curve of Minimal Radii (CMR) algorithm, and it overcomes its significant limitations depending on the shape of the input data. To define the accuracy of the results the threshold parameter was introduced. The described approach is more comprehensive than CMR in terms of the object shape. The tests were conducted on several planar objects, and the results were compared with the original CMR axes and Medial Axis. [ABSTRACT FROM AUTHOR]

Categorization of everyday objects requires that humans form representations of shape that are tolerant to variations among exemplars. Yet, how such invariant shape representations develop remains poorly understood. By comparing human infants (6–12 months; N=82) to computational models of vision using comparable procedures, we shed light on the origins and mechanisms underlying object perception. Following habituation to a never-before-seen object, infants classified other novel objects across variations in their component parts. Comparisons to several computational models of vision, including models of high-level and low-level vision, revealed that infants’ performance was best described by a model of shape based on the skeletal structure. Interestingly, infants outperformed a range of artificial neural network models, selected for their massive object experience and biological plausibility, under the same conditions. Altogether, these findings suggest that robust representations of shape can be formed with little language or object experience by relying on the perceptually invariant skeletal structure.

We obtain an explicit formula for comparing total curvature of level sets of functions on Riemannian manifolds and develop some applications of this result to the isoperimetric problem in spaces of nonpositive curvature. [ABSTRACT FROM AUTHOR]

We investigate the maximal open domain E (M) on which the orthogonal projection map p onto a subset M ⊆ R d can be defined and study essential properties of p. We prove that if M is a C 1 submanifold of R d satisfying a Lipschitz condition on the tangent spaces, then E (M) can be described by a lower semi-continuous function, named frontier function. We show that this frontier function is continuous if M is C 2 or if the topological skeleton of M c is closed and we provide an example showing that the frontier function need not be continuous in general. We demonstrate that, for a C k -submanifold M with k ≥ 2 , the projection map is C k - 1 on E (M) , and we obtain a differentiation formula for the projection map which is used to discuss boundedness of its higher order differentials on tubular neighborhoods. A sufficient condition for the inclusion M ⊆ E (M) is that M is a C 1 submanifold whose tangent spaces satisfy a local Lipschitz condition. We prove in a new way that this condition is also necessary. More precisely, if M is a topological submanifold with M ⊆ E (M) , then M must be C 1 and its tangent spaces satisfy the same local Lipschitz condition. A final section is devoted to highlighting some relations between E (M) and the topological skeleton of M c . [ABSTRACT FROM AUTHOR]

The bisector function is an important tool for analyzing and filtering Euclidean skeletons. In this paper, we are proposing a new way to compute 2D and 3D discrete bisector function based on annuli. From a continuous point of view, a point that belongs to the medial axis is the center of a maximal ball that hits the background in more than one point. The maximal angle between those points is expected to be high for most of the object points and corresponds to the bisector angle. This logic is not really applicable in the discrete space since we may miss some background points that can lead to small bisector angles. In this work we use annuli to find the background points in order to compute the bisector angle. Our approach offers the possibility to change the thickness of the annulus at a given point and is thus flexible when computing skeletons. Our work can be extended to nD and we propose the nD algorithm. [ABSTRACT FROM AUTHOR]

• We present a spline-based medial axis transform representation of binary images. • Our method achieves very high compression ratios while keeping quality high. • Our method has better performance than regular medial axis transform representation. • We show how our method enables generating super-resolution images. • We show how our method allows shape manipulation and captures multiscale skeletons. [Display omitted] Medial axes are well-known descriptors used for representing, manipulating, and compressing binary images. In this paper, we present a full pipeline for computing a stable and accurate piece-wise B-spline representation of Medial Axis Transforms (MATs) of binary images. A comprehensive evaluation on a benchmark shows that our method, called Spline-based Medial Axis Transform (SMAT), achieves very high compression ratios while keeping quality high. Compared with the regular MAT representation, the SMAT yields a much higher compression ratio at the cost of a slightly lower image quality. We illustrate our approach on a multi-scale SMAT representation, generating super-resolution images, and free-form binary image deformation. [ABSTRACT FROM AUTHOR]

We propose a framework of efficient nonlinear deformable simulation with both fast continuous collision detection and robust collision resolution. We name this new framework Medial IPC as it integrates the merits from medial elastics, for an efficient and versatile reduced simulation, as well as incremental potential contact, for a robust collision and contact resolution. We leverage medial axis transform to construct a kinematic subspace. Instead of resorting to projective dynamics, we use classic hyperelastics to embrace real-world nonlinear materials. A novel reduced continuous collision detection algorithm is presented based on the medial mesh. Thanks to unique geometric properties of medial axis and medial primitives, we derive closed-form formulations for identifying between-primitive collision within the reduced medial space. In the meantime, the implicit barrier energy that generates necessary repulsion forces for collision resolution is also formulated with the medial coordinate. In other words, Medial IPC exploits a universal reduced coordinate for simulation, continuous self-/collision detection, and IPC-based collision resolution. Continuous collision detection also allows more aggressive time stepping. In addition, we carefully implement our system with a heterogeneous CPU-GPU deployment such that massively parallelizable computations are carried out on the GPU while few sequential computations are on the CPU. Such implementation also frees us from generating training poses for selecting Cubature points and pre-computing their weights. We have tested our method on complicated deformable models and collision-rich simulation scenarios. Due to the reduced nature of our system, the computation is faster than fullspace IPC or other fullspace methods using continuous collision detection by at least one order. The simulation remains high-quality as the medial subspace captures intriguing and local deformations with sufficient realism. [ABSTRACT FROM AUTHOR]

The medial axis, or skeleton, is a fundamental object representation that has been extensively used in shape recognition. Yet, its extension to natural images has been challenging due to the large appearance and scale variations of objects and complex background clutter that appear in this setting. In contrast to recent methods that address skeleton extraction as a binary pixel classification problem, in this article we present an alternative formulation for skeleton detection. We follow the spirit of flux-based algorithms for medial axis recovery by training a convolutional neural network to predict a two-dimensional vector field encoding the flux representation. The skeleton is then recovered from the flux representation, which captures the position of skeletal pixels relative to semantically meaningful entities (e.g., image points in spatial context, and hence the implied object boundaries), resulting in precise skeleton detection. Moreover, since the flux representation is a region-based vector field, it is better able to cope with object parts of large width. We evaluate the proposed method, termed DeepFlux, on six benchmark datasets, consistently achieving superior performance over state-of-the-art methods. Finally, we demonstrate an application of DeepFlux, augmented with a skeleton scale estimation module, to detect objects in aerial images. This combination yields results that are competitive with models trained specifically for object detection, showcasing the versatility and effectiveness of mid-level representations in high-level tasks. An implementation of our method is available at https://github.com/YukangWang/DeepFlux. [ABSTRACT FROM AUTHOR]

Purpose: Deformable medial modeling is an inverse skeletonization approach to representing anatomy in medical images, which can be used for statistical shape analysis and assessment of patient-specific anatomical features such as locally varying thickness. It involves deforming a pre-defined synthetic skeleton, or template, to anatomical structures of the same class. The lack of software for creating such skeletons has been a limitation to more widespread use of deformable medial modeling. Therefore, the objective of this work is to present an open-source user interface (UI) for the creation of synthetic skeletons for a range of medial modeling applications in medical imaging., Approach: A UI for interactive design of synthetic skeletons was implemented in 3D Slicer, an open-source medical image analysis application. The steps in synthetic skeleton design include importation and skeletonization of a 3D segmentation, followed by interactive 3D point placement and triangulation of the medial surface such that the desired branching configuration of the anatomical structure's medial axis is achieved. Synthetic skeleton design was evaluated in five clinical applications. Compatibility of the synthetic skeletons with open-source software for deformable medial modeling was tested, and representational accuracy of the deformed medial models was evaluated., Results: Three users designed synthetic skeletons of anatomies with various topologies: the placenta, aortic root wall, mitral valve, cardiac ventricles, and the uterus. The skeletons were compatible with skeleton-first and boundary-first software for deformable medial modeling. The fitted medial models achieved good representational accuracy with respect to the 3D segmentations from which the synthetic skeletons were generated., Conclusions: Synthetic skeleton design has been a practical challenge in leveraging deformable medial modeling for new clinical applications. This work demonstrates an open-source UI for user-friendly design of synthetic skeletons for anatomies with a wide range of topologies., (© 2024 Society of Photo-Optical Instrumentation Engineers (SPIE).)

Object recognition relies on different transformations of the retinal input, carried out by the visual system, that range from local contrast to object shape and category. While some of those transformations are thought to occur at specific stages of the visual hierarchy, the features they represent are correlated (e.g., object shape and identity) and selectivity for the same feature overlaps in many brain regions. This may be explained either by collinearity across representations or may instead reflect the coding of multiple dimensions by the same cortical population. Moreover, orthogonal and shared components may differently impact distinctive stages of the visual hierarchy. We recorded functional MRI activity while participants passively attended to object images and employed a statistical approach that partitioned orthogonal and shared object representations to reveal their relative impact on brain processing. Orthogonal shape representations (silhouette, curvature, and medial axis) independently explained distinct and overlapping clusters of selectivity in the occitotemporal and parietal cortex. Moreover, we show that the relevance of shared representations linearly increases moving from posterior to anterior regions. These results indicate that the visual cortex encodes shared relations between different features in a topographic fashion and that object shape is encoded along different dimensions, each representing orthogonal features. [ABSTRACT FROM AUTHOR]

The skeletonization of binary images is a common task in many image processing and machine learning applications. Some of these applications require very fast image processing. We propose novel techniques for efficient 2D and 3D thinning of binary images using GPU processors. The algorithms use bit-encoded binary images to process multiple points simultaneously in each thread. The simpleness of a point is determined based on Boolean algebra using only bitwise logical operators. This avoids computationally expensive decoding and encoding steps and allows for additional parallelization. The 2D algorithm is evaluated using a data set of handwritten characters images. It required an average computation time of 3.53 ns for 32 × 32 pixels and 0.25 ms for 1024 × 1024 pixels. This is 52–18,380 times faster than a multi-threaded border-parallel algorithm. The 3D algorithm was evaluated based on clinical images of the human vasculature and required computation times of 0.27 ms for 128 × 128 × 128 voxels and 20.32 ms for 512 × 512 × 512 voxels, which is 32–46 times faster than the compared border-sequential algorithm using the same GPU processor. The proposed techniques enable efficient real-time 2D and 3D skeletonization of binary images, which could improve the performance of many existing machine learning applications. [ABSTRACT FROM AUTHOR]

The offsetting process that defines straight skeletons of polygons is generalized to arc polygons, i.e., to planar shapes with piecewise circular boundaries. The offsets are obtained by shrinking or expanding the circular arcs on the boundary in a co-circular manner, and tracing the paths of their endpoints. These paths define the associated shape-preserving skeleton, which decomposes the input object into patches. While the skeleton forms a forest of trees, the patches of the decomposition have a radial monotonicity property. Analyzing the events that occur during the offsetting process is non-trivial; the boundary of the offsetting object may get into self-contact and may even splice. This leads us to an event-driven algorithm for offset and skeleton computation. Several examples (both manually created ones and approximations of planar free-form shapes by arc spline curves) are analyzed to study the practical performance of our algorithm. [ABSTRACT FROM AUTHOR]

• A unified algorithmic approach for computing the Voronoi diagram, medial axis, Delaunay graph and α -hull for a set of planar curves. • No pre-processing required in approximating the input curve(s). • No post-processing required in computing the Voronoi segment(s). • Identifying branch points without computing the bisectors greatly reducing the computational complexity. This paper proposes a unified approach towards computing geometry structures viz. Voronoi diagram, medial axis, Delaunay graph and α -hull of planar closed curves. It initially presents an algorithm for computing the Voronoi diagram of a set of planar freeform closed curves without approximating the curves using points, lines or biarcs. The algorithm starts by computing the minimum antipodal discs (MADs) for all pairs of curves and these MADs are systematically processed to identify all branch points. The key feature of the algorithm is that it computes a branch point without computing any of the bisectors a priori. Local computations of Voronoi segments are then done using the identified pairs of the segments of curves. The theoretical foundation of the algorithm has been first laid for a set of convex curves and then extended to non-convex curves. It has also been shown that the developed algorithm for the Voronoi diagram can also be used to compute related structures such as medial axis, Delaunay graph and α -hull. They have also been addressed without computing Voronoi edges/segments. Results of the implementation have been provided along with a detailed discussion of the algorithm. [ABSTRACT FROM AUTHOR]

We propose a framework for the interactive simulation of nonlinear deformable objects. The primary feature of our system is the seamless integration of deformable simulation and collision culling, which are often independently handled in existing animation systems. The bridge connecting them is the medial axis transform (MAT), a high-fidelity volumetric approximation of complex 3D shapes. From the physics simulation perspective, MAT leads to an expressive and compact reduced nonlinear model. We employ a semireduced projective dynamics formulation, which well captures high-frequency local deformations of high-resolution models while retaining a low computation cost. Our key observation is that the most compelling (nonlinear) deformable effects are enabled by the local constraints projection, which should not be aggressively reduced, and only apply model reduction at the global stage. From the collision detection (CD)/collision culling (CC) perspective, MAT is geometrically versatile using linear-interpolated spheres (i.e., the so-called medial primitives (MPs)) to approximate the boundary of the input model. The intersection test between two MPs is formulated as a quadratically constrained quadratic program problem. We give an algorithm to solve this problem exactly, which returns the deepest penetration between a pair of intersecting MPs. When coupled with spatial hashing, collision (including self-collision) can be efficiently identified on the GPU within a few milliseconds even for massive simulations. We have tested our system on a variety of geometrically complex and high-resolution deformable objects, and our system produces convincing animations with all of the collisions/self-collisions well handled at an interactive rate. [ABSTRACT FROM AUTHOR]

The processing of cartographic data demands human involvement. Up-to-date algorithms try to automate a part of this process. The goal is to obtain a digital model, or additional information about shape and topology of input geometric objects. A topological skeleton is one of the most important tools in the branch of science called shape analysis. It represents topological and geometrical characteristics of input data. Its plot depends on using algorithms such as medial axis, skeletonization, erosion, thinning, area collapse and many others. Area collapse, also known as dimension change, replaces input data with lower-dimensional geometric objects like, for example, a polygon with a polygonal chain, a line segment with a point.