代写代考 EBU7240 Computer Vision

EBU7240 Computer Vision
Features: edges, corners
Semester 1
Changjae Oh

Derivatives and Edges
• Edges: intensity discontinuities ̶ Ramp edge
̶ Step edge
Ramp edge step edge Ramp edge step edge

Derivatives and Edges

Effects of Noise in Edge Detection
Intensity profile
Source: D. Hoiem

Effects of Noise in Edge Detection
With a little Gaussian noise
Source: D. Hoiem

Effects of Noise in Edge Detection • Consider a single row or column of the image
̶ Plotting intensity as a function of position
Where is the edge?
Source: S. Seitz

Effects of Noise in Edge Detection
• Difference filters respond strongly to noise
̶ Image noise results in pixels that look very different from their neighbors ̶ Generally, the larger the noise the stronger the response
• What can we do about it?
Source: D. Forsyth

Solution: Smooth First
d (fg) dx
Tofindedges,lookforpeaksin
d (fg) dx
Source: S. Seitz

Derivative Theorem of Convolution
• Differentiation is convolution, and convolution is associative:
• This saves us one operation: f
d (f g)= f  d g dx dx
Source: S. Seitz

off Between Smoothing and Localization
1 pixel 3 pixels 7 pixels
• Smoothed derivative removes noise, but blurs edge.
Source: D. Forsyth

Edge Detection: Derivative of Gaussian Filter
* [1 -1] =
Note) Sobel operators approximate the derivative of Gaussian filter in a simple form.

Edge Detection: • Sobel filter
𝛻𝐼=𝐼,𝐼 =𝑆∗𝐼,𝑆∗𝐼 𝑥𝑦𝑥𝑦

Sobel filter output
𝑀𝑥,𝑦= 𝐼2+𝐼2or𝐼 +|𝐼| 𝑥𝑦𝑥𝑦
For color image,
𝑀 𝑥,𝑦 = 𝑀𝑅 𝑥,𝑦 +𝑀𝐺 𝑥,𝑦 +𝑀𝐵 𝑥,𝑦 /3
Gaussian filtering is often applied as pre- processing.
1) Apply Gaussian filter 2) Apply Sobel filter

Edge Detection: • Laplacian filter
Laplacian Filter
More general form
For color image,
𝑂 𝑥,𝑦 = 𝑂𝑅 𝑥,𝑦 +𝑂𝐺 𝑥,𝑦 +𝑂𝐵 𝑥,𝑦 /3

Edge Detection:
Laplacian of Gaussian (
• Marr- (Laplacian of Gaussian: LoG)
1. Apply the Gaussian filter for removing unnecessary noise.
2. Apply the Laplacian filter
Without Gaussian With Gaussian smoothing smoothing

Canny Edge Detector
• The most popular method for edge detection
• Three criteria for edge detection
Low error rate of detection: finding all edges
Localization of edges: computing precise locations of edges Single response: returning a single pixel for a single edge
Input Image Filtering Image (Low-pass &
High-pass filters)
Non-maximum suppression & Double thresholding
Output Edge Map

Canny Edge Detector
Step 1) Image Gradient using Low-pass & High-pass filters
1. Apply low-pass and high-pass filters ex)
– Gaussian filter→Sobel filter (‘default implementation in OpenCV’) – 1D derivative of Gaussian filter
– Difference of Gaussian filter
2. Compute the magnitude and angle of edge
𝑀(𝑥,𝑦)= 𝐺2+𝐺2 𝑥𝑦
𝐴(𝑥,𝑦)=𝑡𝑎𝑛−1
𝛻𝐺=(𝐺,𝐺)= 𝜕𝐺,𝜕𝐺

Canny Edge Detector
Step 2) Non-maximum suppression
• Key idea: Survive only pixels with a larger edge magnitude 𝑀(𝑥, 𝑦) within a small window
𝑀(𝑥,𝑦)= 𝐺2+𝐺2 𝑥𝑦
𝐴(𝑥,𝑦)=𝑡𝑎𝑛−1
1. Within a small window (e.g. 3 × 3 window) centered at (𝑥, 𝑦),
find neighbor pixels in direction 𝐴(𝑥, 𝑦)
2. Compare the edge magnitudes 𝑀(𝑥, 𝑦) of these two neighbor pixels
• Procedure

