3 of 111

Resize 4x4 -> 7x7

Create our new image
Match up coordinates

4 of 111

Resize 4x4 -> 7x7

Create our new image
Match up coordinates

4/7 X - 3/14 = Y

Iterate over new pts

Map to old coords

5 of 111

Resize 4x4 -> 7x7

Create our new image
Match up coordinates

4/7 X - 3/14 = Y

Iterate over new pts

Map to old coords
(1, 3) -> (5/14, 7/14)
Interpolate old values

q = (166, 172.5, 100)

6 of 111

Resize 4x4 -> 7x7

Create our new image
Match up coordinates

4/7 X - 3/14 = Y

Iterate over new pts

Map to old coords
(1, 3) -> (5/14, 7/14)
Interpolate old values

q = (166, 172.5, 100)

Fill in the rest

7 of 111

Different methods

8 of 111

For shrinking interpolation bad, averaging good

“interpolation”

averaging

9 of 111

Convolution: Weighted sum over pixels

12 of 111

Cross-Correlation vs Convolution

13 of 111

Cross-Correlation vs Convolution

Do this in HW!

14 of 111

Cross-Correlation vs Convolution

These are nicer mathematically

15 of 111

So what can we do with these convolutions anyway?

Mathematically: all the nice things

Commutative

A*B = B*A

Associative

A*(B*C) = (A*B)*C

Distributes over addition

A*(B+C) = A*B + A*C

Plays well with scalars

x(A*B) = (xA)*B = A*(xB)

16 of 111

So what can we do with these convolutions anyway?

This means some convolutions decompose:

2d gaussian is just composition of 1d gaussians

Faster to run 2 1d convolutions

17 of 111

So what can we do with these convolutions anyway?

Blurring
Sharpening
Edges
Features
Derivatives
Super-resolution
Classification
Detection
Image captioning
...

18 of 111

So what can we do with these convolutions anyway?

Blurring
Sharpening
Edges
Features
Derivatives
Super-resolution
Classification
Detection
Image captioning
...

All of computer vision

is convolutions

(basically)

19 of 111

So what can we do with these convolutions anyway?

Blurring
Sharpening
Edges
Features
Derivatives
Super-resolution
Classification
Detection
Image captioning
...

All of computer vision

is convolutions

(basically)

20 of 111

What’s an edge?

Image is a function
Edges are rapid changes in this function

21 of 111

What’s an edge?

Image is a function
Edges are rapid changes in this function

22 of 111

Finding edges

Could take derivative
Edges = high response

23 of 111

Image derivatives

Recall:

We don’t have an “actual”�Function, must estimate
Possibility: set h = 1
What will that look like?

24 of 111

Image derivatives

Recall:

We don’t have an “actual”�Function, must estimate
Possibility: set h = 1
What will that look like?

25 of 111

Image derivatives

Recall:

We don’t have an “actual”�Function, must estimate
Possibility: set h = 2
What will that look like?

26 of 111

Image derivatives

Recall:

We don’t have an “actual”�Function, must estimate
Possibility: set h = 2
What will that look like?

27 of 111

Images are noisy!

28 of 111

But we already know how to smooth

* =

29 of 111

But we already know how to smooth

* =

30 of 111

Smooth first, then derivative

31 of 111

Smooth first, then derivative

32 of 111

Smooth first, then derivative

33 of 111

Smooth first, then derivative

34 of 111

Smooth first, then derivative

35 of 111

Smooth first, then derivative

36 of 111

Smooth first, then derivative

37 of 111

Smooth first, then derivative

38 of 111

Smooth first, then derivative

39 of 111

Smooth first, then derivative

40 of 111

Smooth first, then derivative

41 of 111

Sobel filter! Smooth & derivative

42 of 111

Image derivatives

Recall:

Want smoothing too!

43 of 111

Finding edges

Could take derivative
Find high responses
Sobel filters!
But…

44 of 111

Finding edges

Could take derivative
Find high responses
Sobel filters!
But…
Edges go both ways
Want to find extrema

45 of 111

2nd derivative!

Crosses zero at extrema

46 of 111

Laplacian (2nd derivative)!

Crosses zero at extrema
Recall:

Laplacian:

Again, have to�estimate f’’(x):

47 of 111

Laplacians

Laplacian:

48 of 111

Laplacians

Laplacian:

Measures the divergence of the gradient

Flux of gradient vector field through small area

55 of 111

Laplacians

Laplacian:

56 of 111

Laplacians

Laplacian:

57 of 111

Laplacians

Laplacian:

58 of 111

Laplacians

Laplacian:

59 of 111

Laplacians

Laplacian:

Negative Laplacian, -4 in middle
Positive Laplacian --->

