1. Мета і завдання

Об'єктом дослідження в роботі є інтеграція фотогалерей профілів користувачів. Предметом дослідження є алгоритм для об'їдання фотогалерей профілів користувачів з пов'язаних підгруп соціальних мереж.

Основним завданням даної роботи є розробка і програмна реалізація алгоритму, що дозволяє об'єднати фотогалереї, пов'язаних підгруп в соціальних мережах, за загальними ознаками на фотографіях.

2. Актуальність теми

На даний момент цифрові камери майже замінили плівкові через низку переваг. Власники камери тепер можуть створювати великі цифрові колекції з необмеженою кількістю фотографій і розміщувати їх в різних соціальних мережах. Необхідність ефективного використання та структурування цього величезного і динамічно мінливого обсягу графічних даних, обумовлює актуальність і значимість досліджень в галузі алгоритмів інтеграції фотогалерей профілів користувачів.

3.1 Соціальний граф

Соціальну мережу, як і будь-яку мережу, можна математично моделювати графом, в якому вершини представляють об'єкти мережі, а ребра - взаємини.

Одним з напрямків аналізу соціальних мереж є візуалізація відповідних графів. Візуалізація має важливе значення, оскільки сама можливість побачити мережу дозволяє зробити важливі висновки про характер взаємодії акторів, не вдаючись до інших методів аналізу графа. Як приклад на рис. 3.1 показан граф взаємодій історичних особистостей.

Рисунок 3.1 – Граф взаємодій історичних особистостей

Зв'язки графа можуть бути спрямованими або ненаправленими. Відносини начебто товариства або сусідства формують граф з ненаправленими зв'язками (рис. 3.2). Варіант графа з направленими зв'язками показаний на рис. 3.3. Даний граф побудований за відповідями на питання «З ким би ви хотіли дружити?», задане колективу з чотирьох чоловік.

Рисунок 3.2 – Граф з ненаправленими зв'язками

Математичний апарат аналізу графів дозволяє розрахувати цілий ряд параметрів і дати кількісні відповіді на багато питань. Для обговорення даних параметрів введемо деякі поняття.

Шлях між вершинами - це послідовність вершин і ребер, що з'єднують дві вершини.

Наприклад, шлях від а до d(див. рис. 3.2) - це вершинаа, ребро аb, ребро bd і вершина d.

Або вершина а,ребро ас,ребро cd і вершина d.

Відстань між вершинами - це кількість кроків, які потрібно зробити, щоб дістатися від однієї вершини до іншої, тобто на рис. 3.2 відстань від a до b дорівнює 1, а від а до d- 2.

Вершини в графі можуть бути пов'язані різними способами:

• безпосередньо, якщо між вершинами є ребро або дуга - так, наприклад, на социограмме (рис. 3.3) пов'язані Ваня і Аня;
• побічно, якщо між ними існує шлях, наприклад Ваня і Петя;
• за допомогою базового зв'язку, коли вершини зв'язані прямо і ніяк інакше.

Рисунок 3.3 – Граф з направленими зв'язками

В аналізі соціальних мереж на базі теорії графів виділяють:

• розрахунок індексів для соціальної мережі в цілому;
• для окремих агентів мережі;
• виділення підструктур в соціальній мережі.

Для розрахунку індексів для соціальної мережі в цілому використовують елементарні параметри, такі як число вершин або ребер, і деякі обчислювані параметри. Наприклад, щільність обчислюється як нормоване число ребер - відношення зв'язків у мережі до можливого максимальній кількості зв'язків в мережі з даною кількістю вершин. Число симетричних диад (на рис. 3.3 таких диад дві: Ваня - Катя і Катя - Петя) є показником стабільності соціальної мережі. Кількість транзитивних тріад (рис. 3.4) і циклічних тріад теж дозволяє оцінювати стабільність мережі.

Рисунок 3.4 – Граф транзитивних тріад

