TEMPLATE MATCHING OF SPECKLE IMAGES USING A SUM OF ABSOLUTE DIFFERENCES ALGORITHM ON FPGA Template matching of speckle images using a sum of absolute differences algorithm on FPGA

Abstract

I denne oppgaven er forskjellige malmatching-algoritmer, samt eksempler på deres mask- invareimplementasjoner sammenlignet. Algoritmene er Normalisert Kryss-korrelasjon, Null- gjennomsnittlig Normalisert Kryss-korrelsjon og Sum av Absolutte differanser, som er vanlige å bruke i malmatching. Å utføre kryss-korrelasjon gjennom Fourier transform er også sam- menlignet. Sum av absolutte differanser var valgt som en algoritme å implementere på et ZCU104 Evaluerings sett, for å akselerere malmatching-prosessen ved å bruke en FPGA. Designet plasserer refernase og mal data i PS RAM på en flettet måte, før det sender data gjennom DMA til PL. Desinet funket ikke på FPGAen, og ingen malmatching-prosess var utført i mask- invare. Estimeringer av implementasjonen viser at på grunn av den trege minnehåndtering ville systemet vært tregere enn en alternativ høynivå tilnærming. Dette skyldes flettingen av data i tillegg til mange minneaksesser. Teoretisk utførelse hvor man antar mer effektiv minnehåndtering viser betydelig akselerasjon av prosessen, spesielt for små malstørrelser. Støymessig virker algoritmen særlig treffsikker for store malstørrelser når Gaussisk støy er lagt på bildene. For store maler, er de få feil og de feilene er små. For små malstørrelser er treffsikkerheten lav. De største feilene er også signifikante.

In this thesis, different template matching algorithms and examples of their hardware imple- mentations are compared. The algorithms are Normalized Cross-Correlation (NCC), Zero- mean Normalized Cross Correlation and Sum of Absolute Differences, which are commonly used for template matching. A Fourier transform approach for Cross-correlation is also compared. Sum of Absolute Differences was chosen as an algorithm to implement on the ZCU104 Evaluation kit, in order to accelerate the template matching process using the FPGA. The design places reference and template data in PS RAM in an interleaved fashion, and uses DMA to transfer data to the PL. The design was not implemented correctly on the FPGA, and no template matching process was completed in hardware. Estimations of the implemen- tation also show that the slow memory organization would make the system slower than an alternative high level approach. This is caused by the interleaving of memory, as well as many memory accesses. Theoretical execution assuming more efficient memory organization show significant speed-up. Accuracy wise, the algorithm shows high accuracy for larger template sizes when a Gaussian noise is added. For these larger template sizes, there are few and small errors. For smaller template sizes, the hit rate is poor. The largest errors for smaller templates are significant.