Google

[preface] | [table of contents] | [how to order]

DIGITAL IMAGE WARPING

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 traditionally 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 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.


DIGITAL IMAGE WARPING

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-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


DIGITAL IMAGE WARPING

How to Order

You can order your copy of Digital Image Warping by sending a check or money order for $60 to:
Prof. George Wolberg
Dept. of Computer Science
City College of New York
138th St. at Convent Ave., Rm. R8/206
New York, NY  10031
The price includes shipping and handling.


Back to Wolberg's Home Page