Построение признаков и сравнение изображений: глобальные признаки. Лекции от Яндекса

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

Соответственно, зачем может понадобиться описывать картинку в виде такого короткого набора векторов. (Из зала: — Сжатие.). Сжатие – это отдельная тема. Индексация и поиск. Т.е. сравнить изображения друг с другом вместо того, чтобы сравнивать их попиксельно, что не очень удобно, а во-вторых не позволит нам как-то…, т.е. всегда будут какие-то хитрые меры подобия искать, какие-то хитрые метрики для того, чтобы близкие по содержания изображения такие были близкими.

Понятно, что глаз человека не способен различить разницу в одном пикселе. Но, тем не менее, и нам хорошо бы, если мы, допустим, решаем такие задачи как классификация картинок. Если у нас есть какой-то набор меток, к примеру: или это изображения внутреннего помещения – in door – то, что в английской литературе называется, или out door – загородный, или это какой-то пейзаж, закат или всё, что угодно. И мы хотим в одну кучу складывать и одной меткой помечать даже картинки, которые не совпадают полностью, но которые имеют что-то общее друг с дружкой. К примеру, если рассмотреть вот эти вот картинки. (я их попыталась по парам разбить). Понятно, что эти две картинки интуитивно более похожи друг на друга, чем, скажем, вот эти, с трамваями, и вот эта пара тоже более менее похожи, вот эта пара – но у них есть что-то общее. Т.е. если бы мы, к примеру, решали такие задачи как поиск изображений и в качестве запроса у нас бы выступала какая-то картинка или даже набор слов, если бы мы писали в строке поиска, что мы хотим найти изображения с трамваями. Нам необходимо вернуть все картинки, на которых изображен тот или иной вид трамвая и надо каким-то образом сопоставить аннотацию трамваю. Собственно как это можно сделать мы сегодня немного поговорим.

И есть ещё такая отдельная задача, которую иногда обзывают (англ) – имидж парсинг. Она немного похожа на задачу аннотирования, в том смысле, что это тоже приписывание картинке различных тэгов. Но в отличие от аннотирования, если аннотирование ставит перед собой задачу приписывание тэгов, которые описывают изображение в целом. То есть, к примеру, если мы про какую-то картинку говорим, что есть у неё небо, дорога, берег океана, и все эти аннотации приписываются просто этой картинке в целом. То имидж парсинг сочетает в себе распознавание объектов, т.е. мы должны выделить вот здесь вот – это машина, но в тоже время не только описание каких-то объектных вещей, но и можно сказать, что это солнечный день.

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

Во время классификации тоже происходит сравнение изображений, т.е. что такое задача классификации все из вас, надеюсь, знают. В общих чертах у нас есть некое обучающее множество, состоящее из элементов неких образцов про которые нам известны метки, т.е. соотнесение их к каким-то классам. Например, здесь это может быть открытый пейзаж, закрытый пейзаж, городской вид и внутреннее помещение. Это могут быть, не знаю, какие угодно категории. Дальше происходит обучение модели классификатора во время которого, если говорить очень грубо поверхностными словами, происходит сопоставление особенностей изображений внутри каждой группы (ну это не обязательно должны быть изображения, просто сегодня мы говорим о них, а может быть всё, что угодно) особенностей объекта – меткам. Т.е. нам нужно понять какие признаки объекта отвечают за то, чтобы можно было отнести его к тому или иному классу. На выходе получается модель классификатора, такая стадия обучения, которая обычно происходит офф-лайн. Во время тестирования, т.е. когда у нас приходят новые объекты, о которых мы ничего не знаем к какому классу они относятся, и хотим понять это, т.е. чтобы машина за нас решила — как раз происходит сравнение объекта, т.е. сопоставление той модели, которую мы построили и классификатор предсказывает значение. Т.е. на основании тех данных, на основании которых он был обучен, он предсказывает на выходе класс.

