US5448642A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for coding low entrophy data
Assignee: National Aeronautics and Space Administration
•
Filing: 1994-02-14
•
Granted: 1995-09-05
•
Expires: 2014-02-14
Abstract
Abstract A method of lossless data compression for efficient coding of an electronic signal of information sources of very low information rate is disclosed. In this method, S represents a non-negative source symbol set, {s0, s1, s2, . . . sN-1} of N symbols with si=i. The difference between binary digital data is mapped into symbol set S. Consecutive symbols in symbol set S are then paired into a new symbol set GAMMA which defines a non-negative symbol set containing the symbols { gamma m} obtained as the extension of the original symbol set S. These pairs are then mapped into a comma code which is defined as a coding scheme in which every codeword is terminated with the same comma pattern, such as a 1. This allows a direct coding and decoding of the n-bit positive integer binary digital data differences without the use of codebooks.
Inventors
- 👤 Pen-Shu Yeh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 23:15
CPC Classifications
H; H03; H03M; H03M7/00; H03M7/30; G; G06; G06T; G06T9/00; G06T9/005
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
164 words
A method of coding a low entropy image signal generated by an imager comprising: digitizing the image signal of low entropy generated by said imager into an array of digital image data; determining the difference in value between adjacent digital image data points in the array; mapping each said difference in value between said adjacent digital image data in the array into a first non-negative symbol set defined as a set S, {s 0 , s 1 , s 2 , . . . s N-1 } of N symbols with s i =i; grouping consecutive symbols S 0 . . . S N-1 into a second non-negative symbol set defined as a symbol set Γ including the symbols {γm} obtained as the extension of the original symbol set S; and coding said second non-negative symbol set Γ into a comma code so as to generate coded binary digital data representing a compressed image of said low entropy image signal generated by the imager.
Claim 2
Independent Claim
164 words
A method of coding a low entropy image signal generated by an imager comprising: digitizing the image signal of low entropy generated by said imager into an array of digital image data; determining the difference in value between adjacent digital image data points in the array; mapping each said difference in value between said adjacent digital image data in the array into a first non-negative symbol set defined as a set S, {s 0 , s 1 , s 2 , . . . s N-1 } of N symbols with s i =i; grouping consecutive symbols S 0 . . . S N-1 into a second non-negative symbol set defined as a symbol set Γ including the symbols {γm} obtained as the extension of the original symbol set S; and coding said second non-negative symbol set Γ into a comma code so as to generate coded binary digital data representing a compressed image of said low entropy image signal generated by the imager.
Claim 3
Dependent Claim
24 words
The method of claim 1 wherein said grouping of consecutive symbols in said first non-negative symbol set S comprises grouping in groups of two.
Claim 4
Dependent Claim
65 words
The method of claim 2 wherein said step of mapping said groups of two consecutive symbols into said second non-negative symbol set Γ including the symbols {γ m } comprises: taking every two symbols s i , s j from set S and calculating a variable β=i+j; and calculating a variable m s =β(β+1)/2; calculating the subscript m of γ m as m=m s +j.
Claim 5
Dependent Claim
38 words
The method of claim 3 wherein said step of coding said second non-negative symbol set Γ containing the symbols {γ m } into a comma code comprises assigning γ m =m and coding m with the comma code.
Claim 6
Dependent Claim
22 words
The method of claim 4 wherein said comma code of integer m consists is formed of m 0's followed by a 1.
Claim 7
Dependent Claim
174 words
The method of claim 5 further comprising decoding steps comprising: restoring a first set of non-negative symbols γ m by counting the 0's of said comma code; obtaining a variable β and a variable m s using the following logic: ______________________________________
if m = 0 then β = 0
and m.sub.s = 0
if m = 1,2 then β = 1
and m.sub.s = 1
if m = 3,4,5 then β = 2
and m.sub.s = 3
if m = 6,...,9
then β = 3
and m.sub.s = 6
if m = 10,....,14
then β = 4
and m.sub.s = 10
if m = 15,....,20
then β = 5
and m.sub.s = 15
if m = 21,....,28
then β = 6
and m.sub.s = 21
if m = 28,....,35
then β = 7
and m.sub.s = 28
* * *
* * *
* * *;
______________________________________ calculating a variable j=m-m s ; calculating a variable i=β-j; and restoring a second non-negative set of symbols according to s i =i and s j =j.
Claim 8
Dependent Claim
21 words
The method of claim 1, wherein the entropy of the image signal from the imager is substantially less than 1 bits/sample.
Claim 9
Dependent Claim
20 words
The method of claim 7 wherein the entropy of said image signal from the imager is less than 0.75 bits/sample.
Claim 10
Dependent Claim
24 words
The method of claim 7 wherein the entropy of said image signal from the imager is in the range of 0.75 to 1.5 bits/sample.
Claim 11
Dependent Claim
24 words
The method of claim 1 wherein said grouping of consecutive symbols in said first non-negative symbols set S comprises grouping in groups of three.
Claim 12
Dependent Claim
149 words
The method of claim 10 wherein said step of mapping said groups of three consecutive symbols into said second non-negative symbol set Γ containing the symbols {γ m } comprises: taking every 3 symbols s i , s j , s k from set S, and calculating a variable β'=i+j+k and variable β=i+j; calculating variable m s =β(β+1)/2; determining m i using the following logic: ______________________________________
if m = 0 then β' = 0
and m.sub.1 = 0
if m = 1,2,3 then β' = 1
and m.sub.1 = 1
if m = 4,...,9
then β' = 2
and m.sub.1 = 4
if m = 10,....,19
then β' = 3
and m.sub.1 = 10
if m = 20,....,34
then β' = 4
and m.sub.1 = 20
* * *
* * *
* * *;
______________________________________ calculating the subscript m of γ m as m=m s +m i +i.
Claim 13
Dependent Claim
38 words
The method of claim 11 wherein said step of coding said second non-negative symbol set Γ including the symbols {γ m } into a comma code comprises assigning γ m =m and coding m with the comma code.
Claim 14
Dependent Claim
21 words
The method of claim 12 wherein said comma code of integer m is formed of m 0's followed by a 1.
Claim 15
Dependent Claim
91 words
The method of claim 13 further comprising decoding steps comprising: obtaining γ m by counting the 0's of said comma code; obtaining β' and m i from the logic of claim 11; calculating m s +i by m s +i=m=m i ; using the value of m s +i as the value of m in the logic of claim 11, obtaining β and m s ; calculating i from values obtained above; calculating j from β-i; calculating k from β'-β; and assigning s i =i, s j =j, s k =k.
Claim 16
Dependent Claim
19 words
A method as in claim 1, wherein the digital image data in the array is gray-scale digital image data.
Claim 17
Dependent Claim
224 words
A decoding method for decoding a coded low entropy image signal, the low entropy image signal being generated by an imager comprising: receiving a comma code formed of 0's followed by a 1, the comma code being representative of the coded image data, the image data being representative of a low entropy image signal generated by the imager; restoring a first set of non-negative symbols a variable γ m by counting the 0's of said comma code; obtaining a variable β and a variable m s using the following logic: ______________________________________
if m = 0 then β = 0
and m.sub.s = 0
if m = 1,2 then β = 1
and m.sub.s = 1
if m = 3,4,5 then β = 2
and m.sub.s = 3
if m = 6,...,9
then β = 3
and m.sub.s = 6
if m = 10,....,14
then β = 4
and m.sub.s = 10
if m = 15,....,20
then β = 5
and m.sub.s = 15
if m = 21,....,28
then β = 6
and m.sub.s = 21
if m = 28,....,35
then β = 7
and m.sub.s = 28
* * *
* * *
* * *;
______________________________________ calculating a variable j=m-m s ; calculating a variable i=β-j; and restoring a second non-negative set of symbols according to s i =i and s j =j.
Claim 18
Dependent Claim
224 words
A decoding method for decoding a coded low entropy image signal, the low entropy image signal being generated by an imager comprising: receiving a comma code formed of 0's followed by a 1, the comma code being representative of the coded image data, the image data being representative of a low entropy image signal generated by the imager; restoring a first set of non-negative symbols a variable γ m by counting the 0's of said comma code; obtaining a variable β and a variable m s using the following logic: ______________________________________
if m = 0 then β = 0
and m.sub.s = 0
if m = 1,2 then β = 1
and m.sub.s = 1
if m = 3,4,5 then β = 2
and m.sub.s = 3
if m = 6,...,9
then β = 3
and m.sub.s = 6
if m = 10,....,14
then β = 4
and m.sub.s = 10
if m = 15,....,20
then β = 5
and m.sub.s = 15
if m = 21,....,28
then β = 6
and m.sub.s = 21
if m = 28,....,35
then β = 7
and m.sub.s = 28
* * *
* * *
* * *;
______________________________________ calculating a variable j=m-m s ; calculating a variable i=β-j; and restoring a second non-negative set of symbols according to s i =i and s j =j.
Claim 19
Dependent Claim
212 words
Apparatus for coding a low entropy image signal generated by an imager comprising: digitizing means for digitizing the signal of low entropy generated by said imager into an array of digital image data; difference means, operatively connected to the digitizing means, for determining the difference in value between adjacent digital image data points in the array; mapping means, operatively connected to the difference means, for mapping each said difference in value between said adjacent digital image data in the array into a first non-negative symbol set defined as a set S, {S 0 , S 1 , S 2 , . . . S N-1 } of N symbols with s i =i; grouping means, operatively connected to the mapping means, for grouping consecutive symbols S 0 . . . S N-1 into a second non-negative symbol set defined as a symbol set Γ into a second no-negative symbol set defined as a symbol set Γ including the symbols {γ} obtained as the extension of the original symbol set S; means, operatively connected to the group means, for coding said second non-negative symbol set Γ into a comma code so as to generate coded binary digital data representing a compressed image signal of said low entropy image signal generated by the imager.
Claim 20
Dependent Claim
212 words
Apparatus for coding a low entropy image signal generated by an imager comprising: digitizing means for digitizing the signal of low entropy generated by said imager into an array of digital image data; difference means, operatively connected to the digitizing means, for determining the difference in value between adjacent digital image data points in the array; mapping means, operatively connected to the difference means, for mapping each said difference in value between said adjacent digital image data in the array into a first non-negative symbol set defined as a set S, {S 0 , S 1 , S 2 , . . . S N-1 } of N symbols with s i =i; grouping means, operatively connected to the mapping means, for grouping consecutive symbols S 0 . . . S N-1 into a second non-negative symbol set defined as a symbol set Γ into a second no-negative symbol set defined as a symbol set Γ including the symbols {γ} obtained as the extension of the original symbol set S; means, operatively connected to the group means, for coding said second non-negative symbol set Γ into a comma code so as to generate coded binary digital data representing a compressed image signal of said low entropy image signal generated by the imager.
Claim 21
Dependent Claim
19 words
An apparatus as in claim 17, wherein the digital image data in the array is gray-scale digital image data.
Claim 22
Independent Claim
269 words
An apparatus for decoding a coded low entropy image signal, the low entropy image signal being generated by an imager comprising: receiving means for receiving a comma code formed of 0's followed by a 1, the comma code being representative of the coded image data, the image data being representative of a low entropy image signal generated by the imager; first means, operatively connected to the receiving means, for a first set of non-negative symbols γ m by counting the 0's of said comma code; second means, operatively connected to the first means, for obtaining a variable β and a variable m s by implementing the following logic: ______________________________________
if m = 0 then β = 0
and m.sub.s = 0
if m = 1,2 then β = 1
and m.sub.s = 1
if m = 3,4,5 then β = 2
and m.sub.s = 3
if m = 6,...,9
then β = 3
and m.sub.s = 6
if m = 10,....,14
then β = 4
and m.sub.s = 10
if m = 15,....,20
then β = 5
and m.sub.s = 15
if m = 21,....,28
then β = 6
and m.sub.s = 21
if m = 28,....,35
then β = 7
and m.sub.s = 28
* * *
* * *
* * *;
______________________________________ third means, operatively connected to the second means, for calculating a variable j=m-m s ; fourth means, operatively connected to the third means, for calculating a variable i=β-j; and fifth means, operatively connected to the fourth means, for restoring a second non-negative set of symbols according to s i =i and s j =j.
Claim 23
Independent Claim
269 words
An apparatus for decoding a coded low entropy image signal, the low entropy image signal being generated by an imager comprising: receiving means for receiving a comma code formed of 0's followed by a 1, the comma code being representative of the coded image data, the image data being representative of a low entropy image signal generated by the imager; first means, operatively connected to the receiving means, for a first set of non-negative symbols γ m by counting the 0's of said comma code; second means, operatively connected to the first means, for obtaining a variable β and a variable m s by implementing the following logic: ______________________________________
if m = 0 then β = 0
and m.sub.s = 0
if m = 1,2 then β = 1
and m.sub.s = 1
if m = 3,4,5 then β = 2
and m.sub.s = 3
if m = 6,...,9
then β = 3
and m.sub.s = 6
if m = 10,....,14
then β = 4
and m.sub.s = 10
if m = 15,....,20
then β = 5
and m.sub.s = 15
if m = 21,....,28
then β = 6
and m.sub.s = 21
if m = 28,....,35
then β = 7
and m.sub.s = 28
* * *
* * *
* * *;
______________________________________ third means, operatively connected to the second means, for calculating a variable j=m-m s ; fourth means, operatively connected to the third means, for calculating a variable i=β-j; and fifth means, operatively connected to the fourth means, for restoring a second non-negative set of symbols according to s i =i and s j =j.
References Cited (Backward Citations)
US3524926A
Cited
JPS56165463A
Cited
US4447886A
Cited
US4578704A
Cited
US4646148A
Cited
US4654877A
Cited
US4626829A
Cited
US4841299A
Cited
US4939583A
Cited
US5063608A
Cited
US5021891A
Cited
JPH06225541A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-09-04 | 1999-03-06 | 1999-09-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-09-04 | 2003-03-06 | 2003-09-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-09-04 | 2007-03-06 | 2007-09-05 | $7700.00 | Window Closed / Lapsed |