Vesztes‚ges k¢dol s introkban Flag'98 Coder-l el“ad s rod/mandula [s5001pap@hszk.bme.hu] Bevezet‚s Ebben a le¡r sban a k‚pek vesztes‚ges t”m”r¡t‚s‚r“l olvashatsz. Csak olyan k‚pekkel foglalkozunk, ahol a pixelek sz¡nkomponensenk‚nt vannak t rolva, nem pedig palett b¢l indexelve. A t rgyalt algoritmus a JPEG ‚s MPEG k¢dol s nak is alapja. A sz¡nm‚lys‚g lehet b rmilyen, ez nem befoly solja az algoritmust, de kisebb m‚lys‚ggel jobb t”m”r¡t‚s ‚rhet“ el, mert a komponensegytthat¢k jobban kvant lhat¢ak. Pl. egy 24 bites k‚p eset‚n a pixelek komponensei 8 bitet foglalnak el, m¡g egy 15 bites k‚pn‚l csak 5-”t. Term‚szetesen az elj r s haszn lhat¢ grayscale k‚pek k¢dol s ra is. Ilyenkor csak egy komponenst k¢dolunk a szok sos h romhoz k‚pest. Amikr“l sz¢ lesz: - k¢dol sok csoportos¡t sa - sz¡nmodell v laszt s - transzform ci¢s k¢dol s (DCT) - kvant l s - a k¢dol s befejez“ l‚p‚sei - sz m¡t si komplexit s - k¢dol si hib k - introk vesztes‚ges k¢dol ssal # K¢dol sok csoportos¡t sa - vesztes‚ges, vesztes‚gmentes Vesztes‚gmentes t”m”r¡t‚ssel kb. 1.5-2-szeres t”m”r¡t‚s ‚rhet“ el, ez az ar ny vesztes‚gessel sokkal nagyobb, h tr nya, hogy a k¢dol s ut n kit”m”r¡tett k‚p nem lesz azonos az eredetileg k¢dolttal. - pixelalap£, blokkalap£ A pixelalap£ k¢dol s egy temben egy pixelt k¢dol, m¡g a blokkalap£ egy tipikusan 8x8-as blokkot, amivel nagyobb nyeres‚get kapunk. A k”vetkez“kben a vesztes‚ges, blokkalap£ k¢dol st t rgyaljuk meg. Sz¡nmodell v laszt s A k‚pek k¢dol s ban jelent“s szerepet j tszik, hogy milyen modellt v lasztunk a k‚p le¡r s ra. A l that¢ sz¡nek nagy r‚sze el“ ll¡that¢ az r,g,b komponensek addit¡v kever‚s‚vel, de ez nem hat‚kony, mert a komponensek  tvitel‚hez nagyj b¢l ugyanakkora s vsz‚less‚g szks‚ges, azaz a komponensek t rol s ra k”zel ugyanannyi bitet kell haszn lnunk. Egy kicsit megdobhatja a t”m”r¡t‚st, hogy a z”ld komponens a legfontosabb, valamint az, hogy a szemnk a k‚k sz¡nre a legkev‚sb‚ ‚rz‚keny. De enn‚l van sokkal jobb megold s is. K‚pnket vil goss g ‚s sz¡nkl”nbs‚gi jelek alapj n fogjuk t rolni az YUV rendszerben. RGB modellb“l konvert l s a k”vetkez“ k‚pletek alapj n t”rt‚nhet: y=0.3r+0.59g+0.11b a sz¡njel vil goss ga, f‚nys–r–s‚g u=(b-y)/2.03 k‚k sz¡nkl”nbs‚gi jel v=(r-y)/1.14 v”r”s sz¡nkl”nbs‚gi jel vagy m trixos form ban: |y| | 0.299 0.587 0.114 | |r| |u| = | -0.147 -0.289 0.437 | |g| |v| | 0.615 -0.515 -0.100 | |b| |r| | 1 0 1.140 | |y| |g| = | 1 -0.394 -0.581 | |u| |b| | 1 2.028 0 | |v| Az YUV modellben az u,v komponenseknek nincs f‚nyess‚gtartalmuk, csak az adott jel sz¡n‚r“l hordoznak inform ci¢t. El“nye a felbont snak, hogy az emberi szem sz m ra az u,v felbont¢k‚pess‚g 4-5-sz”r kisebb, mint az y-‚. Ezt kihaszn lva az RGB k‚pnket YUV modellbe konvert lva, t”m”r¡tve, az u,v mint kat sokkal jobban kvant lva nagyobb t”m”r¡t‚st ‚rhetnk el, mint RGB k‚p eset‚n. Kit”m”r¡t‚skor pedig a kapott y,u,v ‚rt‚keket visszasz moljuk r,g,b-re. Transzform ci¢s k¢dol s (DCT) A traszform ci¢s k¢dol s alapelve, hogy a k‚pet NxN-es blokkokra osztjuk ‚s a frekvencias¡kra transzform ljuk, aminek eredm‚nye NxN egytthat¢ lesz. Ez az‚rt kedvez“ sz munkra, mert az eredeti k‚p minden pixele azonosan fontos volt, a transzform ltn l viszont az energiatartalom csak bizonyos egytthat¢kba t”m”rl, a t”bbi amplit£d¢ja kicsi. Tipikusan az NxN-es blokk transzform ci¢jakor kapott ‚rt‚kek els“ elemei nagyobb inform ci¢t hordoznak mint a nagyobb index–ek, ez‚rt a kvant l skor ennek megfelel“ bitsz mot  llap¡tunk meg nekik. A h ts¢ egytthat¢k nagy r‚sze el is hagyhat¢. A t”m”r¡t‚s m‚rt‚k‚t az hat rozza meg, hogy az egytthat¢kat milyen potoss ggal  br zoljuk, azaz h ny bitre kvant ljuk. Ki kell v lasztanunk egy transzform ci¢t, amivel mindezt v‚gezzk. Erre legelterjedtebb a Diszkr‚t Cosinus Transzform ci¢ (DCT). El“nyei k”z‚ tartozik, hogy az egytthat¢k val¢sak ‚s a sz m¡t sig‚ny megfelel“. T”bbek k”z”tt ezt haszn lja a JPEG ‚s az MPEG is. Az 1 dimenzi¢s DCT ‚s inverz DCT k‚pleteit a dct.gif file-ban tal lod. A DCT eredm‚nyek‚nt kapott egytthat¢kat 2 csoportra osztjuk, az X(0)-t DC komponensnek h¡vjuk ‚s a vektor  tlag‚rt‚k‚vel ar nyos ”sszetev“. A t”bbi elem (X(k), k>0) pedig AC komponens. Az ”sszes komponens val¢s. Mivel mi egy blokkot akarunk k¢dolni, ami 2 dimenzi¢s, szks‚gnk lesz egy 2-d DCT-re ‚s inverz‚re is. Az adott k‚pletekkel anal¢g m¢don ez k”nnyen kihozhat¢. Az‚rt nem ¡rom le, mert felesleges. Ugyanis a DCT szepar lhat¢, azaz a 2-dimenzi¢s fel¡rhat¢ 2 darab 1-d transzform ci¢ ”sszegek‚nt £gy, hogy elv‚gezzk minden sorra ‚s oszlopra az 1-d DCT-t. p‚ldak‚nt itt egy k¢dr‚szlet IDCT-re: void idct2D (double coeffs[8*8], double samples[8*8]) { int i; double *sp,*cp; static double tmp[8*8]; for (sp = tmp, cp = coeffs, i = 0; i < 8; i++, sp += 8, cp += 8) idct1D (cp, 1, sp, 1); for (sp = samples, cp = tmp, i = 0; i < 8; i++, sp += 1, cp += 1) idct1D (cp, 8, sp, 8); } void idct1D (double coeffs[], int coeffOffset, double x[], int xOffset) { double *cp, *xp; double dc = 0.70710678*coeffs[0]; int i; static double C[32] = { /* cos(k*pi/16), (0 <= k <= 31) */ +1.00000000, +0.98078528, +0.92387953, +0.83146961, +0.70710678, +0.55557023, +0.38268343, +0.19509032, +0.00000000, -0.19509032, -0.38268343, -0.55557023, -0.70710678, -0.83146961, -0.92387953, -0.98078528, -1.00000000, -0.98078528, -0.92387953, -0.83146961, -0.70710678, -0.55557023, -0.38268343, -0.19509032, -0.00000000, +0.19509032, +0.38268343, +0.55557023, +0.70710678, +0.83146961, +0.92387953, +0.98078528, }; for (i = 8, xp = x; --i >= 0; xp += xOffset) *xp = dc; for (i = 1, xp = x; i <= 15; i += 2, xp += xOffset) { double sum = 0.0; int u,j; for (j = i, u = 7, cp = coeffs + coeffOffset; --u >= 0; j += i, cp += coeffOffset) sum += C[j & 0x1F] * *cp; *xp += sum; } for (i = 8, xp = x; --i >= 0; xp += xOffset) *xp *= 0.5; } Kvant l s A transzform ci¢ elv‚gz‚se ut n kaptunk egy rak s val¢s sz mot, amit valahogy v‚ges bit‚rt‚ken t rolni k‚ne. A bitsz mok kioszt s t, azaz, hogy melyik egytthat¢t h ny biten t roljuk optimaliz lni kellene. Ez k‚t szempont alapj n lehets‚ges. Vagy a rekonstru lt blokk torz¡t s t akarjuk minimaliz lni, vagy pedig az emberi szem sz m ra megfelel“ k‚pet akarunk l‚trehozni. Sz munkra a m sodik sokkal hasznosabb, mert neknk az sz m¡t, hogy min‚l jobban n‚zzen ki a t rolt k‚p, nem pedig, hogy mennyire hasonl¡t az eredetire. Ezt h¡vj k a kvant l si m trix HVS (Human Visual System) alapj n t”rt‚n“ tervez‚s‚nek. Ez alapj n a nagyobb index– egytthat¢kat nagyobb l‚pcs“vel kvant ljuk. Itt felhaszn lhatjuk a YUV modellben tett kijelent‚snket, hogy az y komponens sokkal hangs£lyosabb. Bemutatjuk a JPEG alap kvant l si t bl it: JPEG default kvant l si t bla y komponensre { 16.0, 11.0, 10.0, 16.0, 24.0, 40.0, 51.0, 61.0, 12.0, 12.0, 14.0, 19.0, 26.0, 58.0, 60.0, 55.0, 14.0, 13.0, 16.0, 24.0, 40.0, 57.0, 69.0, 56.0, 14.0, 17.0, 22.0, 29.0, 51.0, 87.0, 80.0, 62.0, 18.0, 22.0, 37.0, 56.0, 68.0, 109.0, 103.0, 77.0, 24.0, 35.0, 55.0, 64.0, 81.0, 104.0, 113.0, 92.0, 49.0, 64.0, 78.0, 87.0, 103.0, 121.0, 120.0, 101.0, 72.0, 92.0, 95.0, 98.0, 112.0, 100.0, 103.0, 99.0 } JPEG default kvant l si t bla u,v komponensre { 17, 18, 24, 47, 99, 99, 99, 99, 18, 21, 26, 66, 99, 99, 99, 99, 24, 26, 56, 99, 99, 99, 99, 99, 47, 66, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99, 99 } A k¢dol s befejez“ l‚p‚sei A k¢dol st k‚t kl”n £ton fogjuk v‚gezni, AC,DC komponensekre szepar lva. Kezdjk az AC komponensekkel. A k¢dolt blokkban az ‚rt‚kesebb egytthat¢k a bal fels“ sarokban fognak csoportosulni, ami a kvant l si m trixok vizsg latakor is ‚szrevehet“. Emiatt a k¢dolt blokkon a bal fels“ sarokb¢l indulva cikk-cakkban fogunk elindulni ‚s ¡gy t roljuk az elemeket, amelyekb“l p rokat k‚peznk a k”vetkez“ m¢dszer szerint: k”zvetlenl az elem el“tt l‚v“ null k sz ma ‚s az ‚rt‚kes (nem 0) egytthat¢k alkotnak egy p rt. Ez van lerajzolva a cikkcakk.gif k‚pen. Ezek a run-level p rok nagyj b¢l a frekvencia szerint alakulnak ki a cikk-cakk rendez‚s miatt, ez‚rt t”bb 0 kerl egym s mell‚, j¢val kevesebb p rt kapunk. Bizonyos p rok gyakrabban, bizonyosak ritk bban fordulnak el“, ezekhez rendelhetnk v ltoz¢ hossz£s g£ k¢dszavakat, pl. Huffman-k¢dot. A DC egytthat¢k kl”nbs‚geit k¢doljuk, azaz a DC(i+1)-DC(i) sz mhoz rendelnk egy Huffman-k¢dsz¢t. A Huffman k¢dol s  ltal ban nem optim lis Huffman, hanem egy meghat rozott t bl val k¢dolnak mindent. A JPEG-ben 2 DC ‚s 2 AC t bla k”zl lehet v lasztani. Sz m¡t si komplexit s A sz mit sig‚ny fgg a v lasztott DCT algoritmust¢l: szorz sok ”sszead sok nagys grendje 1-D DCT defin¡ci¢ alapj n N^2 N^2 2-D DCT defin¡ci¢ alapj n N^4 N^4 2-D szepar l ssal (2N)^3 (2N)^3 A komplexit s a blokkm‚ret fggv‚nye is. Hat‚kony blokkm‚ret 2 eg‚sz sz m£ hatv nya. Homog‚nebb k‚pet kapunk, ha a blokkm‚retet min‚l kisebbre v lasztjuk, viszont min‚l kisebb a blokk, ann l t”bb a kisfrekvenci s egytthat¢, finoman kell kvant lni, a t”m”r¡t‚s m‚rt‚ke kisebb lesz. 4x4-es blokkm‚retn‚l nagyon durv n kell kvant lni a j¢ t”m”r¡t‚shez az el“z“ek miatt. 8x8-as blokk az elterjedt, mert j¢ min“s‚get ad ‚s j¢l t”m”r¡t. 16x16-os blokkm‚retn‚l a t”m”r¡t‚si javul s kis m‚rt‚k–, viszont a sz m¡t sig‚ny jelent“sen n“. K¢dol si hib k A k¢dolt k‚peken ‚szrevehet“ egy blokkosod si hiba, amikor DCT blokkok hat rai megjelennek a k‚pen. M sik probl‚ma a Gibbs-oszcill ci¢ vagy mosquito-zaj, amit az okoz, hogy egy blokkhat ron megy  t egy ‚l. Ilyenkor az ‚l k”rl furcsa elmaszatol¢d st lehet ‚szrevenni. Introk vesztes‚ges k¢dol ssal A 3 legismertebb vesztes‚ges k¢dol st haszn l¢ 64k intro a Black Lotus Jizz ‚s Stash, amik k”rlbell 3 mega truecolor k‚pet tartalmaznak, valamint a Pulse Sink nev– introja. A Jizz kimenti a k‚peket /pandora kapcsol¢val a lemezre, a /mp4 opci¢val az 1 meg s zen‚t is kiszedhetjk. A Sink titkos opci¢ja a /tgas, sajnos nekem a tga k‚pek hib sak voltak ‚s kiment‚s ut n ki is fagyott az intro, ez‚rt pontosan nem tudom, hogy mennyi k‚pet tartalmaz. A Sink kezd“ k‚p‚n (pls_sink.jpg) j¢l ‚szrevehet“ mindk‚t t rgyalt k¢dol si hiba. A Jizz ezt £gy v‚di ki, hogy textur i (tbl_jizz.jpg) teljesen elmosottak, val¢sz¡n–leg 128x128-as k‚pek, amiket  tlagol sos m¢dszerrel nagy¡tottak 256x256-osra ‚s smooth-oltak. Ez egy vektoreffekt textur j n l alig ‚szrevehet“. M sik alkalmazott trkk pedig az, hogy igaz, hogy a lementett k‚pek 24 bites tga-k, de egy 16 bites introba felesleges ilyen sz¡nm‚lys‚gben t rolni a k‚peket. Val¢sz¡n–leg nem kell optim lis Huffmant ¡rni a kit”m”r¡t“be, csak let rolni a 2 Huffman t bl t AC-re ‚s DC-re. Tov bb egyszers¡thetjk a helyzetnket, ha a t”m”r¡t‚ssel nem foglalkozunk, hanem az exe-t”m”r¡t“nkre bizzuk pl. pmwlite, wwpack. B r szerintem ¡gy a t”m”r¡t‚si hat sfok cs”kkenni fog. Rem‚lem, a le¡r s seg¡ts‚g‚vel sok magyar intro fog vesztes‚ges t”m”r¡t‚st haszn lni, megn”velve az introk szinvonal t. Ha k‚rd‚setek van, ¡rjatok a s5001pap@hszk.bme.hu, vagy rod@inf.bme.hu c¡mre.