Blokové zkrácení kódování - Block Truncation Coding

Blokové zkrácení kódování (BTC) je typ ztrátová komprese obrazu technika pro stupně šedi snímky. Rozdělí původní obrázky do bloků a poté pomocí kvantizátoru sníží jejich počet úrovně šedé v každém bloku při zachování stejné znamenat a standardní odchylka. Jedná se o raného předchůdce populárního hardwaru DXTC technika, ačkoli metoda komprese BTC byla nejprve přizpůsobena barvě dlouho před DXTC pomocí velmi podobného tzv. přístupu Komprese barevných buněk.[1] BTC byl také přizpůsoben kompresi videa.[2]

BTC poprvé navrhli profesoři Mitchell a Delp na Purdue University.[3] Další variace BTC je Kódování zkrácení absolutního momentu nebo AMBTC, ve kterém je namísto použití směrodatné odchylky zachován první absolutní moment spolu se střední hodnotou. AMBTC je výpočetně jednodušší než BTC a také obvykle vede k nižší střední kvadratické chybě (MSE). AMBTC navrhli Maximo Lema a Robert Mitchell.[4]

Použití dílčích bloků 4 × 4 pixelů poskytuje kompresní poměr 4: 1 za předpokladu, že se během přenosu nebo ukládání použijí 8bitové celočíselné hodnoty. Větší bloky umožňují větší kompresi (hodnoty „a“ ​​a „b“ rozložené na více pixelů), kvalita se však také snižuje s nárůstem velikosti bloku kvůli povaze algoritmu.

Pro kompresi byl použit algoritmus BTC Mars Pathfinder obrázky roveru.[5]

Postup komprese

A pixel obraz je rozdělen do bloků obvykle 4 × 4 pixelů. Pro každý blok Znamenat a Standardní odchylka z hodnot pixelů se počítá; tyto statistiky se obecně mění z bloku na blok. Hodnoty pixelů vybrané pro každý rekonstruovaný nebo nový blok jsou vybrány tak, aby každý blok komprimovaného obrazu BTC měl (přibližně) stejný průměr a směrodatnou odchylku jako odpovídající blok původního obrazu. Dvouúrovňová kvantizace na bloku je místo, kde získáme kompresi a provádí se následujícím způsobem:

Tady jsou pixelové prvky původního bloku a jsou prvky komprimovaného bloku. To lze vysvětlit slovy: Pokud je hodnota pixelu větší než střední hodnota, je jí přiřazena hodnota „1“, jinak „0“. Hodnoty rovné střední hodnotě mohou mít buď „1“ nebo „0“ v závislosti na preferencích osoby nebo organizace implementující algoritmus.

Tento 16bitový blok se ukládá nebo přenáší spolu s hodnotami střední a standardní odchylky. Rekonstrukce se provádí pomocí dvou hodnot „a“ a „b“, které zachovávají průměr a směrodatnou odchylku. Hodnoty „a“ ​​a „b“ lze vypočítat takto:

Kde je směrodatná odchylka, m je celkový počet pixelů v bloku a q je počet pixelů větší než průměr ()

Pro rekonstrukci obrazu nebo pro vytvoření jeho aproximace jsou prvky s přiřazenou 0 nahrazeny hodnotou „a“ a prvky s přiřazenou a 1 jsou nahrazeny hodnotou „b“.

To ukazuje, že algoritmus je asymetrický v tom, že kodér má mnohem více práce než dekodér. Důvodem je, že dekodér jednoduše nahrazuje jedničky a nuly odhadovanou hodnotou, zatímco kodér je také nutný pro výpočet střední hodnoty, standardní odchylky a dvou hodnot, které se mají použít.[6]

Příklad

Kodér

Vezměte z obrázku blok 4 × 4, v tomto případě horský testovací obrázek:[7]

Jako každý malý blok z obrázku se to zdá být docela nudné, protože čísla jsou docela podobná, taková je povaha ztrátové komprese a jak to může tak dobře fungovat pro obrázky. Nyní musíme z těchto dat vypočítat dvě hodnoty, tj. Střední a standardní odchylku. Průměr lze vypočítat na 241 875, jedná se o jednoduchý výpočet, který by neměl vyžadovat žádné další vysvětlení. Směrodatná odchylka se snadno vypočítá na 4,36. Z toho lze pomocí předchozích rovnic vypočítat hodnoty „a“ ​​a „b“. Vyšlo jim 236 935, respektive 245 718. Posledním výpočtem, který je třeba provést na straně kódování, je nastavit matici pro přenos na čísla 1 a 0, aby bylo možné přenášet každý pixel jako jeden bit.

Dekodér

Nyní na straně dekodéru vše, co musíme udělat, je znovu přiřadit hodnoty „a“ ​​a „b“ k 1 a 0 pixelům. Tím získáte následující blok:

Jak je vidět, blok byl rekonstruován se dvěma hodnotami „a“ a „b“ jako celá čísla (protože obrázky nejsou definovány pro ukládání čísel s plovoucí desetinnou čárkou). Při práci na teorii je to dobrý bod pro výpočet střední a standardní odchylky rekonstruovaného bloku. Měly by se rovnat původní střední hodnotě a směrodatné odchylce. Nezapomeňte použít celá čísla, jinak bude docházet k velké kvantizační chybě, protože jsme dříve kvantovali vše na celá čísla v kodéru.

Viz také

Reference

  1. ^ Liou, D.-M .; Huang, Y .; Reynolds, N. (1990). "Nový zobrazovací systém založený na mikropočítačích s technikou C / sup 3 /". Konference IEEE TENCON'90: 1990 IEEE Region 10 o počítačových a komunikačních systémech. Sborník z konference. p. 555. doi:10.1109 / TENCON.1990.152671. ISBN  0-87942-556-3.
  2. ^ Healy, D .; Mitchell, O. (1981). "Komprese šířky pásma digitálního videa pomocí blokového zkrácení". Transakce IEEE na komunikaci. 29 (12): 1809. Bibcode:1981 ITCom..29.1809H. doi:10.1109 / TCOM.1981.1094938.
  3. ^ Delp, E .; Mitchell, O. (1979). Msgstr "Komprese obrazu pomocí blokového zkrácení". Transakce IEEE na komunikaci. 27 (9): 1335. Bibcode:1979 STIA ... 8011525D. doi:10.1109 / TCOM.1979.1094560.
  4. ^ Lema, M .; Mitchell, O. (1984). "Kódování zkrácení bloku absolutního momentu a jeho aplikace na barevné obrázky". Transakce IEEE na komunikaci. 32 (10): 1148. doi:10.1109 / TCOM.1984.1095973.
  5. ^ „Popis kamerového přístroje Rover“. NASA. Citováno 2011-11-09.
  6. ^ Leis, J 2008, ELE4607 Advance Digital Communications, modul 3: kódování obrazu a videa. Prezentace přednášek, University of Southern Queensland, 2008.
  7. ^ Waterloo Fractal Coding and Analysis Group

externí odkazy