2.1.

Registration Using the Advanced STFS

2.1.1.

Conventional STFS

Prior to describing the advanced STFS, we explain the conventional STFS (Ref. 17) in detail as follows. As illustrated in Fig. 2(a), three consecutive fields, i.e., $f_{n-1},f_n,f_{n+1}$, are involved in the estimation of the motion trajectory. The bidirectional ME and the two kinds of unidirectional ME, i.e., forward and backward ME, are combined in order to fully exploit the information from the three fields.

Fig. 2

Conventional spatial-temporal correlation-assisted search (STFS) scheme.

Let ${\mathrm{SAD}}_P$ and ${\mathrm{SAD}}_N$ be the sum of absolute differences (SAD) between two blocks used in the backward ME and forward ME, respectively, and let ${\mathrm{SAD}}_B$ be the SAD between two blocks used in the bidirectional ME, where these terms are defined as follows:

Eq. (1)

$$\begin{gathered} {\mathrm{SAD}}_B(\mathbf{q})=\sum _{(x,y)\in \mathbf{b}}|f_{n+1}(x+m,y+n)-f_{n-1}(x-m,y-n)| \\ {\mathrm{SAD}}_N(\mathbf{q})=\sum _{(x,y)\in \mathbf{b}}|f_n(x,y)-f_{n+1}(x+m,y+n)| \\ {\mathrm{SAD}}_P(\mathbf{q})=\sum _{(x,y)\in \mathbf{b}}|f_n(x,y)-f_{n-1}(x-m,y-n)|, \end{gathered}$$

where ($x,y$) denotes a position in the current block $\mathbf{b}$, and $\mathbf{q}\equiv (m,n)$ indicates a candidate MV within the given search range. The best MV $\widehat{\mathbf{q}}=(\widehat{m},\widehat{n})$ for the block $\mathbf{b}$ is then obtained by minimizing the following cost:

Eq. (2)

$$\widehat{\mathbf{q}}=\underset{\mathbf{q}}{\arg \min }[\mathrm{SAD}(\mathbf{q})],$$

where

Eq. (3)

$$\mathrm{SAD}(\mathbf{q})={\mathrm{SAD}}_B(\mathbf{q})+{\mathrm{SAD}}_N(\mathbf{q})+{\mathrm{SAD}}_P(\mathbf{q}).$$

Note that the information from the three consecutive fields is involved in the estimation of the motion trajectory. From Fig. 2(a), $\widehat{\mathbf{q}}$ is chosen as the initial MV candidate ${\overrightarrow{\mathbf{v}}}_{\mathrm{ini}}$. For each matching block, there are four spatial MV candidates and five temporal MV candidates, as in Fig. 2(b). The spatial/temporal bidirectional MV candidates are sorted according to the number of occurrences. For the current block, the matching error corresponding to each spatial/temporal MV candidate ${\overrightarrow{\mathbf{v}}}_{\mathrm{ST}}$ is compared to the matching error of the initial MV candidate ${\overrightarrow{\mathbf{v}}}_{\mathrm{ini}}$ according to Eq. (4). The comparison is performed starting from the candidate with the maximum number of occurrences.

Eq. (4)

$$|\mathrm{SAD}({\overrightarrow{\mathbf{v}}}_{\mathrm{ST}})-\mathrm{SAD}({\overrightarrow{\mathbf{v}}}_{\mathrm{ini}})|<T_1,$$

where $T_1$ is a predetermined threshold that is a function of $\mathrm{SAD}({\overrightarrow{\mathbf{v}}}_{\mathrm{ini}})$. If Eq. (4) is satisfied, ${\overrightarrow{\mathbf{v}}}_{\mathrm{ST}}$ is chosen as the final MV. Otherwise, the candidate with the second largest number of occurrences is compared to the initial candidate, and so on. If all the spatial/temporal MV candidates fail to pass the matching error check, ${\overrightarrow{\mathbf{v}}}_{\mathrm{ini}}$ is chosen as the final MV.

2.1.2.

Advanced STFS

