Source: https://patents.justia.com/patent/8947271
Timestamp: 2019-08-25 19:48:27
Document Index: 461076436

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60']

US Patent for Multiple technique entropy coding system and method Patent (Patent # 8,947,271 issued February 3, 2015) - Justia Patents Search
Justia Patents Adaptive CodingUS Patent for Multiple technique entropy coding system and method Patent (Patent # 8,947,271)
Jun 7, 2011 - Soryn Technologies, LLC
Latest Soryn Technologies, LLC Patents:
The present application is a continuation of U.S. patent application Ser. No. 12/234,472, filed Sep. 19, 2008, which is a continuation of U.S. patent application Ser. No. 11/232,726, filed Sep. 21, 2005 and also claimed priority from provisional applications filed Sep. 21, 2004 under U.S. Patent Application No. 60/612,311 entitled RATE CONTROL WITH VARIABLE SUBBAND QUANTIZATION; filed Sep. 22, 2004 under U.S. Patent Application No. 60/612,652 entitled SPLIT TABLE ENTROPY CODING; filed Sep. 22, 2004 under U.S. Patent Application No. 60/612,651 entitled PERMUTATION PROCRASTINATION; filed Oct. 12, 2004 under U.S. Patent Application No. 60/618,558 entitled MOBILE IMAGING APPLICATION, DEVICE ARCHITECTURE, AND SERVICE PLATFORM ARCHITECTURE; filed Oct. 13, 2004 under U.S. Patent Application No. 60/618,938 entitled VIDEO MONITORING APPLICATION, DEVICE ARCHITECTURES, AND SYSTEM ARCHITECTURE; filed Feb. 16, 2005 under U.S. Patent Application No. 60/654,058 entitled MOBILE IMAGING APPLICATION, DEVICE ARCHITECTURE, AND SERVICE PLATFORM ARCHITECTURE AND SERVICES; each of which is incorporated herein by reference in its entirety.
The present application is a continuation-in-part of U.S. patent application Ser. No. 10/944,437 filed Sep. 16, 2004 entitled MULTIPLE CODEC-IMAGER SYSTEM AND METHOD, now U.S. Publication No. US2005/0104752 published on May 19, 2005; continuation-in-part of U.S. patent application Ser. No. 10/418,649 filed Apr. 17, 2003 entitled SYSTEM, METHOD AND COMPUTER PROGRAM PRODUCT FOR IMAGE AND VIDEO TRANSCODING, now U.S. Publication No. US2003/10206597 published on Nov. 6, 2003; continuation-in-part of U.S. patent application Ser. No. 10/418,363 filed Apr. 17, 2003 entitled WAVELET TRANSFORM SYSTEM, METHOD AND COMPUTER PROGRAM PRODUCT, now U.S. Publication No. US2003/0198395 published on Oct. 23, 2003; continuation-in-part of U.S. patent application Ser. No. 10/447,455 filed on May 28, 2003 entitled PILE-PROCESSING SYSTEM AND METHOD FOR PARALLEL PROCESSORS, now U.S. Publication No. US2003/0229773 published on Dec. 11, 2003; continuation-in-part of U.S. patent application Ser. No. 10/447,514 filed on May 28, 2003 entitled CHROMA TEMPORAL RATE REDUCTION AND HIGH-QUALITY PAUSE SYSTEM AND METHOD, now U.S. Publication No. US2003/0235340 published on Dec. 25, 2003; continuation-in-part of U.S. patent application Ser. No. 10/955,240 filed Sep. 29, 2004 entitled SYSTEM AND METHOD FOR TEMPORAL OUT-OF-ORDER COMPRESSION AND MULTISOURCE COMPRESSION RATE CONTROL, now U.S. Publication No. US2005/0105609 published on May 19, 2005; continuation-in-part of U.S. application Ser. No. 11/232,165 filed Sep. 20, 2005 entitled COMPRESSION RATE CONTROL SYSTEM AND METHOD WITH VARIABLE SUBBAND PROCESSING; each of which is incorporated herein by reference in its entirety. This application also incorporates by reference in its entirety U.S. Pat. No. 6,825,780 issued on Nov. 30, 2004 entitled MULTIPLE CODEC-IMAGER SYSTEM AND METHOD; U.S. Pat. No. 6,847,317 issued on Jan. 25, 2005 entitled SYSTEM AND METHOD FOR A DYADIC-MONOTONIC (DM) CODEC; and U.S. application Ser. No. 11/232/725 filed Sep. 21, 2005 entitled PERMUTATION PROCRASTINATION.
A wavelet transform comprises the repeated application of wavelet filter pairs to a set of data, either in one dimension or in more than one. For image compression, a 2D wavelet transform (horizontal and vertical) can be used. For video data streams, a 3D wavelet transform (horizontal, vertical, and temporal) can be used.
2D and 3D wavelets, as opposed to DCT-based codec algorithms, have been highly regarded due to their pleasing image quality and flexible compression ratios, prompting the JPEG committee to adopt a wavelet algorithm for its JPEG2000 still image standard. Unfortunately, most wavelet implementations use very complex algorithms, requiring a great deal of processing power, relative to OCT alternatives. In addition, wavelets present unique challenges for temporal compression, making 3D wavelets particularly difficult.
For example, small video cameras are becoming more widespread, and the advantages of handling their signals digitally are obvious. For instance, the fastest growing segment of the cellular phone market in some countries is for phones with image and video-clip capability. Most digital still cameras have a video-clip feature. In the mobile wireless handset market, transmission of these still pictures and short video clips demand even more capacity from the device battery. Existing video coding standards and digital signal processors put even more strain on the battery.
Given an input symbol to encode, one way to do the encoding is to take the symbol as an index and look it up in a table called a °codebook″. The entry found in the codebook is the encoded output for the symbol. The code book is typically large enough to provide an entry for every possible symbol.
According to one aspect of the invention, Huffman coding by table lookup is combined with computational codeword generation, such as by using an exponential Golomb equation. The most commonly occurring elements are looked up in a small Huffman table, while the remaining elements are coded with the equation. This arrangement offers the advantages of Huffman coding by table lookup (namely, optimum matching to-a known or measured probability distribution) combined with the advantages of simple computed coding (namely, quick computation with no lookup) while avoiding the disadvantage of full Huffman coding (namely, the need to support a very large table).
FIG. 3 is a flow chart showing a process of selecting and applying a Huffman coding technique and a computational generation technique for a positive non-zero integer.
FIG. 4 is a table used by the process of FIG. 3.
FIG. 5 is a flow chart showing a process of selecting and applying a Huffman coding technique and a computational generation technique for a signed integer.
FIG. 6 is a table used by the process of FIG. 5.
According to another aspect of the invention, the choice of which technique to apply to which data elements or symbols can be a simple magnitude test. In this example, the symbols to be entropy coded are always positive, ranging from 1 to 215-1. The value zero is excluded. The symbol is simply tested as to whether it is less than a fixed constant. If so, a table of the same size of the constant is used. If not, the computational method is used.
If S>15, go to Step 3.
Look up S in Table 1 given below, to find the value B and the length L.
W consists of the low-order L bits of B.
Count the significant bits in the number S+8, starting from the leftmost ‘1’ bit inclusive. Call the count C.
for Example Algorithm 1
Output Symbol L B bitstring
1 1 1 1 2 3 3 010 3 3 3 001 4 5 5 00100 5 5 5 00101 6 5 6 00110 7 5 7 00111 8 6 4 000100 9 6 5 000101 10 6 6 000110 11 6 7 000111 12 8 8 00001000 13 8 9 00001010 14 8 10 00001010 15 8 11 00001011
For comparison purposes, Table 2 below provides the output that would have been provided by steps 3 and 4 above (computational generation of codewords) for symbol values less than 16 if Table 1 were not used. It can be seen by comparing the two tables that using the Huffman table approach of Table 1 provides shorter codewords for some of the more frequent symbols as compared with the computational generation approach of Table 2.
1 1 1 1 2 3 2 010 3 3 3 011 4 5 4 00100 5 5 5 00101 6 5 6 00110 7 5 7 00111 8 7 8 0001000 9 7 9 0001001 10 7 10 0001010 11 7 11 0001011 12 7 12 0001100 13 7 13 0001101 14 7 14 0001110 15 7 15 0001111
It offers an arbitrary Huffman code for the most common cases;
to match optimally that part of the probability distribution as measured, it needs only a small table that easily fits in limited memory;
it uses a very simple computation of exp-Golomb coding for the less-common cases;
no matter what the symbol, operation is fast.
Various enhancements can be made to the above example implementation of the present invention. For instance, the entropy coder can be modified to encode signed number symbols as well as the unsigned (positive only) symbols above. To do this efficiently, each L entry in the table is increased by one, the sign bit is appended to each B value, and table entries for negative symbols are included. Table 3 below provides an example. In this table, there is an entry for symbol 0 to allow quicker direct lookup. Since this 0 symbol entry is a dummy entry that is not used, its content is immaterial.
FIG. 5 is a flow chart that demonstrates a process of selecting and applying the Huffman coding technique and a computational generation technique, for a signed integer. In process 500, the algorithm accepts as input a symbol S, a 16-bit integer in binary representation (value zero is not allowed). It produces a bit string W as output, for bitwise appending to the compressed bitstream being generated. FIG. 6 is a table used by Example algorithm 2.
Step 1. If the absolute value of S is greater than 15, go to Step 3.
Step 2. Look up S in Table 3 below, to find the value B and the length L.
Count the significant bits in the absolute value of the number S+8, starting from the leftmost ‘1’ bit inclusive. Call it C.
for Example Algorithm 2
−15 9 23 000010111 −14 9 21 000010101 −13 9 19 000010011 −12 9 17 000010001 −11 7 15 0001111 −10 7 13 0001101 −9 7 11 0001011 −8 7 9 0001001 −7 6 15 001111 −6 6 13 001101 −5 6 11 001011 −4 6 9 001001 −3 4 7 0111 −2 4 5 0101 −1 2 3 11 0 0 0 (unused) 1 2 2 10 2 4 4 0100 3 4 6 0110 4 6 8 001000 5 6 10 001010 6 6 12 001100 7 6 14 001110 8 7 8 0001000 9 7 10 0001010 10 7 12 0001100 11 7 14 0001110 12 9 16 000010000 13 9 18 000010010 14 9 20 000010100 15 9 22 000010110
calculating from an incoming data stream binary representations of magnitudes of symbols for each portion of the incoming data stream according to an algorithmic analysis;
selectively applying a first coding technique to symbols of the portions of the incoming data stream that have binary representations of magnitudes greater than a first threshold value;
selectively applying a second coding technique to portions of the incoming data stream that have binary representations of magnitudes less than the first threshold value but greater than a second threshold value; and
selectively applying a third coding technique to portions of the incoming data stream that have binary representations of magnitudes less than the second threshold value.
means for assigning from an incoming data stream binary representations of magnitudes of symbols to each of the portions of the incoming data stream;
means for applying a first coding technique when binary representations of the magnitudes of symbols of any portion of the incoming data stream is greater than a first threshold value;
means for applying a second coding technique when the binary representations of magnitude of any portion of the incoming data stream is less than the first threshold value but greater than a second threshold value; and
means for applying a third coding technique when the binary representations of magnitude of any portion of the incoming data stream is less than the second threshold value.
3. The method as claimed in claim 1, wherein the first coding technique comprises an exponential Golumb encoding method encoding the portions of the incoming data stream that have binary representations of magnitudes greater than the first threshold value.
4. The system as claimed in claim 2, wherein the means for applying the first coding technique comprises an exponential Golumb encoder encoding any portion of the incoming data stream having a binary representation of a magnitude that is greater than the first threshold value.
5. The system as claimed in claim 4, wherein the means for applying the third coding technique comprises a Huffman encoder for encoding any portion of the incoming data stream having a binary representation of a magnitude that is less than the second threshold value.
6. The method as claimed in claim 3, wherein the third coding technique comprises Huffman encoding any portion of the incoming data stream having a binary representation of a magnitude that is less than the second threshold value.
5812076 September 22, 1998 Yoshida
6373411 April 16, 2002 Shoham
6696992 February 24, 2004 Chu
6969992 November 29, 2005 Vaughan et al.
7671766 March 2, 2010 Pang et al.
7965206 June 21, 2011 Choo et al.
20030227539 December 11, 2003 Bonnery et al.
20060050786 March 9, 2006 Tanizawa et al.
20070189209 August 16, 2007 Awad et al.
20100079312 April 1, 2010 Choo et al.
20120093226 April 19, 2012 Chien et al.
Patent number: 8947271
Patent Publication Number: 20110234431
Assignee: Soryn Technologies, LLC (Jersey City, NJ)
Inventors: William C. Lynch (Palo Alto, CA), Krasimir D. Kolarov (Menlo Park, CA), Steven E. Saunders (Cupertino, CA)
Application Number: 13/155,280
Current U.S. Class: Adaptive Coding (341/51); To Or From Huffman Codes (341/65); To Or From Variable Length Codes (341/67); Coding By Table Look-up Techniques (341/106); To Or From Code Based On Probability (341/107)
International Classification: H03M 7/34 (20060101); H03M 7/40 (20060101); H04N 19/13 (20140101); H04N 19/60 (20140101); H04N 19/12 (20140101); H04N 19/136 (20140101); H04N 19/18 (20140101); H04N 19/169 (20140101);