Attributed Relational Graph (ARG) is a powerful representation for model based object recognition due to its inherent robustness in handling noisy and incomplete data. In the past few years, the availability of efficient ARG matching algorithms and their theoretical underpinnings have greatly contributed to many successful applications of ARG representation in tackling high level vision problems. During my past three year investigation into object recognition using ARG representation, we have developed a number of novel theories and techniques in the subject area. Some are image processing techniques which help to segment and generate primitive features for building ARG representation (Chapter 2 and 4). Some are about projective invariance in ARG representations (Chapter 3 and 5). Some are about new ARG matching algorithms (Chapter 6). This thesis serves as a summary document of these theories and techniques. The most important contributions of our work to the domain of computer vision, in my opinion, are in two areas: Firstly, in the area of projective invariant ARG representation for object recognition. Here, we demonstrated for the first time, a way to systematically derive ARG representation for objects under complex projective transform by exploiting the knowledge of invariance. The methodology developed by us is a sound strategy that generates ARG representations with a number of desirable and provable properties, amongst which, the most important one is the ability to capture global transformation constraint using binary relations only. The approach significantly reduces the heuristic nature of designing relational measurements and paves the way for wider application of ARG representation in 2D and 3D object recognition. Secondly, in the area of ARG matching. A new mathematical framework for deterministic relaxation algorithms was developed to overcome a number of problems appeared in the existing theories and practises of efficient ARG labelling. A novel labelling algorithm was proposed based on the new theoretical framework. The algorithm has a number of desirable properties compared to existing algorithms. In particular, the resulting algorithm delivers more consistent, faithful-to-observation results in the presence of ambiguities and multiple interpretations compared to other algorithms.