US 7,095,445 B2Grant

Method of detecting motion in an interlaced video sequence based on logical operation on linearly scaled motion information and motion detection apparatus

Issue Date:2006-08-22

•25 Claims

•9 Drawing Sheets

Abstract

A motion decision value provides a dependable estimate whether motion occurs in a given region of a video image in an interlaced video sequence. The motion detection is particularly applicable in the conversion from interlaced video to progressive video. An input first is fed to an absolute value former which computes a frame difference signal from a difference between the first field and the second field in one frame. A point-wise motion detection in the frame difference signal is then followed by a region-wise motion detection that combines the point-wise motion detection signal with an adjacent point-wise motion detection signal delayed by one field. The motion decision value is then computed from the region-wise motion detection signal and output for further processing in the video signal processing system, such as for choosing whether the spatially interpolated video signal value or the temporally interpolated video signal value should be used for the output.

Metadata

Assignee

Samsung Electronics Co., Ltd.

Inventors

Yeong-Taeg Kim
Shin-Haeng Kim

Application Information

Application Number:US 10/001,676

Filing Date:2001-10-23

Priority Date:2000-12-20

Art Unit:2622

Classifications

IPC:

H04N5/14H04N7/01H04N9/64H04N11/20

Patent Drawings (9 sheets)

Description

Cross-References to Related Applications

[0001] Applicants claim the benefit of U.S. Provisional Application No. 60/257,338 entitled “Methods of Detecting Motion in an Interlaced Video Sequence Based on Logical Operation on the Linearly Scaled Motion Information and the Apparatus Therefor,” filed Dec. 20, 2000, U.S. Provisional Application No. 60/257,365 entitled “Methods of Detecting Motion in an Interlaced Video Sequence Utilizing Region-Wise Motion and Apparatus” filed Dec. 20, 2000, and U.S. Provisional Application No. 60/273,100 entitled “Method of Detecting Repetitive Motion In An Interlaced Video Sequence and Apparatus Therefore,” filed Mar. 2, 2001, which applications are incorporated herein by reference.

Background of the Invention

[0002] 1. Field of the Invention

[0003] The present invention lies in the signal processing field. More specifically, the present invention pertains to a method of detecting motion in an interlaced video sequence. The invention is particularly applicable to the conversion of an interlaced video signal to a progressive frame video signal, whereby regional motion information is utilized to define whether or not the video sequence contains motion or represents still image information. The present invention also pertains to an apparatus for performing the claimed method.

[0004] 2. Description of the Related Art

[0005] In the development of current digital TV (DTV) systems, it is essential to employ a video format conversion unit because of the variety of the video formats adopted in many different DTV standards worldwide. For instance, the ATSC DTV standard system of the North America adopted 1080x1920 interlaced video, 720x1280 progressive video, 720x480 interlaced and progressive video, and so on, as its standard video formats for digital TV broadcasting. Video format conversion refers to a signal processing operation in which an incoming video format is converted to a specified output video format so that the output video can be properly displayed on a displaying device such as a monitor, FLCD, or a Plasma display, which has a fixed resolution.

[0006] Video format conversion systems are of significant importance since the conversion can directly affect the visual quality of the video of a DTV receiver. Fundamentally, the video format conversion operation requires advanced algorithms for multi-rate system design, poly-phase filter design, and interlaced-to-progressive scanning rate conversion or simply deinterlacing. Deinterlacing represents an operation that doubles the vertical scanning rate of the interlaced video signal.

[0007] Interlaced video in general is a sequence of separately arriving fields, such as A1, A2, A3, etc., where A1, A2, and A3 are interlaced images with Al being a top image, A2 being a bottom image, A3 being the next top image, and so on. The most popular systems currently in use, namely NTSC, PAL, and SECAM are two-field systems, where two consecutive fields (such as the top field Al and the bottom field A2) make up a frame. Each scanned field contains, i.e., updates, every other line of a corresponding frame and the number of lines in the frame is twice the number of lines in each of the fields which contain video information. Typically, the first field is identified with odd-numbered lines and the second field is identified with even-numbered lines. The fields are scanned onto the display screen one after the other at a defined frequency.

[0008] By way of example, NTSC scans close to 30 frames (60 fields of interlaced video) per second, with 525 lines per frame, and a horizontal to vertical aspect ratio of 4:3. The frame difference, therefore, is the difference between two fields having the same types (top or bottom) such as A1 and A3, or A2 and A4. PAL and SECAM scan 25 frames per second, with 625 lines per image, and the same aspect ratio of 4:3. As noted, the interlacing in all of these systems is 2:1, i.e., two fields per one frame. The primary reason for the interlacing of the lines between the fields is to reduce flicker in the display. An image that is updated, say, only 30 times a second would allow the human eye to perceive the scanning, because the image information would already start to fade before the next image is scanned onto the screen. When two fields are used, and each contains half of the information, the scanning rate in effect is raised to 60 Hz, and the human eye no longer perceives any flicker.

[0009] Deinterlacing refers to the filling of unavailable lines in each of the fields A1, A2, A3, and so on. As a result of deinterlacing, a 60 Hz field sequence (of interlaced video fields) becomes a 60 Hz progressive sequence.

[0010] Interlaced video is subject to several intrinsic drawbacks, referred to as artifacts. These include serrated lines that are observed when there is motion between fields, line flickering, raster line visibility, and field flickering. These also apply to DTV (digital TV) receivers. Historically, deinterlacing algorithms have been developed to enhance the video quality of NTSC TV receivers by reducing these intrinsic annoying artifacts of the interlaced video signal. Besides, elaborate deinterlacing algorithms utilizing motion detection or motion compensation provide excellent methods of doubling the vertical scanning rate of the interlaced video signal especially for stationary (motionless) objects in the video signal.

[0011] The present invention therefore also relates to the motion detection based deinterlacing operation that can be used for analog and digital TV receivers.

