Поиск по подобию. Поиск нечетких дубликатов. Лекции от Яндекса

В прошлый раз, если вы помните, мы говорили о том, как можно сравнивать изображения, как их можно представлять в виде векторов признаков, в виде набора каких-то чисел, и как можно сравнивать между собой эти самые вектора. При этом мы говорили, что в принципе изображения можно описать с помощью так называемых глобальных признаков. То есть, когда мы описываем всю картинку целиком, считаем гистограмму по всему изображению, и, собственно, мы рассматривали такие признаки. Я вам говорила о том, что также достаточно популярны, и для ряда задач возникает необходимость вычислять так называемые локальные признаки. То есть, когда у нас описывается не вся картинка целиком, а некая ее окрестность. Ну, собственно, когда у нас глобальные признаки не работают. Вот здесь вот несколько примеров приведено. К примеру, когда у нас существенно изменяется масштаб, то есть, вот эти два фрагмента, они очевидно совпадают. Но, тем не менее, если мы попытаемся посчитать глобальные признаки, так скажем, текстуру по всей картинке здесь, по всей картинке здесь, она будет разная. Гистаграммы, какие угодно, тоже. Формы – тоже. То есть, в принципе нам нужно понимать, что нужно как-то иметь возможность сопоставить вот этот фрагмент вот с этим фрагментом. То есть, посчитать признак, который бы описывал только фрагмент изображения. Изменение, собственно, точки, с которой мы смотрим на объект. То есть, масштаб здесь примерно один и тот же, но, тем не менее, то, что мы здесь смотрим сквозь окно, опять у нас достаточно сильно меняет любой глобальный признак, который мы можем построить по вот этой картинке по сравнению с этим. То есть, они не найдутся друг по другу. Ну, если порог их будет достаточно маленький.

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

Что же можно предложить для того, чтобы побороть все эти неприятности, попытаться посчитать локальные признаки по каким-то фрагментам изображения. То есть, идея в том, что, не смотря на то, что если мы пытаемся построить какую-то числовую характеристику по всей картинке, она будет отличаться для этих двух изображений, можно найти какие-то фрагменты на одной и второй картинке так, что они будут сопоставимы друг с другом. То есть, мы можем сказать, что у нас явно этот фрагмент сопоставим с этим и вот этот фрагмент сопоставим с вот этим. Встают два вопроса, собственно: как выбирать эти самые фрагменты? И второй вопрос: как описывать фрагменты? Ну, собственно, интуитивный, такой, в лоб, подход, как сопоставлять фрагменты, и как их выбирать – это, то есть, мы берем, полностью сканируем нашу пару изображений. То есть, мы выбираем окошко какого-то размера и дальше поехали. На одной картинке зафиксировали. На вторую смотрим: совпадает, не совпадает. Не совпадает, не совпадает, снова не совпадает, вот – попали. Более менее похоже. Ура, совпадение есть. Понятное дело, что этот подход, в общем-то, с одной стороны, конечно, хорош, потому что мы перебираем все возможные варианты и точно ничего не пропустим. Но, с другой стороны, он вычислительно очень сложен, потому что нужно перебрать, непонятно какого размера брать окошко, непонятно, собственно, нужно перебрать все возможные смещения этого окна в одной картинке и во второй картинке. И еще одна проблема, связанная с этим, то, что у нас получается на самом деле слишком много сопоставимых пар. Потому что, если мы возьмем, скажем, что вот у нас изначально вот это вот окно сопоставлялось, это фрагмент сопоставлялся с этим. На самом деле, сдвиг вот здесь вот на этом изображении, окошко на один писель вправо, на один пиксель – влево, он не даст существенного изменения вектору признаков. Получается, что у нас будет соответствий очень много. Нам надо будет заморачиваться потом искать среди перекрывающихся наиболее совпадающие и так далее. Это, в общем, делать не хочется. Другой вариант, который в принципе был бы более приятен и приемлем, это перебирать не все возможные варианты. Вопрос в том, какие же варианты нам перебирать? Было бы хорошо, если бы мы могли на изображении находить какие-то такие вот выделенные особые точки, которые являются наиболее информативными. То есть, которые в себе содержат наибольшую информацию о том, что представлено в этом изображении.

