Another Links in Social Networks using Face Recognition

VSˇB – Technicka´ univerzita Ostrava Fakulta elektrotechniky a informatiky Katedra informatiky

Dalsˇ´ı linky v socia´lnı´ch sı´tı´ch s rozpozna´va´nı´m oblicˇeju˚ Another Links in Social Networks using Face Recognition

2013

Jakub Stonawski

Prohlasˇuji, zˇe jsem tuto diplomovou pra´ci vypracoval samostatneˇ. Uvedl jsem vsˇechny litera´rnı´ prameny a publikace, ze ktery´ch jsem cˇerpal.

V Ostraveˇ 19. cˇervence 2013

.............................

Na tomto mı´steˇ bych prˇedevsˇ´ım ra´d podeˇkoval sve´mu vedoucı´mu diplomove´ pra´ce panu doc. RNDr. Petru Sˇalounovi, Ph.D. za jeho cenne´ rady a cˇas prˇi tvorbeˇ te´to pra´ce a take´ vsˇem blı´zky´m za podporu.

Abstrakt Cı´lem te´to diplomove´ pra´ce je vytvorˇit a popsat algoritmus, ktery´ by, pokud mozˇno bez veˇtsˇ´ıch interakcı´ s uzˇivatelem, nabı´zel nova´ spojenı´ v ra´mci urcˇite´ socia´lnı´ sı´teˇ. V dnesˇnı´ dobeˇ samy socia´lnı´ sı´teˇ poskytujı´ mnoho druhu˚ takovy´chto algoritmu˚, ktere´ ve velke´ veˇtsˇineˇ vyuzˇ´ıvajı´ analy´zu textovy´ch informacı´ o uzˇivateli a s vyuzˇitı´m teˇchto dat posle´ze uzˇivatele kategorizujı´ do skupin, ve ktery´ch je velka´ pravdeˇpodobnost, zˇe se jednotlivci budou zna´t. Cı´lem je k na´vrhu˚m novy´ch spojenı´ vyuzˇ´ıt identifikaci uzˇivatelu˚ s pomocı´ algoritmu˚ rozpozna´va´nı´ oblicˇeju˚. Druhotny´m vy´stupem tohoto rˇesˇenı´ je take´ zpeˇtne´ zverˇejnˇova´nı´ nalezeny´ch informacı´ o osoba´ch zachyceny´ch na fotografiı´ch. Tyto informace jsou poskytova´ny ve formeˇ popisku˚ jmen osob u analyzovany´ch obra´zku˚. V za´veˇrecˇne´ fa´zi te´to pra´ce je nalezene´ rˇesˇenı´ na´vrhu novy´ch spojenı´ podrobeno se´rii testu˚, ktere´ majı´ za u´kol proka´zat, jestli je tento druh vyhleda´va´nı´ novy´ch spojenı´ dostatecˇneˇ robustnı´ a lze jej v praxi pouzˇ´ıt. Klı´cˇova´ slova: Rozpozna´va´nı´ oblicˇeju˚, Socia´lnı´ sı´teˇ, Betaface, Facebook, Flickr, Nalezenı´ novy´ch kontaktu˚

Abstract Main goal of this diploma thesis is to create and describe an algorithm that will offer new connections inside the specific social network. The algorithm should work without an extensive interaction with a user. In the current situation there are number of the algorithms that offer new connections but most of them use only text information for the analysis. Then they categorize users to the specific groups where is a high possibility that users know each other. The goal of this thesis is to use identification of a user with help of a face recognition when new suggestions of contacts are created. Secondary result of the solution is back-propagation of information about people who were found in the photos. This information is published in text form in a tag of the specific photo. In the final phase of this thesis the algorithm is tested what has to prove if the solution is robust enough for a practical usage. Keywords: Face recognition, Social networks, Betaface, Facebook, Flickr, Find new contacts

Seznam pouzˇity´ch zkratek a symbolu˚ API DAU FOAF HTTPS JSON SDK SSL URL WISARD XML

– – – – – – – – – –

Application Programming Interface Daily Active Users Friend of a Friend Hypertext Transfer Protocol Secure JavaScript Object Notation Software Development Kit Secure Sockets Layer Uniform Resource Locator Wilkie Aleksandr and Stonham‘s Recognition Device Extensible Markup Language

1

Obsah 1

´ vod U

2

Na´vrhy novy´ch spojenı´ - stav pozna´nı´

11

3

Vyuzˇitı´ detekce a rozpozna´nı´ oblicˇeju˚ v socia´lnı´ch sı´tı´ch 3.1 Existujı´cı´ studie vyuzˇ´ıvajı´cı´ rozpozna´nı´ oblicˇeju˚ . . . . . . . . . . . . . . . 3.2 Vlastnı´ prˇ´ıstup k vyuzˇitı´ rozpozna´va´nı´ oblicˇeju˚ . . . . . . . . . . . . . . . .

17 17 18

4

Legislativnı´ stra´nka rozpozna´va´nı´ 4.1 Facebook a jeho sluzˇba Tag Suggestions . . . . . . . . . . . . . . . . . . . . 4.2 Google s aplikacı´ Google Googles . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Doporucˇenı´ pro korektnı´ vyuzˇitı´ rozpozna´va´nı´ tva´rˇ´ı . . . . . . . . . . . . .

21 21 22 23

5

Algoritmy rozpozna´va´nı´ oblicˇeju˚ 5.1 Princip analy´zy tva´rˇ´ı . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Techniky rozpozna´va´nı´ oblicˇeju˚ . . . . . . . . . . . . . . . . . . . . 5.3 Volneˇ dostupne´ sluzˇby vyuzˇitelne´ k u´cˇelu rozpozna´va´nı´ oblicˇeju˚ 5.4 Mozˇnost kombinace sluzˇeb a prˇ´ıpadna´ efektivita tohoto rˇesˇenı´ . .

. . . .

. . . .

. . . .

. . . .

. . . .

25 25 25 27 31

Zdroje dat pro analy´zu a na´vrhy novy´ch spojenı´ v socia´lnı´ch sı´tı´ch 6.1 Socia´lnı´ sı´teˇ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Vy´voj pocˇtu uzˇivatelu˚ socia´lnı´ch sı´tı´ . . . . . . . . . . . . . . . . 6.3 Vy´beˇr konkre´tnı´ socia´lnı´ sı´teˇ . . . . . . . . . . . . . . . . . . . . . 6.4 Vy´beˇr vhodne´ho zdroje fotografiı´ pro analy´zu . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

35 35 36 37 38

6

7

9

. . . .

Vlastnı´ na´vrh prototypu algoritmu 7.1 Princip vyhleda´va´nı´ novy´ch spojenı´ . . . . . . . . . . . . . . . . . . . . . . 7.2 Komunikace s externı´mi sluzˇbami . . . . . . . . . . . . . . . . . . . . . . . 7.3 Analy´za sta´vajı´cı´ch spojenı´ v socia´lnı´ sı´ti . . . . . . . . . . . . . . . . . . . 7.4 Vytva´rˇenı´ novy´ch na´vrhu˚ spojenı´ v za´vislosti na analyzovany´ch externı´ch datech . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41 41 43 49

8

Analy´za vy´sledku˚ u´speˇsˇnosti experimenta´lnı´ho algoritmu 8.1 Vyhodnocenı´ spolehlivosti sluzˇby pro analy´zu oblicˇeju˚ Betaface . . . . . . ´ speˇsˇnost nove´ho algoritmu jako celku . . . . . . . . . . . . . . . . . . . . 8.2 U

53 53 55

9

Za´veˇr

57

10 Reference

59

Prˇı´lohy

60

A Obsah CD prˇı´lohy a cˇla´nek SMAP 2013

61

50

2

3

Seznam tabulek 1 2 3 4 5 6

Velikost prˇeneseny´ch dat v jednotlivy´ch fa´zı´ch komunikace . . . Porovna´nı´ prˇeneseny´ch dat v prˇ´ıpadeˇ vyuzˇitı´ jedne´ a dvou sluzˇeb Nejveˇtsˇ´ı socia´lnı´ sı´teˇ podle statistiky z roku 2006 . . . . . . . . . . Prˇ´ıklady URL adres pro vybrane´ pozˇadavky na servery Facebook Vy´sledky testova´nı´ algoritmu˚ sluzˇby Betaface . . . . . . . . . . . Vy´sledky u´speˇsˇnosti cele´ho experimenta´lnı´ho algoritmu . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

33 33 36 46 54 55

4

5

Seznam obra´zku˚ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Prˇ´ıklady sta´vajı´cı´ch metod na´vrhu novy´ch prˇa´tel . . . . . . . . . . . . . . . Prˇ´ıklad na´vrhu novy´ch spojenı´ v socia´lnı´ sı´ti Facebook . . . . . . . . . . . Na´vrh novy´ch spojenı´ zalozˇeny´ na aktivita´ch uzˇivatele . . . . . . . . . . . Na´vrh novy´ch spojenı´ za´visly´ na externı´ch obra´zcı´ch . . . . . . . . . . . . Algoritmus rozpozna´va´nı´ tva´rˇ´ı Google (s cˇ´ısly patentu˚) [20] . . . . . . . . Prima´rnı´ objekty ve tva´rˇi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zmeˇna tva´rˇe v za´vislosti na emocı´ch cˇloveˇka . . . . . . . . . . . . . . . . . Stanovenı´ unika´tnı´ch bodu˚ ve tva´rˇi sluzˇbou Luxand . . . . . . . . . . . . . Prostrˇedı´ Silverlight aplikace Betaface . . . . . . . . . . . . . . . . . . . . . Modelove´ skupiny tva´rˇ´ı vytvorˇene´ samoucˇ´ıcı´m algoritmem . . . . . . . . Prˇenos dat v komunikaci se sluzˇbou Betaface . . . . . . . . . . . . . . . . . Prˇenos dat v komunikaci s jednodusˇsˇ´ı sluzˇbou WaldBoost . . . . . . . . . Rozlozˇenı´ novy´ch uzˇivatelu˚ socia´lnı´ch sı´tı´ . . . . . . . . . . . . . . . . . . . Modifikovany´ zpu˚sob oznacˇova´nı´ prˇa´tel na sı´ti Flickr . . . . . . . . . . . . Standardnı´ fotografie pro zkouma´nı´ mozˇny´ch novy´ch spojenı´ uzˇivatele . Zna´zorneˇnı´ mnozˇiny vsˇech uzˇivatelu˚ Facebook a redukovane´ mnozˇiny pro nalezenı´ nove´ho kontaktu . . . . . . . . . . . . . . . . . . . . . . . . . . . . Struktura vlastnı´ trˇ´ıdy BetafaceImage . . . . . . . . . . . . . . . . . . . . . Na´stin algoritmu analyzujı´cı´ sta´vajı´cı´ prˇa´tele na socia´lnı´ sı´ti . . . . . . . . Registrace nove´ aplikace na sı´ti Flickr . . . . . . . . . . . . . . . . . . . . . Trˇ´ıda FlickrUser reprezentujı´cı´ konkre´tnı´ho uzˇivatele sluzˇby Flickr . . . . . Odsouhlasenı´ prˇ´ıstupu aplikace k datu˚m uzˇivatele . . . . . . . . . . . . . . Algoritmus pro zpracova´nı´ sta´vajı´cı´ch prˇa´tel na socia´lnı´ sı´ti . . . . . . . . Vlastnı´ trˇ´ıdy pro manipulaci s informacemi o prˇa´telı´ch . . . . . . . . . . . Algoritmus vyhodnocova´nı´ informacı´ z externı´ch obrazovy´ch dat . . . . . Testovacı´ data poskytnuta´ Carnegie Mellon University . . . . . . . . . . .

12 14 18 19 24 26 27 28 29 32 32 32 36 39 42 42 43 45 46 47 48 49 50 51 56

6

7

Seznam vy´pisu˚ zdrojove´ho ko´du 1 2 3 4 5 6 7 8

Forma´t pozˇadavku POST (obrazova´ data ko´dova´na do forma´tu base64Binary) Pozˇadavek na informace o rozpoznane´ tva´rˇi ve fotografii . . . . . . . . . . Forma´t odpoveˇdi serveru s detailnı´mi informacemi o obraze . . . . . . . . Prˇevedenı´ obrazovy´ch dat do textove´ho rˇeteˇzce ve forma´tu base64Binary Informace poslane´ ze serveru jako odpoveˇd’ na dotaz o podrobnostech uzˇivatele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Zpu˚sob rˇesˇenı´ prˇihlasˇova´nı´ uzˇivatele k sı´ti Flickr . . . . . . . . . . . . . . . Princip vyrˇesˇenı´ proble´mu s chybneˇ forma´tovany´mi tagy fotografiı´ . . . . Cˇa´st vy´sledku˚ vyhleda´va´nı´ osoby se jme´nem Karel Novak . . . . . . . . .

30 30 31 44 45 47 48 52

8

9

1

´ vod U

V poslednı´ch letech se socia´lnı´ sı´teˇ obecneˇ staly fenome´nem internetu. Logicky to vyplynulo z postupne´ho prˇechodu internetu z me´dia, pouze zprostrˇedkova´vajı´cı´ informace, ktere´ uzˇivatele´ pasivneˇ zpracova´vali, na mysˇlenkovou platformu, oznacˇovanou jako Web 2.0 [18]. Uzˇivatele´ internetu dnes obsah nejen aktivneˇ tvorˇ´ı, ale chteˇjı´ se i prˇirozeneˇ shromazˇd’ovat do skupin, kde jsou schopnı´ sdı´let konkre´tnı´ a naprˇ´ıklad i velice u´zce zameˇrˇeny´ obsah. Obrovsky´ za´jem o socia´lnı´ sı´teˇ dokla´dajı´ i pocˇty aktivnı´ch uzˇivatelu˚. Naprˇ´ıklad v prˇ´ıpadeˇ jedne´ z nejvyuzˇ´ıvaneˇjsˇ´ıch socia´lnı´ch sı´tı´ celosveˇtoveˇ - Facebook, hovorˇ´ıme jizˇ o vı´ce nezˇ miliardeˇ aktivnı´ch u´cˇtu˚ uzˇivatelu˚ [19]. V prˇ´ıpadeˇ socia´lnı´ sı´teˇ Twitter je registrova´no 500 milionu˚ uzˇivatelu˚ a Google+ ma´ nynı´ kolem 343 milionu˚ uzˇivatelu˚ [21]. Tento fakt la´ka´ nejen me´dia, ktera´ zacˇala vnı´mat socia´lnı´ sı´teˇ jako jedny z jejich informacˇnı´ch kana´lu˚, ale i veˇdce, ktery´m se otevı´ra´ nova´ mozˇnost, jak prova´deˇt sve´ vy´zkumy. K tomu, aby byla socia´lnı´ sı´t’u´speˇsˇna´ ovsˇem potrˇebuje velky´ pocˇet uzˇivatelu˚, kterˇ´ı obsah aktivneˇ vytva´rˇejı´ a pozitivneˇ tak motivujı´ i dalsˇ´ı uzˇivatele, aby se na webove´ stra´nky opeˇtovneˇ vraceli. Socia´lnı´ sı´teˇ dnes vyuzˇ´ıvajı´ zejme´na sva´ internı´ data o chova´nı´ jednotlivy´ch uzˇivatelu˚ a na za´kladeˇ jejich vyhodnocova´nı´ nabı´zejı´ uzˇivatelu˚m nova´ spojenı´. Podrobny´ popis aktua´lneˇ vyuzˇ´ıvany´ch metod je uveden v Kapitole 2. Veˇtsˇina teˇchto na´vrhu˚ ovsˇem nenı´ dostatecˇneˇ u´speˇsˇny´ch a mnoho uzˇivatelu˚ cˇaste´ sˇpatne´ na´vrhy obteˇzˇujı´. Je tedy vhodne´ navrhnout algoritmy pro na´vrhy novy´ch spojenı´ le´pe. Pra´veˇ takovy´to sofistikovaneˇjsˇ´ı postup by meˇl aplikovat prototyp algoritmu te´to diplomove´ pra´ce. Algoritmus vyuzˇ´ıva´ analy´zy a rozpozna´va´nı´ oblicˇeju˚ jako verifikacˇnı´ metody k tomu, abychom mohli co nejjednoznacˇneˇji identifikovat jednotlive´ uzˇivatele socia´lnı´ch sı´tı´. Jeho za´kladnı´ funkce spocˇ´ıva´ v tom, zˇe nejprve libovolne´mu uzˇivateli socia´lnı´ sı´teˇ zanalyzuje vsˇechny jeho nyneˇjsˇ´ı kontakty a pokusı´ se identifikovat jejich tva´rˇe. Po te´to fa´zi ma´ za´kladnı´ databa´zi oblicˇeju˚ a jmen uzˇivatelovy´ch sta´vajı´cı´ch kontaktu˚. V dalsˇ´ım kroku je nutne´ sesbı´rat z jine´ho zdroje fotografie uzˇivatele, na ktery´ch jsou detekova´ny dalsˇ´ı osoby. Poslednı´m krokem algoritmu by meˇlo by´t rozhodnutı´, jestli jsou nove´ osoby takte´zˇ uzˇivateli socia´lnı´ sı´teˇ, a paklizˇe jsou, jejich navrhnutı´ za dalsˇ´ı nove´ prˇa´tele nasˇeho ´ speˇsˇnost cele´ho postupu pak vy´raznou meˇrou spocˇ´ıva´ v samotne´ u´speˇsˇnosti uzˇivatele. U algoritmu rozpozna´va´nı´ oblicˇeju˚. Jelikozˇ tato pra´ce ma´ za cı´l vyuzˇ´ıt algoritmy, ktere´ jsou volneˇ dostupne´, je vhodne´ se v prˇ´ıpadny´ch na´vazny´ch pracı´ch zameˇrˇit na vylepsˇenı´ te´to cˇa´sti algoritmu. Samostatnou kategoriı´, kterou je nutno v prˇ´ıpadeˇ nasazenı´ algoritmu do rea´lne´ho provozu vyrˇesˇit, je ota´zka legislativnı´ch proble´mu˚. Jelikozˇ dnes na u´zemı´ EU sta´le jesˇteˇ nenı´ jednotny´ pra´vnı´ postup, jak ochranˇovat biometricke´ u´daje, je obtı´zˇne´ prˇipravit aplikace a jejich podmı´nky vyuzˇ´ıva´nı´ korektneˇ. Ve sta´vajı´cı´ aplikaci te´to pra´ce je proble´mova´ zejme´na fa´ze, kdy z dalsˇ´ıho zdroje (mimo za´kladnı´ socia´lnı´ sı´t’) program analyzuje fotografie a vyhleda´va´ jake´koliv dalsˇ´ı osoby. Tva´rˇe teˇchto osob pote´ procha´zejı´ analy´zou, ovsˇem bez jejich souhlasu. Tento souhlas prakticky totizˇ nenı´ mozˇno v rozumne´m cˇase obstarat. Pro u´cˇely nekomercˇnı´ho akademicke´ho vy´zkumu toto ale mu˚zˇeme prozatı´m zanedbat.

10

11

2

Na´vrhy novy´ch spojenı´ - stav pozna´nı´

V soucˇasnosti jizˇ samozrˇejmeˇ veˇtsˇina socia´lnı´ch sı´tı´ na´vrhy na dalsˇ´ı spojenı´ s jiny´mi uzˇivateli nabı´zı´. Zpu˚soby jaky´m toto vyhleda´va´nı´ prˇa´tel realizujı´ jsou naprˇ´ıcˇ sı´teˇmi vesmeˇs podobne´ (samozrˇejmeˇ v ra´mci konkurencˇnı´ho boje se objevujı´ i origina´lnı´ prˇ´ıstupy, ktere´ vyuzˇ´ıva´ pouze konkre´tnı´ sı´t’). Potrˇeba co mozˇna´ neju´speˇsˇneˇjsˇ´ıch algoritmu˚ vyhleda´va´nı´ novy´ch spojenı´ je obrovska´ pro obeˇ strany, jak pro uzˇivatele, tak i pro samotnou socia´lnı´ sı´t’. Cı´lem diplomove´ pra´ce je prˇedevsˇ´ım pomoci nove´mu uzˇivateli socia´lnı´ sı´teˇ, ktery´ prozatı´m nema´ mnoho kontaktu˚ uvnitrˇ te´to sı´teˇ, a sta´vajı´cı´ na´vrhy novy´ch spojenı´ pro neˇj nejsou adekva´tnı´. Pouzˇitelnost socia´lnı´ sı´teˇ se pro takove´ho uzˇivatele znacˇneˇ omezuje a pokud by tato situace trvala delsˇ´ı dobu, muzˇe to ve´st i k opusˇteˇnı´ socia´lnı´ sı´teˇ. Pokud se na stejnou situaci podı´va´me z pohledu socia´lnı´ sı´teˇ, uzˇivatel, ktery´ nema´ adekva´tnı´ pocˇet prˇa´tel, netra´vı´ na sı´ti mnoho cˇasu. Me´neˇ stra´vene´ho cˇasu na sı´ti znamena´ mensˇ´ı mnozˇstvı´ reklam, ktere´ jsou na uzˇivatele cı´leny a tedy i mensˇ´ı pravdeˇpodobnost u´speˇsˇnosti neˇktere´ z reklam, cozˇ pro socia´lnı´ sı´t’ znamena´ mensˇ´ı prˇ´ıjmy z te´to cˇinnosti. Druhotny´m na´sledkem takove´to situace je samozrˇejmeˇ i mensˇ´ı vyuzˇ´ıva´nı´ doplnˇkovy´ch sluzˇeb samotne´ socia´lnı´ sı´teˇ a jejich prˇ´ıpadna´ propagace mezi uzˇivateli. Z vy´sˇe naznacˇene´ho je mozˇne´ ocˇeka´vat postupne´ zdokonalova´nı´ sta´vajı´cı´ch algoritmu˚ pro na´vrhy novy´ch spojenı´ ze stran samotny´ch socia´lnı´ch sı´tı´. Pokud se tak stane, u´speˇsˇnost teˇchto internı´ch algoritmu˚ bude pravdeˇpodobneˇ vzˇdy veˇtsˇ´ı nezˇ u´speˇsˇnost algoritmu˚ vyvı´jeny´ch trˇetı´mi stranami, jelikozˇ tyto nebudou nikdy disponovat internı´mi daty uzˇivatelu˚ sesbı´rany´mi beˇhem jejich aktivit uvnitrˇ sı´teˇ. Prozatı´m se vsˇak sofistikovaneˇjsˇ´ı algoritmy sta´le na veˇtsˇineˇ nejpouzˇ´ıvaneˇjsˇ´ıch socia´lnı´ch sı´tı´ nevyskytujı´, cozˇ je du˚vod, procˇ ma´ smysl se touto problematikou sta´le zaby´vat. V na´sledujı´cı´m seznamu a Obra´zku 2 jsou pro ilustraci uvedeny neˇktere´ z dnes beˇzˇneˇ vyuzˇ´ıvany´ch zpu˚sobu˚ nalezenı´ pravdeˇpodobny´ch novy´ch spojenı´ v ra´mci socia´lnı´ch sı´tı´. Jedna´ se zejme´na o techniky, ktere´ jsou aktivneˇ vyuzˇ´ıva´ny nejveˇtsˇ´ımi socia´lnı´mi sı´teˇmi, v prˇ´ıpadeˇ minoritnı´ch sı´tı´ mohou by´t aplikova´ny i jine´, prˇ´ıpadneˇ i sofistikovaneˇjsˇ´ı metody, ktere´ ovsˇem nenı´ mozˇne´ na veˇtsˇ´ıch sı´tı´ch aplikovat. Proto jsou metody vyuzˇitelne´ pouze u maly´ch sı´tı´ ze seznamu vynecha´ny.

12