Для обнаружения объектов в общем случае нам тоже нужно сравнивать картинки. Правда здесь обычно сравнивается не вся картинка целиком, а только какие-то фрагменты. Обычно это тоже решается с помощью задачи классификации. Т.е. в качестве обучающего множества выступает не всё изображение целиком, а фрагменты, которые изображают тот или иной объект. И дальше задача на изображениях из базы найти фрагмент, в котором есть тот или иной объект. Т.е. нам нужно сравнивать не всю картинку, а некий фрагмент картинки. Обычно в качестве решения задач обнаружения объекта требуется позиционировать на картинке объект определенного класса. Одна из таких наиболее распространённых задач – это к примеру нахождение пешеходов, обнаружение транспортных средств для того, чтобы скажем сделать беспилотный автомобиль.
Аннатирование, как я уже сказала – задача присвоить набор тэгов. Опять же в общем случае это решается через классификатор, т.е. у нас есть некое обучающее множество, у нас есть картинки, к которым уже приписаны тэги. Тэги выступают в роли названия классов. И дальше каждую входящую картинку мы пытаемся классифицировать по одному из этих классов. У нас получается мультиклассовая (многоклассовая) классификация – когда одно изображение может быть отнесено одновременно к нескольким классам, может быть приписано сразу несколько меток.
Как сравнивать картинки?

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

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

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

Сегодня мы будем говорить только про визуальные признаки, а именно про цвет, текстуру и про форму. Их тоже можно разнести. Т.е. можно в нескольких перспективах смотреть на картинку. Можно описывать цвет, текстуру и форму и как это всё расположено в пространстве на картинке и можно описывать целиком всю картинку, т.е. описывать цвет всего изображения. А можно описывать цвет только какого-то фрагмента и текстуру какого-то фрагмента. Вот обычно говорят про глобальные и локальные признаки. Глобальные признаки – те, которые описывают изображение целиком. Локальные – те, которые описывают только какой-то фрагмент.

Для поиска по подобию чаще всего, конечно, используются глобальные признаки или некое, достаточно большое количество локальных, т.е. посчитанных не во всех точках изображения, а в каких-то заранее определённых. Для задачи поиска скажем нечетких дубликатов или поисках по фрагменту считают локальные признаки чаще, потому что пытаются сопоставить именно фрагмент фрагменту, а не всё изображение всему изображению.

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

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

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

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

Начнём мы с цвета. Цвет проще всего описать с помощью гистограммы, т.е. просто посмотреть на распределение по каждому из цветовых каналов. Надо сказать, что цветовые гистограммы до сих пор используются для решения очень большого количества задач, потому что они очень просто считаются, они очень понятны. Они не всегда решают, способны решать очень сложные задачи. Но там, скажем, простейший поиск по подобию, когда у вас изображения, когда база не очень большая, когда изображения отличаются друг от друга по цветовой композиции — она решается. Или когда наоборот база очень большая и у вас есть возможность найти практически копии данной картинке – то тогда тоже поиск по гистограмме в общем будет как-то работать.

Гистограмма как вычисляется, мы с вами уже обсуждали. Дальше для того, чтобы сравнить гистограммы используются очень большой тоже набор метрик. Это или один или тот же эквивалент на самом деле разности гистограмм, т.е. когда мы берём побиново вычитаем — т.е. у нас есть гистограммы представляющая одно изображение, гистограмма, представляющая второе изображение и мы смотрим просто разность этих векторов. Т.е. у нас разности представляются вектором. Это может быть эвклидово расстояние, это можно брать максимум. Можно считать так называемы хи-квадрат или ещё иногда используют так называемый (по-русски даже не знаю как сказать – орс муви дистонс) – это расстояние, в общем, хорошо работает в том случае, если ваша гистограмма построена таким образом, что у вас соседние промежутки соответствуют всегда соседним близким цветам. Но чаще всего на самом деле используют или простое пересечение, т.е. эль один или квадрат, потому, что их проще всего считать. Хи-квадрат тоже конечно используется, но реже. Хи-квадрат – это на самом деле мера сравнения двух распределений, как привести одно распределение к другому, формула там потом будет. Хи-квадрат хорош тем, что является относительной мерой, вычисляет что нужно, грубо говоря, сделать с одним распределением, чтобы привести его к виду второго.(ну если на пальцах).