Фичерс — это обычно вот именно признаки, то есть, какие-то характеристики. Здесь это точка интересует. То есть, это та позиция, та точка изображения, которая представляет собой некий интерес.
Р: вот-вот, я потому и спросил, что в некоторой смежной области, там как раз используют термин фичерс для обозначения тех точек изображения, которые…
Нет. То есть, обычно, здесь под «фичами» понимают вот именно описание, какие-то характеристики. То есть, вокруг этой точки потом можно построить фич-вектор или посчитать какую-нибудь одну «фичу», которая будет описывать фрагмент, построенный вокруг этой вот особенности. В русской литературе их называют чаще либо «точными особенностями», либо «особыми точками», либо вообще переводят, кто во что горазд, кальки с английского как «ключевые точки», «точки интереса», «точки внимания», в общем, всякие разные варианты возможны. На самом деле идея попытаться найти такие точки, она тоже сопоставима с психологией нашей. Наверняка многие слышали про то, что проводят исследования, к примеру, слежения за вашим зрачком. Если вы переходите на какую-то страницу в вебе, для того, чтобы понять, какая область страницы для вас наиболее интересна, можно повесить веб-камеру, которая будет следить за передвижениями вашего зрачка и, собственно, те координаты веб-страницы, на которых вы больше всего задерживаетесь своим зрачком, предполагается, что они более интересны для вас. То есть, это то, на чем фокусируется наше зрение при попытке понять содержание страницы. И если на самом деле посмотреть вот на такую карту фокусировки и движения зрачка, понятно, что зрачок далеко неравномерно двигается по всему экрану, мы фокусируемся на каких-то таких особых точках. Мы фокусируемся на тех действиях, где есть выделение, то есть, то, что привлекает наше внимание.

Было бы хорошо пытаться находить такие же точки на картинках. То есть, понятно: меньше сравнений существенно. Плюс, скорее всего, мы можем добиться того, чтобы эти точки были более-менее изолированы друг от друга, и, соответственно, у нас не будет проблемы пересекающихся фрагментов, как в предыдущем варианте. Но, в то же время у нас, конечно, нет гарантии, что мы найдем абсолютно все сопоставимые пары. Ну и основной вопрос: как же искать эти самые ключевые точки? Давайте попробуем подумать, какие должны быть, то есть, какие требования мы можем предъявить к этим самым особым точкам, особым фрагментам? С одной стороны, мы хотим, чтобы их было не очень много – существенно меньше, чем пикселей на изображении для того, чтобы выполнялись свойства… для того, чтобы перебор был неполный, и для того, чтобы эти самые фрагменты были разделены. Чтобы у нас не было пересечения большого количества пар. С другой стороны, мы хотим, чтобы эти фрагменты были такие репрезентативные, чтобы было легко сопоставлять один фрагмент на одном изображении и второй фрагмент на другом изображении. То есть, если, к примеру, у нас совершенно однородный фон, понятно, что мы можем выбрать несколько фрагментов, которые будут неотличимы друг от друга, и если у нас на второй картинке есть точно такой же фрагмент, непонятно, с каким, из этих его сопоставлять. То есть, они должны быть как-то вот уникальны в некотором роде. Они должны быть повторяемые в том смысле, что если у нас есть изображение одного и того же объекта, или как-то видоизмененная одна и та же картинка, там как-то пожатая, масштабированная иначе, то мы хотим, чтобы эти фрагменты и какие-нибудь точные особенности совпадали в этих двух картинках. То есть, точка, которую мы посчитали особенной, она, скажем, если мы берем лицо человека, так особыми точками могут быть его глаза. Если мы нашли глаза на одном изображении, мы хотим найти глаза и на другом изображении. То, что на одном изображении мы посчитали особенностями глаза, на втором изображении у нас рот — нет, нам не подойдет, потому что мы опять не сможем их сопоставить. Ну и эти вот сами фрагменты, которые вокруг особых точек строятся, они должны быть небольшого размера для того, чтобы быть устойчивыми к частичному перекрыванию. То есть, если мы вернемся сюда, то вот здесь если у нас был фрагмент большой, то опять же у нас вектор признаков, построенный по этому фрагменту, существенно бы отличался от того, что здесь. То есть, предполагается, что, вообще говоря, в небольшой окрестности этой самой особой точки изменения не должны быть настолько существенны, что вектора признаков будут отличаться.

