Racunarski vid - Masina skripta

Question 1

1. Na koji način je moguće detektovati ivice na slici koja poseduje šum korišćenjem najmanje dva operatora?

Answer 1

• Zavisno od tipa šuma isčistiti sliku Gausom ili medijan filterom
• Zatim na isčišćenoj slici primeniti Sobel operator
• Sobel je izvod slike. Kombinovanjem vertikalnog i horizontalnog Sobela mogu da se dobiju sve ivice na slici. Sobel vraća rezultat u opsegu -255 do 255.
  SLIKA

Question 2

2. Koja je razlika između Gausovog šuma i šuma „so i biber“ (eng. salt and pepper) i koji filtri se koriste za njihovo uklanjanje iz slika?

Answer 2

Gaus – šum koji prati normalnu (Gausovu raspodelu) u odnosu na čistu sliku. Manifestuje se kao visoke frekvencije. Uklanja se Gausovim filterom koji propušta samo niske frekvancije, dok visoke frekvencije eliminiše zamućenjem.
So-biber – šum koji predstavlja velike skokove u signalu. Manifestuje se crnim i belim pikselima na slici. Uklanja se medijan filterom. (Za određeni prozor vrednosti, te vrednosti sortira i uzima onu koja se nalazi na sredini sortiranog niza vrednosti – na taj način eliminiše skokovite promene.)

Question 3

3. Koji filter se koristi za pooštravanje (eng. sharpening) slika i da li je bitno da li se koristi konvolucija ili korelacija?

Answer 3

Konvolucija i korelacija su identične ukoliko je filter simetričan!
Koristi se filter sa slike. Najpre se poveća intenzitet slike, a zatim se od takve slike oduzme slika zamućena box filterom. Dobije se efekat akcentovanja razlika u odnosu na lokalu srednju vrednost.
SLIKA

Question 4

4. Na koji način se morfološke operacije otvaranja i zatvaranja definišu preko dilacije i erozije (grafički ilustrovati)?

Answer 4

Otvaranje – Najpre se vrši erozija radi izdvajanja elemenata, a zatim dilacija kako bi se održala originalna površina. Koristi se isti strukturni element za obe operacije. Otvaranje elementa A elementom B predstavlja uniju svih položaja B unutar A.

Zatvaranje – Najpre se vrši dilacija radi spajanja elemenata, a zatim erozija radi održanja originalne površine. Koristi se isti strukturni element. Zatvaranje elementa A elementom B predstavlja komplement unije svih translacija B, tako da se ne poklapa sa A.
SLIKA

Question 5

Zatvaranje – Najpre se vrši dilacija radi spajanja elemenata, a zatim erozija radi održanja originalne površine. Koristi se isti strukturni element. Zatvaranje elementa A elementom B predstavlja komplement unije svih translacija B, tako da se ne poklapa sa A.

Answer 5

Korišćenjem većeg strukturnog elementa popuniće se i sve rupe i uglovi koji su veći od manjeg strukturnog elementa a manji ili jednaki većem strukturnom elementu. Tj. određeni skup rupa i uglova koji ne bi bio zahvaćen tj. popunjen (izravnat) korišćenjem manjeg strukturnog elementa, bio bi korišćenjem većeg.

Question 6

6. Kako izgleda izlaz Furijeove transformacije kada slika poseduje horizontalne sinusoidalne promene intenziteta (skicirati i objasniti)?

Answer 6

Izlaz Furijeove transformacije slike uvek sadrži 1 beli px u sredini slike, oko njega nalaze se simetrični parovi piksela, gde svaki par opisuje jednu sinusoidalnu komponentu. Za horizontalne sinusoidne promene intenziteta u slici, rezultujući par piksela nalazi se horizontalno raspoređen nakon Furijeove transformacije. Ukoliko su 2 px u paru bliža, to označava nižu frekvenciju, ukoliko su dalja to označava višu frekvenciju.

Question 7

7. Zbog čega konvolucija slike sa Gausovim filtrom smanjuje visoke frekvencije?

Answer 7

Konvolucija u prostornom domenu odgovara množenju u frekventnom domenu.
U frekventnom domenu, visoke frekvencije se nalaze na obodu slike, a niske bliže centru slike. Gausov filter u frekventnom domenu sadrži samo elemente bliske centru slike, pa množenjem sa njim dolazi samo do propuštanja elemenata iz tog dela slike, koji odgovaraju niskim frekvencijama, dok se visoke frekvencije elminišu.
SLIKA

Question 8

8. Kako se manifestuje „aliasing“ i šta ga uzrokuje (grafički ilustrovati)? Koja tehnika se primenjuje da bi se izbegao ovaj efekat?

Answer 8

Alijasing predstavlja promenu frekventne konstitucije slike pri sabsemplingu. Na slici se manifestuje iskrzanim ivicama, deformisanim teksturama, na videu može prouzrokovati prividno okretanje točka automobila u suprotnom smeru itd. Uzok alijasingu je diskretizacija ulaznog signala premalim skupom vrednosti, tako da rekonstrukcijom signala na osnovu tih vrednosti možemo da dobijemo signal koji ne liči ni približno na originalni.
Da bi se izbegao ovaj efekat koristi se Nikvist-Šenonova teorema koja nalaže da semplovanje signala mora da se vrši frekvencijom duplo većom od najveće frekvencije u signalu, kako bi se izbegao alijasing. Da bi se to postiglo povećava se frekvencija semplovanja tako da zadovoljava ovaj uslov, ukoliko je to moguće. Ili, ukoliko nije, vrši se odbacivanje frekvencija iz signala većih od polovine frekvencije semplovanja. Za slike, ovo se radi tako što se primeni zamućenje Gausovim filterom pre sabsemplinga. Ova metoda dovodi do gubitka određene količine informacija, ali je i dalje bolja opcija od pojave alijasinga koji rezultuje time da vidimo nešto što uopšte ne postoji.
SLIKA

Question 9

9. Opisati proces detekcije ivica korišćenjem Canny detektora?

Answer 9

