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

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

Кононыхин Андрей Александрович

МОДЕЛИРОВАНИЕ, ВИЗУАЛИЗАЦИЯ И АНАЛИЗ ОБЪЕМНЫХ ТЕЛ НА ОСНОВЕ РАДИАЛЬНЫХ БАЗИСНЫХ ФУНКЦИЙ

Специальность 05 13 11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

7

ООЗ158243

Москва-2007

00315824855831

Работа выполнена в Московском Государственном Техническом Университете им Н Э Баумана

Научный руководитель

доктор технических наук, профессор В В Девятков

Официальные оппоненты

доктор технических наук, профессор А Н Назаров

кандидат технических наук, старший научный сотрудник М М Сыркин

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

Институт Проблем Управления РАН

Защита диссертации состоится « 25 » октября 2007 г в 16 час 30 мин на заседании диссертационного совета Д 212 141 10 при Московском государственном техническом университете им НЭ Баумана по адресу 105005, Москва, 2-я Бауманская ул , д 5.

С диссертацией можно ознакомиться в библиотеке МГТУ им Н Э Баумана

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

105005, Москва, 2-я Бауманская ул , д 5, МГТУ им. Н Э. Баумана, Ученому секретарю диссертационного совета Д 212 141 10

Автореферат разослан «//» ЛУ/Ш&А 2007 г

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

кандидат технических наук:, доцен' С Р Иванов

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

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

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

Объектом исследования является моделирование, визуализация и анализ объемных тел

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

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

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

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

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

3 Разработать новые методы анализа объемных тел, заданных RBF-моделью, исследовать их вычислительную сложность Разработать метод вычисления меры схожести объемных тел, исследовать его вычислительную сложность для применения в задачах классификации

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

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

6 Внедрить и апробировать разработанные методы и программное обеспечение в области ультразвуковой дефектоскопии массивных металлических изделий (валков прокатных станов)

Методы исследования. Исследования в области моделирования объемных тел, на которых базируется настоящая работа, известны по трудам российских (В Л Рвачев, В В Савченко, А А Пасько) и зарубежных (Дж Kapp, М Алекса, Ю Отаке, П Рютер) ученых Также в работе использовались методы математического моделирования, теории функций многих переменных, линейной алгебры, аналитической и вычислительной геометрии, теории вероятности и математической статистики, теории исследования операций и глобальной оптимизации, методы объектно-ориентированного программирования и разработки интеллектуальных систем

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

1 Разработаны новые эффективные методы RBF-моделирования и RBF-вычисления, теоретические оценки вычислительной сложности которых составляют 0(N logN) и O(logN) соответственно Практические тенденции роста времени работы предложенных алгоритмов для рассматриваемого класса задач составляют O(N) и 0(1) для RBF-моделирования и RBF-вычисления соответственно

2 Разработан новый метод адаптивной децимации, сокращающий количество точек исходного множества и существенно (до 1 5 раз) уменьшающий время работы алгоритма RBF-вычисления

3 Разработаны новые методы анализа объемных тел, заданных RBF-моделями, исследована их вычислительная сложность Предложены методы вычисления площади поверхности, объема, координат центра мае с, моментов инерции объемных тел Разработан метод получения и исследования сечений Предложена новая мера схожести объемных тел, исследована ее вычислительная эффективность, предложен метод ее использования для решения задач классификации

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

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

Реализация и внедрение результатов работы.

1 Результаты работы реализованы в аппаратно-программном комплексе «Валок-5», произведенным в ООО «Демас» по заказу ОАО «Северсталь» в 2004-2005 гг Внедрение результатов подтверждается соответствующими актами

2 В Лаборатории Автоматизации Неразрушающего Контроля ОАО «НПО ЦНИИТМАШ» создан автоматизированный стенд для проведения полунатурных испытаний по ультразвуковому сканированию тел вращения, программная часть которого реализует предложенные в работе методы

3 Теоретические результаты работы реализованы в МГТУ им НЭ Баумана на кафедре ИУ-3 в виде материалов лекций учебного курса «Методы обработки изображений»

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

1 Результаты работы были представлены на стенде ООО «Демас» (Demás Ltd) и в соответствующем стендовом докладе на международной выставке «Металлургия и материалы», проходившей с 28 сентября по 02 октября 2005 года в г Стамбул, Турция

2. Мшды и алгоритмы, предлагаемые в работе, были отражены в выступлении на международной научно-технической конференции "Томография", состоявшейся в Москве 22 марта 2005 года.

3. Ключевые идеи работы были изложены в докладе на международном симпозиуме «Образование через науку», проходившем в МГТУ им. 11.Э. Баумана С 17 но 19 мая 2005 года,

4. IIa международной конференции-выставке но нерайрушшшцему контролю и технической диагностики RCNDT-2006, проходившей с 25 по 29 сентября 2006 год! s г. Берлин, I ермания, был сделан секционный доклад, отражающий основное содержание работы.

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

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

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

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

• Я"'

Ч-*::.'' -Л ' Г- • V...

(а)

1Ч:с. I. Точечно-заданный объёмный дефект, полученный н результате сканирования валка прокатного стана ультразвуковой системой — (а); точечно-заданная копия головы человека, полученная системой лазерного

сканирования - (б)

Визуализацией объемного тела называется изображение его поверхности на устройстве вывода (дисплее компьютера) (см. рисунок 2). Наиболее распространённым типом визуализации является триангуляции -4

!

построение сетки и:) треугольнике и, повторяющей форму поверхности объёмного тела.

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

Рис. 2. Визуализация объёмного дефекта нанка прокатного стана - (а);

