\documentclass[11pt,a4paper]{scrreprt}
\usepackage{fullpage}
\usepackage{mathptmx}
\usepackage[scaled=.92]{helvet}
\usepackage{courier}
\usepackage[T1]{fontenc}
\usepackage{microtype}
\usepackage[bookmarks=true,colorlinks=true,linkcolor=black,urlcolor=black]{hyperref}
\usepackage{booktabs}
\usepackage{longtable}
\usepackage{amsmath}
\usepackage{mathtools}
\usepackage{tabularx}
\usepackage{tikz}
\usepackage{enumitem}

\title{The M4x4 Image Format: \\ Bitstream Format and Decoding Specification}
\author{Martin J. Fiedler \\ 
\href{mailto:keyj-m4x4@emphy.de}{\nolinkurl{keyj-m4x4@emphy.de}}}
\date{DRAFT \\ Revision 0 \\ July 2011}

\newenvironment{syntab}[1]{
    \begin{center}\begin{tabular}{| p{9cm} | p{1.5cm} | p{2.5cm} |} \hline
    \hspace*{0ex} #1 \{ & \textbf{Type} & \textbf{Partition}
}{
    \\ \} & &
    \\ \hline \end{tabular}\end{center}
}\newcommand{\synline}[1] {\\ \hspace*{#1}}
\newenvironment{ul}{\begin{itemize}\setlength{\itemsep}{0pt}}{\end{itemize}}
\newenvironment{dl}{\begin{description}[font=\normalfont\bfseries]\setlength{\itemsep}{0pt}}{\end{description}}

\widowpenalty=10000
\clubpenalty=10000
\setcounter{secnumdepth}{3}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1ex}

\begin{document}

\maketitle

\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Introduction}
M4x4 is a file format for still images. Similar to JPEG, it uses lossy compression specialized for natural scenes, e.g. photos. However, it uses a more modern compression algorithm loosely based on the H.264 video compression scheme which gives it a slight gain in compression efficiency while requiring roughly the same amount of computation as JPEG. The following features are supported:
\begin{ul}
\item supports any image size up to $2^{31}-1$ pixels
\item support a color depth of 8~bits per component
\item compression of grayscale and RGB color images
\item RGB images are compressed in a color space which decouples luminance information from chrominance to improve compression efficiency
\item chrominance information can be sub-sampled to further increase efficiency
\item supports an alpha (transparency) channel, including lossy compression
\item supports adaptive quantization and regions of interest
\item uses a separable integer 4x4 transform
\item uses an intra prediction scheme based on blocks of 4x4 pixels
\item uses an in-loop deblocking filter
\item makes heavy use of data partitioning
\item compresses data partitions using Huffman codes
\item expandable bitstream format
\item supports inclusion of user-specified metadata
\item computable in pure 16-/32-bit integer arithmetic, requiring no divisions
\end{ul}

\section{Format Overview}
An M4x4 image is encoded as a set of \emph{planes}. Each color component is assigned a plane of its own. Every image contains at least the \emph{luminance} plane. Color images additionally contain two \emph{chrominance} planes. RGB images are converted to a modified YCgCo color space prior to encoding. This process separates the luminance and the chrominance information and puts each into a plane of its own. In addition, the chrominance planes can be encoded at a lower resolution by downsampling them horizontally or vertically by a factor of 2, 4 or 8. After decoding these planes at the decoder, the chrominance planes are upsampled again and the luminance and chrominance information is combined and tranformed into the original RGB color space.

Unlike in JPEG, each plane is encoded independently. There is no macroblock structure. Each plane is simply encoded as a series of blocks of 4x4 pixels each.

For each block, a process called \emph{intra prediction} is performed first. Intra prediction attempts to extrapolate pixels from the surrounding blocks into the current block by repeating and mixing them. Only the difference between the prediction and the actual image content, called the \emph{residual}, is then encoded. Unlike H.264, which has 9 different intra prediction modes from which the encoder can select on a per-block basis, M4x4 only uses 4 modes, which are automatically chosen based on the block's surroundings.

The residual is transformed by H.264's two-dimensional separable integer transform. The \emph{transform coefficients} are measurements for the \emph{spatial frequencies} of the residual block. The coefficients are then \emph{quantized}. Like in H.264, quantization not only acts as a means of controlling visual quality of the block, but it is also required to properly scale the transform coefficients. Quantization is controlled by a \emph{quantization parameter}, or \emph{QP} for short, that specifies the desired level of quality on a logarithmic scale. It can change for every block and is encoded using a run-length scheme.

The \emph{quantized transform coefficients} are reordered using a \emph{zig-zag scan pattern} which puts the coefficients into an order better suitable for encoding. The encoding process itself is again very similar to H.264: The total number of non-zero coefficients, the number of zeros in the coefficient scan and the number of ones at the end of the coefficient scan, the absolute values (\emph{levels}) of the remaining coefficients and the signs of all coefficients are encoded separarely to make best use of the redundancy in this kind of data.

Finally, after encoding a block but before encoding the next block, a \emph{deblocking filter} is applied to the upper and left edge of the block. This smoothes out blocking artifacts where they would be visible while trying to retain as much detail as possible.

Images can have transparency information associated to them. This information is encoded as a fourth plane, the \emph{alpha} plane. If such a plane is present, the encoding and decoding procedures differ slightly. The algorithm leverages the fact that alpha information typically contains large regions that are either completely opaque or completely transparent, whereas in most cases only a small part of an image contains other alpha values. A so-called \emph{alpha tree} is encoded to put each 4x4 pixel block of the image in one of the aforementioned three categories: transparent, opaque, or \emph{boundary}, the latter being the case for blocks that are not either completely transparent or completely opaque. On the decoder side, the alpha tree is decoded first, followed by the alpha plane and then the one or three color planes. During the encoding of these planes, all blocks not containing meaningful information are skipped and not encoded at all: For the alpha plane, this is the case for all transparent or opaque blocks (leaving only the boundary blocks left to be encoded), and for the color planes, this is the case for all transparent blocks, as the color information contained therein would not be visible anyway.

The data generated while encoding an image is split up into \emph{partitions}. The header, alpha tree, QP changes and coefficient signs are all encoded in different partitions. The total coefficient counts, total zero counts, trailing one counts and coefficient levels are even spread across up to 16 partitions each to leverage more similarities in the encoded data.

The data inside the partitions can either be stored uncompressed in the resulting stream, allocating one byte per value. This format is not very efficient in itself, but due to the partitioning, similar values are likely to be grouped in close proximity to each other, facilitating compression using standard algorithms like Deflate or LZMA.

To achieve a higher compression ratio without the help of external algorithms, partitions can also be compressed by the M4x4 algorithm itself. In this case, each partition can be encoded either with a Huffman code that is optimally tailored to the distribution of the values stored in the partition or with a more compact literal representation using only as much bits as are really required by the data in the partition.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Definitions and Conventions}
The key words \emph{``must''}, \emph{``must not''}, \emph{``required''}, \emph{``shall''}, \emph{``shall not''}, \emph{``should''}, \emph{``should not''}, \emph{``recommended''}, \emph{``may''} and \emph{``optional''} in this document are to be interpreted as described in IETF Standard / Best Current Practice RFC~2119.

\section{Definitions}
\begin{dl}
\item[alpha plane] The plane containing alpha (i.e. transparency/opacity) data.
\item[available block] A block is called \emph{available} if it is present in a color plane. Available blocks are eligible for filtering.
\item[block] A group of 4x4 samples.
\item[chrominance] Two values describing the hue and saturation of a color.
\item[color plane] One of the planes containing visible color (i.e. luminance or chrominance) data.
\item[intra prediction] The process used to predict the sample values for a 4x4 block based on the samples of surrounding blocks.
\item[LSB] Abbreviation for the \emph{least significant bits} of a binary coded data value.
\item[luminance] A measurement for the perceived \emph{lightness} of a color.
\item[MSB] Abbreviation for the \emph{most significant bits} of a binary coded data value.
\item[plane] A two-dimensional array of samples.
\item[prediction] The process of estimating a value or set of values for a block based on the values of the surrounding blocks.
\item[QP] Abbreviation for \emph{quantization parameter}.
\item[quantization parameter] A scalar integer value in the rage from 0 to 127 inclusive that specifies the amount of quantization applied to a block.
\item[sample] A single pixel inside a plane.
\item[TC] Abbreviation for \emph{TotalCoeff}, the total number of non-zero quantized transform coefficients in a block.
\item[user data] A user-defined block of data whose contents are not described as part of this specification.
\item[valid block] A block is called \emph{valid} if it is coded, i.e. it has a QP and a TotalCoeff value associated with it. Valid blocks are eligible for QP or TotalCoeff prediction as well as intra prediction.
\end{dl}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Operators and Functions}
\begin{tabularx}{\textwidth}{l X}
\multicolumn{2}{l}{\sffamily\bfseries\large Arithmetic operators}
\\ $+$ & Addition.
\\ $-$ & Subtraction (as a binary operator) or negation (as a unary operator).
\\ $\times$ & Multiplication.
\\ $/$ & Division with rounding towards zero.
\\ $\operatorname{abs}$ & $ \operatorname{abs}(x) = \begin{cases} x & \text{if } x \geq 0 \\ -x & \text{if } x < 0 \end{cases} $
\vspace{4pt} \\ \multicolumn{2}{l}{\sffamily\bfseries\large Logical operators}
\\ $\mid\mid$ & Logical OR.
\\ $\&\&$ & Logical AND.
\\ $!$ & Logical NOT.
\vspace{4pt} \\ \multicolumn{2}{l}{\sffamily\bfseries\large Bitwise operators}
\\ $\mid\mid$ & Bitwise OR.
\\ $\&\&$ & Bitwise AND.
\\ $>>$ & Shift right with sign extension. $a >> b$ is identical to a division $a \div 2^b$ with rounding towards negative infinity.
\\ $<<$ & Shift left with zero fill. $a << b$ is identical to a multiplication $a \times 2^b$.
\vspace{4pt} \\ \multicolumn{2}{l}{\sffamily\bfseries\large Relational operators}
\\ $>$ & Greater than.
\\ $>=$ & Greater than or equal to.
\\ $<$ & Less than.
\\ $<=$ & Less than or equal to.
\\ $==$ & Equal to.
\\ $!=$ & Not equal to.
\vspace{4pt} \\ \multicolumn{2}{l}{\sffamily\bfseries\large Assignment operators}
\\ $=$ & Assignment.
\vspace{4pt} \\ \multicolumn{2}{l}{\sffamily\bfseries\large Functions}
\\ $\operatorname{Clip3}$ & $ \operatorname{Clip3}(a, b, x) = \begin{cases} a & \text{if } x < a \\ b & \text{if } x > b \\ x & \text{otherwise} \end{cases} $
\\ $\operatorname{Clip2}$ & $ \operatorname{Clip2}(b, x) = \operatorname{Clip3}(0, b, x) $
\\ $\operatorname{Clip1}$ & $ \operatorname{Clip1}(x) = \operatorname{Clip3}(0, 255, x) $
\\ $\operatorname{SignComb}$ & $\operatorname{SignComb}(s, a) = \begin{cases} a & \text{if } s \,==\, 0 \\ -a & \text{if } s \;\operatorname{!=}\; 0 \end{cases} $
\end{tabularx}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Bitstream Conventions}
A M4x4 bitstream is composed of multiple \emph{partitions}. Each partition contains of a series of bytes, i.e. 8-bit unsigned integer values. A partition can be empty.

