Rotaatioinvariantit vertailualgoritmit

Läpivalaisukuvien vertailussa joudutaan kahta kaksiulotteista kuvaa vertaamaan kaikissa mahdollisissa kulmissa. Tämä on varsin raskasta, kun kulmia on kuvan sivuun verrannollinen määrä [#!rt!#]. (Pessimistisempien arvioiden mukaan niitä on sivun pituuden neliöön verrannollinen määrä [#!cm!#].) Laskennan työläyttä voidaan pyrkiä vähentämään mm. hierarkisella vertailulla, polaarimuunnoksella ja sinogrammien vertailulla. Hierarkisessa vertailussa verrataan kuvia kaikissa kulmissa ensin karkeampina versioina karsien tarkemmista vertailuvaiheista pois ne orientaatiot, jotka eivät voi tulla kysymykseen. Napakoordinaattiesitykseen muunnettaessa voidaan jokaista kehää verrata yksiulotteisen korrelaation avulla rotaatioinvariantisti. Kuva voidaan muuntaa napakoordinaatistoesitykseen ajassa 26#26 ja 29#29 vertailua voidaan tehdä kukin ajassa 30#30, jolloin koko kuvan rotaatioinvariantti vertailu onnistuu ajassa 24#24. Menetelmän suurin ongelma on se, että siinä oletetaan (ainakin periaatteessa) keskipisteen olevan kohtalaisen tarkka. Toinen napakoordinaattimuunnokseen perustuva vertailualgoritmi on sektorien vertailu. Kuva voidaan muuttaa napakoordinaattiesitykseen ajassa 26#26, sektorit voidaan laskea ajassa 26#26 ja vertailu onnistuu ajassa 30#30, jolloin koko algoritmin suoritusajaksi tulee 26#26. Myös tässä algoritmissa tehdään oletus kuvan keskipisteestä, mutta se ei ole kuitenkaan yhtä herkkä kuin edellinen. Se soveltuu mahdollisesti esisuotimeksi, jolla poimitaan esimerkiksi 31#31 parasta ehdotusta. Sinogrammien avulla kuvia voidaan vertailla rotaatioinvariantisti seuraavasti: lasketaan kuvista Radon-muunnokset (eli sinogrammit) ajassa 24#24 ja vertaillaan sinogrammin jokaista riviä toisen sinogrammin jokaiseen riviin ajassa 32#32. Algoritmi ei siis tuo parannusta suoritusaikaan, mutta se vähentää dramaattisesti kohinaa ja on siis luotettavampi vertailumenetelmä. Yksinkertaisemmilla vertailuilla (esim. rivien euklidisen etäisyyden laskemisella) päästään kokonaissuoritusaikaan 24#24. Käyttämällä vertailukohteena mallin kolmiulotteista Radon-muunnosta päästään suoritusaikaan 32#32 mikä on kolmiulotteisen Radon-muunnoksen laskemiseen kuluva aika. Eräs tapa vertailla kahta kuvaa rotaatioinvariantisti tai ainakin löytää hyviä ehdokkaita niiden väliseksi kiertokulmaksi on laskea kummankin kuvan massajakauma sektoreittain ja vertailla näitä jakaumia toisiinsa. Kuvassa 7.1 on havainnollistettu algoritmin toimintaa, ylhäällä on vertailtavat kuvat ja niiden alapuolella massajakaumat, joita sitten vertaillaan toisiinsa. Jakaumien laskeminen tapahtuu käyttämällä valmiiksi laskettua taulukkoa, joka on vertailtavien kuvien kokoinen, ja jossa jokaista kuvapistettä kohden on lista niistä sektoreista, joihin kuvapisteen massa jakautuu. Tämä onnistuu ajassa 26#26. Jotta pienet keskipisteen epätarkkuudet eivät dominoisi jakaumien vertailua, lasketaan massajakaumista vielä diskreetit differenssit kaavalla 33#33 ajassa 34#34 missä A on sektoreiden määrä. Tämän jälkeen etsitään ne vaihesiirtymät, joilla laskettujen diskreettejen differenssien neliöpoikkeama on pienimmillään. Tämä voidaan tehdä ajassa 35#35. Menetelmän etuna on sen nopeus ja se, että summattaessa koko sektorin massa yhteen pienenee kohinan merkitys vertailussa. Haittana on oletus keskipisteen suhtellisen oikeasta sijainnista ja summaamisen aiheuttama informaation menetys tilanteissa, joissa kuvan massa jakautuu kulman suhteen tasaisesti.

  

Figure 7.1: Massajakaumien vertailu

36#36