Система геодезического анализа карт местности

Гальетов Владимир Валерьевич

Система геодезического анализа карт местности

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

Общественные науки в целом

Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d36505f1be77c40d58c5a

UUID: 84869d17-4614-4ad5-80d3-6a1c4d54b504

Язык: Русский

Опубликовано: больше 7 лет назад

Просмотры: 32

Гальетов Владимир Валерьевич

Источник: Санкт-Петербургский государственный университет

Комментировать 0

Рецензировать 0

Скачать - 1301097 bytes

Поделиться работой

Санкт-Петербургский государственный университет Кафедра компьютерных технологий и систем Гальетов Владимир Валерьевич Выпускная квалификационная работа бакалавра «Система геодезического анализа карт местности» Направление 010300 Фундаментальная информатика и информационные технологии Научный руководитель, кандидат физ.-мат. наук, доцент Мисенов Б. А. Санкт-Петербург 2016

Оглавление Введение ............................................................................................................... 3 Постановка задачи................................................................................................ 5 Обзор литературы ................................................................................................ 6 Глава 1. Анализ и теоретические основы реализуемых методов ...................... 8 1.1 Методы сравнения гистограмм .................................................................. 8 1.1.1 Гистограммы ...................................................................................... 8 1.1.2 Особенности применения методов ....................................................... 9 1.1.3 Методы сравнения гистограмм ....................................................... 11 1.2 Метод опорных векторов .......................................................................... 12 1.2.1 Метод опорных векторов для случая линейной разделимости ........ 12 1.2.2 Метод опорных векторов для случая линейной неразделимости ..... 15 Глава 2. Реализация методов ............................................................................. 18 2.1 Обзор инструментария .............................................................................. 18 2.2 Обзор программной реализации ............................................................... 19 2.2.1 Метод сравнения гистограмм ............................................................. 19 2.2.2 SVM...................................................................................................... 21 Глава 3. Тестирование систем ........................................................................... 25 3.1 Тестирование методов сравнения гистограмм ........................................ 25 3.2 Тестирование SVM .................................................................................... 26 3.3 Сравнительное тестирование метода пересечения гистограмм и SVM с ядром RBF ....................................................................................................... 28 3.4 Влияние различных параметров на качество распознавания ................. 29 3.4.1 Параметры метода опорных векторов................................................ 29 3.4.2 Параметры метода сравнения гистограмм ......................................... 30 Выводы ............................................................................................................... 31 Заключение ......................................................................................................... 32 Список литературы ............................................................................................ 33 2

Введение В настоящее время происходит стремительное развитие компьютерной техники, информационных технологий. Каждый год появляется множество новых применений, внедрений этих технологий в жизнь человека. При этом тенденция развития такова, что наука и техника все больше применяются не только в технических, индустриальных сферах, но и в самых повседневных и бытовых областях деятельности человека. И здесь важную роль играет автоматизация, компьютеризация подобных механистических процессов, которые прежде приходилось выполнять человеку. Одним из таких процессов является геодезический анализ, или дешифрирование изображений земной поверхности, полученных с помощью аэрофотосъемки, либо космофотосъемки. Если раньше распознаванием объектов земной поверхности занимались географы, то в настоящее время важной и актуальной задачей является разработка компьютерных систем, автоматически дешифрирующих эти фотоснимки. Значимость выбранной темы заключается в том, что результаты работы подобной компьютерной системы будут полезны для решения целого ряда прикладных задач в самых разных областях. Основываясь на этих результатах, человек сможет заниматься принятием решений на более высоком уровне, а впоследствии, с еще большим развитием компьютерной индустрии, эти результаты могут быть использованы уже системами искусственного интеллекта, которые будут призваны освободить человека от необходимости принятия решений и на этом (более высоком) уровне. Стоит заметить, что компьютерное зрение – одна из активно развивающихся областей на протяжении уже около 40 лет, имеющая множество практических приложений и играющая важную роль в процессе формирования интеллектуальных систем, разработка которых активно 3

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

Постановка задачи Целью данной работы является исследование методов распознавания изображений и разработка двух систем, основанных на выбранных методах, анализ и тестирование полученных систем, выделение их достоинств и недостатков, заключение о возможности формирования на их основе самодостаточной системы распознавания и классификации объектов земной поверхности. Для достижения указанной цели необходимо решить следующие задачи:  провести исследование существующих методов распознавания изображений и выбор двух из них, потенциально подходящих для распознавания на фотоснимках объектов земной поверхности;  осуществить необходимые модификации выбранных методов с целью учета особенностей предметной области;  реализовать две системы, способные распознавать объекты земной поверхности;  провести тестирование разработанных систем, их анализ и оценку эффективности. 5

