ИСПОЛЬЗОВАНИЕ ТЕОРИИ ГРАФОВ ДЛЯ ИДЕНТИФИКАЦИИ ЛИЦ

Дунаев А.А.

ORDCID: 0000-0002-8546-1871, Аспирант, Кафедра ИТАС, Белорусский государственный университет информатики и радиоэлектроники, г. Минск

ИСПОЛЬЗОВАНИЕ ТЕОРИИ ГРАФОВ ДЛЯ ИДЕНТИФИКАЦИИ ЛИЦ

Аннотация

В работе представлен оригинальный подход к решению задачи определения изоморфизма графов, используемый в системе распознавания лиц. Оригинальность предлагаемого в статье подхода базируется на хешировании структуры графа, используя в качестве инвариантной характеристики графа кратчайшие расстояний между всеми вершинами. Для поиска граничных точек частей лица на изображении применяется метод признаков Хаара. Для считывания подсчета характеристик точек на изображении применяется SURF-дескриптор. На основании рассчитанных значений дескрипторов составляются графы.

Ключевые слова: граф, изоморфизм, идентификация лиц, хеширование графа.

Dunaev A.A.

ORDCID: 0000-0002-8546-1871, Postgraduate Student, Department of ITAS, Belarusian State University of Informatics and Radioelectronics, Minsk

USING THE THEORY OF GRAPHS FOR FACE IDENTIFICATION

Abstract

The paper presents an original approach to solving the problem of determining graph isomorphism with the help of the face recognition system. The originality of the approach proposed in the article is based on the hashing of the graph structure, using the shortest distance between all vertices as the invariant characteristic of the graph. The Haar-like feature method is used to find the boundary points of the faces in the image. A SURF descriptor is used to read the calculation of the points’ characteristics on the image. Based on the calculated descriptor values, graphs are made.

Keywords: graph, isomorphism, face identification, graph hashing.

Введение

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

Описание задачи изоморфизма графов

В теории графов изоморфизмом графов называется биекция множества вершин графа G на множество вершин графа H, сохраняющая отношение смежности. Другими словами, для любых вершин u и v графа G их образы и смежны в H тогда и только тогда, когда u и v смежны в G. Отношение изоморфизма графов является эквивалентностью, т.е. оно симметрично, транзитивно и рефлексивно[2].

Анализ подходов

В настоящее время существует большое количество подходов в вопросе решения задачи изоморфизма графов.

Часть из них основано на доказательстве одинаковости структуры графов путем их параллельного обхода. Но использование этих методов требует больших временных затрат, особенно если речь идет о проверке структуры больших графов, состоящие из десятков вершин.

Другая часть подходов основывается на сравнении инвариантных характеристик графа, не зависящих от порядка нумерации вершин и ребер. Например, степени вершин графа. Однако, как показывает практика, данная характеристика является не достаточной, чтобы утверждать, что графы изоморфны [3].

Описание алгоритма считывания изображения лица в графы

Основные этапы алгоритма считывания изображения лица в графы:

– считывается изображение, на котором присутствует изображение лица;

– используя метод признаков Хаара, на изображении ищется изображение лица;

– из большого изображения вырезается изображение лица, дальнейшая обработка будет происходить с ним [5];

– размеры изображения лица изменяется на «квадратные», например, 100х100 точек, что поможет в случае, если изображение лица было растянуто, сжато или наклонено;

– используя метод признаков Хаара, на изображении лица ищутся угловые точки глаз, губ, носа, бровей [9, 10];

– используя SURF-дескриптор, в каждой из этих точек вычисляется значение дескриптора, который является вектором из 128 дробных чисел [7];

– строится граф с количеством вершин равным количеству найденных на предыдущих шагах точек с весами равными среднему арифметическому из предыдущего шага;

– все вершины соединяются ребрами;

– каждому ребру задается вес равный среднем арифметическому весов смежных вершин.

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

Описание алгоритма решения задачи изоморфизма графов

Рассматриваемый алгоритм основан на сравнении результатов хеширования графов. Рассмотрим основные этапы алгоритма решения задачи изоморфизма графов:

– по графу составляется матрица смежностей, состоящая из дробных чисел;

– выбирается число N уровней, например, 5;

– диапазон чисел в матрице смежностей делится на N частей, так чтобы их граничные значения B₁, …, B_N-1 были целыми или кратными 0,5;

– из имеющейся матрицы смежностей с дробными числами строится N-1 целочисленных матриц смежностей используя следующее правило, если значение в исходной матрице меньше B_i, то в целочисленной матрице в соответствующей ячейке пишется 0, иначе ‑ 1;

–  для каждой целочисленной матрице смежностей строится матрица кратчайших расстояний между любыми двумя вершинами, получается симметричная матрица, на главной диагонали которой 0;

– по каждой строке матриц кратчайших расстояний вычисляется среднее арифметическое и для каждой матрицы составляется последовательность из средних кратчайших расстояний;

–  полученные последовательности дробных чисел упорядочиваются по возрастанию элементов.

Полученные последовательности дробных чисел вместе с соответствующими уровнями являются «хеш-кодом» структуры рассматриваемого нечеткого графа. Теперь для того, чтобы определить являются ли графы изоморфными достаточно сравнить их «хеш-коды» по алгоритму, описанному выше.

