Path: news.mathworks.com!newsfeed-00.mathworks.com!newscon02.news.prodigy.net!prodigy.net!newsdst01.news.prodigy.net!prodigy.com!postmaster.news.prodigy.com!newssvr19.news.prodigy.net.POSTED!f08f66eb!not-for-mail
From: "Jon Slaughter" <Jon_Slaughter@Hotmail.com>
Newsgroups: comp.soft-sys.matlab,sci.math,sci.stat.math,sci.stat.consult,sci.stat.edu
References: <f76kg0$ic0$1@news.Stanford.EDU>   <1184291939.529828.55100@o61g2000hsh.googlegroups.com>   <f76pbs$mef$1@news.Stanford.EDU> <1184298239.408921.284810@n2g2000hse.googlegroups.com>
Subject: Re: How to detect turning points in curves...
Lines: 94
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2900.2180
X-RFC2646: Format=Flowed; Original
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180
Message-ID: <MfHli.6345$rL1.6014@newssvr19.news.prodigy.net>
NNTP-Posting-Host: 65.65.63.158
X-Complaints-To: abuse@prodigy.net
X-Trace: newssvr19.news.prodigy.net 1184317548 ST000 65.65.63.158 (Fri, 13 Jul 2007 05:05:48 EDT)
NNTP-Posting-Date: Fri, 13 Jul 2007 05:05:48 EDT
Organization: AT&T http://yahoo.sbc.com
X-UserInfo1: OPYCR^OGYJWUSPE[BJKN^UTAAB]BQUDO@HTHOCULF@^PGDTFOG[]VFW[ML\THRCKV^GGZKJMGV^^_JSCFFUA_QXFGVSCYRPILH]TRVKC^LSN@DX_HCAFX__@J\DAJBVMY\ZWZCZLPA^MVH_P@\\EOMW\YSXHG__IJQY_@M[A[[AXQ_XDSTAR]\PG]NVAQUVM
Date: Fri, 13 Jul 2007 04:05:43 -0500
Xref: news.mathworks.com comp.soft-sys.matlab:418897 sci.math:1030796 sci.stat.math:78246 sci.stat.consult:58915 sci.stat.edu:48362




<AWinestein@gmail.com> wrote in message 
news:1184298239.408921.284810@n2g2000hse.googlegroups.com...
> On Jul 12, 10:49 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>> <AWinest...@gmail.com> wrote in message
>>
>> news:1184291939.529828.55100@o61g2000hsh.googlegroups.com...
>>
>>
>>
>>
>>
>> > On Jul 12, 9:26 pm, "Linus Utopia" <linus_uto...@gmail.com> wrote:
>> >> How to detect turning points in curves
>>
>> >> Hi all,
>>
>> >> If you take a look at the following plot,
>>
>> >>http://img63.imageshack.us/img63/5050/gggyt1.jpg
>>
>> >> You will agree with me that there are two turning points.
>>
>> >> But is there a systematic way to let computer detect the turning 
>> >> points
>> >> automatically and programmatically?
>>
>> >> Please be advised that the second turn isn't neccessarily turning 
>> >> down,
>> >> it
>> >> can also possibly go up...
>>
>> >> And in real-world applications, the turn can be more smooth and round,
>> >> but
>> >> still, naked eyes should be able to find the turning points easily.
>>
>> >> My program has to do a classification:
>>
>> >> All the good curves should first go down, and then either make no 
>> >> turns;
>> >> or
>> >> make a turn, and stay vertically flat and slightly up, going from the
>> >> left
>> >> to the right.
>>
>> >> There should be no second turn (up or down). If there is the second 
>> >> turn,
>> >> then that's the bad curves.
>>
>> >> My program needs to decern the good curves from bad curves.
>>
>> >> I cranked a few algorithms but they don't work well. Are there 
>> >> systematic
>> >> methods of handling this?
>>
>> >> Thanks a lot!
>>
>> > My browser wouldn't show your image, but here's a
>> > thought.  If your points are sampled at equal intervals,
>> > you can do a Fourier transform, use the analytic expression
>> > of the derivative term by term and the Fourier coefficients
>> > to calculate the derivative of the Fourier representation
>> > of your "function", and find the zeros of the derivative
>> > and take those as the turning points.  FWIW.
>>
>> How? Could you please elaborate?- Hide quoted text -
>>
>> - Show quoted text -
>
> This is a brief summary.  Hopefully it doesn't insult your
> intelligence and isn't too sketchy.
>
> Under certain conditions on F,
> F(x) = a0 + a1 cos(kx) + a2 cos(2kx) + ... +
>            b1 sin(kx) + b2 sin(2kx) + ...
> Using a discrete Fourier Transform (preferably using the Fast
> Fourier Transform algorithm if you have very many data points),
> you can calculate a discrete set of a's and b's the cause F to
> agree with your function at the x values for which you have F
> values.  Then F' is given by
> F'(x)= - ka1 sin(kx) - 2ka2 sin(2kx) - ... +
>         kb1 cos(kx) + 2kb2 cos(2kx) + ...
> Set F'(x) = 0 and solve for x's that satisfy this equation.
> These should approximate the turning point.
>
> I don't know if it will work for your application, or how
> practrical it will be.
>

Or better yet, use wavelets which is O(n)(rather than O(nlog n) of FFT) and 
specifically used for detecting "changes" like this.