Алгоритмические схемы распознавания изображений двумерных объектов на основе адресных сортировок тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Гуревич, Михаил Юрьевич

• Гуревич, Михаил Юрьевич
• кандидат технических наук
• 2001

Оглавление диссертации кандидат технических наук Гуревич, Михаил Юрьевич

ВВЕДЕНИЕ И ПОСТАНОВКА ВОПРОСА.

1. ВЫЧИСЛЕНИЕ ЭКСТРЕМУМОВ ФУНКЦИИ ОДНОЙ И ДВУХ ПЕРЕМЕННЫХ ПО СХЕМАМ ЛОКАЛИЗАЦИИ И СПУСКА НА ОСНОВЕ АДРЕСНОЙ СОРТИРОВКИ.

1.1. Введение и постановка вопроса.

1.2. Алгоритмическая схема локализации экстремума на основе адресной распараллеливаемой сортировки.

1.3. Численный эксперимент.

1.3.1. Вычисление всех минимумов функции одной переменной.

1.3.2. Вычисление всех минимумов функции двух переменных

Введение диссертации (часть автореферата) на тему «Алгоритмические схемы распознавания изображений двумерных объектов на основе адресных сортировок»

Задачу распознавания изображений можно рассматривать как частный случай классической задачи общей теории распознавания образов. Однако ей присущи существенные особенности, отличающие ее общей абстрактной задачи. Прежде всего это разнообразие видов изображений, подлежащих распознаванию. Объектами распознавания могут служить изображения, полученные в различных частях спектра излучений (оптические, инфракрасные, ультразвуковые), кроме того специфику вносят технические способы представления изображений (телевизионные, фотографические, лазерные, радиолокационные, радиационные), включая особенности цифровой и аналоговой формы представления изображений. В качестве средств представления изображений используются растровое представление, пазиционное представление, древовидные структуры данных, эскизы Марра (Д. Марр. Зрение. Информационный подход к изучению представления и обработки зрительных образов. - Москва: Радио и связь, 1987) и фреймовые конструкции.

При представлении исходной информации в виде изображений принято выделять три основных направления: машинную графику, обработку изображений и распознавание зрительных образов (изображений), которые в и т-ч и значительной мере пересекаются. В этой связи можно говорить о самостоятельной области информатики - распознавании и анализе изображений (Павлидис Т. Алгоритмы машинной графики и обработки изображений. - М.: Радио и связь, 1986).

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

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

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

По способу представления и обработки выделяются четыре класса изображений (Павлидис Т. Алгоритмы машинной графики и обработки изображений. - М.: Радио и связь, 1986).

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

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

Класс 2: бинарные и выполненные в нескольких цветах изображения (например, печатный текст). Бинарные (черно-белые) изображения могут представляться матрицами с затратой одного бита на элемент, а также в виде карт, поскольку они содержат явно выделяющиеся области одного цвета. Именно поэтому эти два типа изображений объединены в один класс, хотя матричное представление удобно лишь для бинарных изображений.

Класс 3: непрерывные кривые и прямые (контуры, сигналы и графики).

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

Преобразования, не выводяпще изображение за пределы класса, сравнительно просты. Так, фильтрация, обеспечивающая повышение контраста, удаление высокочастотного шума и т.д. являются примерами преобразований, применяемых к изображениям классов 1 и 2, изменение системы координат (в том числе, перенос и поворот) - примером преобразований, применяемых к изображениям классов 3 и 4. К изображениям любого класса может применяться разложение в ряд (ортогональный, чаще всего - ряд Фурье). в настоящее время распознавание изображений приобретает все более весомое значение для многих областей науки и производства. Это связано с увеличением объема обрабатываемой информации. Например, по данным статистики середины 90-х годов, только в США в год получают порядка 25 млрд. снимков, изображений, требующих той или иной обработки. Использование вычислительной техники для их обработки позволяет решать требуемые задачи в короткие сроки и с меньшими затратами по сравнению с другими способами обработки.

Кратко остановимся на основных положениях известных методов распознавания образов.

По классификации III методы распознавания представляются схемой

Методы статисти- Метод

Геометрические „ ческих решении дискриминантных Другие методы методы метод Байеса) функций

Нормальные тт „ Корреля- Стохасти

Линейные , Нелинейные распреде- Ф-функции , ционный ческая апметоды функции ления метод проксимация

