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

На правах рукописи

оиэм—-

БАРСУК Алексей Александрович

РАЗРАБОТКА МЕТОДА И ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ АВТОМАТИЧЕСКОЙ ВАРИАЦИОННОЙ КЛАССИФИКАЦИИ ОБЪЕКТОВ НА ИЗОБРАЖЕНИЯХ ЗЕМНОЙ ПОВЕРХНОСТИ

Специальность 05.13.01 - системный анализ, управление и обработка информации (в науке и технике)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

г 1 МАР 2013

Белгород-2013

005050841

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего профессионального образования «Белгородский государственный национальный исследовательский университет», на факультете компьютерных наук и телекоммуникаций, кафедре информационно-телекоммуникационных систем и технологий

Научный руководитель Жиляков Евгений Георгиевич,

доктор технических наук, профессор

Официальные оппоненты: Ломазов Вадим Александрович,

доктор физико-математических наук, доцент, Белгородская государственная сельскохозяйственная академии им. В.Я. Горина, профессор кафедры информатики и информационных технологий

Томакова Римма Александровна,

кандидат технических наук, доцент, Юго-Западный государственный университет, доцент кафедры биомедицинской инженерии, г.Курск

Ведущая организация Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Государственный университет — учебно-научно-производственный комплекс», г. Орел

Защита состоится 3 апреля 2013 года в 15 часов 00 минут на заседании диссертационного совета Д 212.015.10 на базе ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет», по адресу: 308015 г. Белгород, ул. Победы, 85, корп. 15, ауд. 3-8.

С диссертацией можно ознакомиться в научной библиотеке ФГАОУ ВПО «Белгородский государственный национальный исследовательский университет», по адресу: 308015 г. Белгород, ул. Победы, 85.

Автореферат разослан «_»_2013 г.

Ученый секретарь диссертационного совета кандидат технических наук, старший научный сотрудник

Белов С.П.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Среди существующих современных программных реализаций автоматической классификации объектов на спутниковых фотографиях земной поверхности следует выделить программный комплекс ENVI, в котором реализованы два алгоритма кластеризации, а именно ISODATA (ИСОМАД) и K-Means (К-внутригрупповых средних). Следует отметить, что результаты, получаемые при использовании упомянутых алгоритмов, не всегда совпадают с интуитивными представлениями экспертов об адекватности разбиения.

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

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

Важной особенностью классификации объектов на космофотоснимках земной поверхности является тот факт, что объемы обрабатываемой информации могут быть очень велики, так как количество возможных разбиений исходного множества пикселей на классы составляет В(Ы*М), где В — число Белла1, а М и N — ширина и высота изображения в пикселях, что для изображения 50 на 50 пикселей составляет около 105638. При этом получаемые разбиения должны быть оценены с точки зрения некоторого критерия, основанного на интегральной мере однородности. Это приводит к необходимости применения высокопроизводительных вычислительных систем.

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

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

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

Для достижения поставленной цели были сформулированы и решены следующие задачи.

1. Разработка функционала (критерия) качества автоматической классификации объектов на цифровых ИЗП как интегральной меры однородности получаемых разбиений пикселей на классы.

1 Липский, В. Комбинаторика для программистов [Текст] / В. Липский. - М.:Мир, 1988.-200 с.

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

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

4. Сравнительная оценка адекватности предлагаемого метода автоматической вариационной классификации.

Объект исследований: методы анализа ИЗП.

Предмет исследования: вариационные методы классификации объектов на цифровых ИЗП.

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

Научную новизну работы составляет следующее.

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

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

3. Параллельные алгоритмы принятия решений при классификации:

• алгоритм предварительной классификации;

• алгоритм построения минимального Евклидова дерева векторов признаков;

• алгоритм разрезания и обхода минимального Евклидова дерева;

• алгоритм определения максимума функционала качества классификации.

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

Полученные результаты также используются при проведении НИР и ОКР ООО «НПП «Энергетические и информационные технологии», что подтверждается соответствующим актом, а также в учебном процессе магистрантов факультета КНиТ НИУ «БелГУ».

Связь с научными и инновационными программами.

Результаты диссертационного исследования были использованы в рамках выполнения следующих НИР:

- ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, госконтракт № 14.740.11.0690 от 12 октября 2010;

- ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013, госконтракт № 14.740.11.0390 от 20 сентября 2010;

- грант РФФИ №12-07-00257-а;

- аналитическая ведомственная целевая программа (АВЦП) «Развитие научного потенциала высшей школы» в 2006-2008 гг., проект РНП.2.1.2.4974;