Obra´zek 1: Prˇ´ıklady sta´vajı´cı´ch metod na´vrhu novy´ch prˇa´tel 1. Vyhleda´va´nı´ prˇa´tel pomocı´ spolecˇny´ch zna´my´ch • jedna z nejjednodusˇsˇ´ıch forem zalozˇena´ na prˇedpokladu, zˇe pokud veˇtsˇ´ı pocˇet vasˇich soucˇasny´ch prˇa´tel zna´ urcˇite´ho cˇloveˇka, budete jej pravdeˇpodobneˇ zna´t take´. 2. Vyhleda´va´nı´ pomocı´ spolecˇny´ch za´jmu˚, aktivit a obdobny´ch veˇcı´ • pokud se aktivneˇ seskupujete do urcˇity´ch skupin v ra´mci socia´lnı´ch sı´tı´, pravdeˇpodobneˇ zde budete mı´t i zna´me´, kterˇ´ı se mohou sta´t vasˇimi prˇa´teli; • tento prˇ´ıstup se vsˇak pro lepsˇ´ı u´cˇinnost kombinuje s dalsˇ´ımi metodami (nejcˇasteˇji s bodem 1., naprˇ. pokud jste ve skupineˇ prˇ´ıznivcu˚ fotografie, pravdeˇpodobneˇ va´s ve skupineˇ bude velke´ mnozˇstvı´ a je nutne´ uplatnit dodatecˇny´ filtr (kuprˇ´ıkladu filtr teˇch osob, ktere´ ma´ neˇktery´ z my´ch prˇa´tel ve svy´ch prˇa´telı´ch). 3. Vyhleda´va´nı´ pomocı´ zameˇstna´nı´, oboru˚ • v prˇ´ıpadeˇ zameˇstna´nı´ filtrace dle obdobı´ u´vazku, aby byly zajisˇteˇny relevantneˇjsˇ´ı vy´sledky. 4. Import kontaktu˚ z jiny´ch aplikacı´ • velice ozˇehave´ te´ma na jedne´ z nejveˇtsˇ´ıch socia´lnı´ch sı´tı´ Facebook; • uzˇivateli je nabı´dnuto, at’importuje kontakty kuprˇ´ıkladu ze sve´ho e-mailove´ho u´cˇtu (musı´ poskytnout prˇihlasˇovacı´ u´daje do e-mail klienta); • socia´lnı´ sı´t’se potom pokousˇ´ı nale´zt importovane´ e-mailove´ adresy u jizˇ zaregistrovany´ch uzˇivatelu˚, pokud nalezne, nabı´dne nove´ho prˇ´ıtele; • konkre´tneˇ Facebook si ale importovane´ kontakty ponecha´va´ ve sve´ databa´zi a da´le je vyuzˇ´ıva´, takzˇe mu˚zˇe nastat na´sledujı´cı´ situace:

13

– uzˇivatel A je ve spojenı´ s uzˇivatelem B. Uzˇivatel A povolil vyuzˇ´ıvat sı´ti Facebook svu˚j contact list CLA ; – je pravdeˇpodobne´, zˇe uzˇivateli B bude nabı´dnut neˇktery´ z kontaktu˚ z CLA . V praxi se ovsˇem sta´va´, zˇe jsou takto nabı´zeny na´vrhy na prˇa´telstvı´ s by´valy´mi partnery/kami a obdobne´ neprˇ´ıjemne´ situace. 5. Vyhleda´va´nı´ prˇa´tel s vyuzˇitı´m externı´ch informacı´ • lze vyuzˇ´ıvat shroma´zˇdeˇny´ch dat z bodu 4. • uzˇivatel A nahraje contact list CLA . Uzˇivatel B obdobneˇ nahraje CLB . Uzˇivatele´ A a B zatı´m nejsou ve spojenı´. Existuje mnozˇina M dalsˇ´ıch uzˇivatelu˚, kterˇ´ı nahra´li sve´ contact listy; • socia´lnı´ sı´t’ nejprve vytipuje uzˇivatele z mnozˇiny M , kterˇ´ı by mohli mı´t neˇco spolecˇne´ho (dle bydlisˇteˇ, zameˇstna´nı´,...) a zanalyzuje jejich contact listy – pro na´zornost budou vybra´ni pra´veˇ uzˇivatele´ A a B; • pokud pocˇet spolecˇny´ch kontaktu˚ v CLA a CLB prˇesa´hne urcˇitou hranici (v praxi procentua´lnı´ v za´vislosti na celkove´m pocˇtu osob), navrhne sı´t’spojenı´ mezi uzˇivateli A a B; • ve skrze se jedna´ o obdobny´ prˇ´ıpad jako ten v bodu 1., ovsˇem s tou vy´hodou, zˇe osoby uvedene´ v contact listech vu˚bec nemusı´ by´t uzˇivateli socia´lnı´ sı´teˇ. 6. Nabı´dka novy´ch prˇa´tel s pomocı´ manua´lnı´ interakce uzˇivatelu˚ • prˇi zalozˇenı´ nove´ho u´cˇtu se uzˇivatel nejcˇasteˇji spojı´ pouze s omezenou skupinkou nejblizˇsˇ´ıch a vy´sˇe uvedene´ automaticke´ algoritmy nemusı´ dobrˇe fungovat; • pokud ma´ uzˇivatel delsˇ´ı dobu pouze omezeny´ pocˇet prˇa´tel, mu˚zˇe socia´lnı´ sı´t’ tyto prˇa´tele oslovit, aby uzˇivateli sami manua´lneˇ navrhli prˇa´tele; • tato funkce je na socia´lnı´ch sı´tı´ch jako jaka´si za´brana proti tomu, aby novy´ uzˇivatele´ opustili sı´t’ pouze z du˚vodu toho, zˇe majı´ ma´lo spojenı´ (tudı´zˇ na ni tra´vı´ me´neˇ cˇasu, ma´ pro neˇ mensˇ´ı informacˇnı´ charakter a podobneˇ). 7. Dalsˇ´ı vyhleda´va´nı´ prˇa´tel zalozˇene´ na podrobneˇjsˇ´ıch analy´za´ch chova´nı´ uzˇivatelu˚ • tento postup je pouze spekulativnı´, jelikozˇ zˇa´dna´ socia´lnı´ sı´t’nevyzradı´ uzˇivatelu˚m prˇesne´ algoritmy funkcı´ sve´ sluzˇby; • mluvı´ se naprˇ´ıklad o analy´za´ch na´vsˇteˇv profilu˚ uzˇivatelu˚, se ktery´mi nejste v kontaktu nebo analy´za´ch vyhleda´va´nı´ klı´cˇovy´ch slov – vsˇechny tyto metody pokud by byly pouzˇity jsou vsˇak v plne´m souladu s licencˇnı´mi ujedna´nı´mi jednotlivy´ch socia´lnı´ch sı´tı´, protozˇe veˇtsˇinou licencˇnı´ podmı´nky zahrnujı´ fra´zi ve smyslu toho, zˇe uzˇivatel povoluje sbeˇr dat pro vylepsˇova´nı´ sluzˇeb v ra´mci sı´teˇ (data nebudou poskytnuta trˇetı´ straneˇ).

14

8. Sofistikovaneˇjsˇ´ı metody vyhleda´va´nı´ • Facebook spustil sluzˇbu Graph Search [26] (prozatı´m v anglicˇtineˇ), ktera´ nabı´zı´ uzˇivatelu˚m novy´ zpu˚sob, jak vyhleda´vat v prostrˇedı´ socia´lnı´ sı´teˇ (vyuzˇ´ıva´ prˇi tom klasicky´ch ta´zacı´ch veˇt jako v beˇzˇne´ komunikaci); – funguje na principu skla´da´nı´ dotazu˚, naprˇ. vyhledej me´ prˇa´tele, ktery´m se lı´bı´ urcˇity´ hudebnı´ styl a bydlı´ v me´m okolı´; – algoritmy sluzˇby mu˚zˇe vyuzˇ´ıt i sa´m Facebook na na´vrhy prˇa´tel se spolecˇny´mi za´jmy a podobneˇ.

Obra´zek 2: Prˇ´ıklad na´vrhu novy´ch spojenı´ v socia´lnı´ sı´ti Facebook U vsˇech dnes beˇzˇneˇ vyuzˇ´ıvany´ch technik na´vrhu˚ novy´ch spojenı´ se objevujı´ spolecˇne´ proble´my, zejme´na pak vysoky´ pocˇet chybny´ch, respektive neadekva´tnı´ch na´vrhu˚ novy´ch prˇa´tel. Tato skutecˇnost je zaprˇ´ıcˇineˇna faktem, zˇe veˇtsˇina technik nevyuzˇ´ıva´ zˇa´dny´ sofistikovaneˇjsˇ´ı zpu˚sob verifikace vy´sledku˚ vyhleda´va´nı´. Nabı´zejı´ uzˇivateli velky´ pocˇet mozˇny´ch novy´ch kontaktu˚ a poslednı´ fa´ze filtrace mezi teˇmito vy´sledky je ponecha´na na straneˇ uzˇivatele. Naprˇ´ıklad na sı´ti Facebook (viz Obra´zek 2) z prvnı´ch sˇesti na´vrhu˚ mozˇny´ch prˇa´tel byl zna´my´ cˇloveˇk pouze jeden. Tento zpu˚sob je ovsˇem, zejme´na pro nove´ uzˇivatele, znacˇneˇ nekomfortnı´ a v prˇ´ıpadeˇ velke´ho mnozˇstvı´ chybny´ch na´vrhu˚ mu˚zˇe uzˇivatele dokonce od pouzˇ´ıva´nı´ socia´lnı´ sı´teˇ rychleji odradit. Cı´lem nove´ho algoritmu je poskytnout zpu˚sob na´vrhu˚ novy´ch spojenı´, ve ktere´m bude interakce s uzˇivatelem omezena na co nejmensˇ´ı mozˇnou mı´ru. K tomu je ovsˇem nutne´ zı´skat dodatecˇna´ data o uzˇivateli. Jelikozˇ se nenı´ mozˇno dostat k internı´m datu˚m socia´lnı´ sı´teˇ a nenı´ ani vhodne´ aplikovat techniky, ktere´ by uzˇivatele na internetu sledovaly a vyhodnocovaly jeho chova´nı´, je nutne´ najı´t jiny´ element, ze ktere´ho je mozˇno tyto

15

data extrahovat. Tı´mto elementem mohou by´t pra´veˇ volneˇ dostupne´ fotografie uzˇivatele socia´lnı´ sı´teˇ, ve ktery´ch se objevuje ve spolecˇnosti dalsˇ´ıch lidı´, ktere´ je mozˇne´ za urcˇity´ch, prˇedem urcˇeny´ch podmı´nek povazˇovat za jeho prˇa´tele. Pote´ je mozˇne´ pokusit se tyto prˇa´tele nale´zt na konkre´tnı´ socia´lnı´ sı´ti a poprˇ´ıpadeˇ navrhnout nove´ spojenı´ mezi nimi a uzˇivatelem.

16

17

3

Vyuzˇitı´ detekce a rozpozna´nı´ oblicˇeju˚ v socia´lnı´ch sı´tı´ch

Snahou zjednodusˇit uzˇivateli pouzˇ´ıva´nı´ socia´lnı´ch sı´tı´, prostrˇednictvı´m vyuzˇitı´ detekce cˇi dokonce analy´zy oblicˇeju˚, se jizˇ zaobı´ralo mnozˇstvı´ experimenta´lnı´ch sluzˇeb. Neˇktere´ z nich se dokonce dostaly i do prakticke´ho vyuzˇitı´. V na´sledujı´cı´ kapitole je cı´lem popsat jizˇ implementovane´ zpu˚soby vyuzˇitı´ rozpozna´va´nı´ oblicˇeju˚ v kontextu pra´ce se socia´lnı´ sı´tı´ a nastı´nit vlastnı´ zpu˚sob, jaky´m je mozˇno vyhleda´vat nove´ kontakty uvnitrˇ socia´lnı´ sı´teˇ s vyuzˇitı´m rozpozna´va´nı´ oblicˇeju˚.

3.1

Existujı´cı´ studie vyuzˇ´ıvajı´cı´ rozpozna´nı´ oblicˇeju˚

Prvnı´ vy´zkumny´ cˇla´nek, ktery´ je blı´zky´ te´matu zpracova´nı´ te´to diplomove´ pra´ce, se zaobı´ra´ mozˇnostı´ zautomatizova´nı´ oznacˇova´nı´ prˇa´tel na fotka´ch v socia´lnı´ sı´ti Facebook[14]. Jeho obsahem je experimenta´lnı´ algoritmus, ktery´ analyzuje tva´rˇe vsˇech vasˇich prˇa´tel na socia´lnı´ sı´ti. V prˇ´ıpadeˇ, zˇe nahrajete libovolnou fotku, obsahujı´cı´ detekovatelne´ tva´rˇe osob, na va´sˇ Facebook profil, algoritmus zanalyzuje detekovatelne´ tva´rˇe a pokusı´ se k nim automaticky prˇirˇadit jme´na. Obdoba tohoto algoritmu byla posle´ze socia´lnı´ sı´tı´ Facebook implementova´na, cozˇ zaprˇ´ıcˇinilo vyvola´nı´ kauzy, zda je legitimnı´ takto analyzovat tva´rˇe osob (vı´ce v Kapitole 4.1). Rozdı´lny´ zpu˚sob vyuzˇitı´ rozpozna´va´nı´ oblicˇeju˚ byl implementova´n ve studii Friends with Faces [3], ktera´ vznikla jako soucˇa´st veˇtsˇ´ıho vy´zkumne´ho projektu FaceBots [15]. Cı´lem cele´ho projektu bylo navrhnout robota, ktery´ by byl schopen rozpozna´vat oblicˇeje a meˇl take´ implementova´nu schopnost komunikace v beˇzˇne´ rˇecˇi. Co je pro u´cˇely te´to pra´ce nejdu˚lezˇiteˇjsˇ´ı, je ale fakt, zˇe robot byl za´rovenˇ prˇipojen do socia´lnı´ sı´teˇ, ze ktere´ si vytva´rˇel vlastnı´ socia´lnı´ databa´zi, kterou posle´ze byl schopen vyuzˇ´ıvat v beˇzˇne´m sveˇteˇ prˇi komunikaci s lidmi. Jelikozˇ meˇl schopnost analyzovat i tva´rˇe prostrˇednictvı´m zabudovany´ch kamer, byl schopen i rozhodovat, jaky´ cˇloveˇk je prˇ´ıtel (prˇ´ıpadneˇ koho je urcˇita´ osoba prˇ´ıtelem). Navı´c prˇi analy´ze fotografiı´ vyuzˇ´ıval i informace obsazˇene´ v jejich tag objektech. Algoritmus zpracova´val fotografie podle toho, do jake´ kategorie patrˇily. Rozdeˇlenı´ do prˇ´ıslusˇny´ch kategoriı´ bylo na´sledujı´cı´: a Fotografie obsahujı´cı´ libovolny´ pocˇet tva´rˇ´ı, prˇicˇemzˇ u pra´veˇ jedne´ tva´rˇe je v tagu fotografie uvedeno jme´no osoby, ktere´ patrˇ´ı (zˇa´dne´ dalsˇ´ı informace tag neobsahuje). b Fotografie, u ktere´ nenı´ ani jedna tva´rˇ spojena se jme´nem v tagu. c Fotografie obsahujı´cı´ libovolny´ pocˇet tva´rˇ´ı, prˇicˇemzˇ u vı´ce nezˇ jedne´ tva´rˇe ma´ v tagu fotografie uvedeno jme´no osoby, ktere´ patrˇ´ı. V analy´ze se pote´ dle kategorie, do ktere´ dana´ fotografie patrˇ´ı, aplikovalo rozpozna´va´nı´ s (respektive bez) socia´lnı´ho kontextu. V prˇ´ıpadeˇ, zˇe fotografie neobsahovala zˇa´dne´ informace o jme´nech zachyceny´ch osob, bylo nutne´ vyuzˇ´ıt data sesbı´rana´ ze socia´lnı´ sı´teˇ. S vyuzˇitı´m teˇchto dat a dalsˇ´ıch faktoru˚ nutny´ch k analy´ze, se algoritmus snazˇil identifikovat konkre´tnı´ osoby.

18

3.2

Vlastnı´ prˇ´ıstup k vyuzˇitı´ rozpozna´va´nı´ oblicˇeju˚

Prˇ´ıstup k analy´ze fotografiı´ s vyuzˇitı´m jejich tagu˚ uvedeny´ v pra´ci Friends with Faces [3] se jevı´ jako pomeˇrneˇ robustnı´ a efektivnı´ zpu˚sob, jak danou problematiku rˇesˇit. Je ovsˇem nutna´ interakce se samotny´m robotem, ktery´ si tvorˇ´ı vlastnı´ socia´lnı´ strukturu na sı´ti a vyuzˇ´ıva´ ji k pozdeˇjsˇ´ı analy´ze. V nove´m prˇ´ıstupu, bychom chteˇli tento aspekt u´plneˇ vypustit a mı´sto neˇj se snazˇit dodatecˇne´ informace zı´ska´vat z externı´ho zdroje vhodny´ch fotografiı´. Rozpozna´va´nı´ oblicˇeju˚ by tedy v modifikovane´m pojetı´ slouzˇilo zejme´na jako verifikacˇnı´ metoda. V prvnı´ fa´zi by se tedy nasˇel vhodny´ zdroj externı´ch fotografiı´, v neˇmzˇ by za´rovenˇ byla mozˇnost vyhledat dodatecˇne´ informace o lidech, kterˇ´ı se na fotografiı´ch vyskytujı´. Teprve posle´ze by prˇisˇlo na rˇadu rozpozna´va´nı´ oblicˇeju˚ tak, aby bylo mozˇno spa´rovat jme´na osob s jejich tva´rˇemi. Azˇ v poslednı´ fa´zi by se z takto vytvorˇeny´ch dat vyhleda´valy v urcˇite´ socia´lnı´ sı´ti nove´ kontakty. Prvnı´ mozˇnostı´ by bylo vyuzˇitı´ specificky´ch za´lib cˇi aktivit konkre´tnı´ho uzˇivatele. Na na´sledujı´cı´m prˇ´ıkladu je tento postup demonstrova´n. Uzˇivatel nove´ sluzˇby by byl cˇlenem akademicke´ obce a u´cˇastnil se cele´ rˇady konferencı´. Na teˇchto akcı´ch by potka´val mnoho osob, neˇktere´ z nich pravidelneˇ. Pra´veˇ tyto pravidelne´ kolegy by bylo vhodne´ uzˇivateli navrhnout za nove´ kontakty v socia´lnı´ sı´ti. Zpu˚sob pra´ce s takovouto aplikacı´ je zna´zorneˇn na Obra´zku 3.

Obra´zek 3: Na´vrh novy´ch spojenı´ zalozˇeny´ na aktivita´ch uzˇivatele

Uzˇivatel by byl schopen zada´vat vsˇechny konference, ktery´ch se zu´cˇastnil, poprˇ´ıpadeˇ chysta´ zu´cˇastnit. Tuto manua´lnı´ interakci by bylo samozrˇejmeˇ mozˇne´ nahradit automaticky´m zpu˚sobem. Uzˇivatel by poskytl aplikaci za´kladnı´ u´daje, jako je naprˇ´ıklad cele´ jme´no

19

a na´zev instituce, ve ktere´ pracuje. Dle teˇchto u´daju˚ by aplikace vyhledala ve verˇejneˇ dostupny´ch databa´zı´ch konferencı´ 1 , jestli se jich dany´ uzˇivatel zu´cˇastnil nebo ne. Sluzˇba by posle´ze na oficia´lnı´ch stra´nka´ch vyhledala seznam vsˇech prˇedna´sˇejı´cı´ch na konferenci (obvykle se vyskytujı´ i fotografie prˇedna´sˇejı´cı´ch) a vytvorˇila si internı´ databa´zi osob s jejich tva´rˇemi. V dalsˇ´ı fa´zi by, ve verˇejneˇ prˇ´ıstupny´ch fotografiı´ch z konference, vyhleda´vala uzˇivatele, ktery´ se na fotka´ch vyskytuje s dalsˇ´ımi osobami. Pokud by tyto osoby byly v internı´ databa´zi, bylo by mozˇne´ pokusit se je nale´zt i na socia´lnı´ sı´ti (s pomocı´ internı´ databa´ze). Jako vedlejsˇ´ı produkt te´to analy´zy by byla mozˇnost automaticky oznacˇovat detekovane´ osoby na analyzovany´ch fotografiı´ch. K tomuto by bylo nutno implementovat i webovou sluzˇbu, ktera´ by tuto zpeˇtnou propagaci vy´sledku˚ umozˇnˇovala. Vyuzˇitı´ takto implementovane´ sluzˇby by bylo ovsˇem pouze pro specifickou skupinu uzˇivatelu˚, podle toho, jaky´ typ aktivit nebo za´jmu˚ bychom zvolili. Navı´c by bylo pro umozˇneˇnı´ zpeˇtne´ publikace vy´sledku˚ nutno implementovat svou vlastnı´ webovou sluzˇbu. Samotna´ implementace by proble´m v za´sadeˇ nedeˇlala, ovsˇem vytva´rˇet kvu˚li aplikaci vlastnı´ typ socia´lnı´ sı´teˇ by bylo neefektivnı´. Z teˇchto du˚vodu˚ bylo nutne´ na´sˇ za´meˇr prˇeformulovat tak, aby byl uzˇitecˇny´ co mozˇna´ nejveˇtsˇ´ımu pocˇtu uzˇivatelu˚.

Obra´zek 4: Na´vrh novy´ch spojenı´ za´visly´ na externı´ch obra´zcı´ch Modifikovana´ sluzˇba by se meˇla chovat ve vy´sledku tak, jak je uvedeno na Obra´zku 4. Uzˇivatel musı´ poskytnout prˇ´ıstup ke sve´mu profilu na konkre´tnı´ socia´lnı´ sı´ti. Navı´c je vhodne´, aby sluzˇbeˇ nabı´dl fotografie, ktere´ je mozˇne´ podrobit analy´ze. Tyto fotografie by meˇli obsahovat tva´rˇe ostatnı´ch osob tak, aby bylo mozˇno navrhnout nova´ spojenı´ uvnitrˇ socia´lnı´ sı´teˇ. Je takte´zˇ zˇa´doucı´, aby byly fotografie ulozˇeny online na neˇktere´m z dnes beˇzˇneˇ vyuzˇ´ıvany´ch u´lozˇisˇt’cˇi obrazovy´ch galeriı´. Tato skutecˇnost je totizˇ nutna´ pro zpeˇtnou publikaci analyzovany´ch dat (naprˇ. upravene´ tagy se jme´ny nalezeny´ch osob). Tento zpu˚sob fungova´nı´ sluzˇby je dostupny´ veˇtsˇ´ımu mnozˇstvı´ uzˇivatelu˚, nezˇ v prˇedchozı´m prˇ´ıpadeˇ. Navı´c veˇtsˇina aktivnı´ch uzˇivatelu˚ socia´lnı´ sı´teˇ ma´ i vlastnı´ profil na neˇktere´m z u´lozˇisˇt’ pro fotografie, takzˇe by nemeˇl nastat proble´m se splneˇnı´m druhe´ podmı´nky.

1

naprˇ´ıklad www.conferencealerts.com

20

21

4

Legislativnı´ stra´nka rozpozna´va´nı´

Aplikace, ktere´ pouzˇ´ıvajı´ algoritmy rozpozna´nı´ oblicˇeju˚, jsou dnes v hleda´cˇku mnoha organizacı´, chra´nı´cı´ch osobnı´ u´daje uzˇivatelu˚ internetu. Zejme´na pokud se jedna´ o automaticke´ zpracova´nı´ oblicˇeju˚, ke ktery´m konkre´tnı´ cˇloveˇk, jehozˇ tva´rˇ je takto analyzova´na, nedal explicitnı´ souhlas. V soucˇasne´ dobeˇ sta´le nenı´ vymezena hranice, ve ktery´ch by se automaticke´ zpracova´nı´ teˇchto dat meˇlo pohybovat, a tudı´zˇ schvalova´nı´ prˇijatelnosti konkre´tnı´ aplikace (z hlediska legislativnı´ho pohledu) probı´ha´ veˇtsˇinou ad hoc. Pokud se budeme pohybovat v ra´mci Evropske´ unie, situace je v soucˇasne´ dobeˇ nastavena tak, zˇe biometricka´ data nejsou zahrnuta do kategorie dat, vyzˇadujı´cı´ch prˇi zpracova´nı´ explicitnı´ souhlas uzˇivatele [14]. Tudı´zˇ by se mohlo zda´t, zˇe vy´voj aplikacı´ je zde bezproble´movy´. Tuto domneˇnku vsˇak pozdeˇji vyvra´til nı´zˇe rozvedeny´ spor socia´lnı´ sı´teˇ Facebook, ktery´ znovu doka´zal, zˇe dokud nebude vytvorˇen striktneˇ dany´ ra´mec, ve ktere´m se mohou biometricka´ data zpracova´vat, bude vy´voj aplikacı´ vyuzˇ´ıvajı´cı´ch rozpozna´va´nı´ oblicˇeju˚ nada´le brzdeˇn legislativnı´m schvalova´nı´m aplikacı´. Nı´zˇe jsou pro ilustraci uvedeny jedny z nejvy´znamneˇjsˇ´ıch kauz firem, ktere´ vyuzˇ´ıvaly (cˇi hodlaly vyuzˇ´ıt) automaticke´ho zpracova´nı´ oblicˇeju˚.

4.1

Facebook a jeho sluzˇba Tag Suggestions

Facebook v polovineˇ prosince roku 2010 na sve´m oficia´lnı´m blogu [23] ohla´sil nasazenı´ nove´ sluzˇby Tag Suggestions, ktera´ meˇla uzˇivatelu˚m zprˇ´ıjemnit a zjednodusˇit pra´ci prˇi vkla´da´nı´ novy´ch fotografiı´. Sluzˇba v noveˇ nahrany´ch fotografiı´ch detekuje tva´rˇe a snazˇ´ı se k nim automaticky prˇipojit jme´na z okolı´ vasˇich prˇa´tel na Facebooku. Tato sluzˇba ovsˇem vzbudila, na podneˇt stı´zˇnosti [24] adresovane´ kancela´rˇi evropske´ho komisarˇe pro ochranu osobnı´ch u´daju˚, za´jem Evropske´ unie (konkre´tneˇ Data protection working party), ktera´ v jejich algoritmech videˇla prˇ´ılisˇny´ za´sah do osobnı´ch biometricky´ch u´daju˚ uzˇivatelu˚. Facebook se vsˇak bra´nil faktem, zˇe uzˇivatelu˚m ve svy´ch Za´sada´ch vyuzˇ´ıva´nı´ socia´lnı´ sı´teˇ principy sluzˇby dostatecˇneˇ osveˇtluje a uzˇivatele´ s nimi musı´ projevit souhlas, v opacˇne´m prˇ´ıpadeˇ socia´lnı´ sı´t’nemohou vyuzˇ´ıvat. Nicme´neˇ Evropske´ unii toto konstatova´nı´ nestacˇilo a zacˇala ve´st s Facebookem diskuzi o podmı´nka´ch, za ktery´ch svou sluzˇbu mu˚zˇe uve´st pro uzˇivatele ze zemı´ EU. Evropska´ unie se touto kauzou zacˇala zaby´vat a zacˇlenila ji do sve´ auditnı´ zpra´vy ty´kajı´cı´ se Facebooku [25], ve ktere´ neprosˇetrˇovala pouze zavedenı´ sluzˇby vyuzˇ´ıvajı´cı´ rozpozna´va´nı´ oblicˇeju˚ , ale i zpracova´va´nı´ dalsˇ´ıch u´daju˚ uzˇivatelu˚. Fungova´nı´ sluzˇby a hlavnı´ vy´tky vu˚cˇi nı´ Sluzˇba Tag Suggestions funguje tak, zˇe pokud uzˇivatel nahraje nove´ fotografie, Facebook tyto fotky procha´zı´ a hleda´ v nich tva´rˇe. Pokud tva´rˇe nalezne, pokusı´ se dle drˇ´ıve sesbı´rany´ch informacı´ (zalozˇeny´ch na prˇedchozı´ch rucˇnı´ch oznacˇenı´ch prˇa´tel) navrhnout uzˇivateli jme´na osob, ktere´ se na fotce pravdeˇpodobneˇ nacha´zejı´. Pokud tva´rˇe nenı´ mozˇno identifikovat, Facebook tyto neu´speˇsˇne´ fotografie seskupuje podle podobnostı´ tak, aby je uzˇivatel posle´ze mohl sa´m otagovat co mozˇna´ nejrychleji.

22

Samozrˇejmeˇ blizˇsˇ´ı informace o algoritmech Facebook verˇejneˇ neposkytuje, avsˇak jizˇ z vy´sˇe uvedeny´ch u´daju˚ je zrˇejme´, zˇe algoritmy, ktere´ vyuzˇ´ıva´ jsou smeˇsicı´ algoritmu˚ poloautomaticky´ch (jelikozˇ vyzˇadujı´ prˇedchozı´ informace od uzˇivatele) a algoritmu˚ samoucˇ´ıcı´ch. V nı´zˇe uvedene´m seznamu jsou hlavnı´ vy´tky vu˚cˇi sluzˇbeˇ Tag Suggestions: • Facebook neprˇizna´va´, zˇe generuje cˇi jinak pracuje s biometricky´mi daty uzˇivatelu˚. • Sta´vajı´cı´ uzˇivatele´ nemusı´ s novinkou souhlasit, avsˇak Facebook je nevyzval k udeˇlenı´ nove´ho souhlasu s pozmeˇneˇny´mi Podmı´nkami pouzˇitı´ socia´lnı´ sı´teˇ. • Uzˇivatelu˚m nebyly poskytnuty zˇa´dne´ specificke´ informace o principech fungova´nı´ nove´ sluzˇby. • Sluzˇbu je obtı´zˇne´ deaktivovat a navı´c nenı´ jasne´, zda po deaktivaci sluzˇby Facebook vymazˇe jizˇ nasbı´rana´ data. Navı´c vyvstala i ota´zka, jak jsou na souhlas dotazova´ni uzˇivatele´, kterˇ´ı tuto sluzˇbu aktivneˇ nevyuzˇ´ıvajı´, ale jejich prˇa´tele´ ano, a tudı´zˇ jsou jejich oblicˇeje analyzova´ny take´. Reakce Facebooku na provedeny´ audit byla shleda´na jako dostatecˇna´. Co se ty´ka´ souhlasu uzˇivatelu˚ s u´dajneˇ pozmeˇneˇny´mi podmı´nkami vyuzˇ´ıva´nı´ sı´teˇ, reagoval tak, zˇe jizˇ ve svy´ch prˇedchozı´ch podmı´nka´ch meˇl sekci, ve ktere´ uzˇivatele´ vyslovujı´ souhlas s urcˇity´m zpracova´nı´m osobnı´ch u´daju˚, ve snaze zlepsˇit sluzˇby socia´lnı´ sı´teˇ. Vyvra´til take´ informaci, zˇe by uzˇivatele´ nebyli dostatecˇneˇ sezna´meni s novou sluzˇbou a zˇe je obtı´zˇne´ tuto sluzˇbu vypnout. Takte´zˇ vydal prohla´sˇenı´, zˇe pokud uzˇivatel sluzˇbu deaktivuje, vsˇechna drˇ´ıve sesbı´rana´ data jsou vymaza´na a da´le jizˇ nenı´ pokracˇova´no v jejich opeˇtovne´m sbeˇru. V na´vaznosti na toto poskytl cˇlenu˚m EU algoritmy, ktere´ tento fakt doka´zaly. Fina´lnı´ stanovisko EU, v na´vaznosti na provedene´ zmeˇny ze strany socia´lnı´ sı´teˇ Facebook, bylo takove´, zˇe jsou tyto zmeˇny dostatecˇne´ a Facebook tedy mu˚zˇe svou sluzˇbu provozovat i na u´zemı´ EU. Jako du˚lezˇity´ fakt pro dalsˇ´ı vy´voja´rˇe obdobny´ch aplikacı´ bylo vyda´no doporucˇenı´, zˇe i prˇes skutecˇnost, zˇe biometricka´ data nespadajı´ do kategorie osobnı´ch dat vyzˇadujı´cı´ch souhlas majitele s jejich zpracova´nı´m, je vhodne´ si takovy´to souhlas vyzˇa´dat. Prˇedpokla´da´ se totizˇ, zˇe v budoucnu tyto data do kategorie vysoce citlivy´ch u´daju˚ zahrnuta budou.

4.2

Google s aplikacı´ Google Googles

I firma Google se jizˇ snazˇila vyuzˇ´ıt techniku rozpozna´va´nı´ oblicˇeju˚ ve svy´ch produktech. Konkre´tneˇ v prosinci roku 2009 prˇedstavila svou novou aplikaci Google Googles, cozˇ je aplikace analyzujı´cı´ a rozpozna´vajı´cı´ objekty pomocı´ prˇenosny´ch zarˇ´ızenı´, jako jsou chytre´ telefony cˇi tablety. Ve sve´ soucˇasne´ verzi umı´ naprˇ. zpracova´vat sˇtı´tky a etikety rozdı´lny´ch produktu˚ a vyhleda´vat na internetu informace o nich nebo vyhleda´vat obdobne´ vy´robky. Google tı´mto vlastneˇ volneˇ nava´zal na drˇ´ıve vyvı´jeny´ hardware CueCat, ktery´ meˇl za u´kol naskenovat URL z tisˇteˇny´ch me´diı´ a automaticky otevı´rat tuto stra´nku v prohlı´zˇecˇi. Cı´lem Google bylo do te´to aplikaci implementovat i vyhleda´va´nı´ a rozpozna´va´nı´ oblicˇeju˚. Od tohoto sice prozatı´m upustil [20], ale patent na sve´ jedinecˇne´ vyhleda´va´nı´

23

ma´ jizˇ zaregistrova´n (viz Obra´zek 5) a hodla´ jej pouzˇ´ıt ve sve´ socia´lnı´ sı´ti. Podle vyja´drˇenı´ Google, musı´ vsˇak prˇed samotny´m spusˇteˇnı´m te´to sluzˇby pecˇliveˇ zva´zˇit ota´zku osobnı´ch u´daju˚. Google navı´c take´ uvazˇoval o implementaci rozpozna´va´nı´ oblicˇeju˚ do sve´ nove´ platformy Google Glass nebo alesponˇ poskytl mozˇnost vy´voja´rˇu˚m na te´to platformeˇ rozpozna´va´nı´ implementovat. Konkre´tneˇ se do projektu vy´voju˚ sluzˇeb vyuzˇ´ıvajı´cı´ch rozpozna´va´nı´ oblicˇeju˚ prˇipojily firmy Lambda Labs a Rekognition [17]. Z toho za´meˇru vsˇak byl nucen Google odstoupit [17], opeˇt z jizˇ vy´sˇe uvedeny´ch du˚vodu˚ obav o ochranu soukromı´ uzˇivatelu˚. Vy´sˇe uvedena´ vyja´drˇenı´ jsou uka´zkou tvrzenı´, zˇe je nutne´ zave´st jasny´ ra´mec, jak se staveˇt ke zpracova´nı´ biometricky´ch u´daju˚. Ve sta´vajı´cı´ situaci je totizˇ slozˇite´ nasadit obdobne´ typy sluzˇeb do provozu bez toho, aby byla firma vystavena kritice za zneuzˇ´ıva´nı´ osobnı´ch u´daju˚.

4.3

Doporucˇenı´ pro korektnı´ vyuzˇitı´ rozpozna´va´nı´ tva´rˇ´ı

Prima´rneˇ je nova´ aplikace urcˇena´ pouze pro experimenta´lnı´ provozova´nı´ v akademicke´ sfe´rˇe, takzˇe nevyzˇaduje podrobneˇjsˇ´ı tvorbu podmı´nek vyuzˇ´ıva´nı´ cˇi obdobny´ch koncovy´ch smluv s uzˇivatelem. Pro prˇ´ıpadny´ vy´voj aplikace, urcˇene´ pro ostry´ provoz, je vhodne´ soustrˇedit se na na´sledujı´cı´ fakta. V prvnı´ rˇadeˇ je nutne´ vyzˇa´dat si explicitnı´ souhlas uzˇivatelu˚ sluzˇby se zpracova´nı´m biometricky´ch u´daju˚, a to bez ohledu na skutecˇnost, zˇe nejsou v neˇktery´ch zemı´ch sta´le pokla´da´na za data vyzˇadujı´cı´ zvla´sˇtnı´ nakla´da´nı´ prˇi zpracova´nı´ 2 . Da´le je vhodne´ prˇi vy´voji a nasazenı´ sluzˇby, postupovat podle jizˇ publikovany´ch postupu˚ rˇesˇenı´, tzv. best practices dokumentu˚. Naprˇ´ıklad [6], cozˇ jsou postupy zavedene´ pro vy´voj aplikacı´ v USA (respektive pro ochranu uzˇivatelu˚ aplikacı´ na u´zemı´ USA). V te´to zpra´veˇ jsou zavedeny trˇi za´kladnı´ principy, ktere´ by meˇla noveˇ vznikajı´cı´ sluzˇba, vyuzˇ´ıvajı´cı´ rozpozna´va´nı´ oblicˇeju˚, splnˇovat. V kazˇde´ fa´zi samotne´ho vy´voje aplikace by meˇla by´t bra´na ochrana soukromı´ uzˇivatelu˚ jako priorita. Tam, kde je to mozˇne´, by aplikace nemeˇla ukla´dat zˇa´dne´ citlive´ data, ani je propojovat s daty jiny´mi (tedy by se naprˇ´ıklad v aplikaci nemeˇla vyskytovat analy´za chova´nı´ uzˇivatele). V prˇ´ıpadech, kde je zpracova´nı´ osobnı´ch u´daju˚ uzˇivatelu˚ nutne´, je vhodne´ se chovat transparentneˇ. Kuprˇ´ıkladu poskytovat kazˇde´mu uzˇivateli u´plny´ seznam vsˇech dat, ktera´ jsou o neˇm zpracova´va´na. Take´ je vhodne´ zjednodusˇit uzˇivateli orientaci v poskytovany´ch sluzˇba´ch aplikace, a to vcˇetneˇ detailnı´ho vysveˇtlenı´, jaky´m zpu˚sobem sluzˇby fungujı´. Paklizˇe se vy´voja´rˇi budou rˇ´ıdit vy´sˇe uvedeny´mi na´vrhy, meˇlo by to mı´t za na´sledek minimalizaci pravdeˇpodobnosti stı´zˇnostı´ uzˇivatelu˚ cˇi organizacı´ na jejich aplikace. Jistotu byl ovsˇem prˇivedlo drˇ´ıve zmı´neˇne´ jasne´ stanovenı´ hranic prˇi vy´voji prˇ´ıslusˇny´mi institucemi tak, aby byly aplikace vyvı´jeny bez teˇchto obav z mozˇny´ch pra´vnı´ch sporu˚.

2

dle Irish Data Protection Acts a EU Data Protection Directive

24

Obra´zek 5: Algoritmus rozpozna´va´nı´ tva´rˇ´ı Google (s cˇ´ısly patentu˚) [20]

25

5

Algoritmy rozpozna´va´nı´ oblicˇeju˚

Veˇtsˇina sta´vajı´cı´ch algoritmu˚ urcˇena´ k rozpozna´va´nı´ oblicˇeju˚, pracuje s obrazy v 2D prostoru. Existujı´ samozrˇejmeˇ i algoritmy, pracujı´cı´ s plneˇ 3rozmeˇrny´m modelem tva´rˇe, ty jsou ale pro tuto diplomovou pra´ci bezprˇedmeˇtne´, jelikozˇ cı´lem je analyzovat fotografie, nikoliv modely. Na´sledujı´cı´ text se tedy zameˇrˇuje pouze na kategorii algoritmu˚ pracujı´cı´ch s 2D fotografiemi.

5.1

Princip analy´zy tva´rˇ´ı

Veˇtsˇina dnes beˇzˇneˇ vyuzˇ´ıvany´ch algoritmu˚ rozpozna´va´nı´ na same´m pocˇa´tku analy´zy vyhleda´va´ ve tva´rˇi prima´rnı´ objekty [9], jako jsou ocˇi, u´sta, nos a usˇi a analyzuje, jak vlastnosti kazˇde´ho prvku zvla´sˇt’(velikost, tvar, ...), tak i vlastnosti vza´jemne´ (pomeˇr mezi jednotlivy´mi prvky, vzda´lenost, u´hel, ...). Tento prˇ´ıstup ma´ ovsˇem jizˇ ve sve´ pocˇa´tecˇnı´ fa´zi jednu nezbytnou premisu. Vsˇechny prima´rnı´ prvky musı´ by´t ve tva´rˇi detekovatelne´ a jednoznacˇneˇ identifikovatelne´ (nemu˚zˇe se sta´t, zˇe algoritmus zameˇnı´ naprˇ. ucho za oko). Zde ovsˇem vyvsta´va´ proble´m, jaky´m zpu˚sobem vyhleda´va´nı´ teˇchto prvku˚ zautomatizovat tak, aby mohl vy´sledny´ rozpozna´vacı´ algoritmus probeˇhnout korektneˇ. V za´sadeˇ se prˇi prakticke´ implementaci mu˚zˇeme setkat se dveˇma za´kladnı´mi druhy proble´mu˚. Na analyzovane´ fotografii mu˚zˇe by´t tva´rˇ zachycena s neu´plnou mnozˇinou prima´rnı´ch objektu˚. Nejcˇasteˇjsˇ´ım du˚vodem by´va´ fakt, zˇe osoba je vyfocena z jine´ho nezˇ idea´lnı´ho u´hlu, nebo je neˇktery´ z prima´rnı´ch objektu˚ tva´rˇe v za´krytu jine´ho objektu (stı´n ve tva´rˇi nebo v prˇ´ıpadeˇ zˇen zakrytı´ jednoho oka vlasy). Druhy´m typem proble´mu je situace, kdy je tva´rˇ zachycena ve sˇpatne´m vertika´lnı´m u´hlu. Pokud algoritmus na tento fakt nebude prˇipraven, je sice schopen urcˇit korektneˇ loka´lnı´ vlastnosti jednotlivy´ch prvku˚, ale selha´va´ v analy´ze vza´jemny´ch vlastnostı´ mezi prima´rnı´mi objekty (zejme´na u´hel). I kdyzˇ se podarˇ´ı vyrˇesˇit oba vy´sˇe uvedene´ prima´rnı´ proble´my, vy´sledkem je analy´za oblicˇeje, ktera´ ovsˇem nenı´ dostatecˇneˇ robustnı´ a neposkytuje dostatecˇneˇ kvalitnı´ identifikaci uzˇivatele [16]. Avsˇak i naproti teˇmto nevy´hoda´m a male´ spolehlivosti se i dnes jedna´ o jeden z nejcˇasteˇjsˇ´ıch zpu˚sobu˚ implementace rozpozna´vacı´ch algoritmu˚.

5.2

Techniky rozpozna´va´nı´ oblicˇeju˚

Jak jizˇ bylo vy´sˇe uvedeno, jeden z prvnı´ch kroku˚ prˇi analy´ze tva´rˇ´ı je vyhledat ve tva´rˇ´ıch prima´rnı´ objekty, ktere´ se pozdeˇji blı´zˇe zkoumajı´. Techniky jak tento krok prakticky implementovat, se dajı´ rozdeˇlit do trˇ´ı za´kladnı´ch kategoriı´, podle ktery´ch lze take´ klasifikovat i samotne´ algoritmy. 5.2.1

Poloautomaticke´ metody

Prvnı´m a nejjednodusˇsˇ´ım zpu˚sobem z hlediska implementace, je vyuzˇ´ıt interakci s uzˇivatelem a nechat ho samotne´ho oznacˇit prima´rnı´ objekty na fotce (viz Obra´zek 6), poprˇ. prˇiblizˇna´ mı´sta, kde by se meˇly nacha´zet, pokud na fotografii chybı´ u´plneˇ. I dnes je sta´le

26

Obra´zek 6: Prima´rnı´ objekty ve tva´rˇi velky´ pocˇet aplikacı´, ktery´ tento zpu˚sob vyuzˇ´ıvajı´. Pro u´cˇely te´to diplomove´ pra´ce, je tento typ algoritmu˚ zcela nevhodny´, jelikozˇ cı´lem je implementovat aplikaci, ve ktere´ je interakce s uzˇivatelem omezena na minimum. Prvnı´, kdo se pokusil tento syste´m implementovat byl W.W. Bledsoe [8], ktery´ stanovil postup, zˇe nejprve je nutne´ aby cˇloveˇk vyznacˇil na obra´zku tyto prima´rnı´ objekty a azˇ pote´ je mozˇno aplikovat automaticke´ zpracova´nı´ teˇchto informacı´ [7]. Pozdeˇji tento prˇ´ıstup jesˇteˇ zdokonalili v Bell Labs, kde jednoznacˇneˇ stanovili vektor slozˇeny´ z prima´rnı´ch objektu˚ (o maxima´lnı´ velikosti 21 prvku˚), ktery´ byl pote´ pro automaticke´ vyhodnocova´nı´ vy´hodneˇjsˇ´ı [10]. 5.2.2

Automaticke´ algoritmy

V prˇ´ıpadeˇ, kdy by bylo nutne´ zpracova´vat veˇtsˇ´ı mnozˇstvı´ fotografiı´ za´rovenˇ, by se poloautomaticke´ algoritmy v praxi vyuzˇ´ıvat nedaly. Zacˇaly se tedy uzpu˚sobovat tak, aby bylo mozˇno vyhleda´vat prima´rnı´ objekty v tva´rˇi automaticky. Jako prvnı´ o te´to mozˇnosti zacˇali psa´t Fichler a Elschlager, kterˇ´ı zavedli algoritmus vylepsˇujı´cı´ poloautomaticky´ prˇ´ıstup tak, zˇe doka´zal stanovit a meˇrˇit prima´rnı´ objekty automaticky [11]. Algoritmus Fichlera a Elschlagera byl pote´ da´le zdokonalova´n a byl v neˇm implementova´n parametrizovany´ model oblicˇeje, dı´ky ktere´mu bylo mozˇno daleko spolehliveˇji prima´rnı´ objekty identifikovat (hodnota parametru tohoto modelu se stanovovala automaticky podle konkre´tnı´ho obrazu) [12]. 5.2.3

Samoucˇı´cı´ algoritmy

S postupny´m vylepsˇova´nı´m sta´vajı´cı´ch algoritmu˚ se dosˇlo k za´veˇru, zˇe bude nutne´ zave´st postupy, kdy se sa´m algoritmus bude da´le zdokonalovat v za´vislosti na jizˇ prozkoumany´ch tva´rˇ´ıch. Tento fakt by meˇl za na´sledek take´ eliminaci jednoho z nejveˇtsˇ´ıch proble´mu˚ prˇi rozpozna´va´nı´ oblicˇeju˚, ktery´m jsou zmeˇny tvaru prima´rnı´ch objektu˚ v za´vislosti na

27

Obra´zek 7: Zmeˇna tva´rˇe v za´vislosti na emocı´ch cˇloveˇka vyjadrˇovany´ch emocı´ch cˇloveˇka (viz Obra´zek 7). Zatı´m vsˇechny vy´sˇe uvedene´ algoritmy, se s tı´mto v praxi cˇasty´m proble´mem , nemohly vyrovnat. Zpocˇa´tku se na algoritmech zacˇalo vyuzˇ´ıvat asociativnı´ch sı´tı´, ktere´ obsahovaly jednoduche´ samoucˇ´ıcı´ algoritmy [2]. Algoritmy byly da´le vylepsˇova´ny o procvicˇujı´cı´ syste´my s vyuzˇitı´m zpeˇtne´ propagace vy´sledku˚ [13]. S na´stupem a rozsˇ´ırˇenı´m neuronovy´ch sı´tı´ se zacˇaly algoritmy rozpozna´va´nı´ rozsˇirˇovat i o tento zpu˚sob samoucˇenı´. Na ba´zi neuronovy´ch sı´tı´ byl vyvinut syste´m WISARD, cozˇ byl syste´m pro vsˇeobecne´ vyuzˇitı´ rozpozna´va´nı´ objektu˚, ktery´ byl pozdeˇji vyuzˇit i v prˇ´ıpadeˇ rozpozna´va´nı´ oblicˇeju˚ [1].

5.3

Volneˇ dostupne´ sluzˇby vyuzˇitelne´ k u´cˇelu rozpozna´va´nı´ oblicˇeju˚

Steˇzˇejnı´ cˇa´stı´ cele´ diplomove´ pra´ce je spra´vny´ vy´beˇr algoritmu, respektive softwaru, ktery´ bude pouzˇit pro samotne´ rozpozna´va´nı´ oblicˇeju˚. Vy´beˇr by meˇl by´t proveden zejme´na s ohledem na na´sledujı´cı´ pozˇadavky. 1. Software by meˇl zvla´dat analy´zu veˇtsˇ´ıho mnozˇstvı´ fotografiı´ v kra´tke´m cˇasove´m rozmezı´. 2. Umozˇneˇnı´ ukla´da´nı´ kolekcı´ jizˇ analyzovany´ch fotografiı´ po dobu rˇa´doveˇ jednotek minut. 3. Poskytova´nı´ dodatecˇny´ch textovy´ch dat analyzovany´ch oblicˇeju˚ (naprˇ. pohlavı´, cozˇ lze posle´ze vyuzˇ´ıt k prvotnı´ filtraci tva´rˇ´ı)

28

4. S ohledem na samotne´ zada´nı´ pra´ce by meˇl by´t take´, pokud je to mozˇne´, uvolneˇn ve svobodne´ licenci. Jizˇ na zacˇa´tku, po dohodeˇ s vedoucı´m diplomove´ pra´ce, bylo stanoveno vyuzˇitı´ externı´ aplikace jako celku (poprˇ´ıpadeˇ cele´ho SDK), nikoliv tedy pouze implementace sta´vajı´cı´ch algoritmu˚ do nove´ aplikace. Sluzˇba by meˇla by´t webova´, takzˇe se nebude muset distribuovat loka´lneˇ s aplikacı´. Tento postup ma´ vy´hodu v daleko rychlejsˇ´ım dokoncˇenı´ aplikace i ve faktu, zˇe v prˇ´ıpadeˇ zjisˇteˇnı´ budoucı´ nevyhovujı´cı´ kvality algoritmu, jej lze nahradit. Nevy´hodou je pote´ funkcˇnı´ za´vislost aplikace na externı´ sluzˇbeˇ a zpomalenı´ beˇhu cele´ aplikace z du˚vodu˚ nutnosti komunikovat se sluzˇbou skrze internet. Vyhleda´va´nı´ nejvhodneˇjsˇ´ı externı´ sluzˇby dle vy´sˇe uvedeny´ch parametru˚ nebylo jednoduche´. Veˇtsˇina volneˇ dostupny´ch webovy´ch sluzˇeb implementuje pouze detekci oblicˇeju˚, ale neposkytuje zˇa´dna´ dodatecˇna´ data ani porovna´va´nı´ oblicˇeju˚ navza´jem. V prˇ´ıpadeˇ, zˇe jizˇ sluzˇba porovna´va´nı´ oblicˇeju˚ poskytuje, veˇtsˇinou k tomu vyuzˇ´ıva´ nejjednodusˇeji implementovatelne´ algoritmy. Vy´hoda tohoto typu algoritmu spocˇ´ıva´ v kra´tke´ vy´pocˇetnı´ dobeˇ potrˇebne´ k analy´ze, ovsˇem chybovost teˇchto algoritmu˚ je velika´. S ohledem na tyto fakta byly nakonec vybra´ny dveˇ webove´ sluzˇby, ze ktery´ch byla po analy´ze, v aplikaci pouzˇita jedina´. 5.3.1

Luxand FaceSDK

Nejedna´ se o sluzˇbu jako celek, ale o SDK, ktere´ umozˇnˇuje vyuzˇ´ıvat implementovane´ sluzˇby. Vyuzˇ´ıva´ algoritmy, ktere´ ve tva´rˇi detekujı´ 66 specia´lnı´ch bodu˚, jako jsou ocˇi nebo u´sta (viz Obra´zek 8). Posle´ze tyto body algoritmus vyuzˇ´ıva´ k rozpozna´va´nı´ oblicˇeju˚. Volneˇ je dostupna´ uka´zkova´ aplikace, kompletnı´ SDK jizˇ volneˇ dostupne´ nenı´. Nejsou verˇejneˇ dostupne´ ani informace o ceneˇ, jelikozˇ ta se stanovuje pro kazˇdou aplikaci individua´lneˇ. Pro akademicke´ u´cˇely by tedy bylo nutne´ vyuzˇ´ıvat pouze volneˇ dostupnou aplikaci.

Obra´zek 8: Stanovenı´ unika´tnı´ch bodu˚ ve tva´rˇi sluzˇbou Luxand Vy´hodou pouzˇitı´ te´to aplikace by byl zejme´na fakt, zˇe se jedna´ o komercˇneˇ vyuzˇ´ıvanou sluzˇbu s dobrou podporou a pomeˇrneˇ kvalitnı´m algoritmem rozpozna´va´nı´, ktery´ je vyuzˇ´ıva´n naprˇ´ıklad i pro prˇihlasˇova´nı´ do syste´mu˚ [22]. V te´to pra´ci je ovsˇem jeho pouzˇitı´ nevyhovujı´cı´, jelikozˇ se nejedna´ o volneˇ dostupny´ software a pouzˇitı´ pouze volneˇ dostupne´ uka´zkove´ aplikace se uka´zalo jako nevhodne´.

29

5.3.2

Betaface

Betaface je poskytova´na jako volneˇ dostupna´ webova´ sluzˇba. Za´kladnı´ komunikace s nı´ probı´ha´ prostrˇednictvı´m webove´ stra´nky, na ktere´ beˇzˇ´ı Silverlight aplikace, pomocı´ ktere´ se fotografie nahra´vajı´. Vy´sledky jsou poskytova´ny v textove´ podobeˇ. Dı´ky verˇejneˇ dostupne´mu API, je ale mozˇno komunikovat se sluzˇbou i programoveˇ, pomocı´ klasicky´ch metod GET a POST. Informace o algoritmu, ktery´ sluzˇba vyuzˇ´ıva´ nejsou verˇejneˇ dostupne´, avsˇak z oficia´lnı´ch internetovy´ch stra´nek je mozˇne´ se domnı´vat, zˇe se jedna´ o algortimus, vyuzˇ´ıvajı´cı´ analy´zu prima´rnı´ch objektu˚ ve tva´rˇi, s jistou mı´rou prvku˚ samoucˇenı´. Nevy´hodou te´to sluzˇby je fakt, zˇe zpracova´nı´ veˇtsˇ´ıho mnozˇstvı´ fotografiı´ mu˚zˇe by´t serverem pro free uzˇivatele cı´leneˇ zpomaleno. V prˇ´ıpadeˇ vyuzˇitı´ te´to sluzˇby v komercˇnı´ch aplikacı´ch, je mozˇno se te´to nevy´hodeˇ vyhnout prostrˇednictvı´m na´kupu licence. Jelikozˇ je vsˇak sluzˇba v rozpozna´va´nı´ oblicˇeju˚ robustnı´ (viz Tabulka 5) a je volneˇ dostupna´, bylo rozhodnuto, zˇe bude v diplomove´ pra´ci vyuzˇita.

Obra´zek 9: Prostrˇedı´ Silverlight aplikace Betaface

Za´kladnı´ rysy sluzˇby Betaface Cela´ komunikace se sluzˇbou probı´ha´ prostrˇednictvı´m XML dokumentu˚, ktere´ jsou prˇipojeny k jednotlivy´m request/response pozˇadavku˚m. Toto rˇesˇenı´ ma´ vy´hodu, zˇe dı´ky pouzˇitı´ XML je komunikace jednotneˇjsˇ´ı. Nevy´hodou pouzˇitı´ XML je o ma´lo veˇtsˇ´ı datovy´ prˇenos prˇi samotne´ komunikaci. Velikost XML vsˇak v porovna´nı´ se samotny´mi obrazovy´mi daty nenı´ natolik velika´, aby to znamenalo markantnı´ proble´m. Navı´c sluzˇba poskytuje i dodatecˇne´ textove´ informace (viz Obra´zek 9), ktere´ mu˚zˇou nove´ aplikaci umozˇnit prvotnı´ filtraci vyobrazeny´ch tva´rˇ´ı, naprˇ´ıklad podle pohlavı´ osoby. Komunikace se sluzˇbou Jak bylo vy´sˇe uvedeno, komunikace probı´ha´ pomocı´ XML dokumentu˚. Nejprve je nutne´ nahra´t obrazova´ data na server. Data jsou obsazˇena v jednom z elementu˚ XML souboru ve forma´tu base64Binary[4] (viz Vy´pis 1).V odpoveˇdi server vra´tı´ unika´tnı´ identifika´tor nahrane´ fotografie, ktery´ bude da´le v komunikaci vyuzˇ´ıva´n. Po nahra´nı´ je nutno cˇekat urcˇitou dobu na zpracova´nı´ dat. Tato doba je ovlivneˇna samotnou

30

velikostı´ fotografie, vytı´zˇenostı´ serveru i pocˇtem jizˇ analyzovany´ch dat pro konkre´tnı´ho uzˇivatele Betaface sluzˇby (v prˇ´ıpadeˇ volneˇ dostupne´ varianty Betaface). Definice 5.1 Forma´t base64Binary je ko´dovany´ textovy´ vy´stup bina´rnı´ch dat, ktery´ je vyuzˇ´ıva´n v prˇ´ıpadech, kdy je nutne´ bina´rnı´ data prˇena´sˇet nebo ukla´dat v textove´m forma´tu. Vyuzˇitı´ tohoto forma´tu je dnes naprˇ´ıklad u webovy´ch prohlı´zˇecˇu˚, ktere´ tak ukla´dajı´ neˇktere´ data uzˇivatelu˚. Beˇzˇne´ je i pra´veˇ na´mi uvedene´ pouzˇitı´ forma´tu prˇi vkla´da´nı´ dat do XML dokumentu˚. Modifikace tohoto forma´tu je potom pouzˇitelna´ i u generova´nı´ URL adres, do ktery´ch je potrˇeba vlozˇit jedinecˇne´ id (naprˇ´ıklad z databa´zı´). d45fd466−51e2−4701−8da8−04351c872236 171e8465−f548−401d−b63b−caf0dc28df5f <detection flags>0 /9j/4AAQSkZJRgABAQEAZABkAAD/... ae2.jpg

Vy´pis 1: Forma´t pozˇadavku POST (obrazova´ data ko´dova´na do forma´tu base64Binary) Jelikozˇ doba nemu˚zˇe by´t pevneˇ stanovena, aplikace je nucena se periodicky na server dotazovat na prˇipravenost dat. Toto probı´ha´ opeˇt metodou POST s prˇilozˇeny´m XML dokumentem. Tato komunikace jizˇ probı´ha´ za pouzˇitı´ unika´tnı´ho identifika´toru fotografie, ktera´ jizˇ je na serveru ulozˇena (viz Vy´pis 2). d45fd466−51e2−4701−8da8−04351c872236 171e8465−f548−401d−b63b−caf0dc28df5f 123ab32a−3ae4−42cb−a0e0−a2e53772472c

Vy´pis 2: Pozˇadavek na informace o rozpoznane´ tva´rˇi ve fotografii Vy´sledne´ informace o obra´zku (viz Vy´pis 3) mohou obsahovat odlisˇne´ typy dat v za´vislosti na tom, jestli jsme naprˇ´ıklad pozˇa´dali pouze o analy´zu 1 obrazu nebo vyhleda´va´nı´ podobnostı´ mezi vı´ce oblicˇeji. Data ty´kajı´cı´ se veˇku cˇi pohlavı´ mohou by´t v te´to pra´ci vyuzˇita pro prˇedbeˇzˇne´ roztrˇ´ıdeˇnı´ dat dle podobny´ch vlastnostı´. V te´to odpoveˇdi je du˚lezˇite´ si povsˇimnout, zˇe se objevil novy´ identifika´tor (v ko´du uid). Ten se jizˇ nevztahuje k fotografii jako celku, ale pouze k rozpoznane´ tva´rˇi. Pro dalsˇ´ı dotazy na server Betaface, ty´kajı´cı´ se urcˇova´nı´ shod ru˚zny´ch oblicˇeju˚ jizˇ budeme pouzˇ´ıvat jej.

31

0 <string response>ok df3fe6f94173e6... 22.5 0.95722800493240356 3.179025 −1 <ethincity>other <ethincity confidence>1 female 1 −1 94.421 ... OTHER INFORMATION... ... another detected face description ec43984f−0e81−4a85−866f−31f605d1f3be

Vy´pis 3: Forma´t odpoveˇdi serveru s detailnı´mi informacemi o obraze Klady a za´pory sluzˇby Z du˚vodu vyuzˇitı´ te´to sluzˇby v rezˇimu free uzˇivatele je nutne´ do budoucna pocˇ´ıtat s mozˇny´m omezenı´m sluzˇby. Zejme´na pokud pocˇet uzˇivatelu˚ poroste, je pravdeˇpodobne´, zˇe se naprˇ´ıklad v urcˇite´m cˇasove´m rozmezı´ omezı´ mozˇnost dotazu˚ na server. Samotne´ nahra´va´nı´ fotografiı´ na server je umozˇneˇno dveˇma zpu˚soby. Prvnı´ zpu˚sob je klasicke´ nahra´nı´ dat z loka´lnı´ho u´lozˇisˇteˇ na server. Druhy´m zpu˚sobem je, poskytnout serveru Betaface pouze URL adresu ke konkre´tnı´ fotografii. Pra´veˇ v prˇ´ıpadeˇ druhe´ho zpu˚sobu, ktery´ nova´ aplikace vyuzˇ´ıva´ je mozˇne´ v budoucnu ocˇeka´vat jista´ dodatecˇna´ omezenı´, jelikozˇ v soucˇasne´ situaci je pomeˇrneˇ snadne´ prˇemı´rou takovy´chto pozˇadavku˚ zahltit server. Co se ty´ka´ samotny´ch algoritmu˚, ktere´ se prˇi rozpozna´va´nı´ pouzˇ´ıvajı´, da´ se ocˇeka´vat jejich dalsˇ´ı vylepsˇova´nı´ a tedy i zkvalitnˇova´nı´ celkove´ sluzˇby. Nety´ka´ se to jen samotne´ho rozpozna´va´nı´ dvou cˇi vı´ce tva´rˇ´ı, ale i dodatecˇny´ch textovy´ch informacı´ o kazˇde´ tva´rˇi, jelikozˇ tato analy´za je take´ prova´deˇna samoucˇ´ıcı´mi algoritmy. Na Obra´zku 10 je mozˇne´ videˇt, jak si algoritmus po analy´za´ch velke´ho mnozˇstvı´ oblicˇeju˚, utvorˇil prˇedstavu o tom, jak vypada´ muzˇ a jak zˇena, nebo jak rozlisˇovat mezi veˇkovy´mi skupinami.

5.4

Mozˇnost kombinace sluzˇeb a prˇ´ıpadna´ efektivita tohoto rˇesˇenı´

Ve fa´zi hleda´nı´ vhodny´ch na´stroju˚ pro rozpozna´va´nı´ oblicˇeju˚, byla rovneˇzˇ oveˇrˇova´na mozˇnost kombinace dvou sluzˇeb, ktere´ by se vza´jemneˇ doplnˇovaly. Vhodnost pouzˇitı´

32

Obra´zek 10: Modelove´ skupiny tva´rˇ´ı vytvorˇene´ samoucˇ´ıcı´m algoritmem dvou sluzˇeb byla zalozˇena na domneˇnce, zˇe by bylo mozˇno usˇetrˇit urcˇite´ mnozˇstvı´ prˇeneseny´ch dat. O takove´to redukci prˇena´sˇeny´ch dat, bylo vhodne´ se zaobı´rat, zejme´na v prˇ´ıpadeˇ vyuzˇitı´ sluzˇby Betaface, jejichzˇ komunikace (viz Obra´zek 11) mu˚zˇe by´t v urcˇity´ch prˇ´ıpadech (naprˇ. v situaci velike´ho vytı´zˇenı´ serveru) datoveˇ na´rocˇneˇjsˇ´ı.

Obra´zek 11: Prˇenos dat v komunikaci se sluzˇbou Betaface Koncept spolupra´ce dvou sluzˇeb by byl na´sledujı´cı´. Prvnı´ sluzˇba, ktera´ by analyzovala fotografie v inicializacˇnı´ fa´zi, by byla z kategorie jednodusˇsˇ´ıch. Jejı´m u´kolem by bylo pouze rozhodnout, jestli dana´ fotografie obsahuje alesponˇ jednu detekovatelnou tva´rˇ. Poskytovala by tedy prvotnı´ filtraci fotografiı´. Za za´stupce kategorie teˇchto typu˚ sluzˇeb byla, pro na´sledujı´cı´ experiment, zvolena aplikace WaldBoost 3 ). Princip komunikace s touto sluzˇbou je uveden na Obra´zku 12. Z neˇj je za´rovenˇ patrne´, zˇe komunikace je datoveˇ nena´rocˇna´.

