Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет информатики, математики и компьютерных наук

Программа подготовки бакалавров по направлению

09.03.04 Программная инженерия

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Кластеризация лиц на фотографиях из социальной сети для мобильных платформ

Купоросова Анастасия Олеговна

Рецензент: стажёр-исследователь лаборатории ЛАТАС

Рассадин Александр Георгиевич

Научный руководитель

д-р технических наук, проф.

Савченко Андрей Владимирович

Нижний Новгород, 2019

Содержание

Введение

Глава 1. Обзор литературы

1.1 Обзор существующих решений кластеризации лиц

1.2 Обзор существующих мобильных приложений

1.3 Обзор мобильных платформ

Глава 2. Разработка прототипа мобильного приложения группирующего лица

2.1 Требования к приложению

2.2 Алгоритм кластеризации лиц

2.2.1 Детектирование лиц

2.2.2 Извлечение характерных признаков

2.2.3 Кластеризация лиц

2.3 Архитектура мобильного приложения

2.5 Тестирование мобильного приложения

Глава 3. Экспериментальные исследования методов кластеризации лиц

3.1 Тестовый набор данных

3.2 Результаты экспериментального запуска алгоритмов

Заключение

Список литературы

Введение

В настоящее время машинное обучение в целом и нейронные сети в частности переживают вторую волну популярности, вызванную выросшими возможностями вычислительной техники. Исследователи, программисты, люди из сферы информационных технологий пытаются найти применение этих технологий в различных областях знаний. Всё чаще и чаще мы слышим о беспилотных машинах (практические реализации которых уже ездят в Сколково и Иннополисе), магазинах без обслуживающего персонала, где по камерам отслеживается, что покупатель взял и снимается итоговая сумма с его дебетовой карты, умных камерах, которые могут как распознавать номера автомобилей, так и находить определённых людей в толпе, что может помочь полиции в поисках преступников. Все описанные задачи так или иначе связаны с обработкой изображений. Обработка изображений является той областью, где больше всего сейчас применяются глубокие нейронные сети.

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

В настоящее время существует множество моделей для детектирования лиц, а также множество алгоритмов кластеризации. Комбинируя их, в результате можно найти наилучшее решение для этой задачи. Также задача имеет практическое применение, например, для приведения в порядок галереи в телефоне: все фотографии с людьми будут рассортированы по папкам, которые потом можно отдать другим людям без поисков их фотографий по галерее. Другой вариант использования алгоритма - запустить работать его в фоновом процессе, чтобы новая фотография сразу сравнивалась с уже прошедшими кластеризацию и сортировалась в нужную папку. В целом кластеризация лиц может быть использована в аэропортах, торговых центрах или в других местах, где образуется большое скопление людей в один момент времени. В частности, видеонаблюдение применяется практически во всех публичных местах, где достаточно сложно перебрать руками все кадры с видео, чтобы отследить человека, так что алгоритм кластеризации лиц может помочь в этом.

Целью данной работы является создание мобильного приложения для операционной системы Android, которое группирует фотографии по лицам, предварительно собранные из социальной сети Instagram. Пользователь сможет выбрать, где он хочет запустить алгоритм кластеризации - на сервере или на телефоне, затем он увидит гистограмму, на которой будут отражено количество фотографий в каждом кластере, и после нажатия на элемент гистограммы, который соответствует одному кластеру, можно будет увидеть все фотографии в этом кластере. Фотографии можно будет перенести в отдельную папку, которая создастся при нажатии на кнопку.

Данная цель была разбита на следующие задачи:

1. Провести обзор литературы по заданной теме исследования.

2. Создание набора фотографий, на котором будет тестироваться алгоритм.

3. Запуск существующих алгоритмов для детектирования, извлечения признаков и кластеризации лиц.

4. Реализация мобильного приложения на платформе Android.

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

Глава 1. Обзор литературы

1.1 Обзор существующих решений кластеризации лиц

кластеризация лицо фотография приложение

В ходе подготовки к выполнению работы, были исследованы различные источники, в которых исследователи, программисты уже пытались решить задачу кластеризации лиц. Произведём небольшой обзор этих статей.

Одной из первых работ, касающихся кластерного анализа лиц, является работа от 2001 года авторами которой являются Stefan Eickeler, Frank Wallhoff, Uri Iurgel, Gerhard Rigoll [3]. В своей работе для детектирования лица они использовали простейшую нейронную сеть, для выявления признаков лица использовалась псевдо 2D Скрытая Марковская Модель. Для кластеризации лиц исследователи использовали алгоритм k-means, который использует Скрытые Марковские Модели. Большим преимуществом использования СММ является быстрое вычисление.

Немного другой подход к решению данной задачи описан в статье, изданной в 2007 году авторами Panagiotis Antonopoulos, Nikos Nikolaidis, Ioannis Pitas [1]. В своей работе авторы описывают следующее решение для кластеризации лиц: для детектирования они предлагают использовать метод Boosted Cascade. Этот метод использует алгоритм Adaboost, который выбирает и комбинируют необходимые признаки, что напоминает функции Хаара в области обработки изображений, в результате чего тренируется эффективный классификатор. Такая комбинация сложных классификаторов в каскаде позволяет заблаговременно выделить участки, которые не содержат лица в результате чего уменьшается количество вычислений на данном этапе. Далее авторы описывают подход, который они используют непосредственно для кластеризации. Сначала они используют масштабно-инвариантную трансформацию признаков (SIFT) для создания матрицы попарных различий (dissimilarity matrix). Затем данная матрица подается в алгоритм агломеративной иерархической кластеризации, который использует метод средней связи. В данном алгоритме расстояние между двумя кластерами определяется как среднее расстояние между каждой точкой в этих кластерах.

