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
`
`
`
`
`
`gt.
`Fr‘
`ti
`re‘1*
`
`
`
`
`
`__,_4..4*?’_Ia5*'b?,'$.’,‘e_,'13‘,JK'C..;"-.195;N
`
`VALEO EX. 1029_002
`
`

`

`Published by
`
`IEEE Computer Society Press
`10662 Los Vaqueros Circle
`P.0. Box 3014
`Los Alamitos. CA 90720-1264
`
`Copyright © 1990 by the institute of Electrical and Electronics Engineers, inc.
`
`Cover credit: Raziel's Transformation Sequence from Willow.
`Courtesy of Industrial Light 8. Magic, a Division of Lucastiim Ltd.
`© 1989 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
`Custnmar Service center
`10552 Los ilaquarn: circle
`P.D. Bnx3i|1-1
`
`Lu: A|Imiin3,CA B0320-1264
`
`IEEE Computer Society
`13, Avenue de |'Aqui|on
`B-1200 Brussels
`BELGIUM
`
`IEEE Computer Society
`Ooshima Building
`2-19-1 Minami-Aoyama.
`Minato-Ku
`
`IEEE Service Center
`4:15 Hoes Lane
`P.0. Box 1331
`Piscataway. NJ 08355-1331
`
`Tokyo 107'. JAPAN
`
`'.—
`2
`
`
`
`--4::-'.::a-2-.u-«-.;.c-:-at-,+-.-.
`
`5‘.
`
`
`
`VALEO EX. 1029_003
`
`

`

`
`
`HO.
`
`3 source.
`
`>r private
`f the first
`Jopyright
`'m|tted 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-
`1960s 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. Furthemiore, these textbooks rarely present image warping concepts as a single
`body of lcnowledge. 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
`transformation 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 approximations. 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
`
`
`
`
`
`
`
` 4,__
`
`.,..o-.q.......,-..u-l“‘dvmu_
`
`
`
`,.-............,_.-
`
`
`
`
`
`
`
`‘.1-"'-=-'."a"“-1-AA,.~..e; _-
`
`VALEO EX. 1029_005
`
`

`

`vii
`
`results are particularly useful for both hardware and software realizations of geometric
`transfonnations. 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
`
`_-_.-,..,
`
`
`
`1‘_:';;,{-<_:.-:.--p'.\‘'.‘L3.7:‘
`
`tiny
`rent
`
`this
`
`eers
`
`iing
`I1 to
`has
`ined
`
`g is
`cus-
`
`eory
`con—
`aas.
`
`etric
`
`aper,
`pinginto
`ICISG
`sam-
`
`:hose
`ation
`The
`tacti-
`ment
`
`lish a
`ntext
`
`ented
`
`zptllal
`1 and
`
`alogy,
`2. As
`
`patial
`their
`ns, as
`ts are
`
`:work
`esam-
`
`iscus—
`sed to
`Fast
`These
`
`
`
`VALEO EX. 1029_006
`
`

`

`Ming
`go to
`I1 HU
`‘or his
`.g this
`
`to Ed
`minal
`Ed the
`Heck
`Peter
`lrgam
`ed the
`b a lot
`
`_
`mdlng
`by tfhe
`ft" °"
`. ware
`’’‘’“515’
`
`1' 1°"3-
`ok was
`=0 tbs
`
`_
`
`'
`3.
`"
`.
`
`.
`
`;
`
`1
`
`-
`
`~
`
`*.
`
`;.
`§
`
`'
`
`CHAPTER 1
`
`Z
`
`.
`
`CHAPTER 2
`
`_
`
`TABLE OF CONTENTS
`
`INTRODUCTION
`1.1 BACKGROUND
`1.2 OVERVIEW
`1.2.1 SpaIiaI Transformations
`1.2.2 Sampling Theory
`1.2.3 Resampling
`1.2.4 Aliasing
`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 Disscctors
`2.3.2 So1id—State Sensors
`2.3.2.1 CCD Cameras
`2.3.2.2 CID Cameras
`2.3.3 Mechanical Scanners
`2.4 VIDEO DIGITIZERS
`2.5 DIGITIZED IMAGERY
`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
`48
`
`xi
`
`
`
`VALEO EX. 1029_007
`
`

`

