Video compression system using a dense motion vector field and a triangular patch mesh overlay model

• US 5,654,771 A
• Filed: 05/23/1995
• Issued: 08/05/1997
• Est. Priority Date: 05/23/1995
• Status: Expired due to Fees

• Current Assignee: University of Rochester
• Original Assignee: University of Rochester
• Inventors: Altunbasak, Yucel, Bozdagi, Gozde, Tekalp, A. Murat
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): LIN, BRYAN T
• Application Number:
  US08/447,418
• Time in Patent Office: 805 Days
• Field of Search: 348/416, 348/413, 348/699, 348/402, 348/415, 348/409, 348/401, 348/400, 348/390, 348/384, 382/241, 382/243, 382/238, 382/236, 382/232
• US Class Current: 348/699
• CPC Class Codes: H04N 19/54 using feature points or meshes

Abstract

In a temporal sequence of digitized image frames of video signals, the spatial and temporal image gradients and the pixel-to-pixel motion vectors (dense motion vectors) are obtained between two consecutive image frames. A shape-adaptive triangular patch mesh model overlay is provided on the first image frame such that the location of node points of each patch is determined by the spatial image gradients of the first frame and the pixel-to-pixel motion vectors. A priority ranking of patches is established before determining the node point motion vectors. The node point motion vectors, representing the motion of each of the node points of the triangular mesh patches, are estimated by a linear least-squares solution to an affine transformation of the mesh overlay on the first frame into the second frame. Failure regions are identified and are revised in accordance with a data bit budget. All data are coded prior to transmission at a constant data bit rate by a sending unit to a receiving unit over a data link.

Claims

1. A data compression system in a sending unit for transmission at a constant data bit rate over a data link in accordance with a communication standard between said sending unit and a receiving unit of data of a temporal sequence of image frames of video signals in which each image frame is represented prior to data compression by a two-dimensional coordinate array of a number of digitized picture elements (pixels) wherein said sequence includes a temporally first image frame and at least a temporally second image frame, and frames having scene contents containing spatial gradients and also having regions displaced corresponding to motion of the scene content, the data compression system comprising:

means for computing a dense motion field of dense motion vectors on a pixel-by-pixel basis representing the values and directions of motion of said scene content of said temporally second image frame with respect to said temporally first image frame;

means for generating a two-dimensional model of a mesh overlay on said first image frame, said mesh model comprising a plurality of interconnected shape-adaptive triangular patches with each patch having node points with respectively associated node point coordinates, each of said patches being defined on said first image frame in accordance with mesh-generating constraints and spatial gradients and displaced frame differences;

means for assigning a designation to each one of said triangular patches in accordance with a patch-assigning constraint and to each one of the node points associated therewith;

means for estimating and thereby parameterizing the motion of each one of said node points of said triangular patches overlaid on said first image frame in response to said dense motion vectors, said node point motion being estimated in accordance with motion-estimating constraints by an application of a statistical solution to an affine transformation of said first image frame, whereby said dense motion vectors are data-compressed into estimated node point motion vectors having second coordinates associated therewith and wherein all estimated node point motion vectors together comprise a representation of a data-compressed estimated second image frame;

means for identifying failure regions (MF and UB) in said data-compressed estimated second image frame wherein a difference is computed between the pixel signal levels of the uncompressed second image frame and the data-compressed estimated second image frame in accordance with certain ones of failure-identifying constraints, whereby each failure region is defined as such rectangular coordinate array of pixels of said uncompressed second image frame which encloses the pixels within a failure region identified in said temporally second image frame;

means for establishing a bit budget for the data to be transmitted at said constant data bit rate by said sending unit to said receiving unit;

means for revising the failure regions defined by said failure regions identifying means in accordance with a revised failure-identifying constraint;

means for assigning a designation to each one of said failure regions and alternatively to each one of said revised failure regions;

means for coding the node designations of each one of said triangular patches of said mesh overlay model;

means for coding the pixel signal levels of pixels within each one of said rectangular coordinate array failure regions;

means for coding the node point motion vectors of said data-compressed estimated second image frame;

means for coding the pixel signal levels of all pixels of said temporally first image frame when said first frame is an original or new first frame; and

;

means for transmitting at a constant data bit rate from said sending unit over said data link to said receiving unit said coded pixel signal levels of said first image frame, said coded node point motion vectors, said coded pixel signal levels corresponding to said failure regions, and said coded node designations in accordance with said communication standard.

2. The data compression system of claim 1 wherein said statistical solution is a linear least squares solution.

3. The data compression system of claim 1, wherein said dense motion vector computing means comprises:

means using a 2-D motion field estimation algorithm to obtain said dense motion vectors for each pixel location.

4. The system of claim 1 further comprising means for decoding in said receiving unit said coded signals transmitted from said sending unit to form a temporal sequence of image frames of video signals for display, said sequence including at least said first and second image frames.

5. The data compression system of claim 1, wherein said mesh generating means comprises:

means for selecting a mesh-generating threshold level in accordance with one of said mesh-generating constraints, said coordinates of said node points of said triangular patches on said first image frame being defined by values of said spatial gradients exceeding said selected threshold level, and said displaced frame differences;

means for selecting a minimum coordinate distance which defines a closest distance between neighboring node points in accordance with another one of said mesh-generating constraints, said minimum coordinate distance being selected on the basis of said number of pixels contained in said two-dimensional coordinate array of pixels; and

means for identifying failure regions in said first frame and detecting the location of each one of said node points such that it does not fall within said failure regions.

6. The data compression system of claim 5, wherein said node point location detecting means further comprises:

means for modifying the location of node points detected to be located within a failure region.

7. The data compression system of claim 6, wherein said location modifying means comprises:

means for moving the location of said node points to a nearest pixel location outside of a BTBC failure region; and

means for generating new node points in MF and UB regions.

8. The data compression system of claim 1 further comprising:

means for obtaining the triangular patches using a Delauney triangulization algorithm; and

means for refining the patches using a split-and-merge algorithm.

9. The data compression system of claim 1, wherein said patch designation assigning means comprises:

means for rank ordering said triangular patches on the basis of the values and directions of said dense motion vectors obtained from said computing means and located within each patch in accordance with the following relationship, ##EQU9## where O_k is the rank order of a patch k

11. The data compression system of claim 1, wherein said motion estimating means comprises:

means for deriving the motion of each pixel within a triangular patch overlaid on said temporally first image frame to new coordinate locations in said estimated second image frame in accordance with the following relationships,