\subsection{Partitions}
The partitions are stored in a particular order which is specified in Table~\ref{parttab}. Each partition or group of partitions is assigned a mnemonic name which is used throughout this specification. Note that some partitions are actually arrays of partitions, some of which use zero-based indexes and other use one-based indexes.
\begin{table}[h!]
\caption{List of partitions with according mnemonic names}
\label{parttab}
\begin{center}\begin{tabular}{| c | l |} \hline
\textbf{Index} & \textbf{Partition name}
\\ \hline 1 & Header
\\ \hline 2 & LSBs
\\ \hline 3 & Signs
\\ \hline 4 & CompressedData
\\ \hline 5 & AlphaTree
\\ \hline 6{\ldots}22 & TotalCoeff[0{\ldots}16]
\\ \hline 23{\ldots}38 & TrailingOnes[1{\ldots}16]
\\ \hline 39{\ldots}53 & TotalZeros[1{\ldots}15]
\\ \hline 54{\ldots}68 & CoeffRun[1{\ldots}15]
\\ \hline 69{\ldots}84 & CoeffLevel[0{\ldots}15]
\\ \hline 85 & QP\_Run
\\ \hline 86 & QP\_Delta
\\ \hline \end{tabular}\end{center}
\end{table}

\subsection{Bit Orientation}
All partitions contain byte-oriented data, with the exception of the CompressedData and Signs partitions. These partitions contain bit-oriented data, with bits being read from the bytes in the partition starting with the most-significant bit. If a bit-oriented partition contains a number of bits not divisible by 8, the remaining bits in the last byte shall be ignored.

In the CompressedData partition, multiple bits may be combined into longer syntax elements. In this case, the bits read are combined into the value starting with the most-significant bit.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Syntax tables}
This specification uses special tables to specify the syntax of the bitstream and the parsing processes to decode it.

\subsection{Process specification pseudo-code}
The first column of the syntax tables contains a pseudo-code representation of the parsing processes. The following constructs are used to express these processes:
\begin{longtable}{| l | p{10cm} |} \hline
\parbox[t]{4cm}{
process\_name() \{ \\
\hspace*{3ex} \textbf{syntax\_element} \\
\hspace*{3ex} \ldots \\
\}}
& Defines a process called \emph{process\_name} in which a value with the mnemonic name \emph{syntax\_element} is parsed from the bitstream, possibly followed by other syntax elements or constructs.
\\ \hline
\parbox[t]{4cm}{
if (\emph{condition}) \{ \\
\hspace*{3ex} \textbf{syntax\_element} \\
\hspace*{3ex} \ldots \\
\}}
& Executes the block enclosed in curly braces only if \emph{condition} is true.
\\ \hline
\parbox[t]{4cm}{
if (\emph{condition}) \{ \\
\hspace*{3ex} \textbf{syntax\_element} \\
\hspace*{3ex} \ldots \\
\} else \{ \\
\hspace*{3ex} \textbf{syntax\_element} \\
\hspace*{3ex} \ldots \\
\}}
& Executes the first block if \emph{condition} is true or the second block otherwise.
\\ \hline
\parbox[t]{4cm}{
while (\emph{condition}) \{ \\
\hspace*{3ex} \textbf{syntax\_element} \\
\hspace*{3ex} \ldots \\
\}}
& If \emph{condition} is true, the block is executed. This repeats until \emph{condition} is not true.
\\ \hline
\parbox[t]{4cm}{
do \{ \\
\hspace*{3ex} \textbf{syntax\_element} \\
\hspace*{3ex} \ldots \\
\} while (\emph{condition})}
& Repeats execution at least once until \emph{condition} is not true.
\\ \hline
\parbox[t]{4cm}{
for ($\text{i} = \text{m} \ldots \text{n}$) \{ \\
\hspace*{3ex} \textbf{syntax\_element} \\
\hspace*{3ex} \ldots \\
\}}
& Repeats execution $n - m + 1$ times, assigning the current loop count to a variable $i$.
\\ \hline
\parbox[t]{4cm}{
do \{ \\
\hspace*{3ex} \ldots \\
\hspace*{3ex} continue \\
\hspace*{3ex} \ldots \\
\} while (\emph{condition})}
& Continues execution of the next repetition of the nearest while or do-while loop.
\\ \hline
\parbox[t]{4cm}{
do \{ \\
\hspace*{3ex} \ldots \\
\hspace*{3ex} break \\
\hspace*{3ex} \ldots \\
\} while (\emph{condition})}
& Continues execution after the end of the nearest while or do-while loop.
\\ \hline
\parbox[t]{4cm}{
process\_name() \{ \\
\hspace*{3ex} \ldots \\
\hspace*{3ex} return($\text{i}$) \\
\}}
& Defines a process that returns a value. In this example, the value of the variable $i$ is returned.
\\ \hline
\end{longtable}

\subsection{Type and partition specifiers}
In all lines describing a specific syntax element, the other two columns of the syntax tables are used to specify the \emph{data type} of the syntax element and the mnemonic name of \emph{partition} where the syntax element has to be read from.

\pagebreak[1]
The following type specifiers can appear in the second column of the tables:
\begin{longtable}{ l l}
Byte & An unsigned integer composed of a single byte. \\
SByte & A signed integer composed of a single byte in two's complement notation. \\
Bytes($n$) & A sequence of $n$ consecutive bytes. \\
Bit & A single bit. \\
Bits($n$) & An unsigned integer composed of $n$ bits. \\
Huffman & A huffman codeword (context-dependent). \\
VLI & A variable-length integer, as specified in section~\ref{vlidec}. \\
Level & A level code, as specified in section~\ref{leveldec}.
\end{longtable}

The partition names that can appear in the third column of the tables are specified in Table~\ref{parttab}. A special value labeled ``\emph{(current)}'' is used in places where the partition to read from depends on the partition the calling process wants to read the syntax element from.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Value Encodings}
\subsection{Variable-Length Integer Decoding\label{vlidec}}
To encode values larger than 255 that don't fit into a single byte, M4x4 uses a scheme valled \emph{variable-length integer code}, abbreviated \emph{VLI}. In this scheme, the 7 LSBs of an 8-bit byte are used to transport data bits while the MSB of each byte indicates whether another byte follows or not. This way, integer values of arbitary length can be encoded. \\
The decoding process for VLI-coded values is described in decode\_vli().

\begin{syntab}{decode\_vli()}
\synline{3ex} $\text{value} = 0$ & &
\synline{3ex} do \{ & &
\synline{6ex} \textbf{vli\_byte} & Byte & \emph{(current)}
\synline{6ex} $\text{value} = (\text{value} \,<<\, 7) + (\text{vli\_byte} \,\&\, \text{0x7F})$ & &
\synline{3ex} \} while ($(\text{vli\_byte} \,\&\, \text{0x80}) \,!=\, 0$) & &
\synline{3ex} return($\text{value}$) & &
\end{syntab}

\subsection{Level Decoding\label{leveldec}}
Transform coefficient levels as well as QP run levels are encoded using a different scheme. Small values of 239 and below are directly encoded. Larger values are encoded as two bytes, where the second byte is not stored in the partition of the encoded level, but in the ``LSBs'' partition. Very large values of 3840 and above are encoded using VLIs. \\
The decoding process for level-coded values is described in decode\_level().

\begin{syntab}{decode\_level()}
\synline{3ex} \textbf{level\_code} & Byte & \emph{(current)}
\synline{3ex} if ($\text{level\_code} < \text{0xF0}$) \{ & &
\synline{6ex} return($\text{level\_code}$) & &
\synline{3ex} \} else if ($\text{level\_code} \,!=\, \text{0xFF}$) \{ & &
\synline{6ex} $\text{level\_offset} = (\text{level\_code} \,\&\, \text{0x0F}) \,<<\, 8$ & &
\synline{6ex} \textbf{level\_lsbs} & Byte & LSBs
\synline{6ex} return($\text{0xF0} + \text{level\_offset} + \text{level\_lsbs}$) & &
\synline{3ex} \} else \{ & &
\synline{6ex} \textbf{level\_vli} & VLI & LSBs
\synline{6ex} return($\text{0xF00} + \text{level\_vli}$) & &
\synline{3ex} \} & &
\end{syntab}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Block Status, Relationships and Prediction}

\subsection{Block Availability and Validity\label{avail}}
Throughout this specification, the terms \emph{available} and \emph{valid} are used for blocks with the following meanings:
\begin{ul}
\item Blocks outside of a plane are neither available nor valid.
\item Inside an alpha plane,
      \begin{ul}
      \item Every block is available.
      \item Only blocks marked as boundary blocks are valid.
      \end{ul}
\item Inside a color plane,
      \begin{ul}
      \item If the image contains alpha information,
            \begin{ul}
            \item Blocks marked as transparent are neither available nor valid,
            \item All other blocks are both available and valid.
            \end{ul}
      \item If the image does not contain alpha information, all blocks are both available and valid.
      \end{ul}
\end{ul}

\subsection{Neighbor Block Positions and Names\label{neighbors}}
\definecolor{Cdecoded}{gray}{0.95}
\definecolor{Ccurrent}{gray}{0.75}
The following figure illustrates the surroundings of the currently decoded block. The light shaded blocks have already been decoded, the dark shaded block is the current block.
\begin{center}\begin{tikzpicture}
\shade[inner color=Cdecoded,outer color=white] (-2.5,1.5) rectangle (-1.5,2.5);
\shade[inner color=Cdecoded,outer color=white] (1.5,1.5) rectangle (2.5,2.5);
\shade[bottom color=Cdecoded,top color=white] (-2,2) rectangle (2,2.5);
\shade[right color=Cdecoded,left color=white] (-2.5,0) rectangle (-2,2);
\shade[left color=Cdecoded,right color=white] (2,0) rectangle (2.5,2);
\fill[Cdecoded] (-2,1) rectangle(2,2);
\fill[Cdecoded] (-2,0) rectangle(0,1);
\fill[Ccurrent] (0,0) rectangle (1,1);
\draw[step=1] (-2.5,-0.5) grid (2.5,2.5);
\draw (0.5,0.5) node {C};
\draw (-0.5,0.5) node {L};
\draw (0.5,1.5) node {T};
\draw (-0.5,1.5) node {LT};
\end{tikzpicture}\end{center}
The currently decoded block is denoted with \emph{C}. The immediate left neighbor block is called \emph{L}, the immediate upper neighbor block is \emph{T}, and the upper-left neighbor block is called \emph{LT}.