Обзор литературы Изучение литературы, научных статей и интернет-источников в сфере дистанционного зондирования Земли, мониторинга земной поверхности позволяет говорить о том, что такие задачи, как дешифрирование (интерпретация) аэрофотоснимков и космофотоснимков, а главное – автоматизация этого процесса, являются важными прикладными задачами, требующими эффективного решения. При этом требования детализации решений задач дешифрирования, распознавания могут варьироваться от выделения на снимках объектов только одного вида до полного картографирования территории. В настоящее время активно разрабатываются прикладные программные системы, содержащие подсистемы дешифрирования снимков. Назначение таких систем – анализ и получение новых данных (например, в военных целях), получение карт. Подобные системы могут применяться в таких областях, как сельское хозяйство (задачи классификации, различных оценок, мониторинга), геодезия (в основном – геологические и военные задачи), исследования природной среды – мониторинг лесного покрова (задачи разграничения территории) и мониторинг поверхности в целом (создание более новых карт, планирование рационального использования природных ресурсов, расчет рисков, экологическая защита). [1] Одной из наиболее сложных проблем является распознавание текстур природных объектов. Стоит упомянуть о том, что при решении задач распознавания текстур наиболее важным является нахождение такого алгоритма и его параметров, что они будут работать наиболее универсально для разных видов текстур, так как многие алгоритмы можно настроить таким образом, что для конкретного случая он будет работать практически идеально, а для другого – давать неудовлетворительные результаты [2, 3]. 6

Для реализации таких алгоритмов были выбраны два метода – метод сравнения гистограмм и метод опорных векторов. В [4, 5] подробно и формально описан метод опорных векторов, а также содержится общая информация об алгоритмах машинного обучения. В [6, 7] описаны подробности реализации алгоритмов при помощи графической библиотеки OpenCV. В [8] описаны основные подходы к распознаванию объектов на спутниковых снимках. В [9] содержится информация о практическом тестировании метода опорных векторов. 7

Глава 1. Анализ и теоретические основы реализуемых методов В этой главе подробно рассматриваются методы, выбранные для решения поставленной задачи, включая теоретические основы, необходимые модификации и улучшения. 1.1 Методы сравнения гистограмм 1.1.1 Гистограммы Цветовые гистограммы часто используются в задачах распознавания объектов на изображениях, классификации, нахождения сходных изображений. В общем случае, гистограмма – это некоторый набор, коллекция данных, представленных в виде распределения значений, которые содержат информацию о количестве точек, отражающих какое-либо свойство объекта. Гистограммы можно применять для описания изображений. С помощью гистограмм возможно несколько вариантов описания изображения: пиксели, градиенты, направления и т.д. В работе гистограмма рассматривается как распределение значений, каждое из которых отвечает количеству пикселей изображения с определенной интенсивностью. Здесь стоит отметить, что можно группировать несколько пикселей с разной интенсивностью (т.е. несколько точек), такие группы называются бинами. В этом случае, значение гистограммы, соответствующее такому бину, будет вычисляться как количество пикселей, которые содержит бин. Стоит учитывать разницу между вычислением гистограмм для изображений в градациях серого и для цветных изображений. Чтобы вычислить гистограмму для изображения в градациях серого, необходимо просто подсчитать количество пикселей на изображении для каждого значения интенсивности, которое содержится в диапазоне от 0 до 255 (то есть 8

в данном случае изображение является одноканальным, для хранения одного пикселя достаточно одного байта информации). Однако, для того, чтобы вычислить гистограмму для цветного изображения, необходимо предварительно разделить исходное изображение на три «плоскости» (по числу каналов в цветном изображении в модели RGB), каждая из которых будет содержать значения интенсивности для каждого из трех каналов. На рисунке 1 можно видеть цветное изображение и построенные для нее гистограммы для каждого из RGB-каналов. Рис. 1. Цветное изображение (слева), гистограммы для 3-х каналов (справа) 1.1.2 Особенности применения методов Одним из наиболее простых и широко используемых методов поиска сходных изображений является метод сравнения гистограмм. В рассматриваемой работе этот метод используется для классификации текстур на изображении земной поверхности. Для идентификации текстур (лесного массива, водоемов и т.д.) на изображении используется подход сравнения с эталоном. Таким образом, процедура классификации, в этом случае, сводится к разбиению тестового изображения на множество квадратных участков небольшого размера, построению для них гистограмм и их последующему сравнению с гистограммами, построенными для эталонных участков текстур такого же размера. Такой метод последовательного сравнения гистограммы эталона с гистограммой «окна» – прямоугольной области, захватывающей часть тестового изображения, и сдвигающейся по всему этому изображению, называется методом «скользящего окна». Его недостаток заключается в том, 9

что при сравнении эталона с участком, на котором помимо искомого объекта есть что-то еще, скорее всего, метод сработает неправильно из-за искажения гистограммы. Недостаток можно исправить путем добавления в систему детектора границ, отслеживающего однородные блоки текстур, однако, в данной работе это не рассматривается ввиду работы с более крупным масштабом изображений, т.е. несущественности суммарной ошибки. Еще одной особенностью данного метода является достаточно высокая чувствительность к выбору количества бинов (при малом количестве различия будут критично несущественны, при большом количестве будет неестественно высокая уникальность каждого участка текстуры), поэтому важно эмпирическим путем отыскать оптимальные количества. Поскольку цвет является одной из важных особенностей для каждой из текстур, присутствующих на большинстве изображений поверхностей Земли, то гистограммы имеет смысл вычислять именно для цветных изображений. В предыдущем подпараграфе был кратко рассмотрен подход к построению гистограмм для цветных изображений. Однако, в силу ряда причин, гистограммы желательно строить для изображений в HSV-модели (а не RGB), координатами которой являются цветовой тон, насыщенность и значение цвета (англ. Hue, Saturation, Value). Эта модель является нелинейным преобразованием модели RGB. Одними из причин, по которым используется именно HSV-модель, являются более высокая (чем в модели RGB) инвариантность к степени освещенности, устойчивость к затенению, более удобная с программной точки зрения эквализация и нормализация гистограмм, наконец, естественность координат модели для восприятия человеком. 10