В 2016 году Charles Otto, Dayong Wang и Anil K. Jain выпустили статью [5], в которой описали еще один подход к решению данной проблемы. Для детектирования и получения признаков лиц авторы предлагают использовать свёрточную нейронную сеть, а для кластеризации используются один из алгоритмов агломеративной иерархической кластеризации: rank order clustering, который использует метрику расстояния между ближайшими соседями. Общая часть для агломерационной иерархической кластеризации, учитывая некоторую метрику расстояния, состоит в том, чтобы инициализировать все выборки как отдельные кластеры, а затем итеративно объединять два ближайших кластера. Это требует определения метрики расстояния от кластера к кластеру. В алгоритме расстояние между двумя кластерами считается минимальным расстоянием между любыми двумя выборками в кластерах. В своей статье исследователи предложили некоторое улучшение rank-order clustering алгоритма. Они предложили рассчитывать меру расстояния на основе непосредственного суммирования наличия / отсутствия общих ближайших соседей, а не рангов.

Ещё одна работа по данной теме была опубликована летом 2018 года авторами Yichun Shi, Charles Otto и Anil K. Jain [9]. Для детектирования исследователи использовали глубокую нейронную сеть основанную на ResNet архитектуре. Данная нейронная сеть была натренирована на наборах данных CASIA-Webface и VGG-Face. Авторы предложили новый алгоритм кластеризации, который они назвали Conditional Pairwise Clustering (ConPaC). Этот алгоритм учится на матрице смежности непосредственно из данной матрицы подобия. В настоящее время данный алгоритм является одним из лучших по качеству кластеризации: 96.5% согласно данным, приведённым в статье.

Другой подход предлагают Zhongdao Wang, Liang Zheng, Yali Li и Shengjin Wang в своей работе от 2019 года [10]. В этой статье исследователи предлагают использовать метод на основе связей (linkage-based) для кластеризации лиц. Авторы делают акцент на важности контекста в

кластеризации лиц и предлагают создавать экземпляры сводных подграфов (instance pivot subgraphs), которые отображают контекст заданных узлов. В IPS используется граф сверточных сетей для определения вероятности связи между данным узлом и его соседями.

В результате исследования существующих решений можно сделать вывод, что авторы столкнулись с так называемой проблемой кластеризации. Это означает, что нужно точно указывать количество кластеров на выходе. Во всех предлагаемых алгоритмах кластеризации, кроме последнего, использовались такие алгоритмы, где возникала данная проблема, о чём авторы сами писали в своих статьях, что делает данные подходы тяжело применимыми в жизни, так как в реальных условиях мы не знаем, сколько действительно кластеров должно получиться. Поэтому планируется использовать и сравнить как результаты работы алгоритмов, где не нужно указывать количество кластеров на выходе, так и где необходимо указать это число.

1.2 Обзор существующих мобильных приложений

В ходе поиска существующих реализаций на мобильных платформах было найдено несколько решений. Рассмотрим некоторые из них.

На телефонах серии Huawei по умолчанию работает процесс, который с некоторой периодичностью анализирует галерею и создаёт папки. Кластеризацию нельзя вызвать по желанию пользователя, потому он не знает, когда именно запускается процесс группирования, что может быть неудобно, если срочно нужно группировать фотографии. Из чего состоит алгоритм найти не удалось, так как это является конфиденциальной информацией компании.

Аналогичное приложение есть на продуктах компании Apple [13]. На устройствах есть специальный альбом, который называется Люди. Если необходимо, чтобы в этом альбоме появились фотографии этого человека, а алгоритм пока не произвёл группировку, необходимо выбрать фото с этим человек, указать имя, нажать на кнопку «Далее». Устройство проведёт анализ галереи, и все фотографии с этим человеком будут добавлены в его альбом. Компания также не раскрывает особенности реализации алгоритма кластеризации.

Google представило свой сервис для работы с фотографиями, которое называется Google Photo [22]. Оно также имеет реализацию на смартфонах. Приложение позволяет включать/выключать функцию группирования фотографий людей. Приложение также просит давать имя директории. Если фотографии одного человека кластеризовались в несколько папок, и этим папкам задать одинаковые имена, то приложение предложит объединить эти папки и дальше будет кластеризовать в эту папку. Какой алгоритм кластеризации используется внутри приложения, компания также не раскрывает.

1.3 Обзор мобильных платформ

На текущий момент самыми популярными мобильными операционными системами являются Android, IOS. Согласно данным, найденным в сети интернет, на Android-устройства приходится 74.85% рынка, в то время как доля IOS-устройств равна 22.94% [23]. Данную популярность легко объясняется тем, что сами Android-устройства представлены во всех ценовых сегментах на любой вкус потенциального пользователя, а разработчик не ограничен выбором операционной системы, в которой он будет создавать мобильное приложение, в отличии от разработчика под IOS-устройства (им необходима операционная система MacOS).

Самой популярной средой разработки под Android является Android Studio, которая создана на основе Intellij IDEA и свободно распространяется компаний Google. Писать приложения можно как на Java, который является одним из популярнейших языков программирования, так и на Kotlin, который официально признан компанией Google основным языком для разработки под Android. [20] В то время как среда разработки приложений под IOS поставляется только с MacOS, и разработчику необходимо либо устанавливать эту операционную систему виртуально на своём компьютере, либо приобрести устройство с ней. Более того, IOS-разработчик должен знать один из следующих языков программирования для успешного написания приложения: Objective-C или Swift, которые не столько распространены.

В результате целевой мобильной платформой для данной работы был выбран Android из-за своей распространённости среди пользователей и низкого порога вхождения в процесс разработки.

1.4 Обзор библиотек глубокого обучения

