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

I ¡а правах рукописи

Рюмин Олег Германович РАЗРАБОТКА И ИССЛЕДОВАНИЕ АЛГОРИТМОВ РАСПОЗНАВАНИЯ

ИЗОБРАЖЕНИЙ НА ОСНОВЕ ОПРЕДЕЛЕНИЯ ЭКСТРЕМАЛЬНЫХ ПРИЗНАКОВ ЗАМКНУТЫХ КОНТУРОВ С ПОМОЩЬЮ СОРТИРОВКИ

Специальность:

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации ш соискание ученой степени кандидата технических наук

ТАГАНРОГ 2008

003457278

Работа выполнена в ГОУВПО «Таганрогский государственный педагогический институт».

Научный руководитель: доктор технических наук,

профессор Ромм Яков Евсеевич

Официальные оппоненты: доктор технических наук,

профессор Кравченко Павел Павлович

кандидат технических иаук, старший

научный сотрудник Сапрыкин Владимир Абрамович

Ведущая организация: ФГНУНИИ «СПЕЦВУЗАВТОМАТИКА»,

г. Ростов-на-Дону

Защита состоится « 26 » декабря 2008 г. в 14.20 на заседании диссертационного совета Д212.208.21 Южного федерального университета по адресу: г.Таганрог, пер. Некрасовский, 44, ауд. Д-406.

С диссертацией можно ознакомиться в Зональной научной библиотеке Южного федерального университета по адресу: 344000, г. Ростов-на-Дону, ул. Пушкинская, 148.

Автореферат разослан « 24 » ноября 2008 г.

Просим Вас прислать отзыв на автореферат, заверенный гербовой печатью учреждения, по адресу: 347928, ГСП-17А, Ростовская область, г.Таганрог, пер. Некрасовский, 44, диссертационный совет Д 212.208.21.

Ученый секретарь

диссертационного совета Д 212.208.21 доктор технических наук, профессор

Н.И. Чернов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

3. Построить структуру данных для базы эталонов и схему идентификации изображения путем последовательно!^ сравнения вектора распознавания с эталонными векторами по норме в условиях искажения контура.

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

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

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

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

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

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

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

Внедрение и использование результатов работы. Полученные в работе результаты приняты к использованию в ОАО «Таганрогский завод «Прибой» для выявления экстремумов числовых последовательностей при разработке алгоритмического обеспечения параллельной цифровой обработки гидроакустических сигналов и для разработки алгоритмического и программного обеспечения анализа гидроакустических изображений, получаемых от антенных систем высокого разрешения; в ГОУВПО «Таганрогский государственный педагогический институт» на факультете информатики в преподавании курсов «Информатика», . «Теоретические основы информатики», «Информационные технологии в математике», «Теоретические основы нейроинформатики», «Архитектура нейрокомпьютеров», «Практикум решения задач на ЭВМ», что подтверждено соответствующими актами, приведенными в приложении 8 к диссертационной работе.

Апробация работы. Основные результаты работы были представлены на I международной научно-практической конференции «Текст в системе высшего профессионального образования» (Таганрог, ТГПИ, 2003 г.); XI международной научной конференции «Математические модели физических процессов» (Таганрог, ТГПИ, 2005 г.); международной научно-практической конференции «Модернизация отечественного педагогического образования: проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г.); III всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» (Пенза, 2005 г.); Международной научно-технической конференции «Модели и алгоритмы для имитации физико-химических процессов» (Таганрог, ТГПИ, 2008 г.); IX Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2008 г.).

Публикации. По материалам работы опубликовано И печатных работ общим объемом около 7 печатных листов, в том числе 3 статьи в журналах из перечня рекомендуемых ВАК РФ.

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

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы, характеризуется современное состояние проблем распознавания и идентификации изображений, представлен краткий обзор основных схем сортировки. Формулируются цель и задачи исследования, основные положения, выносимые на защиту.

В первое* глав® рассматриваются разновидности параллельных сортировок, в частности сортировка слиянием с временной сложностью f(l)=0(Nlog2 N) в

последовательном варианте и в параллельном, а также

максимально параллельная форма сортировки подсчетом: Представлена

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

Таблица 1

. Сравнение программных реализаций методов сортировки

метод сортировки время выполнения, мс1 устойчивость взаимно однозначное соответствие входных и выходных индексов

простыми вставками2 0,451033 + -

естественным двучпугевым слиянием2 0,111332 - -

слиянием динамически* иассяаоз индексов 0,180462 + +

слиянием по матрице сравнений3 0,331945 + +

' Тип элементов - Real, Random, N = 394; оценка получена усреднением 106 шмерекий. Конфшурация оборудования: VIA VT8366/A-8233; AMD AthIon(tm) ХР I«00+ (1,41 ГГц); 2304MB RAM; ОС Microsoft Windows XP Professional SP2 3 Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск. 2-е изд.; Пер. с англ. - М.: Издательский дом «Вильяме», 2005. - 824 с. ' РоммЯ.Е. Параллельная сортираока слшнгием но матршим сравнении, I //Кнбернегяна и системный аналт, 1994, №5, С. 3-23

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

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

( 0, 1, ..., i, ..., и-П

О)

е0> е\• •••> ei> •*•» en-t )

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

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

Для /с = 1,2,...,л-2 локальные минимумы входного массива предлагается идентифицировать по индексу гк в случае ложности условия

К-фв (2)

при /=&-!, /г-2,.,.,0; локальные максимумы предлагается идеитифицировать в случае ложности условия (2) при /=/с+1, к+2,..., п-\. Условие (2) не требует проверки при к =0 и при к = п-1, поскольку первый элемент отсортированного массива - всегда глобальный минимум во входном массиве, а последний - всегда глобальный максимум. Процедурная реализация такого способа выявления экстремумов на языке Delphi имеет вид:

Лттннг /

procedure MlnAndMax{const В: array of Integer; const Kpr,: Integer); var k, 1: Integer; begin