Как, допустим, мы умеем искать эти самые особые точки? Как в таком случае будет выглядеть сравнение этих двух изображений с помощью вот этих локальных признаков? В первую очередь мы действительно должны найти особые точки каким-то образом и построить особые фрагменты, как окрестность вокруг этой особой точки. При этом хорошо бы, чтобы наши особые точки были инвариантны к изменению освещения, к изменению, то есть, к разным геометрическим или фотометрическим преобразованиям картинки. То есть, если мы ее растягиваем, сжимаем, объект куда-то переезжает по изображению, если у нас изменяется уровень яркости — интенсивности изображения, чтобы точка все равно находилась все время в одном и том же месте. И для того, чтобы фрагмент у нас тоже был инвариантен к повороту и к изменению масштаба. Дальше мы строим вектор признаков вот по такому фрагменту особому и сопоставляем наборы локальных признаков для разных фрагментов на разных картинках. К примеру, у нас есть одна и та же кошка, повернутая. Мы нашли точечные особенности, для каждой точечной особенности определили окрестность, построили вектор признаков для этой окрестности и хотим иметь возможность их сравнивать и дальше, собственно, две картинки сопоставлять между собой в зависимости от того, какое количество этих векторов признаков у них более-менее совпадает. Ну, и плюс еще на самом деле имеет смысл смотреть как на относительное расположение друг относительно друга сопоставимых фрагментов. То есть, к примеру, если мы говорим, что у нас вот эта точка соответствует вот этой, а вот эта точка соответствует вот этой, сохраняется ли у нас… три, на самом деле, надо было выбрать точки. Ну, вот здесь у нас еще есть особенность, и вот здесь особенность. Скажем, мы сравнили, нашли, выделили все эти точечные особенности, построили фрагменты, построили вектора признаков вокруг них, поняли, что у нас вот этот вот фрагмент соответствует вот этому, вот этот соответствует вот этому, а коленка соответствует коленке. И дальше мы можем еще использовать информацию об относительном расположении этих самых фрагментов здесь и здесь. То есть, у нас в принципе, как они расположены относительно друг друга внутри одного изображения, предполагается, что не сильно меняется.

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

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

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

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

Наверное, наиболее применимый детектор углов, так называемый детектор Харриса, он смотрит на направление градиентов каждой точки, и сейчас мы будем про это говорить более подробно. Рассмотрим вот такую картинку, пирамиду чудесную, и вытащим три фрагмента. Собственно, один фрагмент полностью однородный, второй фрагмент содержит один контур однонаправленный, третий фрагмент содержит явно выраженный контур. То есть, у нас есть два явно выраженных направления градиента. Построим следующую визуализацию. Посчитаем для каждой точки внутри вот этого окошка градиент по иксу и по игреку. И дальше попробуем нанести их вот на такую координатную сетку, то есть, здесь у нас значения по горизонтали – это градиент по иксу, значения по вертикали – градиент по игреку. В общем, нетрудно предположить по понятным причинам, градиенты практически всех точек, они вот тут скучковались в нуле, потому что никаких изменений яркости не происходит. То есть, у нас производная везде – ноль. Конечно, она тут не точно в нуле, потому что это все-таки изображение, у которого далеко не все пиксели полностью совпадают, то есть там какое-то изменение незначительное яркости происходит, поэтому вот тут оно немножко вокруг нуля бегает. Если мы попытаемся проделать то же самое для вот этого фрагмента, то заметим, что у нас уже намного больше регион покрыт, и при этом можно заметить, что на самом деле у нас прослеживается вот такое какое-то одно направление, видимое на этой диаграмме, собственно, которое соответствует углу в 450. То есть, у нас угол в 450 – это означает, как производная по иксу, так и по игреку дает какое-то ненулевое значение. И, при том, что это угол в в 450, они, наверное, более-менее равны друг другу и вот, собственно, это мы имеем здесь. При этом, опять же, если бы мы взяли только точки вдоль вот этого контура исключительно, и контур был бы у нас совершенно идеальный, то есть, там резкий переход из белого в черный, то тогда мы бы получили… Кто-нибудь ответит, где бы мы получили облако? Мы бы получили, на самом бы деле облако, были бы точки все вот здесь вот. Потому что у нас был бы ненулевой достаточно значительный отклик для каждой из точек. В результате получаем что-то тут вот вокруг нуля, потому что, во-первых, тут у нас есть точки опять же с однотонным фоном, что здесь, что здесь, это вокруг нуля нам дает отклик, ну и плюс тут еще какие-то тоже артефакты. Но, тем не менее направление в общем-то просматривается. Если мы возьмем фрагмент вот этот вот, то здесь уже можно при большом желании рассмотреть два направления основных градиента, собственно, соответствующие этим двум контурам.

Задача: если мы умеем строить вот такие визуализации, то есть, мы можем посмотреть на распределение градиентов по иксу, по игреку частично производных, как нам, имея распределение таких вот данных, понять, собственно, есть у нас там какое-то одно направление, есть у нас два направления, или у нас вообще всё вокруг нуля?

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

