Диссертация (Автоматическая сшивка радиолокационных изображений земной поверхности при неизвестных элементах внешнего ориентирования), страница 7

Сложность методаполного перебора для поиска совпадения одной точки интереса (поиска 1ближайшего соседа) оценивается O(n), для всех точек – O(n2).При построении BSP-дерева [73] пространство элементов разбивается надва подпространства с равным (или близким к равному) количеством элементовгиперплоскостью размерности k-1, которые аналогично разбиваются далее, пока вкаждом подпространстве не останется не более заданного l элементов (какправило значение l близко к 1). Таким образом, BSP-дерево является бинарным(двоичным) сбалансированным деревом (рисунок 1.8, а), каждый узел которогосвязан с очередной разбивающей гиперплоскостью, а каждый лист деревасодержит не более l элементов.Поиск по BSP-дереву широко используется в визуализации трехмернойкомпьютернойграфики,однакопостроениетакогодеревазначительноосложняется в рассматриваемых многомерных пространствах дескрипторов точекинтереса необходимостью поиска корректной многомерной гиперплоскости.42Разбиение по R-дереву [73] широко применяется для поиска средипротяженных элементов — каждый лист такого дерева является не точкой, аинтервалом допустимых значений (ограничивающий кубоид).

Такой подходпозволяет быстро ответить на вопрос о различных множествах, в которые попалазаданная точка, что не соответствует типу решаемой нами задачи.Kd-дерево или k-мерное дерево [74] является частным случаем BSP-дерева супрощенным способом поиска разделяющих гиперплоскостей. В данном дереверазбиение пространства элементов происходит по одной из координатных осей.Гиперплоскость проводится перпендикулярно выбранной координатной оси черезмедианный для этой оси элемент поиска – разбивает пространство на дваподпространства с равным количество элементов, в которых рекурсивно строятсяk-мерные поддеревья.

В каждом последующем разбиении координатные осициклически чередуются. Пример разбиения двумерного пространства в kd-деревопоказан на рисунке 1.8, б.а)б)Рисунок 1.8 – Пример бинарного сбалансированного дерева (а) и разбиениедвумерной плоскости с 30 точками для формирования kd-дерева с листьями,содержащими одну точку (б)43Таким образом, каждый узел kd-дерева содержит запись о выбранной дляразбиения координатной оси, а также элемент, через который прошлагиперплоскость разбиения.

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

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

Один из популярных способовпредлагаетдоразбиенияпроводитьсортировкуэлементовпокаждойкоординатной оси (k раз), тогда сложность построения данного дерево в худшемслучае оценивается O((k+1)n log n). Поиск 1 ближайшего соседа по kd-дереву всреднем оценивается O(log n).Vp-деревья [75] также являются бинарными, основываются на выборе длякаждого разбиения опорной точки (случайно или путем поиска точки с наибольшейдисперсией расстояний до других точек). Каждый узел такого дерева содержитвыбранную опорную точку и радиус r. Пространство элементов делится на дваподпространства (которые аналогично разбиваются рекурсивно) с помощью44гиперсферы радиуса r с центром в опорной точке.

Значение r выбирается каксреднее расстояние от опорной до всех остальных точек (или до случайнойвыборки из них в случае большого n), что на практике дает разбиение, близкое кмедианному. Каждый лист vp-дерева содержит не более заданного l элементов.Поиск по vp-дереву проводится аналогично поиску по kd-дереву, но сучетом разбиения гиперсферами – при прохождении узла вычисляется расстояниеот заданной точки до опорной и сравнивается с радиусом r данного узла.Сложность построения vp-дерева не зависит от размерности пространства ив худшем случае оценивается O(n log n). Поиск 1 ближайшего соседа по vp-деревув среднем оценивается O(log n), как и у kd-дерева.В [72] и [76] утверждают, что поиск ближайшего соседа по kd-дереву вмногомерных пространствах неэффективен и значительно проигрывает по быстротеvp-дереву.

Действительно, для поиска одной опорной точки, суммарная сложностьопераций(построениеипоиск)уалгоритмасkd-деревомсоставляетO((n (k+1) +1)log n) против O((n+1) log n) для vp-дерева. Однако, в нашем случае(k = 64 для SURF, n ~ 104-107), вследствие многоразового (n) поиска по одному итому же разбиению, разница становится менее заметной. Кроме того, в каждойоперации при работе с vp-деревом присутствует вычисление расстояния от заданнойточки до опорной, что в 64-мерном пространстве занимает гораздо больше времени,чем сравнение всего одной координаты в аналогичных операциях kd-дерева.Приведенныйобзорпоказывает,чтодлясопоставлениямножествдескрипторов точек интереса алгоритма SURF с целью определение опорныхточек целесообразно использовать алгоритм поиска ближайшего соседа сразбиением по kd-дереву.1.5 Постановка задачи на исследованиеДля повышения эффективности и степени автоматизации дешифрированияивторичнойобработкибольшогомассиваРЛИземнойповерхности45целесообразно формирование единой многослойной радиолокационной карты спомощьюсшивки.Существующиеалгоритмысопоставленияисшивкиизображений не позволяют проводить автоматическую сшивку РЛИ принеизвестных элементах внешнего ориентирования.В этой связи необходимо разработать алгоритм автоматической сшивки РЛИземной поверхности при неизвестных элементах внешнего ориентирования.Искомый алгоритм, опираясь на массив РЛИ земной поверхности с попарнымперекрытием, полученных с помощью различных РСА, должен осуществлятьформирование единой многослойной радиолокационной карты с точностью вединицы элементов разрешения.

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

Разработать и провести анализ алгоритмов расчета взаимной ориентациидвух перекрывающихся РЛИ на основе областей с общей семантикой сучетом возможных геометрических искажений РЛИ земной поверхности.4. Выполнитьразработкуипровестианализалгоритмовуточненияориентации нескольких перекрывающихся РЛИ.5. Разработать алгоритм автоматической сшивки РЛИ земной поверхности принеизвестных элементах внешнего ориентирования.466.

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

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