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

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

Осипов Михаил Павлович

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

05.01.01 — Инженерная геометрия и компьютерная графика

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

Нижний Новгород - 2006

РАБОТА ВЫПОЛНЕНА В НИЖЕГОРОДСКОМ ГОСУДАРСТВЕННОМ АРХИТЕКТУРНО - СТРОИТЕЛЬНОМ УНИВЕРСИТЕТЕ

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

Официальные оппоненты: доктор технических наук, профессор Кучуганов Валерий Никанорович

кандидат технических наук, доцент Митин Сергей Вячеславович

Ведущая организация

Саратовский государственный технический университет

Защита диссертации состоится «17» октября 2006 г. в 15 часов на заседании диссертационного совета Д 212.162.04 при Нижегородском государственном архитектурно-строительном университете по адресу: 603950, г. Нижний Новгород, ул. Ильинская, 65, корпус 5, аудитория 202.

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

Автореферат разослан 2006 г.

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

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

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

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

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

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

— значительная доля участия человека, как оператора фотограмметрических преобразований;

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

— сложность работы с комплексом, что создаёт проблемы в обучении операторов.

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

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

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

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

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

Научная новизна состоит:

— в новом методе иерархического восстановления моделей сложных поверхностей;

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

— в методах и алгоритмах триангуляции в заданном контуре и перестройки триангуляционного разбиения с учетом особенностей формы объекта, представляющие собой модификацию методов построения триангуляции Делоне с ограничениями;

— в методах и алгоритмах для проведения измерений на заданной поверхности;

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

Теоретическая и практическая ценность: В диссертации, выполненной в рамках фундаментальной НИР "Разработка теоретических основ алгоритмов и программ геометрии и графики для параллельных технологий проектирования" (ГР № 01970004538, Нижегородский государственный архитектурно-строительный университет), предложены методы, позволяющие автоматизиро-

s

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

Апробация работы:

Результаты диссертационной работы докладывались:

- на 10-й Нижегородской сессии молодых учёных. Технические науки (март 2005 г.).

- на заседании кафедры "Начертательная геометрия и компьютерная графика" (июнь 2005 г.).

- на научно-методической конференции профессорско-преподавательского состава, аспирантов и специалистов (г. Н. Новгород, ВГАВТ, декабрь 2005 г.).

- на 11-й Нижегородской сессии молодых учёных. Технические науки (февраль 2006 г.).

- на поволжской региональной научно-методической конференции "Компьютерная графика и мультимедийные технологии в задачах конструирования и проектирования" (Саратов, СГТУ, апрель 2006 г.).

Публикации: По теме диссертационной работы опубликовано 13 печатных работ, список которых приведён в конце автореферата.

Структура и объём работы: Работа состоит из введения, шести глав, выводов, списка литературы включающего 119 наименований и приложения. Работа содержит 176 страниц машинописного текста, 38 рисунков, 1 таблицу.

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

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

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

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

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

Такими недостатками являются:

— высокая стоимость используемого оборудования;

— ограничение на размер объекта;

— ограничение на расстояние до объекта;

— проблемы в обучении принципам работы с этими методами.

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

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

Работа первого подхода делится на несколько этапов:

— выделение характерных точек, по крайней мере, на двух изображениях;

— образование множества согласованных пар точек, принадлежащих разным снимкам объекта, причем известно, что эта пара двухмерных точек является изображением одной и той же трехмерной точки;

— восстановление координат трёхмерных точек, используя классический фотограмметрический подход;

— восстановление пространственной формы поверхности объекта.

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

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

Данный подход имеет ощутимые преимущества:

— использование существенно меньшего количества точек для восстановления реальной геометрии объекта;

— уменьшение доли ложных соответствий;

— обеспечение более точной реконструкции.

Основной недостаток такого подхода состоит в требовании наличия грубой модели реконструируемого объекта.

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

Список требований к новому подходу, устраняющих недостатки существующих методов:

— общедоступность (разработка методики восстановления поверхности объекта с учётом наличия аппаратуры доступной пользователю);

— удешевление процесса восстановления поверхности объекта;

— автоматизация (уменьшение доли участия человека в ходе процесса);

— универсализм (надёжность работы комплекса независимо от типа и размера обрабатываемых данных);

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

Рис. 1. Общая схема работы нового подхода

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

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

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

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

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

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

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

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

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

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

Для вычисления элементов взаимного ориентирования в диссертационной работе используются два варианта съёмки:

— общий случай съёмки;

— упрощённый случай съёмки.

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

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

Рис. 2. Модель формирования изображения (а), модель стереофотограмметрической

системы (Ь)

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

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

Элементы взаимного ориентирования определяют положение каждого из снимков относительно заданной системы координат. В данном случае используется система координат левого снимка (¡¡¡ХУХ на рис. 2.Ь), принятая в фотограмметрии. Восстановленное положение снимков позволяет для любой точки снимка установить положение проецирующего луча, проходящего через эту точку, относительно заданной системы координат.

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

точка объекта М, соответствующая ей точка на изображении т^т^ и центр проектирования ¿/(ОД лежат на одной прямой (проецирующем луче).

Таким образом, точка объекта М может быть найдена как точка пересечения проецирующих лучей и 32т2, проходящих через соответствующие точки от/ и Ш2 (рис. 2.Ь). В данном случае точки т/ и т2 являются проекциями точки М.

Окончательно, формула для определения пространственных координат точек объекта примет следующий вид:

дг_ =г0х2 у0г2 -2йу}

X = NX^,Y = NYl,Z = NZi, где X/, У), X) - координаты изображения восстанавливаемой точки на левом снимке (точка т/ на рис.2.Ь);

Лг, Кг, — координаты изображения восстанавливаемой точки на правом снимке (точка т2 на рис.2.Ь) в системе координат Б2ХУ2 оси которой параллельны исходной системе З'/ЛТХ;

Хп, Уд, 2о- координаты центра проецирования правого снимка (точка на рис. 2.Ь);

X, У, 2— координаты восстанавливаемой точки объекта (точка Мна рис.2.Ь).

Чтобы найти пространственные координаты точки объекта, необходимо знать положение соответствующих ей точек на изображениях этого объекта. Определение соответствий между двумя изображениями является наиболее сложной частью анализа стереоданных. В главе представлен краткий обзор существующих методов поиска соответствий. Такие методы можно объединить в две категории:

1) методы согласования профилей яркости изображения;

2) методы согласования характерных элементов изображения.

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

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

К таким методам относятся:

— двухэтапный алгоритм;

— иерархический алгоритм;

