Сравнительный анализ метрик векторного расстояния растровых изображений

ВВЕДЕНИЕ

Метрика – это функция, определяющая расстояние в метрическом пространстве; мера, определяющая расстояние между элементами множества [1]. Метрика определена свойствами: больше или равна нулю; равна нулю при условии, что элементы множества совпадают; симметричная; подчиняется закону треугольника. Введение метрики на множестве определяет метрическое пространство [2]. Метрическое пространство – это множество, в котором определено расстояние между любой парой элементов [3].

Понятие расстояния введено для количественного измерения сходства и различия двух последовательностей. Мера расстояния – функция, присваивающая численное значение паре последовательностей: чем больше расстояние, тем меньше подобие [4].

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

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

Так, метрики сходства или различия применимы для такой предметной области как «интеллектуальная собственность», в узком смысле «правовая охрана средств индивидуализации». Средства индивидуализации – обозначения, при помощи которых коммерческие фирмы и их продукция, а именно товары и услуги, идентифицируются среди множества других подобных, приобретают уникальность. Правовая охрана интеллектуальной собственности, согласно Статье 1232 ГК РФ, предоставляется на основе государственной регистрации, которую осуществляет федеральный орган исполнительной власти Роспатент [5]. По статистике, около 30 % поданных заявок на регистрацию обозначения получают отказ, на основании наличия тождественных или схожих до степени смешения товарных знаков, зарегистрированных ранее. Проведение предварительной проверки обозначения на предмет наличия схожих или тождественных товарных знаков, зарегистрированных ранее, позволит снизить риски отказа в его государственной регистрации. Использование метрик позволит автоматизировать процесс проверки изобразительного обозначения: уменьшить сроки, повысить качество проверки и минимизировать человеческое влияние на результат.

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

Задачи исследования:

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

МАТЕРИАЛЫ И МЕТОДЫ

Источниками информации в области товарных знаков и их государственной регистрации выступили Руководство по осуществлению административных процедур и действий в рамках предоставления государственной услуги по регистрации товарного знака [6] и четвертая часть Гражданского кодекса Российской Федерации [5]. В качестве источника информации о метриках измерения расстояния между последовательностями были использованы научные труды российских и зарубежных ученых. Для поиска и проведения литературного обзора научных статей были использованы ресурсы поисковой системы eLIBRARY, поиск проведен по вышеуказанным ключевым словам. Для поиска и анализа программных кодов, реализующих расчет метрик расстояния, были использованы веб-сервисы, позволяющие просматривать исходные коды программ [7]. Для оценки применимости и эффективности использования различных метрик расстояния между последовательностями были рассчитаны следующие величины: расстояние Хэмминга, расстояние Левенштейна, расстояние Джаро – Винклера, мера Серенсена.

РЕЗУЛЬТАТЫ И ИХ ОБСУЖДЕНИЕ

В ходе проведения исследования была найдена и рассмотрена статья: «Актуальные задачи анализа изображений», подтверждающая актуальность выбранной темы. В статье авторы (А. И. Либерман и Т. Э. Шульга) представляют обзор современного состояния интеллектуального анализа изображений, рассматривают сферы применения анализа изображений и анализируют методы искусственного интеллекта для решения различных практических задач. Авторы приходят к выводу о возможности комбинации методов анализа изображений и онтологического моделирования с целью дальнейшего развития области анализа изображений [8].

Е. Ю. Коломийцева в статье «Анализ изображений в интернете: возможности современных сервисов» рассматривает анализ изображений с помощью искусственного интеллекта с точки зрения применимости и ценности в области журналистской работы. Автор приводит примеры параметров изображений, которые в настоящее время можно анализировать с использованием современных сервисов, например, такие параметры как определение шрифта, определение того, что изображено на фото, распознавание эмоций человека, определение личности человека и другое [9].

В статье «Анализ изображений. Определение дубликатов и степени размытости изображений», автором которой является Д. В. Шестоперов, было предложено решение проблемы затрудненного поиска фотографий в большом файловом хранилище, не имеющем фильтрации – анализ изображений и удаление неподходящих фотографий с использованием алгоритма разностного хеширования и сравнения хэшей при помощи расстояния Хэмминга для поиска дубликатов изображений [10].

Л. К. Ситниковой, М. О. Еланцевым и Р. О. Султановым в статье «Двухэтапный метод поиска изображений в большой базе изображений» были зафиксированы результаты анализа способов поиска в базе данных большого размера. Авторами был сделан вывод о том, что совместное применение метода сравнения по перцептивному хэшу и метода классификации при помощи нейронной сети является наиболее эффективным [11].

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

Метрики и алгоритмы, позволяющие оценить различие или сходство исследуемых объектов:

1. Расстояние Хэмминга – метрика различия объектов одинаковой размерности; метрика измерения расстояния между двумя последовательностями. Метрикой для определения меры различия между двоичными векторами в векторном пространстве кодовых последовательностей – расстоянием Хэмминга d (x; y) между двумя двоичными последовательностями – векторами: xи y, длины n – называется число позиций, в которых они различны. В общем виде расстояние Хэмминга для объектов и размерностей задается функцией [12]:

 (1)

2. Расстояние Левенштейна – метрика сходства между двумя последовательностями; метрика измеряющая по модулю разность между двумя последовательностями символов. Расстояние Левенштейна определяется как минимальное количество односимвольных операций – вставки, удаления, замены, необходимых для превращения одной последовательности элементов в другую. Пусть S₁и S₂ – две строки некоторого алфавита, длины которых M и N соответственно, тогда расстояние Левенштейна d (S₁, S₂), можно рассчитать по формуле:

 (2)

