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

На правах рукописи

Ромм Леонард Яковлевич

ЦЕЛОЧИСЛЕННАЯ ИДЕНТИФИКАЦИЯ ПЛОСКИХ ИЗОБРАЖЕНИИ С УЧЕТОМ МНОЖЕСТВА ВНУТРИКОНТУРНЫХ ТОЧЕК НА ОСНОВЕ ЭКСТРЕМАЛЬНЫХ ПРИЗНАКОВ И АЛГОРИТМОВ

СОРТИРОВКИ

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

18ІШЯ

005531645

Таганрог-2013

005531645

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

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

доктор технических наук, профессор Витиска Николай Иванович

Официальные оппоненты:

Доктор технических наук, профессор Турулин Игорь Ильич, ФГАОУ ВПО «ЮФУ», профессор кафедры АСНИиЭ

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

кандидат технических наук, старший научный сотрудник, заместитель главного конструктора по направлению ОАО «НКБ ВС»

Ведущая организация: ФГАНУ НИИ «Спецвузавтоматика», г. Росгов-

. на-Дону.

Защита состоится <$>9 г. в 14.20 на заседании диссертационного совета

Д 212.208.21 Южного федерального университета по адресу: 347928, г. Таганрог, пер. Некрасовский, 44, ауд. Д- 406.

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

Автореферат разослан « ^ » С/ЮлЯ 2013 г.

Ученый секретарь диссертационного совета доктор технических наук

Боженюк А.В.

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

Актуальность темы. Распознавание, классификация и идентификация изображений -. актуальное направление исследований в теоретической и прикладной информатике, их результаты находят применение во многих научных, технических, промышленных областях, в компьютерных и производственных технологиях. Известные подходы опираются на модели нейронных сетей, Марковских случайных процессов, на генетические и эволюционные алгоритмы, теоретико-множественные методы задания метрических пространств и методы цифровой обработки сигналов на базе ортогональных разложений. Каждый из известных методов существенно продвинут, как правило, в специализированном применении: удается классифицировать изображения астрономических наблюдений, спутниковых снимков, результаты компьютерной томографии, геологической разведки, биометрических данных, графические особенности научных экспериментов и электрокардиограмм, выполнять распознавание полутоновых изображений и сканированных текстов, выделять целевые объекты в условиях помех. Вместе с тем не решены некоторые проблемы математического и алгоритмического характера. Сюда можно отнести выбор и определение меры сходства и различия с эталоном, достоверность и интерпретацию вероятностной оценки результатов распознавания, вопросы сходимости и скорости сходимости к идентификаторам целевого объекта. Быстродействие и точность идентификации являются объективными требованиями, предъявляемыми к распознающим системам. В то же время, обработка изображений сопряжена со значительным объемом вычислений, как правило, в условиях искажения поступающей информации. Кроме того искажение элементов входного изображения возникает в процессе обработки, в том числе при фильтрации на основе ортогональных разложений. Неизбежны погрешности преобразований координат и масштабирования, вычислительных алгоритмов метода распознавания. Затруднения возникают при выборе собственно метода распознавания и эталонных последовательностей. Существующие схемы иногда характеризуются вычислительной сложностью, ориентированы на определенный класс изображений, не отличаются эффективностью при изменении положения изображения на плоскости или изменении масштаба. Погрешность при сравнении полученных в результате обработки изображения признаков с эталонными влечет неточность распознавания. Это неизбежное следствие применения для обработки изображения сложных математических функций в арифметике с плавающей точкой. Для минимизации погрешности в большинстве случаев на практике используется обработка собственно входного изображения. Производится повторная выборка, чтобы убедиться, что координатная система изображения верна; выполняется удаление шума для фильтрации искажений, вносимых считывающим устройством; производится модификация контрастности; реализуется масштабирование для лучшего различения структур на изображении; выполняется выделение деталей: линий, границ контура и кромок. Локализуются «точки интереса»: углы, капли, точки. Более сложные детали могут относиться к структуре, форме или движению. Выполняется детектирование/сегментация: на определенном этапе обработки принимается решение о том, какие точки или участки изображения являются важными для дальнейшей обработки.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическое использование результатов работы. Результаты диссертации используются:

1. В ООО «Конструкторское бюро морской электроники «Вектор» при выполнении поисковой научно-исследовательской работы по теме «Проведение проблемно-ориентированных исследований в области создания эффективных систем обработки сигналов и изображений в реальном времени».

2. В работах по выполнению государственного задания Министерства образования и науки РФ ФГБОУВПО «ТГПИ имени А.П.Чехова» по проекту №7.1398.2011 «Распараллеливаемые компьютерные методы вычисления функций, решения и анализа устойчивости дифференциальных уравнений, цифровой обработки сигналов и распознавания изображений с применением алгоритмов сортировки», а также в работах по грантам РФФИ «Численная оптимизация на основе сортировки с приложением к анализу устойчивости, поиску и распознаванию» в 2010 г. (проект № 10-07-00178-а) и «Компьютерные методы численной оптимизации на основе сортировки с приложением к анализу устойчивости, разностно-полиномиальному решению дифференциальных уравнений, распознаванию изображений и цифровой обработке сигналов» на 2012-2013 г г. (проект № 12-07-00143-а).

3. В учебном процессе кафедры информатики ФГБОУ ВПО «ТГПИ имени А.П. Чехова» в курсах «Информатика», «Дополнительные главы информатики», «Программирование», «Основы искусственного интеллекта», «Компьютерное моделирование», «Алгоритмы параллельных и последовательных сортировок».

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

- Международной научно-технической конференции "Модели и алгоритмы для имитации физико-химических процессов" МАФП' 2008 (2008, Таганрог)

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

- XV всероссийской школе-коллоквиуме по стохастическим методам. IX Всероссийском симпозиуме по прикладной и промышленной математике (2009, Санкт-Петербург)

- X Всероссийском симпозиуме по прикладной и промышленной математике (2009, Сочи)

- XII Всероссийском симпозиуме по прикладной и промышленной математике (2011, Казань)

Публикации. По материалам работы опубликовано 13 печатных работ с общим объемом 11.45 печатных листов, в том числе 5 статей в реферируемых журналах из списка ВАК.

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

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

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

