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

о

и

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

Пестунов Игорь Алексеевич

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

05.13.16 — применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (в экологии)

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

Красноярск - 1998

Работа выполнена в Институте вычислительного моделирования СО РА

Научный руководитель — доктор технических наук, профессор

А.В.Медведев

Официальные оппоненты: доктор технических наук, профессор

Г.А.Доррер;

кандидат физико-математических наук А.А.Новоселов

Ведущая организация — Институт вычислительных технологий СО РА

Защита диссертации состоится " лал. 1998 г. в часов i заседании диссертационного совета К 064.54.01 при Красноярском гос; дарственном техническом университете по адресу: 660074, г. Красноярс: ул. Киренского, 26.

С диссертацией можно ознакомиться в научной библиотеке Красноярско] государственного технического университета.

Автореферат разослан ".&£_" 1998 г.

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

Н.Г.Кузьмен]

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

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

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

— большое количество распознаваемых объектов (например, каждый кадр MCC Landsat содержит ~7.5х10б, а снимок SPOT при захвате площади 60x60 км2 — ~9х10® пикселов);

— высокая априорная неопределенность (отсутствие информации о виде условных плотностей распределения и априорных вероятностях классов);

— наличие классов, не представленных в классифицированной обучающей выборке (часто такая выборка отсутствует совсем).

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

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

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

Методы исследования. При выполнении диссертационной работы использовались методы теории вероятностей, математической статисти-

ки, распознавания образов, кластер-анализа, цифровой обработки изобр; жений и статистического моделирования (Монте-Карло).

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

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

2. Предложены методы и алгоритмы повышения быстродействия клш сификаторов Розенблатта-Парзена при обработке многоспектральной а: рокосмической видеоинформации.

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

4. Предложен эффективный метод выбора информативных наборе спектральных признаков для классификаторов Розенблатта-Парзена в зг дачах тематической обработки.

5. Разработаны непараметрические алгоритмы для распознавания н< стационарных образов; их эффективность подтверждена результатами Ч1 елейного моделирования.

6. Разработан пакет прикладных программ ВЙЗОР, структура и фуш циональное наполнение которого учитывают особенности задач тематич» ской обработки многозональной аэрокосмической видеоинформации, св^ занных с картированием и оценкой состояния лесных насаждений.

Практическая ценность и реализация результатов исследовг ний. Основной практический результат заключается в создании паю та прикладных программ ВИЗОР, предназначенного для решения зада тематической обработки многозональной аэрокосмической видеоинформг ции. Основу пакета составляют разработанные в диссертации новые пепг раметричсскис алгоритмы распознавания образов и автоматической кла< сификации. Пакет ВИЗОР внедрен в Институте леса им. В.Н.Сукач« ва СО РАН, где используется в составе математического обеспечен!; научно-методического центра сбора и обработки аэрокосмической ипфо] мации экологического состояния лесов Красноярского края для анализ материалов сканерных аэро- и космических съемок. С помощью пакет ВЙЗОР решался ряд задач, связанных с картированием и оценкой состоз ния лесных насаждений. Важное практическое значение имеют результ; ты, полученные в ходе обработки данных аэросъемки Краснотурансхм бора сканером С-500 и спутниковой съемки КОЛ А /АУШШ территори

Нижнего Приангарья с целью обнаружения: и анализа очагов повреждения древостоев насекомыми. Пакет успешно применялся также при решении предложенной Институтом "Востсибгипрозем" в г. Красноярске задачи дешифрирования почв по данным аэрофотосъемки. Практическая ценность результатов диссертационной работы подтверждена актами внедрения.

