2.1. Laplace classification

A first step in ALF involves a classification $\mathcal {C}l$. Each sample location $(i,j)$ is classified into one of 25 classes $\mathcal {C}_1, \ldots ,\mathcal {C}_{25}$ which are sets of sample locations. A block-based filter adaptation scheme is applied, all samples belonging to each $4\times 4$ local image block share the same class index [Reference Karczewicz, Shlyakhov, Hu, Seregin and Chien22]. For this process, Laplacian and directional features are computed, involving calculation of gradients in four directions for the reconstructed luma samples – see Fig. 2.

Fig. 2. Classification in ALF based on gradient calculations in vertical, horizontal, and diagonal directions.

Gradients for each sample location $(i,j)$ in four directions can be calculated as follows:

\begin{align*} g_v(i,j) & = \left\vert 2\cdot Y(i,j)-Y(i - 1,j)-Y(i + 1,j)\right\vert ,\\ g_h(i,j) & = \left\vert 2\cdot Y(i,j)-Y(i,j - 1)-Y(i,j + 1)\right\vert \end{align*}

for the vertical and horizontal direction and

\begin{align*} g_{d_0}(i,j) & = \left\vert 2\cdot Y(i,j)-Y(i - 1,j - 1)-Y(i + 1,j + 1)\right\vert ,\\ g_{d_1}(i,j) & = \left\vert 2\cdot Y(i,j)-Y(i - 1,j + 1)-Y(i + 1,j - 1)\right\vert \end{align*}

for the two diagonal directions, where Y is a reconstructed luma image after SAO is performed. First, for each $4\times 4$ block B, all of the gradients are calculated at the subsampled positions within a $8 \times 8$ local block $\tilde B$ containing B according to subsampling rule in [Reference Lim, Kang, Lee, Lee and Kim23]. The activity is then given as the sum of the vertical and horizontal gradients over $\tilde B$. This value is quantized to yield five activity values. Second, the dominant gradient direction within each block B is determined by comparing the directional gradients and additionally the direction strength is determined, which give five direction values. Both features together result in 25 classes. For the chroma channels no classification is performed.

2.2. Filter calculation

For each class $\mathcal {C}l$, the corresponding Wiener filter $F_l$ is estimated for $l\in \{1,\ldots ,25\}$ by minimizing the mean square error (MSE) between the original image and the filtered reconstructed image associated with a class $\mathcal {C}l$. Therefore the following optimization problem has to be solved:

(1)\begin{equation} F_l = \underset{\tilde{F}}{\arg\min}\| (X-Y\ast \tilde{F})\cdot {\chi}_{\mathcal{C}_{\ell}}\| _2, \end{equation}

where X is the original image and ${\chi }_{\mathcal {C}_{\ell }}$ is the characteristic function defined by

(2)\begin{equation} {\chi}_{\mathcal{C}_{\ell}}(i,j)= \begin{cases} 1 & {\rm if}\ (i,j) \in \mathcal{C}_{\ell} \\ 0 & {\rm otherwise}\ \end{cases}. \end{equation}

To solve this optimization task in (1), a linear system of equations can be derived with its solution being the optimal filter $F_l$. For a more detailed description of solving the optimization problem in (1), we refer the reader to [Reference Tsai9].

There is no classification applied for the chroma samples and therefore only one filter is calculated for each chroma channel.

2.3. Filtering process

Each Wiener filter $F_l\in \{1,\ldots ,{25}\}$ is obtained after solving the optimization problem in (1) for a given classification $\mathcal {C}l$ and the resulting classes $\mathcal {C}_1,\ldots ,\mathcal {C}_{{25}}$. The filters $F_l$ are symmetric and diamond-shaped – see Fig. 3. In VTM-4.0, they are $5\times 5$ for chroma and $7\times 7$ for the luma channel. They are applied to the reconstructed image Y resulting in a filtered image $X_{\mathcal {C}l}$ as follows:

(3)\begin{equation} X_{\mathcal{C}l} = \sum_{\ell=1}^{{L}}{\chi}_{\mathcal{C}_{\ell}} \cdot (Y \ast F_l) \end{equation}

where L = 25 in this case. Figure 4 shows this filtering process.

Fig. 3. Symmetric diamond-shaped $7\times 7$ filter consisting of 13 distinct coefficients $c_0,\ldots ,c_{12}$.

Fig. 4. Illustration of filtering process: each sample location is classified into one of three classes and filtered by a $5\times 5$ diamond-shaped filter. All shadowed samples affect the filtering process of the center location.

