Методы сжатия данных без потерь с помощью сортировки параллельных блоков

На правах рукописи

РАТУШНЯК Олег Александрович Методы сжатия данных без потерь с помощью сортировки параллельных блоков 05.13.11 – математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Красноярск — 2002

Работа выполнена в Институте систем информатики им.А.П.Ершова Сибирского отделения Российской академии наук

Научный консультант: доктор физико-математических наук, профессор А.Г.Марчук

Официальные оппоненты: доктор физико-математических наук, профессор Носков М.В.

кандидат физико-математических наук Мурзин Ф.А.

Ведущая организация: Институт автоматики и электрометрии СО РАН

Защита состоится 2 июля 2002 г. в 14 часов на заседании диссер тационного совета Д 212.098.03 при Красноярском государственном техни ческом университете по адресу: 660074, г. Красноярск, ул. акад. Киренско го, 26.

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

Автореферат разослан “” июня 2002 г.

Ученый секретарь диссертационного совета кандидат технических наук Е.А.Вейсов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

Качеству сжатия также уделялось пристальное внимание. В некоторых слу чаях допускалось ухудшение качества на 0.5-1.5%, если это ускоряло алго ритм в 1.5-2 раза.

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

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

Особое внимание уделено методам сортировки, разработанным автором и описываемым впервые:

• сортировка параллельных блоков;

• фрагментирование.

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

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

Научная новизна результатов работы. Автором разработаны и исследо ваны методы решения описанных задач и алгоритмы их реализации.

Как правило, при разработке алгоритмов использовался тот факт, что длина сжимаемых данных естественным образом ограничена сверху: например, ввиду ограниченных объемов носителей информации длина кодируемой последовательности заведомо меньше 264 1.6*1019.

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

На защиту выносятся следующие результаты.

1. Разработаны новая система классификации методов сжатия и карта групп методов сжатия, иллюстрирующая эту систему.

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

2. Разработан и исследован новый метод (обратимой) сортировки данных с целью уменьшения контекстной избыточности: сорти ровка параллельных блоков. Показано, что все известные мето ды сортировки, в том числе полная (BWT) и частичная (ST) яв ляются частными случаями сортировки параллельных блоков (PBS).

3. Разработан и исследован новый метод фрагментирования, по зволяющий существенно (на 5-20%) улучшить степень сжатия неоднородных данных. Метод может использоваться не только для сжатия таких данных, но и для анализа их структуры.

4. Разработаны и исследованы новые варианты улучшения сжатия хорошо известных методов: разделения экспонент и мантисс (SEM), линейно-предсказывающего кодирования (LPC), субпо лосного кодирования (SC), методов обхода плоскости. Показано, как эти методы (а в перспективе и некоторые другие, в частно сти векторное квантование (VQ) и нумерующее кодирование (ENUC)) могут быть применены для сжатия изображений без потерь.

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

Практическая ценность результатов. Все разработанные новые методы и новые варианты существующих методов позволяют существенно улучшить как степень сжатия данных, на которые они ориентированы, так и общую эффективность сжатия таких данных современными вычислительными ма шинами, в среднем на 5…20% по сравнению с лучшими из существующих в настоящее время аналогов, и на 10…90% по сравнению с современными промышленными стандартами (в первую очередь ZIP и PNG).

Реализация и внедрение результатов. Большинство алгоритмов и мето дов сжатия, описанных в данной работе, реализованы автором в компью терной программе сжатия данных ERI (около 10 000 строк на языке Си).

Программа создавалась в основном с целью совершенствования алгоритмов сжатия изображений без потерь, поэтому именно в таком сжатии она уже сейчас является одной из лучших в своем классе, опережая по степени сжа тия и общей эффективности сжатия лучшие из известных аналогов на 2…25% (на малошумных изображениях, достаточно больших, см. Прило жения 1-4).

Совершенствование методов, алгоритмов и программы продолжается.

Апробация работы и публикации. Результаты работы были опубликова ны автором в местной и центральной печати [1-6] (все публикации, кроме первой — без соавторов).

Работа была апробирована на семинарах Института систем информатики им. А. П. Ершова СО РАН и Красноярского государственного технического университета.

