Skeleton Extraction
Related Projects:  Computational Geometry    Robot Task and Motion Planning    Hierarchical Aggregation    Approximate Convex Decomposition (ACD)  

Shape decomposition and skeletonization share many common properties and applications. However, they are generally considered as independent methods. In many applications, the detailed features of a model are not crucial and in fact considering them only may serve to obscure the important structural features and adds to the processing cost. In such cases, an approximate representation of the model, such as approximate convex decomposition (ACD), that captures the key structural features would be preferable. One important example is skeleton extraction. The skeleton is a low dimensional object which essentially represents the ''shape'' of the higher-dimensional target object. The process of generating such a skeleton is called skeleton extraction. ACD partitions a model into nearly convex components, has been shown to reveal important structural information and is used for shape decomposition in this paper. A skeleton of the model is then extracted from the convex hulls of these nearly convex components. The process of simultaneous shape decomposition and skeletonization iterates until the quality of the skeleton becomes satisfactory.



Skeletonization Extraction via Approximate Convex Decomposition

2D Polygon Examples



Original mesh
in tif format in tif format in tif format in tif format
Perturbed mesh
in tif format in tif format in tif format in tif format



3D Polyhdral Examples



Twisted Donut



Video: mpeg format

images:
in tif format in tif format in tif format



Buffalo



Original mesh

Video: mpeg format

images:
in tif format in tif format in tif format

Perturbed mesh


Video: mpeg format

images:
in tif format in tif format in tif format



Twisted X



Original mesh

Video: mpeg format

images:
in tif format in tif format in tif format

Perturbed mesh


Video: mpeg format

images:
in tif format in tif format in tif format

Simultaneous Shape Decomposition and Skeletonization Using Approximate Convex Decomposition

An example of co-evolution of shape decomposition and skeleton extraction


The skeleton (shown in the lower row) evolves with the shape decomposition (shown in the upper row).


Robustness under pertubation and deformation



Robustness tests using perturbed and skeletal deformed meshes. The female, the horse and the triceratop models have 243,442, 39,694 and 5,660 triangles, respectively. DO is the graph edit distance between a skeleton extracted from a perturbed or deformed mesh and a skeleton extracted from the original mesh. D2 O is DO without counting operations on degree-2 nodes.

Application: Skeletal Deformation


Movie: baby boxying (divx, 6.8 MB)

An animation sequence obtained from applying the boxing motion capture data to the extracted skeleton from a baby model. The motion capture data (action number 13_17) is downloaded from the CMU Graphics Lab motion capture database. The first two figures in the sequence are the shape decomposition and the skeleton of the baby. Note the not all joints motions from the data are used because the extracted skeleton has fewer joints.


Related Publications

Fast Collision Detection for Motion Planning Using Shape Primitive Skeletons, Mukulika Ghosh and Shawna Thomas and Nancy M. Amato, Algorithmic Foundations of Robotics XIII. Springer Proceedings in Advanced Robotics (SPAR). The 2018 Workshop on the Algorithmic Foundations of Robotics (WAFR), Vol: 14, pp. 36-51, Springer, Cham, May 2020. DOI: 10.1007/978-3-030-44051-0_3
Keywords: Collision Detection, Computational Geometry, Motion Planning
Links : [Published]

BibTex

@article{ghosh-wafr-2018
, author = "Mukulika Ghosh and Shawna Thomas and Nancy M. Amato"
, title = "Fast Collision Detection for Motion Planning Using Shape Primitive Skeletons"
, journal = "Algorithmic Foundations of Robotics XIII. Springer Proceedings in Advanced Robotics (SPAR)"
, publisher = "Springer, Cham."
, volume = "14"
, pages = "36-51"
, year = "2020"
, doi = "10.1007/978-3-030-44051-0_3"
}


Abstract

In many robotics applications, the environment (robots and obstacles) often have very complex geometries. These result in expensive primitive computations such as collision detection which in turn, affect the overall performance of these applications. Approximating the geometry is a common approach to optimize computation. Unlike other applications of geometric approximation where it is applied to one space (usually obstacle space), we approximate both obstacle and free workspace with a set of geometric shape primitives that are completely contained within the space and represent its topology (skeleton). We use these “shape primitive skeletons” to improve collision detection performance in motion planning algorithms. Our results show that the use of shape primitive skeletons improves the performance of standard collision detection methods in motion planning problems by 20–70% in our 2D and 3D test environments regardless of motion planning strategy. We also show how the same shape primitive skeletons can be used with robots of different sizes to improve the performance of collision detection operation.


