Local feature-based object recognition methods recognize learned objects by unordered local feature matching followed by verification. However, the matching between unordered feature sets might be ambiguous as the number of objects increases, because multiple similar features can be observed in different objects. In this context, we present a new method for textured object recognition based on relational information between local features. To efficiently reduce ambiguity, we represent objects using the Attributed Relational Graph. Robust object recognition is achieved by the inexact graph matching. Here, we propose a new method for building graphs and define robust attributes for nodes and edges of the graph, which are the most important factors in the graphbased object representation, and also propose a cost function for graph matching. Dependent on the proposed attributes, the proposed framework can be applied to both single-image-based and stereo-image-based object recognition.