Аппроксимация полигонов распознаваемого образа полиномиальными сплайнами

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

Аппроксимация полигонов распознаваемого образа полиномиальными сплайнами

А. В. Лубенцов, Л. П. Коротких

Аннотация. Работа посвящена проблеме аппроксимации реперных точек, полученных с исследуемого образа для идентификации его в базе данных.

Ключевые слова: распознавание образов, аппроксимация, реперные точки, граничные, начальные условия, сплайны.

APPROXIMATION OF POLYGONS OF THE RECOGNIZED IMAGE BY POLYNOMIAL SPLINES

A. V. Lubentsov, L. P. Korotkikh

FKOU IN Voronezh Institute of the Federal Penitentiary Service of Russia, Voronezh, Russia

Abstract. The work is devoted to the problem of approximation of fixed points obtained from the image under study for identification in the database.

Keywords: pattern recognition, approximation, fixed points, boundary, initial conditions, splines.

1. Введение

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

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

Рис.1. Пример выделения реперных точек на образе.

2. Постановка задачи. Характеристики сплайна. Выбор вида сплайна

«Сплайны (кусочно-многочленные функции) были введены в рассмотрение в 1946 году И. Шнбергом. Однако только в 1957 году было установлено, что среди всех интерполирующих заданные значения гладких функций именно они минимизируют некий функционал, близкий к функционалу энергии изгибаемой рейки. Данное обстоятельство послужило предпосылкой возможного практического использования сплайнов для математического описания кривых и поверхностей» [3]. Таким образом, сплайн -- это комплексная сложносоставная функция, минимизирующая энергию упругости аппроксимирующей кривой или поверхности. Построение сплайнов в пространствах с размерностью более 3 - отдельная нетривиальная задача и не входит в рассматриваемую тему [4-5].

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

б. Задача аппроксимации

По данному набору значений функции u(x ) на сетке x_i Х g_i , где i =0…N; и восстановить функцию U(x ), совпадающую с u(x_i ) в узлах x_i .

В связи с использованием сплайнов на каждом отрезке [x_i-1; x_i ] функция является некоторым многочленом (полиномом) s_i (x ), причем на каждомотрезке эта функция оригинальная.

В такой постановке задача имеет множество решений. Единственность решения можно обеспечить, потребовав от функции U(x ) некоторой гладкости в местах стыков функций s_i (x ), то есть в узлах коммутации функций.

U(x ) = s_i (x ); x принадлежит [x_i-1; x_i ] (1)

s_i? (x_i ) = s_i?₊₁( x_i ) (2)

s_i?? (x_i ) = s_i??₊₁(x_i ) (3)

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

3. Задание начальных и граничных условий

а. Условия непрерывности

Запишем условия непрерывности сплайна в параметрах коэффициентов на каждом участке: a_i ; b_i ; c_i ; d_i . Тогда условие непрерывности U(x ) в точке x_{i -1}:

a_{i -1} = s_{i -1}(x_{i -1}) = s_i (x_{i -1}) = a_i +b_i (x_{i -1}-x_i )+ (x_{i -1}-x_i )²+ (x_{i -1}-x_i )³ где i = 2;:::; N. (4)

б. Условия гладкости

Для достижения непрерывности и согласованности элементов сплайна на стыках необходимо потребовать непрерывность первой и второй производной. Запишем условия непрерывности первой и второй производной U(x ) в точках x_{i -1}:

b_{i -1} = s_i?_-1(x_{i -1}) = s_i? (x_{i -1}) = b_i + c_i (x_{i -1} - x_i ) + (x_{i -1} - x_i )²; (5)

c_{i -1} = s_i??_-1(x_{i -1}) = s_i?? (x_{i -1}) = c_i + d_i (x_{i -1} - x_i ):i = 2;:::; N. (6)

в. Условия аппроксимирования

Запишем условия аппроксимирования, то есть U(x_i ) = u(x_i )

a_i = s_i (x_i ) = U(x_i ) = u(x_i ); i = 1;:::; N: (7)

Дополнительно зададим начальные условия в точке x₀,

a₁ + b₁(x₀ - x₁) + (x₀ - x₁)² + (x₁ - x₀)3 = s₁(x₀) = U(x₀) = u(x₀), (8)

Условия s_{i +1}(x_i ) = U(x_i ),автоматически удовлетворяются при выполнении условий непрерывности.

a_i = u(x_i ); i = 1;:::; N (9)

г. Краевые условия

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

Применение естественного сплайна

U ?? (x₀) = U ?? (x_N ) = 0: (10)

Понижение степени сплайна на краях до второй

U ??? (x₀) = U ??? (x_N ) = 0: (11)

Применение периодического сплайна

U ??? (x₀) = U ??? (x_N ); U ?? (x₀) = U ?? (x_N ): (12)

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

c_N = s_N?? (x_N ) = U ?? (x_N ) = 0 (13)

4. Построение модели. Построение сплайна

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

В общем виде сплайн будет выглядеть следующим образом:

U(x_i) = , (14)

где k - порядок сплайна.

Найдем выражения для функций s_i (x ), составляющих гладкий кубический сплайн.

Поскольку сплайн имеет степень 3, все функции s_i (x) являются многочленами степени 3. Запишем их в виде

