4.0

4.0 | 2 ratings Rate this file 26 Downloads (last 30 days) File Size: 2.13 KB File ID: #10272
image thumbnail

Quick search for local extremes

by

 

08 Mar 2006 (Updated )

New fast and reliable function for finding local extremes in a real vector.

| Watch this File

File Information
Description

The new function extr.m analyses the given real vector carrying a sequence of samples to be analyzed. At the end, it returns a cell array of extreme positions in the sequence. The cell array consists of two cells only. The first one contains the logical vector of maxima and the other the similar one of minima. Should more equal values be present in adjacent elements of the vector, only one position is returned. The attention is also paid on low memory requirements and a speed of the procedure.

Forms of calls:

 L = extr(x); % Find true local extremes

% ..... x vector containing a sequence to be analyzed,
% ..... L cell array {L(1), L(2)}, where
% ..... L(1) is logical vector of positions of maxima,
% ..... L(2) is logical vector of positions of minima.
 
 There are also circumstances, when the processing time is critical for a user, while the exact true extrems are of less priority. In that case he may use:

 L = extr(c,0); % Find true and false local extrems.

False extrems form pairs of equal value minimum-maximum laying somewhere on the trend of the sequence. They are not extrems, but they do not harm in certain cases of consecutive processing.

Examples:

demoXtr; % See the program and figure demoXtr.jpg
L = extr(x);
y = x(L(1)|L(2)); % y is a vector of all extremes
 
clear, x=rand(1e7,1)-.5; tic, L=extr(x); toc
        Elapsed time is 2.974584 seconds. % (3GHz PC, Windows XP Prof.)

clear, x=rand(1e7,1)-.5; tic, L=extr(x,0); toc
        Elapsed time is 1.392926 seconds. % (3GHz PC, Windows XP Prof.)

Hopefully, the function is error-free. If not, please, let me know.

MATLAB release MATLAB 7.0.1 (R14SP1)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (8)
27 Jun 2013 Shirah

Hello, good piece of work. By the way, does anybody know how to replicate those identified extrema onto a grayscale image.

Thank You

11 Oct 2008 ahmed abdelrahaman

hi

i like to make an algorithm to compute the distance between two time series using just extreme point (extreme points warping)

can you help me

22 May 2007 Julio Rodriguez

I need your help Mr. Miroslav Balda.
This paper "Processing of Blade Monitoring System Data", complete document, data this proyect, information in general

Thanks for attention

09 Mar 2006 Miroslav Balda

I will not continue in discussions here. More by e-mail.

09 Mar 2006 Vassili Pastushenko

Hi Miroslav!
Here is my comparison. It is known that the calc. speed depends on memory limitations. By me vectors 1e6 long are already problematic. Therefore I have selected 1e6, not 1e7. How many people need longer vectors?

Again, you have compared with MAXALL which DID INTERPOLATION. I compare both versions, with and without interpolation.

Yes, without interpolation your extr is apparently 0.5 sec faster for 1e6 vector. But this is again not completely correct, because both progs do different jobs. The user needs BOTH POSITIONS AND VALUES. You analize only y-data, and my prog. searches for both x and y values for extrema. But can a user write down several additional lines within 0.5 sec, in order to extract necessary positions and values?

I was very glad to see that the interpolation is extremely fast: only about 0.2 sec was additionally necessary. I disagree that interpolation is not important. It is frequently nesessary for real data. Typical and quite frequent case is std(diff(signal,2)) comparable with experimental noise amplitude.

As to plateaus: I could agree if you work mainly with double(int8 or int16, uint too). This is however a special niche. In a standard situation, if your sampled data obey a continuous distribution and are represented by double, the probability of such a plateau-extremum is close to zero.

Let users decide, which version they like better.

EXAMPLE: I have filtered somewhat randn, in order to create some similarity with possible real data.

x=savfilt(randn(1,1000000),10);
tic,L=extr(x);te=toc; %time extr
tic,[xp,yp]=maxall(x,0);tm=toc; %time maxall,no interp
tic,[xpi,ypi]=maxall(x);tmi=toc; %time maxall with interpolation

T=[te,tm,tmi] % all times
NUM=[sum(L{2}),length(xp),length(xpi)] %numb. of maxima

T = 0.406 0.906 1.125

NUM = 193980 193980 193980

09 Mar 2006 Miroslav Balda

I do not study behaviour of analytical functions, but long time series - sequences of sampled signals. For that type of tasks, the computing time is restrictive. I have measured time spent by maxall.m on the same problem and same machine as used for testing extr.m, and got the result:

clear, x=rand(1e7,1)-.5; tic, [x,y]=maxall(x); toc
Elapsed time is 30.569705 seconds.

As fas as your final note is concerned, you are right from the point of view of mathematical analysis. However, same values of adjacent samples may occur during measurement. As such the peak values are important and may not be skipped over.

It means that the function maxall is about 10 times slower. If you have more questions, please, send me an e-mail.

09 Mar 2006 Vassili Pastushenko

The problem seems to be easy, but a good tool for practical work is really important.

I would like to see a comparison with similar product MAXALL (cf FEX) which finds all maxima in a vector and all minima in the same vector as maxima in (minus vector). In addition it suggests options for manual positive or negative selection and interpolation for higher accuracy in case of smooth data. I am interested also in comparison of calculation time.

The program behavior in the case of plateau in the data can be skipped because this case does not belong to class of real extrema.

08 Mar 2006 Felix Totir

Being one of the ones wo criticized your work, I really appreciate your effort to improve the function. Really.

Updates
09 Mar 2006

Modification of the description

Contact us