\subsection{QP and TC prediction\label{modepred}}
During decoding, the current quantization parameter (QP) and the expected number of coefficients (TotalCoeff, TC) for a block are predicted using the QP/TC values from the surrounding blocks.

This process uses the neighbor names specified in section~\ref{neighbors}. $X_{L}$, $X_{T}$ and $X_{LT}$ denote the QP or TC values of the surrounding blocks.

\begin{ul}
\item If none of L, T and LT is valid, a default value is used as the predictor:
      \begin{ul}
      \item The default QP is 32.
      \item The default TotalCoeff value is zero.
      \end{ul}
\item If LT is valid, but L and T are not, $X_{LT}$ is used as the predictor.
\item If L is valid, but T is not, $X_{L}$ is used as the predictor.
\item If T is valid, but L is not, $X_{T}$ is used as the predictor.
\item If L and T are valid, but LT is not, $(X_{L} + X_{T} + 1) \,>>\, 1$ is used as the predictor.
\item If all of L, T and LT are valid, an intermediate value is computed:
\[ \Delta = \operatorname{abs}(X_{L} - X_{LT}) - \operatorname{abs}(X_{T} - X_{LT}) \] Then, the following value is used as the predictor:
$\begin{cases}
X_{L} & \text{if } \Delta > 0 \\
(X_{L} + X_{T} + 1) \,>>\, 1 & \text{if } \Delta == 0 \\
X_{T} & \text{if } \Delta < 0 \\
\end{cases} $
\end{ul}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\chapter{Image Decoding and Reconstruction\label{decode}}

\section{Bitstream Header Decoding}

\subsection{Bitstream Header Syntax and Semantics}
The general structure of an M4x4 stream header is as follows:
\begin{syntab}{m4x4\_header()}
\synline{3ex} \textbf{format\_identifier} & Bytes(4) & Header
\synline{3ex} do \{ & &
\synline{6ex} \textbf{user\_data\_size} & VLI & Header
\synline{6ex} for ($\text{i} = 0 \ldots \text{user\_data\_size} - 1$) \{ & &
\synline{9ex} \textbf{user\_data\_byte}[$\text{i}$] & Byte & Header
\synline{6ex} \} & &
\synline{3ex} \} while ($\text{user\_data\_size} \,!=\, 0$) & &
\synline{3ex} \textbf{format\_flags} & VLI & Header
\synline{3ex} \textbf{image\_width} & VLI & Header
\synline{3ex} \textbf{image\_height} & VLI & Header
\synline{3ex} if (color\_flag) \{ & &
\synline{6ex} \textbf{chroma\_subsample\_code} & Byte & Header
\synline{3ex} \} & &
\synline{3ex} \textbf{deblock\_alpha\_offset} & SByte & Header
\synline{3ex} \textbf{deblock\_beta\_offset} & SByte & Header
\synline{3ex} for ($\text{i} = 1 \ldots 86$) \{ & &
\synline{6ex} if (partition\_is\_present($\text{i}$)) \{ & &
\synline{9ex} \textbf{partition\_size}[$\text{i}$] & VLI & Header
\synline{6ex} \} & &
\synline{3ex} \} & &
\end{syntab}

\pagebreak[1]
The following syntax elements are present in the header:
\begin{dl}
\item[format\_identifier] A four-byte syntax element equal to the ASCII string ``M4x4'', i.e. 0x4D 0x34 0x78 0x34 in hexadecimal notation.
\item[user\_data\_size] The number of bytes in the following user data block. An M4x4 stream can contain an arbitrarily long sequence of user data blocks in its header, terminated by a value of user\_data\_size equal to zero.
\item[user\_data\_byte] The payload of a user data block. The syntax of this payload is user-defined and not part of this specification.
\item[format\_flags] An integer value that is interpreted as a bitfield containing flags that specify the used features in the bitstream. See section~\ref{format-flags} below for a detailed description of these flags.
\item[image\_width] The width of the decoded image, in pixels.
\item[image\_height] The height of the decoded image, in pixels.
\item[chroma\_subsample\_code] An 8-bit code consisting of two 4-bit fields describing the chrominance subsampling factors. The horizontal subsampling factor is stored in the upper 4 bits of the code, the vertical subsampling factor is stored in the lower 4 bits of the code. Only values of 1, 2, 4 and 8 are allowed for each of these fields, where 1 means no subsampling.
\item[deblock\_alpha\_offset] A parameter used to control the intensity of the deblocking filter.
\item[deblock\_beta\_offset] A parameter used to control the intensity of the deblocking filter.
\item[partition\_size] An array of values that describe the uncompressed size of each partition, in bytes.
\end{dl}

image\_width and image\_height must always be greater than zero. If alpha\_flag is set in the format flags, at least one of image\_width and image\_height must also be greater than 4.

\pagebreak[1]
\subsection{Format Flags\label{format-flags}}
The following flags are contained in the bits of the format\_flags syntax element, where bit 0 is the least significant bit:
\begin{center}\begin{tabular}{| c | l |}\hline
\textbf{Bit} & \textbf{Flag}
\\ \hline 0 & alpha\_flag
\\ \hline 1 & color\_flag
\\ \hline 2 & compression\_disable\_flag
\\ \hline\end{tabular}\end{center}
If any of the other bits is set, the bitstream is not compliant with this version of the M4x4 specification and can not be decoded properly.

\pagebreak[1]
The meaning of the format flags is as follows:
\begin{dl}
\item[alpha\_flag] Indicates that the image contains an alpha plane.
\item[color\_flag] Indicates that the image contains two chrominance planes in addition to the luminance plane.
\item[compression\_disable\_flag] Indicates that the bitstream data is not compressed, i.e. all partitions are stored as-is. By default, most partitions are compressed using Huffman coding.
\end{dl}

\pagebreak[1]
\subsection{Partition Size Decoding}
At the end of the header section, an array of VLIs containing the uncompressed sizes (in bytes) of all following partitions is to be decoded. The order of the sizes is specified in Table~\ref{parttab}. For partition arrays, the sizes of all partitions in the array are stored in ascending index order. The following modifications apply:
\begin{ul}
\item The size of the Header partition is not encoded in the bitstream. Instead, it is generated internally in the decoder and is equal to the bitstream position after decoding all partition sizes in the Header partition.
\item The size of the CompressedData partition is not encoded in the bitstream.
      \begin{ul}
      \item If compression\_disable\_flag is not set, the size of the CompressedData partition is unspecified. In this case, the CompressedData partition consists of all data following in the compressed stream after the Signs partition.
      \item If compression\_disable\_flag is set, the CompressedData partition size is set to zero.
      \end{ul}
\item If alpha\_flag is not set, the size of the AlphaTree partition is not encoded in the bitstream and is set to zero.
\item The sizes of the TotalZeros partitions are not encoded in the bitstream. They are set to be equal to the sizes of the TrailingOnes partitions.
\end{ul}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Partition Data Decoding}
The data of the other partitions immediately follows the last byte of the Header partition. In an uncompressed bitstream (with compression\_disable\_flag set), the partitions are simply appended one after another in the order specified in Table~\ref{parttab}. Partitions with a size of zero are omitted. This scheme can be seen in the upper part of Figure~\ref{bitstream}.

\begin{figure}[h!]
\caption{General Bitstream Layout}
\label{bitstream}
\begin{center}\begin{tikzpicture}
\draw (0.7,4.5) node {\textbf{Uncompressed Bitstream}};
\draw (2.4,4.1) -- (-3.8,4.1) -- (-3.8,3.4) -- (2.4,3.4);
\draw (2.9,4.1) -- (5.2,4.1) -- (5.2,3.4) -- (2.9,3.4);
\draw (-2.4,3.4) -- (-2.4,4.1);
\draw (-1.2,3.4) -- (-1.2,4.1);
\draw (0,3.4) -- (0,4.1);
\draw (1.9,3.4) -- (1.9,4.1);
\draw (3.4,3.4) -- (3.4,4.1);
\draw (-3.1,4) node[anchor=north] {Header};
\draw (-1.8,4) node[anchor=north] {LSBs};
\draw (-0.6,4) node[anchor=north] {Signs};
\draw (0.95,4) node[anchor=north] {AlphaTree};
\draw (2.65,3.7) node {\ldots};
\draw (4.3,4) node[anchor=north] {QP\_Delta};
\draw (0.7,2.5) node {\textbf{Compressed Bitstream}};
\draw (-3.8,1.4) rectangle (3,2.1);
\draw (-2.4,1.4) -- (-2.4,2.1);
\draw (-1.2,1.4) -- (-1.2,2.1);
\draw (0,1.4) -- (0,2.1);
\draw (-3.1,2) node[anchor=north] {Header};
\draw (-1.8,2) node[anchor=north] {LSBs};
\draw (-0.6,2) node[anchor=north] {Signs};
\draw (1.5,2) node[anchor=north] {CompressedData};
\draw (2.65,0.3) node {\ldots};
\draw (2.4,0.7) -- (0,0.7) -- (0,0) -- (2.4,0);
\draw (2.9,0.7) -- (5.2,0.7) -- (5.2,0) -- (2.9,0);
\draw (1.9,0) -- (1.9,0.7);
\draw (3.4,0) -- (3.4,0.7);
\draw (0.95,0.6) node[anchor=north] {AlphaTree};
\draw (4.3,0.6) node[anchor=north] {QP\_Delta};
\draw[dotted] (0,0.7) -- (0,1.4);
\draw[dotted] (5.2,0.7) -- (3,1.4);
\end{tikzpicture}\end{center}\end{figure}

In a compressed bitstream (with compression\_disable\_flag not set), only the LSBs and Signs partition are stored without compression. All other partitions, however, are combined into a single compressed bitstream in the CompressedData partition which, in turn, is stored after the Signs partition. The order of the partitions inside the CompressedData sub-bitstream is the same as in Table~\ref{parttab}. Each partition is decoded independently. There is no space or alignment whatsoever between partitions; if the compressed data for a partition ends in the middle of a byte, the compressed data for the next partition continues directly with the next bit of that byte. Partitions with a size of zero are skipped completely, i.e. no bits are encoded for them.

Note that there is no way to determine the compressed size of a partition or even for the complete CompressedData partition. Only the uncompressed sizes are specified in the Header partition.

\pagebreak[1]
\subsection{Huffman-compressed Partition Decoding}
The decoding process for a compressed partition is specified by compressed\_partition(part\_idx).
\begin{syntab}{compressed\_partition(part\_idx)}
\synline{3ex} \textbf{compression\_flag} & Bit & CompressedData
\synline{3ex} if ($\text{compression\_flag}$) \{ & &
\synline{6ex} huffman\_codebook() & & CompressedData
\synline{6ex} huffman\_data(part\_idx) & & CompressedData
\synline{3ex} \} else \{ & &
\synline{6ex} \textbf{literal\_bits\_minus1} & Bits(3) & CompressedData
\synline{6ex} $n = \text{literal\_bits\_minus1} + 1$ & &
\synline{6ex} for ($\text{i} = 0 \ldots \text{partition\_size}[\text{part\_idx}] - 1$) \{ & &
\synline{9ex} \textbf{partition\_data\_byte}[$\text{i}$] & Bits($n$) & CompressedData
\synline{6ex} \} & &
\synline{3ex} \} & &
\end{syntab}
A one-bit flag called \textbf{compression\_flag} indicates whether the contents of the partition are encoded a true variable-length Huffman code or if a simple n-bit literal encoding is used instead.

