Superzeef met puinfilters

A damaged building has more smaller parts than an undamaged building. This fact forms the basis for determining which structures have survived an earthquake and which have crumbled, using satellite images. Emergency services need this information to coordinate aid, set up emergency hospitals and rescue as many survivors as possible. Collapsed structures are marked by hand on digital images. Michael Wilkinson is head university teacher at the Rijksuniversiteit Groningen, where they developed an automated way of detecting debris. Using parallel algorithms, multiple processors and morphological filters, calculation time for an area the size of Haiti has been reduced from 34.000 years to 1 hour and 22 minutes.

(rest of the article is in Dutch)

Een kapot gebouw heeft altijd meer kleine onderdelen dan een gebouw dat heel is. Op basis van dat feit is het mogelijk met satellietfoto’s te bepalen wat na een aardbeving nog overeind staat en wat in puin ligt. Het automatisch berekenen hiervan voor een gebied als Haïti kost met een klassiek algoritme 34.000 jaar. In Groningen lukt het ze nu in 1 uur en 22 minuten.

Na een zware aardbeving is het belangrijk snel te weten welke gebouwen in puin liggen, voor de coördinatie van hulpdiensten, het bepalen van de locatie van de noodhospitalen en het zo snel mogelijk redden van bedolven slachtoffers.

Satellietbeelden worden op de computer ingedeeld in rechthoekjes en puin wordt met de hand op het scherm gemarkeerd. In Haïti in 2010 werd – naast de gegevens van de ‘eyes in de sky’ – extra data verzameld met vliegtuigen. Ook Google stelt hi-resbeelden beschikbaar, alsook rekenkracht en serverruimte. Totaal ging het om 1,5 terrapixel: 100.000 plaatjes van vijftien megapixel. Iedere pixel stond voor vijftien centimeter grondoppervlak. Het markeren werd gedaan door het Joint Research Centre van de Europese Commissie in Ispra, Italië. Na vier uur vierkantjes zetten vroeg Georgios Ouzonis zich hardop af of dit niet geautomatiseerd kon worden. Hij belde de man bij wie hij jaren eerder was gepromoveerd: Michael Wilkinson, universitair hoofddocent Intelligent Systems aan de Rijksuniversiteit Groningen. Die wilde zich daar wel op storten.

Morfologisch profiel

Wilkinson: “Beeldverwerkingssoftware kijkt naar de samenhang tussen structuren in een omgeving, op basis van grijswaarden. Dit heet een differential morphological profile. Structuren met het meeste contrast vallen op. De breedte wordt ook gemeten en de software filtert als een zeef. Als iets stuk is, is het fijner dan iets dat heel is. Grote brokken blijven dus buiten beschouwing.” Idealiter leg je twee satellietfoto’s over elkaar: een van vlak voor de ramp en van erna. Dat is echter lang niet altijd mogelijk. De aarde is nog niet helemaal in kaart gebracht, niet alle data is actueel en landschappen veranderen snel, zeker wanneer ze bebouwd zijn.

Het doorrekenen van de breedte van structuren is met een klassiek algoritme niet te doen. Wilkinson: “Dat werkt kwadratisch: twee keer zo veel data kost vier keer zo lang om door te rekenen. Voor Haïti hadden we op die manier 34.000 jaar rekentijd nodig gehad.” Met een lineair algoritme kost twee keer zoveel data twee zeer zoveel tijd, maar dan nog zou het 104 dagen duren om het hele gebied in kaart te brengen. “De algoritmes draaiden allemaal op één processor, dus wij dachten: wat als we kunnen parallelliseren?” Voor het meeste beeldanalysemethoden kan dat makkelijk. Het grote plaatje wordt in stroken verdeelt en de waarden per stuk berekent. “Maar voor deze filters was het lastiger, omdat we werken met structuren. Wat als er iets op de rand van de stroken valt?”

Doorbraak

Groningen bereikte men in 2008 een doorbraak met het verbinden van de stroken in een parallel algoritme. “Toen Georgios belde gebruikten wij het al voor verschillende toepassingen. Op oud drukwerk schemert de achterkant vaak door. Wij digitaliseren het als een schone scan. Ook gebruiken we de technologie voor 3D-beeldweergave van bloedvaten in MRI-hersenscans. Voor het berekenen van satellietbeelden dacht ik dat het beter kon. Thuis heb ik een quadcore staan en dacht: waarom daar niet op?”

Hoe zien we?

De basisvragen die aan beeldverwerking ten grondslag liggen zijn ‘hoe zien we eigenlijk?’ en ‘hoe redeneren we bij het zien van objecten?’ Wilkinson legt uit: “Als mensen kijken wij naar een punt en bepalen wat daarbij hoort. Dat heet flooding. Bij bepaalde systemen is dat ingewikkeld, zoals bij spiralen en optische illusies. Het menselijk oog heeft daar problemen mee, een computer niet. Een machine kan kijken op de manier van een menselijk oog door alle pixels te laten kijken naar hun buren, puur op contrastwaarde. Pixels van dezelfde kleur worden gegroepeerd en vervolgens zoeken we het kleinste component.”

