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

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

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Математичні машини і системи
Дата:2015
Автори: Вишневский, В.В., Калмыков, В.Г., Романенко, Т.Н.
Формат: Стаття
Мова:Російська
Опубліковано: Інститут проблем математичних машин і систем НАН України 2015
Теми:
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/113751
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами / В.В. Вишневский, В.Г. Калмыков, Т.Н. Романенко // Математичні машини і системи. — 2015. — № 4. — С. 57-64. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
_version_ 1860254323459489792
author Вишневский, В.В.
Калмыков, В.Г.
Романенко, Т.Н.
author_facet Вишневский, В.В.
Калмыков, В.Г.
Романенко, Т.Н.
citation_txt Аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами / В.В. Вишневский, В.Г. Калмыков, Т.Н. Романенко // Математичні машини і системи. — 2015. — № 4. — С. 57-64. — Бібліогр.: 8 назв. — рос.
collection DSpace DC
container_title Математичні машини і системи
description Обсуждается алгоритм вычисления коэффициентов параметрического сплайна, аппроксимирующего последовательности экспериментальных данных. Приведены обобщения, позволяющие использовать данный алгоритм для одно-, дву- и трехмерного случаев представления экспериментальных данных. Обговорюється алгоритм обчислення коефіцієнтів параметричного сплайну, що апроксимує послідовності експериментальних даних. Наведені узагальнення, які дозволяють використовувати цей алгоритм для одно-, дво- та тривимірного випадків представлення експериментальних даних. We discuss the algorithm for calculating the coefficients of the parametric spline for approximating sequences of experimental data. We showed the generalizations, which allow using this algorithm for one-, two- and three-dimensional cases of the experimental data submission.
first_indexed 2025-12-07T18:47:02Z
format Article
fulltext © Вишневский В.В., Калмыков В.Г., Романенко Т.Н., 2015 57 ISSN 1028-9763. Математичні машини і системи, 2015, № 4 УДК 004.896 В.В. ВИШНЕВСКИЙ*, В.Г. КАЛМЫКОВ*, Т.Н. РОМАНЕНКО* АППРОКСИМАЦИЯ ОДНО-, ДВУ- И ТРЕХМЕРНЫХ ДУГ КРИВЫХ ПАРАМЕТРИЧЕСКИМИ СПЛАЙНАМИ * Институт проблем математических машин и систем НАН Украины, Киев, Украина Анотація. Обговорюється алгоритм обчислення коефіцієнтів параметричного сплайну, що апрок- симує послідовності експериментальних даних. Наведені узагальнення, які дозволяють використо- вувати цей алгоритм для одно-, дво- та тривимірного випадків представлення експериментальних даних. Ключові слова: контур, експериментальні дані, апроксимація, параметричний сплайн, класифіка- ція. Аннотация. Обсуждается алгоритм вычисления коэффициентов параметрического сплайна, ап- проксимирующего последовательности экспериментальных данных. Приведены обобщения, позво- ляющие использовать данный алгоритм для одно-, дву- и трехмерного случаев представления экс- периментальных данных. Ключевые слова: контур, экспериментальные данные, аппроксимация, параметрический сплайн, классификация. Abstract. We discuss the algorithm for calculating the coefficients of the parametric spline for approx- imating sequences of experimental data. We showed the generalizations, which allow using this algorithm for one-, two- and three-dimensional cases of the experimental data submission. Keywords: circuit, experimental data, approximation, parametric spline, classification. 1. Введение Очень часто исследователь сталкивается с задачей построения алгоритма классификации тех или иных объектов по их форме. Примеров таких задач можно привести множество. Например, анализ формы временного ряда, анализ формы спектрограмм, анализ формы элементов циклических сигналов в медицине, классификация бинарных и полутоновых изображений по форме элементов контуров этих изображений и т.д. Объединяет все эти задачи одно обстоятельство: все они, в конечном счете, могут быть сведены к задаче клас- сификации формы одной или нескольких дуг кривых в одно-, дву- или трехмерном про- странстве координат. В целом ряде статей мы уже рассматривали подходы к решению таких задач при выделении признаков формы кривых, описывающих те или иные экспериментальные дан- ные [1, 2]. В этой статье решено привести обобщение алгоритмического базиса при пред- варительной обработке данных, которые могут быть описаны одной или несколькими ду- гами кривых, для всех случаев пространств координат. Заметим, что описываемые алго- ритмы относятся к этапу предварительной обработки исходных данных и построения сис- темы признаков, чувствительных к форме объектов, для решения задачи классификации [3, 4]. Сама же классификация объектов по их форме в данной статье не рассматривается. 2. Постановка задачи Итак, пусть в результате некоего физического процесса мы получаем дискретные экспери- ментальные данные ( ){ }mxX = , Mm ,0= для одномерного, ( ){ }mxX = , ( ){ }myY = для двумерного и ( ){ }mxX = , ( ){ }myY = , ( ){ }mzZ = для трехмерного случаев, которые иссле- дователем воспринимаются как дискретные отсчеты некоей дуги кривой одномерной, пло- ской или пространственной. Исследователю важно классифицировать форму этой дуги 58 ISSN 1028-9763. Математичні машини і системи, 2015, № 4 кривой, но закон ее построения в общем случае не известен. Исходные экспериментальные данные могут быть заменены аналитическими кри- выми, хорошо совпадающими по форме с кривой исходного контура и в то же время инва- риантными относительно изменения масштаба, количества измерений, уровня помех. Та- кие кривые задаются функциями ( )kx , ( )ky , которые представляют собой полиномы r - ной степени от параметра k : ( ) ,... 1 1 10 rr kr akakakakx ++++= − − (1) ( ) rr kr bkbkbkbky ++++= − − 1 1 10 ... . Выбор r -ной степени полиномов зависит от сложности аппроксимируемых конту- ров. Реализация такого подхода позволяет отобразить все существенные особенности формы кривой, исключив влияние помех. Кроме того, вместо описаний контуров в про- странстве сигналов можно рассматривать аппроксимирующие их полиномы в пространст- ве их коэффициентов. Существенным преимуществом такого описания является его инва- риантность относительно количества измеренных сигналов в каждом массиве эксперимен- тальных данных. В качестве аппроксимирующего параметрического сплайна можно использовать кривую Безье, канонический сплайн (cardinal spline) [5]. В данной работе будет описано применение канонического сплайна третьего порядка. Канонический сплайн – это последовательность полиномов третьего порядка, каж- дый из которых может быть записан параметрическим уравнением общего вида (2). Кри- вые, соответствующие полиномам, начинаются и заканчиваются в управляющих точках, образуя плавную односвязную кривую (рис. 1). ( ) ,23 xxxx dkckbkakx +++= (2) ( ) .23 yyyy dkckbkaky +++= Для аппроксимации последовательности большого количества экспериментальных данных, являющихся реализацией кривых сложной формы, ис- пользуют кардинальные кубические сплайны [5, 7]. Кардиналь- ные кубические сплайны являются последовательностью N ку- бических полиномов, которые определяются управляющими точками ( )nxv = или { }nn yxv ,= , или { }nnn zyxv ,,= , MNNn <<+= ,1,1 . Каждое значение n в последовательности управляющих точек соответствует некоторому значению nm в последовательности измерений. Будем рассматривать только корректные последовательности управляющих точек. Под кор- ректной последовательностью будем понимать такую последовательность, при которой выполняется условие 1+< nn mm . Количество полиномов в последовательности определяет- ся сложностью формы аппроксимируемой экспериментальной кривой. Последователь- ность полиномов ( ) ( ){ }nn tXtX = , ( ) ( ){ }nn tYtY = , ( ) ( ){ }nn tZtZ = соответствует каждой из пространственных координат. Коэффициенты каждого из полиномов в последовательно- сти, например, для координаты x : ( ) nxnxnxnxn dkckbkakX +++= 23 , определяются значе- ниями в управляющих точках 1−nx , nx , 1+nx , 2+nx : Рис. 1. Канонический сплайн x 1 , y 1 x 2 , y 2 x n , y n x 0 , y 0 ISSN 1028-9763. Математичні машини і системи, 2015, № 4 59 ( ) ( ) ( ) ( ) ( ) , , )3(,332 ,22 11 1211 1211 nnx nnnx nnnnnnnx nnnnnnnx xd xxTc xxxxTxxTb xxxxTxxTa = −= +−−−−−= −+−+−= −+ ++−+ ++−+ где T – натяжение (при 0=T кривая вырождается в прямую). Для большинства практиче- ских применений используют значение T =0,5. Для незамкнутых кривых при 11:1 xxn n == − , при Nn xxNn == +1: . Для аппроксимируемой последовательности экспериментальных данных находят такую кривую, которая наилучшим образом отображает ее форму, а это значит, что вычис- ляют координаты управляющих точек этой кривой и, следовательно, коэффициенты сплайна. В результате последовательность экспериментальных данных будет представлена вектором v , компонентами которого являются коэффициенты канонического сплайна (4). В качестве меры сходства аппроксимирующего сплайна и последовательности экс- периментальных данных будем использовать оценку площади фигуры, ограниченной кон- туром, образованным расчетной кривой и ломаной линией, последовательно соединяющей экспериментальные данные ( )PGS , . Тогда поиск сплайна, наилучшим образом аппрокси- мирующего последовательность экспериментальных данных, можно рассматривать как вычисление оптимальных коэффициентов optv , при которых минимизируется значение оценки площади (5). },,{ nn yx=ν (4) ( )PGSvopt ,minarg ν = , (5) где G – последовательность экспериментальных данных ( )gmgmm yxg , ; P – точки аппроксимирующего сплайна ( )pmpmm yxp , ; MMm ,,0= – количество отсчетов в последовательности экспериментальных данных. Минимизация указанной меры сходства (5) достигается методом градиентного спуска [6]. Общий алгоритм итерационной процедуры аппроксимации экспериментальных данных параметрическими сплайнами с использованием итерационного метода градиент- ного спуска представлен на рис. 2. На старте алгоритма имеем произвольное приближение сплайна к последовательности экспериментальных точек. Оцениваем меру сходства и про- изводим шаг градиентного спуска по одному из возможных направлений. Снова оценива- ем меру сходства и делаем шаг в другом направлении градиентного спуска. Такая проце- дура выполняется до тех пор, пока величина изменения меры сходства становится меньше некоторого заранее заданного значения ε . Возможная ситуация с отсутствием сходимости итерационного алгоритма блокируется заранее заданным максимальным количеством ите- раций. 3. Аппроксимация одномерной последовательности экспериментальных данных Одномерную последовательность получим в том случае, если экспериментальные данные будут представлены в виде последовательности измерений или таблицы, в которой с каж- дым отсчетом (или индексом в таблице) связано одно значение интересующей величины. Примером таких данных могут быть измерения температуры воздуха или атмосферного давления через равные промежутки времени, измерения оптической плотности через рав- 60 ISSN 1028-9763. Математичні машини і системи, 2015, № 4 Рис. 3. Аппроксимация одномерной последовательности экспериментальных данных Начальное положение аппроксимирующей кривой v=[y(k),t(k)] Точки на аппроксимирующей кривой Pn с шагом ∆k (n=[0;N]) p0(yp0, tp0), p1(yp1, tp1), … pN (ypN, tpN) Аппроксимируемая последова- тельность G =(g1,g2,…gM) g0(yg0, tg0), g1(yg1, tg1), … gM (ygM, tgM) pm(ypm, tpm) gm(ygm, tgm) Минимизируемый параметр ные интервалы длин волн и т.п. Ось ординат тогда будет отображать интересующую вели- чину, а ось абсцисс – номера отсчетов (или моменты времени измерений, длины волн для вышеприведенных примеров). Характерным для такой дуги является ее однозначность от- носительно оси абсцисс. В этом случае вектор управляющих точек сплайна будет выглядеть как (6) },{ nn tyv → . (6) На рис. 3 представлена иллюстрация работы алгоритма аппроксимации одномерной последовательности экспериментальных данных в наглядном виде. Рис. 2. Схема алгоритма аппроксимации экспериментальных данных параметрическими сплайнами Начальное приближение координат управляющих точек Оценка площади S фигуры, ограниченной контуром S < ε Да Нет Определение направления изменения координат упр. точек Изменение координат управляющих точек Результат vopt ISSN 1028-9763. Математичні машини і системи, 2015, № 4 61 Рис. 4. Примеры аппроксимации спектрограмм каноническими сплайнами Рис. 5. Аппроксимация двумерной последовательности экспериментальных данных pm(xpm, ypm, tpm) Начальное положение ап- проксимирующей кривой v=[x(k), y(k), t(k)] Точки на аппроксимирующей кривой Pn − с шагом ∆k (n=[0;N]) p0(xp0, yp0, tp0), p1(xp1, yp1, tp1), … pN (xpN, ypN, tpN) Аппроксимируемый кон- тур G =(g0,g1,…gM), g0(xg0, yg0, tg0), g1(xg1, yg1, tg1), … gM (xgM, ygM, tgM) gm(xgm, ygm, tgm) Минимизируемый параметр 4. Экспериментальная проверка алгоритма Алгоритм был экспериментально проверен для более 1000 реальных графиков спектро- грамм медицинских препаратов крови, полученных по методу «Онкотест» [2]. На рис. 4 представлены примеры аппроксимации спектрограмм. Как видно из рисунка, по оси абс- цисс отображена длина волны, причем интервалы между отдельными отсчетами по этой оси равны, что позволяет заменить значения длины волны на номер отсчета и рассматри- вать спектрограмму как пример одномерной последовательности экспериментальных дан- ных. 5. Аппроксимация двумерной последовательности экспериментальных данных Двумерную последовательность получим, если экспериментальные данные представлены в виде таблицы, в которой с каждым отсчетом (или индексом) связана пара значений инте- ресующих величин. Как пример такой последовательности может быть приведен плоский контур (контур бинарного изображения). В этом случае вектор управляющих точек сплайна будет выглядеть как (7) },,{ nnn tyxv → . (7) На рис. 5 представлена иллюстрация работы алгоритма аппроксимации двумерной последовательности экспериментальных данных в наглядном виде. 62 ISSN 1028-9763. Математичні машини і системи, 2015, № 4 Начальное положение ап- проксимирующей кривой v=[x(k), y(k), z(k), t(k)] Точки на аппроксимирующей кривой Pn − с шагом ∆k (n=[0;N]) p0(xp0, yp0, zp0, tp0), p1(xp1, yp1, zp1, tp1), … pN (xpN, ypN, zpN, tpN) Аппроксимируемая дуга G =(g0,g1,…gM), g0(xg0, yg0, zg0, tg0), g1(xg1, yg1, zg1, tg1), … gM (xgM, ygM, zgM, tgM) pm(xpm, ypm, zpm, tpm) gm(xgm, ygm, zgm, tgm) Рис. 7. Аппроксимация трехмерной дуги 6. Экспериментальная проверка алгоритма Алгоритм был использован для аппроксимации двумерных контуров, некоторые результа- ты представлены на рис. 6. В данном случае каждый отсчет последовательности экспери- ментальных данных характеризуется двумя значениями – по оси абсцисс и по оси ординат, кроме того, такой контур не является односвязным по оси абсцисс, поэтому его можно рассматривать при аппроксимации как пример двумерной последовательности. 7. Аппроксимация трехмерной последовательности экспериментальных данных Трехмерную последовательность получим, если экспериментальные данные представлены в виде таблицы, в которой с каждым отсчетом (или индексом) связана тройка значений ин- тересующих величин. Как пример можно привести электрокардиограмму в трех ортого- нальных отведениях [8]. В этом случае вектор коэффициентов сплайна будет выглядеть как (8) },,,{ nnnn tzyxv → . (8) На рис. 7 представлен алгоритм аппроксимации трехмерной последовательности экспериментальных данных (трехмерной дуги) в наглядном виде. В случае трехмерной по- следовательности каждый отсчет экспериментальных данных и каждая точка аппроксими- рующего сплайна характеризуются тремя координатами. Иными словами, и эксперимен- Рис. 6. Примеры аппроксимации двумерных контуров каноническими сплайнами ISSN 1028-9763. Математичні машини і системи, 2015, № 4 63 Рис. 8. Пример аппроксимации электрокар- диограммы в ортогональных отведениях каноническим сплайном Рис. 9. Результаты аппроксимации электро- кардиограмм в ортогональных отведениях двух различных пациентов тальные данные, и аппроксимирующий сплайн представляют собой трехмерные дуги. То- гда в качестве меры их сходства нужно использовать оценку площади поверхности, огра- ниченной этими двумя пространственными кривыми. 8. Экспериментальная проверка алгоритма Алгоритм был использован для аппроксимации электрокардиограмм в ортогональных от- ведениях. Так как каждый отсчет такой электрокардиограммы характеризуется тремя зна- чениями, ее можно использовать при аппроксимации как пример трехмерной последова- тельности экспериментальных данных (трехмерной дуги). На рис. 8 изображена часть электрокардиограммы в виде трехмерной дуги, постро- енная по трем ортогональным отведениям, и аппроксимирующий ее канонический сплайн. На рис. 9 приведены две аппроксимированные каноническими сплайнами электрокардио- граммы в ортогональных отведениях для различных пациентов. 9. Заключение Предложенный алгоритм позволяет вычислить коэффициенты параметрического сплайна, аппроксимирующего последовательности экспериментальных данных и может быть ис- пользован для одно-, дву- и трехмерного случаев представления исходных эксперимен- тальных данных. Применение данного алгоритма для предварительной обработки исходных данных позволяет построить систему признаков, чувствительных к форме объекта, которую удоб- но применять при решении задач классификации. СПИСОК ЛИТЕРАТУРЫ 1. Вишневский В.В. Аппроксимация экспериментальных данных кривыми Безье / В.В. Вишневский, В.Г. Калмыков, Т.Н. Романенко // XIII-th International Conference KDS-2007. – Varna, Bulgaria, 2007. – June. – P. 3 – 9. 2. Вишневский В.В. Программно-аппаратный комплекс «Онкотест-WM-01» / В.В. Вишневский, В.А. Владимиров, Т.Н. Романенко // Тезисы доклада ІІ международной школы-семинара «Телемедицина – опыт и перспективы». – Донецк, 2006. – Т. 4, № 2. – С. 62 – 65. 3. Вишневський В.В. Біометрична ідентифікація за допомогою електрокардіограми / В.В. Вишневський, Т.М. Романенко, Л.А. Кізуб // V міжнар. наук.-практ. конф. "Інформаційні технології та комп'ютерна інженерія" ІТКІ 2015. – Івано-Франківськ, 2015. – С. 130 – 131. 64 ISSN 1028-9763. Математичні машини і системи, 2015, № 4 4. Вишневський В.В. Біометрична ідентифікація людини за її електрокардіограмою / В.В. Вишневський, Т.М. Романенко, Л.А. Кізуб // III міжнар. наук.-практ. конф. "Обчислювальний інтелект (результати, проблеми, перспективи)" ComInt 2015. – Черкаси, 2015. – С. 295. 5. Петцольд Ч. Программирование для Microsoft Windows на C#: в 2-х т. / Петцольд Ч.; пер. с англ. – М.: Русская редакция, 2002. − Т. 2. – С. 632 – 641. 6. Корн Г. Справочник по математике / Г. Корн, Т. Корн. − М.: Наука, 1974. − С. 660 − 661. 7. Vishnevskey V. Approximation of Planar and Spatial Experimental Curves by Splines that are Defined Parametrically / V. Vishnevskey, T. Romanenko, V. Kalmykov // Proc. of the international conference on applications of information and communication technology and statistics in economy and education ICAICTSEE-2014. – UNVE, Sofia, Bulgaria, 2014. – Осtober 24–25th. – P. 236 – 240. 8. Орлов В.Н. Руководство по электрокардиографии / Орлов В.Н. – М.: Медицинское информационное агентство, 2012. – С. 58. Стаття надішла до редакції 24.09.2015
id nasplib_isofts_kiev_ua-123456789-113751
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn 1028-9763
language Russian
last_indexed 2025-12-07T18:47:02Z
publishDate 2015
publisher Інститут проблем математичних машин і систем НАН України
record_format dspace
spelling Вишневский, В.В.
Калмыков, В.Г.
Романенко, Т.Н.
2017-02-13T16:09:20Z
2017-02-13T16:09:20Z
2015
Аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами / В.В. Вишневский, В.Г. Калмыков, Т.Н. Романенко // Математичні машини і системи. — 2015. — № 4. — С. 57-64. — Бібліогр.: 8 назв. — рос.
1028-9763
https://nasplib.isofts.kiev.ua/handle/123456789/113751
004.896
Обсуждается алгоритм вычисления коэффициентов параметрического сплайна, аппроксимирующего последовательности экспериментальных данных. Приведены обобщения, позволяющие использовать данный алгоритм для одно-, дву- и трехмерного случаев представления экспериментальных данных.
Обговорюється алгоритм обчислення коефіцієнтів параметричного сплайну, що апроксимує послідовності експериментальних даних. Наведені узагальнення, які дозволяють використовувати цей алгоритм для одно-, дво- та тривимірного випадків представлення експериментальних даних.
We discuss the algorithm for calculating the coefficients of the parametric spline for approximating sequences of experimental data. We showed the generalizations, which allow using this algorithm for one-, two- and three-dimensional cases of the experimental data submission.
ru
Інститут проблем математичних машин і систем НАН України
Математичні машини і системи
Інформаційні і телекомунікаційні технології
Аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами
Апроксимація одно-, дво- і тривимірних дуг кривих параметричними сплайнами
Approximation of one-, two- and three-dimensional curve arcs by parametric splines
Article
published earlier
spellingShingle Аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами
Вишневский, В.В.
Калмыков, В.Г.
Романенко, Т.Н.
Інформаційні і телекомунікаційні технології
title Аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами
title_alt Апроксимація одно-, дво- і тривимірних дуг кривих параметричними сплайнами
Approximation of one-, two- and three-dimensional curve arcs by parametric splines
title_full Аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами
title_fullStr Аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами
title_full_unstemmed Аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами
title_short Аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами
title_sort аппроксимация одно-, дву- и трехмерных дуг кривых параметрическими сплайнами
topic Інформаційні і телекомунікаційні технології
topic_facet Інформаційні і телекомунікаційні технології
url https://nasplib.isofts.kiev.ua/handle/123456789/113751
work_keys_str_mv AT višnevskiivv approksimaciâodnodvuitrehmernyhdugkrivyhparametričeskimisplainami
AT kalmykovvg approksimaciâodnodvuitrehmernyhdugkrivyhparametričeskimisplainami
AT romanenkotn approksimaciâodnodvuitrehmernyhdugkrivyhparametričeskimisplainami
AT višnevskiivv aproksimacíâodnodvoítrivimírnihdugkrivihparametričnimisplainami
AT kalmykovvg aproksimacíâodnodvoítrivimírnihdugkrivihparametričnimisplainami
AT romanenkotn aproksimacíâodnodvoítrivimírnihdugkrivihparametričnimisplainami
AT višnevskiivv approximationofonetwoandthreedimensionalcurvearcsbyparametricsplines
AT kalmykovvg approximationofonetwoandthreedimensionalcurvearcsbyparametricsplines
AT romanenkotn approximationofonetwoandthreedimensionalcurvearcsbyparametricsplines