If compression\_flag is not set, a 3-bit syntax element \textbf{literal\_bits\_minus1} follows. The decoded value, incremented by one, specifies with how many effective bits ($n$) the data bytes of this partition are encoded. This is followed by as many $n$-bit values as specified by the partition size. These values are directly used as decoded data bytes, no further translation or encoding takes place.

If compression\_flag is set, variable-length coding is used. A Huffman code specification described in huffman\_codebook() follows. After that, the actual partition data is decoded as huffman\_data().

\subsubsection{Huffman Code Reconstruction}
M4x4 uses a modified Huffman coding scheme. The codes which are used to represent the encoded bytes of a partition (which will be called ``symbols'' in this section) are specified indirectly by their code length. Thus, only the length of each code needs to be encoded in the codebook. In M4x4, the values of the symbols are fixed: The symbols always represent the first literal values, starting with zero. There is no code-to-value mapping table like in JPEG, for example.

\begin{syntab}{huffman\_codebook()}
\synline{3ex} $\text{code\_bits} = 1$ & &
\synline{3ex} for ($\text{symbol} = 0 \ldots 255$) \{ & &
\synline{6ex} \textbf{delta\_code} & Bits(3) & CompressedData
\synline{6ex} if ($\text{delta\_code} == 0$) \{ & &
\synline{9ex} break & &
\synline{6ex} \} else if ($\text{delta\_code} > 5$) \{ & &
\synline{9ex} $\text{delta} = 2$ & &
\synline{9ex} do \{ & &
\synline{12ex} $\text{delta} = \text{delta} + 1$ & &
\synline{12ex} \textbf{extension\_bit} & Bit & CompressedData
\synline{9ex} \} while ($\text{extension\_bit} \,==\, 0$) & &
\synline{6ex} \} & &
\synline{6ex} $\text{code\_bits} = \text{code\_bits} + \operatorname{decode\_delta}()$ & &
\synline{6ex} $\text{symbol\_bits}[\text{symbol}] = \text{code\_bits}$ & &
\synline{6ex} $\text{last\_symbol} = \text{symbol}$ & &
\synline{3ex} \} & &
\synline{3ex} \textbf{truncated\_code\_flag} & Bit & CompressedData
\synline{3ex} if ($\text{truncated\_code\_flag}$) \{ & &
\synline{6ex} \textbf{literal\_bits\_minus1} & Bits(3) & CompressedData
\synline{3ex} \} & &
\end{syntab}

The code lengths are encoded differentially: A 3-bit \textbf{delta\_code} specified in Table~\ref{delta-code} encodes the difference between the last symbol's code length and the current symbol's code length. The initial code length is fixed to 1. For differences greater than $2$ or less than $-2$, the delta code is extended by one or more \textbf{extension\_bit}s: For each zero bit, the absolute value of the difference is increased by one, until a ``one'' bit is read.

\begin{table}[h!]
\caption{delta\_code map}
\label{delta-code}
\begin{center}\begin{tabular}{| c | l |} \hline
\textbf{Bits} & \textbf{Value}
\\ \hline 000 & \emph{(end of codebook)}
\\ \hline 001 & $\pm 0$
\\ \hline 010 & $+1$
\\ \hline 011 & $-1$
\\ \hline 100 & $+2$
\\ \hline 101 & $-2$
\\ \hline 110 & $+3 + \text{(number of following zero bits)}$
\\ \hline 111 & $-3 - \text{(number of following zero bits)}$
\\ \hline \end{tabular}\end{center}
\end{table}

The codebook is terminated with a special delta\_code value. The highest symbol number that has been assigned a code length up to that point is then stored in a variable \emph{last\_symbol} which is required later.

\pagebreak[1]
The actual code words used to represent the symbols of the data stream are constructed by performing the following steps:
\begin{ul}
\item Sort the symbols in order of ascending code length.
\item Assign the first symbol an all-zero code word.
\item Increase the assigned code word by one (with carry propagation) and assign that to the next symbol.
      \begin{ul}
      \item If the code of the new symbol is longer than that of the previous one, append an appropriate number of zero bits to the code word after heaving increased it.
      \end{ul}
\item Repeat the previous step until all symbols have been assigned a code word.
\item All remaining code words are marked as invalid.
\end{ul}

Following the code length specification, the bitstream contains the \textbf{truncated\_code\_flag}. If this flag is set, another 3-bit syntax element called \textbf{literal\_bits\_minus1} follows. The detailed semantics of these syntax elements are described in section~\ref{huffdec}.

\pagebreak[1]
A valid M4x4 bitstream must meet the following restrictions:
\begin{ul}
\item There must be at least one symbol, i.e. the end-of-codebook code must not be the first delta\_code of the codebook.
\item last\_symbol must not exceed 255.
\item Code lengths of zero or less are forbidden.
\item There must be no code with a length greater than 16.
\item It must be possible to assign code words to the symbols without overflow.
\end{ul}

\subsubsection{Data Decoding\label{huffdec}}
The main data decoding process is laid out in huffman\_data().
\begin{syntab}{huffman\_data(part\_idx)}
\synline{3ex} for ($\text{i} = 0 \ldots \text{partition\_size}[\text{part\_idx}] - 1$) \{ & &
\synline{6ex} \textbf{data\_symbol} & Huffman & CompressedData
\synline{6ex} \parbox[t]{7cm}{if ($\text{truncated\_code\_flag}$ \\ $\,\&\&\, (\text{data\_symbol} \,==\, \text{last\_symbol})$) \{} & &
\synline{9ex} $n = \text{literal\_bits\_minus1} + 1$ & &
\synline{9ex} \textbf{partition\_data\_byte}[$\text{i}$] & Bits($n$) & CompressedData
\synline{6ex} \} else \{ & &
\synline{9ex} partition\_data\_byte[$\text{i}$] $= \text{data\_symbol}$ & &
\synline{6ex} \} & &
\synline{3ex} \} & &
\end{syntab}

Decoding is done by parsing the \textbf{data\_symbol} Huffman code for each decoded target byte. The number of symbols to decode is taken directly from the partition size. The values of the symbols are used directly, without any further translation.

Special processing is done if truncated\_code\_flag is set: In this case, the symbol with the value last\_symbol is \emph{not} encoded verbatim like all other symbols. Instead, an $n$-bit code has to be decoded directly after the symbol's code word. The literal value of this second code will then be used as the decoded value instead of the symbol's original value. The length of this $n$-bit code is determined by adding 1 to literal\_bits\_minus1.

\pagebreak[1]
\subsubsection{Huffman Code Example \emph{(informative)}}
In this section, the following compressed partition bitstream will be decoded as an example:
\begin{center}\begin{tabular}{l*{8}{c@{\;}}}
\textbf{hexadecimal:} & CD & 67 & 69 & 88 & 8B & DF & D4 & \ldots \\
\textbf{binary:} & 11001101 & 01100111 & 01101001 & 10001000 & 10001011 & 11011111 & 11010100 & \ldots
\end{tabular}\end{center}

\pagebreak[1]
First, the code book is parsed into the individual delta code sizes:
\[
\underbrace{110\;01}_{+4}
\underbrace{101}_{-2}
\underbrace{011}_{-1}
\underbrace{001}_{0}
\underbrace{110\;1}_{+3}
\underbrace{101}_{-2}
\underbrace{001}_{0}
\underbrace{100}_{+2}
\underbrace{010}_{+1}
\underbrace{001}_{0}
\underbrace{000}_\text{END}
\underbrace{1}_\text{\;truncated\_code\_flag\;}
\underbrace{011}_{\text{\;literal\_bits\_minus1} \;=\; 3}
\]

\pagebreak[1]
The code length deltas are then accumulated to the actual code lengths:
\newcolumntype{Z}{>{\centering\arraybackslash}m{0.5cm}<{}}
\begin{center}\begin{tabular}{l*{31}{@{}Z}}
\textbf{Delta:} & & $+4$ & & $-2$ & & $-1$ & & $0$ & & $+3$ & & $-2$ & & $0$ & & $+2$ & & $+1$ & & $0$ & \\
\textbf{Code Length:} & \small{(1)} & & 5 & & 3 & & 2 & & 2 & & 5 & & 3 & & 3 & & 5 & & 6 & & 6 \\
\textbf{Symbol Number:} & & & 0 & & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & & 7 & & 8 & & 9
\end{tabular}\end{center}

\pagebreak[1]
The codes are then sorted by code length, but preserving the relative order of the symbols for equal code lengths:
\newcolumntype{Y}{>{\centering\arraybackslash}m{1cm}<{}}
\begin{center}\begin{tabular}{l*{10}{@{}Y}}
\textbf{Code Length:}   & 2 & 2 & 3 & 3 & 3 & 5 & 5 & 5 & 6 & 6 \\
\textbf{Symbol Number:} & 2 & 3 & 1 & 5 & 6 & 0 & 4 & 7 & 8 & 9
\end{tabular}\end{center}

\pagebreak[1]
Using these code lengths, the actual code words are assigned to the symbols:
\begin{center}\begin{tabular}{cl}
\textbf{Symbol} & \textbf{Code Word} \\
2 & \textbf{00} \\
3 & 01 \\
1 & 10\textbf{0} \\
5 & 101 \\
6 & 110 \\
0 & 111\textbf{00} \\
4 & 11101 \\
7 & 11110 \\
8 & 11111\textbf{0} \\
9 & 111111
\end{tabular}\end{center}

\pagebreak[1]
Finally, the data itself is parsed. The following example shows the parsing process for the first three symbols. Note that the second parsed symbol is equal to last\_symbol (9). Since truncated\_code\_flag is set, an additional literal value of $\text{literal\_bits\_minus1} + 1 = 4$ bits is parsed at this point:
\[
\underbrace{110}_{6}
\underbrace{111111}_\text{(9)}
\underbrace{1010}_{10 \text{(literal)}}
\underbrace{100}_{1}
\ldots
\]
Thus, the first three partition\_data\_bytes in this example are 6, 10 and 1 (decimal).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Alpha Tree Decoding}
The alpha tree stores, in a compact manner, whether each block in the image is either fully opaque, fully transparent or contains mixed alpha values. The latter type of blocks is called \emph{boundary blocks} because these blocks usually appear at the edges (bondaries) of objects.

To store the block types, a special encoding is used that stores large areas of transparent or opaque blocks efficiently. To achieve this, the block types are stored as a binary tree where each node specifies the type of its two immediate children and whether to descend the tree further.

