ПОИСК
Категории книг
ОПРОС
Вопрос: Какой язык программирования вы предпочитаете
С/C++
Delphi
Visual Basic
Perl
Java
PHP
ASP
Другой
ЭТО ПОЛЕЗНО!
ОБРАТНАЯ СВЯЗЬ

/ Главная / Программирование / Иллюстрированный самоучитель по SVGA
Иллюстрированный самоучитель по SVGA

 

Воспроизведение сжатых рисунков

Для сокращения размера файлов образы рисунков могут храниться в сжатом виде. Частным случаем является упаковка точек 16- и 2-цветных рисунков, когда в байте располагаются коды двух или восьми подряд расположенных точек (см. раздел). Здесь нас будут интересовать способы упаковки и распаковки 256-цветных рисунков.

Сразу отметим, что в этой области нет никакой унификации, и разработчики стандартов для хранения и передачи файлов выбирают способ сжатия по своему усмотрению. В данном разделе основное внимание уделено способу сжатия, получившему название RLE (Run-Length-Encoding), который предусмотрен в стандартах PCX, BMP и некоторых других. Он дает далеко не лучшие результаты, но имеет одно неоспоримое преимущество, которое заключается в простоте распаковки. Это позволяет привести исчерпывающее описание способа построения рисунка. Стандарт BMP описан в приложении А данной книги, здесь описан стандарт PCX.

Стандарт создала фирма ZSoft разработчик графических редакторов PaintBrush, PhotoFinish и пр. Ему, как и многим другим стандартам, присущи некоторые разночтения, вызванные тем, что улучшать устаревающие версии пыталась не только ZSoft, но и некоторые другие фирмы, например Genius Microprogramming.

Заголовок PCX-файла имеет фиксированный размер 80h байтов, сразу после него (начиная с адреса воь) располагается образ рисунка. Нас будут интересовать лишь некоторые байты и слова заголовка.

Байт 0 должен содержать код ОАЬ, являющийся признаком того, что файл соответствует стандарту PCX.

Байт 1 содержит версию стандарта (от 0 до 5), в частности код 5 соответствует третьей версии стандарта, в которой впервые было введено использование 256-цветной палитры.

Байт 2 содержит 1, если образ рисунка хранится в сжатом виде, или 0 -в противном случае (распаковка не требуется).

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

Слова 4, 6, 8 и OAh содержат минимальные и максимальные значения координат рисунка (xmin, Ymin, xmax, Ymax). Ширина и высота рисунка вычисляются так: iwidth = Xmax - Xmin + 1, iheight = Ymax - Ymin + 1.

Слово 42h содержит размер строки рисунка в байтах, мы обозначим его содержимое fwidth. При четном количестве точек в строке iwidth = fwidth, при нечетном количестве точек в строке fwidth = iwidth + 1. В этом случае строка содержит дополнительный байт, который учитывается при распаковке, но не выводится на экран, т. к. его содержимое не определено.

Заголовок файла содержит и другие величины, но в данном разделе они нам не понадобятся. Более подробную информацию о заголовке рсх-файлов вы найдете в книге, а мы вернемся к рассмотрению стандарта PCX при описании работы с палитрой и построения полноцветных рисунков.

Техника распаковки строки

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

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

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

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

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

Подпрограмма распаковки строки

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

GenOffs dw 0 ; адрес (смещение) в буфере общего назначения
GenSeg dw 0 ; сегмент, содержащий буфер общего назначения

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

Текст подпрограммы распаковки строки приведен в примере 3.24.

Пример 3.24. Распаковка строки рисунка (способ RLE для PCX)

Unpack: PushReg <ax,cx,dx,di,es> ; сохранение содержимого регистров
les di, Dword ptr GenOffs; смещение и сегмент буфера
mov dx, fwidth ; логический размер строки
Unploop: call nxt sym ; читаем в al следующий символ
mov ex, 01 ; количество повторяемых символов
cmp al, OCOh ; символ содержит счетчик повторов ?
jbe Unl ; -> нет, это одиночный символ
mov cl, al ; копируем содержимое al в cl
and cl, 3Fh ; и выделяем количество повторов
call nxt sym ; читаем в al — повторяемый символ
Unl: sub dx, ex ; уменьшаем остаток строки
rep stosb ; записываем символы в буфер строки
or dx, dx ; строка распакована полностью ?
jnz Unploop ; нет, продолжение распаковки
PopReg <es, di, dx, ex, ax> ; восстанавливаем регистры
ret ;-> возврат из подпрограммы

