Verwijdering van uitschieters bij reistijdberekening met kentekenherkenning

Kentekenherkenningssytemen leveren soms uitschieters in de reistijden op. Trajecten zijn niet altijd 'gesloten'; het is soms mogelijk dat voertuigen afslaan en met een omweg bij de volgende camera arriveren. Zo ontstaan de uitschieters in de reistijden. Maria Salomons van de TU Delft heeft een algoritme ontworpen om deze uitschieters uit de dataset te filteren. Onderstaand artikel beschrijft de werking van dit algoritme.

Het uitschietersprobleem

Voor kentekenherkenning worden verschillende camera’s langs een bepaalde route geplaatst. In een (stedelijk) wegennetwerk is het soms mogelijk om met een omweg van de ene naar de andere camera te rijden. Als reistijden worden gebruikt voor dynamisch verkeersmanagement, verkeersinformatie en de validatie van verkeersmodellen zijn echter alleen de directe reistijden interessant. Voertuigen die via een omweg of met een tijdelijke stop tussen de twee camera’s rijden, zijn zogenoemde uitschieters.

Onderstaande figuur illustreert het uitschietersprobleem. Uit de figuur kan worden afgelezen dat alle reistijden langer dan duizend seconden uitschieters zijn. Het merendeel van de reistijden ligt tussen de honderd en tweehonderd seconden. Tijdens de ochtendspits nemen de reistijden toe tot boven de negenhonderd seconden, in de avondspits tot zeshonderd seconden.

Grubb’s test

Het doel van de studie van Salomons is om een methode te ontwikkelen die uitschieters detecteert. Die methode moet kunnen werken met pieken in de reistijden, maar incidentele uitschieters verwijderen. De eerste stap in de ontwikkeling van zo'n methode is om de maximale waarde voor de reistijd te bepalen. Ook reistijden die lager zijn dan de grenswaarde voor reistijd kunnen echter uitschieters zijn. Om deze uitschieters te detecteren wordt de Moving Grubb’s test gebruikt. De Grubb’s test is een methode waarmee uitschieters in een dataset kunnen worden gedetecteerd. Doordat de reistijden variëren in de tijd, wordt de Grubb’s test toegepast met een meelopend tijdskader. Er wordt een tijdkader gevormd waarbinnen de Grubb's test wordt toegepast. Dit tijdskader verschuift over de dag. In dit kader wordt de reistijd min of meer constant verondersteld.

Bij de Moving Grubb’s test worden de volgende stappen uitgevoerd:

• Verwijder de uitschieters die buiten het betreffende tijdskader i (van ΔT) vallen.
• Bereken de Z-waarde voor de reistijd T:

$\operatorname{Z}_{i} = {| {\mu_{1}} - {T}_{i}| \over \sigma^2_{1}}\$

$mu$ = gemiddelde reistijd binnen het tijdskader

$sigma^2$ = standaard deviatie van de reistijd binnen het tijdskader

Als de Z-waarde groter is dan de kritieke Z-waarde wordt de reistijd T gezien als een uitschieter.

• Verwijder de uitschieter uit de dataset met reistijden binnen het tijdskader. Herhaal de berekening met de nieuwe gemiddelde reistijd en standaard deviatie, totdat geen uitschieters meer worden gemeten.
• Verschuif het tijdskader met een stap ΔT en verwijder de uitschieters in de nieuwe dataset.

Onderstaande figuur geeft het resultaat weer van de verwijdering van de uitschieters. Hierbij is gebruik gemaakt van een tijdkader van ΔT = 900 seconden. De metingen die zijn herkend als uitschieters zijn weergegeven met een kruis.

Median Boundary methode

Het tijdskader moet zorgvuldig worden gekozen. Immers, als het kader te groot is worden metingen die geen uitschieters zijn verwijderd. En als het kader te klein is worden uitschieters niet herkend. Reistijden die over de dag niet variëren doen het beter met een groot tijdskader. Met veel variatie in de reistijden is een kleiner tijdskader beter. Onderstaande figuur laat de resultaten zien van een dataset met relatief gelijke reistijden, maar met eenzelfde tijdskader als hierboven. Zoals uit de figuur blijkt, worden minder goede resultaten behaald als in het bovenstaande figuur. Om het juiste tijdkader bij een dataset te vinden is de Median Boundary Methode toegevoegd aan het algoritme.

Een dataset zoals deze is meestal afkomstig van een traject met weinig verkeer en van een traject met (meestal) voldoende capaciteit. De hogere reistijden in deze datasets zijn (bijna altijd) afkomstig van voertuigen die een omweg nemen of een stop maken binnen het gemeten traject. Voor een relatief vlakke dataset kunnen alle reistijden hoger dan bijvoorbeeld 410 seconden in het voorbeeld worden verwijderd. Echter, indien er toch een piek in de dataset blijkt te zitten - bijvoorbeeld bij een incident -, dan wordt die ook verwijderd. De reistijd is dan niet betrouwbaar meer. Doordat vooraf niet bekend is of de dataset pieken bevat of relatief vlak is, is een methode ontwikkeld die zowel geschikte resultaten boekt voor datasets met pieken als voor vlakke datasets: de Median Boundary methode.

Binnen deze methode worden de volgende stappen uitgevoerd:

• Filter de dataset met behulp van de hiervoor beschreven Moving Grubb’s test.
• Bepaal de mediaan (M) en de mediaan absolute deviatie (MAD) voor elk tijdskader.
• Indien een meting in het betreffende tijdskader i groter is dan:

$\operatorname{B}_{i} = K+{M}_{i}+1.5 {MAD}_{i}\$

wordt het gezien als een uitschieter.

• Vervolgens wordt M_O, de mediaan van de uitschieters in het betreffende tijdskader i, en MAD_O, de MAD van alle uitschieters uit het betreffende tijdskader i, bepaald. De uitschieters in het betreffende tijdskader i vormen een groep als geldt:

$\operatorname{MAD}_{O} < 3+ {1 \over N}sum_{i} MAD_i \$

waarbij N het aantal tijdskaders is.

indien een groep van uitschieter is gevonden, wordt de grens van uitgerekt volgens:

$\operatorname {B}_{i} = B + M_{O} + 1.5 {1 \over N}sum_{i} MAD_i \$

Nu wordt een uitschieter in het tijdskader i verwijderd als de meting groter is dan B_i.

Onderstaande twee figuren geven de verwijdering van de uitschieters aan met behulp van de Median Boundary methode. De eerste figuur geeft de filtering aan van een relatief vlakke dataset. De tweede de filtering van een dataset met pieken.

Bronnen

Maria Salomons, TU Delft faculteit Civiele Techniek en Geowetenschappen, afdeling Transport & Planning

Openstaande vragen

Momenteel geen openstaande vragen. Aanvullingen zijn altijd welkom.