\begin{figure}[h!]
\caption{Transparent, opaque and boundary blocks example}
\label{block3example}
\definecolor{Ccircle}{gray}{0.75}
\begin{center}\begin{tikzpicture}
\fill[Ccircle] (1.5,1) circle (0.9);
\fill[Ccircle] (2.25,0.75) circle (0.65);
\draw[step=0.5] (0,0) grid (3,2);
\fill (1.25,0.75) circle (0.075);
\fill (1.25,1.25) circle (0.075);
\fill (1.75,0.75) circle (0.075);
\fill (1.75,1.25) circle (0.075);
\fill (2.25,0.75) circle (0.075);
\draw[ultra thick] (1,0) rectangle (0.5,0.5) rectangle (1,1) rectangle (0.5,1.5) rectangle (1,2) rectangle (1.5,1.5) rectangle (2,2) rectangle (2.5,1.5) rectangle (2,1);
\draw [ultra thick] (3,1.5) rectangle (2.5,1) rectangle (3,0.5) rectangle (2.5,0) rectangle (2,0.5) rectangle (1.5,0) rectangle(1,0.5);
\draw (4,1.45) rectangle (4.5,1.95);
\draw (4.6,0.95) node[anchor=west] {= boundary block};
\fill[Ccircle] (4,0.75) -- (4.5,0.75) -- (4.5,1.25);
\draw[ultra thick] (4,0.75) rectangle (4.5,1.25);
\draw (4.6,1.65) node[anchor=west] {= fully transparent block};
\filldraw[fill=Ccircle] (4,0.05) rectangle (4.5,0.55);
\fill (4.25,0.3) circle (0.075);
\draw (4.6,0.25) node[anchor=west] {= fully opaque block};
\end{tikzpicture}\end{center}\end{figure}

The decoding process is recursive and uses a parameter, the \emph{current area}, that specifies the extent of the currently decoded node. The current area is always rectangular or square. Its dimensions are measured in units of 4x4-pixel blocks. The width and height of the current area are always powers of two.

\pagebreak[1]
The decoding process for a single alpha tree node is as follows:
\begin{ul}
\item Two sub-nodes A and B are formed:
      \begin{ul}
      \item If the current area's width is greater than the current area's height, the current area is split in vertical direction to form two horizontally adjacent sub-areas of half width. The left half is assigned to sub-node A and the right half is assigned to sub-node B.
      \item Otherwise, the current area is split in horizontal direction to form two vertically adjacent sub-areas of half height. The upper half is assigned to sub-node A and the lower half is assigned to sub-node B.
      \end{ul}
\item One symbol is read from the AlphaTree partition and is decoded according to Table~\ref{alphadectab}.
\item For sub-node A,
      \begin{ul}
      \item If the sub-node is marked as transparent, all blocks contained in that node's area are marked as transparent.
      \item If the sub-node is marked as opaque, all blocks contained in that node's area are marked as opaque.
      \item If the sub-node is marked as boundary,
            \begin{ul}
            \item If the sub-node's size is exactly $1 \times 1$ block, that block is marked as boundary.
            \item Otherwise, the decoding process is recursively performed for this sub-node.
            \end{ul}
      \end{ul}
%\item If at least one block of the area associated with sub-node B is located inside the image, the same procedure is applied to sub-node B as was done for sub-node A.
\item For sub-node B, the same procedure is applied as for sub-node A.
\end{ul}

\begin{table}[h!]
\caption{AlphaTree codes}
\label{alphadectab}
\begin{center}\begin{tabular}{| c | c | c |} \hline
\textbf{Code} & \textbf{Sub-Node A} & \textbf{Sub-Node B}
\\ \hline 0 & boundary & boundary
\\ \hline 1 & boundary & opaque
\\ \hline 2 & opaque & boundary
\\ \hline 3 & boundary & transparent
\\ \hline 4 & transparent & boundary
\\ \hline 5 & opaque & transparent
\\ \hline 6 & transparent & opaque
\\ \hline 7 & opaque & opaque
\\ \hline 8 & transparent & transparent
\\ \hline \end{tabular}\end{center}
\end{table}

The decoding process is initially invoked with the current area set so that the upper-left corner of the area is co-located with the upper-left corner of the image. The width and height are set by taking image\_width and image\_height, dividing these values by 4, and rounding them up to the next integer power of two. The current area may thus become larger then the image. If this is the case, assignments to blocks outside of the image shall be ignored.

For example, the following AlphaTree data is decoded to the block map shown in figure~\ref{block3example}: \\ \hspace*{1cm} 00004410004420010301020

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pagebreak[1]
\section{Plane Decoding}
The color planes are decoded in the following order:
\begin{ul}
\item alpha (if alpha\_flag is set)
\item luminance
\item chrominance Cg (if color\_flag is set)
\item chrominance Co (if color\_flag is set)
\end{ul}
Each plane is decoded independently. The size of the alpha and luminance planes in blocks is computed as follows:
\[ \begin{matrix}
\text{plane\_width\_in\_blocks}_\text{luma} = (\text{image\_width} + 3) / 4 \\
\text{plane\_height\_in\_blocks}_\text{luma} = (\text{image\_height} + 3) / 4
\end{matrix} \]
For the chrominance planes, the chroma subsampling factors need to be taken into account:
\[ \begin{matrix}
\text{horiz\_subsample} = \text{chroma\_subsample\_code} \,>>\, 4 \\
\text{vert\_subsample} = \text{chroma\_subsample\_code} \;\&\; 15 \\
\text{plane\_width\_in\_blocks}_\text{chroma} = (\text{plane\_width\_in\_blocks}_\text{luma} + \text{horiz\_subsample} - 1) / \text{horiz\_subsample} \\
\text{plane\_height\_in\_blocks}_\text{chroma} = (\text{plane\_height\_in\_blocks}_\text{luma} + \text{vert\_subsample} - 1) / \text{vert\_subsample}
\end{matrix} \]

Inside each plane, the blocks are decoded in so-called \emph{raster-scan order}, which is identical to normal Latin reading order: blocks are decoded row after row from top to bottom and inside each row, the blocks are encoded from left to right. The plane decoding process is described in plane().

\begin{syntab}{plane()}
\synline{3ex} \textbf{qp\_run} & Level & QP\_Run
\synline{3ex} for ($y = 0 \ldots \text{plane\_height\_in\_blocks} - 1$) \{ & &
\synline{4ex} for ($x = 0 \ldots \text{plane\_width\_in\_blocks} - 1$) \{ & &

\synline{6ex} if (\textit{current plane is alpha}) \{ & &
\synline{9ex} process\_alpha() & &
\synline{6ex} \} & &

\synline{6ex} if (\textit{current block is valid}) \{ & &
\synline{9ex} intra\_pred() & &

\synline{9ex} qp = predict\_qp() & &
\synline{9ex} if ($\text{qp\_run} \,==\, 0$) \{ & &
\synline{12ex} \textbf{qp\_delta\_sign} & Bit & Signs
\synline{12ex} \textbf{qp\_delta\_abs\_minus1} & Level & QP\_Delta
\synline{12ex} \textbf{qp\_run} & Level & QP\_Run
\synline{12ex} $\begin{array}{@{}l@{}l} \text{qp} = \text{qp} + & \operatorname{SignComb}(\text{qp\_delta\_sign}, \\ & \text{qp\_delta\_abs\_minus1} + 1) \end{array}$ & &
\synline{9ex} \} else \{ & &
\synline{12ex} $\text{qp\_run} = \text{qp\_run} - 1$ & &
\synline{9ex} \} & &

\synline{9ex} $p = \text{predict\_tc()}$ & &
\synline{9ex} \textbf{total\_coeff} & Byte & TotalCoeff[$p$]
\synline{9ex} if ($\text{total\_coeff} \;>\; 0$) \{ & &
\synline{12ex} coeff\_decode(total\_coeff) & &
\synline{12ex} process\_block() & &
\synline{9ex} \} & &

\synline{6ex} \} & &
\synline{6ex} deblock() & &
\synline{4ex} \} & &
\synline{3ex} \} & &
\end{syntab}

For blocks in the alpha plane, the process\_alpha() step as described in section~\ref{process-alpha} is performed first.

For blocks which are not marked as valid, most of the further processing for these blocks is skipped, except for deblock(), i.e. deblocking filtering as described in section~\ref{deblock}.

\begin{quote}
\textsf{\textbf{Recommendation:}} The contents of non-valid blocks in color planes are undefined; however, it is recommended to fill the 16 pixels in those blocks with the value 128.
\end{quote}

For all valid blocks, the intra prediction step intra\_pred() as described in section~\ref{intrapred} is performed prior to decoding the QP and the coefficients.

QP decoding is performed for all valid blocks using a predictive run-length scheme. For each block, a QP is predicted using the algorithm described in section~\ref{modepred}. The \textbf{qp\_run} values specify for how many consecutive blocks this prediction is to be used directly. At blocks where such a run ends, the difference between the predicted QP and the actual QP is encoded, split into the sign (\textbf{qp\_delta\_sign}) and the absolute value (\textbf{qp\_delta\_abs\_minus1}). A valid bistream must not contain combinations of these syntax elements that result in the final QP leaving the range of 0 to 127 (inclusive).

The \textbf{total\_coeff} value, which is to be decoded for all valid blocks, is context-dependent: The prediction process described in section~\ref{modepred} is used to determine a \emph{predicted} total\_coeff value, which is then used to select the partition from which the actual total\_coeff value is to be decoded.

Only if total\_coeff is nonzero and a block is valid, the transform coefficients will be parsed, dequantized, transformed and applied to the image. These processes are described as coeff\_decode() in section~\ref{coeff-decode} and process\_block() in section~\ref{iq-it}.

In any case, the deblocking filter deblock() as described in section~\ref{deblock} is applied to a block at the end of the decoding process.

\pagebreak[1]
\subsection{Alpha Processing\label{process-alpha}}
In the alpha plane, special processing is performed for each block prior to deblocking:
\begin{ul}
\item If a block is marked as transparent, all 16 pixels of that block shall be set to 0 (zero).
\item If a block is marked as opaque, all 16 pixels of that block shall be set to 255.
\item If a block is marked as boundary, normal decoding (including intra prediction, coefficient decoding, inverse quantization and inverse transform) is performed.
\end{ul}

\subsection{Block Type Map Downsampling}
If a color image with alpha information uses chrominance subsampling, the per-block opaque~/ transparent~/ boundary classification needs to be subsampled as well, because the availability and validity status of blocks depends on this information which therefore must be at the same scale as the plane to decode. Since the subsampled chrominance planes have fewer blocks, the alpha map needs to be reduced in resolution as well.

For the purposes of this process, not all three block type distinctions are required. Instead, only the types ``transparent'' and ``non-transparent'' are considered. Opaque and boundary blocks are both considered non-transparent.

