Deinterlacing, defined as the process of converting a stream of interlaced frames into a sequence of progressive frames, represents a key feature in video processing. The interlaced video format, introduced by the old analog television transmission systems as a trade-off between framerate and bandwidth capacity, has become obsolete nowadays, when all transmissions are digital. Moreover, almost all recent displays—whether LCD or plasma—require progressive video input, whereas much of the available video content is in interlaced format. In this paper an adaptive, edge-preserving motion-compensated approach for video deinterlacing is proposed. The algorithm preserves strong edges and interpolates the missing pixels along the contours depending on the motion-degree of the region to which they belong. Our proposal is optimized to lower heavy computation, which is the main drawback of motion-compensated deinterlacing algorithms. Therefore it provides complexity scalability as a trade-off tool between performance and computation time. Experiments demonstrate a significant gain in reconstruction quality as compared to other deinterlacing implementations.