US5734755A
Expired / Lapsed
US
⏱️ 0.0 years remaining
JPEG/MPEG decoder-compatible optimized thresholding for image and video signal compression
Assignee: Columbia University
•
Filing: 1994-03-11
•
Granted: 1998-03-31
•
Expires: 2014-03-11
Abstract
Abstract For encoding signals corresponding to still images or video sequences, respective standards known as JPEG and MPEG have been proposed. These standards are based on digital cosine transform (DCT) compression. For economy of transmission, DCT coefficients may be "thresholded" prior to transmission, by dropping the less significant DCT coefficients. While maintaining JPEG or MPEG compatibility, threshold selection for the DCT coefficients of an image or video frame is based on optimizing for minimum distortion for a specified maximum target coding bit rate or, equivalently, for minimized coding bit rate for a specified maximum allowable distortion constraint. In the selection process, a dynamic programming method is used.
Inventors
- 👤 Kannan Ramchandran
- 👤 Martin Vetterli
- 👤 Yanbin Yu
- 👤 Dimitris Anastassiou
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 15:32
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/10; H04N19/189; H04N19/192; H04N19/102; H04N19/132; H04N19/134; H04N19/146; H04N19/147; H04N19/169; H04N19/17; H04N19/176; H04N19/18; H04N19/19; H04N19/60; H04N19/149; H04N19/15; H04N19/152
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
173 words
A method for signal compression in image transmission, comprising: transform coding to obtain an ordered set, T, of JPEG transform coefficients for at least a portion of an image; repeatedly, for different values of a parameter, λ, selecting an ordered subset, S.sub.λ, of the set T of transform coefficients, selection of each ordered subset S.sub.λ being such that, for S=S.sub.λ, a function J(λ)=D(S)+λ·R(S) is minimized over all subsets S of the set T of transform coefficients, wherein D(S) is a measure of image distortion resulting from retaining the subset S as compared with the set T, and wherein R(S) is a minimum bit rate required for transmission of the subset E, repetition being terminated with λ=λ* upon at least approximate leaching of rate-distortion optimality as determined by a function J.sub.min (λ)-λ·R.sub.budget being maximized over λ≧0, wherein J min (λ) is the minimized value of the function J(λ) and wherein R budget is a predetermined maximum target bit rate; and transmitting the finally selected, JPEG compatible subset of transform coefficients over a communications channel.
Claim 2
Independent Claim
173 words
A method for signal compression in image transmission, comprising: transform coding to obtain an ordered set, T, of JPEG transform coefficients for at least a portion of an image; repeatedly, for different values of a parameter, λ, selecting an ordered subset, S.sub.λ, of the set T of transform coefficients, selection of each ordered subset S.sub.λ being such that, for S=S.sub.λ, a function J(λ)=D(S)+λ·R(S) is minimized over all subsets S of the set T of transform coefficients, wherein D(S) is a measure of image distortion resulting from retaining the subset S as compared with the set T, and wherein R(S) is a minimum bit rate required for transmission of the subset E, repetition being terminated with λ=λ* upon at least approximate leaching of rate-distortion optimality as determined by a function J.sub.min (λ)-λ·R.sub.budget being maximized over λ≧0, wherein J min (λ) is the minimized value of the function J(λ) and wherein R budget is a predetermined maximum target bit rate; and transmitting the finally selected, JPEG compatible subset of transform coefficients over a communications channel.
Claim 3
Dependent Claim
42 words
The method of claim 1, wherein repetition is terminated when the difference between a member of a monotonically non-increasing sequence of upper bounds and a member of a monotonically non-decreasing sequence of lower bounds for λ* is less than a predetermined amount.
Claim 4
Dependent Claim
35 words
The method of claim 1, wherein selecting the subset S.sub.λ of transform coefficients comprises (i) finding a last transform coefficient of the subset, and (ii) backtracking to find all transform coefficients preceding the last coefficient.
Claim 5
Independent Claim
181 words
A system for signal compression in image transmission, comprising: coding means for transform coding to obtain an ordered set, T, of JPEG transform coefficients for at least a portion of an image; optimization means for repeatedly, for different values of a parameter, λ, selecting an ordered subset, S.sub.λ, of the set T of transform coefficients, selection of each ordered subset S.sub.λ being such that, for S=.sub.λ, a function J(λ)=D(S)+λ·R(S) is minimized over all subsets B of the set T of transform coefficients, wherein D(S) is a measure of image distortion resulting from retaining the subset S as compared with the set T, and wherein R(S) is a minimum bit rate required for transmission of the subset S, repetition being terminated with λ=λ* upon at least approximate reaching of rate-distortion optimality as determined by a function J.sub.min (λ)-λ·R.sub.budget being maximized over λ≧0, wherein J min (λ) is the minimized value of the function J(λ) and wherein R budget is a predetermined maximum target bit rate; and transmission means for transmitting the finally selected, JPEG-compatible subset of transform coefficients over a communications channel.
Claim 6
Independent Claim
181 words
A system for signal compression in image transmission, comprising: coding means for transform coding to obtain an ordered set, T, of JPEG transform coefficients for at least a portion of an image; optimization means for repeatedly, for different values of a parameter, λ, selecting an ordered subset, S.sub.λ, of the set T of transform coefficients, selection of each ordered subset S.sub.λ being such that, for S=.sub.λ, a function J(λ)=D(S)+λ·R(S) is minimized over all subsets B of the set T of transform coefficients, wherein D(S) is a measure of image distortion resulting from retaining the subset S as compared with the set T, and wherein R(S) is a minimum bit rate required for transmission of the subset S, repetition being terminated with λ=λ* upon at least approximate reaching of rate-distortion optimality as determined by a function J.sub.min (λ)-λ·R.sub.budget being maximized over λ≧0, wherein J min (λ) is the minimized value of the function J(λ) and wherein R budget is a predetermined maximum target bit rate; and transmission means for transmitting the finally selected, JPEG-compatible subset of transform coefficients over a communications channel.
Claim 7
Dependent Claim
48 words
The system of claim 4, wherein the optimization means comprises means for terminating the repetition when the difference between a member of a monotonically non-increasing sequence of upper bounds and a member of a monotonically non-decreasing sequence of lower bounds for λ* is less than a predetermined amount.
Claim 8
Dependent Claim
36 words
The system of claim 4, wherein the optimization means comprises first means for finding a last transform coefficient of the subset S.sub.λ, and second means for backtracking to find all transform coefficients preceding the last coefficient.
Claim 9
Independent Claim
176 words
A method for signal compression in image transmission, comprising: transform coding to obtain an ordered set, T, of MPEG transform coefficients for at least a portion of an image of a video sequence; repeatedly, for different values of a parameter, λ, selecting an ordered subset, λ.sub.λ, of the set T of transform coefficients, selection of each ordered subset S.sub.λ being such that, for S=S.sub.λ, a function J(λ)=D(S)+λ·R(S) is minimized over all subsets S of the set T of transform coefficients, wherein D(S) is a measure of image distortion resulting from retaining the subset S as compared with the set T, and wherein R(S) is a minimum bit rate required for transmission of the subset S, repetition being terminated with λ=λ* upon at least approximate reaching of rate-distortion optimality as determined by a function J.sub.min (λ)-λ·R.sub.budget being maximized over λ≧0, wherein J min (λ) is the minimized value of the function J(λ) and wherein R budget is a predetermined maximum target bit rate; and transmitting the finally selected, MPEG-compatible subset of transform coefficients over a communications channel.
Claim 10
Independent Claim
176 words
A method for signal compression in image transmission, comprising: transform coding to obtain an ordered set, T, of MPEG transform coefficients for at least a portion of an image of a video sequence; repeatedly, for different values of a parameter, λ, selecting an ordered subset, λ.sub.λ, of the set T of transform coefficients, selection of each ordered subset S.sub.λ being such that, for S=S.sub.λ, a function J(λ)=D(S)+λ·R(S) is minimized over all subsets S of the set T of transform coefficients, wherein D(S) is a measure of image distortion resulting from retaining the subset S as compared with the set T, and wherein R(S) is a minimum bit rate required for transmission of the subset S, repetition being terminated with λ=λ* upon at least approximate reaching of rate-distortion optimality as determined by a function J.sub.min (λ)-λ·R.sub.budget being maximized over λ≧0, wherein J min (λ) is the minimized value of the function J(λ) and wherein R budget is a predetermined maximum target bit rate; and transmitting the finally selected, MPEG-compatible subset of transform coefficients over a communications channel.
Claim 11
Dependent Claim
42 words
The method of claim 7, wherein repetition is terminated when the difference between a member of a monotonically non-increasing sequence of upper bounds and a member of a monotonically non-decreasing sequence of lower bounds for λ* is less than a predetermined amount.
Claim 12
Dependent Claim
35 words
The method of claim 7, wherein selecting the subset S.sub.λ of transform coefficients comprises (i) finding a last transform coefficient of the subset, and (ii) backtracking to find all transform coefficients preceding the last coefficient.
Claim 13
Independent Claim
185 words
A system for signal compression in image transmission, comprising: coding means for transform coding to obtain an ordered set, T, of MPEG transform coefficients for at least a portion of an image of a video sequence; optimization means for repeatedly, for different values of a parameter, λ, selecting an ordered subset, S.sub.λ, of the set T of transform coefficients, selection of each ordered subset S.sub.λ being such that, for S=S.sub.λ, a function J(λ)=D(S)+λ·R(S) is minimized over all subsets S of the set T of transform coefficients, wherein D(S) is a measure of image distortion resulting from retaining the subset S as compared with the set T, and wherein R(S) is a minimum bit rate required for transmission of the subset s, repetition being terminated with λ=λ* upon at least approximate reaching of rate-distortion optimality as determined by a function J.sub.min (λ)-λ·R.sub.budget being maximized over λ≧0, wherein J min (λ) is the minimized value of the function J(λ) and wherein R budget is a predetermined maximum target bit rate; and transmission means for transmitting the finally selected, MPEG-compatible subset of transform coefficients over a communications channel.
Claim 14
Independent Claim
185 words
A system for signal compression in image transmission, comprising: coding means for transform coding to obtain an ordered set, T, of MPEG transform coefficients for at least a portion of an image of a video sequence; optimization means for repeatedly, for different values of a parameter, λ, selecting an ordered subset, S.sub.λ, of the set T of transform coefficients, selection of each ordered subset S.sub.λ being such that, for S=S.sub.λ, a function J(λ)=D(S)+λ·R(S) is minimized over all subsets S of the set T of transform coefficients, wherein D(S) is a measure of image distortion resulting from retaining the subset S as compared with the set T, and wherein R(S) is a minimum bit rate required for transmission of the subset s, repetition being terminated with λ=λ* upon at least approximate reaching of rate-distortion optimality as determined by a function J.sub.min (λ)-λ·R.sub.budget being maximized over λ≧0, wherein J min (λ) is the minimized value of the function J(λ) and wherein R budget is a predetermined maximum target bit rate; and transmission means for transmitting the finally selected, MPEG-compatible subset of transform coefficients over a communications channel.
Claim 15
Dependent Claim
48 words
The system of claim 10, wherein the optimization means comprises means for terminating the repetition when the difference between a member of a monotonically non-increasing sequence of upper bounds and a member of a monotonically non-decreasing sequence of lower bounds for λ* is less than a predetermined amount.
Claim 16
Dependent Claim
36 words
The system of claim 10, wherein the optimization means comprises first means for finding a last transform coefficient of the subset S.sub.λ, and second means for backtracking to find all transform coefficients preceding the last coefficient.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-30 | 2001-09-29 | 2002-03-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-30 | 2005-09-29 | 2006-03-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-30 | 2009-09-29 | 2010-03-31 | $7700.00 | Window Closed / Lapsed |