В примере 3.24 перед началом распаковки в стеке сохраняется содержимое используемых регистров. Затем команда les загружает в регистры es:di адрес для записи распакованной строки. Размер строки в байтах помещается в регистр dx, используемый в качестве счетчика распакованных символов. После этого выполняется цикл Unploop.

Действия при распаковке соответствуют описанному выше алгоритму. Очередной байт считывается в регистр al, а в счетчик повторов сх записывается 1. Если код символа меньше чем сон, то происходит пеереход на метку ип_1. В противном случае в cl помещается содержимое 6-ти младших разрядов регистра al и читается повторяемый символ.

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

Подпрограмма Nxtjsym. Для получения кода очередного байта в примере 3.24 вызывается подпрограмма Nxtjsym, текст которой приведен в примере 3.25.

Пример 3.25. Чтение очередного символа из буфера обмена

Nxt sym: cmp si, incount в буфере есть символы ?
jb @F -> да, можно читать очередной символ
push ex сохраняем содержимое сх
mov ex, -I указываем размер порции данных
call Readf читаем данные из файла
mov incount, ax сохраняем размер порции данных
xor si, si очищаем указатель адреса
pop ex восстанавливаем содержимое сх
@@: lods byte ptr fs : [si] чтение очередного байта
ret ; возврат из подпрограммы

Подпрограмма примера 3.25 сравнивает текущее значение указат еля адреса буфера обмена (содержимое регистра si) с переменной incount.-, значение которой соответствует размеру считанной из файла порции данных, т. е. количеству байтов, находящихся в буфере обмена.

Если в буфере достаточно данных, то происходит переход на локальную метку @@ Для чтения кода символа в регистр al, увеличения указат-теля адреса на 1 и выхода из подпрограммы.

Если достигнута граница данных, хранящихся в буфере обменна, то надо прочитать новую порцию данных. Для этого сохраняется содержимое регистра сх, в него записывается предельное количество байтов для чтения (-1 имеет код OFFFFh) и происходит обращение к подпрограмме Readf, описанной в примере 3.23.

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

В примере 3.25 отсутствует проверка состояния С-разряда регистра признаков после чтения. Вы можете включить ее в текст примера 3.25., но целесообразнее контролировать правильность чтения непосредственно-о в подпрограмме Readf. Это упростит структуру всех подпрограмм, котогдрые обращаются К Readf.

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

Построение рисунка

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

Предварительно вы должны открыть файл и прочитать его заголовок для определения значений переменных iheight, iwidth и fwidth. I После чтения заголовка указатель файла содержит значение 80h, соответствующее началу образа рисунка.

Перед вызовом подпрограммы в регистре di указывается адресе левой верхней точки рисунка в видеопамяти и устанавливается соответствующее окно. Регистр es должен содержать код видеосегмента. В разделе данных задачи надо описать переменную incount, имеющую размер слова, HI в ней подпрограмма хранит количество символов, прочитанных в буфер обм/мена.

Пример 3.26. Построение рисунка, упакованного в стандарте PCX

PackDrw
PushReg <cx,si,di,C
jr win>; сохранение используемых величин
xor si, si
очистка регистра si
mov incount, si
incount = 0
mov ex, iheight
ex = количество строк в рисунке
nake:
push ex
сохраняем счетчик повторов
call Unpack
распаковка очередной строки
PushReg <fs,si>
сохранение содержимого fs и si
Ifs si, dword ptr
GenOffs; fs:si = адрес распакованной строки
mov ex, iwidth
сх = количество точек в строке
call drawline
вывод строки рисунка на экран
PopReg <si, fs>
восстановление содержимого fs и si
mov ax, horsize
копируем в ах ширину экрана и
sub ax, iwidth
вычитаем из нее ширину рисунка
add di, ax
адрес начала следующей строки
jnc @F
-> адрес в пределах видеосегмента
call Nxtwin
установка следующего окна
s@:
pop ex
восстановление счетчика повторов
loop make
управление циклом рисования
PopReg <Cur win,di,
з!,сх>; восстановление из стека
call SetWin
восстановление исходного окна
ret
возврат из подпрограммы

Выполнение подпрограммы примера 3.26 начинается с сохранения в стеке тех величин, которые могут измениться при ее работе. Для того чтобы при тервом обращении к подпрограмме Nxt_sym она прочитала в буфер обмена тень образа рисунка, содержимое регистра si должно совпадать со значением переменной incount. Поэтому регистр si и переменная incount очищаются. В регистре сх указывается количество строк рисунка iheight.