На данный момент существует множество библиотек глубокого обучения. Многие из них предоставляют API для последующего запуска нейронных сетей на мобильных устройствах под управлением операционной системы Android. В результате поиска в Интернете по заданным критериям были найдены следующие библиотеки: Caffe2, TensorFlow, TensorFlow Lite, а также PyTorch, Monet. Рассмотрим их подробнее.

Caffe2 - это легковесная, модульная и масштабируемая среда глубокого обучения, созданная Facebook по лицензии Apache 2.0 на основе оригинальной библиотеки Caffe, которая была разработана в Университете Калифорнии в городе Беркли [15]. API доступен для Python и C++, реализована поддержка вычислений на GPU. На данный момент поглощена Porch. Caffe2 предоставляет простой способ работы с нейронными сетями и позволяет использовать последние модели и алгоритмы, идущие в составе библиотеки. Данная среда является кроссплатформенной и легко интегрируется с Visual Studio, Android Studio и Xcode для мобильной разработки. Среда доступна на следующих платформах: MacOS X, Ubuntu, CentOS, Windows, iOS, Android, Raspbian, Tegra. Может быть получена как в виде исходного кода, так и предварительно собранных исполняемых файлов или Docker контейнера.

TensorFlow - одна из самых популярных библиотек с открытым исходным кодом для построения и запуска моделей машинного обучения, разрабатываемая компанией Google [26]. Изначально предназначаясь для внутреннего использования внутри компании, библиотека была переведена в открытый доступ в 2015 году и с тех пор распространяется по лицензии Apache 2.0. API библиотеки доступен для Python, JavaScript, C++ и Java. Её гибкая архитектура позволяет легко развертывать модели на различных платформах, от настольных компьютеров до мобильных и периферийных устройств, в том числе на GPU. В состав библиотеки входит множество подготовленных наборов данных и предобученных моделей, что позволяет ускорить разработку собственных решений. TensorFlow, будучи распространённым решением, имеет развитую экосистему вспомогательных инструментов, упрощающих такие задачи как визуализация, замеры производительности и отладка. В настоящее время TensorFlow предлагает два решения для развертывания моделей машинного обучения на мобильных устройствах: TensorFlow Mobile и TensorFlow Lite.

TensorFlow Lite -- это улучшенная версия TensorFlow Mobile, предлагающая лучшую производительность и меньший размер приложения. Дополнительно, данная версия библиотеки предлагает возможности по оптимизации и уменьшению размера моделей, а также широкий выбор уже предварительно обработанных необходимым образом моделей. Кроме того, Lite имеет сравнительно мало зависимостей по сравнению с TensorFlow Mobile. TensorFlow Lite также поддерживает аппаратное ускорение на Android устройствах с помощью Android Neural Network API.

Mxnet - среда глубокого обучения с открытым исходным кодом, разрабатываемая Apache, используемая для обучения и запуска глубоких нейронных сетей [24]. Распространяется по лицензии Apache License 2.0. Mxnet используется Amazon Web Service и Microsoft Azure, предоставляя пользователю облачный API для глубокого обучения. Данная библиотека доступна для Linux, MacOS, Windows и встраиваемых устройств, поддерживается ускорение с использованием GPU. Реализована поддержка восьми языков программирования, в том числе Java, что позволяет использовать её при разработке под Android. Для запуска моделей на Android устройствах необходимо объединить модель в единый файл, используя скрипт из библиотеки и следует построить OpenBLAS под Android и Mxnet.

Pytorch - современная библиотека глубокого обучения с открытым исходным кодом, которую разрабатывает компания Facebook, отдел исследования искусственного интеллекта [25]. Pytorch основана на библиотеке Torch и распространяется по лицензии Apache 2.0. API библиотеки доступен на языках Python и C++. Поддерживаемые операционные системы - Linux, macOS, Windows. Реализована поддержка GPU. Для запуска моделей на мобильном телефоне, необходимо сконвертировать целевую модель в ONNX формат. После этого модель становится доступной для запуска на Android устройствах используя Caffe2.

В рамках данной работы было принято решение использовать библиотеку TensorFlow для запуска нейронных сетей на компьютере, и TensorFlow Mobile для запуска сетей на смартфоне.

Глава 2. Разработка прототипа мобильного приложения группирующего лица

2.1 Требования к приложению

Данные требования были составлены в соответствии со стандартом IEEE STD 830-1998 [18].

1. Введение

1.1. Назначение

Данные требования описывает версию 1.0.1 приложения, кластеризующего фотографии, взятые из галереи смартфона, с изображенными на них людьми.

1.2. Границы проекта

Приложение помогает пользователю держать галерею в порядке - все фотографии людей сортируются по папкам, пользователю не нужно вручную перебирать галерею, чтобы найти там фотографии определённого человека.

1.3. Ссылки

https://material.io/design/

2. Общее описание

2.1. Классы и характеристики пользователей

Пользователь, который много фотографирует людей и фотографируется сам.

Пользователь, которому необходимо отсылать фотографии изображенному на них человеку.

2.2. Операционная среда

Версия Android 6.0.0+, 90Mb память

Сервер Ubuntu 16.04 LTE, RAM 16Gb, находится в Германии

2.3. Ограничения дизайна и реализации

Использовать модели для детектирования лиц и получения признаков, полученные из фреймворка Tensorflow, так как именно для этого фреймворка существует библиотека под Android;

На сервере использовать Python3.5, так как он точно совместим со всеми версиями используемых библиотек, а также для него много разных модулей для реализации как серверной, так и алгоритмической частей

3. Функции системы

3.1. Запустить работать алгоритм на сервере

3.1.1. Пользователь использует необходимую кнопку для передачи сформированного .json файла, состоящего из фотографий и путей к ним, на сервер; Приоритет - средний;