- АВЦП «Развитие научного потенциала высшей школы» в 20062008 гг., проект РНП.2.2.1.1.3121;

-АВЦП «Развитие научного потенциала высшей школы» на 20092010 гг., проект № 2.1.2/656;

-программа Фонда содействия развитию малых форм предприятий в научно-технической сфере «У.М.Н.И.К.», проект «Информационная технология вариационной классификации объектов на спутниковых фотографиях земной поверхности».

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

п.4. Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации;

п.5. Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации;

п. 12. Визуализация, трансформация и анализ информации на основе компьютерных методов обработки информации.

Положения, выносимые на защиту.

1. Метод вариационной автоматической классификации объектов на цифровых ИЗП на основе максимизации функционала качества как интегральной меры однородности получаемых результатов разбиений.

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

3. Программная реализация параллельных алгоритмов на основе технологий CUD А и ОрепМР.

4. Результаты сравнительной оценки адекватности предлагаемого метода автоматической вариационной классификации.

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

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

Апробация результатов диссертационного исследования. Результаты диссертационного исследования обсуждались на следующих научно-технических конференциях, выставках и конвентах: Международной молодежной конференции «Прикладная математика, управление и информатика», 2012, г. Белгород; Всероссийской молодежной конференции

«Теория и практика системного анализа», 2012, г. Белгород; Первой и Второй Международной научно-технической конференции «Компьютерные науки и технологии», 2011 и 2009, г. Белгород; Всероссийской выставке научно-технического творчества молодежи, 2010, г. Москва; Всероссийской выставке-конкурсе прикладных исследований, изобретений и инноваций, 2009, г. Саратов; Втором Всероссийском молодежном инновационном конвенте, 2009, г. С.-Петербург; Окружном инновационном конвенте , 2009, г. Дубна.

Публикации. По теме диссертационного исследования опубликовано 12 печатных работ (из них 6 в журналах из списка ВАК РФ), а также получено 3 Свидетельства Роспатента РФ о государственной регистрации программы для ЭВМ.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и приложений. Работа изложена на 150 страницах печатного текста, включая 80 рисунков, 27 таблиц и библиографический список из 113 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

В качестве основы для построения интегральных мер однородности используется предложенная Е.Г. Жиляковым и Е.М. Маматовым информационная мера в виде:

N

СП

где

х=(х1,...,х„) (2)

- вектор используемых признаков, компоненты которого удовлетворяют условиям

¿х, =1, х, > 0.

(3)

Легко показать, что выполняется неравенство

о<^(*)<1, (4)

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

max (Fix)) = 1,

то есть тогда и только тогда, когда

Минимальное же значение,

гш Р(х) = 0,

(5)

(6)

(7)

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

Проведенные в диссертации вычислительные эксперименты по исследованию меры (1) показали, что она обладает слабой изменчивостью в области своего максимума. Для оценки изменчивости был взят набор векторов вида х = (х„х2), таких что х2=1-х, , а х, е[0;1]. Ниже продемонстрирован график меры Г (рис. 1а) и ее производной (рис. 16). Анализ первой и второй производных меры (1) показал, что чувствительность тем ниже, чем выше однородность.

а б

Рис. 1. Графики меры х) (а) и ее производной (б)

Поэтому в качестве меры использовать:

однородности предлагается

Я(лг) = 1/

bi^

1 + -

In/V

а = 1 - е, 0 < е «1.

(8)

График меры (8) и ее производной приведены на рис. 2.

а б

Рис. 2. График меры Н(х) (а) и ее производной (б)

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

Глава 2. «Разработка метода автоматической вариационной классификации объектов на изображениях земной поверхности на основе принципа однородности разбиений».

Раздел 2.1. «Исследование свойств информационной меры однородности».

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

Раздел 2.2. «Разработка функционала качества разбиения на основе информационной меры однородности».

Пусть имеется набор объектов, характеризуемых векторами скалярных признаков У=(У1,—,Уь), где Ь — размерность векторов признакового пространства, которые разбиты на К непересекающихся классов, чьи признаки удовлетворяют условиям у <=Рч,ц = \,...,К\ Рч - соответствующие классам множества векторов, мощности которых равны МС1 (количество объектов в д-ом классе). Расстояние от /'-ого объекта д-ото класса до ближайшего соседа из этого же класса обозначим ) а сумму внутриклассовых расстояний д-ого класса положим й?.

кч = Еъ- (9)

1=1

Под расстоянием между объектами будем понимать определенное подходящим образом расстояние (например Евклидово) между соответствующими векторами их признаков.

