Abstract:
A trellis quantizer that produces an output sequence adapted for successively refinable decoded approximation employs a multi-level trellis graph. At any given level a next refinement level is obtained by replacing each transition of the trellis graph at the given level with a trellis graph. The codevectors of the refined trellis quantizer can be optimized for all levels of refinements by an iterative process that assesses the distortions resulting from modifying the codevectors. The optimizing is carried out concurrently for all levels of refinement, achieving thereby a quantizer that is optimized for whatever level of refinement the quantizer is asked to carry out. This optimization takes into account the probability distribution of incoming signal levels.

Description:
REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Application No. 60/064,311, filed Nov. 5, 1997. This application is also related to an application filed on even date herewith, which carries the Ser. No. 09/072,782, and is titled &#34;Multiple Description Trellis Coded Quantization&#34;. 
    
    
     BACKGROUND OF THE INVENTION 
     This invention relates to coding and, more particularly, to trellis coding. 
     In recent years, successively refinable or rate-scalable source coders have received growing attention. By selecting different sub-streams of the output of such coders, various levels of encoding rate and distortion can be achieved. 
     One immediate application of rate-scalability is in progressive transmission. Sometimes the utility of progressive transmission is readily apparent because it is central to an application. One important example is in telemedicine, where a specialist must sort through and retrieve a large number of medical images over a network. If the images can be transmitted progressively so that unneeded images, or sections of images, can be identified before they have been transmitted with high fidelity, then cost and bandwidth can be saved. A similar application is the transmission of maps in which a low-resolution map of a big area can be transmitted first. The user can identify a specific area in the received map and request a high-resolution map of the specified region. 
     Another application of an embedded bit stream is in the transmission of video over an asynchronous transfer mode (ATM) network where some ATM cells may be lost in transit through the network. A video coder with an embedded output bit stream can mark the ATM cells with an importance measure; as a video frame is coded progressively, the descriptions become successively less important since they contribute less to the reduction of distortion. Cells in the network can then be dropped preferentially based upon their importance in distortion reduction. 
     Also, when multicasting over heterogeneous networks, rate-scalability provides the opportunity of using one bit stream for all receivers and intelligently dropping the less important portions of the bit stream for users with less available bandwidth. 
     Additionally, in many practical applications where the signal is transmitted over a noisy channel, the rates of the source and channel codes must be adjusted according to the level of noise in the channel. If the channel is a time-varying channel, as it is in many wireless communication situations, it is prudent to adaptively vary the rate allocation between the source and channel coding operations. Successive refinability allows the possibility of adapting the rate of the source encoder in a straightforward manner. Of course, similar rate-scalability features are needed for the channel coding part. 
     A powerfull source coding scheme for memoryless sources is trellis coded quantization (TCQ). See M. W. Marcellin and T. R. Fischer, &#34;Trellis coded quantization of memoryless and Gauss-Markov sources,&#34; IEEE Trans. Comm., Vol. 38, January 1990, pp. 82-93. It has been shown that for a memoryless uniform source, trellis coded quantizers provide mean squared errors (MSEs) within 0.21 dB of the theoretical distortion bounds (for given rates). The performance of a TCQ is much better than that of the best scalar quantizer (Lloyd-Max quantizer) at the same rate. 
     Until now, it has been thought that trellis coding does not lend itself to successive refinability. In &#34;Multi-state trellis coded quantization (MS-CW)&#34;, reported by H. A. Aksu and M. Salehi, in Proc. Conf. Inform. Sciences and Systems,Baltimore, Md., March 1995, the idea of multi-stage quantization is combined with that of TCQ. Therein, each stage of TCQ quantizes the error between the original and the quantized output of the previous stage. Unfortunately, multi-stage TCQ (MS-TCQ) suffers from about 2 dB performance degradation compared to the performance of TCQ. In &#34;Progressive transmission in trellis coded quantization-based image coders,&#34; P. J. Sementilli et al, reported in Conf. Image Processing, Santa Barbara, Calif., October 1997, the TCQ structure is preserved and trellis coding is applied, but only to the last stage. Using a successive approximation-type setting, the inverse TCQ operation is performed only approximately for all intermediate stages. The resulting quantization scheme has been utilized for progressive transmission of images, but it doesn&#39;t take full advantage of the trellis structure. 
     SUMMARY 
     An improvement in the art is realized with a successively refinable trellis quantizer. A trellis quantizer at a given level of refinement is refined to a next refinement level by replacing each transition of the trellis graph at the given level with a trellis graph. The codevectors of the refined trellis quantizer can be optimized for all levels of refinements by an iterative process that assesses the distortions resulting from modifying the codevectors. The optimizing is carried out concurrently for all levels of refinement, achieving thereby a quantizer that is optimized for whatever level of refinement the quantizer is asked to carry out. This optimization takes into account the probability distribution of incoming signal levels. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     FIG. 1 presents an arrangement that can benefit from a successively refinable coding arrangement; 
     FIG. 2 shows a one-bit trellis coding graph; 
     FIG. 3 depicts a two-bit trellis coding graph; 
     FIG. 4 illustrates how a refinement is effected in the FIG. 1 trellis coding graph; 
     FIG. 5 presents the entire FIG. 1 trellis coding graph with a refinement with an identical graph; 
     FIG. 6 shows a flow chart of the codevectors generation process; and 
     FIG. 7 illustrates a set of code vectors for successively refinable trellis quantizer. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 presents an arrangement that can benefit from successively refinable coding. Block 110 corresponds to a transmitter that encodes an incoming signal and outputs a robust code that is transmitted, via connection channel 150, to receivers 200 and 300. Receiver 200 is adapted to receive, respond to, and benefit from the full store of information that is contained in the code sent by block 110. By contrast, receiver 300 is adapted to respond to, and benefit from, only a subset of the information contained in the code sent by block 110. Illustratively, block 110 might be an encoder/transmitter for a high definition TV (HDTV) signal in a system where there is a requirement that non-HDTV sets must be able to view the same programming. Alternatively, in a different embodiment, block 110 may be an encoder that can be adjusted to develop a code at a specified level of refinement, and receivers 200 and 300 are coupled to block 110 (probably not simultaneously) to request information at a specified level of refinement. The specification of a particular level of coding granularity is delivered to block 110 via channels 201 and 202 and may depend, for example, on the characteristics of channel 150. Channels 201 and 202 are not needed, of course, in the first embodiment mentioned above. In still another embodiment block 110 sends the encoded information in different sub-channels of channel 150, to allow receivers 200 and 300 to choose, independently, the level of granularity that they are able to handle. 
     To better understand the principles disclosed herein, it is helpful to review how trellis coding is achieved. FIG. 2 presents a prior art four-state trellis graph that may be used to encode an incoming signal. Circles 10-13 designate four possible states of a coding stage, and circles 21-23 designate the immediately subsequent four possible states of the coding stage, i.e., after one transition. The four-state graph of FIG. 2 provides a template for encoding an incoming signal that comprises a sequence of values, e.g., quantized voltage samples, into a sequence of bits, based on quantization levels c 0 , c 1 , c 2 , and c 3 , which are associated with transitions D0, D1, D2, or D3, respectively. In trellis coding, the encoding is carried out on frames of the incoming signal. That is, the coded sequence for the frame is not selected until the entire frame has been processed. This approach allows the encoding process to minimize the overall, average, quantization error, which may be expressed by ##EQU1## where L is the number of samples that are encoded, (x i  -x i ) 2  is the magnitude of the difference between the i th  signal sample and its corresponding quantized (decoded) level, squared, and p(x i ) is the probability of signal sample x i . Equation (1) provides a measure of the distortion experienced, but it should be realized that other distortion measures may be used. The following specific example, which illustrates the encoding process, might be helpful in understanding the coding process using TCQ. 
     Assume that the quantization levels of c 0 , c 1 , c 2 , and c 3  were selected to correspond to levels -10, -3, +2, and +12, respectively. That is, state 10 in FIG. 2 resolves between levels -10 and +2, and selects either transition D0 or D2. Similarly, state 11 resolves between levels -3 and +12, and selects either transition D1 or D3. Likewise, state 12 resolves between levels +2, and -10 and selects either transition D2 or D0. Lastly, state 13 resolves between levels +12, and -3 and selects either transition D3 or D1. Assume also that the signal frame to be encoded comprises the sequence {+4, +8, 0, -4, +3, -7, -5}. 
     The encoding process employs the FIG. 2 trellis as a template for each one of the input samples, with states 20-23 of one template merging into states 10-13 of the next template. The table below shows the calculations that the TCQ performs on the frame before reaching a decision regarding the sequence of quantizer levels that would best represent the incoming signal frame. 
     
                       TABLE 1______________________________________ ##STR1##______________________________________ 
    
     Each cumulative sum cell in the above table contains two cost values that are derived from the FIG. 2 graph. The lower cost value is selected for the next calculation step, and is shaded in the above table for the reader&#39;s convenience. Illustratively, the pattern of calculations which responds to the input sample that has the value 0 proceeds as follows: 
     the 620 value derives from adding the 520 cumulative cost to the 10 2  cost that accrues from assuming that quantizer level -10 would be used; 
     the 129 value derives from adding the 125 cumulative cost to the 2 2  cost that accrues from assuming that quantizer level +2 would be used; 
     the 524 value derives from adding the 520 cumulative cost to the 2 2  cost that accrues from assuming that quantizer level +2 would be used; 
     the 225 value derives from adding the 125 cumulative cost to the 10 2  cost that accrues from assuming that quantizer level -10 would be used; 
     the 241 value derives from adding the 232 cumulative cost to the 3 2  cost that accrues from assuming that quantizer level -3 would be used; 
     the 164 value derives from adding the 20 cumulative cost to the 12 2  cost that accrues from assuming that quantizer level +12 would be used; 
     the 376 value derives from adding the 232 cumulative cost to the 12 2  cost that accrues from assuming that quantizer level +12 would be used; and 
     the 29 value derives from adding the 20 cumulative cost to the 3 2  cost that accrues from assuming that quantizer level -3 would be used. 
     The lowest costs at this point in the calculations are 129, 225, 164, and 29. 
     Carrying out the cost calculations to the end of the frame, it turns out that the lowest frame error cost of the illustrative example is 86. This cost is reached when the path followed corresponds to the sequence of shaded cells shown in Table 
     
                       TABLE 2______________________________________ ##STR2##______________________________________ 
    
     This path results from selecting transitions D2, D3, D1, D1, D1, D1 of the FIG. 2 trellis graph, which effectively corresponds to selecting quantizer levels +2, +12, -3, -3, -3, -3, and -3 at the encoder. 
     On the decoder side, a codebook of quantized levels e i  is used to decode the received bits and convert them to sample levels. This set corresponds to the set of quantized levels employed in the encoder, c i , and typically e i  is chosen to equal c i . However, whatever codebook of quantized levels is used, it is fairly obvious that a decoded signal which corresponds to the encoded data would not be an exceptionally good representation for the incoming signal sequence {+4, +8, 0, -4, +3, -7, -5}. For example a decoded sequence of {+2, +12, -3, -3, -3, -3, -3} is certainly not close to the input sequence. Still, it is the best representation within the constraints of the trellis code schema selected. 
     One characteristic of the schema selected is that at any one point a single bit of the quantized signal dictates the state that can be reached, and the single bit can only resolve one out of two states. If two bits were used, then four states could be resolved from any one state, and a decoded signal would more likely be close to the encoded incoming signal sequence. FIG. 3 presents an illustrative trellis graph for an arrangement employing two bits for encoding each sample. 
     The objective of this invention is to create an arrangement that includes the benefits of TCQ even when some of the data might be missing at the receiver, might not be employed by the receiver, or might be sent to the receiver to successively refine the decoded signal. For example, one objective is to create an encoded signal sequence that can be used by one user, while another user employs only a subset of the sequence. Another objective is to create a signal sequence but to send only a portion thereof: the remainder of the sequence would be sent only if the receiver requested it. 
     Until now, it has been thought that trellis coding does not provide such successive approximation capabilities because each state of a decoder in the decoding process, like the state of the encoder in the encoding process, depends on the previous states. Missing a piece of data is likely to completely destroy the integrity of subsequently decoded signals. 
     This problem is overcome, in accordance with the principles disclosed herein by successively replacing each transition in a trellis graph with another trellis graph, and such substitutions can be repeated as many times as desired. This is illustrated in FIG. 4, which shows the D0 and D2 transitions of the FIG. 2 graph (transitions 101 and 100, respectively) replaced with FIG. 2 trellis graphs. Consequently, a sample is represented by one bit that effectively selects either the D0 or the D2 path, and by a second bit that selects a path through the second trellis graph. A full representation of the FIG. 2 graph, refined, or expanded by replacing each of the transitions with a trellis graph, is shown in FIG. 5. Note that there are now 16 output states of the resulting trellis graph. 
     FIG. 5 illustrates a first level of successive refinement, but it should be understood that further successive refinements are directly extendible from FIG. 5 in an identical manner. 
     The remaining question is how to define the quantization levels for the different transitions of the successively refinable trellis quantizer (the -10, -3, +2, and +12 levels in the above example). In our approach, these levels, which make up the codebooks of the different levels in the successive refinement, are designed together based on a training sequence that has the same probability distribution as the expected actual signal. This is in contrast to an approach where the codebook for each refinement stage is designed independently. These are also the levels assigned by the decoder. 
     The basic procedure is iterative, where an appropriate encoder design is fixed, and a best decoder is derived. The derived decoder is then fixed, and a best encoder is derived for that decoder. This completes one iteration, which is repeated until the improvement in the distortion falls below a preselected threshold. 
     More specifically, the average distortion for a trellis code can be expressed by ##EQU2## where x(n) is a sample in a training sequence of length L, and x(n) is a corresponding decoded approximation of c i   j . The average distortion for an arrangement where each successive refinement represents another level,j, is ##EQU3## where p(j) is the probability distribution of using a particular level of refinement, and J is the maximum number of refinement levels. That is, for a given set of codebooks, when the distortion measure of equation (3) is minimized, one obtains the best outputs at different levels of refinement. 
     If B i   j  is defined as the set of all training samples which are encoded as c i   j , where the superscripts j designates a level, and the subscript i designates the different quantization levels in the j th  level, and |B i   j  | corresponds to the number of samples in B i   j , then when c i   j  is replaced with c i   j  defined by ##EQU4## the resulting set of codebooks provides a lower distortion. It may be noted that x(n)εB i   j  does not necessarily mean that c i   j  is the closest quantization level to x(n) . 
     FIG. 6 presents a flow diagram of the design approach. Block 1000 initializes the process by picking a small positive number as the threshold ε, picking an initial set of codevectors, setting index m=1 and setting the 0 th  iteration distortion value D.sup.(0) =+∞. 
     An initial set of codevectors is presented in FIG. 7. In constructing this initial set, a number of items need to be noted, First, the span of inputs (signal span) is defined by the span between points 100 and 200. In selecting the codebook for the first level of refinement, where the four quantizer levels 1, 2, 3, and 4 are selected, these quantizer levels do not need to divide the signal span absolutely equally. The probabilities of the input signal can be considered. However, since the selected quantizer levels are likely to be altered by the FIG. 6 process, quantizer levels 1, 2, 3, and 4 could be selected to divide the signal span equally (although, to maintain generality, the FIG. 6 division is not equal). Second, in selecting the quantizer levels for a subsequent refinement, the expansion of each node (quantizer level) in one refinement level to a set of quantizer levels for the successive refinement level must select quantizer levels such that they would cover the proper signal span. For example, in choosing quantizer levels 11, 12, 13, and 14, one should be cognizant of the fact that if quantizer level 1 was reached, it means that quantizer level 3 could have been reached--but was not reached because of the signal&#39;s value. One should also be cognizant that quantizer levels 2 and 4 were not in the running at all. Consequently, quantizer levels 11, 12, 13, 14, 31, 32, 33, and 34 should be selected to span the entire signal range (from point 100 to point 200), ignoring the contribution from quantization levels 2 and 4. Likewise, quantizer levels 21, 22, 23, 24, 41, 42, 43, and 44 should be selected to span the entire signal range, ignoring the contribution from quantization levels 1 and 3. Third, there is no requirement that all of the quantizer levels need to be distinct. For example, quantizer levels 21 and 22 could have been selected to equal each other. FIG. 7 shows the first and second refinement levels, and a quarter of the third refinement level. 
     Having selected a set of codebooks, control passes to block 1100 which encodes a training sequence, using the algorithm described above. Block 1100 then obtains a distortion measure by first decoding the encoded bits produced by block 1100 to obtain a sequence of samples that approximates the training sequence and by comparing the training sequence to the decoded approximation thereto according to equation (2), denoting it as D.sup.(m). Block 1100 also ascertains the set of B i   j  &#39;s. Control then passes to block 1200 where the distortion improvement measure ##EQU5## is evaluated. Thereafter, control passes to decision block 1300 where the distortion improvement measure is compared to ε. When the distortion improvement measure exceeds ε, control passes to block 1400 where the quantization levels are updated using equation (4). The calculation of equation (4) is repeated for each distinct quantizer level of each level of refinement. From block 1400, the process continues to block 1500 where the index m is incremented and control is passed to block 1100. 
     The above disclosed the principles of this invention, but it should be realized that various features were disclosed merely for illustrative purposes, and that other embodiments are possible, with different embedded features. For example, FIG. 5 illustrates how a trellis quantizer having a trellis graph of FIG. 2 can be refined by replacing each transition in the FIG. 2 graph with a FIG. 2 graph. It should be realized, however, that another trellis graph can be employed to replace the FIG. 2 graph transitions, and that the two graphs don&#39;t have to employ the same number of bits. 
     The above disclosure illustrates the principles of this invention through illustrative embodiments of this invention, and various modifications and enhancements can be introduced by artisans without departing from the spirit and scope of this invention, which is defined by the following claims. For example, the FIG. 2 trellis that forms the &#34;basic building-block&#34; of the trellises employed herein can be replaced with other trellises, and the trellises of the various refinements do not have to be the same as the trellis of the first (primary) encoded representation of the input sequence, or the same as each other. Also, although the above addresses trellis coded quantization (TCQ) using scalar levels, that can be generalized to vectors (TCVQ), to entropy-coded TCQ, and to entropy-coded TCVQ. The generalized class that includes TCQ, TCVQ, entropy-coded TCQ, and entropy-coded TCVQ is termed herein GTCQ.