dippykit.coding module

Module of various image coding functions

This module contains an assortment of functions that encode or decode images in popular or useful manners.

dippykit.coding.huffman_encode(im_vec: numpy.ndarray, symbol_code_dict: typing.Dict[int, numpy.ndarray] = None) → typing.Tuple[[numpy.ndarray, int, typing.Dict[int, numpy.ndarray]], typing.Dict[int, float]][source]

Encodes an integer vector using huffman encoding

Given a vector (one-dimensional ndarray) with either signed or unsigned integer dtype, this function huffman encodes it. The process for this is the following:

  1. If no symbol-code dictionary is provided, create one. The symbol code dictionary (symbol_code_dict) correlates the values in the input vector to the variable-bit-length values in the output vector. In the case that no symbol-code dictionary was provided, a symbol-probability dictionary (symbol_probability_dict) is generated. This symbol probability dictionary has a key set of all unique symbols in im_vec and a value set containing each unique symbol’s frequency in im_vec. The symbol-code dictionary is then generated using huffman_dict() with the symbol-probability dictionary as its argument. This symbol-code dictionary now contains the statistically optimal compressive encoding scheme.

  2. Translate the im_vec vector into its huffman encoded version by replacing each integer value with its appropriate bit sequence in the the symbol-code dictionary.

  3. Pack the bit sequence into a byte sequence (represented as a one-dimensional ndarray of dtype uint8). The last byte is right-padded with 0s if the number of bits in the bit sequence was not a perfect multiple of 8.

  4. Return the following data (in order) as a tuple:

    • byte sequence
    • the number of bits in the previous step’s bit stream
    • the symbol-code dictionary (symbol_code_dict)
    • the symbol-probability dictionary (symbol_probability_dict)

To reverse the huffman encoding, you can pass the first, third, and second returned values to the huffman_decode() function in that order. Optionally, (for optimal speed) pass the length of the original image vector (im_vec) to huffman_decode() as the init_arr_size keyword argument.

Parameters:
  • im_vec (numpy.ndarray) – A vector with either signed integer or unsigned integer dtype to be huffman encoded. With images, one can trivially make them vectors by using the numpy method im.reshape(-1).
  • symbol_code_dict (Dict[int, numpy.ndarray]) – (Optional) A dictionary with either a signed integer or unsigned integer key set and a value set of unique bit sequences (represented as one-dimensional ndarrays with boolean dtype).
Return type:

(numpy.ndarray, int, Dict[int, np.ndarray], Dict[int, float])
Returns:

A tuple containing the following, in order:

  • The huffman encoded byte sequence of the input im_vec
  • The number of bits needed to represent the encoded im_vec
  • The symbol-code dictionary which translates integer symbols to binary codes
  • The symbol-probability dictionary which translates integer symbols to probability weights

Examples:

>>> import numpy as np
>>> im = np.array([[  0, 255, 255,   0],
...                [255,   0,  64, 128]])
>>> im_vec = im.reshape(-1)
>>> im_vec
array([  0, 255, 255,   0, 255,   0,  64, 128])
>>> im_encoded, stream_length, symbol_code_dict, symbol_prob_dict = 
...         huffman_encode(im_vec)
>>> im_encoded
array([205, 202], dtype=uint8)
>>> np.unpackbits(im_encoded)
array([1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0], dtype=uint8)
>>> stream_length
15
>>> symbol_code_dict
{255: array([False]), 
 0: array([ True,  True]), 
 64: array([ True, False, False]), 
 128: array([ True, False,  True])}
>>> symbol_prob_dict
{0: 3, 
 64: 1, 
 128: 1, 
 255: 3}
dippykit.coding.huffman_decode(im_encoded: numpy.ndarray, symbol_code_dict: typing.Dict[int, numpy.ndarray], stream_length: int = -1, init_arr_size: int = -1) → numpy.ndarray[source]

Decodes a huffman encoded byte stream

Given a huffman encoded byte stream and a symbol-code dictionary, this function will decode the byte stream into its original form.

The huffman encoded byte stream (im_encoded) must be represented as a one-dimensional ndarray with dtype uint8. The symbol-code dictionary must be represented as a dictionary that maps either signed integer or unsigned integer symbols to ndarrays with boolean dtype (these ndarrays are the binary huffman codes that compose im_encoded).

The stream_length argument (optional) is an integer that represents the number of bits in im_encoded that actually represent the image vector. Often times, huffman encoding a vector yields a bit stream whose length is not a perfect multiple of 8, therefore the byte stream will be padded at the end with 0s. Specifying stream_length prevents against extra additional values that may arise from these padded 0s.

The init_arr_size argument (optional) is an integer that represents the number of elements that the user anticipates the decoded image vector to have. This value has no effect on the output of the function, its only purpose is to speed up computation. This value can be a rough estimate.

