`Valeo v. Magna
`IPR2015-____
`
`VALEO EX. 1027_001
`
`
`
`DIGITAL IMAGE WARPING
`
`George Wolberg
`
`'
`
`L
`E
`
`Department 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
`
`
`
`Publlshed by
`
`IEEE Computer Society Press
`10862 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: Raziei's Transformation Sequence from Vl/iliow.
`Courtesy of Industrial Light a Magic, 3 Division of Lucastilrn Ltd.
`© 1983 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 iimits 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 indlcated in the code ls 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:
`
`
`
`‘
`
`‘
`_
`J;
`1.1m
`'3
`
`IEEE computer Society Press
`Customer Sunrise center
`10562 Loo Vaquerns Circle
`Ito. Box aim
`Lo: Alumina,“ 00320-1264
`
`IEEE Computer Society
`13, Avenue de I'Aquilon
`8-1200 Brussels
`BELGIUM
`
`IEEE Computer Society
`Ooshima Building
`2-19—1 Minami—Aoyema.
`Mlnato—Ku
`Tokyo 107. JAPAN
`
`iEEE Service Center
`445 Hoes Lane
`FLO. Box 1331
`Piscatawey. NJ 033551331
`
`-‘n‘l-fl‘rmmmo‘wi.3
` VALEO EX. 1027_003
`
`VALEO EX. 1027_003
`
`
`
`-u—-——-
`
`"-r
`
`
`
`
`
`—=-gu—r-Hpm_vv-—rfr-
`
`_At,
`
`no.
`
`a source.
`
`)r private
`tthe first
`Sopyright
`mum to
`=or other
`as, IEEE.
`
`Center
`Lane
`1831
`385554 331
`
`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. 02
`
`VALEO EX. 1027_004
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`-..,-_;,.4»,
`we
`
`
`
`
`
`4'.‘w‘wm-‘rt-mhuus._-,.t-—w;.r.-w..-mw.;ur.’w
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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
`
`l
`
`ii
`
`
`
`32‘
`_I
`“p
`i
`i,
`
`
`
`
`
`-_‘1r‘1'm'iir-z‘
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`VALEO EX. 1027_005
`VALEO EX. 1027_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
`
`image warping a truly fascinating and enjoyable endeavor.
`
`clarifywhatmathematicalnotation sometimes obscures. This makesthestudyofdigital
`
`George Wolberg
`
`~
`
`____.7”,
`
`i
`
`{
`:
`-
`
`..
`it
`
`,
`
`
`a;
`i.
`33
`L"
`3
`
`3
`!l
`
`:
`
`3
`
`,
`
`
`
`.uar'm-w'erxr-'ow-ra:=-‘.-.'
`
`gm),
`rent
`this
`
`-
`
`‘
`
`5ch
`ling
`h to
`has
`ined
`g is
`cus-
`eory
`con—
`
`a“
`
`euic
`aper,
`
`ping
`. into
`{61'th
`sam-
`
`:hose
`
`The
`
`ation
`
`racti—
`ment
`
`lish a
`ntext
`
`ented
`
`:ptual
`i and
`
`rlogy,
`2. As
`
`patial
`their
`ns, as
`ts are
`
`:work
`esam-
`
`iscus—
`sed to
`Fast
`These
`
`VALEO EX. 1027_006
`
`VALEO EX. 1027_006
`
`
`
`riding
`go to
`II HU
`‘or his
`1g this
`
`$15:
`
`ed the
`Heck-
`Peter
`mgaret
`ed the
`b a lot
`
`.
`mdmg
`by the
`‘e‘ for
`.ftware
`”0‘15”
`
`1' 10W!
`0k was
`to the
`
`;
`1
`
`1
`2
`
`./
`
`I
`
`'
`
`‘
`I.
`
`.
`
`.
`
`.
`
`CHAPTER 1
`
`CHAPTER 2
`
`_
`
`:
`
`;
`
`'1;
`'1
`I;
`%
`
`.
`
`CHAPTER 3
`
`TABLE OF CONTENTS
`
`INTRODUCTION
`1.1 BACKGROUND
`1.2 OVERVTEW
`1.2.1 Spatial Transfonnations
`
`1.2.2 Sampling Theory
`
`1.2.3 Resampling
`1.2.4 Aliasing
`1.25 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 C1D Cameras
`2.3.3 Mechanical Scanners
`2.4 VIDEO DIGITIZERS
`2.5 DIGITIZED IMAGERY
`2.6 SUMMARY
`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
`
`1
`
`1
`1
`6
`6
`
`7
`
`7
`8
`9
`10
`
`11
`ll
`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
`
`xi
`
`VALEO EX. 1027_007
`
`VALEO EX. 1027_007
`
`
`
`xii
`
`\
`
`.
`
`.
`
`3.3.2 Rotation
`3.3.3 Scale
`
`49
`
`49
`
`,
`
`3.3.4 Shea:
`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 2zQuadriiatera1—to-Square
`
`3.5 BILINEAR TRANSFORMATIONS
`
`3.4.2.3 Case 3: Quadfilateral-to—Quadrilateral
`3.5.1 Bilinearliiterpolation
`
`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—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 Grimson,1981
`3.8.2.2 Terzopoulos,1984
`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
`
`49
`50
`50
`50
`52
`52
`53
`54
`56
`
`57
`
`56
`58
`
`59
`60
`60
`61
`63
`64
`65
`67
`70
`75
`75
`77
`78
`78
`so
`31
`81
`84
`85
`86
`87
`88
`91
`92
`
`i
`
`I
`
`3
`1.
`"
`
`J
`‘
`
`1
`3
`5
`
`3
`
`i
`i
`l
`3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`‘
`
`1;?
`
`3
`
`
`3
`'1
`3
`
`3
`3
`
`5?"
`
`
`
`
`
`
`
`CHAPTER 4 SAMPLING THEORY
`4.1 INTRODUCTION
`4.2 SAMPLING
`4.3 RECONSTRUCTION
`4.3.1 Reconstruction Conditions
`
`95
`95
`96
`99
`
`
`
`
`
`
`
`wa.—.-r.r..—..___.V
`'-
`
`VALEO EX. 1027_008
`VALEO EX. 1027_008
`
`
`
`
`
`~.__,__mm.__,.___...m...
`
`CHAPTER 5
`
`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
`
`IMAGE RESAMPLING
`5.1 INTRODUCTION
`5.2 IDEAL IMAGE RESAMPLING
`5.3 INTERPOLATION
`5.4 INTERPOLA'IION 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 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 INTERPOLATION METHODS
`5.6 IMPLEMENTATION
`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-Variant 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
`
`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
`61
`63
`
`65
`67
`70
`75
`75
`77
`78
`78
`SO
`81
`81
`84
`85
`86
`87
`88
`91
`92
`
`95
`95
`96
`
`99
`99
`
`VALEO EX. 1027_009
`
`VALEO EX. 1027_009
`
`
`
`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 Nowell, 1976
`
`6.4.3 Feibush, Levoy, and Cook, 1980
`6.4.4 Gangnet, Pemy, and Coaeignoux, 1982
`6.4.5 Greene and Heckbert, 1986
`6.5 PREFE'I'ERI'NG
`
`6.5.1 Pyramids
`6.5.2 Summed-Area Tables
`
`6.6 FREQUENCY CLAMPING
`6.7 AN’I‘IALIASED LINES AND TEXT
`6.8 DISCUSSION
`
`VALEO EX. 1027_010
`
`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. a1., 1986
`7.3.5 Cordic Algorithm
`7.4 2-PASS TRANSFORMS
`7.4.1 Catmnll and Smith, 1980
`7.4.1.1 First Pass
`7.4.1.2 Second Pass
`
`CHAPTER 7 SCANLINE ALGORITHMS
`7.1 INTRODUCTION
`
`7.4.1.3 2—Pass Algorithm
`7.4.1.4 An Example: Rotation
`7.4.1.5 Another Example: Perspective
`
`VALEO EX. 1027_010
`
`
`
`--‘v—a-a 1‘=I
`
`11
`i1
`
`2:
`
`if;
`
`3
`a:
`
`
`
`‘
`
`;
`1
`1.1
`
`F
`(
`1
`1
`1'
`
`1‘
`
`'__
`.i
`1
`E
`31
`J
`5",
`".
`
`;
`
`.
`
`.
`
`‘
`
`_
`
`174
`175
`175
`177
`177
`17g
`173
`178
`173
`179
`179
`181
`181
`133
`184
`134
`135
`
`137
`188
`188
`133
`188
`139
`139
`190
`191
`196
`197
`199
`201
`205
`205
`206
`206
`208
`
`212
`214
`
`215
`215
`215
`217
`217
`218
`
`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 WARPJNG
`242
`7.7.1 Spatial hookup Tables
`244
`7.7.2 Intensity Resampling
`244
`7.7.3 Coordinate Resampling
`245
`7.7.4 Distortions and Errors
`245 1
`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
`243
`7.7.4.6 Bottleneck Distortion
`250
`7.7.5 Foldover Problem
`251
`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 Compositor
`254
`7.7.7 Examples
`254
`7.8 DISCUSSION
`260
`
`CHAPTER 8 EPILOGUE
`
`APPENDIX 1 FAST FOURIER TRANSFORMS
`ALI DISCRETE FOURIER TRANSFORM
`A12 DANIELSON-LANCZOS LEMMA
`A121 Butterfly Flowpraph
`A122 Putting It All Together
`A123 Recursive FFI‘ Algorithm
`
`261
`
`265
`266
`267
`269
`270
`272
`
`.
`
`VALEO EX. 1027_011
`
`VALEO EX. 1027_011
`
`
`
`xvi
`
`A124 Cost of Computation
`A13 COOLEY—TUKEY ALGORITHM
`
`\
`
`A1.3.1 Computational Cost
`A1.4 COOLEY-SANDE ALGORITHM
`A15 SOURCE CODE
`
`A1.5.1 Recursive FFT Algorithm
`A152 Cooley-Tukey FFl‘ Algorithm
`
`APPENDIX 2 INTERPOLATING CUBIC SPLINES
`A2,! DEFINITION
`A22 CONSTRAINTS
`A23 SOLVING FOR THE SPLINE COEFFICIENTS
`
`A211 Derivation of A2
`A232 Derivation of A 3
`A233 Derivation of A 1 and A 3
`A24 EVALUTlNG THE UNKNOWN DERIVATIVES
`A2.4.1 First Derivatives
`A242 Second Derivatives
`
`t
`
`A243 Boundary Conditions
`A25 SOURCE CODE
`A251 Isplinc
`A2.5.2 IsPline_gcn
`
`APPENDIX 3 FORWARD DIFFERENCE METHOD
`
`REFERENCES
`
`273
`274
`
`275
`276
`278
`
`279
`281
`
`283
`283
`284
`285
`
`285
`286
`286
`287
`287
`288
`
`289
`290
`290
`293
`
`297
`
`:
`5
`5:
`
`9 1
`
`2
`
`INDEX
`
`7' ';
`
`_ _-—va—uh_‘.~—w,._,“.—l~_ _.,.-__...,.;W..fi._.n____,
`
`,, .__ _ _.__, 2. "__‘__
`
`-__..,,__..
`
`______‘
`
`VALEO EX. 1027_012
`VALEO EX. 1027_012
`
`
`
`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 transfonnatt’on 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.
`
`
`
`
`
`‘'nhh''-»m“Amm'rr-rnmrem'u-“ca-'-
`
`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
`
`
`
`
`‘—."""'""-""...r”A.
`-‘£.¢Wl—__'
`
`
`..vwmr-wflmneru
`
`Figure 1.2: Viking Lander 2 image after distortion conection [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 @1989 Van Nostrand Reinhold. Reprmted'
`Digital Image Pmming:
`Pmnissionef the Publisher. AllRights Reserved.
`
`by
`
`
`
`'
`
`‘2
`r
`
`‘
`
`,
`
`.
`-
`-
`;
`
`,
`'
`
`_
`
`from the
`the US.
`
`ggressive
`onmental
`1’ this ini-
`vernment
`
`; and sur-
`
`ges of the
`', the task
`
`:sponding
`)ccur due
`time but
`ens aber-
`tt various
`tell.
`
`hese dis—
`ale. This
`
`ce points
`and Iand~
`
`resenting
`tained by
`r polyno-
`n effects.
`
`ing func—
`egion to
`
`.g.
`1 in Figs.
`viewing
`‘5 in Sf313'
`pacecraft
`oblem is
`nsforrna—
`
`:1- related
`instance,
`ation for
`dye are
`a, known
`n. Since
`'
`mg pro-
`)rmation
`
` VALEO EX. 1027_015
`
`VALEO EX. 1027_015
`
`
`
`4
`
`m’rnonucrron
`
`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 [Hoizmann 88].
`
`Figure 1.3: Transformation sequence: faces —~> horse/rider -—) frogs -—> dancers.
`Copyright © 1983 Tom Brigham 1’ NYTT—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
`
`.mL»n1‘:.‘.._-L:L,...‘a‘a'3_.'.‘:.z_;e:_..rahsxu'LAL.-_.J;‘ .1 .._.
`
`, L
`
`a.
`
`"
`
`VALEO EX. 1027_016
`
`
`
`,
`f
`:
`
`‘
`
`1.1 BACKGROUND
`
`5
`
`eSting visual
`m depicts a
`ncers. Other
`ont cover, as
`
`;‘
`
`_It is.instructive at this point to illustrate the relationship between the remote sensing,
`medlcal imaging, computer v1s1on, 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 fortns of data used by the aforementioned
`fields.
`
`Image Processing
`
`Computer
`
`Graphics
`
`Computer
`
`Vision
`
`Description
`
`Scene
`
`"-14.6a _|
`
`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 tenderer 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 fi'om Algorithms for Graphics and Image Processing, edited by Theo
`Pavlidis. 1982. Copyright ©1982 by Computer Science Prms, RockVilie, MD. All rights reserved.
`
`mun-u;._.._,_.
`
`
`
`g.
`
`_,
`I
`
`dancers.
`
`.
`warping has
`t3] hardwa-TC-
`{h the advent
`md improved
`:n towards a
`
`in the recent
`
`VALEO EX. 1027_017
`
`VALEO EX. 1027_017
`
`
`
`urn-rm“.
`
`.1;«r
`
`i9
`
`
`
`'Tf‘ii”.ml'md‘m
`
`nma--i'.‘
`
`6
`
`INTRODUCTION
`
`1.2. OVERVIEW
`
`The purposr: 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, resarnpling, 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 welt. 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 transfonnations.
`
`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.
`
`
`
`.3 i. ."5- ‘..".'
`
`VALEO EX. 1027_018
`VALEO EX. 1027_018
`
`
`
`this field within
`
`:s that comprise:
`resampling, and
`is previded as a
`.sion of efficient
`
`rce to practicing
`
`transformation.
`
`tity of people in
`i terminologies,
`:hniques, partic-
`ghting the com—
`iect of a separate
`We begin with
`
`Jordinate system
`a mapping func-
`input and output
`:5 the value of its
`
`' using the spatial
`ut image.
`
`notions may take
`, analytic expres-
`mnations. More
`
`tnalytic terms can
`:orrespondence is
`nts are evaluated
`
`5 a dense grid of
`ny arbitrary map—
`
`is completely
`nn
`espect to the 2—D
`:rest. The objects
`ttly, three coordi—
`creen space. The
`:0 infer them, are
`
`Hit/VI.“
`n«yaw
`
`
`
`.*Weiu-wwr‘
`
`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 th