— использование эпиполярной прямой;

— динамическое программирование;

— использование дополнительных изображений.

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

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

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

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

Общепринятая схема определения краевых включает в себя следующие стадии:

— выделение яркостной составляющей из цветного изображения;

— сглаживание изображения;

— вычисление перепада яркости в каждой точке изображения;

— подавление не максимумов (упрощение контура);

— подавление значений перепада меньше установленного порога.

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

Чтобы уменьшить трудоемкость алгоритма обработки полученных краевых точек, необходимо представить это множество точек в виде некоторого компактного описания. Вид этого компактного представления зависит от типа и формы анализируемого объекта, представленного на изображениях. Контуры большинства объектов легко могут быть представлены набором прямых линий. Поэтому необходимо аппроксимировать множество краевых точек прямыми линиями.

Для реализации такого подхода были разработаны три быстрых алгоритма выделения прямых линий на изображении. Общая идея этих алгоритмов состоит в использовании при формировании прямой информации о градиенте функции яркости в каждой точке изображения. Результаты работы каждого алгоритма зависят от типа анализируемого объекта. Более подробные особенности работы разработанных алгоритмов описаны в тексте диссертации.

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

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

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

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

Основная идея алгоритмов прямого построения состоит в постоянном наращивании к текущей триангуляции по одному треугольнику за шаг. На каждой итерации алгоритм ищет новый треугольник, удовлетворяющий условию Делоне, и подключает его к границе текущей триангуляции. Иными словами, на каждой итерации происходит поиск очередной точки для текущего ребра, принадлежащего границе триангуляции, с целью образования нового треугольника (рис. 3). Для поиска следующей точки необходимо производить перебор всех точек разбиения, из-за чего общая трудоемкость алгоритма составляет О(Ы') арифметических операций для N точек. Поэтому на практике в качестве алгоритма прямого построения применяют клеточный пошаговый алгоритм. Основное отличие этого алгоритма от других алгоритмов прямого построения состоит в использовании идеи клеточной структуры хранения точек, позволяющей сократить среднюю трудоёмкость алгоритма до О(М). Для этого вся область разбивается на клетки. Общее количество квадратов клеток должно быть О (И). Точки и рёбра треугольников сортируются по этим клеткам.

V

Рис. 3. Поиск следующей точки для текущего ребра

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

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

Поиск точки для текущего ребра в традиционном алгоритме прямого построения осуществляется по принципу выбора точки из текущего набора точек, образующей максимальный угол с концами текущего ребра. Существует несколько подходов к решению данной задачи. Использование в одном из подходов тригонометрических функций при определении угла, резко замедляет процесс триангуляционного разбиения и может привести к ошибочным ситуациям в случае обработки сильно вытянутых треугольников. Поэтому на практике используется алгоритм, где трудоемкая операция вычисления тригонометрических функций заменяется операцией определения центра описанной окружности. Тогда искомой будет являться "точка-кандидат", формирующая вместе с концами текущего ребра описанную окружность, центр которой имеет минимальное расстояние до центра окружности С} (т. 05 на рис. 3). Окружность С¡, в данном случае, построена на концах текущего ребра и не содержит внутри себя точек из текущего набора. Основной недостаток данного подхода состоит в том, что для определения искомой точки необходимо обработать все точки текущего набора. То есть операцию вычисления центра описанной окружности необходимо применить ко всем точкам текущего набора.

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

Преимущества модифицированного подхода:

— возможность выбора следующей точки за один проход;

— постепенное сужение набора "точек-кандидатов".

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

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

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

— метод деления треугольника контурной линией;

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

Первый метод работает с уже готовым триангуляционным разбиением и основан на классическом алгоритме "строй, разбивая". Каждый треугольник, пересекающий контурную линию, делится ею на две части. Одна из этих частей представлена треугольником, а вторая — либо треугольником, либо четырёхугольником. В случае образования четырёхугольника он также делится диагональю на два треугольника. Таким образом, были получены треугольники, не пересекающие контурную линию, а, следовательно, правильно аппроксимирующие поверхность. Главный недостаток такого метода заключается в увеличении объема обрабатываемых данных нового триангуляционного разбиения вследствие роста числа треугольников по ходу работы алгоритма. Основное преимущество данного метода состоит в том, что в ходе его работы не образуются вытянутые треугольники, плохо аппроксимирующие поверхность.

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

1) последовательная перестройка рёбер, пересекающих контурную линию. Полученные рёбра будем называть "модифицированными";

2) перестройка "модифицированных" рёбер, пересекающих другие треугольники.

В результате работы первого этапа последнее "модифицированное" ребро лежит на контурном отрезке, а все ребра, ранее пересекающие этот сегмент, изменили своё положение, тем самым исключив пересечение с контурной ли-

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

Трудоёмкость данного алгоритма составляет в среднем О(Ы) операций (Ы - количество перестраиваемых рёбер), в отличие от классического алгоритма "перестраивай и строй", трудоёмкость которого составляет 0(Ы2) операций. В этом алгоритме нет трудоёмких операций определения угла в процессе перестроения и проверок на пересечение перестраиваемого ребра с другими рёбрами, необходимых для работы классического'алгоритма "перестраивай и строй".

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

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

Если представить границу объекта набором контуров (внешним и внутренними), то работа метода разделена на два этапа:

1) удаление треугольников, расположенных вне внешнего контура;

2) удаление треугольников, лежащих во внутренних контурах.

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

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

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

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

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

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

Создание грубой модели на начальном этапе реконструкции автором предложено осуществлять с помощью оператора путем стандартного восстановления поверхности, основанного на соответствии "изображение — изображение". Этот процесс подробно описан в первой главе.

Формально алгоритм иерархического восстановления на каждом этапе выглядит следующим образом:

1. Определение набора характерных точек на изображениях объекта.

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

3. Восстановление пространственных координат характерных точек объекта.

4. Реконструкция поверхности объекта.

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

Идентификация соответствующих точек осуществляется в два этапа:

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

2. Корректировка полученных точек для установления их в точное соответствие. Процесс корректировки осуществляется в некоторой окрестности посредством работы корреляционных методов.

Ключевые моменты работы первого этапа (рис. 4):

1) выбор очередной характерной точки на первом изображении (точка

р1);

2) определение точки на грубой поверхности (точка Р), изображением которой является выбранная точка р 1;

3) проецирование найденной точки поверхности Р на плоскость второго изображения (точка р2).

Основной недостаток такого подхода состоит в требовании наличия грубой модели реконструируемого объекта.

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

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

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

Существует возможность проведения следующих измерений на объекте:

