Опрос

Какой архиватор наиболее эффективный?:

Новички

Виктор Васильев
Юрий Антонов
Сергей Андреевич
Генадий
Avanasy

Классы приложений

Примеры приложений, использующих алгоритмы компрессии графики

Рассмотрим следующую простую классификацию приложений, исполь­зующих алгоритмы компрессии:

Класс 1. Характеризуются высокими требованиями ко времени ар­хивации и разархивации. Нередко требуется просмотр уменьшенной ко­пии изображения и поиск в базе данных изображений. Примеры: издатель­ские системы в широком смысле этого слова, причем как готовящие качест­венные публикации (журналы) с заведомо высоким качеством изображений и использованием алгоритмов архивации без потерь, так и готовящие газе­ты, и WWW-серверы, где есть возможность оперировать изображениями меньшего качества и использовать алгоритмы сжатия с потерями. В подоб­ных системах приходится иметь дело с полноцветными изображениями са­мого разного размера (от 640x480- формат цифрового фотоаппарата, до 3000x2000) и с большими двуцветными изображениями. Поскольку иллю­страции занимают львиную долю от общего объема материала в документе, проблема хранения стоит очень остро. Проблемы также создает большая разнородность иллюстраций (приходится использовать универсальные ал­горитмы). Единственное, что можно сказать заранее, - это то, что будут преобладать фотореалистичные изображения и деловая графика.

Класс 2. Характеризуется высокими требованиями к степени архи­вации и времени разархивации. Время архивации роли не играет. Ино­гда подобные приложения также требуют от алгоритма компрессии легко­сти масштабирования изображения под конкретное разрешение монитора у пользователя. Пример: справочники и энциклопедии на CD-ROM. С появ­лением большого количества компьютеров, оснащенных этим приводом (в США уровень в 50% машин достигнут еще в 1995 г.), достаточно быстро сформировался рынок программ, выпускаемых на лазерных дисках. Не­смотря на то что емкость одного диска довольно велика (примерно 650 Мб), ее, как правило, не хватает. При создании энциклопедий и игр большую часть диска занимают статические изображения и видео. Таким образом, для этого класса приложений актуальность приобретают существенно асимметричные по времени алгоритмы (симметричность по времени - от­ношение времени компрессии ко времени декомпрессии).

Класс 3. Характеризуется очень высокими требованиями к степени архивации. Приложение клиента получает от сервера информацию по сети. Пример: новая быстро развивающаяся система "Всемирная информацион­ная паутина" - WWW. В этой гипертекстовой системе достаточно активно используются иллюстрации. При оформлении информационных или рек­ламных страниц хочется сделать их более яркими и красочными, что, есте­ственно, сказывается на размере изображений. Больше всего при этом стра­дают пользователи, подключенные к сети с помощью медленных каналов связи. Если страница WWW перенасыщена графикой, то ожидание ее пол­ного появления на экране может затянуться. Поскольку при этом нагрузка на процессор мала, то здесь могут найти применение эффективно сжимаю­щие сложные алгоритмы со сравнительно большим временем разархивации. Кроме того, мы можем видоизменить алгоритм и формат данных так, чтобы просматривать огрубленное изображение файла до его полного получения.

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

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

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

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

ТРЕБОВАНИЯ ПРИЛОЖЕНИЙ К АЛГОРИТМАМ КОМПРЕССИИ

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

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

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

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

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

Масштабирование изображений. Данное требование подразумевает легкость изменения размеров изображения до размеров окна активного при­ложения. Дело в том, что одни алгоритмы позволяют легко масштабировать изображение прямо во время декомпрессии, в то время как другие не только не позволяют легко масштабировать, но и увеличивают вероятность появ­ления неприятных артефактов после применения стандартных алгоритмов масштабирования к декомпрессированному изображению. Например, мож­но привести пример "плохого" изображения для алгоритма JPEG - это изо­бражение с достаточно мелким регулярным рисунком (пиджак в мелкую клетку). Характер вносимых алгоритмом JPEG искажений таков, что уменьшение или увеличение изображения может дать неприятные эффекты.

Возможность показать огрубленное изображение (низкого разреше­ния), использовав только начало файла. Данная возможность актуальна для различного рода сетевых приложений, где перекачивание изображений мо­жет занять достаточно большое время и желательно, получив начало файла, корректно показать preview. Заметим, что примитивная реализация указан­ного требования путем записывания в начало изображения его уменьшен­ной копии заметно ухудшит степень компрессии.

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

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

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

Небольшая стоимость аппаратной реализации. Эффективность про­граммной реализации. Данные требования к алгоритму реально предъяв­ляют не только производители игровых приставок, но и производители мно­гих информационных систем. Так, декомпрессор фрактального алгоритма очень эффективно и коротко реализуется с использованием технологии ММХ и распараллеливания вычислений, а сжатие по стандарту CCITT Group 3 легко реализуется аппаратно.

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

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