2812ICT Perceptual Computing
Image Features
Outline
• line features
• Edge detectors
• RANSAC for line fitting
• Line detection with the Hough transform
Edges and lines
• An edge is a place of rapid change of image intensity, colour or texture, representing:
• Boundaries of objects • Shadow boundaries
• Creases
•…
• Edge points (edgels) can be grouped into: • Curves/contours
• Straight line segments
• Piecewise linear contours
•…
Edge detection
• Goal: Identify sudden changes (discontinuities) in an image.
• Intuitively, most semantic and shape information from the image can be encoded in the edges
• More compact than pixels…
• Ideal: artist’s line drawing (but artist is also
using object-level knowledge)
• Why do we care? It allows us to
• Extract information, recognize objects • Recover geometry and viewpoint
Source: D. Lowe
Origins of edges
surface normal discontinuity:
depth discontinuity:
surface color discontinuity:
illumination discontinuity
Source: D. Hoiem
Characterizing Edges
• An edge is a place of rapid change in the image intensity function
Source: Fei-Fei Li
Finite differences: example
Intensity profile
Source: D. Hoiem
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
Effects of noise
• Finite 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 is to be done?
• Smoothing the image should help, by forcing pixels different to their neighbors (=noise pixels?) to look more like neighbors
Source: D. Forsyth
Solution: smooth first
• To find edges, look for peaks in
Source: S. Seitz
Derivative theorem of convolution
• This theorem gives us a very useful property: • This saves us one operation:
Source: S. Seitz
Derivative of Gaussian filter
Source: Fei-Fei Li
Tradeoff between smoothing and localization
Smoothed derivative removes noise, but blurs edge.
Source: D. Forsyth
Implementation issues
• The gradient magnitude is large along a thick “trail” or “ridge,” so how do we identify the actual edge points?
• How do we link the edge points to form curves?
We will see how this is done later!
Source: D. Forsyth
Designing an edge detector
• Criteria for an “optimal” edge detector:
• Good detection: the optimal detector must minimize the probability of false positives (detecting spurious edges caused by noise), as well as that of false negatives (missing real edges)
• Good localization: the edges detected must be as close as possible to the true edges
• Single response: the detector must return one point only for each true edge point; that is, minimize the number of local maxima around the true edge
Source: Fei-Fei Li
Canny edge detector
• This is probably the most widely used edge detector in computer vision
• Theoretical model: step-edges corrupted by additive Gaussian noise
• Canny has shown that the first derivative of the Gaussian closely approximates the operator that optimizes the product of signal- to-noise ratio and localization
J. Canny, A Computational Approach To Edge Detection, IEEE Trans. Pattern Analysis and Machine Intelligence,
8:679-714, 1986.
Source: Fei-Fei Li
Compute Gradients (DoG)
𝜕𝑓 𝜕𝑥
𝜕𝑓 𝜕𝑦
𝜕𝑓 2 𝜕𝑓 2 𝑀= 𝜕𝑥 + 𝜕𝑦
Get Orientation at Each Pixel
Source: J. Hayes
Non-maximum suppression
Source: D. Forsyth
Before non-max suppression After non-max suppression
Hysteresis thresholding
• Threshold at low/high levels to get weak/strong edge pixels
• Do connected components, starting from strong edge pixels
Source: J. Hayes
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
Edge linking
Source: D. Forsyth
Final Canny Edges
Canny edge detector
1. Filter image with x, y derivatives of Gaussian
2. Find magnitude and orientation of gradient
3. Non-maximum suppression:
• Thin multi-pixel wide “ridges” down to single pixel width
4. Thresholding and linking (hysteresis):
• Define two thresholds: low and high
• Use the high threshold to start edge curves and the low threshold to continue them
MATLAB: edge(image, ‘canny’)
Source: Fei-Fei Li
Effect of (Gaussian kernel spread/size)
• The choice of depends on desired behaviour • Largedetectslargescaleedges
• Small detects fine features
Source: S. Seitz
First and second derivatives
Laplacian operator Gradient (in two dimensions):
Discrete approximation:
Finite differences:
Laplacian:
h is the grid size, normally set h = 1. This gives the following 3×3 kernel
Laplacian of Gaussian (LoG)
Gaussian Laplacian of Gaussian
Edge pixels at zero-crossings in the LoG image
Laplacian of Gaussian: Example
Laplacian and LoG
Laplace LoG
Difference of Gaussians (DoG)
DoG
A model fitting method for edge detection
Fitting as search in parametric space:
• Choose a parametric model to represent a set of features
• Membership criterion is not local
• Can’t tell whether a point belongs to a given model just by looking at that point.
• Three main questions:
• What model represents this set of features best?
• Which of several model instances gets which feature? • How many model instances are there?
• Computationalcomplexityisimportant
• It is infeasible to examine every possible set of parameters and every possible combination of features
Source: L. Lazebnik
Example: Line Fitting
• Why fit lines?
• Many objects characterized by presence of straight lines
Source: K. Grauman
Difficulty of Line Fitting
• Extra edge points (clutter), multiple models:
• Which points go with which line, if any? • Only some parts of each line detected,
and some parts are missing:
• How to find a line that bridges missing evidence?
• Noise in measured edge points, orientations:
• How to detect true underlying parameters?
Source: K. Grauman
Voting
• It’s not feasible to check all combinations of features by fitting a model to each possible subset.
• Voting is a general technique where we let the features vote for all models that are compatible with it.
• Cycle through features, cast votes for model parameters. • Look for model parameters that receive a lot of votes.
• Noise & clutter features will cast votes too, but typically their votes should be inconsistent with the majority of “good” features.
• Ok if some features not observed, as model can span multiple fragments.
Source: K. Grauman
RANSAC [Fischler & Bolles 1981]
• RANdom SAmple Consensus
• Approach: we want to avoid the impact of outliers, so let’s look for “inliers”, and
use only those.
• Intuition: if an outlier is chosen to compute the current fit, then the resulting line won’t have much support from rest of the points.
Keep the transformation with the largest number of inliers
Source: K. Grauman
RANSAC
• RANSAC divides data into inliers and outliers and yields estimate computed from minimal set of inliers.
• Improve this initial estimate with estimation over all inliers (e.g. with standard least-squares minimization).
• But this may change inliers, so alternate fitting with re-classification as inlier/outlier.
Source: D. Lowe
RANSAC: Pros and Cons
• Pros:
• General method suited for a wide range of model fitting problems • Easy to implement and easy to calculate its failure rate
• Cons:
• Only handles a moderate percentage of outliers without cost blowing up
• Many real problems have high rate of outliers (but sometimes selective choice of random subsets can help)
• A voting strategy, The Hough transform, can handle high percentage of outliers.
Source: D. Lowe
Line detection – Hough transform
Note: The straight line representation y = mx + c fails in case of vertical lines
Hough transform
• The Hough Transform is tolerant of gaps in the edges • It is relatively unaffected by noise
• It is also unaffected by occlusion in the image
• Use of accumulator arrays – concept of ‘Voting’
Hough Transform
1. Clear the accumulator array
2. For each detected edgel (edge pixel) at location (x, y) and each orientation 𝜃=𝑡𝑎𝑛−1(𝑛𝑦Τ𝑛𝑥),computethevalueof𝜌=𝑥sin𝜃+𝑦cos𝜃 and increment the accumulator bin corresponding to (𝜌, 𝜃)
3. Find the peaks (local maxima) in the accumulator corresponding to lines
4. Optional post-processing to fit the lines to the constituent edgels.
Example
Example
Hough Transform for Detection of Circles
• The parametric equation of the circle can be written as
(x−a)2 +(y−b)2 =r2
• The equation has three parameters – a, b, r
• The curve obtained in the Hough Transform space for each edge point will be a right-angled circular cone
• Point of intersection of the cones gives the parameters a, b, r
Hough Transform for Detection of Circles
Original Image Circles detected by Hough Transform of the
Detected Circles
Canny edge edge detected image detector
Line detection – complicated scene
Next week:
• Image features extraction – continue • Invariant descriptors
• Matching