US5847776A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for entropy constrained motion estimation and coding of motion vectors with increased search range
Assignee: Citrix Systems Inc
•
Filing: 1996-06-24
•
Granted: 1998-12-08
•
Expires: 2016-06-24
Abstract
Abstract A novel method of improving the motion estimation and coding efficiency of Interframes in a video compression system is disclosed. The method teaches a novel minimization function to be used to determine the optimum motion vector for a block within a picture. The minization function takes into account not just the conventional sum of the differences but also the quantization step, the motion vector itself and the predicted motion vector. The minimization function disclosed better balances the tradeoff between the size of the motion vectors and the size of the resulting residuals. The results are particularly useful when the range of the search is increased. Motion vectors closer to the prediction motion vector will be favored over better matches found further away from the prediction motion vector. In addition, a novel variable length coding (VLC) method is also disclosed. The disclosed encoding method is able to code numbers having a range double that of conventional VLC tables but with a very small penalty in increased bit length.
Inventors
- 👤 Alex Khmelnitsky
- 👤 Eugene Taits
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:23
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/50; H04N19/503; H04N19/51; H04N19/513; H04N19/517; H04N19/567
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
155 words
A method of improving the motion estimation and coding efficiency of Interframes in a video compression system, said video compression system dividing a current picture into a plurality of smaller size blocks, each said block containing (i 1 -i 0 ) by (j 1 -j 0 ) pixels, said method comprising the steps of: stepping through each said block in said current picture; for each said block, stepping through all motion vectors (MV) V X , V Y within a predetermined search range; for each said motion vector, calculating the expression given by ##EQU6## wherein C ij represents a pixel within said search range in a previous picture which preceded said current picture in time, P ij represents a pixel within said block in said current picture, QP is the quantization step, PMV is a predicted motion vector; and determining an optimum motion vector V X , V Y that minimizes the above said expression.
Claim 2
Independent Claim
155 words
A method of improving the motion estimation and coding efficiency of Interframes in a video compression system, said video compression system dividing a current picture into a plurality of smaller size blocks, each said block containing (i 1 -i 0 ) by (j 1 -j 0 ) pixels, said method comprising the steps of: stepping through each said block in said current picture; for each said block, stepping through all motion vectors (MV) V X , V Y within a predetermined search range; for each said motion vector, calculating the expression given by ##EQU6## wherein C ij represents a pixel within said search range in a previous picture which preceded said current picture in time, P ij represents a pixel within said block in said current picture, QP is the quantization step, PMV is a predicted motion vector; and determining an optimum motion vector V X , V Y that minimizes the above said expression.
Claim 3
Dependent Claim
67 words
The method according to claim 1, wherein said expression is given by the following ##EQU7## wherein C ij represents a pixel within said search range in a previous picture which preceded said current picture in time, P ij represents a pixel within said block in said current picture, QP is the quantization step, PMV is a predicted motion vector represented by PV X , PV Y .
Claim 4
Independent Claim
161 words
A method of improving the motion estimation and coding efficiency of Interframes in a video compression system, said video compression system dividing a current picture into a plurality of smaller size blocks, each said block containing (i 1 -i 0 ) by (j 1 -j 0 ) pixels, said method comprising the steps of: stepping through each said block in said current picture; for each said block, stepping through all motion vectors (MV) V X , V Y within a predetermined search range; for each said motion vector, calculating the expression ##EQU8## wherein C ij represents a pixel within said search range in a previous picture which preceded said current picture in time, P ij represents a pixel wit said block in said current picture, QP is the quantization step, PMV is a predicted motion vector represented by PV X , PV Y ; and determining an optimum motion vector V X , V Y that minimizes the above said expression.
Claim 5
Independent Claim
161 words
A method of improving the motion estimation and coding efficiency of Interframes in a video compression system, said video compression system dividing a current picture into a plurality of smaller size blocks, each said block containing (i 1 -i 0 ) by (j 1 -j 0 ) pixels, said method comprising the steps of: stepping through each said block in said current picture; for each said block, stepping through all motion vectors (MV) V X , V Y within a predetermined search range; for each said motion vector, calculating the expression ##EQU8## wherein C ij represents a pixel within said search range in a previous picture which preceded said current picture in time, P ij represents a pixel wit said block in said current picture, QP is the quantization step, PMV is a predicted motion vector represented by PV X , PV Y ; and determining an optimum motion vector V X , V Y that minimizes the above said expression.
Claim 6
Independent Claim
121 words
A method of encoding a number, said method utilizing a suitable variable length coding technique, said method improving the motion estimation and coding efficiency of Interframes in a video compression system, said method comprising the steps of: outputting a single bit if said number equals zero and then terminating said method; outputting a single bit representing the sign of said number; calculating a value V 1 equal to the absolute value of said number minus 1; if said V 1 is even, calculating a value V 2 equal to said V 1 divided by 2; if said V 1 is odd, calculating said V 2 as follows V.sub.2 =-1-(V.sub.1 -1)/2; and encoding said V 2 utilizing said variable length coding technique.
Claim 7
Independent Claim
121 words
A method of encoding a number, said method utilizing a suitable variable length coding technique, said method improving the motion estimation and coding efficiency of Interframes in a video compression system, said method comprising the steps of: outputting a single bit if said number equals zero and then terminating said method; outputting a single bit representing the sign of said number; calculating a value V 1 equal to the absolute value of said number minus 1; if said V 1 is even, calculating a value V 2 equal to said V 1 divided by 2; if said V 1 is odd, calculating said V 2 as follows V.sub.2 =-1-(V.sub.1 -1)/2; and encoding said V 2 utilizing said variable length coding technique.
Claim 8
Independent Claim
140 words
A method of run length encoding a series of numbers, said method utilizing a run length coding technique and a suitable variable length coding technique, said method improving the motion estimation and coding efficiency of Interfames in a video compression system, said method comprising the steps of: for said numbers valued zero: encoding zeros present in said series of numbers using said run length technique; for said numbers valued non-zero: outputting a single bit representing the sign of said number; calculating a value V 1 equal to the absolute value of said number minus 1; if said V 1 is even, calculating a value V 2 equal to said V 1 divided by 2; if said V 1 is odd, calculating said V 2 as follows V.sub.2 =-1-(V.sub.1 -1)/2; and encoding said V 2 utilizing said variable length coding technique.
Claim 9
Independent Claim
140 words
A method of run length encoding a series of numbers, said method utilizing a run length coding technique and a suitable variable length coding technique, said method improving the motion estimation and coding efficiency of Interfames in a video compression system, said method comprising the steps of: for said numbers valued zero: encoding zeros present in said series of numbers using said run length technique; for said numbers valued non-zero: outputting a single bit representing the sign of said number; calculating a value V 1 equal to the absolute value of said number minus 1; if said V 1 is even, calculating a value V 2 equal to said V 1 divided by 2; if said V 1 is odd, calculating said V 2 as follows V.sub.2 =-1-(V.sub.1 -1)/2; and encoding said V 2 utilizing said variable length coding technique.
Claim 10
Independent Claim
263 words
A method of improving the motion estimation and coding efficiency of Interframes in a video compression system, said video compression system dividing a current picture into a plurality of smaller size blocks, each said block containing (i 1 -j 0 ) by (j 1 -j 0 ) pixels, said method utilizing a run length coding technique and a suitable variable length coding technique, said method comprising the steps of: stepping through each said block in said current picture; for each said block, stepping through all motion vectors (MV) V X , V Y within a predetermined search range; for each said motion vector, calculating the expression given by ##EQU9## wherein C ij represents a pixel within said search range in a previous picture which preceded said current picture in time, P ij represents a pixel within said block in said current picture, QP is the quantization step, PMV is a predicted motion vector; determining an optimum motion vector V X , V Y that minimizes the above said expression; for said motion vectors valued zero: encoding zero valued motion vectors using said run length technique; for said motion vectors valued non-zero: outputting a single bit representing the sign of said motion vector; calculating a value V 1 equal to the absolute value of said motion vector minus 1; if said V 1 is even, calculating a value V 2 equal to said V 1 divided by 2; if said V 1 is odd, calculating said V 2 as follows V.sub.2 =-1-(V.sub.1 -1)/2; and encoding said V 2 utilizing said variable length coding technique.
Claim 11
Independent Claim
263 words
A method of improving the motion estimation and coding efficiency of Interframes in a video compression system, said video compression system dividing a current picture into a plurality of smaller size blocks, each said block containing (i 1 -j 0 ) by (j 1 -j 0 ) pixels, said method utilizing a run length coding technique and a suitable variable length coding technique, said method comprising the steps of: stepping through each said block in said current picture; for each said block, stepping through all motion vectors (MV) V X , V Y within a predetermined search range; for each said motion vector, calculating the expression given by ##EQU9## wherein C ij represents a pixel within said search range in a previous picture which preceded said current picture in time, P ij represents a pixel within said block in said current picture, QP is the quantization step, PMV is a predicted motion vector; determining an optimum motion vector V X , V Y that minimizes the above said expression; for said motion vectors valued zero: encoding zero valued motion vectors using said run length technique; for said motion vectors valued non-zero: outputting a single bit representing the sign of said motion vector; calculating a value V 1 equal to the absolute value of said motion vector minus 1; if said V 1 is even, calculating a value V 2 equal to said V 1 divided by 2; if said V 1 is odd, calculating said V 2 as follows V.sub.2 =-1-(V.sub.1 -1)/2; and encoding said V 2 utilizing said variable length coding technique.
Claim 12
Dependent Claim
67 words
The method according to claim 6, wherein said expression is given by the following ##EQU10## wherein C ij represents a pixel within said search range in a previous picture which preceded said current picture in time, P ij represents a pixel within said block in said current picture, QP is the quantization step, PMV is a predicted motion vector represented by PV X , PV Y .
References Cited (Backward Citations)
US5317397A
Cited
US5424779A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-07 | 2002-06-08 | 2002-12-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-07 | 2006-06-08 | 2006-12-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-07 | 2010-06-08 | 2010-12-08 | $7700.00 | Window Closed / Lapsed |