space="preserve" listing-type="equation">u.sub.j =x'"'"'.sub.j -x.sub.j =(a.sub.i1 -1)x.sub.j +a.sub.i2 y.sub.j +a.sub.i3

space="preserve" listing-type="equation">v.sub.j =y'"'"'.sub.j -y.sub.j =a.sub.i4 x.sub.j +(a.sub.i5 -1)y.sub.j +a.sub.i6

where

x_j, y_j are the coordinates of a pixel, j, within a patch i of the first image frame,

x_j, y'"'"'_j are the estimated coordinates of a matching pixel within the patch i of the estimated second image frame,

u_j, v_j are the estimated parametric vectors of the pixel j,

a_i1, . . . a_i6 are affine parameters for patch i,

and wherein u_j =(x'"'"'_j -x_j) and v_j =(y'"'"'_j -y_j) are flow constraints or estimates in accordance with said motion-estimating constraints;

means for determining an estimate of said node point motion vectors of the three node points of an ith triangular patch overlaid on said first image frame, in accordance with the following relationship, ##EQU11## where N_i is the number of estimated dense motion vectors within the first triangular patch, the relationship being minimized with respect to the affine parameters a_i1, . . . , a_i6 by an application of said solution in accordance with the following relationship, ##EQU12## where x₁, . . . , x_Ni and y₁, . . . , y_Ni

are the respective starting coordinates of all N_i dense motion vectors within the first triangular patch of the first image frame

where

x'"'"'₁, . . . , x'"'"'_Ni, and y'"'"'₁, . . . , y'"'"'_Ni are the respective ending coordinates of all N_i dense motion vectors within the first patch of the estimated second image frame

a_i1, . . . , a_i6 are the affine parameters,

and wherein the node point motion vectors of said three node points are included therein and can be extracted therefrom.

14. The data compression system of claim 11 wherein said motion estimating means further comprises:

means for preserving the connectivity among said plurality of interconnected shape-adaptive triangular patches of said mesh overlay model, wherein each node point common to adjoining triangular patches has one and the same node point motion vector in accordance with another one of said motion-estimating constraints, and wherein said means for preserving the connectivity uses a polyogonal boundary constraint.

15. The data compression system of claim 1, wherein said bit budget establishing means comprises:

means for counting as data bits the node point motion vectors; and

means for calculating a data bit rate fraction corresponding to said counted data bits, said fraction being calculated with respect to said constant data bit rate of the data to be transmitted.

16. The data compression system of claim 1, wherein said mesh-generating constraints include exclusion of failure regions (BTBC) in said first image frame which are identified by said dense motion vectors.

17. The data compression system of claim 15, wherein said MF and UB failure regions are in said second image frame.

18. The data compression system of claim 16, wherein said failure regions identifying means comprises:

means for selecting a first failure-identifying threshold level in accordance with said failure-identifying constraints, said failure regions (BTBC) being identified as regions where an absolute difference of pixel signal levels between the original and the coded first image frame is in excess of said first threshold level; and

means for selecting a second failure-identifying threshold level in accordance with said failure-identifying constraints, said MF and said UB being identified as a region where an absolute difference of pixel signals between the original uncompressed second image frame and said estimated second range is in excess of said second threshold level.

19. The data compression system of claim 17, wherein said failure region revising means comprises:

adaptive thresholding means for selecting a revised failure-identifying threshold level in accordance with a revised failure-identifying constraint, wherein said revised threshold is selected to approximate said constant data bit rate of the data to be transmitted from said sending unit to said receiving unit.

20. The data compression system of claim 18, wherein said failure region designation assigning means comprises:

means for determining the coordinates of a rectangular coordinate array of pixels of the uncompressed second image frame which encloses the pixels within said failure region identified in a corresponding polygonal patch overlaid on said estimated second image frame; and

means for partitioning said rectangular coordinate array into adjoining sub-array blocks.

21. The data compression system of claim 19, wherein said failure region pixel coding means comprises:

means for forming a discrete cosine transform (DCT) of the pixel signal levels of the pixels within each of said sub-array blocks, whereby DCT coefficients are obtained for each sub-array block;

means for quantizing said DCT coefficients;

means for determining by an entropy-determining means such number of DCT coefficients as are required to achieve said constant data bit rate of the data to be transmitted from said sending unit to said receiving unit;

means for selecting said required number of DCT coefficients;

means for performing an inverse quantization of said selected required number of DCT coefficients; and

means for computing a signal-to-noise ratio of said DCT coefficients of said failure regions.

22. The date compression system of claim 20, wherein said determining means further comprises:

means for detecting an upper and a lower limit value for a number of bits required to code the DCT coefficients;

means for adjusting said quantizing means whenever the number of bits is higher than said upper limit value; and

means for changing a next frame failure region threshold level whenever the number of bits is lower than said lower limit value.

23. The date compression system of claim 20, wherein said failure region pixel coding means further comprises:

means for computing a signal-to-noise ratio for the pixels within each one of said failure regions (MF and UB) and each one of the remaining regions;

means for detecting a different of said signal-to-noise between said failure regions and the remaining regions; and

means for changing a next frame failure region threshold level whenever said signal-to-noise ratio of said failure regions is lower than said signal-to-noise ratio of the remaining regions.

24. The data compression system of claim 18, wherein said failure region identifying means and alternatively said failure region revising means further comprises:

means for setting an upper limit value for an allowable number of failure regions as a fraction of all regions within said data-compressed estimated second image frame;

means for detecting said fraction of said allowable number of failure regions;

means for deciding that said estimated second image frame constitutes a new first image frame whenever said fraction of said allowable number of failure regions is higher than said upper limit value; and

means for resetting said node point estimating means, said mesh-generating means, and said patch designation assigning means to generate a new mesh for a new first image frame.

25. The data compression system of claim 1, wherein said node designation coding means comprises:

means for generating a binary code representative of each one of said node designations, including said node designations of said failure regions; and

means for entropy-coding said binary code node designations.

26. The data compression system of claim 1, wherein said note point motion vector coding means comprises:

means for predicting the value and direction of a node point motion vector at each node point on the basis of node point vectors having respective correspondence to an immediate predecessor node point motion vector and to node point motion vectors of spatially closest neighbor node points;

means for converting into a binary code the coordinates of said node point motion vector at each node point; and

means for entropy-coding said binary coded vector coordinates.

27. The data compression system of claim 1, wherein said first image frame pixel signal coding means comprises:

means for converting into a binary code the pixel signal levels of all pixels of said temporally first image frame; and

means for entropy-coding said binary coded pixel signal levels.

28. The data compression system of claim 1, wherein said bit budget establishing means comprises:

means for ascertaining an overall signal-to-noise ratio of the data compression system in accordance with the following relationship, ##EQU14## where PSNR is the peak signal-to-noise ratio

255is the maximum number of pixel signal levels representative of spatial image gradients of a scene content

MSD is the mean square difference of the estimated and original second frames.

29. The data compression system according to claim 1, wherein said pixels in each array has associated pixel signal levels corresponding to the contents of the scenes depicted by each of said frames, and wherein said sequence includes a temporally first frame and a temporally second frame having at least one pixel region displaced in correspondence with the motion of said scene content with respect to an identical pixel region of said first frame and further comprising:

means for storing temporarily the pixel signal levels of said first frame, means for determining the values and coordinate locations of said spatial gradients on a pixel-by-pixel basis within said first and second frames, and wherein said computing means further comprises means for computing the different between the pixel values of the spatial gradients at identical coordinate locations within said frames whereby to provide said dense motion vectors.

31. The data compression method of claim 29, wherein said dense motion vector computing step comprises:

selecting a two-dimensional (2-D) motion field estimation algorithm to obtain dense motion vectors for each pixel location.

33. The data compression method of claim 31, wherein said patch designation assigning step comprises:

rank ordering said triangular patches on the basis of the values and directions of said dense motion vectors obtained from said dense motion field computing step and located within each patch in accordance with the following relationship, ##EQU15## where O_k is the rank order of a patch k

36. The data compression method of claim 33, wherein said motion estimating step further comprises:

preserving the connectivity among said plurality of interconnected shape-adaptive triangular patches of said mesh overlay model, wherein each node point common to adjoining triangular patches has one and the same node point motion vector in accordance with another one of said motion-estimating constraints; and

preserving said connectivity by a polyogonal boundary constraint.

37. The data compression method of claim 29, further comprising the steps of:

obtaining the triangular patches by a Delauney triangulization algorithm; and

refining the patches by a split-and-merge algorithm.

38. The data compression method of claim 29, wherein said motion estimating step further comprises an alternative step of determining said estimated node point motion vectors of an ith triangular patch overload on said first image frame, in accordance with the following relationship, ##EQU19## where N_i is the number of pixels within the i-th triangular patch of said first image frame

I_x, I_y are the spatial gradients in respective x and y directions of said N_i pixels within the i-th patch of said first image frame

I_t is a temporal gradient within the i-th patch of the first image frame,

said relationship being minimized with respect to affine parameters a_i1, . . . , a_i6 by an application of a linear least squares solution to determine said estimated node point motion vectors.

39. The data compression method of claim 36, wherein said motion estimating step further comprises:

preserving the connectivity among said plurality of interconnected shape-adaptive triangular patches of said mesh overlay model, wherein each node point common to adjoining triangular patches has one and the same node point motion vector in accordance with an alternative motion-estimating constraint; and

preserving said connectivity by a polyogonal boundary constraint.

40. The data compression method of claim 29, wherein said bit budget establishing step comprises:

counting as data bits the node point motion vectors; and

calculating a data bit rate fraction corresponding to said counted data bits, said fraction being calculated with respect to said constant data bit rate of the data to be transmitted.

41. The data compression method of claim 38, further comprising the steps of:

ascertaining an overall signal-to-the ratio of the data compression method in accordance with the following relationship PSNR=10 log₁₀ (255² /MSD),

where

PSNR is the peak signal-to-noise ratio

255 is the maximum number of pixel signal levels representative of spatial image gradients of a scene content

MSD is the mean square difference of the estimated and original second image frames.

42. The data compression method of claim 29, wherein said failure region revising step comprises:

selecting a revised failure-identifying threshold level in accordance with said revised failure-identifying, wherein said revised threshold is selected to approximate said constant data bit rate of the data to be transmitted from said sending unit to said receiving unit.

43. The data compression method of claim 40, wherein said failure region revising step further comprises:

setting an upper limit value for an allowable number of failure regions as a fraction of all patches within said data-compressed estimated second image frame;

detecting said fraction of said allowable number of failure regions;

deciding that said estimated second image frame constitutes a new first image frame whenever said fraction of said allowable number of failure regions is higher than said upper limit value; and

resetting said node point estimating means, said mesh-generating means, and said patch designation assigning means to generate a new mesh for a new first image frame.

44. The data compression method of claim 40, wherein said failure region designation assigning step comprises:

determining the coordinates of a rectangular coordinate array of pixels of the uncompressed second image frame which encloses the pixels within the failure region identified in a corresponding polygonal patch overlaid on said estimated second image frame; and

partitioning said rectangular coordinate array into sub-array blocks of adjoining sub-arrays.

45. The data compression method of claim 42, wherein said node designation coding step further comprises:

generating a binary code representative of each one of said node designations, including the node designations of said failure regions; and

entropy-coding said binary code node designations.

46. The data compression method of claim 43, wherein the failure region pixel coding step comprises:

forming a discrete cosine transform (DCT) of the pixel signal levels of the pixels within each one of said sub-array blocks of rectangular coordinate arrays, whereby DCT coefficients are obtained for each of said sub-array blocks;

quantizing said DCT coefficients;

determining by an entropy-determining step such number of DCT coefficients as are required to achieve said constant data bit rate of the data to be transmitted from said sending unit to said receiving unit;

selecting said required number of DCT coefficients;

performing an inverse quantization of said selected required number of DCT coefficients; and

computing a signal-to-noise ratio of said DCT coefficients of said failure regions.

47. The data compression method of claim 44, wherein said node point motion vector coding step comprises:

predicting the value and direction of a node point motion vector at each node point on the basis of node point vectors having respective correspondence to an immediate predecessor node point motion vector and to node point motion vectors of spatially closest neighbor node points;

converting into a binary code the coordinates of said node point motion vector at each node point; and

entropy-coding said binary coded vector coordinates.

48. The data compression method of claim 45, wherein said first image frame pixel signal coding step comprises:

converting into a binary code the pixel signal levels of all pixels of said temporally first image frame; and

entropy-coding said binary coded pixel signal levels.

49. The date compression method of claim 44, wherein said determining step further comprises:

detecting an upper and a lower limit value for a number of bits required to code the DCT coefficients;

adjusting said quantizing means whenever the number of bits is higher than said upper limit value; and