Произведем нормировку внутриклассовых расстояний

(10)

В случае одинаковости расстояний (максимальной однородности) будет иметь место равенство

= Т' (Н)

а в общем случае будет выполняться

а,>о,|'А, = 1. (12)

Введем показатель 5ч

Mq-\

(13)

При идеальном разбиении все классы будут содержать одно и то же количество объектов, а соответственно, будут одинаковы для всех ц. Введем нормировочный множитель со:

(14)

Отметим, что соотношения

со

1=1

Г, ? = 1,2,3,..„А- (15)

учитывают однородность расстояний в соответствующих классах и количества составляющих их объектов. Поэтому функционал вида

У =-^-, , , , а = 1-е,0<£«1

Х + 06)

и !МК)

предлагается использовать в качестве комплексной интегральной меры однородности разбиений.

Раздел 2.3. «Особенности применения вариационного метода для классификации объектов при принятии решений в задаче анализа ИЗП».

Любое изображение состоит из пикселей, где пиксель есть вектор в и-мерном пространстве, где п < 3. Первые два признака описывают координату пикселя по осям абсцисс и ординат, а остальные п - 2 -интенсивности по каналам изображения. Если рассматривать широко

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

Pj =(x,y,r,g,b), i = \,2,..,MxN, (17)

где М и N — ширина и высота изображения в пикселях, х, у — координаты пикселя, r,g,b - значения цветовых интенсивностей по каналам красного, зеленого и синего. Таким образом, пиксель есть объект в пятимерном признаковом пространстве. Причем близкие по цвету и координатам пиксели будут образовывать скопления в признаковом пространстве. Если использовать только характеристики интенсивности r,g,b, то результатом классификации изображения будут классы, в которых пиксели близки друг к другу только в трехмерном цветовом пространстве. Координаты пикселей не будут влиять на результат классификации, то есть класс может представлять из себя множество несмежных пикселей и их групп. Чтобы произвести разделение генеральной совокупности объектов на непересекающиеся подмножества, используется подход, основанный на разрезании ребер Евклидова дерева, вершинами которого являются сами классифицируемые объекты.

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

На рис. 4 приведено изображение, которое было сгенерировано таким образом, что на нем присутствуют все возможные векторы интенсивностей (все цвета) в пространстве RGB. Также на изображении имеется две обширные области красного и зеленого цветов.

Рис. 3. Тестовое изображение и минимальное Евклидово дерево, построенное на его основе

Рис. 4. Изображение, содержащее все возможные цвета в пространстве RGB

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

Рис. 5. Минимальное остовное дерево, построенное на основе изображения 4

Рис. 6. Проекция 4-мерного остовного дерева, построенного на основе изображения 4

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

Рис. 7. Карта классификации изображения, содержащего все возможные цвета RGB, с использованием дополнительного признака

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

Глава 3. «Разработка параллельных алгоритмов классификации объектов на изображениях земной поверхности».

Раздел 3.1. «Особенности современных технологий программирования параллельных вычислений».

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

Раздел 3.2. «Параллельные алгоритмы определения максимума функционала».

Общая блок-схема разработанного алгоритма классификации приведена на рис. 8.

Рис. 8. Блок-схема алгоритма автоматической вариационной классификации объектов на ИЗП

Параллельный алгоритм предварительной классификации

используется для выделения на изображении множеств пикселей, описанных одинаковыми векторами интенсивностей. Результатом работы алгоритма является таблица объект-свойства (TOC), объекты в которой описаны четырьмя значениями: интенсивностями по красному, зеленому, синему каналам и количеством пикселей на изображении с соответствующими значениями интенсивностей. Каждой записи в TOC будет соответствовать некоторое множество пикселей. Для каждого пикселя, обладающего заданными цветовыми характеристиками, сохраняется информация о его соответствии объекту TOC.

На рис. 9 приведена блок-схема параллельного алгоритма предварительной классификации.

1. Исходное изображение

2. С„Сд,СЬ

Сг - количество уровней квантования для красного канала Сд - количество уровней квантования для зеленого канала Сь - количество уровней квантования для синего канала

Квантование пиксельных интенсивностей

Разбить пиксели на L групп

Обработка s L потоков

Формирование TOC

L - количество процессоров (ядер)

Строки ТОС - четырехмерные векторы (г.д.Ь.п). где:

г - интенсивность красного канала д - интенсивность зеленого канала " Ь - интенсивность синего канала п - количество пикселей на изображении с такими значениями интенсивностей

1.TOC

2. Карта предварительной классификации

