Pull to refresh

Comments 23

Небольшой комментарий: информация о том, что в большинстве изображений есть очень немного основных цветов — результат моей работы над недавно законченной системой поиска по изображениям. Картинка, иллюстрирующая выделение цветов — результат работы одного из алгоритмов этой системы.
Я думаю поиск гугла на этом на заканчивается, иначе любой бы мог воспроизвести этот поиск на равне.
1. sift в оригинале плюёт на цвет — хоть красный на желтый меняй, главное так, чтобы отношения переходов в яркостях оставалось тоже самое. Он считает разности.
2. Sift инвариантен только односительно вращения + перемещения, и если использовать слои — то и от масштаба. Все перспективные преобразования или транформации его убивают.

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

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

>иначе любой бы мог воспроизвести этот поиск на равне

Вообще-то примерно так оно и есть :) По крайней мере результаты упомянутого чуть ниже Piximilar, ИМХО, ничуть не хуже — если не лучше. Да и наша система (прямо сейчас на нее посмотреть еще нельзя, но очень скоро она появится на одном крупном фотохранилище) вроде не особо хуже.
Другой вопрос, что Гугл будет свой поиск развивать. Думаю, через пару лет он существенно улучшится.
>Я почему-то думаю, что тут суть построить правильное дере вывода по всем этим метрикам. Правильно сегментировать каждое из измерений.

Это да, весьма нетривиальная задача. Объединить разные метрики, особенно более чем две, во что-то внятное — большой кусок работы, с плохо прогнозируемыми результатами.
Самое важное, на мой взгляд — это развитие инфраструктуры к тому, что распознается.
Гугли наладили распознавание лиц, но объектный интерфейс к распознаванию пока не создан.
Собственно, ему надо немногое — теги, контуры, уникальные гиперссылки к каждому объекту. Возможно, раасширяемая система метаданных.
Какие бы не были алгоритмы, всем им требуентся система обучающих тестовых выборок и стандартизация результатов работы. Пока программист не знает что является результатом работы алгоритма — это просто творческий процесс а не софт.
Забавно — такая очевидная вещь пока не сделана. Тупое копирование идеи распознавания мордасов без обобщения.
Если интересно — попробую развернуть концепцию.

С удовольствием почитаю развернутый комментарий — потому как довольно многие вещи сделать можно относительно легко, но лично мне совершенно неясно, насколько это актуально. Какого рода функциональность могла бы быть нужна подобной системе?
Попробую начать (ибо пока мысли, но есть желание облечь их в слова).
1. Наиболее «продвинутые» с информационной точки зрения на сегодня ГИС-приложения. Тут есть и продукты для векторизации (Easytrace, Spotlight и тп) и системы, которые могут эти результаты интегрировать в объектную базу данных (ArcGIS, Mapinfo и тп).
2. Суть интеграции — создание атрибутивной базы. Причем, поскольку это программное обеспечение «реляционной эпохи», то набор атрибутов ограничен и согласован — для того, чтобы получилась единая таблица, один столбец которой отвечает за геометрию (shape) а остальные за информацию, прикрепленную к этой геометрии. Это подход корпоративных систем. недостаток его в том, что требуется изначально спроектированный и согласованный набор признаков, что затрудняет развитие информационной части.
3. Наиболее здравый подход — хранить геометрию и метаданные (XML or JSON), в которых хранится url самого изображения, URL марки на изображении (анимационная часть приближения к фрагменту), набор тегов, авторские данные и тп. Важно, чтобы пользователи могли создавать свои теги. Например, профессионалы ботаники или зоологи могут захотеть добавлять свои системы классификации, геологи-свои.
4. Сервер это дело хранит-возвращает. Вторая часть клиента умеет все как надо искать и спрашивать. API поддерживает возможность создавать умных клиентов, например, классификатор пород из которого выбираются уже характерные фрагменты.
5. Позиция распознавателей в этом случае — участок системы, который умеет учиться у существующей базы данных и возвращать не только геометрию, но и метаданные, добавляя при этом информацию о себе (софт-версия-алгоритм-параметры-оценка достоверности и тп). Похоже на EXIF в фотографиях должно получаться.
6. Как альтернатива распознавателю должен быть простой векторный редактор, позволяющий поверх изображения ставить точки, линии, полигоны (как ближний аналог — Google Earth-Google Maps). Он же является инструментом для генерации обучающих и тестовых выборок. В этих условиях алгоритмы распознавания можно внедрять постепенно, совершенствуя. Система будет просто плавно перетекать из ручного в автоматизированный режим.
Хм… В целом ясно, и это было бы круто. Но не очень понятно, кому может понадобиться таким пользоваться, для чего? Понимаю что вопрос в некотором роде глупый, скорее всего, когда подобная система получит широкое распространение, недоумение будет вызывать то, что кому-то было неочвидна ценность такой штуки :) Но все же. Я пока не вижу, что могло бы побудить лично меня что-то отмечать на каких-то картинках в инете. Хотя наверняка такие мотивы есть в избытке — но хотелось бы понять их сейчас, а не постфактум :)
Спасибо за статью. А не рассматривали какие методы использует tineye.com? Навскидку, изменение цветов и сжатие на 20% по горизонтали не помогло — изображение опознали. По куску картинки оригинал тоже ищется.
Насколько я знаю, tineye использует методы на базе sift — или аналогичные им. Прямо сейчас проверил на примере вот этого изображения: upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Statue_of_Liberty3.jpg/300px-Statue_of_Liberty3.jpg — при поиске неискаженного выдает 10 результатов, если же его несколько сплющить, с высоты в 400 пикселей до высоты в 300 пикселей, то результат останется только один (и, с точки зрения распознавалки, эта поплющенная статуя совпадает с оригинальной если картинку несколько повернуть — это о многом говорит, при повороте пропорции контрастного контура куда больше напоминают исходные, именно это основной аргумент в пользу того, что там используется распознавание на основании подобия конфигурации опорных точек — вопрос только, как именно они выбираются).
Судя по устойчивости алгоритма TinEye к изменениям, особенно что касается фрагментирования, геометрических искажений и изменения цвета, можно предположить, что используются структурные признаки (AKA «признаки формы» / shape features). Перед индексирование изображения скорее всего преобразуются в цветовое пространство YCbCr (используется в JPEG) либо ближайший аналог YIQ (используется в NTSC).

