Автореферат (1137225), страница 3
Текст из файла (страница 3)
Также дан набор точек, заданных географическими координатами, для каждой из которых требуется определить, лежит ли она в каком-либо из полигонов, причём1 ≪ ≪ . Такая задача возникает при совместной обработке векторныхданных и растровых данных, геопривязка которых осуществляется поточечно, и из-за проекционных искажений невозможно по координатам в явномвиде вычислить расположение в растре, поэтому приходится работать как снабором независимых точек. При больших объёмах данных задача становится вычислительно сложной и требует оптимизации, в частности индексациивекторного файла.Разработанный методсостоит в создании одноуровневой индекснойструктуры, параметры которой зависят от параметров векторных данных.Для работы требуется, чтобы полигоны не сильно отличались от некоторого13характерного размера , не были сильно вытянуты и не пересекались.
Реальные данные об очагах активных природных пожаров, полученные по космическим данным, удовлетворяют этим ограничениям. Для всех полигонов ищется общий ограничивающий прямоугольник , который делится на некотороеколичество равных непересекающихся прямоугольников-ячеек , таким образом, чтобы каждая ячейка имела наиболее близкую к квадрату форму.Размеры ячеек выбираются равными характерному размеру полигона.
Затемдля каждой ячейки создается список полигонов, пересекающих ячейку.На этапе сопоставления, когда нужно выяснить, лежит ли точка с определенными координатами в каком-либо из полигонов векторного файла, поэтим координатам явным образом вычисляется номер ячейки, в которой лежит точка, и затем происходит перебор всех полигонов, находящихся в спискедля данной ячейки, с проверкой, лежит ли точка в каком-либо из них методомтрассировки луча.Для определения оптимальных параметров ячеекбыл проведёнанализ вычислительной сложности алгоритма. Пусть , –– размеры ограничивающего прямоугольника; – размер ячейки. При этом считаем, чтоколичество вершин в полигоне ограничено, а значит, можно считать сложность проверки, лежит ли данная точка в заданном полигоне, равной (1).При расчете без индексации алгоритмическая сложность равна произведению числа обрабатываемых точек растра на число полигонов: = (),При индексации(4)рассчитывается число добавлений полигонов в списки ячеек, которое составляет⎧(︂ )︂2⎪⎨ () при > .1 =⎪⎩() при ≤ При поиске,(5)лежит ли точка в одном из полигонов, расчет номераячейки имеет сложность (1), а сопоставление точки с каждым из полигонов,пересекающих эту ячейку:142 = ⎧⎪2⎪⎪⎨ при⎪2⎪⎪⎩ при>.(6)≤При этом, полигоны не пересекаются, и 2 < , поэтому 2 = ()при при ≤ .
Из соотношений 6, 5 видно, что оптимальный размер ячейки ≃ , при этом общая сложность составляет = () + ().Экспериментальная проверка(7)работы данного алгоритма и определение его быстродействия были проведены с использованием данных дистанционного зондирования, отвечающих ограничениям, и использующихся в реальной задаче. Проверка показала, что оптимальное время достигается приразмере ячейки ≃ 3 и близко к оптимальному при < < 10, что подтверждает теоретическую оценку оптимального размера ячейки.Результаты работы алгоритма при оптимальном выборе размера ячейкибыли сравнены с методом квадрантов, на имеющихся данных разработанныйметод работает в среднем на порядок быстрее.Эффективный алгоритм для получения пересечения, объединения, разности полигонов при работе с большими объёмами данных.Типичниым прикладными задачами обработки векторных данных ДЗЗявляются объединение площадей, полученных при обработке данных последовательных пролётов спутников над заданным участком; получение пересечения такой объединённой площади (имеющей обычно весьма сложную форму)с границами административных образований или областями определённоготипа растительности; вычисление разности двух множеств с целью выявления изменений объектов.
Требуется построить алгоритмы, вычисляющие объединение, пересечение, разность таких множеств.Постановка задачиКаждое множество, называемое также операндом,представляет собой набор контуров — многоугольников, которые могут пересекаться между собой (но не самопересекаться).Особенностью практических задач такого типа, возникающих при об15работке данных ДЗЗ, является большой объём информации, поступающейна обработку: количество контуров в каждом операнде может достигать десятков тысяч, количество вершин в каждом контуре, как правило, порядкадесяти, однако в отдельных случаях может достигать тысячи.Решение задачиБыл проведён теоретический анализ существующихалгоритмов, который показал перспективность трёх из них: триангуляции,Леонова и Ватти.Выбранные алгоритмы в существующих реализациях были протестированы на реальных данных, использованы данные о природных пожарах.
Длятестов алгоритмов на первом этапе использована подгруппа файлов, имеющих общий размер 100 килобайт и содержащая 608 контуров.Имеющаяся реализация алгоритма Леонова не прошла по временнымограничениям. Недостатком триангуляционного алгоритма оказалось то, чтопри объединении многих наложенных контуров количество треугольниковрастёт квадратично от числа объединений, а следовательно, при наложениимногих полигонов, появляющихся на одном и том же месте в результатенескольких пролётов КА, будет приводить к сильному возрастанию вычислительной сложности.
Алгоритм Ватти (скан-линейный) был признан наиболее подходящим, однако он потребовал доработки для возможности работыс большими объёмами данных, которые описаны ниже.Исключение рекурсии.Перемещение по спискам в оригинальном коде было реализовано в виде рекурсивного вызова функций обработки элемента. При работе с большими объёмами данных степени самых удалённыхот корня вершин деревьев возрастают до нескольких десятков тысяч. Былисделаны доработки с целью исключить рекурсию. В переработанной версииалгоритма глубина вызовов функций не превышает 5, рекурсия исключена.Таблица попарных пересечений.Была произведена доработка алгоритма, в результате которой необходимый размер массива, содержащегосписки участвующих и не участвующих в пересечении контуров, стал равенне произведению, а сумме числа контуров в операндах.Пересечение фигур в одном операнде.Исследованная реализацияалгоритма Ватти не рассчитана на то, что контуры, принадлежащие одному операнду могут пересекаться.
Была сделана надстройка над алгоритмом.16Каждый из операндов предварительно разбивался на группы контуров (слои),такие, что внутри каждого слоя контуры не пересекались:=∑︁() : ∀ : , ∈ () → ∩ = ∅.(8)=1Для разбиения на слои разработан специальный алгоритм, использующий проецирование ограничивающих прямоугольников фигур на вспомогательный растр. Полученный алгоритм был протестирован на наборе реальных данных, содержащих более 190000 полигонов, и показал стабильную работу и хорошее время работы (до 15 минут).В третьей главепредставлены методы тематической обработки данных дистанционного зондирования Земли. Тематическая обработка данныхдистанционного зондирования — это процесс составления тематических картна основе дешифрирования или распознавания объектов и явлений на космических снимках. К тематической обработке относят широкий спектр методов,позволяющих выделять на изображении интересующие объекты, регионы.Большая часть методов, применяемых к данным дистанционного зондирования, принадлежат к классу методов обработки изображений (машинноезрение, сегментация изображений), с некоторыми особенностями, обусловленными характеристиками данных, отличных от типичных цифровых изображений.Метод выделения выгоревших территорий на космических изображениях.Требуется регулярно и оперативно обнаруживать выгоревшие территории по данным дистанционного зондирования.
Регулярность ставит ограничение на использование только данных низкого разрешения с широкими зонамипокрытия. Такое разрешение не дает возможности использовать текстурныеили геометрические признаки областей, так как средняя площадь лесного пожара близка к размеру одного пикселя, и для отделения выгоревших территорий от невыгоревших остаются только спектральные признаки. Для решения данной задачи были выбраны данные MODIS, так как они доступны дляприема и скачивания, и имеют много спектральных каналов, давая, такимобразом, большие возможности по выделению информативных признаков из17спектральных свойств пикселей.Требование по оперативности обнаружения выгоревших территорий следует из необходимости своевременного слежения за объемами эмиссий продуктов сгорания в атмосферу и приводит к невозможности следовать алгоритмам, требующим серию наблюдений.
Естественным образом это ограничениеснижает точность распознавания, так как невозможна верификация по более поздним данным и анализ временных серий характеристик поверхностиЗемли.Существуют также карты выгоревших территорий, созданные как объединение областей детектированных активных пожаров, недостаточно точные для вычисления площадей отдельных возгораний, но верно отражающиерегионы, в которых произошел пожар, и пригодные для крупномасштабныхоценок.Формально задача имеет следующий вид. Имеется мультиспектральное⃗ ). Также имеетсяизображение земной поверхности низкого разрешения (,список полигонов , каждый из которых включает в себя область, в которойпроизошел пожар.Требуется выделить на изображении пиксели, соответствующие площадям, поврежденным природными пожарами.Метод решенияДля распознавания пикселей выгоревшей территориибыл выбран метод Байесовской классификации в пространстве признаков, составленном из отражающей способности пикселя во всех спектральных диапазонах, содержащихся в изображении.Пространство признаковстроится на основе спектральных характеристик пикселя изображения MODIS, содержащего 36 спектральных каналовв видимом и инфракрасном диапазоне.Важной особенностью этих изображений является разделение каналовпо пространственному разрешению, от 250 до 1000 метров на пиксель.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
