Step detection and step length estimation techniques include detecting salient points in sensor data of one or more sensors. A step frequency is estimated based on a time interval between the detected salient points. A step length of the step may then be computed based on a nonlinear combination of the estimated step frequency and a function of the sensor data, and/or a step model. Alternatively, the step length of the step may be computed based on a combination of a nonlinear function of the estimated step frequency and a (linear or nonlinear) function of the sensor data, and/or a step model.