Algorithms for calculating multichannel image histograms using hierarchical data structures

In the article we offer a novel approach to calculating multichannel image histograms using hierarchical data structures. The proposed methods result in a histogram-tree which has many advantages over existing data structures traditionally used for multidimensional histograms. The suggested data structure requires a significantly smaller memory space for storage in comparison with a histogram that is presented as a frequency table for all possible brightness values (histogram-hypercube). The histogram-tree provides a dramatic decrease in speed in comparison with the list of unique brightness values and their frequencies (histogram-list). Moreover, the histogram-tree allows one to approximate the probabilities of brightness values which are not presented in the analyzed image in contrast with the histogram-list.
The possibility of histogram approximation is very important for practical applications. Such approximation for histogram-tree is constructed by means of tree reduction. Nodes with frequencies lower than a given threshold are removed from the histogram-tree. The reduced histogram-tree benefits from the decrease of the required memory space while maintaining the accuracy of the original probability density distribution representation.
We propose two algorithms for constructing a histogram-tree. The “depth” algorithm operates with image pixels sequentially. For each pixel it constructs appropriate branches and nodes until the maximum depth of the tree is achieved. This algorithm has a recursive realization and is more time efficient than the other one. The “across” algorithm performs a multiple scan of the image, each time filling just one tree level. This algorithm allows one to operate with images with a larger number of channels than the “depth” algorithm because it is more memory efficient in the runtime when approximating a histogram. Both algorithms build the histogram-tree significantly faster when compared with the construction of the histogram-list.
The theoretical estimates and experimental results described in the article demonstrate that computing histogram of multichannel images using histogram-tree has many advantages over the histogram-hypercube and histogram-list.