The reduction process is done by combining the classifications of each non-overlapping rectangular section of $\text{horiz\_subsample} \times \text{vert\_subsample}$ blocks into a single classification, starting at the upper-left corner of the image. If $\text{plane\_width\_in\_blocks}_\text{luma}$ or $\text{plane\_height\_in\_blocks}_\text{luma}$ are not divisible by $\text{horiz\_subsample}$ and $\text{vert\_subsample}$, respectively, the sections at the right and lower edges of the planes shall be accordingly smaller.

\pagebreak[1]
The rule for combining the classifications is the following:
\begin{ul}
\item If any of the blocks inside a section is marked as non-transparent (i.e. opaque or boundary), the resulting block is marked as non-transparent.
\item Otherwise (all blocks inside a section are marked as transparent), the resulting block is marked as transparent.
\end{ul}

For example, if the image shown in Figure~\ref{block3example} is downsampled with $\text{horiz\_subsample} > 1$, all resulting blocks would be marked as non-transparent. If it is downsampled with $\text{horiz\_subsample} == 1$ and $\text{vert\_subsample} > 1$, the blocks at the left edge of the image would be marked as transparent and all other blocks would be marked as non-transparent.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Intra Prediction\label{intrapred}}
Intra Prediction is a process that attempts to estimate the contents of the current block based on the contents of the surrounding blocks. It is performed for all valid blocks in a plane.

The following description uses the nomenclature for neighbor blocks that is defined in section~\ref{neighbors}. The pixels in the current block are called $C_{ij}$, where $i$ is the row coordinate and $j$ is the column coordinate, starting with $C_{00}$ at the upper-left corner of the block. The four pixels immediately above the current block are called $T_j$ and the four pixels immediately left of the block are called $L_i$, with the same semantics for the $i$ and $j$ coordinates. The pixel that is located at the position where $L_{-1}$ and $T_{-1}$ would be is called $X$.

\pagebreak[1]
The intra prediction process is performed as follows:
\begin{ul}
\item If none of the L, T and LT neighbor blocks is valid, the block is filled with 128, i.e. \[ C_{ij} = 128 \]
\item If the L and T neighbor blocks are not valid, but LT is, the block is filled with the upper-left neighbor pixel, i.e. \[ C_{ij} = X \]
\item If the L neighbor block is valid, but T is not, the rightmost row of the L block is repeated to fill the current block, i.e. \[ C_{ij} = L_i \]
\item If the T neighbor block is valid, but L is not, the bottom row of the T block is repeated downwards to fill the current block, i.e. \[ C_{ij} = T_j \]
\item If both neighbor blocks L and T are valid, the predictions of the ``left-only'' and ``top-only'' cases are averaged together as follows: \[ C_{ij} = (L_i + T_j + 1) >> 1 \]
\end{ul}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Transform Coefficient Decoding\label{coeff-decode}}
The transform coefficient decoding process is used to parse and decode a compact representation of quantized transform coefficients into a 16-element integer array called the \emph{coefficient scan} or \textbf{coeff\_scan}$[]$. The scan is encoded in reverse order.

Since a coefficient scan is typically sparse, i.e. many values tend to be zero, a run-length encoding scheme is used: With every non-zero coefficient, a \textbf{run} is encoded that specifies the number of zero coefficients that occur directly in front of that non-zero coefficient. To make use of the context-adaptivity that is provided by M4x4's data partitioning scheme, a \textbf{total\_zeros} value is prepended in front of the coefficient scan. This way, the decoder knows beforehand how many zeros there are in the scan and can pick a different partition for each run value based on the number of zeros left in the scan.

Another characteristic of typical coefficient scans is the fact that the last few non-zero coefficients often have an absolute value of 1. This is exploited by specifying a \textbf{trailing\_ones} value before the coefficient scan and only encoding the sign of these trailing ones for the first coefficients in the scan.

\pagebreak[1]
coeff\_decode() describes the whole coefficient decoding process:
\begin{syntab}{coeff\_decode(total\_coeff)}
\synline{3ex} for ($i = 0 \ldots 15$) \{ & &

\synline{6ex} $\text{coeff\_scan}[$i$] = 0$ & &
\synline{3ex} \} & &
\synline{3ex} $t = \text{total\_coeff}$ & &

\synline{3ex} \textbf{total\_zeros} & Byte & TotalZeros[$t$]
\synline{3ex} \textbf{trailing\_ones} & Byte & TrailingOnes[$t$]
\synline{3ex} $r = \text{total\_zeros}$ & &
\synline{3ex} $i = \text{total\_coeff} + \text{total\_zeros} - 1$ & &
\synline{3ex} for ($k = 0 \ldots \text{total\_coeff} - 1$) \{ & &

\synline{6ex} \textbf{coeff\_sign} & Bit & Signs
\synline{6ex} if ($k < \text{trailing\_ones}$) \{ & &
\synline{9ex} $\text{coeff\_scan}[i] = \operatorname{SignComb}(\text{coeff\_sign}, 1)$ & &
\synline{6ex} \} else \{ & &
\synline{9ex} \textbf{coeff\_abs\_level\_minus1} & Level & CoeffLevel[$i$]
\synline{9ex} $\begin{array}{@{}l@{\;}l} \text{coeff\_scan} [i] = & \operatorname{SignComb}(\text{coeff\_sign}, \\ & \text{coeff\_abs\_level\_minus1} + 1) \end{array}$ & &
\synline{6ex} \} & &

\synline{6ex} if ($r > 0$) \{ & &
\synline{9ex} \textbf{coeff\_run} & Byte & CoeffRun[$r$]
\synline{9ex} $r = r - \text{coeff\_run}$ & &
\synline{6ex} \} else \{ & &
\synline{9ex} $\text{coeff\_run} = 0$ & &
\synline{6ex} \} & &
\synline{6ex} $i = i - \text{coeff\_run} - 1$ & &

\synline{3ex} \} & &
\synline{3ex} $\operatorname{return}(\text{coeff\_scan}[0 \ldots 15])$ & &
\end{syntab}

A valid bitstream must not contain combinations of syntax elements that cause $i$ or $r$ to leave the range of 0 to 15, inclusive. Furthermore, trailing\_ones must not be greater than total\_coeff.

\pagebreak[1]
\subsection{Coefficient Scanning Pattern}
After decoding, the one-dimensional coeff\_scan$[]$ array is transformed into a two-dimensional matrix of quantized transform coefficients $Q_{ij}$ using a zig-zag-like pattern. The mapping of 1D coeff\_scan$[]$ indices to 2D $Q_{ij}$ is shown in Figure~\ref{zigzag}.

\begin{figure}[h!]
\caption{Zig-zag coefficient scanning pattern}
\label{zigzag}
\definecolor{Czz}{gray}{0.85}
\begin{center}\begin{tikzpicture}
\draw[Czz,line width=0.15cm,line cap=round,line join=round] (0.35,-0.35) -- (1.05,-0.35) -- (0.35,-1.05) -- (0.35,-1.75) -- (1.05,-1.05) -- (1.75,-0.35) -- (2.45,-0.35) -- (1.75,-1.05) -- (1.05,-1.75) -- (0.35,-2.45) -- (1.05,-2.45) -- (1.75,-1.75) -- (2.45,-1.05) -- (2.45,-1.75) -- (1.75,-2.45) -- (2.45,-2.45);
\draw[step=0.7] (0,-2.8) grid (2.8,0);
\draw (0.35,-0.35) node {0};
\draw (1.05,-0.35) node {1};
\draw (1.75,-0.35) node {5};
\draw (2.45,-0.35) node {6};
\draw (0.35,-1.05) node {2};
\draw (1.05,-1.05) node {4};
\draw (1.75,-1.05) node {7};
\draw (2.45,-1.05) node {12};
\draw (0.35,-1.75) node {3};
\draw (1.05,-1.75) node {8};
\draw (1.75,-1.75) node {11};
\draw (2.45,-1.75) node {13};
\draw (0.35,-2.45) node {9};
\draw (1.05,-2.45) node {10};
\draw (1.75,-2.45) node {14};
\draw (2.45,-2.45) node {15};
\draw (0.35,0.1) node[anchor=south] {$0$};
\draw (1.05,0.1) node[anchor=south] {$1$};
\draw (1.75,0.1) node[anchor=south] {$2$};
\draw (2.45,0.1) node[anchor=south] {$3$};
\draw (-0.1,0.05) node[anchor=south east] {$j =$};
\draw (-0.1,-0.35) node[anchor=east] {$i = 0$};
\draw (-0.1,-1.05) node[anchor=east] {$i = 1$};
\draw (-0.1,-1.75) node[anchor=east] {$i = 2$};
\draw (-0.1,-2.45) node[anchor=east] {$i = 3$};
\end{tikzpicture}\end{center}\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pagebreak[1]
\section{Inverse Quantization and Transform\label{iq-it}}
This step, denoted process\_block(), consists of three sub-processes:
\begin{ul}
\item Inverse Quantization (``dequantization'') scales the encoded quantized transform coefficients to unquantized transform coefficients based on the current quantization parameter (section~\ref{iq}).
\item Inverse Transform converts the transform coefficients from the frequency domain into the 2D space domain (section~\ref{it}).
\item Finally, the resulting transform residual is added to the intra-predicted values (section~\ref{add-res}).
\end{ul}

\pagebreak[1]
\subsection{Inverse Quantization\label{iq}}
Part of the dequantization process is the multiplication of the decoded coefficients $Q_{ij}$ with a scaling matrix $D$:
\[
D = \begin{pmatrix}
d_0 & d_2 & d_0 & d_2 \\
d_2 & d_1 & d_2 & d_1 \\
d_0 & d_2 & d_0 & d_2 \\
d_2 & d_1 & d_2 & d_1
\end{pmatrix}
\]

\pagebreak[1]
The values $d_0$, $d_1$ and $d_3$ are derived from the lower 3 bits of the current quantization parameter using the mapping defined in table~\ref{invscale}.

\begin{table}[h!]
\caption{Dequantization factors}
\label{invscale}
\begin{center}\begin{tabular}{|c*{8}{|r}|} \hline
$\mathbf{\textbf{qp} \;\&\; 7}$ & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7}
\\ \hline $\mathbf{d_0}$ &  9 & 10 & 11 & 12 & 13 & 15 & 16 & 17
\\ \hline $\mathbf{d_1}$ & 15 & 16 & 18 & 20 & 21 & 23 & 25 & 28
\\ \hline $\mathbf{d_2}$ & 12 & 13 & 14 & 16 & 17 & 18 & 20 & 22
\\ \hline \end{tabular}\end{center}
\end{table}

\pagebreak[1]
For dequantization, another intermediate value $s$ is computed:
\[
s = 4 - (\text{qp} >> 3)
\]