Obra´zek 12: Prˇenos dat v komunikaci s jednodusˇsˇ´ı sluzˇbou WaldBoost Pouze fotografie, ktere´ prosˇly inicializacˇnı´ filtracı´ by byly da´le zpracova´va´ny druhou sluzˇbou. Ta je komplexneˇjsˇ´ı a kromeˇ detekce oblicˇeju˚ obsahuje take´ algoritmy, pro jejich 3

http://cmp.felk.cvut.cz/demos/FaceDetection/

33

kategorizaci a porovna´va´nı´ (v prˇ´ıpadeˇ te´to pra´ce se jedna´ o sluzˇbu Betaface). Fotografie by byly prˇed odesla´nı´m druhe´ sluzˇbeˇ upraveny a zmensˇeny tak, aby obsahovaly pouze tva´rˇe osob, cozˇ by vedlo k vy´sˇe zmı´neˇne´ u´sporˇe prˇeneseny´ch dat u druhe´ sluzˇby. Navı´c se zamezı´ i zbytecˇne´mu prˇena´sˇenı´ mnozˇstvı´ XML dokumentu˚ v prˇ´ıpadech, kdy by analyzovana´ fotografie neobsahovala detekovatelne´ tva´rˇe vu˚bec. Fa´ze

Betaface sluzˇba

