Translator Disclaimer
20 October 2015 Efficient deinterlacing method using simple edge slope tracing
Sajid Khan, Dongho Lee
Author Affiliations +
This paper presents a low-complexity interpolation method that minimizes image quality losses at edges, which are easily perceivable by the human eye. Deinterlacing, which converts an interlaced video into a progressive video, is a problem in image interpolation that doubles the number of vertical lines. Applying averaging, or any linear algorithm, achieves time-efficient deinterlacing but produces artifacts. However, applying other complex methods tends to reduce unwanted artifacts but at the cost of high computation time. The proposed deinterlacing scheme is based on an algorithm called “edge slope tracing” which simply predicts the slope on the basis of information on adjacent slopes. Predicted slopes are used to perform deinterlacing in slope-based line averaging. The simulation results show that this scheme provides better results and reduces complexity compared to conventional state-of-the-art algorithms.



In digital image processing, interpolation is used to produce a higher resolution image from a low-resolution image. Image interpolation is applied in many areas in the field of image processing, computer vision, and video format conversion for digital systems. Televisions and monitors are now more flexible at displaying different video formats than they were in the past. This interpolation has become a primary technique to support these digital displays.

The human eye is very sensitive to the edges of images, in particular. In recent years, interpolation algorithms that take the edge’s direction and gradient into account have been proposed. Although such edge-based interpolation algorithms perform better than conventional nonadaptive methods in the subjective perception of image quality, they have limitations in retaining edge information because they cannot accurately identify the edges of the pixels to be interpolated.

Deinterlacing, which converts interlaced video into progressive video, is a problem for image interpolation; it doubles the number of vertical lines.115 In general, TV broadcasters choose interlaced scanning as the main standard for video formats.16 Since it alternately scans two fields by dividing a frame into two parts, interlacing may cause video quality degradation such as flickering. Because many devices such as DTV, UDTV, or other monitors use progressive scanning, the deinterlacing problem has become serious because it converts interlaced scanned videos into progressive scanned videos.

One representative method for deinterlacing is the edge-based line average (ELA),3 whose simple structure improves the edges of images. However, when incorrect directions are identified for edges, ELA can result in video quality degradation. To resolve this issue, several other ELA-improved methods have been suggested. Of these, efficient edge-based line average (EELA)4 and low-complexity deinterlacing5 effectively increase the accuracy of edge direction determination. In addition, fine directional deinterlacing8 and edge-preserving directional deinterlacing10 are suggested to solve difficult interpolation problems in a low-sloped edge domain involving video quality degradation. Binary patterns,9 gradient-guided deinterlacing (GGD),12 deinterlacing with closeness and similarity14 and the moving least-squares method (MLSM)15 have also been suggested as methods to accurately restore various slopes. Nevertheless, when needed for high performance, such methods have some shortcomings in that they experience performance limitations or are difficult to implement in real time due to their high levels of complexity.

In this paper, a new intrafield deinterlacing algorithm based on edge slope tracing (EST) is proposed. EST predicts the slope of the current pixel on the basis of the information obtained from the slope of the adjacent pixel. This method, however, has some serious problems with interpolation for deinterlacing, which diverges when it fails to trace thin lines or edges. To solve these problems, correction techniques consisting of two-way interpolation, thin line correction, and window-based correction are applied. The complexity of the proposed algorithm is closer to those of linear filters such as ELA and is far less than those of other edge-based methods. Simulation results show that the proposed algorithm provides better results compared to other conventional methods proposed to date.

The rest of this paper is organized as follows. Section 2 describes some of the conventional methods. Section 3 describes the proposed EST-based deinterlacing algorithm. Section 4 describes the performance analysis. Section 5 is the conclusion.


Conventional Methods

In this section, conventional deinterlacing methods are discussed. For instance, GGD12 predicts the gradients of missing pixels for interpolating unknown pixel intensity values. The algorithm is based on minimization of the energy function using

Eq. (1)

where ω1, ω2, and ω3 are the weights assigned to each term. D1(fp) and D2(fp) are calculated using a summation of gradients and the intensities of known neighboring pixels, whereas D3(fp) is based on the absolute sum of the upper and lower horizontal distances from an interpolating pixel that defines all possible edge orientations. Since D(fp) is based on various combinations of all neighboring pixels, it increases the complexity of the algorithm.

