Image analysis – Histogram processing – For setting a threshold
Patent
1988-11-18
1990-02-27
Boudreau, Leo H.
Image analysis
Histogram processing
For setting a threshold
3582612, 341 95, G06K 936
Patent
active
049052977
ABSTRACT:
Apparatus and method for compressing and de-compressing binary decision data by arithmetic coding and decoding wherein the estimated probability Qe of the less probable of the two decision events, or outcomes, adapts as decisions are successively encoded. To facilitate coding computations, an augend value A for the current number line interval is held to approximate one by renormalizing A whenever it becomes less than a prescribed minimum AMIN. When A is renormalized, the value of Qe is up-dated. The renormalization of A and up-dating of Qe are preferably based on a single-bit test. Also, each Qe value is preferably specified as a 12-bit value having the least significant bit set to 1 and having no more than four other bits set to 1. The number of Qe values in the 1/4 to 1/2 probability range is enhanced to improve coding efficiency. A decision coding parameter of preferably six bits indicates the sense of the more probable symbol (MPS) in one bit and identifies a corresponding Qe value with the remaining five bits. In addition to probability adaptation, the present invention discloses an allocation of bits in a code stream register in which preferably two spacer bits are inserted between a next byte portion (which contains a byte of data en route to a buffer) and a fractional portion which may be involved in further computation. With the two spacer bits, any code greater than or equal to Hex `CO` which follows a Hex `FF` byte is illegal for data and therefore provides for an escape from the code stream. The two spacer bits also reduce the number of stuff bits inserted to account for carry or borrow propagation. Encoding and decoding can be performed interchangeably by hardware or software which feature differing coding conventions.
REFERENCES:
patent: 4028731 (1977-06-01), Arps et al.
patent: 4122440 (1978-10-01), Landgon, Jr. et al.
patent: 4168513 (1979-09-01), Hains et al.
patent: 4259693 (1981-03-01), Aaron et al.
patent: 4285049 (1981-08-01), Bird et al.
patent: 4286256 (1981-08-01), Langdon, Jr. et al.
patent: 4295125 (1981-10-01), Langdon, Jr.
patent: 4363036 (1982-12-01), Subramaniam
patent: 4369463 (1983-01-01), Anastassiou et al.
patent: 4386373 (1983-05-01), Kondo et al.
patent: 4426731 (1984-01-01), Edlund et al.
patent: 4435726 (1984-03-01), Liao
patent: 4462081 (1984-07-01), Lehan
patent: 4463342 (1984-07-01), Langdon, Jr. et al.
patent: 4467317 (1984-08-01), Langdon, Jr. et al.
patent: 4488143 (1984-12-01), Martin
patent: 4503420 (1985-03-01), Rub et al.
patent: 4510567 (1985-04-01), Chang et al.
patent: 4516241 (1985-05-01), Farah et al.
patent: 4540973 (1985-09-01), Grallert
patent: 4558302 (1985-12-01), Welch
patent: 4577314 (1986-03-01), Chu et al.
patent: 4584561 (1986-04-01), Bernardson
patent: 4596024 (1986-06-01), Thomson
patent: 4633490 (1986-12-01), Goertzel et al.
patent: 4652856 (1987-03-01), Mohiuddin et al.
J. Rissanen, Combinatorial Coding, Conditional Entropy, and Distance For Sequences, RJ1538, Computer Science 2/75.
G. N. N. Martin, Range Encoding: An Algorithm For Removing Redundancy from a Digitised Message, 7 24-27, 1979, Video & Data Recording Conference.
J. Rissanen, Arithmetic Coding of Strings, Computer Science 6/75 RJ1591.
J. Rissanen, G. G. Langdon, Jr., Arithmetic Coding, RJ2174 1/30/78 Computer Science.
F. Barsi, P. Maestrini, Arithmetic Codes In Residue Number Systems, Digital Processes, 1978 pp. 121-135.
M. Boyarinov, G. A. Kibatyanskii, Iterative Arithmetic Independent-Error-Correcting Codes, Translated From Problemy Peredachi Informatsii, vol. 15, No. 1. pp. 38-49, Jan.-Mar. 1979.
J. Rissanen, G. G. Langdon, Jr., Arithmetic Coding, IBM Journal of Res. & Devel. vol. 23, No. 2, 3/79.
F. Rubin, Arithmetic Stream Coding Using Fixed Precision Registers, IEEE, vol. IT25, No. 6, 11/79.
G. G. Langdon, Jr., J. J. Rissanen, Method For Converting Counts to Coding Parameters, IBM TDB, vol. 22, No. 7, 12/79.
G. G. Langdon, Jr., J. J. Rissanen, Integer-Length Arithmetic Code For Conditional Binary Sources, IBM TDB, vol. 22, No. 10, 3/80.
G. G. Langdon, Jr., Method For Carry-Over Control in a FIFO Arithmetic Code String, IBM TDB, vol. 23, No. 1, 6/80.
D. G. Abraham, Parallel Compression By Table Look-Up, IBM TDB, vol. 23, No. 7A, 12/80.
D. R. Helman, G. G. Langdon, Jr. J. J. Rissanen, Arithmetic Compression Code Control Parameter Approximation, IBM TDB, vol. 23, No. 11, 4/81.
G. G. Langdon, Jr., Apparatus Supporting Half-Duplexed Encoding/Decoding Action, IBM TDB, vol. 23, No. 11, 4/81.
R. B. Arps, G. G. Langdon, Jr., LIFO Arithmetic Compression Coding Method For Conditional Sources, IBM TDB, vol. 23, No. 11, 4/81.
C. B. Jones, An Efficient Coding System for Long Source Sequences, IEEE, vol. IT27, No. 3, May 1981.
G. G. Langdon, Jr., Table-Driven Decoder Involving Prefix Codes, IBM TDB, vol. 23, No. 12, 5/81.
G. G. Langdon, Jr., J. Rissanen, Compression of Black-White Images with Arithmetic Coding, IEEE, vol. 29, No. 6, 6/81.
G. G. Langdon, Jr., J. J. Rissanen, Computational Speed Enhancement by Selective Precision in Arithmetic Code Operations, IBM TDB, vol. 24, No. 2, 7/81.
G. G. Langdon, Jr., Constrained Channel Coding Using a Reduced Number of Arithmetic String Coding Steps Per Cycle, IBM TDB, vol. 24, No. 8, Jan. 1982.
D. R. Helman, G. G. Langdon, Jr., N. Martin, S. J. P. Todd, Statistics Collection for Compression Coding With Randomizing Feature, IBM TDB, vol. 24, No. 10, 3/82.
G. G. Langdon, Jr., J. J. Rissanen, An Adaptive File Compression Algorithm, RJ3460, 4/23/82, Computer Science.
G. G. Langdon, Jr., S. J. P. Todd, General Unit-Time Arithmetic Codes for Constrained Channels, IBM TDB, vol. 25, No. 3A, 8/82.
G. G. Langdon, Jr., S. J. P. Todd, Augend Computation for Arithmetic Channel Codes, IBM TDB, vol. 25, No. 3A, 8/82.
G. G. Langdon, Jr., S. J. P. Todd, Method for Application of ECC to Constrained Channels, IBM TDB, vol. 25, No. 3A, 8/82.
R. B. Arps, J. M. Cheng, G. G. Langdon, Jr., Control Character Insertion Into Arithmetically Encoded Strings, IBM TDB, vol. 25, No. 4, 9/82.
G. G. Langdon, Jr., J. Rissanen, A Simple General Binary Source Code, IEEE, vol. IT28, No. 5, 9/1982.
G. N. N. Martin, G. G. Langdon, Jr., S. J. P. Todd, Arithmetic Codes for Constrained Channels, IBM J. Res. Devel., vol. 27, No. 2, 3/83.
S. J. P. Todd, G. G. Langdon, Jr., G. N. N. Martin, A General Fixed Rate Arithmetic Coding Method for Constrained Channels, IBM J. Res. Devel., vol. 27, No. 2, 3/83.
G. G. Langdon, Jr., A Note on the Ziv-Lempel Model for Compressing Individual Sequences, IEEE, vol. 29, No. 2, 3/83.
G. G. Langdon, P. H. Siegel, S. Todd, Constrained Channel Coding With Spectral Null, IBM TDB, vol. 26, No. 5, 10/83.
G. Langdon, Jr., Adaptive Run-Length Coding Algorithm, IBM TDB, vol. 26, No. 7B, 12/83.
G. G. Langdon, Jr., An Introduction to Arithmetic Coding, IBM J. Res. Devel., vol. 28, No. 2, 3/84.
P. K. Chakraborty, J. C. Biswas, Definition of Unspecified Flag Bits of the Z80 Microprocessor, J. Microprocessor and Microsystems, vol. 9, Issue 1.
D. Mahlab, Compression of Data Compression Algorithms, IEEE, Mar. 26-28, 1985, Tel Aviv, Israel.
S. Todd, G. G. Langdon, Jr., J. Rissanen, Parameter Reduction and Context Selection for Compression of Gray-scale Images, IBM J. Res. Dev., 29, 2, 3/83.
T. R. Rao, K. Vathanvit, A Class of A(N+C) Codes and Its Properties, Proceedings of 7th Symposium on Computer Arithmetic, IEEE, 1985.
R. Shimada, Y. Ohkura, J. Aoe, Nonbinary Arithmetic AN Codes Using Odd Radix Expressions, IEEE, vol. C-34, No. 11, Nov. 1985.
H. Morita, K. Fujimoto, S. Kitada, S. Arimoto, On Efficiency of Binary Arithmetic Codes, Trans Inf. Process. Soc. Jpn., vol. 25, No. 4, 1984.
G. G. Langdon, Jr., J. J. Rissanen-"Method of Converting Counts to Coding Parameters", Dec. 1979, pp. 2880-2882.
D. R. Helman, G. G. Langdon, Jr., J. J. Rissanen, "Arithmetic Compression Code Control Parameter Approximation", Apr. 1981, pp. 5112-5114.
G. G. Langdon, Jr., J. Rissanen-"Compression of Black-White Images with Arithmetic Coding", Jun. 1981, IEEE, pp. 858-867.
G. G. Langdon, Jr.,-"An Introduction to Arithmetic Coding", Mar. 1984, pp. 135-149.
Langdon, Jr. Glen G.
Mitchell Joan L.
Pennebaker William B.
Rissanen Jorma J.
Boudreau Leo H.
Dowd Thomas P.
International Business Machines - Corporation
Mancuso Joseph
LandOfFree
Arithmetic coding encoder and decoder system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Arithmetic coding encoder and decoder system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Arithmetic coding encoder and decoder system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-179876