• Na sliku se primenjuju izvodi Gausove funkcije za x i y
• Na osnovu njih se odrede jačina i orijentacija gradijenata
• Zatim se vrši potiskivanje ne-maksimuma (tanjenje - thinning) – Višepikselne ivice se tanje tako da budu debljine 1px. To se postiže tako što se proverava da li je piksel lokalni maksimum duž pravca gradijenta. Uzimaju se u obzir i intenzitet i orijentacija gradijenta. Za px se posmatraju njegovi susedi u pravcu gradijenta, ukoliko susedi imaju manje intenzitete, dati px se uzima da pripada ivici. Ukoliko neki od susednih piksela ima veći gradijent, taj px se uzima i poredi sa svojim susedima.
• Vrši se povezivanje i pragovanje – histerezis. Koriste se dva praga, niži i viši. Najpre se uzimaju samo pikseli koji prođu viši prag. Nakon toga se posmatraju pikseli koji prolaze niži prag, a nisu prošli viši. Ukoliko su takvi pikseli povezani sa ivicom koja je prošla viši prag, uzimaju se u obzir, ukoliko nisu, odbaicju se.
  Veličinom Gausovog filtera u prvom koraku kontroliše se broj ivica koji će biti detektovan. Veći filter rezultuje uklanjanjem slabih i bliskih ivica.

Question 10

10. Koji filter, tj. funkciju je moguće iskoristi za izdvajanje ivica na slici?

Answer 10

Ivica na slici predstavlja mesto gde se dešava nagla promena u funkciji intenziteta slike. Tako da se ivice mogu detektovati kao ekstremi prvog izvoda slike.
Izvod slike može se dobiti zahvaljujući Sobel operatoru.
Kombinovanjem horizontalnog i vertikalnog rezultata, dobijamo Sobelov gradijent koji nam daje lokaciju svih ivica na slici
gde je gx odziv na Sx, a gy odziv na Sy
Međutim, kako je slika, pa i same ivice, šumovita, potrebno je pre izvoda slike, istu isčistiti primenom Gausove funkcije. Kako bi se izbegla dupla obrada iste slike, moguće je izvod primeniti nad Gausovom funkcijom, pa onda taj prvi izvod Gausove funkcije primeniti na sliku i dobiće se isti rezultat. Ovakvo rešenje daje pozitivne i negativne vrednosti za lokaciju ivice pa je potrebno pretražiti i jedne i druge. Ukoliko želimo uniformno ponašanje funkcije za svaku lokaciju ivice, možemo da koristimo drugi izvod Gausove funkcije, tj. Laplasijan Gausa koji nam omogućava da ivice uvek vidimo kao tačke preseka funkcije sa X osom.
SLIKE VISE KOMADA

Question 11

11. Standardna Hough-ova transformacija se zasniva na glasanju za određene parametarske oblike. Zbog čega se primenjuje ova tehnika i zašto daje rezultate?

Answer 11

Ova tehinika primenjuje se zato što je previše zahtevno proveriti sve moguće modele uparivanjem svakog modela sa svakim podskupom detektovanih fičera. Uz pomoć glasanja samo jednim prolaskom svi fičeri glasaju za modele kojima pripadaju, pa tresholdovanjem rezultata dobijamo sve detektovane modele odjednom. Ovaj metod daje dobre rezultate jer, iako i šum i klaterski fičeri učestvuju u glasanju, oni znatno manje doprinose finalnom skoru pa se njihov uticaj može zanemariti jer će „pravi“ fičeri dati mnogo veći broj glasova. Dodatno, nedostajući elementi modela ne prave problem jer to samo znači par glasova manje, dok će i dalje svi detektovani fičeri dati svoje glasove za pravi model pa će on svakako moći da bude detektovan tresholdovanjem.

Question 12

12. Ukoliko je potrebno da se nađu loptice za bilijar na slici bilijarskog stola, da li je prikladnije koristiti Hough-ovu transformaciju ili RANSAC algoritam? Obrazložiti odgovor.

Answer 12

Prikladnije je koristiti Hough-ovu transformaciju jer su bilijarske loptice fiksne veličine tj. sve imaju isti radijus pa se mogu predstaviti uniformnim 2D modelom u Hough-ovom prostoru. Poznavanje poluprečnika bilijarske loptice omogućava nam da samo na osnovu podataka koje vraća Canny edge detektor u jednom prolasku detektujemo sve instance modela. Ovo čini Hough-ovu transformaciju optimalnijim rešenjem u odnosu na RANSAC algoritam u ovom slučaju.

Question 13

13. Kada kažemo da deskriptori ključnih tačaka trebaju da budu i „invarijantni“ i „prepoznatljivi“, na šta se odnosi „invarijatnost“ i zašto je onda neophodna?

Answer 13

Invarijantnost se odnosi na to da fičer deskriptor treba da bude približno isti nezavisno od, odnosno da njegova prepoznatljivost ne zavisi od fotometrijskih transformacija kao što su promene u osvetljenju scene, niti od geometrijskih transformacija kao što su translacija, rotacija, skaliranje, smicanje… Invarijantnost je neophodna osobina za deskriptor jer nam omogućava da detektujemo isti fičer na više različitih slika, nezavisno od uslova u kojima su te slike slikane, odnosno od položaja fičera na slici i njegove osvetljenosti.

Question 14

14. Harisov detektor uglova koristi matricu momenta drugog reda. Grafički ilustrovati i objasniti kakve sopstvene vrednosti te matrice (λ1 i λ2) ukazuju na dobar fičer za praćenje.

Answer 14

Ukoliko su λ1 i λ2 sopstvene vrednosti matrice momenta drugog reda, možemo da kažemo da opisuju dobar fičer za praćenje ukoliko su obe vrednosti veće od određene donje granice i ukoliko su međusobno uporedive, odnosno ne važi da je jedna vrednost znatno veća od druge. Ukoliko λ1 i λ2 zadovoljvaju ove uslove, to znači da se patch koji opisuju razlikuje značajno od patch-eva susednih u svim pravcima na slici.

Question 15

15. Na koji način je moguće fičer detektor (npr. SIFT) učiniti invarijantnim na promene u osvetljenju?

Answer 15

Da bi fičer deskriptor bio invarijantan na osvetljenje neophodno je, nakon što smo ga učinili invarijantnim na geometrijske transformacije, da se izvrši normalizacija magnituda u deskriptoru na opseg 0-1. Nakon toga se vrši odsecanje svih magnituda većih od 0.2 kako bi se postigla robusnost na nelinearne efekte osvetljenja. Opseg 0-0.2 se zatim opet normalizuje na opseg 0-1.

Question 16

16. Da li su Harisovi uglovi invarijantni na rotaciju? Obrazložiti odgovor. Kakva je situacija po ovom pitanju kod SIFT-a?

Answer 16

