guansy@cs.tamu.edu (Sheng-Yih Guan) (09/26/90)
Hi,
Does there exist a canned method to solve the gray level interpolation
for a deformed image. The deformation is quivalent to a mapping which
may be expressed as
x' = r(x, y)
and
y' = s(x,y).
If r(x, y) and s(x, y) were known analytically it might be possible in
principle to find non-integer values for (x, y) given integer values
of the coordinates(x', y'). Then methods such as bilinear interpolation,
cubic convolution interpolation may be applied for calculating the gray
level at (x', y').
The deformation I am interested in has no easy way to find the inverse
mapping. So, the question is how am I going to solve the gray-level
assignment for my deformed image efficiently and systematically.
Any suggestion or helpful hints ? Please email me at
stanley@visual1.tamu.edu
Thanks in advance!
-Stanley
_ _ _ ___________
| \ /_| / / Visualization Lab /____ ____/
\ \ // / / Computer Science Dept / / _ _ _ _
| | // / / Texas A&M University / / / | | \ / | | | ||
| |// / / College Station, TX 77843-3112/ / / /| | \//|| | | ||
/ / / /____ Tel: (409)845-0531 / / / -|| | |\/ || | !_!|
!__/ /______/ stanley@visual1.tamu.edu /_/ /_/ || !_! || !____!ph@miro.Berkeley.EDU (Paul Heckbert) (09/29/90)
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