What’s an edge?

• Image is a function
• Edges are rapid changes in this function

Image derivatives

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

Image derivatives

• Recall:
• Want smoothing too!

Laplacian (2nd derivative)!

• Crosses zero at extrema
• Recall:
• Laplacian:
• Again, have to�estimate f’’(x):

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

​

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

• =

σ = 1

σ = 2

DoGs

Another approach: gradient magnitude

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

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

Smooth image

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

• You know how to do this, gaussians!

Gradient magnitude and direction

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

• Sobel filter

Non-maximum suppression

Non-maximum suppression

Non-maximum suppression

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

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?

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)

Canny Edge Detection

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

Features!

• Highly descriptive local regions
• Ways to describe those regions
• Useful for:
• Matching
• Recognition
• Detection

How to panorama

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

How close are two patches?

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

How can we find unique patches?

• Sky: bad
• Very little variation
• Could match any other sky

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

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

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?)

Self-difference

Sky: low everywhere

Self-difference

Edge: low along edge

Self-difference

Corner: mostly high

Self-difference

Sky: low everywhere

Edge: low along edge

Corner: mostly high

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

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!

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

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

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

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)

Ok, we found corners, now what?

• Need to match image patches to each other
• Need to figure out transform between images

Ok, we found corners, now what?

• Need to match image patches to each other
• What is a patch? How do we look for matches? Pixels?
• Need to figure out transform between images
• How can we transform images?
• How do we solve for this transformation given matches?

Matching patches: descriptors!

• We want a way to represent an image patch
• Can be very simple, just pixels!
• Finding matching patch is easy, distance metric:
• Σ_x,y (I(x,y) - J(x,y))²
• What problems are there with just using pixels?

Matching patches: descriptors!

• We want a way to represent an image patch
• Can be very simple, just pixels!
• Finding matching patch is easy, distance metric:
• Σ_x,y (I(x,y) - J(x,y))²
• What problems are there with just using pixels?

Matching patches: descriptors!

• We want a way to represent an image patch
• Can be very simple, just pixels!
• Finding matching patch is easy, distance metric:
• Σ_x,y (I(x,y) - J(x,y))²
• What problems are there with just using pixels?
• Descriptors can be more complex
• Gradient information
• How much context?
• Edges, etc. we’ll talk more about descriptors later!

Matching patches: descriptors!

• Already have our patches that are likely “unique”-ish
• Loop over good patches in one image
• Find best match in other image
• Do something with them?

How can we transform images?

• Need to warp one image into the other
• Many different image transforms
• Nested hierarchy of transformations
• Need to learn some new notation to make math easier!

How can we transform images?

• x is a point in our image where:
• x = (x, y) or in matrix terms

Say we want new coordinate system

• Map points from one image into another
• Often we can use matrix operations
• Given a point x, map to new point x’ using M

Scaling is just a matrix operation

• Map points from one image into another
• Often we can use matrix operations
• Given a point x, map to new point x’ using M

Translation is harder...

• x’ = M x
• Want to move x’ by dx and y’ by dy
• How do we pick M?
• Can only add up multiples of x or y
• No easy way to add a constant!

Translation: add another row

• x̄ is x but with an added 1
• Augmented vector

Translation: add another row

• x̄ is x but with an added 1
• Augmented vector
• Now translation is easy

Reminder, I = Identity

Common to just use I as a generic, whatever size identity fits here.

Translation: add another row

• x̄ is x but with an added 1
• Augmented vector
• Now translation is easy

Translation: add another row

• x̄ is x but with an added 1
• Augmented vector
• Now translation is easy
• x’ = 1*x + 0*y + dx*1
• y’ = 0*x + 1*y + dy*1

Translation: add another row

• x̄ is x but with an added 1
• Augmented vector
• Now translation is easy
• x’ = 1*x + 0*y + dx*1
• y’ = 0*x + 1*y + dy*1

Euclidean: rotation + translation

• Want to translate and rotate at same time
• Still just matrix operation

Euclidean: rotation + translation

• Want to translate and rotate at same time
• Still just matrix operation

Euclidean: rotation + translation

• Want to translate and rotate at same time
• Still just matrix operation
• R is rotation matrix, t is translation

Euclidean: rotation + translation

• Want to translate and rotate at same time
• Still just matrix operation
• R is rotation matrix, t is translation

Similarity: scale, rotate, translate

Similarity: scale, rotate, translate

Similarity: scale, rotate, translate

Affine: scale, rotate, translate, shear

Affine: scale, rotate, translate, shear

Affine: scale, rotate, translate, shear

General case of 2x3 matrix

Combinations are still affine

Say you want to translate, then rotate, then translate back, then scale.

x’ = S t R t x̄ = M x̄,

If M = (S t R t)

M is still affine transformation

Wait, but these are all 2x3, how to we multiply them together?

Added row to transforms

Projective transform

• AKA perspective transform or homography
• Wait but affine was any 2x3 matrix...

Need some new coordinates!

• Homogeneous coordinate system
• Useful because we can do this kind of transform
• Each point in 2d is actually a vector in 3d
• Equivalent up to scaling factor
• Have to normalize to get back to 2d

Why does this make sense?

• Remember our pinhole camera model
• Every point in 3d projects onto our viewing plane through our aperture
• Points along a vector are indistinguishable

Projective transform

• AKA perspective transform or homography
• Wait but affine was any 2x3 matrix…
• Homography is general 3x3 matrix
• Multiplication by scalar is equivalent

Projective transform

• AKA perspective transform or homography
• Wait but affine was any 2x3 matrix…
• Homography is general 3x3 matrix
• Multiplication by scalar: equivalent projection
• 3*H ~ H

Using homography to project point

• Multiply x~ by H~ to get x’~
• Convert to x’ by dividing by w’~

Lots to choose from

• What do each of them do?
• Which is right for panorama stitching?

How hard are they to recover?

Lots to choose from

Say we want affine transformation

• Have our matched points
• Want to estimate A that maps from x to x’
• xA = x’

Say we want affine transformation

• Have our matched points
• Want to estimate A that maps from x to x’
• xA = x’
• How many degrees of freedom?

Say we want affine transformation

• Have our matched points
• Want to estimate A that maps from x to x’
• xA = x’
• How many degrees of freedom?
• 6
• How many knowns do we get with one match? mX = n

Say we want affine transformation

• Have our matched points
• Want to estimate A that maps from x to x’
• xA = x’
• How many degrees of freedom?
• 6
• How many knowns do we get with one match? mA = n
• 2
• n_x = a₀₀*m_x + a₀₁*m_y + a₀₂*1
• n_y = a₁₀*m_x + a₁₁*m_y + a₁₂*1

Say we want affine transformation

• How many knowns do we get with one match? mA = n
• n_x = a₀₀*m_x + a₀₁*m_y + a₀₂*1
• n_y = a₁₀*m_x + a₁₁*m_y + a₁₂*1
• Solve M a = b
• M^T M a = M^T b
• a = (M^T M)^-1 M^T b
• Still works if overdetermined
• WHY???