Shape representation and recognition based on invariant unary and binary relations

The problem of transformation invariant object recognition is considered. W e develop a projective transformation invariant representation for both sce ne and model which facilitates an attributed relational graph object matchi ng based only on unary and binary relations. The unary and binary measureme nts used for matching are derived from sets of reference points such as cor ners and bi-tangent points which are stable under the various transformatio ns considered. Each set of reference points is used to generate a distinct barycentric coordinate basis system associated with one node of the object graph representation. We show that barycentric coordinates of the reference image points can be made invariant under any arbitrary projective transfor mation. The conditions that must hold for a basis to be valid are stated. W e illustrate the construction of the barycentric coordinate systems for the affine and perspective transformations. For the object and scene represent ation we use the barycentric coordinates of the reference points generating the barycentric coordinate system, together with auxiliary measurements su ch as colour and texture as the node's unary measurements. For binary measu rements we use the product of the barycentric coordinate system for one nod e with the inverse of the barycentric coordinate system associated with ano ther node. The unary and binary relations provide an orthogonal decompositi on of the shape being matched. They are used in a relaxation process to det ect instances of objects consistent with a given model. We demonstrate the proposed methodology of projective transformation invariant object represen tation on several examples. First we illustrate the stability of the shape representation in terms of unary relations both visually and numerically. W e then experimentally demonstrated the invariance of binary relations on a star-like object. We show experimentally that the binary relations derived are invariant. The final example demonstrates the proposed approach as a to ol for 3D object recognition. The aim is to recognize 3D objects in terms o f planar faces. A hexagonal model shape is hypothesized in the image. The o nly instance of the hypothesized model is successfully recovered. (C) 1999 Elsevier Science B.V. All rights reserved.