Improving skeletal shape abstraction using multiple optimal solutions

• Skeletal shape abstraction is reformulated as the transportation problem.
• A distortion-free graph embedding is used for a better representation.
• All optimal solutions for the transportation problem are considered.
• The optimal solution which most resembles the neighborhood relations is used.
• Experiments demonstrate the improved performance.

Shape abstraction is an important problem faced by researchers in many fields such as pattern recognition, computer vision, and industrial design. A recently-developed previous shape abstraction framework (Demirci et al. [20]) generates an abstracted shape based on the correspondences between the features of the input shapes, where the correspondences are obtained using the first optimal solution of a well-known transportation problem. As the size of the feature space grows, the possibility of having more than one optimal solution for the same problem increases. Considering the case where multiple optimal solutions exist for the same transportation problem, we first rank all optimal solutions based on how much they preserve the local neighborhood relations in this paper. Instead of creating the abstracted shape using the first optimal solution as done by the previous work, we create the abstracted shape using the highest-ranked optimal solution. With this new property, more effective abstracted shapes are generated. Experimental evaluation of the framework demonstrates that the proposed approach compares favorably with the previous technique in a set of shape retrieval experiments for different datasets.