28 November, 2014

# Find local maximas of an 1d signal by convolution

Although there are some great built-in functions in MATLAB to find local maximas, in this post a simple, convolution-based approach is demonstrated to practice using this operation. This post may inspire some MATLAB users to creative ways of using convolution in daily programming tasks.

First have a look at the following 1d signal from which we want to extract the local maximas:

A = [0 1 1 4 3 0 2 0]


A local maxima is higher than its two neighbors, in our sample A signal they are found at the 4th and 7th position. Let us take the difference between neighboring elements: the simplest way to do this is using the diff command:

>> diffA = diff(A)
diffA =
1   0   3  -1  -3   2  -2


Now we have the difference between each pairs. To search for a local maxima we shall look for an increasing-decreasing (positive-negative) pair in the differences as the following figure shows our A and diffA signals:

0   1   1   4   3   0   2   0
1   0   3  -1  -3   2  -2


In a previous post an example is already given for these kind of simple pattern search examples, please have a look at it, too.

Because we are looking for positive-negative pairs, the magnitude of differences are irrelevant, only the sign matters. So apply the sign function on the differences:

>> signA = sign(diffA)
signA =
1   0   1  -1  -1   1  -1


This simplifies the task to search for [1, -1] pairs. Do this by using convolution as in the already mentioned pattern search example:

>> convA = conv2(signA, [-1, 1])
convA =
-1   1  -1   2   0  -2   2  -1


Because convolution mirrors the sliding window, we used the [-1, 1] pattern to search for [1, -1] pairs. You can see, that in the result the value of 2 appears only if the pattern matches exactly. For more explanation, have a look at the following figure, which demonstrates the sliding window during convolution:

    1   0   1  -1  -1   1  -1
1  -1                                  -1
1  -1                               1
1  -1                          -1
1  -1                       2
1  -1                   0
1  -1              -2
1  -1           2
1  -1      -1


There is no other way to get a value of 2, only if the pattern matches. The last step is to find all the values of 2 by using the find command:

>> maximas = find(convA == 2)
maximas =
4   7


This results the positions of the two local maximas in our A signal. By putting it all together, we get a simple one-liner function:

% Find local maximas in a 1d signal by using convolution
function maximas = findLocalMaxima1d(A)
maximas = find(conv2(sign(diff(A)), [-1 1]) == 2);
end


In the next post the 2d variant of this method will be explained with some additional tips and tricks.