Прошло уже больше года после завершения конкурса "Интернет-математика: Яндекс.Карты", но нас до сих пор спрашивают об алгоритме, который принёс нам победу в этом конкурсе. Узнав о том, что недавно Яндекс объявил о старте очередной "Интернет-математики", мы решили поделиться опытом нашего прошлогоднего участия и описать наш подход. Разработанный алгоритм смог с точностью 99.44% правильно определить лишние изображения в сериях панорамных снимков, например, как здесь:
В этой статье мы описываем основные идеи алгоритма и приводим его детали для интересующихся, рассказываем об извлечённых уроках и о том, как это всё вообще было.
Исходный код нашего решения доступен на github (C++ с использованием OpenCV).
Описание конкурсной задачи
В 2011 году Яндекс предложил участникам конкурса интересную задачу по компьютерному зрению, поэтому нашей компании, специализирующейся в этой области, было бы грех не принять участие. Задача заключалась в поиске лишних изображений в сериях панорамных снимков с Яндекс.Карт. В каждой серии было дано по 5 изображений, часть из которых (3, 4 или все 5) были сделаны в одном месте и примерно в одно время, а остальные были лишними. Например, изображения 1, 3 и 5 на серии выше составляют панораму, а изображения 2 и 4 — лишние. Всего было дано 6000 серий и требовалось найти лишние снимки в каждой из них.
От начала до финала
Узнав про конкурс из нашей корпоративной рассылки, каждый из нас скачал себе данные, несколько дней упорно разглядывал картинки (было чем заняться — всего картинок 6000 x 5 = 30 000) и надеялся победить в одиночку. Вскоре стало понятно, что задача на самом деле не такая простая, как показалось на первый взгляд. Поэтому мы решили собраться, обсудить идеи и провести переговоры по возможному объединению усилий. Как выяснилось, у нас были очень разные подходы к решению задачи и было бы здорово дополнить друг друга в одной команде. Так мы и сделали, а дальше всё по стандартной схеме: создали общий репозиторий кода, написали инфраструктуру для тестирования точности алгоритмов, и каждый приступил к проработке своих идей. Мы изучали подходящие статьи, периодически устраивали мозговые штурмы, пробовали новые идеи и отбрасывали неработающие… Так прошёл месяц.
И вот настал финальный день — по условиям конкурса в последний день Яндекс выдавал новый набор данных, на которых нужно было прогнать алгоритм и получить ответ за сутки. Нашей команде предстояла бессонная ночь на работе, так что первоочередной задачей стала всё-таки закупка чипсов и всего, что нужно для продуктивного программирования. После получения доступа к финальному набору данных мы запустили лучшую версию нашего алгоритма, стали разглядывать новую порцию из 30 000 картинок и до последнего генерировали новые идеи, чтобы учесть новые свойства данных (правда, к 5 утра получался уже какой-то бред, который до сих пор у нас является поводом для шуток). Всё оказалось не зря: через несколько дней мы узнали, что наша команда “Мифический Нижний Новгород” стала победителем конкурса!
Далее мы расскажем о том, какой алгоритм у нас получился в итоге.
Основные идеи алгоритма
Итак, задача состоит в разбиении серии изображений на группы: искомая панорама и лишние изображения. Чтобы найти такое разбиение, нужно для любой пары изображений уметь оценивать правдоподобность того, что они принадлежат одной панораме. Для этого мы ввели две меры схожести для пары изображений, основанные на дополняющих друг друга подходах: сравнение цветовых гистограмм изображений и поиск общих частей на изображениях. Мы скомбинировали эти две меры в одну и использовали полученную меру для разбиения изображений на группы (кластеризации). Меру каждого из подходов можно было бы использовать и по отдельности, но комбинирование позволяет объединить их сильные стороны.
Гистограммы позволяют сравнить частоты появления цветов на одном изображении с частотами на другом. Поскольку, согласно описанию задачи, снимки в одной панораме изображают одну сцену в одно время с близких положений камеры, то их цветовые характеристики, как правило, схожи между собой, а у лишних изображений они обычно другие. Поэтому расстояние между гистограммами даёт подходящую оценку близости изображений. Например, лишние изображения из серии, приведённой в начале статьи, гораздо темнее панорамных снимков, поэтому в гистограммах лишних снимков будут преобладать тёмные цвета, и эти гистограммы будут далеки от гистограмм панорамных изображений.
Второй подход, поиск общих частей на изображениях, позволяет определить, что два снимка относятся к одной панораме в случае, когда между ними есть достаточное пересечение, например на них встречается один и тот же объект. Это достигается путём использования популярного в компьютерном зрении подхода: на двух сравниваемых изображениях детектируются характерные ключевые точки, после чего осуществляется поиск соответствий между ними, например путем сравнения окрестностей этих точек. Если удалось найти много похожих окрестностей, то, скорее всего, они относятся к одним и тем же объектам и это два изображения одной и той же сцены. В этом подходе мерой близости является количество похожих окрестностей. Например, работа этого подхода проиллюстрирована на Рис. 1 и 2.
Рис. 1. Пример серии, в которой поиск общих частей даёт правильную классификацию, поскольку на снимках есть части одного и того же здания. При этом цветовые гистограммы изображений 1 и 4 сильно отличаются от остальных, поэтому гистограммный подход считает эти два снимка лишними, что на самом деле неверно.
Рис. 2. Соответствующие друг другу ключевые точки, найденные алгоритмом.
Эти два подхода взаимно дополняют друг друга. Гистограммный подход может работать даже в тех случаях, когда между снимками одной панорамы нет никаких пересечений и общих частей (см. пример на Рис. 3). Однако в некоторых случаях пересечение между изображениями есть, но остальные части очень сильно отличаются между собой по цвету (например, солнце зашло за тучу). В этом случае гистограммы будут далеки друг от друга, а поиск общих частей может определить, что эти изображения относятся всё же к одной панораме даже по небольшому перекрытию (см. пример на Рис. 1 и 2).
Рис. 3. Пример серии, в которой между снимками одной панорамы (3, 4 и 5) нет областей с общими ключевыми точками, но благодаря цветовым гистограммам получается правильная классификация (изображения 1 и 2 — лишние).
Как показали эксперименты, большую часть правильных ответов способен дать гистограммный подход в одиночку, а добавление второго подхода лишь в немногих случаях улучшает классификацию.
Для интересующихся компьютерным зрением и деталями этих двух подходов написаны два следующих раздела, а всем остальным предлагается перейти к Объединению двух подходов и Результатам.
Детали гистограммного подхода
При реализации было использовано цветовое пространство YCrCb, поскольку в нём явно выделена компонента яркости. Это позволяет взять меньшее количество бинов (интервалов группировки) по этой компоненте и тем самым повысить устойчивость алгоритма к изменению освещённости и теням.
Также к этим трём компонентам (Y, Cr, Cb) для построения гистограмм мы добавили ещё одну — ординату пикселя на изображении, чтобы учесть пространственное расположение цветов. Эта идея позволяет более точно сравнивать цвета объектов, которые обычно располагаются на одной высоте: дорога должна сравниваться с дорогой, трава с травой, небо с небом. Такое разбиение изображения по горизонтальным полосам было введено в связи с тем, что в конкурсных данных изображения внутри одной панорамы сдвинуты относительно друг друга преимущественно по горизонтали.
Таким образом, строилась четырёхмерная гистограмма с 12 бинами для яркости, 256 бинами для каждой из двух цветовых компонент и 4 бинами для ординаты пикселя.
Для вычисления расстояния между гистограммами использовалось их пересечение (Histogram Intersection Distance). Для изображений одного разрешения эта дистанция фактически отражает количество похожих пикселей между двумя изображениями.
Детали подхода на основе локальных особенностей
Одним из самых успешных методов в компьютерном зрении является использование уникальных локальных особенностей на изображении, например углов или центров блобов (небольших однородных областей). Этот подход применим, если сцена достаточно текстурная, то есть содержит большое количество таких локальных особенностей. На снимках с Яндекс.Карт изображены текстурные уличные сцены, поэтому этот подход разумно применять. Однако в конкурсном наборе данных существует несколько сложностей: изображения имеют низкое разрешение (300x300 пикселей) и нередко присутствуют большие нетекстурные области (асфальт, небо, …). Столь малое разрешение влечет за собой низкую повторяемость (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
Автор: Billys
