We describe a state-space tracking approach based on a Conditional Random Field(CRF) model, where the observation potentials are \emph{learned} from data. Wefind functions that embed both state and observation into a space wheresimilarity corresponds to $L_1$ distance, and define an observation potentialbased on distance in this space. This potential is extremely fast to compute and in conjunction with a grid-filtering framework can be used to reduce acontinuous state estimation problem to a discrete one. We show how a statetemporal prior in the grid-filter can be computed in a manner similar to asparse HMM, resulting in real-time system performance. The resulting system isused for human pose tracking in video sequences.