Карта предварительной классификации содержит информацию о соответствии пикселя изображения некоторой строке TOC

Конец

Рис. 9. Блок-схема алгоритма предварительной классификации

Алгоритм предварительной классификации содержит в себе процедуру квантования по уровню. Квантование производится для уменьшения количества классов, получаемых в результате предварительной классификации. Используются два метода квантования. Равномерное квантование - такое квантование, при котором весь интервал значений интенсивности пикселя по одному из каналов [0;255] разбивается на равномерные интервалы, и адаптивное - когда используется интервал, ограниченный максимальным и минимальным значениями интенсивностей, присутствующими в канале изображения. Блок-схемы алгоритмов квантования приведены на рис. 10.

Параллельный алгоритм построения минимального Евклидова дерева является наиболее вычислительно сложным среди алгоритмов, реализующих метод вариационной классификации объектов на ИЗП. При его разработке были рассмотрены стандартные алгоритмы, используемые для решения задачи построения такого дерева, а именно, алгоритмы Крускала, Прима и Борувки2. В результате, было установлено, что наибольшим потенциальным параллелизмом обладает алгоритм Борувки. На его основе автором был разработан параллельный модифицированный алгоритм Борувки (ПМАБ).

2 Седжвик, Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах: пер. с англ. [Текст]/ Роберт Седжвик. - СПб.: ООО «ДиаСофтЮП», 2002. - 496 с.

б

Рис. 10. Блок-схемы параллельных алгоритмов квантования (а - равномерного, б - адаптивного)

Для него требуется вычислительная система с общей памятью и как можно большим числом вычислительных узлов. Такими системами являются современные графические ускорители. Алгоритм состоит из двух частей, одна из которых будет выполняться на центральном процессоре, а вторая на видеокарте. Входными данными для алгоритма является массив и-мерных векторов. Предполагается, что между каждой парой векторов существует ребро, поэтому данный массив можно рассматривать как полный неориентированный граф. Следует отметить, что в начале работы алгоритма все векторы представляют собой отдельные деревья, и их количество соответствует количеству самих векторов. Самой трудоемкой в вычислительном плане операцией является поиск ребра, соединяющего два ближайших друг к другу дерева. Эта часть вычислительного процесса производится на графическом процессоре и ее сложность составляет 0(Y ), где Y - количество вершин. Часть алгоритма, выполняемого на центральном процессоре, производит постобработку результатов, полученных на видеокарте, и ее асимптотическая сложность 0(log2 Y). Общая сложность ПМАБ 0(Y 2log2 Y). Блок-схема ПМАБ представлена на рис. 11 (а - часть CPU, б - часть GPU).

В табл. 1 приведены результаты оценки ускорения ПМАБ по сравнению с последовательной реализацией модифицированного алгоритма Борувки (МАБ).

Таблица 1. Информация об ускорении ПМАБ в сравнении с МАБ

Количество вершин Y 20000 30000 40000 50000 60000 70000 80000 90000 100000

МАБ (секунды) 1,26 2,82 5,91 7,74 13,20 17,95 23,44 29,58 36,41

ПМАБ (секунды) 0,02 0,03 0,04 0,05 0,06 0,06 0,08 0,09 0,10

Ускорение (разы) 63 94 147,75 154,8 220 299,16 293 328,66 364,1

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

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

1) вычислить общую длину ребер поддерева;

2) обозначить принадлежность объектов классам.

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

Рис. 11. Блок-схема ПМАБ (а

Начало

1. Массив вершин 2. Массив принадлежности вершин к деревьям

Обработка на США ядрах

Массив ребер между ближайшими деревьями

Конец

б

- часть для CPU, б - часть для GPU)

Рис. 12. Блок-схема рекурсивного алгоритма обхода дерева

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

Рис. 13. Блок-схема параллельного алгоритма определения максимума функционала качества разбиения

Раздел 3.3. «Оценка адекватности разработанных алгоритмов».

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

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

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

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

Матрица погрешностей используется для определения качества проведенной классификации. Точность классификации равна доле правильно классифицированных пикселей (попавших в результате классификации в тот же класс, что и на контрольной карте) и вычисляется согласно следующему соотношению3:

N

I]Е„

5 = (18) 11Х

Для оценки адекватности вариационного метода классификации объектов на ИЗП в качестве исходных данных используются космофотоснимки земной поверхности с различных спутников, сделанные в различных диапазонах длин электромагнитных волн. Особенностью подбираемых для эксперимента снимков является наличие на них четких классов объектов (например, группы полей разных цветов и др.), что облегчает деятельность эксперта при составлении контрольной карты. В табл. 2 приведена информация об использованных изображениях. На рис. 14-16 для примера приведены оригинал изображения 1, его контрольная карта классификации и карта, полученная с использованием вариационного метода соответственно.