Low-complexity interpolation method (LCIM)5 is a simple low-complexity algorithm that interpolates a missing pixel along one of the four directions (horizontal, vertical, first diagonal, and second diagonal) on the basis of minimum absolute differences. Since LCIM covers only four slopes, it fails to recover gentle-slope edges, which results in small slope variation.

MLSM15 is based on a coefficient calculation using matrix multiplication operations as follows:

Eq. (2)

where coefficient matrix a can be calculated by matrix multiplication involving the known intensities of neighboring pixels. MLSM uses predetermined matrix multiplication for all unknown pixels that results in a reduction of complexity to a great extent, but does not provide good performance due to its limitation.


Proposed Method

The proposed algorithm is based on a simple efficient technique, EST, which predicts the present slope change using previous slope information. The slope value obtained by EST is used for slope-based interpolation. To remove unwanted artifacts, correction techniques consisting of two-way interpolation and window-based correction are applied. EST and slope-based interpolation are explained in detail followed by a detailed description of the complete proposed algorithm.


Edge Slope Tracing

The existing edge-based interpolation methods are either highly complex or suffer from problems with gently sloped edges. To resolve the issue with interpolating along gentle slopes using averaging techniques, a large mask is needed to detect the slope and to interpolate with the help of the detected slope. Such types of techniques may result in heavy calculations, consuming a large amount of execution time due to the many correlation calculations. This kind of technique may produce an erroneous edge selection if the mask is not large enough. In this paper, a very low-complexity algorithm is used for slope calculation by predicting the current slope on the basis of the slope information of the previous pixel.

Most of the edges experience a gradual change in the slope domain; in other words, new slopes are created by slightly changing the previous slope. EST searches slopes in the edge domain using the slope information of adjacent pixels; this results in the efficient calculation of the edge slope with greatly reduced complexity. Using EST, there is no need to calculate correlations or to use a large mask since the method depends totally on the slope information of the adjacent pixel which has been recursively calculated.

The flow chart of the entire EST process is shown in Fig. 1. Slope kcur of the current pixel is calculated on the basis of the left, right, and middle slopes calculated using slope kprev (the slope of the adjacent pixel). A value of kprev=0 is used as an initial slope for every first pixel of an image, or a new row, or after a discontinuity. For other pixels, the middle (Smid), left (Sleft), and right (Sright) intensity differences that are used in calculating kcur are given as follows:

Eq. (3)

Two examples of calculating the middle, left, and right slopes using different kprev values are shown in Fig. 2. For all calculations, it is assumed that the current pixel is at image location (i,j). Current slope kcur is calculated by incrementing, decrementing, or using the same value of previous slope kprev depending on the conditions, given as follows:

Eq. (4)

To avoid the production of unwanted artifacts in case a wrong value exists for the reference to previous slope kprev, a resetting criterion is used in which the value of the reference to the previous slope is reset to zero if the condition (|Smin(i,j)Smin(i,j1)|>T and |kcur|>1) is satisfied. A large value of |Smin(i,j)Smin(i,j1)| indicates that the region is not smooth, thus the current slope cannot be predicted on the basis of the information of the previous slope. A large value of T may fail in an efficient reset of the reference slope, whereas a very small value may result in a frequent reset of the reference slope. T=10 is used on the basis of extensive simulations.

Fig. 1

Flow chart of the edge slope tracing (EST) process.


Fig. 2

Examples of slope calculation: (a), (b), and (c) are middle, left, and right slopes using a previous slope=0. (d), (e), and (f) are middle, left, and right slopes using a previous slope=1.



Slope-Based Interpolation

On the basis of slope kcur calculated using EST, the pixel intensity at location (i,j) can be interpolated using

Eq. (5)

Figure 3 shows different examples of the calculation of the interpolated pixel at location (i,j) using different values of kcur. Small gray circles show pixels that are used in slope-based interpolation, whereas large gray circles show pixels that are interpolated by averaging small gray pixels.

Fig. 3

Examples of slope-based interpolation using different slopes: (a) 2, (b) 1, (c) 0, (d) 1, and (e) 2.



Entire Algorithm with Artifact Reduction

The flow chart of the entire proposed algorithm is shown in Fig. 4. First of all, it detects if a pixel to be interpolated is at a vertical or thin edge. For vertical or thin edges, line averaging works well, whereas for other slopes, slope-based interpolation works well and produces good results on the basis of slope prediction.

