Renato Negrinho (IT)
Shape Representation via Symmetric Polynomials: A Complete Invariant Inspired by the Bispectrum
Abstract:
We address the representation of two-dimensional shapes in its most general form, i.e., arbitrary sets of points. Examples of these shapes arise in multiple situations, in the form of sparse sets of representative landmarks, or dense sets of image edge points. Our goal are recognition tasks, where the key is balancing two contradicting demands: shapes that differ by rigid transformations or point relabeling should have the same representation (invariance), but geometrically distinct shapes should have different representations (completeness).
We introduce a new shape representation that marries properties of the symmetric polynomials and the bispectrum. Like the power spectrum, the bispectrum is insensitive to signal shifts; however, unlike the power spectrum, the bispectrum is complete. Particular sets of symmetric polynomials, the so-called elementary ones and the power sums, are complete and invariant to variable relabeling. We show that these polynomials of the shape points depend on the shape orientation in a way that enables interpreting them in the frequency domain and building from them a bispectrum. The result is a shape representation that is complete and invariant to rigid transformations and point relabeling.
We describe the shape representation problem in a very general way by using concepts of group theory. The concept of shape is determined by the definition of the required shape-preserving transformations (e.g., point relabeling and/or geometric ones) through group actions. Shapes are then identified with the orbits of the actions of those groups and shape representation amounts to representing those orbits. This way, as pretended, elements that belong to the same orbit have the same representation and elements that belong to different orbits have different representations. The proposed shape representation attains this goal.
We describe how the proposed representation can be efficiently computed from the shape points using dynamic programming and end by describing experiments that illustrate the proved properties.
--
Bio: Renato Negrinho received a M.Sc degree in Electrical and Computer Engineering from Instituto Superior Técnico, Portugal, in 2013. He currently holds a research scholarship and is working on NLP and Machine Learning problems under the supervision of André Martins at Priberam. He is interested in machine learning, optimization and the application of mathematics in general to solve difficult problems in science.