Ещё одной, не очень прижившейся надо сказать (не знаю почему), способом описания цвета является так называемая статистическая модель, которая предлагает описывать распределение цвета на картинке не с использованием гистограммы, а с использованием различных моментов, т.е. статистических моментов. Если у нас, представляем себе цвет как некое распределение случайной величины и вычисляем мат – ожидания (неразборчиво), дисперсию, момент различной ковариации и моменты высших порядков и дальше строим… Не разборчиво реплика из зала. Ответ — Никак, просто дискретно. У нас есть набор наблюдений, который мы видим в нашем изображении, т.е. получается дискретное распределение.
Соответственно, вектор признаков строится просто как набор вот из этих из разных моментов и в частности в той статье, в которой предлагалось использовать такую модель и в дальнейшем кто если использует, то использовали просто эль один для сравнения векторов.

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

С какими трудностями можно столкнутся при вычислении гистограммы, какие недостатки у гистограммы. Я вам всё говорила, что они такие хорошие. Во-первых нужно понять как … пространство. Не смотря на то, что изображение у нас дискретно, и цвет тоже дискретен в цифровом представлении всё равно, если мы берём обычное полноцветное изображение т.е. 16 миллионов цветов, соответственно в гистограмме 16 миллионов промежутков, это вектор длинной в 16 миллионов. Это не очень удобно. Мало того, что это очень тяжело и нужно большое количество место для того, чтобы хранить эти вектора признаков, их дорого сравнивать. Но помимо этого это ещё и не очень удобно потому, что при таком большом количестве промежутков ни одна из тех простейших мер для сравнения гистограмм она не учитывает подобие цветов в разных промежутках, которые оказались в разных промежутках. Тут встаёт дилемма если у нас есть изначальное цветовое пространство – как его квантовать. Если мы выбираем небольшое количество промежутков, т.е. у нас вектор маленький, это хорошо с точки зрения вычислений, но у нас получается, что расстояние между далёкими цветами маленькое и они попадут в один промежуток. Если наоборот, мы квантуем пространство таким образом, что у нас промежутков очень много, т.е. шаг квантования у нас небольшой то тогда у нас получается некая избыточность в гистограмме и плюс к этому, опять же за счет того, что большинство метрик не позволяет сравнивать между собой подобие именно цветов, то тогда даже близкие по цвету картинки будут отличаться друг от друга достаточно существенно (могут отличаться).

Дело обстоит ещё хуже в том случае, если у нас многомерный признак, ну как к примеру с цветом если мы берём полноцветную картинку у нас обычно три канала – как нам построить гистограмму по всем трём распределениям. Можно строить совместную гистограмму, как здесь у нас для двумерного случая картинка нарисована. По одной оси откладывается значение одного признака. По второй оси – значение второго. К примеру, это может быть значение красного канала, значение синего канала и мы если так уж быть – будет третья ось со значением зеленого. И дальше мы получаем (как на предыдущей картинке) такой вот кубик – разрезанный.

Чем это плохо? Это плохо тем, что, во-первых, у нас очень большое количество промежутков в уже объединённой гистограмме. Т.е. у нас очень большое количество ячеек может быть пустым и тем самым картинки будет сложно сравнить друг с другом.
Можно строить так называемые предельные гистограммы, т.е. отдельно по каждой из переменных, а дальше как-то их комбинировать. Но это тоже не очень удобно, потому, что это предполагает, что у нас признаки независимы, а это не всегда так.

Квантование пространства можно также делать при помощи кластеризации. Если опять же говорить про цвет то здесь мы можем, к примеру, взять некий обучающий набор изображений или даже одну картинку. Построить кластеры по цветам всех пикселей, А дальше объявить центры каждого кластера центрами промежутка гистограммы. И в следующий раз когда к нас приходит картинка для которой мы хотим построить гистограмму мы берём пиксель и смотрим по каждому из признаков к какому из центра кластеров он ближе. И соответственно в тот промежуток гистограммы его и помещаем. Это хорошо тем, что более правильно обрабатывает случай с большей размерностью, чем один. Но требует некой обучающей множества, неких дополнительных вычислений. Но и вообще говоря, никто не гарантировал то, что у нас то множество, по которому мы будем строить эти кластеры – оно достаточно представительно и то, что мы таким образом построим действительно полную картину мира.

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

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