— определение координат точки на поверхности объекта, указанной пользователем;

— вычисление длины выделенного участка на поверхности объекта;

— определение площади поверхности выделенного фрагмента.

Обмер может осуществляться как на проекции объекта, так и непосредственно на самой модели поверхности объекта. В качестве проекции объекта бы-

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

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

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

Рис. 5. Выделенный фрагмент на поверхности объекта, представленной триангуляционным разбиением (светло-серый цвет - треугольники, целиком попавшие внутрь фрагмента (а), тёмно-серый цвет — части фрагмента, заключенные в треугольники, опоясывающие границу фрагмента (а,Ь))

(рис. 5).

а)

Ь)

Метод состоит из четырёх этапов:

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

2) вычисление площади полученных фигур;

3) определение треугольников, целиком попавших внутрь объекта и вычисление их площади;

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

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

Варианты образовании фигур:

1) треугольник отсекает часть фрагмента (рис. б.а)

2) треугольник включает в себя несколько частей фрагмента (рис. б.Ь)

в

гАг

а) Ь)

Рис. 6. Варианты взаимодействия треугольника и фрагмента; треугольник отсекает часть фрагмента (а), треугольник включает в себя несколько частей фрагмента (Ь)

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

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

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

играет направление обхода контура фрагмента. Зная, с какой стороны при движении по контуру расположен фрагмент, площадь многоугольника, чей контур удовлетворяет этому условию обхода, будет считаться положительной, иначе отрицательной. Для этого используется ориентированная площадь многоугольника. Далее аналогично вычисляется ориентированная площадь других многоугольников, образованных от взаимодействия контура фрагмента с данным треугольником. Если сумма полученных площадей (5) не попадает в диапазон [0...5Д], где 5Д — площадь данного треугольника, то происходит последовательное добавление или вычитание из этой суммы площади данного треугольника, пока значение 5 не попадёт в указанный диапазон. В диссертационной работе было доказано, что результатом данных вычислений (5) и является общая площадь частей фрагмента, попавших в данный треугольник.

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

где 5Др — площадь внешнего треугольника на плоскости, 5Д - площадь внешнего треугольника в пространстве (под внешним треугольником подразумевается треугольник, в плоскости которого лежит фигура) и - площадь фигуры в плоскости треугольника.

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

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

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

В главе б приведено описание программного комплекса, основной задачей которого является проведение бесконтактных измерений поверхности объ-

екта. Методы и алгоритмы, включённые в состав этого комплекса, подробно описаны в предыдущих главах.

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

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

Основные этапы работы:

1) на ключевом изображении оператором выделяется контур объекта. Угловые точки контура являются характерными точками объекта;

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

3) соответственные точки автоматически корректируются корреляционной функцией. После проведённой процедуры точки установятся в точное соответствие;

4) производится корректировка калибровочных параметров камер путём анализа полученных точек соответствия;

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

6) поверхность объекта представляется в виде триангуляционного разбиения посредством автоматической работы триангуляции Делоне;

7) производится модификация триангуляции в соответствии с контурными линиями объекта.

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

Работа метода делится на два этапа:

1) создание грубой модели поверхности (рис. 7.а);

2) улучшение поверхности (рис. 7.Ь).

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

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

Рис. 7. Грубая модель поверхности объекта (а), улучшенная модель поверхности объекта (Ь)

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

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

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

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

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

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

а)

Ь)

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

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

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

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

5. Разработаны методы перестройки триангуляционного разбиения с учетом особенностей формы объекта, представляющие собой модификацию методов построения триангуляции Делоне с ограничениями

- метод подразбиения готовой триангуляции в соответствии с контурными линиями;

- метод последовательной перестройки треугольников до соответствия контурным линиям;

6. Разработан эффективный алгоритм триангуляции в заданном контуре, путем сужения выпуклого триангуляционного разбиения до границ объекта (контура);

7. Разработаны быстрые и высокоточные методы и алгоритмы для проведения измерений на заданной поверхности, наиболее важными из которых являются:

- определение расстояния между точками на поверхности объекта;

- вычисление площади поверхности выделенного фрагмента;

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Осипов, М. П. Алгоритм построения триангуляции Делоне для конечного набора точек [Текст] / М. П. Осипов // Сборник трудов Аспирантов и Магистрантов. Технические науки. — Н. Новгород : Нижегород. гос. архит.-строит. ун-т, 2003. - С. 139 - 142.

2. Осипов, М. П. Методы генерации объёмной модели по изображению объекта [Текст] / М. П. Осипов // Сборник трудов Аспирантов и Магистрантов. Технические науки. — Н. Новгород : Нижегород. гос. архит.-строит. ун-т, 2004.-С. 210-213.

3. Осипов, М. П. Задача восстановления ЗИ формы объекта по набору изображений (обзор методов) [Текст] / М. П. Осипов // Совершенствование подготовки учащихся и студентов в области графики, конструирования и стандартизации : межвузовский научно — методический сборник. - Саратов : Саратовский государственный технический университет, 2004. — С. 109 -116.

4. Осипов, М. П. Дистанционные измерения поверхности объекта [Текст] / М. П. Осипов // Проблемы научно - методического и организационного обеспечения учебного процесса по начертательной геометрии и компьютерной графике : сборник трудов всероссийского семинара - совещания заведующих кафедрами графических дисциплин. — Саратов : Саратовский государственный технический университет, 2005. - С. 229 — 234.

5. Осипов, М. П. Выделение объекта на изображении в задаче реконструкции [Текст] / М. П. Осипов // Сборник трудов Аспирантов и Магистрантов. Технические науки. — Н. Новгород : Нижегород. гос. архит.-строит. ун-т, 2005. - С. 222 - 225.

6. Осипов, М. П. Автоматизация процесса восстановления сложных поверхностей [Текст] / М. П. Осипов // Материалы научно-методической конференции профессорско-преподавательского состава, аспирантов и специалистов. Юбилейный выпуск. Часть II. — Н. Новгород : Волжская государственная академия водного транспорта, 2005. — С. 121 — 123.

7. Осипов, М. П. Методы поиска соответствий между изображениями объекта (обзор) [Текст] / М. П. Осипов, С. И. Ротков // Совершенствование подготовки учащихся и студентов в области графики, конструирования и стандартизации : межвузовский научно — методический сборник. — Саратов : Саратовский государственный технический университет, 2006. - С. 59-65.

8. Осипов, М. П. Иерархическое восстановление поверхности объекта [Текст] / М. П. Осипов // Совершенствование подготовки учащихся и студентов в области графики, конструирования и стандартизации : межвузовский научно — методический сборник. — Саратов : Саратовский государственный технический университет, 2006. — С. 72-75.

