# On the Utilization of Reversible Colour Transforms for Lossless 2-D Data Compression
## 2 Burrows-Wheeler Compression Algorithm (BWCA)  
The classical Burrows-Wheeler Compression Algorithm (BWCA) was presented by [PERSON] in [PERSON] (1976) and is shown in Figure 1. It comprised of four stages which are explained briefly below and are depicted in Figure 2. A comprehensive examination of the scheme and its various stages is presented in the works of [PERSON] et al. (2018); [PERSON] et al. (2018); [PERSON] et al. (2018); [PERSON] et al. (2018); [PERSON] et al. (2018). Currently, various variants of the algorithm have been developed by modifying either the complete scheme or its various stages [PERSON] et al. (2018); [PERSON] et al. (2018); [PERSON] et al. (2018). Figure 1: The classical Burrows–Wheeler Compression Algorithm (BWCA) [PERSON] (1976). Figure 2: (**a**) Generated permutations from string (**b**) Permutations sorted with the final column containing the output string (**c**) M-Term Pursuit (MTF) encoding of string followed by Run-Length Encoding (RLE) in (**d**). The source data is input to the first stage of the Burrows-Wheeler Transform (BWT). The BWT is a lossless transform invented by [PERSON] and [PERSON] for text compression [19]. By increasing the recurrence of image pixels, redundancy is enhanced which in turns leads to better compression. In the case of BWCA, it is the BWT that generates runs of symbols which is encoded by the MTF transform in such a way that it increases the occurrence of zeros. The later stages of RLE and entropy coding the various stages of BWCA are detailed as follows in order to elucidate their effectiveness for lossless transformation and compression. The BWCA is based on the Burrows-Wheeler Transform (BWT) with secondary stages taking advantage of it [19]. The BWT is a reversible transform and creates chains of symbol repetitions by lexicographically sorting the permutations of the input string or pixels. The output contains long runs of the symbols which allows for the later stages of MTF and RLE to easily compress these runs effectively [17]. Figure 2 shows the transformation of the example string 'bananana' for clarity. In the first step of BWT, the strings permutations are created by circular left shifting one element at a time. Figure 2a shows all the permutations. Figure 2b depicts the lexicographical sorting of the matrix in Figure 2a. The permutations are sorted in ascending alphabetical order where order is checked for each column of the string. For the example string, the original string position is now 5 and the last column of the sorted matrix contains the string 'nnnbaaaa' having repetitions of alphabets 'n' and 'a'. Large size of input data will create better runs however, it will induce computation cost as memory and computations increase exponentially. The string 'nnnbaaaa' is given to the MTF encoder stage in the reverse order to put it in ascending order. The MTF stage encodes a symbol from the list of all symbols. Its position is then moved to the front of the list so that if the same symbol is being repeated, it will get an index of \"zero\" from the list. Through this method, more runs of zeros are generated for repeating symbols. As shown in Figure 2c, the string is encoded in conjunction with a list of all symbols. Currently the list is 'abn'. The position of alphabet 'a' is index number '0'. The four 'a' runs are encoded as '0000'. When the alphabet 'b' is reached, its position in the list is checked, which is 2 and the run is encoded as '00001'. the symbol 'b' is moved to the front of the list such that if it is repeated, more '0' indexes will be produced. The MTF encoder through this principle aims at increasing the runs of zeros and ones. The RLE stage then encodes these runs. RLE-0 is usually employed and other symbol runs are not encoded by RLE as the runs of zeros are usually more. Different algorithms are presented for this RLE. [PERSON] [17] presented the RLE-BIT and RLE-EXP algorithms while [PERSON] and [PERSON] [19] used the Zero Run Transform (RLE-0). The proposed model uses the RLE-0 scheme.