BaseLine Compression Method in JPEG Files

В данном документе будет рассмотрен не столько алгоритм 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-ти длин.

Построение таблицы Хаффмана производится следующим образом:

1. полагаем переменную текущего "потока бит" равной потоку из 1 бита (как правило, этот бит нулевой);
2. проверяем количество кодов для потоков длиной 1 бит (на самом деле таких потоков в принципе может быть только 2 - "0" и "1"), в таблицах Хаффмана обычно больше 2 кодов, поэтому это количество всегда равно нулю - запись в таблицу Хаффмана на текущем шаге не производится;
3. увеличиваем количество бит в потоке на 1;
4. добавляем в конец текущего битового потока нулевой бит, то есть не только умножаем его значение на 2 (производим двоичный сдвиг по разряду налево), но добавляем в поток еще одну цифру "0" (следует различать "0" и "00");
5. проверяем количество кодов соответствующих текущей длине битового потока, считываем первый код;
6. пишем этот код в таблицу таким образом (для облегчения поиска): элемент массива длин битового потока с индексом кода Хаффмана = количеству бит в текущем потоке, элемент массива кодов битового потока с тем же индексом - сам битовый поток;
7. увеличиваем значение битового потока на 1 (не увеличиваем количество бит, а изменяем сами биты внутри потока, изменяя число, представленное ими в двоичной форме - например, было "0101"=5, стало "0110"=6);
8. если существуют еще коды, соответствующие текущей длине битового потока, переходим к пункту 6, иначе - к 9;
9. если количество кодов для текущей длины исчерпано и текущая длина (количество бит в потоке) меньше 16-ти, переходим к пункту 3 и далее.

Честно говоря, тот, кто знаком с битовыми операциями, легко сможет разобраться по листингу (алгоритм, наверное, не потребуется).

Далее следует инициализация видеорежима $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). В блоке обычно присутствует большое количество нулей, что дает возможность кодировать их последовательности.

1. В начале декодирования изображения обнуляем DC-коэффициенты для всех компонентов.
2. Сначала декодируем нулевой элемент вектора из 64-х коэффициентов, для этого выбираем из битового потока код Хаффмана по таблице для DC-коэффициентов, теперь мы знаем, сколько бит содержит значение разницы между нулевым элементом и значением DC для предыдущего блока текущего компонента. Считываем данное количество бит из битового потока, подсчитываем DC-коэффициент, он же - нулевой элемент. Увеличиваем счетчик элементов на 1.
3. Теперь читаем следующий элемент: считываем код Хаффмана для AC таблицы, разбиваем его на 2 части по 4 бита - старшие 4 бита указывают количество нулей перед отличным от нуля значения элемента, а младшие - количество бит, содержащих значение следующего за нулями элемента.
4. Если значение кода Хаффмана - "0"&"0" (так называемый "конец блока"), то это значит, что до конца вектор заполнен нулями - заполняем и выходим из цикла декодирования вектора.
5. Иначе - увеличивая счетчик на количество предшествующих нулей, заполняем вектор нулями, следующему за ними элементу придаем считанное значение, увеличиваем счетчик на 1.
6. Если счетчик не достиг значения 64 (не вышел за пределы вектора), переходим к пункту 2.

Если последний элемент вектора не равен 0, то код конца блока отсутствует. Затем необходимо деквантовать вектор - просто умножить каждый элемент на соответствующий ему множитель из таблицы квантования. После зигзагообразного преобразования вектора необходимо произвести обратное ДКП (Дискретное Косинусоидальное Преобразование) по формуле:

c(0,0)=1/2; c(0,v)=1/, если v≠0; c(u,0)=1/, если u≠0; c(u,v)=1, если u≠0 и v≠0; 

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.