{a [elLow (E) 11 глобальный минимум; а[е[ШдЬ( E) } ) пюОалъный максимум); for К Succ(Low(E) ) to Pred (High (E) ) do begin 1 Pred(k) ; while 1 > ■ Low(E) do begin

iï №s{e№ - CUH <« Eps then BrcsV.; Dec(l) end;

if 1 < LowtE) then begin {3[e[k]J минимум); Continue end; 1 Succ(k); while 1 <= lUgii(E) do begin if Abstelle) - e[ll) <- Eps then Break; Inc(l) end; if 1 > High(E) then fa[e[k]l максимум!; end;

end;

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

Представлены способы распараллеливания алгоритма идентификации экстремумов, вытекающие из взаимной независимости сравнений всех пар индексов по услоеию (2):

Tafjjiw/a 2

Матрица сравнений ипдсксои (МСИ)

с\ ! : :

% «ю • «20 ] «зо г i

е, «21 [ «31 i i

е2 «32 ; ; <

<h

е„\

О),

Ч»-2>1

«(„-2)3

СО,

'(»-I)!

«(„-1 )3

JV'-JV

......"2

ячеек

<0(»-l)(»-2)

(3)

где

10, если|<?(-е\>в,

к - номер столбца, I -номер строки МСИ, ¿ = 1,2,...,и-1, /-0,1,...Д-1 (по главной диагонали, состоящей из единиц, и ниже МСИ не заполняется ввиду симметрии относительно этой диагонали).

Способ идентификации экстремумов по МСИ (табл. 2) формулируется так: если и>к1 = 1, то в е-окрестности е,.-й элемент входного массива не является локальным минимумом, а е, -й - локальным максимумом.

Алгоритм, реализующий данный способ на параллельных вычислительных системах, допускает бесконфликтность при простой коммутации. В максимально параллельном варианте все ячейки МСИ на (лг2 -Ы)/2 процессорах будут заполнены за время операции сравнения (3). Это означает, что все экстремумы окажутся идентифицированными с временной сложностью г((д'2—А/)/ 2)= 0(1).

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

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

Предполагается, что замкнутый контур идентифицируемой фигуры выявлен одним из известных алгоритмов. Конкретно применяется программная реализация метода сиплексного прослеживания контура (Местецкий Л.М. Непрерывный скелет бинарного растрового изображения // Тр. межд. конф. «Графикон-98», Москва, 1998). При этом в порядке очередности точек при прослеживании формируется массив значений абсцисс

и массив значений ординат

У = (Уо, У^-, у,,-,) точек контура в декартовой системе координат (СК) ХОУ.

С целью формирования признаков выполняется радиально-круговая развертка контура изображения в полярной СК (г<р'). Именно, формируется массив

Д'= (г,\ г;,..., »■;.,) (4)

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

ф'=(<Ро-<!>'.> •••,<¡>'„-1) (5)

соответствующих им величин полярных углов. При этом используются следующие предложения:

1. Центр полярной СК связывается с точкой (рх, ру), координаты которой вычисляются как средние арифметические значения абсцисс и ординат точек контура в декартовой СК:

где N - количество точек, принадлежащих контуру (дискретизированный периметр).

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

»-I

= мах (г/). (б)

В формируемых массивах (4), (5) точке (6) соответствует последняя позиция. Номер для /-Й точки контура определяется по формуле

/'=(/+я-1-с)тос1Аг, (7)

где с - индекс из (6).

3. Элементы (5) подвергаются преобразованию поворота координат, при котором угол становится равным нулю:

9>ф!-Ч»« 1» |=0,1,...,и-1. (8)

4. Элементы (4) нормируются делением на среднее значение

ri/xà j'O /

Я

1 ■■ -•;:>■ ,v •'• *"8

ШЁШЁЁ^

1 у

-1'.

Представленные преобразования «приводят» фигуру к базовому положению в декартовой CK Х'О'Г (рис. 1).

Эксперименты показывают, что количество и положение экстремумов полярного радиуса контура, идентифицирующих изображение, :..■■.■.■••; ' у'$ устойчиво при его сдвиге, ротации и масштабировании в рассматриваемых условиях раст еризации. Преобразования (7), (9) определяют очередность нахождения экстремумов последовательности (4) и нормируют их значения относительно масштаба изображения. На этой основе набор идентифицируемых по значению и по индексу экстремумов полярного радиуса контура изображения рассматривается В Качестве ВеКТОра еГО распознавания. Рис. I Базовое положение символа "F?

Для идентификации всех экстремумов массив (4) сортируется и в результате преобразуется к виду:

= <,...,<,), (10) где г'е йг^ , i = 0,..., и - 2. Перестановка индексов элементов (4) в (10) задает массив обратных адресов Е :

£=(г0,е,, ...,е„...,), (11)

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

- Ik - е), {е, - 0M(et +1), {ек + с)], при (e<n-et )л(е<е, +1),

- Ik -<?).(** - OMk + + при (е>п-ек)л{г.<ек + l) ,

- [(и-е+еД (и-1)]и[0, {ек - l)]u[(e4 +1), (е„ + <?)], при (c<n-et )л(е>е, + О, а диапазон изменения г ограничивается значениями: =1,2,...,[_Л' /2J.

С целью корректного определения локальных экстремумов в данных условиях при произвольном задании радиуса е окрестности локализации экстремума алгоритм идентификации экстремумов на основе сортировки адаптируется на случай замкнутого контура. Для выполнения адаптации условие (2) достаточно заменить составным условием

(|«*-в,|£вМи-|е,-фв), . (12)

в остальном алгоритм идентификации экстремумов на основе условия (2) и алгоритм идентификации экстремумов замкнутого контура на основе (12) идентичны.

Программная реализация алгоритма идентификации экстремумов замкнутого контура отличается от реализации нз листинга 1 заменой пары операторов вида

i£ Abs(а(к) - е[1)) <= Eps then Break;

на соответственные операторы:

if (Abs(е[к] - <а{1}) <= Eps) or (Length(Е) - Abs(e(k] - е[1]) <= Eps) then break?

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

Имеет место

Лемма 1. Зависимость т=т(е) количества идентифицируемых в массиве (4) экстремумов имеет вид кусочно-линейной целочисленной функции, монотонно убывающей до значения т=2 на отрезке Ее[1,[_А?/2_)], где N - число элементов массива (4). При е>\и!2\ значение функции т(е) остается неизменным.

Характерный вид зависимости т(е) приведен на рис. 2.

Лемма 1 положена в основу разработки и программной реализации сходящегося итерационного алгоритма определения параметра е для каждого входного изображения. Данный алгоритм выполняет итерационное отслеживание значений функции т(е) при е=1,2,3,..., в ходе которого выявляются последовательные совпадения результатов идентификации экстремумов. Если при последовательных значениях радиусов локализации экстремумов £=»', е=/+1, е=/+2, ..., е=»+г, где геН, идентифицированные минимумы и максимумы корректно чередуются и при этом

/и(/)=ж(/+1)=от(/+2)=...=1я(;+г), (13)

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

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

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

Пусть при заданном г для массива (4) подобрано значение е, при котором в массиве (4) идентифицируется к локальных минимумов

экстремальных признаков контура фигуры.

т

70

34

1 17 37 65 124 139

Рис. 2 — Зависимость т(е) для символа "К" с рис. 1

»> ' Ж' : б>

ШрШЬ Ч —Ф^ШёЩ

ч .

Рис. 3 - Все экстрему мы молярного радиу са символа "Р** при е™ 1 (а) и отфильтрованные экстремумы при е- 17 (б)

и к локальных максимумов

г' г'..., г', ,г'

1 о' /I * ' )к-г' ./*-»

полярного радиуса, г0, »,.....¡к-г''к-1 и Уо. .......j^-2<jk-¡ - соответствующие

индексы выявленных экстремумов, при этом i0<^0<i^<jl< •••<7*-г<'4-1<Л-1 ввиду чередования локальных минимумов и локальных максимумов вдоль линии контура, ]к_1-п-\ - индекс глобального максимума. Тогда вектор распознавания входного изображения в общем виде записывается следующим образом:

у=( г! ; г'; г! ; г! ; ...; г/ ; г' ; г! ; г] ). (14)

Ниже для (14) используется обозначение

), (15)

где = < , уГ= г'о, у2'-'"= г/, ,..., уГ2= С , = г;,.,, т = 2к.

С целью идентификации входного изображения разработана структура данных и реализована иерархическая схема однопроходного поиска в базе эталонов. Множество изображений класса К', вектор распознавания (15) которых имеет размерность т, определяется как подкласс К',т класса К'. Эталонный вектор казвдого конкретного изображения формируется на основе усреднения координат векторов распознавания (15), сформированных для ряда экземпляров данного изображения. Для записи 1 -го эталонного вектора подкласса К'-"' класса Кх используется обозначение

»"'-(»;-';»."'¡у}4'; ... ¡^у;-/). (16)

Такая структура базы эталонов позволяет выполнять идентификацию изображения путем однопроходного сравнения вектора распознавания (15) с эталонными векторами соответствующего подкласса по евклидовой (в общем случае - канонической) норме. Пусть (16) - один из те-мерных эталонных векторов подкласса К'1" класса К', а (15) -т -мерный вектор распознавания идентифицируемого изображения. Тогда изображение идентифицировано, если:

т-1 . . ijh-I. ,

У -vr) = min J У (vr' -У/")

ffo 1 ' v«'gi" 11 ^ v ' '

<.тЗ

где <5Г>0 - величина допустимого покоординатного отклонения, предотвращающая

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

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

В третьей главе с целью верификации предложенного метода выполняется его экспериментальная проверка на примере распознавания сканированных символов латинского алфавита в условиях помех. Учитываются ограниченные искажения символов, а также сдвиг, ротация и масштабирование (рис. 4). Для задания искажений символы распечатывались на струйном принтере (размер символов 14 пунктов, гарнитура шрифта Times New Roman), затем сканировались с разрешением 600 dpi. В качестве масштабированных использовались символы размером 12 и 16 пунктов. Ряд Рис 4-примеры символов (13,3%) преднамеренно подвергался

рассмотренных искажении дополнительному искажению в графическом редакторе.

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

В табл. 3 приводится фрагмент базы эталонных векторов вида (16), сформированной для заглавных букв латинского алфавита. Таблица иллюстрирует наличие у таких символов, как "В", "В", "Н" и ряда других, нескольких вариантов базового положения на плоскости. Каждый из этих символов содержит несколько точек контура, которые имеют одинаковое с точкой (6) удаление от выбранного центра полярной СК. В условиях искажений в качестве максимально удаленной может определяться ка;кдая из таких точек, соответственно будет варьироваться очередность координат вектора (15). Для решения проблемы потребовалось дополнить базу эталонов вариантами векторов, соответствующими возможным базовым положениям символов. Всего для 26 символов латинского алфавита база включила 92 эталонных вектора - около трех «с половиной» векторов на символ.

Таблица 3

Фрагмент базы згалошых ешсгоров

Г"

"<(75;' 1,62; 0.02; ' Ц>4; 0,9зГ1д7; 0,73 "'Тэт" "А"'

1,04; 1,13; 0,65; 1,17; 1,00; 1,31; 0,58 1,33 "В"

0,59; 1,32; 1,02; 1,12; 0,63; 1,15; 1,01 из "В"

0,59; 1,28; 0,95; 1,11; 1,08; 1,12; 0,97 1,29 "Б"

0,95; 1,12; 1.07; 1,12; 0,96; 1,27; 0,58 1,28 "П"

0,56; 1,48; 1,16; 1,54; 0,08; 0,93; 0,27 1,82

0,88; 1,07; 0,75; 1,10; 0,20; 1,29; 1,10 1.39

0,07; 1,62; 0,87; 1,63; 0,08; 1,62; 0,87 1,64 "Н"

0,87; 1,61; 0,08; 1,62; 0,86; 1,61; 0,08 1,64 "Н"

1,40; 1,51; 0,20; 1,51; 1,40; 1,51; 0,20 1,53 "Г

0,21; 1,50; 1,38; 1,50; 0,20; 1,51; 1,41 1,53 "Г

1,05; 1,32; 0,07; 1,48; 1,39; 1,57; 0,34 1,59 "Г

0,34; 1,56; 1,00; 1,29; 0,07; 1,49; 1,41 1,58 "Л"

0,29; 1,54; 0,71; 1,57, 0,32; 1,63; 0,05 1,80 "К"

1,07; 1,64; 0,37; 1,61; 1,04; 1,74; 0,17 1,76 "М"

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

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

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

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

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

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

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

Имеет место сложным рельефом контура

Лемма 2. Совокупность МСИ, сформированных для фигуры, ограниченной N -элементным замкнутым контуром, при радиусах локализации экстремумов, последовательно принимающих значения с=1,2,...,|_Л'/2_|, представляет собой полную развертку экстремальных признаков контура, заключенных в перестановке (11).

Отличие МСИ для итерационной идентификации и фильтрации экстремумов замкнутого контура состоит в том, что сои из (3) определяется по формуле

(1\ \ ( \ ^ (0>е<ли(Ь-г/Н)Л('Чг*-ф4

Ми-К-Фе)Н, / \ / I 1 * (17)

[ \,еат\\ек-е1\<Е)^{п-\ек-е1\<Е).

Лемма 2 полагается в основу оценок временной сложности метода.

процессорах вся совокупность МСИ будет заполнена за время хю выполнения операции сравнения вида (17).

Таким образом, имеет место

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

Г((ЛТ2-ЛГ)/2х[лг/2])=0(1). (18)

На практике итерационный выбор е рационально осуществлять путем параллельного заполнения текущей МСИ (при каждом соответственном е) до тех пор, пока не будет выполнено (14) при условии корректного чередования экстремумов. Тогда для изображения, ограниченного замкнутым контуром длины N и представленного массивом вида (4), без учета времени сортировки и проверок чередования экстремумов, вектор распознавания на Л процессорах будет определяться за время

Г(Л)*(Г(ЛГ2-ЛГ)/2Л1 х(|ЛГ/2.)+т))г„, (19)

при этом значение [_Л7 2] + х является верхней границей числа итераций, определяющих скорость сходимости алгоритма. С учетом эксперимента показано, что для заданного класса изображений Т(я) из (19) целесообразно оценивать из неравенства

Г(я)* (Г(< -тО/27?] х т))Г(0, (20)

где Ncp и еч, - средние значения периметра изображений и автоматически выбираемого для них радиуса окрестности локализации, поскольку на практике еср « [Wiy) / 2_].

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

В главе дано сравнение предложенного метода с известными аналогами в аспектах временной сложности, эффективности и устойчивости распознавания. Сравнение проводилось с программными пакетами, ориентированными на распознавание печатных символов (в том числе с "ABBY FineReader 6.0", ©2002 ABBY Software House). Как видно из табл. 4, по эффективности распознавания предложенный метод сопоставим с известными. Инвариантность относительно вида изображения с замкнутым контуром, сходимость и распараллеливаемость предложенного метода, а также применимость в условиях произвольного положения и масштаба изображений составляют его положительные отличия.

Таблица 4

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

распознавание изображений параллелизм инвариантность относительно вида изображений

в произвольном ноложеии при масшта-бировани в условиях ограниченных искажений

TexlBridge Classic 1.07 >86,92%' югг данных алфавитные символы текстовых редакторов

ABBY FineReader 6.0 - >95,77%'

пррдложешныГ) метел + + 93,08 -98,65%' геометрическое место точек внутри контура

классифицирующая нейронная сеть (SFAM) - 14,6 ~96,6%2 (10000 бинарных изображений 10 типов самолетов) без оценки временной сложности изображения произвольных объектов

корреляционный алгоритм распознавания по координатам частных центров тяжести (распознавание контурного изображения при отношении сигнал/шум без оценки временной сложности зашумленные контурные изображения некоторых классов

методы стохастической геометрии (триплетпые приз1гаки) + + 100%" (35 бинарных изображений 5 разновидностей эритроцитов) без оценки временной сложности изображения объектов медицинской и технической диагносттси

использование пирамидальны* представлений обращав + + 883-98,4%* (750 полутоновых изображений 25 А&'Ь-жесгов) нет данных изображения с замкнугым контуром

1 На основе выполненных п гл. 3 экспериментов по распознаванию 26 символов латинского алфавит

1 Станкевич ЛА, Хоп Н.Д Мнвариашзюе к ориентации и масштабу распознавание визуальных образов с использованием нечеткой иойросстн // В кн.: Мтема-тческие методы распознавания образов. Н-я Всероссийская конференции: сборник доклансв. - М.: МАКС Пресс, 2007. -С. 396-399

3 Грузман И. С., (ijiKirr.ч/| IM. Алгоритм распознавания объектов, устойчиеьюк геометрическим искажениям: сленгу, масштабу, повороту II Авгометрил, 2004, №Э. - С. 46-53

* Кадыров A.A., Федотов 11.Г. Новые признаки изображений, иивэриянззнле относительно груши движений и аффинных: преобразований// Аетометрия, 1997, Мз4. - С. 05-79

1 Гвиебных С.Н., Ланге M.M. Представление полутоноош объектов с многоуровневым разрешением для ускоренного распознавание образов // В кн.: Математические методы распознавания образов. 13-я Всероссийская конференция: сборник доюгаоов. - M : МАКС Пресс, 2007. - С. 295-299

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

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

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

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

Работа содержит следующие научные результаты:

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ РАБОТЫ

1. Ромм Л.Е., Рюмин О.Г. Выделение линейных участков плоского графического изображения на основе сортировки / ТГПИ. - Таганрог, 2003. - 15 с. - Деп. в ВИНИТИ 18.06.03, №1177 -В2003. (лично автора-0,37 пл.).

2. Ромм Я.Е., Рюмин О.Г. Определение линейных участков графического изображения с учетом экстремальных элементов на основе сортировки // В кн.: Текст в системе высшего профессионального образования: Материалы 1-й международной научно-практической конференции. - Таганрог: Изд-во Таганрог, гос. пед. ин-та, 2003. - С. 191 -192. (лично автора - 0,08 п.л.).

3. Ромм Я.Е., Рюмин О.Г. Выделение линейного участка контура растрового объекта на основе сортировки / ТГПИ. - Таганрог, 2004. - 29 с. - Деп. в ВИНИТИ 03.06.2004, №943 - В2004. (лично автора - 0,81 пл.).

4. Рюмин О.Г. Построение модели плоского контурного изображения в полярной системе координат на основе сортировки // В кн.: Математические модели физических процессов: Материалы 11-й Международной научной конференции. Т.

1. Физико-математические и физико-технические модели, проблемы, технологии. -Таганрог: Изд-во Таганрог, гос. пед. ин-та, 2005, - С. 242-246.

5. Ромм Я.Е., Рюмин О.Г. Распознавание плоского контурного изображения в полярной системе координат на основе сортировки // В кн.: Модернизация отечественного педагогического образования: проблемы, подходы, решения: Сб. науч. тр. Ч. II. «Технологические основы образовательного процесса в современной высшей школе». - Таганрог: Изд-во Таганрог, гос. пед. ин-та, 2005. - С. 29-33. (лично автора - 0,1 п.л.).

6. Ромм Я.Е., Рюмин О.Г. Автоматическая идентификация плоских контурных изображений на основе сортировки / ТГПИ. - Таганрог, 2005. - 52 с. - Деп. в ВИНИТИ 10.11.2005, №1454-В2005. (лично автора - 1,22 п.л.).

7. Ромм Я.Е., Рюмин О.Г. Идентификация плоского изображения на основе сортировки // В кн.: Искусственный интеллект в XXI веке: сборник статей III Всероссийской научно-технической конференции. - Пенза, 2005. - С. 95-98. (лично автора - 0,07 п.л.).

8. Ромм Я.Е„ Рюмин О.Г. Автоматическая идентификация плоских изображений по экстремальным признакам на основе сортировки И Известия вузов. СевероКавказский регион. Технические науки. - 2006. - Приложение к № 1. - С. 37-47. (лично автора - 0,29 пл.).

9. Рюмин О.Г. Параллельная идентификация экстремумов замкнутого контура на основе сортировки с целью распознавания изображений // В кн.: Модели и алгоритмы для имитации физико-химических процессов: Материалы Международной научно-технической конференции (МАФП-2008). - Таганрог: Изд-во НП «ЦРЛ», 2008. - С. 281-286.

10. Рюмин О.Г. Выявление экстремальных признаков замкнутой числовой последовательности с целью распознавания изображений // Обозрение прикладной и промышленной математики. - 2008. - Том 15, выпуск 4. - С. 716-717.

11. Рюмин О.Г. Распараллеливаемая идентификация растеризованного изображения на основе экстремальных признаков замкнутого контура // Известия ЮФУ. Технические науки. Тематический выпуск «Актуальные проблемы производства и потребления электроэнергии». - Таганрог: Изд-во ТТИ ЮФУ, 2008. - №7 (84). -С. 59-66.

Все включенные в диссертацию результаты получены лично соискателем.

Типография ТТИ ЮФУ, ГСП 17А, г. Таганрог, ул. Энгельса, 1. Заказ №376. Тираж 100 экз.

Введение.

Глава 1. Сортировка как основа схемы распознавания плоских контурных изображений в декартовых координатах.

1.1. Сортировка посредством подсчета.

1.2. Сортировка методом слияния.

1.3. Идентификация экстремумов на основе сортировки.

1.4. Обзорное сравнение алгоритма идентификации экстремумов на основе сортировки с существующими методами поиска экстремумов.

1.5. Видоизменение алгоритма идентификации экстремумов к параллельному виду.

1.6. Фильтрация экстремальных элементов.

1.7. Формирование признаков плоских контурных изображений на основе сортировки.

Выводы.

Глава 2. Формирование векторов распознавания произвольно расположенных плоских контурных изображений.

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

2.2. Идентификация экстремумов замкнутого контура при заданном порядке обхода.

2.3. Фильтрация экстремумов, обусловленных растеризацией.

2.4. Алгоритм идентификации экстремумов контуров на растре с взаимно однозначным соответствием фигурам заданного класса.

2.5. Использование экстремальных признаков контуров фигур для построения векторов распознавания.

2.6. Инвариантность векторов распознавания изображений относительно сдвига, масштабирования и ротации.

2.7. О формировании базы эталонов и способе сравнения векторов распознавания с эталонными векторами.

Выводы.

Глава 3. Программный эксперимент по автоматической идентификации изображений.

3.1. Программный эксперимент со сканированными символами латинского алфавита.

3.2. Устойчивость алгоритма распознавания при искажении изображений.

3.3. Параллелизм алгоритма автоматического подбора радиуса окрестности локализации.

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

3.5. Сравнение предложенных схем распознавания с известными методами. 159 Выводы.

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

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

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

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

Разновидности изображений. Существующие устройства ввода, такие как сканеры, фото и видеокамеры, а также устройства вывода, такие как мониторы и принтеры, обусловливают форму представления визуальной информации в виде изображений [1]; в памяти компьютера обычно используется представление изображения в виде матрицы пикселей f(m1,m2), О < ту < Мх -1, 0 < т2 < М2 -1 (растровое изображение) [2]. В зависимости от вида элементов матрицы различают следующие разновидности изображений:

- полноцветные,

- палитровые,

- полутоновые,

- бинарные.

Элементы полноцветных изображений непосредственно хранят всю информацию о цветовых составляющих, использование таких изображений требует больших вычислительных затрат. В палитровых изображениях значение пикселей является ссылкой на ячейку карты цветов (палитру) -двумерный массив, в столбцах которого расположены интенсивности цветовых составляющих каждого цвета. Полутоновое изображение состоит из элементов, которые могут принимать одно из значений интенсивности какого-либо базового цвета. Это один из наиболее распространенных типов изображений, который применяется при исследованиях различного рода (широко используется глубина цвета 8 бит на пиксель). Диапазон значений элементов бинарного (монохромного) изображения ограничен только двумя значениями: О (фоновые точки) или 1 (точки интереса). Природа происхождения таких изображений разнообразна, часто бинарные изображения получаются в результате порогового разделения полутоновых изображений с фиксированным или адаптивным порогом (известные методы преобразования полутоновых изображений в бинарные приводятся в [3]). Количество информации при этом значительно сокращается, поэтому бинарные изображения просты в обработке, хранении и пересылке.

Методы распознавания, в зависимости от предметной области, могут получать на вход полноцветные или палитровые изображения (например, [4]). Однако полутоновые и бинарные изображения используются при распознавании наиболее часто. Если имеют значение пространственные характеристики изображенных объектов, то выбираются полутоновые изображения (например, при распознавании лица человека [5]); переход к бинарным изображениям оправдан в тех предметных областях, где анализируемые объекты являются существенно плоскими (в частности, при распознавании печатных и рукописных символов [6, 7]).

Классификация и обзор методов распознавания. Типология методов распознавания, успешно применяемых в различных областях научных исследований, подробно представлена в [8-10]; статистическая теория распознавания освещена в [11]; традиционные методы стохастической геометрии в распознавании образов приводятся в [12]; справочная информация по распознающим системам дается в [13]; общее состояние проблем распознавания изображений освещено также в [14, 15]. Классификацию методов распознавания, согласно [16], можно проиллюстрировать схемой, приведенной на рис. 1.

Классификация методов распознавания

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

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

Нелинейные методы Произвольные распределения Нелинейные функции Ф-функции

Другие методы

Корреляционный метод Нейро сетевые методы Лингвистический (структурный) метод Регрессионный метод

Рис. 1

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

Геометрические методы. Данные методы, сводящиеся к анализу расположения точек в пространстве объектов, основаны на использовании некоторой функции принадлежности (подобия) S объекта к данному классу. Функция S некоторым образом определяет меру сходства объекта с координатами .г2,.,.*■,) и эталонов множества у"'=(>'[",.,>'"')• За меру сходства принимается среднеквадратическое расстояние т т=1

Метрика d (метод измерения расстояния) в каждом отдельном случае может быть разной, однако она должна удовлетворять следующим условиям:

1. d(a,b)=d(b,a);

2. d(a,c)<d(a,b)+d(b,c);

3. d(a,b)>0, d(a,b)=0 При a=b.

Обучение в геометрических методах сводится к линейной или нелинейной деформации пространства признаков. Задачу обучения в данном подходе можно трактовать как задачу определения такой оптимальной метрики, при которой минимизировалось бы среднеквадратическое расстояние где у — i -й эталон т -го класса. Как правило, рассматривается класс метрик, описываемый формулой d(a,b)= . Требуется найти коэффициент

У„, чтобы последнее выражение стало минимальным. При этом физический смысл коэффициентов часто имеет эвристическое содержание. В общем случае такая схема распознавания весьма сложна. Как отмечается в [16], вследствие сложности вычислений геометрические методы обучения не находят широкого применения, а служат, в основном, для интерпретации других методов.

Методы статистических решений. Байесовская концепция распознавания, заимствованная из теории статистических решений, является одной из наиболее распространенных. Данная концепция может быть сформулирована следующим образом. Имеется полная группа несовместных гипотез, роль которых при распознавании выполняют образы А1,А2,.,А1,.,Ал/.

Также известны априорные распределения вероятностей этих гипотез р(а1),р(а2),.,р(ам), то есть известно, с какой вероятностью появляется л/ данный образ. Так как группа полная, то ^Р\А,)=\. Пусть в результате опыта наблюдается некоторое событие / (в данном случае в роли события выступает появление конкретной реализации объекта). Требуется определить, как изменяется вероятность появления образов после этого опыта - вероятность р(а,/Ьу), условные вероятности p(bj/at), /=1,2,.,м, /=1,2,.,J в общем случае считаются заданными.

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

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

Название метода в определенной степени связано со следующей аналогией (для простоты будем считать, что распознается два образа). Пусть объекты являются точками лу некоторого пространства X. В эти точки помещаются заряды +qJ} если объект принадлежит образу и -q., если объект принадлежит образу Функцию, описывающую распределение электростатического потенциала в таком поле, можно использовать в качестве x-xj решающего правила (пли для его построения). Если потенциал точки создаваемый находящимся в Xj единичным зарядом, равен At(jc, то общий потенциал в создаваемый п зарядами, равен g(x) где к(х,ху) 1 потенциальная функция, которая убывает с ростом евклидова расстояния между х и Xj. Чаще всего в качестве потенциальной используется функция, имеющая максимум при х=ху и монотонно убывающая до нуля при

Практическая задача заключается в разработке методов построения потенциальных функций при заданном наборе эталонов или обучающей последовательности (рис. 2). Функции при этом выбираются так, чтобы облегчить их практическое получение. Такая постановка задачи характерна для вероятностного распознавания. При детерминированном распознавании задается некоторое количество эталонов, любой новый объект требуется отнести к определенному классу (предполагается существование разделительных поверхностей). На множестве эталонов определяются потенциальные функции gt(x). Разделительная поверхность определяется из уравнений gl(x)=gJ(x), i^j. В качестве решающего правила выбирают знак разности AgiJ=gi-gJ. Если эта величина положительна, то объект относят к классу i, если отрицательна — к классу j.

Синтез потенциальной функции в процессе обучения лАЛ/^У потенциальная функция, порождаемая одиночным объектом суммарная потенциальная функция, порожденная обучающей последовательностью

Рис. 2

Разделяющие функции, как правило, полагаются линейными, квадратичными или кусочно-линейными. Соответственно различают линейное, квадратичное и кусочно-линейное распознавание. Для линейного распознавания разделяющая поверхность в общем случае может быть записана в виде g(x) = ю+ ©2*2+.+<»„*„+сол+1; процесс обучения заключается в определении коэффициентов со,.

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

Нейросетевые методы. Нейросетевыми называются методы распознавания образов, базирующиеся на применении различных типов нейронных сетей; данные методы также относятся к числу весьма распространенных [17-19,7]. При распознавании образов и изображений нейронные сети используются для извлечения ключевых характеристик или признаков заданных образов, а также для классификации самих образов и извлеченных из них характеристик.

Нейронная сеть состоит из связанных друг с другом простых элементов, называемых формальными нейронами (рис. 3).

Схематическое изображение формального нейрона

Рис.3

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

Функционирование нейрона определяется формулами:

NET=y,wixn out-f(net-в), где х, - входные сигналы, совокупность которых образует вектор .v; w, -весовые коэффициенты, совокупность которых образует вектор весов w; NET -взвешенная сумма входных сигналов (значение передается на нелинейный элемент); в - пороговый уровень данного нейрона; F - нелинейная функция, называемая функцией активации. Ниже представлены некоторые виды функции активации:

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

OUT также применяется для сетей с непрерывными сигналами, преимущество по сравнению с сигмоидой обусловлено симметричностью функции относительно точки (О, О)); - пологая ступенька

OUT=

О, NET< О, NET-Q

Q<NET<d+ А,

1, NET>Q +А

NLT функция рассчитывается легко, но имеет разрывную производную, тем самым алгоритм обучения усложняется); SOFTMAX -функция

NET оит=-,

NET, суммирование производится по всем нейронам данного слоя, при любых значениях сигналов NETt данного слоя обеспечивает сумму выходов слоя, равную единице, что позволяет трактовать ОШ\ как вероятности событий, совокупность которых образует полную группу).