WaldBoost sluzˇba

1

XML+190= 250 kB

190 kB

2

300 B

18 kB

3

(300 ∗ n) B

N.A.

4

(15 ∗ n) kB

N.A.

Tabulka 1: Velikost prˇeneseny´ch dat v jednotlivy´ch fa´zı´ch komunikace Experiment k potvrzenı´, respektive vyvra´cenı´, vy´sˇe zmı´neˇne´ efektivity kombinace sluzˇeb, byl proveden nad typicky´mi fotografiemi. K meˇrˇenı´ prˇeneseny´ch dat byl vyuzˇit doplneˇk webove´ho prohlı´zˇecˇe Mozilla Firefox, Firebug 4 ve verzi 1.11.4. Typicka´ velikost prˇeneseny´ch dat v kazˇde´ fa´zi komunikace je uvedena v Tabulce 1 (cˇ´ısla kroku˚ v tabulce korespondujı´ s cˇ´ısly v obra´zcı´ch 11 a 12). Pro vy´pocˇet efektivity byla jako referencˇnı´ urcˇena fotografie ve forma´tu JPG, o velikosti 190 kB. Pru˚meˇrna´ hodnota redukcˇnı´ho koeficientu fotografie byla stanovena na u´rovenˇ 3 (v prˇ´ıpadeˇ nalezenı´ tva´rˇe se velikost fotografie zmensˇ´ı 3kra´t). V pru˚beˇhu testova´nı´ bylo nutno, prˇi komunikaci sluzˇbou Betaface, obvykle opakovat pozˇadavek na poskytnutı´ detailnı´ch informacı´ o tva´rˇ´ıch (v Obra´zku 11 jako bod 3, v Tabulce 1 parametr n) v rozmezı´ 1 × −5×. Pro vy´pocˇet bylo da´le pouzˇito, zˇe n = 3. Samotny´ sce´na´rˇ experimentu probı´hal na´sledovneˇ. Kazˇda´ analyzovana´ fotografie byla nejprve zpracova´na sluzˇbou WaldBoost. V prˇ´ıpadeˇ, zˇe se v nı´ nepodarˇilo najı´t ani jeden oblicˇej, fotografie da´le nebyla zpracova´va´na. V prˇ´ıpadeˇ detekova´nı´ alesponˇ jedne´ tva´rˇe, byla fotografie postoupena k u´praveˇ. V nı´ se fotografie orˇezala tak, aby obsahovala pouze detekovane´ oblicˇeje. Tohoto bylo mozˇno dosa´hnout, jelikozˇ informaci o sourˇadnicı´ch detekovany´ch tva´rˇ´ı je mozˇno ze sluzˇby WaldBoost extrahovat. Takto zmensˇena´ fotografie byla prˇeda´na sluzˇbeˇ Betaface k dalsˇ´ımu zpracova´va´nı´. Obsah fotografie

jedna sluzˇba

dveˇ sluzˇby

tva´rˇ(tva´rˇe)

486.2 kB

630.5 kB

bez tva´rˇe

486.2 kB

397.7 kB

Tabulka 2: Porovna´nı´ prˇeneseny´ch dat v prˇ´ıpadeˇ vyuzˇitı´ jedne´ a dvou sluzˇeb ´ spora prˇeneseny´ch dat, v rozsahu Tabulka 2 ukazuje samotne´ vy´sledky experimentu. U cca 18%, byla prˇi pouzˇitı´ dvou sluzˇeb proka´za´na v prˇ´ıpadech, kdy analyzovana´ fotografie neobsahuje oblicˇeje. V prˇ´ıpadech, kdy fotografie obsahuje alesponˇ jednu detekovatelnou tva´rˇ, se velikost prˇeneseny´ch dat zvy´sˇila cca o 33%. Nicme´neˇ toto navy´sˇenı´ je nutno bra´t v potaz s urcˇitou rezervou, jelikozˇ prˇ´ımo za´visı´ na stanovenı´ redukcˇnı´ho koeficientu 4

http://getfirebug.com/

34

u jednotlive´ fotografie. Jelikozˇ vsˇak u´spora prˇeneseny´ch dat nebyla tak rozsa´hla´, aby to meˇlo vliv na prˇ´ıpadnou zatı´zˇenost serveru Betaface, vyuzˇitı´ dvou sluzˇeb na mı´sto jedne´ nebylo doporucˇeno. Navı´c se prˇedpokla´da´, zˇe situacı´, kdy analyzovane´ fotografie nebudou mı´t detekovatelnou ani jednu tva´rˇ, bude minoritnı´ pocˇet.

35

6

Zdroje dat pro analy´zu a na´vrhy novy´ch spojenı´ v socia´lnı´ch sı´tı´ch

Na´sledujı´cı´ sekce se veˇnuje analy´ze mozˇny´ch zdroju˚ dat pro spra´vnou funkcˇnost nove´ho algoritmu. Prvnı´ cˇa´st pojedna´va´ o samotne´ volbeˇ vhodne´ socia´lnı´ sı´teˇ, ve ktere´ budou mozˇna´ nova´ spojenı´ uzˇivatelu˚ navrhova´na. Ve druhe´ cˇa´sti je analy´za vhodny´ch zdroju˚ fotografiı´, prostrˇednictvı´m ktery´ch budou nova´ spojenı´ navrhova´na.

6.1

Socia´lnı´ sı´teˇ