Первая [лапа является обзорной, В главе рассматриваются существующие методы моделирования объёмных тел. Исследуется классический метод RB['-моделирования и существующие на сегодняшний день подходы к уменьшению сложностей RBF-моделироваинн и RBF-вычислепия. Обозначаются актуальные задачи, требующие решения.

[[а сегодняшний день известно большое количество методов моделирования объёмных тел: явными функциями, параметрическими функциями, ё^ер поверхностями второго порядка, полигональными сетками и неявными функциями. I ia основании исследования и сравнения вышеперечисленных Методов, подробно описанных в первой главе диссертации, показано, что наиболее удобным методом моделирования точечно-заданных объёмных тел является использование неявных функций.

Моделирование точечно-заданного объемного тела неявной функцией заключается и интерполяции точек исходного множества функцией /(х,у,г) = 0. Задача интерполяции в таком виде является некорректной, так как существует бесконечное количество поверхностей, которым могут Принадлежать точки исходного множества, В настоящей главе

(а)

(б)

визуализация копии головы человека - (б)

рассматриваются несколько различных типов неявных функций Однако для выбора наиболее адекватной неявной функции, интерполирующей точки исходного множества, было предложено наложить на нее ограничение наибольшей плавности, достигаемое за счет минимизации функционала, представляющего собой энергию изгиба Функции, одновременно удовлетворяющие требованию принадлежности точек исходного множества поверхности объемного тела и ограничению максимальной плавности, называются Радиальными Базисными Функциями («Radial Basis Function, RBF»)-

N M

fix, У, z) = (||(x> z) - (*.' У,' z,) |)+ YucjSj (x> у»z)' (1)

1=1 J=1

где N - количество точек исходного множества, Л, - коэффициенты интерполяции, базисная функция <p(r) = rm~' 1п(г), в случае, если 2т > t и t -четное, <р(г) = Рт~' в противном случае, t - размерность пространства (равна 3 для трехмерного пространства), от - целое положительное число, II II -Евклидова норма в t - мерном пространстве, М - количество членов полинома степени, как минимум (2m-t) /2, в случае если t - четное, и степени, как минимум, (2m-t+l) /2, в противном случае, c¡ - полиномиальные коэффициенты, g, - полиномиальный базис

Выражение (1) назовем RBF-моделью, а моделирование объемных тел при помощи этого выражения - RBF-моделированием Классический метод RBF-моделирования заключается в интерполяции точек исходного множества RBF-моделью Для RBF-моделирования точечно-заданного объемного тела, исходный набор которого содержит N точек, требуется решить систему из (N+M) линейных уравнений Верхняя оценка вычислительной сложности решения такой системы составляет 0(N3) Назовем эту оценку вычислительной сложности сложностью RBF-моделирования Вычисление значения RBF-модели в какой-либо точке пространства назовем RBF-вычислением Для выполнения RBF-вычисления в какой-либо точке пространства требуется порядка O(N) вычислительных операций Верхнюю оценку сложности RBF-вычисления назовем сложностью RBF-вычисления

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

пребывания валка на технологическом участке сканирования и как можно более быстрым вводом валка в производственный процесс Объемный дефект, обнаруженный ультразвуковым сканером, может задаваться исходным множеством, содержащим до двухсот тысяч точек В этом случае классические методы КВР-моделирования и ЯБР-вычисления неэффективны по причине большого времени работы реализующих их программ (тк решение системы, состоящей из 200 000 линейных уравнений, занимает тысячи часов на современных персональных ЭВМ) В работе Р Шабака была предложена классификация методов интерполяции поверхностей по их вычислительной сложности, ставшая общепринятой метод считается вычислительно-эффективным, если его сложность ЯВР-моделирования составляет 0(Ы \ofsJ4), а сложность КВИ-вычисления - 0(\о%Ы) Поэтому актуальна разработка нового эффективного метода КВР-моделирования, отличающегося от известных методов, имеющих указанные оценки, их практическим уменьшением

Практическое уменьшение времени работы программы, осуществляющей КВР-моделирование и ЫВР-вычисление, можно достичь за счет сокращения количества точек исходного множества N Во многих возникающих на практике задачах исходное множество избыточно, так как содержит большое количество точек, удаление которых практически не скажется на свойствах ЛВР-модели Поэтому помимо разработки теоретически эффективных методов ЯБР-моделирования и ИВР-вычисления, актуально создание метода, производящего адаптивную децимацию исходного множества - удаление наименее информативных для 1ШР-моделирования точек

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

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

Ограничивающим параллелепипедом для множества точек в пространстве называется минимальный по объему параллелепипед с параллельными координатным осям гранями, содержащий это множество точек Разбиению подвергается исходный параллелепипед, подобный ограничивающему, но превосходящий его по габаритам (на 5 -10%)

Рис 3 Основные этапы предложенного метода ЯБР-моделирования

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

ЛГ , =

<

N

" тШЛХ '

о N.

о N < N..

0 N>14, N

1 т оуШШ

(2)

оуЫАХ

<о N<N„

где о - действительное число из интервала (0,1), называемое коэффициентом перекрытия, ИоЫи М^шлх - константы, задающие соответственно минимальное и максимальное количество точек в зоне пересечения

Исходный параллелепипед делится на два пересекающихся, первый из которых содержит первое подмножество, а второй - второе подмножество Исходный параллелепипед, ограничивающий параллелепипед и подмножество точек, полученных в результате разбиения, упаковываются в структуру данных, называемую УЗЛОМ Зададимся константой N1, характеризующей минимально возможное количество точек в УЗЛЕ В случае если количество точек в УЗЛЕ больше, либо равно константе 2Ыи он рекурсивно подвергается повторному разбиению В этом случае УЗЕЛ будет содержать ссылки на два дочерних УЗЛА, полученных в результате разбиения В случае если количество точек в УЗЛЕ меньше константы дальнейшее разбиение не производится Такой УЗЕЛ назовем ЛИСТОМ Все

УЗЛЫ и ЛИСТЬЯ, полученные в процессе разбиения, образуют бинарное дерево Каждый полученный ЛИСТ бинарного дерева содержит ограниченное количество точек - от N1 до 2ЭД

Вторым этапом метода ИВР-моделирования, описанным в параграфе 2 4, является алгоритм адаптивной децимации - отбрасывания малоинформативных точек из ЛИСТЬЕВ полученного на первом этапе бинарного дерева Алгоритм с высокой вероятностью оставляет точки, критичные для наиболее точного ЫВР-моделирования, и отбрасывает остальные Предложенный метод является адаптивным в том смысле, что наименее «важные» точки будут с большей вероятностью и в первую очередь отброшены Важность точки определяется на основании следующих эвристических правил 1) чем выше кривизна поверхности объемного тела в данной точке, тем выше ее важность, 2) чем больше точек находится в окрестности данной точки, тем ниже ее важность

Входными данными для алгоритма являются ЛИСТЬЯ бинарного дерева и коэффициент децимации 3 — процент точек, которые желательно отбросить, взятый от их суммарного количества во всех ЛИСТЬЯХ Принципиально алгоритм делится на два этапа этап оценки важности и этап децимации

На этапе оценки важности каждой точке каждого ЛИСТА ставится в соответствие скалярная величина, называемая относительной важностью Нормальная вариация характеризует кривизну поверхности в точке и определяется путем применения Метода Главных Компонент к множеству точек из окрестности этой точки Окрестность должна иметь размеры и объем, приблизительно совпадающие с минимально-различимой деталью поверхности Нормальная вариация вычисляется как отношение наименьшего собственного числа ковариационной матрицы множества точек из рассматриваемой окрестности к полной вариации этого множества Диапазон значений нормальной вариации составляет от 0 до 1/с1 (Д -размерность пространства), при этом нулевое значение означает полную копланарность точек и отсутствие кривизны, максимальное значение -полную анизотропию точек Абсолютной плотностью ЛИСТА назовем отношение содержащегося в нем количества точек к объему их ограничивающего параллелепипеда Локальной плотностью точки назовем отношение количества точек из ее окрестности к объему этой окрестности Тогда относительная плотность точки является отношением ее локальной плотности к абсолютной Численное значение относительной плотности точки, меньшее единицы, характеризует разреженность точек в ее окрестности, значение большее единицы - скопление Тогда важность точки, согласно сформулированным эвристическим правилам, будет определяться отношением ее нормальной вариации к относительной плотности Относительной важностью точки назовем отношение ее важности к максимальной важности точки ЛИСТА, выраженное в процентах Тогда

величина, равная вычтенной из 100% относительной важности, будет характеризовать вероятность ее удаления в процессе децимации Совокупность таких величин образуют распределение вероятностей удаления точек из ЛИСТА

Каждому ЛИСТУ бинарного дерева поставим в соответствие величину, называемую его полной важностью, равную сумме важностей всех его точек Относительной полной важностью ЛИСТА назовем отношение его полной важности к максимальной полной важности из всех ЛИСТЬЕВ, выраженное в процентах Тогда величина, равная вычтенной из 100% относительной полной важности ЛИСТА, будет характеризовать вероятность выбора этого ЛИСТА для удаления из него точек в процессе децимации Совокупность таких величин образуют распределение вероятностей выбора ЛИСТЬЕВ для децимации

На этапе децимации выбирается случайный ЛИСТ, согласно полученному распределению вероятностей более важные ЛИСТЬЯ будут выбираться с меньшей вероятностью, менее важные - с большей Из выбранного ЛИСТА удалим случайную точку, выбранную согласно распределению вероятностей удаления точек из этого ЛИСТА Более важные точки будут удаляться с меньшей вероятностью, менее важные - с большей Удаление точек производится, пока не будет удалено 5 % от суммарного количества точек во всех ЛИСТЬЯХ, либо пока в каждом ЛИСТЕ не останется заранее заданное минимальное количество точек (например, 20)

Третьим этапом метода ИВР-моделирования, описанным в параграфе 2 5, является локальное 11ВР-моделирование По точкам каждого ЛИСТА бинарного дерева, оставшимся после адаптивной децимации, выполняется классическое ЯВР-моделирование, называемое локальным Локальная КВР-модель ассоциируется с ЛИСТОМ, по точкам которого она была получена

Глобальная ЯВР-модсль задается в виде вычислительной процедуры, описанной в параграфе 2 7 Пусть требуется вычислить значение глобальной ИВР-модели в точке р Предложенный алгоритм проходит рекурсивно по всем УЗЛАМ и ЛИСТЬЯМ бинарного дерева, которым принадлежит точка р В случае если точка р принадлежит одному ЛИСТУ, алгоритм возвращает значение локальной ИВР-модели этого ЛИСТА В случае если точка р принадлежит одновременно двум ЛИСТЬЯМ, результат ЯВР-вычисления определяется путем морфинга локальных ЯВР-моделей этих ЛИСТЬЕВ Значение распространяется рекурсивно «снизу вверх» по УЗЛАМ бинарного дерева Операция морфинга, описанная в параграфе 2 6, служит для «слияния» значений двух локальных ЯВР-моделсй в области пересечения пространств соответствующих ЛИСТЬЕВ {УЗЛОВ) Суть операции морфинга заключается в следующем Чем ближе расположена точка р к первому ЛИСТУ, тем ближе результат ИВР-вычисления к значению локальной ИВР-модели этого ЛИСТА, соответственно, чем ближе расположена точка р ко

второму ЛИСТУ, тем ближе результат RBF-вычисления к значению его локальной RBF-модели

Сложность RBF-моделирования и RBF-вычисления доказывается в параграфе 2 8 Опуская подробное описание, необходимое для соблюдения строгости доказательства, сложность RBF-моделирования составляет 0(N log N) - известная оценка сложности структурирования дискретного множества из N элементов и бинарном дереве Локальное RBF-моделирование, выполняемое для каждого ЛИСТА бинарного дерева, производится за постоянное время, так как количество точек в ЛИСТЕ ограничено в диапазоне от Ni до 2Nt Сложность RBF-вычисления в точке р составляет O(log N) - известная оценка сложности поиска по бинарному дереву Для вычисления значения глобальной RBF-модели осуществляется конечное количество таких поисков, так как количество ЛИСТЬЕВ, которым принадлежит точка р - конечно Вычисление значения локальной RBF-модели ЛИСТА осуществляется за постоянное время, так как ЛИСТ содержит ограниченное в диапазоне от Nt до 2Ni количество точек Таким образом, предложенные методы RBF-моделирования и RBF-вычисления являются эффективными согласно классификации Шабака

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

Метод вычисления площади поверхности предлагается в параграфе 3 2 В его основе лежит триангуляция поверхности объемного тела методом Блументаля, который является развитием известного метода Марширующих Кубов Площади треугольников сетки, аппроксимирующей поверхность, суммируются, результатом чего является приближенное значение площади поверхности Верхняя оценка сложности вычисления площади поверхности составляет 0(п2 logN), где п - количество узлов воображаемой решетки по каждому габаритному размеру, на которой осуществляется триангуляция поверхности

Метод вычисления объема тела, координат центра масс и моментов инерции предложен в параграфе 3 3 и сводится к вычислению интеграла вида

jg(x,y,z)dV, О)