Соответственно, основная идея то, что мы для каждого окна смотрим на собственные числа ковариционной матрицы градиентов и, если у нас присутствует… не присутствует вообще собственных чисел, которые превышают какое-то пороговое значение, это означает, что регион у нас плоский полностью. Если у нас одно большое собственное число, то это означает, что у нас присутствует контур. Если у нас два больших собственных числа, мы имеем дело с углом. Ура! Собственно, как можно это всё просмотреть? Посмотрим на изменение интенсивности при сдвиге окошка на вот эту величину. То есть, у нас есть некая точка (икс-игрек), вокруг нее есть некий регион, и мы сдвигаем это окошко на величину [u,v]. Тогда смена интенсивностей будет задаваться таким вот, как разность квадратов, и плюс мы ее взвешиваем, то есть, это какая-то… На самом деле обычно берут такую взвешенную, чтобы отклик в центре давал больший результат, чем по краям этого окна, то есть у нас такая как бы получается нечеткая принадлежность точки к окошку, грубо говоря. Чаще всего в качестве этой взвешивающей функции берут (неразборчиво 0:28:50), можно брать просто, принимать значение этой функции за ноль внутри окна и… за ноль снаружи окна и за единичку – внутри окна. То есть, она у нас будет…

Если мы рассматриваем, одну размерность возьмем. Вот у нас наше окошко. Мы можем сказать, что у нас значение W от X будет единицей для всех пикселей внутри этого окна и нулем – снаружи, и тогда это просто определение окна, а можем сказать, что оно у нас там какое-нибудь вот такое, и тогда у нас получается, что те пиксели, которые ближе к центру окна, они имеют большее влияние на вот эту разность, чем те, которые снаружи. Соответственно, значение интенсивности точки, значение интенсивности в сдвинутой и взвешенная наша функция окна, которая позволяет нам как раз считать на каком-то подмножестве иксов и игреков.
Для небольших сдвигов «u» и «v» мы можем апроксимировать вот это значение сдвинутое, как значение в точке «икс-игрек» плюс частичная производная по иксу, умноженная на сдвиг по соответствующему направлению и плюс частичная производная по игреку, умноженная на сдвиг по направлению игрек. Если мы подставим вот это выражение вот сюда вот, то, сократив «И» от икс-игрек, получим такое вот выражение, которое, в свою очередь, можно записать уже в матричной форме, нас есть «u» и «v», где матрица – это получается такая взвешенная матрица частных производных от интенсивности. И собственные числа, собственно, мы считаем вот в этой матрице. То есть, получается: детектор Харриса заключается в том, что мы строим вот эту вот матрицу из частных производных интенсивности, вычисляем собственные значения и дальше смотрим на их соотношение.

В принципе вычисление собственных значений – задача достаточно ресурсоемкая. Вычислить определитель матрицы и след – несколько проще. Можно сказать, что, поскольку нам нужно… тут детектором угла на самом деле, признаком угла будет то, что у нас оба собственных значения достаточно велики, то в принципе можно построить вот такую… я не знаю, на русский лучше перевести. Такую меру угловатости точки, как разность определителя с квадратом следа, умноженным на какой-то коэффициент. Коэффициент обычно эмпирический, выбирается чаще всего где-то в этом промежутке. Ну, мы, в принципе, определитель матрицы – два на два, это просто произведение ее собственных чисел, след, сумма, ну, если мы сюда поставим, в принципе станет понятно, что требование выполняется. То есть, в том случае, когда у нас оба значения большие, мы получим большое значение вот этого R. В том случае, если у нас хотя бы одно значение большое, второе – маленькое, тогда у нас, скорее всего, вот тут будет отрицательное. И в том случае, когда у нас оба значения маленькие, то R будет близок к нулю.

Ну, собственно, предлагается выделять и определять, является ли точка угловой, по значению вот этой меры угловатости. Получается, что у нас детектор зависит только от значений собственных чисел матрицы, составленной из частных производных интенсивности, и принимает большие значения в угловых точках, отрицательные значения, но большие при этом по модулю – вдоль контуров и близок к нулю там, где точка вообще не особо никак, то есть она в плоском регионе. Это был детектор Харриса, то есть, как мы можем найти кандидатов в алгоритмы, кандидатов в угловые точки. Помимо этого, ну, обычно получается, что рядом с какой-то угловой точкой таких находится довольно много, то есть там будет целое облако тех, которые соответствуют вот этому условию там, где значения, к примеру, больше какого-то порога, но предлагается выбрать из них точки локального максимума, как, собственно, истинную угловую точку. Вот, наверное, самая распространенная картинка при рассказе про детектор Харриса. У нас вот есть некоторое животное, по всей видимости, корова, судя по пятнам. На нем попытаемся найти угловые точки, вот вычисляем значение «А», соответственно, чем ближе к красному, тем больше значение вот этой меры угловатости, и чем ближе к синему, тем ближе… ну, то есть, синий – ноль, красный – это большое. Дальше отфильтруем по порогу, значит, у нас остаются такие вот облака. И дальше для каждого выберем локальный максимум. Не знаю, видно вам или нет, но тут остались такие белые точечки, которые, если мы нанесем на обратно корову, то увидим, что они здесь, здесь. И они на самом деле, то есть это не всегда угол, но это чаще всего вот какое-то такое изменение интенсивности в нескольких направлениях. Ну и на самом деле они более-менее соответствуют друг другу. То есть, не видно, на самом деле есть точка вот здесь вот, и есть точка вот здесь вот, ей соответствующая. Есть точка вот здесь, и есть точка вот здесь. То есть, в принципе, они более-менее, не полностью эти множества совпадают, но тем не менее, по крайней мере, частично.

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