Апробация работы и публикации. Основные положения диссертационной работы доложены и обсуждены на III Всесоюзном симпозиуме по машинным методам обнаружения закономерностей, Новосибирск, 1980; III школе-семинаре "Непараметрические и робастные методы статистики в кибернетике", Красноярск, 1981; III Научной сессии Научно-координационного совета по проблеме "Аэрокосмические исследования природных ресурсов", Новосибирск, 1982; Всесоюзной конференции "Обработка изображений и дистанционные исследования", Новосибирск, 1984; Всесоюзной конференции "Аэрокосмические методы исследования лесов", Красноярск, 1984; I региональном семинаре "Математические и технические проблемы обработки изображений", Новосибирск, 1985; III Всесоюзной конференции "Обработка изображений и дистанционные исследования", Новосибирск, 1987; VI Всесоюзной школе-семинаре по непараметрическим и робастным методам статистики в киберпетике, Томск, 1987; Научно-техническом семинаре "Статистика случайных полей. Обработка изображений", Красноярск, 1988; IV Всесоюзной научно-технической конференции "Применение многомерного статистического анализа в экономике и оценке качества продукции", Тарту, 1989; Международной конференции "Обработка изображений и дистанционные исследования", Новосибирск, 1990; Всесоюзной конференции "Распознавание образов и анализ изображений: новые информационные технологии", Минск, 1991; научной конференции "Проблемы техники и технологий XXI века", Красноярск, 1994, а также на семинарах ИВМ СО РАН, КГТУ, КГТА и ИВТ СО РАН.

По теме диссертации опубликовано 12 работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Объем диссертации составляет 157 страниц машинописного текста, включая 25 рисунков, 18 таблиц, список литературы из 136 наименований и приложение, содержащее акты внедрения результатов работы.

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

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

ценность полученных результатов, дано краткое изложение основных ра делов диссертации.

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

Вторая глава посвящена исследованию непараметрических правил к: сификации, основанных на оценках Розенблатта-Парзена, и разработ] быстрых непараметрических классификаторов.

Пусть в X С SR* с известными и отличными от нуля вероятностям.

м

5,,..., qu ( £ qi = 1) регистрируются наблюдения из классов Q1;..., 9.

г~\

соответственно. Наблюдение из Qi есть реализация ¿-мерного случайн го вектора-столбца х^ = (х^,... 6 3tk, плотность распределен!

которого fi(x) неизвестна (г = 1, М), но имеется классифицированная об;

чающая выборка V — U УМ объема N = £ где VW = {Д') :

_ t=i i=i J 1

j — 1, A^i} - множество из iV,- независимых наблюдений класса Т\ гда семейство непараметрических классификаторов Розенблатта-Парзеь описывается выражением:

м -а)

60 = й0(х; V) = argmin £ 0е)- С

Здесь Xij - величина потерь при отнесении в üj наблюдений из {1,2, ...,M};f$(x) - непараметрическая оценка плотности /¿(а;) в точ! х 6 X, определяемая выражением

т №))"'ф Ö.....

где Ф(-) - некоторая заданная колокодообразная функция, называемая ядр а {/ii(jV,-),..., h/.(Ni)} - набор положительных параметров сглаживани Для состоятельности решающих правил (РП) 6q(x-, V) Ф(-) должны уд влетворять условиям:

1) Цх) > О V х € 3F£fc, 2) sup Ф(ж) < оо,'

хеэг1

б

3) / Цх)йх = \, 4) lim |И|*Ф(*) = 0. (3)

gjb И1!!-00

А для параметров сглаживания при этом должны выполняться асимптотические соотношения:

1) Дш^ hi(Ni) = О V I е {1,2,..., к}, 2) jljmWf П A,(JVf) = со, (4)

Риск классификации для РП вида (1) определяется выражением

м м

Ro = ЗД>; V) = Е Qi £ / Xx.(x)fi(x)dxi i=i j=i ¿t J

где {X,} - разбиение пространства X, соответствующее РП (1), а ХхХ') - индикаторная функция множества Xj.

Практическое использование классификаторов (1) затруднено тем обстоятельством, что при конечном объеме обучающей выборки возникает необходимость в выборе как функций ядра Ф(-), так и параметров сглаживания {hi(Ni)}. Условия (3), (4) несущественно ограничивают свободу этого выбора. Наибольшее влияние на вероятность ошибки (или риска) классификации оказывают параметры сглаживания.

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

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

