`
`George Wolberg
`
`
`
`IEEE Computer Society Press Monograph
`
`
`
`VALEO EX. 1029_001
`
`VALEO EX. 1029_001
`
`
`
`DIGITAL IMAGE WARPING
`
`George Wolberg
`
`Department of Computer Science
`Columbia University
`New York
`
`®
`
`IEEE Computer Society Press
`Los Alamitos, California
`
`Washington
`
`0 Brussels
`
`0
`
`Tokyo
`
`
`
`E1
`
`F?
`:2.g
`i:1‘
`it;
`
`
`
`
`
`
`-.x.*-.mm1.12%:»
`
`
`
`VALEO EX. 1029_002
`
`
`
`Published by
`
`IEEE Computer Society Press
`10662 Los Vagueros Circle
`P.O. Box 3014
`Los Alamitos. CA 90720-1264
`
`Copyright © 1990 by the Institute of Electrical and Electronics Engineers, Inc.
`
`Cover credit: Raziet's Transformation Sequence from Willow.
`Courtesy of Industrial Light 81 Magic, 3 Division of Lucastilm Ltd.
`© 1988 Lucastilm Ltd. All Rights Reserved.
`
`Cover layout by Vic Grenrock
`
`Printed in United States of America
`
`Copyright and Reprint Permissions: Abstracting is permitted with credit to the source.
`Libraries are permitted to photocopy beyond the limits of U.S. copyright law for private
`use of patrons those articles in this volume that carry a code at the bottom of the first
`page. provided the per-copy fee indicated in the code Is paid through the Copyright
`Clearance Center, 29 Congress Street, Salem, MA 01970.
`Instructors are permitted to
`photocopy isolated articles for noncommercial classroom use without fee. For other
`copying, reprint or republication permission. write to Director, Publishing Services, IEEE,
`345 East 47th Street, New York, NY 1001?. Ali rights reserved.
`
`IEEE Computer Society Press Order Number 1944
`IEEE Catalog Number EH0322-8
`ISBN 0-8186-8944-7 (case)
`ISBN 0-8186-5944-0 (microfiche)
`SAN 264-620X
`
`Additional copies can be ordered from:
`
`IEEE Computer Society Press
`Customer Service Banter
`10552 Lee Vaquere: Circle
`[0311:3014
`
`Ln: Alumina,“ 00320-1264
`
`IEEE Computer Society
`13, Avenue de I'Aquilon
`B-1200 Brussels
`BELGIUM
`
`IEEE Computer Society
`Ooshima Building
`2-194 Minami—Aoyema.
`Mlnato—Ku
`
`iEEE Service Center
`445 Hoes Lane
`P.O. Box 1331
`Piscataway. NJ 08355-1331
`
`Tokyo 107'. JAPAN
`
`
`
`--“*II‘EDHHR'tij-q-jn
`
`
`
`
`
`VALEO EX. 1029_003
`
`
`
`‘Hh——-‘
`
`-.k
`
`I
`
`.
`
`l.
`
`
`
`,_s_“;_;:..__.p___e_'
`
`HO.
`
`3 source.
`
`>r private
`f the first
`Dopyrtght
`What! to
`=or other
`as, IEEE.
`
`Canter
`Lane
`1831
`38855-1331
`
`PREFACE
`
`Digital image warping is a growing branch of image processing that deals with
`geometric transformation techniques. Early interest in this area dates back to the mid-
`19603 when it was introduced for geometric correction applications in remote sensing.
`Since that time it has experienced vigorous growth, finding uses in such fields as medical
`imaging, computer vision, and computer graphics. Although image warping has tradi-
`tionally been dominated by results from the remote sensing community, it has recently
`enjoyed a new surge of interest from the computer graphics field. This is largely due to
`the growing availability of advanced graphics workstations and increasingly powerful
`computers that make warping a viable tool for image synthesis and special effects. Work
`in this area has already led to successful market products such as real-time video effects
`generators for the television industry and cost-effective warping hardware for geometric
`correction. Current trends indicate that this area will have growing impact on desktop
`video, a new technology that promises to revolutionize the video production market in
`much the same way as desktop publishing has altered the way in which people prepare
`documents.
`
`Digital image warping has benefited greatly from several fields, ranging from early
`work in remote sensing to recent developments in computer graphics. The scope of these
`contributions, however, often varies widely owing to different operating conditions and
`assumptions. This state is reflected in the image processing literature. Despite the fact
`that image processing is a well-established subject with many textbooks devoted to its
`study, image warping is generally treated as a peripheral subject with only sparse cover
`age. Furthermore, these textbooks rarely present image warping concepts as a single
`body of knowledge. Since the presentations are usually tailored to some narrow reader-
`ship, different components of the same conceptual framework are emphasized. This has
`left a noticeable gap in the literature with respect to a unified treatment of digital image
`warping in a single text. This book attempts to redress this imbalance.
`The purpose of this book is to introduce the fundamental concepts of digital image
`warping and to lay a foundation that can be used as the basis for further study and
`research in this field. Emphasis is given to the development of a single coherent
`
`
`
`VALEO EX. 1029_004
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`vi
`
`PREFACE
`
`framework. This serves to unify the terminology, motivation, and contributions of many
`disciplines that have each contributed in significantly different ways. The coherent
`framework puts the diverse aspects of this subject
`into proper perspective.
`In this
`manner, the needs and goals of a diverse readership are addressed.
`This book is intended to be a practical guide for eclectic scientists and engineers
`who find themselves in need of implementing warping algorithms and comprehending
`the underlying concepts.
`It is also geared to students of image processing who wish to
`apply their knowledge of that subject to a well—defined application. Special effort has
`been made to keep prerequisites to a minimum in the hope of presenting a self-contained
`treatment of this field. Consequently. knowledge of elementary image processing is
`helpful, although not essential. Furthermore, every effort is made to reinforce the discus-
`sion with an intuitive understanding. As a result. only those aspects of supporting theory
`that are directly relevant to the subject are brought to bear. Interested readers may con-
`sult the extensive bibliography for suggested readings that delve further into those areas.
`This book originally grew out of a survey paper that I had written on geometric
`transfonnation techniques for digital images. During the course of preparing that paper,
`the large number of disparate sources with potential bearing on digital image warping
`became strikingly apparent. This writing reflects my goal to consolidate these works into
`a self—contained central repository. Since digital image warping involves many diverse
`aspects, from implementation considerations to the mathematical abstractions of sam—
`pling and filtering theory, I have attempted to chart a middle path by focusing upon those
`basic concepts, techniques, and problems that characterize the geometric transformation
`of digital
`images, given the inevitable limitations of discrete approrrimations. The
`material in this book is thus a delicate balance between theory and practice. The practi—
`cal segment includes algorithms which the reader may implement. The theory segment
`is comprised of proofs and formulas derived to motivate the algorithms and to establish a
`standard of comparison among them.
`In this manner, theory provides a necessary context
`in which to understand the goals and limitations of the collection of algorithms presented
`herein .
`
`The organization of this book closely follows the components of the conceptual
`framework for digital image warping. Chapter 1 discusses the history of this field and
`presents a brief overview of the subsequent chapters. A review of common terminology,
`mathematical preliminaries, and digital image acquisition is presented in Chapter 2. As
`we shall see later, digital image warping consists of two basic operations: a spatial
`transformation to define the rearrangement of pixels and interpolation to compute their
`values. Chapter 3 describes various common formulations for spatial transformations. as
`well as techniques for inferring them when only a set of correspondence points are
`known. Chapter 4 provides a review of sampling theory, the mathematical framework
`used to describe the filtering problems that follow. Chapter 5 describes image resam—
`pling, including several common interpolation kernels. They are applied in the discus-
`sion of antialiasing in Chapter 6. This chapter demonstrates several approaches used to
`avoid artifacts that manifest themselves to the discrete nature of digital images. Fast
`warping techniques based on scanline algorithms are presented in Chapter 7. These
`
`.........___
`
`
`
`
`
`g:A—--=LWW——.,-
`
`
`
`.weane-mgt
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` n.“.
`
`
`
`
`
`.,__.FH-a.i-;-II.‘,fl...
`
`VALEO EX. 1029_005
`
`
`
`vii
`
`results are particularly useful for both hardware and software realizations of geometric
`transformations. Finally, the main points of the book are recapitulated in Chapter 8.
`Source code, written in C, is scattered among the chapters and appendices to demonstrate
`implementation details for various algorithms.
`
`It is often difficult to measure the success of a book. Ultimately, the effectiveness
`of this text can be judged in two ways. First, the reader should appreciate the difficulties
`and subtleties in actually warping a digital image. This includes a full understanding of
`the problems posed due to the discrete nature of digital images, as well as an awareness
`of the tradeoffs confronting an algorithm designer. There are valuable lessons to be
`learned in this process. Second, the reader should master the key concepts and tech-
`niques that facilitate further research and development. Unlike many other branches of
`science, students of digital image warping benefit from the direct visual realization of
`mathematical abstractions and concepts. As a result, readers are fortunate to have images
`clarify what mathematical notation sometimes obscures. This makes the study of digital
`image warping a truly fascinating and enjoyable endeavor.
`
`George Wolberg
`
`_-_.-n‘
`
`1%:5:51:1raga-2v;Li"?
`
`ia
`
`ny
`rent
`
`this
`
`eers
`
`iing
`h to
`has
`ined
`
`g is
`cus-
`
`eory
`con—
`:as.
`
`etric
`
`aper,
`
`ping
`into
`ICISC
`sam-
`
`:hose
`ation
`The
`tacti-
`ment
`
`lish a
`ntext
`
`ented
`
`:ptual
`i and
`
`alogy,
`2. As
`
`patial
`their
`ns, as
`ts are
`
`:work
`:sam-
`
`iscus-
`sed to
`Fast
`These
`
`
`
`VALEO EX. 1029_006
`
`
`
`.idmg
`go to
`I1 HU
`'or his
`1g this
`
`if:
`ed the
`Heck-
`Peter
`11'ng
`ed the
`b a lot
`
`.
`mdmg
`by the
`“3" £01"
`Iftware
`30“”
`
`1' 10%:
`OR was
`to the
`
`.
`
`'
`
`'
`1.
`
`.
`
`.
`
`.-
`I
`1‘
`'=
`1
`
`.
`
`Q
`:
`'3
`
`if
`‘5
`'
`
`CHAPTER 1
`
`/
`
`CHAPTER 2
`
`_
`
`TABLE OF CONTENTS
`
`INTRODUCTION
`1.1 BACKGROUND
`1.2 OVERVIEW
`1.2.1 Spatial Transfonnations
`
`1.2.2 Sampling Theory
`1.2.3 Re'sarnphng
`1.2.4 Ahasmg
`1.2.5 Scanline Algorithms
`1.3 CONCEPTUAL LAYOUT
`
`PRELIMINARIES
`2.1 FUNDAMENTALS
`2.1.1 Signals and Images
`2.1.2 Filters
`2.1.3 Impulse Response
`2.1.4 Convolution
`2.1.5 Frequency Analysis
`2.1.5.1 An Analogy to Audio Signals
`2.1.5.2 Fourier Transforms
`2.1.5.3 Discrete Fourier Transforms
`2.2 IMAGE ACQUISITION
`2.3 IMAGING SYSTEMS
`2.3.1 Electronic Scanners
`2.3.1.1 Vidicon Systems
`2.3.1.2 Image Dissectors
`2.3.2 Solid-State Sensors
`2.3.2.1 CCD Cameras
`2.3.2.2 ClD Cameras
`2.3.3 Mechanical Scanners
`2.4 VIDEO DIGITIZERS
`2.5 DIGITIZED IIVIAGERY
`2.6 SUMMARY
`
`CHAPTER 3
`
`SPATIAL TRANSFORMATIONS
`3.1 DEFINITIONS
`3.1.1 Forward Mapping
`3.1.2 Inverse Mapping
`3.2 GENERAL TRANSFORMATION MATRIX
`3.2.1 Homogeneous Coordinates
`3.3 AFFINE TRANSFORMATIONS
`3.3.1 Translation
`
`I
`
`1
`1
`6
`6
`
`7
`7
`8
`9
`10
`
`11
`11
`11
`14
`15
`15
`19
`19
`20
`26
`28
`32
`32
`33
`34
`35
`35
`36
`36
`37
`38
`40
`
`41
`42
`42
`44
`45
`46
`47
`43
`
`xi
`
`
`
`VALEO EX. 1029_007
`
`
`
`xii
`
`3.3.2 Rotation
`3.3.3 Scale
`3.3.4 Shear
`
`,
`
`3.3.5 Composite Transformations
`3.3.6 Inverse
`
`3.3.7 Inferring Affine Transformations
`3.4 PERSPECIIVE TRANSFORMATIONS
`3.4.1 Inverse
`
`3.4.2 Inferring Perspective Transformations
`3.4.2.1 Case 1: Square-to-Quadrilateral
`3.4.2.2 Case 2: Quadriiateral—to-Square
`3.4.2.3 Case 3: Quadrilateral-to-Quadrilateral
`3.5 BILINEAR TRANSFORMATIONS
`3.5.1 Bilinearl‘nterpolation
`3.5.2 Separability
`3.5.3 Inverse
`
`3.5.4 Interpolation Grid
`36 POLYNOMIAL TRANSFORMATIONS
`3.6.1 Inferring Polynomial Coefficients
`3.6.2 Pseudoinverse Solution
`3.6.3 Least—Squares With Ordinary Polynomials
`3.6.4 Least—Squares With Orthogonal Polynomials
`3.6.5 Weighted Least-Squares
`3.7 PIECEWISE POLYNOMIAL TRANSFORMATIONS
`3.7.1 A Surface Fitting Paradigm for Geometric Correction
`3.7.2 Procedure
`
`3.7.3 Triangulation
`3.7.4 Linear Triangular Patches
`3.7.5 Cubic Triangular Patches
`3.8 GLOBAL SPLINES
`3.8.1 Basis Functions
`
`3.8.2 Regularization
`3.8.2.1 Gfitnson, 1981
`
`3.8.2.2 Terzopoulos, 1984
`3.8.2.3 Discontinuity Detection
`3.8.2.4 Boult and Kender, 1986
`3.8.2.5 A Definition of Smoothness
`3.9 SUMMARY
`
`CHAPTER 4
`
`SAMPLING THEORY
`4.1 INTRODUCTION
`4.2 SAMPLING
`4.3 RECONSTRUCTION
`4.3.1 Reconstruction Conditions
`
`49
`49
`49
`50
`50
`50
`52
`52
`53
`54
`56
`56
`57
`58
`59
`60
`60
`61
`63
`
`65
`67
`70
`75
`75
`77
`78
`78
`80
`81
`81
`84
`85
`86
`87
`88
`91
`92
`
`95
`95
`96
`99
`
`”way—u.-.
`
`
`
`VALEO EX. 1029_008
`
`
`
`\
`
`
`
`..-..m_.-._-_.-.1__-...__._.....__..._..................
`
`‘_
`i
`.
`E
`
`:-
`3
`31
`1
`3
`
`4.3.2 Ideal Low-Pass Filter
`4.3.3 Sine Function
`
`4.4 NONIDEAL RECONSTRUCTION
`4.5 ALIASING
`
`4.6 ANTIALLASING
`4.7 SUMMARY
`
`CHAPTER 5
`
`IMAGE RESAMPLING
`5.1 INTRODUCTION
`
`5.2 IDEAL IMAGE RESAMPLWG
`5.3 INTERPOLATION
`5.4 INTERPOLATION KERNELS
`
`5.4.1 Nearest Neighbor
`5.4.2 Linear Interpolation
`5.4.3 Cubic Convolution
`5.4.4 TWO-Parameter Cubic Filters
`
`5.4.5 Cubic Splines
`5.4.5.1 B-Splines
`5.4.5.2 Interpolating B-Splines
`5.4.6 Windowed Sine Function
`
`5.4.6.1 Hann and Hamming Windows
`5.4.6.2 Blackman Window
`5.4.6.3 Kaiser Window
`5.4.6.4 Lanczos Window
`5.4.6.5 Gaussian Window
`5.4.7 Exponential Filters
`5.5 COMPARISON OF ENTERPOLATION METHODS
`5.6 IMPLEMENTATION
`
`5.6.1 Interpolation with Coefficient Bins
`5.6.2 Fant’s Resampling Algorithm
`5.7 DISCUSSION
`
`CHAPTER6 ANTIALIASING
`6.1
`INTRODUCTION
`
`6.1.1 Point Sampling
`6.1.2 Area Sampling
`6.1.3 Space-Invaiiant Filtering
`6.1.4 Space-Variant Filtering
`6.2 REGULAR SAMPLING
`
`6.2.1 Supersampling
`6.2-2 Adaptive Supersampling
`6.2.3 Reconstmction from Regular Samples
`6.3 IRREGULAR SAMPLING
`6.3.1 Stochastic Sampling
`
`xiii
`
`100
`101
`103
`106
`108
`112
`
`117
`117
`119
`124
`126
`126
`127
`129
`131
`133
`134
`136
`137
`139
`140
`141
`142
`143
`145
`147
`150
`150
`153
`160
`
`163
`163
`163
`166
`168
`168
`168
`168
`169
`171
`173
`173
`
`49
`49
`49
`50
`50
`50
`52
`52
`53
`54
`56
`56
`57
`58
`59
`60
`60
`61
`63
`
`65
`67
`70
`75
`75
`77
`78
`78
`80
`81
`81
`84
`85
`86
`87
`88
`91
`92
`
`95
`95
`96
`
`99
`99
`
`
`
`VALEO EX. 1029_009
`
`
`
`xiv
`
`.2.
`
`
`
`rr'a-r-A-....__.u
`
`t:
`
`.3
`3
`
`
`
`
`
`
`
`
`
`
`
`5
`
`.
`
`,3
`.
`
`174
`175
`176
`177
`177
`178
`17s
`178
`178
`179
`179
`181
`181
`183
`184
`184
`185
`187
`188
`188
`188
`188
`189
`189
`190
`191
`196
`197
`199
`201
`205
`205
`206
`206
`208
`212
`214
`215
`215
`215
`217
`\217
`
`.
`
`3
`5
`53
`2;
`_.
`i
`l
`g:
`7
`l
`:f
`g
`‘1‘
`2?:
`
`
`
`-'
`£-
`
`'
`
`6.3.2 Poisson Sampling
`6.3.3 littered Sampling
`6.3.4 Point-Diffusion Sampling
`6.3.5 Adaptive Stochastic Sampling
`6.3.6 Reconstruction from Irregular Samples
`6.4 DIRECT CONVOLUTION
`6.4.1 Catmull, 1974
`6.4.2 Blinn and Nowell, 1976
`6.4.3 Feibush, Levoy, and Cook, 1980
`6.4.4 Gangnet, Pemy, and Coueignoux, 1982
`6.4.5 Greene and Heckbert, 1986
`6.5 PREFlLTERlNG
`6.5.1 Pyramids
`6.5.2 Summed-Area Tables
`6.6 FREQUENCY CLAMPING
`6.7 ANTIALIASED LINES AND TEXT
`6.8 DISCUSSION
`CHAPTER 7 SCANLINE ALGORITHMS
`7.1 INTRODUCTION
`7.1.1 Forward Mapping
`7.1.2 Inverse Mapping
`7.1.3 Separable Mapping
`72 INCREMENTAL ALGORITHMS
`7.2.1 Texture Mapping
`
`
`7.2.2 Gouraud Shading
`
`
`7.2.3 Incremental Texture Mapping
`
`
`7.2.4 Incremental Perspective Transformations
`
`
`7.2.5 Approximation
`
`
`7.2.6 Quadratic Interpolation
`
`
`7.2.7 Cubic Interpolation
`
`
`7.3 ROTATION
`
`
`7.3.1 Braccini and Marine, 1980
`
`
`7.3.2 Weiman, 1980
`
`
`7.3.3 Cannull and Smith, 1980
`
`
`7.3.4 Paeth, 1986/ Tanaka. et. a1., 1986
`
`
`7.3.5 Cordic Algorithm
`
`
`7.4 2—PASS TRANSFORMS
`
`
`7.4.1 Catmull and Smith, 1980
`
`
`7.4.1.1 FirstPass
`
`
`7.4.1.2 Second Pass
`
`
`7.4.1.3 2—Pass Algorithm
`
`
`7.4.1.4 An Example: Rotation
`
`
`7.4.1.5 Another Example: Perspective
`
`
`VALEO EX. 1029_0010
`
`
`
`174
`175
`176
`177
`177
`178
`178
`178
`178
`179
`179
`181
`181
`
`183
`184
`184
`185
`
`7.
`[5
`
`'
`
`;
`
`'..
`'
`
`219
`7.4.1.6 Bottleneck Problem
`220
`7.4.1.7 Foldover Problem
`221
`7.4.2 Fraser, Schowengerdt, and Briggs, 1985
`221
`7.3.3 Smith, 1987
`222
`7.5 2—PASS MESH WARPING
`222
`7.5.1 Special Effects
`224
`7.5.2 Description of the Algorithm
`225
`7.5.2.1 First Pass
`228
`7.5.2.2 Second Pass
`228
`7.5.2.3 Discussion
`230
`7.5.3 Examples
`233
`7.5.4 Source Code
`240
`7.6 MORE SEPARABLE MAPPINGS
`240
`7.6.1 Perspective Projection: Robertson, 1987
`7.6.2 Warping Among Arbitrary Planar Shapes: Wolberg, 1988 241
`7.6.3 Spatial hookup Tables: Wolberg and Boult, 1989
`242
`7.7 SEPARABLE IMAGE WARPJNG
`242
`7.7.1 Spatial Lookup Tables
`244
`7.7.2 Intensity Resampling
`244
`7.7.3 Coordinate Resampling
`245
`7.7.4 Distortions and Errors
`245 .
`7.7.4.1 Filtering Errors
`246
`7.7.4.2 Shear
`246
`7.7.4.3 Perspective
`248
`7.7.4.4 Rotation
`248
`7.7.4.5 Distortion Measures
`248
`7.7.4.6 Bottleneck Distortion
`250
`7.7.5 Foldover Problem
`25 1
`7.7.5.1 Representing Foldovers
`251
`7.7.5.2 Tracking Foldovers
`252
`7.7.5.3 Storing Information From Foldovers
`253
`'5
`7.7.5.4 Intensity Resampling with Foldovers
`254
`8
`7.7.6 Compositor
`254
`g
`7.7.7 Examples
`254
`E
`7.8 DISCUSSION
`260
`
` CHAPTER 8 EPILOGUE
` APPENDIX 1 FAST FOURIER TRANSFORMS
`
`XV
`
`266
`267
`269
`270
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`187
`188
`188
`188
`188
`189
`189
`190
`191
`196
`197
`199
`201
`205
`205
`206
`206
`208
`212
`214
`215
`215
`A1.1 DISCRETE FOURIER TRANSFORM
`215
`A12 DANIELSON—LANCZOS LEMMA
`217
`A1.2.1 Butterfly Flowpraph
`
`217
`A1.2.2 Putting It All Together
`218
` A123 Recursive FFI‘ Algorithm
`
`'_
`1;:
`
`
`
`
`
`VALEO EX. 1029_0011
`
`
`
`xvi
`
`A124 Cost of Computation
`A13 COOLEY—TUKEY AlfiORl'I'I-m
`
`\
`
`A1.3.1 Computational Cost
`A1.4 COOLEY-SANDE ALGORITHM
`A15 SOURCE CODE
`
`A1.5.I Recursive FFT Algorithm
`A1.5.2 Cooley-Tukey FFT Algorithm
`
`APPENDIX 2 INTERPOLATING CUBIC SPLINES
`A21 DEFINITION
`A22 CONSTRAINTS
`A23 SOLVING FOR THE SPLIN'E COEFFICIENTS
`
`A2.3.1 Derivation of A 2
`A232 Derivation of A 3
`A2.3.3 Derivation of A 1 and A 3
`A24 EVALUTING THE UNKNOWN DERIVATIVES
`A2.4.1 First Derivatives
`A242 Second Derivatives
`
`A243 Boundary Conditions
`A25 SOURCE CODE
`
`A2.5.1 Ispline
`A2.5.2 Ispline_gcn
`
`APPENDIX 3 FORWARD DIFFERENCE METHOD
`
`i
`
`gi-
`
`REFERENCES
`
`INDEX
`
`273
`274
`275
`276
`278
`279
`281
`
`283
`283
`284
`285
`285
`286
`286
`287
`287
`288
`289
`290
`290
`293
`
`297
`
`301
`
`1
`
`5‘.
`:‘L‘
`i;
`it
`
`
`
`VALEO EX. 1029_0012
`
`
`
`1
`
`INTRODUCTION
`
`1.1. BACKGROUND
`
`Digital image warping is a growing branch of image processing that deals with the
`geometric transformation of digital images. A geometric transfonnation is an operation
`that redefines the spatial relationship between points in an image. Although image warp-
`ing often tends to conjure up notions of highly distorted imagery, a warp may range from
`something as simple as a translation, scale, or rotation, to something as elaborate as a
`convoluted transformation. Since all warps do, in fact, apply geometric transformations
`to images, the terms “warp” and “geometric transformation” are used interchangeably
`throughout this book.
`
`It is helpful to interpret image warping in terms of the following physical analogy.
`Imagine printing an image onto a sheet of rubber. Depending on what forces are applied
`to that sheet, the image may simply appear rotated or sealed, or it may appear wildly dis—
`torted, corresponding to the popular notion of a warp. While this example might seem to
`portray image warping as a playful exercise, image warping does serve an important role
`in many applied sciences. Over the past twenty years, for instance, image warping has
`been the subject of considerable attention in remote sensing, medical imaging, computer
`vision, and computer graphics.
`It has made its way into many applications, including
`distortion compensation of imaging sensors, decalibration for
`image registration,
`geometrical normalization for image analysis and display, map projection, and texture
`mapping for image synthesis.
`
`Historically, geometric transformations were first performed on continuous (analog)
`images using optical systems. Early work in this area is described in {Cutrona 60], a
`landmark paper on the use of optics to perform transformations. Since then, numerous
`advances have been made in this field [Homer 87]. Although optical systems offer the
`distinct advantage of operating at the. speed of light, they are limited in control and flexi-
`bility. Digital computer systems, on‘th'e other hand, resolve these problems and poten-
`tially offer more accuracy. Consequently, the algorithms presented in. this book deal
`exclusively with digital (discrete) images.
`
`
`
`VALEO EX. 1029_0013
`
`
`
`mnonucriow
`
` 2
`
`These projects all involved acquiring multi
`~image sets (i.e., multiple images of the
`same area taken either at different times or with
`different sensors). Immediately, the task
`
`VALEO EX. 1029_0014
`
`
`
`from the
`the US.
`
`ggressive
`onmental
`1’ this ini—
`vernment
`
`g and sur-
`
`ges of the
`-, the task
`
`spending
`)ccur due
`time but
`.ens aber-
`lt various
`fell.
`
`hese dis—
`ale. This
`
`ce points
`and land-
`
`resenting
`tained by
`r polyno-
`1 effects.
`
`ing func-
`egion to
`g.
`
`t in Figs.
`viewing
`'5 in Sep-
`pacecraft
`'oblem is
`nsforma—
`
`:r related
`
`instance,
`ation for
`
`dye are
`:, known
`n. Since
`
`:ing pro-
`)rrnation
`
`
`
`
`
`
`Figure 1.2: Viking Lander 2 image after distortion correction [Green 89].
`
`Image warping is a problem that arises in computer graphics as well. Howover, in
`this field the goal is not geometric correction, but rather inducing geometric distortion.
`Graphics research has developed a distinct repertoire of techniques to deal with this prob-
`lem. The primary application is texture mapping, a technique to map ZwD images onto
`3-D surfaces, and then project them back onto a 2-D viewing screen. Texture mapping
`has been used with much success in achieving visually rich and complicated imagery.
`Furthermore, additional sophisticated filtering techniques have been promoted to combat
`artifacts arising from the severe spatial distortions possible in this application. The thrust
`of this effort has been directed'to the study and design of efficient spatially—varying low—
`pass filters. Since the remote sensing and medical
`imaging fields have generally
`attempted to correct only mild distortions, they have neglected this important area. The
`design of fast algorithms for filtering fairly general areas remains a great challenge.
`
`by W13. Green @1989 Van Nose-and Reinhold. Reprinted by
`Digitfrl image Procem'ng:
`permeation of the Publisher. All Rights Reserved.
`
`
`
`VALEO EX. 1029_0015
`
`
`
`
`
`
`
`._a'firhexemwwa‘tw.451'.
`
`4
`
`INTRODUCTION
`
`Image warping is commonly used in graphics design to create interesting visual
`effects. For instance, Fig. 1.3 shows a fascinating Sequence of warps that depicts a
`transfonnation between two faces, a horse and rider, two frogs, and two dancers. Other
`examples of such applications include the image sequence shown on the front cover, as
`well as other effects described in [Holzmann 88].
`
`3
`
`Figure 1.3: Transformation sequence: faces —> horseirider —> frogs -—> dancers.
`Copyright © 1983 Tom Brigham / NYIT—CGL. All rights reserved.
`
`The continuing development of efficient algorithms for digital image warping has
`gained impetus from the growing availability of fast and cost—effective digital hardware.
`The ability to process high resolution imagery has become more feasible with the advent
`of fast computational elements, high-capacity digital data storage devices, and improved
`display technology. Consequently, the trend in algorithm design has been towards a
`more effective match with the implementation technology. This is reflected in the recent
`
`surge of warping products that exploit scanline algorithms.
`
`VALEO EX. 1029_0016
`
`
`
`1.1 BACKGROUND
`
`5
`
`It is instructive at this point to illustrate the relationship between the remote sensing,
`medical imaging, computer vision, and computer graphics fields since they all have ties
`to image warping. As stated earlier, image warping is a subset of image processing.
`These fields are all connected to image warping insofar as they share a common usage
`for image processing. Figure 1.4 illustrates these links as they relate to images and
`mathematical scene descriptions,
`the two forms of data used by the aforementioned
`fields.
`
`Image Processing
`
`Computer
`Graphics
`
`Computer
`Vision
`
`Description
`
`Scene
`
`Figure 1.4: Underlying role of image processing [Pavlidis 82].
`
`Consider the transition from a scene description to an image, as shown in Fig. 1.4.
`This is a function of a renderer in computer graphics. Although image processing is
`often applied after rendering, as a postprocess,
`those rendering operations requiring
`proper filtering actually embed image processing concepts directly. This is true for warp-
`ing applications in graphics, which manifests itself in the form of texture mapping. As a
`result, texture mapping is best understood as an image processing problem.
`The transition from an input image to an output image is characteristic of image
`processing.
`Image warping is thereby considered an image processing task because it
`takes an input image and applies a geometric transformation to yield an output image.
`Computer vision and remote sensing, on the other hand, attempt
`to extract a scene
`description from an image. They use image registration and geometric correction as
`preliminary components to pattern recognition. Therefore, image warping is common to
`these fields insofar as they share images which are subject to geometric transformations.
`
`Reprinted with permission from Algorithms for Graphics and Image Processing. edited by Theo
`Pavlidis. 1982. Copyright ©1982 by Computer Science Press, Rockville, MD. All rights reserved.
`
`W-a-nurwm_fi.h.
`
`
`
`-../.._.~4.
`
`esting visual
`rat depicts a
`ncers. Other
`
`Ont cover, as
`
`
`
`dancers.
`
`warping has
`tal hardware.
`th the advent
`
`1nd improved
`:n towards a
`
`in the recent
`
`
`
`VALEO EX. 1029_0017
`
`
`
`
`
`aLil-’2?'_."‘._'"-'I.
`
`_.'-u.c
`
`‘3m-
`
`
`
`6
`
`INTRODUCTION
`
`1.2. OVERVIEW
`
`The purpose of this book is to describe the algorithms developed in this field within
`a consistent and coherent framework. It centers on the three components that comprise
`all geometric transformations in image warping: spatial transformations, resampling, and
`antialiasing. Due to the central importance of sampling theory, a review is provided as a
`preface to the resampling and antialiasing chapters.
`In addition, a discussion of efficient
`scanline implementations is given as well. This is of particular importance to practicing
`scientists and engineers.
`
`In this section, we briefly review the various stages in a geometric transformation.
`Each Stage has received a great deal of attention from a wide community of people in
`many diverse fields. As a result,
`the literature is replete with varied terminologies,
`motivations, and assumptions. A review of geometric transformation techniques, partic-
`ularly in the context of their numerous applications, is useful for highlighting the com-
`mon thread that underlies their many forms. Since each stage is the subject of a separate
`chapter, this review should serve to outline the contents of this book. We begin with
`some basic concepts in spatial transformations
`
`1.2.1. Spatial Transformations
`
`The basis of geometric transformations is the mapping of one coordinate system
`onto another. This is defined by means of a spatial transformation _ a mapping func-
`tion that establishes a spatial correspondence between all points in the input and output
`images. Given a spatial transformation, each point in the output assumes the value of its
`corresponding point in the input image. The correspondence is found by using the spatial
`transformation mapping function to project the output point onto the input image.
`
`Depending on the application, spatial transformation mapping functions may take
`on many different forms. Simple transformations may be specified by analytic expres-
`sions including affine, projective, bilinear, and polynomial
`transformations. More
`sophisticated mapping functions that are not conveniently expressed in analytic terms can
`be determined from a sparse lattice of control points for which spatial correspondence is
`known. This yields a spatial representation in which undefined points are evaluated
`through interpolation.
`Indeed, taking this approach to the limit yields a dense grid of
`control points resembling a 2-D spatial lookup table that may define any arbitrary map—
`ping function.
`
`transformation is compIetely
`the spatial
`for example,
`In computer graphics,
`;
`specified by the parameterization of the 3-D object, its position with respect to the 2-D
`projection plane (i.e., the viewing screen), viewpoint, and center of interest. The objects
`are usually defined as planar polygons or bicubic patches. Consequently, three coordi-
`nate systems are used: 2-D texture space, 3-D object space, and 2-D screen space. The
`various formulations for spatial transformations, as well as methods to infer them, are
`discussed in Chapter 3.
`
` ..
`
`owner-$512—a..-
`
`
`
`
`
`VALEO EX. 1029_0018
`
`
`
`this field within
`
`:s that comprise
`resampling, and
`is provided as a
`sion of efficient
`
`ice to practicing
`
`transformation.
`
`tity of people in
`i terminologies,
`ehniques, partic-
`ghting the com-
`.ect of a separate
`We begin with
`
`)ordinate system
`a mapping func-
`input and output
`:s the value of its
`
`' using the spatial
`ut image.
`
`notions may take
`' analytic expres-
`irmations. More
`
`tnalytic terms can
`:orrespondence is
`nts are evaluated
`
`5 a dense grid of
`my arbitrary map—
`
`th is completely
`espect to the 2-D
`:rest. The objects
`itly, three coordi—
`creen space. The
`:0 infer them, are
`
`up,«1.-
`
`Weaver-k:w“V-
`
`12 OVERVIEW
`
`7
`
`1.2.2. Sampling Theory
`
`In the continuous domain, a geometric transformation is fully specified by the spa—
`tial transformation. This is due to the fact that an analytic mapping is bijective — one-
`to—one and onto. However, in our domain of interest, complications are introduced due
`to the discrete nature of digital images. Undesirable artifacts can arise if we are not care-
`
`ful. Consequently, we turn to sampling theory for a deeper understanding of the problem
`at hand.
`
`Sampling theory is central to the study of sampled-data systems, e.g., digital image
`transformations.
`It lays a firm mathematical foundation for the analysis of sampled sig-
`nals, offering invaluable insight into the problems and solutions of sampling. It does so
`by providing an elegant mathematical formulation describing the relationship between a
`continuous signal and its samples. We use it to resolve the problems of image recon—
`struction and aliasing. Note that reconstruction is an interpolation procedure applied to
`the sampled data and that aliasing simply refers to the presence of unreproducibly high
`frequencies and the resulting artifacts.
`
`Together with defining theoretical
`
`limits on the continuous reconstruction of
`
`discrete input, sampling theory yields the guidelines for numerically measuring the qual—
`ity of various proposed filtering techniques. This proves most useful in formally describ—
`ing reconstruction, aliasing, and the filtering necessary to combat the artifacts that may
`appear at the output. The fundamentals of sampling theory are reviewed in Chapter 4.
`
`1.2.3. Resampling
`
`transformation is established, and once we accommodate the
`Once a spatial
`subtleties of digital filtering, we can proceed to resample the image. First, however,
`some additional background is in order.
`
`In digital images, the discrete picture elements, or pixels, are restricted to lie on a
`sampling grid, taken to be the integer lattice. The output pixels, now defined to lie on the
`output sampling grid, are passed through the mapping function generating a new grid
`used to resample the input. This new resampling grid, unlike the input sampling grid,
`does not generally coincide with the integer lattice. Rather, the positions of the grid
`points may take on any of the continuous values assigned by the mapping function.
`
`Since the discrete input is defined only at integer positions, an interpolation stage is
`introduced to fit a continuous surface through the data samples. The continuous surface
`may then be sampled at arbitrary positions. This interpolation stage is known as image
`reconstruction.
`In the literature, the terms “reconstruction" and “interpolation” are
`used interchangeably. Collectively, image reconstruction followed by sampling is known
`as image resampling.
`
`Image resampling consists of passing the regularly spaced output grid through the
`1
`spatial transformation, yielding a resampling grid that maps into the input image. Since
`the input is discrete,
`image reconstruction is performed to interpolate the continuous
`input signal from its samples. Sampling the reconstructed signal gives us the values that
`are assigned to the output pixels.
`
`
`
`VALEO EX. 1029_0019
`
`
`
`
`
`
`
`
`