Method for motion compensated frame rate upsampling based on piecewise affine warping

• US 6,438,275 B1
• Filed: 04/21/1999
• Issued: 08/20/2002
• Est. Priority Date: 04/21/1999
• Status: Expired due to Fees

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Martins, Fernando C. M., Kasai, Arlene K.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Kassa, Yosef
• Application Number:
  US09/296,451
• Time in Patent Office: 1,217 Days
• Field of Search: 382/300, 382/295, 382/254, 382/275, 382/236, 382/252, 382/232, 382/299, 382/266, 382/269, 348/441, 348/537, 348/538, 345/606, 345/607, 345/610, 358/528, 358/428, 358/525, 708/290
• US Class Current: 382/300
• CPC Class Codes: H04N 19/132 Sampling, masking or truncation of coding units, e.g. adaptive resampling, frame skipping, frame interpolation or high-frequency transform coefficient masking
• CPC Class Codes: H04N 19/503 involving temporal prediction adaptive coding with adaptive selection between spatial and temporal predictive coding H04N19/107; adaptive coding with adaptive selection among a plurality of temporal predictive coding modes H04N19/109
• CPC Class Codes: H04N 19/537 Motion estimation other than block-based
• CPC Class Codes: H04N 19/54 using feature points or meshes
• CPC Class Codes: H04N 19/587 involving temporal sub-sampling or interpolation, e.g. decimation or subsequent interpolation of pictures in a video sequence
• CPC Class Codes: H04N 19/86 involving reduction of coding artifacts, e.g. of blockiness
• CPC Class Codes: H04N 7/014 involving the use of motion vectors motion estimation and compensation in video coding H04N19/51

Abstract

Interpolation of a new frame between a previous frame and a current frame of a video stream by motion compensated frame rate upsampling. The interpolation method includes identifying nodes and edges of objects such as triangles present in the previous frame, constructing a superimposed triangular mesh based on the identified nodes and edges, estimating displacement such nodes in the superimposed triangular mesh from the previous frame with respect to the current frame, and rendering the new frame based on the estimated displacement of nodes. Additionally, pixels of the previous frame and the current frame may be classified according to whether a pixel'"'"'s value has changed from the previous frame to the current frame. This classification may be used during rendering to reduce overall processing time. Pixel-based forward motion estimation may be used to estimate motion of pixels between the previous frame and the current frame and the estimated motion may be used in estimating node displacement.

Claims

1. A method of interpolating a new frame between a previous frame and a current frame of a video stream comprising:

classifying pixels of the previous frame and the current frame according to whether a pixel'"'"'s value has changed from the previous frame to the current frame;

identifying nodes and edges of triangles present in the previous frame;

constructing a superimposed triangular mesh of the previous frame from the identified nodes and edges using constrained Delaunay triangulation to preserve edge segments;

estimating displacement of nodes in the superimposed triangular mesh from the previous frame to the current frame; and

rendering the new frame based on the estimated displacement of nodes.

2. The method of claim 1, further comprising copying a plurality of pixels of a triangle from the previous frame to the new frame when a predetermined percentage of the triangle'"'"'s pixels has not changed from the previous frame to the current frame.

3. The method of claim 1, further comprising rendering a plurality of new frames without repeatedly performing the identifying, constructing, and estimating actions.

4. The method of claim 1, further comprising estimating motion of pixels between the previous frame and the current frame and using the estimated motion in estimating node displacement.

5. The method of claim 4, wherein the motion estimation comprises a forward motion estimation.

6. The method of claim 5, wherein the motion estimation comprises a forward motion estimation with a weighted spiral search feature.

7. The method of claim 1, wherein rendering comprises rendering the new frame via image warping using scaled versions of estimated displacement vectors for nodes.

8. The method of claim 1, wherein identifying nodes comprises identifying nodes such that the resulting superimposed triangular mesh tessellates the previous frame into edge segments wherein each edge segment belongs to a single object of a scene represented by the previous frame.

9. The method of claim 1, further comprising inserting nodes periodically, before constructing the superimposed triangular mesh, in non-traced areas to fill in areas without nodes, thereby avoiding generation of triangles causing artifacts during estimating displacement of nodes.