Harisovi uglovi jesu invarijantni na rotaciju jer se pri rotaciji slike rotiraju i elipse matrice momenta drugog reda, čime se menja samo njihova orijentacija ali ne i oblik tj. sopstvene vrednosti na osnovu kojih se zapravo vrši opisivanje fičera. SIFT je takođe invarijantan na rotaciju jer se na nivou svakog fičera nalazi dominantan smer gradijenta i na osnovu njega određuje orijentacija čitavog fičera koji se shodno tome rotira. Rezultat toga je da imamo normalizovan fičer koji ne zavisi od orijentacije u kojoj je detektovan na samoj slici.

Question 17

17. Na koji način se vrši formiranje vektora koji predstavlja SIFT deskriptor fičera?

Answer 17

Oblast fičera se najpre normalizuje, vrši se njeno skaliranje shodno skali za koju je dobijen maksimalni odziv i njeno rotiranje zavisno od dominantnog smera gradijenta za tu oblast. Centar tako normalizovane oblasti je u samoj karakterističnoj tački. Na takvu oblast primenjuje se Gausov filter kojim se smanjuje uticaj gradijenata koji su udaljeniji od centra oblasti i povećava uticaj same karakteristične tačke i njoj bliskih piksela. Tako dobijena oblast deli se na matricu 4x4, čiji svaki element predstavlja podmatricu takođe dimenzija 4x4. Na nivou elemenata podmatrice, svih
16x16 elemenata ima svoj gradijent. Na nivou podmatrice (4x4) od 16 gradijenata formira se 8-elementni histogram tako što se za svaki od gradijenata proverava u koju od 8 raspoloživih oblasti spada i njegova amplituda se dodaje na tu vrednost u histogramu. Sada je čitava oblast opisana kao matrica 4x4 8-elementnih histograma. Linearizacijom tih vrednosti dobijamo 448 = 128 komponentni vektor. Tako dobijeni vektor normalizuje se na opseg 0-1, zatim se vrši odsecanje svih magnituda većih od 0.2 nakon čega se ponovo vrši normalizacija na opseg 0-1. Ove normalizacije vrše se u cilju postizanja invarijantnosti na fotometrijske transformacije.
SLIKA

Question 18

18. Na koji način se RANSAC algoritam koristi za spajanje slika u panoramu (skicirati i opisati postupak)?

Answer 18

Nakon što smo detektovali fičere na slikama koje želimo da spojimo i te fičere opisali odgovarajućim deskriptorom određujemo parove ekvivalentnih fičera na obe slike. Kao rezultat toga dobićemo veliki broj dobrih parova ali i određeni, značajan broj parova koji ne predstavljaju iste elemente. RANSAC algoritam nam pomaže da od detektovanih parova izdvojimo samo one koji na najbolji način opisuju preslikavanje između dveju slika, odnosno one koji zapravo predstavljaju iste elemente na obe slike kako bismo na osnovu njih mogli da odredimo adekvatnu transformaciju između slika. To se postiže tako što se nasumično bira skup od 4 parova, na osnovu njih se određuje homografija. Zatim se posmatraju svi parovi i broje se oni za koje važi da je srednje kvadratno rastojanje između 1. tačke u paru i tačke dobijene primenom homografije na 2. tačku u paru manje od nekog praga. Ukoliko je broj takvih tačaka veći od dosadašnjeg najvećeg broja, skup parova koji su zadovoljili uslov se čuva. Postupak se ponavalja određeni broj puta (fiksno ili adaptivno). Nakon toga se na osnovu validnih parova određuje homografija koja obezbeđuje najmanju srednju kvadratnu grešku pri preslikavanju svih parova iz skupa. Takva homografija primenjuje se na drugu sliku, čime se omogućuje njeno spajanje sa prvom slikom u panoramu.
SLIKA

Question 19

19. Pri redukciji dimenzija korišćenjem PCA, prvo se vrši oduzimanje srednje vrednosti tačaka. Objasniti zašto?

Answer 19

Cilj korišćenja PCA je smanjenje dimenzionalnosti prostora u kojem možemo da prikažemo određeni skup tačaka. Sa ciljem što efikasnijeg modelovanja tog skupa tačaka najpre se oduzima srednja vrednost (koja će da se koristi kasnije pri rekonstrukciji vrednosti), kako bi se modelovala samo odstupanja od standarda, a ne i sam standard. Na taj način se potpomaže ideja pojednostavljenja prikaza skupa vrednosti. Srednja vrednost uzima se kao koordinatni početak u novom, manjedimenzionom prostoru, a položaj tačke u odnosu na taj početak definiše se skupom koordinata koje opisuju pomeraj tačke po pravcima najveće varijanse. Pri čemu je broj koordinata koji se koristi znatno manji od broja dimenzija originalnog prostora u kojem su se nalazile tačke.

Question 20

20. Na koji način je moguće iskoristiti PCA za detekciju lica na slici?

Answer 20

• Pretpostavka je da se većina slika lica nalazi u niskodimenzionom prostoru određenom pomoću prvih k pravaca maksimalne varijanse (pri čemu je k mnogo manje od inicijalne dimenzionalnosti prostora slika lica). Tada PCA može da se iskoristi kako bi se našli eigenfaces u1, …, uk koji opisuju taj podprostor. Onda se sve moguće slike lica iz baze mogu predstaviti kao linearna kombinacija eingeface-ova.
• Postupak korišćenja PCA za prepoznavanje je sledeći:
  o Najpre se obrađuje skup trening slika. Nalazi se srednja vrednost i matrica kovarijanse. Zatim se nalazi k glavnih komponenti (eigenvektora) matrice kovarijanse – u1, …, uk. Skup trening slika se onda projektuje na k-dimenzioni prostor, gde se svaka od slika opisuje težinama kojima se množi odgovarajući eigenvector i razlika originalne slike i izračunate srednje slike.
  o Kada se analizira nova slika, od nje se oduzima srednja slika pa se projektuje na poznati k-dimenzioni prostor eigenvectora, prevođenjem u težine (kao u poslednjem koraku sa trening slikama). Ukoliko nam je cilj da zaključimo da li je na slici uopšte bilo lice ili ne, onda iz k-dimenzionog vektora rekonstruišemo sliku i poredimo rekonstrukciju sa originalnom slikom. Ukoliko je razlika prevelika, znači da na ulazu nije bila slika lica. Ukoliko je cilj odrediti koja je osoba na slici (od poznatih osoba iz trening skupa), onda dobijeni k-dimenzioni vektor poredimo sa vektorima dobijenim prevođenjem trening slika i u sličaju bliskog poklapanja možemo da tvrdimo da je u pitanju ista osoba.

Question 21

21. Objasniti razliku između generativnih i diskriminacionih metoda za klasifikaciju?