Fig. 4

Flow chart of the proposed interpolation method.


Fig. 5

Differences for determining ±75 or 90 deg slope: (a) d1, (b) d2, and (c) d3.


The differences for deciding a vertical slope (90 deg or ±75deg) in Fig. 5 are given as follows:

Eq. (6)


Eq. (7)


Eq. (8)

Line averaging is applied to the pixel at location (i,j) if the condition min(d1,d2,d3)<Th is satisfied, using Th=20. In other locations, where min(d1,d2,d3)>Th, it is considered as a nonvertical edge and slope-based interpolation is applied.

Slope-based interpolation sometimes destroys very thin lines or edges. If a very thin edge separates two uniform regions with similar intensity values, few pixels from these thin edges are subjected to distortion since there is a chance that the difference among pixels in those two uniform regions is smaller than that along a thin edge. In such cases, slope-based interpolation selects pixels from those two uniform regions. To avoid such failure, if at least two differences among Sright, Sleft, and Smid given in Eq. (3) appear to be smaller than the threshold, it is considered as a thin edge and line averaging is applied. Hence, pixels at vertical or thin edges are interpolated using line averaging. Slope-based interpolation is applied to the remainder of the regions.

Pixels that are not detected as vertical or thin edge pixels are interpolated along both the left to right (forward interpolation) and right to left (backward interpolation) directions to calculate the forward and backward interpolated images, ILR and IRL, respectively. The proposed method fails to track the slope when edges abruptly change in direction. ILR and IRL are required for the removal of unwanted artifacts. The decision to use the right to left or left to right interpolation is based on the following differences:

Eq. (9)


Eq. (10)

where ILA is the image interpolated using line averaging. On the basis of DLR and DRL, interpolated image I is obtained using interpolated values in ILR that correspond to small differences in DLR compared to DRL and vice versa.

The above method results in an image that provides good results along edges and other detailed regions; however, for some cases, the above method results in the production of unwanted artifacts in the form of a single or pair of pixels in some regions. For removal of such remaining artifacts, a 1×3pixel window is moved across I at every interpolated location, (i,j), and all three pixel intensities, I(i,j1), I(i,j), and I(i,j+1), are compared with ILA(i,j). To remove the uncertainty, an intensity that is closer to ILA(i,j) is used to the replace the intensity value of I at location (i,j) to obtain the final interpolated image.


Performance Evaluation

The performance of the proposed algorithm is evaluated by applying ELA, GGD, LCIM, MLSM, and the proposed algorithm to 14 test images which is shown in Fig. 6. We performed both subjective and objective tests to quantitatively compare the quality of the images created with different methods and the related computational costs. MATLAB 2015a was used for collecting all results, and the tic and toc functions of MATLAB were used to calculate execution time. The optimization levels of all implemented conventional methods were the same.

Fig. 6

Selected test images for evaluations.


Figure 6 shows test images selected for evaluation since they represent varieties of patterns. The set of images in Fig. 6 contains grayscale images, but the proposed algorithm can also be applied to color images by either treating each red, green, and blue channel of an RGB image individually or by calculating the slopes for one channel and using the same slopes for the other two channels to reduce execution time.

For comparison of interpolation algorithms, subjective evaluation is very important, because the efficiency of an interpolation algorithm can be analyzed by observing edges and other details. Figures 711 show some cropped regions of test images subjected to deinterlacing. The ELA, LCIM, and MLSM methods failed to restore edges distorted due to downscaling of the original images, thereby producing jagged edges. ELA and LCIM failed to restore most of the smooth edge patterns, since they were designed to be best for vertical and diagonal edges. However, GGD recovered many cases of smooth edges because it used gradient prediction. GGD showed a similar performance to the proposed method, preserving edges in the presence of minor jagging as can be seen in Figs. 711. The proposed algorithm efficiently restores any edges, including thin lines, compared to other algorithms. For all cases, the proposed algorithm more efficiently restored details and edges compared to all other algorithms.

Fig. 7

Cropped regions after deinterlacing: (a) original, (b) edge-based line average (ELA), (c) gradient-guided deinterlacing (GGD), (d) LCIM, (e) moving least-squares method (MLSM), and (f) the proposed method.


