SPARSE GEOMETRY FOR SUPER RESOLUTION VIDEO PROCESSING

In a method of analyzing an input video sequence, pixels of synthesized images of an output video sequence are associated with respective directions of regularity belonging to a predefined set of directions. A first subset of candidate directions is determined from the predefined set of directions for a region of a first image of the output sequence. For a corresponding region of a second synthesized image of the output sequence following the first image, a second subset of candidate directions is determined from the predefined set of directions, based on images of the input sequence and the first subset of candidate directions. The directions of regularity for pixels of this region of the second synthesized image are detected from the second subset of candidate directions. The recursive determination of the subsets of candidate directions provides a sparse geometry for efficiently analyzing the video sequence.

DESCRIPTION OF PREFERRED EMBODIMENTS

Referring toFIG. 1, a video processing device has an input receiving digital representations of successive images or frames of a video sequence. It, It+1denote frames at discrete times t and t+1, and It(x), It+1(x) denote pixel values of those frames for a pixel located by a 2-dimensional index x=(x1, x2). How the time indexes t and spatial indexes x are managed may differ from one video processing application to another, e.g. between deinterlacing, frame rate conversion and noise reduction. This issue will be addressed further below.

A direction selection unit101implements a time recursive estimation to determine a subset Dτ′of candidate directions for an output frame Îτ′based on a previous subset Dτand on the consecutive input frames. The aforesaid “previous subset Dτ” was determined for an output frame Îτwhich immediately precedes Îτ′in the output video sequence. For example τ′=τ+1 for deinterlacing or simple noise reduction; τ′=τ+δτ for frame rate conversion or super-resolution noise reduction. The input frames involved in the determination of the subset Dτ′at time τ′ include at least Itand It+1such that t≦τ′<t+1. In certain embodiments, they may further include a few past frames It−1, . . . , It−n(n≧1).

As referred to herein, a “direction” v=(dx, dt) is meant as a direction in the 3D space in which two dimensions relate to pixel offsets dx=(dx1, dx2) in the 2D image space and the third direction relates to a time offset dt. There are a number of video applications in which it is desired to look for directions of regularity in an incoming video sequence. When doing video interpolation for example, one must determine the values of certain missing pixels based on “similar” pixels in a neighborhood of the missing pixels. Such a neighborhood can extend in the 2D image space and/or in time, so that it is relevant to look for it in the above-mentioned 3D space. Likewise, in noise reduction applications, the value of an input pixel is corrupted by noise which can be averaged out if it is possible to identify some neighborhood of “similar” pixels. Again, such a neighborhood can extend in the 2D image space and/or in time. The method described below yields directions of regularity for pixels of the images which help determining the “similar” pixel values useful to the processing.

The subset Dτor Dτ′is said to define a sparse geometry. Each subset Dτor Dτ′is a subset of a set Ω containing all the possible directions of regularity. The geometry defined by Dτ, Dτ′is said to be sparse because for each instant τ, τ′, the number of different directions that can be used is limited to a relatively small number. As described further below, the subset of candidate directions Dτ, Dτ′, . . . evolves in time with marginal changes. Directions that would be redundant in Dτ, Dτ′are removed and not used for the pixel-by-pixel processing.

Typically, Ω can contain 200 to 1000 different directions (200≦|Ω|≦1000, bars being used to denote the size of a set). The subsets Dτ, Dτ′, . . . can have their sizes limited in the range 10≦|Dτ|≦50.

A direction detection unit102then determines a distribution of directions of regularity {v} based on the consecutive frames It, It+1(and possibly a few past frames It−1, . . . , It−n) by testing only candidate directions belonging to the subset Dτ′determined by the selection unit101. The reduction in size from Ω to Dτ′makes it possible to carry out the detection without requiring an exceedingly high complexity.

Finally, the video processing unit103uses the detected directions of regularity {v} to perform a video processing, such as deinterlacing, frame rate conversion or noise reduction to deliver output video frames from the input frames It, It+1.