Rs = Re(S0) = E{RC(6Q-V)}, где Е — символ математического ожидания по выборкам объема N.

Для эксперимента были выбраны четыре мультипликативных ядра:

фМ{х) = П р = М, где

Ф(3)Ы = { 0-5 при Ы < 1, {i)( ] ( 1 - М, если \у\ < 1,

(0 при |j/| > 1; 9 U> \ 0, если |у| > 1; у G 3? .

На основании исследований сделаны следующие выводы: ' — если N-,/k > 50, то ядра ф(р)(аг), р = 1,4 обеспечивают одинаковые вероятности ошибки классификации (ВОК). Но при определении значений ядра Ф^(а:) требуется наименьший объем вычислений;

— если 5 < И{/к < 50, то исходя из критерия минимума ВОК мож) использовать любое из ядер Но ядро обе печивает минимальный объем вычислений;

— если N¡/1* < 5, то целесообразно использовать ядро Ф^^а:).

В §2.3 предложен метод генерации быстрых непараметрических алг ритмов классификации на основе классификаторов Розенблатта-Парзен Идея метода заключается в следующем. Пусть А,у = 1 — (г, ? = 1, М где — символ Кронекера, тогда РП (1) перепишется в виде

- /ч л/

¿0 = 80{х] V) = ащщжд{Щ(х). (.

Обратим внимание на то, что при классификации точек с использов нием РП (5) нас, вообще говоря, не интересуют значения оценок {/^(ж сами по себе, достаточно решить лишь вопрос о том, какая из велич! ^Лг^С1)» ■ ■ ■ больше в данной точке. Поэтому предлагается

выражении (5) оценки (х) заменить более простыми (в смысле объел вычислений) статистиками }$(х):

№(г\ - Л Г ЫкФ 1 * <-<№}

где а¡(у) € {1,2,... ,ЛГ,-}, причем элементы а,( 1),... таковы, ч:

если р Ф д, то а,-(р) ф Щ < Д^-.

В результате такой замены РП (5) преобразуется в правило ¿о:

5 о = 50(х;Ш) = axgmaxqiM(x).

м м

Здесь Ш — 0 У/1^ есть рабочая выборка объема И' = £ где И7^

1=1 1=1

е 3 — 1,2,..., Л^}. Для формирования выборки W предложи процедура .АС, которая гарантирует неизменность значения оценки пер классификации и обеспечивает состоятельность РП 8о- В качестве илл! страции работы этой процедуры на рис. 1 в графическом виде представл ны исходная (М = N2 = N3- 500) и рабочая (Щ = 12, Щ = 15, Щ = Г выборки для трехклассовой модели данных. Эффективность процедур АО исследовалась методом статистического моделирования как на модел ных, так и на реальных данных. Результаты исследования показываю что в случае, когда 6й(х; Ш) и ¿>0(2; V) обеспечивают практически один ковую достоверность распознавания, объем выборки У/ оказывается зн чительно (иногда в несколько десятков раз) меньше объема выборки V.

В §2.4 рассматривается комбинированный алгоритм генерации раб чих выборок. Его разработка обусловлена тем, что при выполнении пр цедуры _ДС выборка IV содержит, как правило, избыточное число эл

8-0-

5М-

-гя-

-7Д--

} 1-1111111111III [I п || 1 п ц I т[

8Л~

3-0.

-2Л--

•«7.0---

* +.

ч- + * *

1111111 п 11 I и и-w-^fн-н-н-^-^-^-j—;

•7.0 -2.0 3.0 8.0

-7 Л -и 3.3 8Л

Рис. 1: Исходная (слева) и рабочая выборки

ментов. Поэтому с целью исключения лишних элементов, предлагается выбирать любое наперед заданное число Щ' < Щ элементов выборки ЪУ^ (г = 1,2,... ,М), которые наилучшим образом (в смысле максимума оценки функционала энтропии) сохраняют оценку ¡^.(х). Такую двухэтап-ную процедуру "просеивания" исходной выборки назовем комбинированным алгоритмом АС, а получаемую в результате его применения рабочую

м

выборку обозначим через Я = ОД1- Тогда РП, построенное по выборке

1=1

Я, может быть записано в виде

6о=6о Я) = /

(0

- хт,г

Хк

где

1мм

к ' ' н

АС?) £ {^(1), • • ■, а;(Л'1')}, причем элементы /3,(1),... таковы, что

если р ф 5, то и Д(р) ф

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

В §2.5 описываются и численно исследуются непараметрические алгоритмы классификации, учитывающие временной дрейф вероятностных характеристик классов. Для конструирования таких алгоритмов используется известный прием, суть которого состоит в том, что при оценивании плотностей {/;(£,я)}, зависящих от времени t £ [а,6], вновь поступившая информация получает больший вес по сравнению со "старой". Пусть х^ € — наблюдение из П;, зарегистрированное в момент времени

< - ■ • < Для классификации наблюдений, поступающих в момент времени t > ¿тах = тах №. предлагается РП

¿о = ¿а^ш^х; V) - а^тЫ^ Xijqif^)i(tmax,x)}, где - .....

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

При проведении численных экспериментов хорошо зарекомендовала себя функция памяти рЦ,^) = (^'/ТУ,-)0", где а > 0 (заметим, что при а = 0 получаем правило (1)). В ходе этих экспериментов установлено, что при увеличении значения а сначала происходит снижение (иногда до 1.5 раз), а после чего возможно увеличение В ОК.

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

В §3.1 излагается быстрый алгоритм для вычисления непараметрической оценки Розепблатта-Парзена (2) с ядром Ф^(:е). Исследования показали, что при к < 6 он позволяет в 2-3 раза сократить объем вьпислений по сравнению с традиционным алгоритмом. Добиться этого удается благодаря тому, что значения спектральных признаков лежат в ограниченном диапазоне целых чисел целых чисел от 0 до Ь - 1, где Ь - число уровней квантования видеосигнала, обычно не превышающее 256.

В §3.2 описывается непараметрический классификатор Розенблатта-Парзена с "памятью". Данный алгоритм основан на учете многократной повторяемости большинства векторов спектральных яркостей, характеризующих многозональные аэрокосмические изображения. Это позволяет е несколько раз сократить объем вычислений, требующийся для поэлементной классификадии аэрокосмических изображений. Для достижения этог цели предлагается: 1) в процессе классификации в оперативной памят! ЭВМ формировать таблицу классифицируемых векторов и связанные с ней таблицу частот их встречаемости и таблицу решений, где каждом} вектору ставится в соответствие номер класса, к которому он отнесен; по мере формирования таблиц использовать их при отыскании готовых решений для повторяющихся векторов. Построение таблиц производится не

