Evo moje kompresije

Od 2000 godine se bavim kompresijom podataka, narocito slika I teksta. Razvio sam par dobrih algoritama za kompresiju, ali pre svega zelja mi je bila da preko interneta prenesem video & audio zapis u skoro realnom vremenu, sto se tice video prenosa moze se reci da sam uspeo.Iskoristio sam par mana oka I proucivsi JPEG I GIF algoritam stvorio FVN (fast-video-net).
Velicina fajla formata FVN je sama po sebi bez naknadnih compresija(Huffman, LZW…) veoma mala:
1/1 [S]tand 240x180 rezolicije 1933.33 b = 1.88 kB const.
1/8 [M]ovement 240x180 rezolucije:
(483.33 b = 0.472 kB max) ->8*0.472=3.776 kb
(161 b = 0.157 kB usually) ->8*0.157=1.256 kb

Evo I poredjenja originalne I kompresovane slike:

[img]D:\Documents and Settings\Marko\My Documents\My Pictures\test-1.jpg[/img]

[img]D:\Documents and Settings\Marko\My Documents\My Pictures\test-1a.jpg[/img]

[img]D:\Documents and Settings\Marko\My Documents\My Pictures\test-2.jpg[/img]

[img]D:\Documents and Settings\Marko\My Documents\My Pictures\test-2a.jpg[/img]

[img]D:\Documents and Settings\Marko\My Documents\My Pictures\test-3.jpg[/img]

[img]D:\Documents and Settings\Marko\My Documents\My Pictures\test-3a.jpg[/img]

[img]D:\Documents and Settings\Marko\My Documents\My Pictures\test-4.jpg[/img]

[img]D:\Documents and Settings\Marko\My Documents\My Pictures\test-4a.jpg[/img]


Prosecna velicina fajla JPEG kompresije je 2.88 kB 8x8 matrica ,0% kvalitet, optimizacija; a FVN-a 9x9 matrica, 0% kvalitet, bez optimizacije drugih kompresija pri istoj 1.8 kB, dok na 10% kvaliteta dostize vrednost do 2,7 kB I pri tome se izjednacava sa JPEG kompresijom na 30% kvaliteta od originalne slike. Naravno time je postignuta veca brzina ne samo iscrtavanja slike nego I prenosa (vecoj od REAL fajlova, pri boljem kvalitetu).

Za sada jedini problem je audio sapis koji za jednu sekundu mora da se smesti u nesto manje od 1kB jer se brzina od 4kB smatra “standardnom” na nasim prostorima. Pa bih ovom prilikom pozvao sve one koji mogu da mi pomognu pri realizaciji ovog formata.

Uskoro cu dati ceo algoritam-objasnjenje (cim ga zavrsim sa pisanjem)

Ne radi ti link ka slici.

Ja ne vidim kakve veze ima ova specifikacija tog tog algoritma sa teorijom programiranja - ako si vec hteo da pricas o necem sto spada u ovu diskusionu grupu, onda je trebalo da opises tu svoju kompresiju, kako ona radi, eventualno na bazama kojih drugih algoritama je osmisljena/uradjena, i slicno. Ovako je to samo jedna prosta prica koju je svako mogao da smisli i posalje. - Sto bi nas narod rekao - "mrtvo slovo na papiru".

Potpis

Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin

Bez uvrede, ja ne zelim da omalovazavam tvoj rad, ni slucajno, samo zelim da kazem da bez konkretnog necega ne zelim da verujem ni u sta. One slike takodje mogu biti uradjene nekim filtrom...

Potpis

Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin

Definitivno stvar za koju treba odvojiti uvo ili oko i pratiti razvoj situacije. Mislim da je čak i najavi algoritma ovde mesto, pogotovo ako će opis uskoro uslediti. Ono što bih želeo da vidim u vezi sa ovim algoritmom za kompresiju, kao neko koje umereno obrazovan u obradi signala jeste:

- Zašto je za poređenje izabrana matrica 8x8 za JPEG a 9x9 za FVN? Poznata je činjenica da JPEG a i svi drugi algoritmi za kompresiju energije bolje rade ako je matrica veća. Takođe, kakva je kvantizacija i da li je uopšte korišćena. JPEG u principu ne koristi perceptuelno kodiranje već minimizaciju srednjekvadratne greške tako da tu sigurno ima mesta za poboljšanja.

- Koliko je algoritam jednostavan za implementaciju? JPEG je upravo takav kakav je zato što se jednostavno da napraviti i u softveru i u hardveru. Činjenica da nešto bolje kompresuje sliku od JPEG-a nije isključiv pokazatelj kvaliteta. JPEG je važeći standard jer je jednostavan a ipak efektan.

