11 April 2012 Filter design and its application for scanning format conversion
Author Affiliations +
Optical Engineering, 51(4), 040504 (2012). doi:10.1117/1.OE.51.4.040504
Abstract
This letter presents the issue of interpolating missing line components at the interlaced signals, a procedure called deinterlacing. A filter design method is introduced in detail, utilizing a least-squares algorithm with training set for the requested deinterlacing filter. A thorough research of deinterlacing performance and system complexity is executed. The proposed filter design and its application on deinterlacing is compared with other conventional filter-based deinterlacing methods in terms of quality measures. It was concluded to show outstanding performance and speed trade-off among the methods compared.
Jeon and Lee: Filter design and its application for scanning format conversion

1.

Introduction

Interlaced video frame consists of two sub fields taken in sequence, each sequentially scanned at odd and even lines of the image sensor. Analog television employed this technique because it allowed for less transmission bandwidth and further eliminated the perceived flicker that a similar frame rate would give using progressive scan. The cathode-ray tube (CRT), based displays were able to display interlaced video correctly due to its complete analog nature. All of the newer displays are inherently digital, in that the display comprises discrete pixels. Therefore, the two fields need to be combined into a single frame, which leads to various visual defects, which the deinterlacing process should try to minimize. Deinterlacing has been researched for decades and employs complex processing algorithms. However, consistent results have been very hard to achieve.1 There are various deinterlacing methods with different levels of quality and complexities, which are: (1) basic fixed methods such as the line average and field average; (2) adaptive methods that select one of the basic methods according to the motion information extracted from the image sequence; and (3) methods that utilize the motion estimation and compensation. In this letter, we focus on intra-field deinterlacing method, which belongs to category (1) and gives good performance with low complexity.

Most edge-based deinterlacing methods utilize the uniform weighted sum of two-tap filter [TTF: hTTF=1/2 (Ref. 2)] to estimate the current pixel to be interpolated in the determined edge direction.3 The line average (LA) method4 is commonly used in the software approach, which adopts a single field to reconstruct a progressive frame in 90 deg edge direction. However, the frequency response of two-tap average filter looks like a bell shape as shown in Fig. 1(a). It is obviously known that LA shows high peak signal-to-noise ratio (PSNR) performance. However, it provides apparent jaggedness at edge area.

Fig. 1

Perspective view of frequency responses of filters for deinterlacing. (a) hTTF; (b) hSTF; (c) hLSFS obtained by image#1; (d) hLSFE obtained by image #2 to 24 for deinterlacing image #1; (e) hLSFA obtained by image #1 to 24; and (f) hLSFS obtained by image #2.

OE_51_4_040504_f001.png

Meanwhile, the sinc function is known as an ideal filter, and its frequency response is rectangular-shape. By the sinc function, we can design the filter to have a more rectangular shaped frequency response than the TTF, so interlaced signals can be rebuilt more precisely. In Refs. 3 and 4, the authors adopted one of the sinc interpolation filters, which is a one-dimensional six-tap filter (STF:hSTF=1/128[3177878173]), and coefficients of STF are determined by approximating the sinc function. This is same to the one in the video codec, such as MPEG-4, H0.264/AVC, and high efficiency video coding (HEVC), to decrease residual errors.5 However, this method only regards the similarity of sinc function, and consciousness of the closeness or spatial locality is not taken into account.

In this letter, we proposed filter design algorithm, which minimizes the mean-squared deinterlacing error over a training set (TS). In Sec. 2, we propose filter design algorithm in detail. The simulation results are shown in Sec. 3 and the conclusions are made in Sec. 4.

2.

Proposed Filter Design