After the classification $\mathcal {C}l$, a class merging algorithm is applied to find the best grouping of classes $\mathcal {C}_1,\ldots ,\mathcal {C}_{25}$ by trying different versions of merging classes based onthe rate-distortion-optimizationprocess. This gives the merged classes $\tilde {\mathcal {C}}_1,\ldots ,\tilde {\mathcal {C}}_{\tilde L}$ for some $\tilde L$ with $1\leq \tilde L \leq 25$. In one extreme, all classes share one filter, when $\tilde L=1$; in the other extreme, each class has its own filter, when $\tilde L=25$.

2.4. Other classification methods for ALF

In addition to Laplace classification, there are other classifications proposed during HEVC and its successor VVC standardization process. In [Reference Lai, Fernandes, Alshina and Kim24], subsampled Laplacian classification was proposed to reduce its computational complexity. Also, in [Reference Wang, Ma, Jia and Park25], the authors introduced a novel classification based on intra picture prediction mode and CU depth without calculation of direction and Laplacian features. Finally, a classification method incorporating multiple classifications has been proposed in [Reference Hsu26], which is similar to MCALF. We will provide some comparison test results for this approach in Section 6.

3.1. Sample intensity based classification

The first classification $\mathcal {C}l_I$ is the simplest one and simply takes quantized sample values of the reconstructed luma image Y as follows:

(6)\begin{equation} \mathcal{C}l_{I}(i,j) = \left\lfloor \frac{(K-1)}{2^{BD}}Y(i,j)\right\rfloor \end{equation}

where BD is the input bit depth and K the number of classes.

3.2. Ranking-based classification

The ranking-based classification $\mathcal {C}l_R$ ranks the sample of interest among its neighbors,

(7)\begin{align} \mathcal{C}l_R(i,j) &= \Bigl\vert \{(k_1,k_2) : Y(i,j) > Y(k_1,k_2)\nonumber\\ &\quad {\rm for}\ \vert k_1-i\vert \leq l, \vert k_2-j\vert \leq h\}\Bigr\vert +1 \end{align}

with l and h specifying the size of neighborhood. Note that when l=1 and h=1, $\mathcal {C}l_R$ is given as a map $\mathcal {C}l_R : I \rightarrow \{1,\ldots ,9\}$ taking eight neighboring samples for $Y(i,j)$. In this case, $\mathcal {C}l_R(i,j)$ simply ranks a sample value $Y(i,j)$ in order of its magnitude compared to its neighboring samples. For instance, if $\mathcal {C}l_R(i,j)=1$, all neighboring sample locations of $(i,j)$ have values greater than or equal to $Y(i,j)$. If $\mathcal {C}l_R(i,j)=9$ then $Y(i,j)$ has larger magnitude than its neighboring sample values. An example is shown in Fig. 6. Here, the center sample has five direct neighbors of smaller magnitudes and is therefore mapped to class index 6.

Fig. 6. Illustration of rank calculation of the center sample.

3.3. Classification with two features

Natural images are usually governed by more than one specific underlying local feature. To capture those features, we can apply a classification described by the product of two distinct classifications $\mathcal {C}l_1$ and $\mathcal {C}l_2$ describing two distinct local features,

\[ \mathcal{C}l_1 : I \rightarrow \{1,\ldots,K_1\} \quad {\rm and} \quad \mathcal{C}l_2 : I \rightarrow \{1,\ldots,K_2\}.\]

They can be joined together by a classification $\mathcal {C}l$, which is the product of $\mathcal {C}l_1$ and $\mathcal {C}l_2$,

(8)\begin{equation} \mathcal{C}l(i,j) = (\mathcal{C}l_1(i,j),\mathcal{C}l_2(i,j)) \in \{1,\ldots,K_1\}\times\{1,\ldots,K_2\}. \end{equation}

The constants $K_1$ and $K_2$ define the number of classes $K = K_1 \cdot K_2$. When K exceeds the desired number of classes (for our experiments, we fix the number of classes for each classification as 25), $\mathcal {C}l(i,j)$ can be quantized to have the intended number of classes $\bar {K}$. If $\mathcal {C}l(i,j)\in \{1,\ldots ,K\}$, then we apply a modified classification $\bar {\mathcal {C}l}$,

(9)\begin{equation} \bar{\mathcal{C}l}(i,j) = {\rm round} \left( \mathcal{C}l(i,j)\cdot \frac{\bar{K}}{K} \right) \in \{1,\ldots,\bar{K}\}. \end{equation}