Середня відстань від однієї вершини до інших розраховується на основі мінімальних відстаней від даної вершини до всіх інших. Мінімальну відстань між двома вершинами називають геодезичною відстанню (geodesic distance). Параметром, який показує, наскільки велика мережа, є діаметр соціальної мережі - найбільша геодезична відстань в соціальній мережі (за умови, що граф пов'язаний, тобто якщо між будь-якими двома вершинами є шлях).

Структурні діри (structural holes) - вид структури мережі, при якому агент мережі, який нас цікавить, пов'язаний з деяким числом інших агентів, які не пов'язані між собою. Якщо між агентами мережі є соціальна діра, це означає, що вони не мають можливості взаємодіяти безпосередньо. Таким чином, агенти мережі, що з'єднують незв'язаних агентів, отримують можливість виступати посередниками і контролювати їх взаємодію.

При розрахунку індексів для окремих вершин виділяють наступні параметри:

• вхідна ступінь вершини - кількість ребер графа, що входять в вершину;
• вихідна ступінь вершини - кількість ребер графа, що виходять з вершини;
• відстань від даної вершини до кожної з інших;
• середня відстань від даної вершини до інших;
• ексцентричність (eccentricity) - найбільше з геодезичних відстаней від даної вершини до інших;
• проміжність - число шляхів, що включають дану вершину;
• центральність (центральним агентом мережі є той, у кого найбільше зв'язків).

Знаходження блоків дозволяє виявити ті чи інші структури, приховані в соціальній мережі. Виділення блоків можна робити за різними атрибутам агентів мережі, наприклад по статі. У блоки також можна об'єднувати еквівалентних агентів мережі. Наприклад, якщо відношення, за яким побудована соціальна мережа, - інформаційні потоки, то в один блок можна включити агентів мережі, які передають інформацію, в другий - тих, хто її отримує, в третій - тих, хто отримує і посилає інформацію іншим агентам мережі.

Існує кілька підходів до виділення підструктур в соціальній мережі:

• визначення клік в соціальній мережі. Кліки - це підгрупи, в яких агенти пов'язані між собою сильніше, ніж з членами інших клік;
• виділення компонентів (частин графа), які пов'язані всередині і не пов'язані між собою. Якщо в соціальній мережі є один або декілька ізольованих членів, то вони є компонентами;
• знаходження блоків і перемичок. Вершина називається перемичкою (cutpoint), якщо при її видаленні граф розпадається на блоки (незв'язані частини соціальної мережі);
• виділення угруповань (factions) - груп еквівалентних агентів мережі, які мають максимально схожі профілі зв'язків [1].

3.2 Технологія OpenCV

Ідентифікація людини завжди була важливою проблемою. У процесі еволюції обчислювальної техніки стали активно розвиватися біометричні технології - «методи і технічні засоби отримання та використання біометричних даних людини в цілях його ідентифікації». Їх метою є розробка автоматизованих систем ідентифікації людини на основі біометричних ознак, одною з яких, є зображення обличчя людини.

OpenCV - бібліотека комп'ютерного зору з відкритим вихідним кодом, доступна для завантаження. Бібліотека написана на C і C + +, працює під Linux, Windows і Mac OS X. Відбувається активна розробка інтерфейсів для Python, Ruby, MATLAB та інших мов.

Однією з цілей OpenCV є надання простою у використанні бібліотеки машинного зору, яка допомагає створювати досить складні програми в короткі терміни. OpenCV містить в собі більше 500 функцій які охоплюють багато областей, включаючи контроль якості на виробництві, системи безпеки, обробку зображень, користувальницькі інтерфейси, стереоскопічний зір і роботобудування.

Загалом OpenCV надає інструментарій, достатній для вирішення переважної більшості завдань комп'ютерного зору. Якщо алгоритм немає у складі SDK, то, як правило, він може бути без проблем запрограмований. Крім того, існує безліч авторських версій алгоритмів, написаних користувачами на основі OpenCV.

Також слід зазначити, що за останні роки OpenCV сильно розширилася і стала в деякій мірі «великовагової». У зв'язку з цим, різними групами ентузіастів створюються «полегшені» бібліотеки, засновані на OpenCV [2].

Дана бібліотека допоможе ідентифікувати людей на фотографіях в соціальній мережі, завдяки виділенню характеристичних точок: центрів очей, куточків очей, кінчика носа і т.д.

3.3 Геотегінг

Геотегінг - процес приєднання географічних метаданих до різних інформаційних ресурсів, таких як веб-сайти, RSS, фотографії, які характеризують ці ресурси (точка зйомки, місце розташування і т. п.). Ця інформація складається, як правило, з координат широти і довготи, хоча вона може включати також висоту, відстань і напрям до населених пунктів. Першим кроком у процесі геотегінгу є зіставлення географічних місць з відповідними знімками. Є два способи виконати цю операцію: автоматичний і ручний.

Для автоматичного запису GPS-координат місця зйомки в EXIF-дані використовується фотокамера, оснащена вбудованим GPS-приймачем, що записує координати в файл безпосередньо в момент створення знімка.

Введення точних координат прямо в програмі можна назвати ручним способом. У цьому випадку за допомогою спеціальних програм вручну модифікують GPS-секцію в EXIF-даних фотографії [3].

4. Алгоритм інтеграції фотогалерей профілів користувачів

У разі якщо на завантаженій користувачем фотографії знайдені обличчя і присутні географічні теги, можна визначити до якої фотогалереї в соціальній мережі віднести зображення. На представленій нижче анімації показаний принцип роботи алгоритму. Коли на фотографії ідентифіковані соціальні зв'язки між зображеними людьми, то фотографія буде поміщена в фотогалереї користувача в соціальних мережах з відповідними назвами. У той же час відсутність на фотографії осіб і наявність географічних метаданих дає можливість занести фотографію в галереї з назвою ідентифікованої за координатами місцевості.

Алгоритм интеграції фотогалерей представлено на рисунці 4.1

Рисунок 4.1 – Алгоритм інтеграції фотогалерей
(анімація: 6 кадрів, 10 циклів повтору, 185 килобайт)

Висновки

Проведено огляд існуючих підходів для досягнення поставлених цілей. Розглянуто технології, які допоможуть реалізувати систему для інтеграції фотогалерей профілів користувачів соціальних мереж.

Створення системи, яка зможе ідентифікувати соціальні зв'язки на фотографіях в соціальних мережах та вилучати дані про місце зйомки, дозволить вирішити завдання автоматичного структурування та класифікація фотографій в соціальних мережах, а також зможе без участі користувачів об'єднувати фотоколекції з різних соціальних мереж.

При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2014 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

Перелік посилань

1. Социальные сети и интернет.[Электронный ресурс]/ А. Прохоров. – Режим доступа: http://www.compress.ru/article.aspx?id=16723&iid=776
2. Что такое OpenCV. Электронный ресурс. Режим доступа: http://locv.ru/wiki/1.1_%D0%A7%D1%82%D0%BE_%D1%82%D0%B0%D0%BA%D0%BE%D0%B5_OpenCV
3. Геотегинг. Материал из Википедии – свободной энциклопедии. Электронный ресурс. Режим доступа:http://ru.wikipedia.org/wiki/Геотегинг
4. Feld, Scott L. (1981). The Focused Organization of Social. American Journal of Sociology. 86(5). 1015-1035
5. Ferligoj, Anuska and Valentina Hlebec. (1999). Evaluation of Social Network Measurement Instruments. Social Networks. 21. 111-130.
6. Fu, Yang-chih. (2005). Measuring Personal Networks with Daily Contacts: A Single-Item Survey Question and the Contact Diary. Social Networks. 27. 169-186.
7. Golder, Scott A. and Bernardo A. Huberman. (2006). Usage Patterns of Collaborative Tagging Systems. Journal of Information Science. 32(2) 198-208.
8. Granovetter, Mark S. (1974). Getting a Job: A Study of Contacts and Careers. Cambridge, MA: Harvard U. P.
9. Higgins, Christopher A., Ronald J. McClean and David W. Conrath. (1985). The Accuracy and Biases of Diary Communication Data. Social Networks. 7. 173-187.
10. Kindberg, Tim, Mirijana Spasojevic, Rowanne Fleck and Abigail Sellen. (2005). An In-Depth Study of Camera Phone Use. IEEE Pervasive Computing. April-June 2005. 42-50.
11. Milgram, Stanley. (1967). The Small World Problem. Psychology Today. Vol. 1, issue 61.
12. Rodden, Kerry, and Kenneth R. Wood. (2003). How do People Manage their Digital Photographs? Proc. CHI 2003.
13. Tyler, Josh, Dennis Wilkinson & Bernardo A. Huberman. (2003). Email as Spectroscopy: Automated Discovery of Community Structure within Organizations. Communities and Technologies 2003.
14. Viegas, Fernanda B., Scott Golder & Judith S. Donath. (2006). Visualizing Email Content: Portraying Relationships from Conversational Histories. Proc. CHI 2006.
15. Wasserman, Stanley and Katherine Faust. (1994). Social Network Analysis: Methods and Applications. Cambridge.
16. Wu, Fang and Bernardo A. Huberman. (2004). "Finding Communities in Linear Time: A Physics Approach." Eur. Phys. J. 38(2). Springer.