Таблица 2. Информация об изображениях

№ Спутник Диапазон Пространствен ное разрешение Размер Количество классов Описание

1 ЯарИЕуе Синтезированное цветное изображение 5 метров 1204x768 4 Краснодарский край

2 3 Мультиспектральное изображение в естественных цветах 4 метра 600x429 4 Фиджи, Оно-И-Лау

3 ршскШгё Мультиспектральное изображение в естественных цветах 0.6 метра 565x635 5 Хургада, Египет

3 Рис, У. Основы дистанционного зондирования [Текст] / У. Рис. - М.¡Техносфера, 2006. - 336 с.

Рис. 14 Рис. 15

Таблица 3. Описание контрольной карты изображения 1

№ Информационный класс Площадь (пиксели) Площадь (%) Цвет

1 Красные поля 345157 43.88 Щ Красный

2 Зеленые поля 253515 32.23 Щ Зеленый

3 Белые поля 187760 23.87 | | Белый

• ■ 1 >1 taa t • fll

i 3

/ В Ш a

JSfp

Рис. 16

Таблица 4. Оценка точности классификации

Метод Изображение 1. Точность классификации (%) Изображение 2. Точность классификации (%) Изображение 3. Точность классификации (%) Средняя точность классификации (%)

ISODATA(ENVI) 85.29 72.52 63.54 73.78

K-Means(ENVI) 83.82 74.57 63.54 73.97

Вариационный метод 90.72 72.82 63.25 75.59

В четвертой главе «Программная реализация параллельных алгоритмов вариационной классификации объектов» производится разработка программной системы классификации объектов на изображениях земной поверхности. Прототип системы написан на языке С++ с использованием технологий CUD А, ОрепМР, кроссплатформенной библиотеки QT. В качестве аппаратной платформы предполагается использование ЭВМ класса IBM PC с многоядерным центральным процессором и видеоускорителем

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

1. Загрузить исходное изображение.

2. Сохранить результаты классификации.

3. В интерактивном режиме производить масштабирование изображения и навигацию по нему.

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

5. Произвести классификацию.

6. Визуализировать гистограмму распределения цветов изображения по каждому из каналов.

7. Визуализировать дерево объектов.

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

В приложениях представлены свидетельства о регистрации программ для ЭВМ и акт внедрения.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫ

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

2. Разработана интегральная мера однородности в виде функционала, максимизация которого положена в основу принятия решений при классификации объектов на ИЗП.

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

• алгоритм предварительной классификации;

• алгоритм построения минимального Евклидова дерева;

• алгоритм обхода минимального Евклидова дерева;

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

4. С использованием технологий CUDA и ОрепМР разработана программная реализация созданных алгоритмов, работоспособность которой апробирована на основе обработки реальных ИЗП и модельных изображений.

5. Проведенные сравнительные вычислительные эксперименты по моделированию процесса классификации иллюстрируют адекватность предложенного метода.

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

Монографии

1. Жиляков, Е.Г. Вариационные методы анализа/синтеза изображений земной поверхности в задачах их дешифрирования [Текст] / Е.Г. Жиляков, A.A. Черноморец, A.A. Барсук, А.Н. Заливин, А.Ю. Лихошерстный. -Белгород: ООО «ГиК», 2012. - 204 с.

Статьи в рецензируемых журналах

2. Жиляков, Е.Г. Вариационный алгоритм автоматической классификации объектов [Текст] / Е.Г. Жиляков, Е.М. Маматов, A.A. Барсук // Вопросы радиоэлектроники. Серия: ЭВТ. - 2007. - Вып. 1. - С. 110-123.

3. Жиляков, Е.Г. О компьютерной реализации автоматической вариационной классификации объектов на спутниковых фотографиях земной поверхности [Текст] / Е.Г. Жиляков, A.A. Барсук // Вопросы радиоэлектроники. Серия: ЭВТ. -2010. - Вып. 1. - С. 166-171.

4. Барсук, A.A. О распараллеливании вычислений в задаче автоматической классификации объектов на космофотоснимках [Текст] / A.A. Барсук // Научные ведомости Белгородского государственного университета.-2010,-№ 19(90) Вып. 16/1.-С. 171-175.

