Разработка системы автоматического поиска объектов на изображении

Министерство образования Республики Беларусь

«Гомельский государственный университет имени Франциска Скорины»

Математический факультет Кафедра математических проблем управления Дипломная работа

Разработка системы автоматического поиска объектов на изображении

Исполнитель: Н. С. Музыка Научный руководитель: О. А. Шимчик Рецензент к.т.н, доцент А. В. Воруев Гомель 2013

1. Назначение разрабатываемого приложения

2. Средства разработки приложения

2.1 Язык программирования C++

2.2 Язык программирования C#

2.3 Среда разработки Eclipse

3. Обзор алгоритмов распознания объектов на двумерных изображениях

3.1 Алгоритм поиска максимума кросскорреляционной функции двух изображений

3.1.1 Модификация алгоритма поиска максимума дискретной кросскорреляционной функции от двух изображений

3.1.2 Модификации алгоритма поиска максимума кросскорреляционной функции

3.2 Обнаружение устойчивых признаков изображения: метод SURF

4. Исследование алгоритмов поиска объектов на плоскости

4.1 Методика исследования

4.2 Результаты исследования

4.2.1 Различные размеры подаваемых на вход изображений

4.2.2 Разные углы поворота объекта относительно сцены

4.2.3 Различные перекрытия объектов

4.3 Анализ результатов

5. Практическая реализация и применение алгоритмов поиска объектов на двумерных изображениях Заключение Список используемых источников Приложение

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

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

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

Что привело к возникновению потребности в новых алгоритмах обработки и распознания изображений.

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

Компьютерное зрение (машинное зрение) — совокупность программно-технических средств, обеспечивающих считывание в цифровой форме видеоизображений, их обработку и выдачу результата в форме, пригодной для его практического применения в реальном масштабе времени. Различают монокулярное и бинокулярное машинное зрение, предназначенных соответственно для построения и обработки плоских и объемных изображений. Исследование компьютерного зрения является научным направлением в области искусственного интеллекта и связанных с ним технологий считывания изображений реальных объектов, их обработки и использования полученных данных для автоматизированного решения прикладных задач. Начало разработок, связанных с данным направлением, относится к 1950;м годам. Первый реальный успех в этой области был достигнут в Корнеллской лаборатории аэронавтики в 1958;1960 годах в связи с реализацией на ЭВМ IBM-740 аппаратного варианта системы распознавания простейших зрительных образов — Mark I Perceptron (автор разработки — Фрэнк Розенблатт).

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

1. Назначение разрабатываемого приложения

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

1.Масштаб. Изображения имеют разный масштаб. Предметы, которые мы воспринимаем как одинаковые, на самом деле занимают разную площадь на разных изображениях.

2. Место. Интересующий нас объект может находиться в разных местах изображения.

3.Фон и помехи. Предмет, который мы воспринимаем как что-то отдельное, на изображении никак не выделен, и находится на фоне других предметов. Кроме того, изображение не идеально и может быть подвержено всякого рода искажениям и помехам.

4.Проекция, вращение и угол обзора. Изображение является лишь двумерной проекцией нашего трехмерного мира. Поэтому поворот объекта и изменение угла обзора кардинальным образом влияют на его двумерную проекцию — изображение. Один и тот же объект может давать совершенно разную картинку, в зависимости от поворота или расстояния до него.

При этом образец на сцене может:

a) иметь другой масштаб б) быть повернут в плоскости изображения в) быть в произвольном месте сцены г) может быть зашумлен, виден не полностью, частично заслонен другими предметами д) может иметь отличную от образца яркость и контраст е) его может не быть совсем

Определение 1. Образцом будем называть некоторый объект обладающий рядом визуальных свойств (форма, цвет) уникально идентифицирующими его на изображении.

Определение 2. Сценой будем называть растровое изображение на котором требуется найти образец.

Задача 1. Рассмотреть существующие алгоритмы и методы поиска объектов на двумерных изображениях.

Задача 2. Реализовать некоторые алгоритмы поиска объектов на изображениях с целью их дальнейшего изучения и анализа.

2. Средства разработки приложения

2.1 Язык программирования C++

Название «С++» было придумано Риком Масситти (Rick Mascitti) и впервые было использовано в декабре 1983 года. Ранее, на этапе разработки, новый язык назывался «С с классами».

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

Некоторые программисты на С могут заметить, что если выполняются выражения x=3; y=x++; то в результате получится x=4 и y=3, потому что x увеличивается только после присвоения его y. Однако если второе выражение будет y=++x; то получится x=4 и y=4.

Исходя из этого, можно сделать вывод, что логичнее было бы назвать язык не С++, а ++С. Однако оба выражения c++ и ++c увеличивают c, а кроме того выражение c++ более распространено.

Педанты также могут заметить, что введение языка С++ не изменяет самого C, поэтому самым точным именем было бы «С+1».