In order to obtain more accurate and denser MVs than the conventional STFS, we apply the overlapped motion compensation scheme to the STFS. Note that MV estimation is performed on an $8\times 8$ block basis, but the matching block size is $16\times 16$. As shown in Fig. 3, the best MV for a specific $8\times 8$ block is obtained by block matching for the extended $16\times 16$ block with the $8\times 8$ block as a center. The conventional STFS is used for this block matching. Finally, the estimated MV for the extended $16\times 16$ block is allocated to the $8\times 8$ center of the matching block. Table 1 shows the superiority of the advanced STFS to the conventional STFS in terms of PSNR. For this experiment, we employed the same progressive common intermediate format (CIF) sequences as in Sec. 3 and produced their interlaced versions in the same fashion as described in Sec. 3. For each method, we computed the PSNR between the motion-compensated frame and the original frame. We compared the averaged PSNR for the first 300 frames of each sequence as an objective evaluation measure. For example, Table 1 shows that the advanced STFS outperforms the conventional STFS by 0.8 dB at maximum for the container sequence. This is because the advanced STFS can produce more accurate and denser MVs than the conventional STFS. Thus, we applied this advanced STFS for registration of the proposed temporal deinterlacing, which is described in the following subsection.

Fig. 3

The overlapped matching of the advanced STFS.

Table 1

Peak signal-to-noise ratio (PSNR) comparison between conventional spatial-temporal correlation-assisted search (STFS) and the advanced STFS (dB).

Name	Conventional STFS	Advanced STFS
Foreman	37.69	38.02
Mobile	28.77	28.68
M & D	47.37	47.47
Stefan	31.07	31.23
Coastguard	38.25	38.32
Table tennis	35.62	36.01
Container	46.59	47.42
Average	37.91	38.16

2.2.

MAP Estimator-Based Temporal Deinterlacing

The key point of the proposed algorithm is to reconstruct even registration errors in temporal deinterlacing by employing a MAP estimator, whereas previous temporal deinterlacing methods output motion-compensated pixels only. In order to formulate the MAP estimation problem for temporal deinterlacing, we should define the acquisition model of an interlaced field. First, we assume that a progressive frame $F$ may have a motion model $M$ with adjacent frames. Next, a space-invariant point spread function (PSF) $H$ is applied to $F$ for antialiasing. Finally, an interlaced field $f$ is generated by applying an interlace decimation operator $D$ and adding a noise component $V$. Note that the decimation operator $D$ alternatively subsamples even lines and odd lines, and the decimation operation is defined as follows:

According to Eq. (5), the $n$’th field $f_n$ is derived from the $n$’th frame $F_n$. The current field and its neighbor fields are then defined as

Let the processing block size be $b\times b$ and the scaling ratio be set to $r:1$. Then, $F$ in Eq. (6) has a dimension of [$r^2{b}^2\times 1$], which is arranged in lexicographic order. The [$r^2{b}^2\times r^2{b}^2$] matrix $M_n$ is the geometric motion operator between the original progressive frame $F$ and the $n$’th interlaced field $f_n$ of size [$b^2\times 1$]. The PSF is modeled by the [$r^2{b}^2\times r^2{b}^2$] matrix $H$. The [$b^2\times r^2{b}^2$] matrix $D_n$ represents the decimation operator and the [$b^2\times 1$] matrix $V_n$ denotes the system noise. Based on this model, we propose the MAP estimator-based temporal deinterlacing algorithm.

In general, a MAP estimator for the original progressive frame $F$ given the observed interlaced fields $f_n$ can be formulated to find the MAP estimate $\widehat{F}$ via the following $L_p$ minimization:

In addition, we compare BTV-based regularization of Eq. (8) with a typical TV-based regularization²³ to show the superiority of the BTV-based regularization quantitatively and qualitatively. Table 2 compares BTV-based regularization and TV-based regularization in terms of PSNR. The PSNR value in Table 2 is the average PSNR for the first 50 deinterlaced frames per sequence. We can see that BTV-based regularization provides at maximum 1.1 dB and on average 0.4 dB higher PSNRs than TV-based regularization. For example, Fig. 4 shows the deinterlacing results for carphone and foreman sequences. Note that the TV-based regularization causes some artifacts for flat areas due to its sensitivity to noise. On the other hand, the proposed BTV-based regularization seldom shows such a phenomenon because it is inherently robust against noise and preserves the details such as edges and textures better than TV-based regularization. As a result, we can achieve high-quality temporal deinterlacing via this robust regularized MAP estimator.