5. Жиляков, Е.Г. О реализации параллельных вычислений в методе автоматической вариационной классификации объектов на спутниковых фотографиях земной поверхности [Текст] / Е.Г. Жиляков, A.A. Барсук // Вопросы радиоэлектроники. Серия: ЭВТ. - 2011. - Вып. 1. - С. 10-17.

6. Барсук, A.A. Параллельный алгоритм построения минимального Евклидова дерева в задаче классификации объектов на изображениях для GPU [Текст]/ A.A. Барсук, О.Н. Иванов // Научные ведомости Белгородского государственного университета.-2011. - № 13(108) Вып. 19/1.-С. 107-113.

7. Жиляков, Е.Г. Параллельный модифицированный алгоритм Борувки для GPU в задаче классификации объектов на космофотоснимках земной поверхности [Текст] / Е.Г. Жиляков, A.A. Барсук // Вопросы радиоэлектроники. Серия: ЭВТ. - 2012. - Вып. 1. - С. 64-76.

Публикации в научных журналах и сборниках трудов научных конференций

8. Барсук A.A. GPU реализация параллельного алгоритма поиска минимального Евклидова дерева в задаче классификации объектов на изображениях [Текст] / A.A. Барсук // Компьютерные науки и технологии: сб. тр. Второй Междунар. науч.-техн. конф., 3-5 октября 2011, г. Белгород. -Белгород: ООО «ГиК», 2011. - С. 23-28.

9. Жиляков, Е.Г. Быстрый параллельный алгоритм поиска Евклидова дерева в задаче классификации объектов на изображениях [Текст] / Е.Г. Жиляков, A.A. Барсук // Компьютерные науки и технологии: сб. тр.

Второй Междунар. науч.-техн. конф., 3-5 октября 2011, г. Белгород. -Белгород: ООО «ГиК», 2011. - С. 59-63.

10. Барсук A.A. Алгоритм вариационной классификации объектов на спутниковых фотографиях земной поверхности [Текст] / A.A. Барсук // Компьютерные науки и технологии: сб. тр. Первой Междунар. науч.-техн. конф. - Белгород: ООО «ГиК», 2009. - Ч. 2. - С. 122-128.

11.Барсук A.A. Вариационной метод классификации объектов на спутниковых фотографиях земной поверхности [Текст] / A.A. Барсук // Теория и практика системного анализа: сб. тр. Всерос. молодеж. конф., 1-3 октября 2012, г. Белгород. - Белгород: ИД «Белгород», 2012. - С. 189-192.

12. Барсук A.A. Параллельный алгоритм построения минимального Евклидова дерева для GPU [Текст] / A.A. Барсук // Прикладная математика, управление и информатика: сб. тр. Междунар. молодеж. конф., 3-5 октября 2012, Белгород. В 2 т. - Белгород : ИД «Белгород», 2012. - Т. 2. - С. 334-337.

Программы автора для ЭВМ

13.Свидетельство о регистрации программы для ЭВМ № 2008613623 от 16.06.2008 «Система автоматической классификации объектов и распознавания образов».

14.Свидетельство о регистрации программы для ЭВМ № 2010614898 от 05.10.10 «Система автоматической вариационной классификации объектов на спутниковых фотографиях земной поверхности».

15.Свидетельство о регистрации программы для ЭВМ № 2012614868 от 14.06.12 «Программная система вариационной классификации объектов на изображениях с использованием технологии ОрепМР».

Подписано в печать 27.02.2013. Гарнитура Times New Roman Формат 60x84/1 б.Усл. п. л. 1,0. Тираж 100 экз. Заказ 78. Оригинал-макет подготовлен и тиражирован в ИД «Белгород» НИУ «БелГУ» 308015 г. Белгород, ул. Победы, 85

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОЬРАЗОВАННЯ

«БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ» (НИУ «БелГУ»)

На правах рукописи

04201355675

Барсук Алексей Александрович

РАЗРАБОТКА МЕТОДА И ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ АВТОМАТИЧЕСКОЙ ВАРИАЦИОННОЙ КЛАССИФИКАЦИИ ОБЪЕКТОВ НА ИЗОБРАЖЕНИЯХ ЗЕМНОЙ ПОВЕРХНОСТИ

по специальности 05.13.01 - Системный анализ, управление и обработка информации (в науке и технике)

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель д.техн.н., профессор, Жиляков Е.Г.

Белгород - 2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ..........................................................................................................4

ГЛАВА 1. МЕТОДЫ И АЛГОРИТМЫ КЛАССИФИКАЦИИ ОБЪЕКТОВ НА ИЗОБРАЖЕНИЯХ ЗЕМНОЙ ПОВЕРХНОСТИ. СОСТОЯНИЕ ВОПРОСА И ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ...................................................11

