Недавно, в связи с разработкой новой линейки продукции, в нашей компании встала задача поиска идентичных изображений в базе.
Отдавать реализацию на аутсорс слишком дорого и не гарантирует наилучшего решения. Отдать на откуп фрилансеру — дешевле, но и решение скорее всего будет таким же дешевым и основанным на существующих библиотеках, типа 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
Поделиться с друзьями
aslepov78
Начну с похвал. Вы молодец что:
— не пустились в эвристический маразм с нейронными сетями,
— провели обзор методов для себя,
— увидели геометрическую природу задачи (особые точки).
Теперь критика:
— Не увидел конкретной модели изображения. Вы придумываете серебряную пулю на любое изображение, и это тупик, ибо любые данные можно считать изображением.
— «Не являясь программистом, я не имею возможности..». Увы, в этом деле надо быть или программистом или математиком. Даже так — математиком знающим основные эффективные структуры данных и алгоритмы. А это снова быть программистом.
— Идея с хэшем боюсь тупиковая. Конечно, если вы из картинки выведите структуру вроде «кошка, в углу,… поворот» то получите весь арсенал аля SQL запросов. Но так и самая трудность в том чтобы вывести структуру из картинки.
Чтобы это понять почитайте вычислительную геометрию, например задачу поиска ближайшей точки. Там есть свои эффективные структуры, но не хэш в лоб.
А вообще — спасибо за статью, где нет нейросетей, машинленинга, и боже упаси — генетического программирования.
bezdolgoff
Рад, что простота еще в цене в наше время!
mephistopheies
а сколько нужно кармы что бы человек не мог коментить?
bezdolgoff
К чему Ваш вопрос?
mephistopheies
к тому, что бы узнать сколько кармы нужно, для того что бы не писать тупые коменты
bezdolgoff
Думаю это нужно в правилах почитать.
А по поводу, оценки комментариев — это субъективно.
mephistopheies
ну вот я субъективно проголосовал, надеюсь он уже не сможет коментить
devpony
О господи, кто-то обидел нейронные сети, нужно срочно-срочно мстить и писать гневные комментарии.
bask
ЧТОБЫ
BelBES
Эвристический маразм без сетей, как в посте, конечно намного лучше...
aslepov78
Конечно лучше. Лучше хотя бы тем что пытаются работать с предметной областью понятиями самой предметной области.
BelBES
Имхо, аргумент в стиле "всё лучше, чем по подъездам клей нюхать"...DDD — это прогресс, а решение задач методом нагромождения эвристик — это поиск вчерашнего дня.
aslepov78
Аргумент в том же стиле что и ваш коммент. Я и не защищаю эвристики, хотя без них никуда. Причем тут DDD? Тема статьи — алгоритмы CV, я думал.
BelBES
К вопросу об общем подходе решения CV задач: берем кучу данных и разрабатываем алгоритм, который сам найдет в них закономерности. Глупо изобретать одну чудо-эвристику руками, когда компьютер может проверять их тысячами за короткий промежуток времени и выбирать лучшие.
aslepov78
Ну понятно )) Ваш метод на столько же гениален на сколько бесполезен.
Еще раз говорю — я не за эвристики. Я бы предпочел точные методы вроде метода сортировки со сложностью NLogN. Кстати попробуйте найти таковой вашей методой перебора. Думаю даже в ваших переборах вы используете эвристики для сокращения перебора… Так что вообще не понимаю о чем спор.
BelBES
Современный ML смотрит на вас с изумлением...
А что тогда по вашему из себя представляет метод, описаный в посте?
aslepov78
В посте смесь эвристики и логики. Покажите мне хоть одну статью по ML где нет эвристики.
Разделение точек на плоскости прямой на два класса — и то становится эвристикой сразу как только вы подменяете 2д пространство на пространство параметров предметной области. А метод между тем пришел из чистой прикладной геометрии. Так что не надо гнобить эвристику, особенно в контексте ML.
BelBES
Я и не гноблю, лишь утверждаю, что ваше утверждение:
не соответсвует современной действительности, т.к. обучающиеся алгоритмы придумывают эвристики и ищут закономерности в данных более успешно, чем это делает человек.
А что касается конкретной задачи, ну я ей занимался еще тогда, когда про Deep Learning и не слышно было. Даже на хабре об этом писал как-то, и сравнивая эффективность как современных подходов, так и того, что было до них, считаю, что ML тут является безоговорочным победителем.
aslepov78
Это глупость. Алгоритмы ML не ищут эвристики и не могут искать (смотреть определение эвристики). ML, в лучшем случае, делает перебор некоторого множества алгоритмов, поиск оптимальных параметров. И именно в этом поиске заложена эвристика, но никак не в результате того что она там найдет. И как раз этот перебор нынче модно называть «обучение». Хотя с бытовым пониманием обучения никакой связи.
Рад за вас
BelBES
"Эвристический алгоритм (эвристика) — алгоритм решения задачи, включающий практический метод, не являющийся гарантированно точным или оптимальным, но достаточный для решения поставленной задачи. Позволяет ускорить решение задачи в тех случаях, когда точное решение не может быть найдено." (Википедия)
В каком месте расхождение? Именно это и происходит в процессе обучения тех-же глубоких сетей.
jetcar
а что не так с машинным обучением? всё равно надо параметры подкручивать, а так вместо подбора ручками алгоритм сам найдёт оптимальные параметры
aslepov78
Вы любую подкрутку параметров называете ML-ем? Методов оптимизации море: переборы, град спуски,… нейросети будь они неладны. Поиск минимума параболы — это тоже оптимизация, но вы же не будете обучать нейросеть для этого. Вы просто решите квадратное уравнение. В другом случае будет достаточно перебора… Я к тому что все с ума посходили на ML и перестали видеть простые эффективные решения.
Dark_Daiver
>Методов оптимизации море: переборы, град спуски,… нейросети будь они неладны.
Мммм, а как можно оптимизировать нейросетями?
aslepov78
Обучение алгоритма = оптимизация его параметров или структуры.
jetcar
ну многие программисты не мега математики, мне например в разы проще написать сложный алгоритм чем функцию которая посчитает тоже самое, ну и ML оно более гибкое как мне кажется, надо научиться находить лица даёшь кучу фоток лиц и оно само научиться, надо находить машины почистил всё и дал кучу фоток машин, ничего не переписывая оно само заработает.
devpony
Опять велосипеды… А вы смотрели вот эту статью: https://arxiv.org/abs/1306.3855? Их подход опережает все существующие алгоритмы на порядок и позволяет, например, при выделении региона изображения найти в базе крупные фотографии этого региона или, например, найти все фотографии, где объект, являющийся главным на текущей фотографии, на другой представляет лишь малую часть. Таким образом можно «отдалить» вид от часов на кремле до вида Москвы с птичьего полета и «приблизить» обратно. Естественно, с поиском просто похожих фотографий справляется великолепно. В статье так же предложены оптимизации для мгновенного поиска в базе по 10^7 изображениям.
devpony
Случайно скинул первую статью авторов. Вот вторая, где описано то, о чём я говорил: https://arxiv.org/abs/1503.02619.
bezdolgoff
Спасибо за ссылку!
devpony
del
DOLARiON
Класс!
Не в курсе, а нету ли программной реализации данного алгоритма?
devpony
Есть у авторов (показывали на лекции) и, если не изменяет память, они её продают.
bezdolgoff
Бесплатно вроде распространяют, по крайней мере, на странице авторов http://cmp.felk.cvut.cz/wbs есть ссылки на исходники, наборы данных, документацию.
devpony
Спасибо за уточнение, буду знать.
bezdolgoff
Вот здесь: https://github.com/ducha-aiki/mods
bezdolgoff
А вот статья https://arxiv.org/abs/1504.06603 с их более мощным (по заявлениям авторов) алгоритмом.
Вообще, интересные варианты алгоритмов. Но все нужно проверять, думаю, протестируем их для нашей задачи, совместно с другими алгоритмами.
devpony
У вас в компании нет программистов? Почему вы рассказываете свой алгоритм сначала нам, а не коллегам? Вдруг он не решает вашу бизнесс-задачу?
bezdolgoff
Программисты есть, но пока эта задача не выносилась… Всему свое время.
А разместил здесь, что бы получить отклик профессионалов и любителей, после чего доработать свою теорию или отказаться от нее.
mikkab
После того как вы отобрали «50 самых значимых точек» для данного изображения, вы уже потеряли данные о таких же изображениях, но с чуть другой яркостью или цветом. Дальше при формировании дескриптора вы увеличили ошибку из-за не тех точек. Хеш это все усугубил невероятным размером, а округления на поиске еще раз увеличили ошибку. Поиск и сравнение в таком виде даже среди небольшого числа данных потребует порядочно мощьностей, а результат будет никакой.
bezdolgoff
Как раз выбор самых значимых точек, предполагает, что эти точки можно, с большой долей вероятности, найти на изображениях с некоторыми изменениями.
А настраеиваемый уровень сходства (расстояние Хемминга), как раз позволяет компенсировать случайное несовпадение некоторых точек.
Если отобрать не 50 точек, а скажем 10, то он будут еще более значимыми и размер хэша будет меньше. Все зависит от конкретной задачи.
mikkab
Попробуйте на произвольной картинке поискать 50 или 10 «наиболее значимых точек» и тоже самое на такой же картинке, но с другими параметрами цвета, яркости или просто после минимальной обработки. они могут и будут отличатся.
компенсации тут никакой нет, тк идет явный поиск 1 к 1, в противном случае сложность увеличивается на число точек, тк они все могут быть невалидны и придется их всех проверять. те сложность увеличивается в вашем случае в минимум 50*50 раз…
bezdolgoff
Предположим, что из 50 точек, только 45 совпали на 2х изображения, как ключевые. Остальные 5 (вернее по 5 на каждом изображении) определены ошибочно, т.е. по разному на каждом изображении.
Тогда получем 990 отрезков с одинаковой длинной и 235 с разной.
Если выставим допустимое расстояние больше 235 то изображения будут считаться одинаковыми, если меньше чем 235 то разными. Зачем каждую точку отдельно проверять?
vasiliev
Но ведь после сортировки общие 990 длин отрезков вовсе не обязаны оказаться на тех же положениях в обоих дескрипторах, не так ли? Ведь между ними окажутся некоторые из оставшихся 235 отрезков.
bezdolgoff
Вот это ценное замечание. Спасибо!
Есть над чем подумать.
sleeply4cat
Забавно.
Для поиска фрагмента кадра из фильма я просто разбил фильм на кадры, пожал каждый из них до 200*200, подсчитал среднюю яркость для строк и столбцов. Итого вышло по 400 байт на кадр. Затем получил такие же 2 вектора для входного фрагмента. И затем в цикле пробежался по всем ранее просчитанным кадрам, находя произведение «похожестей» векторов.
В среднем, имея на вход 50% площади кадра с небольшими искажениями, программа выдавала его в топ10. На обработку 1 млн записей в 8 ненастоящих потоков уходило секунд 20 (все данные влезли в RAM).
не знаю, зачем я это написал, просто как вариант неточного, но довольно быстрого велосипеда)
aslepov78
Ваш велосипед справляется только с аддитивным шумом. Собсна классика обработки сигнала (копать в сторону корреляции). А теперь добавьте нелинейные искажения вроде поворота, скалинга, изменения освещения сцены — и приплыли.
sleeply4cat
Скалинг обрабатывается правильно, оси Х и У сравниваются отдельно в разных масштабах. Удивительно, но это сработало.
Яркость тоже можно починить. Сделав, например, её не абсолютной, а относительной по кадру.
Вообще, софтина писалась за два вечера на спор и предназначена была именно для поиска кадра по частичному скриншоту, без поворота и прочих искажений, так что свою задачу она выполнила на все сто :)
p.s. как я мучался с 350 гб картинок — это отдельный вопрос.
aslepov78
Ну если вы скалинг перебором подстраиваете — конечно но проблем. Вообще то любые искажения не помеха если перебором все искать. В том то и беда что перфоманса CPU всегда мало.
sleeply4cat
Не было бы скалинга — загнал бы в
SQLБД и искал напрямую. А так да, перебором. Но с учётом упаковки картинки в 2 предпросчитанных вектора всё оказалось не так страшно.Пытался засунуть обсчёт на видеокарту через aparapi, но всё упёрлось в шину и оказалось раз в 10 медленнее, чем на CPU. Возможно, имей я прямые руки и дрова с нормальной поддержкой OpenCL, что-то и вышло бы, но увы.
IliaSafonov
В статьях подобная задача обсуждается последние лет 20. Рекомендую поискать по ключевым словам «near duplicate detection» and (image or photo). Замечу, что во многих статьях начальные этапы обработки часто совпадают с предлагаемыми в посте. Считаю, что стоит поздравить автора: он свой «велосипед» изобретает в правильном направлении.
Однако, подробно обсуждать предлагаемое решение я не вижу смысла, так как задача не поставлена более-менее чётко. О какого рода изображениях идет речь? Согласен с первым комментарием, что не существует универсальных подходов. Упоминаемые в комментария выше статьи про matching прекрасно работают для обычных бытовых фото, но попробуйте их применить для мэтчинга регулярных текстур или, например, изображений слоёв травления в микроэлектронике. По моему опыту они не работают.
Что значит «похожие»? Согласитесь (или посмотрите в существующих статьях), что формулировка может быть достаточно разной.
Сколько изображений всего уже сейчас или ожидается когда-либо?
Как Вы собираетесь считать точность и какого уровня рассчитываете достичь?
Сколько времени Вы можете себе позволить заниматься разработкой, реализацией и тестированием алгоритма?
Без ответа на хотя бы часть из этих вопросов маловероятно ожидать конструктивного обсуждения предлагаемого подхода. Хотя ссылок «а вот посмотрите еще сюда» «а вот посмотрите еще сюда», накидают, что, конечно, тоже полезно.
babylon
Мой комментарий к статье скуп и прямолинеен. Не делайте так как предлагается в статье. Есть ли универсальные способы представления, кодирования и поиска любых изображений? Есть. Но это не то что предлагает автор. Совсем не то. Статья имеет больше отношения к неспецифическому помехоустойчивому кодированию и поиску, чем к кодированию и поиску собственно изображений. А там есть нюансы и их немалое количество.
BalinTomsk
Обычно для это пользуется поиск по гистограммам если не лезть глубоко в распознование обьектов.
Harddriver
Думаю самый простой метод поиска идентичных изображений — поиск по гамме. Минусы — обманывается зеркалированием, но можно добавить ф-цию «искать в отраженных».
arcman
Вам стоит обратить внимание на перцептивный хэш, он решает схожую задачу:
https://habrahabr.ru/post/120562/
Это самый быстрый способ поиска дубликатов изображений и на его основе можно сделать много интересных приложений, например детектирование движения в кадре.
sleeply4cat
Там в статье всё плохо и алгоритм упрощён до безобразия, смотрите комментарии.
arcman
У нас этот алгоритм прекрасно работал. Видимо у кого то есть свои специфические задачи для которых этот алгоритм не подходит.
Автору однозначно стоит попробовать его на своей выборке, благо реализация уже готова.
589
Друзья, а если расчёт основных точек производить опираясь на «эталон» Подскажите, пожалуйста центр изображения может быть таким «эталоном»? Может быть «эталоном» стоит принять точку с определёнными параметрами освещённости. А перед поиском «эталона» освещённость изображения изменять до 50%
П.С. Прошу, смеяться без злобы. Я юрист, для меня 1+1 будет три. Три знака)))) С уважением, Елисей.
Dark_Daiver
Если изображение и это же изображение смещенное в некоторую сторону считаются идентичными, то скорее всего нет. Т.к. смещение уже изменит центр изображения
noonv
Велосипеды — это конечно здорово, но свой алгоритм можно проверить либо в матлабе, либо используя тот же OpenCV, чтобы понять качество его работы.
leshabirukov
Но положения 50 точек на плоскости однозначно определяются 100 числами. Это сразу десятикратная избыточность. Может быть, попробовать формировать дескриптор из координат точек относительно центра тяжести? Тогда вы всё ещё довольно устойчивы к пропаданию части точек (если центр тяжести не уехал).
bezdolgoff
Только как найти этот «центр тяжести»? Вернее как найти такой «центр» который будет однозначно определяться для схожих, но не идентичных изображений? Ведь правильно замечено, что оно может уехать.
Deosis
Избыточность нужна, потому что мы ищем похожие изображения. Небольшие искажения или повороты внесут изменения во все значения. Но за счет избыточности мы можем игнорировать небольшие различия.