3.1.2. Если галерея с фотографиями пустая, а пользователь все равно нажмет на кнопку, то приложение не упадёт, а пользователь получит сообщение об ошибке.

3.1.3. В результате получения ответа с сервера, открывается следующее Activity

3.2. Запустить работать алгоритм на телефоне

3.2.1. Пользователь использует необходимую кнопку для запуска алгоритма кластеризации на телефоне. Приоритет - высокий;

3.2.2. Если галерея с фотографиями пустая, а пользователь все равно нажмет на кнопку, то приложение не упадёт, а пользователь получит сообщение об ошибке.

3.2.3. В результате получения .json файла с результатами кластеризации, открывается следующее Activity

3.3. Нажатие на элемент гистограммы

3.3.1. Пользователь может нажать на элемент и просмотреть фотографии в данном кластере;

3.4. Пролистать фотографии в кластере

3.4.1. Пользователь может пролистать фотографии в кластере путем перелистывания влево или вправо;

3.5. Сделать папку для фотографий

3.5.1. Если папка для этого кластера существует, пользователь получает об это сообщение; Приоритет - высокий;

3.5.2. Фотографии копируются из галереи в созданную папку.

4. Требования к данным

4.1. Словарь данных

Фотографии на телефоне должны быть формата .jpeg, .jpg;

В папке Diplom должно лежать не менее 4 фотографий - по 2 фотографии на изображенного человека;

5. Требования к внешним интерфейсам

5.1. Пользовательские интерфейсы

Рекомендуется придерживаться стандартов material design;

Кнопка создания папки для кластера должна располагаться внизу;

Над кнопкой создания папки для кластера располагается окно, в котором можно пролистывать фотографии, находящиеся в этом кластере;

Гистограмма должна заниматься весь экран телефона;

На стартовом экран располагаются кнопки, которые позволяют пользователю выбрать, где запустить кластеризацию

Проверять и выводить об этом информацию пользователю, если папка уже была создана;

Сообщать пользователю, если в папке, откуда берутся фотографии, фотографий нет

5.2. Интерфейсы ПО

В папке Diplom, которая находится в галерее телефона, должны лежать фотографии людей;

Пользователь посредством кнопки может выбрать, где запустится алгоритм кластеризации;

Алгоритм вернёт файл формата .json, в котором каждому кластеру будет соответствовать список путей до фотографий;

Отображается гистограмма, показывающая количество фотографий в каждом кластере;

Пользователь может нажать на элемент гистограммы (выбрать кластер для просмотра);

Пользователь может просмотреть фотографии в выбранном кластере;

Пользователь может создать папку для фотографий в кластере;

5.3. Коммуникационные интерфейсы

Телефон отправляет POST-запрос на сервер по https;

Телефон отправляет и принимает от сервера файл формата .json

6. Атрибуты качества

6.1. Удобство использования

Пользователь должен беспрепятственно управляться с приложением - размер элементов приложения не должен быть меньше 150dp

Шрифт на кнопках и экране не менее 20dp

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

6.2. Безопасность

Фотографии пользователя не сохраняются на диске сервера;

Использовать https для передачи фотографий

6.3. Техника безопасности

При использовании кластеризации на сервере, выводить предупреждение о том, что фотографии будут отправлены на сервер.

7. Требования по интернационализации и локализации

Приложение должно быть реализовано с поддержкой английского языка как общепринятого международного языкового стандарта.

2.2 Алгоритм кластеризации лиц

На рисунке (рис.1) представлена схема работы алгоритма кластеризации лиц.



Рис. 1

2.2.1 Детектирование лиц

В самом начале необходимо использовать свёрточную нейронную сеть, которая детектирует лица. Для этой цели была выбрана свёрточная нейронная сеть архитектуры Multi-Task Cascaded Convolutional Neural Network [11], которая определяет положение лица на фотографии и возвращает несколько значений, среди которых координаты региона, содержащего лицо, на фотографии и лицевые ориентиры (углы рта, кончик носа, глаза). Данная сеть состоит из трёх нейронных сетей: Proposal Net (P-Net), Refinement Net (R-Net), Output Net (O-Net). На вход mtcnn подаётся фотография, размер которой постепенно уменьшается, и получается пирамида изображений. P-Net возвращает регионы лица (bounding boxes) и их достоверность (confidence). Так как возвращается большое количество регионов лиц, используется подавление не-максимумов (Non Maximum Suppression), в результате работы которого их количество сокращается. Выход R-Net похож на выход P-Net, но сами регионы лица более точные. Для этого снова используется подавление не-максимумов. O-Net возвращает лицевые ориентиры, координаты регионов лиц и достоверность каждого региона лица.

После того, как был получен результат работы mtcnn, используем его для вырезания лица из данной фотографии и выравнивания его, используя полученные лицевые ориентиры. Выравнивание происходит следующим образом: из координат глаз получаем угол между ними, получаем матрицу вращения и, используя аффинные преобразования, выравниваем его. У полученной картинки изменяем размер согласно тому, который требуется на вход следующей нейронной сети, нормализуем её и запускаем следующую нейронную сеть.

2.2.2 Извлечение характерных признаков

В данной работе были использованы следующие свёрточные нейронные сети для извлечения признаков: mobilenet, VGGFace(vgg16) [6], FaceNet(Inception-ResNet_v1) [8], VGGFace2(ResNet50) [2]. Рассмотрим подробнее каждую из них.

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

В рамках данной работы научным руководителем была предоставлена нейронная сеть MobileNet [7], обученная на наборе данных VGGFace2. Сеть принимает на вход трёхканальное BGR изображение размером 192x192, возвращает вектор признаков размером 1024.

