Mesh based frame processing and applications

• US 20050249426A1
• Filed: 05/07/2004
• Published: 11/10/2005
• Est. Priority Date: 05/07/2004
• Status: Active Grant

• Current Assignee: Intelliview Technologies Inc.
• Original Assignee: University Technologies International, Inc.
• Inventors: Badawy, Wael
• Granted Patent: US 7,616,782 B2
• Time in Patent Office: Days
• US Class Current: 382/241
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/137 Motion inside a coding unit, e.g. average field, frame or block difference
• CPC Class Codes: H04N 19/176 the region being a block, e.g. a macroblock
• CPC Class Codes: H04N 19/20 using video object coding
• CPC Class Codes: H04N 19/527 Global motion vector estimation
• CPC Class Codes: H04N 19/54 using feature points or meshes
• CPC Class Codes: H04N 19/597 specially adapted for multi-view video sequence encoding
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

A method of processing sequential frames of data comprises repeating the following steps for successive frames of data: acquiring at least a reference frame containing data points and a current frame of data points; identifying a set of anchor points in the reference frame; assigning to each anchor point in the reference frame a respective motion vector that estimates the location of the anchor point in the current frame; defining polygons formed of anchor points in the reference frame, each polygon containing data points in the reference frame, each polygon and each data point contained within the polygon having a predicted location in the current frame based on the motion vectors assigned to anchor points in the polygon; for one or more polygons in the reference frame, adjusting the number of anchor points in the reference frame based on accuracy of the predicted locations of data points in the current frame; and if the number of anchor points is increased by addition of new anchor points, then assigning motion vectors to the new anchor points that estimate the location of the anchor points in the current frame.

Claims

1. A method of processing sequential frames of data, the method comprising repeating the following steps for successive frames of data:

acquiring at least a reference frame containing data points and a current frame of data points;

identifying a set of anchor points in the reference frame;

assigning to each anchor point in the reference frame a respective motion vector that estimates the location of the anchor point in the current frame;

defining polygons formed of anchor points in the reference frame, each polygon containing data points in the reference frame, each polygon and each data point contained within the polygon having a predicted location in the current frame based on the motion vectors assigned to anchor points in the polygon;

for one or more polygons in the reference frame, adjusting the number of anchor points in the reference frame based on accuracy of the predicted locations of data points in the current frame; and

if the number of anchor points is increased by addition of new anchor points, then assigning motion vectors to the new anchor points that estimate the location of the anchor points in the current frame.

2. The method of claim 1 in which the accuracy of the predicted location of the data points in the current frame is estimated by finding an error measure and comparing the error measure to an error measure threshold.

3. The method of claim 2 in which the error measure is a function of the difference between the predicted location of the data points in the current frame and the actual location of the data points in the current frame.

4. The method of claim 3 in which adjusting the number of anchor points comprises adding or removing a number of anchor points that depends on the magnitude of the error measure.

5. The method of claim 1 further comprising repeating the adjustment of the number of anchor points until accuracy of the predicted location is below an accuracy threshold.

6. The method of claim 1 further comprising repeating the adjustment of the number of anchor points until a stop measure based on anchor point density is achieved.

7. The method of claim 1 in which adjusting the number of anchor points in a polygon is based at least in part on accuracy of predicted locations of data points in neighboring polygons.

8. The method of claim 7 in which polygons are processed in a sequential order that tends to maximize the number of neighboring polygons already processed when any given polygon is processed.

9. The method of claim 1 in which processing of successive frames is stopped due to an artifact, and re-started with a carry-over of an anchor point distribution from a frame processed before the processing was stopped.

10. The method of claim 1 further comprising repeating the adjustment of the number of anchor points until a stop measure is achieved that is based on the number of repetitions of the adjustment of the number of anchor points.

11. The method of claim 1 carried out as part of a method of data compression.

12. The method of claim 1 carried out as part of a method of motion detection in successive frames of video data.

13. The method of claim 1 carried out as part of a method of object analysis in successive frames of video data.

14. The method of claim 13 in which the object analysis comprises object tracking or identification.

15. The method of claim 14 in which the method of object analysis comprises assigning tracking points to an object in the successive frames of video data.

16. The method of claim 15 in which at least three tracking points are assigned to the object.

17. The method of claim 16 further comprising finding motion vectors corresponding to the tracking points.

18. The method of claim 17 further comprising computing the velocity of the object from the motion vectors corresponding to the tracking points.

