[2D compression] | conditional image run length coding

1, Run length encoding

The idea behind this data compression method is: if a data item d appears n times continuously in the input stream, replace n times with a single pair of nd. Then, the continuous occurrence of a data item is called run length N, and this method of data compression is called run length coding or RLE. We first apply this idea to text compression, and then apply it to image compression.

2, Image run length coding

1. Conditional image run length coding method

Assuming an image with n gray levels, this method first assigns an n-bit code to each pixel according to the nearest neighbor of each pixel. It then converts the n-bit code into a long string and calculates the run length. Run the prefix code assigned to the compressed stream. In this method, each scan line in the image is regarded as a second-order Markov model. In such a model, the value of the current data item only depends on its past two neighbors, not necessarily two direct neighbors. A set of training images is used to calculate each pair of possible values of neighbors a and B, that is, the number of times each value of X appears. If a and B have similar values, it is natural to expect x to have similar values. If a and B have very different values, we expect x to have many different values, and the probability of each value is very low

2. Implementation of conditional image run length coding code

def int2bin(n, count):
    """returns the binary of integer n,using count number of digits"""
    return "".join([str((n >> y) & 1) for y in range(count - 1, -1, -1)])

class Run_Length_Encoding:
    def __init__(self):
        self.lowbit = '0'
        self.highbit = '1'
        self.compression_factor_text = 3
        self.escape_character = '@'
        self.alphabet_bit = 14

    def condictional_run_length_encoding_image(self, input: list):
        import random
        approch_run_length_encoding = self.run_length_encoding_grayimage(input)
        # approch_run_length_encoding = [random.randint(0, 15) for i in range(100)]  # Do a random test
        from Huffman import Huffman
        dic = Huffman().dictionary(approch_run_length_encoding)
        Huffmandic = Huffman().huffman_code(dic)

        A_list = [elem[:] for elem in dic.keys()]
        B_list = [elem[:] for elem in dic.keys()]
        C_list = []
        Out_list = []
        Name_list = []

        for i in A_list:
            for j in B_list:
                for c in range(len(approch_run_length_encoding) - 2):
                    if approch_run_length_encoding[c] == int(i) and approch_run_length_encoding[c + 1] == int(j):
                        C_list.append(approch_run_length_encoding[c + 2])
                C_dic = Huffman().dictionary(C_list)
                C_dic = Huffman().huffman_code(C_dic)
                C_list = []
                Out_list.append(C_dic) if len(C_dic) != 0 else None
                Name_list.append(i + "+" + j) if len(C_dic) != 0 else None

        condictional_rle_outstring = int2bin(approch_run_length_encoding[0], self.alphabet_bit) + int2bin(
            approch_run_length_encoding[1], self.alphabet_bit)

        Huffman_outstring = ''

        for k in range(2, len(approch_run_length_encoding)):
            alphabet = Out_list[Name_list.index(
                str(approch_run_length_encoding[k - 2]) + "+" + str(approch_run_length_encoding[k - 1]))]
            condictional_rle_outstring += alphabet[str(approch_run_length_encoding[k])]

        for k in range(len(approch_run_length_encoding)):
            Huffman_outstring += Huffmandic[str(approch_run_length_encoding[k])]

        print("Huffman_outstring : ", len(Huffman_outstring), Huffman_outstring)
        print("condictional_rle_outstring : ", len(condictional_rle_outstring), condictional_rle_outstring)

input =  [[0, 0, 0, 1], [1, 1, 1, 0], [1, 1, 1, 0]]
output :  [3, 4, 1, 3, 1]


The above is what we want to talk about today. This paper only briefly introduces the relevant definitions of conditional image run length coding and the implementation method of simple code.

reference resources

[1] Salomon, David, and Giovanni Motta. Handbook of data compression. London; New York: Springer, 2010.
[2] H. Gharavi, "Conditional Run-Length and Variable-Length Coding of Digital Pictures," in IEEE Transactions on Communications, vol. 35, no. 6, pp. 671-677, June 1987, doi:10.1109/TCOM.1987.1096817.

Part of this article refers to the Handbook of Data Compression, which is only for learning and research. If you like, please support the purchase of authentic books. The code reference blog for the Huffman section of this article Implementation of Huffman coding with Python code . This article is about run_ length_ encoding_ The implementation of grayimage refers to the image run length coding blog mentioned above.
If you reprint this article, please contact the original author for authorization. At the same time, please indicate that this article is from Chiyu zuiyuan blog.

Tags: Python Algorithm Computer Vision

Posted by Quevas on Mon, 16 May 2022 22:50:47 +0300