s_i (x) = a_i + b_i (x - x_i) + (x - x_i )² + (x - x_i )^3/(15)

Такая форма записи соответствует ряду Тейлора для s_i (x) в окрестности точки x_i. Поскольку s_i (x) кубический многочлен, его ряд Тейлора обрывается после кубического слагаемого. Из аналогии с рядом Тейлора заключаем, что

a_i = s_i (x_i ); b_i = s_i? (x_i ); c_i = s_i?? (x ); d_i = s_i??? (x_i ). (16)

а. Система уравнений

Объединим полученные ранее уравнения в единую систему, подставив h_i= x - x_i

a_{i -1} = a_i - b_i h_i + h_i² - h_i³; i = 2;:::; N; (17)

b_{i -1} = b_i - c_i h_i + h_i²; i = 2;:::; N; (18)

c_{i -1} = c_i - d_i h_i ; i = 2;:::; N ; (19)

a_i = u(x_i ); i = 1;:::; N ; (20)

a₁ - b₁h₁ + h₁² - h₁³ = u(x₀); (21)

Всего в этой линейной системе 4N - 2 уравнения, хотя неизвестных 4N. Для замыкания системы два дополнительных условия могут быть выбраны достаточно произвольно, например, как краевые условия на концах отрезка в точках x₀ и x_N.

б. Линейная система

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

в. Сглаживание

Доказано, что если u(x) непрерывна, то последовательность кубических сплайнов UN (x) будет сходиться к u(x) равномерно, то есть

= 0,(22)

где max h_i > 0.

Исследуемые сплайны, как правило, относится к глобальным. Если изменить значение u(x_i) в какой-либо точке, это приведет к изменению всего сплайна U(x), с затуханием амплитуды изменения по мере удалении от точки x_i.

Таким образом, использование аппарата сплайнов для описания реперных точек сравниваемого образа, позволяет добиться однозначной математической идентификации. Для идентификации образа в базе данных необходимо корректно задать пределы допустимых флуктуаций коэффициентов сплайна. Кроме этого, модель сплайна позволяет сравнивать образы с пространством признаков больше трех, что бывает затруднительно в других моделях [7].

аппроксимация реперный флуктуация сплайн

Литература

1. https://shop.mts.ru/news/ja-uznaju-tebja-po-mimike-tekhnologija-razblokirovki-smartfona-po-litsu/ (Дата обращения: 12.02.2019)

2. Шумейко А.А. Некоторые экстремальные задачи теории приближения функций сплайнами: ил РГБ ОД 61:85-1/1617

3. Волков Ю.С. Исследование аппроксимативных свойств интерполяционных сплайнов, Методы сплайн-функций. Российская конференция. Институт математики им. С.Л. Соболева Сибирского отделения РАН 2011. - С. 33-35.

4. Де Бор К. Практическое руководство по сплайнам Пер. с англ. -- М.: Радио и связь, 1985. - 304 с.

5. Алберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения Монография. -- Перев. с англ. Ю.Н. Субботина. -- М.: Мир, 1972. - 319 с.

6. Васильев, Юрий Сергеевич. Аппроксимация сплайнами с нефиксированными узлами: автореферат дис. кандидата физико-математических наук: 01.01.01. - Екатеринбург, 1992. - 18 с.

7. Гомонов А.Д. Математическое моделирование уровенной поверхности океана по спутниковым данным на основе двумерной B-сплайн аппроксимации: диссертация кандидата технических наук: 05.13.18 / А.Д. Гомонов [Место защиты: С.-Петерб. гос. электротехн. ун-т (ЛЭТИ)]. - Санкт-Петербург, 2011. - 131 с.: ил. РГБ ОД, 61 11-5/3318

References

1. https://shop.mts.ru/news/ja-uznaju-tebja-po-mimike-tekhnologija-razblokirovki-smartfona-po-litsu/ (Contact date: 12.02.2019)

2. Shumeyko A.A. Some extremal problems of the theory of approximation of functions by splines: silt RSL of OD 61: 85-1 / 1617

3. Volkov, Yu.S. Investigation of the approximate properties of interpolation splines, Methods of spline functions. Russian conference. Institute of Mathematics S.L. Sobolev, Siberian Branch of the Russian Academy of Sciences 2011. - p. 33-35.

4. De Boer K. A practical guide to the splines Per. from English - M .: Radio and communication, 1985. - 304 p.

5. Alberg, J., Nilson, E., Walsh, J. The theory of splines and its applications Monograph. - Trans. from English Yu.N. Subbotin. - M .: Mir, 1972. - 319 p.

6. Vasilyev, Yury Sergeevich. Approximation by splines with non-fixed nodes: abstract of dis. Candidate of Physical and Mathematical Sciences: 01.01.01. - Ekaterinburg, 1992. - 18 p.

7. Gomonov A.D. Mathematical modeling of a level ocean surface from satellite data on the basis of a two-dimensional B-spline approximation: dissertation of a candidate of technical sciences: 05.13.18 / AD Gomonov [Place of protection: St. Petersburg. state electrical engineering un-t (LETI)]. - St. Petersburg, 2011. - 131 pp., Ill. RSL OD, 61 11-5 / 3318

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