`GAUSSIAN CHANNELS
`
`Thomas P. O’Rourke, Robert L. Stevenson, Yih-Fang Huang,
`Lance C. Perez and Daniel J. Costello Jr.
`
`Laboratory for Image and Signal Analysis
`Department of Electrical Enginering
`University of Notre Dame
`Notre Dame, IN 46556 USA
`
`ABSTRACT
`Many image communication systems have constraints on
`bandwidth, power and time which prohibit transmission of
`uncompressed raw image data. Compressed image formats,
`however, are extremely sensitive to bit errors which can
`seriously degrade the quality of the image at the receiver.
`A new list-based iterative trellis decoder is proposed which
`accepts feedback from a post-processor which can detect
`channel errors in the reconstructed image. Experimental
`results are shown which indicate the new decoder provides
`significant improvement over the standard Viterbi decoder.
`
`1. INTRODUCTION
`
`The sensitivity of the compressed image representation to
`bit errors requires application of a channel code before trans-
`mission over noisy channels. To prevent the uncontrolled
`degradation caused by a channel error, an error control-
`ling channel code is applied to the compressed representa-
`tion before transmission. The cost of the additional bits
`for redundancy in the channel code is paid for by an in-
`creased compression ratio which results in additional con-
`trolled quantization error.
`Although the channel code greatly reduces the number
`of errors in the compressed image representation, a single
`error could still produce severe degradation in the quality of
`the received image. The post-processing method for reduc-
`ing the visibility of quantization errors presented in [l, 21
`makes use of the Huber Markov random field (HMRF) im-
`age model. The robust image communication system pro-
`posed here uses this image model to detect errors in the
`compressed image representation and feeds this error infor-
`mation back to the channel decoder for a second pass at
`decoding the channel symbols. After channel errors have
`been corrected, the image is post-processed to reduce the
`visibility of the quantization error. Unlike other algorithms,
`this system coordinates channel error recovery with quanti-
`zation error reduction. A new iterative channel decoder
`accepts error feedback from the now dual-purpose post-
`processor. In Section 2, a more detailed summary of the
`proposed image communication system will be presented.
`This work was supported in part by NASA Lewis Research
`Center under contract NASA-NAG 3-1549.
`
`Experimental results are shown in Section 3 to illustrate
`the concepts involved. The results of simulation experi-
`ments also show the average performance of the proposed
`system for varying noise levels.
`
`2. SYSTEM SUMMARY
`
`A block diagram of the proposed image communication sys-
`tem is shown in Figure 1.
`
`2.1. Transmitter
`The input image z is compressed by the source encoder us-
`ing the JPEG still image compression standard [3]. JPEG’s
`extended sequential mode of operation is used with custom
`quantization tables, optimized Huffman coding tables, and
`restart markers after each row of blocks. The restart mark-
`ers limit the influence of a channel error to a single row of
`blocks. The compressed representation b is encoded for the
`noisy channel using a rate 1/2 convolutional code with con-
`straint length 7 [4]. The bit sequence b* is then transmitted
`over the noisy channel using BPSK modulation.
`
`2.2. Receiver
`An iterative decoder based on a soft decision Viterbi trellis
`decoder interprets the noisy received bit-stream b’. The
`first iteration decodes the standard soft decision trellis to
`obtain the maximum likelihood sequence b given the -re-
`ceived channel symbols. However, it is also known that b is
`a JPEG compressed image representation. Since a correct
`decoding of the JPEG header information is critical to the
`correct reconstruction of the image, the second iteration
`redecodes the section of the trellis containing the JPEG
`header. The header syntax defined by the JPEG standard
`determines the value of many bits in the header and allows
`detection of incorrect header information. The known bits
`reduce the number of paths through the trellis and decrease
`the probability of decoding an incorrect path. This is very
`similar to the pinned state decoder described in [5].
`The third iteration considers the header to be known
`correctly and redecodes sections of the trellis corresponding
`to entropy coded image data which have been signaled by
`the post-processor as possible sites for error events. The
`
`231 9
`
`0-7803-2431 5/95 $4.00 0 1995 IEEE
`
`Sony, Ex. 1026, p.1
`
`
`
`Channel
`Coder
`
`- b
`-
`
`Channel
`Decoder
`
`Modulator
`
`C
`
`1
`
`-
`
`;*
`
`A
`C
`Demodulator -I
`
`’
`
`&-
`
`Source
`Decoder
`
`w. 1
`
`0
`
`Post-
`
`output 2 Processing
`F(.)
`
`Image
`
`Figure 1: Proposed image communication system
`
`success of the third iteration depends on the ability of the
`post-processor to detect error events in the reconstructed
`image. The errors are detected using the Huber-Markov
`random field (HMRF) image model. See [l, 21 for more
`information on the HMRF image model. The HMRF model
`is characterized by a special form of the Gibbs distribution
`P r ( x ) = -exp{--zppr(d:x)}
`1
`1
`x
`Z
`
`where A is a scalar constant that is greater than zero, d,
`is a collection of linear operators and the function p ~ ( . ) is
`given by
`
`C € C
`
`for the exponent term ccCc
`
`This model is used to detect errors in a region of the image
`by estimating the probability of that region. Regions which
`are greatly affected by channel errors will have a large value
`pT(d:x) and the probability
`measure for these regions wdl be very low.
`An error event produces three different types of arti-
`facts in the reconstructed image. A missed End-of-Block
`code will cause an incorrect number of blocks for a partic-
`ular row. While an incorrect number of blocks indicates
`an error has occurred, this first type of error does not pro-
`vide information on where in the row the error occurred.
`Second, an error in the DC term will propagate until the
`next restart marker at the end of the row. This error can
`be detected by calculating the probability from the image
`model for the boundary area between the current row and
`the previous row. The third type of error occurs in the AC
`coefficients and often causes a single 8 x 8 block to differ
`greatly from the blocks expected by the image model. This
`error is detected by calculating the image model on each
`8 x 8 block and is most easily detected when large high fre-
`quency components are present. This third type of error is
`most useful since the location of the error within the row
`can be calculated. The first and last bits of the row are
`indicated by restart markers. The region of doubt is cal-
`culated as 3 ~ 1 0 % of the bits in the row and is centered at
`the estimated position of the low-probability block in the
`bit-stream. Since error events from the channel decoder
`can produce a burst of errors, a combination of these three
`types of artifacts are often found together.
`
`Figure 2: Original airport image, 256 x 256.
`
`Information about possible error locations is fed back to
`the trellis decoder for reconsideration. Boundaries between
`rows and individual blocks which have probabilities below
`a particular error detection threshold are considered possi-
`ble error regions and the corresponding sections of the bit-
`stream are marked. To prevent false alarms, the locations of
`the three 8 x 8 image blocks with the lowest probability are
`given to the decoder a5 side information. Additionally, the
`error detection threshold which is calculated for the partic-
`ular image is also given to the decoder as side information.
`This small amount of side information can be included in
`the header with additional redundancy for error protection.
`The Viterbi decoder makes a branch decision at each
`state to select the incoming path with the lowest weight.
`When the post-processor questions the decoding of the trel-
`lis, the confidence with which each branch decision is made
`is entered into a list for each state along the most likely path
`in the region of doubt. This list is sorted with the least
`confident decision at the top. The branch decision with
`
`2320
`
`Sony, Ex. 1026, p.2
`
`
`
`Figure 3: Airport image compressed by JPEG to 1.00 bpp,
`no errors.
`
`Figure 4: Example of quantization table error, after first
`iteration, Channel SNR 3.60 dB.
`
`least confidence is overturned and the new path through
`the trellis is decoded, uncompressed, and sent to the post-
`processor. The process continues overturning branch deci-
`sions in the sorted list until the post-processor does not sig-
`nal an error in this section or the end of the list is reached.
`Only one branch decision is overturned at a time since it
`is assumed the region of doubt contains only a single error
`event. To prevent erroneous redecoding due to false alarms
`signaled by the post-processor, the length of the list is lim-
`ited to contain only branch decisions which were made with
`confidence less than a particular threshold value.
`
`3. RESULTS
`
`Experiments were run using the airport image shown in
`Figure 2. This image was compressed to 1.00 bpp, see Fig-
`ure 3. Image SNR is used here to measure image quality.
`Although subjective image evaluation is more meaningful,
`an objective quality measure was needed to illustrate per-
`formance averaged over several trials. The compression re-
`duces the image SNR to 23.29 dB. Channel SNR (EP/No)
`is expressed in dB where Ep is the energy per pixel. Since
`the compressed image has 1.00 bpp, this is equal to the
`more common Eb/No where Eb is the energy per informa-
`tion bit. Using EP/No will allow comparison of systems
`with different compression ratios.
`The importance of correct decoding of the image header
`is shown in Figure 4. An error in the quantization table
`after standard Viterbi decoding has severely degraded the
`image (SNR 15.46 dB). This error is corrected in the second
`iteration. The resulting image (SNR 23.26 dB) contains
`only one small error which is not very noticeable and not
`detected in the third iteration.
`Since the image header consists of a relatively small
`
`number of bits, most of the error events appear in the larger
`entropy coded image body. The features which make an
`error highly visible can be seen in Figure 5 which shows
`an example with two error events after the first iteration
`(SNR 19.18 dB). The effect of each channel error is limited
`to a single row by the restart markers. The first error event
`caused an extra block to be inserted shifting the row to the
`right. In the second error event, a missing End-of-Block
`code caused the next block to be treated as high frequency
`information which shifted the remainder of the row to the
`left. A DC error is also propagated through the rest of both
`rows. Both of these error events are corrected in the third
`iteration resulting in an image identical to the error free
`image shown in Figure 3. The quantization error reduction
`by the post-processor is not shown here.
`While the above examples show very good error cor-
`rection, the actual performance will vary depending on the
`particular realization of the noise. Different noise sequences
`of equal power can have very different effects on the recon-
`structed images. Figure 6 shows the average performance
`of the system under consideration. 600 trials were con-
`ducted for each of the nine channel SNR levels. As ex-
`pected, the image SNR increases as the channel SNR in-
`creases. The quantization noise due to compression lim-
`its the performance at high channel SNR. Performance af-
`ter standard Viterbi decoding, corresponding to the first
`iteration, is shown with the solid line. The dotted line
`shows performance after the second iteration has corrected
`header errors. The dashed line shows performance after the
`third iteration has corrected errors in the image body. Im-
`ages which are severely degraded by header errors improve
`tremendously when the error in the header is corrected.
`Although more images have errors in the image body, the
`degradations which are corrected are less severe.
`
`2321
`
`Sony, Ex. 1026, p.3
`
`
`
`’ i s
`
`317
`
`318
`
`I
`
`I
`4.2
`4.1
`319
`4
`Channel SNR @/NO (dB)
`
`I
`
`I
`4.3
`
`I
`
`4.4
`
`.5
`
`Figure 6: Image SNR vs. Channel SNR
`
`4. CONCLUSION
`
`The new iterative trellis decoder is able to overcome chan-
`nel noise using knowledge of compressed image syntax and
`the HMRF image model. The results are scalable to differ-
`ent degrees of quantization and can be extended to other
`compression techniques. Additional error protection is pos-
`sible by using a longer constraint convolutional code at the
`expense of additional receiver complexity.
`
`5. REFERENCES
`111 R. L. Stevenson, “Reduction of coding artifacts in
`transform image coding,” in Proc. ICASSP-93, (Min-
`neapolis, MN), pp. V:401-404, Apr. 1993.
`[a] T. P. O’Rourke and R. L. Stevenson, “Improved im-
`age decompression for reduced transform coding arti-
`facts,” in Proc. SPIE Image and Video Processing 11,
`vol. 2182, (San Jose, CA, Feb. 7-9, 1994), pp. 90-101,
`1994.
`[3] W. B. Pennebaker and J. L. Mitchell, JPEG: Still Im-
`age Data Compression Standard. New York Van Nos-
`trand Reinhold, 1993.
`[4] S. Lin and D. J. Costello, Jr., Error Control Coding:
`Fundamentals and Applications, Englewood CliEs, NJ:
`Prentice-Hall, 1983.
`151 0. Collins and M. Hizlan, “Determinate State Con-
`volutional Codes,” IEEE Trans. on Communications,
`vol. 41, pp. 1785-1794, Dec. 1993.
`
`Figure 5: Example with 2 error events in entropy coded
`data, after first iteration, Channel SNR 3.60 dB.
`
`2322
`
`Sony, Ex. 1026, p.4