9. Осипов, М. П. Восстановление формы поверхности объекта [Текст] / М. П. Осипов // Совершенствование подготовки учащихся и студентов в области графики, конструирования и стандартизации : межвузовский научно — методический сборник. — Саратов : Саратовский государственный технический университет, 2006. — С. 89-93.

10. Осипов, М. П. Система проведения бесконтактных измерений на поверхности объекта [Текст] / М. П. Осипов // XI нижегородская сессия молодых учёных. Технические науки. — Н. Новгород : Изд. Гладкова О. В., 2006. — С. 23.

11. Осипов, М. П. Фотограмметрический комплекс дистанционных измерений [Текст] / М. П. Осипов // XI нижегородская сессия молодых учёных. Технические науки. — Н. Новгород : Изд. Гладкова О. В., 2006. - С. 38.

12. Осипов, М. П. Методы вычисления метрических характеристик геометрических объектов [Текст] / М. П. Осипов // Вестник ИжГТУ : периодический научно-теоретический журнал. - Ижевск : ИжГТУ, 2006. Вып. 3. — С. 105112.

13. Осипов, М. П. Методы восстановления поверхности в задаче стереорекон-струкции [Текст] / М. П. Осипов // Вестник ИжГТУ : периодический научно-теоретический журнал. — Ижевск : ИжГТУ, 2006. — Вып. 3. — С. 112-118.

ЛР №020823 от 21.09.98 Подписано к печати^2^^92006г. Формат 60 х 90 1/16. Бумага писчая. Печать офсетная Объем 1 печ. л. Тираж 100 экз. Заказ № _

Нижегородский государственный архитектурно-строительный университет, 603950, Н.Новгород, Ильинская, 65.

Полиграфцентр ННГАСУ, 603950, Н.Новгород, Ильинская, 65.

Введение.

Глава 1. Методы восстановления поверхности объекта по набору изображений.

1.1 Историческое развитие методов моделирования объектов.И

1.2 Методы реконструкции моделей объектов.

1.3 Пассивные методы.

1.4 Активные методы.

1.5 Анализ результатов.

Глава 2. Основы стереорекопструкции.

2.1 Модель камеры.

2.2 Калибровка камеры.

2.2.1 Параметры камеры.

2.2.2 Методы калибровки камеры.

2.3 Работа с некалиброванными изображениями.

2.3.1 Определение внутренних параметров камеры.

2.3.2 Определение внешних параметров камеры.

2.4 Анализ пары снимков.

2.4.1 Взаимное ориентирование снимков.

2.4.2 Определение элементов взаимного ориентирования.

2.4.2.1 Приведение уравнения к линейному виду.

2.4.2.2 Использование упрощённого случая съёмки.

2.4.3 Трансформация снимка, вызванная его переводом в другое положение.

2.4.4 Определение координат точек объекта.

2.5 Определение точек соответствия.

2.5.1 Эпиполярная прямая.

2.5.2 Методы поиска соответствий.

2.5.3 Повышение эффективности методов согласования.

2.5.3.1 Двухэтапный алгоритм.

2.5.3.2 Иерархический алгоритм.

2.5.3.3 Использование дополнительных изображений.

2.5.3.4 Использование условия упорядочивания и динамического программирования.

2.6 Анализ результатов.

Глава 3 Выделение объекта на изображении.

3.1 Постановка задачи.

3.2 Сегментация.

3.3 Построение контура.

3.3.1 Выделение прямых линий на изображении.

3.4 Анализ результатов.

Глава 4 Восстановление формы поверхности объекта.

4.1 Постановка задачи.

4.2 Обзор методов.

4.3 Триангуляция Делоне для конечного набора точек.

4.3.1 Структура хранения элементов триангуляционного разбиения.

4.3.2 Алгоритм построения триангуляции Делоне для конечного набора точек.

4.3.2.1 Выбор первого ребра.

4.3.2.2 Формирование области поиска следующей точки.

4.3.2.3 Принцип выбора следующей точки для построения нового треугольника.

4.3.2.4 Клеточный пошаговый алгоритм.

4.3.2.5 Новый метод выбора следующей точки для построения треугольника.

4.3.2.6 Построение нового треугольника.

4.3.3 Сравнение эффективности модифицированного алгоритма прямого построения с традиционными методами.

4.4 Создание триангуляционного разбиения с учетом особенностей формы объекта.

4.4.1 Подразбиение готовой триангуляции в соответствии с контурными линиями.

4.4.1.1 Поиск треугольника из триангуляционного разбиения, касающегося или включающего в себя один из концов контурного отрезка.

4.4.1.2 Последовательный переход по ветке соседних рёбер к треугольникам, пересекающим контурный отрезок.

4.4.2 Перестройка триангуляционного разбиения в соответствии с контурными линиями.

4.4.3 Сужение выпуклой триангуляции до границ объекта.

4.5 Иерархическое восстановление поверхности объекта.

4.6 Анализ результатов.

Глава 5 Вычисление метрических характеристик объекта.

5.1 Получение координат точки на поверхности объекта по координатам точки на его проекции.

5.2 Определение расстояния между точками по поверхности объекта.

5.3 Вычисление площади поверхности выделенного фрагмента.

5.3.1 Триангуляционное разбиение внутренности фрагмента.

5.3.2 Определение площади поверхности, используя текущее триангуляционное разбиение.

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

5.3.2.2 Формирование фигуры внутри треугольника.

5.3.2.3 Вычисление площади многоугольной фигуры.

5.3.2.4 Алгоритм определения площади части фрагмента отсекаемой треугольником.

5.3.2.5 Новый алгоритм определения площади части фрагмента, попавшего во внутренность треугольника.

5.3.2.6 Определение треугольников, целиком лежащих на объекте и вычисление их площади.

5.4 Анализ результатов.

Глава 6 Построение диалоговой системы. Программная реализация.

6.1 Требования к диалоговой системе.

6.2 Технические характеристики системы.

6.3 Этапы работы комплекса.

6.4 Улучшение поверхности объекта.

6.5 Проведение бесконтактных измерений на поверхности объекта.

6.7 Анализ результатов.

Выводы но диссертации.

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

