Proceedings
`
`INTERNATIONAL CONFERENCE ON
`IMAGE PROCESSING
`
`October 23 — 26, 1995
`
`Washington, DC.
`
`Sponsored by
`
`The IEEE Signal Processing Society
`
`VO1ume Iiof 111
`
`IEEE Computer Society Press
`
`Los Alamitos, California
`
`Washington
`
`0
`
`Brussels
`
`o
`
`Tokyo
`
`RPX Exhibit 1123
`
`RPX Exhibit 1123
`RPX v. DAE
`
`RPX V. DAE
`
`

`
`
`
`V
`
`0
`
`
`
`IEEE Computer Society Press
`10662 Los Vaqueros Circle
`P.O. Box 3014
`
`Los Alamitos, CA 90720-1264
`
`Copyright © 1995 by The Institute of Electrical and Electronics Engineers, Inc.
`All rights reserved.
`
`Copyright and Reprint Permissions: Abstracting is permitted with credit to the source. Libraries may
`photocopy beyond the limits of US copyright law, for private use of patrons, those articles in this volume that
`carry a code at the bottom of the first page, provided that the per-copy fee indicated in the code is paid
`through the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923.
`
`Other copying, reprint, or republication requests should be addressed to: IEEE Copyrights Manager, IEEE
`Service Center, 445 Hoes Lane, P.O. Box 1331, Piscataway, NJ 08855-1331.
`
`The papers in this book comprise the proceedings of the meeting mentioned on the cover and title page. They
`reflect the authors’ opinions and,
`in the interests of timely dissemination, are published as presented and
`without change. Their inclusion in this publication does not necessarily constitute endorsement by the
`editors, the IEEE Computer Society Press, or the Institute ofElectrical and Electronics Engineers, Inc.
`
`
`
`95CB358l9
`330% temper
`ienftboundl
`€§8fi”73i0~9
`803r3i22r2 tceeehoundi
`“R03“31?3*Q {microfiche}
`8fl3r2749»7 {fW~Rmw)
`M
`23
`(
`3}
`N.
`"
`
`
`E
`
`IEEE Computer Society Press
`Customer Service Center
`10662 Los Vaqueros Circle
`P.O. Box 3014
`Los Alamitos, CA 90720-1264
`Tel: +1-714-821-8380
`Fax: +1-714-821-4641
`Email: cs.books@computer.org
`
`IEEE Service Center
`445 Hoes Lane
`P.O. Box 1331
`Piscataway, NJ 08855-1331
`Tel: +1-908-981-1393
`Fax: +1-908-981-9667
`mis.custserv@computenorg
`
`IEEE Computer Society
`13, Avenue de1’Aqui1on
`B-1200 Brussels
`BELGIUM
`Tel: +32-2-770-2198
`Fax: +32-2-770-8505
`euro.ofc@computer.org
`
`IEEE Computer Society
`Ooshima Building
`2-19-1 Minami-Aoyama
`Minato-ku, Tokyo 107
`JAPAN
`Tel: +81-3-3408-3118
`Fax: +81-3-3408-3553
`tokyo.ofc@computer.org
`
`Editorial production by Bob Werner
`Cover design by Alex Torres
`Cover art production by Joe Daigle/Studio Productions
`Printed in the United States of America by VictorGraphics, Inc.
`
`@ The Institute of Electrical and Electronics Engineers, Inc.
`
`

`
`This material may be protected by Copyright law (Title 17 U.S. Code)
`
`

`
`curve. This pruning process is fundamentally an interaction
`between the source and channel coding algorithms, i.e., a
`method of joint source/channel coding.
`In its simplest form, a video source transmits the layers
`on their respective multicast addresses without any explicit
`feedback from the receivers.
`If no -receivers tune in to
`the transmission, the multicast routing protocol prunes the
`transmission all the way back to the source’s sub-network.
`When a receiver subscribes to one or more layers, the net-
`work allows the corresponding multicast groups to flow along
`the branches of the distribution tree to that receiver. No
`explicit signalling is required to tell the network where or
`how to filter flows.
`'
`This simple mechanism, which is already deployed (to
`some extent) in the Internet, provides the necessary primi-
`tives to implement our receiver-based congestion avoidance
`scheme. Assume a receiver has subscribed to N layers of a
`transmission. The adaptation algorithm is as follows:
`
`0 On congestion, drop layer N.
`
`0 When capacity is available, add layer N + 1.
`
`Congestion can be inferred through packet loss (e.g., us-
`ing sequence numbers) or conveyed directly from routers to
`end-systems through explicit congestion notification. On
`the other hand, inferring spare capacity is more difficult.
`One approach is to probe for available bandwidth by sp on-
`taneously adding a layer.
`If congestion results, the layer
`will be quickly dropped. By employing conservative prob-
`ing and aggressive backoff strategies and by using relatively
`long time constants, we believe we can produce a stable
`system.
`As an optimization, receivers generate low rate feedback
`messages to the source that indicate the bandwidth utilized
`to each destination. This receiver—feedback is carried out in
`a scalable fashion using RTP [10].
`If the source utilizes
`an embedded compression algorithm, then it can use the
`receiver feedback to adjust the allocation of rate to the dif-
`ferent layers of the multicast distribution. For example, a
`source might discover that some layers are not in use and
`thereby avoid coding and transmitting them, or it might
`discover that all receivers are connected at high bandwidth
`and can therefore collapse the layers into a single, high qual-
`ity stream.
`The success of our proposed multicast video transport
`system depends strongly on the eflicacy of the underlying
`video codec, which must be designed to match the con-
`straints of the layered transport system and the delay and
`loss behavior of the Internet. Since our design is motivated
`heavily by the goal of timely deployment in the Internet,
`it must be easily distributed and operate within the con-
`straints of the existing technology base. Thus, it must be
`feasible to operate the codec in software on a general pur-
`pose workstation in real-time.
`
`3. CURRENT INTERNET VIDEO CODECS
`
`In designing our layered codec, we leveraged of current ex-
`perience in the design of video transmission systems for the
`Internet. The two predominant applications are the IN-
`RIA Video Conferencing system (£225) [13] and the Network
`Video (no) [5] tool from Xerox PARC. The former is based
`
`on a software-only H.261 codec, while the latter utilizes a
`custom compression scheme.
`One early outcome of the deployment of these video
`tools was that the user community preferred the custom
`m1 compression scheme, even though the compression per-
`formance of H.261 is much higher. The reason is twofold.
`First, the nv compression algorithm does not code image
`differences, while the H.261 codec in ins codes the majority
`of the block updates as differences. Consequently, the m)
`coder is more robust to packet loss since the resulting errors
`are relatively short-lived. Second, the no coder runs fast. It
`utilizes a simple compression scheme based on run-length
`encoded Haar transform coefficients. This low complexity
`results in higher perceived quality because the system rarely
`bottlenecks in the compression process.
`More recently, the advantages of standards compliance
`and interoperability of H.261 were combined with nv’s ro-
`bustness in an H.261 coder implemented (by one of us) in
`the UCB/LBL Video Conferencing tool, via
`The result
`is a scheme in which blocks are conditionally replenished, as
`in nu, but the blocks are coded using H.261. By employing
`a very restricted subset of H.261 (intramode block updates
`only), we implemented the robust coding style of no using
`an H.261 compliant syntax. Moreover, the computational
`requirements were substantially reduced by eliminating mo-
`tion estimation. Even with this sacrifice, the Intra-H.261
`
`coder typically outperforms the m1 coder by 6 to 7dB.
`
`4. A LAYERED CODEC
`
`We now turn to a discussion of our prototype layered coding
`scheme. While high-quality layered compression schemes
`have been proposed, these systems focus on optimizing com-
`pression performance without placing tight constraints on
`complexity. Our goal is not to design a codec that outper-
`forms all existing schemes, but rather one that can be imple-
`mented to run in real—time on standard workstations, and
`at the same time, perform “adequately”. In the short term,
`we must make tradeoffs in complexity for viable operation,
`while in the long term, we can develop more sophisticated
`algorithms to track processor performance advances since
`the codec will be software—based and easily re-deployed.
`(1)
`The four key design constraints for the codec are:
`robustness to packet loss, (2) low computational complexity,
`(3) compute scalability, and (4) a layered representation.
`Robustness. One technique for providing high robust-
`ness to loss is to avoid the interframe prediction loop by
`using intraframe coding as in “Motion JPEG”. However,
`this results in poor compression performance. Our hybrid
`approach is to employ the block—based conditional replen-
`ishment scheme used in the existing video tools. Here, block
`updates are intracoded, while blocks whose difference sig-
`nal is below some threshold are suppressed entirely. This
`results in a packet stream where data is independent of the
`past. In particular, it is independent of past losses.
`To avoid persistent errors, a background process scans
`the entire image refreshing blocks at some configurable (low)
`rate. For the video sources with stationary backgrounds
`(which is common in current Internet transmissions), per-
`sistent errors are fairly uncommon. Since loss (usually) is
`associated with a non-stationary area of the image, it is
`
`

`
`subband Domain
`
`Pixel Domain
`
`
`
`Figure 1: Relationship between subband coefficients and
`pixel blocks.
`
`likely restored via conditional replenishment (before the re-
`fresh process updates it). Thus the artifact is (usually)
`absolved immediately.
`Low computational complexity. Because the codec
`must operate in software,
`it must exhibit low computa-
`tional complexity. Fortunately, the robustness constraints
`imposed above reduce the computational requirements sub-
`stantially. Conditional replenishment can be carried out in
`the pixel domain, so very early in the coding process, com-
`putational load is shed by deciding not to code a block. Ad-
`ditionally, the elimination of interframe prediction means
`that expensive motion searches are not performed. A sim-
`ilar approach has been taken in [15], where blocks are in-
`tracoded using an efficient table driven approach based on
`hierarchical vector quantization.
`Compute Scalability. In the heterogeneous environ-
`ment like the Internet, end systems will have diverse com-
`putational resources. Users With less capable end systems
`should still be able to decode a transmission. With the
`layered scheme presented here, an end system can adapt
`to local computational resource availability in exactly the
`same way it adapts to network resource availability. When
`the decoder becomes computation bound, it can drop layers
`to reduce load. Likewise, an encoder can code fewer layers
`under load (albeit at the expense of all the receivers).
`Layered Representation. While a block-based con-
`ditional replenishment scheme is attractive because it re-
`duces computational overhead and results in a robust trans-
`mission, it is at odds with a layered subband coding scheme.
`Traditional subband coding algorithms operate on entire
`images rather than individual blocks. To resolve this mis-
`match, we can treat each conditionally replenished block as
`an independent image and apply an existing 2D subband
`coding scheme to each block. However, this produces block-
`ing artifacts which are amplified by the signal extension
`techniques used to attain critically subsampled decomposi-
`tions.
`
`Instead, we take an alternate approach where we re-
`plenish subband coefficients instead of pixel blocks. Each
`subband coefficient represents the scale and location of a
`wavelet basis vector in the original image. Thus, we can
`relate each coefficient with its spatial location in the im-
`age, as illustrated in Figure 1. We still employ pixel—based
`conditional replenishment, but instead of coding the block
`directly, we use it to identify the subband coeflicients that
`need to be replenished.
`
`Unfortunately, recursive iteration of the analysis filters
`results in coarse scale wavelet basis functions with large
`regions of support.
`In other words, spatially local scene
`changes can affect a large number of wavelet coefficients.
`Moreover, we observed a phase inversion effect where large
`numbers of coefficients would change sign from frame to
`frame with very little scene activity. Even with relatively
`short filters (e.g., four taps), these effects were prohibitive.
`On the other hand, the two tap Haar basis does not suffer
`from these effects at all, since the basis function of one
`image block do not overlap with those of another (and the
`Haar is the only such basis). That is, an N x N pixel block
`is in exact correspondence with N2 coefficients from the
`subband decomposition (as shown in the figure).
`However, a marked disadvantage of the Haar basis is
`that quantization of its square-wave prototype functions
`produces blocking artifacts. Our (partial) solution to this
`problem is to use a hybrid approach, where the first stage
`(or two) of the subband analysis is carried out using a
`longer filter while the remaining stages are carried out us-
`ing the Haar filter. As a result, the blocking artifacts of
`the Haar decomposition are smoothed out by the low-pass
`reconstruction filters. Finally, while the longer first stage
`filter produces some amount of block overlap, the effects are
`minimized by not allowing the filter to iterate.
`The Prototype. Our prototype coder can be decom-
`posed into four stages:
`
`>'«=-LoLo+—A\_,~/\_A./
`
`conditional replenishment
`subband analysis
`scanning set determination
`bit-plane entropy coding
`
`First, we determine the blocks to be replenished by com-
`paring the current frame with a reference frame of trans-
`mitted blocks. Then, each block is analyzed with a sub-
`band decomposition. The first stage is the biorthogonal
`filter pair, Ho(z) = -0.25 + 0.752 -1- 0.7522 — 0.2523 and
`I-11(2) = 0.25 + 0.75z — 0.7522 — 0.25z3, While the remain-
`ing stages use Haar filters. Note that both the Haar and
`biorthogonal filters can be carried out very efficiently using
`fixed point shifts, sums, and differences. Because the filters
`are cheap, the bottleneck becomes memory accesses. Hence,
`we minimize memory traffic by storing each coefficient in a
`single byte by retaining only the 8 most significant bits.
`We then compute coefficient scanning sets using the
`well-known quadtree interpretation of the subband COeH'l—
`cients [12]. For each coefficient, we determine the set of bit
`positions such that at least one successor in the quadtree
`has a non-zero value in the given bit position. These sets
`can be computed efficiently in a single bottom—up traversal
`of the subbands, using only simple bit-wise operations.
`Finally, we entropy code the bit—planes using a depth-
`first traversal of the coefficient quadtrees. Groups of bit-
`planes are allocated to layers, and all of the layers are
`encoded in parallel. During the scan, we retain a bit vector
`of active bit positions which is updated using the scanning
`sets from step 3. When we find that a. bit position has no
`children, we remove it from the active set, effectively ter-
`minating the scan at that position. For each layer of each
`coefficient, we produce a Huffman code using a table lookup
`
`27
`
`

`
`[8]
`
`[9]
`
`[19]
`
`[7] JAcoBsoN, V., AND MCCANNE, S. V2‘sualAudi'o Tool.
`Lawrence Berkeley Laboratory. Software available via
`ftp://ftp.ee.lbl.gov/conferencing/vat.
`MCCANNE, S., AND JAcoBsoN, V. VIC: video con-
`ference. Lawrence Berkeley Laboratory and Univer-
`sity of California, Berkeley.
`Software available via
`ftp://ftp.ee.lbl.gov/conferencing/Vic.
`SCHULZRINNE, H. Voice communication across the In-
`ternet: A network voice terminal. Technical Report
`TR 92-50, Dept. of Computer Science, University of
`Massachusetts, Amherst, Massachusetts, July 1992.
`SCHULZRINNE, H., CASNER, S., FREDERICK, R., AND
`JACOBSON, V. RTP: /-1 Transport Protocol for Real-
`Time Applications. Internet Engineering Task Force,
`Audio—Video Transport Working Group, June 1994.
`Internet Draft expires 10/ 1/ 94.
`SHACHAM, N. Multipoint communication by hierar-
`chically encoded data.
`In Proceedings IEEE Infocom
`£92 (1992), ACM.
`SHAPIRO, J. M. Embedded image coding using ze-
`rotrees of wavelet coefficients. IEEE Transactions on
`Signal Processing 41, 12 (Dec. 1993), 3445—3462.
`TURLETTI, T.
`INRIA Video Conferencing System
`(ins).
`Institut National de Recherche en Informa-
`tique et an Automatique.
`Software available Via
`ftp: / / avahi.inria.fr/pub / videoconference.
`TURLETTI, T., AND BOLOT, J.-C.
`Issues with mul-
`ticast Video distribution in heterogeneous packet net-
`works. In Proceedings of the Siasth International Work-
`shop on Packet Video (Portland, OR, Sept. 1994).
`VISHWANATH, M., AND CHOU, P. An efficient al-
`gorithm for hierarchical compression of video.
`IEEE
`International Conference on Image Processing (Nov.
`1994).
`
`[11]
`
`[12]
`
`[13]
`
`based on‘ bits from the active bit vector, the current coef-
`ficient, and the scanning set. A very simple Huffman code
`was designed manually from inspection of the zero-order
`entropy of the symbol stream. While this approach fails
`to exploit symbol correlations that are ‘easily captured with
`adaptive arithmetic coding, it is very cheap to implement,
`requiring only table lookups and fast bit—wise operations.
`The coder prototype as described above has been im-
`plemented in version 2.7 of vie. Our initial performance
`evaluation is promising. Compression performance is ade-
`quate and run-time performance is good. The 512x512 Lena
`image is coded at 33dB of PSNR at 0.5 bits per pixel, and
`the run—time performance of our untuned implementation
`is comparable to that of our highly tuned H.261 codec.
`
`5. CONCLUSION
`
`We have proposed a joint source/channel coding solution
`to the problem of multicast packet video over the Internet.
`Our source coding scheme employs a low complexity, hier-
`archical decomposition based on a Wavelet transform. This
`approach complements the channel coding scheme, which
`is built upon receiver-based adaptation to network conges-
`tion. By constraining our design to operate in real-time on
`standard Workstations and by distributing our implementa-
`tion for use in the Internet remote conferencing community,
`we gain practical design feedback on relatively short time
`scales. Our software-based appraoch allows us to evolve
`the design and explore the tradeoffs between complexity
`and performance, optimizing the design specifically to the
`application at hand (i.e., multicast Internet video).
`
`6. REFERENCES
`
`[1] BOLOT, J.—C., TURLETTI, T., AND WAKEMAN, I. Scal-
`able feedback control for multicast video distribution
`in the Internet. In Proceedings of SIGCOMM ’94 (Uni-
`versity College London, London, U.K., Sept. 1994),
`ACM.
`
`DEERING, S. Host Extensions for IP Multicasting.
`ARPANET Working Group Requests for Comment,
`DDN Network Information Center, SRI International,
`Menlo Park, CA, Aug. 1989. RFC—1112.
`Jan.
`DEERING, S.
`Re:
`hierarchical encoding‘?,
`1993.
`Email message sent
`to the Inter-Domain
`Multicast Routing (IDMR) mailing list, archived in
`ftp:://cs.ucl.ac.uk/darpa/IDMR/idmr-archive.Z.
`DELGROSSI, L., HALSTRICK, C., HEHMANN, D., HER-
`RTWICH, R. G., KRONE, 0., SANDvoss, 3., AND
`VOGT, C. Media scaling for audiovisual communica-
`tion with the Heidelberg transport system.
`In Pro-
`ceedings of ACM Multimedia "93 (Aug. 1993), ACM,
`pp. 99-104.
`Xerox
`(nu).
`Network Video
`FREDERICK, R.
`Palo Alto Research Center.
`Software available via
`
`ftp://ftp.parc.xerox.com/net-research.
`FREDERICK, R. Experiences with real-time software
`Video compression.
`In Proceedings of the Sixth Inter-
`national Workshop on Packet Video (Portland, OR,
`Sept. 1994).
`
`28