Computer Vision (7CCSMCVI / 6CCS3COV)
Recap
• Image formation
● Low-level vision
● Mid-level vision
● grouping and segmentation of image elements
● Biological
● bottom-up influences (Gestalt cues)
● top-down influences (knowledge, expectation, etc.)
● Artificial
● thresholding, region-based, clustering, fitting
● Multi-View Vision
● correspondence problem
● stereo ● video
● High-level vision
● object recognition
←Today
Computer Vision / Mid-Level Vision / Correspondence
1
Multiple Images
Arise due to:
• multiple cameras (stereo)
– two, or more, images taken simultaneously by different cameras
• multiple times (video)
– two, or more, images taken at different times by one camera
• object recognition
– current image and memorised “training” image(s)
Computer Vision / Mid-Level Vision / Correspondence 2
Correspondence Problem
Finding matching image elements across views is fundamental to solving many problems in vision:
● stereodepthrecovery
● finding corresponding points in two images taken by different
cameras enables recovery of 3D information ● motiontracking
● finding corresponding points in two images taken at different times enables estimation of camera and/or object motion
● objectrecognition
● finding corresponding points in training and test images enable
object recognition
Computer Vision / Mid-Level Vision / Correspondence 3
Correspondence Problem
For each selected element in one image, find the corresponding element in the other image.
This is a search problem.
Three main design decisions for correspondence algorithms:
– which elements to match, e.g. intensities, edges, other features. – how to search for matching elements.
– how to compare elements to confirm/reject match.
Basic requirements to be able to solve the correspondence problem: 1. Most scene points visible in both images
2. Corresponding image regions appear “similar”
Computer Vision / Mid-Level Vision / Correspondence 4
Correspondence Problem: problems
Occlusions
some elements may not have a corresponding element due to self- occlusion, occlusion by other object(s), or no longer being “in shot”
False matches
there may be several similar elements, only one of which can be the “true match”
Changing element characteristics
feature values of corresponding elements may differ due to, e.g.: – change in lighting direction (change in intensity)
– viewpoint differences (change in size and shape)
Large search space
each element in one image has many possible matches in other image.
Methods often employ additional assumptions to constrain search space and resolve ambiguities.
Computer Vision / Mid-Level Vision / Correspondence 5
Correspondence Problem: solutions Algorithms to solve the correspondence problem fall into two classes:
Correlation-based methods
Attempt to establish a correspondence by matching image intensities – usually over a window of pixels in each image
• start from raw image intensity values
• match image windows
• compare them using a similarity measure for intensity values
Feature-based methods
Attempt to establish a correspondence by matching sparse sets of image features
• start from image features extracted by preprocessing
• match image features
• compare them using distance between feature descriptors
Computer Vision / Mid-Level Vision / Correspondence 6
Correlation-Based Methods
Matching based on correlating pixel values within image regions.
I1
For each region I1 in image one
For each region I2 of same size in search area of other image
Compute similarity between I1 and I2 .
Repeat for all regions in image two within a search area. Corresponding point is centre of region giving highest similarity.
Repeat for all regions in image one for which correspondence is required.
Computer Vision / Mid-Level Vision / Correspondence
7
BEST MATCH
SEARCH REGION
I2
Correlation-Based Methods
Need to decide on:
1. Size of correlation window – success depends on window exhibiting a distinctive structure that occurs infrequently in the search region of the other image
too small a window
may not capture enough image structure to be distinctive, and
may be too noise sensitive resulting in many false matches too large a window
decreases precision (blurs correspondence map) decreases tolerance to viewpoint
2. Size of search area – full correlation of all pixels is computationally expensive. Therefore usually constrained either:
arbitrarily to be around pixel location from which I1 taken, or by explicit knowledge of task (e.g. using epipolar geometry in stereo
correspondence problem [next lecture]). 3. Method used to measure similarity.
●
●
●
●
● ●
●
●
Computer Vision / Mid-Level Vision / Correspondence 8
Similarity Measures
We can maximise the following measures:
correlation is the dot-product of these vectors
Normalised cross-correlation:
I1.I2=∥I1∥∥I2∥cos ∑I1i,jI2i,j I .I
i,j = 1 2 =cos ∑Ii,j2 ∑Ii,j2 ∥I1∥∥I2∥
∑I1i, jI2i, j i,j
Cross-correlation:
If I1 and I2 are considered to be vectors in feature space, then the cross-
Correlation coefficient:
equals normalised cross-correlation if means are zero
i , j 1 i , j 2
∑ I i , j − I I i , j − I
1122
i,j
∑Ii,j−I2 ∑Ii,j−I2
1122 i,j i,j
Computer Vision / Mid-Level Vision / Correspondence 9
Similarity Measures
We can minimise the following measures:
SumofSquaredDifferences(SSD): ∑I1i,j−I2i,j2 i,j
Euclidean distance: SSD= ∑I i , j−I i , j2 12
i,j
SumofAbsoluteDifferences(SAD): ∑∣I1i,j−I2i,j∣ i,j
In practice, SAD is often used as it is simple and the increased computational costs of using other measures is usually not justified in terms of improved performance.
Computer Vision / Mid-Level Vision / Correspondence 10
Correlation-Based Methods: performance
Advantages
− Easy to implement
− Provides a dense correspondence map (i.e. we calculate correspondence at all points, not just a few)
Disadvantages
− Computationally expensive
− Needs images with lots of distinct intensity patterns to work well
● regions that are constant or repetitive give many false matches − Doesn’t work well when viewpoints are very different, due to
change in illumination
− changes image intensity values
foreshortening
• changes size/shape/appearance of corresponding regions.
●
●
Computer Vision / Mid-Level Vision / Correspondence 11