Долгое время все операции связанные с геометрическими измерениями, выполнялись вручную и поэтому являлись не производительными. Качество и объём работ зависели от субъективных факторов. Появление фотографии положило начало фотограмметрии - пауке об определении формы, размера, и пространственного положения различных объектов посредством измерения их фотографических изображений [6]. Данный подход имеет ряд преимуществ, а именно: высокую точность измерений, большую производительность труда и возможность измерения параметров объекта бесконтактным методом [36]. Обработка снимков производится на различных приборах: стереопроекторах, сте-реоавтографах стереокомпараторах, монокомпараторах и т.д. [35]. Несмотря на высокую стоимость приборов, применение фотограмметрических методов имеет значительные экономические преимущества.

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

Бурное развитие вычислительной техники, которая становится всё более производительной и доступной по цене, а также применение изображений, получаемых цифровыми съемочными системами, позволяют резко удешевить и автоматизировать процесс измерения. Для этого все этапы работы со снимками на дорогостоящих приборах заменяются обработкой изображений на обычном персональном компьютере [60]. На сегодняшний день существует несколько программных продуктов, использующих данный подход (ImageModeler [96], ВИДИС [10], Photomodeler [94] и т.д.). Основные недостатки существующих программных комплексов:

- значительная доля участия человека, как оператора фотограмметрических преобразований;

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

- сложность работы с комплексом, что создаёт проблемы в обучении операторов.

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

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

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

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

Научная новизна состоит:

- в новом методе иерархического восстановления моделей сложных поверхностей;

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

- в методах и алгоритмах триангуляции в заданном контуре и перестройки триангуляционного разбиения с учетом особенностей формы объекта, представляющие собой модификацию методов построения триангуляции Делоне с ограничениями;

- в методах и алгоритмах для проведения измерений на заданной поверхности;

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

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

Апробация работы:

Результаты диссертационной работы докладывались:

- на 10-й Нижегородской сессии молодых учёных. Технические науки (март 2005 г.);

- на заседании кафедры "Начертательная геометрия и компьютерная графика" (июнь 2005 г.);

- на научно-методической конференции профессорско-преподавательского состава, аспирантов и специалистов (г. Н. Новгород, ВГАВТ, декабрь 2005 г.);

- на 11-й Нижегородской сессии молодых учёных. Технические науки (февраль 2006 г.);

- на поволжской региональной научно-методической конференции "Компьютерная графика и мультимедийные технологии в задачах конструирования и проектирования" (Саратов, СГТУ, апрель 2006 г.).

Публикации: По теме диссертационной работы опубликовано 13 печатных работ [107-119].

Структура и объём работы: Работа состоит из введения, шести глав, выводов, списка литературы включающего 119 наименований и приложения. Работа содержит 176 страниц машинописного текста, 38 рисунков, 1 таблицу.

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

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

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

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

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

В главе 5 предложены методы и алгоритмы для проведения измерений на заданной поверхности.

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

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

ВЫВОДЫ ПО ДИССЕРТАЦИИ

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

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

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

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

5. Разработаны методы перестройки триангуляционного разбиения с учетом особенностей формы объекта, представляющие собой модификацию методов построения триангуляции Делоне с ограничениями

- метод подразбиения готовой триангуляции в соответствии с контурными линиями;

- метод последовательной перестройки треугольников до соответствия контурным линиям;

6. Разработан эффективный алгоритм триангуляции в заданном контуре, путем сужения выпуклого триангуляционного разбиения до границ объекта (контура);

7. Разработаны быстрые и высокоточные методы и алгоритмы для проведения измерений на заданной поверхности, наиболее важными из которых являются:

- определение расстояния между точками на поверхности объекта;

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

1. Абламсйко, С. В. Обработка изображений: технология, методы, применение Текст. : Учеб. пособие для вузов / С. В. Абламейко, Д. М. Лагунов-ский. Минск : Амалфея, 2000. - 304 с.

2. Бсллман, Р. Динамическое программирование Текст. / Р. Беллман. М. : Изд-во иностр. лит., 1960. - 400 с.

3. Бирюков, В. С. Цифровые снимки в фотограмметрии Текст. / B.C. Бирюков // Геодезия и картография. 2000. - № 10. - С. 33-36.

4. Бобир, И. Я. Фотограмметрия Текст. / Н. Я. Бобир, А. Н. Лобанов, Г. Д. Федорук. М.: Недра, 1974. - 472 с.

5. Брайс, К. Р. Анализ сцены при помощи выделения областей Текст. / К. Р. Брайс, К. Л. Феннема // Интегральные роботы. М.: Мир, 1975. - Вып. 2. -С.136-159.

6. Василевский, Ю. А. Цифровая фотография Текст. /10. А. Василевский. -М.: Леруша, 1998.-31 с.

7. Веденов, А. А. Математика стереоизображений Текст. / А. А. Веденов. -М.: Знание, 1991.- 48 с.

8. Видеометрический комплекс дистанционных измерений (ВИДИС) Электронный ресурс. Режим доступа: http://www.extech.ru/src/srcrus/ catalog/17/tech/2.htm.

9. И. Гельман, Р. Н. Опыт использования и калибровки цифровых камер при совместной аэрофотосъемке с АФА Текст. / Р. Н. Гельман, М. Ю. Никитин, A. JI. Дунц // Геодезия и картография. 2001. - № 6. - С. 25-31.

10. Гельман, Р. Н. Возможности использования обычных цифровых камер для наземной стереосъемки Текст. / Р. Н. Гельман // Геодезия и картография. -2000.-№4.-С. 39-41.

11. Гельман, Р. Н. Лабораторная калибровка цифровых камер с большой дис-торсией Текст. / Гельман Р. Н., Дунц A. JI. // Геодезия и картография. -2002. № 7. - С. 23-31.

12. Гельман, Р. Н. Точность измерений по снимкам полученным неметрической фотокамерой Текст. / Р. Н. Гельман // Геодезия и картография. -1982. № 7. - С.29-32.

13. Делоне, Б. Н. О пустоте сферы Текст. / Б. Н. Делоне // Изв. АН СССР. -ОМЕН, 1934. № 4. - С. 793-800.

14. Демидов, В. Как мы видим то, что видим Текст. / В. Демидов. М. : Знание, 1987.-240 с.

15. Дубиновский, В. Б. Калибровка снимков Текст. / В. Б. Дубиновский. М. : Недра, 1982.-224 с.

16. Журавель, И. М. Краткий курс теории обработки изображений Электронный ресурс. / И. М. Журавель // Сообщество пользователей Matlab и Simulink. Режим доступа : http://matlab.exponenta.rn/imageprocess/book2/.

17. Игнатенко, А. Методы представления дискретных трёхмерных данных Электронный ресурс. / А. Игнатенко // Графика и мультимедиа. 2003. -Режим доступа : http://cgm.graphicon.ru/obzoryi/metodyipredstavleniyadis kretnyihtrehmernyihdannyih.html.