Canny Edge Detector
• But, the image is a discrete signal. ̶ So, quantize the gradient direction
Gradient direction
𝐴(𝑥, 𝑦) = 𝑡𝑎𝑛−1

Canny Edge Detector Step 3) Double thresholding
Hysteresis thresholding (𝑇 , 𝑇 ) 𝐿𝐻
If 𝑀(𝑥, 𝑦) > 𝑇 , then (𝑥, 𝑦) is an edge 𝐻
If 𝑀 𝑥, 𝑦 < 𝑇 , then (𝑥, 𝑦) is NOT an edge 𝐿 ̶ If𝑇≤𝑀𝑥,𝑦≤𝑇, 𝐿𝐻 • If the neighboring pixels of (x,y) is an edge, then (𝑥, 𝑦) is an edge. • Otherwise,then(𝑥,𝑦)isNOTanedge. Canny Edge Detector Example original image (Lena) Compute Gradients X-Derivative of Gaussian Y-Derivative of Gaussian Gradient Magnitude Before Non max Suppression max Suppression Final Canny Edges • After applying Hysteresis thresholding (Double thresholding) Interest points 9300 Pkwy, Charlotte, NC Slides from , , and Corners: Applications • Corners are used for: Image alignment/3D reconstruction Find correspondences across different views Motion tracking/robot navigation Which points are good to track? Object recognition/Indexing and database retrieval Find patches likely to tell us something about object category Corner Detection: Basic Idea • We should easily recognize the point by looking through a small window • Shifting a window in any direction should give a large change in intensity “flat” region: no change in all di rections no change along the edge direction significant change in all directions Source: A. Efros Corner Detection: Mathematics Change in appearance of window w(x,y) for the shift [u,v]: E(u,v)=w(x,y)I(x+u,y+v)−I(x,y)2 x,y Corner Detection: Mathematics The quadratic approximation simplifies to where M is a second moment matrix computed from image derivatives: E(u,v)  [u v] M u  v  xxy M =w(x,y) I2 I I  x,y II I2 xy y Corners as Distinctive Interest Points II II M=w(x,y)x x x y Ix Iy  2 x 2 matrix of image derivatives (averaged in neighborhood of a point) Ix I Iy I x y IxIy II x y Corner Response Function R=det(M)−trace(M)2 = −( + )2 1212 α: constant (0.04 to 0.06) Note) The eigenvalues are not needed. Instead, we can use the determinant and trace of the second moment matrix. “Flat” region Detector: Procedure Step 1) Compute M matrix for each window to get their cornerness scores. Step 2) Find points whose surrounding window gave large corner response (R> threshold)
Step 3) Take the points of local maxima,
i.e., perform non-maximum suppression

Detector: Input
Performing corner detection to each image independently

Detector: Step 1)
Compute corner response R

Detector: Step 2)
Find points with large corner response: R>threshold

Detector: Step 3)
Take only the points of local maxima of R

Detector: Results
Advantages? Drawbacks?

Affine intensity change
𝐼 → 𝑎𝐼 + 𝑏
• Only derivatives are used
=> invariance to intensity shift: 𝐼 → 𝐼 + 𝑏
• Intensity scaling: 𝐼 → 𝑎𝐼
RR threshold
x (image coordinate) x (image coordinate)
• Partially invariant to affine intensity change
Slide from J. Hays

Image translation
• Derivatives and window function are shift-invariant
Corner location is covariant w.r.t. translation
Slide from J. Hays

Image rotation
Second moment ellipse rotates but its shape (i.e . eigenvalues) remains the same
Corner location is covariant w.r.t. rotation
Slide from J. Hays

All points will be classified as edges
Corner location is not covariant to scaling!
Slide from J. Hays

Not always the best
https://medium.com/pixel-wise/detect-those-corners-aba0f034078b

Corner detection: pros & cons
• Corner detection can localize in x-y, but not scale
Slide from J. Hays

