Block Truncation Coding

Block Truncation Coding или BTC је тип алгоритама компресије са губитком података који се користи за црно-беле слике.Алгоритам дели слике у блоковима и после користи кфантификатор (енг. quantiser) у сваком нивоу док одржава исто значење и стандардну девијацију. Он је претходник популарне хардверске технике DXTC, иако је BTC први адаптиран на боју дуго пре него што је DXTC користио веома сличан приступ који се звао компресија боја ћелија (енг. Color Cell Compression).^[1] BTC је такође адаптиран на видео компресију. ^[2] BTC је такође адаптиран на видео компресију.

BTC је први пут представљен од стране O.R. Mitchell ^[3] на универзитету Пердју. Још једна варијанта BTC је Absolute Moment Block Truncation Coding или AMBTC, у којој уместо коришћења стандардне девијације у апсолутно првом тренутку је очуван заједно са значењем.AMBTC је рачунарски је једноставнији од BTC али такође даје типичне резултате у нижим Mean Squared Error (MSE).AMBTC је предложен од старане Maximo Lema и Robert Mitchell.^[4]

Користећи под блокове од 4х4 пиксела, дајући однос компресије 4:1 ако смо претходно користили 8-битне целобројне вредности током трансформације или при чувању. Вечи блокови омогућавају већу компресију ("a" and "b" су вредности које покривају већи број пиксела) међутим квалитет се такође смањује са повећањем величине блока због природе алгоритама.

BTC алгоритам је коришћен за компресију слике ровера ( Mars Pathfinder).^[5]

Процедура компресије

Пиксели слика су распоређени у блоковима који су обично димензија 4х4 пиксела. За сваки блок значење и стандардна девијација пиксела се рачуна, ове статистике се мењају од блока до блока. Вредности пиксела за сваки селектовани реконструисан или нови блок су изабрани тако да имају исто значење и стандардну девијацију за одговарајући блок оригиналне слике. На другом нивоу квантификације где добијамо компресију слике и она се изводи преко формуле:

$y(i,j)={\begin{cases}1,&x(i,j)>{\bar {x}}\\0,&x(i,j)\leq {\bar {x}}\end{cases}}$

Овде су $x(i,j)$ пиксели оригиналног блока и $y(i,j)$ су елементи компресованог блока. Ово може другачије да се објасни као: Ако је вредност пиксела већа од значаја онда се додељује вредност 1 у супротном 0. Вредности које су једнаке значају може им се доделити вредност 1 или 0 у зависности како је имплементиран алгоритам.

Овај 16-битни блок је сачуван или пренесен заједно са вредностима значаја и стандардне девијације. Реконструкција се добија са две вредности "a" и "b" које чувају вредност знацаја и стандардне девијације. Ове вредности можемо добити помоћу следећих формула:

$a={\bar {x}}-\sigma {\sqrt {\cfrac {q}{m-q}}}$

$b={\bar {x}}+\sigma {\sqrt {\cfrac {m-q}{q}}}$

Где је $\sigma$ ознака за стандардну девијацију,m је укупан број пиксела у блоку и q је број пиксела који је већи од значаја ( ${\bar {x}}$ ). Да реконструишемо слику или направимо њену апроксимацију, елементима којима је додељена вредност 0 добијају вредност вредности а и елементима који имају вредност 1 добијају вредност елементата b.

$x(i,j)={\begin{cases}a,&y(i,j)=0\\b,&y(i,j)=1\end{cases}}$

Ово показије да је алгоритам симетричан и да енкодер има већи део посла од декодера. Ово је из разлога сто декодер једноставно врши замену нула и јединица са одговарајућим елементима, док енкодер мора да изврши израчнавања за значење и стандардну девијацију за вредности које се користе.^[6]

Пример

Енкодер

Ако узмемо 4х4 блок од слике, и одрадимо тест слике:^[7]

${\begin{matrix}245&239&249&239\\245&245&239&235\\245&245&245&245\\245&235&235&239\end{matrix}}$

Као и сбаки мали блок слике ово изгледа веома досадно за рад јер су бројеви веома мали, ово је природа рада са компресијом са губитком података и како добро ради за слике. Сада морамо да срачунамо две вредности из ових података а то су значење и стандардна девијација. Значај може да се срачуна до 241.875, што не би требало да захтева додатног објашњавања. Стандардна девијација може са лакоћом да се израчуна до 4.36. Сада можемо да израчунамо вредности "a" и "b" користећи претходне једначине. Тако добијамо вредности 236.935 и 245.718. У последњој калкулацији ми морамо да вредностима у матрици доделимо вредности 0 и 1.

${\begin{matrix}1&0&1&0\\1&1&0&0\\1&1&1&1\\1&0&0&0\end{matrix}}$

Декодер

Сада декодер мора да замени вредности "a" и "b" са вредностима 0 и 1. И то ће нам дати следећи блок:

${\begin{matrix}245&236&245&236\\245&245&236&236\\245&245&245&245\\245&236&236&236\end{matrix}}$

Као сто смо видели блок је сада реконструисан са целобројним вредностима "a" и "b". Када пролазимо кроз теорију ово је добар тренутак да израчунамо стандардну девијацију и значај за реконструисани блок. Они би требало да буду једнаки са оригиналним значењем и стандардном девијацијом. Не треба заборавити да користимо целобројне вредности јер у супротном имаћемо више грешака кад је енкодер у питању.

Референце

^ 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. стр. 555. doi:10.1109/TENCON.1990.152671. ISBN 978-0-87942-556-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.
^ Delp, E.; Mitchell, O. (1979). „Image Compression Using Block Truncation Coding”. IEEE Transactions on Communications. 27 (9): 1335. doi:10.1109/TCOM.1979.1094560.
^ 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.
^ „Rover Camera Instrument Description”. NASA. Архивирано из оригинала 05. 03. 2016. г. Приступљено 9. 11. 2011.
^ Leis, J 2008, ELE4607 Advance Digital Communications, Module 3: Image & Video Coding. Lecture Slides, University of Southern Queensland, 2008.
^ Waterloo Fractal Coding and Analysis Group

[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. стр. 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. Архивирано из оригинала 05. 03. 2016. г. Приступљено 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]