- PVSM.RU - https://www.pvsm.ru -
Прошло уже больше года после завершения конкурса "Интернет-математика: Яндекс.Карты [1]", но нас до сих пор спрашивают об алгоритме, который принёс нам победу [2] в этом конкурсе. Узнав о том, что недавно Яндекс объявил о старте очередной "Интернет-математики [3]", мы решили поделиться опытом нашего прошлогоднего участия и описать наш подход. Разработанный алгоритм смог с точностью 99.44% правильно определить лишние изображения в сериях панорамных снимков, например, как здесь:
В этой статье мы описываем основные идеи алгоритма и приводим его детали для интересующихся, рассказываем об извлечённых уроках и о том, как это всё вообще было.
Исходный код нашего решения доступен на github [4] (C++ с использованием OpenCV [5]).
В 2011 году Яндекс предложил участникам конкурса интересную задачу по компьютерному зрению, поэтому нашей компании [6], специализирующейся в этой области, было бы грех не принять участие. Задача заключалась в поиске лишних изображений в сериях панорамных снимков с Яндекс.Карт. В каждой серии было дано по 5 изображений, часть из которых (3, 4 или все 5) были сделаны в одном месте и примерно в одно время, а остальные были лишними. Например, изображения 1, 3 и 5 на серии выше составляют панораму, а изображения 2 и 4 — лишние. Всего было дано 6000 серий и требовалось найти лишние снимки в каждой из них.
Узнав про конкурс из нашей корпоративной рассылки, каждый из нас скачал себе данные, несколько дней упорно разглядывал картинки (было чем заняться — всего картинок 6000 x 5 = 30 000) и надеялся победить в одиночку. Вскоре стало понятно, что задача на самом деле не такая простая, как показалось на первый взгляд. Поэтому мы решили собраться, обсудить идеи и провести переговоры по возможному объединению усилий. Как выяснилось, у нас были очень разные подходы к решению задачи и было бы здорово дополнить друг друга в одной команде. Так мы и сделали, а дальше всё по стандартной схеме: создали общий репозиторий кода, написали инфраструктуру для тестирования точности алгоритмов, и каждый приступил к проработке своих идей. Мы изучали подходящие статьи, периодически устраивали мозговые штурмы, пробовали новые идеи и отбрасывали неработающие… Так прошёл месяц.
И вот настал финальный день — по условиям конкурса в последний день Яндекс выдавал новый набор данных, на которых нужно было прогнать алгоритм и получить ответ за сутки. Нашей команде предстояла бессонная ночь на работе, так что первоочередной задачей стала всё-таки закупка чипсов и всего, что нужно для продуктивного программирования. После получения доступа к финальному набору данных мы запустили лучшую версию нашего алгоритма, стали разглядывать новую порцию из 30 000 картинок и до последнего генерировали новые идеи, чтобы учесть новые свойства данных (правда, к 5 утра получался уже какой-то бред, который до сих пор у нас является поводом для шуток). Всё оказалось не зря: через несколько дней мы узнали, что наша команда “Мифический Нижний Новгород” стала победителем конкурса!
Далее мы расскажем о том, какой алгоритм у нас получился в итоге.
Итак, задача состоит в разбиении серии изображений на группы: искомая панорама и лишние изображения. Чтобы найти такое разбиение, нужно для любой пары изображений уметь оценивать правдоподобность того, что они принадлежат одной панораме. Для этого мы ввели две меры схожести для пары изображений, основанные на дополняющих друг друга подходах: сравнение цветовых гистограмм изображений и поиск общих частей на изображениях. Мы скомбинировали эти две меры в одну и использовали полученную меру для разбиения изображений на группы (кластеризации). Меру каждого из подходов можно было бы использовать и по отдельности, но комбинирование позволяет объединить их сильные стороны.
Гистограммы [7] позволяют сравнить частоты появления цветов на одном изображении с частотами на другом. Поскольку, согласно описанию задачи, снимки в одной панораме изображают одну сцену в одно время с близких положений камеры, то их цветовые характеристики, как правило, схожи между собой, а у лишних изображений они обычно другие. Поэтому расстояние между гистограммами даёт подходящую оценку близости изображений. Например, лишние изображения из серии, приведённой в начале статьи, гораздо темнее панорамных снимков, поэтому в гистограммах лишних снимков будут преобладать тёмные цвета, и эти гистограммы будут далеки от гистограмм панорамных изображений.
Второй подход, поиск общих частей на изображениях, позволяет определить, что два снимка относятся к одной панораме в случае, когда между ними есть достаточное пересечение, например на них встречается один и тот же объект. Это достигается путём использования популярного в компьютерном зрении подхода: на двух сравниваемых изображениях детектируются характерные ключевые точки, после чего осуществляется поиск соответствий между ними, например путем сравнения окрестностей этих точек. Если удалось найти много похожих окрестностей, то, скорее всего, они относятся к одним и тем же объектам и это два изображения одной и той же сцены. В этом подходе мерой близости является количество похожих окрестностей. Например, работа этого подхода проиллюстрирована на Рис. 1 и 2.
Рис. 1. Пример серии, в которой поиск общих частей даёт правильную классификацию, поскольку на снимках есть части одного и того же здания. При этом цветовые гистограммы изображений 1 и 4 сильно отличаются от остальных, поэтому гистограммный подход считает эти два снимка лишними, что на самом деле неверно.
Рис. 2. Соответствующие друг другу ключевые точки, найденные алгоритмом.
Эти два подхода взаимно дополняют друг друга. Гистограммный подход может работать даже в тех случаях, когда между снимками одной панорамы нет никаких пересечений и общих частей (см. пример на Рис. 3). Однако в некоторых случаях пересечение между изображениями есть, но остальные части очень сильно отличаются между собой по цвету (например, солнце зашло за тучу). В этом случае гистограммы будут далеки друг от друга, а поиск общих частей может определить, что эти изображения относятся всё же к одной панораме даже по небольшому перекрытию (см. пример на Рис. 1 и 2).
Рис. 3. Пример серии, в которой между снимками одной панорамы (3, 4 и 5) нет областей с общими ключевыми точками, но благодаря цветовым гистограммам получается правильная классификация (изображения 1 и 2 — лишние).
Как показали эксперименты, большую часть правильных ответов способен дать гистограммный подход в одиночку, а добавление второго подхода лишь в немногих случаях улучшает классификацию.
Для интересующихся компьютерным зрением и деталями этих двух подходов написаны два следующих раздела, а всем остальным предлагается перейти к Объединению двух подходов [8] и Результатам [9].
При реализации было использовано цветовое пространство YCrCb [10], поскольку в нём явно выделена компонента яркости. Это позволяет взять меньшее количество бинов (интервалов группировки) по этой компоненте и тем самым повысить устойчивость алгоритма к изменению освещённости и теням.
Также к этим трём компонентам (Y, Cr, Cb) для построения гистограмм мы добавили ещё одну — ординату пикселя на изображении, чтобы учесть пространственное расположение цветов. Эта идея позволяет более точно сравнивать цвета объектов, которые обычно располагаются на одной высоте: дорога должна сравниваться с дорогой, трава с травой, небо с небом. Такое разбиение изображения по горизонтальным полосам было введено в связи с тем, что в конкурсных данных изображения внутри одной панорамы сдвинуты относительно друг друга преимущественно по горизонтали.
Таким образом, строилась четырёхмерная гистограмма с 12 бинами для яркости, 256 бинами для каждой из двух цветовых компонент и 4 бинами для ординаты пикселя.
Для вычисления расстояния между гистограммами использовалось их пересечение (Histogram Intersection Distance [11]). Для изображений одного разрешения эта дистанция фактически отражает количество похожих пикселей между двумя изображениями.
Одним из самых успешных методов в компьютерном зрении является использование уникальных локальных особенностей на изображении, например углов или центров блобов (небольших однородных областей). Этот подход применим, если сцена достаточно текстурная, то есть содержит большое количество таких локальных особенностей. На снимках с Яндекс.Карт изображены текстурные уличные сцены, поэтому этот подход разумно применять. Однако в конкурсном наборе данных существует несколько сложностей: изображения имеют низкое разрешение (300x300 пикселей) и нередко присутствуют большие нетекстурные области (асфальт, небо, …). Столь малое разрешение влечет за собой низкую повторяемость (repeatability [12]) детектора локальных особенностей: ключевая точка, найденная на одном из изображений, часто будет не продетектирована на другом снимке той же панорамы, и мы не сможем определить, что между изображениями есть соответствия. Для решения этих проблем мы выставили такие параметры детектора локальных особенностей, чтобы он находил большое число ключевых точек на изображении (~10k). Однако это приводит к тому, что особенности на сравниваемых изображениях становятся менее уникальными, и при поиске соответствующих друг другу особенностей часто находятся ложные соответствия. Поэтому для выбора правильных соответствий мы применили несколько дополнительных фильтраций. Перейдём к деталям.
В цикле поиска гомографии по схеме RANSAC для оценки качества очередной гипотезы о гомографии применялось несколько эвристик: фильтр по минимальному сингулярному числу матрицы гомографии, фильтр инлаеров (соответствий, удовлетворяющих текущей гипотезе о матрице гомографии) по согласованности изменений ориентаций продетектированных углов, замена близко расположенных инлаеров одним. В результате выбиралась гомография, дающая наибольшее количество инлаеров.
На многих снимках этому алгоритму хватало даже небольшого пересечения между изображениями, чтобы найти достаточное количество соответствующих ключевых точек. Так, интересный и неожиданный для нас пример работы описанного алгоритма приведён на Рис. 4.
Рис. 4. Забавная ситуация, когда снимки можно объединить в одну панораму по присутствию одних и тех же облаков на небе. На этой паре снимков гистограммы чувствуют себя неуверенно из-за большой тени, но ситуацию спасают локальные особенности и облачная погода.
Описанные подходы позволяют посчитать два вида дистанций между изображениями. Чтобы учесть оба подхода, мы комбинируем эти дистанции следующим образом:
dcomb = min(c * dhist, dfeat),
где
dcomb — комбинированное расстояние,
dhist и dfeat — нормированные в отрезок [0, 1] расстояния, вычисленные с помощью подходов на гистограммах и локальных особенностях соответственно;
c — коэффициент меньший единицы, позволяющий придать больший приоритет результатам работы алгоритма, использующего гистограммы.
Для объединения двух подходов была выбрана именно функция минимума, потому что если хотя бы одна из двух дистанций мала, то изображения действительно близки.
Вычислив попарные комбинированные расстояния между изображениями одной серии, мы проводим иерархическую кластеризацию (Agglomerative hierarchical clustering using single-linkage [24]) этих изображений. Кластер с максимальным количеством элементов признаётся искомой панорамой, а остальные изображения лишними. Такая иерархическая кластеризация очень естественно подходит для этой задачи, поскольку внутри одной панорамы могут быть далёкие непересекающиеся изображения, которые связаны цепочкой других близких друг к другу изображений панорамы, и этот метод позволяет объединить такие изображения в одну панораму.
Итак, после упорной работы над нашим алгоритмом, на финальном наборе данных он показал очень хороший результат: было правильно классифицировано 99.44% изображений, что позволило занять первое место в конкурсе. А также получить приз в размере 100 000 рублей на празднование победы :-)
В качестве заключения мы хотим поделиться несколькими уроками, которые мы извлекли или закрепили, участвуя в конкурсе. Нам они точно пригодились.
Рис. 5. Пример весьма непростой серии. Как вы думаете, какие изображения здесь лишние?
Проблема с неразрешимыми сериями была поднята участниками на форуме конкурса, и организаторы обещали не допустить такого в финальном наборе данных. Это означало, что финальный набор данных будет иметь другие свойства, чем предварительный набор. Тем самым не выполнялось фундаментальное предположение алгоритмов машинного обучения, что тренировочная и тестовая выборка должны быть порождены одним вероятностным распределением. Поэтому мы решили использовать максимально простые алгоритмы с небольшим количеством настраиваемых параметров, так как иначе крайне высок риск переобучения. Как показала практика, это было очень ценное наблюдение, поскольку несколько других участников, использующих продвинутые алгоритмы машинного обучения, действительно переобучились и показали не такой хороший результат на финальных данных, как на предварительных.
До встречи на следующих конкурсах по компьютерному зрению!
Авторы статьи:
Мария Димашова (Itseez, research engineer), mdim [30]
Илья Лысенков (Itseez, research engineer), billys [31]
Автор: Billys
Источник [32]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/20429
Ссылки в тексте:
[1] Интернет-математика: Яндекс.Карты: http://imat2011.yandex.ru/
[2] победу: http://yandex.livejournal.com/140651.html
[3] Интернет-математики: http://switchdetect.yandex.ru/
[4] github: https://github.com/ilysenkov/imat2011
[5] OpenCV: http://opencv.org/
[6] компании: http://itseez.com/
[7] Гистограммы: http://docs.opencv.org/doc/tutorials/imgproc/histograms/histogram_calculation/histogram_calculation.html#histogram-calculation
[8] Объединению двух подходов: #Mixing
[9] Результатам: #Results
[10] YCrCb: http://docs.opencv.org/modules/imgproc/doc/miscellaneous_transformations.html#cvtcolor
[11] Histogram Intersection Distance: http://docs.opencv.org/modules/imgproc/doc/histograms.html#comparehist
[12] repeatability: http://www.robots.ox.ac.uk/~vgg/research/affine/det_eval_files/vibes_ijcv2004.pdf
[13] FAST: http://www.edwardrosten.com/work/fast.html
[14] Гауссовой пирамиды изображений: http://docs.opencv.org/doc/tutorials/imgproc/pyramids/pyramids.html
[15] SURF: http://www.vision.ee.ethz.ch/~surf/index.html
[16] SIFT: http://en.wikipedia.org/wiki/Scale-invariant_feature_transform
[17] L1 расстоянию: http://en.wikipedia.org/wiki/Taxicab_geometry
[18] FLANN: http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN
[19] cross-check: http://docs.opencv.org/modules/features2d/doc/common_interfaces_of_descriptor_matchers.html#bfmatcher-bfmatcher
[20] гомографии: http://en.wikipedia.org/wiki/Homography
[21] RANSAC: http://ru.wikipedia.org/wiki/RANSAC
[22] теории: http://www.robots.ox.ac.uk/~vgg/hzbook/
[23] фундаментальной матрицы: http://en.wikipedia.org/wiki/Fundamental_matrix_(computer_vision)
[24] Agglomerative hierarchical clustering using single-linkage: http://en.wikipedia.org/wiki/Hierarchical_clustering
[25] Решение задачи «Яндекс интернет математика — 2011». Определение визуальной схожести изображений: http://habrahabr.ru/post/132555/
[26] Обнаружение устойчивых признаков изображения: метод SURF: http://habrahabr.ru/post/103107/
[27] Построение SIFT дескрипторов и задача сопоставления изображений: http://habrahabr.ru/post/106302/
[28] Фильтрация ложных соответствий между изображениями при помощи динамического графа соответствий: http://habrahabr.ru/post/154975/
[29] Распознавание плоских объектов OpenCV 2.4: http://habrahabr.ru/post/155651/
[30] mdim: http://habrahabr.ru/users/mdim/
[31] billys: http://habrahabr.ru/users/billys/
[32] Источник: http://habrahabr.ru/post/158645/
Нажмите здесь для печати.