We present an intuitive scheme for lossy color-image compression: Use the color information from a few representative pixels to learn a model which predicts color on the rest of the pixels. Now, storing the representative pixels and the image in grayscale suffice to recover the original image. A similar scheme is also applicable for compressing videos, where a single model can be used to predict color on many consecutive frames, leading to better compression. Existing algorithms for colorization - the process of adding color to a grayscale image or video sequence - are tedious, and require intensive human-intervention. We bypass these limitations by using a graph-based inductive semi-supervised learning module for colorization, and a simple active learning strategy to choose the representative pixels. Experiments on a wide variety of images and video sequences demonstrate the efficacy of our algorithm.