- Kako se algoritam poredi sa KL-optimalnom transformacijom slike? Karhunen-Loeve je transformacija slike (poput DFT ili nečeg sličnog) koja dokazano optimalno komprimuje energiju slike (ne mož' bolje!) ali se zato svodi na računske operacije koje su izuzetno zahtevne. DCT pod izvesnim uslovima konvergira ka KL pa bi zanimljivo bilo videti da li FVN može da se udene između ove dve.

- Šta tačno znače procenti kompresije. To što je JPEG komprimovan sa 0% kvaliteta ne znači ništa posebno i samo je subjektivna mera u softveru

- Kako se metodologija DCT-a prebacuje u domen pokretnih slika, a naročito kako se došlo do zaključka da je složenije kodirati zvuk nego sliku. Naime statistika zvučnog signala je kudikamo prostija nego statistika slike (proces je stacionaran, jednodimenzioni, jako korelisan itd) i opšte mišljenje je da je upravo obrnuto. Standardi za streaming video koriste i vremensku korelaciju uzastopnih slika i tu ulogu igraju stvari kao što je segmentacija, praćenje, procena i predviđanje pokreta i na tome se prilično tvrdo radi poslednjih godina (decenija?). Svaki pomak u tom smislu bi vredeo dosta para.

f

Naravno da je sve bez objasnjenja "mrtvo" ali evo objasnjenja:

[S]tand slike
1. velicina slike koju smatram optimalnu za nase uslove je 240x180
2. koliko imam blokova 9x9 u njoj:
M=(240x180)/(9x9)=534
3. koliko imam bitova po jednoj 9x9 matrici:
COLOR_1 [Y]:[U]:[V]=[1] : [1/16] : [1/16]
COLOR_2 [Y]:[U]:[V]=[1/16] : [0] : [0]

COLOR_1 ukupno ima 8+4+4=16 bitova
COLOR_2 ukupno ima 4+0+0=4 bitova

COLOR_1 je tacka (0,0) u matrici I nosi originalnu informaciju o luminentnoj vrednosti dok za hrominentne komponente ima upola manju gledano u bitovima.
COLOR_2 je vrednost samo luminentnog signala ali prosecna za sve vrednosti, medjutim ja sam koristio I srednju vrednost prve dve vrednosti, dok za hrominentne nisam uzimao nikakve vec sam koristio vec postojece

Komponente sam definisao kao:
Y=0.3R+0.59G+0.11B za COLOR_1
Y=(0.3R+0.59G+0.11B) / 16 za COLOR_2
U=R/16
V=B/16 (da bi bile pozitivne I male)

E sada sam isparcelisao matricu 9x9 na 3x3 I dobio 9 novih koje sam dalje definisao kao 1 ili 0.Znaci ako je trenutna podmatrica po intezitetu luminentne komponente manja onda bi ta cela matrica bila popunjena 0:
0-0-0
0-0-0
0-0-0

A ukoliko bi bi bila veca onda bi izgledala ovako:
1-0-1
0-1-0
1-0-1

Mesta na kojima se nalazi 1 iscrtava se prva vrednost luminentne komponente, a gde je 0 onda se iscrtava ona sredja vrednost sledecih.
Naglasavam da se iz podmatrica ne uzima nova vrednost za luminentne I hrominentne komponente, vec se koristi ona iz prve podmatrice u prvom redu (ili glavne matrice prva).

N=COLOR_1 + COLOR_2 + 9=16+4+9=29bits (~3.6byte)
UKUPNO=M*N=534*3.6=1922.4 Bytes=1.877 kB

Kao sto vidite ovde nema nikakvih koeficijenata matrice kojima se obradjuje originalna.Evo I prakticnog primera jedne matrice (dodatak).

Pratim ovu temu i pogledao sam test primere, i nesto mi nije jasno u njima - koje su od ovih slika obradjene tvojim algoritmom a koje su originali?

Pretpostavljam da je, recimo, TEST-1.JPG originalna slika u JPEG formatu, dok je TEST-1A.JPG ta ista slika obradjena tvojim algoritmom?

Razjasni mi to pa da nastavim komentar.

Potpis

Alex: My favorite site is http://localhost/
R.J. Oppenheimer: "I am become death, destroyer of worlds" (1945 AD)
tweet.13x ||
linkedin.13x

Komentar će ići na kraju, ali najpre nekoliko potpitanja u vezi objašnjenja (kako bi u sledećoj iteraciji bilo jasnije)


Zašto optimalna i za koje naše uslove? Optimalna znači najbolja, a ako je najbolja onda je izabrana kao najbolja u odnosu na neki kriterijum. Koji kriterijum? Koji su to naši uslovi?


Ovaj deo računa mi nije jasan. Šta je 1/16 i kako se od toga dobije 4? Očigledno množenjem sa 8, ali zašto baš sa 8? Čini mi se da ima veze sa normiranjem na 8-bitne vrednosti ali ako si tako mislio, onda si to morao i da napišeš.


U kojoj matrici? Koje matrice uopšte učestvuju u kompresiji? Ovo objašnjenje ti je dosta maglovito a veoma je bitno da bi se išta razumelo na dalje! Moraš da ovo razjasniš, na primer tako što ćeš uvesti definicije pojmova sa kojima radiš. To moraš uraditi kako bismo te razumeli.


Šta su Y,U,V, šta su R,G,B. Moraš objasniti! Igrom slučaja znam o čemu govoriš ali to ne treba da se podrazumeva. U kom formatu se pamti slika, u kom formatu se pamti bilo šta drugo? Kvantizacija koju ćeš ovde primeniti je od suštinske važnosti za kvalitet kompresije tako da je jako bitno šta se pod svim ovim komponentama podrazumeva.


Ovo kodiranje je vrlo neefikasno, ali se to može srediti (verovatno jesi sredio u implementaciji).


Pošto ne znamo koja je to prva podmatrica, ne znamo koja je glavna podmatrica, verovatno ne znamo ni o čemu govoriš. Ovo bi trebalo bolje objasniti.


Opet isto, govori se o nekakvim jednim i originalnim matricama, a da te matrice nigde pre nisu definisane.

Ok, nadam se da ćeš primedbe uvažiti, pošto sam opisao šta mi u tvom obrazloženju nije bilo jasno.

E sad idemo dalje sa komentarom. Kao što u životu to obično biva, imam za tebe jednu dobru i jednu lošu vest. Dobra vest je da je očigledno da si dobro uradio domaći zadatak. U tvom kodiranju postoje skoro sve bitne komponente kodiranja 2D signala: perceptuelno kodiranje (YUV), kvantizacija (nejednak raspored bita), filtriranje (usrednjavanje susednih) i diferencijalno kodiranje (pamćenje samo razlika).

Loša vest je da je tvoje kodiranje verovatno daleko od najboljeg mogućeg i to iz više razloga. Najpre, perceptuelno kodiranje je uzeto proizvoljno -- kod, ajde da kažem profesionalnih sistema za obradu slike, tablice osetljivosti se definišu za različite rezolucije, posmatrače itd. Tvoja kvantizacija je takođe linearna, što verovatno nije pravi model za ljudsko opažanje. Dalje, ključ kompresije -- usrednjavanje i diferencijalno kodiranje koje si primenio rade ali imaju ozbiljne mane (zato ljudi i nisu batalili problem kompresije slika već se i dalje zezaju sa time): naime, usrednjavanje je neka vrsta NF filtra za sliku, ali problem sa njim je što su spektralne osobine takvog filtra prilično loše, jer se skidaju sve komponente spektra i gubitak informacija je veliki.

Da pojasnim: ako u celoj slici četvorke od po piksela zameniš njihovom srednjom vrednošću (poznati pixelize efekat) količina informacije se smanji -- hoću da kažem da se time svaka slika može srezati na četvrtinu originalne veličine. Problem je što onda nisi odrezao samo deo spektra koji ti nije potreban, već i deo koji nosi informaciju. Činjenica da to nisi radio u prostoru RGB nego u YUV nema preterano puno značaja. Zato se upravo i istražuju načini da se nepotrebni spektar što bolje odreže a da potrebni deo ostane tu.

I napokon tu je diferencijalno kodiranje koje, zbog prirode operacije unosi šum (jer snaga šuma postaje dvaput veća dok se signal po intenzitetu smanjuje) i koje zato valja izbegavati koliko je god moguće. Zato se diferencijalno kodiranje kod JPEG-a recimo koristi samo za srednju vrednost celog bloka, s obzirom da su tu signali dovoljno jaki da šum nema preterano mnogo uticaja.

Tvojoj kompresiji vrlo fali obrada slike u frekventnom domenu. Ako te zanima nešto više o kompresiji slike (mislim da si na dobrom putu, uzgred budi rečeno!) možeš se javiti na mail, imam nešto materijala o tome (na srpskom!).

f

Mislim da bi tema trebala da ostane u AOP forumu dok se ne smisli neki bolji - posto u "Audio - Vizuelne Tehnologije" sigurno ne spada jer je vise skoncentrisana na istrazivacki rad a manje na "korisnicki" deo.

Potpis

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey

pokusa cu da ti odgovorim pitanje po pitanje:

1. 240x180 je 'optimalna' u slucaju da se u obzir uzme i velicina fajla koji bi se dobio

2. moja je greska, mislio sam da znas da se svaka R,G,B boja nalazi u opsegu od 00-FF (hex), odnosno 0-255 (dec).

3. Y je luminentna komponenta (osvetljaj), U i V su hrominentne komponente i od manje su vaznosti, za razliku od luminentne.

4. moram priznati da sam naveo na nesporazum, ali trudi cu se da to ispravim, naime, matricom sam smatrao 'tabelu' sacinjenu od 9 redova i 9 kolona, kasnije sam rekao da ima 9 'pod-tabela', manjih od po 3 reda i 3 kolone, kojih ukupno imam 9. Prva podtabela je najvaznija jer se iz nje uzimaju 'glavna' Y,U i V komponente i srednja vrednost za tu prvu i odmah sledecu vrednost (ovo se odnosi samo na Y komponentu).E sad kako bi umanjio velicinu u bajtovima morao sam da uvedem one 'sare'.

marko tasic postade slavan

svaka cast!

U kom smislu 'slavan'? Je li uradio nesto od ovoga?
Daj prosvetli me, molim te.

Rajko

http://www.blic.co.yu/danas/broj/strane/tema.htm

Marko cestitam ti.
Nadam se da ce biti jos pametnih momaka(i devojaka :)) kojima ce nasa zemlja moci da se ponosi u svetu.

