In this paper, we propose a graph-based shape matching method for deformable objects. In our approach, a graph is
generated from an over-segmented input image, and a shape matching problem is treated as finding a optimal cycle in the
graph. Given a shape template and a graph generated from the input, a product graph is generated to consider every possible correspondences between graph edges and template subparts. Because the proposed approach can estimate correct correspondences between a target object and a template, the target object can be found robustly in the presence of shape deformation and background clutter. The experiments on various examples are also presented to verify the performance of the proposed method.