OpenCV je započet s razvojem 1999. godine od strane Gary Bradsky-a, te je prva inačica puštena 2000. godine. Gary-u Bradsky-u se kasnije pridružuje Vadim Pisarevsky u upravljanju Intelovim Ruskim timom za OpenCV. U 2005. godini OpenCV je korišten na Stanely-u, mašina koja je 2005 godine osvojila DARPA Grand Challenge. Danas OpenCV podržava mnogo različith algoritama poveznih s kompjuterskim "promatranjem"(Computer Vision) i strojnim učenjem te raste iz dana u dan. Trenutno OpenCV podržava veliki broj programskih jezika kao što su C++, Python, Java i ostali, a isto tako dostupan je i na različitim platformama uključujući Windows, Linux, OS X, Android, iOS. Isto tako sučelja bazirana na CUDA-i i OpenCL-u su aktivno razvijana za vrlo brze procesorske operacije.
Kako bi mogli započeti bilo koji projekt vezan uz OpenCV potrebno je računalu postaviti sliku koju nastojimo naći ili prepoznati u nekoj drugoj slici. U praktičnom djelu, može se vidjeti da je slika koju smo mi učitali znak stop na bjeloj podlozi. Računalo ovu sliku kao i svaku drugu vidi kao niz bitova, te je potrebno te bitove nekako usporediti da bi mogli međusobno usporediti slike. Postoji nekoliko načina postavljanja ključnih točaka na slici te traženja tih točaka na promatranoj slici. Ali ono što je zajedničko svim algoritmima je pretvaranje slike iz RGB u BGR format slike. BGR format vraća polje s vrijednostima za plavu, zelenu i crvenu boju.
Za početak važno je objasniti što su to značajke slike. Ovaj pojam je najlakše objasniti preko slaganja puzli. Slaganjem puzli slažemo velik broj rascjepkanih djelova slike koji su najčešće razbacani i ne odgovaraju rasporedom, u cijelinu koja predstavlja željenu sliku. Čovjek prilikom slaganja puzli prvo gleda značajke tih puzli, odnosno na koji način se puzle mogu povezati. Broj „muških“ i „ženskih“ djelova puzli se može promatrati kao jedna značajka. Ti djelovi najčešće nisu istog oblika, pa se i oblik tih djelova može promatrati kao druga značajka. Kad smo uspijeli nači dvije značajke koje odgovaraju oblikom jedna drugoj, potrebno je promotriti boje, ukoliko i boje odgovaraju promatramo oblike koje kreiraju boje i linije na puzlama koje želimo spojiti, kad sve značajke odgovaraju tek onda možemo spojiti puzle. Spajanjem svih puzli na ovaj način dobivamo originalnu sliku. Na isti način bi se moglo opisati traženje podudarnosti između slike koju smo postavili da tražimo, i slike na kojoj tražimo tu sliku. Razlika je u ljudskom razumjevanju i dodjeljivanju vrijednosti značajki i računalnom dodjeljivanju značajki koje će se promatrati i uspoređivati. Kako bi što jednostavnije našli tražene značajka, treba prvo potražiti jedinstvene uzorke na slici, koje se jednostavno prati i uspoređuje. Problem se pojavljuje kad mi to želimo prikazati računalu na način da on to razumije.
Slika 1: Usporedba traženja jedinstvenih uzoraka i ponavljajućih uzoraka
Sa slike 1 se može jasno vidjeti koliko je lakše pronači točno mjesto na slici ako imamo uzorak kao što je prikazano pod okvirima, E i F, a isto tako koliko je teško smjetiti kvadrate A i B na njihovo mjesto jer pregledom slike se može uočiti više mjesta gdje bi ti oblici pristajali.
Slika 2: Objašnjenje razumjevanja unikatnosti djelova slike
Crveni kvadrat predstavlja kutove. Kutovi se najlakše mogu pronaći i usporediti iz razloga jer se mogu pozicionirati samo na djelove koji odgovaraju kutu i orijentaciji. Crni pravokutnik predstavlja rub. Rub je nešto teže pronaći od kuta ali opet puno jednostavnije nego područje prekriveno plavim pravokutnikom. Područje prekriveno plavim pravokutnikom odgovara području prikazanom na 70% slike, tako je izrazito teško odrediti točnu lokaciju. Ovaj dio tražen ja djela slike se zove detekcija značajki slike. Logičan nastavak detekcija značajki je opis tih značajki kako bi ih mogli tražiti na drugoj slici. Postoji nekoliko algoritama za detekciju značajki slike, ovdje će biti pobrojani te će biti prikazane slike nad kojima je primjenjen određeni algortiam, te će biti opisan algoritam koji je korišten u projektu.
Algoritmi za detekciju i deskripciju(opisivanje značajki):
Slika3: Detekcija kutova uz pomoć Harissovog algoritma
Slika 4: Detekcija kutova i dobrih značajki za praćenje uz pomoć Shi Tomasi algoritma
Slika 5: Rezultat dobiven detekcijom FAST algoritmom
Slika 6: Rezultat dobiven detekcijom ORB algoritmom
U našem projektu korišten je algoritam STAR za otkrivanje značajki.
Slika 7: Broj detektiranih značajki
Na temelju slike se može vidjeti da STAR algoritam definira najamnje značajki, ove značajke su najčešće, prema rezultatima uspoređivanja, jedinstvene i izbjegavaju šumove, te je jednostavno uspoređivanje. Na sljedećoj slici će biti prikazano omjer vremena potrebnog da algoritam detektira cjeli okvir i da detektira ključnu točku.
Slika 8: Utrošak milisekundi po značajki
Sa slike se može vidjeti da FAST, kao što je i očekivano troši najmanje vremena za detektiranje značajki, jer detektira veliki broj značajki. GFTT pyramid, SURF i STAR pokazuju solidne rezultate dok, MSER za gotovo sve slike troši najviše vremena za otkrivanje značajki
Usporedba na mobilnim uređajima
Slika 9: Utrošak vremena(Laptop, iPhone)
Sa slike se može vidjeti da svi algoritmi troše mnogo više vremena na smartphone-u nego na destkop aplikacijama. Uprvo zbog toga važno je optimizirati kod kako traženje i izvođenje nebi predugo trajalo.
Na dosadašnjim slikama se mogla vidjeti usporedba različitih tipova algoritama, pravi razlog zašto smo odabrali STAR prikazana je na sljedeće dvije slike
Slika 10: Broj pogrešaka prilikom otkrivanja značajki
Slika 11: Postotak uspješnosti otkrivanja značajki
Na ovim slikama se jasno može vidjeti da STAR algoritam prikazuje najmanje pogrešaka prilikom otkrivanja ključnih točaka na drugoj slici, dok istovremeno ima najveći postotak uspješno otkrivenih značajki. Nedostatak STAR algoritma je u opisivanju značajki, odnosno STAR služi isključivo za detekciju značajki, dok se opisivanje istih mora obaviti pomoću drugih algoritama.
Za opisivanje značajki u našem projektu odlučili smo se za FREAK koji služi samo za opisivanje značajki Klasa FREAK metoda public DescriptorExtractor Klasa koja implementira FREAK(Fast Retina Keypoint) deskriptor ključnih točaka. Algoritam predlaže novi deskriptor ključnih točaka inspiriran ljudskim vizualnim sustavom ili preciznije mrežnicom. Kaskada binarnih nizova izračunava se toliko učinkovito da se može usporediti sa intezitetom s kojim mrežnica radi uzorkovanje uzorka. Za razliku od SIFT, SURF i BRISK algoritma, FREAK se općenito brže izvodi i to s manje memorijskog opterećenja.
FREAK konstruktor
FREAK::FREAK(bool orientationNormalized=true, boolscaleNormalized=true, float patternScale=22.0f, int nOctaves=4, const vector
Nakon što smo otkrili značajke na slikama te postavili deskriptore za svaku pojedinu ključnu točku, kreće proces traženja sličnosti između slike koju smo postavili i slike s kojom uspoređujemo. važno je naći ključne točke koje se podudaraju, ako se te ključne točke podudaraju spajamo te dvije točke. Ukoliko imamo dovoljno spojenih točaka(korisnički definrano), rezultat je pronađena slika, unutar slike na kojoj smo tražili. Kao i za detekciju, opisivanje, tako i za upravianje postoji više različitih algoritama, mi smo se odlučili za BRUTEFORCE_HAMMING algoritam, BRUTEFORCE označava algoritam za uparivanje, dok HAMMING ekstenzija označava da se takav algoritam koristi na binarnom deskriptoru. BRUTE-FORCE „uparivač“ je jednostavan, koristi opis jedne od značajki i provjerava podudarnost sa svim ostalima na temelju njihovih međusobnih udaljenosti.
Slika 12: Rezultat dobiven uparivanjem značajki uz pomoć Brute-Force matcher-a