Размещено на http://www.allbest.ru/

1

30TMN215

1

30TMN215

УДК 004.93

ОАО “Каспийский завод листового стекла” Россия, Махачкала

ФГБОУ ВПО “Дагестанский государственный технический университет” Россия, Махачкала

Кривые Безье в задачах распознавания образов

Штанчаев Хайрутин Баширович

Инженер АСУ ТП

Аспирант

E-mail: Shtanchaev.h@gmail.com

Аннотация

распознавание искусственный интеллект безье

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

Ключевые слова: математическая модель; граф; графовая модель; кривая Безье; сплайн; точка интереса; признаки объекта.

Abstract

Pattern recognition is one of the major problems of artificial intelligence. Problems related to machine vision, until recently, were very complex. This was associated with a small computing facilities, the lack of universal decision rules and methods. The article is devoted to the methods of recognition based on Bezier curves. The method allows to solve a wide range of pattern recognition and therefore universal. The method is modular and therefore it is possible to integrate it into any recognition as a tool for finding key attributes of object recognition. The article is an example of the search features of the object to a segmented region. The mathematical apparatus for searching and finding points of interest in a particular recognition task. The method will allow indefinitely increase recognition accuracy. It is only limited by the power of computing.

Keywords: mathematical model; graph; graph model; Bezier curve; spline; point of interest; the signs of the object.

Кривые Безье или Кривые Бернштейна-Безье были разработаны в 60-х годах XX века независимо друг от друга Пьером Безье из автомобилестроительной компании «Рено» и Полем де Кастельжо из компании «Ситроен», где применялись для проектирования кузовов автомобилей. Благодаря простоте задания и манипуляции, кривые Безье нашли широкое применение в компьютерной графике для моделирования гладких линий[1,4].

Кривая Безье -- параметрическая кривая, задаваемая выражением:

Где Pi - функция компонент векторов опорных вершин, bi,n базисные функции кривой Безье, называемые также полиномами Бернштейна [4].

где - число сочетаний из n по i, где n-степень полинома, ш-порядковый номер опорной вершины.

При n=1 кривая представляет собой отрезок прямой линии, опорные точки P0 и P1 определяют его начало и конец (рис.1.).

Рис. 1. Кривая Безье первого порядка

Приведем некоторые свойства кривой Безье которые идеально подходят для задач распознавания.

• Непрерывность заполнения сегмента между начальной и конечной точками.

• Кривая Безье симметрична, то есть обмен местами между начальной и конечной точками (изменение направления траектории) не влияет на форму кривой;

• Масштабирование и изменение пропорций кривой Безье не нарушает ее стабильности, так как она с математической точки зрения «аффинноинвариантна»;

• Изменение координат хотя бы одной из точек ведет к изменению формы всей кривой Безье;

• Невозможно создать параллельные кривые Безье, за исключением тривиальных случаев (прямые линии и совпадающие кривые).

Первое свойство кривой поясняет то, что кривая позволяет обводить распознаваемый объект непрерывно на всем участке. Свойство полезно для определения большего связного полигона при сегментации. Второе, третье и четвертое свойства дают возможность представить ключевые точки интереса объекта распознавания в качестве опорных точек кривой. Тем самым они останутся неизменными. Пятое свойство поясняет что не может быть одинаковых объектов с разными точками интереса. В задачах распознавания наибольшее значение имеют кривые Безье второй и третьей степеней (квадратичные и кубические). Кривые высших степеней при обработке требуют большего объёма вычислений и для практических целей используются реже. Для построения сложных по форме линий отдельные кривые Безье могут быть последовательно соединены друг с другом в сплайн Безье. Для того, чтобы обеспечить гладкость линии в месте соединения двух кривых, три смежные опорные точки обеих кривых должны лежать на одной прямой.

Пусть имеется кривая Безье описываемая выражением 1. При n=3 получим следующий вид записи для числа сочетаний n по i:

Исходя из (3) найдем базисные функции кривой Безье:

Используя (4) получим общий вид уравнения описывающий кривую Безье третьего порядка:

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

Рис. 2. Область в которой определена графовая модель губ идентифицируемого человека

Под термином построить кривую Безье подразумевается то, что мы будем строить две кривые Безье для данной графовой модели используя (5), которые при соединении начальных и конечных вершин максимально повторяют контур графовой модели. Для их построения необходимо найти две точки и , т.е. начальную и конечную точки кривой Безье.

Пусть область изображенная на рисунке 2 представляется следующей цветной графовой моделью[2].

(6)

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

??₀ = ??_??1(??, ??)если ???_??1(??, ??) ? ??_????(??), ?? < ??

Где k1 - количество вершин в ??_ОР.

Вершину ??_ОР ??_??1(??, ??) можно считать точкой ??₃ для кривых проводимых в этой зоне если абсцисса вершины является большей из абсцисс вершин ??_ОР, т.е.:

??₃ = ??_??1(??, ??)если ???_??1(??, ??) ? ??_????(??), ?? > ??

Т.е. вершину графовой модели ??_??1 можно считать точкой ??₀ если она расположена левее всех вершин. И соответственно вершину графовой модели ??_??1 можно считать точкой ??₃ если она находится правее всех вершин геометрически.

Для дальнейшего построения двух кривых Безье ??(??) и ??^?(??) необходимо найти 4 точки: ??1, ??2, ??1?, ??2?

Найдем две вершины ??_ОР ??₁(??₁, min (??₁)) и ??₂(??₂, min( ??₂)) у которых ордината вершины является меньшей ординатой вершин ??_ОР.

Если ??₁ > ??₂ , то точку ??_ОР ??₁(??₁, min (??₁)) можно считать точкой ??^?₂ , а точку ??₂(??₂, min (??₂)) можно считать точкой ??₁^? .

