Source: https://patents.google.com/patent/US10291255B2/en
Timestamp: 2019-09-19 22:11:59
Document Index: 271768812

Matched Legal Cases: ['application No. 60', 'Application No. 03718500', 'Application No. 10195913', 'Application No. 03718500', 'Application No. 10195913', 'Application No. 15169824', 'Application No. 15169825', 'Application No. 15169824', 'Application No. 15169825', 'Application No. 15169824']

US10291255B2 - System and method for arithmetic encoding and decoding - Google Patents
US10291255B2
US10291255B2 US15/948,115 US201815948115A US10291255B2 US 10291255 B2 US10291255 B2 US 10291255B2 US 201815948115 A US201815948115 A US 201815948115A US 10291255 B2 US10291255 B2 US 10291255B2
US15/948,115
US20180226987A1 (en
2002-04-23 Priority to US37477002P priority Critical
2003-04-23 Priority to PCT/US2003/012518 priority patent/WO2003091942A1/en
2003-04-23 Priority to US10/469,630 priority patent/US7822283B2/en
2009-09-30 Priority to US12/570,383 priority patent/US9577667B2/en
2016-10-26 Priority to US15/334,736 priority patent/US20170047944A1/en
2018-04-09 Priority to US15/948,115 priority patent/US10291255B2/en
2018-04-09 Application filed by NTT Docomo Inc filed Critical NTT Docomo Inc
2018-08-09 Publication of US20180226987A1 publication Critical patent/US20180226987A1/en
2019-05-14 Publication of US10291255B2 publication Critical patent/US10291255B2/en
This application is a continuation application of U.S. patent application Ser. No. 15/334,736 filed Oct. 26, 2016, which is a continuation application of U.S. patent application Ser. No. 12/570,383 filed on Sep. 30, 2009, which is a continuation application of U.S. patent application Ser. No. 10/469,630 filed on May 6, 2004, which is 371 application of PCT/US2003/012518 having an international filing date of Apr. 23, 2003, which claims priority to U.S. provisional application No. 60/374,770 filed on Apr. 23, 2002, the entire contents of which are incorporated herein by reference.
In accordance with another embodiment of the invention, an arithmetic decoder is also provided for converting n information sequence comprised of at least one information piece to an event sequence comprised of a plurality of events, including at least one input port for receiving information pieces of the information sequence, at least one output port, and a sequencer coupled with the at least one input port and the at least one output port and including a context generator for generating context information for at least one generated event. The probability estimator is coupled with the sequencer for receiving a generated event of the event sequence and the corresponding context information, and for determining a probability estimate. A core engine is coupled with the sequencer and the probability estimator for processing zero or more information pieces of the information sequence from the sequencer responsive to the probability estimate to generate one event by accounting for a bounded ratio of events to information pieces. The generated event is provided to the probability estimator with corresponding context information from the sequencer for updating the probability estimate, and the generated event is provided to the sequencer for transmittal as the event sequence from the at least one output port.
The value register 770 is initialized at step 805 by collecting 16 bits into the value register 770, for example the first 16 information pieces of the information sequence, as described in Arithmetic Coding Revisited, by Moffat et al., ACM Transactions on Information Systems, VOL. 16, NO. 3, July 1998, pages 256-294, hereby incorporated by reference herein, and as would be appreciated by one skilled in the art.
The entropy encoder may encode the sequence of events 1135 in a similar fashion as described above with respect to the arithmetic encoder 100 of FIG. 1. For example, the arithmetic encoder 1115 may include, where appropriate, a sequencer, and probability estimator as described above with respect to FIG. 1. The arithmetic encoder 1115 may further include a core engine with Range. Low and Bit Outstanding Registers. The controller 1120 may include one or more counters for tracking a number of events of the sequence of events 1135 processed and a number of information pieces of the information sequence 1130 generated. Alternatively, the one or more counters may be present within the entropy coder 1110, where the controller 1120 is capable of monitoring the counter(s) to ensure the threshold between events processed and information pieces generated is substantially maintained. The controller 1120 may constrain the number of information pieces, for example, over each individual sequence of events being encoded. For example, the controller may ensure that (# generated information pieces)×(threshold)≥(# events processed). This may be accomplished, for example, in a similar fashion as discussed above with respect to FIGS. 1-6, and specifically FIG. 4, where the controller increments a counter for each event processed, and subtracts a number from the counter representing the threshold value, for example “4” when a bit is processed. The controller may then compare the value of the counter, with for example the value 0, and trigger the insertion of a stuffing bit if the value of the counter is larger than 0. In this way, the controller is capable of ensuring that the arithmetic encoder 1115 is substantially constrained to a 4:1 ratio of events processed to information pieces generated.
e≤αB+βS,
The values for α and β are typically provided to the controller 1120, and the derivation of α and β will be discussed below. The value α may represent a decrement value to, for example, a counter upon generation of an information piece at the coder, where the value β may represent decrement value to, for example, a counter upon completion of processing a segment. In the alternative, the value β may be decremented from a counter value at the beginning of processing of a segment, or at any other time during the processing of a segment as would be apparent to one skilled in the art.
e−βS≤αB,
Since the total number of segments, S, and the value β are known, the product of β×S may be subtracted from the number of events, e, for the sequence of events 1135 during or after processing of the one or more segments of the input data 1125. For example, where a counter is utilized to constrain the number of events responsive to the number of bits that have been generated, the counter may initially be decremented by a value of β×S, and may be decremented by a value α for each information piece generated, while the counter is incremented by “1” for each event of the sequence of events 1135 processed by the entropy encoder 1110. The value of β may be any value, typically in the range of 1 to 100, and may be determined, for example, as described further below. The value of a may be any value, typically in the range of 1 to 10, and may be determined, for example, as described further below.
1. A method of arithmetic decoding for converting an information sequence comprised of information pieces to derive an event sequence comprised of events, the method comprising:
receiving the information pieces of the information sequence;
generating context information for the events;
generating, according to the generated context information, a probability estimate estimating a probability of occurrence of the events;
converting the received information pieces to derive the events, using the generated probability estimate, by accounting for a bounded ratio of events to information pieces;
wherein accounting for a bounded ratio of events to information pieces comprises increasing a number of the information pieces so that a number of the events being outputted resulting from the increased number of information pieces does not exceed a threshold which is a linear function of the increased number of information pieces.
US15/948,115 2002-04-23 2018-04-09 System and method for arithmetic encoding and decoding Active US10291255B2 (en)
US37477002P true 2002-04-23 2002-04-23
US10/469,630 US7822283B2 (en) 2002-04-23 2003-04-23 System and method for arithmetic encoding and decoding
US12/570,383 US9577667B2 (en) 2002-04-23 2009-09-30 System and method for arithmetic encoding and decoding
US15/334,736 US20170047944A1 (en) 2002-04-23 2016-10-26 System and method for arithmetic encoding and decoding
US15/948,115 US10291255B2 (en) 2002-04-23 2018-04-09 System and method for arithmetic encoding and decoding
US15/334,736 Continuation US20170047944A1 (en) 2002-04-23 2016-10-26 System and method for arithmetic encoding and decoding
US20180226987A1 US20180226987A1 (en) 2018-08-09
US10291255B2 true US10291255B2 (en) 2019-05-14
US12/570,383 Active 2024-11-10 US9577667B2 (en) 2002-04-23 2009-09-30 System and method for arithmetic encoding and decoding
US15/334,736 Pending US20170047944A1 (en) 2002-04-23 2016-10-26 System and method for arithmetic encoding and decoding
US15/948,115 Active US10291255B2 (en) 2002-04-23 2018-04-09 System and method for arithmetic encoding and decoding
JPH07273664A (en) 1994-03-31 1995-10-20 Mitsubishi Electric Corp Coding and decoding device, coder and decoder
JPH08228342A (en) 1994-12-01 1996-09-03 Ricoh Co Ltd Compression method and context modeller
US5781136A (en) 1996-06-19 1998-07-14 Mitsubishi Denki Kabushiki Kaisha Digital information encoding device, digital information decoding device, digital information encoding/decoding device, digital information encoding method, and digital information decoding method
GB2330473A (en) 1997-09-30 1999-04-21 Ricoh Kk Compression and decompression system with reversible wavelets and lossy reconstruction
JP2002033925A (en) 2000-07-18 2002-01-31 Matsushita Graphic Communication Systems Inc Method arithmetic encoding and decoding, and apparatus for arithmetic encoding and decoding
US20030118241A1 (en) 1994-09-21 2003-06-26 Ricoh Company, Ltd. Method and apparatus for compression using reversible wavelet transforms and an embedded codestream
US7260735B2 (en) 2003-12-18 2007-08-21 Lsi Corporation Method and system for maintaining a running count of events updated by two asynchronous processes
2009-09-30 US US12/570,383 patent/US9577667B2/en active Active
2016-10-26 US US15/334,736 patent/US20170047944A1/en active Pending
2018-04-09 US US15/948,115 patent/US10291255B2/en active Active
Bossen, F., "Bounding the Complexity of Arithmetic Decoding", Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG (ISO/IEC JTC1/SC29/WG11 and ITU-T SG16 Q.6, 3rd Meeting: Fairfax, Virginia, USA, May 6-10, 2002, 13 pages.
European Search Report for European Application No. 03718500.6, dated May 18, 2010, 5 pages.
Examination Report for counterpart European Application No. 10195913.8, dated Sep. 21, 2011, 7 pages.
Examination Report for European Application No. 03718500.6, dated Aug. 27, 2010, 9 pages.
Extended European Search Report for European Application No. 10195913.8, dated Feb. 24, 2011, 8 pages.
Extended Search Report in corresponding European Application No. 15169824.8, dated Sep. 23, 2015, 11 pages.
Extended Search Report in corresponding European Application No. 15169825.5, dated Sep. 23, 2015, 14 pages.
International Telecommunication Union, "Line Transmission of Non-Telephone Signals-Video Coding for Low Bitrate Communication", ITU-T, Draft H.263, May 2, 1996, 54 pages.
Japanese Office Action for Japanese Application No. P2004-500244, dated Sep. 16, 2008, 5 pages (with translation).
Moffat et al., "Arithmetic coding revisited", ACM Transactions on Information Systems, vol. 16, No. 3, Jul. 1998, pp. 256-294.
Notice of Allowance for co-pending U.S. Appl. No. 10/469,630, dated Jun. 17, 2010, 7 pages.
Office Action from co-pending U.S. Appl. No. 10/469,630, dated Jan. 29, 2010, 16 pages.
Office Action in co-pending U.S. Appl. No. 10/469,630, dated Sep. 2, 2009, 17 pages.
Office Action in corresponding European Application No. 15169824.8, dated Feb. 6, 2018, 13 pages.
Office Action in corresponding European Application No. 15169825.5, dated Feb. 6, 2018, 6 pages.
Office Action in Europe Application No. 15169824.8, dated Nov. 8, 2018, pp. 1-16.
Office Action in U.S. Appl. No. 15/334,736, dated Aug. 6, 2018, pp. 1-11.
Office Action in U.S. Appl. No. 15/334,736, dated Jan. 10, 2019, 14 pages.
Salomon D Ed-Salomon David, "Data Compression: The Complete Reference; Section 2.14, 2.15: (Adaptive) Arithmetic Coding", Data Compression: The Complete Reference, Springer, New York, dated Jan. 1, 1998 (Jan. 1, 1998), p. 69-p. 84, XP002270343.
Van Der Vleuten, Rene, "Low Complexity Arithmetic Coding Implementation", Document JVT-B033, JVT meeting, Geneva, Jan. 2002, pp. 1-13.
Winger et al., "Low Complexity Arithmetic Coding Engine", Document JVT-B036, JVT meeting, Geneva, 2002, pp. 1-10.
US9577667B2 (en) 2017-02-21
US20180226987A1 (en) 2018-08-09
US20170047944A1 (en) 2017-02-16
US20100014581A1 (en) 2010-01-21