2/16/2021
CSE 473/573
Introduction to Computer Vision and Image Processing
‘-
FEATURE EXTRACTION
‘-
1
2/16/2021
Filters for features
• Previously, thinking of filtering as
a way to remove or reduce noise
• Now, consider how filters will
allow us to abstract higher-level ‘- “features”.
• Map raw pixels to an intermediate representation that will be used for subsequent processing
• Goal: reduce amount of data, discard redundancy, preserve what’s useful
3
Template matching
• Filters as templates:
Note that filters look like the effects they are intended to find — “matched filters”
‘-
• Use normalized cross-correlation score to find a given pattern (template) in the image.
• Szeliski Eq. 8.11
• Normalization needed to control for relative brightness’s.
4
2
2/16/2021
Template matching
Scene
‘-
Template (mask)
A toy example
5
Template matching
Detected template
‘-
Template
Is there only one match? What if the pattern is not exact?
6
3
2/16/2021
Correlation of Template and Imgae
‘-
Detected template Correlation map
7
Where’s Waldo?
‘-
Template
Scene
8
4
2/16/2021
Where’s Waldo?
‘-
Template
Scene
9
Where’s Waldo?
‘-
Detected template Correlation map
10
5
2/16/2021
Template matching
Scene
‘-
Template
What if the template is not identical to some sub image in the scene?
11
Template matching
Detected template
‘-
Template
Match can be meaningful, if scale, orientation, and general appearance is right.
12
6
2/16/2021
But what if it is not?
• We need more flexible, and powerful and forgiving representations
‘-
13
Image Representations: Histograms
‘-
Global histogram
• Represent distribution of features Space Shuttle • Color, texture, depth, … Cargo Bay
Images from Dave Kauchak
14
7
2/16/2021
Image Representations: Histograms
Histogram: Probability or count of data in each bin
• Joint histogram • Requires lots of data • Loss of resolution to
‘-
Marginal histogram
• Requires independent features • More data/bin than
Images from Dave Kauchak
avoid empty bins
joint histogram
15
Image Representations: Histograms
Clustering
‘-
EASE Truss Assembly
Use the same cluster centers for all images
Space Shuttle Cargo Bay
16
Images from Dave Kauchak
8
2/16/2021
Computing histogram distance
histint(hi,hj)1
Histogram intersection (assuming normalized histograms)
m1
1K [h(m)h(m)]2 2(hi,hj) i j
K
minh(m),h (m) ij
‘-
2m1 hi(m)hj(m) Chi-squared Histogram matching distance
Cars found by color histogram matching using chi-squared
17
Histograms: Implementation issues
• Quantization
• Grids: fast but applicable only with few dimensions
• Clustering: slower but can quantize data in higher dimensions
Few Bins
Need less data Coarser representation
‘-
• Matching
• Histogram intersection or Euclidean may be faster
• Chi-squared often works better
• Earth mover’s distance is good for when nearby bins represent similar values
Many Bins Need more data Finer representation
18
9
2/16/2021
What kind of things do we compute histograms of?
• Color
‘-
L*a*b* color space HSV color space
• Texture (filter banks or HOG over regions)
19
What kind of things do we compute histograms of?
• Histograms of oriented gradients
‘-
SIFT – Lowe IJCV 2004
20
10
2/16/2021
Edge detection
• Goal: map image from 2D array of pixels to a set of curves
or line segments or contours.
• Why?
‘-
Figure from J. Shotton et al., PAMI 2007
• Main idea: look for strong gradients, post-process
21
What can cause an edge?
Reflectance change: appearance information, texture
Change in surface orientation: shape
Depth discontinuity: object boundary
‘-
Cast shadows
22
11
2/16/2021
Contrast and invariance
‘-
23
Recall : Images as functions • Edges look like steep cliffs
‘-
24
Source: S. Seitz
12
2/16/2021
Derivatives and edges
An edge is a place of rapid change in the image intensity function.
image
intensity function (along horizontal scanline)‘-
first derivative
edges correspond to extrema of derivative Source: L. Lazebnik 25
Differentiation and convolution
For 2D function, f(x,y), the partial derivative is:
f(x,y)lim f(x,y)f(x,y) x0
For discrete data, we can approximate using finite differences:
f(x,y) f(x1,y)f(x,y) x 1
‘-
To implement above as convolution, what would be the associated filter?
26
13
2/16/2021
Partial derivatives of an image
f (x, y) f (x, y) x ‘- y
? or
-1
1
1
-1
-1
1
Which shows changes with respect to x?
(showing flipped filters)
27
Assorted finite difference filters
‘-
28
14
2/16/2021
Image gradient
The gradient of an image:
The gradient points in the direction of most rapid change in intensity
‘-
The gradient direction (orientation of edge normal) is given by: The edge strength is given by the gradient magnitude
29
Slide credit S. Seitz
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?
30
15
2/16/2021
Solution: smooth first
‘-
Where is the edge? Look for peaks in
31
Derivative theorem of convolution
Differentiation property of convolution.
‘-
32
16
2/16/2021
Derivative of Gaussian filter
(Ig)h I(gh)
0.0030 0.0133 0.0219 0.0133 0.0030 0.0133 0.0596 0.0983 0.0596 0.0133 0.0219 0.0983 0.1621 0.0983 0.0219
‘-
1 1 33
0.0133 0.0596 0.0983 0.0596 0.0133
0.0030 0.0133 0.0219 0.0133 0.0030
Derivative of Gaussian filters
x-direction
‘-
y-direction
34
Source: L. Lazebnik
17
2/16/2021
Laplacian of Gaussian
Consider
‘-
Laplacian of Gaussian operator
Where is the edge? Zero-crossings of bottom graph 35
2D edge detection filters
‘-
• is the Laplacian operator:
Laplacian of Gaussian
Gaussian derivative of Gaussian
36
18
2/16/2021
Mask properties
• Smoothing
• Values positive
• Sum to 1constant regions same as input
• Amount of smoothing proportional to mask size
• Remove “high-frequency” components; “low-pass” filter
‘-
• Derivatives
• Opposite signs used to get high response in regions of high contrast • Sum to 0no response in constant regions
• High absolute value at points of high contrast
• Filters act as templates
• Highest response for regions that “look the most like the filter” • Dot product as correlation
37
Gradients -> edges
‘-
2. Edge enhancement: filter for contrast
3. Edge localization
Determine which local maxima from filter output are actually edges vs. noise
• Threshold, Thin
Primary edge detection steps:
1. Smoothing: suppress noise
38
19
2/16/2021
Smoothing with a Gaussian
Recall: parameter σ is the “scale” / “width” / “spread” of the Gaussian kernel, and controls the amount of smoothing.
‘-
…
39
Effect of σ on derivatives
‘-
σ = 1 pixel
The apparent structures differ depending on
Gaussian’s scale parameter.
Larger values: larger scale edges detected Smaller values: finer features detected
σ = 3 pixels
40
20
2/16/2021
So, what scale to choose? It depends what we’re looking for.
‘-
Too fine of a scale…can’t see the forest for the trees.
Too coarse of a scale…can’t tell the maple grain from the cherry.
41
Thresholding
• Choose a threshold value t
• Set any pixels less than t to zero (off)
• Set any pixels greater than or equal to t to one (on) ‘-
42
21
2/16/2021
Original image
‘-
43
Gradient magnitude image
‘-
44
22
2/16/2021
Thresholding gradient with a lower threshold
‘-
45
Thresholding gradient with a higher threshold
‘-
46
23
2/16/2021
Canny edge detector
• • •
•
Filter image with derivative of Gaussian
Find magnitude and orientation of gradient
Non-maximum suppression:
• Thin multi-pixel wide “ridges” down to single pixel
width
‘-
Linking and thresholding (hysteresis):
• Define two thresholds: low and high
• Use the high threshold to start edge curves and the low threshold to continue them
Source: D. Lowe, L. Fei-Fei
47
The Canny edge detector
original image (Lena)
‘-
48
24
2/16/2021
The Canny edge detector
‘-
norm of the gradient
49
The Canny edge detector
‘-
thresholding
50
25
2/16/2021
The Canny edge detector
‘-
How to turn these thick regions of the gradient into curves?
51
thresholding
Non-maximum suppression
Check if pixel is local maximum along gradient direction, select single max across width of the edge
• requires checking interpolated pixels p and r ‘-
52
26
2/16/2021
The Canny edge detector
‘-
thinning (non-maximum suppression)
Problem: pixels along this edge didn’t survive the thresholding
53
Hysteresis thresholding
• Check that maximum value of gradient value is sufficiently large
• drop-outs? use hysteresis
‘-
‐ use a high threshold to start edge curves and a low threshold to continue them.
Source: S. Seitz
54
27
2/16/2021
Hysteresis thresholding
original image
‘-
high threshold (strong edges)
low threshold (weak edges)
hysteresis threshold
55
Source: L. Fei-Fei
Object boundaries vs. edges
‘-
Background Texture
Shadows
56
28
2/16/2021
Edge detection is just the beginning…
Berkeley segmentation database:
http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/segbench/
‘-
image human segmentation
gradient magnitude Source: L. Lazebnik
57
Project #1: Optical Character Recognition
• Enrollment
• Given a set of characters to recognize, enroll them • Feature Extraction
• Templates are the most straight forward and will earn you UP TO
90% – Very Slow
‘-
• Detection
• Given a gray scale image, find candidate characters
• Connected Component Analysis – Szeliski 3.3.4 – can be slow
• Classification/Recognition
• Determine if candidates match enrolled characters
58
29
2/16/2021
Next Class: Pyramids
‘-
59
30