Digital image warping

[Rogers 90] Rogers, D.F. and J.A. Adams, Mathematical Elements for Computer

Graphics, McGraw-Hill, NY, 1990.

[Rosenfeld 82] Rosenfeld, A. and A.C. Kak, Digital Picture Processing, Vol. 2,

Academic Press, Orlando, FL, 1982.

[Sakrison 77] Sakrison, David J., "On the Role of the Observer and a Distortion Meas-

ure in Image Transmission," IEEE Trans. Comm., vol. COMM-25, no.

11, pp. 1251 - 1267, November 1977.

[Samek 86] Samek, Marcel, Cheryl Slean, and Hank Weghorst, "Texture Mapping

and Distortion in Digital Graphics," Visual Computer, vol, 3, pp. 313-

320, 1986.

[Schafer 73] Schafer, Ronald W. and Lawrence R. Rabiner, "A Digital Signal Pro-

cssing Approach to Interpolation," Proc. IEEE, vol. 61, pp. 692-702,

June 1973.

[Schowengerdt 83]

Schowengerdt, Robert A., Techniques for Image Processing and

Classification in Remote Sensing, Academic Press, Orlando, FL, 1983.

[Schreiber 85] Schreiber, William F., and Donald E. Troxel, "Transformation Between

Continuous and Discrete Representations of Images: A Perceptual

Approach," IEEE Trans. Pattern Analysis and Machine Intelligence,

vol. PAMI-7, no. 2, pp. 178-186, March 1985.

[Schreiber 86] Schreiber, William F., Fundamentals of Electronic Imaging Systems,

Springer-Verlag, Berlin, 1986.

[Shannon 48] Shannon, Claude E., "A Mathematical Theory of Communication," Bell

System Tech. J., vol. 27, pp. 379-423, July 1948, and vol. 27, pp. 623-

656, October 1948.

[Shannon 49] Shannon, Claude E., "Communication in the Presence of Noise," Proc.

Inst. Radio Eng., vol. 37, no. 1, pp. 10-21, January 1949.

[Simon 75] Simon, K.W., "Digital Image Reconstruction and Resampling for

Geometric Manipulation," Proc. IEEE Symp. on Machine Processing of

Remotely Sensed Data, pp. 3A-1-3A-11, 1975.

[Singh 79] Singh, M., W. Frei, T. Shibita, G.H. Huth, and N.E. Telfer, "A Digital

Technique for Accurate Change Detection in Nuclear Medicine Images

-- with Application to Myocardial Perfussion Studies Using Thallium

201," IEEE Trans. Nuclear Science, vol. NS-26, pp. 565-575, February

1979.

[Smith 83] Smith, Alvy Ray, "Digital Filtering Tutorial for Computer Graphics,"

inar notes, pp. 244-272, July 1983.

[Smith 87] Smith, Alvy Ray, "Planar 2-Pass Texture Mapping and Warping," Com-

