Реферат: Помехоустойчивое кодирование, распознавание символов
Примерный вид полученных графиков приведен на рисунках 1.2.1 и 1.2.2.
45
Количество
ошибок,%
15
20 40 60 100
Количество повторений, n
Рисунок 1.2.1 – Число ошибок восстановления
100
Количество
ошибок,%
 |
|
 |
15
20 40 60 100
p01,p10, %
Рисунок 1.2.1 – Число ошибок восстановления
1.3 ОПИСАНИЕ ПРОГРАММЫ
В соответствии с заданием мною была разработана программная модель канала с выводом графика зависимости числа ошибок от числа n. Программа написана на языке Borland Pascal 7.0.
Для программной реализации канала программа запрашивает длину передаваемого массива сообщений, число n и выполняет подсчет числа ошибок при его передаче. Затем идет расчет массива данных для построения графика зависимости числа ошибок от n для n, изменяющегося в интервале 1..100 с шагом 3. После этого происходит вывод на экран искомого графика.
В программе используются следующие процедуры и функции:
Функция flag может принимать булевское значение в зависимости от входной вероятности. Она служит для осуществления в программе случайного события с заранее заданной вероятностью.
Процедура ver рассчитывает ансамбль вероятностей исходного сообщения в зависимости от A и B, а также упорядочивает его по убыванию.
Процедура set_codes заполняет массив кодов по алгоритму Шеннона-Фэно и инициализирует маски для декодирования неравномерного кода.
Функция без параметров sourse при каждом обращении к ней принимает значение сообщения из ансамбля в соответствии с его вероятностью. Она использует тот же принцип, что и функция flag.
Процедура deranges вносит в код, соответствующий сообщению sourse, помехи в соответствии с моделью (n,1)-кода. В ней используются функции побитного сдвига shr и shl, а также функция flag.
Процедура decoder служит для раскодирования неравномерного двоичного кода после действия на него помех в канале. Поскольку наибольшая длина кода не превышает 8 бит, то для их хранения, передачи и декодирования используется тип данных – байт, причем располагаются они
в старших битах.
Процедура graphik служит для отображения на экране графика зависимости числа ошибок восстановления информации от значений параметра n (n,1) – кода. Всё изображение привязано к началу координат (x0,y0). Для удобства по
оси y откладываются значения в %. График отображается отрезками прямых для сглаживания резких скачков
значений.
1.4 ВЫВОД
В данном разделе были рассмотрены алгоритм построения неравномерного двоичного кода по алгоритму Шеннона-Фэно и такие характеристики кода и канала, как совместная энтропия, условная энтропия, производительность источника и т.д.
Кодирование информации по Шеннону-Фэно в сочетании с кодированием (n,1) кодом показало неплохие результаты при программном моделировании канала. Так, при передаче порядка 1000 символов при n = 20..25 практически не наблюдается ошибок при р10 и р01, определенных по заданию.
2 РАСПОЗНАВАНИЕ СИМВОЛОВ
2.1 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Под распознаванием объекта будем понимать его узнавание, т.е. определение его как элемента некоторой совокупности объектов, называемой классом.Под образом (классом) будем понимать множество объектов, объединённых общими свойствами.
Признаки – это характеристики объекта, которыми определяются его свойства. Множеству образов соответствует алфавит, а множеству признаков соответствует словарь признаков.
Все ситемы и модели распознавания можно классифицировать следующим образом.
|
По заданию курсового проекта определён алфавит объектов – множество, состоящее из пяти прописных и пяти строчных букв латинского алфавита. Необходимо построить простую детерминированную систему распознавания.
Под простой будем понимать систему, алгоритм работы которой определён на основе априорной информации.
Сложные системы состоят из нескольких подсистем и уровней распознавания. Примером такого вида систем являются медицинские диагностические системы.
Работа систем без обучения осуществляется на основе априорной информации о признаках. В обучающиеся системы заложен алгоритм обучения по специально подобранной обучающей выборке. В самообучающихся системах заключены правила, по которым система сама определяет множество классов(алфавит классов).
Детерминированная система – это такая система, в которой связь между значениями признаков и классами жесткая, определенная.
Существует три подхода к задаче распознавания текстовых символов.
Первый – шаблонная (растровая) классификация. При её использовании считанный символ сравнивают со всеми шаблонами, хранящимися в базе. Критерии совпадения символов:
а)
Q=S fш (xi,yj) XOR fs (xi,yj) min( по всем шаблонам );
б) Корреляция между шаблоном и считываемым символом
R(t,z)=òx òy fш
(x,y) . fs (x - t, y -z)
max
Преимущества: малая чувствительность к дефектам (разрывы, шумы…)
Недостатки: необходимо обучение новым шрифтам и типам размеров шрифтов.
Второй – признаковая классификация.
Преимущества: изображение символа преобразуется в простой набор признаков.
Недостатки: уход от истинного изображения.
При использовании этого метода можно использовать следующие признаки:
- размеры и соотношения размеров символов (длина, высота, площадь);
- проекции на различные оси;
- моменты относительно различных осей и соотношения между ними;
Третий – структурная классификация. Заключается в анализе топологии символов.
Обнаружение: углов, окрестностей, линий, пересечений, конечных точек и их взаимное расположение.
В своей работе наиболее приемлемым я счел использование шаблонной классификации на основе корреляционной функции. Использование других признаков я счёл лишним, т.к. они обладают меньшей эффективностью, а следовательно, уменьшают эффективность распознавания.
2.2 ОПИСАНИЕ ПРОГРАММЫ
Для моделирования системы распознавания я разработал программу на языке Borland Pascal.
В программу вхолят следующие процедуры и функции.
Процедура Init_Graph_Mode осуществляет вход в графический режим при использовании графического драйвера видеоадаптера SVGA. Т.к. драйвер svga256.bgi не является встроенным в таблицу BGI, то для его использования необходимо обратиться к стандартной процедуре InstallUserDriver. Кроме того, эта процедура инициализирует палитру GrayScale путем обращения к стандартной процедуре SetRGBPalette.
Процедура ShowList служит для отображения на экране картинки со строкой символов. Отображение идет с увеличением в 9 раз, т.е. каждый пиксель исходной картинки отображается на экране окном 3*3 одинаковых пикселей. В процедуру в качестве параметров передается x и y точки-начала координат, относительно которой и происходит отображение.
Процедура Init_Data служит для заполнения массивов данных: массивов, где содержатся считанные в память картинки.
Процедура Deranges вносит в исходную картинку помехи.
Внесение помех осуществлялось из расчёта 20% от общего веса символов. Координаты пикселей-помех являются случайными числами в пределах ширины и высоты картинки. Пиксель со случайными координатами инвертируется, т.е. при попадании на белый фон ставится чёрная точка, а при попадании на символ – белая точка.
Процедура Filter производит посильное удаление внесённых помех. Для этого используются 16 видов масок: для удаления помех, “залезших” на символ, для удаления групп из двух помех, для удаления помех, “пристроившихся” к символу. При совпадении маски с фрагментом изображения происходит изменение соответствующих пикселей.
Процедура Ramka служит для нахождения координат минимально описанного прямоугольника. Соответствующие переменные являются глобальными, процедура изменяет их значения и значение текущей координаты x. В зависимости от значения переменной flag происходит рисование полученной рамки на картинке.
