Compressing Wearable Data: the Discrete Wavelet Transform

Less is more. The limited memory and battery power of wearables necessitates rapid and efficient transmission of data. Reducing the size of transmitted data via compression algorithms, including run-length encoding and Huffman encoding, is one way to minimize power consumption and facilitate storage of ever-accumulating amounts of data.

This lossy method of wearable data compression involves six major steps — the discrete wavelet transform, thresholding, scaling, quantization, combination, and compression — and was tested on five types of data — accelerometry (ACC), electrocardiogram (ECG), electrodermal activity (EDA), photoplethysmogram (PPG), and temperature (TEMP).

Its effectiveness was measured by calculating the compression ratio (CR) and percent root-mean-square difference (PRD). Powerful compression algorithms maximize CR and minimize PRD (i.e. reduce file size and deviation from original data) by attaining the optimal trade-off between these two quantities. This is one method developed for the Biosignal Data Compression Toolbox. You can read the full publication here.

Definitions

compression ratio (CR): an evaluation metric of compression algorithms defined as the ratio of the size of the original file over that of the compressed file

percent root-mean-square difference (PRD): an evaluation metric of compression algorithms that quantifies the difference between the original and reconstructed signal

Wavelet Decomposition

Wavelets are local in both frequency (scale) and time (shift) and can represent many classes of functions in a more compact manner, making them ideal for data compression. The discrete wavelet transform has notable applications in signal processing across many areas of research and industry, including biomedical engineering. It decomposes a signal into multiple levels such that coefficients with significant energy can be retained while discarding those that account for low energy.

Figure 1. The bior4.4 wavelet and its scaling functions

In this method, the bior4.4 wavelet from the biorthogonal family of wavelets is used with five levels of decomposition. The biorthogonal wavelets were chosen over the orthonormal wavelet family due to their flexibility in representing nonstationary signals, advantage in coding gain, and more efficient treatment of boundaries in signal coding applications. At a decomposition level of five, the signal is decomposed into 6 parts: one approximation (e.g. cA5 below) and five detail components (e.g. cD5 to cD1 below). The first components store the lower frequencies and more energy of the signal, with this energy being decomposed successively in the subsequent levels.

Figure 2. Plot of all six levels of decomposition for sample EDA data

The wavelet and levels of decomposition can be customized by modifying the parameters of the wavedec function from the PyWavelets API (see Figure 3 below).

Figure 3. The wavelet decomposition function using the bior4.4 wavelet with 5 levels of decomposition

Thresholding of Wavelet Coefficients + Generation of Binary Map

At each decomposition level, the wavelet coefficients can be more efficiently represented by retaining those that constitute much of the total energy. Since the most energy is held in the approximation coefficients, the percentage of retained energy is highest for this decomposition level of the signal. Within each decomposition level, coefficients below the user-defined threshold are set to zero.

Figure 4. Definition of the threshold percentages for the coefficients in various levels of decomposition

Exact thresholds can be adjusted by the user to achieve the desired balance of CR and PRD. Note that lower thresholds yield higher CR at the cost of higher PRD. In the context of wearables data, a high PRD disables the analyst from accurately developing biomarkers as the reconstructed signal may contain patterns and values that differ significantly from the original signal.

After thresholding, a binary map is generated to indicate which elements of the coefficient arrays were not retained. A value of zero in the binary map array indicates that the coefficient at that index was zeroed while a value of one represents a nonzero, retained coefficient.

Figure 5. A simple example of the threshold process

Figure 6. The cD3 detailed coefficients before and after thresholding with 95% energy retained

Scaling of Coefficients

To prepare the coefficients for quantization, they are normalized to values in the range of zero to one. This involves shifting the coefficients in each decomposition level by their respective minimum value and then dividing by their respective maximum value.

Figure 7. Plot of scaled coefficients for sample EDA data

Quantization

In this step, the wavelet coefficients will be quantized to N bits, meaning each value will be multiplied by 2^(N)-1 and rounded to the nearest integer. To determine the minimum acceptable value of N, the user can set a desired maximum PRD, effectively deciding on a balance between CR and PRD. Note that a greater N yields lower PRD at the cost of a lower CR.