Units102and103can implement any conventional or state-of-the-art methods, and simple examples will be given for completeness. In particular, the detection unit102can use the loss function described in WO 2007/115583 A1. The core of the invention lies in unit101that will be described in greater detail.

As the direction selection unit101considers a much larger set of directions than the direction detection unit102, an interesting possibility is to use a simpler or cost function in unit101than in unit102. In other words, the local cost functions are estimated more coarsely in the step of determining the direction subset Dτ′(selection unit101) than in the step of picking the directions from that subset (direction detection unit102). This provides substantial savings in terms of computational complexity or, equivalently, in terms of ASIC/FPGA logic size.

This can be done, for example, by using less precise representations of pixel values, e.g. 5- or 6-bit pixel values in unit101instead of 8- to 10-bit pixel values in unit102. Another possibility is to use in the direction selection unit101convolution windows g (to be described further below) that are simpler to compute than those used in the direction detection unit102, e.g. window profiles corresponding to simple infinite impulse response (IIR) filters which do not require so much logic and memory as large explicit finite impulse response (FIR) filters. Also, cost functions (described below) of different computational complexities can be used for the subset selection in unit101, and for the pixelwise direction detection in unit102.

The aim of the selection unit101is to compute a subset of directions Dτ′providing a useful description of the local regularity of the video sequence at an instant τ′ in the output sequence. The best subset D is the one that minimizes a global cost (or loss) function L(D):

where the sum over the pixels (x) spans the whole image area (or part of it). The quantity Lx(v) to be minimized over the candidate directions v of D is a local cost (or loss) function, which can be of various kinds for v=(dx, dt), such as:

Weighted sum of absolute differences:

Weighted sum of quadratic differences:

where g is a convolution window function, i.e. with non-zero values in a vicinity of (0,0).

Other variants are possible, including computing local cost functions over more than two frames of the video sequence, e.g. Lx(v)=|It(x)−It+dt(x+dx)|+|It(x)−It−dt(x−dx)|, and similar variations.

For convenience, we also define the local cost Lx(D) of a set of directions as the minimum of the loss function over all directions in that set:

Note that finding the subset D minimizing (1) is of extreme combinatorial complexity, because the value of adding a direction to the subset D depends on the directions already present in that subset. To overcome this difficulty, an incremental approach is proposed. The minimization is done using time recursion, by applying only marginal changes to Dτ, Dτ′, . . . in time.

The direction selection unit101as depicted inFIG. 2has a block201for evaluating margins m(v) for different directions v of the set of possible directions Ω, and an arbitration block202to decide, based on the margins m(v) which directions of Dτshould be excluded from Dτ′and which directions of Ω−Dτshould be included into Dτ′. The directions v selected to be added to Dτto get Dτ′are chosen depending on how much they would marginally contribute to improving (reducing) the cost function L(D) according to (1). Likewise, the directions v to be removed from Dτare chosen depending on how little they marginally contribute to reducing that cost function L(D).

Deciding which elements are in Dτ′cannot be done by evaluating L(D) for the various combinations D which may form Dτ′. However, how L(D) varies when a new direction v of Ω−D is added to D can be estimated using the margin, noted m(v|D), of a direction v with respect to an existing direction subset D:

where D+(v) denotes the union of the set D and of the singleton {v}. In other words, m(v|D) is the measure of how much a new direction marginally contributes to lowering the cost function (1) already obtained with a subset of directions D. The margins m(v|D) can be computed using:

where the local margin mx(v|D) at location x of v with respect to D is:mx(v|D)=0 if Lx(v)≧Lx(D), i.e. when v is not better at minimizing the cost function at pixel position x than the directions already in D;mx(v|D)=Lx(D)−Lx(v) else.

Computing a margin mx(v|D) for a fixed D and for each x and each candidate v in Ω−D can be done by determining the quantities Lx(D) and Lx(v). Then m(v|D) is computed by updating running sums of mx(v|D).

Let us consider the case of including a new direction va, and removing an already selected direction vrfrom Dτto compute Dτ′as

The decrease of the global cost (1) caused by such an exchange can be written as an exchange margin Mexch(va, vr):