Geometric Approximations and Their Application to Motion Planning, Mukulika Ghosh, Doctoral Dissertation, Texas A&M University, College Station, TX, Aug 2019.
Keywords: Computational Geometry, Convex Decomposition, Sampling-Based Motion Planning
Links : [Published]

BibTex

@phdthesis{ghosh-phd-2019
, author = "Mukulika Ghosh"
, title = "Geometric Approximations and Their Application to Motion Planning"
, school = "Department of Computer Science and Engineering, Texas A\&M University"
, month = "August"
, year = "2019"
, note = "https://oaktrust.library.tamu.edu/handle/1969.1/187961"
}


Abstract

Geometric approximation methods are a preferred solution to handle complexities (such as a large volume or complex features such as concavities) in geometric objects or environments containing them. Complexities often pose a computational bottleneck for applications such as motion planning. Exact resolution of these complexities might introduce other complexities such as unmanageable number of components. Hence, approximation methods provide a way to handle these complexities in a manageable state by trading off some accuracy. In this dissertation, two novel geometric approximation methods are studied: aggregation hierarchy and shape primitive skeleton. The aggregation hierarchy is a hierarchical clustering of polygonal or polyhedral objects. The shape primitive skeleton provides an approximation of bounded space as a skeleton of shape primitives. These methods are further applied to improve the performance of motion planning applications. We evaluate the methods in environments with 2D and 3D objects. The aggregation hierarchy groups nearby objects into individual objects. The hierarchy is created by varying the distance threshold that determines which objects are nearby. This creates levels of detail of the environment. The hierarchy of the obstacle space is then used to create a decom-position of the complementary space (i.e, free space) into a set of sampling regions to improve the efficiency and accuracy of the sampling operation of the sampling based motion planners. Our results show that the method can improve the efficiency (10 − 70% of planning time) of sampling based motion planning algorithms. The shape primitive skeleton inscribes a set of shape primitives (e.g., sphere, boxes) inside a bounded space such that they represent the skeleton or the connectivity of the space. We apply the shape primitive skeletons of the free space and obstacle space in motion planning problems to improve the collision detection operation. Our results also show the use of shape primitive skeleton in both spaces improves the performance of collision detectors (by 20 − 70% of collision detection time) used in motion planning algorithms. In summary, this dissertation evaluates how geometric approximation methods can be applied to improve the performance of motion planning methods, especially, sampling based motion planning methods


Motion Planning using Hierarchical Aggregation of Workspace Obstacles, Mukulika Ghosh, Shawna Thomas, Marco Morales, Sam Rodriguez, and Nancy M. Amato, In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pp. 5716-5721, Daejeon, Korea, Oct 2016. DOI: 10.1109/IROS.2016.7759841
Keywords: Motion Planning, Workspace Topology
Links : [Published]

BibTex

@inproceedings{ghosh2016motion,
title={Motion planning using hierarchical aggregation of workspace obstacles},
author={Ghosh, Mukulika and Thomas, Shawna and Morales, Marco and Rodriguez, Sam and Amato, Nancy M},
booktitle={2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)},
pages={5716--5721},
year={2016},
organization={IEEE}
}


Abstract

Sampling-based motion planning is the state-of-the-art technique for solving challenging motion planning problems in a wide variety of domains. While generally successful, their performance suffers from increasing problem complexity. In many cases, the full problem complexity is not needed for the entire solution. We present a hierarchical aggregation framework that groups and models sets of obstacles based on the currently needed level of detail. The hierarchy enables sampling to be performed using the simplest and most conservative representation of the environment possible in that region. Our results show that this scheme improves planner performance irrespective of the underlying sampling method and input problem. In many cases, improvement is significant, with running times often less than 60% of the original planning time.


Fast Approximate Convex Decomposition, Mukulika Ghosh, Texas A&M University, College Station, TX, Aug 2012.
Keywords: Computational Geometry, Convex Decomposition
Links : [Published]

BibTex

TODO: Ghosh, Mukulika (2012). Fast Approximate Convex Decomposition. Master's thesis, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /ETD -TAMU -2012 -08 -11873.


Abstract

