The voronoi diagram is our first step. It is used in our method as a discrete approximation of the Medial Axis Transform of Blum (1967). These shape skeletons are extremely sensitive to the noise in the contour; a small bump added to the contour will add an entire new skeletal branch. We take the medial axis and prune branches to find the MAP skeleton (Feldman & Singh, 2006), which results in shape skeletons with one axis for each perceptually salient shape part. We would like a system that classifies objects based upon their shape to give the same classification even if in some images the boundary extracted for an image has more noise than the object boundary might have in a different image, which makes the MAP skeleton a good representation for us to use.
Specifically, the MAP skeleton is looking for the skeleton that maximizes the posterior p(skeleton | shape), which is proportional to p(skeleton) and p(shape | skeleton).
p(skeleton) gives higher probability to skeletons that have fewer branches and have straighter axes.
p(shape | skeleton) gives the current shape a high probability if it is well fit to the skeleton, which gives a preference to more complex skeletons.
The posterior then balances complexity and explanatory power of the skeleton.

Thank you for your great question. The evidence that the Tensor model [ Gnang, Elgammal, Retakh 2011] improves over other approaches comes from the fact that the tensor model captures many alternative discrete shape models based on matrix analysis, while providing a natural generalization to higher order correlation settings. Finally the tensor framework allows us to express explicitly the running time of induced algorithms in terms of the symmetries present in the shape.

Thank you very much for your questions. Allow me to address the computational aspects of the Tensor model. As formulated the shape recognition problem reduces to hypergraph sub-isomorphism instances and unless P=NP there should be no polynomial time algorithm for solving the problem in complete generality. However we have not yet tried our algorithm on computer vision datasets so it remains to be determined how it will compare to other approaches. Our overall approach improves on the generic Gröbner basis approach for solving hypergraph sub-isomorphism and we express the running time of our algorithms in terms of the size of the automorphism group of the hypergraph.

The practical application of recognizing if a silhouette is an animal or leaf was added to show that our IGERT is working on a breadth of approaches in both computer and human vision. We have not directly compared the skeletal model to the state of the art in computer vision because the questions in that project are about the human visual system (whether or not a skeletal representation contains psychologically relevant information above and beyond what would be easily accessible from a contour representation), and since we are only using a couple properties/summaries of the shape skeleton an approach that includes additional information, such as color or texture, would perform better. Also, the test we performed was how consistent the skeletal model’s classifications were with human classifications. There is no “correct” answer in this test, we are simply comparing to human data. We did use alternative representations that have been suggested to be psychologically relevant, such as various contour representations, aspect ratio, compactness, perimeter/area^2, contour complexity, and combinations of those representations. These all failed to predict the human classifications.

Thank you for your remark, The next step would consist in trying our model and proposed algorithm on various datasets and implement efficient libraries for performing spectral analysis of tensors.

Thanks for your comments , the skeleton project is somewhat independent of the point cloud model. It is meant to complement a computer vision approach with a human vision approach. As far as I know we did not show the subjects any shape that was created with erroneous branches. But it sounds like a great idea for future direction.

A lab involved in our IGERT has not looked at classification of shapes with extra branches, but there has been work looking at different types of shape deformations that are either natural or unnatural. They find that human perception distinguishes between unnatural shape deformations (the addition of an extra shape part/skeletal branch, or the translation of a skeletal branch) and natural ones (articulation of a skeletal branch).

Thank you very much for your comments. We have not yet used the point cloud invariants to classify skeleton shape models. But it seems like a great idea to pursue in the future.

Thanks, we owe a lot if not all to our great professors such as yourself for the constant inspiration and the diligent mentorship we have received during our training.

Thanks a lot