где m (a, b) равна нулю, если a = b и единице в противном случае min {a, b, c} возвращает наименьшее из аргументов. Шаг по i символизирует удаление из первой строки, по j – вставку в первую строку, а шаг по обоим индексам символизирует замену символа или отсутствие изменений [13].

3. Сходство Джаро – Винклера – мера схожести для измерения расстояния между двумя последовательностями символов.

Расстояние Джаро – Винклера – это минимальное число односимвольных преобразований, которое необходимо для того, чтобы изменить одно слово в другое. Чем меньше расстояние Джаро – Винклера d_w для двух последовательностей, тем больше сходства имеют эти последовательности друг с другом. Результат нормируется так, что d_w = 0 – отсутствие сходства, d_w = 1 – точное сходство. Сходство Джаро – Винклера равно 1 – d_w.

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

Пусть S₁ и S₂ – две строки, расстояние Джаро – Винклера d_w можно рассчитать по формуле:

d_w = d_j + (l_p (1 – d_j)), (3)

где d_j – расстояние Джаро для строк S₁ и S₂;

l – длина общего префикса от начала строки до максимума четырех символов;

p – постоянный коэффициент масштабирования, использующийся для того, чтобы скорректировать оценку в сторону повышения для выявления наличия общих префиксов: p = const = 0,1 [14].

4. Коэффициент Серенсена – бинарная мера сходства. Коэффициент Серенсена создан для определения схожести любых множеств. Коэффициент Серенсена K_sрассчитывается по формуле:

 (4)

где a – количество видов первой экосистемы;

b – количество видов второй экосистемы;

c – количество общих для 1-й и 2-й экосистемы видов [15].

5. Алгоритм SIFT (масштабно-инвариантная трансформация признаков) – алгоритм выявления признаков в компьютерном зрении для выявления и описания локальных признаков в изображениях.

Первостепенно в алгоритме SIFT извлекаются ключевые точки объектов из набора изображений и запоминаются в базе данных. Заданный объект в новом изображении распознается путем сравнения признаков из нового изображения с признаками из базы данных и нахождения признаков-кандидатов на основе евклидова расстояния между векторами признаков. Ключевые точки отбираются из набора соответствий в новом изображении, на основании наиболее близкого сходства с объектом по его местоположению, масштабу и ориентации. Подходящие блоки признаков определяются с помощью реализации хэш-таблицы обобщенного преобразования Хафа, каждый согласующийся с объектом блок из трех или более признаков подлежит дальнейшей подробной проверке. Резко отклоняющиеся блоки признаков отбрасываются. Определяется набор признаков, который с высокой вероятностью подтвердит наличие искомого объекта на рассматриваемом изображении [16].

6. Перцептивный хэш-алгоритм. Хэш-алгоритмы основаны на генерации сравнимых хэшей. Данные, используемые для генерации хэша, выполняют роль источника случайных чисел – одинаковые данные дадут одинаковый результат, разные данные – разный результат. Характеристики изображений используются для генерации индивидуальных отпечатков, которые можно сравнивать друг с другом. Выводы, которые можно сделать на основании сравнения хэшей: хэши отличаются – данные разные; хэши совпадают – данные одинаковые. Изменение размера, соотношения сторон и цветовых характеристик (яркость, контраст и т. д.) сравниваемых изображений не повлияет на результат вычисления перцептивного хэша.

Этапы получения перцептивного хэша:

– уменьшение размера рассматриваемого изображения;

– перевод изображения в градации серого;

– вычисление среднего значения яркости получившегося изображения;

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

– построение хэша, перевод полученных отдельных значений в одно 64-битное значение [17].

На основании рассмотренных выше методов были разработаны алгоритмы для сравнения логотипов с целью проверки их уникальности. Основой для алгоритмов выступили шесть методов: расстояние Хэмминга, расстояние Левенштейна, сходство Джаро – Винклера, коэффициент Серенсена, SIFT и метод перцептивной хэш-суммы с последующим вычислением расстояния Хэмминга для сравнения. Методы реализованы на языке программирования Python с использованием библиотек: OpenCV, NumPy, Editdistance, Strsimpy и ImageHash.

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

Расстояние Левенштейна было реализовано с помощью алгоритма Дамерау – Левенштейна, который позволяет находить минимальное количество операций редактирования, необходимых для превращения одной строки в другую, реализован с применением библиотек: Editdistance, NumPy.

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

Алгоритм, основанный на расчете коэффициента Серенсена, реализован как отношение числа общих символов в строках к общему числу символов, с применением библиотек: Strsimpy, NumPy.

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

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

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

Разработанными программами были обработаны четыре пары логотипов, размером 1024 × 1024 пикселя:

1) полностью черный/полностью белый (далее – черно-белые);

2) существующий логотип/его инвертированная версия (далее – инвертированные);

3) существующий логотип/точно такой же существующий логотип (далее – идентичные);

4) существующий логотип/другой существующий логотип (далее – разные).

Результаты тестирования представлены в табл. 1. Сходство логотипов изменяется в процентах, где 100 % – полное сходство, 0 % – отсутствие сходства.

Результаты работы программ подтверждают корректную работу алгоритмов: черно-белые логотипы – 0 % сходства, идентичные алгоритмы – 100 % сходства. Результаты сравнения инвестированной пары логотипов: расстояние Хэмминга – 0 % сходства, SIFT – 4 %, расстояние Левенштейна – 17 %, коэффициент Серенсена – 23 %, сходство Джаро – Винклера – 33 %, перцептивный хэш-алгоритм – 38 %. Результаты сравнения разных логотипов существенно отличаются: расстояние Хэмминга, расстояние Левенштейна и хэш-сумма – 60–70 % сходства, сходство Джаро – Винклера – 87 %, коэффициент Серенсена – 13 %, SIFT – 1 % сходства.

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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