Compression of palettized images and binarization for bitwise coding of M-ary alphabets therefor

A method of compressing input symbols, where each input symbol is selected from an alphabet of M symbols to represent a pixel in a palettized image, into codewords which are represented in fewer bits and from which the input symbols can be decoded, comprising the steps of:

• reading an input stream of M-ary input symbols;
• binarizing said M-ary input symbols into a stream of binarized symbols;
• identifying a context for each bit of each binarized symbol, wherein a context for said each bit is determined by said each bit's position within said each binarized symbol and a context symbol which is a symbol other than said each binarized symbol and is in a predefined relationship to said each binarized symbol, said predefined relationship being such that, when decoding, said each binarized symbol is decoded after said context symbol;
• determining a binary entropy code for said contexts;
• encoding each bit of said stream of binarized symbols according to said binary entropy code determined from the context of said each bit of said stream and the value of said each bit of said stream.

A method of compressing input symbols, where each input symbol is selected from an alphabet of M symbols to represent a pixel in a palettized image, into codewords which are represented in fewer bits and from which the input symbols can be decoded, comprising the steps of:

• reading an input stream of M-ary input symbols;
• binarizing said M-ary input symbols into a stream of binarized symbols;
• identifying a context for each bit of each binarized symbol, wherein a context for said each bit is determined by said each bit's position within said each binarized symbol and bits of a binarization of a context symbol, said context symbol being a symbol other than said each binarized symbol in a predefined relationship to said each binarized symbol, said predefined relationship being such that, when decoding, said each binarized symbol is decoded after said context symbol;
• determining a binary entropy code for said contexts;
• encoding each bit of said stream of binarized symbols according to said binary entropy code determined from the context of said each bit of said stream and the value of said each bit of said stream.

A compression engine, for compressing M-ary symbols, each representing a pixel value in a palettized image and selected from an alphabet of M symbols, into codewords which are represented in fewer bits and from which the M-ary symbols can be extracted, the compression engine comprising:

• means for determining a distribution of symbols in said input stream;
• a reindex table generator which determines a binarization for each of the M possible symbols, said binarization is based on a distribution of the M-ary symbols, wherein said binarization is represented by a reindex table;
• reindexing means for binarizing each M-ary symbol into a binary sequence according to said reindex table, thereby transforming the M-ary symbols representing the palettized image into a binary bit stream;
• a binary entropy encoding compressor which compresses said binary bit stream and outputs a resulting codeword stream,
• wherein said binarization is selected to minimize the bitwise entropy of the binarized input stream.

An entropy encoder, wherein input symbols are encoded based on a context provided by context symbols, which are also input symbols, comprising:

• symbol reordering means, coupled to a symbol input of the entropy encoder, for reordering input symbols from an input stream order to a reordered stream order;
• a context modeler, coupled to an output of said symbols reordering means, which accepts input symbols in said reordered stream order and stores input symbols as necessary to determine context of a current input symbol from said current input symbol's context symbols;
• a probability estimator, coupled to receive said current input symbol and a context of said current input symbol from said context modeler, for estimating the probability of said current input symbol occurring given its context;
• and
• a bit generator, coupled to said probability estimator, for generating codewords based on probability estimates provided by said probability estimator, said codewords being a compressed representation of said reordered stream of input symbols,
• wherein said symbol reordering means reorders input symbols such that a reordered distance between said current input symbol and said current input symbol's context symbols in said reordered stream is greater than an original distance between said current input symbol and said current input symbol's context symbols in said input stream.

An entropy coder, wherein a plurality of bits taken from an input bit stream are coded in parallel, comprising:

• a context modeler which accepts an input bit and outputs a pairing of said input bit with an associated context of said input bit, said context determined from at least one of previously input bits, said input bit's position within an input symbols and a predetermined context model;
• a context-sensitive parallel coder, coupled to receive pairings output from said context modeler, which generates codewords based on probability estimates of input bits given said paired contexts, said codewords being a compressed representation of said stream of input bits, and said parallel coder comprising:
• means for forming a parallel stream of input bits, grouping N bits into a set of bits;
• and
• a plurality of N coding stages, each of which processes one input bit from said set of bits so grouped;
• and
• bit reordering means, coupled between an input for the input bit stream and said context modeler, for reordering input bits such that a context of a bit in a set of bits is independent of other bits in said set of bits.

An entropy coder, wherein a plurality of bits taken from an input bit stream are coded in a pipeline of a plurality of stages, comprising:

• a context modeler which accepts an input bit and outputs a pairing of said input bit with an associated context of said input bit, said context determined from at least one of previously input bits, said input bit's position within an input symbols and a predetermined context model;
• a context-sensitive pipeline coder, coupled to receive pairings output from said context modeler, which generates codewords based on probability estimates of input bits given said paired contexts, said codewords being a compressed representation of said stream of input bits, and said pipeline coder comprising:
• an input stage, which processes input bits output by said context modeler;
• a plurality of intermediate stages which process outputs of said input stage, each coupled to other stages in a pipelined manner, wherein at least one stage is a context-sensitive stage which processes an input bit based on said input bit's paired context;
• and
• an output for a final stage of said plurality of intermediate stages;
• and
• bit reordering means, coupled between an input for the input bit stream and said context modeler, for reordering input bits such that a context of a given bit is independent of other bits being processed in said plurality of intermediate stages when said given bit is being processed in said context-sensitive stage.