Table 2

PSNR comparison between total variation (TV) regularization and bilateral total variation (BTV) regularization (dB).

Fig. 4

The deinterlaced frames according to regularization term.

We use the steepest descent algorithm to find the solution to Eq. (7). We can thus obtain an optimal solution in the following iterative manner. That is, the ($t+1$)’th MAP estimate ${\widehat{F}}_{t+1}$ is derived from the $t$’the estimate ${\widehat{F}}_t$.

2.3.

Mode Decision

Conventional spatiotemporal deinterlacing methods often suffer from feathering, blur, and jagging artifacts caused by false mode decision. For instance, feathering artifacts occur near object boundaries due to occlusion or inaccurate MVs. Mode decision, hence, significantly affects the visual quality of spatiotemporal deinterlacing algorithms. Fan and Chung employed the so-called slope detector (SD)-based feathering artifact detector due to its low complexity and high detection ability.¹⁷

This paper presents a stronger mode decision method that additionally takes into account mean of absolute differences (MAD) values, MV correlation, and MAD correlation. Figure 5 illustrates the proposed mode decision scheme where the MV reliability is examined on a block basis in two steps. Assume that the MVs are produced by the advanced STFS. First, for each block that is motion-compensated by the advanced STFS, feathering artifacts are detected by the aforementioned SD-based detector of Ref. 17. If a feathering artifact is not detected, temporal deinterlacing is applied to the block. Otherwise, additional examination is performed with more information. The reason why we chose such a conservative approach is that the blur phenomenon caused by spatial deinterlacing is visually less annoying than feathering artifacts. The second examination procedure is explained in greater detail below.

Fig. 5

The proposed mode decision scheme.

Since the SD-based detector depends on the motion-compensated image only, it may cause false positives in detecting various feathering artifacts. We hence propose an additional step to reduce the false positive rate of the first step by taking into account MAD values, MV correlation, and MAD correlation. As shown in Fig. 5, if the MAD of the current block is sufficiently small, i.e., $\mathrm{MAD}(\widehat{\mathbf{v}})<{\delta }_1$, and the MAD and MV of the current block are highly correlated with those of its neighbors, i.e., $\mathrm{cor}(\mathrm{MV})<{\delta }_2\&\mathrm{cor}(\mathrm{MAD})<{\delta }_3$, we determine that the current block has a reliable MV. Let $\mathrm{cor}(\mathrm{MV})$ be the $L_1$-norm distance between the current MV and the component-wise median of MVs of its eight-connected blocks, while $\mathrm{cor}(\mathrm{MAD})$ indicates the $L_1$-norm distance between $\mathrm{MAD}(\widehat{\mathbf{v}})$ and the average MAD for the eight-connected neighbor blocks. In this paper, ${\delta }_1$, ${\delta }_2$, and ${\delta }_3$ are empirically set to 20, 5, and 5, respectively. Therefore, since this second decision step further examines the MV reliability independently of the motion-compensated image, it can effectively prevent the entire mode decision from being trapped in false positives.

2.4.

Spatial Deinterlacing

For spatial deinterlacing of the proposed algorithm, we adopted a block-based directional interpolation algorithm proposed by Chen and Tai in Ref. 14. This subsection briefly introduces Chen’s algorithm. Figure 6 shows a deinterlaced frame, where the dotted line indicates the missing scan line that needs to be interpolated and the solid lines indicate the original field data. It is assumed that the missing pixel $f_n(x,y)$ is centered in a target block BC; ${\mathrm{BU}}_{\mathbf{q}}$ and ${\mathrm{BL}}_{\mathbf{q}}$ are defined as the corresponding upper and lower referenced blocks, respectively, and $\mathbf{q}$ is assumed to be a candidate directional vector between the BC and its upper candidate block. Note that the blocks BC, ${\mathrm{BU}}_{\mathbf{q}}$, and ${\mathrm{BL}}_{\mathbf{q}}$ only contain pixels in $f_n$. The best directional vector $\widehat{\mathbf{q}}$ is detected using the following equation:

