Кодирование и шифрование информации в системах связи. Часть 1. Кодирование

81

следовательно, максимальная длина кода равна log2 (объем словаря в байтах).

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

Кодирование фразы алгоритмом LZ77 со следующими размерами СЛОВАРЬ/БУФЕР Таблица 2.3. Варианты расчетных заданий

Используем ввод фразы с клавиатуры в программе LZ77.EXE для разных размеров словаря/буфера:

Рис. 2.9. Ввод фразы с клавиатуры для размеров 8/5

82

Рис. 2.10. Ввод фразы с клавиатуры для размеров 12/5

Рис. 2.11. Ввод фразы с клавиатуры для размеров 12/8

Рис. 2.12. Ввод фразы с клавиатуры для размеров 16/8

Используем ввод текста из файла для разных размеров словаря/буфера:

Текст: «Полуадаптированное моделирование pешает эту проблему, используя для каждо-

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

вание сжатого текста, модель должна быть пеpедана pаскодиpовщику. Несмотря на до-

полнительные затpаты по передаче модели, эта стpатегия в общем случае окупается бла-

годаря лучшему соответствию модели тексту.

Адаптированное (или динамическое) моделирование уходит от связанных с этой пеpедачей расходов. Первоначально и кодировщик, и раскодировщик присваивают себе некоторую пустую модель, как если бы символы все были равновероятными. Кодировщик

83

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

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

Адаптированные модели представляют собой элегантную и эффективную технику, и

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

Рис. 2.13. Ввод текста из файла для размеров 32/5

Рис. 2.14. Ввод текста из файла для размеров 64/5

84

Рис. 2.15. Ввод текста из файла для размеров 80/5

Рис. 2.16. Ввод текста из файла для размеров 128/5

Таблица 2.4. Результаты измерений

85

Рис. 2.17. График зависимости коэффициента сжатия от размера словаря Кодирование для разной длины текста и одинакового размера словаря 64/5:

Рис. 2.18. Ввод текста длиной 39 байт

Рис. 2.19. Ввод текста длиной 452 байта

86

Рис. 2.20. Ввод текста длиной 1488 байт

Рис. 2.21. Ввод текста длиной 4292 байта Таблица 2.5. Результаты измерений

Рис. 2.22. График зависимости коэффициента сжатия от размера словаря При кодировании коротких текстов коэффициент сжатия оказывается меньше 1, т.е.

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

87

большом размере словаря снижается скорость кодирования. При увеличении размера текста

коэффициент сжатия увеличивается.

2.4. Фрактальные методы кодирования изображений

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

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

Фрактал (лат. fractus — дроблёный, сломанный, разбитый) — геометрическая фигура,

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

[14]. Слово «фрактал» может употребляться не только как математический термин.

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

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

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

Фракталы, особенно на плоскости, популярны благодаря сочетанию красоты с простотой построения при помощи компьютера. Первые примеры самоподобных множеств с необычными свойствами появились в XIX веке (например, множество Кантора). Термин

«фрактал» был введён Бенуа Мандельбротом в 1975 году и получил широкую популярность с выходом в 1977 году его книги «Фрактальная геометрия природы».

88

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

Рис. 2.23. Доменный и ранговый блоки Область большого размера называется доменным блоком, а меньшего – ранговым

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

v– сдвиг по яркости.

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

зеркального отражения и поворота зеркального отражения.

Из всех возможных доменных блоков выбирается блок, ближайший (в выбранной метрике) к рассматриваемому ранговому блоку.

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

Ниже, на рисунке 2.32. ,представлен алгоритм фрактального сжатия.

89

Рис. 2.24. Алгоритм фрактального сжатия

Программное обеспечение в DELPHI 7

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

В нее можно загружать любые изображения, но размер должен быть не более 512х512

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

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

Основные характеристики:

Сжатие и декодирование изображений формата .bmp;

Просмотр полученного результата;

Просмотр размер полученного изображения.

90

На рисунке 2.35. представлено главное и единственное меню программы.

Рис. 2.25. Главное меню программы.

В программе доступны для изменения 2 следующих пункта: смещение домена и размер региона.

Смещение домена: Определяет шаг поиска участка в доменном изображении.

Минимальный шаг равен 1. Чем больше шаг, тем быстрее выполняется поиск, но при этом могут быть пропущены важные детали изображения.

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

тем хуже качество и при этом уменьшается размер IFS-изображения.

Методика работы в программе и проведение исследования основных

технических характеристик системы

Для обеспечения фрактального сжатия была выбрана программа «Фрактальное сжатие /

распаковка растровых изображений».

Для того чтобы начать работать с программой необходимо:

1.Загрузить изображение, которое удовлетворяет требование программы;

2.Выставить значение параметров «Смещение домена» и «Размер региона»;

3.Нажать кнопку старт;