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 coverage. Furthermore, these textbooks rarely present image warping concepts as a single body of knowledge. Since the presentations are usually tailored to some narrow readership, 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 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 discussion 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 consult 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 sampling 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 practical 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 resampling, including several common interpolation kernels. They are applied in the discussion 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 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 techniques 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.
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-Quadrilateral56 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, 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 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 1 FAST 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 2 INTERPOLATING 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_2 285 A2.3.2 Derivation of A_3 286 A2.3.3 Derivation of A_1 and A_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 3 FORWARD DIFFERENCE METHOD 297 REFERENCES 301 INDEX 315
Prof. George Wolberg Dept. of Computer Science City College of New York 138th St. at Convent Ave., Rm. R8/206 New York, NY 10031The price includes shipping and handling.