Course
« Computer Vision»
Sid-Ahmed Berrani
2024-2025
1
Correlation and convolution
Linear spatial filtering can be described in terms of correlation and convolution.
• Correlation:
The process of moving a filter mask over a signal (the image in our case) and computing
the sum of products at each location.
• Convolution:
Similar to correlation but the filter mask is first rotated by 180°.
2
Correlation
An example:
Suppose that we want to compute the correlation of the 1D signal:
f(x) = 0 0 0 1 0 0 0 0
with the mask:
w(x) = 1 2 3 2 8
0 0 0 00 0 0 1 0 0 0 0 0 0 0 0
81 3821 8
2 2138 8132 32
1 21 321 123 2813 318 2312 8213 832 382 82 8
0 008 232 1 0 000
3
Correlation vs. Convolution
• Correlation is a function of displacement of the filter. The first value of correlation
corresponds to zero displacement, the second corresponds to one unit
displacement, and so on
• Correlating a filter w with a function that contains all 0s and a single 1 yields a result
that is a copy of w, but rotated by 180°
• Convolution works exactly the same way, but the filter is rotated by 180° before the
shift operations.
• A fundamental property of convolution is that convolving a function with a unit
impulse yields a copy of the mask at the location of the impulse.
4
2D Correlation/Convolution
In case of 2D functions, like images, the correlation/convolution works in a similar
manner:
• For a filter of size MxN we first pad the image with a minimum of:
• M-1 rows at top and M-1 rows at bottom (filled with 0s)
• N-1 cols at left and N-1 cols at right (filled with 0s)
• We shift the filter at each vertical and horizontal shift to perform the correlation/convolution
operation:
Correlation: ⨂
Convolution: *
5
2D Correlation
Convolution
6
Template Matching
Image (f)
Template (w)
• How do we locate the template in the image?
=> Minimize:
𝑎 𝑏
2
𝐸[𝑖, 𝑗] = 𝑤 𝑠, 𝑡 − 𝑓(𝑖 + 𝑠, 𝑗 + 𝑡)
7
𝑠=−𝑎 𝑡=−𝑏
Template Matching
𝑎 𝑏
2
𝐸 𝑖, 𝑗 = 𝑤 𝑠, 𝑡 − 𝑓 𝑖 + 𝑠, 𝑗 + 𝑡
𝑠=−𝑎 𝑡=−𝑏
𝑎 𝑏
2 2
𝐸 𝑖, 𝑗 = 𝑤 𝑠, 𝑡 + 𝑓 𝑖 + 𝑠, 𝑗 + 𝑡 − 2 𝑤 𝑠, 𝑡 𝑓 𝑖 + 𝑠, 𝑗 + 𝑡
𝑠=−𝑎 𝑡=−𝑏
Minimizing 𝐸 𝑖, 𝑗 => Maximizing
𝑎 𝑏
𝑤 𝑠, 𝑡 𝑓 𝑖 + 𝑠, 𝑗 + 𝑡 = 𝑤⨂𝑓(𝑖, 𝑗)
𝑠=−𝑎 𝑡=−𝑏
8
Filters as Templates
• Filters offer a natural mechanism for finding simple patterns.
• Filters respond most strongly to pattern elements that look like the filter.
• ⨂
9
Correlation as a Dot Product
When performing a correlation (or a convolution):
• The response is obtained by associating image elements with filter kernel elements, multiplying the
associated elements and summing
• It is the same process as a dot product.
• The dot product achieves its largest value when the vector representing the image is parallel to the
vector representing the kernel.
A filter responds most strongly when it encounters an image pattern that looks like the filter.
But this dot product is a poor way to find patterns because the response might be large just because
the image region is bright.
10
Correlation for Pattern Matching
w:
𝒂 𝒃
𝑹𝒘𝒇 𝒊, 𝒋 = 𝒘⨂𝒇 𝒊, 𝒋 = 𝒘 𝒔, 𝒕 𝒇 𝒊 + 𝒔, 𝒋 + 𝒕
𝒔=−𝒂 𝒕=−𝒃
𝑅𝑤𝑓 𝐶 > 𝑅𝑤𝑓 𝐵 > 𝑅𝑤𝑓 𝐴
However, we need 𝑹𝒘𝒇 𝑨 to be the maximum.
11
Normalized Correlation for Pattern Matching
Solution: Normalizing the correlation
σ𝑎𝑠=−𝑎 σ𝑏𝑡=−𝑏 𝑤 𝑠, 𝑡 𝑓 𝑖 + 𝑠, 𝑗 + 𝑡
𝑁𝑤𝑓 𝑖, 𝑗 =
σ𝑠 σ𝑡 𝑤(𝑠, 𝑡)2 . σ𝑠 σ𝑡 𝑓(𝑖 + 𝑠, 𝑖 + 𝑡)2
Energy of the template Energy of the image area covered
by the template
This make the correlation insensitive to brightness.
12
Normalized Correlation for Pattern Matching
w:
σ𝑎𝑠=−𝑎 σ𝑏𝑡=−𝑏 𝑤 𝑠, 𝑡 𝑓 𝑖 + 𝑠, 𝑗 + 𝑡
𝑁𝑤𝑓 𝑖, 𝑗 =
σ𝑠 σ𝑡 𝑤(𝑠, 𝑡)2 . σ𝑠 σ𝑡 𝑓(𝑖 + 𝑠, 𝑖 + 𝑡)2
𝑁𝑤𝑓 𝐴 > 𝑁𝑤𝑓 𝐵 > 𝑁𝑤𝑓 𝐶
13
Normalized Correlation for Pattern Matching
14
Normalized Correlation for Pattern Matching
⨂ =
15
