Prvo najavljujem da će ovaj post prvi dobiti svoju englesku verziju :).
Već drugi post ovaj mjesec, a posla sve više :). Počeo sam se i
ozbiljnije baviti kriptografijom pa je tako iz te želje nastala
implementacija navedenog algoritma.
Grøstl je algoritam koji računa sažetak poruke i on je predložen za SHA3. Ušao je među 5 finalista ali na kraju je pobijedio Keccak.
I sad dalje nema posta... Za one koji žele znati više i probati implementaciju tu se nalazi link na stranicu gdje je objavljen rad koji sam radio u sklopu seminara na naprednim operacijskim sustavima: http://os2.zemris.fer.hr
English version
I've made Grøstl implementation for education usage. You can see project on link: http://os2.zemris.fer.hr or on GitHub.
Monday, May 20, 2013
Tuesday, May 7, 2013
Kompresija slike bez gubitaka
Uh, gotova pauza :). Prošlo je dosta vremena od zadnji put. Razlog su opet obaveze. Zadnjih četiri-pet mjeseci bavio sam se kompresijom slika bez gubitaka pa mi je želja ukratko ispričati o čemu se radi.
Cilj kompresije podataka je smanjiti njihovu originalnu veličinu. Razlozi mogu biti različiti, od želje za uštedom memorijskog prostora do bržeg prijenosa preko mreže i sl. Glavna podjela kompresija je na one s gubitkom i one bez. Kompresija s gubitkom je kompresija pri kojoj se određena količina podataka izgubi i ne može se više vratiti. Poznati formati kao što su JPEG ili MP3 su upravo kompresije s gubitkom. Kako su to kompresije za sliku odnosno zvuk, temelje se na tome da iz podataka maknu informacije koje čovjek ionako ne može uočiti u obliku slike ili zvuka. Kompresija bez gubitaka komprimira podatke ali tako da se poslije mogu vratiti u identičan originalni oblik. Da bi podatke bilo moguće komprimirati potrebna je određena redundancija u njima. Jednostavan primjer je kompresija teksta. Obično se tekst u binarnom formatu zapisuje tako da se za svaki znak (slovo) koristi 8 bitova. Kako se neka slova češće pojavljuju od drugih, ideja je korištenja manjeg broja bitova za takve znakove i većeg broja bitova za znakove koji se rjeđe ponavljaju. Iako neki znakovi sada budu kodirani možda s 15 bitova oni se rijetko pojavljuju, a oni češći će biti kodirani npr. s 2 bita. Rezultat toga je smanjenje prosječne duljine binarnog koda znakova. Ovo je ukratko bio uvod :).
Cilj projekta na kojem sam radio bio je implementacija kompresije bez gubitaka na grafičkim karticama pomoću okruženja CUDA. Kompresija slike bez gubitaka veoma je važna u medicini, gdje je potrebno očuvati originalnu informaciju. Algoritam koji se implementirao bazirao se na predviđanju piksela. Ako su poznati susjedi nekog piksela, tada je velika vjerojatnost da je taj piksel sličan svojim susjedima, ako se radi o prirodnim slikama (npr. slika s puno šuma nema smisla u ovom kontekstu). Problem je što na slikama postoji više različitih područja. Zato samo jedna predikcijska funkcija daje loše rezultate na cijeloj slici. Kompresija se temelji na grešci predviđanja. Za svaki piksel se izračuna razlika između njegove vrijednosti i vrijednosti koje mu je dala predikcijska funkcija. Dobra predikcijska funkcija malo griješi i očekivana greška je 0. To znači da je vjerojatnost pojavljivanja greške 0 velika, pa se sad taj problem može pretvoriti u klasičan problem kao kod kompresije teksta. Direktna kompresija slike kao teksta nije dobra jer je distribucija vrijednosti piksela ujednačena, tj. ne postoji "boja" koja se češće pojavljuje.
Kao što sam naveo, jedna predikcijska funkcija na cijeloj slici nije sasvim dovoljna. Zato se koriste adaptivne metode, koje prepoznaju dijelove slika i prema tome odrede koja će se predikcijska funkcija koristiti. Jedna od takvih metoda implementirana je u ovom projektu. I sad tu još postoji puno detalja ali ako netko ovo i pročita i zanima ga više slobodno me kontaktira :).
Rezultati su bili dobri. Zbog korištenja grafičke kartice umjesto procesora dobilo se ubrzanje algoritma. Osim toga algoritam na grafičkoj kartici troši manje električne energije nego dok se izvodi na procesoru. Moram se zahvaliti zahvaliti i kolegi s kojim sam to radio :).
Eto toliko za sada. Uskoro bi morao doći i post o kriptografiji, preciznije o jednoj relativno novoj hash funkciji (neću reći kojoj :)).
Cilj kompresije podataka je smanjiti njihovu originalnu veličinu. Razlozi mogu biti različiti, od želje za uštedom memorijskog prostora do bržeg prijenosa preko mreže i sl. Glavna podjela kompresija je na one s gubitkom i one bez. Kompresija s gubitkom je kompresija pri kojoj se određena količina podataka izgubi i ne može se više vratiti. Poznati formati kao što su JPEG ili MP3 su upravo kompresije s gubitkom. Kako su to kompresije za sliku odnosno zvuk, temelje se na tome da iz podataka maknu informacije koje čovjek ionako ne može uočiti u obliku slike ili zvuka. Kompresija bez gubitaka komprimira podatke ali tako da se poslije mogu vratiti u identičan originalni oblik. Da bi podatke bilo moguće komprimirati potrebna je određena redundancija u njima. Jednostavan primjer je kompresija teksta. Obično se tekst u binarnom formatu zapisuje tako da se za svaki znak (slovo) koristi 8 bitova. Kako se neka slova češće pojavljuju od drugih, ideja je korištenja manjeg broja bitova za takve znakove i većeg broja bitova za znakove koji se rjeđe ponavljaju. Iako neki znakovi sada budu kodirani možda s 15 bitova oni se rijetko pojavljuju, a oni češći će biti kodirani npr. s 2 bita. Rezultat toga je smanjenje prosječne duljine binarnog koda znakova. Ovo je ukratko bio uvod :).
Cilj projekta na kojem sam radio bio je implementacija kompresije bez gubitaka na grafičkim karticama pomoću okruženja CUDA. Kompresija slike bez gubitaka veoma je važna u medicini, gdje je potrebno očuvati originalnu informaciju. Algoritam koji se implementirao bazirao se na predviđanju piksela. Ako su poznati susjedi nekog piksela, tada je velika vjerojatnost da je taj piksel sličan svojim susjedima, ako se radi o prirodnim slikama (npr. slika s puno šuma nema smisla u ovom kontekstu). Problem je što na slikama postoji više različitih područja. Zato samo jedna predikcijska funkcija daje loše rezultate na cijeloj slici. Kompresija se temelji na grešci predviđanja. Za svaki piksel se izračuna razlika između njegove vrijednosti i vrijednosti koje mu je dala predikcijska funkcija. Dobra predikcijska funkcija malo griješi i očekivana greška je 0. To znači da je vjerojatnost pojavljivanja greške 0 velika, pa se sad taj problem može pretvoriti u klasičan problem kao kod kompresije teksta. Direktna kompresija slike kao teksta nije dobra jer je distribucija vrijednosti piksela ujednačena, tj. ne postoji "boja" koja se češće pojavljuje.
Kao što sam naveo, jedna predikcijska funkcija na cijeloj slici nije sasvim dovoljna. Zato se koriste adaptivne metode, koje prepoznaju dijelove slika i prema tome odrede koja će se predikcijska funkcija koristiti. Jedna od takvih metoda implementirana je u ovom projektu. I sad tu još postoji puno detalja ali ako netko ovo i pročita i zanima ga više slobodno me kontaktira :).
Rezultati su bili dobri. Zbog korištenja grafičke kartice umjesto procesora dobilo se ubrzanje algoritma. Osim toga algoritam na grafičkoj kartici troši manje električne energije nego dok se izvodi na procesoru. Moram se zahvaliti zahvaliti i kolegi s kojim sam to radio :).
Eto toliko za sada. Uskoro bi morao doći i post o kriptografiji, preciznije o jednoj relativno novoj hash funkciji (neću reći kojoj :)).
Subscribe to:
Posts (Atom)