Fig. 6

Edge-based spatial deinterlacing.

3.1.

Experimental Condition

First, for an objective quality evaluation, we used 12 progressive CIF sequences; foreman, mobile, mother and daughter (M&D), Stefan, coastguard, table tennis, container, flower garden, football, highway, Paris, and tempete. We generated the interlaced fields by applying a simple low-pass filter of {1, 2, 1} to those progressive frames and alternatively subsampling the low-pass filtered frames. After deinterlacing, we computed the PSNR between the reconstructed progressive frame and the original frame. Note that only Y components are treated here. We chose the averaged PSNR for the first 300 frames of each sequence as an objective evaluation measure.

We compared the proposed algorithm with LA, ELA, Lee’s algorithm,⁹ Chang’s algorithm,¹³ Chen’s algorithm,¹⁴ Fan’s algorithm,¹⁷ Yang’s algorithm,¹⁸ Mohammadi’s algorithm,²¹ and Trocan’s algorithm.²² The number of reference fields for the proposed temporal deinterlacing was set to 3, i.e., the current field and its temporally previous and next fields.

The search range for registration in the proposed algorithm and Chang’s algorithm was $\pm 32$ both horizontally and vertically. All the block sizes for matching in the advanced STFS were set to $16\times 16$ and the block sizes of overlapping are set to $8\times 8$. In Eq. (8), $\alpha$ and $\tau$ are fixed to 0.5 and 2, respectively. Figure 7 shows the influence of a parameter $\alpha$ on the overall performance of the proposed algorithm for four test sequences, i.e., highway, carphone, foreman, and football. For this experiment, when deinterlacing the first field of each sequence, we progressively changed $\alpha$ from 0.1 to 1.0 and tracked the PSNR values accordingly. From Fig. 7, we can observe that as $\alpha$ becomes larger than 0.5, the PSNR starts to decrease. So, we set $\alpha$ to 0.5. Through a similar experiment, we found that another parameter $\tau$ rarely affects the overall performance of the proposed algorithm. So, we fixed $\tau$ to an acceptable value. Table 3 shows the appropriate values of the other parameters, i.e., $\beta$ and $\lambda$ chosen for each sequence to maximize the temporal deinterlacing performance in terms of PSNR. Note that $\beta$ and $\lambda$ should be determined on a shot basis in a sequence. For instance, since the foreman and table tennis sequences consist of two different shots, we derived and applied two different parameters to those sequences, as given in Table 3.

Fig. 7

Peak signal-to-noise ratio (PSNR) performance according to $\alpha$ for four video sequences.

Table 3

Parameter setting for temporal deinterlacing.

Figure 8 shows the effects of the parameters in Eq. (7) on the overall performance of the proposed temporal deinterlacing. This experiment was performed for a field in the first shot of the foreman sequence. From Fig. 8(a), we can observe that if the optimal parameters are used, the PSNR performance is very stable. On the contrary, Fig. 8(b) shows that if nonoptimal parameters, i.e., the parameters of the second shot, are employed, the PSNR performance drastically decreases as the iterations go on, and the peak PSNR also becomes low in comparison with that in Fig. 8(a). From Fig. 8, we can also find that the termination point of iteration is important. Thus, we selected the optimal number of iterations for each sequence, as given in Table 3.

Fig. 8

PSNR values according to the number of iterations for the first shot of the foreman sequence. (a) Results with the optimal parameters. (b) Results with nonoptimal parameters.

3.2.

Performance Evaluation

Table 4 shows the PSNR results of several algorithms for 12 test sequences. For this experiment, we implemented LA, ELA, Chang’s algorithm,¹³ and Mohammadi’s algorithm²¹ personally and verified them. We can see that the proposed algorithm provides $~5\mathrm{dB}$ higher PSNR than Chang’s¹³ and Mohammadi’s algorithms²¹ on average. Especially, for container sequence, the proposed algorithm goes beyond Chang’s algorithm¹³ up to 12 dB.