Некоторые результаты, в частности самые важные, были опубликованы (на английском языке) в Интернете, в группе новостей comp.compression, регу лярно читаемой практически всеми специалистами в области сжатия дан ных. Выпуски сравнительных тестов, выполняемых автором, «Art Of Loss less Data Compression» публикуются в Интернете более четырех лет, с кон ца 1997-го года ( http://go.to/artest, http://artst.narod.ru/ ) и являются лучши ми по многим параметрам, в частности по числу и общему объему файлов, на которых производится тестирование программ сжатия, доступности и читабельности наборов команд, тестирующих компрессоры (файлы скрип тов: *.BAT), и другим параметрам.

Результаты работы используются в книге «Методы сжатия данных» (авто ры – Д.Ватолин, А.Ратушняк, М.Смирнов, В.Юкин), публикуемой в Москве издательством «Диалог-МИФИ» в мае 2002-го года, электронный вариант книги можно увидеть в Интернете по адресу http://compression.graphicon.ru/ и http://compression.graphicon.ru/tmp/.

Структура работы. Диссертационная работа состоит из вводной части, пяти глав и четырёх приложений.

Первая часть (вводная) содержит все используемые в работе определения и аббревиатуры, а также систему классификации методов сжатия и карту групп методов сжатия, иллюстрирующую эту систему. По мнению автора и многих ведущих специалистов в области сжатия данных (в частности, Д.Ватолина, М.Смирнова и В.Юкина), классификации и карта групп позво ляют лучше понимать конкретные методы сжатия и приблизительные гра ницы областей их применимости, причем система автора полнее, чем все другие наборы классификаций. В частности, хорошо видно, почему мето ды, синтезирующие LZ+BWT или LZ+PPM, эффективны и находят приме нение, а синтезирующие PPM+BWT теоретически возможны, но на практи ке неэффективны.

Других систем классификаций и карт групп методов сжатия в настоящее время либо не существует, либо они автору не известны.

Главы 1-4 работы посвящены описанию новых разработанных автором ме тодов, а также новых вариантов существующих методов.

В каждом случае изложение метода делается поступательно: от самого про стого варианта к достаточно сложному.

Пятая глава работы содержит подробное описание нового разработанного автором семейства методов сжатия изображений без потерь ERI97, а также компьютерной программы ERI, реализующей некоторые варианты алго ритмов этих методов.

В приложениях даны результаты сравнения работы программы ERI с дру гими программами, сжимающими полноцветные изображения: лучшие из изветных программ, а также программы, реализующие промышленные стандарты (PNG, LOCO-I/JPEG-LS, baseline JPEG). Сравнение с алгорит мом JPEG, сжимающим изображения с потерями, приведено только для общего сведения.

Работа заканчивается списком использованной литературы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении содержатся краткие сведения об используемых терминах, су ществующих методах сжатия, критериях их оценки и т. д. Вся терминоло гия была разработана автором и в полном виде вошла в книгу «Методы сжатия данных». Терминов, необходимых для понимания классификации и карты групп, относительно немного.

Блок — конечная последовательность цифровой информации.

Поток — последовательность с неизвестными границами: данные посту пают маленькими блоками, и нужно обрабатывать их сразу, не накапливая.

Блок — последовательность с произвольным доступом, а поток — с после довательным.

R-битный элемент — совокупность R битов — имеет 2R возможных зна чений-состояний. Большинство источников цифровой информации порож дает элементы одного размера R. А в большинстве остальных случаев — элементы нескольких размеров: R1, R2, R3... (например, 8, 16 и 32).

Конечная последовательность элементов называется словом, а количество элементов в слове — длиной слова.

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

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

Можно говорить, что источник без памяти порождает ”элементы”, а ис точник данных с памятью — ”слова”, поскольку во втором случае • учет значений соседних элементов (контекста) улучшает сжатие, то есть имеет смысл трактовать данные как слова;

• поток данных выглядит как поток слов.

В первом же случае имеем дело с перестановкой элементов, и рассматри вать данные как слова нет смысла.

Кавычки показывают, что это условные названия способов интерпретации входных данных: ”слова”, ”элементы”, ”биты”.

По традиции бинарный источник без памяти называют обычно «источник Бернулли», а важнейшим частным случаем источника данных с памятью является «источник Маркова» (N-го порядка): состояние на i-ом шаге за висит от состояний на N предыдущих шагах: i-1, i-2,…, i-N.

Третья важнейшая применяемая при сжатии данных математическая мо дель — «аналоговый сигнал»:

• данные считаются количественными;

• источник данных считается источником Маркова 1-го порядка.

Если использовать модель «аналоговый сигнал» с N 1, то при малых N эффективность сжатия неизменна или незначительно лучше, но метод су щественно сложнее, а при дальнейшем увеличении N эффективность резко уменьшается.

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

Еще две важных характеристики алгоритма сжатия — объемы памяти, не обходимые для сжатия и для разжатия (для хранения данных, создаваемых и/или используемых алгоритмом).

Карта групп методов сжатия Статистические Трансформирующие Поточные Блочные Поточные Блочные CM, DMC, CMBZ, pre- Все LZ, в ST, в т.ч.

для ”слов”, все PPM conditioned т.ч. LZH и BWT модель «Источник с PPMZ LZW памятью» адаптив- статиче- SEM, VQ, DCT, FT, для ”элементов”, ный HUFF ский HUFF MTF, DC, Фракталь модели «Источник SC, DWT ные мето без памяти» или ды «Аналоговый сиг нал» адаптив- статиче- RLE, LPC, PBS, ENUC для ”элементов” ный ARIC ский ARIC в т.ч. Дель или ”битов” та Каждая группа (ветвь, семейство) содержит множество методов. Ис ключением является блочно-ориентированный CM — это относительно мало исследованная область. Автору не известны другие практические реа лизации, кроме компрессоров CM Булата Зиганшина и ”pre-conditioned PPMZ” Чарльза Блума.

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

Все поточные методы применимы и к блокам, но обратное неверно. Блоч ные методы неприменимы к потокам, поскольку не могут начать выполне ние, пока не задана длина блока, заполненного данными, подлежащими сжатию.

В первой строке «карты групп» — методы для источников с памятью, порождаемые ими данные выгодно трактовать как слова. Однако методы для потоков ”слов” оперируют, как правило, элементами заданного разме ра, а не словами, поскольку разбиение потока элементов на слова заранее в общем случае неизвестно.

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

Не все методы для потоков R-битных ”элементов” применимы к ”би там” (только те, которые в третьей строке «карты»).

Очевидно, что невыгодно применять методы для ”элементов” — к ”словам” или ”битам”. Менее очевидно, что невыгодно и обратное: при менять методы для потоков ”слов” к данным без значимых вероятностных взаимосвязей, к ”элементам” или ”битам”.

Все названия и аббревиатуры методов содержатся в тексте работы.

Базовых стратегий сжатия три:

1) Трансформация потока («Скользящее окно-словарь»).

