20.500.12556/DKUM-62069 Pohitritev transformacije domnevnih razdalj Optimization of Quasi Distance Transform V magistrskem delu opisujemo pohitritev transformacije domnevnih razdalj, ki je izpeljanka tradicionalnih algoritmov transformacij razdalj. Transformacije razdalj običajno delujejo nad dvodimenzionalnimi binarnimi slikami, kjer vsakemu elementu ospredja določijo oddaljenost do najbližjega elementa ozadja. Kadar slika ni binarna, je nad njo potrebno izvesti dodano predprocesiranje, ki vključuje korak binarizacije. Nasprotno pa lahko transformacijo domnevnih razdalj uporabimo neposredno nad sivinskimi, barvnimi in multispektralnimi slikami in se tako izognemo pogoste neželenemu predprocesiranju. Slabost tega pristopa pa je časovna zahtevnost, ki je v naivni implementaciji kar O(N^2.5). V magistrskem delu predstavimo pohitren algoritem transformacije domnevnih razdalj ter teoretično analizo njegove časovne zahtevnosti. Nad implementiranim algoritmom izvedemo tudi meritve, s čimer potrdimo teoretične časovne zahtevnosti pohitrenega pristopa, ki je enaka O(N^1.5) v pričakovanem ter O(N^2) v najslabšem primeru. This thesis presents an optimisation of Quasi Distance Transform, derived from traditional distance transformation algorithms. Distance transform is typically applied on two-dimensional binary images, where each foreground element is assigned the distance to its closest background element. When the image is not binary, additional preprocessing with binarisation is required. On the other hand, Quasi Distance Transform can be applied directly to grayscale, colour or multi-spectral images, thus avoiding often unwanted preprocessing. However, the weakness of the method is its time complexity, which is in naive implementation equal to O(N^2.5). In this thesis, we present a new optimised algorithm and the theoretical analysis of its time complexity. We confirm the theoretical time complexity for quasi distance transformation together with measurements, thus proving they are N^(1.5) for the expected and O(N^2) for the worst case. matematična morfologija transformacija domnevnih razdalj transformacija razdalj časovna zahtevnost optimizacijske metode mathematical morphology quasi distance transform distance transform time complexity optimisation methods true true false D. Žlaus Slovenski jezik Angleški jezik Magistrsko delo/naloga 2016-08-22 14:09:17 2016-09-06 11:26:20 2022-06-28 03:07:41 2019-07-11 12:42:34 2016 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.93'11(043.2) 19836182 URN:SI:UM:DK:FIOSK6PM MAG_Zlaus_Danijel_2016.pdf MAG_Zlaus_Danijel_2016.pdf 1 78A2715B74A1A86C6C8CF6A6E44D16A4 975c10e049b2a174b72ba3151fadc6458177149997a863563debe2e30ef9387a 1125b8ba-7c0d-11eb-bb7a-00155d0001ca https://dk.um.si/Dokument.php?lang=slv&id=99391 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0