Computer Graphics and Image Processing
What is an image?
A real image is a two dimensional function. The value at any point is an intensity or color.
The eye
The retina is an array of light detection cells.
The fovea is the high resolution area of the retina.
The optic nerve takes signals from the retina to the visual cortex in the brain.
Cones come in three types, sensitive to short, medium
and long wavelengths.
They are concentrated at the center of the retina, many in the fovea.
The distribution of rods in the fovea is about 7% short, 37% medium and 56% long, so we cannot see fine detail in blue. The luminance in the fovea is the sum of the response functions of the rods, the luminance outside the fovea is the response function of the rods.
Outside the fovea there are mainly rods, which are low resolution and monochromatic which are used for peripheral vision and in the dark.
The eye can do edge detection very well, and can discriminate intensity well (except in extremes of dark or light) but aren't so good at discriminating colours.
The pre-processing can cause illusions, e.g. Mach bands and Ghost squares.
Illuminants
The light source illuminating an object has a great effect on what the object looks like, eg; sunlight is quite uniform but light bulbs are very red.
Illuminant x reflection = reflected light
Munsells Colour Classification
Three axes:
● hue > what is the principal colour?
● value > how light or dark is it?
● chroma > how vivid or dull is it?
Based on testing people, so quite irregular, but easy to use by humans.
HSV is based on Munsell, "value"="hue" and "saturation"="chroma"
XYZ Colour Space
Y is the measure of brightness/luminance.
The chroma (colour) is specified by x,y,z - which are derived from X,Y,Z :
Based on measurements of the eye. Not perceptually uniform, ie you won't notice a big change in green but will notice a little change in red.
Luv, Lab Colour Space
Based on XYZ, but designed to be more perceptually uniform.
RGB Space
Used by televisions, CRT & LCD Screens etc.
Maps to a triangle in XYZ space: not all of XYZ space can be displayed.
Luminance Y = .3R + .6R + .1G
CMYK Space
Printers make colours by mixing inks, at its simplest is the inverse of RGB
● cyan absorbs red, reflects blue and green
● magneta absorbs green, reflects red and blue
● yellow absorbs blue, reflects green and red
● key (black) gives a good black
Sampling Resolution and Quantization
A digital image is a sampled and quantized (for example seeking to reduce the number of colors required to represent an image). It is stored as a rectangular array of intensity or color values.
Printers have a low bit depth (low quantization/reduced number of intensity levels) but high resolution as the eye can pick up detail on something stationary.
Grey scale
Commonly 1 byte is used, so an image of size WxH can be stored in a block of WxH bytes.
One way to store pixel [x][y] is at memory location x+ Width.y
Colour images
Commonly 24 bits: One bit red, one green, one blue
Size will be W x H x 3. Normally stored in 3 WxH planes (one for each colour).
The frame buffer
|
|
|
Most computers have a special
piece of memory reserved for storage of the current image being displayed.
The frame buffer is normally built from DRAM.
When the image is being updated we nay see bits of the old image being displayed halfway through the update. Double buffering solves this: draw into one frame, display from the other. Once drawing is complete, we switch buffers.
Cathode Ray Tubes (CRT)
Used in monitors, TVs.
● The heater emits electrons, which are accelerated by the potential difference between cathode and anode. Electrons hitting the front screen excite the phosphor, making it emit visible light
● Changing voltage changes the intensity of the beam and hence spot
● Deflection coils magnetically deflect the electron beam to any position on the screen
● Beam scans screen left to right, cuts power then whizzes back to start and up a line
● Repeated fast enough, (>20Hz) gives illusion of continuous picture.
Colour is achieved through three separate electron guns (one for each colour) and three separate colour phosphors. To ensure the guns hit the right colored phosphor shadow masks are used.
Cutaway rendering of a color CRT
1. Electron guns
2. Electron beams
3. Focusing coils
4. Deflection coils
5. Anode connection
6. Mask for separating beams for red, green, and blue part of displayed image
7. Phosphor layer with red, green, and blue zones
8. Close-up of the phosphor-coated inner side of the screen
Liquid Crystal Displays
● Before applying an electric field the molecules twist to try to line up. Half of the light is absorbed by the first polarizing filter, but otherwise the entire assembly is transparent.
● Applying a voltage ruins the twisting phenomenon so the pixel becomes opaque (no light can get through the two polarizers at 90).
● Colour is achieved with colour filters
Lower power consumption,thin.
Plasma Displays
● A high voltage across the electrodes ionizes a noble gas (xenon, neon)
● The noble gas emits ultraviolet light
● The ultraviolet light excites the phosphor, which emits visible light
Large and thin but lots of power and expensive.
Digital Micro mirror Devices
● Manufactured like a silicon chip
● Used increasingly in projectors
● Colour achieved from three DMD chips, or one chip and a rotating colour filter
Printers
● Inkjet sprays ink onto paper. May use electrostatic field. 300-1200 dpi. Home printer.
● Laser printer uses a laser to lay down pattern of charge on a drum, which picks up charged toner and is then pressed onto the paper and fixed. 300-1200 dpi. Office printer.
● Commercial photo typesetter. Whole page put on plates with a roller, repeatedly inked and pressed against paper. High quality 2400 dpi, thousands of copies. CMYK plus spot colour to produce one colour (eg corporate logo) without half toning.
● Dye sublimation gives true greyscale, but is very expensive
Greyscale printing
● Half toning: Split into a grid. The greater the intensity, the larger the spot.
Can create obvious line effects though, and photocopies badly
● Dithering is similar but instead of a single blob patterns which don't make lines are used
Drawing a Straight Line
A straight line can be defined by y=mx+c
You get the best line by choosing to draw the closest pixel to the line in each column, not every pixel through which the line passes.
Bresenham's line drawing algorithm
(For the first octant)
//Find the gradient: how much the line increases in y every x++
d= (y1 -y0) / (x1 - x0)
//Initialise
x = x0
yi = y0
y = y0
//Draw the first point
DRAW(x,y)
//While we're not at the end of the line
WHILE x <x1 DO
//Move along the line one
x = x + 1
//Find actual y position at current x
yi = yi + d
//Round y to get plottable value
y = ROUND(yi)
DRAW(x,y)
END WHILE
As floating point calculations are slow, instead of rounding can use an if:
IF (yf > 1/2) THEN
y = y + 1
yf = y -1
END IF
(yf instead of yi, initialized to 0)
Can now multiple all operations involving yf by 2(x1-x0), removing floating point arithmetic if end points have integer co-ordinates.
Midpoint line drawing algorithmic
A decision variable decides whether next pixel is on to the right, or one to the right and up one.
a = (y1 - y0)
b = -(x1 - x0)
c = x1y0 - x0y1
x = ROUND(x0)
y = ROUND(y0 - (x - x0)(a/b))
d = a * (x=1) + b * (y+1/2) + c
DRAW(x,y)
WHILE x < (x1 - 1/2) DO
x = x + 1
IF d < 0 THEN
d = d + a
ELSE
d = d + a + b
y = y + 1
END IF
DRAW(x,y)
END WHILE
This can easily be extended to draw circles, wher ethe decision variable d can be
d = x2 + y2 - r2
Bezier Cubes
Four points P0, P1, P2 and P3 in the plane or in three-dimensional space define a cubic Bézier curve. The curve starts at P0 going toward P1 and arrives at P3 coming from the direction of P2. Usually, it will not pass through P1 or P2; these points are only there to provide directional information. The distance between P0 and P1 determines "how long" the curve moves into direction P2 before turning towards P3.
The parametric form of the curve is:
The weighting functions (P0-P3) sum to one.
Joins at end points can be:
● C1 continuity both position and tangent vector
● G1 continuous in position, tangent vector in same direction
● C0 continuous in position only
We could just draw a bezier curve as a set of short line segments between Bezier(t) and Bezier(t+step).
A better way is adaptive sub-devision:
● Check if straight line between P0 and P3 is an adequate approximation to the Bezier
● If so: draw the straight line
● If not: divide the Bezier into two halves, each a Bezier, and repeat for the two new Beziers
Checking for flatness:
S = AB.AC / |AB|2
Overhausers Cubic
Given points A,B,C,D the Bezier control points are:
P0 = B P1 = B + (C-A)/6 P3 = C P2=C-(D-B)/6
Douglas & Pucker's algorithm
This reduces the number of line segments in a chain without compromising quality
● find point C, at greatest distance from segment AB
● if distance from C to AB is more than some specified tolerance then subdivide into AC and CB, repeat for each of the subdivisions
● otherwise approximate entire chain from A to B by the single line segment AB
Clipping
When clipping around a rectangle, you could just check every line against each of the four edges.
 |