Описание поступающих данных через уже обработанные. Сюда входят LZ-методы для потоков ”слов”, т.е. когда комбинации поступающих эле ментов предсказуемы по уже обработанным комбинациям. Преобразование по таблице, RLE, LPC, DC, MTF, VQ, SEM, Subband Coding, Discrete Wave let Transform, — для потоков ”элементов”, т.е. когда не имеет смысла рас сматривать комбинации длиной два и более элемента, или запоминать эти комбинации, как в случае Linear Prediction Coding.

Никаких вероятностей, в отличие от второй стратегии, не вычисляется.

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

2) Статистическая стратегия.

а) Адаптивная (поточная).

Вычисление вероятностей для поступающих данных на основании ста тистики по уже обработанным данным. Кодирование с использованием этих вычисленных вероятностей. Семейство PPM-методов — для потоков ”слов”, адаптивные варианты методов Хаффмана и Шеннона-Фано, ариф метического кодирования — для потоков ”элементов”. В отличие от пер вого случая, давно собранная статистика имеет тот же вес, что и недавняя, если метод не борется с этим специально, что гораздо сложнее, чем в слу чае LZ. Кроме того, считаются вероятными все комбинации, даже те, кото рые еще не встречались в потоке, и, скорее всего, никогда не встретятся.

б) Блочная.

Отдельно кодируется и добавляется к сжатому блоку его статистика.

Статические варианты методов Хаффмана, Шеннона-Фано и Арифметиче ского Кодирования — для потоков ”элементов”. Статическое CM для ”слов”.

3) Трансформация блока.

Входящие данные разбиваются на блоки, которые затем трансформи руются целиком, а в случае блока однородных данных лучше брать весь блок, который требуется сжать. Это методы сортировки блоков (“BlockSort ing”-методы: ST, BWT, PBS), а также Fourier Transform, Discrete Cosine Transform, фрактальные преобразования, Enumerative Coding.

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