То, соответственно, опять же к вопросу — те проблемы, на которые указывает Джеймс это тоже квантование, говорит про то, что если мы используем такое равномерное квантование (здесь он их обзывает «Grids») — это очень просто, но сложно понять, сложно с этим работать, когда у нас многомерные признаки. И кластеризация – у неё есть свои недостатки, потому, что необходимо понять на основании каких данных мы строим центры наших кластеров. Кластеризация получается несколько сложнее уже во время вычисления гистограммы. Но, тем не менее, это работает намного лучше для многомерных признаков.

Дальше для того, чтобы сравнивать эти самые гистограммы наиболее интуитивно понятный и в первую очередь, применяющиеся методы это как раз эль один и эль два. И они высчитываются достаточно быстро, но в общем хи-квадрат работает намного лучше на некоторых цветовых пространствах. И, как я уже говорила, этот Earth mover's distance, которая если опять же грубо говорить, — если мы представляем гистограмму как некое такое распределение кучек как нам нужно эти кучки потом переместить из одной гистограммы в другую. Т.е. столько нам нужно пикселей подвинуть, чтобы из первой гистограммы получить вторую. «Earth mover» если переводить дословно – это движение земли, передвижение грязи.

Если наша метрика никак не учитывает подобие цветов, т.е. это всё то, что было перечислено выше, кроме Earth mover, то тогда, к примеру, вот здесь мы получим что расстояние между первой гистограммой и второй оно будет больше чем расстояние между первой гистограммой и третьей. Хотя визуально, скорее всего, будет казаться, что картинка, по которой построилась первая гистограмма и картинка по которой построилась вторая – они ближе друг к другу, чем первая и третья. Тут у нас чуть съехал оттенок. Но тем не менее они вот так вот все распределены. Тут просто всё в красно-жёлтом диапазоне.

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

Дальше ещё один недостаток цветовой гистограммы это то, что она никак не учитывает пространственное расположение цветов. К примеру, вот для этих трёх изображений гистограмма будет абсолютно одна и та же, потому, что количество чёрного и количество белого на этих картинках одинаково. Хотя зрительно они воспринимаются несколько разными. И ещё один более наглядный пример. Гистограммы этих изображений они тоже абсолютно одинаково посчитаны. Хотя мы наверно не скажем, что эта картинка похожа на эту.
Что с эти можно делать. Наивная идея это пытаться разбивать изображение на фиксированные блоки.т.е. у нас есть одна картинка. Мы её делим попалам и попалам и можно строить целую пирамиду этих самых блоков и считать отдельно гистограммы для каждого из этих блоков. И учитывать соответственно какое распределение цветов у нас в каждом из блоков.

Еще одна идея близкая к этой это использовать так называемые нечёткие области. Т.е. вот здесь вот то, что они выглядят таким вот образом не принципиально. Принципиально то, что нет чётких границ между этими обрастями. Т.е. есть некая функция, которая задаёт степень принадлежности пикселя каждой из этих областей, которая близка к единице если пиксель далёк от границы с соседом, и близка к нулю, если он где-то на границе, т.е. к соседней. Т.е. пиксели, которые находится на границе двух областей они будут пополам принадлежать. У них будет 0,5 принадлежность к R1, и 0,5 к R0 и т.д. те которые в центре, они, скажем, у них принадлежность к R0 – единичка. За счет задания нечетких границ — это позволяет более гибко реагировать на небольшие смещения этих цветовых пятен по картинке. Эти нечеткие области были предложены теми же самыми авторами, которые предложили статистическую модель описания цвета. По их экспериментам это работает неплохо. Но почему-то дальше это никто не использовал. Собственно мои собственные эксперименты не показали такого уж большого превосходства этих статистических моделей над гистограммами.

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

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

A и C не различаться, в уже немножко отъедет, потому, что центр будет смещён у черного и у белого по сравнению с … ну это такой несколько вырожденный пример. На самом деле да, эта штука она не работает в том случае, если у нас есть два цветовых пятна одного и того же цвета на картинке. Если у нас тут было бы синее озеро такого же цвета как небо, то тогда бы центр массы оказался где-то посередине, что не очень соответствует. ну т.е. центр массы действительно посередине, но это не совсем верное представление даёт о реальном пространственном расположении цветов. Несколько центров, да, можно делать, но вот в этой работе это не делалось. Можно. Но это уже тогда будет, т.е. надо будет делвть какую-то сегментацию, про что я говорила раньше, что дорого.

