In this paper, we propose an MRF-based deinterlacing algorithm that combines the benefits of rule-based algorithms such as motion-adaptation, edge-directed interpolation, and motion compensation, with those of an MRF formulation. MRF-based interpolation and enhancement algorithms are typically formulated as an optimization over pixel intensities or colors, which can make them relatively slow. In comparison, our MRFbased deinterlacing algorithm uses interpolation functions as labels. We use 7 interpolants (3 spatial, 3 temporal, and 1 for motion compensation). The core dynamic programming algorithm is therefore sped up greatly over the direct use of intensity as labels. We also show how an exemplar-based learning algorithm can be used to refine the output of our MRF-based algorithm. The training set can be augmented with exemplars from static regions of the same video, as a form of “self-learning.”