Answer 21

Generativni pristup podrazumeva korišćenje trening podataka kako bi se izgradili reprezentativni modeli verovatnoća za svaku klasu ponaosob. Dok diskriminativni pristup, sa druge strane, umesto nezavisnih modela klasa, modeluje granicu odluke između klasa. Prednost generativnog pristupa je to što ima dobru osnovu u teoriji verovatnoće i može dobro da se modeluje Gausovim funkcijama. Omogućava dodavanje novih klasa na postojeći model i dobro radi za veliki broj različitih klasa. Međutim ne radi dobro za visokodimenzionalne podatke, u tom slučaju diskriminacioni metodi imaju prednost jer ne pokušavaju da modeluju same klase već samo granične slučajeve koji su problematični za donošenje odluka. Diskriminacioni metodi stoga predstavljaju bolje rešenje u slučaju kada imamo fiksni broj klasa i kada je bitno samo klasifikovati objekat. Dodatno, diskriminacioni modeli najčešće samostalno određuju fičere po kojima vrše klasifikaciju pa predstavljaju pogodno rešenje u slučajevima kada nismo sigurni koji su fičeri ključni za razlikovanje pripadnika klasa.

Question 22

22. Opisati na koji način se vrši detekcija objekata na slici metodom klizajućeg prozora?

Answer 22

Detekcija objekata na slici metodom klizajućeg prozora vrši se u 2 koraka – obučavanje i eksploatacija. U koraku obučavanja najpre se svaka slika iz trening skupa prevodi u odgovarajući niz fičera koji je opisuje. Zahvaljujući činjici da je trening skup slika anotiran, tj. da se zna kojoj klasi koja slika pripada, vrši se obučavanje klasifikatora koji na osnovu fičera koji se nalaze na slici treba da zaključi pripadnost klasi. U fazi eksploatacije potrebno je da za neku novu ulaznu sliku klasifikator zaključi da li se na njoj nalaze objekti neke klase. Kako bi se obezbedila detekcija objekata svih veličina i tako da mogu da se nađu bilo gde na slici, iz slike se izdvajaju prozori fiksne veličine od gornjeg levog do donjeg desnog ugla sa određenim pomerajem. Nakon što se „obiđe“ cela slika, vrši se smanjivanje slike za određeni faktor i ponavalja se prolazak, postupak se ponavalja sve dok veličina slike ne spadne na veličinu prozora po makar jednoj dimenziji. Svaki tako izdvojen nezavisan prozor prolazi kroz kalsifikaciju zasebno, iz njega se izvlače fičeri i na osnovu njih klasifikator zaključuje da li se u tom prozoru nalazi neki objekat i koja je klasa tog objekta. Ovakav pristup nam omogućuje detekciju i lokalizaciju objekata na slici.

Question 23

23. Na koji način se kaskadni klasifikator koristi za detekciju lica na slici? Koja je njegova glavna prednost?

Answer 23

Za detekciju lica na slici koristi se kaskadni klasifikator tako što se u kaskadu vezuju slabi klasifikatori koji u svakom koraku sa malom greškom obezbeđuju odbacivanje primeraka koji ne sadrže lice. U svakom koraku se donosi odluka da li nešto nije lice, i ukoliko nije, slika se odmah odbacuje, a ukoliko možda jeste, slika mora da prođe kroz sve klasifikatore u kaskadi da bi se potvrdilo prisustvo lica na slici. Upravo to je i glavna prednost kaskadnog klasifikatora jer velika većina prozora koji uđu u kaskadu ne sadrže lice i dobija se znatno na brzini ukoliko se takvi prozori odmah odbace. Za slučaj da prozor sadrži lice, prihvatljivo je utrošiti neko dodatno vreme da bismo to potvrdili. SLIKA

Question 24

24. Šta predstavljaju integralne slike i na koji način se one koriste kod detekcije lica na slici?

Answer 24

Integralne slike predstavljaju slike kod kojih svaki px ima vrednost koja odgovara zbiru vrednosti svih piksela koji se nalaze u prozoru koji je omeđen tim pikselom i gornjim levim pikselom slike. One se koriste u Viola-Jones metodu za detekciju lica na slici. Kod ovog metoda koriste se fičeri i slabi klasifikatori koji predstavljaju pravougaonike sa pravougaonim crnim i belim delovima. Izlaz za ovakve filtere se računa tako što se saberu svi pikseli u belom delu i od njih oduzme zbir piksela u crnom delu. Integralne slike su izuzetno pogodne za ovakva izračunavanja jer se zbir u bilo kom pravougaoniku na slici može dobiti uz samo 3 sabiranja/oduzimanja.

Question 25

25. Na koji način je moguće iskoristiti SVM kad podaci nisu linearno separabilni?

Answer 25

Ukoliko originalni prostor sadrži podatke koji nisu linearno separabilni, možemo da izvršimo mapiranje na višedimenzioni prostor (pri čemu su nove dimenzije izvedene iz postojećih) u kojem podaci jesu linearno separabilni. Funkcija Fi predstavlja mapiranje između orignialnog i novog, višedimenzionalnog prostora. Da ne bismo eksplicitno računali funkciju transformacije prostora, koristi se kernel funkcija kako bi se obezbedila nelinearna granica u originalnom prostoru. Primeri kernel funkcije su: - Linearna - - daje linearnu granicu - Gausova RBF - - daje beskonačno dimenzioni prostor pa se površ koja razdvaja tačke može zakriviti - Presek histograma - - daje opseg od 0 (histogrami koji nemaju presek) do 1 (isti histogrami) SLIKA

Question 26

26. Opisati kako se metod histograma orijentisanih gradijenata (HOG) u kombinaciji sa linearnim SVM-om koristi za detekciju osoba na slici.

Answer 26

Ulazna slika se deli na ćelije i na nivou svake ćelije se na osnovu gradijenata piksela određuje histogram gradijenata po orijentaciji (HOG) tj. za svaki gladijent se određuje u koji od opsega orijentacija spada i njegova amplituda se dodaje na odgovarajuću stavku u histogramu. Slika sada predstavlja matricu histograma. Njenom linearizacijom dobija se vektor amplituda. Nad odgovarajućim trening skupom ovakvih vektora trenira se linearni SVM koji pokušava na što optimalniji način da definiše graničnu liniju koja razdvaja skup vektora koji predstavljaju osobu i onih koji ne predstavljaju osobu.

Question 27

27. Na koji način se metod „vreća vizuelnih reči“ koristi za pretragu slika?

Answer 27