f{x,у, z)<0

по внутреннему пространству/(х,у,z) < О объемного тела, где функция g(x,y,z) может быть равна одному из выражений - 1, х, у, z, х, у2, z2, ху, yz, zx Этот объемный интеграл предлагается свести к поверхностному, применив теорему дивергенций (теорему Остроградского) и заменив его суммой

Римана, учитывая, что поверхность интегрирования представляет собой триангуляцию

т

¡8{х,у,г) (IV = ^ йУ= \ь 4 (4)

/(лу>,г)< 0 /(здг)<0 5 '=1

где т - количество треугольников триангуляции, (х„ уи г,) - точка, принадлежащая г-му треугольнику (например, его центроид - среднее арифметическое координат вершин), куили) - вектор единичной

нормали к г-му треугольнику, А, - площадь г-го треугольника Верхняя оценка сложности вычисления суммы в выражении (4) составляет 0(п logN), т е совпадает с оценкой сложности вычисления площади поверхности, т к объёмный интеграл свелся к поверхностному

Метод вычисления меры схожести точечно-заданных объемных тел и ее применение в задачах классификации предлагается в параграфе 3 5 Классификация объемного тела осуществляется путем его автоматического отнесения к тому или иному классу объемных тел Каждый класс содержит эталонное, наиболее характерное для него объемное тело Решение об отнесении исследуемого объемного тела к какому-либо классу принимается на основании максимальной схожести между ним и эталонным объемным телом данного класса Схожесть между двумя объемными телами предлагается вычислять в два этапа грубого и точного совмещения На этапе грубого совмещения оба точечно-заданных объемных тела масштабируются в единичный куб, смещаются в новые центры координат, совпадающие с их центроидами, выравниваются вдоль своих главных направлений путем преобразования поворота Главные направления рассчитываются методом главных компонент На этапе точного совмещения осуществляется преобразование точек исходного множества исследуемого объемного тела, состоящее из масштабирования в я раз, поворота на углы {ос, Д у) вокруг координатных осей и параллельного переноса на (т, п, к) вдоль координатных осей Координаты каждой точки из преобразованного множества исследуемого объемного тела последовательно подставляется в ЯБР-модель эталонного объемного тела, возводятся в квадрат и суммируются, в результате чего получается функция Е(я, а, Д у, т, п, к), называемая энергией ошибки и зависящая от параметров преобразования нелинейно Минимизация энергии ошибки дает оптимальные параметры преобразования, при которых оба объемных тела максимально совмещаются Энергия ошибки является мерой схожести объемных тел чем меньше ее значение, тем больше объемные тела походят друг на друга В отличие от известной меры схожести, используемой в методе Итерационных Ближайших Точек и имеющей верхнюю оценку вычислительной сложности, равную 0(И2), вычисление предложенной меры осуществляется за количество операций, пропорциональное 0(N logN)

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

70

во

50

<■> О 40

е 30

1—

20

10

0

)

■л X

/ш» ^ Д.

Ъг

-N1=60 -N1=50 N1=40 N1=30

100000 N

15

о 10

£ 5

0

1

и»***

1

-N1=60 -N1-50 N1=40 N1=30

О 50000 100000 150000 200000

N

Рис 4 Зависимость времени ЯВР-моделирования (Тт) и времени ЯВИ-вычисления (Те) от количества точек исходного множества для N1 - 30 60

