Software & Systems

Фокусное приближение кривых является методом гладкой аппроксимации, основанным на представлении поточечно заданной замкнутой эмпирической кривой системой конечного набора точек внутри кривой, называемых фокусами (рис. 1а). Классом аппроксимирующих функций служит семейство многофокусных лемнискат, представляющих собой гладкие замкнутые кривые на плоскости, параметрами которых являются количество и расположение фокусов, а также радиус. Каждая лемниската определяется через систему конечного числа m точек-фокусов {f1,…,fm} внутри и числовой параметр R, называемый радиусом лемнискаты, как геометрическое место точек, произведение расстояний от которых до фокусов постоянно и равно Rm (рис. 1б). Инвариант и уравнение многофокусной лемнискаты имеют вид

=Rm,                                                              (1)

где rj – евклидово расстояние от произвольной точки лемнискаты до j-го фокуса (j=1, ..., m). Для заданной системы фокусов инвариант (1) представляет собой линию уровня аппликаты двухмерного полинома для значения Rm.

Семейство лемнискат обладает рядом таких свойств, которые позволяют использовать их в качестве инструмента приближения формы кривой. Число фокусов, их координаты и радиус, являющиеся параметрами лемнискаты, представляют собой степени свободы фокусного метода аппроксимации, обеспечивающие необходимое приближение. Пример семейства изофокусных лемнискат с тремя фокусами, параметризованного по радиусу, приведен на рисунке 1в. Для фиксированного набора фокусов лемнискаты с разными радиусами образуют семейство вложенных кривых: кривые с большим радиусом охватывают кривые с меньшим радиусом, нигде с ними не пересекаясь [1–3].

Впервые вопрос об аппроксимационных возможностях многофокусных лемнискат исследовал Д. Гильберт [1]. Им доказано, что при определенных условиях на аппроксимируемую кривую С для любого e всегда найдутся такие система фокусов и радиус, что отвечающая им лемниската L пройдет в e-окрестности каждой точки кривой С. Однако вопрос об определении радиуса, количества фокусов и их координат для конкретной эмпирической кривой С, заданной координатами n своих точек, остался открытым.

Теоретические аспекты фокусного метода аппроксимации, такие как постановка задачи, литературные источники, свойства класса приближающих лемнискат, характеристики фокусного приближения и сравнение его с точки зрения аппроксимационных возможностей с клаcсическими методами гладкого приближения, а также возможности использования более широкого класса аппроксимирующих функций – квазилемнискат, описаны в работах [1–6].

Ввиду неявной формы (1) и высокой степени нелинейности решение не только обратной, но и прямой задачи не удается найти аналитически. Автором разработан метод алгоритмического решения прямой задачи построения лемнискаты по заданным фокусам и радиусу, основанный на процедуре прослеживания, использующей свойства лемнискат [3, 4].

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

В то время как прямая задача принципиальной сложности не составляет, обратная задача, практически более востребованная, вызывает значительные трудности. Настоящая работа посвящена рассмотрению алгоритмов автоматического поиска параметров фокусного приближения на вещественной (комплексной [5]) плоскости.

Пусть задано координатное описание гладкого контура (кривой) C набором n своих необязательно равноотстоящих точек {xi, yi}, i=1, ..., n.

Требуется найти такую систему m фокусов {fj} с координатами {aj, bj}, что при определенном значении радиуса R соответствующая им лемниската L будет близка с необходимой точностью к кривой C в смысле выбранного критерия Crt(C,L).

Иными словами, задача приближения состоит в том, чтобы для гладкой замкнутой кривой С, заданной n точками {сi}, построить ее непрерывную аппроксимацию лемнискатой L, удовлетворяющую некоторому заданному критерию сходства Crt(C,L). Поскольку лемниската L однозначно определяется координатами своих фокусов {aj, bj} и радиусом R, задача приближения сводится к отысканию числа фокусов m, их координат {aj, bj} и радиуса R, таких, что

Crt(n,{xi,yi},m,{aj,bj},R)

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

Критерии точности приближения

Принципиальным вопросом в решении аппроксимационной задачи является критерий близости двух кривых Crt(C,L). Особенностью фокусного метода приближения является возможность использования двух типов критерия.