changing a next frame failure region threshold level whenever the number of bits is lower than said lower limit value.

50. The data compression method of claim 44, wherein the failure region pixel coding step further comprises:

performing an inverse quantization of said selected required number of DCT coefficients;

computing a signal-to-noise ratio for the pixels within each one of said failure regions (MF and UB) and each one of the remaining regions;

detecting a difference of said signal-to-noise ratio between said failure regions and the remaining regions; and

changing a next frame failure region threshold level whenever said signal-to-noise ratio of said failure regions is lower than said signal-to-noise ratio of the remaining regions.

51. The data compression method of claim 29, wherein a receiving step in said receiving unit comprises the step of:

decoding the coded signals transmitted from said sending unit to form a temporal sequence of image frames of video signals for display, said sequence including at least said first and second image frames.

52. The data compression method of claim 29, wherein said mesh-generating step further comprises the steps of:

selecting the mesh-generating constraint to include exclusion of failure regions (BTBC) in the first image frame which are identified by the dense motion vectors.

53. The data compression method of claim 50, further comprising the step of:

designating MF and UB as the failure regions in the second image frame.

54. The date compression method of claim 51, wherein said failure regions identifying step comprises:

selecting a first failure-identifying threshold level in accordance with said failure-identifying constraint, said failure regions (BTBC) being identified as regions where an absolute difference of pixel signal levels between the original and the compressed first image frame, is in excess of said first threshold level; and

selecting a second failure-identifying threshold level in accordance with said failure-identifying constraint, said MF and said UB being identified as regions where an absolute difference of pixel signal levels between the original uncompressed second image frame and said estimated second image frame is in excess of said second threshold level.

55. The data compression method of claim 51, wherein said node point designation assigning step further comprises the steps of:

modifying the location of node points detected to be located within a failure region; and

selecting the initial node points on the boundary of BTBC.

56. The data compression method of claim 53, wherein said location modifying step comprises the steps of:

deleting said node points which are in BTBC, MF and UB; and

generating new node points in MF and UB.

57. The data compression method of claim 29 wherein said mesh generating step further comprises the step of:

arranging said plurality of interconnected triangular patches so as to form a common node point among one of the node points of each of the patches whereby remaining node points of each of the patches have node point coordinates defining a polygonal boundary.

58. The data compression method of claim 55 wherein said motion estimating step includes the steps of:

determining an estimate of the node point motion vector of the common node point wherein a least squares statistical solution is used to minimize a displaced frame difference over the patches defining the polygonal boundary; and

establishing motion constraints on the common node point and on the node points defining the polygonal boundary.

59. The data compression method of claim 29 wherein said dense motion computing step further includes the step of:

computing a displaced frame difference (DFD) when a plurality of pixel regions of the second image frame are displaced with respect to identical pixel regions of the first image frame.

61. The data compression system of claim 58, wherein said mesh-generating means comprises:

means for selecting a mesh-generating threshold level in accordance with one of said mesh-generating constraints, said coordinates of said node points of said triangular patches on said first image frame being defined by values of said spatial gradients exceeding said selected threshold level, and said displaced frame differences; and

means for selecting a minimum coordinate distance which defines a closest distance between neighboring node points in accordance with another one of said mesh-generating constraints, said minimum coordinate distance being selected on the basis of said number of pixels contained in said two-dimensional coordinate array of pixels.

62. The data compression system of claim 58, wherein said mesh-generating means further comprises:

means for arranging said plurality of interconnected triangular patches so as to form a common node point among one of the node points of each of the patches whereby remaining node points of each of the patches have node point coordinates defining a polygonal boundary.

63. The data compression system of claim 58 further comprising:

means for obtaining the triangular patches using a Delauney triangulization algorithm; and

means for refining the patches using a split-and-merge algorithm.

64. The data compression system of claim 58, wherein said computing means includes means for computing a displaced frame difference (DFD) where a plurality of pixel regions of the second image frame are displaced with respect to identical pixel regions of said first image frame.

66. The data compression system of claim 63, wherein said patch designation assigning means comprises:

means for rank ordering said triangular patches on the basis of the values and directions of said dense motion vectors obtained from said computing means and located within each patch in accordance with the following relationship, ##EQU20## where O_k is the rank order of a patch k

68. The data compression system of claim 63, wherein said motion estimating means comprises:

means for deriving the motion of each pixel within a triangular patch overlaid on said temporally first image frame to new coordinate locations in said estimated second image frame in accordance with the following relationships,

space="preserve" listing-type="equation">u.sub.j =x'"'"'.sub.j -x.sub.j =(a.sub.i1 -1)x.sub.j +a.sub.i2 y.sub.j +a.sub.i3

space="preserve" listing-type="equation">v.sub.j =y'"'"'.sub.j -y.sub.j =a.sub.i4 x.sub.j +(a.sub.i5 -1)y.sub.j +a.sub.i6,

where

x_j, y_j are the coordinates of a pixel, j, within a patch i of the first image frame,

x'"'"'_j, y'"'"'_j are the estimated coordinates of a matching pixel within the patch i of the estimated second image frame,

u_j, v_j are the estimated parametric motion vectors of the pixel j,

a_i1, . . . a_i6 are affine parameters for patch i,