Какими свойствами обладает детектор Харриса? Он инвариантен к поворотам, потому что, несмотря на… то есть, мы повернем, если мы повернем наш угол, то у нас изменится направление, изменятся, собственно, вектора. Но значения собственных чисел останутся теми же. Соответственно, R у нас будет тем же самым, но и, в общем-то, точка, которая определяется углом, она останется тоже, той же самой. Плюс, он инвариантен к сдвигу интенсивности, поскольку всё вычисляется по производным, соответственно, то, что мы добавим какую-то константу интенсивности, это ни на что не повлияет. Но, к сожалению, он не инвариантен к изменению масштаба. Если мы посмотри на одну и ту же кривую в большом масштабе и наоборот, маленьком-большом, большом-маленьком, ну, короче, когда у нас уголок маленький и большой, и возьмем окошко одного и того же размера, то здесь у нас все точки будут определены как контур. В то время как, если мы его уменьшим, мы получим угол. Нехорошо. Что с этим можно сделать? И как добиться? Ну, такое, опять же, решение в лоб: мы можем попробовать рассмотреть фрагменты разного размера на разных картинках. То есть, мы будем изменять размер. Допустим, зафиксируем окрестность на одной картинке, будем изменять окрестность на второй до тех пор, пока мы не найдем такой размер фрагмента, который будет соответствовать второй картинке. То есть, у нас на двух изображениях найдутся соответствующие масштабы, но при условии, что эти два изображения уменьшенная-увеличенная копия одного и того же объекта, при которых вот эти вот маленькие фрагментики будут выглядеть похожими.

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

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

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