Функция подобия, которая учитывает эти координаты тоже была предложена достаточно простая. Она состоит их двух множителей. Это дистанция по гистограмме – это простое пересечение гистограмм – эль один. Второй множитель это эвклидово расстояние между центрами масс. Ну тут какие-то коэффициенты.

По результатам экспериментов получается что это гистограмма, которая учитывает пространственное расположение цветов вместе с соответствующей ей функцией подобия – она в общем практически всё время для любого квантования выигрывает у классических гистограмм с манхэттенской метрикой, то что эль один. Т.е. здесь на графике показана разность в точности. Т.е. эксперимент проводился на задаче поиск изображений. Мы подаём картинку – запрос в систему. Система возвращает картинки подобные на запрос. И мы смотрим сколько действительно похожиъ оказалось среди первых результатов выдачи. И вычитаем то, сколько реально подобных оказалось при поиске с использованием этой гистрограммы с пространственным расположением цветов и сколько подобных оказалось при поиске по обычной гистограмме. Число получается всегда положительным. При чем результат вот тут выше на достаточно существенный показатель – двадцать, двадцать пять процентов. А здесь по оси – это количество промежутков гистограммы, т.е. насколько подробрый был вектор признака. И видим, что чем меньше размер вектора, тем больше выигрыш. Что в общем то хорошо, потому, что это означает, что с использованием вот этой вот штуки мы можем записать информацию о картинке, которая будет решать задачу примерно с тем же качеством в меньший вектор признаков.

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

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

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

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

И есть ещё геометрические диаграммы Баранова, которые пытаются описать текстуру через (неразборчиво) треангуляции и какие-то структурные, когда описываются, просто задаются некие структурные шаблоны (ярко, ярче и ещё ярче) и вот ищутся по всей картинке такие вот шаблоны.

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

Дальше получив такие матрицы смежности можно по ним считать различные характеристики. Но таких матриц обычно строят не одну, а по крайней мере по четырём направлениям — верх, низ, право, лево. Иногда диагональные и ещё может быть разным шаг сдвига.

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

Если матрица смежности – это попытка анализировать текстуру с математической точки зрения, (т.е. мы смотрим на функцию и пытаемся понять, как можно её описать) то признаки Тамура – это попытка пойти с другой стороны. Они проводили (Тамура и его группа) очень масштабное исследование — они опрашивали людей, просили их описать разными словами разные наборы текстур и пытались определить какие слова являются отличительными для той или иной текстуры. Выяснилось, что это шесть свойств: зернистость, контрастность, направленность, линейность, регулярность, грубость. А после этого они пытались их каким-то образом смоделировать с помощью численных вычислений и дальше опять же попытаться понять какие из этих значений лучше всего представляют текстуру. Т.е. изначально у них было шесть вот таких направлений, которые каким-то образом вычислялись, дальше они считали, в общем строили что-то вроде фич селекшн, т.е. пытались выбрать из них наиболее независимые, наиболее информативные с математической точки зрения. Получилось что это вот эти вот первые три и дальше тогда вот признаками Тамура обычно считается так называемое изображение Тамуры, поскольку всего три значения получается и оно вычисляется для каждого пикселя по окрестностям этого пикселя. Т.е. у нас получается для исходной картинки некая картинка Тамуры которая опять же трёхмерная, как цветное изображение. А значением является значение каждой из этих характеристик. И дальше можно строить картинки строя опять же гистограммы или статистические моменты., т.е. точно таким же образом, каким мы описывали цвет. Формула, по которым все вот это вычисляется можно найти в статьях. Здесь я их приводить не буду. Про признаки я уже сказала.

Наиболее наверно используемыми на сегодня признаками, которые описывают текстуру являются фильтры Габора. И ещё один набор фильтров, построенных на основе анализа независимых компонент, он не очень используется пока что, но предложен был довольно недавно — мне кажется, что у них есть будущее.

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