Ako se pitanje odnosi na pretragu sličnih slika onda je odgovor kao za 28. Ako se odnosi na prepoznavanje instanci tj. klasifikaciju slika na osnovu vreće vizuelnih reči onda: Za ulaznu sliku nalaze se svi fičeri koje ona sadrži. Ti fičeri mapiraju se na prostor fičera koji je klasterizovan tako da centar svakog klastera predstavlja vizuelnu reč koja služi da opiše čitav klaster. Proverom pripadnosti fičera klasterima tj. vizuelnim rečima, slika se konvertuje u histogram pojavljivanja vizuelnih reči tj. u vreću vizuelnih reči. Taj histogram zapravo predstavlja fičer vektor koji opisuje sliku pa se problem klasifikacije slike svodi na problem klasifikacije fičer vektora. Tj. mogu da se koriste metode poput SVM ili boosting-a. SLIKA

Question 28

28. Objasniti upotrebu inverznog indeksa na vizuelne reči?

Answer 28

Za svaku sliku koju želimo da sačuvamo/indeksiramo pomoću inverznog indeksa nalazimo fičere koji se na njoj nalaze. Te fičere mapiramo na prostor fičera u kojem određujemo klastere. Centar svakog klastera predstavlja „vizuelnu reč“ i koristi se kao reprezentacija čitavog tog klastera fičera. Nalaženjem kom klasteru tj. kojoj vizuelnoj reči pripadaju svi fičeri neke slike, ta slike biva konvertovana u skup vizuelnih reči. Za svaku vizuelnu reč nađenu u slici dodaje se referenca na tu sliku. Na taj način se gradi struktura u kojoj imamo spisak vizuelnih reči i za svaku od njih reference na sve slike u kojima se ta vizuelna reč javlja. Kada želimo da na osnovu neke nove slike pretražimo ovi inverznu strukturu kako bismo dobili njoj slične slike, iz originalne slike se na isti način nalaze vizuelne reči koje sadrži. Zatim se na osnovu tih vizuelnih reči nalaze sve slike koje ih sadrže, nakon čega se vrši rangiranje nađenih slika po tome po koliko se vizuelnih reči poklapaju. Na taj način dobija se spisak sličnih slika od one sa najvećim poklapanjem.

Question 29

29. Opisati model veštačkog neurona. Kako izgleda ReLU aktivaciona funkcija? Zbog čega je ovaj tip aktivacione funkcije veoma zastupljen u dubokim neuronskim mrežama?

Answer 29

Veštački neuron predstavlja jednostavni procesni element koji obavlja relativno jednostavnu matematičku funkciju (aktivacioni funkciju a). Sadrži ulaze x1, ... xn koji na funkciju utiču težinama wi1, ... win (u kojima se zapravo akvizira znanje), na izlaz još utiče i tetai koji predstavlja prag okidanja (bias). ReLU aktivaciona funkcija predstavlja funkciju f(x) = max(0,x). Ova funkcija je najčešće u upotrebi jer je dosta jednostavna pa se izuzetno brzo izračunava, a u praksi se pokazalo da daje dobre rezultate.

Question 30

30. Šta predstavlja overfitting problem kod obučavanja veštačkih neuronskih mreža i koje tehnike se koriste kako bi se izbegao?

Answer 30

Overfitting predstavlja problem kada se funkcija savršeno uklapa u trening podatke ali ne generalizuje model dobro za nepoznati skup podataka. Ovo se dešava usled korišćenja mreže prevelikog kapaciteta, sa prevelikim brojem neurona. Za izbegavanje overfitting-a, čak i kada se koristi mreža sa isuviše velikim brojem neurona, koriste se tehinike regularizacije. Regularizacija se vodi idejom da treba izbegavati velike težine jer kod njih male promene u ulazu vode velikim promenama u izlazu. Kako bi se to postiglo, povećava se cena koju nose velike težine. Na taj način, pojava velikih težina će znatno uticati na povećanje greške pa će se model truditi da minimizuje takva odstupanja. Metodi regularizacije su glasanje i dropout. - Glasanje – S obzirom na to da treniranje uvek kreće od nasumičnih vrednosti, svaki put dobijamo različiti model. Ideja je utrenirati više različitih modela koji će onda da glasaju za izlaze. - Dropout – Ideja je da u svakom koraku obučavanja odaberemo nasumičan skup neurona koje ćemo isključiti iz mreže. Na taj način obavezujemo neurone narednog sloja da nauče da se oslanjaju na sve neurone podjednako (odnosno da ne favorizuju rezultate nijednog zasebnog neuroa) jer ne znaju koji će neuroni u kom trenutku biti isključeni iz mreže. Ova tehnika koristi se samo u fazi obučavanja i daje slične rezultate kao glasanje ali predstavlja jeftinije rešenje.

Question 31

31. Zbog čega su se duboke konvolucione neuronske mreže pokazale jako efikasnim u rešavanju različitih problema računarskog vida?

Answer 31

Duboke konvolucione neuronske mreže su vrlo efikasne zato što je moguće paralelizovati ih korišćenjem GPU, čime se znatno povećava brzina izračunavanja. Takođe, njihova konfiguracija je vrlo jednostavna, što znatno olakšava testiranje različitih struktura mreža. Ovo je naročito bitno jer je potrebno napraviti mrežu koja prepoznaje na hiljade različitih klasa uzoraka, a veza između strukture mreže i uzoraka koje ona prepoznaje nije uvek očigledna.

Question 32

32. Opisati strukturu tipične konvolucione neuronske mreže.

Answer 32

Konvoluciona neuronska mreža predstavlja višeslojnu veštačku neuronsku mrežu koja se sastoji od jednog ili više konvolucionih slojeva. Svaki konvolucioni sloj ponaša se kao ekstraktor fičera iz ulazne slike – sa slike koju dobija na ulazu izvlači fiksan broj fičera fiksnih dimenzija, pri čemu svaki fičer predstavlja jedan 2D sloj u 3D rezultatu koji konvolucioni sloj generiše. Iza konvolucionih slojeva najčešće se nalaze pooling slojevi koji služe za smanjenje prostorne dimenzije slike, odnosno od slike prave neku vrstu mape. Rezolucija slike se u ovim slojevima smanjuje, najčešće duplo, i na taj način se slika prevodi u skup informacija o sadržaju – znamo šta se nalazi na slici, a nije nam važno gde na slici se to nalazi. Pooling slojevi omogućavaju invarijantnost na pomeranje i distorziju. Mreža koja se sastoji od konvolucionih i pooling slojeva na izlazu generisaće skup fičera sa malom prostornom, a velikom dimenzijom fičera, koji opisuju sadržinu ulazne slike. Kako bi se na osnovu njih donela odluka pripadnosti klasi, na izlazni kraj čitave konvolucione neuronske mreže stavlja se potpuno povezana slojevita neuronska mreža koja vrši klasifikaciju, odnosno povezuje sve izlaze iz poslednjeg konvolucionog/poolig sloja sa izlaznim neuronima koji reprezntuju klase. U tim neuronima najčešće se koristi softmax funkcija koja obezbeđuje da na izlazu iz čitave mreže imamo verovatnoće pripadanja svakoj od klasa.

