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


ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ
ПО ВЫСШЕМУ ОБРАЗОВАНИЮ
Кубанский Государственный Технологический Университет
Кафедра автоматизации производственных процессов

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовой работе
Тема: «КОДИРОВАНИЕ И ПЕРЕДАЧА ИНФОРМАЦИИ.
РАСПОЗНАВАНИЕ ГРАФИЧЕСКИХ ОБЪЕКТОВ».
Выполнил: студент гр. 97-ОА-62
Яворский Д.Н.
Номер зачётной
книжки: 97-ОА-650
Проверил: доцент каф. АПП
Шахворостов Н.Н.
Краснодар
1999

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ
ПО ВЫСШЕМУ ОБРАЗОВАНИЮ
Кубанский Государственный Технологический Университет
ЗАДАНИЕ
На курсовую работу

Студенту гр.

По дисциплине


Тема курсовой работы


Исходные данные





1. Выполнить расчёты:
1.1
1.2

1.3
1.4

2. Выполнить графические работы:
2.1
2.2
3. Выполнить научные и учебно-исследовательские работы:
3.1
3.2
3.3
3.4

4. Оформить расчётно-пояснительную записку
5. Основная литература



Задание выдано

Срок сдачи работы

Задание принял

Руководитель проекта

Работа защищена

С оценкой

ЧЛЕНЫ КОМИССИИ:
РЕФЕРАТ
ПЕРЕДАЧА ИНФОРМАЦИИ, КОДИРОВАНИЕ, КОД ШЕННОНА-ФЭНО,
ЭФФЕКТИВНОСТЬ КОДА, РАСПОЗНАВАНИЕ СИМВОЛОВ.
Темой курсового проекта является моделирование передачи эффективно закодированной информации по каналу связи с помехами, а также распознавание пяти букв латинского алфaвита.
В первой части произведен теоретический расчет информационных характеристик последовательного канала связи с помехами. Программное моделирование показало, что реальные каналы приближаются по своим характеристикам к идеализированному каналу лишь при определенных значениях своих параметров.
Во второй части сделана попытка распознавания строки в графическом формате, составленной из пяти строчных и пяти прописных букв латинского алфавита,
и cодержащей помехи. В программе была смоделирована система распознавания, основанная на шаблонной классификации.
Курсовой проект содержит страниц, 3 рисунка,
13 таблиц, 4 источника, 2 приложения. СОДЕРЖАНИЕ
ВВЕДЕНИЕ.......................................
1 КОДИРОВАНИЕ И ПЕРЕДАЧА ИНФОРМАЦИИ
1.1 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ.....................
1.2 ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ......................
1.3 ОПИСАНИЕ ПРОГРАММЫ.........................
1.4 ВЫВОД......................................
2 РАСПОЗНАВАНИЕ ГРАФИЧЕСКИХ ОБЪЕКТОВ
1.1 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ ....................
1.2 ОПИСАНИЕ ПРОГРАММЫ.........................
1.3 ВЫВОД......................................
ЗАКЛЮЧЕНИЕ.....................................
ЛИТЕРАТУРА.....................................
ПРИЛОЖЕНИЕ А...................................

ПРИЛОЖЕНИЕ Б...................................
ВВЕДЕНИЕ
Данная работа демонстрирует моделирование процессов передачи и распознавания информации. Она состоит из двух частей.
Первая часть посвящена моделированию канала передачи информации. Для передачи сообщения через такой канал с помехами используется алгоритм кодирования по методу Шеннона-Фэно с последующим кодированием (n,1) кодом.
Вторая часть посвящена моделированию простой системы распознавания. В качестве объектов выступают пять прописных и пять строчных букв латинского алфавита в BMP-формате. Строка символов содержит помехи в виде одиночных и объединившихсявгруппыпикселей.Использован шаблонныйподходкраспознаванию.1 КОДИРОВАНИЕ И ПЕРЕДАЧА ИНФОРМАЦИИ
1.1 ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ
Кодирование и передача информации по каналу связи осуществляется в соответствии со схемой канала, изображенной на рисунке 1.1.1.
Приемник
Источник


Vi Vj
Декодер
источника
Кодер источника

Помехи


Zi Zj
Канал
Декодер
канала
Кодер
канала
Xi Yj

Рисунок 1.1.1 - Структура передачи информации
Источник генерирует последовательность сообщений из ансамбля {V, P(V)},
где V – символ сообщения;
P(V) – вероятность символа сообщения, рассчитываемая по формуле:
(1.1.1)

где i=1…m;
m, r – заданные величины.
Кодер источника кодирует сообщение Vi в Zi по алгоритму Шеннона-Фэно.
Энтропия сообщения H(Z), бит/символ вычисляется по следующей формуле:
(1.1.2)
Формула для расчета средней длины кода Lср, бит имеет вид:
(1.1.3)
где L(Zi) – длина кода, бит;
P(Zi) – вероятность кода.
Максимальная энтропия H(Z)max, бит/символ неравномерного двоичного кода Zi определяется по формуле:
(1.1.4)
Зная среднюю длину кода, можно определить коэффициент эффективности Кэф кода Zi по формуле:
(1.1.5)
Для расчета коэффициента избыточности Кизб используется формула:
(1.1.6)
Кодер канала осуществляет простое кодирование повторением n = 3 раз каждого двоичного сигнала сообщения Zi. Таким образом, имеется всего два кода:
Х1=(0 0 0)Х2=(1 1 1)
Вероятность каждого из них определяется по формуле:
(1.1.7)
где к=0,1;
- количество элементов «к» в коде Zi.
При передаче Xк по каналу связи возможны ошибки с вероятностями, определяемыми следующим образом:
P10=0.2 + 0.02A(1.1.8)

