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

Прокопенко Евгения Викторовна

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

КРИВЫХ И ИХ ИСПОЛЬЗОВАНИЕ В ЗАДАЧАХ ИЗУЧЕНИЯ

МНОГОМЕРНЫХ МАССИВОВ

05.13.18 – математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Барнаул, 2009

Работа выполнена на кафедре математического анализа ГОУ ВПО «Кемеровский государственный университет»

Научный руководитель: кандидат физико-математических наук, доцент Ким Виталий Борисович

Официальные оппоненты: доктор физико-математических наук, профессор Родионов Евгений Дмитриевич;

кандидат физико-математических наук, доцент Астраков Сергей Николаевич

Ведущая организация: ГОУ ВПО «Томский государственный университет»

Защита состоится 06 ноября 2009 г. в 16:00 часов на заседании диссертационного совета Д 212.005.04 при ГОУ ВПО «Алтайский государственный университет» по адресу: 656049, г. Барнаул, пр. Ленина, 61.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Алтайский государственный университет» по адресу: 656049, г. Барнаул, пр. Ленина, 61.

Автореферат разослан «_» «_» 2009 г.

Ученый секретарь диссертационного совета д.ф.-м.н., профессор С.А. Безносюк

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

Актуальность исследования.

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

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

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

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

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

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

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

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

Удачным подходом к решению сформулированных задач можно считать сплайновый подход к построению как составных поверхностей, так и кривых.

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

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

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

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

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

Отметим, что проблемам обработки и анализа изображений посвящено множество зарубежных и отечественных журналов «Image and Vision Computing», «Pattern Recognition», «IEEE Image processing», «IEEE Transactions on pattern analysis and machine intelligence», «Journal of mathematical imaging and vision», «Цифровая обработка сигналов», «Информационные технологии».

Исследованиями в области моделирования рельефа занимаются такие известные ученые, как Ю.Л. Костюк, Л.И. Чернова, М.В. Черноусов, В.В. Поддубный, В.Я. Цветков, А.Л. Фукс, С.А. Жихарев. Вопросы геоинформатики рассмотрены в работах А.М. Берлянта, В.С. Тикунова, К.Л. Проворова, Е.Г. Карпова, А.А.

Лютого, А.В. Кошкарева, В.Я. Цветкова, В.А. Коугия, В.П. Кулагина. Визуализацией в геоинформатике занимались: В.Я. Цветков, С.И. Матвеев, Б.А. Левин, У.Д.

Ниясгулов, А.С. Масленников, А.М. Бедлянт, В.С. Тикунов, А.А. Лютый, А.В.

Кошкарев, В.П. Кулагин.

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

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

Для достижения поставленной цели в работе решаются следующие задачи:

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

- классификация и свойства плоских и пространственных элементарных и составных В-сплайновых кривых на основе использования канонических моделей;

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

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

- создание программного комплекса для анализа геоинформационных данных, их сортировки и моделирования рельефа;

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

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

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

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

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

Основные положения, выносимые на защиту:

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

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

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

- разработка программного комплекса для моделирования рельефа и обработки медико-статистических данных.

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

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

- даны классификация и свойства плоских и пространственных элементарных и составных В-сплайновых кривых на основе использования канонических моделей;

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

- создан программный комплекс по моделированию рельефа;

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

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

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

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

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

Апробация работы. Результаты работы докладывались и обсуждались на российских и международных научно-практических конференциях: Региональные конференции по математике на Алтае, «МОНА2006», «МОНА2007», «МОНА2008», г. Барнаул; 7 Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых), 2006, Красноярск; Российская конференция «Математика в современном мире», посвященная 50-летию института математики им. С.Л. Соболева, СО РАН, 2007, Новосибирск; Международная конференция «Геометрия в Одессе - 2008», 2008, Одесса; Международная конференция «Геометрия в Астрахани - 2008», 2008, Астрахань; Всероссийская конференция «Всероссийская конференция по математике и механике с международным участием», 2008, г. Томск;