Следующая нейронная сеть, которая была рассмотрена, это FaceNet - модель, основанная на архитектуре FaceNet [8]. В рамках данной работы использовалась модель, обученная на наборе данных VGGFace2. Сеть также принимает на вход трёхканальное RGB изображение, а возвращает вектор признаков размером 512.

Также были опробованы сети архитектуры VGGFace, VGGFace2, реализация которых была взята из модуля для библиотеки компьютерного зрения Keras с backend на TensoFlow [21]. На вход обеим архитектурам подаётся трёхканальное изображение размером 224х224. Вектор признаков для VGGFace можно получить из активационного слоя fc7/relu с ReLU активацией. Его размер будет равен 4096. Для VGGFace2 размерность вектора признаков будет равняться 2048 и получить его можно из слоя AveragePooling2D. Модели были обучены на наборе данных VGGFace.

2.2.3 Кластеризация лиц

На третьем этапе полученный вектор признаков подавался в алгоритм кластеризации. Были опробованы следующие алгоритмы кластеризации: DBSCAN, HDBSCAN, K-means, agglomerative hierarchical clustering, approximate rank order, fcluster.

Рассмотрим использованные алгоритмы кластеризации и некоторые их особенности.

Density-Based Spatial Clustering of Applications with Noise - алгоритм кластеризации, основанный на плотности. Он группирует объекты, которые расположены рядом, и помечает как выбросы те объекты, которые находятся одиноко в областях с низкой плотностью. В DBSCAN для измерения расстояния между признаками фотографий использовалось евклидово расстояние. В алгоритме DBSCAN необходимо указывать минимальное количество объектов в кластере, а также расстояние между

Hierarchical DBSCAN расширяет DBSCAN, преобразовывая его в алгоритм иерархической кластеризации, а затем используя технику нисходящей кластеризации, основанной на стабильности кластеров. В нём необходимо указывать минимальное количество объектов в кластере, причём объектов должно быть строго больше, чем 1. То есть если на фотографии несколько человек, и их фотографий нет, или в базе есть одна фотография человека, то такое лицо будет неправильно кластеризовано.

Алгоритм Hierarchical Agglomerative Clustering начинает работу с того, что оценивает каждый объект в отдельный кластер. На следующем этапе два наиболее похожих объекта объединяются в один кластер. И так происходит, пока не получаются один большой кластер. Затем начинается обратный процесс разделения. Данный алгоритм требует на вход ожидаемое количество кластеров на выходе, которое невозможно указать в условиях решения реальных задач.

Алгоритм Kmeans является одним из самых популярных алгоритмов кластеризации. На каждой итерации алгоритма центр масс пересчитывается для каждого кластера, полученного на предыдущем шаге. Потом векторы разбиваются на кластеры вновь соответственно близости новых центров по выбранной метрике. Главным минусом этого алгоритма является то, что требуется указать на входе ожидаемое количество кластеров на выходе, что невозможно сделать в условиях решения реальных задач.

Алгоритм Approximate Rank Order [5] является модификацией алгоритма The Rank Order Clustering [12]. ARO требуется подавать на вход порог расстояния между кластерами.

В третьей главе данной работы будут приведены результаты практических испытаний описанных алгоритмов кластеризации и моделей, извлекающих признаков.

2.3 Архитектура мобильного приложения

Приложение было реализовано с использованием языка программирования Kotlin на Android-части, и Python 3.5 для серверной части.

На рисунке (рис. 2) представлена UML-диаграмма мобильного приложения. Приложение можно разделить на backend и frontend части. Первая занимается сбором фотографий из папки и их последующей обработкой, кластеризацией. Вторая же предоставляет пользователю интерфейс, где запустить работать алгоритм, отображает результаты работы алгоритма. Разберём подробнее за что отвечает каждый класс.

Приложение начинает свою работу с InferLocationActivity. В данном классе происходит сбор фотографий из директории “Diplom”, далее в зависимости от того, где будет происходить процесс кластеризации фотографий, или формуется JSON формата путь до фотографии на телефоне - закодированные base64 байты фотографии, который отправляется на сервер, или фотографии передаются в класс MTCNNModel, где происходит их предобработка и детектируются лица, которые затем передаются в класс MobilenetModel, который извлекает признаки.



Рис. 2

Кластеризация происходит в методе makeCluster(), в котором вызывается алгоритм DBSCAN. BarChartActivity принимает JSON, в котором указан кластер и находящиеся в нём фотографии. В этом классе происходит десериализация JSON и отрисовка гистограммы, которая показывает количество фотографий в каждом кластере, и на элемент которой можно нажать. В классе PhotoActivity пользователь может просмотреть фотографии и создать папку для кластера.

В проектировании приложения использовались паттерны Фабрика и Одиночка. является класс RemoteServer, отвечающий за работу сервера. В нём реализована функция, отсылающая POST-запрос на кластеризацию.
Фабрика занимается генерацией классов в зависимости от модели, которая будет использоваться. В основе лежит некоторый базовый класс BaseModel, от которого унаследованы классы MTCNNModel и MobilenetModel, отвечающий за извлечение признаков из детектированных лиц.

В классе MTCNNModel был реализован запуск MTCNN, в частности для получения результатов каждой сети были созданы отдельные методы. Также была реализована предобработка фотографий, необходимая для работы MTCNN.

2.4 Интерфейс мобильного приложения

На изображении ниже (рис. 3) представлен Activity flow - какое действие порождает следующее Activity, а также показано, как предварительно должен выглядеть пользовательский интерфейс.

Рис. 3

После установки и открытия приложения, пользователь увидит на экране кнопки, нажав на которые, можно запустить алгоритм на телефоне или на сервере.

