|
Info Guide
#10
30 апреля 2007 |
|
Форматы - Подробно о декодере jpeg.
Всем привет! Помните меня? :) Поскольку тема данной статьи интересует многих, я, не долго думая, решил нацарапать статейку. Несмотря на всю кажущуюся сложность, постараюсь изложить всё в простой, понятной форме. Хочу сразу предупредить: всё, о чем я буду писать, есть результат моих собственных экспериментов, а посему не является истиной в последней инстанции. Это всего лишь мои мысли. Таким образом, если что не так, я не виноват :). В статье буду использовать фрагменты из документации по жпегу by Ceryx, а также оптимизированные и страшно изуродованные:)) куски кода из пасовского исходника жпег декодера by Алексей Абрамов. Там, правда, мало что от него осталось, но в любом случае его я использовал в качестве базы. Данный материал не рассчитан на но─ вичков - как минимум, требуются знания языка Паскаль. Вступление сказано, теперь переходим непосредственно к делу. Декодирование жпега можно разделить на две стадии. 1-я - Сканирование жпега, обработка маркеров и загрузка таб─ лиц. Это стадия начальной инициализации, на ней осуществляется настройка декодера на соответствующий жпег, всё это я опишу в первую очередь. 2-я - Непосредственно сам процесс декодирования, это найдёте дальше по тексту. Для лучшего понимания алгоритмов, кое-где буду приводить куски пасовского исходника. Немного теории. JPEG представляет собой упакованный кадр фотореалистичного изображения, то есть расчитан он в основном на сжатие цветных фотографий с глубиной цвета 24 бита (до цветовых преобразований подразумевается по 8 бит на каждую цветовую ком─ поненту RGB). Чтобы было понятно, как декодировать жпег, вкратце опишу процесс сжатия кадра. Кадр разбивается на блоки 8x8. Над каждым блоком производится ДКП (Дискретное Косинусное Преобразование), тем самым происходит трансформация яркостных данных из временной области в частотную. Затем полученная частотная матрица квантизируется, при этом про─ исходит оптимизация частот. Собственно, на данном этапе и проис─ ходит сжатие, за счёт отбрасывания излишней высокочастотной информации. Далее все члены матрицы вытягиваются в одну цепочку зигзагом и кодируются по RLC (Zero Run Length Coding). Финальный этап - кодирование по Хаффману, в результате которого из полного блока 8x8 остаётся лишь упакованная горстка битов. Процесс деко─ дирования выполняется в обратном кодированию порядке. Конечно, я описал лишь общую схему процесса сжатия, но думаю, пока этого вполне достаточно. Нам понадобится ещё несколько понятий. Цвета в жпеге хранятся не как RGB, а в формате YCbCr: Y - компонента яркости; Сb/Cr - цветоразностные компоненты, приблизительно показывают, сколько голубой и красной составляющей в цвете. Таким образом, если нас не интересуют цвета, можно извлечь только Y компоненту. Также по тексту будут фигурировать обозначения DC/AC. В полученном нами векторе из 64 элементов, необходимых для последующего преобразо─ вания по ДКП, первый элемент со смещением 0 называется DC - это, так сказать, нулевая частота,то есть фоновая яркость; все после─ дующие 63 элемента - AC. Это необходимо потому, что разные коэф─ фициенты кодируются по разному. 0-я частота, как правило, меняе─ тся слабо, поэтому кодируется не сам коэффициент, а разность ме─ жду этим и предыдущим DC коэффициентом. AC приходится кодировать как есть, там уже частоты меняются существенно, на протяжении всего кадра. Жпег представляет собой файл, поделенный на части - сегменты. Вот что из себя представляет сегмент: - заголовок (4 байта): $ff идентификатор сегмента n тип сегмента (1 байт) sh, sl размер сегмента, включая эти 2 байта, но не включая $FF и тип сегмента. Не в Intel'овском, а в Motorol'овском порядке: старший байт первый, младший последний! - содержимое сегмента, макс. 65533 байта. В начале сегмента стоит маркер - определённая метка: первый байт всегда FF, следующий - тип сегмента. Формат JPEG использует мотороловской формат для слов, то есть старший байт слова идёт первым, младший вторым. Приведу основные маркеры, которые нам понадобятся: D8 - SOI Start Of Image C0 - SOF0 Start Of frame (baseline) C2 - SOF2 Start Of frame (progressive) C4 - DHT Define Huffman table DB - DQT Define Quantization table DD - DRI Define Restart Interval DA - SOS Start Of Scan D9 - EOI End Of Image Немного подробнее опишу маркеры: D8,D9 = начало, конец файла; C0,C2 = определить основные параметры кадра (разрешение, цве─ тность, таблицы); C4 = таблицы Хаффмана (необходимы для декодирования битового потока); DB = таблицы квантизации (нужны для процесса деквантизации); DD = определить интервал перезапуска (редко используется в декодере); DA = начало сканирования (с этого маркера начинаются непосре─ дственно упакованные данные самого жпега). Дабы не захламлять ваши головы, уважаемые читатели, не буду сейчас углубляться в алгоритмы паковки жпега, сделаю это позже. Скажу лишь, что всё, что нам необходимо вначале сделать, - это просканировать файл от начала, от маркера SOI до маркера SOS, попутно инициализируя соответствующие переменные и таблицы. Мар─ кер SOS определяет начало пакованных данных жпега, а всё, что идёт после него, относится уже к процессу декодирования, это рассмотрим дальше. Процесс сканирования жпега начинается с чтения маркера SOI. Если в начале файла его нет, то это не жпег и можно смело пре─ кращать чтение.Сразу за маркером следуют 2 байта длины сегмента, исключение составляют SOI и EOI, у них сегмент отсутствует. Вот как выглядит основной цикл сканирования: ... 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; if (b<>$D8) and (b<>$D9) then begin BlockRead(PictureFile,v,2); FilePtr:=Swap(v)-2; Case b of $C0,$C2: ... { Main Image Parameters } $C4: ... { Read & compile Huffman Tables } $DA: ... { Start Of Scan } $DB: ... { Define Quantization Tables } $DD: ... { Define Restart Interval } End; while FilePtr<>0 do begin BlockRead(PictureFile,v,1); dec(FilePtr) end; if IOResult<>0 then begin WriteLn('I/O error !'); Close(PictureFile); Halt end end Until (b=$D9) or (b=$DA); ... BlockRead - читает из файла заданное количество байт Lo/Hi - выделяет младший/старший байт Swap - меняет старший и младший байт местами Все остальные маркеры и их сегменты, соответственно, пропус─ каются. Сканирование маркеров выполняется до тех пор, пока не встретится SOS. Это говорит о том, что все подготовительные опе─ рации выполнены и далее следует битовый поток данных самого жпега. Теперь рассмотрим подробнее обработку самих маркеров. Из─ лагать буду в такой последовательности: вначале полный формат соответствующего сегмента,далее фрагмент кода,затем комментарий. Пока описание буду давать краткое, более детально всё рассмотрим далее. Поэтому, если вдруг вам что-то будет неясно, советую пока пропустить это место и читать дальше. SOF0,SOF2: Начало кадра: ~~~~~~~~~~~~~~~~~~~~~~~~ - $ff, $c0 (SOF0) - длина (старший, младший байт), 8+кол.компонент*3 - точность данных (1 байт) в формате бит/элемент, обычно 8 - высота жпега (2 байта, Ст-Мл) - ширина жпега (2 байта, Ст-Мл) - кол.компонент (1 байт): обычно 1=чёрно-белое;3=цветное YCbCr - для каждого компонента: 3 байта - идентификатор компонента (1=Y, 2=Cb, 3=Cr) - сэмплинг фактор (бит 0-3 верт., 4-7 гор.) - номер таблицы квантизации ... $C0,$C2: begin vv :=ReadByte; { Main Image Parameters } Height:=ReadWord; Width :=ReadWord; planes:=ReadByte; if (vv<>8) or ((planes<>1) and (planes<>3)) then begin WriteLn('Only 8-bit Grayscale/RGB images supported'); Close(PictureFile); Halt end; For hh:=0 to planes-1 do begin CmpID[hh].C:=ReadByte; vv:=ReadByte; CmpID[hh].H:=Hi4(vv); CmpID[hh].V:=Lo4(vv); CmpID[hh].T:=ReadByte end; method:=b end; ... ReadByte/ReadWord - чтение байта/слова из файла Lo4/Hi4 - выделяет младшую/старшую часть байта Вначале следуют: разрядность данных (обычно 8 бит, остальные значения можно не обрабатывать); высота, ширина картинки в пик─ селах; количество компонент (определяет тип изображения: 1=чёр─ но-белое, 3=цветное). Далее для каждой компоненты следуют 3 бай─ та: тип компоненты (1=Y,2=Cb,3=Cr); сэмплинг фактор; номер таб─ лицы квантизации. Все эти параметры необходимо сохранить в соот─ ветствующих переменных и массивах, они нам понадобятся позже. DHT: Определить таблицу Хаффмана (ТХ): ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - $ff, $c4 (DHT) - длина (старший, младший байт) - информационный байт ТХ: бит 0..3: номер ТХ (0..3, иначе ошибка) бит 4 : тип ТХ, 0=DC таблица, 1=AC таблица бит 5..7: не используется=0 - 16 байтов: количество символов с кодами длиной 1..16, сумма этих байтов есть общее количество кодов, должно быть <= 256 - n байтов: таблица, содержащая символы в порядке увеличения длины кода (n = общее число кодов) Комментарий: - один DHT сегмент может содержать несколько таблиц, каждая со своим информационным байтом. ... $C4:begin Repeat { Read & compile Huffman Tables } hh:=ReadByte; For vv:=0 to 15 do HT.L[vv]:=ReadByte; aa:=0; For vv:=0 to 15 do For m:=1 to HT.L[vv] do begin HT.V[aa]:=ReadByte;inc(aa); end; c:=0;aa:=0; For vv:=0 to 15 do begin if HT.L[vv]>0 then begin HT.H2[Hi4(hh),Lo4(hh),vv].SV:=aa-c; HT.H2[Hi4(hh),Lo4(hh),vv].EV:=aa+HT.L[vv]; end; For m:=1 to HT.L[vv] do begin HT.H1[Hi4(hh),Lo4(hh),aa].V:=HT.V[aa]; if vv<8 then begin HT.H1[Hi4(hh),Lo4(hh),c].L:=vv+1; HT.H1[Hi4(hh),Lo4(hh),c].LV:=HT.V[aa]; end; inc(aa);inc(c) end; c:=c shl 1; end; Until FilePtr=0; end; ... Здесь несколько сложнее. Дело в том,что мало просто загрузить эти таблицы. Необходимо также преобразовать их в удобный для ра─ боты декодера формат. Поэтому остановимся на этом поподробней. Для начала немного теории. Хаффман относится к статистическому кодированию, то есть символам с большим числом вхождений в файл присваивается код с меньшей разрядностью, с меньшим числом - бо─ льшая разрядность. Таким образом образуется символьный алфавит с непропорциональными длинами присвоенных ему кодов. За счет этого достигается сжатие групп символов. В результате чего образуется выходной битовый поток данных. Для успешного декодирования бито─ вого потока необходимо иметь таблицы соответствия символов и их кодов соответствующей длины. Нас будут интересовать коды длин от 0 до 15, то есть 16 бит максимум. Вернёмся к нашему фрагменту кода. В начале стоит информацион─ ный байт, в нём: биты 0..3 - номер таблицы Хаффмана; бит 4 - тип таблицы 0=DC/1=AC. За ним следует 16 байт, которые описывают количество символов с длиной кодов от 1 до 16, сумма этих байтов есть общее количество кодов и не должна превышать 256. Потом идут символы в порядке увеличения длин кодов. Внимание!!! Идут символы, но не их коды. То есть коды нам ещё придётся им присво─ ить. Один DHT сегмент может иметь в себе несколько таблиц,каждую со своим информационным байтом. Всего таких таблиц может быть 8: 4 для DC и 4 для AC. Мы имеем таблицу символов и их длин. Теперь нам необходимо определить коды Хаффмана для каждого символа. Делается это по следующему алгоритму: вначале стартовый код c = 0; по порядку проходим все символы нашей таблицы от длины 1 до 16; на каждой итерации увеличиваем значение кода на единицу; при изменении длины кода умножаем код на 2, что равносильно сдвигу кода на один разряд влево. В результате имеем полную таб─ лицу всех символов и соответствующих им кодов Хаффмана. Что с ней делать дальше, станет понятно позже. Пока нам необходимо просто сохранить все эти данные. DQT: Определить таблицу квантизации (ТК): ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - $ff, $db (DQT) - длина (старший, младший байт) - информационный байт ТК: бит 0..3: номер ТК (0..3, иначе ошибка) бит 4..7: точность ТК, 0 = 8 бит, иначе 16 бит - n байт ТК, n = 64*(точность+1) Комментарий: - один DQT сегмент может содержать несколько таблиц, каждая со своим информационным байтом. - для точности 1 (16 бит) порядок следования - старший, потом младший (для каждого из 64 слов). ... $DB: begin Repeat { Define Quantization Tables } hh:=ReadByte; For vv:=0 to $3F do if Hi4(hh)=0 then qtmp[vv]:=ReadByte; for m:=0 to 63 do Quant[Lo(hh),m]:=qtmp[z2t[m]]; for v:=0 to 7 do for w:=0 to 7 do begin if w=0 then cw:=frac else cw:=round(frac*cos((w*PI)/16)*sqrt(2)); if v=0 then cv:=frac else cv:=round(frac*cos((v*PI)/16)*sqrt(2)); cw:=(cw*cv) shr prec; Quant[Lo(hh),v*8+w]:=mul1(Quant[Lo(hh),v*8+w],cw); end; Until FilePtr=0; end; ... Таблицы квантизации необходимы для восстановления частотной матрицы и имеют размерность 8x8, то есть всего таких коэффициен─ тов в одной матрице будет 64. На листинге: вначале считывается информационный байт, в нём биты 0..3 - номер таблицы квантизации от 0 до 3; биты 4..7 - разрядность элементов матрицы (0=8 бит, иначе 16 бит). Далее выполняется чтение и масштабирование элеме─ нтов. Один DQT сегмент может содержать несколько таблиц кванти─ зации, каждую со своим информационным байтом. Большинство жпегов рассчитаны на 8-битные таблицы. DRI: Определить интервал перезапуска: ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - $ff, $dd (DRI) - длина (старший, младший байт) = 4 - рестарт интервал (старший, младший байт) в единицах MCU блоков - это значит, что через каждые n MCU блоков может быть найден маркер RSTn. Первый маркер должет быть RST0, затем RST1, и так далее, до RST7, затем снова RST0. ... $DD: begin RestartInterval:=ReadWord end ... Всё, что необходимо сделать,- это сохранить его в переменной. Отмечу, что встречаются они крайне редко. SOS: Начало сканирования: ~~~~~~~~~~~~~~~~~~~~~~~~~ - $ff, $da (SOS) - длина (старший, младший байт), 6+2*(кол.компонент сканирования) - количество компонент сканирования (1 байт), должно быть >= 1 и <= 4 (иначе ошибка), обычно 1 либо 3 - для каждого компонента: 2 байта - идентификатор компонента (1=Y, 2=Cb, 3=Cr), смотреть SOF0 - используемая таблица Хаффмана: - бит 0..3: AC таблица (0..3) - бит 4..7: DC таблица (0..3) - 3 байта, должны быть пропущены (???) Комментарий: - Данные жпега следуют сразу за SOS сегментом. $DA: begin m:=ReadByte; { Start Of Scan } For hh:=0 to m-1 do begin Scan.Cmp[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; За ним следует количество сканируемых компонент - обычно 1 либо 3. Далее для каждой компоненты следуют 2 байта: 1-й - иден─ тификатор компоненты (1=Y, 2=Cb, 3=Cr), 2-й - Номер используемой таблицы Хаффмана, здесь биты 0..3 = AC таблица (0..3), 4..7 = DC таблица (0..3). Затем идут 3 байта которые необходимо пропус─ тить. Как было уже сказано раньше, этот маркер является послед─ ним, за ним непосредственно следуют сжатые данные жпега. Итак, все приготовления сделаны, теперь необходимо переходить непосредственно к самому процессу декодирования жпега.Для начала объясню, как расположены сжатые данные. Информация в жпеге хра─ нится блоками 8x8, то есть по 64 байта на каждую из компонент Y/Cb/Cr. Хотя это частный случай,когда сэмплинг фактор 1:1:1, но об этом позже. Сразу за Y компонентой следуют Cb и Cr, таким об─ разом, мы имеем всего 3*64 байта на блок 8x8 изображения. Блоки начинаются с левого верхнего угла изображения и идут слева направо и сверху вниз. То есть мы постепенно спускаемся вниз. В конце этого битстрима стоит маркер конца жпега EOI, который нам не обязательно отслеживать, ведь мы и так уже знаем сколько пик─ селей, а соответственно, и блоков в нашем жпеге. Все байтовые выравнивания маркеров осуществляются заполнением оставшихся би─ тов единицами, поэтому, если в потоке встречается байт FF, его необходимо пропускать. Общий список стадий декодирования выглядит следующим образом: 1) Хаффман декодер (декодирование DC/AC коэффициентов) 2) Деквантизация вектора из 64 элементов 3) Зиг-Заг сортировка и восстановление блока 8x8 4) Применение к блоку ОДКП Повторить первые 4 стадии для каждого блока 8x8, каждого ком─ понента изображения Y/Cb/Cr. 5) Масштабирование Cb/Cr 6) Преобразование уровня 7) Преобразование YCbCr->RGB Все эти стадии описывают лишь декодирование одного блока пик─ селей MCU. Для остальных необходимо повторить эти стадии,попутно считывая данные из файла и копируя их в соответствующее место на экране или в буфере. Рассмотрим подробно каждую стадию. 1. Хаффман декодер Все данные закодированы Хаффманом, этим достигается конечное сжатие жпега. Что представляет собой этот вид кодирования? Как я уже писал, каждому кодируемому символу сопоставляется код Хаффмана в зависимости от частоты появления символа в потоке. Чем меньше вероятность появления символа, тем большей длины код ему назначается, и наоборот. Тем самым происходит так называемое непропорциональное кодирование. За счёт этого производится опти─ мизация избыточности. В результате мы имеем битовый поток (бит─ стрим). Так как данные имеют битовую структуру, а текущий код имеет неизвестно какую длину, наш дисковый драйвер должен уметь читать данные последовательно бит за битом. Далее на каждой ите─ рации необходимо добавлять бит к уже имеющимся и проверять соот─ ветствие по таблицам Хаффмана.Если код найден,то раскодированное значение сохраняется, иначе продолжается декодирование. Встаёт вопрос, как можно быстро найти текущий код в таблице? Вначале приведу процедуру чтения битового потока: procedure NextBit(var V:byte); begin V:=(V shl 1)+Read1bit end; function Read1bit:byte; { Take one bit from Current 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 begin FillChar(DC,SizeOf(DC),0);ReadByte; end; if Current_byte=0 then Current_byte:=$FF; end end; Read1bit:=(Current_byte shr 7) and 1; Current_byte:=Current_byte shl 1; inc(Current_bit); if Current_bit=8 then Current_bit:=0 end; Как видно, процедура NextBit просто добавляет следующий бит к переменной V. Функция Read1bit возвращает следующий считаный бит из потока. Она также пропускает байт FF и инициализирует все DC коэффициенты, в случае, если встречается маркер RST0-RST7 (D0-D7). Теперь перейдем к сути, декодеру: function hd(T,C:byte):byte; { Decoding Huffman Code from bitstream } var v,code:byte; begin v:=0; { L - HuffCode len; L=0 - no code; L=len+1 (1..8) lookup } NextBit(v); if HT.H1[T,C,v].L=1 then begin hd:=HT.H1[T,C,v].LV;exit end; NextBit(v); if HT.H1[T,C,v].L=2 then begin hd:=HT.H1[T,C,v].LV;exit end; NextBit(v); if HT.H1[T,C,v].L=3 then begin hd:=HT.H1[T,C,v].LV;exit end; NextBit(v); if HT.H1[T,C,v].L=4 then begin hd:=HT.H1[T,C,v].LV;exit end; NextBit(v); if HT.H1[T,C,v].L=5 then begin hd:=HT.H1[T,C,v].LV;exit end; NextBit(v); if HT.H1[T,C,v].L=6 then begin hd:=HT.H1[T,C,v].LV;exit end; NextBit(v); if HT.H1[T,C,v].L=7 then begin hd:=HT.H1[T,C,v].LV;exit end; NextBit(v); if HT.H1[T,C,v].L=8 then begin hd:=HT.H1[T,C,v].LV;exit end; { SV - Start Value (aa-w); EV - Next Code Len Value } NextBit(v);code:=v+HT.H2[T,C, 8].SV; if code<HT.H2[T,C, 8].EV then begin hd:=HT.H1[T,C,code].V;exit end; NextBit(v);code:=v+HT.H2[T,C, 9].SV; if code<HT.H2[T,C, 9].EV then begin hd:=HT.H1[T,C,code].V;exit end; NextBit(v);code:=v+HT.H2[T,C,10].SV; if code<HT.H2[T,C,10].EV then begin hd:=HT.H1[T,C,code].V;exit end; NextBit(v);code:=v+HT.H2[T,C,11].SV; if code<HT.H2[T,C,11].EV then begin hd:=HT.H1[T,C,code].V;exit end; NextBit(v);code:=v+HT.H2[T,C,12].SV; if code<HT.H2[T,C,12].EV then begin hd:=HT.H1[T,C,code].V;exit end; NextBit(v);code:=v+HT.H2[T,C,13].SV; if code<HT.H2[T,C,13].EV then begin hd:=HT.H1[T,C,code].V;exit end; NextBit(v);code:=v+HT.H2[T,C,14].SV; if code<HT.H2[T,C,14].EV then begin hd:=HT.H1[T,C,code].V;exit end; NextBit(v);code:=v+HT.H2[T,C,15].SV; if code<HT.H2[T,C,15].EV then begin hd:=HT.H1[T,C,code].V;exit end; hd:=$ff; end; Хочу привести вам результаты своих экспериментов в данной области. Еще раз предупреждаю, что практически всё, о чем я буду говорить и говорил раньше, есть результат моих собственных домы─ слов, поэтому может отличаться от общепринятых методов и форму─ лировок. Как выяснилось, большая часть кодов не превышает 8 бит, таким образом, можно создать 256-байтную таблицу перекодировки. В этом случае декодирование происходит экстремально быстро: всё, что нам нужно - просто взять из таблицы уже готовое значение. В случае, если код >8 бит, тут немного сложнее. Нам нужно знать все начальные позиции SV и конечные позиции EV для длин кодов 8..16. То есть надо создать табличку значений, а вернее, три таблички. Первая будет содержать последовательно все наши закодирован─ ные символы, назовём её таблицей V. Расскажу, как сформировать две другие. Для каждой длины кода от 8..16 нужно задать началь─ ную позицию SV = смещению первого кода в таблице V минус сам первый код. Например, у нас есть код %110 = 6, идёт он под номе─ ром 5 в таблице, тогда SV = 5 - 6 = -1. Третья таблица должна содержать конечную позицию EV для текущей длины кода. Как и в предыдущем случае, для всех длин кодов от 8..16 нужно задать EV = смещению первого кода в таблице V плюс количество кодов этой длины. По предыдущему примеру, если количество кодов теку─ щей длины L = 4, то EV = 5 + 4 = 9. Всё это было приведено рань─ ше в куске кода обработки маркера DHT. Теперь объясню,для чего это всё нужно.В соответствии с нашими таблицами,как показано во фрагменте кода выше,поиск значения ко─ да выполняется следующим образом.Для соответствующей длины кода: складываем текущий код и SV, code = v + SV; если code < EV, то извлекаем из таблицы V декодированный символ, идёт он по смеще─ нию code, или, что равнозначно, hd = V[code]. Ред.: Поскольку биты из потока приходится читать в любом ме─ тоде декодирования Хаффмана, то проще (и,как ни странно,быстрее, если вести разговор о процессоре Z80) декодировать коды непосре─ дственно по дереву, бит за битом, не используя дополнительных таблиц. Соответствующие процедуры вы можете позаимствовать из распаковщика smallunr.H (см.в приложении). В ZXUnRar декодирова─ ние тоже идёт побитно, но для этого предварительно генерируется процедура разбора кодов Хаффмана на основе текущего дерева, поэ─ тому получается ещё более высокая скорость декодирования. Если вы думаете, что процесс декодирования коэффициентов на этом заканчивается, то вы ошибаетесь - он только начинается :). Пока мы имеем только раскодированные байты,из которых необходимо получить коэффициенты DC/AC. Плюс ко всему для увеличения эффек─ тивности сжатия было добавлено RLC сжатие последовательности нулей. Посмотрим, как раскодировать эти коэффициенты. Декодирование DC коэффициента производится по следующему ал─ горитму: В начале DC = 0 а) извлечение соответствующего кода Хаффмана (проверяем в таблице Хаффмана для DC) б) смотрим, к какой категории этот код принадлежит в) читаем N = биты категории, и определяем значение Diff = = (категория, N битов) г) DC = DC + Diff д) пишем DC в 64-элементный вектор: vector[0] = DC Декодирование AC коэффициентов производится по следующему алгоритму: Для каждого AC коэффициента, пока не встретился EOB и AC_counter <= 64 а) извлечение соответствующего кода Хаффмана (проверяем в таблице Хаффмана для AC) б) декодируем код Хаффмана в соответствии с (кол_пред_0, категория) в) читаем N=биты категории, и определяем значение AC = = (категория, N битов) г) пишем в 64х элементный вектор последовательность нулей = = кол_пред_0 д) увеличиваем AC_counter на кол_пред_0 е) пишем AC в 64-элементный вектор: vector[AC_counter] = AC Фрагмент кода для чтения коэффициентов DC/AC выглядит следую─ щим образом: hb:=HD(0,Scan.TD[b]); vec[0]:=DC[b]+Bits2Integer(Lo4(hb),ReadBits(Lo4(hb))); DC[b]:=vec[0];xx:=1; if method<>$C2 then Repeat hb:=HD(1,Scan.TA[b]); if hb=0 then Repeat vec[xx]:=0; inc(xx) Until xx>=64 else begin yy:=Hi4(hb); for m:=1 to yy do begin vec[xx]:=0; inc(xx) end; vec[xx]:=Bits2Integer(Lo4(hb),ReadBits(Lo4(hb))); inc(xx) end Until xx>=64; Объясню подробнее. Сначала определяем DC. Для этого нужно декодировать Diff. Кодируется он двумя элементами (кат, Nбит). В начале идут 4 бита (тетрада) категории, представляющие собой длину считываемого кода, которая и кодируется Хаффманом. То есть сначала декодируем её, а затем, уже зная длину кода Diff, читаем N бит. Далее идёт преобразование N битов в знаковое слово по следующим правилам: Значение Категория Биты 0 0 - -1,1 1 0,1 -3,-2,2,3 2 00,01,10,11 -7,-6,-5,-4,4,5,6,7 3 000,001,010,011,100,101,110,111 -15..-8,8..15 4 0000..0111,1000..1111 -31..-16,16..31 5 00000..01111,10000..11111 -63..-32,32..63 6 . -127..-64,64..127 7 . -255..-128,128..255 8 . -511..-256,256..511 9 . -1023..-512,512..1023 10 . -2047..-1024,1024..2047 11 . -4095..-2048,2048..4095 12 . -8191..-4096,4096..8191 13 . -16383..-8192,8192..16383 14 . -32767..-16384,16384..32767 15 . Преобразованием занимается следующий код: 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; В конце определяем значение DC как сумму предыдущего DC и найденного Diff. Итоговое значение сохраняется в векторе по ну─ левому смещению. Теперь о том, как определить коэффициенты AC. Здесь сложнее - их может быть несколько. Кроме того, дополнительно используется кодирование последовательности нулей (RLC). Для каждого элемента от 2 до 64 необходимо декодировать байт, содержащий в тетрадах данные (кол_пред_0, категория), где кол_пред_0 = количество предшествующих нулей. Далее от текущей позиции необходимо запол─ нить вектор нулями в количестве кол_пред_0. При этом, если байт равен (0,0), то это признак конца блока EOB, в этом случае оставшиеся элементы вектора заполняются нулями, и на этом запол─ нение вектора заканчивается. Если этого не произошло,выполняется чтение группы из Nбит бит и преобразование значения AC коэффици─ ента, как и в предыдущем случае. Декодирование DC/AC коэффициентов необходимо выполнять по со─ ответствующим таблицам Хаффмана. Ещё один момент. Существует два формата следования данных в жпеге. Первый называется baseline (маркер С0), о нём я и писал, в нём все 64 коэффициента вектора идут подряд. Жпеги этого типа открываются за один проход сверху вниз. Существует ещё один формат - progressive (маркер C2). В нём за один кадр считывается только один коэффициент, сначала DC, далее последовательно все AC. Таким образом один общий скан разбивается на несколько последовательно идущих сканов. Количес─ тво коэффициентов зависит от качества сжатия жпега. Для открытия жпега этого типа необходим кадровый буфер для хранения коэффици─ ентов DC/AC. Преимуществом данного типа является возможность увидеть кадр изображения, не дожидаясь конца файла. Чтение сле─ дующей порции коэффициентов будет лишь улучшать качество картин─ ки, кадр будет как бы фокусироваться. Ввиду сложности реализации прогрессивной развертки, я не стал поддерживать её полностью, сделав лишь чтение первого скана, содержащего DC коэффициенты. 2. Деквантизация вектора из 64х элементов На этой стадии выполняется восстановление оптимизированных коэффициентов вектора. Выполняется это следующим образом. На этапе подготовки было выполнено чтение всех необходимых нам таб─ лиц квантизации. Всё, что нам теперь нужно,- просто умножить все элементы нашего вектора на соответствующие элементы таблицы ква─ нтизации. Можно объединить эту стадию со стадией ОДКП (обратное ДКП), как поступил я сам. 3. Зиг-Заг сортировка и восстановление блока 8x8 На этапе сжатия, при переводе блока 8x8 в вектор,коэффициенты обходились зигзагом. Это было необходимо для лучшей группировки последовательности нулей. Теперь нам необходимо сделать обратную операцию - восстановить блок 8x8 из вектора. Приведу порядок следования коэффициентов в матрице: 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 То есть элементы вектора необходимо записывать в ячейки мат─ рицы, в соответствии с их порядковыми номерами. В результате мы имеем полностью восстановленную матрицу для последующей,пожалуй, самой важной из всех, стадии. 4. Применение к блоку ОДКП Это самая интересная часть декодирования. ОДКП (Обратное Дис─ кретное Косинусное Преобразование) относится к семейству преоб─ разований Фурье и выполняет преобразование данных из частотной области во временную. То есть на входе мы имеем матрицу частот, после применения ОДКП будет матрица дискретных значений, или яркости, пикселей. Главная трудность этой стадии состоит в том, что на самом деле преобразования Фурье выполняются слишком мед─ ленно. Не стану здесь расписывать всякие классические математи─ ческие формулы и выкладки, на эту тему можно написать целую книгу, приведу лишь самое, на мой взгляд, оптимальное решение. Существует семейство быстрых алгоритмов преобразования Фурье - ОБПФ (Обратное Быстрое Преобразование Фурье). Из множества дан─ ных методов я выбрал схему AA&N, как самую быструю. Единственный минус данного метода - небольшая потеря точности, хотя на глаз я её не заметил. Приведу фрагмент кода, считающий матрицу 1x8: ... { Even part } t0:=tout[i*8+0];t1:=tout[i*8+2]; t2:=tout[i*8+4];t3:=tout[i*8+6]; t10:=t0+t2;t11:=t0-t2;t13:=t1+t3; t12:=(t1-t3)*(2*c4)-t13; t0:=t10+t13;t3:=t10-t13; t1:=t11+t12;t2:=t11-t12; { Odd part } t4:=tout[i*8+1];t5:=tout[i*8+3]; t6:=tout[i*8+5];t7:=tout[i*8+7]; z13:=t6+t5;z10:=t6-t5; z11:=t4+t7;z12:=t4-t7; t7:=z11+z13; t11:=(z11-z13)*(2*c4); z5:=(z10+z12)*(2*c2); t10:=(2*(c2-c6))*z12-z5; t12:=(-2*(c2+c6))*z10+z5; t6:=t12-t7;t5:=t11-t6;t4:=t10+t5; tout[i*8+0]:=t0+t7;tout[i*8+7]:=t0-t7; tout[i*8+1]:=t1+t6;tout[i*8+6]:=t1-t6; tout[i*8+2]:=t2+t5;tout[i*8+5]:=t2-t5; tout[i*8+4]:=t3+t4;tout[i*8+3]:=t3-t4; ... Здесь: tout[] - рабочая матрица 1x8 i - номер текущей строки матрицы Константы: c2 = cos(2*PI/16); c4 = cos(4*PI/16); c6 = cos(6*PI/16); Данным кодом необходимо пройтись вначале по всем строкам на─ шей 8x8 матрицы, а затем по всем столбцам. Получается 16 итера─ ций: 8 на строки + 8 на столбцы. При обработке столбцов перед финальной записью результата следует разделить его на 8, этого требует специфика метода. Есть ещё одна тонкость, без которой алгоритм не будет работать. Перед обработкой начальную матрицу необходимо умножить на константу. Вот как это будет выглядеть: ... for j:=0 to 7 do for i:=0 to 7 do begin if i=0 then ci:=1 else ci:=cos((i*PI)/16)*sqrt(2); if j=0 then cj:=1 else cj:=cos((j*PI)/16)*sqrt(2); tout[j*8+i]:=tin[j*8+i]*ci*cj; end; ... Как видно, если номер элемента не нулевой,нужно умножить этот элемент на cos((i*PI)/16)*sqrt(2), иначе на единицу, то же самое и по j. Эти ухищрения делаются для уменьшения количества умноже─ ний в цикле обработки. Если предварительно перемножить данные константы с таблицами квантизации и объединить стадии 2 и 4, то есть включить в ОБПФ деквантизацию,можно выиграть немного скоро─ сти. Это и было проделано раньше при обработке маркера DQT, смо─ треть фрагмент кода. ──────────────────────────────────────────────────────────────── Все описанные выше этапы позволяют получить коэффициенты то─ лько одной компоненты (Y/Cb/Cr). Поэтому четыре первые стадии необходимо повторить для каждой компоненты, если, конечно, жпег полноцветный. Далее следует описание стадий уже после декодиро─ вания всех 3 компонент. ──────────────────────────────────────────────────────────────── 5. Масштабирование Cb/Cr В результате предыдущих стадий была получена информация о 3 компонентах Y/Cb/Cr. То есть 3 блока 8x8, описывающие пиксели изображения. На самом деле это является частным случаем, когда масштаб (сэмплинг фактор) компонент Y/Cb/Cr=1:1:1, но так бывает не всегда. Часто масштаб компонент принимается 2:1:1, что озна─ чает, что на 2 элемента яркости Y приходится по 1 элементу цвет─ ности Cb/Cr. Тоже самое происходит и по другой координате, то есть и по X, и по Y. Эти данные загружались раньше,при обработке маркера SOS. Существует понятие минимального кодированного блока - MCU (Minimum Coded Unit), которое описывает блок изображения. При сэмплинг факторе 1:1:1 MCU равен 8x8. При 2:1:1 MCU равен 16x16. Во втором случае получается, что данных Y компоненты в 4 раза больше, чем для Cb/Cr. Если представить блок 8x8 как DU (DataUnit), то последний случай запишется в виде: YDU, YDU, YDU, YDU, CbDU, CrDU. На 4 блока данных для яркости Y приходится по одному блоку цветности Cb/Cr. Такое допущение позволяет получить ещё большее сжатие при практически незаметном ухудшении качества картинки. С учётом сказанного для каждой компоненты необходимо также учитывать масштаб и выполнять полностью загрузку MCU. Блоки данных из 64 элементов распологаются в MCU слева направо, сверху вниз. После того, как будет загружена полностью информа─ ция о всех компонентах, необходимо выполнить ресэмплинг, то есть отмасштабировать,если необходимо, компоненты Cb/Cr. При сэмплинг факторе 2:1:1 в результате получим 3 матрицы элементов 16x16. В случае 1:1:1 все компоненты идут один к одному,и масштабирование выполнять не нужно, MCU будет равен 8x8. В принципе, бывают и другие вариации, например, Cb/Cr по X может быть на 2 юнита (1:1:1), а по Y на 1 (2:1:1). Но такие случаи бывают крайне редко, я не стал морочить ими голову и поддержал только два пер─ вых. 6. Преобразование уровня Необходимо преобразовать значения наших компонент из знаковой в беззнаковую форму. Сделать это очень просто - всё, что нужно,- это прибавить 128 ко всем 8-битным знаковым значениям наших ком─ понент. На данном этапе также выполняются регулировки яркостного и цветового баланса. Если в таблицах яркости и цветности учесть сразу и значение уровня, то данное преобразование будет выполня─ ться автоматически. 7. Преобразование YCbCr->RGB Это преобразование является заключительным этапом декодирова─ ния и осуществляет преобразование из цветового пространства YCbCr в формат экранных пикселей RGB. Делается это по стандарт─ ным формулам: R = Y + 1.402 *(Cr-128) G = Y - 0.34414*(Cb-128) - 0.71414*(Cr-128) B = Y + 1.772 *(Cb-128) Все значения YCbCr - 8 битные беззнаковые. В результате имеем декодированные пиксели изображения в формате true color (по 8 бит на компоненту). ──────────────────────────────────────────────────────────────── Вот,собственно,и всё,о чём я хотел вам рассказать.Изначально, правда, задумывалось написать статью в формате спековского асма, но, учитывая неподъёмность исходников, пришлось отказаться от этой затеи и расписать на примере пасовских фрагментов. Можно было бы ещё написать про масштабирование полученного изображе─ ния, про его обработку выходными фильтрами, но это тема отдель─ ной статьи. Да и без этого, думаю, информации для размышления подкинул достаточно. Так что, господа кодеры, изучайте, думайте и пишите качественные декодеры жпега для нашего любимого спекки. Ред.: В приложении лежит просмотрщик xjpeg by scor^3umf и исходники этого просмотрщика (публикация исходников не означает, что автор забросил этот проект - перед внесением каких-либо изменений свяжитесь с автором по адресу scorpzx@mail.ru ).
Другие статьи номера:
Похожие статьи:
В этот день... 21 ноября