Socia´lnı´ sı´teˇ lze rozdeˇlit do dvou za´kladnı´ch kategoriı´, podle jejich prima´rnı´ funkcˇnosti. V prvnı´ kategorii jsou obsazˇeny ty socia´lnı´ sı´teˇ, ktere´ stavı´ na vza´jemne´m vytva´rˇenı´ novy´ch vztahu˚ mezi jejich uzˇivateli. Tyto vztahy jsou ve veˇtsˇineˇ prˇ´ıpadu˚ vytva´rˇeny podle rea´lny´ch vztahu˚ z beˇzˇne´ho zˇivota. Socia´lnı´ sı´teˇ z te´to kategorie zameˇrˇujı´ svou veˇtsˇinovou funkcˇnost na vylepsˇova´nı´ a zjednodusˇova´nı´ noveˇ vytva´rˇeny´ch spojenı´ uzˇivatelu˚. Veˇtsˇina uzˇivatelu˚ ma´, pokud se hovorˇ´ı o pojmu socia´lnı´ sı´t’, na mysli pra´veˇ sı´teˇ z te´to kategorie. Nejzna´meˇjsˇ´ımi za´stupci jsou Facebook, MySpace, poprˇ´ıpadeˇ i Twitter, i kdyzˇ u poslednı´ zmı´neˇne´ je velice silny´ prvek mikroblogove´ sluzˇby. Druhou kategoriı´ sı´tı´ tvorˇ´ı ty, ktere´ prima´rneˇ poskytujı´ uzˇivatelu˚m neˇjakou svou sluzˇbu nebo pouze zprostrˇedkova´vajı´ na´stroj pro vlastnı´ prezentaci uzˇivatelu˚. Takte´zˇ sice obsahujı´ prvek socia´lnı´ho spojova´nı´ jednotlivy´ch uzˇivatelu˚, ale nestavı´ na neˇm prima´rneˇ funkcˇnost svy´ch sluzˇeb. V teˇchto typech socia´lnı´ch sı´tı´ je i samotne´ vytva´rˇenı´ spojenı´ samotny´mi uzˇivateli pouzˇ´ıva´no minoritneˇ. Prˇ´ıkladem za´stupcu˚ te´to kategorie mohou by´t YouTube nebo Flickr, kterˇ´ı poskytujı´ prostor pro prezentaci samotny´ch uzˇivatelu˚ prostrˇednictvı´m jejich video cˇi obrazovy´ch deˇl. Spojova´nı´ uzˇivatelu˚, naprˇ. u YouTube je vyuzˇ´ıva´no zejme´na prostrˇednictvı´m tzv. prˇihla´sˇenı´ se k odbeˇru kana´lu konkre´tnı´ho uzˇivatele, i kdyzˇ i klasicka´ forma socia´lnı´ho spojenı´ je dostupna´. Jelikozˇ se vsˇak tato pra´ce soustrˇed’uje na vyhleda´va´nı´ mozˇny´ch novy´ch prˇ´ımy´ch spojenı´ mezi uzˇivateli, prˇi vy´beˇru vhodne´ socia´lnı´ sı´teˇ budou zohlednˇova´ni pouze za´stupci prvnı´ kategorie. Prˇi volbeˇ vhodne´ socia´lnı´ sı´teˇ je dobre´ bra´t v potaz zejme´na velikost sı´teˇ, urcˇenou pocˇtem uzˇivatelu˚. Vı´ce uzˇivatelu˚ prˇ´ımo u´meˇrneˇ znamena´ vysˇsˇ´ı pravdeˇpodobnost, zˇe konkre´tnı´ho cˇloveˇka na sı´ti algoritmus nalezne. V Tabulce 3 je uveden seznam nejveˇtsˇ´ıch socia´lnı´ch sı´tı´ (umozˇnˇujı´cı´ch vytva´rˇenı´ socia´lnı´ch vztahu˚ mezi uzˇivateli) dle databa´ze 5 , ´ daje o pocˇtu uzˇivatelu˚ jsou v tabulce zalozˇeny ktera´ vznikla, jako soucˇa´st projektu [27]. U na hodnoteˇ DAU, ktera´ urcˇuje pocˇet aktivnı´ch uzˇivatelu˚ sı´teˇ denneˇ. Jedna´ se o pomeˇrneˇ robustnı´ metodu, jak lze velikost socia´lnı´ch sı´tı´ urcˇovat, jelikozˇ pouhy´ pocˇet vytvorˇeny´ch u´cˇtu˚ v sı´tı´ch by nebyl objektivnı´. Nezohlednˇuje totizˇ zˇa´dne´ duplicitnı´ uzˇivatele, ani falesˇne´ u´cˇty. Uvedena je rovneˇzˇ podpora FOAF vy´stupu, cozˇ je urcˇity´ framework, ktery´m jsou popisova´ny osoby v sı´ti a jejich vza´jemne´ vztahy takovy´m zpu˚sobem, ktery´ umozˇnˇuje pozdeˇjsˇ´ı programove´ zpracova´nı´. I kdyzˇ byla vy´sˇe uvedena´ statistika vytvorˇena v roce 2006, lze ji sta´le pokla´dat za relevantnı´, jelikozˇ na´ru˚st novy´ch uzˇivatelu˚ je u jednotlivy´ch sı´tı´ setrvaly´ (viz Obra´zek 13). 5

http://trust.mindswap.org/cgi-bin/wbsnSearch.cgi

36

Socia´lnı´ sı´t’

Pocˇet uzˇivatelu˚ (DAU)

Zameˇrˇenı´ sı´teˇ

FOAF vy´stup

MySpace

300 000 000

spolecˇenske´/za´bava

NE

Facebook

200 000 000

spolecˇenske´/za´bava

NE

Bebo

40 000 000

spolecˇenske´/za´bava

NE

Cyworld

21 000 000

spolecˇenske´/za´bava

NE

Black Planet

18 000 000

spolecˇenske´/za´bava/seznamka

NE

LinkedIn

17 000 000

pracovnı´

NE

Vkontakte

5 000 000

spolecˇenske´/za´bava

NE

TagWorld

2 700 000

spolecˇenske´/za´bava

NE

Hyves

2 500 000

spolecˇenske´/za´bava

NE

MeetMe (myYearbook)

1 500 000

spolecˇenske´/za´bava

NE

Tabulka 3: Nejveˇtsˇ´ı socia´lnı´ sı´teˇ podle statistiky z roku 2006 Tedy v prˇ´ıpadeˇ nejveˇtsˇ´ıch sı´tı´ je na´ru˚st novy´ch uzˇivatelu˚ nejveˇtsˇ´ı, zatı´mco u mensˇ´ıch sı´tı´ je vy´razneˇ nizˇsˇ´ı.

6.2

Vy´voj pocˇtu uzˇivatelu˚ socia´lnı´ch sı´tı´

Cˇa´st jizˇ drˇ´ıve zminˇovane´ho projektu[27] se zaby´vala i vy´vojem pocˇtu uzˇivatelu˚ vybrany´ch socia´lnı´ch sı´tı´. V pru˚beˇhu trˇ´ı let byly tyto u´daje analyzova´ny a vy´sledky byly pro tuto pra´ci takte´zˇ zajı´mave´. Pocˇet socia´lnı´ch sı´tı´, ktery´m pocˇet aktivnı´ch uzˇivatelu˚ prˇekrocˇil hranici jednoho milionu se v obdobı´ od roku 2004 do roku 2006, zvy´sˇil z 18 na 41. Prˇitom ale na´ru˚st uzˇivatelu˚ znatelneˇ neovlivnil zˇebrˇ´ıcˇek nejveˇtsˇ´ıch sı´tı´. Tendence na´ru˚stu tedy zu˚stala setrvala´.

Obra´zek 13: Rozlozˇenı´ novy´ch uzˇivatelu˚ socia´lnı´ch sı´tı´

37

Toto zjisˇteˇnı´ potvrzuje, zˇe se neda´ ocˇeka´vat, zˇe by sta´vajı´cı´ mensˇ´ı cˇi strˇednı´ socia´lnı´ sı´teˇ v budoucnosti prˇerostly sve´ dnesˇnı´ veˇtsˇ´ı konkurenty. Za´rovenˇ se vsˇak z toho take´ dajı´ odvodit dva za´veˇry, ty´kajı´cı´ se nejveˇtsˇ´ıch socia´lnı´ch sı´tı´. Bud’ majı´ tyto sı´teˇ velice dobrou vlastnı´ propagaci a dovedou si efektivneˇ zı´ska´vat sta´le nove´ uzˇivatele nebo se vztahy mezi uzˇivateli teˇchto sı´tı´ zakla´dajı´ ve veˇtsˇineˇ na rea´lny´ch vztazı´ch z beˇzˇne´ho zˇivota. Druhy´ za´veˇr by byl vysveˇtlitelny´ na´sledujı´cı´m prˇ´ıkladem. Pokud ma´ osoba v rea´lne´m zˇivoteˇ okruh prˇa´tel, kterˇ´ı jsou uzˇivateli urcˇite´ socia´lnı´ sı´teˇ, ale samotna´ osoba zatı´m ne, lze ocˇeka´vat, zˇe osobeˇ bude tato socia´lnı´ sı´t’doporucˇova´na.

6.3

Vy´beˇr konkre´tnı´ socia´lnı´ sı´teˇ

S ohledem na informace uvedene´ v prˇedchozı´ch kapitola´ch byl sestaven seznam nejvhodneˇjsˇ´ıch socia´lnı´ch sı´tı´, ze ktery´ch bylo nutno vybrat jedinou. V na´sledujı´cı´m textu jsou tyto sı´teˇ strucˇneˇ zhodnoceny. LinkedIn Jedna´ se o socia´lnı´ sı´t’ zameˇrˇenou na profesnı´ zˇivot jejich uzˇivatelu˚. Dı´ky tomuto faktu obsahuje minima´lnı´ pocˇet tzv. fake u´cˇtu˚. Nova´ spojenı´ se veˇtsˇinou realizujı´ za pomoci spolecˇny´ch zameˇstna´nı´ nebo profesnı´ch specializacı´. V jednotlivy´ch u´cˇtech je take´ mozˇno nastavit si situace, za ktery´ch je konkre´tnı´ho uzˇivatele vhodne´ kontaktovat (naprˇ. prˇi nabı´dce zameˇstna´nı´ cˇi prosbou o odbornou pomoc). I kdyzˇ se jedna´ o socia´lnı´ sı´t’ rozsˇ´ırˇenou, ktera´ obsahuje dostatecˇny´ pocˇet uzˇivatelu˚, pro u´cˇely te´to pra´ce nenı´ idea´lnı´, jelikozˇ je zameˇrˇena na u´zkou cı´lovou skupinu. Idea´lnı´ by naopak bylo jejı´ vyuzˇitı´ v prˇ´ıpadeˇ, kdyby bylo prˇistoupeno k vyuzˇ´ıtı´ analy´zy novy´ch spojenı´, v za´vislosti na u´cˇasti na konferencı´ch uzˇivatelu˚, jak je rozvedeno v Kapitole 3.2. Facebook Jedna z nejveˇtsˇ´ıch socia´lnı´ch sı´tı´. Dı´ky sve´ rozsˇ´ırˇenosti poskytuje dostatecˇny´ pocˇet uzˇivatelu˚, nad ktery´mi se dajı´ nale´zt konkre´tnı´ osoby. Oproti sı´ti LinkedIn vsˇak pomeˇrneˇ velke´ mnozˇstvı´ u´cˇtu˚ uzˇivatelu˚ obsahuje v profilovy´ch obra´zcı´ch fotografie, na ktery´ch nenı´ dobrˇe identifikovatelny´ oblicˇej. Dı´ky sve´ rozsˇ´ırˇenosti za´rovenˇ obsahuje take´ mnozˇstvı´ fake u´cˇtu˚ nebo u´cˇtu˚, ktere´ nejsou vhodne´ pro zpracova´nı´ nasˇim algoritmem (naprˇ. profil rea´lne´ho cˇloveˇka, ovsˇem s pozmeˇneˇny´m jme´nem nebo jme´nem zkomoleny´m). ResearchGate Oproti dveˇma jizˇ zmı´neˇny´m sı´tı´m, se do fina´lnı´ho seznamu dostala i socia´lnı´ sı´t’ ResearchGate 6 . Jedna´ se, obdobneˇ jako u LinkedIn, o sı´t’ u´zce zameˇrˇenou na urcˇitou profesnı´ skupinu akademicky´ch pracovnı´ku˚ a veˇdcu˚. Vyuzˇ´ıva´ ovsˇem neˇktere´, zajı´mave´ prvky analy´zy uzˇivatelu˚, naprˇ´ıklad jejich kategorizaci podle institucı´, ve ktery´ch pracujı´. Tyto techniky by se daly v budoucnu vyuzˇ´ıt a usnadnit prostrˇednictvı´m nich prˇ´ıpadne´ prvotnı´ filtrace novy´ch na´vrhu˚ spojenı´. Proti vyuzˇitı´ byla ovsˇem stejna´ fakta, jako v jizˇ zmı´neˇne´ sı´ti LinkedIn.

6

http://www.researchgate.net/

38

Z vy´sˇe uvedeny´ch informacı´ vyply´va´, zˇe pro u´cˇely te´to pra´ce byla vybra´na socia´lnı´ sı´t’ Facebook. Jedna´ se podle me´ho na´zoru o nejvhodneˇjsˇ´ı na´stroj, v neˇmzˇ lze nejle´pe nale´zt konkre´tnı´ osoby pro na´vrhy novy´ch spojenı´. Za´rovenˇ obliba te´to sı´teˇ je na velice velke´ u´rovni, cozˇ nahra´va´ i perspektivnı´ vyuzˇitelnosti nove´ aplikace. Pro praktickou implementaci je rovneˇzˇ du˚lezˇite´, zˇe prˇ´ıstup k socia´lnı´ sı´ti je dobrˇe zdokumentova´n v oficia´lnı´m API a prˇ´ıpadne´ rˇesˇenı´ proble´mu˚ je sna´ze rˇesˇitelne´ s vyuzˇitı´m oficia´lnı´ch blogu˚ vy´voja´rˇu˚.

6.4

Vy´beˇr vhodne´ho zdroje fotografiı´ pro analy´zu

V dalsˇ´ım kroku je nutne´ vybrat vhodnou webovou sluzˇbu, ze ktere´ bude novy´ algoritmus zı´ska´vat fotografie s osobami pro pozdeˇjsˇ´ı na´vrhy novy´ch spojenı´ uvnitrˇ sı´teˇ Facebook. Opeˇt byly zvoleny z me´ho hlediska nejperspektivneˇjsˇ´ı sluzˇby, ze ktery´ch byla nakonec vybra´na fina´lnı´. Pro jednodusˇsˇ´ı volbu byly sestaveny steˇzˇejnı´ krite´ria, ktere´ by vy´sledna´ sluzˇba meˇla splnˇovat. 1. Sluzˇba by meˇla obsahovat mozˇnost editace za´kladnı´ch informacı´ u fotografie, tedy nejen umozˇnit vlozˇenı´ a editaci komenta´rˇu˚, ale take´ pra´ci s tagy poprˇ´ıpadeˇ mozˇnost prˇ´ımo oznacˇovat ve fotografiı´ch osoby. 2. Meˇlo by se jednat o jednu ze zna´my´ch a vyuzˇ´ıvany´ch sluzˇeb, ktera´ je veˇtsˇineˇ beˇzˇny´ch uzˇivatelu˚ zna´ma´, jednak protozˇe funkcˇnost a podpora takovy´ch sluzˇeb je kvalitneˇjsˇ´ı, ale take´ je veˇtsˇ´ı pravdeˇpodobnost toho, zˇe potenciona´lnı´ uzˇivatel nove´ sluzˇby, jizˇ bude mı´t na sluzˇbeˇ u´cˇet. 3. Sluzˇba by nemeˇla vyzˇadovat instalaci loka´lnı´ch aplikacı´ nutny´ch k jejı´mu pouzˇ´ıva´nı´. 4. Volitelnou vlastnostı´, by meˇla by´t snadna´ mozˇnost implementovat komunikacˇnı´ vrstvu mezi sluzˇbou a novou aplikacı´, poprˇ´ıpadeˇ dostupnost specificky´ch knihoven, ktere´ by tato aplikace mohla vyuzˇ´ıvat. Nı´zˇe je uveden seznam aplikacı´, ze ktery´ch byl proveden vy´beˇr nejvhodneˇjsˇ´ı. Google Picasa Web Albums Sluzˇba, ktera´ je u´zce sva´zana´ s aplikacı´ Google Picasa. Pro vyuzˇ´ıva´nı´ ale nenı´ nutno instalovat samotne´ho desktopove´ho klienta. Jelikozˇ se jedna´ o sluzˇbu Google, je spojena i s dalsˇ´ımi jeho produkty a prˇihlasˇova´nı´ do sluzˇby je realizova´no pomocı´ u´cˇtu Google, tedy stejne´ho jako naprˇ. do socia´lnı´ sı´teˇ Google+. Obsahuje mozˇnost vytva´rˇet a editovat tagy ve fotografiı´ch, avsˇak pra´ce s nimi nenı´ tak idea´lnı´ jako byla v jiny´ch prˇ´ıpadech (zejme´na v porovna´nı´ s Flickr) Photobucket Tato sluzˇba nabı´zı´ prostor pro sdı´lenı´ nejen fotografiı´, ale take´ video souboru˚. Pra´ce s fotografiemi je zpracova´na dobrˇe, v kazˇde´ je mozˇno prˇida´vat i editovat tagy, ale jsou zde restrikce (kazˇda´ fotografie mu˚zˇe obsahovat maxima´lneˇ 20 tagu˚ a i celkovy´ pocˇet tagu˚ na jeden u´cˇet je omezen na 3500). Prˇihla´sˇenı´ se do sluzˇby je, kromeˇ zalozˇenı´ nove´ho u´cˇtu ve sluzˇbeˇ, umozˇneˇno i prostrˇednictvı´m socia´lnı´ch sı´tı´ Facebook nebo Twitter. Z du˚vodu male´ rozsˇ´ırˇenosti sluzˇby u na´s je ale nevhodna´ k dalsˇ´ımu vyuzˇitı´.

39

Flickr Velice rozsˇ´ırˇena´ sluzˇba pro sdı´lenı´ fotografiı´. Prˇihla´sˇenı´ se do sluzˇby je umozˇneˇno prostrˇednictvı´m socia´lnı´ch sı´tı´ Facebook nebo Google+, poprˇ´ıpadeˇ standardnı´ metodou registrace se u Flickr (prostrˇednictvı´m sdruzˇene´ho Yahoo! u´cˇtu). I u te´to sluzˇby je mozˇno prˇida´vat tagy k jednotlivy´m fotografiı´m. Poskytuje i mozˇnost oznacˇovat urcˇite´ osoby na fotce, ovsˇem tyto musı´ by´t take´ uzˇivateli Flickr (nenı´ mozˇno prˇidat pouze textovou informaci o osobeˇ, osoba oznacˇena´ na fotce musı´ by´t spa´rova´na s id uzˇivatele Flickr). Komunikace s externı´mi aplikacemi je mozˇna´ i s vyuzˇitı´m externı´ch knihoven. 500PX Stejneˇ tak, jako vy´sˇe uvedene´ sluzˇby, i tato poskytuje mozˇnost prˇipojovat k fotografiı´m dodatecˇne´ informace. I do te´to webove´ sluzˇby je mozˇno se prˇihla´sit pomocı´ externı´ch u´cˇtu˚ Facebook, Twitter nebo Google. Sluzˇba se ovsˇem zameˇrˇuje zejme´na na profesiona´lnı´ nebo umeˇlecke´ fotografie, ktere´ lze prostrˇednictvı´m ni i proda´vat, takzˇe nenı´ mozˇno prˇedpokla´dat veˇtsˇ´ı za´jem beˇzˇny´ch uzˇivatelu˚. Jako nejvhodneˇjsˇ´ı byla nakonec zvolena sluzˇba Flickr. Pro u´cˇely te´to pra´ce vsˇak bude nutno nahradit vyuzˇitı´ jejı´ho oznacˇova´nı´ prˇa´tel jiny´m zpu˚sobem, protozˇe je pozˇadova´no, aby oznacˇova´nı´ probı´halo neza´visle na tom, jestli je konkre´tnı´ osoba take´ uzˇivatelem sı´teˇ Flickr cˇi nikoliv. Jako na´hrada byl vyuzˇit objekt samotne´ho tagu (viz Obra´zek 14) u kazˇde´ fotografie, do ktere´ho se bude ukla´dat jme´no s prˇ´ıjmenı´m konkre´tnı´ osoby, kterou budou uzˇivatele´ aplikace chtı´t na fotografii oznacˇit.

Obra´zek 14: Modifikovany´ zpu˚sob oznacˇova´nı´ prˇa´tel na sı´ti Flickr

40

41

7

Vlastnı´ na´vrh prototypu algoritmu

V te´to kapitole je popsa´n samotny´ na´vrh a zpu˚sob implementace experimenta´lnı´ho algoritmu pro na´vrhy novy´ch spojenı´ v socia´lnı´ sı´ti Facebook. Nejprve je teoreticky popsa´na beˇzˇna´ situace, ktera´ prˇi rˇesˇenı´ proble´mu nasta´va´ a jsou stanoveny krite´ria, za ktery´ch je mozˇno na´vrh novy´ch spojenı´ poskytovat. V dalsˇ´ıch cˇa´stech jsou popsa´ny proble´my, se ktery´mi jsem se beˇhem samotne´ implementace setkal a rˇesˇenı´, ktera´ jsme zvolil. Jako technologie k implementaci algoritmu byl zvolen programovacı´ jazyk C# s .NET Framework. Du˚vod volby te´to technologie byl zejme´na ten, zˇe veˇtsˇ´ı cˇa´st funkcˇnosti je realizova´na za pomoci komunikace s externı´mi sluzˇbami prostrˇednictvı´m internetu, cozˇ se v .NET Framework rˇesˇ´ı velice komfortneˇ.

7.1

Princip vyhleda´va´nı´ novy´ch spojenı´

Protozˇe socia´lnı´ sı´teˇ obsahujı´ stovky milio´nu˚ uzˇivatelu˚, musı´ by´t nalezen sofistikovany´ zpu˚sob, jaky´m je mozˇne´ tuto velikou mnozˇinu prvku˚ zmensˇit. Aby toto bylo mozˇne´ realizovat, je nutne´ nejprve prozkoumat standardnı´ sce´na´rˇ, ktery´ se prˇi rˇesˇenı´ proble´mu vyskytuje. Jelikozˇ jizˇ drˇ´ıve v textu bylo uvedeno, zˇe algoritmus bude pracovat se socia´lnı´ sı´tı´ Facebook, zde jizˇ vsˇechny situace budou popisova´ny na te´to sı´ti. Standardnı´ fotografie, ktera´ prˇijde na vstup nove´ho algoritmu je ilustrova´na na Obra´zku 15. Jedna´ se o fotografii, sta´hnutou ze sı´teˇ Flickr, ktera´ obsahuje tva´rˇe minima´lneˇ dvou osob, z nichzˇ jedna je samotny´ uzˇivatel nove´ sluzˇby. Tento pozˇadavek byl nastaven z du˚vodu˚ zamezenı´ zkouma´nı´ fotografiı´ osob, ktere´ by byly na fotce bez konkre´tnı´ho uzˇivatele. U teˇchto by totizˇ nebylo mozˇno rozhodnout, jestli jsou s uzˇivatelem v rea´lne´m vztahu. Detekce uzˇivatele A je mozˇna´, protozˇe aplikaci poskytl pra´va k analy´ze sve´ho profilu na socia´lnı´ sı´ti, a to vcˇetneˇ prˇ´ıstupu ke sve´ profilove´ fotografii. Da´le je umozˇneˇn take´ prˇ´ıstup k seznamu vsˇech jeho sta´vajı´cı´ch prˇa´tel v socia´lnı´ sı´ti. Ke kazˇde´mu prˇ´ıteli je take´ mozˇno vyzˇa´dat si profilovou fotografii. Dalsˇ´ım krokem je postupna´ detekce vsˇech ostatnı´ch tva´rˇ´ı ve fotografii. Pote´ je tva´rˇ osoby B (poprˇ´ıpadeˇ dalsˇ´ıch Bi jestli jsou na fotografii zachyceny) porovna´va´na z tva´rˇemi sta´vajı´cı´ch prˇa´tel uzˇivatele A. V prˇ´ıpadeˇ, zˇe je nalezena shoda tva´rˇ´ı nezna´me´ osoby a sta´vajı´cı´ho prˇ´ıtele, algoritmus mu˚zˇe informaci o nalezene´ osobeˇ prˇipojit k analyzovane´ fotografii. V situaci, kdy nenı´ ani jeden prˇ´ıtel uzˇivatele A oznacˇen jako shodna s osobou B respektive Bi , je nutne´ se pokusit nezna´mou osobu vyhledat na cele´ sı´ti Facebook. Protozˇe vsˇak nenı´ mozˇne´ procha´zet sekvencˇneˇ vsˇechny uzˇivatelske´ u´cˇtu v socia´lnı´ sı´ti, je nutne´ mnozˇinu vsˇech uzˇivatelu˚ redukovat na takovou velikost, ve ktere´ jizˇ analy´za vsˇech jejich prvku˚ bude mozˇna´. Prvnı´ mozˇnostı´ k te´to redukci, je vyuzˇitı´ informacı´, ktere´ lze z tva´rˇe nezna´me´ osoby extrahovat. Teˇmito mohou by´t naprˇ´ıklad veˇk, pohlavı´ cˇi etnicka´ skupina (tyto informace Betaface sluzˇba poskytuje viz Obra´zek 9). Spolehlivost teˇchto extrahovany´ch informacı´ vsˇak v soucˇasne´ situaci sta´le jesˇteˇ nenı´ uspokojiva´. Navı´c ani v profilovy´ch u´cˇtech uzˇivatelu˚ sı´teˇ Facebook tyto informace nemusı´ by´t vu˚bec vyplneˇny. Je tedy nutne´ nale´zt jiny´ zpu˚sob redukce mnozˇiny. Vy´razneˇ omezit pocˇa´tecˇnı´ mnozˇinu je mozˇno tak, zˇe budou filtrova´na pouze konkre´tnı´ jme´na uzˇivatelu˚. Tı´mto je zı´ska´na mnozˇina uzˇivatelsky´ch u´cˇtu˚ Facebooku, ve ktere´ jizˇ je

42

Obra´zek 15: Standardnı´ fotografie pro zkouma´nı´ mozˇny´ch novy´ch spojenı´ uzˇivatele umozˇneˇno konkre´tnı´ prvky porovna´vat s nezna´my´m cˇloveˇkem B. Tento za´sah ovsˇem zmeˇnı´ i pocˇa´tecˇnı´ pozˇadavky na vstupnı´ fotografie. Novy´ algoritmus (v prˇ´ıpadeˇ zˇe nebude nalezena shoda detekovany´ch osob s prˇa´teli uzˇivatele A) bude zpracova´vat pouze fotografie, ktere´ ve sve´m tagu obsahujı´ jme´na osob, ktere´ se na nich vyskytujı´.

