Содержание к диссертации
Введение
Глава 1. Методы моделирования, визуализации и анализа объёмных тел 18
1.1. Моделирование явными функциями 18
1.2. Моделирование параметрическими функциями 19
1.3. Моделирование суперповерхностями второго порядка .. 21
1.4. Моделирование полигональными сетками 24
1.5. Моделирование неявными функциями 27
1.6.Выводы по методам моделирования 31
1.7.0бзор методов моделирования неявными функциями 34
1.7.1.Моделирование функциями знаковых расстояний 34
1.7.2 Моделирование скользящими наименьшими квадратами 37
1.7ДМоделирование Радиальными Базисными Функциями 39
1.7.3.1.Моделирование с использованием нормалей 45
1.7.3.2.Моделирование с использованием несущей функции .46
1.7АВыводы по методам моделирования неявными функциями .48
Вычислительная сложность моделирования Радиальными Базисными Функциями и методы её оптимизации 50
1.8.1.Метод «Быстрых Вычислений» 51
1.8.2.Метод компактных носителей 53
1.8.3.Многоуровневые методы 54
1.8.4.Иерархический метод разбиения единицы 56
1.8.5,Выводы по методам оптимизации вычислительной сложности 58
1 ^.Визуализация объёмных тел, заданных Радиальными Базисными Функциями 60
1.10. Анализ объёмных тел, заданных Радиальными Базисными Функциями. Классификация объёмных тел 63
1.1.1-Применения RBF-моделей объёмных тел 65
1.12.Выводы по главе 66
Глава 2. Метод RBF-моделирования на основе локального морфинга с применением адаптивной децимации 68
2.1.Постановка задачи ...68
2.2.Описание метода 68
2.3. Структурирование исходных данных в бинарном дереве 70
2 ААдаптивная децимация 82
2.5.Получение локальной RBF-модели 95
2.6.Морфинг объёмных тел 98
2.7. Получение глобальной RBF-модели методом локального морфинга ...100
2.8.Получение верхних оценок вычислительной сложности 106
2.9.Выводы по главе 111
Глава 3. Анализ объёмных тел, заданных RBF-моделями 113
3.1.Краткое описание методов 113
3.2. Вычисление площади поверхности объёмного тела 113
3.3, Вычисление объёма, координат центра масс и моментов инерции тела 116
З.4. Построение и анализ сечений объёмного тела 121
3.5. Вычисление меры схожести объёмных тел и её применение в
задачах классификации 122
З.б.Выводы по главе 131
Глава 4. Реализация, экспериментальные исследования и испытания разработанных методов 133
4.1.Программная реализация разработанных методов 133
4.2.Вычислительный эксперимент по выяснению влияния параметров и оценке сложности алгоритмов RBF-моделирования, RBF-вычисления 135
4.3. Промышленное применение разработанных методов в области ультразвукового контроля прокатных валков 143
4.4. Выводы по главе 151
Заключение 153
Выводы 154
Литература
- Моделирование суперповерхностями второго порядка
- Структурирование исходных данных в бинарном дереве
- Вычисление площади поверхности объёмного тела
- Промышленное применение разработанных методов в области ультразвукового контроля прокатных валков
Введение к работе
Достижения последних лет в области измерительной техники обусловили появление цифровых устройств, способных с высокой точностью получать информацию об объёмных телах произвольной формы. Модели объёмных тел, основанные на данных, полученных от измерительных устройств, широко применяются в астрономии, медицине, геологии и многих других областях. Особую актуальность моделирование объёмных тел имеет в области ультразвуковой дефектоскопии массивных металлических изделий (валков, оправок, и т.п.) [18]. Целью моделирования является визуализация и анализ внутренних технологических объёмных дефектов (полостей, раковин, каверн), имеющих, в общем случае, произвольную форму. Своевременное и достоверное выявление и исследование дефектов в прокатных валках (основных деталях прокатного стана) позволяет определить и вывести из работы бракованные валки. Это предотвращает аварийные остановки прокатного стана, следствием которых, помимо экономических потерь, могут быть и человеческие жертвы.
Настоящая работа в её теоретической части посвящена решению актуальной задачи развития методов моделирования объёмных тел, а в прикладной - реализации этих методов для промышленного использования. Объёмным телом будем называть замкнутую геометрическую фигуру в трёхмерном Евклидовом пространстве, имеющую произвольную форму. Современные технические системы сбора информации об объёмных телах, такие как: лазерные установки [55], механические зондирующие устройства, ультразвуковые сканеры [18] и системы стереоскопического компьютерного зрения, - получают множество точек в трехмерном пространстве, принадлежащих поверхности исследуемого объёмного тела (см. рисунок 1). Такое множество точек назовём исходным, а заданное им объёмное тело -точечно-заданным.
(а) (б)
Рис. 1. (а) - точечно-заданный объёмный дефект, полученный в результате сканирования валка прокатного стана ультразвуковой системой; (б) - точечно-заданная копия головы человека, полученная системой
лазерного сканирования
Визуализацией объемного тела называется изображение его поверхности на устройстве вывода (дисплее компьютера) (см. рисунок 2). Наиболее распространённым типом визуализации является триангуляция -построение сетки из треугольников, повторяющей форму поверхности объёмного тела.
Анализом объёмного тела называется нахождение его количественных и качественных характеристик. Классом объёмных тел называется множество объёмных тел, сгруппированных по определенным признакам сходства. Классификацией называется автоматическое отнесение объёмного тела к тому или иному классу. Анализом объёмного тела является, например, определение объёма, площади поверхности, моментов инерции, геометрических характеристик сечений. Отдельной задачей анализа является определение классификация объёмных тел. Примером классификации является автоматическое определение типа объёмного дефекта (графитовое
включение, расслоение, раковина, и т.д.), обнаруженного внутри металлического изделия ультразвуковым сканером.
(а) (б)
Рис. 2. (а) - визуализация объёмного дефекта валка прокатного стана;
(б) - визуализация копии головы человека
Решение задач визуализации и анализа непосредственно на основе точечного задания имеет ряд недостатков, почти исключающих прямое использование точечно-заданных объёмных тел для решения большинства практических задач. К числу таких недостатков относятся:
Точечное задание является дискретным, поэтому для анализа объёмного тела не применимы классические методы дифференциального и интегрального исчисления. Например, невозможно вычислить объём тела путём интегрирования.
В результате работы системы сканирования объёмного тела возможно появление плохо отсканированных участков - пробелов в исходном множестве, восполнение которых не обеспечивается точечным заданием.
Построение триангуляции, вершинами которой являются точки исходного множества, представляет собой вычислительно сложную задачу с неоднозначным решением.
4. В случае применения увеличивающего масштабирования к точечно-заданному объёмному телу плотность точек уменьшается, что приводит к понижению качества изображения.
Для того чтобы избежать указанных недостатков, переходят к аналитическому описанию объёмного тела, называемого его моделью. Модель объёмного тела может быть задана как формулой (или формулами), так и вычислительной процедурой. Процесс построения модели объёмного тела назовём моделированием.
На сегодняшний день известно большое количество методов моделирования объёмных тел [41]: явными функциями, параметрическими функциями, суперповерхностями второго порядка, полигональными сетками и неявными функциями. На основании исследования и сравнения вышеперечисленных методов, подробно описанных в Главе 1 настоящей работы, показано, что наиболее удобным методом моделирования точечно-заданных объёмных тел является использование неявных функций [17].
Для того чтобы сформулировать особенности метода моделирования неявными функциями, введём ряд понятий и определений. Функция / называется задающей, если она определяет скалярное поле в трёхмерном Евклидовом пространстве, т.е. каждой точке из области определения функции/ставит в соответствие действительное число d =f(x,ytz). Задающая функция обладает следующими свойствами:
l)f(x,y,z) = 0 для любой точки с координатами (x,y,z)9 лежащей на поверхности объёмного тела;
f(xtytz) = d < 0 для любой точки с координатами (x,y,z)9 лежащей внутри объёмного тела;
f(xty,z) =d> 0 для любой точки с координатами (x,ytz)9 лежащей вне объёмного тела;
4) абсолютное значение d характеризует удаленность точки с координатами (xtytz) в трехмерном пространстве от поверхности объёмного тела.
Функция f(x>y,z) = 0 называется неявной функцией, а геометрическое место точек S = { (xty>z)\ f(x>y>z) = 0 } - неявной поверхностью. Объёмное тело, поверхность которого задаётся неявной функцией, назовём неявным объёмным телом. Важным свойством функции/является знак её значения, позволяющий классифицировать все точки трёхмерного пространства на лежащие внутри и вне объёмного тела. Это свойство позволяет использовать численные методы дифференциального и интегрального исчисления для анализа объёмного тела. Например, вычисление объёма тела заключается в интегрировании единичной функции по области/(х,у,г^ > 0.
Моделирование точечно-заданного объёмного тела неявной функцией заключается в интерполяции точек исходного множества функцией f(x,y,z) = 0. Задача интерполяции в таком виде является некорректной, так как существует бесконечное количество поверхностей, которым могут принадлежать точки исходного множества. В Главе 1 настоящей работы рассматриваются несколько различных типов неявных функций. Однако для выбора наиболее адекватной неявной функции, интерполирующей точки исходного множества, было предложено [53] наложить на неё ограничение максимальной плавности, достигаемое за счёт минимизации функционала, представляющего собой энергию изгиба. Функции, одновременно удовлетворяющие требованию принадлежности точек исходного множества поверхности объёмного тела и ограничению максимальной плавности, называются Радиальными Базисными Функциями («Radial Basis Function, RBF» [53]):
N M
где N - количество точек исходного множества; Л/ - коэффициенты интерполяции; базисная функция <р(г) = г^м 1п(г), в случае, если 2т> twt-четное, (р(г) = г2""' в противном случае; г-размерность пространства (равна 3 для трёхмерного пространства); т - целое положительное число; || || -Евклидова норма в t - мерном пространстве; М - количество членов полинома степени, как минимум (2m-t) / 2, в случае если / - чётное, и степени, как минимум, (2m-t+I) / 2, в противном случае; с/ -полиномиальные коэффициенты;#- полиномиальный базис.
Выражение (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)9 а сложность RBF-вычисления -OflogN). Поэтому актуальна разработка нового эффективного метода RBF-моделирования, отличающегося от известных методов, имеющих указанные оценки, их практическим уменьшением.
Практическое уменьшение времени работы программы, осуществляющей RBF-моделирование и RBF-вычисление, можно достичь за счёт сокращения количества точек исходного множества N. Во многих возникающих на практике задачах исходное множество избыточно, так как содержит большое количество точек, удаление которых практически не скажется на свойствах RBF-модели. Поэтому помимо разработки теоретически эффективных методов RBF-моделирования и RBF-вычисления, актуально создание метода, производящего адаптивную децимацию исходного множества - удаление наименее информативных для RBF-моделирования точек.
Актуальность темы в научном аспекте определяется:
необходимостью разработки вычислительно-эффективных методов RBF-моделирования и RBF-вычисления точечно-заданного объёмного тела, исходное множество которого содержит десятки и сотни тысяч точек;
необходимостью разработки и исследования эффективности методов анализа объёмных тел, заданных RBF-моделями.
Актуальность темы в прикладном аспекте определяется необходимостью создания программных продуктов, реализующих методы RBF-моделирования, визуализации и анализа точечно-заданных объёмных тел, содержащих большое число (десятки и сотни тысяч) точек, используя современные настольные вычислительные системы класса ПК. В частности, актуально решение задачи ультразвуковой дефектоскопии массивных металлических изделий по компьютерному моделированию, визуализации и анализу объёмных дефектов на основе данных ультразвукового сканирования.
Объектом исследования является моделирование, визуализация и анализ объёмных тел.
Предметом исследования являются оптимизированные по вычислительной сложности моделирование, визуализация и анализ объёмных тел на основе Радиальных Базисных Функций при условии, что объёмное тело может быть задано десятками и сотнями тысяч точек.
Цель работы - разработка вычислительно-эффективных методов моделирования, визуализации и анализа объёмных тел с использованием Радиальных Базисных Функций, позволяющих решать практические задачи большой размерности, в частности в области ультразвуковой дефектоскопии массивных металлических изделий.
Задачи исследования.
Осуществить сравнительный анализ методов моделирования точечно-заданных объёмных тел, включая классический метод RBF-моделирования. Рассмотреть и выделить недостатки в существующих на сегодняшний день подходах к уменьшению сложностей RBF-моделирования и RBF-вычисления.
Разработать новые вычислительно-эффективные методы RBF-моделирования и RBF-вычисления, получить теоретические оценки их вычислительной сложности. Разработать и исследовать новый метод адаптивной децимации исходного множества точек.
Разработать новые методы анализа объёмных тел, заданных RBF-моделью, исследовать их вычислительную сложность. Разработать метод вычисления меры схожести объёмных тел, исследовать его вычислительную сложность для применения в задачах классификации.
Разработать программное обеспечение, реализующее предложенные в работе методы,
Провести вычислительные эксперименты, подтверждающие эффективность предложенных в работе методов и выявляющие практические тенденции роста времени выполнения программ, в зависимости от количества точек исходного множества.
6* Внедрить и апробировать разработанные методы и программное обеспечение в области ультразвуковой дефектоскопии массивных металлических изделий (валков прокатных станов).
Методы исследования.
Исследования в области моделирования объёмных тел, на которых базируется настоящая работа, известны по трудам российских (В .Л. Рвачёв, В.В. Савченко, А.А. Пасько) и зарубежных (Дж. Карр, М. Алекса, Ю. Отаке, П. Рютер) учёных. При решении поставленных задач использовались методы
математического моделирования, теории функций многих переменных, линейной алгебры, аналитической и вычислительной геометрии, теории вероятности и математической статистики, теории исследования операций и глобальной оптимизации, методы объектно-ориентированного программирования и разработки интеллектуальных систем.
Научная новизна.
В процессе проведения исследований были получены новые научные результаты теоретического и прикладного характера.
Разработаны новые эффективные методы RBF-моделирования и RBF-вычисления, теоретические оценки вычислительной сложности которых составляют 0(N logN) и 0(logN) соответственно. Практические тенденции роста времени работы предложенных алгоритмов для рассматриваемого класса задач составляют 0(N) и 0(1) для RBF-моделирования и RBF-вычисления соответственно.
Разработан новый метод адаптивной децимации, сокращающий количество точек исходного множества и существенно (до 1.5 раз) уменьшающий время работы алгоритма RBF-вычисления.
Разработаны новые методы анализа объёмных тел, заданных RBF-моделями, исследована их вычислительная сложность. Предложены методы вычисления площади поверхности, объёма, координат центра масс, моментов инерции объёмных тел. Разработан метод получения и исследования сечений. Предложена новая мера схожести объёмных тел, исследована её вычислительная эффективность, предложен метод её использования для решения задач классификации.
Впервые решена важная прикладная задача ультразвуковой дефектоскопии массивных металлических изделий по моделированию, визуализации и анализу внутренних объёмных технологических дефектов.
Практическая ценность работы.
В результате проведенного исследования разработано математическое и программное обеспечение, реализующее методы RBF-моделирования, визуализации и анализа объёмных тел, заданных исходным множеством, содержащем десятки и сотни тысяч точек. Применение созданного программного обеспечения позволило исследовать свойства объёмных дефектов произвольной формы в ультразвуковой дефектоскопии массивных металлических изделий. Универсальность предложенных решений позволяет использовать их и в других областях применения.
На защиту выносятся следующие положения.
Новый вычислительно-эффективный метод RBF-моделирования.
Методика анализа объёмных тел.
Программная реализация предложенных методов и их применение в области дефектоскопии прокатных валков.
Реализация и внедрение результатов работы.
Результаты работы реализованы в аппаратно-программном комплексе «Валок-5», произведенным в ООО «Демас» по заказу ОАО «Северсталь» в 2004-2005 гг. Внедрение результатов подтверждается соответствующими актами.
В Лаборатории Автоматизации Неразрушающего Контроля ОАО НПО «ЦНИИТМАШ» создан автоматизированный стенд для проведения полунатурных испытаний по ультразвуковому сканированию тел вращения, программная часть которого реализует предложенные в работе методы.
Теоретические результаты работы реализованы в МГТУ им. Н.Э. Баумана на кафедре ИУ-3 в виде материалов лекций учебного курса «Обработка изображений в информационных системах».
Апробация работы.
Результаты работы были представлены на стенде ООО «Демас» (Demas Ltd.) и в соответствующем стендовом докладе на международной выставке «Металлургия и материалы», проходившей с 28 сентября по 02 октября 2005 года в г. Стамбул, Турция.
Методы и алгоритмы, предлагаемые в работе, были отражены в выступлении на научно-технической конференции "Томография", состоявшейся в Москве 22 марта 2005 года.
Ключевые идеи работы были изложены в докладе на международном симпозиуме «Образование через науку», проходившем в МГТУ им. Н.Э. Баумана с 17 по 19 мая 2005 года.
На международной конференции-выставке по неразрушающему контролю и технической диагностики ECNDT-2006, проходившей с 25 по 29 сентября 2006 года в г. Берлин, Германия, был сделан секционный доклад, отражающий основное содержание работы.
Публикации.
Основное содержание диссертации отражено автором в семи работах, среди которых статьи и материалы конференций. Ключевые идеи, касающиеся методов моделирования объёмных тел в работах, написанных в соавторстве, принадлежат автору настоящей диссертации.
Структура и объем работы.
Диссертационная работа состоит из введения, четырёх глав, заключения и списка литературы, занимающих 165 страниц текста, в том числе 49 рисунков на 44 страницах, 10 таблиц на 10 страницах, список использованной литературы из 91 наименования на 10 страницах.
В первой главе рассматриваются существующие методы моделирования объёмных тел. Исследуется классический метод RBF-моделирования и существующие на сегодняшний день подходы к
уменьшению сложностей RBF-моделирования и RBF-вычисления. Обозначаются актуальные задачи, требующие решения.
Во второй главе предлагаются новые вычислительно-эффективные методы RBF-моделирования и RBF-вычисления. Предлагается метод адаптивной децимации - сокращения избыточного количества точек исходного множества. Доказывается вычислительная эффективность разработанных методов: рассчитываются теоретические оценки вычислительной сложности разработанных алгоритмов.
В третьей главе предлагается методика анализа объёмных тел, заданных RBF-моделями. Приводятся методы вычисления площади поверхности, объёма, геометрических характеристик сечений и т.п. Приводится новая, вычислительно-эффективная мера схожести объёмных тел, предлагается способ её применения в задачах классификации. Исследуется вычислительная сложность предложенных методов.
В четвертой главе проводится вычислительный эксперимент, подтверждающий эффективность предложенных методов RBF-моделирования и RBF-вычисления, выясняются оптимальные параметры для . разработанных методов. Описывается применение метода RBF-моделирования, визуализации и анализа объёмных тел в ультразвуковой дефектоскопии валков прокатных станов.
В заключении приводятся результаты и делаются выводы по проделанной работе.
Моделирование суперповерхностями второго порядка
Суперповерхностью второго порядка S(rj,a ) называется объёмный примитив, заданный одновременно в параметрической и неявной форме [86]: S(tj,e )= yfy,o) a, cos 1 (rficos 2 {со) a2 cos (Tj)sinei (со) аъ sin (7) , --//-, -жйайя, S(x,y,z)= , \a\; + Ж s.aU -, gMk Ka J -\s = 1, где x,y,z - координаты конца вектора с началом в точке (0,0,0), описывающего поверхность объёмного тела, при варьировании двух независимых параметров rj и со; со - угол между осью х и проекцией вектора [xj ,z] на плоскость (ху); г\ - угол между вектором [x,y,z] и его проекцией на плоскость (ху). Параметры ц и со соответствуют углам широты и долготы вектора [x,y,z]T в сферических координатах. Параметры а\, а% аз определяют габаритный размер объёмного тела по осям х,уиг соответственно; ej и г2 -параметры квадратности в плоскости широты и долготы соответственно; S(x,y,z) - неявная форма задания функции S(rj,co), получаемая из неё путём исключения параметров ц и со, используя соотношение sm2(a) + cos2(a) = L
В виде суперповерхностей второго порядка могут быть представлены многие стандартные объёмные тела: сферы, цилиндры, параллелепипеды и их различные деформированные варианты (см. рисунок 1.3). В случае, когда оба параметра Є/ и е2 равны единице, вектор [x,y,z] описывает поверхность эллипсоида, или если aj = а2 = а$ = / - поверхность сферы. В случае выполнения условия 6j « 1 и е2 - U суперповерхность моделирует цилиндр, а в случае / / и е2« 1 - параллелепипед.
В работах [75], изучающих свойства суперповерхностей второго порядка показано, что с применением сужающих, крутящих и изгибающих деформаций возможно моделирование разнообразных объёмных тел. Например, на рисунке 1.4 изображена суперповерхность второго порядка с параметрами {аІ = Q2 = с з = 1 и г/ = 1.0; = 0.3), к которой применены следующие деформации: - сужение вдоль оси г: rz(?]y6))+\ х(т],0) - кручение относительно оси z, используя 0=n(l-z(f],a )):
Моделирование объёмного тела, заданного множеством точек в пространстве осуществляется путём их аппроксимации зависимостью (1.4) с учетом применения возможных деформаций. Основной недостаток такого моделирования заключается в невозможности воспроизведения мелких элементов поверхностей [41]. Например, элементы лица человека воспроизводятся с неудовлетворительной точностью, т.е. лица разных людей будут задаваться примерно одинаковыми моделями и выглядеть примерно одинаково.
Таким образом, суперповерхности второго порядка хорошо подходят лишь для грубого моделирования объёмных тел. Такие модели иногда используются в методах распознавания трёхмерных образов на этапе грубой классификации с целью сокращения время работы более вычислительно-сложных алгоритмов для последующего точного распознавания.
1 . Моделирование полигональными сетками.
На сегодняшний день самыми популярными моделями объёмных тел в компьютерной графике являются полигональные сетки. Поверхность тела в этом случае задаётся упорядоченным множеством вершин и соединяющих их многоугольников: S = (P,V), (1.5) где V={vIt у&„ч vrf, К - количество вершин vr=(xb уи zj, заданных своими трёхмерными координатами; Р-{ри рь— Рм}, М - количество многоугольников, казвдых из которых задан списком индексов вершин: Pi=/V,,/, vii2, ... W Большой объём оперативной памяти, характерный для современных персональных ЭВМ, позволяет использовать полигональные модели с большой плотностью вершин, что даёт возможность описать даже топологически сложные элементы поверхностей объёмных тел. Одной из задач современных исследований является адаптивное распределение плотности вершин многоугольников на поверхности объекта [84], в зависимости от локальных свойств поверхности, таких как кривизна, степень детализации и пр..
Структурирование исходных данных в бинарном дереве
Структурирование исходных данных в бинарном дереве является первым этапом метода и заключается в разбиении исходного множества точек Р на М подмножеств Р(% каждое из которых содержит ограниченное количество точек. Результат разбиения подчиняется соотношению: м ы\ Pt = {peP: petlX м (2.1) ы где Q - часть пространства Hd9 в которой содержится исходное множество точек Р, Q/ - часть пространства Q, в котором содержится множество точек Pi.
Шаг 1. Рассмотрим пространство Q с Rd, являющееся внутренней областью параллелепипеда и содержащее все точки исходного множества Р (см. рисунок 2.2). Параллелепипед, с гранями параллельными координатным осям, задающий пространство Q, характеризуется координатами концов диагонали - точками 5/ и В . Здесь и далее в тексте будем обозначать параллелепипед парой точек в круглых скобках: (В/; В$. Точки В\ и В2 выбираются по следующему принципу: для любой вершины Я, параллелепипеда с координатами [XJM 2ВІ, W верны неравенства: т.е. В/ всегда является «самой левой и нижней», а В2 - самой «правой и верхней» вершиной параллелепипеда. Пространство Q, состоящее из геометрического места точек, находящихся внутри параллелепипеда (Bt; 5 , подвергается бинарному рекурсивному разбиению согласно следующим шагам.
Шаг 2. Рассмотрим параллелепипед (С\; СУ, координаты задающей диагонали которого формируются по правилу: 2С == П11П Х2 9 22 9 » t/2 Л 2С2 = П" Ч 12» 22 »"ч /2/» (2.3)
Вершина Cj состоит из наименьших координат по каждому измерению, а вершина С - из наибольших. Таким образом, параллелепипед (Сі; С , является минимальным по объёму параллелепипедом с гранями, параллельными координатным осям, внутреннее пространство которого содержит все точки исходного множества. Такой параллелепипед будем называть ограничивающим. Шаг 3. Вычислим длины граней //, l2 ..., U ограничивающего параллелепипеда по формулам: h х\сг Х\С, h = Х2С2 X2Ct h XdC2 XdCx (2.4) Найдём грань максимальной длины и найдём координатную ось /, которой она параллельна: /:/, =max(/p/2v..,/J. (2.5) Шаг 4. Упорядочив точки множества Р по возрастанию координаты по оси г, получим множество: (2.6) Шаг 5. Зададимся действительным числом оє(0;1)9 которое назовём коэффициентом перекрытия. Этот коэффициент характеризует количество точек Novj9 которое будет принадлежать одновременно обоим параллелепипедам (т.е. лежать в зоне пересечения), после разбиения параллелепипеда (В/; Bj) на два: Novi=o-N. (2.7)
Для контроля над количеством точек в зоне пересечения, зададимся двумя параметрами NOVIMIN И МЫМЛХ ограничивающими диапазон значений Тогда количество точек с точностью до единицы внутри каждого из двух полученных после разбиения параллелепипедов будет равно:
Тогда исходное множество Р будет равно объединению этих двух множеств. Шаг 7. Определим параллелепипеды, задающие пространства Q и Q", содержащие, соответственно, множества Р и Р , по следующему правилу.
Параллелепипед, задающий пространство Q определяется диагональю (Вґ;В2 ): в\=в{, (2Л2) XtB2 xipn т.е. все координаты точки В/ совпадают с координатами точки Ви и все координаты точки 5/ совпадают с координатами точки 5 , за исключением координаты по оси / (вдоль самого длинного ребра ограничивающего параллелепипеда); эта координата берётся от точки pih Параллелепипед, задающий пространство Q , определяется диагональю (Ві V В2 ): в2 = в2, Bl = [xkB\k = l9...9d9k t9 (2.13) XtB\ xtpi2 т.е. все координаты точки Д" совпадают с координатами точки В2у и все координаты точки В]11 совпадают с координатами точки Ви за исключением координаты по оси / (вдоль самого длинного ребра ограничивающего параллелепипеда); эта координата берётся от точки рі2.
Вычисление площади поверхности объёмного тела
Пусть поверхность объёмного тела задана JtiiF-модепъю f(x,y,z) - 0 и выполняется условие: означающее, что в каждой точке поверхности существует нормаль, с направляющим вектором:
Разобьём поверхность f(xty,z) = 0 сеткой гладких кривых на т элементарных областей ASb i=1,2,...tm. Обозначим через АЬ наибольший линейный размер такой области. Если независимо от разбиения, существует предел то он называется площадью поверхности.
На сегодняшний день, нет известных методов аналитического вычисления выражения (3.3), так как форма поверхности f(x,y,z) = О произвольна, а известные методы [25] опираются на однозначность её проецирования на координатные плоскости. Выражение (3.3) является точным значением площади поверхности, однако для многих практических задач достаточно вычислять её приближенное значение. При этом приближенное значение будет тем ближе к точному, чем меньше будет ALmax, который, в свою очередь, зависит от способа разбиения поверхности.
Эффективный метод разбиения поверхности на элементарные области (треугольники) был предложен Джулесом Блументалем [38] (см. параграф 1.9). Максимальный линейный размер треугольника AL убывает с ростом количества (п-1) ячеек на которые разбита воображаемая решетка вдоль каждого габаритного размера поверхности (см. рисунок 1.14).
Площадь поверхности, в этом случае, приближенно будет равна сумме площадей треугольников, аппроксимирующих поверхность, полученных на выходе алгоритма триангуляции Джулеса Блументаля: т м (3-4) где т - количество треугольников, S) - площадь /-го треугольника.
Рассмотрим численный метод определения S . Зная координаты вершин (xfJf У/, zV, ( Д 2 , fxj, У?, т!з) /-го треугольника, длины его рёбер Iіh І7 и Iіз вычислим по формулам:
Тогда площадь треугольника / вычислим по формуле Герона, так как известны длины его граней: - полупериметр /-го треугольника.
Известно, что формула Гсрона (3.6) является вычислительно нестабильной, т.е. даёт большую погрешность при её вычислении компьютерной программой в случаях, когда одно из рёбер треугольника существенно меньше другого. Поэтому, в компьютерной программе предлагается реализовывать вычислительно стабильную формулу, алгебраически эквивалентную (3.6):
С ростом количества ячеек и, будет убывать ALmaX9 увеличиваться количество треугольников т и значение S4, полученное численным методом будет стремиться к точному значению S. Известно, что верхняя оценка вычислительной сложности алгоритма триангуляции Джулеса Блументаля в единицах количества точек исходного множества составляет 0(п N). Это объясняется тем, что в пропорциональном п количестве узлов требуется осуществить RBF-вычисление, сложность которого, используя классический алгоритм составляет 0(N). Используя новый, предложенный в главе 2 метод вычисления значения глобальной RBF-модели, который выполняется за 0(log N) операций, оценка вычислительной сложности алгоритма триангуляции сократится до 0(п2 log N). Верхняя оценка вычислительной сложности алгоритма, реализующего вычисление приближенного значения площади поверхности по формуле (3.4), составляет тгО(1)% т.к. вычисление площади одного треугольника осуществляется за постоянное время. Таким образом, верхняя оценка вычислительной сложности предложенного алгоритма для вычисления площади поверхности точечно-заданного объёмного тела составит: 0{п2 log N)+ т 0(1)= 0(п2 log N\ (3.9) так как количество треугольников т всегда меньше количества узлов решетки (пропорционального п2\ необходимых для их получения.
Пусть объёмное тело задано RBF-моделью f(x,ytz) в пространстве R3. Разобьём область f(x,y,z) 0 (т.е. внутренность объёмного тела) на к непересекающихся элементарных объёмных тел, объёмом AVb 1=1,2,...,к каждое. Пусть ALmax - максимальный линейный размер элементарного тела. Если независимо от разбиения, существует предел ton tw=r, (3.9) то он называется объёмом тела.
Промышленное применение разработанных методов в области ультразвукового контроля прокатных валков
Основная часть металлопродукции выпускается в настоящее время в виде проката. С каждым годом в общей структуре выпуска металлургических предприятий увеличивается доля листового проката. Современный листопрокатный стан представляет собой сложный комплекс машин и механизмов. Основным инструментом стана, формирующим размеры листа, его чистоту поверхности и свойства, являются валки, смонтированные в клети (см. рисунок 4.8) [18].
Прокатный валок является обычно цельнометаллической деталью прокатного стана, которая состоит из бочки, непосредственно участвующей в контактировании и шеек (цапф), расположенных с обеих сторон бочки и опирающихся на подшипники. У листопрокатных валков бочка цилиндрическая [4]. При прокате черных металлов используют прокатные станы простой конструкции с двумя рабочими и двумя опорными валками [18] (см. рисунок 4.8). рабочие валки QHQPHk ie валки
Современное листопрокатное производство характеризуется высокой интенсивностью процесса. Скорость прокатки в непрерывных станах может достигать 40 м/с. С каждым годом повышаются требования к качеству прокатываемого листа, его чистоте поверхности и допускам на разнотолщинность. Увеличивается степень обжатия при прокатке, возрастает доля труднодеформируемых материалов [24]. Всё это приводит к ужесточению условий эксплуатации рабочих и опорных валков, поэтому особо остро стоит вопрос их качества.
Очевидно, что бесперебойная работа прокатного стана и получение высокосортной продукции в значительной степени зависят от качества прокатных валков [5]. Основным параметром, определяющим качество валка, является его стойкость, т.е. количество прокатанного металла до списания. Списание валка может осуществляться как по регламенту, так и вне него - по обнаружению в нём дефектов, способных вызвать его разрушение.
Каждая поломка валка значительно увеличивает простой прокатного стана. Так, выход из строя рабочего валка на листовом стане металлургического комбината приводит к остановке не менее чем на 1 час, а опорного - на 4 часа[23]. Доля затрат на валки в общих расходах составляет от 2 до 15% в цехах горячей прокатки и от 15 до 25% в цехах холодной прокатки [24]. В связи с этим расход валков в значительной мере определяет себестоимость проката. Поэтому отбраковка дефектных валков и продление ресурса бездефектных (предварительно убедившись в отсутствии в них дефектов методами неразрушающего контроля) являются экономически-важными задачами листопроктного производства.
Технология изготовления прокатных валков [4] показывает, что после выплавки, разливки и ковки в них могут оставаться разнообразные дефекты металлургического характера. В присутствии растягивающих остаточных напряжений возможен рост трещин, спровоцированных дефектами, что может привести к разрушению валка еще на стадии производства, при хранении, а также на начальном этапе эксплуатации [23]. По естественному износу выходит из строя меньше половины рабочих и опорных валков. Оставшаяся часть приходит в негодность вследствие полного или частичного разрушения (см. рисунок 4.9).
Наиболее частой причиной преждевременного разрушения валков являются недостатки их изготовления, к которым обычно относятся дефекты макроструктуры: зональная и пятнистая ликвация, внутрикристаллические надрывы, флокены, неметаллические включения, рыхлость, пористость [5]. Отмеченные объёмные дефекты возникают в процессе выплавки и разливки стали и могут послужить причиной зарождения и роста трещин. Последующие технологические операции ковки и предварительной термической обработки направлены на устранение указанных дефектов. Однако, как показывают методы неразрушающего контроля, избавиться от них до конца не удаётся. Практика производства и эксплуатации прокатных валков показывает, что их разрушение до эксплуатации или сразу после завалки в клеть происходит с образованием хрупкого излома [23]. Часто в зоне излома наблюдается незаварившаяся при ковке объёмная несплошность, являющаяся причиной роста трещины, приводящей к излому.
Таким образом, недостатки изготовления в первую очередь влияют на прочность валков как до начала эксплуатации, так и после. Ясно, что конструктивные недоработки и нарушения технологии эксплуатации могут не привести к разрушению валка только в случае отсутствия в нём дефектов недопустимых размеров [5].
Дефекты валка можно разделить на внешние и внутренние. Внешние дефекты начинают своё развитие с поверхности валка и растут в глубину. Наиболее характерными внешними дефектами являются поверхностные трещины, для обнаружения которых используются современные методы и установки вихретокового контроля [18]. Боле опасными, с точки зрения разрушения до начала эксплуатации, являются всё же не внешние, а внутренние дефекты.
