 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| BaseLine Compression Method in JPEG Files |  Алексей Абрамов |
05.05.2000 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 
20k | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
В данном документе будет рассмотрен не столько алгоритм JPEG-компрессии (информацию о нем можно найти на многих сайтах Internet и даже в сборниках документации на CD), сколько о внутреннем устройстве самого JPEG-файла (к сожалению, подробно будет рассмотрен только способ сжатия Baseline). Для примера будут приведены выдержки из листинга на языке Borland Pascal 7.0 моего просмотрщика с подробными комментариями (я опустил описания переменных и констант). Предположим, надо вывести на экран файл, записанный в формате JPEG Baseline. Если Вы уже прошли через операции считывания битов и многобайтовых целых, то можете обратиться сразу к следующей странице, дабы Вам не наскучило сие "нудное" занятие. Для начала определимся, что нам необходимо иметь функции считывания информации из файла (1 байта, 2-байтового целого, 1 бита, 4-битных частей байта). Стандартными операциями работы с файлами предусмотрено только считывание целого количества байт. Далее следует функция считывания одного байта из файла и записи его значения в переменную "текущего байта" для дальнейшей обработки. function ReadByte:byte; begin BlockRead(PictureFile,Current_byte,1); ReadByte:=Current_byte; inc(FilePtr); Current_bit:=0 end; Порядок байт в 2-байтовых переменных отличается от Intel-стандарта, то есть сначала пишется старший байт, затем младший. Поэтому применяем для переменной типа WORD предусмотренную функцию Swap. function ReadWord:word; var Current_word:word; begin BlockRead(PictureFile,Current_word,2); ReadWord:=Swap(Current_word); inc(FilePtr,2) end; Таким же образом пишутся и биты - сначала старшие, затем младшие. Если счетчик текущего бита = 0, то нам необходим следующий байт. Если байт равен $FF (255), то - это: (Об этом чуть позже). Берем из байта один бит (путем операций побитового смещения и логических) и прибавляем счетчик на 1; если он достиг 8 (вышел за пределы байта), то счетчик необходимо обнулить, следующий байт считаем в следующий раз.
function Read1bit:byte;
begin
if Current_bit=0 then begin
ReadByte;
if Current_byte=$FF then begin
Repeat ReadByte Until Current_byte<$FF;
if (Current_byte>=$D0) and
(Current_byte<=$D7) then FillChar(DC,SizeOf(DC),0);
if Current_byte=0 then Current_byte:=$FF else ReadByte
end
end;
Read1bit:=(Current_byte shr (7-Current_bit)) and 1;
inc(Current_bit); if Current_bit=8 then Current_bit:=0
end;
Далее - операции прибавления к целому следующего бита и считывания нескольких бит. procedure NextBit(var V:longint); begin V:=(V shl 1)+Read1bit end; function ReadBits(bits:byte):word; var i:byte; L:longint; begin L:=0; For i:=1 to bits do NextBit(L); ReadBits:=L end; Затем следуют опреации деления одного байта на две 4-битные части (не всегда легче и лучше считать два раза по 4 бита). function Hi4(b8:byte):byte; begin Hi4:=b8 shr 4 end; function Lo4(b8:byte):byte; begin Lo4:=b8 and $F end; В файле JPEG присутствует понятие значения, отличного от 0, причем принято значения с большей амплитудой записывать в большее количество бит согласно следующей таблице:
Далее следует операция преобразования значения с заданным числом бит в целое со знаком. Например, для последовательности из трех бит 010 (двоичное значение - два) функция Bits2Integer(3,2) дает результат "-5" (минус пять); для значений, у которых старший бит = 1, битовое значение соответствует целому со знаком "плюс".
function Bits2Integer(bits:byte; value:word):integer;
begin
if (value and (1 shl (bits-1))>0) then
Bits2Integer:= value
else
Bits2Integer:=-(value xor (1 shl bits-1))
end;
Функция выявления кода Хаффмана из битового потока (побитное считывание однозначно определяет этот код - на этом принципе построена таблица Хаффмана, подробнее - см. теорию упаковки ZIP, LZH и др.). Метод построения таблицы будет рассмотрен после считывания маркера определения таблицы Хаффмана из JPEG-файла.
function HuffmanCode(T,C:byte):word;
var i,L:byte; V:longint;
begin
L:=0; V:=0;
Repeat
inc(L);
NextBit(V);
For i:=0 to $FF do if (Huff_Tab.C[T,C,i].L=L) and
(Huff_Tab.C[T,C,i].V=V) then
begin HuffmanCode:=i; Exit end;
Until L=16;
HuffmanCode:=V
end;
На следующей странице будут рассмотрены функции преобразования цветового пространства JPEG (яркость + цветоразность) в стандартный RGB-цвет и операции вывода на экран в 24 или 32-битном режиме по стандарту VESA. Преобразование ведется по формулам: R = [ Y + 1,402 (Cr - 128) ]; G = [ Y - 0,34414 (Cb - 128) - 0,71414 (Cr - 128) ]; B = [ Y + 1,772 (Cb - 128) ]; (уменьшение значений цветоразностей требуется для преобразования их из байтового значения, в котором они хранятся, в знаковое целое). Далее идет проверка на преодоление порога яркости (0:255) и обрезание значений до входа в диапазон 8-битового значения. procedure YCbCr2RGB(Y,Cb,Cr:integer; var R,G,B:byte); var RR,GG,BB:integer; begin RR:=Round(Y +1.40200*(Cr-128)); GG:=Round(Y-0.34414*(Cb-128)-0.71414*(Cr-128)); BB:=Round(Y+1.77200*(Cb-128)); if RR<0 then R:=0 else if RR>255 then R:=255 else R:=RR; if GG<0 then G:=0 else if GG>255 then G:=255 else G:=GG; if BB<0 then B:=0 else if BB>255 then B:=255 else B:=BB end; Далее следуют операции, описанные в документации по VESA видео режимам и функциям, которые вполне можно заменить собственными операциями вывода изображения на плоттер, например, или записи его в память. Но в конкретном примере я использовал именно их для простоты и наглядности. Операция определения текущего банка памяти (обычно размером 64 Kb). procedure SetBank(bank:word); assembler; asm mov ax,4F05h mov bx,0 mov dx,Bank int 10h end; Операции ввода-вывода RGB значений точки с заданными координатами X, Y. procedure pointRGB(x,y:word; r,g,b:byte); var a:longint; begin a:=(longint(y)*Xres+x)*BytesPerPixel; SetBank(a div BankSize); mem[$A000:a mod BankSize]:=b; inc(a); SetBank(a div BankSize); mem[$A000:a mod BankSize]:=g; inc(a); SetBank(a div BankSize); mem[$A000:a mod BankSize]:=r end; procedure pixelRGB(x,y:word; var r,g,b:byte); var a:longint; w:word; begin a:=(longint(y)*Xres+x)*BytesPerPixel; SetBank(a div BankSize); b:=mem[$A000:a mod BankSize]; inc(a); SetBank(a div BankSize); g:=mem[$A000:a mod BankSize]; inc(a); SetBank(a div BankSize); r:=mem[$A000:a mod BankSize] end; Наконец-то, далее - текст основной программы (правда, слегка усеченный):
Begin
if ParamCount<1 then begin
Write('Please enter JPEG file name : ');
ReadLn(FileName)
end else FileName:=ParamStr(1);
Assign(PictureFile,FileName); Reset(PictureFile,1);
if IOResult<>0 then begin
WriteLn('File "',FileName,'" not found');
Halt
end;
Fillchar(Huff_Tab,SizeOf(Huff_Tab),0);
For m:=$C0 to $FE do Marker[m]:=False;
method:=0;
RestartInterval:=0;
Итак, мы имеем имя входного файла (FileName), у нас обнулены значения в таблицах Хаффмана (Huff_Tab), присутствие маркеров (Marker), метод кодирования (method) и интервал перезапуска (RestartInterval). Зачем? Файл JPEG состоит из сегментов, отмеченных маркерами, наподобие тегов TIFF, при этом каждый маркер начинается с байта $FF (255), за ним следует байт, определяющий тип маркера:
Остальные значения маркеров не поддерживаются или зарезервированы. После кода каждого маркера следует 2-байтовый размер сегмента (вначале идет старший байт, затем - младший); сегмент включает в себя 2 байта своего размера. Исключениями являются начало ($D8) и конец ($D9) изображения - после них не следуют ни размер, ни содержимое блока; после кода начала сканирования DA (SOS) следует только размер заголовка, затем идет содержимое - сжатые данные. Исходя из изложенного материала и приведенной таблицы, можно начинать ввод данных об изображении и вспомогательных данных для его раскодирования. Далее приведен цикл последовательной обработки сегментов вплоть до маркера начала сканирования. Если мы раньше встретим маркер конца изображения, то изображения в этом файле нет или файл испорчен, сбой вызовет также ошибка чтения. Начало кадра определяет основные параметры изображения - ширину, высоту, глубину (количество бит на компонент) - для Baseline кодирования всегда равно 8, количество компонентов (обычно 1 - для черно-белых или 3 - для полноцветных изображений), показатели дискретизации. Также считывается информация о номерах таблиц квантования для каждого компонента. Если встречается маркер определения таблиц, то считывание идет до последнего байта сегмента - таблиц может быть записано несколько подряд без разделения на сегменты (счетчик считанных из сегмента байт (FilePtr) увеличивается в функции ReadByte на 1, а в ReadWord - на 2) и чтение сегмента заканчивается по достижении счетчиком значения длины сегмента. В сегменте начала сканирования определяются номера таблиц Хаффмана DC и AC коэффициентов для каждого компонента, а также параметры этих таблиц. Зигзагообразное преобразование таблиц квантования и векторов из 64 элементов, а также метод построения таблиц Хаффмана (!) рассмотрим через страницу.
Repeat
BlockRead(PictureFile,v,2);
if Lo(v)<>$FF then begin WriteLn('Invalid file format');
Close(PictureFile); Halt end;
b:=Hi(v); Marker[b]:=True;
Z:=FilePos(PictureFile);
if (b<>$D8) and (b<>$D9) then begin
BlockRead(PictureFile,v,2); v:=Swap(v);
Case b of
$C0,$C1,$C2,$C3,$C5,$C6,$C7,$C9,$CA,$CB,$CD,$CE,
$CF: begin
vv :=ReadByte;
Height:=ReadWord;
Width :=ReadWord;
planes:=ReadByte;
if (vv<>8)
or ((planes<>1) and (planes<>3)) then begin
WriteLn('Only 8-bit Grayscale or RGB images supported');
Close(PictureFile);
Halt
end;
For hh:=1 to planes do begin
ComponentID[hh].C:=ReadByte; vv:=ReadByte;
ComponentID[hh].H:= Hi4(vv);
ComponentID[hh].V:= Lo4(vv);
ComponentID[hh].T:=ReadByte
end;
method:=b end;
$C4: begin FilePtr:=2;
Repeat
hh:=ReadByte;
For vv:=1 to 16 do Huff_Tab.L[vv]:=ReadByte;
For vv:=1 to 16 do
For m :=1 to Huff_Tab.L[vv] do
Huff_Tab.V[vv,m]:=ReadByte;
w:=0;
For vv:=1 to 16 do begin
For m :=1 to Huff_Tab.L[vv] do begin
Huff_Tab.C[Hi4(hh),Lo4(hh),Huff_Tab.V[vv,m]].L:=vv;
Huff_Tab.C[Hi4(hh),Lo4(hh),Huff_Tab.V[vv,m]].V:=w;
inc(w)
end;
w:=w shl 1
end
Until FilePtr>=v
end;
$DA: begin
m:=ReadByte;
For hh:=1 to m do begin
Scan.Component[hh]:=ReadByte; vv:=ReadByte;
Scan.TD[hh]:=Hi4(vv);
Scan.TA[hh]:=Lo4(vv)
end;
Scan.Ss:=ReadByte;
Scan.Se:=ReadByte;
vv:=ReadByte;
Scan.Ah:=Hi4(vv);
Scan.Al:=Lo4(vv)
end;
$DB: begin FilePtr:=2;
Repeat
hh:=ReadByte;
For vv:=0 to $3F do
if Hi4(hh)=0 then ZigZag[Lo(hh),vv]:=ReadByte else
ZigZag[Lo(hh),vv]:=ReadWord
Until FilePtr>=v
end;
$DD: begin RestartInterval:=ReadWord end
End;
Seek(PictureFile,Z+v);
if IOResult<>0 then begin WriteLn('I/O error !');
Close(PictureFile); Halt end
end
Until (b=$D9) or (b=$DA);
if (method<>$C0) or (b=$D9) then
begin
WriteLn('Not Baseline JPEG');
Close(PictureFile);
Halt
end;
Хочу отметить, что система проверяет правильность внутренних данных JPEG-файла, и при ошибке корректно прерывает выполнение программы. Данные в JPEG-файле упорядочены в блоки по 64 элемента - 8x8. Чтобы их удобнее было хранить и обрабатывать применяется так называемое зигзагообразное преобразование. При раскодировании нам потребуется обратное, то есть при обращении к двухмерному массиву с индексацией 0:7, 0:7 получить порядковый номер элемента (0:63) в одномерном массиве - векторе из 64-х коэффициентов. Этого можно добиться при обращении к константе ZigZag2Table:
Const ZigZag2Table:array [0..7,0..7]
of byte=(( 0, 1, 5, 6,14,15,27,28),
( 2, 4, 7,13,16,26,29,42),
( 3, 8,12,17,25,30,41,43),
( 9,11,18,24,31,40,44,53),
(10,19,23,32,39,45,52,54),
(20,22,33,38,46,51,55,60),
(21,34,37,47,50,56,59,61),
(35,36,48,49,57,58,62,63));
Если с таблицей квантования все более или менее понятно - в байте перед списком из 64-х элементов указывается номер таблицы (младшие 4 бита) и формат данных (если старшие 4 бита в этом байте = 0, то далее следуют 64 байта, иначе - 128 байт или 64 двухбайтовых значения) - то с таблицей Хаффмана придется повозиться. Итак, приступим. Читаем 1 байт, в нем старшие 4 бита указывают тип таблицы (1 - DC, 0 - AC), а младшие 4 бита - номер таблицы, на который затем будет ссылаться обрабатываемый компонент (обычно имеется одна таблица для яркости, другая - общая для обоих коэффициентов цветоразности). Затем - 16 байт, каждый из которых указывает количество кодов Хаффмана для так называемых "потоков бит" с длинами от 1 до 16 бит. После этого пишутся сами значения кодов Хаффмана, причем сумма числа кодов равна сумме 16-ти длин. Построение таблицы Хаффмана производится следующим образом:
Честно говоря, тот, кто знаком с битовыми операциями, легко сможет разобраться по листингу (алгоритм, наверное, не потребуется). Далее следует инициализация видеорежима $112 - 640x480, 32bits (предполагается, что стандарт VESA и данный видеорежим поддерживаются оборудованием или программно). w :=$112; Xres:= 640; Yres:= 480; BytesPerPixel:=4; BankSize :=65536; asm mov ax,4F02h mov bx,w int 10h end; А сейчас, когда все подготовительные работы выполнены, начинается раскодирование изображения. X & Y - координаты левого верхнего угла выводимого участка. Его размер может изменяться и зависит от максимальных показателей горизонтальной и вертикальной дискретизации. Например, показатель горизонтальной дискретизации (H) для яркости (Y) равен 4, показатель вертикальной дискретизации - VY = 2; аналогично, для цветоразности: HCb = 1, VCb = 1; HCr = 1; VCr = 1. Максимальными обычно являются показатели для яркости, отсюда размер выводимого участка по горизонтали - 4x8=32, по вертикали - 2x8=16, следовательно, резервируем блок данных 32x16. Все компоненты равномерно распределяем по этому блоку, то есть значения яркости, в данном случае, будут назначены для каждой точки, а цветоразности - по одному для блока точек 4x2 (в общем случае, показатели цветоразности могут быть разными для Cb и Cr). Показатели дискретизации указывают количество блоков данных 8x8. В каждом таком блоке большие значения данных расположены ближе к верхнему левому углу (0,0), а меньшие - к нижнему правому (7,7). В блоке обычно присутствует большое количество нулей, что дает возможность кодировать их последовательности.
Если последний элемент вектора не равен 0, то код конца блока отсутствует. Затем необходимо деквантовать вектор - просто умножить каждый элемент на соответствующий ему множитель из таблицы квантования. После зигзагообразного преобразования вектора необходимо произвести обратное ДКП (Дискретное Косинусоидальное Преобразование) по формуле:
c(0,0)=1/2; c(0,v)=1/ u, v - индексы вектора F, над которым выполнено обратное зигзагообразное преобразование и деквантование, x, y - индексы блока данных изображения f.
Case method of
$C0: begin
if not (Marker[$C4] and Marker[$DB]) then begin
WriteLn('Tables markers not found');
Close(PictureFile);
Halt
end;
FillChar(DC,SizeOf(DC),0);
Y:=0;
Repeat
X:=0;
Repeat
For b:=1 to planes do
For vv:=1 to ComponentID[b].V do
For hh:=1 to ComponentID[b].H do Begin
Z:=HuffmanCode(0,Scan.TD[b]);
Vector[0]:=DC[b]+Bits2Integer(Lo4(Z),ReadBits(Lo4(Z)));
DC[b]:=Vector[0];
xx:=1;
Repeat
Z:=HuffmanCode(1,Scan.TA[b]);
if Z=0 then
Repeat
Vector[xx]:=0;
inc(xx)
Until xx>=64
else begin
yy:=xx+Hi4(Z);
While xx<yy do begin
Vector[xx]:=0;
inc(xx)
end;
Vector[xx]:=Bits2Integer(Lo4(Z),ReadBits(Lo4(Z)));
inc(xx)
end
Until xx>=64;
For yy:=0 to 7 do
For xx:=0 to 7 do begin
sum:=0;
For v:=0 to 7 do
For w:=0 to 7 do begin
m:=ZigZag2Table[v,w];
idct:=Vector[m]*ZigZag[ComponentID[b].T,m]
*Cos((2*xx+1)*w*Pi/16)
*Cos((2*yy+1)*v*Pi/16);
if w=0 then idct:=idct/sqrt(2);
if v=0 then idct:=idct/sqrt(2);
sum:=sum+idct
end;
w:=X+(hh-1)*8+xx;
v:=Y+(vv-1)*8+yy;
if (w<Width) and (v<Height) then begin
Z:=Round(sum/4)+128;
if Z<0 then Z:=0;
if Z>255 then Z:=255;
if b=1 then pointRGB(w,v,Z,Z,Z)
else begin
pixelRGB(w,v,r,g,m);
if b=2 then pointRGB(w,v,r,Z,Z)
else pointRGB(w,v,r,g,Z)
end
end
end
End;
Если изображение черно-белое (в оттенках серого), то каждый блок данных равен блоку 8x8 и дальнейшее преобразование для этих блоков не потребуется. Для удобства и сокращения использования ресурсов я использовал для предварительного хранения данных о яркости и цветоразности область видеоданных (хотя это значительно замедляет процесс и для создания оптимального просмотрщика совершенно не обязательно) - значение яркости пишется на красную цветовую плоскость, значения цветоразности - на синюю и зеленую плоскости. Затем данные с каждой плоскости преобразовываются и распределяются по всей рабочей области текущего блока (лучше слов об этом расскажет листинг).
if planes>1 then
For yy:=ComponentID[1].V*8-1 downto 0 do
For xx:=ComponentID[1].H*8-1 downto 0 do
if (X+xx<Width) and (Y+yy<Height) then begin
pixelRGB(X+xx,Y+yy,r,g,b);
Z:=r;
pixelRGB(X+(xx*ComponentID[2].H) div ComponentID[1].H,
Y+(yy*ComponentID[2].V) div ComponentID[1].V,r,g,b);
v:=g;
pixelRGB(X+(xx*ComponentID[3].H) div ComponentID[1].H,
Y+(yy*ComponentID[3].V) div ComponentID[1].V,r,g,b);
w:=b;
YCbCr2RGB(Z,v,w,r,g,b); pointRGB(X+xx,Y+yy,r,g,b)
end;
Inc(X,ComponentID[1].H*8)
Until X>=Width;
if RestartInterval>0 then Current_bit:=0;
Inc(Y,ComponentID[1].V*8)
Until Y>=Height
end;
End;
Координаты X и Y увеличиваются соответственно на 8 Hmax и 8 Vmax, причем в конце каждой строки, если интервал перезапуска больше 0, обнуляется значение текущего бита, то есть при этом данные в файле для каждой строки выровнены по байту. При встрече маркера интервала перезапуска обнуляются DC-коэффициенты. Далее - закрытие файла, нажатие "Enter", переход в текстовый режим и, собственно, все!
Close(PictureFile);
ReadLn;
asm
mov ax,3
int 10h
end;
End.
(С) 2000 Alex (Алексей Абрамов) По всем вопросам обращаться лично ко мне по адресу E-mail: tm@osu.ac.ru Программа рассчитана только на JPEG-файлы, закодированные методом Baseline с глубиной цвета 8 бит (256 оттенков каждого цвета) на одну (черно-белое изображение ) или три цветовых плоскости (полноцветное), вывод производится начиная с крайнего левого верхнего угла экрана до конца файла (может выйти за пределы экрана). С нетерпением буду ждать отзывов, замечаний, предложений, а главное - сообщений о замеченных ошибках и неточностях (претензии по скорости работы не принимаются). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
, если v≠0; c(u,0)=1/