`
`ere IEEE TRANSACTIONS ON
`COMMUNICATIONS
`
`JULY 1984
`
`VOLUME COM-32
`
`NUMBER 7
`
`(ISSN 0090-6778)
`
`A PUBLICATION OF THE IEEE COMMUNICATIONS SOCIETY
`
`\\
`[f
`en eee
`Ne
`Ne
`[77
`Hh
`Se4 &
`
`PAPERS
`
`Forthcoming Topics of IEEE Journal on Select
`
`Signal Processing and Communication Electronics
`Noise Reduction in Image Sequences Using Motion-Compensated Temporal Filtering......£. Dubois and
`S. Sabri
`The Effectiveness and Efficiency of Hybrid Transform/DPCM Interframe Image Coding..... W.A. Pearlman
`and P.. Jakatdar
`
`Communication Theory
`On Optimum and Nearly Optimum Data Quantization for Signal Detection..... B. Aazhang and H. V. Poor
`On M-ary DPSK Transmission OverTerrestrial and Satellite Channels..... R. F. Pawula
`Performance of Portable Radio Telephone Using Spread‘Spectrum..... K. Yamada, K. Daikoku, and H. Usui
`
`Computer Communications
`Random Multiple-Access Communication and Group Testing..... T. Berger, N. Mehravari, D. Towsley, and
`J. Wolf
`Synthesis of Communicating Finite State Machines with Guaranteed Progress.....M. G. Gouda and Y.-T. Yu
`
`Data Communication Systems
`Network Design for a Large Class of Teleconferencing Systems..... M. J. Ferguson and L. Mason
`
`Satellite and Space Communication
`Interference Cancellation System for Satellite Communication Earth Station. .... T. Kaitsuka and T. Inoue
`Unique Word Detection in TDMA: Acquisition and Retention.....S. 8. Kamal and R. G. Lyons
`TSI-OQPSK for Multiple Carrier Satellite Systems..... H. Pham Van and K. Feher
`
`CONCISE PAPERS
`
`Signal Processing and Communication Electronics
`Multiplierless Implementations of MF/DTMF Receivers..... R.C. Agarwal, R. Sudhakar, and B. P. Agrawal
`
`CORRESPONDENCE
`
`Communication Theory
`Preemphasis/Deemphasis Effect on the Output SNR of SSB-FM..... E. K. Al-Hussaini and E.M. El-Rabhie
`Decimations of the Frank—Heimiller Sequences..... W. O. Alltop
`A Two-Power-Level Method for Multiple Access Frequency-Hopped Spread-Spectrum Communication
`. aatiJ. J. Metzner
`
`Signal Processing and Communication Electronics
`Hamming Coding of DCT-Compressed Images Over Noisy Channels..... D. R. Comstock and J. D. Gibson
`A One-Stage Look-Ahead Algorithm for Delta Modulators..... N. Scheinberg, E. Feria, J. Barba, and
`D. L. Schilling
`
`Page 1 of 9
`
`GOOGLE EXHIBIT 1007
`
`
`
` Ame
`
`A CENTURY OF ELECTRICAL PROGRESS
`
`IEEE COMMUNICATIONS SOCIETY
`
`IEEE
`
`—~
`
`®
`
`The field of interest of the IEEE Communications Society consists of all telecommunications including telephone, telegraphy, facsimile,
`and point-to-point television, by electromagnetic
`C
`propagation including radio; wire; aerial, underground, coaxial, and submarine cables; waveguides, communication satellites, and|
`asers;1n marine, aeronautical, space and fixed Station services;
`repeaters,
`radio relaying, signal storage, and regeneration; telecommunication error detection and correction; multiplexing and carrier techni
`ques; communication switching systems: data
`communications; and communication theory.
`In addition to. the above, this TRANSACTIONS contains papers pertaining to analog and digital signal processing and modulation, audio and video encoding techniques, the theory and design of
`
`transmitters, receivers, and repeaters for communications via optical and sonic media, the design and analysis of computer communication systems, and the development of communication
`software. Contributions of theory enhancing the understanding of communication systems and techniques are included, as a
`are discussions of the social implications of the development of
`communication technology. All members of the [EEE are eligible for membership in the Society and will receive this TRANS,
`ACTIONS or the IEEE JOURNAL ON SELECTED AREAS IN .
`CoMMUNICATIONS upon paymentof the annual Society membership fee of $15.00. Members may alsoreceive both publ.
`the IBEEat the address below.
`ications upon payment of $21.00 total. For information onjoining, write to
`
`PAUL E. GREEN, JR., Director of Publications
`IBM Res, Cen., Rm. 39218
`Yorktown Heights, NY 10598
`
`A. NETRAVALI, Signal Processing and
`Communication Electronics
`Bell Lab.
`Holmdel, NJ 07733
`Associate Editors
`J. Gipson, Speech Processing
`Telecommun. & Control Syst. Lab.
`Dep. Elec. Eng., Texas A&M Univ.
`College Station, TX 77843
`E. Y. Ho, VLSI in Communications
`American Bell, Rm. 4G304
`Holmdel, NJ 07733
`
`N. F. MAXEMCHUK, Data Communication
`Systems
`Bell Lab., Rm, 7C-219
`Murray Hill, NJ 07974
`Associate Editors
`D.C. Coir, CATV
`Dep. Syst. Comput. Eng., Carleton Univ.
`Ottawa, Ont., Canada K1S 5B6
`S. Pasupatuy
`Dep. Elec. Eng., Univ. Toronto
`Toronto, Ont., Canada MSS 1A4
`S. S. RAPPAPORT
`Dep. Elec. Eng, State Univ. New York
`Stony Brook, NY 11794
`
`A. S. ACAMPORA,Satellite and Space
`Communication
`AT&T Bell Lab., Rm. R219
`Holmdel, NJ 07733
`
`E. G. SaBLe, Communication §witching
`Bell Lab.
`Holmdel, NJ 07733
`Associate Editors
`J.G. Kapper
`Bell-Lab.
`Holmdel, NJ 07733
`D. Viack
`Bell Lab. Rm. 6B-342
`Naperville, IL 60540
`
`TEEE COMMUNICATIONS SOCIETY
`TRANSACTIONSEditorial Board 1984
`J. L. LoCicero, Publications Editor
`J. O. Limr, Editor-in-Chief
`Bell Commun.Res., Inc., Rm. 3D-479
`Dep. Elec. Eng., Illinois Inst. Technol.
`Murray Hill, NJ 07974
`Chicago, IL 60616
`Editors
`
`Computer Communications
`Associate Editors
`M. J. FerGuson, Performance Evaluation
`INRS Telecommun,
`a/s Recherches Bell-Northern Ltd.
`3 Place du Commerce
`Verdun, P.Q., Canada H3E 1H6
`K. KUmmerte, Local Area Networks
`IBM Zurich Res. Lab.
`Saumerstrasse 4, Zurich, Switzerland
`S. LAM, Network Protocols
`Dep, Comput. Sci., Univ. Texas
`Austin, TX 78712
`A. LEON-Garcta, Voice-Daia Systems
`Dep. Elec. Eng., Univ. Toronto
`Toronto, Ont., Canada MSS 1A4
`J. MARK, Wide Area Networks
`Comput. Commun. Network Group
`Uniy. Waterloo
`Waterloo, Ont., Canada N2L 3G1
`P. PaPANTONI-KAzakos, Random Access
`Systems
`Dep. Elec. Eng. Comput. Sci., Box U157
`Univ. Connecticut
`Storrs, CT 06268
`A. SEGALL, Theory
`IBM T. J. Watson Res. Cen.
`Yorktown Heights, NY 10598
`C. A. SUNSHINE, Protocol Specification
`and Validation
`SYTEK,Inc.
`6029 Bristol Pkwy., Suite 210
`Culver City, CA 90230
`F. A. Topaci, Random Access Systems
`Dep. Elec. Eng., Stanford Univ.
`Stanford, CA 94305
`
`
`T. BYRNE, Communications Software
`Bell Lab., Rm. 3C-432A
`Murray Hill, NJ 07974
`
` i
`Communication Terminals
`Bell Lab., Rm. 4F-631
`Holmdel, NJ 07733
`
`J. Lesu, Conimunication Theory
`Jet Propulsion Lab.
`4800 Oak Grove Dr., M/S 238-420
`Pasadena, CA 91103
`Associate Editors
`F. Davipson, Optical Communications
`Dep. Elec. Eng., Johns Hopkins Univ.
`Baltimore, MD 21218
`
`D.D. FaLconer, Digital Communications
`Dep. Syst. Comput. Eng., Carleton Univ.
`Ottawa, Ont., Canada K1S 5B6
`A. Hasist, Image Processing and Pattern
`Recognition
`Aerospace Corp.
`P.O. Box 92957
`Los Angeles, CA 90009
`W. HAGMANN, Synchronization and Phase-
`Locked Loops
`Comsat Lab.
`Clarksburg, MD 20871
`P. McLane, Modulation Theory, Nonlinear
`and Nonstationary Channels
`Dep. Elec. Eng., Queen’s Univ.
`Kingston, Ont., Canada K7L3NG
`W. Stark, Spread Spectrum
`Dep. Elec. Comput. Eng.
`Univ. Michigan
`Ann Arbor, MI 48109
`J. UHRAN, Anulog Communications
`Dep. Elec. Eng., Univ. Notre Dame
`South Bend, IN 46556
`
`S. WILSON, Coding Applications
`Dep. Elec. Eng., Uniy. Virginia
`Charlottesville, VA 22901
`
`J. G. NAULT, Subscriber Loops and
`Services
`Bell Northern Research
`3 Place du Commerce
`Verdun, P.Q., Canada H3E 1H6
`
`D. R. Ucel, Assoc. Publications Editor
`Dep. Elec. Eng., State Univ. New York
`Stony Brook, NY 11794
`
`
`
`K. S. SHANMUGAN, Computer-Aided
`Design of Communication Systems
`Dep. Elec. Eng., Univ. Kansas
`Lawrence, KS 66045
`Associate Editor
`P. BALABAN
`AT&T Bell Lab., Rm. 3E238
`Holmdel, NJ 07733
`
`D. P. CALLAHAN, Transmission Systems
`GTC
`1357 E. 3rd St., Long Beach, CA 90802
`
`P. R. Triscuitta, Fiber Optics
`Bell Lab., Rm, 3C-310
`Holmdel, NJ 07733
` J. C.-Y. HUANG, Radio Communication
`Aydin Corp., Microwave Div.
`75 E. Trimble Rd., San Jose, CA 95131
`
`C. E. Cook, Communication Systems
`Disciplines
`Commun. Div., MITRE Corp.
`Bedford, MA 01730
`
`H. Rupin, Exropean Contributions
`IBM Res. Lab Zurich
`Saumerstrasse 4
`8803 Ruschlikon ZH, Switzerland
`
`T. Osarake, Far Eastern Contributions
`47-5 Nogata-6-chome
`Nakano-ku, Tokyo, Japan, 165
`
`Consultants
`M, R. AARON
`C. ELenowitz. [EEE Production Manager
`
`(Information for Authors, ComSoc Board of Governors, Departments, and Committees appear on Cover LI.)
`THE INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS,INC.
`Officers
`Ricuarp J. Gowen, President
`J. Barry Oakes, Vice President, Educational Activities
`CHARLES A. ELDON, President-Elect
`
`Russevt C. Drew, Vice President, Professional Activities
`Henry L. BACHMAN, Executive Vice President
`Jose B. Cruz, JR., Vice President, Publication Activities
`V. Prasap Kopatt, Secretary
`MerRILL W. Buck.ey, Jr., Vice President, Regional Activities
`Cyrit J. Tunis, Treasurer
`STEPHEN KAHNE, Vice President, Technical Activities
`ALAN F. CULBERTSON, Division Lil Director
`Headquarters Staff
`Eric HERZ, Executive Director and General Manager
`ELwoop K. GANNETT, Deputy General Manager
`Davip L. Staiger, Staff Director, Publishing Services |
`Cnarces P. Stewart, Jr., Staff Director, Administration Services
`’ Director, Field Services
`DONALD L. Suppers, Sta
`Tuomas C. Write, Staff Director, Public Information
`JOHN F. WILHELM, Staff Director, Educational Services
`Publication Department
`Production Managers: ANN H., BurGMEYER, CaroLyne ELENOWITZ, GAIL S. FERENC
`Associate Editor; Pau ¥. OLowacz
`IEEE TRANSactions
`ON COMMUNICATIONSis published monthly
`NY 10017 U.S.A.
`by The Institute of Electrical an
`Responsibility for the
`d Electronics Engineers, Inc. Headquarters: 345 East 47th Street, New York,
`n/Section/Student
`Contents rests upon the authors and not uponthe IEEE,the Society,
`Services): 445 Hoes L,
`or its members. IEEE Service Center(for orders, subscriptions, address changes. Region
`7860. Publishing
`Services-7560, Standards-7960
`ca
`fa
`fe
`quarters 212-705 + extension: Information-7900, General M
`Telex: 236-411
`anager-7910, Controller-7748, Educational SOLMERSs
`> Fechnical Services-7890. IEEE Service Center 201-981-0060, Professional Services: W
`
`fee. Price for
`ashington Office 202-785-0017, NY Telecopier: 212-752-4929.
`EE members$6.00 (first copy only), nonmembe
`
`112.00. Available in Microfiche and microfi
`12.00 per copy. Annualsubscription price: IEEE members, dues plus Society 5
`beyond the
`of
`U.S.
`Private use of
`Im. Copyright and Reprint Permission: Abstra
`limits.of U.S. Copyright law forpri
`cting is permitted with credit to the source. Libraries are permitted to photocony
`through the
`patrons; (1) those post-1977 articles that carry a codeat the bottom ofthefirst page, provided the per-copyfee indicated in the code is paid
`Copyright Clearance Center, 29 Congress St,
`se without
`, Salem, MA 01970;(2) pre-1978 articles without fee. Instructors are permitted to photocopyisolated articles for noncommercial classroom Ut
`fee. For other Copying, reprint, or republicat
`Publishing Services
`ion permission, write to Director,
`The Institute of Electrical and
`Electronics Engineers, Inc. Printed in U.S
`A. Secor
`at IEEE Headquarters. All rights reserved. Copyright © 1984 by
`‘
`445 Hoes Lane,
`Piscataway, NJ 08854.
`nd-class postage paid at New York, NY an
`id at additional mailing offices. Postmaster: Send address changes to IEEE.
`
`THOMAS W. BartLett, Controller
`DONALD CHRISTIANSEN, Editor of Spectrum
`IRVING ENGELSON, Staff Director, Technical Activities
`
`sional Activities
`LEO FANNING, Staff Director, Profes
`ctor, Standards
`SAVA SHERR, Staff Dire
`
`
`
`
`
`
`
`
`Page 2 of 9
`
`Page 2 of 9
`
`
`
`
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-32,NO.7, JULY 1984
`
`745
`
`Ooeee
`a A
`
`On Optimum and Nearly OptimumData Quantization for
`Signal Detection
`>
`%
`Uy
`G, STUDENTMEMBER, IEEE, AND H. VINCENT POOR,sENIORMEMBER,
`IE) Gpig i
`\@&by,-FiIL
`?
`oat?BFF
`meeaa
`Abstract—The application of companding approximation theory to the
`optimally quantizing data in the minimum mean-squared error
`quantization of data for detection of coherentsignals in a noisy environ-
`sense; see also Gersho [11]).
`ment
`is considered. This application is twofold, allowing for greater
`In this paper, we apply the companding approximation
`simplicity in both analysis and design of quantizers for detection systems.
`theory to signal detection problems, First, we use the com-
`Most computational methods for designing optimum (most efficient)
`panding approximation to help in solving Kassam’s system of
`quantizers for signal detection systems are iterative and are extremely
`nonlinear equations for the optimum quantizer parameters
`(see also Bucklew and Gallagher [12]). Then, we present a
`sensitive to initial conditions. Companding approximation theory is used
`here to obtain suitable initial conditions for this problem. Furthermore,
`scheme to design a quantizer which in a sense estimates Kas-
`the companding approximation idea is applied to design suboptimum
`sam’s optimum quantizer using a companding approximation.
`The performance of detection systems using these companding
`quantizers which are nearly as efficient as optimum quantizers when the
`numberoflevels is large. In this design, iteration is not needed to derive the
`quantizers is compared to that of Kassam’s optimum quantizer
`detector. Also, the exact performance of the optimum system
`parameters of the quantizer, and the design procedureis yery simple. In
`is compared to its approximate performance predicted by the
`this paper, we explore this approach numerically and demonstrate its
`effectiveness for designing and analyzing quantizers in detection systems.
`companding model. These issues are explored numerically for
`a wide range of noise distributions, including both Gaussian
`and non-Gaussian cases,
`
`BEHNAAM AAZHAN
`
`BnrGrn
`@
`
`>
`
`I. INTRODUCTION
`
`N recent years there have been several studies of problems
`relating to the quantization of data for use in signal detec-
`tion systems [1]-[6]. These studies include both analytical
`and numerical
`treatment of
`the problem of optimal data
`quantization for the detection of deterministic (coherent)
`signals [1], [2] and purely stochastic signals [5], and analyti-
`cal treatments of quantization within more general signal de-
`tection formulations [3]-[6]. In particular, Kassam [1] has
`considered this problem for the coherent detection case and
`has developed a design technique for this situation based on
`the solution to a system of nonlinear equations in the quan-
`tizer parameters. He showed that quantizers derived in this
`manner have maximum efficacy (ie., are most efficient)
`among all quantizers with a fixed number of output levels.
`lt
`is
`interesting to compare Kassam’s quantizer
`to those
`optimized by a criterion not specifically for signal detection
`purposes; for instance, the minimum-distortion quantizer [7] ,
`which minimizes the mean-squared error between data and its
`quantized version, coincides with the optimum quantizer
`based on Kassam’s detection criterion [1] only for Gauss-
`ian noise,
`In the alternative context of quantizing data for minimum
`distortion, approximations to the minimum-distortion non-
`uniform quantizer which are of practical interest have been
`proposed, Bennett [8] modeled a nonuniform quantizer by a
`compressor, followed by a uniform quantizer and an expander
`(compander), With this companding model, Panter and Dite
`[9] presented a useful approximation to minimum-distortion
`quantizers, Later, Algazi [10] used the companding approxi-
`mation to obtain results on optimal quantizers for a general
`class of error criteria (Algazi estimated distortion due to
`
`Paper approved by the Editor for Communication Theory of the IEEE
`Communications Society for publication after presentation at the Conference
`on Information Sciences and Systems, Johns Hopkins University, Baltimore,
`MD, March 1983. Manuscript received March 22, 1983; revised November
`21, 1983. This work was supported by the Joint Services Electronics Program
`(U.S. Army, Navy, and Air Force) under Contract N00014-79-C-0424.
`The authors are with the Department of Electrical Engineering and the
`Coordinated Science Laboratory, University of Illinois at Urbana-Champaign,
`Urbana, IL 61801.
`
`II. PRELIMINARIES
`The model we consider is based on a standard additive noise
`assumption. In particular, we assume that we have a sequence
`of data samples x = {x;; i = 1, 2, +, n} from a random se-
`quence X = {X;;i = 1, 2, -, n} which can obey one of the
`two possible statistical hypotheses:
`
`Hg: X; = Nj,
`versus
`
`BIE, Bocce ia)
`
`Hy: X;=Nj+0s;, 1=1, 2,--,n
`
`(2.1)
`
`where {N;; 7 = 1, 2, --, n} is an independent, identically dis-
`tributed (ii.d.) zero-mean noise sequence with known com-
`mon univariate probability density and distribution functions
`fand F, respectively. Throughout this work, the noise proba-
`bility density function fis assumed to be symmetric about the
`origin. The parameter 6 is a positive signal-to-noise ratio (SNR)
`parameter and {s,;;
`i = 1, 2, -, n} is a known coherent (Geen
`deterministic) signal sequence. As a practical case, we wish
`to consider the weak signal case (@ + 0*), since this is the
`situation in which the design is most critical, Therefore, rather
`than maximizing the detection probability (8) for a fixed false
`alarm probability (a), we consider the locally optimum de-
`tector for Hg versus H, which maximizes the slope of the
`power function (08(@)/0@) at @ = 0 while keeping a fixed false-
`alarm probability, Within mild regularity conditions,
`the
`locally optimum test statistic for our detection problem is
`given by
`
`Ah
`W= >) si810(X)
`i=]
`
`where the locally optimum nonlinearity g,(-) is given by
`
`Bio) i= —
`
`I@)
`
`(2.2)
`
`(2.3)
`
`
`
`0090-6778/84/0700-0745$01.00 © 1984 IEEE
`
`Page 3 of 9
`
`Page 3 of 9
`
`
`
`
`
`826
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-32, NO. 7, JULY 1984
`
`Noise Reduction in Image Sequences Using
`Motion-Compensated Temporal Filtering
`
`ERIC DUBOIS, memper, IEEE, AND SHAKER SABRI, MEMBER, IEEE
`
`Note that d is not defined in newly exposed areas, i.e., for
`those picture elements (pels) which were not visible in the
`previous field. For backgroundand stationary objects, d(x, f) =
`0, while for an object
`in translational motion, d(x, t) is a
`constant over the object. In general, d(x, t) is a slowly vary-
`ing function of space, except for discontinuities at the edges
`of moving objects.
`The value over time of the image sequenceat a given object
`point
`forms a one-dimensional signal, defined on the time
`interval for which this point is visible in the scene. This signal
`is assumed to be the sum of an image component and an ad-
`ditive noise component. The variation in the image compo-
`nent is solely due to change in the luminance of the object
`point, caused by changes in illumination or orientation of the
`object. This changeis relatively slow, so that the image compo-
`nent
`is a low bandwidth signal. The noise is assumed to be
`white and uncorrelated with the signal. By performing a low-
`pass filtering operation on this signal, the noise component
`can be significantly attenuated, with a minimal effect on the
`Paper approved by the Editor for Signal Processing and Communication
`image component.
`Electronics of the IEEE Commnications Society for publication withoutoral
`In practice,
`the image sequence is sampled spatially, and
`presentation. Manuscript received September 26, 1983. This work was sup-
`it is not precisely possible to filter the sequences correspond-
`ported by the International TelecommunicationsSatellite Organization (IN-
`ing to given object points. However,
`the principle of per-
`TELSAT) under Contract INTEL-114, 1980.
`forming a temporal filtering or averaging operation along the
`E. Dubois is with INRS-Télécommunications, Université du Québec, Ile
`des Soeurs, Verdun, P.Q., Canada H3E 1H6.
`trajectory of motion is feasible. This filtering can be of cither
`S. Sabri is with Bell-Northern Research, Ile des Soeurs, Verdun, P.Q.,
`the recursive or nonrecursive type. Since greater selectivity
`Canada H3E 1H6.
`can be obtained foragiven filter order with recursive filters,
`
`0090-6778/84/0700-0826$01.00 © 1984 IEBE
`
`filtering
`The concept of motion-compensated temporal
`has been described by Huang and Hsu [4]. In this approach,
`the displacement at each picture element
`is estimated, and
`a
`temporal averaging is performed along the trajectory of
`motion. Reference
`[4]
`describes nonrecursive linear and
`median temporal
`filters, both with and without motion
`compensation. However, the amount of noise reduction which
`can be attained with low-order nonrecursive filters is quite
`limited. Also this approach can introduce artifacts in areas
`where motion is not tracked and in newly exposed areas.
`In this paper, the nonlinear recursive filtering approach of
`[2], [3] is extended by the application of motion compensa-
`tion techniques. A specific noise reducer for use with NTSC
`composite television signals is then described, and computer
`simulation results of its performance on several video se-
`quences are presented. It is shown that this approachis success-
`ful
`in improving image quality, while also improving the
`performance of subsequent image coding operations.
`
`Il. MOTION -COMPENSATED TEMPORAL FILTERS FOR
`NoIs—E REDUCTION
`A. Theory ofMotion-Compensated Temporal Filtering
`Let u(x, ¢) be the image intensity at spatial location x =
`(x1, X2) and time f, and let d(x, t) be the displacement of the
`image point at (x, t) between time t — T and ¢. The vector
`field d(x,
`t) is called the displacement field. If the intensity
`of the object point has not changed over the time 7, then
`u(x, t) = u(x— d(x, 1), t—T),
`
`(1)
`
`Abstract—Noise in television signals degrades both the image quality
`and the performance of image coding algorithms. This paper describes a
`nonlinear temporalfiltering algorithm using motion compensation for
`reducing noise in image sequences. A specific implementation for NTSC
`composite television signals is described, and simulation results on several
`video sequences are presented. This approach is shownto be successful in
`improving image quality and also improving the efficiency of subsequent
`image coding operations.
`
`I. INTRODUCTION
`
`Nos introduced in television signals degrades both the
`
`image quality and the performance of subsequent image
`coding operations. This noise may arise in the initial signal
`generation and handling operations, or in the storage or trans-
`mission of these signals. The effect of additive noise on poten-
`tial image coding performanceis illustrated by considering a
`uniformly distributed noise with values —1, 0,
`1 out of 256,
`giving an SNR of 45.8 dB. Although this added noiseis barely
`perceptible, it has an entropy of 1.58 bits/sample, clearly limit-
`ing the image coding compression factor. Thus, there is great
`interest in reducing the noise level in the input signal in order
`to get maximum coding efficiency.
`Noise reduction in image sequences is possible to the ex-
`tent that image and noise components have different character-
`istics. For stationary random processes, the classical method
`of noise reduction is Wiener filtering, based on the image
`and noise power spectra. However, images are not well modeled
`by stationary random processes, and other approaches based on
`improved image models are sought. A major distinguishing fea-
`ture between the noise and signal in image sequencesis that the
`noise is uncorrelated from frame to frame, while the image
`is highly correlated, especially in the direction of motion.
`By performing a low-pass temporal filtering in the direction
`of motion, the noise component can be attenuated without
`affecting the signal component.
`Noise reduction using temporal filtering to give improved
`image quality has been described in [1]-[3]. These systems
`use motion detection,
`as opposed to motion estimation:
`temporal filtering is only applied in the nonchanging parts
`of
`the picture. This
`is accomplished either by explicitly
`segmenting into changing and nonchanging areas, or by a non-
`linear
`filtering approach (to be discussed later). These al-
`gorithms have the disadvantage that noise cannot be reduced in
`moving areas without modifying the image detail, and noise
`can appear and disappear as objects begin and stop moving.
`Although noise in moving areas is masked to some extent by
`the motion, it will still be visible in slowly moving areas.
`
`
`
`LAER
`
`
`Page 4 of 9
`
`
`
`
`
`DUBOIS AND SABRI: NOISE REDUCTION IN IMAGE SEQUENCES
`
`827
`
`this type of filter has been chosen for this application. This
`is especially important
`in temporal filtering, where each in-
`crease by one in filter order requires an additional frame
`memory.
`A block diagram of a first-order recursive temporal filter
`with motion compensation is shown in Fig.
`1
`(assume for
`now that the output of the block NL is a constant value a).
`The basic operation of this filter is described by
`
`Ux, t) = au(x, t) + (1 — a)i(x — d(x, 0, t— 1)
`
`(2)
`
`where U is the output of the filter, d is an estimate of d, and
`U is an estimate of v at a non-grid point obtained by spatial
`interpolation. The signal u(x, t) = D(x — d,
`t — T)is called
`the prediction and e = u — w is called the prediction error.
`This filter requires a frame memory in order to be able to
`form the prediction. A module for estimating the displacement
`field is also required. This estimation can be performed using
`any of a number of algorithms which have been proposed
`in the literature [5]-[8]. The displacement estimator can
`use the input signal as well as any of the signals available in
`the noise reducer to perform the estimate.
`An indication of the ability of this filter to reduce noise
`can be obtained by considering its performance in stationary
`areas where d = 0. In this case, the filter reduces to a standard
`one-dimensional
`temporal recursive filter with transfer func-
`tion
`
` a
`
`
`Displacement
`Estimator
`
`First-order recursive temporal filter with motion compensation.
`
`Fig. 1.
`
`ale)
`
`Ge
`
`ab
`
`32e
`Py
`RS
`°oOc
`2=oO
`ro
`2=i
`=
`
`(3)
`
`H(z) =
`
`[Sas
`It can easily be shown that for a white noise input, the noise
`power is reduced by 10 log;o((2 — a)/a) dB. Due to the
`spatial interpolation error, the performance in moving areas
`will be slightly different, even if the displacement estimate is
`perfectly accurate.
`A numberof modifications are required to make this scheme
`work in practice. The major change is based on the observa-
`tion that the displacement field is not defined for the newly
`exposed parts of the image, and that the displacement estimate
`may not always be accurate, especially in regions where
`(1)
`is violated. These regions are characterized by a large
`value of prediction error. Since the movement is not being
`followed in these regions, it is preferable to disable thefiltering
`operation. This can be accomplished by varying the value of
`@ as a function of the prediction error, which is equivalent
`to passing the prediction error e through a memoryless non-
`linearity y = a(e)ee. A typical piecewise-linear characteris-
`tic for the function a(e) is shownin Fig. 2. It is given by
`
`Xp,
`Xp a
`a(e) = {(———~|e| + Pap — Peay,
`b +e
`
`if|e|<P,;
`
`if Py <|e|<Po:
`
`We,
`
`if |e|> Pp.
`
`(4)
`
`In areas where the motion is tracked, e(x, ¢) is small (of the
`order of the noise level), and a linear temporalfiltering with
`Parameter & = a, is performed. In areas where the motion is
`not being tracked and e(x, ¢) is large, a temporalfiltering with
`parameter & is performed. To avoid introducing artifacts
`in these regions, a, is typically set to unity. For values of e
`between P, and P,, a(e) varies linearly between a, and dp,
`to provide a smooth transition between regions where motion
`is tracked and where it
`is not. The choice of values of P,
`and P. to be used depends on the noise level and the appearance
`of artifacts.
`
`Ph
`
`Pe
`Prediction Error
`
`e
`
`Fig. 2. Nonlinear function for multiplier coefficient a.
`
`The digital noise reducers which have been described in
`the literature [1]-[3] are basically obtained by setting the
`displacement estimate to zero, and filtering only in the sta-
`tionary areas. This can be accomplished by explicitly seg-
`menting into changed and unchanged areas, and filtering
`with a linear temporal filter in the unchanged areas, or by
`using a nonlinear
`temporal
`filter with the nonlinearity as
`described above,
`In either case, the noise in the moving or
`changed areas can only be reduced at the expense of image
`detail. (Note that higher noise level in changing areas is per-
`missible to a certain extent because the movement or change
`will mask the noise), With this system, noise can abruptly
`appear in areas which were fixed and then begin to move.
`If an accurate displacement estimate is available, these effects
`can be reduced. Clearly, a displacement estimator whichis
`robust in the presence of noise is required.
`
`B. A Motion-Compensated Noise Reducer for NTSC
`Composite Video Signals
`temporal
`a particular nonlinear
`This
`section describes
`filter with motion compensation suitable for noise reduction
`in NTSC composite video signals. This noise reducer must
`specifically account for the properties of the NISC composite
`signal, namely, the modulation of the chrominance informa-
`tion on a subcarrier, and the 2:1 line-interlaced scanning. The
`issues related to displacement estimation and prediction from
`NTSC composite signals are discussed in [8]. The techniques
`described here can easily be adapted to component processing
`of color video signals.
`The NTSC Signal: The NTSCsignal has the form
`
`U(t) = ¥(t) + C(t) = Y(t) + ID) cos (2tfget + 33°)
`
`+ Q(t) sin (27f,.t + 33°)
`
`(5)
`
`where Y is the luminance component and J and Q are the
`chrominance components, quadrature-modulated on a sub-
`
`
`——_
`Page 5 of 9
`
`Page 5 of 9
`
`
`
`~
`828
`
`IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. COM-32, NO. 7, JULY 1984
`
`3.579545 MHz. The composite
`frequency ge
`carrier at
`signal
`is sampled orthogonally at a frequency 4/g¢, in phase
`with the 7 component, giving the spatiotemporal sampling
`pattern shownin Fig. 3. With respect to the coordinate system
`of Fig, 3, the sampled composite signal has the form
`
`nyt
`»
`U(a) = Y(a) + U(@) cos — (-1)"?
`
`x2
`
`x2
`
`
`
`a
`
`sin (et|)1)"
`
`+ Q(m) sin
`{——
`]¢ 1)"2
`(6)
`
`where 7 = (7), M2, Nas).
`In order
`to perform the prediction and displacement
`it
`estimation,
`is necessary to separate the composite signal
`U into luminance and chrominance components Y and C.
`This can be accomplished by using a two-dimensional digital
`filter [8S]. In the present system, the chrominance component
`is separated from the composite signal with a separable zero-
`phase FIR bandpass filter having impulse response
`
`J
`1o-2 0
`,
`heft, nQ)=— ][-2
`0
`4 0-2].
`16
`Ue ee,
`a!
`
`(7)
`i
`
`The leminance is obtained by subtracting the chrominance
`component from the composite signal.
`Prediction: The role of the predictor is to estimate the value
`of the composite signal at the current pel from previous fields,
`given the displacement estimate. This estimate Is given by
`
`U(X, OD = YL OF CYA
`
`(8)
`
`where C(x, 1) = 2x, t) or 2Q(x, ¢), Thus, the predictor must
`demodulate the output composite signal, and estimate the
`displaced luminance and chrominance components separately.
`The following prediction scheme has been used. Assume that
`&
`e
`=
`Q
`Qa
`the output F is separated inte components Fp and Cp:
`
`(9)
`
`P(X) = FeO + Coie 9
`~
`“
`.
`;
`.
`where Cg = Sfp or $09. Then F(x, t) = Yo— d,r — 1),
`
`where Fo 8 obtained from Fe by two-dimensional bilinear
`interpolation. Cae, 4) = £Cy@ — [d]2, ¢ — T) where [d],
`
`
`to their
`
`
`
`
`
`nts due to their low bandwidth with respect
`
`~ Stee
`
`computed by
`tf
`rewions,
`
`thon,
`Phe the
`
`MAS, LAS
`©
`Sign
`
`tke
`i
`RCe Sen
`
`the smali
`
`predictor js shown in
`
`
`thms have
`im image se-
`
`t of the algo-
`
`been. selected.
`
`
`Fig. 3. Orthogonal sampling structure for NTSC signals.
`
`
`
`
`
`Y-c
`Separation
`
`Fig. 4. Block diagram of motion-compensated predictor.
`
`area pels are skipped). Define the displaced frame difference
`
`D(x, t, d) = u(x, t)—u(é— d; t— T),
`
`(10)
`
`The goal of thedisplacement estimator is to choose d; so as
`to make Dj, t, d;) as small as possible. This is done recursively
`using the algorithm of steepest descent. giving [6]
`‘
`d; = d;
`
`t=, eD(X;, ee d;
`
`1)Vu@;—- d._ 1-6 T)
`
`ad 1)
`
`Tt has been shownthat the estimator can be greatly simplified,
`without significantly affecting performance, as follows [6]:
`a
`d; = d;
`
`sign (D(X, tC a; 1) sign (Ve; — d;_ asf T)).
`(12)
`
`\
`
`The sean order which hag been found to give good results
`[8]
`is a raster sean of subblocks of size Npels by Mlines.
`the initial displacement estimate for the block is the estimate
`for the last pel
`in the corresponding block in the previous
`field, This scanning orderis illustrated in Fig. 5. As mentioned
`above,
`the displacement estimateis only updated for moving
`
`Page 6 of 9
`
`€
`
`
`ae SnelneeeeeeeeeeeeeSeaeea PEPE
`
`DUBOIS AND SABRI: NOISE REDUCTION IN IMAGE SEQUENCES
`
`VYo(%)—\_4, t-7)
`
`
`
`
`Memory