Здесь еще одно, визуализация. Если есть у нас две копии одного и того же изображения, берем этот фрагмент, то есть, у нас есть некая особая точка, размер этого особого фрагмента возьмем таким образом, чтобы в нем достигалась максимум некой функции. При этом точка вот этого локального максимума, то есть, этот вот масштаб, она называется обычно характеристическим масштабом, (неразборчиво по-английски), а соотношение между этими масштабами, оно равно соотношению, ну, соотношение точек локальных максимумов равно соотношению между масштабами соответствующих фрагментов. То есть, таким образом мы понимаем, насколько нам нужно увеличить или уменьшить вторую картинку, так чтобы ее фрагменты стали сопоставимы с фрагментами первой. Как должна выглядеть хорошая функция для определения этих соотношений масштаба в зависимости от размера региона? Она должна иметь желательно один выраженный локальный максимум. В общем, выясняется, что на самом деле таким свойством для изображений удовлетворяет фильтр Гаусса, Гауссиана и различные там операции над ними. В принципе мы можем в качестве такого детектора, инвариантного к масштабу, ну и, на самом деле, к изменению яркости, к изменению, к повороту, тоже выбрать либо Лапласиан, можем взять разность Гауссиана. То есть, мы оба сворачиваем наше изображение с фильтрами, ну, с масками Гауссиана или Лапласиана различных размеров, и пытаемся их сопоставить друг с дружкой. То есть, на самом деле мы строим вот такую как бы пирамиду в, можно сказать, что в масштабе, то есть, мы берем исходную картинку и сворачиваем ее с Лапласиан-Гауссиан, если вы помните, мексиканская шляпа такого вида, которая позволяет выделить на картинке наиболее контрастные точки с разным значением масштаба. То есть, у нас разный радиус у этой функции. Разный радиус на самом деле реагируют на разный размер каких-то там особенностей структур. То есть, если у нас есть на изображении некая там точка такого размера, то на нее отреагирует фильтр небольшого радиуса, больше – большего и так далее. Но суть в том, что мы пытаемся, то есть, мы фиксируем некоторую точку и дальше сворачиваем ее окрестность с Лапласианами разных размеров и получаем результат, то есть, у нас получается вот такая пирамида ответов, пирамида масштабов. И дальше мы производим поиск вот в этом пространстве таких точек, которые бы были максимальны на всех масштабах, и в то же время в каждом, из этих масштабов, чтобы выполнялось свойство вот этих вот угловой особенности. То есть, чтобы она была как максимальна с точки зрения изменения яркости, так и ровно в этой же точке, в независимости от масштаба, было бы то же самое. То есть, если мы берем, можно сказать, картинку разного масштаба и пытаемся посчитать для какой-то точки, является она особой или нет, то в качестве истинно особой мы оставляем только ту, которая является особой на разных масштабах. То есть, как-то так. Ну, второй вариант сделать примерно то же самое, это посчитать разность Гауссиана, собственно, по этой картинке видно, что форма ядер на самом деле очень похожа, и автор признака локального, про который мы будем дальше говорить, который (по-английски), он показал, что (неразборчиво 0:45:50) является приближением на самом деле Лапласиана-Гауссиана, можно использовать вместо Лапласиана-Гауссиана разницу Гауссиан, то есть, делаем всё то же самое, только вычисляем разницу Гауссиан. То есть, мы берем исходную картинку, сворачиваем ее с фильтром Гаусса, вычисляем разницу между ней и ее гауссовой копией, сворачиваем уменьшенную картинку, ну, или ту же самую картинку, только просто вместе с фильтром Гаусса меньшего размера и дальше вычисляем опять же разницу между, то есть, тут разница вместо… получается здесь разность по, как раз, по сигме, а здесь разница по масштабам. И дальше опять же осуществляем поиск вот в этом пространстве таких точек, которые являются локальными максимумами во всей этой пирамиде. Ну, здесь примерно то же самое. То есть, мы берем картинку с помощью Гаусса мы ее заблюриваем, вычисляем, получаем разность, картинку уменьшаем, проделываем ту же операцию, получаем вот здесь такую как бы пирамиду вот этих вот разностей.
Как нам локализовать ту особую точку так, чтобы она была, во-первых, угловой, и во-вторых, чтобы она была угловой вне зависимости от масштаба? Ну, мы берем такую вот пирамиду разных масштабов и для каждого масштаба определяем особенность в случае вот этого оператора Харрис-Лапласиана. Для каждого масштаба мы ищем угловую точку с помощью детектора Харриса и выбираем максимум с помощью уже Лапласиана по масштабам. И то же самое можно сделать с помощью разницы Гауссиан, с той только разницей, что у нас тут, собственно, не нужно, то есть, здесь мы сначала, грубо говоря, выполняем, ищем с помощью детектора Харриса угловые точки в каждом из масштабов и дальше используем Лапласиан для определения как бы наилучшего масштаба. То есть, выбираем такой масштаб, в котором у нас наша функция Лапласиан максимальна. А здесь мы ищем максимальную точку в пространстве вот этих вот разностей Гауссиан, как в масштабе, так и, собственно, в пространственном изменении яркости. Собственно, как нам, есть некий резюме, искать вот эти вот особые точки так, чтобы они были инвариантны к повороту и к изменению масштаба? То есть, нас дано два изображения одной и той же сцены в разном масштабе, и мы хотим найти независимо друг от друга особые точки так, чтобы они были одинаковы в том и другом изображении. Ну и в качестве решения мы должны искать максимальные значения, то есть, точки локальных максимумов, вот некоторых таких функций так, чтобы эти были максимумы в пространстве и в, то есть, по масштабу и по изменению интенсивности. То есть, Space – это изменение интенсивности. Ну, вот здесь придется два таких метода, Харрис-Лапласиан и SIFT. После того, как мы нашли точки. Хорошо, отлично, мы нашли инвариантные точки. Дальше как мы можем, собственно, сопоставить их друг другу? У нас есть набор точек ключевых особых на одной картинке, на второй картинке. Как мы можем сопоставить их друг другу? Нам необходимо каким-то образом для начала вычислить, ну, то есть, построить вот этот вот особый фрагмент вокруг каждой точки таким образом, чтобы он опять же был инвариантен к повороту и инвариантен к изменению масштабов.

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