сти и взаимно однозначного соответствия входных и выходных индексов сортируемых элементов. Многопутевое слияние (от-слияние) применяется к т упорядоченным по отношению 2 одномерным массивам («отрезкам») и преобразует их в единый упорядоченный массив из яхт элементов. В результате т -слияния сохраняется взаимный порядок равных элементов, порядок положения отрезков для слияния задается априори. В главе приводится общий вид МС для слияния произвольных отрезков, который ниже поясняет

Пример 1. Выполняется 3-слияние отрезков (1,2), (2, 5), (4, б). Набор МС®, элемента которых имеют знак «+», если элемент столбца больше элемента строки, «-», - если меньше, и «О», если равен ему, примет вид:

-оо 1 2 оо -ОО 2 5 оо -«0 4 6

-<ю 0 + + + 0 + +

1 мгоо 1 - + + + М С<12> 1 + + +

2 2 - 0 + + 2 + + +

ас оо - - - 0 - 0

-<ю 2 до ? 4 л

-00 и + + * -00 -00 0 + + +

2 - - 0 + МС64 2 МС®> 2 - + + +

5 - - + 5 5 - - + +

<* 0 « - - - 0

** 1 2 со 2 5 ао -оо 4 6 оо

-X 0 + + + -00 0 + + + -оо

4 - + МС"" 4 - + + МС™ 4

6 - - + 6 - - + 6

оо - 0 ос - - - 0 оо

МС"»

