Image interpolation for motion/disparity compensation

The present invention claims priority from U.S. Appln No. 61/244,901 filed Sep. 23, 2009 which is incorporated herein by reference for all purposes.

The present invention relates to methods of image interpolation, and in particular to temporal interpolation for adjusting video frame rate, and/or to spatial interpolation for adjusting stereoscopic 3D effect.

When a motion picture needs to be transmitted or displayed at a frame rate different from an original frame rate of the motion picture, or when a perceived depth of a stereoscopic image pair needs to be adjusted, a need arises to “interpolate” between two images. The term “image interpolation” refers to obtaining an image displaying objects, the shape, size, brightness, color, and/or position of which is intermediate between those of corresponding objects of the two known images.

Temporal image interpolation is used in frame rate up-conversion to increase the number of displayed images per second in a video or film sequence. It creates a more smooth motion in the video or converts between different video and film frame rates that are used around the world. Frame rate up-conversion is also used in a low bit rate video transmission. In this case, the source video is temporally down-sampled to a low frame rate and transmitted at a low bit rate. At the receiver, the original frame rate is recovered using frame rate up-conversion.

View interpolation based on so called disparity compensation reconstructs intermediate views or images between the left-eye and right-eye views of a stereoscopic still image pair or video. It is used to create multi-view video, adjust perceptional depth, and guide graphic and text editing and integration in 3D video.

Motion-compensated or disparity-compensated interpolation creates new images by image interpolation along so called motion trajectories or disparity trajectories, respectively. The motion or disparity trajectories correspond to movement or displacement of individual objects or individual blocks of pixels in going from one image to another. The quality of thus created images depends on an accuracy of estimation of the motion or disparity trajectories, as well as on performance of image processing methods used to smooth or even out the transitions between objects or blocks of pixels that have been displaced along the motion or disparity trajectories. An array of vectors corresponding to motion or disparity trajectories of individual blocks of pixels in going from one image to another is commonly called a “motion field” or a “disparity map”.

Referring to FIG. 1 , a prior-art method of motion-compensated video frame interpolation between a first video frame 110 and a second video frame 130 is illustrated. The method includes steps of dividing the first video frame 110 into rectangular blocks 112 A, B, C . . . ; obtaining the motion field by estimating motion vectors 114 A, B, C . . . for each block 112 A, B, C . . . in going from the first video frame 110 to the second video frame 130 ; and creating an interpolated video frame 120 along the estimated motion vectors 114 A, B, C . . . . A special algorithm estimates the motion vectors 114 A, B, C . . . for each of the blocks 112 A, B, C . . . by searching the second video frame 130 for blocks 132 A, B, C . . . resembling as closely as possible the blocks 112 A, B, C . . . . Once the blocks 132 A, B, C . . . are found, the corresponding motion vectors 114 A, B, C . . . can be determined. In FIG. 1 , only the motion vector 114 C is shown entirely, for simplicity. After the motion vectors 114 A, B, C . . . for each of the blocks 112 A, B, C . . . of the first video frame 110 are estimated, the interpolated video frame 120 can be calculated by shifting the blocks 112 A, B, C . . . by a fraction of the corresponding motion vectors 114 A, B, C . . . , so as to obtain shifted blocks 122 A, B, C . . . . The magnitude of the fraction depends on the time separation (for frame rate up-conversion), or the spatial separation (for view interpolation), between the first video frame 110 and the interpolated video frame 120 . By way of example, if a video frame rate needs to be doubled, then the interpolated video frame 120 is interpolated “in the middle”, that is, the blocks 122 A, B, C . . . are shifted by one half of a shift represented by the motion vectors 114 A, B, C . . . .

A motion field formed by the motion vectors 114 A, B, C . . . is called unidirectional because all motion vectors 114 A, B, C . . . pass through the interpolated video frame 120 in one direction. The motion vectors 114 A, B, C . . . are associated with the blocks 112 A, B, C . . . that are contiguous in the first video frame 110 . After motion compensation, the blocks 122 A, B, C . . . may not be contiguous in the interpolated video frame 120 , which causes two problems.

The first problem is related to so called holes and overlaps. For example, an area 125 of the interpolated video frame 120 is an area of overlap of blocks 122 C and 122 B. In other words, pixels in the overlap area 125 have multiple motion vectors passing through them. Pixels in a hole area 127 have no motion vectors passing through them. The hole area 127 and the overlap area 125 can be created due to motion estimation errors, or they can be created due to so called occlusions. The term “occlusion” refers to the appearance of new objects and disappearance of existing objects when comparing the first video frame 110 and the second video frame 130 . By way of example, referring to FIGS. 2A and 2B , occlusions are illustrated by means of frontal and side views, respectively, of a head 200 of a fictitious cartoon character wearing goggles 202 . When the head 200 is turned sideways as shown in FIG. 2B , a profile of a nose 204 appears, while a frontal view of the nose disappears as shown at 208 . At the same time, one of the eyes also disappears, as shown at 206 . The areas 204 , 206 , and 208 are termed occluded areas. The motion vectors, not shown, in the occluded areas 204 , 206 , and 208 , could not be properly estimated, because to estimate a motion vector, a block similar to a block of the first video frame 110 has to be found in the second video frame 130 . The occluded areas 204 , 206 , and 208 are dissimilar in the first and the second video frames 110 and 130 ; therefore, the motion vectors for these areas cannot be properly estimated.