Groeperen gebeurt op verschillende kenmerken, die gerangschikt zijn in een hiërarchie. Zo is ‘groot’ hoger in hiërarchie dan ‘klein’. “Met een boomstructuur is dat heel goed te filteren. Voorheen maakten we een boomstructuur van iedere strook, maar we wisten dan niet wat er aan de randen van de stroken gebeurde. We voegen die nu efficiënt samen door één boomstructuur te maken van het complete beeld. De processoren rekenen met diezelfde boomstructuur maar voor afzonderlijke stroken. Alles gaat door dezelfde set zeven, een voor iedere grootteklasse.”

80% efficiencywinst

Maar meerdere processoren betekent een langere wachttijd, omdat de processoren op allemaal klaar moeten zijn met een klasse, voor ze de volgende stap kunnen nemen. “We hebben nu het filter, de zeef, ingewikkelder gemaakt zodat hij alle grootteklassen tegelijk kan uitrekenen. Een plaatje van 1,2 gigapixel duurde twee uur op een processor, maar acht minuten op een 24-core. “Dat is 17-18 keer zo snel met een efficiency van 70-80%. “Dat is een zeer respectabele uitkomst,” zegt Wilkinson bescheiden. Dan, met een grijns: “En dankzij subsidie van NWO krijgen we een 48-core in Groningen!” Behalve meer processoren gaat de toekomst ook een ander soort filters brengen, die naar oppervlakte kijken in plaats van breedte. “Nu bekijken we het hele object en zoeken dan het breedste stuk. Straks kijken we naar de oppervlakte en kunnen zeggen: ‘dit is te groot om puin te zijn, hier hoef je verder niks te bepalen’.” Ook daar zal weer tijdwinst te behalen zijn.

In september 2011 verzamelt JRC Ispra nieuwe data in Port au Prince. De stad wordt een ijkpunt voor het grootschalig parallel doorrekenen van data. De tsunami van 2004 was nog te vroeg: er was niet genoeg rekenkracht ter plekke. “Doorberekenen van die dataset had een half miljoen jaar zullen duren.” Voor de tsunami in Japan dit jaar werd de methode evenmin ingezet. Pas na de toetsing in september kan het systeem echt worden gebruikt. Het is een vreemd vakgebied om in te werken. “Je hoopt dat je code nooit gebruikt wordt,” zegt Wilkinson. Mocht het dan toch nodig zijn, dan draait het systeem de komende jaren samen met menselijke waarnemers. Wilkinson hoopt dat deze methode bijdraagt aan het mondiale project dat de hele aarde in beeld wil brengen op een vierkante meter per pixel. “Dan kunnen we de hele aarde in een week doorberekenen. Dat is bijvoorbeeld nuttig om sluipende veranderingen in de natuur goed vast te leggen. Soms is het wel handig dat grote broer meekijkt.”

KADER: Bessensap is een jaarlijks evenement dat NWO organiseert in samenwerking met de Vereniging van Wetenschapsjournalisten in Nederland. Het evenement brengt journalisten, redacteuren, voorlichters en mediagenieke onderzoekers onder het motto ‘Wetenschap ontmoet pers’ bij elkaar. Michael Wilkinson sprak op Bessensap 2011 over ‘speuren in satellietbeelden’ en had een echte zeef meegebracht om zijn werk te verduidelijken aan journalisten.

KADER: BIO’TJE Michael Wilkinson begon zijn academische loopbaan als student sterrenkunde omdat daar computerbeeldanalyse zat. Informatica bestond nog niet. Zijn interesse in beeldanalyse bracht hem naar de medische microbiologie als wetenschappelijk programmeur. “Dat zijn de mannen en vrouwen die de problemen oplossen voor wetenschappers.” Hij werkte aan een project over darmbacteriën en was erg goed in het werken met weinig belichting. “Als je vijf uur gewend bent in sterrenkunde, dan is vijf seconden belichting geweldig.” Daarna probeerde hij het een aantal jaren als ondernemer, tot iemand tegen hem zei: ‘Jij bent geen ondernemer, jij bent wetenschapper.’ Wilkinson voelde dat het waar was en keerde terug naar de beeldanalyse.

Hij promoveerde in 1995 in de informatica, en verwierf fondsen voor een postdoc in het modelleren van darmflora. Beeldanalyse lonkte echter weer, in de vorm van een ecologische toepassing. Diatomeeen of kiezelwieren hebben een hele specifieke structuur en specifieke soorten leven in bepaalde gebieden. Veranderingen in de populatie zijn een indicator voor subtiele ecologische veranderingen in een gebied. In 1999 werd hij UD, en richtte hij zich meer en meer op morfologische filters. Sinds 2009 is hij UHD en werkt aan theorie, algoritmen en toepassingen van filters gebaseerd op samenhang van objecten.

Advertisements