In this pater, we propose a method for matching of two images (stereo, motion stereo, etc.) using relaxation. We have already proposed an algebraic expression of line images using unit vectors, and matching method based on similarity measure between two image graphs. This similarity measure of images is insensitive to scaling, rotation, gray level modification and small motion between the two images in the case when we examine image registration or image matching. The approach based on the line structural similarity results in high rate of correspondence between nodes of the two images. In order to obtain higher rate of correspondence, we introduce a relaxation method when examine the degree of similarity between the two images. Our relaxation method improves a relational similarity of correspondence between two image graphs in an iterative manner. The relational similarity is defined as a correct likelihood of correspondence between nodes in consideration of connective relationship of the image graphs. Finally, we show several experimental results which confirm effectiveness of our approach.