`E I
`
`I11
`
`g
`1.
`‘A
`
`D
`5
`W"
`‘
`
`.
`)
`;
`
`‘
`
`,
`
`a
`§
`
`'
`-.
`E
`4
`
`49
`49
`
`49
`50
`50
`50
`52
`52
`53
`54
`56
`56
`57
`58
`
`59
`60
`60
`61
`63
`64
`65
`67
`70
`75
`75
`77
`78
`73
`80
`31
`81
`84
`85
`86
`87
`88
`91
`92
`
`95
`95
`96
`99
`
`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 PERSPECTIVE TRANSFORMATIONS
`3.4.1 Inverse
`3.4.2 Inferring Perspective Transformations
`3.4.2.1 Case 1: Square—to-Quadriiateral
`3.4.2.2 Case 2: Quadri1ateraI—to—Square
`3.4.2.3 Case 3: Quadrilateral-to—Quadri1atera1
`3.5 BILINEAR TRANSFORMATIONS
`3.5.1 Biiinear\I‘nterpo1ation
`
`3.5.2 Separability
`3.5.3 Inverse
`3.5.4 Interpolation Grid
`3.6 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—Squa.res 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.74 Linear Triangular Patches
`3.7.5 Cubic Tiiangular Patches
`3.8 GLOBAL SPLINES
`3.8.1 Basis Functions
`3.8.2 Regularization
`3.8.2.1 Giimson, 1981
`3.8.2.2 Terzopouios, 1984
`3.8.2.3 Discontinuity Detection
`3.8.2.4 Boult and Kender, 1986
`3.8.2.5 A Definition of Srnoothness
`3.9 SUMMARY
`
`CHAPTER 4 SAMPLING THEORY
`4.1 INTRODUCTION
`4.2 SAMPLING
`4.3 RECONSTRUCTION
`4.3.1 Reconstruction Conditions
`
`1
`,
`
`I
`
`.
`
`3;:
`‘
`
`
`
`VALEO EX. 1029_008
`
`

`

`
`
`..-«._'_.j_._‘______,.,.,._.,..._-_...——._—.w%q .
`
`
`
`
`
`\
`
`i_
`E
`_
`E
`
`.
`fl
`91
`‘
`3
`
`4.3.2 Ideal Low-Pass Filter
`4.3.3 Sine Function
`
`4.4 NONIDEAL RECONSTRUCTION
`4.5 ALIASING
`
`4.6 ANTIALIASING
`4.7 SUMMARY
`
`CHAPTER 5
`
`IMAGE RESAMPLING
`5.1 INTRODUCTION
`
`5.2 IDEAL IMAGE RESAMPLING
`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—Sp1ines
`5.4.6 Windowed Sine Function
`
`5.4.6.1 Ham 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 IMPLEl’vIENTA'I‘ION
`
`5.6.1 Interpolation with Coefficient Bins
`5.6.2 Fant’s Resampling Algorithm
`5.7 DISCUSSION
`
`CHAPTER 6 ANTIALIASING
`6.1
`INTRODUCTION
`
`6.1.1 Point Sampling
`6.1.2 Area Sampling
`6.1.3 Space—Invariant Filtering
`6.1.4 Space—Van'a.nt Filtering
`6.2 REGULAR SAMPLING
`
`6.2.1 Supersampling
`6.2-2 Adaptive Supersampling
`6.2.3 Reconstruction from Regular Samples
`6.3 IRREGULAR SAMPLING
`6.3.1 Stochastic Sampling
`
`xiii
`
`I00
`101
`103
`106
`I08
`112
`
`117
`I17
`119
`124
`126
`126
`127
`129
`131
`133
`134
`136
`I37
`139
`140
`141
`142
`I43
`145
`147
`150
`150
`153
`160
`
`163
`163
`163
`166
`168
`168
`168
`168
`169
`171
`173
`173
`
`49
`49
`49
`50
`50
`S0
`52
`52
`53
`54
`56
`56
`57
`58
`59
`60
`60
`
`63
`
`65
`67
`70
`75
`75
`77
`78
`78
`80
`
`84
`85
`86
`
`91
`92
`
`95
`95
`96
`
`99
`99
`
`
`
`VALEO EX. 1029_009
`
`

