Fast Correlation Computations on Large Image Data Sets
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3098525Utgivelsesdato
2023Metadata
Vis full innførselSamlinger
Sammendrag
Målet med denne masteroppgåva er å optimalisere krysskorrelasjon for ei stor mengd bilete med flekkemønster(speckle patterns). Dette skal også implementerast i maskinvare. Krysskorrelasjon kan brukas til å finne forskyving av to bildete med overlapp. Flekkemønstre får ein av å lyse ein laser på ei overflate. Denne overflata vil ha ein ruleik slik at laserlyset vil sprette i ulike rettingar basert på ruleiken. Ein kan då observera eit flekkemønster. Desse flekkemønstera kan bli brukast å måle lokasjon på eit objekt eller ei overflate svært nøyaktig. Men viss ein skal representera eit objekt eller ei overflate med flekkemønster må ein ha mange bilete. Dette er naudsynt sidan laserlyset vil observerast ulikt sjølv med små flyttingar. Dette førar då til at krysskorrelasjonsutrekningane, som alt tek tid, vil ta enno lenger tid.
Krysskorrelasjon kan gjerast i det romlege planet eller i frekvensplanet. I denne masteroppgåva vil vi bruka frekvensplanet for å utnytte at flekkemønster vil fordele seg i ein jamn kjegleform i frekvensspekteret. Dette kjenneteiknet er då brukt til å utvikle delvis krysskorrelasjon. Delvis krysskorrelasjon utfører berre korrelasjonsberekningane på delar av frekvensspekteret. Dette gjer at ein får ei særdels rask utrenking. Sjølv om det er berre delar av frekvensspekteret som blir brukt, så er delvis krysskorrelasjon framleis nøyaktig.
Delvis krysskorrelasjon har vorte implementert og testa med høgnivåspåket Python. Python er eit programmeringsspråk som eignar seg godt for rask utvikling og implementering av algoritmar. Resultata av testinga viser at det er mogleg å bruka delvis krysskorrelasjon for å finne forskyving i flekkemøsterbilete. Resultata viser også at det er eit potensiale for bruk på andre bilete, men med lågare presisjon. Testing med ulike system viser ei kraftig forbetring i programvareyting smamalikna med den vanlege metoden på mellom 300 og 500 gonger for bilete som har ein storleik på 512 gonger 512.
Delvis krysskorrelasjon eignar seg godt for ein maskinvareimplementasjon. Resursbruken er kraftig redusert både i form av logikk og lagringsplass. Delvis krysskorrelasjon bruker 256 gonger mindre plass på å lagra frekvensspektera enn den vanlege metoden når bileta er 512 gonger 512. Trongen for maskinvareresursar er også kraftig redusert, og det er enklare å implementera delvis krysskorrelasjon. Ytelseforbetringane i maskinvare over programvare er mellom 13 og 190 gonger. The aim of this thesis is to optimize the cross-correlation of a large number of speckle images and implement it in hardware. Cross-correlation may be used to find the displacement of images with overlapping content. Speckle images are obtained by shining a laser on a surface. The laser will scatter in different directions depending on the roughness of the surface. This may then be used to measure a location very accurately. However, even small changes to the observing location will make the speckle pattern appear differently. Consequently, there is a need for a substantial amount of images to represent an object or area. Cross-correlation is computationally heavy and therefore a substantial amount of time may be used if there is a large number of images.
Cross-correlation may be performed in the spatial domain or the frequency domain. In this thesis, the frequency domain is used to capitalize on the characteristics of speckle images in the frequency domain. The frequencies of a speckle image will be distributed in an even cone shape in the frequency spectrum. This characteristic was then used to create the suggested solution of partial cross-correlation. Partial cross-correlation performs cross-correlation on parts of the frequency spectrum. This allows for a significant increase in performance, and the method still gives an exact result.
Partial cross-correlation is tested with the high-level programming language Python. This allows for a fast implementation. The results show that Partial cross-correlation is viable for use on speckle images. The use of partial cross-correlation on normal images may be possible, however, without pixel accuracy. Partial cross-correlation shows a performance improvement over the normal method of between 300 and 500 times depending on the system used and when the image size is 512 by 512.
Partial cross-correlation is very resource friendly. The data that is required to store the image frequency spectrums is reduced by 256 when the image size is 512 by 512. The hardware needed to implement partial cross-correlation is also greatly reduced compared to the normal method and no resource optimization is necessary. The performance improvements of using partial cross-correlation in hardware rather than software are between 14 and 190, depending on the system used.