В первом Activity пользователь выбирает, где запустить кластеризацию. Пока идёт процесс кластеризации, описанный в пункте 2.2, пользователю показывается загрузка (рис. 4).

Рис. 4

В результате успешной кластеризации пользователь гистограмму, которая показывает количество фотографий в кластере. Каждый кластер назван по принципу Person #Number. На рисунке (рис. 5) представлено, как выглядит гистограмма в текущей реализации.



Рис. 5

Рис. 6

После нажатия на элемент гистограммы, пользователю открывается следующее Activity, в котором он может пролистать кластеризованные фотографии и создать для этого кластера папку (рис. 6).

Рис. 7

2.5 Тестирование мобильного приложения

Для того, чтобы проверить стабильность работы приложения, было проведено тестирование его различных составляющих компонент.

Для описание данного раздела использовался стандарт IEEE 829-2008 IEEE Standard for Software and System Test Documentation [17].

1. Ссылки

Страница 12 пункт 2.1 текущего документа - Требование к программному обеспечению.

2. Введение

Данный план тестирования был составлен для определения частей программного обеспечения, которые должны быть протестированы.

3. Тестируемый Функционал

1) Проверить, что фотографии есть в папке, откуда берутся фотографии;

2) Проверить, что эта папка существует;

3) Проверить, что характерные признаки были получены из нейронной сети;

4) Проверить, что детектирование лиц было завершено успешно;

5) Сравнить, что разница между двумя фотографиями одного человека удовлетворяет заданному порогу;

6) Сравнить, что разница между двумя фотографиями разных людей больше заданного порога;

7) Проверить правильность работы метрики;

8) Проверить работу сервера;

9) Проверить, что папка для кластеризованных фотографий создалась;

10) Проверить, что алгоритм кластеризации работает;

11) Проверить, что фотографии перенеслись в созданную директорию;

1. Подход (Стратегия)

Для того, чтобы проверить стабильность работы приложения, было проведено тестирование его различных составляющих компонент.

Процесс тестирования в данной работе можно разделить на две части:

? Тестирование пайплайна алгоритма кластеризации;

? Тестирование самого приложения.

Андроид Студия, которая использовалась для разработки приложения, позволяет покрывать продукт следующими видами тестов из коробки: JUnit-тестами, которые запускаются на локальной JVM-машине, или так называемые инструментальные тесты, которые проверяют работу Andoird API и запускаются на виртуальном или реальном девайсе.

В лучшем случае тестирование приложения должно включать в себя три категории тестов: unit-тесты, интеграционные тесты и end-to-end тесты, проверяющие в том числе и UI. На рисунке (рис. 8) представлена тестовая пирамида, которая показывает количество каждого вида тестов.



Рис. 8

Согласно ей и документации для Андроид-разработчиков, 70% должны составлять unit-тесты, 20% интеграционные тесты и 10% end-to-end тесты. Тестирование предлагается проводить или на виртуальном устройстве, либо с использованием Firebase test lab, чтобы проверить работу приложения на различных устройствах, то есть с разными размерами экранов и аппаратными характеристиками [14].

Тесты должны быть реализованы с использованием стандартной библиотеки JUnit. Также должен быть организован процесс автоматического тестирования в репозитории на базе Gitlab, где лежит код программы. Это позволит на этапе интеграции понимать, какие изменения какую часть программы могли поломать.

2. Критерии Успешного/Неуспешного Выполнения

Процесс тестирования считается успешным, если все модульные тесты были пройдены.

Процесс тестирования будет считаться неуспешным, если хотя бы один тест не пройдёт.

3. Критерии Остановки и Условия Продолжения

Необходимо прервать тестирование, если:

· нет фотографий;

· не обнаружилось лиц на фотографии;

· папки с фотографиями не существует;

· в папке лежит одна фотография;

7. Требования к Окружению

Версия Android Studio 3.4.0 и старше;

Смартфон на базе Android 6.0.0 и старше;

Python версий 3.5, 3.6;

RAM не менее 8Гб;

Данными являются фотографии формата .jpeg, .jpg на которых есть как минимум один человек;

Глава 3. Экспериментальные исследования методов кластеризации лиц

3.1 Тестовый набор данных

Тестовый набор данных представляет собой фотографии людей, которые были собраны из социальной сети Instagram. Для загрузки фотографий из Instagram было использовано приложение, которое запускается из командной строки, «instagram-scraper» [19]. Для запуска этого приложения необходимо как аргументы указать своё имя пользователя, имя пользователя, чьи фотографии необходимо скачать, пароль от своего пользователя. После запуска «instagram-scraper», начнётся процесс выкачивания фотографий.

Всего было собрано 454 фотографии 10 пользователей. На них преимущественно изображены сами владельцы профиля в социальной сети Instagram, но встречаются фотографии, на которых есть несколько человек. После запуска mtcnn и получения картинок, содержащих только лица, данные были просмотрены вручную, и для лиц, на которых не изображен владелец аккаунта, были созданы отдельные папки для более точной оценки работы алгоритма.

Более того, для оценки работы алгоритмов также был использованы данные под названием Group Face in the Wild [16]. Это один из самых больших наборов данных, собранных с разрешения владельцев профилей в китайской социальной сети. Набор состоит из 58 альбомов, в каждом из которых находятся папки с фотографиями определенного человека. Только первые две папки содержат множество разных людей, в одной из которой собраны люди, единожды встречающиеся в наборе данных, а во второй содержатся картинки низкого разрешения, на которых невозможно детектировать человека.

В ходе проведения исследования, первые две папки в каждом альбоме не использовались.

3.2 Результаты экспериментального запуска алгоритмов