1.1.3 Методы сравнения гистограмм Замечание. Перед тем, как сравнивать, гистограммы требуется нормализовать, т.е. сумма значений бинов должна равняться единице. Все методы вычисляют некое «расстояние», или уровень сходства между гистограммами – распределениями пикселей. Обозначения: 𝐻1(𝑖) – значение функции распределения в i-м бине; ̅1 – среднее по распределению; 𝐻 Рассмотрим 4 основных метода сравнения гистограмм: 1. Корреляционный метод, где d(𝐻1, 𝐻2 ) находится в интервале [-1; 1], в котором нижняя и верхняя граница определяют максимальную степень соответствия. 𝑑 (𝐻1 , 𝐻2 ) = Ноль означает отсутствие корреляции; ̅1)(𝐻2 (𝑖) − 𝐻 ̅2 ) ∑𝑖(𝐻1(𝑖) − 𝐻 ̅1)2 ∗ (𝐻2 (𝑖) − 𝐻 ̅2 )2 √∑𝑖 (𝐻1(𝑖) − 𝐻 2. Метод «Хи-квадрат», где d(𝐻1, 𝐻2 ) находится в интервале [0; +∞), а ноль означает максимальную степень соответствия, в то время как степень минимального соответствия обусловлена количеством бинов; (𝐻1 (𝑖) − 𝐻2 (𝑖))2 𝑑(𝐻1, 𝐻2) = ∑ 𝐻1(𝑖) 𝑖 3. Метод пересечения гистограмм, где d(𝐻1, 𝐻2 ) находится в интервале [0; 1], в котором нижняя граница определяет минимальную степень соответствия, а верхняя – максимальную; 𝑑(𝐻1, 𝐻2) = ∑ min(𝐻1(𝑖), 𝐻2 (𝑖)) 𝑖 11

4. Метод «Расстояние интервале [0; 1], Бхаттачарья», где d(𝐻1, 𝐻2 ) находится в в котором нижняя граница определяет максимальную степень соответствия, а верхняя – минимальную. 𝑑(𝐻1 , 𝐻2 ) = √1 − ∑ 𝑖 √𝐻1 (𝑖) ∗ 𝐻2 (𝑖) √∑𝑖 𝐻1(𝑖) ∗ ∑𝑖 𝐻2(𝑖) В силу того, что в методе «Хи-квадрат» степень минимального соответствия обусловлена, его использование в программной реализации является не вполне оправданным, поэтому было принято решение от него отказаться. 1.2 Метод опорных векторов В этом параграфе рассматривается метод опорных векторов, в англоязычных источниках также известном, как Support Vector Machine (SVM). Также предлагаются некоторые дополнения, необходимые для применения метода в задачах классификации изображений. 1.2.1 Метод опорных векторов для случая линейной разделимости Метод опорных векторов – это метод, который в теории машинного обучения рассматривается как метод обучения с учителем. Это означает, что перед тем как система, основанная на методе, допускается к распознаванию тестовых данных, ее «тренируют» при помощи обучающей выборки, то есть подают на вход системе множество примеров и соответствующих им ответов, после чего она выстраивает зависимость между ними и далее способна прогнозировать ответы уже для тестовых данных. Метод относится к категории дискриминативных линейных классификаторов. Первое означает, что для его работы не имеет значения, как были сгенерированы данные, а второе – что классификатор принимает решения на основе значения линейной комбинации характеристик 12 объектов, называемых также

признаками, которые в машинном представлении хранятся в векторах, называемых векторами особенностей, или векторами признаков. Иными словами, метод строит линейную разделяющую поверхность (если имеются два класса, поверхность называется разделяющей гиперплоскостью). Метод опорных векторов в случае, если обучающие данные линейно разделимы, осуществляется следующим образом: дано множество точек, принадлежащих к одному из двух классов, классификатор находит оптимальную гиперплоскость, оставляющую наибольшее количество точек одного класса с одной стороны, второго класса – с другой, причем расстояние от гиперплоскости до точек каждого из классов максимизируется. Рис. 2. Разделяющие гиперплоскости, справа – оптимальная На рисунке 2 можно видеть две гиперплоскости, каждая из которых правильно разделяет множества точек на два класса, но только правая гиперплоскость является оптимальной, так как максимизирует зазор (margin) между параллельными гиперплоскостями, касающимися точек. Величина зазора и ошибка классификатора связаны между собой обратно пропорционально. Формальная постановка задачи построения линейного классификатора по методу SVM. Имеются обучающие данные из n точек (𝑥⃗1, 𝑦1 ), … , (𝑥⃗𝑛 , 𝑦𝑛 ), где 𝑦𝑖 может быть равным 1 или −1, указывая на класс, которому принадлежит одна из точек 𝑥⃗𝑖 , из которых состоит вещественный вектор с 13

размерностью, равной p. Нужно отыскать оптимальную гиперплоскость, разделяющую множество точек, для которых 𝑦𝑖 = 1 и множество точек, для которых 𝑦𝑖 = −1, причем расстояние от нее до ближайших точек из обоих классов должно быть максимальным. Гиперплоскость может быть выражена следующим уравнением: 𝑤 ⃗⃗⃗ ∙ 𝑥⃗ − 𝑏 = 0, где вектор 𝑤 ⃗⃗⃗ – нормальный вектор к гиперплоскости, а величина 𝑏 ‖𝑤 ⃗⃗⃗‖ – расстояние от гиперплоскости до начала координат. В случае линейной разделимости обучающих данных можно построить две параллельные гиперплоскости, с наибольшим зазором разделяющие данные. Оптимальная гиперплоскость параллельна им и лежит посередине между ними. Эти две гиперплоскости можно описать следующими уравнениями: 𝑤 ⃗⃗⃗ ∙ 𝑥⃗ − 𝑏 = 1 и 𝑤 ⃗⃗⃗ ∙ 𝑥⃗ − 𝑏 = −1. Соответственно, гиперплоскостями равно расстояние 2 между касающимися данных , то есть для его максимизации нужно ‖𝑤 ⃗⃗⃗‖ минимизировать знаменатель. Для того чтобы не допустить попадания точек в зазор, нужно добавить следующее ограничение, тогда каждая из точек будет лежать на правильной стороне относительно гиперплоскости: 𝑤 ⃗⃗⃗ ∙ ⃗⃗⃗⃗ 𝑥𝑖 − 𝑏 ≥ 1, если 𝑦𝑖 = 1 или 𝑤 ⃗⃗⃗ ∙ 𝑥 ⃗⃗⃗⃗𝑖 − 𝑏 ≤ −1, если 𝑦𝑖 = −1. Объединяя эти ограничения, можно выразить их следующим образом: 𝑦𝑖 (𝑤 ⃗⃗⃗ ∙ 𝑥 ⃗⃗⃗⃗𝑖 − 𝑏) ≥ 1, для всех 1 ≤ 𝑖 ≤ 𝑛. (1) Теперь требования максимизации зазора между гиперплоскостями и нахождения точек в своих классах можно выразить через постановку задачи оптимизации: Минимизировать ‖𝑤 ⃗⃗⃗‖ при условии 𝑦𝑖 (𝑤 ⃗⃗⃗ ∙ ⃗⃗⃗⃗ 𝑥𝑖 − 𝑏) ≥ 1, 𝑖 = 1, … , 𝑛 𝑤 ⃗⃗⃗ и 𝑏, решающие задачу, определяют классификатор 𝑥⃗ ⟼ 𝑠𝑖𝑔𝑛(𝑤 ⃗⃗⃗ ∙ ⃗⃗⃗⃗ 𝑥𝑖 − 𝑏). 14

Важно заметить, что оптимальная гиперплоскость полностью определяется теми точками ⃗⃗⃗⃗, 𝑥𝑖 которые лежат к ней ближе всего. Точки 𝑥 ⃗⃗⃗⃗𝑖 называются опорными векторами. 1.2.2 Метод опорных векторов для случая линейной неразделимости В этом подпараграфе проведено обобщение метода на случай, если обучающие данные линейно неразделимы, так как большинство приложений, в которых используется SVM, требуют более мощный инструмент, нежели линейный классификатор, так как в подобных задачах обучающие данные редко можно разделить гиперплоскостью. Это связано в том числе с тем, что для обучения SVM необходимо загружать сложную совокупность позитивных и негативных примеров распознавания, а в этом случае может оказаться невозможно линейно отделить их друг от друга. В случае линейной неразделимости в методе делается допущение, что некоторые из точек будут классифицированы неверно. Величина ошибочной классификации вводится как отдельная переменная в задачу оптимизации. Соответственно, задача может быть переформулирована как поиск разделяющей гиперплоскости с максимальным зазором при минимуме ошибок классификации. Рассмотрим функцию потерь: max(0, 1 − 𝑦𝑖 (𝑤 ⃗⃗⃗ ∙ 𝑥 ⃗⃗⃗⃗𝑖 − 𝑏)). Она равна нулю в том случае, если выполнено ограничение (1) из предыдущего подпараграфа, то есть все 𝑥 ⃗⃗⃗⃗𝑖 лежат на правильных сторонах относительно гиперплоскости, для остальных же ⃗⃗⃗⃗ 𝑥𝑖 значения функции будут пропорциональны расстоянию от зазора. Тогда нужно минимизировать 1 [ ∑𝑛𝑖=1 max (0, 1 − 𝑦𝑖 (𝑤 ⃗⃗⃗ ∙ ⃗⃗⃗⃗ 𝑥𝑖 − 𝑏))] + 𝜆‖𝑤 ⃗⃗⃗‖2, 𝑛 где 𝜆 определяет компромисс между увеличением зазора и гарантией того, что точки ⃗⃗⃗⃗ 𝑥𝑖 будут классифицированы верно. Эту минимизацию можно 15

переписать в виде оптимизационной задачи с ограничениями и дифференцируемой целевой функцией следующим образом: Для каждого 𝑖 ∈ {1, … , 𝑛} нужно ввести переменную, равную 𝜉𝑖 = max (0, 1 − 𝑦𝑖 (𝑤 ⃗⃗⃗ ∙ ⃗⃗⃗⃗ 𝑥𝑖 − 𝑏)) тогда и только тогда, когда 𝜉𝑖 – наименьшее неотрицательное число, удовлетворяющее неравенству 𝑦𝑖 (𝑤 ∙ 𝑥𝑖 + 𝑏) ≥ 1 − 𝜉𝑖 . Замечание. Геометрический смысл переменных 𝜉𝑖 в том, что каждая из них обозначает расстояние от точки данных до правильной области решения. Если точка уже находится в этой области, то переменная равна нулю. Таким образом, оптимизационную задачу можно представить в виде: minimize 1 𝑛 ∑𝑛𝑖=1 𝜉𝑖 + 𝜆‖𝑤 ⃗⃗⃗‖2, при условии, что 𝑦𝑖 (𝑥𝑖 ∙ 𝑤 + 𝑏) ≥ 1 − 𝜉𝑖 и 𝜉𝑖 ≥ 0 для всех 𝑖. Метод опорных векторов способен эффективно решать задачу нелинейной классификации, используя способ, который называется в англоязычных источниках “kernel trick”, при этом происходит неявное отображение данных в пространство признаков большей размерности, в предположении, что там данные будут линейно разделимы. Идея способа заключается в том, что вместо скалярного произведения точек теперь используется нелинейная функция ядра, фактически выполняющая ту же роль, только в пространстве большей размерности. Функция, отвечающая оптимальной решающей функции в первоначальном пространстве, будет нелинейной в силу нелинейности ее отображения в пространство большей размерности. Некоторые часто используемые ядра (в скобках – обозначения в библиотеке OpenCV):  Полиномиальное (однородное) (POLY): 𝑑 𝑘(𝑥 ⃗⃗⃗⃗, ⃗⃗⃗⃗) ⃗⃗⃗⃗𝑖 ∙ 𝑥 ⃗⃗⃗⃗) 𝑖 𝑥 𝑗 = (𝑥 𝑗 16

 Полиномиальное (неоднородное) (POLY): 𝑘(𝑥 ⃗⃗⃗⃗,𝑖 ⃗⃗⃗⃗) 𝑥𝑗 = (𝑥 ⃗⃗⃗⃗𝑖 ∙ 𝑥 ⃗⃗⃗⃗𝑗 + 1)𝑑  Гауссовская радиальная базисная функция (RBF): 2 𝑥𝑗 ) 𝑖 ⃗⃗⃗⃗⃗‖ 𝑘(𝑥 ⃗⃗⃗⃗, 𝑥𝑗 = 𝑒 (−𝛾‖𝑥⃗⃗⃗⃗− , для 𝛾 > 0; 𝑖 ⃗⃗⃗⃗) может использоваться параметр 𝛾 = 1⁄2𝜎 2  Гиперболический тангенс (SIGMOID): 𝑘(𝑥 ⃗⃗⃗⃗, ⃗⃗⃗⃗) ⃗⃗⃗⃗𝑖 ∙ ⃗⃗⃗⃗ 𝑥𝑗 + 𝑐), 𝑖 𝑥 𝑗 = tanh(𝛾𝑥 для некоторых (не всяких) 𝛾 > 0 и 𝑐 < 0 Ядро связано с преобразованием 𝜑(𝑥 ⃗⃗⃗⃗𝑖 ) уравнением 𝑘(𝑥 ⃗⃗⃗⃗, ⃗⃗⃗⃗) 𝑥𝑖 ) ∙ 𝜑(𝑥 ⃗⃗⃗⃗). 𝑖 𝑥 𝑗 = 𝜑 (⃗⃗⃗⃗ 𝑗 Величина 𝑤 в преобразованном пространстве 𝑤 ⃗⃗⃗ = ∑𝑖 𝛼𝑖 𝑦𝑖 𝜑(𝑥 ⃗⃗⃗⃗𝑖 ). Произведения данных с этой величиной могут быть вычислены с помощью “kernel trick”: 𝑤 ⃗⃗⃗ ∙ 𝜑(𝑥⃗ ) = ∑ 𝛼𝑖 𝑦𝑖 𝑘 (⃗⃗⃗⃗, 𝑥𝑖 𝑥⃗ ). 𝑖 17

Глава 2. Реализация методов В этой главе содержится обоснование выбора программных средств, используемых при реализации описанных выше методов, а также их краткий обзор. Помимо этого, глава содержит сведения о способе реализации систем распознавания, специфические детали, модификации. 2.1 Обзор инструментария На данный момент существует довольно небольшое количество возможных путей программной реализации задач, относящихся к области распознавания и классификации изображений, в силу малого количества библиотек, связанных именно с компьютерным зрением. Для выполнения этой работы была выбрана библиотека OpenCV. Среди ее преимуществ можно отметить следующие:  OpenCV имеет BSD лицензию, а это значит, ее можно свободное использовать как в академических, так и в коммерческих продуктах;  OpenCV содержит большое количество модулей и алгоритмов, в том числе SVM и широкие возможности для работы с гистограммами;  Поддержка многих языков программирования, платформ и операционных систем;  Высокая популярность и большая поддержка – обширная документация, туториалы, интернет-поддержка, что особенно важно для начинающих разработчиков. Разработка с использованием графической библиотеки OpenCV возможна на нескольких языках программирования, среди которых C, C++, Python, Java, MATLAB [10]. Для программной реализации был выбран C++ по следующим причинам:  высокая производительность; 18

 содержательная OpenCV-документация;  широкая поддержка конкретно связки OpenCV – C++ – большое сообщество разработчиков, множество примеров реализаций в литературе и интернет-источниках. Для разработки систем классификации использовались следующие программные продукты:  Графическая библиотека OpenCV версии 3.0.0;  Интегрированная среда разработки Microsoft Visual Studio Community 2015. 2.2 Обзор программной реализации 2.2.1 Метод сравнения гистограмм Известно, что при сравнении гистограмм необходимо загрузить тестовое изображение и эталонные распознаваемых классов в цвете. участки изображений текстур При сравнении используется так называемое «скользящее окно», при этом последовательно сравниваются гистограммы эталона и такого же по размеру элемента тестового изображения. Так выглядит функция, в которой реализована концепция «скользящего окна»: int rshift = 0, dshift = 0; for (int i = 0; i < c_cols; i++) { for (int j = 0; j < c_rows; j++) { Rect r(0 + rshift, 0 + dshift, side, side); Mat copy = test; Mat crop = copy(r); if (hist_comparison(etalon, crop)) test(r) += CV_RGB(0, 0, 255); 19

dshift += side; if (j == c_rows - 1) dshift = 0; } rshift += side; } Приведем подробное описание реализации метода сравнения: 1. Сначала необходимо преобразовать два квадратных участка (эталон и такая же часть исходного изображения, например, размером 20х20 пикселей): Mat hsv_etalon, hsv_test_crop; cvtColor(etalon, hsv_etalon, COLOR_BGR2HSV); cvtColor(test_crop, hsv_test_crop, COLOR_BGR2HSV); 2. Затем необходимо задать количество бинов для канала тона и насыщенности, диапазоны их изменения (H, S), и количество каналов: int h_bins = 10; int s_bins = 60; int histSize[] = { h_bins, s_bins }; float h_ranges[] = { 0, 180 }; float s_ranges[] = { 0, 256 }; const float* ranges[] = { h_ranges, s_ranges }; int channels[] = { 0, 1 }; 3. Далее необходимо создать матрицы для хранения гистограмм и вызвать функции вычисления равномерность и гистограмм отсутствие (последние накопления два данных), аргумента после – чего нормализовать гистограммы (здесь 0 и 1 – нижняя и верхняя границы нормализации диапазона соответственно, 5-й аргумент указывает на способ нормализации внутренних значений, 6-й на то, что выходные данные будут иметь тот же тип, последний – тип маски): Mat hist_etalon; Mat hist_test_crop; calcHist(&hsv_etalon, 1, channels, Mat(), hist_etalon, 2, histSize, ranges, true, false); 20

normalize(hist_etalon, hist_etalon, 0, 1, NORM_MINMAX, -1, Mat()); calcHist(&hsv_test_crop, 1, channels, Mat(), hist_test_crop, 2, histSize, ranges, true, false); normalize(hist_test_crop, hist_test_crop, 0, 1, NORM_MINMAX, -1, Mat()); 4. Наконец, подготовленные данных выгружаются в библиотечную функцию сравнения гистограмм compareHist, последний ее аргумент указывает на метод сравнения гистограмм (в данном случае – пересечение). Далее устанавливается допустимый порог, отвечающий за требовательность к совпадению гистограмм. Функция сравнения паттернов – булева, в случае удовлетворительного результата сравнения возвращает true. double test = compareHist(hist_etalon, hist_test_crop, CV_COMP_INTERSECT); double match_percent = 0.35; if (test >= match_percent) return 1; else return 0; 2.2.2 SVM Стоит отметить, что при реализации метода опорных векторов существуют несколько потенциальных недостатков, среди которых:  необходимость полной маркировки обучающих данных  применимость только для двух классов  затруднительность интерпретации параметров решаемой модели и их подбора для наилучшей классификации В реализации метода SVM важной частью задачи является подготовка обучающих данных. Далее прилагается пример загрузки данных в SVM в случае, когда размер квадрата равен 15х15 пикселей, соответственно, размер 21

обучающей выборки составит 2 ∙ 88 ∙ 43 = 7568 (при размере изображения, равном 1334х645, на котором помещается выборка). Замечание. Данные в SVM загружаются в виде изображений в градациях серого, то есть распознающий алгоритм использует больше информацию о текстуре, нежели информацию о цветовой составляющей. Таким образом, процедура загрузки данных существенно ускоряется. Ниже приведен пример заполнения половины обучающей выборки, которая сначала выгружается из изображения в двумерный массив матрицизображений 15х15, откуда извлекается для загрузки в SVM-модель. Предварительно создается контейнер под всю выборку, последовательно заполняется половина выборки, содержащая «позитивные» примеры, таким же образом заполняется вторая половина, содержащая «негативные» примеры. Замечание. SVM-модель OpenCV требует загрузки данных следующим образом – все обучающие примеры, в данном случае, изображения 15х15, необходимо «развернуть» построчно, таким образом, в общем контейнере каждая строка будет содержать один обучающий пример-изображение. То есть вектором особенностей в данном случае будет вектор-строка, содержащая цифровое представление изображения участка текстуры. int file_num = 0, column = 0; for (int k = 0; k < my_cols; k++) { for (int l = 0; l < my_rows; l++) { for (int i = 0; i < side; i++) for (int j = 0; j < side; j++) training_mat.at<uchar>(file_num, column++) = arr_positive_sample[k][l].at<uchar>(i, j); file_num++; column = 0; } } Затем каждую строку, загруженную в большой контейнер, необходимо «пометить» либо 1, либо –1, поместив, таким образом, 22

обучающее изображение в один из двух классов. Для этого создается одностолбцовая матрица с количеством строк, равным количеству строк в большом контейнере. Mat labelsMat(num_files, 1, CV_32SC1); for (int i = 0; i < num_files; i++) if (i < border) labelsMat.at<int>(i, 0) = 1; else labelsMat.at<int>(i, 0) = -1; После этого устанавливаются необходимые параметры модели SVM, загружаются обучающие данные. Сначала выбирается тип модели с возможностью выбора параметра C (в предыдущей главе был обозначен как 𝜆), отвечающего за штрафы при неправильной классификации. Далее выбираются параметр С, тип ядра, параметры 𝛾, степень и коэффициент, которые имеют значение, если выбранный тип ядра использует их. Параметр Termination Criteria отвечает за ручную установку максимального числа итераций (это необходимо, чтобы регулировать точность нелинейной классификации), а так же ошибки допуска. Последняя строка запускает процесс обучения с указанной обучающей выборкой и метками. Ptr<SVM> svm = SVM::create(); svm->setType(SVM::C_SVC); svm->setC(0.3); svm->setKernel(SVM::RBF); svm->setGamma(0.0003); svm->setDegree(2); svm->setCoef0(0); svm->setTermCriteria(TermCriteria(TermCriteria::MAX_ITER + TermCriteria::EPS, 1000, 1e-4)); svm->train(trainingDataMat, ROW_SAMPLE, labelsMat); После проведения обучения программа проходит все изображение «скользящим окном» и, получая ответы 1 или –1, закрашивает искомую текстуру. Запрашивая у обученной системы отклик, необходимо так же «разворачивать» изображение в строку. 23

int rshift = 0, dshift = 0; for (int i = 0; i < my_cols; i++) { for (int j = 0; j < my_rows; j++) { Rect r(0 + rshift, 0 + dshift, side, side); Mat crop = image(r); Mat copy(1, img_area, CV_32F); int column = 0; for (int i = 0; i < side; i++) { for (int j = 0; j < side; j++) { copy.at<float>(0, column++) = crop.at<uchar>(i, j); } } float response = svm->predict(copy); if (response == 1) image_c(r) += CV_RGB(0, 200, 0); else if (response == -1) image_c(r) += CV_RGB(200, 0, 0); dshift += side; if (j == my_rows - 1) dshift = 0; } rshift += side; } 24

Глава 3. Тестирование систем В этой главе рассмотрены результаты работы реализованных систем при изменении различных параметров. Конфигурация компьютера: Процессор: Intel Pentium CPU B980 2.40GHz x64 ОЗУ: 4 Gb DDR3 ОС: Windows 10 x64 Тесты проводились без применения аппаратного ускорения расчетов на GPU 3.1 Тестирование методов сравнения гистограмм В этом параграфе проведено тестирование трех методов сравнения гистограмм – корреляции, пересечения и метода расстояния Бхаттачарья, и выбран лучший, исходя из оптимальности сочетания тройки качествоскорость-стабильность. Тесты проводились на четырех изображениях размером 1320х645 пикселей, с различным содержанием, на примере распознавания лесных массивов. Количество бинов зафиксировано – h_bins = 5; s_bins = 60. При сравнении каждого участка размером 15х15 пикселей будет происходить сравнение гистограмм тестового участка и 9 примеров данного класса, при этом алгоритм оптимизирован таким образом, что при разовом закрашивании участка происходит выход из проверки оставшихся примеров. Качество измеряется количеством штрафных участков, которое составляет сумму из неправильно распознанных и не распознанных правильно участков. Для каждого метода порог распознавания устанавливается отдельно. 25

Таблица 1. Время обработки изображения (с/изображение 1320х645) Номер изображения 1 Метод пересечения 3.185 Метод корреляции 3.854 Расстояние Бхаттачарья 3.076 2 4.294 3.629 4.054 3 4.549 4.563 4.952 4 5.641 6.018 6.376 Таблица 2. Качество обработки изображения (количество штрафных баллов) Номер изображения 1 Метод пересечения 80 Метод корреляции 30 Расстояние Бхаттачарья 30 2 400 400 700 3 350 300 250 4 200 50 50 По результатам эксперимента можно сделать вывод, что лучшим является метод корреляции, так как он наиболее стабилен, а также является более быстрым методом, по сравнению с аналогичным по качеству «расстоянием Бхаттачарья». 3.2 Тестирование SVM В этом параграфе предлагается, подобно предыдущему параграфу, зафиксировать остальные параметры в некоем стабильном состоянии и провести сравнение ядер. Эмпирическим путем было выяснено, что в качестве рабочих ядер для данной задачи можно использовать радиальную базисную функцию (RBF), ядро «Хи-квадрат» (CHI2) и ядро пересечения гистограмм (INTER). Параметры ядер на протяжении эксперимента 26

подобраны примерно оптимально. Тесты проводились на тех же данных, что и в предыдущем параграфе. Таблица 3. Время обработки изображения (с/изображение 1320х645) Номер изображения 1 RBF CHI2 INTER 3.595 17.375 3.760 2 3.672 16.398 3.734 3 3.561 17.682 3.554 4 3.600 20.224 3.772 Таблица 4. Качество обработки изображения (количество штрафных баллов) Номер изображения 1 RBF CHI2 INTER 150 >>1000 400 2 200 >>1000 1000 3 700 >>1000 >>1000 4 150 >>1000 400 По результатам эксперимента можно сделать вывод, что наилучшим ядром для решения поставленной задачи оказалось ядро RBF, что подтверждает информацию в документации OpenCV, где говорится о том, что это ядро подходит во многих случаях. Остальные же ядра показали либо очень плохое время и результаты (CHI2), либо высокую нестабильность применительно к поставленной задаче. Качественный результат распознавания изображения 2, где результат, полученный с помощью гистограмм, был неудовлетворительным, связан с качественным распознаванием форм объекта. 27

3.3 Сравнительное тестирование метода пересечения гистограмм и SVM с ядром RBF В этом параграфе проведено сравнительное тестирование хорошо зарекомендовавших себя методов – метода пересечения гистограмм и метода опорных векторов, производящем переход в пространство большей размерности при помощи ядра RBF. Теперь методы распознают другой класс объектов – водоемы. Условия те же, что и в предыдущих параграфах, помимо корректировки некоторых параметров – порога в методе пересечения гистограмм и параметров 𝛾 и 𝐶 в методе опорных векторов. Изображения другие, нежели в предыдущих методах. Таблица 5. Время обработки изображения (с/изображение 1320х645) Номер изображения 1 Метод пересечения гистограмм 6.417 Метод опорных векторов 2.448 2 5.217 2.827 3 5.428 2.376 4 6.937 2.323 Таблица 2. Качество обработки изображения (количество штрафных баллов) Номер изображения 1 Метод пересечения гистограмм 50 Метод опорных векторов 15 2 300 300 3 400 30 4 20 25 На основе тестовых данных можно заключить, что метод опорных векторов более стабилен, быстр и работает более качественно, что же касается метода пересечения гистограмм, его имеет смысл использовать 28

только как дополнительный метод в комплексной системе, без перебора выборочных данных, так как это замедляет работу системы и не дает качественных результатов, так как существует большая зависимость между ними и выборкой. 3.4 Влияние различных параметров на качество распознавания 3.4.1 Параметры метода опорных векторов Стоит заметить, что метод SVM можно использовать в режиме одинпротив-одного, когда все изображение распознается либо как один, либо как другой класс, однако данный режим практически не применим в реальных системах, так как работает только на изображениях, где присутствуют только два этих класса. Поэтому гораздо более предпочтителен режим один-противвсех и создание негативной выборки для каждого класса. Негативная выборка является важнейшим аспектом системы SVM и ее правильный подбор может оказать колоссальное влияние на качество распознавания, при этом крайне важно учитывать соответствие масштаба выборки и тестовых изображений. Фактически, обучение системы, создание выборок определяет качество распознавания. В методе SVM большая длительность обучения не сильно влияет на результат, т.е., после определенного порога с ростом времени обучения качество распознавания существенно не увеличивается. Что касается других классов, то, например, водные объекты SVM распознает достаточно точно и быстро, это связано с тем, что текстура воды достаточно проста, практически без особенностей, поэтому этот вид объектов не так чувствителен к подбору негативной выборки. Если брать более крупный размер участков, например 25х25, то, разумеется, распознавание более крупных, природных объектов будет более успешным и быстрым, но, например, в городах такой размер участка неприменим, в отсутствие в комплексной системе детектора границ. Это 29

замечание справедливо и для размера 15х15. На рисунках 3 и 4 приведены примеры распознавания лесных массивов в городе и природной среде. Рис. 3. Распознавание в городе Рис. 4. Распознавание в природной среде Соответственно, при более мелком (менее 10х10) размере участков, SVM не сможет уловить закономерности текстуры, распознавание будет более хаотическим, зашумленным. 3.4.2 Параметры метода сравнения гистограмм В методе сравнения гистограмм в основном на качество распознавания влияет количество бинов канала Hue и порог распознавания. Правильный подбор этих параметров может немного улучшить качество и скорость распознавания и сделать метод пригодным в качестве использования в комплексной системе. 30

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

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

Список литературы 1. Шовенгердт Р.А. Дистанционное зондирование. Модели и методы обработки изображений. М.: Техносфера, 2010. 560 с. 2. Шитова О. В., Пухляк А. Н., Дроб Е. М. Анализ методов сегментации текстурных областей изображений в системах обработки изображений // Научные ведомости Белгородского государственного университета. Серия: Экономика. Информатика. 2014. №8-1 (179). URL: http://cyberleninka.ru/article/n/analiz-metodov-segmentatsii-teksturnyhoblastey-izobrazheniy-v-sistemah-obrabotki-izobrazheniy (дата обращения: 10.05.2016). 3. Мурзин Ф.А., Половинко О.Н., Лобив И.В. Распознавание текстур по пространственным закономерностям // Материалы междунар. конф. Новые информационные технологии в науке и образовании. Новосибирск, 2003. С. 256-268. 4. Воронцов К.В. Машинное обучение. Курс лекций // 2004 5. Хайкин С. Нейронные сети. Полный курс // 2006 6. Bradski G., Kaehler A. Learning OpenCV. Computer Vision with the OpenCV Library // O’Reilly // 2008 7. OpenCV 3.0.0 Documentation. http://docs.opencv.org/3.0.0/ 8. Лабутина И.А. Дешифрирование аэрокосмических снимков. М.: АСПЕКТ ПРЕСС, 2004. 184 с. 9. A Practical Guide to Support Vector Classification. http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf (дата обращения: 14.04.2016). 10. OpenCV (C++ vs Python) vs MATLAB for Computer Vision. http://www.learnopencv.com/opencv-c-vs-python-vs-matlab-for-computervision/ (дата обращения: 33 17.02.2016).

Рецензии:

Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Отзывы:

Авторизуйтесь, чтобы оставить отзыв