60 of 111

Laplacians also sensitive to noise

Again, use gaussian smoothing
Can just use one kernel since convs commute
Laplacian of Gaussian, LoG
Can get good approx. with�5x5 - 9x9 kernels

61 of 111

Another edge detector:

Image is a function:

Has high frequency and low frequency components
Think in terms of fourier transform

Edges are high frequency changes
Maybe we want to find edges of a specific size (i.e. specific frequency)

62 of 111

Difference of Gaussian (DoG)

Gaussian is a low pass filter
Strongly reduce components with frequency f < σ
(g*I) low frequency components
I - (g*I) high frequency components
g(σ1)*I - g(σ2)*I

Components in between these frequencies

g(σ1)*I - g(σ2)*I = [g(σ1) - g(σ2)]*I

63 of 111

Difference of Gaussian (DoG)

g(σ1)*I - g(σ2)*I = [g(σ1) - g(σ2)]*I

σ = 2

σ = 1

64 of 111

Difference of Gaussian (DoG)

g(σ1)*I - g(σ2)*I = [g(σ1) - g(σ2)]*I
This looks a lot like our LoG!
(not actually the same but similar)

65 of 111

DoG (1 - 0)

66 of 111

DoG (2 - 1)

67 of 111

DoG (3 - 2)

68 of 111

DoG (4 - 3)

69 of 111

Another approach: gradient magnitude

Don’t need 2nd derivatives
Just use magnitude of gradient

70 of 111

Another approach: gradient magnitude

Don’t need 2nd derivatives
Just use magnitude of gradient
Are we done? No!

71 of 111

Another approach: gradient magnitude

Don’t need 2nd derivatives
Just use magnitude of gradient
Are we done? No!

72 of 111

What we really want: line drawing

73 of 111

Canny Edge Detection

http://bigwww.epfl.ch/demo/ip/demos/edgeDetector/

Your first image processing pipeline!

Old-school CV is all about pipelines

Algorithm:

Smooth image (only want “real” edges, not noise)
Calculate gradient direction and magnitude
Non-maximum suppression perpendicular to edge
Threshold into strong, weak, no edge
Connect together components

74 of 111

Smooth image

http://bigwww.epfl.ch/demo/ip/demos/edgeDetector/

You know how to do this, gaussians!

75 of 111

Gradient magnitude and direction

http://bigwww.epfl.ch/demo/ip/demos/edgeDetector/

Sobel filter

76 of 111

Non-maximum suppression

http://bigwww.epfl.ch/demo/ip/demos/edgeDetector/

Want single pixel edges, not thick blurry lines
Need to check nearby pixels
See if response is highest

77 of 111

Non-maximum suppression

78 of 111

Non-maximum suppression

79 of 111

Non-maximum suppression

80 of 111

Non-maximum suppression

81 of 111

Non-maximum suppression

82 of 111

Non-maximum suppression

83 of 111

Non-maximum suppression

84 of 111

Non-maximum suppression

http://bigwww.epfl.ch/demo/ip/demos/edgeDetector/

85 of 111

Threshold edges

http://bigwww.epfl.ch/demo/ip/demos/edgeDetector/

Still some noise
Only want strong edges
2 thresholds, 3 cases

R > T: strong edge
R < T but R > t: weak edge
R < t: no edge

Why two thresholds?

86 of 111

Connect ‘em up!

http://bigwww.epfl.ch/demo/ip/demos/edgeDetector/

Strong edges are edges!
Weak edges are edges �iff they connect to strong
Look in some neighborhood�(usually 8 closest)

87 of 111

Canny Edge Detection

http://bigwww.epfl.ch/demo/ip/demos/edgeDetector/

Your first image processing pipeline!

Old-school CV is all about pipelines

Algorithm:

Smooth image (only want “real” edges, not noise)
Calculate gradient direction and magnitude
Non-maximum suppression perpendicular to edge
Threshold into strong, weak, no edge
Connect together components
Tunable: Sigma, thresholds

88 of 111

Canny Edge Detection

http://bigwww.epfl.ch/demo/ip/demos/edgeDetector/

89 of 111

What else is there?

90 of 111

So what can we do with these convolutions anyway?

Blurring
Sharpening
Edges
Features
Derivatives
Super-resolution
Classification
Detection
Image captioning
...

91 of 111

Features!

Highly descriptive local regions
Ways to describe those regions
Useful for:

Matching
Recognition
Detection

92 of 111

What makes a good feature?

Want to find patches in image that are useful or have some meaning
For objects, want a patch that is common to that object but not in general
For panorama stitching, want patches that we can find easily in another image of same place
Good features are unique!

Can find the “same” feature easily
Not mistaken for “different” features

