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

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

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

Факультет Информационных систем и технологий

Направление Информационные системы и технологии

Кафедра Информационных систем и технологий

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

Исследование алгоритмов распознания символов. Формирование дескрипторов образов

Разработал А.А. Козлов

Самара 2017

Содержание

• Введение
• 1. Обзор методов создания дескрипторов образов объектов
• 1.1 Дескрипторы границ
• 1.2 Дескрипторы областей
• 1.2.1 Функция regionprops
• 1.2.2 Спектральная характеристика
• 1.2.3 Структурная характеристика
• 1.2.4 Статистический подход
• 1.3 Реляционные дескрипторы
• 1.4 Использование главных компонент для описания
• 2. Возможности Matlab для создания дескрипторов образов объектов
• 2.1 Раздел математика
• 2.2 Оптимизация
• 2.3 Работа с данными
• 2.4 Обработка сигналов и изображений
• 2.5 Проектирование систем управления
• 2.6 Оптимальные и робастные системы управления
• 2.7 Финансовые приложения
• 2.8 Функции пакета Image Processing Toolbox
• 3. Создание дескрипторов образов объектов. Рассмотрение результатов
• 3.1 Подробное описание алгоритма создания дескрипторов
• 3.2 Исследование по нахождению подходящих дескрипторов
• 3.3 Результаты исследования
• Заключение

Введение

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

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

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

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

Все вышесказанное определило актуальность темы работ - Исследование алгоритмов распознания символов; Формирование дескрипторов образов.

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

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

1) Рассмотреть известные на сегодня методы создания дескрипторов;

2) Выбрать подходящий метод для выполнения поставленной выше цели;

3) Подробно исследовать его и сделать необходимые выводы;

4) Создать дескриптор образа символа алфавита;

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

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

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

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

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

В третьей главе описано подробное исследование выбранного в первой главе алгоритма, проверяется его эффективность для выполнения поставленной цели.

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

matlab дескриптор изображение

1. Обзор методов создания дескрипторов образов объектов

1.1 Дескрипторы границ

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

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

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

Рис. 1.1 - Номера направлений цепных кодов а) с 4 направлениями б) с 8 направлениями

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

Рис.1.2 - Дискретная граница с наложенной укрупненной сеткой дискретизации и результаты

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

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

Основываясь на методах, перечисленных выше, мы можем перейти к подробному описанию создания дескрипторов на основе цепных кодов границы. Длинной четырехсвязной границы называется число пикселей этой границы. При подсчете длинны для горизонтальных и вертикальных переходов восьмисвязной границы к общей сумме добавляются единицы, а для диагональных переходов добавляют число равное корню из двух. Для выделения границы объектов на изображении используют функцию bwperim, имеющую следующий синтаксис: g = bwperim (f, conn), где g - это двоичное изображение f с выделенными границами объектов. Параметр conn обозначает тип связности и может принять значения 4 или 8, по умолчанию используется 8-связность. На исходном изображении объекты могут иметь любые значения пикселей, допустимые классом изображения, но фоновые пиксели будут иметь нулевые значения. По определению, пиксели периметра объекта должны быть не равны нулю и связаны по крайней мере с одним другим ненулевым пикселем.

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

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

Следующий дескриптор основанный на кодах Фримена - это нумерация фигур. Он строится на основе четырехнаправленного цепного кода и определяется как первая разность с минимальным численным значением. По определению порядок номера фигуры - это число цифр в его записи. Реализуется это при помощи формулы length(c.diffmm). Данный дескриптор инвариантен к выбору начальной точки и повороту, но повороты должны быть кратны 90 градусов. Один из приемов стандартизации произвольных поворотов состоит в совмещении координатных осей с направлением главной оси, а затем создание кода после данных преобразований.

Дескриптор Фурье

