De-Interlacing Using Nonlocal Costs and Markov-Chain-Based Estimation of Interpolation Methods

A new method of de-interlacing is proposed. De-interlacing is revisited as the problem of assigning a sequence of interpolation methods (interpolators) to a sequence of missing pixels of an interlaced frame (field). With this assumption, our de-interlacing algorithm (de-interlacer), undergoes transitions from one interpolation method to another, as it moves from one missing pixel position to the horizontally adjacent missing pixel position in a missing row of a field. We assume a discrete countable-state Markov-chain model on the sequence of interpolators (Markov-chain states) which are selected from a user-defined set of candidate interpolators. An estimation of the optimum sequence of interpolators with the aforementioned Markov-chain model requires the definition of an efficient cost function as well as a global optimization technique. Our algorithm introduces for the first time using a nonlocal cost (NLC) scheme. The proposed algorithm uses the NLC to not only measure the fitness of an interpolator at a missing pixel position, but also to derive an approximation for transition matrix (TM) of the Markov-chain of interpolators. The TM in our algorithm is a frame-variate matrix, i.e., the algorithm updates the TM for each frame automatically. The algorithm finally uses a Viterbi algorithm to find the global optimum sequence of interpolators given the cost function defined and neighboring original pixels in hand. Next, we introduce a new MAP-based formulation for the estimation of the sequence of interpolators this time not by estimating the best sequence of interpolators but by successive estimations of the best interpolator at each missing pixel using Forward-Backward algorithm. Simulation results prove that, while competitive with each other on different test sequences, the proposed methods (one using Viterbi and the other Forward-Backward algorithm) are superior to state-of-the-art de-interlacing algorithms proposed recently. Finally, we propose motion compensated versions of our algorithm based on optical flow computation methods and discuss how it can improve the proposed algorithm.