Дикл построения рисунка имеет метку make. Его выполнение начинается с охранения в стеке содержимого регистра сх и вызова подпрограммы unpack. Чосле распаковки в стеке сохраняется содержимое регистров fs, si и соманда ifs загружает в них адрес начала распакованной строки. В регистре ;х указывается размер строки iwidth и вызывается подпрограмма drawline шя записи строки в видеопамять. Какой именно вариант этой подпрограммы вы будете использовать, не имеет значения.

После возврата из подпрограммы drawline восстанавливается содержимое >егистров si и fs, вычисляется константа для коррекции адреса строки в мдеопамяти (horsize - iwidth), которая прибавляется к текущему адресу (видеопамяти, находящемуся в регистре di. Если при сложении произойдет переполнение, то подпрограмма Nxtwin установит следующее окно видео-памяти.

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

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

Недостатки сжатия по способу RLE

Способ сжатия RLE используется не только в стандарте PCX, но и в стандарте BMP. В деталях эти варианты различаются, но в главном они совпадают. При упаковке группа одинаковых кодов (одноцветных точек) заменяется двумя байтами, в первый записывается количество повторов, а во второй — повторяемый код.

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

Характеристика стандарта GIF

Проблема сжатия рисунков приобрела особую важность по мере развития сначала локальных, а затем и глобальных сетей ЭВМ. В июне 1987 года компания CompuServe Incorporated опубликовала описание стандарта GIF (Graphics interchange Format — формат графического обмена). Для сжатия рисунков в нем применяется модифицированный алгоритм LZW (Lempei-ziv-weich), используемый в распространенных архиваторах текстовых данных. На сегодняшний день это наилучший способ сжатия растровых рисунков, подготовленных с использованием палитры цветов.
Алгоритмы LZW и RLE различаются принципиально. Главный недостаток RLE заключается в самой идее подсчитывать число подряд расположенных совпадающих кодов. Способ LZW избавлен от этого недостатка. При сжатии запоминаются и используются все последовательности встречающихся в рисунке точек, независимо от совпадения или различия их цветов. В выходной файл записываются не байты, а цепочки битов переменной длины, коды которых соответствуют кодам отдельных точек или их комбинаций.

Предположим, что размер кодов точек рисунка равен к, а их значения изменяются от 0 до N-I, где N = 2):. Например, если в рисунке используются все 256 цветов, то к= 8, а N = 256. Первоначально для хранения цепочек отводится к+1 разряд. Если код цепочки меньше N, то это просто код одной точки. Коды N и N+I имеют специачьное назначение. Комбинации точек кодируются, начиная от значения ы+2. Какой комбинации соответствует тот или иной код цепочки (если он больше чем N+I) можно узнать только из таблицы цепочек.

Первоначально таблица цепочек пуста, в процессе сжатия в нее записываются все новые (отсутствующие в таблице) комбинации точек. Если таблица окажется полностью заполненной, то размер цепочек увеличивается на I разряд и увеличивается пространство, отведенное для таблицы. Предельно допустимый размер цепочки составляет 12 разрядов. Если этого окажется недостаточно (вероятность такого события мала), то в выходной файл записывается специальный признак новой таблицы (код N), таблица цепочек очищается, выбирается размер цепочки, равный к+i, и продолжается процесс сжатия с формированием новой таблицы.

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

Для сравнения приведем размеры файла, хранящегося в трех стандартах:

ciouds.bmp 307514 файл не упакован, 640x480 точек
ciouds.pcx 300527 файл упакован по способу RLE
ciouds.gif 159287 файл упакован по способу LZW

Файл ciouds.bmp (облака.bmp) выбран по двум причинам. Во-первых, это одна из стандартных заставок Windows 9X и вы можете увидеть хранящийся в нем рисунок. Во-вторых, этот рисунок трудно сжимаемый, и применение способа RLE не дает ощутимых результатов. Тем не менее стандарт GIF сокращает размер файла почти в два раза, причем это не лучший результат. Сжатие файла выполнено с помощью графического редактора PhotoFinish фирмы ZSoft. Этот редактор (как и любой другой) при упаковке не изменяет количество цветов. В рисунке "Облака" используется 65 цветов. Если пожертвовать одним из них, то размер кода точки сократится с 7-ми до 6-ти разрядов, а размер файла в формате GIF сократится почти в 4 раза. Однако для анализа и сокращения количества цветов нужна специальная программа.

Стандарт GIF разрабатывался специально для передачи данных по компьютерным сетям. Поэтому упакованный файл разбит на отдельные блоки (при ошибке передачи повторно передается только один блок).

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

 


Компьютерные книги © 2006-2013
computers.plib.ru