US5585944A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for compressing and decompressing images by subdividing pixel color distributions
Assignee: Apple Inc
•
Filing: 1994-05-10
•
Granted: 1996-12-17
•
Expires: 2014-05-10
Abstract
Abstract The present invention provides methods and apparatus for representing visual images in compressed digital form. A series of digital images is provided to a random access memory and compressed one frame at a time. The compressor of the present invention divides a frame into a predefined number of blocks. Each block is tested to determine whether the block has a homogeneous color distribution. If the block has a homogeneous color distribution as defined by a selected homogeneity test, each pixel in that block is encoded with a single color value. If the block does not have a homogeneous color distribution, the block is split into two distributions, one distribution with a greater luminance than the average luminance of the first distribution and one distribution with a smaller luminance than the average luminance of the first distribution. These distributions are separately tested for homogeneity and the same process is repeated until the region has been resolved into homogeneous distributions. Distributions are then merged to check whether the merged distribution is homogeneous. After merging, pixels in homogeneous distributions are encoded as a single color.
Inventors
- 👤 Arturo A. Rodriguez
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 12:49
CPC Classifications
H; H04; H04N; H04N11/00; H04N11/04; H04N11/042; H04N19/00; H04N19/90; H04N19/96; H04N19/10; H04N19/102; H04N19/13; H04N19/60; H04N19/91
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
137 words
A method for converting an image frame into an encoded data stream, including the steps of: storing said image frame in a memory; associating a group of pixels with a region of said image frame; generating a first color distribution of said group of pixels associated with said region; testing said first color distribution to determine whether said group of pixels associated with said region has a homogeneous color distribution; if said group of pixels associated with said region does not have a homogeneous color distribution, dividing said first color distribution into two or more second color distributions; testing at least one of said second color distributions to determine whether a group of pixels associated with said tested second color distribution has a homogeneous color distribution; encoding a group of pixels associated with a homogeneous color distribution.
Claim 2
Independent Claim
137 words
A method for converting an image frame into an encoded data stream, including the steps of: storing said image frame in a memory; associating a group of pixels with a region of said image frame; generating a first color distribution of said group of pixels associated with said region; testing said first color distribution to determine whether said group of pixels associated with said region has a homogeneous color distribution; if said group of pixels associated with said region does not have a homogeneous color distribution, dividing said first color distribution into two or more second color distributions; testing at least one of said second color distributions to determine whether a group of pixels associated with said tested second color distribution has a homogeneous color distribution; encoding a group of pixels associated with a homogeneous color distribution.
Claim 3
Dependent Claim
23 words
The method of claim 1 wherein said first color distribution comprises a luminance distribution of said group of pixels associated with said region.
Claim 4
Dependent Claim
45 words
The method of claim 1, wherein said group of pixels associated with said region has a homogeneous color distribution, further including the step of associating said region with a region color and encoding said group of pixels associated with said region as said region color.
Claim 5
Dependent Claim
134 words
The method of claim 3, wherein at least one of said groups of pixels associated with said tested second color distributions does not have a homogeneous color distribution, further including the steps of: dividing a tested second color distribution associated with a group of pixels that does not have a homogeneous color distribution into two or more third color distributions; testing at least one of said third color distributions to determine whether a group of pixels associated with said tested third color distribution has a homogeneous color distribution; if said group of pixels associated with said tested third color distribution has a homogeneous color distribution, associating said tested third color distribution with a third distribution color and encoding said group of pixels associated with said tested third color distribution as said third distribution color.
Claim 6
Dependent Claim
30 words
The method of claim 4 wherein each of said second color distributions is tested to determine whether a group of pixels associated with said tested second color distributions is homogeneous.
Claim 7
Dependent Claim
177 words
The method of claim 5 further including the steps of: testing each of said third color distributions to determine whether a group of pixels associated with said tested third color distributions is homogeneous; if at least one of said groups of pixels associated with said tested third color distributions does not have a homogeneous color distribution, then dividing each of said tested third color distributions into two or more fourth color distributions; testing each said fourth color distribution to determine whether a group of pixels associated with said tested fourth color distribution has a homogeneous color distribution; if at least one of said groups of pixels associated with said tested fourth color distributions does not have a homogeneous color distribution, recursively dividing said tested fourth color distributions and testing each resulting color distribution until each tested final color distribution is associated with a group of pixels that has a homogeneous color distribution; associating each final color distribution with a final distribution color and encoding a group of pixels associated with said final color distribution as one color.
Claim 8
Dependent Claim
67 words
The method of claim 3 wherein said step of dividing said first color distribution includes the steps of: calculating an average luminance of said first color distribution; associating a group of pixels that have a greater luminance than said average luminance with a high second color distribution; associating a group of pixels that have a smaller luminance than said average luminance with a low second color distribution.
Claim 9
Independent Claim
531 words
A method for converting an image frame into an encoded data stream, including the steps of: storing said image frame in a memory; associating a group of pixels with a region of said image frame; generating a first color distribution of said group of pixels associated with said region; testing said first color distribution to determine whether said group of pixels associated with said region has a homogeneous color distribution; if said group of pixels associated with said region has a homogeneous color distribution, associating said region with a region color and encoding said group of pixels associated with said region as said region color; if said group of pixels associated with said region does not have a homogeneous color distribution, dividing said first color distribution into two or more second color distributions; testing at least one of said second color distributions to determine whether a group of pixels associated with said tested second color distribution has a homogeneous color distribution; dividing a tested second color distribution associated with a group of pixels that does not have a homogeneous distribution into two or more third color distributions; testing at least one of said third color distributions to determine whether a group of pixels associated with said tested third color distribution has a homogeneous color distribution; if at least one of said groups of pixels associated with said tested third color distributions has a homogeneous color distribution, then if at least one of said groups of pixels associated with said tested second color distributions has a homogeneous color distribution, then merging said tested third color distribution associated with a group of pixels with a homogeneous color distribution with said tested second color distribution to form a first merged color distribution; testing said first merged color distribution to determine whether a group of pixels associated with said first merged color distribution has a homogeneous color distribution; if said group of pixels associated with said first merged color distribution has a homogeneous color distribution, associating said first merged color distribution with a first merged color distribution color and encoding a group of pixels associated with said first merged color distribution as said first merged distribution color; if none of said groups of pixels associated with said tested second color distributions has a homogeneous color distribution, then testing a different third color distribution to determine whether a group of pixels associated with said tested different third color distribution of a homogeneous color distribution; if a group of pixels associated with said different third color distribution has a homogeneous color distribution, then merging said tested third color distribution with said tested different third color distribution to form a second merged color distribution; testing said second merged color distribution to determine whether a group of pixels associated with said second merged color distribution has a homogeneous color distribution; if said group of pixels associated with said second merged color distribution has a homogeneous color distribution, associating said second merged color distribution with a second merged distribution color and encoding said group of pixels associated with said second merged color distribution as said second merged distribution color; encoding a group of pixels associated with a homogeneous color distribution.
Claim 10
Independent Claim
531 words
A method for converting an image frame into an encoded data stream, including the steps of: storing said image frame in a memory; associating a group of pixels with a region of said image frame; generating a first color distribution of said group of pixels associated with said region; testing said first color distribution to determine whether said group of pixels associated with said region has a homogeneous color distribution; if said group of pixels associated with said region has a homogeneous color distribution, associating said region with a region color and encoding said group of pixels associated with said region as said region color; if said group of pixels associated with said region does not have a homogeneous color distribution, dividing said first color distribution into two or more second color distributions; testing at least one of said second color distributions to determine whether a group of pixels associated with said tested second color distribution has a homogeneous color distribution; dividing a tested second color distribution associated with a group of pixels that does not have a homogeneous distribution into two or more third color distributions; testing at least one of said third color distributions to determine whether a group of pixels associated with said tested third color distribution has a homogeneous color distribution; if at least one of said groups of pixels associated with said tested third color distributions has a homogeneous color distribution, then if at least one of said groups of pixels associated with said tested second color distributions has a homogeneous color distribution, then merging said tested third color distribution associated with a group of pixels with a homogeneous color distribution with said tested second color distribution to form a first merged color distribution; testing said first merged color distribution to determine whether a group of pixels associated with said first merged color distribution has a homogeneous color distribution; if said group of pixels associated with said first merged color distribution has a homogeneous color distribution, associating said first merged color distribution with a first merged color distribution color and encoding a group of pixels associated with said first merged color distribution as said first merged distribution color; if none of said groups of pixels associated with said tested second color distributions has a homogeneous color distribution, then testing a different third color distribution to determine whether a group of pixels associated with said tested different third color distribution of a homogeneous color distribution; if a group of pixels associated with said different third color distribution has a homogeneous color distribution, then merging said tested third color distribution with said tested different third color distribution to form a second merged color distribution; testing said second merged color distribution to determine whether a group of pixels associated with said second merged color distribution has a homogeneous color distribution; if said group of pixels associated with said second merged color distribution has a homogeneous color distribution, associating said second merged color distribution with a second merged distribution color and encoding said group of pixels associated with said second merged color distribution as said second merged distribution color; encoding a group of pixels associated with a homogeneous color distribution.
Claim 11
Independent Claim
77 words
The method of claims 1 or 3 wherein said step of testing a color distribution for homogeneity includes the steps of: determining a standard deviation, T, of said color distribution to be tested; determining a standard deviation, S, of a color distribution from which said tested color distribution to be tested was derived; and defining Q as a percentage such that said color distribution to be tested is said to be homogeneous if T<S (Q(1-Q)) 1/2 .
Claim 12
Dependent Claim
42 words
The method of claim 3 wherein said step of associating said first color distribution with a first distribution color includes the steps of generating an average color of said first color distributions and associating said average color with said first color distribution.
Claim 13
Dependent Claim
51 words
The method of claim 1 wherein said step of encoding said group of pixels associated with said region includes the steps of: assigning a number field to indicate that said group of pixels associated with said region has a homogeneous color distribution; assigning a color field to represent said region color.
Claim 14
Dependent Claim
107 words
The method of claim 3 wherein said step of encoding said group of pixels associated with said second color distribution includes the steps of: assigning a number field to indicate the number of distribution colors to be encoded; assigning a color field to represent a distribution color to be encoded and associating a bit pattern with said distribution color to be encoded; encoding a pixel in said region with one of said bit patterns associated with a distribution color such that said pixel associated with a color distribution is encoded with a bit pattern corresponding to the color associated with said color distribution associated with said pixel.
Claim 15
Independent Claim
17 words
The method of claims 1 or 3 wherein at least one of said regions is a square.
Claim 16
Independent Claim
90 words
The method of claims 11 or 12 further including the step of decoding said encoded data stream, said step including the steps of: examining said number field; if said number field indicates a homogeneous region, substituting each pixel in said homogeneous region with a bit pattern in said color field; if said number field does not indicate a homogeneous region, associating each color in said color field with a bit pattern; parsing said encoded pixels into separate portions; substituting for each said separate portion a color associated with said portion.
Claim 17
Independent Claim
165 words
An apparatus for converting an image frame into an encoded data stream, including: storing means for storing said image frame in a memory; first associating means for associating a group of pixels with a region of said image frame; first generating means for generating a first color distribution of said group of pixels associated with said region; first testing means for testing said first color distribution to determine whether said group of pixels associated with said region has a homogeneous color distribution; first dividing means for dividing said first color distribution into two or more second color distributions, said first dividing means operative when said group of pixels associated with said region does not have a homogeneous color distribution; first testing means for testing at least one of said second color distributions to determine whether a group of pixels associated with said tested second color distribution has a homogeneous color distribution; encoding means for encoding a group of pixels associated with a homogeneous color distribution.
Claim 18
Independent Claim
165 words
An apparatus for converting an image frame into an encoded data stream, including: storing means for storing said image frame in a memory; first associating means for associating a group of pixels with a region of said image frame; first generating means for generating a first color distribution of said group of pixels associated with said region; first testing means for testing said first color distribution to determine whether said group of pixels associated with said region has a homogeneous color distribution; first dividing means for dividing said first color distribution into two or more second color distributions, said first dividing means operative when said group of pixels associated with said region does not have a homogeneous color distribution; first testing means for testing at least one of said second color distributions to determine whether a group of pixels associated with said tested second color distribution has a homogeneous color distribution; encoding means for encoding a group of pixels associated with a homogeneous color distribution.
Claim 19
Dependent Claim
23 words
The apparatus of claim 15 wherein said first color distribution includes a luminance distribution of said group of pixels associated with said region.
Claim 20
Dependent Claim
62 words
The apparatus of claim 15 further including first distribution associating means for associating said region with a region color and second encoding means for encoding said group of pixels associated with said region as said region color, said first distribution associating means and said second encoding means operative when said group of pixels associated with said region has a homogeneous color distribution.
Claim 21
Dependent Claim
21 words
The apparatus of claim 15 further including second associating means for associating said second color distribution with a second distribution color.
Claim 22
Dependent Claim
73 words
The apparatus of claim 17 wherein said dividing means further includes: calculating means for calculating an average luminance for a color distribution to be divided; third associating means for associating a group of pixels that have a greater luminance than said average luminance with a high second color distribution; fourth associating means for associating a group of pixels that have a smaller luminance than said average luminance with a low second color distribution.
Claim 23
Dependent Claim
13 words
The apparatus of claim 17 further including merging means for merging homogeneous distributions.
Claim 24
Dependent Claim
80 words
The apparatus of claim 15 or 17 wherein said first and second testing means further include: first determining means for determining a standard deviation, T, of a color distribution to be tested; second determining means for determining a standard deviation, S, of a color distribution from which said tested color distribution to be tested was derived; and defining means for defining Q as a percentage such that said color distribution is said to be homogeneous if T<S (Q(1-Q)) 1/2 .
Claim 25
Dependent Claim
25 words
The apparatus of claim 17 wherein said second associating means further includes average color generating means for generating an average color of a color distribution.
Claim 26
Dependent Claim
53 words
The apparatus of claim 17 wherein said second encoding means further includes: first assigning means for assigning a number field to represent a number of homogeneous color distributions within said region; second assigning means for assigning a color field to represent a final color or a plurality of final colors to be encoded.
Claim 27
Dependent Claim
76 words
The apparatus of claim 22 wherein second encoding means further includes: bit pattern associating means for associating each of said plurality of final colors with a bit pattern; pixel encoding means for encoding a pixel in said region with one of said bit patterns associated with a color such that said pixel associated with a color distribution is encoded with a bit pattern corresponding to the color associated with said color distribution associated with said pixel.
Claim 28
Dependent Claim
15 words
The apparatus of claim 17 wherein at least one of said regions is a square.
Claim 29
Dependent Claim
37 words
The apparatus of claim 23 further including a decompressor, said decompressor including: examining means for examining said number field; substituting means for substituting each pixel in said homogeneous region with a bit pattern in said color field.
Claim 30
Independent Claim
570 words
An apparatus for converting an image frame into an encoded data stream comprising: storing means used to store said image frame in a memory; first associating means for associating a group of pixels with a region of said image frame; first generating means for generating a first color distribution of said group of pixels associated with said region; first testing means for testing said first color distribution to determine whether said group of pixels associated with said region has a homogeneous color distribution; second associating means, operative when said group of pixels associated with said region has a homogeneous color distribution, for associating said region with a region color and encoding said group of pixels associated with said region as said region color; means operative when said group of pixels associated with said region does not have a homogeneous color distribution for dividing said first color distribution into two or more second color distributions and testing at least one of said second color distributions to determine whether a group of pixels associated with said tested second color distribution has a homogeneous color distribution; dividing means for dividing a tested second color distribution associated with a group of pixels that does not have a homogeneous distribution into two or more third color distributions; second testing means for testing at least one of said third color distributions to determine whether a group of pixels associated with said tested third color distribution has a homogeneous color distribution; merging means operative when at least one of said groups of pixels associated with said tested third color distributions has a homogeneous color distribution for performing the following operations: if at least one of said groups of pixels associated with said tested second color distributions has a homogeneous color distribution, then merging said tested third color distribution associated with a group of pixels with a homogeneous color distribution with said tested second color distribution to form a first merged color distribution; testing said first merged color distribution to determine whether a group of pixels associated with said first merged color distribution has a homogeneous color distribution; if said group of pixels associated with said first merged color distribution has a homogeneous color distribution, associating said first merged color distribution with a first merged color distribution color and encoding a group of pixels associated with said first merged color distribution as said first merged distribution color; if none of said groups of pixels associated with said tested second color distributions has a homogeneous color distribution, then testing a different third color distribution to determine whether a group of pixels associated with said tested different third color distribution has a homogeneous color distribution; if a group of pixels associated with said different third color distribution has a homogeneous color distribution, then merging said tested third color distribution with said tested different third color distribution to form a second merged color distribution; testing said second merged color distribution to determine whether a group of pixels associated with said second merged color distribution has a homogeneous color distribution; if said group of pixels associated with said second merged color distribution has a homogeneous color distribution, associating said second merged color distribution with a second merged distribution color and encoding said group of pixels associated with said second merged color distribution as said second merged distribution color; encoding means for encoding a group of pixels associated with a homogeneous color distribution.
Claim 31
Independent Claim
570 words
An apparatus for converting an image frame into an encoded data stream comprising: storing means used to store said image frame in a memory; first associating means for associating a group of pixels with a region of said image frame; first generating means for generating a first color distribution of said group of pixels associated with said region; first testing means for testing said first color distribution to determine whether said group of pixels associated with said region has a homogeneous color distribution; second associating means, operative when said group of pixels associated with said region has a homogeneous color distribution, for associating said region with a region color and encoding said group of pixels associated with said region as said region color; means operative when said group of pixels associated with said region does not have a homogeneous color distribution for dividing said first color distribution into two or more second color distributions and testing at least one of said second color distributions to determine whether a group of pixels associated with said tested second color distribution has a homogeneous color distribution; dividing means for dividing a tested second color distribution associated with a group of pixels that does not have a homogeneous distribution into two or more third color distributions; second testing means for testing at least one of said third color distributions to determine whether a group of pixels associated with said tested third color distribution has a homogeneous color distribution; merging means operative when at least one of said groups of pixels associated with said tested third color distributions has a homogeneous color distribution for performing the following operations: if at least one of said groups of pixels associated with said tested second color distributions has a homogeneous color distribution, then merging said tested third color distribution associated with a group of pixels with a homogeneous color distribution with said tested second color distribution to form a first merged color distribution; testing said first merged color distribution to determine whether a group of pixels associated with said first merged color distribution has a homogeneous color distribution; if said group of pixels associated with said first merged color distribution has a homogeneous color distribution, associating said first merged color distribution with a first merged color distribution color and encoding a group of pixels associated with said first merged color distribution as said first merged distribution color; if none of said groups of pixels associated with said tested second color distributions has a homogeneous color distribution, then testing a different third color distribution to determine whether a group of pixels associated with said tested different third color distribution has a homogeneous color distribution; if a group of pixels associated with said different third color distribution has a homogeneous color distribution, then merging said tested third color distribution with said tested different third color distribution to form a second merged color distribution; testing said second merged color distribution to determine whether a group of pixels associated with said second merged color distribution has a homogeneous color distribution; if said group of pixels associated with said second merged color distribution has a homogeneous color distribution, associating said second merged color distribution with a second merged distribution color and encoding said group of pixels associated with said second merged color distribution as said second merged distribution color; encoding means for encoding a group of pixels associated with a homogeneous color distribution.
References Cited (Backward Citations)
FR2628864A1
Cited
US4980764A
Cited
US5046119A
Cited
US5228098A
Cited
JPH06124343A
Cited
US5319793A
Cited
US5392072A
Cited
US5418714A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-12-17 | 2000-06-17 | 2000-12-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-17 | 2004-06-17 | 2004-12-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-17 | 2008-06-17 | 2008-12-17 | $7700.00 | Window Closed / Lapsed |