Download Two Dmension Sgnal and Image Processing by Jae s. Lim PDF

TitleTwo Dmension Sgnal and Image Processing by Jae s. Lim
File Size34.4 MB
Total Pages358
Document Text Contents
Page 1


Alan V. Oppenheim, Editor

ANDREWS AND HUNT Digital lmage Restoration
BRIGHAM The Fast Fourier Transform
BRIGHAM The Fast Fourier Transform and Its Applications
BURDIC Underwater Acoustic System Analysis
CASTLEMAN Digital Image Processing
COWAN AND GRANT Adaptive Filters
CROCHIERE AND RABINER Multirate Digital Signal Processing
DUDGEON AND MERSEREAU Multidimensional Digital Signal Processing
HAMMING Digital Filters, 3IE
HAYKIN, ED. Array Signal Processing
JAYANT AND NOLL Digital Coding of W a v e f o m
KAY Modern Spectral Estimation
KINO Acoustic Waves: Devices, Imaging, and Analog Signal Processing
LEA, ED. Trends in Speech Recognition
LIM Two-Dimensional Signal and Image Processing
LIM, ED. Speech Enhancement
LIM AND OPPENHEIM, EDS. Advanced Topics in Signal Processing
MARPLE Digital Spectral Analysis with Applications
MCCLELLAN AND RADER Number Theory in Digital Signal Processing
MENDEL Lessons in Digital Estimation Theory
OPPENHEIM, ED. Applicatiom of Digital Signal Processing
OPPENHEIM AND SCHAFER Digital Signal Processing
OPPENHEIM AND SCHAFER Discrete-Time Signal Processing
QUACKENBUSH ET AL. Objective Measures of Speech Quality
RABINER AND GOLD Theory and Applications of Digital Signal Processing
RABINER AND SCHAFER Digital Processing of Speech Signals
ROBINSON AND TREITEL Geophysical Signal Analysis
STEARNS AND DAVID Signal Processing Algor i thm
TRIBOLET Seismic Applications of Homomorphic Signal Processing
WIDROW AND STEARNS Adaptive Signal Processing

Department of Electrical Engineering

and Computer Science
Massachusetts Institute of Technology

PRENTICE HALL PTR, Upper Saddle River, New Jersey 07458

Page 2

Library of Congress Cataloging-in-Publication Data

Lim, Jae S.
Two-dimensional signal and image processing 1 Jae S. Lim

p. cm.- rentic ice Hall signal processing series)
~ i b l i o ~ r a ~ h ~ : p.
Includes index.
ISBN 0-13-935322-4
1. Signal processing-Digital techniques. 2. Image processing-

Digital techniques. I. Title. 11. Series.
TK5102.5.L54 1990
621.382'2-dc20 89-33088


EditoriaYproduction supervision: Raeia Maes
Cover design: Ben Santora
Manufacturing buyer: Mary Ann Gloriande

O 1990 Prentice Hall PTR
Prentice-Hall, Inc.
Simon & Schuster I A Viacom Company
Upper Saddle River, New Jersey 07458

All rights reserved. No part of this book may be
reproduced, in any form or by any means,
without permission in writing from the publisher.

Printed in the United States of America

ISBN 0-13-735322-q

Prentice-Hall International (UK) Limited, London
Prentice-Hall of Australia Pty. Limited, Sydney
Prentice-Hall Canada Inc., Toronto
Prentice-Hall Hispanoamericana, S. A , , Mexico
Prentice-Hall of India Private Limited, New Delhi
Prentice-Hall of Japan, Inc., Tokyo
Simon & Schuster Asia Pte. Ltd., Singapore
Editora Prentice-Hall do Brasil, Ltda., Rio de Janeiro


Page 179

Figure P5.19

(a) Let a sequence c(n, , n,) denote the inverse of b(n , , n,); that is,

Is c(n, , n,) a well-defined sequence; that is, is C ( w , , w,) a valid Fourier transform?
Explain your answer.

(b) Can you recover a(n, , n,) from b(n , , n,)? If so, express a(n , , n,) in terms of
b(n , , n,). If not, explain why a(n , , n,) cannot be recovered from b(n, , n,).

5.20. Suppose an image x(n , , n,) is degraded by blurring in such a way that the blurred
image y(n , , n,) can be represented by

where b(n, , n,) represents the impulse response of the blurring system. Using the
complex cepstrum, develop a method to reduce the effect of b(n , , n,) by linear filtering
in the complex cepstrum domain. This type of system is referred to as a homomorphic
system for convolution. Determine the conditions under which the effect of b (n , , n,)
can be completely eliminated by linear filtering in the complex cepstrum domain.

5.21. Consider a 2 x 2-point first-quadrant support sequence a(n , , n,) sketched in the
following figure.