Question 33

33. Koja je uloga i na koji način se formira izlaz konvolucionog sloja kod konvolucionih neuronskih mreža (ilustrovati na primeru)?

Answer 33

Konvolucioni sloj kod konvolucionih neuronskih mreža predstavlja ekstraktor fičera. Na ulaznoj slici prepoznaje i izvlači fičere koji su značajni i karakteristični. Generiše 3D izlaz, pri čemu svaki od 2D slojeva tog izlaza predstavlja odziv na jedan od fičera. Parametri konvolucionog sloja su dimenzija ulazne slike (imageSize), dimenzija popune koja se dodaje kao okvir na sliku (padding), veličina kernela koji se koristi za ekstrakciju fičera (kernelSize) i pomeraj sa kojim se kernel primenjuje na sliku (stride). Veličina izlaza po prve 2 dimenzije raluna se po sledećoj formuli: Dok je veličina po 3. dimenziji jednaka broju fičera koji se detektuje u tom sloju. Da bi se dobio odziv na jedan fičer slika se najpe uokviruje padding brojem nula sa sve 4 strane (čime se kontroliše da li će ili ne doći do smanjenja veličine izlaza), zatim se obilazi od gorenjeg levog do donjeg desnog ugla. Od piksela koji se trenutno obilazi posmatra se matrica veličine kernelSize x kernelSize i nad njom se vrši funkcija redukcije shodno odgovarajućem fičeru čime se generiše jedna izlazna vrednost. Zatim se vrši pomeranje za stride piksela udesno i ponavlja izračunvanje, sve tako dokle god ima piksela za obilazak tako da oblast koju zahvatamo kernel matricom ne izlazi van granica slike. Zatim se vrši povratak na 0. px po x osi i spuštanje za stride piksela po y osi i ponavalja se postupak dokle je to moguće pod istim uslovima kao za kretanje po x osi. SLIKA

Question 34

34. Koja je uloga i na koji način se formira izlaz pooling sloja kod konvolucionih neuronskih mreža (ilustrovati na primeru)?

Answer 34

Pooling sloj kod konvolucionih neuronskih mreža predstavlja sloj u kojem se vrši redukcija prostornih dimenzija, pri čemu se ne utiče na dimenziju fičera. Na ovaj način slika se prevodi u neku vrstu mape, odnosno izvlače se informacije o njenoj sadržini jer nam je od interesa samo šta se na slici nalazi, a ne i gde se nalazi. Pooling sloj obezbeđuje invarijantnost na pomeranje i distorzije. Parametri pooling sloja su veličina ulazne slike (imageSize), veličina kernel matrice na nivou koje se vrši izračunavanje (kernelSize) i pomeraj sa kojim se kreće po slici po x i y osi (stride). Prve dve dimenzije izlaza mogu da se dobiju po formuli: (imageSize - kernelSize) / stide + 1 Dok treća dimenzija ostaje nepromenjena. Razlikujemo dva različita tipa pooling slojeva – average pool ili max pool. Tip sloja određuje funkciju (average ili max) kojom se vrši redukcija vrednosti iz matrice kernela na rezultujuću vredsnost. Ulazna slika obilazi se od gornjeg levog ka donjem desnom uglu, od početnog piksela posmatra se matrica veličine kernelSize x kernelSize i nad njenim vrednostima primenjuje se odgovarajuća funkcija (average ili max, zavisno od tipa pooling sloja) čime se dobija izlazna vrednost. Zatim se vrši pomeranje za stride piksela po x osi i ponavlja izračunavanje. Taj postupak se ponavlja sve dok je moguće kretati se po x osi tako da kernel matrica ne ispada van opsega slike. Zatim se vrši povratak na 0. px po x osi i spuštanje za stride piksela po y osi. Kretanje se nastavlja i po y osi pod istim uslovima kao za kretanje po x osi.

Question 35

35. Gde se 3D tačka (x,y,z) u prostoru kamere prilikom perspektivne projekcije preslikava u prostor slike (skicirati i napisati izraze za u,v)?

Answer 35

3D tačka, sa koordinatama X, Y, Z, iz prostora kamere (3D prostora čiji se centar, tj. tačka 0,0,0, nalazi u centru kamere) može se mapirati na 2D tačku, sa koordinatama U, V, u prostoru slike (2D prostoru koji odgovara ravni slike i u kojem se centar slike nalazi na koordinatama u0, v0) uz pomoć sledećih formula koje opisuju perspektivnu projekciju. f predstavlja fokalnu dužinu kamere tj. udaljenost centra kamere od ravni slike.

Question 36

36. Grafički ilustrovati i opisati pinhole model kamere? Objasniti koji parametri određuju unutrašnju (eng. intrinsic) i spoljašnju (eng. extrinsic) matricu.

Answer 36