Резюмируя одним предложением: метод сжатия может быть или стати стическим, или трансформирующим, и обрабатывать данные либо поточно, либо блоками, причем • чем больше и однороднее данные и память, тем эффективнее блоч ные методы;

• чем меньше и неоднороднее данные и память, тем эффективней по точные методы;

• чем сложнее источник, тем сильнее улучшит сжатие оптимальная трансформация;

• чем проще источник, тем эффективней прямолинейное статистиче ское решение (математические модели «источник Бернулли» и «ис точник Маркова»).

В первой главе рассматривается кодирование источников данных типа «аналоговый сигнал»: Линейно-предсказывающее кодирование и Субпо лосное кодирование. Описаны в основном те варианты методов, которые показали высокую эффективность на практике. Большинство из них разра ботано автором.

Метод LPC применяется обычно для сжатия аналоговых сигналов. И как правило, каждый элемент сигнала отклоняется от своего предсказывае мого значения не только из-за «сильных» обусловленных изменений — эволюции, но и из-за «слабых» фоновых колебаний, то есть шума. Поэтому возможно два противоположных типа моделей:

• вклад шума невелик по сравнению с вкладом эволюции;

• вклад эволюции невелик по сравнению с вкладом шума.

В первом случае мы будем предсказывать значение S[i] на основании сложившейся линейной тенденции, во втором — как равное среднему арифметическому h предыдущих элементов.

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

Требуется минимизировать ошибки предсказаний, поэтому применим такой критерий: оптимальна та модель, которая дает наименьшую сумму абсолютных значений этих ошибок:

min( | Di |) i В алгоритме PNG для сжатия изображения можно выбрать одну из сле дующих LPC-моделей (называемых также «фильтрами»):

1) E=0 (нет фильтра) 2) E=D (элемент слева) 3) E=B (элемент сверху) 4) E=(B+D)/ 5) алгоритм Paeth Все пять — варианты шумовой модели, и только последняя модель являет ся комбинированной, учитывающей эволюцию.

В алгоритме Lossless JPEG может быть задан один из восьми предсказате лей-фильтров:

1) E=0 (нет фильтра) 2) E=B (элемент сверху) 3) E=D (элемент слева) 4) E=A (выше и левее) 5) E=B+D–A 6) E=B+(D–A)/ 7) E=D+(B–A)/ 8) E=(B+D)/ Пятый, шестой и седьмой — варианты эволюционной модели, остальные — шумовой.

Выбор фильтра в общем случае. Имеем множество фильтров Spn[X,Y]=Sn(Ki,j·S[X–i,Y–j]) дающих оценки-предсказания Spn для значения элемента в позиции (X,Y) как функцию Sn от значений элементов контекста, то есть элементов, соседних с текущим S[X,Y].

Два самых очевидных пути дальнейших действий:

1. выбрать одно значение Spn, даваемое той функцией Sn, которая точнее на заданном числе предыдущих элементов, 2. выбрать значение, вычисляемое как сумма всех Spn, взятых с разными весами: Sp = (Wn·Spn), 0Wn1.

Кроме довольно очевидного способа — корректировки Wn, весов, с ко торыми берутся предсказания, даваемые разными фильтрами, есть и еще варианты:

3. брать те K значений Spn, которые дают Sn, лучшие на K (задаваемом числе) ближайших элементов контекста (некоторые из этих Sn могут совпадать, и их останется меньше, чем K).

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

Четвертый вариант является простым расширением первого. Третий же предполагает сопоставление каждому элементу одной Sn, дающей для него самое точное предсказание. В обоих случаях, если требуется выбрать одну Sn из нескольких Si с одинаковым значением точности, можно посмотреть значения точности этих Si на большем числе элементов.

Во 2-м, 3-м и 4-м часто полезно уменьшить шум описанным в работе способом. И в конечном итоге сложить оставшиеся Sp = (Wn·Spn). В про стейшем случае Wn=1/H, где H — количество оставшихся Sn.

Субполосное кодирование. Цель метода — сжатие потока R-битных эле ментов, в предположении, что значение каждого из них отличается от зна чений соседних элементов незначительно: Si Si-1.

