Block Truncation Coding

S Vikipedije, slobodne enciklopedije

Block Truncation Coding ili BTC je tip algoritama kompresije sa gubitkom podataka koji se koristi za crno-bele slike.Algoritam deli slike u blokovima i posle koristi kfantifikator (eng. quantiser) u svakom nivou dok održava isto značenje i standardnu devijaciju. On je prethodnik popularne hardverske tehnike DXTC, iako je BTC prvi adaptiran na boju dugo pre nego što je DXTC koristio veoma sličan pristup koji se zvao kompresija boja ćelija (eng. Color Cell Compression).[1] BTC je takođe adaptiran na video kompresiju. [2] BTC je takođe adaptiran na video kompresiju.

BTC je prvi put predstavljen od strane O.R. Mitchell [3] na univerzitetu Perdju. Još jedna varijanta BTC je Absolute Moment Block Truncation Coding ili AMBTC, u kojoj umesto korišćenja standardne devijacije u apsolutno prvom trenutku je očuvan zajedno sa značenjem.AMBTC je računarski je jednostavniji od BTC ali takođe daje tipične rezultate u nižim Mean Squared Error (MSE).AMBTC je predložen od starane Maximo Lema i Robert Mitchell.[4]

Koristeći pod blokove od 4h4 piksela, dajući odnos kompresije 4:1 ako smo prethodno koristili 8-bitne celobrojne vrednosti tokom transformacije ili pri čuvanju. Veči blokovi omogućavaju veću kompresiju ("a" and "b" su vrednosti koje pokrivaju veći broj piksela) međutim kvalitet se takođe smanjuje sa povećanjem veličine bloka zbog prirode algoritama.

BTC algoritam je korišćen za kompresiju slike rovera ( Mars Pathfinder).[5]

Procedura kompresije[uredi | uredi izvor]

Pikseli slika su raspoređeni u blokovima koji su obično dimenzija 4h4 piksela. Za svaki blok značenje i standardna devijacija piksela se računa, ove statistike se menjaju od bloka do bloka. Vrednosti piksela za svaki selektovani rekonstruisan ili novi blok su izabrani tako da imaju isto značenje i standardnu devijaciju za odgovarajući blok originalne slike. Na drugom nivou kvantifikacije gde dobijamo kompresiju slike i ona se izvodi preko formule:


Ovde su pikseli originalnog bloka i su elementi kompresovanog bloka. Ovo može drugačije da se objasni kao: Ako je vrednost piksela veća od značaja onda se dodeljuje vrednost 1 u suprotnom 0. Vrednosti koje su jednake značaju može im se dodeliti vrednost 1 ili 0 u zavisnosti kako je implementiran algoritam.

Ovaj 16-bitni blok je sačuvan ili prenesen zajedno sa vrednostima značaja i standardne devijacije. Rekonstrukcija se dobija sa dve vrednosti "a" i "b" koje čuvaju vrednost znacaja i standardne devijacije. Ove vrednosti možemo dobiti pomoću sledećih formula:

Gde je oznaka za standardnu devijaciju,m je ukupan broj piksela u bloku i q je broj piksela koji je veći od značaja (). Da rekonstruišemo sliku ili napravimo njenu aproksimaciju, elementima kojima je dodeljena vrednost 0 dobijaju vrednost vrednosti a i elementima koji imaju vrednost 1 dobijaju vrednost elementata b.

Ovo pokazije da je algoritam simetričan i da enkoder ima veći deo posla od dekodera. Ovo je iz razloga sto dekoder jednostavno vrši zamenu nula i jedinica sa odgovarajućim elementima, dok enkoder mora da izvrši izračnavanja za značenje i standardnu devijaciju za vrednosti koje se koriste.[6]

Primer[uredi | uredi izvor]

Enkoder[uredi | uredi izvor]

Ako uzmemo 4h4 blok od slike, i odradimo test slike:[7]

Kao i sbaki mali blok slike ovo izgleda veoma dosadno za rad jer su brojevi veoma mali, ovo je priroda rada sa kompresijom sa gubitkom podataka i kako dobro radi za slike. Sada moramo da sračunamo dve vrednosti iz ovih podataka a to su značenje i standardna devijacija. Značaj može da se sračuna do 241.875, što ne bi trebalo da zahteva dodatnog objašnjavanja. Standardna devijacija može sa lakoćom da se izračuna do 4.36. Sada možemo da izračunamo vrednosti "a" i "b" koristeći prethodne jednačine. Tako dobijamo vrednosti 236.935 i 245.718. U poslednjoj kalkulaciji mi moramo da vrednostima u matrici dodelimo vrednosti 0 i 1.

Dekoder[uredi | uredi izvor]

Sada dekoder mora da zameni vrednosti "a" i "b" sa vrednostima 0 i 1. I to će nam dati sledeći blok:

Kao sto smo videli blok je sada rekonstruisan sa celobrojnim vrednostima "a" i "b". Kada prolazimo kroz teoriju ovo je dobar trenutak da izračunamo standardnu devijaciju i značaj za rekonstruisani blok. Oni bi trebalo da budu jednaki sa originalnim značenjem i standardnom devijacijom. Ne treba zaboraviti da koristimo celobrojne vrednosti jer u suprotnom imaćemo više grešaka kad je enkoder u pitanju.

Reference[uredi | uredi izvor]

Block Truncation Coding na Vikimedijinoj ostavi.
  1. ^ Liou, D. -M.; Huang, Y.; Reynolds, N. (1990). „A new microcomputer based imaging system with C/sup 3/ technique”. IEEE TENCON'90: 1990 IEEE Region 10 Conference on Computer and Communication Systems. Conference Proceedings. str. 555. doi:10.1109/TENCON.1990.152671. ISBN 978-0-87942-556-2. 
  2. ^ Healy, D.; Mitchell, O. (1981). „Digital Video Bandwidth Compression Using Block Truncation Coding”. IEEE Transactions on Communications. 29 (12): 1809. doi:10.1109/TCOM.1981.1094938. 
  3. ^ Delp, E.; Mitchell, O. (1979). „Image Compression Using Block Truncation Coding”. IEEE Transactions on Communications. 27 (9): 1335. doi:10.1109/TCOM.1979.1094560. 
  4. ^ Lema, M.; Mitchell, O. (1984). „Absolute Moment Block Truncation Coding and akhand Its Application to Color Images”. IEEE Transactions on Communications. 32 (10): 1148. doi:10.1109/TCOM.1984.1095973. 
  5. ^ „Rover Camera Instrument Description”. NASA. Arhivirano iz originala 05. 03. 2016. g. Pristupljeno 9. 11. 2011. 
  6. ^ Leis, J 2008, ELE4607 Advance Digital Communications, Module 3: Image & Video Coding. Lecture Slides, University of Southern Queensland, 2008.
  7. ^ Waterloo Fractal Coding and Analysis Group
Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Block_Truncation_Coding&oldid=26731051”