Approximate convex decomposition (ACD) is a technique that partitions an input object into "approximately convex" components. Decomposition into approximately convex pieces is both more efficient to compute than exact convex decomposition and can also generate a more manageable number of components. It can be used as a basis of divide-and-conquer algorithms for applications such as collision detection, skeleton extraction and mesh generation. In this paper, we propose a new method called Fast Approximate Convex Decomposition (FACD) that improves the quality of the decomposition and reduces the cost of computing it for both 2D and 3D models. In particular, we propose a new strategy for evaluating potential cuts that aims to reduce the relative concavity, rather than absolute concavity. As shown in our results, this leads to more natural and smaller decompositions that include components for small but important features such as toes or fingers while not decomposing larger components, such as the torso that may have concavities due to surface texture. Second, instead of decomposing a component into two pieces at each step, as in the original ACD, we propose a new strategy that uses a dynamic programming approach to select a set of n_c non-crossing (independent) cuts that can be simultaneously applied to decompose the component into n_c + 1 components. This reduces the depth of recursion and, together with a more efficient method for computing the concavity measure, leads to significant gains in efficiency. We provide comparative results for 2D and 3D models illustrating the improvements obtained by FACD over ACD and we compare with the segmentation methods given in the Princeton Shape Benchmark.


Approximate Convex Decomposition of Polyhedra, Jyh-Ming Lien, Nancy M. Amato, Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling (SPM 07), pp. 121-131, Jun 2007. DOI: https://doi.org/10.1145/1236246.1236265
Keywords: Computational Geometry, Convex Decomposition
Links : [Published]

BibTex

@inproceedings{10.1145/1236246.1236265,
author = {Lien, Jyh-Ming and Amato, Nancy M.},
title = {Approximate Convex Decomposition of Polyhedra},
year = {2007},
isbn = {9781595936660},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1236246.1236265},
doi = {10.1145/1236246.1236265},
abstract = {Decomposition is a technique commonly used to partition complex models into simpler components. While decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this paper we explore an alternative partitioning strategy that decomposes a given model into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficiently. Indeed, for many applications, an approximate convex decomposition (ACD) can more accurately represent the important structural features of the model by providing a mechanism for ignoring less significant features, such as surface texture. We describe a technique for computing ACDs of three-dimensional polyhedral solids and surfaces of arbitrary genus. We provide results illustrating that our approach results in high quality decompositions with very few components and applications showing that comparable or better results can be obtained using ACD decompositions in place of exact convex decompositions (ECD) that are several orders of magnitude larger.},
booktitle = {Proceedings of the 2007 ACM Symposium on Solid and Physical Modeling},
pages = {121–131},
numpages = {11},
keywords = {concavity measurement, convex decomposition},
location = {Beijing, China},
series = {SPM '07}
}


Abstract

Decomposition is a technique commonly used to partition complex models into simpler components. While decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this paper we explore an alternative partitioning strategy that decomposes a given model into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficiently. Indeed, for many applications, an approximate convex decomposition (ACD) can more accurately represent the important structural features of the model by providing a mechanism for ignoring less significant features, such as surface texture. We describe a technique for computing ACDs of three-dimensional polyhedral solids and surfaces of arbitrary genus. We provide results illustrating that our approach results in high quality decompositions with very few components and applications showing that comparable or better results can be obtained using ACD decompositions in place of exact convex decompositions (ECD) that are several orders of magnitude larger.


Approximate Convex Decomposition and its Applications, Jyh-Ming Lien, Doctoral dissertation, Texas A & M University, College Station, Texas, USA, Dec 2006. DOI: N/A
Keywords: Computational Geometry, Convex Decomposition
Links : [Published]

BibTex

@phdthesis{lien2006approximate,
title={Approximate convex decomposition and its applications},
author={Lien, Jyh-Ming},
volume={69},
number={01},
year={2006}
}


Abstract

Geometric computations are essential in many real-world problems. One important issue in geometric computations is that the geometric models in these problems can be so large that computations on them have infeasible storage or computation time requirements. Decomposition is a technique commonly used to partition complex models into simpler components. Whereas decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this work, we have developed an approximate technique, called Approximate Convex Decomposition (ACD), which decomposes a given polygon or polyhedron into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficently. Indeed, for many applications, an ACD can represent the important structural features of the model more accurately by providing a mechanism for ignoring less significant features, such as wrinkles and surface texture. Our study of a wide range of applications shows that in addition to providing computational efficiency, ACD also provides natural multi-resolution or hierarchical representations. In this dissertation, we provide some examples of ACD's many potential applications, such as particle simulation, mesh generation, motion planning, and skeleton extraction.


