Block trunkeringskodning

Block Truncation Coding ( BTC ) är en typ av bildkomprimeringsteknik med förlust för gråskalebilder . Den delar upp originalbilderna i block och använder sedan en kvantiserare för att minska antalet grånivåer i varje block samtidigt som samma medelvärde och standardavvikelse bibehålls . Det är en tidig föregångare till den populära hårdvarutekniken DXTC , även om BTC-komprimeringsmetoden först anpassades till färg långt före DXTC med en mycket liknande metod som kallas Color Cell Compression . BTC har även anpassats till videokomprimering.

BTC föreslogs först av professorerna Mitchell och Delp vid Purdue University. En annan variant av BTC är Absolute Moment Block Truncation Coding eller AMBTC , där istället för att använda standardavvikelsen bevaras det första absoluta momentet tillsammans med medelvärdet. AMBTC är beräkningsmässigt enklare än BTC och resulterar också vanligtvis i ett lägre medelkvadratfel (MSE). AMBTC föreslogs av Maximo Lema och Robert Mitchell.

Att använda underblock på 4×4 pixlar ger ett komprimeringsförhållande på 4:1 förutsatt att 8-bitars heltalsvärden används under överföring eller lagring. Större block tillåter större komprimering ("a" och "b"-värden spridda över fler pixlar), men kvaliteten minskar också med ökningen av blockstorleken på grund av algoritmens natur.

BTC-algoritmen användes för att komprimera Mars Pathfinders roverbilder.

Kompressionsprocedur

En pixelbild är uppdelad i block med typiskt 4×4 pixlar. För varje block medelvärdet och standardavvikelsen för pixelvärdena; denna statistik ändras i allmänhet från block till block. Pixelvärdena som väljs för varje rekonstruerat, eller nytt, block väljs så att varje block i den BTC-komprimerade bilden kommer att ha (ungefär) samma medelvärde och standardavvikelse som motsvarande block i originalbilden. En tvånivåkvantisering på blocket är där vi får komprimeringen och utförs enligt följande:

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

Här är $x(i,j)$ pixelelement i det ursprungliga blocket och $y(i,j)$ är element i det komprimerade blocket. I ord kan detta förklaras som: Om ett pixelvärde är större än medelvärdet tilldelas det värdet "1", annars "0". Värden lika med medelvärdet kan ha antingen en "1" eller en "0" beroende på preferensen hos den person eller organisation som implementerar algoritmen.

Detta 16-bitars block lagras eller överförs tillsammans med värdena för medelvärde och standardavvikelse. Rekonstruktion görs med två värden "a" och "b" som bevarar medelvärdet och standardavvikelsen. Värdena för "a" och "b" kan beräknas enligt följande:

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

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

Där $\sigma$ är standardavvikelsen, m är det totala antalet pixlar i blocket och q är antalet pixlar större än medelvärdet ( ${\bar {x}}$ )

För att rekonstruera bilden, eller skapa dess approximation, ersätts element som tilldelats en 0 med värdet "a" och element som tilldelats en 1 ersätts med värdet "b".

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

Detta visar att algoritmen är asymmetrisk genom att kodaren har mycket mer att göra än avkodaren. Detta beror på att avkodaren helt enkelt ersätter 1:or och 0:or med det uppskattade värdet, medan kodaren också krävs för att beräkna medelvärdet, standardavvikelsen och de två värdena som ska användas.

Exempel

Encoder

Ta ett 4×4 block från en bild, i det här fallet bergstestbilden:

$&2429\4\5252&245 245\\245&235&235&239\end{matris}}}$

Liksom alla små block från en bild verkar detta ganska tråkigt att arbeta med eftersom siffrorna alla är ganska lika, detta är karaktären av förlustkomprimering och hur det kan fungera så bra för bilder. Nu måste vi beräkna två värden från dessa data, det vill säga medelvärdet och standardavvikelsen. Medelvärdet kan beräknas till 241,875, detta är en enkel beräkning som inte behöver behöva någon ytterligare förklaring. Standardavvikelsen beräknas enkelt till 4,36. Från detta kan värdena för "a" och "b" beräknas med hjälp av de föregående ekvationerna. De kommer ut att vara 236.935 respektive 245.718. Den sista beräkningen som behöver göras på kodningssidan är att ställa in matrisen att sända till 1:or och 0:or så att varje pixel kan överföras som en enda bit.

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

Avkodare

Nu på dekodersidan är allt vi behöver göra om att tilldela "a" och "b" värdena till 1 och 0 pixlar. Detta ger oss följande block:

$&2423&4\5245&2423 245\\245&236&236&236\end{matris}}}$

Som kan ses har blocket rekonstruerats med de två värdena "a" och "b" som heltal (eftersom bilder inte är definierade för att lagra flyttal). När man arbetar igenom teorin är detta en bra punkt för att beräkna medelvärdet och standardavvikelsen för det rekonstruerade blocket. De ska vara lika med det ursprungliga medelvärdet och standardavvikelsen. Kom ihåg att använda heltal, annars kommer mycket kvantiseringsfel att bli inblandade, eftersom vi tidigare kvantifierat allt till heltal i kodaren.

Se även

• Color Cell Compression (en nyare derivata av Block Truncation Coding)

externa länkar

• Media relaterade till Block Truncation Coding på Wikimedia Commons