Нейроны могут объединяться в сети различного вида. Самым распространенным видом сети является многослойный персептрон (рис. 4).

Схематическое изображение многослойного персептрона

Модификации многослойных машин различаются числом слоев, количеством пороговых логических блоков в каждом слое и степенью настраиваемости этих блоков для каждого слоя [21].

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

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

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

Изображение (а) и его иерархическое структурное описание (б) а) б) изображение F F b н дуга а отрезок отрезок отрезок отрезок прямой с прямойd прямойе прямойf

Рис.5

Совокупность геометрических характеристик изображения и множество правил их соединения образуют специальный язык PDL (Picture Description Language), который используется в рамках иерархического описания изображений. Его синтаксис имеет графическую интерпретацию [22], распознавание строится на ее основе.

Простейшие элементы, из которых выстраиваются слова, а затем и предложения, принято называть непроизводными элементами. Правила конструирования композиций из непроизводных элементов задаются с помощью специальных грамматик, называемых грамматиками описания изображений. Для т классов изображений V1,V2,.,V„ можно построить т соответствующих грамматик G,,G2,.,GM, таких, что цепочки, порожденные грамматикой G,, будут представлять изображения только из класса V}.

Для произвольного изображения, описываемого цепочкой X, задача распознавания сводится к ответу на вопрос: верно ли, что XeL(Gj), где у=1,2,.,/я? Алгоритм распознавания описывается в виде: XeVJ9 если XeL(Gj) и

