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

Содержание Введение

1. Исследовательский раздел

1.1 Постановка задачи для разработки системы распознавания специального изображения

1.2 Обзор и анализ существующих методов распознавания, применимых к задаче

1.2.1 Распознавание по шаблонам

1.2.2 Контекстное распознавание

1.2.3 Структурный подход

1.2.4 Нейронные сети

1.2.5 Клеточные автоматы

1.2.6 Другие варианты решения задачи распознавания текста

1.3 Обзор и анализ существующих программ распознавания

1.3.1 MatanCrack

1.3.2 Интернет сервис anti-captcha.com

1.3.3 AddSite

1.3.4 PWNtcha

1.3.5 aiCaptcha

1.4 Формализованное описание постановки задачи

1.5 Обоснование выбора векторного пространства для принятия решения о совпадении символов Выводы

2. Специальный раздел

2.1 Формально-логическая модель процесса разработки программного обеспечения

2.2 Метод распознавания символов на основе теории векторного пространства

2.3 Архитектура модуля распознавания символа, модулей корректировки изображения

2.4 Особенности реализации предложенного решения и его качественная оценка Выводы

3. Технологический раздел

3.1 Структура программного комплекса и UML-представление ПО

3.2 Обоснование выбора инструментальных средств реализации программного решения

3.3 Алгоритмическая реализация решения задачи

3.4 Критерии сравнения разработанного ПО с существующими

решениями

3.5 Анализ точности совпадения распознанного изображения

4. Безопасность жизнедеятельности

4.1 Анализ опасных и вредных факторов на рабочем месте пользователя ПЭВМ

4.2 Аттестация рабочего места пользователя ПЭВМ

4.3 Требования к микроклимату, содержанию аэроионов и вредных химических веществ в воздухе на рабочих местах, оборудованных ПЭВМ

4.4 Требования к уровням шума и вибрации на рабочих местах, оборудованных ПЭВМ

4.5 Требования к освещению на рабочих местах, оборудованных ПЭВМ

4.6 Требования к помещениям для работы с ПЭВМ

4.7 Экологическая оценка драгоценных металлов в деталях, узлах и модулях ПЭВМ, и технологическая схема переработки

5. Организационно-экономический раздел

5.1 Планирование разработки программного продукта с построением

графика

5.2 Определение трудоемкости и продолжительности работ по созданию программного продукта

5.3 Построение ленточного графика разработки программного

продукта

5.4 Расчет сметы затрат на разработку программного продукта

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

6.1 6. Другие разделы

6.2 Руководство пользователя

6.3 Руководство программиста

6.4 Руководство системного администратора

7. Научная новизна и практическая значимость проекта

Заключение

Список использованных источников Приложение А. Листинг программы

Введение

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

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

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

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

В этой работе под специальным изображением мы будем подразумевать «капчу"(Captcha).

Captcha — это (от англ. «Completely Automated Public Turing test to tell Computers and Humans Apart» — полностью автоматизированный публичный тест Тьюринга для различия компьютеров и людей) — торговая марка Университета Карнеги-Меллона, в котором разработали компьютерный тест, используемый для того, чтобы определить, кем является пользователь системы: человеком или компьютером. Термин появился в 2000 году. Основная идея теста: предложить пользователю такую задачу, которую с лёгкостью может решить человек, но которую несоизмеримо сложнее решить компьютеру.

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

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

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

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

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

Предварительно обработать изображение, преобразовать его к необходимому формату;

Удалить зашумляющие линии;

Определить границы символов и разделить их;

Распознать символы.

Структура дипломного проекта включает в себя следующие разделы:

Исследовательский раздел посвящен обзору методов и алгоритмов распознавания изображений.

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

Технологический раздел включает в себя алгоритмы и составные части разрабатываемого ПО.

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

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

1. Исследовательский раздел

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

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

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

Распознавание текста включает в себя следующие подзадачи и подпроцессы[1.1]:

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

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

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

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

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

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

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

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

Рассмотрим несколько примеров специальных изображений:

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

Усложнение в распознавании заключается в нестабильном фоне. Но из-за фиксированного шрифта, постоянного расположения символов, большого контраста фона и текста алгоритм уязвим к банальному сравнению символов с эталоном.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3.1 MatanCrack

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

Недостатки программы:

