Door Rean Neil Luces
Template matching is een belangrijk onderwerp op het gebied van Artificial Intelligence (AI), omdat het een van de benaderingen is van het basisprobleem van beeldverwerking, namelijk het lokaliseren van het gebied van belang. Het zoekt uit waar een bepaald object zich in het gegeven beeld bevindt. Het heeft een breed scala van toepassingen, zoals object detectie, tracking, bewaking, medische beeldvorming, en image stitching.
Template matching bestaat ook uit twee hoofdcomponenten: het bronbeeld en het sjabloonbeeld of de patch. Het bronbeeld is het beeld waarin we verwachten een overeenkomst te vinden met het sjabloonbeeld, terwijl het sjabloonbeeld het patchbeeld is dat zal worden vergeleken met het subbeeld van het bronbeeld.
De twee algemene classificaties van sjabloon- of beeldmatching zijn sjabloon-gebaseerd en feature-gebaseerd. De op sjabloon gebaseerde benadering, ook bekend als de gebiedsgebaseerde benadering, functioneert zeer goed wanneer sjablonen geen sterke kenmerken hebben met een beeld, aangezien zij direct op de pixelwaarden werken. Overeenkomsten worden gemeten aan de hand van de intensiteitswaarden van zowel het beeld als het sjabloon. Anderzijds wordt de op kenmerken gebaseerde aanpak gebruikt wanneer zowel bron- als sjabloonbeelden meer overeenkomst vertonen wat betreft kenmerken en controlepunten. In dit geval omvatten de kenmerken punten, curven of een oppervlaktemodel om de template-matching uit te voeren.
Template-gebaseerde benadering
De template-gebaseerde benadering is eenvoudiger te implementeren dan de feature-gebaseerde benadering. Bij eenvoudige sjabloonmatching wordt het sjabloonbeeld vergeleken met het bronbeeld door het te verschuiven. Het sjabloonbeeld wordt één pixel per keer van links naar rechts of van boven naar onder verschoven, zodat een numerieke maat van overeenkomst met het overlappende beeld kan worden berekend. Beide beelden worden omgezet in binaire beelden of in zwart-wit en dan worden technieken voor het matchen van sjablonen toegepast, zoals genormaliseerde kruiscorrelatie, kruiscorrelatie en som van het gekwadrateerde verschil.
Een van de uitdagingen van de sjabloon-gebaseerde benadering is schaalinvariantie. Veranderingen in de grootte van het bronbeeld of het sjabloonbeeld zullen de prestaties van het algoritme beïnvloeden. Een eenvoudige truc om dit probleem op te lossen is om de sjabloonafbeelding te vergroten of te verkleinen en dan te vergelijken met de bronafbeelding. Na het doorlopen van alle schalen, neemt u het gebied met de grootste correlatiecoëfficiënt en gebruikt u dat als het “gematchte” gebied. De rotatie invariantie is echter moeilijk op te lossen met deze aanpak. Daarom heeft Kim, Hae & Araújo, Sidnei (2007) het Ciratefi-algoritme ontwikkeld om het rotatieprobleem op te lossen door het brute-krachtalgoritme te verbeteren, waarbij het sjabloonbeeld onder elke hoek wordt geroteerd. Het Ciratefi-algoritme is 400 keer sneller dan het brute-force-algoritme en levert dezelfde resultaten op.
Feature-based Approach
Afbeeldingseigenschappen, zoals randen en interessante punten, bieden rijke informatie over de beeldinhoud. Lokale kenmerken en hun descriptoren zijn de bouwstenen van veel computervisie-algoritmen. Hun toepassingen omvatten beeldregistratie, objectdetectie en -classificatie, traceren en bewegingsschatting. Deze kenmerken zijn exclusief voor elk beeld en helpen dus bij het identificeren tussen beelden. De kenmerken van een beeld blijven behouden, zelfs als de grootte en de oriëntatie veranderen, zodat de aanpak nog bruikbaarder kan blijken als de overeenkomst in het zoekbeeld op de een of andere manier wordt getransformeerd. Deze aanpak is ook efficiënter te gebruiken als het beeld een grote resolutie heeft. Het schuiven van het sjabloonbeeld in een groot bronbeeld, pixel voor pixel, en het herhalen in verschillende schalen zal rekenkundig duur zijn.
Feature-based template matching omvat vier hoofdstappen. De eerste twee stappen zijn feature detection en feature extraction. SIFT (Scale Invariant Feature Transform) en SURF (Speeded Up Robust Feature) zijn het meest bruikbaar om kenmerken te detecteren en te matchen, omdat ze invariant zijn voor schaal, rotatie, vertaling, belichting en vervaging. Na de detectie en extractie van kenmerken is de volgende stap het matchen van kenmerken met behulp van Fast Library for Approximate Nearest Neighbors (FLANN). Deze bevat een verzameling algoritmen die geoptimaliseerd zijn voor snel zoeken naar de dichtstbijzijnde buren in grote datasets en kenmerken met hoge dimensies. Uit de overeenkomende kenmerken die door FLANN matcher zijn verzameld, worden goede overeenkomsten geselecteerd op basis van Lowe’s ratio test. Na het filteren van kenmerkpunten is de volgende stap het berekenen van homografie door middel van het RANdom SAmple Consensus (RANSAC) algoritme.
Deze aanpak kan echter niet worden gebruikt wanneer de beelden minder kenmerken hebben of verschillende objecten dezelfde kenmerken hebben, omdat het algoritme er dan niet in slaagt het sjabloon in het bronbeeld te vinden.