Path: news.mathworks.com!newsfeed-00.mathworks.com!newscon02.news.prodigy.net!prodigy.net!border1.nntp.dca.giganews.com!nntp.giganews.com!postnews.google.com!n60g2000hse.googlegroups.com!not-for-mail
From:  AWinestein@gmail.com
Newsgroups: comp.soft-sys.matlab,sci.math,sci.stat.math,sci.stat.consult,sci.stat.edu
Subject: Re: How to detect turning points in curves...
Date: Fri, 13 Jul 2007 06:02:09 -0700
Organization: http://groups.google.com
Lines: 101
Message-ID: <1184331729.785200.153510@n60g2000hse.googlegroups.com>
References: <f76kg0$ic0$1@news.Stanford.EDU>
NNTP-Posting-Host: 64.24.177.109
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
X-Trace: posting.google.com 1184331729 13487 127.0.0.1 (13 Jul 2007 13:02:09 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Fri, 13 Jul 2007 13:02:09 +0000 (UTC)
In-Reply-To: <MfHli.6345$rL1.6014@newssvr19.news.prodigy.net>
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; .NET CLR 1.1.4322),gzip(gfe),gzip(gfe)
Complaints-To: groups-abuse@google.com
Injection-Info: n60g2000hse.googlegroups.com; posting-host=64.24.177.109;
Bytes: 5131
Xref: news.mathworks.com comp.soft-sys.matlab:418918 sci.math:1030819 sci.stat.math:78251 sci.stat.consult:58919 sci.stat.edu:48365



On Jul 13, 5:05 am, "Jon Slaughter" <Jon_Slaugh...@Hotmail.com> wrote:
> <AWinest...@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.- Hide quoted text -
>
> - Show quoted text -

Yes, wavelets are good.  Kind of depends on whether there are
any reasons to prefer more global or local function behavior
to influence one's calculation of local turning points.  There
didn't appear to be any given in the OP's post, so wavelets
might well be better there.