Спросить
Войти
Метод моделирования кривой первого порядка гладкости
Давдинова Татьяна Цыбиковна
кандидат технических наук
доцент, Восточно-Сибирский государственный университет технологий и управления 670000, Россия, республика Бурятмя, г. Улан-Удэ, ул. Ключевская, 40 В
ЕЗ dtatyanac@mail.ru Бубеев 1/Ьннокектий Трофимович
кандидат технических наук
доцент, кафедра Инженерная и компьютерная графика, Восточно-Сибирский государственный
университет технологий и управления
ЕЗ it_bubeev@mail.ru
Мотоикин Петр Владимирович
кандидат технических наук
доцент, кафедра Инженерная и компьютерная графика, Восточно-Сибирский государственный
университет технологий и управления
ЕЗ mpv_mpv@mail.ru
Статья из рубрики "Компьютерная графика, обработка изображений и распознавание образов"
Аннотация.
В статье представлен алгоритм моделирования составной кривой первого порядка гладкости. Приведены необходимые формулы для определения обвода, состоящего из дуг полиномов третьей степени. Первый вариант описывает аппроксимацию всего массива точек с требованием инцидентности первой и последней точкам контура. Второй вариант рассматривает моделирование кривой, с требованием инцидентности первой точке и свободным концом в последней точке, при этом используется принцип построения лекальных кривых. В третьем варианте кривая должна проходить через последнюю точку массива, а в первой точке должна соответствовать требованию первого порядка гладкости по касательной, полученной на предыдущем этапе. Предварительно на объекте определяются особые точки - точки излома контура и точки с вертикальными и горизонтальными касательными, которые накладывают условия гладкости на моделируемый обвод. Для моделирования кривой выполняется аппроксимация по методу наименьших квадратов полиномами третьей степени на множестве упорядоченных точек, ограниченных точками излома, которые составляют кромку. Преимущество разработанного способа моделирования обвода заключается, во-первых, в возможности обработки большого массива точек с соблюдением заданной точности. Во-вторых, значительно упрощается обеспечение гладкости первой степени обвода по сравнению с другими способами, использующими различные функции стыковки дуг обвода, а также немаловажное значение имеет возможность существенно сократить объем обрабатываемых данных, сохраняя при этом необходимую заданную точность. В дальнейших работах будут представлены остальные варианты и формулы для
расчета и их применение в области обратного проектирования, при решении задач геометрического моделирования при обработке изображений.
Дата направления в редакцию:
Дата рецензирования:
Дата публикации:
Введение
Повышение технических характеристик видеокамер и 3D сканеров и их повсеместное использование в различных областях обуславливает дальнейшее развитие методов и способов обработки изображений. Информация из видеопотока или информация в виде облака точек в дальнейшем используется в задачах распознавания, для получения характеристик отдельных деталей на объектах. Одной из областей применения этих данных является обратное проектирование, целью которого является определение формы, размеров, и других характеристик объектов реального мира на основе информации, представленной в виде облака точек. Координаты точек представляются в stl-формате из которого можно получить данные по сечениям и анализировать форму объекта на плоскости. При этом одной из важнейших задач является получение геометрической модели плоского контура, соответствующего заданной степени гладкости и точности [1, 2].
Задаче моделирования обводов - кривой, состоящей из нескольких частей, посвящено
множество научных исследований [2, 3,4], начиная с момента развития автоматизации проектно-конструкторских работ в отраслях тяжелой и легкой промышленности. Новый импульс эта задача получила с развитием компьютерной графики, систем обработки изображений, 3D сканированию, обратному проектированию. Анализ работ последних
лет показывает, что данная задача по-прежнему актуальна. [5, 6—7]. Особая роль отводится моделированию гладких обводов, имеющих совпадение на границах участков по ка с а те льной или крив из не .
Постановка задачи
Для моделирования кривой выполняется аппроксимация по методу наименьших квадратов полиномами третьей степени на множестве упорядоченных точек,
ограниченных точками излома, которые составляют кромку. Особые точки - точки излома, через которые должна проходить аппроксимирующая кривая - это точки нулевого порядка гладкости. Точки с вертикальными и горизонтальными касательными -точки первого порядка гладкости.
Для того, чтобы полиномы были состыкованы друг с другом по первому порядку гладкости, при моделировании используется метод построения лекальных кривых. С целью устранения появления участков с вертикальной касательной аппроксимация на каждом этапе выполняется в локальной системе координат.
Таким образом, на концах аппроксимируемой кромки возможны следующие сочетания видов точек:
■ обе граничные точки являются точками нулевого порядка гладкости;
■ начальная точка - точка нулевого порядка гладкости, конечная - точка первого порядка гладкости;
■ начальная точка - точка первого порядка гладкости, конечная точка - точка нулевого порядка гладкости;
■ обе точки - точки первого порядка гладкости. Рассмотрим алгоритм построения обвода.
Вначале выполняется аппроксимация всех точек кромки полиномом третьей степени в локальной системе координат, проходящей через конечные точки. Аппроксимация считается неудовлетворительной, если несколько точек подряд отстоят от аппроксимирующей кривой на расстоянии, превышающем некоторое допустимое значение б. В этом случае массив аппроксимируемых точек сокращается, изменяется локальная система координат и аппроксимация повторяется. Эти действия повторяются до тех пор, пока не будет достигнута требуемая точность аппроксимации на рассматриваемом множестве точек.
Когда второй конец аппроксимирующей кривой свободен, например, если на конце множества точек находится точка первого порядка гладкости, как дополнительное условие гладкости искомой кривой используется принцип построения лекальных кривых. Применение принципа построения лекальных кривых влияет на форму кривой, что облегчает стыковку со следующей дугой обвода. После этого выполняется аппроксимация оставшегося множества точек в новой локальной системе координат.
Четыре варианта сочетания видов граничных точек показал, что к дуге обвода могут быть предъявлены следующие требования:
и последнюю точки, выдерживая заданный
точку, выдерживая в ней заданное
первую
Моделирование обвода 1 степени гладкости
Вычисление коэффициентов аппроксимирующего полинома возможно в различных вариантах, так как сначала из условия аппроксимации можно установить взаимозависимости между некоторыми коэффициентами, а остальные свободные коэффициенты вычислить из минимизируемого функционала.
Приведем формулы, позволяющие вычислить коэффициенты
аппроксимирующего полинома третьей степени для случая, когда массив точек находится между двумя точками нулевого порядка гладкости (варианты 1, 2, 3).
Обвод будет состоять из дуг полиномов третьей степени, имеющих вид
у = а0 + а^ + агхг + а3х3 (1)
Вариант 1. На искомую кривую наложено условие прохождения через конечные точки множества аппроксимирующего полинома. Из условия аппроксимации следует, что полином должен быть инцидентен первой и последней точкам множества, которые задают локальную систему координат, следовательно, эти точки имеют координаты (0,0) и ( xN,0) . Учитывая это, получим коэффициенты данной кривой:
Тогда минимизируемый функционал можно записать в виде
Выполнив необходимые преобразования, получим коэффициенты а2, а3 :
^22 5*^2 51г5гг — 5г151г
Ь1 = У± Х1 Ох - Ьг = У1 (х{ - х1&)_
После определения а2 и а3 можно по формуле (2) вычислить коэффициент а1, затем по (1), получим искомое уравнение аппроксимирующего полинома, который описывает все точки кромки, если они находятся на расстоянии не большем заданного б.
Вариант 2. При несоответствии допустимой погрешности аппроксимации точек всей кромки (вариант 1), количество аппроксимируемых точек сокращается, и аппроксимация выполняется только с соблюдением условия инцидентности аппроксимирующей кривой
первой точке.
Для обеспечения гладкой стыковки следующей дуги используется принцип построения лекальных кривых,- к множеству аппроксимируемых точек присоединяются дополнительно несколько близлежащих точек следующей дуги, что влияет на форму кривой.
Исходя из существующего условия инцидентности кривой началу координат, коэффициент а0 будет равен 0, минимизируемый функционал аппроксимации будет выглядеть как
Коэффициенты
получаются из решения системы уравнений
Вариант 3. Аппроксимация выполняется на массиве точек оставшихся после успешного решения задачи, рассмотренной выше. Аппроксимирующий полином должен удовлетворять условию инцидентности первой и последней точкам множества, кроме того, на кривую наложено условие соблюдения угла наклона в первой точке.
Для уравнения (1) получим уравнение первой производной
Вычислив по выражению (3) и подставив вычисленные коэффициенты, получим уравнение аппроксимирующего полинома для варианта 3.
Результаты работы
Данная методика использовалась авторами для моделирования обвода по точкам контура лекал обувных и швейных изделий по их цифровым изображениям. При большом разрешении количество точек контура резко возрастает и перезадание точек кривыми дает возможность существенно сократить объем памяти, необходимый для хранения информации с сохранением необходимой точности.
Обвод, построенный в соответствии с предлагаемой методикой, с использованием расчетов по приведенным формулам представлен на рис.1.
Рис.1. Обвод первой степени гладкости
Пунктирной линией показана дуга, полученная при попытке построения обвода на всем множестве точек в системе хОу (вариант 1). Но так как она не выдерживает заданную погрешность, количество точек сокращается и аппроксимация выполняется в локальной системе x&O&y& с учетом принципа построения лекальных кривых (вариант 2). Оставшиеся точки аппроксимируются с учетом касательной к предыдущей дуге обвода (вариант 3).
Библиография