`

`xiv
`
`6.3.2 Poisson Sampling
`6.3.3 Jittered 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 Newell, 1976
`
`6.4.3 Feibush, Levoy, and Cook, 1980
`6.4.4 Gangnet, Pemy, and Coueignoux, 1932
`6.4.5 Greene and I-Ieckbert, 1986
`6.5 PREFILTERING
`
`6.5.1 Pyramids
`6.5.2 Summed-Area Tables
`
`6.6 FREQUENCY CLAMPING
`6.7 ANTIALIASED LINES AND TEXT
`6.8 DISCUSSION
`
`174
`175
`176
`177
`177
`178
`178
`178
`178
`179
`179
`181
`
`181
`183
`184
`184
`185
`
`CHAPTER 7
`
`SCANLINE ALGORITHMS
`7.1 INTRODUCTION
`
`
`
`
`
`-c.=:-age-.7...._.-“'-r-4_.--,..-.--§_...¢._,,
`
`2,-.»'...w.1:..,,._,.,__-_._-.
`
`
`anaemia-figakaa.-.m9~w»-1‘:.-:.,g..;,_;_;‘.-.,...A.-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`7.4.1.3 2-Pass Algorithm
`
`
`7.4.1.4 An Example: Rotation
`
`
`7.4.1.5 Another Example: Perspective
`
`
`7.1.1 Forward Mapping
`7.1.2 Inverse Mapping
`7.1.3 Separable Mapping
`7.2 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 Marino, 1980
`7.3.2 Weiman, 1980
`7.3.3 Catmull and Smith, 1980
`7.3.4 Paeth, 1986lTat1aka, et. a1., 1986
`7.3.5 Cordic Algorithm
`7.4 2-PASS TRANSFORMS
`7.4.1 Catmull and Smith, 1980
`7.4.1.1 First Pass
`7.4.1.2 Second Pass
`
`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
`
`
`
`
`
`VALEO EX. 1029_0010
`
`

`

`
`
`
`
`
`
`XV
`
`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 Lookup Tables: Wolberg and Boult, 1989
`242
`7.7 SEPARABLE IMAGE WARPING
`242
`7.7.1 Spatial Lookup Tables
`244
`187
`7.7.2 Intensity Resampling
`244
`188
`7.7.3 Coordinate Resampling
`245
`188
`7.7.4 Distortions and Errors
`245 ,
`188
`7.7.4.1 Filtering Errors
`246
`188
`7.7.4.2 Shear
`246
`189
`7.7.4.3 Perspective
`248
`189
`7.7.4.4 Rotation
`248
`190
`7.7.4.5 Distortion Measures
`248
`191
`7.7.4.6 Bottleneck Distortion
`250
`196
`7.7.5 Foldover Problem
`25 1
`197
`7.7.5.1 Representing Foldovers
`251
`199
`7.7.5.2 Tracking Foldovers
`252
`201
`7.7.5.3 Storing Information From Foldovers
`253
`205
`7.7.5.4 Intensity Resampling with Foldovers
`254
`205
`7.7.6 Cornpositor
`254
`206
`7.7.7 Examples
`254
`206
`7.8 DISCUSSION
`260
`208
`212
`
` CHAPTER 8 EPILOGUE
`214
`215
` APPENDIX 1 FAST FOURIER TRANSFORMS
`215
`A1.1 DISCRETE FOURIER TRANSFORM
`215
`A1.2 DANIELSON-LANCZOS LEMMA
`
`
`217
`A1.2.1 Butterfly Flowpraph
`
`217
`Al.2.2 Putting It All Together
`218
` A1.2.3 Recursive FFI‘ Algorithm
`
`266
`267
`269
`270
`
`174
`175
`176
`177
`177
`178
`178
`178
`178
`179
`179
`181
`181
`
`183
`184
`184
`185
`
`_
`=_;
`
`‘
`
`33.
`'
`
`‘_
`1;":
`
`*3
`%
`%
`
`
`
`VALEO EX. 1029_0011
`
`

`

`xvi
`
`A1.2.4 Cost of Computation
`A13 COOLEY—TUKEY ALGORITHM
`
`\
`
`A1.3.1 Computational Cost
`A1.4 COOLEY—SANDE ALGORITHM
`A1.5 SOURCE CODE
`
`A1.5.I Recursive FFI‘ Algorithm
`A1.5.2 Cooley-Tukey FF1‘ Algorithm
`
`APPENDIX 2 INTERPOLATING CUBIC SPLINES
`A2.1 DEFINITION
`A22 CONSTRAINTS
`A2.3 SOLVING FOR THE SPLINE COEFFICIENTS
`
`A2.3.1 Derivation of A 2
`A2.3.2 Derivation of A 3
`A2.3.3 Derivation of A 1 and A 3
`A24 EVALUTING THE UNKNOWN DERIVATIVES
`A2.4.1 First Derivatives
`A2.4.2 Second Derivatives
`
`A2.4.3 Boundary Conditions
`A25 SOURCE CODE
`
`A2.5.1 Ispline
`A25 .2 Isp1ine_gen
`
`APPENDIX 3 FORWARD DIFFERENCE METHOD
`
`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
`
`:
`
`I
`
`if
`
`35;
`‘‘‘!<‘
`i;
`;
`
`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 rransfonmztion 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 tertns “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 scaled, 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 perfonn 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
`
`

`

