1.

Introduction

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.^1–15 In general, TV broadcasters choose interlaced scanning as the main standard for video formats.¹⁶ 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),³ 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)⁴ and low-complexity deinterlacing⁵ effectively increase the accuracy of edge direction determination. In addition, fine directional deinterlacing⁸ and edge-preserving directional deinterlacing¹⁰ are suggested to solve difficult interpolation problems in a low-sloped edge domain involving video quality degradation. Binary patterns,⁹ gradient-guided deinterlacing (GGD),¹² deinterlacing with closeness and similarity¹⁴ and the moving least-squares method (MLSM)¹⁵ 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.

2.

Conventional Methods

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

Low-complexity interpolation method (LCIM)⁵ 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.

MLSM¹⁵ is based on a coefficient calculation using matrix multiplication operations as follows:

3.

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.

3.1.

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 $k_{\mathrm{cur}}$ of the current pixel is calculated on the basis of the left, right, and middle slopes calculated using slope $k_{\mathrm{prev}}$ (the slope of the adjacent pixel). A value of $k_{\mathrm{prev}}=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 ($S_{\mathrm{mid}}$), left ($S_{\mathrm{left}}$), and right ($S_{\mathrm{right}}$) intensity differences that are used in calculating $k_{\mathrm{cur}}$ are given as follows:

Eq. (3)

$$\{\begin{array}{l}{S}_{\mathrm{mid}}=|I(i-1,j+k_{\mathrm{prev}})-I(i+1,j-k_{\mathrm{prev}})|,\\ S_{\mathrm{left}}=|I(i-1,j+k_{\mathrm{prev}}-1)-I(i+1,j-k_{\mathrm{prev}}+1)|,\\ S_{\mathrm{right}}=|I(i-1,j+k_{\mathrm{prev}}+1)-I(i+1,j-k_{\mathrm{prev}}-1)|.\end{array}$$

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

Eq. (4)

$$\{\begin{array}{ll}{k}_{\mathrm{cur}}=k_{\mathrm{prev}}-1,& \text{if}\min (S_{\mathrm{left}},S_{\mathrm{mid}},S_{\mathrm{right}})=S_{\mathrm{left}}\\ k_{\mathrm{cur}}=k_{\mathrm{prev}}+1,& \text{if}\min (S_{\mathrm{left}},S_{\mathrm{mid}},S_{\mathrm{right}})=S_{\mathrm{right}}\\ k_{\mathrm{cur}}=k_{\mathrm{prev}},& \text{else}\end{array}.$$

To avoid the production of unwanted artifacts in case a wrong value exists for the reference to previous slope $k_{\mathrm{prev}}$, a resetting criterion is used in which the value of the reference to the previous slope is reset to zero if the condition ($|S_{\min }^{(i,j)}-S_{\min }^{(i,j-1)}|>T$ and $|k_{\mathrm{cur}}|>1$) is satisfied. A large value of $|S_{\min }^{(i,j)}-S_{\min }^{(i,j-1)}|$ 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 $\text{previous slope}=0$. (d), (e), and (f) are middle, left, and right slopes using a $\text{previous slope}=1$.

3.2.

Slope-Based Interpolation

On the basis of slope $k_{\mathrm{cur}}$ calculated using EST, the pixel intensity at location $(i,j)$ can be interpolated using

Eq. (5)

$$I(i,j)=\frac{I(i-1,j+k_{\mathrm{cur}})+I(i+1,j-k_{\mathrm{cur}})}{2}.$$

Figure 3 shows different examples of the calculation of the interpolated pixel at location $(i,j)$ using different values of $k_{\mathrm{cur}}$. 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.

3.3.

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 $\pm 75$ or 90 deg slope: (a) $d_1$, (b) $d_2$, and (c) $d_3$.

The differences for deciding a vertical slope (90 deg or $\pm 75\mathrm{deg}$) in Fig. 5 are given as follows:

Eq. (6)

$$d_1=|I(i-1,j-1)-I(i+1,j-1)|+|I(i-2,j)-I(i+1,j)|+|I(i-1,j+1)-I(i+1,j+1)|,$$

Eq. (7)

$$d_2=|I(i-1,j-1)-I(i+1,j)|+|I(i-1,j)-I(i+1,j+1)|,$$

Eq. (8)

$$d_3=|I(i-1,j)-I(i+1,j-1)|+|I(i-1,j+1)-I(i+1,j)|.$$

Line averaging is applied to the pixel at location $(i,j)$ if the condition $\min (d_1,d_2,d_3)<\mathrm{Th}$ is satisfied, using $\mathrm{Th}=20$. In other locations, where $\min (d_1,d_2,d_3)>\mathrm{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 $S_{\mathrm{right}}$, $S_{\mathrm{left}}$, and $S_{\mathrm{mid}}$ 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, $I^{\mathrm{LR}}$ and $I^{\mathrm{RL}}$, respectively. The proposed method fails to track the slope when edges abruptly change in direction. $I^{\mathrm{LR}}$ and $I^{\mathrm{RL}}$ 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)

$$D^{\mathrm{LR}}=|I^{\mathrm{LR}}-I^{\mathrm{LA}}|,$$

Eq. (10)

$$D^{\mathrm{RL}}=|I^{\mathrm{RL}}-I^{\mathrm{LA}}|,$$

where $I^{\mathrm{LA}}$ is the image interpolated using line averaging. On the basis of $D^{\mathrm{LR}}$ and $D^{\mathrm{RL}}$, interpolated image $I$ is obtained using interpolated values in $I^{\mathrm{LR}}$ that correspond to small differences in $D^{\mathrm{LR}}$ compared to $D^{\mathrm{RL}}$ 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\times 3\text{pixel}$ window is moved across $I$ at every interpolated location, $(i,j)$, and all three pixel intensities, $I(i,j-1)$, $I(i,j)$, and $I(i,j+1)$, are compared with $I^{\mathrm{LA}}(i,j)$. To remove the uncertainty, an intensity that is closer to $I^{\mathrm{LA}}(i,j)$ is used to the replace the intensity value of $I$ at location $(i,j)$ to obtain the final interpolated image.

4.

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 7–11 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. 7–11. 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.

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.

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).

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.

5.

Conclusion

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.