Patent US6069977A successfully refreshed from Google Patents.
US6069977A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Image compression method using wavelet transform techniques
Assignee: Samsung Electronics Co Ltd
•
Filing: 1996-01-19
•
Granted: 2000-05-30
•
Expires: 2016-01-19
Abstract
Abstract An image compression method is provided which uses a wavelet transform technique to generate transform coefficients relating to an input image. Furthermore, the method generates and encodes an efficient tree structure of the transform coefficients by performing the following steps. First, transform coefficients are obtained by transforming an input image in accordance with the wavelet transforming technique. Then, a quantizing interval which minimizes quantization errors is determined for a predetermined step size and is determined according to statistical characteristics of the input image. Then, a simple tree structure is generated based on the transform coefficients, and such tree structure is modified by using statistical characteristics of the transform coefficients to produce a monotonically decreasing tree structure. The resultant tree structure is modified by limiting a maximum height difference between parent nodes and child nodes of the tree structure to produce the tree list. In addition, the transform coefficients may be quantized based on the quantizing interval to produce quantized transform coefficients, and the modified tree list and the quantized transform coefficients may be arithmeticlly coded.
Inventors
- 👤 Youg-kyu Kim
- 👤 Kyu-tae Park
- 👤 Im-geun Lee
- 👤 Jong-sik Kim
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 16:06
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/60; H04N19/63; H04N19/64; H04N19/647; H04N19/10; H04N19/102; H04N19/124
Claims Analysis
Total Claims: 28
Claim 1
Independent Claim
198 words
An image compression method which uses a wavelet transform technique and which converts an input image into coded data of an output compressed image, comprising the steps of: (a) inputting said input image and obtaining transform coefficients by transforming said input image in accordance with said wavelet transforming technique; (b) determining a quantizing interval which minimizes quantization errors in a predetermined step size, wherein said quantizing interval is determined according to statistical characteristics of said input image; (c) generating a simple tree structure based on said transform coefficients; (d) modifying said simple tree structure by using statistical characteristics of said transform coefficients to produce a monotonically decreasing tree structure, wherein said monotonically decreasing tree structure comprises a parent node and child nodes which correspond to said parent node; (e) modifying said monotonically decreasing tree structure by limiting a maximum height difference between said parent node and said child nodes to produce a modified tree list; (f) quantizing said transform coefficients based on said quantizing interval to produce quantized transform coefficients; and (g) arithmetically coding said modified tree list and said quantized transform coefficients to produce said coded data, wherein said coded data corresponds to said output compressed image.
Claim 2
Dependent Claim
198 words
An image compression method which uses a wavelet transform technique and which converts an input image into coded data of an output compressed image, comprising the steps of: (a) inputting said input image and obtaining transform coefficients by transforming said input image in accordance with said wavelet transforming technique; (b) determining a quantizing interval which minimizes quantization errors in a predetermined step size, wherein said quantizing interval is determined according to statistical characteristics of said input image; (c) generating a simple tree structure based on said transform coefficients; (d) modifying said simple tree structure by using statistical characteristics of said transform coefficients to produce a monotonically decreasing tree structure, wherein said monotonically decreasing tree structure comprises a parent node and child nodes which correspond to said parent node; (e) modifying said monotonically decreasing tree structure by limiting a maximum height difference between said parent node and said child nodes to produce a modified tree list; (f) quantizing said transform coefficients based on said quantizing interval to produce quantized transform coefficients; and (g) arithmetically coding said modified tree list and said quantized transform coefficients to produce said coded data, wherein said coded data corresponds to said output compressed image.
Claim 3
Dependent Claim
90 words
An image compression method according to claim 1, wherein said step (b) of determining said quantizing interval comprises the steps of: (b1) obtaining a density function p(x) based on a histogram of said transform coefficients, wherein said density function p(x) is a function of x and wherein x corresponds to data relating to said input image; (b2) manipulating said density function p(x) such that said density function approximates a piece wise linear function; and (b3) determining said quantizing interval having minimal quantization errors based on said piece wise liner function.
Claim 4
Dependent Claim
74 words
An image compression method according to claim 2, wherein said quantizing interval satisfies the equation: ##EQU14## wherein said density function p(x) equals ax+b, a and b are arbitrary constants, k is an integer, G is said predetermined step size, r is a constant determined by said statistical characteristics of said input image and said predetermined step size G, and kG is a quantization value, and wherein said quantizing interval is defined by [kG-r, (k+1)G-r)].
Claim 5
Dependent Claim
177 words
An image compression method according to claim 1, wherein said step (c) of generating said simple tree structure comprises the step of: (c1) determining a height h(C ij ) of said transform coefficients C ij , wherein said height h(C ij ) satisfies the equation: ##EQU15## wherein said height h(C ij ) equals zero if |C ij |<G-r and ∃m ε Dc ij for |m|≦G, wherein said height h(C ij ) equals NULL if |C ij |<G-r and ∀m ε Dc ij for |m|<G, wherein said height h(C ij ) is deemed not to exist if said height h(C ij ) equals NULL, and wherein Dc ij represents sets of values of said child nodes respectively corresponding to said transform coefficients C ij , G equals said predetermined step size, r is a constant determined by said statistical characteristics of said input image and said predetermined step size G, i equals a first set of integers, j equals a second set of integers, and m is an element of said sets of values of said child nodes.
Claim 6
Dependent Claim
65 words
An image compression method according to claim 4, wherein said step (d) of modifying said simple tree structure to produce said monotonically decreasing tree structure comprises the step of: (d1) modifying tree information T(i,j) which corresponds to said transform coefficient C ij and which is contained in said simple tree structure, wherein said tree information T(i,j) is modified in accordance with the following equation: ##EQU16##
Claim 7
Dependent Claim
115 words
An image compression method according to claim 5, wherein said step (e) of modifying said monotonically decreasing tree structure to produce said modified tree list comprises the steps of: (e1) limiting a height difference Diff(C ij ) between said parent node and said child nodes in accordance with the equations: T(i,j)=T(i.sub.p,j.sub.p)-Maxdiff if T(i.sub.p,j.sub.p)-T(i,j)>Maxdiff, and T(i,j)=T(i.sub.p,j.sub.p)-Diff(C.sub.ij) if T(i.sub.p,j.sub.p)-T(i,j)≦Maxdiff, wherein T(i p ,j p ) equals tree information which corresponds to one of said transform coefficients C ij that relates to said parent node, T(i,j) equals tree information which corresponds to said transform coefficients C ij that relate to said child nodes, and Maxdiff is said maximum height difference between said parent node and said child nodes.
Claim 8
Dependent Claim
168 words
An image compression method according to claim 1, wherein said step (g) of arithmetically coding said modified tree list comprises the steps of: (g1) separating a set S of symbols in said modified tree list into N subsets S 1 to S N , wherein said symbols relate to said input image and wherein said subsets S 1 to S N are capable of being independently coded and decoded; (g2) determining a particular subset S i of said subsets S 1 to S N to which particular symbols of said symbols belong based on previously coded information contained within said modified tree list; (g3) coding said particular symbols which correspond to said particular subset S i by an arithmetic coder which corresponds to said particular subset S i ; and (g4) arithmetically coding at least one of said quantized transform coefficients by dividing said at least one of said quantized transform coefficients into code data and size data and arithmetically coding said code data and said size data.
Claim 9
Independent Claim
117 words
A method of generating quantized data based on transform coefficients corresponding to an input image, wherein said method comprises the steps of: (a) inputting said input image; (b) obtaining said transform coefficients by transforming said input image in accordance with a wavelet transform technique; (c) obtaining a density function p(x) based on a histogram of said transform coefficients; (d) manipulating said density function p(x) such that said density function approximates a piece wise linear function; (e) determining a quantizing interval having minimal quantization errors for a predetermined step size based on said piece wise liner function; and (f) quantizing said transform coefficients based on said quantizing interval to produce said quantized data corresponding to said input image.
Claim 10
Independent Claim
117 words
A method of generating quantized data based on transform coefficients corresponding to an input image, wherein said method comprises the steps of: (a) inputting said input image; (b) obtaining said transform coefficients by transforming said input image in accordance with a wavelet transform technique; (c) obtaining a density function p(x) based on a histogram of said transform coefficients; (d) manipulating said density function p(x) such that said density function approximates a piece wise linear function; (e) determining a quantizing interval having minimal quantization errors for a predetermined step size based on said piece wise liner function; and (f) quantizing said transform coefficients based on said quantizing interval to produce said quantized data corresponding to said input image.
Claim 11
Dependent Claim
61 words
A method of quantization according to claim 8, wherein said quantizing interval satisfies the equation: ##EQU17## wherein said density function p(x) equals ax+b, a and b are arbitrary constants, k is a real number, G is said predetermined step size, r is a positive number, and kG is a quantization value, and wherein said quantizing interval is defined by [kG-r, (k+1)G-r)].
Claim 12
Independent Claim
221 words
A method of generating a tree list based on transform coefficients corresponding to an input image, comprising the steps of: (a) inputting said input image; (b) obtaining said transform coefficients by transforming said input image in accordance with a wavelet transform technique; (c) generating a simple tree structure which corresponds to said transform coefficients by determining a height h(C ij ) for each of at least some of said transform coefficients C ij , wherein said height h(C ij ) satisfies the equation: ##EQU18## wherein said height h(C ij ) equals zero if |C ij |<G-r and ∃m ε Dc ij for |m|≧G, wherein said height h(C ij ) equals NULL if |C ij |<G-r and ∀m ε Dc ij for |m|<G wherein said height h(C ij ) is deemed not to exist if said height h(C ij ) equals NULL, and wherein Dc ij represents sets of values of child nodes within said simple tree structure, said child nodes respectively correspond to said transform coefficients C ij , G equals a predetermined step size, r is a positive number, i equals a first set of integers, j equals a second set of integers, and m is an element of said sets of values of said child nodes; and (d) generating simple tree structure data corresponding to said simple tree structure.
Claim 13
Independent Claim
221 words
A method of generating a tree list based on transform coefficients corresponding to an input image, comprising the steps of: (a) inputting said input image; (b) obtaining said transform coefficients by transforming said input image in accordance with a wavelet transform technique; (c) generating a simple tree structure which corresponds to said transform coefficients by determining a height h(C ij ) for each of at least some of said transform coefficients C ij , wherein said height h(C ij ) satisfies the equation: ##EQU18## wherein said height h(C ij ) equals zero if |C ij |<G-r and ∃m ε Dc ij for |m|≧G, wherein said height h(C ij ) equals NULL if |C ij |<G-r and ∀m ε Dc ij for |m|<G wherein said height h(C ij ) is deemed not to exist if said height h(C ij ) equals NULL, and wherein Dc ij represents sets of values of child nodes within said simple tree structure, said child nodes respectively correspond to said transform coefficients C ij , G equals a predetermined step size, r is a positive number, i equals a first set of integers, j equals a second set of integers, and m is an element of said sets of values of said child nodes; and (d) generating simple tree structure data corresponding to said simple tree structure.
Claim 14
Dependent Claim
65 words
A method of generating a tree list according to claim 10, further comprising the step of: (e) modifying said simple tree structure to produce a monotonically decreasing tree structure by modifying tree information T(i,j) which corresponds to said transform coefficients C ij and which is contained in said simple tree structure, wherein said tree information T(i,j) is modified in accordance with the following equation: ##EQU19##
Claim 15
Dependent Claim
126 words
A method of generating a tree list according to claim 11, further comprising the step of: (f) modifying said monotonically decreasing tree structure to produce said tree list by: (f1) limiting a height difference Diff(C ij ) between a parent node and said child nodes in accordance with the equations: T(i,j)=T(i.sub.p,j.sub.p)-Maxdiff if T(i.sub.p,j.sub.p)-T(i,j)>Maxdiff, and T(i,j)=T(i.sub.p,j.sub.p)-Diff(C.sub.ij) if T(i.sub.p,j.sub.p)-T(i,j)≦Maxdiff, wherein T(i p ,j p ) equals tree information which corresponds to one of said transform coefficients C ij that relates to said parent node, T(i,j) equals tree information which corresponds to said transform coefficients C( ij ) that relate to said child nodes, and Maxdiff is a predetermined maximum height difference between said parent node and said child nodes, wherein said tree list corresponds to said input image.
Claim 16
Independent Claim
271 words
A method of coding a tree list corresponding to an input image, wherein said method comprises the steps of: (a) inputting said input image; (b) transforming said input image into transform coefficients based on a wavelet transform technique; (c) generating said tree list based on said transform coefficients; (d) separating a set S of symbols in said tree list into N subsets S 1 to S N , wherein said symbols relate to said input image and wherein said subsets S 1 to S N are capable of being independently coded and decoded; (e) determining a first particular subset S i of said subsets S 1 to S N to which first particular symbols of said symbols belong based on previously coded information which is contained within said tree list; and (f) coding said first particular symbols which correspond to said first particular subset S i by a first arithmetic coder which corresponds to said first particular subset S i , wherein said first arthimetic coder codes said first particular symbols into first coded symbol data that corresponds to said input image; (g) determining a second particular subset S j of said subsets S 1 to S N to which second particular symbols of said symbols belong based on previously coded information which is contained within said tree list; and (h) coding said second particular symbols which correspond to said second particular subset S j by a second arithmetic coder which corresponds to said second particular subset S j , wherein said second arthimetic coder codes said second particular symbols into second coded symbol data that corresponds to said input image.
Claim 17
Independent Claim
271 words
A method of coding a tree list corresponding to an input image, wherein said method comprises the steps of: (a) inputting said input image; (b) transforming said input image into transform coefficients based on a wavelet transform technique; (c) generating said tree list based on said transform coefficients; (d) separating a set S of symbols in said tree list into N subsets S 1 to S N , wherein said symbols relate to said input image and wherein said subsets S 1 to S N are capable of being independently coded and decoded; (e) determining a first particular subset S i of said subsets S 1 to S N to which first particular symbols of said symbols belong based on previously coded information which is contained within said tree list; and (f) coding said first particular symbols which correspond to said first particular subset S i by a first arithmetic coder which corresponds to said first particular subset S i , wherein said first arthimetic coder codes said first particular symbols into first coded symbol data that corresponds to said input image; (g) determining a second particular subset S j of said subsets S 1 to S N to which second particular symbols of said symbols belong based on previously coded information which is contained within said tree list; and (h) coding said second particular symbols which correspond to said second particular subset S j by a second arithmetic coder which corresponds to said second particular subset S j , wherein said second arthimetic coder codes said second particular symbols into second coded symbol data that corresponds to said input image.
Claim 18
Dependent Claim
62 words
A method of coding a tree list according to claim 13, wherein said method further comprises the step of: (i) arithmetically coding a quantized transform coefficient by dividing said quantized transform coefficient into code data and size data and arithmetically coding said code data and said size data, wherein said quantized transform coefficient corresponds to at least one of said transform coefficients.
Claim 19
Dependent Claim
166 words
An image compression method which uses a wavelet transform technique and which converts an input image into an output compressed image, comprising the steps of: (a) inputting said input image and obtaining transform coefficients by transforming said input image in accordance with said wavelet transforming technique; (b) determining a quantizing interval which minimizes quantization errors in a predetermined step size, wherein said quantizing interval is determined according to statistical characteristics of said input image; (c) generating a simple tree structure based on said transform coefficients; (d) modifying said simple tree structure by using statistical characteristics of said transform coefficients to produce a monotonically decreasing tree structure, wherein said monotonically decreasing tree structure comprises a parent node and child nodes which correspond to said parent node; and (e) modifying said monotonically decreasing tree structure by limiting a maximum height difference between said parent node and said child nodes to produce a modified tree list and generating modified tree list data which corresponds to said output compressed image.
Claim 20
Dependent Claim
166 words
An image compression method which uses a wavelet transform technique and which converts an input image into an output compressed image, comprising the steps of: (a) inputting said input image and obtaining transform coefficients by transforming said input image in accordance with said wavelet transforming technique; (b) determining a quantizing interval which minimizes quantization errors in a predetermined step size, wherein said quantizing interval is determined according to statistical characteristics of said input image; (c) generating a simple tree structure based on said transform coefficients; (d) modifying said simple tree structure by using statistical characteristics of said transform coefficients to produce a monotonically decreasing tree structure, wherein said monotonically decreasing tree structure comprises a parent node and child nodes which correspond to said parent node; and (e) modifying said monotonically decreasing tree structure by limiting a maximum height difference between said parent node and said child nodes to produce a modified tree list and generating modified tree list data which corresponds to said output compressed image.
Claim 21
Dependent Claim
90 words
An image compression method according to claim 15, wherein said step (b) of determining said quantizing interval comprises the steps of: (b1) obtaining a density function p(x) based on a histogram of said transform coefficients, wherein said density function p(x) is a function of x and wherein x corresponds to data relating to said input image; (b2) manipulating said density function p(x) such that said density function approximates a piece wise linear function; and (b3) determining said quantizing interval having minimal quantization errors based on said piece wise liner function.
Claim 22
Dependent Claim
74 words
An image compression method according to claim 16, wherein said quantizing interval satisfies the equation: ##EQU20## wherein said density function p(x) equals ax+b, a and b are arbitrary constants, k is an integer, G is said predetermined step size, r is a constant determined by said statistical characteristics of said input image and said predetermined step size G, and kG is a quantization value, and wherein said quantizing interval is defined by [kG-r, (k+1)G-r)].
Claim 23
Dependent Claim
177 words
An image compression method according to claim 15, wherein said step (c) of generating said simple tree structure comprises the step of: (c1) determining a height h(C ij ) of said transform coefficients C ij , wherein said height h(C ij ) satisfies the equation: ##EQU21## wherein said height h(C ij ) equals zero if |C ij |<G-r and ∃m ε Dc ij for |m|≧G, wherein said height h(C ij ) equals NULL if |C ij |<G-r and ∀m ε Dc ij for |m|<G, wherein said height h(C ij ) is deemed not to exist if said height h(C ij ) equals NULL, and wherein Dc ij represents sets of values of said child nodes respectively corresponding to said transform coefficients C ij , G equals said predetermined step size, r is a constant determined by said statistical characteristics of said input image and said predetermined step size G, i equals a first set of integers, j equals a second set of integers, and m is an element of said sets of values of said child nodes.
Claim 24
Dependent Claim
65 words
An image compression method according to claim 18, wherein said step (d) of modifying said simple tree structure to produce said monotonically decreasing tree structure comprises the step of: (d1) modifying tree information T(i,j) which corresponds to said transform coefficient C ij and which is contained in said simple tree structure, wherein said tree information T(i,j) is modified in accordance with the following equation: ##EQU22##20.
Claim 25
Dependent Claim
115 words
An image compression method according to claim 19, wherein said step (e) of modifying said monotonically decreasing tree structure to produce said modified tree list comprises the steps of: (e1) limiting a height difference Diff(C ij ) between said parent node and said child nodes in accordance with the equations: T(i,j)=T(i.sub.p,j.sub.p)-Maxdiff if T(i.sub.p,j.sub.p)-T(i,j)>Maxdiff, and T(i,j)=T(i.sub.p,j.sub.p)-Diff(C.sub.ij) if T(i.sub.p,j.sub.p)-T(i,j)≦Maxdiff, wherein T(i p ,j p ) equals tree information which corresponds to one of said transform coefficients C ij that relates to said parent node, T(i,j) equals tree information which corresponds to said transform coefficients C ij that relate to said child nodes, and Maxdiff is said maximum height difference between said parent node and said child nodes.
Claim 26
Independent Claim
109 words
A method of generating quantized interval data based on transform coefficients corresponding to an input image, wherein said method comprises the steps of: (a) inputting said input image; (b) obtaining said transform coefficients by transforming said input image in accordance with a wavelet transform technique; (c) obtaining a density function p(x) based on a histogram of said transform coefficients; (d) manipulating said density function p(x) such that said density function approximates a piece wise linear function; and (e) determining a quantizing interval having minimal quantization errors for a predetermined step size based on said piece wise liner function to produce said quantized interval data corresponding to said input image.
Claim 27
Independent Claim
109 words
A method of generating quantized interval data based on transform coefficients corresponding to an input image, wherein said method comprises the steps of: (a) inputting said input image; (b) obtaining said transform coefficients by transforming said input image in accordance with a wavelet transform technique; (c) obtaining a density function p(x) based on a histogram of said transform coefficients; (d) manipulating said density function p(x) such that said density function approximates a piece wise linear function; and (e) determining a quantizing interval having minimal quantization errors for a predetermined step size based on said piece wise liner function to produce said quantized interval data corresponding to said input image.
Claim 28
Dependent Claim
61 words
A method of quantization according to claim 21, wherein said quantizing interval satisfies the equation: ##EQU23## wherein said density function p(x) equals ax+b, a and b are arbitrary constants, k is a real number, G is said predetermined step size, r is a positive number, and kG is a quantization value, and wherein said quantizing interval is defined by [kG-r, (k+1)G-r)].
References Cited (Backward Citations)
US5321776A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-30 | 2003-11-29 | 2004-05-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-30 | 2007-11-29 | 2008-05-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-30 | 2011-11-29 | 2012-05-30 | $7700.00 | Window Closed / Lapsed |