Shape similarity based on combinatorial maps and a tree pattern kernel

While the skeleton of a 2D shape corresponds to a planar graph, its encoding by usual graph data structures does not allow to capture its planar properties. Graph kernels may be defined on graph's encoding of the skeleton in order to define a similarity measure between shapes. Such graph kernels are usually based on a decomposition of graphs into bags of walks or trails. These linear patterns do not allow to fully encode the structure of a skeleton on branching points, hence losing important informations about the shape. This paper aims to solve these two drawbacks by using an encoding of the skeleton taking explicitly into account the orientation of the plane and by decomposing the resulting graph model into both linear and nonlinear patterns.