Черные символы на белом фоне;

Отсутствие шумов и других артефактов (например линий);

Символы никогда не пересекаются;

Всегда одинаковый шрифт;

Под интегралом всегда 4 слагаемых.

Степени и множители состоят из одной цифры;

Степени и множители находятся в диапазоне от 2 до 5.

К сильным сторонам можно отнести:

Наличие нелинейных искажений;

Возможное отсутствие степени или множителя;

Иногда, dx слипаются в один символ;

Меняется ширина капчи.

Интернет сервис anti-captcha.com

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

1.3.2 AddSite

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

1.3.3 PWNtcha

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

1.3.4 aiCaptcha

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

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

исследовать процесс обработки изображения на основе теории векторного пространства;

разработать алгоритм разбиения изображения текста на изображения символов;

определить принцип выделения признаков;

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

определить возможность построения векторного пространства в процессе классификации признаков символов.

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

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

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

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

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

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

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

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

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

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

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

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

Определение вектора.

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

Определение векторного пространства.

Множество V называется векторным пространством, если для него выполняются следующие аксиомы:

Множество V является аддитивной абелевой группой.

Для любого вектора и любого скаляра — элемента a поля F определено произведение av, являющееся вектором. Это произведение определено так, что lv=v, где l — единичный элемент поля F.

Выполняются законы дистрибутивности

и ,

где — скаляры, а и - векторы.

Выполняется закон ассоциативности

где — скаляры, а — вектор.

Свойства векторного пространства

Максимальное число линейно независимых векторов в V называется размерностью пространства V над полем F.

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

Подмножество W векторного пространства F такое, что любая линейная комбинация векторов этого подмножества снова принадлежит W, называется подпространством пространства V. Легко проверить, что все векторы подпространства удовлетворяют аксиомам 1 — 4. Очевидно, что размерность подпространства не превышает размерности пространства, т.к. во всем пространстве содержится не более n линейно независимых векторов. Каждое подпространство можно рассматривать как самостоятельное пространство. Следовательно, каждое подпространство имеет свой базис.

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

Можно показать, что и .

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

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

Можно показать, что если - подпространство размерности k n-мерного векторного пространства, то размерность нулевого пространства равна n-k.

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

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

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

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

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

Если посмотреть на нашу, тестовую капчу, то можно увидеть три основных цвета:

Белый (фон);

Серый (шум);

Красный (текст).

Для начала мы открываем наше изображение и преобразуем его в GIF формат. Это облегчит нам работу, т.к. в этом стандарте всего 255 цветов. Распечатав результат, мы получим следующие данные (таблица 2.1):

Таблица 2.1 — Основные цвета изображения

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

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

Таблица 2.2 — Результат бинарного преобразования

После этого, нам необходимо избавиться от шумов на изображении. Сделать это можно с помощью преобразования Хафа[2.2]. Преобразование Хафа — метод по извлечению элементов из изображения, используемый в анализе, обработке изображения и компьютерном видении. Данный метод предназначен для поиска объектов, принадлежащих определённому классу фигур с использованием процедуры голосования. Процедура голосования применяется к пространству параметров, из которого и получаются объекты определённого класса фигур по локальному максимуму в, так называемом, накопительном пространстве, которое строится при вычислении трансформации Хафа. При автоматизированном анализе цифровых изображений очень часто возникает проблема определения простых фигур, таких как прямые, круги или эллипсы. Во многих случаях используется алгоритм детектирования границ в качестве предобработки для получения точек, находящихся на кривой в изображении. Однако, либо из-за зашумлённости изображения, либо из-за несовершенства алгоритма детектирования границ могут появиться «потерянные» точки на кривой, так же как и небольшие отклонения от идеальной формы прямой, круга или эллипса. По этим причинам часто довольно сложно сгруппировать выделенные границы в соответствующий набор прямых, кругов и эллипсов. Назначение преобразования Хафа в том, чтобы разрешить проблему группировки граничных точек путём применения определённой процедуры голосования к набору параметризованных объектов изображения.