основе хеширования. Для каждого классифицируемого вектора-столбца х — Х2,... £ вычисляется некоторая хеш-функция. Вычи^ сленное значение служит индексом для доступа в массивы, содержащие соответствующие формируемые таблицы.

При обработке материалов аэросъемки, полученных с помощью сканера С-500, хорошо зарекомендовали себя хеш-функции вида

Н(х) = (агх 1 ® а2а'2 ф ... © щхк) mod К,

где ф — побитовая логическая операция "исключающее или"; К - простое число, определяющее размеры таблиц; (•) mod К - остаток от деления (•) на К; ai, • • •! ак ~ коэффициенты, подобранные таким образом, чтобы распределение значений Н{х) в интервале [О, К~ 1] было близким к равномерному. Используя эту функцию, удается более чем в 4.5 раза повысить быстродействие классификаторов Розенблатта-Парзена.

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

М М JV; Nj k

Rc = 2E E £ п Ш

(i) \2h- |43 - 1, если la:« - < 2h, M (0, если |«й-х«|>2Л,

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

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

Для того, чтобы пояснить схему работы процедуры VI] введем некотс рые определения и обозначения. Пусть произведена съемка участка мест ности, содержащего тпхп элементов разрешения. Сопоставим каждому тг кому элементу с условными координатами (г,, г = 1 ,т, = 1,«, векто (1) М\

a¿J■ = I агу,..., а,у 1 соответствующих ему измеренных значении яркости

диапазонах спектра. Тогда матрицу А = (ау) назовем &-спектральны: изображением размером тохп элементов, а подматрицу

аР, 7+в-1 ^

Ор+И/

— его фрагментом с координатами (р, 5) и размером / х 5 элементов.

Для фрагмента А'^ соседними будем считать фрагменты Ар_1д> Ар+1Ч и АрЛ+6. Фрагмент назовем квазиоднородным (/со-фрагментом), есл для почти всех его элементов след ковариационной матрицы не превосхс дит заданного порога §1. Предполагается, что вектор средних значени (в.с.з.) /го-фрагмента вычисляется только по тем его элементам, которы удовлетворяют условию квазиоднородности. Квазиоднородную облает (&о-область) определим по индукции:

1) ¿о-фрагмент является /со-областыо;

2) ¿о-область, состоящая из I (I > 1) фрагментов, может быть расшг рена путем присоединения к ней соседнего ¿о-фрагмента, если евклидов расстояние между в.с.з. этого фрагмента и в.с.з. ¿о-области (вычиелг ется путем усреднения в.с.з. ¿^-фрагментов, входящих в /го-область), н превосходит заданного порога 5ч- Пусть изображение разбито на рд не больших фрагментов размером элементов. На первом этапе выделя ются ко-области путем последовательного просмотра полос изображен!« состоящих из одного ряда фрагментов. Характеристики каждой выделвь ной ко-области (в.с.з. и число фрагментов, составляющих ее) занося! ся в таблицу Т1. Одновременно производится заполнение таблицы Т1 в которую для каждого /с о-фрагмент а заносится номер соответствующе: ему /со-области, а для фрагментов, не являющихся квазиоднородными, -нуль. Для формирования и выделения ко-областей разработана ории: нальная схема, основное достоинство которой заключается в том, что дл ее реализации требуется всего лишь один последовательный просмотр изс бражения.

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

