Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for performing visual tracking. In one aspect, a method comprises receiving: (i) one or more reference video frames, (ii) respective reference labels for each of a plurality of reference pixels in the reference video frames, and (iii) a target video frame. The reference video frames and the target video frame are processed using a colorization machine learning model to generate respective pixel similarity measures between each of (i) a plurality of target pixels in the target video frame, and (ii) the reference pixels in the reference video frames. A respective target label is determined for each target pixel in the target video frame, comprising: combining (i) the reference labels for the reference pixels in the reference video frames, and (ii) the pixel similarity measures.