(по цифровому вещанию) Dvorkovich_V_Cifrovye_videoinformacionnye_sistemy

Глава 5. Визуальная избыточность изображений

Рис. 5.16. Изменение цветового тона далеко расположенных друг от друга деталей голубого цвета

Растровый формат TIFF (Tag Image File Format) [2.121] — стандартный метод хранения монохромных, индексированных, полутоновых и полноцветных изображений в моделях RGB и CMYK с восьми- и шестнадцатибитовыыми каналами. Его модификации 4.0–6.0 поддерживают обработку цветных RGB-изобра- жений c цветовым форматом до 24 битов/пиксел. TIFF — один из многоцелевых

иразносторонних растровых форматов, обладающих возможностью расширения

иподдержки различных схем сжатия цифровых данных — RLE, LZW, CCITT, JPEG. TIFF-файлы содержат заголовки файла изображений IFH (Image File Header), директории файла изображений IFD (Image File Directory) и растровые данные. Допускается возможность существования файла, не содержащего растровых данных. Директория файла изображений содержит информацию о ширине, высоте и пиксельном формате изображения, количестве цветовых плоскостей и типе сжатия данных.

Формат PXR (Pixar) [2.124] предназначен для высокоразвитых современных графических станций и программ трехмерной графики, используется для обмена со специализированными графическими станциями Pixar, ориентированными на трехмерное моделирование и анимацию. Поддерживаются только полутоновые и полноцветные RGB-изображения. Сокращение избыточности не применяется.

5.6. Компьютерные методы хранения изображений

Рис. 5.17. Изменение цветового тона далеко расположенных друг от друга деталей пурпурного цвета

Метафайловый формат EMF (Microsoft Enhanced Metafile) [2.125] — относительно новый формат. При сохранении в формате EMF растровые изображения переводятся в векторную форму. Если простые растровые образы передаются после векторизации достаточно точно, то аппроксимация картинок с плавными цветовыми переходами, градиентными заливками и полутонами иногда требует очень большого количества векторных объектов. Это замедляет перерисовку экрана и выполнение всех вычислительных операций. Файлы EMF экономно расходуют дисковое пространство. Максимальная глубина цвета — 32 бита/пиксел, сжатие не предусматривается.

Растровый формат TGA (Truevision Graphics Adapter, Targa Graphics Adapter Image) [2.121] широко применяется для обработки и хранения изображений, данные которых имеют глубину до 32 бита/пиксел. Он известен также под сокращенными названиями VST, VDA, ICB, TPIC. Хорошо документированный формат широкого применения, схема сжатия недостаточно эффективна — используется алгоритм сжатия RLE. Формат TGA использует три метода упорядочения данных изображения: псевдоцвет, direct-color и truecolor. Цветовые таблицы псевдоцветных изображений определяют каждый цвет в виде отдельного

Глава 5. Визуальная избыточность изображений

Рис. 5.18. Изменение цветового тона наложенных друг на друга деталей желтого цвета

элемента, причем значения отдельного цветового канала индивидуально недоступны. Изображения direct-color подобны псевдоцветным изображениям, однако в них каждый цветной канал RGB записывается как отдельный элемент и может быть модифицирован индивидуально — значения каждого пиксела содержат три индекса, по одному на каждый канал цветовой таблицы. Изображения truecolor (полноцветные) хранят цветовую информацию пиксела непосредственно в данных изображения, для их отображения цветовая таблица не применяется.

Растровый формат BMP (Microsoft Windows Bitmap) [2.121] — это собственный формат Windows, использующийся для хранения практически всех растровых данных. Формат известен также как DIB, Windows BMP, Windows DIB, Compatible Bitmap. В настоящее время используется множество версий формата BMP, которые разрабатывались для компьютеров, базирующихся на процессорах Intel, и по этой причине общей их чертой является хранение данных в порядке байтов «little endian». Данные об изображениях имеют цветовую глубину до 32 бита/пиксел при максимальных размерах до 2Γ ×2Γ пикселов. Файлы BMP содержат заголовок файла, информационный заголовок, цветовую палитру и растровые данные. Несжатые данные изображения представляют собой либо

5.6. Компьютерные методы хранения изображений

Рис. 5.19. Изменение цветового тона наложенных друг на друга деталей голубого цвета

индексы в цветовой палитре, либо реальные RGB-значения. Пикселы упаковываются в байты и упорядочиваются по строкам развертки. Формат Windows BMP поддерживает простую схему группового кодирования RLE, обеспечивающую сжатие только 4-битовых и 8-битовых растровых данных.

