Deinterlacing of video involves converting interlaced video to progressive video by interpolating a missing pixel in the interlaced video from other pixels in the video. A plurality of interpolants are provided, each of which interpolates a pixel value from other pixels that are nearby in space and/or time. The data costs of using the various interpolants is calculated. A particular one of the interpolants is chosen based on the data costs associated with the various interpolants. The chosen interpolant is used to interpolate the value of the missing pixel. The interpolated pixel value may be refined based on exemplars. The exemplars may be taken from the video that is being deinterlaced.