Вычислительный эксперимент, приведенный в параграфе 4 2, применяет предложенные в работе методы к точечно-заданному объемному телу, имитирующему объемный дефект валка прокатного стана Количество точек, которыми задано объемное тело, варьировалось от 5 ООО до 200 ООО Целью эксперимента было нахождение зависимостей времени ЯВР-моделирования и ИВР-вычисления от количества точек исходного множества для различных значений параметра N1 (от 20 до 120) и определение оптимального значения этого параметра В результате наилучшее, практически линейное время работы алгоритма ЯБР-моделирования и практически постоянное время ЯВР-вычисления достигалось при значениях N1 из диапазона от 30 до 60 Практически линейное время ИВР-моделирования, не смотря на теоретическую оценку вычисленной сложности 0(М достигается за счет того, что структурирование точек исходного

множества в бинарном дереве осуществляется довольно быстро и основное время алгоритм осуществляет локальные 11ВР-моделирования для ЛИСТЬЕВ этого дерева Так как количество ЛИСТЬЕВ пропорционально N и каждое локальное КВР-моделирование осуществляется за постоянное время, время работы всего алгоритма будет примерно пропорционально N (см рисунок 4)

Аналогично, при ТШР-вычислении в некоторой точке р, время поиска по бинарному дереву относительно мало, и основное время алгоритм осуществляет вычисление значений локальных ШЗР-моделей ЛИСТЬЕВ, пространству которых принадлежит точка р Так как количество таких ЛИСТЬЕВ ограничено, и вычисление значения локальной ИВР-модели осуществляется за постоянное время, вычисление значения глобальной ИВР-модели будет также осуществляться за примерно постоянное время (см рисунок 4)

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

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

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

2 Разработаны новые методы и вычислительно-эффективные алгоритмы КВР-моделирования и ЯБР-вычисления Получены верхние теоретические оценки вычислительной сложности разработанных методов, составляющие 0(N logN) для алгоритма КВР-моделирования и 0(1о^И) для алгоритма ЮЗР-вычисления, притом, что известные оценки классических алгоритмов составляют, соответственно, 0(И3) и О(И)

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

раза) Применение метода не увеличивает полученной теоретической оценки сложности RBF-моделирования

4 Разработана новая методика анализа объемных тел, заданных RBF-моделями, включающая эффективные алгоритмы, имеющие существенно более низкую вычислительную сложность, по сравнению с известными аналогичными алгоритмами Предложены алгоритмы вычисления площади поверхности, объема, координат центра масс и моментов инерции, имеющие низкую оценку вычислительной сложности 0(п2 logN), по сравнению с оценкой тривиальных алгоритмов - 0(п3 N) Новые алгоритмы вычисления геометрических характеристик сечений имеют низкую оценку вычислительной сложности 0(п logN), по сравнению с оценкой тривиальных алгоритмов - 0(n2N) Предложена новая вычислительно-эффективная мера схожести объемных тел для ее применения в задачах классификации Оценка вычислительной сложности новой меры схожести составляет 0(N logN), в отличие от известной оценки 0(N2)

5 Проведены вычислительные эксперименты, в результате которых выявлены оптимальные параметры работы алгоритмов RBF-моделирования и RBF-вычисления в реальных условиях (о=5%, Novimin = 30, NovlMAX = 50, Ni = 30 60) Установлено, что при оптимальных параметрах сложность RBF-моделирования составляет приблизительно O(N), а сложность RBF-вычисления - 0(1), что существенно (в log N раз) ниже полученных теоретических оценок

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

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

Сформулируем выводы по результатам выполненной работы

1 Полученные теоретические оценки сложностей RBF-моделирования и RBF-вычисления и улучшающие их экспериментальные результаты позволяют применять Радиальные Базисные Функции для моделирования, визуализации и анализа объемных тел, заданных сотнями тысяч точек

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

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

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

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

Работы по теме диссертации.

1 Кононыхин А А, Самедов Я Ю Трехмерное моделирование дефектных областей по данным ультразвукового контроля // Заводская лаборатория Диагностика материалов -2006 -№6, Т 72 - С 31-34

2 Кононыхин А А Развитие методики моделирования, анализа и визуализации объемных тел в трехмерном пространстве на основе функций радиального базиса // ИНФОРМАТИКА И СИСТЕМЫ УПРАВЛЕНИЯ В XXI ВЕКЕ Сборник трудов №3 молодых ученых, аспирантов и студентов - М Изд-во МГТУ им Н Э Баумана, 2005 - С 3-16 ISBN 5-7038-2645-2

3 Кононыхин А А Методика распознавания объемных тел, заданных точками поверхности с использованием функций радиального базиса // ОБРАЗОВАНИЕ ЧЕРЕЗ НАУКУ Сборник докладов международного симпозиума - М Изд-во МГТУ им Н Э Баумана, 2006 - С 366-373 ISBN 5-7038-2715-9

4 Кононыхин А А Развитие методики моделирования, анализа и визуализации объемных тел в трехмерном пространстве на основе функций радиального базиса // Тезисы докладов международной конференции «Образование через науку» (Москва, 17-19 мая 2005 г) - М Изд-во МГТУ им НЭ Баумана, 2005 - С 114

5 Самедов Я Ю, Кононыхин А А Трехмерная визуализация результатов ультразвукового контроля // Тезисы научно-технической конференции "Томография" (Москва, 22 марта 2005г) - М, 2005 - С 8

6 Неразрушающий контроль прокатных валков / Я Ю Самедов, В Г Щербинский, В П Ромашов, А А Кононыхин, В В Кутянин // Труды шестого конгресса прокатчиков (Липецк, 18-21 октября 2005г ) - М, 2005 -С 505-507

7 Samedov Y, Kononykhin A Inner Defects Visualization Based on Ultrasonic Scanning // ECNDT-2006 Proceedings, Topic Fr 2 3 2 (Berlin, September 2529,2006) -2006 - 7 p

Подписано к печати 18 09 07 Заказ № 640 Объем 1,0 печ л Тираж 100 экз Типография МГТУ им Н Э Баумана 105005, Москва, 2-я Бауманская ул , д 5 263-62-01

ВВЕДЕНИЕ.

Глава 1. МЕТОДЫ МОДЕЛИРОВАНИЯ, ВИЗУАЛИЗАЦИИ И

АНАЛИЗА ОБЪЁМНЫХ ТЕЛ.

1. ^Моделирование явными функциями.

1.2. Моделирование параметрическими функциями.

1.3. Моделирование суперповерхностями второго порядка.

1.^Моделирование полигональными сетками.

1.5. Моделирование неявными функциями.

1.6. Выводы по методам моделирования.

1.7.0бзор методов моделирования неявными функциями.

1.7.1. Моделирование функциями знаковых расстояний.

1.7.2Моделирование скользящими наименьшими квадратами.

1.7.3.Моделирование Радиальными Базисными Функциями.

1.7.3.1.Моделирование с использованием нормалей.

1.7.3.2.Моделирование с использованием несущей функции

1.7.4.Выводы по методам моделирования неявными функциями .48 1 ^.Вычислительная сложность моделирования Радиальными Базисными Функциями и методы её оптимизации.

1.8.1.Метод «Быстрых Вычислений».

1.8.2.Метод компактных носителей.

1.8.3.Многоуровневые методы.

1.8.4.Иерархический метод разбиения единицы.

1.8.5.Выводы по методам оптимизации вычислительной сложности.

1.9.Визуализация объёмных тел, заданных Радиальными Базисными Функциями.

1.10. Анализ объёмных тел, заданных Радиальными Базисными Функциями. Классификация объёмных тел.

1.11. Применения RBF-моделей объёмных тел.

1.12 .Выводы по главе.

Глава 2. МЕТОД RBF-МОДЕЛИРОБАНИЯ НА ОСНОВЕ ЛОКАЛЬНОГО МОРФИНГА С ПРИМЕНЕНИЕМ АДАПТИВНОЙ

ДЕЦИМАЦИИ.

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

2.2.0писание метода.

2.3.Структурирование исходных данных в бинарном дереве.

2.4.Адаптивная децимация.

2.5.Получение локальной RBF-модели.