In a first approximation, m(vr|Dτ−{vr}+{va}) is replaced by m(vr|Dτ−{vr}). The following inequality is always verified:

The complexity gain provided by this approximation is significant. The number of margins to be computed is now of order |D| instead of |Ω−D|×|D|. Using this approximation, we can derive a exchange margin M′exch(Va, vr) as follows:

Note that the exchange margin M′exch(va, vr) in (7) is not more than the actual exchange margin Mexch(Va, vr) in (5). If the approximated exchange margin M′exch(va, vr) is non-negative, the actual exchange margin Mexch(va, vr) is also non-negative. So a swap decided based on (7) cannot be a wrong one from the point of view of (5).

FIG. 3is a flow chart illustrating a procedure usable by block201to evaluate the margins m(va|Dτ) and m(vr|Dτ−{vr}) used in (7). InFIG. 3, it is assumed that one subset Dτ′of candidate directions is determined for each new input frame It+1received by the direction selection unit101. This assumption is valid for video deinterlacing or simple noise reduction (e.g. τ=t, τ′=t+1), or for frame rate doubling (τ=t−½, τ′=t+½). Generalization to frame rate conversion with a ratio other than 2 is straightforward (a procedure of the kind shown inFIG. 3is generally run for each new output frame to be generated; the above assumption just makes the explanation clearer because it means that the rate of the new output frames is the same as that of the input frames). With this assumption, we can drop the time indexes t−1, t and τ, τ′ due to the time recursion in the procedure. In addition, m(v) stands for m(vr|Dτ−{vr}) if the direction v (=vr) is in D (=Dτ) and may be removed, and for m(va|Dτ) if the direction v (=va) is in Ω−D and may be added to D. The margins m(v) are evaluated for all directions v in Ω by updating running sums that are set to zero at the initialization301of the procedure.

The procedure scans the pixels x of the frame arrays Itand It+1one by one, a first pixel x being selected in step302. A first loop310over the directions v of D is executed in order to update the running sums for the directions of D (=Dτ) regarding pixel x. This first loop is initialized in step311by taking a first direction v in D and setting a variable A to an arbitrarily large value (for example its maximum possible value). At the end of loop310, variable A will contain the value of Lx(D) defined in (2).

In each iteration of loop310(step312), the local cost Lx(v) for pixel x and direction v is obtained and loaded into variable L. In step312, block201can either compute Lx(v), for example according to one of the above-mentioned possibilities, or retrieve it from a memory if the costs Lx(v) were computed beforehand. A test313is performed to evaluate whether L is smaller than A. If L<A, the direction index v is stored in a variable u and a variable B receives the value A in step314. Then the value L is allocated to the variable A in step315. At the end of loop310, variable u will contain the index of the direction v of D which minimizes Lx(v), i.e.

and variable B will contain the second smallest value of Lx(v) for the directions v of D, i.e.

If L≧A in test313, the local cost is compared to B in test316. If A≦L<B (yes in test316), the variable B is updated with the value L in step317. If L≧B in test316, or after step315or317, the end-of-loop test318is performed to check if all the directions v of D have been scanned. If not, another direction v of D is selected in step319and the procedure returns to step312for another iteration of loop310.

When loop310is over, the margin m(u) of the direction u of Dτwhich minimizes the local cost at pixel x is updated by adding thereto the quantity B−A (step321). As far as pixel x is concerned, removing u from D would degrade the cost by that quantity while the margins for the other directions of D would remain unaffected.

The processing for pixel x is then continued by a second loop330over the possible directions v that are not in D, in order to update the running sums for the directions of Ω−D regarding pixel x.

This second loop is initialized in step331by taking a first direction v in Ω−D. In each iteration (step332), the local cost Lx(v) for pixel x and direction v is computed or retrieved to be loaded into variable L. A test333is then performed to evaluate whether L is smaller than A=Lx(D). If L<A, the margin m(v) for direction v is updated by adding thereto the quantity A−L (step334) in order to take into account the improvement of the cost function that would result from the addition of v into D regarding pixel x. If L≧A in test333, or after step334, the end-of-loop test335is performed to check if all the directions v of Ω−D have been scanned. If not, another direction v of Ω−D is selected in step336and the procedure returns to step332for another iteration of loop330.

