Abstract: Similarity measurement is the key of Geography Information System (GIS), it is widely applied to spatial retrieval, spatial information integration and spatial data mining, etc. By considering the scale difference and studying the spatial semantics of spatial scenes, this paper build a formalized description model of spatial scene. According to the description model, multi-scale spatial scenes can be abstracted to feature matrices that contain the essential features. With feature matrices, we establish the initial probability matrix of spatial scenes, and iteratively update the matrix by relaxation labeling approach until it convergences to a global minimum value. After that the matched objects between two spatial scenes can be found. Accordingly, we calculate the spatial scenes similarity. In the experiment stage, Wuhan residential region data was adopted. We analyze the accuracy and total time spent of spatial scene matching process under different neighborhood searching radius. The experimental result confirms that spatial scene matching based on relaxation labeling approach has a high accuracy.