Obstacle detection on the road is a key function for self-driving vehicles. A lot of research has focused on detecting large obstacles such as cars and pedestrians. Small obstacles can also be the source of serious accidents, especially at high speed. We present an approach for detecting anomalies on the road using a higher-order Boltzmann machine. As opposed to conventional anomaly detectors the proposed system learns to inpaint the road patches with commonly occurring road features such as lane markings and expansion dividers, depending on the context. The system does not consider these frequent road artifacts as anomalies and significantly reduces the number of obstacle candidates. We show initial empirical results for anomaly detection with this new approach.