A computer implemented method comprising: 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, said labels indicating, for each of multiple possible categories, a respective likelihood that the pixel corresponds to one of the categories, or for each of multiple possible key points, a respective likelihood that the pixel corresponds to the key point, and (iii) a target video frame; processing the reference video frames and the target video frame using a colorization machine learning model, which includes an embedding neural network, 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, said processing comprising: providing the reference video frames and the target video frame as an input to the embedding neural network; processing the input in accordance with current values of embedding neural network parameters to generate a respective embedding of each of (i) the target pixels in the target video frame, and (ii) the reference pixels in the reference video frames; and generating the respective pixel similarity measures between each of (i) the target pixels in the target video frame, and (ii) the reference pixels in the reference video frames using the embeddings; wherein the colorization machine learning model is trained to generate pixel similarity measures wherein a respective estimated color of each of the target pixels in the target video frame is defined by combining: (i) actual colors of each of the reference pixels in the reference video frames, and (ii) the pixel similarity measures; and determining a respective target label 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. 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, said labels indicating, for each of multiple possible categories, a respective likelihood that the pixel corresponds to one of the categories, or for each of multiple possible key points, a respective likelihood that the pixel corresponds to the key point, and (iii) a target video frame; processing the reference video frames and the target video frame using a colorization machine learning model, which includes an embedding neural network, 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, said processing comprising: providing the reference video frames and the target video frame as an input to the embedding neural network; processing the input in accordance with current values of embedding neural network parameters to generate a respective embedding of each of (i) the target pixels in the target video frame, and (ii) the reference pixels in the reference video frames; and generating the respective pixel similarity measures between each of (i) the target pixels in the target video frame, and (ii) the reference pixels in the reference video frames using the embeddings; wherein the colorization machine learning model is trained to generate pixel similarity measures wherein a respective estimated color of each of the target pixels in the target video frame is defined by combining: (i) actual colors of each of the reference pixels in the reference video frames, and (ii) the pixel similarity measures; and providing the reference video frames and the target video frame as an input to the embedding neural network; processing the input in accordance with current values of embedding neural network parameters to generate a respective embedding of each of (i) the target pixels in the target video frame, and (ii) the reference pixels in the reference video frames; and generating the respective pixel similarity measures between each of (i) the target pixels in the target video frame, and (ii) the reference pixels in the reference video frames using the embeddings; wherein the colorization machine learning model is trained to generate pixel similarity measures wherein a respective estimated color of each of the target pixels in the target video frame is defined by combining: (i) actual colors of each of the reference pixels in the reference video frames, and (ii) the pixel similarity measures; and determining a respective target label 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.