Today's Lecture

● Repetition and refinement of image basics:

– What is an image?
– Sampling
– Interpolation
– Aliasing
– Convolution
– The Fourier Domain
– Point operations
 Image Definition
● Continuous image n
f : D  ℝ , D⊂ℝ
(D is a compact subdomain of ℝ)
– Finite in size
– Each point has a scalar value
● Multi-valued image n
f : D ℝ
k
, D⊂ℝ
– Each point has multiple values
● Discrete image n
f : D ℝ , D⊂ℤ
– Sampled version of continuous image
– Sample values still real-valued!
● Digital image n
f :D ℤ , D⊂ℤ
– Sample values also discretized
 Samples and Pixels
● Sample: the value f(x) of a function at a point x
– 1-D signals: people talk of “samples”
– 2-D images: people talk of “pixels”
– 3-D images: people talk of “voxels”
– These are all the same thing! (suggested: imels)

● Pixels represented as little

rectangles on the screen
– This is the Voronoi
tesselation of the samples
in a rectangular grid
 Alternative Sampling Grids
● Do we always need to use rectangular grids?
● Alternative in 2-D: hexagonal grid
– Advantages:
● All direct neighbours at same distance
● All direct neighbours share an edge (no "connectivity paradox")
● 3 directions of equal distance, vs 2 in square grid
Alternative Sampling Grids
 Alternative Sampling Grids
● Alternatives in 3-D (generalizations of hexagonal grid):
– Face centered cubic
● Voronoi tessellation is rhombic dodecahedron
● Tightest possible packing density (Kepler)
– Body centered cubic
● Voronoi tessellation is truncated octahedrons
● Like hexagonal grid, all direct neighbors share faces
Reconstruction of the Cont. Function
Alternative Interpolation Kernels

sin(πx)/πx uses all data points

Alternative Interpolation Kernels

uses 1 data point

Alternative Interpolation Kernels

uses 2 data points

Alternative Interpolation Kernels

4 cubic polynomials pieced together uses 4 data points

Alternative Interpolation Kernels

sin(πx) / (πx) * sin(πx/2) / (πx/2) uses 4 data points

 What is trilinear interpolation?
● In n-D images, interpolation can be done on each
dimension independently:

– “bilinear” means linear interpolation in 2-D image

– “trilinear” means linear interpolation in 3-D image
Aliasing
 Aliasing

Undersampled Not undersampled

 Convolution
● Convolution mimics Linear Time Invariant (LTI) systems:
– Sampling
– Reconstruction
– Microscope lenses
– CCD sensor
– Electric circuits
– Radio
– …
 Convolution
● Sum of infinite number of kernels, weighted with input
function
● Or: for each output point, integral of multiplication of
mirrored kernel with input function

● For discrete image and discrete kernel: finite sum

∞ N −1
f  x  = ∫ f  h x− d  f [n] = ∑ f [k ] h[n−k ]
−∞ k =0
 Convolution Properties
● Linear:
– Scaling invariant: a A⊗B=a A⊗B

– Distributive: A⊗BC= A⊗B A⊗C

● Time Invariant: shift  A⊗B=shift  A⊗B

● Associative: A⊗B⊗C= A⊗B⊗C

● Commutative: A⊗B=B⊗ A
The Sampling Property of Convolution

Continuous
LTI
Continuous Continuous
image image

(if band-limited!)
reconstruction

sampling

Discrete
LTI
Discrete Discrete
image image
Convolution at the Image Edge
Convolution at the Image Edge

Mean padding Zero order hold

Convolution at the Image Edge

Periodic boundary condition Symmetric boundary condition

 Fourier Domain (or Frequency Domain)

FREQUENCY
impulse 1
SPATIAL

cosine 2 impulses

sine 2 impulses

box sinc
Notice the
symmetry!
sinc box

Gaussian Gaussian

white white
noise noise
 Fourier Transform in 2D, 3D, etc.
● Simplest thing there is! — the FT is separable:
– Perform transform along x-axis,
– Perform transform along y-axis of result,
– Perform transform along z-axis of result, (etc.)
● All the same properties apply as for 1-D Fourier
Transform
● Note error in the book (pg 59): 2D Fourier transform needs half
the plane, not only the first quadrant!
 What's more important?

Jean Baptiste Joseph Fourier

magnitude phase
What's more important?
 Properties of the Fourier Transform
● Linearity ℱ {c Ad B} = c ℱ {A}d ℱ {B}
● Convolution ℱ {A⊗B} = ℱ {A}⋅ℱ {B}

● Spatial scaling

● Spatial shift phase change

real, even
● Symmetry real, even
real, odd

imaginary, odd
The Shift Property

magnitude phase
 Revisiting Sampling
spatial domain frequency domain

continuous
function

sampling
function

sampled
function

sampled
function
 Revisiting Sampling
spatial domain frequency domain

continuous
function

sampled
function

continuous
image

discrete
image
 Basic Image Operations
● Image arithmetic:
– So trivial it's not even mentioned in the book
● Point operations (next):
– Function that maps image values
– Independent of spatial location
● Geometric transforms (Anders's lecture on Sept 29):
– Function that maps image coordinates
– Independent of image values
● Filtering (next 2 lectures):
– Function that changes image values based on local
neighbourhood
 Point Operations
● Apply a function (mapping) to each pixel in the image,
independent of pixel location
– Increase contrast
– Bring interesting grey-value range in view
– Make details visible
● Common:

– Change gamma: f  y = y
– Stretch
– Logarithmic stretch (e.g. for displaying Fourier Transform)
– Clipping
– Histogram equalization
 Gamma
● Increases contrast at one end of the range at the
expense of the other end of the range

=0.5 =2
 Clipping
● Brings values outside of the range to the range
boundary

f  y = { a ,
y ,
y a
otherwise

{
f  y = b ,
y ,
y b
otherwise

{
a , y a
f  y = b , y b
y , otherwise
 Histogram Equalization
● Mapping derived from histogram: tries to make
histogram as flat as possible
Mapping:
 Summary of Today’s Lecture
● Convolution describes Linear Time Invariant systems
● Sampling and reconstruction are LTI systems
● Imaging devices often are LTI systems
● Fourier Domain useful for analysing LTI systems
● Convolution in Spatial Domain is multiplication in
Fourier Domain

f  x ⊗h x  ℱ F H 

⇒