Obra´zek 16: Zna´zorneˇnı´ mnozˇiny vsˇech uzˇivatelu˚ Facebook a redukovane´ mnozˇiny pro nalezenı´ nove´ho kontaktu Pokud jsou vy´sˇe uvedena´ omezenı´ na mnozˇinu aplikova´na, je mozˇno rozhodnout, zda nezna´ma´ osoba B je prˇ´ıtomna na socia´lnı´ sı´ti, poprˇ´ıpadeˇ rovnou navrhnout nove´ spojenı´ mezı´ nı´ a uzˇivatelem A. Standardneˇ mohou nastat dveˇ situace, kde se osoba B mu˚zˇe nacha´zet (viz Obra´zek 16). Pokud je nalezena osoba na socia´lnı´ sı´ti, u ktere´ je detekova´na shoda tva´rˇe s osobou B, pak platı´, zˇe B = x. V opacˇne´m prˇ´ıpadeˇ bude platit B = z. Situace, ve ktere´ bude B = y, pak mu˚zˇe nastat v prˇ´ıpadeˇ, zˇe vy´sˇe uvedene´ restrikce byly aplikova´ny chybneˇ. Naprˇ´ıklad u fotografie, bylo jme´no osoby B uvedeno v neprˇesne´m nebo zkomolene´m forma´tu.

43

Obra´zek 17: Struktura vlastnı´ trˇ´ıdy BetafaceImage

7.2

Komunikace s externı´mi sluzˇbami

V na´sledujı´cı´ kapitole jsou vysveˇtleny principy komunikacı´ se sluzˇbami a socia´lnı´mi sı´teˇmi, ktere´ algoritmus vyuzˇ´ıva´. Ve veˇtsˇineˇ prˇ´ıpadu˚ bylo zvoleno, zˇe komunikacˇnı´ vrstva bude implementova´na uvnitrˇ nove´ aplikace a nebude vyuzˇ´ıvat externı´ch knihoven. Tato metoda byla zvolena, protozˇe tak umozˇnˇuje veˇtsˇ´ı kontrolu nad jednotlivy´mi fa´zemi komunikace a ve veˇtsˇineˇ prˇ´ıpadu˚ ma´ take´ za na´sledek mensˇ´ı prˇenesena´ data, jelikozˇ jsou ze sluzˇby zı´ska´va´ny pouze nezbytneˇ nutne´ informace. Jedina´ vy´jimka nastala prˇi komunikaci se sı´tı´ Flickr, kde byla pouzˇita externı´ knihovna, protozˇe v prˇ´ıpadeˇ komunikace s touto sluzˇbou bylo nutne´ se autentizovat specia´lnı´mi zpu˚soby, ktere´ zmı´neˇna´ knihovna implementovala velice efektivneˇ. Komunikace se sluzˇbou Betaface Za´kladnı´ princip komunikace, ktery´ je zalozˇen na odesı´la´nı´ a prˇ´ıjı´ma´nı´ XML dokumentu˚ je jizˇ uveden v Kapitole 5.3.2. Autorˇi Betaface na svy´ch oficia´lnı´ch stra´nka´ch poskytujı´ i knihovnu pro .NET Framework, ktera´ pokry´va´ vsˇechny funkce, ktere´ sluzˇba nabı´zı´. Jejı´ nevy´hodou je ale prˇ´ılisˇna´ komplexnost prˇi vola´nı´ za´kladnı´ch funkcı´ (je nutne´ prˇena´sˇet vı´ce dat nezˇ aplikace potrˇebuje). Z tohoto du˚vodu bylo rozhodnuto implementova´nı´ vlastnı´ komunikacˇnı´ vrstvy.

44