\pagebreak[1]
The dequantization process itself computes the dequantized transform coefficients $T_{ij}$ from the quantized transform coefficients $Q_{ij}$ as follows:
\[
T_{ij} = \begin{cases}
\big(Q_{ij} \times D_{ij} + (1 << (s - 1))\big) >> s & \text{if } s > 0 \\
\big(Q_{ij} \times D_{ij}\big) << (-s) & \text{otherwise}
\end{cases}
\]
Note that the multiplication $Q_{ij} \times D_{ij}$ is a component-wise multiplication, not an algebraic matrix multiplication.

\pagebreak[1]
\subsection{Inverse Transform\label{it}}
By applying the inverse transform, the $T_{ij}$ matrix of transform coefficients is converted into the $R_{ij}$ matrix of (signed) pixel differences. This is performed in a two-step process. First, the one-dimensional core transform described in section~\ref{coretrans} is applied in horizontal direction over the four rows of the matrix. Each row is transformed independently of the others. After the rows have been transformed, the core transform is applied vertically on all the columns of the (already partially transformed) matrix. Each column is transformed independently of the others. The resulting matrix is then called $R_{ij}$.

\pagebreak[1]
\subsubsection{Core Transform\label{coretrans}}
The one-dimensional core transform operates on the four values $a_0$, $a_1$, $a_2$ and $a_3$, which correspond to the items of one row or column of the matrix. Intermediate values $e_i$ will be used during this process. The computations are performed as follows:
\begin{align*}
e_0 &= a_0 + a_2 \\
e_1 &= a_0 - a_2 \\
e_2 &= (a_1 >> 1) - a_3 \\
e_3 &= a_1 + (a_3 >> 1) \\
a_0 &= e_0 + e_3 \\
a_1 &= e_1 + e_2 \\
a_2 &= e_1 - e_2 \\
a_3 &= e_0 - e_3
\end{align*}

\pagebreak[1]
\subsection{Residual Application\label{res-add}}
After the inverse transform, the residual $R_{ij}$ is added to the intra-predicted pixels $C_{ij}$ of the current block as follows:
\[
C_{ij} = \operatorname{Clip1}(C_{ij} + ((R_{ij} + 2) >> 2))
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pagebreak[1]
\section{Deblocking Filter\label{deblock}}
After a block has been reconstructed, but before the intra prediction of the next block is performed, a deblocking filter is applied to the edges of a block. This is done for all blocks, including invalid ones.

\pagebreak[1]
Deblocking is performed in the following order:
\begin{ul}
\item First, the pixels at the upper edge of the block are filtered in vertical direction.
\item Second, the pixels at the left edge of the block are filtered in horizontal direction.
\end{ul}

\pagebreak[1]
An edge is filtered only if the following conditions are met:
\begin{ul}
\item The blocks on both sides of the edge must be marked as available.
\item At least one of the blocks must be marked as valid. The valid block(s) may be on either side of the edge.
\end{ul}
If any of these conditions is not fulfilled for an edge, the filtering process is skipped for this edge.

\subsection{Edge Deblocking Strength Computation}
For each edge that is to be filtered, various parameters that influence the amount of deblocking to be applied are derived.

\pagebreak[1]
First, a measure of the average quantization parameter $QP_0$ is determined as follows:
\begin{ul}
\item If only one of the blocks along the edge is marked as valid, the quantization parameter of that block is used as $QP_0$.
\item If both blocks along the edge are marked as valid, $QP_0$ is computed using the following equation, with $QP_C$ being the quantization parameter of the current block and $QP_X$ the quantization of the block on the far side of the edge: \[
QP_0 = (QP_C + QP_X) >> 1
\] \end{ul}

\pagebreak[1]
Based on this value, two indexes $i_A$ and $i_B$ are computed: \begin{align*}
i_A &= \operatorname{Clip2}(127,\; QP_0 + \text{deblock\_alpha\_offset}) \\
i_B &= \operatorname{Clip2}(127,\; QP_0 + \text{deblock\_beta\_offset})
\end{align*}
These indexes are used to look up the thresholds $\alpha$, $\beta$ and $t_{C0}$ from Table~\ref{lftab}. Values that are omitted from the tables are assumed to be 255.

\begin{table}[p]
\caption{Deblocking filter thresholds}
\label{lftab}
\newcolumntype{T}{>{\centering\arraybackslash}m{0.8cm}<{}}
\begin{center}\begin{tabular}{|c*{17}{|@{}T@{}}|} \hline
$i_A, i_B$    & <20 &  20 &  21 &  22 &  23 &  24 &  25 &  26 &  27 &  28 &  29 &  30 &  31 &  32 &  33 &  34 &  35 \\ \hline
$\alpha[i_A]$ &   0 &   4 &   4 &   4 &   5 &   5 &   6 &   7 &   7 &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  16 \\ \hline
$\beta[i_B]$  &   0 &   0 &   1 &   1 &   1 &   2 &   2 &   3 &   3 &   3 &   4 &   4 &   4 &   5 &   5 &   6 &   6 \\ \hline
$t_{C0}[i_A]$ &   0 &   0 &   0 &   0 &   0 &   0 &   0 &   0 &   0 &   1 &   1 &   1 &   1 &   1 &   1 &   1 &   1 \\ \hline
\end{tabular}\end{center}
\begin{center}\begin{tabular}{|c*{17}{|@{}T@{}}|} \hline
$i_A, i_B$    &  36 &  37 &  38 &  39 &  40 &  41 &  42 &  43 &  44 &  45 &  46 &  47 &  48 &  49 &  50 &  51 &  52 \\ \hline
$\alpha[i_A]$ &  17 &  19 &  20 &  22 &  25 &  27 &  29 &  32 &  35 &  38 &  42 &  46 &  50 &  55 &  60 &  65 &  71 \\ \hline
$\beta[i_B]$  &   6 &   7 &   7 &   7 &   8 &   8 &   9 &   9 &   9 &  10 &  10 &  10 &  11 &  11 &  12 &  12 &  12 \\ \hline
$t_{C0}[i_A]$ &   1 &   1 &   1 &   1 &   2 &   2 &   2 &   2 &   2 &   2 &   3 &   3 &   3 &   3 &   4 &   4 &   4 \\ \hline
\end{tabular}\end{center}
\begin{center}\begin{tabular}{|c*{17}{|@{}T@{}}|} \hline
$i_A, i_B$    &  53 &  54 &  55 &  56 &  57 &  58 &  59 &  60 &  61 &  62 &  63 &  64 &  65 &  66 &  67 &  68 &  69 \\ \hline
$\alpha[i_A]$ &  78 &  85 &  93 & 101 & 110 & 120 & 131 & 143 & 156 & 171 & 186 & 203 & 221 & 242 & 255 & 255 & 255 \\ \hline
$\beta[i_B]$  &  13 &  13 &  13 &  14 &  14 &  15 &  15 &  15 &  16 &  16 &  16 &  17 &  17 &  18 &  18 &  18 &  19 \\ \hline
$t_{C0}[i_A]$ &   5 &   5 &   6 &   6 &   7 &   7 &   8 &   8 &   9 &  10 &  11 &  12 &  13 &  14 &  16 &  17 &  19 \\ \hline
\end{tabular}\end{center}
\begin{center}\begin{tabular}{|c*{17}{|@{}T@{}}|} \hline
$i_A, i_B$    &  70 &  71 &  72 &  73 &  74 &  75 &  76 &  77 &  78 &  79 &  80 &  81 &  82 &  83 &  84 &  85 &  86 \\ \hline
$\beta[i_B]$  &  19 &  19 &  20 &  20 &  21 &  21 &  21 &  22 &  22 &  22 &  23 &  23 &  24 &  24 &  24 &  25 &  25 \\ \hline
$t_{C0}[i_A]$ &  20 &  22 &  24 &  26 &  29 &  31 &  34 &  37 &  40 &  44 &  48 &  52 &  57 &  62 &  68 &  74 &  81 \\ \hline
\end{tabular}\end{center}
\begin{center}\begin{tabular}{|c*{17}{|@{}T@{}}|} \hline
$i_A, i_B$    &  87 &  88 &  89 &  90 &  91 &  92 &  93 &  94 &  95 &  96 &  97 &  98 &  99 & 100 & 101 & 102 & 103 \\ \hline
$\beta[i_B]$  &  25 &  26 &  26 &  27 &  27 &  27 &  28 &  28 &  28 &  29 &  29 &  30 &  30 &  30 &  31 &  31 &  31 \\ \hline
$t_{C0}[i_A]$ &  88 &  96 & 105 & 114 & 124 & 136 & 148 & 161 & 176 & 192 & 209 & 228 & 249 & 255 & 255 & 255 & 255 \\ \hline
\end{tabular}\end{center}
\begin{center}\begin{tabular}{|c*{17}{|@{}T@{}}|} \hline
$i_B$         & 104 & 105 & 106 & 107 & 108 & 109 & 110 & 111 & 112 & 113 & 114 & 115 & 116 & 117 & 118 & 119 & 120 \\ \hline
$\beta[i_B]$  &  32 &  32 &  33 &  33 &  33 &  34 &  34 &  34 &  35 &  35 &  36 &  36 &  36 &  37 &  37 &  37 &  38 \\ \hline
\end{tabular}\end{center}
\begin{center}\begin{tabular}{|c*{7}{|@{}T@{}}|} \hline
$i_B$         & 121 & 122 & 123 & 124 & 125 & 126 & 127 \\ \hline
$\beta[i_B]$  &  38 &  39 &  39 &  39 &  40 &  40 &  40 \\ \hline
\end{tabular}\end{center}
\end{table}

\subsection{Edge Deblocking Process}
The filtering process operates on the six pixels $p_0$ to $p_2$ and $q_0$ to $q_2$, with $p_i$ being the pixels on one side of the edge and $q_i$ being the pixels on the other side. The pixels with index 0 are the pixels directly along the edge. Figure~\ref{p0q0} illustrates the locations of the pixels.

\begin{figure}[h!]
\caption{Pixel positions for deblocking}
\label{p0q0}
\begin{center}\begin{tikzpicture}
\draw[step=0.7] (-2.1,0) grid (2.1,0.7);
\draw[very thick] (0,-0.3) -- (0,1);
\draw (-1.75,0.35) node {$p_2$};
\draw (-1.05,0.35) node {$p_1$};
\draw (-0.35,0.35) node {$p_0$};
\draw (0.35,0.35) node {$q_0$};
\draw (1.05,0.35) node {$q_1$};
\draw (1.75,0.35) node {$q_2$};
\end{tikzpicture}\end{center}\end{figure}

\begin{tabular}{l}
The filtering process itself is performed using the following algorithm: \\
\hspace*{6ex} $t_C = t_{C0}$ \\
\hspace*{6ex} $\mu = (p_0 + q_0 + 1) >> 1$ \\
\hspace*{6ex} if ($\operatorname{abs}(p_2 - p_0) < \beta)$ \{ \\
\hspace*{9ex} $\Delta = \operatorname{Clip3}(-t_{C0},\; t_{C0},\; p_2 + \mu - (p_1 << 1)) >> 1$ \\
\hspace*{9ex} $p_1 = \operatorname{Clip1}(p_1 + \Delta)$ \\
\hspace*{9ex} $t_C = t_C + 1$ \\
\hspace*{6ex} \} \\
\hspace*{6ex} if $(\operatorname{abs}(q_2 - q_0) < \beta)$ \{ \\
\hspace*{9ex} $\Delta = \operatorname{Clip3}(-t_{C0},\; t_{C0},\; q_2 + \mu - (q_1 << 1)) >> 1$ \\
\hspace*{9ex} $q_1 = \operatorname{Clip1}(q_1 + \Delta)$ \\
\hspace*{9ex} $t_C = t_C + 1$ \\
\hspace*{6ex} \} \\
\hspace*{6ex} $\Delta = \operatorname{Clip3}(-t_C,\; t_C,\; (((q_0 - p_0) << 2) + p_1 - q_1 + 4) >> 3)$ \\
\hspace*{6ex} $p_0 = \operatorname{Clip1}(p_0 + \Delta)$ \\
\hspace*{6ex} $q_0 = \operatorname{Clip1}(q_0 - \Delta)$
\end{tabular}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Chrominance Upscaling and Color Space Conversion}
After all planes of a color image have been decoded, the image needs to be converted from M4x4's internal YCgCo-derived color space into the RGB color space before it can be used by an application. If color subsampling is used (i.e. chroma\_subsample\_code is not equal to 0x11), the chrominance planes need to be upsampled to the full resolution of the luminance plane first. The upscaling algorithm should take into account that the chrominance samples are horizontally and vertically centered between the co-located luminance samples as demonstrated in Figure~\ref{samplepos}. Note that this specification does not specify a concrete upsampling method.

