Sad je prošlo već podosta vremena i morao bi već nešto napisati.
Prošlo je ako dobro vidim 6 mjeseci... pola godine! I stvarno ne znam kad. Bilo je ovo prvo radno ljeto (ajde ne baš cijelo). Možda baš zbog toga nije bilo novih postova.
Mogu reći da se puno toga promijenilo od zadnji put. Iako neplanirano (da, da) privremeno sam se zaposlio. Odluka nije bila jednoglasna s moje strane. Jedini razlog koji je prevagnuo bio je "ajmo probati nešto novo".
Međuvremenu radilo se tu malo i sa strojnim učenjem i uglavnom bilo je zabavno. Opet razmišljam o tome da pišem neki konstruktivan blog npr. o nekim novim spoznajama i da to bude kontinuirano. Ali znam da ću se izgubiti u vremenu.
Neka ovo bude najava o blogu koji se bavi novim spoznajama iz svijeta fizike/računarstva i to sam čvrsto odlučio da bude na engleskom. Pa eto ako ne bude tako, slobodno mi javite da sam zaboravio sam na sebe.
Wednesday, November 20, 2013
Monday, May 20, 2013
Grøstl - sigurnosni algoritam za računanje sažetka poruke
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.
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.
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 :)).
Saturday, February 16, 2013
Kvantna računala
Ovaj post htio bih posvetiti kvantnim računalima, tj. pokušat ću objasniti to na jednostavan i prihvatljiv način.
Da bismo mogli razumjeti što su kvantna računala, moramo znati što je to kvantna fizika uopće. Kvantna fizika je nešto kao matematički framework koji može objasniti eksperimente na kvantnoj razini. To nije ništa drugo nego matematički model koji jako dobro opisuje prirodu. Kvantni efekti dolaze na vidjelo kada se proučavaju male čestice (molekule, atomi, ...). A riječ kvantna dolazi od svojstva da sve što mjerimo ima točno određeni skup vrijednosti i ništa više. Hm... :). Recimo to ovako, kad bi mi doživljavali kvantne efekte tada bi na primjer mogli voziti auto brzinom 1 km/h, 10 km/h, 15 km/h, 200 km/h. Ali samo tim brzinama, ništa između, ništa više, ništa manje. Između ne postoji i nije ostvarivo. To je kvantna fizika. I sad postaje sve nelogično :). Problem kvantne fizike je u tome što je neintuitivna, tj. ljudi je nikad nisu doživjeli i teško je to povezivati s bilo čime. Zato je tu matematika, koja je dobro definirana i iz koje možemo proučavati prirodu. Poznati fizičar Richar Feynman izjavio je: "If you think you understand quantum mechanics, you don't understand quantum mechanics."
Dakle, ne treba se mučiti s pitanjima zašto je to tako, jer odgovor koji bi nama ljudima bio prirodan za sada još ne postoji. (Idemo vjerovati matematici.)
Postoje postulati kvantne mehanike (fizike), ali sad ne bih htio ulaziti u dubinu svakoga od njih. Bit ove rečenice je da postoje aksiomi koji postavljaju model i dalje se sve radi prema njima. Ono što je bitno za shvatiti je da u igru ulaze vjerojatnosti i linearna algebra (matrice). Sve što mjerimo je slučajno. Tj. svi rezultati koje dobismo nisu apsolutni već je svaki rezultat moguć s nekom vjerojatnosti. Kada bi nam netko mjerio brzinu s kojom se vozimo (primjer od gore), on bi mogao izmjeriti bilo koju od mogućih brzina (1, 10, 15, 200), ali svaka bi imala određenu vjerojatnost. Recimo to tako, da izmjeri brzinu 1 km/h vjerojatnost je 10%, da izmjeri brzinu 10km/h vjerojatnost je 20%, da izmjeri 15km/h vjerojatnost je 30% i da izmjeri brzinu 200km/h vjerojatnost je 40%. Pa dobro tko je tu lud? S kojom brzinom se uopće mi vozimo. E tu je bit kvantne mehanike. Takvu informaciju onaj koji mjeri ne može imati prije nego izmjeri (haha). A fora u mjerenju je da mjeritelj utječe na sam sustav. Recimo da postoji instrument koji mjeri brzinu tako da gađa auto kamenjem, čija je masa 20kg. Očito će taj kamen utjecati na brzinu auta, i upravo se to događa na mikroskopskim česticama, mi utječemo na mjerenje.
Druga bitna stvar je da su sve fizikalne veličine linearni operatori (a joj...). Ali ne ćemo se ni time zamarati previše. Važna posljedica toga je da su fizikalne veličine matrice.
Sad idemo na računala :). Kvantna računala su u svojoj biti kvantno-mehanički sustavi. A to može biti bilo što :). Primjer: elektroni, molekule, atomi... Prvi koncept koji se ne poklapa s klasičnim računalima su bitovi, tj. qubitovi. Pa što je qubit? Qubit je pravo kvantno-mehaničko stanje (ha?). Zamislimo da imamo jedan bistabil (1bit registar) i mjerimo tj. čitamo što u njemu piše. U klasičnim računalima piše ili 1 ili 0. U kvantnima piše i 1 i 0 istovremeno. To se zove superpozicija stanja. Na jednak način kako mjeritelj brzine ne zna kojom se brzinom vozimo, već zna samo vjerojatnosti, na jednak način mi čitamo taj qubit. Znamo da postoji određena vjerojatnost pojave 1 i pojave 0, ali ne znamo unaprijed što ćemo pročitati (osim ako vjerojatnosti nisu rubni slučajevi, tj. da je vjerojatnost nule ili jedinice 1). Qubit predstavljamo vektorom dimenzije 2x1. Množenjem matrice i vektora dobivamo novi vektor i to nam je sad novo stanje, tj. obavili smo operaciju nad qubitom (računanje). Konstruiranjem različitih matrica postižemo različite operacije i to je zapravo srž kvantnih računala. Problem je fizički konstruirati to. Ima tu još problema, jedan od glavnih problema je vanjski utjecaj na qubite, tj. njihova izolacija od vanjskog svijeta.
Najvažnija efekt, zbog koje su kvantna računala brza je kvantna sprega (engl. entanglement). Neka su dvije čestice nastale u istom procesu (nije bitno konkretno kako). Pošaljemo ih međusobno jako jako daleko. I sad mjereći neku fizikalnu veličinu na jednoj u istom trenutku znamo tu fizikalnu veličinu na drugoj čestici. Kako je to moguće? Ako su čestice tako razmaknute da svjetlosti treba par godina da dođe, tada ovaj efekt postaje čudan. Jer kako je jedna čestica mogla znati da je druga izmjerena. Postoje mnoga tumačenja ovog efekta, ali bilo što bilo on postoji. Računalna moć proizlazi upravo iz tako sparenih qubita. Kada imam sparene qubite i nad njima radimo operacije, dobijemo paralelne efekte (slično kao da imamo više procesora), ali sve to jednim relativno malim kvantno-mehaničkih sustavom.
Za kraj jedan konkretan (i osnovni) kvantni algoritam:
(detalje pogledati na: http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm)
(slika preuzeta od: http://commons.wikimedia.org/wiki/File%3ADeutsch_algorithm_circuit.svg)
Na slici je prikazana shema Deutschovog algoritma. Vidimo da su algoritmi modelirani kao procesni elementi (slično kao algoritmi u digitalnoj logici).
Što je i kako radi algoritam?
Pretpostavimo da imamo funkciju $$f(x)$$ koja može kao ulaz primiti 0 ili 1, i isto tako daje izlaz 0 ili 1 (slično kao u digitalnoj logici). Definirat ćemo dvije vrste funkcija:
Na ulazu - prva "žica" ima qubit kojemu je vjerojatnost da je 0 jednaka 1 (tj. 100% je 1). Na drugoj "žici" imamo qubit na kojemu je 100% 1. Dva modula na kojima piše H su Hadamartova vrata (matrice) i nakon toga dobijemo qubitove na kojima više nije 100% 1 ili 0, nego 50:50. Takvi qubitovi se procesiraju u ovom velikom modulu gdje na prvom izlazu je qubit koji je bio i na ulazu (prva "žica"). Ali drugi qubit nije isti, nego je on poprima stanje ovisno o vrijednosti funkcije. Primjenjujući još jednom vrata i mjereći dobivamo jedinstven odgovor, ili mjerimo 1, ili mjerimo 0. Sad tu bi trebalo staviti malo matematike i množenja matrica i provedbu računa. Bitna stvar je da se kvantno računalo ponašalo kao paralelni stroj, tj. istovremeno smo izračunali vrijednosti funkcije ali u jednom koraku, i tu je njegova snaga. Tj. možemo gledati kao da su qubiti na paralelnim "žicama" spareni).
Više detalja pogledajte na:
http://en.wikipedia.org/wiki/Quantum_computer
I obavezno pogledajte knjigu:
Quantum Computation and Quantum Information, Michael A. Nielsen, Isaac L. Chuang
Za kraj: Nisam htio biti naporan s previše detalja (iako sam naporan sam po sebi :) ), ali se ipak nadam se ste osjetili ideju koja stoji iza toga.
Da bismo mogli razumjeti što su kvantna računala, moramo znati što je to kvantna fizika uopće. Kvantna fizika je nešto kao matematički framework koji može objasniti eksperimente na kvantnoj razini. To nije ništa drugo nego matematički model koji jako dobro opisuje prirodu. Kvantni efekti dolaze na vidjelo kada se proučavaju male čestice (molekule, atomi, ...). A riječ kvantna dolazi od svojstva da sve što mjerimo ima točno određeni skup vrijednosti i ništa više. Hm... :). Recimo to ovako, kad bi mi doživljavali kvantne efekte tada bi na primjer mogli voziti auto brzinom 1 km/h, 10 km/h, 15 km/h, 200 km/h. Ali samo tim brzinama, ništa između, ništa više, ništa manje. Između ne postoji i nije ostvarivo. To je kvantna fizika. I sad postaje sve nelogično :). Problem kvantne fizike je u tome što je neintuitivna, tj. ljudi je nikad nisu doživjeli i teško je to povezivati s bilo čime. Zato je tu matematika, koja je dobro definirana i iz koje možemo proučavati prirodu. Poznati fizičar Richar Feynman izjavio je: "If you think you understand quantum mechanics, you don't understand quantum mechanics."
Dakle, ne treba se mučiti s pitanjima zašto je to tako, jer odgovor koji bi nama ljudima bio prirodan za sada još ne postoji. (Idemo vjerovati matematici.)
Postoje postulati kvantne mehanike (fizike), ali sad ne bih htio ulaziti u dubinu svakoga od njih. Bit ove rečenice je da postoje aksiomi koji postavljaju model i dalje se sve radi prema njima. Ono što je bitno za shvatiti je da u igru ulaze vjerojatnosti i linearna algebra (matrice). Sve što mjerimo je slučajno. Tj. svi rezultati koje dobismo nisu apsolutni već je svaki rezultat moguć s nekom vjerojatnosti. Kada bi nam netko mjerio brzinu s kojom se vozimo (primjer od gore), on bi mogao izmjeriti bilo koju od mogućih brzina (1, 10, 15, 200), ali svaka bi imala određenu vjerojatnost. Recimo to tako, da izmjeri brzinu 1 km/h vjerojatnost je 10%, da izmjeri brzinu 10km/h vjerojatnost je 20%, da izmjeri 15km/h vjerojatnost je 30% i da izmjeri brzinu 200km/h vjerojatnost je 40%. Pa dobro tko je tu lud? S kojom brzinom se uopće mi vozimo. E tu je bit kvantne mehanike. Takvu informaciju onaj koji mjeri ne može imati prije nego izmjeri (haha). A fora u mjerenju je da mjeritelj utječe na sam sustav. Recimo da postoji instrument koji mjeri brzinu tako da gađa auto kamenjem, čija je masa 20kg. Očito će taj kamen utjecati na brzinu auta, i upravo se to događa na mikroskopskim česticama, mi utječemo na mjerenje.
Druga bitna stvar je da su sve fizikalne veličine linearni operatori (a joj...). Ali ne ćemo se ni time zamarati previše. Važna posljedica toga je da su fizikalne veličine matrice.
Sad idemo na računala :). Kvantna računala su u svojoj biti kvantno-mehanički sustavi. A to može biti bilo što :). Primjer: elektroni, molekule, atomi... Prvi koncept koji se ne poklapa s klasičnim računalima su bitovi, tj. qubitovi. Pa što je qubit? Qubit je pravo kvantno-mehaničko stanje (ha?). Zamislimo da imamo jedan bistabil (1bit registar) i mjerimo tj. čitamo što u njemu piše. U klasičnim računalima piše ili 1 ili 0. U kvantnima piše i 1 i 0 istovremeno. To se zove superpozicija stanja. Na jednak način kako mjeritelj brzine ne zna kojom se brzinom vozimo, već zna samo vjerojatnosti, na jednak način mi čitamo taj qubit. Znamo da postoji određena vjerojatnost pojave 1 i pojave 0, ali ne znamo unaprijed što ćemo pročitati (osim ako vjerojatnosti nisu rubni slučajevi, tj. da je vjerojatnost nule ili jedinice 1). Qubit predstavljamo vektorom dimenzije 2x1. Množenjem matrice i vektora dobivamo novi vektor i to nam je sad novo stanje, tj. obavili smo operaciju nad qubitom (računanje). Konstruiranjem različitih matrica postižemo različite operacije i to je zapravo srž kvantnih računala. Problem je fizički konstruirati to. Ima tu još problema, jedan od glavnih problema je vanjski utjecaj na qubite, tj. njihova izolacija od vanjskog svijeta.
Najvažnija efekt, zbog koje su kvantna računala brza je kvantna sprega (engl. entanglement). Neka su dvije čestice nastale u istom procesu (nije bitno konkretno kako). Pošaljemo ih međusobno jako jako daleko. I sad mjereći neku fizikalnu veličinu na jednoj u istom trenutku znamo tu fizikalnu veličinu na drugoj čestici. Kako je to moguće? Ako su čestice tako razmaknute da svjetlosti treba par godina da dođe, tada ovaj efekt postaje čudan. Jer kako je jedna čestica mogla znati da je druga izmjerena. Postoje mnoga tumačenja ovog efekta, ali bilo što bilo on postoji. Računalna moć proizlazi upravo iz tako sparenih qubita. Kada imam sparene qubite i nad njima radimo operacije, dobijemo paralelne efekte (slično kao da imamo više procesora), ali sve to jednim relativno malim kvantno-mehaničkih sustavom.
Za kraj jedan konkretan (i osnovni) kvantni algoritam:
(detalje pogledati na: http://en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm)
Na slici je prikazana shema Deutschovog algoritma. Vidimo da su algoritmi modelirani kao procesni elementi (slično kao algoritmi u digitalnoj logici).
Što je i kako radi algoritam?
Pretpostavimo da imamo funkciju $$f(x)$$ koja može kao ulaz primiti 0 ili 1, i isto tako daje izlaz 0 ili 1 (slično kao u digitalnoj logici). Definirat ćemo dvije vrste funkcija:
- ako funkcija za bilo koji ulaz daje isti izlaz - zovemo ju konstantnom
- ako funkcija za različite ulaze da je različite izlaze - zovemo ju nekonstantnom
Na ulazu - prva "žica" ima qubit kojemu je vjerojatnost da je 0 jednaka 1 (tj. 100% je 1). Na drugoj "žici" imamo qubit na kojemu je 100% 1. Dva modula na kojima piše H su Hadamartova vrata (matrice) i nakon toga dobijemo qubitove na kojima više nije 100% 1 ili 0, nego 50:50. Takvi qubitovi se procesiraju u ovom velikom modulu gdje na prvom izlazu je qubit koji je bio i na ulazu (prva "žica"). Ali drugi qubit nije isti, nego je on poprima stanje ovisno o vrijednosti funkcije. Primjenjujući još jednom vrata i mjereći dobivamo jedinstven odgovor, ili mjerimo 1, ili mjerimo 0. Sad tu bi trebalo staviti malo matematike i množenja matrica i provedbu računa. Bitna stvar je da se kvantno računalo ponašalo kao paralelni stroj, tj. istovremeno smo izračunali vrijednosti funkcije ali u jednom koraku, i tu je njegova snaga. Tj. možemo gledati kao da su qubiti na paralelnim "žicama" spareni).
Više detalja pogledajte na:
http://en.wikipedia.org/wiki/Quantum_computer
I obavezno pogledajte knjigu:
Quantum Computation and Quantum Information, Michael A. Nielsen, Isaac L. Chuang
Za kraj: Nisam htio biti naporan s previše detalja (iako sam naporan sam po sebi :) ), ali se ipak nadam se ste osjetili ideju koja stoji iza toga.
Tuesday, January 15, 2013
Rezanje kapa
Kakvo li sad rezanje kapa? Pa eto, što sam radio preko vikenda i potrošio cca 42 sata. E pa na rezanje kapa. Da malo približim o čemu se radi. Projekt na jednom kolegiju je bio "Detekcija i klasifikacija različitih pokrivala za glavu". Ideja je dakle da se na slici pronađe čovjek, odnosno njegovo lice i da se s njegove glave izreže kapa. Izrezati u smislu kako bi to npr. napravili u Photoshop-u. Naravno to treba biti automatizirano. U ovom trenutku se naslućuje kompleksnost problema, ali to nije zabavni dio priče.
Zabavni dio priče je taj da smo to radili u timu. Tim od osam ljudi. Projekt je bio davno zadan, tamo negdje u 10. mjesecu prošle godine. Naravno kako to kod nas ide projekt se počeo ozbiljno raditi tri dana prije predaje. Netko bi se mogao pitati: "Za tri dana stignete pronaći kapu na čovjeku i još k tome reći koja je vrsta kape?". E nismo ni mi (tim) znali da je moguće ali očito je :).
Moj zadatak bio je da odredim gdje se nalazi kapa i da ju probam čim bolje odrezati. Otud i naziv za ovaj post. Da se ne hvalim moram napomenuti da sam na tom zadatku radio zajedno s kolegicom.
Ideja je sljedeća:
Ima sad tu još puno drugih stvari vezanih uz projekt ali ovo je bitno za rezanje kape.
Moram napomenuti da je ovaj algoritam produkt naših ideja i istraživanja (tj. isprobavanja, budimo iskreni, ali kao što se vidi nije to nešto previše komplicirano).
Rezultati:
Greške zbog kojih dolazi unutar kape su posljedica micanja lica, gdje se onda i neke boje s kapa maknu. Ali to pomaže u preciznjem rezanju donjeg oblika kapa i zapravo ta greška ne utječe jako na krajnji rezultat (tj. prepoznavanje kape).
I sad neočekivani zaključak: Rad u timu od 8 ljudi je prava umjetnost. Nikad nisam volio raditi u timu, ali to nekako progutam ako imam sa sobom razumne ljude, u ovom slučaju su to bili i iznimno pametni ljudi.
Sad par savjeta što ne raditi:
Zabavni dio priče je taj da smo to radili u timu. Tim od osam ljudi. Projekt je bio davno zadan, tamo negdje u 10. mjesecu prošle godine. Naravno kako to kod nas ide projekt se počeo ozbiljno raditi tri dana prije predaje. Netko bi se mogao pitati: "Za tri dana stignete pronaći kapu na čovjeku i još k tome reći koja je vrsta kape?". E nismo ni mi (tim) znali da je moguće ali očito je :).
Moj zadatak bio je da odredim gdje se nalazi kapa i da ju probam čim bolje odrezati. Otud i naziv za ovaj post. Da se ne hvalim moram napomenuti da sam na tom zadatku radio zajedno s kolegicom.
Ideja je sljedeća:
- Pronađi lice na slici (postoji puno gotovih algoritama za to i to nije problem)
- Procijeni gdje se nalazi kapa (očito iznad lica i veličine je lica + 30% prema dole)
- Iz te slike obriše se lice (zna se koja je boja lica i ti pixeli se izbrišu iz te manje slike gdje se pretpostavlja da je kapa)
- Iz slike gdje je izbačeno lice probaju se naći krivulje i po tim krivuljama odrezati kapu (e tu je onaj zanimljivi dio)
- Prvo se slika pretvori u nijanse sive (boja->crno-bijela)
- Na toj slici se traže rubovi i nastaje čisto crno bijela slika (bez nijansi sive), gdje je 1 predstavlja pixel koji je na rubu a 0 su svi ostali pixeli. (Na rubu znači da je između te točke na slici i susjedne nagla promjena u boji, i to se definira kao rub)
- Iz tako novo dobivene konstruiraju se krivulje, tako da ako se dvije točke koje predstavljaju rub susjedne, točke na istoj krivulji (znači može biti više odvojenih krivulja na slici)
- Ali to nije sve: Sad je tu trik. Kako te točke koje su rubovi i na kad gledamo našim okom očito su te točke na istoj krivulji, Canny često tu napravi grešku. Ideja je da se svaka točka podeblja. Sad umjesto da je veličine jednog pixela, duplo je veća npr. 2x2 kvadrat pixela.
- Sad se još jednom probaju naći krivulje. Iz takvih krivulja uzme se ona krivulja koja zatvara najveću površinu, i kaže se to je kapa.
- Iz informacije o obliku kape slika se odreže (pomoću maske)
Ima sad tu još puno drugih stvari vezanih uz projekt ali ovo je bitno za rezanje kape.
Moram napomenuti da je ovaj algoritam produkt naših ideja i istraživanja (tj. isprobavanja, budimo iskreni, ali kao što se vidi nije to nešto previše komplicirano).
Rezultati:
Greške zbog kojih dolazi unutar kape su posljedica micanja lica, gdje se onda i neke boje s kapa maknu. Ali to pomaže u preciznjem rezanju donjeg oblika kapa i zapravo ta greška ne utječe jako na krajnji rezultat (tj. prepoznavanje kape).
I sad neočekivani zaključak: Rad u timu od 8 ljudi je prava umjetnost. Nikad nisam volio raditi u timu, ali to nekako progutam ako imam sa sobom razumne ljude, u ovom slučaju su to bili i iznimno pametni ljudi.
Sad par savjeta što ne raditi:
- Pokušajte izbjegavati velike timove (u praksi nemoguće)
- Ako voditelj tima nije izabran, izaberite nekoga tko zna voditi tim (nije nužno da bude i najveći stručnjak)
- Nemojte svi u timu biti "pametni" - svi rade sve a nitko ništa ne radi
- Što prije precizno definirajte zadatke: tko, što, gdje, kako
- Nemojte to raditi 3 dana prije roka
Subscribe to:
Posts (Atom)