93 of 111

How close are two patches?

Sum squared difference
Images I, J
Σ_x_,y (I(x,y) - J(x,y))²

94 of 111

How can we find unique patches?

Say we are stitching a panorama
Want patches in image to match to other image
Need to only match one spot

95 of 111

How can we find unique patches?

Sky: bad

Very little variation
Could match any other sky

96 of 111

How can we find unique patches?

Sky: bad

Very little variation
Could match any other sky

Edge: ok

Variation in one direction
Could match other patches�along same edge

97 of 111

How can we find unique patches?

Sky: bad

Very little variation
Could match any other sky

Edge: ok

Variation in one direction
Could match other patches�along same edge

Corners: good!

Only one alignment matches

98 of 111

How can we find unique patches?

Want a patch that is unique in the image
Can calculate distance between patch and every other patch, lot of computation

99 of 111

How can we find unique patches?

Want a patch that is unique in the image
Can calculate distance between patch and every other patch, lot of computation
Instead, we could think about auto-correlation:

How well does image match shifted version of itself?

Σ_dΣ_x,y (I(x,y) - I(x+d_x,y+d_y))²

Measure of self-difference (how am I not myself?)

100 of 111

Self-difference

Sky: low everywhere

101 of 111

Self-difference

Edge: low along edge

102 of 111

Self-difference

Corner: mostly high

103 of 111

Self-difference

Sky: low everywhere

Edge: low along edge

Corner: mostly high

104 of 111

Self-difference is still expensive

Σ_dΣ_x,y (I(x,y) - I(x+d_x,y+d_y))²
Lots of summing
Need an approximation

If you want the mathy details, Szeliski pg 212

105 of 111

Approximate self-difference

Look at nearby gradients I_x and I_y
If gradients are mostly zero, not a lot going on

Low self-difference

If gradients are mostly in one direction, edge

Still low self-difference

If gradients are in twoish directions, corner!

High self-difference, good patch!

106 of 111

Approximate self-difference

How do we tell what’s going on with gradients?
Eigen vectors/values!
Need structure matrix for patch, just a weighted sum of nearby gradient information

Not as complex as it looks, weighted sum of gradients near pixel

107 of 111

Structure matrix

Weighted sum of gradient information

| Σ_iw_iI_x(i)I_x(i) Σ_iw_iI_x(i)I_y(i) |
| Σ_iw_iI_x(i)I_y(i) Σ_iw_iI_y(i)I_y(i) |

Can use Gaussian weighting (so many gaussians)
Eigen vectors/values of this matrix summarize the distribution of the gradients nearby
λ₁and λ₂ are eigenvalues

λ₁and λ₂ both small: no gradient
λ₁>> λ₂: gradient in one direction
λ₁and λ₂ similar: multiple gradient directions, corner

108 of 111

Estimating smallest eigen value

A few methods:

det(S) = λ₁*λ₂
trace(S) = λ₁+λ₂

det(S) - α trace(S)² = λ₁λ₂ - α(λ₁+λ₂)²
det(S) / trace(S) = λ₁λ₂/(λ₁+λ₂)
If these estimates are large, λ₂ is large

109 of 111

Harris Corner Detector

Calculate derivatives I_x and I_y
Calculate 3 measures I_xI_x, I_yI_y, I_xI_y
Calculate weighted sums

Want a weighted sum of nearby pixels, guess what this is?
Gaussian!

Estimate response based on smallest eigen value
Non-max suppression (just like canny)

1 of 111

2 of 111

3 of 111

4 of 111

5 of 111

6 of 111

7 of 111

8 of 111

9 of 111

10 of 111

11 of 111

12 of 111

13 of 111

14 of 111

15 of 111

16 of 111

17 of 111

18 of 111

19 of 111

20 of 111

21 of 111

22 of 111

23 of 111

24 of 111

25 of 111

26 of 111

27 of 111

28 of 111

29 of 111

30 of 111

31 of 111

32 of 111

33 of 111

34 of 111

35 of 111

36 of 111

37 of 111

38 of 111

39 of 111

40 of 111

41 of 111

42 of 111

43 of 111

44 of 111

45 of 111

46 of 111

47 of 111

48 of 111

49 of 111

50 of 111

51 of 111

52 of 111

53 of 111

54 of 111

55 of 111

56 of 111

57 of 111

58 of 111

59 of 111

60 of 111

61 of 111

62 of 111

63 of 111

64 of 111

65 of 111

66 of 111

67 of 111

68 of 111

69 of 111

70 of 111

71 of 111

72 of 111

73 of 111

74 of 111

75 of 111

76 of 111

77 of 111

78 of 111

79 of 111

80 of 111