`VALEO EX. 1029_0014
`
`

`

`
`
`Figure 1.2: Viking Lander 2 image after distortion correction [Green 89].
`
`Image warping is a problem that arises in computer graphics as well. However, 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 2-D "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 @1939 Van Nosu-and Reinhold. Reprinted by
`Dizital Image Procesxing:
`Permission of the Publisher. All Rights Reserved,
`
`from the
`the U.S.
`
`ggressive
`onmental
`i’ this ini-
`vemment
`
`g and sur-
`
`ges of the
`-, the task
`
`zsponding
`)ccur due
`time but
`.ens aber-
`it various
`well.
`
`hese dis-
`ale. This
`
`ce points
`and land-
`
`resenting
`tained by
`r polyno-
`.1 effects.
`
`ing func-
`egion to
`g.
`
`i in Figs.
`viewing
`'5 in Sep-
`pacecraft
`oblem is
`nsforma—
`
`:r related
`
`instance,
`ation for
`
`dye are
`:, known
`n. Since
`
`zing pro-
`mnation
`
`
`
`
`
`VALEO EX. 1029_0015
`
`

`

`VALEO EX. 1029_0016
`
`

`

`1.1 BACKGROUND
`
`5
`
`esting visual
`rat depicts a
`ncers. Other
`
`Ont COVBI, ES
`
`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 perrnission from Algorithms for Graphics and Image Processing, edited by Theo
`Pavlirlis. 1982. Copyright ©1982 by Computer Science Press, Rockville, MD. All rights reserved.
`
`dancers.
`
`warping has
`tal hardware.
`th the advent
`
`llld. improved
`an towards a
`
`in the recent
`
`IU*--I|IIw'¢&nI*u-—'Ia.nu:.Vtn-nu-wu».a-..\..a..
`
`
`
`-..z,._.-A.
`
`
`
`VALEO EX. 1029_0017
`
`

`

`-:"..-
`
`e3,5.
`
`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 transfonnafions, 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 completely
`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.
`
`
`
`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,
`shniques, partic-
`ghting the com-
`.ect of a separate
`We begin with
`
`iordinate system
`a mapping func-
`input and output
`:s the value of its
`
`' using the spatial
`ut image.
`
`notions may take
`' analytic expres-
`nrnations. More
`
`tnalytic terms can
`2c-rrespondence is
`nts are evaluated
`
`s a dense grid of
`ny arbitrary map-
`
`is completely
`un
`espect to the 2-D
`:rest. The objects
`ttly, three coordi-
`creen space. The
`:o infer them, are
`
`«dike:-:11’-r‘-I"&rw-"»'-~.-w44,--
`
`12 ovsnvrnw
`
`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 resarnple 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
`
`

`

`8
`
`rrrrnonucrron
`
`The accuracy of interpolation has significant impact on the quality of the output
`image. As a result, many interpolation functions have been studied from the viewpoints
`of both computational efficiency and approximation quality. Popular interpolation func- I
`tions include cubic convolution, bilinear, and nearest neighbor. They can exactly recon-
`struct second-,
`first—, and zero—degree polynomials, respectively. More expensive and
`accurate methods include cubic spline interpolation and convolution with a sine function.
`Using sampling theory, this last choice can be shown to be the ideal filter. However, it
`cannot be realized using a finite number of neighboring elements. Consequently, the
`alternate proposals have been given to offer reasonable approximations.
`Image resarn-
`pling and reconstruction are described in Chapter 5.
`
`1.2.4. Aliasing
`
`Through image reconstruction, we have solved the first problem that arises due to
`operating in the discrete domain — sampling a discrete input. Another problem now
`arises in evaluating the discrete output. The problem, related to the resarnpling stage, is
`described below.
`
`
`
`
`The output image, as described earlier, has been generated by point sampling the
`reconstructed input. Point (or zero—spread) sampling refers to an ideal sampling process
`in which the value of each sampled po