В ходе выполнения работы были проведены экспериментальные запуски алгоритма кластеризации лиц на тестовом наборе данных [28]. Эксперимент заключался в следующем: попробовать различные нейронные сети для извлечения признаков лиц и различные алгоритмы кластеризации для получения наилучшей комбинации и последующей реализации на мобильной платформе.

Как было упомянуто выше, MTCNN возвращает помимо координат региона, содержащего лицо, лицевые ориентиры, которые могут быть применены для выравнивания лица, если на фотографии оно повёрнуто, что на практике встречается довольно часто. В ходе экспериментальных исследований было получено, что фотографии, на которых лица были повёрнуты, кластеризовались лучше, чем лица, к которым поворот лица не применялся. Также перед подачей лица в следующую сетку была выдвинута гипотеза, что L2-нормализация позволит вытащить признаки лучше, чем если просто нормализовать фотографию.

Для извлечения признаков лица использовались следующие свёрточные нейронные сети: vgg2_mobilenet_2, VGGFace, VGGFace2, FaceNet.

Для оценки качества работы алгоритмов кластеризации использовались следующие метрики: BCubed precision, recall и f-score, точность (homogeneity), полнота (completeness), v-мера (v-measure), скорректированный коэффициент Рэнда (adjusted Rand score), усреднённая взаимная информация (adjusted mutual info score).

Точность (precision) - показывает сколько объектов в данном кластере в самом деле принадлежат данном кластеру.

Полнота (recall) - отношение количества объектов в полученном кластере к общему числу объектов, которое должно быть в данном кластере.

Значения обеих метрик лежат в промежутке [0; 1]. Чем ближе к единице, тем лучше отработал алгоритм кластеризации.

Определим величину, называемую условной энтропией разбиения для эталонной классификации и прогнозной кластеризация :

а - энтропию класса, определим по формуле:

где - общее число элементов, и - число элементов соответственно в классе и кластере . Аналогичным образом задаётся и .

Точность определяется по следующей формуле:

Результат кластеризации удовлетворяет точности, если все его кластеры содержат только точки данных, которые являются членами одного класса. Значение точности находится в следующем промежутке: [0, 1].

Полнота определяется следующим образом:



Результат кластеризации удовлетворяет полноте, если все точки данных, которые являются членами данного класса, являются элементами одного кластера. Значение полноты распределено в промежутке: [0, 1].

V-мера это гармоническое среднее полноты и однородности. Она определяется следующей формулой:

Скорректированный индекс Рэнда является версией индекса Рэнда с поправкой на случайную кластеризацию. Принимает значения на отрезке
[-1; 1]. Отрицательное значение говорит о неудачной кластеризации. Значения, близкие к единице говорят о удачной кластеризации. Значение около нуля указывает на независимость выбранного кластеризующего алгоритма от признаков.

Пусть C - эталонная кластеризация объектов, с которой требуется сравнить прогнозную кластеризацию K. Дополнительно определим:

· - число пар объектов, попавших в один класс и в один кластер,

· - число пар объектов, попавших в различные классы и различные кластеры,

· - общее число элементов.

Индекс Рэнда (Rand index) задается следующим образом:

Тогда скорректированный индекс Рэнда будет определяться следующей формулой:

,

где E[RI] - оценка математического ожидания индекса Рэнда для случайных кластеризаций, max(RI) - максимальное значение индекса Рэнда среди полученных для случайных кластеризаций.

Усреднённая взаимная информация принимает значение близкие к единице, когда два разбиения идентичны, и 0, когда взаимная информация между двумя разбиениями равна значению, ожидаемому благодаря случайности.

Усреднённая взаимная информация высчитывается по следующей формуле:

где U, V - два разбиения пространства, H(U), H(V) - энтропия неравномерности для каждого разбиения, MI - взаимная информация, E[MI] - некоторый коэффициент взаимной информации между двумя случайными кластерами.

Экспериментальные запуски были выполнены на персональном компьютере на базе процессора Intel Core i5-4210U CPU, 64-разрядной операционной системе Windows 10.

Весь экспериментальный код был написан на языке Python 3.5 в PyCharm IDE. Для запуска моделей использовалась библиотека Tensorflow. Многие алгоритмы кластеризации и реализации метрик к ним были взяты из пакета scikit-learn версии 0.20.2.

В данной таблице представлено среднее время выделения признаков лица на одной фотографии и размер моделей.

Таблица 1. Размер и время работы моделей

	Размер, Мб	Время, с	Размер вектора признаков
Mobilenet	12.4	0.03	1024
VGGFace	524	0.34	4096
VGGFace2	92	0.24	2048
FaceNet	91.3	0.07	512

Из таблицы 1 видно, что самой тяжеловесной моделью оказалась VGGFace (ее размер в ~5 раз больше других моделей, и в 40 раз больше размера mobilenet), из чего сразу можно сделать вывод, что она не пригодна для применения на телефоне. Эта же модель показала самое большое время извлечения признаков. Моделью, показавшей наибольшую производительность оказалась Mobilenet, которая также имеет и наименьший размер, а значит по заданным в таблице параметрам она является наилучшей для запуска на телефоне.

Сравним же теперь результаты кластеризации по упомянутым выше метрикам.

Все запуски проводились с выравниванием лица и L2-нормализацией фотографий. Но для сравнения качества работы для модели VGGFace2 также был проведённым дополнительный запуск без выравнивания лица. Для проверки гипотезы про L2-нормализацию был произведён дополнительный запуск FaceNet, которая принимала фотографии без L2-нормализации.

Таблица 2. Результаты для mobilenet

	Precision	Recall	F-score	homogeneity	completeness	v-measure	ARS	AMI	N clusters
