Ракурс
English info@racurs.ru

Статьи и презентации

Библиография PHOTOMOD

Опыт пользователей

Учебные материалы

Материалы конкурса PHOTOMOD Lite

Вики — фотограмметрия

 НОВОСТИ  О КОМПАНИИ  ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ  ДАННЫЕ ДЗЗ  УСЛУГИ  ОБУЧЕНИЕ  ПОДДЕРЖКА  БИБЛИОТЕКА  КОНТАКТЫ  ЛИЧНЫЙ КАБИНЕТ 
 Статьи и презентации  Вики — Фотограмметрия 

Применение TIN с невыпуклой границей в приложениях цифровой фотограмметрии

М.А.Дракин ("Ракурс")

Скачать эту статью (PDF, 606kB)

Построение моделей рельефа является одним из основных приложений цифровой фотограмметрии. При этом, как правило, строится интерполяционная модель, т. е. поверхность восстанавливается как двумерная функция z(x,y) по набору точек (пикетов) с известными трехмерными координатами, причем, как правило, нерегулярному. В общем виде эта задача сформулирована в [2]. На практике обычно используется кусочно-линейная интерполяция либо непосредственно по набору пикетов в виде нерегулярной триангуляционной сети (triangulated irregular network - TIN), либо с предварительной переинтерполяцией на регулярный в плоскости XY массив точек. В последнем случае модель обычно обозначается как DEM (digital elevation model), или матрица высот (рис. 1).

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

TIN широко применяется в современных ГИС и фотограмметрических приложениях. При этом обычно используется триангуляция Делоне, т. е. из всех возможных триангуляций на данном наборе пикетов выбирается тот вариант, в котором треугольники наиболее близки к равносторонним, что повышает вычислительную устойчивость используемых алгоритмов и точность модели. Наиболее распространенные алгоритмы построения и обработки TIN подробно описаны в [1].

Рис. 1
Модели: а - регулярная (DEM); б - нерегулярная (TIN)

Классический подход к триангуляции - построение сети с выпуклой (в проекции на плоскость XY) границей. Это условие существенно для многих алгоритмов построения и обработки TIN. На практике, как правило, входной массив пикетов более или менее равномерно распределен по области. При этом триангуляция Делоне хорошо работает внутри области, однако на границе может возникать множество треугольников с очень острыми углами (рис.2а), что, с учетом конечной точности вычислений на компьютере, приводит к ухудшению стабильности алгоритмов и ошибкам при обработке модели. Кроме того, в пределах области интереса могут иметься специфические регионы, внутри которых отсутствуют пикеты, что также приводит к возникновению "неправильных" треугольников, как на рис. 2б. Поскольку во многих ситуациях для заданного набора входных точек невозможно построить выпуклую триангуляцию, избавленную от подобных граничных эффектов, для исправления ситуации вносят изменения во входные данные, по возможности не ухудшающие точность.

Во-первых, возможно добавление "фиктивных" узлов в TIN, несущественно меняющих профиль моделируемой поверхности, таким образом, чтобы в результате "длинные и узкие" треугольники были разбиты на несколько треугольников более "правильной" формы, как описано, например, в [3]. К сожалению, во многих случаях такая стратегия неприемлема вследствие того, что постановкой задачи не допускается добавление дополнительных пикетов, как, например, на реке на рис. 2б.

Рис. 2
а - краевые эффекты TIN с выпуклой границей;
б - последствия неравномерного распределения пикетов

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

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

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

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

Рис.3
а - исходный массив пикетов;
б - построение TIN с ручным вводом границы
в - автоматическое построение невыпуклого TIN

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

Алгоритм состоит из следующих основных этапов (вся обработка производится в проекции на плоскость XY; координата z рассматривается как атрибут пикета):

1. Строится вспомогательный регулярный TIN по прямоугольной области, которая с некоторым запасом включает в себя все исходные пикеты. Шаг регулярной сетки выбирается таким образом, чтобы общее число вспомогательных узлов M по порядку величины совпадало с числом исходных пикетов N:

M=c*N, где 0,1<c<1

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

2. Для каждого входного пикета ищется треугольник регулярной сетки, в который он попадает. Если в этот треугольник еще не производилось добавление пикетов, он разбивается пикетом на три новых треугольника, которые добавляются в результирующий TIN, а ссылки на них помещаются в запись массива Tidx для данного вспомогательного треугольника. Если же пикеты уже добавлялись в этот треугольник, в соответствующей записи Tidx ищется перебором треугольник результирующего TIN, в который попадает новый пикет, и разбивается на три новых треугольника, с соответствующим обновлением записи в Tidx и результирующего TIN.

3. Проводится оптимизация результирующего TIN (который на данном этапе содержит как исходные пикеты, так и вспомогательные узлы).

4. Производится удаление из TIN вспомогательных узлов, причем порядок перебора этих узлов при помощи специального вспомогательного алгоритма выбирается таким образом, чтобы вначале происходило удаление узлов, расположенных "среди" исходных пикетов (в этом случае вместо набора треугольников, содержащих удаляемый узел, создается новый набор треугольников), а затем - краевых, которые удаляются вместе с содержащими их треугольниками.

5. При необходимости производится повторная оптимизация результирующего TIN.

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

Как несложно видеть, в худшем случае данный алгоритм имеет сложность порядка O(N2). В самом деле, если большая часть исходных пикетов локализована в относительно небольшой области, то добавление пикетов на шаге 2 каждый раз требует перебора всех предыдущих добавленных треугольников, число которых прямо пропорционально числу узлов.

Однако при равномерном распределении пикетов каждый шаг алгоритма имеет сложность порядка O(N): благодаря тому, что число служебных узлов пропорционально числу исходных пикетов, поиск подходящего треугольника на шаге 2 занимает в среднем константное время; операции добавления/удаления узла в TIN локальны и не зависят от N; операция оптимизации TIN также имеет сложность O(N).

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

Следует отметить, что создаваемая автоматическим алгоритмом невыпуклая граница TIN, как правило, имеет меньшую гладкость, чем вводимая оператором для аналогичного набора пикетов. Тем не менее, обычно для дальнейшего применения используется только внутренняя область модели с некоторым отступом от краев, поэтому данная особенность не является критичной.

Описанный алгоритм реализован в модуле построения цифровых моделей рельефа PHOTOMOD DTM цифрового фотограмметрического комплекса PHOTOMOD начиная с версии 3.5.

Литература

1. Скворцов А.В. Триангуляция Делоне и ее применение // Томск: Изд-во Томск. ун-та, 2002.

2. De Floriani L., Bussi S., Magillo P. Triangle-Based Surface Models // Tech. Rep. PDISI-98-05, Computer and Information Science Department (DISI), University of Genova, Italy, 1998.

3. Ruppert J. A Delaunay Refinement Algorithm for Quality 2-Dimensional Mesh Generation // RNR Technical Report, NASA, Ames Research Ctr., Jan 1994.

Подписка на новости 129366, г. Москва
ул. Ярославская, д. 13А, офис 15
Tel   (495) 720-51-27 (многоканальный)
Fax   (495) 720-51-28
Последнее обновление: 21.02.2019© Ракурс, 2004-2019