wolberg@cs (08/03/90)
A new book entirely devoted to image warping will be made available at SIGGRAPH:
George Wolberg, "Digital Image Warping", IEEE Computer Society Press, 1990.
The book is the first of its kind to be entirely devoted to geometric
transformation techniques for digital images. It has over 30 pages of color images
illustrating various concepts in spatial transformations, sampling theory,
image reconstruction, antialiasing, scanline algorithms, and more. It also describes
the warping algorithm used by Industrial Light & Magic (ILM, a division of Lucasfilm)
in several motion pictures, including Willow, Indiana Jones and the Last Crusade, and
The Abyss. C code and many illustrations are used throughout the book to reinforce the
reader's understanding. If you're interested, check it out at the IEEE Computer Society
Press booth at SIGGRAPH. Here's the table of contents:
TABLE OF CONTENTS
CHAPTER 1 INTRODUCTION 1
1.1 BACKGROUND 1
1.2 OVERVIEW 6
1.2.1 Spatial Transformations 6
1.2.2 Sampling Theory 7
1.2.3 Resampling 7
1.2.4 Aliasing 8
1.2.5 Scanline Algorithms 9
1.3 CONCEPTUAL LAYOUT 10
CHAPTER 2 PRELIMINARIES 11
2.1 FUNDAMENTALS 11
2.1.1 Signals and Images 11
2.1.2 Filters 14
2.1.3 Impulse Response 15
2.1.4 Convolution 16
2.1.5 Frequency Analysis 19
2.1.5.1 An Analogy to Audio Signals 19
2.1.5.2 Fourier Transforms 20
2.1.5.3 Discrete Fourier Transforms 26
2.2 IMAGE ACQUISITION 28
2.3 IMAGING SYSTEMS 32
2.3.1 Electronic Scanners 32
2.3.1.1 Vidicon Systems 33
2.3.1.2 Image Dissectors 34
2.3.2 Solid-State Sensors 35
2.3.2.1 CCD Cameras 35
2.3.2.2 CID Cameras 36
2.3.3 Mechanical Scanners 36
2.4 VIDEO DIGITIZERS 37
2.5 DIGITIZED IMAGERY 38
2.6 SUMMARY 40
CHAPTER 3 SPATIAL TRANSFORMATIONS 41
3.1 DEFINITIONS 42
3.1.1 Forward Mapping 42
3.1.2 Inverse Mapping 44
3.2 GENERAL TRANSFORMATION MATRIX 45
3.2.1 Homogeneous Coordinates 46
3.3 AFFINE TRANSFORMATIONS 47
3.3.1 Translation 48
3.3.2 Rotation 49
3.3.3 Scale 49
3.3.4 Shear 49
3.3.5 Composite Transformations 50
3.3.6 Inverse 50
3.3.7 Inferring Affine Transformations 50
3.4 PERSPECTIVE TRANSFORMATIONS 52
3.4.1 Inverse 52
3.4.2 Inferring Perspective Transformations 53
3.4.2.1 Case 1: Square-to-Quadrilateral 54
3.4.2.2 Case 2: Quadrilateral-to-Square 56
3.4.2.3 Case 3: Quadrilateral-to-Quadrilateral 56
3.5 BILINEAR TRANSFORMATIONS 57
3.5.1 Bilinear Interpolation 58
3.5.2 Separability 59
3.5.3 Inverse 60
3.5.4 Interpolation Grid 60
3.6 POLYNOMIAL TRANSFORMATIONS 61
3.6.1 Inferring Polynomial Coefficients 63
3.6.2 Pseudoinverse Solution 64
3.6.3 Least-Squares With Ordinary Polynomials 65
3.6.4 Least-Squares With Orthogonal Polynomials 67
3.6.5 Weighted Least-Squares 70
3.7 PIECEWISE POLYNOMIAL TRANSFORMATIONS 75
3.7.1 A Surface Fitting Paradigm for Geometric Correction 75
3.7.2 Procedure 77
3.7.3 Triangulation 78
3.7.4 Linear Triangular Patches 78
3.7.5 Cubic Triangular Patches 80
3.8 GLOBAL SPLINES 81
3.8.1 Basis Functions 81
3.8.2 Regularization 84
3.8.2.1 Grimson, 1981 85
3.8.2.2 Terzopoulos, 1984 86
3.8.2.3 Discontinuity Detection 87
3.8.2.4 Boult and Kender, 1986 88
3.8.2.5 A Definition of Smoothness 91
3.9 SUMMARY 92
CHAPTER 4 SAMPLING THEORY 95
4.1 INTRODUCTION 95
4.2 SAMPLING 96
4.3 RECONSTRUCTION 99
4.3.1 Reconstruction Conditions 99
4.3.2 Ideal Low-Pass Filter 100
4.3.3 Sinc Function 101
4.4 NONIDEAL RECONSTRUCTION 103
4.5 ALIASING 106
4.6 ANTIALIASING 108
4.7 SUMMARY 112
CHAPTER 5 IMAGE RESAMPLING 117
5.1 INTRODUCTION 117
5.2 IDEAL IMAGE RESAMPLING 119
5.3 INTERPOLATION 124
5.4 INTERPOLATION KERNELS 126
5.4.1 Nearest Neighbor 126
5.4.2 Linear Interpolation 127
5.4.3 Cubic Convolution 129
5.4.4 Two-Parameter Cubic Filters 131
5.4.5 Cubic Splines 133
5.4.5.1 B-Splines 134
5.4.5.2 Interpolating B-Splines 136
5.4.6 Windowed Sinc Function 137
5.4.6.1 Hann and Hamming Windows 139
5.4.6.2 Blackman Window 140
5.4.6.3 Kaiser Window 141
5.4.6.4 Lanczos Window 142
5.4.6.5 Gaussian Window 143
5.4.7 Exponential Filters 145
5.5 COMPARISON OF INTERPOLATION METHODS 147
5.6 IMPLEMENTATION 150
5.6.1 Interpolation with Coefficient Bins 150
5.6.2 Fant's Resampling Algorithm 153
5.7 DISCUSSION 160
CHAPTER 6 ANTIALIASING 163
6.1 INTRODUCTION 163
6.1.1 Point Sampling 163
6.1.2 Area Sampling 166
6.1.3 Space-Invariant Filtering 168
6.1.4 Space-Variant Filtering 168
6.2 REGULAR SAMPLING 168
6.2.1 Supersampling 168
6.2.2 Adaptive Supersampling 169
6.2.3 Reconstruction from Regular Samples 171
6.3 IRREGULAR SAMPLING 173
6.3.1 Stochastic Sampling 173
6.3.2 Poisson Sampling 174
6.3.3 Jittered Sampling 175
6.3.4 Point-Diffusion Sampling 176
6.3.5 Adaptive Stochastic Sampling 177
6.3.6 Reconstruction from Irregular Samples 177
6.4 DIRECT CONVOLUTION 178
6.4.1 Catmull, 1974 178
6.4.2 Blinn and Newell, 1976 178
6.4.3 Feibush, Levoy, and Cook, 1980 178
6.4.4 Gangnet, Perny, and Coueignoux, 1982 179
6.4.5 Greene and Heckbert, 1986 179
6.5 PREFILTERING 181
6.5.1 Pyramids 181
6.5.2 Summed-Area Tables 183
6.6 FREQUENCY CLAMPING 184
6.7 ANTIALIASED LINES AND TEXT 184
6.8 DISCUSSION 185
CHAPTER 7 SCANLINE ALGORITHMS 187
7.1 INTRODUCTION 188
7.1.1 Forward Mapping 188
7.1.2 Inverse Mapping 188
7.1.3 Separable Mapping 188
7.2 INCREMENTAL ALGORITHMS 189
7.2.1 Texture Mapping 189
7.2.2 Gouraud Shading 190
7.2.3 Incremental Texture Mapping 191
7.2.4 Incremental Perspective Transformations 196
7.2.5 Approximation 197
7.2.6 Quadratic Interpolation 199
7.2.7 Cubic Interpolation 201
7.3 ROTATION 205
7.3.1 Braccini and Marino, 1980 205
7.3.2 Weiman, 1980 206
7.3.3 Catmull and Smith, 1980 206
7.3.4 Paeth, 1986/ Tanaka, et. al., 1986 208
7.3.5 Cordic Algorithm 212
7.4 2-PASS TRANSFORMS 214
7.4.1 Catmull and Smith, 1980 215
7.4.1.1 First Pass 215
7.4.1.2 Second Pass 215
7.4.1.3 2-Pass Algorithm 217
7.4.1.4 An Example: Rotation 217
7.4.1.5 Another Example: Perspective 218
7.4.1.6 Bottleneck Problem 219
7.4.1.7 Foldover Problem 220
7.4.2 Fraser, Schowengerdt, and Briggs, 1985 221
7.3.3 Smith, 1987 221
7.5 2-PASS MESH WARPING 222
7.5.1 Special Effects 222
7.5.2 Description of the Algorithm 224
7.5.2.1 First Pass 225
7.5.2.2 Second Pass 228
7.5.2.3 Discussion 228
7.5.3 Examples 230
7.5.4 Source Code 233
7.6 MORE SEPARABLE MAPPINGS 240
7.6.1 Perspective Projection: Robertson, 1987 240
7.6.2 Warping Among Arbitrary Planar Shapes: Wolberg, 1988241
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 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 261
APPENDIX 1FAST FOURIER TRANSFORMS 265
A1.1 DISCRETE FOURIER TRANSFORM 266
A1.2 DANIELSON-LANCZOS LEMMA 267
A1.2.1 Butterfly Flow Graph 269
A1.2.2 Putting It All Together 270
A1.2.3 Recursive FFT Algorithm 272
A1.2.4 Cost of Computation 273
A1.3 COOLEY-TUKEY ALGORITHM 274
A1.3.1 Computational Cost 275
A1.4 COOLEY-SANDE ALGORITHM 276
A1.5 SOURCE CODE 278
A1.5.1 Recursive FFT Algorithm 279
A1.5.2 Cooley-Tukey FFT Algorithm 281
APPENDIX 2INTERPOLATING CUBIC SPLINES 283
A2.1 DEFINITION 283
A2.2 CONSTRAINTS 284
A2.3 SOLVING FOR THE SPLINE COEFFICIENTS 285
A2.3.1 Derivation of $A sub 2$ 285
A2.3.2 Derivation of $A sub 3$ 286
A2.3.3 Derivation of $A sub 1$ and $A sub 3$ 286
A2.4 EVALUTING THE UNKNOWN DERIVATIVES 287
A2.4.1 First Derivatives 287
A2.4.2 Second Derivatives 288
A2.4.3 Boundary Conditions 289
A2.5 SOURCE CODE 290
A2.5.1 Ispline 290
A2.5.2 Ispline_gen 293
APPENDIX 3FORWARD DIFFERENCE METHOD 297
REFERENCES 301
INDEX 315
--
-----------------------------------------------
George Wolberg
Department of Computer Science
Columbia Universitymarkv@gauss.Princeton.EDU (Mark VandeWettering) (08/04/90)
In article <1990Aug3.094410.11616@cs.columbia.edu> wolberg@cs () writes:
[ the table of contents from (his?) book on image transformation ]
Wow! A topic near and dear to my heart. My pocketbook is already breaking!
Between the Foley, Van Dam et. al, Graphics Gems, and this, I should have
LOTS of interesting reading.
Computer graphics is slowly moving from "wizardry" to "documented wizardry".
The books that have come out recently are much better than the ones listed
in the FAQ posting. Perhaps we should have vote for what books we like,
and post the results in FAQ.
Markjef@well.sf.ca.us (Jef Poskanzer) (09/04/90)
In the referenced message, Mark VandeWettering wrote: } Perhaps we should have vote for what books we like, }and post the results in FAQ. Sounds good to me, if by "vote" you mean send suggested listings to me and I put them in the posting. The only reason for the out-of-date books in the FAQ posting is that those are the only books people have suggested. --- Jef Jef Poskanzer jef@well.sf.ca.us {ucbvax, apple, hplabs}!well!jef Some assembly required.