The second problem is the appearance of so called blocking artifacts. Referring back to FIG. 1 , a line 111 present in the first video frame 110 is broken at locations 121 in the intermediate video frame 120 as a result of the block-wise interpolation described above. Broken lines, and the blocking visual defects in general, are easily noticeable by a human vision system and therefore are highly detrimental.

A number of algorithms have been proposed to handle holes, overlaps, and blocking artifacts. In one approach, image and motion field segmentation is used. For example, Huang et al. in an article entitled “Motion-compensated interpolation for scan rate up-conversion,” Optical Engineering , vol. 35, No. 1, pp. 166-176, January 1996, incorporated herein by reference, disclose an approach based on image and motion field segmentation. In another approach, a depth order of objects is determined and used to handle overlaps. For example, Wang et al. in U.S. Pat. No. 6,625,333, incorporated herein by reference, disclose using the depth order to handle overlaps.

Benois-Pineau et al. in an article entitled “A new method for region-based depth ordering in a video sequence: application to frame interpolation,” Journal of Visual Communication and Image Representation , vol. 13, pp. 363-385, 2002, which is incorporated herein by reference, disclose a median filter to fill hole areas such as the hole area 127 in FIG. 1 . Bertalmio et al. in an article “Image inpainting,” Computer Graphics ( SIGGRAPG 2000), July 2000, pp. 417-424, which is incorporated herein by reference, disclose so called “image inpainting” to fill hole areas. Most of these algorithms are quite complex, because the overlaps and holes are usually irregular in shape and size.

To avoid the problems of holes and overlaps, a number of researchers have proposed to use so called bi-directional motion fields. Referring to FIG. 3 , a prior-art bi-directional motion field approach is illustrated by means of the first video frame 110 , second video frame 130 , and the interpolated video frame 120 . In the bi-directional motion field approach, the interpolated video frame 120 is created as an empty frame and is divided into the blocks 122 A, B, C . . . , which are initially empty. For each of the blocks 122 A, B, C . . . , two motion vectors are estimated, one corresponding to the shift of the blocks 122 A, B, C . . . relative to the blocks 112 A, B, C . . . of the first video frame 110 , and the other corresponding to the shift of the blocks 122 A, B, C . . . relative to the blocks 132 A, B, C . . . of the second video frame 130 . For example, for the block 122 C, two motion vectors are estimated, 301 C and 303 C. The first motion vector 301 C provides a magnitude and a direction of displacement of the corresponding block 112 C of the first video frame 110 relative to the block 122 C, and the second motion vector 303 C provides a magnitude and a direction of displacement of the corresponding block 132 C of the second video frame 130 relative to the block 122 C. When all these vectors are known, the blocks 122 A, B, C . . . can be filled with pixels from the blocks 112 A, B, C . . . from the first video frame 110 , shifted by corresponding motion vectors, as well as with pixels form the blocks 132 A, B, C . . . from the second video frame 130 , shifted by corresponding motion vectors. The pixel values transferred from the first video frame 110 and the second video frame 130 are then averaged using a weighted averaging method. The bi-directional motion field can be estimated using an algorithm disclosed by Choi et al. in an article entitled “New frame rate up-conversion using bi-directional motion estimation,” IEEE Trans. Consumer Electronics , vol. 46, No. 3, pp. 603-609, August 2000, which is incorporated herein by reference. Alternatively, the bi-directional motion field can be derived from a unidirectional motion field as disclosed by Castagno et al. in an article entitled “A method for motion adaptive frame rate up-conversion,” IEEE Trans. Circuits and Systems for Video Technology , vol. 6, No. 5, pp. 436-445, October 1996, which is incorporated herein by reference.

One apparent advantage of the bi-directional approach is that there is no need to handle holes and overlaps, since the blocks in the frame to be interpolated are contiguous. For the same reason, one can use overlapped block motion compensation (OBMC) disclosed by Kang et al. in an article entitled “Motion compensated frame rate up-conversion using extended bilateral motion estimation”, IEEE Trans. Consumer Electronics , vol. 53, No. 4, pp. 1759-1767, November 2007, which is incorporated herein by reference. The OBMC can be used to reduce blocking artifacts in the interpolated image 120 divided into the contiguous blocks 122 A, B, C . . . .

However, there are two essential performance problems associated with the bi-directional approach. The first problem is the difficulty to accurately estimate the bi-directional motion since the pixels within the block to be interpolated are not known. The second problem is the lack of information on occlusions. Occluded areas exist in only one of the two existing video frames 110 and 130 and, therefore, should be interpolated using only one of the video frames 110 and 130 .

The prior art is lacking a method of image interpolation that would provide fast and accurate image interpolation while reducing undesirable effects of holes, overlaps, and blocking artifacts in the interpolated image. Accordingly, it is an object of the invention to provide such a method.

In accordance with the invention there is provided a new unidirectional motion-compensated frame interpolation method that addresses the problems of blocking artifacts, overlaps, and holes. Unidirectional motion field provides more accurate estimation of motion trajectories and information on occlusions than a bi-directional motion field. To reduce the blocking artifacts and solve the problem of holes and overlaps associated with a unidirectional motion field, the individual blocks of pixels are expanded and weighted before applying the unidirectional motion field. To fill holes, a new directional hole interpolation method is used. The advantages of these methods are their simplicity and effectiveness.

