Signal Processing: Image Communication 112 (2023) 116914 Contents lists available at ScienceDirect Signal Processing: Image Communication journal homepage: www.elsevier.com/locate/image Probability models for highly parallel image coding architecture Francesc Aulí-Llinàs ∗, Joan Bartrina-Rapesta, Miguel Hernández-Cabronero Department of Information and Communications Engineering, Universitat Autònoma de Barcelona, 08193 Bellaterra, Spain ARTICLE INFO ABSTRACT Keywords: A key aspect of image coding systems is the probability model employed to code the data. The more precise the Image coding probability estimates inferred by the model, the higher the coding efficiency achieved. In general, probability Parallel computing models adjust the estimates after coding every new symbol. The main difficulty to apply such a strategy to Entropy coding a highly parallel coding engine is that many symbols are coded simultaneously, so the probability adaptation Probability models requires a different approach. The strategy employed in previous works utilizes stationary estimates collected a priori from a training set. Its main drawback is that statistics are dependent of the image type, so different images require different training sets. This work introduces two probability models for a highly parallel architecture that, similarly to conventional systems, adapt probabilities while coding data. One of the proposed models estimates probabilities through a finite state machine, while the other employs the statistics of already coded symbols via a sliding window. Experimental results indicate that the latter approach improves the performance achieved by the other models, including that of JPEG2000 and High Throughput JPEG2000, at medium and high rates with only a slight increase in computational complexity. 1. Introduction such as VVC (ITU H.266) and High Throughput (HT) JPEG2000 utilize arithmetic coding [15] and variable length coding [16], respectively. The core of most compression systems holds an entropy coder that These standards also provide parallelization opportunities that can be converts pre-processed data into a more compact representation. Key adopted in implementations tailored for CPUs or GPUs, since this is the to achieve compression is to exploit the probabilities of the coded current trend to increase the throughput of computationally intensive symbols. Symbols with a higher probability can be represented more applications. compactly, with the limit imposed by the Shannon’s entropy. In gen- In the same vein as these latest standards, Bitplane Image Coding eral, two aspects affect the efficiency of the entropy coder: the coding with Parallel Coefficient Processing (BPC-PaCo) [17] is a wavelet-based scheme and the probability model. There are many different coding image coding engine with features similar to those of the JPEG2000 schemes, ranging from Huffman coding [1], arithmetic coding [2], standard. Its main difference is the bitplane and entropy coding engine, or the recently introduced asymmetric numeral systems [3], among which provides more opportunities to exploit fine-grain parallelism others. Each coding scheme imposes a computational burden and an in highly parallel architectures such as those of GPUs. Contrarily to efficiency limit. The probability model, on the other hand, extracts rela- most image codecs that process image coefficients one by one, BPC- tionships among the coded data in order to estimate the probabilities of the new symbols fed to the coder. In general, this is achieved employing PaCo codes 32 coefficients in parallel. The probability model employed contextual information, since previous symbols with the same context by the original BPC-PaCo [17] is based on stationary probabilities tend to have similar probabilities. generated with a training set of images [12]. This model was adopted In the field of image and video coding, the first compression stan- due to its low computational complexity, since probability estimates are dards such as JPEG (ISO/IEC 10918-1) and MPEG-2 (ITU H.262) em- obtained by simply accessing a lookup table (LUT). The main drawback ployed, among others, entropy coding schemes based on Huffman. Vari- is that it needs to be trained with a set of images similar to that coded, ants of such entropy coders and their probability models were proposed which may not be feasible in some scenarios, and that the LUT must be to improve coding efficiency and reduce computational costs [4–6]. (possibly transmitted and) specified in the encoder and the decoder. To The next generation of standards, including JPEG2000 (ISO/IEC 15444- use adaptive probabilities like most conventional image coding systems 1), AVC (ITU H.264), and HEVC (ITU H.265) adopted low-complexity, poses a challenge in the highly parallelized engine of BPC-PaCo because context-adaptive binary arithmetic coders [7–9]. They were the topic probability estimates need to be synchronized and shared among all of many works in the literature too [10–14]. The latest standards threads of execution. ∗ Correspondence to: Escola Enginyeria, UAB, 08193 Bellaterra, Spain. E-mail addresses: francesc.auli@uab.cat (F. Aulí-Llinàs), joan.bartrina@uab.cat (J. Bartrina-Rapesta), miguel.hernandez@uab.cat (M. Hernández-Cabronero). https://doi.org/10.1016/j.image.2022.116914 Received 12 July 2022; Received in revised form 25 November 2022; Accepted 7 December 2022 Available online 30 December 2022 0923-5965/© 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). F. Aulí-Llinàs, J. Bartrina-Rapesta and M. Hernández-Cabronero Signal Processing: Image Communication 112 (2023) 116914 This paper approaches this challenge with the study of two prob- once per coding pass. The parallel processing of BPC-PaCo is tailored ability models that use adaptive probabilities. This study is carried for the highly parallel architecture of GPUs, which typically maps out mostly from the point of view of coding performance. The first parallel execution flows to vector instructions. In the following, thread model employs a finite state machine that predicts the probability of is referred to such an execution flow. future symbols. This strategy is similar to that employed in JPEG2000 Each bit emitted by the bitplane coder is fed to the entropy coder and other standards such as HEVC and VVC. The second model is accompanied by its context. The context is an important aspect of the based on a sliding window mechanism that adjusts probability esti- probability model because the entropy coder obtains the probability mates through statistics of already coded symbols. This latter approach estimate of the incoming bit depending on its context. A comprehen- achieves high performance regardless of the image type, improving the sive study of context formation [24] concludes that simple strategies results achieved by the remaining models and also by JPEG2000. obtain high performance. BPC-PaCo embraces this simplicity to reduce The rest of the paper is structured as follows. Section 2 reviews BPC- computational costs too. Contexts are defined as follows: let the eight PaCo. Section 3 describes the original probability model employed in adjacent neighbors of 𝜐 be denoted by 𝜐𝑘 , 1 ≤ 𝑘 ≤ 8. Its significance BPC-PaCo and introduces the two new models proposed in this paper. state in bitplane 𝑗 is referred to as 𝛷(𝜐𝑘 , 𝑗), being 1 when 𝜐𝑘 has been Section 4 provides extensive experimental results with four different coded in the previous significance pass (i.e., if there is an 𝑠 > 𝑗 such corpora, assessing coding performance and computational complexity. that 𝑏𝑠 (𝜐𝑘 ) = 1), or when it is coded in the current bitplane -and The final section concludes with a brief summary and some remarks. the coefficient is already visited in the current coding pass. Otherwise 𝛷(𝜐𝑘 , 𝑗) = 0. The context employed for significance coding in SPP and 2. Bitplane coding with Parallel Coefficient Processing CP in bitplane 𝑗 is defined as the sum of the significance states of the adjacent neighbors of 𝜐, more precisely BPC-PaCo is a coding engine tailored for wavelet-based image cod- ∑ 𝜙𝑠𝑖𝑔 (𝜐, 𝑗) = 𝛷(𝜐𝑘 , 𝑗) , (1) ing systems. The first stage of such codecs commonly entails one or 𝑘=1…8 various transforms, including the discrete wavelet transform, to remove so 𝜙𝑠𝑖𝑔 (𝜐, 𝑗) ∈ [0, 8]. We note that using the significance state of these spatial, spectral, and/or temporal redundancy. The resulting wavelet neighbors does not create thread dependencies because all threads ad- coefficients are quantized and coded via bitplane and entropy coding, vance their execution at the same pace, i.e., in a lockstep synchronous which is the stage that accounts for more than 80% of the compu- way. tational workload [18]. There are many bitplane coding engines in The context for sign coding employs the sign of the vertical and the literature, e.g., SPIHT [19], SPECK [20], EBCOT [21], JPEG2000’s horizontal adjacent neighbors of coefficient 𝜔. Let 𝜒(𝜔𝑘 , 𝑗) be 0, 1 or tier-1 [22], or BPC-PaCo [17]. To allow coarse-grain parallelism, the −1 at bitplane 𝑗 when the coefficient is still not significant, significant wavelet coefficients are typically partitioned in small sets, referred to and positive, and significant and negative, respectively. 𝜒 𝑉 and 𝜒 𝐻 as codeblocks, that are coded independently, producing a bitstream for are defined as the sum of 𝜒(𝜔𝑘 , 𝑗), respectively for the two vertical each. These bitstreams are possibly (truncated and) re-organized to fit and horizontal adjacent neighbors of 𝜔. The context for sign coding a target rate, or to form layers of quality, in the last stage of the coding is defined as pipeline. ⎧9 if (𝜒 𝑉 > 0 and 𝜒 𝐻 > 0) or The main idea behind bitplane coding is to code all data within the ⎪ codeblock bit by bit, beginning from the highest magnitude bit of all ⎪ (𝜒 𝑉 < 0 and 𝜒 𝐻 < 0) quantized coefficients and finishing with the lowest. If [𝑏𝑀−1 , 𝑏𝑀−2 , … , ⎪ 𝜙𝑠𝑖𝑔𝑛 (𝜔, 𝑗) = ⎨10 if 𝜒 𝑉 = 0 and 𝜒 𝐻 ≠ 0 . (2) 𝑏1 , 𝑏0 ] with 𝑏𝑖 ∈ {0, 1} being the binary representation of the absolute ⎪ ⎪11 if 𝜒𝑉 ≠ 0 and 𝜒𝐻 =0 value of 𝜐 obtained when wavelet coefficient 𝜔 is quantized, bitplane 𝑗 ⎪12 otherwise is defined as the set of bits 𝑏𝑗 from all coefficients. The coding engine ⎩ codes all bits from bitplane 𝑀 −1 to bitplane 0, assuming that all indices A single context is employed for refinement bits since more complex 𝜐 are lower than 2𝑀 . approaches do not obtain significant coding gains, so 𝜙𝑟𝑒𝑓 (𝜐, 𝑗) = 13. In The coefficients are defined as significant or non-significant. A total 14 different contexts are employed, 9 for significance, 4 for sign, coefficient becomes significant at bitplane 𝑠 when the first non-zero and 1 for refinement coding. bit of its binary representation is found, more precisely, when 𝑏𝑠 = 1 Let 𝑃𝑠𝑖𝑔 (𝑏𝑗 = 0 | 𝜙𝑠𝑖𝑔 (𝜐, 𝑗)) denote the probability estimate for one with 𝑏𝑠′ = 0, 𝑀 > 𝑠′ > 𝑠. 𝑏𝑠 is called the significant bit for that context of significance coding. Conventional models devised for single- coefficient, and 𝑏𝑟 , 0 ≤ 𝑟 < 𝑠 are called refinement bits. Commonly, the threaded execution, like JPEG2000, typically set 𝑃𝑠𝑖𝑔 (⋅) = 0.5 at the coefficients are scanned multiple times in each bitplane, first coding beginning of coding and then adjust this probability depending on the bits of non-significant coefficients in previous bitplanes because every new bit coded. This procedure cannot be reproduced in BPC-PaCo these bits reduce most the image distortion [23]. Then, a second coding due to the parallel processing of coefficients. pass emits the refinement bits of the remaining coefficients. JPEG2000 further refines this procedure employing three coding passes. The first 3. Probability models is called Significance Propagation Pass (SPP) and codes the bits of non-significant coefficients that are neighbors of already significant 3.1. Stationary coefficients. The second is the magnitude refinement pass (MRP) and codes refinement bits. The last is the Cleanup Pass (CP) and codes The original model of BPC-PaCo is based on stationary probabilities. the bits of the remaining coefficients. Once a coefficient becomes Instead of adjusting probabilities adaptively depending on the incoming significant, its sign 𝑑 ∈ {+, −} is immediately coded to allow the data, this model uses fixed estimates that depend on the wavelet sub- decoder approximate 𝜔 as soon as possible. band, bitplane, and context. The model is thoroughly studied in [12]. The order in which the coefficients are scanned is a key difference The main idea is to collect statistics of images captured with the same between JPEG2000 and BPC-PaCo. Fig. 1 illustrates both orders for sensor in order to build a LUT that both the encoder and decoder share. a codeblock of 16 × 16 coefficients. In JPEG2000, a single thread The data produced by the same wavelet filter bank for images of the consecutively scans all the coefficients within the codeblock, producing same type are statistically similar [24–26], so the LUT can be employed an embedded bitstream in which each bit can only be decoded after to estimate the symbols’ probability of other images. the previous. BPC-PaCo employs one execution thread per each pair First, the probability mass function (pmf) of the quantization indices of columns, coding 32 coefficients simultaneously (in codeblocks of is computed with all the images in the training set. The pmf for subband 64 columns). The scanning is repeated three times in each bitplane, 𝑢 at bitplane 𝑗 is referred to as 𝐹𝑢 (𝜐 | 𝜙𝑠𝑖𝑔 (𝜐, 𝑗)) for the contexts of 2 F. Aulí-Llinàs, J. Bartrina-Rapesta and M. Hernández-Cabronero Signal Processing: Image Communication 112 (2023) 116914 Fig. 1. Scanning orders employed by (a) the original tier-1 coding stage of JPEG2000 standard, and (b) the highly parallel engine BPC-PaCo. significance coding. The support of this pmf is [0, … , 2𝑗+1 − 1] because results can be employed to update the probability estimate of each it considers coefficients 𝜐 ∈ [0, 2𝑗+1 ). Then, the probability that 𝑏𝑗 = 0 context. Fig. 2 illustrates the state machine used in our approach. is determined as It has 64 states depicted with circles. Transitions of MPSs and LPSs 𝑗 −1 2∑ are respectively depicted in blue and red arrows. The coding of an 𝐹𝑢 (𝜐 | 𝜙𝑠𝑖𝑔 (𝜐, 𝑗)) MPS increases the probability estimate linearly from 0.5 to 0.992, 𝜐=0 whereas coding an LPS decreases the estimate exponentially. Similar 𝑃𝑠𝑖𝑔 (𝑏𝑗 = 0 | 𝜙𝑠𝑖𝑔 (𝜐, 𝑗)) = . (3) 2𝑗+1 ∑−1 strategies are employed in other image codecs (such as the MQ coder 𝐹𝑢 (𝜐 | 𝜙𝑠𝑖𝑔 (𝜐, 𝑗)) of JPEG2000 [12]). It has been devised empirically with a large dataset 𝜐=0 to achieve high coding efficiency regardless of the image type. These probabilities populate the LUT for significance coding, which Algorithm 1 describes the three coding passes carried out by BPC- is accessed as 𝑢 [𝑗][𝜙𝑠𝑖𝑔 (⋅)]. The LUTs for refinement and sign coding PaCo when encoding. Decoding is the inverse procedure, so it is not are derived similarly. Through these LUTs, the coding procedure com- detailed herein. These coding passes are called consecutively in each putes the coefficient’s context and then accesses the corresponding LUT bitplane (not shown in the algorithm). The algorithm is described from to obtain the estimate. No further operations are required since the the point of view of a single execution flow (i.e., a thread) that codes LUTs are not updated during the coding process, so the computational the data of two adjacent columns. Nonetheless, note that the execution complexity of such a strategy is very low. in the GPU runs all threads of the codeblock in parallel, advancing their execution synchronously. The procedures in Algorithm 1 receive 3.2. Finite state machine the bitplane and thread as parameters. The bitplane is employed to emit the corresponding bit and to compute the context, whereas the Adapting the probability estimates with a finite state machine is thread is employed to compute the processed columns. The two first a widely employed technique in image and video coding [8,22,27]. lines in each coding pass embody the scanning order. Then, SPP(⋅) and Each state holds a probability estimate for the most probable symbol CP(⋅) check whether the coefficient has to be coded in that pass or not. (MPS), in the range [0.5, 1), and has two transitions to other states. One Quantization indices and coefficients are respectively referred to as 𝜐𝑦,𝑥 of the transitions is employed when coding the MPS, and the other and 𝜔𝑦,𝑥 following the same notation as above but denoting the position when coding the least probable symbol (LPS). Each context points at within the codeblock. If the coefficient needs to be coded, ACencode(⋅) one state. They are commonly initialized at the state with the lowest is called. If the coefficient is significant, sign coding also calls this pro- probability (i.e., 0.5). Every time a new symbol is coded, a transition cedure with its corresponding context (line 6 in both SPP(⋅) and CP(⋅)). to a new state with a higher (lower) probability in the case of an Refinement coding is similar but without sign coding. ACencode(⋅) is MPS (LPS) is carried out. In general, the state machine contains a also executed in parallel and synchronously for all threads. If a thread series of states that increase the probability estimate very rapidly at the does not call this procedure, it remains idle until the remaining threads beginning of coding while MPSs are found, and then the probabilities finish its processing. In all coding passes, ACupdate(⋅) is called just are more finely adjusted as more data are processed.1 after the coefficient is coded (also in parallel and synchronously for all Such a state machine works well when transitions among states threads). The parameter given to this procedure is thread 𝑡, although are carried out for every new symbol coded, which is not feasible it is received as context 𝑐 in Algorithm 2. Whereas Algorithm 1 and in BPC-PaCo. The threads processing coefficients in parallel cannot ACencode(⋅) in Algorithm 2 use one thread per each pair of columns, share information about the symbols that are currently coding because ACupdate(⋅) uses the same threads to update the probabilities of all that would entail causal relations among them, disrupting the parallel contexts in parallel. As there are only 14 contexts, threads 𝑡 ≥ 15 do processing. However, once the coefficients are processed, the coding not contribute to the updating operation and are idle during this step. Algorithm 2 describes the operations related to the probability 1 We refer the reader to [12, Figure 2] for an illustration of the state model that are carried out by the arithmetic coder. The first line in machine employed in the MQ coder of JPEG2000. ACencode(⋅) sets probability 𝑝, employed to code the interval. In this 3 F. Aulí-Llinàs, J. Bartrina-Rapesta and M. Hernández-Cabronero Signal Processing: Image Communication 112 (2023) 116914 Fig. 2. Finite state machine employed to estimate probabilities of future symbols. Each state is depicted with a gray circle. The estimated probability of the MPS symbol associated with each state is depicted in the vertical axis. Blue and red lines indicate transitions when coding an MPS and LPS, respectively. Algorithm 1 BPC-PaCo with adaptive prob. models Algorithm 2 Arithmetic coder (relevant operations) SPP(𝑗 bitplane, 𝑡 thread) ACencode(𝑠 symbol, 𝑐 context, 𝑡 thread) { 1: for 𝑦 ∈ [0, numRows − 1] do 𝑃 ′ [[𝑐]] ∕ ∗ finite state machine ∗ ∕ 1: 𝑝 ← 2: for 𝑥 ∈ [𝑡 ⋅ 2, 𝑡 ⋅ 2 + 1] do 𝑃 ′′ [𝑐] ∕ ∗ sliding window ∗ ∕ 3: if 𝜐𝑦,𝑥 is not significant AND 𝜙𝑠𝑖𝑔 (𝜐𝑦,𝑥 , 𝑗) ≠ 0 then 2: code(𝑠, 𝑝, 𝑡) ∕ ∗ interval coding − see [17, Algorithm 1] ∗ ∕ 4: ACencode(𝑏𝑗 , 𝜙𝑠𝑖𝑔 (𝜐𝑦,𝑥 , 𝑗), 𝑡) 3: if 𝑠 = 0 then 5: if 𝑏𝑗 = 1 then 4: 0 [𝑐] ← 0 [𝑐] + 1 6: ACencode(𝑑, 𝜙𝑠𝑖𝑔𝑛 (𝜔𝑦,𝑥 , 𝑗), 𝑡) 5: end if 7: end if 6:  [𝑐] ←  [𝑐] + 1 8: end if 9: ACupdate(t) ACupdate(𝑐 context) ∕ ∗ finite state machine ∗ ∕ 10: end for 1: if 𝑐 < 15 AND  [𝑐] > 0 then 11: end for 2: [𝑐] ← LPStransition( [𝑐] − 0 [𝑐]) 3: [𝑐] ← MPStransition(0 [𝑐]) MRP(𝑗 bitplane, 𝑡 thread) 4:  [𝑐] ← 0 1: for 𝑦 ∈ [0, numRows − 1] do 5: 0 [𝑐] ← 0 2: for 𝑥 ∈ [𝑡 ⋅ 2, 𝑡 ⋅ 2 + 1] do 6: end if 3: if 𝜐𝑦,𝑥 is significant in 𝑗 ′ > 𝑗 then ACupdate(𝑐 context) ∕ ∗ sliding window ∗ ∕ 4: ACencode(𝑏𝑗 , 𝜙𝑟𝑒𝑓 (𝜐𝑦,𝑥 , 𝑗), 𝑡) 1: if 𝑐 < 15 AND  [𝑐] > 0 then 5: end if 2: 𝑃 ′′ [𝑐] ← 0 [𝑐]∕ [𝑐] 6: ACupdate(t) 3: if 0 [𝑐] = −1 AND  [𝑐] ≥ 𝑊 then 7: end for 4: 0 [𝑐] ← 0 [𝑐] 8: end for 5: [𝑐] ←  [𝑐] CP(𝑗 bitplane, 𝑡 thread) 6: end if 1: for 𝑦 ∈ [0, numRows − 1] do 7: if  [𝑐] ≥ 2𝑊 then 2: for 𝑥 ∈ [𝑡 ⋅ 2, 𝑡 ⋅ 2 + 1] do 8:  [𝑐] ←  [𝑐] − [𝑐] 3: if 𝜐𝑦,𝑥 is not significant AND not coded in SPP then 9: [𝑐] ←  [𝑐] 4: ACencode(𝑏𝑗 , 𝜙𝑠𝑖𝑔 (𝜐𝑦,𝑥 , 𝑗), 𝑡) 10: 0 [𝑐] ← 0 [𝑐] − 0 [𝑐] 5: if 𝑏𝑗 = 1 then 11: 0 [𝑐] ← 0 [𝑐] 6: ACencode(𝑑, 𝜙𝑠𝑖𝑔𝑛 (𝜔𝑦,𝑥 ), 𝑡) 12: end if 7: end if 13: end if 8: end if 9: ACupdate(t) 10: end for 11: end for update the number of 0s and the total number of symbols coded for this context, which are stored in 0 [𝑐] and  [𝑐], respectively. These operations can be implemented as atomic increments in a GPU, so that even if two or more threads use the same context in the same step, the model, [𝑐] denotes the state of the corresponding context, whereas 𝑃 ′ result remains correct. is the probability associated with that state. Once 𝑝 is set, operations to The procedure ACupdate(⋅) employed in this model (second in Algo- code the interval with that probability are carried out via code(𝑠, 𝑝, 𝑡), rithm 2) updates the state of the context. If one or more symbols have which uses an independent arithmetic coder for each thread. This been coded with that context, the state is decreased by the number of procedure is not included in Algorithm 2 for simplicity, but can be LPSs coded (i.e.,  [𝑐]−0 [𝑐]) and then increased by the number of MPSs consulted in [17, Algorithm 1]. The remaining lines in ACencode(⋅) coded (i.e., 0 [𝑐]). Afterwards, 0 [𝑐] and  [𝑐] are reset to zero. 4 F. Aulí-Llinàs, J. Bartrina-Rapesta and M. Hernández-Cabronero Signal Processing: Image Communication 112 (2023) 116914 3.3. Sliding window Table 1 Evaluation of lossless coding performance. A variable-size sliding window [28,29] is employed by this last BPC-PaCo model of probabilities. The main idea is to use statistics of the last HT Station- State Sliding JP2 JP2 ary machine window coded symbols, enclosed in this window, to estimate the probability of the incoming. This strategy assumes that the new symbols have Portrait 3.81 4.0 3.94 3.94 3.82 Cafeteria 4.69 4.97 4.79 4.80 4.69 a similar distribution to the last ones. The window has between 𝑊 Fruit 3.96 4.22 4.15 4.06 3.96 and 2𝑊 symbols, approximately, except at the beginning of coding. Wine 3.94 4.20 4.12 4.05 3.94 With some abuse of notation, let the number of 0s and total number ISO 12640-1 Bicycle 3.90 4.18 4.09 4.04 3.93 of symbols coded within this window be denoted by 0 [𝑐] and  [𝑐], Orchid 3.45 3.69 3.68 3.56 3.46 respectively. When  [𝑐] ≥ 2𝑊 , the window size is reduced subtracting Music. 5.34 5.63 5.52 5.42 5.29 Candle 4.75 5.03 4.87 4.86 4.75 the statistics of the first 𝑊 symbols, approximately, which are stored Average 4.23 +0.27 +0.16 +0.11 +0.00 in 0 [𝑐] and [𝑐] for the 0s and the total, respectively. Like the previous model, probability estimates are updated after forest1 6.20 6.51 6.16 6.25 6.10 forest2 6.28 6.59 6.23 6.33 6.18 processing 32 coefficients in parallel, so the procedures detailed in Al- aerial urban1 5.54 5.88 5.55 5.68 5.50 gorithm 1 hold for this approach too. Algorithm 2 details the operations urban2 5.20 5.52 5.23 5.33 5.16 required to compute the probability and update the window. Procedure Average 5.80 +0.32 −0.01 +0.09 −0.07 ACencode(⋅) carries out the same operations for both models except the A 6.37 6.68 6.30 6.40 6.27 first, which in this case uses 𝑃 ′′ [𝑐] to set the probability 𝑝 corresponding B 6.48 6.79 6.45 6.52 6.37 to that context. 𝑃 ′′ [𝑐] is updated after checking that at least one symbol X-ray C 6.35 6.66 6.29 6.38 6.25 has been coded with this context in the first operation of ACupdate(⋅) Average 6.40 +0.31 +0.05 +0.03 −0.11 (third procedure in Algorithm 2). This updating is expressed as a cuprite 7.01 7.32 6.98 7.09 6.90 division, though in practice it can be implemented with bit shifts and jasper 7.66 7.98 7.61 7.74 7.52 AVIRIS additions depending on the interval partitioning procedure employed. lunarLake 6.91 7.22 6.89 6.98 6.81 We also note that the result of the division may never reach 1. At the Average 7.19 +0.31 −0.03 +0.08 −0.12 beginning of coding, all array positions in 𝑃 ′′ [𝑐] are initialized to 0.5 except for the first, which is set to 0.9. This first context is initialized to 0.9 because it is employed to code the significance bits of coefficients that do not have any significant neighbor, so they are generally 0 too. and HT JPEG2000. Each image is coded at 100 equally spaced rates. This increases slightly the efficiency of the coder. The conditional in Quality is evaluated in terms of peak signal to noise ratio (PSNR). Fig. 3 line 3 checks if the number of symbols coded in the window exceeds reports the results achieved by one image of each corpus. Similar results 𝑊 for the first time (via 0 [𝑐] that is initialized to −1). If so, sets hold for the others. Results are reported as the PSNR difference between variables 0 [𝑐] and [𝑐]. Every time the window contains 2𝑊 symbols that obtained by the evaluated method and that of JPEG2000. The or more, it is half emptied as detailed in lines 7–12. Experimental horizontal straight line in each plot is the performance of JPEG2000, evidence indicates that 𝑊 = 256 obtains high coding efficiency. while the remaining represent the evaluated methods. Results below (above) this horizontal line indicate lower (higher) performance than 4. Experimental results that of JPEG2000. The results of Fig. 3 suggest that the state machine model, which is similar to that employed by JPEG2000, obtains low The experimental tests below utilize 4 corpora with different types performance when applied to parallel processing. Differences vary of images to consider a wide variety of scenarios. The first corpus is the depending on the rate and image type. This seems to indicate that the ISO 12640-1, which has eight color images of 2048 × 2560 and 8 bits transitions among states, which are necessarily performed only once for per sample (bps). The images in the second corpus are captured with every 32 coefficients coded, diminishes the precision of the probability an aerial sensor covering vegetation and urban areas, are gray scale, 8 estimates. Contrarily, the sliding window model achieves the highest bps and have a size of 7200 × 5000. The third corpus belongs to the performance at medium and high rates in three of the four types of medical field. It consists of three X-ray angiography images with a size images evaluated. At these rates, this model obtains gains in the order of 512 × 512 with 15 components and 12 bps. The last corpus con- of 0.5 dB with respect to JPEG2000, while at low rates it is in general sists of three AVIRIS (Airbone Visible/Infrared Imaging Spectrometer) less than 0.2 dB inferior to the standard, suggesting that very precise hyperspectral images of 512 × 512 with 224 components and 16 bps probability estimates are obtained when enough data are within the that are provided by NASA. This corpora is the same to that employed window (i.e., from medium to high rates). Compared to HT JPEG2000, in the original BPC-PaCo paper [17] to allow comparison. All codecs the sliding window model obtains similar performance at low rates but except HT JPEG2000, are implemented in our Java framework [30]. much higher at medium and high rates. Similar results are obtained Results for HT JPEG2000 are obtained with Kakadu [31]. Codeblocks of for codeblocks of smaller size (not shown in the figure), with the 64 × 64 and 5 levels of irreversible (reversible) wavelet transformation performance achieved by the two adaptive approaches being slightly are employed for the lossy (lossless) regime.2 Training is neither needed more penalized than that achieved by the stationary model because by (HT) JPEG2000 nor by BPC-PaCo using either of the two models fewer data are coded and so the probabilities are adjusted with less proposed in this work, since probabilities are adaptively adjusted while precision. The abrupt variations in coding performance seen in Fig. 3 coding new data. The training set required by the stationary model for some of the images are due to the statistical behavior of the data includes all images of each corpus except the one that is evaluated. coded in each coding pass, which is handled differently depending on the employed probability model. First, lossy coding performance is assessed. The stationary, state The evaluation of lossy coding performance is completed with the machine, and sliding window models are compared against JPEG2000 test reported in Fig. 4, which compares the above-mentioned methods against JPEG XS (ISO/IEC 21122). JPEG XS is a wavelet-based im- 2 The proposed methods do not employ the bit stuffing technique deployed age compression standard tailored for very low complexity and high in JPEG2000 that avoids coding bytes with a 0𝑥𝐹 𝐹 value. This does not signif- throughput. Results are obtained with the JPEG XS Reference Software icantly affect the rate–distortion comparisons since this technique increments using profile ‘‘High444.12.’’ As seen in the figure, the performance negligibly the length of the codestream. achieved by this standard is lower than that obtained by the proposed 5 F. Aulí-Llinàs, J. Bartrina-Rapesta and M. Hernández-Cabronero Signal Processing: Image Communication 112 (2023) 116914 Fig. 3. Evaluation of lossy coding performance for images of different corpora: (a) ‘‘Musicians’’ of the ISO12640-1 corpus, (b) ‘‘forest2’’ of the aerial corpus, (c) ‘‘B’’ of the X-ray corpus, and (d) ‘‘jasper’’ of the AVIRIS corpus. average difference between the method evaluated and JPEG2000. The best results are depicted in bold. The sliding window model obtains the lowest rate for almost all images, achieving improvements about 0.1 bps with respect to JPEG2000. Again, these results suggest that this model is highly efficient at high rates, when more data are available. This is also seen through the gains obtained for the X-ray and AVIRIS images, which are slightly higher than those achieved for the natural and aerial images because X-ray and AVIRIS images have higher bit- depths. The state machine model achieves inferior performance to that of JPEG2000, similar to that achieved by the original stationary model. HT JPEG2000 obtains lower performance, suggesting that it is more indicated for lossy regimes. Third, computational complexity is analyzed. It is approximated as the execution time spent by the bitplane and entropy coder when executed with a single thread.3 This provides an idea of the complexity burden imposed by each model as compared to the stationary, which is the simplest computationally. Our experience indicates that this Fig. 4. Evaluation of lossy coding performance, including JPEG XS, for the ‘‘Musicians’’ burden is similar to that achieved with GPU implementations. This image of the ISO12640-1 corpus. comparison only considers the complexity of the probability models proposed for BPC-PaCo to evaluate its complexity differences, leaving apart JPEG2000 and HT JPEG2000 since they utilize different scanning methods, in part due to the lack of arithmetic coding. Similar results orders and entropy coders. A workstation with an i7-6700K CPU at are obtained for the other images. 4.00 GHz and 32 GB of DDR4 RAM is employed to carry out these Second, lossless coding performance is appraised. Table 1 reports the results for all images. They are expressed in bps of the compressed 3 The lowest execution time of 10 execution runs is employed, since that file except for the average of each corpus. These rows report the corresponds with the execution that is less disrupted. 6 F. Aulí-Llinàs, J. Bartrina-Rapesta and M. Hernández-Cabronero Signal Processing: Image Communication 112 (2023) 116914 Fig. 5. Evaluation of computational complexity for different corpora: (a) ISO12640-1, (b) aerial, (c) X-ray, and (d) AVIRIS. tests. Fig. 5 shows the average results achieved in lossy regime for each to JPEG2000. In terms of computational complexity, experimental tests corpus. The left and right column depicted for each method represent indicate a moderate increase of 10%, approximately. Although this encoding and decoding time, respectively. Results hold for lossless work is based on our previous algorithm BPC-PaCo, conclusions may regimes as well. As seen in the figure, the complexity increase of the also be extended to other parallel codecs. Future work will implement sliding window model is slightly lower than that of the state machine, the sliding window model in a modern GPU to assess its complexity requiring an approximate increase of 10% with respect to the stationary and performance when executed in a highly parallel processor. model. In general, encoding takes slightly more time than decoding in all tests due to operations required by the rate–distortion optimization CRediT authorship contribution statement process. Francesc Aulí-Llinàs: Conceptualization, Methodology, Validation, 5. Conclusions Investigation, Writing – original draft, Writing – review & editing. Joan Bartrina-Rapesta: Methodology, Investigation, Writing – review This work evaluates two probability models for a wavelet-based, & editing. Miguel Hernández-Cabronero: Methodology, Investigation, highly-parallel image coding architecture. The main novelty of these Writing – review & editing. models is that they adaptively adjust the probabilities while coding data instead of using training as required in previous work. The first pro- Declaration of competing interest posed model utilizes a finite state machine to adaptively adjust proba- bilities. It is inspired in the same mechanism employed in conventional image and video codecs. Experimental results indicate regular coding The authors declare that they have no known competing finan- efficiency, suggesting that this model is not suitable for fine-grain cial interests or personal relationships that could have appeared to parallelism. The second proposed model employs a sliding window, a influence the work reported in this paper. completely different mechanism that determines probability estimates based on statistical data from past symbols. Experimental results sug- Data availability gest that the sliding window is well suited for fine-grain parallelism, achieving higher compression efficiency than that of the original BPC- Two of the image corpora employed (ISO 12640-1 and NASA PaCo and, at medium to high rates, than that of JPEG2000. This model AVIRIS) are publicly available, and the other two corpora (aerial and obtains gains of approximately 0.1 bps in lossless coding as compared X-ray) are provided by institutions without permission to share them. 7 F. Aulí-Llinàs, J. Bartrina-Rapesta and M. Hernández-Cabronero Signal Processing: Image Communication 112 (2023) 116914 Acknowledgments [14] Y. Zhang, C. Lu, A highly parallel hardware architecture of table-based CABAC bit rate estimator in an HEVC intra encoder, IEEE Trans. Circuits Syst. Video Technol. 29 (5) (2019) 1544–1558. This work has been partially supported by the Spanish Ministry [15] D. Karwowski, Precise probability estimation of symbols in VVC CABAC entropy of Science, Innovation and Universities (MICIU) and by the European encoder, IEEE Access 9 (2021) 65361–65368. Regional Development Fund (FEDER) under Grants RTI2018-095287- [16] D. Taubman, A. Naman, R. Mathew, High throughput block coding in the B-I00 and PID2021-125258OB-I00, by the Catalan Government under HTJ2K compression standard, in: Proc. IEEE International Conference on Image Grants 2018-BP-00008 and 2017SGR-463, and by the Horizon 2020 Processing, 2019, pp. 1079–1083. [17] F. Auli-Llinas, P. Enfedaque, J.C. Moure, V. Sanchez, Bitplane image coding under the Marie Skłodowska-Curie grant agreement #801370. with parallel coefficient processing, IEEE Trans. Image Process. 25 (1) (2016) 209–219. References [18] C. de Cea-Dominguez, J.C. Moure, J. Bartrina-Rapesta, F. Auli-Llinas, GPU- oriented architecture for an end-to-end image/video codec based on JPEG2000, [1] D. Huffman, A method for the construction of minimum redundancy codes, Proc. IEEE Access 8 (2020) 68474–68487. IRE 40 (1952) 1098–1101. [19] A. Said, W.A. Pearlman, A. new, fast, And efficient image codec based on set [2] J. Rissanen, Generalized Kraft inequality and arithmetic coding, IBM J. Res. Dev. partitioning in hierarchical trees, IEEE Trans. Circuits Syst. Video Technol. 6 (3) 20 (3) (1976) 198–203. (1996) 243–250. [3] J. Duda, K. Tahboub, N.J. Gadgil, E.J. Delp, The use of asymmetric numeral [20] W.A. Pearlman, A. Islam, N. Nagaraj, A. Said, Efficient, Low-complexity image systems as an accurate replacement for huffman coding, in: Proc. IEEE Picture coding with a set-partitioning embedded block coder, IEEE Trans. Circuits Syst. Coding Symposium, 2015, pp. 65–69. Video Technol. 14 (11) (2004) 1219–1235. [4] G. Lakhani, Modified JPEG huffman coding, IEEE Trans. Image Process. 12 (2) [21] D. Taubman, High performance scalable image compression with EBCOT, IEEE (2003) 159–169. Trans. Image Process. 9 (7) (2000) 1158–1170. [5] J.-S. Lee, J.-H. Jeong, T.-G. Chang, An efficient method of huffman decoding for [22] D.S. Taubman, M.W. Marcellin, JPEG2000 Image Compression Fundamentals, MPEG-2 AAC and its performance analysis, IEEE Trans. Speech Audio Process. Standards and Practice, Kluwer Academic Publishers, Norwell, Massachusetts 13 (6) (2005) 1206–1209. 02061 USA, 2002. [6] G. Lakhani, Modifying JPEG binary arithmetic codec for exploiting inter/intra- [23] F. Auli-Llinas, M.W. Marcellin, Scanning order strategies for bitplane image block and DCT coefficient sign redundancies, IEEE Trans. Image Process. 22 (4) coding, IEEE Trans. Image Process. 21 (4) (2012) 1920–1933. (2013) 1326–1339. [24] F. Auli-Llinas, Stationary probability model for bitplane image coding through [7] A. Skodras, C. Christopoulos, T. Ebrahimi, The JPEG2000 still image compression local average of wavelet coefficients, IEEE Trans. Image Process. 20 (8) (2011) standard, IEEE Signal Process. Mag. 18 (5) (2001) 36–58. 2153–2165. [8] D. Marpe, H. Schwarz, T. Wiegand, Context-based adaptive binary arithmetic [25] R.W. Buccigrossi, E.P. Simoncelli, Image compression via joint statistical char- coding in the H.264/AVC video compression standard, IEEE Trans. Circuits Syst. acterization in the wavelet domain, IEEE Trans. Image Process. 8 (12) (1999) Video Technol. 13 (7) (2003) 620–636. 1688–1701. [9] G.J. Sullivan, J.-R. Ohm, W.-J. Han, T. Wiegand, Overview of the high efficiency [26] F. Auli-Llinas, M.W. Marcellin, J. Serra-Sagrista, J. Bartrina-Rapesta, Lossy-to- video coding (HEVC) standard, IEEE Trans. Circuits Syst. Video Technol. 22 (12) lossless 3D image coding through prior coefficient lookup tables, ELSEVIER Inf. (2012) 1649–1668. Sci. 239 (1) (2013) 266–282. [10] M. Dyer, D. Taubman, S. Nooshabadi, A.K. Gupta, Concurrency techniques for [27] J.L. Mitchell, W.B. Pennebaker, Software implementations of the Q-Coder, IBM arithmetic coding in JPEG2000, IEEE Trans. Circuits Syst. I 53 (6) (2006) J. Res. Dev. 32 (1988) 753–774. 1203–1212. [28] E. Belyaev, A. Turlikov, K. Egiazarian, M. Gabbouj, An efficient adaptive binary [11] M. Rhu, I.-C. Park, Optimization of arithmetic coding for JPEG2000, IEEE Trans. arithmetic coder with low memory requirement, IEEE J. Sel. Top. Signal Process. Circuits Syst. Video Technol. 20 (3) (2010) 446–451. 7 (6) (2013) 1053–1061. [12] F. Auli-Llinas, M.W. Marcellin, Stationary probability model for microscopic [29] F. Auli-Llinas, Context-adaptive binary arithmetic coding with fixed-length parallelism in JPEG2000, IEEE Trans. Multimedia 16 (4) (2014) 960–970. codewords, IEEE Trans. Multimedia 17 (8) (2015) 1385–1390. [13] D. Zhou, J. Zhou, W. Fei, S. Goto, Ultra-high-throughput VLSI architecture of [30] F. Auli-Llinas, BOI codec, 2022, URL https://deic.uab.cat/~francesc/software/ H.265/HEVC CABAC encoder for UHDTV applications, IEEE Trans. Circuits Syst. boi. Video Technol. 25 (3) (2015) 497–507. [31] D. Taubman, Kakadu software, 2022, URL http://www.kakadusoftware.com. 8