А:

и —

Р1 ~

ря

анализ нескольких тысяч областей затруднителен. Поэтому на втором этапе обработки ¿о-области объединяются в группы "похожих" с помощью алгоритма группировки. Для обработки нескольких тысяч реализаций (объектов) практически могут быть использованы, лишь наиболее 'простые и нетрудоемкие алгоритмы. К их числу относится эффективный (с точки зрения поиска локальных максимумов плотности распределения в.с.з.) алгоритм группировки "Форэль", применяемый на втором этапе. В качестве исходных реализаций для этого алгоритма используются в.с.з. ко-областей. Причем каждой реализации приписывается "вес", пропорциональный числу фрагментов, содержащихся в соответствующей ей &о-области. Результатом 2-го этапа является набор пар (¡>0), (г(2), <3(2)),..., <2(Ч)} и картосхема изображения, на которой представлены выделенные группы ¿о-областей. Здесь Ь — общее число групп (спектральных классов).

Опыт применения процедуры РЗ к реальным изображениям показал, что при оптимальном выборе на втором этапе значения настраиваемого параметра ¿>3, число Ь обычно достаточно велико (~200-300). По этой причине получаемые на данном этапе картосхемы представляют собой, как правило, раздробленные и трудноанализируемые картины. Поэтому на третьем этапе используется алгоритм, который не только учитывает локальные максимумы плотности в.с.з., но и их взаимное расположение в пространстве признаков. Этот алгоритм позволяет выделять классы, определяемые следующим образом. Пусть Ог(г) есть множество г-ближайших соседей к точке величину Рг(г) определим выражением

Р л _ / 1/г при <Э«> < 64,

При <2® > ¿4.

Здесь ¿4 - некоторый заданный порог. Две точки г^ и г^ являются г-смежными, если г® € и г^ 6 Пг(г). Пусть 5г(г) - множество