The round-function maps the input value to the closest integer value. For instance, one can take $\mathcal {C}l_1 = \mathcal {C}l_I$ with $K_1=3$ defined in (6) and $\mathcal {C}l_2 = \mathcal {C}l_R$ as in (7) with l=1, h = 1 which gives $K_2=9$. The product of $\mathcal {C}l_I$ and $\mathcal {C}l_R$ results in $K=K_1\cdot K_2 = 27$ classes. After quantization performed according to (9), we obtain $\bar {K} = 25$ classes.

4.1. Ideal classification

For fixed positive integers n and L, let $\mathcal {C}l^{id}$ be a classification with its corresponding classes $\mathcal {C}_1^{id},\ldots ,\mathcal {C}_L^{id}$ and $n\times n$ Wiener filters $F_1^{id},\ldots ,F_L^{id}$. Then, we call $\mathcal {C}l^{id}$ an ideal classification if

(10)\begin{equation} \| X-X_{\mathcal{C}l^{id}}\| _2 \leq \| X-X_{\mathcal{C}l}\| _2 \end{equation}

for all possible classifications $\mathcal {C}l$ with the corresponding classes $\mathcal {C}_1, \ldots ,\mathcal {C}_L$ and $n\times n$ Wiener filters $F_1, \ldots ,F_L$. $X_{\mathcal {C}l^{id}}$ and $X_{\mathcal {C}l}$ are the filtered reconstructions according to (3). Equation (10) implies that an ideal classification leads to a reconstructed image $X_{\mathcal {C}l^{id}}$ with the smallest MSE compared with X among all reconstructions $X_{\mathcal {C}l}$. Please note that this definition does not incorporate the merging process and the resulting rate. In fact, classes

(11)\begin{equation} \begin{aligned} \tilde{\mathcal{C}}_1 &= \{(i,j) \in I : Y(i,j) \leq X(i,j)\}, \\ \tilde{\mathcal{C}}_2 &= \{(i,j) \in I: Y(i,j) > X(i,j)\} \end{aligned} \end{equation}

with L = 2 were introduced for ideal classes in [Reference Erfurt, Lim, Schwarz, Marpe and Wiegand21]. In (11), I is the set of all luma sample locations and X and Y are original and reconstructed luma images respectively. Intuitively this partition into $\tilde {C}_1$ and $\tilde {C}_2$ is reasonable. In fact, one can obtain a better approximation to X than Y by magnifying reconstructed samples $Y(i,j)$ for $(i,j)$ belonging to $\tilde {C}_1$ and demagnifying samples associated with $\tilde {C}_2$. These samples have to be multiplied by a factor larger than 1 in the former and by a factor smaller than 1 in latter case.

4.2. Approximation of an ideal classification

To find a classification which gives a partition into the ideal classes $\tilde {\mathcal {C}}_1$ and $\tilde {\mathcal {C}}_2$ might be an infeasible task. Instead, we want to approximate such a classification by utilizing information from the original image which need to be transmitted ultimately to the decoder.

Suppose we have a certain classification ${\rm {\cal C}}l:I\to \{ 1, \ldots ,9\} $ which can be applied for a reconstructed image Y at each sample location $(i,j) \in I$. Now, to approximate the two ideal classes $\tilde {\mathcal {C}}_1$ and $\tilde {\mathcal {C}}_2$ with $\mathcal {C}l$, we construct an estimate of those two classes, i.e. ${\mathcal {C}}^{e}_{1}$ and ${\mathcal {C}}^{e}_{2}$ as follows.

First, we apply a classification $\mathcal {C}l$ to pre-classify each sample location $(i,j)$ into the pre-classes $\mathcal {C}_1^{pre}, \dots ,\mathcal {C}_9^{pre}$. For each $k \in \{1,\dots ,9\}$, $\mathcal {C}l(i,j) = k$ implies a sample location $(i,j)$ belongs to a class $\mathcal {C}_k^{pre}$. Now we measure how much accurately the classification $\mathcal {C}l$ identifies sample locations in $\tilde {\mathcal {C}}_1$ or $\tilde {\mathcal {C}}_2$. For this, we define $p_{k,1}$ and $p_{k,2}$ by

(12)\begin{equation} p_{k,1} = \frac{\vert \mathcal{C}_k^{pre} \cap \tilde{\mathcal{C}}_{1}\vert }{\vert \mathcal{C}_k^{pre}\vert }, \quad p_{k,2} = \frac{\vert \mathcal{C}_k^{pre} \cap \tilde{\mathcal{C}}_{2}\vert }{\vert \mathcal{C}_k^{pre}\vert } \end{equation}