\begin{quote}
\textsf{\textbf{Recommendation:}} To ensure optimum image quality, at least a bilinear upsampling filter should be used. A bicubic filter is preferred.
\end{quote}

\def\symX{+(-0.2,-0.2) -- +(0.2,0.2) +(-0.2,0.2) -- +(0.2,-0.2)}
\def\symO{circle (0.2)}
\begin{figure}[h!]
\caption{Chrominance sample position examples \textit{(informative)}}
\label{samplepos}
\begin{center}\begin{tikzpicture}
\draw[thick] (0,5) \symX; \draw[thick] (0,5) \symO;
\draw[thick] (1,5) \symX; \draw[thick] (1,5) \symO;
\draw[thick] (2,5) \symX; \draw[thick] (2,5) \symO;
\draw[thick] (3,5) \symX; \draw[thick] (3,5) \symO;
\draw[thick] (0,6) \symX; \draw[thick] (0,6) \symO;
\draw[thick] (1,6) \symX; \draw[thick] (1,6) \symO;
\draw[thick] (2,6) \symX; \draw[thick] (2,6) \symO;
\draw[thick] (3,6) \symX; \draw[thick] (3,6) \symO;
\draw[thick] (0,7) \symX; \draw[thick] (0,7) \symO;
\draw[thick] (1,7) \symX; \draw[thick] (1,7) \symO;
\draw[thick] (2,7) \symX; \draw[thick] (2,7) \symO;
\draw[thick] (3,7) \symX; \draw[thick] (3,7) \symO;
\draw[thick] (0,8) \symX; \draw[thick] (0,8) \symO;
\draw[thick] (1,8) \symX; \draw[thick] (1,8) \symO;
\draw[thick] (2,8) \symX; \draw[thick] (2,8) \symO;
\draw[thick] (3,8) \symX; \draw[thick] (3,8) \symO;
\draw (1.5,8.75) node {\textsf{No subsampling (4:4:4)}};
\draw[thick] (5,5) \symX;
\draw[thick] (6,5) \symX; \draw[thick] (5.5,5) \symO;
\draw[thick] (7,5) \symX;
\draw[thick] (8,5) \symX; \draw[thick] (7.5,5) \symO;
\draw[thick] (5,6) \symX;
\draw[thick] (6,6) \symX; \draw[thick] (5.5,6) \symO;
\draw[thick] (7,6) \symX;
\draw[thick] (8,6) \symX; \draw[thick] (7.5,6) \symO;
\draw[thick] (5,7) \symX;
\draw[thick] (6,7) \symX; \draw[thick] (5.5,7) \symO;
\draw[thick] (7,7) \symX;
\draw[thick] (8,7) \symX; \draw[thick] (7.5,7) \symO;
\draw[thick] (5,8) \symX;
\draw[thick] (6,8) \symX; \draw[thick] (5.5,8) \symO;
\draw[thick] (7,8) \symX;
\draw[thick] (8,8) \symX; \draw[thick] (7.5,8) \symO;
\draw (6.5,8.75) node {\textsf{2:1 horizontal subsampling (4:2:2)}};
\draw[thick] (0,0) \symX;
\draw[thick] (1,0) \symX; \draw[thick] (0.5,0.5) \symO;
\draw[thick] (2,0) \symX;
\draw[thick] (3,0) \symX; \draw[thick] (2.5,0.5) \symO;
\draw[thick] (0,1) \symX;
\draw[thick] (1,1) \symX;
\draw[thick] (2,1) \symX;
\draw[thick] (3,1) \symX;
\draw[thick] (0,2) \symX;
\draw[thick] (1,2) \symX; \draw[thick] (0.5,2.5) \symO;
\draw[thick] (2,2) \symX;
\draw[thick] (3,2) \symX; \draw[thick] (2.5,2.5) \symO;
\draw[thick] (0,3) \symX;
\draw[thick] (1,3) \symX;
\draw[thick] (2,3) \symX;
\draw[thick] (3,3) \symX;
\draw (1.5,3.75) node {\textsf{2:1 subsampling (4:2:0)}};
\draw[thick] (5,0) \symX;
\draw[thick] (6,0) \symX; \draw[thick] (6.5,0) \symO;
\draw[thick] (7,0) \symX;
\draw[thick] (8,0) \symX;
\draw[thick] (5,1) \symX;
\draw[thick] (6,1) \symX; \draw[thick] (6.5,1) \symO;
\draw[thick] (7,1) \symX;
\draw[thick] (8,1) \symX;
\draw[thick] (5,2) \symX;
\draw[thick] (6,2) \symX; \draw[thick] (6.5,2) \symO;
\draw[thick] (7,2) \symX;
\draw[thick] (8,2) \symX;
\draw[thick] (5,3) \symX;
\draw[thick] (6,3) \symX; \draw[thick] (6.5,3) \symO;
\draw[thick] (7,3) \symX;
\draw[thick] (8,3) \symX;
\draw (6.5,3.75) node {\textsf{4:1 horizontal subsampling (4:1:1)}};
\draw[thick] (3,10.5) \symX;
\draw[thick] (3.25,10.45) node[anchor=west] {= luminance sample};
\draw[thick] (3,10) \symO;
\draw[thick] (3.25,9.95) node[anchor=west] {= chrominance sample};
\end{tikzpicture}\end{center}\end{figure}

\pagebreak[1]
\subsection{YCgCo to RGB Conversion}
After the chrominance planes have been upsampled to the full resolution, the color data in YCgCo format can be converted into RGB. This is accomplished by computing the following formulae for all pixels of the image, where $Y$, $C_g$ and $C_o$ denote the 8-bit color values for that pixel from the luminance, Cg and Co planes, respectively, and $R$, $G$ and $B$ denote the resulting RGB intensities:
\begin{align*}
a &= Y - C_g + 128 \\
b &= a - C_o + 128 \\
R &= \operatorname{Clip1}(b + ((C_o - 128) << 1)) \\
G &= \operatorname{Clip1}(a + ((C_g - 128) << 1)) \\
B &= \operatorname{Clip1}(b)
\end{align*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\appendix
\chapter{Forward Transform and Quantization \emph{(informative)}}
This chapter describes some of the algorithms that are used to generate compliant streams.

\pagebreak[1]
\section{Forward Transform}
A residual matrix $R^{\star}_{ij}$ of signed pixel differences of a block is transformed into a $T^{\star}_{ij}$ matrix of transform coefficients by applying the foward core transform in-place first on all columns of the matrix and then on all rows of the matrix. The forward core transform operates on the four values $a_0$, $a_1$, $a_2$ and $a_3$, which correspond to the items of one row or column of the matrix. Intermediate values $e_i$ will be used during the process. The computations are performed as follows:
\begin{align*}
e_0 &= a_0 + a_3 \\
e_1 &= a_1 + a_2 \\
e_2 &= a_1 - a_2 \\
e_3 &= a_0 - a_3 \\
a_0 &= e_0 + e_1 \\
a_1 &= e_2 + (e_3 << 1) \\
a_2 &= e_0 - e_1 \\
a_3 &= e_3 - (e_2 << 1)
\end{align*}

\pagebreak[1]
\section{Quantization}
The quantization process computes a matrix of transformed quantized coefficients $Q_{ij}$ from the transformed coefficients $T^{\star}_{ij}$. First, an intermediate value $s$ is computed:
\[
s = (\text{qp} >> 3) + 15
\]
Then, all 16 coefficients are quantized independently of each other using the following formula:
\begin{align*}
t &= (\operatorname{abs}(T^{\star}_{ij}) \times M_{ij} + (1 << (s - 1))) >> s \\
Q_{ij} &= \begin{cases}
t & \text{if }T^{\star}_{ij} \geq 0 \\
-t & \text{if }T^{\star}_{ij} \leq 0 \\
\end{cases}
\end{align*}
Note that the multiplication ($\times$) is a scalar multiplication, not an algebraic vector multiplication.

\pagebreak[1]
The scaling matrix $M_{ij}$ used in the process is composed of values $m_0$, $m_1$ and $m_2$ as follows:
\[
M = \begin{pmatrix}
m_0 & m_2 & m_0 & m_2 \\
m_2 & m_1 & m_2 & m_1 \\
m_0 & m_2 & m_0 & m_2 \\
m_2 & m_1 & m_2 & m_1
\end{pmatrix}
\]

\pagebreak[1]
The values $m_0$, $m_1$ and $m_3$ are derived from the lower 3 bits of the current quantization parameter using the mapping defined in table~\ref{fwdscale}.

\begin{table}[h!]
\caption{Dequantization factors}
\label{fwdscale}
\begin{center}\begin{tabular}{|c*{8}{|r}|} \hline
$\mathbf{\textbf{qp} \;\&\; 7}$ & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7}
\\ \hline $\mathbf{m_0}$ & 14563 & 13107 & 11916 & 10923 & 10082 &  8738 &  8192 &  7710
\\ \hline $\mathbf{m_1}$ &  5592 &  5243 &  4660 &  4194 &  3994 &  3647 &  3355 &  2996
\\ \hline $\mathbf{m_2}$ &  8738 &  8066 &  7490 &  6553 &  6168 &  5825 &  5243 &  4766
\\ \hline \end{tabular}\end{center}
\end{table}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% TODO: rectangular AlphaTrees
% TODO: don't encode last run

\end{document}
