Pull to refresh

Comments 61

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

Теперь критика:
— Не увидел конкретной модели изображения. Вы придумываете серебряную пулю на любое изображение, и это тупик, ибо любые данные можно считать изображением.
— «Не являясь программистом, я не имею возможности..». Увы, в этом деле надо быть или программистом или математиком. Даже так — математиком знающим основные эффективные структуры данных и алгоритмы. А это снова быть программистом.
— Идея с хэшем боюсь тупиковая. Конечно, если вы из картинки выведите структуру вроде «кошка, в углу,… поворот» то получите весь арсенал аля SQL запросов. Но так и самая трудность в том чтобы вывести структуру из картинки.
Чтобы это понять почитайте вычислительную геометрию, например задачу поиска ближайшей точки. Там есть свои эффективные структуры, но не хэш в лоб.

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

Эвристический маразм без сетей, как в посте, конечно намного лучше...

Конечно лучше. Лучше хотя бы тем что пытаются работать с предметной областью понятиями самой предметной области.

Имхо, аргумент в стиле "всё лучше, чем по подъездам клей нюхать"...DDD — это прогресс, а решение задач методом нагромождения эвристик — это поиск вчерашнего дня.

Аргумент в том же стиле что и ваш коммент. Я и не защищаю эвристики, хотя без них никуда. Причем тут DDD? Тема статьи — алгоритмы CV, я думал.
Причем тут DDD?

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

разрабатываем алгоритм, который сам найдет

Ну понятно )) Ваш метод на столько же гениален на сколько бесполезен.
Еще раз говорю — я не за эвристики. Я бы предпочел точные методы вроде метода сортировки со сложностью NLogN. Кстати попробуйте найти таковой вашей методой перебора. Думаю даже в ваших переборах вы используете эвристики для сокращения перебора… Так что вообще не понимаю о чем спор.
Ну понятно )) Ваш метод на столько же гениален на сколько бесполезен.

Современный ML смотрит на вас с изумлением...


Еще раз говорю — я не за эвристики.

А что тогда по вашему из себя представляет метод, описаный в посте?

В посте смесь эвристики и логики. Покажите мне хоть одну статью по ML где нет эвристики.
Разделение точек на плоскости прямой на два класса — и то становится эвристикой сразу как только вы подменяете 2д пространство на пространство параметров предметной области. А метод между тем пришел из чистой прикладной геометрии. Так что не надо гнобить эвристику, особенно в контексте ML.
Так что не надо гнобить эвристику

Я и не гноблю, лишь утверждаю, что ваше утверждение:


— не пустились в эвристический маразм с нейронными сетями,

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


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

обучающиеся алгоритмы придумывают эвристики и ищут закономерности в данных более успешн

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

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


В каком месте расхождение? Именно это и происходит в процессе обучения тех-же глубоких сетей.

а что не так с машинным обучением? всё равно надо параметры подкручивать, а так вместо подбора ручками алгоритм сам найдёт оптимальные параметры
Вы любую подкрутку параметров называете ML-ем? Методов оптимизации море: переборы, град спуски,… нейросети будь они неладны. Поиск минимума параболы — это тоже оптимизация, но вы же не будете обучать нейросеть для этого. Вы просто решите квадратное уравнение. В другом случае будет достаточно перебора… Я к тому что все с ума посходили на ML и перестали видеть простые эффективные решения.
>Методов оптимизации море: переборы, град спуски,… нейросети будь они неладны.
Мммм, а как можно оптимизировать нейросетями?
Обучение алгоритма = оптимизация его параметров или структуры.
ну многие программисты не мега математики, мне например в разы проще написать сложный алгоритм чем функцию которая посчитает тоже самое, ну и ML оно более гибкое как мне кажется, надо научиться находить лица даёшь кучу фоток лиц и оно само научиться, надо находить машины почистил всё и дал кучу фоток машин, ничего не переписывая оно само заработает.
Опять велосипеды… А вы смотрели вот эту статью: https://arxiv.org/abs/1306.3855? Их подход опережает все существующие алгоритмы на порядок и позволяет, например, при выделении региона изображения найти в базе крупные фотографии этого региона или, например, найти все фотографии, где объект, являющийся главным на текущей фотографии, на другой представляет лишь малую часть. Таким образом можно «отдалить» вид от часов на кремле до вида Москвы с птичьего полета и «приблизить» обратно. Естественно, с поиском просто похожих фотографий справляется великолепно. В статье так же предложены оптимизации для мгновенного поиска в базе по 10^7 изображениям.
Класс!
Не в курсе, а нету ли программной реализации данного алгоритма?
Есть у авторов (показывали на лекции) и, если не изменяет память, они её продают.
Бесплатно вроде распространяют, по крайней мере, на странице авторов http://cmp.felk.cvut.cz/wbs есть ссылки на исходники, наборы данных, документацию.
А вот статья https://arxiv.org/abs/1504.06603 с их более мощным (по заявлениям авторов) алгоритмом.

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