Нелинейные Произвольные Линейные Кус°чн° Лингвистичес- Регрес линейные „ сионный методы распределения функции кий метод функции метод

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

Геометрический метод распознавания основан на использовании некоторой функции подобия (принадлежности) 5' объекта данному классу. Эта функция определяет некоторую меру близости объекта bj с координатами л: = (хА,,.Хдг) к множеству эталонов у"А = (лл ,у2,.уА)~ Часто за меру близости принимается среднеквадратическое расстояние \ i л л / \ 5(х,у'")= - УсАНх,у"А)

Метрика с/, или метод измерения расстояния, в каждом отдельном случае может быть разной. Однако метрика должна удовлетворять условиям: d{a,b)=d{b,a), d{a,c)<d{a,b)+d{b,c), d{a,b)>0, d{a,b = 0) только при а = Ь.

Обучение при геометрическом подходе можно трактовать как задачу определения такой оптимальной метрики, при которой минимизировалось бы среднеквадратическое расстояние где улу,,— /-Й эталон т-то класса. Как правило, рассматривается такой класс метрик, который описывается формулой

Ь=1

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

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

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

Имеется полная группа несовместных гипотез, роль которых при распознавании выполняют образы

А: 4, Л2,.4-,.Лм

Известны априорные распределения вероятностей этих гипотез, то есть известно, с какой вероятностью появляется данный образ:

Р(4),Р(Л).".Фм) причем, так как группа полная, то м 1

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

В общем случае считаются заданными условные вероятности Р(ЬА./ЛД / = 1,2,. ,М, 7 = 1,2,,.,Г; требуется определить вероятность Р[АА1Ъ^).

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

Не детализируя базовые соотношения байесовского метода, подробно описанные в /1 /, остановимся на основных положениях метода дискриминантных функций. Этот метод имеет две модификации: метод решающих функций и метод потенциальных функций, однако идея у этих модификаций одна. Считается, что существуют поверхности условных плотностей распределения вероятностей Р{х1 Ал = Рл,(х), то есть вероятностей появления значений признака х при условии, что объект принадлежит к классу . Однако запомнить в ЭВМ эту многомерную функцию зачастую не представляется возможным. Поэтому ее аппроксимируют функциями, которые и называются решающими, потенциальными или дискриминантными функциями gA(x). Причбм практически задача заключается не столько в аппроксимации, сколько в разработке методов построения этих функций, если заданы набор эталонов или обучающая последовательность. Сами функции должны выбираться так, чтобы облегчить процесс их практического получения. Эта постановка задачи характерна для вероятностного распознавания. При детерминированном распознавании задается некоторое количество эталонов и требуется любой новый объект отнести к определенному классу. Здесь предполагается существование разделительных поверхностей. На этом множестве эталонов определяются дискриминантные функции gi{x). Разделительная поверхность определяется из уравнений gi(x) = gJ{x), ]. В методе дискриминанных и потенциальных функций в качестве решающего правила выбирают знак разности AgjJ = gA - gj. Если эта величина положительна, то объект относят к классу /, если отрицательна - к классу ].

Разделяющие функции, как правило, берутся линейными, квадратичными или кусочно-линейными. Соответственно этому различают линейное, квадратичное и кусочно-линейное распознавание. Для линейного распознавания в общем случае разделяющая поверхность может быть записана в виде g{x) = ЩХА + Ш2Х2 + . + йтлхдг + .

Процесс обучения заключается в определении коэффициентов .

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

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

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

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

В методах распознавания активно используется лингвистическая модель, в частности, она используется для распознавания изображений. Изображения рассматриваются состоящими из ряда частей, в качестве которых выступают геометрические характеристики изображения. На первом этапе производится выделение этих характеристик, затем составляется логическое описание изображения, в котором элементами являются характеристики форм частей изображения и характеристики из взаимного расположения. Совокупность геометрических характеристик изображения и множество правил их соединения представляют собой специальный язык PDL (picture description language). Его синтаксис, приводимый в III, имеет графическую интерпретацию, на основе которой строится распознавание. Лингвистическое распознавание часто называют структурным. Конечная цель процедур структурного распознавания - это получение структурных описаний входных объектов и, в частности, изображений.

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