Один, L-критерий, основан на расстоянии между точками кривых на плоскости и может быть, например, минимаксным:  где r(c,l) – евклидово расстояние от точки c кривой С до точки l лемнискаты L, минимум ищется по точкам лемнискаты, а максимум – по точкам кривой. L-критерий универсален, он не привязан к системе аппроксимирующих функций.

Другой, R-критерий, напротив, специальный, вытекающий из инвариантного свойства лемнискаты сохранять во всех своих точках постоянным значение радиуса. R-критерий устанавливает соответствие между степенью близости кривых C и L и мерой отклонения значения радиуса вдоль кривой С от константы: , где r(ci,fj) – расстояние в i-й точке кривой С до j-го фокуса.

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

Во втором типе (R-критерии) представление о близости кривых присутствует в неявном виде, он менее нагляден, но проще в вычислениях, и поэтому применение R-критериев удобнее как в аналитическом плане, так и в алгоритмическом.

Показано, что L- и R-критерии топологически эквивалентны: при стремлении к нулю расстояния между аппроксимируемой кривой и аппроксимирующей лемнискатой в смысле L-критерия стремятся к нулю и колебания радиуса на кривой, и наоборот [3, 4]. В представленных в данной работе алгоритмах работают оба критерия.

Использование известных методов

Поиск непосредственно параметров аппроксимирующей лемнискаты – координат фокусов {aj, bj} и значения радиуса R – при использовании среднеквадратичного критерия сводится к решению оптимизационной задачи

                     (3)

Система (3) является нелинейной по определяемым 2m+1 параметрам. Степень нелинейности зависит от числа фокусов, так как координаты фокусов входят в уравнения в виде произведений с высшей степенью m или 2m. Это обстоятельство представляет значительные трудности как в теории, так и на практике. Минимизация функционала приводит к следующей системе уравнений:

,

,

 l=1,…,m.

Из этой системы видно, что за радиус приближающей лемнискаты принимается среднее значение радиусов по всем точкам кривой, а координаты каждого из фокусов должны удовлетворять условию равенства нулю суммы единичных векторов, направленных из фокуса на все точки кривой и взвешенных невязкой в каждой точке кривой, и радиусом по системе остальных фокусов. Анализировать подобную систему сложно, поэтому такие традиционные вопросы аппроксимации, как единственность представления и оценка остаточного члена, трудно исследовать теоретически. По той же причине и решение системы в явном виде найти не удается. Для численного решения такой системы был применен метод Ньютона в модификации Канторовича [7]. Матрица итерационной системы уравнений получалась довольно громоздкой из-за двойного дифференцирования, а результат неудовлетворительным ввиду его крайней неустойчивости [3]. Есть основания полагать, что и другие универсальные методы не смогут обеспечить решение задачи.

Общая структура алгоритма

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

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

Начальные условия работы алгоритма определяются выбором исходного положения фокусов {f} и вычисленным значением радиуса R. Так как все m фокусов лемнискаты расположены внутри кривой, то в начальный момент все предполагаемые фокусы могут быть сосредоточены, например, в геометрическом центре кривой C.

Каждая итерация алгоритма содержит следующие основные компоненты:

·     выбор одного из фокусов, который должен перемещаться;

·     определение направления движения для каждого из выбранных фокусов;

·     определение пути, проходимого фокусами, и их новое расположение;

·     вычисление радиуса лемнискаты по новой системе фокусов;

·     проверка критерия качества приближения.

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

Процесс размножения фокусов добавляет в алгоритм еще две компоненты:

·     определение момента добавления нового фокуса;

·     определение начального положения нового фокуса.

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

Два варианта локального цикла алгоритма

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

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

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

Рассмотрим в формализованном виде алгоритм фокусного приближения и его варианты. Пусть некоторым образом определен критерий сходства Crt(C, mf, R), где mf – полная система m фокусов {f1, …, fm}; Di – значение невязки критерия в i-й точке кривой. Произведение расстояний от i-й точки кривой до всех фокусов обозначим ri и назовем радиусом в i-й точке. Предположим также, что число фокусов m известно, и пусть в начальный момент все они сосредоточены в геометрическом центре кривой zc:

, .

С-вариант алгоритма

На каждой его итерации t выполняются следующие действия.

1. Вычисляется радиус лемнискаты по точкам кривой C и расположению фокусов, полученному на предыдущей итерации: Rt=R(C, mf). Конкретная функция для вычисления радиуса зависит от выбранного критерия Crt.