The Cohen-Sutherland clipper uses a 4 bit code for each section around the rectangle. If you and each end of the line with the section code it is in, and the result is 0, then nothing has to be clipped-otherwise you know where to clip.
Make a four bit code, one bit for each inequality
A = x < Xleft B = x > Xright C = y < Ybottom D = y > Yright
Evaluate this for both end points Q1 = A1B1C1D1 Q2 = A2B2C2D2
If both Q1 and Q2 are zero then both ends are in the rectangle, accept
If Q1 AND Q2 != 0 then both ends must have the same bit code as 1 - both ends outside and in the same section - reject
Otherwise, intersect line with one of the edges loop, clip
Scanline Polygon Fill Algorithm
Create and edge list
Start with the left most point of the polygon, move right filling in all pixels whose centers lie inside the polygon, move up a line once scanned entire line.
To find the intersection points use an incremental line drawing algorithm.
Sutherland-Hodgman Polygon Clipping I
Clip polygon against an infinite line, then pass the result on and clip with next edge.
Homogeneous 2d co-ordinates
Homogeneous coordinates solve the problem of representing translation as a matrix operation.
For every x,y in normal space there is an infinite number of x,y,w points where
(x,y,w) = (x/w,y/w)
w=0 represents a point at infinity, the inverse transform is (x,y) = (x,y,1)
In 3d:
(x,y,z,w) = (x/w,y/w,z/w)
Matrix transformations
Note that concatenation is not commutative.
Translation
To move points (x,y,w) to (x+x0,y+y0,w'):
multiply (x,y,w) by the matrix
1 0 x0
0 1 y0
0 0 1
In 3d:
Scale
About origin, factor m
To scale about a point, translate to center, scale, then translate back again.
In 3d:
Rotate
About origin, angle Ө
In 3d, about x-axis:
In 3d, about y-axis
In 3d, about z-axis
Do nothing
Identity
In 3d:
Shear
Parallel to x axis, factor a
Bounding boxes
Speed up some operations, can clip around them at increasing levels of detail.
Bit block transfer (BitBit)
Often quicker to predraw something then copy the image to the correct position on the screen when required. Copy an image is essentially a memory operation.
Typefaces
● Pre-rendered bit maps. Use BitBit to put into frame buffer. Don't scale well.
● Outline definitions. Scale well, need to fill to put into frame buffer.
Viewing Co-ordinates
The camera in world co-ordinates is specified by:
●
eye (camera) position at 
●
look point (center of screen)
at 
●
up along vector 
- perpendicular to el
You can trim along a pyramid just as you would with a 2D rectangle.
You can also project to 2D (giving you lots or rectangles as you progress through z) then clip.
To transform from world to viewing co-ordinates:
e goes to (0,0,0) and l goes to (0,0,d)
●
T=translate eye point 
to origin (0,0,0)
● S=scale so that the eye point to look point distance, el, is distance from origin to screen centre
● Align el with z-axis:
transform e and l into new co-ordinate system
e'' = S x T x e =0 l'' = S x T x l
R1= Rotate e''l'' into yz plane, rotating about y-axis
● R2=Rotate viewing vector again, this time about the x-axis so it aligns with the z-axis
● R3=Rotate the up vector about the z-axis so that it lies in the positive y half of the yz plane
Examples
The joints of a robot arm can only move in the xy-plane, the shoulder is attached to a z-axis vertical slider.
The initial position of the arm is
● shoulder joint: position (0,0,0), rotation 0°
● elbow joint: position (2,0,0), rotation 0°
● hand: position (3,0,0)
There is a soft drink can located at position (1,1,1). Make the arm touch it.
To rotate elbow about Z-axis by 90:
| Cos90 | -sin90 | 0 | 0 |
| Sin90 | Cos90 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 |
To rotate elbow about Y-axis by 90
| Cos90 | 0 | Sin90 | 0 |
| 0 | 1 | 0 | 0 |
| -sin90 | 0 | Cos90 | 0 |
| 0 | 0 | 0 | 1 |
Sin90=1, cos90=0
To move shoulder -2 along x-axis
| 1 | 0 | 0 | -2 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 |
Give a matrix, in homogeneous co-ordinates which will project 3D space onto the plane z=d with the origin as the center of projection.
Looking for
=> 
Got
which comes from 
Bezier Patches
Bézier patches are defined by a 4×4 grid of 16 evenly spaced control points that form a surface made up of nine rectangular sub-patches.
where 
Online demo at http://www.nbb.cornell.edu/neurobio/land/OldStudentProjects/cs490-96to97/anson/BezierPatchApplet/index.html
Simliarly to Bezier curves, Bezier patches can be drawn by approximating them with planar polygons (subdividing according to tolerance level).
Continuity between Bezier patches
● C0 - continuous in position (the four edge control points must match)
● C1 - continuous in position and tangent vector (four edge control points must match, the two control points on either side of each of the four edge control points must be co-linear with both the edge point and each another and be equidistant from the edge point)
3D line drawing
● project end points onto the 2D screen
● use a line drawing algorithm to draw the lines- giving a wireframe version
● remove hidden lines
Depth sort polygon drawing
● transform all polygon vertices into viewing co-ordinates and project these into 2D, keeping z information
● calculate a depth ordering for polygons, based on the most distant z co-ordinate in each polygon
● resolve any ambiguities caused by polygons overlapping in z- split polygons if necessary and throw away original
● draw the polygons in depth order from front to back with a 2D polygon scan conversion.
don't draw back facing parts of solid polyhedrons-they will be hidden by the front
Slow with large numbers
Binary Space-Partitioning trees
Binary space partitioning data is calculated for a level before play, recursively splitting space by hyperplanes and storing in a tree.
BSP algorithm:
1. Start at the root node.
2. Draw the child nodes of this node recursively. The child node closest to the camera is drawn first. This can be found from looking at which side of the node's dividing line the camera is on.
3. When a sub sector is reached, draw it.
The algorithm stops when all pixels have been drawn, preventing double drawing.
Walls are drawn completely vertically aligned along the Y axis, meaning you cant look up and down but rendering is quick.
Z-buffering
If two objects in the scene share the same pixel on the projected screen, the closer one is drawn.
Test the z - depth of each surface to determine the closest (visible) surface. Declare an array z buffer(x, y) with one entry for each pixel position. Initialize the array to the maximum depth.
for each polygon P
for each pixel (x, y) in P
compute z_depth at x, y
if z_depth < z_buffer (x, y) then
set_pixel (x, y, colour)
z_buffer (x, y) <= z_depth
An A-buffer averages the different visible polygon colours to get an acceptable result, whereas in simple z buffering only the exact center of pixels is considered- leading to jagged edges and some small polygons not being drawn at all.
Fast and easy to implement in hardware.
Anti-aliasing
● Using the centre of piels for colours leads to small polygons being missed, agged edges etc.
● Getting rid of these artefact's is called anti-aliasing
Methods include:
● Averaging the colour
● Super sampling (sample on a finer grid)
● A-buffering
Reflective surfaces
Note that most specular surfaces aren't perfect and so the incident angle isn't the same as the reflection.
Common assumptions when shading a polygon include:
● There is only diffuse reflection
● No interaction between polygons
● Light source is infinitely far away, so vector is same across whole polygon
Diffuse shading calculation
● L is a normalized vector pointing in the direction of the light source
● N is the normal to the polygon
● Ii is the intensity of the light source
● Kd is the proportion of light which is diffusely reflected by the surface
● I is the intensity of the light reflected by the surface
Gourad shading
Calculate the diffuse illumination at each vertex rather than for each polygon
Phong shading
Approximation to specular reflection
Ray tracing
●
Shoot a ray from the eye through the center of every pixel and
see what it hits
● Shoots rays from that point to all of the light sources, and calculate the diffuse and specular reflections off the object at this point
● Check whether another object is between that point and the light and is hence casting shadow
Often use random or poisson discs patterns for super sampling for anti-aliasing
Sampling texture space: interpolation methods
● nearest neighbour: fast, artefact's
● biinear: fairly fast, blurry
● bicubic: good but slow
Some more things around p 306
GIF
GIF is a standard 8 bit bitmap format, with LZW lossless compression.
JPEG
Converted from RGB to YCbCr color space.
The channels are split into 8x8 blocks of pixels
The Cb and Cr components are seen in less detail by the human eye, so these are downsampled.
Each component is tiled into sections of 8x8 pixels using a discrete cosine transform.
High frequency brigthness variations are hard to tell apart by the human eye, so high frequency colour areas are averaged out.
The
lossless data compression algorithm "entropy encoding" is applied.