X<£L{g). Здесь l(Gj) - язык, порожденный грамматикой G}. Самый простой способ распознавания состоит в сопоставлении входной цепочки, соответствующей распознаваемому изображению с эталоном каждого образа. Цепочка X относится к тому образу, из которого взята эталонная цепочка, наилучшим образом согласующаяся с данной. Требуется либо точное совпадение цепочки с эталоном, либо выполнение подходящего критерия согласования. Структурная синтаксическая информация при таком подходе используется не полностью, однако его отличительной чертой является простота.

Необходимо отметить, что структурный подход целесообразно применять только в том случае, когда непроизводные элементы изображений могут быть гарантированно выделены и распознаны. Данный подход успешно применяется в системах распознавания печатных и рукописных текстов [23], в том числе в системе FineReader [6] (возникающие при этом проблемы освещаются в [24, 25]). Помимо перечисленных источников, структурный метод описания и распознавания изображений рассматривается в [26].

Выделение и распознавание отдельных элементов изображения является вполне самостоятельной задачей. Например, при анализе геофизических данных (фотографических и микрографических, данных дистанционного зондирования) возникает необходимость выделения прямолинейных участков [27, 28]. В темное время суток, когда контрастность объектов на изображении существенно падает, локализация движущихся транспортных средств системами контроля трафика осуществляется по паре фар [29]. При анализе состава крови возникает необходимость подсчета красных кровяных телец — окружностей и эллипсов на изображении, поступающем с микроскопа [30]. Именно прямые линии и дуги окружностей наиболее часто требуется выделять на изображениях технического характера [31]. В связи с этим нельзя не выделить преобразование Хафа, которое широко используется при выделении комплексов характерных элементов на изображениях.

Преобразование Хафа. Преобразование Хафа (the Hough transform, НТ) [32 - 34] позволяет находить на монохромном изображении прямые, окружности, . эллипсы, а также произвольные плоские кривые, заданные параметрически.

Пусть семейство кривых на плоскости задано параметрическим уравнением F{avaz,.,an,x,y) =0, где F - некоторая функция, а1,а2,.,ап параметры семейства кривых, х,у — координаты на плоскости. Идея преобразования состоит в поиске кривых, проходящих через достаточное количество точек интереса.

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

Ключевая трудность классического варианта преобразования состоит в том, что при увеличении размерности фазового пространства лишь на единицу временная сложность преобразования возрастает на порядок, что обусловливает ограниченность области его применения. В связи с этим известны различные модификации преобразования Хафа: RHT [35 - 37], GHT [38], FHT [39], РНТ [40], HNS [41], ISHT [30]. Сравнительный обзор некоторых модификаций преобразования приводится в [42]. В [43] дано обобщение преобразования Хафа на основе аппарата функций расстояния.

Известны качественно иные подходы к задаче выделения прямых линий и дуг окружностей на изображениях [44]. Например, в [45] описан подход, позволяющий выделить прямолинейные участки, дуги окружностей и концевые точки (стрелки) на инженерных построениях. Такие подходы, наряду с преобразованием Хафа, используются в контексте перевода растровых изображений в векторную форму, в том числе для их последующего распознавания; некоторые алгоритмы распознавания основаны на совместном использовании векторной и растровой моделей - представления информации [46, 47]. Задача векторизации растровых изображений актуальна в области геоинформационных систем, систем автоматизированного проектирования [48-50].

В основе существующих методов распознавания также используются: описание изображения функцией яркости [51], локальные адаптивные элементы [52], параметрический поиск [53], локальные анизотропные признаки [54], функции расстояния [43]. Применяются: ряды Фурье [55], алгоритмы, основанные на вычислении оценок [56], алгоритмы на основе игровых решающих правил [57] и симультанная модель распознавания [58]. Вводятся и исследуются триплетные признаки изображений [59]. Для получения различных топологических характеристик (вращение, сдвиг, масштабирование) при распознавании формы и классификации бинарных изображений используется спектр лапласиана Дирихле [60] (классификация по нескольким характеристикам в данном методе осуществляется нейронной сетью с механизмом прогнозирования событий; в результате геометрические фигуры, изображенные от руки или в графическом редакторе, идентифицируются с точностью от 88.9% до 99.2%). Алгебраический подход к анализу и пониманию изображений [61] формируется на основе дескриптивных алгебр изображений (алгебраическая специфика которых определяется тем, что элементами кольца являются как модели изображений, так и операции над ними).

Существует широкий спектр алгоритмов обнаружения и распознавания лица человека. Например, по результатам программы Feret (face recognition technology) агентства DARPA и Исследовательской лаборатории армии США лучшими признаны: алгоритм Университета Южной Калифорнии [62], алгоритм университета штата Мэриленд [63], алгоритм, созданный в Media Laboratory Массачусетского технологического института [64]. Современные подходы к задаче обнаружения и распознавания лица человека описаны также в [65, 66]. На основе данных алгоритмов, а также алгоритмов идентификации личности по отпечаткам пальцев (аспекты которых рассматриваются, например, в [67, 68]) функционируют системы персональной идентификации [69], осуществляется верификация кредитных карточек и криминалистическая экспертиза [70, 83]. Высокий исследовательский интерес к данной тематике обусловливается внедрением интеллектуальных сред, распространением носимых информационных устройств, в том числе встраиваемых в предметы одежды и аксессуары [71 - 73]. Краткий обзор современного состояния технологий биоидентификации и биометрического рынка приводится в [74, 75].

Цифровая обработка изображений и анализ формы контуров. Считается, что форма контуров является наиболее стабильным признаком при яркостных искажениях, поэтому методы распознавания, основанные на анализе контурных представлений объектов, являются наиболее распространенными [76 - 80]. Поиск и распознавание в условиях перепадов яркости актуальны при обработке результатов геофизических наблюдений, в биологии и медицине, на транспорте, в аэрокосмической навигации, робототехнике и многих других областях [81, 82]. Целесообразность подхода, основанного на анализе формы контуров, подтверждается также исследованиями психологов [83,84]: для человека, при распознавании и анализе объектов на изображениях, основная информация заключена не в яркости отдельных областей, а в их очертаниях. В силу этого предложенное в работе исследование акцентируется именно на идентификации изображения по его контурному представлению.

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

Цифровая обработка изображения в широком смысле заключается в выполнении какого-либо преобразования матрицы пикселей /(т^щ), в результате которого формируется набор ее числовых характеристик или новое, обработанное изображение Ь(щ,п2), 0<л, <JV, -1, 0<n2<N2~\. Преобразование может касаться значений элементов или их координат (индексов), выполняться над матрицей в целом, группой элементов или над каждым элементом в отдельности. Различают рекурсивные и нерекурсивные методы обработки: рекурсивные методы используют результат обработки предыдущего пикселя, нерекурсивные - не используют. Помимо контрастирования, цифровая обработка изображений включает в себя: фильтрацию, деконволюцию, локально-адаптивную обработку, оптимизацию палитры изображений, их кодирование, сжатие, сегментацию, поиск и прослеживание границы изображенного объекта, его остова (скелета), векторизацию [85,86,49,50]. Области применения цифровой обработки изображений постоянно расширяются. Например, цифровая реставрация изображений представляет собой выполнение обращения искажений, внесенных в оригинал: в [87] описан метод реставрации, использующий псевдообращение матриц на основе расщепления их спектра.

В иных ситуациях изображения могут намеренно приводиться к виду, весьма далекому от естественного, однако удобному для визуальной интерпретации или машинного анализа. Многие такие операции — операции препарирования - осуществляются при помощи известных поэлементных преобразований специальных видов [83]:

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

Ь(х у)=\Ь™*' "Р11^-^05 где b(x,y) - зависящая от координат функция, именуемая характеристической, /0 — некоторое пороговое значение яркости;

- преобразование яркостного среза является обобщением пороговой обработки и позволяет выделить определенный интервал диапазона яркостей, произвести анализ отдельных объектов, различающихся именно по яркости;

- преобразование контрастного масштабирования используется для представления конкретного интервала яркостей на однородном фоне;

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

Указанные операции часто предваряют собой выделение контуров на изображении.

Задача выделения контуров. Задача выделения контуров состоит в построении границ (краев) объектов и очертаний связных областей.

Замечание. Компоненты изображения (области, геометрические объекты, отверстия в них) с математической точки зрения могут быть определены как множества точек в евклидовом пространстве, это позволяет комбинировать изображения с помощью теоретико-множественных операций, например объединения и пересечения. О связности компонентов изображения (в некоторых источниках - связанности) можно говорить исходя из определения т связной области в [88]: изображение объекта связно, если любые две точки, лежащие внутри его контура, можно соединить ломаной линией, также лежащей всеми своими точками внутри контура. Иными словами, точки бинарного изображения связны, если существует путь между ними, вдоль которого характеристическая функция ь(х,у) постоянна. В данном исследовании термин «область» применительно к изображению трактуется как его связная компонента, то есть максимальное множество связных точек.

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

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

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

