Содержание к диссертации
Введение
1 Анализ существующих методов структурного анализа изображений 16
1.1 Структурные методы, абстрагирующиеся от индивидуальных особенностей зрительных образов 18
1.1.1 Методы, основанные на контурном описании изображения 19
1.1.2 Методы, основанные на локальных признаках 23
1.1.3 Способы учета геометрического положения структурных элементов в
пространстве изображения 26
1.2 Построение структурного описания путем обучения 33
1.3 Выводы 39
2 Сопоставление изображений трехмерных сцен с использованием кластерного анализа 42
2.1 Кластеризация параметров сопоставлений ключевых точек 42
2.1.1 Обнаружение объектов 43
2.1.2 Сопоставление произвольных трёхмерных сцен 44
2.1.3 Вероятность образования кластера ключевых точек 46
2.2 Верификация кластерной гипотезы 50
2.2.1 Метод наименьших квадратов 51
2.2.2 Алгоритм RANSAC 62
2.3 Предварительная обработка сопоставлений 72
3 Поиск изображений трехмерных сцен в базе данных с использованием концепции визуальных слов и кластерного анализа 83
3.1 Применение визуальных слов с использованием структурной информации 83
3.2 Составление словаря визуальных слов 87
3.3 Организация процедуры кластеризации с помощью преобразования Хафа 90
3.4 Выводы 94
4 Практические результаты 96
4.1 Общие особенности практической реализации 96
4.2 Сопоставление изображений трехмерных сцен 101
4.3 Поиск изображений трехмерных сцен в базе данных с использованием гистограмм визуальных слов 112
4.4 Использование структурных методов для улучшения плотных карт глубины 115
4.4.1 Автоматическая оценка диапазона диспаратностей 118
4.4.2 Изменение матрицы корреляционной энергии 119
4.4.3 Результаты 121
4.4.4 Выводы 127
4.5 Сопоставление аэрокосмических снимков 128
Заключение 138
Литература 140
- Методы, основанные на локальных признаках
- Сопоставление произвольных трёхмерных сцен
- Составление словаря визуальных слов
- Поиск изображений трехмерных сцен в базе данных с использованием гистограмм визуальных слов
Методы, основанные на локальных признаках
Объектом исследования в данной диссертационной работе являются методы автоматического СА изображений трехмерных сцен. В настоящее время алгоритмы обработки изображений принято связывать с разными уровнями описания изображений. Рассмотрение изображений на более высоких уровнях описания позволяет абстрагироваться от особенностей изображения, не несущих важную для анализа информацию. В настоящее время принято говорить о системном взаимодействии следующих иерархических уровней описания [1]:
Переход от нижних уровней представления к верхним сопровождается неизбежной потерей информации, поэтому переход от одного уровня описания изображения к другому должен происходить так, чтобы сохранять максимально большое соотношение полезной и бесполезной информации. При этом полезной информации должно быть достаточно для принятия правильного решения.
Различия в представлении изображения на пиксельном уровне, как правило, сводятся к различиям формата представления изображения, связанным с аппаратными особенностями фотокамеры. Признаковый уровень основан на признаках, содержащихся в нескольких (иногда в одном) пикселях. Признаки выражают некоторую значимую характеристику объекта численно.
Уровень СЭ позволяет частично абстрагироваться от данных исходного изображения. СЭ могут строиться на основе контуров, или точек интереса, которые выделяют в рамках признакового подхода. На уровне составных СЭ выявляются связи между отдельными СЭ, что позволяет получить абстракцию еще более высокого уровня. В литературе структурными методами называют методы, которые работают со структурным описанием изображений и методы, которые учитывают связи между отдельными элементами изображения. Таким образом, при использовании сочетания «структурный метод» [2–7], как правило, имеют ввиду, что при анализе изображения в расчет принимается взаимное пространственное положение отдельных частей изображения, его СЭ, т.е. анализируются структурные связи.
На уровне знаний изображение интерпретируется в терминах естественного языка, а при использовании иерархического описания методы оперируют с описаниями разных уровней за счет использования обратных связей.
Привлечение знаний о предметной области может производиться автоматически посредством обучения, но часто в используемых на практике системах автоматического анализа изображений информацию о предметной области и предполагаемых свойствах изображения, закладывают в систему вручную. Это позволяет добиться лучших результатов для конкретных задач, но приводит к тому, что системы становятся узкоспециализированными, не применимыми к другим задачам компьютерного зрения. Использование структурного представления позволяет существенно повысить качество работы таких алгоритмов. Так, например, в задаче обнаружения лица можно использовать простой детектор цвета кожи [8, 9], однако, существенного улучшения работы алгоритма можно добиться, если анализировать форму выделенной области искомого цвета [10] или дополнительно производить оценку положения носа и глаз в области с цветом кожи [11, 12]. Использование по-настоящему универсальных методов СА позволяет увеличить эффективность работы алгоритмов в условиях малой предсказуемости содержания изображений. В создании как можно более универсальных методов заинтересованы также разработчики вычислительной аппаратуры, поскольку, чем более широкий круг задач способен решать алгоритм, тем больше серия чипа, реализующего этот алгоритм, что в свою очередь существенно влияет на конечную стоимость разрабатываемого прибора (приборов). Все приведенные выше факторы стимулируют исследования объектно-независимых методов в области технического зрения. В последние годы исследователям удалось добиться прогресса в создании подобных методов, из-за чего при решении практических задач такие методы часто выбираются в качестве «основы», которая дополняется эвристиками характерными для области применения.
В настоящее время можно выделить два подхода к построению объектно-независимых методов анализа изображений: такие методы либо абстрагируются от особенностей анализируемых зрительных образов и для построения структурных описаний используют лишь самые общие закономерности их формирования, либо получают знания об особенностях зрительных образов автоматически посредством обучения на маркированной БД. Для построения систем устойчивых к различного рода искажениям учитывается положение отдельных элементов изображения, поэтому оба вида методов можно считать структурными.
Сопоставление произвольных трёхмерных сцен
По сравнению с методами, основанными на кластеризации в пространстве параметров отдельных СЭ или КТ, одним из видимых преимуществ метода обнаружения кластеров сопоставленных локальных признаков, предложенного Лове [40] для обнаружения объектов на сцене, является то, что учитывается ориентация и размер участка, на котором построен дескриптор КТ, в то время как большинство других методов эту информацию игнорируют и рассматривают сопоставляемые элементы изображения как безразмерные точки в пространстве изображения. В литературе, тем не менее, этому методу уделено намного меньшее внимание, чем алгоритмам, отвечающим за обнаружение КТ и построение дескрипторов SIFT. Об этом в частности свидетельствует то, что в существующих открытых реализациях алгоритма SIFT [146, 147] отсутствуют модули, отвечающие за проведение кластерного анализа сопоставлений. Одна из причин этого может заключаться в том, что подход предложен Лове для сопоставления изображений объектов [40], а не для сопоставления произвольных сцен. В данной работе показывается, что подход [40], основанный на кластеризации сопоставленных локальных признаков, применим к распознаванию трехмерных сцен [148]. Далее приводится краткое описание подхода и интерпретация его для изображений произвольных трёхмерных сцен.
В дальнейшем тексте под сочетанием слов «размер КТ» следует понимать уникально подобранный размер участка для расчета дескриптора КТ, а под сочетанием слов «ориентация КТ» – ориентацию дескриптора КТ. Такие термины является не вполне корректными, поскольку точка является безразмерным объектом, но поскольку для каждой КТ рассчитывается дескриптор, то эти термины в ходе дальнейшего изложения иногда будут использоваться для краткости.
Обнаружение объектов Д. Лове рассматривает задачу обнаружения объектов на произвольном изображении. В этом случае в качестве модели выступает изображение объекта на тёмном фоне, требуется определить положение модели на тестовом изображении.
Сопоставление дескрипторов в пространстве признаков дает исходный набор сопоставлений. Как уже было сказано, в нем содержится большое количество ошибок, некоторое количество которых удается удалить за счет проведения предварительной обработки, которая будет описана в следующих разделах. Удаление оставшихся ошибок достигается за счёт кластеризации локальных ПГП, задаваемых сопоставленными КТ. Такая кластеризация возможна, поскольку каждая из сопоставленных КТ имеет положение, размер и ориентацию, а параметры взаимного масштаба, разворота и смещения задают уникальное ПГП. Кластеризация осуществляется путем проведения преобразования Хафа, – каждое сопоставление увеличивает счетчик определенной ячейки аккумулятора Хафа. Аккумулятор имеет четыре измерения, соответствующих углу разворота модели, изменению масштаба и положению модели на плоскости (по оси X и Y). Поскольку изображение объекта может быть подвергнуто более сложным преобразованиям чем ПГП (например, аффинному преобразованию), то допускаются значительные отклонения от него. Это достигается за счет использования больших ячеек аккумулятора. Размер ячейки аккумулятора – 30 градусов для угла поворота, 0.25 максимального разрешения для положения модели и степень 2 для масштаба. Для предотвращения граничного эффекта каждое из сопоставлений дополнительно увеличивает счетчики ячеек аккумулятора Хафа, ближайших к ячейке, описывающей параметры ПГП сопоставления.
После проведения преобразования Хафа рассматриваются только те сопоставления, которые попали в ячейки аккумулятора с достаточным количеством голосов и, таким образом, большая часть ошибок удаляется после этого шага.
Сопоставление произвольных трёхмерных сцен можно приравнять к сопоставлению многих объектов эталонного изображения со многими объектами тестового изображения. Разные объекты могут образовывать разные кластеры в пространстве ПГП. Отметим, что в таком случае возможны ошибки, когда на паре изображений присутствует несколько одинаковых объектов. Эти ошибки могут быть удалены с помощью проведения дополнительных проверок каким-либо дополнительным методом, например, с помощью учета глобальной геометрии сцены [105].
Поскольку одним из измерений в пространстве Хафа является положение модели, то необходимо пояснить, что является положением модели (или «опорной точкой») в случае трёхмерных сцен. При решении задачи обнаружения объектов существует так называемое модельное изображение (model image) – изображение, на котором изображен только объект. В случае если форма объекта не сложна, то для каждой пары сопоставленных изображений должен быть найден только один кластер ключевых точек, - поверхность объекта произвольной формы аппроксимируется плоскостью, от которой допускаются значительные отклонения. В экспериментах Лове в качестве эталонов использовал снимки объектов на чёрном фоне, в которых объект располагался по центру. В этом случае, очевидно, положению объекта на изображении соответствует центр модельного изображения.
Поскольку при кластеризации важно, чтобы сопоставления, относящиеся к одному и тому же объекту, были отнесены к одной и той же ячейке аккумулятора, а конкретное положение объекта не важно, то в случае трехмерных сцен можно предположить, что каждый объект занимает все изображение и его центру соответствует центр изображения.
Составление словаря визуальных слов
Одной из важных задач компьютерного зрения является поиск изображений в БД, когда одно или несколько эталонных изображений используют в качестве запроса, по которому в БД требуется найти изображения, схожие с эталонными в некоторых аспектах, например, изображения той же местности. При организации поиска с помощью автоматического анализа содержимого изображений [117] большую роль играет время сравнения описаний, извлеченных из изображений, поскольку в БД, как правило, хранят не сами изображения, а описания, извлеченные из этих изображений. В процессе распознавания извлекать описание нужно только из эталонных изображений, производить сопоставление же, как правило, приходится для каждого из изображений БД.
Одним из известных вычислительно эффективных способов поиска изображений в больших БД являются алгоритмы, использующие концепцию визуальных слов.
Алгоритмы распознавания и категоризации изображений, использующие визуальные слова в последние годы обретают все большую популярность. Этот подход был позаимствован из алгоритмов анализа текста – дескриптор каждой КТ рассматривается как аналог слова в тексте.
Для получения словаря визуальных слов используют все дескрипторы, извлеченные из изображений БД – в многомерном пространстве признаков (дескрипторов) выполняется поиск кластеров с помощью алгоритма К-средних. После этого каждый дескриптор, извлеченный из тестового изображения, относится к определенному визуальному слову за счет сравнения дескриптора с центрами полученных кластеров. После этого формируют гистограмму визуальных слов, которую используют для описания изображений.
В классической концепции визуальных слов сопоставление изображений осуществляется без учёта взаимного положения визуальных слов на изображении, что позволяет системе быть устойчивой к ракурсным искажениям. В связи с этим возможно применение таких методов к сопоставлению изображений трёхмерных сцен. С другой стороны отсутствие структурной информации существенно снижает дискриминационные способности метода, поскольку, как уже отмечалось выше, учет взаимного расположения элементов изображения является более важным при распознавании изображения, чем содержимое элементов изображения. Именно важность структурной информации является самым главным отличием анализа изображений от анализа текста, хотя имеются и другие отличия (такие как наличие значительного шума в визуальных словах) [7].
В связи со сказанным выше, в последние годы большие усилия исследователей направлены на дополнение алгоритмов, использующих концепцию визуальных слов, информацией о взаимном расположении визуальных слов. В [127] авторы учитывают взаимное расположение визуальных слов, расположенных близко друг к другу. В [128] по визуальным словам изображения строится граф. В [129] мешки визуальных слов обогащаются с помощью привлечения соотношения часть-целое – привлекается информация о том, что одни дескрипторы посчитаны на участке изображения, использованного для расчета другого «более крупного» дескриптора.
Во многих работах структурная информация извлекается посредством обучения на серии эталонных снимков. В этом случае, как правило, детектор КТ не используют – КТ равномерно распределяются по всей площади изображений и располагаются в узлах сетки ортогональных линий, следующих с одинаковым шагом [152, 153]. В [7] и [126] в качестве эталона выступает единственное изображение, детектор КТ используется для того, чтобы снизить количество визуальных слов, по которым принимается решение. Учет взаимного положения сопоставленных признаков выполняется только среди N лучших изображений-кандидатов, полученных с помощью непосредственного сопоставления ГВС. «Структурная верификация» двух «похожих» ГВС осуществляется за счет генерации набора сопоставлений КТ и учета их пространственного положения. Для этого дополнительно к ГВС сохраняется информация о параметрах КТ, попавших в ячейки гистограммы. После этого, ячейки гистограмм, соответствующие друг другу можно интерпретировать как сопоставления групп ключевых точек двух изображений. Программа в [7] организована так, чтобы одна ячейка ГВС не давала больше одного сопоставления – если на двух изображениях больше чем по одному визуальному слову определенного типа, то среди всех дескрипторов соответствующих этому слову выполняется поиск ближайших соседей, чтобы сформировать одну наиболее достоверную гипотезу сопоставления. После генерации сопоставлений с помощью RANSAC осуществляется подбор параметров плоской модели в частном аффинном пространстве (без учета ориентации).
В рамках данной диссертационной работы предлагается модифицировать алгоритмы [7] для распознавания трехмерных сцен, используя для учета структурной информации алгоритмы кластерного анализа из главы 2 [148]. Заметим, что отказ от ориентации является часто используемым приемом, поскольку обеспечивает значительное повышение эффективности распознавания объектов и сцен в характерных положениях. В настоящей работе ориентация сцены полагалась априорно неизвестной, но распознавание сцен с учетом характерных ориентаций может быть осуществлено за счет несложных модификаций предложенных алгоритмов. В силу тривиальности подобных модификаций в данной диссертационной работе подробно они не рассматриваются. Чтобы не хранить дескрипторы эталонных изображений, предлагается отказаться от уточнения лучших гипотез сопоставления КТ путем сравнения дескрипторов КТ, когда количество КТ в ячейках гистограммы больше одного. В этом случае, правда, придется мириться с тем, что по одной ячейке гистограммы будет генерироваться mn сопоставлений, где m и n – количество КТ в соответствующих ячейках двух гистограмм (рисунок 12).
Поиск изображений трехмерных сцен в базе данных с использованием гистограмм визуальных слов
В третьей главе был предложен способ учета структурной информации в алгоритмах поиска изображений в БД с использованием ГВС. По двум сопоставленным ГВС предлагается генерировать сопоставления КТ и проводить дополнительный анализ параметров сопоставленных КТ.
В ходе экспериментов рассматривались словари, состоящие из 1000 и 2000 визуальных слов. Лучшие результаты были получены при использовании большего словаря и все результаты приводятся для словарей такого размера. В таблице 2 приведены результаты применения алгоритмов кластерного анализа к сопоставлениям, сгенерированным по ГВС, в задаче сопоставления изображений (BoW(SURF)). В этом случае по сравнению с анализом сопоставлений, полученных путем сравнения дескрипторов двух изображений в пространстве признаков, было найдено меньшее количество локальных соответствий и поэтому сопоставлено меньшее количество изображений (273 вместо 309), но при этом достоверность полученных локальных сопоставлений выше (11.6% ошибок вместо 17%), что позволяет говорить о том, что снижается вероятность «ложной тревоги». Таким образом, даже несмотря на уменьшение количества сопоставленных изображений, можно говорить о том, что передоложенный алгоритм позволяет получать корректные результаты и может быть использован, по крайней мере, в задачах, в которых критично время и объем занимаемой памяти. Кроме того, существует потенциал для развития метода за счет использования более изощренных способов получения словаря визуальных слов, например, путем выявления слов нестабильных к ракурсным искажениям с последующим исключением этих слов при проведении СА. Выявить нестабильные визуальные слова можно, например, проанализировав вручную промаркированные сопоставления (см. раздел 2.3). Однако данные исследования выходят за рамки данной диссертационной работы.
Для того чтобы продемонстрировать возможность сочетания алгоритмов, использующих ГВС, с алгоритмами СА при работе с БД изображений была составлена БД изображений трехмерных сцен состоящая из 300 изображений размером 640480. По базе данных был осуществлен поиск 44 изображений, корректность обработки запросов оценена вручную.
Для непосредственного сравнения двух ГВС использовались не непосредственно гистограммы, а мера TF.IDF [160], учитывающая «важность» слова в изображении, а также частоту появления этих слов в других изображениях: где/у- частота (количество появлений) слова/в изображении;, щ - количество изображений, содержащих слово /. Поскольку TF.IDF является вектором, то для сравнения этих векторов использовался коэффициент корреляции Пирсона, который показал лучшие результаты по сравнению с использованием расстояния в евклидовом пространстве между двумя полученными векторами.
Из изображений БД были извлечены описания - гистограммы визуальных слов, параметры КТ и индексы их визуальных слов. В таблице 3 приведены результаты поиска 44 тестовых изображений в БД с использованием ГВС совместно с предлагаемыми методами СА (BoW+SA) и с использованием только ГВС (BoW). В таблице приведены результаты при структурной верификации одного и двадцати изображений ближайших к тестовому с точки зрения меры TF.IDF.
Предложенные в главе 3 способы уменьшения количества анализируемых кластерных гипотез путем частичного игнорирования граничного эффекта, позволили добиться существенного снижения временных затрат – для генерации сопоставлений по ГВС и проведения кластерного анализа сопоставлений одного изображения на персональном компьютере требуется в среднем 3 мс. Для сравнения, даже без учета времени, требующегося для учета геометрии трехмерной сцены, для получения набора сопоставлений за счет сравнения BRISK дескрипторов в пространстве признаков требуется в среднем 10 мс. Здесь необходимо отметить, что если объединить дескрипторы всех изображений в одну БД и использовать алгоритмы поиска приближенно ближайших соседей [80], то количество необходимых операций при поиске изображения можно сократить, но это, во-первых, ведет к неполноценным результатам сопоставления, а, во-вторых, учет геометрии сцены все равно придется проводить для каждой пары изображений в отдельности.
Без учета времени требующегося для обнаружения и описания КТ на тестовом изображении поиск в БД из 300 изображений с помощью ГВС занимает около 30 мс. Таким образом, при учете структурных связей на одном изображении общее время поиска составляет в среднем 33 мс, а при учете структурных связей на 20 изображениях – 90 мс.
Выводы. В данной диссертационной работе был предложен способ учета геометрии трехмерных сцен в алгоритмах поиска изображений в БД при использовании ГВС. Предлагается проведение дополнительного структурного анализа сгенерированных сопоставлений. Эксперименты показывают, что при поиске изображений трехмерных сцен в использованной БД проведение дополнительного СА параметров сопоставлений для одного изображения-кандидата обеспечивает уменьшение количества ошибок первого рода более чем в 20 раз за счет увеличения количества ошибок второго рода лишь на 4,5%. При проведении СА для 20 изображений-кандидатов обеспечивается уменьшение ошибок второго рода на 36% и десятикратное уменьшение ошибок первого рода. При этом сохраняется низкая вычислительная сложность программы поиска изображений и сравнительно небольшие требования к объему памяти, необходимой для хранения БД изображений.
Расстояние до отдельных частей изображения, несёт информацию о форме объектов реального мира, которую можно использовать для решения многих задач компьютерного зрения [13].
Карта глубины (дальности) – это изображение, в котором яркость каждого пикселя пропорциональна расстоянию от объектива фотоприемника до объектов реальной трехмерной сцены, снимаемой с помощью камеры. Карта глубины, в которой расстояние удается получить для каждого пикселя изображений стереопары, называется плотной. Восстановление глубины при использовании стереокамеры сводится к решению задачи сопоставления пикселей левого и правого изображений. Зная диспаратность (смещение) пикселя в изображениях стереопары и параметры стереокамеры (стереобаза и фокус), можно восстановить реальное расстояние с точностью, зависящей от разрешения стереокамеры. Поскольку глубина напрямую связана с диспаратностью, то часто употребляют термин «карта диспаратности», подразумевая, что одно легко получить из другого.
