Алгоритмы сжатия данных (стр. 1 из 3)

Московский государственный университет имени Ломоносова

Механико-математический факультет

Курсовая работа

на тему «Алгоритмы сжатия данных»

Студент 3го курса И. Межиров

Научный руководитель А. Шень

Москва 2004

Оглавление

Введение ............................................................................................. 1

Основной алгоритм сравнения пары букв........................................... 3

Быстрый отказ для пары разных букв................................................. 5

Получение монохромных изображений ........................................... 7

Ссылки.................................................................................................... 9

Введение

В этой работе описывается способ улучшения сжатия файлов формата DjVu.

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

Этот формат был придуман и развивался в фирме AT&T между 1995 и 1999 годами. В 2000 году все права были проданы фирме LizardTech. В том же году LizardTech опубликовала часть кода под лицензией GPL. На основе этого кода группа разработчиков, работавшая над этим проектом в AT&T, создала свой независимый вариант (тоже под лицензией GPL), который называется DjVuLibre [1]. В бесплатно доступных программах есть возможности разархивирования и просмотра DjVu-файлов, но только демонстрационное сжатие. К сожалению, эти программы не работают под Windows (разве что через cygwin — перенос среды Unix в Windows). Программы с полными возможностями продаются фирмой LizardTech; с ее сайта [4] можно также бесплатно скачать программу для просмотра DjVu под Windows.

В DjVu-файле хранится отдельно фон, передний план и монохромная маска, определяющая, какие пиксели изображения принадлежат фону, а какие — переднему плану. Фон и передний план кодируются алгоритмом IW44, который, как и JPEG, несколько размывает изображение. Авторы утверждают, что IW44 достигает уменьшения размеров файла в два раза по сравнению с JPEG при том же уровне искажений.

Черно-белая маска кодируется алгоритмом JB2. Этот алгоритм достигает сжатия в 4-6 раз лучшего, чем TIFF-G4 (CCITT/MMRGroup 4). Как и в случае со многими другими алгоритмами (МРЗ, например), алгоритм декодировщика определен жестко, однако в алгоритме кодировщика возможны изменения, улучшающие сжатие.

Часть DjVu-файла, сжатая по алгоритму JB2, представляет собой заархивированную последовательность команд. Эти команды могут иметь вид "поставить такое-то изображение в такую-то точку", а могут иметь вид "поставить одно из ранее встречавшихся изображений в такую-то точку". Так как в первом случае команда содержит целое изображение, пусть и заархивированное, а во втором случае — всего лишь номер, то ясно, что чем больше элементарных изображений одинаковы, тем лучше будет сжатие.

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

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

При помощи алгоритмов, разработанных автором, размер файла уменьшается на 55 ± 5% (для страниц, содержащих только текст; рисунки и диаграммы уменьшают этот показатель, так как занимают много места и не сжимаются). Единственная некоммерческая программа для ЛВ2-сжатия, cjb2 из DjVuLibre, достигает уменьшения размера только на 30 ± 5%.

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

Возможность «нет» существует только для ускорения. Если алгоритм вместо «нет» будет всегда говорить «может быть», то результат не изменится, но скорость упадет (в программе скорость падает в 4,5 раза).

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

Рассмотрим все буквы в тексте и применим к каждой паре сравнение. Теперь объявим классами связные компоненты относительно ответа «да». Это и будет тот ответ, который выдает программа. Однако программа работает быстрее за счет того, что классов обычно намного (в среднем в 5-10 раз) меньше, чем букв. Кроме того, она учитывает ответы «нет».

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

Итак, возьмем новую букву и по очереди сравним ее со всеми имеющимися классами. Сравнение буквы с классом устроено так: буква сравнивается со всеми элементами класса до получения первого ответа «да» или «нет», который и объявляется результатом сравнения буквы с классом. Если все сравнения дали «может быть», то результатом сравнения буквы с классом будет «нет».

Теперь объединим букву и все классы, давшие ответ «да», в один класс, после чего перейдем к следующей букве.

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

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

В DjVuLibre 3.5 используется простой алгоритм сравнения пары букв. Изображения накладываются одно на другое и считается количество отличающихся пикселей. Если это количество не превышает 6% от их общего числа (в одной из картинок), то буквы считаются одинаковыми. Порог в 6% подбирался экспериментально и, кстати, иногда дает ошибки, отождествляя буквы «и» и «н».

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

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

Способ состоит в следующем: определяется некоторое преобразование черно-белого изображения — «очистка». В ходе очистки белые пиксели остаются белыми. После нескольких последовательных очисток изображение перестает меняться. Черные пиксели, выжившие все очистки, объявляются наиболее важными; важность остальных черных пикселей уменьшается в геометрической прогрессии по мере того, на сколько очисток меньше они выдержали.

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

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

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

Знаки вопроса означают, что пиксель может быть любого цвета. Таким образом, картинка с четырьмя знаками вопроса эквивалентна шестнадцати отдельным раскраскам.

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

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

Третье правило запрещает удаление одиночных пикселей.

Четвертое правило означает, что только пиксели с границы черного и белого могут быть удалены.

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

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

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

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