19. The method of claim 16 in which the tracking points are allocated around the boundary of the object.

20. The method of claim 1 carried out as part of a method of video surveillance.

37. Apparatus for carrying out the method of claim 1, the apparatus comprising a video camera for acquiring successive frames of data and a data processor for processing the successive frames of data.

21. A method of processing sequential frames of data, the method comprising repeating the following steps for successive frames of data:

acquiring at least a reference frame containing data points and a current frame of data points;

identifying a set of anchor points in the reference frame;

assigning to each anchor point in the reference frame a respective motion vector that estimates the location of the anchor point in the current frame;

defining polygons in the reference frame, each polygon being defined by at least four anchor points;

for one or more polygons in the reference frame, adjusting the number of anchor points in the reference frame; and

if the number of anchor points is increased by addition of new anchor points, then assigning motion vectors to the new anchor points that estimate the location of the anchor points in the current frame.

22. The method of claim 21 further comprising repeating the adjustment of the number of anchor points until a stop measure based on anchor point density is achieved.

23. The method of claim 21 in which processing of successive frames is stopped due to an artifact, and re-started with a carry-over of an anchor point distribution from a frame processed before the processing was stopped.

24. The method of claim 21 further comprising repeating the adjustment of the number of anchor points until a stop measure is achieved that is based on the number of repetitions of the adjustment of the number of anchor points.

25. The method of claim 21 carried out as part of a method of data compression.

26. The method of claim 21 carried out as part of a method of motion detection in successive frames of video data.

27. The method of claim 21 carried out as part of a method of object analysis in successive frames of video data.

28. The method of claim 27 in which the object analysis comprises object tracking or identification.

29. The method of claim 28 further comprising computing the velocity of the object.

30. The method of claim 21 carried out as part of a method of video surveillance.

38. Apparatus for carrying out the method of claim 21, the apparatus comprising a video camera for acquiring successive frames of data and a data processor for processing the successive frames of data.

31. A method of processing sequential frames of data, the method comprising repeating the following steps for successive frames of data:

acquiring at least a reference frame containing data points and a current frame of data points;

identifying a set of anchor points in the reference frame, where the distribution of anchor points is based on texture of the reference frame;

assigning to each anchor point in the reference frame a respective motion vector that estimates the location of the anchor point in the current frame;

defining polygons in the reference frame, each polygon being defined by anchor points;

assigning tracking points to at least one object in the reference frame, each object being formed by one or more polygons; and

analyzing the object using the tracking points.

32. The method of claim 31 in which analyzing the object comprises identifying the object.

33. The method of claim 32 in which the object is identified using the size of the object as defined by the tracking points.

34. The method of claim 31 in which analyzing the object comprises monitoring movement of the object.

35. The method of claim 34 further comprising computing the velocity of the object.

36. The method of claim 31 in which the tracking points are allocated around the boundary of the object.

39. Apparatus for carrying out the method of claim 31, the apparatus comprising a video camera for acquiring successive frames of data and a data processor for processing the successive frames of data.

40. A method of processing a frame of data, the method comprising the steps of:

dividing the frame of data into cells; and

processing the cells according to an order that preserves the proximity of the processed cells, such that neighboring cells are processed in close sequence to each other.

41. The method of claim 40 in which the order is a Z-order process.

42. The method of claim 40 in which the order is a Gilbert order.

43. The method of claim 40 in which the order is a Gray order.

44. A method of tracking an object across frames of data, the method comprising the steps of:

identifying a set of n tracking points on the object; and

through successive frames, following different combinations of the set of n tracking points to track the object while specific ones of the n tracking points are not usable for tracking.

45. A method of analyzing frames of data from a source of frames, the method comprising the steps of:

identifying objects in the frames of data, where the objects comprise patches of data having similar motion; and

identifying an unusual condition as occurring when the object size corresponds to the frame size.

46. The method of claim 45 in which a persistent unusual condition is identified as a weather event.

47. The method of claim 45 in which an oscillating movement of the object is identified as a shaking of the source of the frames.

48. A method of encoding a bit stream carrying a frame of data, the method comprising the steps of:

encoding a first portion of the frame of data using a first compression algorithm to generate a first code stream;

encoding a second portion of the frame of data using anchor points of a mesh, the anchor points having associated motion vectors to generate a second code stream; and

transmitting a bit stream containing the first code stream and the second code stream.

49. The method of claim 48 in which the first compression algorithm is a DCT algorithm.