Pinhole model kamere predstavlja model kod kojeg se podrazumeva da kamera sadrži mali otvor, koji se nalazi u optičkom centru kamere i koji je dovoljno mali da kroz njega prolazi samo po jedan i tačno jedan zrak od svake tačke realnog objekta. Ti zraci se sakupljaju na ravni slike, koja se nalazi sa suprotne strane kamere u odnosu na realan objekat, i formiraju 2D obrnutu sliku realnog objekta. Koordinatni sistem iw, jw, kw, sa centrom u Ow predstavlja svetski koordinatni sistem i opisuje 3D prostor u kojem se nalazi realan objekat. Koordinatni sistem i, j, k sa centrom u O predstavlja koordinatni sistem kamere i opisuje 3D prostor kamere, sa centrom u centru kamere. Dok π’ predstavlja ravan na kojoj se formira slika. f’ predstavlja fokalnu dužinu kamere, tj. udaljenost centra kamere od ravni slike. Mapiranje 3D tačke iz realnog sveta u 2D prostor slike po pinhole modelu kamere opisano je sa: Matrica [R t], dimenzija 3x4, predstavlja spoljašnju (extrinsic) matricu kamere i opisuje kako se svetski koordinatni sistem (opšti koordinatni sistem koji ne zavisi od kamere) preslikava na koordinatni sistem kamere. Ova matrica se stalno menja sa pomeranjem kamere. R komponenta predstavlja rotacionu matricu, a t komponenta translacioni vektor. Matrica K, dimenzija 3x3, predstavlja unutrašnju (intrinsic) matricu koja predstavlja matricu projekcije tj. opisuje transformaciju iz 3D prostora kamere u 2D prostor slike. Ova matrica se određuje samo jednom jer ne zavisi od međusobnog položaja kamere i spoljnog sveta. Intrinsic matrica zavisi od fokalne dužine kamere po x (fx) i po y (fy), od položaja centra slike u prostoru slike – u0, v0 su koordinate C’ u prostoru slike, i od s koji predstavlja model iskošenja (ako i i j nisu pod 90 stepeni onda je s različito od 0). Extrinsic matrica zavisi od translacionog vektora t (tx, ty, tz) koji opisuje pomeraj centra svetskog koordinatnog sistema u odnosu na centar kamere po x, y i z osi i od rotacione matrice R (opisane sa r11 do r33) koja opisuje rotaciju po x, y i z osi svetskog koordinatnog sistema u odnosu na koordinatni sistem kamere.

Question 37

37. Zbog čega paralelne linije konvergiraju u jednoj tački (vanishing point) na slici?

Answer 37

Kako bi 3D svet mogao da se prikaže u 2D prostoru slike koristi se projektivna transformacija. Prlikom projekivne transformacije sve linije iz 3D sveta koje nisu paralelne sa ravni slike gube atribut paralelnosti. Usled projektovanja dubine, kako dimenzija Z teži ka beskonačnosti, tako tako dimenzije U i V teže jednoj tački na slici koja predstavlja tačku nestajanja (vanishing point). Sve tačke nestajanja jedne slike nalaze se na istoj pravoj – liniji nestajanja tj. horizontu.

Question 38

38. Jedan način da se odrede parametri modela kamere je da se odrede parovi 3D tačaka u sceni i 2D tačaka na slici. Koliko je minimalno tačaka potrebno da određivanje parametara kamere? Ukoliko imamo veći broj tačaka, na koji način se nalaze parametri kamere?

Answer 38

Kalibraciona matrica kamere ima 11 stepeni slobode. Za njihovo određivanje potrebna je po jedna jednačina, što znači da nam je potrebno 5 i po parova tačaka da bismo ih odredili (tj. 5 parova tačaka i za jednu tačku veza samo po u ili v). Za svaki skup od 5 i po tačaka možemo da odredimo jednu matricu kamere (svih 11 stepeni slobode). Ukoliko imamo više parova njihovim grupisanjem u skupove od 5 i po parova, dobijamo više različitih rešenja za M. Kako bismo odredili najoptimalnije moguće M za broj parova veći od 5 i po, koristi se metod minimizacije srednje kvadratne greške. Odnosno traži se matrica M takva da je suma rastojanja njene primene na 3D tačku od 2D para te tačke minimalna. Takva matrica na najbolji način modeluje dati skup.

Question 39

39. Šta je afina transformacija i koliko parova tačaka je potrebno za njeno određivanje (grafički ilustrovati)?

Answer 39

Afina transformacija je kombinacija translacije, rotacije, skaliranja i smicanja. Ima 6 stepeni slobode pa je za njeno određivanje potrebno imati 3 para tačaka. Pri primeni afine transformacije očuvavaju se paralelne linije i prave linije ostaju prave, dok se površine, dužine i uglovi ne očuvavaju. SLIKA

Question 40

40. Šta je homografija i koliko parova tačaka je potrebno za njeno određivanje (grafički ilustrovati)?

Answer 40

Homografija je kombinacija translacije, rotacije, skaliranja, smicanja i projektivnog krivljenja (što znači da svaki „ćošak“ slike može nezavisno da se „razvuče“). Ima 8 stepeni slobode pa je za njeno određivanje potrebno 4 parova tačaka. Pri primeni hoomgrafije očuvavaju se jedino prave linije dok se površine, dužine, uglovi i paralelne linije ne očuvavaju. SLIKA

Question 41

41. Ukoliko imamo dve kamere i tačku X u prostoru, prikazati položaj epipolarnih linija na ravnima slika.

Answer 41

Osnova je linija OO’ koja povezuje centre kamera stereo sistema. Epipolovi (e i e’) su preseci osnove sa ravnima slika i predstavljaju projekcije centra druge kamere. Epipolarna ravan (OXO’) je ravan koja sadrži tačku X i osnovu. A epipolarne linije (l i l’) se nalaze u preseku epipolarne ravni i ravni slika. SLIKA

Question 42

42. Šta je epipol? Gde se nalaze epipolovi kod kretanja duž ose kamere, a gde kod kretanja upravno na osu kamere (grafički ilustrovati)?

Answer 42

Epipol je tačka preseka osnove (linije koja spaja centre kamera stereo sistema) i ravni slike. Predstavlja projekciju centra druge kamere stereo sistema. Takođe predstavlja tačku preseka svih epipolarnih linija. Pri pomeraju paralelnom sa ravni slike (upravno na osu kamere) epipolovi se nalaze u beskonačnosti. Dok se pri pomeraju duž ose kamere epipol nalazi na samoj slici. SLIKA

Question 43

43. Koja je razlika između esencijalne i fundamentalne matrice?

Answer 43

Esencijalna matrica E je matrica dimenzija 3x3 koja povezuje parove normalizovanih homogenih koordinata u slikama. Sadrži informacije o relativnom položaju i orijentaciji kamera, odnosno relativnu rotaciju i translaciju između kamera, tj. njihove extrinsic parametre. Dok fundimentalna matrica F obezbeđuje vezu između nekalibrisanih kamera (kada intrisnic matrice kamera nisu poznate). Matrica F je takođe dimenzija 3x3 ali je rang matrice 2 (jedna kolona je linearna kombinacija druge dve). Veza između E i F je sledeća: Gde K i K’ predstavljaju intrisnic matrice kamera stereo sistema. FORMULA

Question 44

44. Koji je odnos između dispariteta piksela u kalibrisanom stereo sistemu i daljine odgovarajuće tačke od kamere (grafički ilustrovati)?

Answer 44