Соответственно, одним из способов вот такого вычисления, как точек локальных особенностей, так и фрагментов и построения признаков, является алгоритм Сифт (расшифровка по-английски), предложенный Дэвидом Лоуи кажется в 2004-м году. Почему так давно? Он, в общем, является на данный момент такой классикой локальных признаков, поэтому мы сейчас про него будем говорить. Но, с тех пор уже было предложено несколько улучшений его, в том числе. То есть, сегодня я не успею про это рассказать, но, в общем, просто по названиям, есть сифт, который пространство признаков уменьшает за счет применения как раз анализа главных компонент, есть Сёрф, который мы сегодня тоже не успеем рассказать, к сожалению., который тоже чуть более быстр, чем вычисление Сифта. Ну, соответственно, основные шаги алгоритма это то, что мы рассмотрели на предыдущих слайдах. Это выделение вот этих особых точек с использованием разности Гауссиан, то есть, мы выделяем такой вот локальный максимум, как в масштабе, так в изменениях интенсивности. После этого происходит удаление нестабильных точек. Дальше нам нужно понять, выделить каким-то образом фрагмент, особый фрагмент вокруг каждой точки и нужно понять, как он ориентирован. То есть, если у нас одна картинка является повернутой копией второй, мы хотим сонаправить эти фрагменты относительно друг друга так, чтобы потом, когда мы будем вычислять признаки по этим фрагментам, они были сопоставимы. Ну и последний шаг – это вычисление, собственно, самого дескриптора. Здесь еще раз, собственно, что у нас происходит. То есть, мы строим пирамиду масштабов, то есть мы получаем уменьшенные копии разных картинок и их сворачиваем с фильтром Гаусса, вычисляем разницу Гауссиан. Всё то же самое, то есть, у нас есть Гауссианы с разным ядром, и мы строим разность, то есть, у нас с одной стороны есть картинки разного масштаба, разного размера, с другой стороны у нас есть Гауссианы с разным размером ядра. То есть, у нас, мы каждую картинку одного масштаба сворачиваем вот с таким ядром, с таким ядром, вычисляем их разность. Сворачиваем с этим и с этим, вычисляем разность и так далее, что было там раньше. И, плюс к этому, мы это проделываем для каждого из масштабов. Вычисляем, собственно, сворачиваем, вычисляем разницы и вычисляем такие точки, которые являются как бы максимумами для всех масштабов и для регионов изменения интенсивности. Ну, к примеру, для изображений Эйнштейна вот тут эти желтые крестики, они являются точками локального вот этого максимума. Собственно, дальше что нам нужно сделать для того, чтобы попытаться описать некий фрагмент вокруг этой ключевой точки? Дэвид Лоуи предложил следующий вариант. Для начала, как нам сориентировать наш фрагмент? Возьмем, посчитаем градиенты и их размер. Ну, во-первых, как нам определить размер фрагмента и как нам определить его направленность? Возьмем, в каждой вот этой нашей особой точке вычислим ее некоторую окрестность и вычислим, посчитаем градиенты. Соответственно, ну, во-первых, для начала да, просто градиент в самой точке у нас есть некоторое направление, и есть некоторая сила, то есть, как сильно изменяется яркость. Если мы возьмем две разных картинки, то есть, две картинки разного масштаба, к примеру, если вернуться к нашим человечкам, то, к примеру, если у нас ключевой точкой является какая-нибудь вот на голове. То градиент у нас будет направлен, скажем, вот сюда вот, и, причем, величина отклика будет, понятно, соответствовать скорости изменения интенсивности. А скорость изменения интенсивности у нас зависит от масштаба. То есть, для меньшего масштаба она будет изменяться быстрее, то есть, спектр будет, то есть изменение будет короче. Здесь она будет как бы так вот наоборот. То есть, она будет изменяться быстрее, то есть, вектор у нас будет достаточно длинный, у нас изменение интенсивности происходит так: резко. А здесь картинка больше, поэтому градиент в этой точке будет поменьше, сейчас я нарисую. Здесь – побольше. Соответственно, мы можем взять построить фрагмент размером, сопоставимым с величиной градиента, скажем, выделить вот такую штуку, и, если бы у нас эти картинки еще были перевернуты одна относительно другой, мы эти фрагменты можем выровнять по направлению, тоже выровняв направление их градиентов. То есть, соответственно, в качестве вот этого фрагмента, по которому мы хотим посчитать признак, мы выбираем фрагмент, размер которого зависит от размера градиента ключевой точки, и дальше мы его поворачиваем так, у нас есть какая-то нормализация по направлению того самого градиента. И дальше, в качестве признака вычисляется следующая вещь, то есть, мы берем, вот у нас есть огромное количество вот этих точек интереса, вот эти квадратики – это как раз фрагменты особые. Для каждой точки фрагмента, то есть, вот этого квадратика, который я вот здесь вот построила, мы опять же вычисляем градиент. Дальше мы делим картинку на, на самом деле в исходном алгоритме было на четыре части и для каждого… не на четыре, в смысле, а на четыре, потом еще раз на четыре, пополам, пополам и еще раз пополам, пополам, для каждой локальной штуки вычисляем гистограмму градиентов по направлениям. То есть, мы их вот, скажем, в одном углу какие направления градиентов наиболее типичны для там одного угла нашего квадратика, для второго угла, для третьего. И у нас получается вот такое вот описание, то есть, у нас есть отклики по направлениям и, собственно, модуль самого отклика градиента. Это и есть вектор признаков Сифта. Ну, вот здесь еще один пример, собственно, изображение Лены многострадальной, вот здесь рассматривается в качестве особой точки ее глаз, тест на глаз, нормально повернутый, глаз, повернутый на 900. Мы видим, что особую точку мы вычислили с помощью как раз этой разницы Гауссиан. Дальше мы взяли в этой особой точке градиент, посмотрели на его направление и на его величину. Построили окрестность соответствующую, нормализовали по направлению и дальше для каждой точки, то есть мы разбили вот этот вот фрагмент просто пространственно на 16 регионов, в каждом из 16-ти регионов мы построили гистограмму направлений градиентов по, по-моему, восьми направлениям они строили. Ну и, собственно, значение этих гистограмм каждого квадратика, это и есть один большой вектор признаков. Ну и, надо сказать, что-то я сегодня разогналась, в качестве заключения то, что глобальные признаки не всегда работают. Можно вычислять локальные, которые, собственно, работа с ними сводится к тому, что мы определяем некие особые точки. Чаще всего в качестве таких особых точек, ну, на практике получается как бы что бы вы не использовали: или детектор Харриса или разность Гауссиан, это получаются точки, в которых перепад, случается перепад яркости, то есть, там, где у нас неоднородность такая, обычно во многих направлениях. Дальше мы выделяем особые фрагменты, которые должны быть инвариантны к масштабу и к повороту на самом деле тоже, строим вектора признаков. Ну и понятно, что вектор признаков, построенный вот по этому фрагменту, вообще говоря, может быть каким угодно. То есть, мы можем по этому фрагменту посчитать, то есть это дескриптор Сифт оригинальный, мы можем по этому фрагменту посчитать ту же самую гистограмму или всё, что угодно. И дальше мы сопоставляем уже локальные дескрипторы для пары изображений.