Новые возможности по сравнению с С Нововведениями С++ в сравнении с С являются:

— поддержка объектно-ориентированного программирования;

— поддержка обобщённого программирования через шаблоны;

— дополнительные типы данных;

— исключения;

— пространства имён;

— встраиваемые функции;

— перегрузка операторов;

— перегрузка имён функций;

— ссылки и операторы управления свободно распределяемой памятью;

— дополнения к стандартной библиотеке.

Язык С++ во многом является надмножеством С. Новые возможности С++ включают объявления в виде выражений, преобразования типов в виде функций, операторы new и delete, тип bool, ссылки, расширенное понятие константности, подставляемые функции, аргументы по умолчанию, переопределения, пространства имён, классы (включая и все связанные с классами возможности, такие как наследование, функции-члены, виртуальные функции, абстрактные классы и конструкторы), переопределения операторов, шаблоны, оператор, обработку исключений, динамическую идентификацию и многое другое. Язык С++ также во многих случаях строже относится к проверке типов, чем С.

В С++ появились комментарии в виде двойной косой черты («//»), которые были в предшественнике С — языке BCPL.

Некоторые особенности С++ позднее были перенесены в С, например ключевые слова const и inline, объявления в циклах for и комментарии в стиле С++ («//»). В более поздних реализациях С также были представлены возможности, которых нет в С++, например макросы vararg и улучшенная работа с массивами-параметрами.

Достоинства C++ — чрезвычайно мощный язык, содержащий средства создания эффективных программ практически любого назначения, от низкоуровневых утилит и драйверов до сложных программных комплексов самого различного назначения. В частности:

— Поддерживаются различные стили и технологии программирования, включая традиционное директивное программирование, ООП.

— Имеется возможность работы на низком уровне с памятью, адресами, портами.

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

— Кроссплатформенность.

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

— Эффективность.

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

Недостатки Отчасти недостатки C++ унаследованы от языка-предка — Си, — и вызваны изначально заданным требованием возможно большей совместимости с Си. Это такие недостатки, как:

— Синтаксис, провоцирующий ошибки: Операция присваивания обозначается как =, а операция сравнения как ==. Их легко спутать, при этом операция присваивания возвращает значение, поэтому присваивание на месте выражения является синтаксически корректным, а в конструкциях цикла и ветвления появление числа на месте логического значения также допустимо, так что ошибочная конструкция оказывается синтаксически правильной. Типичный пример подобной ошибки: if (x=0) { операторы } Здесь в условном операторе по ошибке написано присваивание вместо сравнения. В результате, вместо того, чтобы сравнить текущее значение x с нулём, программа присвоит x нулевое значение, а потом интерпретирует его как значение условия в операторе if. Так как нуль соответствует логическому значению «ложь» (false), блок операторов в условной конструкции не выполнится никогда. Ошибки такого рода трудно выявлять, но во многих современных компиляторах предлагается диагностика некоторых подобных конструкций. Операции присваивания (=), инкрементации (++), декрементации (—) и другие возвращают значение. В сочетании с обилием операций это позволяет, хотя и не обязывает, создавать трудночитаемые выражения. Наличие этих операций в Си было вызвано желанием получить инструмент ручной оптимизации кода, но в настоящее время оптимизирующие компиляторы обычно генерируют оптимальный код и на традиционных выражениях. С другой стороны, один из основных принципов языков C и C++ — позволять программисту писать в любом стиле, а не навязывать «хороший» стиль.

— Макросы (#define) являются мощным, но опасным средством. Они сохранены в C++ несмотря на то, что необходимость в них, благодаря шаблонам и встроенным функциям, не так уж велика. В унаследованных стандартных С-библиотеках много потенциально опасных макросов.

— Некоторые преобразования типов неинтуитивны. В частности, операция над беззнаковым и знаковым числами выдаёт беззнаковый результат.

— Необходимость записывать break в каждой ветви оператора switch и возможность последовательного выполнения нескольких ветвей при его отсутствии провоцирует ошибки из-за пропуска break. Эта же особенность позволяет делать сомнительные «трюки», базирующиеся на избирательном неприменении break и затрудняющие понимание кода.

— Препроцессор, унаследованный от С, очень примитивен. Это приводит с одной стороны к тому, что с его помощью нельзя (или тяжело) осуществлять некоторые задачи метапрограммирования, а с другой, вследствие своей примитивности, он часто приводит к ошибкам и требует много действий по обходу потенциальных проблем. Некоторые языки программирования (например, Scheme и Nemerle) имеют намного более мощные и более безопасные системы метапрограммирования (также называемые макросами, но мало напоминающие макросы С/С++).

— Плохая поддержка модульности (по сути, в классическом Си модульность на уровне языка отсутствует, её обеспечение переложено на компоновщик). Подключение интерфейса внешнего модуля через препроцессорную вставку заголовочного файла (#include) серьёзно замедляет компиляцию при подключении большого количества модулей (потому что результирующий файл, который обрабатывается компилятором, оказывается очень велик). Эта схема без изменений скопирована в C++. Для устранения этого недостатка, многие компиляторы реализуют механизм прекомпиляции заголовочных файлов Precompiled Headers.

К собственным недостаткам C++ можно отнести: Сложность и избыточность, из-за которых C++ трудно изучать, а построение компилятора сопряжено с большим количеством проблем. В частности: В языке практически полностью сохранён набор конструкций Си, к которому добавлены новые средства. Во многих случаях новые средства и механизмы позволяют делать то же самое, что и старые, но в языке сохраняются оба варианта.

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

Недостаток информации о типах данных во время компиляции (CTTI). Метапрограммирование на основе шаблонов C++ сложно и при этом ограничено в возможностях. Оно состоит в реализации средствами шаблонов C++ интерпретатора примитивного функционального языка программирования выполняющегося во время компиляции. Сама по себе данная возможность весьма привлекательна, но такой код весьма трудно воспринимать и отлаживать. Языки Lisp/Scheme, Nemerle и некоторые другие имеют более мощные и одновременно более простые для восприятия подсистемы метапрограммирования. Кроме того, в языке D реализована сравнимая по мощности, но значительно более простая в применении подсистема шаблонного метапрограммирования. Хотя декларируется, что С++ мультипарадигменный язык, реально в языке отсутствует поддержка функционального программирования. Отчасти, данный пробел устраняется различными библиотеками (Loki, Boost) использующими средства метапрограммирования для расширения языка функциональными конструкциями (например, поддержкой лямбд/анонимных методов), но качество подобных решений значительно уступает качеству встроенных в функциональные языки решений. Такие возможности функциональных языков, как сопоставление с образцом, вообще крайне сложно эмулировать средствами метапрограммирования. Некоторые считают недостатком языка C++ отсутствие встроенной системы сборки мусора. С другой стороны, в C++ имеется достаточно средств, позволяющих почти исключить использование опасных указателей, нет принципиальных проблем и в реализации и использовании сборки мусора (на уровне библиотек, а не языка). Отсутствие встроенной сборки мусора позволяет пользователю самому выбрать стратегию управления ресурсами.

2.2 Язык программирования C#

Язык C# является языком программирования, по синтаксису очень похожим на Java (но не идентичным ему). Однако называть C# «переработанным» вариантом Java будет неверно. C#, как и Java, основан на синтаксических конструкциях C++. Так же, как и Java, C# можно называть «рафинированной» версией C++ - в конце концов, это языки одного семейства. Многие синтаксические конструкции C# построены с учетом решений, принятых в Visual Basic 6.0 и C++. Например, как и в VB6, в C# поддерживаются формальные свойства типов (в противоположность традиционным методам get и set) и возможность объявления методов с переменным числом аргументов (через массивы параметров). Подобно C++, в C# позволяется перегрузка операций, а также создание структур, перечней и функций обратного вызова (посредством делегатов).

Благодаря тому, что C# является гибридом множества языков, он является продуктом, который синтаксически так же «чист», как Java (если не «чище»), почти так же прост, как VB6, и обладает почти такой же мощью и гибкостью, как C++ (без соответствующих «ужасных» конструкций).

По сути, язык C# предлагает следующие возможности (многие из которых присущи и всем другим языкам программирования, обеспечивающим поддержку .NET).

— Не требуется никаких указателей! Программы на C# обычно не требуют прямого обращения к указателям (хотя имеется возможность получить к ним доступ на более низком уровне, если вы сочтете это абсолютно необходимым).

— Автоматическое управление памятью через сборку мусора. По этой причине в C# не поддерживается ключевое слово delete.

— Формальные синтаксические конструкции для перечней, структур и свойств классов.

— Аналогичная C++ перегрузка операций для пользовательских типов, но без лишних сложностей (например, вам не требуется контролировать «возвращение *this для связывания»).

— В C# 2005 имеется возможность строить общие типы и общие члены с использованием синтаксиса, очень похожего на шаблоны C++.

— Полная поддержка технологии аспектно-ориентированного программирования (АОП) через атрибуты. Эта ветвь разработки позволяет назначать характеристики типам и их членам, чтобы уточнять их поведение.

Возможно, самым важным для правильного понимания языка C#, поставляемого Microsoft в связке с платформой .NET, является то, что получаемый с помощью C# программный код может выполняться только в среде выполнения .NET (вы не сможете использовать C# для построения «классического» COM-сервера или автономного приложения Win32 API). Официальный термин, который используется для описания программного кода, предназначенного для среды выполнения .NET, — управляемый программный код (managed code). Бинарный объект, содержащий такой управляемый программный код, называется компоновочным блоком (подробнее о компоновочных блоках мы поговорим немного позже). С другой стороны, программный код, который не может непосредственно управляться средой выполнения .NET, называется неуправляемым программным кодом (unmanaged code).

2.3 Среда разработки Eclipse

Первоначально Eclipse разрабатывалась фирмой IBM как преемник среды разработки IBM VisualAge, в качестве корпоративного стандарта IDE для разработки на разных языках под платформы IBM. По сведениям IBM, проектирование и разработка стоили 40 миллионов долларов. Исходный код был полностью открыт и сделан доступным после того, как Eclipse был передан для дальнейшего развития независимому от IBM сообществу.

В Eclipse 3.0 (2003 год) были выбраны спецификации сервисной платформы OSGi, как архитектура времени выполнения. С версии 3.0 Eclipse перестал быть монолитной IDE, поддерживающей расширения, а сам стал набором расширений. В основе лежат фреймворк OSGi и SWT/JFace, на основе которых разработан следующий слой — RCP (Rich Client Platform, платформа для разработки полноценных клиентских приложений). RCP служит основой не только для Eclipse, но и для других RCP-приложений, например Azureus и File Arranger. Следующий слой — сам Eclipse, представляющий собой набор расширений RCP — редакторы, панели, перспективы, модуль CVS и модуль Java Development Tools (JDT).

С 2006 года фонд Eclipse координирует ежегодный общий релиз (Simultaneous Release), который происходит в июне. Каждый выпуск включает в себя платформу Eclipse, а также ряд других проектов Eclipse.

Eclipse служит в первую очередь платформой для разработки расширений, чем он и завоевал популярность: любой разработчик может расширить Eclipse своими модулями. Уже существуют Java Development Tools (JDT), C/C++ Development Tools (CDT), разрабатываемые инженерами QNX совместно с IBM, и средства для языков Ada (GNATbench, Hibachi), COBOL, FORTRAN, PHP и пр. от различных разработчиков. Множество расширений дополняет среду Eclipse менеджерами для работы с базами данных, серверами приложений и др.

Eclipse JDT (Java Development Tools) — наиболее известный модуль, нацеленный на групповую разработку: среда интегрирована с системами управления версиями — CVS, GIT в основной поставке, для других систем (например, Subversion, MS SourceSafe) существуют плагины. Также предлагает поддержку связи между IDE и системой управления задачами (ошибками). В основной поставке включена поддержка трекера ошибок Bugzilla, также имеется множество расширений для поддержки других трекеров (Trac, Jira и др.). В силу бесплатности и высокого качества, Eclipse во многих организациях является корпоративным стандартом для разработки приложений.

Eclipse написана на Java, потому является платформо-независимым продуктом, за исключением библиотеки SWT, которая разрабатывается для всех распространённых платформ (см. ниже). Библиотека SWT используется вместо стандартной для Java библиотеки Swing. Она полностью опирается на нижележащую платформу (операционную систему), что обеспечивает быстроту и натуральный внешний вид пользовательского интерфейса, но иногда вызывает на разных платформах проблемы совместимости и устойчивости приложений. Основой Eclipse является платформа расширенного клиента (RCP — от англ. rich client platform). Её составляют следующие компоненты:

— Ядро платформы (загрузка Eclipse, запуск модулей);

— OSGi (стандартная среда поставки комплектов (англ. bundles));

— SWT (портируемый инструментарий виджетов);

— JFace (файловые буферы, работа с текстом, текстовые редакторы);

— Рабочая среда Eclipse (панели, редакторы, проекции, мастеры).

GUI в Eclipse, написан с использованием инструментария SWT. Последний, в отличие от Swing (который самостоятельно эмулирует графические элементы управления), использует графические компоненты данной операционной системы. Пользовательский интерфейс Eclipse также зависит от промежуточного слоя GUI, называемого JFace, который упрощает построение пользовательского интерфейса, базирующегося на SWT.

Гибкость Eclipse обеспечивается за счёт подключаемых модулей, благодаря чему возможна разработка не только на Java, но и на других языках, таких как C/C++, Perl, Groovy, Ruby, Python, PHP, Erlang, Компонентного Паскаля, Zonnon и прочих.

3. Обзор алгоритмов распознания объектов на двумерных изображениях

3.1 Алгоритм поиска максимума кросскорреляционной функции двух изображений

Дискретной кросскорреляций функций f (t) и g (t), определенных на множестве целых чисел Z, называется следующая операция:

Кросскорреляция чаще всего применяется в обработке сигналов, при этом f считается образцом, а g — сигналом, содержащим образец. Результат — это вектор чисел, показывающих, насколько сильно образец выражен в сигнале. В нашем случае мы можем представить наши изображения в виде двух дискретных функций яркости и применить к ним операцию кросс-корреляции. Максимум этой функции будет находиться в той области где изображения совпадают больше всего. По сути операция кросс-корреляции является сверткой двух функций.

3.1.1 Модификация алгоритма поиска максимума дискретной кросскорреляционной функции от двух изображений

Как упоминалось ранее операция кросс-корреляции по сути является сверткой двух функций. Свёртка функций — операция в функциональном анализе, показывающая «схожесть» одной функции с отражённой и сдвинутой копией другой.

Свойства:

1. Коммутативность:

f * g = g * f

2. Ассоциативность:

f * (g * h) = (f * g) * h

3. Дистрибутивность:

f * (g + h) = (f * g) + (f * h)

4. Ассоциативность умножения на скаляр:

5. Правило дифференцирования:

D (f * g) = Df * g = f * Dg,

где Df обозначает производную функции f.

6. Свойство Фурье-образа:

где F (f)

обозначает преобразование Фурье функции f.

Как следствие мы можем воспользоваться свойством 6 свертки.

Преобразование Фурье — операция, сопоставляющая функции вещественной переменной другую функцию вещественной переменной. Эта новая функция описывает коэффициенты («амплитуды») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами.

Преобразование Фурье функции f вещественной переменной является интегральным преобразованием и задается следующей формулой:

По сути говоря, мы заменяем операцию вычисления свертки операцией умножения Фурье-образов функций яркости изображений. Что позволяет значительно повысить производительность.

Применительно к нашей области мы воспользуемся дискретным преобразованием Фурье.

Прямое преобразование:

Обратное преобразование:

Применяя прямое преобразование к функциям яркости наших изображений, мы получаем вектора комплексных чисел. Перемножая поэлементно их, мы получим вектор комплексных чисел. Беря обратное преобразование Фурье, получаем значения функции свертки. Находя максимум среди этих значений, мы находим точку в которой наши два изображения наиболее похожи.

Достоинства метода:

— Простота реализации

— Быстрота работы (как будет показано позднее)

— Качественное детектирование объектов на изображении

— Устойчивость к масштабированию Недостатки метода:

— Т. к. метод ищет глобальный максимум, то он может найти только 1 совпадение

— Не устойчив к поворотам

— Относительно плохо устойчив к изменению общего уровня яркости изображений

3.1.2 Модификации алгоритма поиска максимума кросскорреляционной функции

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

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

— Найти все точки с координатами i, j такие что где maxi и maxj координаты глобального максимума, а e некоторая константа. е можно выбирать разными способами.

— Найти все точки с координатами i, j такие что где w-ширина изображения h — высота изображения N=w*h.

Результатом данной модификации является избавление от проблемы детектирования лишь 1 объекта.

3.2 Обнаружение устойчивых признаков изображения: метод SURF

Принцип работы алгоритма заключается в следующем. Для изображения сцены и изображения эталона с помощью метода SURF находятся особые точки и уникальные дескрипторы для них. Сравнивая эти наборы дескрипторов, мы можем выделить эталонный объект на сцене. А теперь более подробно.

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

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

Градиент в точке вычисляется с помощью фильтров Хаара.

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

Флуктуации градиента также считаются с помощью фильтра Хаара.

Интегральное представление Для эффективного вычисления фильтров Гессе и Хаара — используется интегральное представление изображений.

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

Где I (i, j) — яркость пикселей исходного изображения.

Имея интегральную матрицу можно очень быстро вычислять сумму яркостей пикселей произвольных прямоугольных областей изображения, по формуле:

SumOfRect (ABCD) = II (A) + II (С) — II (B) — II (D)

Где ABCD — интересующий нас прямоугольник.

Вычисление матрицы Гессе. Обнаружение особых точек в SURF основано на вычислении детерминанта матрицы Гессе (гессиана).

Матрица Гессе для двумерной функции и ее детерминант определяется следующим образом:

Значение гессиана используется для нахождения локального минимума или максимума яркости изображения. В этих точках значение гессиана достигает экстремума. Теоретически, вычисление матрицы Гессе сводится к нахождению Лапласиана Гауссиан.

По сути, элементы матрицы Гессе вычисляются как свертка (сумма произведений) пикселей изображения на фильтры, изображенные на рисунке 1:

Рисунок 1

На рисунке 1 изображены дискретизированные фильтры для нахождения четырех элементов матрицы Гессе (четвертый — совпадает с третьим, поскольку матрица Гессе симметрична). Фильтры имеют пространственный масштаб 9×9 пикселей. Темные участки соответствуют отрицательным значениям фильтра, светлые — положительным.

Однако, SURF не использует лапласиан гауссианы в том виде, который изображен на рисунке. Во-первых, по утверждению авторов, дискретизированный лапласиан гауссианы имеет довольно большой разброс значения детерминанта, при вращении образца (напомним, что в идеале гессиан должен быть инвариантен к вращению). Особенно детерминант «проседает» в районе поворота на 45 градусов. А во-вторых, и это главное, фильтр для лапласиана гауссианы имеет непрерывный характер. Почти все пиксели фильтра имеют разные величины яркости. А это не позволяет эффективно использовать такой мощный механизм расчёта, как интегральную матрицу изображения. Поэтому SURF использует бинаризированную аппроксимацию лапласиана гауссиан (авторы назвали его Fast-Hessian):

Рисунок 2

На рисунке 2 изображены фильтры, используемые для нахождения матрицы Гессе в SURF. Белые области соответствуют значению +1, черные -2 (на третьем фильтре -1), серые — нулевые. Пространственный масштаб — 9×9 пикселей.

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

Таким образом, в SURF, гессиан вычисляется так:

Где Dxx, Dyy, Dxy — свертки по фильтрам, изображенным на рисунке вверху. Коэффициент 0.9 имеет теоретическое обоснование, и корректирует приближенный характер вычислений.

Итак, для нахождения особых точек, SURF пробегается по пикселям изображения и ищет максимум гессиана. Способ нахождения локального максимума гессиана мы рассмотрим позднее. В методе задается пороговое значение гессиана. Если вычисленное значение для пикселя выше порога — пиксель рассматривается как кандидат на ключевую точку.

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

Кроме того, свойства гессиана таковы, что он достигает максимума, как в точке белого пятна на черном фоне, так и черного пятна на белом фоне. Таким образом, метод обнаруживает и темные, и светлые особенности изображения.

Шкалы Как уже отмечалось, гессиан не инвариантен относительно масштаба. Это значит, что для одного и того же пикселя, гессиан может меняться при изменении масштаба фильтра.

Решение этой проблемы только одно — перебирать различные масштабы фильтров и поочередно их применять к данному пикселю.

Из соображений симметрии и дискретизации, размер фильтра Fast-Hessian не может принимать произвольные значения. Допустимые размеры этого фильтра таковы (начиная с минимального): 9, 15, 21, 27 и так далее, с шагом 6. Однако, на практике, постепенно увеличивать размер фильтра на 6 — не выгодно, потому что для крупных масштабов шаг 6 оказывается слишком мелким, а фильтры — избыточными. Поэтому (и по некоторым другим причинам), SURF разбивает все множество масштабов на так называемые октавы.

Каждая октава покрывает определенный интервал масштабов, и имеет свой характерный размер фильтра.

При этом если бы на октаву приходился только один фильтр, это было бы слишком грубым приближением. Кроме того, мы бы не могли найти локальный максимум гессиана, среди разных масштабов, в разных октавах. Ведь одна и та же точка может иметь несколько локальных максимумов гессиана, в разных масштабах. Это хорошо видно на картинке:

Рисунок 3

Рисунок 3 показывает две ключевые точки разного масштаба в одной точке изображения.

Если мы будем искать максимум среди всех гессианов, по всем масштабам, то мы бы нашли только один из максимумов, в то время как их может быть несколько. Один — в одном масштабе, другой — в другом.

Исходя из перечисленного, октава содержит не один фильтр, а четыре фильтра, которые хорошо покрывают характерный масштаб октавы:

Рисунок 4

На рисунке 4 показаны первые три октавы метода SURF. Цифры в прямоугольниках показывают размер фильтра Fast-Hessian. Логарифмическая шкала снизу — показывает масштабы, покрываемые октавами.

Шаг размера фильтра в первой октаве — составляет 6, во второй — 12, в третьей — 24 и так далее.

Как видим, октавы значительно перекрываются друг другом. Это увеличивает надежность нахождения локальных максимумов. Почему в октаве именно четыре фильтра станет ясно из следующей главы.

Возникает вопрос, а сколько собственно октав достаточно для покрытия множества особых точек разных масштабов? Теоретически, масштабы бесконечны, однако в реальных изображениях, они вполне конечны, и основная масса сосредоточена в интервале от 1 до 10 (по данным авторов метода). Для покрытия этого диапазона достаточно четырех октав. Плюс добавляется одна или две октавы для покрытия больших масштабов. Итого, используется 5−6 октав. Теоретически, этого вполне достаточно для покрытия всевозможных масштабов на изображении 1024×768 пикселов.

Нахождение локального максимума гессиана Для нахождения локального максимума гессиана, используется так называемый метод соседних точек 3x3x3.

Его смысл понятен из рисунка ниже:

Рисунок 5

Пиксель, помеченный крестиком считается локальным максимумом, если его гессиан больше чем у любого его соседа в его масштабе, а также больше любого из соседей масштабом меньше и масштабом больше (всего 26 соседей).

Исходя из такого определения локального максимума, понятно, что октава должна содержать не менее трех фильтров, иначе мы не сможем определить факт нахождения локального максимума гессиана внутри октавы.

Отметим еще такой момент. Фильтры октавы считаются не для всех пикселов подряд.

Первая октава считается для каждого второго пикселя изображения. Вторая — для каждого четвертого, третья — для каждого восьмого и так далее. Смысл понятен — две точки с расстоянием 2 не могут содержать более одного максимума масштаба 2, 3 или более высоких масштабов. Поэтому нет смысла перебирать все точки изображения, для нахождения максимума масштаба 3, например.

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

Поэтому, несмотря на то, что октава содержит четыре фильтра, на самом деле каждая октава (кроме первой) считает только два характерных для нее размера, два других — всегда можно взять из предыдущих октав. Первая же октава вынуждена считать все четыре своих фильтра.

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

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

Сначала, вычисляются точечные градиенты в пикселях, соседних с особой точкой. Для рассмотрения берутся пиксели в окружности радиуса 6s вокруг особой точки. Где s — масштаб особой точки. Для первой октавы берутся точки из окрестности радиусом 12.

Для вычисления градиента, используется фильтр Хаара. Размер фильтра берется равным 4s, где s — масштаб особой точки. Вид фильтров Хаара показан на рисунке 6:

Рисунок 6

Фильтры Хаара. Черные области имеют значения -1, белые +1. Фильтры Хаара дают точечное значение перепада яркости по оси X и Y соответственно.

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

Значения вейвлета Хаара dX и dY для каждой точки умножаются на вес и запоминаются в массиве. Вес определяется как значение гауссианы с центром в особой точке и сигмой равной 2s. Взвешивание на гауссиане необходимо для отсечения случайных помех на далеких от особой точки расстояниях.

Далее, все найденные значения dX и dY, условно наносятся в виде точек на плоскость, как показано на рисунке 7:

Рисунок 7

На рисунке 7 показаны все найденные градиенты в виде точек в пространстве dXdY.

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

Манипуляции с окном нужны для уменьшения влияния шумовых точек. Ниже на рисунке 8 приведен пример градиента при идеальном крае, и при крае с шумом:

Рисунок 8

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

Отметим, что не всегда требуется инвариантность дескрипторов относительно вращения.

Метод SURF имеет модификацию, в которой ориентация особых точек не рассчитывается.

Такая модификация позволяет надежно идентифицировать точки, повернутые не более чем на ±15 градусов.

Вычисление дескриптора особой точки Дескриптор представляют собой массив из 64 (в расширенной версии 128) чисел, позволяющих идентифицировать особую точку. Дескрипторы одной и той же особой точки на образце и на сцене должны примерно совпадать. Метод расчета дескриптора таков, что он не зависит от вращения и масштаба. Для вычисления дескриптора, вокруг особой точки формируется прямоугольная область, имеющая размер 20s, где s — масштаб в котором была найдена особая точка. Для первой октавы, область имеет размер 40×40 пикселей. Квадрат ориентируется вдоль приоритетного направления, вычисленного для особой точки.

Дескриптор считается как описание градиента для 16 квадрантов вокруг особой точки.

Рисунок 9

Далее, квадрат разбивается на 16 более мелких квадрантов, как показано на рисунке. В каждом квадранте берется регулярная сетка 5×5 и для точки сетки ищется градиент, с помощью фильтра Хаара. Размер фильтра Хаара берется равным 2s, и для первой октавы составляет 4×4.

Следует отметить, что при расчёте фильтра Хаара, изображение не поворачивается, фильтр считается в обычных координатах изображения. А вот полученные координаты градиента (dX, dY) поворачиваются на угол, соответствующий ориентации квадрата. Итого, для вычисления дескриптора особой точки, нужно вычислить 25 фильтров Хаара, в каждом из 16 квадрантов. Итого, 400 фильтров Хаара. Учитывая, что на фильтр нужно 6 операций, выходит, что дескриптор обойдется минимум в 2400 операций.

После нахождения 25 точечных градиента квадранта, вычисляются четыре величины, которые собственно и являются компонентами дескриптора: ?dX, ?|dX|, ?dY, ?|dY|

Две из них есть просто суммарный градиент по квадранту, а две других — сумма модулей точечных градиентов.

Четыре компонента на каждый квадрант, и 16 квадрантов, дают 64 компонента дескриптора для всей области особой точки. При занесении в массив, значения дескрипторов взвешиваются на гауссиану, с центром в особой точке и с сигмой 3.3s. Это нужно для большей устойчивости дескриптора к шумам в удаленных от особой точки областях.

Плюс к дескриптору, для описания точки используется знак следа матрицы Гессе, то есть величина sign (Dxx+Dyy). Для светлых точек на темном фоне, след отрицателен, для темных точек на светлом фоне — положителен. Таким образом, SURF различает светлые и темные пятна.

Таким образом применив SURF к изображению мы получим набор дескрипторов который будет уникально идентифицировать эталон на сцене.

Достоинства метода:

— Инвариантен к поворотам и масштабированию

— Инвариантен к разнице общей яркости изображений

— Может детектировать более 1 объекта на сцене Недостатки метода:

— Достаточно сложен в реализации

— Относительно медленная работа алгоритма

4. Исследование алгоритмов поиска объектов на плоскости

4.1 Методика исследования

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

Для сравнения алгоритмов в различных условиях в экспериментах строились наборы данных, со следующими характеристиками:

— Размер сцены от 500×500 до 1500×1500, размер эталонного изображения от 40×40 до 500×500.

— Разные углы поворота объекта относительно сцены от 0 до 360.

— Различные перекрытия объекта посторонними наложениями от 0% до 100%

В параграфах 4.2.1 — 4.2.3 приведены результаты моделирования работы различных алгоритмов поиска объектов на различных типах экспериментальных данных.

Эксперименты проводились на машине с процессором intel i5 core, среднее время обработки представлено в миллисекундах, точность работы алгоритмов измеряется в процентах от общего количества правильно локализованных объектов на сцене.

4.2 Результаты исследования

4.2.1 Различные размеры подаваемых на вход изображений

Рисунок 10

График показывает время обработки в зависимости от суммарного количества пикселов.

4.2.2 Разные углы поворота объекта относительно сцены

Рисунок 11

График показывает, сколько процентов повернутых на угол объектов правильно локализовано, угол поворота указан в градусах.

4.2.3 Различные перекрытия объектов

Рисунок 12

График показывает, сколько процентов заслоненных объектов правильно локализовано, нижняя ось отражает какой процент площади объекта заслонен.

4.3 Анализ результатов

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

5. Практическая реализация и применение алгоритмов поиска объектов на двумерных изображениях

Автором была разработана программная реализация двух алгоритмов поиска объектов на двумерных изображениях, которые могут быть применены в различных приложениях. В настоящее время разработанные программные продуты находится на стадии оптимизации.

Пример работы реализации метода поиска максимума кросскорреляционной функции.

— После запуска приложения нам предлагается ввести пути к изображению сцены и к эталонному изображению объекта

Рисунок 13

— После непродолжительной обработки будут показаны два окна

Рисунок 14

В окне «Etalonobject» отображается загруженное эталонное изображение объекта, в окне «Findobject» отображается уже обработанная сцена с отмеченным на ней объектом.

Пример работы реализации метода SURF.

После загрузки приложения нажмите кнопку «Run» откроется диалоговое окно выбора файлов укажите файл эталон и файл сцену, после непродолжительной работы будут показаны результаты обработки этих файлов.

Рисунок 15

Кругами выделены особые точки, найденные с помощью метода SURF.

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

Заключение

По результатам проведенной работы можно сделать следующий вывод Как показало исследование, различные алгоритмы имеют свои преимущества и недостатки, как следствие все алгоритмы имеют свою область применения.

В ходе работы над проектом были достигнуты следующие цели:

1. Проанализированы существующие алгоритмы поиска объектов на изображениях в двухмерном пространстве. Показаны их достоинства и недостатки.

2. Проанализированы способы эффективной практической реализации алгоритмов поиска объектов на изображениях.

3. Предложен подход для поиска дополнительных максимумов, позволяющий улучшить существующий алгоритм.

4. Проведено исследование некоторых алгоритмов поиска объектов на двумерных изображениях.

5. Реализованы несколько алгоритмов для поиска объектов на двумерных изображениях.

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

Список используемых источников

1. Дуда Р., Харт П. Распознавание образов и анализ сцен. текст] - М.: Мир, 1976. — 511 с.

2. Верхаген К., Дейн Р., Грун Ф. Распознавание образов: Состояние и перспективы. текст] - М.: Радио и связь, 1985. — 104 с.

3. Пересада В. П. Автоматическое распознавание образов. Библиотека по автоматике, выпуск 392. текст] - 1970. — С. 92.

4. Вапник В. Н., Червоненкис А. Я. — Теория распознавания образов и стохастические проблемы обучения. текст] - M.: Наука, 1974 г. — 416 с.

5.Мерков А. Б. — Распознавание образов.

Введение

в методы ъ статистического обучения. текст] - М.: Едиториал УРСС, 2011 г. — 256 с.

6.Потапов А. С. — Распознавание образов и машинное восприятие. текст] - М.: Политехника, 2007 г. — 552 с.

7. Шапиро Л., Стокман Дж. — Компьютерное зрение. текст] - М.: Бином. Лаборатория знаний, 2006 г. — 752 с.

8. Дэвид Форсайт, Жан Понс Компьютерное зрение. Современный подход. текст] - М.: Вильямс, 2004 г. — 928 с.

9. Алпатов Б. А., Бабаян П. В., Балашов О. Е., Степашкин А. И. Методы автоматического обнаружения и сопровождения объектов. Обработка изображений и управление. текст] - М.: Радиотехника, 2008 г. — 176 с.