bedak što je ispao neshvaćen na ES :)

Potpis

Jel potpis treba pisanim ili
štampanim slovima?
___________________________________
______
[url=http://www.dizajnzona.com/foru
ms/]dizajnzona.com[/url]
[url=http://www.netizenfaction.com/
]netizenfaction.com[/url]
egoideas.
com
levodesn
o.com

Otkud ti to? Ljudi su bili zainteresovani i pitali su šta ih je o tome zanimalo.

f

Mislim da bi sve bilo mnogo jasnije kada bi poslao neki sorsić. Tema je vrlo interesantna.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Elem, za one sa jeftinijim ulaznicama koji tvrde da neko nije shvacen:

Autor je impliciitno sugerisao da je unapredio state of the art (JPEG, itd...), zatim su sledila potpuno smislena pitanja od strane kolege Filmila kakvu bi postavio bilo ko upucen u materiju.

Na neke odgovore je dat odgovor od autora - na neke nije, i bilo bi lepo kada bi se diskusija nastavila.

Ja licno imam velike rezerve prema tvrdnji o unapredjenju (pre svega, JPEG kakav je uopste ni nije state-of-the-art), takodje nacin vrednovanja (weighting) koeficijenata (tj. ispravno je reci piksela, posto se ne radi o spektralnim koeficijentima) nije optimalan, radi se u neoptimalnom domenu (prostornom, ne spektralnom i time se gubi dosta na mogucnosti redukcije irelevantnosti), pa mi se cini da je neophodno dodatno pojasnjenje o tvrdnjama da bi se dao krajnji sud koji je cini mi se negativan u odnosu na tvrdnje o unapredjenju u odnosu na stanje nauke - ovako kako je opisano (ne mora da znaci da nije unapredjeno) ima vrlo male sanse (da se tako izrazim) da bude efikasnije od transformacionog kodera optimizovanog sa perceptualnom matricom i vrlo dobrim ukidanjem irelevancije (entropijskim kodiranjem)

