• Michael Wilkinson bedacht een bijzonder algoritme

    Superzeef helpt rampen bestrijden

    Slechts weinig mensen raken opgewonden van een algoritme. Sterker nog, veel mensen weten niet eens wat het is. Maar op de vijfde verdieping van de Bernouilliborg, ergens aan de noordkant van het gebouw, zit een man die al begint te stuiteren bij het woord alleen.

    Wat is een algoritme?

    Een algoritme is een serie instructies voor het uitvoeren van een wiskundige berekening. Zo’n instructie bevat bijvoorbeeld aanwijzingen over waar benodigde gegevens vandaan moeten worden gehaald en wat er met deze gegevens moet gebeuren om het gewenste resultaat te bereiken. Elke actie in een algoritme is een wiskundige bewerking en door het uitvoeren van deze acties kan een algoritme patronen herleiden uit grote hoeveelheden data.

    Die man is Michael Wilkinson, universitair hoofddocent Intelligent Systems aan de bètafaculteit. Een vrolijke, enthousiaste man, met de neiging met ingewikkelde termen als ‘differentieel morfologisch profiel’ en ‘flooding’ te strooien – en daarbij ook nog aan te nemen dat de betekenis daarvan algemeen bekend is.

    Dat is niet zo. Toch geeft het niets. Wilkinson beschikt namelijk ook over de kracht je langzaam maar zeker mee te voeren in zijn wereld van algoritmen. Een wereld die vooral draait om algoritmen die samenhang detecteren tussen structuren in beelden en die dat ook nog supersnel doen.

    Superzeef

    Hoe die algoritmen precies werken, legt Wilkinson uit aan de hand van een powerpoint-presentatie. Een presentatie van zeker dertig slides en op meer dan de helft prijken ingewikkelde formules, boomstructuren en grafieken.

    algoritme-raster
    Luchtfoto die door de computer in vierkantjes ingedeeld is.

    Gelukkig zijn er ook plaatjes. Plaatjes die wél duidelijk maken wat een algoritme precies doet. Wilkinson laat een luchtfoto zien van Haïti voor en na de aardbeving in 2010. ‘Een algoritme werkt in dit geval als een soort superzeef’, zegt Wilkinson. ‘De software filtert de plaatjes, het kijkt naar de samenhang tussen structuren op basis van 256 grijswaarden. Structuren met veel contrast vallen op. Maar als iets kapot is, is dat fijner en is het contrast dus minder.’

    36 minuten

    Een beeld, een plaatje, is in feite een som van vierkantjes. Nog niet zo lang geleden werden die beelden – afkomstig van satellieten, van vliegtuigen of van Google – op de computer ingedeeld in vierkantjes. Puin tekende Wilkinson met de hand in op het scherm. Dat is precies zoals bij grote rampen nog altijd de verwoesting in beeld wordt gebracht.

    Dat kan sneller dacht Wilkinson en hij kwam – samen met zijn collega’s Georgios Ouzounis, Martino Pesaresi en Pierre Soille uit Ispra in Italië – met een supersnelle, geautomatiseerde variant.

    ‘De eerste, klassieke algoritmen waren langzaam’, zegt Wilkinson. ‘Als je een foto neemt van de ravage na de aardbeving in Haïti zou een oorspronkelijk algoritme er 34.000 jaar over doen om het puin in kaart te brengen. Een lineair algoritme zou er 104 dagen over doen.’ Maar Wilkinson ontwikkelde een parallel algoritme en dat doet er slechts 36 minuten over.

    Verdeel en heers

    De truc? ‘Verdeel en heers’, zegt Wilkinson. Hij springt op van zijn stoel om op het grote scherm aan te wijzen hoe het werkt. ‘Je snijdt als het ware plakjes van een beeld’, zegt hij, terwijl zijn hand een hakbeweging maakt. ‘Zo’n beeld bestaat uit 1,5 miljoen megapixel. Dat zijn 100.000 plaatjes van vijftien megapixel en iedere pixel staat voor 15 centimeter op de grond.’

    Met een boomstructuur is dat heel goed in kaart te brengen. ‘Eerder maakten we van elke plak een structuur’, zegt Wilkinson. ‘Maar we wisten toen niet wat er aan de randen van de stroken gebeurde. Dat viel weg, er was op die plekken geen structuur meer te herkennen.’ Nu wordt er een boomstructuur gemaakt van het hele beeld.

    Deze animatie toont een oude tekst van Ubbo Emmius. Het laat zien hoe deze met hulp van het algoritme van Wilkinson ‘schoon’ is gemaakt. De grijswaarden lager dan een bepaalde waarde zijn eruit gezeefd, waardoor uiteindelijk een schoon document tevoorschijn komt.

    In de vierkantjes die vroeger per plakje om het puin werden getrokken, zat veel ruis. Nu, in de gehele boomstructuur, wordt er gekeken naar de samenhang tussen structuren. ‘Dat kan in allerlei vormen zijn’, zegt Wilkinson. ‘De beelden wordt niet meer in vierkantjes gedrukt. Er valt niets meer weg.’

    Grijswaarden

    Hoe dat er uit ziet, is het makkelijkste voor te stellen aan de hand van oude documenten. Op oud drukwerk schemert de achterpagina vaak door. Wilkinson en Ouzounis kunnen het digitaliseren als een schone pagina. ‘Het algoritme kijkt naar contrastwaarde. Pixels van dezelfde kleur worden gegroepeerd en alles met een grijswaarde lager dan een bepaald punt, valt er buiten.’ De schone letter wordt als één geheel gezien, niet als een deel in een vierkantje.

    Toegepast op natuurrampen als de aardbeving in Haïti of de cycloon die over de Filipijnen raasde, maakt zo’n algoritme het mogelijk om snel en gemakklijk de verwoestingen in beeld te brengen. En kunnen hulpverleners sneller naar de juiste plek gestuurd worden.

    Maar algoritmen worden niet alleen gebruikt om puin na aardbevingen of tsunami’s te detecteren. ‘Ze zijn handig in allerlei wetenschappen’, benadrukt Wilkinson. ‘Om melkwegstelsels die samensmelten in kaart te brengen, worden algoritmen gebruikt. Ook is voor ons supersnelle algoritme al interesse van bedrijven. Voor nummerplaatherkenning, in de surveillance en de dermatologie.’

    Slide 30

    Dan is daar opeens slide 30. Wilkinson slaakt een zucht en gaat weer op zijn stoel zitten. ‘Dat was het algoritme in het kort’, zegt hij. ‘Spannend, niet? Nog vragen?’