A visual tracker tracks an object in a sequence of input images. A tracking module detects a location of the object based on a set of weighted blocks representing the object's shape. The tracking module then refines a segmentation of the object from the background image at the detected location. Based on the refined segmentation, the set of weighted blocks are updated. By adaptively encoding appearance and shape into the block configuration, the present invention is able to efficiently and accurately track an object even in the presence of rapid motion that causes large variations in appearance and shape of the object.