[0012] The state of the art includes a variety of deinterlacing algorithms, each having been exploited and studied comprehensively by many researchers during the last decade. Deinterlacing algorithms can be categorized into two classes, namely, 2-D (spatial) deinterlacing algorithms and 3-D (spatio-temporal) deinterlacing algorithms depending on the use of motion information embedded in consecutive interlaced video sequence. Combined spatial and temporal 3-D deinterlacing algorithms based on a motion detection give more pleasing performance than 2-D deinterlacing algorithms. The key point of a 3-D deinterlacing algorithm is how to precisely detect motion in the interlaced video signals. The publications in the following list disclose some of the applicable deinterlacing methods. They may be categorized as follows:

- [0013] [1] Simple line doubling scheme, vertical filtering, vertical edge controlled interpolation method disclosed in the IEEE Transactions on Consumers Electronics, pp. 279–89, August 1989 by D. I. Hentschei;
- [0014] [2] Edge direction dependent deinterlacing method disclosed in the Proc. of the Int. Workshop on HDTV, 1994, by D. Bagni, R Lancini, and S. Tubaro;
- [0015] [3] Nonlinear interpolation methods based on:
- [0016] a weighted median filter disclosed in the Proc. of the IEEE ISCAS, pp. 433–36, Portland, USA, May 1989, by J. Juhola, A. Nieminen, J. Sal, and Y. Neuvo,
- [0017] FIR median hybrid interpolation disclosed in Pro. Of SPIE's Visual Communications and Image Processing, Lausanne, Switzerland, October 1990, 00. 125–32 by A. Lehtonen and M. Renfors,
- [0018] a complementary median filter disclosed in Proc. of the Int. Workshop on HDTV, 1994 by H. Blume, I. Schwoerer, and K. Zygis,
- [0019] [4] A motion adaptive method disclosed in IEEE Transactions on Consumer Electronics, pp. 110–114, May 1990 by C. Markhauser.

[0020] More recently, a new motion detection based deinterlacing method has been described in the following two, commonly assigned patents:

- [0021] [5] U.S. Pat. No. 5,943,099, Aug. 24, 1999, issued to Young-Taeg Kim, entitled Interlaced-to-Progressive Conversion Apparatus and Method Using Motion and Spatial Correlation. There, an interlaced-to-progressive conversion device includes a spatial interpolator that provides for spatial interpolation and a temporal interpolator that provides for temporal interpolation of an interlaced video input signal. The system reduces jitter and related artifacts by temporally or spatially interpolating the signals.
- [0022] [6] U.S. Pat. No. 5,959,681, Sep. 28, 1999, to Yong-Hun Cho, entitled Motion Picture Detecting Method. There, two separate field memories are utilized for detecting rapid motion and slow motion in an interlaced video sequence. An interlaced video signal is thereby converted into a progressive-scanned signal. Differences between spatial interpolation and temporal interpolation are used to determine whether the image is in motion. If the differences exceed certain defined thresholds, motion is determined. The thresholds are dynamically adapted during the process.

[0023] The core of the methods described in the latter two patents is to estimate a motion decision factor based on the frame difference signal and the sample correlation in the vertical direction. These methods provide a way of reducing the visual artifacts that can be possibly arising from false motion detection by utilizing the sample correlation in vertical direction of the sampling point where the value is to be interpolated. A common drawback of those methods, however, is that they do not provide a true motion detection method when there are high frequency components in the vertical direction. In other words, when there are high frequency components in the vertical direction, the methods described in the references [5] and [6] will come to the conclusion that motion pictures are processed.

[0024] As a consequence, in many instances, those prior art processing methods do not provide for an increase in the vertical resolution even when no real motion is present between fields.

Summary of the Invention

[0025] It is accordingly an object of the invention to provide a motion detection method in an interlaced video sequence, which overcomes the above-mentioned disadvantages of the heretofore-known devices and methods of this general type and which provides for a robust method of estimating a motion decision parameter which is associated with the point to point degree of motion in the interlaced video sequence. It is another object of the present invention to disclose a deinterlacing method and apparatus by utilizing the motion decision parameter of the invention.

[0026] With the foregoing and other objects in view there is provided, in accordance with the invention, a method of computing a motion decision value for further utilization in a video signal processing system. The method comprises the following steps:

[0027] inputting a video signal with an interlaced video sequence;

[0028] computing a frame difference signal from a difference between a previous field and a next field in the video sequence;

[0029] forming a point-wise motion detection signal from the frame difference signal;

[0030] computing a region-wise motion detection signal from the point-wise motion detection signal and an adjacent point-wise motion detection signal delayed by one field; and

[0031] forming from the region-wise motion detection signal a motion decision value and outputting the motion decision value for further processing in the video signal processing system.

[0032] In accordance with an added feature of the invention, the difference signal is low-pass filtered prior to the step of forming the point-wise motion detection signal.

[0033] The low-pass filter may be defined by a low pass filter matrix

[0034]

W_{M \times N} = [\begin{matrix} w_{11} & w_{12} & \dots & w_{1 N} \\ w_{21} & w_{22} & \dots & w_{2 N} \\ ⋮ & ⋮ & ⋰ & ⋮ \\ w_{M1} & w_{M2} & \dots & w_{MN} \end{matrix}]

[0035] where w₁₁, . . . w_MNrepresent a set of predetermined coefficients.

[0036] In accordance with an additional feature of the invention, the step of forming the point-wise motion detection signal comprises computing
f_n(i,h)=l_K(d_n(i,h))

[0037] where f_nis the point-wise motion detection signal, i and h define a spatial location of the respective video signal value in a cartesian matrix, l_K(•) denotes a linearly scaling function represented as

[0038]

l_{K} (y) = {\begin{matrix} 1, & if & y \geq K \\ y / K, & otherwise \end{matrix}}

[0039] in which K is a positive constant value, or, alternatively, with the linearly scaling function

[0040]

l_{K} (y) = {\begin{matrix} 1, & if & y \geq K \\ {(y / K)}^{a} & otherwise \end{matrix}}

[0041] where K is still constant and a is a real number.

[0042] Various options are available for computing the region-wise motion detection signal from the point-wise motion detection signal. The following equations can be selected

[0043]

\begin{matrix} ϕ_{n} (i, h) = f_{n} (i, h) + \min (f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)) \\ ϕ_{n} (i, h) = med (f_{n} (i, h), f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)), or \\ ϕ_{n} (i, h) = \max (f_{n} (i, h), f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)) \end{matrix}