Например, для т классов изображений Fi,F2,.,FA можно построить т соответствующих грамматик Ga, G2 , G a , таких, что цепочки, порожденные грамматикой Gj, будут представлять изображения только из класса Vj. Тогда для произвольного изображения, описываемого цепочкой X, задача распознавания сводится к вопросу: верно ли, что

XeL[Gj\ 7 = 1,2,.

Алгоритм распознавания описывается в виде

XeVj, если XEL[GJ} HX*L{GI).

Здесь L{GJJ - язык, порожденный грамматикой Gj.

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

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

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

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

Возвращаясь к общей характеристике состояния проблемы распознавания изображений, следует отметить, что на сегодняшний день известны многочисленные методы распознавания, успешно применяемые в различных отраслях производства и областях научных исследований. Основы существующих методов различны, среди них, такие как: использование локальных адаптивных элементов (Koh Eunyoung, Metaxas Dimitry, Baldev Norm. Hierarchical shape representation using locally adaptive finite elements // Lect. Notes Comput. Sei. - 1994. - №300. - pp. 441-446), вьщеление ключевых точек контуров 111, параметрический поиск с использованием пространственно-ориентированных масок объектов / 3 /. Широкий класс методов основан на применении нейроподобных сред и элементов, где используются элементы искусственного интеллекта и генетического поиска / 4-7 /; схемы распознавания, использующие активные распределенные нейроподобные среды / 8 /, а также мультимодульные нейросетевые модели 191 однослойный / 10 / и многослойный перцептроны. Помимо того, используются: симультанная модель распознавания /11/, алгоритмы основанные на вычислении оценок /12/, стохастические методы /13/, алгоритмы на основе решающих правил /14/, кореляционно-экстремальные методы / 15 /.

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

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

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

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

В производстве коммерческих систем, применяемых для распознавания двуцветных изображений, в частности, для распознавания текста, одним из лидеров является компания ABBY Software House и ее программный продукт -семейство пакетов распознавания текстовой информации FineReader. Сравнивая FineReader с другими существующими пакетами распознавания, такими как TextBridge компании ScanSoft Inc. и CuneiForm компании Cognitive Technologies, можно отметить преимущество первого. Удобство в использовании, качественное и быстрое распознавание, адаптация к различным языкам - это преимущества, доступные каждому пользователю. Вместе с тем применение данного пакета к распознаванию нетипичных изображений (то есть, изображений с пониженным разрешением, изображений с измененными размерами) обнаруживает снижение качества распознавания, а в критических случаях и неработоспособность используемых в пакете программ алгоритмов. Существенно отметить, что по оценкам специалистов, требуемая достоверность распознавания изолированных символов должна приближаться к 100%, а при вводе слитного текста ее значение должно быть не ниже 95-96%. В некоторых из отмеченных критических случаев достоверность распознавания снижается до 56%).

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

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

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

Системы распознавания оперируют с большим объемом информации, требуюш,им соответственно больших объемов памяти и высокого быстродействия вычислительных устройств. Одним из развитых направлений решения этих проблем является распараллеливание алгоритмов распознавания и использование средств параллельных вычислительных систем, таких как кластерные параллельные суперкомпьютеры класса Beowulf, реализованых в системах Hrothgar, Hive (NASA), Loki (Los Alamos National Laboratory), Megalon и Aeneas cluster (California) /16-19/. Отчасти этим, a также спецификой алгоритмических схем распознавания обусловлено направление в построении систем распознавания образов на базе нейрокомпьютеров /4-10,20-27 /.

Дополнительный аспект актуальности темы диссертационной работы можно видеть в подходе к распознаванию на основе сортировки. Сама по себе тема конструирования эффективных, в частности, распараллеливаемых сортировок традиционно сохраняет актуальность в области теоретических основ информатики / 28-36 /. Эта актуальность имеет объективные причины, обусловленные тем, что схемы сортировки находят разнообразное применение в системах программирования, в программном обеспечении, в системах обработки информации, управления базами данных, а также существенно используются в архитектуре современных ЭВМ / 37 /.

Таким образом, в работе по существу соединены две актуальные тематики в области теоретических основ и приложений информатики.

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

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

Для достижения цели в диссертации формулируются и решаются следующие задачи:

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

2) перенести схему на область поиска экстремальных особенностей дискретных числовых последовательностей и, соответственно, применить схему поиска для нахождения экстремальных особенностей числовых идентификаторов изображений плоских объектов;

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

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

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

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

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

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

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

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

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

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

Внедрение результатов. Результаты диссертационной работы внедрены в госбюджетной НИР ТГПИ «Математические методы устойчивой параллельной обработки, поиска и распознавания» - код ВНТИЦ 02 0318 206 0355; использовались в НКБ Вычислительных систем ТРТУ.

Апробация работы. Основные результаты работы докладывались на профессорско-преподавательских конференциях в Таганрогском педагогическом институте (1998-2001 гг), на рабочих семинарах ТГПИ (2000, 2001 гг) и ТРТУ (2001 г); на 5-й международной конференции «Математические модели физических процессов и их свойства» (Таганрог,

1999 г); на Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности» (Таганрог, 1999 г), на 6-й международной конференции «Математические модели физических процессов и их свойства» (Таганрог, 2000 г), на международной научно-практической конференции «Проблемы образования студентов гуманитарных вузов в свете развития современных информационных технологий» (Таганрог, 2001 г).

Публикации. По теме диссертации опубликовано 8 работ, из которых одна работа в центральной печати, 4 включены в труды международных конференций.

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

Заключение диссертации по теме «Теоретические основы информатики», Гуревич, Михаил Юрьевич

Результаты работы программы абсцисса- 1 ордината- 1 функция (максимум) - О аргумент функции - О абсцисса- .9999999772945353 ордината- 2.772453850905516 функция (максимум) - О аргумент функции - 1 абсцисса- 2.735984839677407 ордината- .6423000000000006 функция (максимум) - -2.678977844196551Е-068 аргумент функции - 1 абсцисса- .4519623246620783 ордината- 2.6856 функция (максимум) - -1.325841973931019Е-067 аргумент функции - 1 абсцисса- 1.70364366947326 ордината- 2.6268 функция (максимум) - -1.579513156541428Е-064 аргумент функции - 1 абсцисса-, 1.788110965276968 ордината- 2.5876 функция (максимум) - -1.381786968815111Е-072 аргумент функции - 1

Приближенное вычисление нулей и экстремумов производных

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

В частности, для локализации нулей первых производных функции, представленной в программе в виде функции пользователя Def fn f ( х ) = . , массив на входе сортировки составляется из модулей приращений этой функции на каждом шаге for i = 1 to п : с (i)=abs(fn fxO + h + i * h ) - fh f(xO + i * h ) ) : next i