VI и VII Молодежные школы-конференции «Лобачевские чтения-2007», «Лобачевские чтения-2008», г. Казань; Всероссийская молодежная школа-конференция «Проблема теоретической и прикладной математики» Институт математики и механики УрО РАН, 2009, г. Екатеринбург.

Публикации. По теме диссертации опубликована 21 печатная работа, куда входят (в скобках указан общий объем этого типа публикаций, в знаменателе – объем, принадлежащий лично автору) 1 статья в издании, рекомендованном ВАК (0.25/0.13 печ.л.), 8 – в трудах всероссийских и международных конференций (2,56/2.56 печ.л.), 12 – в тезисах всероссийских и международных конференций (2.31/2.1 печ.л.).

Личный вклад соискателя. При выполнении работ [1, 19], опубликованных совместно с научным руководителем соискатель принимал участие в постановке задач, разработке численных алгоритмов, обсуждении научных результатов, подготовке и представлении статей и докладов на конференциях. Подготовлена программная реализация всех разработанных вычислительных алгоритмов, проведены расчеты тестовых задач и получены результаты экспериментов. Результаты, изложенные в работе, являются новыми и получены автором самостоятельно.

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

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

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

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

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

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

F (u, v) = a111u + 3a112 u v + 3a122 uv + a 222 v.

При классификации используем инварианты формы F(u,v), вычисляя которые, можно определить, к какому из типов относится кубика. Приведем таблицу классификации, данную Н.П. Соколовым1.

Соколов Н.П. Пространственные матрицы и их приложения.– М.: ГИФМЛ, 1960.

Каждой форме F соответствует многочлен f (t ) = 0 t 3 + 3 1t 2 + 3 2 t + 3,где:

t=u/v. Каждому многочлену f(t) соответствует форма: F (u, v) = v 3 f (u / v). При этом из рассмотрения исключается случай v=0, что соответствует t =. Однако это не влияет на общность наших рассуждений, т.к. нас интересует случай, когда параметр t пробегает единичный отрезок. Поэтому при рассмотрении многочленов f(t) будем под инвариантами, r, rA, rB, H, Q этого многочлена подразумевать инварианты соответствующей формы F(u,v), ассоциированной с многочленом. Тогда каждому классу канонических форм будет соответствовать класс форм f(t).

Рассмотрим кривую заданную системой уравнений:

Назовем её кубически параметризованной кривой. Для каждой из форм x(t), y(t), z(t) – можно найти её инварианты и тем самым определить её тип и канонический вид Fi(t). Пусть форме x(t) соответствует канонический вид Fi, форме y(t) – канонический вид Fj, а форме z(t) – канонический вид Fk.

Определение. Кривую – заданную уравнениями назовем канонической моделью типа (Fi,Fj,Fk) кривой Г.

Показано, что можно одним аффинным преобразованием систему уравнений (1) привести к виду (2), следовательно, справедлива теорема:

Теорема 1.1 Существует единственное аффинное преобразование, ставящее в соответствие каждой кубически параметризованной кривой её каноническую модель.

Показано что канонические модели, являются плоскими кривыми. Отсюда следует теорема:

Теорема 1.2 Для любой кубически параметризованной кривой каноническая модель является плоской кривой.

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

Плоскости канонических моделей определяются однозначно. В случае ( i j k ) в пространстве имеется 24 невырожденных модели типа {Fi, F j, Fk }, которые, расположены в соответствующих плоскостях.

При этом получаем всего 6 различных плоскостей:

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

Вторая глава диссертации «Канонические модели В-сплайновых кривых»

посвящена плоским и пространственным элементарным и составным сплайновым кривым, которые относятся к кривым, заданным параметрическими уравнениями третьей степени (сюда входят кривые Безье, В-сплайновые кривые, Бетасплайновые кривые и кривые Catmull-Rom). На практике все известные типы сплайновых кривых задаются с помощью массивов точек или векторов.

Говоря о сплайновых кривых и сплайновых поверхностях, будем понимать их в смысле определения, данных Е.И. Шикиным и А.И. Плиссом в работе [69].

Согласно этим определениям, смежные куски составных кривых или поверхностей могут стыковаться не только по граничным точкам или кривым, как это имеет место для классических сплайновых кривых и поверхностей, а даже иметь общие участки – так называемые перекрытия. Указанное отличие от классического определения сплайна позволяет гарантировать гладкость построенной кривой (поверхности).

Определение2 Задан массив вершин P = {Pi ( xi, y i, z i ), i = 0,1,..m}. Матричная запись параметрических уравнений, описывающих элементарную кубическую сплайновую кривую имеет вид: R(t)=PMT, где:

порождающий сплайновую кривую, матрица М – имеет вид:

Шикин, Е.В. Кривые и поверхности на экране компьютера / Е.В. Шикин, А.И. Плис. – М.: ДИАЛОГ-МИФИ, 1996.

Связь между базисными матрицами этих кривых выражается следующими соотношениями:

где:

Заметим, что матрица Mb является матрицей полиномов Бернштейна относительно естественного базиса e1 = t 3, e2 = t 2, e3 = t, e4 = 1. Они образуют базис Бернштейна для множества всех полиномов одной переменной степени три, т.е. любой полином третьей степени от одной переменной можно представить в виде линейной комбинации из полиномов Бернштейна.

Определены канонические типы многочленов Бернштейна:

Аналогично рассмотрены многочлены, определяемые матрицей C:

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

Заметим, что из рассмотренных базисов {pi}, {qi}, {ni}– только в базис {ni} входят формы всех четырех канонических типов.

Рассмотрены параметрические уравнения элементарной В-сплайновой кривой, порожденной массивом P = {Pi ( xi, y i, z i ), i = 0,1,2,3}.

Эта кубическая В-сплайновая кривая определяется уравнениями:

Записываем эти уравнения в виде:

Коэффициенты Ai,j,k, Bi,j,k, Ci,j,k В-сплайновой кривой определяются через точки массива однозначно. Для В-сплайновой кривой найдены инварианты, определенные выше. Покажем некоторые из них на примере формы x(t).

Дискриминант:

Гессиан:

Якобиан:

Для форм y(t) и z(t) соответствующие инварианты получаются из вышеприведенных формул заменой переменной x на переменные y и z соответственно.

Следствие. Для каждой из форм x(t), y(t), z(t) имеет место соотношение:

D =, где D – дискриминант формы, – дискриминант Гессиана формы.

Рассмотрены конфигурации, образованные каноническими моделями и их плоскостями для В-сплайновых кривых. Рассмотрен случай, когда типы координатных форм различны – {Fi, F j, Fk }, i j k. Найдены плоскости, в которых расположены каноническая модель каждой кривой.

Теорема 2.1 Каноническая модель кривой типа {Fi, F j, Fk } лежит в одной из следующих плоскостей:

Каждой из плоскостей принадлежит несколько типов канонических моделей, например:

Рассмотрена конфигурация, которую образуют канонические модели.

На рисунке 1 изображены примеры канонических моделей. На рисунке 2 изображена проекция плоскостей, указанных в теореме 2.1, параллельно вектору n=(1,1,1) на плоскость x+y+z=1.

Рассмотрены случаи моделей типа: {Fi, Fi, F j }, {Fi, Fi, Fi }.

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

Так как сплайновые кривые определяются массивом, то каноническую модель для соответствующей В-сплайновой кривой также можно определить массивом точек – назовем его каноническим массивом. Например:

Кривой типа (F2,F1',F1) соответствует массив: Pk = 0 6.

Рассмотрен вопрос построения модели для составных сплайновых кривых.

Определение3 (Составной) кубической В-сплайновой кривой, определяемой массивом, P0,…, Pm, m 3 называется кривая, которую можно представить в виде объединения элементарных кубических В-сплайновых кривых (1),..., ( m2) = (1)... ( m2) ; (i) – я кривая i описывается параметрическим уравнением вида: R (i ) (t ) = ( Pi 1 Pi Pi +1 Pi + 2 ) MT,0 t 1, i = 1,..., m 2, где М – базисная матрица кубической В-сплайновой кривой.

Каждая кривая Ri(t) имеет свою каноническую модель. Пусть Rl(t) – l-ый кусок составной В-сплайновой кривой. Его модель будет иметь тип – ( Fil, F jl, Fkl ) и будет лежать в соответствующей канонической плоскости, определенной таблицей. Смежные куски Rl-1(t) и Rl+1(t) будут иметь канонические модели типа ( Fil 1, F jl 1, Fkl 1 ) и ( Fil +1, F jl +1, Fkl +1 ), и лежать в соответствующих канонических плоскостях. Заметим, что число канонических плоскостей для составной кривой не превышает числа элементарных кривых. Это связано с тем, что число канонических плоскостей меньше числа канонических моделей.

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

Теорема 2.2 Для составных кривых, состоящих из (n-2) элементарных кривых, модель представляет собой объединение из (n-2) - канонических моделей, соответствующих элементарных кривых.

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

Рассмотрены плоские В-сплайновые кривые. Не умаляя общности, можно считать, что кривая Г находится в плоскости z (t ) = 0, а её параметрические уравнения имеют вид:

Шикин, Е.В. Кривые и поверхности на экране компьютера / Е.В. Шикин, А.И. Плис. – М.: ДИАЛОГ-МИФИ, 1996.

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

Определение. Кривую – заданную уравнениями где каждая из форм x(t ), y (t ) – имеет канонический тип Fi, (i = 1,2,3,1) соответственно, назовем канонической моделью кривой Г типа {Fi, F j }, i j.

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

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

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

Известна гипотеза Фокса и Пратта4, которые утверждают, что если X – точка пересечения прямых S0S1 и S2S3, где S0S1= S0Х и S2S3= ХS3, и параметры и Фокс, А. Вычислительная геометрия. Применение в проектировании и на производстве / А. Фокс, М. Пратт. М.: МИР, - 1982. – 304с.

удовлетворяют соотношению ( 4 / 3)( 4 / 3) > 4 / 9, > 1, > 1, то кривая Безье, порожденная массивом S 0, S1, S 2, S 3, будет иметь самопересечение, и будет образовывать петлю.

При исследовании В-сплайновых кривых с помощью системы Maple, были построены примеры кривых Безье, для которых оба условия выполняются, но петля отсутствует.

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

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

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

Представлены преимущества сплайновой модели, её особенности. Приведены необходимые сведения о системе аналитических вычислений Maple V и о высокоуровневом языке программирования Visual FoxPro. Дано краткое описание пакетов встроенных процедур, используемых при решении, выше указанных задач. Описаны комплексы компьютерных моделей и алгоритмы, реализованные в пакете символьной математики Maple и высокоуровневом языке программирования Visual FoxPro и используемые при решении данных задач.

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

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

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

Главным преимуществом сплайновой модели является ее гладкость. Сравним две поверхности: кубическую В-сплайновую поверхность и поверхность Безье.

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

Рассмотрена следующая задача, возникающая при моделировании рельефа по геоинформационным данным. Дан набор точек с координатами (X,Y,Z). Обозначим исходный массив как: P = ( xi yi z i, i = 1,.., N ).

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

Предложена математическая модель построения поверхностей, а также способ сглаживания на поверхности точек «выброса».

Одна из проблем построения поверхности заключается в том, что построенная по данному массиву В-сплайновая поверхность не проектируется на плоский массив (X,Y). Чтобы исправить данную ситуацию, используем метод «кратных точек»5, а именно – добавляем «кратные точки» на границах поверхности по следующему алгоритму:

Для массива P = {Pij, i = 0,.., m, j = 0,..., n}, зададим 2m + 2n + 8 новых вершин, положив:

Эти вершины как бы «окаймляют» заданный массив Р и вместе с ним образуют новый массив P* = {Pi, j, i = 1,..., m + 1, j = 1,.., n + 1} из (m + 3)(n + 3) вершин.

Как множества точек массивы Р и Р* неразличимы, так как все добавляемые вершины отличаются от заданных только номерами – геометрически новых вершин не появилось. Это позволяет рассматривать В-сплайновую поверхность как поверхность, построенную над массивом (X,Y).

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

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

Шикин, Е.В. Кривые и поверхности на экране компьютера / Е.В. Шикин, А.И. Плис. – М.: ДИАЛОГ-МИФИ, 1996.

Проведен анализ моделирования рельефа, его результаты показывают, что построенная поверхность достаточно хорошо моделирует реальный рельеф. Относительная погрешность на исследуемом массиве не превышает 0,012%. Программа реализована при помощи языка программирования Visual FoxPro и пакета символьной математики Maple V.

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

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

На первом этапе мы строим В-сплайновую кривую, находим каноническую модель. На втором этапе определяем для каких массивов точек каноническая модель не определяется. На третьем – выделяем соответствующие точки (массивы данных), и эти данные используются врачом, которые дают им медицинскую интерпретацию.

Исследуя канонические модели составной кривой, построенной по данному массиву, видим, что в некоторых точках канонический тип кривой не определяется. Рассмотрение этих данных на конкретных примерах, показало, что данный период совпадает с «критическим» периодом, т.е. с периодом возможного наилучшего исхода лечения, т.е. выздоровления, либо, в противном случае – риском летального исхода.

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

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

В приложении 1 представлены листинг программных модулей, разработанных в системе Maple и с использованием высокоуровневого языка программирования Visual FoxPro; результаты моделирования рельефа.

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

В ходе проведенного исследования решены поставленные задачи и достигнуты следующие результаты:

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

- предложена классификация и изучены свойства плоских и пространственных элементарных и составных В-сплайновых кривых на основе использования канонических моделей;

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ИССЛЕДОВАНИЯ

1. Прокопенко, Е.В. Составная В-сплайновая кривая, построенная на базе канонических моделей / Е.В. Прокопенко, В.Б. Ким // Вестник Поморского университета. Серия «Естественные и точные науки». – 2009. – № 2. – С. 83-86.

2. Прокопенко, Е.В. О проблеме классификации В-сплайновых кривых / Е.В.

Прокопенко // 6 Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям: материалы международной конференции. – Кемерово, 2005. – С. 24-25.

3. Прокопенко, Е.В. Об одном классе В-сплайновых кривых / Е.В. Прокопенко // Вестник КемГУ. – Кемерово, 2005. – №4. – С. 182-186.

4. Прокопенко, Е.В. Сравнение кривизны кривых, построенных по методу закругленности с В-сплайновыми кривыми, на примере массива точек выбранного по базисным функциям и произвольному массиву точек / Е.В. Прокопенко // Труды СГУ. – М., 2006. – С. 91-97.

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

5. Прокопенко, Е.В. Инварианты двойничных кубических форм и сплайновые кривые / Е.В. Прокопенко // Математическое образование на Алтае «МОНА 2006»: тезисы региональной конференции. – Барнаул, 2006. – С. 30-31.

6. Прокопенко, Е.В. Сплайновый подход к результатам графической обработки эксперимента / Е.В. Прокопенко // 7 Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (с участием иностранных ученых): тезисы всероссийской конференции. – Красноярск, 2006. – С. 26.

7. Прокопенко, Е.В. Об одной конструкции ассоциированной и В-сплайновой кривой / Е.В. Прокопенко // Наука и образование: материалы международной конференции. – Белово, 2006. – С. 516-520.

8. Прокопенко, Е.В. Об одном свойстве кривой Безье / Е.В. Прокопенко // Образование, наука, инновации – вклад молодых исследователей: материалы международной научно-практической конференции. – Кемерово, 2006. – Режим доступа: http://conference.kemsu.ru/conf/aprel2006/sect/index.dhtm?sec_id=719. – С. 16.

9. Прокопенко, Е.В. Об оценке параметров, влияющих на форму сплайновой кривой / Е.В. Прокопенко // Математика в современном мире : тезисы российской конференции, посвященной 50-летию института математики им. С.Л. Соболева, СО РАН. – Новосибирск, 2007. – Режим доступа: http://math.nsc.ru /conference/conf50/Abstracts.pdf. – С. 88-89.

10. Прокопенко, Е.В. Зависимость формы В-сплайновой кривой от опорного массива / Е.В. Прокопенко // Образование, наука, инновации – вклад молодых исследователей : материалы международной научно-практической конференции. – Кемерово, 2007. – Режим доступа: http://conference.kemsu.ru/conf/aprel /sect/index.dhtm?sec_id=831.– С.70.

11. Прокопенко, Е.В. Классификация В-сплайновых кривых с использованием кубических матриц / Е.В. Прокопенко // Математическое образование в регионах России : труды региональной конференции. – Барнаул, 2007. – С. 39-44.

12. Прокопенко, Е.В. Канонические модели кубически параметризованных кривых / Е.В. Прокопенко // Геометрия в Одессе – 2008 : тезисы международной конференции. – Одесса, 2008. – С.120-122.

13. Прокопенко, Е.В. К вопросу о классификации кубических сплайновых кривых / Е.В. Прокопенко // Геометрия в Астрахани – 2008 : тезисы международной конференции. – Астрахань, 2008. – С.45-48.

14. Прокопенко, Е.В. Канонические модели кубически параметризованных кривых / Е.В. Прокопенко // Исследовано в России. – Режим доступа:

http://zhurnal.ape.relarn.ru/articles/2008/029.pdf. – С. 329-337.

15. Прокопенко, Е.В. Канонические модели сплайновых кривых / Е.В. Прокопенко // Всероссийская конференция по математике и механике с международным участием : тезисы всероссийской конференции. – Томск, 2008. – С. 109-110.

16. Прокопенко, Е.В. Плоская составная В-сплайновая кривая, построенная на базе канонических моделей / Е.В. Прокопенко // Математическое образование на Алтае, «МОНА 2008» : тезисы региональной конференции. – Барнаул, 2008. – С. 71-76.

17. Прокопенко, Е.В. Составная В-сплайновая кривая, построенная на базе канонических моделей / Е.В. Прокопенко // Лобачевские чтения-2008 : тезисы VII международной школы-конференции. – Казань, 2008. – №37. – С. 144-146.

18. Прокопенко, Е.В. Канонические модели плоских В-сплайновых кривых / Е.В. Прокопенко // Вестник КемГУ. – Кемерово, 2008. – №3(35). – С. 13-19.

19. Прокопенко, Е.В. Составная В-сплайновая кривая, построенная на базе канонических моделей / Е.В. Прокопенко, В.Б. Ким // Проблема теоретической и прикладной математики : тезисы всероссийской молодежной школы-конференции / Институт математики и механики УрО РАН. – Екатеринбург, 2009. С. 83-87.

20. Прокопенко, Е.В. Сплайновые кривые в медицинских исследованиях / Е.В. Прокопенко // Образование, наука, инновации – вклад молодых исследователей, IV (XXXVI): тезисы международной научно-практической конференции. – Кемерово, 2009. – С. 179-183.

21. Прокопенко, Е.В. Канонические модели сплайновых кривых в медицинских исследованиях / Е.В. Прокопенко // МАК-2009 : тезисы двенадцатой региональной конференции по математике. – Барнаул, 2009. – С. 106-108.