puter Graphics, (SIGGRAPH '87 Proceedings), vol. 21, no. 4, pp. 263-

272, July 1987.

[Smythe 90] Smythe, Douglas B., "A Two-Pass Mesh Warping Algorithm for Object

Transfomaation and Image Interpolation," ILM Technical Memo//1030,

Computer Graphics Department, Lucasfilm Ltd., 1990.

[Stead 84] Stead, S.E., "Estimation of Gradients from Scattered Data," Rocky

Mountain J. Math., vol. 14, pp. 265-279, 1984.

[Steiner 77] Steiner, D. and M.E. Kirby, "Geometrical Referencing of Landsat

Images by Affine Transformation and Overlaying of Map Data,"

313

Photogrametria, vol. 33, pp. 41-75, 1977.

Pictorial Image Reproduction," IEEE Trans. Comm., vol. COMM-29,

no. 12, pp. 1898-i925, December 1981.

[Stxang 80] Strang, Gilbert, Linear Algebra and Its Applications, 2nd ed., Academic

Press, NY, 1980.

[Tabata 86] Tabata, Kuniaki and Haruo Takeda, "Processing Method for the Rota-

tion of an Image," U.S. Patent 4,618,991, Hitachi Ltd., October 21,

1986.

Method for Raster Image Using Skew Transfomation," Proc. IEEE

Conference on Computer Vision and Pattern Recognition, pp. 272-277,

June 1986.

[Tanaka 88] Tanaka, Atsushi and Masatoshi Kameyama, "Image Rotating System By

an Arbitrary Angle," U.S. Patent 4,759,076, Mitsubishi Denki Kabushiki

Kaisha, July 19, 1988.

[Terzopoulos 83]

Terzopoulos, Demetd, "Multilevel Computational Processes for Visual

Surface Reconstruction," Computer Vision, Graphics, and Image Pro-

cessing, vol. 24, pp. 52-96, 1983.

[Terzopoulos 84]

Terzopoalos, Demetri, Multiresolution Computation of Visible-Surface

Representations, Ph.D. Thesis, Dept. of EECS, MIT, 1984.

[Terzopoulos 85]

Terzopoulos, Demetrl, "Computing Visible Surface Representations,"

AI Lab, Cambridge, MA, AI Memo 800, 1985.

[Terzopoulos 86]

Terzopoulos, Demetri, "Regularization of Inverse Visual Problems

Involving Discontinuities," IEEE Trans. Pattern Analysis and Machine

Intelligence, vol. PAMI-8, no. 4, pp. 413-424, 1986.

[Tikhonov 77] Tikhonov, A.N. and V.A. Amenin, Solutions of Ill-Posed Problems,

Winston and Sons, Washington, D.C., 1977.

[Turkowski 82] Turkowski, Ken, "Anti-Aliasing Through the Use of Coordinate

Transfomations," ACM Trans. on Graphics, vol. 1, no. 3, pp. 215-234,

July 1982.

[Turkowski 88a] Turkowski, Ken, "Several Filters for Sample Rate Conversion,"

Technical Report No. 9, Apple Computer, Cupertino, CA, May 1988.

[Turkowski 88b] Turkowski, Ken, "The Differential Geometry of Texture Mapping,"

Technical Report No. 10, Apple Computer, Cupertino, CA, May 1988.

14 REFERENCF

[Voider 59]

[Ward 89]

[Weiman 79]

[Weiman 80]

[Whitted 80]

[Williams 83]

[Wolberg 88]

[Wolberg 89a]

[Wolberg 89b]

[Wolberg 90]

[Wong 77]

[Yellott 83]

[Ulichney 87] Ulichncy, Robert, Digital Halftoning, MIT Press, Cambridge, MA, 1987.

[Van Wie 77] Van Wie, Peter and Maurice Stein, "A Landsat Digital Image

Rectification System," IEEE Trans. Geoscience Electronics, vol. GE-15,

pp. 130-17, 1977.

Voider, Jack E., "The CORDIC Trigonometric Computing Technique,"

IRE Trans. Electron. Cornput., vol. EC-8, no. 3, pp. 330-334, September

1959.

Resizing and Rotation," Proc. SPIE Digital Image Processing Applica-

tions, vol. 1075, pp. 260-269, 1989.

Weiman, Carl F.R. and George M. Chaikin, "Logarithmic Spiral Grids

for Image Processing and Display," Computer Graphics and Image Pro-

cessing, vol. 1i, pp. 197-226, 1979.

Weiman, Carl F.R., "Continuous Anti-Aliased Rotation and Zoom of

Raster Images," Computer Graphics, (SIGGRAPH '80 Proceedings),

vol. 14, no. 3, pp. 286-293, July 1980.

Whitted, Turner, "An Improved Illumination Model for Shaded

Display," Comm. ACM, vol. 23, no. 6, pp. 343-349, June 1980.

Williams, Lance, "Pyramidal Parametrics," Computer Graphics, (SIG-

GRAPH '83 Proceedings), vol. 17, no. 3, pp. 1-11, July 1983.

Wolberg, George, "Image Warping Among Arbitrary Planar Shapes,"

New Trend$ in Computer Graphics (Proc. Computer Graphics Intl. '88),

Ed. by N. Magnenat-Thalmann and D. Thaimann, Springer-Verlag, pp.

209-218, 1988.

Wolberg, George, "Skeleton-Based Image Warping," Visual Computer,

vol. 5, pp. 95-108, i989.

Wolberg, George and Torrance E. Boult, "Image Warping with Spatial

Lookup Tables," Computer Graphics, (SIGGRAPH '89 Proceedings),

vol: 23, no. 3, pp. 369-378, July 1989.

Wolberg, George, Separable Image Warping: Implications and Tech-

niques, Ph.D. Thesis, Dept. of Computer Science, Columbia University,

NY, 1990.

Wong, Robert Y., "Sensor Transfommtion," IEEE Trans. Syst. Man

Cybern., vol. SMC-7, pp. 836-840, Dec. 1977.

Yellott, John I. Jr., "Spectral Consequences of Photoreceptor Sampling

in the Rhesus Retina," Science, vol. 221, pp. 382-385, 1983.

Adaptive supersampling, 169

Affine transformation, 47-51

incremental, 193

inferring, 50-51

inverse, 50

Aliasing, 8, 106-108

Analog-to-digital converter, 31

Antialiasing, 8, 108-111

Area sampling, i66

Bandlimited function, 97

Bartlett window, 128

Baseband, 99

Bilinear

interpolation, 58

inverse, 60

mapping, 57

separability, 59

transformation, 57-61

Blackman window, 140

Blinn, 178

Bottleneck, 219

Boult, 88, 242

Boundary conditions, 289

Box filter, 126

Braccini, 205

Briggs, 221

B-splines, 134-137

Butterfly flow graph, 269

Catmull, 178,206, 215

CCD camera, 32, 35

INDEX

CID camera, 32, 36

Comb function, 30

Control points, 63, 133

Convolution, 16-18

Convolution kemel 16

Cook, 178

Cooley-Sande algorithm, 276

Cooley-Tukey algorithm, 274

CORDIC algorithm, 185, 212-214

Coueignoux, 179

Cubic convolution, i29

Cubic splines, 133,283-296

Danielson-Lanczos lemma, 267

Decimation-in-frequency, 276

Decimation-in-time, 274

Digital image, 12

Digital image acquisition} 28

Digitization, 31

Digitizers, 28

Dirac delta function, 15

Discrete image, 12

Discrete Fourier transfom, 26-28,266

Dram scanner, 36

Elliptical weighted average filter, 179

Exponential filters, 145-146

Fant, 153

Feibush, 178

FFT, 28, 265-282

Filter, 14

315

ff 7r ii

finite impulse response, 125

infinite impulse response, 125

kernel, i6

linear, i4

low-pass, 100

mcursive, 125

response, 14

space-invariant, 14, 168

space-variant, 168

Flat-bed scanners, 36

Flying spot scanner, 32

Foldover, 220

Forward difference, 199, 297-300

Forward mapping, 42, 188

Four-comer mapping, 43

Fourier

coefficients, 22

integral, 23

series, 22

transfom, 20-26

properties, 25-26

spectrum, 21

window, 126

Frame buffer, 38

Frame grabber, 38

Frame store, 38

Fraser, 22i

Frequency domain, 19

Frequency leakage, 104

Frozen edge, 228

Gangnet, 179

Gaussian window, I43

Geometric transfomation, 1

Gibbs phenomenon, 22, 102

Global splines, 81-84

Global transfommtion, 76

Gouraud shading, 190

Gray levels, 12

Greene, 179

Grimson, 85

Ground control points, 63

Hamming window, 139

Hann window, 139

Heckbert, 179

Homogeneous coordinates, 46-47

Image, 11

continuous, 12

continuous-continuous, 12

continuous-discrete, 12

discrete-continuous, 12

discrate-discrete, 12

dissectors, 34-35

element, 31

reconstruction, 7, 17, 95, 99-105, 117

registration, 2

resampling, 7, 117

Impulse response, 15

Incremental algorithms, 189

Interpolation, 124

Interpolation grid, 60-61, 63

Interpolation kernels, 126-146

Inverse mapping, 44, i88

Irregular sampling, 173

Jittered sampling, 175

Kaiser window, 141

Kender, 88

Kronecker delta function, 15

Lanczos window, 142

Least Squares

Ordinary Polynomials, 65-67

Orthogonal Polynomials, 67-70

Weighted, 70-75

Levoy, 178

Linear interpolation, 127

Local transformation, 77

Marino, 205

Mesh warping, 222-240

Microdensitometer, 37

Mip maps, 181

Monochrome image, 12

Multispectral image, 12

Nearest neighbor, 126

Newell, 178

Normal equations, 66

NTSC, 37

Nyquist rate, 99

Paeth, 208

PAL, 37

Parzen window, 135

Passband, 103

Pel, 31

Perspective transformation, 52-56

incremental, 196

Inferring, 53-56

Inverse, 52

Robertson, 240

Two-pass, 218

Picture element, 31

Piecewise polynomial transformations, 75-81

Pixel, 7, 31

Point diffusion, 176

Point sampling, 8, 96, i63

Point shift algorithm, 126

Point spread function, 16, 29

Poisson-disk distribution, 174

Poisson sampling, 174

Polynomial transfmations, 61-75

Postaliasing, 108

Postfilter, 108

Prealiasing, 108

Prefilter, 108, 166, 181

Preimage, 166

Pseudoinverse solution, 64-65

Pyramids, 181

Quantization, 30-31

Rate buffering, 38

Reconstruction, 17, 95, 99-105, 1 i7

Regularizafion, 84

Regular sampling, 168

Resampling filter, 121

Robertson, 240

Roof function, 128

Rotation, 49, 205-214

Sample-and-hold function, 126

Sampling, 12, 97-98

Adaptive, 169

Area, 166

irregular, 173

jittered, 175

nonunifoma, 173

point-diffusion, 176

INDEX

Poisson, 174

stochastic, 173

uniform, 168

Sampling grid, 7, 30, 117

Sampling theory, 6, 95-116

Scale, 49

Scanline algorithms, 9, 187

Scanning camera, 36

Schowengerdi, 221

Screen space, 178

SECAM, 37

Separability, 29, 59, 187, 214

Separable mapping, 188,240

Shear, 49

Sifting integral, 15

Signal, 11

Sinc function, 101-102

Smith, 206, 215,221

Spatial

interpolation, 63

transformation, 6, 41-94

Special Effects, 222

Stochastic sampling, 173

Stopband, 103

Summed-area tables, 183

Supersampling, 168

Surface fitting, 75, 81

Tanaka, 208

Tent filter, 128

Terzopoulos, 86

Texture mapping, 189

Texture space, 178

Tiepoints, 63

Transfomation matrix, 45

Translation, 48

Triangle filter, 128

Triangulation, 78-81

Two-parameter cubic filter, 131

Unifom sampling, 168

Video digitizer, 37

Vidicon camera, 32-34

Warp, 1

318 lsox

Weiman, 206

Windowed sine function, 137-146

Windows,

Blackman, 140

Gaussian, 143

Hamming, 139

Hann, 139

Kaiser, 141

Lanczos, 142

Rect, 137

Wolberg, 241-242

GEORGE WOLBERG

BIOGRAPHICAL SKETCH

George Wolberg was born on February 25, 1964, in Buenos Aires, Argentina. He

received the B.S. and M.S. degrees in electrical engineering from Cooper Union, New

York, NY, in 1985, and the Ph.D. degree in computer science from Columbia University,

New York, NY, in 1990.

He is currently an Assistant Professor in the Computer Science deparanent at the

City College of New York / CUNY, and an Adjunct Assistant Professor at Columbia

University. He has worked at AT&T Bell Laboratories, Murray Hill, NJ, and at IBM T.J.

Watson Research Center, Yorktown Heights, NY, during the summers of 1983/4 and

1985/9, respectively. His research at these labs centered on image restoration, image

segmentation, graphics algorithms, and texture mapping. From 1985 to 1988, he served

as an image processing consultant to Fantastic Animation Machine, New York, NY, and

between 1986 and 1989, he had been an Instructor of Computer Science at Columbia

University. He spent the summer of 1990 at the Electrotechnical Laboratory in Tsukuba,

Ibaraki, Japan, as a selected participant in the Summer Institute in Japan, a research pro-

gram sponsored by the U.S. National Science Foundation and by the Science and Tech-

nology Agency of Japan.

Dr. Wolberg was the recipient of a National Science Foundation Graduate Fellow-

ship. His research interests include image processing, computer graphics, and computer

vision. He is a member of Tau Beta Pi, Eta Kappa Nu, and the IEEE Computer Society.

?EEE Computer Society

IEEE Computer Society Press

Press Actlvlffss Board

vice President: James H. Ayler, Universi[y of Vrginia

Jon T. BuUer, U.S. Naval Postgraduate School

Ronald D, Willtern s, University of V]rgthia

EZ Nahourthi. IBM

Eugene M+ Falken, IEEE Computer Sodsty

Ted I.wis, Oregon State Udiversity

Fred E. Perry. Tdiane University

Murali Varanasi, University of South Fodde

Guylaine Pollock, Sandia Natondi Laboratories

Editorial Board

Editer-in-Chief: Ez Nabourrdi, IBM

EditOrs: Jori T. Butier, U.S. Naval Postgraduate School

Joydeep Gosh. University of Texas, Austn

A.R. Hutson. Pennsylvania SLate Unversty

Gany R. Kempart, Searde University

Krishna Keri. University of Texas, Adington

Fmdedck E. Perry, Tulane University

Charles Rich(at. MCC

Sol Shaz, University el Illinois, Chicago

predip K. Srimeni, Cdiomde State University

MureJi R. Vatanasi, University el South PloMa

Rao Vemud, Univeraity o[ caigomia, Davis

T. Mchael Elliott, Executve OireCtor

Eugene M. Faiken, Directer

Margaret J. Brown, Managing Edi[or

Walter Hutrhine. ProdetOn Edi[or

Ann Macestrum. Product[ca Editor

Robert Warear, Production Editor

{)e'a PadicE,, Editorial Assistant

Usa O'Conner. Press Secretary

Thomas F[nk, Advertsing/Promotions Manager

Fdeda Kosstar, Markstag/Customer SO nices Manager

Becky Jacobs, Marketing/Customer Sonices Admin. Assl

Susan Roarke, Customer Serviceszrder Processing

Offices of the IEEE Computer Society

Headquarters Office

Publications Office

Asian Office

IEEE Computer Society Press Publications

MonographJ: A mcegrsph is an authored book

Tutorials: A tutodal is a colleUon of original materials prepared

by the edi[ors and reprints el {he best acles published in a

subject area. They must canon at least five percent odginal

mateddi (t5 to 20 percent oiginal material is recmmendud),

Reprint Books: A repdnl book is a collecton of reprints cvided

inlo sections with a preface. table of contents, and secon

Inloduodens that discuss the regints and why Ihey were

selected. It contains less than five percent odgine] meteHeJ.

(Subject) Technology SorleJ= Each technology series is a

coltact on el anthdiegles of reprints, each with a namow focus q

a subset el a par'dculsr diedplinth sudn as networks,

ardntecm. software. robndos.

Submte81on of proposals: For guidelines on preparing CS

Press Soohs. wrte Editor-in-Chief. IEEE Computer Society, P.O.

Sex 9O]4, t0662 Los Vaqueros Cirdie. Los Alarntos. CA 90720-

1264 (telephone 71421380).

Purpose

el computer science and engineering, pornotos the exchange of

tochnrdaJ informalion among 100.9O0 members woltdwide, and

provides a wide rgo el services to members and nonmembers.

Membership

Members receive the acclaimed monthly magazine Computer,

discounts. and opportudites o serve (all act141ies re led by

volunteer members). Membership is open to dil IEEE members.

afiliate sodiety members, and others sedously Interested in the

computer field.

Publications and Activities

Computer. An authottaUve, easy-to-read magazine

containing {utodal and in,epth el[cles on topics across the

cxmputer field. plus news, cenferences, c4aJendar, inteniews,

and new products.

Perdodloal, The sodety publishes six magazines and four

research transaotons, Refer to membership applioaton or

request infoaton as noted above,

Conference Proceedlngo. Tutortel Texts. Standerda

Doumenll, The Computer Sodiety Press pubtshes more than

19O ttes every year.

Slendarde Working Groups. Over 1(30 of these groups

produce IEEE stdade used throughout the industrial world.

Thnll Commitlees. Over 30 TCs publish newsletters,

provide [nteractten with peers in spediaby reas, and directly

influence standards, conferences. and educeton.

Conferences/Education. The society holds about

conferences each year and sponsors many nducatoneJ acerites,

including computng science

Cdaptel. Regular and sindent chapters weddwide prede

the opperunily to interact with colleagues, hear technical

experls, end sere the Iol prolessional community.

Other IEEE Computer Society Press Texts

71'9 8