Fig. 8

Cropped regions after deinterlacing: (a) original, (b) ELA, (c) GGD, (d) LCIM, (e) MLSM, and (f) the proposed method.


Fig. 9

Cropped regions after deinterlacing: (a) original, (b) ELA, (c) GGD, (d) LCIM, (e) MLSM, and (f) the proposed method.


Fig. 10

Cropped regions after deinterlacing: (a) original, (b) ELA, (c) GGD, (d) LCIM, (e) MLSM, and (f) the proposed method.


Fig. 11

Cropped regions after deinterlacing: (a) original, (b) ELA, (c) GGD, (d) LCIM, (e) MLSM, and (f) the proposed method.


A video sequence of a fast-moving roller coaster was also used for performance evaluation. Figure 12(a) shows a cropped region of an interlaced frame which includes disparities in two different fields. The ELA, GGD, LCIM, and MLSM methods failed to restore some thin or gentle edge patterns, while the proposed algorithm recovered many cases of edges, but produced a few artifacts as well.

Fig. 12

Cropped regions after deinterlacing: (a) original interlaced frame, (b) ELA, (c) GGD, (d) LCIM, (e) MLSM, and (f) the proposed method.


Although an interpolation algorithm can be analyzed mainly by using subjective evaluation, the peak signal to noise ratio (PSNR), calculated as in Eq. (11), is also used for objective comparisons with other methods.

Eq. (11)

where MSE is the mean square error.

Table 1 shows the average PSNR for 14 test images when deinterlaced using ELA, GGD, LCIM, MLSM, and the proposed method. The results show that proposed method provides the highest PSNR in all cases. An image deinterlaced using the proposed method provides a PSNR that is higher than that of the existing methods: more than 0.6 dB higher than ELA, more than 1 dB higher than LCIM, more than 0.4 dB higher than GGD, and more than 3.4 dB higher than MLSM. ELA, like other simple averaging methods, provides a high PSNR even though it fails in recovering details and edges.

Table 1

Comparison of the PSNR (dB) for different images.

Horse toy33.4733.6733.3731.1134.09

Table 2 shows a comparison of the execution times for all six algorithms applied to 14 test images. The execution time of ELA is the best among all algorithms since it requires few comparators and additions. ELA is almost 2 times faster than that of the proposed algorithm. The execution time for the proposed algorithm is almost 13 times faster than LCIM, which is the second most time-efficient method. GGD and MLSM are very complex compared to the proposed algorithm.

Table 2

Comparison of complexity by elapsed CPU time (s).

Horse toy0.0172.2380.5511.3520.036

Figure 13 shows performance comparisons for 60 frames of the roller coaster video when deinterlaced using ELA, GGD, LCIM, MLSD, and the proposed method. The results show that the proposed method provides the highest PSNR for all frames as shown in Fig. 13(a). For a few frames, the PSNR of GGD is close to that of the proposed algorithm; however, for most cases, the PSNR of proposed method is far better than all other algorithms. Elapsed CPU time comparison is also shown in Fig. 13(b). The execution time of the proposed algorithm is close to ELA, but far better than that of the other algorithms.

Fig. 13

Comparison for a video sequence: (a) PSNR and (b) elapsed CPU time.


The reason the proposed algorithm is so simple is because it is based only on additions and comparisons. The proposed method using EST requires just two lines of memory, 18 additions, no multiplications, and nine comparators.



In this paper, an efficient edge-based deinterlacing method is proposed. A technique called EST that predicts the present slope on the basis of the information of previous slopes is introduced and used for deinterlacing. The proposed deinterlacing offers high performance at very low complexity. Moreover, to improve the accuracy of EST-based deinterlacing, a slope resetting criteria, the application of two-way EST-based deinterlacing, and compensation for thin lines are also applied. Simulation results showed that restorations of edges were clearer in the proposed algorithm compared to most state-of-the-art conventional algorithms, whereas simple deinterlacing of an image without calculation of coefficients or the need for large correlation masks, unlike other conventional algorithms, demonstrates the superiority of the proposed algorithm on the basis of low complexity.



F. Yao and S. Li, “Overview of scan format conversion for digital video,” in Int. Conf. Artificial Intelligence, Management Science and Electronic Commerce, 4123 –4126 (2011). Google Scholar


