Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!ucsd!sdd.hp.com!zaphod.mps.ohio-state.edu!julius.cs.uiuc.edu!apple!bionet!agate!pasteur!miro.Berkeley.EDU!ph
From: ph@miro.Berkeley.EDU (Paul Heckbert)
Newsgroups: comp.graphics
Subject: Re: gray-level interpolation
Message-ID: <28322@pasteur.Berkeley.EDU>
Date: 28 Sep 90 22:47:24 GMT
References: <8536@helios.TAMU.EDU>
Sender: news@pasteur.Berkeley.EDU
Reply-To: ph@miro.Berkeley.EDU (Paul Heckbert)
Organization: University of California at Berkeley
Lines: 111

In article <8536@helios.TAMU.EDU> guansy@cs.tamu.edu (Sheng-Yih Guan)
asked about methods for performing resampling when an image is being
warped by a non-invertible deformation.
Assume that the source image, in (u,v) space, is mapped to the
the destination image, in (x,y) space, by x=x(u,v), y=y(u,v).

Methods for image warping can be grouped into three classes:

    1. Destination Scanning
        Scan in the destination image space, at each (x,y) pixel inverting the
        mapping to find (u,v).
        For a non-invertible or difficult-to-invert mapping, you could
        use iterative techniques such as Newton's method to solve for
        (u,v) given (x,y).
        Given estimates of the Jacobian of the inverse mapping in this vicinity
        (partial u / partial x), (partial v / partial y) etc, you can do
        good filtering (interpolation or decimation).

    2. Source Scanning
        Scan in source space, at each (u,v) pixel computing the destination
        point (x,y).
        This method is prone to holes and overlaps if you do point sampling
        (write to only one destination pixel), so it is better to map a
        little filter (take your pick: a 1x1 box filter, a 2x2 triangle
        filter, a bicubic filter, a truncated sinc ...) to destination space,
        and accumulate contributions in a destination array.

    3. Multi-pass Methods
        There are several of these.
        These generally perform a complex warp as a succession of simpler
	warps that only distort along rows or columns.
	Affine, projective (perspective), and bilinear warps can be done
	quite directly using two-pass warps, as described by [Catmull-Smith].
	[Paeth] describes a nice, simple 3-pass rotation algorithm.
	[Smith87] generalizes the method to bicubic and other mappings.

When the mapping is difficult to invert, performing the warp at all,
even with point sampling, can be hard.
For your problem, you might try approximating your complex mapping function
by a grid of simpler mappings.  Projective mappings are convenient because
they are defined by 4 points.  They would give you continuity of position
but not of its first derivative.  Projective mappings are easily invertible,
so they would be much easier to program than an arbitrary mapping.

Some references on image warping:

%A Edwin E. Catmull
%T A Subdivision Algorithm for Computer Display of Curved Surfaces
%R PhD thesis
%I Dept. of CS, U. of Utah
%D Dec. 1974
%Z bicubic patches, 1st texture mapping, uses "accumulation buffer"

%A Edwin E. Catmull
%A Alvy Ray Smith
%T 3-D Transformations of Images in Scanline Order
%J Computer Graphics
(SIGGRAPH '80 Proceedings)
%V 14
%N 3
%D July 1980
%P 279-285
%K texture mapping
%Z two-pass image warp

%A Donald Fraser
%A Robert A. Schowengerdt
%A Ian Briggs
%T Rectification of Multichannel Images in Mass Storage Using Image
Transposition
%J Computer Vision, Graphics, and Image Processing
%V 29
%N 1
%D Jan. 1985
%P 23-36
%Y ph
%Z texture mapping, two-pass image warp, just like Catmull & Smith 80!
see corrigendum vol. 31, p. 395

%A Paul S. Heckbert
%T Fundamentals of Texture Mapping and Image Warping
%R Master's thesis, UCB/CSD 89/516
%I CS Dept, UC Berkeley
%D May 1989
%Z affine, projective, bilinear 2-D mappings; ideal resampling filters

%A Alan W. Paeth
%T A Fast Algorithm for General Raster Rotation
%B Graphics Interface '86
%D May 1986
%K image warp, texture mapping, two-pass, three-pass
%P 77-81

%A Alvy Ray Smith
%T Planar 2-Pass Texture Mapping and Warping
%J Computer Graphics
(SIGGRAPH '87 Proceedings)
%V 21
%N 4
%D July 1987
%P 263-272

%A George Wolberg
%T Digital Image Warping
%I IEEE Computer Society Press
%D 1990
%Z survey of previous work

Paul Heckbert, Computer Science Dept.
570 Evans Hall, UC Berkeley		INTERNET: ph@miro.berkeley.edu
Berkeley, CA 94720			UUCP: ucbvax!miro.berkeley.edu!ph