When loop330is over, it is determined in test341if all pixels x of the relevant frame array have been scanned. If not, another pixel x of the array is selected in step342and the procedure returns to step311. The operation of block201regarding the current frame is over when test341shows that all the pixels have been processed.

For each new input frame It+1, block201thus outputs the margins m(v) for all directions v of Ω, i.e. removal margins for the directions of D and addition margins for the directions of Ω−D.

To initialize the procedure at the beginning of an input video sequence, the subset D can have an arbitrary content, or it can be determined with a coarse method over the first few frames. A correct subset will quickly be built due to the time recursion of the selection procedure.

A second approximation can be made to further reduce the complexity of block201. In this approximation, m(va|Dτ) is replaced by a modified margin m*(va|Dτ). As in (4), a modified margin m*(v|D) is a pixelwise sum:

of local modified margins m*x(v|D) defined as:m*x(v|D)=Lx(D)−Lx(v) if Lx(v)<Lx(Ω−{v}), i.e. when v is the best direction in Ω from the point of view of minimizing the cost function at pixel position x;m*x(v|D)=0 else.

With the first and second approximations, a modified exchange margin M*exch(va, vr) can be derived as follows:

Again, the modified exchange margin M*exch(Va, vr) is not more than the actual exchange margin Mexch(va, vr), because of (6) and because m*x(va|D)≦mx(va|D). So a swap decided based on (9) cannot be a wrong one from the point of view of (5).

The modified margins m*x(va|D) can be computed with less expensive computations or circuitry because, for each location x, at most one running sum corresponding to a single absolute best direction in Ω−D has to be updated, whereas with non-modified margins mx(va|D), the number of such winners is in the worst case (test333always positive inFIG. 3) equal to |Ω−D|. In implementations using hardwired ASIC or FPGA circuits, the impact on logic size is significant. For identical reasons, the impact on the worst-case execution time in a software implementation is also important.

With the second approximation, the procedure ofFIG. 3is modified by replacing loop330by a modified loop430illustrated inFIG. 4. Loop430is initialized in step431(replacing step331) by taking a first direction v in Ω−D and setting the value of A=Lx(D) for another variable A*. At the end of loop430, variable A* will contain the minimum of Lx(v) for all directions v in Ω, i.e. Lx(Ω).

In each iteration, the local cost Lx(v) for pixel x and direction vεΩ−D is computed or retrieved to be loaded into variable L in step432. A test433is then performed to evaluate whether L is smaller than A*. If L<A*, the above-mentioned variable u is updated to contain the direction index v, and the value L is allocated to the variable A* in step434. If L≧A* in test433, or after step434, the end-of-loop test435is performed to check if all the directions v of Ω−D have been scanned. If not, a further direction v of Ω−D is selected in step436and the procedure returns to step432for another iteration of loop430.

When loop430is over, the margin m(u) of the direction u of Ω which minimizes the local cost at pixel x is updated by adding thereto the quantity A−A* (step441). If uεD, step441changes nothing. If u≠D, adding u to D would reduce the cost function by A−A* as far as pixel x is concerned, while the margins for the other directions of Ω−D would remain unaffected.

The reduction of complexity results from the fact that the updating step441is performed out of the loop430. The downside of this simplification is some loss of accuracy for the less-than-optimal directions of Ω−D, but this is not such a significant problem in view of the time recursion of the procedure that will eventually reveal the directions actually relevant to the video sequence.

Various procedures can be applied by block202to arbitrate between the candidate directions v for which the margins m(v) were computed by block201.

In the simple example depicted inFIG. 5, block202selects the direction v of the subset D=Dτwhich has the lowest margin m(v) as computed by block201and which is thus the best candidate for exclusion from Dτ′(step501). It also selects the direction w of Ω−D which has the highest margin m(w), i.e. the best candidate for inclusion into Dτ′(step502). If m(w)>m(v) (test503), the exchange is done in step504: v is replaced by w in D so that Dτ′=Dτ−{v}+{w}. If m(w)≦m(v) in test503, there is no exchange: Dτ′=Dτ.