Пример

В данном примере будет рассмотрен простой случай сравнения двух фотографий одного человека (рис. 1).

Рис. 1 – Считанные изображения человека

 

Следующим шагом используя метод признаков Хаара, на изображении лица ищется изображение лица и вырезается. Размеры изображения изменяется на «квадратные», для исправления растягивания и сжатия изображений и наклонов. Используя метод признаков Хаара, на изображениях лица ищутся угловые точки глаз, губ, носа и бровей (рис. 2).

Рис. 2 – Найденные точки частей лица на изображениях лиц

 

Используя SURF-дескриптор, в каждой из этих точек вычисляется значение дескриптора, который является вектором дробных чисел. Находится среднее арифметическое каждого вектора (табл. 1).

 

Таблица 1 – Средние арифметические векторов SURF дескрипторов

№	Название точки	Значение среднего вектора SURF-дескриптора
		Первое изображение	Второе изображение
1	Середина носа слева	0,120741	0,135028
2	Верх левого глаза	0,111313	0,087418
3	Верх правого глаза	0,051477	0,103232
4	Корень носа слева	0,169554	0,150959
5	Левый угол губ	0,192544	0,143660
6	Низ правого глаза	0,069248	0,108784
7	Центр носа	0.127991	0.170225
8	Корень носа справа	0,176355	0,154309
9	Середина носа справа	0,182539	0,194021
10	Низ левого глаза	0,071085	0,103680
11	Внутренняя левого глаза	0,167743	0,139524
12	Внешняя правого глаза	0,142344	0,144758
13	Внешняя левого глаза	0,144429	0,118897
14	Верх верхней губы	0,185874	0,189344
15	Правый угол губ	0,119799	0,154154
16	Низ верхней губы	-0,135612	-0,125378
17	Верх нижней губы	-0,084521	-0,108821
18	Внутренняя правого глаза	-0,057081	-0,083396

 

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

Далее необходимо проверить являются ли эти два графа изоморфными. Числа в матрицах смежностей находятся в диапазоне от -0,135612 до 0,194021. Выбирается число уровней, например, 6. Выбираются граничные значения уровней: -0,1; -0,05; 0; 0.05; 0,1; 0,15. Для каждого графа составляется 6 целочисленных матриц смежностей по следующему правилу. Если значение в ячейке исходной матрицы по каждому уровню больше либо равно граничному значению, то ставится единица, иначе ставится ноль.

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

 

Таблица 2 – Средние арифметические кратчайших расстояний по вершинам первого графа

 

Таблица 3 –  Средние арифметические кратчайших расстояний по вершинам второго графа

 

Для получения «хеш-кодов» графов необходимо упорядочить данные последовательности для каждого уровня.

Составленные «хеш-коды» сравниваются по уровням. Результат сравнения «хеш-кодов» по уровням показан в таблице 4.

 

Таблица 4 – Результат сравнивания «хеш-кодов» по уровням

Уровень	-0,1	-0,05	0	0,05	0,1	0,15
Результат сравнения	-	+	-	+	+	-

 

Если все пары «хеш-кодов» равны, то можно говорить о том, что рассматриваемые графы абсолютно изоморфны. В рассматриваемом примере 50% пар «хеш-кодов» графов совпадают, что свидетельствует о достаточно высоком уровне похожести этих графов и изображений лиц, на которых они построены.

Экспериментальная проверка метода

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

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

Заключение

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

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

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

1. Luks E.M. Isomorphism of graphs of bounded valence can be found in polynomial time //Journal of Computational Sciences. 1982, № 25(vol.1). P. 42–65.
2. Babai L. Moderately exponential bound for graph isomorphism. // Proceedings of the International FCT-Conference on foundations of computer theory. – London, 1981, P. 34–50.
3. Babai L. Random graph isomorphism // L. Babai, Erdos P., Selkow M. SIAM Journal of Com-puting, № 9 (vol. 3), 1980, P. 628-635.
4. Bahram Javidi Image Recognition and Classification: Algorithms, Systems, and Applications // CRC Press, 2002
5. Boguslaw Cyganek Object Detection and Recognition in Digital Images: Theory and Practice // Wiley, 2013
6. Lowe D. G. Distinctive Image Features from Scale-Invariant Keypoints // International Journal of Computer Vision. 2004. 60. № 2, P. 91–110.
7. Bay H., Ess A., Tuytelaars T., Gool L. V. SURF: Speeded Up Robust Features // Computer Vision and Image Understanding (CVIU). 2008. 110. №3. P. 346–359.
8. Torres-Méndez L.A., Ruiz-Suárez J. C., Sucar L. E., Gómez G. Translation, Rotation, and Scale-Invariant Object Recognition // IEEE Transactions on Systems, Man and Cybernetics. 2000. 30, № 1. P. 125–130.
9. Stan Z. Li, Anil Jain Handbook of Face Recognition // Springer Science & Business Media, 2011
10. Asit Kumar Datta,Madhura Datta,Pradipta Kumar Banerjee Face Detection and Recognition: Theory and Practice // Chapman and Hall, 2015