Reference no: EM132694463
Project - Tracking Image Movement using Convolution
Task 1: Interpreting Averaging as a Convolution
Consider the system S : [Z → R] → [N0 → R] whose output is the average of its last M inputs:
y = S(x) =⇒ ∀n ∈ N , y(n) = 1/M ΣM-1k=0 x(n - k).
1. Find the signal h ∈ [Z → R] such that
y = S(x) =⇒ y(n) = (h ∗ x)(n) for all n ≥ 0, where the symbol ∗ denotes convolution.
2. Let y be defined as above. For what values of n ≥ 0 is y(n) independent of x(k) for all k < 0?
Task 2 : Cross Correlation
Another operation that acts on two signals to produce a new signal is cross correlation. The cross correlation of two signals is defined by the relationship
y = g × x =⇒ ∀n ∈ Z, y(n) = Σ∞-∞ g(k - n) · x(k).
This operator is very similar to convolution but has a more straightforward interpretation. Notice that if y = g × x, then y(0) is simply the sum of the product of the values of g and x at each index. This is analogous to the dot product of two vectors. Similarly to the dot product, this value is a measure of the closeness of the two signals g and x. For values of n that are larger than zero, y(n) is simply the dot product of the signal x with a copy of g that is shifted by n units in time. Therefore, y(n) is simply of measure of how similar x is to a n-shifted copy of g.
3. Suppose g × x = h ∗ x. Based on the above definition for the cross correlation, find the relationship between g(n) and h(n) for all n ∈ Z.
4. Recall the system S from Question 1. What is the signal g ∈ [Z → R] such that S(x) = y =⇒ y = g × x?
You should notice that in both Question 1 and Question 3, the signal that is either convolved or cross correlated with the input to create the averaging system is of finite support (i.e., the number of non-zero elements is finite). Therefore, it is possible to store this signal on a device with finite physical memory like a computer. In the context of cross correlation, this signal would be called a convolutional kernel. By convention, convolutional kernels are usually the left argument to a cross correlation operation. This may be confusing since the term convolutional kernel is more commonly associated with cross correlation than convolution however it is common machine learning and digital signal processing lingo.
5. Suppose x ∈ [Z → R] is an aperiodic signal. Let y = x × Dd(x), where
Dd : [Z → R] → [Z → R], z = Dd(x) =⇒ ∀n ∈ Z, z(n) = x(n - d),
i.e., Dd is a delay system by d units in time. Determine for what value n is y(n) greatest? Show your steps. (Hint: Consider the Cauchy-Schwartz inequality.)
Task 3 : Cross Correlation of Images
In the programming task in the next section, you will use cross correlation of images to perform a classification task. Therefore we must now generalize the definition and intuition of cross correction developed above such that the definition will work with images. An image can be viewed as a two-dimensional signal and luckily it is straightforward to make the jump to operating on two-dimensional signals using cross correlation.
Just as single dimensional cross correlation takes in two single dimensional signals and returns a single dimen- sional signal, the two-dimensional generalization of cross correlation should operate on a pair of two-dimensional signals and return another two-dimensional signal. Furthermore, just as the single dimensional cross correlation measures the similarity of two signals when one is shifted in time by n time steps, the two-dimensional output of the two-dimensional cross correlation should measure how similar the first input is to the second input after the first input has been shifted both vertically and horizontally by m and n units respectively.
This suggests the following definition
y = g × x =⇒ ∀m, n ∈ Z, y(m, n) = Σ∞i=-∞Σ∞j=-∞ g(i - m, j - n) · x(i, j). (1)
Notice that the sums in the above equation are infinite, even though images do not usually have infinite extent as it is often assumed for signals. The most common way to deal with this issue is to assume some values for the "missing values" outside the image. Some common options are treating the signal representation of the image as periodic outside of the defined pixel values or assuming all values in the signal outside of the defined pixel values are equal to zero.
For the latter case, considering a grey-scale image signal as
ximg ∈ [{0, 1, . . . , dvert - 1} × {0, 1, . . . , dhori - 1} → [0, 1]] the signal x used in the correlation (1) would be obtained as
x(i, j) = ximg(i, j), 0 i < dvert, 0 j < dhori
= 0, otherwise (2)
In this assignment we will use a different approach. We will only store the results of the cross correlation that are independent of any values outside of the defined range of the images. The indices of the output that are considered will depend on the sizes of both two-dimensional input images and you should expect the output to have a smaller (or equal) size compared to the larger of the two inputs.
6. Suppose ximg ∈ [{0, 1, . . . , 99}2 → [0, 1]] is the signal representation of an image that is 100 pixels wide and 100 pixels tall. Let y be the cross correlation of x obtained from ximg as in (2) with a convolutional kernel g where g(i, j) = 0 if i < 0, i ≥ 3, j < 0 or j ≥ 3. For what values of m and n is y(m, n) independent of x(i, j) for all i < 0 or i ≥ 100 and j < 0 or j ≥ 100?
We chose to pad x with zeros for indices outside the domain of ximg but for these values of m and n we could have put anything there and got the same result for y(m, n).
Submit your written response for these written questions via PDF on Canvas.
Task 4: Programming Task: Finding the Direction of a Video
This portion of the project is available via Github Classroom. Use Git to clone the project directory from the Github repository created by Github Classroom. To complete the assignment, implement the functions within the given function skeletons and use Git commands to push your changes to Github.
You must use the Python libraries NumPy and Imageio to complete this project while you may also use the SciPy library. To install these dependencies you can run python -m pip install numpy scipy imageio in your Git Bash terminal.
Attachment:- Tracking Image Movement using Convolution.rar