Method of modeling a curve of the first order smoothness

Damdinova Tatiana Tsybikovna PhD in Technical Science Associate Professor, East-Siberian State University of Technology and Management 670000, Russia, respublika Buryatiya, g. Ulan-Ude, ul. Klyuchevskaya, 40 V dtatyanac@mail.ru Other publications by this author     Bubeev Innokentii Trofimovich PhD in Technical Science Associate Professor, Department of Engineering and Computer Graphics, East-Siberian State University of Technology and Management 670013, Russia, respublika Buryatiya, g. Ulan-Ude, ul. Klyuchevskaya,, 40v it_bubeev@mail.ru

Motoshkin Petr Vladimirovich PhD in Technical Science Associate Professor, Department of Engineering and Computer Graphics, East-Siberian State University of Technology and Management 670013, Russia, respublika Buryatiya, g. Ulan-Ude, ul. Klyuchevskaya,, 40v mpv_mpv@mail.ru

Введение

Повышение технических характеристик видеокамер и 3D сканеров и их повсеместное использование в различных областях обуславливает дальнейшее развитие методов и способов обработки изображений. Информация из видеопотока или информация в виде облака точек в дальнейшем используется в задачах распознавания, для получения характеристик отдельных деталей на объектах. Одной из областей применения этих данных является обратное проектирование, целью которого является определение формы, размеров, и других характеристик объектов реального мира на основе информации, представленной в виде облака точек. Координаты точек представляются в stl-формате из которого можно получить данные по сечениям и анализировать форму объекта на плоскости. При этом одной из важнейших задач является получение геометрической модели плоского контура, соответствующего заданной степени гладкости и точности ^{[1, 2]}.

Задаче моделирования обводов – кривой, состоящей из нескольких частей, посвящено множество научных исследований ^{[2, 3,4]}, начиная с момента развития автоматизации проектно-конструкторских работ в отраслях тяжелой и легкой промышленности. Новый импульс эта задача получила с развитием компьютерной графики, систем обработки изображений, 3D сканированию, обратному проектированию. Анализ работ последних лет показывает, что данная задача по-прежнему актуальна. ^{[5, 6, 7]}. Особая роль отводится моделированию гладких обводов, имеющих совпадение на границах участков по касательной или кривизне.

Постановка задачи

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

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

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

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

· начальная точка - точка нулевого порядка гладкости, конечная - точка первого порядка гладкости;

· начальная точка - точка первого порядка гладкости, конечная точка - точка нулевого порядка гладкости;

· обе точки - точки первого порядка гладкости.

Рассмотрим алгоритм построения обвода.

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

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

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

1. кривая должна проходить через первую и последнюю точки аппроксимируемого множества;

2. кривая должна проходить через первую точку;

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

4. кривая должна проходить через первую точку, выдерживая в ней заданное направление касательной;

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

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

Моделирование обвода 1 степени гладкости

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

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

аппроксимирующего полинома третьей степени для случая, когда массив точек находится между двумя точками нулевого порядка гладкости (варианты 1, 2, 3).

Обвод будет состоять из дуг полиномов третьей степени, имеющих вид

(1)

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

(2)

Тогда минимизируемый функционал можно записать в виде

Выполнив необходимые преобразования, получим коэффициенты a2, a3:

где

, .

После определения a2 и a3 можно по формуле (2) вычислить коэффициент a1, затем по (1), получим искомое уравнение аппроксимирующего полинома, который описывает все точки кромки, если они находятся на расстоянии не большем заданного δ.

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

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

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

Коэффициенты получаются из решения системы уравнений

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

Для уравнения (1) получим уравнение первой производной

Вычислив по выражению (3) и подставив вычисленные коэффициенты, получим уравнение аппроксимирующего полинома для варианта 3.

Результаты работы

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

Обвод, построенный в соответствии с предлагаемой методикой, с использованием расчетов по приведенным формулам представлен на рис.1.

Рис.1. Обвод первой степени гладкости

Пунктирной линией показана дуга, полученная при попытке построения обвода на всем множестве точек в системе хОу (вариант 1). Но так как она не выдерживает заданную погрешность, количество точек сокращается и аппроксимация выполняется в локальной системе x’O’y’ с учетом принципа построения лекальных кривых (вариант 2). Оставшиеся точки аппроксимируются с учетом касательной к предыдущей дуге обвода (вариант 3).