Gait as a biometric was inspired by the ability to recognize an acquaintance by his manner of walking even when seen at a distance. In this paper, we describe a novel Fourier descriptor based gait recognition method that models the periodic deformation of human contours. A new measure of similarity using the product of Fourier coefficients is proposed as a distance measure between closed curves. In order to maximize the similarity between subsequent closed curves, the assembly of contours in gait cycle is circularly shifted by a circular permutation matrix. Subsequently, an element-wise frame interpolation is correspondingly applied to produce length invariant gait signatures. The experiments on OU-ISIR gait database and CASIA gait database reveal promising recognition accuracy. The element-wise frame interpolation method is able to preserve temporal information even when the gait cycles change, and therefore offers a better robustness to slight variation in walking speed.