Компания Idée Inc., разработчик поисковика TinEye, предлагает продукт Piximilar, использующий различные виды признаков для поиска подобных изображений. Вот что о них известно:
Multicolour Search: Piximilar
Our multicolour search algorithms utilize a colour space that is based on the human perception of colour and return much more natural results then simple colour histogram approaches. They also support the ability to specify a varied distribution of colours in the query.

Visual Similarity Search: Piximilar
Piximilar uses sophisticated algorithms to analyze hundreds of image attributes such as colour, shape, texture, luminosity, complexity, objects and regions.
These attributes form a unique visual signature and are arranged into a visual index. The compact image signature is calculated quickly, stored efficiently and used to facilitate searches for similar images using an optimized and accurate comparison engine.

TinEye же, скорее всего, использует какой-то один или отсилы два вида признаков (первый, например, для первичного отбора примерно похожих на запрошенное изображений, второй — для ранжирования их в выдаче).
>Our multicolour search algorithms utilize a colour space that is based on the human perception of colour

Ага, это пространство Lab. Очень рекомендую его использовать, кстати, там конечно толковая формула для цветового расстояния такая мудреная, что на ее отладку уйдет неделя, если не две (баги просто неизбежны, слишком много интуитивно-неочевидных вычислений), но результат того стоит — я проверял :)

Вообще подход у Piximilar безусловно более интересный, чем у TinEye. И результаты у них хорошие.
Небольшой оффтопик: как воспользоваться поиском Google по файлу изображения с Android?
UFO landed and left these words here
Ок, я неудачно выразился. Под этой базой я имел в виду те картинки, метаинформация к которым позволяет сделать однозначные выводы о том, что там изображено. Это справедливо для небольшого процента изображений, и если поиск дает совпадение с одним из них — то логика выдачи результатов принципиальным образом отличается от логики выдачи результатов в другом случае.
Почти все выводы неоднозначны.

1) «Границы: Поэтому этот класс признаков может служить только глубоко вспомогательным.» Ну я бы не стал гвоорить о «глубоко вспомогательности». Во первых, есть конутрный анализ, который справляется с некторыми задачами очень хорошо. Во-вторых есть ряд методов, основанных на диаграмме градиентов, которые тоже используются неплохо. А некоторые системы (например распознавание человека) работают только на анализе гистограммы градиентов.

