3
$\begingroup$

I am a civil engineer and am analyzing traffic data recorded by capturing vehicle movements over a highway for a specified time period. The database I am dealing with contains observations at every 0.1 seconds (total about 4 million rows) and has some 'noise' in position (lateral and longitudinal) columns. A research paper suggests to 'smooth' the velocity and acceleration data (derived from position) by using following formula: enter image description here

Someone told me it is a 'convolution'. Since I have no background in electronics/ DSP, I had no idea what convolution is. After studying some online resources I can understand a little about the concept but I need a thorough understanding of this topic from a resource which is targeted towards people who have no background in DSP. Could anyone please guide me to the required resources? I am using R for analysis.

$\endgroup$
3
$\begingroup$

I disagree with the assertion in the answer by user7090 that the calculation in question is not a convolution; it is indeed a convolution. Let us consider the case $D=2$. Ignoring $Z$ for now, the five terms in that sum $\displaystyle \sum_{k = i-2}^{i+2} x(t_k)e^{-|i-k|/\Delta}$ on the left in the OP's question are $$\begin{align} x(t_{i-2})e^{-|i - (i-2))|/\Delta} &= x(t_{i-2})e^{-2/\Delta}\\ x(t_{i-1})e^{-|i - (i-1))|/\Delta} &= x(t_{i-1})e^{-1/\Delta}\\ x(t_{i-0})e^{-|i - (i-0))|/\Delta} &= x(t_i)e^{-0/\Delta} = x(t_i)\\ x(t_{i+1})e^{-|i - (i+1))|/\Delta} &= x(t_{i+1})e^{-1/\Delta}\\ x(t_{i+2})e^{-|i - (i-2))|/\Delta} &= x(t_{i+2})e^{-2/\Delta} \end{align}$$ and so the sum is very much a convolution of the sequence $x$ whose $i$-th term is $x(t_i)$ with a length-$5$ sequence $h$ whose $n$-th term is $e^{-|n|/\Delta}$ for $|n| \leq 2$ in this case (and a length-$(2D+1)$ sequence with $|n| \leq D$ more generally).

What you, the OP, need to understand is the following (and don't get bogged down in words like convolution). You are doing a smoothing of the data that you have collected. Each $x(t_i)$ of the original data is being replaced by a $\tilde{x}(t_i)$ which is formed as a weighted sum of $x(t_i)$ and its immediate neighbors. The weights assigned to $x(t_i)$ is the largest, the weight assigned to its nearest neighbors $x(t_{i+1})$ and $x(t_{i-1})$ are smaller (but equal), the weights assigned to slightly more distant neighbors $x(t_{i+2})$ and $x(t_{i-2})$ is yet smaller, and so on, till the we get to $x(t_{i+D})$ and $x(t_{i-D})$ which get the smallest weights of all. Anything more than $D$ away gets a weight of $0$. The weights in question are normalized in the sense that the total weight is $1$, but let us look at the raw weights which are alleged to be those $e^{-|i-k|/\Delta}$. What you really have (before normalization of the weights) is that sum (let us use $D = 3$ for simplicity) which is

$x(t_i) + \left.\left.e^{-1/\Delta}\right[x(t_{i+1}) + x(t_{i-1)}\right] + \left.\left.e^{-2/\Delta}\right[x(t_{i+2}) + x(t_{i-2})\right] + \left.\left.e^{-3/\Delta}\right[x(t_{i+3}) + x(t_{i-3})\right]$

$= e^{-3/\Delta}x(t_{i-3}) + e^{-2/\Delta}x(t_{i-2}) + e^{-1/\Delta}x(t_{i-1}) + x(t_i) + e^{-1/\Delta}x(t_{i+1}) + e^{-2/\Delta}x(t_{i+2}) + e^{-3/\Delta}x(t_{i+3})\quad (1)$ where on the right side we have the elements occurring in the natural order, flanking the central element $x(t_i)$ on both sides. Now, the sum of the raw weights exhibited in $(1)$ is $$e^{-3/\Delta} + e^{-2/\Delta} + e^{-1/\Delta} + 1 + e^{-1/\Delta} + e^{-2/\Delta} + e^{-3/\Delta} \tag{2}$$ which is just the element $Z$ in the question, and so the normalized weights are just the ones exhibited in $(2)$ divided by $Z$. A better way of writing $Z$ might be $$Z = \sum_{k=-D}^D e^{-|k|/\Delta} = 1 + 2\sum_{k=1}^De^{-k/\Delta} \tag{3}$$ and perhaps a better way of expressing the first sum might be $$\tilde{x}(t_i) = \frac{1}{Z}\sum_{k=-D}^D x(t_{i-k})e^{-|k|/\Delta}$$ which expresses more clearly that we are forming a weighted sum of $x(t_i)$ and its nearest neighbors and that the weights assigned to neighbors at distance $k$ decrease exponentially as a function of $k$ (here $k \geq 0$ of course since we are not distinguishing between the directions of separation).

$\endgroup$
  • $\begingroup$ Beautiful explanation! Thank you very much. I understand the concept pretty well now. However, I believe that for the implementation of this formula within a program I have to understand the basic parameters of convolution so that I can use the function 'convolve' in R language. Thanks again! $\endgroup$ – umair Nov 27 '13 at 2:50
  • $\begingroup$ Nice explanation, Dilip! +1 $\endgroup$ – Peter K. Nov 27 '13 at 15:07
2
$\begingroup$

That's not convolution, but its close. Its technically non-causal, so it is actually a complicated beast from an analysis standpoint. Basically what its doing is taking the a single point and creating a weighted average from D points ahead and D points behind a single measurement. The weights are the terms in the second sum. Z is simply the normalization factor. In a normal average you'd divide by the number of elements, in a weighted average you divide by the sum of the weights.

I'm not sure I'd recommend doing that if you've got position data to work with directly already. If I was you, without a background in DSP, I'd look at doing an alpha-beta-gamma filter to start with, and if you want something better, your problem works well with a Kalman filter. These use the basic position/velocity/acceleration equations in their estimation, but rely on data that comes before your current measurement. If you want to use the data that comes afterwards, Rauch-Taung-Striebel smoothing is an extension of Kalman filtering that takes all of your data as well as physical models to estimate position, velocity and acceleration over time from a set of position measurements. I do recommend starting with Alpha-Beta-Gamma filtering though, its easy to understand, quick to program and is oftentimes good enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.