Object localization using affine invariant substructure constraints

In this paper we propose a novel method for generic object localization. The method is based on modeling the object as a graph at two levels: a local substructural representation and a global object graph. In the first level, an object substructure is a quasi affine-invariant canonical encoding of a set of four straight contour lines of the object. The second level is a connectivity graph of these substructures that defines the object. The candidate substructures in an observed image are selected probabilistically using the model distribution. To extract the object graph from these candidates, we exploit the strong inter-structural affinities within the object. We consider the connected graph of all candidates and find a bi-partition of this graph. Finally, the partition with higher density (and hence with higher affinity) is selected and labeled as the object structure. This method is independent of affine transformations of objects and robust to intra-class variability and partial occlusion.