US5343539A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for spatial domain image compression
Assignee: Individual
•
Filing: 1992-07-27
•
Granted: 1994-08-30
•
Expires: 2012-07-27
Abstract
Abstract A method of spatial domain image compression comprises splitting the image up into a plurality of 2*2 sub-blocks, and then compressing each sub-block where this can be done without unacceptable loss of detail by encoding it to either 1, 2, or 3 intensity values. On a second pass, the sub-blocks can themselves be concatenated into larger-sub-blocks, so achieving further compression, and those larger-sub-blocks can on a third pass be concatenated into still-larger-sub-blocks. The computational time required by the algorithm is low, both for compression and for decompression.
Inventors
- 👤 Yiu K. Chan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 23:24
CPC Classifications
G; G06; G06T; G06T9/00; G06T9/005; H; H04; H04N; H04N19/00; H04N19/10; H04N19/102; H04N19/13; H04N19/60; H04N19/90; H04N19/91
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
234 words
A method of spatial domain image compression comprising: a. taking a stored record of an image consisting of a plurality of pixels, each pixel having a respective stored intensity value: b. for a sub-block b 1 having p 1 pixels, determining the amount of variability between the p 1 pixel intensities within the sub-block; c. compressing the sub-block b 1 , c1. by using a single intensity value I 1 to represent the intensities of the p 1 pixels in sub-block b 1 if the absolute difference between the intensity of each p 1 pixel is less than a first predetermined value; otherwise, c2. by using two intensity values I 1 ,I 2 to represent the intensities of the pixels in sub-block b 1 if a first sum of squares of differences of the p 1 pixels is less than a second predetermined value; otherwise, c3. by using intensity values from I 3 to I.sub.(p1-1) to represent the intensities of the p 1 pixels in sub-block b 1 up until a corresponding sum of squares of differences of the p 1 pixels is less than a corresponding value, c4. recording values representative of q 1 intensities; d. repeating steps b and c through c4 for successive sub-blocks b 2 , b 3 . . . of respectively of p 2 , p 3 . . . pixels until the entire image has been processed.
Claim 2
Independent Claim
234 words
A method of spatial domain image compression comprising: a. taking a stored record of an image consisting of a plurality of pixels, each pixel having a respective stored intensity value: b. for a sub-block b 1 having p 1 pixels, determining the amount of variability between the p 1 pixel intensities within the sub-block; c. compressing the sub-block b 1 , c1. by using a single intensity value I 1 to represent the intensities of the p 1 pixels in sub-block b 1 if the absolute difference between the intensity of each p 1 pixel is less than a first predetermined value; otherwise, c2. by using two intensity values I 1 ,I 2 to represent the intensities of the pixels in sub-block b 1 if a first sum of squares of differences of the p 1 pixels is less than a second predetermined value; otherwise, c3. by using intensity values from I 3 to I.sub.(p1-1) to represent the intensities of the p 1 pixels in sub-block b 1 up until a corresponding sum of squares of differences of the p 1 pixels is less than a corresponding value, c4. recording values representative of q 1 intensities; d. repeating steps b and c through c4 for successive sub-blocks b 2 , b 3 . . . of respectively of p 2 , p 3 . . . pixels until the entire image has been processed.
Claim 3
Dependent Claim
17 words
A method as claimed in claim 1 in which the sub-blocks have the same number of pixels.
Claim 4
Dependent Claim
15 words
A method as claimed in claim 2 in which the sub-blocks are the same shape.
Claim 5
Dependent Claim
13 words
A method as claimed in claim 3 in which the sub-blocks are square.
Claim 6
Dependent Claim
15 words
A method as claimed in claim 4 in which the sub-blocks are 2*2 pixel sub-images.
Claim 7
Independent Claim
31 words
A method as claimed in any one of the preceding claims in which the amount of variability is determined by calculating the maximum difference between the pixel intensities within the sub-block.
Claim 8
Dependent Claim
179 words
The method of claim 5, wherein the step of compressing sub-block b 1 comprises the steps of: using a single intensity value I 1 to represent the four intensities of the p 1 pixels in sub-block b 1 if the absolute difference between the intensity of each p 1 pixel is less than a first predetermined value; otherwise, using two intensity values I 1 , I 2 to represent the four intensities of the p 1 pixels in sub-block b 1 if a first sum of squares of differences of the p 1 pixels is less than a second predetermined value; otherwise, using three intensity values I 1 , I 2 , I 3 to represent the four intensities of the p 1 pixels in sub-block b 1 if a second sum of squares of differences of the p 1 pixels is less than a third predetermined value; otherwise, using four intensity values I 1 , I 2 , I 3 , I 4 to represent the four intensities of the p 1 pixels in sub-block b 1 .
Claim 9
Dependent Claim
42 words
A method as claimed in claim 1 in which the amount of variability is determined by calculating a plurality of sums of squares of intensities of different combinations of pixels within the sub-block, and taking the lowest sum of squares thus calculated.
Claim 10
Dependent Claim
127 words
A method as claimed in claim 1 including the further Steps e to g: e. for a larger-sub-block B 1 comprising a plurality of contiguous sub-blocks b, determining the amount of variability between the intensities recorded in respect of the sub-blocks b; f. compressing the larger-sub-block B 1 by applying the method of steps c through c4 to the plurality of contiguous sub-blocks b by recording values representative of Q 1 intensities, where Q 1 is less than the total number of intensities recorded in respect of the sub-blocks and is a function of the amount of variability determined in step e; g. repeating steps e and f for successive larger sub-blocks B 2 , B 3 . . . until the entire image has been reprocessed.
Claim 11
Dependent Claim
20 words
A method as claimed in claim 9 in which each larger-sub-block consists of four 2*2 sub-blocks in a square configuration.
Claim 12
Dependent Claim
41 words
A method as claimed in claim 9 or claim 10 including the further step h: h. repeating steps e to g with the respective differences having been considered in respect of still-larger-sub-blocks, each still-larger-sub-block comprising a plurality of contiguous larger-sub-blocks B.
Claim 13
Dependent Claim
19 words
A method as claimed in claim 11 in which each still-larger-sub-block consists of four larger-sub-blocks in a square configuration.
Claim 14
Dependent Claim
49 words
A method as claimed in claim 9 in which the larger-sub-block or the still-larger-sub-block is not considered for further compression at Step f unless all the sub-blocks making up the larger-sub-block, or all the larger-sub-blocks making up the still-larger-sub-block, respectively, are themselves each encoded to a single intensity value.
Claim 15
Dependent Claim
26 words
A method as claimed in claim 13 in which the larger-sub-block or the still-larger-sub-block, if compressed at Step f, is encoded to a single intensity value.
Claim 16
Dependent Claim
19 words
A method as claimed in claim 1 including the final step of further compressing the image by DPCM techniques.
Claim 17
Dependent Claim
23 words
A method as claimed in claim 1 including the final step of further compressing the image by encoding according to Huffman encoding techniques.
Claim 18
Dependent Claim
35 words
A method as claimed in claim 1 in which the sub-block is encoded to a single intensity value if the maximum difference between the individual pixel intensity values is less than a cut-off value (V1).
Claim 19
Dependent Claim
24 words
A method as claimed in claim 1 in which the sub-block is encoded to dual intensity according to a algorithms, and a look-up table.
Claim 20
Dependent Claim
24 words
A method as claimed in claim 1 in which the sub-block is encoded to triple intensity according to a algorithm, and a look-up table.
Claim 21
Dependent Claim
15 words
A method as claimed in claim 1 in combination with decompressing the image after compression.
Claim 22
Dependent Claim
18 words
A method as claimed in claim 20, in which the decompression includes interpolation across boundaries of adjacent sub-blocks.
Claim 23
Dependent Claim
55 words
A method as claimed in claim 21 in which during interpolation: ______________________________________
a a b b a a b b
a a b b becomes a w x b
c c d d → c y z d
c c d d c c d d
______________________________________ where w, x, y, z are interpolated values.
Claim 24
Dependent Claim
41 words
A method as claimed in claim 20, in which the decompression includes enlargement of the image by a factor of E, the enlargement being achieved by replacing each single pixel in the reconstituted image with a block of E*E identical pixels.
Claim 25
Dependent Claim
17 words
A method as claimed in claim 23 including interpolating across boundaries between adjacent sub-blocks, after the enlargement.
Claim 26
Independent Claim
221 words
A method of spatial domain image compression comprising: a. taking a stored record of an image consisting of a plurality of pixels, each pixel having a respective stored intensity value; b. dividing the image up into a plurality of sub-blocks, each consisting of p pixels; compressing each sub-block c1. by selectively encoding it to one of 1, 2, 3 . . . (p-1) intensity values by using a single intensity value I 1 to represent the intensities of the p pixels if the absolute difference between the intensity of each p pixel is less than a first predetermined value; otherwise, c2. by using two intensity values I 1 ,I 2 to represent the intensities of the p pixels if a first sum of squares of differences of the p pixels is less than a second predetermined value; otherwise, c3. by using three intensity values I 1 ,I 2 ,I 3 to represent the intensities of the p pixels if a second sum of squares of differences of the p pixels is less than a third predetermined value; otherwise, c4. by using intensity values from four to (p-1) intensity values I 1 ,I 2 , . . . I.sub.(p-1) to represent the intensities of the p pixels up until a corresponding sum of squares of differences is less than a corresponding value.
Claim 27
Independent Claim
221 words
A method of spatial domain image compression comprising: a. taking a stored record of an image consisting of a plurality of pixels, each pixel having a respective stored intensity value; b. dividing the image up into a plurality of sub-blocks, each consisting of p pixels; compressing each sub-block c1. by selectively encoding it to one of 1, 2, 3 . . . (p-1) intensity values by using a single intensity value I 1 to represent the intensities of the p pixels if the absolute difference between the intensity of each p pixel is less than a first predetermined value; otherwise, c2. by using two intensity values I 1 ,I 2 to represent the intensities of the p pixels if a first sum of squares of differences of the p pixels is less than a second predetermined value; otherwise, c3. by using three intensity values I 1 ,I 2 ,I 3 to represent the intensities of the p pixels if a second sum of squares of differences of the p pixels is less than a third predetermined value; otherwise, c4. by using intensity values from four to (p-1) intensity values I 1 ,I 2 , . . . I.sub.(p-1) to represent the intensities of the p pixels up until a corresponding sum of squares of differences is less than a corresponding value.
Claim 28
Dependent Claim
38 words
A method as claimed in claim 25 including the further Step d: d. concatenating contiguous sub-blocks, where each is encoded to a single intensity value, into larger-sub-blocks, the larger-sub-blocks themselves each being encoded to a single intensity value.
Claim 29
Dependent Claim
38 words
A method as claimed in claim 26 including the further Step e: e. concatenating contiguous larger-sub-blocks, where each is encoded to a single intensity value, into still-larger-sub-blocks, the still-larger-sub-blocks themselves each being encoded to a single intensity value.
Claim 30
Independent Claim
22 words
A method as claimed in any one of claims 25-27 in which p=4, and each sub-block comprises a 2*2 square of pixels.
References Cited (Backward Citations)
US3992572A
Cited
US3974325A
Cited
US4150401A
Cited
US4319267A
Cited
US4409623A
Cited
US5073966A
Cited
US4742558A
Cited
US4885786A
Cited
US4723298A
Cited
US4797741A
Cited
US4803558A
Cited
US4788498A
Cited
US4768082A
Cited
US4947447A
Cited
US4903128A
Cited
US4965843A
Cited
US4853778A
Cited
US4965754A
Cited
US4944023A
Cited
US4885636A
Cited
US5038389A
Cited
US5093872A
Cited
US5163104A
Cited
US4903138A
Cited
US5127064A
Cited
US5101443A
Cited
US5086489A
Cited
US5065447A
Cited
US5014134A
Cited
US5001559A
Cited
US5007001A
Cited
US5068911A
Cited
US5107345A
Cited
US5022091A
Cited
US5166987A
Cited
US5020121A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-08-29 | 1998-02-28 | 1998-08-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-08-29 | 2002-02-28 | 2002-08-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-08-29 | 2006-02-28 | 2006-08-30 | $7700.00 | Window Closed / Lapsed |