Если ??₁ < ??₂ , то точку ??_ОР ??₁(??₁, min( ??₁)) можно считать точкой ??₁^? , а точку ??₂(??₂, min (??₂)) можно считать точкой .

Находим две вершины ??_ОР ??₁(??₁, max (??₁)) и ??₂(??₂, max (??₂)) у которых ордината вершины является большей ординатой вершин ??_ОР.

Если ??₁ > ??₂, то вершину ??_ОР ??₁(??₁, max (??₁)) можно считать точкой ??₂, а вершину ??₂(??₂, max (??₂)) можно считать точкой ??₁.

Если ??₁ < ??₂ , то точку ??_ОР ??₁(??₁, max( ??₁)) можно считать точкой ??₁ , а точку ??₂(??₂, max (??₂)) можно считать точкой ??₂.

Обозначим найденные точки на рисунке восстановив изображение 3:

Рис. 3. Точки отмеченные на изображении

По данным точкам проводим кривые Безье, а именно ??(??) и ??^?(??) используя отмеченные на рис.3. точки. Учитывая выше найденные точки, формулы для построения будут выглядеть следующим образом:

??(??) = (1 ? ??)³??₀ + 3??(1 ? ??)²??₁ + 3??²(1 ? ??)??₂ + ??³??₃(7)

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

Таблица 1 Коэффициенты для построения кривых Безье

Результат построения двух кривых Безье для графовой модели можно видеть на рисунке 4.

Рис. 4. Результат построения кривых Безье. Справа отмеченные точки для построения. Слева результат построения

В том или ином методе распознавания используются определенные признаки для отнесения предложенного объекта к классу объектов. Не менее сложным, чем сам процесс распознавания является процесс выделения этих признаков объекта. В описываемом методе признаками для распознавания являются точки интереса. Точки интереса получаем после построения кривой Безье. Кривые Безье могут строится начиная из любой точки, т.е. точка ??₀ может иметь любые координаты в рассматриваемой области. Это прямым способом влияет на точность распознавания, т.к. объект в области(а именно губы) может располагаться в любом месте и точки интереса одного и того же объекта на различных изображениях могут иметь разные координаты. В связи с этим мы производим параллельный перенос объектов во всех трех областях. Для осуществления параллельного переноса каждая точка объекта изменяется на определенное число а для абсциссы и b для ординаты. Пусть имеется графовая модель G включающих все вершины черного цвета рассматриваемой зоны:

?? = (??, ??)

Тогда имеем две вершины:??₀, ??.

Как выше описывалось ??₀ - начальная точка кривой Безье. Эта вершина имеет координаты . А вершина ?? определяется в зависимости от точек .

Пусть . Тогда имеем условие: если если , т.е.

Необходимо осуществить параллельный перенос таким образом чтобы вершины ??₀, ?? имели следующие координаты:

??₀(0, ??^?) ??(??^???, ??)

Для этого имеем:

?? = ??^? ? 0 ?? = ?? ? ??^???

Тогда:

???_?? ? ??, ??_??(?? ? ??, ?? + ??)

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

Для области (рис.3.) будем иметь дело с множеством точек кривых Безье. Сначала рассчитаем точки кривых в каждой из областей по t от 0 до 1 с шагом 0.5.

Коэффициенты bij для t от 0 до 1 c шагом 0.05 будут иметь вид:

Таблица 2 Коэффициенты bij рассчитанные для t=0…1

Подставив в 7 значения t из таблицы 2. и координаты точек ??₀, ??₁, ??₂, ??₃ получим 21 точку интереса для кривой ??(??). Подставив 8 значения t из таблицы 2 и координаты точек ??₀, ??^?₁, ??^?₂, ??₃ получим 21 точку интереса для кривой ??^?(??). Следовательно имеем для каждой области по 2 множества (одно множество для кривой ??(??) второе для ??^?(??) ). Получим множества Каждый элемент множества представляет собой точку ??(??_??, ??_??) . Каждая точка интереса и является признаком объекта. Имея выделенные признаки объекта можно любым известным методом распознавания образов идентифицировать объект. Исходя из проведенных экспериментов наиболее подходящим по таким критериям как быстродействие и точность распознавания является метод вычисления разностных термов[3] который хорошо себя зарекомендовал в задачах распознавания и идентификации человека.

При недостаточной точности распознавания в той или иной задаче необходимо увеличить шаг t. Следовательно можно получить большее количество точек интереса. Увеличение точности распознавания таким путем ограничено только ресурсами вычислительной техники.

Литература

1. Роджерс Д., Адамс Дж. Математические основы машинной графики. -- М.: Мир, 2001.

2. Штанчаев Х.Б. Исследование оптимальных решающих процедур для идентификации и классификации человека на изображении // Интернет-журнал «НАУКОВЕДЕНИЕ» Том 7, №3 (2015) http://naukovedenie.ru/PDF/02TVN315.pdf (доступ свободный). Загл. с экрана. Яз. рус., англ. DOI: 10.15862/02TVN315

3. Штанчаев Х.Б. Применение графовой модели и априорного классификатора для сегментации изображения в задачах распознавания лица человека // Интернетжурнал «НАУКОВЕДЕНИЕ» Том 7, №2 (2015) http://naukovedenie.ru/PDF/130TVN215.pdf (доступ свободный). Загл. с экрана. Яз. рус., англ. DOI: 10.15862/130TVN215

4. Shane Aherne. "Kochanek and Bartels Splines". Motion Capture -- exploring the past, present and future. Retrieved 2009-04-15.

Размещено на Allbest.ru