FIG. 6illustrates another approach in which block202can swap more than one pair of directions. In step601, the n directions v1, v2, . . . , vnof the subset D=Dτwhich have the lowest margins are selected and sorted with increasing margins: m(v1)≦m(v2)≦ . . . ≦m(vn). The number n can be any integer between 1 and |D|. In the case n=1, the procedure ofFIG. 6is the same as that ofFIG. 5. In step602, the direction w1, w2, . . . , wnof Ω−D which have the highest margins are also selected and sorted with decreasing margins: m(w1)≧m(w2)≧ . . . ≧m(wn). Then it is determined how many direction pairs can be swapped. For example, after initializing a loop index i (i=1) in step603, block202compares the margins m(wi) and m(vi) in test604. If direction wiof Ω−D is better than direction viof D, i.e. m(wi)>m(vi), the exchange is done in step605, wireplacing viin D, and then i is compared to n in test606. If i<n, not all the pairs have been checked and i is incremented in step607before checking the next pair in a new test604. The procedure is terminated when a test604reveals that m(wi)≦m(vi) for some i<n, or when i=n in test606. If n′ direction pairs are swapped (n′≦n), the updated direction subset is Dτ′=Dτ−{v1, . . . , vn′}+{w1, . . . , wn′}.

In an embodiment, when the directions of regularity are detected by unit102, only directions v that have a margin m(v) above a given threshold T are used. This is easily done once Dτ′has been determined by block202, by ignoring in the direction detection unit102the directions v of Dτ′such that m(v)<T.

Alternatively, the inclusion of new directions w of Ω−Dτinto Dτ′can be prevented when m(w) is below the threshold T. There are various ways of doing this. For example, if the procedure ofFIG. 6is used, the number n can be set as the largest integer in {1, 2, . . . , |D|} such that m(wi)>T for all indexes i such that 1≦i≦n.

The use of the threshold T helps to prune the set of candidate directions and to select a number of candidate directions that is adapted to the geometric complexity of the video, i.e. to select the sparsest set of directions suitable for the video.

FIGS. 7 and 8illustrate the results provided by an embodiment of the invention in a case where the video processing unit103performs interpolation and more particularly frame rate conversion with a ratio of 2 between the frame rates of the output and input video sequences.

The video sequence in this example is a horizontally scrolling caption with the text “Sweeet”.701and801denote the image at time t,703and803the image at time t+1 and702and802the synthesized image at time=τ′+½, with a mismatch inFIG. 7and with a correct interpolation in FIG.8. Between images701/801and703/803(times t and t+1), the whole text “Sweeet” has scrolled 10 pixels to the left. A possible cause for mismatch is that the text contains several times the letter “e” with a periodicity of 8 pixels, and the direction detection unit102might be mistaken by the first “e” at time t looking like another “e” in the next input image at time t+1, leading to artifacts as shown in702.

In the example ofFIGS. 7 and 8, the cost function used in unit101is centered, and Ω contains only directions v=(dx, dt) with dt=½. The cost for a direction v=(dx, dt) at location x and time τ′=t+½ is then, for example, Lx(v)=|It′−dt(x−dx)−Iτ′+dt(x+dx)|=|It(x−dx)−It+1(x+dx)| or preferably a windowed version of this cost, by convolution with a non-negative spatial window function g. Two directions of regularity can be found with a local measure on this sequence:

Once a direction v=(dx, ½) is detected by unit102for a pixel x at time τ′=t+½, the interpolation for frame rate conversion done in unit103may consist in computing Îτ′(x)=Ît+1/2(x)=[It(x−dx)+It+1(x+dx)]/2.

InFIG. 7, we assume that no sparse geometry is used, so that all directions in Ω are considered in the detection unit102. For some pixels between the first and the third “e” of the text, the detected direction may group the first “e” at time t with the second “e” at time t+1 (see the squares inFIG. 7) and the second “e” at time t with the third “e” at time t+1, leading to incorrect temporal interpolation. Reference702shows an incorrect image with an artifact resulting from this incorrect interpolation. A simple workaround consisting in mixing the interpolated values corresponding to both detected directions v(1), v(2)does not solve the problem either.