1.1. Проблема классификации объектов на спутниковых фотографиях земной поверхности...........................................................................................11

1.2. Вариационный и эвристический подходы к решению задачи классификации...................................................................................................12

1.3. Методы и алгоритмы классификации объектов......................................15

1.3.1. Метод минимального расстояния......................................................15

1.3.2. Алгоритм параллелепипеда................................................................16

1.3.3. Иерархическая классификация..........................................................17

1.3.4. Метод максимума правдоподобия.....................................................22

1.3.5. Алгоритм РОЯЕЬ................................................................................25

1.3.6. Алгоритм К-внутригрупповых средних (К-Меаш)..........................27

1.3.7. Алгоритм ИСОМАД (ЗОБАТА)......................................................29

1.4. Принцип однородности разбиения при классификации объектов.........34

1.5. Информационная мера однородности.....................................................38

1.6. Постановка задач исследований...............................................................52

ГЛАВА 2. РАЗРАБОТКА МЕТОДА АВТОМАТИЧЕСКОЙ ВАРИАЦИОННОЙ КЛАССИФИКАЦИИ ОБЪЕКТОВ НА ИЗОБРАЖЕНИЯХ ЗЕМНОЙ ПОВЕРХНОСТИ НА ОСНОВЕ ПРИНЦИПА ОДНОРОДНОСТИ РАЗБИЕНИЙ.....................................................................53

2.1. Исследование свойств информационной меры однородности...............53

2.2. Разработка функционала качества разбиения на основе информационной меры однородности............................................................67

2.3. Особенности применения вариационного метода классификации объектов при принятии решений об отборе наилучшего разбиения пикселей

на классы в задаче дешифрирования ИЗП........................................................71

2.4. Основные результаты и выводы главы....................................................81

ГЛАВА 3. РАЗРАБОТКА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ КЛАССИФИКАЦИИ ОБЪЕКТОВ НА ИЗОБРАЖЕНИЯХ ЗЕМНОЙ ПОВЕРХНОСТИ................................................................................................82

3.1. Особенности современных технологий программирования параллельных вычислений................................................................................82

3.2. Параллельные алгоритмы определения максимума функционала........88

3.2.1. Параллельный алгоритм предварительной классификации.............88

3.2.2. Параллельный алгоритм построения минимального

Евклидова дерева...........................................................................................92

3.2.3. Алгоритм обхода минимального остовного дерева........................104

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

3.3. Оценка эффективности разработанных алгоритмов.............................108

3.4. Основные результаты и выводы главы..................................................123

ГЛАВА 4. ПРОГРАММНАЯ РЕЛИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ ВАРИАЦИОННОЙ КЛАССИФИКАЦИИ ОБЪЕКТОВ. ..125

4.1. Выбор технологий программирования..................................................125

4.2. Архитектура программной реализации.................................................129

4.3. Основные результаты и выводы главы..................................................133

ЗАКЛЮЧЕНИЕ................................................................................................134

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ........................................135

ПРИЛОЖЕНИЕ А............................................................................................147

ПРИЛОЖЕНИЕ Б.............................................................................................150

ВВЕДЕНИЕ

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

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

Среди существующих современных программных реализаций

автоматической классификации объектов на спутниковых фотографиях земной поверхности следует выделить программный комплекс ENVI, в котором реализованы два алгоритма кластеризации, а именно ISODATA (ИСОМАД) и K-Means (К-внутригрупповых средних). Следует отметить, что результаты, получаемые при использовании упомянутых алгоритмов, не всегда совпадают с интуитивными представлениями экспертов об адекватности разбиения.

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

Важной особенностью классификации объектов на космофотоснимках земной поверхности является тот факт, что объемы обрабатываемой информации могут быть очень велики, так как количество возможных разбиений исходного множества пикселей на классы составляет B(N*M), где В-число Белла, a M и N - ширина и высота изображения в пикселях, что для

5638

изображения 50 на 50 пикселей составляет около 103OJ6. При этом получаемые разбиения должны быть оценены с точки зрения некоторого критерия, основанного на интегральной мере однородности. Это приводит к необходимости применения высокопроизводительных вычислительных систем.

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

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

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

Для достижения поставленной цели были сформулированы и решены следующие задачи:

1. Разработка функционала (критерия) качества автоматической классификации объектов на цифровых ИЗП как интегральной меры однородности получаемых разбиений пикселей на классы.

2. Разработка параллельных алгоритмов принятия решений при отборе

6

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

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

4. Сравнительная оценка адекватности предлагаемого метода автоматической вариационной классификации.