2.6.Морфинг объёмных тел.

2.7. Получение глобальной RBF-модели методом локального морфинга.

2.8.Получение верхних оценок вычислительной сложности.

2.9.Выводы по главе.

Глава 3. АНАЛИЗ ОБЪЁМНЫХ ТЕЛ, ЗАДАННЫХ RBF-МОДЕЛЯМИ

3.1.Краткое описание методов.

3.2.Вычисление площади поверхности объёмного тела.

3.3. Вычисление объёма, координат центра масс и моментов инерции тела.

3.4.Построение и анализ сечений объёмного тела.

3.5.Вычисление меры схожести объёмных тел и её применение в задачах классификации.

3.6.Выводы по главе.

Глава 4. РЕАЛИЗАЦИЯ, ЭКСПЕРИМЕНТАЛЬНЫЕ

ИССЛЕДОВАНИЯ И ИСПЫТАНИЯ РАЗРАБОТАННЫХ МЕТОДОВ

4.1.Программная реализация разработанных методов.

4.2.Вычислительный эксперимент по выяснению влияния параметров и оценке сложности алгоритмов RBF-моделирования, RBF-вычисления.

4.3.Промышленное применение разработанных методов в области ультразвукового контроля прокатных валков.

4.4.Выводы по главе.

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

Настоящая работа в её теоретической части посвящена решению актуальной задачи развития методов моделирования объёмных тел, а в прикладной - реализации этих методов для промышленного использования. Объёмным телом будем называть замкнутую геометрическую фигуру в трёхмерном Евклидовом пространстве, имеющую произвольную форму. Современные технические системы сбора информации об объёмных телах, такие как: лазерные установки [55], механические зондирующие устройства, ультразвуковые сканеры [18] и системы стереоскопического компьютерного зрения, - получают множество точек в трехмерном пространстве, принадлежащих поверхности исследуемого объёмного тела (см. рисунок 1). Такое множество точек назовём исходным, а заданное им объёмное тело -точечно-заданным. а) (б)

Рис. 1. (а) - точечно-заданный объёмный дефект, полученный в результате сканирования валка прокатного стана ультразвуковой системой; (б) - точечно-заданная копия головы человека, полученная системой лазерного сканирования

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

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

Рис. 2. (а) - визуализация объёмного дефекта валка прокатного стана; б) - визуализация копии головы человека

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

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

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

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

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

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

На сегодняшний день известно большое количество методов моделирования объёмных тел [41]: явными функциями, параметрическими функциями, суперповерхностями второго порядка, полигональными сетками и неявными функциями. На основании исследования и сравнения вышеперечисленных методов, подробно описанных в Главе 1 настоящей работы, показано, что наиболее удобным методом моделирования точечно-заданных объёмных тел является использование неявных функций [17].

Для того чтобы сформулировать особенности метода моделирования неявными функциями, введём ряд понятий и определений. Функция / называется задающей, если она определяет скалярное поле в трёхмерном Евклидовом пространстве, т.е. каждой точке из области определения функции /ставит в соответствие действительное число d = f(x,y,z). Задающая функция обладает следующими свойствами:

1) f(x,y,z) = 0 для любой точки с координатами (x,y,z), лежащей на поверхности объёмного тела;

2) f(x,y,z) = d < О для любой точки с координатами (x,y,z), лежащей внутри объёмного тела;

3) f(x,y,z) =d> 0 для любой точки с координатами (x,y,z), лежащей вне объёмного тела;

4) абсолютное значение d характеризует удаленность точки с координатами (x,y,z) в трехмерном пространстве от поверхности объёмного тела.

Функция f(x,y,z) = 0 называется неявной функцией, а геометрическое место точек S = { (x,y,z)\ f(x,y,z) = 0 } - неявной поверхностью. Объёмное тело, поверхность которого задаётся неявной функцией, назовём неявным объёмным телом. Важным свойством функции / является знак её значения, позволяющий классифицировать все точки трёхмерного пространства на лежащие внутри и вне объёмного тела. Это свойство позволяет использовать численные методы дифференциального и интегрального исчисления для анализа объёмного тела. Например, вычисление объёма тела заключается в интегрировании единичной функции по области f(x,y,z) > 0.

Моделирование точечно-заданного объёмного тела неявной функцией заключается в интерполяции точек исходного множества функцией f(x,y,z) = 0. Задача интерполяции в таком виде является некорректной, так как существует бесконечное количество поверхностей, которым могут принадлежать точки исходного множества. В Главе 1 настоящей работы рассматриваются несколько различных типов неявных функций. Однако для выбора наиболее адекватной неявной функции, интерполирующей точки исходного множества, было предложено [53] наложить на неё ограничение максимальной плавности, достигаемое за счёт минимизации функционала, представляющего собой энергию изгиба. Функции, одновременно удовлетворяющие требованию принадлежности точек исходного множества поверхности объёмного тела и ограничению максимальной плавности, называются Радиальными Базисными Функциями («Radial Basis Function, RBFv> [53]):