where $\vert A\vert$ is the number of elements contained in a set A. We call $p_{k,1}$ and $p_{k,2}$ confidence level. For a fixed positive constant $p \in (1/2,1)$ and a given classification $\mathcal {C}l$, we now define a map $P_{\mathcal {C}l} : \{1,\ldots ,9\} \longrightarrow \{0,1,2\}$ as follows:

(13)\begin{equation} P_{\mathcal{C}l}(k) = \begin{cases} 1 & p_{k,1}> p \\ 2 & p_{k,2}> p \\ 0 & {\rm otherwise} .\end{cases} \end{equation}

The confidence level calculation is illustrated in Fig. 7. Here, a large part of $\mathcal {C}_k^{pre}$ intersect with the ideal class $\tilde {C}_2$, which leads to a high confidence level value $p_{k,2}$ and ultimately sets $P_{\mathcal {C}l}(k) = 2$ (if the constant p is reasonably high). We would like to point out that the map $P_{\mathcal {C}l}$ can be given as a vector $P_{\mathcal {C}l} = (P_{\mathcal {C}l}(1), \ldots ,P_{\mathcal {C}l}(9))$ of length 9 and one can now obtain $\mathcal {C}^e_{\ell }$ by

(14)\begin{equation} \mathcal{C}^e_{\ell} = \{(i,j) \in I : P_{\mathcal{C}l}(\mathcal{C}l(i,j)) = \ell\} \quad {\rm for}\ \ell = 1,2 \end{equation}

using $P_{\mathcal {C}l}$ and $\mathcal {C}l$. Note that $\mathcal {C}^e_{\ell }$ are obtained by collecting sample locations $(i,j)$ which can be classified into the ideal classes $\tilde {\mathcal {C}}_{\ell }$ with sufficiently high confidence (higher than p) by a given classification $\mathcal {C}l$. The vector $P_{\mathcal {C}l}$ has to be encoded into the bitstream.

Fig. 7. Illustration of confidence level calculation. The outer ellipse is the set of all sample locations and divided into the ideal classes $\tilde {C}_1$ and $\tilde {C}_2$. The inner ellipse represents the pre-class $C_k^{pre}$ for $k\in \{1,\ldots ,9\}$, which intersects with $\tilde {C}_1$ and $\tilde {C}_2$.

Not all sample locations are classified by the classification $\mathcal {C}l$ into either $C_1^{e}$ or $C_2^{e}$. Sample locations $(i,j)$ with $P_{\mathcal {C}l}(\mathcal {C}l(i,j))=0$ have to be classified with a second classification $\tilde {\mathcal {C}l}$, producing $\tilde {K}$ additional classes,

(15)\begin{equation} \mathcal{C}_{\ell} = \{(i,j) \notin \mathcal{C}^e_{1} \cup \mathcal{C}^e_{2} : \tilde{\mathcal{C}l}(i,j) = \ell\} \quad {\rm for} \ \ell = 1,\ldots,\tilde{K}. \end{equation}

This gives $\tilde {K}+2$ classes, namely $\mathcal {C}^e_{1}, \mathcal {C}^e_{2}, \mathcal {C}_1,\ldots ,\mathcal {C}_{\tilde {K}}$.

6.1. Extension of original MCALF

The first algorithm MCALF-1 incorporates five classifications. For our extension MCALF-2, we apply a new reconstruction scheme (21) with three classifications consisting of Laplace classification and two additional classifications, which will be specified in the next section. We choose a threshold parameter T = 2 for $\mathcal {C}l_T$ to construct classes $\mathcal {D}_{\ell }$ in (21). This parameter is experimentally chosen. Alternatively, it can be selected at the encoder so that the corresponding RD cost is minimized with this selected threshold. In this case, the selected threshold T should be transmitted to the bitstream.

6.2. Experimental setup

For the results of our experimental evaluation, we integrate our MCALF algorithms and compare VTM-4.0 + MCALF-1 and VTM-4.0 + MCALF-2 to VTM-4.0. Please note that ALF is adopted into the reference software. We also compare our MCALF approach to the ALF algorithm with the classification method in [Reference Hsu26]. In [Reference Hsu26], a classification method employing three classifications has been proposed. Two of the classifications are nearly identical to Laplace and sample intensity based classifications while the third one classifies samples based on similarity between neighboring samples. For this comparison test, we integrate those three classifications into VTM-4.0 and call it ALF-2.

The coding efficiency is measured in terms of bit-rate savings and is given in terms of Bjøntegaard delta (BD) rate [Reference Bjøntegaard29]. In the experiments, the total of 26 different video sequences, covering different resolutions including WQVGA, WVGA, 1080p, and 4K, are used. They build the set of sequences of the common test conditions (CTC) for VVC [Reference Boyce, Suehring, Li and Seregin30] The quantization parameterssettings are 22, 27, 32, and 37. The run-time complexity is measured by the ratio between the anchor and tested method.

