Het oplossen van legpuzzels als testcase voor automatische reconstructietechnieken
Het oplossen van legpuzzels is voor vele mensen een intrigerende bezigheid, zowel op zeer jonge, als op latere leeftijd. Het is in de eerste plaats een ontspannend tijdverdrijf en je kan je dus afvragen wat het wetenschappelijk nut is van de reconstructie van legpuzzels via de computer.
Maar als we even de analogie beschouwen tussen de puzzelstukken van een legpuzzel en de scherven van een gebroken siertegel uit de Romeinse tijd, dan wordt de wetenschappelijke relevantie misschien al duidelijker. Bij de reconstructie van een siertegel komen dezelfde problemen naar voor die optreden bij het ineenpuzzelen van de legpuzzel. Men moet zoeken naar puzzelstukken (scherven) die in elkaar passen, naar puzzelstukken (scherven) met een zelfde kleur,… Uiteindelijk moet men ook bij de tegel een rechthoekige vorm verkrijgen als eindresultaat.
Naast toepassingen in de archeologie, kan men reconstructietechnieken ook gebruiken in de forensische wetenschappen bij b.v. de reconstructie van in stukken gescheurde documenten, achtergelaten in de vuilbak door een crimineel. In de medische sector kunnen de technieken nuttig zijn bij het terug aan elkaar plaatsen van gebroken botten. Zelfs bij de productie van nieuwe medicijnen is er een mogelijke toepassing, het zoeken van passende moleculen.
Nu de link is gelegd met enkele reële problemen, blijft de vraag nog steeds waarom een computer dan nuttig kan zijn bij de reconstructie van die siertegel. Wel, het amusante tijdverdrijf bij het handmatig oplossen van een legpuzzel is het zoeken naar de puzzelstukken die in elkaar passen. Maar bij de reconstructie van die siertegel verspeelt men liever niet veel tijd aan dit proces. Daar kan de hulp van de computer een uitkomst bieden. Men kan een digitale representatie maken van alle scherven en dan de computer het tijdrovende zoeken van passende scherven laten doen. Een bijkomend voordeel is dan dat de originele fragmenten niet meer nodig zijn na de digitalisatie, zodat de fragmenten zeker geen extra beschadiging oplopen.
Het beschreven proces noemen we een semi-automatische reconstructie van de siertegel. Als naast het zoeken van de passende scherven, ook het ineenpassen van de scherven gebeurt door middel van de computer, dan spreken we van een volledig automatische reconstructie. Bij siertegels die gebroken zijn in een klein aantal scherven is deze volledig automatische reconstructie zeker mogelijk, maar dan kan men net zo goed de tegel handmatig reconstrueren omdat de tijdwinst nihil is. Bij de meeste reële reconstructie problemen is een volledig automatische reconstructie echter een utopie door de enorme complexiteit bij veel fragmenten en/of door het gebrek aan voldoende diversiteit in de fragmenten. Dit is de reden dat men meestal werkt op vereenvoudigde varianten van het gestelde probleem voor het ontwikkelen van de basistechnieken.
Sinds 1964 kan men tussen de wetenschappelijke artikels over reconstructietechnieken regelmatig een artikel terugvinden dat het oplossen van legpuzzels met behulp van computeralgoritmen behandelt. Hieruit blijkt dus dat het automatisch oplossen van een legpuzzel een populaire vereenvoudigde variant is. De populariteit is te verklaren door de het feit dat quasi iedereen weet wat een legpuzzel is, en zo wordt het gestelde probleem beter vatbaar. Een andere verklaring is dat de testobjecten (de puzzelstukken) zeer makkelijk verkrijgbaar zijn.
Nu beschrijven we de stappen die we doorlopen hebben om te komen tot de oplossing van de legpuzzel via de computer. Bij het reconstrueren van de siertegel zouden we juist dezelfde stappen doorlopen.
De eerste stap is vanzelfsprekend het digitaliseren van alle puzzelstukken. Via een eenvoudige scanprocedure wordt van meerdere puzzelstukken tegelijkertijd een digitaal beeld gevormd. De bekomen digitale beelden van de puzzelstukken worden dan één voor één gesegmenteerd en elk puzzelstukken wordt apart opgeslagen op de harde schijf. De segmentatie kunnen we best aanschouwelijk voorstellen als het knippen van de puzzelstukken uit het digitale beeld. Bij het manueel ineenpuzzelen zou je er niet op letten, maar voor een computer is het zeer belangrijk dat we rekening houden met de eventuele vuiltjes die aan de puzzelstukken kunnen hangen. Dit hebben we gedaan door ze te gebruiken in een formaat dat zeer robust is tegen zo'n problemen.
De volgende stap is dan het zoeken van de juiste plaats in de legpuzzel van alle puzzelstukken. Dit verloopt zeer analoog met de methode die de meeste puzzelaars gebruiken. Eerst worden de hoekstukken en de randstukken gezocht en daarmee wordt de rand van de legpuzzel gevormd. De computer probeert één voor één de puzzelstukken te passen bij de reeds gelegde randpuzzelstukken totdat de volledige rand gelegd is. Deze procedure wordt dan herhaald voor de puzzelstukken binnen de rand. Het programma stopt uiteindelijk als alle puzzelstukken een plaats gekregen hebben. Hoe goed twee puzzelstukken in of bij elkaar passen wordt bepaald op basis van de vorm en kleur van de twee puzzelstukken. De manier waarop dit gebeurt is ook hier geïnspireerd op de puzzeltechnieken die een puzzelaar gebruikt.
Het ultieme resultaat van deze uitdaging is het kunnen oplossen van een legpuzzel van 300 puzzelstukken in 244 seconden. Het aantal puzzelstukken lijkt misschien weinig, maar het is op dit moment de grootste legpuzzel die automatisch opgelost is met behulp van een computer. Aan de volgende dus om dit record te breken…