18. Ильман, В. М. Алгоритмы триангуляции плоских областей по нерегулярным сетям точек Текст. / В. М. Ильман // Алгоритмы и программы. М.: ВИЭМС, 1985.-Т. 88, № 10.-С. 3-35.

19. Ильман, В. М. Экстремальные свойства триангуляции Делоне Текст. / В. М. Ильман // Алгоритмы и программы. М.: ВИЭМС, 1985. - Т. 88, № 10. -С. 57-66.

20. Канаев М. Б. PhotoModeler программа для обработки фотоизображений Электронный ресурс. / М. Б. Канаев // Автоматизация проектирования / Открытые системы. - 1997. - № 2. - Режим доступа : http://osp.aanet.ru /ap/1997/ap2/27.htm.

21. Кармазин, Ю. И. Восстановление моделей архитектурно строительных объектов средствами графики и фотограмметрии Текст. / Ю. И. Кармазин, А. И. Метелкин, С.Д. Шерстников. - В. : Воронежский политехнический институт, 1984. - 55 с.

22. Книжников, Ю. Ф. Компьютерная система для измерения цифровых стереопар при решении нетопографических задач и научных исследованиях Текст. / 10. Ф. Книжников, Р. Н. Гельман // Геодезия и картография. -1999.-№2.-С. 136-149.

23. Кормен, Т. Алгоритмы: построение и анализ Текст. / Т. Кормен, Ч. Лей-зерсон, Р. Ривест. М.: МЦНМО, 2000. - 960 с.

24. Корн, Г. Справочник по математике для научных работников и инженеров Текст. / Г. Корн, Т. Корн. М.: Наука, 1968. - 720 с.

25. Корриган, Д. Компьютерная графика: Секреты и решения Текст. / Д. Корриган ; пер. с англ. Д.А. Куликова. М.: Энтроп, 1995. - 350 с.: ил.

26. Кравцов, А. Общая формулировка задачи внешней калибровки камеры Электронный ресурс. / А. Кравцов, В. Вежневец // Графика и мультимедиа. 2003. - Режим доступа : http://cgm.graphicon.ru/obzoryi/obschaya formulirovkazadachivneshneykalibrovkikameryi.html.

27. Кузнецов, Н. С. Начертательная геометрия Текст. / Н. С. Кузнецов. М.: Высшая школа, 1981.-262 с.: ил.

28. Культин, Н. Б. С/С ++ в задачах и примерах Текст. / Н. Б. Культин. -СПб.: БХВ-Петербург, 2001.-288 с.: ил.

29. Ласло, М. Вычислительная геометрия и компьютерная графика на С++ Текст. / М. Ласло ; пер. с англ. В. Львова. М. : БИНОМ, 1997. - 304 с. : ил.

30. Лобанов, А. Н. Автоматизация фотограмметрических процессов Текст. / А. Н. Лобанов, И. Г. Журкин. М.: Недра, 1980. - 240 с.

31. Лобанов, А. Н. Фотограмметрия Текст. / А. Н. Лобанов. М. : Недра, 1984.-551 с.

32. Лопшиц, А. М. Вычисление площадей ориентированных фигур Текст. / А. М. Лопшиц. М. : Государственное издательство технико-теоретической литературы, 1956. - 64 с.

33. Методы компьютерной обработки изображений Текст. : Учеб. пособие / М. В. Гашников, Н. И. Глумов, Н. 10. Ильясова [и др.] ; под ред. В.А. Сойфера. М.: Физматлит, 2001. - 784 с.: ил.

34. Мусин, О. Р. Диаграмма Вороного и триангуляция Делоне Текст. / О. Р. Мусин // Информационный бюллетень / ГИС Ассоциация. 1999. - Т. 19, №2.-С. 51-52.

35. Назарьев, В. В. Цвет: Компьютерная обработка цветных изображений Текст. / В. В. Назарьев. М.: Эком, 1996. - 80 с.: ил.

36. Огарков, В. М. От триангуляции Делоне к управляемой триангуляции (о настоящих моделях рельефа в ГИС) Текст. / В. М. Огарков // Информационный бюллетень / ГИС Ассоциация. 1999. - Т. 19, № 2. - С. 53-54.

37. Павлидис, Т. Алгоритмы машинной графики и обработки изображений Текст. / Т. Павлидис ; пер. с англ. Н. Г. Гуревича. М. : Радио и связь, 1986.-400 с.: ил.

38. Подбельский, В. В. Язык Си++ Текст. : Учеб. Пособие / В. В. Подбельский. М.: Финансы и статистика, 1998. - 560 е.: ил.

39. Препарата, Ф. Вычислительная геометрия. Введение. Текст. / Ф. Препарата, М. Шеймос ; пер. с англ. С. А. Вичеса, М. М. Комарова. М. : Мир, 1989.-478 с.

40. Роджерс, Д. Алгоритмические основы машинной графики Текст. / Д. Роджерс.-М. : Мир, 1989.-512 с.

41. Ромашок, А. Алгоритмы триангуляции Электронный ресурс. / А. Рома-нюк, А. Сторчак // Компыотеры+Программы. 2001. - № 1. - Режим доступа : http://www.citforum.ru/programming/theory/algtriangl/.

42. Рощин, И. Вывод чёрно-белых изображений с градациями яркости Текст. / И. Рощин // Ваш компьютер. 2002. - № 9. - С. 39-42.

43. Симинеев, А. А. Определение элементов ориентирования снимка из условия коллинеарности векторов в неявном виде Текст. / А. А. Симинеев, JI. Д. Власова // Геодезия и картография. 2000. - № 12. - С. 24-27.

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

45. Скворцов, А. В. Эффективные алгоритмы построения триангуляции Делоне Текст. / А. В. Скворцов, Ю. JI. Костюк // Геоинформатика. Теория и практика / Томский ун-т. 1998. - № 1. - С. 22-47.

46. Спунитис, А. Отсечение полигона ребром: алгоритм KS для получения набора невырожденных полигонов Текст. / А. Спунитис // Computer Modeling & New Technologies. 1999. - Vol. 3. - P. 37-39.

47. Тихомиров, Ю. Программирование трехмерной графики Текст. / Ю. Тихомиров. СПб.: BHV-Санкт-Петербург, 1998. - 256 с.

48. Томпсон, Н. Секреты программирования трехмерной графики для Windows 95 Текст. / Н. Томпсон ; пер. с англ. Е. Матвеева. Спб. : Питер, 1997.-352 с.

