Содержание к диссертации
Введение
ГЛАВА 1. Кодирование источников данных типа «аналоговый сигнал» 14
Линейно-предсказывающее кодирование 14
Прямое преобразование 14
Обратное преобразование 15
Пути увеличения скорости схатия 16
Увеличение скорости разжатия
Пути улучшения степени сжатия
Субполосное кодирование 23
Прямое преобразование 24
Обратное преобразование 25
Пути улучшения степени сжатия 25
ГЛАВА 2. Методы обхода плоскости 31
Змейка (зигзаг-сканирование) 31
Обход строками 31
Строками с разворотами 31
Обход полосами 32
Полосами с разворотами 32
Обход решетками 33
С учетом значений элементов 33
Контурный обход 33
С неизвестными контурами 34
Другие методы 35
«Квадратная змейка» 35
По спирали 37
Общее для всех случаев 38
Прямоугольных 38
Сложной формы 38
ГЛАВА 3. Обобщенные методы сортирующих преобразований 39
Сортировка параллельных блоков 39
Основной алгоритм преобразования 40
Обратное преобразование 41
Пути увеличения скорости сжатия 42
Увеличение скорости разжатия 44
Пути улучшения сжатия 44
Фрагментирование 46
Основной алгоритм преобразования 48
Пути улучшения скорости 49
Пути улучшения сжатия 50
ГЛАВА 4. Кодирование источников данных без памяти 53
Разделение мантисс и экспонент 53
Прямое преобразование 53
Обратное преобразование 55
Пути увеличения степени сжатия 56
Пути увеличения скорости сжатия и разжатия 61
Нумерующее кодирование 62
Векторное квантование 64
Прямое преобразование 65
Увеличение скорости сжатия 66
ГЛАВА 5. Методы сжатия изображений без потерь с помощью сортировки параллельных блоков 67
Первичная обработка 69
Поворот 69
Перестановка компонент 70
Сдвиг нуля 70
Преобразование компонент 70
Контекстная обработка 72
Улучшенное преобразование компонент 72
Субполосное Кодирование (СК) 73
Линейно-Предсказывающее Кодирование (ЛПК) 73
Перестановка битов 75
Обход плоскости 76
PBS, Сортировка параллельных блоков 77
Выводы 79
Приложения 80
- Пути улучшения степени сжатия
- «Квадратная змейка»
- Нумерующее кодирование
- Линейно-Предсказывающее Кодирование (ЛПК)
Введение к работе
Актуальность темы. В течение последних двадцати лет наблюдается стремительное увеличение количества используемых компьютеров, сопровождаемое неуклонным ростом их возможностей. Это привело к значительному расширению как круга пользователей ЭВМ, так и сферы применения компьютеров. Одновременное развитие телекоммуникационных систем, рост пропускной способности и общего количества линий связи, появление и развитие глобальных компьютерных сетей, в настоящее время доступных сотням миллионов пользователей, вызвали быстрое увеличение объемов хранимой и передаваемой информации.
В связи с продолжающимся ростом глобальных сетей и расширением спектра предоставляемых ими услуг при экспоненциальном росте числа пользователей сетей, а также успешно выполняемыми проектами по переводу в цифровой вид содержимого огромных хранилищ информации, в частности библиотек, выставочных залов и художественных галерей, следует ожидать, что объемы хранимой и передаваемой по системам связи информации будут продолжать увеличиваться с такой же или даже еще большей скоростью.
Таким образом, задача хранения и передачи текстовой, графической, звуковой и другой информации в наиболее компактном виде достаточно актуальна.
Цель работы. Цель данной работы заключается в разработке высокоэффективных методов и алгоритмов неискажающего сжатия данных (в первую очередь графических), которые одновременно с высокой скоростью обладают и высоким качеством сжатия.
Особое значение придавалось достижению сравнительно высокой средней скорости работы алгоритма сжатия на типичных изображениях, которая имеет наибольшее практическое значение, при приемлемой скорости сжатия в наихудшем случае.
Качеству сжатия также уделялось пристальное внимание. В некоторых случаях допускалось ухудшение качества на 0.5-1.5%, если это ускоряло алгоритм в 1.5-2 раза.
Задачи исследования. В данной работе рассматривались только методы сжатия, допускающие эффективную программную реализацию на последовательных ЭВМ, поскольку в настоящее время параллельные компьютеры
встречаются достаточно редко, а область применения аппаратных решений очень узкая.
Основные усилия были направлены на изучение, анализ и дальнейшее развитие основных методов, используемых для сжатия изображений: методов первичной обработки, контекстной обработки, методов обхода плоскости, методов сжатия одномерных данных без контекстной корреляции. Особое внимание уделено методам сортировки, разработанным автором и описываемым впервые:
сортировка параллельных блоков;
фрагментирование.
Сортировка производится для уменьшения контекстной корреляции и в общем случае зависит только от размера данных, но не от их содержания.
Методы исследования. В процессе исследований были использованы основные положения теории информации, теории кодирования дискретных источников сообщений, комбинаторики, дискретной математики, теории чисел, методы динамического программирования, математического анализа и теории асимптотических функций.
Научная новизна результатов работы. Автором разработаны и исследованы методы решения описанных задач и алгоритмы их реализации. Как правило, при разработке алгоритмов использовался тот факт, что длина сжимаемых данных естественным образом ограничена сверху: например, ввиду ограниченных объемов носителей информации длина кодируемой последовательности заведомо меньше 264 «1.6*1019.
Предложенные алгоритмы не обязательно являются асимптотически оптимальными, однако близки к таковым с практической точки зрения, обладая при этом рядом преимуществ. На защиту выносятся следующие результаты.
Разработаны новая система классификации методов сжатия и карта групп методов сжатия, иллюстрирующая эту систему. Классификации и карта групп позволяют лучше понимать конкретные методы сжатия и приблизительные границы областей их применимости.
Разработан и исследован новый метод (обратимой) сортировки данных с целью уменьшения контекстной избыточности: сортировка параллельных блоков. Показано, что все известные методы сортировки, в том числе полная (BWT) и частичная (ST) яв-
ляются частными случаями сортировки параллельных блоков (PBS).
Разработан и исследован новый метод фрагментирования, позволяющий существенно (на 5-20%) улучшить степень сжатия неоднородных данных. Метод может использоваться не только для сжатия таких данных, но и для анализа их структуры.
Разработаны и исследованы новые варианты улучшения сжатия хорошо известных методов: разделения экспонент и мантисс (SEM), линейно-предсказывающего кодирования (LPC), субполосного кодирования (SC), методов обхода плоскости. Показано, как эти методы (а в перспективе и некоторые другие, в частности векторное квантование (VQ) и нумерующее кодирование (ENUC)) могут быть применены для сжатия изображений без потерь.
Разработано и исследовано новое семейство методов сжатия изображений без потерь с помощью сортировки параллельных блоков (ERI97). Совершенствование методов продолжается, но уже сейчас их практическая реализация превосходит все известные аналоги как по степени сжатия, так и по эфективности, на широком классе изображений.
Практическая ценность результатов. Все разработанные новые методы и новые варианты существующих методов позволяют существенно улучшить как степень сжатия данных, на которые они ориентированы, так и общую эффективность сжатия таких данных современными вычислительными машинами, в среднем на 5... 20% по сравнению с лучшими из существующих в настоящее время аналогов, и на 10...90% по сравнению с современными промышленными стандартами (в первую очередь ZIP и PNG).
Реализация и внедрение результатов. Большинство алгоритмов и методов сжатия, описанных в данной работе, реализованы автором в компьютерной программе сжатия данных ERI (около 10 000 строк на языке Си). Программа создавалась в основном с целью совершенствования алгоритмов сжатия изображений без потерь, поэтому именно в таком сжатии она уже сейчас является одной из лучших в своем классе, опережая по степени сжатия и общей эффективности сжатия лучшие из известных аналогов на 2...25% (на мало шумных изображениях, достаточно больших, см. Приложения 1-4). Совершенствование методов, алгоритмов и программы продолжается.
Апробация работы и публикации. Результаты работы были опубликованы автором в местной и центральной печати [1-6] (все публикации, кроме первой — без соавторов).
Работа была апробирована на семинарах Института систем информатики им. А. П. Ершова СО РАН и Красноярского государственного технического университета.
Некоторые результаты, в частности самые важные, были опубликованы (на английском языке) в Интернете, в группе новостей сотр.compression, регулярно читаемой практически всеми специалистами в области сжатия данных. Выпуски сравнительных тестов, выполняемых автором, «Art Of Lossless Data Compression» публикуются в Интернете более четырех лет, с конца 1997-го года ( , ) и являются лучшими по многим параметрам, в частности по числу и общему объему файлов, на которых производится тестирование программ сжатия, доступности и читабельности наборов команд, тестирующих компрессоры (файлы скриптов: *.ВАТ), и другим параметрам.
Результаты работы используются в книге «Методы сжатия данных» (авторы - Д.Ватолин, А.Ратушняк, М.Смирнов, В.Юкин), публикуемой в Москве издательством «Диалог-МИФИ» в мае 2002-го года, электронный вариант книги можно увидеть в Интернете по адресу и .
Структура работы. Диссертационная работа состоит из вводной части, пяти глав и четырёх приложений.
Первая часть (вводная) содержит все используемые в работе определения и аббревиатуры, а также систему классификации методов сжатия и карту групп методов сжатия, иллюстрирующую эту систему. По мнению автора и многих ведущих специалистов в области сжатия данных (в частности, Д.Ватолина, М.Смирнова и В.Юкина), классификации и карта групп позволяют лучше понимать конкретные методы сжатия и приблизительные границы областей их применимости, причем система автора полнее, чем все другие наборы классификаций. В частности, хорошо видно, почему методы, синтезирующие LZ+BWT или LZ+PPM, эффективны и находят применение, а синтезирующие PPM+BWT теоретически возможны, но на практике неэффективны.
Других систем классификаций и карт групп методов сжатия в настоящее время либо не существует, либо они автору не известны.
Главы 1-4 работы посвящены описанию новых разработанных автором методов, а также новых вариантов существующих методов. В каждом случае изложение метода делается поступательно: от самого простого варианта к достаточно сложному.
Пятая глава работы содержит подробное описание нового разработанного автором семейства методов сжатия изображений без потерь ERI97, а также компьютерной программы ERI, реализующей некоторые варианты алгоритмов этих методов.
В приложениях даны результаты сравнения работы программы ERI с другими программами, сжимающими полноцветные изображения: лучшие из изветных программ, а также программы, реализующие промышленные стандарты (PNG, LOCO-I/JPEG-LS, baseline JPEG). Сравнение с алгоритмом JPEG, сжимающим изображения с потерями, приведено только для общего сведения. Работа заканчивается списком использованной литературы.
Пути улучшения степени сжатия
Каждому детерминирующему может соответствовать не один, а несколько детерминированных, и наоборот, каждому детерминированному может соответствовать несколько детерминирующих. Так что можно дать аналогичные определения детерминированных и детерминирующих групп битов.
Понятно, что при достаточно большом числе элементов, каждый бит в контексте старших и младших в какой-то степени является и детерминирующим (для битов младше него), и детерминированным (относительно старших). И каждый можно трактовать как детерминирующий, как детерминированный, или как «шумовой», то есть остальной.
В целом у более старших битов больше возможностей быть детерминирующими, а у более младших - детерминированными. Поэтому в первом приближении можно использовать модель, делящую все В битов на две половины -старшие и младшие. И далее считающую старшие В/2 битов детерминирующими, а младшие В/2 - детерминированными. Во втором приближении (особенно при сжатии мультимедийных данных, в том числе изображений) можно выделить в третью группу «шумовые», не являющиеся ни детерминирующими, ни детерминированными.
Из определений видно, насколько сложным может быть метод оптимальной перестановки битов. Перестановка внутри младших і битов может зависеть как от значения старших (В-і) битов, так и от значений битов элементов контекста.
Практика же показывает, что 1. если актуальна скорость работы, такого сложного анализа лучше не делать; 2. сжатие лучше, если переставлять не отдельные биты, а группы битов: если, например, имеем три восьмибитных компоненты: В первом случае двухбитные группы еще и переставлены так, чтобы образовалось три четырехбитных: АВСС АВВС ААВС. В алгоритме ERI97 разбиение на группы при перестановке битов, порядок групп внутри формируемых компонент, а также схема инвертирования битов - полностью зависят от соответствующих задаваемых параметров. Обход плоскости ОП выполняется одним из способов, подробно описанных в одноименной главе этой работы. Здесь самым важным является то, что не только для каждой компоненты, но даже для каждой битовой плоскости можно использовать свой вариант ОП. Методу ERJ97 задается как схема разбиения всех В битов на F групп, к каждой из которых будет применяться свой вариант ОП, так и вариант ОП для каждой из этих групп (если задаваемый параметр FL=0). Если FL=T, метод выбирает для каждой группы из всего множества вариантов ОП один наиболее оптимальный. Самая быстрая схема разбиения создает одну группу со всеми В битами. Вторая по скорости работы - B/Rm групп (с округлением вверх), в каждой по Rm битов. Здесь Rm - размер элемента, имеющего уникальный адрес в памяти, как правило, 8, 16, 24 или 32. Как правило, размер компонент изображения R=Rm. После всех предыдущих шагов первичной и контекстной обработки B =R N. PBS, Сортировка параллельных блоков Основная идея и главные варианты СПБ описаны в одноименной главе этой работы. Для записи значения каждого элемента изображения после ЛПК и/или СК необходимо В битов. Первое, что следует заметить, - разбиение множества В битов на G групп должно быть таким же, как при обходе плоскости. Но в то же время 1. внутри макрогруппы для ОП (ко всем группам макрогруппы применяется один вариант ОП) может быть несколько групп для СПБ, но обратное не имеет смысла (т.е. если внутри макрогруппы, к которой применяется СПБ, есть несколько групп с разными вариантами ОП, сжатие будет существенно хуже); 2. если группа К; использует группу К„ в качестве параллельного блока, она может (и должна) использовать К„ с вариантом ОП, примененным к Kj, а не Кп с вариантом ОП, примененным к Кп. Таким образом, разбиение на группы для СПБ задает и разбиение для ОП. Второе: элементы внутри каждой группы можно сортировать (1) по соседним элементам этой же группы, и/или (2) по элементам из других групп, еще не сортированных, или же (3) вообще не применять СПБ к данной группе. Только у одной из групп, а именно, сортируемой последней, нет возможности быть сортированной по (2), а только по (1). Относительно порядка применения СПБ к группам при сжатии - Кь К2, ..., KG.i, KG,- при разжатии порядок (де-)сортируемых групп - обратный: К0, К , ..., К2, Ki. Это не обязательно, если элементы каждой из G групп сортируются только по (1) или (3), но если есть и (2), т.е. пары (Kj, К„), такие, что элементы группы К; сортируются в том числе по элементам группы Кп, то при сжатии следует применять СПБ сначала к Kj, затем к К„, а при разжатии - наоборот: сначала к Кп, затем к К;. Далее. Если перестановка битов не выполнялась, имеет смысл для битов каждой компоненты создать одну отдельную группу. И к каждой из них либо (1), либо (2), либо (1) и (2), либо (3). Если перестановка битов выполнялась, и созданы группы с детерминирующими битами (в простейшем случае это самые старшие), детерминированными (средними) и шумовыми (самыми младшими) битами, то имеет смысл каждую группу сортировать по всем группам с битами старше битов данной группы, то есть (2), но не (3) и не (1). В обоих случаях как минимум к одной из них - только (1) либо (3), без (2). Если элементы группы Кр сортируются и по (1), то способ применения СПБ очень зависит от варианта ОП. Рассмотрим это подробнее на примерах. Сначала заметим, что при любом ОП, если сохранять и длины контейнеров, то атрибуты могут вычисляться любым возможным способом. Например, как сумма восьми ближайших элементов контекста, деленная на 8. Если обозначим так: то атрибут для элемента Е в этих обозначениях: От варианта ОП зависит положение каждого из этих восьми элементов контекста внутри одномерного блока. А также какие из них уже известны (и следовательно, их значение можно использовать) при вычислении атрибута для Е. При самом простом ОП известны А, В, С и D, и атрибут можно вычислять как (A+B+C+D)/4. Если же длины не сохраняем, для вычисления атрибута і-го элемента А[і] могут использоваться только элементы D[i-k], D[i-2 k], ..., D[i-m k]. Шаг k 0 и глубина m 0 постоянны при всем процессе СПБ. Поэтому ОП «змейкой», «квадратной змейкой» и «по спирали», а также контурные - мало подходят для СПБ без сохранения длин. Только (і-І)-ьій элемент является одним из восьми ближайших элементов контекста, а положение остальных семи зависит от і и от варианта ОП. При ОП строками уже два из восьми ближайших элементов контекста находятся на известном расстоянии от і-того: (і-І)-ьій и (i-W)-bm, где W - ширина изображения, то есть длина строки. Но есть два минуса: особенность самой первой строки и «разрывы» в конце каждой строки. ОП строками с разворотами устраняет разрывы, но и добавляет ещё больший минус: каждый (i-W)-bm элемент при таком ОП уже не будет ближайшим элементом для і-ого, каким бы ни было W.
ОП полосами и ОП полосами с разворотами в целом очень подходят для последующей СПБ. Если L — ширина полосы, то каждый (і-Ь)-ьій элемент является для і-ого одним из четырех ближайших. Исключение составляют лишь вертикальные границы изображения.
ОП решетками обязательно использует для создания последовательности «узлов» решетки некоторый другой ОП. После того, как сохранены «узлы», делается обход по узлам с одинаковыми атрибутами. Тоже с использованием некоторого другого, «внешнего» варианта ОП.
«Квадратная змейка»
Может оказаться полезным сохранять блок А вместо Р, особенно если параллельный блок строится одновременно с сортируемым — например, Р[/] вычисляется по Рр-1] и 1п[/-1]. Тогда Р должен быть восстановим по А, и функция А должна быть биективной: по значению А[г ]=А(Р[/]) однозначно находится [i]. Реально такая функция А сводится к перестановке: имеем контейнеры с атрибутами А[/]=Р[г], затем перетасовываем их, меняя местами внутри единого выходного блока Out, но не изменяя их содержимого. Но формально А может выглядеть очень по-разному, содержать прибавление константы:
Ненамного сложнее будет выглядеть А, собирающая вместе элементы 1п[г], соответствующие тем Р[г], остаток которых от деления на заданное К одинаков.
Если функция А не адаптивна или зависит только от элементов параллельного блока, сами контейнеры, поскольку их длины известны, можно сортировать внутри единого выходного блока по их длинам. Это может улучшить сжатие даже при ST/BWT, особенно в случае качественных данных, а не количественных. Часто оказывается выгодным группировать короткие контейнеры в одном конце выходного блока, а длинные — в другом. И при сжатии, и при разжатии процедура сортировки контейнеров по длинам добавится между циклами (2) и (3). Рассмотрим последний вариант: весь блок А сохраняется и передается (компрессором декомпрессору), поэтому и строится он именно с учетом такой особенности. Если есть параллельный блок Р, можно строить А так, чтобы и Р преобразовывать на основе А, и чтобы суммарно блоки А, Р, In сжимались лучше, чем Р и In. Если нет Р, то получается, что In распадается на две компоненты: «идеальную» — моделируемые, предсказываемые A[i], и «реальную» — отклонения 1п[г] от предсказанных значений А[г].
Параллельным блоком может быть предыдущая, уже обработанная строка таблицы. Либо предсказываемая (текущая), формируемая на основе одной или нескольких предыдущих строк. В обоих случаях целесообразно вычислять атрибут как среднее арифметическое соседних элементов, особенно для мультимедийных данных: Тогда, опять же, длины контейнеров (частоты значений атрибутов) надо обязательно передавать декомпрессору. Перед делением полезно делать округление до ближайшего числа, кратного делителю. Еще сложнее будут формулы, если использовать более одной предыдущей строки. Заметим важное полезное свойство метода: увеличение сложности вычислений не влечет увеличения объема необходимой памяти. Если рассматривать множество строк как единый блок, то в простейшем случае A[i]=P[i]=In[i-JF] (W— число элементов в строке), то есть в качестве атрибута используется значение «верхнего» элемента. Тогда таблицу длин сохранять не нужно, но первые элементов в неизменном виде — обязательно. Фрагментирование Цель: разбиение исходного потока или блока на фрагменты с разными статистическими свойствами. Такое разбиение должно увеличить степень последующего сжатия. В простейшем случае битового потока необходимо находить границы участков с преобладанием нулей, участков с преобладанием единиц, и участков с равномерным распределением нулей и единиц. Если поток символьный, может оказаться выгодным разбить его на фрагменты, отличающиеся распределением вероятностей элементов: например, на фрагменты с русским текстом и фрагменты с английским. Основная идея состоит в том, чтобы для каждой точки потока X (лежащей между парой соседних элементов) находить значение функции отличия FO(JQ предыдущей части потока от последующей. В базовом простейшем варианте используется «скользящее окно» фиксированной длины: Z элементов до точки X, и Z элементов после нее. Иллюстрация (Z=7): ...8536429349586436542 9865332 \Х\ 6564387 58676780674389... Цифрами обозначены элементы потока, вертикальными чертами «» границы левого и правого окон. X — не элемент потока, а точка между парой элементов, в данном случае между "2" и "6". При фиксированной длине окон Z и одинаковой значимости, или весе, всех элементов внутри окон (независимо от их удаленности от точки X), значение функции отличия может быть легко вычислено на основании разности частот элементов в левом и правом окнах. Это сумма по всем 2R возможным значениям Vt элементов. Суммируются абсолютные значения разностей: число элементов с текущим значением V в левом окне длиной Z минус число элементов с данным значением V в правом окне длиной Z Суммируя 2R модулей разности, получаем значение FO(Z) в данной точке X: После того как все значения FO(X) найдены, остается отсортировать их по возрастанию и выбрать границы по заданному критерию (заданное число границ и/или пока FO(X) Fmjn). Размер данных в результате фрагментирования увеличивается: либо появляется второй поток с длинами фрагментов, либо флаги границ в одном результирующем потоке. Дня сжатия результата работы метода может быть применена любая комбинация методов — RLE, LPC, MTF, DC, PBS, HUFF, ARIC, ENUC, SEM... Методы этой группы трансформирующие и поточные, т.е. могут применяться даже в том случае, когда длина блока с данными не задана. Обратного преобразования не требуется. В общем случае скорость работы компрессора зависит только от размера данных, но не от их содержания: Скорость=0(Размер). Памяти требуется порядка 2Л+1. Для левого окна 0(2 ), и столько же для правого. Операций умножения и деления нет. С точки зрения сегментации данных, метод отличается от RLE лишь тем, что выделяет из потока (или блока) не только цепочки одинаковых элементов, но и вообще отделяет друг от друга фрагменты с разными распределениями вероятностей значений элементов. Из краткого описания общей идеи видно, что 1) порождается либо второй поток с длинами фрагментов, либо в исходный поток добавляются флаги границ (флаг может отвечать условию не только на значение одного элемента, но и условию на значение функции нескольких элементов); 2) задаваемыми параметрами могут быть (максимальная) длина окна Z, Fmin — минимальное значение FO(X), минимальное расстояние между границами Rm{n (а в случае фрагментирования блока заданной длины — еще и число границ NG, минимальное и/или максимальное число границ: Nmin, Nmm); 3) вычисление функции отличия при нескольких длинах окон — Z\ , Z2, ... , Za — в общем случае улучшит качество фрагментирования; 4) уменьшение веса элементов окна с удалением от точки X также в общем случае улучшит качество фрагментирования. Каков бы ни был размер окон Z, при проходе по входным данным Ъ[Щ в каждой точке X при переходе к следующей точке (Х+1) достаточно следить за тремя элементами: вышедшим из левого окна (из-за сдвига точки X вправо), вошедшим в правое окно, и перешедшим из правого окна в левое. Но сначала разберем самый понятный алгоритм: с проходом по всем элементам окон для каждой точки X.
Нумерующее кодирование
Во второй части работы описывается ERI97 - семейство быстрых высокоэффективных алгоритмов сжатия цифровой графической информации без потерь. Важнейшей частью ERI97 является сортировка параллельных блоков (Parallel Blocks Sorting, PBS). Поскольку она описывается впервые, о ней будет подробно рассказано отдельно. ERI97, как и PBS, - алгоритмы блочные, трансформирующие. Размер данных в результате применения ERI97 и PBS не изменяется.
Не будут рассмотрены следующие важные сопутствующие алгоритмы: 1. Анализ графического блока 2. Фрагментирование блока 3. Отделение шума 4. Выбор оптимальных параметров, задаваемых алгоритму ERI97 5. Сжатие результата работы алгоритма (здесь может быть применена любая комбинация других методов - RLE, LPC, MTF, DC, HUFF, ARIC, ENUC, SEM...) Основные свойства описываемой группы алгоритмов: 1. Размер получаемых данных равен размеру задаваемых данных плюс А байт служебной информации (А зависит только от параметров, задаваемых алгоритму). 2. Скорость работы ERI97 сравнима со скоростью аналогов - JPEG, PNG, LOCO - но качество достигаемого сжатия - уже сейчас лучше на 10%-70% (не вариант JPEG-a без потерь, а именно JPEG с потерями, но лучшим качеством). 3. Алгоритм состоит из последовательности четырех независимых действий, причем каждое из них работает с каждым пикселом (элементом изображения); любые из них могут быть пропущены при прямой и затем при обратной трансформации; "сжимающая" трансформация (компрессор) осуществляет их в прямом порядке, а "разжимающая" трансформация (декомпрессор) - в обратном. 4. Скорость работы компрессора в общем случае равна скорости декомпрессора и зависит только от размера данных, но не от их содержания: Ск=0(размер). 5. Памяти требуется 2 (размер входных данных)+С. 6. В общем случае отсутствуют операции умножения и деления. 7. Число N компонент каждого пиксела, как и разрядность пикселов R, являются двумя из множества задаваемых параметров, и могут быть произвольными. Алгоритм был реализован в компьютерной программе ERI32 в 1997-ом году и активно совершенствуется в течение последних четырех лет. В настоящее время ERI32 достигает лучших результатов среди всех известных аналогов по сжатию без потерь малошумных 24-битных изображений. Причем как по качеству сжатия, так и по общему суммарному показателю, учитывающему также и скорости сжатия и разжатия. Основные отличия реализации - программы ERI32 (последняя версия на текущий момент - 24-е мая 2002-го года - 5.1fre) : 1. Примерно десять внешне задаваемых параметров. 2. В настоящее время поддерживается только режим N=3, R=8, то есть каждый пиксел состоит из трех 8-битных компонент. 3. Байт-ориентированность: операции над битами по возможности сведены к минимуму, что многократно увеличивает скорость работы, но немного ухудшает качество сжатия. Почему именно 24 бита, то есть три восьмибитных компоненты? 1. Это самый распространенный формат, подавляющее большинство полноцветных изображений хранится, передается и обрабатывается именно в таком формате. 2. С точки зрения восприятия полноцветной графики человеком, 16-и битов явно недостаточно, а 32-х гораздо более чем достаточно, хотя и удобнее для обработки 32-битными процессорами семейства х8б. 3. С точки зрения сжатия, каковы бы ни были компоненты - RGB, CMYK, HSB, YCrCb или иное, и каковы бы ни были R и N, - желательно чтобы произведение R N было кратно трем (а поскольку чаще всего R - степень двойки, именно N должно быть кратно трем). Причина этого вот в чем: из всего множества 2R N возможных цветов в каждом изображении используется, как правило, менее одного процента цветов. Поэтому эти подмножества использованных цветов можно представлять себе как сгустки в N-мерном кубе с ребром длиной 2R. Тогда, в "идеальном" для сжатия случае, эти D скоплений 1. не пересекаются, и 2. их проекции на ребра куба обладают свойствами: (а) длины близки к степеням двойки: Ly= 2Xlj, i=l...D, j=l...N. (б) их границы выровнены по длинам: Bij=K 2Xlj, i=l...D, j=l...N. И тогда выгодно разделять и обрабатывать отдельно: 1. "детерминирующие" биты, т.е. указывающие на сектор с одним скоплением; 2. "детерминированные" биты, указывающие на положение скопления внутри сектора; 3. "шумовые" биты, указывающие на положение точки внутри скопления, их обычно нет, если изображение получено не оцифровкой, а синтезировано алгоритмом. Учитывая, что, как правило, каждый из N компонентов хранится в отдельном байте с уникальным адресом, хорошо, когда N кратно трем, и можно отвести по N/3 байтов под "детерминирующие", "детерминированные" и "шумовые" биты. Четыре действия, из которых и состоит ERI97, компрессор выполняет в следующем порядке: 1. Первичная обработка 2. Контекстная обработка 3. Обход плоскости 4. PBS, Сортировка параллельных блоков При разжатии эти действия выполняются в обратном порядке. Первые три действия в том или ином виде присутствуют во всех аналогичных методах. Первые два действия не имеют отношения к PBS и могут совершаться отдельно, практически никак не ориентируясь на последующую PBS. Более того, каждое из них может выполняться параллельно, распадаясь на Р процессов, причем возможные значения Р - от 1 до S, где S - число пикселов в обрабатываемом блоке. Первое действие настолько тривиально, что в практической реализации легко может быть совмещено со вторым. Тем не менее, поскольку логически это разные действия, в описании алгоритма они идут отдельно. Первичная обработка Поворот Как показала практика, во многих случаях поворот изображения на л/2 радиан до контекстной обработки (КО) существенно улучшает степень достигаемого затем сжатия. Для иллюстрации причины этого явления возьмем такое изображение размером 2 256: S[0,j]=0, И такой алгоритм контекстной обработки: ЛПК с фильтром Sp[ij]=S[i-lj]. В результате ЛПК всегда сохраняются значения D[ij]=S[ij]-Sp[ij] (но какое именно Sp[ij] будет использовано, зависит от подробностей алгоритма с ЛПК). Таким образом, если не делать поворот на л/2, в результате ЛПК получится D[lj]=S[lj]-S[Oj]=j, а если сделать поворот: S[j,0]=0, S0,l]=j, j=0...255, D(j,l]=S[j,l]-S(j-l,l]=j-(j-l)=l. Во втором случае кодирование результата ЛПК даст лучшее сжатие. Если в КО присутствует ЛПК или СК, каждый вариант алгоритма распадается на два подварианта, симметричные относительно двух направлений в плоскости. За исключением тех вариантов ЛПК, которые используют только сумму каждой пары значений элементов контекста, взятых из симметричных относительно прямой X=Y позиций (X=Y, если X Y 0, или Х= -Y, если X Y 0). То есть если позиция (0,0) соответствует текущему элементу, к которому применяется КО, то значение каждого элемента (X,Y) должно присутствовать (при вычислении предсказуемого значения) только в сумме с элементом (Y,X) (с (-Y, -X), если X Y 0), только такой вариант ЛПК будет давать тот же результат после поворота на я/2 радиан.
Линейно-Предсказывающее Кодирование (ЛПК)
Понятно, что при достаточно большом числе элементов, каждый бит в контексте старших и младших в какой-то степени является и детерминирующим (для битов младше него), и детерминированным (относительно старших). И каждый можно трактовать как детерминирующий, как детерминированный, или как «шумовой», то есть остальной.
В целом у более старших битов больше возможностей быть детерминирующими, а у более младших - детерминированными. Поэтому в первом приближении можно использовать модель, делящую все В битов на две половины -старшие и младшие. И далее считающую старшие В/2 битов детерминирующими, а младшие В/2 - детерминированными. Во втором приближении (особенно при сжатии мультимедийных данных, в том числе изображений) можно выделить в третью группу «шумовые», не являющиеся ни детерминирующими, ни детерминированными.
Из определений видно, насколько сложным может быть метод оптимальной перестановки битов. Перестановка внутри младших і битов может зависеть как от значения старших (В-і) битов, так и от значений битов элементов контекста. Практика же показывает, что 1. если актуальна скорость работы, такого сложного анализа лучше не делать; 2. сжатие лучше, если переставлять не отдельные биты, а группы битов: если, например, имеем три восьмибитных компоненты: В первом случае двухбитные группы еще и переставлены так, чтобы образовалось три четырехбитных: АВСС АВВС ААВС. В алгоритме ERI97 разбиение на группы при перестановке битов, порядок групп внутри формируемых компонент, а также схема инвертирования битов - полностью зависят от соответствующих задаваемых параметров. Обход плоскости ОП выполняется одним из способов, подробно описанных в одноименной главе этой работы. Здесь самым важным является то, что не только для каждой компоненты, но даже для каждой битовой плоскости можно использовать свой вариант ОП. Методу ERJ97 задается как схема разбиения всех В битов на F групп, к каждой из которых будет применяться свой вариант ОП, так и вариант ОП для каждой из этих групп (если задаваемый параметр FL=0). Если FL=T, метод выбирает для каждой группы из всего множества вариантов ОП один наиболее оптимальный. Самая быстрая схема разбиения создает одну группу со всеми В битами. Вторая по скорости работы - B/Rm групп (с округлением вверх), в каждой по Rm битов. Здесь Rm - размер элемента, имеющего уникальный адрес в памяти, как правило, 8, 16, 24 или 32. Как правило, размер компонент изображения R=Rm. После всех предыдущих шагов первичной и контекстной обработки B =R N. PBS, Сортировка параллельных блоков Основная идея и главные варианты СПБ описаны в одноименной главе этой работы. Для записи значения каждого элемента изображения после ЛПК и/или СК необходимо В битов. Первое, что следует заметить, - разбиение множества В битов на G групп должно быть таким же, как при обходе плоскости. Но в то же время 1. внутри макрогруппы для ОП (ко всем группам макрогруппы применяется один вариант ОП) может быть несколько групп для СПБ, но обратное не имеет смысла (т.е. если внутри макрогруппы, к которой применяется СПБ, есть несколько групп с разными вариантами ОП, сжатие будет существенно хуже); 2. если группа К; использует группу К„ в качестве параллельного блока, она может (и должна) использовать К„ с вариантом ОП, примененным к Kj, а не Кп с вариантом ОП, примененным к Кп. Таким образом, разбиение на группы для СПБ задает и разбиение для ОП. Второе: элементы внутри каждой группы можно сортировать (1) по соседним элементам этой же группы, и/или (2) по элементам из других групп, еще не сортированных, или же (3) вообще не применять СПБ к данной группе. Только у одной из групп, а именно, сортируемой последней, нет возможности быть сортированной по (2), а только по (1). Относительно порядка применения СПБ к группам при сжатии - Кь К2, ..., KG.i, KG,- при разжатии порядок (де-)сортируемых групп - обратный: К0, К , ..., К2, Ki. Это не обязательно, если элементы каждой из G групп сортируются только по (1) или (3), но если есть и (2), т.е. пары (Kj, К„), такие, что элементы группы К; сортируются в том числе по элементам группы Кп, то при сжатии следует применять СПБ сначала к Kj, затем к К„, а при разжатии - наоборот: сначала к Кп, затем к К;. Далее. Если перестановка битов не выполнялась, имеет смысл для битов каждой компоненты создать одну отдельную группу. И к каждой из них либо (1), либо (2), либо (1) и (2), либо (3). Если перестановка битов выполнялась, и созданы группы с детерминирующими битами (в простейшем случае это самые старшие), детерминированными (средними) и шумовыми (самыми младшими) битами, то имеет смысл каждую группу сортировать по всем группам с битами старше битов данной группы, то есть (2), но не (3) и не (1). В обоих случаях как минимум к одной из них - только (1) либо (3), без (2). Если элементы группы Кр сортируются и по (1), то способ применения СПБ очень зависит от варианта ОП. Рассмотрим это подробнее на примерах. Сначала заметим, что при любом ОП, если сохранять и длины контейнеров, то атрибуты могут вычисляться любым возможным способом. Например, как сумма восьми ближайших элементов контекста, деленная на 8. Если обозначим так: то атрибут для элемента Е в этих обозначениях: (A+B+C+D+F+G+H+I)/8. От варианта ОП зависит положение каждого из этих восьми элементов контекста внутри одномерного блока. А также какие из них уже известны (и следовательно, их значение можно использовать) при вычислении атрибута для Е. При самом простом ОП известны А, В, С и D, и атрибут можно вычислять как (A+B+C+D)/4. Если же длины не сохраняем, для вычисления атрибута і-го элемента А[і] могут использоваться только элементы D[i-k], D[i-2 k], ..., D[i-m k]. Шаг k 0 и глубина m 0 постоянны при всем процессе СПБ. Поэтому ОП «змейкой», «квадратной змейкой» и «по спирали», а также контурные - мало подходят для СПБ без сохранения длин. Только (і-І)-ьій элемент является одним из восьми ближайших элементов контекста, а положение остальных семи зависит от і и от варианта ОП. При ОП строками уже два из восьми ближайших элементов контекста находятся на известном расстоянии от і-того: (і-І)-ьій и (i-W)-bm, где W - ширина изображения, то есть длина строки. Но есть два минуса: особенность самой первой строки и «разрывы» в конце каждой строки. ОП строками с разворотами устраняет разрывы, но и добавляет ещё больший минус: каждый (i-W)-bm элемент при таком ОП уже не будет ближайшим элементом для і-ого, каким бы ни было W. ОП полосами и ОП полосами с разворотами в целом очень подходят для последующей СПБ. Если L — ширина полосы, то каждый (і-Ь)-ьій элемент является для і-ого одним из четырех ближайших. Исключение составляют лишь вертикальные границы изображения. ОП решетками обязательно использует для создания последовательности «узлов» решетки некоторый другой ОП. После того, как сохранены «узлы», делается обход по узлам с одинаковыми атрибутами. Тоже с использованием некоторого другого, «внешнего» варианта ОП.
