Video-based gait recognition is a challenging problem in computer vision. In this paper, fractal scale wavelet analysis is applied to describe and automatically recognize gait. Fractal scale based on wavelet analysis represents the self-similarity of signals, and improves the flexibility of wavelet moments. Optimal wavelets based on generalized multi-resolution analysis are used to improve the recognition rate. Descriptors of fractal scale are translation, scale and rotation invariant. Moreover, a combination of fractal scale and wavelet moments improves the recognition rate. Experiments show that the proposed descriptor is efficient for gait recognition.