This paper presents a method that is capable of robustly estimating gait phase of a human walking using the motion of a sparse cloud of feature points extracted using a standard feature tracker. We first learn statistical motion models of the trajectories we would expect to observe for each of the main limbs. By comparing the motion of the tracked features to our models and integrating over all features we create a state probability matrix that represents the likelihood of being at a particular phase as a function of time. By using dynamic programming and allowing only likely phase transitions to occur between consecutive frames, an optimal solution can be found that estimates the gait phase for each frame. This work demonstrates that despite the sparsity and noise contained in the tracking data, the information encapsulated in the motion of these points is sufficient to extract gait phase to a high level of accuracy. Presented results demonstrate our system is robust to changes in height of the walker, gait frequency and individual gait characteristics.