Navigace:  » Úvodní stránka  » Rubriky  » C/C++  

6. února 2003, 00.00 | V tomto článku se vrátíme k problematice JPEG komprese a na malém prográmku si ukážeme praktickou funkčnost JPEGu, jeho výhody a nevýhody. Součástí je samozřejmě detailní popis algoritmu, matematické vyjádření a plně funkční ukázkový kod.

V předchozím článku jsme si rozebrali JPEG standard z teoretického hlediska. Jelikož je jméno tohoto serveru builder, tak před tím než se vypravíme do tajů dalších typů grafické komprese, ukážeme si dnes něco víc z praxe a "nabuildujeme" si malý prográmek jenž nám pomůže lépe pochopit výhody nevýhody JPEG komprese.  

Kód jsem napsal v Pascalu a měl by být zkompilovatelný pod Delphi5. Základem prográmku je nasledující záznam a z něho pak odvozeno třírozměrné pole:

type TClr=record
  red,green,blue:byte;
  hue,saturation,brightness:double;
  DCTH, DCTS, DCTB:double;
  TCDH, TCDS, TCDB:double;
  newred,newgreen,newblue:byte;
end;

var
ClrArray:array[1..1000,1..8,1..8] of TClr;

Smysl proměnných je asi zřejmý : red, green, blue  a newred, newgreen a newblue jsou hodnoty kanálů RGB původního a nového obrázku. Hue,saturation, brigthness a TCDH, TCDS, TCDB jsou hodnoty HSB původního a nového obrázku, ale zřejmě se naskýstá otázka, proč jsou typu double jenž v Delphi zabíra 64 bitů, když se jedná o stupnice s velmi malým rozsahem. Odpověd je jednoduchá, jestli chceme dělat přesnou kompresi je dobré se při výpočtech v co největší míře vyhnout předčasnému zaokrouhlování a zaokrouhlit vše až nakonec.

Další otazník by mohl být nad rozměry pole ClrArray. [1..8,1..8] jsou rozměry matice s níž se v JPEG pracuje a první rozměr 1..1000 slouží jen jako jakýsi index k definici s kterým čtveřečkem [1..8,1..8] zrovna pracujeme.

V samotném kódu se setkáváme více méně jen se dvěma problematickými okamžiky, a to je převod HSB->RGB a zpět a převod HSB na koeficienty DCT a zpět. Převod RGB na HSB je poměrně jednoduchý a je více zpusobů jak jej provést. Tady je jeden z nich:

procedure RGBtoHSB; ...       MaxColor := Max(red,Max(green,blue));       MinColor := Min(red,Min(green,blue));       Difference := MaxColor-MinColor;       brightness := (MaxColor+MinColor)*100 / (510);         // 510 je 2*255 jako maximalni mozny hodnoty RGB       if MaxColor = MinColor then begin        saturation := 0;        hue := 0;       end      else begin      if brightness < 50 then saturation := (MaxColor-MinColor)*100/(MaxColor+MinColor)                        else saturation := (MaxColor-MinColor)*100/(510-MaxColor-MinColor);     if red = MaxColor  then hue := 60*(green-blue)/Difference       else if green = MaxColor  then hue := 120+60*(blue-red)/Difference          else hue := 240+60*(red-green)/Difference;     If Hue < 0 then hue := hue + 360;//hodnoty pod 0 jsou ekvivaletni hodnotam pod 360

Převod HSB zpátky do RGB je již poněkud zložitější a je vázán na způsob, kterým jsme hodnoty HSB získali.

procedure HSBtoRGB; ...   if TCDH <=60 then begin     newRed1 := 255;     newGreen1 := (255/60)*TCDH;     newBlue1 := 0;   end   else if TCDH <=120 then begin     newRed1 := 255-(255/60)*(TCDH-60);     newGreen1 := 255;     newBlue1 := 0;    end ... //podobne pro vsechny vysece kruhu   Sat := Abs((TCDS-100)/100);   newRed1 := newRed1-((newRed1-128)*Sat);   newGreen1 := newGreen1-((newGreen1-128)*Sat);   newBlue1 := newBlue1-((newBlue1-128)*Sat);   Lum := (TCDB-50)/50;   if Lum > 0 then begin     newRed1 := newRed1+((255-newRed1)*Lum);     newGreen1 := newGreen1+((255-newGreen1)*Lum);     newBlue1 := newBlue1+((255-newBlue1)*Lum);   end   else if Lum < 0 then begin     newRed1 := newRed1+(newRed1*Lum);     newGreen1 := newGreen1+(newGreen1*Lum);     newBlue1 := newBlue1+(newBlue1*Lum);   end;   //Nakonec musime udelat jednu drobnustku protoze newRed je typu byte a   //pripadny vysledek 255.6 by se pretransformoval na 0   if newRed1>=255 then newRed:=255       else newRed:=round(newRed1); ...

Tak a teď vzhůru do Diskrétní kosinové transformace. Vzoreček jenž jsem uvedl v předchozím díle pochází ze stránek http://www.faqs.org/, ale není tak docela přesný. Úplně správná verze je zde. A jak to vypadá v kódu: (Uvádím zápis jenom pro složku hue ostatní složky jsou identické)