Table 4

PSNR comparison for different deinterlacing algorithms (dB).

In addition, Table 5 provides PSNR comparison results for several recent methods in the literature. In Table 5, the numerical values of Refs. 9, 14, 17, 18, and 22 were directly extracted from those papers. Hence, a few values are not available in the table. Note that the proposed algorithm provides on average 0.8 dB higher PSNR than the cutting-edge algorithm, i.e., Fan’s algorithm.¹⁷ For the Stefan sequence, in particular, we achieve a significant PSNR improvement of $~2\mathrm{dB}$ over Fan’s algorithm. We also find from the available PSNR values in Table 5 that the proposed algorithm is superior to Trocan’s algorithm.²² As a result, the proposed algorithm outperforms the previous works in terms of objective visual quality of PSNR. In addition, Fig. 9 shows the PSNR values according to the frame number. We can state that the proposed algorithm consistently provides higher PSNR values than the previous works.

Table 5

PSNR comparison for different deinterlacing algorithms in the literature (dB).

Fig. 9

PSNR performance according to the frame number. (a) Foreman. (b) Mobile. (c) Container.

In Figs. 10 and 11, the deinterlaced results for mobile and Stefan sequences are compared. Note that the proposed algorithm produces a deinterlaced result close to its original frame, while Chang’s algorithm and LA suffer from visually annoying artifacts, such as jagging and blur. For the mobile sequence (see Fig. 10), we find that the proposed algorithm outperforms the others. Especially observing the numbers in the calendar, the proposed algorithm shows almost the same visual quality as the original frame. From Fig. 11, we can find a perfect court line generated by the proposed temporal deinterlacing. Note that the competitors show severe jagging artifacts and line-crawling in the near horizontal edges.

Fig. 10

The deinterlaced frames for the mobile sequence. (a) Original. (b) Line averaging (LA). (c) Chang’s method.¹³ (d) Proposed method.

Fig. 11

The deinterlaced frames for the Stefan sequence. (a) Original. (b) LA. (c) Chang’s method.¹³ (d) Proposed method.

In addition, Figs. 12 and 13 show the deinterlaced results for real interlaced video sequences. We adopted two well-known interlaced sequences ($720\times 480i$), car and table tennis. Even for real interlaced video sequences, the proposed algorithm still provides outstanding visual quality without any artifacts in comparison with the existing methods. For example, LA and Chang’s algorithm show jagging and feathering artifacts [see Figs. 12(b) and 12(c)], but the proposed algorithm does not cause such artifacts, as shown in Fig. 12(d).

Fig. 12

The results for a cropped region of the car sequence. (a) Input interlaced frame. (b) LA. (c) Chang’s method.¹³ (d) Proposed method.

Fig. 13

The results for a cropped region of the table tennis sequence. (a) Input interlaced frame. (b) LA. (c) Chang’s method.¹³ (d) Proposed method.

In addition, we measured the execution times of several algorithms. This experiment was executed on a quad-core CPU at 2.66 GHz with 3 GB DDR2 DRAM. Since motion estimation occupies most of the complexity of MC-based deinterlacing algorithm, we adopted a fast full search²⁵ and a famous fast search algorithm, i.e., enhanced predictive zonal search (EPZS)²⁶ for fast motion estimation in this experiment. Table 6 compares the proposed algorithm with LA, ELA, and Ref. 13 in terms of the CPU running time. Note that each numerical value indicates the average for the first 10 fields of foreman sequence, and all the algorithms were implemented in MATLAB®. We could find that in comparison with fast full search, the EPZS cuts the CPU running time of the proposed algorithm in half with an acceptable PSNR drop of $~1\mathrm{dB}$ on average. The proposed algorithm using EZPS still provides $~1.8$ times longer execution time than Ref. 13. However, if we employ several optimization skills additionally, we can significantly reduce the computational cost of the proposed algorithm.

Table 6

CPU running times for various algorithms (s).