A.Y. Denisova, V.V. Sergeyev

Image Processing Systems Institute îf RAS – Branch of the FSRC “Crystallography and Photonics” RAS, Samara, Russia

Full text of article: Russian language.

Abstract**:**

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.

Keywords:

multichannel images, histogram, linked list, hierarchical data structure, non- balanced tree.

Citation:

Denisova AY, Sergeev VV. Algorithms for calculating multichannel image histogram using hierarchical data structures. Computer Optics 2016; 40(4): 535-542. DOI: 10.18287/2412-6179-2016-40-4-535-542.

References:

- Ioannidis Y. The history of histograms (abridged). Proceedings of the 29th international conference on Very large data bases-Volume 29. VLDB Endowment; 2003: 19-30.
- Narendra PM, Goldberg M. A non-parametric clustering scheme for LANDSAT. Pattern Recognition 1977; 9(4): 207-215. DOI: 1016/0031-3203(77)90005-X.
- Asmus VV, Bunichev AA, Pyatkin VP. The Cluster Analysis and Classification with Training of Multispectral Data of Earth Remote Sensing [in Russian]. Journal of Siberian Federal University: Engineering & Technologies 2009; 2(1): 23-31.
- Sidorova VS. Multidimensional histogram and separating of the vector feature space on the unimodal clusters [in Russian]. International conference Graphicon, 2005; 2005: 267-274.
- Mason M, Duric Z. Using histograms to detect and track objects in color video. Applied Imagery Pattern Recognition Workshop, AIPR 2001 30th. IEEE, 2001: 154-159. DOI: 10.1109/AIPR.2001.991219.
- Wharton SW. A generalized histogram clustering scheme for multidimensional image data. Pattern Recognition 1983; 16(2): 193-199. DOI: 10.1016/0031-3203(83)90022-5.
- Ventzel ES. The Theory of possibility [In Russian]. Moscow: “Vysshaya shkola” Publisher; 1999.
- Russinovich Ì, Solomon D. Internal structure of Microsoft Windows: Windows Server 2003, Windows XP and Windows [In Russian]. Saint-Petersburg: “Piter” Publisher; 2005.
- MODIS Level 1B Product User’s Guide. Members of the MODIS Characterization Support Team. NASA/Goddard Space Flight Center, Greenbelt, MD 20771. July 20, 2012.
- Denisov VI, Lemeshko BU, Postovalov SN. Applied statistics. The rules of coherence of experimental distribution with theoretical distribution. Guidelines. Part 1. χ2 tests [In Russian]. Novosibirsk: “NGTU” Publisher, 1998.

© 2009,Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; e-mail: ko@smr.ru; Phones: +7 (846 2) 332-56-22, Fax: +7 (846 2) 332-56-20IPSI RAS