The easiest way, according to the comp.graphics faq, is to take
the rotation transformation and invert it. Then you just iterate
over the destination image, apply this inverse transformation and
find which source pixel to copy there.
A much nicer way comes from the observation that the rotation
matrix:
R(T) = { { cos(T), -sin(T) }, { sin(T), cos(T) } }
is formed my multiplying three matrices, namely:
R(T) = M1(T) * M2(T) * M3(T)
where
M1(T) = { { 1, -tan(T/2) },
{ 0, 1 } }
M2(T) = { { 1, 0 },
{ sin(T), 1 } }
M3(T) = { { 1, -tan(T/2) },
{ 0, 1 } }
Each transformation can be performed in a separate pass, and
because these transformations are either row-preserving or
column-preserving, anti-aliasing is quite easy.
Another fast approach is to perform first a column-preserving roation,
and then a row-preserving rotation. For an image W pixels wide and
H pixels high, this requires W+H BitBlt operations in comparison to
the brute-force rotation, which uses W*H SetPixel operations (and a
lot of multiplying).
Reference:
Paeth, A. W., "A Fast Algorithm for General Raster Rotation",
Proceedings Graphics Interface '89, Canadian Information
Processing Society, 1986, 77-81
[Note - e-mail copies of this paper are no longer available]
[Gems I]
[Gems I] pp. 287-293, "A Simple Method for Color Quantization:
Octree Quantization"
B. Kurz. Optimal Color Quantization for Color Displays.
Proceedings of the IEEE Conference on Computer Vision and Pattern
Recognition, 1983, pp. 217-224.
[Gems II] pp. 116-125, "Efficient Inverse Color Map Computation"
This describes an efficient technique to
map actual colors to a reduced color map,
selected by some other technique described
in the other papers.
[Gems II] pp. 126-133, "Efficient Statistical Computations for
Optimal Color Quantization"
Xiaolin Wu. Color Quantization by Dynamic Programming and
Principal Analysis. ACM Transactions on Graphics, Vol. 11, No. 4,
October 1992, pp 348-372.
"A Fast Algorithm for the Restoration of Images Based on Chain
Codes Description and Its Applications", L.W. Chang & K.L. Leu,
Computer Vision, Graphics, and Image Processing, vol.50,
pp296-307 (1990)
Heckbert, Paul S., Generic Convex Polygon Scan Conversion and Clipping,
Graphics Gems, p. 84-86, code: p. 667-680, PolyScan/.
Heckbert, Paul S., Concave Polygon Scan Conversion, Graphics Gems, p.
87-91, code: p. 681-684, ConcaveScan.c.
http://www.acm.org/tog/GraphicsGems/gems/PolyScan/
http://www.acm.org/tog/GraphicsGems/gems/ConcaveScan.c
For filling a region of a bitmap, see
Heckbert, Paul S., A Seed Fill Algorithm, Graphics Gems, p. 275-277,
code: p. 721-722, SeedFill.c. The code is at
http://www.acm.org/tog/GraphicsGems/gems/SeedFill.c
[Gems I]
[Foley]
[Hearn]
A simple method is to put the bitmap through the filter:
-1 -1 -1
-1 8 -1
-1 -1 -1
This will highlight changes in contrast. Then any part of the
picture where the absolute filtered value is higher than some
threshold is an "edge".
A more appropriate edge detector for noisy images is
described by Van Vliet et al. "A nonlinear Laplace operator
as edge detector in noisy images", in Computer Vision,
Graphics, and image processing 45, pp. 167-195, 1989.
Sharpening of bitmaps can be done by the following algorithm:
I_enh(x,y) = I_fuz(x,y)-k*Laplace(I_fuz(x,y))
or in words: An image can be sharpened by subtracting a positive
fraction k of the Laplace from the fuzzy image.
One "Laplace" kernel, approximating a Laplacian operator, is:
1 1 1
1 -8 1
1 1 1
The following library implements Fast Gaussian Blurs:
MAGIC: An Object-Oriented Library for Image Analysis by David Eberly
The library source code and the documentation (in Latex) are at
http://www.magic-software.com/
The code compiles on Unix systems using g++ and on PCs using
Microsoft Windows 3.1 and Borland C++. The fast Gaussian blurring
is based on a finite difference method for solving s u_s = s^2 \nabla^2 u
where s is the standard deviation of the Gaussian (t = s^2/2). It
takes advantage of geometrically increasing steps in s (rather than
linearly increasing steps in t), thus getting to a larger "time" rapidly,
but still retaining stability. Section 4.5 of the documentation contains
the algorithm description and implementation.
A bitmap is a sampled image, a special case of a digital signal,
and suffers from two limitations common to all digital signals.
First, it cannot provide details at fine enough spacing to exactly
reproduce every continuous image, nor even more detailed sampled
images. And second, each sample approximates the infinitely fine
variability of ideal values with a discrete set of ranges encoded
in a small number of bits---sometimes just one bit per pixel. Most
bitmaps have another limitation imposed: The values cannot be
negative. The resolution limitation is especially important, but
see "How do I display a 24 bit image in 8 bits?" for range issues.
The ideal way to enlarge a bitmap is to work from the original
continuous image, magnifying and resampling it. The standard way
to do it in practice is to (conceptually) reconstruct a continuous
image from the bitmap, and magnify and resample that instead. This
will not give the same results, since details of the original have
already been lost, but it is the best approach possible given an
already sampled image. More details are provided below.
Both sharpening and fuzzing are examples of filtering. Even more
specifically, they can be both be accomplished with filters which
are linear and shift invariant. A crude way to sharpen along a row
(or column) is to set output pixel B[n] to the difference of input
pixels, A[n]-A[n-1]. A similarly crude way to fuzz is to set B[n]
to the average of input pixels, 1/2*A[n]+1/2*A[n-1]. In each case
the output is a weighted sum of input pixels, a "convolution". One
important characteristic of such filters is that a sinusoid going
in produces a sinusoid coming out, one of the same frequency. Thus
the Fourier transform, which decomposes a signal into sinusoids of
various frequencies, is the key to analysis of these filters. The
simplest (and most efficient) way to handle the two dimensions of
images is to operate on first the rows then the columns (or vice
versa). Fourier transforms and many filters allow this separation.
A filter is linear if it satisfies two simple relations between the
input and output: scaling the input by a factor scales the output
by the same factor, and the sum of two inputs gives the sum of the
two outputs. A filter is shift invariant if shifting the input up,
down, left, or right merely shifts the output the same way. When a
filter is both linear and shift invariant, it can be implemented as
a convolution, a weighted sum. If you find the output of the filter
when the input is a single pixel with value one in a sea of zeros,
you will know all the weights. This output is the impulse response
of the filter. The Fourier transform of the impulse response gives
the frequency response of the filter. The pattern of weights read
off from the impulse response gives the filter kernel, which will
usually be displayed (for image filters) as a 2D stencil array, and
it is almost always symmetric around the center. For example, the
following filter, approximating a Laplacian (and used for detecting
edges), is centered on the negative value.
1/6 4/6 1/6
4/6 -20/6 4/6
1/6 4/6 1/6
The symmetry allows a streamlined implementation. Suppose the input
image is in A, and the output is to go into B. Then compute
B[i][j] = (A[i-1][j-1]+A[i-1][j+1]+A[i+1][j-1]+A[i+1][j+1]
+4.0*(A[i-1][j]+A[i][j-1]+A[i][j+1]+A[i+1][j])
-20.0*A[i][j])/6.0
Ideal blurring is uniform in all directions, in other words it has
circular symmetry. Gaussian blurs are popular, but the obvious code
is slow for wide blurs. A cheap alternative is the following filter
(written for rows, but then applied to the columns as well).
B[i][j] = ((A[i][j]*2+A[i][j-1]+A[i][j+1])*4
+A[i][j-1]+A[i][j+1]-A[i][j-3]-A[i][j+3])/16
For sharpening, subtract the results from the original image, which
is equivalent to using the following.
B[i][j] = ((A[i][j]*2-A[i][j-1]-A[i][j+1])*4
-A[i][j-1]-A[i][j+1]+A[i][j-3]+A[i][j+3])/16
Credit for this filter goes to Ken Turkowski and Steve Gabriel.
Reconstruction is impossible without some assumptions, and because
of the importance of sinusoids in filtering it is traditional to
assume the continuous image is made of sinusoids mixed together.
That makes more sense for sounds, where signal processing began,
than it does for images, especially computer images of character
shapes, sharp surface features, and halftoned shading. As pointed
out above, often image values cannot be negative, unlike sinusoids.
Also, real world images contain noise. The best noise suppressors
(and edge detectors) are, ironically, nonlinear filters.
The simplest way to double the size of an image is to use each of
the original pixels twice in its row and in its column. For much
better results, try this instead. Put zeros between the original
pixels, then use the blurring filter given a moment ago. But you
might want to divide by 8 instead of 16 (since the zeros will dim
the image otherwise). To instead shrink the image by half (in both
vertical and horizontal), first apply the filter (dividing by 16),
then throw away every other pixel. Notice that there are obvious
optimizations involving arithmetic with powers of two, zeros which
are in known locations, and pixels which will be discarded.
Paul S. Heckbert, "Survey of Texture Mapping", IEEE Computer
Graphics and Applications V6, #11, Nov. 1986, pp 56-67 revised
from Graphics Interface '86 version
Eric A. Bier and Kenneth R. Sloan, Jr., "Two-Part Texture
Mappings", IEEE Computer Graphics and Applications V6 #9, Sept.
1986, pp 40-53 (projection parameterizations)
[Currently empty entry.]
ftp://oak.oakland.edu/SimTel/msdos/
See also James Murray's graphics file formats FAQ:
http://www.ora.com/centers/gff/gff-faq/index.htm
Morphing is the name that has come to be applied to the technique
ILM used in the movie "Willow", where one object changes into
another by changing both its shape and picture detail. It was a
2D image manipulation, and has been done in different ways. The
first method published was by Thad Beier at PDI. Michael Jackson
famously used morphing in his music videos, notably "Black or
White". The word is now used more generally.
For more, see [Anderson], Chapter 3, page 59-90, and Beier's
http://www.hammerhead.com/thad/morph.html
The easiest way is to render each line separately into an edge
buffer. This buffer is a structure which looks like this (in C):
struct { int xmin, xmax; } edgebuffer[YDIM];
There is one entry for each scan line on the screen, and each
entry is to be interpreted as a horizontal line to be drawn from
xmin to xmax.
Since most people who ask this question are trying to write fast
games on the PC, I'll tell you where to find code. Look at:
ftp::/ftp.uwp.edu/pub/msdos/demos/programming/source
ftp::/ftp.luth.se/pub/msdos/demos (Sweden)
ftp::/NCTUCCCA.edu.tw:/PC/uwp/demos
/www.wit.com:/mirrors/uwp/pub/msdos/demos">http://www.wit.com:/mirrors/uwp/pub/msdos/demos
ftp::/ftp.cdrom.com:/demos
See also Subject 3.03, which describes methods for filling polygons.
See:
ftp://gondwana.ecr.mu.oz.au/pub/
ftp://ftp.cis.ohio-state.edu/pub/siggraph...raph92_C23.shar
In it there are implementations of Perlin's noise and turbulence
functions, (By the man himself) as well as Lewis' sparse
convolution noise function (by D. Peachey) There is also some of
other stuff in there (Musgrave's Earth texture functions, and some
stuff on animating gases by Ebert).
SPD (Standard Procedural Databases) package:
ftp://avalon.chinalake.navy.mil/utils/SPD/
ftp://avalon.chinalake.navy.mil/utils/SPD/.
Now moved to http://www.viewpoint.com/
References:
[Ebert]
Noise, Hypertexture, Antialiasing and Gesture, (Ken Perlin) in
Chapter 6, (p.193-), The disk accompanying the book is available
from
ftp://archive.cs.umbc.edu/pub/.
For more info on this text/code see:
http://www.cs.umbc.edu/~ebert/book/book.html
For examples from a current course based on this book, see:
http://www.seas.gwu.edu/graphics/ProcTexCourse/
Linke broken 21Jan03; will remove eventually if not fixed.
[Watt:Animation]
Three-dimensional Nocie, Chapter 7.2.1
Simulating turbulance, Chapter 7.2.2
For fractal mountains, trees and sea-shells:
SPD (Standard Procedural Databases) package:
ftp://avalon.chinalake.navy.mil/utils/SPD/
ftp://avalon.chinalake.navy.mil/utils/SPD/.
Now moved to http://www.viewpoint.com/
Reaction-Diffusion Algorithms:
For an illustartion of the parameter space of a reaction
diffusion system, check out the Xmorphia page at
http://www.ccsf.caltech.edu/ismap/image.html
References:
[Ebert]
Entire book devoted to this subject, with RenderMan™ and C code.
[Watt:Animation]
Procedural texture mapping and modelling, Chapter 7
"Generating Textures on Arbitrary Surfaces Using Reaction-Diffusion"
Greg Turk, Computer Graphics, Vol. 25, No. 4, pp. 289-298
July 1991 (SIGGRAPH '91)
http://www.cs.unc.edu:80/~turk/reaction_di..._diffusion.html
A list of procedural texture synthesis related web pages
http://www.threedgraphics.com/pixelloom/tex_synth.html
References:
[Watt:3D] pp. 313-354
[Foley] pp. 563-603
"GIF" is an acronymn for "Graphics Interchange Format." Despite the
hard "G" in "Graphics," GIF is pronounced "JIF." Although we don't
have a direct quote from the official CompuServe specification
released June 1987, here is a quote from related CompuServe documentation,
for CompuShow, a DOS-based image viewer used shortly thereafter:
"The GIF (Graphics Interchange Format), pronounced "JIF", was
designed by CompuServe ..."
We also have a report that the principal author of the GIF spec,
Steve Wilhite, says "it's pronounced JIF (like the peanut butter."
See also