49. Тюфлин, Ю. С. Информационные технологии с применением фотограмметрии Текст. / Ю. С. Тюфлин // Геодезия и картография. 2002. - № 2. -С.39-45.

50. Форсайт, Д. А. Компьютерное зрение современный подход Текст. / Д. А. Форсайт, Ж. Понс ; пер. с англ. А. В. Назаренко, И. Ю. Дорошенко М. : Вильяме, 2004. - 928 с.: ил.

51. Фридман, A. JI. Объективно-ориентированное программирование на языке Си++ Текст. / A. JI. Фридман. 2-е изд. - М. : Горячая линия-Телеком, 2001.-232 с.: ил.

52. Фукс, А. Л. Предварительная обработка набора точек при построении триангуляции Делоне Текст. / A. JI. Фукс // Геоинформатика. Теория и практика/Томский ун-т. 1998.-№ 1. - С. 48-60.

53. Хсдли, Дж. Нелинейное и динамическое программирование Текст. / Дж.

54. Хедли. М.: Мир, 1967. - 506 с.

55. Цифровая стереоскопическая модель местности: экспериментальные исследования Текст. /10. Ф. Книжников [и др.]. М.: Научный мир, 2004. -244 с.

56. Чибуиичев, А. Г. О возможностях применения цифровых методов фотограмметрии для решения инженерных задач Текст. / А. Г. Чибуничев // Известия вузов. Геодезия и аэросъемка. 1990. - № 6. - С. 76-82.

57. Шатохин, A. JI. Исследование методов калибровки цифровых камер / А. JI. Шатохин Текст. // Сборник трудов магистрантов. Донецк : ДонНТУ, 2003.-Вып. 2.-С. 343-353.

58. Шикин, Е. В. Компьютерная графика : Динамика, реалистич. изображения Текст. / Е. В. Шикин, А. В. Боресков. М.: Диалог-МИФИ, 1995. - 288 с.

59. Щербак, М. Алгоритм автоматической генерации двумерной конечно элементной сетки Электронный ресурс. / М. Щербак. Режим доступа: http://alglib.sources.ru/articles/g2dgrid.php.

60. Юрченко, В. И. Об учете систематических искажений неметрических снимков Текст. / В. И. Юрченко // Геодезия и картография. 2002. - № 7. -С. 31-38.

61. A multistage stereo method giving priority to reliable matching with self calibration by stereo Text. / O. Nakayama [et al] // IEEE/RSJ International Workshop on Intelligent Robots and Systems (IROS'91). 1991. - Vol. 2. - P. 869874.

62. Becker, S. C. Semiautomatic 3-d model extraction from uncalibrated 2-d camera views Text. / S. C. Becker, V. M. Bove, Jr. // SPIE Proceedings "Visual Data Exploration and Analysis II". 1995. - Vol. 2410. - P. 447-461.

63. Birchfield, S. Depth discontinuities by pixel-to-pixel stereo Text. / S. Birchfield, C. Tomasi // International Journal of Computer Vision. 1999. -Vol. 35, № 3. - P. 269-293.

64. Canny, J. A computational approach to edge detection Text. / J. Canny // IEEE

65. Trans. Pattern Analysis and Machine Intelligence. 1986. - Vol. 8, № 6. - P. 679-698.

66. Caprile, B. Using vanishing point for camera calibration Text. / B. Caprile, V. Torre // International Journal of Computer Vision. 1990. - Vol. 4, № 2. - P. 127-140.

67. Chowdhury, A. R. Face Reconstruction From Video Using Uncertainty Analysis and a Generic Model Text. / A. Roy Chowdhury, R. Chellappa // Computer Vision and Image Understanding (CVIU). 2003. - Vol. 91. - № 1-2. - P. 188213.

68. Cox, I. A Maximum Likelihood Stereo Algorithm Text. /1. Cox, S. Hingorani, S. Rao // Computer Vision and Image Understanding. 1996. - Vol. 63, № 3. -P. 542-567.

69. Debevec, P. Modeling and Rendering Architecture from Photographs: dissertation . doctor of philosophy in computer science Text. / P. Debevec ; chair J. Malik; University of California at Berkeley. Berkeley, 1996. - 154 p.

70. Deng, Y. Color Image Segmentation Text. / Y. Deng, B.S. Manjunath, H. Shin // IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR *99). 1999. - Vol. 2. - P. 446-451.

71. Forstner, W. Photogrammetric standard methods and digital image matching techniques for high precision surface measurements Text. / W. Forstner, A. Pertl // Pattern Recognition in Practice II. 1986. - P. 57-72.

72. Fua, P. A parallel stereo algorithm that produces dense depth maps and preserves image features Text. / P. Fua // Machine Vision and Applications: IN-RIA research report 1369. 1993. - Vol. 6, № 1. - P. 35-49.

73. Gennery, D. B. Modelling the environment of an exploring vehicle by means of stereo vision Text.: PhD thesis / D. B. Gennery. Stanford University, 1980. -151 p.

74. Grimson, W. A Computer Implementation of a Theory of Human Stereo Vision Text. / W. Grimson // Philosophical Transactions of the Royal Society of London. 1981.-Vol. 292, Issue 1058.-P. 217-253.

75. Harman, P. V. Rapid 2D to 3D conversion Text. / P. V. Harman, J. Flack, S. Fox, M. Dowley // SPIE Proceedings "Stereoscopic Displays and Virtual Reality Systems IX". 2002. - Vol. 4660. - P. 78-86.

76. Hoff, W. Surfaces from Stereo: Integrating Feature Matching, Disparity Estimation, and Contour Detection Text. / W. Hoff, N. Ahuja // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1989. - Vol. 11, № 2. - P. 121-136.

77. Knyaz, V. A. Approach to Accurate Photorealistic Model Generation for Complex 3D Objects Text. / V. A. Knyaz, S. Yu. Zheltov // International Archives of Photogrammetry and Remote Sensing. Amsterdam, 2000. - Vol. XXXIII. -part B5/1.-P. 428-433.

78. Koepfler, G. A multiscale algorithm for image segmentation by variational method Text. / G. Koepfler, C. Lopez, J. M. Morel // SIAM Journal on Numerical Analysis (SINUM). 1994. - Vol. 31, № 1. - P. 282-299.

79. Lee, D. T. Two algorithms for constructing a Delanay triangulation Text. / D. T. Lee, B. J. Schacter // International Journal of Computer and Information Sciences. 1980. - Vol. 9, № 3. - P. 219-242.