Simultaneous Shape Decomposition and Skeletonization, Jyh-Ming Lien, John Keyser , Nancy M. Amato, In. Proc. of the 2006 ACM symposium on Solid and physical modeling, Cardiff, Wales, United Kingdom, Jun 2006. DOI: 10.1145/1128888.1128919
Keywords: Computational Geometry, Convex Decomposition
Links : [Published]

BibTex

@inproceedings{10.1145/1128888.1128919,
author = {Lien, Jyh-Ming and Keyser, John and Amato, Nancy M.},
title = {Simultaneous Shape Decomposition and Skeletonization},
year = {2006},
isbn = {1595933581},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1128888.1128919},
doi = {10.1145/1128888.1128919},
booktitle = {Proceedings of the 2006 ACM Symposium on Solid and Physical Modeling},
pages = {219–228},
numpages = {10},
keywords = {skeletonization, convex decomposition, multi-resolution skeleton},
location = {Cardiff, Wales, United Kingdom},
series = {SPM '06}
}


Abstract

Shape decomposition and skeletonization share many common properties and applications. However, they are generally treated as independent computations. In this paper, we propose an iterative approach that simultaneously generates a hierarchical shape decomposition and a corresponding set of multi-resolution skeletons. In our method, a skeleton of a model is extracted from the components of its decomposition --- that is, both processes and the qualities of their results are interdependent. In particular, if the quality of the extracted skeleton does not meet some user specified criteria, then the model is decomposed into finer components and a new skeleton is extracted from these components. The process of simultaneous shape decomposition and skeletonization iterates until the quality of the skeleton becomes satisfactory. We provide evidence that the proposed framework is efficient and robust under perturbation and. deformation. We also demonstrate that our results can readily be used in problems including skeletal deformations and virtual reality navigation.


Approximate Convex Decomposition, Jyh-Ming Lien, Nancy M. Amato, Proceedings of the Twentieth Annual Symposium on Computational Geometry (SOCG 04), pp. 457-458, Brooklyn, New York, Jun 2004. DOI: 10.1145/997817.997889
Keywords: Computational Geometry
Links : [Published]

BibTex

@inproceedings{ la-acd-04
, author = "J.-M. Lien and N. M. Amato"
, title = "Approximate Convex Decomposition"
, booktitle = "Proc.\ 20th Annual {ACM} Symp.\ Computat.\ Geom.\ (SoCG)"
, year = "2004"
, month = "June"
, note = "Video Abstract."
, pages = "457--458"
}


Abstract

Not applicable (it is a video abstract)


Approximate Decomposition of Polygons, Jyh-Ming Lien, Nancy M. Amato, Proceedings of the Twentieth Annual Symposium on Computational Geometry (SOCG 04), pp. 17-26, Brooklyn, New York, Jun 2004. DOI: 10.1145/997817.997823
Keywords: Computational Geometry, Convex Decomposition
Links : [Published]

BibTex

@inproceedings{ la-acdp-04
, author = "J.-M. Lien and N. M. Amato"
, title = "Approximate Convex Decomposition of Polygons"
, booktitle = "Proc.\ 20th Annual {ACM} Symp.\ Computat.\ Geom.\ (SoCG)"
, year = "2004"
, month="June"
, pages = "17--26"
}


Abstract

We propose a strategy to decompose a polygon, containing zero or more holes, into ``approximately convex'' pieces. For many applications, the approximately convex components of this decomposition provide similar benefits as convex components, while the resulting decomposition is significantly smaller and can be computed more efficiently. Moreover, our approximate convex decomposition (ACD) provides a mechanism to focus on key structural features and ignore less significant artifacts such as wrinkles and surface texture a user specified tolerance determines allowable concavity. We propose a simple algorithm that computes an ACD of a polygon by iteratively removing (resolving) the most significant non-convex feature (notch). As a by product, it produces an elegant hierarchical representation that provides a series of `increasingly convex' decompositions. Our algorithm computes an ACD of a simple polygon with n vertices and r notches in O(nr) time. In contrast, exact convex decomposition is NP-hard or,if the polygon has no holes, takes O(nr2) time.