Outliers

Some readings are not noisy, they are wrong. The median, and gating on what you expected.

U4.4Noise and filteringUniversity25 min

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Moving average and low-pass filters explained

Noise is a reading that is a little wrong. An outlier is a reading that is not a measurement of what you think it is measuring.

Depth sensors produce them constantly: the beam misses the object and hits the far wall, or nothing at all and comes back at maximum range; something crosses in front; the surface is dark or at a sharp angle and the return is nonsense. None of that is Gaussian, and averaging it is actively harmful. One reading of 400 in an average of ten shifts the answer by 34 cm.

Watch one happen

The wall in this scene is narrow. As the robot swings, the wall leaves the sensor's view and the reading jumps to whatever is behind it.

from bugbot import *
connect()

drive(0, 0, 40)
for i in range(40):
    print(round(distance(), 1))
    wait(0.1)
stop()

Run this in the simulator

A tidy run of numbers around 89 while the wall is ahead, then 143.9 and a stretch between 136 and 162 once the beam has slipped past the end of the wall and is reaching the far edge of the mat, then a slow fall as the robot swings round to face the side and the back. To a program holding a gap to the wall, those readings in the 140s are not noisy measurements of the wall. They are measurements of something else.

From above, the robot turning past the end of a narrow wall, and the distance readings it gets as it turnswallrobotfar edge of the matfrom above01234050100150time, sdistance, cmthe wallthe far edgeturning to theside and back
The robot turns on the spot. While the beam hits the wall it reads about 89 cm (green). A few degrees later the beam passes the end of the wall and reaches the far edge of the mat: 143.9 cm and more (red). Those readings are not noisy measurements of the wall; they measure something else.

The scene has a second kind of outlier, the "something crosses in front" kind. Another robot shuttles across the mat between you and the wall. Drive towards the wall and print what the sensor says:

from bugbot import *
connect()

forward(40)
for i in range(50):
    print(round(distance(), 1))
    wait(0.1)
stop()

Run this in the simulator

The readings fall steadily from 89 towards 56, except twice. At about 1.1 s they read 55.0 and 55.6 between neighbours of 84 and 80, and at about 3.5 s they read 31.2 and 35.7 between 67 and 64. Both times the other robot was in the beam: two readings each, both far too short. A program that stops at 35 cm from the wall would stop at the second one, about 30 cm early.

Distance readings while driving at the wall: they fall steadily, except for two pairs of readings far too short01234520406080100time, sdistance, cmstop at 35 cmthe other robotthe other robota stop here, with the wallstill about 66 cm away
The readings from the second cell. They fall steadily from about 89 cm, except at 1.1 s and 3.5 s, when the other robot was in the beam. The second pair dips below 35 cm, so a program that trusts every reading stops there.

A mean of five is dragged down by the very first of them. A median of five ignores the first two and only follows once three of the five are wrong, so it rides out a short spike completely but not a change that lasts. That is what a gate, below, is for.

The median filter

Keep the last n readings and take the middle one:

window.append(raw)
if len(window) > 5:
    window.pop(0)
estimate = sorted(window)[len(window) // 2]

A median of five survives two bad readings out of five untouched. That is what robust means in statistics: the answer does not depend on the worst data, only on the middle of it. The price is that a median rounds off genuine sharp changes too, and it costs a sort per tick, which on a microcontroller at 200 Hz is not free.

Gating

The cheaper and often better method is to refuse readings that disagree with what you expected:

if abs(raw - expected) > GATE:
    pass                 # ignore it, and count it
else:
    accept(raw)

Where does expected come from? Your model: the last estimate, or a prediction of where the wall should be given how far you have driven. This is the shape of validation gating in tracking systems, and in a Kalman filter the gate is set from the covariance so that it widens exactly when the filter is genuinely unsure.

A gate: a band either side of the expected distance; readings outside it are refused and counted5060708090100the next few readingsdistance, cmrefused: 1refused: 2green band: expected,plus or minus GATE
Each green band is where the next reading is expected: the last accepted estimate, plus or minus GATE. Readings inside it are accepted and move the band. The two short ones fall outside, so they are refused, and the count goes up.

Count what you reject. A gate that is throwing away half the readings is not protecting you, it is hiding the fact that your expectation is wrong. Print the number. A filter that silently discards data is a filter that will lie to you one day.

Task: throw out the wrong ones

Drive towards the wall with a median filter and a gate running, and stop 35 cm from it, without being fooled by the robot that crosses in front. Plot raw and median, and print thrown out:, the number of readings your gate rejected.

from bugbot import *
connect()

window = []
thrown = 0

Challenges

  1. Compare a mean of five with a median of five on the same data, plotted together.
  2. Set the gate too tight and watch the count of rejections climb. What does the estimate do?
  3. Reject any reading at maximum range before doing anything else. Is that a gate or a special case?