2. Выбирается направление движения фокусов. Этот выбор также зависит от критерия Grt и определяется худшей точкой ztiÎC, в которой невязка Di максимальна.

Направление уточняется линейной интерполяцией по невязкам: : zti®zt.

3. Выбираются фокусы, которые должны двигаться в заданном направлении zt. Для этого все m фокусов ранжируются по мере увеличения расстояния dj(zt) от j-го фокуса до точки zt, первым движущимся фокусом является ближайший к ней.

4. Выполняется поочередное перемещение фокусов в направлении zt: , где s – параметр шага перемещения фокуса; wtj – весовой коэффициент j-го фокуса; vtj – вектор направления от j-ro фокуса на точку zt. Весовой коэффициент регулирует перемещение разных фокусов за один шаг, уменьшая его с увеличением расстояния фокуса от точки zt, так что последние фокусы практически не двигаются. Введение весовой функции задает своего рода упругость растягивающейся пленки, имея в виду приведенную выше аналогию. Весовая функция может, например, иметь вид

, j=1, …, m.

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

Операция движения фокусов заканчивается, когда все m фокусов переместились в направлении zt, задавая их новое расположение: mft+1.

6. Определяется новый радиус лемнискаты:

7. Сравнивается критерий сходства Crt с пороговым значением e: алгоритм заканчивает работу, если , иначе выполняется следующая итерация.

Таково содержание основного цикла C-вари­анта, в котором очередность движения фокусов зависит от локализации наихудшего приближения на кривой C.

F-вариант алгоритма

В отличие от C-варианта первичным в F-ва­рианте является априорная очередность фокусов, а направление движения каждого фокуса определяется градиентом критерия качества в точке расположения фокуса.

На каждой итерации устанавливается одна и та же очередность движения фокусов – в порядке их номеров. Для каждого фокуса независимо делаются пробные шаги равной величины s в разных k направлениях с вычислением критерия, значения которых сравниваются между собой и со значением критерия для исходного расположения фокуса. Реальный шаг делается фокусом в направлении минимального значения Crt. Фокус может остаться на месте, если значения критерия вокруг исходной точки оказались больше, то есть если для данного фокуса ftj на данном такте оказался локальный минимум критерия. Поле направлений пробных движений задается параметрически, углом сканирования направлений или их количеством k:

После того как все фокусы поочередно реализовали свои возможности сделать шаг каждый в своем направлении, фиксируется новое расположение фокусов mft+1. Здесь, как и в С-варианте, возможно не только одношаговое движение, но и многошаговое, выполняемое до тех пор, пока значение критерия уменьшается.

Как и в С-варианте, последними операциями являются вычисление нового радиуса Rt+1=R(C, mft+1) и проверка критерия Ctr(C, ft+1, Rt+1)≤e.

Цикл повторяется, если качество приближения не достигло e-порога.

Системный цикл

Кроме пофокусного цикла в алгоритме присутствует еще глобальный цикл, в котором система фокусов перемещается как целое в одном направлении. Необходимость в таком цикле обусловлена желанием скорректировать пофокусное движение основного цикла. Схема алгоритма остается той же. Глобальный цикл также заканчивается сравнением критерия с пороговым значени- ем e. Два цикла алгоритма – основной пошаговый и системный – выполняются поочередно, составляя одну итерационную ступень алгоритма. Такова в целом структура алгоритма фокусной аппроксимации. Его компьютерная реализация требует конкретизации ряда обозначенных выше аспектов.

Конкретизация параметров алгоритма

Входом алгоритма, кроме координат {xi, уi} n точек аппроксимируемой кривой С и порога e на качество приближения, являются его параметры: числовые, функциональные, а также индексные, означающие тот или иной вариант алгоритма. Основные параметры числового задания – это величина шага движения фокусов s и порог на ветвление g, которые подбираются эмпирически с учетом скорости работы алгоритма и его надежности. Функциональными параметрами являются критерии качества приближения, а также формулы для вычисления радиуса и направления движения фокусов.

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

а) ,

, ;

б) ,

, ;

в) ,

, .