Вопрос по поводу размеров области. У нас получается, чем больше изображение, тем меньше его градиент. Чем больше изображение, да, тем меньше его градиент. И тем меньшую область мы берем.
То есть она будет, смотрите, если у вас картинку, ну, опять же вот здесь хороший пример: у нас вот здесь один и тот же глаз: маленький и большой. Соответственно, вот здесь вот у нас изменение яркости отсюда сюда, оно будет происходить быстрее, как бы величина градиента будет больше. Здесь будет изменяться, ну, в некотором случае вроде медленнее, и размер градиента будет, ну, по отношению к размеру всей картинки, меньше. Но, на самом деле, поскольку изображение это одно и то же, то та скорость, с которой мы переходим здесь от черного к светлому, она ровно та же, что и здесь. То есть, у нас здесь будет размер градиента вот такой, здесь – сякой. То есть, если мы… может, пример…

Вот здесь два изображения целиком. Здесь количество, т.е. ключевые точки искались как раз с помощью Сифта и размеры их соответствуют тоже Сифту. Вот здесь вот можно посмотреть. У нас есть пример вот здесь ключевая точка и размер её, и вот здесь ключевая точка и направление градиента. Т.е. в принципе на одну картинку их получается довольно много. Не везде понятно вдоль каких-то изменений тех же облаков они находятся, какие-то точки есть на одном изображении, но их нет на втором. Но поскольку их там вот в среднем там получается 500 тысяч и полторы тысячи в зависимости от того, насколько богата текстура, насколько много изменений яркости на изображении здесь и здесь, то удаётся выбрать такую пару картинок порядка сотни более менее сопоставимых. Так что у нас может быть, что пик горный ровно не отобразиться, но какая-то соседняя точка рядом с пиком – где изменение яркости чуть больше – она может отобразиться. И ещё один комментарий по поводу детектора Хариса. Он на самом деле хорошо работает, особенно вот это выделение угловых особенностей для поиска по изображениям с разными зданиями, где много углов. Его используют часто восстановления трёхмерных сцен по двумерным фотографиям. Т.е. у нас есть две фотографии одной и той же площади, набор фотографий, чтобы по этим фотографиям построить трёхмерную модель нам нужно сопоставить точки на разных фотографиях друг другу. И вот как раз детектор Хариса, который вычисляет эти угловые особенности – он ищет все уголки на этих зданиях, после чего можно сопоставить углы этого здания на одной картинке углам этого же здания на второй и дальше уже построить трёхмерную модель. А если взять какую-то такую хаотичную структуру, то он там в общем будет выдавать за особую точку практически все точки на изображении и это не очень эффективно.

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