Prˇi vytva´rˇenı´ objektu typu BetafaceImage (struktura trˇ´ıdy je uvedena v Obra´zku 17), je mu pouze nutne´ prˇedat informace o umı´steˇnı´ fotografie tak, aby trˇ´ıda byla schopna vytvorˇit interneˇ objekt typu Image (standardnı´ trˇ´ıda). BetafaceImage umı´ vytva´rˇet Image objekty jak z loka´lnı´ch obrazovy´ch souboru˚, tak i z fotografiı´, ktere´ jsou umı´steˇny online (prostrˇednictvı´m datove´ho streamu). Po te´to inicializacˇnı´ fa´zi jizˇ je uvnitrˇ trˇ´ıdy nutno pouze obra´zek zako´dovat do forma´tu base64Binary, cozˇ je provedeno tak, jak ukazuje Vy´pis 4. Trˇ´ıda BetafaceImage ma´ v sobeˇ take´ prˇ´ımo prˇipraveny promeˇnne´ pro ukla´da´nı´ jmen osob, ktere´ se na fotografii vyskytujı´ i jme´na detekovany´ch a rozeznany´ch tva´rˇ´ı, ktere´ se budou naplnˇovat azˇ v dalsˇ´ıch fa´zı´ch analy´zy. private string convertImage(Stream s=null) { Image im; if (s!=null) { im=Image.FromStream(s); } else { im=Image.FromFile(imPath); LoadTagsFromImage(im); } using (MemoryStream ms = new MemoryStream()) { // Convert Image to byte[] im.Save(ms, ImageFormat.Jpeg); byte[] imageBytes = ms.ToArray(); // Convert byte[] to Base64 String string base64String = Convert.ToBase64String(imageBytes); return base64String; } }

Vy´pis 4: Prˇevedenı´ obrazovy´ch dat do textove´ho rˇeteˇzce ve forma´tu base64Binary Komunikace se socia´lnı´ sı´tı´ Facebook Facebook na svy´ch oficia´lnı´ch stra´nka´ch pro vy´voja´rˇe poskytuje informace o zpu˚sobech, jak prˇistupovat k datu˚m uzˇivatelu˚ nebo skupin, ktere´ se na te´to socia´lnı´ sı´ti vyskytujı´. Vsˇechny dotazy lze posı´lat na servery klasicky´mi metodami GET a POST a pro zpeˇtne´ zı´ska´va´nı´ dat ze serveru˚ lze vyuzˇ´ıt i zabezpecˇene´ spojenı´ prostrˇednictvı´m protokolu HTTPS se sˇifrova´nı´m SSL (viz Tabulka 4). Veˇtsˇina dat je ze serveru˚ odesı´la´na ve forma´tu JSON (viz Vy´pis 5). Facebook kazˇde´ho uzˇivatele nebo skupinu reprezentuje jako objekt s jedinecˇny´m identifika´torem, cozˇ zjednodusˇuje procha´zenı´ struktur mnoho jednotlivcu˚, naprˇ´ıklad prˇi analy´ze vsˇech prˇa´tel konkre´tnı´ho cˇloveˇka. K za´kladnı´m informacı´m o uzˇivateli je mozˇno prˇistupovat pomocı´ zmı´neˇne´ho identifika´toru, poprˇ´ıpadeˇ pomocı´ jeho jme´na, cozˇ vsˇak v prˇ´ıpadeˇ vı´ce uzˇivatelu˚ se stejny´m jme´nem nenı´ spolehlive´.

45

{ ” id ” : ”100003085620908”, ”name”: ”Jakub Stonawski”, ”first name” : ”Jakub”, ”last name”: ”Stonawski”, ” link ” : ” http :// www.facebook.com/jakub.stonawski.7”, ”username”: ”jakub.stonawski.7”, ”gender”: ”male”, ” locale ” : ”cs CZ” }

Vy´pis 5: Informace poslane´ ze serveru jako odpoveˇd’ na dotaz o podrobnostech uzˇivatele K detailneˇjsˇ´ım informacı´m je mozˇny´ prˇ´ıstup pouze po souhlasu konkre´tnı´ho uzˇivatele. Tento souhlas lze zı´skat, pokud se dany´ uzˇivatel prˇihla´sı´ vu˚cˇi serveru Facebooku a aplikaci pote´ prˇeda´ specificky´ token, dı´ky neˇmuzˇ si lze tyto detailneˇjsˇ´ı informace ze serveru˚ vyzˇa´dat. Tento token nenı´ pouze jeden pro kazˇde´ho uzˇivatele, ale generuje se vzˇdy v za´vislosti na tom, kolik a jaky´ druh informacı´ chceme od dane´ho uzˇivatele zı´skat. Ten to samozrˇejmeˇ v za´vislosti na situaci nemusı´ akceptovat a token aplikaci neposkytne.

Obra´zek 18: Na´stin algoritmu analyzujı´cı´ sta´vajı´cı´ prˇa´tele na socia´lnı´ sı´ti Pru˚beˇh analy´zy dosavadnı´ch prˇa´tel je uveden na Obra´zku 18. Pote´ co je od konkre´tnı´ho uzˇivatele zı´ska´n seznam jeho prˇa´tel, je u kazˇde´ho prˇ´ıtele nejprve nutne´ podle jeho identifika´toru zazˇa´dat o profilovy´ obra´zek. Pak na´sleduje spa´rova´nı´ profilove´ho obra´zku s daty konkre´tnı´ osoby a paklizˇe je rozezna´n oblicˇej, cely´ tento za´znam je ulozˇen pro

46

pozdeˇjsˇ´ı zpracova´nı´. Tı´mto zpu˚sobem jsou ze vsˇech prˇa´tel uzˇivatele vyfiltrova´ni ti, ktere´ nelze analyzovat podle tva´rˇe. Je du˚lezˇite´ poznamenat, zˇe mu˚zˇe nastat prˇ´ıpad, kdy v odpoveˇdi na pozˇadavek o seznam vsˇech prˇa´tel na socia´lnı´ sı´ti servery Facebooku nevra´tı´ vsˇechny prˇa´tele. Jestli ma´ konkre´tnı´ uzˇivatel, ktery´ by meˇl by´t v seznamu prˇa´tel nastaveno zabezpecˇenı´ soukromı´ na nejvysˇsˇ´ı u´rovenˇ, nenı´ mozˇno zjisˇt’ovat, cˇ´ı je tento konkre´tnı´ uzˇivatel prˇ´ıtel. Tato skutecˇnost nejde zˇa´dny´m zpu˚sobem obejı´t a je nutno ji tedy bra´t v potaz prˇi analy´ze vy´sledku˚ nasˇeho experimenta´lnı´ho algoritmu. Forma´t URL adresy

Vy´znam pozˇadavku

token

https://graph.facebook.com/ID

za´kladnı´ info o uzˇivateli

NE

https://graph.facebook.com/ID/picture?type=large

profilova´ fotka uzˇivatele

NE

https://developers.facebook.com/tools/explorer https://graph.facebook.com/ID/friends?accesstoken=TOKEN

zı´ska´nı´ tokenu

NE

seznam prˇa´tel uzˇivatele

ANO

Tabulka 4: Prˇ´ıklady URL adres pro vybrane´ pozˇadavky na servery Facebook

Komunikace se sı´tı´ Flickr U te´to jedine´ sluzˇby je vyuzˇita externı´ knihovna pro komunikaci, ktera´ je navrzˇena pro .NET framework 7 . Kazˇda´ externı´ aplikace trˇetı´ strany, ktera´ chce komunikovat se sı´tı´ Flickr, musı´ by´t navı´c zaregistrova´na na samotne´ sı´ti (viz Obra´zek 19). Po registraci je prˇideˇlen aplikaci jedinecˇny´ identifika´tor a tajny´ klı´cˇ, pomocı´ nichzˇ da´le tato aplikace komunikuje s Flickr sı´tı´.

Obra´zek 19: Registrace nove´ aplikace na sı´ti Flickr Flickr nepodporuje mozˇnost automaticke´ho prˇihlasˇova´nı´ uzˇivatele z aplikacı´ trˇetı´ch stran. V nove´ aplikaci tedy nenı´ mozˇne´, aby uzˇivatel pouze jednou vyplnil prˇihlasˇovacı´ 7

http://flickrnet.codeplex.com/releases/view/92730

47

u´daje do sluzˇby a tyto byly da´le vyuzˇ´ıva´ny automaticky. Je nutne´, aby se prˇi kazˇde´m nove´m prˇ´ıstupu na sı´t’, prˇi ktere´ je vyzˇadova´va´no prˇihla´sˇenı´, uzˇivatel znovu autorizoval prostrˇednictvı´m webove´ho rozhranı´ (viz Obra´zek 21). V nove´ aplikaci je k tomuto u´cˇelu vyuzˇita trˇ´ıda WebBrowser, s jejichzˇ vyuzˇitı´m je zobrazena prˇ´ıslusˇna´ prˇihlasˇovacı´ stra´nka. Tı´mto je zamezeno otevı´ra´nı´ externı´ho webove´ho prohlı´zˇecˇe, ktery´ by jinak bylo nutno pouzˇ´ıt.

Obra´zek 20: Trˇ´ıda FlickrUser reprezentujı´cı´ konkre´tnı´ho uzˇivatele sluzˇby Flickr Zpeˇtne´ zı´ska´nı´ informace, jestli bylo prˇihla´sˇenı´ uzˇivatele u´speˇsˇne´ je vyrˇesˇeno zpu˚sobem, ktery´ zobrazuje Vy´pis 6. Formula´rˇ, obsahujı´cı´ WebBrowser obsahuje i uda´lost, ktera´ je vyvola´va´na prˇi uzavrˇenı´ webove´ho prohlı´zˇecˇe. K te´to je prˇihla´sˇena metoda wvAuthorizationCompleted, ve ktere´ je vyvola´va´na kontrola, jestli ma´ aplikace opravdu povolenı´ k prˇ´ıstupu k datu˚m uzˇivatele. // WebView is a form that incudes WebBrowser object for displaying web pages ... WebView wv = new WebView(); wv.Url = user. url ; wv.AuthorizationCompleted += wvAuthorizationCompleted; wv.ShowDialog(); ... void wv AuthorizationCompleted(object sender, EventArgs e) { user.GetPermission(); FillData () ; }

Vy´pis 6: Zpu˚sob rˇesˇenı´ prˇihlasˇova´nı´ uzˇivatele k sı´ti Flickr Pro samotnou pra´ci se stazˇeny´mi daty Flickr uzˇivatele, byla navı´c implementova´na i vlastnı´ trˇ´ıda(Obr. 20), obsahujı´cı´ obsluzˇne´ metody, ktere´ data z Flickr upravujı´ do podoby, ve ktere´ mohou by´t poskytova´na sluzˇbeˇ Betaface. V pru˚beˇhu komunikace s Flickr bylo

48

nutno rˇesˇit pouze jeden proble´m, ty´kajı´cı´ se pra´ce s tagy fotografiı´. Knihovna ke komunikaci, totizˇ pro efektivneˇjsˇ´ı zpracova´va´nı´, upravuje tag objekty Flickr tak, zˇe v ko´du jsou jizˇ dostupne´ pouze jako textove´ informace. Jsou z nich navı´c take´ orˇeza´ny vsˇechny specia´lnı´ znaky a mezery. Se specia´lnı´mi znaky proble´m nebyl, ovsˇem po odstraneˇnı´ mezer jizˇ nebylo mozˇno rozlisˇit, mezi jme´nem a prˇ´ıjmenı´m osob. Zava´deˇt kvu˚li tomuto specia´lnı´ forma´t, ktery´m by muselo by´t jme´no napsa´no (naprˇ. s podtrzˇ´ıtkem nebo pomlcˇkou), by nebylo efektivnı´.

Obra´zek 21: Odsouhlasenı´ prˇ´ıstupu aplikace k datu˚m uzˇivatele Mı´sto toho bylo zvoleno na´sledujı´cı´ rˇesˇenı´. Prˇ´ıstup k origina´lnı´mu, nepozmeˇneˇne´mu objektu tag, byl mozˇny´ prˇi vola´nı´ metody, ktera´ zı´ska´vala dodatecˇne´ informace o fotografii. Tato metoda ovsˇem vyzˇaduje autentizaci uzˇivatele, takzˇe je ji nutno volat azˇ po tomto kroku. Po zavola´nı´, metoda vracı´ objekt tag, kde kazˇdy´ jednotlivy´ za´znam je reprezentova´n jako samostatny´ prvek, ktery´ obsahuje text ve sve´ origina´lnı´ podobeˇ tak, jak je ulozˇen na serveru Flickr. Aplikace tyto informace zpracuje a ulozˇ´ı je do promeˇnne´ description, ktera´ je jizˇ pro pozdeˇjsˇ´ı zpracova´nı´ dostupna´ i bez opeˇtovne´ autorizace uzˇivatele (podrobneˇjsˇ´ı popis nabı´zı´ Vy´pis 7). Prˇitom nenı´ porusˇeno zˇa´dne´ bezpecˇnostnı´ opatrˇenı´, jelikozˇ informace v tag objektech jsou take´ dostupne´ bez autorizace, jen v nevyhovujı´cı´m forma´tu. public List GetSelectedImages(List<string> imagesIDs){ List results = new List(); foreach (Photo p in this.allPhotosFromPhotoStream){ if (imagesIDs.Contains(p.PhotoId)){ p.Description=GetNamesFromTag(flickr.PhotosGetInfo(p.PhotoId,p.Secret)); results .Add(p); } if ( results .Count == imagesIDs.Count) break; } return results ;}

Vy´pis 7: Princip vyrˇesˇenı´ proble´mu s chybneˇ forma´tovany´mi tagy fotografiı´

49

7.3

Analy´za sta´vajı´cı´ch spojenı´ v socia´lnı´ sı´ti

Pote´, co byl v prˇedchozı´ch kapitola´ch nastı´neˇn zpu˚sob komunikace se vsˇemi sluzˇbami, je jizˇ mozˇne´ popsat samotny´ zpu˚sob, jaky´m je provedena analy´za sta´vajı´cı´ch spojenı´ mezi uzˇivateli socia´lnı´ sı´teˇ Facebook. Za´kladnı´ princip tohoto algoritmu je uveden na Obra´zku 22. V prvnı´ fa´zi, pote´ co se uzˇivatel autorizuje vu˚cˇi socia´lnı´ sı´ti, je cı´lem sta´hnout informace o vsˇech prˇa´telı´ch (respektive vsˇech dostupny´ch viz Kapitola 7.2) konkre´tnı´ho uzˇivatele, a ty pote´ spa´rovat s jejich profilovy´mi fotografiemi. Pote´ je na tento prvotnı´ seznam aplikova´n filtr, ktery´ ma´ vyrˇadit ty za´znamy, u ktery´ch nenı´ mozˇno analyzovat tva´rˇe. Tento filtr je proveden prostrˇednictvı´m vyuzˇitı´ Betaface sluzˇeb. Analyzovane´ profilove´ fotografie nenı´ nutno stahovat fyzicky, ale stacˇ´ı na neˇ algoritmu poskytnout URL odkaz.

Obra´zek 22: Algoritmus pro zpracova´nı´ sta´vajı´cı´ch prˇa´tel na socia´lnı´ sı´ti Vy´sledkem te´to analy´zy je vytvorˇenı´ databa´ze existujı´cı´ch prˇa´tel, u ktery´ch lze analyzovat oblicˇeje z profilovy´ch fotografiı´ na socia´lnı´ sı´ti. Tato databa´ze je reprezentova´na v ko´du jednotlivy´mi objekty typu Friend tak, jak je ilustrova´no na Obra´zku 23. Pro snazsˇ´ı manipulaci s daty je take´ implementova´na podpu˚rna´ trˇ´ıda FriendsHolder.

50

Obra´zek 23: Vlastnı´ trˇ´ıdy pro manipulaci s informacemi o prˇa´telı´ch

7.4

Vytva´rˇenı´ novy´ch na´vrhu˚ spojenı´ v za´vislosti na analyzovany´ch externı´ch datech

Pote´, co je vytvorˇena databa´ze sta´vajı´cı´ch prˇa´tel, je mozˇne´ prˇistoupit k samotne´mu vyhodnocenı´ novy´ch na´vrhu˚ na spojenı´. Princip funkcˇnosti zobrazuje Obra´zek 24. I v tomto prˇ´ıpadeˇ je vyzˇadova´na autorizace uzˇivatele vu˚cˇi sı´ti Flickr. Prˇ´ıstup a zpracova´nı´ fotografiı´, dostupny´ch ve verˇejne´ slozˇce sluzˇby, je sice mozˇne´ i bez autorizace, ovsˇem pro pozdeˇjsˇ´ı u´pravu informacı´ v tag objektech jizˇ nutna´ autorizace je. Pro jednotnost funkce nove´ho algoritmu byl tedy fakt autorizace oznacˇen jako nezbytny´. Uzˇivateli je nabı´dnuta mozˇnost zvolit si pouze urcˇite´ slozˇky s fotografiemi, ktere´ na sı´ti Flickr ma´ nahrane´. Pote´ je na vybrane´ fotografie aplikova´n filtr, ktery´ ma´ vyrˇadit ty fotografie, ktere´ neobsahujı´ detekovatelne´ tva´rˇe. Tento filtr je opeˇt realizova´n sluzˇbou Betaface. V prˇ´ıpadeˇ, zˇe je ve fotografii zachyceno vı´ce tva´rˇ´ı, je tato pro dalsˇ´ı zpracova´nı´ upravena tak, zˇe kazˇda´ tva´rˇ je zpracova´va´na jako jedna fotografie. Jakmile jsou vsˇechny vybrane´ fotografie prˇipraveny, algoritmus mu˚zˇe prˇejı´t do hlavnı´ fa´ze. V te´to fa´zi mohou nastat dveˇ situace. V prvnı´ je analyzovana´ tva´rˇ vyhodnocena jako tva´rˇ jednoho ze sta´vajı´cı´ch prˇa´tel uzˇivatele. V tom prˇ´ıpadeˇ algoritmus upravı´ tag te´to fotografie prˇida´nı´m jme´na a prˇ´ıjmenı´ osoby z jejı´ho profilu na sı´ti Facebook. Ve druhe´

51

Obra´zek 24: Algoritmus vyhodnocova´nı´ informacı´ z externı´ch obrazovy´ch dat situaci nenı´ analyzovana´ tva´rˇ shodna´ ani s jednı´m dosavadnı´m prˇ´ıtelem. Ted’ je steˇzˇejnı´ veˇcı´, jestli analyzovana´ fotografie obsahuje informaci o jme´nech osob, ktere´ jsou na ni zachyceny. V prˇ´ıpadeˇ, zˇe informace u fotografie nenı´, nelze nijak zjistit u´daje o osoba´ch a v tom prˇ´ıpadeˇ analy´za koncˇ´ı neu´speˇchem. V prˇ´ıpadeˇ, zˇe tag obsahuje alesponˇ jedno jme´no osoby, ktere´ nenı´ shodne´ se jme´nem uzˇivatele sluzˇby, algoritmus prˇida´ za´znam do databa´ze mozˇny´ch novy´ch kontaktu˚. Za´znam je slozˇen ze jme´na (poprˇ´ıpadeˇ jmen, pokud je jich v tagu vı´ce) a tva´rˇe, ktera´ je analyzovana´. Pro informaci je vhodne´ prˇipomenout, zˇe tato databa´ze je odlisˇna´ od drˇ´ıve uvedene´ databa´ze sta´vajı´cı´ch prˇa´tel v Kapitole 7.4. Pozna´mka 7.1 V situaci, kdy je v tagu fotografie obsazˇeno vı´ce nezˇ jedno jme´no, algoritmus nenı´ schopen ihned verifikovat, k jake´ tva´rˇi na fotografii patrˇ´ı. V tomto prˇ´ıpadeˇ musı´ by´t vsˇechny jme´na z tag objektu ulozˇena do databa´ze mozˇny´ch novy´ch kontaktu˚ s analyzovanou tva´rˇ´ı. Ve fina´lnı´ fa´zi se pote´ algoritmus pokusı´ najı´t vsˇechny osoby se specificky´m jme´nem z tagu a rozhodnutı´, ktera´ je ta spra´vna´ (v za´vislosti na porovna´nı´ oblicˇeju˚), je provedeno azˇ tehdy. Ve fina´lnı´ fa´zi analy´zy procha´zı´ algoritmus vsˇechny za´znamy v databa´zi mozˇny´ch novy´ch kontaktu˚ a snazˇ´ı se kazˇdou osobu nale´zt na socia´lnı´ sı´ti Facebook. Vyhleda´va´nı´

52

probı´ha´ dotazem na vsˇechny uzˇivatele se specificky´m jme´nem (viz Vy´pis 8) a selekce toho spra´vne´ho je provedena pomocı´ porovna´va´nı´ analyzovane´ tva´rˇe s profilovy´mi fotografiemi uzˇivatelu˚ socia´lnı´ sı´teˇ. V prˇ´ıpadeˇ, zˇe je osoba nalezena, je k za´znamu v databa´zi prˇida´n identifika´tor nalezene´ho uzˇivatele z profilu na sı´ti Facebook. Pote´, co jsou vsˇechny za´znamy v databa´zi takto zpracova´ny, je proveden jesˇteˇ jeden pru˚chod skrze vsˇechny tyto za´znamy. Prˇi neˇm jsou odstraneˇny ty za´znamy, ktere´ neobsahujı´ identifika´tor osoby na sı´ti Facebook. Vy´sledna´ databa´ze tedy obsahuje pouze osoby, ktere´ budou uzˇivateli nabı´dnuty, jako mozˇna´ nova´ spojenı´ uvnitrˇ socia´lnı´ sı´teˇ. { ”data”: [ { ”name”: ”Karel Karelv Novak”, ” id ” : ”100006080585981” }, { ”name”: ”Karel Novak”, ” id ” : ”100006104803839” }, { ”name”: ”Karel Novak”, ” id ” : ”100003628884701” } ], ”paging”: {} }

Vy´pis 8: Cˇa´st vy´sledku˚ vyhleda´va´nı´ osoby se jme´nem Karel Novak

53

8

Analy´za vy´sledku˚ u´speˇsˇnosti experimenta´lnı´ho algoritmu

Experimenta´lnı´ algoritmus, ktery´ je vy´sledkem diplomove´ pra´ce, byl v za´veˇru podroben testova´nı´, ktere´ meˇlo uka´zat, jestli je tento navrzˇeny´ zpu˚sob vyhleda´va´nı´ novy´ch kontaktu˚ na socia´lnı´ sı´ti dostatecˇneˇ efektivnı´ k prakticke´mu vyuzˇitı´. Testovacı´ fa´ze byla rozdeˇlena do dvou cˇa´stı´. V te´ prvnı´ byla oveˇrˇova´na spolehlivost samotne´ sluzˇby pro rozpozna´va´nı´ a analy´zu oblicˇeju˚ - Betaface. Ve druhe´ fa´zi byl testova´n novy´ algoritmus jako celek. V na´sledujı´cı´ch kapitola´ch jsou uvedeny vy´sledky teˇchto testu˚.

8.1

Vyhodnocenı´ spolehlivosti sluzˇby pro analy´zu oblicˇeju˚ Betaface

Cı´lem tohoto testova´nı´ bylo zejme´na proka´zat vhodnost pouzˇitı´ externı´ sluzˇby Betaface. Ralph Gross z Carnegie Mellon University 8 poskytl testovacı´ obrazova´ data. Jednalo se o archiv cˇtyrˇ tisı´c fotografiı´ oblicˇeju˚, ktery´ byl sestaven v pru˚beˇhu dvoumeˇsı´cˇnı´ho fotografova´nı´ celkem 63 lidı´ [5]. Tva´rˇe lidı´ byly fotografova´ny za cele´ rˇady rozlicˇny´ch podmı´nek (rozdı´lne´ sveˇtelne´ situace nebo tva´rˇe zachyceny s odlisˇny´ch u´hlu˚). Z te´to databa´ze byly pro u´cˇely te´to pra´ce na´hodneˇ vybra´ny trˇi osoby (dva muzˇi a jedna zˇena), jejichzˇ oblicˇeje, zachycene´ za rozdı´lny´ch podmı´nek, byly analyzova´ny sluzˇbou Betaface (viz popis podmı´nek nı´zˇe). Pro kazˇdou osobu byla stanovena vzˇdy tzv. referencˇnı´ fotografie, zachycujı´cı´ jejı´ tva´rˇ fronta´lneˇ. V idea´lnı´m prˇ´ıpadeˇ meˇly by´t i ostatnı´ fotografie te´zˇe osoby oznacˇene´ Betaface sluzˇbou jako shodne´. situace 1 Referencˇnı´ fotografie. Tva´rˇ subjektu je zachycena za norma´lnı´ch sveˇtelny´ch ´ sta osoby jsou mı´rneˇ pootevrˇena, prˇi podmı´nek (jen mı´rneˇ podexponovany´ch). U mluvenı´. Tva´rˇ je k fotoapara´tu otocˇena prˇ´ımo. Osoby A a B jsou zachyceny s bry´lemi. situace 2-4 Tva´rˇ je vu˚cˇi fotoapara´tu v prˇ´ıme´m u´hlu. Sveˇtelne´ podmı´nky variujı´ u kazˇde´ situace od podexponovane´ho prˇ´ıpadu azˇ k prˇeexponovane´mu (u te´ je pouzˇit blesk).Osoby A a B jsou zachyceny s bry´lemi. situace 5-8 Tva´rˇ je zachycena v ostrˇejsˇ´ım u´hlu (vertika´lnı´m i horizonta´lnı´m), nezˇ v prˇedesˇly´ch situacı´ch, sta´le jsou vsˇak viditelne´ vsˇechny prima´rnı´ objekty. Sveˇtelne´ podmı´nky jsou rozdı´lne´ od norma´lu. situace 9-11 V teˇchto situacı´ch je tva´rˇ vu˚cˇi fotoapara´tu v nejveˇtsˇ´ıch u´hlech (nejsou jizˇ viditelne´ vsˇechny prima´rnı´ objekty). Fotografie jsou porˇ´ızeny za beˇzˇny´ch sveˇtelny´ch podmı´nek. situace 12-14 Tva´rˇ zachycena v prˇ´ıme´m u´hlu s fotoapara´tem. Sveˇtelne´ podmı´nky jsou v kazˇde´ situaci odlisˇne´. situace 15-18 Sveˇtelne´ podmı´nky jsou norma´lnı´. Tva´rˇ zachycena v prˇ´ıme´m u´hlu s otevrˇeny´ma i zavrˇeny´ma ocˇima. Osoby A a B jsou zachyceny jak s, tak i bez bry´lı´. 8

http://www.ri.cmu.edu/research project detail.html?project id=418&menu id=261

54

Vy´sledky testova´nı´ jsou uvedeny v Tabulce 5. Pokud nebyla tva´rˇ detekova´na nebo byla detekova´na jako neshodna´ s referencˇnı´ tva´rˇ´ı, je uvedeno x. Proble´my prˇi detekci se objevovaly zejme´na v situacı´ch 5 azˇ 11. Bylo to zpu˚sobeno tı´m, zˇe tva´rˇe jsou zachyceny vu˚cˇi fotoapara´tu v prˇ´ılisˇ veliky´ch u´hlech, cozˇ deformuje vy´sledny´ model tva´rˇe. V situacı´ch 9 azˇ 11 dokonce ve fotografiı´ch uzˇ tva´rˇ nenı´ mozˇno ani detekovat, jelikozˇ veˇtsˇ´ı mnozˇstvı´ prima´rnı´ch objektu˚ chybı´. Co se vsˇak podarˇilo proka´zat, je neza´vislost u´speˇsˇne´ detekce shodny´ch oblicˇeju˚ za odlisˇny´ch sveˇtelny´ch cˇi barevny´ch podmı´nek. V tomto jsou sta´vajı´cı´ algoritmy sluzˇby Betaface robustnı´. Za´vislost u´speˇsˇnosti detekce na konkre´tnı´ch osoba´ch take´ nebyla proka´za´na. Vy´sledky analy´zy tva´rˇ´ı u osob A a B jsou shodne´. V prˇ´ıpadeˇ Osoby C je mozˇno pozorovat odlisˇnosti v situacı´ch 2 a 5 (v situaci 16 analy´za nebyla prova´deˇna, protozˇe osoba nenı´ zachycena s bry´lemi). To je vsˇak zpu˚sobeno tı´m, zˇe Osoba C je mensˇ´ı nezˇ dveˇ prˇedesˇle´, avsˇak fotoapara´t prˇi focenı´ zu˚stal ve stejne´ vy´sˇce. Tva´rˇ je tedy umı´steˇna ve spodnı´ trˇetineˇ fotografie. V te´to pozici je me´neˇ na´chylneˇjsˇ´ı ke zmeˇna´m parametru˚ modelu u veˇtsˇ´ıch u´hlu˚ vu˚cˇi fotoapara´tu. Typ fotografie

Osoba A

Osoba B

Osoba C

situace 1 situace 2 situace 3 situace 4 situace 5 situace 6 situace 7 situace 8 situace 9 situace 10 situace 11 situace 12 situace 13 situace 14 situace 15 situace 16 situace 17 situace 18

N.A. detekova´na detekova´na detekova´na x x x x x x x detekova´na detekova´na detekova´na detekova´na detekova´na detekova´na detekova´na

N.A. detekova´na detekova´na detekova´na x x x x x x x detekova´na detekova´na detekova´na detekova´na detekova´na detekova´na detekova´na

N.A. x detekova´na detekova´na detekova´na x x x x x x detekova´na detekova´na detekova´na detekova´na N.A. detekova´na detekova´na

Tabulka 5: Vy´sledky testova´nı´ algoritmu˚ sluzˇby Betaface Vy´sledky teˇchto testu˚ dokazujı´, zˇe v pru˚meˇru dosahujı´ algoritmy rozpozna´va´nı´ sluzˇby Betaface 58% u´speˇsˇnosti. Bylo take´ proka´za´no, zˇe nejveˇtsˇ´ım proble´mem prˇi zpracova´va´nı´ je, kdyzˇ ve tva´rˇi chybı´ veˇtsˇ´ı mnozˇstvı´ prima´rnı´ch objektu˚, cozˇ v neˇktery´ch prˇ´ıpadech vede dokonce k nenalezenı´ oblicˇeje ve fotografii. Pokud by se algoritmy sluzˇby da´le vylepsˇovaly a vyuzˇ´ıvaly samoucˇ´ıcı´ch metod, tato nevy´hoda by se znacˇneˇ eliminovala.

55

8.2

´ speˇsˇnost nove´ho algoritmu jako celku U

V druhe´ cˇa´sti byla testova´nı´ podrobena nova´ aplikace jako celek. K testova´nı´ byly pouzˇity vlastnı´ u´cˇty na socia´lnı´ch sı´tı´ch Facebook a Flickr. V prˇ´ıpadeˇ u´cˇtu na sı´ti Facebook byla situace na´sledujı´cı´. Obsahoval celkem 77 sta´vajı´cı´ch prˇa´tel, z cˇehozˇ pouze 75 bylo mozˇno analyzovat (viz Kapitola 7.2). Po provedene´ pocˇa´tecˇnı´ filtraci, prˇi ktere´ byli odstraneˇni prˇa´tele´, ktery´m nebylo mozˇno detekovat tva´rˇ na profilove´ fotografii, zbylo k testova´nı´ 51 uzˇivatelu˚. V sı´ti Flickr byla pro testova´nı´ vytvorˇena se´rie 20 fotografiı´, ktera´ zachycovala uzˇivatele nove´ sluzˇby s dalsˇ´ımi osobami. Cela´ se´rie byla rozdeˇlena do dvou cˇa´stı´ po 10 fotografiı´ch. V te´ prvnı´ byly obsazˇeny pouze ty, ktere´ obsahovaly ve sve´m tagu informace o jme´nech osob, ktere´ se na nich vyskytujı´. Z teˇchto deseti bylo peˇt fotografiı´ se sta´vajı´cı´mi prˇa´teli uzˇivatele a peˇt s cizı´mi lidmi. Ve druhe´ cˇa´sti se´rie byly pouze ty fotografie bez uvedeny´ch jmen v tag objektech. Opeˇt peˇt z nich bylo fotografie se sta´vajı´cı´mi prˇa´teli na sı´ti Facebook a peˇt s dosud nezna´my´mi lidmi. Cela´ tato se´rie fotografiı´ byla prˇeda´na na vstup aplikace a vy´sledky jsou uvedeny v Tabulce 6. Fotografie

Pocˇet Novy´ch tva´rˇı´

Pocˇet Prˇa´tel

Pocˇet Detekovany´ch tva´rˇı´

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

0 0 0 1 2 1∗ 1∗ 0 3∗ 1∗ 0 0 0 2 2∗ 0 (4+1∗ ) 1∗ 1 0

2 3 2 0 1 0 0 1 0 0 1 4 6 0 7 2 0 0 0 2

2 3 3 1 4 1 1 3 2 1 2 0 6 2 9 2 6 1 1 2

Na´vrh novy´ch spojenı´ spra´vne´ chybne´ 0 0 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Prˇida´ny tagy spra´vne´ chybne´ 1 0 0 0 1 0 0 1 0 0 0 0 1 2 1 0 0 0 1 0

Tabulka 6: Vy´sledky u´speˇsˇnosti cele´ho experimenta´lnı´ho algoritmu

0 2 0 1 1 0 0 0 0 0 0 0 2 0 3 1 2 0 0 0

56

Jme´na osob, uvedena´ v tag objektech jednotlivy´ch fotografiı´ byla ve forma´tu, ktery´ umozˇnˇoval vyhleda´nı´ osoby na socia´lnı´ sı´ti. Jestlizˇe fotografie obsahuje nezna´me´ osoby, je ve sloupci Pocˇet novy´ch tva´rˇ´ı cˇ´ıslo rovno pocˇtu teˇchto osob. Jestlizˇe je navı´c u tohoto cˇ´ısla hveˇzdicˇka, znacˇ´ı to, zˇe osoby nelze vyhledat (tag fotografie neobsahuje jme´no teˇchto lidı´).

Obra´zek 25: Testovacı´ data poskytnuta´ Carnegie Mellon University Jak je z vy´sledku˚ testu patrne´, ve 20 fotografiı´ch bylo v idea´lnı´m prˇ´ıpadeˇ detekovatelny´ch deset novy´ch osob. Tva´rˇe vsˇech teˇchto osob byly na fotografiı´ch detekovane´, cozˇ je nutne´ oznacˇit za u´speˇch algoritmu˚ Betaface. Celkem cˇtyrˇi lide´ z teˇchto deseti byli u´speˇsˇneˇ identifikova´ni na socia´lnı´ sı´ti Facebook a byly tak navrzˇeny cˇtyrˇi nove´ spojenı´ s uzˇivatelem aplikace. Uspokojivy´m vy´sledkem je mozˇne´ take´ oznacˇit fakt, zˇe nebyl realizova´n ani jeden chybny´ na´vrh nove´ho spojenı´. Veˇtsˇ´ı chybovost ale byla detekova´na u vytva´rˇenı´ novy´ch tag objektu˚ s popisem osob, ktere´ se na fotografiı´ch vyskytujı´. V sedmi z 20 fotografiı´ se objevila alesponˇ jedna chybna´ informace o osobeˇ, ktera´ je na nich zachycena. Jelikozˇ je vsˇak tato funkce doplnˇkova´ k mnohem du˚lezˇiteˇjsˇ´ı funkci novy´ch na´vrhu˚ spojenı´, je mozˇno cely´ experimenta´lnı´ algoritmus oznacˇit za u´speˇsˇny´.

57

9

Za´veˇr

Cı´lem te´to diplomove´ pra´ce bylo sestavit experimenta´lnı´ algoritmus pro vyhleda´va´nı´ novy´ch spojenı´ uvnitrˇ konkre´tnı´ socia´lnı´ sı´teˇ. Tento algoritmus meˇl jako svu˚j prima´rnı´ na´stroj pouzˇ´ıt rozpozna´va´nı´ oblicˇeju˚. Meˇl take´ poskytovat dostatecˇneˇ relevantnı´ na´vrhy tak, aby byl pouzˇitelny´ v prakticke´m nasazenı´ jako pomocny´ na´stroj zejme´na pro nove´ uzˇivatele socia´lnı´ sı´teˇ. Relevantnost vy´sledku˚ byla proka´za´na se´rii testu˚ prˇipojeny´ch k textu te´to pra´ce. V soucˇasne´ dobeˇ jsou v nejveˇtsˇ´ıch socia´lnı´ch sı´tı´ch pro na´vrhy novy´ch spojenı´ vyuzˇ´ıva´ny zejme´na textove´ informace, ktere´ ovsˇem vedou k na´vrhu˚m, ktere´ nejsou dostatecˇneˇ relevantnı´. Zarˇazenı´m elementu rozpozna´va´nı´ oblicˇeju˚ je mozˇno velkou chybovost teˇchto algoritmu˚ eliminovat. V prvnı´ cˇa´sti bylo nutne´ nale´zt vhodny´ na´stroj rozpozna´va´nı´ tva´rˇ´ı ve formeˇ externı´ sluzˇby. Zde jsem byl nucen rˇesˇit zejme´na proble´m nedostatecˇne´ho pocˇtu volneˇ dostupny´ch sluzˇeb. Jako nejvhodneˇjsˇ´ı byla nakonec zvolena sluzˇba Betaface, u ktere´ navı´c lze ocˇeka´vat, zˇe se budou jejı´ algoritmy s postupem cˇasu vylepsˇovat, cozˇ povede i ke zlepsˇenı´ u´speˇsˇnosti nove´ aplikace. V dalsˇ´ı cˇa´sti byly vybra´ny socia´lnı´ sı´t’a zdroj obrazovy´ch dat, nad ktery´mi byla aplikace testova´na. Opeˇt byly na vy´beˇr mnohe´ varianty, ze ktery´ch vzesˇly fina´lnı´ sı´teˇ, ktere´ dle me´ho na´zoru byly nejperspektivneˇjsˇ´ı. U vybrany´ch sı´tı´ Facebook a Flickr bylo nutno vyrˇesˇit i autorizaci aplikace prˇi prˇ´ıstupu k datu˚m jejich uzˇivatelu˚. Zatı´mco u sı´teˇ Flickr byla experimenta´lnı´ aplikace zaregistrova´na oficia´lneˇ a autorizace probı´hala v automaticke´m rezˇimu od pocˇa´tku, u sı´teˇ Facebook byl nejprve zvolen prˇ´ıstup, kdy uzˇivatel nove´ sluzˇby musel autorizaci vu˚cˇi sı´ti odsouhlasit manua´lneˇ, jelikozˇ podmı´nky registrace aplikacı´ trˇetı´ch stran zde byly komplikovaneˇjsˇ´ı. V za´veˇru implementacˇnı´ fa´ze se vsˇak proble´m registrace aplikace vyrˇesˇil, a tak mohla by´t i v prˇ´ıpadeˇ sı´teˇ Facebook zvolena autorizace v automaticke´m rezˇimu. V testovacı´ fa´zi pra´ce bylo potvrzeno, zˇe noveˇ vyvinuty´ experimenta´lnı´ algoritmus je schopen navrhovat nova´ spojenı´ uzˇivatelu˚, ktera´ jsou relevantnı´. V konkre´tnı´ch testech se dokonce neobjevil ani jeden chybny´ na´vrh nove´ho spojenı´. Jako sekunda´rnı´ vy´sledek aplikace byla rovneˇzˇ implementova´na funkce, ktera´ automaticky okomentovala fotografie, na ktery´ch rozeznala sta´vajı´cı´ prˇa´tele ze socia´lnı´ sı´teˇ. V tomto prˇ´ıpadeˇ byla sice chybovost vysˇsˇ´ı, ovsˇem byla prˇ´ımo za´visla´ na schopnostech konkre´tnı´ch rozpozna´vacı´ch algoritmu˚ sluzˇby Betaface. Da´ se tedy ocˇeka´vat dalsˇ´ı vylepsˇova´nı´ vy´sledku˚ i v te´to cˇa´sti algoritmu, pokud se bude sluzˇba Betaface rozvı´jet. V pru˚beˇhu vy´voje algoritmu byla zjisˇteˇna i cela´ rˇada cest, ktery´mi by se vy´sledek te´to pra´ce dal v budoucnu vylepsˇovat. Hlavnı´ cˇa´stı´ je zejme´na analy´za textovy´ch informacı´, ktere´ jsou ke zkoumany´m fotografiı´m prˇilozˇeny. V prˇ´ıpadeˇ te´to pra´ce byla premisa, zˇe jme´na osob jsou u fotografie uvedena v takove´m forma´tu, ktery´ umozˇnˇuje nalezenı´ osob na socia´lnı´ch sı´tı´ch. V prakticke´m nasazenı´ aplikace, ktera´ by implementovala postupy te´to pra´ce, by bylo nutno osˇetrˇit i ty prˇ´ıpady, kdy je jme´no osoby zkomoleno nebo jsou naprˇ´ıklad uzˇity zdrobneˇliny jmen nebo ru˚zne´ dalsˇ´ı u´pravy. Toto je vsˇak ota´zka, vyzˇadujı´cı´ separa´tnı´ vy´zkum v oblasti zı´ska´va´nı´ a analyzova´nı´ textovy´ch informacı´. Bylo by rovneˇzˇ dobre´ v budoucnu zapracovat na prˇ´ıpadne´ implementaci vlastnı´ch algoritmu˚ rozpozna´va´nı´ oblicˇeju˚, ktere´ by vyuzˇ´ıvaly techniky samoucˇenı´, ktere´ se proka´zaly jako silny´ na´stroj, jenzˇ by vy´sledky experimenta´lnı´ho algoritmu znatelneˇ zlepsˇil.

58

Z te´matu te´to diplomove´ pra´ce vznikl rovneˇzˇ i odborny´ cˇla´nek Recommending New Links in Social Networks using Face Recognition, ktery´ obsahoval vysveˇtlenı´ problematiky i s vy´sledky nove´ho algoritmu. Fina´lnı´ verze cˇla´nku, ktera´ byla odesla´na na konferenci SMAP 2013, 8th International Workshop on Semantic and Social Media Adaptation and Personalization, je prˇilozˇena k te´to diplomove´ pra´ci. Informace o tom, jestli byla oficia´lneˇ prˇijata, bude zna´ma azˇ po odevzda´nı´ diplomove´ pra´ce, dne 24. srpna 2013.

59

10

Reference

[1] Stonham,John,Thomas. Practical face recognition and verification with WISARD soucˇa´st Aspects of Face Processing. Nijhoff Publishers,1986 [2] Kohonen,Teuvo - Oja,Erkki - Lehtio,Pekka. Storage and processing of information in distributed asociative memory systems - chapter from Parallel models of associative memory, Lawrence Erlbaum Associates, Publishers Hillsdale,1981. p.105-143 [3] Mavridis,Nikolaos - Kazmi,Wajahat - Toulis,Panos. Friends with Faces: How Social Networks Can Enhance Face Recognition and Vice Versa - Chapter from Computational Social Network Analysis. Springer-Verlag London Limited,2010. p.453-482 [4] Josefsson,Simon. The Base16, Base32, and Base64 Data Encodings - Request for Comments: 4648. Network Working Group,2006. [5] Sim,Terence - Baker,Simon - Bsat,Maan. The CMU Pose, Illumination, and Expression (PIE) Database of Human Faces, Carnegie Mellon University [CMU-RI-TR-0102],2001. 18 pages [6] Federal Trade Commission. Best Practices for Common Uses of Facial Recognition Technologies[Staff Report]. Federal Trade Commission,2012. 30 pages [7] Bledsoe,Wilson,Woodrow. The model method in facial recognition - Technical Report PR I15. Palo Alto:Panoramatic Research Inc,1966 [8] Bledsoe,Wilson,Woodrow. Man-Machine facial recognition - Technical Report PRI 22. Palo Alto:Panoramatic Research Inc [9] Turk,Matthew - Pentland,Alex. Eigenfaces for Recognition - Journal of Cognitive Neuroscience. Massachusetts Institute of Technology,1991. p.71-86 [10] Goldstein,A.,Jay - Harmon,D.,Leon - Lesk,B.,Ann,. Identification of human faces proc. IEEE vol.59,1971. p.748-756 [11] Fischler,A.,Martin - Elschlager,A.,Robert. The Representation and matching of pictorial structures - proc. IEEE vol.c-22,1973. p.67-92 [12] Yuille,L.,Alan - Cohen,S.,David - Hallinan,W.,Peter. Feature extraction from faces using deformable templates - International Journal of Computer Vision,1992. p.99111 [13] Fleming,K.,Michael - Cottrell,W.,Garrison. Categorization of faces using unsupervised feature extraction - IJCNN International Joint Conference,1990. p.65-70 [14] Stone,Zack - Zickler,Todd - Darrell,Trevor. Autotagging Facebook: Social Network Context Improves Photo Annotation - Computer Vision and Pattern Recognition Workshops. IEEE Computer Society Conference on ,2008. p.1-8

60

[15] Mavridis,Nikolaos - Datta,Chandan - Emami,Shervin - Tanoto,Andry - BenAbdelkader,Chiraz - Rabie,Tamer. FaceBots: Social Robots Utilizing FaceBook - HumanRobot Interaction Human-Robot Interaction. ACM/IEEE 4th International Conference,2009. 195 pages [16] Carey,Susan - Diamond,Rhea. From piecemeal to configurational representation of faces. Science, New Series, Vol. 195,1977. p.312-314 [17] Charles,Arthur. The Guardian - Google bans facial recognition on Google Glass[online]. [cit. 2013-06-27]. http://www.guardian.co.uk/technology/ 2013/jun/03/google-glass-facial-recognition-ban [18] O’Reilly,Tim. What is Web 2.0[online]. [cit. 2013-04-07]. http:// www.oreillynet.com/pub/a/oreilly/tim/news/2005/09/30/ what-is-web-20.html [19] Facebook. Facebook Reports First Quarter 2013 Results[online]. [cit. 2013-07-01]. http://investor.fb.com/releasedetail.cfm?ReleaseID=761090 [20] Claburn,Thomas. Google Seeks Social Networking Face Recognition Patent[online]. [cit. 2013-03-10]. http://www.informationweek.com/internet/google/ google-seeks-social-networking-face-reco/229218484 [21] Smith,Craig. How Many People Use the Top Social Media, Apps and Services[online]. [cit. 2013-04-07]. http://expandedramblings.com/index.php/ resource-how-manypeople-use-the-top-social-media/ [22] Konoplev,Alex. Build Electronic Watchdogs with Highly Accurate Face Recognition - Press Release[online]. [cit. 2013-06-27]. http://luxand.com/press/detail. php?ID=1983 [23] Facebook. Facebook Blog[online]. [cite 2013-03-10]. http://blog.facebook. com/blog.php?post=467145887130 [24] Office of the Data Protection Commissioner. Complaint against Facebook Ireland Ltd.[online]. [cit. 2013-03-10]. http://europe-v-facebook.org/Complaint_ 09_Face_Recognition.pdf [25] Data Protection Commissioner. Facebook Ireland Audit Report[online]. [cit. 2013-03-10]. http://www.dataprotection.ie/docs/ Facebook-Ireland-Audit-Report-December-2011/1187.htm [26] Facebook. Graph Search[online]. [cit. 2011-04-07]. https://www.facebook.com/ about/graphsearch [27] J.,Golbeck. The Dynamics of Web-Based Social Networks: Membership,Relationships and Change - First Monday[online]. [cit. 2013-06-28]. http://www.uic.edu/ htbin/cgiwrap/bin/ojs/index.php/fm/article/view/2023/1889

61

A

Obsah CD prˇ´ılohy a cˇla´nek SMAP 2013 DiplomovaPrace-Stonawski aplikace FaceCompare FaceCompare solution video diplomovaPrace-text testovaci data

Recommending New Links in Social Networks using Face Recognition ˇ Petr Saloun, Jakub Stonawski, Ivan Zelinka Faculty of Electrical Engineering and Computer Science VSB-Technical University of Ostrava Czech Republic Email: [email protected], [email protected], [email protected] Abstract—The main task of our work is to help to a new user of a social network with finding new contacts. In the current situation mainly text data is used for these purposes. In our work we focus on information that is saved in images with the faces of potential users of a social network. Since there are hundreds of a photos from almost each user of a social network online, if we found the way how to analyze them effectively then we can suggest to the user new contacts. These new contacts will be more relevant than these which came from current methods for friends suggestions. The experimental algorithm for the new way of suggestions is described in this paper. The algorithm uses tools what are freely available by any user what one of our main targets was. The result of testing shows that our algorithm is successful during new contact suggestions. Keywords-social network,new Betaface, Facebook, Flickr

contacts,face

on getting information about relations from images. The main idea of whole concept is that there is a hundreds of pictures of the specific user of social networks in the internet. Many of these pictures contain also faces of another people. If we can find a way how to recognize people who appeared with the user in a photograph, we can also make a connection between them in the social network. Since this technique is still not common enough we have to deal with a number of problems, mostly related to reliability of recognize algorithms. There is also law problem during face recognition(e.g. Facebook‘s Tag Suggestions service [1] and complaints against it [2]), about which a separate papers discussed [14].

recognition,

I. I NTRODUCTION One of the most difficult situations for a new user of the social network appears when he has not adequate number of contacts (friends) inside the network. The social network itself provides many ways how can a user find contacts but unfortunately most of these is not so effective and provides also many wrong suggestions. Our work is to help the user find new contacts without these wrong suggestions. If we start examine this problem from the social network point of view we also discovered that right suggestions of the new contacts is important for network itself. Simplistically it can be said that the more users the social network have the more income from advertisements will come. If the user will have a connection to real friends or colleagues, the time what he spend on social network will increase which is exactly what a social networks wants. Nowadays the text information is used for creation of a new connection between users in the most of the biggest social networks. The text information can be e-mail addresses or external storage of contacts that are used directly for creation of the new connection. The second way is to monitor the user and collect important data which are further used for the new contact suggestions. The data can contains favorite topics, hobbies as well as the place of residence. The data is further used for creation of groups where is a high probability that users know each other(see Figure 1). All of the nowadays used techniques are not effective enough so the tendency of find better way is obvious. We focus

Fig. 1.

Example of the current new links suggestions

II. S TATE OF THE ART Goal of our work is to help to a new user with new connections in the early stages on the social network. Nowadays there exists different solutions how to help user with this problem (see Section I) but we focuse on usage of a face recognition element. There already exist solutions which implement the face recognition in a social network for example the work of Stone, Zickler and Darrell, that solve the problem of automatic tagging of the photos in the Facebook social network [15]. The service based on the principles that was described in the paper were deployed by Facebook what raises the law issue problem during face recognition [3].

The other example of the solution is research paper Friends with faces [16]. It is a part the project FaceBots: Social Robots utilizing Facebook [17]. The goal of whole project was to develop a robot with face recognition ability and dialog capabilities that is connected into the social database. With these features the robot is able to analyze information in the social network and use them in the real world. The face recognition can be done above real world photos captured by robot‘s cameras or above photos downloaded from Facebook. After the analysis the robot can decide who is friend of whom. The algorithms of the Facebots can analyze three basic types of the photos. The photos which contain exactly one tag with name of the person captured on it. The photos without any tag contain names. And the photos with more than one tag contains name. Depending on category where the photo belongs, the algorithms can work with use of the social context information (if there is not tag with names) or without any social context. In our approach we would like to replace the analysis of a social context by the analysis of common available photos from which we can extract needed information to new contact suggestions. III. S OLUTION WITH FACE RECOGNITION

profile picture. When the face of a user A is detected in the photo comparison with the profile picture of the user is done. When face of person B (as well as Bi if there are another people in the photo) is detected our algorithm can go through the all contacts of the user A and comparison of their faces taken from their profile pictures can be done. If face B does not match to any friend of a user A the search for B (Bi ) in Facebook begins. We are not able to go sequentially through all members of the Facebook since it is huge set of more than a billion accounts. The limited set of members of the Facebook has to be created. The first option is to use publicly available information detectable from the image such is gender or ethnicity But this information is not reliable enough since current algorithms for this purposes is still not so successful. Instead of this the restrictions of the input image has been determined. Our algorithm will consider only with input images that has additional information about people who are present1 . The information must be name of the person B (or also other Bi if there are any) and it is connected with image by its tag(initial assumptions have changed). With the name of the person a restriction of the set of all Facebook‘s users can be applied (see Figure 3).

Since the social network has a huge amount of users a sophisticated algorithm for browsing the elements of large set of contacts has to be used. In the following chapter the efficient way for finding new contacts with use of face recognition will be described.

Fig. 3. users

Fig. 2. Standard input scenario for finding new contacts with face comparison

Standard scenario during finding new contact and its solution Firstly we established standard start scenario. Since our solution works on Facebook all situations will be described for this social network. Initial assumptions: 1) a photograph downloaded from internet where faces of at least 2 persons are shown (see Figure 2) 2) face A belongs to user of our application 3) face B belongs to unknown person who is not in contact with user A on Facebook User A is a user of our service which means that we have a permission for browse through the list of his contacts and his