[0044] where f_n−1(•) denotes a motion detection signal delayed by one field, med(•) denotes a median operation, max(•) denotes an operation to minimize an error from a false motion detection, and the indices i and h define a spatial location of the respective video signal value in a cartesian matrix.

[0045] In accordance with another feature of the invention, the region-wise motion detection signal is low-pass filtered prior to the outputting step. In a preferred embodiment, the region-wise motion detection signal is low-pass filtered to form the motion decision value m_n(i,h) by:

[0046]

m_{n} (i, h) = \sum_{p = - a}^{b} \sum_{q = - c}^{d} ϕ_{n} (i + 2 \times p, h + 2 \times q) \cdot α_{p, q}

[0047] where a,b,c,d≧0, and α_p,qrepresents a set of normalized predetermined coefficients of a low pass filter.

[0048] The kernel of the low-pass filter may be defined as

[0049]

[α_{p, q}^{'} s] = [\begin{matrix} 0 & 1 / 8 & 0 \\ 1 / 8 & 4 / 8 & 1 / 8 \\ 0 & 1 / 8 & 0 \end{matrix}] .

[0050] With the above objects in view there is also provided, in accordance with the invention, a method of processing interlaced video signals, which comprises:

[0051] spatially interpolating a value of the video signal at a given location from a video signal of at least one adjacent location in a given video field;

[0052] temporally interpolating the value of the video signal at the given location from a video signal at the same location in temporally adjacent video fields; and

[0053] forming a motion decision value for the same location in accordance with the above-outlined method; and

[0054] mixing an output signal for the video signal at the given location from the spatially interpolated signal and the temporally interpolated signal and weighting the output signal in accordance with the motion decision value.

[0055] In accordance with again an added feature of the invention, the motion decision value is varied between 0 and 1 as a function of an estimate of the degree of motion at the given location and, upon estimating a high degree of motion, heavily weighting the output signal towards the spatially interpolated signal and, upon estimating a low degree of motion, heavily weighting the output signal towards the temporally interpolated signal.

[0056] In accordance with again an additional feature of the invention, the spatially interpolated signal is output as the output signal upon estimating a high degree of motion, and the temporally interpolated signal is output as the output signal upon estimating a low degree of motion.

[0057] With the above and other objects in view there is also provided, in accordance with the invention, an apparatus for computing a motion decision value in a video processing system. The apparatus comprises:

[0058] an input for receiving a video signal with an interlaced video sequence;

[0059] difference forming means connected to the input for computing a frame difference signal from a difference between a previous field and a next field of a current field to be deinterlaced;

[0060] means for forming a point-wise motion detection signal from the frame difference signal, and for computing a region-wise motion detection signal from the point-wise motion detection signal and an adjacent point-wise motion detection signal delayed by one field; and

[0061] means for forming from the region-wise motion detection signal a motion decision value and for outputting the motion decision value for further processing in the video signal processing system.

[0062] The apparatus is configured and/or programmed to perform the method outlined above.

[0063] A corresponding apparatus of processing interlaced video signals, for example for interlaced to progressive conversion, comprises:

[0064] an input for receiving a video signal with an interlaced video sequence of fields;

[0065] a spatial interpolator connected to the input and configured to spatially interpolate a value of the video signal at a given location from a video signal of at least one adjacent location in a given video field;

[0066] a temporal interpolator connected to the input in parallel with the spatial interpolator for temporally interpolating the value of the video signal at the given location from a video signal at the same location in temporally adjacent video fields; and

[0067] a computing apparatus as outlined above connected to the input and in parallel with the spatial interpolator and the temporal interpolator for forming a motion decision value for the same location; and

[0068] a mixer connected to receive an output signal from each of the spatial interpolator, the temporal interpolator, and the computing apparatus, the mixer being configured to mix an output signal for the video signal at the given location from the spatially interpolated signal and the temporally interpolated signal in dependence on the motion decision value output by the computing apparatus.

[0069] Other features which are considered as characteristic for the invention are set forth in the appended claims.

[0070] Although the invention is illustrated and described herein as embodied in a method of detecting motion in an interlaced video sequence based on logical operation on the linearly scaled motion information and an apparatus therefor, it is nevertheless not intended to be limited to the details shown, since various modifications and structural changes may be made therein without departing from the spirit of the invention and within the scope and range of equivalents of the claims.

[0071] The construction of the invention, however, together with additional objects and advantages thereof will be best understood from the following description of the specific embodiment when read in connection with the accompanying drawings.

Brief Description of the Drawing

[0072] FIG. 1 is a diagrammatic view of two juxtaposed fields of a frame of an interlaced video sequence;

[0073] FIG. 2 is a diagrammatic illustration of three fields serving to describe the deinterlacing problem;

[0074] FIG. 3 is a more detailed view illustrating the deinterlacing process;

[0075] FIG. 4-6 are block diagrams illustrating the computation of a motion decision parameter according to three algorithms; and

[0076] FIG. 7-9 are block diagrams illustrating the computation of the motion decision parameter, as illustrated in FIGS. 4–6, and the resultant mixing of the spatially and temporally interpolated signals in dependence on the motion decision.

Description of the Preferred Embodiments

[0077] Referring now to the figures of the drawing in detail and first, particularly, to the introductory view of FIG. 1, an interlaced video sequence is a series of frames each including a plurality of fields. As noted above, all conventional systems utilize two fields per frame which are sequentially scanned. A top field 1 contains information regarding the first (v=0), third (v=2), fifth (v=4), etc. lines, and a bottom field 2 contains information regarding the second (v=1), fourth (v=3), sixth (v=5), etc. lines.

[0078] In order to systematically describe the deinterlacing problem and the methods of the present invention, let x_ndenote the incoming interlaced video field at a time instant t=n and x_n(v,h) denote the associated value of the video signal at the geometrical location (v,h). The variable v represents the vertical location and h represents horizontal location, in the cartesian matrix system commonly applied. By definition, the signal values of x_nof the interlaced video signal are available only for the even lines (v=0,2,4, . . . ) if x_nis the top field 1. Similarly, the signal values of x_nare available only for the odd lines of v (v=1,3,5, . . . ) if x_nis the bottom field 2. Conversely, the signal values of x_nare not available for odd lines if x_nis a top field signal and the signal values of x_nare not available for even lines if x_na bottom field. FIG. 1 shows the top field 1 scanned at t=m and the bottom field 2 scanned at t=m+1. Top and bottom fields are typically available in turn in the time axis, that is, the top and bottom fields are sequentially scanned to make up a frame.

[0079] Based upon the description of the interlaced video signal, deinterlacing problem can be stated as a process to reconstruct or interpolate the non-available signal values of each field. That is, the deinterlacing problem is to reconstruct the signal values of x_nat the odd lines (v=1,3,5, . . . ) for the top field x_nand to reconstruct the signal values of x_nat the even lines (v=0,2,4, . . . ) for the bottom field x_n.

[0080] For the simple description of the present invention, and to avoid any notational confusion in the disclosure, the deinterlacing problem will be simplified as a process which reconstructs or interpolates the unavailable signal value of x_nat the i^thline where the signal values of the lines at i±1, i±3, i±5, . . . are available. More simply deinterlacing is to interpolate the value of x_n(i,h), which is not originally available. It must be noted that, since x_n−1, and x_n+1have a different sampling phase from x_n, the signal values of x_n−1(i,h) and x_n+1(i,h) are available, which is why motion detection can be incorporated with the deinterlacing problem. This relationship is depicted in FIG. 2, where dotted lines (and white circles) represent “no data available” and solid lines (and black circles) represent “available data.”

[0081] The deinterlacing method and an exemplary apparatus of the present invention with preferred embodiments will be better understood from the following description, which will make specific reference to FIGS. 3–5 of the drawing.

[0082] Referring now to FIG. 4, there is illustrated the novel method of estimating a motion decision parameter m_n(i,h). Fundamentally, m_n(i,h) is estimated from the incoming interlaced video sequence and associated with the point-to-point degree of motion in the interlaced video sequence. The importance or the usefulness of estimating m_n(i,h) can be easily understood from FIGS. 2 and 3. Suppose that precise motion detection information is available when we interpolate x_n(i,h) and suppose there is no motion at the spatial location (i,h), then the best interpolation for x_n(i,h) is to use the value of x_n−1(i,h). This follows logically from the fact that no motion is introduced between t=n−1 and t=n+1 at the spatial location (i,h), which very strongly implies that the value of x_n(i,h) would be close to the value of x_n−1(i,h). The usage of the motion decision parameter of the present invention is also to utilize the motion information for deinterlacing to properly mix the temporal information, which will be described later.

[0083] First, the frame difference signal D_nis computed by taking the difference between the fields in one frame interval as
D_n=|x_n+1−x_n−1|

[0084] which associates with the scene change that occurred between the fields x_n+1and x_n−1. The frame difference signal is then low pass filtered to form
d_n=LPF(D_n)

[0085] where LPF(•) represents a low pass filtering process over the input video signal. The M×N kernel, W_M×N, in general, of the low pass filter LPF(•), can be expressed as

[0086]

W_{M \times N} = [\begin{matrix} w_{11} & w_{12} & \dots & w_{1 N} \\ w_{21} & w_{22} & \dots & w_{2 N} \\ ⋮ & ⋮ & ⋰ & ⋮ \\ w_{M1} & w_{M2} & \dots & w_{MN} \end{matrix}]

[0087] where (w₁₁, . . . , w_MN) represents a set of predetermined coefficients. It should be mentioned that the characteristic of the LPF (•) can be all-pass filter depending on the choice of the kernel W_M×N. That is, if the kernel is set as M=N=1, and w₁₁1, the LPF(•) becomes an all-pass filter and, thus, d_n=D_n.

[0088] Next, a point-wise motion detection signal is computed as
f_n(i,h)=l_K(d_n(i,h)) (1)

[0089] where l^K(•) denotes a linearly scaling function represented as

[0090]

l_{K} (y) = {\begin{matrix} 1, & if & y \geq K \\ y / K, & otherwise \end{matrix}}

[0091] in which K is a positive constant value. Or, as an alternative method, we can define the scaling function l_K(y) as

[0092]

l_{K} (y) = {\begin{matrix} 1, & if & y \geq K \\ {(y / K)}^{a} & otherwise \end{matrix}}

[0093] where a is a real number. Or, more in general, this invention discloses to use the scaling function l_K(y) as to be a monotonously increasing function represented as l_K(0)=0, l_K(y)=1 for y≧K, and
∀0≦y₁≦y₂≦K,1_K(y₁)≦l_K(y₂)

[0094] which implies l_K(y) is monotonously increasing as y increases. Then the region-wise motion detection signal is computed from the point-wise motion detection signal as
φ_n(i,h)=f_n(i,h)+min(f_n−1(i−1,h),f_n−1(i+1,h)) (2)

[0095] where f_n−1(•) denotes the one field delayed motion detection signal described in (1). Or, as an alternative method, we define the region-wise motion detection signal as
φ_n(i,h)=med(f_n(i,h),f_n−1(i−1,h),f_n−1(i+1,h)) (3)

[0096] where med(•) denotes a median operation. Or, in order to minimize the error from a false motion detection, we define the region-wise motion detection signal as
φ_n(i,h)=max(f_n(i,h),f_n−1(i−1,h),f_n−1(i+1,h)) (4)

[0097] Finally, the region-wise motion detection signal is low pass filtered to form the motion decision parameter m_n(i,h) as

[0098]

\begin{matrix} m_{n} (i, h) = \sum_{p = - a}^{b} \sum_{q = - c}^{d} ϕ_{n} (i + 2 \cdot p, h + 2 \cdot q) \cdot α_{p, q} & (5) \end{matrix}

[0099] where a,b,c,d≧0, and a_p,qrepresents a set of normalized (i.e.,

[0100]

\sum_{p = - a}^{b} \sum_{q = - c}^{d} α_{p, q} = 1

predetermined coefficients of a low pass filter. For instance, the kernel of the low pass filter used in (5) can be

[0101]

[α_{p, q}^{'} s] = [\begin{matrix} 0 & 1 / 8 & 0 \\ 1 / 8 & 4 / 8 & 1 / 8 \\ 0 & 1 / 8 & 0 \end{matrix}]

[0102] The block diagram of FIG. 4 illustrates the computation of the motion decision parameter m_n(i,h) as described above with the region-wise motion detection signal defined in equation (2).

[0103] The block diagram of FIG. 5 illustrates the computation of the motion decision parameter m_n(i,h) as described above with the region-wise motion detection signal defined in equation (3).

[0104] The block diagram of FIG. 6 illustrates the computation of the motion decision parameter m_n(i,h) as described above with the region-wise motion detection signal defined in equation (4).

[0105] The computed motion decision parameter m_n(i,h) is then used to mix a spatially interpolated signal and the a temporally interpolated signal, which is described next.

[0106] FIGS. 7, 8, and 9 are block diagrams of embodiments of the present invention for interpolating the value of x_n(i,h) for an interlaced video sequence. The apparatus comprises a spatial interpolator 3, a temporal interpolator 4, a motion decision processor 5, and a mixer 6. The decision processor 5 corresponds to the diagram illustrated in FIGS. 4, 5, and 6, respectively, and includes, in a signal flow direction, an absolute value former 51 which defines the absolute difference parameter D_n; a first low pass filter LPF 52 in which the filtering function W_M×Nwith the M×N kernel is set; the member 53 represents the linearly scaling function as outlined above; a buffer memory 54 and a further line memory 55 are connected to a minimum former 56; the function signal φ_n(i,h) is formed in an adder 58 from the signal f_n(i,h) and the signal from the member 56; finally, the motion detection signal m_n(i,h) is formed by low pass filtering in a second filter, i.e., a spatial low pass filter LPF 57. The output of the low pass filter 57 is connected so that the motion detection signal m_n(i,h) is supplied to a control input of the mixer 6.

[0107] The spatial interpolator 3 spatially interpolates the value of x_n(i,h) by using a predetermined algorithm. The temporal interpolator 4 temporally interpolates the value of x_n(i,h) by using a predetermined algorithm. The motion decision processor 5 computes the motion decision value, m_n(i,h) as disclosed in the foregoing, which represents the degree of the motion at the interpolation location (i,h). Conceptually, the value of the motion decision parameter will be bounded as 0≦m_n(i,h)≦1 where m_n(i,h)=0 implies “no motion” and m_n(i,h)=1 implies “motion”. The mixer 6 mixes the output signal x_n^s(i,h) of the spatial interpolator 3 and the output signal x_n^t(i,h) of the temporal interpolator 4 in accordance with the motion decision value. Where x_n^s(i,h) and x_n^t(i,h) are the output signal of the spatial interpolator 3 and the output signal of the temporal interpolator 4, respectively, the output signal of the mixer, or, the interpolated signal is represented as
x_n(i,h)=(1−m_n(i,h))·x_n^t(i,h)+m_n(i,h)·x_n^s(i,h) (6)

[0108] Note that x_n(i,h)=x_n^t(i,h) when m_n(i,h)=0(no motion) and x_n(i,h)=x_n^s(v,h) when m_n(i,h)=1(motion).

[0109] In FIG. 7, FIG. 8, and FIG. 9, it does not matter what kind of a spatial interpolating algorithm and a temporal interpolating algorithm are used for the spatial interpolator 3 and the temporal interpolator 4, respectively. The present invention only relates to estimating the motion decision value m_n(i,h) and to mixing a spatially interpolated signal and a temporally interpolated signal in accordance with the estimated motion decision value.

[0110] Specific information with regard to the interpolation of interlaced video signals and interlaced to progressive conversion is readily available to those of skill in the pertinent art. The above-noted disclosures, namely U.S. Pat. Nos. 5,943,099 and 5,959,68 1, are specifically incorporated by reference.

[0111] Some examples of the spatially interpolated signal x_n^s(v,h) are
x_n^s(i,h)=(x_n(i−1,h)+x_n(i+1,h))/2

[0112] which corresponds to a line average and
x_n^s(i,h)=x_n(i−1,h)

[0113] which corresponds to a method known as line doubling.

[0114] Some examples of temporally interpolated signal x_n^s(v,h) are
x_n^t(i,h)=(x_n+1(i,h)+x_n−1(i,h))/2
and
x_n^t(i,h)=x_n−1(i,h)

Claims

What is claimed is:

1. In a video signal processing system, a method of computing a motion decision value, which comprises the following steps:

inputting a video signal with an interlaced video sequence of fields;

computing a frame difference signal from a difference between a previous field and a next field in the video sequence;

forming a point-wise motion detection signal from the frame difference signal;

computing a region-wise motion detection signal from the point-wise motion detection signal and an adjacent point-wise motion detection signal delayed by one field; and

forming from the region-wise motion detection signal a motion decision value and outputting the motion decision value.

2. The method according to claim 1, which further comprises low-pass filtering the difference signal prior to the step of forming the point-wise motion detection signal.

3. The method according to claim 2, wherein the step of low-pass filtering is defined by a low pass filter matrix

W_{MxN} = [\begin{matrix} w_{11} & w_{12} & \dots & w_{1 N} \\ w_{21} & w_{22} & \dots & w_{2 N} \\ ⋮ & ⋮ & ⋰ & ⋮ \\ w_{M1} & w_{M2} & \dots & w_{MN} \end{matrix}]

where w₁₁, . . . w_MNrepresent a set of predetermined coefficients.

4. The method according to claim 1, wherein the step of forming the point-wise motion detection signal comprises computing

f_n(i,h)=l_K(d_n(i,h))

where f_nis the point-wise motion detection signal, i and h define a spatial location of the respective video signal value in a cartesian matrix, l _K(•) denotes a linearly scaling function represented as

l_{K} (y) = {\begin{matrix} 1, & if & y \geq K \\ y / K, & otherwise \end{matrix}}

in which K is a positive constant value.

5. The method according to claim 1, wherein the step of forming the point-wise motion detection signal comprises computing

f_n(i,h)=l_K(d_n(i,h))

where f_nis the point-wise motion detection signal, i and h define a spatial location of the respective video signal value in a cartesian matrix, l_K(•) denotes a linearly scaling function represented as

l_{K} (y) = {\begin{matrix} 1, & if & y \geq K \\ {(y / K)}^{a} & otherwise \end{matrix}}

where K is a positive constant value and a is a real number.

6. The method according to claim 1, wherein the region-wise motion detection signal is computed from the point-wise motion detection signal by an equation selected from the group consisting of

\begin{matrix} ϕ_{n} (i, h) = f_{n} (i, h) + \min (f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)) \\ ϕ_{n} (i, h) = med (f_{n} (i, h), f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)) \\ ϕ_{n} (i, h) = \max (f_{n} (i, h), f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)) \end{matrix}

where f_n−1(•) denotes a motion detection signal delayed by one field, med(•) denotes a median operation, max(•) denotes an operation to minimize an error from a false motion detection, and the indices i and h define a spatial location of the respective video signal value in a cartesian matrix.

7. The method according to claim 1, which further comprises low-pass filtering the region-wise motion detection signal prior to the outputting step.

8. The method according to claim 7, wherein the region-wise motion detection signal is low-pass filtered to form the motion decision value m_n(i,h) by:

m_{n} (i, h) = \sum_{p = - a}^{b} \sum_{q = - c}^{d} ϕ_{n} (i + 2 \times p, h + 2 \times q) \cdot α_{p, q}

where a,b,c,d≧0, and α_p,qrepresents a set of normalized predetermined coefficients of a low pass filter.

9. The method according to claim 7, which comprises defining a kernel of the low pass filter as

[α_{p, q}^{'} s] = [\begin{matrix} 0 & 1 / 8 & 0 \\ 1 / 8 & 4 / 8 & 1 / 8 \\ 0 & 1 / 8 & 0 \end{matrix}] .

10. The method according to claim 1, wherein the step of forming the point-wise motion detection signal comprises the steps of scaling the frame difference signal to form the point-wise motion detection signal.

11. The method according to claim 1, wherein the step of forming the point-wise motion detection signal comprises the steps of linearly scaling the frame difference signal to form the point-wise motion detection signal.

12. The method according to claim 1, wherein the step of forming the point-wise motion detection signal comprises the steps of scaling the frame difference signal with a monotonously increasing function, to form the point-wise motion detection signal.

13. In a method of processing interlaced video signals, which comprises:

spatially interpolating a value of the video signal at a given location from a video signal of at least one adjacent location in a given video field;

temporally interpolating the value of the video signal at the given location from a video signal at the same location in temporally adjacent video fields; and

forming a motion decision value for the same location in accordance with claim 1; and

mixing an output signal for the video signal at the given location from the spatially interpolated signal and the temporally interpolated signal and weighting the output signal in accordance with the motion decision value.

14. The method according to claim 13, which comprises varying the motion decision value between 0 and 1 as a function of an estimate of the degree of motion at the given location and, upon estimating a high degree of motion, heavily weighting the output signal towards the spatially interpolated signal and, upon estimating a low degree of motion, heavily weighting the output signal towards the temporally interpolated signal.

15. The method according to claim 14, which comprises outputting the spatially interpolated signal as the output signal upon estimating a high degree of motion, and outputting the temporally interpolated signal as the output signal upon estimating a low degree of motion.

16. In a video signal processing system, an apparatus for computing a motion decision value, comprising:

an input for receiving a video signal with an interlaced video sequence;

difference forming means connected to said input for computing a frame difference signal from a difference between a previous field and a next field of a current field to be deinterlaced;

means for forming a point-wise motion detection signal from the frame difference signal, and for computing a region-wise motion detection signal from the point-wise motion detection signal and an adjacent point-wise motion detection signal delayed by one field; and

means for forming from the region-wise motion detection signal a motion decision value and for outputting the motion decision value.

17. The apparatus according to claim 16, which further comprises a low-pass filter connected to said difference forming means.

18. The apparatus according to claim 17, wherein said low-pass filter is programmed with a low pass filter matrix

W_{MxN} = [\begin{matrix} w_{11} & w_{12} & \dots & w_{1 N} \\ w_{21} & w_{22} & \dots & w_{2 N} \\ ⋮ & ⋮ & ⋰ & ⋮ \\ w_{M1} & w_{M2} & \dots & w_{MN} \end{matrix}]

where w₁₁, . . . w_MNrepresent a set of predetermined coefficients.

19. The apparatus according to claim 16, wherein said means for forming the point wise motion detection signal are programmed to compute

f_n(i,h)=l_K(d_n(i,h))

where In is the point-wise motion detection signal, i and h define a spatial location if the respective video signal value in a cartesian matrix, I_K(•) denotes a linearly scaling function represented as

l_{K} (y) = {\begin{matrix} 1, & if & y \geq K \\ y / K,^{} & otherwise \end{matrix}}, and

K is a positive constant value.

20. The apparatus according to claim 16, wherein said means for forming the point wise motion detection signal are programmed to compute

f_n(i,h)=l_K(d_n(i,h))

where f_nis the point-wise motion detection signal, i and h define a spatial location of the respective video signal value in a cartesian matrix, l_K(•) denotes a linearly scaling function represented as

l_{K} (y) = {\begin{matrix} 1, & if & y \geq K \\ {(y / K)}^{a} & otherwise \end{matrix}}, and

wherein K is a positive constant value and a is a real number.

21. The apparatus according to claim 16, wherein the means for computing the region-wise motion detection signal are programmed to compute the region-wise motion detection signal from the point-wise motion detection signal by an equation selected from the group consisting of

\begin{matrix} ϕ_{n} (i, h) = f_{n} (i, h) + \min (f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)) \\ ϕ_{n} (i, h) = med (f_{n} (i, h), f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)) \\ ϕ_{n} (i, h) = \max (f_{n} (i, h), f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)) \end{matrix}

where f_n−1(•)denotes a motion detection signal delayed by one field, med(•) denotes a median operation, max(•) denotes an operation to minimize an error from a false motion detection, and the indices i and h define a spatial location of the respective video signal value in a cartesian matrix.

22. The apparatus according to claim 16, which further comprises a low-pass filter connected to an output of said outputting means.

23. The apparatus according to claim 22, wherein said low-pass filter is programmed to filter the region-wise motion detection signal to form the motion decision value m_n(i,h) by:

m_{n} (i, h) = \sum_{p = - a}^{b} \sum_{q = - c}^{d} ϕ_{n} (i + 2 \times p, h + 2 \times q) \cdot α_{p, q}

where a,b,c,d≧0, and α_p,qrepresents a set of normalized predetermined coefficients of said low pass filter.

24. The apparatus according to claim 23, wherein said low-pass filter is defined with a kernel

[α_{p, q}^{'} s] = [\begin{matrix} 0 & 1 / 8 & 0 \\ 1 / 8 & 4 / 8 & 1 / 8 \\ 0 & 1 / 8 & 0 \end{matrix}] .

25. An apparatus of processing interlaced video signals, which comprises:

an input for receiving a video signal with an interlaced video sequence of fields;

a spatial interpolator connected to said input and configured to spatially interpolate a value of the video signal at a given location from a video signal of at least one adjacent location in a given video field;

a temporal interpolator connected to said input in parallel with said spatial interpolator for temporally interpolating the value of the video signal at the given location from a video signal at the same location in temporally adjacent video fields; and

a computing apparatus according to claim 16 connected to said input and in parallel with said spatial interpolator and said temporal interpolator for forming a motion decision value for the same location; and

a mixer connected to receive an output signal from each of said spatial interpolator, said temporal interpolator, and said computing apparatus, said mixer being configured to mix an output signal for the video signal at the given location from the spatially interpolated signal and the temporally interpolated signal in dependence on the motion decision value output by said computing apparatus.

Patent Citations (56)

Patent	Date	Inventor	Cited By
US4661853(A)	1987-04-01	Roeder et al.	Examiner
US4933759(A)	1990-06-01	Van der Meer et al.	Examiner
US5027201(A)	1991-06-01	Bernard	Examiner
US5051826(A)	1991-09-01	Ishii et al.	Examiner
US5081532(A)	1992-01-01	Rabii	Examiner
US5434627(A)	1995-07-01	Weston	Examiner
US5534935(A)	1996-07-01	Kawai et al.	Examiner
US5600377(A)	1997-02-01	David et al.	Examiner
US5638139(A)	1997-06-01	Clatanoff et al.	Examiner
US5661525(A)	1997-08-01	Kovacevic et al.	Examiner
US5796437(A)	1998-08-01	Muraji et al.	Examiner
US5943099(A)	1999-08-01	Kim	Examiner
US5959681(A)	1999-09-01	Cho	Applicant
US6014182(A)	2000-01-01	Swartz	Examiner
US6037986(A)	2000-03-01	Zhang et al.	Examiner
US6061100(A)	2000-05-01	Ward et al.	Examiner
US6072531(A)	2000-06-01	Shibano	Examiner
US6108041(A)	2000-08-01	Faroudja et al.	Examiner
US6122017(A)	2000-09-01	Taubman	Examiner
US6239842(B1)	2001-05-01	Segman	Examiner
US6266092(B1)	2001-07-01	Wang et al.	Examiner
US6268886(B1)	2001-07-01	Choi	Examiner
US6275259(B1)	2001-08-01	Gowda et al.	Examiner
US6288745(B1)	2001-09-01	Okuno et al.	Examiner
US6295091(B1)	2001-09-01	Huang	Examiner
US6307560(B1)	2001-10-01	Kondo et al.	Examiner
US6317165(B1)	2001-11-01	Balram et al.	Examiner
US6330032(B1)	2001-12-01	Boehlke	Examiner
US6331874(B1)	2001-12-01	de Garrido et al.	Examiner
US6340990(B1)	2002-01-01	Wilson	Examiner
US6348949(B1)	2002-02-01	McVeigh	Examiner
US6414719(B1)	2002-07-01	Parikh	Examiner
US6418233(B1)	2002-07-01	Kondo et al.	Examiner
US6421090(B1)	2002-07-01	Jiang et al.	Examiner
US6449312(B1)	2002-09-01	Zhang et al.	Examiner
US6452639(B1)	2002-09-01	Wagner et al.	Examiner
US6452972(B1)	2002-09-01	Ohara	Examiner
US6459455(B1)	2002-10-01	Jiang et al.	Examiner
US6483546(B1)	2002-11-01	Kondo et al.	Examiner
US6512550(B1)	2003-01-01	de Garrido et al.	Examiner
US6621936(B1)	2003-09-01	Kondo et al.	Examiner
US6630961(B1)	2003-10-01	Shin et al.	Examiner
US6633612(B1)	2003-10-01	Selby	Examiner
US6636267(B1)	2003-10-01	Adachi	Examiner
US6647062(B1)	2003-11-01	Mackinnon	Examiner
US6754371(B1)	2004-06-01	Kondo et al.	Examiner
US6795123(B1)	2004-09-01	Gotanda et al.	Examiner
US6822691(B1)	2004-11-01	Kim et al.	Examiner
US6829013(B1)	2004-12-01	Thompson et al.	Examiner
US6847405(B1)	2005-01-01	Hsu et al.	Examiner
US6859237(B1)	2005-02-01	Swartz	Examiner
US6909466(B1)	2005-06-01	Scheffler et al.	Examiner
US2002/0027610(A1)	2002-03-01	Jiang et al.	Examiner
US2004/0184541(A1)	2004-09-01	Brockmeyer et al.	Examiner
US2004/0196901(A1)	2004-10-01	Demos	Examiner
US2004/0202245(A1)	2004-10-01	Murakami et al.	Examiner

Non-Patent Literature (6)

Simple line doubling scheme, vertical filtering edge controlled interpolation method disclosed in the IEEE Transactions on Consumers Electronics, pp. 279-289, Aug. 1989 by D.I. Hentschei.Applicant
Edge direction dependent deinterlacing method disclosed in the Proc. of the Int. Workshop on HDTV, 1994, by D. Bagni, R. Lancini, and S. Tubaro, S Landi pp. 137-145.Applicant
Nonlinear interpolation methods based on: a weighted median filter disclosed in the Proc. of IEEE ISCAS, pp. 433-436 Portland, USA, May 1989, by J. Juhola, A. Nieminen, J. Sal, and Y. Neuvo.Applicant
Nonlinear interpolation based on: FIR median hybrid interpolation disclosed in Pro. of SPIE's Visual Communications and Image Processing, Lausanne, Switzerland, Oct. 1990, pp. 135-142 by A. Lehtonen and M. Renfors.Applicant
Nonlinear interpolation methods based on: a complementary median filter disclosed in Proc. of the Int. Workshop on HDTV, 1994 by H. Blume, I. Schwoerer, and K. Zygis, pp. 127-135.Applicant
A motion adaptive method disclosed in IEEE Transactions on Consumer Electronics, pp. 110-114, May 1990 by C. Markhauser.Applicant

Abstract

Description

Cross-References to Related Applications

Background of the Invention

[0002] 1. Field of the Invention

[0004] 2. Description of the Related Art

[0011] The present invention therefore also relates to the motion detection based deinterlacing operation that can be used for analog and digital TV receivers.

- [0013] [1] Simple line doubling scheme, vertical filtering, vertical edge controlled interpolation method disclosed in the IEEE Transactions on Consumers Electronics, pp. 279–89, August 1989 by D. I. Hentschei;
- [0014] [2] Edge direction dependent deinterlacing method disclosed in the Proc. of the Int. Workshop on HDTV, 1994, by D. Bagni, R Lancini, and S. Tubaro;
- [0015] [3] Nonlinear interpolation methods based on:
- [0016] a weighted median filter disclosed in the Proc. of the IEEE ISCAS, pp. 433–36, Portland, USA, May 1989, by J. Juhola, A. Nieminen, J. Sal, and Y. Neuvo,
- [0017] FIR median hybrid interpolation disclosed in Pro. Of SPIE's Visual Communications and Image Processing, Lausanne, Switzerland, October 1990, 00. 125–32 by A. Lehtonen and M. Renfors,
- [0018] a complementary median filter disclosed in Proc. of the Int. Workshop on HDTV, 1994 by H. Blume, I. Schwoerer, and K. Zygis,
- [0019] [4] A motion adaptive method disclosed in IEEE Transactions on Consumer Electronics, pp. 110–114, May 1990 by C. Markhauser.

[0020] More recently, a new motion detection based deinterlacing method has been described in the following two, commonly assigned patents:

- [0021] [5] U.S. Pat. No. 5,943,099, Aug. 24, 1999, issued to Young-Taeg Kim, entitled Interlaced-to-Progressive Conversion Apparatus and Method Using Motion and Spatial Correlation. There, an interlaced-to-progressive conversion device includes a spatial interpolator that provides for spatial interpolation and a temporal interpolator that provides for temporal interpolation of an interlaced video input signal. The system reduces jitter and related artifacts by temporally or spatially interpolating the signals.
- [0022] [6] U.S. Pat. No. 5,959,681, Sep. 28, 1999, to Yong-Hun Cho, entitled Motion Picture Detecting Method. There, two separate field memories are utilized for detecting rapid motion and slow motion in an interlaced video sequence. An interlaced video signal is thereby converted into a progressive-scanned signal. Differences between spatial interpolation and temporal interpolation are used to determine whether the image is in motion. If the differences exceed certain defined thresholds, motion is determined. The thresholds are dynamically adapted during the process.

[0024] As a consequence, in many instances, those prior art processing methods do not provide for an increase in the vertical resolution even when no real motion is present between fields.

Summary of the Invention

[0027] inputting a video signal with an interlaced video sequence;

[0028] computing a frame difference signal from a difference between a previous field and a next field in the video sequence;

[0029] forming a point-wise motion detection signal from the frame difference signal;

[0030] computing a region-wise motion detection signal from the point-wise motion detection signal and an adjacent point-wise motion detection signal delayed by one field; and

[0031] forming from the region-wise motion detection signal a motion decision value and outputting the motion decision value for further processing in the video signal processing system.

[0032] In accordance with an added feature of the invention, the difference signal is low-pass filtered prior to the step of forming the point-wise motion detection signal.

[0033] The low-pass filter may be defined by a low pass filter matrix

[0034]

W_{M \times N} = [\begin{matrix} w_{11} & w_{12} & \dots & w_{1 N} \\ w_{21} & w_{22} & \dots & w_{2 N} \\ ⋮ & ⋮ & ⋰ & ⋮ \\ w_{M1} & w_{M2} & \dots & w_{MN} \end{matrix}]

[0035] where w₁₁, . . . w_MNrepresent a set of predetermined coefficients.

[0036] In accordance with an additional feature of the invention, the step of forming the point-wise motion detection signal comprises computing
f_n(i,h)=l_K(d_n(i,h))

[0038]

l_{K} (y) = {\begin{matrix} 1, & if & y \geq K \\ y / K, & otherwise \end{matrix}}

[0039] in which K is a positive constant value, or, alternatively, with the linearly scaling function

[0040]

l_{K} (y) = {\begin{matrix} 1, & if & y \geq K \\ {(y / K)}^{a} & otherwise \end{matrix}}

[0041] where K is still constant and a is a real number.

[0042] Various options are available for computing the region-wise motion detection signal from the point-wise motion detection signal. The following equations can be selected

[0043]

\begin{matrix} ϕ_{n} (i, h) = f_{n} (i, h) + \min (f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)) \\ ϕ_{n} (i, h) = med (f_{n} (i, h), f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)), or \\ ϕ_{n} (i, h) = \max (f_{n} (i, h), f_{n - 1} (i - 1, h), f_{n - 1} (i + 1, h)) \end{matrix}

[0046]

m_{n} (i, h) = \sum_{p = - a}^{b} \sum_{q = - c}^{d} ϕ_{n} (i + 2 \times p, h + 2 \times q) \cdot α_{p, q}

[0047] where a,b,c,d≧0, and α_p,qrepresents a set of normalized predetermined coefficients of a low pass filter.

[0048] The kernel of the low-pass filter may be defined as

[0049]

[α_{p, q}^{'} s] = [\begin{matrix} 0 & 1 / 8 & 0 \\ 1 / 8 & 4 / 8 & 1 / 8 \\ 0 & 1 / 8 & 0 \end{matrix}] .