Вейвлет-преобразование отличается от фурье-преобразования в основном тем, что — набором базисных функций по которым происходит разложение. И там и там мы пытаемся представить исходную функцию в виде разложения по некоторому базису. Т.е. у нас есть некий набор заранее заданных функций в виде линейной комбинации в которых мы хотим представить исходную. Отличие от фурье-преобразования в том, что фурье-преобразование вот этот базис, эти гармонические функции — т.е. у них период всё время одинаковый. И они, если мы рассматриваем одномерный сигнал (обычно аналогия ближайшая – это аудио сигнал0 – т.е. это как изменяется звук по времени. т.е. у нас есть некое значение и время. То в гармонических функциях они не зависят от времени, т.е. она – вот этот базис, он все время одинаковый. Вейвлет базис и Вейвлет- функция они отличаются тем, что задаются небольшими волнами у которых во-первых может меняться частота, во-вторых, самое главное, у них меняется…, т.е. они могут затухать, они не нулевые на каком-то промежутке. Т.е. если мы попытаемся… вот здесь наверно…это не совсем вейвлеты, я про это расскажу.

Если мы представим что у нас одна из базисных функций она выглядит вот таким вот образом. в том случае, если бы это была бы гармоническая функция – она бы дальше все время вот так и продолжалась бы. Мы пытались наш изначальный сигнал представить в качестве, в виде разложения вот с таких возможно бесконечного набора гармоник, которые не затухают. Вейвлеты характеризуются тем, что у них каждая базисная функция она затухает, т.е. у неё есть какой-то промежуток (ну принято говорить — по времени. если опять же аналог к одномерному случаю звукового сигнала) когда она не нулевая, а дальше она — ноль. И ещё отличительной особенностью вейвлетов считается, является то, что на самом деле они все порождаются, ну т.е. эти базисные функции, они порождаются одна из другой. У нас есть некий базовый вейвлет, все остальные получаются путём растяжения и масштабирования первого.

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

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

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

На самом деле все эти базисные функции они потом задаются в приложении к изображению в виде так называемых банков фильтров. Т.е. каждая базисная функция – это тоже двумерная функция, которую можно представить в виде картинки. И посчитав свёртку с этим фильтром вы получите отклик исходной картинки на фильтр – т.е. насколько она соответствует, насколько она похожа. Но с вейвлетами тут ещё фокус в том, что изначально, т.е. мы можем пытаться представить наше исходное изображение — исходный аудио сигнал (здесь одномерная функция, одномерный случай) в виде суммы большого количества вот этих вот сдвинутых, растянутых базисных функций с какими-то коэффициентами.
Но на самом деле пространство, которое получается путём натяжения на набор вот этих вот базисов… т.е. мы берём сначала одну базисную функцию. Понятно, что есть какой-то набор функций, который можно разложить по этому базису. Т.е. там два умножить на неё, три умножить, т.е. какие-то коэффициенты. Допустим что это множество всех таких функций – это вот этот вот самый V0. Т.е. всё пространство функции, которое может быть представлено с помощью линейной комбинации из одной единственной базисной функции.

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

Дальше у нас появилась вторая базисная функция и набор функций, который можно представить в виде двух базисных функций – он расширился, он такой вот. Он включает в себя предыдущую пространство. Но мы можем представить такой набор, ещё третий набор базисных функций, который на самом деле будет задавать вот это вот пространство функции, куда не входит ви ноль, а входит ви один как бы без ви ноль. И как раз вот это вот и называется вейвлетами. Они тоже будут, они строиться будут дальше тоже по такому же правилу, они являются растяжимыми и масштабируемыми. А дальше получается, что мы можем задать каждое последующее… чем больше мы расширяем, чем больше мы добавляем вот этих базисных функций исходных, тем больший набор функций, чем шире вот это пространство, тем больший набор функций мы можем описать.

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

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

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

Допустим у нас есть некое пространство функция которого задаётся вот таким вот базисом. Т.е. это может быть… ну т.е. различные функции, которые могут быть получены растяжением, сужением или перемножением и соответственно сменой знака, т.е. различные варианты, типа не знаю вот такой. Или вот такой. Или какой угодно. Т.е. функции вот такого вида они могут быть представлены как некий коэффициент умноженный вот на такую функцию.

Дальше если мы берём следующую функцию, масштабирующую функцию Хаара, т.е. мы её сужаем, мы берём вот такой. Это будет следующий базис. Всё пространство функции, которое может быть представлено с помощью вот такого базиса обозначим за вэ ноль. Всё пространство функции, которое может быть представлено набором вот из двух таких базисных функций – это ви один. Так вот получается, что для того, чтобы перейти из ви ноль в ви один нам нужно добавить, т.е. вместо вот этого мы можем добавить вот один вот такой и таким образом т.е. вот это вот будет как раз вот этот вот ви ноль. Т.е. если у нас был вот это вот, то вот это вот ви ноль.
Т.е. все те функции, которые входят в… которые могут быть представлены как линейная комбинация вот этих двух (V0 и V1), но не могут быть представлены как линейная комбинация вот этого (V0) – могут быть представлены как линейная комбинация вот этого вот одного (W0).

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

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

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

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

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

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

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

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

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

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

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

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

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

Какие могут быть требования к признакам формы. Понятно хочется чтобы он был во-первых инвариантен параллельному переносу. Если у нас на одной картинке тигр скачет в левом нижнем углу, а на второй картинке в правом верхнем, ну все-таки хотим понять, что и там и там это был тигр. Инвариантность к изменению масштаба, чтобы признаки, которые были построены по одному и тому же объекту в разном масштабе совпадали. Инвариантность к повороту, чтобы признаки, построенные по объекту повернутому под разными углами тоже совпадали. Устойчивость к незначительным изменениям. Хорошо бы, чтобы это было просто вычислимо и просто сравнимо, но как показывает практика достаточно хорошо описывающих содержание признаков – это сложно. Обычно первые четыре конфликтуют со вторыми.

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

Начнем с самых приятных цепных кодов простых, которые тоже были предложены как все простое раньше всех. Они строятся по следующему принципу. К примеру, у нас есть некий контур выделенный. И мы хотим придумать как нам описать этот контур таки образом, чтобы если мы обнаружим на другой картинке такой же контур, но повернутый, перенесенный или сжатый – код, который описывает этот контур вектор признака был бы точно одинаковый в обоих случаях. Для начала выбираем количество направлений, т.е. их может быть, они могут быть четырехсвязные и восьмисвязные цепные коды. Сейчас будем смотреть на восьмисвязные. Здесь собственно пример четырехсвязного, когда мы можем ходить только влево, вправо, вверх, вниз. А на этой картинке пример восьмисвязного, в котором мы можем ходить еще по диагонали.

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

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

Дальше как мы можем получить инвариантность к повороту. Давайте считать не номера, выписывать сюда не номера собственно направлений, а разность соседей. Т.е. у нас вот был уже изначальный инвариантный к начальной точке. А дальше мы его преобразуем таким образом, что мы вычитаем из последующего номера предыдущий. Ну с по модулю семь. Ноль минус ноль это будет ноль. Один минус ноль это будет один. Шесть минус один это будет пять. Шесть минус шесть – ноль. Шесть минус шесть – ноль. Тут дальше пять минус шесть по модулю семь будет семь. Ну и так далее. Таким образом, мы получаем инвариантность к повороту.

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

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

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

Дальше для того, чтобы отнормировать (часто довольно используют не коэффициент Фурье в чистом виде, а нормализованные коэффициенты Фурье – они позволяют нам сделать этот признак инвариантным относительно масштаба). Потому, что, вообще говоря, первый коэффициент Фурье – это среднее значение функции обычно. Т.е. соответственно в таком случае у нас если была бы рожица больше, среднее значение было больше, если мы делим на нулевой, на первый коэффициент Фурье – на нулевой, таким образом, мы делаем представление инвариантным, относительно размера.

Ну и в силу на самом деле свойств фурье-преобразования он является инвариантным относительно поворота. Ну а дальше сравнение, просто сравниваем соответственно два вектора которые являются коэффициентами Фурье.
Дальше как можно описывать собственно всю область целиком. Опять же очень такой наглядный метод простой так называемый Грид-метод. Снова накладываем сетку на нашу область. А теперь записываем нолики, вектор нолики и единички, в зависимости от того пересекает наша область клеточку или нет. Т.е. у нас наборы клеточек в зэд порядке. Соответственно первые две ячейки мы не пересекаем – тут нолики. Третью и четвертую пересекаем – будут единички. И дальше тоже пересекаем пятую и шестую — тоже единички. Дальше не пересекаем – нолики и т.д. Получается такой длинный длинный вектор из нулей и единичек. Для того, чтобы добиться инвариантности, то мы нормализуем по главной оси. Таким образом добиваемся относительно и поворота и масштаба.

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

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