Основная идея состоит в том, чтобы формировать два потока: для каждой пары S2i, S2i+1 сохранять полусумму (S2i + S2i+1)/2 и разность (S2i – S2i+1). Да лее эти потоки следует обрабатывать раздельно, поскольку их характери стики существенно различны.

К получаемым потокам можно и дальше рекурсивно применять разложение на полусуммы (Average) и разности (Delta). При сжатии аналоговых сигна лов, как правило, полезно дальнейшее разложение полусумм.

Есть два пути создавать три выходных потока или блока:

1. Original Average1+Delta DA+DD ( DA — Average2, получаемая при разложении разностей Delta1, DD — Delta2, получаемая при разложении Delta1. Аналогично с остальными обо значениями).

2. Original Average1+Delta AA+AD Пять вариантов создания четырех, 14 вариантов создания пяти, и так далее.

При принятии решения о целесообразности разложения некоторого потока или блока S на A и D, оказывается полезен следующий прием. Будем загля дывать на несколько шагов вперед: если непосредственные результаты раз ложения A и D сжимаемы суммарно хуже, чем исходный S, может оказать ся, что если разложить дальше A и/или D, то только тогда результат — три или четыре потока, по которым восстановим S, — сжимаем лучше, чем S.

Если же и эти AA, AD, DA, DD дают в сумме худшее сжатие, заглянем еще на шаг вперед, то есть попытаемся разложить эти вторичные результаты, и так далее, пока глубина такого просмотра не достигнет заданного предела, или же дальнейшее разложение окажется невозможным из-за уменьшения длин в два раза на каждом шаге.

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

• змейка (зигзаг-сканирование), • обход строками и столбцами, в т.ч. с разворотами, • полосами, в т.ч. с разворотами, • решетками, в т.ч. с учетом значений элементов, • контурный обход, в т.ч. с неизвестными контурами, • другие методы (по спирали, квадратная змейка).

Задача обхода плоскости возникает при обработке двухмерных данных.

Самым рапространенным видом таких данных являются изображения.

Цель метода: создание одномерного массива D из двухмерного S. Причем если предполагается последующее сжатие D, то желательно создавать его так, чтобы «разрывов» было как можно меньше: каждый следующий эле мент di, заносимый в D на i–ом шаге, является соседним (в плоскости) для предыдущего, занесенного в D на (i-1)–ом шаге, di-1.

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

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

В случае контура сложной формы может возникнуть необходимость поме чать уже обработанные точки плоскости, чтобы избежать лишних вычисле ний, предотвращающих повторное их занесение в D. Тогда есть два основ ных варианта: либо добавить по одному «флаговому» биту для каждой точ ки плоскости, либо выбрать (или добавить) значение для «флага», показы вающего, что точка уже внесена в D, и записывать это значение на место уже внесенных точек.

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

В третьей главе описываются методы сортирующих преобразований: Сор тировка параллельных блоков и Фрагментирование. Рассматриваются как простейшие «демонстрационные» варианты, так и достаточно сложные, более эффективные в некоторых важных частных случаях. Весь материал этой главы разработан и впервые описывается автором.

Два блока A и B называются параллельными, если каждому элементу A[i] первого блока поставлен в соответствие один элемент B[i] второго блока, и наоборот. Длины блоков LA и LB равны: LA = LB = L. Размеры элементов блоков RA и RB могут быть разными.

Основная идея метода PBS состоит в сортировке элементов In[i] входного блока In и их раскладывании в несколько выходных блоков Outj на основа нии атрибутов A[i] этих элементов. Атрибут A[i] есть значение функции A, определяемой значениями предшествующих элементов In[j] и/или элемен тов P[k] из параллельного блока P:

A[i]=A(i, In[j], P[k]), i=0...L-1;

j=0,...,i-1;

k=0,...,L- При декодировании осуществляется обратное преобразование: элементы из нескольких блоков Outj собираются в один результирующий, соответст вующий несжатому блоку In.

Чем лучше значения In[i] предсказуемы по значениям A[i], тем эффектив нее последующее сжатие блоков Outj с помощью простых универсальных методов.

В простейшем случае сортирующего преобразования ST(1) значение атри бута вычисляется так: A[i]=In[i-1] ;

при ST(2): A[i]=In[i-1]·2R + In[i-2], и так далее.