Непосредственным подсчетом из вида МС(1Л получаются адреса вставки элементов отрюзка (1,2): 1-й +0 + 0 = 1, 2->2 + 0 + 0 = 2,

"Г I /о Уо к, >■ Уо Уо к,

Аналогично, из МС(2Л получаются вставки элементов (2,5):

2-^1+2 + 0 = 3 «Р I Л Уо к,

5->2 + 2+1-5

"Г е Л Л к,

Из МС® выполняется вставка элементов отрезка (4,6):

4->1+2 + 1

Л Л к,

6-»2 + 2+2 = 6 а? I Л Л к,

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

Пример 2. Для 2-слияния отрезков (1, 2), (2, 5) набор МС имеет вид:

мс<">

МС™

-оо _0__+

_2__-__^

3 -

МС™

МС114

Вставки можно получить из единственной (с учетом симметрии) МС справа вверху:

¿1=1-» «1+0 =ci. Ьг = 2~* с2+0=с2,а,= 2-> си2 = с,, аг=5-> с2,2 = с4.

Пусть по отношешпо < требуется упорядочить массив -V- целая степень числа т, т >2.

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

N

Шаг 1. Массив с сохранением порядка элементов разбивается на — групп по т элемент

тов. По всем группам и всем элементам групп выполняется параллельное т -слияние в каждой

группе. Роль сливаемых отрезков длины и = 1 играют элементы группы. Результат шага — — от-

т

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

Шаг ¡¿2. Пусть в результате (r-I)-ro шага получены -^-г слитых отрезков, каждый длит

N N

ны л = т' . Эти отрезки в порядке их расположения слева направо делятся на —г групп. По —г

т' т

группам и по всем элементам групп выполняется параллельное т -слияние отрезков в каждой

г. N I

группе. Результат шага--г слитых отрезков длины тп= т , располагаемых слева направо в пот'

рядке взаимного расположения исходных на данном шаге групп сливаемых отрезков. На шаге i = log т N сортировка будет закончена.

Количество процессоров на i'-м шаге сортировки: Д = —(m2-m)x(mM)2x — или

2 т'

Отсюда максимальное Д = ^.У2. Временная сложность сортировки состав-

= log„ N х, где т - время бинарного сравнения. Отсюда

Т * j .V2 j = О (log m n) . Параллельная сортировка подсчетом на основе матриц сравнения является частным случаем сортировки m -слиянием при m-N, i = logA. N = 1 , n = N'~' =1. На единственном шаге этой сортировки сравниваются отрезки длины 1, то есть сами элементы массива. Пример 3. МС для сортировки массива а = (7, 5, 7, 3, 4) имеет вид:

7 5 7 3 4

7 0 - 0 - -

5 + 0 + - -

7 0 - 0 - -

3 + + + 0 +

4 + + + - 0

Номер j-го элемента входного массива а в отсортированном массиве с подсчитывается как число нулей и плюсов в j-м столбце МС над диагональю, включая диагональный элемент, сложенное с числом плюсов под диагональю (нумерация от У=1). Например, а[2] = 5 -> 0 + 1 + 0 + 1 + 1 = 3 —► е[з]. Ядро последовательной процедуры, в дальнейшем именуемой sort сводится к циклическим операторам:

forj:=l to n do begin k:" 0;

fori:=l 10 j do if а()]>=а[П then k:-k+l; for i:=j+l to n do if a[j]>a[i] thenk:=k+l;

c[k]~a[j]; e[k]:=j; end;

С учетом симметрии противоположных знаков относительно нулевой диагонали в ^ МС четыре общих правила вставки для сортировки N -слиянием (подсчетом) имеют следующую интерпретацию:.

Правило 1. В МС для сортировки подсчетом элемент о,, расположенный по горизонтали над у-м столбцом, на выходе сортировки имеет номер, который равен сумме числа "нулей" и "плюсов" в j -м столбце выше диагонали, а также на диагонали, сложенную с числом "минусов" в j -й строке справа от диагонали, j = 1,2,..., N.

Правило 2. В МС для той же сортировки элемент о,- на выходе сортировки имеет номер, который равен сумме числа "нулей" и "плюсов" в j -м столбце выше диагонали, а также на диагонали, сложенную с числом "плюсов" J-го столбца ниже диагонали, j = 1,2,..., N.

Правило 3. В МС для той же сортировки элемент а, на выходе сортировки имеет номер, который равен сумме числа "минусов" и "нулей" в j-й строке до диагонали, а также на диагонали, сложенную с числом "минусов" j -й строки справа от диагонали, / ¿= 1, 2-... ,N.

Правило 4. В МС для той же сортировки элемент на выходе сортировки имеет номер, который равен сумме числа "минусов" и "нулей" в j -й строке до диагонали, а также на диагонали, сложенную с числом "плюсов" у-го столбца ниже диагонали, j = 1,2.....N.

Теорема 1. Без учета длительности обмена параллельная сортировка т -слиянием массива

из N элементов, - N — целая степень числа т, т> 2, на = процессорах выполнима с

длительностью, logm Л^ последовательных сравнений: Г j~І0§N Х' ШІИ'

~p"jw2j = o(log„ Jv).' Сортировка выполняется по обобщешшм правилам вставки, инвариантным относительно т.

Следствие 1. В условиях теоремы 1 при т-2, - Д = -і-Л'2, rQ-jV2 j= log, Л'т, или,

=C(log2 N). Таким образом, параллельная сортировка т -слиянием переходит в обычную

параллельную сортировку слиянием с логарифмической временной сложностью. При этом ее последовательный вариант выполняется за время Г (l )=JVlog2 N х, или, Т{\)=0(Nlog2 N).

Следствие 2. В условиях теоремы 1 при m = А' получается R = > временная слож-

ность Т (л) =1 logv N т , поэтому = mm,-rQ-JVJj=o(l). Таким образом, параллельная

сортировка m -слиянием переходит в параллельную сортировку подсчетом с единичной оценкой временной сложности.

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

Сортировки устойчивы и устанавливают взаимно однозначное соответствие входных и выходных индексов. В частности, операторы c[k]:-a(j]; e[k].-j; в цикле for j:=l to П do процедуры sort каждому входному индексу j сопоставляют единственный индекс к, и каждому выходному индек-

V

су t — единственный входной индекс j: e[k]:=j. Входные индексы на выходе сортировки ^ располагаются в порядке отсортированных элементов.

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

Л = («о. «1. •••."„.,) (1)

после выполнения сортировки sort принимают вид-

С = (с0,с,.....с,.,), с,йсм, 0 ii £п-2. (2)

Взаимно однозначное соответствие индексов из (1), (2) образует подстановку:

О, 1, ..., i..... л-Р,

(3)

'в, е

Перестановка входных и выходных индексов (нижний ряд (3)) задается массивом адресов Е:

£=(«o.«i.....e»-i)- - (4)

Порядок индексов е. совпадает с порядком отсортированных элементов с,. Взаимосвязь (1) - (4) позволяет использовать массив Е и перестановку (4) для получения различных признаковых характеристик изображения, представленного входным массивом координат. В частности, массив Е определяет количество и положение локально экстремальных элементов массива А при произвольно заданном радиусе окрестности локализации е , где е - натуральное число. Конкретно, локальный минимум массива А вциклепо к, 0 £ £ < п-1, определяется тем, что условие \et_,-<?t jse не должно выполняться ни при одном I из неравенства 1 <£<к. Аналогично, локальный максимум в цикле по индексу к, 0 < к s л-1, определяется тем, что условие |et -et+,[<£ не должно выполняться ни при одном ( из неравенства 1 < i < .

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

Программная реализация идентификации экстремумов имеет вид (с - eps): {sort(n,a,c,e),} k:-l; while k <= n do begin for r=l to k-1 do if abs(e[k]-e[k-r]) <- eps {forr=l to k-1 do if abs(e[k]-e[k-r]) > =1} {for r:=l to n - k do if abs(e[k]-e[k+r]) <- eps} {for r:=l to n-k do if abs(e[k]-e[k+r]) > =1} then goto 11; ik~ e[k]; ll:k:=k+l end;

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

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

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

ионического (в первоначальном варианте) расположения в декартовых координатах. Точки контура нумеруются по ходу считывания сверху вниз, слева направо (рис. 1), расстояние И между вертикалями пропорционально максимальному по горизонтали расстоянию О между точками контура, на рис. 1 й = £>/16. В порядке нумерации сортируются ординаты точек. В результате входные индексы образуют перестановку.

■ : Л К, ,

! l]tr

■ fililí Mi i

Рис. I Нумерация входных точек контура в канонических декартовых координатах

В данном примере для эллипса-

(16,14,18,12,20,10,22,8,24,6,26,4,28,2,30,0,31,1,29,3,27,5,25,7,23,9,21,11,19,13,17,15) и для тупоугольного равнобедренного треугольника -

(0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,31,1,29,3,27,5,25,7,23,9,21,11,19,13,17,15). В первой последовательности на четных местах - элементы арифметической прогрессии с разностью - 2 до значения 0, на нечетных - с разностью 2 до значения 30. Затем, от середины, на четных - арифметическая прогрессия с разностью 2 до значения 17, на нечетных - с разностью -2 до значения 15. Во второй последовательности прогрессия с разностью 2 в последовательности номеров до значения 30, а далее чередуются элементы убывающей прогрессии с разностью -2, и возрастающей - с разностью 2. Таким образом, данные перестановки из натуральных чисел характерны для двух фигур и различают их между собой. В третьей главе будут раскрыты экстремальные особенности данных закономерностей, а в гл. 1 даны дополнительные примеры с преобразованием перестановок и подстановок. Например, конечные разности элементов перестановки для эллипса: (-2,4,-6,8,-10,10,12,...), а для треугольника- (2,2,2,2,2,...).

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

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

В заключение гл. 1 представлено обзорное сравнение идентификации экстремумов на основе сортировки с известными методами поиска экстремумов.

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

некоторой начальной точки экрана до первой встречи вдоль вертикали с точкой контура, после чего выполняется возврат в начальную точку с последующим сдвигом на один пиксель по горизонтали и, соответственно, возобновляется по вертикали (аналогично, для трех других считываний). Процесс продолжается до некоторой фиксированной конечной точки экрана. Начальная и конечная точка выбираются так, чтобы заведомо охватить изображение. К выходу процедуры sort подсоединяются операторы идентификации глобальных экстремумов: {sort(n,a,c,e);} k:=l; while k <= n do begin for r~l to k-1 do if abs(e[k]-e[k-r]) > =1 (forn=l ton-kdoifabs(e[k]-e[k+r])>=l} then goto ll;ik:=e[k]; 11: k:=k+l end;

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

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

(г,<р): х=гсо&р, у- rsm<p , г = ijx1 + уг , tg <р = — . Центр полярной системы предварительно

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

1 "j- 1 —

*/„=— Е хи ,У/„Е y,j,j-1,4, где j - номер набора считанных координат, xjsr - среднее

арифметическое значение всех считанных абсцисс точек контура фигуры j -го набора, yt - среднее арифметическое всех считанных ординат этого набора в декартовой системе, я, - количество элементов данного набора, х,7, ytJ - абсциссы и ординаты i-й точки набора. Центр полярной системы окончательно вычисляются усреднением по четырем наборам: 1 4 1 4

x,r = ~ У. х,„, У ¡г = — Е >',' ■ В каждом из наборов в порядке считывания составляются длины ра-

4 у = 1 4 у = I

диусов ;-й точки, образуя массив с индексом i: гДг] = -*„)2 + (.yij-y„Y , j = ¡74. Сортировкой радиусов sort с обратной адресацией к входным индексам определяется максимальный радиус и его декартовы координаты хгт„ и угаю. Поворот декартовой системы координат выполняется следующим образом. Ось абсцисс новой системы направляется вдоль максимального радиуса. Вычисляется угол а между старой и новой осью абсцисс: tga = (>V,mx-y,r)Kxrma -x,r)', « = arctg(tga). Далее, вьшолняется имитация поворота фигуры, которая

позволяет, не меняя характеристик текущего изображения, моделировать изменение его положения на плоскости:

x' = (>-xjr)cosa+0>--jv)sma , / = -(*-x„.)sma + (y-.j>,)cosa. (5)

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

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

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

Здесь Гга„,, Yr!a:i2 - идентификаторы значений глобальных максимумов, полученных при первом и втором считываниях соответственно, /,„„,, {тхг - идентификаторы их индексов, другие идентификаторы имеют аналогичные определения. Для выявления пропорций между полученными соотношениями из них составляются дроби, умноженные на 10 с округлением до целого:

D^lloirf.+ll/t/j+lJJ.D^llO^tll/Vj+llJiDj.tlolj,,.!)/^,«));