Definition of the set of all Facebook‘s users and subset of a limited

When above restrictions are deployed we are able to determinate if person B is a user of the Facebook and if the new contact suggestion will be made. Basically there are two options where person B can be present. If person B is found in Facebook than person B = x. If person B is not found than person B = z. Situation when person B = y can occur when above mentioned restrictions are done with an error (for example misidentification of the person’s B name). IV. FACE R ECOGNITION TECHNIQUES Nowadays a specific primary objects in face is used for face recognition in most of the current algorithms [4]. When these objects are found in a face the algorithms usually comparing positions and size of the objects and then these data are used 1 Respectively its part what dealing with new contact suggestions because our solution contains also function for creation of the new tags with names.

for face comparison. Many problems such a occultation of part of the face can occur. Success in dealing with these problems depends on fact how can each algorithm adapt in not ideal conditions.

recursive results propagation [11]. When the neural Networks began to be used the algorithms become more effective. B. The tuning of the services There was an assumption that some of the transferred data can be saved if our algorithm will use two services in face recognition phase instead of one complex service. The idea is that the first, simpler service (in our experiment WaldBoost service was used 2 ) will be used only for face detection in analyzing photo. Only photos that contain at least 1 face will be processed to the second service that is more complex and enables not only detection but also face recognition.Photo provided to second, complex service will be trimmed to include only face (faces) which will lead to previously mentioned saving of transferred data.

Fig. 4.

Primary objects for face comparison algorithms

A. Basic classification of the algorithms The algorithms for face comparison can be divided to following groups (depends on how adaptive they are). a) Semiautomatic algorithms: These algorithms represent the easiest way how the face recognition can be done. Interaction with the users is required before recognition can starts. The user have to mark the primary objects in face or if there is some of these objects missing mark approximate area of occurrence (see Figure 4). After this phase computation above the primary objects begin [5]. First who tried to implement this system was W.W. Bledsoe [6]. The whole system was then improved in Bell Labs where the vector composed of the primary objects was determined. The improvement leads to better results during analyze phase [7]. Algorithms based on these systems are still used but for our purposes are inappropriate since the user interaction during face recognition needs to be eliminated. b) Automatic algorithms: Similar comparison techniques like in previous group are essentially used also in automatic algorithms. Only manually mark of the primary objects is replaced by automatic detection of these objects. This automatic detection was first implemented by Fichler and Elschlager [8]. Their algorithm was then improved and worked with parametric model of human face [9] where primary objects were detected more reliably since parameter of this model was determined for each photo individually. Level of errors during comparison of faces is also unsatisfactory in this group of algorithms. Especially if the picture of face is taken in bad conditions (for ex. some parts of face is missing or covered by shadows). c) Self-learning algorithms: The algorithms what are able to self-learning is the most reliable because problems mentioned above can be solved by them. In beginnings an associative networks which implemented basic self-learning algorithms were used [10]. This was then improved by using

Fig. 5.

Data transfer between application and Betaface service

The mentioned idea was proposed because communication with complex Betaface service is done as Figure 5 described . There are a many XML files that has to be transferred even if specific photo does not contain face. Communication between simpler pre-service is more efficient from data transfer point of view (see Figure 6) and it can avoid further processing of photos without face. The experiment whose task was to confirm or refute the hypothesis was made on the real image data.

Fig. 6.

Example of data transfer to simpler service

Typical size of the transferred data in each phase (number of step corresponds with number in Figures5 and 6) is described in Table I. Standard jpg picture of size 190 kB was used. The average value of reduction of an image if there is a face detected was also determined as three (size of a picture is reduced 3-times). The typical number of repetitions of specific requests during Betaface communication (in Table I marked as n) was in interval n(1; 5). For further calculation value three will be used. The typical scenario during experiment was, that every image was firstly processed by WaldBoost service. If there is no face detected the image will not be processed further. If 2 http://cmp.felk.cvut.cz/demos/FaceDetection/

Step

Betaface Service

WaldBoost service

1 2 3 4

xml+190= 250 kB 300 B (300 ∗ n) B (15 ∗ n) kB

190 kB 18 kB N.A. N.A.

TABLE I S IZE OF TRANSFERRED DATA IN DIFFERENT PHASES

B. Discovering of new connections After the Database of friends is created, finding of new contacts can started (see Figure 7). After authentication which is necessary for future modification of an image‘s tag, the preliminary filter must be applied. For this filtering the Betaface application is used. After all data is finally prepared the main phase of the algorithm may begin.

at least 1 face was detected the image was trimmed to include only face(s). The trimmed photo is than processed by Betaface. In Table II results of the experiment are shown. Saving of amount of data transferred was proved in case that two services are used and the analyzing photo does not contain face. This saving of amount of transferred data is however not sufficient. Additionally in case that the image contains a face, what is more usual case, the amount of the data is bigger than the potential savings from previous case. Considering the result of the experiment as well as the facts mentioned earlier, the usage of two services was not recommended. Image contains face(s) no face(s)

one service

two services

486.2 kB 486.2 kB

630.5 kB 397.7 kB

TABLE II S IZE OF TRANSFERRED AND PROCESSED DATA IN CASE OF 1 OR 2 SERVICES

Fig. 7.

V. ACQUISITION OF DATA FOR FINDING NEW RELATIONS As it was mentioned in Section III, the image with an user and his friends is required for finding new contacts. The freeware online photo gallery Flickr 3 was chosen as a source for these purposes. API library for communication via .NET framework called Flickr.net 4 was used. In the following text the algorithms for finding new relations in a social network are described. A. Information processing about existing friends In the first phase set of information about all friends from the social network has to be created. The user of our application has to be authenticated again the social network firstly. It caused that data about all 5 user‘s friends are available to our application. Than the image of every friend of the user has to be add to downloaded information separately since basic information are available only in text form. After filtration of an inappropriate friends (these who have a profile photo without recognized face) the Database of friends can be created. 3 http://www.flickr.com

4 http://flickrnet.codeplex.com/

5 Actually not every friend has to be included in the list (depends on the privacy settings of a particular friend).

The algorithm for new contacts suggestions

Basically two situations can occur during the main phase. The first one is that in the analyzing face one of user‘s friends was detected. The algorithm then checks if the tag of the image contains information about the name of a friend. If there is no name in the tag the algorithm adds this information to photo. The second scenario occurred when no friends of a user is detected in photo. Then the determinative fact is if photo contains any names of the persons. If there is no names at all in photo‘s tag the algorithm cannot suggests any new contact. If there is at least one name of a person (which does not belong to user of our application) the algorithm adds record to the Database of new contacts 6 . The record consists of the name(or names) and the face of the person. Situation when picture‘s tag contains more than one name: • • •

the algorithm cannot immediately verifies which name belongs to the detected face; all names from the tag have to be saved in the Database of new contacts with the detected face; in the final phase, the algorithm try to find all persons (by all names from record) and the right person (whom detected face actually belongs) is found (if there is any).

6 The Database of new contacts is a separate database and it is different from the Database of friends

C. Final phase - new contacts suggestions In the final phase the task of the algorithm is to go through all records in the Database of new contacts and try to find specific persons in the social network (by his name and face). If the person is found the specific id of his account in the social network is added to the current record in the database. When all records are processed the Database of new contacts is modified (all records without specific id of the account are deleted) and new contacts are provided to the user of our application. VI. E XPERIMENT The experimental application has been tested in 2 phases. In the first one the objects of the test were recognize algorithms in Betaface service itself. The ability to detect and identify faces during different conditions was subject of the first test. The second phase of testing was focused on our experimental algorithm for finding of new contacts. In the second phase only our own Facebook account was used for all testing purposes due to possible law conflict. Probationary Facebook account has 77 friends but only 75 accounts of friends were accessible for further testing (because of the privacy settings of each account see Section V). After the initial filtration, where friends without recognized face in profile picture were deleted, 51 accounts remained for detection phase. A. Test of Betaface’s recognition algorithms The test set of the pictures was provided by Ralph Gross from Carnegie Mellon University 7 . This set of the picture was taken during two months when 63 people were photographed in more than 4000 images [13]. In our experiment three random persons (two men and one woman) were chosen for analysis. The testing situation is described below: Detail information about test data: 1 Reference picture of a person. The subject (his face) is captured in normal light condition and in normal angle 2-4 Face is located in normal angle. Light conditions are different in each particular situation. 5-8 Face is located in sharper angles (horizontal and vertical). Uncommon light conditions. 9-11 The biggest angles during photography. Normal light conditions. 12-14 Different light conditions. Face is located in normal angle. 15-18 Normal light conditions. Open and close eyes. The person is captured with and without smile. Person A and B are captured with and without glasses. The results of this test are shown in Table III. The problems occurred mainly during analysis of the pictures from situations 5 to 11. It is caused by the big angles between face and camera. Especially in situations 9 to 11 where the face is captured almost from the side and the algorithm cannot find 7 http://www.ri.cmu.edu/research project detail.html?project id= 418&menu id=261

critical points in the face (see Figure 4). On the other hand susceptibility of the algorithms to the different light condition has not been proven. Situation

Person A

Person B

Person C

s1 s2 s3 s4 s5 s6-s11 s12 s13 s14 s15 s16 s17 s18

N.A. detected detected detected

N.A. detected detected detected

N.A.

detected detected detected detected detected detected detected

detected detected detected detected detected detected detected

detected detected detected detected detected detected detected N.A. detected detected

TABLE III R ESULTS OF THE FIRST PHASE OF THE TESTING

The results for person A and B is same only difference is person C. First fact is that person C has not picture from situation 16 because she has not wear glasses. The results of the C are different in the situations 2 and 5. The face of a C is captured in low part of the image and the face is less susceptible to bigger angles between face and camera.The result shows that average success rate of Betaface service during face recognition is 58 percent. B. Test of our experimental algorithm The source of pictures with possible new contacts (as it is described in Section V) was our Flickr profile. For the test purpose set of 20 images with different people was chosen. Every photo was captured with the user of our application. The set of all photos can be divided to two groups, each group contains 10 photos. The first contains photos with names of the persons captured in it. The second one contains only photos without any names. Each subset can be divided as follows: • 5 pictures with current friends in Facebook • 5 pictures with unknown people All tags that were attached to the specific pictures contain names of the persons in the format that enables to algorithm find the person in social network. If the picture contains the tag, it has a number in column new face equal to the number of names in its tag. If in the new face column is number with a star it means that the new face cannot be recognized (there is no tag with name in the picture). With this dataset the test was performed and the results are shown in Table IV In set of 20 pictures there were 10 people that can be found in ideal case. All these 10 faces were detected in the pictures. 4 of the 10 faces were also successfully detected in the Facebook and 4 new suggestions of contacts were provided to the user. Satisfactory is also fact that zero incorrect new suggestions were provided. Function for create tags with names was detected as not so reliable since in 7 of 20 pictures at least one error in tag appeared.

Picture

Number of

Number of

Number of

New face

Friends

Detected faces

New connection detected correct

incorrect

correct

Tags added incorrect

1

0

2

2

0

0

1

0

2

0

3

3

0

0

0

2

3

0

2

3

0

0

0

0

4

1

0

1

0

0

0

1

5

2

1

4

1

0

1

1

6

1∗

0

1

0

0

0

0

7

1∗

0

1

0

0

0

0

8

0

1

3

0

0

1

0

9

3∗

0

2

0

0

0

0

10

1∗

0

1

0

0

0

0

11

0

1

2

0

0

0

0

12

0

4

0

0

0

0

0

13

0

6

6

0

0

1

2

14

2

0

2

2

0

2

0

15

2∗

7

9

0

0

1

3

16

0

2

2

0

0

0

1

17

(4+1∗ )

0

6

0

0

0

2

18

1∗

0

1

0

0

0

0

19

1

0

1

1

0

1

0

20

0

2

2

0

0

0

0

TABLE IV R ESULTS OF THE SECOND PHASE OF THE TESTING

VII. C ONCLUSION AND FUTURE WORK The main goal of our work was to create new experimental algorithm that can be used for new contact suggestions inside the specific social network (in our case Facebook). We have to suggest better way how the new links can be established since nowadays there are a lot of different options for this purposes but all of them with big amount of an error suggestions. The face recognition was chosen as an effective method for better results during finding new contacts inside the social network. As a source of the input images from which the algorithm can received sufficient amount of data Flickr service was used.The critical for successful determination of the new contact is appropriate set of input images and correct names of the persons in tags. As our results shows the experimental algorithm was successful in phase of new contact suggestions where from 10 new people who appeared in the test set of 20 images recognized and suggest 4 new links in the social network. Other faces of 6 remaining persons were successfully detected in the picture but cannot be find in the social network. Respectively they were found by their names, but cannot be verified by their profile pictures in the social network. Very good result was fact that algorithm did not suggest any wrong new contacts what was the main goal of the experimental solution. Less effective was the algorithm in the second phase where new tags for images should be created. There was noticeable error rate where in 35% of analyzing images at least one mistake appeared during person recognition. It shows that face recognition algorithms is still not efficient enough. For the future improvement of the algorithm mainly analyze of the names in the image‘s tags should be improved. In the testing set of images all names in tags were listed only in the correct form (name and surname of a person).If the algorithm will be transferred to the practical usage also other version

of the service for face recognize should be used. Free variant of the Betaface service is not designed for extensive usage of many users. It is also appropriate to consider implementation of the better face recognition service what can lead to better results especially in creation of the tags phase. Acknowledgement The following grants are acknowledged for the financial support provided for this research: Grant Agency of the Czech Republic - GACR P103/13/08195S, by the Development of human resources in research and development of latest soft computing methods and their application in practice project, reg. no. CZ.1.07/2.3.00/20.0072 funded by Operational Programme Education for Competitiveness, co-financed by ESF and state budget of the Czech Republic, and by Grant of ˇ - Technical University of Ostrava, SGS No. SP2013/114, VSB Czech Republic. R EFERENCES [1] Facebook. Facebook Blog[online]. [cite 2013-03-10]. http://blog.facebook.com/blog.php?post=467145887130 [2] Office of the Data Protection Commissioner. Complaint against Facebook Ireland Ltd.[online]. [cite 2013-03-10]. http://europe-v-facebook. org/Complaint 09 Face Recognition.pdf [3] Data Protection Commissioner. Facebook Ireland Audit Report[online]. [cite 2013-03-10]. http://www.dataprotection.ie/docs/FacebookIreland-Audit-Report-December- 2011/1187.htm [4] Turk,Matthew - Pentland,Alex. Eigenfaces for Recognition - Journal of Cognitive Neuroscience. Massachusetts Institute of Technology,1991. p.71-86 [5] Bledsoe,Wilson,Woodrow. The model method in facial recognition. Palo Alto:Panoramatic Research Inc,1966 [6] Bledsoe,Wilson,Woodrow. Man-Machine facial recognition. Palo Alto:Panoramatic Research Inc [7] Goldstein,A.,Jay - Harmon,D.,Leon - Lesk,B.,Ann,. Identification of human faces - proc. IEEE vol.59,1971. p.748-756 [8] Fischler,A.,Martin - Elschlager,A.,Robert. The Representation and matching of pictorial structures - proc. IEEE vol.c-22,1973. p.67-92 [9] Yuille,L.,Alan - Cohen,S.,David - Hallinan,W.,Peter. Feature extraction from faces using deformable templates - International Journal of Computer Vision,1992. p.99-111 [10] Kohonen,Teuvo - Oja,Erkki - Lehtio,Pekka. Storage and processing of information in distributed asociative memory systems - chapter from Parallel models of associative memory, Lawrence Erlbaum Associates, Publishers Hillsdale,1981. p.105-143 [11] Fleming,K.,Michael - Cottrell,W.,Garrison. Categorization of faces using unsupervised feature extraction - IJCNN International Joint Conference,1990. p.65-70 [12] Facebook. Graph Search[online]. [cite 2011-04-07]. https://www.facebook.com/about/graphsearch [13] Sim,Terence - Baker,Simon - Bsat,Maan. The CMU Pose, Illumination, and Expression (PIE) Database of Human Faces, Carnegie Mellon University [CMU-RI-TR-01-02],2001. 18 pages [14] Federal Trade Commission. Best Practices for Common Uses of Facial Recognition Technologies[Staff Report]. Federal Trade Commission,2012. 30 pages [15] Stone,Zack - Zickler,Todd - Darrell,Trevor. Autotagging Facebook: Social Network Context Improves Photo Annotation - Computer Vision and Pattern Recognition Workshops. IEEE Computer Society Conference on ,2008. p.1-8 [16] Mavridis,Nikolaos - Kazmi,Wajahat - Toulis,Panos. Friends with Faces: How Social Networks Can Enhance Face Recognition and Vice Versa Chapter from Computational Social Network Analysis. Springer-Verlag London Limited,2010. p.453-482 [17] Mavridis,Nikolaos - Datta,Chandan - Emami,Shervin - Tanoto,Andry BenAbdelkader,Chiraz - Rabie,Tamer. FaceBots: Social Robots Utilizing FaceBook - Human-Robot Interaction Human-Robot Interaction. ACM/IEEE 4th International Conference,2009. 195 pages