Source: http://www.google.com/patents/US20080030384?ie=ISO-8859-1
Timestamp: 2014-07-14 09:01:02
Document Index: 273816357

Matched Legal Cases: ['Application No. 2006', 'Application No. 2007', 'art 530', 'art 540', 'art 550', 'art 560', 'art 610', 'art 600', 'art 530', 'art 710', 'art 700']

Patent US20080030384 - Encoding apparatus, decoding apparatus, encoding method, computer readable ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsThis invention provides an encoding apparatus including a group generating unit that puts plural information values to be compressed together and generates a group of information values to be compressed; a code assignment unit that assigns a code to each group generated by the group generating unit;...http://www.google.com/patents/US20080030384?utm_source=gb-gplus-sharePatent US20080030384 - Encoding apparatus, decoding apparatus, encoding method, computer readable medium storing program thereof, and computer data signalAdvanced Patent SearchPublication numberUS20080030384 A1Publication typeApplicationApplication numberUS 11/882,672Publication dateFeb 7, 2008Filing dateAug 3, 2007Priority dateAug 7, 2006Also published asUS7548175Publication number11882672, 882672, US 2008/0030384 A1, US 2008/030384 A1, US 20080030384 A1, US 20080030384A1, US 2008030384 A1, US 2008030384A1, US-A1-20080030384, US-A1-2008030384, US2008/0030384A1, US2008/030384A1, US20080030384 A1, US20080030384A1, US2008030384 A1, US2008030384A1InventorsTaro Yokose, Masanori Sekino, Tomoki TaniguchiOriginal AssigneeFuji Xerox Co., Ltd.Export CitationBiBTeX, EndNote, RefManReferenced by (2), Classifications (4), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetEncoding apparatus, decoding apparatus, encoding method, computer readable medium storing program thereof, and computer data signalUS 20080030384 A1Abstract This invention provides an encoding apparatus including a group generating unit that puts plural information values to be compressed together and generates a group of information values to be compressed; a code assignment unit that assigns a code to each group generated by the group generating unit; and an information encoding unit that encodes the information values to be compressed belonging to each group, using the code assigned to each group.
a group generating unit that puts a plurality of information values to be compressed together and generates a group of information values to be compressed; a code assignment unit that assigns a code to each group generated by the group generating unit; and an information encoding unit that encodes the information values to be compressed belonging to each group, using the code assigned to each group. 2. The encoding apparatus according to claim 1,
wherein the group generating unit puts the plurality of information values to be compressed together and generates a lower-order group of information values to be compressed; the apparatus further includes a group sorting unit that sorts a lower-order group generated by the group generating unit to a higher-order group; the code assignment unit assigns a code to the higher-order group; and the information encoding unit encodes the information values to be compressed of a lower-order group belonging to the same higher-order group, using a variable length code assigned to the higher-order group. 3. The encoding apparatus according to claim 2,
wherein the group generating unit puts every predetermined number of information values to be compressed which have been input together in order of input and generates a lower-order group containing the predetermined number of information values to be compressed; and the group sorting unit sorts the lower-order group to a higher-order group, based on the numbers of bits to represent, respectively, the information values to be compressed belonging to the lower-order group. 4. The encoding apparatus according to claim 1,
wherein the code assignment unit assigns an entropy code to each group, according to the probability of appearance of each group. 5. The encoding apparatus according to claim 1, further comprising:
an information converting unit that converts each of input information values to be compressed to a value represented in a string of bits fewer than the bits of the original information value to be compressed; wherein the information encoding unit encodes the information values to be compressed belonging to each group, using bit strings converted by the information converting unit and a code assigned to the group. 6. The encoding apparatus according to claim 1, further comprising:
a table-use encoding unit that encodes the group of information values to be compressed using a code table showing linkage between a plurality of information values which can be contained in the group and code data of these information values; and a directing unit that directs the group of information values generated by the group generating unit to a combination of the code assignment unit and the information encoding unit, or to the table-use encoding unit; wherein the code assignment unit assigns a code to the group directed by the directing unit, and the compressed information encoding unit encodes the information values of the group directed by the directing unit. 7. A decoding apparatus, comprising:
a code length parsing unit that, for a group including a plurality of compressed information values, parses code length of each of the compressed information values belonging to the group, based on a code assigned to the group; and a compressed information decoding unit that decodes the compressed information values belonging to the group, based on the code length of each compressed information value parsed by the code length parsing unit. 8. An encoding method comprising:
putting a plurality of information values to be compressed together and generating a group of information values to be compressed; assigning a code to each generated group; and encoding the information values to be compressed belonging to each group, using the code assigned to each group. 9. A computer readable medium storing a program causing a computer to perform the following:
putting a plurality of information values to be compressed together and generating a group of information values to be compressed; assigning a code to each generated group; and encoding the information values to be compressed belonging to each group, using the code assigned to each group. 10. A computer data signal embodied in a carrier wave for enabling a computer to perform a process for encoding, the process comprising:
putting a plurality of information values to be compressed together and generating a group of information values to be compressed; assigning a code to each generated group; and encoding the information values to be compressed belonging to each group, using the code assigned to each group. Description
CROSS-REFERENCE TO RELATED APPLICATIONS This application is based on and claims priority under 35 USC 119 from Japanese Patent Application No. 2006-214348 filed Aug. 7, 2006 and Japanese Patent Application No. 2007-184219 filed Jul. 13, 2007.
BACKGROUND Technical Field The present invention relates to an encoding apparatus, a decoding apparatus, an encoding method, a computer readable medium storing a program thereof, and a computer data signal.
SUMMARY According to an aspect of the present invention, there is provided an encoding apparatus including a group generating unit that puts plural information values together and generates a group of information values; a code assignment unit that assigns a code to each group generated by the group generating unit; and an information encoding unit that encodes the information values belonging to each group, using the code assigned to each group.
DETAILED DESCRIPTION To help understanding of the exemplary embodiment of the present invention, its background and outline are first discussed.
For example, Huffman coding assigns one codeword to each one symbol value; that is, the Huffman coding process gives one output (codeword) to one input (symbol). Here, the symbol is information to be compressed (encoded) by entropy coding. In other words, the term of �information to be compressed� used herein may include symbols to be encoded by entropy coding and, additionally, compressed data (e.g., image data or discrete cosine transform (DCT) coefficients in a JPEG encoding process) before data modeling is performed thereon.
[Hardware Structure] Then, a hardware structure of the image processing apparatus 2 in the present exemplary embodiment is described.
[Encoding Program] FIG. 3 illustrates a functional structure of an encoding program 5 embodied in a computer readable medium for realizing the encoding method of the exemplary embodiment when executed by the controller 20 (FIG. 2).
The symbol converting part 530 converts each symbol included in the block to a symbol represented in the required number of bits, as illustrated in FIG. 4B. The number of bits required for symbol representation (the required number of bits) is obtained by adding 1 to the base 2 log of the symbol value. However, a symbol value of 0 is defined to be 0 bit. For example, a symbol value of 1 is represented in one bit, symbol values of 2 and 3 are represented in two bits, and symbol values of 4 to 7 are represented in three bits. In this example, because a source symbol is made up of 8 bits, the required number of bits for a symbol can be determined as one of 9 bits from 0 to 8 bits. For example, given that the required numbers of bits for the symbols in a block are 3, 1, 4, and 1, respectively, the group sorting part 540 of this example sorts the block to a higher-order group based on the combination �3, 1, 4, 1� of the required numbers of bits. Thus, this block is contracted to a higher-order group �3141�. A possible number of different higher-order groups is 6561 (=9 raised to the fourth power). The code assignment part 550 measures the probability of block appearance per higher-order group, constructs a Huffman code, and creates a codeword.
To the higher-order group �3141�, one of 512 (=8�2�16�2) blocks may be contracted. To identify each source block, values represented in the required numbers of bits for each symbol are appended following the above codeword. Specifically, as illustrated in FIG. 4C, the code coalescing part 560 coalesces the code assigned to the higher-order group (the codeword for the higher-order group �3141�) and the symbol values (represented in the required numbers of bits) contained in the block.
[Coding Operation] Then, overall operation of the image processing apparatus 2 (encoding program 5) is described.
[Decoding Program] FIG. 6 illustrates a functional structure of a decoding program 6 embodied in a computer readable medium, which is executed by the controller 20 (FIG. 2).
[Decoding Operation] FIG. 7 is a flowchart of a decoding process (S20) by the decoding program 6 (FIG. 6).
At step 220 (S220), the symbol extracting part 610 retrieves the bit string of each symbol (i.e., the symbol represented in the required number of bits) out of the bit string of the target block, based on the required number of bits for each symbol parsed by the code length parsing part 600. For example, as illustrated in FIG. 4C, when decoding a group code corresponding to the higher-order group �3141�, 3 bits, 1 bit, 4 bits, and 1 bit are retrieved in order from the beginning as the bit strings (codes) of the symbols in the block.
MODIFICATION EXAMPLE 1 Next, a modification example 1 of the above-described exemplary embodiment is described.
MODIFICATION EXAMPLE 2 In the above-described exemplary embodiment, the symbols in a block are respectively represented in the required numbers of bits, as illustrated in FIG. 10A. On the other hand, in a second modification example, out of the bit string of each symbol represented in the required number of bits, the most significant bit (i.e., the MSB of the symbol) is further removed, as illustrated in FIG. 10B. Specifically, when symbols to be represented in N bits include a bit having the same value, this bit may be removed. For example, when symbol 2 and symbol 3 are represented in two bits, the MSB (Most Significant Bit) of each symbol is 1. Thus, it is not needed to include this bit in the 2-bit representation.
In the second modification example, when N-bit representation is used to represent one particular value of symbols, the N-bit representation may be removed. For example, a symbol value of �1� is represented in one bit as illustrated in FIG. 10A, the 1-bit representation is only used to represent the particular value of �1� of symbols and, therefore, the bits having the symbol value of �1� can be removed, as illustrated in FIG. 10B. This symbol value of �1� can be decoded by decoding �1� in the group code �3141�.
MODIFICATION EXAMPLE 3 In the foregoing exemplary embodiment and modification example 1, encoding is performed on an implicit assumption that symbols with smaller values appear at higher frequencies. Particularly when the source coder is provided in the preceding stage, such assumption is quite commonly applied and it is relatively simple to design the source coder to realize this.
MODIFICATION EXAMPLE 4 As a further modification example which is a variant of the above modification example 3, the encoding process as described in the above modification example 2 (or the exemplary embodiment) is performed in the first path, during which the appearance frequencies of the symbols are measured. Then, if a higher compression ratio is desired, a re-encoding process is further performed, as described in the above modification example 3. Since the amount of coded data to be output after the re-encoding process can be estimated accurately from the measured appearance frequencies of the symbols, it may be determined whether to perform the re-encoding process based on this estimation in some implementation.
OTHER MODIFICATION EXAMPLES While, in the foregoing exemplary embodiment, the symbol converting part 530 converts symbols on a symbol by symbol basis, this conversion may be performed in units of plural symbols. For example, a lookup table defining combinations of patterns of two succeeding symbols may be created and referenced for the conversion. This implementation may increase the compression ratio of source data to be stored.
Second Embodiment Next, a second exemplary embodiment is described.
However, generally, such table becomes very large when plural symbols are input as in the case of the above exemplary embodiment, therefore this arrangement is often unreasonable. In the above exemplary embodiment, assuming that one block contains eight symbols, when N=1 holds, (2̂1)̂8=256 outputs may occur. Similarly, when N=2 holds, (2̂2)̂8=6.6�10̂4 outputs may occur. When N=8 holds, (2̂8)̂8=1.8�10̂19 outputs may occur. Thus the table has a size which cannot be realized without difficulty by current techniques.
FIG. 12 shows a code table in a case where one block contains 8 symbols and N=1 or N=2 holds. Assuming that each symbol is represented in 8 bits, the code table in FIG. 12 may be constructed with 6.6�10̂4 entries. For reference to the code table by the table encoding part 710, a process to retrieve an entry from 8 bit�8 data is required. This may be realized by simple bit manipulation.
MODIFICATION EXAMPLE Next, a modification example of the second exemplary embodiment is described.
The directing part 700 of the example determines whether the current mode is the monochrome mode or not in accordance with an external instruction. In the monochrome mode, an input image is generated with monochrome binary values, or output in monochrome binary values is designated. In the monochrome mode, the value of an image signal is always one of 0 and 255. In this case, the prediction residual is any one of −255, 0 and 255. In consideration of representation using a complement of 2 in 8-bit limitation, the above values are equivalent to 1, 0 and −1. The uniqueness is not lost in this conversion. For example, when a true value is 0 and a predicted value is 255, as a prediction residual is −255, to reproduce the true value from the predicted value and the prediction residual, 255+(−255)=0 holds. Assuming that this residual is represented as 1, when the above expression is substituted with 8-bit limited calculation, 255+l=256 holds. It is understood that in 8-bit limited calculation, i.e., when lower-order 8 bits are taken, 256→0 holds and the true value may be reproduced. This calculation is referred to as �wrap around� and is a general technique.
Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8737750Feb 9, 2011May 27, 2014Telefonaktiebolaget L M Ericsson (Publ)Pixel block compression and decompressionWO2012105882A1 *Feb 4, 2011Aug 9, 2012Telefonaktiebolaget L M Ericsson (Publ)Pixel block compression and decompression* Cited by examinerClassifications U.S. Classification341/59International ClassificationH03M7/00Cooperative ClassificationH03M7/30European ClassificationH03M7/30Legal EventsDateCodeEventDescriptionNov 14, 2012FPAYFee paymentYear of fee payment: 4Aug 3, 2007ASAssignmentOwner name: FUJI XEROX CO., LTD., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:YOKOSE, TARO;SEKINO, MASANORI;TANIGUCHI, TOMOKI;REEL/FRAME:019707/0352Effective date: 20070726RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google