Теория распознавания
презентация к уроку на тему

Слайд 1

Теория распознавания Сжатие, кодирование , архивация.

Слайд 2

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

Слайд 3

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

Слайд 4

МЕТОДЫ распознавания : Для оптического распознавания образов можно применить метод перебора вида объекта под различными углами, масштабами, смещениями и т. д. Для букв нужно перебирать шрифт, свойства шрифта и т. д. Второй подход — найти контур объекта и исследовать его свойства (связность, наличие углов и т. д.) Ещё один подход — использовать искусственные нейронные сети . Этот метод требует либо большого количества примеров задачи распознавания (с правильными ответами), либо специальной структуры нейронной сети, учитывающей специфику данной задачи.

Слайд 5

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

Слайд 6

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

Слайд 7

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

Слайд 8

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

Слайд 9

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

Слайд 10

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

Слайд 11

Если приблизительные характеристики энтропии потока данных предварительно известны, может быть полезен более простой статический код, такой как унарное кодирование , гамма-код Элиаса , код Фибоначчи , код Голомба или кодирование Райса . Согласно теореме Шеннона , существует предел сжатия без потерь, зависящий от энтропии источника. Чем более предсказуемы получаемые данные, тем лучше их можно сжать. Случайная независимая равновероятная последовательность сжатию без потерь не поддаётся.

Слайд 12

Большинство алгоритмов сжатия базируется на последовательной схеме сжатия Лемпеля-Зива ( Lempel-Ziv , 1977). Этот алгоритм используется, в частности, стандартной процедурой UNIX Compress . Алгоритмы словарного сжатия Зива-Лемпела появились во второй половине 1970-х годов. Это были так называемые алгоритмы LZ77 и LZ78, разработанные совместно Зивом ( Ziv ) и Лемпелом ( Lempel ). Методы Лемпела-Зива

Слайд 13

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

Слайд 14

Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.

Слайд 16

Алгоритм был реализован в программе compress , которая стала более или менее стандартной утилитой Unix-систем приблизительно в 1986 году. Несколько других популярных утилит-архиваторов также используют этот метод или близкие к нему . В 1987 году алгоритм стал частью стандарта на формат изображений GIF . Он также может (опционально) использоваться в формате TIFF . В настоящее время, алгоритм содержится в стандарте PDF .

Слайд 17

Особенности программ-архиваторов Если коды алгоритмов типа LZ передать для кодирования (адаптивному) алгоритму Хаффмена или арифметическому, то полученный двухшаговый (конвейерный, а не двухпроходный) алгоритм даст результаты сжатия подобные широко известным программам: GZIP, ARJ , PKZIP , ...

Слайд 18

Большинство программ-архиваторов сжимает каждый файл по отдельности, но некоторые сжимают файлы в общем потоке, что дает увеличение степени сжатия, но одновременно усложняет способы работы с полученным архивом, например, замена в таком архиве файла на его более новую версию может потребовать перекодирования всего архива. Примером программы, имеющей возможность сжимать файлы в общем потоке, является RAR. Архиваторы ОС Unix ( gzip , bzip2, ...) сжимают файлы в общем потоке практически всегда.

Слайд 19

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