Распознавание на базе оценок сходства, инвариантных относительно аффинных преобразований1 Ю. Г. Васин2, Л. И. Лебедев2



Скачать 83.02 Kb.
Дата20.10.2016
Размер83.02 Kb.


РАСПОЗНАВАНИЕ НА БАЗЕ ОЦЕНОК СХОДСТВА, ИНВАРИАНТНЫХ ОТНОСИТЕЛЬНО АФФИННЫХ ПРЕОБРАЗОВАНИЙ1

Ю.Г. Васин2, Л.И. Лебедев2
2Научно-исследовательский институт прикладной математики и кибернетики
Нижегородского государственного университета им. Н.И. Лобачевского
603005, Россия, Нижний Новгород, ул. Ульянова, 10, НИИ ПМК.
E-mail: vasin@focus.ac.su, lebedev@pmk.unn.ru

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



Введение

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




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

Группа аффинных преобразований на плоскости является одной из примитивных групп Ли и может быть задана следующим уравнением


, (1)
где матрица , – произвольная точка плоскости, а – образ этой точки, – вектор параллельного переноса. Если оценку сходства эталона с произвольным объектом формировать на основе невязки их метрических описаний, то она будет инвариантной относительно аффинных преобразований при вычислении ошибки по формуле
. (2)
В формуле (2) вычисления невязки через и обозначены согласованные описания эталона и распознаваемого объекта соответственно, полученные при равномерной интерполяции контуров заданным количеством точек .

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



Методы решения

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


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

Полученные результаты

Теорема 1. С точностью до параллельного переноса любое аффинное преобразование можно задать последовательностью операций , то есть имеет решение следующая нелинейная система уравнений относительно неизвестных
(5)
Доказательство. Из первого и третьего уравнений системы (5) легко определяется основное значение угла
. (6)

(Случай дает особое решение , , . При этом, если и значения , то очевидным решением системы будет при произвольных значениях других неизвестных величин). Из этих же первого и третьего равенств находим, что


. (7)
Алгебраическая сумма второго и четвертого уравнений системы (5), предварительно умноженных соответственно на и дает следующий результат
. (8)
Значение коэффициента масштабирования найдем из уравнения
,
которое можно получить, если во второе уравнение подставить найденные параметры (6)-(8) и освободиться от радикалов возведением обеих частей равенства в квадрат. Из четырех корней биквадратного уравнения два отрицательных корня отбрасываем по смыслу коэффициента масштабирования, а из двух положительных корней необходимо взять с наибольшим значением. Корень с наименьшим положительным значением не удовлетворяет нас потому, что при значение коэффициента масштабирования окажется равным нулю, чего в общем случае не должно быть. Следовательно,
, (9)
где .

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

Если это действительно так, то должно выполнятся неравенство

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

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

.

Следовательно, решение по углу существует. Для доказательства существования решения по углу необходимо показать, что правая часть в выражении (8) по модулю не превышает единицу при любых значениях . Если обозначить через и , то выражение (8) можно представить в виде


. (11)
Таким образом, необходимо показать, что . Подстановка в данное неравенство значения приводит к неравенству (10), истинность которого мы доказали выше. Следовательно, формулы (6)-(9) определяют одно из решений нелинейной системы (5). Теорема доказана.
Теорема 2. Сложность предлагаемого метода вычисления коэффициента сходства, инвариантного относительно аффинных преобразований для согласованных описаний эталона и объекта, определяется величиной

.

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



– число узлов в методе сеток при дискретизации параметров и соответственно;

– число операций, связанных с вращением одной точки в пространстве;

– число операций, приходящихся на одну точку описания при вычислении коэффициента сходства эталона с объектом;

- количество точек в исходных описаниях эталона и объекта соответственно.

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

.

Заключение

Предложенный метод декомпозиции операций, реализующих аффинное преобразование, был применен для решения задачи уточнения направления распознаваемых надписей на основании учета наклона входящих в нее символов. С точностью до масштабирования и ортогонального преобразования на плоскости аффинное преобразование с параметрами , позволяет определить наклон распознаваемого символа относительно эталона. При этом на основании формул (6)-(8) имеем и, следовательно, для получения различных описаний в соответствии с (3) варьировать необходимо только один параметр в пределах от 0 до 90 градусов. Отсюда, угол наклона определяется по формуле , а истинное направление надписи значением угла ортогонального преобразования.



Список литературы

  1. Васин Ю.Г., Лебедев Л.И., Инвариантные методы определения сходства плоских форм. // Информационные технологии в анализе изображений и распознавании образов: I-ая Междунар. конф.: Тез. докл. /Львов, Физ.-мат. ин-т АН УССР, 1990. С.225-228.

  2. Васин Ю.Г., Лебедев Л.И., Плесков А.В., Пучкова О.В., Морозов В.А. Двухуровневый алгоритм распознавания последовательностей графических изображений. // Распознавание образов и анализ изображений: новые информационные технологии (РОАИ-2-95): 2-ая Всероссийская с участием стран СНГ конференция: Тез. докл. /Ульяновск, УГТУ, 1995, ч.2. С.67-68.

  3. Файн Б.М. Опознавание изображений. - М., «Наука», 1970. 299 с.

____________________________________________________________

1Работа выполнена при поддержке РФФИ, проект № 05-01-00590

Каталог: data -> materials -> conf -> pria8 -> disc rus -> vol2
data -> Сборник «В поисках смыслов: успешные практики патриотического воспитания молодежи»
data -> 1. Технические спецификации как средство ограничения конкуренции на рынке государственных закупок
data -> Программа дисциплины Системы управления проектами для направления 080100. 62
data -> Лабораторная работа №1 Разработка описания и анализ информационной системы
data -> Программа дисциплины Подготовка многостраничного текста эссе и его презентация на компьютере для направления 080100. 62
data -> Использование облачных технологий Google в проектЕ «Scotland» по английскому языку
data -> Проект программы дисциплины
disc rus -> Методы визуализации моделей data mining при обработке телеметрической информации а. О. Дерипаска1, В. В. Геппенер1


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©grazit.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал