Partition-based optimization model for generative anatomy modeling language (POM-GAML)

BACKGROUND: This paper presents a novel approach for Generative Anatomy Modeling Language (GAML). This approach automatically detects the geometric partitions in 3D anatomy that in turn speeds up integrated non-linear optimization model in GAML for 3D anatomy modeling with constraints (e.g. joints). This integrated non-linear optimization model requires the exponential execution time. However, our approach effectively computes the solution for non-linear optimization model and reduces computation time from exponential to linear time. This is achieved by grouping the 3D geometric constraints into communities. METHODS: Various community detection algorithms (k-means clustering, Clauset Newman Moore, and Density-Based Spatial Clustering of Applications with Noise) were used to find communities and partition the non-linear optimization problem into sub-problems. GAML was used to create a case study for 3D shoulder model to benchmark our approach with up to 5000 constraints. RESULTS: Our results show that the computation time was reduced from exponential time to linear time and the error rate between the partitioned and non-partitioned approach decreases with the increasing number of constraints. For the largest constraint set (5000 constraints), speed up was over 2689-fold whereas error was computed as low as 2.2%. CONCLUSION: This study presents a novel approach to group anatomical constraints in 3D human shoulder model using community detection algorithms. A case study for 3D modeling for shoulder models developed for arthroscopic rotator cuff simulation was presented. Our results significantly reduced the computation time in conjunction with a decrease in error using constrained optimization by linear approximation, non-linear optimization solver.