Digital image warping / George Wolberg.

Format:

Book

Author/Creator:

Wolberg, George, 1964-

Series:

IEEE Computer Society Press monograph

Language:

English

Subjects (All):

Image processing--Digital techniques.

Image processing.

Imaging systems--Image quality.

Imaging systems.

Fourier transformations.

Sampling (Statistics).

Digital filters (Mathematics).

Algorithms.

Physical Description:

xvi, 318 pages : illustrations (some color) ; 27 cm.

Place of Publication:

Los Alamitos, Calif. : IEEE Computer Society Press, [1990]

Contents:

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

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

Chapter 3 Spatial Transformations 41

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

Chapter 4 Sampling Theory 95

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

Chapter 5 Image Resampling 117

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

Chapter 6 Antialiasing 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

Chapter 7 Scanline Algorithms 187

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

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.2 Constraints 284

A2.3 Solving for the Spline Coefficients 285

A2.3.1 Derivation of A[subscript 2] 285

A2.3.2 Derivation of A[subscript 3] 286

A2.3.3 Derivation of A[subscript 1] and A[subscript 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.

Notes:

Includes bibliographical references (pages 301-314) and index.

"IEEE catalog number EH0322-8"--T.p. verso.

"IEEE Computer Society Press order number 1944"--T.p. verso.

ISBN:

0818689447

0818659440

OCLC:

22620363