10. An article comprising a machine readable medium having a plurality of machine readable instructions, wherein when the instructions are executed by a processor the instructions interpolate a new frame between a previous frame and a current frame of a video stream by classifying pixels of the previous frame and the current frame according to whether a pixel'"'"'s value has changed from the previous frame to the current frame, by identifying nodes and edges of triangles present in the previous frame, by constructing a superimposed triangular mesh of the previous frame from the identified nodes and edges using constrained Delaunay triangulation to preserve edge segments, by estimating displacement of nodes in the superimposed triangular mesh from the previous frame to the current frame, and by rendering the new frame based on the estimated displacement of nodes.

11. The article of claim 10, further comprising instructions for copying a plurality of pixels of a triangle from the previous frame to the new frame when a predetermined percentage of the triangle'"'"'s pixels has not changed from the previous frame to the current frame.

12. The article of claim 10, further comprising instruction for rendering a plurality of new frames without repeatedly performing the identifying, constructing, and estimating actions.

13. The article of claim 10, further comprising instructions for estimating motion of pixels between the previous frame and the current frame and using the estimated motion in estimating node displacement.

14. The article of claim 13, wherein the motion estimation comprises a forward motion estimation.

15. The article of claim 14, wherein the motion estimation instructions comprise instructions for forward motion estimation with a weighted spiral search feature.

16. The article of claim 10, wherein instructions for rendering comprises instructions for rendering the new frame via image warping using scaled versions of estimated displacement vectors for nodes.

17. The article of claim 10, wherein instructions for identifying nodes comprise instructions for identifying nodes such that the resulting superimposed triangular mesh tessellates the previous frame into edge segments wherein each edge segment belongs to a single object of a scene represented by the previous frame.

18. The article of claim 10, further comprising instructions for inserting nodes periodically, before constructing the superimposed triangular mesh, in non-traced areas to fill in areas without nodes, thereby avoiding generation of triangles causing artifacts during estimating displacement of nodes.

19. An apparatus for frame rate upsampling based on a previous frame and a current frame of a video stream comprising:

a pixel classification component to classify pixels of the previous frame and the current frame according to whether a pixel'"'"'s value has changed from the previous frame to the current frame;

a node and edge identification component to identify nodes and edges of triangles present in the previous frame;

a triangulation component to construct a superimposed triangular mesh of the previous frame from the identified nodes and edges using constrained Delaunay triangulation to preserve edge segments;

a node displacement estimation component to estimate displacement of nodes in the superimposed triangular mesh from the previous frame to the current frame; and

a renderer to render the new frame based on the estimated displacement of nodes.

20. The apparatus of claim 19, further comprising a forward motion estimation component to estimate motion of pixels between the previous frame and the current frame.

21. The apparatus of claim 20, wherein the forward motion estimation component comprises motion estimation according to a weighted spiral search.

22. The apparatus of claim 19, wherein the renderer renders the new frame via image warping using scaled versions of estimated displacement vectors for nodes.

23. The apparatus of claim 19, wherein the node and edge identification component identifies nodes such that the resulting superimposed triangular mesh tessellates the previous frame into edge segments wherein each edge segment belongs to a single object of a scene represented by the previous frame.

24. The apparatus of claim 19, wherein the node and edge identification component inserts nodes periodically, before constructing the superimposed triangular mesh, in non-traced areas to fill in areas without nodes, thereby avoiding generation of triangles causing artifacts during estimating displacement of nodes.

25. A method of pixel-based frame rate upsampling using piece-wise affine warping comprising:

classifying pixels of a previous frame and a current frame of a video stream according to whether a pixel'"'"'s value has changed from the previous frame to the current frame;

forwardly estimating motion of pixels between the previous frame and the current frame;

identifying nodes and edges of triangles present in the previous frame;

constructing a superimposed triangular mesh of the previous frame from the identified nodes and edges using constrained Delaunay triangulation to preserve edge segments;

estimating displacement of nodes in the superimposed triangular mesh from the previous frame to the current frame based on the forward motion estimation; and

rendering an interpolated frame based on the estimated displacement of nodes.

26. The method of claim 25, wherein identifying nodes and edges comprises:

detecting edges in the previous frame;

thinning edges;

removing short edges from edge maps;

inserting nodes in the previous frame'"'"'s boundary;

tracing edges with a protected zone of demarcation; and

inserting nodes in non-protected areas of the previous frame.