N M где N - количество точек исходного множества; Л,- - коэффициенты интерполяции; базисная функция (р(г) = г2™'11п(г), в случае, если 2т > tut -четное, <р(г) = г2"1"' в противном случае; / — размерность пространства (равна 3 для трёхмерного пространства); т - целое положительное число; || || -Евклидова норма в / - мерном пространстве; М - количество членов полинома степени, как минимум (2m-t) /2, в случае если t - чётное, и степени, как минимум, (2m-t+l) / 2, в противном случае; Cj -полиномиальные коэффициенты; gj- полиномиальный базис.

Выражение (1) назовём RBF-моделью, а моделирование объёмных тел при помощи этого выражения - RBF-моделированием. Классический метод RBF-моделирования заключается в интерполяции точек исходного множества RBF-моделью. Для RBF-моделирования точечно-заданного объёмного тела, исходный набор которого содержит N точек, требуется решить систему из (N+M) линейных уравнений [8]. Верхняя оценка вычислительной сложности решения такой системы составляет 0(N3) [61]. Назовём эту оценку вычислительной сложности сложностью RBF-моделирования. Вычисление значения RBF-модели в какой-либо точке пространства назовём RBF-вычислением. Для выполнения RBF-вычисления в какой-либо точке пространства, требуется порядка 0(N) вычислительных операций. Верхнюю оценку сложности RBF-вычисления назовём сложностью RBF-вычисления.

Современные технические системы сканирования объёмных тел производят исходные множества, состоящие из десятков и сотен тысяч точек. При сканировании с высоким разрешением крупногабаритных объёмных тел количество точек исходного множества может достигать миллиона. Согласно указанным оценкам вычислительной сложности, даже при количестве точек, равном десяткам тысяч, время работы алгоритмов RBF-моделирования и RBF-вычисления становится неприемлемым. Например, при ультразвуковом сканировании валков прокатных станов для выявления и анализа внутренних дефектов время моделирования, визуализации и анализа не должно превышать нескольких минут. Это связано с ограничением времени пребывания валка на технологическом участке сканирования и как можно более быстрым вводом валка в производственный процесс. Объёмный дефект, обнаруженный ультразвуковым сканером, может задаваться исходным множеством, содержащим до двухсот тысяч точек. В этом случае классические методы RBF-моделирования и RBF-вычисления неэффективны по причине большого времени работы реализующих их программ (т.к. решение системы, состоящей из 200 000 линейных уравнений, занимает тысячи часов на современных персональных ЭВМ). В работе Р. Шабака [81] была предложена классификация методов интерполяции поверхностей по их теоретическим оценкам вычислительной сложности, ставшая общепринятой: метод считается вычислительно-эффективным, если его сложность RBF-моделирования составляет 0(N logN), а сложность RBF-вычисления -0(logN). Поэтому актуальна разработка нового эффективного метода RBF-моделирования, отличающегося от известных методов, имеющих указанные оценки, их практическим уменьшением.

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

Актуальность темы в научном аспекте определяется:

• необходимостью разработки вычислительно-эффективных методов RBF-моделирования и RBF-вычисления точечно-заданного объёмного тела, исходное множество которого содержит десятки и сотни тысяч точек;

• необходимостью разработки и исследования эффективности методов анализа объёмных тел, заданных RBF-моделями.

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

Объектом исследования является моделирование, визуализация и анализ объёмных тел.

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

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

Задачи исследования.

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

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

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

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

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

6. Внедрить и апробировать разработанные методы и программное обеспечение в области ультразвуковой дефектоскопии массивных металлических изделий (валков прокатных станов).

Методы исследования.

Исследования в области моделирования объёмных тел, на которых базируется настоящая работа, известны по трудам российских (B.JL Рвачёв, В.В. Савченко, А.А. Пасько) и зарубежных (Дж. Карр, М. Алекса, Ю. Отаке, П. Рютер) учёных. При решении поставленных задач использовались методы математического моделирования, теории функций многих переменных, линейной алгебры, аналитической и вычислительной геометрии, теории вероятности и математической статистики, теории исследования операций и глобальной оптимизации, методы объектно-ориентированного программирования и разработки интеллектуальных систем.

Научная новизна.

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

1. Разработаны новые эффективные методы RBF-моделирования и RBF-вычисления, теоретические оценки вычислительной сложности которых составляют 0(N logN) и 0(logN) соответственно. Практические тенденции роста времени работы предложенных алгоритмов для рассматриваемого класса задач составляют 0(N) и 0(1) для RBF-моделирования и RBF-вычисления соответственно.

2. Разработан новый метод адаптивной децимации, сокращающий количество точек исходного множества и существенно (до 1.5 раз) уменьшающий время работы алгоритма RBF-вычисления.

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

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

Практическая ценность работы.

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

На защиту выносятся следующие положения.

1. Новый вычислительно-эффективный метод RBF-моделирования.

2. Методика анализа объёмных тел.

3. Программная реализация предложенных методов и их применение в области дефектоскопии прокатных валков.

Реализация и внедрение результатов работы.

1. Результаты работы реализованы в аппаратно-программном комплексе «Валок-5», произведенным в ООО «Демас» по заказу ОАО «Северсталь» в 2004-2005 гг. Внедрение результатов подтверждается соответствующими актами.

2. В Лаборатории Автоматизации Неразрушающего Контроля ОАО НПО «ЦНИИТМАШ» создан автоматизированный стенд для проведения полунатурных испытаний по ультразвуковому сканированию тел вращения, программная часть которого реализует предложенные в работе методы.

3. Теоретические результаты работы реализованы в МГТУ им. Н.Э. Баумана на кафедре ИУ-3 в виде материалов лекций учебного курса «Обработка изображений в информационных системах».

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

1. Результаты работы были представлены на стенде ООО «Демас» (Demas Ltd.) и в соответствующем стендовом докладе на международной выставке «Металлургия и материалы», проходившей с 28 сентября по 02 октября 2005 года в г. Стамбул, Турция.

2. Методы и алгоритмы, предлагаемые в работе, были отражены в выступлении на научно-технической конференции "Томография", состоявшейся в Москве 22 марта 2005 года.

3. Ключевые идеи работы были изложены в докладе на международном симпозиуме «Образование через науку», проходившем в МГТУ им. Н.Э. Баумана с 17 по 19 мая 2005 года.

4. На международной конференции-выставке по неразрушающему контролю и технической диагностики ECNDT-2006, проходившей с 25 по 29 сентября 2006 года в г. Берлин, Германия, был сделан секционный доклад, отражающий основное содержание работы.

Публикации.

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

Структура и объем работы.

Диссертационная работа состоит из введения, четырёх глав, заключения и списка литературы, занимающих 165 страниц текста, в том числе 49 рисунков на 44 страницах, 10 таблиц на 10 страницах, список использованной литературы из 91 наименования на 10 страницах.

ВЫВОДЫ

Сформулируем выводы по результатам выполненной работы:

1. Полученные теоретические оценки сложностей RBF-моделирования и RBF-вычисления и улучшающие их экспериментальные результаты позволяют применять Радиальные Базисные Функции для моделирования, визуализации и анализа объёмных тел, заданных сотнями тысяч точек.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

2. Разработаны новые методы и вычислительно-эффективные алгоритмы RBF-моделирования и RBF-вычисления. Получены верхние теоретические оценки вычислительной сложности разработанных методов, составляющие 0(N logN) для алгоритма RBF-моделирования и 0(logN) для алгоритма RBF-вычисления, притом, что известные оценки классических алгоритмов составляют, соответственно, 0(N3) и 0(N).

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

4. Разработана новая методика анализа объёмных тел, заданных RBF-моделями, включающая эффективные алгоритмы, имеющие низкую вычислительную сложность, по сравнению с известными. Предложены алгоритмы вычисления площади поверхности, объёма, координат центра масс и моментов инерции, имеющие низкую у оценку вычислительной сложности 0(п logN), по сравнению с оценкой тривиальных алгоритмов - 0(п3 N). Новые алгоритмы вычисления геометрических характеристик сечений имеют низкую оценку вычислительной сложности 0(п logN), по сравнению с у оценкой тривиальных алгоритмов - 0(п N). Предложена новая вычислительно-эффективная мера схожести объёмных тел для её применения в задачах классификации. Оценка вычислительной сложности новой меры схожести составляет 0(N logN), в отличие от оценки известной - 0(N2).

5. Проведены вычислительные эксперименты, в результате которых выявлены оптимальные параметры работы алгоритмов RBF-моделирования и RBF-вычисления в реальных условиях (о=5%, Novimin = 30, Novimax = 50, Nt = 30.60). Установлено, что при оптимальных параметрах сложность RBF-моделирования составляет приблизительно 0(N), а сложность RBF-вычисления - 0(1), что существенно ниже полученных теоретических оценок.

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

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

1. Аджиев В., Пасько А., Савченко В., Сурнн А. Моделирование форм с использованием вещественных функций // Открытые системы. - 1996. -№05. -С. 14-18

2. А.В. Аттетков, С.В. Галкин, B.C. Зарубин. Методы оптимизации М.: МГТУ, 2003. - 440 с.

3. Берёзкин Е.Н. Курс теоретической механики М.: МГУ, 1974. - 641 с.

4. Будагьянц Н.А, Карский В.Е. Литые прокатные валки. М.: Металлургия, 1995.-368 с.

5. Р.К. Вафин, A.M. Покровский, В.Г. Лешковцев. Прочность термообрабатываемых прокатных валков М.: МГТУ, 2004. - 264 с.

6. Джонсон Н., Лион Ф. Статистика и планирование эксперимента в технике и науке / Пер. с англ. М.: Мир, 1980. - 511 с.

7. Джорж А., Лю Дж. Численное решение больших разреженных систем уравнений / Пер. с англ. М.: Мир, 1984. - 333 с.

8. Д. Каханер, К. Моулер, С. Нэш. Численные методы и программное обеспечение / Пер. с англ. под ред. Х.Д. Икрамова. М.: Мир, 1998. -575 с. ISBN 5030024328.

9. Кононыхин А.А. Методика распознавания объёмных тел, заданных точками поверхности с использованием функций радиального базиса // ОБРАЗОВАНИЕ ЧЕРЕЗ НАУКУ. Сборник докладов международного симпозиума. М.: МГТУ, 2006. - С. 366-373. ISBN 5-7038-2715-9

10. Кононыхин А.А., Самедов Я.Ю. Трёхмерное моделирование дефектных областей по данным ультразвукового контроля // Заводская лаборатория. Диагностика материалов. 2006. - №6, том 72. - С. 31-34.

11. Краснов М. OpenGL. Графика в проектах DELPHI СПб.: BHV, 2004. -352 с.

12. Лешковцев В.Г., Покровский A.M. Расчёт закалочных напряжений в стальных деталях с учётом упруговязкопластических свойств и изменения фазового состава // Известия АН. Механика твёрдого тела. -1999.-№ 2.-С. 101-107.

13. Никольский С.М. Курс математического анализа М.: ФИЗМАТЛИТ, 2001.-592 с.

14. Оноприйко М.Д. Реконструкция поверхностей геометрических моделей, представленных дискретным множеством цифровых данных: Дис. канд. техн. наук. Н. Новгород, 2003. - 124 с.

15. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах- М.: Высшая школа, 2005. 544 с.

16. Рвачев В.Л. Теория R-функций и некоторые ее приложения Киев: Наук, думка, 1982. - 552 с.

17. Самедов Я.Ю. Установки неразрушающего контроля валков прокатных станов // В мире неразрушающего контроля. 2004. - № 3. - С. 20 - 23.

18. Самедов Я.Ю., Кононыхин А.А. Трехмерная визуализация результатов ультразвукового контроля // Тезисы научно-технической конференции "Томография" (Москва, 22 марта 2005г.). М, 2005. - С. 8.

19. Самедов Я.Ю., Щербинский В.Г., Ромашов В.П., Кононыхин А.А., Кутянин В.В. Неразрушающий контроль прокатных валков // Труды шестого конгресса прокатчиков (Липецк, 18-21 октября 2005г.).- Липецк, 2005. -С. 505-507.

20. Сенин М.А., Кожекин Н.Е., Савченко В.В. Деформация поверхностей на основе функций радиального базиса с компактным носителем // Электронный журнал «ИССЛЕДОВАНО В РОССИИ». 2004. - С. 19821981.

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

22. Тахаутдинов Р.С., Салганик В.М., Фиркович А.Ю. Производство и эксплуатация валков на металлургическом предприятии / Т. 2. -Магнитогорск: Изд-во МГТУ им. Г.И. Носова, 1999. - 174 с.

23. Третьяков А.В. Валки обжимных, сортовых и листовых станов. М.: Интермет инжиниринг, 1999. - 80 с.

24. Шипачев B.C. Высшая математика. М: Высшая школа, 2007. - 479 с. ISBN 5-06-003959-5

25. Шлее М. Qt. Профессиональное программирование на С++. СПб.: БХВ-Петербург, 2006. - 544 с.

26. Щербинский В. Г. Технология ультразвукового контроля сварных соединений. 2-е изд., испр - М.: Тиссо, 2005. - 326 с. ISBN 5-81220256-7.

27. Щербинский В. Г., Самедов Я. Ю., Артемьев С. А. Автоматизированные установки контроля валков прокатных станов // Металлург. 2003. - № 6. - С. 45-48.

28. Adzhiev V. Cartwright R., Fausett E. HyperFun project: a framework fortcollaborative multidimensional FRep modeling // Implicit Surfaces '99, Eurographics/ACM SIGGRAPH Workshop. 1999. - pp. 59-69.

29. Alexa M., Behr J., Cohen-Or D., Fleishman S., Levin D., Silva C.T. Computing and rendering point set surfaces // IEEE Transactions on Computer Graphics and Visualization. 2002. - # 8(4). - pp. 3-15.

30. Amenta N., Bern M., Kamvysselis M. A new Voronoi-based surface reconstruction algorithm // In Proceedings of ACM Siggraph. 1998. - pp. 415-421.

31. Arun K.S., Huang T.S., Blostein S.D. Least square fitting of two 3-d point sets // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1987. #9(5).-pp. 698-700.

32. Baxter B. THE INTERPOLATION THEORY OF RADIAL BASIS FUNCTIONS: Trinity College, A dissertation presented in fulfillment of the requirements for the degree of Doctor of Philosophy. Cambridge University, 1992.-134 p.

33. Beatson R.K., Light W.A., Billings S. Fast Solution of the Radial Basis Function Interpolation Equations: Domain decomposition methods // SIAM

34. J.Sci. Comput. -2000. vol.22, No.5. - pp. 1717-1740.

35. Besl P.J. The Freeform Surface Matching Problem // In H. Freeman, editor, Machine vision for ThreeDimensional Scenes. Academic Press, 1990. - pp. 25-71.

36. Besl P.J., McKay N.D. A Method for Registration of 3-D Shapes // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1992. - vol. 14, issue 2. - pp. 239 - 256.

37. Bloomenthal J. An implicit surface polygonizer // In Heckbert, P., ed., Graphics Gems IV. Academic Press, 1994. - pp. 324-349.

38. Bloomenthal J. Polygonization of implicit surfaces // Computer Aided Geometric Design. -1988. #5(4), Nov. - pp. 341- 355.

39. Bloomenthal J., Wyvill B. Introduction to implicit surfaces. San Francisco, С A, USA: Morgan Kaufmann Publishers Inc, 1997. - 400 p.

40. Campbell R. Recognition of free-form 3d objects in range data using global and local features: Ph.D. dissertation thesis. Ohio State University, 2001. -235 p.

41. Campbell R., Flynn P. A Survey of Free-form Object Representation and Recognition Techniques // Computer Vision and Image Understanding. -2001. — # 81(2).-pp. 166-210.

42. Reconstruction and representation of 3D objects with radial basis functions / Carr J., Beatson R., Cherrie J., Mitchell Т., Fright W., McCallum В., Evans T.R. // Computer Graphics Proceedings, Annual Conference Series. 2001. -pp. 67-76.

43. Carr J.C., Fright W.R., Beatson R.K. Surface interpolation with radial basis functions for medical imaging // IEEE Trans. Medical Imaging. 1997. -#16(1).-pp. 96-107.

44. Chapman P., Stevens P., Wills D., Brookes G. Seabed visualization // In Proceedings of Visualization'98. IEEE Computer Society Press, 1998. -pp. 479-481. ISBN: 0-8186-9176-X

45. Chetverikov D., Stepanov D., Krsek P. Robust Euclidean alignment of 3D point sets: the trimmed iterative closest point algorithm // IMAGE AND VISION COMPUTING. 2005. - Vol. 23, issue 3. - pp. 299-309.

46. Cowan E.J., Beatson R.K, Fright W.R., McLennan T.J., Mitchell T.J. Rapid Geological Modelling // Applied Structural Geology for Mineral Exploration and Mining International Symposium (Kalgoorlie, WA, Australia, September 2002).-2002.-pp. 23-25.

47. Dierckx P. Curve and Surface Fitting with Splines. New York: Oxford Science, 1995.-304 p.

48. Eberly D. Polyhedral Mass Properties (Revisited): Technical Report / Magic Software Inc. (January 25,2003). 2003. - 6 p. (http://www.geometrictools.com/).

49. Erikson C. Morphing Three Dimensional Polyhedral Objects: Oberlin College Honors Paper. 1994. - 13 p.

50. Ervin S.M., Hasbrouck H.H. LANDSCAPE MODELING: Digital Techniques for Landscape Visualization. McGraw-Hill Professional, 2001. - 352 p. ISBN: 0-07-135745-9.

51. Farin G. Curves and Surfaces For CAGD, A Practical Guide. 5th ed. -Morgan-Kaufmann, 2002.-499 p. ISBN 1-55860-737-4

52. Girosi F., Jones M., Poggio Т., Priors, Stabilizers, and Basis Functions: From Regularization to Radial, Tensor, and Additive Splines // MIT AI Lab Memo. 1993.-# 1430 (June, 1993).-27p.

53. Greengard L., Rokhlin V. A fast algorithm for particle simulations // J. Comput.Phys. 1987. - #73. - pp. 325-348.

54. Harrison J.A., Nixon M.A., Fright W.R., Snape L. Use of hand-held laser scanning in the assessment of facial swelling: a preliminary study // British Journal of Oral and Maxillofacial Surgery. 2004. - #42, - pp. 8 - 17.

55. Hoppe H., DeRose Т., Duchamp Т., McDonald J., Stuetzle W. Surface Reconstruction from Unorganized Points // Computer Graphics (SIGGRAPH •92 Proceedings). -1992. Vol. 26, #2 (July 1992). -pp. 71-78.

56. Horn B.K.P. Closed-form solution of absolute orientation using unit quaternions // Journal of the Optical Society of America A, 1987. - #4(4, April 1987).-pp. 629-642.

57. Jolliffe I. Principle Component Analysis. 2nd ed. - Springer, 2002. - 502 p. ISBN-13:978-0387954424

58. Koivunen V., Bajcsy R. Spline representations in 3-D vision // Object Representation in Computer Vision, (M. Hebert, J. Ponce, T. Boult, and A. Gross Eds.).-Berlin: Springer-Verlag, 1995. -pp. 177-190.

59. Kojekine N., Hagiwara I., Savchenko V. Software Tools Using CSRBFs for Processing Scattered Data // International journal "Computers & Graphics". -Elsevier Science. #27/2 (2003). - pp. 309-317.

60. Krishnamurthy V., Levoy M. Fitting smooth surfaces to dense polygon meshes // in Proceedings of SIGGRAPH '96 (New Orleans, Louisiana, August 1996).- 1996. -pp.313-324.

61. Kwang-Ho В., Lichti Derek D. Automated Registration of Unorganised Point Clouds from Terrestrial Laser Scanners // INTERNATIONAL ARCHIVES OF PHOTOGRAMMETRY REMOTE SENSING AND SPATIAL INFORMATION SCIENCES. 2004. -Vol. 35, Part 5. - pp. 222-227.

62. Lorensen W.E., Cline H.E. Marching Cubes: A High Resolution 3D Surface Construction Algorithm // Computer Graphics. 1987. - vol. 21, #3. - pp. 163-169.

63. Madsen K., Nielsen H.B., Tingleff O. METHODS FOR NON-LINEAR LEAST SQUARES PROBLEMS. 2nd ed. // Lecture Notes, Informatics and Mathematical Modelling Technical University of Denmark. - 2004. - 57 p.

64. Mirtich B. Fast and accurate computation of polyhedral mass properties // Journal of Graphics Tools. 1996. - #1(2). - pp. 31-50.

65. Mitra N. J., Gelfand N., Pottmann H., Guibas L. Registration of Point Cloud Data from a Geometric Optimization Perspective // Eurographics Symposium on Geometry Processing. 2004. - pp. 23-32.

66. Neumaier A. Complete Search in Continuous Global Optimization and Constraint Satisfaction // in: Acta Numerica 2004 (A. Iserles, ed.). -Cambridge University Press, 2004. pp. 271- 369.

67. Ning P., Bloomenthal J. An evaluation of implicit surface tillers // Comput. Graphics Appl. -1993. -#13. pp. 33-41.

68. Ohtake Y., Belyaev A. G., Seidel H. P. A multi-scale approach to 3d scattered data interpolation with compactly supported basis functions // In Shape Modeling International (Seoul, Korea, May 2003). 2003. - pp. 153-161.

69. Ohtake Y., Belyaev A.G., Seidel H.-P. Multi-scale and adaptive CS-RBFs for shape reconstruction from cloud of points // In MINGLE workshop on Multiresolution in Geometric Modelling (Cambridge, UK, September 2003). -2003.-pp. 337-348.

70. Pasko A., Adzhiev V., Sourin A., Savchenko V. Function representation in geometric modeling: concepts, implementation and applications // The Visual Computer. 1995. -#11(8). -pp. 429 - 446.

71. Pauly M., Gross M., Kobbelt L. P. Efficient simplification of pointsampled surfaces // In Proceedings of the conference on Visualization '02. IEEE Computer Society. - 2002. - pp. 163-170.

72. Pentland A. P. Perceptual organization and the representation of natural form // Artif. Intell. 1986. - #28. - pp. 293-331.

73. Reuter P. Reconstruction and rendering of Implicit Surfaces from Large Unorganized Point Sets: Ph.D. dissertation thesis. Bordeaux University, 2003.-167 p.

74. Samedov Y., Kononykhin A. Inner Defects Visualization Based on Ultrasonic Scanning // ECNDT-2006 Proceedings, Topic Fr.2.3.2 (Berlin, September 25-29,2006).-2006.-7 p.

75. Savchenko V. STAR Report: Application of Radial Basis Functions for CAD and CG // Proceedings 14th International Conference on Computer Graphics and Vision (Graphicon04, Sept. 2004). 2004. - pp. 16-23.

76. Savchenko V.V., Pasko A.A., Okunev O.G., Kunii T.L. Function representation of solids reconstructed from scattered surface points and contours // Computer Graphics Forum (October, 1995). 1995. - pp. 181188.

77. Schaback R. Remarks on Meshless Local Construction of Surfaces // invited survey, The mathematics of surfaces IX (eds: R. Cipolla et. al.) Proceedings of the Ninth IMA Conference on the Mathematics of Surfaces. -Springer, 2000.-26 p.

78. Schneider P.J., Eberly D. Geometric Tools for Computer Graphics. NY, USA: Elsevier Science Inc, 2002. - 1056 p. - ISBN: 1558605940.

79. Sedgewick R. Algorithms. Addison-Wesley, 1983. - 551 p.

80. Shaffer E., Garland M. Efficient adaptive simplification of massive meshes // In Visualization'01 Conference Proceedings.-2001.-pp. 127-134.

81. Smith L.I. A tutorial on Principal Components Analysis. 2002. - 26 p.

82. Solina F., Bajcsy R. Recovery of parametric models from range images: The case for superquadrics with global deformations // IEEE Trans. Pattern Anal. Mach. Intell. 1990. -#12. - pp. 131-147.

83. Tobor I., Reuter P., Schlick C. Efficient reconstruction of large scattered geometric datasets using the partition of unity and radial basis functions // Journal of WSCG. 2004. - 9 p.

84. Turk G., O'Brien J.F. Variational Implicit Surfaces // Tech Report GIT-GVU-99-15, Georgia Institute of Technology. 1999. - 9 p.

85. Walker M.W., Shao L., Volz R.A. Estimating 3-d location parameters using dual number quaternions // CVGIP: Image Understanding. 1991. - # 54. -pp. 358-367.

86. Wendland H. On the smoothness of positive definite and radial functions // Journal of Computational and Applied Mathematics. 1999. - #101. - pp. 177-188.

87. Wendland H. Piecewise polynomial, positive definite and compactly supported radial basis functions of minimal degree // Advances in Computational Mathematics. 1995. - #4. - pp. 389-396.