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.

To read more about the basics of convolution, please read the following article: the basics of convolution.

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.

         

New comment

comments powered by Disqus