Patent ID: 7570827
Filing Date: 2009-08-04
Classification: G06T,H04N

Abstract:
1. A method of compressing a sequence of n coefficients by determining a cost-determined sequence of n coefficient indices represented by a cost-determined sequence of (run, size, ID) triples under a given quantization table and run-size distribution, wherein each sequence of (run, size, ID) triples defines a corresponding sequence of coefficient indices such that (i) each index in the corresponding sequence of coefficient indices is a digital number, (ii) the corresponding sequence of coefficient indices includes a plurality of values including a special value, and (iii) each (run, size, ID) triple defines a run value representing a number of consecutive indices of the special value, an integer value ID specifying the amplitude of the index following the number of consecutive indices of the special value and a size value defining a number of bits required to store an index within a category specified by the ID value, the method comprising: using a computer to perform the steps of: (a) using the given quantization table and run-size distribution to formulate a cost function for a plurality of possible sequences of (run, size, ID) triples; (b) applying the cost function to each possible sequence in the plurality of possible sequences of (run, size, ID) triples to determine an associated cost; (c) selecting the cost-determined sequence of (run, size, ID) triples from the plurality of possible sequences of (run, size, ID) triples based on the associated cost function of possible sequences of (run, size, ID) triples; and (d) encoding the corresponding selected sequence of (run, size) pairs using Huffman coding; wherein step (c) comprises: (i) providing a sequence of n nodes in one-to-one relation with the sequence of n coefficients, such that each coefficient C (ii) providing an end node following the sequence of n nodes; (iii) providing a plurality of connections between pairs of nodes to represent the plurality of possible (run, size, ID) triples; (iv) determining the associated cost as an associated incremental cost for each connection (run, size) in the plurality of connections; (v) determining a least cost sequence of connections from the plurality of connections, wherein the sequence of connections extends from the first node in the sequence of n nodes to the end node; and (vi) determining the cost-determined sequence of (run, size, ID) triples from the least cost sequence of connections; and wherein providing the plurality of connections comprises: (A) for each node in the sequence of n nodes having a predecessor node preceding that node in the sequence of n nodes, and for each predecessor node that precedes that node in the sequence of n nodes, such that the number of intermediary nodes separating that node from that predecessor node does not exceed a maximum run value in the plurality of possible (run, size, ID) triples, establishing a number of connections connecting that node to that predecessor node, such that the number of connections equals a maximum size value in the plurality of possible (run, size, ID) triples, wherein each pair of connected nodes corresponds to a different run value and each connection between connected nodes corresponds to a different size value in the plurality of possible (run, size, ID) triples; (B) for each node other than the last node in the sequence of n nodes having a predecessor node preceding that node in the sequence of n nodes, such that the number of intermediary nodes separating that node from that predecessor node equals the maximum run value in the plurality of possible (run size, ID) triples, establishing a further single connection connecting that node to that predecessor node, wherein the single connection corresponds to a zero runlength code; and (C) for each node in the sequence of n nodes, establishing a single connection to the end node, wherein the single connection corresponds to an end-of-block code.