Lucid Mesh

Up until now we've been learning about the fundamental concepts and basic tools of digital signal processing (DSP). Now we're going to use those tools to solve a common problem in DSP: edge detection. When you think of edge detection, you probably immediately think of image processing and finding edges in photographs or a video signal. It's true that there are plenty of edge detection applications in image processing, especially with some of the new technologies being developed for self-driving cars, facial recognition, and automatic photo processing, but edge detection is useful in a much wider range of applications than that.

Anywhere you need to monitor a signal for a change of state is a likely candidate for edge detection. That would include the feedback systems in robotic motion, industrial automation, touch screens and other touch inputs, pressure sensors in car airbag safety systems, accelerometers in any toy or gadget that senses motion, and the list goes on. Sometimes, the relevant signal in these systems varies within a well-defined range, and the edge is easy to detect by setting a fixed threshold. If the signal crosses the threshold, the system detects an edge and does what it needs to do.

Other times edge detection is not so simple. If the signal drifts around over long periods of time, or the threshold for the occurrence of an edge doesn't necessarily happen at the same value every time, it's difficult or impossible to set a fixed threshold for detecting an edge. In cases like this, we need to do some further processing to build up a signal that we can assign a fixed threshold to for detecting edges. That's the kind of problem we'll attempt to solve here, detecting edges in a signal where the edges tend to happen anywhere within its range. Let's start by generating a representative signal that would be somewhat difficult to process.

The Signal

Real-world signals are not pristine, well-behaved things. They can have noise and random components, so we'll make the signal we're going to process have these characteristics. We'll have the signal randomly jump between values in its range, creating edges that we will attempt to locate. On top of this signal, we'll add some random noise with a peak amplitude that is half the minimum size of an edge. This combination makes it quite difficult to define a fixed threshold for detecting edges. Here's what it looks like (click the graph to start and stop scrolling):


Hopefully your signals will have a better signal-to-noise ratio than this one does. Notice how on the edges there isn't even necessarily a clean jump from one level to the next. The noise in the signal creates glitches in the edges that could cause multiple edges to be detected if we're not careful.

Discounting the noise, the signal levels between edges are quite stable, and the signal you're working with may not have such stable values between edges. Real signals can drift or have lower-frequency noise that isn't represented in this signal, but the algorithm we'll develop would still work in many of these cases. The primary function of the algorithm is to detect a sustained change in the signal that happens within a short enough timespan while ignoring the superfluous noise.

Smoothing

The first thing we need to do with this signal is get rid of some of the noise, and to do that, we can use one of our handy-dandy averaging methods. Any of the moving average, exponential average, or filtering methods will work, but we're going to make some assumptions about the system we're designing the algorithm for. Let's say it's an embedded system without a huge amount of processing power or external memory because the system architecture is also being designed to meet certain power and cost requirements.

Also, assume that processing this signal is not the only thing the system has to do in real-time. It has other control, logging, and signal processing tasks to take care of, so we can't spend all of the time between samples running the perfect smoothing filter. In situations like this, the exponential average is the DSP tool of choice because it requires only a couple of variables for storing the weighting factor and previous average and can be computed in only a few operations.

Let's define a function to calculate the smoothed samples of the incoming signal. I'll show JavaScript code, which may or may not be available in a real embedded system, but that's not too much of an issue since C code would be fairly similar.

function ExpAvg(sample, avg, w) {
  return w*sample + (1-w)*avg
}

The avg parameter that's passed into ExpAvg() is the previous exponential average, and w is the weighting of the current sample and must be less than one. If we use a value of 0.25 for the weighting on our generated signal, the smoothed signal looks like this (click to start and stop the signal):


The exponential average doesn't completely remove the noise, but it does clean up the signal dramatically, reducing the amplitude of the noise and revealing more of the edges. Now that we have a smoother signal, how can we do the actual edge detection?

Finding the Edge

Ideally, we want to compare the signal to a fixed reference so that an edge can be detected simply by observing a large difference between the signal and the reference. Since we don't have a fixed reference to compare the signal to, we'll have to create one. What we want is another signal that follows the smoothed signal with a delay, but without needing to store a large queue of samples from the signal to create that delay. The easiest way to create such a signal is to use the exponential average again, but this time with a much smaller weighting on the newest sample.

If we use a weighting of 0.0625 for the second exponential average, we get the second signal in red in the following graph:


The red signal can be referred to as the slow average and the blue signal as the fast average because the red signal reacts more slowly to changes in value than the blue signal does. It is also even smoother than the fast average, having removed nearly all of the noise from the original signal, but that's not important for our purposes. The important thing is that the slow average acts like a reference for the fast average.

Now that we have a slower-moving pseudo-reference signal, what do we do with it? Subtract it from the fast average, of course. After doing that we get the following white signal:


In this case I took the absolute value of the subtraction, so all edges will create a positive spike in the difference signal. If the direction of the edge is important, then you would want to do only the subtraction and leave out the absolute value. The purple horizontal line that's plotted along with the white signal is a static threshold that we can use to detect the edges. Whenever the white signal crosses the threshold from below, we can mark that point as an edge. Notice that it doesn't matter where in the range of the signal the edges occur, the same static threshold works for all of them.

Here's what the algorithm looks like in JavaScript:

function EdgeDetect(samples, threshold) {
  var fastAvg = samples[0]
  var slowAvg = samples[0]
  var prevDifference = 0
  var edges = []

  samples.forEach(function (sample) {
    fastAvg = ExpAvg(sample, fastAvg, 0.25)
    slowAvg = ExpAvg(sample, slowAvg, 0.0625)
    var difference = Math.abs(fastAvg - slowAvg)
    isEdge = prevDifference < threshold && difference >= threshold
    edges.push(isEdge)
    prevDifference = difference
  })

  return edges
}

This function takes an array of samples and the static threshold used to mark edges and returns an array of boolean values that mark the indexes where edges occur. A real-time system will look a little different because the samples will come one at a time instead of all together in an array. In that case, the fast and slow averages and the previous difference need to be static variables that persist between function calls, or they need to be passed into and returned from the function so that they can be maintained by the caller.

Another issue that may come up in a real system is that unwanted noise in the difference signal may cause multiple edge detections within a small number of samples. To prevent this from occurring, you can either ignore edge detections for some number of samples after an initial edge detection or add hysteresis to the threshold. Hysteresis effectively widens the threshold, creating a no-man's land where values can't trigger an edge detection. If the difference crosses the threshold plus the hysteresis, an edge is detected. Another edge will not be detected until the difference crosses below the threshold minus the hysteresis to reset the edge detector.

There you have it, a simple algorithm for edge detection that amounts to a couple of exponential averages, a subtraction, and a couple of comparisons. What could be easier than that? As an added bonus, we can do something else with this edge detection algorithm by changing one of the parameters and tweaking it a bit.

In-Range Detection

Instead of edge detection, sometimes you want to detect when a signal increases by some amount and then recovers near its original value, but like with edge detection, the high and low values may drift over time. When the signal increases by at least a certain amount, it's considered in-range, and when it decreases again or enough time has passed, it's considered out-of-range.

The same algorithm used for edge detection will work for in-range detection if we dramatically slow down the slow average. Instead of a weighting of 0.0625, let's use a value of 0.001. Because this exponential average will move sooooo slowly, we want to readjust it quickly when the fast average moves out of range. Otherwise, it can take too long for the slow average to catch up, and later movements of the signal will be missed. To reset the slow average, we can simply reassign the slow average value to the fast average value whenever the fast average drops below it. Now the signals look like this:


Remember that the fast average is in blue and the slow average is in red. The difference between them is the white signal, and the threshold is the purple horizontal line. Whenever the fast average moves up so that that the difference crosses the threshold, an in-range value is detected. Then the slow average creeps up to the fast average, and if the slow average reaches the fast average, it acts like a timeout and establishes a new baseline for an out-of-range signal. Then another increase in the fast average will be detected as a new in-range signal. If the fast average drops down, it pushes the slow average with it so that a new lower baseline is quickly established in case the fast average jumps up again.

In this case the difference signal can also be used as a gate so that some other action is either allowed or prevented as long as the signal is within range. (Another way to think about this is that the signal is active when it's in range.) At the same time, the algorithm adjusts to the long-term behavior of the signal automatically. That can be very useful in systems where the relative behavior of a signal is known, but the absolute values that it will attain are uncertain or change over time, especially due to changes in the environment like temperature or humidity.

This in-range detection algorithm shows how with a few modifications, an algorithm can be used for different purposes. If you understand how an algorithm works, you can change it slightly to apply it to new problems and create more elegant solutions. Most basic algorithms are like this, where they can be combined or extended in simple ways to have wider applications. The more deeply you understand the fundamentals, the better equipped you are to design solutions that neatly fit the problem domain with simple components.

While the basic ideas used for this edge detection algorithm are simple, there are lots of options at play. Instead of an exponential average, other types of averaging can be used if you have more resources available. The amount of averaging to do for both the fast and slow averages, the threshold level, and the amount of hysteresis to use are all knobs that need to be dialed in to design the right solution for the specific problem at hand. Building the right algorithm is only part of the effort, and further experimentation, refinement, and validation are always necessary to vet out a solution.

Keep the basic ideas of edge detection—using averages to create pseudo-references and using signal differences to bring out relative changes—in mind. They're sure to come in handy for other DSP problems. Next week we'll take a look at another DSP application that uses simple components: signal envelopes.


Other DSP posts:
Basic Signals
Transforms
Sampling Theory
Averaging
Step Response of Averaging
Signal Variance
Edge Detection
Signal Envelopes
Frequency Measurement
The Discrete Fourier Transform
The DFT in Use
Spectral Peak Detection
FIR Filters
Frequency Detection
DC and Impulsive Noise Removal