Определение соседних пикселей а) б) в) г) д)

О • О ©#©••00••о

Рис. 6

Выделение (прослеживание) контуров активно используется в качестве вспомогательной компоненты схем распознавания, предваряет собой преобразование Хафа [30], выступает основой построения скелета (остова) изображений для их последующей векторизации [85, 49, 89] (считается, что методы скелетизации являются наиболее универсальным способом построения векторных моделей объектов [90]). Из контурного представления извлекаются типографические элементы шрифтов, преобразуемых к параметрической типографической форме (PTR) [91].

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

Одним из наиболее простых способов выделения контуров на полутоновых изображениях является пространственное дифференцирование функции яркости (градиентный метод) [83]. Применение лапласиана для определения краев и детекторы краев на основе градиентов описаны в [66]. В [92] для выделения контурных линий предлагается использовать иерархическую триангулированную нерегулярную сеть (HTIN). Выделение контуров бинарных изображений, основанное на преобразовании Хафа, описано в [93, 94]. Также известен алгоритм дельта-сегментации изображения [95], основанный на адаптивном изменении значения порога в зависимости от статистических характеристик яркости в скользящем окне.

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

Для следящей пары задается направление от точки объекта к точке фона. Процесс прослеживания состоит в последовательном перемещении одного конца следящей пары в новую точку, лежащую от пары слева. Это обеспечивает обход контуров таким образом, что объект оказывается слева от границы, а фон - справа. На каждом шаге прослеживания анализируется одна новая пробная точка, смежная с обеими точками пары. Пробная точка замещает соответствующую точку следящей пары. Пусть {p,q) - следящая пара точек, р = (рх,ру) - граничная точка объекта, a q = (qx,qv) - точка фона. Пробная точка r = [rx,ry) ищется следующим образом: если точки следящей пары лежат в одном столбце или в одной строке матрицы /, то новая пробная точка выбирается с координатами rx=qx + py-qyi ry = qy + qx~p/, в противном случае пробная точка имеет координаты rx=(px+qx+py-qy)/2, ry = (py+qy~ px + qx)/2 (рис. 7).

Последовательные положения следящей пары

• О О • О

• • •

• • •

• • •

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

Распознавание на основе кусочно-линейной аппроксимации контуров. Модель изображения при его распознавании (как, например, в [77, 78]) может формироваться на основе кусочно-линейной аппроксимации контуров. Согласно [96], если />={/?,}, l<i<M - множество отрезков ломаных, аппроксимирующих контуры изображения, то данное изображение можно однозначно описать взаиморасположением всех вершин {а,} относительно начала какого-либо выбранного отрезка аппроксимирующей ломаной (базового отрезка). При этом отмечается, что необходимо достижение компромисса по числу отрезков, описывающих контур. Поскольку однотипные изображения различного масштаба должны представляться близким числом отрезков, необходимо выполнять их взаимное масштабирование. Степень близости сопоставляемых изображений определяется при помощи метрики Хаусдорфа [97], при этом осуществляется перебор по всем парам отрезков ломаных в обоих изображениях с поиском минимального значения данной метрики (в силу неоднозначности выбора базового отрезка). Как следствие, наиболее сложные функции, в числе которых поиск минимумов и максимумов в массиве переменных, предлагается возлагать на аппаратный акселератор.

Распознавание на основе анализа числовых характеристик области. Ниже рассматривается набор простейших числовых характеристик объекта, представленного областью на изображении. Данные характеристики тем или иным образом используются в различных методах распознавания (например, в [98, 99]), в том числе и при классификации. Это:

- периметр,

- площадь,

- удлиненность,

- компактность.

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

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

Разновидности периметра

4-смежность 8-смежность внутренние ОООООООО ОООООООО контуры О00««««0 ooot«««o оо«#*#*о оо•••••о ОООООООО оффф®ффо офффъффо ооо####о Ottootoo оффоофоо оо#151#о ОООООООО ОООООООО оффффффо оооффффо оо©©©в< оффооф оо оофффффф оффффф4 ОООООООО оффффффф ффффффл внешние + контуры * * 4 о©фоо@оо фффффффо

Рис. 8

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

S=lftb(x,y)dxdy, где интегрирование осуществляется по всему изображению I. При наличии нескольких объектов на изображении эта формула определяет их суммарную площадь.

Геометрический центр. Геометрический центр (центр тяжести) определяется как центр масс однородной фигуры той же формы - точка, в которой можно сконцентрировать всю массу объекта без изменения его первого момента относительно любой оси. В двумерном случае первые моменты рассчитываются по формулам: х^ b(x,y)dxdy=^ xb{x,y)dxdy (относительно оси *), y\\b{x,y)dxdy=jj^yb{x,y)dxdy (относительно оси у), где (х, у) - координаты геометрического центра. Интегралы в левой части соотношений - не что иное, как площадь S\ чтобы найти величины хну, полагается, что S* 0. При переходе к дискретным бинарным изображениям интегралы становятся суммами. Например, формула для подсчета площади примет вид:

Ш|-1 ntj-l

S-EZX.

0 7=0 где btJ- значение элемента /-й строки у-го столбца матрицы бинарного изображения /.

Геометрический центр обычно используется для привязки к объекту декартовой или полярной системы координат [51] (выступает в качестве полюса радиально-круговой развертки объекта); кроме того, взаимное расположение геометрических центров определенных элементов объекта может использоваться для формирования вектора признаков [98].

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

Удлиненность. Удлиненность Е (нецентрированность, эксцентриситет) рассчитывается по формуле

Е^т20+т02+т1(т20 -т02)2 + 4mTi т20 + 1П02 -л1{т20~то2)2+4тп где дискретный центральный момент тч определяется следующим образом: х,у JeReg

- 1 V - 1 V iV (дг, ~Rcg м (х,у )eRcg

N — количество пикселей области, х и у варьируются в пределах этой области).

Компактность. Компактность С используется для характеристики формы идентифицируемого объекта; компактность определена как отношение р2 квадрата периметра к площади: С=-. Нормированная компактность S результат домножения на коэффициент —) указывает, насколько форма

4лобъекта отлична от окружности [99].

Отмеченные характеристики фигур в непрерывном случае являются величинами, инвариантными к их сдвигу, масштабированию и ротации. На практике они всегда имеют ту или иную погрешность, обусловленную ошибками аппроксимации кривых на дискретной сетке (величина ошибки зависит от формы и положения кривых и уменьшается при увеличении размера объекта по отношению к размеру ячейки сетки). В [100] было отмечено, что для некоторого непрерывного контура g(jt) и множества заданных точек у,, аппроксимирующих его на дискретной координатной сетке, практически невозможно определить ошибку аппроксимации контура по формулам максимальной, абсолютной и ср еднекв адр атической оценок: т т

Zb'-sW]2; а в [101] доказано, что ошибку дискретизации в общем случае вычислить невозможно. В свою очередь это не может не сказаться на методах, использующих такие характеристики.

Метод идентификации изображений на основе контурных функций. В методе идентификации на основе контурных функций [99] величина классификационного допуска является функцией компактности. Метод относится к классу методов геометрической корреляции [102-104], которые теоретически не зависят от формы распознаваемых объектов. Однако на практике выявлен ряд факторов, влияющих на качество идентификации. Основное затруднение состоит в том, что теоретические и практические значения компактности показывают расхождение в силу дискретности растра и последствий сглаживания изображений фильтрами нижних частот. Поэтому в [99] исследуется функциональная зависимость компактности от типа и размера рассматриваемой фигуры. В качестве параметра, выражающего зависимость компактности от размеров, предлагается использовать среднее значение радиуса контурной функции, вычисленное на отрезке [0,360°] до ее нормировки:

360 rw=l/360^V((p). Для коррекции компактности используются регрессионные

Ф=1 полиномы, вычисляемые для каждого конкретного эталона по точкам графика функции c(rw), отражающей зависимость компактности от размера.

Радиально-круговая развертка объектов. В [98] для решения задачи распознавания предлагается использовать центры тяжести отрезков контурных линий, попавших в сектор при радиально-круговой развертке объектов (частные центры тяжести). При этом полюс развертки совмещается с центром тяжести распознаваемого объекта. Такой способ развертки обеспечивает независимость размера вектора признаков от масштабных искажений и помехоустойчивость алгоритмов распознавания, по крайней мере для объектов, приведенных на рис. 9.

Пример объектов, успешно распознаваемых на основе радиально-круговой развертки

О ^

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

Выделение ключевых точек контуров бинарных изображений.

Выделение ключевых (особых) точек достаточно широко применяется в обработке и распознавании изображений различного происхождения. Например, данная задача возникает при выделении характерных особенностей рельефа местности в геоинформационных системах [105] или при переводе графических построений из растровой формы в векторную в системах автоматизированного проектирования [89]. Преобразование существующих на бумаге гарнитур шрифтов к параметрической типографической форме, как отмечалось выше, осуществляется на основе извлечения из контуров каждого символа различных типографических элементов. В числе таких элементов (рис. 10) - контрольные точки на углах, перегибах и стыках линий, а также локальные экстремумы по различным направлениям [91].

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

Выделение ключевых точек контуров с целью распознавания рассматривается в рамках дескриптивного (алгебраического) подхода распознавания изображений [56,60]. В [107] приводятся обладающие свойством параллелизма алгоритмы поиска особых точек двоичных изображений на основе аппарата клеточной логики.

Распознавание на основе сортировки. Традиционная для теоретической информатики схема исследования инициирует задачу совмещения различных тематик в контексте единого метода. Например, известны успешные попытки применения сортировки в задачах визуализации [108-110]. Поскольку применение сортировки делает информацию упорядоченной, становится

Контрольные точки различных типов

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

Попытки использования сортировки при распознавании предпринимались в [117- 120]. Ниже в п. 1.7 главы 1 рассматриваются подходы к формированию признаков изображений на основе сортировки согласно [121]. Однако в данных работах либо алгоритмы сортировки применялись в несколько вспомогательном контексте (например, сортировка традиционно используется для упорядочения эталонных образов), либо метод не был распространен на распознавание изображений инвариантно к их сдвигу, изменению масштаба и повороту. Поэтому использование сортировки как конструктивной части метода распознавания, где сортировка применялась бы для обработки именно графической информации, можно рассматривать как предмет актуального исследования.

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

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

Если требуется упорядочить записи в файле, то соответствующие поля записей, управляющие процессом сортировки, именуют ключами [112], а сортировку - сортировкой по ключу.

Известно значительное количество методов сортировки [53, 112, 115, 116, 122], классификацию основных можно проиллюстрировать схемой, приведенной на рис. 11.

Методы сортировки

Внутренние сортировки

Пирамидальная

Быстрая

Пузырьковая Корневая Подсчетом

Вставками Шелла Слиянием

Внешние сортировки

Сбалансированное двухпоточное слияние

Сбалансированное многопоточное слияние

Рис. 11

Ниже приводится краткая характеристика основных методов внутренней сортировки. При этом временная сложность сортировки измеряется количеством последовательных шагов его выполнения. В частности, временная сложность последовательной сортировки измеряется числом выполняемых сравнений. Временная сложность параллельного алгоритма всюду ниже будет оцениваться на модели неветвящихся параллельных программ без учета обмена. Точное указание временной сложности алгоритма осуществляется с помощью обозначения T{R)=kxbin, где xtm — время бинарного сравнения, к -количество последовательных сравнений, R - число используемых процессорных элементов (компараторов). Приближенное указание временной сложности осуществляется с помощью обозначения t(r)=o(/), где о(/) — 1сласс функций, растущих не быстрее / [123].

Пузырьковая сортировка (обменная сортировка с выбором) имеет временную сложность t(\)=o(n2), где n - количество сортируемых элементов. Сортировка осуществляется сравнением элементов попарно, элементы тех пар, порядок в которых нарушен, обмениваются местами.

Временная сложность сортировки вставками (включением) [124] также оценивается как r(l)=o(iV2). Сортировка осуществляется вставкой очередного элемента в нужное место уже отсортированного списка.

Сортировка Шелла [125] имеет временную сложность 7,(i)=o(jv1'5) и представляет собой многопроходную сортировку, при которой список разбивается на подсписки, каждый из которых сортируется отдельно (сортировкой вставками), на каждом проходе число подсписков уменьшается, а их длина растет (рис. 12). Таким образом, вначале устраняется общий беспорядок в массиве (сравниваются далеко отстоящие друг от друга элементы), на поздних стадиях осуществляются перестановки соседних элементов (если такие перестановки являются необходимыми).

Пример сортировки методом Шелла

Рис. 12

Корневая сортировка (поразрядная сортировка) при условии, что длина ключа невелика по сравнению с числом ключей, имеет временную сложность 7'(i)=o(jV) [124]. Список разбивается на стопки, при каждом проходе используется отдельная часть ключа. Препятствием в реализации корневой сортировки служит неэффективность по памяти. Реализация стопок массивами приводит к необходимости выделения дополнительного объема памяти под 1(W записей для числовых ключей, 26n записей для буквенных ключей. Этот объем увеличивается, если в ключ, помимо букв, входят другие символы или в буквенных ключах учитывается регистр. Кроме того, при использовании массивов требуется значительное время на копирование записей в стопки.

Пирамидальная сортировка имеет временную сложность r(l)=o(N\og2N). Сортировка осуществляется построением бинарного дерева (рис. 13), значение каждого узла в котором превышает значение потомков.

Пирамида и ее списочное представление П2)

10 ) (11

С5 J TV С8 J 6J

СО 2 J C7J Гз С4 У

12 10 11 5 9 8 6 1 2 7 3 4

1 2 3 4 5 6 7 8 9 10 11 12

Рис. 13

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

Временная сложность сортировки подсчетом [112] оценивается как t(\)=o(n2). В ходе сортировки определяются номера мест элементов множества, расстановка по которым дает упорядоченное множество.

Сортировка слиянием имеет временную сложность 2^(1 )=C>(Arlog2 iV). Процесс сортировки заключается в итеративном слиянии двух (или более) уже отсортированных списков в один отсортированный список.

Быстрая сортировка (сортировка Хоара) в наихудшем случае имеет временную сложность r(l)=o(w2), в среднем временная сложность оценивается как r(l)=0(Nlog2JV). В процессе сортировки рекурсивно выбирается элемент (называемый осевым), разбивающий список на две части (рис. 14), части соответственно состоят из элементов меньших и больших выбранного.

Пример быстрой сортировки

Исходный спиоок 6 2 4 7 1 3 8 5

Ось в ячейке 6: 5 2 4 1 3 6 8 7

Ось в ячейке 5: 3 2 4 1 5 6 8 ' 7

Ось в ячейке 3: 1 2 3 4 5 6 8 7

Ось в ячейке 1: I 1 2 3 4 5 6 8 7

Ось в ячейке 8: 1 2 3 4 5 6 7 8 |

Рис. 14

Подробное обсуждение актуальных методов последовательных сортировок приводится в работах [112,126-128]. В приложении 1 даны программные реализации некоторых основных методов сортировки на языке Delphi.

Ниже в качестве конструктивной основы будут использоваться параллельные варианты сортировок подсчетом [111] и слиянием [113, 129, 130] с временной сложностью r(yV2/2)=0(l) и T{N2jA)=o{\og2N) соответственно. Обоснование такого выбора и детализированное описание данных методов будет дано ниже в главе 1.

Среди иных известных схем параллельных сортировок можно выделить: параллельную сортировка Бэтчера [112], ее временная сложность оценивается как )=<9(log22 Af); сортировку на линейных сетях [124] с временной сложностью t(n)=0(n)\ четно-нечетную сортировку перестановками [124], временная сложность которой t(n/2)=0(n).