In accordance with the invention there is provided a method for image interpolation between first and second images, comprising:

(a) dividing the first image into contiguous blocks of pixels; (b) obtaining a forward motion field from the first image to the second image, wherein the forward motion field includes a plurality of motion vectors, wherein each motion vector corresponds to a displacement of a particular one of the blocks of step (a) in going from the first image to the second image; (c) expanding boundaries of the blocks of step (a) for an overlap therebetween, and weighting pixel values of thus expanded blocks using a pre-defined weight matrix; (d) applying the forward motion field of step (b) to the pixel value weights of the expanded blocks of step (c), so as to obtain a two-dimensional matrix of cumulative pixel value weights for a first interpolated image; (e) applying the forward motion field of step (b) to the pixel values of the expanded blocks of step (c), so as to obtain a two-dimensional matrix of cumulative pixel values for the first interpolated image; and (f) computing the first interpolated image by dividing cumulative pixel values by corresponding cumulative pixel value weights for each pixel of the first interpolated image.

In one embodiment, the second image is also divided into contiguous blocks of pixels, and a second interpolated image is computed by performing steps (b) through (f) above using a backward motion field from the second image to the first image, wherein the backward motion field includes a plurality of motion vectors, wherein each motion vector corresponds to a displacement of a particular one of the blocks of the second image in going from the second image to the first image. Then, the first and the second interpolated images are combined, preferably using weighted averaging. As a result of combining the images, the hole areas are reduced.

In one embodiment of the invention, the first and the second images are represented by two-dimensional matrices F 1 (i,j) and F 2 (i,j), respectively, of pixel values;

wherein in step (d), the two-dimensional matrix of cumulative pixel value weights is obtained using the formula ω(i+τx B ,j+τy B )+=w(i−i 0 ,j−j 0 ); wherein in step (e), the two-dimensional matrix of cumulative pixel values is obtained using the formula ζ(i+τx B ,j+τy B )+=w(i−i 0 ,j−j 0 )[(1−τ)F 1 (i,j)+τF 2 (i+x B ,j+y B )]; and wherein in step (f), the first interpolated image is computed as

F f ⁡ ( i , j ) = { ζ ⁡ ( i , j ) / ω ⁡ ( i , j ) , if ⁢ ⁢ ω ⁡ ( i , j ) > 0 H f , otherwise ;

wherein i, j are pixel coordinates; i 0 , j 0 are pixel coordinates of a first pixel of an expanded block B E of the expanded blocks of step (c); += denotes accumulation over the expanded blocks of step (c); (x B , y B ) is a motion vector of the forward motion field of step (b), the motion vector (x B , y B ) corresponding to the expanded block B E ; τ is a separation between the first image and the first interpolated image divided by a separation between the first and the second images; H f is a constant corresponding to an undetermined pixel (a hole) in the first interpolated image F f (i,j); and w(x,y) is the pre-defined two-dimensional weight matrix of step (c).

Methods of the invention can be used for motion-compensated video frame interpolation, as well as for a view reconstruction and/or depth adjustment for a stereoscopic video.

The patent or application file contains at least one drawing executed in color. Copies of this patent or patent application publication with color drawing(s) will be provided by the Office upon request and payment of the necessary fee.

Exemplary embodiments will now be described in conjunction with the drawings, in which:

FIG. 1 is an exploded view of two images and an interpolated image therebetween formed using a prior-art unidirectional motion field;

FIGS. 2A and 2B are illustrations of occlusions in frontal and side views, respectively, of a head of a fictitious cartoon character wearing goggles;

FIG. 3 is an exploded view of two images and an interpolated image therebetween formed using a prior-art bi-directional motion field;

FIGS. 4A and 4B are plan views of unexpanded and expanded blocks of pixels, respectively, in original and interpolated images;

FIG. 5 is an exploded view of two images and corresponding forward and backward motion fields according to the invention;

FIG. 6 is a plan view of holes in a combined image before a directional interpolation of the invention is applied to fill the holes;

FIG. 7 is a block diagram of a preferred method of image interpolation according to the invention;

FIG. 8 is a bar graph comparing results of applying conventional method and a method of the invention to motion compensation to eight standard video sequences; and

FIGS. 9A and 9B are interpolated color images obtained using a method of the invention and a prior-art method, respectively.

While the present teachings are described in conjunction with various embodiments and examples, it is not intended that the present teachings be limited to such embodiments. On the contrary, the present teachings encompass various alternatives, modifications and equivalents, as will be appreciated by those of skill in the art.

Description of Methods of the Invention

As noted above, a method of image interpolation of the invention is based on unidirectional motion fields between first and second images. Referring to FIG. 4A , a first image 410 is divided into contiguous blocks 411 , 412 , 413 . . . of pixels. Then, a forward motion field 425 in going from the first image 410 to a second image, not shown, is obtained using any suitable method of prior art. The forward motion field 425 includes a plurality of motion vectors, not shown. Each motion vector corresponds to a displacement of a particular one of the blocks 411 , 412 , 413 . . . in going from the first image 410 to the second image, so as to obtain shifted blocks 421 , 422 , 423 . . . of an interpolated image 420 .

In accordance with the invention, boundaries of the blocks 411 , 412 , 413 . . . are expanded for an overlap therebetween. Referring now to FIG. 4B , expanded blocks 411 E, 412 E, 413 E . . . of the first image 410 are shown in dashed, dotted, and dashed-double-dotted lines, respectively. Each pixel of each of the expanded blocks 411 E, 412 E, 413 E . . . is weighted in dependence upon a position of the pixel in the block, using a pre-defined weight matrix having a size of the expanded blocks 411 E, 412 E, 413 E . . . of pixels. Then, the forward motion field 425 is applied to the expanded blocks 411 E, 412 E, 413 E . . . , so as to obtain shifted expanded blocks 421 E, 422 E, 423 E . . . shown in dashed, dotted, and dashed-double-dotted lines, respectively. Pixel value weights are accumulated in the interpolated image 420 , so as to obtain a two-dimensional matrix of the accumulated pixel value weights. The two-dimensional matrix of weights has the same size as the interpolated image 420 .

At a next step, the forward motion field 425 is applied to the pixel values of the expanded blocks 411 E, 412 E, 413 E . . . , so as to obtain a two-dimensional matrix of cumulative pixel values for the interpolated image 420 . The two-dimensional matrix of pixel values has the same size as the interpolated image 420 . Finally, the interpolated image 420 is computed by dividing cumulative pixel values by corresponding cumulative pixel value weights for each pixel of the interpolated image 420 . Dividing the cumulative pixel values by weights allows one to avoid bright spots in areas of multiple overlaps of the expanded blocks 421 E, 422 E, 423 E . . . , such as an area 440 , for example. The image interpolation obtained by applying a unidirectional motion field to expanded weighted blocks is termed herein “the irregular-grid expanded-block weighted motion compensation”, or IEWMC.

In one embodiment of the invention, the IEWMC procedure is performed twice, once in a forward direction from a first image to a second, and once in a backward direction, from the second image to the first. Turning to FIG. 5 , first and second images 510 and 530 are shown. The first image 510 corresponds to the first image 410 of FIG. 4B . The IEWMC in the forward direction is performed by dividing the first image 510 of FIG. 5 into blocks 511 and applying forward motion vectors 502 (only one forward motion vector 502 is shown). Similarly, to perform the IEWMC in the backward direction, the second image 530 is divided into blocks 531 and the IEWMC procedure is repeated using a backward motion field from the second image 530 to the first image 510 . The backward motion field includes a plurality of motion vectors, such as a backward motion vector 504 , for example. Each backward motion vector corresponds to a displacement of a particular one of the expanded blocks, not shown, of the second image 530 in going from the second image 530 to the first image 510 .

The forward and backward-interpolated images are then combined into a single interpolated image. Preferably, a weighted averaging is used to combine the images. Pixel values of the forward-interpolated image are weighted in dependence upon a difference between corresponding pixel values of the second image 530 and an image obtained by applying the forward motion field to the first image 510 all the way to the second image 530 . Similarly, pixel values of the backward-interpolated image are weighted in dependence upon a difference between corresponding pixel values of the first image 510 and an image obtained by applying the backward motion field to the second image 530 all the way to the first image 510 .

As noted above, using unidirectional motion fields can result in appearance of holes and overlaps. Using expanded weighted blocks, such as the expanded weighted blocks 411 E, 412 E, 413 E . . . of FIG. 4B , results in considerable reduction of number and magnitude of these defects. Occasionally, holes can be formed even when the expanded weighted blocks 411 E, 412 E, 413 E . . . are used. When the forward-interpolated image includes a hole having at least one undetermined pixel, the combined interpolated image can use non-hole pixels of the backward-interpolated image to fill the hole. When both forward-interpolated and backward-interpolated images have holes at the same location, the combined interpolated image will have a hole at that location, as well.

When the combined interpolated image has a hole, that hole can be filled using values of pixels disposed outside the hole. Prior-art methods rely on extensive averaging or smoothing to fill holes. These methods result in appearance of blurred areas in the interpolated image at location of the holes. According to the invention, the holes can be filled by performing a block-wise directional hole interpolation.

Referring to FIG. 6 , a combined interpolated image 600 is shown. The combined interpolated image 600 has pixels 602 having determined values and pixels 604 having undetermined values. The undetermined pixels 604 form an area of a hole 606 .

At a first step of directional interpolation, the combined interpolated image is divided into contiguous hole interpolation blocks, such as a hole interpolation block 608 including the hole 606 . The hole interpolation blocks are not necessarily of the same size as the size of the blocks 511 used in the image interpolation.

At a second step, averages of absolute differences between values of adjacent pixels 602 A and 602 B disposed along first and second mutually orthogonal horizontal and vertical lines 611 and 612 , respectfully, are calculated. The mutually orthogonal lines 611 and 612 cross at a pixel 620 disposed within the hole 606 . The adjacent pixels 602 A and 602 B are disposed within or no more than two pixels away from the hole interpolation block 608 and outside the hole 606 .

At a third step, pixels of the hole 606 are assigned values derived from the values of the pixels 602 around the hole 606 . For example, the pixel 620 , disposed at the crossing of the mutually orthogonal lines 611 and 612 , is assigned a value derived from a value of at least one pixel 602 A or 602 B disposed on the mutually orthogonal lines 611 and 612 , respectively. The derived values are weighted by a reciprocal of the averages calculated in the second step above. The procedure is repeated for each remaining hole pixel 604 . Weighting the interpolated values by a reciprocal of the adjacent pixel value differences will ensure that the interpolation will not blur existing sharp edges. For example, if a sharp edge is present in the combined interpolated image 600 and is disposed along the horizontal line 611 , the adjacent pixels 602 B disposed along the vertical line 612 will have large difference in luminosity values. Accordingly, the pixels 602 B disposed along the vertical line 612 above and below the hole 606 will not contribute significantly to the hole pixels 606 , and the sharp horizontal edge along the horizontal line 611 will be preserved. Pixels P 1 and P 2 disposed on the horizontal line 611 on both sides of the hole 606 will contribute significantly to the interpolation.

To account for cases when the sharp edges are disposed diagonally, the averaging procedure can account for averaged values of pixels disposed along diagonal lines 625 and 627 . The diagonal lines 625 and 627 will be perpendicular to each other when the pixel spacing of the pixels 602 is the same in horizontal and vertical directions, as shown in FIG. 6 .

Referring now to FIG. 7 , a preferred method 700 of image interpolation of the invention includes the above described methods of IEWMC interpolation and block-wise directional hole interpolation. Specifically, the method 700 includes performing IEWMC interpolation 702 and 704 between images F 1 and F 2 in forward and backward directions using motion fields M f and M b , respectively; error-adaptive combination 706 of interpolated images F f and F b generated by the IEWMC interpolation steps 702 and 704 ; and block-wise directional, hole interpolation 708 of the resulting combined interpolated image F c to eliminate holes in the combined interpolated image F c , corresponding to the combined interpolated image 600 of FIG. 6 , and obtain the final interpolated image F.

Mathematical Illustration of Methods of Image Interpolation

Methods of image interpolation of the invention will now be illustrated by means of mathematical formulas defining the forward-interpolated image F f , the backward-interpolated image F b , the combined interpolated image F c , and the final interpolated image F.

A. Irregular-Grid Expanded-Block Weighted Motion-Compensation (IEWMC)

Application of IEWMC to computation of the forward-interpolated image F f will now be described. The forward-interpolated intermediate image F f is created using the forward motion field M f . Suppose that the normalized time separation between the first frame F 1 and the intermediate image F f is τ, and between F f and the second frame F 2 it is 1−τ. Let (i, j) stand for the spatial coordinates of a pixel and m B =(x, y) a motion vector associated with block B. The conventional unidirectional MCFI can be described as:

F f ( i+τx,j+τy )=(1−τ) F 1 ( i,j )+τ F 2 ( i+x,j+y ),for( i,j )∈ B   (1)

If the block is occluded, that is, the pixels within block B in the first frame F 1 have no correspondence in the second frame F 2 , then F f should be created using only F 1 :

F f ( i+τx,j+τy )= F 1 ( i,j ),for( i,j )∈ B   (2)

The interpolated pixels F f (i+τx, j+τy) resulting from the motion vector m B may overlap those resulting from other motion vectors, as illustrated at 440 in FIG. 4B . When this occurs, the conventional motion-compensation frame interpolation (MCFI) usually selects the interpolation value that has the smallest motion compensation difference |F 1 (i,j)−F 2 (i+x, j+y)|. A problem with this approach is that it leads to abrupt transitions between pixels resulting from one motion vector and those pixels from other motion vectors. These abrupt transitions may appear as blocking artifacts, such as the blocking artifacts 121 in FIG. 1 , which, as noted above, are very perceptible by the human visual system.

With the IEWMC, each block is expanded in four directions. For example, blocks of 4×4 pixels are expanded to blocks of 8×8 pixels. Referring back to FIG. 4B , three expanded blocks 421 E, 422 E, and 423 E are irregularly spaced because of motion compensation. Their locations in the interpolated frame 420 depend on their corresponding motion vectors. Within each expanded block 421 E, 422 E, and 423 E, the contribution of the motion compensation to the interpolated image is weighted by a pre-determined weighting matrix w(x, y) with a size equal to the size of each expanded block 421 E, 422 E, and 423 E. The value of a pixel in the interpolated image F f is a weighted average of all the contributions to that pixel. The weights in matrix w(x, y) vary with the spatial location within the expanded block 421 E, 422 E, or 423 E. Generally, the weights decrease from the largest value at the center of the matrix to a minimum value at the boundary. The weighted average results in a smooth transition between pixels. The following is an example integer weight matrix that is obtained using a bilinear function:

As the location of the expanded blocks 421 E, 422 E, and 423 E in the interpolated image depends on the corresponding motion vector, it is possible for any motion vector to contribute to a given pixel in the interpolated image 420 . Thus, to know the coefficients of the weighted average, the motion compensation from all the motion vectors has to be done. This is different from the conventional overlapped block motion compensation (OBMC), whereby the blocks in the interpolated image are regularly spaced and the coefficients of the weighted average are pre-defined. Since the coefficients of the weighted average are unknown until the motion compensations from all the motion vectors have been done, the IEWMC has to be performed in two passes. In the first pass, the motion compensation is carried out block by block and the weights of the motion compensations for each interpolated pixel are accumulated. The second pass normalizes the motion compensations for every interpolated pixel. A weighted average E f (i, j) of the motion compensation differences is also computed; it can be used in the error-adaptive combination step 706 of FIG. 7 . Accordingly, the IEWMC is implemented in the following three steps:

(i) Initialization: Initialize a memory for three images ζ(i,j), ω(i,j), and ε(i,j) for calculating the accumulations of the weighted motion compensations, the weights, and the weighted motion compensation differences, respectively. Set all pixels in these images to zero.

(ii) Accumulations: Compute the motion compensations using one motion vector after another, multiply the motion compensations with the corresponding weights, and accumulate the weighted motion compensations, the weights, and the weighted motion compensation differences.

Again, let B E denote an expanded block, (i 0 ,j 0 ) the spatial position of the first pixel (that is, the pixel at the upper-left corner) within the block B E , (x B , y B ) the motion vector associated with B E , and τ the normalized time separation between frames F 1 and F f . The accumulations can be represented as follows:

ζ( i+τx B ,j+τy B )+= w ( i−i 0 ,j−j 0 )[(1−τ) F 1 ( i,j )+τ F 2 ( i+x B ,j+y B )]  (3)

ε( i+τx B ,j+τy B )+= w ( i−i 0 ,j−j 0 )| F 1 ( i,j )− F 2 ( i+x B ,j+y B )|  (4)

ω( i+τx B ,j+τ B )+= w ( i−i 0 ,j−j 0 )  (5)

where (i, j)∈B E and the symbol += means that the value calculated on the right-hand side of an equation is added to the value on the left-hand side of the equation. This symbol is used in some computer programming languages, such as C and C++. If a block is occluded, Equation (3) changes to:

ζ( i+τx B ,j+τy B )+= w ( i−i 0 ,j−j 0 ) F 1 ( i,j )  (6)

This is the first pass of the IEWMC, carried out from the first motion vector to the last motion vector. At the end of this pass, ζ(i,j) is the sum of the weighted motion compensations with all the motion vectors that contribute to the pixel at (i,j) through expanded blocks. ε(i,j) is the sum of the weighted motion compensation differences, and ω(i,j) is the sum of the weights.

(iii) Normalization: Since the sum ω(i,j) of the weights for a pixel may not be the same, the sums ζ(i,j) and ε(i,j) calculated in step (ii) need to be normalized to obtain the interpolated image F f (i,j) and the weighted average E f (i,j) of the motion compensation differences. This is the second pass of the IEWMC, carried out one pixel after another as follows:

F f ⁡ ( i , j ) = { ζ ⁡ ( i , j ) / ω ⁡ ( i , j ) , if ⁢ ⁢ ω ⁡ ( i , j ) > 0 H , otherwise ( 7 ) E f ⁡ ( i , j ) = ɛ ⁡ ( i , j ) / ω ⁢ ( i , j ) , if ⁢ ⁢ ω ⁢ ( i , j ) > 0 ( 8 )

where H is a constant indicating that the pixels are within holes. If coli, ω(i,j)=0, motion compensation does not contribute to the pixel at (i, j). This pixel is deemed to be inside a hole caused by occlusion or by a motion estimation error.

B. Error Adaptive Combination

The intermediate images F f and F b are combined into one image F c to reduce the area of the holes and increase the image quality. F b and E b are calculated following the process described in the previous subsection, except that the backward motion field M b is used and, therefore, Equations (3)-(6) change accordingly.

Generally, the quality of F f (i, j) and F b (i, j) in the areas other than the holes can be roughly measured by the normalized motion compensation differences E f (i, j) and E b (i, j), respectively. Thus, the combination of F f (i, j) and F b (i, j) should be based on the values of E f (i, j) and E b (i, j). Based on experimental results with a large number of video sequences, the following error-adaptive combination provides the best image quality:

F c ⁡ ( i , j ) = { E b ⁡ ( i , j ) + α E f ⁡ ( i , j ) + E b ⁡ ( i , j ) + 2 ⁢ α ⁢ F f ⁡ ( i , j ) + E f ⁢ ( i , j ) + α E f ⁡ ( i , j ) + E b ⁡ ( i , j ) + 2 ⁢ α ⁢ F b ⁡ ( i , j ) , if ⁢ ⁢ F f ⁡ ( i , j ) ≠ H ⁢ ⁢ and ⁢ ⁢ F b ⁡ ( i , j ) ≠ H F f ⁡ ( i , j ) , if ⁢ ⁢ F f ⁡ ( i , j ) ≠ H ⁢ ⁢ and ⁢ ⁢ F b ⁡ ( i , j ) = H F b ⁡ ( i , j ) , if ⁢ ⁢ F f ⁡ ( i , j ) = H ⁢ ⁢ and ⁢ ⁢ F b ⁡ ( i , j ) ≠ H H otherwise

wherein the first line on the right-hand side is a weighted average of the two pixels from F f (i, j) and F b (i, j). The weights are determined by the normalized motion compensation differences E f (i, j) and E b (i, j). a is an empirically selected pre-determined parameter used to smooth the weights and to avoid the combination being too sensitive to small values of E f (i, j) or E b (i, j). In our experiments, a is set to 8.

C. Block-Wise Directional Hole Interpolation

After the error-adaptive combination, image F c (i, j) may still contain holes that need to be filled, as designated by pixels with an assigned value of H. The undetermined pixels in the holes cannot be interpolated using motion compensation because the motion for these pixels is not available. These pixels should be constructed using the spatial information provided by the interpolated pixels around the holes. Benois-Pineau et al. in the abovementioned article “A new method for region-based depth ordering in a video sequence: application to frame interpolation” discloses a median filter repeatedly applied to the undetermined pixels until all holes were filled. Wang et al. in the abovementioned U.S. Pat. No. 6,625,333 discloses linear spatial interpolations used to fill the holes. These methods have the following two shortcomings. First, they are not well suited for hardware implementation and real-time applications, although they are easily implemented in software. The shape and size of the holes are arbitrary and depend on the image content and motion. The number of calculations required to fill the holes varies with the shape and size of the holes. The second shortcoming is that these methods do not take into account the local orientation of the edges and textures in the image and, therefore, make the filled areas blurry.

The basic idea behind the block-wise directional hole interpolation (BDHI) method of the invention is to divide F c into blocks, analyze the orientation of the edges and texture within each block, and interpolate the holes block by block according to the orientation.

Specifically, in the BDHI method, the image F c is divided into blocks of size N×N. This size is not necessarily the same as a block size used for motion estimation. In the BDHI method, the blocks are examined one by one in the scanning order. Referring again to FIG. 6 , for each block 608 that contains the undetermined pixels 604 , averages of the absolute differences between adjacent interpolated pixels 602 A and 602 B in each of the horizontal and vertical directions represented by lines 611 and 612 , respectively, and optionally the two diagonal directions indicated by diagonal lines 625 and 627 within the block 608 , are calculated. For example, for the horizontal direction, the average value of |F c (i,j)−F c (i,j−1)| is calculated for all interpolated pixels within the block, excluding the undetermined pixels. The four average absolute differences, denoted by a h , a v , a d , and a r respectively, are used to represent the sharpness of the edges and the variation of the texture in these directions. If there are too few interpolated pixels within the block, the pixels in the two rows above the block and those in the two columns on the left of the block are included in the calculation of the absolute differences. In general, a large average absolute difference in a given direction indicates that there are sharp edges crossing this direction. As noted above, to preserve sharp edges in the image 600 , pixels crossing sharp edges should have little effect on the interpolation of the undetermined pixels, whereas pixels along edges should have a strong effect on the interpolation.

For each undetermined pixel 604 within the block 608 , the BDHI method then carries out the linear interpolations p h , p v , p d , and p r in the horizontal, vertical, and the two diagonal directions shown by the horizontal, vertical, and two diagonal lines 611 , 612 , 625 , and 627 in FIG. 6 . Each of the linear interpolations uses the two closest interpolated pixels that are on the line in the corresponding direction. For example, the linear interpolation p h in the horizontal direction uses the two interpolated pixels P 1 and P 2 in the same row as the undetermined pixel 620 , as shown FIG. 6 . One pixel P 1 is on the left side of the undetermined pixel, while the other pixel P 2 is the other on the right side. Let d 1 denote the spatial separation between P 1 and the undetermined pixel 620 , and d 2 that between P 2 and the undetermined pixel 620 . Then p h is computed as:

If both P 1 and P 2 do not exist, the corresponding interpolation is not performed. It should be noted that P 1 and P 2 are limited to be within the block, on the row above the block, or on the column on the left of the block in order to reduce the computation complexity and to better exploit the local edge orientation.

After the linear interpolations, the BDHI method calculates the weighted average of the two interpolations p h and p v , or all four interpolations p h , p v , p d , and p r and assigns it to the undetermined pixel 620 . As discussed above, the weights are proportional to the reciprocals of the average absolute differences a h , a v , a d , and a r . With these weights, the interpolation in the direction that does not cross edges has a larger effect than that in the direction that crosses sharp edges. Therefore, the undetermined pixel is filled with the following value:

The BDHI method has two advantages that come from its “block-wise” and “directional” attributes. The first advantage is that large holes of arbitrary size and shape are divided into small blocks of known size and shape. Thus, the number of the required calculations is reduced and easy to control. The second advantage is that the information on local edges and texture can be extracted and used in the interpolation to get better image quality.

The above described methods of unidirectional motion-compensated frame interpolation were compared to existing methods by performing image interpolation of standard videos that are widely used in image processing experiments. These are Flower Garden, Mobile & Calendar, Foreman, Football, Bicycle, Coast Guard, Ferris Wheel, and Table Tennis. The first four test sequences have a spatial resolution of 352×288 pixels, while the last four have a spatial resolution of 352×240 pixels. All the test sequences have a frame rate of 30 frames per second and each of them consists of 101 frames. To quantitatively measure the quality of the interpolated images, the 50 odd frames were removed and 50 new odd frames were interpolated from the 51 even frames. Then, the average peak signal-to-noise ratio (PSNR) of the interpolated frames with respect to the original odd frames has been computed.

Experimental Results

The performance of the IEWMC method of the invention has been compared with the performance of a conventional unidirectional motion-compensated frame interpolation (MCFI) of FIG. 1 . The performance of the BDHI method of the invention has been compared with the performance of the repeated median filter method used by Benois-Pineau et al. in the abovementioned article “A new method for region-based depth ordering in a video sequence: application to frame interpolation”. Referring now to FIG. 8 , the average PSNR of the interpolated frames obtained using the proposed IEWMC method, and the conventional MCFI, are displayed at 802 and 804 , respectively. Results in FIG. 8 indicate that the IEWMC method of the invention outperforms the conventional MCFI method for all eight test sequences. The average PSNR over all the sequences obtained using the IEWMC is 0.3 dB higher than that obtained using the conventional MCFI. The IEWMC generally produces smoother images. In contrast, the conventional MCFI may create sharp transitions and blocking artifacts to which the human visual perception is very sensitive. Referring now to FIG. 9 , this difference is illustrated using a portion of a frame from the sequence Table Tennis. In the area 902 between the arms, this difference is clearly seen.

After the IEWMC and error-adaptive combination, there are still holes, but in only two of the eight test sequences: Football and Table Tennis. The IEWMC method significantly reduces the hole areas, as compared with the conventional MCFI. The total hole area is reduced from 31,150 pixels to 2,418 pixels for Football and from 2,244 pixels to 60 pixels for Table Tennis. To fill these holes, comparative tests were done using the BDHI method of the invention and the repeated median filter.

The median filter is repeatedly applied to the interpolated frames until all the holes are filled. The support of the median filter is a square of 5×5 pixels. For each undetermined pixel, the median filter searches for the median value of the interpolated pixels within the support and assigns it to the undetermined pixel. If all the support falls within a hole, the undetermined pixel will be determined in the next repeated filtering process. For Football, the median filtering was repeated as many as 6 times to fill all the holes for one frame.

Table I below reports the PSNR of the filled pixels. The proposed BDHI results in PSNR values that are higher than those obtained with the median filter, specifically, 1.28 dB higher for Football and 0.41 dB higher for Table Tennis.

To evaluate the performance of the new methods in the context of motion-compensated frame up-conversion (MC-FRUC), three existing MC-FRUC methods were used as a benchmark: a typical bi-directional method illustrated in FIG. 3 , an object-based algorithm disclosed by Wang et al. in the abovementioned U.S. Pat. No. 6,625,333, and a commercial plug-in product, Twixtor™ 4.5.11, available from “RE: Vision Effects” Inc, California, USA.

The first benchmark algorithm, a typical bi-directional MC-FRUC algorithm, utilizes bi-directional motion estimation and overlapped block motion compensation (OBMC). The bi-directional motion estimation test results were taken from the abovementioned article by Kang et al. entitled “Motion compensated frame rate up-conversion using extended bilateral motion estimation”. Kang et al. tested their bi-directional algorithm using four test sequences: Flower garden, Mobile, Foreman, and Football. The test conditions were the same. The test sequences had a spatial resolution of 352×288 pixels, a frame rate of 30 frames per second, and a length of 101 frames. The inventors first removed the 50 odd frames, interpolated 50 new odd frames in their place, and computed the average PSNR of the interpolated frames. As shown in Table II below, the average PSNR of the bi-directional MC-MRUC for the four test sequences are the same as those presented by Kang et al. The unidirectional MC-FRUC using the new methods of the invention provides PSNR gains of 1.44 dB for one test sequence and over 3 dB for the other three.

The second benchmark algorithm, the object-based MC-FRUC algorithm disclosed in the abovementioned U.S. Pat. No. 6,625,333, is based on image segmentation, object-based motion field processing, and a method for measuring motion reliability. From Table II, the MC-FRUC method of the invention outperforms this benchmark algorithm for all four test sequences. The average PSNR gain is 0.61 dB.

The last benchmark algorithm, Twixtor™ 4.5.11, is used as a plug-in to Adobe After Affects™ 6.5 available from Adobe Systems Inc., California, USA. Since Twixtor™ 4.5.11 works with video in RGB format, we have to convert the test sequences from YCrCb 4:2:0 format to RGB format and convert back after the frame rate conversion. The interpolated odd frames, therefore, include the distortion of the frame interpolation as well as that of the color format conversion. To exclude the distortion of the color format conversion from the PSNR calculation, the original odd frames also went through the same color format conversion. In addition, Twixtor™ is allowed to either interpolate or repeat frames, depending on a parameter called motion sensitivity. Twixtor was forced to interpolate every odd frame in the experiment. One can conclude from Table II that the MC-FRUC method of the invention performs better than Twixtor™ for all the four test sequences. The average PSNR gain is 1.01 dB.

The methods of the invention have been disclosed in the present application in the application to motion-compensated frame interpolation (MCFI) only by way of an example. The methods of the invention are equally applicable to other image interpolation tasks, such as disparity compensated stereoscopic view interpolation. In particular, the methods of the invention are usable for a view reconstruction and/or depth adjustment for a stereoscopic video.

The methods of the invention can be implemented using any suitable processor, including a field-programmable gate array (FPGA), a microprocessor, a computer, etc. The computer code implementation of the methods of the invention can be stored and/or transmitted using a suitable computer readable medium.