Using a sparse geometry Dτ′in unit101helps to overcome this problem. Indeed, if the subset Dτdoes not contain the direction

the margin of v(1)with respect to Dτ′will be high because only v(1)can account for the scrolling of the letters “S”, “w” and “t”. So v(1)will at some time τ′ enter Dτ′. This done, since v(1)is a possible direction of the video over all letters including all “e”s, the margin of

will become very low or even zero, because there is no region of the video where it is a possible direction of regularity and v(1)is not. As a result, the direction v(2)will be kept out of the set Dτ′so that it will not be taken into account in the detection unit102, or will be ignored because its margin is below a threshold T. The correct interpolation will be computed as depicted in802.

Note that the temporal interpolation can be done at times other than halfway between two original frames. For example, in applications to conversion between the 50 Hz and 60 Hz frame rate standards, interpolation is done at times τ′=t+h/6, where h is one of 1, 2, 3, 4 or 5. The loss function used in units101and102can then be adapted accordingly.

FIGS. 9-12are diagrams similar toFIGS. 7-8illustrating application of an embodiment of the invention to super-resolution video deinterlacing.

FIGS. 9-10show the same text “Sweeet” scrolling in an interlaced video format at the input of the apparatus. References901,1001,1101and1201show an even input field at time t−1, references903,1003,1103and1203show the next even input field at time t+1, and references902and1002show the intervening odd input field at time t. The purpose of deinterlacing is the compute the even lines at time t to synthesize a full progressive frame at time τ′=t containing both even and odd lines.

In the example ofFIGS. 9-12, the cost function used in unit101is centered, and Ω may contain only directions v=(dx1, dx2, dt) such that dt=1 and dx2is even. The cost for a direction v=(dx, dt) of Ω at location ξ=x=(x1, x2) and time τ′=t is then, for example, Lx(v)=|It−dt(x−dx)−It+dt(x+dx) or a windowed version of this cost. Several directions of regularity can be found a priori on this sequence, including v(1)=(dx1(1),dx2(1),dt(1))=(−5,0,1) and v(2)=(dx1(2),dx2(2),dt(2))=(−1,0,1).

Once a direction v=(dx, 1) is detected by unit102for a pixel x at time τ′=t, the interpolation for deinterlacing done in the processing unit103may consist in computing Îτ′(ξ)=Ît(x)=[It−1(x−dx)+It+1(x+dx)]/2.

InFIG. 11, we again assume that the selection unit101feeds all directions of Ω to the detection unit102without using a sparse geometry. The detection unit102cannot properly discriminate between directions v(1)=(−5,0,1) and v(2)=(−1,0,1) and the output can again display dislocation-type of artifacts as shown in1102.

FIG. 12illustrates the result of a better deinterlacing when only the direction v(1)=(−5,0,1) is retained in the sparse geometry by the selection unit101, the superfluous direction v(2)=(−1,0,1) being eliminated in the selection step of the analysis.

Alternatively, in a deinterlacing application, when computing pixels at time τ′=t, a direction can be computed between t−2 and t+2 using the value dt=2 in the directions of Ω, in order to account for directions with higher definition. This means that directions v=(dx, 1) and 2v=(2dx, 2) are used in the same way in the interpolation. Because of parity constraints of the interlaced source, corresponding loss functions |It−2(x−2dx)−It+2(x+2dx)| can be computed. If a direction 2v=(2dx, 2dt)=(2dx1, 2dx2, 2dt) is detected by unit102, the vertical coordinate dx2of to the half-direction v can be odd. This allows deinterlacing properly video sequences including half-pixel vertical speeds. If such a direction description is referred to in the direction selection and detection units101-102, the processing unit103may interpolate Îτ′(ξ) as:

The direction measure that is used can involve time steps of either dt=1 or dt=2. This corresponds to comparing various directions as well as different temporal offsets (1 or 2, or even more).