Современное состояние проблем параллельных сортировок также освещено в [131-134], где, в частности, приводятся схемы с временной сложностью t{n)~o{\oq.1 N).

Принцип построения параллельных схем сортировки можно пояснить на примере известной сортировки по дереву (рис. 15).

Пример распараллеливания этапа сортировки по дереву N элементов

N/2 процессоров

Каждый из текущих минимальных элементов можно найти на не более чем n/2 процессорах за время 6>(log2 n). После n просеиваний минимумов упорядоченный массив будет сформирован.

Помимо временной сложности, важным фактором при выборе определенной схемы сортировки является качество устойчивости. Согласно [112] сортировка считается устойчивой, если она обладает свойством сохранения порядка записей с одинаковыми ключами. Иными словами, очередность равных элементов входного массива, не нарушаясь в процессе сортировки, сохраняется в отсортированном массиве. К числу устойчивых относится, например, сортировка вставками, к числу неустойчивых - обменная, пирамидальная, быстрая. Существуют модификации известных неустойчивых схем сортировки, в результате которых они приобретают устойчивость и в то же время приводятся к параллельному виду [135, 136].

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

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

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

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

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

3. Построить структуру данных для базы эталонов и схему идентификации изображения путем последовательного сравнения вектора распознавания с эталонными векторами по норме в условиях искажения контура.

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

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

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

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

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

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

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

Внедрение и использование результатов работы. Полученные в работе результаты приняты к использованию в ОАО «Таганрогский завод «Прибой» для выявления экстремумов числовых последовательностей при разработке алгоритмического обеспечения параллельной цифровой обработки гидроакустических сигналов и для разработки алгоритмического и программного обеспечения анализа гидроакустических изображений, получаемых от антенных систем высокого разрешения; в ГОУВПО «Таганрогский государственный педагогический институт» на факультете информатики в преподавании курсов «Информатика», «Теоретические основы информатики», «Информационные технологии в математике», «Теоретические основы нейроинформатики», «Архитектура нейрокомпьютеров», «Практикум решения задач на ЭВМ», что подтверждено соответствующими актами, приведенными в приложении 8 к диссертационной работе.

Апробация работы. Основные результаты работы были представлены на:

- I международной научно-практической конференции «Текст в системе высшего профессионального образования» (Таганрог, ТГПИ, 2003 г.);

- XI международной научной конференции «Математические модели физических процессов» (Таганрог, ТГПИ, 2005 г.);

- международной научно-практической конференции «Модернизация отечественного педагогического образования: проблемы, подходы, решения» (Таганрог, ТГПИ, 2005 г.);

- Ш всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» (Пенза, 2005 г.);

- Международной научно-технической конференции «Модели и алгоритмы для имитации физико-химических процессов» (Таганрог, ТГПИ, 2008 г.);

- IX Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2008 г.).

Публикации. По материалам работы опубликовано 11 печатных работ общим объемом около 7 печатных листов, в том числе 3 статьи в журналах из перечня рекомендуемых ВАК РФ.

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

Выводы

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

Работа содержит следующие научные результаты.

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

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

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

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

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

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

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

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

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

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

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

Практическое использование результатов работы. Полученные в работе результаты приняты к использованию в ОАО «Таганрогский завод «Прибой» для выявления экстремумов числовых последовательностей при разработке алгоритмического обеспечения параллельной цифровой обработки гидроакустических сигналов и для разработки алгоритмического и программного обеспечения анализа гидроакустических изображений, получаемых от антенных систем высокого разрешения; в ГОУВПО «Таганрогский государственный педагогический институт» на факультете информатики в преподавании курсов «Информатика», «Теоретические основы информатики», «Информационные технологии в математике», «Теоретические основы нейроинформатики», «Архитектура нейрокомпьютеров», «Практикум решения задач на ЭВМ, что подтверждено соответствующими актами, приведенными в приложении 8 к диссертационной работе.

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

2. Сойфер В.А. Методы компьютерной обработки изображений. Изд. 2. М.: ФИЗМАТЛИТ, 2003. - 784 с.

3. Gonzalez R.С., Woods R.E. Digital image processing. MA.: Addison-Wesley, 1992.-716 p.

4. РоммЯ.Е., ГуревичМ.Ю. Применение адресной сортировки к распознаванию оптических спектров / ТГТ1И, Таганрог, 2000. 17 с. - Деп. в ВИНИТИ 13.03. 2000, № 619 -В00.

5. PentlandA., ChoudhuryT. Face recognition for smart environments // IEEE Computer, February 2000. pp. 50-55.

6. Терещенко В., Рыбкин В., ШамисА., Ян Д. Принципы распознавания рукописных текстов в системе FineReader // В кн.: Труды Ш конф. «Распознавание образов и анализ изображений: новые информационные технологии», Ч. П, Нижний Новгород, 1997. С. 310-314.

7. Lee S., Kim Y.J. Off-line Recognition of Totally Unconstrained Handwritten Numerals Using Multilayer Cluster Neural Network // Proc. Of the 12th IAPR International Conference on Pattern Recognition, Jerusalem, Israel, 1994. pp. 507-509.

8. Горелик A.JI., Скрипкин B.A. Методы распознавания. M.: Высшая школа, 1984.-219 с.

9. Ту Дж., Гонсалес Р. Принципы распознавания образов. М.: Мир, 1978. -321 с.

10. УинстонП., Искусственный интеллект: Пер. с англ. М.: Мир, 1980. — 520 с.

11. Барабаш Ю.Л. Вопросы статистической теории распознавания. // Под ред. Варского Б.В. М.: Советское радио, 1967. - 400с.

12. Федотов Н.Г. Методы стохастической геометрии в распознавании образов. М.: Радио и связь, 1990. - 299 с.

13. Васильев В.И. Распознающие системы: Справочник. Киев: Наукова думка, 1983.-230 с.

14. Путятин Е.П., Аверин С.И. Обработка изображений в робототехнике. М: Машиностроение, 1990. - 320 с.

15. Рудаков П.И., Сафонов В.И. Обработка сигналов и изображений. М.: ДИАЛОГ-МИФИ, 2000. -416 с.

16. Кузин Л.Т. Основы кибернетики. Т.2. М.: Энергия, 1979. - 584 с.

17. Головко В.А. Нейроинтеллект: Теория и применения. Книга 1. Организация и обучение нейронных сетей с прямыми и обратными связями Брест: БПИ, 1999. - 260 с.

18. KrzyzakA., DaiW., SuenC.Y. Unconstrained Handwritten Character Classification Using Modified Backpropagation Model // Proc. 1st Int. Workshop on Frontiers in Handwriting Recognition, Montreal, Canada, 1990. -pp. 155-166.

19. Jacobsen X., Zscherpel U., Perner P. A Comparison between Neural Networks and Decision Trees. Lecture Notes in Artificial Intelligence Machine Learning and Data Mining in Pattern Recognition, 1999. - pp. 144-158.

20. Kobayashi Norihiko, Iwata Akira. Multimodule neural network model for higher order association // Proc. Int. Jt. Cont. Neural Networks, Nagoya, 1993. pp. 233-236.

21. ФуК. Структурные методы в распознавании образов: Пер.с англ. М.: Мир, 1977.-320 с.

22. Славин О.А., Корольков Г.В., Болотин П.В. Методы распознавания грубых объектов // В сб. «Развитие безбумажных технологий в организациях», 1999.-С. 290-311.

23. Petrou M. Learning in Pattern Recognition. Lecture Notes in Artificial Intelligence // Machine Learning and Data Mining in Pattern Recognition, 1999. -pp. 1-12.

24. GarrisM.D. Component-Based Handprint Segmentation Using Adaptive Writing Style Model // NISTR 5843, Internal report of National Institute of Standards and Technology.

25. МацеллоВ.В. Структурный метод описания и распознавания векторизованных изображений // Теоретические и прикладные вопросы распознавания изображений: Сб. науч. тр. / Науч. совет НАН Украины по проблеме «Кибернетика». Киев, 1995. - С. 52.

26. Fitton N., Сох S. Linear Feature Extraction In Geoscientific Data // Proceedings of «Digital Image Techniques & Applications 95», Brisbane, 1995. pp. 104109.

