We present a new terrain classification technique both for effective, autonomous locomotion over rough, unknown terrains and for the qualitative analysis of terrains for exploration and mapping. Our approach requires a single camera with little processing of visual information. Specifically, we derived a gait bounce measure from visual servoing errors that results from vehicle-terrain interactions during normal locomotion. Characteristics of the terrain, such as roughness and compliance, manifest themselves in the spatial patterns of this signal and can be extracted using pattern classification techniques. This vision-based approach is particularly beneficial for resource-constrained robots with limited sensor capability. In this paper, we present the gait bounce derivation. We demonstrate the viability of terrain classification for legged vehicles using gait bounce with a rigorous study of more than 700 trials, obtaining an 83% accuracy on a set of laboratory terrains. We describe how terrain classification may be used for gait adaptation, particularly in relation to an efficiency metric. We also demonstrate that our technique may be generally applicable to other locomotion mechanisms such as wheels and treads.