В этой статье мы описываем основные идеи алгоритма и приводим его детали для интересующихся, рассказываем об извлечённых уроках и о том, как это всё вообще было.
Исходный код нашего решения доступен на github (C++ с использованием OpenCV).
Описание конкурсной задачи
В 2011 году Яндекс предложил участникам конкурса интересную задачу по компьютерному зрению, поэтому нашей компании, специализирующейся в этой области, было бы грех не принять участие. Задача заключалась в поиске лишних изображений в сериях панорамных снимков с Яндекс.Карт. В каждой серии было дано по 5 изображений, часть из которых (3, 4 или все 5) были сделаны в одном месте и примерно в одно время, а остальные были лишними. Например, изображения 1, 3 и 5 на серии выше составляют панораму, а изображения 2 и
От начала до финала
Узнав про конкурс из нашей корпоративной рассылки, каждый из нас скачал себе данные, несколько дней упорно разглядывал картинки (было чем
И вот настал финальный
Далее мы расскажем о том, какой алгоритм у нас получился в итоге.
Основные идеи алгоритма
Итак, задача состоит в разбиении серии изображений на группы: искомая панорама и лишние изображения. Чтобы найти такое разбиение, нужно для любой пары изображений уметь оценивать правдоподобность того, что они принадлежат одной панораме. Для этого мы ввели две меры схожести для пары изображений, основанные на дополняющих друг друга подходах: сравнение цветовых гистограмм изображений и поиск общих частей на изображениях. Мы скомбинировали эти две меры в одну и использовали полученную меру для разбиения изображений на группы (кластеризации). Меру каждого из подходов можно было бы использовать и по отдельности, но комбинирование позволяет объединить их сильные стороны.
Гистограммы позволяют сравнить частоты появления цветов на одном изображении с частотами на другом. Поскольку, согласно описанию задачи, снимки в одной панораме изображают одну сцену в одно время с близких положений камеры, то их цветовые характеристики, как правило, схожи между собой, а у лишних изображений они обычно другие. Поэтому расстояние между гистограммами даёт подходящую оценку близости изображений. Например, лишние изображения из серии, приведённой в начале статьи, гораздо темнее панорамных снимков, поэтому в гистограммах лишних снимков будут преобладать тёмные цвета, и эти гистограммы будут далеки от гистограмм панорамных изображений.
Второй подход, поиск общих частей на изображениях, позволяет определить, что два снимка относятся к одной панораме в случае, когда между ними есть достаточное пересечение, например на них встречается один и тот же объект. Это достигается путём использования популярного в компьютерном зрении подхода: на двух сравниваемых изображениях детектируются характерные ключевые точки, после чего осуществляется поиск соответствий между ними, например путем сравнения окрестностей этих точек. Если удалось найти много похожих окрестностей, то, скорее всего, они относятся к одним и тем же объектам и это два изображения одной и той же сцены. В этом подходе мерой близости является количество похожих окрестностей. Например, работа этого подхода проиллюстрирована на Рис. 1 и 2.
Рис. 1. Пример серии, в которой поиск общих частей даёт правильную классификацию, поскольку на снимках есть части одного и того же здания. При этом цветовые гистограммы изображений 1 и 4 сильно отличаются от остальных, поэтому гистограммный подход считает эти два снимка лишними, что на самом деле неверно.
Рис. 2. Соответствующие друг другу ключевые точки, найденные алгоритмом.
Эти два подхода взаимно дополняют друг друга. Гистограммный подход может работать даже в тех случаях, когда между снимками одной панорамы нет никаких пересечений и общих частей (см. пример на Рис. 3). Однако в некоторых случаях пересечение между изображениями есть, но остальные части очень сильно отличаются между собой по цвету (например, солнце зашло за тучу). В этом случае гистограммы будут далеки друг от друга, а поиск общих частей может определить, что эти изображения относятся всё же к одной панораме даже по небольшому перекрытию (см. пример на Рис. 1 и 2).
Рис. 3. Пример серии, в которой между снимками одной панорамы (3, 4 и 5) нет областей с общими ключевыми точками, но благодаря цветовым гистограммам получается правильная классификация (изображения 1 и
Как показали эксперименты, большую часть правильных ответов способен дать гистограммный подход в одиночку, а добавление второго подхода лишь в немногих случаях улучшает классификацию.
Для интересующихся компьютерным зрением и деталями этих двух подходов написаны два следующих раздела, а всем остальным предлагается перейти к Объединению двух подходов и Результатам.
Детали гистограммного подхода
При реализации было использовано цветовое пространство YCrCb, поскольку в нём явно выделена компонента яркости. Это позволяет взять меньшее количество бинов (интервалов группировки) по этой компоненте и тем самым повысить устойчивость алгоритма к изменению освещённости и теням.
Также к этим трём компонентам (Y, Cr, Cb) для построения гистограмм мы добавили ещё
Таким образом, строилась четырёхмерная гистограмма с 12 бинами для яркости, 256 бинами для каждой из двух цветовых компонент и 4 бинами для ординаты пикселя.
Для вычисления расстояния между гистограммами использовалось их пересечение (Histogram Intersection Distance). Для изображений одного разрешения эта дистанция фактически отражает количество похожих пикселей между двумя изображениями.
Детали подхода на основе локальных особенностей
Одним из самых успешных методов в компьютерном зрении является использование уникальных локальных особенностей на изображении, например углов или центров блобов (небольших однородных областей). Этот подход применим, если сцена достаточно текстурная, то есть содержит большое количество таких локальных особенностей. На снимках с Яндекс.Карт изображены текстурные уличные сцены, поэтому этот подход разумно применять. Однако в конкурсном наборе данных существует несколько сложностей: изображения имеют низкое разрешение (300×300 пикселей) и нередко присутствуют большие нетекстурные области (асфальт, небо, …). Столь малое разрешение влечет за собой низкую повторяемость (repeatability) детектора локальных особенностей: ключевая точка, найденная на одном из изображений, часто будет не продетектирована на другом снимке той же панорамы, и мы не сможем определить, что между изображениями есть соответствия. Для решения этих проблем мы выставили такие параметры детектора локальных особенностей, чтобы он находил большое число ключевых точек на изображении (~10k). Однако это приводит к тому, что особенности на сравниваемых изображениях становятся менее уникальными, и при поиске соответствующих друг другу особенностей часто находятся ложные соответствия. Поэтому для выбора правильных соответствий мы применили несколько дополнительных фильтраций. Перейдём к деталям.
- В качестве детектора локальных особенностей мы использовали FAST, который позволяет быстро находить углы на изображении. Для устойчивости алгоритма к изменению расстояния до снимаемых объектов при различных положениях камеры необходимо детектировать локальные особенности разных масштабов. Для этого мы масштабируем изображения, используя 4 уровня Гауссовой пирамиды изображений, запускаем FAST на каждом уровне и объединяем множества найденных ключевых точек.
- Для ключевых точек каждого изображения вычисляем дескрипторы (описатели) их окрестностей. Мы использовали дескриптор SURF, который быстрее, чем более известный SIFT, но имеет сравнимое качество.
- Далее мы находим соответствующие друг другу ключевые точки на двух изображениях, используя вычисленные дескрипторы, представляющие собой 64-мерные вектора вещественных чисел. Для этого для каждого дескриптора одного изображения находится ближайший дескриптор на другом изображении по L1 расстоянию между векторами дескрипторов. Это расстояние более устойчиво к шумам, чем стандартное евклидово расстояние. Поскольку мы имеем огромное количество локальных особенностей, то поиск ближайшего дескриптора полным перебором потребовал бы слишком много времени. Поэтому мы использовали приближённый поиск ближайшего дескриптора с помощью библиотеки FLANN, интегрированной в OpenCV.
- Найденные соответствия между локальными особенностями фильтруются по критерию надежности cross-check, который из всех соответствий оставляет только взаимно однозначные.
- Фильтруем оставшиеся соответствия по у-координате: если у-координаты точек, связанных соответствием, отличаются больше чем на 100 пикселей (значение параметра подобрано экспериментально), то такое соответствие считаем ложным. Этот фильтр обоснован тем, что в конкурсных изображениях встречались только горизонтальные панорамы.
- Вычисляем матрицу гомографии по схеме RANSAC по множеству взаимно однозначных соответствий между локальными особенностями. Согласно теории, между точками изображений существует преобразование гомографии (при произвольном изменении положения камеры), если их прообразы в 3D мире лежат на одной плоскости. Для неплоских объектов мы также можем искать преобразование гомографии, если отклонение точек объекта от плоской формы много меньше, чем расстояние от камеры до объекта. Поиск гомографии для конкурсных изображений панорам обоснован следующими фактами: 1) для объектов городских сцен характерно наличие плоскостей; 2) объекты часто достаточно удалены, чтобы считать их плоскими; 3) вычисление гомографии требует меньшего количества итераций RANSAC, чем нужно для нахождения фундаментальной матрицы.
В цикле поиска гомографии по схеме RANSAC для оценки качества очередной гипотезы о гомографии применялось несколько эвристик: фильтр по минимальному сингулярному числу матрицы гомографии, фильтр инлаеров (соответствий, удовлетворяющих текущей гипотезе о матрице гомографии) по согласованности изменений ориентаций продетектированных углов, замена близко расположенных инлаеров одним. В результате выбиралась гомография, дающая наибольшее количество инлаеров.
- В качестве меры близости между изображениями берётся количество инлаеров для найденной матрицы гомографии.
На многих снимках этому алгоритму хватало даже небольшого пересечения между изображениями, чтобы найти достаточное количество соответствующих ключевых точек. Так, интересный и неожиданный для нас пример работы описанного алгоритма приведён на Рис. 4.
Рис. 4. Забавная ситуация, когда снимки можно объединить в одну панораму по присутствию одних и тех же облаков на небе. На этой паре снимков гистограммы чувствуют себя неуверенно из-за большой тени, но ситуацию спасают локальные особенности и облачная погода.
Объединение двух подходов
Описанные подходы позволяют посчитать два вида дистанций между изображениями. Чтобы учесть оба подхода, мы комбинируем эти дистанции следующим образом:
dcomb = min(c * dhist, dfeat),
где
dcomb — комбинированное расстояние,
dhist и dfeat — нормированные в отрезок [0, 1] расстояния, вычисленные с помощью подходов на гистограммах и локальных особенностях соответственно;
c — коэффициент меньший единицы, позволяющий придать больший приоритет результатам работы алгоритма, использующего гистограммы.
Для объединения двух подходов была выбрана именно функция минимума, потому что если хотя бы одна из двух дистанций мала, то изображения действительно близки.
Вычислив попарные комбинированные расстояния между изображениями одной серии, мы проводим иерархическую кластеризацию (Agglomerative hierarchical clustering using single-linkage) этих изображений. Кластер с максимальным количеством элементов признаётся искомой панорамой, а остальные изображения лишними. Такая иерархическая кластеризация очень естественно подходит для этой задачи, поскольку внутри одной панорамы могут быть далёкие непересекающиеся изображения, которые связаны цепочкой других близких друг к другу изображений панорамы, и этот метод позволяет объединить такие изображения в одну панораму.
Результаты
Итак, после упорной работы над нашим алгоритмом, на финальном наборе данных он показал очень хороший результат: было правильно классифицировано 99.44% изображений, что позволило занять первое место в конкурсе. А также получить приз в размере 100 000 рублей на празднование победы 🙂
Уроки конкурса
В качестве заключения мы хотим поделиться несколькими уроками, которые мы извлекли или закрепили, участвуя в конкурсе. Нам они точно пригодились.
- Без друзей меня чуть-чуть, а с друзьями много. Участвовать единой командой было нашим лучшим решением за всё время конкурса. Ни один из нас не смог бы победить в конкурсе в одиночку. Мы вместе генерировали идеи, смогли параллельно проверить очень много разных подходов, использовали знания и опыт каждого, поддерживали и вдохновляли друг друга и не давали никому заснуть в последнюю ночь перед дедлайном, продолжая генерировать бредовые идеи в 5 утра. Да и победу приятнее отмечать всем вместе.
- Горе от ума (или overfitting). В начале конкурса Яндекс предоставил размеченные данные для предварительного тестирования алгоритмов. Однако во многих сериях практически невозможно было найти лишние изображения даже человеку (см. пример на Рис. 5).
Рис. 5. Пример весьма непростой серии. Как вы думаете, какие изображения здесь лишние?Ответ1 и 3 — лишние изображения, а 2, 4 и 5 образуют одну панораму. Если приглядеться, то лишние снимки были сделаны в другое время года.Проблема с неразрешимыми сериями была поднята участниками на форуме конкурса, и организаторы обещали не допустить такого в финальном наборе данных. Это означало, что финальный набор данных будет иметь другие свойства, чем предварительный набор. Тем самым не выполнялось фундаментальное предположение алгоритмов машинного обучения, что тренировочная и тестовая выборка должны быть порождены одним вероятностным распределением. Поэтому мы решили использовать максимально простые алгоритмы с небольшим количеством настраиваемых параметров, так как иначе крайне высок риск переобучения. Как показала практика, это было очень ценное наблюдение, поскольку несколько других участников, использующих продвинутые алгоритмы машинного обучения, действительно переобучились и показали не такой хороший результат на финальных данных, как на предварительных.
- Зри в корень. Для проверки идей, понимания поведения и проблем алгоритмов, да и просто отладки необходима правильная визуализация (как итоговых результатов, так и промежуточных шагов). Это дало нам прочувствовать специфику задачи и данных, более чётко и быстро двигаться к правильным решениям.
- Мал, да удал. Решение задачи стоит начинать с простых подходов: их очень легко и быстро реализовать, зато сразу получится результат для сравнения (baseline). К тому же даже примитивный подход может показать удивительно хорошие результаты, а если его немного доточить под специфику задачи, то он может стать непобедимым. Так получилось у нас с гистограммами: очень простая идея, принёсшая нам основной результат (локальные особенности увеличили точность классификации меньше, чем на один процент). При этом обсчёт всех финальных данных гистограммами занял всего пару минут, а результатов подхода на локальных особенностях мы ждали несколько часов.
- Хук справа, хук слева. Атаковать задачу лучше с разных сторон: полезно разрабатывать запасные стратегии решения задачи и иметь инструменты, способные справиться со всеми обнаруженными свойствами задачи. Например, мы пробовали подходы, учитывающие цвет, градиенты и их ориентации, пространственное положение, отсутствие и наличие перекрытий между изображениями. В результате для улучшения точности классификации мы скомбинировали найденные решения.
- Don’t worry, be happy. Мы не забывали получать удовольствие от процесса, ценили возможность научиться чему-то новому и пообщаться с друг другом. Это был очень приятный и полезный опыт. Победить в
конкурсе — это , конечно, здорово, но мы чаще вспоминаем не момент объявления результатов, а много других весёлых и безумных моментов за время участия вконкурсе — это на всю жизнь 🙂
До встречи на следующих конкурсах по компьютерному зрению!
Полезные материалы на Хабре
- Алгоритм другой команды: Решение задачи «Яндекс интернет математика — 2011». Определение визуальной схожести изображений
- Описание детектора и дескриптора SURF: Обнаружение устойчивых признаков изображения: метод SURF
- Описание детектора и дескриптора SIFT: Построение SIFT дескрипторов и задача сопоставления изображений
- Описание альтернативного подхода к фильтрации соответствий: Фильтрация ложных соответствий между изображениями при помощи динамического графа соответствий
- Tutorial про стандартную схему применения локальных особенностей, которую мы использовали (детектор + дескриптор + поиск соответствий + гомография): Распознавание плоских объектов OpenCV 2.4
Авторы статьи:
Мария Димашова (Itseez, research engineer), mdim
Илья Лысенков (Itseez, research engineer), billys
ссылка на оригинал статьи http://habrahabr.ru/company/itseez/blog/158645/
Добавить комментарий