Af Rean Neil Luces
Skabelonmatchning er et vigtigt emne inden for kunstig intelligens (AI), da det er en af tiltagene til det grundlæggende problem ved billedbehandling, som er at lokalisere regionen af interesse. Den finder ud af, hvor et bestemt objekt befinder sig i det givne billede. Det har en lang række anvendelser som f.eks. objektdetektion, sporing, overvågning, medicinsk billeddannelse og billedsyning.
Skabelonmatchning består også af to hovedkomponenter: kildebilledet og skabelonbilledet eller patchen. Kildebilledet er det billede, hvor vi forventer at finde et match med skabelonbilledet, mens skabelonbilledet er det patch-billede, som vil blive sammenlignet med delbilledet af kildebilledet.
De to generelle klassifikationer af skabelon- eller billedmatchning er skabelonbaseret og funktionsbaseret. Den skabelonbaserede tilgang, også kendt som den områdebaserede tilgang, fungerer meget godt, når skabeloner ikke har nogen stærke træk med et billede, da de opererer direkte på pixelværdierne. Overensstemmelser måles ved hjælp af intensitetsværdierne for både billedet og skabelonen. På den anden side anvendes den funktionsbaserede metode, når både kilde- og skabelonbillederne indeholder flere overensstemmelser med hensyn til funktioner og kontrolpunkter. I dette tilfælde omfatter features punkter, kurver eller en overflademodel til at udføre skabelonmatchning.
Skabelonbaseret tilgang
Den skabelonbaserede tilgang er lettere at implementere end den featurebaserede. Simpel skabelonmatchning indebærer, at skabelonbilledet sammenlignes med kildebilledet ved at glide det. Skabelonbilledet flyttes en pixel ad gangen fra venstre til højre eller fra top til bund for at gøre det muligt at beregne et numerisk mål for ligheden med det område, som det overlapper. Begge billeder konverteres til binære billeder eller i sort/hvid, og derefter anvendes skabelonmatchningsteknikker som normaliseret krydskorrelation, krydskorrelation og summen af den kvadrerede forskel.
En af udfordringerne ved den skabelonbaserede tilgang er skalainvarians. Ændringer i størrelsen af kildebilledet eller skabelonbilledet vil påvirke algoritmens ydeevne. Et simpelt trick til at løse problemet er at ændre størrelsen på skabelonbilledet til flere skalaer og derefter sammenligne det med kildebilledet. Når du har gennemløbet alle størrelser, skal du tage det område med den største korrelationskoefficient og bruge det som dit “matchede” område. Rotationsinvariansen er dog vanskelig at løse med denne fremgangsmåde. Derfor har Kim, Hae & Araújo, Sidnei (2007) udviklet Ciratefi-algoritmen til at løse rotationsproblemet ved at forbedre brute force-algoritmen, som indebærer rotation af skabelonbilledet i hver enkelt vinkel. Ciratefi-algoritmen er 400 gange hurtigere end brute force-algoritmen og opnår de samme resultater.
Feature-baseret tilgang
Billedfunktioner, såsom kanter og interessepunkter, giver rig information om billedets indhold. Lokale funktioner og deres deskriptorer er byggestenene i mange algoritmer til computervision. De anvendes bl.a. til billedregistrering, objektdetektion og -klassificering, sporing og bevægelsesvurdering. Disse træk er eksklusive for hvert billede og hjælper derfor med at identificere billederne indbyrdes. Et billedes karakteristika vil forblive, selv om der sker en ændring i størrelse og orientering, så metoden kan vise sig at være yderligere nyttig, hvis matchet i det søgte billede transformeres på en eller anden måde. Denne fremgangsmåde er også mere effektiv at anvende, hvis billedet har en stor opløsning. Det vil være beregningsmæssigt dyrt at skubbe skabelonbilledet ind i et stort kildebillede en pixel ad gangen og gentage det i forskellige skalaer.
Featurebaseret skabelonmatchning omfatter fire hovedtrin. De første to trin er detektion af kendetegn og udtrækning af kendetegn. SIFT (Scale Invariant Feature Transform) og SURF (Speeded Up Robust Feature) er mest nyttige til at detektere og matche funktioner, fordi de er invariante over for skala, rotation, translation, belysning og sløring. Efter detektion og udtrækning af funktioner er det næste trin matchning af funktioner ved hjælp af FLANN (Fast Library for Approximate Nearest Neighbors). Det indeholder en samling af algoritmer, der er optimeret til hurtig søgning efter nærmeste nabo i store datasæt og med højdimensionelle funktioner. Ud af de matchende funktioner, der er indsamlet af FLANN matcher, udvælges gode matches baseret på Lowe’s ratio-test. Efter filtrering af funktionspunkter er det næste trin at beregne homografi gennem RANdom SAmple Consensus (RANSAC)-algoritmen.
Denne fremgangsmåde kan dog ikke udnyttes, når billederne har færre funktioner eller forskellige objekter deler de samme funktioner, da algoritmen ikke vil finde skabelonen i kildebilledet.