`NOISY CHANNELS
`
`Thomas P. O’Rourke, Robert L. Stevenson, Yh-Fang Huang and Daniel J. Costello Jr.
`
`Laboratory for Image and Signal Analysis
`Department of Electrical Enginering
`University of Notre Dame
`Notre Dame, IN 46556 USA
`0 ’Rourlre. 4Qnd. edu, Stevenson. 1 @nd. edu
`
`A B S T R A C T
`This paper presents an image communication system
`with improved decoding of compressed image informa-
`tion. A convolutional code protects the compressed
`image information from channel noise while a Reed-
`Solomon outer code gives additional protection to the
`critical image header information. A post-processor de-
`tects uncorrected channel errors in the reconstructed
`image and feeds error location information to a list-
`based iterative trellis decoder. This list-based decoder
`provides significant improvement in image quality. Ex-
`perimental results are given for varying channel SNR
`and for varying bit rate.
`
`1. I N T R O D U C T I O N
`
`Images must be compressed for many applications due
`to limitations on available bandwidth. Since compressed
`image representations are very sensitive to bit errors,
`the effects of channel errors can be quite severe when
`the compressed image is transmitted over a noisy chan-
`nel. The redundancy added by a channel code pro-
`tects the compressed image information from channel
`noise. In addition to increased system complexity, this
`redundancy is purchased either by increased quantiza-
`tion noise due to higher compression requirements or
`by decreased channel symbol SNR due t o constant im-
`age power constraints. When transmitting over noisy
`channels, the price of redundancy must be paid to re-
`ceive the image information.
`A similar robust image communication system with
`a list-based trellis decoder was proposed in [l]. A con-
`volutional code is applied to the compressed image rep-
`resentation before transmission over the channel. In
`-
`This work was supported i n p a r t by Lockheed Martin Cor-
`poration and by NASA Lewis Research Center under contract
`NASA-NAG 3-1549.
`
`that system, the decoder uses header syntax informa-
`tion t o correct errors in the header. A post-processor
`which can detect errors in the decompressed image sends
`feedback to the list-based trellis decoder. Although this
`system [l] was found capable of locating and correct-
`ing errors in the decompressed image, the experimental
`performance was significantly degraded by uncorrected
`channel errors in the image header information.
`The system proposed in this paper uses a Reed-
`Solomon (RS) outer code to protect the header from
`channel errors. With the correct decoding of the im-
`age header, the benefits of the list-based trellis decoder
`from [l] are more clearly evident. The proposed robust
`image communication system is described more fully
`in section 2. Results given in section 3 indicate sig-
`nificant improvement in image quality due both t o the
`improved header decoding and to the list-based trellis
`decoder.
`
`2. S Y S T E M S U M M A R Y
`
`2.1. Transmitter
`The input image i s compressed by the source encoder
`using the JPEG still image compression standard [a].
`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 markers limit the influence of a
`channel error to a single row of blocks.
`Since a correct decoding of the JPEG header in-
`formation is critical to the correct decompression of
`the image, a block code is used to provide the header
`with additional protection from channel noise. The
`header is coded into 2 RS codewords using 2 different
`RS codes. The codes (255, R I ) and (255, kz) are chosen
`so that k l + Ra will accommodate the largest antici-
`pated header. The JPEG header length is expanded to
`
`0-8186-7310-9/95 $4.00 @ 1995 IEEE
`
`65
`
`IPR2016-01179 Ex. 2013
`Page 1 of 4
`
`
`
`kl + k2 with OxFP fill bytes. The coded header is then
`interleaved into the entropy coded image body to pro-
`vide the new compressed representation. The number
`of additional bits required for this redundant informa-
`tion is small compared to the total number of bits used
`by the compressed representation. A coded header was
`also interleaved into the image body in [3]. Unequal
`strength RS codes are used here to take advantage of
`the iterative decoding at the receiver.
`The compressed representation is encoded for the
`noisy channel using a rate l / 2 convolutional code with
`constraint length 7 [4]. This bit-stream is then trans-
`mitted 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.
`The first iteration decodes the standard soft decision
`trellis to obtain the maximum likelihood compressed
`representation given the received channel symbols. Fol-
`lowing [5], the strongest RS codeword is extracted from
`the compressed representation and corrected
`using
`Berlekamp’s algorithm [4]. After this codeword is cor-
`rected] it is known that some of the states in the trellis
`are not possible and some of the state transitions are
`determined or “pinned.” The corrected code word is
`used to pin transitions in the trellis. A second itera-
`tion re-decodes the trellis with the pinned transitions.
`Similarly, the next RS codeword is corrected; the corre-
`sponding transitions are pinned, and the third iteration
`re-decodes the trellis if necessary.
`After the third iteration, the header is assumed to
`be known correctly. The image is decompressed and
`sent to the post-processor. For the fourth iteration,
`the post-processor feeds information on the location
`of possible channels errors back to the list-based trellis
`decoder for reconsideration. The trellis decoder creates
`a list of possible paths through the trellis. The decoder
`returns the next most likely path from the list until the
`post-processor accepts the decompressed image.
`The success of the fourth iteration depends on the
`ability of the source decoder to provide a reconstructed
`image to the post-processor and on the ability of the
`post-processor to detect error events in the reconstructed
`image. The correct decoding of the JPEG header en-
`ables the successful operation of the source decoder.
`The detection of error events by the post-processor is
`described below in section 2.2.1 and the operation of
`list-based trellis decoder is described in section 2.2.2.
`More details can be found in [l].
`
`2.2.1. Error detectaon b y post-processor
`Channel errors may cause the entropy coder to lose syn-
`chronization and an incorrect number of 8 x 8 blocks
`may be decoded for a particular row. This type of error
`is easily detected by counting the number of decom-
`pressed blocks. Channel errors also leave highly visible
`artifacts in the reconstructed image. An image model
`provides a measure of how closely an image matches
`prior expectations for that image. These highly visi-
`ble artifacts deviate greatly from what is expected to
`be found in an image. The errors are detected using
`the Huber-Markov random field (HMRF) image model.
`The HMRF model is characterized by a special form of
`the Gibbs distribution
`1
`1
`z
`P r ( x ) = - e x p { - - x p ~ ( d L x ) }
`C€C
`where X is a scalar constant that is greater than zero, x
`is the image, d, is a collection of linear operators and
`the function p ~ ( . ) is given by
`
`This model is used to detect errors in a region of the
`image by estimating the probability of that region. Re-
`gions which are greatly affected by channel errors will
`have a large value for the exponent term Cp~(d:x)
`and the probability measure for these regions will be
`very low. See [6, 71 for more information on the HMRF
`image model.
`
`2.2.2. Lzst-based trellzs decoder
`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
`trellis, the confidence with which each branch decision
`was 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 least confidence is overturned and
`the new path through the trellis is decoded, uncom-
`pressed, and sent to the post-processor. The process
`continues overturning branch decisions in the sorted
`list until the post-processor does not signal 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 limited to contain only branch decisions
`which were made with confidence less than a particular
`threshold value.
`
`66
`
`IPR2016-01179 Ex. 2013
`Page 2 of 4
`
`
`
`0.974 1.012 I 1.048 1.106 I 1.198
`1.004 1.045 I 1.083 1.145 I 1.243
`
`I
`1
`
`JPEG
`w/ RS
`
`3. RESULTS
`
`A 256 x 256 image of an airport was used as a test
`image. The test image was compressed to the bit rates
`given in the first row of Table 1. The header was then
`encoded using RS codes with IC1 = 171 and k2 = 107
`which expanded the compressed representation to the
`bit rates given in the second row of Table 1. The rate
`1/2 convolutional code then doubled the bit rate. The
`channel symbols were sent over an additive Gaussian
`noise channel. The channel SNR is measured as 10 *
`log,o(Ep/No) where Ep is energy per pixel.
`Keeping the bit rate fixed at 1.045 bpp, the chan-
`nel SNR was varied from 3.3157 dB to 3.9157 dB. The
`results after 600 trials at each channel SNR value are
`shown in Figure 1. The average image SNR is calcu-
`lated by
`
`Image SNRave = 10 * loglo( -)
`S a v e
`Nave
`where Sa,, is average signal power and Nave is average
`noise power. The average image SNR is relative to
`the original unquantized image. Although subjective
`quality measurement is much more useful than image
`SNR, an objective measure is necessary to show results
`for a large number of trials. The dashed line at the
`top of the graph represents the image quality for the
`quantized image with a noiseless channel.
`It can be seen in Figure 1 that large improvements
`are achieved by the second and third iterations. This is
`expected since these iterations correct header informa-
`tion which is critical to successful image reconstruction.
`An error in the image header can affect the entire im-
`age. With the restart markers after each row of image
`data, the effect of an error in the image body is limited
`to a single row. The fourth iteration which uses the
`list-based decoder also shows significant improvement.
`The change in average image SNR is smaller since the
`list-based decoder corrects errors which are limited to a
`single row but are still subjectively significant. In chan-
`nel SNR ranges where the curves are relatively flat, a
`large increase in signal power is required to give an
`equivalent increase in image quality.
`Without channel noise, the image SNR increases
`as the bit rate for the compressed image is increased.
`This is shown by the dashed line in Figure 2. Keeping
`the energy per pixel constant , however, an increased
`bit rate means less energy is available for each chan-
`
`nel symbol leading to increased probability of errors.
`This effect can be seen in Figure 2 which shows the re-
`sults after 600 trials at each bit rate. The channel SNR
`was fixed at 3.7157 dB. As the bit rate is reduced, the
`probability of error is decreased and the image quality
`is generally improved. This improvement is less signif-
`icant close to the ceiling imposed by the quantization
`noise. Quantization noise increases with decreased bit
`rate and would become a limiting factor at lower bit
`rates.
`
`4. CONCLUSION
`
`The list-based trellis decoder with error detection by
`the post-processor provides significant improvement in
`image quality. The RS outer code dramatically re-
`duces the probability of uncorrected errors in the crit-
`ical image header. Increased quantization noise can be
`traded for increased average image quality. Although
`the JPEG standard was used for image source coding
`in the system discussed here, other source coders can
`be used with the list-based trellis decoder as well.
`
`5. REFERENCES
`
`[1] T. P. O’Rourke, R. L. Stevenson, Y.-F. Huang,
`L. C. Perez and D. J. Costello Jr., “Robust trans-
`mission of compressed images over noisy Gaussian
`channels,” in Proc. ICASSP-95, vol. 4, (Detroit,
`MI), pp. 2319-2322, 1995.
`[a] W. B. Pennebaker and J. L. Mitchell, JPEG: Still
`Image Data Compresszon Standard. New York:
`Van Nostrand Reinhold, 1993.
`[3] D. W. Redmill and N. G. Kingsbury, “Still im-
`age coding for noisy channels,” in Proc. ICIP-94,
`(Austin, TX), pp. I:95-99, Nov. 1994.
`[4] S. Lin and D. J . Costello, Jr., Error Control Cod-
`zng: Fundamentals and Applications, Englewood
`Cliffs, NJ: Prentice-Hall, 1983.
`[5] 0. Collins and M. Hizlan, “Determinate State
`Convolutional Codes,” IEEE Trans. on Commu-
`nzcatzons, vol. 41, pp. 1785-1794, Dec. 1993.
`[6] R. L. Stevenson, “Reduction of coding artifacts
`in transform image coding,” in Proc. ICASSP-93,
`(Minneapolis, MN), pp. V:401-404, Apr. 1993.
`[7] T. P. O’Rourke and R. L. Stevenson, “Improved
`image decompression for reduced transform coding
`artifacts,” Proc. IS&T/SPIE Symposaum o n Elec-
`tronzc Imagzng an Sczence and Technology (San
`Jose, CA), 1994.
`
`67
`
`IPR2016-01179 Ex. 2013
`Page 3 of 4
`
`
`
`-
`18 is
`.U 2 1 6 -
`z
`0
`$14-
`E -
`1 2 - , ,
`' . .
`
`10-
`
`8 -
`
`solid = list-based decoder
`
`. . . . . . . . . . . .
`. . . . . . . . . . .
`. . - .
`
`. . . . . .
`
`. . . .
`
`. . . .
`
`, . . '
`
`, . .
`
`, , , , ,
`
`dash-dot = 2nd header correction
`
`,f , ,
`, ,
`
`dotted = 1st header correction
`,x- - - - - --x
`, ,
`, ,
`
`, x M
`,
`, ,
`
`dashed X = Viterbi decoder
`
`x'
`
`.
`-
`, c
`
`I
`3.4
`
`I
`
`3.5
`
`I
`I
`3.7
`3.6
`Channel SNR (dB Ep/No)
`Figure 1: Image SNR vs. Channel SNR
`
`25
`
`2c
`
`-
`Lg 15
`
`v
`[r
`Z cn
`a, cn
`E I C -
`
`E
`
`C
`
`. . . . . .
`
`. . .
`
`x . . .
`.
`x ,
`
`. . .
`
`. . .
`
`, . .
`-x- . . . . . . .
`.
`
`dashed = noiseless channel
`solid = list-based decoder
`dash-dot = 2nd header correction
`dotted = 1 st header correction
`dashed X = Viterbi decoder
`,
`1.15
`1.1
`Bit rate (bpp)
`Figure 2: Image SNR vs. Bit Rate
`
`I
`1.05
`
`I
`
`68
`
`I
`
`3.8
`
`1
`3.9
`
`I
`1.2
`
`1
`
`'5
`
`IPR2016-01179 Ex. 2013
`Page 4 of 4
`
`