Метафайловый формат PCT (Macintosh PICT, PICT) [2.126] — собственный формат Macintosh, применим и для растровых, и для векторных изображений. Несмотря на то, что он используется преимущественно для обмена графическими данными между приложениями Mac, его поддерживают и многие программы для PC. Современная версия поддерживает до 32 битов на пиксел. Файлы PICT-формата могут поддерживать объектно-ориентированную векторную графику и растровые изображения. Изображения в PICT могут содержать графические данные в разнообразных подформатах, включая двухцветные растровые изображения, полноцветные изображения JPEG или список команд рисования. В формате PICT используется схема сжатия RLE.

Растровый формат PCX (PC Paintbrush File Format) [2.121] — один из широко используемых форматов, применяется для хранения иллюстраций в настольных издательских системах. Он известен также под сокращенными назва-

Глава 5. Визуальная избыточность изображений

Рис. 5.20. Изменение цветового тона наложенных друг на друга деталей пурпурного цвета

ниями DCX и PCC. Данные об изображениях имеют цветовую глубину до 24 битов/пиксел при максимальных размерах до 64K × 64K пикселов. Данные изображения могут кодироваться с использованием алгоритма RLE, который нельзя назвать эффективным. Файлы PCX состоят из заголовка, данных изображения и цветовой палитры. Пиксельные данные строк развертки хранятся либо в пик- сельно-ориентированном, либо в плоскостно-ориентированном виде. Пиксельноориентированные данные хранятся в виде непрерывной строки последовательно записанной пиксельной информации, независимо от того, это реальные данные или индексы цветовой палитры. При хранении по плоскостям данные разбиваются на RGB-составляющие и группируются по цвету в строки развертки.

Векторный формат SWF (Adobe Flash, Shockwave Flash) [2.127] может включать в себя текст, векторную и растровую графику; проигрывается в веббраузерах, которые имеют установленный модуль проигрывания flash мультимедийного контента для платформы «Adobe Engagement Platform» (такого, как веб-приложения, игры и мультфильмы). SWF-формат является в настоящее время единственным векторным форматом, файлы которого могут использоваться

5.6. Компьютерные методы хранения изображений

Таблица 5.2. Размеры файлов различных форматов с изображением «Гавань»

при создании Web-страниц. На Web-странице можно как разместить отдельные элементы, так и разработать практически всю страницу целиком на основе технологии Flash. Предусматривается сжатие информации по стандарту Lossless JPEG.

Растровый формат PNG (Portable Network Graphic Format) [2.121] позволяет хранить изображения, битовая глубина которых до 16 битов в полутоновых или до 48 битов в полноцветных изображениях при максимальном размере изображения 2Γ × 2Γ пикселов. Этот формат обеспечивает поэтапное отображение данных изображения, хранение информации о показателе гамма, о прозрачности, о текстовой информации. В нем используется эффективный метод сжатия без потерь LZW. Данные изображения в формате PNG представлены в виде растра, строки которого записаны слева направо, сверху вниз. В начале каждой строки развертки записывается дополнительный байт «типа фильтра», который используется при сжатии и распаковке изображения и указывает тип алгоритма филь-

Глава 5. Визуальная избыточность изображений

Рис. 5.21. Статическое изображение «Гавань» («Harbour»)

трации, примененный при обработке строки. Формат чисел — «big endian». Формат PNG разработан как альтернатива стандарту Graphics Interchange Format (GIF) и существенно его превосходит по функциональным возможностям.

Растровый формат GIF (Graphics Interchange Format) [2.121] является форматом, обеспечивающим передачу и хранение данных об изображениях, однако он не поддерживает хранение полноцветных изображений. Используемая палитра цветов — до 256, максимальный размер изображения — 64K × 64K пикселов. GIF в отличие от многих растровых форматов использует потоковое хранение данных. GIF-файл состоит из последовательности пакетов данных и дополнительной протокольной информации, при этом файл читается так, как будто он является непрерывным потоком данных. Формат чисел — «little endian». Для кодирования данных изображения, записанного в GIF-файле, применяется метод LZW, позволяющий сжимать строки байтов с одинаковыми значениями в отдельное кодовое слово и способный уменьшить размер 8-битовых пиксельных данных практически до двух раз. Формат позволяет хранить в одном файле несколько изображений, но эта возможность редко используется. Формат поддерживает возможность хранения и воспроизведения изображений с чересстрочной разверткой.