Kmeans	0.733	0.822	0.775	0.807	0.763	0.785	0.746	0.753	11
ARO	0.616	0.833	0.708	0.821	0.678	0.743	0.604	0.642	49
DBSCAN	0.736	0.765	0.750	0.774	0.766	0.770	0.705	0.757	81
HDBSCAN	0.679	0.846	0.754	0.846	0.738	0.788	0.720	0.721	16
HAC	0.656	0.970	0.783	0.973	0.687	0.812	0.758	0.644	10
Fcluster	0.656	0.970	0.783	0.973	0.697	0.812	0.758	0.644	89
GCN	0.744	0.837	0.816	0.981	0.835	0.883	0.823	0.751	14

Таблица 3. Результаты для VGGFace

	Precision	Recall	F-score	homogeneity	completeness	v-measure	ARS	AMI	N clusters
Kmeans	0.741	0.801	0.770	0.792	0.773	0.783	0.732	0.764	10
ARO	0.622	0.757	0.683	0.786	0.669	0.722	0.591	0.631	46
DBSCAN	0.671	0.866	0.757	0.897	0.694	0.782	0.704	0.647	71
HDBSCAN	0.689	0.761	0.723	0.782	0.727	0.754	0.686	0.713	13
HAC	0.653	0.828	0.730	0.815	0.717	0.763	0.663	0.703	13
Fcluster	0.672	0.866	0.756	0.896	0.694	0.782	0.704	0.647	72
GCN	0.754	0.836	0.805	0.878	0.764	0.801	0.752	0.703	15

В таблицах 3 и 4 представлены результаты запуска модели FaceNet с различными алгоритмами кластеризации. Отличием в запусках является то, что в таблице 4 полученные признаки нормализовали, используя L2-нормализацию.

Таблица 4. Результаты для facenet без L2-нормализации

	Precision	Recall	F-score	homogeneity	completeness	v-measure	ARS	AMI	N clusters
Kmeans	0.672	0.854	0.752	0.853	0.731	0.787	0.755	0.716	13
ARO	0.700	0.876	0.778	0.868	0.749	0.804	0.738	0.728	33
DBSCAN	0.707	0.974	0.820	0.976	0.734	0.837	0.794	0.693	74
HDBSCAN	0.740	0.362	0.453	0.360	0.597	0.449	0.140	0.328	51
HAC	0.744	0.866	0.801	0.859	0.772	0.813	0.794	0.760	13
Fcluster	0.691	0.975	0.809	0.976	0.724	0.831	0.785	0.689	75
GCN	0.814	0.865	0.835	0.903	0.754	0.845	0.836	0.945	15

Таблица 5. Результаты для facenet с L2-нормализацией

	Precision	Recall	F-score	homogeneity	completeness	v-measure	ARS	AMI	N cl
Kmeans	0.668	0.851	0.749	0.843	0.737	0.786	0.681	0.725	13
ARO	0.511	0.900	0.652	0.900	0.623	0.736	0.581	0.567	70
DBSCAN	0.706	0.973	0.819	0.975	0.733	0.837	0.794	0.692	74
HDBSCAN	0.742	0.796	0.768	0.826	0.765	0.795	0.725	0.751	14
HAC	0.744	0.866	0.800	0.858	0.771	0.813	0.794	0.760	12
Fcluster	0.706	0.973	0.819	0.975	0.733	0.837	0.794	0.692	75
GCN	0.831	0.905	0.874	0.895	0.785	0.869	0.845	0.967	16

В таблицах 5 и 6 представленные результаты запуска сети VGGFace2 на всех рассмотренных алгоритмах кластеризации с разницей в том, что в таблице 5 лица предварительно были выровнены, а в таблице 6 нет. Согласно полученным результатам, выравнивание лиц положительно влияет на качество работы большинства кластеризующих алгоритмов.

Таблица 6. Результаты для VGGFace2

	Precision	Recall	F-score	homogeneity	completeness	v-measure	ARS	AMI	N cl
Kmeans	0.753	0.820	0.785	0.804	0.787	0.796	0.735	0.779	10
ARO	0.663	0.839	0.741	0.834	0.719	0.772	0.615	0.692	38
DBSCAN	0.727	0.960	0.828	0.966	0.754	0.847	0.805	0.723	55
HDBSCAN	0.752	0.898	0.819	0.899	0.784	0.838	0.813	0.771	16
HAC	0.679	0.872	0.764	0.863	0.758	0.807	0.692	0.746	13
Fcluster	0.727	0.960	0.828	0.966	0.755	0.847	0.806	0.723	56
GCN	0.842	0.863	0.854	0.964	0.785	0.845	0.873	0.834	15

Таблица 7. Результаты для VGGFace2 без face alignment

	Precision	Recall	F-score	homogeneity	completeness	v-measure	ARS	AMI	N cl
Kmeans	0.723	0.885	0.796	0.867	0.760	0.810	0.715	0.749	10
ARO	0.697	0.946	0.803	0.939	0.728	0.820	0.771	0.699	34
DBSCAN	0.798	0.982	0.881	0.983	0.794	0.878	0.862	0.771	34
HDBSCAN	0.830	0.917	0.871	0.907	0.822	0.863	0.869	0.813	10
HAC	0.640	0.889	0.744	0.876	0.702	0.780	0.633	0.685	13
Fcluster	0.798	0.982	0.881	0.983	0.794	0.878	0.862	0.771	35
GCN	0.854	0.898	0.876	0.986	0.878	0.906	0.894	0.945	15

В результате приведённого исследования можно сделать вывод, что наихудший результат показала модель VGGFace. Наилучший результат показала сеть VGGFace2 и алгоритм кластеризации HDBSCAN. Планируется, что для серверной части будет использована именно эта комбинация алгоритмов.

Mobilenet показал результаты луч...