Title :
Two Maximum Entropy-Based Algorithms for Running Quantile Estimation in Nonstationary Data Streams
Author :
Arandjelovic, Ognjen ; Duc-Son Pham ; Venkatesh, Svetha
Author_Institution :
Sch. of Inf. Technol., Deakin Univ., Geelong, VIC, Australia
Abstract :
The need to estimate a particular quantile of a distribution is an important problem that frequently arises in many computer vision and signal processing applications. For example, our work was motivated by the requirements of many semiautomatic surveillance analytics systems that detect abnormalities in close-circuit television footage using statistical models of low-level motion features. In this paper, we specifically address the problem of estimating the running quantile of a data stream when the memory for storing observations is limited. We make the following several major contributions: 1) we highlight the limitations of approaches previously described in the literature that make them unsuitable for nonstationary streams; 2) we describe a novel principle for the utilization of the available storage space; 3) we introduce two novel algorithms that exploit the proposed principle in different ways; and 4) we present a comprehensive evaluation and analysis of the proposed algorithms and the existing methods in the literature on both synthetic data sets and three large real-world streams acquired in the course of operation of an existing commercial surveillance system. Our findings convincingly demonstrate that both of the proposed methods are highly successful and vastly outperform the existing alternatives. We show that the better of the two algorithms (data-aligned histogram) exhibits far superior performance in comparison with the previously described methods, achieving more than 10 times lower estimate errors on real-world data, even when its available working memory is an order of magnitude smaller.
Keywords :
closed circuit television; computer vision; data handling; feature extraction; image motion analysis; maximum entropy methods; statistical distributions; storage management; video surveillance; abnormality detection; available working memory; close-circuit television footage; computer vision; data-aligned histogram; distribution quantile; low-level motion feature; maximum entropy-based algorithms; nonstationary data streams; nonstationary streams; running quantile estimation; semiautomatic surveillance analytics system; signal processing; statistical model; storage space; surveillance system; Entropy; Estimation; Histograms; Indexes; Random variables; Signal processing algorithms; Surveillance; Histogram; Novelty; histogram; novelty; surveillance; video;
Journal_Title :
Circuits and Systems for Video Technology, IEEE Transactions on
DOI :
10.1109/TCSVT.2014.2376137