Аналогично задаются ее приращения при спуске к локализованному значению. Непосредственно как разности соседних элементов массива приращения задать нельзя при используемой схеме спуска. Для вычисления нулей производных второго порядка на вход сортировки подаются модули выражений конечных разностей второго порядка через значения функции for i=l to п : c(i)=abs(fii fxO + 2* h + i * h) - 2* fh f(xO + h + i * h) + +fn f(xO + i * h) ) : next i и аналогичное выражение используется при спуске.

Собственно для самой локализации приращения можно задавать в виде разностей элементов входного массива.

Данные выражения непосредственно пригодны для вычисления нулей.

Для нахождения экстремумов производных выражения конечных разностей необходимо поделить, соответственно, ш h и

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

Схема переносится на случай частных производных функции двух переменных на основе конечно-разностных аппроксимаций этих производных.

О временной сложности вычисления экстремумов функции двух переменных при помощи сортировки. В / 34, 44 / выводятся следующие оценки времени вычисления М экстремумов рассматриваемой функции внутри квадрата со стороной О. При последовательном вычислении с сортировкой-2, 8 N В' 3 , 10§2 Л N

Ч0 A J

Л0 А Г 2 2 время существенно зависит от числа ЛЛ узлов равномерной прямоугольной сетки (РПС) на шаге "Я//" /34/, от числа экстремумов, от времени сортировки, от отношения расстояния 28 между ближайшими минимумами (максимумами) к заданной границе абсолютной погрешности го , а также от отношения О к к. Для максимально параллельной формы метода на основе сортировки-1

2 + 1ов2 г=6>(1). (1.22)

1}? Л0

В (1.22) время вычисления зависит только от отношения расстояния между экстремумами к заданной границе погрешности. Количество ПЭ процессорных элементов) равно Оценки распространяются на

1к' вычисление всех комплексных корней многочлена произвольной степени.