Растровый формат JPEG (JPEG File Interchange Format) [2.121] изначально предназначался для хранения графики и изображений. Он известен также под сокращенными названиями JFIF, JFI, JPG. JPEG File Interchange Format ис-

5.6. Компьютерные методы хранения изображений

пользуется для хранения данных, закодированных с использованием стандарта JPEG, разработанного организацией Joint Photographic Experts Group (Объединенная группа экспертов по фотографии). Формат позволяет хранить цветные изображения, битовая глубина которых достигает максимум 24 бита/пиксел при размере изображения до 64K×64K пикселов. Данные представляют собой потоки байтов, причем 16-битовые слова хранятся в формате чисел «big endian». Формат обеспечивает сжатие информации с потерями. При сохранении JPEG-файла можно указать степень сжатия, которую обычно задают в некоторых условных единицах. При этом побитно восстановленное изображение всегда отличается от оригинала. Распространенным заблуждением является мнение о том, что качество JPEG тождественно доле сохраняемой информации. При сжатии изображение переводится в цветовую систему YCbCr. Далее каналы изображения Cb и Cr, отвечающие за цвет, уменьшаются в 4 раза (в два раза по горизонтали и по вертикали). Уже на этом этапе необходимо хранить только четверть информации о цвете изображения. Далее каналы изображения, включая черно-белый канал Y, разбиваются на блоки 8 × 8 пикселов. Каждый блок подвергается дискретнокосинусному преобразованию. Полученные коэффициенты подвергаются квантованию и упаковываются с помощью кодов переменной длины. Матрица, используемая для квантования коэффициентов, хранится вместе с изображением. Обычно она строится так, что высокочастотные коэффициенты подвергаются более сильному квантованию, чем низкочастотные. Это приводит к огрублению мелких деталей на изображении. Чем выше степень сжатия, тем более сильному квантованию подвергаются все коэффициенты. Применяются различные способы записи сжатого изображения. Progressive JPEG — такой способ записи сжатого изображения в файл, при котором старшие (низкочастотные) коэффициенты находятся в начале файла. Это позволяет получить уменьшенное изображение при загрузке лишь небольшой части файла и повышать детализацию изображения по мере загрузки оставшейся части. Поэтому Progressive JPEG получил широкое распространение в Интернете. К недостаткам формата следует отнести то, что при сильных степенях сжатия дает знать о себе блочная структура данных, изображение «дробится на квадратики» (каждый размером 8 ×8 пикселов). Этот эффект особенно заметен на областях с низкой пространственной частотой (плавные переходы изображения, например, чистое небо). В областях с высокой пространственной частотой (например, контрастные границы изображения) возникают характерные «артефакты» — иррегулярная структура пикселов искаженного цвета и/или яркости. Кроме того, из изображения пропадают мелкие цветные детали. Однако несмотря на недостатки JPEG получил очень широкое распространение из-за высокой степени сжатия по отношению к существовавшим во время его появления форматам.

2.1.Цифровая обработка телевизионных и компьютерных изображений. 2-е изд., перераб. и доп./ Под ред. Ю.Б. Зубарева и В.П. Дворковича. М.: НАТ, 1997.

2.2.Шеннон К. Работы по теории информации и кибернетике/ Пер. с англ под ред. Р.Л. Добрушина и О.Б. Лупанова. М.: Иностранная литература, 1963.

2.3.Gallager R.G. Information Theory and Reliable Communication/ John Wiley and Sons, Inc. N.Y. 1968.

2.4.Netravali A.N., Haskell B.G. Digital pictures: Representation and Compression: Plenum Press. N.Y. 1991.

2.5.Гонсалес Р., Вудс Р. Цифровая обработка изображений. М.: Техносфера, 2005.

2.6.Семенюк В.В. Экономное кодирование дискретной информации. СПб.: ИТМО, 2001.

2.7.Golomb S.W. Run-Length Encoding// IEEE Trans. Inform. Theory. 1966. Vol. 12. № 3.

2.8.Rice R.F. Some Practical Universal Noiseless Coding Techniques: JPL Publications 79-22. Jet Propulsion Lab. Pasadena, California, USA, Mar., 1979.

2.9.Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. М.: ДИАЛОГМИФИ, 2003.

2.10.Дискретная математика: Алгоритмы. Кодирование целых чисел. СПб.: СПбГУ информационных технологий, механики и оптики http://rain.ifmo.ru/cat/view.php/theory/coding/integer-2005

2.11.Fenwick P. Punctured Elias Codes for variable-length coding of the integers// Technical Report 137. 1996. Dec., 5.

2.12.Fano F.M. Technical. N 65. The Research Laboratory of Electronics// Technical. № 65., MIT Mar., 17, 1949.

2.13.Хаффмен Д.А. Метод построения кодов с минимальной избыточностью// Кибернетический сборник. М., ИЛ, 1961. Вып. 3.

2.14.Pasco R. Source Coding Algorithms For Fast Data Compression, Ph.D. dissertation, Dept of Electrical Engineering. Stanford University, California, USA, 1976.

2.15.Rissanen J.J. Generalized Kraft Inequality and Arithmetic Coding// IBM J. Res. Develop., 1976. Vol. 20, 6. № 3.

2.16.Rissanen J.J., Langdon G.G. Arithmetic Coding// IBM J. Res. Develop., 1979. Vol. 23. № 2.

2.17.Pennebaker W.B., Mitchell J.L., Langdon G.G., Arps R.B. An Overview of the Basic Principles of the Q-Coder Adaptive Binary Arithmetic Coder// IBM J. Res. Develop., 1988. Vol. 32. № 6.

Литература к части II

2.18.Rissanen J.J., Langdon G.G. Arithmetic Coding// IBM J. Res. Develop., 1979. Vol. 23. № 2.

2.19.Rubin F. Arithmetic Stream Coding Using Fixed Precision Registers// IEEE Trans. Inform. Theory, 1979. Vol. 25. № 6.

2.20.Guasso M. A General Minimum-Redundancy Source-Coding Algorithm// IEEE Trans. Inform. Theory, 1980. Vol. 26. № 1.

2.21.Martin G.N.N. Range encoding: an algorithm for removing redundancy from a digitized message// Video & Data Recording Conference. IBM UK Scientific Center, Southampton. July, 1979.

2.22.Cleary J., Witten I.H. Data Compression Using Adaptive Coding and Partial String Matching// IEEE Trans. Commun., 1984. Vol. 32. № 4.

2.23.Mo at A., Neal R., Witten I.H. Arithmetic Coding Revisited// Proc IEEE Data Compression Conf. Snowbird, Utah, USA. Mar., 1995.

2.24.Howard P.G., Vitter J.S. Practical Implementations of Arithmetic Coding// Storer A. Image and Text Compression, Kluwer Academic Publishers. Massachusetts, USA, 1992.

2.25.Ziv J., Lempel A. A Universal Algorithms for Sequential Data Compression// IEEE Trans. Inform. Theory. 1977. Vol. 23/ № 3.

2.26.Ziv J., Lempel A. Compression of Individual Sequences via Variable-Rate Coding// IEEE Trans. Inform. Theory/ 1978. Vol. 24. № 5.

2.27.Rodeh M., Pratt V.R., Even S. Linear Algorithm for Data Compression via String Matching // J. ACM. 1981. Vol. 28., № 1.

2.28.Storer J.A., Szymanski T.G. Data Compression via Textual Substitution// J. ACM. 1982. Vol. 29. № 4.

2.29.Bell T.C. Better OPM/L Text Compression// IEEE Trans. Commun. 1986. Vol. 34. № 12.

2.30.Bell T.C. A Unifying Theory and Improvements for Existing Approaches to Text Compression, Ph.D. Dissertation. Dept. of Computer Sciences, University of Centerbury. New Zealand, 1987.

2.31.Brent R.P. A Linear Algorithm for Data Compression// Aust. Comput. J. 1987. Vol. 19. № 2.

2.32.Welch T.A. A Technique for High-Performance Data Compression// IEEE Computer. 1984. Vol. 17. № 6.

2.33.Thomas S.W., McKie J., Davies S., Turkowski K., Woods J.A., Orost J.W.

Compress (Version 4.0): Program and Documentation, 1985.

2.34.Tischer P. A Modified Lempel-Ziv-Welch Data Compression Scheme// Aust. Comput. Sci. Commun., 1987. Vol. 9. № 1.

2.35.Miller V.S., Wegman M.N. Variations on a Theme by Ziv and Lempel// Apostolico A., Galil Z. Combinatorial Algorithms on Words. Springer-Verlag, New York, USA, 1985.

2.36.Jacobson M. Compression of Character String by an Adaptive Dictionary// BIT. 1985. Vol. 25. № 4.