Sto naravno ne znaci da decko nema talenat ili zelju da istrazuje, sto je svakako demonstrirao dugim radom na polju kompresije i to je sa svaku pohvalu i drago mi je da je uspeo da nadje nacin da nastavi svoj istrazivacki rad na mestu gde to moze da postigne.

Ali, da se vratimo na sustinu - codec, onakav kakav ga je opisao je daleko od unapredjenja nauke ili nekog danasnjeg optimuma - ali uz dosta rada to mozda moze i da postane (mozda je vec postao ali mi nemamo povratnu informaciju)

Dakle ne radi se o nerazumevanju, vec o naucnoj diskusiji kakva bas treba da bude i koja ukljucuje i naucni rigor.

Ono sto su mediji objavili o tome, ako se radi o istoj stvari, je ipak naduvavanje i moze samo da skodi svima.

Potpis

DigiCortex (ex. SpikeFun) - Cortical Neural Network Simulator:
http://www.digicortex.net/node/1 Videos: http://www.digicortex.net/node/17 Gallery: http://www.digicortex.net/node/25
PowerMonkey - Redyce CPU Power Waste and gain performance! - https://github.com/psyq321/PowerMonkey

Slazem se prethodnom porukom u vezi svega, ali moram reci da je sve odo gore bilo probno 'zagrevanje' sada sam malo vise svestan stvari koje radim, i nadam se da cu uskoro reci o cemu se radi. Ako neko ima svoje istrazivanje ili nesto sl neka postavi ovde pa da svi razmenjujemo iskustva.

a kako onda zoves ovo:
https://www.elitesecurity.org/t72240


:))