Объект исследований: методы анализа ИЗП.

Предмет исследования: вариационные методы классификации объектов на цифровых ИЗП.

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

Научную новизну работы составляет следующее:

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

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

3. Параллельные алгоритмы принятия решений при классификации:

• алгоритм предварительной классификации;

• алгоритм построения минимального Евклидова дерева векторов признаков;

• алгоритм разрезания и обхода минимального Евклидова дерева;

• алгоритм определения максимума функционала качества классификации.

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

Полученные результаты также используются при проведении НИР и ОКР ООО «НПП «Энергетические и информационные технологии», что подтверждается соответствующим актом, а также в учебном процессе магистрантов факультета КНиТ НИУ «БелГУ».

Связь с научными и инновационными программами.

Результаты диссертационного исследования были использованы в рамках выполнения следующих НИР:

ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, госконтракт № 14.740.11.0690 от 12 октября 2010;

ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013, госконтракт № 14.740.11.0390 от 20 сентября 2010;

Грант РФФИ №12-07-00257-а;

Аналитическая ведомственная целевая программа (АВЦП) «Развитие научного потенциала высшей школы» в 2006-2008 гг., проект РНП.2.1.2.4974;

АВЦП «Развитие научного потенциала высшей школы» в 2006-2008 гг., проект РНП.2.2.1.1.3121;

АВЦП «Развитие научного потенциала высшей школы» на 2009-2010 гг., проект № 2.1.2/656;

Программа Фонда содействия развитию малых форм предприятий в научно-технической сфере «У.М.Н.И.К.», проект «Информационная технология вариационной классификации объектов на спутниковых фотографиях земной поверхности»;

Область исследования: Содержание диссертации соответствует следующим пунктам паспорта специальности 05.13.01 «Системный анализ, управление и обработка информации (в науке и технике)»:

П.4. Разработка методов и алгоритмов решения задач системного анализа, оптимизации, управления, принятия решений и обработки информации.

П.5. Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, управления, принятия решений и обработки информации.

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

Положения, выносимые на защиту:

1. Метод вариационной автоматической классификации объектов на цифровых ИЗП на основе максимизации функционала качества как интегральной меры однородности получаемых результатов разбиений.

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

3. Программная реализация параллельных алгоритмов на основе технологий С1ЛЭА и ОрепМР.

4. Результаты сравнительной оценки адекватности предлагаемого метода автоматической вариационной классификации.

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

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

Апробация результатов диссертационного исследования.

Результаты диссертационного исследования обсуждались на следующих научно-технических конференциях, выставках и конвентах: Международная молодежная конференция «Прикладная математика, управление и информатика», 2012, г. Белгород; Всероссийская молодежная конференция «Теория и практика системного анализа», 2012, г. Белгород; Первая и Вторая Международная научно-техническая конференция «Компьютерные науки и технологии», 2011 и 2009, г. Белгород; Всероссийская Выставка научно-технического творчества молодежи, 2010, г. Москва; Всероссийская выставка-конкурс прикладных исследований, изобретений и инноваций, 2009, г. Саратов; Второй Всероссийский молодежный инновационный конвент, 2009, г. С.-Петербург; Окружной инновационный конвент , 2009, г. Дубна.

Публикации. По теме диссертационного исследования опубликовано 12 печатных работ (из них 6 в журналах из списка ВАК РФ), а так же 3 Свидетельства Роспатента РФ о государственной регистрации программы для ЭВМ.

Объем и структура работы. Диссертация состоит из Введения, четырех глав, Заключения и Приложений. Работа изложена на 150 страницах машинописного текста, включая 80 рисунков, 27 таблиц и список литературных источников из 113 наименований.

ГЛАВА 1. МЕТОДЫ И АЛГОРИТМЫ КЛАССИФИКАЦИИ ОБЪЕКТОВ НА ИЗОБРАЖЕНИЯХ ЗЕМНОЙ ПОВЕРХНОСТИ. СОСТОЯНИЕ ВОПРОСА И ПОСТАНОВКА ЗАДАЧ ИССЛЕДОВАНИЯ

1.1. Проблема классификации объектов на спутниковых фотографиях

земной поверхности

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

• классификация с обучением (контролируемая классификация);

• классификация без обучения (автоматическая классификация);

Для контролируемой классификации используют эталонные области,

которые выбираются оператором в соответствии с их принадлежностью к

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

оператор опирается на свое знание территории и расположенных на ней

объектов. Таким образом, именно он контролирует разделение всех объектов

на определенные классы. Значения пикселе