Не являясь программистом, я не имею возможности самостоятельно проверить алгоритм в работе. Буду рад, если кто-то из членов Хабра-сообщества, сможет реализовать программно этот алгоритм и протестировать его в работе.


У вас в компании нет программистов? Почему вы рассказываете свой алгоритм сначала нам, а не коллегам? Вдруг он не решает вашу бизнесс-задачу?
Программисты есть, но пока эта задача не выносилась… Всему свое время.
А разместил здесь, что бы получить отклик профессионалов и любителей, после чего доработать свою теорию или отказаться от нее.
После того как вы отобрали «50 самых значимых точек» для данного изображения, вы уже потеряли данные о таких же изображениях, но с чуть другой яркостью или цветом. Дальше при формировании дескриптора вы увеличили ошибку из-за не тех точек. Хеш это все усугубил невероятным размером, а округления на поиске еще раз увеличили ошибку. Поиск и сравнение в таком виде даже среди небольшого числа данных потребует порядочно мощьностей, а результат будет никакой.
Как раз выбор самых значимых точек, предполагает, что эти точки можно, с большой долей вероятности, найти на изображениях с некоторыми изменениями.
А настраеиваемый уровень сходства (расстояние Хемминга), как раз позволяет компенсировать случайное несовпадение некоторых точек.
Если отобрать не 50 точек, а скажем 10, то он будут еще более значимыми и размер хэша будет меньше. Все зависит от конкретной задачи.
Попробуйте на произвольной картинке поискать 50 или 10 «наиболее значимых точек» и тоже самое на такой же картинке, но с другими параметрами цвета, яркости или просто после минимальной обработки. они могут и будут отличатся.
компенсации тут никакой нет, тк идет явный поиск 1 к 1, в противном случае сложность увеличивается на число точек, тк они все могут быть невалидны и придется их всех проверять. те сложность увеличивается в вашем случае в минимум 50*50 раз…
Предположим, что из 50 точек, только 45 совпали на 2х изображения, как ключевые. Остальные 5 (вернее по 5 на каждом изображении) определены ошибочно, т.е. по разному на каждом изображении.
Тогда получем 990 отрезков с одинаковой длинной и 235 с разной.
Если выставим допустимое расстояние больше 235 то изображения будут считаться одинаковыми, если меньше чем 235 то разными. Зачем каждую точку отдельно проверять?

Но ведь после сортировки общие 990 длин отрезков вовсе не обязаны оказаться на тех же положениях в обоих дескрипторах, не так ли? Ведь между ними окажутся некоторые из оставшихся 235 отрезков.