Одним из самых эффективных методов создания простых дескрипторов можно считать дескрипторы Фурье. Они представляют собой K-точечную дискретную границу на плоскости xy. Данную границу можно обойти начиная с произвольной точки (x₀,y₀), к примеру, по часовой стрелке обозначая координаты встреченных точек границы как (x₀, y₀), (x₁, y₁),…,(x_K-1, y_K-1). Если записать полученные координаты в виде x(k) = x_k а y(k) = y_k, то саму границу можно записать в виде последовательности координатных пар s(k) = [x(k), y(k)], где k = 0, 1, … K-1. Затем каждую полученную пару координат можно представить в виде комплексного числа:

(1.1)

Известно, что двумерное дискретное преобразование Фурье (DFT, Desrete Fourier Transform) для изображения f, Которое обозначается как F(u,v) задается следующим уравнением:

(1.2)

где u = 0, 1, 2, …, M-1;

v = 0, 1, 2, …, N-1;

Обратное дискретное преобразование Фурье задается уравнением:

(1.3)

где x = 0, 1, 2, …, M-1;

y = 0, 1, 2, …, N-1;

Из вышесказанного следует, что дискретное преобразование Фурье конечной последовательности s(k) задается уравнением:

(1.4)

где u = 0, 1, 2, …, K-1.

Комплексные коэффициенты a(u) называются фурье-дескрипторами границы. Если к полученным значениям применить обратное преобразование Фурье, то оно позволит восстановить границу исходного изображения s(k):

(1.5)

где k = 0, 1, 2, …, K-1;

Хотя для вычисления используется лишь P членов, но параметр k по-прежнему проходит по всему диапазону от 0 до K-1. Это означает то, что в приближенной границе будет такое же число точек, не смотря на то, что для их восстановления использовалось меньшее число членов. Важным является то, что низкочастотные составляющие описывают определяют общую форму границы объекта, а высокочастотные отвечают за описание мелких деталей. Отсюда следует, что чем меньше значение P, тем хуже детализация границы. Это можно продемонстрировать следующим примером.

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

Рис. 1.3 - Пример оригинального изображение и его восстановление при различных значениях P

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

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

При выполнении такой операции для каждой точки s(k) получим поворот всей последовательности на угол относительно начала координат.

Данную последовательность характеризует дескриптор следующего вида:

(1.5)

где u = 0, 1, 2, …, K-1;

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

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

Таблица 1.1 Зависимость формул границы и фурье-дескрипторов при преобразованиях

Преобразование	Граница	Фурье-дескрипторы
Тождественное	s(k)
Поворот
Параллельный перенос
Изменение масштаба
Смена начальной точки

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

(1.6)

Аналогично рассмотрим функцию изменения начальной точки последовательности с k = 0 на k = k₀. Основываясь на выражении получим следующую функцию:

(1.7)

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

1.2 Дескрипторы областей

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

1.2.1 Функция regionprops

Является одной из стандартных в matlab, относящихся к набору функций для анализа изображений из Image Processing Toolbox. Считается одним из главных инструментов при вычислении дескрипторов областей. Рассмотрим ее синтаксис: D = regionprops(L, properties), где L - размечающая матрица, а D является массивом структур, имеющим длину max(L(:)).

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