Локальное расстояние Li между двумя кривыми в i-й точке определяется несимметрично, только в одну сторону – от точек кривой C к лемнискате L. Это связано с тем, что число отсчетов исходной кривой не может быть сколь угодно большим, а лемниската, напротив, может быть представлена с любой разумной точностью, достаточной, чтобы по сравнению с исходной кривой ее можно было считать практически непрерывной линией. При этом расстояние Li от произвольной точки кривой до лемнискаты определяется довольно точно. Систематическую ошибку сверху можно оценить как Dls/4, где Dls – шаг вычисления лемнискаты, для уменьшения которой используется линейная интерполяция в одном из соседних интервалов.

Работу алгоритма иллюстрирует рисунок 2, где слева приведены фазы приближения фигуры трехфокусной лемнискаты C-алгоритмом в минимаксной (а), а справа – F-алгоритмом в усредненной конфигурации (б).

Точками на этих и последующих рисунках отмечены координаты {xi, yj} исходной кривой C, звездочками – фокусы, сплошной линией – лем­ниската L. Адекватность поведения алгоритма можно оценить визуально. На рисунках представлены графики зависимости ошибки приближения от номера итерации. Как видно, эта ошибка монотонно уменьшается. В сравнительном тестировании на точность определения параметров оба варианта алгоритма оказались достаточно эффективными. В работе алгоритма с тестовыми кривыми, параметры которых известны, C- и F-вари­анты давали схожие координаты фокусов, практически не отличимые от действительных.

  Выход из локальных экстремумов

В процессе движения фокусов может сложиться ситуация, отвечающая локальному минимуму критерия, то есть когда ни один фокус не может никуда двинуться, а качество приближения еще не достигло e-порога. На этот случай предусмотрены процедуры, связанные с корректировкой величины шага движения фокусов или с изменением случайным образом их расположения (встряхиванием): fj=fj+x.

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

Размножение фокусов

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

Алгоритм может начинать свою работу с любого числа фокусов, например с m=1. В процессе работы с явно недостаточным числом фокусов алгоритм за некоторое число шагов осуществляет оптимальную их расстановку с точки зрения критерия качества приближения, значение которого достигает минимального уровня (>e), после чего дальнейшая работа алгоритма не может изменить этот уровень, алгоритм будет работать вхолостую. Такая ситуация должна послужить сигналом к увеличению числа фокусов. Для оценки ситуации требуется анализ эффективности работы алгоритма за q последних итераций. Фокус добавляется, если различие текущего значения критерия со средним по предыдущим q итерациям меньше порогового значения g.

Новый фокус прежде всего помещается в исходную позицию ftm+1=zc.

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

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

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

На рисунке 4 приведены результаты эксперимента с размножением фокусов от 3 до 6 для эмпирической кривой в режиме ветвления фокусов: новые фокусы здесь добавлялись в место расположения ветвящегося фокуса (на графике сходимости моменты появления новых фокусов сопровождаются всплесками большей амплитуды, всплески соответствуют появлению 4, 5 и 6-го фокусов).

Судя по рисункам 3 и 4, приближения с использованием обоих режимов размножения дают хорошие результаты. Отметим, что эти эксперименты по размножению фокусов были выполнены комбинированным алгоритмом, автоматически переходящим от C- к F-варианту в зависимости от фазы приближения.

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

Литература

1.   Hilbert D. Gessamelte Abhandlungen, Berlin: Springer, 1935. Bd. 3. 435 p.

2.   Маркушевич А.И. Теория аналитических функций. М.: Наука, 1967. Т. 1. 486 с.

3.   Ракчеева Т.А. Приближение кривых многофокусными лемнискатами // Человеко-машинные системы и анализ данных. М.: Наука, 1992. С. 93–110.

4.   Ракчеева Т.А. Приближение кривых: фокусы или гармоники // Математика, компьютер, образование: сб. науч. тр.; [под ред. Г.Ю. Ризниченко].  М.–Ижевск: НИЦ «Регулярная и хаотическая динамика». 2007. Т. 2. С. 83–90.

5.   Ракчеева Т.А. Приближение кривых многофокусными лемнискатами на комплексной плоскости // Математика, компьютер, образование: там же. 2008. Т. 2. С. 68‑75.

6.   Ракчеева Т.А. Алгоритм фокусного приближения кривых // Человеко-машинные системы и анализ данных. М.: Наука, 1992. С. 111–129.

7.   Канторович Л.В., Акилов Г.Р. Функциональный анализ. М.: Наука, 1984. 752 с.