To huffman encode an image vector, see huffman_encode().

Parameters:
  • im_encoded (numpy.ndarray) – A one-dimensional ndarray of dtype uint8 composed of huffman encoded values.
  • symbol_code_dict (Dict[int, np.ndarray]) – A dictionary that maps either signed integer or unsigned integer symbols for the decoded image to binary huffman codes present in the im_encoded vector.
  • stream_length (int) – (Optional) The number of bits from the im_encoded vector to decode.
  • init_arr_size (int) – (Optional) The anticipated number of elements in the decoded image. This parameter has no effect on the return value of this function. It only reduces the computation time when it is close to the actual number of elements in the decoded image.
Return type:

numpy.ndarray
Returns:

The decoded image vector, represented as a one-dimensional ndarray with dtype int64.

Examples:

>>> import numpy as np
>>> im = np.array([[  0, 255, 255,   0],
...                [255,   0,  64, 128]])
>>> im_vec = im.reshape(-1)
>>> im_vec
array([  0, 255, 255,   0, 255,   0,  64, 128])
>>> im_encoded, stream_length, symbol_code_dict, symbol_prob_dict = 
...         huffman_encode(im_vec)
>>> huffman_decode(im_encoded, symbol_code_dict)
array([  0, 255, 255,   0, 255,   0,  64, 128, 255], dtype=int64)
>>> huffman_decode(im_encoded, symbol_code_dict, stream_length)
array([  0, 255, 255,   0, 255,   0,  64, 128], dtype=int64)
>>> huffman_decode(im_encoded, symbol_code_dict, stream_length, 
...         im_vec.size)
array([  0, 255, 255,   0, 255,   0,  64, 128], dtype=int64)
>>> huffman_decode(im_encoded, symbol_code_dict, stream_length, 1)
array([  0, 255, 255,   0, 255,   0,  64, 128], dtype=int64)
>>> huffman_decode(im_encoded, symbol_code_dict, stream_length, 10000)
array([  0, 255, 255,   0, 255,   0,  64, 128], dtype=int64)
dippykit.coding.huffman_dict(symbol_probability_dict: typing.Dict[int, float]) → typing.Dict[int, numpy.ndarray][source]

Generates a symbol-code dictionary using huffman encoding

Given a dictionary where each key is a symbol in some integer vector and the corresponding values are floating point weights of the frequency of occurrence of said symbol, this function returns a dictionary with an identical key set as the input but with corresponding values representing the huffman codes of each symbol. These huffman codes are represented as vectors (one-dimensional ndarray) with boolean dtype.

The algorithm used in this implementation of huffman dictionary generation is based on that of RosettaCode .

Parameters:symbol_probability_dict (Dict[int, float]) – A dictionary with integer symbol keys and frequency weighting values
Return type:Dict[int, numpy.ndarray]
Returns:A dictionary with the same integer symbol keys as the symbol_probability_dict argument but with huffman code values.

Examples:

>>> import numpy as np
>>> rand_vec = np.array([0, 0, 1, 2, 2, 2, 2, 3, 3, 3])
>>> symbols, values = np.unique(rand_vec, return_counts=True)
>>> symbols
array([0, 1, 2, 3])
>>> values
array([2, 1, 4, 3], dtype=int64)
>>> symbol_probability_dict = dict(zip(symbols, values))
>>> symbol_probability_dict
{0: 2,
 1: 1,
 2: 4,
 3: 3}
>>> huffman_dict(symbol_probability_dict)
{2: array([False]),
 3: array([ True,  True]),
 0: array([ True, False,  True]),
 1: array([ True, False, False])}
dippykit.coding.huffman_tree(symbol_code_dict: typing.Dict[int, numpy.ndarray]) → typing.List[source]

Generates a huffman tree from a symbol-code dictionary

Given a symbol-code dictionary, this function generates a corresponding huffman tree. This huffman tree is a binary tree, and is represented as a length 2 list of nested length 2 lists. The first element in these length 2 lists represents a 0 in the huffman code, and the second element represents a 1 in the huffman code.

Parameters:symbol_code_dict (Dict[int, numpy.ndarray]) – A symbol-code dictionary that maps either signed integer or unsigned integer symbols to binary huffman codes. These binary huffman codes are represented as ndarrays with boolean dtype.
Return type:List
Returns:The huffman tree corresponding to the symbol-code dictionary, represented as a list of nested lists.

Examples:

>>> symbol_code_dict = {0: np.array([ True,  True]),
...                     3: np.array([ True, False]),
...                     4: np.array([False, False]),
...                     1: np.array([False, True,  True]),
...                     2: np.array([False,  True, False])}
>>> huffman_tree(symbol_code_dict)
[[4, [2, 1]], [3, 0]]