• Edge detection
̶ Identify sudden changes (discontinuities) in an image
̶ Derivative of Gaussian, Sobel, Laplacian, Laplacian of Gaussian, Canny detector
• Canny edge detector
̶ The most popular edge detector
1. Applying low- and high-pass filtering
2. Non-maximum suppression
3. Double thresholding
• Harris corner detector
1. Compute the second moment matrix
2. Non-maximum suppression

Computer Vision
Features: SIFT, SURF, and matching
Semester 1
Changjae Oh

• Feature Descriptor
̶ Scale Invariant Feature Transform (SIFT) descriptor ̶ Speeded Up Robust Features (SURF) descriptor
• Feature Matching
̶ Nearest Neighbor (NN) Matching

Harris corner detector
Pros & Cons
Robust against shift/rotation transformations and brightness changes, Not robust against scale changes.
Solution: Scale invariant blob detector by SIFT
Scale Change
Scale-Controllable Kernel
→ LoG (DoG) Blob detector
[Ref: Distinctive Image Features from Scale-Invariant Keypoints, IJCV 2004]

• We want to extract keypoints with characteristic scales that are covariant with respect to the image transformation
detection with scale selection

Automatic scale selection
f (Ii1im (x,)) = f (Ii1im (x,))
How to find corresponding patch sizes? A: Blob detector

Basic idea
• Convolve the image with a “blob filter” at multiple scales and look for extre ma of filter response in the resulting scale space
T. Lindeberg, Feature detection with automatic scale selection, IJCV 30(2), pp 77-116, 1998

Blob detection
• Find maxima and minima of blob filter response in space and scale

Blob filter
• Laplacian of Gaussian
̶ Circularly symmetric operator for blob detection in 2D
2 g = 2 g + 2 g x2 y2

Laplacian of Gaussian (
2I(x,y) 2I(x,y)
x2 + y2 Laplacian
2 (GI)=(2 G)I
G(x,y)= 1 exp−x2+y2 22  22 
 2G 2G
2G=x2 +y2  
x2+y2−22  x2+y2 =  2 6  exp − 2 2 
LoG function
 : LoG Parameter

Recall: Edge detection
d2 fdx2 g
Second derivative of Gaussian (Laplacian)
Edge = zero crossing of second derivative
Source: S. Seitz

Laplacian of Gaussian (
• LoG applied on Edge
• LoG applied on Pulse (Blob):
̶ Superposition of two ripples, generating an extremal value at the center of the pulse (blob)
Convolving with a pulse signal, 1-D LoG generates an extremal pulse when its sigma matches the width of the pulse.
Slides from Won

normalized
Original signal
Unnormalized Laplacian response
Scale-normalized Laplacian response
Need to multiply σ2 to LoG for the scale normalization
Slides from Won

Blob Detection with 2 LoG filtered scale-space
Source: http://www.cs.utah.edu/~jfishbau/advimproc/project1/

(Difference of Gaussian)
Normalized LoG ≈(k-1) x Difference of Gaussian (DoG)
=2(G (x,y,)+G (x,y,)) xx yy
DoG=G(x,y,k)−G(x,y,)
0.3 0.2 0.1
0 -0.1 -0.2 -0.3 -0.4
• Use DoG instead of LoG
DoG(x, y, ) (k −1)LoG norm
=1,k=21/3 1.26 -5 -4 -3 -2 -1 0 1 2 3 4 5
1) Gaussian Filtering : G(x,y,σ), G(x,y,kσ)
2) Subtraction
D(x, y, )= I G(x, y,k )− I G(x, y, )
= I (G(x, y,k )−G(x, y, ))= I DoG(x, y,k, )

space blob detector: Example

SIFT descriptors
• Inspiration: complex neurons in the primary visual cortex
D. Lowe, Distinctive image features from scale-invariant keypoints, IJCV 60 (2), pp. 91-110, 2004

Step 1) Scale Space Extrema Detection
Scale-Space Extrema Detection
Detect the candidates of interest points, which are extrema points in the scale- space domains.
Scale-Space Extrema detection
Key Point Localization
Orientation Assignment
Key Point Descriptor Construction
Detector Descriptor
Source: D. Lowe

