Gait analysis using footprints is a simple method of obtaining valuable information relating to gait conditions. Recently, we have developed a gait analysis system which recognizes each footprint from foot trace images recorded on a paper of 10m length and calculates various parameters such as each step length, step width, etc. In addition to these parameters, a new index called the shape similarity measure can be derived from footprint data. This paper describes a method of determining the shape similarity of two footprints by using image processing. The method consists of the following three procedures. (1)The edge of a footprint shape is detected and identified according to each part such as plantar and toes. (2)The edge shape is decomposed and represented as a hierarchical tree structure with convex components. (3)The corresponding components between two tree structures to be compared are decided and the similarity of each component is calculated. This method is applied to rehabilitation patients and non-handicapped persons. The results suggest that the similarity measure is effective to some extent to investigate the change of gait condition.