and wherein u_j =(x'"'"'_j -x_j) and v_j =(y_j -y_j) are flow constraints or estimates in accordance with said motion-estimating constraints;

means for determining an estimate of said node point motion vectors of the three node points of an ith triangular patch overlaid on said first image frame, in accordance with the following relationship, ##EQU22## where N_i is the number of estimated dense motion vectors within the first triangular patch, the relationship being minimized with respect to the affine parameters a_i1, . . . , a_i6 by an application of said solution in accordance with the following relationship, ##EQU23## where x₁, . . . , x_Ni and y₁, . . . , y_Ni are the respective starting coordinates of all N_i dense motion vectors within the ith triangular patch of the first image frame

x'"'"'₁, . . . , x'"'"'_Ni and y'"'"'₁, . . . , y'"'"'_Ni

are the respective ending coordinates of all N_i dense motion vectors within the ith patch of the estimated uncompressed second image frame

a_i1, . . . , a_i6 are the affine parameters,

and wherein the node point motion vectors of said three node points are included therein and can be extracted therefrom.

69. The data compression system of claim 63 and having said plurality of interconnected triangular patches arranged to form a common node point among one of the node points of each of the patches with remaining node points of each of the patches having node point coordinates defining a polygonal boundary, and wherein said motion estimating means comprises:

means for determining an estimate of said node point motion vector of said common node point wherein said statistical solution is a least squares solution to minimizing a displaced frame difference over the patches defining said polygonal boundary, said determining means including means for establishing motion constraints on the node points forming the common node point and on the node points common to adjoining patches and defining said polygonal boundary.

70. The data compression system of claim 63, wherein said motion estimating means further comprises:

means for preserving the connectivity among said plurality of interconnected shape-adaptive triangular patches of said mesh overlay model, wherein each node point common to adjoining triangular patches has one and the same node point motion vector in accordance with another one of said motion-estimating constraints, and wherein said means for preserving the connectivity uses a polygonal boundary constraint.

71. The data compression system of claim 63 wherein said pixels in each array have associated pixel signal levels corresponding to the contents of the scenes depicted by each of said frames, and wherein said sequence includes a temporally first frame and a temporally second frame having at least one pixel region displaced in correspondence with the motion of said scene content with respect to an identical pixel region of said first frame and further comprising:

means for storing temporarily the pixel signal levels of said first frame, means for determining the values and coordinate locations of said spatial gradients on a pixel-by-pixel basis within said first and second frames, and wherein said computing means further comprises means for computing the difference between the values of said spatial gradients at identical coordinate locations within said frames whereby to provide said dense motion vectors.

72. The data compression system of claim 63, wherein said failure regions identifying means comprises:

means for selecting a first failure-identifying threshold level in accordance with said failure-identifying constraints, a failure region (BTBC) being identified as a region where an absolute difference of pixel signal levels between the original and the compressed first image frame is in excess of said first threshold level; and

means for selecting a second failure-identifying threshold level in accordance with said failure-identifying constraints, said MF and said UB being identified as regions where an absolute difference of pixel signal levels between the original uncompressed second image frame and said estimated second image frame is in excess of said second threshold level.

73. The data compression system of claim 63, wherein said bit budget establishing means comprises:

means for counting as data bits the node point motion vectors; and

means for calculating a data bit rate fraction corresponding to said counted data bits, said fraction being calculated with respect to said constant data bit rate of the data to be transmitted.

74. The data compression system of claim 63, wherein said failure region identifying means further comprises:

means for setting an upper limit value for an allowable number of failure regions as a fraction of all regions within said data-compressed estimated second image frame;

means for detecting said fraction of said allowable number of failure regions;

means for deciding that said estimated second image frame constitutes a new first image frame whenever said fraction of said allowable number of failure regions is higher than said upper limit value; and

means for resetting said node point estimating means, said mesh-generating means, and said patch designation assigning means to generate a new mesh for a new first image frame.

75. The data compression system of claim 63, wherein said bit budget establishing means further comprises:

means for ascertaining an overall signal-to-noise ratio of the data compression system in accordance with the following relationship, ##EQU24## where PSNR is the peak signal-to-noise ratio

255is the maximum number of pixel signal levels representative of spatial image gradients of a scene content

MSD is the mean square difference of the estimated and original second frames.

76. The data compression system of claim 63, wherein said mesh generating means comprises:

means for selecting a mesh-generating threshold level in accordance with one of said mesh-generating constraints, said coordinates of said node points of said triangular patches on said first image frame being defined by values of said spatial gradients exceeding said selected threshold level, and said displaced frame differences;

means for selecting a minimum coordinate distance which defines a closest distance between neighboring node points in accordance with another one of said mesh-generating constraints, said minimum coordinate distance being selected on the basis of said number of pixels contained in said two-dimensional coordinate array of pixels; and

means for identifying failure regions in said first frame and means for detecting the location of each one of said node points such that it does not fall within said failure regions.

78. The data compression system of claim 74, wherein said motion estimating means comprises:

means for deriving the node point motion vectors of said polygonal boundary node points and of said common node point from said dense motion vectors by a least squares statistical solution whereby a difference of said displaced regions and alternatively a displaced frame difference (DFD) is minimized over said patches having said assigned designations in accordance with the following relationships,

space="preserve" listing-type="equation">H·

a=0,

where

0 is a vector of the common node point whose vector elements are zero,

H is a matrix equation as follows;

##EQU25## where rows and columns of the matrix are designated,

x₀, y₀, -x₀, -y₀

are the respective coordinates of the common node point,

x₁, y₁, -x₁, -y₁ . . . , x_N, y_N, -x_N, -y_N are the respective coordinates of the polygonal boundary node points;

with unspecified matrix elements having a zero value, and a is given by;

##EQU26## where (a_i1, a_i2, a_i3, a_i4, a_i5, a_i6) are the affine parameters associated with an ith triangle, the first 3 affine parameters (a_i1, a_i2, a_i3) are decoupled from the last 3 affine parameters (a_i4, a_i5, a_i6), whereby only the matrix equation governing the first 3 affine parameters of each triangle of the polygon is used, and wherein said least squares statistical solution is utilized in accordance with motion-estimating constraints.

79. The data compression system of claim 75, wherein said motion-estimating constraints include one constraint that the common node point of all intersecting triangular patches must have one node point motion vector, and another constraint that each polygonal boundary node point common to adjoining triangular patches must have one and the same node point motion vector.

10. α

₁. α

₂ are positive scalars selected such that ##EQU10## are of the same order,

space="preserve" listing-type="equation">D.sub.k

is the displaced region difference (DRD) within a patch k,

space="preserve" listing-type="equation">N.sub.k

is the total number of pixels within a patch k,

space="preserve" listing-type="equation">σ

.sub.k.sup.2

is the variance among the pixel signal levels within a patch k

wherein patches having the highest variance are assigned the highest rank and correspondingly highest priority for processing by said motion estimating means in accordance with at least one of said patch-assigning constraints, and

said means for rank ordering using a function of

space="preserve" listing-type="equation">D.sub.k,

N_k, and

space="preserve" listing-type="equation">σ

.sub.k.sup.2.

10.

12. The data compression system of claim 10, wherein said motion estimating means further comprises alternative means for determining said estimate for said three node points of said ith triangular patch overlaid on said first image frame, in accordance with the following relationship, ##EQU13## where N_i is the number of pixels within said ith triangular patch of said first image frame

where

I_x, I_y are the spatial image gradients in respective x and y directions of said N_i pixels within said ith patch of said first image frame

where

I_t is a temporal gradient within the ith patch of the first image frame,

said relationship being minimized with respect to said affine parameters a_i1, . . . , a_i6 in terms of spatio-temporal image gradients and node point coordinates by said application of said solution to determine said estimate of said node point motion vectors.

13. The data compression system of claim 10, wherein said motion estimating means further comprises:

means for preserving the connectivity among said plurality of interconnected shape-adaptive triangular patches of said mesh overlay model, wherein each node point common to adjoining triangular patches has one and the same node point motion vector in accordance with another one of said motion-estimating constraints, and wherein said means for preserving the connectivity uses a polygonal boundary constraint.

30. A method of data compression in a sending unit for transmitting at a constant data bit rate over a data link in accordance with a communication standard between said sending unit and a receiving unit of data of a temporal sequence of image frames of video signals in which each image frame is represented prior to data compression by a two-dimensional coordinate array of a number of digitized picture elements (pixels) having associated pixel signal levels corresponding to a scene content containing spatial gradients and wherein said sequence includes a temporally first image frame and at least a temporally second image frame having at least one pixel region displaced in correspondence with motion of said scene content with respect to an identical pixel region of said first image frame, the data compression method comprising the steps of:

storing temporarily in a storing means the pixel signal levels of said first image frame;

determining the values and the coordinate locations of said spatial gradients on a pixel-by-pixel basis within said first and second image frames;

computing a dense motion field of dense motion vectors on a pixel-by-pixel basis representing the values and directions of motion of said scene content of aid temporally second image frame with respect to said temporally first image frame;

generating a two-dimensional model of a mesh overlay on said first image frame, said mesh model comprising a plurality of interconnected shape-adaptive triangular patches with each patch having node points with respectively associated node point coordinates, each of said patches being defined on said first image frame in accordance with mesh-generating constraints in response to said spatial gradients and displaced region differences;

assigning a designation to each one of said shape-adapted triangular patches in accordance with the patch-assigning constraint and to each one of the node points associated therewith;

estimating and thereby parameterizing the motion of each one of said node points of said triangular patches overlaid on said first image frame in response to said dense motion vectors, said note point motion being estimated in accordance with motion-estimating constraints by an application of a statistical solution to an affine transformation of said first image format, whereby said dense motion vectors are data-compressed into estimated note point motion vectors having second coordinates associated therewith and wherein all estimated node point motion vectors together comprise a representation of a data-compressed estimated second image frame;

identifying failure regions in said data-compressed estimated second image frame wherein a difference is computed between the pixel signal levels of a temporarily stored uncompressed second image frame and said data-compressed estimated second image frame in accordance with a failure-identifying constraint, whereby each failure region is defined as such rectangular coordinate array of pixels of the uncompressed second image frame which encloses the pixels within a failure region identified in said temporally second image frame;

establishing a bit budget for the data to be transmitted at said constant data bit rate by said sending unit to said receiving unit;

revising the failure regions defined in said failure regions identifying step in accordance with a revised failure-identifying constraint;

assigning a designation to each one of said failure regions and alternatively to each one of said revised failure regions;

coding the node designations of each one of said triangular patches of said mesh overlay model;

coding the pixel signal levels of pixels within each one of the rectangular coordinate array failure revised failure regions;

coding the node point motion vectors of said data-compressed estimated second image frame;

coding the pixel signal levels of all pixels of said temporally first image frame when said first frame is an original or a new first frame; and

transmitting at a constant data bit rate from said sending unit over said data link to said receiving unit said coded pixel signal levels of said first image frame, said coded node point motion vectors, the coded pixel signal levels corresponding to said failure regions and said coded node designations in accordance with said communication standard.

32. The data compression method of claim 30, wherein said mesh-generating step comprises:

selecting a mesh-generating threshold level in accordance with one of said mesh-generating constraints, said coordinates of said node points of said triangular patches on said first image frame being defined by values of said spatial gradients in excess of said selected mesh-generating threshold level, and by said displaced region differences;

selecting a minimum coordinate distance which defines a closest distance between neighboring node points in accordance with another one of said mesh-generating constraints, said minimum coordinate distance selected on the basis of said number of pixels contained in said two-dimensional coordinate array of pixels;

identifying failure regions in said first image frame; and

selecting the location of each one of said node points such that each node point is located outside each one of said failure regions.

35. The data compression method of claim 32, wherein said motion estimating step comprises:

deriving the motion of each pixel within a triangular patch overlaid on said temporally first image frame to new coordinate locations in said estimated second image frame in accordance with the following relationships,

space="preserve" listing-type="equation">u.sub.j =x'"'"'.sub.j -x.sub.j =(a.sub.i1 -1)x.sub.j +a.sub.i2 y.sub.j +a.sub.i3

space="preserve" listing-type="equation">v.sub.j =y'"'"'.sub.j -y.sub.j =a.sub.i4 x.sub.j +(a.sub.i5 -1)y.sub.j +a.sub.i6,

where

x_j, y_j are the coordinates of a pixel, j, within a patch i of the first image frame,

x'"'"'_j, y'"'"'_j are the estimated coordinates of a matching pixel within the patch i of the estimated second image frame,

u_j, v_j are estimated parametric motion vectors of the pixel j;

and

a_i1, . . . a_i6 are affine parameters for patch i,

and wherein u_j =(x'"'"'_j -x_j) and v_j =(y'"'"'_j -y_j) are optical flow constraints or estimates in accordance with one of said motion-estimating constraints;

determining an estimate of said node point motion vectors of the three node points of an ith triangular patch overlaid on said first image frame, in accordance with the following relationship, ##EQU17## where N_i is the number of estimated dense motion vectors within the i-th triangular patch, said relationship being minimized with respect to the affine parameters a_i1, . . . , a_i6 by an application of a linear least-squares solution in accordance with the following relationship, ##EQU18## where x₁, . . . , x_Ni and y₁, . . . , y_Ni

are the respective starting coordinates of all N_i dense motion vectors within the i-th triangular patch of the first image frame

x'"'"'₁, . . . , x'"'"'_Ni and Y'"'"'₁, . . . , Y'"'"'_Ni

are the respective ending coordinates of all N_i dense motion vectors within the i-th patch of the estimated uncompressed second image frame

a_i1, . . . a_i6 are the affine parameters,

and wherein the node point motion vectors of the three node points are included therein and can be extracted therefrom.

34. α

₁. α

₂ are positive scalars selected such that ##EQU16## are of the same order,

space="preserve" listing-type="equation">D.sub.k

is the displaced region difference (DRD) within a patch k,

space="preserve" listing-type="equation">N.sub.k

is the total number of pixels within a patch k,

space="preserve" listing-type="equation">σ

.sub.k.sup.2

is the variance among the pixel signal levels within a patch k

wherein patches having the highest variance are assigned the highest rank and correspondingly highest priority for processing by said motion estimating means in accordance with the patch-assigning constraint; and

rank ordering by a function of

space="preserve" listing-type="equation">D.sub.k,

N_k, and

space="preserve" listing-type="equation">σ

.sub.k.sup.2.

60. In a video data compression system in a sending unit for transmitting at a constant data bit rate over a data link in accordance with a communication standard between said sending unit and a receiving unit of data of a temporal sequence of image frames of video signals in which each image frame is represented prior to data compression by a two-dimensional coordinate array of a number of digitized picture elements (pixels) having associated pixel signal levels representative of spatial image gradients corresponding to a scene content and wherein said sequence includes a temporally first image frame and at least a temporally second image frame having at least one pixel region displaced in correspondence with motion of said scene content with respect to an identical pixel region of said first image frame, the data compression system comprising:

means for temporarily storing the pixel signal levels of said first image frame;

means for determining the values and the coordinate locations of said spatial image gradients on a pixel-by-pixel basis within said first and second image frames;

means for computing a dense motion field of dense motion vectors on a pixel-by-pixel basis representing the values and directions of motion of said scene content of said temporally second image frame with respect to said temporally first image frame; and

means for generating a two-dimensional model of a mesh overlay on said first image frame, said mesh model comprising a plurality of interconnected shape-adaptive triangular patches with each patch having node points with respectively associated node point coordinates, each of said patches being defined on said first image frame in accordance with mesh-generating constraints and spatial gradients and displaced frame differences.

65. In a video data compression system in a sending unit for transmission at a constant data bit rate over a data link in accordance with a communication standard between said sending unit and a receiving unit of data of a temporal sequence of image frames of video signals in which each image frame is represented prior to data compression by a two-dimensional coordinate array of a number of digitized picture elements (pixels) wherein said sequence includes a temporally first image frame and at least a temporally second image frame, the frames having scene contents containing spatial gradients and also having regions displaced corresponding to motion of the scene content, the data compression system comprising:

means for computing a dense motion field of dense motion vectors on a pixel-by-pixel basis representing the values and directions of motion of said scene content of said temporally second image frame with respect to said temporally first image frame;

means for generating a two-dimensional model of a mesh overlay on said first image frame, said mesh model comprising a plurality of interconnected shape-adaptive triangular patches with each patch having node points with respectively associated node point coordinates, each of said patches being defined on said first image frame in accordance with mesh-generating constraints and spatial gradients and displaced frame differences;

means for assigning a designation to each one of said shape-adaptive triangular patches in accordance with a patch-assigning constraint and to each one of the node points associated therewith;

means for estimating and thereby parameterizing the motion of each one of said node points of said triangular patches overlaid on said first image frame in response to said dense motion vectors, said node point motion being estimated in accordance with motion-estimating constraints by an application of a statistical solution to an affine transformation of said first image frame, whereby said dense motion vectors are data-compressed into estimated node point motion vectors having second coordinates associated therewith and wherein all estimated node point motion vectors together comprise a representation of a data-compressed estimated second image frame;

means for identifying failure regions (MF and UB) in said data-compressed estimated second image frame wherein a difference is computed between the pixel signal levels of the uncompressed second image frame and said data-compressed estimated second image frame in accordance with failure-identifying constraints, whereby each failure region is defined as such rectangular coordinate array of pixels of the uncompressed second image frame which encloses the pixels within a failure region identified in said temporally second image frame; and

means for establishing a bit budget for the data to be transmitted at said constant data bit rate by said sending unit to said receiving unit.

67. α

₁. α

₂ are positive scalars selected such that ##EQU21## are of the same order, D_k is the displaced region difference (DRD) within a patch k,

N_k is the total number of pixels within a patch k,

σ

_k² is the variance among the pixel signal levels within a patch k,

wherein patches having the highest variance are assigned the highest rank and correspondingly highest priority for processing by said motion estimating means in accordance with at least one of said patch-assigning constraints, and

said means for rank ordering using a function of D_k, N_k, and σ

_k².

77. In a video data compression system in a sending unit for transmission at a constant data bit rate over a data link in accordance with a communication standard between said sending unit and a receiving unit of data of a temporal sequence of image frames of video signals in which each image frame is represented prior to data compression by a two-dimensional coordinate array of a number of digitized picture elements (pixels) wherein said sequence includes a temporally first image frame and at least a temporally second image frame, the frames having scene contents containing spatial gradients and also having regions displaced corresponding to motion of the scene content, the data compression system comprising:

means for computing a dense motion field of dense motion vectors on a pixel-by-pixel basis representing the values and directions of motion of said scene content of said temporarlly second image frame with respect to said temporally first image frame;

means for generating a two-dimensional model of a mesh overlay on said first image frame, said mesh model comprising a plurality of interconnected shape-adaptive triangular patches with each patch having node points with respectively associated node point coordinates, each of said patches being defined on said first image frame in accordance with mesh-generating constraints and spatial gradients and displaced frame differences and wherein said plurality of interconnected patches are arranged to form a common node point among one of the node points of each of the patches with remaining node points of each of the patches having node point coordinates defining a polygonal boundary;

means for assigning a designation to each one of said shape-adaptive triangular patches in accordance with a patch-assigning constraint and to each one of the node points associated therewith; and

means for estimating and thereby parameterizing the motion of each one of said polygonal boundary node points and of said common node point of said triangular patches overlaid on said first image frame in response to said dense motion vectors, said node point motion being estimated in accordance with a motion-estimating constraint by an application of statistical solution to an affine transformation of said first image frame, whereby said dense motion vectors are data-compressed into estimated node point motion vectors having second coordinates associated therewith and wherein all estimated node point motion vectors together comprise a representation of a data-compressed estimated second image frame.

81. The data compression method of claim 77, wherein said pixels in each array have associated pixel signal levels corresponding to the contents of the scenes depicted by each of said frames, and wherein said sequence includes a temporally first frame and a temporally second frame having at least one pixel region displaced in correspondence with the motion of said scene content with respect to an identical pixel region of said first frame and further comprising the steps of:

storing temporarily the pixel signal levels of said first frame, determining the values and coordinate locations of said spatial gradients on a pixel-by-pixel basis within said first and second image frames, and wherein said computing step further includes the step of computing the difference between the values of said spatial gradients at identical coordinate locations within said frames whereby to provide said dense motion vectors.

82. The data compression method of claim 77, further comprising the steps of:

obtaining the triangular patches by a Delauney triangulization algorithm; and

refining the patches by a split-and-merge algorithm.

83. The data compression method of claim 77, wherein said dense motion vector computing step comprises:

selecting a two-dimensional (2-D) motion field estimation algorithm to obtain dense motion vectors for each pixel location.

85. The data compression method of claim 81, wherein said patch designation assigning step comprises:

rank ordering said triangular patches on the basis of the values and directions of said dense motion vectors obtained from said dense motion field computing step and located within each patch in accordance with the following relationship, ##EQU27## where O_k is the rank order of a patch k

87. The data compression method of claim 82, wherein said motion estimating step comprises:

deriving the node point motion vectors of said polygonal boundary node points and of said common node point from said dense motion vectors by a least squares statistical solution whereby a difference of said displaced frame difference (DFD) is minimized over said patches having said assigned designations in accordance with the following relationships,

space="preserve" listing-type="equation">H·

a=0,

where

0 is a vector of the common node point whose vector elements are zero,

H is a matrix equation as follows;

##EQU29## where rows and columns of the matrix are designated,

x₀, y₀, -x₀, -y0

are the respective coordinates of the common node point,

x₁, y₁, -x₁, -y₁ . . . , x_N, y_N, -x_N, -y_N

are the respective coordinates of the polygonal boundary node points;

with unspecified matrix elements having a zero value, and a is given by;

##EQU30## where (a_i1, a_i2, a_i3, a_i4, a_i5, a_i6) are the affine parameters associated with an ith triangle, the first 3 affine parameters (a_i1, a_i2, a_i3) are decoupled from the last 3 affine parameters (a_i4, a_i5, a_i6), whereby only the matrix equation governing the first 3 affine parameters of each triangle of the polygon is used, and wherein said least squares statistical solution is utilized in accordance with motion-estimating constraints.

88. The data compression method of claim 83, wherein said motion estimating constraints utilizing step includes the steps of:

defining one constraint so that the common node point of all intersecting triangular patches has one node point motion vector; and

defining another constraint so that each polygonal boundary node point common to adjoining triangular patches has one and the same node point motion vector.

89. The data compression method of claim 83, wherein said failure regions identifying step comprises:

selecting a first failure-identifying threshold level in accordance with said failure-identifying constraint, failure region (BTBC) being identified as a region where an absolute difference of pixel signal levels between the original and the compressed first image frame is in excess of said first threshold level; and

selecting a second failure-identifying threshold level in accordance with said failure-identifying constraint, said MF and said UB being identified as regions where an absolute difference of pixel signal levels between the original uncompressed second image frame and said estimated second image frame is in excess of said second threshold level.

90. The data compression method of claim 85, wherein said bit budget establishing step comprises:

counting as data bits the node point motion vectors; and

calculating a data bit rate fraction corresponding to said counted data bits, said fraction being calculated with respect to said constant data bit rate of the data to be transmitted.

80. In a video data compression method in a sending unit for transmission at a constant data bit rate over a data link in accordance with a communication standard between said sending unit and a receiving unit of data of a temporal sequence of image frames of video signals in which each image frame is represented prior to data compression by a two-dimensional coordinate array of a number of digitized picture elements (pixels) wherein said sequence includes a temporally first image frame and at least a temporally second image frame, the frames having scene contents containing spatial gradients and also having regions displaced corresponding to motion of the scene content, the data compression method comprising the steps of:

computing a dense motion field of dense motion vectors on a pixel-by-pixel basis representing the values and directions of motion of said scene content of said temporally second image frame with respect to said temporally first image frame;

generating a two-dimensional model of a mesh overlay on said first image frame, said mesh model comprising a plurality of interconnected shape-adaptive triangular patches with each patch having node points with respectively associated node point coordinates, each of said patches being defined on said first image frame in accordance with mesh-generating constraints and spatial gradients and displaced frame differences, and wherein said plurality of interconnected patches are arranged to form a common node point among one of the node points of each of the patches with remaining node points of each of the patches having node point coordinates defining a polygonal boundary;

assigning a designation to each one of said shape-adaptive triangular patches in accordance with a patch-assigning constraint and to each one of the node points associated therewith;

estimating and thereby parameterizing the motion of each one of said polygonal boundary node points and of said common node points of said triangular patches overlaid on said first image frame in response to said dense motion vectors, said node point motion being estimated in accordance with motion-estimating constraints by an application of a statistical solution to an affine transformation of the first image frame, whereby said dense motion vectors are data-compressed into estimated node point motion vectors having second coordinates associated therewith and wherein all estimated node point motion vectors together comprise a representation of a data-compressed estimated second image frame;

identifying failure regions (MF and UB) in said data-compressed estimated second image frame wherein a difference is computed between the pixel signal levels of a temporarily stored uncompressed second image frame and said data-compressed estimated second image frame in accordance with a failure-identifying constraint, whereby each failure region is defined as such rectangular coordinate array of pixels of the uncompressed second image frame which encloses the pixels within a failure region identified in said temporally second image frame; and

establishing a bit budget for the data to be transmitted at said constant data bit rate by said sending unit to said receiving unit.

84. The data compression method of claim 80, wherein said mesh generating step comprises:

selecting a mesh-generating threshold level in accordance with one of said mesh-generating constraints, said coordinates of said node points of said triangular patches on said first image frame being defined by values of said spatial gradients in excess of said selected mesh-generating threshold level, and by displaced region differences;

selecting a minimum coordinate distance which defines a closest distance between neighboring node points in accordance with another one of said mesh-generating constraints, said minimum coordinate distance selected on the basis of a number of pixels contained in said two-dimensional coordinate array of pixels;

identifying failure regions in said first image frame; and

selecting the location of each one of said node points such that each node point is located outside each one of said failure regions.

86. α

₁. α

₂ are positive scalars selected such that ##EQU28## are of the same order D_k is the displaced frame difference (DFD) within a patch k,

N_k is the total number of pixels within a patch k,

σ

_k² is the variance among the pixel signal levels within a patch k

wherein patches having the highest variance are assigned the highest rank and correspondingly highest priority for processing by said motion estimating step in accordance with one of said patch-assigning constraints; and

rank ordering by a function of D_k, N_k, and σ

_k².