В простейшем же случае PBS A[i]=P[i], то есть значение атрибута равно значению элемента из параллельного блока. Выходных блоков столько, сколько значений принимают P[i]. Делая проход по P, считаем частоты зна чений атрибута, и в результате получаем размеры сортированных блоков (далее «контейнеров»), в которые будем раскладывать элементы из вход ного блока In:

for( a=0;

an;

a++) Attr[a]=0;

//инициализация (1) for( i=0;

iL;

i++) Attr[P[i]]++;

//подсчет частот (2) In — входной сортируемый блок длины L;

P — параллельный блок длины L;

L — количество элементов во входном блоке;

n=2R — число всех возможных значений атрибута;

Attr[n] — частоты значений атрибута.

Например, в P содержатся старшие 8 битов массива 16-битных чисел, а в In — младшие 8. Заметим, что этот процесс «дробления» можно продол жать и дальше, создавая вплоть до 16-и параллельных блоков: содержащий первые биты, вторые, и так далее. Кроме того, при сжатии мультимедийных данных часто уже имеются параллельные блоки: например, левый и правый каналы стереозвука, красная, зеленая и синяя компоненты изображения, и т.п.

Если функция A задана иначе, то и при подсчете частот формула будет иной:

// A[i]=P[i]&252 :

for( i=0;

iL;

i++) Attr[ P[i]&252 ]++;

// (2a) // A[i]=255-P[i] :

for( i=0;

iL;

i++) Attr[ 255-P[i] ]++;

// (2b) // A[i]=(P[i]+P[i-1])/2 :

Attr[ P[0] ]++;

// (2c) for( i=1;

iL;

i++) Attr[ (P[i]+P[i-1])/2 ]++;

Итак, после двух циклов — инициализации и подсчета частот —мы полу чили в массиве Attr длины контейнеров (сортированных блоков). Теперь можно вычислить, где какой контейнер будет начинаться, если их последо вательно сцепить в один блок в порядке возрастания значения атрибута:

for( a=0, pos=0;

an;

a++) { // (3) tmp=Attr[a];

// длина текущего a-го контейнера Attr[a]=pos;

// теперь там адрес-указатель на его начало // (указатель на начало свободного места в нем) pos+=tmp;

// начало следующего — дальше на длину текущего } В том же массиве Attr[n] теперь адреса-указатели на начала контейнеров.

Остается только пройти по входному блоку, раскладывая элементы из него по контейнерам:

for(i=0;

iL;

i++) Out[Attr[P[i]]++]=In[i];

//(4c) Out — выходной отсортированный блок (sorted, transformed), содержащий все контейнеры. Подробнее:

for( i=0;

iL;

i++) { // На каждом шаге:

s=In[i];

// берем следующий элемент s из входного блока In, a=P[i];

// берем его атрибут a из параллельного блока P, // и адрес свободного места в контейнере, задаваемом этим a;

pos=Attr[a];

// кладем элемент s в выходной блок Out по этому адресу, Out[pos]=s;

pos++;

//теперь в этом контейнере на один элемент больше, Attr[a]=pos;

//а свободное место — на один элемент дальше.

} Функция А — та же, что и во втором цикле. То есть, для выше рассмотрен ных примеров:

(2a) a=P[i]&252;

(2b) a=255-P[i];

(2c) a=(P[i]+P[i-1])/2;

//причем i=1...L-1, а когда i=0, a=P[0].

Обратное преобразование. Совершенно идентичны первые три цикла: ини циализируем, в результате прохода по параллельному блоку находим дли ны контейнеров, затем определяем адреса начал контейнеров во входном отсортированном блоке In. Именно эти адреса — цель выполнения первых трех циклов. И только в четвертом цикле — наоборот: берем из отсортиро ванного блока с контейнерами In, кладем в единый выходной блок Out:

for(i=0;

iL;

i++) Out[i]=In[Attr[P[i]]++];

//(4d) In — входной отсортированный блок со всеми контейнерами Out — создаваемый выходной блок Подробнее:

for( i=0;

iL;

i++) { a=P[i];

pos=Attr[a];

//так было при прямом (сжимающем) преобразовании:

//Out[pos]=In[i];

//(в текущих обозначениях это записывается так:

//In[pos]=Out[i];

) //а так делаем сейчас, при разжимающем преобразовании:

Out[i]=In[pos];

pos++;

Attr[a]=pos;

} Фрагментирование. Цель: разбиение исходного потока или блока на фрагменты с разными статистическими свойствами. Такое разбиение долж но увеличить степень последующего сжатия. В простейшем случае битово го потока необходимо находить границы участков с преобладанием нулей, участков с преобладанием единиц, и участков с равномерным распределе нием нулей и единиц. Если поток символьный, может оказаться выгодным разбить его на фрагменты, отличающиеся распределением вероятностей элементов: например, на фрагменты с русским текстом и фрагменты с анг лийским.

