Недавно, в связи с разработкой новой линейки продукции, в нашей компании встала задача поиска идентичных изображений в базе.
Отдавать реализацию на аутсорс слишком дорого и не гарантирует наилучшего решения. Отдать на откуп фрилансеру — дешевле, но и решение скорее всего будет таким же дешевым и основанным на существующих библиотеках, типа OpenCV. Но если бы задача решалась так просто, то конкуренты уже давно бы этим воспользовались и сделали достойный продукт, но его на рынке нет. В общем, присущие нам перфекционизм, амбициозность и желание быть лучшими, не позволяют нам выводить на рынок продукт «как у всех», нам нужно лучше, быстрее, сильнее. Приняли решение самостоятельно разобраться в вопросе, выработать решение, написать подробное техническое задание и уже отдать на реализацию фрилансеру. Была надежда, что существуют готовые решения, которых просто не заметили конкуренты. Но изучив вопрос (а вместе с ним и алгоритмы ORB, BRIEF, FAST, SIFT, SURF, BRISK, A-KAZE, Viola-Jones и еще несколько) стало понятно, что у всех этих алгоритмов есть свои недостатки. Хотя для решения нашей задачи некоторые из вышеперечисленных алгоритмов и подходили, но как то неожиданно захотелось уникальности и простоты решения. И вот выношу на суд сообщества, алгоритм собственного сочинения.
Любителей покритиковать (конструктивно) прошу под кат.
Изначально, и это принципиально, был выбран способ сравнения изображений основанный на поиске и сравнении т.н. ключевых точек.
Как и любой (или практически любой) алгоритм подобного рода, мой состоит из следующих шагов.
Шаг 1. Поиск ключевых точек на изображении.
Шаг 2. Формирование дескриптора.
Шаг 3. Формирование бинарной строки (хэша).
Шаг 4. Сравнение хэшей обрабатываемого изображения с хэшами изображений хранящимися в БД.
Шаг 5. Получение результата в требуемом виде.
Для поиска особых точек я использую «Детектор FAST» как лучший по соотношению скорость работы к качеству, хотя для других задач можно использовать и другие детекторы.
Далее с помощью «Детектора углов Харриса» отбираем не большое (у меня это 50) количество самых значимых ключевых точек.
* С принципами работы детекторов FAST и Харриса, можно ознакомиться в интереснейшей статье lightsource "Детекторы углов".
На этом шаге, я предлагаю отойти методов описания ключевых точек, которые обычно используются в подобных алгоритмах и обратиться к более простым методам.
Я предлагаю, вместо того, чтобы описывать каждую ключевую точку через ее окружение, измерить расстояния от каждой такой точке к оставшимся точкам. Т.е. проложить все возможные отрезки между найденными точками и измерить их длинны.
Так вот, такое полученное, в результате измерения, число (длину отрезка), я и предлагаю называть дескриптором.
Как известно через Х точек можно проложить Х*(Х-1)/2 отрезков, т.е. из 50 точек можно составить 50*49/2=1225 отрезков. Т.е. наша строка будет состоять из 1225 целых чисел. Причем эти числа должны иметь одинаковое количество знаков. Требуемое количество знаков, выбирается исходя из разрешения изображения (например, для изображения 500*500 максимальна длина отреза 707 (по диагонали), а значит знаков должно быть 3).
Для достижения инвариантности к повороту в плоскости, запишем длинны отрезков в строчку не по мере их вычисления, а от большего к меньшему.
Получим строку: А1, А2,..., А1225, где А1>А2>...>А1225
Для поиска подобных изображений в БД нужно сравнить полученный нами хэш А1, А2,..., А1225 с хранящимися в БД.
Для примера сравним хэш А1, А2,..., А1225, где А1>А2>...>А1225 с В1, В2,..., В1225 причем пусть дескрипторы А трехзначны, а дескрипторы В четырех. Это может быть в двух случаях, если изображения разные или если одно изображения в разных масштабах.
Для достижения инвариантности к масштабу приведем каждый дескриптор к единому масштабу. Для этого определяем максимальное число М той же разрядности, что и разрядность большего дескриптора (для нашего примера максимальное четырехзначное число М = 9999) и находим коэф. масштабирования К по формуле: Ка=М/А1 (для строки А1, А2,..., А1225) и Кв=М/В1 (для строки В1, В2,..., В1225). Далее приведем хаши к единому масштабу, для это перемножим каждый дескриптор хэша А на Ка, а каждый дескриптор хэша В на Кв. Запишем результаты в строки А'1, А'2,..., А'1225 и В'1, В'2,..., В'1225, округляя значения до целого числа. В результате получим 2 хэша одного масштаба и одной размерности.
Теперь строки А'1, А'2,..., А'1225 и В'1, В'2,..., В'1225 можно сравнивать. Для этого будем использовать модифицированную формулу расстояния Хемминга.
Дело в том, расстояние Хемминга учитывает количество ошибок, как количество не равных значений в строках. Но мы на предыдущем шаге применили округление до целого числа, что может привести к ложным результатам. Поэтому мы не будем считать ошибкой, если значения соответствующих дескрипторов строк А и В, отличаются на Е (т.е. разность Аi и Вi взятая по модулю должна быть больше Е, для того, что бы считать значения в строках не равными). Назовем Е «коэф. лояльности» и в общем случае принимаем Е=1.
Далее простым суммированием считаем количество ошибок. Получаем расстояние Р.
Для разных задач, может понадобится разное представление результатов работы алгоритма.
* С удовольствием приму к сведению, ваши комментарии с указанием недостатков алгоритма, с тем, что бы его доработать.
Не являясь программистом, я не имею возможности самостоятельно проверить алгоритм в работе. Буду рад, если кто-то из членов Хабра-сообщества, сможет реализовать программно этот алгоритм и протестировать его в работе.
После такой проверки мы сможем отнести самый важный параметр «точность работы» к достоинствам или недостаткам моего алгоритма.
1. "Детекторы углов" — lightsource
2. "Сравнительный анализ дескрипторов особых точек изображений с внедрением алгоритмов под операционной системой «Android» — Патин М.В.
3. "Кеширование", wikipedia.org
P.S. Второй (улучшенный) вариант алгоритма: habrahabr.ru/post/320994
Отдавать реализацию на аутсорс слишком дорого и не гарантирует наилучшего решения. Отдать на откуп фрилансеру — дешевле, но и решение скорее всего будет таким же дешевым и основанным на существующих библиотеках, типа OpenCV. Но если бы задача решалась так просто, то конкуренты уже давно бы этим воспользовались и сделали достойный продукт, но его на рынке нет. В общем, присущие нам перфекционизм, амбициозность и желание быть лучшими, не позволяют нам выводить на рынок продукт «как у всех», нам нужно лучше, быстрее, сильнее. Приняли решение самостоятельно разобраться в вопросе, выработать решение, написать подробное техническое задание и уже отдать на реализацию фрилансеру. Была надежда, что существуют готовые решения, которых просто не заметили конкуренты. Но изучив вопрос (а вместе с ним и алгоритмы ORB, BRIEF, FAST, SIFT, SURF, BRISK, A-KAZE, Viola-Jones и еще несколько) стало понятно, что у всех этих алгоритмов есть свои недостатки. Хотя для решения нашей задачи некоторые из вышеперечисленных алгоритмов и подходили, но как то неожиданно захотелось уникальности и простоты решения. И вот выношу на суд сообщества, алгоритм собственного сочинения.
Любителей покритиковать (конструктивно) прошу под кат.
1. Принцип работы алгоритма
Изначально, и это принципиально, был выбран способ сравнения изображений основанный на поиске и сравнении т.н. ключевых точек.
Как и любой (или практически любой) алгоритм подобного рода, мой состоит из следующих шагов.
Шаг 1. Поиск ключевых точек на изображении.
Шаг 2. Формирование дескриптора.
Шаг 3. Формирование бинарной строки (хэша).
Шаг 4. Сравнение хэшей обрабатываемого изображения с хэшами изображений хранящимися в БД.
Шаг 5. Получение результата в требуемом виде.
2. Описание работы алгоритма
2.1. Поиск ключевых точек на изображении.
Ключевая (особая точка, или особенность) – это точка изображения, удовлетворяющая ряду свойств:
- Определенность (distinctness) – особенность должна выделяться на фоне среди соседних точек.
- Устойчивость (repeatability) – изменение яркости, контрастности и цветовой гаммы не должны влиять на место особой точки на объекте или сцене.
- Стабильность (stability) –зашумленность изображения, не превышающая определенный порог, не должна влиять на работу детектора.
- Интерпретируемость (interpretability) – особые точки должны быть представлены в формате, пригодном для дальнейшей работы.
- Количество (quantity) – количество обнаруженных особых точек должно обеспечивать требуемому их количеству для обнаружения объектов.
Для поиска особых точек я использую «Детектор FAST» как лучший по соотношению скорость работы к качеству, хотя для других задач можно использовать и другие детекторы.
Далее с помощью «Детектора углов Харриса» отбираем не большое (у меня это 50) количество самых значимых ключевых точек.
* С принципами работы детекторов FAST и Харриса, можно ознакомиться в интереснейшей статье lightsource "Детекторы углов".
2.2. Формирование дескриптора
Дескриптор (от лат. descriptor — описывающий) – описание особой точки, определяющее особенности её окрестности, представляет собой числовой или бинарный вектор определенных параметров. Длина вектора и вид параметров определяются применяемым алгоритмом. Дескриптор позволяет выделить особую точку из всего их множества на изображении, это необходимо для составления ключевых пар особенностей, принадлежащих одному объекту, при сравнении разных изображений.
На этом шаге, я предлагаю отойти методов описания ключевых точек, которые обычно используются в подобных алгоритмах и обратиться к более простым методам.
Я предлагаю, вместо того, чтобы описывать каждую ключевую точку через ее окружение, измерить расстояния от каждой такой точке к оставшимся точкам. Т.е. проложить все возможные отрезки между найденными точками и измерить их длинны.
Так вот, такое полученное, в результате измерения, число (длину отрезка), я и предлагаю называть дескриптором.
2.3. Формирование хэша
Хеширование или хэширование (англ. hashing) — преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины, выполняемое определённым алгоритмом. Функция, реализующая алгоритм и выполняющая преобразование, называется «хеш-функцией» или «функцией свёртки». Исходные данные называются входным массивом, «ключом» или «сообщением». Результат преобразования (выходные данные) называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».
Как известно через Х точек можно проложить Х*(Х-1)/2 отрезков, т.е. из 50 точек можно составить 50*49/2=1225 отрезков. Т.е. наша строка будет состоять из 1225 целых чисел. Причем эти числа должны иметь одинаковое количество знаков. Требуемое количество знаков, выбирается исходя из разрешения изображения (например, для изображения 500*500 максимальна длина отреза 707 (по диагонали), а значит знаков должно быть 3).
Для достижения инвариантности к повороту в плоскости, запишем длинны отрезков в строчку не по мере их вычисления, а от большего к меньшему.
Получим строку: А1, А2,..., А1225, где А1>А2>...>А1225
2.4. Сравнение хэша с БД
Для поиска подобных изображений в БД нужно сравнить полученный нами хэш А1, А2,..., А1225 с хранящимися в БД.
Для примера сравним хэш А1, А2,..., А1225, где А1>А2>...>А1225 с В1, В2,..., В1225 причем пусть дескрипторы А трехзначны, а дескрипторы В четырех. Это может быть в двух случаях, если изображения разные или если одно изображения в разных масштабах.
Для достижения инвариантности к масштабу приведем каждый дескриптор к единому масштабу. Для этого определяем максимальное число М той же разрядности, что и разрядность большего дескриптора (для нашего примера максимальное четырехзначное число М = 9999) и находим коэф. масштабирования К по формуле: Ка=М/А1 (для строки А1, А2,..., А1225) и Кв=М/В1 (для строки В1, В2,..., В1225). Далее приведем хаши к единому масштабу, для это перемножим каждый дескриптор хэша А на Ка, а каждый дескриптор хэша В на Кв. Запишем результаты в строки А'1, А'2,..., А'1225 и В'1, В'2,..., В'1225, округляя значения до целого числа. В результате получим 2 хэша одного масштаба и одной размерности.
Теперь строки А'1, А'2,..., А'1225 и В'1, В'2,..., В'1225 можно сравнивать. Для этого будем использовать модифицированную формулу расстояния Хемминга.
Дело в том, расстояние Хемминга учитывает количество ошибок, как количество не равных значений в строках. Но мы на предыдущем шаге применили округление до целого числа, что может привести к ложным результатам. Поэтому мы не будем считать ошибкой, если значения соответствующих дескрипторов строк А и В, отличаются на Е (т.е. разность Аi и Вi взятая по модулю должна быть больше Е, для того, что бы считать значения в строках не равными). Назовем Е «коэф. лояльности» и в общем случае принимаем Е=1.
Далее простым суммированием считаем количество ошибок. Получаем расстояние Р.
2.5. Получение результатов
Для разных задач, может понадобится разное представление результатов работы алгоритма.
2.5.1. Оценка схожести 2х изображение
Результатом будет показ вычисленного на шаге 2.4. расстояния 2х хэшей Р. Или их оценочное значение. Например, при Р<10 можно считать, что изображения идентичны; при 10<Р<100 — изображения похожи; и т.д.2.5.2. Поиск изображения в БД максимально похожего на исследуемое
Результатом будет вывод изображения (или изображений) имеющего наименьшее значения расстояния Р. Или вывод сообщения, что изображений подобных искомому не найдено, если все расстояния Р больше определенного порога.3. Достоинства и недостатки алгоритма
3.1. К достоинствам приведенного алгоритма можно отнести:
- Простоту,
- Высокую скорость работы,
- Гибкость (можно применять различные методы поиска ключевых точек, в зависимости от задачи, характеристик изображения и необходимой точности).
- Возможность применять для изображений разного качества, благодаря коэф. лояльности Е.
- Инвариантность к повороту и масштабированию изображения.
3.2. К недостаткам я бы отнес:
- Отсутствие инвариантности к искажениям перспективного характера. Хотя в некоторой степени этого можно достичь если разделить исходное изображение на не большие фрагменты и увеличить коэф. Е.
- Не возможность поиска куска изображения в большом изображении.
* С удовольствием приму к сведению, ваши комментарии с указанием недостатков алгоритма, с тем, что бы его доработать.
3.3. Неопределенность
Не являясь программистом, я не имею возможности самостоятельно проверить алгоритм в работе. Буду рад, если кто-то из членов Хабра-сообщества, сможет реализовать программно этот алгоритм и протестировать его в работе.
После такой проверки мы сможем отнести самый важный параметр «точность работы» к достоинствам или недостаткам моего алгоритма.
Ссылки:
1. "Детекторы углов" — lightsource
2. "Сравнительный анализ дескрипторов особых точек изображений с внедрением алгоритмов под операционной системой «Android» — Патин М.В.
3. "Кеширование", wikipedia.org
P.S. Второй (улучшенный) вариант алгоритма: habrahabr.ru/post/320994