точек, являющихся г-смежными к точке На элементах множества 2 — {.г^, ■ ■ -, введем отношение подчиненности: полагаем, что точка г^ подчинена точке если РГЦ) = тш^^ф Рг(з). Если при этом окажется, что 7 — г, то точку г® назовем центральной. В результате введения такого отношения множество 2 разбивается па подмножества. Каждое из этих подмножеств будем считать классом. В соответствии с определением класс имеет иерархическую структуру. При увеличении числа ближайших соседей г число классов будет уменьшаться. Варьируя значение параметра г, можно получать картосхемы различной степени подробности, что существенно облегчает интерпретацию результатов обработки.

В четвертой главе рассматриваются вопросы программного обеспе-

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

В §4.1 формулируются общие требования к программно-алгоритмиче< кому обеспечению задач тематической обработки.

В §4.2 описывается структура, назначение и функциональные возмог ности пакета программ ВИЗОР, приводятся примеры обработки с поме щыо модулей пакета. Алгоритмы решения конкретных тематических з< дач организуются пользователем как некоторая последовательность пре; ставленных в пакете процедур визуализации, фильтрации и повышена контраста изображения, статистического анализа, формирования и выбор информативных признаков, классификации с обучением и автоматическо классификации. Для улучшения визуальных характеристик изображени в пакете имеются процедуры линейного растяжения динамического диапг зона значений яркости на всю шкалу, эквализации гистограммы pacnpi деления значений яркостей, пороговой медианной фильтрации, линейнс фильтрации с использованием масочного оператора.

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

В блок формирования признаков включены процедуры получения н<

коррелированных линейных комбинаций исходных измерений по метод

главных компонент; вычисления текстурных признаков и вегетационны

индексов. При реализации метода главных компонент использован т<

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

сократить их объем. В пакете предусмотрено определение текстурны