Least mean squares method is a class of adaptive filter utilized to simulate a desired filter by obtaining the filter coefficients that relate to presenting the least mean squares of the error signal, e.g., difference between the desired and the real signal. A general approach is introduced in Refs. 67.8. Let us assume xO[i,j] is original image, that we reconstruct by filtering interlaced image xI[i,j] with the linear, shift-invariant filter having unit-sample response hTS:x^O=xI*hTS, where hTS is desired filter obtained by TS. If we suppose the remainder between x^O and xO can be designed as a stationary random field, then we may select hTS=argminhE[(xO[i,j](xI*h)[i,j])2]. Because a good random field model is hard to be modeled, we can minimize the substantial error on TS of representative images. Let us suppose that we have TS of original images. For every image in this TS, we can create (width×height)/2 sized interlaced image xI from the width×height sized desired image xO. Assume we segment the TS into S sub-images, where k’th sub-image is specified on the partial block P(κ). Assume that the desired filter hTS is a two-dimensional (2-D) finite impulse response filter with area of support QΛ, where rectangular lattice Λ=Z2. Then the desired filter can be acquired as solution to

(1)

hTS=argminhκ=1S(i,j)P(κ){xO(κ)[i,j](m,n)Qh[m,n]xI(κ)[im,jn]}2.

We assume QN=card(Q) and PN=card[P(κ)] be the number of filter coefficients to be decided and the number of samples in the sub-images. We create an QN×1 column vector h from the filter coefficients by examining the area Q in some fixed command. Correspondingly, we create an PN×1 column vector xO(κ) from xO(κ)[i,j] by examining the pixels of P(κ) in a fixed manner. Eventually, we create an PN×QN matrix M(κ) from the components of xI(κ) as each column of M(κ) matches an element (m,n)Q examined in the same way as used to create h; this column is obtained by scanning the elements of xI(κ)[im,jn] for (i,j)P(κ) in the identical manner exploited to create xO(κ). Finally, Eq. (1) can be described in matrix form as

(2)

hTS=argminhκ=1SM(κ)hxO(κ)2.
Equation (2) is a standard least-squares (LS) issue with solution9

(3)

hTS={κ=1S[M(κ)]TM(κ)}1{κ=1S[M(κ)]TxO(κ)}.