Starting from N=12 bits, the signal is quantized, reconstructed and the associated PRD is calculated. This process is repeated for decreasing integer values of N until the PRD exceeds the user-defined maximum. Once the minimum N value is determined, the signal is quantized to that N number of bits.

Figure 8. Example plot of original EDA signal and reconstructed signals at varying values of N

Combination of Coefficient Arrays and Binary Maps

So far, the wavelet coefficients and their associated binary maps were separated by their decomposition levels. To improve the compression ratio, all six wavelet coefficient arrays are compiled into one array, as are the six binary maps.

Compression of Coefficients and Binary Map

If N is less than or equal to 8, the coefficients are first compressed via simple bit packing. Otherwise, they are compressed in a lossless manner via Huffman encoding. Unlike the coefficient array, the binary map contains highly repetitive patterns of zeros and ones. Hence, the binary map is encoded via variable run-length encoding.

Simple Bit Packing

Figure 8. A simple example of encoding via simple bit packing (N=4)

The flowchart above summarizes the process of simple bit packing. This method is only effective if N is less than 8. For example, for N=5, each quantized coefficient only contains five bits of information, yet is stored as a byte, occupying eight bits. Through this method, the extra three bits from each coefficient can be eliminated, thereby reducing the amount of data stored.

Note that because the total number of bits may not be divisible by 8, the number of bits of the last value must be stored in the variable num_bits_last_byte_coeffs for use in later decompression (see example in Variable Run-Length Encoding).

Variable Run-Length Encoding

In essence, this encoding algorithm represents the zeroes and ones in terms of their run count. Given that the value in the binary map must be zero or one and that it always alternates between those two values, only three details need to be stored: the initial value, run count, and number of bits of the last “byte”.

Figure 9. A simple example of encoding via variable run-length encoding

The diagram above summarizes the process with a sample binary map consisting of three zeroes followed by 729 ones, 2020 zeros, and a one. Each consecutive run can be represented by a two-bit header, along with additional bits if the run count is greater than or equal to four.

Headers ‘00’, ‘01’, ‘10’, and ’11’ correspond to a run count of one, two, three, and four or greater. In the case that the run count is four or greater (e.g. the 729 ones and the 2020 zeroes), the next 4 bits after the header will represent the n number of bits required to read the run count. For example, 10 bits are required to represent the number 729 in binary. Hence, the four bits that follow the ‘11’ header are ‘1010’, or 10 in decimal form. The next n bits are the binary representation of the actual run count (e.g. ‘1011011001’ for a run count of 729).

As with simple bit packing, these binary bits are then concatenated to an array of binary strings, with each string consisting of 8 bits. Each of these 8-bit values are converted from binary to decimal.

Again, because the total number of bits may not be divisible by 8, the number of bits of the last value must be stored for use in later decompression. In the example above, the last value in the compressed binary map ‘10000’ consists of five bits, so five is stored in the variable num_bits_last_byte_binary_map.

Across all five data types, variable run-length encoding yielded an average compression ratio of 11.78.

Huffman Encoding

The tcmpr Python package is used to perform Huffman encoding on the combined coefficient array and the combined binary map, both of which are saved as text files. This method of encoding is lossless and improved the overall compression ratio across all five data types by an average factor of 2.87.

So, is this the optimal method for wearables data?

The high customizability of the parameters for this compression method allow for further optimization in wearables data applications and beyond. Feel free to modify the wavelet, levels of decomposition, threshold values, threshold method, number of quantization bits, maximum number of bits to represent run length, and other parameters to improve the CR and PRD.

Remember: Digital biomarker development depends on the transmission, storage, and analysis of extensive amounts of data and compression makes that possible.

More resources

The above compression module, inspired by this wavelet-based ECG compression algorithm, is but a subset of the tools available on the Digital Biomarker Discovery Pipeline for digital biomarker research. To learn more, visit dbdp.org, access the GitHub repo, or follow @TheDBDP on Twitter.