В простейшем случае преобразование Хафа является линейным преобразованием для обнаружения прямых. Прямая может быть задана уравнением y = mx + b и может быть вычислена для любой пары точек на изображении (x, y). При преобразовании Хафа главная идея — учесть характеристики прямой не как точек изображения, а в терминах её параметров, то есть m — коэффициента наклона и b — точки пересечения. Основываясь на этом факте прямая y = mx + b может быть представлена в виде точки с координатами (b, m) в пространстве параметров. Однако, есть одна проблема в том, что вертикальные прямые имеют бесконечные значения для параметров m и b. Соответственно для удобства вычислений лучше всего представить прямую с помощью других параметров, более известных как и (тета). Параметр представляет собой длину радиус-вектора ближайшей к началу координат точки на прямой, а — это угол между этим вектором и осью координат. Таким образом уравнение прямой можно записать так (формула 2.2)

(2.2)

что может быть преобразовано в

. (2.3)

Поэтому возможно связать с каждой прямой на изображении пару (r, и) которая является уникальной при условии если

или если .

Плоскость (r, и) иногда называется Пространство Хафа для набора прямых 2-мерном случае. Это представление делает трансформацию Хафа концептуально очень близкой к 2-мерному преобразованию Радона.

Бесконечное число прямых может проходить через одну точку плоскости. Если эта точка имеет координаты в изображении, то все прямые, проходящие через неё соответствуют следующему уравнению:

(2.4)

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

Алгоритм преобразования Хафа использует массив, называемый аккумулятором, для определения присутствия прямой y = mx + b. Размерность аккумулятора равна количеству неизвестных параметров пространства Хафа. Например, для линейной трансформации нужно использовать двумерный массив, так как имеются два неизвестных параметра: m и b. Два измерения аккумулятора соответствуют квантизированным значениям параметров m и b. Для каждой точки и её соседей алгоритм определяет достаточен ли вес границы в этой точке. Если да, то алгоритм вычисляет параметры прямой и увеличивает значение в ячейке аккумулятора, соответствующей данным параметрам.

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

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

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

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

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

Основные операции[2.3]:

Перенос. Операция переноса множества пикселов X на вектор t задаётся в виде =x+t. Следовательно, перенос множества единичных пикселов на бинарном изображении сдвигает все пикселы множества на заданное расстояние. Вектор переноса t может задаваться в виде упорядоченной пары (?r,?c), где? r — компонент вектора переноса в направлении строк, а? c — компонент вектора переноса в направлении столбцов изображения.

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

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

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

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

Рисунок 2.2 — Результат разбиения изображения на символы.

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

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

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

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

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

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

Как бы хорошо не была обучена система, идеального распознавания добиться не получится. На данный момент нет идеального решения, способного распознавать изображения, как человек. Но в этом нету ни чего удивительного, за частую даже человеку сложно понять, что написано на изображении. Помимо зашумления, создавать трудность могут похожие символы. Например, человек может ошибиться в символе «О» и числе «0». От этих ситуаций не застрахован и компьютер. Тем не менее, приемлемым результатом работы системы, я считаю, вероятность угадывания в 40%. Так как скорость работы компьютера во много раз превышает человеческую, то система способна за доли секунды распознать изображение, хоть и не с первого раза.

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

3. Технологический раздел

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

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

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

Далее приведено перечисление всех моментов, реализованных в программе:

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

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

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

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

Ниже представлена UML диаграмма классов (рисунок 3.2)

Рисунок 3.2 — UML диаграмма классов.

3.2 Обоснование выбора инструментальных средств реализации программного решения Выбор языка программирования и среды разработки обуславливался несколькими требованиями:

Разработанная на данном языке программа должна работать под большинством количеством ОС;

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

Программа должна работать на платформе Windows Mobile, Android OS, для того, чтобы запускать программно-математический комплекс на мобильных устройствах. Это делает шире область применения данной системы;

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

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

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

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

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

Графический интерфейс будет реализован с использованием библиотеки PyQt. PyQt — набор «привязок» графического фреймворка Qt для языка программирования Python, выполненный в виде расширения Python. PyQt работает на всех платформах, поддерживаемых Qt: Linux и другие UNIX-подобные ОС, Mac OS X и Windows. PyQt также включает в себя Qt Designer (Qt Creator) — дизайнер графического интерфейса пользователя. Программа pyuic генерирует Python код из файлов, созданных в Qt Designer. Это делает PyQt очень полезным инструментом для быстрого прототипирования. Кроме того, можно добавлять новые графические элементы управления, написанные на Python, в Qt Designer.