Вот это ценное замечание. Спасибо!
Есть над чем подумать.
UFO landed and left these words here
Ваш велосипед справляется только с аддитивным шумом. Собсна классика обработки сигнала (копать в сторону корреляции). А теперь добавьте нелинейные искажения вроде поворота, скалинга, изменения освещения сцены — и приплыли.
UFO landed and left these words here
Ну если вы скалинг перебором подстраиваете — конечно но проблем. Вообще то любые искажения не помеха если перебором все искать. В том то и беда что перфоманса CPU всегда мало.
UFO landed and left these words here
В статьях подобная задача обсуждается последние лет 20. Рекомендую поискать по ключевым словам «near duplicate detection» and (image or photo). Замечу, что во многих статьях начальные этапы обработки часто совпадают с предлагаемыми в посте. Считаю, что стоит поздравить автора: он свой «велосипед» изобретает в правильном направлении.
Однако, подробно обсуждать предлагаемое решение я не вижу смысла, так как задача не поставлена более-менее чётко. О какого рода изображениях идет речь? Согласен с первым комментарием, что не существует универсальных подходов. Упоминаемые в комментария выше статьи про matching прекрасно работают для обычных бытовых фото, но попробуйте их применить для мэтчинга регулярных текстур или, например, изображений слоёв травления в микроэлектронике. По моему опыту они не работают.
Что значит «похожие»? Согласитесь (или посмотрите в существующих статьях), что формулировка может быть достаточно разной.
Сколько изображений всего уже сейчас или ожидается когда-либо?
Как Вы собираетесь считать точность и какого уровня рассчитываете достичь?
Сколько времени Вы можете себе позволить заниматься разработкой, реализацией и тестированием алгоритма?
Без ответа на хотя бы часть из этих вопросов маловероятно ожидать конструктивного обсуждения предлагаемого подхода. Хотя ссылок «а вот посмотрите еще сюда» «а вот посмотрите еще сюда», накидают, что, конечно, тоже полезно.

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

Обычно для это пользуется поиск по гистограммам если не лезть глубоко в распознование обьектов.
Думаю самый простой метод поиска идентичных изображений — поиск по гамме. Минусы — обманывается зеркалированием, но можно добавить ф-цию «искать в отраженных».
Вам стоит обратить внимание на перцептивный хэш, он решает схожую задачу:
https://habrahabr.ru/post/120562/

Это самый быстрый способ поиска дубликатов изображений и на его основе можно сделать много интересных приложений, например детектирование движения в кадре.
UFO landed and left these words here
У нас этот алгоритм прекрасно работал. Видимо у кого то есть свои специфические задачи для которых этот алгоритм не подходит.
Автору однозначно стоит попробовать его на своей выборке, благо реализация уже готова.
Друзья, а если расчёт основных точек производить опираясь на «эталон» Подскажите, пожалуйста центр изображения может быть таким «эталоном»? Может быть «эталоном» стоит принять точку с определёнными параметрами освещённости. А перед поиском «эталона» освещённость изображения изменять до 50%

П.С. Прошу, смеяться без злобы. Я юрист, для меня 1+1 будет три. Три знака)))) С уважением, Елисей.
Подскажите, пожалуйста центр изображения может быть таким «эталоном»?

Если изображение и это же изображение смещенное в некоторую сторону считаются идентичными, то скорее всего нет. Т.к. смещение уже изменит центр изображения

Велосипеды — это конечно здорово, но свой алгоритм можно проверить либо в матлабе, либо используя тот же OpenCV, чтобы понять качество его работы.

Как известно через Х точек можно проложить Х*(Х-1)/2 отрезков, т.е. из 50 точек можно составить 50*49/2=1225 отрезков. Т.е. наша строка будет состоять из 1225 целых чисел.

Но положения 50 точек на плоскости однозначно определяются 100 числами. Это сразу десятикратная избыточность. Может быть, попробовать формировать дескриптор из координат точек относительно центра тяжести? Тогда вы всё ещё довольно устойчивы к пропаданию части точек (если центр тяжести не уехал).
Только как найти этот «центр тяжести»? Вернее как найти такой «центр» который будет однозначно определяться для схожих, но не идентичных изображений? Ведь правильно замечено, что оно может уехать.
Избыточность нужна, потому что мы ищем похожие изображения. Небольшие искажения или повороты внесут изменения во все значения. Но за счет избыточности мы можем игнорировать небольшие различия.
Only those users with full accounts are able to leave comments. Log in, please.