Step 1) Scale Space Extrema Detection
Ex) 2 Levels (S=2) 2 Octave
– Need to generate S+3=2+3=5 blurred images per octave
-k=21/S =21/2 =1.414
k =0.707  k=2 k=2.828
0 0 k0=1,4140 0 0 0 0
G(x,y,1.4140)− G(x,y,0)
G(x, y,20 )− G(x, y,1.4140 )
FirstOctave : -1
First Octave
Original Image
G(x, y,0 )− G(x, y,0.7070 )
G(x, y,2.8220 )− G(x, y,20 )
Starting Image
k =1,414 k =2 k =2.828 k =4 k =5.656
23 0000000000
Second Octave
G(x, y,20 )− G(x, y,5.656 0 )− Slides from Won
G(x,y,1.4140)
G(x, y,2.8280 )−
G(x,y,20)
G(x,y,4 )−
G(x, y,2.8280 )
G(x, y,40 )

Step 1) Scale Space Extrema Detection
Scale-Space Extrema Detection
– Compare a pixel with 26 pixels in current and adjacent scales (Green circles) – Select a pixel as an extrema if larger/smaller than neighboring 26 pixels
– Needs further localization and sampling
Source: D. Lowe

(1) Sub-pixel localization and removal of extrema points with low contrast:
Use Taylor series expansion of the
scale-space function D to find maximum of surface
) Key Point Localization
DT 1 2D D(X )= D + X + X T X
D and its derivatives are evaluated at the sample point
The sub-pixel location of the extremum
ˆ 2D−1 D X=−X2 X
The function value at the extremum, D(X ) 1 DT
D(X )= D + X ˆ 2Xˆ
Scale-Space Extrema detection
Key Point Localization
Orientation
Assignment
Key Point Descriptor Construction
If D(X ) Th, then discard the extremum.

Step 2) Key Point Localization
Scale-Space Extrema detection
Key Point Localization
Orientation
(2) Delete edge-like features by calculating the curvature H: Hessian matrix
Assignment
Key Point Descriptor Construction
D D 2 2 1+2
Trace(H) ( + )
 H=xxxyr= =12=1
   H2
If r>Th, then delete the extreme point.

1. Take 16×16 square window
2. Compute edge orientation for each 2×2 block in 16×16 square
22 L(x,y)=G(x,y,)*I(x,y) m(x,y)= (L(x+1,y)−L(x−1,y)) +(L(x,y+1)−L(x,y−1))
(x, y)= tan−1((L(x, y +1)− L(x, y −1)) (L(x +1, y)− L(x −1, y)))
3. Throw out weak edges (threshold gradient magnitude)
4. Create histogram by accumulating the Gaussian weighted edge magnitude
Step 3) Orientation Assignment
0 2 angle histogram
Scale-Space Extrema detection
Localization
Orientation Assignment
Key Point Descriptor Construction

Step 4) Descriptor Construction
Scale-Space Extrema detection
1. Normalize the window as 16×16 window using orientation/scale.
2. For each 4×4 block, compute gradient histogram over 8 directions.
Gradient magnitudes are weighted by a Gaussian of variance half the window (for s mooth fall-off)
SIFT descriptor: 128-D vector
Localization
Orientation
Assignment
Key Point Descriptor Construction

Step 4) Descriptor Construction
3. Concatenate 8-D vectors of 4×4 arrays and normalise the magnitude 128-D vector t o 1.
SIFT Descriptor: Binning of Spatial Coordinates and Gradient Orientations
4. Threshold gradient magnitudes to avoid excessive influence of high gradients
1. after normalization, clamp gradients >0.2
2. Renormalize the vector

Properties of SIFT
• Extraordinarily robust detection and description technique
Can handle changes in viewpoint
• Uptoabout60degreeout-of-planerotation
Can handle significant changes in illumination Sometimes even day vs. night
Fast and efficient—can run in real time
Source: N. Snavely