D, -[ 10 U +1)/ (js +|) ]; D, - [ 10 (/!, +))/ (d, +l) j; D, = [ 10 ¿/„-и)/ (J, n) j; (7)

D, -[ ЮЦ.+l) ];D, =[ 10ff. +l)/ (j, +l) ); Ds =[ 10 (j,+l)/ (j,0 tl) j.

Сдвиг числителя и знаменателя на единицу выполнен, чтобы избежать деления на ноль. Совокупность этих выражений образует искомый вспомогательный вектор: D[l], D[2],..., D[9]. Необходимо отметить, что эти данные, а также приводимые ниже условные операторы составлены исключительно для априори заданного конечного множества распознаваемых фигур некоторого класса (полный набор множеств распознаваемых изображений в рамках программного эксперимента дан в приложении к гл. 2). Согласно эксперименту элемент dl0 из (6) обнаруживает устойчивость без дополнительных преобразований, поэтому используется в исходном виде в качестве компонента Di ■ Д™ распознавания фигур другого класса или другого множества условные операторы пришлось бы составлять заново в соответствии с новым множеством и классом изображений.

Путем преобразований вспомогательного вектора с использованием выражений отношения строится идентифицирующий вектор. Его элементы ниже представлены массивом: Dl[l], DJ[2],.,., Dl[9], для которого в качестве примера приводятся условия формирования координат для приведенного в приложении к главе множества из 16 фигур с учетом искажений:

if (Dili- tO)or(D[l]»9) then Dl[t]:-I; ifDIIj-0ihenDl[!]:-2;

if (D[l] = 20)and(D[3J> 20)thcn D1I3):-1;

if {Dil] = 0)and(D[3J=0 then DI[3]:=2;

if (D[2] - D[3])or(abt(D[2]-D(3|)- 2)tfienDI[2}:-1,

if(D[2J<20)and(Dt2]>9)thenDI{2]:=2:

•f (D[2]<300)aod(D(2]>l70)ihen DI(2]:-3;

<f<D[2i-D[3|-l0)or(D{2]-D[3}-lI)tJienDlI3J:-3;

if(D[41<1000)and(D(4J> 100)Икп DI[4]:= 1;

if(Dl4I>1200)Bnd(Di4)<2000)ibsnDl[dl:-2;if(D[4]>2000)lhenDl[4J:-3;

¡f(Dl4J>20}end{D[41<30)ihcnDl[41:-2;

if (D[5]s0) theo D1[5J:-1:

if((DI5]<-10)or(D[5I>700)and(DtSI<ZCKKi)X(iinDl|5I:-2;

if(D[6]-0)th«nDU6l:-l;

if ab^DJ6])-4 Iben Dl[6J:-2:

¡f(DI7J>-l0IHt)and(D[7J<-!30)i]iCnDlI7|:-li

if(DI2)>-90)and(D[7]<-80)then Dl[7];=2;

if(DI7]>-IO)and(D[7]<ö)thcnDII71:-3:

if (DI8I > 20) and (DIU] - 100) then D1[8J :-

if (D|8] >- 10) and (Dfil <- 20) then DI[8| :- 2;

if (D[8] > 80) and (D{81 < 700) Ihcn Dl[8] :- 3;

if D[9] " 1 dien Dl(9] I;

if D|9] - 9 ihcn Dl[9} -- 2:

if DI9] - D[8] then D119} 3;

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

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

Пример 4. Требуется идентифицировать равносторонние треугольники при наличии искажений: •

Рис. 2 Идентифицируемые искажения равностороннего треугольника

Идентифицирующие векторы 01 для неискаженного равностороннего треугольника: 01 = (1,1,0,1,1,1,0,1,0); 01 = (1,2,0,1,1,0,1,2,2) (соответственно повороту по — и против часовой стрелке). В случае искажения одной из сторон идентифицирующий вектор, учитывающий направление поворота по часовой стрелке, примет вид: О! =(2,3,0,0,2,1,0,1,0). Изменились первый, второй, четвертый и пятый из элементов. Вектор, учитывающий направление поворота против часовой стрелки, остается неизменным: 01 =(1,2,0,1,1,0,1,2,2). Согласно эксперименту при различных искажениях контура фигуры (рис. 2) идентифицирующий вектор, полученный для искаженного варианта, либо сохраняет неизменность (Б1 =(2,3,0,ОД, 1,0,1,0)), либо при некоторых направлениях поворота искаженной фигуры вновь преобразуется в исходный вектор (Ш = (1,1,0,1,1,1,0,1,0)). Таким образом, идентифицирующие векторы в данном примере сохраняют устойчивость при наличии существенных искажений.

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

Пример 5. Для восьмиконечной звезды (рис. 3) с разрывами в контуре идентифицирующие векторы

Рис. 3 Восьмиконечная звезда с разрывами в контуре (с учетом двух направлений угла поворота): 01 =(2,0,0,0,0,0,0,2,0); Б1 = (1,2,0,0,0,0,0,2,0). Несмотря на разрывы контура, векторы идентификации не изменяются и совпадают с эталонным для неискаженного варианта фигуры. Это происходит потому, что разрывы контура сравнительно невелики, не изменяют класс фигуры, кроме того, независимо от направления считывания, среди координат, соответствующих внутренней части разрыва, при данном способе считывания не обнаруживается экстремальных элементов, превосходящих по значению глобально максимальный (минимальный элемент), соответствующий неискаженному контуру. В целом устойчивость распознавания и идентификации на изложенной основе объясняется тем, что по каждому из четырех взаимно ортогональных направлений считывания выбирается глобальный экстремум, при котором фильт-

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

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

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

Рис. 4 Различные положения изображения рукописной буквы «В» в квадрате до и после поворота

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

Способ считывания множества внутриконтурных точек фигуры сохраняет название «сквоз-I ное считывание», основан на подходе из гл. 1, но применяется к фигуре в новых декартовых координатах после преобразования изображения в каноническое положение. Считывание производится непосредственно с загружаемого в программу графического изображения, абсциссе начальной | точки присваивается нулевое значение, ординате - числовое значение размера изображения по ( вертикали. Вертикаль (в новых координатах), вдоль которой производится считывание, ортого-: нальна оси ОХ, сдвиг вертикали при выполнении обхода происходит вдоль ОХ. Порядок обхода: : снизу вверх, слева направо - с параметрическим заданием шага вдоль оси абсцисс и отдельно шага вдоль оси ординат. В порядке обхода с данным выбором шагов последовательно считываются все точки внутри фигуры, вся информация по ходу считывания заносится в два одномерных массива ! соответственно абсциссам и ординатам.

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

В главе доказана

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

|> Е, С = 1,2,...,*-1. .. (8)

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

\ер-ер*г | > £> 1 = 1.2,■.-.,»-/>. (9)

Из (8), (9) вытекает

Следствие 3. В условиях теоремы 1 наибольшее значение £„ радиуса локализации минимума в окрестности зафиксированного индекса ек определяется из соотношения:

Етах = тах е : | - ек_( | > е, г = 1,2,...,*-1.

Наибольшее значение радиуса локализации максимума в окрестности зафиксированного индекса е* -

= тах е: | et -| > е, 6 = 1,2.....п-к.

Следствие 4. Если соседние индексы перестановки (1) различаются на ±1 (V, = .,-<у = ±1), то первый из индексов не является индексом максимума, второй - индексом минимума ни при каком значении радиуса локализации. Если V1 ¿у = ± е, то первый из ин-

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

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

У,. К. У,)-

Первым элементом Г, идентифицирующего вектора в соответствии со следствием 4 является число одинаковых по абсолютной величине разностей между предыдущим и текущим входными индексами ординат для е= ±1. Вторым и третьим элементами У2 и V, являются общее количество найденных локальных максимумов и минимумов входных ординат соответственно порядку считывания. Четвертым и пятым элементами являются общее число найденных локально максимальных и минимальных элементов последовательности входных индексов отсортированных ординат.

Пример 5. Построить идентифицирующий вектор внутриконтурной части фигуры на рис. 5:

Рис. 5 Рукописная буква «а» Рис. 6 Правильные многоугольники

внутри квадрата в квадратном контуре

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

Таблица 1

Результаты программного преобразования подстановок индексов

2 4 8 1« и 1$ и 25 26 43 49 І0 51 .4

за 44 44 50 11 - к ¿4 11 2» 49 - 1 16 1»

-и « ... -2 •1» 13 -4 -23 4* 19 49 а д,

-1 -1 •1 1 -4 32 ... | и -11 1» -11 •2* •19 19 •18 і» д'"

В первой строке таблицы располагаются порядковые номера элементов трех других строк: ік, Ду, Л® • Во второй строке в порядке нумерации располагаются переставленные входные индексы отсортированных ординат фигуры. В третьей - разность между переставленным входным индексом и его порядковым номером. В четвертой - разность между предыдущим и текущим переставленными в результате сортировки индексами. Элементом V, идентифицирующего вектора является число одинаковых разностей из 4-й строки, в данном случае равных -1, что иллюстрирует количество монотонных участков последовательности внутренних точек изображения. Вторым и третьим элементами Уг, V, являются общее число найденных локальных максимумов и минимумов ординат соответственно. Четвертым и пятым элементами являются общее число найденных локально максимальных и минимальных элементов последовательности переставленных в результате сортировки индексов ординат. В итоге идентифицирующий вектор данного на рис. 5 изображения имеет вид: (Л = (7,4,3,6,6).

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

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

А„г , г = 1,2,.... от„, (10)

а последовательность соответственных ординат -

Гкг , г = 1,2.....т„

(И)

Согласно специфике алгоритма идентификации максимально (минимально) экстремальных элементов последовательности на основе сортировки элементы (11) располагаются в порядке неубывания:

, г = 1,2.....тя-1. (12)

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

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

Г,г, г = 1,2,..., ж., <?,<<?„, . г = 1,2.....т,-1. (13)

Чтобы сформировать искомую новую последовательность, остается элементы подпоследовательности (13) перенумеровать по порядку-

У„ г = 1,2,...,«„. (14)

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

Данные преобразования позволяют получить признаковые характеристики наиболее характерных в смысле экстремальных особенностей частей изображения. Полученная последовательность (14) подвергается обработке согласно следствию 4, по аналогии с примером 5 для этой последовательности строится компонента У, идентифицирующего вектора. В программном эксперименте остальные координаты сохраняют ранее изложенный смысл и способ построения. Для определенности, радиус локализации в данных примерах равен 5, как в случае локализации собственно ординат, так и в случае локализации их индексов, для входной последовательности и ее преобразования (14): ере = 5, ерз1 = 5.

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

Таблиид 2

Последовательность (14) и результаты программного преобразования . подстановок индексов применительно к изображению на рис. 6

Для образования первого компонента учитывается только количество ± 1 четвертой строки, в данном случае У1 = 22. Общее количество локально максимальных элементов исходной последовательности ординат (в порядке сквозного считывания) в данном случае У2 =31, общее количество ее локально минимальных ординат У} = 34. Общее число локально максимальных элементов среди переставленных поете сортировки входных индексов последовательности К4 = 28, общее число локально минимальных ординат среди них И5 = 25. ■ Таким образом, V = (^1 У,, У*. 22, 31, 34, 28, 25 ).

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

Пример 7. Требуется идентифицировать внутриконгурную часть изображения на рис. 7.

а) 6)

Рис. 7 Идентифицируемая внутриконгурнах часть со стилизованной буквой «Г» внутри правильных многоугольников без искажения и с искажением

Идентифицирующий вектор внугриконтурной части изображения на рис. Т\ V = (31,53,53,37,38) В случае искажения (рис. 7Ч) - ^ = (29,51,51,35,33). Значения компонентов вектора с первого по четвертый изменились на число 2, пятый компонет - на значение 5. Данные изменения позволяют формализовать идентификацию, использовав заданную область значений для изменяющихся компонентов. .

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

Предельная устойчивость признаков изображения достигается посредством варьируемого подбора радиусов окрестности локализации экстремумов входной и преобразованной последовательности (14) множества внутриконтурных точек изображения. В главе приводится результат работы программы, полностью данной в приложении, при расширенных радиусах окрестности локализации экстремумов исходной последовательности ординат и (14), ерз = 15, ерэ1 = 50, соответственно. Для фигуры на рис. 7"' значения локально экстремальных ординат после проведения фильтрации (14): минимумы - 90, индекс 9; максимумы - 250, индекс 4; разность индексов соседних минимумов -9; разность индексов соседних максимумов -4. Эта же комбинация в точности повторилась для искаженного изображения (рис. 7Ч). Результаты работы программы по индексам (9, 4, -9, -4) совпали для неискаженного и искаженного изображения за счет фильтрации промежуточных между экстремумами точек при достаточном увеличении радиуса локализации экстремумов входной последовательности и существенно большем его увеличении для (14). Та же программа для фигуры на рис. 8а)

а) б)

Рис. 8 Стилизованная буква лр» в пятиугольнике внутри квадрата

выдает результат - минимумы: 102, индекс: 6; максимумы: 250, индекс: 1; разность индексов соседних минимумов: -6; разность индексов соседних максимумов: -1. Комбинация в точности повторяется для искаженного изображения (рис. 8б)). Таким образом, для пары изображений на рис. 8 получается комбинация индексов: (б, 1, -6, -1). Принципиально, что совпадая для изображений однотипных фигур, эти результаты различаются для изображений фигур различных типов.

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

Т1ап ы =С>('). гДе Р ~ размер в пикселях диагонали экрана, Я - параметрический шаг,

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

Метод построения целочисленных идентифицирующих векторов целесообразно применить для организации поиска изображений, когда подрисуночные надписи неизвестны или ими нельзя воспользоваться в силу их условности и семантического несоответствия. Пусть задано изображение, по которому требуется выполнить поиск аналога в некоторой базе, содержащей конечное множество изображений. Изображение-маска обрабатывается согласно изложенному методу, формируется целочисленный идентифицирующий вектор. Например, для внутриконтурной части изображения на рис. 7а): К = (31,53,53,37,38). Полученный вектор принимается за эталонный на время поиска. Затем каждое изображение базы аналогично обрабатывается с целью получения идентифицирующего вектора. Идентифицирующий вектор текущего изображения рассматриваемой выборки сравнивается с эталонным. Если имеет место покомпонентное совпадение, то изображение запоминается как элемент списка выдачи. Если в дальнейших выборках обнаруживается аналогичное покомпонентное совпадение для какого-либо другого изображения базы, то это изображение также включается в список выдачи, при последующих выборках в список включаются все изображения, имеющие такой же идентифицирующий вектор. В список выдачи, помимо изображений с идентифицирующим вектором, равным эталонному вектору, включаются также те изображения базы, которые имеют идентифицирующие векторы с близкими по значению компонентами. Например, рис. 7б), для которого вектор К=(29,51,51,35,33) отличается от эталонного на две единицы в четырех подряд компонентах, также включается в список. Помимо критерия малости целочисленного отклонения для формирования списка выдачи могут использоваться более сложные логические условия. В результате формируется список выдачи, в который входят изображения, совпадающие с маской (если таковые находятся в исследуемом множестве), и те, которые имеют сходство при незначительном отклонении. Совпадение идентифицирующих векторов ещё не-означает тождественного совпадения изображений: они могут различаться в промежуточных между шагами считывания точках, а в более общем случае - если координаты их точек одинаково упорядочиваются после сортировки, но не совпадают между собой по значениям. Список выдачи оказывается достаточно компактным, поскольку изображения, не обладающие достаточным сходством, не имеют сравнительно близких компонентов идентифицирующих векторов. Компактность возрастет с ростом устойчивости идентифицирующих векторов, в частности, при использовании вариации радиуса окрестности локализации экстремумов, описанной на примере рис. 7,8.

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

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

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

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

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

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

Полный список научно новых результатов приведен в начале автореферата. ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК

1. Ромм Л.Я., Ромм Я.Е. Целочисленная идентификация плоских контурных изображений на основе экстремальных признаков // «Известия вузов. Северо-Кавказский регион. Технические науки», раздел «Управление, вычислительная техника и информатика». - 2008. - №4. - С. 18-24.

2. Ромм ЛЯ. Метод распознавания плоских контурных изображений на основе сортировки и подстановки индексов // Обозрите прикладной и промышленной математики. - Т. 16. - Вып.З. - 2009. - С. 474 - 475 (XV Всероссийская школа-коллоквиум по стохастическим методам. IX Всероссийский симпозиум по прикладной и промышлешгой математике, 19-24 мая 2009, Санкт-Петербург).

3. Ромм Л.Я. Методы распознавания плоских контурных и внугрикошурных изображений на основе сортировки экстремальных признаков и подстановки индексов // Известия ЮФУ. Технические науки. Актуальные проблемы производства и потребления электроэнергии. - Технологический институт Южного федерального университета. Таганрог. - 2009. - Ks 5. - С. 23 - 30.

4. Ромм Л.Я. Метод распознавания плоских виутрикоитурных изображений с использованием сквозного считывания // Обозрение прикладной и промышленной математики. - Т. 16. - Вып.6. -2009. - С. 1112 - 1113 (X Всероссийский симпозиум по прикладной и промышленной математике 1-8 октября 2009, Сочи).

5. Ромм Л.Я. Распараллеливаемая целочисленная идентификация растровых изображений // Обозрение прикладной и промышленной математики. - Т. 18. - Вып.6. - 2011. - С. 140-141 (XII Всероссийский симпозиум по прикладной и промышленной математике, 1-8 мая 2011, Казань).

Публикации в других изданиях

6. Ромм Л.Я., Ромм Я.Е. Целочисленная векторная идентификация плоских изображений в каноническом положении на основе экстремальных признаков контура / ТГПИ - Таганрог 2007 -37 с. Дел. в ВИНИТИ 29.01.07, № 74 - В2007. ' '

7. Ромм Л.Я., Ромм Я.Е. Целочисленная векторная идентификация произвольно расположенных плоских изображений на основе экстремальных признаков контуров / ТГПИ - Таганрог 2007 -50 с. Деп. в ВИНИТИ 31.08.07, № 856-В2007. '

8. Ромм Л.Я., Ромм Я.Е Целочисленная идентификация плоских контурных изображений с учетом поворота, масштаба и искажений на основе экстремальных признаков / ТГПИ - Таганрог 2008 -58 с. Деп. в ВИНИТИ 28.01.08, № 54-В2008. '

9. Ромм Л.Я. Метод распознавания плоских изображений на основе сортировки и подстановок индексов / В кн.: Сборник научных трудов Международной научно-технической конференции «Модели и алгоритмы для имитации физико-химических процессов» МАФГГ 2008 ( 8 09 08 - 12 09 081 /Таганрог.-2008.-С. 255-259.

10. Ромм Л.Я. Идентификация графических изображений с использованием экстремальных признаков контура / В кн.: 4-я Международная научно-практическая конференция Методология и практика образовательных технологий в условиях модернизации образования (29 сентября - 1 октября 2008 г., Таганрог), Таганрог, Издательский центр ТГПИ, 2008. - С. 106 - 108.

11. Ромм ЛЯ. Распознавание изображений на плоскости с помощью сортировки и подстановок индексов / Сборник трудов пятьдесят второй научной студенческой конференции ТГПИ (есгест-

венные науки). - Издательский центр ГОУВПО «Таганрогский государственный педагогический институт». Таганрог. -2009. - С. 79 - 80.

12. Ромм Л.Я., Ромм Я.Е. Распознавание плоских изображений на основе сортировки с фильтрацией неэкстремальных координат / ТГГТИ. - Таганрог, 2010. - 53 с. Деп. в ВИНИТИ 15 02 10 № 63 -В2010.

13. Ромм Л.Я. Распознавание внутрикоіпурной части плоских изображений путем сквозного считывания и фильтрации координат с применением сортировки / Збірник тез наукових доповідей студентів Бердянського державного педагогічного університету на Днях науки 13 травня 2010 ро-ку-Т.З. — 2010,- С. 15-17.

Личный вклад автора в работах, опубликованных в соавторстве: [1] - разработка метода, синтез алгоритма выделения экстремальных признаков контура изображения; [6 - 8] - синтез алгоритма, разработка и отладка программ построения идентифицирующих векторов с целыми компонентами для контурно представленных изображений с произвольным положением на плоскости; [12] - разработка метода, синтез алгоритма, построение и отладка программ выделения вложенных экстремальных признаков множества внутриконтурных точек изображения для его устойчивой целочисленной идентификации с учетом искажений при произвольном положении на плоскости.

Типогр. ИПК ЮФУ Заказ №//<?тир./Я%кз.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «ТАГАНРОГСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ

имени А.П. Чехова»

На правах рукописи

Ромм Леонард Яковлевич

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

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

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

Диссертация на соискание ученой степени . кандидата технических наук

'м* 00

О м

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

^ ^ профессор Витиска Н.И.

^ СГ)

О ° СМ ^

Таганрог - 2013

ОГЛАВЛЕНИЕ

Введение.....................................................................................6

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

1.1. Определение и свойства матрицы сравнений...................................26

1.2. Последовательное 2-слияние по матрицам сравнений........................29

1.3. Модификация сортировок слиянием и подсчетом на основе многопутевого слияния...................................................................31

1.3.1. Временная сложность га-слияния...............................................35

1.3.2. Слияние двух одномерных массивов как частный случай га-слияния....................................................................................35

1.3.3. Параллельная сортировка га-путевым слиянием на основе матриц сравнения....................................................................................37

1.3.4. Временная сложность параллельной сортировки га-слиянием на основе матриц сравнения..........................................................................38

1.3.5. Параллельная сортировка подсчетом на основе матриц сравнения......39

1.3.6. Временная сложность параллельной модификации сортировки подсчетом....................................................................................42

1.4. Идентификация экстремальных элементов числовой последовательности на основе сортировки..........................................46

1.5. Сравнение идентификации экстремумов на основе сортировки

с существующими методами............................................................51

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

на основе сортировки.....................................................................53

1.6.1. Предварительные примеры идентификации элементарных геометрических фигур с помощью подстановок.......................................55

1.7. Выводы.................................................................................62

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

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

2.1.1. Схема считывания декартовых координат точек контура..................63

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

в полярные...................................................................................64

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

плоских изображений.....................................................................67

2.1.4. Принцип формирования целочисленных компонентов векторных идентификаторов...........................................................................69

2.2. Формирование вспомогательного и идентифицирующего векторов......70

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

2.3.1. Устойчивость идентифицирующего вектора относительно поворота изображения.................................................................................74

2.3.2. Устойчивость идентифицирующего вектора к искажениям

и разрывам контура фигуры.............................................................75

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

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

2.5. Частные случаи схемы идентификации..........................................84

2.6. Выводы.................................................................................86

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

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

3.1. Метод программной реализации инвариантности поворота и сдвига

относительно начального положения обрабатываемого изображения.........88

3.1.1. Метод сквозного считывания....................................................93

3.2. Распознавание и идентификация внутриконтурной части изображения .......................................................................................................95

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

3.2.2. Построение идентифицирующего вектора без фильтрации последовательности исходных координат............................................98

3.2.3. Целочисленная идентификация рукописных символов на основе сортировки и подстановки индексов...................................................99

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

3.3. Фильтрация исходной последовательности координат на основе локализации экстремальных элементов при помощи сортировки.............109

3.3.1. Примеры идентификации множества внутриконтурных точек фигур

с учетом фильтрации координат......................................................110

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

3.3.3. О достижимости предельной устойчивости целочисленной идентификации изображений при вариации радиуса локализации экстремумов входной и отфильтрованной последовательности подмножества внутренних точек......................................................124

3.4. Полная оценка временной сложности параллельной идентификации фигуры......................................................................................126

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

и натуральных идентификаторов.....................................................129

3.6. Применение параллельной целочисленной идентификации для поиска изображений...............................................................................133

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

3.8. Выводы................................................................................138

Заключение...............................................................................141

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

Приложение..............................................................................157

Приложение к главе 1..................................................................158

Приложение к главе 2..................................................................161

Приложение к главе 3..................................................................189

Приложение 4............................................................................223

Введение

Распознавание, классификация и идентификация изображений - одно из наиболее актуальных направлений исследования теоретической информатики. Тематика распознавания имеет приложения во многих областях научных, технических, промышленных исследований, а также в области компьютерных и производственных технологий. Быстродействие и точность идентификации являются важнейшими требованиями, предъявляемыми к распознающим системам. В то же время, обработка изображений сопряжена со значительным объемом вычислений, как правило, в условиях искажения поступающей информации. Методы распознавания, в зависимости от предметной области, могут получать на вход полноцветные или палитровые изображения [1, 2]. Однако полутоновые и бинарные изображения используются в практике распознавания наиболее часто. Если имеют значение пространственные характеристики изображенных объектов, то выбираются полутоновые изображения, - например, при распознавании лица человека [3]. Переход к бинарным изображениям оправдан в тех предметных областях, где анализируемые объекты являются существенно плоскими, в частности, при распознавании печатных и рукописных символов [4, 5].

Обзор методов распознавания изображений. Типология методов распознавания успешно применяемых в различных областях научных исследований подробно представлена в [6-8]; статистическая теория распознавания освещена в [9]; справочная информация по распознающим системам приводится в [10]; общее состояние проблем распознавания изображений освещено также в [11 - 13].

Геометрические методы [13]. Данные методы, суть которых состоит в анализе расположения точек в пространстве, основаны на использовании некоторой функции подобия £ объекта объектам данного класса. Эта функция определяет меру сходства объекта Ъ с координатами х=(х1,х2,...,хп) и эталонов множества У = (у™, У™, • • •, У™) • За меру сходства принимается средне-

квадратическое расстояние

М т = 1

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

1. с1(а,Ь)=с1(Ь,а)',

2. с1(а,с)<с1(а,Ь)+с1(Ь,с);

3. ¿¿{а,Ь)>0, ¿¡(а,Ь)=0 при а = Ь.

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

( \ 1 мп,мт / \

где ут - i -й эталон т -го класса. Рассматривается класс метрик, описывае-

Гй ~

мый формулой с/(а,Ь)= ¡¿соал-Ьп) . Требуется найти такой коэффициент

V л=1

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

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

Байесовский подход к классификации основан на теореме, утверждаю-

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

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

Пусть х - множество описаний объектов, у - множество номеров (или наименований) классов. На множестве пар «объект, класс» X х У определена вероятностная мера Р. Имеется конечная обучающая выборка независимых наблюдений Хт = {(х1,у1),...,(хт,ут)}, полученных согласно вероятностной мере Р.

Задача классификации заключается в том, чтобы построить алгоритм а : X-» У, способный классифицировать произвольный объект х& X.

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

Построение классификатора при известных плотностях классов.

Пусть для каждого класса у е У известна априорная вероятность Р того, что появится объект класса У, и плотности распределения Р (х) каждого

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

чение функционалу среднего риска.

Средний риск определяется как математическое ожидание ошибки:

yeYseY

где "к - цена ошибки или штраф за отнесение объекта класса Y к какому-

либо другому классу.

Решением этой задачи является алгоритм а(х) = arg тахХ Рр (х)

уеУ У

Значение Р{у\х) = РуР (х) интерпретируется как апостериорная вероятность того, что объект х принадлежит классу Y.

Если классы равнозначны, X Ру = const(>>), то объект х просто относится к классу с наибольшим значением плотности распределения в точке х.

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

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

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

Параметрическое восстановление плотности при предположении, что плотности нормальные (гауссовские), приводит к нормальному дискрими-нантному анализу и линейному дискриминанту Фишера [15].

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

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

способом восстановления плотностей.

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

Метод дискриминантных функций [15]. Распознаваемый объект представляется в виде п -мерного вектора значений, характеризующих этот объект признаков. Такой вектор определяет точку в п -мерном пространстве. Предполагается, что объекты одного образа группируются в соседних точках пространства и составляют некоторую область в пространстве. Если теперь некоторыми поверхностями разделить области, соответствующие разным образам, то задача распознавания неизвестного объекта сводится к определению области, в которую попадает точка, соответствующая объекту.

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

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

и

довательности. Функции при этом выбираются так, чтобы облегчить их практическое получение. Такая постановка задачи характерна для вероятностного распознавания. При детерминированном распознавании задается некоторое количество эталонов, любой новый объект требуется отнести к определенному классу. На множестве эталонов определяются потенциальные функции Разделительная поверхность определяется из уравнений gl(x)=g^{x)>

]. В качестве решающего правила выбирают знак разности АglJ-gl-gJ■

Если эта величина положительна, то объект относят к классу г, если отрицательна - к классу ] .

Разделяющие функции, как правило, полагаются линейными, квадратичными или кусочно-линейными. Соответственно, различают линейное, квадратичное и кусочно-линейное распознавание. Для линейного распознавания разделяющая поверхность в общем случае может быть записана в виде ^(х) = со [X, + со 2