J. F. Stromeyer and S. Klein, “Spatial frequency channels in human vision as asymmetric (edge) mechanisms,” Vision Res., 14 (12), 1409 –1420 (1974). VISRAM 0042-6989 Google Scholar


T. Doyle, “Interlaced to sequential conversion for EDTV applications,” in 2nd Int. Workshop Signal Proc. HDTV, 412 –430 (1998). Google Scholar


T. Chen, H. R. Wu and Z. H. Yu, “Efficient deinterlacing algorithm using edge-based line average interpolation,” Opt. Eng., 39 (8), 2101 –2105 (2000). Google Scholar


P. Y. Chen and Y. H. Lai, “A low-complexity interpolation method for deinterlacing,” IEICE Trans. Inf. Syst., E90-D (2), 606 –608 (2007). ITISEF 0916-8532 Google Scholar


M. K. Kim and J. C. Jeong, “An efficient deinterlacing algorithm using the new edge-directed interpolation,” J. Korean Soc. Broadcast Eng., 12 (2), 185 –192 (2007). Google Scholar


S. H. Keller, F. Lauze and M. Nielsen, “Deinterlacing using variational methods,” IEEE Trans. Image Process., 17 (11), 2015 –2028 (2008). IIPRE4 1057-7149 Google Scholar


S. Jin, W. Kim and J. Jeong, “Fine directional de-interlacing algorithm using modified Sobel operation,” IEEE Trans. Consum. Electron., 54 (2), 857 –862 (2008). ITCEDA 0098-3063 Google Scholar


D. H. Lee, “A new edge-based intra-field interpolation method for deinterlacing using locally adaptive-thresholded binary image,” IEEE Trans. Consum. Electron., 54 (1), 110 –115 (2008). ITCEDA 0098-3063 Google Scholar


S. Yang, D. Kim and J. Jeong, “Fine edge-preserving deinterlacing algorithm for progressive display,” IEEE Trans. Consum. Electron., 55 (3), 1654 –1662 (2009). ITCEDA 0098-3063 Google Scholar


X. Chen, G. Jeon and J. Jeong, “Filter switching interpolation method for deinterlacing,” Opt. Eng., 51 107402 (2012). Google Scholar


B. Jin, J. G. Kuk and N. I. Cho, “A gradient guided deinterlacing algorithm,” in Int. Conf. Image Processing, 853 –856 (2012). Google Scholar


D. H. Lee, “A simple, high performance edge-adaptive deinterlacing algorithm with very low complexity,” in IEEE Int. Conf. Consumer Electronics, 636 –637 (2012). Google Scholar


J. Wang, G. Jeon and J. Jeong, “Efficient adaptive deinterlacing algorithm with awareness of closeness and similarity,” Opt. Eng., 51 (1), 017003 (2012). Google Scholar


J. Wang, G. Jeon and J. Jeong, “Moving least-square method for interlaced to progressive scanning format conversion,” IEEE Trans. Circuits Syst. Video Technol., 23 (11), 1865 –1872 (2013). ITCTEM 1051-8215 Google Scholar


T. Fukinuki, “Television: past, present, and future,” Proc. IEEE, 86 (5), 998 –1004 (1998). Google Scholar


Sajid Khan received his BS degree in telecom engineering from FAST University Peshawar campus in 2011. He is currently pursuing his PhD in the Department of Electronics and Communication Engineering at the Hanyang University ERICA Campus. His current research interests include image interpolation, edge detection, biomedical image processing, and image denoising.

Dongho Lee received his MS and PhD degrees in electrical and computer engineering from the University of Texas at Austin in 1988 and 1991, respectively. From June 1991 to February 1994, he worked as a senior engineer at LG Electronics involving the development and implementation of DTV systems. Since 1994, he has been a professor in the Department of Electronics and Communication Engineering at the Hanyang University ERICA campus with research interests including digital image processing and pattern recognition.

© The Authors. Published by SPIE under a Creative Commons Attribution 3.0 Unported License. Distribution or reproduction of this work in whole or in part requires full attribution of the original publication, including its DOI.
Sajid Khan and Dongho Lee "Efficient deinterlacing method using simple edge slope tracing," Optical Engineering 54(10), 103108 (20 October 2015).
Published: 20 October 2015

Cited by 7 scholarly publications.

Back to Top