признаков CON — Ei2Ps(i), ASM = EPS2(»'). i?AT = - E Pa{i) log P„(i i i i MEAN = l/m£P,(¿). Здесь s - заданное расстояние между парами эл< i

ментов изображения, для которых вычисляются разности сиектральны яркостей; т - число элементов изображения в окрестности; Ps(i) - част( та, с которой среди значений разности для элементов окрестности Bcxpi чается значение г.

В пакете имеются две процедуры выбора информативных признако; Одна из них описана в §3.3 и рекомендуется к применению в сочетании классификаторами, основанными на оценках Розенблатта-Парзена, а др; гая — в сочетании с параметрическим классификатором, построенным предположении нормальности условных плотностей распределения вект! ра признаков для каждого из рассматриваемых классов.

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

м м

ехр[-/?я(»,.;')], где

¿>/¿=1

РБ&З) = 1/4{21п|(Е, + £.)/2| -1п|Й| -1п|£,.|}+

+1/4(д(0 - + £.)-\а® -

выбирается небольшая группа лучших наборов признаков. На втором — из этой группы по минимуму оценки "скользящего экзамена" выбирается наилучший набор признаков.

В пакете реализованы два классификатора с обучением: параметрический и непараметрический. При построении параметрического классификатора предполагается, что условная плотность распределения /¿(ж) для класса П,- (г = 1,М) является нормальной плотностью с неизвестными параметрами. Для непараметрического классификатора никаких ограничений на вид плотности не накладывается. В процессе классификации могут встречаться объекты, не относящиеся ни к одному из М заданных классов. Тогда считается, что такие области принадлежат к дополнительному классу-фону Параметрическое РП записывается в виде г € если С^- + < + 5; для V г ф ] и < х2а<ь г 6 П$, если Qj + < <3,- + для У г ф j ■aQj >

Здесь <5, — (г - 1{г - /¿¿), $ ~ 1&1 ~ 21п?,-, где порог х1,к нахо-

дится по таблицам распределения из условия Р{х2(к) > Ха,к} ~ а> где а — заданная вероятность отказа. Для повышения быстродействия этого РП реализован алгоритм двухступенчатого распознавания, позволяющий для ряда классов вместо махаланобисова расстояния <5,- вычислять квадрат евклидова расстояния г,-(г) = (г - - Для вычисле-

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

Непараметрическое РП записывается в виде

I г 6 Яь если qjf¡^ > для всех %ф]\

} г 6 Пф, если = 0 для г — 1,2,..., М. Здесь = 1 ,М, - ненараметрическая оценка вида (2). При его реализации использованы алгоритмы, предложенные в §2.3 и §2.4.

В пакете имеется две процедуры автоматической классификации, в том числе описанная в §3.4.

В §4.3 рассматриваются вопросы практического применения програм; пакета ВИЗОР для решения задач обнаружения и анализа очагов повре ждения древостоев насекомыми по данным многозональных аэро- и кос мических съемок. Объектами исследования являлись сосновые насаждена Краснотуранского бора, часть которых повреждена сосновой пяденицей, также темнохвойные леса южной тайги Красноярского края (Нижнее При ангарье), где в 1992-96 гг. развивалась крупномасштабная (~1 млн. га вспышка массового размножения сибирского шелкопряда.

Для автоматизированного анализа насаждений Краснотуранского бс ра использовались данные съемки сканером С-500, представляющим 8 канальную систему. Каналам 1-8 соответствуют длины волн 800-97С 620-710, 565-630, 490-550, 525-575, 685-730, 730-800, 900-1060 нм. Высо та съемки - 7300 м, размер разрешаемого элемента на местности составля, ~9х18 м2. В качестве исходного был выбран набор признаков {х\,х%,... гд}, где я,- - значение яркости измеренное в г-ом канале сканера (г = 1,8), £д - вегетационный индекс, определяемый по формуле хд = ЮОхх/х^. Ана лиз исходного набора показывает, что для распознавания поврежденны насаждений с помощью непараметрического классификатора достаточн использовать набор из трех признаков: {1,2,5}, а с помощью параметра ческого - наборы из трех-четырех признаков, например, {1,2,5}, {1,2,5,6} При этом средняя достоверность распознавания составляет ~93%.

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

Для обнаружения повреждений предлагается простая пороговая процс дура сегментации на основе индекса х$. Для построения картосхемы ис пользуется процедура "РЗ, описанная в §3.4. В результате нолучена утог ненная картосхема зоны повреждений и найден функциональный вид ре грессионной зависимости между спектральными характеристиками клас сов и количественными характеристиками категорий состояния объект исследования.

Состояние территории Нижнего Приангарья оценивалось по данньп полученным 16 августа 1995 года спектрорадиометром АУНШ1 в диапг зонах 0.58-0.68, 0.725-1.1, 3.55-3.93, 10.3-11.3 и 11.5-12.5 мкм, наземно разрешение ~1 км. Автоматизированная обработка включала стати си ческпй анализ данных, выбор информативных признаков и автоматич< скую классификацию. В качестве исходного был выбран набор признаке {^1,..., где Х},г = 1,5, - измеренное значение яркости в ¡-ом каш ле АУНШ1, а х§ и х7 - вегетационные индексы, определяемые по форм]

лам: х6 = кхц/хг, хг = к2(х2 - х{)[(х2 + £1) + к3, где кик2,к3 - нормировочные коэффициенты, обеспечивающие попадание значений гд, хч в' отрезок [0, 255]. Анализ исходного набора показал, что пары {а^х,а:б} {аг2,Жб}, {21,3:5} являются наиболее информативными. Увеличение числа признаков приводит к незначительному улучшению точности классификации. Из одиночных признаков наилучшими являются вегетационные индексы Х(,, хт. В результате классификации тестовых фрагментов выяснено, что, если фрагменты однородны, то достоверность классификации очень высокая (~95%) даже при использовании одного признака. На подвергнутых анализу изображениях средняя вероятность ошибок классификации составляет ~15%. Основной источник ошибок - неоднородность исследуемой территории: при наземном разрешении системы АУНИК км в пределах практически каждого элемента разрешения возможно присутствие нескольких категорий земель. Установлено, что съемка АУНШ1 позволяет обнаруживать катастрофические изменения лесного покрова и получать генерализованную информацию о масштабах происходящих изменений; наземное разрешение изображений АУН1Ш. адекватно для картирования в масштабе 1:1000000.

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

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

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

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

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

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

4. Разработаны эффективные непараметрические методы и алгоритмы

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

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

6. Создано программное обеспечение (пакет программ ВИЗОР) д. тематической обработки многозональной аэрокосмической видеоинформ ции, основанное на предложенных в диссертационной работе непараы трических алгоритмах выбора информативных признаков, распознавай] образов и автоматической классификации.

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

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

Основные результаты диссертации опубликованы в следующих раб тах.

1. Пестунов И.А., Харук В.И., Кривчикова Л.Д. Сканерная съемка анализе структуры сосновых насаждений // Тез. докл. Всесоюз. кон "Аэрокосмические методы исследования лесов". —Красноярск, 1984. С. 69-70.

2. Пестунов И.А., Харук В.И., Успенский С.А. Сканерная съемка в и дикации патологии леса // Дистанционные исследования природных р сурсов Сибири. — Новосибирск: Наука, 1986. — С. 29-34.

3. Пестунов И.А. Выбор информативных признаков для непараметр ческого классификатора при обработке многозональной аэрокосмическ видеоинформации. — Красноярск, 1988. — Препр. / ВЦК СО РАН; №

— С. 16-19.

4. Пестунов И.А. Непараметрические алгоритмы классификации ме гозональной аэрокосмической видеоинформациии // Численный анализ с ратных задач дифракции. — Красноярск: КГУ, 1989. — С. 103-113.

5. Анциферов В.К., Вогульская H.A., Пестунов И.А. Пакет програг. обработки многозональной аэрокосмической видеоинформации ВИЗОР Численный анализ обратных задач дифракции. - Красноярск: КГУ, 19£

— С. 4-12.

6. Медведев A.B., Пестунов И.А. Непараметрический алгоритм оценки качества продукции при изменяющихся условиях // Тез. докл. Всесоюз. конф. "Применение многомерного статистического анализа в экономике и оценке качества продукции. — Тарту, 1989. — 4.2. — С. 326-327.

7. Пестунов И.А. О методах повышения быстродействия непараметрических классификаторов, основанных на оценках Розенблатта-Парзена // Тез. докл. Международ, конф. "Обработка изображений и дистанционные исследования". — Новосибирск: ВЦ СО АН СССР. — 1990. — С. 171-172.

8. Пестунов H.A. Модификация непараметрических алгоритмов классификации, основанных на парзеновских оценках плотности распределения с целью повышения быстродействия // Тез. докл. Всесоюз. конф. "Распознавание образов и анализ изображений: новые информационные технологии". — Минск, 1991. — Ч.З. — С. 138-141.

9. Пестунов И.А. О методах построения вычислительно эффективных непараметрическпх алгоритмов классификации // Тез. докл. Республ. конф. "Компьютерный анализ данных и моделирование". -— Минск, 1992.

10. Пестунов И.А. Непараметрические алгоритмы классификации для обработки больших массивов данных // Математические модели и алгоритмы в задачах обработки данных. — Красноярск: КГУ, 1993. —

11. Пестунов И.А. Непараметрическая процедура автоматической классификации данных многозональной сканерной съемки для изучения и оценки состояния лесных насаждений // Математическое обеспечение и архитектура ЭВМ: матер, научн.-техн. конфер. "Проблемы техники и технологий XXI века". — Красноярск: КГТУ, 1994. — С. 141-145.

12. Пестунов И.А. Автоматизированные методы обнаружения и анализа очагов повреждения древостоев по данным многозональной сканерной съемки // Математическое обеспечение и архитектура ЭВМ. — Красно-

— С. 41.

С. 137-146.

ярск: КГТУ, 1997. — С. 249-253.