Infinite Impulse Response Filters Chap. 5

Figure P5.21

Let b(n, , n,) be a 2 x I-point sequence that is zero outside 0 5 n , 5 1 , n, = 0.
Determine b(n , , n,), the planar least squares inverse of a (n , , n,).

5.22. In this problem, we study one significant difference between spatial and frequency
domain methods. For simplicity, we consider the I-D case. The result extends
straightforwardly to the 2-D case. Let the desired impulse response hd(n) be given

hd(n) = ( f )"u(n) + 8(4)"u(-n - 1). (1)
Let the desired frequency response Hd(w) be the Fourier transform of hd(n). We
wish to design an TIR filter with the system function given by

Let h(n) denote the impulse response of the filter.
(a) In a spatial domain design method, we assume that the computational procedure

is given by

We estimate the filter coefficients a , b , and c by minimizing

Error = 2 (hd(n) - h(n) )2 .
" = -r

Show that a = -4, b = 0, c = 1 , and h(n) is given by h(n) = (4lnu(n).
(b) Is the system in (a) stable?
(c) In a frequency domain design method, we assume that

We estimate a , b , and c by minimizing

' j H a w ) - H(w)12 dw. Error = - 27T w = - =

Chap. 5 Problems

Page 180

Show that a = - 912, b = 2, c = - 7, and h(n) obtained by inverse Fourier
transforming H(w) is given by

Note that the filter is stable, but it does not have the same region of support as
h(n) in (a), and it is not even recursively computable.

(d) Suppose we use the a, b, and c obtained in (c) but use the computational procedure
in (3). Determine h(n) and show that the system is unstable.

(e) Suppose hd(n) = (f)"u(n). Show that the impulse responses obtained from the
spatial domain design method in (a) and the frequency domain design method in
(c) are the same.

Even though Parseval's theorem states that the two error criteria in (4) and (6) are
the same, they can lead to different results in practice, depending on how they are

5.23. One error criterion that penalizes an unstable filter is given by (5.127). If we let the
parameter a in (5.127) approach a , is the filter designed guaranteed to be stable? Is

minimizing the Error in (5.127) while letting a approach a good way to design an
IIR filter?

5.24. In one design method by spectral transformation, a 2-D IIR filter is designed from a
I-D IIR filter. Let H(z) represent a 1-D causal and stable IIR filter. The filter is
a lowpass filter with cutoff frequency of 312. We design two 2-D filters H,(z,, z,)
and H2(z1, 2,) by

(a) What is the approximate magnitude response of H,(z,, z,)?
(b) Is H,(zI, 2,) stable and recursively computable?
(c) What is the approximate magnitude response of [email protected],, z,)?
(d) Is H2(z1, 2,) stable and recursively computable?
(e) We design another 2-D filter HT(zI, 2,) by

What is the approximate magnitude response of HT(zI, z2)? : I
5.25. Let H(z,, z,) denote a system function given by 1

(a) Sketch a signal flowgraph that realizes the above system function using a direct

(b) Sketch a signal flowgraph that realizes the above system function using a cascade

5.26. Consider the following computational procedure:

Draw a signal flowgraph that requires the smallest (within a few storage elements
from the ~ i n i m u n : possible) ~ m b c i cf storage wi ts when the input is available row

by row. You may assume that the input x(n,, n,) is zero outside 0 5 n, 5 N - 1,
0 s n, 5 N - 1 where N >> 1, and that we wish to compute y(n,, n,) for 0 5 n, 5
N - 1 , 0 s n 2 s N - 1 .

Figure P5.27

(a) Write a series of difference equations that will realize the above signal flowgraph.
(b) Determine the system function of the above signal flowgraph.

5.28. Consider a first-quadrant support IIR filter whose system function is given by

The filter may or may not be stable, depending on the coefficients, a, b, and c.
(a) If a = 2, b = 4, and c = 8, the filter is unstable. Determine H'(zl , z,) which

is stable and is a first-quadrant support system, and which has the same magnitude
response as H(zl, 2,). Note that the denominator polynomial is factorable for
this choice of a, b, and c.

(b) We wish to implement H(z,, z,), even though it may be unstable. Sketch a signal
flowgraph of H(zl, z,), which minimizes (within a few storage elements from the
minimum possible) the number of storage elements needed when the input is
available column by column. Find the total number of storage elements needed
when the input is zero outside 0 s n, 5 N - 1, 0 5 n2 5 N - 1 and we wish to
compute the output for 0 s n, s N - 1 , 0 n, 5 N - 1.

5.29. Consider the following signal flowgraph, which implements an IIR filter:

v, In,, n,)
t v(nl, nz)

x(nl, nz) o

Figure P5.29

Chap. 5 Problems

Infinite Impulse Response Filters Chap. 5
; 1

Page 357

