Итерационный алгоритм построения кривой Безье по заданным точкам
В статье рассматривается алгоритм аппроксимации дискретных данных параметрическим сплайном в виде кривой Безье. Выдвигается гипотеза о возможности использования кривых Безье в задачах распознавания образов. В статті розглядається алгоритм апроксимації дискретних даних за допомогою параметричного спл...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2004 |
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2004
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/83933 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Итерационный алгоритм построения кривой Безье по заданным точкам / В.В. Вишневский, И.К. Рысцов, М.В. Волжева // Мат. машини і системи. — 2004. — № 4. — С. 108-116. — Бібліогр.: 5 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-83933 |
|---|---|
| record_format |
dspace |
| spelling |
Вишневский, В.В. Рысцов, И.К. Волжева, М.В. 2015-06-28T14:51:46Z 2015-06-28T14:51:46Z 2004 Итерационный алгоритм построения кривой Безье по заданным точкам / В.В. Вишневский, И.К. Рысцов, М.В. Волжева // Мат. машини і системи. — 2004. — № 4. — С. 108-116. — Бібліогр.: 5 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83933 519.6 В статье рассматривается алгоритм аппроксимации дискретных данных параметрическим сплайном в виде кривой Безье. Выдвигается гипотеза о возможности использования кривых Безье в задачах распознавания образов. В статті розглядається алгоритм апроксимації дискретних даних за допомогою параметричного сплайну у вигляді кривої Без'є. Висувається гіпотеза про можливість використання кривих Без'є в задачах розпізнавання образів. In article it is considered the algorithm of aproximation of discrete date with help of parametric splines in the manner of Bezier-curves. The hypothesis is advanced about possibility of using Beziers spline in problems of pattern recognition. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Итерационный алгоритм построения кривой Безье по заданным точкам Ітераційний алгоритм побудови кривої Без'є за заданими точками Iteration algorithm of building Beziers spline on setings points Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Итерационный алгоритм построения кривой Безье по заданным точкам |
| spellingShingle |
Итерационный алгоритм построения кривой Безье по заданным точкам Вишневский, В.В. Рысцов, И.К. Волжева, М.В. Обчислювальні системи |
| title_short |
Итерационный алгоритм построения кривой Безье по заданным точкам |
| title_full |
Итерационный алгоритм построения кривой Безье по заданным точкам |
| title_fullStr |
Итерационный алгоритм построения кривой Безье по заданным точкам |
| title_full_unstemmed |
Итерационный алгоритм построения кривой Безье по заданным точкам |
| title_sort |
итерационный алгоритм построения кривой безье по заданным точкам |
| author |
Вишневский, В.В. Рысцов, И.К. Волжева, М.В. |
| author_facet |
Вишневский, В.В. Рысцов, И.К. Волжева, М.В. |
| topic |
Обчислювальні системи |
| topic_facet |
Обчислювальні системи |
| publishDate |
2004 |
| language |
Russian |
| container_title |
Математичні машини і системи |
| publisher |
Інститут проблем математичних машин і систем НАН України |
| format |
Article |
| title_alt |
Ітераційний алгоритм побудови кривої Без'є за заданими точками Iteration algorithm of building Beziers spline on setings points |
| description |
В статье рассматривается алгоритм аппроксимации дискретных данных параметрическим сплайном в виде кривой Безье. Выдвигается гипотеза о возможности использования кривых Безье в задачах распознавания образов.
В статті розглядається алгоритм апроксимації дискретних даних за допомогою параметричного сплайну у вигляді кривої Без'є. Висувається гіпотеза про можливість використання кривих Без'є в задачах розпізнавання образів.
In article it is considered the algorithm of aproximation of discrete date with help of parametric splines in the manner of Bezier-curves. The hypothesis is advanced about possibility of using Beziers spline in problems of pattern recognition.
|
| issn |
1028-9763 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/83933 |
| citation_txt |
Итерационный алгоритм построения кривой Безье по заданным точкам / В.В. Вишневский, И.К. Рысцов, М.В. Волжева // Мат. машини і системи. — 2004. — № 4. — С. 108-116. — Бібліогр.: 5 назв. — рос. |
| work_keys_str_mv |
AT višnevskiivv iteracionnyialgoritmpostroeniâkrivoibezʹepozadannymtočkam AT ryscovik iteracionnyialgoritmpostroeniâkrivoibezʹepozadannymtočkam AT volževamv iteracionnyialgoritmpostroeniâkrivoibezʹepozadannymtočkam AT višnevskiivv íteracíiniialgoritmpobudovikrivoíbezêzazadanimitočkami AT ryscovik íteracíiniialgoritmpobudovikrivoíbezêzazadanimitočkami AT volževamv íteracíiniialgoritmpobudovikrivoíbezêzazadanimitočkami AT višnevskiivv iterationalgorithmofbuildingbezierssplineonsetingspoints AT ryscovik iterationalgorithmofbuildingbezierssplineonsetingspoints AT volževamv iterationalgorithmofbuildingbezierssplineonsetingspoints |
| first_indexed |
2025-11-25T22:42:34Z |
| last_indexed |
2025-11-25T22:42:34Z |
| _version_ |
1850569513195536384 |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
108
УДК 519.6
В.В. ВИШНЕВСКИЙ, И.К. РЫСЦОВ, М.В. ВОЛЖЕВА
ИТЕРАЦИОННЫЙ АЛГОРИТМ ПОСТРОЕНИЯ КРИВОЙ БЕЗЬЕ ПО ЗАДАННЫМ
ТОЧКАМ
Abstract: In article it is considered the algorithm of aproximation of discrete date with help of parametric splines in the
manner of Bezier -curves. The hypothesis is advanced about possibility of using Beziers spline in problems of pattern
recognition.
Key words: Bezier splines, aproximation, iteration algorithm, pattern recognition.
Анотація: У статті розглядається алгоритм апроксимації дискретних даних за допомогою
параметричного сплайну у вигляді кривої Без'є. Висувається гіпотеза про можливість використання кривих
Без'є в задачах розпізнавання образів.
Ключові слова: крива Без'є, апроксимація, ітераційний алгоритм, розпізнавання образів.
Аннотация: В статье рассматривается алгоритм аппроксимации дискретных данных параметрическим
сплайном в виде кривой Безье. Выдвигается гипотеза о возможности использования кривых Безье в
задачах распознавания образов.
Ключевые слова: кривая Безье, аппроксимация, итерационный алгоритм, распознавание образов.
1. Введение
Известно, что кривые Безье являются основой многих компьютерных приложений для
компьютерной графики. Так, например, для CAD/CAM/CAE – систем высшего и среднего уровня, а
также для коммерческих, внутренних производственных приложений и приложений для обмена
данными промышленным стандартом становится геометрическое ядро Parasolid компании
Unigraphics Solutions Inc., в основу которого, в свою очередь, положена теория неоднородных
рациональных В-сплайнов (NURBS) и кривых Безье [1].
Интуитивно понятная геометрическая интерпретация кривых Безье позволяет
предположить, что они могут быть эффективно использованы и в задачах распознавания образов.
Одной из таких задач может быть, например, распознавание бинарных растровых изображений.
Для этой задачи использование кривых Безье может обеспечить инвариантность алгоритмов
распознавания при осуществлении афинных преобразований. Однако широкое использование
кривых Безье в задачах распознавания образов сдерживается сложностью вычислительных
алгоритмов аппроксимации экспериментальных данных параметрическими сплайнами, к которым
относятся и кривые Безье.
В данной публикации описывается итерационный алгоритм, обладающий средней
вычислительной сложностью, что позволяет аппроксимировать, например, участки контура
бинарного изображения или других экспериментальных данных, которые могут быть описаны
гладкой кривой с одним или двумя экстремумами.
2. Математическая постановка задачи
Обычно под кривой Безье понимается дуга плоской кривой третьего порядка ( ) ( ) ( )( )tBytBxtBz ,= ,
10 ≤≤ t , заданной в следующем параметрическом виде:
3
0
( ) ( ) ( )j j
j
Bx t Ber t x Q
=
= ⋅∑ ,
3
0
( ) ( ) ( )j j
j
By t Ber t y Q
=
= ⋅∑ , (1)
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
109
где ( )tBerj – базовые скалярные полиномы Бернштейна третьей степени: ( ) ( )( )jjj QyQxQ ,= –
коэффициенты кривой, а параметр t изменяется в единичном интервале [0,1]. Полиномы
Бернштейна определяются следующим образом:
3 3
3
3!
( ) (1 ) (1 )
!(3 )!
j j j j j
jBer t C t t t t
j j
− −= ⋅ − = ⋅ −
−
, 30 ≤≤ j , (2)
где
jC3 , 30 ≤≤ j – биномиальные коэффициенты. Базис Бернштейна является довольно
распространенной формой аппроксимации функций, поскольку он имеет ряд преимуществ перед
классическим базисом { }32 ,,,1 ttt . В частности, он обладает большей вычислительной
устойчивостью [1].
Кривая Безье задается в параметрическом виде, поскольку в общем случае геометрические
контуры не могут быть описаны в виде однозначной функции ( )xfy = . Например, контур может
иметь вертикальные касательные или описываться обратной функцией ( )yfx = и т.д. В этом
состоит одна из трудностей непосредственного применения классических численных методов
полиномиальной аппроксимации [2].
Заметим, что коэффициенты кривой Безье 0Q и 3Q определяют крайние точки, через
которые проходит кривая
( ) ( ) ( )( ) 00,00 QByBxBz == , ( ) ( ) ( )( ) 31,11 QByBxBz == . (3)
Коэффициенты 1Q и 2Q определяют величины касательных в крайних точках («усы» кривой). На
рис. 1 показан пример кривой Безье, из которого становится понятным ее геометрический смысл.
Рис. 1. Пример кривой Безье
Учитывая приведенные выше определения, можно сформулировать задачу следующим образом.
Пусть имеется упорядоченная последовательность различных точек на плоскости
( ) ( )( )iii PyPxP ,= , 10 +≤≤ Ni , содержащая, по крайней мере, четыре точки. Требуется провести
кривую Безье таким образом, чтобы она проходила через две крайние точки 0P , 1+NP и
располагалась как можно ближе к промежуточным точкам iP , Ni ≤≤1 .
В качестве меры отклонения кривой от заданных точек используется квадратичная функция невязки:
Q3
Q0 Q2
Q1
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
110
2 2
1
1
( , ) [( ( ) ( )) ( ( ) ( )) ]
2
N
i i i i
i
f Q U Bx t x P By t y P
=
= − + −∑ . (4)
Здесь суммируются квадраты евклидовых расстояний между точками ( )iBz t ( ) ( )( )ii tBytBx ,= и
( ) ( )( )iii PyPxP ,= . Вектор коэффициентов кривой { }3210 ,,, QQQQQ = и параметрический вектор
1( , ... )NU t t= , где все it принадлежат единичному интервалу [0, 1], являются аргументами этой
функции. Каждую точку ( )iBz t можно рассматривать как «представителя» на кривой Безье,
соответствующего исходной точке iP . Поэтому функцию невязки нужно минимизировать по Q и
по U .
Поскольку функция невязки нелинейно зависит от параметрического вектора, то в целом
эту задачу можно рассматривать как нелинейную проблему наименьших квадратов и решать ее
известными численными методами [3, гл. 10]. Но реализация этих методов может потребовать в
данном случае слишком большого объема вычислений, поскольку при этом придется вычислять
многомерные якобианы и гессианы. Поэтому, учитывая возможную размерность задачи (от
нескольких десятков до сотен точек), авторами был разработан другой метод решения.
Далее будет показано, что компоненты базовых функций
( ) ( ) ( )i i ix F Bx t x P= − , ( ) ( ) ( )i i iy F By t y P= − , Ni ≤≤1 (5)
линейно зависят от коэффициентов кривой Безье, и, очевидно, что каждая из них зависит только от
одной переменной it вектора U . Из (4) видно, что функция невязки, по существу, является суммой
квадратов этих компонент. Поэтому данную задачу целесообразно разбить на несколько подзадач.
Сначала можно решить линейную задачу наименьших квадратов и провести минимизацию
целевой функции по первому аргументу Q при фиксированном значении второго аргумента U , а
затем, наоборот, зафиксировать Q и провести минимизацию по каждой компоненте вектора U .
Наконец, на заключительном этапе, комбинируя эти методы, можно получить итерационный
алгоритм минимизации целевой функции. В соответствии с этим планом и построим наше
дальнейшее изложение.
3. Линейная задача наименьших квадратов
Итак, зафиксируем параметрический вектор 1( , ... )NU t t= и будем искать кривую Безье, которая
минимизирует значение невязки (4) при заданных значениях промежуточных параметров.
Согласно свойству (3), коэффициенты 0Q , и 3Q должны совпадать с крайними точками,
через которые проходит кривая Безье, но по условию задачи этими крайними точками должны быть
точки 0P и 1+NP . Поэтому для граничных значений параметра 00 =t и 11 =+Nt получаем
следующие краевые условия:
0 0(0)Bz Q P= = , 3 1(1) NBz Q P += = . (6)
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
111
Остается найти коэффициенты 1Q и 2Q кривой Безье. Для этого удобно перейти к
матричной записи основных соотношений между параметрами задачи. Обозначим через ( )UBer
матрицу размера 4×N , состоящую из значений полиномов Бернштейна [ ( )]j iBer t ,
1 , 0 3i N j≤ ≤ ≤ ≤ , вычисленных на параметрическом векторе U . Эту матрицу назовем
бернштейнианом (матрицей Бернштейна) и она для полиномов Бернштейна играет ту же роль, что
и матрица Вандермонда для обычного полиномиального базиса [1]. Столбцы матрицы Бернштейна
будем обозначать через ( )jBer U , 30 ≤≤ j .
Далее пусть 1( ) ( ( ), , ( ))Nx P x P x P= K – вектор абсцисс точек iP , 1 i N≤ ≤ , а
1( ) ( ( ), , ( ))Ny P y P y P= K – вектор ординат этих точек. Аналогично пусть
0 1 2 3( ) ( ( ), ( ), ( ), ( ))x Q x Q x Q x Q x Q= – вектор абсцисс коэффициентов кривой Безье и
соответственно ( )y Q – вектор ординат этих коэффициентов. Наконец, обозначим через ( )Fx
вектор абсцисс базовых функций 1( ( ), , ( ))Nx F x FK , определенных по формуле (5), и
аналогично через ( )Fy обозначим вектор ординат этих функций. Тогда из (1) и (5) получаем
следующие матричные равенства:
( ) ( ) ( ) ( )x F Ber U x Q x P= ⋅ − , ( ) ( ) ( ) ( )y F Ber U y Q y P= ⋅ − . (7)
Функцию невязки (4) можно также представить в векторной форме:
2 21 1
( , ) ( ) ( )
2 2
f Q U x F y F= + , (8)
где норма вектора берется в N–мерном евклидовом пространстве [4].
Из формулы (7) видно, что вектор абсцисс базовых функций ( )Fx линейно зависит от
вектора абсцисс ( )Qx и аналогично вектор ординат базовых функций ( )Fy линейно зависит от
вектора ( )Qy . Таким образом, получаем классическую линейную задачу о наименьших квадратах
[3]. Хорошо известен метод Гаусса для решения этой задачи, а именно, векторы ( )Qx и ( )Qy , на
которых достигается минимум невязки (8), должны удовлетворять следующей системе линейных
уравнений [3, § 3.6]:
( ) ( ) ( ) ( )TA U x Q Ber U x P⋅ = ⋅ , ( ) ( ) ( ) ( )TA U y Q Ber U y P⋅ = ⋅ , (9)
где ( ) ( ) ( )TA U Ber U Ber U= , а ( )TBer U - транспонированный бернштейниан. Чтобы убедиться
в этом, достаточно продифференцировать невязку (8) по переменным ( )Qx и ( )Qy и приравнять
все частные производные нулю, т.е. записать необходимое условие экстремума. Матрица
( ) [ ]jkA U a= будет составлена из скалярных произведений столбцов матрицы Бернштейна:
6
3 3
1
( ), ( ) (1 )
N
j k j k j k
jk j k i i
i
a Ber U Ber U C C t t+ − −
=
= = ⋅ ⋅ ⋅ −∑ , 0 , 3j k≤ ≤ . (10)
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
112
В нашем случае система (9) будет содержать по четыре уравнения с четырьмя
неизвестными. Если матрица A(U) будет обратимой, то система (9) будет иметь единственное
решение, которое дается следующими формулами:
1( ) ( ) ( ) ( )Tx Q A U Ber U x P−= ,
1( ) ( ) ( ) ( )Ty Q A U Ber U y P−= . (11)
На этом, в принципе, решение линейной задачи можно считать законченным, но возникает
вопрос об условиях, когда матрица ( )UA будет обратимой. На этот вопрос ответ будет дан чуть
позднее, а сейчас обратим внимание на еще одну особенность, которая отличает наше решение от
общего решения (11). Из краевых условий (6) имеем выражения для крайних коэффициентов
0 0Q P= и 3 1NQ P += , и, следовательно, в системе (9) в нашем случае будет всего по два
неизвестных вместо четырех. Чтобы найти компактные выражения для этих неизвестных,
воспользуемся аппаратом векторной алгебры. При желании в дальнейшем читатель может
рассматривать неизвестные 1Q , 2Q и точки iP как комплексные числа. Подставим краевые
условия (6) в уравнение (9). Тогда, раскрывая скобки и собирая все члены при 1Q и 2Q , получим
следующую систему уравнений относительно этих неизвестных:
11 1 12 2 1a Q a Q R⋅ + ⋅ = , 21 1 22 2 2a Q a Q R⋅ + ⋅ = , (12)
где свободные члены jR вычисляются по следующим формулам:
0 0 3 1
1
( )
N
j j i i j j N
i
R Ber t P a P a P +
=
= ⋅ − ⋅ − ⋅∑ , 21 ≤≤ j . (13)
Здесь и в (12) коэффициенты jka являются элементами матрицы ( )UA и определяются по
формуле (10).
Обозначим определитель системы (12) через ∆ и предположим, что он не равен нулю.
Тогда по формулам Крамера получаем решение системы (12) в следующем виде:
1 22 1 12 2( ) /Q a R a R= ⋅ − ⋅ ∆ , 2 11 2 12 1( ) /Q a R a R= ⋅ − ⋅ ∆ . (14)
Из формулы (10) заключаем, что определитель 11 22 12 21a a a a∆ = − системы (12)
определяется по следующей формуле:
2 2 2
1 2 1 2( ) ( ) ( ), ( )Ber U Ber U Ber U Ber U∆ = ⋅ − . (15)
Здесь норма и скалярное произведение по-прежнему определяются в N –мерном евклидовом
пространстве. Тогда из известного неравенства Коши - Буняковского [5, § 1.3-2] заключаем, что
определитель ∆ должен быть неотрицательным. Он будет положительным тогда и только тогда,
когда столбцы ( )UBer1 и ( )UBer2 являются линейно-независимыми. Этот вывод является
частным случаем известной теоремы [3], которая утверждает, что матрица ( )UA будет обратимой,
если столбцы матрицы ( )UBer являются линейно-независимыми.
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
113
Поскольку 1 2( ) / ( )i iBer t Ber t =1/ 1it − , то для положительности определителя ∆
необходимо и достаточно, чтобы внутри открытого интервала [0,1] находились по крайней мере два
различных значения 1t и 2t из параметрического вектора U . Вместе с граничными значениями 0
и 1 это дает четыре различных значения параметра. На практике, как правило, выполняется более
сильное условие, поскольку вектор U предполагается упорядоченным:
0 1 10 1N Nt t t t += < < < < =L . (16)
Поскольку по условию задачи 2≥N , то на любом упорядоченном параметрическом векторе
определитель ∆ будет положительным.
4. Минимизация по параметрам
Рассмотрим теперь проблему минимизации невязки (4) для фиксированной кривой Безье, т.е. при
фиксированном векторе Q . Тогда невязка будет зависеть только от параметрического вектора
),...( 1 NuuU = и, следовательно, в этом случае имеем нелинейную задачу наименьших
квадратов.
Если параметры it , Ni ≤≤1 , рассматривать как независимые действительные
переменные, то существование глобального минимума по всем переменным it следует из
известной теоремы анализа о том, что непрерывная функция ( )Uf достигает своего минимума на
компакте (многомерном кубе) [0,1]N
. Свойство (16) упорядоченности вектора U противоречит
предположению о независимости его компонент. Но нетрудно видеть, что упорядоченные
параметрические векторы образуют открытое всюду плотное подмножество куба [0,1]N , поэтому к
указанному минимуму можно приблизиться с любой точностью, двигаясь только по упорядоченным
параметрическим векторам.
Сначала запишем необходимое условие экстремума. Для этого продифференцируем
невязку (4) по всем переменным it и в результате получим следующую систему нелинейных
уравнений:
( ) ( ( ) ( )) ( ) ( ( ) ( )) 0i i i i i i
i
f
Bx t Bx t x P By t By t y P
t
∂ ′ ′= ⋅ − + ⋅ − =
∂
, Ni ≤≤1 . (17)
Для вычисления производных ( )iBx t′ и ( )iBy t′ можно воспользоваться формулой (1) и взять
обычную производную от функций ( )Bx t и ( )By t по переменной t , а затем подставить вместо
нее параметр it . Производные от полиномов Бернштейна ( )j iBer t′ также легко вычисляются по
формуле (2) и выражаются через полиномы Бернштейна второй степени [1]. Из системы (17),
раскрывая скобки, получаем следующую систему из N нелинейных уравнений с N неизвестными it :
( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )i i i i i i i iBx t Bx t By t By t Bx t x P By t y P′ ′ ′ ′⋅ + ⋅ = ⋅ + ⋅ , Ni ≤≤1 . (18)
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
114
Уравнения этой системы зависят от различных переменных it , Ni ≤≤1 , поэтому вместо
решения многомерной нелинейной системы здесь нужно N раз решать уравнения от одной
переменной. Из формул (1) и (2) видно, что левая часть каждого из уравнений (18) представляет
собой, по существу, один и тот же многочлен пятой степени ( )M t относительно переменной t , в
который вместо этой переменной каждый раз подставляется своя переменная it . Правая часть
каждого уравнения системы (18) является многочленом второй степени ( )i iM t относительно той
же переменной it . Таким образом, задача сводится к поиску вещественных корней у многочленов
пятой степени, и, значит, каждое уравнение ( )iM t = ( )i iM t этой системы может иметь не более 5
и не менее одного вещественных корней, из которых можно выбрать один корень, который
минимизирует невязку (4).
Но локализация и нахождение корней многочлена пятой степени является не простой
вычислительной задачей. Кроме того, экстремальная точка может оказаться локальным
максимумом или точкой перегиба функции невязки. К тому же, точное решение промежуточной
задачи может существенно увеличить общее время минимизации невязки по всем переменным.
Поэтому вместо точного решения системы (18) был использован приближенный локальный
алгоритм минимизации невязки градиентного типа.
Этот алгоритм основан на геометрических соображениях и состоит в изменении значения
переменной it таким образом, чтобы уменьшалась невязка (4). С геометрической точки зрения
соотношения (17) означают перпендикулярность касательного вектора ( ) ( ( ), ( ))Bz t Bx t By t′ ′ ′= в
точке itt = вектору ( ) ( ( ) ( ), ( ) ( ))i i i i i iBz t P Bx t x P By t y P− = − − . При этом, если косинус угла
между этими плоскими векторами больше нуля, то параметр it надо уменьшать, чтобы увеличить
угол между векторами ( )iBz t′ и ( )i iBz t P− . Если же cos( ) 0iα < , то параметр it надо
увеличивать, чтобы уменьшить угол между этими векторами. Другими словами, смещение должно
происходить как бы в сторону перпендикуляра, опущенного из точки Pi на кривую Безье. На рис. 2
иллюстрируются возникающие здесь ситуации. Конечно, вариацию параметра it надо проводить
только в том случае, если невязка уменьшается, поскольку подозрительная точка может оказаться
локальным максимумом. Смещение можно осуществлять методом половинного деления между
соседними значениями параметра либо другими подобными методами. Метод половинного
деления отрезка имеет преимущество перед смещением по равномерным узлам сетки, поскольку
он позволяет сохранить упорядоченность параметрического вектора. Смещения заканчиваются,
когда невязка существенно не изменяется.
Этот простой локальный алгоритм оказался достаточно быстрым. Хотя он и не гарантирует
достижения глобального минимума, о котором шла речь в начале этого раздела, но позволяет
быстро найти приемлемое решение.
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
115
Рис. 2. Исходные точки и кривая Безье
5. Моделирование алгоритма в пакете Maple
Для численного решения линейной задачи наименьших квадратов была разработана процедура
LLSquare(U), которая по заданному параметрическому векторуU вычисляет вектор коэффициентов
кривой Безье Q . Аналогично, для реализации алгоритма минимизации по параметрам была
разработана процедура Midpoints(Q,U), которая по заданной кривой Безье Q и параметрическому
вектору U смещает вектор U по всем параметрам it , Ni ≤≤1 с целью уменьшения невязки (4).
Общий алгоритм минимизации начинает работу с равномерного параметрического вектора
( )1/ += Niti , ,1 Ni ≤≤ и состоит в поочередном вызове процедур LLSquare(U) и Midpoints(Q,U)
до тех пор, пока изменение невязки станет меньше заданного числа 0>ε .
На рис. 3 приведены примеры работы алгоритма, характерные для задачи аппроксимации
участка контура бинарного изображения, для первых 3-х итераций. Крестиками обозначены
исходные значения данных, через которые должна пройти искомая кривая Безье.
α1
Р1
Bz(t1)
Р2
Р0 PN+1
Bz(t2)
α2
Рис. 3. Пример моделирования итерационного алгоритма
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
116
После проведения моделирования алгоритма была разработана динамическая библиотека
(dll), которая, в свою очередь, была успешно использована в эксперименте распознавания
бинарных изображений нейрокомпьютером. Эксперимент подтвердил гипотезу о возможности
построения алгоритмов распознавания, инвариантных к афинным преобразованиям. Описание
этого эксперимента и связанной с ним информационной технологии обработки бинарных
изображений является темой отдельной статьи.
6. Выводы
Задача аппроксимации участков контура кривыми Безье может быть эффективно решена на
практике путем разбиения на две подзадачи: линейную процедуру аппроксимации по методу
наименьших квадратов и нелинейную итерационную процедуру подбора параметров.
Итерационная процедура подбора параметров кривой Безье не обеспечивает нахождения
глобального экстремума для любого типа кривой Безье. Однако для практических задач
аппроксимации контуров бинарных изображений такая процедура позволяет минимизировать
невязку (4) с любой вычислительной точностью.
Учитывая интуитивно понятный геометрический смысл кривой Безье, приемлемую
вычислительную сложность алгоритма ее построения и проведенные модельные эксперименты,
можно выдвинуть гипотезу о возможности использования кривых Безье в задачах распознавания
образов.
СПИСОК ЛИТЕРАТУРЫ
1. Денискин Ю.И. Особенности аппроксимации обводов параметрическими полиномами в форме Бернштейна
// Прикладная геометрия. – 1999. – Вып. 2, № 2.
2. Хемминг Р.В. Численные методы. – М., Наука, 1972. – 400 с.
3. Денис Дж., Шнабель Р. Численные методы безусловной оптимизации и решение нелинейных уравнений. –
М., Мир, 1988. – 440 с.
4. Халмош П. Конечномерные векторные пространства. – М.: ФМ, 1963. − 263 с.
5. Корн Г., Корн Т. Справочник по математике. – М., Наука, 1970.– 720 с.
|