3

To convert the black wave to the red signal.

enter image description here

Fabricio
  • 7,705
  • 9
  • 52
  • 87
  • What does the blue line signify? – Chris Taylor May 31 '13 at 13:07
  • 6
    [Quantization](http://en.wikipedia.org/wiki/Quantization_%28signal_processing%29). – Sirko May 31 '13 at 13:07
  • @ChrisTaylor - just the x axis, ignore it. – Fabricio May 31 '13 at 13:08
  • @ChrisTaylor: The x-axis/x=0 I’d guess … – CBroe May 31 '13 at 13:08
  • 2
    Obviously, the black line is some signal, and red are local minima / maxima. But it does not seem to me that the red rampart curve keeps the area, @Fabricio needs to specify this task more before anyone can answer. And I hate so say that, but what did you try, @Fabricio? – Boris Stitnicky May 31 '13 at 13:09
  • @Fabricio: In which (data) format is the black wave given to you? As this picture? – Bergi May 31 '13 at 13:11
  • @BorisStitnicky: Actually I'm just wondering how I could convert that. None specific task. These days I'm playing with kinect and analyzing some points and it give me things like that (a bit more fuzzy though), so I was wondering if there is some algorithm to convert such things. – Fabricio May 31 '13 at 13:15
  • @Fabricio: I'd imagine that most often you would want to keep the integral under the curve between the local maxima and minima, but you can have different requirements. All in all, I think that asking this on SO is premature before you have a concrete problem. It's just so interesting, that I'm not gonna flag it for closing, but upvote it instead. So, quickly, formulate the problem statement and make up some "what did you try" idea, before content nazis close your question as too vague :-) – Boris Stitnicky May 31 '13 at 13:18
  • @BorisStitnicky: Heh, I was wondering in a generic/abstrac way. I didnt realize that that would be so complex. – Fabricio May 31 '13 at 13:22
  • @Fabricio Do you have a mathematical description of what you want? Is there only one unique discretization for a given analog black wave? What I mean is, could you draw the intervals differently and still serve the purpose you want? How do you make the decision when to switch from local minimum to local maximum with the red line? – G. Bach May 31 '13 at 13:44
  • 3
    Please improve your title so that others with the same problem can find this question. – Raymond Chen May 31 '13 at 13:54
  • When does the red signal change size? – sethi May 31 '13 at 13:56
  • @Fabricio This won't get exactly your red lines, but it kind of looks like you want the steps to happen at inflection points. Is that true? That would make a lot more sense than midpoints in most applications, I think. – Aaron Dufour May 31 '13 at 15:11
  • 1
    This is not a quantization problem. Quantization does not quantize just the extrema, it digitizes all parts of the signal. – Tyler Durden May 31 '13 at 15:21
  • Do you have the data available somewhere, for the curve? Would make it a lot easier for people to help test possible solutions. – Lasse V. Karlsen May 31 '13 at 22:26
  • @wildplasser: Those characters wouldn't have been useless. It's not clear how FFT would apply here. You could have explained that for example. – recursive May 31 '13 at 22:33

2 Answers2

3

Taking forward Jesse Craig's answer and dukeling's comment of spotting a switch between increasing and decreasing does yield a solution, at least in simple cases where there is no noise.

E.g. with this input signal

enter image description here

if you calculate the differences between consecutive values of y (the code below is in R, so is operating on vectors)

diffs = y[2:length(y)] - y[1:length(y)-1]

then the signs of the differences

dir = sign(diffs)

assuming that no values are equal (we have no zeros in diffs), you can spot a direction change by looking for where the signs are different

dir_change = dir[2:length(dir)] != dir[1:length(dir)-1]
# no change of direction for first two positions
dir_change = c(FALSE, FALSE, dir_change)

This identifies the maxima and minima, (where dir_change is TRUE)

enter image description here

and the square wave can be calculated as Jesse Craig suggested, by taking the midpoints between the maxima and minima.

So far so good. I wasn't sure if the OP's signal included noise. Assuming that it did, I tried a few techniques to try to identify maxima and minima with noise present, but I found it pretty hard (I've spent at least 10x as long trying to get an algorithm that is robust to noise as I did on the above code). I tried a moving average, and some simple thresholding, but I couldn't get either technique to work straightforwardly. This seems to confirm it's not trivial to deal with noise! I'd be interested if anyone could comment (or I could search for or ask an SO question on this).

Edit there is a nice summary of peak detection methods in this answer.

Community
  • 1
  • 1
TooTone
  • 7,129
  • 5
  • 34
  • 60
2

You need to use a local search technique like Hill Climbing to identify all the local minimums and maximums. That will give you all the horizontals lines in your square wave. Then find the mid point (value of X for the mean value of Y) between adjacent local maximums and minimums and that will tell you where the edges (vertical lines) in your square wave are found.

Jesse Craig
  • 560
  • 5
  • 18
  • 1
    Fabricio's verticals do not seem to be at midpoints. He did not answer yet what are his requirements for the rampart curve, and he did not tell us what did he try yet, so you shouln't answer him so eagerly yet. I know you want more reputation, but I'mm going to upvote some other works of yours. Feel better now? – Boris Stitnicky May 31 '13 at 13:15
  • @Fabricio: Great. So we have the first hint regarding the problem formulation. – Boris Stitnicky May 31 '13 at 13:31
  • @Fabricio: Kinect you say. So you would need some sort of real time stream processing. – Boris Stitnicky May 31 '13 at 13:41
  • 4
    If the "black wave" is a stream of points, rather than something more complex, you don't even need to complicate it as much as using Hill Climbing - just record where it switches between increasing and decreasing, which is easy to do. Though, in either case, if there's noise you'll need some modification so you don't generate a mess. – Bernhard Barker May 31 '13 at 15:50
  • @Dukeling agreed. It seems fairly straightforward unless you have noise. I'd be interested to see an answer that suggested how to deal with noise (using some kind of tolerance, or smoothing or curve fitting possibly, but the curve fitting is complicated by the fact that it seems to be a stream rather than a finite set of points). – TooTone May 31 '13 at 16:34