`Valeo v. Magna
`IPR2015-____
`
`VALEO EX. 1027_001
`
`
`
`
`
`DIGITAL IMAGE WARPING
`
`George Wolberg
`
`Depanment of Computer Science
`Columbia University
`New York
`
`®
`
`IEEE Computer Society Press
`Los Alamitos, California
`
`Washington
`
`0 Brussels
`
`0
`
`Tokyo
`
`VALEO EX. 1027_002
`
`VALEO EX. 1027_002
`
`
`
`l \ ilL
`
`{t
`i
`
`I
`'
`
`,_.—.—_—,14.,‘._
`
`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: Fiaziei's Transformation Sequence from Willow.
`Courtesy of industrial Light 8. Magic, a Division of Lucasfiim Ltd.
`© 1988 Lucasfilm 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 10017. All 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 center
`111562 Ln: ilaquarns circle
`P.Ci. Box 3014
`Lu: k|Imiin3,CA B0320-1264
`
`IEEE computer Society
`13, Avenue de i'Aquilon
`B-1200 Brussels
`BELGIUM
`
`JEEE Computer Society
`Ooshima Building
`2-19-1 Minami-Aoyama,
`Mlnato-Ku
`Tokyo 107. JAPAN
`
`IEEE Service Center
`445 Hoes Lane
`P.O. Box 1331
`Plsoataway. NJ 08355-1331
`
`VALEO EX. 1027_003
`
`VALEO EX. 1027_003
`
`
`
`
`
`
`
`..c.._...._‘__‘__.;_"_...',_',4_1..'.'.._._'_'‘'
`
`
`
`
`
`730.
`
`a source.
`
`>r private
`t the first
`Dopyrtght
`'m|tted to
`=or other
`as, IEEE.
`
`Center
`Lane
`1831
`38355-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 tnid-
`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. 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. 1027_004
`
`
`
`;
`V
`
`ii
`l
`;'
`i
`,
`i
`
`I.
`
`‘-
`
`
`11.
`
`
`
`
`
`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 wel1—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 these
`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
`
`VALEO EX. 1027_005
`VALEO EX. 1027_O05
`
`
`
`
`
`Vll
`
`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
`
`—
`
`guy
`mm '
`this
`
`5513
`fing
`h to
`has
`gned
`g is
`Cus-
`gory
`Con-
`;3_s_
`emu
`aper,
`
`?i“g
`into
`JCISC
`sam-
`
`:hose
`ation
`The
`racti—
`ment
`
`lish a
`ntext
`
`ented
`
`:ptlla1
`i and
`
`plogy,
`3. As
`
`patial
`their
`ns, as
`ts are
`
`:work
`35am-
`
`iscus—
`sed to
`Fast
`These
`
`'
`
`;
`-
`I
`
`kl
`1‘
`l
`
`T
`
`?{
`
`”
`
`F
`T
`
`«.‘.!"\~7|.-2.,’="'‘
`
`VALEO EX. 1027_006
`
`VALEO EX. 1027_006
`
`
`
`qdjng
`go to
`n I-Iu
`or his
`1g this
`
`ed the
`Heck
`Peter
`Lrgam
`
`:1t1]:
`
`_
`‘ndmg
`by the
`{cf for
`flware
`”°“513’
`
`F 10‘’3-
`0k W33
`to the
`
`A
`
`1.
`
`1
`
`.
`
`.
`
`;
`j
`‘
`:1
`1
`‘
`
`-
`
`CHAPTER 1
`
`.//
`
`TABLE OF CONTENTS
`
`INTRODUCTION
`1.1 BACKGROUND
`1.2 OVERVIEW
`1.2.1 Spatial Transformations
`1.2.2 Sampling Theory
`
`1.2.3 Resampling
`1.2.4 Aliasing
`1.2.5 Scanline Algorithms
`1.3 CONCEPTUAL LAYOUT
`
`CHAPTER 2
`
`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 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
`
`r
`1
`
`1
`
`1
`1
`6
`6
`7
`
`7
`8
`9
`10
`
`11
`
`11
`11
`14
`15
`16
`19
`19
`20
`26
`28
`32
`32
`33
`34
`35
`35
`36
`36
`37
`38
`40
`
`41
`42
`42
`44
`45
`46
`47
`48
`
`1
`
`"
`
`VALEO EX. 1027_007
`
`VALEO EX. 1027_007
`
`
`
`A
`
`3.3.2 Rotation
`3.3.3 Scale
`
`49
`49
`
`xii
`
`\
`
`9.
`
`fi1
`
`EI
`.
`A
`1
`‘-
`
`‘
`g
`1
`
`‘
`
`J
`
`_.
`.-
`
`A
`
`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
`78
`80
`81
`81
`34
`85
`86
`87
`88
`91
`92
`95
`95
`96
`99
`99
`
`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-Quadrilateral
`3.4.2.2 Case 2: Quadrilateral—to—Square
`3.4.2.3 Case 3: Quadrilateral-to—Quadri1atera1
`3.5 BIL.INEAR TRANSFORMATIONS
`
`3.5.1 BilineaITnterpo1ation
`
`L
`.
`
`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—Squanes 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.3.2 Regularization
`3.8.2.1 Gritnson, 1981
`3.8.2.2 Terzopoulos, 1934
`3.3.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
`
`VALEO EX. 1027_008
`
`VALEO EX. 1027_008
`
`’
`
`
`
`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
`
`CHAPTER 5
`
`"
`
`\
`
`g
`5
`f
`E
`'
`
`‘n
`‘
`
`:
`.
`
`4.3.2 Ideal Low-Pass Filter
`4.3.3 Sine Function
`4.4 NONIDEAL RECONSTRUCTION
`4.5 ALIASING
`4.6 ANIIALIASING
`4.7 SUMMARY
`
`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-Splines
`5.4.6 Windowed Sinc Function
`5.4.6.1 Ham: and Hamming Windows
`5.4.6.2 Blackrnan 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 INTERPOLATION 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—Inva1iant Filtering
`6.1.4 Space—Va1'iant Filtering
`6.2 REGULAR SAMPLING
`6.2.1 Supersarnpling
`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
`ll?
`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
`
`VALEO EX. 1027_009
`
`VALEO EX. 1027_009
`
`
`
`xiv
`
`5
`
`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, 1982
`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 ANFIALIASED LINES AND TEXT
`6.8 DISCUSSION
`
`;
`1
`
`1:
`
`_-
`
`‘
`
`174
`175
`176
`177
`177
`178
`178
`178
`178
`179
`179
`131
`181
`183
`184
`184
`185
`
`CHAPTER 7 SCANLINE ALGORITHMS
`7.1 INTRODUCTION
`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 Marine, 1980
`
`
`7.3.2 Weiman, 1980
`
`
`7.3.3 Catmull and Smith, 1980
`
`
`7.3.4 Paeth, 1986/ Tanaka, et. al., 1986
`
`
`7.3.5 Cordic Algorithm
`
`
`7.4 2~PASS TRANSFORMS
`
`
`7.4.1 Catrnull 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
`
`
`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. 1027_010
`VALEO EX. 1027_010
`
`
`
`
`
`174
`175
`176
`177
`177
`178
`178
`I78
`
`178
`179
`179
`181
`181
`183
`I84
`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
`218
`
`
`
`_;,~.A....*,t:r.n'..'-.».":"'n-'...<".'
`
`
`
`
`
`7.4.1.6 Bottleneck Problem
`
`XV
`
`219
`
`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
`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
`7.7.5.4 Intensity Resampling with Foldovers
`254
`7.7.6 Cornpositor
`254
`7.7.7 Examples
`254
`7.8 DISCUSSION
`260
`
`CHAPTER 8 EPILOGUE
`
`APPENDIX 1 FAST FOURIER TRANSFORMS
`A1.1 DISCRETE FOURIER TRANSFORM
`A1.2 DANIELSON-LANCZOS LEMMA
`A1.2.1 Butterfly Flowfiraph
`A1.2.2 Putting It All Together
`A123 Recursive FF1" Algorithm
`
`261
`
`265
`266
`267
`269
`270
`272
`
`VALEO EX. 1027_011
`
`VALEO EX. 1027_011
`
`
`
`xvi
`
`APPENDIX 2
`
`A1.2.4 Cost of Computation
`A13 COOLEY-TUKEY ALGORITI-IM
`
`A1.3.1 Computational Cost
`A1.4 COOLEY—SANDE ALGORITI-IM
`A1.5 SOURCE CODE
`
`A1.5.1 Recursive FFI‘ Algorithm
`A1.5.2 Cooley-Tukey FFT Algorithm
`
`INTERPOLATING CUBIC SPLINES
`A21 DEFINITION
`A2.2 CONSTRAINTS
`A23 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
`A2.S.2 Ispiine_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
`
`315
`
`
`
`
`
`VALEO EX. 1027_012
`VALEO EX. 1027_012
`
`
`
`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 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 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. 1027_013
`
`VALEO EX. 1027_013
`
`
`
`INTRODUCTION
`
` 2
`
`These projects all involved acquiring multi
`same area taken either at different times or with
`
`-image sets (i.e., multiple images of the
`different sensors). Immediately, the task
`
`VALEO EX. 1027_014
`VALEO EX. 1027_014
`
`
`
`
`
`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.
`
`’
`I
`,
`
`3
`;
`‘
`
`
`
`:',r'31'l':i'-'‘--'1-
`
`_
`
`_?
`
`3
`.
`"
`
`__
`f
`
`.1‘
`'
`
`from the
`
`the U.S.
`ggressive
`onmental
`1’ this ini—
`vemment
`g and sur-
`;es of the
`', the task
`zsponding
`JCCIJT due
`time but
`ens aber-
`Lt various
`Iell.
`
`zhese dis-
`ale. This
`
`ce points
`and land-
`
`resenting
`tained by
`r polyno-
`:1 effects.
`
`ing func-
`egion to
`
`_
`g'_
`1 1? F{g5-
`‘’_1eW1“8
`es in Sep-
`Pacacraft
`°b13m is
`"5f°"“a‘
`
`:1‘ relatcd
`instance,
`ation for
`dye are
`3, known
`n. Since
`
`ing Pro—
`mnation
`
`.
`
`.
`
`'
`
` _
`
`by W13. Green @1959 V N u d R in]-told.
`Digital Image Processing:
`permissiarnofthe Publisher. A1lRightsReserved.
`an
`O3 m E
`
`eprin
`R M by
`
`VALEO EX. 1027_015
`VALEO EX. 1027_015
`
`
`
`4
`
`rnrnonucrron
`
`I
`
`g
`'
`
`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
`transformation 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].
`
`Figure 1.3: Transformation sequence: faces —> horse/rider —> frogs ~> dancers.
`Copyright © 1983 Tom Brigham I 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. 1027_016
`VALEO EX. 1027_016
`
`
`
`,
`
`:_
`'
`
`I l
`
`i
`
`i
`
`'
`
`wing visual
`mt depicts a
`mars‘ other
`Om cover, as
`
`‘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.
`
`1.1 BACKGROUND
`
`5
`
`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 f.'rom Algorithms for Graphics and Image Processing, edited by Theo
`Pavlidis. 1932. Copyright ©1932 by Computer Science Press, Rockville, MD. All rights reserved.
`
`dancers.
`
`warping has
`I31 hardware“
`th the advent
`ind improved
`an towards a
`in the recent
`
`'
`
`.
`3
`
`5
`
`VALEO EX. 1027_017
`
`VALEO EX. 1027_017
`
`
`
`
`
`,-3:‘.-‘-.-.s"_.";-.1‘...-.
`
`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 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.
`
`
`
`6.l-Ii‘Ivna-..;g.-.».:y'gt~,-e,«-‘H_
`
`
`
`VALEO EX. 1027_018
`VALEO EX. 1027_018
`
`
`
`
`
`.-T-~-.-34
`
`5'!‘-."'T':'
`
`this field within
`
`:s that comprise
`resampling, and
`is provided as a
`.sion of efficient
`
`ICE‘. to practicing
`
`transformation.
`
`.ity of people in
`i terminologies,
`zhniques, partic-
`ghting the com-
`ect of a separate
`We begin with
`
`)ordinate system
`a mapping func-
`input and output
`:5 the value of its
`
`' using the spatial
`ut image.
`
`notions may take
`' analytic expres-
`nmations. More
`
`malytic terms can
`zorrespondence is
`nts are evaluated
`
`s a dense grid of
`ny arbitrary map-
`
`In is completely
`'espect to the 2-D
`:rest. The objects
`ltly, three coordi-
`creen space. The
`:o infer them, are
`
`
`
`-‘£:!.$1:."M'!-.~'-Kw":I;nIw...;i‘..
`
`1.2 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
`I
`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 E