2/18/2020
CSE 473/573
Introduction to Computer Vision and Image Processing
‘-
CONVOLUTION VS CORRELATION
STITCHING
Questions?
‘-
1
2/18/2020
Correlation vs Convolution
• Correlation is measurement of the similarity between two signals/sequences.
• A Neighborhood Operation • Uses a Correlation Filter
‘-
• Convolution is measurement of effect of one signal on the other signal.
• Mathematical way of applying a filter • Uses a Convolution Filter
3
Correlation filtering
Say the averaging window size is 2k+1 x 2k+1:
‘-
Attribute uniform Loop over all pixels in neighborhood weight to each pixel around image pixel F[i,j]
Now generalize to allow different weights depending on neighboring pixel’s relative position:
Non-uniform weights
4
2
2/18/2020
Filter (Correlation) vs. Convolution • 2D filtering (Correlation)
f=filter I=image
• h=filter2(f,I); or h=imfilter(I,f); ‘-
h[m,n]f[k,l]I[mk,nl] k,l
• 2D convolution
• h=conv2(f,I);
h[m,n]f[k,l]I[mk,nl]
k,l 5
Effect on the filter
h[m,n]f[k,l]I[mk,nl] k,l
When k = l = -1 (m-1, n-1)
1 2 3 ‘- 456 789
EXERCISE
Convolution Filters are rotated by 180 degrees
6
h[m,n]f[k,l]I[mk,nl]
k,l
When k = l = -1 (m+1, n+1)
123 456 789
3
2/18/2020
What Properties do they have? • Both extract information from the image
• Both are shift or translation Invariant
• Both are linear (a linear combination of neighbors)
• Only the Convolution is Associative • F * (G * I) = (F * G) * I
‘-
7
Exercise
• What happens when you take a correlation of a (non-symmetric)
Filter, W, with a 2D matrix f that
has a single value of 1 in the
middle? ‘-
• What if we take a Convolution (pre-rotating the filter)?
• What if we have a symmetric Filter?
8
4
2/18/2020
When to use which?
• Correlation
• Applying a template or filter to an image • Measuring Similarity
• When we don’t care of it is associative
‘-
• Convolution
• Applying an operation to an image (filtering) • When we want association
9
Algorithm Summaries
• Least Squares Fit
• closed form solution • robust to noise
• not robust to outliers
• Robust Least Squares
• improves robustness to outliers • requires iterative optimization
‘-
• RANSAC
• robust to noise and outliers
• works with a moderate number of parameters (e.g, 1-8)
• Hough transform
• robust to noise and outliers
• can fit multiple models
• only works for a few parameters (1-4 typically)
10
5
2/18/2020
Panoramas: generating synthetic views
real camera
synthetic camera
‘-
Can generate any synthetic camera view
as long as it has the same center of projection!
Source: Alyosha Efros
11
changing camera center
synthetic PP
• Does it still work?
PP2
PP1
‘-
Source: Alyosha Efros
12
6
2/18/2020
RANSAC Line Fitting Example
Total number of points within a threshold of line.
‘-
13
RANSAC Line Fitting Example
Repeat, until get a good result
‘-
14
7
2/18/2020
How to choose parameters? • Number of samples N
• Choose N so that, with probability p, at least one random sample is free from outliers (e.g. p=0.99) (outlier ratio: e )
• Number of sampled points s
• Minimum number needed to fit the model
‘-
proportion of outliers e
s 5% 10% 20% 25% 30% 40% 50%
2 2 3 5 6 7 11 17
• Distance threshold
• Choose so that a good point with noise is likely (e.g., prob=0.95) within threshold • Zero-mean Gaussian noise with std. dev. σ: t2=3.84σ2
s N log1 p/ log1 1 e
3 3 4 3 5 4 6 4 7 4 8 5
4 7 9 11 19 35
5 9 6 12 7 16 8 20 9 26
13 17 17 26 24 37 33 54 44 78
modified from M. Pollefeys
For p = 0.99
34 72 57 146 97 293
163 588 272 1177
15
RANSAC example: Translation
‘-
Putative matches
Source: Rick Szeliski
16
8
2/18/2020
‘-
Select one match, count inliers
17
‘-
Select one match, count inliers
18
9
2/18/2020
‘-
Find “average” translation vector
19
RANSAC conclusions
Good
• Robust to outliers
• Applicable for larger number of model parameters than Hough transform • Optimization parameters are easier to choose than Hough transform
‘-
Bad
• Computational time grows quickly with fraction of outliers and number of parameters
• Not good for getting multiple fits
Common applications
• Computing a homography (e.g., image stitching)
• Estimating fundamental matrix (relating two views)
20
10
2/18/2020
IMAGE STITCHING
‘-
Image Stitching
1. 2.
Align the images over each other • camera pan ↔ translation on cylinder
Blend the images together
‘-
22
Szeliski
11
2/18/2020
Assembling the panorama
•Stitch pairs together, blend, then crop
‘-
23
Szeliski
Problem: Drift
• Error accumulation
• small (vertical) errors accumulate over time
• apply correction so that sum = 0 (for 360° pan.)
‘-
24
Szeliski
12
2/18/2020
Problem: Drift
(x1,y1)
• Solution
• add another copy of first image at the end
• this gives a constraint: yn = y1
• there are a bunch of ways to solve this problem
‐ add displacement of (y1 – yn)/(n -1) to each image after the first
‐ compute a global warp: y’ = y + ax
‐ run a big optimization problem, incorporating this constraint
• best solution, but more complicated • known as “bundle adjustment”
(xn,yn)
‘-
copy of first image
25
Szeliski
Full-view (360° spherical) panoramas ‘-
Szeliski
13
2/18/2020
Full-view Panorama
+
++
‘-
+
27
Szeliski
Texture Mapped Model
‘-
28
Szeliski
14
2/18/2020
Global alignment
• Register all pairwise overlapping images
• Use a 3D rotation model (one R per image)
• Use direct alignment (patch centers) or feature based
• Infer overlaps based on previous mat‘-ches (incremental)
• Optionally discover which images overlap other images using feature selection (RANSAC)
Szeliski
29
Image Blending
• How do we put images together so there is no obvious divisions?
‘-
Szeliski
15
2/18/2020
Image feathering
• Weight each image proportional to its distance from the edge
(distance map [Danielsson, CVGIP 1980]
‘-
• 1. Generate weight map for each image
• 2. Sum up all of the weights and divide by sum: weightssumupto1: wi’=wi /(∑i wi)
Szeliski
31
Image Feathering
‘-
32
Szeliski
16
2/18/2020
Feathering
+
1=1 00
‘-
33
Szeliski
Effect of window size
‘-
1 left 1
right 00
34
Szeliski
17
2/18/2020
Effect of window size
‘-
11 00
35
Szeliski
Good window size
1
‘-
0
“Optimal” window: smooth but not ghosted • Doesn’t always work…
36
Szeliski
18
2/18/2020
Pyramid Blending
‘-
Burt, P. J. and Adelson, E. H., A multiresolution spline with applications to image
mosaics, ACM Transactions on Graphics, 42(4), October 1983, 217-236. 37 Szeliski
Laplacian level
4
Laplacian level
2
Laplacian level
0
‘-
left pyramid
right pyramid
blended pyramid 38 Szeliski
19
2/18/2020
Laplacian image blend
1. ComputeLaplacianpyramid
2. ComputeGaussianpyramidonweightimage (can put this in A channel)
3. BlendLaplaciansusingGaussianblurred
weights
4. Reconstructthefinalimage
• Q: How do we compute the original weights?
• A: For horizontal panorama, use mid-lines
• Q: How about for a general “3D” panorama?
Szeliski
‘-
39
Weight selection (3D panorama) • Idea: use original feather weights to select
strongest contributing image
‘-
• Can be implemented using L-∞ norm: (p = 10) • wi’ = [wip / ( ∑i wip)]1/p
40
Szeliski
20
2/18/2020
Poisson Image Editing
‘-
• Blend the gradients of the two images, then integrate • For more info: Perez et al, SIGGRAPH 2003
41
Szeliski
De-Ghosting
‘-
Szeliski
21
2/18/2020
Local alignment (deghosting)
• Use local optic flow to compensate for small motions [Shum & Szeliski, ICCV’98]
‘-
43
Szeliski
Local alignment (deghosting)
• Use local optic flow to compensate for radial distortion [Shum & Szeliski, ICCV’98]
‘-
44
Szeliski
22
2/18/2020
Region-based de-ghosting
• Select only one image in regions-of-difference using weighted vertex cover
[Uyttendaele et al., CVPR’01]
‘-
45
Szeliski
Region-based de-ghosting
•Select only one image in regions-of-difference using weighted vertex cover [Uyttendaele et al., CVPR’01]
‘-
Szeliski
23
2/18/2020
Cutout-based de-ghosting
•Select only one image per output pixel, using spatial continuity
•Blend across seams using
gradient continuity (“Poisson ‘- blending”)
[Agarwala et al., SG’2004]
Szeliski
Cutout-based compositing
• Photomontage [Agarwala et al., SG’2004]
• Interactively blend different images: group portraits
‘-
48
Szeliski
24
2/18/2020
Cutout-based compositing
• Photomontage [Agarwala et al., SG’2004]
• Interactively blend different images: focus settings
‘-
49
Szeliski
Cutout-based compositing
• Photomontage [Agarwala et al., SG’2004]
• Interactively blend different images: people’s faces
‘-
50
Szeliski
25
2/18/2020
Other types of mosaics
‘-
• Can mosaic onto any surface if you know the geometry
• See NASA’s Visible Earth project for some stunning earth mosaics
‐ http://earthobservatory.nasa.gov/Newsroom/BlueMarble/
51
Szeliski
Final thought:
What is a “panorama”? • Tracking a subject
• Repeated (best) shots • Multiple exposures
‘-
• “Infer” what photographer wants?
• Also referred to as “Computational Photography”
52
Szeliski
26
2/18/2020
Next Class: Texture
‘-
53
27