Spatial domain design (cont.)
linear closed-form algorithms,

zero-phase filter design, 283-85

Spatial frequency response, mach
band effect and, 432-34

Spatial interpolation, 495-97
motion estimation methods and,

509- 11
Spatial masking, 434-35
Spatial resolution, 440, 441
Spatio-temporal constraint equation,

Spatio-temporal constraint methods,

Special support systems, 20-22
Spectral estimation, random

processes and, 347 -58
Spectral estimation methods:

application of, 391 -97
based on autoregressive signal

modeling, 369, 371-73, 375,

conventional methods, 361-63
data or correlation extension, 377
dimension-dependent processing,

363, 365
estimating correlation, 388-89, 391
maximum entropy method, 377-81
maximum likelihood method,

365-67, 369
modern or high resolution, 363
performance comparisons of,

Spectral subtraction, short-space,

545 -46

algorithms for testing, 117- 19
one-dimensional tests, 119-24
problem of testing, 102-5
theorems, 105-17

Stabilization of unstable filters, 304
by the complex cepstrum method,

by the planar least squares inverse

method, 308-9

Stable systems, 20 I

State-space representation, 325-28
Stationary random process, 349-50
Statistical coding, 613
Statistical parameter estimation,

Steepest descent method, 279 -80

with accelerated convergence
method, 281

Stopband region, 201
Stopband tolerance, 202
Subband signal coding, 632, 639
Subimage-by-subimage coding, 647
Subimage-by-subimage processing,

Subtractive color systems, 419-20
Symmetry properties:

discrete cosine transform and, 158
discrete Fourier series and, 138
discrete Fourier transform and, 142
discrete-space cosine transform

and, 162
Fourier transform and, 25
z-transform and, 76

convolution, 14-20
linear, 12-14
purpose of, 1-2
shift-invariant , 12- 14
special support, 20-22
stable, 20
See also Linear shift-invariant


Television images, improving,

Temporal filtering for image

frame averaging, 568-70
motion-compensated, 570, 573-75

Threshold coding, 647-48
Tolerance scheme? 2.01

Transform image coding:
adaptive coding and vector quan-

tization, 655-56
description of, 42, 590, 642
hybrid, 654-55
implementation considerations and

examples, 647-52
properties of, 642-44
reduction of blocking effect,

type of coders, 644-47

Transition band, 202
Tree codebook and binary search,

609- 11
Tristimulus values, 420-21
Tube sensors, 440
Two-channel coders, 466, 468, 538,

630, 632

comparison of one- and two-
dimensional linear constant
coefficient difference equa-
tions, 79

comparison of one- and two-
dimensional optimal filter
design, 240 - 43

complex cepstrum, 301 -4
discrete cosine transform, 154-57
discrete-space cosine transform,

See also Discrete-space signals,


Ultraviolet radiation, 414
Uniform convergence, Fourier trans-

form and, 25
Uniform-length codeword

assignment, 612- 13
Uniquely decodable, 612
Unit sample sequence, 3-5
Unit step sequence, 5-6


Unit surface, 66
Unsharp masking, 459, 462-63
Useful relations, z-transform and, 76

Variable-length codeword
assignment, 613- 16

Vector quantization, 598-611
adaptive coding and, 640-42,

Vector radix fast Fourier transforms,

Vertical state variables, 327
Video communications and

conferencing, 411
Vidicon, 438-40
Visual system, human:

adaptation, 431-32
the eye, 423-28
intensity discrimination, 429-31
mach band effect and spatial

frequency response, 432-34
model for peripheral level of,

other visual phenomena, 435-37
spatial masking, 434-35

Waveform coding:
advantages of, 617
delta modulation, 622, 624-27
description of, 590
differential pulse code modulation,

pulse code modulation, 618-21
pyramid coding, 632-34, 636-40
subband coding, 632, 639
two-channel coders, 630, 632

lndex I

Page 358

vector quantization and adaptive,

Weber's law, 430
Wedge support output mask, 95
Wedge support sequence, 21 -22
Weighted Chebyshev approximation

problem, 236, 239, 268
White noise process, 351
Wiener filtering:

adaptive, 536-39
noncausal, 354-56
reducing additive random noise

and, 527-31
variations of, 531 -33

Window method of design for finite
impulse response filters,
202- 13

Winograd Fourier transform
algorithm (WFTA), 178-82

Zero-mean random process, 349
Zero-order interpolation, 496
Zero-phase filter design:

frequency domain design, 313- 15
spatial domain design, 283-85

Zero-phase filters, 196-99
Zonal coding, 647-48

definition of, 65-66
examples of, 67-72
inverse, 76-78
linear constant coefficient

difference equations and,
78- 102

properties of, 74, 76
rational, 102
stability and, 102-24


Similer Documents