2) «Текстуры: Соответственно эти признаки тоже могут быть только вторичными, хотя их значение несколько больше.» Угу, «несколько больше». Посмотрите, например метод «Integrated Region Matching». Там очень хорошие результаты, основанные в основном на анализе текстур. Кроме того, текстурный метод использует большинство систем поиска изображений по контенту.
3) «SIFT не найдет котенка». Да, котенка не найдет, а вот здание, например, найдет с разных ракурсов.
4) «Цвет является, пожалуй, наиболее значимой для анализа характеристикой». Ну это вы завернули :) В ч/б изображении содержится 90% информации об изображении. Вы без труда узнаете человека на ч/б фотографии. А попробуйте его узнать по спектрограмме ;) Да гугл, может и ищет по цвету, но только после того как не смог найти по другим признакам. Так что на «самую значимую» характеристику цвет не катит. Я понимаю, тех, кто только начинает разработку подобных систем, привлекает спектрограмма своей простотой. Но в дальнейшеам оказывается, что это тупиковый путь.

n) Некторые методы вообще не рассмотрены. Например, вейвлетные (фильтры Хаара и т.п.). А ведь для распознавания лиц, от того же гугла, работает только с помощью этих методов.

В принципе вы молодец, что поднимаете эту тему, но нужно быть более аккуратными с выводами. Иначе у читающих могут возникнуть неправильные представления о теме.
>А некоторые системы (например распознавание человека) работают только на анализе гистограммы градиентов

Понятно, что в границах потенциально лежит много информации. Но достать ее оттуда — отдельная, весьма сложная задача, и сказать что система «основана на выделении границ», если у нее начальной ступенью обработки является выделение границ, а потом над этим результатом работает еще десяток нетривиальных алгоритмов — ну… Не то чтобы нельзя, но — странно :)
Хотя если набор границ с минимальной обработкой, поданный на тривиальный классификатор типа нейронных сетей, дает возможность эффективно детектировать человека — то я, пожалуй, неправ. Только я не слышал о таких системах — те, о которых слышал, работали весьма «через раз».

>Посмотрите, например метод «Integrated Region Matching». Там очень хорошие результаты, основанные в основном на анализе текстур

Все же не совсем так. Эта техника очень зависит от того, насколько хорошо нам удастся сопоставить характеристики одного региона с другим. И хотя при сопоставлении двух регионов текстура, конечно, является куда более важной характеристикой, чем при сопоставлении разных изображений «в лоб», но если ее не дополнить другими — в частности, тем же цветом — то результаты в рамках задачи «отсортировать базу изображений по подобию на заданное» будут явно не лучшими. Хотя в целом согласен, я текстуры слишком поверхностно оценил.

>Да, котенка не найдет, а вот здание, например, найдет с разных ракурсов.

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

>В ч/б изображении содержится 90% информации об изображении

Я, разумеется, имел в виду значимость цвета для поиска по цветным изображениям.
А с ч/б все куда печальнее на сегодня: при попытке найти визуально похожие на заданную ч/б картинку вывод того же гугла визуально не очень-то отличается от случайной выборки всех ч/б изображений подряд.

>Да гугл, может и ищет по цвету, но только после того как не смог найти по другим признакам

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

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

Ну как… Простота — да, у меня на все, связанное с непосредственно поиском по цветам, ушло два месяца, остальные 4, пока разрабатывалась веб-обвязка к ядру, я сидел и занимался разными другими интересными вещами, иногда подправляя мелочи :) Но среди этих «интересных вещей» была масса усилий, которые я потратил на анализ формы, на вопросы кодирования топологических признаков и поиска по ним (просто такая задача не входила в данный проект — но для себя я сделал немало). И я не могу сказать, что сегодня есть какая-то удовлетворительная техника для работы с формой — все работает очень «через раз», и, что самое неприятное, эффективно объединить результаты разных методов — весьма нетривиальная задача, действительно хорошего решения которой я ни сам не нашел, ни в других работах не увидел. Именно поэтому я так подчеркнул цвет — это единственное, что сегодня анализируется действительно хорошо. Остальное — только в отдельных специфических задчах.

>Некторые методы вообще не рассмотрены. Например, вейвлетные (фильтры Хаара и т.п.). А ведь для распознавания лиц, от того же гугла, работает только с помощью этих методов.

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