Another possibility in deinterlacing applications is to compute costs for directions where the fields are shot at irregularly spaced times, in addition to directions associated with fields shot at evenly spaced times. This is for example the case when the original source of the video contents is film converted to video using “telecine”. For example, in 2:2 telecine used in Europe, when 25 fps (frames per second) film is transferred to 50 fps video, each film frame is used to generate two video fields, so fields I0, I1, I2, I3are shot at respective times 0 s, 0 s, 2/50 s, 2/50 s, instead of times 0/50 s, 1/50 s, 2/50 s, 3/50 s for video-originating contents. Furthermore, a video signal can contain a mix of film-originating contents and video-originating contents, so this detection has to be made pixelwise. Specific local cost functions can be chosen for detecting whether for a given pixel, the video is film-originating and whether the field just before or just after originates from the same film frame. A configuration of the direction at each pixel is then one of the following:

where “film-before” means that at a given pixel location, the contents is film-originating, and the preceding field comes from the same film frame, so that missing pixels can be picked at the same location from the preceding field, where “film-after” means that at a given pixel location, the contents is film-originating, and the field after comes from same film frame, and where (video, v) means that at the current pixel location, the contents is video-originating, and the direction vector is v. This description exemplifies another case where the “direction” can be defined by a local descriptor more complex than a single 3D vector v. In this case, the “direction” is a symbol which is one of (film-before), (film-after), (video,v) where v is a vector.

In the case of super-resolution video noise reduction, the processing unit103ofFIG. 1computes for each target pixel ξ, τ its new value by using a directional averaging function Kvat ξ with:

where the sum runs over all pixels (x, t) of the input images in a vicinity of (ξ, τ), including the pixel (ξ, τ) itself if ξ=x, τ=t for some point (x, t) of the input grid, and Kvdepends on the local direction v=(dx,dt). In an exemplary embodiment, the averaging functions Kvare directional averaging functions along a direction v=(dx, dt). An example is the function:

In another embodiment, the video processing performed in the processing unit103receives a variable number of directions from the direction detection unit102. Each of these directions can be accompanied with a relevance measure. In the case where the number of directions is 0, a fallback interpolation function or averaging function can be used. In the case where the number of directions is larger than 1, the target pixel value can be computed by combining the pixel values computed with each interpolating or averaging function corresponding to each direction. This combination can be an averaging, a weighted averaging using the relevance measure, or a median, or a weighted median, or any other kind of method to combine these pixel values.

In another exemplary embodiment, the noise reduction processing along direction v=(dx, dt) can be any kind of known directional filtering, including infinite impulse response (IIR) filtering.

In another exemplary embodiment, the sparse geometry is used to enhance the type of processing disclosed in WO 2007/059795 A1 when the processed signal is a video signal. The directions (dx, dt) may then be limited to values of dt=1 and to integer values of dx. They can be used to construct a mapping between pixels of a frame at time t and pixels of a frame t+1: (x,t)(x+dx,t+1), and provide an embodiment for the first grouping estimation used in WO 2007/059795 A1.

In an embodiment of the direction selection unit101, the set Ω of candidate directions is partitioned into a plurality of subsets Ω1, . . . , ΩJ(J>1), and only one of the subsets Ω1, . . . , ΩJis considered by the direction selection unit101at each time τ′ to provide candidates to enter the subset of selected directions Dτ′. This is interesting when the set Ω is too large to be entirely scanned for candidates in every cycle τ′. For example, at a time when subset Ωjis considered (1≦j≦J), loop330inFIG. 3or430inFIG. 4is carried out for the directions v that are in Ω1but not in D.

In certain cases, it may be interesting, in addition to the selection of a global subset Dτ′for the whole image area, to split the image support into several windows Wp,qof pixels, for example defined as rectangular regions:

where h and w are respectively the height and the width (in pixels) of these windows, and the window indexes p, q are in the ranges 1≦p≦P, 1≦q≦Q. The total number of windows is P×Q. When P=Q=1, there is only one window consisting of the whole image area as described previously. For each direction v inside each window Wp,q, a margin mp,q(v|D) can be computed using a formula similar to (4), but with a sum spanning an image region limited to this window Wp,q:

Local subset of directions Dτ′,p,q⊂Dτ′can be computed using these margins. A third subset Dτ′,p,qof candidate directions is thus determined as a subset of the second subset Dτ′determined for the whole area of It+1, based on cost margins mp,q(v|D) computed for pixels of the window Wp,qin the input images Itand It+1. When the direction detection unit102measures a direction at a pixel ξ=x which is inside one of the windows Wp,q, only candidate directions from Dτ′,p,qare taken into account. This is helpful to increase the robustness of the detection to avoid bad directions. Referring again to the example depicted inFIGS. 7-12, the selection allows to eliminate a bad direction (−1, 0, ½) [or (−2, 0, 1)] and to only use the right direction (−5, 0, ½) [or (−10, 0, 1)]. If the scene is more complex and somewhere else in the picture an object happens to be exhibiting a direction of regularity (−1, 0, ½), this vector (−1, 0, ½) will be present in Dτ′, and the benefit of the selection made in unit101may be lost to properly handle the scrolling text. If the selection margins are recomputed on smaller windows Wp,q, the probability that such a window Wp,qincludes both the scrolling text and the object having the single direction of regularity (−1, 0, ½) will be much lower.

When using too small windows Wp,q(e.g., in the case ofFIGS. 7-12a region spanning only one or two “e”s), the selection may become difficult because on too small windows, it is not possible any more to discriminate between two different directions of regularity. A multiscale selection scheme can be devised to avoid this difficulty, by recursively splitting the image support into windows, and each window into sub-windows. For each window, the subset of directions is selected as a subset of the subset of directions that was selected for the parent region (whole image or higher-layer window). In the multiscale selection scheme, one or more of the windows Wp,qis further split into a plurality of sub-windows Wp,q,r,s, and for each sub-window a fourth subset Dτ′,p,q,r,sof candidate directions is determined as a subset of the third subset Dτ′,p,qdetermined for the window Wp,q, based on cost margins mp,q,r,s(v|D) computed for pixels of sub-window Wp,q,r,sin the input images Itand It+1:

The directions of regularity for pixels of sub-window Wp,q,r,sof the output image Îτ′are then detected from subset Dτ′,p,q,r,s, possibly after one or more iterations of the recursive splitting of the windows.

In some embodiments, the subset Dτ′of selected directions can be constrained to satisfy various criteria. For example:some particular directions (such as (0, 0, 1) typically) can be forced to permanently stay within Dτ′, regardless of the margin associated with these directions;the set of directions Ω can also be split into R clusters Ω(1), . . . , Ω(R), and a constraint can be enforced that for each cluster Ω(r)(1≦r≦R, R>1), only one or a limited number of directions is selected to be included into subset Dτ′.

The above-described embodiments may be implemented by means of software run by general-purpose microprocessors or digital signal processors, in which case the modules described above with reference toFIGS. 1-6are understood to be or form part of software modules or routines. It may also be implemented as a hardware component as illustrated inFIG. 13, for example in an application-specific integrated circuit (ASIC) or field-programmable gate array (FPGA) for interpolating a video stream, in addition to other video processing blocks1302,1304, before and/or after the video interpolation block1303. Alternatively, the video processing block1303may implement a noise reduction method as described above. In an exemplary embodiment, the video processing blocks1302,1303,1304are implemented in a single chip1301. The chip also has video input and output interfaces, and external RAM (random access memory) devices1305and1306as temporary storage required for the different video processing steps performed in1302,1303and1304. Other variants of this embodiment can be equally considered as part of the invention, with more complete video processing chips, or even system-on-chip devices including other functionalities. The hardware device can then be incorporated into various kinds of video apparatus.

While a detailed description of exemplary embodiments of the invention has been given above, various alternative, modifications, and equivalents will be apparent to those skilled in the art. Therefore the above description should not be taken as limiting the scope of the invention which is defined by the appended claims.