Параметр properties может быть смешанным массивом строк, разделенным запятой списком символьных строк, или одиночной строкой `basic' или `all'. Regionprops позволяет вычислять большое количество различных дескрипторов областей. К примеру, если в параметре properties будет значение `basic', будут вычислены основные дескрипторы `Area', `Centroid' и `BoundingBox'. Соответственно при использовании параметра `all' мы получим все дескрипторы, поддерживаемые данной функцией. Как следует из описания, данная функция позволяет решать очень большой спектр задач связанных с созданием дескрипторов областей.

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

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

Теперь мы рассмотрим эти методы подробнее.

1.2.2 Спектральная характеристика

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

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

Обнаружить и интерпретировать спектральные признаки становиться легче, если предварительно перейти к полярным координатам, в которых спектральные функции выражены в виде S(r,и), где r и и являются переменными в данной системе координат. Для каждого угла и функция S(r,и) рассматривается как одномерная S_и(r). Данное утверждение справедливо и для каждого значения частоты r, при которых функция принимает вид S_r(и). Проанализировав функцию S_и(r) при фиксации значения и мы получаем картину поведения спектра по направлению радиуса из начала координат. При анализе функции S_r(и), где фиксировано значение частоты, переменная r, будет получено поведение спектральной функции по окружности с центром в начале координат. Глобальное описание будет получено при интегрировании (или суммировании в дискретном случае) функций:

(1.8)

(1.9)

где R₀ - радиус круга с центром в начале координат;

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

1.2.3 Структурная характеристика

Ко второму по важности методу создания дескрипторов можно отнести структурный подход. Пусть существует правило, которое можно записать в форме , указывающее, что символ S можно переписывать в виде (к примеру, при троекратном применении данного правила получается строка символов вида ). Допустим, что символ представляет круг, следовательно строка есть ни что иное, как «последовательность кругов в право от начальной точки», и применение правила позволяет представить текстуру в виде, приведенном на рис.1.4

Рис. 1.4 - 1) Базовый элемент текстуры 2) Текстура, построенная применением правила 3) Двумерная текстура, полученная применением нескольких правил

Если к полученной схеме добавить еще несколько правил: , V, A, , . В данном случае b интерпретируется как «круг ниже», а с - как «круг слева». Комбинируя эти правила можно получить символьную строку вида , которой будет соответствовать матрица 3x3построенная из кругов. Таким же образом можно создавать более сложные и крупные текстурные образы.

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

1.2.4 Статистический подход

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

(1.10)

Где m - среднее значение величины z(Средняя яркость изображения), которое можно найти:

(1.11)

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

Характеристикой асимметрии гистограммы является третий момент, который можно найти по формуле:

(1.12)

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

(1.13)

а также среднюю энтропию:

(1.14)

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

1.3 Реляционные дескрипторы

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

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

Самым очевидным свойством для кодирования данной структуры является чередование элементов a и b. Из этого следует, что простейший способ символьного описания будет заключаться в построении рекурсивной зависимости, в которой участвуют данные базисные элементы. Таким образом, можно получить следующие правила подстановки:



Рис.1.5 - а) Простая ступенчатая структура б) Структура в закодированном виде

a)

b)

c)

В данном случае S и A являются переменными, а элементы a и b будут константами, соответствующими непроизводным элементам. В первом правиле говорится, что начальный символ S разрешается заменить на непроизводный элемент со следующей за ним переменной A. По второму правилу таким же способом из полученной ранее переменной мы можем получить b или сочетание b и S. Последнее правило позволяет повторить процедуру из первого правила, а при замене A на b вся процедура заканчивается, так как в выражении больше не остается переменных. Рассмотрим рисунок 1.6, где продемонстрированы примеры применения данной процедуры для описания фигуры. Под каждой из фигур указана очередь применяемых правил. Во всех случаях между a и b сохраняется связь, поскольку вслед за непроизводным элементом a появляется элемент b. Особенность данного алгоритма заключается в том, что с помощью этих простых правил подстановки можно описать бесконечное множество «похожих» структур.



Рис. 1.6 - Пример применения правил

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

Рис.1.7 - Кодирование границы области при помощи направленных отрезков

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

Рис.1.8 - а) Абстрактные непроизводные элементы. б) Операции над элементами

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

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



Рис.1.9 - а) Набор непроизводных элементов б) Шаги построения некоторой структуры

Для наглядности рассмотрим некоторое дерево T (рис. 1.10). Оно является конечным множеством, состоящим из одной и более вершин, таких что:

a) Существует единственная вершина (обозначим ее знаком $), которая будет являться корнем дерева.

b) Остальные вершины разделяются на m непересекающихся множеств, каждое из которых в свою очередь является деревом, называемым поддеревом дерева T.

Рис.1.10 - Простое дерево с корнем $ и концевыми вершинами x и y

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

Существует два вида важной информации об элементах (вершинах) дерева. К таковым можно отнести информацию о самой вершине, хранящуюся в виде некоторых параметров, описывающих ее, и информация о связи вершины с соседями, которая существует в виде набора указателей на эти соседние вершины. Первый вид информации определяет фрагмент структуры изображений (Это может быть граница или часть области), а второй определяет физическую связь этого фрагмента с другими (другими словами, показывает отношения между ними). К примеру, возьмем некоторый объект, представленный на рис 1.11. Его можно представить в виде дерева при помощи отношения «находиться внутри», и тогда корнем дерева выступит область, обозначенная знаком $, к первому уровню будут отнесены области a и c, которые дадут ветви, исходящие из корня. К следующему уровню будут отнесены область b, расположенная внутри a, d и e, находящиеся внутри c, а на области f, находящейся внутри e, постройка дерева будет завершена.

Рис.1.11 - а) Некоторая область, состоящая из вложенных подобластей

б) Представление в виде дерева, полученное при помощи отношения «находиться внутри»

1.4 Использование главных компонент для описания

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

Пусть даны три цветовые компоненты. Их можно рассматривать как единое целое, если любую группу из трех соответственных пикселей считать вектором. Допустим, x₁, x_2, x₃ имеют значения первого пикселя в каждом из трех изображений. Такие элементы можно записать в виде вектор столбца x с размерностью равной трем:

(1.15)

Данный вектор представляет один общий пиксель во всех трех изображениях. Если рассматриваемые изображения имеют размеры MxN, то, представив все их пиксели в таком виде, мы сможем получить K=MN таких трехмерных векторов. Если регистрировать n совмещенных изображений, то векторы станут n-мерными.

(1.16)

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

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

(1.17)

где - ожидаемое значение аргумента;

индекс x - связь с генеральной совокупностью векторов x;

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

Ковариационная матрица для генеральный совокупности векторов определяется как:

(1.18)

Так как x является n-мерным вектором, а и - это матрицы порядка . Элемент матрицы есть дисперсия , т.е. i-ой совокупности компоненты векторов x генеральной совокупности, а элемент матрицы есть ковариация компонент этих векторов. Значения данной матрицы действительные и симметричные относительно главной диагонали. Допустим, что компоненты будут некоррелированными, следовательно их ковариация будет равна нулю и . Следует сделать замечание, что данные выше определения при n=1 будут сведены к одномерным эквивалентам.

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

(1.19)

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

(1.20)

Вывод

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

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

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

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

2. Возможности Matlab для создания дескрипторов образов объектов

Matlab - это программный комплекс для решения прикладных математических задач. Свою историю он начинает с конца 1970-х годов, когда Кливом Моулером (англ. Cleve Moler) был разработан одноименный язык программирования для работы с библиотеками численных методов, написанных на FORTRAN в целях облегчить работу людям, не знакомым с данным языком. Особенностями Matlab является ориентация на работу с матрицами (от этого неофициальным лозунгом данного языа стало выражение «Think vectorized», что можно перевести как «Думай векторами»), готовая реализация ряда полезных алгоритмов, богатые возможности для визуализации данных и взаимодействия с другими языками.

В 1984 году совместными усилиями Клива моулера и Стива Бангерта (англ. Steve Bangert) Matlab был переписан на язык C, а первая версия программы носила название JACKPAC и позиционировалась как проектировочная система управления, но также нашла широкое распространение в образовании, в частности для преподавания численных методов и линейной алгебры. Matlab обладает широким функционалом для решения различных задач. Их можно разбить на семь основных блоков: Математика, Оптимизация, Работа с данными, обработка сигналов и изображений, проектирование систем управления, оптимальные и робастные системы управления, финансовые приложения. В каждое из этих направлений входит несколько наборов инструментов, предназначенных для решения задач данного типа. Далее будет представлено краткое описание представленных наборов инструментов.

2.1 Раздел математика

Curve Fitting Toolbox

Представлен набором пользовательских графических интерфейсов (GUIs) и M-функций для применения в:

§ Первичной обработке данных, например разбиение на области и сглаживание.

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

§ Оценках качества проведенной аппроксимации.

§ Анализах, таких как дифференцирование, экстраполяция и интегрирование.

Statistic toolbox

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

Neural Network Toolbox

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

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

Symbolic math Toolbox

Позволяет использовать вычислительное ядро пакета Maple V(разработана Waterloo Maple Software) для вычислений с плавающий точкой и пользоваться символьной математикой. Дополнение Extended Symbolic math Toolbox дает дополнительную возможность программирования на Maple и предоставляет доступ к специализированным библиотекам.

Partial Differential Equation (PDE) Toolbox

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

2.2 Оптимизация

Optimization Toolbox

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

Genetic Algorithm and Direct Search Toolbox

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

2.3 Работа с данными

Data Acquisition Toolbox

Представлен коллекцией M и MEX-файлов (DLLs) созданных в среде Matlab, для выполнения следующих функция:

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

§ Поддержку аналоговых входов (AI) и выходов (AO) и цифровых входов/выходов I/O (DIO) подсистем включая мгновенны аналоговые преобразования.

§ Сбор данных, управляемый событиями.

Instrument Control Toolbox

Представляет набор функций направленных на взаимодействие с такими инструментами, как функциональные генераторы и осциллографы, непосредственно чрез оболочку программы Matlab. Он содержит набор M-файлов и графических интерфейсов, позволяющих посылать команды на устройства и принимать данные для дальнейшей обработки, также поддерживается прием как в двоичном так ив ASCII коде. Упомянутые выше ASCII коды можно использовать для написания команд, позволяющих изменять настройки подключенного оборудования, а также подготовить инструменты к передаче данных или получить информацию об их состоянии. Данный пакет поддерживает текстовые команды Standard Commands for Programmable Instruments (SCPI), а при помощи двоичных команд позволяет провести изменение численных величин, к примеру, для калибровки инструментов. Поддерживаются как синхронные, так и асинхронные операции приема и передачи данных.

Database Toolbox

Как следует из названия, данный блок предоставляет мощные средства анализа данных и визуализации в среде Matlab для работы с данными, находящимися в базе данных. Предоставляется возможность использования команд языка запросов SQL для различных манипуляций с данными, как чтение из базы, так и запись новых данных, а также выполнение простых и сложных запросов. Еще одной возможностью является взаимодействие с ODBC/JDBC-совместимыми базами данных, такими как Oracle, Microsoft Access, Ingres и т.д., а благодаря модулю Visual Query Builder свои запросы может составлять пользователь, не знакомый с SQL.

Excel Link Toolbox

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

2.4 Обработка сигналов и изображений

Signal Processing Toolbox

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

Image Processing Toolbox

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

Image Acquisition Toolbox

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

Communications Toolbox

Представляет собой набор для создания, анализа и тестирования цифровых и аналоговых систем, а также устройств связи и передачи информации. Благодаря функции Real-Time Workshop на основе созданных систем можно генерировать переносимый C код.

System Identification Toolbox

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

Wavelet Toolbox

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

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

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

Filter Design Toolbox

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

Mapping Toolbox

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

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

Control System Toolbox

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

Fuzzy Logic Toolbox

Модуль предназначен для проектирования и диагностики нечетких моделей и работает совместно с Simulink. Поддерживает современные методы нечеткой кластеризации и адаптивные нечеткие нейронные сети. При подключении Real-Time Workshop генерирует ANSI C код для работы в реальном времени.

Model-Based Calibration Toolbox

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

2.6 Оптимальные и робастные системы управления

В данную группу входят функции для исследования и проектирования систем управления динамическими объектами. Основывается на Control System Toolbox, но отличается тем, что применяет теорию оптимизации по нормам пространств Харди и . Для лучшего понимания следует дать определение робастности. Робастность - (англ. Robustness, от robust - «крепкий», «устойчивый») это свойство системы, характеризующее независимость влияния на результаты ее исследования различного рода выбросов (т.е. сильно выделяющиеся из общей выборки) и устойчивость к помехам.

Mu-Analysis and Synthesis Toolbox

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

Robust Control Toolbox

Данный модуль состоит из программ для анализа и синтеза систем управления с робастными свойствами, при помощи методов теории оптимизации в пространствах Харди.

LMI Control Toolbox

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

Model Predictive Control Toolbox

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

2.7 Финансовые приложения

Financial Toolbox

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

...