P01=0.2 + 0.02B(1.1.9)

где р10 – вероятность принятия нуля при передаче единицы;
р01 – вероятность принятия единицы при передаче нуля;
А, В – заданные величины.
В дальнейшем, для удобства будут использоваться следующие принятые обозначения:
Х - передаваемый код;
Y - принимаемый код.
При построении канальной матрицы P(Y/X) воспользуемся тем, что при передаче может произойти ошибка лишь в одном разряде X1 или X2.
Тогда в 1 строке матрицы элементы определятся следующим образом:
1 – p01 , i = 1

P(xi,yj) = P01/3 , i = 2,3,4. (1.1.10)

0 , i = 5,6,7,8.
Элементы канальной матрицы совместной вероятности P(X,Y) определяются по формуле:
P(xi,yj)=P(xi)P(yj/xi)(1.1.11)
Зная матрицу совместной вероятности P(X,Y), можно вычислить элементы матрицы вероятностей P(Y). Они находятся по формуле:
P(yi)=P(x1,yi)+ P(x2,yi)(1.1.12)
В свою очередь, формула для расчета элементов матрицы условной вероятности P(X/Y) имеет вид:
P(xi/yj)=P(xi,yj)/P(yj)(1.1.13)
Энтропия передаваемого сигнала H(X), бит/символ и принимаемого сигнала H(Y), бит/символ определяется соответственно по формуле:
(1.1.14)
(1.1.15)
Условные энтропии H(X/Y), бит/символ и H(Y/X), бит/символ рассчитываются соответственно по формулам:
(1.1.16)
(1.1.17)

Совместная энтропия H(X,Y), бит/символ находится по формуле:
(1.1.18)
Взаимная энтропия I(X,Y), бит/символ определяется по формуле:
(1.1.19)

Передача информации по каналу связи осуществляется со скоростью V, рассчитываемой по формуле:

V = 1000(A+1)(1.1.20)
Постоянную скорость передачи двоичных символов по каналу связи R, бит/с можно рассчитать по формуле:
R = V I(X,Y) / 3; (1.1.21)