Основная идея состоит в том, чтобы для каждой точки потока X (лежащей между парой соседних элементов) находить значение функции отличия FO(X) предыдущей части потока от последующей. В базовом простейшем варианте используется «скользящее окно» фиксированной длины: Z эле ментов до точки X, и Z элементов после нее.

Иллюстрация (Z=7):

…8536429349586436542 | 9865332 | X | 6564387 | 58676780674389… Цифрами обозначены элементы потока, вертикальными чертами «|» грани цы левого и правого окон. X — не элемент потока, а точка между парой элементов, в данном случае между ”2“ и ”6“.

При фиксированной длине окон Z и одинаковой значимости, или весе, всех элементов внутри окон (независимо от их удаленности от точки X), значение функции отличия может быть легко вычислено на основании раз ности частот элементов в левом и правом окнах. Это сумма по всем 2R воз можным значениям Vi элементов. Суммируются абсолютные значения раз ностей: число элементов с текущим значением V в левом окне длиной Z минус число элементов с данным значением V в правом окне длиной Z.

Суммируя 2R модулей разности, получаем значение FO(X) в данной точке X:

2 R CountLeft[V ] CountRight[V ], FO ( X ) = V = где CountLeft[V] — число элементов со значением V в левом окне;

CountRight[V] — число элементов со значением V в правом окне.

Видно, что если в обоих окнах элементы одинаковые, то сумма будет стре миться к нулю, если же элементы совершенно разные — к 2·Z.

Для приведенного выше примера:

V= 2 3 4 5 6 7 8 FO(X) = +|1-0| +|2-1| +|0-1| +|1-1| +|1-2| +|0-1| +|1-1| +|1-0| = После того как все значения FO(X) найдены, остается отсортировать их по возрастанию и выбрать границы по заданному критерию (заданное число границ и/или пока FO(X)Fmin).

В четвертой главе рассмотрены некоторые методы сжатия источников данных без памяти: SEM, VQ, ENUC. Показано, что SEM (разделение ман тисс и экпонент) является большим семейством методов сжатия, содержа щим методы универсального кодирования как частный случай. Обсужда ются четыре основных варианта SEM:

• Фиксированная длина экспоненты — фиксированная длина мантис сы, • Фиксированная длина экспоненты — переменная длина мантиссы, • Переменная длина экспоненты — переменная длина мантиссы • Переменная длина экспоненты — фиксированная длина мантиссы.

Описано, как коды Элиаса и Голомба можно обобщить и задавать с двумя параметрами.

В пятой главе подробно описано семейство методов сжатия изображений без потерь ERI97. Существенно используется материал, изложенный в пре дыдущих главах.

Основные свойства описываемой группы алгоритмов:

1. Размер получаемых данных равен размеру задаваемых данных плюс A байт служебной информации (A зависит только от параметров, задаваемых алгоритму).

2. Скорость работы ERI97 сравнима со скоростью аналогов – JPEG, PNG, LOCO – но качество достигаемого cжатия – уже сейчас лучше на 10%-70% (не вариант JPEG-а без потерь, а именно JPEG с поте рями, но лучшим качеством).

3. Алгоритм состоит из последовательности четырех независимых действий, причем • каждое из них работает с каждым пикселом (элементом изо бражения);

• любые из них могут быть пропущены при прямой и затем при обратной трансформации;

• "сжимающая" трансформация (компрессор) осуществляет их в прямом порядке, а "разжимающая" трансформация (декомпрес сор) – в обратном.

4. Скорость работы компрессора в общем случае равна скорости де компрессора и зависит только от размера данных, но не от их со держания: Ск=O(размер).

5. Памяти требуется 2*(размер входных данных)+C.

6. В общем случае отсутствуют операции умножения и деления.

7. Число N компонент каждого пиксела, как и разрядность пикселов R, являются двумя из множества задаваемых параметров, и могут быть произвольными.

