Digital image warping

INTRODUCTION

1.1 BACKGROUND

1.20VERVmW

1.2.1 Spatial Transformations

1.2.2 Sampling Theory

1.2.3 Resampling

1.2.4 Aliasing

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

6

7

7

9

10

11

14

16

19

26

32

33

35

36

37

40

42

44

46

48

3.3.2 Rotation

3.3.3 Scale

3.3.4 Shear

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 2: Quadrilateral-to-Square

3.4.2.3 Case 3: Quadrilateral-to-Quadrilateral

3.5 BILINEAR TRANSFORMATIONS

3.5.1 Bilinear Interpolation

3.5.2 Separability

3.5.3 Inverse

3.5.4 Interpolation Grid

3.6 POLYNOMIAL TRANSFORMATIONS

3.6.1 In ferring Polynomial Coefficients

3.6.2 Pseudoinverse Solution

3.6.3 Least-Squares With Ordinary Polynomiais

3.6.4 Least-Squares With Orthogonal Polynomials

3.6.5 Weighted Least-Squares

3.7 PIE CEWIS E POLYNOMIAL TRANS FORMATIONS

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 Regularizafion

3.8.2.1 Grimson, 1981

3.8.2.2 Terzopoulos, 1984

3.8.2.3 Discontinuity Detection

3.8.2.4 Boult and Kender, 1986

3.8.2.5 A Definition of Smoothness

3.9 SUMMARY

CHAPTER 4 SAMPLING THEORY

4.1 INTRODUCTION

4.2 SAMPLING

4.3 RECONSTRUCTION

4.3.1 Reconstruction Conditions

49

49

5O

5O

52

54

56

58

60

61

64

67

75

77

78

81

84

86

88

92

95

99

4.3.2 Ideal Low-Pass Filter

4.3.3 Sinc Function

4.4 NONIDEAL RECONSTRUCTION

4.5 ALIASING

4.6 ANTIALIASING

4.7 SUMMARY

CHAPTER $ IMAGE RESAMPLING

5.1 INTRODUCTION

5.2 IDEAL IMAGE RESAMPLING

5.3 INTERPOLATION

5.4 INTERPOLATION 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 Hann 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

100

103

108

117

119

126

127

131

134

137

140

142

145

150

153

163

163

168

168

169

173

xiv

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 Caunull, 1974

6.4.2 Blinn and Newell, 1976

6.4.3 Feibush, Levoy, and Cook, 1980

6.4.4 Gangnet, Perny, and Coueignoux, 1982

6.4.5 Greene and Heckben, 1986

6.5 PREFILTERING

6.5.1 Pyramids

6.5.2 Summed-Area Tables

6.6 FREQUENCY CLAMPING

6.7 ANTIALIASED LINES AND TEXT

6.8 DISCUSSION

CHAPTER 7 SCANLINE ALGORITHMS

7.1 INTRODUCTION

7.1.1 Forward Mapping

7.1.2 Inverse Mapping

7.1.3 Separable Mapping

7.2 INCREMENTAL ALGOR/TI-LMS

7.2.1 Texture Mapping

7.2.2 Goutand 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 Marino, 1980

7.3.2 Weiman, 1980

7.3.3 Catmull and Smith, 1980

7.3.4 Paeth, 1986/Tanaka, et. al., 1986

7.3.5 Cordic Algorithm

7.4 2-PASS TRANSFORMS

7.4.1 Catmull and Smith, 1980

7.4.1.1 First Pass

7.4.1.2 Second Pass

7.4.1.3 2-Pass Algorithm

7.4.1.4 An Example: Rotation

7.4.1.5 AnotherExample:Perspective

174

176

177

178

178

179

181

184

185

188

188

189

190

196

199

205

206

208

214

215

217

218

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

A1.2 DANIELSON-LANCZOS LEMMA

A1.2.1 Butterfly Flow Graph

A1.2.2 Putting It All Together

A1.2.3 Recursive FFTAlgorithm

265

267

270

xvi

A1.3 COOLEY-TUKEY ALGORITHM

A1.3.1 Computational Cost

A1.4 COOLEY-SANDE ALGORITHM

A1.5 SOURCE CODE

A1.5.1 Recursive FFT Algorithm

A1.5.2 Cooley-Tukey  Algorithm

APPENDIX 2 INTERPOLATING CUBIC SPLINES

A2.1 DEFINITION

A2.2 CONSTRAINTS

A2.3 SOLVING FOR THE SPLINE COEFFICIENTS

A2.3.1 Derivation of A2

A2.3.2 Derivation of A3

A2.3.3 Derivation ofA 1 and A3

A2.4 EVALUTING THE UNKNOWN DERIVATIVES

A2.4.1 First Derivatives

A2.4.2 Second Derivatives

A2.4.3 Boundary Conditions

A2.5 SOURCE CODE

A2.5.1 Ispline

A2.5.2 Ispline_gen

APPENDIX 3 FORWARD DIFFERENCE METHOD

REFERENCES

INDEX 

274

276

279

283

284

285

286

287

289

290

297

315