SURF (Speeded Up Robust Features)
• SIFT is one of the best but slow
• Using integral images for an efficient implementation
• Detect and describe SIFT like features
• SURF describes image 3 times faster than SIFT
S = (A − B − C + D) • Keypoint detection based on Hessian matrix: blob-like features
H(p,)=Lxx(p,) Lxy(p,) H(p,)=L (p,)L (p,)−L (p,)2   xx yy xy
• SURF is not as well as SIFT on invariancae to illumination change and viewpoint change
Lxy (p, ) Lyy (p, ) 
where Lxx (p, ) is the convolution of the second order Gaussian derivative 2G(p, )/ x2 with the image I in p and similarly for L (p, ) and L (p, ).
Integral images: accumulated sum of gray scale pixel values of images
Bay, H., Tuytelaars, T., Gool, L.V., “SURF: Speeded Up Robust Features”, ECCV 2006. Bay, H. et al., “Speeded-Up Robust Features (SURF)”, Computer Vision and Image Understanding, 2008

• SURF is more than three times faster than SIFT
• SURF is inferior to SIFT for luminance and viewpoint changes.
• SURF integrates the gradient information within a subpatch, whereas SIFT depends on the orientations of the individual gradients. This makes SURF less sensitive to noise.

• Feature Descriptor
̶ Scale Invariant Feature Transform (SIFT) descriptor ̶ Speeded Up Robust Features (SURF) descriptor
• Feature Matching
̶ Nearest Neighbor (NN) Matching

How do we decide which features match?

Overview of Feature Matching
1. Find a set of distinctive keypoints
2. Define a region around each keypoint
3. Extract and normalize the region content
4. Compute a local descriptor from the normalized region
5. Match local descriptors
d(fA, fB)T
Slide from K. Grauman, B. Leibe

• Nearest neighbor matching
One feature matches to another if those features are nearest neighbors and their distance is below some threshold.
{𝑓|𝑖 = 1,…,𝑁} for 𝐼 and {𝑔 |𝑗 = 1,…,𝑀} for 𝐼 𝑖1𝑗2
𝑘=min𝑑𝑖𝑠𝑡(𝑓,𝑔 ) & 𝑑𝑖𝑠𝑡(𝑓,𝑔 )<𝑇→𝑁𝑁(𝑓)=𝑔 • Problems ̶ Threshold 𝑇 is difficult to set ̶ Non-distinctive features could have lots of close matches, only one of which is correct Feature Matching • Simple Solution: Cross-checking technique 𝑘 = min𝑑𝑖𝑠𝑡(𝑓,𝑔 ) → 𝑁𝑁(𝑓) = 𝑔 𝑖𝑗𝑖𝑘 𝑙=min𝑑𝑖𝑠𝑡(𝑓,𝑔 ) → 𝑁𝑁(𝑔 )=𝑓 If 𝑖 = 𝑙 , the matching is assumed to be reliable. Otherwise, the matching is unreliable. Reliable match Unreliable match Feature Matching • Simple Solution Refine matched points using threshold ratio of nearest to 2nd nearest descriptor 𝑘 =min𝑑𝑖𝑠𝑡(𝑓,𝑔) 1𝑗𝑖𝑗 𝑑𝑖𝑠𝑡(𝑓 , 𝑔 ) 𝑖 𝑘1 <𝑇 → 𝑁𝑁(𝑓)=𝑔 𝑑𝑖𝑠𝑡(𝑓,𝑔 2) 2𝑗𝑖𝑗𝑖𝑘 𝑘 =secondmin𝑑𝑖𝑠𝑡(𝑓,𝑔 ) This gets rid of 90% false matches, 5% of true matches in Lowe’s study Feature Matching and Fitting Feature matching Fundamental matrix estimation Feature matching Image stitching using geometric transform estimation Next topic • We’ve learned how to process pixels and detect features, e.g. edges, corners, blobs. • A higher-level, more compact representation of the features in the image by grouping multiple features according to a simple model ̶ Prerequisite • Review EBU6230 Image/Video Processing – Week3: Interest points • Review EBU7240 Computer Vision – Week1: feature (what you learned today) 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts