Image processing

Jorge s. Marques, José Santos-Victor, 2018 1

what is an image?

Digital Camera

We’ll focus on these in this class

(More on this process later) The Eye

Jorge s. Marques, José Santos-Victor, 2018 Source: A. Efros 2
 images: what are they?

Jorge s. Marques, José Santos-Victor, 2018 3

what is shown in this image?

What is this?

Jorge s. Marques, José Santos-Victor, 2018 4

 what is an image

images describe the evolution of physical variables (intensity, color, reflectance,

condutivity) in a plane or in a 3D volume.

Jorge s. Marques, José Santos-Victor, 2018 5

coordinate systems

y
y

x
x x

most common choice

Jorge s. Marques, José Santos-Victor, 2018 6
 discrete images

Most electronic sensors produce discrete images defined on a grid of points

42 45 49 57 65 54 66 63 42 64 95
73 72 68 67 69 75 59 62 55 35 37
82 83 83 84 85 81 79 90 77 76 73

n 96
93
95
91
95
93
92
95
90
95
93
96
88
97
79
104
95
94
88
96
93
104
110 107 102 104 110 107 103 102 110 97 106
109 112 113 109 105 107 101 108 116 115 111
f(m,n) 109 107 109 112 113 101 119 128 143 121 122
CCD sensor m 114 114 115 115 113 119 146 154 115 110 116
125 125 120 118 121 160 140 112 118 116 122
114 110 115 137 161 132 119 119 107 124 120

pixel

pixel – picture element each pixel is characterized by its

position and value
Jorge s. Marques, José Santos-Victor, 2018 7

image types
gray scale images binary images multi-spectral images

color images

Jorge s. Marques, José Santos-Victor, 2018 8

 topological concepts

what is the neighborhood of a pixel(i,j) ?

neighborhood 4
N4 (i , j ) = {(i - 1, j ), (i + 1, j ), (i , j - 1), (i , j + 1)}

neighborhood 8
N8 (i , j ) = {(i - 1, j - 1), (i - 1, j ), (i - 1, j + 1), (i , j - 1),
(i , j + 1), (i + 1, j - 1), (i + 1, j ), (i + 1, j + 1)}

Jorge s. Marques, José Santos-Victor, 2018 9

connectivity

y
x are x, y connected?

NO
binary image

connectivity: two pixels x, y of a binary image u(m,n) are connected iif (if and
only if) there a sequence of points z1, z2, ..., zn:
1 n
z = x, z = y
i i +1
z ,z are neighbors "i Î { 1, 2, ..., n - 1}
i
u( z ) = 1 "i = 1,..., n

Jorge s. Marques, José Santos-Victor, 2018 10

 regions

regions

Region R is a set of fully connected pixels i.e.,

"x, y Î R, x, y are connected

A maximal set of connected pixels is called a connected component.

Jorge s. Marques, José Santos-Victor, 2018 11

extraction of connected components

The algorithm assigns different labels to pixels belonging to different
connected components
If the neighbors have different
ssign the label of the previous labels create na equivalence
neighbors if they are equal table
1↔2

1 1
1 2 1 2
1 1 1 3 3 3
3 3

4↔5

4 4
5 5 5 5
5 5 5 5
5 5 5 5

Jorge s. Marques, José Santos-Victor, 2018 12

 boundary

The boundary of a region R is the set of R pixels

whose neighborhood is not contained in R.

Jorge s. Marques, José Santos-Victor, 2018 13

image filtering
Modify the pixels in an image based on some function
of a local neighborhood of each pixel

10 5 3 Some function
4 5 1 7
1 1 7
Local image data Modified image data

Jorge s. Marques, José Santos-Victor, 2018 Source: L. Zhang 14

 linear filtering

Jorge s. Marques, José Santos-Victor, 2018 15

examples
original blurred

sharpened edge preserving blurred

Jorge s. Marques, José Santos-Victor, 2018 16

 noise reduction

how can we remove the noise in

an (homogeneous) image?

idea: replace each pixel by an average

i +N j +N
g(i , j) = 1 å å f(k, l) N=1
( 2N +1)2 k = i - N l = j - N

mean filter
2N+1
N=2
2N+1

Jorge s. Marques, José Santos-Victor, 2018 17

gaussian filter
filtered image 2 2
- k +l
G(k , l ) = C e 2s 2
g(i , j) = å G(k - i,l - j)f(k , l)
k ,l

j j
f(i,j)
weighted average i i
g(i,j)

Jorge s. Marques, José Santos-Victor, 2018 18

 Gaussian filtering

orig. s=0.2

s=1 s=2

the gaussian filter destroys the transitions!!

Jorge s. Marques, José Santos-Victor, 2018 19

Mean vs. Gaussian filtering

Jorge s. Marques, José Santos-Victor, 2018 20

 smoothing with a Gaussian

s =0 s =1 s =3 s =6

Jorge s. Marques, José Santos-Victor, 2018 21

smoothing with a Gaussian

Recall: parameter σ is the “scale” / “width” / “spread” of the Gaussian
kernel, and controls the amount of smoothing.

Kristen Grauman, UT-

Austin

Jorge s. Marques, José Santos-Victor, 2018 22

 linear filtering
2D correlation

g (i , j ) = å M (k - i , l - j )f (k , l ) = M (i , j ) Ä f (i , j ) M(i , j ) mask
k,l

g(i , j ) = å h(i - k , j - l )f (k , l ) = h(i , j ) * f (i , j ) h(i , j ) = M(-i ,- j ) impulse response

k,l
2D convolution sum

mask / impulse response

j
f g

the mask/impulse response is shifted by an amount (i,j)

Jorge s. Marques, José Santos-Victor, 2018 23

separable filters

Separable filters have the following property:

M (i , j ) = M1(i ) M2 ( j ), h(i , j ) = h1(i ) h2 ( j )

Separable filters can be implemented in a very efficient way.

Algorithm:
1. filter all the image columns using filter h1 (1D)
2. filter all the lines of the previous image using filter h2 (1D)
original image column filtering line filtering

Jorge s. Marques, José Santos-Victor, 2018 24

 border effects

Jorge s. Marques, José Santos-Victor, 2018 25

matrix notation

Linear filtering can be written in matrix notation.

g = Hf g, f Î IR p , H Î IR p´ p

g, f are column vectors with all the pixel intensities;

H is a (huge) square matrix;
p is the number of pixels in the image.

This notation is very elegant but image filtering cannot be implemented in

this way.

Jorge s. Marques, José Santos-Victor, 2018 26

 examples

M(i,j) = 1 2 1 M(i,j) = -1 -2 -1
2 4 2 0 0 0
1 2 1 1 2 1

weighted average of vertical difference,

neighboring pixels horizontal mean

Jorge s. Marques, José Santos-Victor, 2018 27

example
J (m, n ) = h(m, n ) * I (m, n ) h(m, n ) = δ (m, n ) - G(m, n )

original filtered

Jorge s. Marques, José Santos-Victor, 2018 28

 1st order derivatives: gradient vector

gradient vector:

é ¶f ( x ) ù f(x) continuous image

é g ( x) ù
! g ( x ) = ê 1 ú = ê ¶f¶(xx ) ú
ëg2 ( x )û êê ¶y úú x=(x1,x2) – continuous variables
ë û

length and direction

|| g ( x ) ||= g12 ( x ) + g 22 ( x )

Ðg ( x ) = arctan g2( x )
1
( )
g (x)

Jorge s. Marques, José Santos-Victor, 2018

gradient discretization

1) Derivatives can be approximated by finite differences

-1
I (m + 1, n ) - I (m - 1, n )
g1(m, n ) » 0 -1 0 1
2 1
I (m, n + 1) - I (m, n - 1)
g 2 (m, n ) » Linear filtering!
2

2) a better choice: Sobel masks

-1 -2 -1 -1 0 1
0 0 0 -2 0 2
1 2 1 -1 0 1

High pass filtering in one direction, and low pass filtering in the orthogonal direction

Jorge s. Marques, José Santos-Victor, 2018 30

 example

Jorge s. Marques, José Santos-Victor, 2018 31

example

Jorge s. Marques, José Santos-Victor, 2018 32

 example: gradient

g1

g2 |g|

Jorge s. Marques, José Santos-Victor, 2018 33

effects of noise
• Consider a single row or column of the image
– Plotting intensity as a function of position gives a signal

Where is the edge?

Source: S. Seitz
Jorge s. Marques, José Santos-Victor, 2018 34
 solution: smooth first

Where is the edge? Look for peaks in Source: S. Seitz

Jorge s. Marques, José Santos-Victor, 2018 35

Derivative theorem of convolution

Slide credit Steve

Jorge s. Marques, JoséSeitz
Santos-Victor, 2018 36
 Laplacian of Gaussian
Consider

!(#)

Laplacian of Gaussian
operator

Where is the edge? Zero-crossings of bottom

Jorge s. Marques, José Santos-Victor, 2018 graph 37

2nd order derivatives: Laplacian filter

Laplacian of a 2D image

( "# ( "#
! " # $, & = + zero crossings are associated to transitions
($ " (& "
Since the derivatives increase noise, the image should first be filtered using a
Gaussian filter

! " * $, & ∗ # $, & = [! " * $, & ] ∗ # $, &

where

$" + &" 2
! "* $, & = − *($, &)
./ ."

Jorge s. Marques, José Santos-Victor, 2018 38

 Directional filters: Gabor filters
Some cells of the visual cortex are activated by directional stimula. Gabor filters
approximate the behavior of these cells.
Their impulse response is the multiplication of a sinusoid by a Gaussian
envelope in a rotated 2D space.

, , #+
# + + . ,% + 24 +6
ℎ" #, % = exp − cos 5
20 ,
#′, + . , %′, #′
ℎ, #, % = exp − , sin 24 + 6
20 5
rotation

# + = # cos : + % sin :
% + = −# sin : + % cos :
Jorge s. Marques, José Santos-Victor, 2018 39

Directional analysis: difference of Gaussians

Difference of Gaussians

10

12

2 4 6 8 10 12

Skin lesion – dermoscopy images

Barata, Transactions on Biomedical

Engineering, 2012

Jorge s. Marques, José Santos-Victor, 2018 40

 nonlinear filtering

Jorge s. Marques, José Santos-Victor, 2018 41

non-linear filtering

linear filters reduce noise but they destroy image contours.

Is it possible to solve this conflict i.e., removing the noise, preserving the
contours?

Jorge s. Marques, José Santos-Victor, 2018 42

 median filter …

Jorge s. Marques, José Santos-Victor, 2018 43

1D median filter

f g
g (n ) = median{ f (n - M ),..., f (n + M )}
filter

f 1 0 2 4 5 g 1
1 0

012 non linear!

example

Jorge s. Marques, José Santos-Victor, 2018 44

 2d median filter

f g
filter

g (m, n) = median{f (m - M , n - N ),...,f (m + M , n + N )}

Jorge s. Marques, José Santos-Victor, 2018 45

example

original image

Jorge s. Marques, José Santos-Victor, 2018 46

 sequence filtering

video sequence

time

median filter can be applied in space, in time or in space-time.

Jorge s. Marques, José Santos-Victor, 2018 47

example – time filtering

output: background image

Jorge s. Marques, José Santos-Victor, 2018 48

 non-linear diffusion

Jorge s. Marques, José Santos-Victor, 2018 49

non linear diffusion

Perona & Malik

Jorge s. Marques, José Santos-Victor, 2018

how is this possible? 50
 heat equation

!" " (, # temperature

= % & '"
!# *+ , *+ ,
& '" = +
*- + */ +

diffusion

Jorge s. Marques, José Santos-Victor, 2018 51

linear diffusion

t0=0 t1>0 t2>t1

||x||2
-
Gσ ( x ) = 1 e 2σ 2
Solution of heat equation:
2πσ 2
σ = 2t (check it!)

Jorge s. Marques, José Santos-Victor, 2018 52

 linear diffusion
%&
Definition: = '2&
%$

& (, 0 = +((), initial condition

This equation has a unique solution

(Gs * I )( x ) = ò Gs ( x - y )f ( y ) dy
ì f ( x) t =0
g ( x,t ) = í R2
î(G 2t * f )( x ) t > 0 -
||x||2
Gs ( x )= 1 e 2s 2
2ps 2

Gaussian filtering: beautiful!!

Linear diffusion leads to Gaussian filtering with parameter: ! = 2$

Jorge s. Marques, José Santos-Victor, 2018 53

gaussian filtering

time

Jorge s. Marques, José Santos-Victor, 2018 54

 Space-scale

Many images contain structures with different sizes. Therefore it is useful

to represent it as a family of images with increasingly less details.

Space scale of an image f(x) is a family of images indexed by a

parameter s, denoted as:
!" #, % ≥ 0
such that
!( # = #
!"*+ # = !" !+ # semi-group property

Jorge s. Marques, José Santos-Victor, 2018 55

Gaussian space-scale
The Gaussian space-scale is obtained by filtering the image using a
Gaussian kernel and changing the parameter s from 0 to infinity.
!" # = %" ∗ #

The semi-group property holds. Prove it !

Limitations:
- It destroys the contour information: how can we overcome this difficulty?
- Can be generated with a linear diffusion process

Jorge s. Marques, José Santos-Victor, 2018 56

 Generalization

g(x) - concentration

mass flows from regions of high concentration to regions with smaller concentration
taking the gradient opposite direction.
Fick’s law Mass conservation law
¶g j(x,t) – diffusion flux
j = -cÑg = -div j c(x,t) – diffusion coefficient
¶t g(x,t) – concentration

homogeneous material: constant diffusivity.

Perona & Malik: space dependent diffusivity
Idea: filter homogeneous regions and not transitions
Jorge s. Marques, José Santos-Victor, 2018 57

conductivity

conductivity (Perona & Malik) c

1

1
c( x,t ) =
2
1 + a Ñg ( x,t )
0 1 2 3 |Ñg|

Conductivity depends on the concentration at a given position and time instant,

and changes along the time.

In homogeneous regions (|Ñg|=0) and conductivity is constant c=1.

At the contour points, conductivity is almost zero.

Jorge s. Marques, José Santos-Victor, 2018 58

 non linear diffusion

Diffusion equation (Perona & Malik)

¶g 1
= div (c(x, t)Ñg) c( x,t ) =
2
¶t 1 + a Ñg ( x,t )

remark:
¶A ¶B
div v = + v = (A,B )
¶x ¶y

Jorge s. Marques, José Santos-Victor, 2018 59

discretization
Perona & Malik algorithm is based on a discretization of the diffusion equation in
which the partial derivatives are replaced by first order differences.

where
N um-1,n
,n = gm,n + l [cN ÑN g + cS ÑS g + cE ÑE g + cW ÑW g ]m,n
t +1 t t
gm 0 £ l £ 1/ 4
W E um,n+1
um,n-1
um,n

ÑNum,n = um-1,n - um,n ÑSum,n = um+1,n - um,n S

um+1,n
ÑE gm,n = gm,n+1 - gm,n ÑS gm,n = gm,n-1 - gm,n

cN m,n = g( (Ñg)m +1/ 2,n )fm,n cS m,n = g( (Ñg)m -1/ 2,n )

cE m,n = g( (Ñg)m,n -1/ 2 )fm,n cW m,n = g( (Ñg)m,n +1/ 2 )

Jorge s. Marques, José Santos-Victor, 2018 60

 example
original Gaussian filter Perona-Malik

Jorge s. Marques, José Santos-Victor, 2018 61

interpolation and pyramids

Jorge s. Marques, José Santos-Victor, 2018 62

 bilinear interpolation

!"#": % &, ( &, ( ∈ {0,1}

1

0 d
% 0, . = 1 − . % 0,0 + .% 0,1
h 1
% 1, . = 1 − . % 1,0 + .% 1,1

% 2, . = 1 − 2 % 0, . + 2% 1, .
1

0.8 Replacing
0.6

0.4 % 2, . = 1 − 2 1 − . % 0,0 + 1 − 2 .% 0,1

0.2 +2 1 − . % 1,0 + 2.% 1,1
0
1
0.5 1
0 0.5
0
-0.5 -0.5
-1 -1

Jorge s. Marques, José Santos-Victor, 2018 63

interpolation at equally spaced points

Sometimes we wish to increase the resolution of images. This can be
done by interpolation.
f(i)

! " = $ & ' ℎ(" − '+)

1D 0 1 2 3 i %
g(i)
f(i) d(i) g(i)
r h(i)
0 r 2r 3r i

"
! " = - " ∗ ℎ " = ∑ - 7 ℎ(" − 7)
- " = .& + " = '+
0 01ℎ2+3"42
= $ & ' ℎ(" − '+) 7 = '+
%

2D
! ", 9 = $ & ', ; ℎ(" − '+, 9 − ;+)
%,:
Jorge s. Marques, José Santos-Victor, 2018 64
 Interpolation results
filters bilinear bicubic (a=-1)

bicubic (a=-0.5) windowed sinc

extracted from Szeliski book

Jorge s. Marques, José Santos-Victor, 2018 65

decimation
Decimation reduces the image resolution by a factor k. It involves two
steps: 1) lowpass filtering (anti-aliasing) and 2) subsampling.

f(i)
f(i) d(i) g(i)
1D h(i) r
0 r 2r 3r i

d(i)
! " = $ & ' ℎ(" − ')
%
0 r 2r 3r i
g(i)
, " = !(-") = $ & ' ℎ(-" − ')
%
0 1 2 3 i

2D
, ", / = $ & ', 1 ℎ(-" − ', -/ − 1) , ", / = $ & ', 1 ℎ(" − '/-, / − 1/-)
%,0 %,0

Jorge s. Marques, José Santos-Victor, 2018 h(k,l) is the decimation kernel if h(k,l) is the interpolation kernel 66
 Gaussian pyramid (Burt & Adelson)

lowpass filter

!
!" 14641

Jorge s. Marques, José Santos-Victor, 2018 67

Laplacian pyramid (Burt & Adelson)

reconstruction

reconstruction

Block diagram

• perfect reconstruction
• inefficient representation

Jorge s. Marques, José Santos-Victor, 2018 Szeliski book 68

 Credits

Some slides are based on:

Richard Szeliski,
Computer Vision: Algorithms and Application,
Springer, 2011

Jorge s. Marques, José Santos-Victor, 2018 69