Figure 1 shows the perspective view of frequency response of the (a) hTTF; (b) hSTF; (c) hLSFS (LS filter obtained by image #1); (d) hLSFE (LS filter obtained by other 23 images to deinterlace a image); (e) hLSFA (LS filter obtained by whole 24 images); and (f) hLSFS (LS filter obtained by image #2). In this letter, 11×11 filters were designed.

3.

Experimental Results

The proposed method under different filter condition was tested on the 24 Kodak images.10 We denote MTTF3, MSTF,4 MLSFS, MLSFE, and MLSFA as the method that employed hTTF, hSTF, hLSFS, hLSFE, and hLSFA, respectively.

Table 1 shows the PSNR results of 24 Kodak images. The MLSFS gave the highest PSNR (however, this is infeasible method), and MLSFE and MLSFA gave the same result. This implies that the proposed method is not sensitive to TS. In Fig. 2, reconstructed results of the image #5 are shown. It can be noticed that the proposed method with various filters present less artifacts with respect to the other filter based methods.

Table 1

PSNR (DB) results of different filter-based methods for various kodak images.

Kodak imagesMTTF3MSTF4MLSFSMLSFEMLSFA
124.0021.6527.0326.9226.94
231.7729.3834.8434.7434.74
331.4629.0535.9334.7834.80
431.7928.9335.9835.7235.71
523.9321.2628.3128.0928.10
624.8722.7127.7927.5427.55
729.6026.3035.3435.0235.02
823.2221.0126.6326.2526.26
929.4226.6234.0733.9033.90
1030.2127.8335.1133.7733.77
1127.0524.7430.0530.0330.03
1231.3028.8234.5034.4334.43
1321.7519.7424.4724.4124.41
1426.4623.8830.0329.9829.98
1531.7329.0535.5235.4135.40
1628.3626.2330.9630.7230.72
1730.2427.5534.0833.9433.94
1826.0923.7729.4829.4129.41
1925.6123.1229.1429.1029.10
2029.4526.7933.4833.3033.30
2125.6223.2328.9628.8928.89
2229.2726.8332.5232.4632.46
2332.0029.1336.9436.5236.52
2425.0823.0028.0127.9127.91
Avg.27.9325.4431.6331.3931.39

Fig. 2

(a) Original Kodak image;10 Deinterlaced image #5 using: (b) hTTF; (c) hSTF; (d) hLSFS obtained by image #5; (e) hLSFE obtained by image #1 to 4 and #6 to 24 for deinterlacing image #5; (f) hLSFA obtained by image #1 to 24; and (g) hLSFS obtained by image #6.

OE_51_4_040504_f002.png

Table 2 shows PSNR performance of the proposed MLSFE and other conventional deinterlacing algorithm systems from the literature, they are LCID,11 FDD,2 EMD,12 FEPD,13 MCAD,14 CASA,15 and DCAD.16 At first observation, it is noticed that our proposed method outperforms all other methods over the entire images in terms of PSNR.

Table 2

PSNR (DB) results of conventional deinterlacing methods for various kodak images.

imageLCID11FDD2EMD12FEPD13MCAD14CASA15DCAD16MLSFE
126.8126.8926.7126.6626.6026.8226.7626.92
234.7534.6834.3634.2734.5334.7634.7634.74
334.6534.4534.4334.5835.1234.6334.6034.78
435.6535.6635.2635.0735.3035.7235.8335.72
528.2727.9727.7127.4427.6928.2728.2728.09
627.5527.5127.4427.5027.4527.5327.4827.54
735.1334.6034.4534.2035.0135.1635.3035.02
826.1226.2425.7425.0826.0726.1826.2026.25
933.7733.6433.3133.1133.6633.8133.9333.90
1033.3833.4333.1633.1434.2733.3333.0333.77
1130.0729.9929.7929.7330.0030.0630.0530.03
1234.4534.4034.1834.0234.2834.4734.4434.43
1324.3424.2624.1924.3624.0724.3024.1924.41
1430.0929.8829.7429.7129.6930.0930.1229.98
1535.3135.2934.8934.7034.9435.3735.4735.41
1630.8230.7530.7230.8430.7530.7930.6730.72
1734.0133.7733.4833.3633.8834.0634.1933.94
1829.2329.2129.0029.0728.9129.2229.1229.41
1929.0829.0728.8228.5528.9729.0928.4629.10
2033.4133.1332.8632.6532.2033.4833.6133.30
2128.8628.8028.6728.7328.6328.8528.8528.89
2232.3332.3431.9931.7432.2032.3732.4332.46
2336.7136.3036.0735.8237.1836.7837.1936.52
2427.6027.5827.4327.4727.2527.5927.4927.91
avg.31.3531.2431.0230.9131.1931.3631.3531.39

4.

Conclusion

The proposed filter based deinterlacing has shown the lowest reconstruction error among published filter-based techniques on the reference Kodak dataset. This letter has demonstrated that the feasible hLSFE filter is sufficient to achieve the full benefits of the technique, improving over the MTTF method by 3.46 dB. Moreover, the proposed hLSFE filter is superior to CASA by 0.21 dB, which is the best edge-based method in literature.

Acknowledgments

This work was supported in part by the National Science Foundation of China (NSFC) under Grant 61001100, 61077009, and the Provincial Science Foundation of Shaanxi, China, under Grant 2010K06-15.

References

1. 

K. Jack, “Video demystified—a handbook for the digital engineer,” Elsevier, Eagle Rock, VA (2005).Google Scholar

2. 

S. JinW. KimJ. Jeong, “Fine directional de-interlacing algorithm using modified sobel operation,” IEEE Trans. Cons. Elect. 54(2), 857–862 (May. 2008).ITCEDA0098-3063http://dx.doi.org/10.1109/TCE.2008.4560171Google Scholar

3. 

E. B. BellarsG. D. Haan, “Deinterlacing: a key technology for scan rate conversion,” Elsevier, Amsterdam (2000).Google Scholar

4. 

S. M. HongS.-J. ParkJ. Jeong, “Deinterlacing algorithm using fixed directional interpolation filter and adaptive distance weighting scheme,” Opt. Eng. 50(6), 067008 (June 2011).OPEGAR0091-3286http://dx.doi.org/10.1117/1.3584843Google Scholar

5. 

A. Fuldsethet al., “Low complexity directional interpolation filter,” ITU-T SG16/Q.6 Doc. VCEG-AI12, pp. 16–18 (2008).Google Scholar

6. 

T. Kondoet al., “Picture conversion apparatus picture conversion method learning apparatus and learning method,” U.S. Patent 6 323 905 (Nov. 2001).Google Scholar

7. 

X. LiM. T. Orchard, “New edge-directed interpolation,” IEEE Trans. Image Process. 10(10), 1521–1527 (Oct. 2001).IIPRE41057-7149Google Scholar

8. 

M. Zhao, “Video enhancement using content-adaptive least mean square filters.,” PhD Thesis, Technische Universiteit Eindhoven (2006).Google Scholar

9. 

S. Haykin, “Adaptive filter theory.,” Prentice Hall, (2002).Google Scholar

10. 

11. 

P. Y. ChenY. H. Lai, “A low-complexity interpolation method for deinterlacing,” IEICE Trans. Inf. Syst. E90-D(2), 606–608 (2007).ITISEF0916-8532http://dx.doi.org/10.1093/ietisy/e90-d.2.606Google Scholar

12. 

K. KangG. JeonJ. Jeong, “A single field interlaced to progressive format conversion using edge map in the image block,” in IASTED Signal and Image Processing (SIP) 2009, pp. 80–85 (2009).Google Scholar

13. 

S. YangD. KimJ. Jeong, “Fine edge-preserving deinterlacing algorithm for progressive display,” IEEE Trans. Cons. Elect. 55(3), 1654–1662 (Aug. 2009).ITCEDA0098-3063http://dx.doi.org/10.1109/TCE.2009.5278039Google Scholar

14. 

S. J. ParkG. JeonJ. Jeong, “Covariance-based adaptive deinterlacing method using edge map,” in International Conference on Image Processing Theory Tools and Applications (IPTA) 2010, pp. 166–171 (2010).Google Scholar

15. 

S. J. ParkG. JeonJ. Jeong, “Computation-aware algorithm selection approach for interlaced-to-progressive conversion,” Opt. Eng. 49(5), 057005 (2010).OPEGAR0091-3286http://dx.doi.org/10.1117/1.3431711Google Scholar

16. 

S. J. ParkS. M. HongJ. Jeong, “Deinterlacing algorithm using direction-oriented inverse-free wiener filtering,” Opt. Eng. 50(6), 067014 (2011).OPEGAR0091-3286http://dx.doi.org/10.1117/1.3593162Google Scholar

Gwanggil Jeon, Jong-Kyu Lee, "Filter design and its application for scanning format conversion," Optical Engineering 51(4), 040504 (11 April 2012). http://dx.doi.org/10.1117/1.OE.51.4.040504
Submission: Received ; Accepted
JOURNAL ARTICLE
4 PAGES


SHARE
KEYWORDS
Image filtering

Optical filters

Digital filtering

Electronic filtering

Sinc filters

Video

Video coding

RELATED CONTENT

A-new-mixed-noise-filtering-method-for-laser-image
Proceedings of SPIE (November 28 2011)
Video-signal-processing-using-vector-median
Proceedings of SPIE (September 01 1990)
Recursive-wavelet-filters-for-video-coding
Proceedings of SPIE (July 31 2006)

Back to Top