We present a system, which is able to track multiple objects under partial and total occlusion. The reasoning system builds up a graph based spatio-temporal representation of object hypotheses and thus is able to explain the scene even if objects are totally occluded. Furthermore it adapts the object models and learns new appearances at assumed object locations. We represent objects in a star-shaped geometrical model of interest points using a codebook. The novelty of our system is to combine a spatio-temporal reasoning system and an interest point based object detector for on-line improving of object models in terms of adding new, and deleting unreliable interest points. We propose this system for a consistent representation of objects in an image sequence and for learning changes of appearances on the fly.