A motion and edge adaptive interlaced-to-progressive conversion using fuzzy logic-based systems

A motion and edge adaptive interlaced-to-progressive conversion using fuzzy logic-based systems P. Brox Instituto de Microelectr´onica de Sevilla (CSIC) and University of Seville (Spain) bro[email protected] I. Baturone Instituto de Microelectr´onica de Sevilla (CSIC) and University of Seville (Spain) [email protected] S. S´anchez-Solano Instituto de Microelectr´onica de Sevilla (CSIC) Seville (Spain) san[email protected] Abstract This paper presents an algorithm for video de-interlacing. The approach uses three fuzzy logic-based systems to adapt the interpolation strategy to the presence of motion and edges. Furthermore, the algorithm is able to deal with any kind of TV material independently of the source used to acquire the scene. Extensive simulations of standard and real sequences prove the efficiency of the proposed algorithm. Keywords: Video de-interlacing, fuzzy logic-based system, motion adaptive, edge adaptive. 1 Introduction Interlacing was introduced by the TV community since it provides an effective reduction of the video bandwidth. It reduces the bandwidth at half since only the even or odd lines that compose a frame are alternatively transmitted. Interlacing is currently used by all the analog TV standards (PAL, NTSC and SECAM) and also, by some of the more modern digital transmissions [1]. Recently, there is an increasing need of a progressive scanning format at the receiver side of TV signal. Many devices such as modern displays (LCDs, Plasma), DVDs, and projectors, work with progressive material and incorporate an embedded chip that implement a deinterlacing algorithm. It consists of converting interlaced video into a progressive form by interpolating the non-transmitted lines. Several features of the picture like the presence of motion and edges could complicate this task. Many de-interlacing algorithms have been proposed in the literature during the last years [2]. Basically, they can be classified into two categories: motion (MC) and nonmotion compensated (non-MC) algorithms. MC techniques look for a motion vector in each pixel or block of pixels of the image and achieve the best results in moving areas. However, the computational cost involved in the calculation of the most appropriate motion vector is quite high. An alternative among non-MC algorithms are the motion adaptive de-interlacing techniques [3]-[6]. As its name indicates, this kind of algorithms estimates the level of motion in the image and adapt the interpolation strategy according to it. If there is no motion or the level of motion is barely appreciable then the temporal neighbors are suitable to perform the interpolation. On the contrary, when the level of motion is high a spatial interpolator is chosen to interpolate the new pixel. The efficiency of motion adaptive algorithms relies on the quality of the motion detector. Primitive approaches use the difference between pixels with the same spatial coordinates from two consecutive frames to measure motion, and a crisp transition between the temporal and spatial interpolator [3]. However, they are far to achieve good results in tricky parts of the image, which contain high contrast detailed areas, high level of motion, L. Magdalena, M. Ojeda-Aciego, J.L. Verdegay (eds): Proceedings of IPMU’08, pp. 1175–1182 Torremolinos (M´alaga), June 22–27, 2008 noise and/or a high number of edges. To improve the robustness of the motion detector several proposals have been presented in the literature during the last years [2], [4]. Some authors combine the output of several motion detectors [2], whereas others apply filtering techniques to field difference signal [4]. Other authors improve the performance of motion adaptive de-interlacing algorithms [4]- [6]. In [4], the crisp transition between the temporal and spatial interpolator is substituted by a soft transition. In this sense, several options are proven in [4] such as a linear or a step piecewise transition. Other alternative is to use fuzzy logic and to apply different heuristic rules with approximate levels or uncertainty, which implicitly perform a nonlinear filtering [5]-[6]. This paper describes a new motion adaptive de-interlacing as result of a work developed during the last years. The combination of the spatial and temporal interpolator is carried out by a fuzzy system (F S1), whose input is a bi-dimensional convolution of field difference signal. Furthermore, the spatial and temporal interpolators are also calculated by two fuzzy systems: a second fuzzy system (F S2) provides the temporal interpolator, which is capable of dealing with any kind of video material, and a third fuzzy system (F S3) is able to adapt the spatial interpolation to edges. a1 a2 a b c c1 c2 FS3 motion IS dissimilarity FS2 output FS1 IT Figure 1: Block diagram of the proposed algorithm. 2 Description of the algorithm Figure 1 shows a descriptive diagram of the implemented algorithm. The following subsections describe the three fuzzy systems used in the proposed algorithm. 2.1 Fuzzy system to combine the interpolators with the presence of motion (F S1) Since current TV standards work with video coding algorithms where luminance component contains more information than chrominance components [1], our study is only developed for this unique component. However, its extension to color images is simple and direct by applying the final interpolation expression to the color components. Our proposal uses as input value the bidimensional convolution of field difference signals that can be mathematically expressed as follows: motion =ΣCj,iHi,j ΣCj,i = =(1 2 1) (H1,1H1,2H1,3)T 4(1) where Cj,i are the values of the weights and Hi,j are described by the following differences of luminance values (see Figure 2(a)): H1,1=|B0−B|(2) H1,2=|X0−X|(3) H1,3=|E0−E|(4) Different weights and sizes of matrix Hhave been studied to achieve a good trade-off between the computing resources and the quality of motion measurement [7]-[8]. As can be seen in expression (1), the selected convolution only includes neighbors in vertical direction since a wide number of video sequence simulations shown a non-decisive influence of horizontal neighbors to measure the level of motion. Unlike the proposals in [5]-[6], which use four fields, our algorithm reduces the temporal aperture up to three fields as shown Figure 1176 Proceedings of IPMU’08 B0 X0 E0 X B E Xn (t-1) Interpolated line Transmitted line (t) Sequence order (t+1) (a) 3rd motion is M X=λIT+δIS 2nd motion is L X=IS 1st motion is S X=IT If antecedent consequent 1 0 S (small)M (medium)L (large) µmotion motion (b) (c) Current pixel Figure 2: (a) Pixels involved in the calculation of the bi-dimensional convolution. (b) Rulebase of the F S1. (c) Membership functions used in F S1. 2(a). The interpolated values calculated in the previous field (B0, E0) are necessary to evaluate the motion value in expression (1). The spatial interpolator (IS) is employed to calculate the first progressive frame. The influence of motion in selecting the kind of interpolation is evaluated by considering three rules that are linguistically expressed as follows: 1. If motion in the current pixel is small (S), the most adequate interpolated value is obtained by applying a temporal interpolation (IT). 2. If motion in the current pixel is large (L), the best result is obtained by performing a spatial interpolation (IS). 3. If motion in the current pixel is medium (M), then the value is better calculated by applying a linear combination of the temporal and spatial interpolators (λIT+ δIS). This rulebase is summarized in the Table of Figure 2(b). The fuzzy concepts small, large and medium used in the rules are modeled according to the membership functions shown in Figure 2(c). Using the Fuzzy Mean as defuzzification method the new pixel value is calculated as follows: X=α1IT+α2IS+α3(λIT+δIS) (5) where αiis the corresponding activation degree of each rule in the Table of Figure 2(b). Three degrees of motion (small, medium and large) are considered in this fuzzy system. After analyzing up to five degrees of motion [9], the rulebase with three rules has been selected since it provides the most attractive solution in terms of hardware resources and quality of the interpolated image. 2.2 Fuzzy logic-based system for the temporal interpolation (F S2) In order to understand the strategy implemented in F S2to obtain the temporal interpolator, it is necessary to review the origin of material. If the sequence was recorded by a video camera at a picture rate of 50 Hz (PAL) or 60 Hz (NTSC), the three fields of the aperture are different in moving areas of the image (different numbers in Figure 3(a)). However, if the material was registered with a cine-camera the picture rate is 24 Hz and a conversion of film material is necessary to display it on TV. The conversion to adapt both picture rates basically consists of repeating the fields twice (to achieve 50 Hz), or twice and three times alternatively (to achieve 60 Hz) as it is shown in Figure 3(b). This process is known as pull-down 2:2 and pull-down 3:2, respectively. Since the temporal aperture of this approach would be composed from film material (for instance 2-even, 2-odd, 3-odd), two of the fields in the aperture has to come from the same original frame. The detection of these cases is very interesting due to two reasons. Firstly, the risen presence of film and hybrid material Proceedings of IPMU’08 1177 123 Source: Telecine 24 Hz 112233 50 Hz 50 Hz 123456 Source: Video camera (a) (b) Interlaced material even odd even odd even odd Interlaced material even odd even odd even odd Figure 3: (a) Video sequence. (b) Sequence of film material. 1 0 S (small)L (large) μdissimilarity dissimilarity (a) (b) B0 E0 X B E (t-1) (t) Sequence order X0 2nd dissimilarity is L IT = Xn 1st dissimilarity is S IT = X0 If antecedent then consequent Figure 4: (a) Rulebase of the F S2. (b) Membership functions used in F S2. on TV and secondly, a perfect de-interlacing can be achieved by copying this information from the repeated field in the aperture at a expense of a minimal cost (if the repeated field is correctly detected in the aperture). A simple fuzzy system is proposed that is able to deal with film material. It selects the most adequate temporal interpolation depending on dissimilarity signal between two consecutive fields, given by the following expression: dissimilarity =|B−B0|+|E−E0| 2(6) The heuristic knowledge of this fuzzy system is expressed by means of the following linguistic rules: 1. If dissimilarity between the fields (t-1) and (t) is small (S), the most adequate interpolated value is obtained by selecting the pixel value in the previous field at the same spatial position (X0)(see Figure 4(a)). 2. On the contrary, if dissimilarity is large (L), the pixel value in the previous field is not a good choice and is better to bet on the pixel in the next field (Xn)(see Figure 4(a)). Table in Figure 4(a) summarizes the rulebase of this second fuzzy system. The shape of membership functions to model the fuzzy concepts small and large are shown in Figure 4(b). The output of this fuzzy system is given by the following expression: IT=β1X0+β2Xn(7) where βiis the activation of each rule in the Table of Figure 4(a). 2.3 Fuzzy logic-based system for the spatial interpolation (F S3) F S3performs a smart interpolation among pixels in the spatial neighborhood. The heuristic knowledge developed in the fuzzy rulebase adapts the interpolation strategy according to the presence of edges in the picture. To detect edges the following differences 1178 Proceedings of IPMU’08 XC1 BC A1 F1 A D1DEF (t) Sequence order (a) 5th a1is VL and a is VL and b is L IS=(C1+D1)/2 and c is Land c1is S 3rd a is VS and b is L and c is VS IS=(A+F+C+D)/4 2nd a is L and b is L and c is S IS=(C+D)/2 6th otherwise IS=(B+E)/2 4th a1is S and a is L and b is L IS=(A1+F1)/2 and c is VL and c1is VL 1st a is S and b is L and c is L IS=(A+F)/2 If antecedent then consequent 1 0 VS (very small) VL (very large) μa a (b) (c) a=|A-F| a1=|A1-F1| b=|B-E| c=|C-D| c1=|C1-D1| SL Figure 5: (a) Pixels involved in the spatial interpolator. (b) Rulebase of the F S3. (c) Membership functions used in F S3. abc a1c1 26.5º 45º 135º 153.43º Figure 6: Directions evaluated by the F S3. of pixel values along five directions are calculated (see Figure 5(a) and Figure 6): a1=|A1−F1|(8) a=|A−F|(9) b=|B−E|(10) c=|C−D|(11) c1=|C1−D1|(12) The following knowledge is employed to estimate the edge adaptive interpolation: 1. If there is a small (S) difference in direction a, and if band care large (L), then an edge could be in direction aand the best solution is to apply the average between the two pixels that defines adirection. 2. If there is a small (S) difference in direction c, and if band aare large (L), then an edge could be in direction cand the best solution is to apply the average between the two pixels that defines cdirection. 3. If there is a very small (VS) difference in directions aand c, and a large (L) difference in direction b, neither there is an edge nor vertical linear interpolation performs well; the best option is a linear interpolation between the neighbors with small differences: A, C, D, F. 4. An edge is clear in direction a1not only if a1is small (S), but also if aand bare large (L) and cand c1are very large (VL). Then the spatial interpolation is calculated by applying the average between the two pixels that defines a1direction. 5. An edge is clear in direction c1not only if c1is small (S), but also if band care large (L) and aand a1are very large (VL). Then the spatial interpolation is calculated by applying the average between the two pixels that defines c1direction. 6. Otherwise, a vertical linear interpolation would be the most adequate. Table of the Figure 5(b) summarizes the ruleProceedings of IPMU’08 1179 Table 1: Average PSNR values (in dBs) using video sequences. SEQUENCE Missa Paris Trevor Salesman News Mother Carphone FORMAT CIF CIF CIF CIF QCIF QCIF QCIF Line Doubling 36.44 23.61 31.05 29.75 25.18 31.81 28.25 Line Average 40.47 26.67 35.04 33.53 29.25 35.94 32.61 ELA 3+3 39.49 25.53 34.11 32.11 26.63 35.39 32.65 ELA 5+5 38.56 24.64 33.31 30.17 25.92 34.2 31.51 Field Insertion 38.36 29.86 34.36 36.17 33.13 36.14 30.34 VT 2fields 40.25 30.73 36.61 36.54 35.46 39.61 34.08 VT 3fields 40.52 31.37 37.16 36.95 35.67 40.89 34.54 Technique in [5] 40.01 33.12 35.38 37.62 34.73 39.49 32.27 Technique in [6] 40.18 35.28 36.69 38.29 37.51 41.87 34.78 Proposal 40.81 35.87 37.63 38.35 38.78 42.11 35.09 base of this second fuzzy system. From the analysis of these rules, we can see that a higher number of antecedents are used in the rules that evaluate a1and c1directions, since a reinforcement is necessary to avoid the detection of false edges when the system works with 5+5 pixels in the neighborhood. The shape of membership functions to model the fuzzy concepts small, large, very small and very large are shown in Figure 5(c). The output of this fuzzy system is obtained by applying the Fuzzy Mean as follows: IS=χ1(A+F 2) + χ2(C+D 2)+ +χ3(A+C+D+F 4) + χ4(A1+F1 2)+ +χ5(C1+D1 2) + χ6(B+E 2) (13) where χiis the activation of each rule in the Table of Figure 5(b). 3 Simulation results The performance of the proposed algorithm has been analyzed by de-interlacing several video sequences. They can be divided into two categories: a first group of standard video sequences and a second one of real film sequences. The video sequences considered have widely been used as benchmarks in video processing applications. After obtaining the interlaced video data from these progressive sequences by eliminating lines, several de-interlacing algorithms have been applied. The Peak Signal to Noise Ratio (PSNR) is used as figure of merit, to evaluate the quality between the obtained interpolated frames and the original ones. The proposed algorithm has been also compared with other de-interlacing algorithms with less or similar computational cost: four spatial method such as line doubling, line average, and conventional ELA (edgeadaptive interpolation algorithm [2]) using 3+3 and 5+5 taps; the simplest temporal de-interlacing algorithm called field insertion, and two vertico-temporal filtering with two and three fields [2]; and, finally the fuzzy motion adaptive algorithms reported in [5] and [6]. Table 1 shows the average PSNR values obtained when de-interlacing fifty fields of seven video sequences. The PSNR results show that the proposed algorithm performs better than the other algorithms since it achieves the highest values. Moreover, its computational complexity is quite low since the three fuzzy systems are very simple. The algorithm has also been tested to deinterlace the real film sequences shown in Table 2. These results prove the advantages of the inclusion of the second fuzzy system (F S2). Finally, the superior performance of our approach can be corroborated by the visual in1180 Proceedings of IPMU’08 Table 2: Average PSNR values (in dBs) using film sequences. SEQUENCE Fire Rose Chop Hunt Fargo Repair Fargo Tokyo FORMAT PAL TV PAL TV PAL TV PAL TV PAL TV Line Doubling 34.51 39.97 30.48 28.79 27.22 Line Average 38.76 44.61 35.92 34.31 31.46 ELA 3+3 35.55 44.07 35.28 33.66 30.02 ELA 5+5 33.61 43.16 34.33 32.16 28.53 Field Insertion 36.41 24.06 31.23 33.07 36.49 VT 2fields 40.32 44.18 35.87 40.99 36.84 VT 3fields 41.16 46.08 38.43 38.91 35.13 Technique in [5] 39.36 43.71 36.64 40.11 34.88 Technique in [6] 41.14 42.64 37.33 42.54 37.71 Proposal 42.11 48.81 41.63 42.81 37.75 spection of the de-interlaced frames from the Carphone sequence shown in Figure 7. 4 Conclusions The algorithm presented herein is the result of the application of fuzzy logic-based systems to video processing. Especially this approach tackles the problem of de-interlacing, which is currently more demanded in consumer devices. The algorithm overcomes the performance of other well-known de-interlacing algorithms by adapting the interpolation strategy to the presence of motion and edges. To achieve it, the approach includes three fuzzy systems: one is used to combine a spatial and a temporal interpolator according to the level of motion, and the other two provide a smart temporal and spatial interpolator. Acknowledgements This work has been supported in part by the Spanish MEC Projects TEC2005-04359 and DPI2005-02293, and by the Projects TIC2006-635 and TEP2006-375 from the Andalusian regional Government. References [1] J. Whitaker. Television transmissions systems, chapter book of ’Standard handbook of video and television engineering’. McGraw-Hill Editorial, Blacklick OH (USA), 2002. [2] G. de Haan. De-interlacing, chapter book of ’Digital Video. Post Processing’, pages 185-201, University Press Eindhoven, Sep. 2006. [3] A. M. Bock. Motion-adaptive standards conversion between formats of similar field rates. Signal Processing: Image Communication, vol.6, no.3, pages 275280, 1994. [4] H. Jiang, D. Huu and E. Tinyork. Motion adaptive deinterlacing. United States Patent (US 6,459,455), Oct. 2002. [5] D. Van de Ville, R. Van de Wall, W. Philips and I. Lemahieu. Motion adaptive de-interlacing using fuzzy logic. Proc. International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU), pages 1989-1996, Jul. 2002. [6] J. Guti´errez-R´ıos, F. Fern´andezHern´andez, J. C. Crespo and G. Trevi˜no. Motion adaptive fuzzy video de-interlacing method based on convolution techniques. In Proceedings of the conference IPMU’2004, pages 1635-1642, Perugia, Italy, Jul. 2004. [7] P. Brox I. Baturone S. S´anchez-Solano J. Guti´errez-R´ıos and F. Fern´andezHern´andez. A fuzzy edge-dependent motion adaptive algorithm for deinterlacing. Fuzzy Sets and Systems, vol.158, no.3, pages 337-347, Feb.2007. Proceedings of IPMU’08 1181 LINE DOUBLING LINE AVERAGE ELA 3+3 ELA 5+5 FIELD INSERTION VERTICO TEMPORAL 2 FIELDS VERTICO TEMPORAL 3 FIELDS TECHNIQUE IN [7] VAN DE VILLE ET AL. [6] PROPOSED ALGORITHM Figure 7: De-interlaced frames of Carphone sequence. [8] P. Brox I. Baturone and S. S´anchezSolano. A fuzzy motion adaptive algorithm for interlaced-to-progressive conversion. In Proceedings of the Conference IPMU’2006, Par´ıs, France, Jul. 2006. [9] P. Brox I. Baturone and S. S´anchezSolano. Fuzzy motion adaptive algorithm for video de-interlacing. In Proceedings of the Conference KES’2006, Bournemouth, United Kingdom, Oct. 2006. 1182 Proceedings of IPMU’08