US5778192A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and device for optimal bit allocation between different sources of information in digital video compression
Assignee: Motorola Solutions Inc
•
Filing: 1995-10-26
•
Granted: 1998-07-07
•
Expires: 2015-10-26
Abstract
Abstract The present invention provides a method (200, 400) and device (500) for, within a variable or fixed block size video compression scheme, providing optimal bit allocation among at least three critical types of data: segmentation, motion vectors and prediction error, or DFD. Since the amount of information represented by one bit for a particular type of data is not equivalent to the information represented by one bit for some other data type, this consideration is taken into account to efficiently encode the video sequence. Thus, a computationally efficient method is provided for optimally encoding a given frame of a video sequence wherein, for a given bit budget the proposed encoding scheme leads to the smallest possible distortion and vice versa, for a given distortion, the proposed encoding scheme leads to the smallest possible rate.
Inventors
- 👤 Guido M. Schuster
- 👤 Aggelos Katsaggelos
- 👤 Mark R. Banham
- 👤 James C. Brailean
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 17:51
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/008; H; H04; H04N; H04N19/00; H04N19/10; H04N19/102; H04N19/115; H04N19/134; H04N19/146; H04N19/147; H04N19/169; H04N19/17; H04N19/172; H04N19/176; H04N19/189; H04N19/19; H04N19/192; H04N19/50; H04N19/503; H04N19/51; H04N19/60; H04N19/61; H04N19/20
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
98 words
A method for allocating bits for optimal rate/distortion performance in digital video compression, comprising the steps of: A) mapping information for a current frame and information for a correlated frame that is stored in a memory unit into a set of information of A1-A4: A1) displaced frame difference information and displacement vector field information; A2) displaced frame difference information and segmentation information: A3) displacement vector field information and segmentation information; A4) displaced frame difference information, displacement vector field information, and segmentation information; B) using the set of information to optimally represent the current frame based on rate/distortion characteristics.
Claim 2
Independent Claim
98 words
A method for allocating bits for optimal rate/distortion performance in digital video compression, comprising the steps of: A) mapping information for a current frame and information for a correlated frame that is stored in a memory unit into a set of information of A1-A4: A1) displaced frame difference information and displacement vector field information; A2) displaced frame difference information and segmentation information: A3) displacement vector field information and segmentation information; A4) displaced frame difference information, displacement vector field information, and segmentation information; B) using the set of information to optimally represent the current frame based on rate/distortion characteristics.
Claim 3
Dependent Claim
16 words
The method of claim 1 wherein the rate/distortion characteristics are minimized using a Lagrangian relaxation scheme.
Claim 4
Dependent Claim
25 words
The method of claim 2 where the minimization step of the Lagrangian relaxation scheme is performed utilizing a dynamic programming approach implemented on a trellis.
Claim 5
Dependent Claim
16 words
The method of claim 3 further including utilizing a predetermined set of admissible displacement vector fields.
Claim 6
Dependent Claim
15 words
The method of claim 3 further including utilizing a predetermined set of admissible quantization values.
Claim 7
Dependent Claim
43 words
The method of claim 2 wherein the Lagrangian coefficient is determined using at least one of: A) Bisection method using an arithmetic mean; B) Bisection method using a geometric mean; C) Fast convex search; and D) Parametric parabola such as the Bezier curve.
Claim 8
Dependent Claim
20 words
The method of claim 1 wherein the displaced frame difference information is determined by the following equation: dfd(r)=f.sub.k (r)-f.sub.k-1 (r-d(r)).
Claim 9
Dependent Claim
20 words
The method of claim 1 wherein the displacement vector field information is determined utilizing a block matching motion estimation approach.
Claim 10
Dependent Claim
16 words
The method of claim 1 wherein the segmentation information is determined utilizing a quadtree segmentation approach.
Claim 11
Dependent Claim
21 words
The method of claim 9 wherein the contribution to the rate by the segmentation information is generated through the quadtree representation.
Claim 12
Dependent Claim
38 words
The method of claim 1 wherein the contribution to the rate by the displaced frame difference information is generated by utilizing at least one of the following compression techniques: A) Discrete Cosine Transform; and B ) Vector Quantization.
Claim 13
Dependent Claim
37 words
The method of claim 1 wherein the contribution to the rate by the displacement vector field information is generated using differential pulse code modulation with a single neighbor of a predetermined scanning order through the current frame.
Claim 14
Dependent Claim
24 words
The method of claim 12 wherein at least one of the following predetermined scanning orders is used: A) Hilbert scan; and B) Raster scan.
Claim 15
Dependent Claim
36 words
The method of claim 1 wherein the method is a process whose steps are embodied in an application specific integrated circuit arranged and configured to determine the first modified received signal having minimized distortion and interference.
Claim 16
Dependent Claim
17 words
The method of claim 1 wherein, for a predetermined number of bits per frame, distortion is minimized.
Claim 17
Dependent Claim
18 words
The method of claim 1 wherein, for a preselected distortion per frame, a number of bits is minimized.
Claim 18
Dependent Claim
36 words
The method of claim 1 wherein the method is a process whose steps are embodied in a field programmable gate array, arranged and configured to determine the first modified received signal having minimized distortion and interference.
Claim 19
Dependent Claim
33 words
The method of claim 1 wherein the method is a process whose steps are embodied in a microprocessor, arranged and configured to determine the first modified received signal having minimized distortion and interference.
Claim 20
Dependent Claim
34 words
The method of claim 1 wherein the method is a process whose steps are embodied in a computer-readable memory, arranged and configured to determine the first modified received signal having minimized distortion and interference.
Claim 21
Independent Claim
112 words
A device for allocating bits for optimal rate/distortion performance in digital video compression, wherein the device is directed by a computer program and the computer program includes steps of A-B: A) mapping information for a current frame and information for a correlated frame that is stored in a memory unit into a set of information of A1-A4: A1) displaced frame difference information and displacement vector field information; A2) displaced frame difference information and segmentation information: A3) displacement vector field information and segmentation information: A4) displaced frame difference information, displacement vector field information, and segmentation information; and B) using the set of information to optimally represent the current frame based on rate/distortion characteristics.
Claim 22
Independent Claim
112 words
A device for allocating bits for optimal rate/distortion performance in digital video compression, wherein the device is directed by a computer program and the computer program includes steps of A-B: A) mapping information for a current frame and information for a correlated frame that is stored in a memory unit into a set of information of A1-A4: A1) displaced frame difference information and displacement vector field information; A2) displaced frame difference information and segmentation information: A3) displacement vector field information and segmentation information: A4) displaced frame difference information, displacement vector field information, and segmentation information; and B) using the set of information to optimally represent the current frame based on rate/distortion characteristics.
Claim 23
Dependent Claim
16 words
The device of claim 20 wherein the rate/distortion characteristics are minimized using a Lagrangian relaxation scheme.
Claim 24
Dependent Claim
25 words
The device of claim 21 where the minimization step of the Lagrangian relaxation scheme is performed utilizing a dynamic programming approach implemented on a trellis.
Claim 25
Dependent Claim
15 words
The device of claim 22 further including utilizing a predetermined set of admissible quantization values.
Claim 26
Dependent Claim
16 words
The device of claim 22 further including utilizing a predetermined set of admissible displacement vector fields.
Claim 27
Dependent Claim
28 words
The device of claim 21 wherein the Lagrangian coefficient is determined using at least one of: A) Bisection method; and B) Parametric parabola such as the Bezier curve.
Claim 28
Dependent Claim
15 words
The device of claim 20 wherein, for a predetermined number of bits, distortion is minimized.
Claim 29
Dependent Claim
18 words
The device of claim 20 wherein, for a preselected distortion per frame, a number of bits is minimized.
Claim 30
Dependent Claim
37 words
The device of claim 20 wherein the contribution to the rate by the displacement vector field information is generated using differential pulse code modulation with a single neighbor of a predetermined scanning order through the current frame.
Claim 31
Dependent Claim
24 words
The device of claim 28 wherein at least one of the following predetermined scanning orders is used: A) Hilbert scan; and B) Raster scan.
Claim 32
Dependent Claim
20 words
The device of claim 20 wherein the displaced frame difference information is determined by the following equation: dfd(r)=f.sub.k (r)-f.sub.k-1 (r-d(r)).
Claim 33
Dependent Claim
20 words
The device of claim 20 wherein the displacement vector field information is determined utilizing a block matching motion estimation approach.
Claim 34
Dependent Claim
16 words
The device of claim 20 wherein the segmentation information is determined utilizing a quadtree segmentation approach.
Claim 35
Dependent Claim
21 words
The device of claim 32 wherein the contribution to the rate by the segmentation information is generated through the quadtree representation.
Claim 36
Dependent Claim
36 words
The device of claim 20 wherein contribution to the rate by the displaced frame difference information is generated by utilizing at least one of the following compression techniques: A) Discrete Cosine Transform; and B) Vector Quantization.
Claim 37
Independent Claim
109 words
A device for allocating bits for optimal rate/distortion performance in digital video compression comprising: A) a multi-level mapper, for mapping information for a current frame and information for a correlated frame that is stored in a memory unit into a set of information of A1-A4; A1) displaced frame,difference information and displacement vector field information; A2) displaced frame difference information and segmentation information: A3) displacement Mec|to field information and segmentation information; A4) displaced frame difference information, displacement vector field information, and segmentation information; and B) a rate/distortion frame optimizer, coupled to the multi-level mapper, for using the set of information to optimally represent the current frame based on rate/distortion characteristics.
Claim 38
Independent Claim
109 words
A device for allocating bits for optimal rate/distortion performance in digital video compression comprising: A) a multi-level mapper, for mapping information for a current frame and information for a correlated frame that is stored in a memory unit into a set of information of A1-A4; A1) displaced frame,difference information and displacement vector field information; A2) displaced frame difference information and segmentation information: A3) displacement Mec|to field information and segmentation information; A4) displaced frame difference information, displacement vector field information, and segmentation information; and B) a rate/distortion frame optimizer, coupled to the multi-level mapper, for using the set of information to optimally represent the current frame based on rate/distortion characteristics.
Claim 39
Independent Claim
189 words
A device for allocating bits for optimal rate/distortion performance in digital video compression, wherein the available bits per frame are allocated among at least two sources of information comprising at least two of: A) displaced frame difference, DFD, information; B) displacement vector field information; and C) segmentation information; wherein the device comprises: D) a DFD generator coupled to receive input from two frame buffer memories, for generating a DFD signal; E) a predetermined motion vector memory; F) a pre-computed transition costs memory; G) a predetermined quantization step size memory; H ) a computation unit, for computing an optimal encoded frame; I ) a predetermined target memory; J ) a comparator unit coupled to receive input from the predetermined target memory and the computation unit, for determining compliance with a predetermined target; K ) a Lagrange multiplier generator coupled to the comparator unit and the computation unit, for generating a Lagrange multiplier parameter for use in the computation unit; L) a multi-level trellis memory coupled to the DFD generator, the predetermined motion vector memory, the pre-computed transition costs memory, the predetermined quantization step memory, the controller, and the computation unit.
Claim 40
Independent Claim
189 words
A device for allocating bits for optimal rate/distortion performance in digital video compression, wherein the available bits per frame are allocated among at least two sources of information comprising at least two of: A) displaced frame difference, DFD, information; B) displacement vector field information; and C) segmentation information; wherein the device comprises: D) a DFD generator coupled to receive input from two frame buffer memories, for generating a DFD signal; E) a predetermined motion vector memory; F) a pre-computed transition costs memory; G) a predetermined quantization step size memory; H ) a computation unit, for computing an optimal encoded frame; I ) a predetermined target memory; J ) a comparator unit coupled to receive input from the predetermined target memory and the computation unit, for determining compliance with a predetermined target; K ) a Lagrange multiplier generator coupled to the comparator unit and the computation unit, for generating a Lagrange multiplier parameter for use in the computation unit; L) a multi-level trellis memory coupled to the DFD generator, the predetermined motion vector memory, the pre-computed transition costs memory, the predetermined quantization step memory, the controller, and the computation unit.
Claim 41
Dependent Claim
51 words
The device of claim 36 wherein the device is embodied in a computer-readable memory, arranged and configured for allocating bits for optimal rate/distortion performance in digital video compression, wherein the available bits per frame are allocated among at least two sources of information in accordance with a scheme of claim 36.
Claim 42
Dependent Claim
50 words
The device of claim 36 wherein the device is embodied in a microprocessor, arranged and configured for allocating bits for optimal rate/distortion performance in digital video compression, wherein the available bits per frame are allocated among at least two sources of information in accordance with a scheme of claim 36.
Claim 43
Dependent Claim
53 words
The device of claim 36 wherein the device is embodied in an application specific integrated circuit, arranged and configured for allocating bits for optimal rate/distortion performance in digital video compression, wherein the available bits per frame are allocated among at least two sources of information in accordance with a scheme of claim 36.
Claim 44
Dependent Claim
53 words
The device of claim 36 wherein the device is embodied in a field programmable gate array, arranged and configured for allocating bits for optimal rate/distortion performance in digital video compression, wherein the available bits per frame are allocated among at least two sources of information in accordance with a scheme of claim 36.
References Cited (Backward Citations)
US5297170A
Cited
US5521988A
Cited
US5506686A
Cited
US5691770A
Cited
US5612900A
Cited
US5686963A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-07-06 | 2002-01-05 | 2002-07-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-07-06 | 2006-01-05 | 2006-07-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-07-06 | 2010-01-05 | 2010-07-07 | $7700.00 | Window Closed / Lapsed |