Производительность источника , бит/с определяется по следующей формуле:
= (H(X) V)(1.1.22)
1.2 ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ
По условию варианта определены следующие постоянные:
m = 15;
r = 10;
Определим характеристики посылаемых символов.
Вероятности символов Vi(они же - вероятности кода Zi), генерируемых источником рассчитываем по формуле 1.1.1. Полученные значения вероятностей приведены в таблице 1.2.2.
Сначала вероятности строятся по убыванию. После этого все вероятности делятся на две группы так, чтобы в пределах каждой группы их значения были примерно одинаковыми. В старший разряд кодов, соответствующих первой группе вероятностей, записывается 1,для второй группы кодов – 0. Затем каждая из полученных подгрупп, в свою очередь, делится аналогичным образом. При прохождении цикла деления по одному разряду происходит переход на разряд вправо. Деление продолжается до тех пор, пока в каждой группе не окажется по одному коду.
Результаты разработки кодов показаны в таблице 1.2.1.
Таблица 1.2.1 - Вероятности и коды символов
Vi P(Vi) Zi L(Zi)
1 0.231 11 2
2 0.183 10 2
3 0.1408 011 3
4 0.1042 0101 4
5 0.0732 01001 5
6 0.0732 01000 5
7 0.0479 00111 5
8 0.0479 00110 5
9 0.0282 00101 5
10 0.0282 00100 5
11 0.0141 00011 5
12 0.0141 00010 5
13 0.0056 000011 6
14 0.0056 000010 6
15 0.0028 000000 6
Вычислим энтропию сообщения H(Z),бит/символ по формуле
1.1.2 :
H(Z) = 3.218 бит/символ
Среднюю длину неравномерного кода определим по формуле
1.1.3 :
Lср = 3.5652 бит
Максимальную энтропию неравномерного двоичного кода Zi определяем по формуле 1.1.4:
H(Z)max = 3.218 бит
По формуле 1.1.5 вычислим коэффициент эффективности Кэф неравномерного двоичного кода Zi:
Кэф = 0.903
Для расчета коэффициента избыточности Кизб воспользуемся формулой 1.1.6:
Кизб = 0.176
При простом кодировании повторением n=3 раз каждого двоичного сигнала сообщения Zi имеется два кода: Х1 и Х2, вероятности которых Р(Х1) и Р(Х2) находятся по формуле 1.1.7:
Р(Х1) = 0.4113 Р(Х2) = 0.5885
Вероятности возможных ошибок, при прохождении кода по каналу определяются по формулам 1.1.8 и 1.1.9 соответственно:
P10 = 0.3P01 = 0.2
Канальная матрица P(Y/X) со стороны приемника для кода Х0 и Х1, рассчитанная по формуле 1.1.10, приведена в таблице 1.2.3. Для проверки расчета в последнем столбце таблицы 1.2.3 приведена сумма по текущей строке. Значения вероятностей в таблице 1.2.3 приводятся в десятитысячных долях единицы.
Таблица 1.2.2 - Канальная матрица P(Y/X)
X Y сумма
000 001 010 100 011 101 110 111 000 8000 0667 0667 0667 0000 0000 0000 0000 10000
111 0000 0000 0000 0000 1000 1000 1000 1000 10000
В таблице 1.2.3 приведены значения элементов канальной матрицы совместной вероятности P(X,Y), определенные по формуле 1.1.11. Значения вероятностей в таблице 1.2.3 приводятся в десятитысячных долях единицы.
Таблица 1.2.3 - Матрица совместных вероятностей P(X,Y)
Х Y
000 001 010 100 011 101 110 111
000 3292 0274 0274 0274 0000 0000 0000 0000
111 0000 0000 0000 0000 0588 0588 0588 4119
Элементы матрицы вероятностей P(Y) находятся по формуле 1.1.12. Полученные данные приведены в таблице 1.2.4 в десятитысячных долях единицы. В последнем столбце для проверки приведена сумма по строке.
Таблица 1.2.4 - Матрица P(Y)
Y Сумма
000 001 010 100 011 101 110 111 3292 0274 0274 0274 0588 0588 0588 4119 10000
Рассчитав матрицы P(X,Y) и P(Y), можно вычислить элементы матрицы условной вероятности P(X/Y) по формуле 1.1.13. Матрица P(X/Y) приведена в таблице 1.2.6.
Рассчитываем энтропию передаваемого сигнала H(X) и энтропию принимаемого сигнала H(Y) по формулам 1.1.14 и 1.1.15 соответственно:
H(X) = 0.9777 бит/символ
H(Y) = 2.2025 бит/символ
Условные энтропии H(X/Y) и H(Y/X) рассчитаем, воспользовавшись формулами 1.1.16 и 1.1.17 соответственно:
H(X/Y) = 0.0000 бит/символ
H(Y/X) = 1.2244 бит/символ
Таблица 1.2.5 - Матрица P(X/Y)
X Y Сумма
000 111 000 1 0 1.0000
001 1 0 1.0000
010 1 0 1.0000
100 1 0 1.0000
011 0 1 1.0000
101 0 1 1.0000
110 0 1 1.0000
111 0 1 1.0000
По формуле 1.1.18 находим совместную энтропию H(X,Y):
H(X,Y) = 2.2014 бит/символ
Сделаем проверку полученных значений энтропий:
H(Y/X) + H(X) = 2.2025 бит/символ
H(X/Y) + H(Y) = 2.2025 бит/символ
Совпадение полученных значений свидетельствует о правильности найденных значений энтропий.
Определим значение взаимной энтропии I(X,Y), используя формулу 1.1.19:
I(X,Y) = 0.9777 бит/символ
Для отыскания следующих характеристик канала вычислим скорость передачи двоичных символов по каналу связи с помощью формулы 1.1.20:
V = 6000 символов/c
Информация передается по каналу связи с постоянной скоростью R, вычисляемой с помощью формулы 1.1.21:
R = 1956.1 бит/с
Производительность источника по формуле 1.1.22 равна:
= 5868.3 бит/с
Результатом работы программы являются графики числа ошибок восстановления информации от параметра n (n,1) – кода и от p01 и p10. При теоретическом расчёте мы предположили, что в канале нет ошибок. Действительно, полученное нулевое значение энтропии H(X/Y) также об этом свидетельствует.
Однако полученный график говорит о том, что это предположение становится соответствующим действительности только начиная со значений n, равных 20..25.
Примерный вид полученных графиков приведен на рисунках 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= fш (xi,yj) XOR fs (xi,yj) min( по всем шаблонам );
б) Корреляция между шаблоном и считываемым символом
R(,z)=x y fш (x,y) . fs (x - , 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 происходит рисование полученной рамки на картинке.
Распознавание по корреляции оформлено в основном блоке программы. В процессе распознавания происходит поочерёдное выделение минимально описанных прямоугольников вокруг “испорченных” помехами символов. Затем идет цикл сравнения очередного символа со всеми шаблонами. После проверки того, что символ по размерам не меньше очередного шаблона, идет вычисление корреляционной функции. Если символ больше шаблона, то вычисляется несколько значений со смещениями по x и y, а затем из них берётся максимальное. Полученные значения сравниваются между собой. Номер шаблона, с которым получено наибольшее сходство, и будет распознанным символом.
ЗАКЛЮЧЕНИЕ

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

ЛИТЕРАТУРА
1. Теоретические основы информационной техники/Темников Ф.Е.и др.- М.:Энергия, 1971
2. Орлов В.А., Филлипов Л.И. Теория информации в упражнениях и задачах. - М.:Высш.шк., 1976
3. Сигорский В.П. Математический аппарат инженера - Киев:Техника, 1975
4. Солодов А.В. Теория информации и её
применение к задачам автоматического управления и контроля - М.: Наука, 1967.
2.3 ВЫВОД
Во второй части была рассмотрена модель распознавания, основанная на шаблонной классификации. Программное моделирование показало неплохие результаты. Модель распознаёт строку практически в 100% случаев при уровне помех до 40%. Однако данный подход может использоваться только в том случае, если заранее известно, что распознаваемые символы будут одинакового шрифта.
ПРИЛОЖЕНИЕ А

Текст программы моделирования канала связи.
Program final_of_work;
uses crt,graph;
const a=5;
b=0;
m=10+(a mod 6); {15}
r=trunc((m+a-b)/2); {10}
var
n, {n для (n,1) - кода}
temp,ent,out,symb,decode:byte; {буферы для кодирования}
p:array[1..m] of real; {вероятности}
p01,p10:real; {p единичной ошибки}
z,dl:array[1..m] of byte; {код, длина кода}
mask: array[1..8] of byte; {маски для декодирования}
data_n,data_p
:array[1..100] of integer; {данные для графика}
i,j, {счетчики}
count_of_errors, {счетчик ошибок восстановления}
dlina,sh, {длина массива сообщений}
count:integer; {счетчик для построения графика}
range,c,s,l:byte;
fl:boolean;
function flag(px:real):boolean;
{---осуществляет событие с вероятностью p---}
var ww,wq : word;
begin
ww := round(px * 100);
wq := random(100);
if ww > wq then flag := true else flag := false;
end;
procedure ver; {------------расчет вероятностей---------}
var s,i3,j3: integer;
tmp,s1:real;
begin
s:=0;tmp:=0; {вычисляем вероятности}
for j3:=1 to m do
s:=s+sqr(j3-r);
s:=s+m;
for i3:=1 to m do
p[i3]:=(1+sqr(i3-r))/s;
{-------упорядочиваем вероятности--------}
for i3:=1 to m-1 do {внешний цикл}
begin
tmp := p[i3]; {локальный максимум}
for j3:=i3 to m do
if p[j3] >= tmp then
begin
tmp := p[j3]; {максимум на i шаге}
s:=j3 {его номер}
end;
p[s] := p[i3]; {обмен}
p[i3] := tmp
end;
end;
procedure deranges; {----------внесение помех------------}
var tmp : byte;
c0,c1 : integer; {счетчики 0 и 1 для декодирования}
begin
out := 0; {выходной код после помех}
for i := 0 to 7 do {цикл по разрядам}
begin
c0 := 0; {сброс счетчиков}
c1 := 0;
tmp := (z[ent] shr i) and 1; {выделяем разряд}
for j := 1 to n do {цикл по разрядам (n,1)-кода}
case tmp of {определяемм помеху}
0 : if flag(p01) then inc(c1) else inc(c0);
1 : if flag(p10) then inc(c0) else inc(c1)
end;
if c1 > c0 then out := out or (1 shl i)
end; {вносим помеху в выходной код}
end;
procedure set_codes; {-----по алгоритму Шеннона - Фэно-----}
var i3,j2 : byte;
function numb(v:real):byte;{номер вероятности, находящейся}
var i2 : byte; {"" той, что передается как параметр}
begin
for i2 := 1 to m do {цикл по вероятностям}
if(v >= p[i2 + 1]) and (v <= p[i2]){если нашли границы}
then
numb := i2; {присваиваем номер "верхнего"}
end;
begin {-------------of procedure------------}
for i := 1 to m do {обнуляем коды и длины}
begin
z[i] := 0;
dl[i] := 0
end;
range := 8; {разряд - в максимальное значение}
c := 0; {счетчик по "вертикали" - на начало}
repeat {внешний цикл по кодам......}
if c = 0 {если в начале...}
then
dec(range); {... уменьшаем текущий разряд}
inc(c); {увеличиваем внутренний счетчик}
if (z[c] = z[c + 1]) and (c <= m)
{если два кода равны...}
then
begin {...то цикл деления}
fl := false; {флаг дальнейшего деления}
i := c; {"верхняя" граница}
j := c + 1; {"нижняя" граница}
if (z[j] = z[j + 1]) or (j + 1 < m)
{если ещё есть равные...}
then
fl := true; {...то ещё делим}
while fl do {пока можно делить...}
begin
inc(j); {...увеличиваем нижнюю границу}
if (z[j] <> z[j - 1]) or (j > m - 1) then
fl := false
end;
if((j - i) > 1) and (j < m)
{если > 2 элементов...}
then
dec(j); {...корректируем нижнюю границу}
s := numb((p[i] + p[j])/2); {делим}
if p[i] = p[j] {если два элемента...}
then
s := i; {середину - на "верхний"}
if j <= m {если не за пределами кодов...}
then
for l := i to j do {...цикл по группе}
if l <= s then {устанавливаем коды и длины}
begin
z[l] := z[l] or (1 shl range);
dl[l] := dl[l] + 1
end
else
dl[l] := dl[l] + 1;
if j < m then {устанавливаем текущий счетчик}
c := j
else
c := 0
end
else if c = m then c := 0;
until range = 0;{...пока не дойдем до последнего разряда}
{--------------инициализация масок--------------}
temp := 0;
for i := 1 to 8 do
begin
temp := temp or (1 shl (7 - (i - 1)));
mask[i] := temp
end
end;
function sourse:byte; {-----генерирует число из 1..15-----}
var cou : byte;
tu,ttu : real;
begin
cou := 1; {начальное значение}
ttu := p[cou]; {случайное число из 0..1}
tu := random;
while ttu < tu do begin {пока не превысили random...}
inc(cou);
ttu := ttu + p[cou]; {увеличиваем счетчик}
end;
sourse := cou; {присваиваем число из 1..15}
end;
procedure decoder; {---для неравномерного кода---}
var
code:byte;
begin
code:=out;
for i:=1 to 8 do {цикл со старшего разряда}
begin
temp:=code and mask[i]; {выделяем код}
for j:=1 to m do
if (temp=z[j]) and (i=dl[j]){если совпадает}
then
decode:=j; {...декодируем}
end;
end;
procedure graphiki; {-----------построение графика----------}
const x0=250; {начало координат}
y0=400;
var nn,ss,ii:integer;
sr:string;
driver,mode,errcode:integer;
begin
driver:=detect;
initgraph(driver, mode,''); {инициализация графики}
errcode:=graphResult;
if errcode<>grOk then
begin
Writeln(' Ошибка графики. ');
writeln(GraphErrorMSG(Errcode));
halt
end;
setcolor(white); {контуры фигур и текст}
line(x0,y0,x0,y0-300); {------ось y-----}
line(x0,y0,x0+200,y0); {------ось x-----}
SetTextStyle(DefaultFont, HorizDir, 1); {установка шрифта}
OutTextXY(x0,y0+40,'Количество повторений , n');
SetTextStyle(DefaultFont, VertDir, 1);
SetTextJustify(LeftText,TopText);{--способ выравнивания--}
OutTextXY(x0-50,180,'Количество ошибок , %');
SetTextStyle(DefaultFont, HorizDir, 1);
for i:=1 to 5 do
line(x0+i*35,y0,x0+i*35,y0-5);{делительные штрихи оси x}
outtextxy(x0+35,y0+10,'20');
outtextxy(x0+5*35,y0+10,'100');
for i:=1 to 4 do
line(x0,y0-i*65,x0+5,y0-i*65);{делительные штрихи оси y}
outtextxy(x0-20,y0-65,'15');
outtextxy(x0-20,y0-3*65,'45');
for nn:=1 to 33 do
begin {рисуем график}
setcolor(2);
line(x0+(nn+1)*5,round((y0-data_n[nn])),
x0+(nn+2)*5,round((y0-data_n[nn+1])));
end;
setcolor(15);
outtextxy(50,460,'Press any key...');
readkey;
ClearViewPort;
line(x0,y0,x0,y0-360); {------ось y-----}
line(x0,y0,x0+200,y0); {------ось x-----}
SetTextStyle(SmallFont, HorizDir, 5); {---установка шрифта--}
OutTextXY(x0,y0+40,'Значения p01 и p10 , %');
SetTextStyle(SmallFont, VertDir, 5);
SetTextJustify(LeftText,TopText); {-----способ выравнивания-----}
OutTextXY(x0-50,140,'Количество ошибок , %');
SetTextStyle(DefaultFont, HorizDir, 1);
for i:=1 to 5 do
line(x0+i*35,y0,x0+i*35,y0-5); {----делительные штрихи оси x---}
outtextxy(x0+35,y0+5,'20');
outtextxy(x0+5*35,y0+5,'100');
for i:=1 to 4 do
line(x0,y0-i*75,x0+5,y0-i*75); {----делительные штрихи оси y---}
outtextxy(x0-25,y0-75,'25');
outtextxy(x0-25,y0-2*75,'50');
outtextxy(x0-25,y0-3*75,'75');
outtextxy(x0-25,y0-4*75,'100');
{line(x0,y0-4*75,x0+200,y0-4*75);}
setcolor(2);
for nn:=1 to 13 do
{рисуем график}
line(x0+(nn+1)*12,round((y0-data_p[nn])),
x0+(nn+2)*12,round((y0-data_p[nn+1])));
end;
{=====================ОСНОВНОЙ БЛОК=======================}
Begin
clrscr;
p10:=0.2+0.02*a;
p01:=0.2+0.02*b;
randomize; {--инициализация генератора случайных чисел--}
ver; {инициализация и упорядочивание вероятностей}
set_codes; {--------инициализация кодов---------}
TextColor(15);
gotoxy(10,1);
write('ПАРАМЕТРЫ КАНАЛА :');
gotoxy(1,2);write('Вероятности одиночных ошибок :');
gotoxy(3,5);write('при передаче нуля : ',p01:4:3);
gotoxy(3,6);write('при передаче единицы : ',p10:4:3);
gotoxy(40,1);write('НЕРАВНОМЕРНЫЕ КОДЫ СООБЩЕНИЙ : ');
for i := 1 to m do {--------вывод кодов--------}
begin
gotoxy(45,1+i);
write(' z(',i,') = ');
gotoxy(55,1+i);
for j := 1 to dl[i] do
write((z[i] shr (8 - j)) and 1); {побитно}
end;
gotoxy(10,19);
write('Ввести длину передаваемого массива сообщений : ');
read(dlina);
write(' Ввести n для (n,1) - кода : ');
read(n);
count_of_errors := 0;
for sh := 1 to dlina do
begin {--------передача сообщений----------}
ent := sourse; {--случайное сообщение из ансамбля---}
deranges; {-----------внесение помех-----------}
decoder; {----декодирование двоичного кода----}
if ent <> decode then inc(count_of_errors);
end;
gotoxy(10,23);
write('РЕЗУЛЬТАТ ПЕРЕДАЧИ СООБЩЕНИЙ : ');
TextColor(12);
write( 'КОЛИЧЕСТВО ОШИБОК = ',count_of_errors);
TextColor(15);
gotoxy(10,24);
write('Please wait...');
{---------расчет count_of_errors для разных n-----------}
n := 0;count := 0;dlina := 100;
repeat
n := n + 3;
inc(count);
count_of_errors := 0;
for sh := 1 to dlina do
begin
ent := sourse;
deranges;
decoder;
if ent <> decode then inc(count_of_errors);
end;
data_n[count] := round(count_of_errors*3) ;
until n >= 96;
{---расчет count_of_errors для разных p01 и p10---}
n:=3;count:=0;dlina := 100;p01:=0;p10:=0;
repeat
p01:=p01+0.07;
p10:=p10+0.07;
inc(count);
count_of_errors := 0;
for sh := 1 to dlina do
begin
ent := sourse;
deranges;;
decoder;
if ent <> decode then inc(count_of_errors);
end;
data_p[count] := round(count_of_errors*3) ;
until p01 >= 0.98;
gotoxy(10,24);
writeln('Press any key to continue...');
readkey;
graphiki;
readkey;
closegraph;
End.
ПРИЛОЖЕНИЕ Б

Текст программы распознавания символов
Program Final_of_work;
uses graph;
const BiH=50; {-------высота картинки в пикселях------}
BiW=160; {-------ширина картинки в пикселях------}
stroka:array[1..10] of char=
('I','h','i','G','F','k','H','g','J','j');
{-----эталонная строка для установления соответствия-----}
type arr=array[1..BiW,1..BiH] of byte; {тип массива-картинки}
const
path0='work.bmp'; {путь к bmp-файлу с исходной строкой}
var file0,file1:file of byte; {файловые переменные для связи}
counter, {счетчик текущей позиции распознавания}
rasp:byte; {номер текущего распознанного символа}
f0, {массив с эталонной картинкой}
f:arr; {массив с картинкой, содержащей помехи}
x,y, {счетчики хода по массивам}
xmin, ymin,xmax, ymax , {минимально описанный прямоугольника}
xt, {текущая позиция x при движении по картинке}
xsav,{для сохранения текущего x при использовании корреляции}
i,j, {вспомогательные счетчики}
xm,xk,ym,yk,
{для сохранения текущего м.о.п. при использовании корреляции}
k,{счетчик шаблонов при использовании корреляции}
di,dj : integer;
{смещения шаблона и символа по x и y при наложении}
flag :boolean; {признак отображения на экране рамки}
kfmax, {глобальный максимум корреляции для символа}
max, {значение корреляции для текущего шаблона}
kf, {текущая переменная для вычисления корреляции}
smin:longint; {минимально возможная площадь шаблона}
Procedure Init_Graph_Mode; {-----инициализация графики-----}
var
Driver, {код драйвера графического устройства}
Mode, {код графического режима}
TestDriver, {внутренний номер драйвера в таблице BGI}
ErrCode: Integer; {код ошибки}
function TestDetect: Integer; far;
{функция определения параметров графического режима драйвера}
{полный адрес точки входа в функцию, т.е. = сегмент+смещение}
begin
TestDetect := 3; {разрешение экрана 800*600 точек}
end;
begin
TestDriver := InstallUserDriver('svga256', @TestDetect);
{устанавливает новый драйвер в таблицу BGI}
if GraphResult <> grOk then
begin
Writeln('Ошибка при установке драйвера:',
GraphErrorMSG(ErrCode));
Halt(1);
end;
Driver := Detect;{автоматическое определение драйвера-SVGA}
InitGraph(Driver, Mode, '');
{инициализация графического режима;}
{драйвер - в текущем каталоге}
ErrCode := GraphResult;
if ErrCode <> grOk then
begin
Writeln('Ошибка графического режима:',
GraphErrorMSG(ErrCode));
Halt(1);
end;
SetTextStyle(DefaultFont, HorizDir, 1); {текущий шрифт}
OutTextXY(120,20,'Идет инициализация графического режима...');
for x := 0 to 255 do {инициализация палитры grayscale}
SetRGBPalette(x,x,x,x);
OutTextXY(450,20,'Ok.');
end;
Procedure showlist(xn,yn:integer);
{---отображение картинки c масштабированием в 9 раз---}
{xn,yn-начало координат при отображении}
begin
x := 1; {текущие координаты-в начало}
y := 1;
repeat {внешний цикл-по высоте}
for i := -1 to 1 do
for j := -1 to 1 do {текущий пиксель - окном 3*3}
PutPixel((3*x+i)+xn,(3*BiH-3*y+j)+yn,f[x,y]);
x := x + 1; {приращение по x}
if x = BiW then {если с краю...}
begin
x := 1; {...то переходим в следующий ряд}
y := y + 1
end;
until y = BiH; {пока не окажемся в последней строке}
end;
procedure Init_Data; {-----заполнение массивов данных-----}
var t:byte;
begin
assign(file0,path0);
reset(file0);
seek(file0,$436);
for y:=1 to BiH do
for x:=1 to BiW do
begin
read(file0,t); {заполняем массив шаблонов}
f0[x,y]:=t;
end;
for x := 1 to BiW do{заполняем массив для внесения помех}
for y := 1 to BiH do
f[x,y]:=f0[x,y];
end;
Procedure Deranges; {-----------внесение помех-----------}
const u=20; {---уровень помех в % от общего веса символов---}
var count, {количество внесенных помех}
w : integer; {суммарный вес символов}
begin
count := 0;
w:=0;
randomize; {инициализация генератора случайных чисел}
for x := 1 to BiW do {подсчитываем суммарный вес}
for y := 1 to BiH do
if f[x,y] = 0 then w:= w+1;
repeat {------вносим помехи...------}
x := random(BiW); {случайные координаты}
y := random(BiH);
if (x in [3..BiW-2]) and (y in [3..BiH-2]) then
begin
if (f[x,y] = 255) then {если на белом фоне...}
f[x,y] := 1; {...то черная точка}
if (f[x,y] = 0) then {если на черном фоне...}
f[x,y] := 255 {...то белая точка}
end;
count := count + 1; {ув. счетчик помех}
until 100*count >= u * w; {пока не получим данный уровень}
for x := 1 to BiW do {перекрашиваем в 0-й цвет}
for y := 1 to BiH do
if f[x,y] = 1 then
f[x,y] := 0
end;
Procedure Filter; {-----фильтрация изображения от помех-----}
{специальные маски для удаления помех;}
{если при наложении маска совпала с фрагментом изображения,}
{то изменяем соответствующие пиксели}
const mask1:array[1..4,-1..1,-1..1] of byte =
(((1,1,0),(1,0,0),(1,1,0)),
((1,1,1),(1,0,1),(0,0,0)),
((0,1,1),(0,0,1),(0,1,1)),
((0,0,0),(1,0,1),(1,1,1)));
{для удаления помех, "залезших" на символ}
mask2:array[5..12,-2..2,-2..2] of byte =
(((0,0,0,0,0),(0,0,0,0,0),(0,0,1,0,0),(0,1,0,0,0),(0,0,0,0,0)),
((0,0,0,0,0),(0,0,0,0,0),(0,1,1,0,0),(0,0,0,0,0),(0,0,0,0,0)),
((0,0,0,0,0),(0,1,0,0,0),(0,0,1,0,0),(0,0,0,0,0),(0,0,0,0,0)),
((0,0,0,0,0),(0,0,1,0,0),(0,0,1,0,0),(0,0,0,0,0),(0,0,0,0,0)),
((0,0,0,0,0),(0,0,0,1,0),(0,0,1,0,0),(0,0,0,0,0),(0,0,0,0,0)),
((0,0,0,0,0),(0,0,0,0,0),(0,0,1,1,0),(0,0,0,0,0),(0,0,0,0,0)),
((0,0,0,0,0),(0,0,0,0,0),(0,0,1,0,0),(0,0,0,1,0),(0,0,0,0,0)),
((0,0,0,0,0),(0,0,0,0,0),(0,0,1,0,0),(0,0,1,0,0),(0,0,0,0,0)));
{для удаления групп одиночных помех}
mask3:array[13..14,-2..2,-1..1] of byte =
(((1,0,0),(1,0,0),(1,1,0),(1,0,0),(1,0,0)),
((0,0,1),(0,0,1),(0,1,1),(0,0,1),(0,0,1)));
mask4:array[15..16,-1..1,-2..2] of byte =
(((1,1,1,1,1),(0,0,1,0,0),(0,0,0,0,0)),
((0,0,0,0,0),(0,0,1,0,0),(1,1,1,1,1)));
{для удаления помех, "пристроившихся" к символу}
var m,n,l : integer; {вспомогательные счетчики}
flg : boolean; {признак выхода из цикла}
su : array[1..16] of longint; {массив сумм для масок}
begin
for i := 3 to BiW-2 do {внешний цикл по изображению}
for j := 3 to BiH-2 do
begin
l := 0; {если белая точка окружена черными...}
for m:=-1 to 1 do
for n:= -1 to 1 do
l := l + f[i+m,j+n];
if (l = 255) and (f[i,j] = 255) then
f[i,j] := 0; {...то делаем и её черной}
{если черная точуа окружена белыми...}
if (l >= 255*8) and (f[i,j] = 0) then
f[i,j] := 255; {...то делаем и её белой}
{обнуляем суммы для масок}
for l := 1 to 16 do
su[l] := 0;
{суммируем по всем видам масок}
for l := 1 to 4 do
for m:=-1 to 1 do
for n:= -1 to 1 do
su[l] := su[l] + ((not f[i+m,j+n]) xor mask1[l,m,n]) and 1;
for l := 5 to 12 do
for m:=-2 to 2 do
for n:=-2 to 2 do
su[l] := su[l] + ((not f[i+m,j+n]) xor mask2[l,m,n]) and 1;
for l := 13 to 14 do
for m:=-2 to 2 do
for n:=-1 to 1 do
su[l] := su[l] + ((not f[i+m,j+n]) xor mask3[l,m,n]) and 1;
for l := 15 to 16 do
for m:=-1 to 1 do
for n:=-2 to 2 do
su[l] := su[l] + ((not f[i+m,j+n]) xor mask4[l,m,n]) and 1;
{---проверяем по очереди каждый вид масок---}
{для первого вида - зачерняем центральную точку}
l := 0;
flg := false;
repeat
l := l + 1;
if su[l] = 0 then
flg := true;
until (flg) or (l = 4);
if flg then
f[i,j] := 0;
{для второго - делаем белым окно 3*3}
l := 4;
flg := false;
repeat
l := l + 1;
if su[l] = 0 then
flg := true;
until (flg) or (l = 12);
if flg then
for m := -2 to 2 do
for n := -2 to 2 do
f[i+m,j+n] := 255;
{для третьего и четвертого - делаем белой центральную точку}
l := 12;
flg := false;
repeat
l := l + 1;
if su[l] = 0 then
flg := true;
until (flg) or (l = 16);
if flg then
f[i,j] := 255;
end
end;
{-----------минимально описанный прямоугольник----------}
procedure ramka(zx:arr;flagx:boolean);
var
c : integer; {счетчик черных точек}
begin
xmin:=BiW;xmax:=0;ymin:=BiH;ymax:=0;
{начальные значения координат м.о.п.}
c:=0; {начальное значение счетчика}
xt := xt + 1; {сдвигаем текущую координату}
repeat {цикл увеличения xt по картинке...}
xt := xt + 1;
for y := 3 to BiH-2 do {просмотр по высоте}
if zx[xt,y] = 0 then
c:= c+1;
until (c <> 0) or (xt > BiW - 6);
{...пока не встретим черную точку}
c:= 0; {начальное значение счетчика}
repeat {цикл по символу...}
c := 0;
for y := 3 to BiH - 2 do {просмотр по высоте}
if zx[xt,y] = 0 then {если черная точка...}
begin
c:=c+1; {...то ув. счетчик}
if xt < xmin then xmin := xt; {изм.коорд.м.о.п.}
if xt > xmax then xmax := xt;
if y < ymin then ymin := y;
if y > ymax then ymax := y
end;
if xt <> 0 then xt := xt + 1; {ув. текущий x}
until (c=0) or (xt > BiW - 2);{...пока не дойдем до белого}
if flagx then {если признак...}
begin {...то рисуем рамку;100-цвет}
for x:=xmin-1 to xmax+1 do f[x,ymin-1]:=100;
for x:=xmin-1 to xmax+1 do f[x,ymax+1]:=100;
for y:=ymin-1 to ymax+1 do f[xmin-1,y]:=100;
for y:=ymin-1 to ymax+1 do f[xmax+1,y]:=100
end
end;
{=====================ОСНОВНОЙ БЛОК=======================}
BEGIN
Init_Graph_Mode;
OutTextXY(120,30,'Идет инициализация данных... ');
Init_Data;
OutTextXY(345,30,'Ok.');
flag := false;
smin:=BiH*BiH; {max возможная площадь символа}
For counter := 1 to 10 do {цикл по шаблонам}
begin {определяем min возможную площадь символа}
Ramka(f0,flag);
if (xmax-xmin)*(ymax-ymin) <= smin then
smin:= (xmax-xmin)*(ymax-ymin)
end;
OutTextXY(300,50,'Исходная строка символов : ');
Deranges;
ShowList(170,70);
Filter;
OutTextXY(270,260,'Строка символов после фильтрации : ');
xt := 2;
ShowList(170,280);
OutTextXY(120,500,'Идет распознавание строки символов : ');
SetTextStyle(DefaultFont, HorizDir, 4);
flag := true; {рисовать рамку}
counter := 0;
Repeat {---цикл по картинке с помехами---}
counter := counter + 1;{текущий символ}
Ramka(f,flag);
{---------Распознавание по корреляции---------}
kfmax:=0; {min возможное значение Kf}
xsav:=xt; {сохраняем текущий x в картинке с помехами}
xm:=xmin; {сохраняем текущие координаты м.о.п.}
xk:=xmax;
ym:=ymin;
yk:=ymax;
xt:=2; {текущий x - в начало картинки с шаблонами}
for k := 1 to 10 do {---цикл по шаблонам---}
begin
Ramka(f0,not flag);
di:=0; {смещение шаблона и символа по x}
dj:=0; {смещение шаблона и символа по y}
max:=0; {min возможное значение текущей Kf}
if (xk-xm >= xmax-xmin) and (yk-ym >= ymax-ymin)
{если шаблон <= текущего символа...}
then {...тогда сравниваем с текущим шаблоном}
repeat
kf:=0; {min возможное значение temp - Kf}
{---цикл по текущему шаблону---}
for i:=xmin to xmax do
for j:=ymin to ymax do
kf := kf +
(f0[i+di,j+dj] * f[i-xmin+xm,j-ymin+ym]) and 1;
if kf > max then max := kf; {локальный max}
di:=di+1; {ув. смещение по x}
if xmax-xmin+di>=xk-xm {если сместили по x}
then {...то смещаем по y}
begin
di:=0;
dj:=dj+1
end;
until (ymax-ymin+dj>=yk-ym);
{...пока не сместим по y}
if max > kfmax {ищем глобальный max...}
then
begin
kfmax:=max;
rasp:=k {...и его номер}
end
end;
xt:=xsav; {восстанавливаем текущий x}
ShowList(170,280);
if (xk-xm)*(yk-ym) >= smin{если допустимая площадь}
then {...то выводим распознанный символ}
OutTextXY(190 + 35*counter,520,stroka[rasp]);
Until xt >= BiW - 15;
ShowList(170,280);
ReadLn;
CloseGraph; {сбрасываем графичесий режим}
END.

Приложенные файлы


Добавить комментарий