Probabilistic model of error in fixed-point arithmetic Gaussian pyramid

The half-octave Gaussian pyramid is an important tool in computer vision and image processing. The existence of a fast algorithm with linear computational complexity makes it feasible to implement the half-octave Gaussian pyramid in embedded computing systems using only integer arithmetic. However, the use of repeated convolutions using integer coefficients imposes limits on the minimum number of bits that must be used for representing image data. Failure to respect this limits results in serious degradation of the signal to noise ratio of pyramid images. In this paper we present a theoretical analysis of the accumulated error due to repeated integer coefficient convolutions with the binomial kernel. We show that the error can be seen as a random variable and we deduce a probabilistic model that describes it. Experimental and theoretical results demonstrate that the linear complexity algorithm using integer coefficients can be made suitable for video rate computation of a half-octave pyramid on embedded image acquisition devices.