CPSC 425 Extended Example Example: Convolution (Re-Visited)
In computer vision, correlation is an operation that is useful to perform. Convolution, on the other hand, is an operation that we can “speed up” (compared to direct implementation based on its defining formula). This helps because we can implement correlation as a convolution (and vice versa) provided we remember to “flip” the filter appropriately (if it is not symmetric about the origin).
The question arises, “Is there a situation where convolution itself is a meaningful (and therefore useful) operation to perform?”
One positive answer comes from probability and statistics. Consider the following theorem:
Copyright By PowCoder代写 加微信 powcoder
Sum of Two Random Samples
Let ⊗ denote convolution Theorem:
Let X1 and X2 be two random samples, chosen independently, from distributions with probability density function (pdf) f1(x) and f2(x), respectively
Then the random variable
Y =X1 +X2 f1(x) ⊗ f2(x)
Note: This theorem applies in both the continuous and the discrete case.
Let’s apply the theorem to the simple example of determining the probability density function (pdf) of the sum of tossing two standard six-sided dice.
Let X be the random variable associated with the toss of a single die. Probability Density Function: Toss of One Die
…−2−10 1 2 3 4 5 6 7 8 9 …
Now consider the toss of two dice. To determine the probability density function (pdf) of the sum we convolve the pdf for the toss of one die with itself.
To visualize the convolution, we take a copy of the probability density function (pdf) for the toss of one die and flip it about the origin (shown in red).
We then imagine sliding this flipped version along the original X axis from X = −∞ to X = ∞. Tossing Two Dice as a Convolution
…−2−10 1 2 3 4 5 6 7 8 9 …
Tossing Two Dice as a Convolution
…−2−10 1 2 3 4 5 6 7 8 9 …
The first time there is overlap between the original pdf (black) and the flipped pdf (red) is when theflippedpdfispositionedatX =2. Theonlywaytotossasumof2isforeachdietobea1 (shown in blue). The probabilty of tossing a sum equal to 2 is therefore
1×1=1 6 6 36
Tossing Two Dice as a Convolution
…−2−10 1 2 3 4 5 6 7 8 9 …
Moving along, we next show the case for a sum of 7. This occurs when the flipped pdf is positioned at X = 7. There are six ways to toss a sum of 7 (shown in blue). The probabilty of tossing a sum equal to 7 is therefore
1×1+1×1+1×1+1×1+1×1+1×1=6×1 =1
6 6 6 6 6 6 6 6 6 6 6 6
Tossing Two Dice as a Convolution
…−2−10 1 2 3 4 5 6 7 8 910…
Next, we show the case for a sum of 10. This occurs when the flipped pdf is positioned at X = 10. There are three ways to toss a sum of 10 (shown in blue). The probabilty of tossing a sum equal to 10 is therefore
1×1+1×1+1×1=3×1 = 1 6 6 6 6 6 6 36 12
Tossing Two Dice as a Convolution
…−2−10123456789… 12X
As a last example, we show the case for a sum of 12. This occurs when the flipped pdf is positioned atX=12. Theonlywaytotossasumof12isforeachdietobea6(showninblue). The probabilty of tossing a sum equal to 12 is therefore
1×1=1 6 6 36
This is the last time there is overlap between the original pdf (black) and the flipped pdf (red) since, indeed, it is impossible to attain a sum greater than 12 from the toss of two standard dice.
We have illustrated visually a few special cases for the sum of the toss two die. Filling in the intermediate cases is left as an exercise for the reader.
Regardless, it should now be clear how the pdf for the sum of tossing two standard six-sided dice can be expressed as the convolution of the pdf for the toss of one die with itself.
Note: There are only six possible (discrete) outcomes for the toss of a single die. Even so, we have modeled the outcome of a single toss using a discrete random variable, X, taking on (integer) values from X = −∞ to X = ∞. In defining the associated pdf, the probabilty for values of X outside the set {1, 2, 3, 4, 5, 6} is taken to be zero.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com