procedure CalculateDCT(which:integer);//which je globálni promenna - matice se kterou se pracuje var i,j,ii,jj:byte;        dctH1,dctS1,dctB1:double; begin   for i:=0 to 7 do     for j:=0 to 7 do begin         dctH1:=0;dctS1:=0;dctB1:=0;             if (i=0)and(j=0) then begin //pripad bunky [0,0]            for ii:=0 to 7 do              for jj:=0 to 7 do begin                dctH1:=dctH1+0.25*1/sqrt(2)*1/sqrt(2)*ClrArray[which,ii+1,jj+1].hue;             end;           dctH1:=dctH1*1/sqrt(2);           ClrArray[which,i+1,j+1].DCTH:=dctH1;       end     else     if (j=0) or (i=0) then begin //prni radek nebo prvni sloupec oba maji specialni koefic.        for ii:=0 to 7 do           for jj:=0 to 7 do begin            dctH1:=dctH1+0.17667*ClrArray[which,ii+1,jj+1].hue*                          cos(i*(2*ii+1)*pi/16)*cos(j*(2*jj+1)*pi/16);          end;     ClrArray[which,i+1,j+1].DCTH:=dctH1;     end    else    begin // vsechny ostatni pripady      for ii:=0 to 7 do         for jj:=0 to 7 do begin           dctH1:=dctH1+0.25*ClrArray[which,ii+1,jj+1].hue*                         cos(i*(2*ii+1)*pi/16)*cos(j*(2*jj+1)*pi/16);            end;     ClrArray[which,i+1,j+1].DCTH:=dctH1;    end; end; end;

Po tomhto kroku máme k dispozici frekvenční matici koeficientů DCT s níž si můžeme dělat co se nám zlíbí. Totiž koeficienty můžeme zaokrouhlovat nebo také rovnou mazat a stejně se nám obrázek podaří znovu získat zpět.

Podívejme se tedy jak vypočítat s frekvenčních koeficientů zpátky hodnoty HSB.V podstatě se jedná o obrácený proces výpočtu DCT jenž se matematicky zapisuje takto. A v kódu pak vypadá následně:

{Rozdeleni do podcyklu a ruzne koeficienty jsou ze stejneho duvodu jako v pripade vypoctu DCT} procedure CalculateTCD(which:integer); var i,j,ii,jj:byte;        tcdH,tcdS,tcdB:double; begin   for i:=0 to 7 do     for j:=0 to 7 do begin       tcdH:=0;tcdS:=0;tcdB:=0;   for ii:=0 to 7 do     for jj:=0 to 7 do begin          if (ii=0) or (jj=0) then begin           tcdH:=tcdH+0.25*1/sqrt(2)*ClrArray[which,ii+1,jj+1].DCTH*cos(ii*(2*i+1)*pi/16)                     *cos(jj*(2*j+1)*pi/16);            end          else        if (ii=0) and (jj=0) then begin           tcdH:=tcdH+0.25*1/sqrt(2)*1/sqrt(2)*ClrArray[which,ii+1,jj+1].DCTH                     *cos(ii*(2*i+1)*pi/16)*cos(jj*(2*j+1)*pi/16);         end       else        begin          tcdH:=tcdH+0.25*ClrArray[which,ii+1,jj+1].DCTH*cos(ii*(2*i+1)*pi/16)                    *cos(jj*(2*j+1)*pi/16);        end;     end;     ClrArray[which,i+1,j+1].TCDH:=tcdH;   end; end;

Tak získané hodnoty HSB převedeme zpátky na kanály RGB a můžeme si obrázek zobrazit.

Kde je tedy komprese?

Komprese vzniká právě při již zmiňovaném mazání a zaokrouhlování koeficientů. Jestli si zkompilujete přiložený kód, najdete v něm obrázek, při přepočtu kterého jsou odstraněny z frekvenční matice všechny koeficienty [3..8,3..8]  resp. jsou nahrazeny nulou. Ukázka zde. Další finta taky je, že i když koeficienty vypočítáváme jako double můžeme je zaokrouhlit a kvalita (mám na mysli lidským okem postřehnutelnou kvalitu) tím neutrpí. Poté je možné koeficienty přenášet jako čísla typu byte. Nebo taky je převést do 7 bitového formátu což si možná příště taky ukážeme. (toto ovšem neplatí pro koeficient [0,0] jehož hodnota je povětšinou větší než 255) Ostatní koeficienty hlavně při zjednodušení škál HSB, viz předchozí díl, by se měly vejít do 7 bitů.

Pár slov na závěr.

Kód jenž jsem tady vytvořil není dokonalý a také to není žádný krasopis. To ostatné ani nebylo účelem, snažil jsem se ho spíš napsat tak aby se z něj dalo vyčíst jak dané výpočty zapsat a jak fungují. Použil jsem Pascal ale jestli to bude čtenářům více vyhovovat mohu v příštích dílech pokračovat v C++.

zdrojové kody [183 kB]