27. YuenH., Illingworth J., Kittler J. Detecting partially occluded ellipses using the Hough transform // Image and Vision Computing, 1989, Vol. 8, No. 1. pp. 7177.

28. Walsh Daniel, Raftery Adrian Е. Accurate and Efficient Curve Detection in Images: The Importance Sampling Hough Transform // Technical Report No. 388, Department of Statistics, University of Washington, February 2001.

29. Грибов М.Г., ХачумовВ.М. Определение геометрических параметров объектов по растровым изображениям // Автометрия, 2001, №1. С. 40-49.

30. Hough P.V.C. Method and means for recognizing complex patterns. U.S. patent 3 069 654,1962.

31. Illingworth J., Kittler J., A survey of the Hough transform // Computer Vision Graphics and Image Processing, 1988, Vol. 44, No. 1. pp. 87-116.

32. Duda R.O., Hart P.E. Use of the Hough Transform To Detect Lines and Curves in Pictures // Communications of the ACM, 1972, Vol. 15, No. 1. pp. 11-15.

33. XuL., OjaE., KultanenP. A new curve detection method: Randomized Hough Transform (RHT) // Pattern Recognition Letters, 1990, Vol. 11, No. 5. pp. 331-338.

34. Kalviainen H., Hirvonen P. An extension to the randomized Hough transform exploiting connectivity // Pattern Recognition Letters, 1997, Vol. 18, No. 1. -pp. 77-85.

35. McLaughlin R. Randomized Hough Transform: Improved ellipse detection with comparison // Pattern Recognition Letters, 1998, Vol. 19, No. 3-4. pp. 299305.

36. Ballard D.H. Generalizing the Hough transform to detect arbitrary shapes // Pattern Recognition, 1991, Vol. 13, No. 2. pp. 111-122.

37. Han J.H., Koczy L.T., Poston T. Fuzzy Hough transform // Pattern Recognition Letters, 1994, Vol. 15, No. 7. pp. 649-658.

38. Kalviainen H., Hirvonen P., XuL. OjaE. Probabilistic Hough transforms -overview and comparisons // Image and Vision Computing, 1995, Vol. 13, No. 4.-pp. 239-252.

39. Samal A., Edwards J. Generalized Hough transform for natural shapes // Pattern Recognition Letters, 1997, Vol. 18, No. 5. pp. 473-480.

40. Leavers V. Which Hough transform? A survey of Hough transform methods // CVGIP Image Understanding, 1993, Vol. 58, No. 2. - pp. 250-264.

41. СемерийО.С. Построение и исследование аналитических функций расстояния и их применение для анализа и синтеза изображений. Автореферат диссертации на соискание ученой степени кандидата физико-математических наук. ТРТУ, Таганрог, 2004. - 16 с.

42. LiuW., DoriD. A protocol for performance evaluation of line detection algorithms // Machine Vision and Applications, 1997, No. 9. pp. 240-250.

43. Don D., Liang Y., Dowell J., Chai I. Sparse-pixel recognition of primitives in engineering drawings // Machine Vision and Applications, 1993, No. 6. pp. 69-82.

44. Васин Ю.Г., Лебедев Л.И. Инвариантные методы распознавания бинарных изображений //В кн.: Труды 3-й конф. «Распознавание образов и анализ изображений: новые информационные технологии», Ч. 2. Н. Новгород, 1997.-С. 120-122.

45. Nieuwenhuizen P. van, Kiewiet О., Bronsvoort W. An Integrated Line Tracking and Vectorization Algorithm // EUROGRAPHICS, 1994, Vol. 13, No. 3. pp. 349-359.

46. Wu Y. R2V Conversion: Why and How? // Geolnformatics, No. 6, Vol. 3, Sept. 2000.-pp. 28-31.

47. Корнилов В.Ю. Простое инвариантное описание изображения // Автометрия, 2000, №1. С. 104-106.

48. Koh Е., Metaxas D., Baldev N. Hierarchical shape representation using locally adaptive finite elements // Lect. Notes Comput. Sci, 1994, No. 300. pp. 441446.

49. Ахо A.B., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. -М.: Вильяме, 2000. 384 с.

50. Плеханова И.В., Финогенов Л.В., Борисова И.В., Попов П.Г. Распознавание символов на цилиндрических поверхностях методом локальных анизотропных признаков // Автометрия, 2001, №6. — С. 80-90.

51. Mills R.L. Novel method and system for pattern recognition and processing using data encoded as Fourier series in Fourier space // Engineering Applications of Artificial Intelligence, Vol. 19, Issue 2, March 2006. pp. 219234.

52. Журавлев Ю.И., Никифоров B.B. Алгоритмы распознавания, основанные на вычислении оценок // Кибернетика, 1971, №3. С. 1-11.

53. Белоусов В.А., Калядин Н.И., Шумилов Е.Е. Игровые решающие правила для отношений и распознавания конечных множеств / Москва, 1996. 16 с. - Деп. в ВИНИТИ, №333 - В96.

54. Белоусов В.А., Калядин Н.И. Обобщенная симультанная модельраспознавания изображений // В кн.: Тез. докладов Всесоюзной1конференции «Методы и средства обработки сложной графической информации». Горький, 1988. - С. 34-35.

55. Кадыров А.А., Федотов Н.Г. Новые признаки изображений, инвариантные относительно группы движений и аффинных преобразований // Автометрия, 1997, №4. С. 65-79.

56. Гуревич И.Б., Журавлев Ю.И., Сметанин Ю.Г. Дескриптивные алгебры изображений: определения и пример // Автометрия, 1999, №6. — С. 4-22.

57. Wiskott L. Face Recognition by Elastic Bunch Graph Matching // Trans. IEEE Pattern Analysis and Machine Intelligence, July 1997. pp. 1724-1733.

58. EtemadK., ChellapaR. Discriminant Analysis for Recognition of Human Face Images //J. Optical Soc. of America, pp. 1724-1733.

59. MoghaddamB., PenlandA. Probobalistic Visualrecognition for Object Recognition // Trans. IEEE Pattern analysis and Machine Intelligence, July 1997. pp. 477-500.

60. Глазунов А.С. Компьютерное распознавание человеческих лиц // Зарубежная Радиоэлектроника. Успехи современной радиоэлектроники, Москва, №8, 1997. с. 3-14.

61. Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход: Пер. с англ. -М.: Издательский дом «Вильяме», 2004. 928 с.

62. NanniL., LuminiA. Two-class fingerprint matcher // Pattern Recognition, Vol. 39, Issue 4, April 2006. pp. 714-716.

63. Nanni L., Lumini A. A novel method for fingerprint verification that approaches the problem as a two-class pattern recognition problem // Neurocomputing , Vol. 69, Issues 7-9, March 2006, pp. 846-849.

64. Choudhury T. Multimodal Person Recognition Using Unconstrained Audio and Video // Proc. 2nd Conf. Audio- and Video-Based Biometric Person Authentication, Univ. of Maryland, College Park, Md., 1999. -pp. 176-181.

65. Глазунов A.C. Автоматическое распознавание и идентификация лиц // В кн.: Труды Академии управления МВД РФ «Компьютерные технологии в криминалистике и информационная безопасность», Москва, 1997. С. 7487.

66. Weiser М. The Computer for the 21st Century // Scientific American, Mar. 1991. pp. 66-76.

67. Pentland A. Smart Rooms, Smart Clothes // Scientific American, Apr. 1996. -pp. 68-76.

68. Pentland A. Wearable Intelligence // Scientific American, Apr. 1998. pp. 9095.

69. Евангели А. Технологии биоидентификации и биометрический рынок // PC Week, 2003, №7. С. 24.

70. Евангели А. Технологии биоидентификации и биометрический рынок // PC Week, 2003, №10.-С. 26.

71. Прэтт У. Цифровая обработка изображений. Кн. 2. М.: Мир, 1982. 480 с.

72. Абламейко С.В. Лагуновский Д.М. Обработка изображений. Минск: Амалфея, 2000. 304 с.

73. Рейер И.А. Распознавание формы плоских объектов на основе гомеоморфного отображения границы //В кн.: Труды 5-й межд. конф. «Распознавание образов и анализ изображений: новые информационные технологии». Самара, 2000, Т. 2. - С. 377-381.

74. Кревецкий А.В. Распознавание трехмерных объектов по форме пространственных контуров // Автометрия, 2001, №2. С. 21-30.

75. Забияка Ю.И., Типикин А.П. Алгоритм гомеоморфного распознавания внешних контуров бинарных изображений //. Сборник материалов 5 межд. конф. «Распознавание 2001», Курск, 2001, Т.1. С. 27-29.

76. Никулин Е.А. Компьютерная геометрия и алгоритмы машинной графики. — СПб.: БХВ-Петербург, 2003. 560 с.

77. ЛевинВ.И. Автоматно-логическая модель распознавания образов // В кн.: Труды Ш Всероссийской научно-технической конференции «Искусственный интеллект в XXI веке», Пенза, 2005. — С. 98-101.

78. Сойфер В.А. Компьютерная обработка изображений. Часть 2. Методы и алгоритмы//СОЖ, 1996, №3. С. 110-121.

79. Еникеев М. Общая, социальная и юридическая психология: Учебник для вузов. СПб.: Питер, 2003. 752 с.

80. Местецкий Л.М. Скелетизация многоугольной фигуры на основе обобщенной триангуляции Делоне // Программирование, 1999, № 3. С. 16-31.

81. Ланго Д. Соболев А. Модифицированные алгоритмы Форчуна и Ли скелетизации многоугольной фигуры // В кн.: Труды межд. конф. «GraphiCon'2001», Нижний Новгород, Сентябрь 2001. С. 122-127.

82. Миронов В.Г., Немов Ю.Н. Некоторые задачи оптимизации при проектировании электронных цепей и систем // Вестник МЭИ, №3, 2000. -С. 82-87.

83. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Том 1. Москва, Ленинград: ОГИЗ, Государственное издательство технико-теоретической литературы, 1949. — 690 с.

84. RamelJ.Y., Vincent N., EmptozH. A coarse vectorization as an initial representation for the understanding of line drawing images // Graphics Recognition Algorithms and Systems. Lecture Notes in Computer Science, Vol. 1389, 1998.-pp. 48-55.

85. Новиков Ю.Л. Эффективные алгоритмы векторизации растровых изображений и их реализация в геоинформационной системе. Автореферат диссертации на соискание ученой степени кандидата технических наук. -Томск, ТГУ, 2002. 19 с.

86. ShainirA., RappoportA. Extraction of Typographic Elements from Outline Representations of Fonts // EUROGRAPHICS, 1996, Vol. 15, No. 3. pp. 259268.

87. Floriani Daniela Mirra L., PuppoE. Extracting contour lines from a hierarchical surface model // EUROGRAPHICS, 1993, Vol. 12, No. 3. - pp. 249-260.

88. Greig G. Klein F. Fast contour identification through efficient Hough transform and simplified interpretation strategy // Proceedings of the Eighth International Conference on Pattern Recognition, Paris, 1986. pp. 498-500.

89. Bonnet N. An unsupervised generalized Hough transform for natural shapes // Pattern Recognition 2002, Vol. 35, No. 5. pp. 1193-1196.

90. Гостев И.М. Об одном методе получения контуров изображений // Изв. РАН, Теория и системы управления, 2004, №3. С. 97-104.

91. Забияка Ю.И., Типикин А.П., Титов B.C. Теоретические основы быстродействующего устройства инвариантного распознавания контурных изображений//Изв. вузов, Приборостроение, 2005, №2. С. 14-18.

92. ГрузманИ.С., Никитин В.Г. Алгоритмы распознавания объектов, устойчивые к геометрическим искажениям: сдвигу, масштабу, повороту // Автометрия, 2004, №3. С. 46-53.

93. Гостев И.М. О методах повышения качества идентификации графических объектов в методах геометрической корреляции // Изв. РАН, Теория и системы управления, 2005, №3. С. 55-64.

