US5870502A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for a multiresolution transform of digital image information
Assignee: Columbia University
•
Filing: 1996-04-08
•
Granted: 1999-02-09
•
Expires: 2016-04-08
Abstract
Abstract Digital image data is encoded and compressed by a technique which combines the advantages of both wavelet and fractal encoding. The technique produces an encoded image which can be efficiently matched to other compressed images in order to identify the image being processed. The encoding technique spatially decimates the images at numerous frequency scales produced by wavelet transformations and forms blocks comprising of groups of pixels at each frequency scales. The average modulus values and average angle values of the data in each of the blocks are compared to the next higher scale. Each frequency scale is then encoded for the blocks which have corresponding matching blocks in the adjacent scale. The technique provides the edge retention benefits of wavelet and the compression benefits fractal encoding and also accelerates the matching process between the scales. A decoding technique which includes a synthetic edge procedure is used to reconstruct the image. Video encoding can also be done using a variation of the encoding technique.
Inventors
- 👤 Robert J. Bonneau
- 👤 Henry E. Meadows
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 20:44
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/10; H04N19/169; H04N19/186; G; G06; G06V; G06V10/00; G06V10/70; G06V10/74; G06V10/75; G06V10/751; G06V10/7515; G06V40/00; G06V40/10; G06V40/16; G06V40/168; H04N19/60; H04N19/61; H04N19/619; H04N19/63; H04N19/64; H04N19/645; H04N19/90; H04N19/99; H04N19/20
Claims Analysis
Total Claims: 44
Claim 1
Independent Claim
110 words
A method for processing digital image data comprising the steps of: spatially decomposing said image data into frequency scales of decreasing frequencies; forming edge point representations at each of said frequency scale, including a lowest frequency scale; dividing each said point representations of each of said frequency scales into blocks; computing the normalized average modulus and angle values of each of said blocks; matching said average modulus and angle values from said blocks of each of said frequency scales, except said lowest frequency scale, to said blocks of said next lower frequency scale; storing information describing said matching blocks; and storing a spatially decimated representation at said lowest frequency scale.
Claim 2
Independent Claim
110 words
A method for processing digital image data comprising the steps of: spatially decomposing said image data into frequency scales of decreasing frequencies; forming edge point representations at each of said frequency scale, including a lowest frequency scale; dividing each said point representations of each of said frequency scales into blocks; computing the normalized average modulus and angle values of each of said blocks; matching said average modulus and angle values from said blocks of each of said frequency scales, except said lowest frequency scale, to said blocks of said next lower frequency scale; storing information describing said matching blocks; and storing a spatially decimated representation at said lowest frequency scale.
Claim 3
Dependent Claim
32 words
The method of claim 1, wherein during said matching step, said blocks of said frequency scale being matched are range blocks and said blocks of said next higher scale are domain blocks.
Claim 4
Dependent Claim
22 words
The method of claim 1, wherein said spatially decomposing step uses a combined wavelet and gradient transformation function to perform said step.
Claim 5
Dependent Claim
18 words
The method of claim 3, wherein said wavelet transformation function is based on a quadratic spline basis set.
Claim 6
Dependent Claim
21 words
The method of claim 1, wherein said representations at each frequency scale includes high frequency representation and a low frequency representation.
Claim 7
Dependent Claim
17 words
The method of claim 5, wherein said matching step is only performed on said high frequency representations.
Claim 8
Dependent Claim
20 words
The method of claim 5, wherein said representation at said spatially decimated lowest frequency scale is a low frequency representation.
Claim 9
Dependent Claim
55 words
The method of claim 5 further comprising the steps of: chain coding said high frequency representations in each of said frequency scales to indicate an object; matching features of said object across said frequency scales; preserving only those said matched features which satisfy a predetermined condition; and identifying said preserved features using other stored features.
Claim 10
Dependent Claim
15 words
The method of claim 8, wherein said matching step is performed using a Lipschitz equation.
Claim 11
Dependent Claim
22 words
The method of claim 8, wherein a Lipschitz equation is used in said matching step to remove noise from said encoded image.
Claim 12
Dependent Claim
19 words
The method of claim 8, wherein said predetermined condition in said preserving step is based on a Lipschitz equation.
Claim 13
Dependent Claim
23 words
The method of claim 8, wherein said predetermined condition in said preserving step is based on modulus values associated with said image data.
Claim 14
Dependent Claim
18 words
The method of claim 8, wherein said identifying step is performed using a range block centroid matching scheme.
Claim 15
Dependent Claim
19 words
The method of claim 1, wherein said matching steps includes sorting said average modulus values to increase matching efficiencies.
Claim 16
Dependent Claim
19 words
The method of claim 1, wherein said matching steps includes sorting said average angle values to increase matching efficiencies.
Claim 17
Dependent Claim
14 words
The method of claim 1, wherein said spatially decomposing step compresses said image data.
Claim 18
Dependent Claim
23 words
The method of claim 1, wherein said edge point representations are formed comprising the step of calculating the derivative of a transformation function.
Claim 19
Independent Claim
80 words
A method for compressing digital image data combining wavelet and block encoding techniques comprising the steps of: spatially decomposing said image into frequency scales of decreasing frequencies; matching domain and range blocks representing said image from each said frequency scales except said lowest frequency scale, to said blocks of said next lower frequency scale using the normalized average modulus and angle values of each said block; and storing information describing said matched domain and range blocks for each said scale.
Claim 20
Independent Claim
80 words
A method for compressing digital image data combining wavelet and block encoding techniques comprising the steps of: spatially decomposing said image into frequency scales of decreasing frequencies; matching domain and range blocks representing said image from each said frequency scales except said lowest frequency scale, to said blocks of said next lower frequency scale using the normalized average modulus and angle values of each said block; and storing information describing said matched domain and range blocks for each said scale.
Claim 21
Dependent Claim
19 words
The method of claim 18, wherein said spatially decomposing step uses a wavelet transformation function to perform said step.
Claim 22
Dependent Claim
18 words
The method of claim 19, wherein said wavelet transformation function is based on a quadratic spline basis set.
Claim 23
Dependent Claim
18 words
The method of claim 18, wherein each said frequency scale includes high frequency components of said image data.
Claim 24
Dependent Claim
16 words
The method of claim 21, wherein said matching step is performed on said high frequency components.
Claim 25
Dependent Claim
19 words
The method of claim 18, wherein said matching step includes sorting said average modulus values to increase matching efficiencies.
Claim 26
Dependent Claim
19 words
The method of claim 18, wherein said matching step includes sorting said average angle values to increase matching efficiencies.
Claim 27
Dependent Claim
21 words
The method of claim 18, wherein said spatially decompressing step comprises the step of calculating the derivative of a transformation function.
Claim 28
Independent Claim
165 words
A method for processing compressed digital image data representing an original image, wherein said image data has been spatially decomposed into a plurality of frequency scales each having a low frequency representation and high frequency point representation and wherein said high frequency point representations were encoded at least by matching average modulus and angle values of portions of said high frequency point representations between adjacent said frequency scales, the method comprising the steps of: a. decoding said encoded representation in said lowest frequency scale; b. decoding a high frequency point representation at each of said frequency scales; c. transforming said decoded low and high frequency representations for each of said frequency scales into a corresponding representation in the next higher frequency scale; d. adding said transformed low frequency image and said transformed high frequency image to produce a new low frequency image at the next highest scale; and e. repeating steps c and d until said new low frequency image closely approximates said original image.
Claim 29
Independent Claim
165 words
A method for processing compressed digital image data representing an original image, wherein said image data has been spatially decomposed into a plurality of frequency scales each having a low frequency representation and high frequency point representation and wherein said high frequency point representations were encoded at least by matching average modulus and angle values of portions of said high frequency point representations between adjacent said frequency scales, the method comprising the steps of: a. decoding said encoded representation in said lowest frequency scale; b. decoding a high frequency point representation at each of said frequency scales; c. transforming said decoded low and high frequency representations for each of said frequency scales into a corresponding representation in the next higher frequency scale; d. adding said transformed low frequency image and said transformed high frequency image to produce a new low frequency image at the next highest scale; and e. repeating steps c and d until said new low frequency image closely approximates said original image.
Claim 30
Dependent Claim
25 words
The method of claim 26, wherein said coded high frequency representations include chain coded data and said decoding step b includes a synthetic edge procedure.
Claim 31
Dependent Claim
15 words
The method of claim 26, wherein said decoding step a is accomplished with fractal techniques.
Claim 32
Dependent Claim
25 words
The method of claim 26, further including the step of comparing image information to a threshold in order to remove said information from said image.
Claim 33
Dependent Claim
25 words
The method of claim 26, wherein said high frequency point representations include chain coded data and said decoding step b uses said chain coded data.
Claim 34
Dependent Claim
23 words
The method of claim 26, wherein said point representations include blocks and said decode step b uses an average modulus value for decoding.
Claim 35
Dependent Claim
23 words
The method of claim 26, wherein said point representations include blocks and said decode step b uses an average angle value for decoding.
Claim 36
Independent Claim
128 words
A system for processing digital image data comprising: an image recorder for recording an image; a digitizer for converting said recorded image as said image data; at least one first processor which spatially decomposes said image data into frequency scales of decreasing frequencies, forms edge point representations at each said frequency scale, including a lowest frequency scale, for dividing said point representations of each said frequency scales into blocks, computes the average modulus and angle values of each of said blocks, matches said average modulus and angle values from said blocks of each of said frequency scales, except said lowest frequency scale, to said blocks of said next lower frequency scale; a storage medium for storing information describing said matching blocks; and a monitor to display said image.
Claim 37
Independent Claim
128 words
A system for processing digital image data comprising: an image recorder for recording an image; a digitizer for converting said recorded image as said image data; at least one first processor which spatially decomposes said image data into frequency scales of decreasing frequencies, forms edge point representations at each said frequency scale, including a lowest frequency scale, for dividing said point representations of each said frequency scales into blocks, computes the average modulus and angle values of each of said blocks, matches said average modulus and angle values from said blocks of each of said frequency scales, except said lowest frequency scale, to said blocks of said next lower frequency scale; a storage medium for storing information describing said matching blocks; and a monitor to display said image.
Claim 38
Dependent Claim
21 words
The system of claim 33, wherein said first processor calculates the derivative of a transformation function while forming edge point representations.
Claim 39
Dependent Claim
38 words
The system of claim 33, further comprising: a storage medium containing a database of image data to be used for pattern matching; at least one second processor for matching said information describing said matching blocks to said database.
Claim 40
Dependent Claim
15 words
The system of claim 33, wherein said first and second processors are the same processor.
Claim 41
Dependent Claim
22 words
The system of claim 33, further comprising a databus for connecting said storage medium and said second processor to said first processor.
Claim 42
Dependent Claim
16 words
The system of claim 37, further comprising a separate third processor for decoding said image data.
Claim 43
Dependent Claim
18 words
The system of claim 38, further comprising a databus for connecting said third processor to said first processor.
Claim 44
Dependent Claim
18 words
The system of claim 38, further comprising a network for connecting said third processor to said first processor.
References Cited (Backward Citations)
US5065447A
Cited
US5347600A
Cited
US5454051A
Cited
US5510838A
Cited
US5398067A
Cited
US5416856A
Cited
US5497435A
Cited
US5537493A
Cited
US5577134A
Cited
US5600373A
Cited
US5604824A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-08 | 2002-08-10 | 2003-02-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-08 | 2006-08-10 | 2007-02-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-08 | 2010-08-10 | 2011-02-09 | $7700.00 | Window Closed / Lapsed |