Четыре действия, из которых состоит ERI97, компрессор выполняет в сле дующем порядке:

1. Первичная обработка 2. Контекстная обработка 3. Обход плоскости 4. PBS, Сортировка параллельных блоков При разжатии эти действия выполняются в обратном порядке.

Первые три действия в том или ином виде присутствуют во всех аналогич ных методах. Первые два действия не имеют отношения к PBS и могут со вершаться отдельно, практически никак не ориентируясь на последующую PBS. Более того, каждое из них может выполняться параллельно, распада ясь на P процессов, причем возможные значения P – от 1 до S, где S – число пикселов в обрабатываемом блоке. Первое действие настолько тривиально, что в практической реализации легко может быть совмещено со вторым.

Тем не менее, поскольку логически это разные действия, в описании алго ритма они идут отдельно.

Алгоритм был реализован в компьютерной программе ERI в 1997-ом году и активно совершенствуется в течение последних четырех лет.

Основные отличия реализации – программы ERI (последняя версия на те кущий момент – 21-е мая 2002-го года – 5.1fre) :

1. Примерно десять внешне задаваемых параметров.

2. В настоящее время поддерживается только режим N=3, R=8, то есть каждый пиксел состоит из трех 8-битных компонент.

3. Байт-ориентированность: операции над битами по возможности сведе ны к минимуму, что многократно увеличивает скорость работы, но не много ухудшает качество сжатия.

В настоящее время ERI достигает лучших результатов среди всех извест ных аналогов по сжатию без потерь малошумных 24-битных изображений.

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

В приложениях даны результаты сравнения работы программы ERI с дру гими программами, сжимающими полноцветные изображения: лучшие из известных программ, а также программы, реализующие промышленные стандарты (PNG, LOCO-I/JPEG-LS, baseline JPEG).

Основные результаты и выводы В работе показано, что • разработанный автором класс ЛПК-фильтров оказывается на практике выгоднее, чем несколько фильтров, используемых в алгоритмах PNG и LOCO-I и являющихся лишь частными случаями из множества ЛПК фильтров описываемого класса;

• в случае разложения сжимаемых данных на высокочастотную и низко частотную компоненты с помощью субполосного кодирования и дис кретного вэйвлетного преобразования, возможно не просто рекурсив ное применение такого разложения, но и «рекурсия с просмотром на шаг вперед»;

• разработаны и впервые описаны обощенные методы сортировки;

опти мизированные варианты методов PBS и фрагментирования существен но лучше «демонстрационных» по скорости и требованиям к объему рабочей памяти.

• широко известные коды Элиаса и Голомба можно обобщить и задавать с двумя параметрами, вследствие чего степень сжатия многих типов данных (этими кодами) существенно улучшится;

• многие методы, не считавшиеся принадлежащими к группе методов «Представление целых чисел» (в частности DAKX исследователя Д.А.Копфа и «структурная модель» Фенвика) реально используют ту же идею (разделение мантисс и экспонент) и принадлежат одному из четырех основных вариантов;

• использование векторного квантования и нумерующего кодирования являются очень перспективными направлениями исследований, в част ности в задаче сжатия изображений без потерь;

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

Основные публикации по теме диссертации 1. Д.Ватолин, А.Ратушняк, М.Смирнов, В.Юкин. Методы сжатия дан ных. Учебное пособие. // Москва, «Диалог-Мифи» - 2002. 384 стр.

http://compression.graphicon.ru 2. Ратушняк О.А. Методы фрагментирования, анализа структуры и сжа тия импульсно-сигнальной информации, а также устройство для их реализации. Патент РФ No. 3. Ратушняк О.А. О сжатии информации. // КомпьютерПресс. - 2000. №.5 – стр. 160-163.

4. Ратушняк О.А. Сжатие мультимедийной информации. // Hard’n’Soft.

- 2001. - №.4 – стр. 78-79.

5. Ратушняк О.А. Высокоэффективные алгоритмы сжатия изображений без потерь. // Сборник материалов 5-й Международной Конференции "Распознавание-2001", Курск 2001– стр. 155-158.

6. Ратушняк О.А. Алгоритмы сжатия изображений без потерь с помо щью сортировки параллельных блоков. // Тезисы докладов конфе ренции молодых учёных по математике, мат. моделированию и ин форматике, Новосибирск, 4-6 декабря 2001 г. – стр. 48-49.