80. Lhuillier, M. Match propagation for image-based modeling and rendering Text. / M. Lhuillier, L. Quan // IEEE Trans. Pattern Analysis and Machine Intelligence. 2002. - Vol. 24, № 8. - P. 1140-1146.

81. Ma, W. Y. Edge flow: a framework of boundary detection and image segmentation Text. / W. Y. Ma, B. S. Manjunath // IEEE International Conference on Computer Vision and Pattern Recognition (CVPR'97). 1997. - P. 744-749.

82. Marroquin, J. L. Probabilistic Solution of Inverse Problems Text.: Technical Report / J. L. Marroquin. Cambridge : Massachusetts Institute of Technology,1985. 206 p. - AITR-860.

83. McCullagh, M. J. Delanay triangulation of a random data set for isarithmic mapping Text. / M. J. McCullagh, C. G. Ross // The cartographic Journal. -1980.-Vol. 17, №2. -P. 93-99.

84. Niem, W. Robust and Fast Modelling of 3D Natural Objects from Multiple Views Text. / W. Niem // SPIE Proceedings "Image and Video Processing II". San Jose, 1994. - Vol. 2182. - P. 388-397.

85. Nishihara, H. K. PRISM: A practical real-time imaging stereo matcher Text. : Technical Report / H. K. Nishihara. Massachusetts Institute of Technology, 1984.-31 p.-AI Memo 780.

86. Object based representations of spatial images Text. / S. Newsam [et al] // Acta Astronautica. 2001. - Vol. 48, Issue 5-12. - P. 567-577.

87. Ohta, Y. Stereo by Intra- and Inter-Scanline Search Using Dynamic Programming Text. / Y. Ohta, T. Kanade // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1985. - Vol. 7, № 2. - P. 139-154.

88. Owens, R. Stereo matching Electronic resource. / Robyn Owens // On-Line Compendium of Computer. 1997. - Режим доступа : http://homepages.inf. ed.ac.uk/rbf/CVonline/LOCALCOPIES/OWENS/LECTll/node5.html.

89. Photomodeler Electronic resource. Режим доступа http://www.photomodeler .com.

90. Real time correlation based stereo: algorithm implementations and aapplications Text.: Technical Report / 0. Faugeras [et al] // NRIA. 1993. - № 2013. - 49 P

91. Realviz-ImageModeler Electronic resource. Режим доступа : http://www. realviz.com/products/im/index.php.

92. Remondino, F. 3D reconstruction of static human body with a digital camera Text. / F. Remondino // Videometrics VII, SPIE Electronic Imaging. 2003. -Vol. 5013, P. 38-45.

93. Ruppert, J. A Delaunay Refinement Algorithm for Quality 2-Dimentional174 ;

94. Mesh Generation Text. / J. Ruppert. Journal of Algorithms. - 1995. - Vol. 18, Issue 3.-P. 548-585.

95. Sanderson, A. S. Structured Highlight Inspection of Specular Surfaces Text. / A. S. Sanderson, L. E. Weiss, S. K. Nayar // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1988. -Vol. 10, № 1.-P. 44-55.

96. Shirai, Y. Recognition of polyhedrons with a range finder Text. / Y. Shirai // Pattern Recognition. 1972. - Vol. 4. - P. 243-250.

97. Sibson, R. Locally equiangular triangulations Text. / R. Sibson // The Computer Journal. 1978. - Vol. 21, № 3. - P. 243-245.

98. Sobel, I. An isotropic 3X3 image gradient operator Text. /1. Sobel // Machine Vision for Three-Dimensional Scenes. Boston : Academic Press., 1990. - P. 376-379.

99. Тек, H. Volumetric segmentation of medical images by three-dimensional bubbles Text. / H. Тек, В. В. Kimia // Computer Vision and Image Understanding, CVIU. 1997. - Vol. 65, № 2. - P. 246-258.

100. Williams, P. S. Generic texture analysis applied to newspaper segmentation Text. / P. S. Williams, M. D. Alder // IEEE International Conference on Neural Networks (ICNN96). 1996. - Vol. 3. - P. 1664-1669.

101. Wolf, H. G. Structured lighting for upgrading 2D-vision system to 3D Text. / H. G. Wolf // SPIE Proceedings "International Symposium on Laser, Optics and Vision for Productivity in Manufacturing". Micropolis, 1996. - Vol. 2787. - P. 20-25.

102. Xu, G. A Unified Approach to Image Matching and Segmentation in Stereo, Motion, and Object Recognition via Recovery of Epipolar Geometry Text. / G. Xu // VIDERE: J. Computer Vision Research. 1996. - Vol. 1, № 1. - P. 21-56.

103. Основные положения исследования опубликованы в следующих работах:

104. Осипов, М. П. Алгоритм построения триангуляции Делоне для конечного набора точек Текст. / М. П. Осипов // Сборник трудов Аспирантов и Магистрантов. Технические науки. Н. Новгород : Нижегород. гос. архит.строит, ун-т, 2003. С. 139-142.

105. Осипов, М. П. Методы генерации объёмной модели по изображению объекта Текст. / М. П. Осипов // Сборник трудов Аспирантов и Магистрантов. Технические науки. Н. Новгород : Нижегород. гос. архит.-строит. ун-т,2004.-С. 210 -213.

106. Осипов, М. П. Выделение объекта на изображении в задаче реконструкции Текст. / М. П. Осипов // Сборник трудов Аспирантов и Магистрантов. Технические науки. Н. Новгород : Нижегород. гос. архит.-строит. ун-т,2005.-С. 222-225.

107. Осипов, М. П. Система проведения бесконтактных измерений на поверхности объекта Текст. / М. П. Осипов // XI нижегородская сессия молодых учёных. Технические науки. Н. Новгород : Изд. Гладкова О. В., 2006. - С. 23.

108. Осипов, М. П. Фотограмметрический комплекс дистанционных измерений Текст. / М. П. Осипов // XI нижегородская сессия молодых учёных. Технические науки. Н. Новгород : Изд. Гладкова О. В., 2006. - С. 38.

109. Осипов, М. П. Методы вычисления метрических характеристик геометрических объектов Текст. / М. П. Осйпов // Вестник ИжГТУ : периодический научно-теоретический журнал. Ижевск : ИжГТУ, 2006. Вып. 3. - С. 105112.

110. Осипов, М. П. Методы восстановления поверхности в задаче стереорекон-струкции Текст. / М. П. Осипов // Вестник ИжГТУ : периодический научно-теоретический журнал. Ижевск : ИжГТУ, 2006. - Вып. 3. - С. 112-118.