Ukoliko pretpostavimo da su kamere koje čine stereo sistem kalibrisane i da su njihove optičke ose paralelne, onda na osnovu položaja tačke na slikama koje generišu kamere možemo da odredimo dubinu te tačke u 3D prostoru tj. njeno rastojanje od kamera. Na osnovu trouglova (OL, P, OR) i (PL, P, PR) možemo da zakjlučimo: SLIKA

Question 45

45. Koje ograničenje se koristi za nalaženje uparenih piksela na stereo slikama (grafički ilustrovati)?

Answer 45

Za nalaženje uparenih piksela na stereo slikama koristi se epipolarno ograničenje koje nalaže da se na osnovu položaja projekcije tačke na jednoj od slika može odrediti linija na drugoj slici na kojoj se sigurno nalazi projekcija te site tačke. Ta linija se zove epipolarna linija. Za slučaj kalibrisanih kamera, ovo ograničenje može da se opiše sa: , gde je E esencijalna matrica i , Tj. 𝑥̂ je zrak koji iz centra kamere prolazi kroz projekciju tačke X na ravni slike (x) i ide ka tački X. Za slučaj nekalibrisanih kamera, ograničenje se opisuje sa: , pri čemu je .

Question 46

46. Lukas-Kanade metod za nalaženje optičkog toka se zasniva na korišćenju gradijenata na statičkoj slici. Sa kojim pretpostavkama je izveden ovaj metod i koje tehnike se primenjuju kako bi se metod primenio na situacije kada ove pretpostavke ne važe?

Answer 46

Pretpostavke sa kojima je izveden Lukas-Kanade algoritam su: - U nekom prozoru oko centralnog piksela se i drugi pikseli kreću na isti način – ograničenje prostorne koherencije - Pomeraj koji piksel napravi između dva frejma je mali (manji od 1px) - Boja piksela (tj. njegov osvetljaj) je konstantna Međutim, ove pretpostavke nisu uvek tačne. Npr. konstantni osvetljaj nije uvek zadovoljen. Ovaj problem može da se prevaziđe praćenjem fičera koji su invarijantni na promene u osvetljenju, poput SIFT-a. Takođe, pomeraj između dva frejma za neke objekte je često veći od 1px. Ovo vodi problemu alijasinga – ukoliko je pomeraj preveliki, pogrešno će se naći najbliži sličan sused piksela i dobićemo privid kretanja koje zapravo ne postoji. Kako bi se ovo prevazišlo koristi se tehnika grube ka finoj proceni. Ova tehnika bazira se na ideji da pomeraj može da se svede na subpiksel vrednost ukoliko se smanji rezolucija. Zato se kreira Gausova piramida slika koja se generiše tako što se ista slika zamuti Gausovim filterom pa zatim smanji duplo i proces se ponavlja dok se ne dođe do neke minimalne veličine. Zatim se kreće obrada od najmanje slike i na njoj se odrede pomeraji. Zatim se ti pomeraji dupliraju i primene na veću sliku i tako u njoj otklone veći pomeraji pa se zatim u toj slici nalaze pomeraji koji su za nju <1px i oni dodaju na već izračunate. Proces se nastavlja do najveće slike (originalna rezolucija). SLIKA

Question 47

47. Objasniti problem aperture kod određivanja pravca kretanja. Ilustrovati primerima.

Answer 47

Problem aperture uzrokovan je time što nekada ne vidimo čitav objekat i njegovo kretanje već samo jedan njegov deo što rezultuje time da možemo da dođemo do pogrešnih pretpostavki o tome kako se objekat zapravo kreće. SLIKA

Question 48

48. Koja je veza između Lukas-Kanade metoda za određivanje optičkog toka i Harisovog detektora uglova?

Answer 48

Prilikom izvođenja formule za određivanje pomeraja piksela između trenutaka t i t+1 kod Lukas-Kanade metoda za određivanje optičkog toka, dolazi se do zaključka da matrica ATA (koja sadrži sume proizvoda izvoda slike za određeni prozor piksela po x i po y) treba da bude invertujuća. Da bi taj uslov bio zadovoljen moraju da budu ispunjeni isti uslovi za sopstvene vrednosti 1 i 2 matrce ATA, kao uslovi koji se koriste da bi se odabrao dobar fičer za praćenje kod Harisovog detektora uglova. Odnosno 1 i 2 treba da budu veće od nekog predefinisanog praga i treba da budu međusobno uporedive tj. da ne važi da je jedna vrednost znatno veća od druge.

Question 49

49. Objasniti princip rada dubinske kamere kod Kinect-a?

Answer 49

Kinect obezbeđuje informacije o dubini svakog piksela tako što pored kamere poseduje i projektor koji projektuje neki pseudo-slučjani patern u infra-crvenom spektru na prostor koji snima kamera. Kamera snima klasičnu RGB sliku, ali ima i IC senzor koji pokuplja i projektovane informacije. Na osnovu obrasca rasipanja projekovanih infra-crvenih zraka na objekte koji se snimaju kamerom, moguće je određivanje dubine na kojoj se nalazi svaki piksel tj. krairanje RGBD (dubinske) slike koja za svaki piksel sadrži informaciju o boji i udaljenosti od kamere.

Question 50

50. Objasniti metod srednjeg pomeraja (eng. Mean Shift). Na koji način se on koristi za segmentaciju delova tela kod Kinect-a?

Answer 50

Mean shift algoritam predstavlja algoritam za segmentaciju na osnovu boja, odnosno algoritam koji na osnovu skupa već klasifikovanih tačaka nalazi centre klastera za svaku klasu. Za svaku tačku iz skupa, centar prozora se najpre postavi na tu tačku (veličina prozora se definiše pre početka algoritma i predstavlja njegov bitan parametar). Za prozor se određuje centar mase tj. srednja vrednost tačaka koje upadaju u prozor, pa se prozor pomera tako da se centar mase poklopi sa centrom položaja. Zatim se ponovo računa centar mase i postupak se ponavlja sve dok se ne dođe u situaciju da se novi centar mase poklapa sa centrom položaja. Tada se smatra da je centar klastera nađen. Za sve tačke koje vode istom centru klastera smatra se da pripadaju istom klasteru. Kod Kinecta, ovaj algoritam se koristi da na osnovu već klasifikovanih piksela odredi položaj zglobova. Dakle, na osnovu dubinske slike vrši se klasifikacija piksela na osnovu pripadnosti delovima tela. Tako klasifikovani pikseli ulaze u Mean shift algoritam kako bi se za svaki zglob (deo tela) odredila njegova tačna lokacija (koja će zapravo biti centar klastera te klase).