6.3. Evaluation of simulation results

Tables 1 and 2 show the results for random access (RA) and low delay B (LDB) configurations respectively. It is evident that RD performance is improved for both multiple classification algorithms MCALF-1 and MCALF-2. In particular, MCALF-2 algorithm increases coding efficiency up to $1.43\%$ for RA configuration. It should be also noted that MCALF-2 consistently outperforms MCALF-1 for all test video sequences except for one of screen content sequences, SlideEditing. The last three columns inTable 1 show how often each classification in MCALF-2 is selected for each test video sequence. This shows how each of classifications performs compared to others with respect to RD performance depending on test video sequences.

Table 1. Coding gains of MCALF-1 and MCALF-2 for RA configuration and percentage of each classification in MCALF-2.

Table 2. Coding gains of MCALF-1 and MCALF-2 for LDB configuration.

Furthermore, Tables 3 and 4 show the comparison results between ALF-2 and MCALF-2 for RA and LDB. It is clear that MCALF-2 consistently outperforms ALF-2 with the classification method in [Reference Hsu26] for all test video sequences.

Table 3. Coding gains of ALF-2 and MCALF-2 for RA configuration.

Table 4. Coding gains of ALF-2 and MCALF-2 for LDB configuration.

6.4. Discussion of complexity/implementation aspects

Having multiple classifications in general does not notably increase the complexity as each of classifications considered in this paper is comparable with Laplace classification in terms of complexity. For instance, the ranking-based classification $\mathcal {C}l_R(i,j)$ requires eight comparisons and eight additions for each $(i,j) \in I$. Therefore the total number of operations for $\mathcal {C}l_{R,I}$ is comparable with Laplace classification with 176/16 additions and 64/16 comparisons for each sample location $(i,j) \in I$. We also note that $\mathcal {C}l_{I}$ is less complex than $\mathcal {C}l_{R,I}$.

For Laplace classification, $4 \times 4$ block-based classification is recently adopted, which significantly reduces its complexity. One can also modify sample-based classifications $\mathcal {C}l_{I}$ and $\mathcal {C}l_{R,I}$ used in MCALF-2 so that resulting classifications are applied for each non-overlapping $4 \times 4$ block. For this, we first define $4 \times 4$ block $B(i,j)$ for $(i,j) \in I$ as follows:

\[ B(i,j) = \{(i+\ell_1,j+\ell_2) : 0 \leq \ell_1, \ell_2 \leq 3\}\]

For each block $B(i,j)$, an average sample value over $B(i,j)$ is given as

(24)\begin{equation} \overline{Y}(B(i,j)) = \frac{1}{16}\sum_{(\ell_1,\ell_2) \in B(i,j)} Y(\ell_1,\ell_2). \end{equation}

Then we define $4 \times 4$ block-based classifications for $\mathcal {C}l_{I}$ and $\mathcal {C}l_{R,I}$ by simply replacing $Y(i,j)$ and $Y(k_1,k_2)$ by $\overline {Y}(B(i,j))$ and $\overline {Y}(B(k_1,k_2))$ in (6) and (7). Finally, we apply (21) with those $4 \times 4$ block-based classifications instead of $\mathcal {C}l_{R,I}$ and $\mathcal {C}l_{I}$. This reduces its complexity compared to MCALF-2 and gives $-0.37 \%$ (Y), $-0.86 \%$ (U), $-0.74 \%$ (V) coding gains on average for RA over 15 video sequences in classes A1, A2, B,and C.

There are two main issues for implementing MCALF-2. First, the classification $\mathcal {C}l_T$ in (18) requires extra memory to store a whole reconstructed image $Y_1$. One remedy for this would be to take the difference between two images Y and $\hat Y$, a reconstructed image obtained by applying filtering with Wiener filters $F_k$ to Y, instead of $Y_1-Y$ in (18). This approach can be then extended to take neighboring sample values of $Y(i,j)-\hat {Y}(i,j)$ with some weights for $(i,j) \in I$ as suggested in [Reference Lim, Schwarz, Marpe and Wiegand27], which can be further investigated for future work. Second, line buffer issue is always the key for any coding tool design. In particular, the size of the line buffer is determined by the vertical size of the filter employed in ALF. For this, one can further explore an approach [Reference Budagavi, Sze and Zhou31] to derive ALF filter sets with reduced vertical size.