94. Pratt W.K. Digital Image Processing. -N.Y.: J. Wiley, 1978. 750 p.

95. Bennet J.R., MacDonald J.S. On the Measurement of Curvature in a Quantized Environment // IEEE Trans. Computers, 1975, Vol. 24, No. 8. pp. 803-820.

96. Гиренко А.В., Ляшенко В.В., Машталир В.П., Путятин Е.П. Методы корреляционного обнаружения объектов. Харьков: АО "БизнесИнформ", 1996.-112 с.

97. Yang Jenn-Hwai, Yang Miin-Shen. A control chart pattern recognition system using a statistical correlation coefficient method // Computers & Industrial Engineering, Vol. 48, Issue 2, March 2005. pp. 205-221.

98. Takahashi S.5 IkedaT., Shinagawa Y., KuniiT.L. UedaM. Algorithms for Extracting Correct Critical Points and Constructing Topological Graphs from Discrete Geographical Elevation Data // Computer Graphics Forum, 1995, Vol. 14, Issue 3.-pp. 181-192.

99. Li S.Z. The role of key-points in finding contours // Lect. Notes Comput. Sci, 1994, No. 300. pp. 371-382.

100. Кумсков М.И., Голенков В.П., Акиндинов B.B. Параллельные алгоритмы поиска «особых точек» двоичных изображений //В кн.: Труды Ш конф.

101. Распознавание образов и анализ изображений: новые информационные технологии», Нижний Новгород, 1997, Ч. П. С. 177-181.

102. Stein С., Becker В., MaxN. Sorting and hardware assisted rendering for volume visualization // ACM SIGGRAPH, Symposium on Volume Visualization, 1994. -pp. 83-90.

103. Snyder J., Lengyel J. Visibility Sorting and Compositing Without Splitting for Image Layer Decomposition//Proc. SIGGRAPH, 1998. pp. 219-230.

104. CombaJ., Klosowski J.T., Max N„ Mitchell J.S.B., SilvaC.T., Williams P.L. Fast Polyhedral Cell Sorting for Interactive Rendering of Unstructured Grids // EUROGRAPHICS, 1999, Vol. 18, No. 3. pp. 369-376.

105. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки. Диссертация на соискание ученой степени доктора технических наук. Таганрог, ТРТУ, 1998. - 546 с. - ВНТИ Центр, № 05.990.001006.

106. Кнут Д. Искусство программирования. ТомЗ. Сортировка и поиск. 2-е изд.: Пер. с англ. -М.: Издательский дом «Вильяме», 2005. 824 с.

107. Ромм Я.Е. Параллельная сортировка слиянием. Приложение к вычислению нулей, экстремумов функций и распознаванию образов. Таганрог: Изд-во ТГПИ, 1998. - 190 с.

108. Цейтлин Г.Е. Распараллеливание алгоритмов сортировки // Кибернетика, 1989, № 6. С. 67-74.

109. Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. - 360 с.

110. Лорин Г. Сортировка и системы сортировки. М.: Наука, 1983. - 384 с.

111. Цейтлин Г.Е. Алгоритмы адаптивной сортировки и их классификация. 4.2 // Проблемы управления и информатики 1995, № 3. С. 95-103.

112. Цейтлин Г.Е. Введение в алгоритмику. Киев: Сфера, 1998. 473 с.

113. Яценко Е.А., МохницаА.С. Инструментальные средства конструирования синтаксически правильных параллельных алгоритмов и программ // Проблемы программирования, 2004, № 2-3. С. 444-450.

114. Гуревич М.Ю. Алгоритмические схемы распознавания изображений двумерных объектов на основе адресных сортировок. Автореферат диссертации на соискание ученой степени кандидата технических наук. — Таганрог, ТГГ1И, 2001. 22 с.

115. Ромм Я.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. П // Кибернетика и системный анализ, 2001, № 5. С. 81-101.

116. Климова JI.M. Pascal 7.0. Практическое программирование. Решение типовых задач. М.: КУДИЦ-ОБРАЗ, 2000. - 528 с.

117. Кнут Д. Искусство программирования. Том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. М.: Издательский дом «Вильяме», 2005. - 720 с.

118. Макконнелл Дж. Анализ алгоритмов. Вводный курс. М.: Техносфера, 2002.-304 с.

119. Shell D.L. A High-Speed Sorting Procedure // Communications of the ACM, Vol. 2, No. 7, 1959. pp. 30-32.

120. Biedl Th., Chan Т., Demaine E.D., Fleischer R., Golin M., King J.A., Munro J.I. Fun-Sort or the chaos of unordered binary search // Discrete Applied Mathematics, Vol. 144, Issue 3, 2004. - pp. 231-236.

121. Gerbessiotis A.V., Siniolakis C.J. Probabilistic integer sorting // Information Processing Letters, Vol. 90, Issue 4, 2004. pp. 187-193.

122. Sanguthevar Rajasekaran, Sandeep Sen. A generalization of the 0-1 principle for sorting//Information Processing Letters, Vol. 94, Issue 1, 2005. P. 43-47.

123. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. I // Кибернетика и системный анализ, 1994, № 5. С. 3-23.

124. Ромм Я.Е. Параллельная сортировка слиянием по матрицам сравнений. П И Кибернетика и системный анализ, 1995, № 4. С. 13-37.

125. GasarchW., GolubE., Kruskal С. Constant time parallel sorting: an empirical view // Journal of Computer and System Sciences, Vol. 67, Issue 1, 2003. pp. 63-91.

126. NardelliE., Proietti G. Efficient unbalanced merge-sort // Information Sciences, Vol. 176, Issue 10, 2006. pp. 1321-1337.

127. Seiferas J. Networks for sorting multitonic sequences // Journal of Parallel and Distributed Computing, Vol. 65, Issue 12, 2005. pp. 1601-1606.

128. TaniarD., Rahayu J.W. Parallel database sorting // Information Sciences, Vol. 146, Issues 1-4, 2002. pp. 171-219.

129. Ромм Я.Е., Виноградский B.B. Преобразование сортировок в форму устойчивых схем со свойствами прямой и обратной адресности / ТГПИ, Таганрог, 2003. 43 с. - Деп. в ВИНИТИ 8. 12. 2003, № 2130 - В2003.

130. Ромм Я.Е., Виноградский В.В. Преобразование сортировок к устойчивойлформе без перемещения элементов и параллельное видоизменение сортировки Хоара / ТГПИ, Таганрог, 2004. 44 с. - Деп. в ВИНИТИ 17.06.2004, № 1020 -В2004.

131. Вельтмандер П.В. Машинная графика: Учебное пособие в 3-х книгах. Книга 2. Основные алгоритмы компьютерной графики. Новосибирск: НГУ, 1997. - 197 с.

132. Ромм Я.Е. Метод вычисления нулей и экстремумов функций на основе сортировки с приложением к поиску и распознаванию. I // Кибернетика и системный анализ, 2001, № 4. С. 142-159.

133. PannyW., PredingerH. Bottom-up mergesort a detailed analysis // Algorithmica, 1995, Vol. 14, No 4. - pp. 340-354.

134. Ромм Я.Е., Рюмин О.Г. Автоматическая идентификация плоских контурных изображений на основе сортировки / ТГПИ, Таганрог, 2005. -52 с. Деп. в ВИНИТИ 10.11.2005, №1454-В2005.

135. Ромм Я.Е., Белоконова С.С. Схема поиска на основе сортировки и локализации экстремальных элементов. / ТГПИ. Таганрог, 2003. - 31 с. Деп. В ВИНИТИ 12.03.2003, № 436 - В2003.

136. Половинкин А.И., Попов В.В. Техническое творчество: теория, методология, практика. Энциклопедический словарь-справочник М.: НПО «Информ-система», 1995. - 408 с.

137. Барладян Б.Х., Галактионов В.А., Зуева Е.Ю., КугушевЕ.И. Параметрические модели трехмерных объектов и их использование для реконструкции сцен// Открытые системы, 1995, №5. С. 13-16.

138. Аттетков А.В. Методы оптимизации. Учебн. для студ. втузов. — М.: изд. МГТУ им. Н.Э. Баумана, 2003. 439с.

139. Харчистов Б.Ф. Методы оптимизации. Таганрог: Изд-во ТРТУ, 2004. -140 с.

140. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988.-552 с.

141. Самарский А.А. Введение в численные методы. М.: Наука, 1987. - 288 с.

142. Шуп Т. Решение инженерных задач на ЭВМ. М.: Мир, 1982. - 240 с.

143. Тихонов А.Н., Костомаров Д.П., Вводные лекции по прикладной математике. -М.: Наука, 1984. 192 с.

144. Бахвалов С., Жидков Н., Кобельков Г. Численные методы. — М.: Лаборатория Базовых Знаний, 2001. 632 с.

145. БерезинИ.С., Жидков Н.П. Методы вычислений. Т. 2. М.: Государственное издательство физико-математической литературы, 1962. - 640 с.

146. ВлахИ., Сингхал К. Машинные методы анализа и проектирования электрических схем: Пер. с англ. М.: Радио и связь, 1988. - 559 с.

147. Галеев Э.М., Тихомиров В.Н. Оптимизация: теория, примеры, задачи. -М.: Эдигориал УРСС, 2000. 320 с.

148. Амосов А.А., Дубинский Ю.А., Копчёнова Н.В. Вычислительные методы для инженеров. М.: Высшая школа, 1994. - 544 с.

149. Банди Б. Методы оптимизации. Вводный курс: Пер. с англ. — М.: Радио и связь, 1988. 128 с.

150. Вержбицкий В.М. Основы численных методов. М.: Высшая школа, 2002. - 848 с.

151. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2004. - 608 с.

152. Воуег V., Bourdin J.J. Fast Lines: a Span by Span Method // EUROGRAPHICS, 1999, Vol. 18, No. 3. pp. 377-384.

153. Ромм Я.Е., Кузнецов С.Н. Идентификация геометрических образов с помощью сортировки / ТГПИ, Таганрог. 34 с. - Деп. в ВИНИТИ 16.01.1996, № 185-В96.

154. РоммЯ.Е., Рюмин О.Г. Выделение линейного участка контура растрового объекта на основе сортировки / ТГПИ, Таганрог, 2004. 29 с. - Деп. в ВИНИТИ 03.06.2004, №943 -В2004.

155. РоммЯ.Е., Рюмин О.Г. Идентификация плоского изображения на основе сортировки // В кн.: Труды Ш Всероссийской научно-технической конференции «Искусственный интеллект в XXI веке», Пенза, 2005. С. 9598.

156. Ромм Я.Е., Рюмин О.Г. Автоматическая идентификация плоских контурных изображений на основе сортировки / ТГПИ, Таганрог, 2005. — 52 с. Деп. в ВИНИТИ 10.11.2005, №1454-В2005.

157. Вишняков Ю.М., Кодачигов В.И., Родзин С.И. Учебно-методическое пособие для самостоятельной работы по курсам «Системы искусственного интеллекта», «Методы распознавания образов». Таганрог: Изд-во ТРТУ, 1999.-132 С.

158. Броневич А.Г., Каркшценко А.Н. Обобщения понятия статистического класса и меры возможностного включения // Автоматика и телемеханика, 1997, №6. С. 84-94.

159. Лепский А.Е., Броневич А.Г. Математические методы распознавания образов. Курс лекций. Таганрог: Изд-во ТТИ ЮФУ, 2007. - 142 с.

160. Каркшценко А.Н., Лепский А.Е. Об устойчивости центра масс, векторов и дескриптора Фурье векторного представления контура изображения // Автоматика и телемеханика, 2001, №3. С. 141-151.

161. Лепский А.Е. Вероятностные и возможностные модели описания неопределенности в задачах обработки и анализа изображений. Автореферат диссертации на соискание ученой степени доктора физико-математических наук. Таганрог, ТТИ ЮФУ, 2008. — 32 с.